--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1116,16 +1116,23 @@ Database::InitSchema(bool* aDatabaseMigr
 
       if (currentSchemaVersion < 39) {
         rv = MigrateV39Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       // Firefox 57 uses schema version 39.
 
+      if (currentSchemaVersion < 40) {
+        rv = MigrateV40Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 58 uses schema version 40.
+
       // Schema Upgrades must add migration code here.
 
       rv = UpdateBookmarkRootTitles();
       // We don't want a broken localization to cause us to think
       // the database is corrupt and needs to be replaced.
       MOZ_ASSERT(NS_SUCCEEDED(rv));
     }
   }
@@ -2341,16 +2348,41 @@ Database::MigrateV39Up() {
   // Create an index on dateAdded.
   nsresult rv = mMainConn->ExecuteSimpleSQL(CREATE_IDX_MOZ_BOOKMARKS_DATEADDED);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
+Database::MigrateV40Up() {
+  MOZ_ASSERT(NS_IsMainThread());
+  // We are changing the hashing function to crop the hashed text to a maximum
+  // length, thus we must recalculate the hashes.
+  // Due to this, on downgrade some of these may not match, it should be limited
+  // to unicode and very long urls though.
+  nsresult rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_places "
+    "SET url_hash = hash(url) "
+    "WHERE url_hash <> hash(url)"));
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_icons "
+    "SET fixed_icon_url_hash = hash(fixup_url(icon_url)) "
+    "WHERE fixed_icon_url_hash <> hash(fixup_url(icon_url))"));
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_pages_w_icons "
+    "SET page_url_hash = hash(page_url) "
+    "WHERE page_url_hash <> hash(page_url)"));
+  NS_ENSURE_SUCCESS(rv, rv);
+  return NS_OK;
+}
+
+nsresult
 Database::GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                            nsTArray<int64_t>& aItemIds)
 {
   nsCOMPtr<mozIStorageStatement> stmt;
   nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
     "SELECT b.id FROM moz_items_annos a "
     "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id "
     "JOIN moz_bookmarks b ON b.id = a.item_id "

--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 39
+#define DATABASE_SCHEMA_VERSION 40
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -299,16 +299,17 @@ protected:
   nsresult MigrateV32Up();
   nsresult MigrateV33Up();
   nsresult MigrateV34Up();
   nsresult MigrateV35Up();
   nsresult MigrateV36Up();
   nsresult MigrateV37Up();
   nsresult MigrateV38Up();
   nsresult MigrateV39Up();
+  nsresult MigrateV40Up();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                             nsTArray<int64_t>& aItemIds);

--- a/toolkit/components/places/SQLFunctions.cpp
+++ b/toolkit/components/places/SQLFunctions.cpp
@@ -14,21 +14,28 @@
 #include "nsUnicodeProperties.h"
 #include "nsUTF8Utils.h"
 #include "nsINavHistoryService.h"
 #include "nsPrintfCString.h"
 #include "nsNavHistory.h"
 #include "mozilla/Likely.h"
 #include "nsVariant.h"
 #include "mozilla/HashFunctions.h"
+#include <algorithm>
 
 // Maximum number of chars to search through.
 // MatchAutoCompleteFunction won't look for matches over this threshold.
 #define MAX_CHARS_TO_SEARCH_THROUGH 255
 
+// Maximum number of chars to use for calculating hashes. This value has been
+// picked to ensure low hash collisions on a real world common places.sqlite.
+// While collisions are not a big deal for functionality, a low ratio allows
+// for slightly more efficient SELECTs.
+#define MAX_CHARS_TO_HASH 1500U
+
 using namespace mozilla::storage;
 
 ////////////////////////////////////////////////////////////////////////////////
 //// Anonymous Helpers
 
 namespace {
 
   typedef nsACString::const_char_iterator const_char_iterator;
@@ -233,17 +240,17 @@ namespace {
       sourceCur = sourceNext;
     }
 
     return false;
   }
 
   static
   MOZ_ALWAYS_INLINE nsDependentCString
-  getSharedString(mozIStorageValueArray* aValues, uint32_t aIndex) {
+  getSharedUTF8String(mozIStorageValueArray* aValues, uint32_t aIndex) {
     uint32_t len;
     const char* str = aValues->AsSharedUTF8String(aIndex, &len);
     if (!str) {
       return nsDependentCString("", (uint32_t)0);
     }
     return nsDependentCString(str, len);
   }
 
@@ -411,36 +418,36 @@ namespace places {
   {
     // Macro to make the code a bit cleaner and easier to read.  Operates on
     // searchBehavior.
     int32_t searchBehavior = aArguments->AsInt32(kArgIndexSearchBehavior);
     #define HAS_BEHAVIOR(aBitName) \
       (searchBehavior & mozIPlacesAutoComplete::BEHAVIOR_##aBitName)
 
     nsDependentCString searchString =
-      getSharedString(aArguments, kArgSearchString);
+      getSharedUTF8String(aArguments, kArgSearchString);
     nsDependentCString url =
-      getSharedString(aArguments, kArgIndexURL);
+      getSharedUTF8String(aArguments, kArgIndexURL);
 
     int32_t matchBehavior = aArguments->AsInt32(kArgIndexMatchBehavior);
 
     // 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 (matchBehavior != mozIPlacesAutoComplete::MATCH_ANYWHERE_UNMODIFIED &&
         StringBeginsWith(url, NS_LITERAL_CSTRING("javascript:")) &&
         !HAS_BEHAVIOR(JAVASCRIPT) &&
         !StringBeginsWith(searchString, NS_LITERAL_CSTRING("javascript:"))) {
       NS_ADDREF(*_result = mCachedZero);
       return NS_OK;
     }
 
     int32_t visitCount = aArguments->AsInt32(kArgIndexVisitCount);
     bool typed = aArguments->AsInt32(kArgIndexTyped) ? true : false;
     bool bookmark = aArguments->AsInt32(kArgIndexBookmark) ? true : false;
-    nsDependentCString tags = getSharedString(aArguments, kArgIndexTags);
+    nsDependentCString tags = getSharedUTF8String(aArguments, kArgIndexTags);
     int32_t openPageCount = aArguments->AsInt32(kArgIndexOpenPageCount);
     bool matches = false;
     if (HAS_BEHAVIOR(RESTRICT)) {
       // Make sure we match all the filter requirements.  If a given restriction
       // is active, make sure the corresponding condition is not true.
       matches = (!HAS_BEHAVIOR(HISTORY) || visitCount > 0) &&
                 (!HAS_BEHAVIOR(TYPED) || typed) &&
                 (!HAS_BEHAVIOR(BOOKMARK) || bookmark) &&
@@ -467,17 +474,17 @@ namespace places {
     // Clean up our URI spec and prepare it for searching.
     nsCString fixedUrlBuf;
     nsDependentCSubstring fixedUrl =
       fixupURISpec(url, matchBehavior, fixedUrlBuf);
     // Limit the number of chars we search through.
     const nsDependentCSubstring& trimmedUrl =
       Substring(fixedUrl, 0, MAX_CHARS_TO_SEARCH_THROUGH);
 
-    nsDependentCString title = getSharedString(aArguments, kArgIndexTitle);
+    nsDependentCString title = getSharedUTF8String(aArguments, kArgIndexTitle);
     // Limit the number of chars we search through.
     const nsDependentCSubstring& trimmedTitle =
       Substring(title, 0, MAX_CHARS_TO_SEARCH_THROUGH);
 
     // Determine if every token matches either the bookmark title, tags, page
     // title, or page URL.
     nsCWhitespaceTokenizer tokenizer(searchString);
     while (matches && tokenizer.hasMoreTokens()) {
@@ -999,52 +1006,57 @@ namespace places {
     MOZ_ASSERT(aArguments);
 
     // Fetch arguments.  Use default values if they were omitted.
     uint32_t numEntries;
     nsresult rv = aArguments->GetNumEntries(&numEntries);
     NS_ENSURE_SUCCESS(rv, rv);
     NS_ENSURE_TRUE(numEntries >= 1  && numEntries <= 2, NS_ERROR_FAILURE);
 
-    nsString str;
-    aArguments->GetString(0, str);
+    nsDependentCString str = getSharedUTF8String(aArguments, 0);
     nsAutoCString mode;
     if (numEntries > 1) {
       aArguments->GetUTF8String(1, mode);
     }
 
+    // HashString doesn't stop at the string boundaries if a length is passed to
+    // it, so ensure to pass a proper value.
+    const uint32_t maxLenToHash = std::min(static_cast<uint32_t>(str.Length()),
+                                           MAX_CHARS_TO_HASH);
     RefPtr<nsVariant> result = new nsVariant();
     if (mode.IsEmpty()) {
       // URI-like strings (having a prefix before a colon), are handled specially,
       // as a 48 bit hash, where first 16 bits are the prefix hash, while the
       // other 32 are the string hash.
       // The 16 bits have been decided based on the fact hashing all of the IANA
       // known schemes, plus "places", does not generate collisions.
-      nsAString::const_iterator start, tip, end;
-      str.BeginReading(tip);
+      // Since we only care about schemes, we just search in the first 50 chars.
+      // The longest known IANA scheme, at this time, is 30 chars.
+      const nsDependentCSubstring& strHead = StringHead(str, 50);
+      nsACString::const_iterator start, tip, end;
+      strHead.BeginReading(tip);
       start = tip;
-      str.EndReading(end);
-      if (FindInReadable(NS_LITERAL_STRING(":"), tip, end)) {
-        const nsDependentSubstring& prefix = Substring(start, tip);
+      strHead.EndReading(end);
+      uint32_t strHash = HashString(str.get(), maxLenToHash);
+      if (FindCharInReadable(':', tip, end)) {
+        const nsDependentCSubstring& prefix = Substring(start, tip);
         uint64_t prefixHash = static_cast<uint64_t>(HashString(prefix) & 0x0000FFFF);
         // The second half of the url is more likely to be unique, so we add it.
-        uint32_t srcHash = HashString(str);
-        uint64_t hash = (prefixHash << 32) + srcHash;
+        uint64_t hash = (prefixHash << 32) + strHash;
         result->SetAsInt64(hash);
       } else {
-        uint32_t hash = HashString(str);
-        result->SetAsInt64(hash);
+        result->SetAsInt64(strHash);
       }
     } else if (mode.EqualsLiteral("prefix_lo")) {
       // Keep only 16 bits.
-      uint64_t hash = static_cast<uint64_t>(HashString(str) & 0x0000FFFF) << 32;
+      uint64_t hash = static_cast<uint64_t>(HashString(str.get(), maxLenToHash) & 0x0000FFFF) << 32;
       result->SetAsInt64(hash);
     } else if (mode.EqualsLiteral("prefix_hi")) {
       // Keep only 16 bits.
-      uint64_t hash = static_cast<uint64_t>(HashString(str) & 0x0000FFFF) << 32;
+      uint64_t hash = static_cast<uint64_t>(HashString(str.get(), maxLenToHash) & 0x0000FFFF) << 32;
       // Make this a prefix upper bound by filling the lowest 32 bits.
       hash +=  0xFFFFFFFF;
       result->SetAsInt64(hash);
     } else {
       return NS_ERROR_FAILURE;
     }
 
     result.forget(_result);

--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -1,17 +1,17 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2 -*-
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 // It is expected that the test files importing this file define Cu etc.
 /* global Cu, Ci, Cc, Cr */
 
-const CURRENT_SCHEMA_VERSION = 39;
+const CURRENT_SCHEMA_VERSION = 40;
 const FIRST_UPGRADABLE_SCHEMA_VERSION = 11;
 
 const NS_APP_USER_PROFILE_50_DIR = "ProfD";
 const NS_APP_PROFILE_DIR_STARTUP = "ProfDS";
 
 // Shortcuts to transitions type.
 const TRANSITION_LINK = Ci.nsINavHistoryService.TRANSITION_LINK;
 const TRANSITION_TYPED = Ci.nsINavHistoryService.TRANSITION_TYPED;

new file mode 100644
index 0000000000000000000000000000000000000000..3eff303261b52cc7cc63660fa20822920ff5d6fa
GIT binary patch
literal 1146880
zc%1Fsdz4)FT^R5?kDZ-aYxTrlJF(+Y9K}{FtyZtdGB}Pbtsa*3uq-K3iqA5;b9Z;7
z*}3bPSxGBfx>le)lsc!-!#M=XBfz1QhNL-%(&li|&_mPGwB(RN0*8<jQov3Eh0tKf
zoRB|yXJ((;T?G!MCh_NUcJFU~-~0VN?(aV4O8@LrPd-s;hQ-mSK2d5GcLvV~>2&bU
zVlfDUZ1Q_wFz=q3*sN6Y`#^AO*`Po5?%r$7;LR658(cql?YZZ!UfcQX`<^>=wSRhW
z`j4($oL+V1uFH>J{;f;5H$U5aZ}Ux!|Ij#E|6KjMpZViw9-sX9<U6AO5j|1+NbTW?
zU!K@dy^(YR000000000000000000000000000000004h4ZoK8q-F;6!n7VPkQY(j7
zCZelDm1a267%J6jQKS92)NIx(!&A+0xs3bvpBmhEda!ur_>m{i3>J?ZKQMT%_|1DM
zo;ZGUR`G#WWvEi#Qf$?S<{BiS%{SI;?Cv{sZ|cV2+$1_(PgYAK;nEqlcfNV0xvkiA
zc3LwNYG<r8qkD_pedjl&ZXBB%^kO)DIjWaudY+6L&2p((8k(wAo|y`lWNln&cHg|4
z*=f#ZE}UsAf2h@9^NsYq-F-*yPu<u!H}-H8U7RS@FE)n8rYhx|XEwLDxYE>CZa+Jv
z`92<KrEGrgP2GKi$sF!lW)8_L!&12%mY43kcV-654ZXP8G6S~~_O%i=-&l7~ci&UV
z@Vl28zIC}(OO574RIZFxmYc<!ZZV5xTQ4)2(TiJ(t-ND1d7H1@-QD--3TI`qR1a&-
zr91Aq#Y7ggS!Vdo-u7itX;z}z=4am6-S?fz@VzUn$kOoL-((eTb>z+I$#C<H%p1D<
z_HSEw$m5kpGpbKtswA`OoYCcXy>ZFdE3}*)f6?yZ1MRY%mCWL<ThC&&9!)I2>kZ#z
z7IQ6Em_=*<P`k4EM&F&?eaDhnJi5Xx+IRBG3v$;tnabkkE6iv9X|Z5^F7+kLvoUq!
z_PK%EY0Ez<I=k*%={d1N%h~C4cF#N^uHTV7**7jcEi<iKcTIbKi&mqvvv0{Vtk~%0
zL0cI^3yyo@_U^t%lJN^Sk3U)uN5b03^iA<QRvLOy{>`J#?%aIgJG%S!EH_+xN+Z!!
ztvMgOeWkJHlW!iVb7bvZo5Ky=eY=yfQa6t^o_tB%6#I^qhMLR0d8B%Hsl9Xa#QGIh
zaH?J%8ZR}*Z;EeNX{bf{HxD<vbMw)4xxP)CQvaw~8m@+oXR66FXsFRFHMcMPynbek
z)B7HKVz9Vy&jZcj>Xu6R%9d7b^Lrjz+uirzgQ@SkzunzU?<6->*DdOF$@@#OSScq5
zb$am7;Hl!tQ%8>NJ9WNzbnyI^;>?@P+|J`CP8W}#dE$v>UMyyFwiHLAS~Gce7oRwB
z{LtBbr}iJ-mjp+vrLo3bKL-X6?mP3u>EghaVt8e;QZKb0@yqRPJ%^Wz&wW)cw{zjw
z*3$i(-*f+(?!J5PO?}@zb4xe3XzdScmn_#eU8vb7)3?`3-B{b(-M4dR>c*i(D>Z*K
zjb%csmtDOD3Ab9uT4^FI&Md_PJ9liJeMHYL=jOrHxxVu|Q$hPyo4GwoQ_ZMdA6jO#
zq3z2A*PL9HYu!EP7u}0t^1QE&++6Kl_Kuv{`9N#JTaw!58*l3AZr$ED;<>e&ea&6?
z`L-piGygKY(y|oyojHBt$nm7*vBBe~w-jeu6i*MHJ3X^NORvBMZ`AF?&3kUk^&Q=G
ztCgF3f#1Hcw(7<k^U0%sPwK{*xg%TfQX5voW>{V}SXgqbOHx_~-TF4|9Lu6hp>^S&
zN=CaBF1@Q3T%$({xxT0O-0HBF4B9!qCE=d;jCFVS-G6`TANMXj&_$K}$_I9<i+kZM
zn%w6Xm)vok2S(@BchPyQEWGQJjw;P+xcI3tbG8;;0Haa09M*^0!?xCUnTNshkAN-n
z=VVK<F<l#ZD*4KpYTV*9bkg>Zmuh3-{?>PRSYJ7N`{o;4y4sK6_soBLwZ4%Xb02a`
zR=6F$)#|nqI+xMhfV20;>`Tmo6-?ITR+m+>>h*B6a;0<YY|rKT2JgMqHP)V8=elZt
z?7s2#On2Ybt*Q6iJOBM$o1ALSywToV&o2FjUa+@y*thtGX{Ro{92V@GYJ{Das`+DI
z_+(k|O5N^d^X5mhxxS~i-s)Hv&a89D3nN`Y5aiqcLvtwI-M4L9>OGIlpW}tE^GgDm
zrRRL{>;KB<e*PaS3vQbw55)PG=bK}T@61NnXe_wjHh=G)RCnLTjj4aKckW0!FL(2w
z(o5z(`}$X0dDh9B;o_TknfrS7Wp#0M!OQY;U+d$Q<Q`w<En&fRvG@j9F5~8#W-e*#
z_61ot{i|dydC?<eG^&S{vD!)#UU<3Aye!`$De1Z#Hb&}|$@W9BGeUB=UaEwbhbj}L
zv9R?%-nnsmlk2eOxf?<JGx7fGe|r6gu7Ah1FI=l%D?Im!BnSWi000000000000000
z00000000000000000000{Qq^ZXHD>AuqI!~=Yvg!ToAPXEd0Z*zrOy++uz!V>di;C
z?|SP*>B_0FF;#6g9@#$7KRA4Ls&*_oFtB&990V`#I`jBvw!EXTCfK*MpLPci-PFFZ
zcl5~czFp&!R}R%$?ce_Uzwjet`8C1*%{vSELOQpp&=myZ&E{m|;ceTJerjQ}e<HeC
zsa8w<QGION$#$rCtP>imNByO0wQ@C@=x>I#QgyOF|Hh!}{N<NE_VoCk6DKboeyVi#
zVB@h153WCc?e@1+yVnLcx`X@j`FuK9G}1(6c(~H+ABiTmJ=zHCm%{oZmHNoSk>5Hp
zUaHl?>LZ(W?5tJB#+%jYiD;z1*=jh^AG{Dw?Pwlr>>fIE>cYMU*FSpx?zip8tqJZA
zf|<dRWho6uQ_Y7*>ZQhb*a%*@RDI_BV}qCKmq$h~1i?@J+y{%l_Tgu{k{R9}>|8p-
zQn?(}8jIE<tZhB>)V9$|Jsgd$bP~4BOl@m3Y&66A)@Bq{8`~BxQ==A@%cW$(dq)Q9
zj~(7K6}{`?*$3CZFmQPATy{-xB-q;-JGEf!a(F4MMw4NE(eMj<t%s9QHOVR`9gjEm
z9X)*b>dE5=PnXjVuK(E|9{<qU%$nd(uxDw{!&76O4p-{9U5-r+C;dKoVdChnsgcuL
zkCt{O{eJq-FFgHpdQEU5cy#G%4OgSF{+YE{vG3_>b9}5)>mQ4%t^QA*Jb0;c{OH~T
zdxj4@xc)=mxbZvRomvwN1zVSPfBEv|WzNJ%RBP5N!&A+0(J-y#;Dz$ZYPDJ)xbXP&
z)$<RoAN{TOKiiw!f~ok=g5(DP00000000000000000000000000000000000003Se
z)}^|Gd@7g9=Yy{EmtXqW)8pyhB%F%B79>9a000000000000000000000000000000
z00000008hhlTT$+8w&Y}=xR?=OU17S$qxVk000000000000000000000000000000
z000000KDGhv#AY*{6uuMH>q^T?+oHUjXx28Abug9jK4dn0ssI2000000000000000
z0000000000000000002M-^v@hbHVm>A(*U|YGJc~BDz|sR!jX+eJuaR^|@TIF`W-4
zD#OE-X8%Yu5xnq*u2z0ND3!}mt+6mac;TLGF4&XoD~FfDYBU+v7w^71lM8kyyN9R7
zI?+XYi|JhONNaC38tboB#>Sh~>BSivQn}#1)^rvIdy-@5j>|#(<@h(^Uy6S;{(<<}
zqzV84000000000000000000000000000000000000RPY3k=dS_td?qFvwtGGTB%k`
z{ZW0adv)f%!h-th%*ND2Wq7#K>>r6Ha(89+q{`u?uo_K<^@Z)ScV>2{hNs3lfdxA<
zcV`|+4OgSF{#s>hyjh)IxHH|FM5$bkYK?{AuHIyR>!1Bl5dU`kBk{TTt=GSF{oh=l
zyng?+Kfd-e*Un$N{khLP_s^eu^0_;n{alg+000000000000000000000000000000
z000000094>Y+1iLNCl}v@-dg&R48Q9LD%`qFLh-HX3Ha2rw{Los-@A!@YqA^RtJSt
zDt})mJJpju6^?|pX7O}stkG_e`stuuW<T-1!^g)@)_1@A%;`M`qx9ajotB$sS{5?L
zqDHfLw$i9H!*Z+1i?9CV^PMh!;?DB!$EWuXTxvdXWNaY)U2ED+Q=8jO^QnA3ce4Gr
z&x^-8e|Egx`jtD@cFKFcFu3n>^sXmIk3K#Wol75B-D$mdrge9|>p-P3GSz4lk9Yp4
zc`>RLkDS`yY29<KQ?7pJm8iV^METtGnd66cr{B@r>1FFoFS&enU$t7Cj;89xk$R~y
z9<~qv#h1VSkxu*c_lLXAO$<bPhofU-htiL&>a^cI)4nU8nH~Lf*l33J;^`==&h+t>
zpi_SBQ~R3(M<#Y`ePZZB>D}o=w{`k>bf%ANK0UJl#RIc{*1dQ<Y+jD)7dsvN!S{5^
zFAf|(vg6p`+xP7}bLr|}=AAw5jtV<xI?Ci{`+00?ta!R!8o3zOJ1u|xFFNJ#{@~92
z2aZh-o!xrk?7^LxeTB~1oIRX${$QmZjz(AJ*0l9k<2y}1`cS9*c>eI!gW-jN6XlWS
z)HCTr`Syi3cQomA`sO}Pg^gr=M`oAy!_Uv2=#$UXYL#6lw^yh49>_n`oy;Y<pf=4O
z&7tJVI8wV5RWHq4STFzhUv<h~eBZHMr$%=SJ+yuI#bYDs@5;5NP?$NXg+e-eEE=v<
z!{TF6baA3ozt|c0a~nP~TTZn154C+)SEu!ZGgovvbD}w(oPnDfulZDG><a@^wb7(;
zx!pKDknOa-eRk~h>@76cBq^IoY-q+KnRbi9w%PIK25MhB!=?J7*2&$}?1bB`yB<!r
zo98z#ZGJ4QO)YHOy6Y#B*zCw%52jje^ZDM{$=;k@kD}&mc5myk^89Q2R09A200000
z000000000000000000000000000000fY(}2YxDeTJP7~*00000000000000000000
z0000000000000000C<h{Cco+UPlNbt$p!!b000000000000000000000000000000
z000000KWYd(p|xZR4`GlW%H@7U|lL0zMAPtcBJF42JzRE4FCWD000000000000000
z00000000000000000000yl!-7Hl!xXwRBfzU19iYZxTtxe;y=1000000000000000
z000000000000000000000002+I<YpD*_4`yt`1!cr!PnKawFZFL^JURg7}N^$CCm8
z000000000000000000000000000000000000091>>&s+<-6yN1k+8Atsfkj(`B)TP
zOv;NJ)0yDN@J!`oJ(>*b%}SC~4jUu&%4D+=)%sFN+lgqnQVqAwW;RYmQL`uMI1~S3
z5PvcLcv1iW000000000000000000000000000000000000Kh+ZeVN^biD<Y|4Yv(P
z(Zz{U{bJ)(6gA(RIg*+UoUBKaVZB)i8{5iZW29c0Y*wOL`p(Sm)X8dTBndy2q%|L#
zNze4QI)45&J}>|P000000000000000000000000000000000000C<h{CcoMEfgt{J
zd@Vked;kCd00000000000000000000000000000000000fLnMV+Y_Wx8}q4DF1Ido
zDjW%G&C{i^Mm7_4oxl82_P>01w%nX)W!~4$T$?!-HJWEDjY=~t&!nb);?CLfLi)BO
z^+qQ*lipV@7l)(h;zX%_u~BSB#pZaWQ5=n`<*?qWHo`Cog%ibcr7>A8O^4-TRBJ_w
zkIl6@9YxjQQoS?Qi!Z<T+-!M!Dw$ScO+Hn~W^>!KFMh7?{jJ~L<k;3e_t_x+pYi+S
zW_&ch@A|9Pf9?8vuRnSH?rUGZ_Q7k<UOReib&>!80000000000000000000000000
z00000000000DKGEu{OKu=!S{t>d?h-`f^k+HyY1WE6s4IG}VkMwQ_i6XyMMG?K_Iw
zzjIA?)A_!I;YBHv)zU~f88w>aQnNHPRjWKR6}EdynijYBug>28op-ew%>5DfMU|ms
z@QHT%_J@i)iaQ2+v-dxGtNh7QJ*+inTkI-se|S~){-?g#2-Q-fIT4jBqm{6{V6^SG
zW$z!n{T6MLV+u><@`6S?d$RW*xmA;~sY-d_G9-<*KU~OeJJw#p@k*l^)u%628kJ^a
zNuaZstwB3YTPwITpWU{9!{4CoXg!*kZML)fZ`f$zSZ~W^H$KunwDvR_^Ph&M>eZp~
zQe(W6I#AsH)~@Wv-OJ~WC)dJk-j4gT*^PUa&uh<MB$}!<lf>O`%d9x~XgwSWYa`RM
zo$lI}&Tc%kd~WMRw>zFcu%z>?sqDu6%QskZx{`zIN$!-M_`N~=O8h7B7vj&v|2_WI
z_}|4pAOBbq1ONa40000000000000000000000000000000001h*TSkyE)@hX?>h7N
zXSVdrR^I;mzwjf4PUWY5?t{f&`*5x&)0KK~{ipx@!qb_~#}9qu#_yy%AAk0T$3K+q
ze0*Wx@L*RV(^YtI{pfGK|JhFP__f>LlJ9(c^!(j#>+VU0?THTu@n6TU#9xU&6aPy5
zGw~0^m*R6t5C8xG00000000000000000000000000000000000{+8Bc?n_NXBmK?F
z@Ni|Kzx$rdqp7ia)L*JrD_5h5{^@FSe5_LIAB(EP{pk&vt%ZeqFJHdg-<R3Bs6{iZ
zm8z5d`J3a7T2wBV`n%qc*}EuS4=1B)cquIRXYb1FS+uKNj!g~sXSy<LQvE&cZ6TWp
zQn{XF?mh8u2JtuISL3h7e-?i!{-gNw@$bc-PJ#dc0000000000000000000000000
z00000000000Pw9Tn<=F7*-Spw)7lhTo9@;o*V=ToHrduD)7qpnnS7xqY19+{Y7qZ*
z{I&Qm;xEU482^6!>G+fJe@%h_00000000000000000000000000000000000008i<
zA(u&~@^8$yir|IrPLb;rU7aG^DKecR-IYlfl3*sE>S=8XJxM1$@vjH*H{w_0uf~5C
ze<}W>`1A4a#h*@s000000000000000000000000000000000000002+tz}gvmkPSh
zUw-LhPmkxbnIP5E+7w!w?$##P+H|!x+14i0+N3j?pwN>v?up+O#9xU&AAd6bX#9cr
zU&cQWPsig)5C8xG00000000000000000000000000000000000{%+Q0Hl;3ApE>{7
z;HCQIk<kmeR-mzW^vLkOUE`Bi4%G^+z<6Wd(Zh$Yo;-f=bUE7!gi|}3#~Qnb&YZfi
zuX{~qQ=xpaTCLUxE<8Sc^?WPg$qN%lcTJ6)-g>mOGt&y3JbCa^<@nLP2lfmfNVfum
z!)K>z$D#uRdk4!st-#)qf%;>I_e@3ax_Gv$71(p)<i*2JmChb)Ja!@9lT0=he>F&c
z000000000000000000000000000000000000002sb)+|&$`$fK*ZIpYeeCJ+o+Ofr
zzY!!q000000000000000000000000000000000000002+x|GS}3q47hieC<r9{>OV
z00000000000000000000000000000000000cwM<IlPd&W=P$qXv8Ts-lKT4i`-1rE
z@n6ROJAN_#eEhrdr{Yh<|2h6>{LAr&;-8P-AOC3lFXDfeBmn>b000000000000000
z00000000000000000000z~7@>HdRRVtZNsAwe2Fmrd@QeZWp=UcG0z}U1V=-7nz=R
zkuG#)3rS`!8>CX1_3a{^?-aRC(bXxkog&jI(p^bWNcSY;uaBP(;=hhxiN6wmDgIya
zXXD?Fe<S{Q{2$|gAOG9<U&rr{-xvR2{QXH1000000000000000000000000000000
z000000002|J?YM-QmK4yO{eTy-6^xZoiekkQ>JgrWmAPzz9%X2seGYb%XGJEnYHbl
zbUNRTrq{Ql>2<kmA(hJJ+C`?TU8J*J*+SAV*(Mp;Y(8J;N#?Nr`Zt33tMMPlzZ3tr
z_*dc&#y=JRQ2f1dGY;dk@uB#kcys)Q__ibo000000000000000000000000000000
z00000004k*ORKY~T&gGNI)C}4>?hv0u3as(tEr#3b8WktZ&hD><(@CBX;-^D)z$A@
z-LB?3)%5rGwyRz3>dRmI)T(wh+o^tW;I?)()2aUM5B9XH=}z_I`9g2DkV|!HzxclH
z-fYmRz0{Q*Sih*2UX|1ev$eThFTVPd&u8XquiUXVKVN(K!a&!2?Q<JGl3P$)^Qml4
zvJUIxz94=%{$l*u_>=K}ihn8oSMiU=FT`<NkHh#}d^CPXyghzPk^}$%0000000000
z0000000000000000000000000!0XMbOfD64oxl82S9W0iTqX6>!MfSXi?9CV^K0iS
zuiUYA&3vWj-0Hc?%U}OU?|kJe!K(SnAAHYk^Oax!i=O$)M;|K8S3dlFe!lYKf7Lx#
z`P_z&<mM}DKGn6bl3iHIEUct&%j62Pm7e5a*I)n5ApT1H`S_FZN8=B~KNkPf_)0t$
zpN$9OUGaVKhB$rw|6Kn<k^}$%00000000000000000000000000000000000z_*IE
znN6uHQF;4`^110V#}DmZ-3m<AMl02@Jk-+F3N)jrI$Wx^1DST9G}aiJkzJG7RH#Q$
zb2iXQn23gxE;{vGI}p~UW)sq_K)CDN#6YxnI65|VsJ9g;?|yuG|G=f@6Gz4d*0usC
zpQ+U<yH0MePVYUCZv~DY*>P;}?fZ6~xpZ~#wpQTSu2Z8sh926!`{J>Y?pEN))#=0g
zqH1ZhF+8@u6*zqLV0dBRM0un+^-Q51I6i)|zWd#0PVYGwt!o7a_g#+O_2lT$$A_YG
zYg&Q*&4D8mJGMSCbfNU_Rjt6z{RfUs51rk5;_ShlJw3^yrQ^R0;;$zg0000000000
z00000000000000000000000000001Z{m5lgK`NW>N{T|JrxkhrHJ%Xw0000000000
z0000000000000000000000000006wkdXnF4{D(pOSMgWlKS@3S000000000000000
w00000000000000000000006+ZrS5Dhm0Fj{w#&7dOjkBlDCF9;OgjC40ogPS>i_@%

--- a/toolkit/components/places/tests/migration/xpcshell.ini
+++ b/toolkit/components/places/tests/migration/xpcshell.ini
@@ -20,16 +20,17 @@ support-files =
   places_v32.sqlite
   places_v33.sqlite
   places_v34.sqlite
   places_v35.sqlite
   places_v36.sqlite
   places_v37.sqlite
   places_v38.sqlite
   places_v39.sqlite
+  places_v40.sqlite
 
 [test_current_from_downgraded.js]
 [test_current_from_v6.js]
 [test_current_from_v11.js]
 [test_current_from_v19.js]
 [test_current_from_v24.js]
 [test_current_from_v25.js]
 [test_current_from_v26.js]

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unit/test_hash.js
@@ -0,0 +1,44 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+add_task(async function() {
+  // Check particular unicode urls with insertion and selection APIs to ensure
+  // url hashes match properly.
+  const URLS = [
+    "http://президент.президент/президент/",
+    "https://www.аррӏе.com/аррӏе/",
+    "http://名がドメイン/",
+  ];
+
+  for (let url of URLS) {
+    await PlacesTestUtils.addVisits(url);
+    Assert.ok(await PlacesUtils.history.fetch(url),
+              "Found the added visit");
+    await PlacesUtils.bookmarks.insert({
+      url, parentGuid: PlacesUtils.bookmarks.unfiledGuid
+    });
+    Assert.ok(await PlacesUtils.bookmarks.fetch({ url }),
+              "Found the added bookmark");
+    let db = await PlacesUtils.promiseDBConnection();
+    let rows = await db.execute(
+      "SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url",
+      {url: new URL(url).href});
+    Assert.equal(rows.length, 1, "Matched the place from the database");
+    let id = rows[0].getResultByName("id");
+
+    // Now, suppose the urls has been inserted without proper parsing and retry.
+    // This should normally not happen through the API, but we have evidence
+    // it somehow happened.
+    await PlacesUtils.withConnectionWrapper("test_hash.js", async wdb => {
+      await wdb.execute(`
+        UPDATE moz_places SET url_hash = hash(:url), url = :url
+        WHERE id = :id
+      `, {url, id});
+      rows = await wdb.execute(
+        "SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url",
+        {url});
+      Assert.equal(rows.length, 1, "Matched the place from the database");
+    });
+
+  }
+});

--- a/toolkit/components/places/tests/unit/xpcshell.ini
+++ b/toolkit/components/places/tests/unit/xpcshell.ini
@@ -78,16 +78,17 @@ skip-if = (os == "win" && os_version == 
 [test_corrupt_telemetry.js]
 [test_crash_476292.js]
 [test_database_replaceOnStartup.js]
 [test_download_history.js]
 [test_frecency.js]
 [test_frecency_decay.js]
 [test_frecency_zero_updated.js]
 [test_getChildIndex.js]
+[test_hash.js]
 [test_history.js]
 [test_history_autocomplete_tags.js]
 [test_history_catobs.js]
 [test_history_clear.js]
 [test_history_notifications.js]
 [test_history_observer.js]
 [test_history_sidebar.js]
 [test_hosts_triggers.js]