Bug 455555 - Use asynchronous queries for places AutoComplete.
authorShawn Wilsher <sdwilsh@shawnwilsher.com>
Mon, 13 Jul 2009 12:19:03 -0700
changeset 30902 b2fd524aff54ba2692dd4abd42620be19bcdd7fd
parent 30222 e5393e793a0c8c3fe7ee5c895b5a4d05e6a1bb9d
child 30903 98c36c2d0a522bb4fdc76ee5962b65f45f8810a9
push idunknown
push userunknown
push dateunknown
bugs455555
milestone1.9.2a1pre
Bug 455555 - Use asynchronous queries for places AutoComplete. This changes the location bar's AutoComplete provider to use asynchronous queries instead of synchronous ones. No more blocking the main thread FTW! r=mak r=Mardak r=dietrich
browser/installer/unix/packages-static
browser/installer/windows/packages-static
storage/public/storage.h
toolkit/components/places/public/Makefile.in
toolkit/components/places/public/mozIPlacesAutoComplete.idl
toolkit/components/places/src/Makefile.in
toolkit/components/places/src/SQLFunctions.cpp
toolkit/components/places/src/SQLFunctions.h
toolkit/components/places/src/nsNavHistory.cpp
toolkit/components/places/src/nsNavHistory.h
toolkit/components/places/src/nsNavHistoryAutoComplete.cpp
toolkit/components/places/src/nsPlacesAutoComplete.js
toolkit/components/places/src/nsPlacesModule.cpp
toolkit/components/places/tests/autocomplete/head_autocomplete.js
toolkit/components/places/tests/unit/test_000_frecency.js
--- a/browser/installer/unix/packages-static
+++ b/browser/installer/unix/packages-static
@@ -233,16 +233,17 @@ bin/components/sessionstore.xpt
 bin/components/nsURLFormatter.js
 bin/components/urlformatter.xpt
 bin/components/libbrowserdirprovider.so
 bin/components/libbrowsercomps.so
 bin/components/txEXSLTRegExFunctions.js
 bin/components/nsLivemarkService.js
 bin/components/nsTaggingService.js
 bin/components/nsPlacesDBFlush.js
+bin/components/nsPlacesAutoComplete.js
 bin/components/nsDefaultCLH.js
 bin/components/nsContentPrefService.js
 bin/components/nsContentDispatchChooser.js
 bin/components/nsHandlerService.js
 bin/components/nsWebHandlerApp.js
 bin/components/libdbusservice.so
 bin/components/aboutRights.js
 bin/components/aboutRobots.js
--- a/browser/installer/windows/packages-static
+++ b/browser/installer/windows/packages-static
@@ -240,16 +240,17 @@ bin\components\sessionstore.xpt
 bin\components\nsURLFormatter.js
 bin\components\urlformatter.xpt
 bin\components\browserdirprovider.dll
 bin\components\brwsrcmp.dll
 bin\components\txEXSLTRegExFunctions.js
 bin\components\nsLivemarkService.js
 bin\components\nsTaggingService.js
 bin\components\nsPlacesDBFlush.js
+bin\components\nsPlacesAutoComplete.js
 bin\components\nsDefaultCLH.js
 bin\components\nsContentPrefService.js
 bin\components\nsContentDispatchChooser.js
 bin\components\nsHandlerService.js
 bin\components\nsWebHandlerApp.js
 bin\components\aboutRights.js
 bin\components\aboutRobots.js
 bin\components\aboutCertError.js
--- a/storage/public/storage.h
+++ b/storage/public/storage.h
@@ -56,9 +56,11 @@
 #include "mozIStorageStatementCallback.h"
 
 ////////////////////////////////////////////////////////////////////////////////
 //// Native Language Helpers
 
 #include "mozStorageHelper.h"
 #include "mozStorageCID.h"
 
+#include "mozilla/storage/Variant.h"
+
 #endif // mozilla_storage_h_
--- a/toolkit/components/places/public/Makefile.in
+++ b/toolkit/components/places/public/Makefile.in
@@ -56,12 +56,13 @@ XPIDLSRCS += \
   nsIBrowserHistory.idl \
   nsIFaviconService.idl \
   nsINavBookmarksService.idl \
   nsILivemarkService.idl \
   nsIDynamicContainer.idl \
   nsITaggingService.idl  \
   nsPIPlacesDatabase.idl \
   nsPIPlacesHistoryListenersNotifier.idl \
+  mozIPlacesAutoComplete.idl \
   $(NULL)
 endif
 
 include $(topsrcdir)/config/rules.mk
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/public/mozIPlacesAutoComplete.idl
@@ -0,0 +1,110 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: sw=2 ts=2 sts=2
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Places code
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Shawn Wilsher <me@shawnwilsher.com> (Original Author)
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * 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 ***** */
+
+#include "nsISupports.idl"
+
+/**
+ * This interface provides some constants used by the Places AutoComplete
+ * search provider.
+ */
+[scriptable, uuid(a5ae8332-333c-412a-bb02-a35df8247714)]
+interface mozIPlacesAutoComplete : nsISupports
+{
+  //////////////////////////////////////////////////////////////////////////////
+  //// Matching Constants
+
+  /**
+   * Match anywhere in each searchable term.
+   */
+  const long MATCH_ANYWHERE = 0;
+
+  /**
+   * Match first on word boundaries, and if we do not get enough results, then
+   * match anywhere in each searchable term.
+   */
+  const long MATCH_BOUNDARY_ANYWHERE = 1;
+
+  /**
+   * Match on word boundaries in each searchable term.
+   */
+  const long MATCH_BOUNDARY = 2;
+
+  /**
+   * Match only the beginning of each search term.
+   */
+  const long MATCH_BEGINNING = 3;
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// Search Behavior Constants
+
+  /**
+   * Search through history.
+   */
+  const long BEHAVIOR_HISTORY = 1 << 0;
+
+  /**
+   * Search though bookmarks.
+   */
+  const long BEHAVIOR_BOOKMARK = 1 << 1;
+
+  /**
+   * Search through tags.
+   */
+  const long BEHAVIOR_TAG = 1 << 2;
+
+  /**
+   * Search the title of pages.
+   */
+  const long BEHAVIOR_TITLE = 1 << 3;
+
+  /**
+   * Search the URL of pages.
+   */
+  const long BEHAVIOR_URL = 1 << 4;
+
+  /**
+   * Search for typed pages.
+   */
+  const long BEHAVIOR_TYPED = 1 << 5;
+
+  /**
+   * Search javascript: URLs.
+   */
+  const long BEHAVIOR_JAVASCRIPT = 1 << 6;
+};
--- a/toolkit/components/places/src/Makefile.in
+++ b/toolkit/components/places/src/Makefile.in
@@ -82,36 +82,39 @@ CPPSRCS = \
           nsNavHistory.cpp \
           nsNavHistoryExpire.cpp \
           nsNavHistoryQuery.cpp \
           nsNavHistoryResult.cpp \
           nsNavBookmarks.cpp \
           nsMaybeWeakPtr.cpp \
           nsMorkHistoryImporter.cpp \
           nsPlacesModule.cpp \
+          SQLFunctions.cpp \
           $(NULL)
 
-ifdef MOZ_XUL
-CPPSRCS += \
-          nsNavHistoryAutoComplete.cpp \
-          $(NULL)
-endif
-
 EXTRA_DSO_LDOPTS += \
 	$(DEPTH)/db/morkreader/$(LIB_PREFIX)morkreader_s.$(LIB_SUFFIX) \
 	$(MOZ_UNICHARUTIL_LIBS) \
 	$(MOZ_COMPONENT_LIBS) \
 	$(NULL)
 
 LOCAL_INCLUDES += -I$(srcdir)/../../build
 
-EXTRA_PP_COMPONENTS = nsLivemarkService.js \
-                      nsTaggingService.js \
-                      nsPlacesDBFlush.js \
-                      $(NULL)
+EXTRA_PP_COMPONENTS = \
+  nsLivemarkService.js \
+  nsTaggingService.js \
+  $(NULL)
+
+EXTRA_COMPONENTS = \
+  nsPlacesDBFlush.js \
+  $(NULL)
+
+ifdef MOZ_XUL
+EXTRA_COMPONENTS += nsPlacesAutoComplete.js
+endif
 
 EXTRA_JS_MODULES = \
   utils.js \
   PlacesDBUtils.jsm \
   $(NULL)
 
 EXTRA_PP_JS_MODULES = utils.js
 
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/src/SQLFunctions.cpp
@@ -0,0 +1,292 @@
+/* vim: sw=2 ts=2 et lcs=trail\:.,tab\:>~ :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Places code.
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Shawn Wilsher <me@shawnwilsher.com> (Original Author)
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * 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 ***** */
+
+#include "mozilla/storage.h"
+#include "nsString.h"
+#include "nsUnicharUtils.h"
+#include "nsWhitespaceTokenizer.h"
+#include "nsEscape.h"
+#include "mozIPlacesAutoComplete.h"
+#include "SQLFunctions.h"
+
+using namespace mozilla::storage;
+
+namespace mozilla {
+namespace places {
+
+////////////////////////////////////////////////////////////////////////////////
+//// AutoComplete Matching Function
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// MatchAutoCompleteFunction
+
+  /* static */
+  nsresult
+  MatchAutoCompleteFunction::create(mozIStorageConnection *aDBConn)
+  {
+    nsRefPtr<MatchAutoCompleteFunction> function(new MatchAutoCompleteFunction);
+    NS_ENSURE_TRUE(function, NS_ERROR_OUT_OF_MEMORY);
+
+    nsresult rv = aDBConn->CreateFunction(
+      NS_LITERAL_CSTRING("autocomplete_match"), kArgIndexLength, function
+    );
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    return NS_OK;
+  }
+
+  /* static */
+  nsString
+  MatchAutoCompleteFunction::fixupURISpec(const nsDependentCString &aURISpec)
+  {
+    nsCAutoString unescapedSpec;
+    (void)NS_UnescapeURL(aURISpec, esc_SkipControl | esc_AlwaysCopy,
+                         unescapedSpec);
+
+    // If this unescaped string is valid UTF-8, we'll convert it.  Otherwise,
+    // we will simply convert our original string.
+    nsString fixedSpec;
+    if (IsUTF8(unescapedSpec))
+      CopyUTF8toUTF16(unescapedSpec, fixedSpec);
+    else
+      CopyUTF8toUTF16(aURISpec, fixedSpec);
+
+    if (StringBeginsWith(fixedSpec, NS_LITERAL_STRING("http://")))
+      fixedSpec.Cut(0, 7);
+    else if (StringBeginsWith(fixedSpec, NS_LITERAL_STRING("https://")))
+      fixedSpec.Cut(0, 8);
+    else if (StringBeginsWith(fixedSpec, NS_LITERAL_STRING("ftp://")))
+      fixedSpec.Cut(0, 6);
+
+    return fixedSpec;
+  }
+
+  /* static */
+  bool
+  MatchAutoCompleteFunction::findAnywhere(const nsDependentSubstring &aToken,
+                                          const nsAString &aSourceString)
+  {
+    return !!CaseInsensitiveFindInReadable(aToken, aSourceString);
+  }
+
+  /* static */
+  bool
+  MatchAutoCompleteFunction::findBeginning(const nsDependentSubstring &aToken,
+                                           const nsAString &aSourceString)
+  {
+    return !!StringBeginsWith(aSourceString, aToken,
+                              nsCaseInsensitiveStringComparator());
+  }
+
+  /* static */
+  bool
+  MatchAutoCompleteFunction::findOnBoundary(const nsDependentSubstring &aToken,
+                                            const nsAString &aSourceString)
+  {
+    // We cannot match anything if there is nothing to search.
+    if (aSourceString.IsEmpty())
+      return false;
+
+    // Define a const instance of this class so it is created once.
+    const nsCaseInsensitiveStringComparator caseInsensitiveCompare;
+
+    const_wchar_iterator tokenStart(aToken.BeginReading()),
+                         tokenEnd(aToken.EndReading()),
+                         sourceStart(aSourceString.BeginReading()),
+                         sourceEnd(aSourceString.EndReading());
+
+    // The start of aSourceString is considered a word boundary, so start there.
+    do {
+      // We are on a word boundary, so start by copying the iterators.
+      const_wchar_iterator testTokenItr(tokenStart),
+                           testSourceItr(sourceStart);
+
+      // Keep trying to match the token one by one until it doesn't match.
+      while (!caseInsensitiveCompare(*testTokenItr, *testSourceItr)) {
+        // We matched something, so move down one.
+        testTokenItr++;
+        testSourceItr++;
+
+        // Matched the full token, so we are done!
+        if (testTokenItr == tokenEnd)
+          return true;
+
+        // However, if we ran into the end of the source while matching the
+        // token, we will not find it.
+        if (testSourceItr == sourceEnd)
+          return false;
+      }
+
+      // Always advance our starting iterator, and if we are not currently on a
+      // word boundary, advance to the next word boundary.
+      if (!isWordBoundary(ToLowerCase(*sourceStart++)))
+        sourceStart = nextWordBoundary(sourceStart, sourceEnd);
+    } while (sourceStart != sourceEnd);
+
+    return false;
+  }
+
+  /* static */
+  MatchAutoCompleteFunction::const_wchar_iterator
+  MatchAutoCompleteFunction::nextWordBoundary(const_wchar_iterator aStart,
+                                              const_wchar_iterator aEnd)
+  {
+    while (aStart != aEnd && !isWordBoundary(*aStart))
+      aStart++;
+    return aStart;
+  }
+
+  /* static */
+  bool
+  MatchAutoCompleteFunction::isWordBoundary(const PRUnichar &aChar)
+  {
+    // Only check lowercase alphabetic characters so we can match CamelCase
+    // words.  This means that matches will happen after an upper-case
+    // character.
+    return !(PRUnichar('a') <= aChar && aChar <= PRUnichar('z'));
+  }
+
+  /* static */
+  MatchAutoCompleteFunction::searchFunctionPtr
+  MatchAutoCompleteFunction::getSearchFunction(PRInt32 aBehavior)
+  {
+    switch (aBehavior) {
+      case mozIPlacesAutoComplete::MATCH_ANYWHERE:
+        return findAnywhere;
+      case mozIPlacesAutoComplete::MATCH_BEGINNING:
+        return findBeginning;
+      case mozIPlacesAutoComplete::MATCH_BOUNDARY:
+      default:
+        return findOnBoundary;
+    };
+  }
+
+  NS_IMPL_THREADSAFE_ISUPPORTS1(
+    MatchAutoCompleteFunction,
+    mozIStorageFunction
+  )
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// mozIStorageFunction
+
+  NS_IMETHODIMP
+  MatchAutoCompleteFunction::OnFunctionCall(mozIStorageValueArray *aArguments,
+                                            nsIVariant **_result)
+  {
+    // Macro to make the code a bit cleaner and easier to read.  Operates on
+    // searchBehavior.
+    PRInt32 searchBehavior = aArguments->AsInt32(kArgIndexSearchBehavior);
+    #define HAS_BEHAVIOR(aBitName) \
+      (searchBehavior & mozIPlacesAutoComplete::BEHAVIOR_##aBitName)
+
+    nsDependentString searchString;
+    (void)aArguments->GetString(kArgSearchString, searchString);
+    nsDependentCString url;
+    (void)aArguments->GetUTF8String(kArgIndexURL, url);
+
+    // We only want to filter javascript: URLs if we are not supposed to search
+    // for them, and the search does not start with "javascript:".
+    if (!HAS_BEHAVIOR(JAVASCRIPT) &&
+        !StringBeginsWith(searchString, NS_LITERAL_STRING("javascript:")) &&
+        StringBeginsWith(url, NS_LITERAL_CSTRING("javascript:"))) {
+      NS_IF_ADDREF(*_result = new IntegerVariant(0));
+      NS_ENSURE_TRUE(*_result, NS_ERROR_OUT_OF_MEMORY);
+      return NS_OK;
+    }
+
+    PRInt32 visitCount = aArguments->AsInt32(kArgIndexVisitCount);
+    bool typed = aArguments->AsInt32(kArgIndexTyped) ? true : false;
+    bool bookmark = aArguments->AsInt32(kArgIndexBookmark) ? true : false;
+    nsDependentString tags;
+    (void)aArguments->GetString(kArgIndexTags, tags);
+
+    // Make sure we match all the filter requirements.  If a given restriction
+    // is active, make sure the corresponding condition is not true.
+    bool matches = !(
+      (HAS_BEHAVIOR(HISTORY) && visitCount == 0) ||
+      (HAS_BEHAVIOR(TYPED) && !typed) ||
+      (HAS_BEHAVIOR(BOOKMARK) && !bookmark) ||
+      (HAS_BEHAVIOR(TAG) && tags.IsVoid())
+    );
+    if (!matches) {
+      NS_IF_ADDREF(*_result = new IntegerVariant(0));
+      NS_ENSURE_TRUE(*_result, NS_ERROR_OUT_OF_MEMORY);
+      return NS_OK;
+    }
+
+    // Clean up our URI spec and prepare it for searching.
+    nsString fixedURI = fixupURISpec(url);
+
+    // Obtain our search function.
+    PRInt32 matchBehavior = aArguments->AsInt32(kArgIndexMatchBehavior);
+    searchFunctionPtr searchFunction = getSearchFunction(matchBehavior);
+
+    nsDependentString title;
+    (void)aArguments->GetString(kArgIndexTitle, title);
+
+    // Determine if every token matches either the bookmark title, tags, page
+    // title, or page URL.
+    nsWhitespaceTokenizer tokenizer(searchString);
+    while (matches && tokenizer.hasMoreTokens()) {
+      const nsDependentSubstring &token = tokenizer.nextToken();
+
+      bool matchTags = searchFunction(token, tags);
+      bool matchTitle = searchFunction(token, title);
+
+      // Make sure we match something in the title or tags if we have to.
+      matches = matchTags || matchTitle;
+      if (HAS_BEHAVIOR(TITLE) && !matches)
+        break;
+
+      bool matchURL = searchFunction(token, fixedURI);
+      // If we do not match the URL when we have to, reset matches to false.
+      // Otherwise, keep track that we did match the current search.
+      if (HAS_BEHAVIOR(URL) && !matchURL)
+        matches = false;
+      else
+        matches = matches || matchURL;
+    }
+
+    NS_IF_ADDREF(*_result = new IntegerVariant(matches ? 1 : 0));
+    NS_ENSURE_TRUE(*_result, NS_ERROR_OUT_OF_MEMORY);
+    return NS_OK;
+    #undef HAS_BEHAVIOR
+  }
+
+} // namespace places
+} // namespace mozilla
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/src/SQLFunctions.h
@@ -0,0 +1,208 @@
+/* vim: sw=2 ts=2 et lcs=trail\:.,tab\:>~ :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Places code.
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Shawn Wilsher <me@shawnwilsher.com> (Original Author)
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * 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 ***** */
+
+#ifndef mozilla_places_SQLFunctions_h_
+#define mozilla_places_SQLFunctions_h_
+
+/**
+ * This file contains functions that Places adds to the database handle that can
+ * be accessed by SQL queries.
+ */
+
+#include "mozIStorageFunction.h"
+
+class mozIStorageConnection;
+
+namespace mozilla {
+namespace places {
+
+////////////////////////////////////////////////////////////////////////////////
+//// AutoComplete Matching Function
+
+/**
+ * This function is used to determine if a given set of data should match an
+ * AutoComplete query.
+ *
+ * In SQL, you'd use it in the WHERE clause like so:
+ * WHERE AUTOCOMPLETE_MATCH(aSearchString, aURL, aTitle, aTags, aVisitCount,
+ *                          aTyped)
+ *
+ * @param aSearchString
+ *        The string to compare against.
+ * @param aURL
+ *        The URL to test for an AutoComplete match.
+ * @param aTitle
+ *        The title to test for an AutoComplete match.
+ * @param aTags
+ *        The tags to test for an AutoComplete match.
+ * @param aVisitCount
+ *        The number of visits aURL has.
+ * @param aTyped
+ *        Indicates if aURL is a typed URL or not.  Treated as a boolean.
+ * @param aBookmark
+ *        Indicates if aURL is a bookmark or not.  Treated as a boolean.
+ * @param aMatchBehavior
+ *        The match behavior to use for this search.
+ * @param aSearchBehavior
+ *        A bitfield dictating the search behavior.
+ */
+class MatchAutoCompleteFunction : public mozIStorageFunction
+{
+public:
+  NS_DECL_ISUPPORTS
+  NS_DECL_MOZISTORAGEFUNCTION
+
+  /**
+   * Registers the function with the specified database connection.
+   *
+   * @param aDBConn
+   *        The database connection to register with.
+   */
+  static nsresult create(mozIStorageConnection *aDBConn);
+
+private:
+  /**
+   * Argument Indexes
+   */
+  static const PRUint32 kArgSearchString = 0;
+  static const PRUint32 kArgIndexURL = 1;
+  static const PRUint32 kArgIndexTitle = 2;
+  static const PRUint32 kArgIndexTags = 3;
+  static const PRUint32 kArgIndexVisitCount = 4;
+  static const PRUint32 kArgIndexTyped = 5;
+  static const PRUint32 kArgIndexBookmark = 6;
+  static const PRUint32 kArgIndexMatchBehavior = 7;
+  static const PRUint32 kArgIndexSearchBehavior = 8;
+  static const PRUint32 kArgIndexLength = 9;
+
+  /**
+   * Typedefs
+   */
+  typedef bool (*searchFunctionPtr)(const nsDependentSubstring &aToken,
+                                    const nsAString &aSourceString);
+
+  typedef nsAString::const_char_iterator const_wchar_iterator;
+
+  /**
+   * Obtains the search function to match on.
+   *
+   * @param aBehavior
+   *        The matching behavior to use defined by one of the
+   *        mozIPlacesAutoComplete::MATCH_* values.
+   * @return a pointer to the function that will perform the proper search.
+   */
+  static searchFunctionPtr getSearchFunction(PRInt32 aBehavior);
+
+  /**
+   * Searches aSourceString for aToken anywhere in the string in a case-
+   * insensitive way.
+   *
+   * @param aToken
+   *        The string to search for.
+   * @param aSourceString
+   *        The string to search.
+   * @return true if found, false otherwise.
+   */
+  static bool findAnywhere(const nsDependentSubstring &aToken,
+                           const nsAString &aSourceString);
+
+  /**
+   * Tests if aSourceString starts with aToken.
+   *
+   * @param aToken
+   *        The string to search for.
+   * @param aSourceString
+   *        The string to search.
+   * @return true if found, false otherwise.
+   */
+  static bool findBeginning(const nsDependentSubstring &aToken,
+                            const nsAString &aSourceString);
+
+  /**
+   * Tests if aToken is found on a word boundary in aSourceString.
+   *
+   * @param aToken
+   *        The string to search for.
+   * @param aSourceString
+   *        The string to search.
+   * @return true if found, false otherwise.
+   */
+  static bool findOnBoundary(const nsDependentSubstring &aToken,
+                             const nsAString &aSourceString);
+
+  /**
+   * Obtains an iterator to the next word boundary as defined by isWordBoundary.
+   *
+   * @param aStart
+   *        An iterator pointing to the start of the string.
+   * @param aEnd
+   *        An iterator pointing to the end of the string.
+   * @return an iterator pointing to the next word boundary.
+   */
+  static const_wchar_iterator nextWordBoundary(const_wchar_iterator aStart,
+                                               const_wchar_iterator aEnd);
+  /**
+   * Determines if aChar is a word boundary.  A 'word boundary' is anything that
+   * is not used to build up a word from a string of characters.  We are very
+   * conservative here because anything that we do not list will be treated as a
+   * word boundary.  This means searching for that not-actually-a-word-boundary
+   * character can still be matched in the middle of a word.
+   *
+   * @param aChar
+   *        The Unicode character to check against.
+   * @return true if the character is considered a word boundary, false
+   *          otherwise.
+   */
+  static inline bool isWordBoundary(const PRUnichar &aChar);
+
+  /**
+   * Fixes a URI's spec such that it is ready to be searched.  This includes
+   * unescaping escaped characters and removing certain specs that we do not
+   * care to search for.
+   *
+   * @param aURISpec
+   *        The spec of the URI to prepare for searching.
+   * @return the new string to use for the URI spec.
+   */
+  static nsString fixupURISpec(const nsDependentCString &aURISpec);
+};
+
+} // namespace places
+} // namespace storage
+
+#endif // mozilla_places_SQLFunctions_h_
--- a/toolkit/components/places/src/nsNavHistory.cpp
+++ b/toolkit/components/places/src/nsNavHistory.cpp
@@ -49,16 +49,17 @@
 #include "nsAnnotationService.h"
 #include "nsIIdleService.h"
 #include "nsILivemarkService.h"
 
 #include "nsPlacesTables.h"
 #include "nsPlacesIndexes.h"
 #include "nsPlacesTriggers.h"
 #include "nsPlacesMacros.h"
+#include "SQLFunctions.h"
 
 #include "nsIArray.h"
 #include "nsTArray.h"
 #include "nsArrayEnumerator.h"
 #include "nsCollationCID.h"
 #include "nsCOMPtr.h"
 #include "nsCRT.h"
 #include "nsDebug.h"
@@ -84,30 +85,28 @@
 #include "prprf.h"
 #include "nsEscape.h"
 #include "nsIVariant.h"
 #include "nsVariant.h"
 #include "nsIEffectiveTLDService.h"
 #include "nsIIDNService.h"
 #include "nsIClassInfoImpl.h"
 #include "nsThreadUtils.h"
-
-#include "mozIStorageConnection.h"
-#include "mozIStorageFunction.h"
-#include "mozIStoragePendingStatement.h"
-#include "mozIStorageService.h"
-#include "mozIStorageStatement.h"
-#include "mozIStorageValueArray.h"
-#include "mozStorageCID.h"
-#include "mozStorageHelper.h"
-#include "mozIStorageError.h"
 #include "nsAppDirectoryServiceDefs.h"
+#include "mozilla/storage.h"
+
+#ifdef MOZ_XUL
+#include "nsIAutoCompleteInput.h"
+#include "nsIAutoCompletePopup.h"
+#endif
 
 #include "nsMathUtils.h" // for NS_ceilf()
 
+using namespace mozilla::places;
+
 // Microsecond timeout for "recent" events such as typed and bookmark following.
 // If you typed it more than this time ago, it's not recent.
 // This is 15 minutes           m    s/m  us/s
 #define RECENT_EVENT_THRESHOLD (15 * 60 * PR_USEC_PER_SEC)
 
 // Microseconds ago to look for redirects when updating bookmarks. Used to
 // compute the threshold for nsNavBookmarks::AddBookmarkToHash
 #define BOOKMARK_REDIRECT_TIME_THRESHOLD (2 * 60 * PR_USEC_PER_SEC)
@@ -119,30 +118,16 @@
 // 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_MIN    "history_expire_days_min"
 #define PREF_BROWSER_HISTORY_EXPIRE_DAYS_MAX    "history_expire_days"
 #define PREF_BROWSER_HISTORY_EXPIRE_SITES       "history_expire_sites"
-#define PREF_AUTOCOMPLETE_ENABLED               "urlbar.autocomplete.enabled"
-#define PREF_AUTOCOMPLETE_MATCH_BEHAVIOR        "urlbar.matchBehavior"
-#define PREF_AUTOCOMPLETE_FILTER_JAVASCRIPT     "urlbar.filter.javascript"
-#define PREF_AUTOCOMPLETE_ENABLED               "urlbar.autocomplete.enabled"
-#define PREF_AUTOCOMPLETE_MAX_RICH_RESULTS      "urlbar.maxRichResults"
-#define PREF_AUTOCOMPLETE_DEFAULT_BEHAVIOR      "urlbar.default.behavior"
-#define PREF_AUTOCOMPLETE_RESTRICT_HISTORY      "urlbar.restrict.history"
-#define PREF_AUTOCOMPLETE_RESTRICT_BOOKMARK     "urlbar.restrict.bookmark"
-#define PREF_AUTOCOMPLETE_RESTRICT_TAG          "urlbar.restrict.tag"
-#define PREF_AUTOCOMPLETE_MATCH_TITLE           "urlbar.match.title"
-#define PREF_AUTOCOMPLETE_MATCH_URL             "urlbar.match.url"
-#define PREF_AUTOCOMPLETE_RESTRICT_TYPED        "urlbar.restrict.typed"
-#define PREF_AUTOCOMPLETE_SEARCH_CHUNK_SIZE     "urlbar.search.chunkSize"
-#define PREF_AUTOCOMPLETE_SEARCH_TIMEOUT        "urlbar.search.timeout"
 #define PREF_DB_CACHE_PERCENTAGE                "history_cache_percentage"
 #define PREF_FRECENCY_NUM_VISITS                "places.frecency.numVisits"
 #define PREF_FRECENCY_FIRST_BUCKET_CUTOFF       "places.frecency.firstBucketCutoff"
 #define PREF_FRECENCY_SECOND_BUCKET_CUTOFF      "places.frecency.secondBucketCutoff"
 #define PREF_FRECENCY_THIRD_BUCKET_CUTOFF       "places.frecency.thirdBucketCutoff"
 #define PREF_FRECENCY_FOURTH_BUCKET_CUTOFF      "places.frecency.fourthBucketCutoff"
 #define PREF_FRECENCY_FIRST_BUCKET_WEIGHT       "places.frecency.firstBucketWeight"
 #define PREF_FRECENCY_SECOND_BUCKET_WEIGHT      "places.frecency.secondBucketWeight"
@@ -155,16 +140,18 @@
 #define PREF_FRECENCY_BOOKMARK_VISIT_BONUS      "places.frecency.bookmarkVisitBonus"
 #define PREF_FRECENCY_DOWNLOAD_VISIT_BONUS      "places.frecency.downloadVisitBonus"
 #define PREF_FRECENCY_PERM_REDIRECT_VISIT_BONUS "places.frecency.permRedirectVisitBonus"
 #define PREF_FRECENCY_TEMP_REDIRECT_VISIT_BONUS "places.frecency.tempRedirectVisitBonus"
 #define PREF_FRECENCY_DEFAULT_VISIT_BONUS       "places.frecency.defaultVisitBonus"
 #define PREF_FRECENCY_UNVISITED_BOOKMARK_BONUS  "places.frecency.unvisitedBookmarkBonus"
 #define PREF_FRECENCY_UNVISITED_TYPED_BONUS     "places.frecency.unvisitedTypedBonus"
 
+#define PLACES_AUTOCOMPLETE_FEEDBACK_UPDATED_TOPIC "places-autocomplete-feedback-updated"
+
 // Default (integer) value of PREF_DB_CACHE_PERCENTAGE from 0-100
 // This is 6% of machine memory, giving 15MB for a user with 256MB of memory.
 // The most that will be used is the size of the DB file. Normal history sizes
 // look like 10MB would be a high average for a typical user, so the maximum
 // should not normally be required.
 #define DEFAULT_DB_CACHE_PERCENTAGE 6
 
 // We set the default database page size to be larger. sqlite's default is 1K.
@@ -234,20 +221,16 @@ NS_INTERFACE_MAP_BEGIN(nsNavHistory)
   NS_INTERFACE_MAP_ENTRY(nsIGlobalHistory3)
   NS_INTERFACE_MAP_ENTRY(nsIDownloadHistory)
   NS_INTERFACE_MAP_ENTRY(nsIBrowserHistory)
   NS_INTERFACE_MAP_ENTRY(nsIObserver)
   NS_INTERFACE_MAP_ENTRY(nsISupportsWeakReference)
   NS_INTERFACE_MAP_ENTRY(nsICharsetResolver)
   NS_INTERFACE_MAP_ENTRY(nsPIPlacesDatabase)
   NS_INTERFACE_MAP_ENTRY(nsPIPlacesHistoryListenersNotifier)
-#ifdef MOZ_XUL
-  NS_INTERFACE_MAP_ENTRY(nsIAutoCompleteSearch)
-  NS_INTERFACE_MAP_ENTRY(nsIAutoCompleteSimpleResultListener)
-#endif
   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsINavHistoryService)
   NS_IMPL_QUERY_CLASSINFO(nsNavHistory)
 NS_INTERFACE_MAP_END
 
 // We don't care about flattening everything
 NS_IMPL_CI_INTERFACE_GETTER5(
   nsNavHistory
 , nsINavHistoryService
@@ -361,31 +344,16 @@ const PRInt32 nsNavHistory::kGetInfoInde
 const PRInt32 nsNavHistory::kGetInfoIndex_VisitCount = 4;
 const PRInt32 nsNavHistory::kGetInfoIndex_VisitDate = 5;
 const PRInt32 nsNavHistory::kGetInfoIndex_FaviconURL = 6;
 const PRInt32 nsNavHistory::kGetInfoIndex_SessionId = 7;
 const PRInt32 nsNavHistory::kGetInfoIndex_ItemId = 8;
 const PRInt32 nsNavHistory::kGetInfoIndex_ItemDateAdded = 9;
 const PRInt32 nsNavHistory::kGetInfoIndex_ItemLastModified = 10;
 
-const PRInt32 nsNavHistory::kAutoCompleteIndex_URL = 0;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_Title = 1;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_FaviconURL = 2;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_ParentId = 3;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_BookmarkTitle = 4;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_Tags = 5;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_VisitCount = 6;
-const PRInt32 nsNavHistory::kAutoCompleteIndex_Typed = 7;
-
-const PRInt32 nsNavHistory::kAutoCompleteBehaviorHistory = 1 << 0;
-const PRInt32 nsNavHistory::kAutoCompleteBehaviorBookmark = 1 << 1;
-const PRInt32 nsNavHistory::kAutoCompleteBehaviorTag = 1 << 2;
-const PRInt32 nsNavHistory::kAutoCompleteBehaviorTitle = 1 << 3;
-const PRInt32 nsNavHistory::kAutoCompleteBehaviorUrl = 1 << 4;
-const PRInt32 nsNavHistory::kAutoCompleteBehaviorTyped = 1 << 5;
 
 static const char* gQuitApplicationGrantedMessage = "quit-application-granted";
 static const char* gXpcomShutdown = "xpcom-shutdown";
 static const char* gAutoCompleteFeedback = "autocomplete-will-enter-text";
 static const char* gIdleDaily = "idle-daily";
 
 // annotation names
 const char nsNavHistory::kAnnotationPreviousEncoding[] = "history/encoding";
@@ -419,31 +387,16 @@ nsNavHistory::GetSingleton()
 
 // nsNavHistory::nsNavHistory
 
 nsNavHistory::nsNavHistory() : mBatchLevel(0),
                                mBatchHasTransaction(PR_FALSE),
                                mNowValid(PR_FALSE),
                                mExpireNowTimer(nsnull),
                                mExpire(this),
-                               mAutoCompleteEnabled(PR_TRUE),
-                               mAutoCompleteMatchBehavior(MATCH_BOUNDARY_ANYWHERE),
-                               mAutoCompleteMaxResults(25),
-                               mAutoCompleteRestrictHistory(NS_LITERAL_STRING("^")),
-                               mAutoCompleteRestrictBookmark(NS_LITERAL_STRING("*")),
-                               mAutoCompleteRestrictTag(NS_LITERAL_STRING("+")),
-                               mAutoCompleteMatchTitle(NS_LITERAL_STRING("#")),
-                               mAutoCompleteMatchUrl(NS_LITERAL_STRING("@")),
-                               mAutoCompleteRestrictTyped(NS_LITERAL_STRING("~")),
-                               mAutoCompleteSearchChunkSize(100),
-                               mAutoCompleteSearchTimeout(100),
-                               mAutoCompleteDefaultBehavior(0),
-                               mAutoCompleteCurrentBehavior(0),
-                               mPreviousChunkOffset(-1),
-                               mAutoCompleteFinishedSearch(PR_FALSE),
                                mExpireDaysMin(0),
                                mExpireDaysMax(0),
                                mExpireSites(0),
                                mNumVisitsForFrecency(10),
                                mTagsFolder(-1),
                                mInPrivateBrowsing(PRIVATEBROWSING_NOTINITED),
                                mDatabaseStatus(DATABASE_STATUS_OK),
                                mCanNotify(true),
@@ -514,21 +467,16 @@ nsNavHistory::Init()
   // Notify we have finished database initialization.
   // Enqueue the notification, so if we init another service that requires
   // nsNavHistoryService we don't recursive try to get it.
   nsRefPtr<PlacesEvent> completeEvent =
     new PlacesEvent(PLACES_INIT_COMPLETE_EVENT_TOPIC);
   rv = NS_DispatchToMainThread(completeEvent);
   NS_ENSURE_SUCCESS(rv, rv);
 
-#ifdef MOZ_XUL
-  rv = InitAutoComplete();
-  NS_ENSURE_SUCCESS(rv, rv);
-#endif
-
   // 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_historyvisits" won't have good performance.
   // This is long before we use our temporary tables, so we do not have to join
   // on moz_historyvisits_temp to get the right result here.
   {
     nsCOMPtr<mozIStorageStatement> selectSession;
     rv = mDBConn->CreateStatement(NS_LITERAL_CSTRING(
@@ -560,29 +508,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_ENABLED, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_MATCH_BEHAVIOR, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_FILTER_JAVASCRIPT, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_MAX_RICH_RESULTS, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_DEFAULT_BEHAVIOR, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_RESTRICT_HISTORY, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_RESTRICT_BOOKMARK, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_RESTRICT_TAG, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_MATCH_TITLE, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_MATCH_URL, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_RESTRICT_TYPED, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_SEARCH_CHUNK_SIZE, this, PR_FALSE);
-    pbi->AddObserver(PREF_AUTOCOMPLETE_SEARCH_TIMEOUT, this, PR_FALSE);
     pbi->AddObserver(PREF_BROWSER_HISTORY_EXPIRE_DAYS_MAX, this, PR_FALSE);
     pbi->AddObserver(PREF_BROWSER_HISTORY_EXPIRE_DAYS_MIN, this, PR_FALSE);
     pbi->AddObserver(PREF_BROWSER_HISTORY_EXPIRE_SITES, this, PR_FALSE);
   }
 
   observerService->AddObserver(this, gQuitApplicationGrantedMessage, PR_FALSE);
   observerService->AddObserver(this, gXpcomShutdown, PR_FALSE);
   observerService->AddObserver(this, gAutoCompleteFeedback, PR_FALSE);
@@ -1146,21 +1081,25 @@ nsNavHistory::InitViews()
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 nsNavHistory::InitFunctions()
 {
-  nsresult rv;
-
-  rv = mDBConn->CreateFunction(
-      NS_LITERAL_CSTRING("get_unreversed_host"), 1, 
-      new mozStorageFunctionGetUnreversedHost);
+  nsCOMPtr<mozIStorageFunction> func =
+    new mozStorageFunctionGetUnreversedHost;
+  NS_ENSURE_TRUE(func, NS_ERROR_OUT_OF_MEMORY);
+  nsresult rv = mDBConn->CreateFunction(
+    NS_LITERAL_CSTRING("get_unreversed_host"), 1, func
+  );
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = MatchAutoCompleteFunction::create(mDBConn);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 // nsNavHistory::InitStatements
 //
 //    Called after InitDB, this creates our stored statements
@@ -2141,72 +2080,16 @@ nsNavHistory::LoadPrefs(PRBool aInitiali
   mPrefBranch->GetIntPref(PREF_BROWSER_HISTORY_EXPIRE_DAYS_MIN, &mExpireDaysMin);
   // Cap max days to min days to prevent expiring pages younger than min
   // NOTE: if history is disabled in preferences, then mExpireDaysMax == 0
   if (mExpireDaysMax && mExpireDaysMax < mExpireDaysMin)
     mExpireDaysMax = mExpireDaysMin;
   if (NS_FAILED(mPrefBranch->GetIntPref(PREF_BROWSER_HISTORY_EXPIRE_SITES,
                                         &mExpireSites)))
     mExpireSites = EXPIRATION_CAP_SITES;
-  
-#ifdef MOZ_XUL
-  mPrefBranch->GetBoolPref(PREF_AUTOCOMPLETE_ENABLED, &mAutoCompleteEnabled);
-
-  PRInt32 matchBehavior = 1;
-  mPrefBranch->GetIntPref(PREF_AUTOCOMPLETE_MATCH_BEHAVIOR,
-                          &matchBehavior);
-  switch (matchBehavior) {
-    case 0:
-      mAutoCompleteMatchBehavior = MATCH_ANYWHERE;
-      break;
-    case 2:
-      mAutoCompleteMatchBehavior = MATCH_BOUNDARY;
-      break;
-    case 3:
-      mAutoCompleteMatchBehavior = MATCH_BEGINNING;
-      break;
-    case 1:
-    default:
-      mAutoCompleteMatchBehavior = MATCH_BOUNDARY_ANYWHERE;
-      break;
-  }
-
-  mPrefBranch->GetBoolPref(PREF_AUTOCOMPLETE_FILTER_JAVASCRIPT,
-                           &mAutoCompleteFilterJavascript);
-  mPrefBranch->GetIntPref(PREF_AUTOCOMPLETE_MAX_RICH_RESULTS,
-                          &mAutoCompleteMaxResults);
-  mPrefBranch->GetIntPref(PREF_AUTOCOMPLETE_SEARCH_CHUNK_SIZE,
-                          &mAutoCompleteSearchChunkSize);
-  mPrefBranch->GetIntPref(PREF_AUTOCOMPLETE_SEARCH_TIMEOUT,
-                          &mAutoCompleteSearchTimeout);
-  mPrefBranch->GetIntPref(PREF_AUTOCOMPLETE_DEFAULT_BEHAVIOR,
-                          &mAutoCompleteDefaultBehavior);
-  nsXPIDLCString prefStr;
-  mPrefBranch->GetCharPref(PREF_AUTOCOMPLETE_RESTRICT_HISTORY,
-                           getter_Copies(prefStr));
-  CopyUTF8toUTF16(prefStr, mAutoCompleteRestrictHistory);
-  mPrefBranch->GetCharPref(PREF_AUTOCOMPLETE_RESTRICT_BOOKMARK,
-                           getter_Copies(prefStr));
-  CopyUTF8toUTF16(prefStr, mAutoCompleteRestrictBookmark);
-  mPrefBranch->GetCharPref(PREF_AUTOCOMPLETE_RESTRICT_TAG,
-                           getter_Copies(prefStr));
-  CopyUTF8toUTF16(prefStr, mAutoCompleteRestrictTag);
-  mPrefBranch->GetCharPref(PREF_AUTOCOMPLETE_MATCH_TITLE,
-                           getter_Copies(prefStr));
-  CopyUTF8toUTF16(prefStr, mAutoCompleteMatchTitle);
-  mPrefBranch->GetCharPref(PREF_AUTOCOMPLETE_MATCH_URL,
-                           getter_Copies(prefStr));
-  CopyUTF8toUTF16(prefStr, mAutoCompleteMatchUrl);
-  mPrefBranch->GetCharPref(PREF_AUTOCOMPLETE_RESTRICT_TYPED,
-                           getter_Copies(prefStr));
-  CopyUTF8toUTF16(prefStr, mAutoCompleteRestrictTyped);
-
-  // Clear out the search on any pref change to invalidate cached search
-  mCurrentSearchString = EmptyString();
-#endif
 
   // get the frecency prefs
   nsCOMPtr<nsIPrefBranch> prefs(do_GetService("@mozilla.org/preferences-service;1"));
   if (prefs) {
     prefs->GetIntPref(PREF_FRECENCY_NUM_VISITS, 
       &mNumVisitsForFrecency);
     prefs->GetIntPref(PREF_FRECENCY_FIRST_BUCKET_CUTOFF, 
       &mFirstBucketCutoffInDays);
@@ -5652,20 +5535,16 @@ nsNavHistory::Observe(nsISupports *aSubj
 {
   NS_ASSERTION(NS_IsMainThread(), "This can only be called on the main thread");
 
   if (strcmp(aTopic, gQuitApplicationGrantedMessage) == 0) {
     if (mIdleTimer) {
       mIdleTimer->Cancel();
       mIdleTimer = nsnull;
     }
-    if (mAutoCompleteTimer) {
-      mAutoCompleteTimer->Cancel();
-      mAutoCompleteTimer = nsnull;
-    }
     nsresult rv;
     nsCOMPtr<nsIPrefService> prefService =
       do_GetService(NS_PREFSERVICE_CONTRACTID, &rv);
     if (NS_SUCCEEDED(rv))
       prefService->SavePrefFile(nsnull);
 
     // notify expiring system that we're quitting, it may want to do stuff
     mExpire.OnQuit();
@@ -5677,17 +5556,16 @@ nsNavHistory::Observe(nsISupports *aSubj
   }
   else if (strcmp(aTopic, gXpcomShutdown) == 0) {
     nsresult rv;
     nsCOMPtr<nsIObserverService> observerService =
       do_GetService("@mozilla.org/observer-service;1", &rv);
     NS_ENSURE_SUCCESS(rv, rv);
     observerService->RemoveObserver(this, NS_PRIVATE_BROWSING_SWITCH_TOPIC);
     observerService->RemoveObserver(this, gIdleDaily);
-    observerService->RemoveObserver(this, gAutoCompleteFeedback);
     observerService->RemoveObserver(this, gXpcomShutdown);
     observerService->RemoveObserver(this, gQuitApplicationGrantedMessage);
   }
 #ifdef MOZ_XUL
   else if (strcmp(aTopic, gAutoCompleteFeedback) == 0) {
     nsCOMPtr<nsIAutoCompleteInput> input = do_QueryInterface(aSubject);
     if (!input)
       return NS_OK;
@@ -7741,16 +7619,141 @@ nsNavHistory::FixInvalidFrecencies()
     rv = UpdateFrecencyInternal(placeId, typed, hidden, oldFrecency, isBook);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;
 }
 
 
+#ifdef MOZ_XUL
+
+namespace {
+
+// Used to notify a topic to system observers on async execute completion.
+class AutoCompleteStatementCallbackNotifier : public mozIStorageStatementCallback
+{
+public:
+  NS_DECL_ISUPPORTS
+  NS_DECL_MOZISTORAGESTATEMENTCALLBACK
+};
+
+NS_IMPL_ISUPPORTS1(AutoCompleteStatementCallbackNotifier,
+                   mozIStorageStatementCallback)
+
+NS_IMETHODIMP
+AutoCompleteStatementCallbackNotifier::HandleCompletion(PRUint16 aReason)
+{
+  if (aReason != mozIStorageStatementCallback::REASON_FINISHED)
+    return NS_ERROR_UNEXPECTED;
+
+  nsresult rv;
+  nsCOMPtr<nsIObserverService> observerService =
+    do_GetService("@mozilla.org/observer-service;1", &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = observerService->NotifyObservers(nsnull,
+                                        PLACES_AUTOCOMPLETE_FEEDBACK_UPDATED_TOPIC,
+                                        nsnull);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+NS_IMETHODIMP
+AutoCompleteStatementCallbackNotifier::HandleError(mozIStorageError *aError)
+{
+#ifdef DEBUG
+  PRInt32 result;
+  nsresult rv = aError->GetResult(&result);
+  NS_ENSURE_SUCCESS(rv, rv);
+  nsCAutoString message;
+  rv = aError->GetMessage(message);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCAutoString warnMsg;
+  warnMsg.Append("An error occured while executing an async statement: ");
+  warnMsg.Append(result);
+  warnMsg.Append(" ");
+  warnMsg.Append(message);
+  NS_WARNING(warnMsg.get());
+#endif
+
+  return NS_OK;
+}
+
+NS_IMETHODIMP
+AutoCompleteStatementCallbackNotifier::HandleResult(mozIStorageResultSet *aResultSet)
+{
+  NS_ASSERTION(PR_FALSE, "You cannot use AutoCompleteStatementCallbackNotifier to get async statements resultset");
+  return NS_OK;
+}
+
+} // anonymous namespace
+
+nsresult
+nsNavHistory::AutoCompleteFeedback(PRInt32 aIndex,
+                                   nsIAutoCompleteController *aController)
+{
+  // We do not track user choices in the location bar in private browsing mode.
+  if (InPrivateBrowsingMode())
+    return NS_OK;
+
+  mozIStorageStatement *stmt = GetDBFeedbackIncrease();
+  mozStorageStatementScoper scope(stmt);
+
+  nsAutoString input;
+  nsresult rv = aController->GetSearchString(input);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = stmt->BindStringParameter(0, input);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsAutoString url;
+  rv = aController->GetValueAt(aIndex, url);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = stmt->BindStringParameter(1, url);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // We do the update asynchronously and we do not care about failures.
+  nsCOMPtr<AutoCompleteStatementCallbackNotifier> callback =
+    new AutoCompleteStatementCallbackNotifier();
+  nsCOMPtr<mozIStoragePendingStatement> canceler;
+  rv = stmt->ExecuteAsync(callback, getter_AddRefs(canceler));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+mozIStorageStatement*
+nsNavHistory::GetDBFeedbackIncrease()
+{
+  if (mDBFeedbackIncrease)
+    return mDBFeedbackIncrease;
+
+  nsresult rv = mDBConn->CreateStatement(NS_LITERAL_CSTRING(
+    // Leverage the PRIMARY KEY (place_id, input) to insert/update entries.
+    "INSERT OR REPLACE INTO moz_inputhistory "
+      // use_count will asymptotically approach the max of 10.
+      "SELECT h.id, IFNULL(i.input, ?1), IFNULL(i.use_count, 0) * .9 + 1 "
+      "FROM moz_places_temp h "
+      "LEFT JOIN moz_inputhistory i ON i.place_id = h.id AND i.input = ?1 "
+      "WHERE url = ?2 "
+      "UNION ALL "
+      "SELECT h.id, IFNULL(i.input, ?1), IFNULL(i.use_count, 0) * .9 + 1 "
+      "FROM moz_places h "
+      "LEFT JOIN moz_inputhistory i ON i.place_id = h.id AND i.input = ?1 "
+      "WHERE url = ?2 "
+        "AND h.id NOT IN (SELECT id FROM moz_places_temp)"),
+    getter_AddRefs(mDBFeedbackIncrease));
+  NS_ENSURE_SUCCESS(rv, nsnull);
+
+  return mDBFeedbackIncrease;
+}
+#endif
+
+
 nsICollation *
 nsNavHistory::GetCollation()
 {
   if (mCollation)
     return mCollation;
 
   // locale
   nsCOMPtr<nsILocale> locale;
@@ -7896,16 +7899,19 @@ nsNavHistory::GetDBBookmarkToUrlResult()
   NS_ENSURE_SUCCESS(rv, nsnull);
 
   return mDBBookmarkToUrlResult;
 }
 
 nsresult
 nsNavHistory::FinalizeStatements() {
   mozIStorageStatement* stmts[] = {
+#ifdef MOZ_XUL
+    mDBFeedbackIncrease,
+#endif
     mDBGetURLPageInfo,
     mDBGetIdPageInfo,
     mDBRecentVisitOfURL,
     mDBRecentVisitOfPlace,
     mDBInsertVisit,
     mDBGetPageVisitStats,
     mDBIsPageVisited,
     mDBUpdatePageVisitStats,
@@ -7915,26 +7921,16 @@ nsNavHistory::FinalizeStatements() {
     mDBSetPlaceTitle,
     mDBVisitToURLResult,
     mDBVisitToVisitResult,
     mDBBookmarkToUrlResult,
     mDBVisitsForFrecency,
     mDBUpdateFrecencyAndHidden,
     mDBGetPlaceVisitStats,
     mDBFullVisitCount,
-    mDBCurrentQuery,
-    mDBAutoCompleteQuery,
-    mDBAutoCompleteTypedQuery,
-    mDBAutoCompleteHistoryQuery,
-    mDBAutoCompleteStarQuery,
-    mDBAutoCompleteTagsQuery,
-    mDBPreviousQuery,
-    mDBAdaptiveQuery,
-    mDBKeywordQuery,
-    mDBFeedbackIncrease
   };
 
   for (PRUint32 i = 0; i < NS_ARRAY_LENGTH(stmts); i++) {
     nsresult rv = nsNavHistory::FinalizeStatement(stmts[i]);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;
--- a/toolkit/components/places/src/nsNavHistory.h
+++ b/toolkit/components/places/src/nsNavHistory.h
@@ -47,24 +47,16 @@
 #include "mozIStorageStatement.h"
 #include "nsAutoPtr.h"
 #include "nsCOMArray.h"
 #include "nsCOMPtr.h"
 #include "nsDataHashtable.h"
 #include "nsINavHistoryService.h"
 #include "nsPIPlacesDatabase.h"
 #include "nsPIPlacesHistoryListenersNotifier.h"
-#ifdef MOZ_XUL
-#include "nsIAutoCompleteController.h"
-#include "nsIAutoCompleteInput.h"
-#include "nsIAutoCompletePopup.h"
-#include "nsIAutoCompleteSearch.h"
-#include "nsIAutoCompleteResult.h"
-#include "nsIAutoCompleteSimpleResult.h"
-#endif
 #include "nsIBrowserHistory.h"
 #include "nsICollation.h"
 #include "nsIGlobalHistory.h"
 #include "nsIGlobalHistory3.h"
 #include "nsIDownloadHistory.h"
 #include "nsIPrefService.h"
 #include "nsIPrefBranch.h"
 #include "nsIObserver.h"
@@ -104,63 +96,52 @@
 
 // This magic number specified an uninitialized value for the
 // mInPrivateBrowsing member
 #define PRIVATEBROWSING_NOTINITED (PRBool(0xffffffff))
 
 #define PLACES_INIT_COMPLETE_EVENT_TOPIC "places-init-complete"
 #define PLACES_DB_LOCKED_EVENT_TOPIC "places-database-locked"
 
-struct AutoCompleteIntermediateResult;
-class AutoCompleteResultComparator;
 class mozIAnnotationService;
 class nsNavHistory;
 class nsNavBookmarks;
 class QueryKeyValuePair;
 class nsIEffectiveTLDService;
 class nsIIDNService;
 class PlacesSQLQueryBuilder;
+class nsIAutoCompleteController;
 
 // nsNavHistory
 
 class nsNavHistory : public nsSupportsWeakReference
                    , public nsINavHistoryService
                    , public nsIObserver
                    , public nsIBrowserHistory
                    , public nsIGlobalHistory3
                    , public nsIDownloadHistory
                    , public nsICharsetResolver
                    , public nsPIPlacesDatabase
                    , public nsPIPlacesHistoryListenersNotifier
-#ifdef MOZ_XUL
-                   , public nsIAutoCompleteSearch
-                   , public nsIAutoCompleteSimpleResultListener
-#endif
 {
-  friend class AutoCompleteIntermediateResultSet;
-  friend class AutoCompleteResultComparator;
   friend class PlacesSQLQueryBuilder;
 
 public:
   nsNavHistory();
 
   NS_DECL_ISUPPORTS
 
   NS_DECL_NSINAVHISTORYSERVICE
   NS_DECL_NSIGLOBALHISTORY2
   NS_DECL_NSIGLOBALHISTORY3
   NS_DECL_NSIDOWNLOADHISTORY
   NS_DECL_NSIBROWSERHISTORY
   NS_DECL_NSIOBSERVER
   NS_DECL_NSPIPLACESDATABASE
   NS_DECL_NSPIPLACESHISTORYLISTENERSNOTIFIER
-#ifdef MOZ_XUL
-  NS_DECL_NSIAUTOCOMPLETESEARCH
-  NS_DECL_NSIAUTOCOMPLETESIMPLERESULTLISTENER
-#endif
 
 
   /**
    * Obtains the nsNavHistory object.
    */
   static nsNavHistory *GetSingleton();
 
   /**
@@ -653,134 +634,25 @@ protected:
       nsCStringHashKey::KeyType aKey, RedirectInfo& aData, void* aUserArg);
   PRBool GetRedirectFor(const nsACString& aDestination, nsACString& aSource,
                         PRTime* aTime, PRUint32* aRedirectType);
 
   // session tracking
   PRInt64 mLastSessionID;
   PRInt64 GetNewSessionID() { mLastSessionID ++; return mLastSessionID; }
 
-  //
+#ifdef MOZ_XUL
   // AutoComplete stuff
-  //
-  static const PRInt32 kAutoCompleteIndex_URL;
-  static const PRInt32 kAutoCompleteIndex_Title;
-  static const PRInt32 kAutoCompleteIndex_FaviconURL;
-  static const PRInt32 kAutoCompleteIndex_ParentId;
-  static const PRInt32 kAutoCompleteIndex_BookmarkTitle;
-  static const PRInt32 kAutoCompleteIndex_Tags;
-  static const PRInt32 kAutoCompleteIndex_VisitCount;
-  static const PRInt32 kAutoCompleteIndex_Typed;
-  nsCOMPtr<mozIStorageStatement> mDBCurrentQuery; //  kAutoCompleteIndex_* results
-  nsCOMPtr<mozIStorageStatement> mDBAutoCompleteQuery; //  kAutoCompleteIndex_* results
-  nsCOMPtr<mozIStorageStatement> mDBAutoCompleteTypedQuery; //  kAutoCompleteIndex_* results
-  mozIStorageStatement* GetDBAutoCompleteHistoryQuery();
-  nsCOMPtr<mozIStorageStatement> mDBAutoCompleteHistoryQuery; //  kAutoCompleteIndex_* results
-  mozIStorageStatement* GetDBAutoCompleteStarQuery();
-  nsCOMPtr<mozIStorageStatement> mDBAutoCompleteStarQuery; //  kAutoCompleteIndex_* results
-  mozIStorageStatement* GetDBAutoCompleteTagsQuery();
-  nsCOMPtr<mozIStorageStatement> mDBAutoCompleteTagsQuery; //  kAutoCompleteIndex_* results
-  nsCOMPtr<mozIStorageStatement> mDBPreviousQuery; //  kAutoCompleteIndex_* results
-  nsCOMPtr<mozIStorageStatement> mDBAdaptiveQuery; //  kAutoCompleteIndex_* results
-  nsCOMPtr<mozIStorageStatement> mDBKeywordQuery; //  kAutoCompleteIndex_* results
   mozIStorageStatement* GetDBFeedbackIncrease();
   nsCOMPtr<mozIStorageStatement> mDBFeedbackIncrease;
 
-  /**
-   * AutoComplete word matching behavior to determine if words should match on
-   * word boundaries or not or both.
-   */
-  enum MatchType {
-    MATCH_ANYWHERE,
-    MATCH_BOUNDARY_ANYWHERE,
-    MATCH_BOUNDARY,
-    MATCH_BEGINNING
-  };
-
-  nsresult InitAutoComplete();
-  nsresult CreateAutoCompleteQueries();
-  PRBool mAutoCompleteEnabled;
-  MatchType mAutoCompleteMatchBehavior;
-  PRBool mAutoCompleteFilterJavascript;
-  PRInt32 mAutoCompleteMaxResults;
-  nsString mAutoCompleteRestrictHistory;
-  nsString mAutoCompleteRestrictBookmark;
-  nsString mAutoCompleteRestrictTag;
-  nsString mAutoCompleteMatchTitle;
-  nsString mAutoCompleteMatchUrl;
-  nsString mAutoCompleteRestrictTyped;
-  PRInt32 mAutoCompleteSearchChunkSize;
-  PRInt32 mAutoCompleteSearchTimeout;
-  nsCOMPtr<nsITimer> mAutoCompleteTimer;
-
-  static const PRInt32 kAutoCompleteBehaviorHistory;
-  static const PRInt32 kAutoCompleteBehaviorBookmark;
-  static const PRInt32 kAutoCompleteBehaviorTag;
-  static const PRInt32 kAutoCompleteBehaviorTitle;
-  static const PRInt32 kAutoCompleteBehaviorUrl;
-  static const PRInt32 kAutoCompleteBehaviorTyped;
-
-  PRInt32 mAutoCompleteDefaultBehavior; // kAutoCompleteBehavior* bitmap
-  PRInt32 mAutoCompleteCurrentBehavior; // kAutoCompleteBehavior* bitmap
-
-  // Original search string for case-sensitive usage
-  nsString mOrigSearchString;
-  // Search string and tokens for case-insensitive matching
-  nsString mCurrentSearchString;
-  nsTArray<nsString> mCurrentSearchTokens;
-  void GenerateSearchTokens();
-  void AddSearchToken(nsAutoString &aToken);
-  void ProcessTokensForSpecialSearch();
-
-#ifdef MOZ_XUL
   nsresult AutoCompleteFeedback(PRInt32 aIndex,
                                 nsIAutoCompleteController *aController);
-
-  nsCOMPtr<nsIAutoCompleteObserver> mCurrentListener;
-  nsCOMPtr<nsIAutoCompleteSimpleResult> mCurrentResult;
 #endif
 
-  MatchType mCurrentMatchType;
-  MatchType mPreviousMatchType;
-  nsDataHashtable<nsStringHashKey, PRBool> mCurrentResultURLs;
-  PRInt32 mCurrentChunkOffset;
-  PRInt32 mPreviousChunkOffset;
-
-  nsDataHashtable<nsTrimInt64HashKey, PRBool> mLivemarkFeedItemIds;
-  nsDataHashtable<nsStringHashKey, PRBool> mLivemarkFeedURIs;
-
-  nsresult AutoCompleteFullHistorySearch(PRBool* aHasMoreResults);
-  nsresult AutoCompletePreviousSearch();
-  nsresult AutoCompleteAdaptiveSearch();
-  nsresult AutoCompleteKeywordSearch();
-
-  /**
-   * Query type passed to AutoCompleteProcessSearch to determine what style to
-   * use and if results should be filtered
-   */
-  enum QueryType {
-    QUERY_KEYWORD,
-    QUERY_FILTERED
-  };
-  nsresult AutoCompleteProcessSearch(mozIStorageStatement* aQuery,
-                                     const QueryType aType,
-                                     PRBool *aHasMoreResults = nsnull);
-  PRBool AutoCompleteHasEnoughResults();
-
-  nsresult PerformAutoComplete();
-  nsresult StartAutoCompleteTimer(PRUint32 aMilliseconds);
-  static void AutoCompleteTimerCallback(nsITimer* aTimer, void* aClosure);
-
-  PRBool mAutoCompleteFinishedSearch;
-  void DoneSearching(PRBool aFinished);
-
-  // Used to unescape encoded URI strings for searching
-  nsCOMPtr<nsITextToSubURI> mTextURIService;
-  nsString FixupURIText(const nsAString &aURIText);
-
   PRInt32 mExpireDaysMin;
   PRInt32 mExpireDaysMax;
   PRInt32 mExpireSites;
 
   // frecency prefs
   PRInt32 mNumVisitsForFrecency;
   PRInt32 mFirstBucketCutoffInDays;
   PRInt32 mSecondBucketCutoffInDays;
deleted file mode 100644
--- a/toolkit/components/places/src/nsNavHistoryAutoComplete.cpp
+++ /dev/null
@@ -1,1276 +0,0 @@
-/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
-/* ***** BEGIN LICENSE BLOCK *****
- * Version: MPL 1.1/GPL 2.0/LGPL 2.1
- *
- * The contents of this file are subject to the Mozilla Public License Version
- * 1.1 (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * Software distributed under the License is distributed on an "AS IS" basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Original Code is Places code.
- *
- * The Initial Developer of the Original Code is
- * Google Inc.
- * Portions created by the Initial Developer are Copyright (C) 2005
- * the Initial Developer. All Rights Reserved.
- *
- * Contributor(s):
- *   Brett Wilson <brettw@gmail.com>
- *   Joe Hewitt <hewitt@netscape.com>
- *   Blake Ross <blaker@netscape.com>
- *   Seth Spitzer <sspitzer@mozilla.org>
- *   Dietrich Ayala <dietrich@mozilla.com>
- *   Edward Lee <edward.lee@engineering.uiuc.edu>
- *   Ehsan Akhgari <ehsan.akhgari@gmail.com>
- *   Marco Bonardo <mak77@bonardo.net>
- *
- * Alternatively, the contents of this file may be used under the terms of
- * either the GNU General Public License Version 2 or later (the "GPL"), or
- * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
- * in which case the provisions of the GPL or the LGPL are applicable instead
- * of those above. If you wish to allow use of your version of this file only
- * under the terms of either the GPL or the LGPL, and not to allow others to
- * 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 ***** */
-
-
-/**
- * Autocomplete algorithm:
- *
- * Searches moz_places by frecency (in descending order)
- * in chunks (mAutoCompleteSearchChunkSize).  We currently
- * do SQL LIKE searches of the search term in the place title, place url
- * and bookmark titles (since a "place" can have multiple bookmarks)
- * within in each chunk. The results are ordered by frecency.
- * Note, we exclude places with no frecency (0) because 
- * frecency = 0 means "don't show this in autocomplete". place: queries should
- * have that, as should unvisited children of livemark feeds (that aren't
- * bookmarked elsewhere).
- *
- * But places with frecency < 0 are included, as that means that these items
- * have not had their frecency calculated yet (will happen on idle).
- */
-
-#include "nsNavHistory.h"
-#include "nsNetUtil.h"
-#include "nsEscape.h"
-#include "nsThreadUtils.h"
-
-#include "mozIStorageService.h"
-#include "mozIStorageConnection.h"
-#include "mozIStorageValueArray.h"
-#include "mozIStorageStatement.h"
-#include "mozIStorageFunction.h"
-#include "mozStorageCID.h"
-#include "mozStorageHelper.h"
-#include "nsFaviconService.h"
-#include "nsUnicharUtils.h"
-#include "nsNavBookmarks.h"
-#include "nsPrintfCString.h"
-#include "nsILivemarkService.h"
-#include "mozIStoragePendingStatement.h"
-#include "mozIStorageStatementCallback.h"
-#include "mozIStorageError.h"
-#include "nsPlacesTables.h"
-
-#define NS_AUTOCOMPLETESIMPLERESULT_CONTRACTID \
-  "@mozilla.org/autocomplete/simple-result;1"
-
-// Helpers to get and set fields in the mAutoCompleteCurrentBehavior bitmap
-#define GET_BEHAVIOR(aBitName) \
-  (mAutoCompleteCurrentBehavior & kAutoCompleteBehavior##aBitName)
-#define SET_BEHAVIOR(aBitName) \
-  mAutoCompleteCurrentBehavior |= kAutoCompleteBehavior##aBitName
-
-// Helper to get a particular column with a desired name from the bookmark and
-// tags table based on if we want to include tags or not. Make sure to provide
-// enough buffer space for printf.
-#define BOOK_TAG_FRAG(name, column, forTag) nsPrintfCString(200, ", (" \
-  "SELECT %s " \
-  "FROM moz_bookmarks b " \
-  "JOIN moz_bookmarks t ON t.id = b.parent AND t.parent %s= ?1 " \
-  "WHERE b.fk = h.id AND b.type = %d " \
-  "%s) AS %s", \
-  column, \
-  forTag ? "" : "!", \
-  nsINavBookmarksService::TYPE_BOOKMARK, \
-  forTag ? "AND LENGTH(t.title) > 0" : "ORDER BY b.lastModified DESC LIMIT 1", \
-  name)
-
-// Get three named columns from the bookmarks and tags table
-#define BOOK_TAG_SQL (\
-  BOOK_TAG_FRAG("parent", "b.parent", 0) + \
-  BOOK_TAG_FRAG("bookmark", "b.title", 0) + \
-  BOOK_TAG_FRAG("tags", "GROUP_CONCAT(t.title, ',')", 1))
-
-// This separator is used as an RTL-friendly way to split the title and tags.
-// It can also be used by an nsIAutoCompleteResult consumer to re-split the
-// "comment" back into the title and tag.
-// Use a Unichar array to avoid problems with 2-byte char strings: " \u2013 "
-const PRUnichar kTitleTagsSeparatorChars[] = { ' ', 0x2013, ' ', 0 };
-#define TITLE_TAGS_SEPARATOR nsAutoString(kTitleTagsSeparatorChars)
-
-// This fragment is used to get best favicon for a rev_host
-#define BEST_FAVICON_FOR_REVHOST( __table_name ) \
-  "(SELECT f.url FROM " __table_name " " \
-   "JOIN moz_favicons f ON f.id = favicon_id " \
-   "WHERE rev_host = IFNULL( " \
-     "(SELECT rev_host FROM moz_places_temp WHERE id = b.fk), " \
-     "(SELECT rev_host FROM moz_places WHERE id = b.fk)) " \
-   "ORDER BY frecency DESC LIMIT 1) "
-
-#define PLACES_AUTOCOMPLETE_FEEDBACK_UPDATED_TOPIC "places-autocomplete-feedback-updated"
-
-// Used to notify a topic to system observers on async execute completion.
-// Will throw on error.
-class AutoCompleteStatementCallbackNotifier : public mozIStorageStatementCallback
-{
-public:
-  NS_DECL_ISUPPORTS
-  NS_DECL_MOZISTORAGESTATEMENTCALLBACK
-};
-
-// AutocompleteStatementCallbackNotifier
-NS_IMPL_ISUPPORTS1(AutoCompleteStatementCallbackNotifier,
-                   mozIStorageStatementCallback)
-
-NS_IMETHODIMP
-AutoCompleteStatementCallbackNotifier::HandleCompletion(PRUint16 aReason)
-{
-  if (aReason != mozIStorageStatementCallback::REASON_FINISHED)
-    return NS_ERROR_UNEXPECTED;
-
-  nsresult rv;
-  nsCOMPtr<nsIObserverService> observerService =
-    do_GetService("@mozilla.org/observer-service;1", &rv);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = observerService->NotifyObservers(nsnull,
-                                        PLACES_AUTOCOMPLETE_FEEDBACK_UPDATED_TOPIC,
-                                        nsnull);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-NS_IMETHODIMP
-AutoCompleteStatementCallbackNotifier::HandleError(mozIStorageError *aError)
-{
-  PRInt32 result;
-  nsresult rv = aError->GetResult(&result);
-  NS_ENSURE_SUCCESS(rv, rv);
-  nsCAutoString message;
-  rv = aError->GetMessage(message);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  nsCAutoString warnMsg;
-  warnMsg.Append("An error occured while executing an async statement: ");
-  warnMsg.Append(result);
-  warnMsg.Append(" ");
-  warnMsg.Append(message);
-  NS_WARNING(warnMsg.get());
-
-  return NS_OK;
-}
-
-NS_IMETHODIMP
-AutoCompleteStatementCallbackNotifier::HandleResult(mozIStorageResultSet *aResultSet)
-{
-  NS_ASSERTION(PR_FALSE, "You cannot use AutoCompleteStatementCallbackNotifier to get async statements resultset");
-  return NS_OK;
-}
-
-void GetAutoCompleteBaseQuery(nsACString& aQuery) {
-// Define common pieces of various queries
-// XXX bug 412736
-// in the case of a frecency tie, break it with h.typed and h.visit_count
-// which is better than nothing.  but this is slow, so not doing it yet.
-
-// Try to reduce size of compound table since with partitioning this became
-// slower. Limiting moz_places with OFFSET+LIMIT will mostly help speed
-// of first chunks, that are usually most wanted.
-// Can do this only if there aren't additional conditions on final resultset.
-
-// Note: h.frecency is selected because we need it for ordering, but will
-// not be read later and we don't have an associated kAutoCompleteIndex_
-  aQuery = NS_LITERAL_CSTRING(
-      "SELECT h.url, h.title, f.url") + BOOK_TAG_SQL + NS_LITERAL_CSTRING(", "
-        "h.visit_count, h.typed "
-      "FROM ("
-        "SELECT " MOZ_PLACES_COLUMNS " FROM moz_places_temp "
-        "UNION ALL "
-        "SELECT " MOZ_PLACES_COLUMNS " FROM moz_places "
-        "WHERE +id NOT IN (SELECT id FROM moz_places_temp) "
-        "ORDER BY frecency DESC LIMIT ?2 OFFSET ?3) h "
-      "LEFT OUTER JOIN moz_favicons f ON f.id = h.favicon_id "
-      "WHERE h.frecency <> 0 "
-      "{ADDITIONAL_CONDITIONS}");
-}
-
-////////////////////////////////////////////////////////////////////////////////
-//// nsNavHistoryAutoComplete Helper Functions
-
-/**
- * Returns true if the string starts with javascript:
- */
-inline PRBool
-StartsWithJS(const nsAString &aString)
-{
-  return StringBeginsWith(aString, NS_LITERAL_STRING("javascript:"));
-}
-
-/**
- * Callback function for putting URLs from a nsDataHashtable<nsStringHashKey,
- * PRBool> into a nsTArray<nsString>.
- *
- * @param aKey
- *        The hashtable entry's key (the url)
- * @param aData
- *        Unused data
- * @param aArg
- *        The nsTArray<nsString> pointer for collecting URLs
- */
-PLDHashOperator
-HashedURLsToArray(const nsAString &aKey, PRBool aData, void *aArg)
-{
-  // Append the current url to the array of urls
-  static_cast<nsTArray<nsString> *>(aArg)->AppendElement(aKey);
-  return PL_DHASH_NEXT;
-}
-
-/**
- * Returns true if the unicode character is a word boundary. I.e., anything
- * that *isn't* used to build up a word from a string of characters. We are
- * conservative here because anything that we don't list will be treated as
- * word boundary. This means searching for that not-actually-a-word-boundary
- * character can still be matched in the middle of a word.
- */
-inline PRBool
-IsWordBoundary(const PRUnichar &aChar)
-{
-  // Lower-case alphabetic, so upper-case matches CamelCase. Because
-  // upper-case is treated as a word boundary, matches will also happen
-  // _after_ an upper-case character.
-  return !(PRUnichar('a') <= aChar && aChar <= PRUnichar('z'));
-}
-
-/**
- * Returns true if the token matches the target on a word boundary
- *
- * @param aToken
- *        Token to search for that must match on a word boundary
- * @param aTarget
- *        Target string to search against
- */
-PRBool
-FindOnBoundary(const nsAString &aToken, const nsAString &aTarget)
-{
-  // Define a const instance of this class so it is created once
-  const nsCaseInsensitiveStringComparator caseInsensitiveCompare;
-
-  // Can't match anything if there's nothing to match
-  if (aTarget.IsEmpty())
-    return PR_FALSE;
-
-  nsAString::const_iterator tokenStart, tokenEnd;
-  aToken.BeginReading(tokenStart);
-  aToken.EndReading(tokenEnd);
-
-  nsAString::const_iterator targetStart, targetEnd;
-  aTarget.BeginReading(targetStart);
-  aTarget.EndReading(targetEnd);
-
-  // Go straight into checking the token at the beginning of the target because
-  // the beginning is considered a word boundary
-  do {
-    // We're on a word boundary, so prepare to match by copying the iterators
-    nsAString::const_iterator testToken(tokenStart);
-    nsAString::const_iterator testTarget(targetStart);
-
-    // Keep trying to match the token one by one until it doesn't match
-    while (!caseInsensitiveCompare(*testToken, *testTarget)) {
-      // We matched something, so move down one
-      testToken++;
-      testTarget++;
-
-      // Matched the token! We're done!
-      if (testToken == tokenEnd)
-        return PR_TRUE;
-
-      // If we ran into the end while matching the token, we won't find it
-      if (testTarget == targetEnd)
-        return PR_FALSE;
-    }
-
-    // Unconditionally move past the current position in the target, but if
-    // we're not currently on a word boundary, eat up as many non-word boundary
-    // characters as possible -- don't kill characters if we're currently on a
-    // word boundary so that we can match tokens that start on a word boundary.
-    if (!IsWordBoundary(ToLowerCase(*targetStart++)))
-      while (targetStart != targetEnd && !IsWordBoundary(*targetStart))
-        targetStart++;
-
-    // If we hit the end eating up non-boundaries then boundaries, we're done
-  } while (targetStart != targetEnd);
-
-  return PR_FALSE;
-}
-
-/**
- * A local wrapper to CaseInsensitiveFindInReadable that isn't overloaded
- */
-inline PRBool
-FindAnywhere(const nsAString &aToken, const nsAString &aTarget)
-{
-  return CaseInsensitiveFindInReadable(aToken, aTarget);
-}
-
-/**
- * A local wrapper to case insensitive StringBeginsWith
- */
-inline PRBool
-FindBeginning(const nsAString &aToken, const nsAString &aTarget)
-{
-  return StringBeginsWith(aTarget, aToken, nsCaseInsensitiveStringComparator());
-}
-
-// nsNavHistory::InitAutoComplete
-nsresult
-nsNavHistory::InitAutoComplete()
-{
-  nsresult rv = CreateAutoCompleteQueries();
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  if (!mCurrentResultURLs.Init(128))
-    return NS_ERROR_OUT_OF_MEMORY;
-
-  if (!mLivemarkFeedItemIds.Init(128))
-    return NS_ERROR_OUT_OF_MEMORY;
-
-  if (!mLivemarkFeedURIs.Init(128))
-    return NS_ERROR_OUT_OF_MEMORY;
-
-  return NS_OK;
-}
-
-// nsNavHistory::GetDBAutoCompleteHistoryQuery()
-//
-//    Returns the auto complete statement used when autocomplete results are
-//    restricted to history entries.
-mozIStorageStatement*
-nsNavHistory::GetDBAutoCompleteHistoryQuery()
-{
-  if (mDBAutoCompleteHistoryQuery)
-    return mDBAutoCompleteHistoryQuery;
-
-  nsCString AutoCompleteHistoryQuery;
-  GetAutoCompleteBaseQuery(AutoCompleteHistoryQuery);
-  AutoCompleteHistoryQuery.ReplaceSubstring("{ADDITIONAL_CONDITIONS}",
-                                            "AND h.visit_count > 0");
-  nsresult rv = mDBConn->CreateStatement(AutoCompleteHistoryQuery,
-    getter_AddRefs(mDBAutoCompleteHistoryQuery));
-  NS_ENSURE_SUCCESS(rv, nsnull);
-
-  return mDBAutoCompleteHistoryQuery;
-}
-
-// nsNavHistory::GetDBAutoCompleteStarQuery()
-//
-//    Returns the auto complete statement used when autocomplete results are
-//    restricted to bookmarked entries.
-mozIStorageStatement*
-nsNavHistory::GetDBAutoCompleteStarQuery()
-{
-  if (mDBAutoCompleteStarQuery)
-    return mDBAutoCompleteStarQuery;
-
-  nsCString AutoCompleteStarQuery;
-  GetAutoCompleteBaseQuery(AutoCompleteStarQuery);
-  AutoCompleteStarQuery.ReplaceSubstring("{ADDITIONAL_CONDITIONS}",
-                                         "AND bookmark IS NOT NULL");
-  nsresult rv = mDBConn->CreateStatement(AutoCompleteStarQuery,
-    getter_AddRefs(mDBAutoCompleteStarQuery));
-  NS_ENSURE_SUCCESS(rv, nsnull);
-
-  return mDBAutoCompleteStarQuery;
-}
-
-// nsNavHistory::GetDBAutoCompleteTagsQuery()
-//
-//    Returns the auto complete statement used when autocomplete results are
-//    restricted to tagged entries.
-mozIStorageStatement*
-nsNavHistory::GetDBAutoCompleteTagsQuery()
-{
-  if (mDBAutoCompleteTagsQuery)
-    return mDBAutoCompleteTagsQuery;
-
-  nsCString AutoCompleteTagsQuery;
-  GetAutoCompleteBaseQuery(AutoCompleteTagsQuery);
-  AutoCompleteTagsQuery.ReplaceSubstring("{ADDITIONAL_CONDITIONS}",
-                                         "AND tags IS NOT NULL");
-  nsresult rv = mDBConn->CreateStatement(AutoCompleteTagsQuery,
-    getter_AddRefs(mDBAutoCompleteTagsQuery));
-  NS_ENSURE_SUCCESS(rv, nsnull);
-
-  return mDBAutoCompleteTagsQuery;
-}
-
-// nsNavHistory::GetDBFeedbackIncrease()
-//
-//    Returns the statement to update the input history that keeps track of
-//    selections in the locationbar.  Input history is used for adaptive query.
-mozIStorageStatement*
-nsNavHistory::GetDBFeedbackIncrease()
-{
-  if (mDBFeedbackIncrease)
-    return mDBFeedbackIncrease;
-
-  nsresult rv = mDBConn->CreateStatement(NS_LITERAL_CSTRING(
-    // Leverage the PRIMARY KEY (place_id, input) to insert/update entries
-    "INSERT OR REPLACE INTO moz_inputhistory "
-      // use_count will asymptotically approach the max of 10
-      "SELECT h.id, IFNULL(i.input, ?1), IFNULL(i.use_count, 0) * .9 + 1 "
-      "FROM moz_places_temp h "
-      "LEFT JOIN moz_inputhistory i ON i.place_id = h.id AND i.input = ?1 "
-      "WHERE url = ?2 "
-      "UNION ALL "
-      "SELECT h.id, IFNULL(i.input, ?1), IFNULL(i.use_count, 0) * .9 + 1 "
-      "FROM moz_places h "
-      "LEFT JOIN moz_inputhistory i ON i.place_id = h.id AND i.input = ?1 "
-      "WHERE url = ?2 "
-        "AND h.id NOT IN (SELECT id FROM moz_places_temp)"),
-    getter_AddRefs(mDBFeedbackIncrease));
-  NS_ENSURE_SUCCESS(rv, nsnull);
-
-  return mDBFeedbackIncrease;
-}
-
-// nsNavHistory::CreateAutoCompleteQueries
-//
-//    The auto complete queries we use depend on options, so we have them in
-//    a separate function so it can be re-created when the option changes.
-//    We are not lazy creating these queries because they will be most likely
-//    used on first search, and we don't want to lag on first autocomplete use.
-nsresult
-nsNavHistory::CreateAutoCompleteQueries()
-{
-  nsCString AutoCompleteQuery;
-  GetAutoCompleteBaseQuery(AutoCompleteQuery);
-  AutoCompleteQuery.ReplaceSubstring("{ADDITIONAL_CONDITIONS}", "");
-  nsresult rv = mDBConn->CreateStatement(AutoCompleteQuery,
-    getter_AddRefs(mDBAutoCompleteQuery));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  nsCString AutoCompleteTypedQuery;
-  GetAutoCompleteBaseQuery(AutoCompleteTypedQuery);
-  AutoCompleteTypedQuery.ReplaceSubstring("{ADDITIONAL_CONDITIONS}",
-                                          "AND h.typed = 1");
-  rv = mDBConn->CreateStatement(AutoCompleteTypedQuery,
-    getter_AddRefs(mDBAutoCompleteTypedQuery));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  // In this query we are taking BOOK_TAG_SQL only for h.id because it
-  // uses data from moz_bookmarks table and we sync tables on bookmark insert.
-  // So, most likely, h.id will always be populated when we have any bookmark.
-  // We still need to join on moz_places_temp for other data (eg. title).
-  nsCString sql = NS_LITERAL_CSTRING(
-    "/* do not warn (bug 487789) */ "
-    "SELECT IFNULL(h_t.url, h.url), IFNULL(h_t.title, h.title), f.url ") +
-      BOOK_TAG_SQL + NS_LITERAL_CSTRING(", "
-      "IFNULL(h_t.visit_count, h.visit_count), IFNULL(h_t.typed, h.typed), rank "
-    "FROM ( "
-      "SELECT ROUND(MAX(((i.input = ?2) + (SUBSTR(i.input, 1, LENGTH(?2)) = ?2)) * "
-        "i.use_count), 1) AS rank, place_id "
-      "FROM moz_inputhistory i "
-      "GROUP BY i.place_id HAVING rank > 0 "
-      ") AS i "
-    "LEFT JOIN moz_places h ON h.id = i.place_id "
-    "LEFT JOIN moz_places_temp h_t ON h_t.id = i.place_id "
-    "LEFT JOIN moz_favicons f ON f.id = IFNULL(h_t.favicon_id, h.favicon_id) "
-    "WHERE IFNULL(h_t.url, h.url) NOTNULL "
-    "ORDER BY rank DESC, IFNULL(h_t.frecency, h.frecency) DESC");
-  rv = mDBConn->CreateStatement(sql, getter_AddRefs(mDBAdaptiveQuery));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  sql = NS_LITERAL_CSTRING(
-    "/* do not warn (bug 487787) */ "
-    "SELECT IFNULL( "
-        "(SELECT REPLACE(url, '%s', ?2) FROM moz_places_temp WHERE id = b.fk), "
-        "(SELECT REPLACE(url, '%s', ?2) FROM moz_places WHERE id = b.fk) "
-      ") AS search_url, IFNULL(h_t.title, h.title), "
-      "COALESCE(f.url, "
-        BEST_FAVICON_FOR_REVHOST("moz_places_temp") ", "
-        BEST_FAVICON_FOR_REVHOST("moz_places")
-      "), "
-      "b.parent, b.title, NULL, IFNULL(h_t.visit_count, h.visit_count), "
-      "IFNULL(h_t.typed, h.typed) "
-    "FROM moz_keywords k "
-    "JOIN moz_bookmarks b ON b.keyword_id = k.id "
-    "LEFT JOIN moz_places AS h ON h.url = search_url "
-    "LEFT JOIN moz_places_temp AS h_t ON h_t.url = search_url "
-    "LEFT JOIN moz_favicons f ON f.id = IFNULL(h_t.favicon_id, h.favicon_id) "
-    "WHERE LOWER(k.keyword) = LOWER(?1) "
-    "ORDER BY IFNULL(h_t.frecency, h.frecency) DESC");
-  rv = mDBConn->CreateStatement(sql, getter_AddRefs(mDBKeywordQuery));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-// nsNavHistory::StartAutoCompleteTimer
-
-nsresult
-nsNavHistory::StartAutoCompleteTimer(PRUint32 aMilliseconds)
-{
-  nsresult rv;
-
-  if (!mAutoCompleteTimer) {
-    mAutoCompleteTimer = do_CreateInstance("@mozilla.org/timer;1", &rv);
-    NS_ENSURE_SUCCESS(rv, rv);
-  }
-  
-  rv = mAutoCompleteTimer->InitWithFuncCallback(AutoCompleteTimerCallback, this,
-                                                aMilliseconds,
-                                                nsITimer::TYPE_ONE_SHOT);
-  NS_ENSURE_SUCCESS(rv, rv);
-  return NS_OK;
-}
-
-// nsNavHistory::AutoCompleteTimerCallback
-
-void // static
-nsNavHistory::AutoCompleteTimerCallback(nsITimer* aTimer, void* aClosure)
-{
-  nsNavHistory* history = static_cast<nsNavHistory*>(aClosure);
-  (void)history->PerformAutoComplete();
-}
-
-nsresult 
-nsNavHistory::PerformAutoComplete()
-{
-  // if there is no listener, our search has been stopped
-  if (!mCurrentListener)
-    return NS_OK;
-
-  nsresult rv;
-  // Only do some extra searches on the first chunk
-  if (!mCurrentChunkOffset) {
-    // Only show keywords if there's a search
-    if (mCurrentSearchTokens.Length()) {
-      rv = AutoCompleteKeywordSearch();
-      NS_ENSURE_SUCCESS(rv, rv);
-    }
-
-    // Get adaptive results first
-    rv = AutoCompleteAdaptiveSearch();
-    NS_ENSURE_SUCCESS(rv, rv);
-  }
-
-  PRBool moreChunksToSearch = PR_FALSE;
-  // If we constructed a previous search query, use it instead of full
-  if (mDBPreviousQuery) {
-    rv = AutoCompletePreviousSearch();
-    NS_ENSURE_SUCCESS(rv, rv);
-
-    // We want to continue searching if we didn't finish last time, so move to
-    // one before the previous chunk so that we move up to the previous chunk
-    if (moreChunksToSearch = mPreviousChunkOffset != -1)
-      mCurrentChunkOffset = mPreviousChunkOffset - mAutoCompleteSearchChunkSize;
-  } else {
-    rv = AutoCompleteFullHistorySearch(&moreChunksToSearch);
-    NS_ENSURE_SUCCESS(rv, rv);
-  }
-
-  // If we ran out of pages to search, set offset to -1, so we can tell the
-  // difference between completing and stopping because we have enough results
-  PRBool notEnoughResults = !AutoCompleteHasEnoughResults();
-  if (!moreChunksToSearch) {
-    // But check first to see if we don't have enough results, and we're
-    // matching word boundaries, so try again without the match restriction
-    if (notEnoughResults && mCurrentMatchType == MATCH_BOUNDARY_ANYWHERE) {
-      mCurrentMatchType = MATCH_ANYWHERE;
-      mCurrentChunkOffset = -mAutoCompleteSearchChunkSize;
-      moreChunksToSearch = PR_TRUE;
-    } else {
-      mCurrentChunkOffset = -1;
-    }
-  } else {
-    // We know that we do have more chunks, so make sure we want more results
-    moreChunksToSearch = notEnoughResults;
-  }
-
-  // Determine the result of the search
-  PRUint32 count;
-  mCurrentResult->GetMatchCount(&count); 
-
-  if (count > 0) {
-    mCurrentResult->SetSearchResult(moreChunksToSearch ?
-      nsIAutoCompleteResult::RESULT_SUCCESS_ONGOING :
-      nsIAutoCompleteResult::RESULT_SUCCESS);
-    mCurrentResult->SetDefaultIndex(0);
-  } else {
-    mCurrentResult->SetSearchResult(moreChunksToSearch ?
-      nsIAutoCompleteResult::RESULT_NOMATCH_ONGOING :
-      nsIAutoCompleteResult::RESULT_NOMATCH);
-    mCurrentResult->SetDefaultIndex(-1);
-  }
-
-  rv = mCurrentResult->SetListener(this);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  mCurrentListener->OnSearchResult(this, mCurrentResult);
- 
-  // if we're not done searching, adjust our current offset
-  // and search the next chunk
-  if (moreChunksToSearch) {
-    mCurrentChunkOffset += mAutoCompleteSearchChunkSize;
-    rv = StartAutoCompleteTimer(mAutoCompleteSearchTimeout);
-    NS_ENSURE_SUCCESS(rv, rv);
-  } else {
-    DoneSearching(PR_TRUE);
-  }
-  return NS_OK;
-}
-
-void
-nsNavHistory::DoneSearching(PRBool aFinished)
-{
-  mPreviousMatchType = mCurrentMatchType;
-  mPreviousChunkOffset = mCurrentChunkOffset;
-  mAutoCompleteFinishedSearch = aFinished;
-  mCurrentResult = nsnull;
-  mCurrentListener = nsnull;
-}
-
-// nsNavHistory::StartSearch
-//
-
-NS_IMETHODIMP
-nsNavHistory::StartSearch(const nsAString & aSearchString,
-                          const nsAString & aSearchParam,
-                          nsIAutoCompleteResult *aPreviousResult,
-                          nsIAutoCompleteObserver *aListener)
-{
-  // We don't use aPreviousResult to get some matches from previous results in
-  // order to make sure ordering of results are consistent between reusing and
-  // not reusing results, see bug #412730 for details
-
-  NS_ENSURE_ARG_POINTER(aListener);
-  NS_ASSERTION(NS_IsMainThread(), "This can only be called on the main thread");
-
-  // Lazily init nsITextToSubURI service
-  if (!mTextURIService)
-    mTextURIService = do_GetService(NS_ITEXTTOSUBURI_CONTRACTID);
-
-  // Keep track of the previous search results to try optimizing
-  PRUint32 prevMatchCount = mCurrentResultURLs.Count();
-  nsAutoString prevSearchString(mCurrentSearchString);
-
-  // Keep a copy of the original search for case-sensitive usage
-  mOrigSearchString = aSearchString;
-  // Remove whitespace, see bug #392141 for details
-  mOrigSearchString.Trim(" \r\n\t\b");
-  // Copy the input search string for case-insensitive search
-  ToLowerCase(mOrigSearchString, mCurrentSearchString);
-
-  // Fix up the search the same way we fix up the entry url
-  mCurrentSearchString = FixupURIText(mCurrentSearchString);
-
-  mCurrentListener = aListener;
-
-  nsresult rv;
-  mCurrentResult = do_CreateInstance(NS_AUTOCOMPLETESIMPLERESULT_CONTRACTID, &rv);
-  NS_ENSURE_SUCCESS(rv, rv);
-  mCurrentResult->SetSearchString(aSearchString);
-
-  // Short circuit to give no results if we don't need to search for matches.
-  // Use the previous in-progress search by looking at which urls it found if
-  // the new search begins with the old one and both aren't empty. We don't run
-  // into bug 412730 because we only specify urls and not titles to look at.
-  // Also, only reuse the search if the previous and new search both start with
-  // javascript: or both don't. (bug 417798)
-  if (!mAutoCompleteEnabled ||
-      (!prevSearchString.IsEmpty() &&
-       StringBeginsWith(mCurrentSearchString, prevSearchString) &&
-       (StartsWithJS(prevSearchString) == StartsWithJS(mCurrentSearchString)))) {
-
-    // Got nothing before? We won't get anything new, so stop now
-    if (!mAutoCompleteEnabled ||
-        (mAutoCompleteFinishedSearch && prevMatchCount == 0)) {
-      // Set up the result to let the listener know that there's nothing
-      mCurrentResult->SetSearchResult(nsIAutoCompleteResult::RESULT_NOMATCH);
-      mCurrentResult->SetDefaultIndex(-1);
-
-      rv = mCurrentResult->SetListener(this);
-      NS_ENSURE_SUCCESS(rv, rv);
-
-      (void)mCurrentListener->OnSearchResult(this, mCurrentResult);
-      DoneSearching(PR_TRUE);
-
-      return NS_OK;
-    } else {
-      // We either have a previous in-progress search or a finished search that
-      // has more than 0 results. We can continue from where the previous
-      // search left off, but first we want to create an optimized query that
-      // only searches through the urls that were previously found
-
-      // We have to do the bindings for both tables, so we build a temporary
-      // string
-      nsCString bindings;
-      for (PRUint32 i = 0; i < prevMatchCount; i++) {
-        if (i)
-          bindings += NS_LITERAL_CSTRING(",");
-
-        // +2 to skip over the ?1 for the tag root parameter
-        bindings += nsPrintfCString("?%d", i + 2);
-      }
-
-      nsCString sql = NS_LITERAL_CSTRING(
-        "SELECT h.url, h.title, f.url") + BOOK_TAG_SQL + NS_LITERAL_CSTRING(", "
-          "h.visit_count, h.typed "
-        "FROM ( "
-          "SELECT " MOZ_PLACES_COLUMNS " FROM moz_places_temp "
-          "WHERE url IN (") + bindings + NS_LITERAL_CSTRING(") "
-          "UNION ALL "
-          "SELECT " MOZ_PLACES_COLUMNS " FROM moz_places "
-          "WHERE id NOT IN (SELECT id FROM moz_places_temp) "
-          "AND url IN (") + bindings + NS_LITERAL_CSTRING(") "
-        ") AS h "
-        "LEFT OUTER JOIN moz_favicons f ON f.id = h.favicon_id "
-        "ORDER BY h.frecency DESC");
-
-      rv = mDBConn->CreateStatement(sql, getter_AddRefs(mDBPreviousQuery));
-      NS_ENSURE_SUCCESS(rv, rv);
-
-      // Collect the previous result's URLs that we want to process
-      nsTArray<nsString> urls;
-      (void)mCurrentResultURLs.EnumerateRead(HashedURLsToArray, &urls);
-
-      // Bind the parameters right away. We can only use the query once.
-      for (PRUint32 i = 0; i < prevMatchCount; i++) {
-        rv = mDBPreviousQuery->BindStringParameter(i + 1, urls[i]);
-        NS_ENSURE_SUCCESS(rv, rv);
-      }
-
-      // Use the same match behavior as the previous search
-      mCurrentMatchType = mPreviousMatchType;
-    }
-  } else {
-    // Clear out any previous result queries
-    mDBPreviousQuery = nsnull;
-    // Default to matching based on the user's preference
-    mCurrentMatchType = mAutoCompleteMatchBehavior;
-  }
-
-  mAutoCompleteFinishedSearch = PR_FALSE;
-  mCurrentChunkOffset = 0;
-  mCurrentResultURLs.Clear();
-  mCurrentSearchTokens.Clear();
-  mLivemarkFeedItemIds.Clear();
-  mLivemarkFeedURIs.Clear();
-
-  // Make the array of search tokens from the search string
-  GenerateSearchTokens();
-
-  // Figure out if we need to do special searches
-  ProcessTokensForSpecialSearch();
-
-  // find all the items that have the "livemark/feedURI" annotation
-  // and save off their item ids and URIs. when doing autocomplete, 
-  // if a result's parent item id matches a saved item id, the result
-  // it is not really a bookmark, but a rss feed item.
-  // if a results URI matches a saved URI, the result is a bookmark,
-  // so we should show the star.
-  mozStorageStatementScoper scope(mFoldersWithAnnotationQuery);
-
-  rv = mFoldersWithAnnotationQuery->BindUTF8StringParameter(0, NS_LITERAL_CSTRING(LMANNO_FEEDURI));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  PRBool hasMore = PR_FALSE;
-  while (NS_SUCCEEDED(mFoldersWithAnnotationQuery->ExecuteStep(&hasMore)) && hasMore) {
-    PRInt64 itemId = 0;
-    rv = mFoldersWithAnnotationQuery->GetInt64(0, &itemId);
-    NS_ENSURE_SUCCESS(rv, rv);
-    mLivemarkFeedItemIds.Put(itemId, PR_TRUE);
-    nsAutoString feedURI;
-    // no need to worry about duplicates.
-    rv = mFoldersWithAnnotationQuery->GetString(1, feedURI);
-    NS_ENSURE_SUCCESS(rv, rv);
-    mLivemarkFeedURIs.Put(feedURI, PR_TRUE);
-  }
-
-  // fire right away, we already waited to start searching
-  rv = StartAutoCompleteTimer(0);
-  NS_ENSURE_SUCCESS(rv, rv);
-  return NS_OK;
-}
-
-// nsNavHistory::StopSearch
-
-NS_IMETHODIMP
-nsNavHistory::StopSearch()
-{
-  NS_ASSERTION(NS_IsMainThread(), "This can only be called on the main thread");
-
-  if (mAutoCompleteTimer)
-    mAutoCompleteTimer->Cancel();
-
-  DoneSearching(PR_FALSE);
-
-  return NS_OK;
-}
-
-void
-nsNavHistory::GenerateSearchTokens()
-{
-  // Split the search string into multiple search tokens
-  nsString::const_iterator strStart, strEnd;
-  mCurrentSearchString.BeginReading(strStart);
-  mCurrentSearchString.EndReading(strEnd);
-  nsString::const_iterator start = strStart, end = strEnd;
-  while (FindInReadable(NS_LITERAL_STRING(" "), start, end)) {
-    // Add in the current match
-    nsAutoString currentMatch(Substring(strStart, start));
-    AddSearchToken(currentMatch);
-
-    // Reposition iterators
-    strStart = start = end;
-    end = strEnd;
-  }
-  
-  // Add in the last match
-  nsAutoString lastMatch(Substring(strStart, strEnd));
-  AddSearchToken(lastMatch);
-} 
-
-inline void
-nsNavHistory::AddSearchToken(nsAutoString &aToken)
-{
-  aToken.Trim("\r\n\t\b");
-  if (!aToken.IsEmpty())
-    mCurrentSearchTokens.AppendElement(aToken);
-}
-
-void
-nsNavHistory::ProcessTokensForSpecialSearch()
-{
-  // Start with the default behavior
-  mAutoCompleteCurrentBehavior = mAutoCompleteDefaultBehavior;
-
-  // Determine which special searches to apply
-  for (PRInt32 i = PRInt32(mCurrentSearchTokens.Length()); --i >= 0;) {
-    PRBool needToRemove = PR_TRUE;
-    const nsString& token = mCurrentSearchTokens[i];
-
-    if (token.Equals(mAutoCompleteRestrictHistory))
-      SET_BEHAVIOR(History);
-    else if (token.Equals(mAutoCompleteRestrictBookmark))
-      SET_BEHAVIOR(Bookmark);
-    else if (token.Equals(mAutoCompleteRestrictTag))
-      SET_BEHAVIOR(Tag);
-    else if (token.Equals(mAutoCompleteMatchTitle))
-      SET_BEHAVIOR(Title);
-    else if (token.Equals(mAutoCompleteMatchUrl))
-      SET_BEHAVIOR(Url);
-    else if (token.Equals(mAutoCompleteRestrictTyped))
-      SET_BEHAVIOR(Typed);
-    else
-      needToRemove = PR_FALSE;
-
-    // Remove the token if it's special search token
-    if (needToRemove)
-      mCurrentSearchTokens.RemoveElementAt(i);
-  }
-
-  // Search only typed pages in history for empty searches
-  if (mOrigSearchString.IsEmpty()) {
-    SET_BEHAVIOR(History);
-    SET_BEHAVIOR(Typed);
-  }
-
-  // We can use optimized queries for restricts, so check for the most
-  // restrictive query first
-  mDBCurrentQuery = GET_BEHAVIOR(Tag) ? GetDBAutoCompleteTagsQuery() :
-    GET_BEHAVIOR(Bookmark) ? GetDBAutoCompleteStarQuery() :
-    GET_BEHAVIOR(Typed) ? static_cast<mozIStorageStatement *>(mDBAutoCompleteTypedQuery) :
-    GET_BEHAVIOR(History) ? GetDBAutoCompleteHistoryQuery() :
-    static_cast<mozIStorageStatement *>(mDBAutoCompleteQuery);
-}
-
-nsresult
-nsNavHistory::AutoCompleteKeywordSearch()
-{
-  mozStorageStatementScoper scope(mDBKeywordQuery);
-
-  // Get the keyword parameters to replace the %s in the keyword search
-  nsCAutoString params;
-  PRInt32 paramPos = mOrigSearchString.FindChar(' ') + 1;
-  // Make sure to escape them as if they were the query in a url, so " " become
-  // "+"; "+" become "%2B"; non-ascii escaped
-  NS_Escape(NS_ConvertUTF16toUTF8(Substring(mOrigSearchString, paramPos)),
-    params, url_XPAlphas);
-
-  // The first search term might be a keyword
-  const nsAString &keyword = Substring(mOrigSearchString, 0,
-    paramPos ? paramPos - 1 : mOrigSearchString.Length());
-  nsresult rv = mDBKeywordQuery->BindStringParameter(0, keyword);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = mDBKeywordQuery->BindUTF8StringParameter(1, params);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = AutoCompleteProcessSearch(mDBKeywordQuery, QUERY_KEYWORD);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-nsresult
-nsNavHistory::AutoCompleteAdaptiveSearch()
-{
-  mozStorageStatementScoper scope(mDBAdaptiveQuery);
-
-  nsresult rv = mDBAdaptiveQuery->BindInt64Parameter(0, GetTagsFolder());
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = mDBAdaptiveQuery->BindStringParameter(1, mCurrentSearchString);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = AutoCompleteProcessSearch(mDBAdaptiveQuery, QUERY_FILTERED);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-nsresult
-nsNavHistory::AutoCompletePreviousSearch()
-{
-  nsresult rv = mDBPreviousQuery->BindInt64Parameter(0, GetTagsFolder());
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = AutoCompleteProcessSearch(mDBPreviousQuery, QUERY_FILTERED);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  // Don't use this query more than once
-  mDBPreviousQuery = nsnull;
-
-  return NS_OK;
-}
-
-// nsNavHistory::AutoCompleteFullHistorySearch
-//
-// Search for places that have a title, url, 
-// or bookmark title(s) that contains mCurrentSearchString
-// and are within our current chunk of "frecency".
-//
-// @param aHasMoreResults is false if the query found no matching items
-//
-
-nsresult
-nsNavHistory::AutoCompleteFullHistorySearch(PRBool* aHasMoreResults)
-{
-  mozStorageStatementScoper scope(mDBCurrentQuery);
-
-  nsresult rv = mDBCurrentQuery->BindInt64Parameter(0, GetTagsFolder());
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = mDBCurrentQuery->BindInt32Parameter(1, mAutoCompleteSearchChunkSize);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = mDBCurrentQuery->BindInt32Parameter(2, mCurrentChunkOffset);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = AutoCompleteProcessSearch(mDBCurrentQuery, QUERY_FILTERED, aHasMoreResults);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-nsresult
-nsNavHistory::AutoCompleteProcessSearch(mozIStorageStatement* aQuery,
-                                        const QueryType aType,
-                                        PRBool *aHasMoreResults)
-{
-  // Unless we're checking if there are any results for the query, don't bother
-  // processing results if we already have enough results
-  if (!aHasMoreResults && AutoCompleteHasEnoughResults())
-    return NS_OK;
-
-  nsFaviconService* faviconService = nsFaviconService::GetFaviconService();
-  NS_ENSURE_TRUE(faviconService, NS_ERROR_OUT_OF_MEMORY);
-
-  // We want to filter javascript: URIs if the search doesn't start with it
-  PRBool filterJavascript = mAutoCompleteFilterJavascript &&
-    !StartsWithJS(mCurrentSearchString);
-
-  // Determine what type of search to try matching tokens against targets
-  PRBool (*tokenMatchesTarget)(const nsAString &, const nsAString &);
-  switch (mCurrentMatchType) {
-    case MATCH_ANYWHERE:
-      tokenMatchesTarget = FindAnywhere;
-      break;
-    case MATCH_BEGINNING:
-      tokenMatchesTarget = FindBeginning;
-      break;
-    case MATCH_BOUNDARY_ANYWHERE:
-    case MATCH_BOUNDARY:
-    default:
-      tokenMatchesTarget = FindOnBoundary;
-      break;
-  }
-
-  PRBool hasMore = PR_FALSE;
-  // Determine the result of the search
-  while (NS_SUCCEEDED(aQuery->ExecuteStep(&hasMore)) && hasMore) {
-    nsAutoString escapedEntryURL;
-    nsresult rv = aQuery->GetString(kAutoCompleteIndex_URL, escapedEntryURL);
-    NS_ENSURE_SUCCESS(rv, rv);
-
-    // If we need to filter and have a javascript URI.. skip!
-    if (filterJavascript && StartsWithJS(escapedEntryURL))
-      continue;
-
-    // Prevent duplicates that might appear from previous searches such as tag
-    // results and chunking. Because we use mCurrentResultURLs to remove
-    // duplicates, the first url wins, so we might not show it as a "star" if
-    // the parentId we get first is the one for the livemark and not the
-    // bookmark or no "star" at all.
-    // XXX bug 412734
-    PRBool dummy;
-    if (!mCurrentResultURLs.Get(escapedEntryURL, &dummy)) {
-      PRInt64 parentId = 0;
-      nsAutoString entryTitle, entryFavicon, entryBookmarkTitle;
-      rv = aQuery->GetString(kAutoCompleteIndex_Title, entryTitle);
-      NS_ENSURE_SUCCESS(rv, rv);
-      rv = aQuery->GetString(kAutoCompleteIndex_FaviconURL, entryFavicon);
-      NS_ENSURE_SUCCESS(rv, rv);
-      rv = aQuery->GetInt64(kAutoCompleteIndex_ParentId, &parentId);
-      NS_ENSURE_SUCCESS(rv, rv);
-      
-      // Only fetch the bookmark title if we have a bookmark
-      if (parentId) {
-        rv = aQuery->GetString(kAutoCompleteIndex_BookmarkTitle, entryBookmarkTitle);
-        NS_ENSURE_SUCCESS(rv, rv);
-      }
-
-      nsAutoString entryTags;
-      rv = aQuery->GetString(kAutoCompleteIndex_Tags, entryTags);
-      NS_ENSURE_SUCCESS(rv, rv);
-      PRInt32 visitCount = 0;
-      rv = aQuery->GetInt32(kAutoCompleteIndex_VisitCount, &visitCount);
-      NS_ENSURE_SUCCESS(rv, rv);
-      PRInt32 typed = 0;
-      rv = aQuery->GetInt32(kAutoCompleteIndex_Typed, &typed);
-
-      // Always prefer the bookmark title unless it's empty
-      nsAutoString title =
-        entryBookmarkTitle.IsEmpty() ? entryTitle : entryBookmarkTitle;
-
-      nsString style;
-      switch (aType) {
-        case QUERY_KEYWORD: {
-          // If we don't have a title, then we must have a keyword, so let the
-          // UI know it's a keyword; otherwise, we found an exact page match,
-          // so just show the page like a regular result
-          if (entryTitle.IsEmpty())
-            style = NS_LITERAL_STRING("keyword");
-          else
-            title = entryTitle;
-
-          break;
-        }
-        case QUERY_FILTERED: {
-          // If we get any results, there's potentially another chunk to proces
-          if (aHasMoreResults)
-            *aHasMoreResults = PR_TRUE;
-
-          // Keep track of if we've matched all the filter requirements such as
-          // only history items, only bookmarks, only tags. If a given restrict
-          // is active, make sure a corresponding condition is *not* true. If
-          // any are violated, matchAll will be false.
-          PRBool matchAll = !((GET_BEHAVIOR(History) && visitCount == 0) ||
-                              (GET_BEHAVIOR(Typed) && typed == 0) ||
-                              (GET_BEHAVIOR(Bookmark) && !parentId) ||
-                              (GET_BEHAVIOR(Tag) && entryTags.IsEmpty()));
-
-          // Unescape the url to search for unescaped terms
-          nsString entryURL = FixupURIText(escapedEntryURL);
-
-          // Determine if every token matches either the bookmark title, tags,
-          // page title, or page url
-          for (PRUint32 i = 0; i < mCurrentSearchTokens.Length() && matchAll; i++) {
-            const nsString& token = mCurrentSearchTokens[i];
-
-            // Check if the tags match the search term
-            PRBool matchTags = (*tokenMatchesTarget)(token, entryTags);
-            // Check if the title matches the search term
-            PRBool matchTitle = (*tokenMatchesTarget)(token, title);
-
-            // Make sure we match something in the title or tags if we have to
-            matchAll = matchTags || matchTitle;
-            if (GET_BEHAVIOR(Title) && !matchAll)
-              break;
-
-            // Check if the url matches the search term
-            PRBool matchUrl = (*tokenMatchesTarget)(token, entryURL);
-            // If we don't match the url when we have to, reset matchAll to
-            // false; otherwise keep track that we did match the current search
-            if (GET_BEHAVIOR(Url) && !matchUrl)
-              matchAll = PR_FALSE;
-            else
-              matchAll |= matchUrl;
-          }
-
-          // Skip if we don't match all terms in the bookmark, tag, title or url
-          if (!matchAll)
-            continue;
-
-          break;
-        }
-      }
-
-      // Always prefer to show tags if we have them
-      PRBool showTags = !entryTags.IsEmpty();
-
-      // Pretend a page isn't bookmarked/tagged if the user only wants history,
-      // but still show the star and tag if the user explicitly wants them
-      if (GET_BEHAVIOR(History) && !(GET_BEHAVIOR(Bookmark) || GET_BEHAVIOR(Tag))) {
-        showTags = PR_FALSE;
-        style = NS_LITERAL_STRING("favicon");
-      }
-
-      // Add the tags to the title if necessary
-      if (showTags)
-        title += TITLE_TAGS_SEPARATOR + entryTags;
-
-      // Tags have a special style to show a tag icon; otherwise, style the
-      // bookmarks that aren't feed items and feed URIs as bookmark
-      if (style.IsEmpty()) {
-        if (showTags)
-          style = NS_LITERAL_STRING("tag");
-        else if ((parentId && !mLivemarkFeedItemIds.Get(parentId, &dummy)) ||
-                 mLivemarkFeedURIs.Get(escapedEntryURL, &dummy))
-          style = NS_LITERAL_STRING("bookmark");
-        else
-          style = NS_LITERAL_STRING("favicon");
-      }
-
-      // Get the URI for the favicon
-      nsCAutoString faviconSpec;
-      faviconService->GetFaviconSpecForIconString(
-        NS_ConvertUTF16toUTF8(entryFavicon), faviconSpec);
-      NS_ConvertUTF8toUTF16 faviconURI(faviconSpec);
-
-      // New item: append to our results and put it in our hash table
-      rv = mCurrentResult->AppendMatch(escapedEntryURL, title, faviconURI, style);
-      NS_ENSURE_SUCCESS(rv, rv);
-      mCurrentResultURLs.Put(escapedEntryURL, PR_TRUE);
-
-      // Stop processing if we have enough results
-      if (AutoCompleteHasEnoughResults())
-        break;
-    }
-  }
-
-  return NS_OK;
-}
-
-inline PRBool
-nsNavHistory::AutoCompleteHasEnoughResults()
-{
-  return mCurrentResultURLs.Count() >= (PRUint32)mAutoCompleteMaxResults;
-}
-
-// nsNavHistory::OnValueRemoved (nsIAutoCompleteSimpleResultListener)
-
-NS_IMETHODIMP
-nsNavHistory::OnValueRemoved(nsIAutoCompleteSimpleResult* aResult,
-                             const nsAString& aValue, PRBool aRemoveFromDb)
-{
-  NS_ASSERTION(NS_IsMainThread(), "This can only be called on the main thread");
-
-  if (!aRemoveFromDb)
-    return NS_OK;
-
-  nsresult rv;
-  nsCOMPtr<nsIURI> uri;
-  rv = NS_NewURI(getter_AddRefs(uri), aValue);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = RemovePage(uri);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-nsresult
-nsNavHistory::AutoCompleteFeedback(PRInt32 aIndex,
-                                   nsIAutoCompleteController *aController)
-{
-  // we don't track user choices in the awesomebar in private browsing mode
-  if (InPrivateBrowsingMode())
-    return NS_OK;
-
-  mozIStorageStatement *stmt = GetDBFeedbackIncrease();
-  mozStorageStatementScoper scope(stmt);
-
-  nsAutoString input;
-  nsresult rv = aController->GetSearchString(input);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindStringParameter(0, input);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  nsAutoString url;
-  rv = aController->GetValueAt(aIndex, url);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindStringParameter(1, url);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  // We do the update async and we don't care about failures
-  nsCOMPtr<AutoCompleteStatementCallbackNotifier> callback =
-    new AutoCompleteStatementCallbackNotifier();
-  nsCOMPtr<mozIStoragePendingStatement> canceler;
-  rv = stmt->ExecuteAsync(callback, getter_AddRefs(canceler));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-nsString
-nsNavHistory::FixupURIText(const nsAString &aURIText)
-{
-  // Unescaping utilities expect UTF8 strings
-  NS_ConvertUTF16toUTF8 escaped(aURIText);
-
-  // Strip off some prefixes so we don't have to match the exact protocol for
-  // sites. E.g., http://mozilla.org/ can match other mozilla.org pages.
-  if (StringBeginsWith(escaped, NS_LITERAL_CSTRING("https://")))
-    escaped.Cut(0, 8);
-  else if (StringBeginsWith(escaped, NS_LITERAL_CSTRING("http://")))
-    escaped.Cut(0, 7);
-  else if (StringBeginsWith(escaped, NS_LITERAL_CSTRING("ftp://")))
-    escaped.Cut(0, 6);
-
-  nsString fixedUp;
-  // Use the service if we have it to avoid invalid UTF8 strings
-  if (mTextURIService) {
-    mTextURIService->UnEscapeURIForUI(NS_LITERAL_CSTRING("UTF-8"),
-      escaped, fixedUp);
-    return fixedUp;
-  }
-
-  // Fallback on using this if the service is unavailable for some reason
-  NS_UnescapeURL(escaped);
-  CopyUTF8toUTF16(escaped, fixedUp);
-  return fixedUp;
-}
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/src/nsPlacesAutoComplete.js
@@ -0,0 +1,1056 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: sw=2 ts=2 sts=2 expandtab
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2008
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Shawn Wilsher <me@shawnwilsher.com> (Original Author)
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * 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 ***** */
+
+Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
+
+////////////////////////////////////////////////////////////////////////////////
+//// Constants
+
+const Cc = Components.classes;
+const Ci = Components.interfaces;
+const Cr = Components.results;
+
+// This is just a helper for the next constant.
+function book_tag_sql_fragment(aName, aColumn, aForTag)
+{
+  return ["(",
+    "SELECT ", aColumn, " ",
+    "FROM moz_bookmarks b ",
+    "JOIN moz_bookmarks t ",
+      "ON t.id = b.parent ",
+      "AND t.parent ", (aForTag ? "" : "!"), "= :parent ",
+    "WHERE b.type = ", Ci.nsINavBookmarksService.TYPE_BOOKMARK, " ",
+      "AND b.fk = h.id ",
+    (aForTag ? "AND LENGTH(t.title) > 0" :
+               "ORDER BY b.lastModified DESC LIMIT 1"),
+  ") AS ", aName].join("");
+}
+
+// This SQL query fragment provides the following:
+//   - the parent folder for bookmarked entries (kQueryIndexParent)
+//   - the bookmark title, if it is a bookmark (kQueryIndexBookmarkTitle)
+//   - the tags associated with a bookmarked entry (kQueryIndexTags)
+const kBookTagSQLFragment =
+  book_tag_sql_fragment("parent", "b.parent", false) + ", " +
+  book_tag_sql_fragment("bookmark", "b.title", false) + ", " +
+  book_tag_sql_fragment("tags", "GROUP_CONCAT(t.title, ',')", true);
+
+// observer topics
+const kQuitApplication = "quit-application";
+const kPrefChanged = "nsPref:changed";
+
+// Match type constants.  These indicate what type of search function we should
+// be using.
+const MATCH_ANYWHERE = Ci.mozIPlacesAutoComplete.MATCH_ANYWHERE;
+const MATCH_BOUNDARY_ANYWHERE = Ci.mozIPlacesAutoComplete.MATCH_BOUNDARY_ANYWHERE;
+const MATCH_BOUNDARY = Ci.mozIPlacesAutoComplete.MATCH_BOUNDARY;
+const MATCH_BEGINNING = Ci.mozIPlacesAutoComplete.MATCH_BEGINNING;
+
+// AutoComplete index constants.  All AutoComplete queries will provide these
+// columns in this order.
+const kQueryIndexURL = 0;
+const kQueryIndexTitle = 1;
+const kQueryIndexFaviconURL = 2;
+const kQueryIndexParentId = 3;
+const kQueryIndexBookmarkTitle = 4;
+const kQueryIndexTags = 5;
+const kQueryIndexVisitCount = 6;
+const kQueryIndexTyped = 7;
+const kQueryIndexPlaceId = 8;
+const kQueryIndexQueryType = 9;
+
+// AutoComplete query type constants.  Describes the various types of queries
+// that we can process.
+const kQueryTypeKeyword = 0;
+const kQueryTypeFiltered = 1;
+
+// This separator is used as an RTL-friendly way to split the title and tags.
+// It can also be used by an nsIAutoCompleteResult consumer to re-split the
+// "comment" back into the title and the tag.
+const kTitleTagsSeparator = " \u2013 ";
+
+// The list of columns in the moz_places table that we use in our queries.
+const kMozPlacesColumns =
+  "id, url, title, rev_host, visit_count, hidden, typed, favicon_id, " +
+  "frecency, last_visit_date"
+
+const kBrowserUrlbarBranch = "browser.urlbar.";
+
+////////////////////////////////////////////////////////////////////////////////
+//// Global Functions
+
+/**
+ * Generates the SQL subquery to get the best favicon for a given revhost.  This
+ * is the favicon for the most recent visit.
+ *
+ * @param aTableName
+ *        The table to join to the moz_favicons table with.  This must have a
+ *        column called favicon_id.
+ * @return the SQL subquery (in string form) to get the best favicon.
+ */
+function best_favicon_for_revhost(aTableName)
+{
+  return "(" +
+    "SELECT f.url " +
+    "FROM " + aTableName + " " +
+    "JOIN moz_favicons f ON f.id = favicon_id " +
+    "WHERE rev_host = IFNULL( " +
+      "(SELECT rev_host FROM moz_places_temp WHERE id = b.fk), " +
+      "(SELECT rev_host FROM moz_places WHERE id = b.fk) " +
+    ") " +
+    "ORDER BY frecency DESC " +
+    "LIMIT 1 " +
+  ")";
+}
+
+////////////////////////////////////////////////////////////////////////////////
+//// AutoCompleteStatementCallbackWrapper class
+
+/**
+ * Wraps a callback and ensures that handleCompletion is not dispatched if the
+ * query is no longer tracked.
+ *
+ * @param aCallback
+ *        A reference to a nsPlacesAutoComplete.
+ */
+function AutoCompleteStatementCallbackWrapper(aCallback)
+{
+  this._callback = aCallback;
+}
+
+AutoCompleteStatementCallbackWrapper.prototype = {
+  //////////////////////////////////////////////////////////////////////////////
+  //// mozIStorageStatementCallback
+
+  handleResult: function ACSCW_handleResult(aResultSet)
+  {
+    this._callback.handleResult.apply(this._callback, arguments);
+  },
+
+  handleError: function ACSCW_handleError(aError)
+  {
+    this._callback.handleError.apply(this._callback, arguments);
+  },
+
+  handleCompletion: function ACSCW_handleCompletion(aReason)
+  {
+    // Only dispatch handleCompletion if we are not done searching and are a
+    // pending search.
+    let callback = this._callback;
+    if (!callback.isSearchComplete() && callback.isPendingSearch(this._handle))
+      callback.handleCompletion.apply(callback, arguments);
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// AutoCompleteStatementCallbackWrapper
+
+  /**
+   * Executes the specified query asynchronously.  This object will notify
+   * this._callback if we should notify (logic explained in handleCompletion).
+   *
+   * @param aQuery
+   *        The query to execute asynchronously.
+   * @return a mozIStoragePendingStatement that can be used to cancel the query.
+   */
+  executeAsync: function ACSCW_executeAsync(aQuery)
+  {
+    return this._handle = aQuery.executeAsync(this);
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// nsISupports
+
+  QueryInterface: XPCOMUtils.generateQI([
+    Ci.mozIStorageStatementCallback,
+  ])
+};
+
+////////////////////////////////////////////////////////////////////////////////
+//// nsPlacesAutoComplete class
+
+function nsPlacesAutoComplete()
+{
+  //////////////////////////////////////////////////////////////////////////////
+  //// Shared Constants for Smart Getters
+
+  // Define common pieces of various queries.
+  // TODO bug 412736 in case of a frecency tie, break it with h.typed and
+  // h.visit_count which is better than nothing.  This is slow, so not doing it
+  // yet...
+  // Note: h.frecency is only selected because we need it for ordering.
+  const SQL_BASE =
+    "SELECT h.url, h.title, f.url, " + kBookTagSQLFragment + ", h.visit_count, " +
+           "h.typed, h.id, :query_type " +
+    "FROM ( " +
+      "SELECT " + kMozPlacesColumns + " FROM moz_places_temp " +
+      "UNION ALL " +
+      "SELECT " + kMozPlacesColumns + " FROM moz_places " +
+      "WHERE +id NOT IN (SELECT id FROM moz_places_temp) " +
+      "ORDER BY frecency DESC " +
+    ") AS h " +
+    "LEFT OUTER JOIN moz_favicons f " +
+    "ON f.id = h.favicon_id " +
+    "WHERE h.frecency <> 0 " +
+    "AND AUTOCOMPLETE_MATCH(:searchString, h.url, IFNULL(bookmark, h.title), " +
+                           "tags, h.visit_count, h.typed, parent, " +
+                           ":matchBehavior, :searchBehavior) " +
+    "{ADDITIONAL_CONDITIONS}";
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// Smart Getters
+
+  this.__defineGetter__("_db", function() {
+    delete this._db;
+    return this._db = Cc["@mozilla.org/browser/nav-history-service;1"].
+                      getService(Ci.nsPIPlacesDatabase).
+                      DBConnection;
+  });
+
+  this.__defineGetter__("_bh", function() {
+    delete this._bh;
+    return this._bh = Cc["@mozilla.org/browser/global-history;2"].
+                      getService(Ci.nsIBrowserHistory);
+  });
+
+  this.__defineGetter__("_textURIService", function() {
+    delete this._textURIService;
+    return this._textURIService = Cc["@mozilla.org/intl/texttosuburi;1"].
+                                  getService(Ci.nsITextToSubURI);
+  });
+
+  this.__defineGetter__("_bs", function() {
+    delete this._bs;
+    return this._bs = Cc["@mozilla.org/browser/nav-bookmarks-service;1"].
+                      getService(Ci.nsINavBookmarksService);
+  });
+
+  this.__defineGetter__("_ioService", function() {
+    delete this._ioService;
+    return this._ioService = Cc["@mozilla.org/network/io-service;1"].
+                             getService(Ci.nsIIOService);
+  });
+
+  this.__defineGetter__("_faviconService", function() {
+    delete this._faviconService;
+    return this._faviconService = Cc["@mozilla.org/browser/favicon-service;1"].
+                                  getService(Ci.nsIFaviconService);
+  });
+
+  this.__defineGetter__("_defaultQuery", function() {
+    delete this._defaultQuery;
+    let replacementText = "";
+    return this._defaultQuery = this._db.createStatement(
+      SQL_BASE.replace("{ADDITIONAL_CONDITIONS}", replacementText, "g")
+    );
+  });
+
+  this.__defineGetter__("_historyQuery", function() {
+    delete this._historyQuery;
+    let replacementText = "AND h.visit_count > 0";
+    return this._historyQuery = this._db.createStatement(
+      SQL_BASE.replace("{ADDITIONAL_CONDITIONS}", replacementText, "g")
+    );
+  });
+
+  this.__defineGetter__("_bookmarkQuery", function() {
+    delete this._bookmarkQuery;
+    let replacementText = "AND bookmark IS NOT NULL";
+    return this._bookmarkQuery = this._db.createStatement(
+      SQL_BASE.replace("{ADDITIONAL_CONDITIONS}", replacementText, "g")
+    );
+  });
+
+  this.__defineGetter__("_tagsQuery", function() {
+    delete this._tagsQuery;
+    let replacementText = "AND tags IS NOT NULL";
+    return this._tagsQuery = this._db.createStatement(
+      SQL_BASE.replace("{ADDITIONAL_CONDITIONS}", replacementText, "g")
+    );
+  });
+
+  this.__defineGetter__("_typedQuery", function() {
+    delete this._typedQuery;
+    let replacementText = "AND h.typed = 1";
+    return this._typedQuery = this._db.createStatement(
+      SQL_BASE.replace("{ADDITIONAL_CONDITIONS}", replacementText, "g")
+    );
+  });
+
+  this.__defineGetter__("_adaptiveQuery", function() {
+    delete this._adaptiveQuery;
+    // In this query, we are taking kBookTagSQLFragment only for h.id because it
+    // uses data from the moz_bookmarks table and we sync tables on bookmark
+    // insert.  So, most likely, h.id will always be populated when we have any
+    // bookmark.  We still need to join on moz_places_temp for other data (eg.
+    // title).
+    return this._adaptiveQuery = this._db.createStatement(
+      "/* do not warn (bug 487789) */ " +
+      "SELECT IFNULL(h_t.url, h.url), IFNULL(h_t.title, h.title), f.url, " +
+              kBookTagSQLFragment + ", IFNULL(h_t.visit_count, h.visit_count), " +
+              "IFNULL(h_t.typed, h.typed), IFNULL(h_t.id, h.id), " +
+              ":query_type, rank " +
+      "FROM ( " +
+        "SELECT ROUND(MAX(((i.input = :search_string) + " +
+                          "(SUBSTR(i.input, 1, LENGTH(:search_string)) = :search_string)) * " +
+                          "i.use_count), 1) AS rank, place_id " +
+        "FROM moz_inputhistory i " +
+        "GROUP BY i.place_id " +
+        "HAVING rank > 0 " +
+      ") AS i " +
+      "LEFT JOIN moz_places h ON h.id = i.place_id " +
+      "LEFT JOIN moz_places_temp h_t ON h_t.id = i.place_id " +
+      "LEFT JOIN moz_favicons f ON f.id = IFNULL(h_t.favicon_id, h.favicon_id) "+
+      "WHERE IFNULL(h_t.url, h.url) NOTNULL " +
+      "ORDER BY rank DESC, IFNULL(h_t.frecency, h.frecency) DESC"
+    );
+  });
+
+  this.__defineGetter__("_keywordQuery", function() {
+    delete this._keywordQuery;
+    return this._keywordQuery = this._db.createStatement(
+      "/* do not warn (bug 487787) */ " +
+      "SELECT IFNULL( " +
+          "(SELECT REPLACE(url, '%s', :query_string) FROM moz_places_temp WHERE id = b.fk), " +
+          "(SELECT REPLACE(url, '%s', :query_string) FROM moz_places WHERE id = b.fk) " +
+        ") AS search_url, IFNULL(h_t.title, h.title), " +
+        "COALESCE(f.url, " + best_favicon_for_revhost("moz_places_temp") + "," +
+                  best_favicon_for_revhost("moz_places") + "), b.parent, " +
+        "b.title, NULL, IFNULL(h_t.visit_count, h.visit_count), " +
+        "IFNULL(h_t.typed, h.typed), COALESCE(h_t.id, h.id, b.fk), " +
+        ":query_type " +
+      "FROM moz_keywords k " +
+      "JOIN moz_bookmarks b ON b.keyword_id = k.id " +
+      "LEFT JOIN moz_places AS h ON h.url = search_url " +
+      "LEFT JOIN moz_places_temp AS h_t ON h_t.url = search_url " +
+      "LEFT JOIN moz_favicons f ON f.id = IFNULL(h_t.favicon_id, h.favicon_id) " +
+      "WHERE LOWER(k.keyword) = LOWER(:keyword) " +
+      "ORDER BY IFNULL(h_t.frecency, h.frecency) DESC"
+    );
+  });
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// Initialization
+
+  // load preferences
+  this._loadPrefs(true);
+
+  // register observers
+  this._os = Cc["@mozilla.org/observer-service;1"].
+              getService(Ci.nsIObserverService);
+  this._os.addObserver(this, kQuitApplication, false);
+
+}
+
+nsPlacesAutoComplete.prototype = {
+  //////////////////////////////////////////////////////////////////////////////
+  //// nsIAutoCompleteSearch
+
+  startSearch: function PAC_startSearch(aSearchString, aSearchParam,
+                                        aPreviousResult, aListener)
+  {
+    // Note: We don't use aPreviousResult to make sure ordering of results are
+    //       consistent.  See bug 412730 for more details.
+
+    // We want to store the original string with no leading or trailing
+    // whitespace for case sensitive searches.
+    this._originalSearchString = aSearchString.trim();
+
+    this._currentSearchString =
+      this._fixupSearchText(this._originalSearchString.toLowerCase());
+
+    this._listener = aListener;
+    let result = Cc["@mozilla.org/autocomplete/simple-result;1"].
+                 createInstance(Ci.nsIAutoCompleteSimpleResult);
+    result.setSearchString(aSearchString);
+    result.setListener(this);
+    this._result = result;
+    this._notifyResults(true);
+
+    // If we are not enabled, we need to return now.
+    if (!this._enabled) {
+      this._finishSearch(true);
+      return;
+    }
+
+    // Reset our search behavior to the default.
+    this._behavior = this._defaultBehavior;
+
+    // If we have no search terms, this is a special search that should only
+    // look for BEHAVIOR_HISTORY and BEHAVIOR_TYPED.
+    if (!this._currentSearchString) {
+      this._setBehavior("history");
+      this._setBehavior("typed");
+    }
+
+    // For any given search, we run up to three queries:
+    // 1) keywords (this._keywordQuery)
+    // 2) adaptive learning (this._adaptiveQuery)
+    // 3) query from this._getSearch
+    // We always run (2) and (3), but (1) only gets ran if we get any filtered
+    // tokens from this._getSearch (if there are no tokens, there is nothing to
+    // match, so there is no reason to run the query).
+    let {query, tokens} =
+      this._getSearch(this._getUnfilteredSearchTokens(this._currentSearchString));
+    let queries = tokens.length ?
+      [this._getBoundKeywordQuery(tokens), this._getBoundAdaptiveQuery(), query] :
+      [this._getBoundAdaptiveQuery(), query];
+
+    // Start executing our queries.
+    this._executeQueries(queries);
+
+    // Set up our persistent state for the duration of the search.
+    this._searchTokens = tokens;
+    this._usedPlaceIds = {};
+  },
+
+  stopSearch: function PAC_stopSearch()
+  {
+    // We need to cancel our searches so we do not get any [more] results.
+    this._stopActiveQueries();
+
+    this._finishSearch(false);
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// nsIAutoCompleteSimpleResultListener
+
+  onValueRemoved: function PAC_onValueRemoved(aResult, aURISpec, aRemoveFromDB)
+  {
+    if (aRemoveFromDB)
+      this._bh.removePage(this._ioService.newURI(aURISpec, null, null));
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// mozIStorageStatementCallback
+
+  handleResult: function PAC_handleResult(aResultSet)
+  {
+    let row, haveMatches = false;
+    while (row = aResultSet.getNextRow()) {
+      let match = this._processRow(row);
+      haveMatches = haveMatches || match;
+
+      if (this._result.matchCount == this._maxRichResults) {
+        // We have enough results, so stop running our queries.
+        this._stopActiveQueries();
+
+        // And finish our search.
+        this._finishSearch(true);
+        return;
+      }
+
+    }
+
+    // Notify about results if we've gotten them.
+    if (haveMatches)
+      this._notifyResults(true);
+  },
+
+  handleError: function PAC_handleError(aError)
+  {
+    Components.utils.reportError("Places AutoComplete: " + aError);
+  },
+
+  handleCompletion: function PAC_handleCompletion(aReason)
+  {
+    // If we have already finished our search, we should bail out early.
+    if (this.isSearchComplete())
+      return;
+
+    // Remove the first query in our array of pending queries since it is the
+    // one we are getting notified about.
+    this._pendingQueries.shift();
+
+    // If we still have pending queries, we bail out because we aren't done
+    // getting results.
+    if (this._pendingQueries.length)
+      return;
+
+    // If we do not have enough results, and our match type is
+    // MATCH_BOUNDARY_ANYWHERE, search again with MATCH_ANYWHERE to get more
+    // results.
+    if (this._matchBehavior == MATCH_BOUNDARY_ANYWHERE &&
+        this._result.matchCount < this._maxRichResults && !this._secondPass) {
+      this._secondPass = true;
+      let query = this._getBoundSearchQuery(MATCH_ANYWHERE, this._searchTokens);
+      this._executeQueries([query]);
+      return;
+    }
+
+    this._finishSearch(true);
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// nsIObserver
+
+  observe: function PAC_observe(aSubject, aTopic, aData)
+  {
+    if (aTopic == kQuitApplication) {
+      this._os.removeObserver(this, kQuitApplication);
+
+      // Remove our preference observer.
+      let prefs = Cc["@mozilla.org/preferences-service;1"].
+                  getService(Ci.nsIPrefService).
+                  getBranch(kBrowserUrlbarBranch).
+                  QueryInterface(Ci.nsIPrefBranch2);
+      prefs.removeObserver("", this);
+
+      // Finalize the statements that we have used.
+      let stmts = [
+        "_defaultQuery",
+        "_historyQuery",
+        "_bookmarkQuery",
+        "_tagsQuery",
+        "_typedQuery",
+        "_adaptiveQuery",
+        "_keywordQuery",
+      ];
+      for (let i = 0; i < stmts.length; i++) {
+        // We do not want to create any query we haven't already created, so
+        // see if it is a getter first.  __lookupGetter__ returns null if it is
+        // actually a statement.
+        if (!this.__lookupGetter__(stmts[i]))
+          this[stmts[i]].finalize();
+      }
+    }
+    else if (aTopic == kPrefChanged) {
+      this._loadPrefs();
+    }
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// nsPlacesAutoComplete
+
+  /**
+   * Used to unescape encoded URI strings, and drop information that we do not
+   * care about for searching.
+   *
+   * @param aURIString
+   *        The text to unescape and modify.
+   * @return the modified uri.
+   */
+  _fixupSearchText: function PAC_fixupSearchText(aURIString)
+  {
+    let uri = aURIString;
+
+    if (uri.indexOf("http://") == 0)
+      uri = uri.slice(7);
+    else if (uri.indexOf("https://") == 0)
+      uri = uri.slice(8);
+    else if (uri.indexOf("ftp://") == 0)
+      uri = uri.slice(6);
+
+    return this._textURIService.unEscapeURIForUI("UTF-8", uri);
+  },
+
+  /**
+   * Generates the tokens used in searching from a given string.
+   *
+   * @param aSearchString
+   *        The string to generate tokens from.
+   * @return an array of tokens.
+   */
+  _getUnfilteredSearchTokens: function PAC_unfilteredSearchTokens(aSearchString)
+  {
+    // Calling split on an empty string will return an array containing one
+    // empty string.  We don't want that, as it'll break our logic, so return an
+    // empty array then.
+    return aSearchString.length ? aSearchString.split(" ") : [];
+  },
+
+  /**
+   * Properly cleans up when searching is completed.
+   *
+   * @param aNotify
+   *        Indicates if we should notify the AutoComplete listener about our
+   *        results or not.
+   */
+  _finishSearch: function PAC_finishSearch(aNotify)
+  {
+    // Notify about results if we are supposed to.
+    if (aNotify)
+      this._notifyResults(false);
+
+    // Clear our state
+    delete this._originalSearchString;
+    delete this._currentSearchString;
+    delete this._searchTokens;
+    delete this._listener;
+    delete this._result;
+    delete this._usedPlaceIds;
+    this._secondPass = false;
+  },
+
+  /**
+   * Executes the given queries asynchronously.
+   *
+   * @param aQueries
+   *        The queries to execute.
+   */
+  _executeQueries: function PAC_executeQueries(aQueries)
+  {
+    // Because we might get a handleCompletion for canceled queries, we want to
+    // filter out queries we no longer care about (described in the
+    // handleCompletion implementation of AutoCompleteStatementCallbackWrapper).
+    let PAC = this;
+    this._pendingQueries = aQueries.map(function(aQuery) {
+      // Create our wrapper object and execute the query.
+      let callbackWrapper = new AutoCompleteStatementCallbackWrapper(PAC);
+      return callbackWrapper.executeAsync(aQuery);
+    });
+  },
+
+  /**
+   * Stops executing all active queries.
+   */
+  _stopActiveQueries: function PAC_stopActiveQueries()
+  {
+    this._pendingQueries.forEach(function(aQuery) aQuery.cancel());
+    delete this._pendingQueries;
+  },
+
+  /**
+   * Notifies the listener about results.
+   *
+   * @param aSearchOngoing
+   *        Indicates if the search is ongoing or not.
+   */
+  _notifyResults: function PAC_notifyResults(aSearchOngoing)
+  {
+    let result = this._result;
+    let resultCode = result.matchCount ? "RESULT_SUCCESS" : "RESULT_NOMATCH";
+    if (aSearchOngoing)
+      resultCode += "_ONGOING";
+    result.setSearchResult(Ci.nsIAutoCompleteResult[resultCode]);
+    result.setDefaultIndex(result.matchCount ? 0 : -1);
+    this._listener.onSearchResult(this, result);
+  },
+
+  /**
+   * Loads the preferences that we care about.
+   *
+   * @param [optional] aRegisterObserver
+   *        Indicates if the preference observer should be added or not.  The
+   *        default value is false.
+   */
+  _loadPrefs: function PAC_loadPrefs(aRegisterObserver)
+  {
+    let prefs = Cc["@mozilla.org/preferences-service;1"].
+                getService(Ci.nsIPrefService).
+                getBranch(kBrowserUrlbarBranch);
+    function safeGetter(aName, aDefault) {
+      let types = {
+        boolean: "Bool",
+        number: "Int",
+        string: "Char"
+      };
+      let type = types[typeof(aDefault)];
+      if (!type)
+        throw "Unknown type!";
+
+      // If the pref isn't set, we want to use the default.
+      try {
+        return prefs["get" + type + "Pref"](aName);
+      }
+      catch (e) {
+        return aDefault;
+      }
+    }
+
+    this._enabled = safeGetter("autocomplete.enabled", true);
+    this._matchBehavior = safeGetter("matchBehavior", MATCH_BOUNDARY_ANYWHERE);
+    this._filterJavaScript = safeGetter("filter.javascript", true);
+    this._maxRichResults = safeGetter("maxRichResults", 25);
+    this._restrictHistoryToken = safeGetter("restrict.history", "^");
+    this._restrictBookmarkToken = safeGetter("restrict.bookmark", "*");
+    this._restrictTypedToken = safeGetter("restrict.typed", "~");
+    this._restrictTagToken = safeGetter("restrct.tag", "+");
+    this._matchTitleToken = safeGetter("match.title", "#");
+    this._matchURLToken = safeGetter("match.url", "@");
+    this._defaultBehavior = safeGetter("default.behavior", 0);
+
+    // Validate matchBehavior; default to MATCH_BOUNDARY_ANYWHERE.
+    if (this._matchBehavior != MATCH_ANYWHERE &&
+        this._matchBehavior != MATCH_BOUNDARY &&
+        this._matchBehavior != MATCH_BEGINNING)
+      this._matchBehavior = MATCH_BOUNDARY_ANYWHERE;
+
+    // register observer
+    if (aRegisterObserver) {
+      let pb = prefs.QueryInterface(Ci.nsIPrefBranch2);
+      pb.addObserver("", this, false);
+    }
+  },
+
+  /**
+   * Given an array of tokens, this function determines which query should be
+   * ran.  It also removes any special search tokens.
+   *
+   * @param aTokens
+   *        An array of search tokens.
+   * @return an object with two properties:
+   *         query: the correctly optimized, bound query to search the database
+   *                with.
+   *         tokens: the filtered list of tokens to search with.
+   */
+  _getSearch: function PAC_getSearch(aTokens)
+  {
+    // Set the proper behavior so our call to _getBoundSearchQuery gives us the
+    // correct query.
+    for (let i = aTokens.length - 1; i >= 0; i--) {
+      switch (aTokens[i]) {
+        case this._restrictHistoryToken:
+          this._setBehavior("history");
+          break;
+        case this._restrictBookmarkToken:
+          this._setBehavior("bookmark");
+          break;
+        case this._restrictTagToken:
+          this._setBehavior("tag");
+          break;
+        case this._matchTitleToken:
+          this._setBehavior("title");
+          break;
+        case this._matchURLToken:
+          this._setBehavior("url");
+          break;
+        case this._restrictTypedToken:
+          this._setBehavior("typed");
+          break;
+        default:
+          // We do not want to remove the token if we did not match.
+          continue;
+      };
+
+      aTokens.splice(i, 1);
+    }
+
+    // Set the right JavaScript behavior based on our preference.  Note that the
+    // preference is whether or not we should filter JavaScript, and the
+    // behavior is if we should search it or not.
+    if (!this._filterJavaScript)
+      this._setBehavior("javascript");
+
+    return {
+      query: this._getBoundSearchQuery(this._matchBehavior, aTokens),
+      tokens: aTokens
+    };
+  },
+
+  /**
+   * Obtains the search query to be used based on the previously set search
+   * behaviors (accessed by this._hasBehavior).  The query is bound and ready to
+   * execute.
+   *
+   * @param aMatchBehavior
+   *        How this query should match its tokens to the search string.
+   * @param aTokens
+   *        An array of search tokens.
+   * @return the correctly optimized query to search the database with and the
+   *         new list of tokens to search with.  The query has all the needed
+   *         parameters bound, so consumers can execute it without doing any
+   *         additional work.
+   */
+  _getBoundSearchQuery: function PAC_getBoundSearchQuery(aMatchBehavior,
+                                                         aTokens)
+  {
+    // We use more optimized queries for restricted searches, so we will always
+    // return the most restrictive one to the least restrictive one if more than
+    // one token is found.
+    let query = this._hasBehavior("tag") ? this._tagsQuery :
+                this._hasBehavior("bookmark") ? this._bookmarkQuery :
+                this._hasBehavior("typed") ? this._typedQuery :
+                this._hasBehavior("history") ? this._historyQuery :
+                this._defaultQuery;
+
+    // Bind the needed parameters to the query so consumers can use it.
+    let (params = query.params) {
+      params.parent = this._bs.tagsFolder;
+      params.query_type = kQueryTypeFiltered;
+      params.matchBehavior = aMatchBehavior;
+      params.searchBehavior = this._behavior;
+
+      // We only want to search the tokens that we are left with - not the
+      // original search string.
+      params.searchString = aTokens.join(" ");
+    }
+
+    return query;
+  },
+
+  /**
+   * Obtains the keyword query with the properly bound parameters.
+   *
+   * @param aTokens
+   *        The array of search tokens to check against.
+   * @return the bound keyword query.
+   */
+  _getBoundKeywordQuery: function PAC_getBoundKeywordQuery(aTokens)
+  {
+    // The keyword is the first word in the search string, with the parameters
+    // following it.
+    let searchString = this._originalSearchString;
+    let queryString = searchString.substring(searchString.indexOf(" ") + 1);
+
+    // We need to escape the parameters as if they were the query in a URL
+    queryString = encodeURIComponent(queryString).replace("%20", "+", "g");
+
+    // The first word could be a keyword, so that's what we'll search.
+    let keyword = aTokens[0];
+
+    let query = this._keywordQuery;
+    let (params = query.params) {
+      params.keyword = keyword;
+      params.query_string = queryString;
+      params.query_type = kQueryTypeKeyword;
+    }
+
+    return query;
+  },
+
+  /**
+   * Obtains the adaptive query with the properly bound parameters.
+   *
+   * @return the bound adaptive query.
+   */
+  _getBoundAdaptiveQuery: function PAC_getBoundAdaptiveQuery()
+  {
+    let query = this._adaptiveQuery;
+    let (params = query.params) {
+      params.parent = this._bs.tagsFolder;
+      params.search_string = this._currentSearchString;
+      params.query_type = kQueryTypeFiltered;
+    }
+
+    return query;
+  },
+
+  /**
+   * Processes a mozIStorageRow to generate the proper data for the AutoComplete
+   * result.  This will add an entry to the current result if it matches the
+   * criteria.
+   *
+   * @param aRow
+   *        The row to process.
+   * @return true if the row is accepted, and false if not.
+   */
+  _processRow: function PAC_processRow(aRow)
+  {
+    // Before we do any work, make sure this entry isn't already in our results.
+    let entryId = aRow.getResultByIndex(kQueryIndexPlaceId);
+    if (this._inResults(entryId))
+      return false;
+
+    let escapedEntryURL = aRow.getResultByIndex(kQueryIndexURL);
+    let entryTitle = aRow.getResultByIndex(kQueryIndexTitle) || "";
+    let entryFavicon = aRow.getResultByIndex(kQueryIndexFaviconURL) || "";
+    let entryParentId = aRow.getResultByIndex(kQueryIndexParentId);
+    let entryBookmarkTitle = entryParentId ?
+      aRow.getResultByIndex(kQueryIndexBookmarkTitle) : null;
+    let entryTags = aRow.getResultByIndex(kQueryIndexTags) || "";
+
+    // Always prefer the bookmark title unless it is empty
+    let title = entryBookmarkTitle || entryTitle;
+
+    let style;
+    if (aRow.getResultByIndex(kQueryIndexQueryType) == kQueryTypeKeyword) {
+      // If we do not have a title, then we must have a keyword, so let the UI
+      // know it is a keyword.  Otherwise, we found an exact page match, so just
+      // show the page like a regular result.  Because the page title is likely
+      // going to be more specific than the bookmark title (keyword title).
+      if (!entryTitle)
+        style = "keyword";
+      else
+        title = entryTitle;
+    }
+
+    // We will always prefer to show tags if we have them.
+    let showTags = !!entryTags;
+
+    // However, we'll act as if a page is not bookmarked or tagged if the user
+    // only wants only history and not bookmarks or tags.
+    if (this._hasBehavior("history") &&
+        !(this._hasBehavior("bookmark") || this._hasBehavior("tag"))) {
+      showTags = false;
+      style = "favicon";
+    }
+
+    // If we have tags and should show them, we need to add them to the title.
+    if (showTags)
+      title += kTitleTagsSeparator + entryTags;
+
+    // We have to determine the right style to display.  Tags show the tag icon,
+    // bookmarks get the bookmark icon, and keywords get the keyword icon.  If
+    // the result does not fall into any of those, it just gets the favicon.
+    if (!style) {
+      // It is possible that we already have a style set (from a keyword
+      // search), so only set it if we haven't already done so.
+      if (showTags)
+        style = "tag";
+      else if (entryParentId)
+        style = "bookmark";
+      else
+        style = "favicon";
+    }
+
+    // And finally add this to our results.
+    this._addToResults(entryId, escapedEntryURL, title, entryFavicon, style);
+    return true;
+  },
+
+  /**
+   * Checks to see if the given place has already been added to the results.
+   *
+   * @param aPlaceId
+   *        The place_id to check for.
+   * @return true if the place has been added, false otherwise.
+   */
+  _inResults: function PAC_inResults(aPlaceId)
+  {
+    return (aPlaceId in this._usedPlaceIds);
+  },
+
+  /**
+   * Adds a result to the AutoComplete results.  Also tracks that we've added
+   * this place_id into the result set.
+   *
+   * @param aPlaceId
+   *        The place_id of the item to be added to the result set.  This is
+   *        used by _inResults.
+   * @param aURISpec
+   *        The URI spec for the entry.
+   * @param aTitle
+   *        The title to give the entry.
+   * @param aFaviconSpec
+   *        The favicon to give to the entry.
+   * @param aStyle
+   *        Indicates how the entry should be styled when displayed.
+   */
+  _addToResults: function PAC_addToResults(aPlaceId, aURISpec, aTitle,
+                                           aFaviconSpec, aStyle)
+  {
+    // Add this to our internal tracker to ensure duplicates do not end up in
+    // the result.  _usedPlaceIds is an Object that is being used as a set.
+    this._usedPlaceIds[aPlaceId] = true;
+
+    // Obtain the favicon for this URI.
+    let favicon;
+    if (aFaviconSpec) {
+      let uri = this._ioService.newURI(aFaviconSpec, null, null);
+      favicon = this._faviconService.getFaviconLinkForIcon(uri).spec;
+    }
+    favicon = favicon || this._faviconService.defaultFavicon.spec;
+
+    this._result.appendMatch(aURISpec, aTitle, favicon, aStyle);
+  },
+
+  /**
+   * Determines if the specified AutoComplete behavior is set.
+   *
+   * @param aType
+   *        The behavior type to test for.
+   * @return true if the behavior is set, false otherwise.
+   */
+  _hasBehavior: function PAC_hasBehavior(aType)
+  {
+    let behavior = Ci.mozIPlacesAutoComplete["BEHAVIOR_" + aType.toUpperCase()];
+    return (this._behavior & behavior);
+  },
+
+  /**
+   * Enables the desired AutoComplete behavior.
+   *
+   * @param aType
+   *        The behavior type to set.
+   */
+  _setBehavior: function PAC_setBehavior(aType)
+  {
+    let behavior = Ci.mozIPlacesAutoComplete["BEHAVIOR_" + aType.toUpperCase()];
+    this._behavior |= behavior;
+  },
+
+  /**
+   * Determines if we are done searching or not.
+   *
+   * @return true if we have completed searching, false otherwise.
+   */
+  isSearchComplete: function PAC_isSearchComplete()
+  {
+    // If _pendingQueries is null, we should no longer do any work since we have
+    // already called _finishSearch.  This means we completed our search.
+    return this._pendingQueries == null;
+  },
+
+  /**
+   * Determines if the given handle of a pending statement is a pending search
+   * or not.
+   *
+   * @param aHandle
+   *        A mozIStoragePendingStatement to check and see if we are waiting for
+   *        results from it still.
+   * @return true if it is a pending query, false otherwise.
+   */
+  isPendingSearch: function PAC_isPendingSearch(aHandle)
+  {
+    return this._pendingQueries.indexOf(aHandle) != -1;
+  },
+
+  //////////////////////////////////////////////////////////////////////////////
+  //// nsISupports
+
+  classDescription: "AutoComplete result generator for Places.",
+  classID: Components.ID("d0272978-beab-4adc-a3d4-04b76acfa4e7"),
+  contractID: "@mozilla.org/autocomplete/search;1?name=history",
+
+  QueryInterface: XPCOMUtils.generateQI([
+    Ci.nsIAutoCompleteSearch,
+    Ci.nsIAutoCompleteSimpleResultListener,
+    Ci.mozIStorageStatementCallback,
+    Ci.nsIObserver,
+  ])
+};
+
+////////////////////////////////////////////////////////////////////////////////
+//// Module Registration
+
+let components = [nsPlacesAutoComplete];
+function NSGetModule(compMgr, fileSpec)
+{
+  return XPCOMUtils.generateModule(components);
+}
--- a/toolkit/components/places/src/nsPlacesModule.cpp
+++ b/toolkit/components/places/src/nsPlacesModule.cpp
@@ -32,22 +32,16 @@ static const nsModuleComponentInfo compo
     NS_NAVHISTORY_CLASSINFO },
 
   { "Browser Navigation History",
     NS_NAVHISTORYSERVICE_CID,
     "@mozilla.org/browser/global-history;2",
     nsNavHistoryConstructor,
     NS_NAVHISTORY_CLASSINFO },
 
-  { "Browser Navigation History",
-    NS_NAVHISTORYSERVICE_CID,
-    "@mozilla.org/autocomplete/search;1?name=history",
-    nsNavHistoryConstructor,
-    NS_NAVHISTORY_CLASSINFO },
-
   { "Download Navigation History",
     NS_NAVHISTORYSERVICE_CID,
     NS_DOWNLOADHISTORY_CONTRACTID,
     nsNavHistoryConstructor,
     NS_NAVHISTORY_CLASSINFO },
 
   { "Page Annotation Service",
     NS_ANNOTATIONSERVICE_CID,
--- a/toolkit/components/places/tests/autocomplete/head_autocomplete.js
+++ b/toolkit/components/places/tests/autocomplete/head_autocomplete.js
@@ -108,60 +108,63 @@ function ensure_results(aSearch, aExpect
     do_check_eq(numSearchesStarted, 1);
     aExpected = aExpected.slice();
 
     // Check to see the expected uris and titles match up (in any order)
     for (let i = 0; i < controller.matchCount; i++) {
       let value = controller.getValueAt(i);
       let comment = controller.getCommentAt(i);
 
-      print("Looking for " + value + ", " + comment + " in expected results...");
+      print("Looking for '" + value + "', '" + comment + "' in expected results...");
       let j;
       for (j = 0; j < aExpected.length; j++) {
         // Skip processed expected results
         if (aExpected[j] == undefined) continue;
 
         let [uri, title, tags] = gPages[aExpected[j]];
 
         // Load the real uri and titles and tags if necessary
         uri = toURI(kURIs[uri]).spec;
         title = kTitles[title];
         if (tags && appendTags)
           title += " \u2013 " + tags.map(function(aTag) kTitles[aTag]);
+        print("Checking against expected '" + uri + "', '" + title + "'...");
 
         // Got a match on both uri and title?
         if (uri == value && title == comment) {
           print("Got it at index " + j + "!!");
           // Make it undefined so we don't process it again
           aExpected[j] = undefined;
           break;
         }
       }
 
       // We didn't hit the break, so we must have not found it
       if (j == aExpected.length)
-        do_throw("Didn't find the current result (" + value + ", " + comment + ") in expected: " + aExpected);
+        do_throw("Didn't find the current result ('" + value + "', '" + comment + "') in expected: " + aExpected);
     }
 
     // Make sure we have the right number of results
+    print("Expecting " + aExpected.length + " results; got " +
+          controller.matchCount + " results");
     do_check_eq(controller.matchCount, aExpected.length);
 
     // If we expect results, make sure we got matches
     do_check_eq(controller.searchStatus, aExpected.length ?
                 Ci.nsIAutoCompleteController.STATUS_COMPLETE_MATCH :
                 Ci.nsIAutoCompleteController.STATUS_COMPLETE_NO_MATCH);
 
     // Fetch the next test if we have more
     if (++current_test < gTests.length)
       run_test();
 
     do_test_finished();
   };
 
-  print("Searching for.. " + aSearch);
+  print("Searching for.. '" + aSearch + "'");
   controller.startSearch(aSearch);
 }
 
 // Get history services
 try {
   var histsvc = Cc["@mozilla.org/browser/nav-history-service;1"].
                 getService(Ci.nsINavHistoryService);
   var bhist = histsvc.QueryInterface(Ci.nsIBrowserHistory);
--- a/toolkit/components/places/tests/unit/test_000_frecency.js
+++ b/toolkit/components/places/tests/unit/test_000_frecency.js
@@ -236,18 +236,18 @@ AutoCompleteInput.prototype = {
       return this;
 
     throw Components.results.NS_ERROR_NO_INTERFACE;
   }
 }
 
 function run_test() {
   var controller = Components.classes["@mozilla.org/autocomplete/controller;1"].
-                   getService(Components.interfaces.nsIAutoCompleteController);  
-  
+                   getService(Components.interfaces.nsIAutoCompleteController);
+
   // Make an AutoCompleteInput that uses our searches
   // and confirms results on search complete
   var input = new AutoCompleteInput(["history"]);
 
   controller.input = input;
 
   // always search in history + bookmarks, no matter what the default is
   prefs.setIntPref("browser.urlbar.search.sources", 3);
@@ -259,17 +259,17 @@ function run_test() {
   var numSearchesStarted = 0;
   input.onSearchBegin = function() {
     numSearchesStarted++;
     do_check_eq(numSearchesStarted, 1);
   };
 
   input.onSearchComplete = function() {
     do_check_eq(numSearchesStarted, 1);
-    do_check_eq(controller.searchStatus, 
+    do_check_eq(controller.searchStatus,
                 Ci.nsIAutoCompleteController.STATUS_COMPLETE_MATCH);
 
     // test that all records with non-zero frecency were matched
     do_check_eq(controller.matchCount, results.length);
 
     // test that matches are sorted by frecency
     for (var i = 0; i < controller.matchCount; i++) {
       let searchURL = controller.getValueAt(i);
@@ -278,17 +278,18 @@ function run_test() {
         do_check_eq(controller.getValueAt(i), results[i][0].spec);
         do_check_eq(controller.getCommentAt(i), results[i][2]);
       } else {
         // If the results didn't match exactly, perhaps it's still the right
         // frecency just in the wrong "order" (order of same frecency is
         // undefined), so check if frecency matches. This is okay because we
         // can still ensure the correct number of expected frecencies.
         let getFrecency = function(aURL) aURL.match(/frecency:(-?\d+)$/)[1];
-        print("### searchURL: '"+searchURL+"', expectedURL: '"+expectedURL+"'");
+        print("### checking for same frecency between '" + searchURL +
+              "' and '" + expectURL + "'");
         do_check_eq(getFrecency(searchURL), getFrecency(expectURL));
       }
     }
 
     do_test_finished();
   };
 
   controller.startSearch(searchTerm);