166288 - Autocomplete from bookmarks URLs as well

Status: RESOLVED FIXED

(Camino Graveyard :: Location Bar & Autocomplete, enhancement)

Description

[S Woodside]

This request is to complete URLs using the bookmarks as well as pages in the
history.

IE has this feature. I occasionally delete the history cache ;-) and it's nice
that I can add pages to my bookmarks and they'll always be autocompleted. It's
another way to access the bookmarks file, i.e., by starting to type the url of
the bookmark.

Comment 1

[Greg K.]

Confirmed using Chimera/2002090205 on 10.1.5. Dependent on bug 158325?

Comment 2

[Nicholas Suhor]

Agreed!  In fact, I think that this is my primary method of accessing bookmarks.
 Command-L to the Location bar and start typing.

Comment 3

[Greg K.]

*** Bug 167366 has been marked as a duplicate of this bug. ***

Comment 4

[Amanuel]

Since there seems to be progress to get keywords working, this may be a good time to 
see if the target milestone can be moved to something earlier...say 0.7 ;-) It can't be that 
complex to add this feature...can it?

Comment 5

[Visa Kopu]

Eh? Bookmark keywords *are* working in the latest nightlies.

Comment 6

[S Woodside]

This bug isn't about keywords, it's about autocompletion based on URLs in
bookmarks. Keywords are cool, but have to be set manually. autocompletion will
just automatically fill in based on the pool of bookmarked urls.

Comment 7

[Amanuel]

My comment/request was to move this feature's (auto completion on bookmarks data) 
target milestone closer since it seems work is being done on the keywords feature. 

As an aside currently two bookmarks with the same keywords results in the keyword 
resolving to the first item in the bookmarks db. If it put up a dropdown like the auto 
complete appeared we could then have matches showing up on paritial 
keywords...hmm...I suppose this comment could be put elswhere (another bug report) 
discussing keywords as well.

Comment 8

[S Woodside]

Just to be completely clear, this bug is to add the URLs of all of your
bookmarks to the list of autocompletion URLs.
Autocompleting based on the "name" of the bookmark is Bug 162450

Comment 9

[Stephane Moureau]

*** Bug 190183 has been marked as a duplicate of this bug. ***

Comment 10

[Gabriel Radic]

Safari does this too, and it's very handy.

Comment 11

[guanxi]

*** This bug has been marked as a duplicate of 101642 ***

Comment 12

[louis bennett]

this bug is for Camino (bug 101642 is for Mozilla) -- do we want to keep the two
separate?

Comment 13

[guanxi]

Apologies, I didn't notice -- does it require a separate solution?

Comment 14

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

Do we need to do this ourselves in Camino, or will the SeaMonkey bug, if it ever
gets fixed, be sufficient?

Comment 15

[Simon Fraser [no longer active]]

Camino's bookmark code is all its own.

Comment 16

[Didier Oswald]

(In reply to comment #15)
> Camino's bookmark code is all its own.

Is this feature planed for the 1.0 release ?

Comment 17

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

The "Target Milestone" field indicates the Camino release for which a bug is
tentatively targeted.

Comment 18

[Yuan Qi]

I think even Safari 2 has this feature! We should try to keep up with our
competition...

Comment 19

[Chris Lawson (gone)]

Any brilliant ideas on how to handle this? I got as far as thinking we need to pull in bookmarks data somewhere in the general neighbourhood of line 379 in AutoCompleteTextField.mm :)

cl

Comment 20

[Simon Fraser [no longer active]]

What I would do is emulate
-(NSArray *)resolveBookmarksKeyword:(NSString *)keyword;

Comment 21

[Chris Lawson (gone)]

Taking. If I can really bust my ass on this and get a patch ground out in the next seven days or so, is there a chance this could make 1.0?

cl

Comment 22

[Simon Fraser [no longer active]]

(In reply to comment #21)
> Taking. If I can really bust my ass on this and get a patch ground out in the
> next seven days or so, is there a chance this could make 1.0?

If it's robust, fast, and passes review, yes, I would think so.

Comment 23

[Simon Fraser [no longer active]]

When ready, please test with the 3.1Mb bookmarks file from bug 236373 to make sure it's fast enough.

Comment 24

[Samuel Sidler (old account; do not CC)]

*** Bug 318582 has been marked as a duplicate of this bug. ***

Comment 25

[Håkan Waara]

Is there some specific reason why bug 340469 would block this from happening?

Comment 26

[Chris Lawson (gone)]

(In reply to comment #25)
> Is there some specific reason why bug 340469 would block this from happening?

Because all this work would have to be done again when we migrate away from xpfe's autocomplete implementation?

That is, unless someone doesn't mind doing a bunch of work twice.

cl

Comment 27

[Håkan Waara]

(In reply to comment #26)
> (In reply to comment #25)
> > Is there some specific reason why bug 340469 would block this from happening?
> 
> Because all this work would have to be done again when we migrate away from
> xpfe's autocomplete implementation?
> 
> That is, unless someone doesn't mind doing a bunch of work twice.

I don't know of a compelling reason to spend time migrating to toolkit's autocomplete. From what I heard in #developers, it's just different interfaces to the same stuff basically.

Comment 28

[Simon Fraser [no longer active]]

xpfe's autocomplete really doesn't do much for us. We could just do the autocomplete with cocoa classes.

Comment 29

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

Moving to 1.2, but we'll take it if it's fixed :)

Comment 30

[Simon Fraser [no longer active]]

Lump into bug 162450?

Comment 33

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

Mass un-setting milestone per 1.6 roadmap.

Filter on RemoveRedonkulousBuglist to remove bugspam.

Developers: if you have a patch in hand for one of these bugs, you may pull the bug back to 1.6 *at that point*.

Comment 35

[Dan Weber]

Attachment: Patch 1

This is a very early patch for autocompleting from bookmarks. It also removes all old xpfe code. Plans for the future include making it multithreaded and improving the matching/sorting algorithm. This patch depends on the code changes in bug 495496.

Comment 36

[Dan Weber]

Attachment: Patch 1

oops

Comment 37

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

If this patch is what I think it is, I have a question: it's not necessarily a requirement for this patch, but is the new autocomplete code written in such a way that the current Keychain multiple accounts autocomplete stuff (originally implemented in bug 178607) can switch to it easily?

Comment 38

[Dan Weber]

Attachment: Patch 2

Added multithreading

Comment 39

[Dan Weber]

Attachment: Patch 2

Comment 40

[Stuart Morgan]

Comment on attachment 381994 [details] [diff] [review]
Patch 2

This is just a quick first-pass, since I didn't have time to look at this as much as I had hoped over the weekend.

First off, I totally spaced when we talked about this on Friday... The history and bookmark systems aren't threadsafe :( I don't think we want to add locking overhead to every bookmark and history item accessor, so making them threadsafe is probably not a realistic option. I think what you'll want to do is make this an asynchronous search on the main thread, which is a bit trickier but not terrible. Basically, you would grab the whole set you are searching, stuff it into an array, then process that in chunks with a series of performSelector:withObject:afterDelay calls to allow user events to filter in and get handled between chunks.

>+      NSEnumerator* bookmarksEnum = [[manager bookmarkMenuFolder] objectEnumerator];
>+      while ((curItem = [bookmarksEnum nextObject])) {
>+        if ([curItem isKindOfClass:[Bookmark class]]) {
>+          if ([self item:(Bookmark *)curItem isAMatchForString:searchString])
>+            [results addObject:(Bookmark *)curItem];

This is only searching direct children of the bookmark menu. You actually want allChildBookmarks of bookmarkRoot (I know, the docs in the bookmark code are not so good :( )

>+      NSSortDescriptor *visitCountDescriptor = [[[NSSortDescriptor alloc] initWithKey:@"numberOfVisits"
>+                                                                            ascending:NO] autorelease];
>+      [results sortUsingDescriptors:[NSArray arrayWithObject:visitCountDescriptor]];

Given that you only want a handful of results, you could likely make your search substantially more efficient by having the caller tell you how many results they want, doing this sort first, and then only doing string matching until you have the number of matches you need.

Similarly for History.

>+  if ([searchString hasPrefix:@"http://"] && [searchString length] > 7 && [url hasPrefix:searchString] ||
>+      [searchString hasPrefix:@"https://"] && [searchString length] > 8 && [url hasPrefix:searchString] ||
>+      [searchString hasPrefix:@"www."] && [searchString length] > 4 && [url hasPrefix:[NSString stringWithFormat:@"http://%@", searchString]] ||
>+      [searchString hasPrefix:@"www."] && [searchString length] > 4 && [url hasPrefix:[NSString stringWithFormat:@"https://%@", searchString]] ||
>+      [url hasPrefix:[NSString stringWithFormat:@"%@%@", @"http://www.", searchString]] ||
>+      [url hasPrefix:[NSString stringWithFormat:@"%@%@", @"https://www.", searchString]])
>+    return YES;
>+  return NO;

I'm confused by the logic here. It looks like it's impossible to find, say, http://foo.com by typing foo. Also, given that you are going to be doing this in what can be a really long loop, it would be really good if you could avoid making lots of temporary strings. If nothing else you should make your strings once, instead of once per bookmark/history item, since they don't change. But I'm not sure you even need that, since I think you could get the effect you want with something along the lines of:
1) See if the strings match starting at index 0.
2) If not, find the index after the 'scheme://', and see if it matches starting there (either using rangeOfString:options:range: and careful range construction and length to force matching at that index, or something similar that doesn't involve creating a new string),
3) If not, see if there is a www after the scheme:// part, and repeat step 2 from that index.

(In fact, you could generalize 3 to walk each subdomain, so that http://foo.bar.baz.com could be found with baz.com, or bar.baz.com, but we can play with that in a follow-up bug.)


You'll also need to re-sync changes from the files in your other tree before the next diff here, since the diff gets confusing where you have changes to now-refactored code, but without the refactoring. You'll probably want to do the current round of appearance changes before syncing up though.

Comment 41

[S Woodside]

This is exciting, I filed this buy 7 years ago.

Regarding searchString, surely a regular expression would be more efficient and more clear. Or, isn't there a function somewhere else that already does this for history items, and you can just call that function??

Regarding the bookmarks iteration, you could probably get less LoC if you used fast enumeration like "for( Bookmark * curBookmark in [manager allChildBookmarks] )" (or whatever) (but will that work on older OS's?)

Also, you could make it even more beautiful using NSArray extensions for Higher Order Messaging like http://www.metaobject.com/blog/2009/01/simple-hom.html ...

  NSArray * candidates = [[allBookmarksArray collect] completeForString:searchString];
  candidates = [some code that returns the first N non-nil entries of candidates];

Then in Bookmark object, define a method - completeForString:(NSString*)searchString; which returns the bookmark if it should be a candidate for autocompletion and nil if it isn't. Simple as pie! And it looks good too.

In AutoCompleteCell, why not use @properties to avoid all of those method declarations? Is this something to do with backwards compatibility?

One last thing, I'm not sure if I'm seeing code duplication for History and Bookmarks. A DRYer way to do that would be either if they share a superclass, or if they both implement a protocol, and then you would only have one set of code that acts against that superclass/protocol.

Hopefully some of this is useful.

Comment 42

[Stuart Morgan]

(In reply to comment #41)
> (but will that work on older OS's?)

Nope, fast enumeration is ObjC 2 (10.5+)

> Also, you could make it even more beautiful using NSArray extensions for Higher
> Order Messaging

That seems unlikely to be compatible with chunked asynchronous processing.

> Then in Bookmark object, define a method -
> completeForString:(NSString*)searchString; which returns the bookmark if it
> should be a candidate for autocompletion and nil if it isn't.

I'd rather we not start pushing the details of the autocomplete behavior onto low-level model objects.

> In AutoCompleteCell, why not use @properties to avoid all of those method
> declarations?

Properties are ObjC 2.

> One last thing, I'm not sure if I'm seeing code duplication for History and
> Bookmarks. A DRYer way to do that would be either if they share a superclass,
> or if they both implement a protocol, and then you would only have one set of
> code that acts against that superclass/protocol.

There are a lot of problems with the bookmark and history code, but refactoring the enumeration structure of both systems is really out of the scope of both this bug and the SoC project.

Comment 43

[Dan Weber]

Attachment: Patch 3

Comment 44

[Dan Weber]

Attachment: Patch 3

Comment 45

[S Woodside]

Good to see regex now :-)

(In reply to comment #42)
> > Also, you could make it even more beautiful using NSArray extensions for Higher
> > Order Messaging
> That seems unlikely to be compatible with chunked asynchronous processing.

Yes... I don't see how you would easily chunk it without diving into the HOM code. But doing it that way seems nasty to me. Would making those two classes thread-safe (at least to be written and read at the same time) really be that hard? It may well be useful down the road or even now in other places. Alternatively, is copying implemented on these data sources... spawn a thread with copies and let it run wild.

> > Then in Bookmark object, define a method -
> > completeForString:(NSString*)searchString; which returns the bookmark if it
> > should be a candidate for autocompletion and nil if it isn't.
> I'd rather we not start pushing the details of the autocomplete behavior onto
> low-level model objects.

Hrm. I see what you're saying, but. The problem is, by the same token, why should the autocompletion code know the internal working of the History & Bookmark classes. I'm saying that you would ask the bookmark object if, given a search string, it feels like it should be included in the autocomplete list. To me that's a better abstraction model. After all, if the bookmark model changes, they will need to change that code, and so it should be in the model code.

Instead, you're adding on a layer that needs to be kept in sync with the underlying data models and will break if they change substantially.

Comment 46

[Stuart Morgan]

(In reply to comment #45)
> Would making those two classes thread-safe (at least to be written and read
> at the same time) really be that hard?

We aren't going to add the overhead of complete thread safety to two large subsystems of Camino just because a perfectly reasonable solution to this one problem isn't quite as elegant as it could be.

> Alternatively, is copying implemented on these data sources... spawn a thread
> with copies and let it run wild.

The whole point of this change is to prevent performance problems for people with extremely large histories and/or bookmark collections, so copying everything would not solve the problem; it would probably make it substantially worse.

> why should the autocompletion code know the internal working of the History &
> Bookmark classes

It doesn't. The fact that bookmarks and history have things like titles, histories, visit counts, and exist in enumerable collections are not "internal workings", they are the API. That's the whole point of those model objects.

> I'm saying that you would ask the bookmark object if, given a
> search string, it feels like it should be included in the autocomplete list.
> To me that's a better abstraction model.

Yes, I understand what you are saying, I just don't agree at all. I think we're going to have to just agree to disagree on this, because I really don't want this bug to be sidetracked by sweeping and un-resolvable arguments about programming philosophies.

Comment 47

[Stuart Morgan]

Comment on attachment 382621 [details] [diff] [review]
Patch 3

Definitely getting there :)

General note: this patch has a whole lot of tabs in it that all need to be converted to spaces. Unless you are also working on other projects that use tabs, you could avoid this problem in the future by changing your Xcode settings for indentation.


>+#import "MAAttachedWindow.h"
> #import "BrowserWindowController.h"
> #import "BrowserTabViewItem.h"
> #import "NSString+Utils.h"
>-#import "MAAttachedWindow.h"

Looks like the header was added separately in the two trees; make them match to remove the needless churn here.

>+- (BOOL)isEqual:(Bookmark *)bookmark {
>+	if ([[bookmark url] isEqualToString:mURL])
>+		return YES;
>+	return NO;
>+}

This worries me; are you certain that this isn't going to have unexpected side-effects in other parts of the bookmark code? This definition is true for you, but not for code dealing in actual user bookmarks.

>@interface AutoCompleteDataSource : NSObject

Needs a class-level comment explaining what the class does/is for.

>+	HistoryItem*            mRootHistoryItem;
>...	
>+	NSMutableArray*         mBookmarkData;
>+	NSMutableArray*         mHistoryData;
>+	NSMutableArray*         mBookmarkResults;
>+	NSMutableArray*         mHistoryResults;
>+	
>+	NSImage*                mGenericSiteIcon;     // owned
>+	NSImage*                mGenericFileIcon;     // owned

All of these are owned, so they should all be marked as such.

>+- (void)clearResults;
>+- (void)loadSearchableData;
>+- (void)performSearchWithString:(NSString *)searchString delegate:(id)delegate;
>+- (int)rowCount;
>+- (id)resultForRow:(int)aRow columnIdentifier:(NSString *)aColumnIdentifier;

These all need comments documenting them.

>+const unsigned int kChunkSize = 100;

Needs a more descriptive name.

>+// This whole class was stolen from HistoryMenu.
>+@interface HistoryDataSourceOwner : NSObject

Needs a class-level comment describing it (and explaining why we use it instead of creating one on demand).

>+@interface AutoCompleteDataSource (Private)
>+- (BOOL)item:(id)item isAMatchForString:(NSString *)searchString;
>+- (void)updateResultsForString:(NSString *)searchString;

Need method-level comments.

>+		if ([curItem isKindOfClass:[Bookmark class]] && ![mBookmarkData containsObject:curItem])
>+			[mBookmarkData addObject:curItem];

Checking for duplicates up-front is unnecessarily expensive; you'd be better off checking for duplicates as you build your final result list instead, since you'll only have to compare a few bookmarks against at most four others, rather than every bookmark against all earlier bookmarks.

(I'd be curious to know whether this is actually the reason you were seeing pauses on start as discussed on IRC, rather than the sorting.)

>+	// Process one chunk of bookmarks.
>+	for (unsigned int i = mChunkRange.location; i < [mBookmarkData count] && i < NSMaxRange(mChunkRange)
>+		 && [mBookmarkResults count] < kMaxResultsPerHeading; i++)
>+		if ([self item:[mBookmarkData objectAtIndex:i] isAMatchForString:searchString])
>+			[mBookmarkResults addObject:[mBookmarkData objectAtIndex:i]];
>+	// Process on chunk of history items.
>+	for (unsigned int i = mChunkRange.location; i < [mHistoryData count] && i < NSMaxRange(mChunkRange)
>+		 && [mHistoryResults count] < kMaxResultsPerHeading; i++)
>+		if ([self item:[mHistoryData objectAtIndex:i] isAMatchForString:searchString])
>+			[mHistoryResults addObject:[mHistoryData objectAtIndex:i]];

Rather than duplicate this code, abstract the logic into a helper method that takes a source array and a destination array, since those are the only things that differ between the two blocks.

>+	// Check if finished.
>+	BOOL bookmarksDone, historyDone = NO;
>+	if ([mBookmarkResults count] == kMaxResultsPerHeading || NSMaxRange(mChunkRange) >= [mBookmarkData count])
>+		bookmarksDone = YES;
>+	if ([mHistoryResults count] == kMaxResultsPerHeading || NSMaxRange(mChunkRange) >= [mHistoryData count])
>+		historyDone = YES;

You can also push this logic into the helper method as a return value.

>+		if ([mBookmarkResults count] > 0) {
>+			AutoCompleteCellInfo *info = [[[AutoCompleteCellInfo alloc] init] autorelease];
>+			[info setIsHeader:YES];
>+			[info setTitle:@"Bookmarks"];
>+			[mBookmarkResults insertObject:info atIndex:0];
>+		}
>+		if ([mHistoryResults count] > 0) {
>+			AutoCompleteCellInfo *info = [[[AutoCompleteCellInfo alloc] init] autorelease];
>+			[info setIsHeader:YES];
>+			[info setTitle:@"History"];
>+			[mHistoryResults insertObject:info atIndex:0];
>+		}
>+		mChunkRange = NSMakeRange(0, kChunkSize);
>+		[mDelegate searchResultsAvailable];

Break this into its own method (e.g., reportResults) to keep the logic in this method focused on the processing. You'll also want to clean out members that are no longer necessary, like the *Data arrays, so they don't sit around.

>+- (BOOL)item:(id)item isAMatchForString:(NSString *)searchString {

Nit; why not matchesString: rather than isAMatchForString:?

>+	NSString *url = [item url];

Remove the temp variable; it's short and only used once.

>+	NSString *regex = [NSString stringWithFormat:@".*(.*://)%@(www.)?%@.*",
>+                     [searchString rangeOfString:@"://"].location != NSNotFound ? @"?" : @"", searchString];

I've never used NSPredicate regexes; do they only match if the *entire* string matches? If not, the leading and trailing .* shouldn't be necessary. The .* inside the parens can definietly go. I believe the www. can move into that earlier conditional as well.

However, the whole thing would be a lot clearer as an if/else that constructed a different regex for the two cases rather than playing tricks with optional sections that can't actually exist in one case.

>+  NSPredicate *regexTest = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", regex];

This should be a member constructed when the search starts and lasting until results are returned, not created potentially thousands of times over the course of the filtering.


>+  if ([regexTest evaluateWithObject:url] == YES)
>+    return YES;
>+	return NO;

Just do |return [regexTest evaluateWithObject:url];|

>+- (id)resultForRow:(int)aRow columnIdentifier:(NSString *)aColumnIdentifier {
>+	AutoCompleteCellInfo *info = [[[AutoCompleteCellInfo alloc] init] autorelease];

This object is going to be the same every time (modulo a site icon coming in during autocomplete, which we don't really care about). It would be more efficient, and probably clearer, to convert the two Results arrays into one array of pre-constructed AutoCompleteCellInfo objects and just vend those directly here. That would also avoid the odd type mismatch of the headers.

(It would also address my isEqual: concern; if you define an isEqual: on your ACCI class (making sure it works correctly with headers) you can use that instead of changing the bookmarks code.)

>-@class MAAttachedWindow;
> @class AutoCompleteDataSource;
> @class ClickMenuImageView;
> @class PageProxyIcon;
>+@class MAAttachedWindow;

Again, avoid the churn here.

>+// get/set the autcomplete session
> - (PageProxyIcon*)pageProxyIcon;
> - (void)setPageProxyIcon:(NSImage *)aImage;
> - (void)setURI:(NSString*)aURI;

This comment seems wrong.

>+++ /Users/danweber/Documents/mozilla/camino/src/browser/AutoCompleteTextField.mm	2009-06-10 

This file is riddled with changes that look like they are just s/  /[tab]/, so I'm having a really hard time reviewing it; I'll take a look in the next spin. (It's a good idea to skim your patch files before posting them to make sure there aren't obvious issues like this.)

Comment 48

[S Woodside]

I don't want to hold this bug up :-)

(In reply to comment #47)
> >+	NSString *regex = [NSString stringWithFormat:@".*(.*://)%@(www.)?%@.*",
> >+                     [searchString rangeOfString:@"://"].location != NSNotFound ? @"?" : @"", searchString];
> 
> I've never used NSPredicate regexes; do they only match if the *entire* string
> matches? If not, the leading and trailing .* shouldn't be necessary. The .*
> inside the parens can definietly go. I believe the www. can move into that
> earlier conditional as well.
> 
> However, the whole thing would be a lot clearer as an if/else that constructed
> a different regex for the two cases rather than playing tricks with optional
> sections that can't actually exist in one case.

Seems like an great demonstration case for the value of implementing unit testing in Camino.

Comment 49

[Dan Weber]

Attachment: Patch 4

Comment 50

[Dan Weber]

Attachment: Patch 4

Comment 51

[Dan Weber]

Attachment: Patch 4

Comment 52

[S Woodside]

Some more practical comments are below, particular w.r.t. the regex.

> // Starts the search for matching bookmarks/history items using the string passed
> // from AutoCompleteTextField. This is an asynchronous method--when the search is
> // complete, searchResultsAvailable will be called on the delegate.
> - (void)performSearchWithString:(NSString *)searchString delegate:(id)delegate;

You don't want to have a delegate protocol?

nit, but searchCompleted would sound more standard I think

> // Adds the appropiate header to the specified results array. This is

typo appropiate > appropriate

>   [mBookmarkData addObjectsFromArray:[bookmarkRoot allChildBookmarks]];

You might be able to take 3 lines down to 1 if you use mBookmarkData = [NSArray arrayWithArray:[bookmarkRoot allChildBookmarks]];

>  HistoryItem *rootHistoryItem = [historyDataSource rootItem];
>  NSEnumerator* historyEnum = [[rootHistoryItem children] objectEnumerator];

Can save a line without losing readability with NSEnumerator* historyEnum = [[[historyDataSource rootItem] children] objectEnumerator];

Also you've got inconsistency there in whether you've got the space before or after the *.

>  while ((curChild = [historyEnum nextObject]))   
>    if ([curChild isKindOfClass:[HistorySiteItem class]])
>      [mHistoryData addObject:curChild];

I don't know what the moz style guide says but I'd add curly brackets to this for clarity & safety. (and in other places where you have one-line ifs)


>  NSString *regex;
>  if ([searchString rangeOfString:@"://"].location == NSNotFound)
>    regex = [NSString stringWithFormat:@".*://(www.)?.*%@.*", searchString];
>  else
>    regex = [NSString stringWithFormat:@".*(www.)?.*%@.*", searchString];

OK, I'm looking at this and thinking, if the searchString DOES have :// then it's probably something like "http://foo"... in which case regex = @".*(www.)?.*http://foo.*" ... in which case the (www.)? is impossible in a URL to occur before the protocol designator. Are you trying to prefer matching against the text immediately following "://(www.)?" ? That won't work given these regex's because it only returns true/false, not a score. the regex ".*(www.)?.*" will collapse down to ".*" in all cases. So you might as well use:

  NSString *regex = [NSString stringWithFormat:@".*%@.*", searchString]; // may as well use rangeOfString:

But... looking back at Patch 2 isAMatchForString: what it did there is different. In that case you would ONLY match against the beginning of a URL, in which case the proper regex would be something like: "^(http:\/\/|https:\/\/)?(www\.)?%@.*". (I'm using \ to make / and . into literals, since they are normally special.) In fact I think that's exactly what you want.

>      AutoCompleteCellInfo *info = [self cellInfoForItem:dataItem];

You might achieve some small speed-up if you move the definition of info outside the loop.

>  BOOL bookmarksDone, historyDone = NO;

You might actually want BOOL bookmarksDone = NO, historyDone = NO; but it doesn't matter because ObjC sets them to NO anyway I think.

>  /*PRInt32 defaultRow;

I would suggest deleting instead of commenting out this block...

Comment 53

[Stuart Morgan]

Comment on attachment 383806 [details] [diff] [review]
Patch 4

>+/*
>+ * This class is in charge of retrieving/sorting the history and bookmark results
>+ * for the location bar autocomplete, and is also the datasource for the table view
>+ * in the autocomplete popup window. All of the work is performed on the main thread
>+ * using a chunked asynchronous method (see updateResultsForString:), which should
>+ * allow everything to run smoothly even with large number of bookmark/history items.
>+ */

C-style comments rather than C++ please.

>+  NSPredicate*            mRegexTest;

Needs an // owned

>+// This method is only called when the autocomplete popup window is opening.

Method comments should generally not document how they are currently being used, since it's easy for that information to become out of sync with reality.

>+const unsigned int kNumberOfItemsPerChunk = 100;

>+// Called after every update to check if we are done with the search.
>+// We are done when we have finished looking at all bookmark/history
>+// data or when we have enough results to satisfy kMaxResultsPerHeading.
>+// If we are done, reports this to the delegate; otherwise, calls
>+// updateResultsForString to process the next chunk.
>+- (void)reportResults;

This is doing a lot more than what the name suggests; too much got moved into it. reportResults should be something that's called only when you are done, and the rest should be a different method.

>+// Adds the appropiate header to the specified results array. This is
>+// called after every chunk update so even results that have not yet
>+// finished will have a header.

Why? It shouldn't matter what state the result array is in before the search is completed. Is the autocomplete window using the results array live while it's still in flux? If so, there needs to be a new stable intermediate array so that doesn't happen, or there will be a lot of flickering.

>--(id)init
>-{
>+-(id)init {

Camino style is (unfortunately) the two-line version, so all the old and new methods should use it. (Sorry I didn't notice this in earlier patches; Google style is different so the second way looks normal to me.)

>+  [mBookmarkData release];
>+  [mHistoryData release];
>+  [mBookmarkResults release];
>+  [mHistoryResults release];

Release your regex as well.

>+  [historyDataSource setSortColumnIdentifier:@"last_visit"]; // always sort by last visit

Remove the comment here, since it doesn't add anything.

>+    regex = [NSString stringWithFormat:@".*://(www.)?.*%@.*", searchString];

You want ".*://(www.)?%@.*", unless you are trying to make URL matching a whole lot more flexible. 

>+    regex = [NSString stringWithFormat:@".*(www.)?.*%@.*", searchString];

And I believe this should just be "%@.*".

Can you put a comment above the regex construction section explaining what the expected behavior of the matching is? It would be easier to see if they were right given an English description of the intended behavior.

>+       && [resultsArray count] < kMaxResultsPerHeading; i++) {

This isn't correct if you pre-add the headings, so if that doesn't change this will need to.

>   [info setIcon:mGenericSiteIcon];
>...
>   if (cachedFavicon) {
>     [info setIcon:cachedFavicon];
>+  } else if ([[info url] hasPrefix:@"file://"]) {
>     [info setIcon:mGenericFileIcon];
>   }

It would be clearer to move the mGenericSiteIcon part into a final |else| on this conditional.

>+  BOOL bookmarksDone, historyDone = NO;

bookmarksDone is uninitialized here. Generally you should avoid declaring multiple variables on a line because it hides bugs like this one (and causes headaches when the type is a pointer).

>+  if (results == mBookmarkResults)
>+    [info setTitle:@"Bookmarks"];
>+  else if (results == mHistoryResults)
>+    [info setTitle:@"History"];

Make this string an argument so you don't have to do the comparison against the member variables.

>+- (int)rowCount {
>+  return [mBookmarkResults count] + [mHistoryResults count];
>+}

If you have a more stable data source array, as mentioned above, you can simply this and resultForRow:columnIdentifier:

>+- (int)numberOfRowsInTableView:(NSTableView*)aTableView {
>+  return [mBookmarkResults count] + [mHistoryResults count];

return [self rowCount];

> - (void) completeDefaultResult
> {
>-  PRInt32 defaultRow;
>+  /*PRInt32 defaultRow;
>   mResults->GetDefaultItemIndex(&defaultRow);
>   
>   if (mCompleteResult && mCompleteWhileTyping) {
>     [self selectRowAt:defaultRow];
>     [self completeResult:defaultRow];
>   } else {
>     [self selectRowAt:-1];
>-  }
>+  }*/

Why have you removed the use of this method? That will break the hidden pref to do inline autocomplete.

>+    [title drawInRect:NSMakeRect(cellFrame.origin.x + 10, 
>+                                 cellFrame.origin.y + kTextVerticalPadding + 2,
>+                                 cellFrame.size.width - 20,

No magic numbers! :) You should have a horizontal padding constant here (the duplication with the other one is fine, since there's no reason headers and results would necessarily always want the same padding), and a descriptive constant for whatever "2" means here.

>+  BOOL               mIsHeader; // if it's a header, we'll use the mSiteTitle as the header text

Remove the comment; that's a view-level decision, and this is a model object.

Comment 54

[hhaamu]

>+    regex = [NSString stringWithFormat:@".*://(www.)?.*%@.*", searchString];

This should probably be (www\.), otherwise it will hit domains starting with "www" ("wwwf.org")

Comment 55

[Dan Weber]

Attachment: Patch 5

Comment 56

[Stuart Morgan]

Comment on attachment 384733 [details] [diff] [review]
Patch 5

r=smorgan with minor nits addressed. It's fun to be able to search for my bookmarks :) (And I'm definitely excited about title search after this part lands!)

>+// using a chunked asynchronous method (see updateResultsForString:), which should

Remove the method name, since it's clearly easy for the comment to get out of sync with reality ;)

>+- (void)clearResults;
>...
>+- (void)updateResults;

These names are confusing now that you have mResults, which they don't operate on. How about "resetSearch" and something like "runSearch" or "processNextSearchChunk"?

>+- (AutoCompleteResult *)cellInfoForItem:(id)item;

Needs renaming to match the new class (autoCompleteResultForItem:)

>+  NSSortDescriptor *visitCountDescriptor = [[[NSSortDescriptor alloc] initWithKey:@"numberOfVisits" ascending:NO] autorelease];

Break this line before |ascending:|

>+  while ((curChild = [historyEnum nextObject]))   
>+    if ([curChild isKindOfClass:[HistorySiteItem class]])
>+      [mHistoryData addObject:curChild];

The while loop needs braces, since its contents are multi-line (even if it's only one statement).

>+  BOOL bookmarksDone;
>+  BOOL historyDone;
>+  if ([mBookmarkResultsInProgress count] == kMaxResultsPerHeading || NSMaxRange(mChunkRange) >= [mBookmarkData count])
>+    bookmarksDone = YES;
>+  if ([mHistoryResultsInProgress count] == kMaxResultsPerHeading || NSMaxRange(mChunkRange) >= [mHistoryData count])
>+    historyDone = YES;

bookmarksDone and historyDone are undefined here when they are intended to be NO. Just write these inline as:

BOOL bookmarksDone = [mBookmarkResultsInProgress count] == kMaxResultsPerHeading ||
                     NSMaxRange(mChunkRange) >= [mBookmarkData count];
BOOL historyDone = [mHistoryResultsInProgress count] == kMaxResultsPerHeading ||
                   NSMaxRange(mChunkRange) >= [mHistoryData count];

>+  if (bookmarksDone && historyDone)
>+    [self reportResults];
>+  else {
>+    // Set new range and process the next chunk.
>+    mChunkRange = NSMakeRange(NSMaxRange(mChunkRange), kNumberOfItemsPerChunk);
>+    [self performSelector:@selector(updateResults) withObject:nil afterDelay:0.0];
>+  }

The |if| needs braces, since the else has them.

>+  // This is a short-term hack to filter out all history items that have an
>+  // empty title. These are uwanted because they appear whenever the user
>+  // typed in an address and is redirected to another page/site. For example,
>+  // www.bankofthewest.com has an empty title and redirects to
>+  // https://www.bankofthewest.com/BOW/home_sl.html with the correct title.
>+  // We want only the latter to appear in autocomplete results.
>+  //if ([item isKindOfClass:[HistoryItem class]] && [[item title] isEqualToString:@""])
>+  //  return NO;

Remove this entirely, since it didn't end up working out.

>+  [self addHeader:@"Bookmarks" toResults:mBookmarkResultsInProgress];
>+  [self addHeader:@"History" toResults:mHistoryResultsInProgress];
>+  [mResults removeAllObjects];
>+  [mResults addObjectsFromArray:mBookmarkResultsInProgress];
>+  [mResults addObjectsFromArray:mHistoryResultsInProgress];
>+  mChunkRange = NSMakeRange(0, kNumberOfItemsPerChunk);

Replace the mChunkRange with a call to resetSearch, since there's no need to keep the intermediate result arrays around at this point.

>+  [mRegexTest release];
>+  mRegexTest = nil;

And fold this into resetSearch, since it's logically part of the same operation (you'll need to move the call in performSearchWithString:delegate: up to before the new mRegexTest construction).

>+  if ([results count] == 0)
>+    // Don't add a header to empty results.
>+    return;

Braces, since it's multi-line.

>+  PRInt32 defaultRow = 1;
>   if (mCompleteResult && mCompleteWhileTyping) {
>     [self selectRowAt:defaultRow];
>     [self completeResult:defaultRow];

Move the declaration into the |if|, since it's only used there.


Things we should file follow-ups on after landing, while I'm thinking of them:
- Optimize for the extremely common case of "new query is a substring of old query", so we don't recheck already-rejected items, thus improving post-first-letter performance.
- Improve the rankings (which Dan has already been working on).
- Make sure that bookmarks always show up under Bookmarks (if feasible); currently if they are also recent history items they might well show up under History instead, which seems like it would be confusing.
- Improve the situation with respect to redirects (e.g., show the rich Gmail result when a user types gmail, rather than the no-title-or-favicon result). Beyond the scope of SoC since it requires capabilities we don't have in the history system (AFAIK), but we should still get it on file.

Comment 57

[Dan Weber]

Attachment: Patch 6

Comment 58

[Stuart Morgan]

Comment on attachment 386320 [details] [diff] [review]
Patch 6

A couple of quick notes on the changes--don't bother respinning now though, just fold these in when you make any changes from pink's sr.

>+  [self resetSearch];
>+  mDelegate = delegate;
>+  if (mRegexTest) {
>+    // The user has typed without waiting for the previous search to finish. Therefore,
>+    // we release the previous test and cancel all previous search requests.
>+    [mRegexTest release];
>+    [NSObject cancelPreviousPerformRequestsWithTarget:self];
>+  }

mRegexTest will never be true after resetSearch, and the [mRegexTest release] is superfluous. Remove the latter, and either move the remainder of the block above the reset or (probably better) just call cancelPrevious... unconditionally.

>+  BOOL bookmarksDone = [mBookmarkResultsInProgress count] == kMaxResultsPerHeading || NSMaxRange(mChunkRange) >= [mBookmarkData count];
>+  BOOL historyDone = [mHistoryResultsInProgress count] == kMaxResultsPerHeading || NSMaxRange(mChunkRange) >= [mHistoryData count];

Break these lines after the ||

Comment 59

[Mike Pinkerton (not reading bugmail)]

Comment on attachment 386320 [details] [diff] [review]
Patch 6

 - (void) selectRowAt:(int)aRow

looks like we're starting to get conflicting naming styles in here with the addition of the new methods. How about taking a pass after this checkin to normalize them to not having a space after the ")"?

+- (NSDictionary *)headerAttributes {
+  return [[[NSMutableDictionary alloc] initWithObjectsAndKeys:
+           [NSColor grayColor], NSForegroundColorAttributeName,
+           [NSFont systemFontOfSize:12.0], NSFontAttributeName,
+           nil] autorelease];
+}

this should just return [NSDictionary dictionaryWithObjectsAndKeys:...]. You don't really need it to be mutable do you?

Also, is it worth caching this somewhere rather than rebuilding it all the time? Not sure how often this is called.

+    [siteIcon setFlipped:YES];
+    [siteIcon drawInRect:imageRect fromRect:NSMakeRect(0, 0, kIconSize.width, kIconSize.height) operation:NSCompositeSourceOver fraction:1.0];
+    [siteIcon setFlipped:NO];

can you not just flip it once and leave it that way rather than doing it every time you need to draw?

+    //[title drawInRect:titleTextRect withAttributes:titleAttributes];
+    [title drawInRect:titleTextRect withAttributes:titleAttributes];

remove the commented-out one? They look the same.

fix these and sr=pink.

Comment 60

[Dan Weber]

Attachment: Patch 7

Comment 61

[Dan Weber]

Attachment: Patch 8

Comment 62

[Mike Pinkerton (not reading bugmail)]

Comment on attachment 387475 [details] [diff] [review]
Patch 8

rs=pink.

I didn't give this a full re-review, just spot-checked the areas I mentioned before.

Comment 63

[Stuart Morgan]

FYI, if you hand-edit patches you have to be very, very careful. They have information like how many lines are in each section, and 'patch' doesn't like it if you make it lie.

Welcome to the brotherhood of People Who Have Been Caught Posting Hand-Edited Patches. We have many members here in Camino-land ;)

Comment 64

[Stuart Morgan]

Attachment: Patch 9

Same as patch 8, but with metadata hand-edited so that it will apply (assuming bug 495496 has landed or been locally applied).

Comment 65

[Stuart Morgan]

Landed on CVS trunk.

Comment 66

[S Woodside]

Yay!!!!!