320181 - Reduce autocomplete search

Status: RESOLVED FIXED

(Firefox :: Bookmarks & History, defect, P1)

Description

[Brett Wilson]

The URL autocomplete code does a complete search of history. This should be time-limited to some reasonable time, possibly doing a second query if there aren't "enough" results.

Comment 1

[Brett Wilson]

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

Comment 2

[Brett Wilson]

Attachment: Rewrite of autocomplete

Please see the newsgroup posting for some conceptual changes:
http://groups.google.com/group/mozilla.dev.apps.firefox/browse_frm/thread/aaec53f1bb43a9b7/6f704941e614df99

Comment 3

[Annie Sullivan]

Comment on attachment 215428 [details] [diff] [review]
Rewrite of autocomplete

>Index: nsNavHistory.cpp
>===================================================================
>RCS file: /cvsroot/mozilla/browser/components/places/src/nsNavHistory.cpp,v
>retrieving revision 1.84
>diff -u -u -8 -p -r1.84 nsNavHistory.cpp
>--- nsNavHistory.cpp	10 Mar 2006 20:57:37 -0000	1.84
>+++ nsNavHistory.cpp	17 Mar 2006 19:44:40 -0000
>@@ -93,17 +93,16 @@
> // never visited) in the RECENT_EVENT_THRESHOLD. Otherwise, we'll start
> // checking each one for every page visit, which will be somewhat slower.
> #define RECENT_EVENT_QUEUE_MAX_LENGTH 128
> 
> // preference ID strings
> #define PREF_BRANCH_BASE                        "browser."
> #define PREF_BROWSER_HISTORY_EXPIRE_DAYS        "history_expire_days"
> #define PREF_AUTOCOMPLETE_ONLY_TYPED            "urlbar.matchOnlyTyped"
>-#define PREF_AUTOCOMPLETE_MAX_COUNT             "urlbar.autocomplete.maxCount"
> #define PREF_AUTOCOMPLETE_ENABLED               "urlbar.autocomplete.enabled"
> 
> // the value of mLastNow expires every 3 seconds
> #define HISTORY_EXPIRE_NOW_TIMEOUT (3 * PR_MSEC_PER_SEC)
> 
> // see bug #319004 -- clamp title and URL to generously-large but not too large
> // length
> #define HISTORY_URI_LENGTH_MAX 65536
>@@ -248,23 +247,18 @@ nsNavHistory::Init()
>   PRBool doImport;
>   rv = InitDB(&doImport);
>   NS_ENSURE_SUCCESS(rv, rv);
> #ifdef IN_MEMORY_LINKS
>   rv = InitMemDB();
>   NS_ENSURE_SUCCESS(rv, rv);
> #endif
> 
>-  // commonly used prefixes that should be chopped off all history and input
>-  // urls before comparison
>-  mIgnoreSchemes.AppendString(NS_LITERAL_STRING("http://"));
>-  mIgnoreSchemes.AppendString(NS_LITERAL_STRING("https://"));
>-  mIgnoreSchemes.AppendString(NS_LITERAL_STRING("ftp://"));
>-  mIgnoreHostnames.AppendString(NS_LITERAL_STRING("www."));
>-  mIgnoreHostnames.AppendString(NS_LITERAL_STRING("ftp."));
>+  rv = InitAutoComplete();
>+  NS_ENSURE_SUCCESS(rv, rv);
> 
>   // extract the last session ID so we know where to pick up. There is no index
>   // over sessions so the naive statement "SELECT MAX(session) FROM
>   // moz_historyvisit" won't have good performance. Instead we select the
>   // session of the last visited page because we do have indices over dates.
>   // We still do MAX(session) in case there are duplicate sessions for the same
>   // date, but there will generally be very few (1) of these.
>   {
>@@ -340,17 +334,16 @@ nsNavHistory::Init()
>   nsCOMPtr<nsIObserverService> observerService =
>     do_GetService("@mozilla.org/observer-service;1", &rv);
>   NS_ENSURE_SUCCESS(rv, rv);
> 
>   nsCOMPtr<nsIPrefBranch2> pbi = do_QueryInterface(mPrefBranch);
>   if (pbi) {
>     pbi->AddObserver(PREF_AUTOCOMPLETE_ONLY_TYPED, this, PR_FALSE);
>     pbi->AddObserver(PREF_BROWSER_HISTORY_EXPIRE_DAYS, this, PR_FALSE);
>-    pbi->AddObserver(PREF_AUTOCOMPLETE_MAX_COUNT, this, PR_FALSE);
>   }
> 
>   observerService->AddObserver(this, gQuitApplicationMessage, PR_FALSE);
>   observerService->AddObserver(this, gXpcomShutdown, PR_FALSE);
> 
>   if (doImport) {
>     nsCOMPtr<nsIMorkHistoryImporter> importer = new nsMorkHistoryImporter();
>     NS_ENSURE_TRUE(importer, NS_ERROR_OUT_OF_MEMORY);
>@@ -1086,20 +1079,23 @@ nsNavHistory::VacuumDB(PRTime aTimeAgo)
> 
> nsresult
> nsNavHistory::LoadPrefs()
> {
>   if (! mPrefBranch)
>     return NS_OK;
> 
>   mPrefBranch->GetIntPref(PREF_BROWSER_HISTORY_EXPIRE_DAYS, &mExpireDays);
>+  PRBool oldCompleteOnlyTyped = mAutoCompleteOnlyTyped;
>   mPrefBranch->GetBoolPref(PREF_AUTOCOMPLETE_ONLY_TYPED,
>                            &mAutoCompleteOnlyTyped);
>-  if (NS_FAILED(mPrefBranch->GetIntPref(PREF_AUTOCOMPLETE_MAX_COUNT, &mAutoCompleteMaxCount))) {
>-    mAutoCompleteMaxCount = 2000; // FIXME: add this to default prefs.js
>+  if (oldCompleteOnlyTyped != mAutoCompleteOnlyTyped) {
>+    // update the autocomplete statement if the option has changed.
>+    nsresult rv = CreateAutoCompleteQuery();
>+    NS_ENSURE_SUCCESS(rv, rv);
>   }
>   return NS_OK;
> }
> 
> 
> // nsNavHistory::GetNow
> //
> //    This is a hack to avoid calling PR_Now() too often, as is the case when
>Index: nsNavHistory.h
>===================================================================
>RCS file: /cvsroot/mozilla/browser/components/places/src/nsNavHistory.h,v
>retrieving revision 1.60
>diff -u -u -8 -p -r1.60 nsNavHistory.h
>--- nsNavHistory.h	9 Mar 2006 17:34:35 -0000	1.60
>+++ nsNavHistory.h	17 Mar 2006 19:44:40 -0000
>@@ -71,44 +71,42 @@
> #include "nsWeakReference.h"
> #include "nsTArray.h"
> #include "nsINavBookmarksService.h"
> #include "nsMaybeWeakPtr.h"
> 
> #include "nsNavHistoryResult.h"
> #include "nsNavHistoryQuery.h"
> 
>-// Number of prefixes used in the autocomplete sort comparison function
>-#define AUTOCOMPLETE_PREFIX_LIST_COUNT 6
>-// Size of visit count boost to give to urls which are sites or paths
>-#define AUTOCOMPLETE_NONPAGE_VISIT_COUNT_BOOST 5
> // set to use more optimized (in-memory database) link coloring
> //#define IN_MEMORY_LINKS
> 
> #define QUERYUPDATE_TIME 0
> #define QUERYUPDATE_SIMPLE 1
> #define QUERYUPDATE_COMPLEX 2
> #define QUERYUPDATE_COMPLEX_WITH_BOOKMARKS 3
> 
>-class AutoCompleteIntermediateResultSet;
>+class AutoCompleteIntermediateResult;
>+class AutoCompleteResultComparator;
> class mozIAnnotationService;
> class nsNavHistory;
> class nsNavBookmarks;
> class QueryKeyValuePair;
> 
> // nsNavHistory
> 
> class nsNavHistory : public nsSupportsWeakReference,
>                      public nsINavHistoryService,
>                      public nsIObserver,
>                      public nsIBrowserHistory,
>                      public nsIGlobalHistory3,
>                      public nsIAutoCompleteSearch
> {
>   friend class AutoCompleteIntermediateResultSet;
>+  friend class AutoCompleteResultComparator;
> public:
>   nsNavHistory();
> 
>   NS_DECL_ISUPPORTS
> 
>   NS_DECL_NSINAVHISTORYSERVICE
>   NS_DECL_NSIGLOBALHISTORY2
>   NS_DECL_NSIGLOBALHISTORY3
>@@ -437,19 +435,36 @@ protected:
> 
>   // session tracking
>   PRInt64 mLastSessionID;
>   PRInt64 GetNewSessionID() { mLastSessionID ++; return mLastSessionID; }
> 
>   //
>   // AutoComplete stuff
>   //
>-  nsStringArray mIgnoreSchemes;
>-  nsStringArray mIgnoreHostnames;
>+  struct AutoCompletePrefix
>+  {
>+    AutoCompletePrefix(const nsAString& aPrefix, PRBool aSecondLevel) :
>+      prefix(aPrefix), secondLevel(aSecondLevel) {}
>+
>+    // The prefix, for example, "http://" or "https://www."
>+    nsString prefix;
>+
>+    // Set when this prefix contains a spec AND a host. For example,
>+    // "http://www." is a second level prefix, but "http://" is not. This
>+    // flag is used to exclude matches. For example, if I type "http://w"
>+    // I probably want it to autocomplete to sites beginning with w and
>+    // NOT every "www" site I've ever visited.
>+    PRBool secondLevel;
>+  };
>+  nsTArray<AutoCompletePrefix> mAutoCompletePrefixes;
> 
>+  nsCOMPtr<mozIStorageStatement> mDBAutoCompleteQuery;
>+  nsresult InitAutoComplete();
>+  nsresult CreateAutoCompleteQuery();
>   PRInt32 mAutoCompleteMaxCount;
>   PRInt32 mExpireDays;
>   PRBool mAutoCompleteOnlyTyped;
> 
>   // Used to describe what prefixes shouldn't be cut from
>   // history urls when doing an autocomplete url comparison.
>   struct AutoCompleteExclude {
>     // these are indices into mIgnoreSchemes and mIgnoreHostnames, or -1
>@@ -461,27 +476,21 @@ protected:
>   };
> 
>   nsresult AutoCompleteTypedSearch(nsIAutoCompleteSimpleResult* result);
>   nsresult AutoCompleteFullHistorySearch(const nsAString& aSearchString,
>                                          nsIAutoCompleteSimpleResult* result);
>   nsresult AutoCompleteRefineHistorySearch(const nsAString& aSearchString,
>                                    nsIAutoCompleteResult* aPreviousResult,
>                                    nsIAutoCompleteSimpleResult* aNewResult);
>-  void AutoCompleteCutPrefix(nsString* aURL,
>-                             const AutoCompleteExclude* aExclude);
>-  void AutoCompleteGetExcludeInfo(const nsAString& aURL,
>-                                  AutoCompleteExclude* aExclude);
>-  PRBool AutoCompleteCompare(const nsAString& aHistoryURL,
>-                             const nsAString& aUserURL,
>-                             const AutoCompleteExclude& aExclude);
>-  PR_STATIC_CALLBACK(int) AutoCompleteSortComparison(
>-                             const void* match1Void,
>-                             const void* match2Void,
>-                             void *navHistoryVoid);
>+  nsresult AutoCompleteQueryOnePrefix(const nsString& aSearchString,
>+                                      const nsTArray<PRInt32>& aExcludePrefixes,
>+                                      PRInt32 aPriorityDelta,
>+                                      nsTArray<AutoCompleteIntermediateResult>* aResult);
>+  PRInt32 AutoCompleteGetPrefixLength(const nsString& aSpec);
> 
>   // in nsNavHistoryQuery.cpp
>   nsresult TokensToQueries(const nsTArray<QueryKeyValuePair>& aTokens,
>                            nsCOMArray<nsNavHistoryQuery>* aQueries,
>                            nsNavHistoryQueryOptions* aOptions);
> 
>   // creates supplemental indexes that we'd like to not bother with
>   // updating during import.
>Index: nsNavHistoryAutoComplete.cpp
>===================================================================
>RCS file: /cvsroot/mozilla/browser/components/places/src/nsNavHistoryAutoComplete.cpp,v
>retrieving revision 1.1
>diff -u -u -8 -p -r1.1 nsNavHistoryAutoComplete.cpp
>--- nsNavHistoryAutoComplete.cpp	16 Dec 2005 00:16:14 -0000	1.1
>+++ nsNavHistoryAutoComplete.cpp	17 Mar 2006 19:44:40 -0000
>@@ -33,94 +33,275 @@
>  * use your version of this file under the terms of the MPL, indicate your
>  * decision by deleting the provisions above and replace them with the notice
>  * and other provisions required by the GPL or the LGPL. If you do not delete
>  * the provisions above, a recipient may use your version of this file under
>  * the terms of any one of the MPL, the GPL or the LGPL.
>  *
>  * ***** END LICENSE BLOCK ***** */
> 
>+
>+/**
>+ * Autocomplte algorithm:
>+ *
>+ * Scoring
>+ * -------
>+ * Generally ordering is by visit count. We given boosts to items that have
>+ * been bookmarked or typed into the address bar (as opposed to clicked links).
>+ * The penalties below for schemes and prefix matches also apply. We also
>+ * prefer paths (URLs ending in '/') and try to have shorter ones generally
>+ * appear first. The results are then presented in descending numeric order
>+ * using this score.
>+ *
>+ * Database queries
>+ * ----------------
>+ * It is tempting to do a select for "url LIKE user_input" but this is a very
>+ * slow query since it is brute-force over all URLs in histroy. We can,
>+ * however, do very efficient queries using < and > for strings. These
>+ * operators use the index over the URL column.
>+ *
>+ * Therefore, we try to prepend any prefixes that should be considered and
>+ * query for them individually. Therefore, we execute several very efficient
>+ * queries, score the results, and sort it.
>+ *
>+ * To limit the amount of searching we do, we ask the database to order the
>+ * results based on visit count for us and give us on the top N results.
>+ * These results will be in approximate order of score. As long as each query
>+ * has more results than the user is likely to see, they will not notice the
>+ * effects of this.
>+ *
>+ * First see if any specs match that from the beginning
>+ * ----------------------------------------------------
>+ * - If it matches the beginning of a known prefix prefix, exclude that prefix
>+ *   when querying. We would therefore exclude "http://" and "https://" if you type
>+ *   "ht". But match any other schemes that begin with "ht" (probably none).
>+ *
>+ * - Penalize all results. Most people don't type the scheme and don't want
>+ *   matches like this. This will make "file://" links go below
>+ *   "http://www.fido.com/". If one is typing the scheme "file:" for example, by
>+ *   the time you type the colon it won't match anything else (like "http://file:")
>+ *   and the penalty won't have any effect on the ordering (it will be applied to
>+ *   all results).
>+ *
>+ * Try different known prefixes
>+ * ----------------------------
>+ * - Prepend each prefix, running a query. If the concatenated string is itself a
>+ *   prefix of another known prefix (ie input is "w" and we prepend "http://", it
>+ *   will be a prefix of "http://www."), select out that known prefix. In this
>+ *   case we'll query for everything starting with "http://w" except things
>+ *   starting with "http://www."
>+ *
>+ * - For each selected out prefix above, run a query but apply prefix match
>+ *   penalty to the results. This way you'll still get "http://www." results
>+ *   if you type "w", but they will generally be lower than "http://wookie.net/"
>+ *   For your favorite few sites with many visits, you might still get matches
>+ *   for "www" first, which is probably what you want for your favorite sites.
>+ */
>+
> #include "nsNavHistory.h"
>+#include "nsNetUtil.h"
> 
> #include "mozIStorageService.h"
> #include "mozIStorageConnection.h"
> #include "mozIStorageValueArray.h"
> #include "mozIStorageStatement.h"
> #include "mozIStorageFunction.h"
> #include "mozStorageCID.h"
> #include "mozStorageHelper.h"
> 
> #define NS_AUTOCOMPLETESIMPLERESULT_CONTRACTID \
>   "@mozilla.org/autocomplete/simple-result;1"
> 
>+// Size of visit count boost to give to URLs which are sites or paths
>+#define AUTOCOMPLETE_NONPAGE_VISIT_COUNT_BOOST 5
>+
>+// Boost to give to URLs which have been typed
>+#define AUTOCOMPLETE_TYPED_BOOST 5
>+
>+// Boost to give to URLs which are bookmarked
>+#define AUTOCOMPLETE_BOOKMARKED_BOOST 5
>+
>+// Penalty to add to sites that match a prefix. For example, if I type "w"
>+// we will complte on "http://www.w..." like normal. We we will also complete
>+// on "http://w" which will match almost every site, but will have this penalty
>+// applied so they will come later. We want a pretty big penalty so that you'll
>+// only get "www" beating domain names that start with w for your very favorite
>+// sites.
>+#define AUTOCOMPLETE_MATCHES_PREFIX_PENALTY (-50)
>+
>+// Penalty applied to matches that don't have prefixes applied. See
>+// discussion above.
>+#define AUTOCOMPLETE_MATCHES_SCHEME_PENALTY (-20)
>+
>+// Number of results we will consider for each prefix. Each prefix lookup is
>+// done separately. Typically, we will only match one prefix, so this should be
>+// a sufficient number to give "enough" autocomplete matches per prefix. The
>+// total number of results that could ever be returned is this times the number
>+// of prefixes. This should be as small as is reasonable to make it faster.
>+#define AUTOCOMPLETE_MAX_PER_PREFIX 50
>+
>+// This is the maximum number of visits that an item can have for us to
>+// try to remove the path and put a virtual item with just the hostname as the
>+// first entry. The virtual item helps the case where you've visited a site deep
>+// down and want to visit the main site. This limit makes sure we don't take
>+// the first autocomplete spot for a page you are more likely to go to.
>+#define AUTOCOMPLETE_MAX_TRUNCATION_VISIT 2
> 
> PRInt32 ComputeAutoCompletePriority(const nsAString& aUrl, PRInt32 aVisitCount,
>-                                    PRBool aWasTyped);
>+                                    PRBool aWasTyped, PRBool aIsBookmarked);
>+nsresult NormalizeAutocompleteInput(const nsAString& aInput,
>+                                    nsString& aOutput);
> 
> // nsIAutoCompleteSearch *******************************************************
> 
> 
> // AutoCompleteIntermediateResult/Set
> //
> //    This class holds intermediate autocomplete results so that they can be
> //    sorted. This list is then handed off to a result using FillResult. The
> //    major reason for this is so that we can use nsArray's sorting functions,
> //    not use COM, yet have well-defined lifetimes for the objects. This uses
> //    a void array, but makes sure to delete the objects on desctruction.
> 
> struct AutoCompleteIntermediateResult
> {
>+  AutoCompleteIntermediateResult(const nsString& aUrl, const nsString& aTitle,
>+                                 PRInt32 aVisitCount, PRInt32 aPriority) :
>+    url(aUrl), title(aTitle), visitCount(aVisitCount), priority(aPriority) {}
>   nsString url;
>   nsString title;
>-  PRUint32 priority;
>+  PRInt32 visitCount;
>+  PRInt32 priority;
> };
>-class AutoCompleteIntermediateResultSet
>+
>+
>+// AutoCompleteResultComparator
>+
>+class AutoCompleteResultComparator
> {
> public:
>-  AutoCompleteIntermediateResultSet()
>-  {
>-  }
>-  ~AutoCompleteIntermediateResultSet()
>-  {
>-    for (PRInt32 i = 0; i < mArray.Count(); i ++) {
>-      AutoCompleteIntermediateResult* cur = NS_STATIC_CAST(
>-                                    AutoCompleteIntermediateResult*, mArray[i]);
>-      delete cur;
>+  AutoCompleteResultComparator(nsNavHistory* history) : mHistory(history) {}
>+
>+  PRBool Equals(const AutoCompleteIntermediateResult& a,
>+                const AutoCompleteIntermediateResult& b) const {
>+    // Don't need an equals, this call will be optimized out when it
>+    // is used by nsQuickSortComparator above
>+    return PR_FALSE;
>+  }
>+  PRBool LessThan(const AutoCompleteIntermediateResult& match1,
>+                  const AutoCompleteIntermediateResult& match2) const {
>+    // we actually compare GREATER than here, since we want the array to be in
>+    // most relevant (highest priority value) first
>+
>+    // In most cases the priorities will be different and we just use them
>+    if (match1.priority != match2.priority)
>+    {
>+      return match1.priority > match2.priority;
>     }
>-  }
>-  PRBool Add(const nsString& aURL, const nsString& aTitle, PRInt32 aPriority)
>-  {
>-    AutoCompleteIntermediateResult* cur = new AutoCompleteIntermediateResult;
>-    if (! cur)
>-      return PR_FALSE;
>-    cur->url = aURL;
>-    cur->title = aTitle;
>-    cur->priority = aPriority;
>-    mArray.AppendElement(cur);
>-    return PR_TRUE;
>-  }
>-  void Sort(nsNavHistory* navHistory)
>-  {
>-    mArray.Sort(nsNavHistory::AutoCompleteSortComparison, navHistory);
>-  }
>-  nsresult FillResult(nsIAutoCompleteSimpleResult* aResult)
>-  {
>-    for (PRInt32 i = 0; i < mArray.Count(); i ++)
>+    else
>     {
>-      AutoCompleteIntermediateResult* cur = NS_STATIC_CAST(
>-                                    AutoCompleteIntermediateResult*, mArray[i]);
>-      nsresult rv = aResult->AppendMatch(cur->url, cur->title);
>-      NS_ENSURE_SUCCESS(rv, rv);
>+      // secondary sorting gives priority to site names and paths (ending in a /)
>+      PRBool isPath1 = PR_FALSE, isPath2 = PR_FALSE;
>+      if (!match1.url.IsEmpty())
>+        isPath1 = (match1.url.Last() == PRUnichar('/'));
>+      if (!match2.url.IsEmpty())
>+        isPath2 = (match2.url.Last() == PRUnichar('/'));
>+
>+      if (isPath1 && !isPath2) return PR_FALSE; // match1->url is a website/path, match2->url isn't
>+      if (!isPath1 && isPath2) return PR_TRUE;  // match1->url isn't a website/path, match2->url is
>+
>+      // find the prefixes so we can sort by the stuff after the prefixes
>+      PRInt32 prefix1 = mHistory->AutoCompleteGetPrefixLength(match1.url);
>+      PRInt32 prefix2 = mHistory->AutoCompleteGetPrefixLength(match2.url);
>+
>+      // Compare non-prefixed urls using the current locale string compare. This will sort
>+      // things alphabetically (ignoring common prefixes). For example, "http://www.abc.com/"
>+      // will come before "ftp://ftp.xyz.com"
>+      PRInt32 ret = 0;
>+      mHistory->mCollation->CompareString(
>+          nsICollation::kCollationCaseInSensitive,
>+          Substring(match1.url, prefix1), Substring(match2.url, prefix2),
>+          &ret);
>+      if (ret != 0)
>+        return ret > 0;
>+
>+      // sort http://xyz.com before http://www.xyz.com
>+      return prefix1 > prefix2;
>     }
>-    return NS_OK;
>+    return PR_FALSE;
>   }
> protected:
>-  nsVoidArray mArray;
>+  nsNavHistory* mHistory;
> };
> 
>+
>+// nsNavHistory::InitAutoComplete
>+
>+nsresult
>+nsNavHistory::InitAutoComplete()
>+{
>+  nsresult rv = CreateAutoCompleteQuery();
>+  NS_ENSURE_SUCCESS(rv, rv);
>+
>+  AutoCompletePrefix* ok;
>+
>+  // These are the prefixes we check for implicitly. Prefixes with a
>+  // host portion (like "www.") get their second level flag set.
>+  ok = mAutoCompletePrefixes.AppendElement(AutoCompletePrefix(NS_LITERAL_STRING("http://"), PR_FALSE));
>+  NS_ENSURE_TRUE(ok, NS_ERROR_OUT_OF_MEMORY);
>+  ok = mAutoCompletePrefixes.AppendElement(AutoCompletePrefix(NS_LITERAL_STRING("http://www."), PR_TRUE));
>+  NS_ENSURE_TRUE(ok, NS_ERROR_OUT_OF_MEMORY);
>+  ok = mAutoCompletePrefixes.AppendElement(AutoCompletePrefix(NS_LITERAL_STRING("ftp://"), PR_FALSE));
>+  NS_ENSURE_TRUE(ok, NS_ERROR_OUT_OF_MEMORY);
>+  ok = mAutoCompletePrefixes.AppendElement(AutoCompletePrefix(NS_LITERAL_STRING("ftp://ftp."), PR_TRUE));
>+  NS_ENSURE_TRUE(ok, NS_ERROR_OUT_OF_MEMORY);
>+  ok = mAutoCompletePrefixes.AppendElement(AutoCompletePrefix(NS_LITERAL_STRING("https://"), PR_FALSE));
>+  NS_ENSURE_TRUE(ok, NS_ERROR_OUT_OF_MEMORY);
>+  ok = mAutoCompletePrefixes.AppendElement(AutoCompletePrefix(NS_LITERAL_STRING("https://www."), PR_TRUE));
>+  NS_ENSURE_TRUE(ok, NS_ERROR_OUT_OF_MEMORY);
>+
>+  return NS_OK;
>+}
>+
>+
>+// nsNavHistory::CreateAutoCompleteQuery
>+//
>+//    The auto complete query we use depends on options, so we have it in
>+//    a separate function so it can be re-created when the option changes.
>+
>+nsresult
>+nsNavHistory::CreateAutoCompleteQuery()
>+{
>+  nsCString sql;
>+  if (mAutoCompleteOnlyTyped) {
>+    sql = NS_LITERAL_CSTRING(
>+        "SELECT url, title, visit_count, typed, "
>+         "(SELECT item_child FROM moz_bookmarks WHERE item_child = id) "
>+        "FROM moz_history "
>+        "WHERE url >= ?1 AND url < ?2 "
>+        "AND typed = 1 "
>+        "ORDER BY visit_count DESC "
>+        "LIMIT ");
>+  } else {
>+    sql = NS_LITERAL_CSTRING(
>+        "SELECT url, title, visit_count, typed, "
>+          "(SELECT item_child FROM moz_bookmarks WHERE item_child = id) "
>+        "FROM moz_history "
>+        "WHERE url >= ?1 AND url < ?2 "
>+        "AND (hidden <> 1 OR typed = 1) "
>+        "ORDER BY visit_count DESC "
>+        "LIMIT ");
>+  }
>+  sql.AppendInt(AUTOCOMPLETE_MAX_PER_PREFIX);
>+  nsresult rv = mDBConn->CreateStatement(sql,
>+      getter_AddRefs(mDBAutoCompleteQuery));
>+  return rv;
>+}
>+
>+
> // nsNavHistory::StartSearch
> //
> 
> NS_IMETHODIMP
> nsNavHistory::StartSearch(const nsAString & aSearchString,
>                           const nsAString & aSearchParam,
>                           nsIAutoCompleteResult *aPreviousResult,
>                           nsIAutoCompleteObserver *aListener)
>@@ -129,43 +310,28 @@ nsNavHistory::StartSearch(const nsAStrin
> 
>   NS_ENSURE_ARG_POINTER(aListener);
> 
>   nsCOMPtr<nsIAutoCompleteSimpleResult> result =
>       do_CreateInstance(NS_AUTOCOMPLETESIMPLERESULT_CONTRACTID, &rv);
>   NS_ENSURE_SUCCESS(rv, rv);
>   result->SetSearchString(aSearchString);
> 
>-  PRBool usePrevious = (aPreviousResult != nsnull);
>-
>-  // throw away previous results if the search string is empty after it has had
>-  // the prefixes removed: if the user types "http://" throw away the search
>-  // for "http:/" and start fresh with the new query.
>-  if (usePrevious) {
>-    nsAutoString cut(aSearchString);
>-    AutoCompleteCutPrefix(&cut, nsnull);
>-    if (cut.IsEmpty())
>-      usePrevious = PR_FALSE;
>-  }
>-
>-  // throw away previous results if the new string doesn't begin with the
>-  // previous search string
>-  if (usePrevious) {
>-    nsAutoString previousSearch;
>-    aPreviousResult->GetSearchString(previousSearch);
>-    if (previousSearch.Length() > aSearchString.Length()  ||
>-        !Substring(aSearchString, 0, previousSearch.Length()).Equals(previousSearch)) {
>-      usePrevious = PR_FALSE;
>-    }
>-  }
>-
>+  // Performance: We can improve performance for refinements of a previous
>+  // result by filtering the old result with the new string. However, since
>+  // our results are not a full match of history, we'll need to requery if
>+  // any of the subresults returned the maximum number of elements (i.e. we
>+  // didn't load all of them).
>+  //
>+  // Timing measurements show that the performance of this is actually very
>+  // good for specific queries. Thus, the times where we can do the
>+  // optimization (when there are few results) are exactly the times when
>+  // we don't have to. As a result, we keep it this much simpler way.
>   if (aSearchString.IsEmpty()) {
>     rv = AutoCompleteTypedSearch(result);
>-  } else if (usePrevious) {
>-    rv = AutoCompleteRefineHistorySearch(aSearchString, aPreviousResult, result);
>   } else {
>     rv = AutoCompleteFullHistorySearch(aSearchString, result);
>   }
>   NS_ENSURE_SUCCESS(rv, rv);
> 
>   // Determine the result of the search
>   PRUint32 count;
>   result->GetMatchCount(&count);
>@@ -201,18 +367,20 @@ nsNavHistory::StopSearch()
> //    visit count (primary) and time since last visited (secondary).
> 
> nsresult nsNavHistory::AutoCompleteTypedSearch(
>                                             nsIAutoCompleteSimpleResult* result)
> {
>   // note: need to test against hidden = 1 since the column can also be null
>   // (meaning not hidden)
>   nsCOMPtr<mozIStorageStatement> dbSelectStatement;
>-  nsresult rv = mDBConn->CreateStatement(
>-      NS_LITERAL_CSTRING("SELECT url,title FROM moz_history WHERE typed = 1 AND hidden <> 1 ORDER BY visit_count DESC LIMIT 1000"),
>+  nsresult rv = mDBConn->CreateStatement(NS_LITERAL_CSTRING(
>+      "SELECT url, title "
>+      "FROM moz_historyvisit v JOIN moz_history h ON v.page_id = h.id "
>+      "WHERE h.typed = 1 AND h.hidden <> 1 ORDER BY visit_count DESC LIMIT 100"),
>       getter_AddRefs(dbSelectStatement));
>   NS_ENSURE_SUCCESS(rv, rv);
> 
>   PRBool hasMore = PR_FALSE;
>   while (NS_SUCCEEDED(dbSelectStatement->ExecuteStep(&hasMore)) && hasMore) {
>     nsAutoString entryURL, entryTitle;
>     dbSelectStatement->GetString(0, entryURL);
>     dbSelectStatement->GetString(1, entryTitle);
>@@ -229,71 +397,232 @@ nsresult nsNavHistory::AutoCompleteTyped
> //
> //    A brute-force search of the entire history. This matches the given input
> //    with every possible history entry, and sorts them by likelihood.
> //
> //    This may be slow for people on slow computers with large histories.
> 
> nsresult
> nsNavHistory::AutoCompleteFullHistorySearch(const nsAString& aSearchString,
>-                                            nsIAutoCompleteSimpleResult* result)
>+                                            nsIAutoCompleteSimpleResult* aResult)
> {
>-  // figure out whether any known prefixes are present in the search string
>-  // so we know not to ignore them when comparing results later
>-  AutoCompleteExclude exclude;
>-  AutoCompleteGetExcludeInfo(aSearchString, &exclude);
>+  nsString searchString;
>+  nsresult rv = NormalizeAutocompleteInput(aSearchString, searchString);
>+  if (NS_FAILED(rv))
>+    return NS_OK; // no matches for invalid input
>+
>+  nsTArray<AutoCompleteIntermediateResult> matches;
>+
>+  // Try a query using this search string and every prefix. Keep track of
>+  // known prefixes that the input matches for exclusion later
>+  PRUint32 i;
>+  const nsTArray<PRInt32> emptyArray;
>+  nsTArray<PRInt32> firstLevelMatches;
>+  nsTArray<PRInt32> secondLevelMatches;
>+  for (i = 0; i < mAutoCompletePrefixes.Length(); i ++) {
>+    if (StringBeginsWith(mAutoCompletePrefixes[i].prefix, searchString)) {
>+      if (mAutoCompletePrefixes[i].secondLevel)
>+        secondLevelMatches.AppendElement(i);
>+      else
>+        firstLevelMatches.AppendElement(i);
>+    }
> 
>-  mozStorageStatementScoper scoper(mDBFullAutoComplete);
>-  nsresult rv = mDBFullAutoComplete->BindInt32Parameter(0, mAutoCompleteMaxCount);
>-  NS_ENSURE_SUCCESS(rv, rv);
>+    // current string to search for
>+    nsString cur = mAutoCompletePrefixes[i].prefix + searchString;
> 
>-  // load the intermediate result so it can be sorted
>-  AutoCompleteIntermediateResultSet resultSet;
>-  PRBool hasMore = PR_FALSE;
>-  while (NS_SUCCEEDED(mDBFullAutoComplete->ExecuteStep(&hasMore)) && hasMore) {
>+    // see if the concatenated string itself matches any prefixes
>+    nsTArray<PRInt32> curPrefixMatches;
>+    for (PRUint32 prefix = 0; prefix < mAutoCompletePrefixes.Length(); prefix ++) {
>+      if (StringBeginsWith(mAutoCompletePrefixes[prefix].prefix, cur))
>+        curPrefixMatches.AppendElement(prefix);
>+    }
>+
>+    // search for the current string, excluding those matching prefixes
>+    AutoCompleteQueryOnePrefix(cur, curPrefixMatches, 0, &matches);
> 
>-    PRBool typed = mDBFullAutoComplete->AsInt32(kAutoCompleteIndex_Typed);
>-    if (!typed) {
>-      if (mAutoCompleteOnlyTyped)
>-        continue;
>+    // search for each of those matching prefixes, applying the prefix penalty
>+    for (PRUint32 match = 0; match < curPrefixMatches.Length(); match ++) {
>+      AutoCompleteQueryOnePrefix(mAutoCompletePrefixes[curPrefixMatches[match]].prefix,
>+                                 emptyArray, AUTOCOMPLETE_MATCHES_PREFIX_PENALTY,
>+                                 &matches);
>     }
>+  }
> 
>-    nsAutoString entryurl;
>-    mDBFullAutoComplete->GetString(kAutoCompleteIndex_URL, entryurl);
>-    if (AutoCompleteCompare(entryurl, aSearchString, exclude)) {
>-      nsAutoString entrytitle;
>-      rv = mDBFullAutoComplete->GetString(kAutoCompleteIndex_Title, entrytitle);
>+  // Now try searching with no prefix
>+  if (firstLevelMatches.Length() > 0) {
>+    // This will get all matches that DON'T match any prefix. For example, if
>+    // the user types "http://w" we will match "http://westinghouse.com" but
>+    // not "http://www.something".
>+    AutoCompleteQueryOnePrefix(searchString,
>+                               firstLevelMatches, 0, &matches);
>+  } else if (secondLevelMatches.Length() > 0) {
>+    // if there are no first level matches (i.e. "http://") then we fall back on
>+    // second level matches. Here, we assume that a first level match implies
>+    // a second level match as well, so we only have to check when there are no
>+    // first level matches.
>+    AutoCompleteQueryOnePrefix(searchString,
>+                               secondLevelMatches, 0, &matches);
>+
>+    // now we try to fill in matches of the prefix. For example, if you type
>+    // "http://w" we will still match against "http://www." but with a penalty.
>+    // We only do this for second level prefixes.
>+    for (PRUint32 match = 0; match < secondLevelMatches.Length(); match ++) {
>+      AutoCompleteQueryOnePrefix(mAutoCompletePrefixes[secondLevelMatches[match]].prefix,
>+                                 emptyArray, AUTOCOMPLETE_MATCHES_SCHEME_PENALTY,
>+                                 &matches);
>+    }
>+  } else {
>+    // Input matched no prefix, try to query for all URLs beinning with this
>+    // exact input.
>+    AutoCompleteQueryOnePrefix(searchString, emptyArray,
>+                               AUTOCOMPLETE_MATCHES_SCHEME_PENALTY, &matches);
>+  }
>+
>+  // sort according to priorities
>+  AutoCompleteResultComparator comparator(this);
>+  matches.Sort(comparator);
>+
>+  // fill into result
>+  nsAutoString zerothEntry;
>+  if (matches.Length() > 0 &&
>+      matches[0].visitCount <= AUTOCOMPLETE_MAX_TRUNCATION_VISIT) {
>+    // Here, we try to make sure that the first match is always a host name
>+    // we take the previous first match and extract its host name and add it
>+    // before. If the first item has been visited a lot, don't do that because
>+    // they probably want to go there instead
>+    nsCOMPtr<nsIURI> uri;
>+    rv = NS_NewURI(getter_AddRefs(uri), NS_ConvertUTF16toUTF8(matches[0].url));
>+    NS_ENSURE_SUCCESS(rv, rv);
>+    uri->SetPath(NS_LITERAL_CSTRING("/"));
>+
>+    nsCAutoString spec;
>+    uri->GetSpec(spec);
>+    zerothEntry = NS_ConvertUTF8toUTF16(spec);
>+
>+    if (! zerothEntry.Equals(matches[0].url))
>+      aResult->AppendMatch(zerothEntry, EmptyString());
>+    rv = aResult->AppendMatch(matches[0].url, matches[0].title);
>+    NS_ENSURE_SUCCESS(rv, rv);
>+  } else if (matches.Length() > 0) {
>+    // otherwise, just append the first match
>+    rv = aResult->AppendMatch(matches[0].url, matches[0].title);
>+    NS_ENSURE_SUCCESS(rv, rv);
>+  }
>+  for (i = 1; i < matches.Length(); i ++) {
>+    // only add ones that are NOT the same as the previous one. It's possible
>+    // to get duplicates from the queries.
>+    if (! matches[i].url.Equals(matches[i-1].url) &&
>+        ! zerothEntry.Equals(matches[i].url)) {
>+      rv = aResult->AppendMatch(matches[i].url, matches[i].title);
>       NS_ENSURE_SUCCESS(rv, rv);
>-      PRInt32 priority = ComputeAutoCompletePriority(entryurl,
>-                    mDBFullAutoComplete->AsInt32(kAutoCompleteIndex_VisitCount),
>-                    typed);
>+    }
>+  }
>+  return NS_OK;
>+}
>+
>+
>+// nsNavHistory::AutoCompleteQueryOnePrefix
>+//
>+//    The values in aExcludePrefixes are indices into mAutoCompletePrefixes
>+//    of prefixes to exclude during this query. For example, if I type
>+//    "ht" this function will be called to match everything starting with
>+//    "ht" EXCEPT "http://" and "https://".
>+
>+nsresult
>+nsNavHistory::AutoCompleteQueryOnePrefix(const nsString& aSearchString,
>+    const nsTArray<PRInt32>& aExcludePrefixes,
>+    PRInt32 aPriorityDelta,
>+    nsTArray<AutoCompleteIntermediateResult>* aResult)
>+{
>+  // All URL queries are in UTF-8. Compute the beginning (inclusive) and
>+  // ending (exclusive) of the range of URLs to include when compared
>+  // using strcmp (which is what sqlite does).
>+  nsCAutoString beginQuery = NS_ConvertUTF16toUTF8(aSearchString);
>+  if (beginQuery.IsEmpty())
>+    return NS_OK;
>+  nsCAutoString endQuery = beginQuery;
>+  unsigned char maxChar[6] = { 0xfd, 0xbf, 0xbf, 0xbf, 0xbf, 0xbf };
>+  endQuery.Append(NS_REINTERPRET_CAST(const char*, maxChar), 6);
>+
>+  nsTArray<nsCString> ranges;
>+  if (aExcludePrefixes.Length() > 0) {
>+    // we've been requested to include holes in our range, sort these ranges
>+    ranges.AppendElement(beginQuery);
>+    for (PRUint32 i = 0; i < aExcludePrefixes.Length(); i ++) {
>+      nsCAutoString thisPrefix = NS_ConvertUTF16toUTF8(
>+          mAutoCompletePrefixes[aExcludePrefixes[i]].prefix);
>+      ranges.AppendElement(thisPrefix);
>+      thisPrefix.Append(NS_REINTERPRET_CAST(const char*, maxChar), 6);
>+      ranges.AppendElement(thisPrefix);
>+    }
>+    ranges.AppendElement(endQuery);
>+    ranges.Sort();
>+  } else {
>+    // simple range with no holes
>+    ranges.AppendElement(beginQuery);
>+    ranges.AppendElement(endQuery);
>+  }
>+
>+  NS_ASSERTION(ranges.Length() % 2 == 0, "Ranges should be pairs!");
>+
>+  // The nested select expands to nonzero when the item is bookmarked.
>+  // It might be nice to also select hidden bookmarks (unvisited) but that
>+  // made this statement more complicated and should be an unusual case.
>+  nsresult rv;
>+  for (PRUint32 range = 0; range < ranges.Length() - 1; range += 2) {
>+    mozStorageStatementScoper scoper(mDBAutoCompleteQuery);
>+
>+    rv = mDBAutoCompleteQuery->BindUTF8StringParameter(0, ranges[range]);
>+    NS_ENSURE_SUCCESS(rv, rv);
>+    rv = mDBAutoCompleteQuery->BindUTF8StringParameter(1, ranges[range + 1]);
>+    NS_ENSURE_SUCCESS(rv, rv);
> 
>-      if (! resultSet.Add(entryurl, entrytitle, priority))
>-        return NS_ERROR_OUT_OF_MEMORY;
>+    PRBool hasMore;
>+    nsAutoString url, title;
>+    while (NS_SUCCEEDED(mDBAutoCompleteQuery->ExecuteStep(&hasMore)) && hasMore) {
>+      mDBAutoCompleteQuery->GetString(0, url);
>+      mDBAutoCompleteQuery->GetString(1, title);
>+      PRInt32 visitCount = mDBAutoCompleteQuery->AsInt32(2);
>+      PRInt32 priority = ComputeAutoCompletePriority(url, visitCount,
>+          mDBAutoCompleteQuery->AsInt32(3) > 0,
>+          mDBAutoCompleteQuery->AsInt32(4) > 0) + aPriorityDelta;
>+      aResult->AppendElement(AutoCompleteIntermediateResult(
>+          url, title, visitCount, priority));
>     }
>   }
>+  return NS_OK;
>+}
>+
> 
>-  // sort and populate the final result
>-  resultSet.Sort(this);
>-  return resultSet.FillResult(result);
>+// nsNavHistory::AutoCompleteGetPrefixLength
>+
>+PRInt32
>+nsNavHistory::AutoCompleteGetPrefixLength(const nsString& aSpec)
>+{
>+  for (PRUint32 i = 0; i < mAutoCompletePrefixes.Length(); ++i) {
>+    if (StringBeginsWith(aSpec, mAutoCompletePrefixes[i].prefix))
>+      return mAutoCompletePrefixes[i].prefix.Length();
>+  }
>+  return 0; // no prefix
> }
> 
> 
> // nsNavHistory::AutoCompleteRefineHistorySearch
> //
> //    Called when a previous autocomplete result exists and we are adding to
> //    the query (making it more specific). The list is already nicely sorted,
> //    so we can just remove all the old elements that DON'T match the new query.
> 
> nsresult
> nsNavHistory::AutoCompleteRefineHistorySearch(
>                                   const nsAString& aSearchString,
>                                   nsIAutoCompleteResult* aPreviousResult,
>                                   nsIAutoCompleteSimpleResult* aNewResult)
> {
>+  /*
>   // figure out whether any known prefixes are present in the search string
>   // so we know not to ignore them when comparing results later
>   AutoCompleteExclude exclude;
>   AutoCompleteGetExcludeInfo(aSearchString, &exclude);
> 
>   PRUint32 matchCount;
>   aPreviousResult->GetMatchCount(&matchCount);
> 
>@@ -303,180 +632,21 @@ nsNavHistory::AutoCompleteRefineHistoryS
>     NS_ENSURE_SUCCESS(rv, rv);
>     if (AutoCompleteCompare(cururl, aSearchString, exclude)) {
>       nsAutoString curcomment;
>       rv = aPreviousResult->GetCommentAt(i, curcomment);
>       NS_ENSURE_SUCCESS(rv, rv);
>       rv = aNewResult->AppendMatch(cururl, curcomment);
>       NS_ENSURE_SUCCESS(rv, rv);
>     }
>-  }
>+  }*/
>   return NS_OK;
> }
> 
> 
>-// nsNavHistory::AutoCompleteGetExcludeInfo
>-//
>-//    If aURL begins with a protocol or domain prefix from our lists, then mark
>-//    their index in an AutocompleteExclude struct.
>-
>-void
>-nsNavHistory::AutoCompleteGetExcludeInfo(const nsAString& aURL,
>-                                         AutoCompleteExclude* aExclude)
>-{
>-  aExclude->schemePrefix = -1;
>-  aExclude->hostnamePrefix = -1;
>-
>-  PRInt32 index = 0;
>-  PRInt32 i;
>-  for (i = 0; i < mIgnoreSchemes.Count(); ++i) {
>-    nsString* string = mIgnoreSchemes.StringAt(i);
>-    if (Substring(aURL, 0, string->Length()).Equals(*string)) {
>-      aExclude->schemePrefix = i;
>-      index = string->Length();
>-      break;
>-    }
>-  }
>-
>-  for (i = 0; i < mIgnoreHostnames.Count(); ++i) {
>-    nsString* string = mIgnoreHostnames.StringAt(i);
>-    if (Substring(aURL, index, string->Length()).Equals(*string)) {
>-      aExclude->hostnamePrefix = i;
>-      index += string->Length();
>-      break;
>-    }
>-  }
>-
>-  aExclude->postPrefixOffset = index;
>-}
>-
>-
>-// nsNavHistory::AutoCompleteCutPrefix
>-//
>-//    Cut any protocol and domain prefixes from aURL, except for those which
>-//    are specified in aExclude.
>-//
>-//    aExclude can be NULL to cut all possible prefixes
>-//
>-//    This comparison is case-sensitive.  Therefore, it assumes that aUserURL
>-//    is a potential URL whose host name is in all lower case.
>-//
>-//    The aExclude identifies which prefixes were present in the user's typed
>-//    entry, which we DON'T want to cut so that it can match the user input.
>-//    For example. Typed "xyz.com" matches "xyz.com" AND "http://www.xyz.com"
>-//    but "www.xyz.com" still matches "www.xyz.com".
>-
>-void
>-nsNavHistory::AutoCompleteCutPrefix(nsString* aURL,
>-                                    const AutoCompleteExclude* aExclude)
>-{
>-  PRInt32 idx = 0;
>-  PRInt32 i;
>-  for (i = 0; i < mIgnoreSchemes.Count(); ++i) {
>-    if (aExclude && i == aExclude->schemePrefix)
>-      continue;
>-    nsString* string = mIgnoreSchemes.StringAt(i);
>-    if (Substring(*aURL, 0, string->Length()).Equals(*string)) {
>-      idx = string->Length();
>-      break;
>-    }
>-  }
>-
>-  if (idx > 0)
>-    aURL->Cut(0, idx);
>-
>-  idx = 0;
>-  for (i = 0; i < mIgnoreHostnames.Count(); ++i) {
>-    if (aExclude && i == aExclude->hostnamePrefix)
>-      continue;
>-    nsString* string = mIgnoreHostnames.StringAt(i);
>-    if (Substring(*aURL, 0, string->Length()).Equals(*string)) {
>-      idx = string->Length();
>-      break;
>-    }
>-  }
>-
>-  if (idx > 0)
>-    aURL->Cut(0, idx);
>-}
>-
>-
>-
>-// nsNavHistory::AutoCompleteCompare
>-//
>-//    Determines if a given URL from the history matches the user input.
>-//    See AutoCompleteCutPrefix for the meaning of aExclude.
>-
>-PRBool
>-nsNavHistory::AutoCompleteCompare(const nsAString& aHistoryURL,
>-                                  const nsAString& aUserURL,
>-                                  const AutoCompleteExclude& aExclude)
>-{
>-  nsAutoString cutHistoryURL(aHistoryURL);
>-  AutoCompleteCutPrefix(&cutHistoryURL, &aExclude);
>-  return StringBeginsWith(cutHistoryURL, aUserURL);
>-}
>-
>-
>-// nsGlobalHistory::AutoCompleteSortComparison
>-//
>-//    The design and reasoning behind the following autocomplete sort
>-//    implementation is documented in bug 78270. In most cases, the precomputed
>-//    priorities (by ComputeAutoCompletePriority) are used without further
>-//    computation.
>-
>-PRInt32 PR_CALLBACK // static
>-nsNavHistory::AutoCompleteSortComparison(const void* match1Void,
>-                                         const void* match2Void,
>-                                         void *navHistoryVoid)
>-{
>-  // get our class pointer (this is a static function)
>-  nsNavHistory* navHistory = NS_STATIC_CAST(nsNavHistory*, navHistoryVoid);
>-
>-  const AutoCompleteIntermediateResult* match1 = NS_STATIC_CAST(
>-                             const AutoCompleteIntermediateResult*, match1Void);
>-  const AutoCompleteIntermediateResult* match2 = NS_STATIC_CAST(
>-                             const AutoCompleteIntermediateResult*, match2Void);
>-
>-  // In most cases the priorities will be different and we just use them
>-  if (match1->priority != match2->priority)
>-  {
>-    return match2->priority - match1->priority;
>-  }
>-  else
>-  {
>-    // secondary sorting gives priority to site names and paths (ending in a /)
>-    PRBool isPath1 = PR_FALSE, isPath2 = PR_FALSE;
>-    if (!match1->url.IsEmpty())
>-      isPath1 = (match1->url.Last() == PRUnichar('/'));
>-    if (!match2->url.IsEmpty())
>-      isPath2 = (match2->url.Last() == PRUnichar('/'));
>-
>-    if (isPath1 && !isPath2) return -1; // match1->url is a website/path, match2->url isn't
>-    if (!isPath1 && isPath2) return  1; // match1->url isn't a website/path, match2->url is
>-
>-    // find the prefixes so we can sort by the stuff after the prefixes
>-    AutoCompleteExclude prefix1, prefix2;
>-    navHistory->AutoCompleteGetExcludeInfo(match1->url, &prefix1);
>-    navHistory->AutoCompleteGetExcludeInfo(match2->url, &prefix2);
>-
>-    // compare non-prefixed urls
>-    PRInt32 ret = Compare(
>-      Substring(match1->url, prefix1.postPrefixOffset, match1->url.Length()),
>-      Substring(match2->url, prefix2.postPrefixOffset, match2->url.Length()));
>-    if (ret != 0)
>-      return ret;
>-
>-    // sort http://xyz.com before http://www.xyz.com
>-    return prefix1.postPrefixOffset - prefix2.postPrefixOffset;
>-  }
>-  return 0;
>-}
>-
>-
> // ComputeAutoCompletePriority
> //
> //    Favor websites and webpaths more than webpages by boosting
> //    their visit counts.  This assumes that URLs have been normalized,
> //    appending a trailing '/'.
> //
> //    We use addition to boost the visit count rather than multiplication
> //    since we want URLs with large visit counts to remain pretty much
>@@ -484,23 +654,77 @@ nsNavHistory::AutoCompleteSortComparison
> //    often for a reason and there shouldn't be a problem with putting them
> //    high in the autocomplete list regardless of whether they are sites/
> //    paths or pages.  However for URLs visited only a few times, sites
> //    & paths should be presented before pages since they are generally
> //    more likely to be visited again.
> 
> PRInt32
> ComputeAutoCompletePriority(const nsAString& aUrl, PRInt32 aVisitCount,
>-                            PRBool aWasTyped)
>+                            PRBool aWasTyped, PRBool aIsBookmarked)
> {
>   PRInt32 aPriority = aVisitCount;
> 
>   if (!aUrl.IsEmpty()) {
>     // url is a site/path if it has a trailing slash
>     if (aUrl.Last() == PRUnichar('/'))
>       aPriority += AUTOCOMPLETE_NONPAGE_VISIT_COUNT_BOOST;
>   }
> 
>   if (aWasTyped)
>-    aPriority += AUTOCOMPLETE_NONPAGE_VISIT_COUNT_BOOST;
>+    aPriority += AUTOCOMPLETE_TYPED_BOOST;
>+  if (aIsBookmarked)
>+    aPriority += AUTOCOMPLETE_BOOKMARKED_BOOST;
> 
>   return aPriority;
> }
>+
>+
>+// NormalizeAutocompleteInput
>+
>+nsresult NormalizeAutocompleteInput(const nsAString& aInput,
>+                                    nsString& aOutput)
>+{
>+  nsresult rv;
>+
>+  if (aInput.IsEmpty()) {
>+    aOutput.Truncate();
>+    return NS_OK;
>+  }
>+  nsCAutoString input = NS_ConvertUTF16toUTF8(aInput);
>+
>+  nsCOMPtr<nsIURI> uri;
>+  rv = NS_NewURI(getter_AddRefs(uri), input);
>+  PRBool isSchemeAdded = PR_FALSE;
>+  if (NS_FAILED(rv)) {
>+    // it may have failed because there is no scheme, prepend one
>+    isSchemeAdded = PR_TRUE;
>+    input = NS_LITERAL_CSTRING("http://") + input;
>+
>+    rv = NS_NewURI(getter_AddRefs(uri), input);
>+    if (NS_FAILED(rv))
>+      return rv; // still not valid, can't autocomplete this URL
>+  }
>+
>+  nsCAutoString spec;
>+  rv = uri->GetSpec(spec);
>+  NS_ENSURE_SUCCESS(rv, rv);
>+  if (spec.IsEmpty())
>+    return NS_OK; // should never happen but we assume it's not empty below, so check
>+
>+  aOutput = NS_ConvertUTF8toUTF16(spec);
>+
>+  // trim the "http://" scheme if we added it
>+  if (isSchemeAdded) {
>+    NS_ASSERTION(aOutput.Length() > 7, "String impossibly short");
>+    aOutput = Substring(aOutput, 7);
>+  }
>+
>+  // it may have appended a slash, get rid of it
>+  // example: input was "http://www.mozil" the URI spec will be
>+  // "http://www.mozil/" which is obviously wrong to complete against.
>+  // However, it won't always append a slash, for example, for the input
>+  // "http://www.mozilla.org/supp"
>+  if (input[input.Length() - 1] != '/' && aOutput[aOutput.Length() - 1] == '/')
>+    aOutput.Truncate(aOutput.Length() - 1);
>+
>+  return NS_OK;
>+}

Comment 4

[Dave Townsend [:mossop]]

If the pref "browser.urlbar.autoFill" is set to true then this patch causes some fairly broken behaviour. The pref is supposed to put the first result of the autocomplete into the url bar highlighted so you can continue typing to overwrite. But when the phantom host entry is at the top whatever code does this gets confused and the cursor gets moved to the beginning of the url bar.

Not necessarily a problem since I guess that pref is not officially supported, but I do see numerous people asking for it on IRC and so there are likely a fair few using it.

Comment 5

[Brett Wilson]

On 1.8 branch and trunk. Note bug 331144 which makes the results look broken sometimes.

Comment 6

[Gervase Markham [:gerv]]

Bug 451915 - move Firefox/Places bugs to Firefox/Bookmarks and History. Remove all bugspam from this move by filtering for the string "places-to-b-and-h".

In Thunderbird 3.0b, you do that as follows:
Tools | Message Filters
Make sure the correct account is selected. Click "New"
Conditions: Body   contains   places-to-b-and-h
Change the action to "Delete Message".
Select "Manually Run" from the dropdown at the top.
Click OK.

Select the filter in the list, make sure "Inbox" is selected at the bottom, and click "Run Now". This should delete all the bugspam. You can then delete the filter.

Gerv