1/* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 5"use strict"; 6 7/** 8 * This file implements a mirror and two-way merger for synced bookmarks. The 9 * mirror matches the complete tree stored on the Sync server, and stages new 10 * bookmarks changed on the server since the last sync. The merger walks the 11 * local tree in Places and the mirrored remote tree, produces a new merged 12 * tree, then updates the local tree to reflect the merged tree. 13 * 14 * Let's start with an overview of the different classes, and how they fit 15 * together. 16 * 17 * - `SyncedBookmarksMirror` sets up the database, validates and upserts new 18 * incoming records, attaches to Places, and applies the changed records. 19 * During application, we fetch the local and remote bookmark trees, merge 20 * them, and update Places to match. Merging and application happen in a 21 * single transaction, so applying the merged tree won't collide with local 22 * changes. A failure at this point aborts the merge and leaves Places 23 * unchanged. 24 * 25 * - A `BookmarkTree` is a fully rooted tree that also notes deletions. A 26 * `BookmarkNode` represents a local item in Places, or a remote item in the 27 * mirror. 28 * 29 * - A `MergedBookmarkNode` holds a local node, a remote node, and a 30 * `MergeState` that indicates which node to prefer when updating Places and 31 * the server to match the merged tree. 32 * 33 * - `BookmarkObserverRecorder` records all changes made to Places during the 34 * merge, then dispatches `nsINavBookmarkObserver` notifications. Places uses 35 * these notifications to update the UI and internal caches. We can't dispatch 36 * during the merge because observers won't see the changes until the merge 37 * transaction commits and the database is consistent again. 38 * 39 * - After application, we flag all applied incoming items as merged, create 40 * Sync records for the locally new and updated items in Places, and upload 41 * the records to the server. At this point, all outgoing items are flagged as 42 * changed in Places, so the next sync can resume cleanly if the upload is 43 * interrupted or fails. 44 * 45 * - Once upload succeeds, we update the mirror with the uploaded records, so 46 * that the mirror matches the server again. An interruption or error here 47 * will leave the uploaded items flagged as changed in Places, so we'll merge 48 * them again on the next sync. This is redundant work, but shouldn't cause 49 * issues. 50 */ 51 52var EXPORTED_SYMBOLS = ["SyncedBookmarksMirror"]; 53 54Cu.importGlobalProperties(["URL"]); 55 56ChromeUtils.import("resource://gre/modules/Services.jsm"); 57ChromeUtils.import("resource://gre/modules/XPCOMUtils.jsm"); 58 59XPCOMUtils.defineLazyModuleGetters(this, { 60 Async: "resource://services-common/async.js", 61 AsyncShutdown: "resource://gre/modules/AsyncShutdown.jsm", 62 Log: "resource://gre/modules/Log.jsm", 63 OS: "resource://gre/modules/osfile.jsm", 64 PlacesSyncUtils: "resource://gre/modules/PlacesSyncUtils.jsm", 65 PlacesUtils: "resource://gre/modules/PlacesUtils.jsm", 66 Sqlite: "resource://gre/modules/Sqlite.jsm", 67}); 68 69XPCOMUtils.defineLazyGetter(this, "MirrorLog", () => 70 Log.repository.getLogger("Sync.Engine.Bookmarks.Mirror") 71); 72 73// These can be removed once they're exposed in a central location (bug 74// 1375896). 75const DB_URL_LENGTH_MAX = 65536; 76const DB_TITLE_LENGTH_MAX = 4096; 77const DB_DESCRIPTION_LENGTH_MAX = 256; 78 79const SQLITE_MAX_VARIABLE_NUMBER = 999; 80 81// The current mirror database schema version. Bump for migrations, then add 82// migration code to `migrateMirrorSchema`. 83const MIRROR_SCHEMA_VERSION = 1; 84 85// Use a shared jankYielder in these functions 86XPCOMUtils.defineLazyGetter(this, "maybeYield", () => Async.jankYielder()); 87function yieldingIterator(collection) { 88 return Async.yieldingIterator(collection, maybeYield); 89} 90 91/** 92 * A mirror maintains a copy of the complete tree as stored on the Sync server. 93 * It is persistent. 94 * 95 * The mirror schema is a hybrid of how Sync and Places represent bookmarks. 96 * The `items` table contains item attributes (title, kind, description, 97 * URL, etc.), while the `structure` table stores parent-child relationships and 98 * position. This is similar to how iOS encodes "value" and "structure" state, 99 * though we handle these differently when merging. See `BookmarkMerger` for 100 * details. 101 * 102 * There's no guarantee that the remote state is consistent. We might be missing 103 * parents or children, or a bookmark and its parent might disagree about where 104 * it belongs. This means we need a strategy to handle missing parents and 105 * children. 106 * 107 * We treat the `children` of the last parent we see as canonical, and ignore 108 * the child's `parentid` entirely. We also ignore missing children, and 109 * temporarily reparent bookmarks with missing parents to "unfiled". When we 110 * eventually see the missing items, either during a later sync or as part of 111 * repair, we'll fill in the mirror's gaps and fix up the local tree. 112 * 113 * During merging, we won't intentionally try to fix inconsistencies on the 114 * server, and opt to build as complete a tree as we can from the remote state, 115 * even if we diverge from what's in the mirror. See bug 1433512 for context. 116 * 117 * If a sync is interrupted, we resume downloading from the server collection 118 * last modified time, or the server last modified time of the most recent 119 * record if newer. New incoming records always replace existing records in the 120 * mirror. 121 * 122 * We delete the mirror database on client reset, including when the sync ID 123 * changes on the server, and when the user is node reassigned, disables the 124 * bookmarks engine, or signs out. 125 */ 126class SyncedBookmarksMirror { 127 constructor(db, { recordTelemetryEvent, finalizeAt = 128 AsyncShutdown.profileBeforeChange } = {}) { 129 this.db = db; 130 this.recordTelemetryEvent = recordTelemetryEvent; 131 132 // Automatically close the database connection on shutdown. 133 this.finalizeAt = finalizeAt; 134 this.finalizeBound = () => this.finalize(); 135 this.finalizeAt.addBlocker("SyncedBookmarksMirror: finalize", 136 this.finalizeBound); 137 } 138 139 /** 140 * Sets up the mirror database connection and upgrades the mirror to the 141 * newest schema version. Automatically recreates the mirror if it's corrupt; 142 * throws on failure. 143 * 144 * @param {String} options.path 145 * The full path to the mirror database file. 146 * @param {Function} options.recordTelemetryEvent 147 * A function with the signature `(object: String, method: String, 148 * value: String?, extra: Object?)`, used to emit telemetry events. 149 * @param {AsyncShutdown.Barrier} [options.finalizeAt] 150 * A shutdown phase, barrier, or barrier client that should 151 * automatically finalize the mirror when triggered. Exposed for 152 * testing. 153 * @return {SyncedBookmarksMirror} 154 * A mirror ready for use. 155 */ 156 static async open(options) { 157 let db = await Sqlite.cloneStorageConnection({ 158 connection: PlacesUtils.history.DBConnection, 159 readOnly: false, 160 }); 161 try { 162 try { 163 await db.execute(`ATTACH :mirrorPath AS mirror`, 164 { mirrorPath: options.path }); 165 } catch (ex) { 166 if (ex.errors && isDatabaseCorrupt(ex.errors[0])) { 167 MirrorLog.warn("Error attaching mirror to Places; removing and " + 168 "recreating mirror", ex); 169 options.recordTelemetryEvent("mirror", "open", "error", 170 { why: "corrupt" }); 171 await OS.File.remove(options.path); 172 await db.execute(`ATTACH :mirrorPath AS mirror`, 173 { mirrorPath: options.path }); 174 } else { 175 MirrorLog.warn("Unrecoverable error attaching mirror to Places", ex); 176 throw ex; 177 } 178 } 179 await db.execute(`PRAGMA foreign_keys = ON`); 180 await db.executeTransaction(async function() { 181 await migrateMirrorSchema(db); 182 await initializeTempMirrorEntities(db); 183 }); 184 } catch (ex) { 185 options.recordTelemetryEvent("mirror", "open", "error", 186 { why: "initialize" }); 187 await db.close(); 188 throw ex; 189 } 190 return new SyncedBookmarksMirror(db, options); 191 } 192 193 /** 194 * Returns the newer of the bookmarks collection last modified time, or the 195 * server modified time of the newest record. The bookmarks engine uses this 196 * timestamp as the "high water mark" for all downloaded records. Each sync 197 * downloads and stores records that are strictly newer than this time. 198 * 199 * @return {Number} 200 * The high water mark time, in seconds. 201 */ 202 async getCollectionHighWaterMark() { 203 // The first case, where we have records with server modified times newer 204 // than the collection last modified time, occurs when a sync is interrupted 205 // before we call `setCollectionLastModified`. We subtract one second, the 206 // maximum time precision guaranteed by the server, so that we don't miss 207 // other records with the same time as the newest one we downloaded. 208 let rows = await this.db.execute(` 209 SELECT MAX( 210 IFNULL((SELECT MAX(serverModified) - 1000 FROM items), 0), 211 IFNULL((SELECT CAST(value AS INTEGER) FROM meta 212 WHERE key = :modifiedKey), 0) 213 ) AS highWaterMark`, 214 { modifiedKey: SyncedBookmarksMirror.META.MODIFIED }); 215 let highWaterMark = rows[0].getResultByName("highWaterMark"); 216 return highWaterMark / 1000; 217 } 218 219 /** 220 * Updates the bookmarks collection last modified time. Note that this may 221 * be newer than the modified time of the most recent record. 222 * 223 * @param {Number|String} lastModifiedSeconds 224 * The collection last modified time, in seconds. 225 */ 226 async setCollectionLastModified(lastModifiedSeconds) { 227 let lastModified = lastModifiedSeconds * 1000; 228 if (!Number.isFinite(lastModified)) { 229 throw new TypeError("Invalid collection last modified time"); 230 } 231 await this.db.executeBeforeShutdown( 232 "SyncedBookmarksMirror: setCollectionLastModified", 233 db => db.execute(` 234 REPLACE INTO meta(key, value) 235 VALUES(:modifiedKey, :lastModified)`, 236 { modifiedKey: SyncedBookmarksMirror.META.MODIFIED, lastModified }) 237 ); 238 } 239 240 /** 241 * Stores incoming or uploaded Sync records in the mirror. Rejects if any 242 * records are invalid. 243 * 244 * @param {PlacesItem[]} records 245 * Sync records to store in the mirror. 246 * @param {Boolean} [options.needsMerge] 247 * Indicates if the records were changed remotely since the last sync, 248 * and should be merged into the local tree. This option is set to 249 * `true` for incoming records, and `false` for successfully uploaded 250 * records. Tests can also pass `false` to set up an existing mirror. 251 */ 252 async store(records, { needsMerge = true } = {}) { 253 let options = { needsMerge }; 254 await this.db.executeBeforeShutdown( 255 "SyncedBookmarksMirror: store", 256 db => db.executeTransaction(async () => { 257 for await (let record of yieldingIterator(records)) { 258 switch (record.type) { 259 case "bookmark": 260 MirrorLog.trace("Storing bookmark in mirror", record.cleartext); 261 await this.storeRemoteBookmark(record, options); 262 continue; 263 264 case "query": 265 MirrorLog.trace("Storing query in mirror", record.cleartext); 266 await this.storeRemoteQuery(record, options); 267 continue; 268 269 case "folder": 270 MirrorLog.trace("Storing folder in mirror", record.cleartext); 271 await this.storeRemoteFolder(record, options); 272 continue; 273 274 case "livemark": 275 MirrorLog.trace("Storing livemark in mirror", record.cleartext); 276 await this.storeRemoteLivemark(record, options); 277 continue; 278 279 case "separator": 280 MirrorLog.trace("Storing separator in mirror", record.cleartext); 281 await this.storeRemoteSeparator(record, options); 282 continue; 283 284 default: 285 if (record.deleted) { 286 MirrorLog.trace("Storing tombstone in mirror", 287 record.cleartext); 288 await this.storeRemoteTombstone(record, options); 289 continue; 290 } 291 } 292 MirrorLog.warn("Ignoring record with unknown type", record.type); 293 this.recordTelemetryEvent("mirror", "ignore", "unknown", 294 { why: "kind" }); 295 } 296 }) 297 ); 298 } 299 300 /** 301 * Builds a complete merged tree from the local and remote trees, resolves 302 * value and structure conflicts, dedupes local items, applies the merged 303 * tree back to Places, and notifies observers about the changes. 304 * 305 * Merging and application happen in a transaction, meaning code that uses the 306 * main Places connection, including the UI, will fail to write to the 307 * database until the transaction commits. Asynchronous consumers will retry 308 * on `SQLITE_BUSY`; synchronous consumers will fail after waiting for 100ms. 309 * See bug 1305563, comment 122 for details. 310 * 311 * @param {Number} [options.localTimeSeconds] 312 * The current local time, in seconds. 313 * @param {Number} [options.remoteTimeSeconds] 314 * The current server time, in seconds. 315 * @param {String[]} [options.weakUpload] 316 * GUIDs of bookmarks to weakly upload. 317 * @return {Object.<String, BookmarkChangeRecord>} 318 * A changeset containing locally changed and reconciled records to 319 * upload to the server, and to store in the mirror once upload 320 * succeeds. 321 */ 322 async apply({ localTimeSeconds = Date.now() / 1000, 323 remoteTimeSeconds = 0, 324 weakUpload = [] } = {}) { 325 let hasChanges = weakUpload.length > 0 || (await this.hasChanges()); 326 if (!hasChanges) { 327 MirrorLog.debug("No changes detected in both mirror and Places"); 328 return {}; 329 } 330 // We intentionally don't use `executeBeforeShutdown` in this function, 331 // since merging can take a while for large trees, and we don't want to 332 // block shutdown. Since all new items are in the mirror, we'll just try 333 // to merge again on the next sync. 334 let { missingParents, missingChildren } = await this.fetchRemoteOrphans(); 335 if (missingParents.length) { 336 MirrorLog.warn("Temporarily reparenting remote items with missing " + 337 "parents to unfiled", missingParents); 338 this.recordTelemetryEvent("mirror", "orphans", "parents", 339 { count: String(missingParents.length) }); 340 } 341 if (missingChildren.length) { 342 MirrorLog.warn("Remote tree missing items", missingChildren); 343 this.recordTelemetryEvent("mirror", "orphans", "children", 344 { count: String(missingChildren.length) }); 345 } 346 347 let { missingLocal, missingRemote, wrongSyncStatus } = 348 await this.fetchInconsistencies(); 349 if (missingLocal.length) { 350 MirrorLog.warn("Remote tree has merged items that don't exist locally", 351 missingLocal); 352 this.recordTelemetryEvent("mirror", "inconsistencies", "local", 353 { count: String(missingLocal.length) }); 354 } 355 if (missingRemote.length) { 356 MirrorLog.warn("Local tree has synced items that don't exist remotely", 357 missingRemote); 358 this.recordTelemetryEvent("mirror", "inconsistencies", "remote", 359 { count: String(missingRemote.length) }); 360 } 361 if (wrongSyncStatus.length) { 362 MirrorLog.warn("Local tree has wrong sync statuses for items that " + 363 "exist remotely", wrongSyncStatus); 364 this.recordTelemetryEvent("mirror", "inconsistencies", "syncStatus", 365 { count: String(wrongSyncStatus.length) }); 366 } 367 368 // It's safe to build the remote tree outside the transaction because 369 // `fetchRemoteTree` doesn't join to Places, only Sync writes to the 370 // mirror, and we're holding the Sync lock at this point. 371 MirrorLog.debug("Building remote tree from mirror"); 372 let remoteTree = await this.fetchRemoteTree(remoteTimeSeconds); 373 if (MirrorLog.level <= Log.Level.Trace) { 374 MirrorLog.trace("Built remote tree from mirror\n" + 375 remoteTree.toASCIITreeString()); 376 } 377 378 let observersToNotify = new BookmarkObserverRecorder(this.db); 379 380 let changeRecords = await this.db.executeTransaction(async () => { 381 MirrorLog.debug("Building local tree from Places"); 382 let localTree = await this.fetchLocalTree(localTimeSeconds); 383 if (MirrorLog.level <= Log.Level.Trace) { 384 MirrorLog.trace("Built local tree from Places\n" + 385 localTree.toASCIITreeString()); 386 } 387 388 MirrorLog.debug("Fetching content info for new mirror items"); 389 let newRemoteContents = await this.fetchNewRemoteContents(); 390 391 MirrorLog.debug("Fetching content info for new Places items"); 392 let newLocalContents = await this.fetchNewLocalContents(); 393 394 MirrorLog.debug("Building complete merged tree"); 395 let merger = new BookmarkMerger(localTree, newLocalContents, 396 remoteTree, newRemoteContents); 397 let mergedRoot = await merger.merge(); 398 for (let { value, extra } of merger.telemetryEvents) { 399 this.recordTelemetryEvent("mirror", "merge", value, extra); 400 } 401 402 if (MirrorLog.level <= Log.Level.Trace) { 403 MirrorLog.trace([ 404 "Built new merged tree", 405 mergedRoot.toASCIITreeString(), 406 ...merger.deletionsToStrings(), 407 ].join("\n")); 408 } 409 410 // The merged tree should know about all items mentioned in the local 411 // and remote trees. Otherwise, it's incomplete, and we'll corrupt 412 // Places or lose data on the server if we try to apply it. 413 if (!await merger.subsumes(localTree)) { 414 throw new SyncedBookmarksMirror.ConsistencyError( 415 "Merged tree doesn't mention all items from local tree"); 416 } 417 if (!await merger.subsumes(remoteTree)) { 418 throw new SyncedBookmarksMirror.ConsistencyError( 419 "Merged tree doesn't mention all items from remote tree"); 420 } 421 422 MirrorLog.debug("Applying merged tree"); 423 let localDeletions = Array.from(merger.deleteLocally).map(guid => 424 ({ guid, level: localTree.levelForGuid(guid) }) 425 ); 426 let remoteDeletions = Array.from(merger.deleteRemotely); 427 await this.updateLocalItemsInPlaces(mergedRoot, localDeletions, 428 remoteDeletions); 429 430 // At this point, the database is consistent, and we can fetch info to 431 // pass to observers. Note that we can't fetch observer info in the 432 // triggers above, because the structure might not be complete yet. An 433 // incomplete structure might cause us to miss or record wrong parents and 434 // positions. 435 436 MirrorLog.debug("Recording observer notifications"); 437 await this.noteObserverChanges(observersToNotify); 438 439 MirrorLog.debug("Staging locally changed items for upload"); 440 await this.stageItemsToUpload(weakUpload); 441 442 MirrorLog.debug("Fetching records for local items to upload"); 443 let changeRecords = await this.fetchLocalChangeRecords(); 444 445 await this.db.execute(`DELETE FROM mergeStates`); 446 await this.db.execute(`DELETE FROM itemsAdded`); 447 await this.db.execute(`DELETE FROM guidsChanged`); 448 await this.db.execute(`DELETE FROM itemsChanged`); 449 await this.db.execute(`DELETE FROM itemsRemoved`); 450 await this.db.execute(`DELETE FROM itemsMoved`); 451 await this.db.execute(`DELETE FROM annosChanged`); 452 await this.db.execute(`DELETE FROM itemsToWeaklyReupload`); 453 await this.db.execute(`DELETE FROM itemsToUpload`); 454 455 return changeRecords; 456 }, this.db.TRANSACTION_IMMEDIATE); 457 458 MirrorLog.debug("Replaying recorded observer notifications"); 459 try { 460 await observersToNotify.notifyAll(); 461 } catch (ex) { 462 MirrorLog.error("Error notifying Places observers", ex); 463 } 464 465 return changeRecords; 466 } 467 468 /** 469 * Discards the mirror contents. This is called when the user is node 470 * reassigned, disables the bookmarks engine, or signs out. 471 */ 472 async reset() { 473 await this.db.executeBeforeShutdown( 474 "SyncedBookmarksMirror: reset", 475 async function(db) { 476 await db.executeTransaction(async function() { 477 await db.execute(`DELETE FROM meta`); 478 await db.execute(`DELETE FROM structure`); 479 await db.execute(`DELETE FROM items`); 480 await db.execute(`DELETE FROM urls`); 481 482 // Since we need to reset the modified times for the syncable roots, 483 // we simply delete and recreate them. 484 await createMirrorRoots(db); 485 }); 486 } 487 ); 488 } 489 490 /** 491 * Fetches the GUIDs of all items in the remote tree that need to be merged 492 * into the local tree. 493 * 494 * @return {String[]} 495 * Remotely changed GUIDs that need to be merged into Places. 496 */ 497 async fetchUnmergedGuids() { 498 let rows = await this.db.execute(`SELECT guid FROM items WHERE needsMerge`); 499 return rows.map(row => row.getResultByName("guid")); 500 } 501 502 async storeRemoteBookmark(record, { needsMerge }) { 503 let guid = validateGuid(record.id); 504 if (!guid) { 505 MirrorLog.warn("Ignoring bookmark with invalid ID", record.id); 506 this.recordTelemetryEvent("mirror", "ignore", "bookmark", 507 { why: "id" }); 508 return; 509 } 510 511 let url = validateURL(record.bmkUri); 512 if (!url) { 513 MirrorLog.trace("Ignoring bookmark ${guid} with invalid URL ${url}", 514 { guid, url: record.bmkUri }); 515 this.recordTelemetryEvent("mirror", "ignore", "bookmark", 516 { why: "url" }); 517 return; 518 } 519 520 await this.maybeStoreRemoteURL(url); 521 522 let serverModified = determineServerModified(record); 523 let dateAdded = determineDateAdded(record); 524 let title = validateTitle(record.title); 525 let keyword = validateKeyword(record.keyword); 526 let description = validateDescription(record.description); 527 let loadInSidebar = record.loadInSidebar === true ? "1" : null; 528 529 await this.db.executeCached(` 530 REPLACE INTO items(guid, serverModified, needsMerge, kind, 531 dateAdded, title, keyword, 532 urlId, description, loadInSidebar) 533 VALUES(:guid, :serverModified, :needsMerge, :kind, 534 :dateAdded, NULLIF(:title, ""), :keyword, 535 (SELECT id FROM urls 536 WHERE hash = hash(:url) AND 537 url = :url), 538 :description, :loadInSidebar)`, 539 { guid, serverModified, needsMerge, 540 kind: SyncedBookmarksMirror.KIND.BOOKMARK, dateAdded, title, keyword, 541 url: url.href, description, loadInSidebar }); 542 543 let tags = record.tags; 544 if (tags && Array.isArray(tags)) { 545 for (let rawTag of tags) { 546 let tag = validateTag(rawTag); 547 if (!tag) { 548 continue; 549 } 550 await this.db.executeCached(` 551 INSERT INTO tags(itemId, tag) 552 SELECT id, :tag FROM items 553 WHERE guid = :guid`, 554 { tag, guid }); 555 } 556 } 557 } 558 559 async storeRemoteQuery(record, { needsMerge }) { 560 let guid = validateGuid(record.id); 561 if (!guid) { 562 MirrorLog.warn("Ignoring query with invalid ID", record.id); 563 this.recordTelemetryEvent("mirror", "ignore", "query", 564 { why: "id" }); 565 return; 566 } 567 568 let url = validateURL(record.bmkUri); 569 if (!url) { 570 MirrorLog.trace("Ignoring query ${guid} with invalid URL ${url}", 571 { guid, url: record.bmkUri }); 572 this.recordTelemetryEvent("mirror", "ignore", "query", 573 { why: "url" }); 574 return; 575 } 576 577 await this.maybeStoreRemoteURL(url); 578 579 let serverModified = determineServerModified(record); 580 let dateAdded = determineDateAdded(record); 581 let title = validateTitle(record.title); 582 let tagFolderName = validateTag(record.folderName); 583 let description = validateDescription(record.description); 584 let smartBookmarkName = typeof record.queryId == "string" ? 585 record.queryId : null; 586 587 await this.db.executeCached(` 588 REPLACE INTO items(guid, serverModified, needsMerge, kind, 589 dateAdded, title, tagFolderName, 590 urlId, description, smartBookmarkName) 591 VALUES(:guid, :serverModified, :needsMerge, :kind, 592 :dateAdded, NULLIF(:title, ""), :tagFolderName, 593 (SELECT id FROM urls 594 WHERE hash = hash(:url) AND 595 url = :url), 596 :description, :smartBookmarkName)`, 597 { guid, serverModified, needsMerge, 598 kind: SyncedBookmarksMirror.KIND.QUERY, dateAdded, title, tagFolderName, 599 url: url.href, description, smartBookmarkName }); 600 } 601 602 async storeRemoteFolder(record, { needsMerge }) { 603 let guid = validateGuid(record.id); 604 if (!guid) { 605 MirrorLog.warn("Ignoring folder with invalid ID", record.id); 606 this.recordTelemetryEvent("mirror", "ignore", "folder", 607 { why: "id" }); 608 return; 609 } 610 if (guid == PlacesUtils.bookmarks.rootGuid) { 611 // The Places root shouldn't be synced at all. 612 MirrorLog.warn("Ignoring Places root record", record.cleartext); 613 this.recordTelemetryEvent("mirror", "ignore", "folder", 614 { why: "root" }); 615 return; 616 } 617 618 let serverModified = determineServerModified(record); 619 let dateAdded = determineDateAdded(record); 620 let title = validateTitle(record.title); 621 let description = validateDescription(record.description); 622 623 await this.db.executeCached(` 624 REPLACE INTO items(guid, serverModified, needsMerge, kind, 625 dateAdded, title, description) 626 VALUES(:guid, :serverModified, :needsMerge, :kind, 627 :dateAdded, NULLIF(:title, ""), 628 :description)`, 629 { guid, serverModified, needsMerge, kind: SyncedBookmarksMirror.KIND.FOLDER, 630 dateAdded, title, description }); 631 632 let children = record.children; 633 if (children && Array.isArray(children)) { 634 for (let position = 0; position < children.length; ++position) { 635 await maybeYield(); 636 let childRecordId = children[position]; 637 let childGuid = validateGuid(childRecordId); 638 if (!childGuid) { 639 MirrorLog.warn("Ignoring child of folder ${parentGuid} with " + 640 "invalid ID ${childRecordId}", { parentGuid: guid, 641 childRecordId }); 642 this.recordTelemetryEvent("mirror", "ignore", "child", 643 { why: "id" }); 644 continue; 645 } 646 await this.db.executeCached(` 647 REPLACE INTO structure(guid, parentGuid, position) 648 VALUES(:childGuid, :parentGuid, :position)`, 649 { childGuid, parentGuid: guid, position }); 650 } 651 } 652 } 653 654 async storeRemoteLivemark(record, { needsMerge }) { 655 let guid = validateGuid(record.id); 656 if (!guid) { 657 MirrorLog.warn("Ignoring livemark with invalid ID", record.id); 658 this.recordTelemetryEvent("mirror", "ignore", "livemark", 659 { why: "id" }); 660 return; 661 } 662 663 let feedURL = validateURL(record.feedUri); 664 if (!feedURL) { 665 MirrorLog.trace("Ignoring livemark ${guid} with invalid feed URL ${url}", 666 { guid, url: record.feedUri }); 667 this.recordTelemetryEvent("mirror", "ignore", "livemark", 668 { why: "feed" }); 669 return; 670 } 671 672 let serverModified = determineServerModified(record); 673 let dateAdded = determineDateAdded(record); 674 let title = validateTitle(record.title); 675 let description = validateDescription(record.description); 676 let siteURL = validateURL(record.siteUri); 677 678 await this.db.executeCached(` 679 REPLACE INTO items(guid, serverModified, needsMerge, kind, dateAdded, 680 title, description, feedURL, siteURL) 681 VALUES(:guid, :serverModified, :needsMerge, :kind, :dateAdded, 682 NULLIF(:title, ""), :description, :feedURL, :siteURL)`, 683 { guid, serverModified, needsMerge, 684 kind: SyncedBookmarksMirror.KIND.LIVEMARK, 685 dateAdded, title, description, feedURL: feedURL.href, 686 siteURL: siteURL ? siteURL.href : null }); 687 } 688 689 async storeRemoteSeparator(record, { needsMerge }) { 690 let guid = validateGuid(record.id); 691 if (!guid) { 692 MirrorLog.warn("Ignoring separator with invalid ID", record.id); 693 this.recordTelemetryEvent("mirror", "ignore", "separator", 694 { why: "id" }); 695 return; 696 } 697 698 let serverModified = determineServerModified(record); 699 let dateAdded = determineDateAdded(record); 700 701 await this.db.executeCached(` 702 REPLACE INTO items(guid, serverModified, needsMerge, kind, 703 dateAdded) 704 VALUES(:guid, :serverModified, :needsMerge, :kind, 705 :dateAdded)`, 706 { guid, serverModified, needsMerge, kind: SyncedBookmarksMirror.KIND.SEPARATOR, 707 dateAdded }); 708 } 709 710 async storeRemoteTombstone(record, { needsMerge }) { 711 let guid = validateGuid(record.id); 712 if (!guid) { 713 MirrorLog.warn("Ignoring tombstone with invalid ID", record.id); 714 this.recordTelemetryEvent("mirror", "ignore", "tombstone", 715 { why: "id" }); 716 return; 717 } 718 719 if (PlacesUtils.bookmarks.userContentRoots.includes(guid)) { 720 MirrorLog.warn("Ignoring tombstone for syncable root", guid); 721 this.recordTelemetryEvent("mirror", "ignore", "tombstone", 722 { why: "root" }); 723 return; 724 } 725 726 await this.db.executeCached(` 727 REPLACE INTO items(guid, serverModified, needsMerge, isDeleted) 728 VALUES(:guid, :serverModified, :needsMerge, 1)`, 729 { guid, serverModified: determineServerModified(record), needsMerge }); 730 } 731 732 async maybeStoreRemoteURL(url) { 733 await this.db.executeCached(` 734 INSERT OR IGNORE INTO urls(guid, url, hash, revHost) 735 VALUES(IFNULL((SELECT guid FROM urls 736 WHERE hash = hash(:url) AND 737 url = :url), 738 GENERATE_GUID()), :url, hash(:url), :revHost)`, 739 { url: url.href, revHost: PlacesUtils.getReversedHost(url) }); 740 } 741 742 async fetchRemoteOrphans() { 743 let infos = { 744 missingParents: [], 745 missingChildren: [], 746 }; 747 748 let orphanRows = await this.db.execute(` 749 SELECT v.guid AS guid, 1 AS missingParent, 0 AS missingChild 750 FROM items v 751 LEFT JOIN structure s ON s.guid = v.guid 752 WHERE NOT v.isDeleted AND 753 s.guid IS NULL 754 UNION ALL 755 SELECT s.guid AS guid, 0 AS missingParent, 1 AS missingChild 756 FROM structure s 757 LEFT JOIN items v ON v.guid = s.guid 758 WHERE v.guid IS NULL`); 759 760 for await (let row of yieldingIterator(orphanRows)) { 761 let guid = row.getResultByName("guid"); 762 let missingParent = row.getResultByName("missingParent"); 763 if (missingParent) { 764 infos.missingParents.push(guid); 765 } 766 let missingChild = row.getResultByName("missingChild"); 767 if (missingChild) { 768 infos.missingChildren.push(guid); 769 } 770 } 771 772 return infos; 773 } 774 775 /** 776 * Checks the sync statuses of all items for consistency. All merged items in 777 * the remote tree should exist as either items or tombstones in the local 778 * tree, and all NORMAL items and tombstones in the local tree should exist 779 * in the remote tree, if the mirror has any merged items. 780 * 781 * @return {Object.<String, String[]>} 782 * An object containing GUIDs for each problem type: 783 * - `missingLocal`: Merged items in the remote tree that aren't 784 * mentioned in the local tree. 785 * - `missingRemote`: NORMAL items in the local tree that aren't 786 * mentioned in the remote tree. 787 */ 788 async fetchInconsistencies() { 789 let infos = { 790 missingLocal: [], 791 missingRemote: [], 792 wrongSyncStatus: [], 793 }; 794 795 let problemRows = await this.db.execute(` 796 SELECT v.guid, 1 AS missingLocal, 0 AS missingRemote, 0 AS wrongSyncStatus 797 FROM items v 798 LEFT JOIN moz_bookmarks b ON b.guid = v.guid 799 LEFT JOIN moz_bookmarks_deleted d ON d.guid = v.guid 800 WHERE NOT v.needsMerge AND 801 NOT v.isDeleted AND 802 b.guid IS NULL AND 803 d.guid IS NULL 804 UNION ALL 805 SELECT b.guid, 0 AS missingLocal, 1 AS missingRemote, 0 AS wrongSyncStatus 806 FROM moz_bookmarks b 807 LEFT JOIN items v ON v.guid = b.guid 808 WHERE EXISTS(SELECT 1 FROM items 809 WHERE NOT needsMerge AND 810 guid <> :rootGuid) AND 811 b.syncStatus = :syncStatus AND 812 v.guid IS NULL 813 UNION ALL 814 SELECT d.guid, 0 AS missingLocal, 1 AS missingRemote, 0 AS wrongSyncStatus 815 FROM moz_bookmarks_deleted d 816 LEFT JOIN items v ON v.guid = d.guid 817 WHERE EXISTS(SELECT 1 FROM items 818 WHERE NOT needsMerge AND 819 guid <> :rootGuid) AND 820 v.guid IS NULL 821 UNION ALL 822 SELECT b.guid, 0 AS missingLocal, 0 AS missingRemote, 1 AS wrongSyncStatus 823 FROM moz_bookmarks b 824 JOIN items v ON v.guid = b.guid 825 WHERE EXISTS(SELECT 1 FROM items 826 WHERE NOT needsMerge AND 827 guid <> :rootGuid) AND 828 b.guid <> :rootGuid AND 829 b.syncStatus <> :syncStatus`, 830 { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL, 831 rootGuid: PlacesUtils.bookmarks.rootGuid }); 832 833 for await (let row of yieldingIterator(problemRows)) { 834 let guid = row.getResultByName("guid"); 835 let missingLocal = row.getResultByName("missingLocal"); 836 if (missingLocal) { 837 infos.missingLocal.push(guid); 838 } 839 let missingRemote = row.getResultByName("missingRemote"); 840 if (missingRemote) { 841 infos.missingRemote.push(guid); 842 } 843 let wrongSyncStatus = row.getResultByName("wrongSyncStatus"); 844 if (wrongSyncStatus) { 845 infos.wrongSyncStatus.push(guid); 846 } 847 } 848 849 return infos; 850 } 851 852 /* 853 * Checks if Places or mirror have any unsynced/unmerged changes. 854 * 855 * @return {Boolean} 856 * `true` if something has changed. 857 */ 858 async hasChanges() { 859 // In the first subquery, we check incoming items with needsMerge = true 860 // except the tombstones who don't correspond to any local bookmark because 861 // we don't store them yet, hence never "merged" (see bug 1343103). 862 let rows = await this.db.execute(` 863 SELECT 864 EXISTS ( 865 SELECT 1 866 FROM items v 867 LEFT JOIN moz_bookmarks b ON v.guid = b.guid 868 WHERE v.needsMerge AND 869 (NOT v.isDeleted OR b.guid NOT NULL) 870 ) OR EXISTS ( 871 WITH RECURSIVE 872 syncedItems(id, syncChangeCounter) AS ( 873 SELECT b.id, b.syncChangeCounter FROM moz_bookmarks b 874 WHERE b.guid IN ('menu________', 'toolbar_____', 'unfiled_____', 875 'mobile______') 876 UNION ALL 877 SELECT b.id, b.syncChangeCounter FROM moz_bookmarks b 878 JOIN syncedItems s ON b.parent = s.id 879 ) 880 SELECT 1 881 FROM syncedItems 882 WHERE syncChangeCounter > 0 883 ) OR EXISTS ( 884 SELECT 1 885 FROM moz_bookmarks_deleted 886 ) 887 AS hasChanges 888 `); 889 return !!rows[0].getResultByName("hasChanges"); 890 } 891 892 /** 893 * Builds a fully rooted, consistent tree from the items and tombstones in the 894 * mirror. 895 * 896 * @param {Number} remoteTimeSeconds 897 * The current server time, in seconds. 898 * @return {BookmarkTree} 899 * The remote bookmark tree. 900 */ 901 async fetchRemoteTree(remoteTimeSeconds) { 902 let remoteTree = new BookmarkTree(BookmarkNode.root()); 903 let startTime = Cu.now(); 904 905 // First, build a flat mapping of parents to children. The `LEFT JOIN` 906 // includes items orphaned by an interrupted upload on another device. 907 // We keep the orphans in "unfiled" until the other device returns and 908 // uploads the missing parent. 909 let itemRows = await this.db.execute(` 910 SELECT v.guid, IFNULL(s.parentGuid, :unfiledGuid) AS parentGuid, 911 IFNULL(s.position, -1) AS position, v.serverModified, v.kind, 912 v.needsMerge 913 FROM items v 914 LEFT JOIN structure s ON s.guid = v.guid 915 WHERE NOT v.isDeleted AND 916 v.guid <> :rootGuid 917 ORDER BY parentGuid, position = -1, position, v.guid`, 918 { rootGuid: PlacesUtils.bookmarks.rootGuid, 919 unfiledGuid: PlacesUtils.bookmarks.unfiledGuid }); 920 921 let pseudoTree = new Map(); 922 for await (let row of yieldingIterator(itemRows)) { 923 let parentGuid = row.getResultByName("parentGuid"); 924 let node = BookmarkNode.fromRemoteRow(row, remoteTimeSeconds); 925 if (pseudoTree.has(parentGuid)) { 926 let nodes = pseudoTree.get(parentGuid); 927 nodes.push(node); 928 } else { 929 pseudoTree.set(parentGuid, [node]); 930 } 931 } 932 933 // Second, build a complete tree from the pseudo-tree. We could do these 934 // two steps in SQL, but it's extremely inefficient. An equivalent 935 // recursive query, with joins in the base and recursive clauses, takes 936 // 10 seconds for a mirror with 5k items. Building the pseudo-tree and 937 // the pseudo-tree and recursing in JS takes 30ms for 5k items. 938 // (Note: Timing was done before adding maybeYield calls) 939 await inflateTree(remoteTree, pseudoTree, PlacesUtils.bookmarks.rootGuid); 940 941 // Note tombstones for remotely deleted items. 942 let tombstoneRows = await this.db.execute(` 943 SELECT guid FROM items 944 WHERE isDeleted AND 945 needsMerge`); 946 947 for await (let row of yieldingIterator(tombstoneRows)) { 948 let guid = row.getResultByName("guid"); 949 remoteTree.noteDeleted(guid); 950 } 951 952 let elapsedTime = Cu.now() - startTime; 953 let totalRows = itemRows.length + tombstoneRows.length; 954 this.recordTelemetryEvent("mirror", "fetch", "remoteTree", 955 { time: String(elapsedTime), 956 count: String(totalRows) }); 957 958 return remoteTree; 959 } 960 961 /** 962 * Fetches content info for all items in the mirror that changed since the 963 * last sync and don't exist locally. 964 * 965 * @return {Map.<String, BookmarkContent>} 966 * Changed items in the mirror that don't exist in Places, keyed by 967 * their GUIDs. 968 */ 969 async fetchNewRemoteContents() { 970 let newRemoteContents = new Map(); 971 let startTime = Cu.now(); 972 973 let rows = await this.db.execute(` 974 SELECT v.guid, IFNULL(v.title, "") AS title, u.url, v.smartBookmarkName, 975 IFNULL(s.position, -1) AS position 976 FROM items v 977 LEFT JOIN urls u ON u.id = v.urlId 978 LEFT JOIN structure s ON s.guid = v.guid 979 LEFT JOIN moz_bookmarks b ON b.guid = v.guid 980 WHERE NOT v.isDeleted AND 981 v.needsMerge AND 982 b.guid IS NULL AND 983 IFNULL(s.parentGuid, :unfiledGuid) <> :rootGuid`, 984 { unfiledGuid: PlacesUtils.bookmarks.unfiledGuid, 985 rootGuid: PlacesUtils.bookmarks.rootGuid }); 986 987 for await (let row of yieldingIterator(rows)) { 988 let guid = row.getResultByName("guid"); 989 let content = BookmarkContent.fromRow(row); 990 newRemoteContents.set(guid, content); 991 } 992 993 let elapsedTime = Cu.now() - startTime; 994 this.recordTelemetryEvent("mirror", "fetch", "newRemoteContents", 995 { time: String(elapsedTime), 996 count: String(rows.length) }); 997 998 return newRemoteContents; 999 } 1000 1001 /** 1002 * Builds a fully rooted, consistent tree from the items and tombstones in 1003 * Places. 1004 * 1005 * @param {Number} localTimeSeconds 1006 * The current local time, in seconds. 1007 * @return {BookmarkTree} 1008 * The local bookmark tree. 1009 */ 1010 async fetchLocalTree(localTimeSeconds) { 1011 let localTree = new BookmarkTree(BookmarkNode.root()); 1012 let startTime = Cu.now(); 1013 1014 // This unsightly query collects all descendants and maps their Places types 1015 // to the Sync record kinds. We start with the roots, and work our way down. 1016 // The list of roots in `syncedItems` should be updated if we add new 1017 // syncable roots to Places. 1018 let itemRows = await this.db.execute(` 1019 WITH RECURSIVE 1020 syncedItems(id, level) AS ( 1021 SELECT b.id, 0 AS level FROM moz_bookmarks b 1022 WHERE b.guid IN (:menuGuid, :toolbarGuid, :unfiledGuid, :mobileGuid) 1023 UNION ALL 1024 SELECT b.id, s.level + 1 AS level FROM moz_bookmarks b 1025 JOIN syncedItems s ON s.id = b.parent 1026 ) 1027 SELECT b.id, b.guid, p.guid AS parentGuid, 1028 /* Map Places item types to Sync record kinds. */ 1029 (CASE b.type 1030 WHEN :bookmarkType THEN ( 1031 CASE SUBSTR((SELECT h.url FROM moz_places h 1032 WHERE h.id = b.fk), 1, 6) 1033 /* Queries are bookmarks with a "place:" URL scheme. */ 1034 WHEN 'place:' THEN :queryKind 1035 ELSE :bookmarkKind END) 1036 WHEN :folderType THEN ( 1037 CASE WHEN EXISTS( 1038 /* Livemarks are folders with a feed URL annotation. */ 1039 SELECT 1 FROM moz_items_annos a 1040 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1041 WHERE a.item_id = b.id AND 1042 n.name = :feedURLAnno 1043 ) THEN :livemarkKind 1044 ELSE :folderKind END) 1045 ELSE :separatorKind END) AS kind, 1046 b.lastModified / 1000 AS localModified, b.syncChangeCounter 1047 FROM moz_bookmarks b 1048 JOIN moz_bookmarks p ON p.id = b.parent 1049 JOIN syncedItems s ON s.id = b.id 1050 ORDER BY s.level, b.parent, b.position`, 1051 { menuGuid: PlacesUtils.bookmarks.menuGuid, 1052 toolbarGuid: PlacesUtils.bookmarks.toolbarGuid, 1053 unfiledGuid: PlacesUtils.bookmarks.unfiledGuid, 1054 mobileGuid: PlacesUtils.bookmarks.mobileGuid, 1055 bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK, 1056 queryKind: SyncedBookmarksMirror.KIND.QUERY, 1057 bookmarkKind: SyncedBookmarksMirror.KIND.BOOKMARK, 1058 folderType: PlacesUtils.bookmarks.TYPE_FOLDER, 1059 feedURLAnno: PlacesUtils.LMANNO_FEEDURI, 1060 livemarkKind: SyncedBookmarksMirror.KIND.LIVEMARK, 1061 folderKind: SyncedBookmarksMirror.KIND.FOLDER, 1062 separatorKind: SyncedBookmarksMirror.KIND.SEPARATOR }); 1063 1064 for await (let row of yieldingIterator(itemRows)) { 1065 let parentGuid = row.getResultByName("parentGuid"); 1066 let node = BookmarkNode.fromLocalRow(row, localTimeSeconds); 1067 localTree.insert(parentGuid, node); 1068 } 1069 1070 // Note tombstones for locally deleted items. 1071 let tombstoneRows = await this.db.execute(` 1072 SELECT guid FROM moz_bookmarks_deleted`); 1073 1074 for await (let row of yieldingIterator(tombstoneRows)) { 1075 let guid = row.getResultByName("guid"); 1076 localTree.noteDeleted(guid); 1077 } 1078 1079 let elapsedTime = Cu.now() - startTime; 1080 let totalRows = itemRows.length + tombstoneRows.length; 1081 this.recordTelemetryEvent("mirror", "fetch", "localTree", 1082 { time: String(elapsedTime), 1083 count: String(totalRows) }); 1084 1085 return localTree; 1086 } 1087 1088 /** 1089 * Fetches content info for all NEW and UNKNOWN local items that don't exist 1090 * in the mirror. We'll try to dedupe them to changed items with similar 1091 * contents and different GUIDs in the mirror. 1092 * 1093 * @return {Map.<String, BookmarkContent>} 1094 * New items in Places that don't exist in the mirror, keyed by their 1095 * GUIDs. 1096 */ 1097 async fetchNewLocalContents() { 1098 let newLocalContents = new Map(); 1099 let startTime = Cu.now(); 1100 1101 let rows = await this.db.execute(` 1102 SELECT b.guid, IFNULL(b.title, "") AS title, h.url, 1103 (SELECT a.content FROM moz_items_annos a 1104 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1105 WHERE a.item_id = b.id AND 1106 n.name = :smartBookmarkAnno) AS smartBookmarkName, 1107 b.position 1108 FROM moz_bookmarks b 1109 JOIN moz_bookmarks p ON p.id = b.parent 1110 LEFT JOIN moz_places h ON h.id = b.fk 1111 LEFT JOIN items v ON v.guid = b.guid 1112 WHERE v.guid IS NULL AND 1113 p.guid <> :rootGuid AND 1114 b.syncStatus <> :syncStatus`, 1115 { smartBookmarkAnno: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO, 1116 rootGuid: PlacesUtils.bookmarks.rootGuid, 1117 syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL }); 1118 1119 for await (let row of yieldingIterator(rows)) { 1120 let guid = row.getResultByName("guid"); 1121 let content = BookmarkContent.fromRow(row); 1122 newLocalContents.set(guid, content); 1123 } 1124 1125 let elapsedTime = Cu.now() - startTime; 1126 this.recordTelemetryEvent("mirror", "fetch", "newLocalContents", 1127 { time: String(elapsedTime), 1128 count: String(rows.length) }); 1129 1130 return newLocalContents; 1131 } 1132 1133 /** 1134 * Builds a temporary table with the merge states of all nodes in the merged 1135 * tree, rewrites tag queries, and updates Places to match the merged tree. 1136 * 1137 * Conceptually, we examine the merge state of each item, and either keep the 1138 * complete local state, take the complete remote state, or apply a new 1139 * structure state and flag the item for reupload. 1140 * 1141 * Note that we update Places and flag items *before* upload, while iOS 1142 * updates the mirror *after* a successful upload. This simplifies our 1143 * implementation, though we lose idempotent merges. If upload is interrupted, 1144 * the next sync won't distinguish between new merge states from the previous 1145 * sync, and local changes. Since this is how Desktop behaved before 1146 * structured application, that's OK. In the future, we can make this more 1147 * like iOS. 1148 * 1149 * @param {MergedBookmarkNode} mergedRoot 1150 * The root of the merged bookmark tree. 1151 * @param {Object[]} localDeletions 1152 * `{ guid, level }` tuples for items to remove from Places and flag as 1153 * merged. 1154 * @param {String[]} remoteDeletions 1155 * Remotely deleted GUIDs that should be flagged as merged. 1156 */ 1157 async updateLocalItemsInPlaces(mergedRoot, localDeletions, remoteDeletions) { 1158 MirrorLog.debug("Setting up merge states table"); 1159 let mergeStatesParams = Array.from(mergedRoot.mergeStatesParams()); 1160 if (mergeStatesParams.length) { 1161 await this.db.execute(` 1162 INSERT INTO mergeStates(localGuid, mergedGuid, parentGuid, level, 1163 position, valueState, structureState) 1164 VALUES(IFNULL(:localGuid, :mergedGuid), :mergedGuid, :parentGuid, 1165 :level, :position, :valueState, :structureState)`, 1166 mergeStatesParams); 1167 } 1168 1169 MirrorLog.debug("Rewriting tag queries in mirror"); 1170 await this.rewriteRemoteTagQueries(); 1171 1172 MirrorLog.debug("Inserting new URLs into Places"); 1173 await this.db.execute(` 1174 INSERT OR IGNORE INTO moz_places(url, url_hash, rev_host, hidden, 1175 frecency, guid) 1176 SELECT u.url, u.hash, u.revHost, 0, 1177 (CASE v.kind WHEN :queryKind THEN 0 ELSE -1 END), 1178 IFNULL((SELECT h.guid FROM moz_places h 1179 WHERE h.url_hash = u.hash AND 1180 h.url = u.url), u.guid) 1181 FROM items v 1182 JOIN urls u ON u.id = v.urlId 1183 JOIN mergeStates r ON r.mergedGuid = v.guid 1184 WHERE r.valueState = :valueState`, 1185 { queryKind: SyncedBookmarksMirror.KIND.QUERY, 1186 valueState: BookmarkMergeState.TYPE.REMOTE }); 1187 await this.db.execute(`DELETE FROM moz_updatehostsinsert_temp`); 1188 1189 // Deleting from `itemsToMerge` fires the `insertNewLocalItems` and 1190 // `updateExistingLocalItems` triggers. 1191 MirrorLog.debug("Updating value states for local bookmarks"); 1192 await this.db.execute(`DELETE FROM itemsToMerge`); 1193 1194 // Update the structure. The mirror stores structure info in a separate 1195 // table, like iOS, while Places stores structure info on children. We don't 1196 // check the parent's merge state here because our merged tree might 1197 // diverge from the server if we're missing children, or moved children 1198 // without parents to "unfiled". In that case, we *don't* want to reupload 1199 // the new local structure to the server. 1200 MirrorLog.debug("Updating structure states for local bookmarks"); 1201 await this.db.execute(`DELETE FROM structureToMerge`); 1202 1203 MirrorLog.debug("Removing remotely deleted items from Places"); 1204 for (let chunk of PlacesSyncUtils.chunkArray(localDeletions, 1205 SQLITE_MAX_VARIABLE_NUMBER)) { 1206 1207 let guids = chunk.map(({ guid }) => guid); 1208 1209 // Record item removed notifications. 1210 await this.db.execute(` 1211 WITH 1212 guidsWithLevelsToDelete(guid, level) AS ( 1213 VALUES ${chunk.map(({ level }) => `(?, ${level})`).join(",")} 1214 ) 1215 INSERT INTO itemsRemoved(itemId, parentId, position, type, placeId, 1216 guid, parentGuid, level) 1217 SELECT b.id, b.parent, b.position, b.type, b.fk, b.guid, p.guid, 1218 o.level 1219 FROM moz_bookmarks b 1220 JOIN moz_bookmarks p ON p.id = b.parent 1221 JOIN guidsWithLevelsToDelete o ON o.guid = b.guid`, 1222 guids); 1223 1224 // Recalculate frecencies. The `isUntagging` check is a formality, since 1225 // tags shouldn't have annos or tombstones, should not appear in local 1226 // deletions, and should not affect frecency. This can go away with 1227 // bug 1293445. 1228 await this.db.execute(` 1229 UPDATE moz_places SET 1230 frecency = -1 1231 WHERE id IN (SELECT placeId FROM itemsRemoved 1232 WHERE NOT isUntagging)`); 1233 1234 // Remove annos for the deleted items. 1235 await this.db.execute(` 1236 DELETE FROM moz_items_annos 1237 WHERE item_id IN (SELECT itemId FROM itemsRemoved 1238 WHERE NOT isUntagging)`); 1239 1240 // Remove any local tombstones for deleted items. 1241 await this.db.execute(` 1242 DELETE FROM moz_bookmarks_deleted 1243 WHERE guid IN (SELECT guid FROM itemsRemoved)`); 1244 1245 await this.db.execute(` 1246 DELETE FROM moz_bookmarks 1247 WHERE id IN (SELECT itemId FROM itemsRemoved 1248 WHERE NOT isUntagging)`); 1249 1250 // Flag locally deleted items as merged. 1251 await this.db.execute(` 1252 UPDATE items SET 1253 needsMerge = 0 1254 WHERE needsMerge AND 1255 guid IN (SELECT guid FROM itemsRemoved 1256 WHERE NOT isUntagging)`); 1257 } 1258 1259 MirrorLog.debug("Flagging remotely deleted items as merged"); 1260 for (let chunk of PlacesSyncUtils.chunkArray(remoteDeletions, 1261 SQLITE_MAX_VARIABLE_NUMBER)) { 1262 1263 await this.db.execute(` 1264 UPDATE items SET 1265 needsMerge = 0 1266 WHERE needsMerge AND 1267 guid IN (${new Array(chunk.length).fill("?").join(",")})`, 1268 chunk); 1269 } 1270 } 1271 1272 /** 1273 * Creates local tag folders mentioned in remotely changed tag queries, then 1274 * rewrites the query URLs in the mirror to point to the new local folders. 1275 * 1276 * For example, an incoming tag query of, say, "place:type=6&folder=3" means 1277 * it is a query for whatever tag is defined by the local record with id=3 1278 * (and the incoming record has the actual tag in the folderName field). 1279 * We need to ensure that the URL is adjusted so the folder ID refers to 1280 * whatever local folder ID represents that tag. 1281 * 1282 * This can be removed once bug 1293445 lands. 1283 */ 1284 async rewriteRemoteTagQueries() { 1285 // Create local tag folders that don't already exist. This fires the 1286 // `tagLocalPlace` trigger. 1287 await this.db.execute(` 1288 INSERT INTO localTags(tag) 1289 SELECT v.tagFolderName FROM items v 1290 JOIN mergeStates r ON r.mergedGuid = v.guid 1291 WHERE r.valueState = :valueState AND 1292 v.tagFolderName NOT NULL`, 1293 { valueState: BookmarkMergeState.TYPE.REMOTE }); 1294 1295 let queryRows = await this.db.execute(` 1296 SELECT u.id AS urlId, u.url, b.id AS newTagFolderId FROM urls u 1297 JOIN items v ON v.urlId = u.id 1298 JOIN mergeStates r ON r.mergedGuid = v.guid 1299 JOIN moz_bookmarks b ON b.title = v.tagFolderName 1300 JOIN moz_bookmarks p ON p.id = b.parent 1301 WHERE p.guid = :tagsGuid AND 1302 r.valueState = :valueState AND 1303 v.kind = :queryKind AND 1304 v.tagFolderName NOT NULL`, 1305 { tagsGuid: PlacesUtils.bookmarks.tagsGuid, 1306 valueState: BookmarkMergeState.TYPE.REMOTE, 1307 queryKind: SyncedBookmarksMirror.KIND.QUERY }); 1308 1309 let urlsParams = []; 1310 for (let row of queryRows) { 1311 let url = new URL(row.getResultByName("url")); 1312 let tagQueryParams = new URLSearchParams(url.pathname); 1313 let type = Number(tagQueryParams.get("type")); 1314 if (type != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) { 1315 continue; 1316 } 1317 1318 // Rewrite the query URL to point to the new folder. 1319 let newTagFolderId = row.getResultByName("newTagFolderId"); 1320 tagQueryParams.set("folder", newTagFolderId); 1321 1322 let newURLHref = url.protocol + tagQueryParams; 1323 urlsParams.push({ 1324 urlId: row.getResultByName("urlId"), 1325 url: newURLHref, 1326 }); 1327 } 1328 1329 if (urlsParams.length) { 1330 await this.db.execute(` 1331 UPDATE urls SET 1332 url = :url, 1333 hash = hash(:url) 1334 WHERE id = :urlId`, 1335 urlsParams); 1336 } 1337 } 1338 1339 /** 1340 * Records Places observer notifications for removed, added, moved, and 1341 * changed items. 1342 * 1343 * @param {BookmarkObserverRecorder} observersToNotify 1344 */ 1345 async noteObserverChanges(observersToNotify) { 1346 MirrorLog.debug("Recording observer notifications for removed items"); 1347 // `ORDER BY v.level DESC` sorts deleted children before parents, to ensure 1348 // that we update caches in the correct order (bug 1297941). We also order 1349 // by parent and position so that the notifications are well-ordered for 1350 // tests. 1351 let removedItemRows = await this.db.execute(` 1352 SELECT v.itemId AS id, v.parentId, v.parentGuid, v.position, v.type, 1353 h.url, v.guid, v.isUntagging 1354 FROM itemsRemoved v 1355 LEFT JOIN moz_places h ON h.id = v.placeId 1356 ORDER BY v.level DESC, v.parentId, v.position`); 1357 for await (let row of yieldingIterator(removedItemRows)) { 1358 let info = { 1359 id: row.getResultByName("id"), 1360 parentId: row.getResultByName("parentId"), 1361 position: row.getResultByName("position"), 1362 type: row.getResultByName("type"), 1363 urlHref: row.getResultByName("url"), 1364 guid: row.getResultByName("guid"), 1365 parentGuid: row.getResultByName("parentGuid"), 1366 isUntagging: row.getResultByName("isUntagging"), 1367 }; 1368 observersToNotify.noteItemRemoved(info); 1369 } 1370 1371 MirrorLog.debug("Recording observer notifications for changed GUIDs"); 1372 let changedGuidRows = await this.db.execute(` 1373 SELECT b.id, b.lastModified, b.type, b.guid AS newGuid, 1374 c.oldGuid, p.id AS parentId, p.guid AS parentGuid 1375 FROM guidsChanged c 1376 JOIN moz_bookmarks b ON b.id = c.itemId 1377 JOIN moz_bookmarks p ON p.id = b.parent 1378 ORDER BY c.level, p.id, b.position`); 1379 for await (let row of yieldingIterator(changedGuidRows)) { 1380 let info = { 1381 id: row.getResultByName("id"), 1382 lastModified: row.getResultByName("lastModified"), 1383 type: row.getResultByName("type"), 1384 newGuid: row.getResultByName("newGuid"), 1385 oldGuid: row.getResultByName("oldGuid"), 1386 parentId: row.getResultByName("parentId"), 1387 parentGuid: row.getResultByName("parentGuid"), 1388 }; 1389 observersToNotify.noteGuidChanged(info); 1390 } 1391 1392 MirrorLog.debug("Recording observer notifications for new items"); 1393 let newItemRows = await this.db.execute(` 1394 SELECT b.id, p.id AS parentId, b.position, b.type, h.url, 1395 IFNULL(b.title, "") AS title, b.dateAdded, b.guid, 1396 p.guid AS parentGuid, n.isTagging 1397 FROM itemsAdded n 1398 JOIN moz_bookmarks b ON b.guid = n.guid 1399 JOIN moz_bookmarks p ON p.id = b.parent 1400 LEFT JOIN moz_places h ON h.id = b.fk 1401 ORDER BY n.level, p.id, b.position`); 1402 for await (let row of yieldingIterator(newItemRows)) { 1403 let info = { 1404 id: row.getResultByName("id"), 1405 parentId: row.getResultByName("parentId"), 1406 position: row.getResultByName("position"), 1407 type: row.getResultByName("type"), 1408 urlHref: row.getResultByName("url"), 1409 title: row.getResultByName("title"), 1410 dateAdded: row.getResultByName("dateAdded"), 1411 guid: row.getResultByName("guid"), 1412 parentGuid: row.getResultByName("parentGuid"), 1413 isTagging: row.getResultByName("isTagging"), 1414 }; 1415 observersToNotify.noteItemAdded(info); 1416 } 1417 1418 MirrorLog.debug("Recording observer notifications for moved items"); 1419 let movedItemRows = await this.db.execute(` 1420 SELECT b.id, b.guid, b.type, p.id AS newParentId, c.oldParentId, 1421 p.guid AS newParentGuid, c.oldParentGuid, 1422 b.position AS newPosition, c.oldPosition 1423 FROM itemsMoved c 1424 JOIN moz_bookmarks b ON b.id = c.itemId 1425 JOIN moz_bookmarks p ON p.id = b.parent 1426 ORDER BY c.level, newParentId, newPosition`); 1427 for await (let row of yieldingIterator(movedItemRows)) { 1428 let info = { 1429 id: row.getResultByName("id"), 1430 guid: row.getResultByName("guid"), 1431 type: row.getResultByName("type"), 1432 newParentId: row.getResultByName("newParentId"), 1433 oldParentId: row.getResultByName("oldParentId"), 1434 newParentGuid: row.getResultByName("newParentGuid"), 1435 oldParentGuid: row.getResultByName("oldParentGuid"), 1436 newPosition: row.getResultByName("newPosition"), 1437 oldPosition: row.getResultByName("oldPosition"), 1438 }; 1439 observersToNotify.noteItemMoved(info); 1440 } 1441 1442 MirrorLog.debug("Recording observer notifications for changed items"); 1443 let changedItemRows = await this.db.execute(` 1444 SELECT b.id, b.guid, b.lastModified, b.type, 1445 IFNULL(b.title, "") AS newTitle, 1446 IFNULL(c.oldTitle, "") AS oldTitle, 1447 h.url AS newURL, i.url AS oldURL, 1448 p.id AS parentId, p.guid AS parentGuid 1449 FROM itemsChanged c 1450 JOIN moz_bookmarks b ON b.id = c.itemId 1451 JOIN moz_bookmarks p ON p.id = b.parent 1452 LEFT JOIN moz_places h ON h.id = b.fk 1453 LEFT JOIN moz_places i ON i.id = c.oldPlaceId 1454 ORDER BY c.level, p.id, b.position`); 1455 for await (let row of yieldingIterator(changedItemRows)) { 1456 let info = { 1457 id: row.getResultByName("id"), 1458 guid: row.getResultByName("guid"), 1459 lastModified: row.getResultByName("lastModified"), 1460 type: row.getResultByName("type"), 1461 newTitle: row.getResultByName("newTitle"), 1462 oldTitle: row.getResultByName("oldTitle"), 1463 newURLHref: row.getResultByName("newURL"), 1464 oldURLHref: row.getResultByName("oldURL"), 1465 parentId: row.getResultByName("parentId"), 1466 parentGuid: row.getResultByName("parentGuid"), 1467 }; 1468 observersToNotify.noteItemChanged(info); 1469 } 1470 1471 MirrorLog.debug("Recording observer notifications for changed annos"); 1472 let annoRows = await this.db.execute(` 1473 SELECT itemId, annoName, wasRemoved FROM annosChanged 1474 ORDER BY itemId`); 1475 for await (let row of yieldingIterator(annoRows)) { 1476 let id = row.getResultByName("itemId"); 1477 let name = row.getResultByName("annoName"); 1478 if (row.getResultByName("wasRemoved")) { 1479 observersToNotify.noteAnnoRemoved(id, name); 1480 } else { 1481 observersToNotify.noteAnnoSet(id, name); 1482 } 1483 } 1484 1485 MirrorLog.debug("Recording notifications for changed keywords"); 1486 let keywordsChangedRows = await this.db.execute(` 1487 SELECT EXISTS(SELECT 1 FROM itemsAdded WHERE keywordChanged) OR 1488 EXISTS(SELECT 1 FROM itemsChanged WHERE keywordChanged) 1489 AS keywordsChanged`); 1490 observersToNotify.shouldInvalidateKeywords = 1491 !!keywordsChangedRows[0].getResultByName("keywordsChanged"); 1492 } 1493 1494 /** 1495 * Stores a snapshot of all locally changed items in a temporary table for 1496 * upload. This is called from within the merge transaction, to ensure that 1497 * structure changes made during the sync don't cause us to upload an 1498 * inconsistent tree. 1499 * 1500 * For an example of why we use a temporary table instead of reading directly 1501 * from Places, consider a user adding a bookmark, then changing its parent 1502 * folder. We first add the bookmark to the default folder, bump the change 1503 * counter of the new bookmark and the default folder, then trigger a sync. 1504 * Depending on how quickly the user picks the new parent, we might upload 1505 * a record for the default folder, commit the move, then upload the bookmark. 1506 * We'll still upload the new parent on the next sync, but, in the meantime, 1507 * we've introduced a parent-child disagreement. This can also happen if the 1508 * user moves many items between folders. 1509 * 1510 * Conceptually, `itemsToUpload` is a transient "view" of locally changed 1511 * items. The change counter in Places is the persistent record of items that 1512 * we need to upload, so, if upload is interrupted or fails, we'll stage the 1513 * items again on the next sync. 1514 * 1515 * @param {String[]} weakUpload 1516 * GUIDs of bookmarks to weakly upload. 1517 */ 1518 async stageItemsToUpload(weakUpload) { 1519 // Stage explicit weak uploads such as repair responses. 1520 for (let chunk of PlacesSyncUtils.chunkArray(weakUpload, 1521 SQLITE_MAX_VARIABLE_NUMBER)) { 1522 await this.db.execute(` 1523 INSERT INTO itemsToWeaklyReupload(id) 1524 SELECT b.id FROM moz_bookmarks b 1525 WHERE b.guid IN (${new Array(chunk.length).fill("?").join(",")})`, 1526 chunk); 1527 } 1528 1529 // Stage remotely changed items with older local creation dates. These are 1530 // tracked "weakly": if the upload is interrupted or fails, we won't 1531 // reupload the record on the next sync. 1532 await this.db.execute(` 1533 INSERT OR IGNORE INTO itemsToWeaklyReupload(id) 1534 SELECT b.id FROM moz_bookmarks b 1535 JOIN mergeStates r ON r.mergedGuid = b.guid 1536 JOIN items v ON v.guid = r.mergedGuid 1537 WHERE r.valueState = :valueState AND 1538 /* "b.dateAdded" is in microseconds; "v.dateAdded" is in 1539 milliseconds. */ 1540 b.dateAdded / 1000 < v.dateAdded`, 1541 { valueState: BookmarkMergeState.TYPE.REMOTE }); 1542 1543 // Stage remaining locally changed items for upload. 1544 await this.db.execute(` 1545 WITH RECURSIVE 1546 syncedItems(id, level) AS ( 1547 SELECT b.id, 0 AS level FROM moz_bookmarks b 1548 WHERE b.guid IN (:menuGuid, :toolbarGuid, :unfiledGuid, :mobileGuid) 1549 UNION ALL 1550 SELECT b.id, s.level + 1 AS level FROM moz_bookmarks b 1551 JOIN syncedItems s ON s.id = b.parent 1552 ) 1553 INSERT INTO itemsToUpload(id, guid, syncChangeCounter, parentGuid, 1554 parentTitle, dateAdded, type, title, isQuery, 1555 url, tags, description, loadInSidebar, 1556 smartBookmarkName, keyword, feedURL, siteURL, 1557 position) 1558 SELECT b.id, b.guid, b.syncChangeCounter, p.guid, p.title, 1559 b.dateAdded / 1000, b.type, b.title, 1560 IFNULL(SUBSTR(h.url, 1, 6) = 'place:', 0), h.url, 1561 (SELECT GROUP_CONCAT(t.title, ',') FROM moz_bookmarks e 1562 JOIN moz_bookmarks t ON t.id = e.parent 1563 JOIN moz_bookmarks r ON r.id = t.parent 1564 WHERE b.type = :bookmarkType AND 1565 r.guid = :tagsGuid AND 1566 e.fk = h.id), 1567 (SELECT a.content FROM moz_items_annos a 1568 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1569 WHERE b.type IN (:bookmarkType, :folderType) AND 1570 a.item_id = b.id AND 1571 n.name = :descriptionAnno), 1572 IFNULL((SELECT a.content FROM moz_items_annos a 1573 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1574 WHERE a.item_id = b.id AND 1575 n.name = :sidebarAnno), 0), 1576 (SELECT a.content FROM moz_items_annos a 1577 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1578 WHERE a.item_id = b.id AND 1579 n.name = :smartBookmarkAnno), 1580 (SELECT keyword FROM moz_keywords WHERE place_id = h.id), 1581 (SELECT a.content FROM moz_items_annos a 1582 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1583 WHERE b.type = :folderType AND 1584 a.item_id = b.id AND 1585 n.name = :feedURLAnno), 1586 (SELECT a.content FROM moz_items_annos a 1587 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 1588 WHERE b.type = :folderType AND 1589 a.item_id = b.id AND 1590 n.name = :siteURLAnno), 1591 b.position 1592 FROM moz_bookmarks b 1593 JOIN moz_bookmarks p ON p.id = b.parent 1594 JOIN syncedItems s ON s.id = b.id 1595 LEFT JOIN moz_places h ON h.id = b.fk 1596 LEFT JOIN itemsToWeaklyReupload w ON w.id = b.id 1597 WHERE b.syncChangeCounter >= 1 OR 1598 w.id NOT NULL`, 1599 { menuGuid: PlacesUtils.bookmarks.menuGuid, 1600 toolbarGuid: PlacesUtils.bookmarks.toolbarGuid, 1601 unfiledGuid: PlacesUtils.bookmarks.unfiledGuid, 1602 mobileGuid: PlacesUtils.bookmarks.mobileGuid, 1603 bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK, 1604 tagsGuid: PlacesUtils.bookmarks.tagsGuid, 1605 descriptionAnno: PlacesSyncUtils.bookmarks.DESCRIPTION_ANNO, 1606 sidebarAnno: PlacesSyncUtils.bookmarks.SIDEBAR_ANNO, 1607 smartBookmarkAnno: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO, 1608 folderType: PlacesUtils.bookmarks.TYPE_FOLDER, 1609 feedURLAnno: PlacesUtils.LMANNO_FEEDURI, 1610 siteURLAnno: PlacesUtils.LMANNO_SITEURI }); 1611 1612 // Record tag folder names for tag queries. Parsing query URLs one by one 1613 // is inefficient, but queries aren't common today, and we can remove this 1614 // logic entirely once bug 1293445 lands. 1615 let queryRows = await this.db.execute(` 1616 SELECT id, url FROM itemsToUpload 1617 WHERE isQuery`); 1618 1619 let tagFolderNameParams = []; 1620 for (let row of queryRows) { 1621 let url = new URL(row.getResultByName("url")); 1622 let tagQueryParams = new URLSearchParams(url.pathname); 1623 let type = Number(tagQueryParams.get("type")); 1624 if (type == Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) { 1625 continue; 1626 } 1627 let tagFolderId = Number(tagQueryParams.get("folder")); 1628 tagFolderNameParams.push({ 1629 id: row.getResultByName("id"), 1630 tagFolderId, 1631 folderType: PlacesUtils.bookmarks.TYPE_FOLDER, 1632 }); 1633 } 1634 1635 if (tagFolderNameParams.length) { 1636 await this.db.execute(` 1637 UPDATE itemsToUpload SET 1638 tagFolderName = (SELECT b.title FROM moz_bookmarks b 1639 WHERE b.id = :tagFolderId AND 1640 b.type = :folderType) 1641 WHERE id = :id`, tagFolderNameParams); 1642 } 1643 1644 // Record the child GUIDs of locally changed folders, which we use to 1645 // populate the `children` array in the record. 1646 await this.db.execute(` 1647 INSERT INTO structureToUpload(guid, parentId, position) 1648 SELECT b.guid, b.parent, b.position FROM moz_bookmarks b 1649 JOIN itemsToUpload o ON o.id = b.parent`); 1650 1651 // Finally, stage tombstones for deleted items. Ignore conflicts if we have 1652 // tombstones for undeleted items; Places Maintenance should clean these up. 1653 await this.db.execute(` 1654 INSERT OR IGNORE INTO itemsToUpload(guid, syncChangeCounter, isDeleted, 1655 dateAdded) 1656 SELECT guid, 1, 1, dateRemoved / 1000 FROM moz_bookmarks_deleted`); 1657 } 1658 1659 /** 1660 * Inflates Sync records for all staged outgoing items. 1661 * 1662 * @return {Object.<String, BookmarkChangeRecord>} 1663 * A changeset containing Sync record cleartexts for outgoing items 1664 * and tombstones, keyed by their Sync record IDs. 1665 */ 1666 async fetchLocalChangeRecords() { 1667 let changeRecords = {}; 1668 let childRecordIdsByLocalParentId = new Map(); 1669 1670 let childGuidRows = await this.db.execute(` 1671 SELECT parentId, guid FROM structureToUpload 1672 ORDER BY parentId, position`); 1673 1674 for (let row of childGuidRows) { 1675 let localParentId = row.getResultByName("parentId"); 1676 let childRecordId = PlacesSyncUtils.bookmarks.guidToRecordId( 1677 row.getResultByName("guid")); 1678 if (childRecordIdsByLocalParentId.has(localParentId)) { 1679 let childRecordIds = childRecordIdsByLocalParentId.get(localParentId); 1680 childRecordIds.push(childRecordId); 1681 } else { 1682 childRecordIdsByLocalParentId.set(localParentId, [childRecordId]); 1683 } 1684 } 1685 1686 let itemRows = await this.db.execute(` 1687 SELECT id, syncChangeCounter, guid, isDeleted, type, isQuery, 1688 smartBookmarkName, tagFolderName, 1689 loadInSidebar, keyword, tags, url, IFNULL(title, "") AS title, 1690 description, feedURL, siteURL, position, parentGuid, 1691 IFNULL(parentTitle, "") AS parentTitle, dateAdded 1692 FROM itemsToUpload`); 1693 1694 for await (let row of yieldingIterator(itemRows)) { 1695 let syncChangeCounter = row.getResultByName("syncChangeCounter"); 1696 1697 let guid = row.getResultByName("guid"); 1698 let recordId = PlacesSyncUtils.bookmarks.guidToRecordId(guid); 1699 1700 // Tombstones don't carry additional properties. 1701 let isDeleted = row.getResultByName("isDeleted"); 1702 if (isDeleted) { 1703 changeRecords[recordId] = new BookmarkChangeRecord(syncChangeCounter, { 1704 id: recordId, 1705 deleted: true, 1706 }); 1707 continue; 1708 } 1709 1710 let parentGuid = row.getResultByName("parentGuid"); 1711 let parentRecordId = PlacesSyncUtils.bookmarks.guidToRecordId(parentGuid); 1712 1713 let type = row.getResultByName("type"); 1714 switch (type) { 1715 case PlacesUtils.bookmarks.TYPE_BOOKMARK: { 1716 let isQuery = row.getResultByName("isQuery"); 1717 if (isQuery) { 1718 let queryCleartext = { 1719 id: recordId, 1720 type: "query", 1721 // We ignore `parentid` and use the parent's `children`, but older 1722 // Desktops and Android use `parentid` as the canonical parent. 1723 // iOS is stricter and requires both `children` and `parentid` to 1724 // match. 1725 parentid: parentRecordId, 1726 // Older Desktops use `hasDupe` (along with `parentName` for 1727 // deduping), if hasDupe is true, then they won't attempt deduping 1728 // (since they believe that a duplicate for this record should 1729 // exist). We set it to true to prevent them from applying their 1730 // deduping logic. 1731 hasDupe: true, 1732 parentName: row.getResultByName("parentTitle"), 1733 // Omit `dateAdded` from the record if it's not set locally. 1734 dateAdded: row.getResultByName("dateAdded") || undefined, 1735 bmkUri: row.getResultByName("url"), 1736 title: row.getResultByName("title"), 1737 queryId: row.getResultByName("smartBookmarkName"), 1738 // folderName should never be an empty string or null 1739 folderName: row.getResultByName("tagFolderName") || undefined, 1740 }; 1741 let description = row.getResultByName("description"); 1742 if (description) { 1743 queryCleartext.description = description; 1744 } 1745 changeRecords[recordId] = new BookmarkChangeRecord( 1746 syncChangeCounter, queryCleartext); 1747 continue; 1748 } 1749 1750 let bookmarkCleartext = { 1751 id: recordId, 1752 type: "bookmark", 1753 parentid: parentRecordId, 1754 hasDupe: true, 1755 parentName: row.getResultByName("parentTitle"), 1756 dateAdded: row.getResultByName("dateAdded") || undefined, 1757 bmkUri: row.getResultByName("url"), 1758 title: row.getResultByName("title"), 1759 }; 1760 let description = row.getResultByName("description"); 1761 if (description) { 1762 bookmarkCleartext.description = description; 1763 } 1764 let loadInSidebar = row.getResultByName("loadInSidebar"); 1765 if (loadInSidebar) { 1766 bookmarkCleartext.loadInSidebar = true; 1767 } 1768 let keyword = row.getResultByName("keyword"); 1769 if (keyword) { 1770 bookmarkCleartext.keyword = keyword; 1771 } 1772 let tags = row.getResultByName("tags"); 1773 if (tags) { 1774 bookmarkCleartext.tags = tags.split(","); 1775 } 1776 changeRecords[recordId] = new BookmarkChangeRecord( 1777 syncChangeCounter, bookmarkCleartext); 1778 continue; 1779 } 1780 1781 case PlacesUtils.bookmarks.TYPE_FOLDER: { 1782 let feedURLHref = row.getResultByName("feedURL"); 1783 if (feedURLHref) { 1784 // Places stores livemarks as folders with feed and site URL annos. 1785 // See bug 1072833 for discussion about changing them to queries. 1786 let livemarkCleartext = { 1787 id: recordId, 1788 type: "livemark", 1789 parentid: parentRecordId, 1790 hasDupe: true, 1791 parentName: row.getResultByName("parentTitle"), 1792 dateAdded: row.getResultByName("dateAdded") || undefined, 1793 title: row.getResultByName("title"), 1794 feedUri: feedURLHref, 1795 }; 1796 let description = row.getResultByName("description"); 1797 if (description) { 1798 livemarkCleartext.description = description; 1799 } 1800 let siteURLHref = row.getResultByName("siteURL"); 1801 if (siteURLHref) { 1802 livemarkCleartext.siteUri = siteURLHref; 1803 } 1804 changeRecords[recordId] = new BookmarkChangeRecord( 1805 syncChangeCounter, livemarkCleartext); 1806 continue; 1807 } 1808 1809 let folderCleartext = { 1810 id: recordId, 1811 type: "folder", 1812 parentid: parentRecordId, 1813 hasDupe: true, 1814 parentName: row.getResultByName("parentTitle"), 1815 dateAdded: row.getResultByName("dateAdded") || undefined, 1816 title: row.getResultByName("title"), 1817 }; 1818 let description = row.getResultByName("description"); 1819 if (description) { 1820 folderCleartext.description = description; 1821 } 1822 let localId = row.getResultByName("id"); 1823 let childRecordIds = childRecordIdsByLocalParentId.get(localId); 1824 folderCleartext.children = childRecordIds || []; 1825 changeRecords[recordId] = new BookmarkChangeRecord( 1826 syncChangeCounter, folderCleartext); 1827 continue; 1828 } 1829 1830 case PlacesUtils.bookmarks.TYPE_SEPARATOR: { 1831 let separatorCleartext = { 1832 id: recordId, 1833 type: "separator", 1834 parentid: parentRecordId, 1835 hasDupe: true, 1836 parentName: row.getResultByName("parentTitle"), 1837 dateAdded: row.getResultByName("dateAdded") || undefined, 1838 // Older Desktops use `pos` for deduping. 1839 pos: row.getResultByName("position"), 1840 }; 1841 changeRecords[recordId] = new BookmarkChangeRecord( 1842 syncChangeCounter, separatorCleartext); 1843 continue; 1844 } 1845 1846 default: 1847 throw new TypeError("Can't create record for unknown Places item"); 1848 } 1849 } 1850 1851 return changeRecords; 1852 } 1853 1854 /** 1855 * Closes the mirror database connection. This is called automatically on 1856 * shutdown, but may also be called explicitly when the mirror is no longer 1857 * needed. 1858 */ 1859 finalize() { 1860 if (!this.finalizePromise) { 1861 this.finalizePromise = (async () => { 1862 await this.db.close(); 1863 this.finalizeAt.removeBlocker(this.finalizeBound); 1864 })(); 1865 } 1866 return this.finalizePromise; 1867 } 1868} 1869 1870this.SyncedBookmarksMirror = SyncedBookmarksMirror; 1871 1872/** Synced item kinds. Each corresponds to a Sync record type. */ 1873SyncedBookmarksMirror.KIND = { 1874 BOOKMARK: 1, 1875 QUERY: 2, 1876 FOLDER: 3, 1877 LIVEMARK: 4, 1878 SEPARATOR: 5, 1879}; 1880 1881/** Valid key types for the key-value `meta` table. */ 1882SyncedBookmarksMirror.META = { 1883 MODIFIED: 1, 1884}; 1885 1886/** 1887 * An error thrown when the merge can't proceed because the local or remote 1888 * tree is inconsistent. 1889 */ 1890SyncedBookmarksMirror.ConsistencyError = 1891 class ConsistencyError extends Error {}; 1892 1893// Indicates if the mirror should be replaced because the database file is 1894// corrupt. 1895function isDatabaseCorrupt(error) { 1896 return error instanceof Ci.mozIStorageError && 1897 (error.result == Ci.mozIStorageError.CORRUPT || 1898 error.result == Ci.mozIStorageError.NOTADB); 1899} 1900 1901/** 1902 * Migrates the mirror database schema to the latest version. 1903 * 1904 * @param {Sqlite.OpenedConnection} db 1905 * The mirror database connection. 1906 */ 1907async function migrateMirrorSchema(db) { 1908 let currentSchemaVersion = await db.getSchemaVersion("mirror"); 1909 if (currentSchemaVersion < 1) { 1910 await initializeMirrorDatabase(db); 1911 } 1912 // Downgrading from a newer profile to an older profile rolls back the 1913 // schema version, but leaves all new columns in place. We'll run the 1914 // migration logic again on the next upgrade. 1915 await db.setSchemaVersion(MIRROR_SCHEMA_VERSION, "mirror"); 1916} 1917 1918/** 1919 * Initializes a new mirror database, creating persistent tables, indexes, and 1920 * roots. 1921 * 1922 * @param {Sqlite.OpenedConnection} db 1923 * The mirror database connection. 1924 */ 1925async function initializeMirrorDatabase(db) { 1926 // Key-value metadata table. Currently stores just the server collection 1927 // last modified time. 1928 await db.execute(`CREATE TABLE mirror.meta( 1929 key INTEGER PRIMARY KEY, 1930 value NOT NULL 1931 CHECK(key = ${SyncedBookmarksMirror.META.MODIFIED}) 1932 )`); 1933 1934 await db.execute(`CREATE TABLE mirror.items( 1935 id INTEGER PRIMARY KEY, 1936 guid TEXT UNIQUE NOT NULL, 1937 /* The server modified time, in milliseconds. */ 1938 serverModified INTEGER NOT NULL DEFAULT 0, 1939 needsMerge BOOLEAN NOT NULL DEFAULT 0, 1940 isDeleted BOOLEAN NOT NULL DEFAULT 0, 1941 kind INTEGER NOT NULL DEFAULT -1, 1942 /* The creation date, in milliseconds. */ 1943 dateAdded INTEGER NOT NULL DEFAULT 0, 1944 title TEXT, 1945 urlId INTEGER REFERENCES urls(id) 1946 ON DELETE SET NULL, 1947 keyword TEXT, 1948 tagFolderName TEXT, 1949 description TEXT, 1950 loadInSidebar BOOLEAN, 1951 smartBookmarkName TEXT, 1952 feedURL TEXT, 1953 siteURL TEXT, 1954 /* Only bookmarks and queries must have URLs. */ 1955 CHECK(CASE WHEN kind IN (${[ 1956 SyncedBookmarksMirror.KIND.BOOKMARK, 1957 SyncedBookmarksMirror.KIND.QUERY, 1958 ].join(",")}) THEN urlId NOT NULL 1959 ELSE urlId IS NULL END) 1960 )`); 1961 1962 await db.execute(`CREATE TABLE mirror.structure( 1963 guid TEXT NOT NULL PRIMARY KEY, 1964 parentGuid TEXT NOT NULL REFERENCES items(guid) 1965 ON DELETE CASCADE, 1966 position INTEGER NOT NULL 1967 ) WITHOUT ROWID`); 1968 1969 await db.execute(`CREATE TABLE mirror.urls( 1970 id INTEGER PRIMARY KEY, 1971 guid TEXT NOT NULL, 1972 url TEXT NOT NULL, 1973 hash INTEGER NOT NULL, 1974 revHost TEXT NOT NULL 1975 )`); 1976 1977 await db.execute(`CREATE TABLE mirror.tags( 1978 itemId INTEGER NOT NULL REFERENCES items(id) 1979 ON DELETE CASCADE, 1980 tag TEXT NOT NULL 1981 )`); 1982 1983 await db.execute(`CREATE INDEX mirror.urlHashes ON urls(hash)`); 1984 1985 await createMirrorRoots(db); 1986} 1987 1988/** 1989 * Sets up the syncable roots. All items in the mirror should descend from these 1990 * roots. If we ever add new syncable roots to Places, this function should also 1991 * be updated to create them in the mirror. 1992 * 1993 * @param {Sqlite.OpenedConnection} db 1994 * The mirror database connection. 1995 */ 1996async function createMirrorRoots(db) { 1997 const syncableRoots = [{ 1998 guid: PlacesUtils.bookmarks.rootGuid, 1999 // The Places root is its own parent, to satisfy the foreign key and 2000 // `NOT NULL` constraints on `structure`. 2001 parentGuid: PlacesUtils.bookmarks.rootGuid, 2002 position: -1, 2003 needsMerge: false, 2004 }, { 2005 guid: PlacesUtils.bookmarks.menuGuid, 2006 parentGuid: PlacesUtils.bookmarks.rootGuid, 2007 position: 0, 2008 needsMerge: true, 2009 }, { 2010 guid: PlacesUtils.bookmarks.toolbarGuid, 2011 parentGuid: PlacesUtils.bookmarks.rootGuid, 2012 position: 1, 2013 needsMerge: true, 2014 }, { 2015 guid: PlacesUtils.bookmarks.unfiledGuid, 2016 parentGuid: PlacesUtils.bookmarks.rootGuid, 2017 position: 2, 2018 needsMerge: true, 2019 }, { 2020 guid: PlacesUtils.bookmarks.mobileGuid, 2021 parentGuid: PlacesUtils.bookmarks.rootGuid, 2022 position: 3, 2023 needsMerge: true, 2024 }]; 2025 for (let { guid, parentGuid, position, needsMerge } of syncableRoots) { 2026 await db.executeCached(` 2027 INSERT INTO items(guid, kind, needsMerge) 2028 VALUES(:guid, :kind, :needsMerge)`, 2029 { guid, kind: SyncedBookmarksMirror.KIND.FOLDER, needsMerge }); 2030 2031 await db.executeCached(` 2032 INSERT INTO structure(guid, parentGuid, position) 2033 VALUES(:guid, :parentGuid, :position)`, 2034 { guid, parentGuid, position }); 2035 } 2036} 2037 2038/** 2039 * Creates temporary tables, views, and triggers to apply the mirror to Places. 2040 * 2041 * The bulk of the logic to apply all remotely changed items is defined in 2042 * `INSTEAD OF DELETE` triggers on the `itemsToMerge` and `structureToMerge` 2043 * views. When we execute `DELETE FROM newRemote{Items, Structure}`, SQLite 2044 * fires the triggers for each row in the view. This is equivalent to, but more 2045 * efficient than, issuing `SELECT * FROM newRemote{Items, Structure}`, 2046 * followed by separate `INSERT` and `UPDATE` statements. 2047 * 2048 * Using triggers to execute all these statements avoids the overhead of passing 2049 * results between the storage and main threads, and wrapping each result row in 2050 * a `mozStorageRow` object. 2051 * 2052 * @param {Sqlite.OpenedConnection} db 2053 * The mirror database connection. 2054 */ 2055async function initializeTempMirrorEntities(db) { 2056 // Columns in `items` that correspond to annos stored in `moz_items_annos`. 2057 // We use this table to build SQL fragments for the `insertNewLocalItems` and 2058 // `updateExistingLocalItems` triggers below. 2059 const syncedAnnoTriggers = [{ 2060 annoName: PlacesSyncUtils.bookmarks.DESCRIPTION_ANNO, 2061 columnName: "newDescription", 2062 type: PlacesUtils.annotations.TYPE_STRING, 2063 }, { 2064 annoName: PlacesSyncUtils.bookmarks.SIDEBAR_ANNO, 2065 columnName: "newLoadInSidebar", 2066 type: PlacesUtils.annotations.TYPE_INT32, 2067 }, { 2068 annoName: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO, 2069 columnName: "newSmartBookmarkName", 2070 type: PlacesUtils.annotations.TYPE_STRING, 2071 }, { 2072 annoName: PlacesUtils.LMANNO_FEEDURI, 2073 columnName: "newFeedURL", 2074 type: PlacesUtils.annotations.TYPE_STRING, 2075 }, { 2076 annoName: PlacesUtils.LMANNO_SITEURI, 2077 columnName: "newSiteURL", 2078 type: PlacesUtils.annotations.TYPE_STRING, 2079 }]; 2080 2081 // Stores the value and structure states of all nodes in the merged tree. 2082 await db.execute(`CREATE TEMP TABLE mergeStates( 2083 localGuid TEXT NOT NULL, 2084 mergedGuid TEXT NOT NULL, 2085 parentGuid TEXT NOT NULL, 2086 level INTEGER NOT NULL, 2087 position INTEGER NOT NULL, 2088 valueState INTEGER NOT NULL, 2089 structureState INTEGER NOT NULL, 2090 PRIMARY KEY(localGuid, mergedGuid) 2091 ) WITHOUT ROWID`); 2092 2093 // A view of the value states for all bookmarks in the mirror. We use triggers 2094 // on this view to update Places. Note that we can't just `REPLACE INTO 2095 // moz_bookmarks`, because `REPLACE` doesn't fire the `AFTER DELETE` triggers 2096 // that Places uses to maintain schema coherency. 2097 await db.execute(` 2098 CREATE TEMP VIEW itemsToMerge(localId, remoteId, hasRemoteValue, newLevel, 2099 oldGuid, newGuid, newType, 2100 newDateAddedMicroseconds, newTitle, 2101 oldPlaceId, newPlaceId, newKeyword, 2102 newDescription, newLoadInSidebar, 2103 newSmartBookmarkName, newFeedURL, 2104 newSiteURL) AS 2105 SELECT b.id, v.id, r.valueState = ${BookmarkMergeState.TYPE.REMOTE}, 2106 r.level, r.localGuid, r.mergedGuid, 2107 (CASE WHEN v.kind IN (${[ 2108 SyncedBookmarksMirror.KIND.BOOKMARK, 2109 SyncedBookmarksMirror.KIND.QUERY, 2110 ].join(",")}) THEN ${PlacesUtils.bookmarks.TYPE_BOOKMARK} 2111 WHEN v.kind IN (${[ 2112 SyncedBookmarksMirror.KIND.FOLDER, 2113 SyncedBookmarksMirror.KIND.LIVEMARK, 2114 ].join(",")}) THEN ${PlacesUtils.bookmarks.TYPE_FOLDER} 2115 ELSE ${PlacesUtils.bookmarks.TYPE_SEPARATOR} END), 2116 /* Take the older creation date. "b.dateAdded" is in microseconds; 2117 "v.dateAdded" is in milliseconds. */ 2118 (CASE WHEN b.dateAdded / 1000 < v.dateAdded THEN b.dateAdded 2119 ELSE v.dateAdded * 1000 END), 2120 v.title, h.id, u.newPlaceId, v.keyword, v.description, 2121 v.loadInSidebar, v.smartBookmarkName, v.feedURL, v.siteURL 2122 FROM items v 2123 JOIN mergeStates r ON r.mergedGuid = v.guid 2124 LEFT JOIN moz_bookmarks b ON b.guid = r.localGuid 2125 LEFT JOIN moz_places h ON h.id = b.fk 2126 LEFT JOIN ( 2127 SELECT h.id AS newPlaceId, u.id AS urlId 2128 FROM urls u 2129 JOIN moz_places h ON h.url_hash = u.hash AND 2130 h.url = u.url 2131 ) u ON u.urlId = v.urlId 2132 WHERE r.mergedGuid <> '${PlacesUtils.bookmarks.rootGuid}'`); 2133 2134 // Changes local GUIDs to remote GUIDs, drops local tombstones for revived 2135 // remote items, and flags remote items as merged. In the trigger body, `OLD` 2136 // refers to the row for the unmerged item in `itemsToMerge`. 2137 await db.execute(` 2138 CREATE TEMP TRIGGER mergeGuids 2139 INSTEAD OF DELETE ON itemsToMerge 2140 BEGIN 2141 /* We update GUIDs here, instead of in the "updateExistingLocalItems" 2142 trigger, because deduped items where we're keeping the local value 2143 state won't have "hasRemoteValue" set. */ 2144 UPDATE moz_bookmarks SET 2145 guid = OLD.newGuid, 2146 syncStatus = ${PlacesUtils.bookmarks.SYNC_STATUS.NORMAL} 2147 WHERE OLD.oldGuid <> OLD.newGuid AND 2148 id = OLD.localId; 2149 2150 /* Record item changed notifications for the updated GUIDs. */ 2151 INSERT INTO guidsChanged(itemId, oldGuid, level) 2152 SELECT OLD.localId, OLD.oldGuid, OLD.newLevel 2153 WHERE OLD.oldGuid <> OLD.newGuid; 2154 2155 /* Drop local tombstones for revived remote items. */ 2156 DELETE FROM moz_bookmarks_deleted WHERE guid = OLD.newGuid; 2157 2158 /* Flag the remote item as merged. */ 2159 UPDATE items SET 2160 needsMerge = 0 2161 WHERE needsMerge AND 2162 id = OLD.remoteId; 2163 END`); 2164 2165 // Inserts items from the mirror that don't exist locally. 2166 await db.execute(` 2167 CREATE TEMP TRIGGER insertNewLocalItems 2168 INSTEAD OF DELETE ON itemsToMerge WHEN OLD.localId IS NULL 2169 BEGIN 2170 /* Record an item added notification for the new item. */ 2171 INSERT INTO itemsAdded(guid, keywordChanged, level) 2172 VALUES(OLD.newGuid, OLD.newKeyword NOT NULL OR 2173 EXISTS(SELECT 1 FROM moz_keywords 2174 WHERE place_id = OLD.newPlaceId OR 2175 keyword = OLD.newKeyword), 2176 OLD.newLevel); 2177 2178 /* Sync associates keywords with bookmarks, and doesn't sync POST data; 2179 Places associates keywords with (URL, POST data) pairs, and multiple 2180 bookmarks may have the same URL. For simplicity, we bump the change 2181 counter for all local bookmarks with the remote URL (bug 1328737), 2182 then remove all local keywords from remote URLs, and the remote keyword 2183 from local URLs. */ 2184 UPDATE moz_bookmarks SET 2185 syncChangeCounter = syncChangeCounter + 1 2186 WHERE fk IN ( 2187 /* We intentionally use "place_id = OLD.newPlaceId" in the subquery, 2188 instead of "fk = OLD.newPlaceId OR fk IN (...)" in the WHERE clause 2189 above, because we only want to bump the counter if the URL has 2190 keywords. */ 2191 SELECT place_id FROM moz_keywords 2192 WHERE place_id = OLD.newPlaceId OR 2193 keyword = OLD.newKeyword); 2194 2195 /* Remove the new keyword from existing items, and all keywords from the 2196 new URL. */ 2197 DELETE FROM moz_keywords WHERE place_id = OLD.newPlaceId OR 2198 keyword = OLD.newKeyword; 2199 2200 /* Remove existing tags for the new URL. */ 2201 DELETE FROM localTags WHERE placeId = OLD.newPlaceId; 2202 2203 /* Insert the new item, using "-1" as the placeholder parent and 2204 position. We'll update these later, in the "updateLocalStructure" 2205 trigger. */ 2206 INSERT INTO moz_bookmarks(guid, parent, position, type, fk, title, 2207 dateAdded, lastModified, syncStatus, 2208 syncChangeCounter) 2209 VALUES(OLD.newGuid, -1, -1, OLD.newType, OLD.newPlaceId, OLD.newTitle, 2210 OLD.newDateAddedMicroseconds, 2211 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000, 2212 ${PlacesUtils.bookmarks.SYNC_STATUS.NORMAL}, 0); 2213 2214 /* Insert a new keyword for the new URL, if one is set. */ 2215 INSERT OR IGNORE INTO moz_keywords(keyword, place_id, post_data) 2216 SELECT OLD.newKeyword, OLD.newPlaceId, '' 2217 WHERE OLD.newKeyword NOT NULL; 2218 2219 /* Insert new tags for the new URL. */ 2220 INSERT INTO localTags(tag, placeId) 2221 SELECT t.tag, OLD.newPlaceId FROM tags t 2222 WHERE t.itemId = OLD.remoteId; 2223 2224 /* Insert new synced annos. These are almost identical to the statements 2225 for updates, except we need an additional subquery to fetch the new 2226 item's ID. We can also skip removing existing annos. */ 2227 INSERT OR IGNORE INTO moz_anno_attributes(name) 2228 VALUES ${syncedAnnoTriggers.map(annoTrigger => 2229 `('${annoTrigger.annoName}')` 2230 ).join(",")}; 2231 2232 ${syncedAnnoTriggers.map(annoTrigger => ` 2233 INSERT INTO moz_items_annos(item_id, anno_attribute_id, content, flags, 2234 expiration, type, lastModified, dateAdded) 2235 SELECT (SELECT id FROM moz_bookmarks 2236 WHERE guid = OLD.newGuid), 2237 (SELECT id FROM moz_anno_attributes 2238 WHERE name = '${annoTrigger.annoName}'), 2239 OLD.${annoTrigger.columnName}, 0, 2240 ${PlacesUtils.annotations.EXPIRE_NEVER}, ${annoTrigger.type}, 2241 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000, 2242 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000 2243 WHERE OLD.${annoTrigger.columnName} NOT NULL; 2244 2245 /* Record an anno set notification for the new synced anno. */ 2246 REPLACE INTO annosChanged(itemId, annoName, wasRemoved) 2247 SELECT b.id, '${annoTrigger.annoName}', 0 FROM moz_bookmarks b 2248 WHERE b.guid = OLD.newGuid AND 2249 OLD.${annoTrigger.columnName} NOT NULL; 2250 `).join("")} 2251 END`); 2252 2253 // Updates existing items with new values from the mirror. 2254 await db.execute(` 2255 CREATE TEMP TRIGGER updateExistingLocalItems 2256 INSTEAD OF DELETE ON itemsToMerge WHEN OLD.hasRemoteValue AND 2257 OLD.localId NOT NULL 2258 BEGIN 2259 /* Record an item changed notification for the existing item. */ 2260 INSERT INTO itemsChanged(itemId, oldTitle, oldPlaceId, keywordChanged, 2261 level) 2262 SELECT id, title, OLD.oldPlaceId, OLD.newKeyword NOT NULL OR 2263 EXISTS(SELECT 1 FROM moz_keywords 2264 WHERE place_id IN (OLD.oldPlaceId, OLD.newPlaceId) OR 2265 keyword = OLD.newKeyword), 2266 OLD.newLevel 2267 FROM moz_bookmarks 2268 WHERE id = OLD.localId; 2269 2270 UPDATE moz_bookmarks SET 2271 title = OLD.newTitle, 2272 dateAdded = OLD.newDateAddedMicroseconds, 2273 lastModified = STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000, 2274 syncStatus = ${PlacesUtils.bookmarks.SYNC_STATUS.NORMAL}, 2275 syncChangeCounter = 0 2276 WHERE id = OLD.localId; 2277 2278 /* Bump the change counter for items with the old URL, new URL, and new 2279 keyword. */ 2280 UPDATE moz_bookmarks SET 2281 syncChangeCounter = syncChangeCounter + 1 2282 WHERE fk IN (SELECT place_id FROM moz_keywords 2283 WHERE place_id IN (OLD.oldPlaceId, OLD.newPlaceId) OR 2284 keyword = OLD.newKeyword); 2285 2286 /* Remove the new keyword from existing items, and all keywords from the 2287 old and new URLs. */ 2288 DELETE FROM moz_keywords WHERE place_id IN (OLD.oldPlaceId, 2289 OLD.newPlaceId) OR 2290 keyword = OLD.newKeyword; 2291 2292 /* Remove existing tags. */ 2293 DELETE FROM localTags WHERE placeId IN (OLD.oldPlaceId, OLD.newPlaceId); 2294 2295 /* Update the URL and recalculate frecency. It's important we do this 2296 *after* removing old keywords and *before* inserting new ones, so that 2297 the above statements select the correct affected items. */ 2298 UPDATE moz_bookmarks SET 2299 fk = OLD.newPlaceId 2300 WHERE OLD.oldPlaceId <> OLD.newPlaceId AND 2301 id = OLD.localId; 2302 2303 UPDATE moz_places SET 2304 frecency = -1 2305 WHERE OLD.oldPlaceId <> OLD.newPlaceId AND 2306 id IN (OLD.oldPlaceId, OLD.newPlaceId); 2307 2308 /* Insert a new keyword for the new URL, if one is set. */ 2309 INSERT OR IGNORE INTO moz_keywords(keyword, place_id, post_data) 2310 SELECT OLD.newKeyword, OLD.newPlaceId, '' 2311 WHERE OLD.newKeyword NOT NULL; 2312 2313 /* Insert new tags for the new URL. */ 2314 INSERT INTO localTags(tag, placeId) 2315 SELECT t.tag, OLD.newPlaceId FROM tags t 2316 WHERE t.itemId = OLD.remoteId; 2317 2318 /* Record anno removed notifications for the synced annos. */ 2319 REPLACE INTO annosChanged(itemId, annoName, wasRemoved) 2320 SELECT a.item_id, n.name, 1 FROM moz_items_annos a 2321 JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id 2322 WHERE item_id = OLD.localId AND 2323 anno_attribute_id IN (SELECT id FROM moz_anno_attributes 2324 WHERE name IN (${syncedAnnoTriggers.map( 2325 annoTrigger => `'${annoTrigger.annoName}'` 2326 ).join(",")})); 2327 2328 /* Remove existing synced annos. */ 2329 DELETE FROM moz_items_annos 2330 WHERE item_id = OLD.localId AND 2331 anno_attribute_id IN (SELECT id FROM moz_anno_attributes 2332 WHERE name IN (${syncedAnnoTriggers.map( 2333 annoTrigger => `'${annoTrigger.annoName}'` 2334 ).join(",")})); 2335 2336 /* Insert new synced annos. */ 2337 INSERT OR IGNORE INTO moz_anno_attributes(name) 2338 VALUES ${syncedAnnoTriggers.map(annoTrigger => 2339 `('${annoTrigger.annoName}')` 2340 ).join(",")}; 2341 2342 ${syncedAnnoTriggers.map(annoTrigger => ` 2343 INSERT INTO moz_items_annos(item_id, anno_attribute_id, content, flags, 2344 expiration, type, lastModified, dateAdded) 2345 SELECT OLD.localId, (SELECT id FROM moz_anno_attributes 2346 WHERE name = '${annoTrigger.annoName}'), 2347 OLD.${annoTrigger.columnName}, 0, 2348 ${PlacesUtils.annotations.EXPIRE_NEVER}, ${annoTrigger.type}, 2349 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000, 2350 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000 2351 WHERE OLD.${annoTrigger.columnName} NOT NULL; 2352 2353 /* Record an anno set notification for the new synced anno. */ 2354 REPLACE INTO annosChanged(itemId, annoName, wasRemoved) 2355 SELECT OLD.localId, '${annoTrigger.annoName}', 0 2356 WHERE OLD.${annoTrigger.columnName} NOT NULL; 2357 `).join("")} 2358 END`); 2359 2360 // A view of the structure states for all items in the merged tree. The 2361 // mirror stores structure info in a separate table, like iOS, while Places 2362 // stores structure info on children. Unlike iOS, we can't simply check the 2363 // parent's merge state to know if its children changed. This is because our 2364 // merged tree might diverge from the mirror if we're missing children, or if 2365 // we temporarily reparented children without parents to "unfiled". In that 2366 // case, we want to keep syncing, but *don't* want to reupload the new local 2367 // structure to the server. 2368 await db.execute(` 2369 CREATE TEMP VIEW structureToMerge(localId, hasNewStructure, isRoot, 2370 oldParentId, newParentId, oldPosition, 2371 newPosition, newLevel) AS 2372 SELECT b.id, r.structureState = ${BookmarkMergeState.TYPE.NEW}, 2373 '${PlacesUtils.bookmarks.rootGuid}' IN (r.mergedGuid, r.parentGuid), 2374 b.parent, p.id, b.position, r.position, r.level 2375 FROM moz_bookmarks b 2376 JOIN mergeStates r ON r.mergedGuid = b.guid 2377 JOIN moz_bookmarks p ON p.guid = r.parentGuid`); 2378 2379 // Updates all parents and positions to reflect the merged tree. 2380 await db.execute(` 2381 CREATE TEMP TRIGGER updateLocalStructure 2382 INSTEAD OF DELETE ON structureToMerge WHEN NOT OLD.isRoot 2383 BEGIN 2384 UPDATE moz_bookmarks SET 2385 parent = OLD.newParentId 2386 WHERE id = OLD.localId AND 2387 parent <> OLD.newParentId; 2388 2389 UPDATE moz_bookmarks SET 2390 position = OLD.newPosition 2391 WHERE id = OLD.localId AND 2392 position <> OLD.newPosition; 2393 2394 /* Record observer notifications for moved items. We ignore items that 2395 didn't move, and items with placeholder parents and positions of "-1", 2396 since they're new. */ 2397 INSERT INTO itemsMoved(itemId, oldParentId, oldParentGuid, oldPosition, 2398 level) 2399 SELECT OLD.localId, OLD.oldParentId, p.guid, OLD.oldPosition, 2400 OLD.newLevel 2401 FROM moz_bookmarks p 2402 WHERE p.id = OLD.oldParentId AND 2403 -1 NOT IN (OLD.oldParentId, OLD.oldPosition) AND 2404 (OLD.oldParentId <> OLD.newParentId OR 2405 OLD.oldPosition <> OLD.newPosition); 2406 END`); 2407 2408 // Bump the change counter for folders with new structure state, so that 2409 // they're reuploaded to the server. 2410 await db.execute(` 2411 CREATE TEMP TRIGGER flagNewStructure 2412 INSTEAD OF DELETE ON structureToMerge WHEN OLD.hasNewStructure 2413 BEGIN 2414 UPDATE moz_bookmarks SET 2415 syncChangeCounter = syncChangeCounter + 1 2416 WHERE id = OLD.localId; 2417 END`); 2418 2419 // A view of local bookmark tags. Tags, like keywords, are associated with 2420 // URLs, so two bookmarks with the same URL should have the same tags. Unlike 2421 // keywords, one tag may be associated with many different URLs. Tags are also 2422 // different because they're implemented as bookmarks under the hood. Each tag 2423 // is stored as a folder under the tags root, and tagged URLs are stored as 2424 // untitled bookmarks under these folders. This complexity, along with tag 2425 // query rewriting, can be removed once bug 1293445 lands. 2426 await db.execute(` 2427 CREATE TEMP VIEW localTags(tagEntryId, tagEntryGuid, tagFolderId, 2428 tagFolderGuid, tagEntryPosition, tagEntryType, 2429 tag, placeId) AS 2430 SELECT b.id, b.guid, p.id, p.guid, b.position, b.type, p.title, b.fk 2431 FROM moz_bookmarks b 2432 JOIN moz_bookmarks p ON p.id = b.parent 2433 JOIN moz_bookmarks r ON r.id = p.parent 2434 WHERE b.type = ${PlacesUtils.bookmarks.TYPE_BOOKMARK} AND 2435 r.guid = '${PlacesUtils.bookmarks.tagsGuid}'`); 2436 2437 // Untags a URL by removing its tag entry. 2438 await db.execute(` 2439 CREATE TEMP TRIGGER untagLocalPlace 2440 INSTEAD OF DELETE ON localTags 2441 BEGIN 2442 /* Record an item removed notification for the tag entry. */ 2443 INSERT INTO itemsRemoved(itemId, parentId, position, type, placeId, guid, 2444 parentGuid, isUntagging) 2445 VALUES(OLD.tagEntryId, OLD.tagFolderId, OLD.tagEntryPosition, 2446 OLD.tagEntryType, OLD.placeId, OLD.tagEntryGuid, 2447 OLD.tagFolderGuid, 1); 2448 2449 DELETE FROM moz_bookmarks WHERE id = OLD.tagEntryId; 2450 2451 /* Fix the positions of the sibling tag entries. */ 2452 UPDATE moz_bookmarks SET 2453 position = position - 1 2454 WHERE parent = OLD.tagFolderId AND 2455 position > OLD.tagEntryPosition; 2456 END`); 2457 2458 // Tags a URL by creating a tag folder if it doesn't exist, then inserting a 2459 // tag entry for the URL into the tag folder. `NEW.placeId` can be NULL, in 2460 // which case we'll just create the tag folder. 2461 await db.execute(` 2462 CREATE TEMP TRIGGER tagLocalPlace 2463 INSTEAD OF INSERT ON localTags 2464 BEGIN 2465 /* Ensure the tag folder exists. */ 2466 INSERT OR IGNORE INTO moz_bookmarks(guid, parent, position, type, title, 2467 dateAdded, lastModified) 2468 VALUES(IFNULL((SELECT b.guid FROM moz_bookmarks b 2469 JOIN moz_bookmarks p ON p.id = b.parent 2470 WHERE b.title = NEW.tag AND 2471 p.guid = '${PlacesUtils.bookmarks.tagsGuid}'), 2472 GENERATE_GUID()), 2473 (SELECT id FROM moz_bookmarks 2474 WHERE guid = '${PlacesUtils.bookmarks.tagsGuid}'), 2475 (SELECT COUNT(*) FROM moz_bookmarks b 2476 JOIN moz_bookmarks p ON p.id = b.parent 2477 WHERE p.guid = '${PlacesUtils.bookmarks.tagsGuid}'), 2478 ${PlacesUtils.bookmarks.TYPE_FOLDER}, NEW.tag, 2479 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000, 2480 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000); 2481 2482 /* Record an item added notification if we created a tag folder. 2483 "CHANGES()" returns the number of rows affected by the INSERT above: 2484 1 if we created the folder, or 0 if the folder already existed. */ 2485 INSERT INTO itemsAdded(guid, isTagging) 2486 SELECT b.guid, 1 FROM moz_bookmarks b 2487 JOIN moz_bookmarks p ON p.id = b.parent 2488 WHERE CHANGES() > 0 AND 2489 b.title = NEW.tag AND 2490 p.guid = '${PlacesUtils.bookmarks.tagsGuid}'; 2491 2492 /* Add a tag entry for the URL under the tag folder. Omitting the place 2493 ID creates a tag folder without tagging the URL. */ 2494 INSERT OR IGNORE INTO moz_bookmarks(guid, parent, position, type, fk, 2495 dateAdded, lastModified) 2496 SELECT GENERATE_GUID(), 2497 (SELECT b.id FROM moz_bookmarks b 2498 JOIN moz_bookmarks p ON p.id = b.parent 2499 WHERE p.guid = '${PlacesUtils.bookmarks.tagsGuid}' AND 2500 b.title = NEW.tag), 2501 (SELECT COUNT(*) FROM moz_bookmarks b 2502 JOIN moz_bookmarks p ON p.id = b.parent 2503 JOIN moz_bookmarks r ON r.id = p.parent 2504 WHERE p.title = NEW.tag AND 2505 r.guid = '${PlacesUtils.bookmarks.tagsGuid}'), 2506 ${PlacesUtils.bookmarks.TYPE_BOOKMARK}, NEW.placeId, 2507 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000, 2508 STRFTIME('%s', 'now', 'localtime', 'utc') * 1000000 2509 WHERE NEW.placeId NOT NULL; 2510 2511 /* Record an item added notification for the tag entry. */ 2512 INSERT INTO itemsAdded(guid, isTagging) 2513 SELECT b.guid, 1 FROM moz_bookmarks b 2514 JOIN moz_bookmarks p ON p.id = b.parent 2515 JOIN moz_bookmarks r ON r.id = p.parent 2516 WHERE b.fk = NEW.placeId AND 2517 p.title = NEW.tag AND 2518 r.guid = '${PlacesUtils.bookmarks.tagsGuid}'; 2519 END`); 2520 2521 // Stores properties to pass to `onItem{Added, Changed, Moved, Removed}` 2522 // bookmark observers for new, updated, moved, and deleted items. 2523 await db.execute(`CREATE TEMP TABLE itemsAdded( 2524 guid TEXT PRIMARY KEY, 2525 isTagging BOOLEAN NOT NULL DEFAULT 0, 2526 keywordChanged BOOLEAN NOT NULL DEFAULT 0, 2527 level INTEGER NOT NULL DEFAULT -1 2528 ) WITHOUT ROWID`); 2529 2530 await db.execute(`CREATE TEMP TABLE guidsChanged( 2531 itemId INTEGER NOT NULL, 2532 oldGuid TEXT NOT NULL, 2533 level INTEGER NOT NULL DEFAULT -1, 2534 PRIMARY KEY(itemId, oldGuid) 2535 ) WITHOUT ROWID`); 2536 2537 await db.execute(`CREATE TEMP TABLE itemsChanged( 2538 itemId INTEGER PRIMARY KEY, 2539 oldTitle TEXT, 2540 oldPlaceId INTEGER, 2541 keywordChanged BOOLEAN NOT NULL DEFAULT 0, 2542 level INTEGER NOT NULL DEFAULT -1 2543 )`); 2544 2545 await db.execute(`CREATE TEMP TABLE itemsMoved( 2546 itemId INTEGER PRIMARY KEY, 2547 oldParentId INTEGER NOT NULL, 2548 oldParentGuid TEXT NOT NULL, 2549 oldPosition INTEGER NOT NULL, 2550 level INTEGER NOT NULL DEFAULT -1 2551 )`); 2552 2553 await db.execute(`CREATE TEMP TABLE itemsRemoved( 2554 guid TEXT PRIMARY KEY, 2555 itemId INTEGER NOT NULL, 2556 parentId INTEGER NOT NULL, 2557 position INTEGER NOT NULL, 2558 type INTEGER NOT NULL, 2559 placeId INTEGER, 2560 parentGuid TEXT NOT NULL, 2561 /* We record the original level of the removed item in the tree so that we 2562 can notify children before parents. */ 2563 level INTEGER NOT NULL DEFAULT -1, 2564 isUntagging BOOLEAN NOT NULL DEFAULT 0 2565 ) WITHOUT ROWID`); 2566 2567 // Stores properties to pass to `onItemAnnotation{Set, Removed}` anno 2568 // observers. 2569 await db.execute(`CREATE TEMP TABLE annosChanged( 2570 itemId INTEGER NOT NULL, 2571 annoName TEXT NOT NULL, 2572 wasRemoved BOOLEAN NOT NULL, 2573 PRIMARY KEY(itemId, annoName, wasRemoved) 2574 ) WITHOUT ROWID`); 2575 2576 await db.execute(`CREATE TEMP TABLE itemsToWeaklyReupload( 2577 id INTEGER PRIMARY KEY 2578 )`); 2579 2580 // Stores locally changed items staged for upload. See `stageItemsToUpload` 2581 // for an explanation of why these tables exists. 2582 await db.execute(`CREATE TEMP TABLE itemsToUpload( 2583 id INTEGER PRIMARY KEY, 2584 guid TEXT UNIQUE NOT NULL, 2585 syncChangeCounter INTEGER NOT NULL, 2586 isDeleted BOOLEAN NOT NULL DEFAULT 0, 2587 parentGuid TEXT, 2588 parentTitle TEXT, 2589 dateAdded INTEGER, /* In milliseconds. */ 2590 type INTEGER, 2591 title TEXT, 2592 isQuery BOOLEAN NOT NULL DEFAULT 0, 2593 url TEXT, 2594 tags TEXT, 2595 description TEXT, 2596 loadInSidebar BOOLEAN, 2597 smartBookmarkName TEXT, 2598 tagFolderName TEXT, 2599 keyword TEXT, 2600 feedURL TEXT, 2601 siteURL TEXT, 2602 position INTEGER 2603 )`); 2604 2605 await db.execute(`CREATE TEMP TABLE structureToUpload( 2606 guid TEXT PRIMARY KEY, 2607 parentId INTEGER NOT NULL REFERENCES itemsToUpload(id) 2608 ON DELETE CASCADE, 2609 position INTEGER NOT NULL 2610 ) WITHOUT ROWID`); 2611} 2612 2613// Converts a Sync record ID to a Places GUID. Returns `null` if the ID is 2614// invalid. 2615function validateGuid(recordId) { 2616 let guid = PlacesSyncUtils.bookmarks.recordIdToGuid(recordId); 2617 return PlacesUtils.isValidGuid(guid) ? guid : null; 2618} 2619 2620// Converts a Sync record's last modified time to milliseconds. 2621function determineServerModified(record) { 2622 return Math.max(record.modified * 1000, 0) || 0; 2623} 2624 2625// Determines a Sync record's creation date. 2626function determineDateAdded(record) { 2627 let serverModified = determineServerModified(record); 2628 return PlacesSyncUtils.bookmarks.ratchetTimestampBackwards( 2629 record.dateAdded, serverModified); 2630} 2631 2632function validateTitle(rawTitle) { 2633 if (typeof rawTitle != "string" || !rawTitle) { 2634 return null; 2635 } 2636 return rawTitle.slice(0, DB_TITLE_LENGTH_MAX); 2637} 2638 2639function validateURL(rawURL) { 2640 if (typeof rawURL != "string" || rawURL.length > DB_URL_LENGTH_MAX) { 2641 return null; 2642 } 2643 let url = null; 2644 try { 2645 url = new URL(rawURL); 2646 } catch (ex) {} 2647 return url; 2648} 2649 2650function validateDescription(rawDescription) { 2651 if (typeof rawDescription != "string" || !rawDescription) { 2652 return null; 2653 } 2654 return rawDescription.slice(0, DB_DESCRIPTION_LENGTH_MAX); 2655} 2656 2657function validateKeyword(rawKeyword) { 2658 if (typeof rawKeyword != "string") { 2659 return null; 2660 } 2661 let keyword = rawKeyword.trim(); 2662 // Drop empty keywords. 2663 return keyword ? keyword.toLowerCase() : null; 2664} 2665 2666function validateTag(rawTag) { 2667 if (typeof rawTag != "string") { 2668 return null; 2669 } 2670 let tag = rawTag.trim(); 2671 if (!tag || tag.length > Ci.nsITaggingService.MAX_TAG_LENGTH) { 2672 // Drop empty and oversized tags. 2673 return null; 2674 } 2675 return tag; 2676} 2677 2678// Recursively inflates a bookmark tree from a pseudo-tree that maps 2679// parents to children. 2680async function inflateTree(tree, pseudoTree, parentGuid) { 2681 let nodes = pseudoTree.get(parentGuid); 2682 if (nodes) { 2683 for (let node of nodes) { 2684 await maybeYield(); 2685 tree.insert(parentGuid, node); 2686 await inflateTree(tree, pseudoTree, node.guid); 2687 } 2688 } 2689} 2690 2691/** 2692 * Content info for an item in the local or remote tree. This is used to dedupe 2693 * NEW local items to remote items that don't exist locally. See `contentsMatch` 2694 * for how we determine if two items are dupes. 2695 */ 2696class BookmarkContent { 2697 constructor(title, urlHref, smartBookmarkName, position) { 2698 this.title = title; 2699 this.url = urlHref ? new URL(urlHref) : null; 2700 this.smartBookmarkName = smartBookmarkName; 2701 this.position = position; 2702 } 2703 2704 static fromRow(row) { 2705 let title = row.getResultByName("title"); 2706 let urlHref = row.getResultByName("url"); 2707 let smartBookmarkName = row.getResultByName("smartBookmarkName"); 2708 let position = row.getResultByName("position"); 2709 return new BookmarkContent(title, urlHref, smartBookmarkName, position); 2710 } 2711 2712 hasSameURL(otherContent) { 2713 return !!this.url == !!otherContent.url && 2714 this.url.href == otherContent.url.href; 2715 } 2716} 2717 2718/** 2719 * The merge state indicates which node we should prefer when reconciling 2720 * with Places. Recall that a merged node may point to a local node, remote 2721 * node, or both. 2722 */ 2723class BookmarkMergeState { 2724 constructor(type, newStructureNode = null) { 2725 this.type = type; 2726 this.newStructureNode = newStructureNode; 2727 } 2728 2729 /** 2730 * Takes an existing value state, and a new node for the structure state. We 2731 * use the new merge state to resolve conflicts caused by moving local items 2732 * out of a remotely deleted folder, or remote items out of a locally deleted 2733 * folder. 2734 * 2735 * Applying a new merged node bumps its local change counter, so that the 2736 * merged structure is reuploaded to the server. 2737 * 2738 * @param {BookmarkMergeState} oldState 2739 * The existing value state. 2740 * @param {BookmarkNode} newStructureNode 2741 * A node to use for the new structure state. 2742 * @return {BookmarkMergeState} 2743 * The new merge state. 2744 */ 2745 static new(oldState, newStructureNode) { 2746 return new BookmarkMergeState(oldState.type, newStructureNode); 2747 } 2748 2749 // Returns the structure state type: `LOCAL`, `REMOTE`, or `NEW`. 2750 structure() { 2751 return this.newStructureNode ? BookmarkMergeState.TYPE.NEW : this.type; 2752 } 2753 2754 // Returns the value state type: `LOCAL` or `REMOTE`. 2755 value() { 2756 return this.type; 2757 } 2758 2759 /** 2760 * Returns a representation of the value ("V") and structure ("S") state 2761 * for logging. "L" is "local", "R" is "remote", and "+" is "new". We use 2762 * compact notation here to reduce noise in trace logs, which log the 2763 * merge state of every node in the tree. 2764 * 2765 * @return {String} 2766 */ 2767 toString() { 2768 return `(${this.valueToString()}; ${this.structureToString()})`; 2769 } 2770 2771 valueToString() { 2772 switch (this.value()) { 2773 case BookmarkMergeState.TYPE.LOCAL: 2774 return "V: L"; 2775 case BookmarkMergeState.TYPE.REMOTE: 2776 return "V: R"; 2777 } 2778 return "V: ?"; 2779 } 2780 2781 structureToString() { 2782 switch (this.structure()) { 2783 case BookmarkMergeState.TYPE.LOCAL: 2784 return "S: L"; 2785 case BookmarkMergeState.TYPE.REMOTE: 2786 return "S: R"; 2787 case BookmarkMergeState.TYPE.NEW: 2788 // We intentionally don't log the new structure node here, since 2789 // the merger already does that. 2790 return "S: +"; 2791 } 2792 return "S: ?"; 2793 } 2794 2795 toJSON() { 2796 return this.toString(); 2797 } 2798} 2799 2800BookmarkMergeState.TYPE = { 2801 LOCAL: 1, 2802 REMOTE: 2, 2803 NEW: 3, 2804}; 2805 2806/** 2807 * A local merge state means no changes: we keep the local value and structure 2808 * state. This could mean that the item doesn't exist on the server yet, or that 2809 * it has newer local changes that we should upload. 2810 * 2811 * It's an error for a merged node to have a local merge state without a local 2812 * node. Deciding the value state for the merged node asserts this. 2813 */ 2814BookmarkMergeState.local = new BookmarkMergeState( 2815 BookmarkMergeState.TYPE.LOCAL); 2816 2817/** 2818 * A remote merge state means we should update Places with new value and 2819 * structure state from the mirror. The item might not exist locally yet, or 2820 * might have newer remote changes that we should apply. 2821 * 2822 * As with local, a merged node can't have a remote merge state without a 2823 * remote node. 2824 */ 2825BookmarkMergeState.remote = new BookmarkMergeState( 2826 BookmarkMergeState.TYPE.REMOTE); 2827 2828/** 2829 * A node in a local or remote bookmark tree. Nodes are lightweight: they carry 2830 * enough information for the merger to resolve trivial conflicts without 2831 * querying the mirror or Places for the complete value state. 2832 */ 2833class BookmarkNode { 2834 constructor(guid, age, kind, needsMerge = false) { 2835 this.guid = guid; 2836 this.kind = kind; 2837 this.age = age; 2838 this.needsMerge = needsMerge; 2839 this.children = []; 2840 } 2841 2842 // Creates a virtual folder node for the Places root. 2843 static root() { 2844 let guid = PlacesUtils.bookmarks.rootGuid; 2845 return new BookmarkNode(guid, 0, SyncedBookmarksMirror.KIND.FOLDER); 2846 } 2847 2848 /** 2849 * Creates a bookmark node from a Places row. 2850 * 2851 * @param {mozIStorageRow} row 2852 * The Places row containing the node info. 2853 * @param {Number} localTimeSeconds 2854 * The current local time, in seconds, used to calculate the 2855 * item's age. 2856 * @return {BookmarkNode} 2857 * A bookmark node for the local item. 2858 */ 2859 static fromLocalRow(row, localTimeSeconds) { 2860 let guid = row.getResultByName("guid"); 2861 2862 // Note that this doesn't account for local clock skew. `localModified` 2863 // is in milliseconds. 2864 let localModified = row.getResultByName("localModified"); 2865 let age = Math.max(localTimeSeconds - localModified / 1000, 0) || 0; 2866 2867 let kind = row.getResultByName("kind"); 2868 2869 let syncChangeCounter = row.getResultByName("syncChangeCounter"); 2870 let needsMerge = syncChangeCounter > 0; 2871 2872 return new BookmarkNode(guid, age, kind, needsMerge); 2873 } 2874 2875 /** 2876 * Creates a bookmark node from a mirror row. 2877 * 2878 * @param {mozIStorageRow} row 2879 * The mirror row containing the node info. 2880 * @param {Number} remoteTimeSeconds 2881 * The current server time, in seconds, used to calculate the 2882 * item's age. 2883 * @return {BookmarkNode} 2884 * A bookmark node for the remote item. 2885 */ 2886 static fromRemoteRow(row, remoteTimeSeconds) { 2887 let guid = row.getResultByName("guid"); 2888 2889 // `serverModified` is in milliseconds. 2890 let serverModified = row.getResultByName("serverModified"); 2891 let age = Math.max(remoteTimeSeconds - serverModified / 1000, 0) || 0; 2892 2893 let kind = row.getResultByName("kind"); 2894 let needsMerge = !!row.getResultByName("needsMerge"); 2895 2896 return new BookmarkNode(guid, age, kind, needsMerge); 2897 } 2898 2899 isRoot() { 2900 return this.guid == PlacesUtils.bookmarks.rootGuid || 2901 PlacesUtils.bookmarks.userContentRoots.includes(this.guid); 2902 } 2903 2904 isFolder() { 2905 return this.kind == SyncedBookmarksMirror.KIND.FOLDER; 2906 } 2907 2908 newerThan(otherNode) { 2909 return this.age < otherNode.age; 2910 } 2911 2912 * descendants() { 2913 for (let node of this.children) { 2914 yield node; 2915 if (node.isFolder()) { 2916 yield* node.descendants(); 2917 } 2918 } 2919 } 2920 2921 /** 2922 * Generates a human-readable, ASCII art representation of the node and its 2923 * descendants. This is useful for visualizing the tree structure in trace 2924 * logs. 2925 * 2926 * @return {String} 2927 */ 2928 toASCIITreeString(prefix = "") { 2929 if (!this.isFolder()) { 2930 return prefix + "- " + this.toString(); 2931 } 2932 return prefix + "+ " + this.toString() + "\n" + this.children.map(childNode => 2933 childNode.toASCIITreeString(`${prefix}| `) 2934 ).join("\n"); 2935 } 2936 2937 /** 2938 * Returns a representation of the node for logging. This should be compact, 2939 * because the merger logs every local and remote node when trace logging is 2940 * enabled. 2941 * 2942 * @return {String} 2943 * A string in the form of "bookmarkAAAA (B; 1.234s; !)", where 2944 * "B" is the kind, "1.234s" is the age, and "!" indicates that the 2945 * node needs to be merged. 2946 */ 2947 toString() { 2948 let info = `${this.kindToString()}; ${this.age.toFixed(3)}s`; 2949 if (this.needsMerge) { 2950 info += "; !"; 2951 } 2952 return `${this.guid} (${info})`; 2953 } 2954 2955 kindToString() { 2956 switch (this.kind) { 2957 case SyncedBookmarksMirror.KIND.BOOKMARK: 2958 return "B"; 2959 case SyncedBookmarksMirror.KIND.QUERY: 2960 return "Q"; 2961 case SyncedBookmarksMirror.KIND.FOLDER: 2962 return "F"; 2963 case SyncedBookmarksMirror.KIND.LIVEMARK: 2964 return "L"; 2965 case SyncedBookmarksMirror.KIND.SEPARATOR: 2966 return "S"; 2967 } 2968 return "?"; 2969 } 2970 2971 // Used by `Log.jsm`. 2972 toJSON() { 2973 return this.toString(); 2974 } 2975} 2976 2977/** 2978 * A complete, rooted tree with tombstones. 2979 */ 2980class BookmarkTree { 2981 constructor(root) { 2982 this.byGuid = new Map(); 2983 this.infosByNode = new WeakMap(); 2984 this.deletedGuids = new Set(); 2985 2986 this.root = root; 2987 this.byGuid.set(this.root.guid, this.root); 2988 } 2989 2990 isDeleted(guid) { 2991 return this.deletedGuids.has(guid); 2992 } 2993 2994 nodeForGuid(guid) { 2995 return this.byGuid.get(guid); 2996 } 2997 2998 parentNodeFor(childNode) { 2999 let info = this.infosByNode.get(childNode); 3000 return info ? info.parentNode : null; 3001 } 3002 3003 levelForGuid(guid) { 3004 let node = this.byGuid.get(guid); 3005 if (!node) { 3006 return -1; 3007 } 3008 let info = this.infosByNode.get(node); 3009 return info ? info.level : -1; 3010 } 3011 3012 /** 3013 * Inserts a node into the tree. The node must not already exist in the tree, 3014 * and the node's parent must be a folder. 3015 */ 3016 insert(parentGuid, node) { 3017 if (this.byGuid.has(node.guid)) { 3018 let existingNode = this.byGuid.get(node.guid); 3019 MirrorLog.error("Can't replace existing node ${existingNode} with node " + 3020 "${node}", { existingNode, node }); 3021 throw new TypeError("Node already exists in tree"); 3022 } 3023 let parentNode = this.byGuid.get(parentGuid); 3024 if (!parentNode) { 3025 MirrorLog.error("Missing parent ${parentGuid} for node ${node}", 3026 { parentGuid, node }); 3027 throw new TypeError("Can't insert node into nonexistent parent"); 3028 } 3029 if (!parentNode.isFolder()) { 3030 MirrorLog.error("Non-folder parent ${parentNode} for node ${node}", 3031 { parentNode, node }); 3032 throw new TypeError("Can't insert node into non-folder"); 3033 } 3034 3035 parentNode.children.push(node); 3036 this.byGuid.set(node.guid, node); 3037 3038 let parentInfo = this.infosByNode.get(parentNode); 3039 let level = parentInfo ? parentInfo.level + 1 : 0; 3040 this.infosByNode.set(node, { parentNode, level }); 3041 } 3042 3043 noteDeleted(guid) { 3044 this.deletedGuids.add(guid); 3045 } 3046 3047 * guids() { 3048 for (let [guid, node] of this.byGuid) { 3049 if (node == this.root) { 3050 continue; 3051 } 3052 yield guid; 3053 } 3054 for (let guid of this.deletedGuids) { 3055 yield guid; 3056 } 3057 } 3058 3059 /** 3060 * Generates an ASCII art representation of the complete tree. Deleted GUIDs 3061 * are prefixed with "~". 3062 * 3063 * @return {String} 3064 */ 3065 toASCIITreeString() { 3066 return this.root.toASCIITreeString() + "\n" + Array.from(this.deletedGuids, 3067 guid => `~${guid}` 3068 ).join(", "); 3069 } 3070} 3071 3072/** 3073 * A node in a merged bookmark tree. Holds the local node, remote node, 3074 * merged children, and a merge state indicating which side to prefer. 3075 */ 3076class MergedBookmarkNode { 3077 constructor(guid, localNode, remoteNode, mergeState) { 3078 this.guid = guid; 3079 this.localNode = localNode; 3080 this.remoteNode = remoteNode; 3081 this.mergeState = mergeState; 3082 this.mergedChildren = []; 3083 } 3084 3085 /** 3086 * Yields the decided value and structure states of the merged node's 3087 * descendants. We use these as binding parameters to populate the temporary 3088 * `mergeStates` table when applying the merged tree to Places. 3089 */ 3090 * mergeStatesParams(level = 0) { 3091 for (let position = 0; position < this.mergedChildren.length; ++position) { 3092 let mergedChild = this.mergedChildren[position]; 3093 let mergeStateParam = { 3094 localGuid: mergedChild.localNode ? mergedChild.localNode.guid : null, 3095 // The merged GUID is different than the local GUID if we deduped a 3096 // NEW local item to a remote item. 3097 mergedGuid: mergedChild.guid, 3098 parentGuid: this.guid, 3099 level, 3100 position, 3101 valueState: mergedChild.mergeState.value(), 3102 structureState: mergedChild.mergeState.structure(), 3103 }; 3104 yield mergeStateParam; 3105 yield* mergedChild.mergeStatesParams(level + 1); 3106 } 3107 } 3108 3109 /** 3110 * Creates a bookmark node from this merged node. 3111 * 3112 * @return {BookmarkNode} 3113 * A node containing the decided value and structure state. 3114 */ 3115 async toBookmarkNode() { 3116 if (MergedBookmarkNode.cachedBookmarkNodes.has(this)) { 3117 return MergedBookmarkNode.cachedBookmarkNodes.get(this); 3118 } 3119 3120 let decidedValueNode = this.decidedValue(); 3121 let decidedStructureState = this.mergeState.structure(); 3122 let needsMerge = decidedStructureState == BookmarkMergeState.TYPE.NEW || 3123 (decidedStructureState == BookmarkMergeState.TYPE.LOCAL && 3124 decidedValueNode.needsMerge); 3125 3126 let newNode = new BookmarkNode(this.guid, decidedValueNode.age, 3127 decidedValueNode.kind, needsMerge); 3128 MergedBookmarkNode.cachedBookmarkNodes.set(this, newNode); 3129 3130 if (newNode.isFolder()) { 3131 for await (let mergedChildNode of yieldingIterator(this.mergedChildren)) { 3132 newNode.children.push(await mergedChildNode.toBookmarkNode()); 3133 } 3134 } 3135 3136 return newNode; 3137 } 3138 3139 /** 3140 * Decides the value state for the merged node. Note that you can't walk the 3141 * decided node's children: since the value node doesn't include structure 3142 * changes from the other side, you'll depart from the merged tree. You'll 3143 * want to use `toBookmarkNode` instead, which returns a node with the 3144 * decided value *and* structure. 3145 * 3146 * @return {BookmarkNode} 3147 * The local or remote node containing the decided value state. 3148 */ 3149 decidedValue() { 3150 let valueState = this.mergeState.value(); 3151 switch (valueState) { 3152 case BookmarkMergeState.TYPE.LOCAL: 3153 if (!this.localNode) { 3154 MirrorLog.error("Merged node ${guid} has local value state, but " + 3155 "no local node", this); 3156 throw new TypeError( 3157 "Can't take local value state without local node"); 3158 } 3159 return this.localNode; 3160 3161 case BookmarkMergeState.TYPE.REMOTE: 3162 if (!this.remoteNode) { 3163 MirrorLog.error("Merged node ${guid} has remote value state, but " + 3164 "no remote node", this); 3165 throw new TypeError( 3166 "Can't take remote value state without remote node"); 3167 } 3168 return this.remoteNode; 3169 } 3170 MirrorLog.error("Merged node ${guid} has unknown value state ${valueState}", 3171 { guid: this.guid, valueState }); 3172 throw new TypeError("Can't take unknown value state"); 3173 } 3174 3175 /** 3176 * Generates an ASCII art representation of the merged node and its 3177 * descendants. This is similar to the format generated by 3178 * `BookmarkNode#toASCIITreeString`, but logs value and structure states for 3179 * merged children. 3180 * 3181 * @return {String} 3182 */ 3183 toASCIITreeString(prefix = "") { 3184 if (!this.mergedChildren.length) { 3185 return prefix + "- " + this.toString(); 3186 } 3187 return prefix + "+ " + this.toString() + "\n" + this.mergedChildren.map( 3188 mergedChildNode => mergedChildNode.toASCIITreeString(`${prefix}| `) 3189 ).join("\n"); 3190 } 3191 3192 /** 3193 * Returns a representation of the merged node for logging. 3194 * 3195 * @return {String} 3196 * A string in the form of "bookmarkAAAA (V: R, S: R)", where 3197 * "V" is the value state and "R" is the structure state. 3198 */ 3199 toString() { 3200 return `${this.guid} ${this.mergeState.toString()}`; 3201 } 3202 3203 toJSON() { 3204 return this.toString(); 3205 } 3206} 3207 3208// Caches bookmark nodes containing the decided value and structure. 3209MergedBookmarkNode.cachedBookmarkNodes = new WeakMap(); 3210 3211/** 3212 * A two-way merger that produces a complete merged tree from a complete local 3213 * tree and a complete remote tree with changes since the last sync. 3214 * 3215 * This is ported almost directly from iOS. On iOS, the `ThreeWayMerger` takes a 3216 * complete "mirror" tree with the server state after the last sync, and two 3217 * incomplete trees with local and remote changes to the mirror: "local" and 3218 * "mirror", respectively. Overlaying buffer onto mirror yields the current 3219 * server tree; overlaying local onto mirror yields the complete local tree. 3220 * 3221 * On Desktop, our `localTree` is the union of iOS's mirror and local, and our 3222 * `remoteTree` is the union of iOS's mirror and buffer. Mapping the iOS 3223 * concepts to Desktop: 3224 * 3225 * - "Mirror" is approximately all `moz_bookmarks` where `syncChangeCounter = 0` 3226 * and `items` where `needsMerge = 0`. This is approximate because Desktop 3227 * doesn't store the shared parent for changed items. 3228 * - "Local" is all `moz_bookmarks` where `syncChangeCounter > 0`. 3229 * - "Buffer" is all `items` where `needsMerge = 1`. 3230 * 3231 * Since we don't store the shared parent, we can only do two-way merges. Also, 3232 * our merger doesn't distinguish between structure and value changes, since we 3233 * don't record that state in Places. The change counter notes *that* a bookmark 3234 * changed, but not *how*. This means we might choose the wrong side when 3235 * resolving merge conflicts, while iOS will do the right thing. 3236 * 3237 * Fortunately, most of our users don't organize their bookmarks into deeply 3238 * nested hierarchies, or make conflicting changes on multiple devices 3239 * simultaneously. Changing Places to record structure and value changes would 3240 * require significant changes to the storage schema. A simpler two-way tree 3241 * merge strikes a good balance between correctness and complexity. 3242 */ 3243class BookmarkMerger { 3244 constructor(localTree, newLocalContents, remoteTree, newRemoteContents) { 3245 this.localTree = localTree; 3246 this.newLocalContents = newLocalContents; 3247 this.remoteTree = remoteTree; 3248 this.newRemoteContents = newRemoteContents; 3249 this.mergedGuids = new Set(); 3250 this.deleteLocally = new Set(); 3251 this.deleteRemotely = new Set(); 3252 this.telemetryEvents = []; 3253 } 3254 3255 async merge() { 3256 let localRoot = this.localTree.nodeForGuid(PlacesUtils.bookmarks.rootGuid); 3257 let remoteRoot = this.remoteTree.nodeForGuid(PlacesUtils.bookmarks.rootGuid); 3258 let mergedRoot = await this.mergeNode(PlacesUtils.bookmarks.rootGuid, localRoot, 3259 remoteRoot); 3260 3261 // Any remaining deletions on one side should be deleted on the other side. 3262 // This happens when the remote tree has tombstones for items that don't 3263 // exist in Places, or Places has tombstones for items that aren't on the 3264 // server. 3265 for await (let guid of yieldingIterator(this.localTree.deletedGuids)) { 3266 if (!this.mentions(guid)) { 3267 this.deleteRemotely.add(guid); 3268 } 3269 } 3270 for await (let guid of yieldingIterator(this.remoteTree.deletedGuids)) { 3271 if (!this.mentions(guid)) { 3272 this.deleteLocally.add(guid); 3273 } 3274 } 3275 return mergedRoot; 3276 } 3277 3278 async subsumes(tree) { 3279 for await (let guid of Async.yieldingIterator(tree.guids())) { 3280 if (!this.mentions(guid)) { 3281 return false; 3282 } 3283 } 3284 return true; 3285 } 3286 3287 mentions(guid) { 3288 return this.mergedGuids.has(guid) || this.deleteLocally.has(guid) || 3289 this.deleteRemotely.has(guid); 3290 } 3291 3292 /** 3293 * Merges two nodes, recursively walking folders. 3294 * 3295 * @param {String} guid 3296 * The GUID to use for the merged node. 3297 * @param {BookmarkNode?} localNode 3298 * The local node. May be `null` if the node only exists remotely. 3299 * @param {BookmarkNode?} remoteNode 3300 * The remote node. May be `null` if the node only exists locally. 3301 * @return {MergedBookmarkNode} 3302 * The merged node, with merged folder children. 3303 */ 3304 async mergeNode(mergedGuid, localNode, remoteNode) { 3305 await maybeYield(); 3306 this.mergedGuids.add(mergedGuid); 3307 3308 if (localNode) { 3309 if (localNode.guid != mergedGuid) { 3310 // We deduped a NEW local item to a remote item. 3311 this.mergedGuids.add(localNode.guid); 3312 } 3313 3314 if (remoteNode) { 3315 MirrorLog.trace("Item ${mergedGuid} exists locally as ${localNode} " + 3316 "and remotely as ${remoteNode}; merging", 3317 { mergedGuid, localNode, remoteNode }); 3318 let mergedNode = await this.twoWayMerge(mergedGuid, localNode, remoteNode); 3319 return mergedNode; 3320 } 3321 3322 MirrorLog.trace("Item ${mergedGuid} only exists locally as " + 3323 "${localNode}; taking local state", { mergedGuid, 3324 localNode }); 3325 let mergedNode = new MergedBookmarkNode(mergedGuid, localNode, null, 3326 BookmarkMergeState.local); 3327 if (localNode.isFolder()) { 3328 // The local folder doesn't exist remotely, but its children might, so 3329 // we still need to recursively walk and merge them. This method will 3330 // change the merge state from local to new if any children were moved 3331 // or deleted. 3332 await this.mergeChildListsIntoMergedNode(mergedNode, localNode, 3333 /* remoteNode */ null); 3334 } 3335 return mergedNode; 3336 } 3337 3338 if (remoteNode) { 3339 MirrorLog.trace("Item ${mergedGuid} only exists remotely as " + 3340 "${remoteNode}; taking remote state", { mergedGuid, 3341 remoteNode }); 3342 let mergedNode = new MergedBookmarkNode(mergedGuid, null, remoteNode, 3343 BookmarkMergeState.remote); 3344 if (remoteNode.isFolder()) { 3345 // As above, a remote folder's children might still exist locally, so we 3346 // need to merge them and update the merge state from remote to new if 3347 // any children were moved or deleted. 3348 await this.mergeChildListsIntoMergedNode(mergedNode, /* localNode */ null, 3349 remoteNode); 3350 } 3351 return mergedNode; 3352 } 3353 3354 // Should never happen. We need to have at least one node for a two-way 3355 // merge. 3356 throw new TypeError("Can't merge two nonexistent nodes"); 3357 } 3358 3359 /** 3360 * Merges two nodes that exist locally and remotely. 3361 * 3362 * @param {String} mergedGuid 3363 * The GUID to use for the merged node. 3364 * @param {BookmarkNode} localNode 3365 * The existing local node. 3366 * @param {BookmarkNode} remoteNode 3367 * The existing remote node. 3368 * @return {MergedBookmarkNode} 3369 * The merged node, with merged folder children. 3370 */ 3371 async twoWayMerge(mergedGuid, localNode, remoteNode) { 3372 let mergeState = this.resolveTwoWayValueConflict(mergedGuid, localNode, 3373 remoteNode); 3374 MirrorLog.trace("Merge state for ${mergedGuid} is ${mergeState}", 3375 { mergedGuid, mergeState }); 3376 3377 let mergedNode = new MergedBookmarkNode(mergedGuid, localNode, remoteNode, 3378 mergeState); 3379 3380 if (localNode.isFolder()) { 3381 if (remoteNode.isFolder()) { 3382 // Merging two folders, so we need to walk their children to handle 3383 // structure changes. 3384 MirrorLog.trace("Merging folders ${localNode} and ${remoteNode}", 3385 { localNode, remoteNode }); 3386 await this.mergeChildListsIntoMergedNode(mergedNode, localNode, remoteNode); 3387 return mergedNode; 3388 } 3389 3390 if (remoteNode.kind == SyncedBookmarksMirror.KIND.LIVEMARK) { 3391 // We allow merging local folders and remote livemarks because Places 3392 // stores livemarks as empty folders with feed and site URL annotations. 3393 // The livemarks service first inserts the folder, and *then* sets 3394 // annotations. Since this isn't wrapped in a transaction, we might sync 3395 // before the annotations are set, and upload a folder record instead 3396 // of a livemark record (bug 632287), then replace the folder with a 3397 // livemark on the next sync. 3398 MirrorLog.trace("Merging local folder ${localNode} and remote " + 3399 "livemark ${remoteNode}", { localNode, remoteNode }); 3400 this.telemetryEvents.push({ 3401 value: "kind", 3402 extra: { local: "folder", remote: "folder" }, 3403 }); 3404 return mergedNode; 3405 } 3406 3407 MirrorLog.error("Merging local folder ${localNode} and remote " + 3408 "non-folder ${remoteNode}", { localNode, remoteNode }); 3409 throw new SyncedBookmarksMirror.ConsistencyError( 3410 "Can't merge folder and non-folder"); 3411 } 3412 3413 if (localNode.kind == remoteNode.kind) { 3414 // Merging two non-folders, so no need to walk children. 3415 MirrorLog.trace("Merging non-folders ${localNode} and ${remoteNode}", 3416 { localNode, remoteNode }); 3417 return mergedNode; 3418 } 3419 3420 MirrorLog.error("Merging local ${localNode} and remote ${remoteNode} " + 3421 "with different kinds", { localNode, remoteNode }); 3422 throw new SyncedBookmarksMirror.ConsistencyError( 3423 "Can't merge different item kinds"); 3424 } 3425 3426 /** 3427 * Determines the merge state for a node that exists locally and remotely. 3428 * 3429 * @param {String} mergedGuid 3430 * The GUID of the merged node. This is the same as the remote GUID, 3431 * and usually the same as the local GUID. The local GUID may be 3432 * different if we're deduping a local item to a remote item. 3433 * @param {String} localNode 3434 * The local bookmark node. 3435 * @param {BookmarkNode} remoteNode 3436 * The remote bookmark node. 3437 * @return {BookmarkMergeState} 3438 * The two-way merge state. 3439 */ 3440 resolveTwoWayValueConflict(mergedGuid, localNode, remoteNode) { 3441 if (PlacesUtils.bookmarks.userContentRoots.includes(mergedGuid)) { 3442 return BookmarkMergeState.local; 3443 } 3444 if (!remoteNode.needsMerge) { 3445 // The node wasn't changed remotely since the last sync. Keep the local 3446 // state. 3447 return BookmarkMergeState.local; 3448 } 3449 if (!localNode.needsMerge) { 3450 // The node was changed remotely, but not locally. Take the remote state. 3451 return BookmarkMergeState.remote; 3452 } 3453 // At this point, we know the item changed locally and remotely. We could 3454 // query storage to determine if the value state is the same, as iOS does. 3455 // However, that's an expensive check that requires joining `moz_bookmarks`, 3456 // `moz_items_annos`, and `moz_places` to the mirror. It's unlikely that 3457 // the value state is identical, so we skip the value check and use the 3458 // timestamp to decide which node is newer. 3459 let valueState = localNode.newerThan(remoteNode) ? 3460 BookmarkMergeState.local : 3461 BookmarkMergeState.remote; 3462 return valueState; 3463 } 3464 3465 /** 3466 * Merges a remote child node into a merged folder node. This handles the 3467 * following cases: 3468 * 3469 * - The remote child is locally deleted. We recursively move all of its 3470 * descendants that don't exist locally to the merged folder. 3471 * - The remote child doesn't exist locally, but has a content match in the 3472 * corresponding local folder. We dedupe the local child to the remote 3473 * child. 3474 * - The remote child exists locally, but in a different folder. We compare 3475 * merge flags and timestamps to decide where to keep the child. 3476 * - The remote child exists locally, and in the same folder. We merge the 3477 * local and remote children. 3478 * 3479 * This is the inverse of `mergeLocalChildIntoMergedNode`. 3480 * 3481 * @param {MergedBookmarkNode} mergedNode 3482 * The merged folder node. 3483 * @param {BookmarkNode} remoteParentNode 3484 * The remote folder node. 3485 * @param {BookmarkNode} remoteChildNode 3486 * The remote child node. 3487 * @return {Boolean} 3488 * `true` if the merged structure state changed because the remote 3489 * child was locally moved or deleted; `false` otherwise. 3490 */ 3491 async mergeRemoteChildIntoMergedNode(mergedNode, remoteParentNode, 3492 remoteChildNode) { 3493 if (this.mergedGuids.has(remoteChildNode.guid)) { 3494 MirrorLog.trace("Remote child ${remoteChildNode} already seen in " + 3495 "another folder and merged", { remoteChildNode }); 3496 return false; 3497 } 3498 3499 MirrorLog.trace("Merging remote child ${remoteChildNode} of " + 3500 "${remoteParentNode} into ${mergedNode}", 3501 { remoteChildNode, remoteParentNode, mergedNode }); 3502 3503 // Make sure the remote child isn't locally deleted. 3504 let structureChange = await this.checkForLocalStructureChangeOfRemoteNode( 3505 mergedNode, remoteParentNode, remoteChildNode); 3506 if (structureChange == BookmarkMerger.STRUCTURE.DELETED) { 3507 // If the remote child is locally deleted, we need to move all descendants 3508 // that aren't also remotely deleted to the merged node. This handles the 3509 // case where a user deletes a folder on this device, and adds a bookmark 3510 // to the same folder on another device. We want to keep the folder 3511 // deleted, but we also don't want to lose the new bookmark, so we move 3512 // the bookmark to the deleted folder's parent. 3513 return true; 3514 } 3515 3516 // The remote child isn't locally deleted. Does it exist in the local tree? 3517 let localChildNode = this.localTree.nodeForGuid(remoteChildNode.guid); 3518 if (!localChildNode) { 3519 // Remote child doesn't exist locally, either. Try to find a content 3520 // match in the containing folder, and dedupe the local item if we can. 3521 MirrorLog.trace("Remote child ${remoteChildNode} doesn't exist " + 3522 "locally; looking for content match", 3523 { remoteChildNode }); 3524 3525 let localChildNodeByContent = await this.findLocalNodeMatchingRemoteNode( 3526 mergedNode, remoteChildNode); 3527 3528 let mergedChildNode = await this.mergeNode(remoteChildNode.guid, 3529 localChildNodeByContent, 3530 remoteChildNode); 3531 mergedNode.mergedChildren.push(mergedChildNode); 3532 return false; 3533 } 3534 3535 // Otherwise, the remote child exists in the local tree. Did it move? 3536 let localParentNode = this.localTree.parentNodeFor(localChildNode); 3537 if (!localParentNode) { 3538 // Should never happen. The local tree must be complete. 3539 MirrorLog.error("Remote child ${remoteChildNode} exists locally as " + 3540 "${localChildNode} without local parent", 3541 { remoteChildNode, localChildNode }); 3542 throw new SyncedBookmarksMirror.ConsistencyError( 3543 "Local child node is orphan"); 3544 } 3545 3546 MirrorLog.trace("Remote child ${remoteChildNode} exists locally in " + 3547 "${localParentNode} and remotely in ${remoteParentNode}", 3548 { remoteChildNode, localParentNode, remoteParentNode }); 3549 3550 if (this.remoteTree.isDeleted(localParentNode.guid)) { 3551 MirrorLog.trace("Unconditionally taking remote move for " + 3552 "${remoteChildNode} to ${remoteParentNode} because " + 3553 "local parent ${localParentNode} is deleted remotely", 3554 { remoteChildNode, remoteParentNode, localParentNode }); 3555 3556 let mergedChildNode = await this.mergeNode(localChildNode.guid, 3557 localChildNode, remoteChildNode); 3558 mergedNode.mergedChildren.push(mergedChildNode); 3559 return false; 3560 } 3561 3562 if (localParentNode.needsMerge) { 3563 if (remoteParentNode.needsMerge) { 3564 MirrorLog.trace("Local ${localParentNode} and remote " + 3565 "${remoteParentNode} parents changed; comparing " + 3566 "modified times to decide parent for remote child " + 3567 "${remoteChildNode}", 3568 { localParentNode, remoteParentNode, remoteChildNode }); 3569 3570 let latestLocalAge = Math.min(localChildNode.age, 3571 localParentNode.age); 3572 let latestRemoteAge = Math.min(remoteChildNode.age, 3573 remoteParentNode.age); 3574 3575 if (latestLocalAge < latestRemoteAge) { 3576 // Local move is younger, so we ignore the remote move. We'll 3577 // merge the child later, when we walk its new local parent. 3578 MirrorLog.trace("Ignoring older remote move for ${remoteChildNode} " + 3579 "to ${remoteParentNode} at ${latestRemoteAge}; " + 3580 "local move to ${localParentNode} at " + 3581 "${latestLocalAge} is newer", 3582 { remoteChildNode, remoteParentNode, latestRemoteAge, 3583 localParentNode, latestLocalAge }); 3584 return true; 3585 } 3586 3587 // Otherwise, the remote move is younger, so we ignore the local move 3588 // and merge the child now. 3589 MirrorLog.trace("Taking newer remote move for ${remoteChildNode} to " + 3590 "${remoteParentNode} at ${latestRemoteAge}; local " + 3591 "move to ${localParentNode} at ${latestLocalAge} is " + 3592 "older", { remoteChildNode, remoteParentNode, 3593 latestRemoteAge, localParentNode, 3594 latestLocalAge }); 3595 3596 let mergedChildNode = await this.mergeNode(remoteChildNode.guid, 3597 localChildNode, remoteChildNode); 3598 mergedNode.mergedChildren.push(mergedChildNode); 3599 return false; 3600 } 3601 3602 MirrorLog.trace("Remote parent unchanged; keeping remote child " + 3603 "${remoteChildNode} in ${localParentNode}", 3604 { remoteChildNode, localParentNode }); 3605 return true; 3606 } 3607 3608 MirrorLog.trace("Local parent unchanged; keeping remote child " + 3609 "${remoteChildNode} in ${remoteParentNode}", 3610 { remoteChildNode, remoteParentNode }); 3611 3612 let mergedChildNode = await this.mergeNode(remoteChildNode.guid, localChildNode, 3613 remoteChildNode); 3614 mergedNode.mergedChildren.push(mergedChildNode); 3615 return false; 3616 } 3617 3618 /** 3619 * Merges a local child node into a merged folder node. 3620 * 3621 * This is the inverse of `mergeRemoteChildIntoMergedNode`. 3622 * 3623 * @param {MergedBookmarkNode} mergedNode 3624 * The merged folder node. 3625 * @param {BookmarkNode} localParentNode 3626 * The local folder node. 3627 * @param {BookmarkNode} localChildNode 3628 * The local child node. 3629 * @return {Boolean} 3630 * `true` if the merged structure state changed because the local 3631 * child doesn't exist remotely or was locally moved; `false` 3632 * otherwise. 3633 */ 3634 async mergeLocalChildIntoMergedNode(mergedNode, localParentNode, localChildNode) { 3635 if (this.mergedGuids.has(localChildNode.guid)) { 3636 // We already merged the child when we walked another folder. 3637 MirrorLog.trace("Local child ${localChildNode} already seen in " + 3638 "another folder and merged", { localChildNode }); 3639 return false; 3640 } 3641 3642 MirrorLog.trace("Merging local child ${localChildNode} of " + 3643 "${localParentNode} into ${mergedNode}", 3644 { localChildNode, localParentNode, mergedNode }); 3645 3646 // Now, we know we haven't seen the local child before, and it's not in 3647 // this folder on the server. Check if the child is remotely deleted. 3648 let structureChange = await this.checkForRemoteStructureChangeOfLocalNode( 3649 mergedNode, localParentNode, localChildNode); 3650 if (structureChange == BookmarkMerger.STRUCTURE.DELETED) { 3651 // If the child is remotely deleted, we need to move any new local 3652 // descendants to the merged node, just as we did for new remote 3653 // descendants of locally deleted children. 3654 return true; 3655 } 3656 3657 // At this point, we know the local child isn't deleted. See if it 3658 // exists in the remote tree. 3659 let remoteChildNode = this.remoteTree.nodeForGuid(localChildNode.guid); 3660 if (!remoteChildNode) { 3661 // The local child doesn't exist remotely, but we still need to walk 3662 // its children. 3663 let mergedChildNode = await this.mergeNode(localChildNode.guid, localChildNode, 3664 /* remoteChildNode */ null); 3665 mergedNode.mergedChildren.push(mergedChildNode); 3666 return true; 3667 } 3668 3669 // The local child exists remotely. It must have moved; otherwise, we 3670 // would have seen it when we walked the remote children. 3671 let remoteParentNode = this.remoteTree.parentNodeFor(remoteChildNode); 3672 if (!remoteParentNode) { 3673 // Should never happen. The remote tree must be complete. 3674 MirrorLog.error("Local child ${localChildNode} exists remotely as " + 3675 "${remoteChildNode} without remote parent", 3676 { localChildNode, remoteChildNode }); 3677 throw new SyncedBookmarksMirror.ConsistencyError( 3678 "Remote child node is orphan"); 3679 } 3680 3681 MirrorLog.trace("Local child ${localChildNode} exists locally in " + 3682 "${localParentNode} and remotely in ${remoteParentNode}", 3683 { localChildNode, localParentNode, remoteParentNode }); 3684 3685 if (this.localTree.isDeleted(remoteParentNode.guid)) { 3686 MirrorLog.trace("Unconditionally taking local move for " + 3687 "${localChildNode} to ${localParentNode} because " + 3688 "remote parent ${remoteParentNode} is deleted locally", 3689 { localChildNode, localParentNode, remoteParentNode }); 3690 3691 let mergedChildNode = await this.mergeNode(localChildNode.guid, 3692 localChildNode, remoteChildNode); 3693 mergedNode.mergedChildren.push(mergedChildNode); 3694 return true; 3695 } 3696 3697 if (localParentNode.needsMerge) { 3698 if (remoteParentNode.needsMerge) { 3699 MirrorLog.trace("Local ${localParentNode} and remote " + 3700 "${remoteParentNode} parents changed; comparing " + 3701 "modified times to decide parent for local child " + 3702 "${localChildNode}", { localParentNode, 3703 remoteParentNode, 3704 localChildNode }); 3705 3706 let latestLocalAge = Math.min(localChildNode.age, 3707 localParentNode.age); 3708 let latestRemoteAge = Math.min(remoteChildNode.age, 3709 remoteParentNode.age); 3710 3711 if (latestRemoteAge <= latestLocalAge) { 3712 MirrorLog.trace("Ignoring older local move for ${localChildNode} " + 3713 "to ${localParentNode} at ${latestLocalAge}; " + 3714 "remote move to ${remoteParentNode} at " + 3715 "${latestRemoteAge} is newer", 3716 { localChildNode, localParentNode, latestLocalAge, 3717 remoteParentNode, latestRemoteAge }); 3718 return false; 3719 } 3720 3721 MirrorLog.trace("Taking newer local move for ${localChildNode} to " + 3722 "${localParentNode} at ${latestLocalAge}; remote " + 3723 "move to ${remoteParentNode} at ${latestRemoteAge} " + 3724 "is older", { localChildNode, localParentNode, 3725 latestLocalAge, remoteParentNode, 3726 latestRemoteAge }); 3727 3728 let mergedChildNode = await this.mergeNode(localChildNode.guid, 3729 localChildNode, remoteChildNode); 3730 mergedNode.mergedChildren.push(mergedChildNode); 3731 return true; 3732 } 3733 3734 MirrorLog.trace("Remote parent unchanged; keeping local child " + 3735 "${localChildNode} in local parent ${localParentNode}", 3736 { localChildNode, localParentNode }); 3737 3738 let mergedChildNode = await this.mergeNode(localChildNode.guid, localChildNode, 3739 remoteChildNode); 3740 mergedNode.mergedChildren.push(mergedChildNode); 3741 return true; 3742 } 3743 3744 MirrorLog.trace("Local parent unchanged; keeping local child " + 3745 "${localChildNode} in remote parent ${remoteParentNode}", 3746 { localChildNode, remoteParentNode }); 3747 return false; 3748 } 3749 3750 /** 3751 * Recursively merges the children of a local folder node and a matching 3752 * remote folder node. 3753 * 3754 * @param {MergedBookmarkNode} mergedNode 3755 * The merged folder node. This method mutates the merged node to 3756 * append local and remote children, and sets a new merge state 3757 * state if needed. 3758 * @param {BookmarkNode?} localNode 3759 * The local folder node. May be `null` if the folder only exists 3760 * remotely. 3761 * @param {BookmarkNode?} remoteNode 3762 * The remote folder node. May be `null` if the folder only exists 3763 * locally. 3764 */ 3765 async mergeChildListsIntoMergedNode(mergedNode, localNode, remoteNode) { 3766 let mergeStateChanged = false; 3767 3768 if (localNode && remoteNode) { 3769 if (localNode.newerThan(remoteNode)) { 3770 // The folder exists locally and remotely, and the local node is newer. 3771 // Walk and merge local children first, followed by remaining unmerged 3772 // remote children. 3773 if (await this.mergeLocalChildrenIntoMergedNode(mergedNode, localNode)) { 3774 mergeStateChanged = true; 3775 } 3776 if (await this.mergeRemoteChildrenIntoMergedNode(mergedNode, remoteNode)) { 3777 mergeStateChanged = true; 3778 } 3779 } else { 3780 // The folder exists locally and remotely, and the remote node is newer. 3781 // Merge remote children first, then remaining local children. 3782 if (await this.mergeRemoteChildrenIntoMergedNode(mergedNode, remoteNode)) { 3783 mergeStateChanged = true; 3784 } 3785 if (await this.mergeLocalChildrenIntoMergedNode(mergedNode, localNode)) { 3786 mergeStateChanged = true; 3787 } 3788 } 3789 } else if (localNode) { 3790 // The folder only exists locally, so no remote children to merge. 3791 if (await this.mergeLocalChildrenIntoMergedNode(mergedNode, localNode)) { 3792 mergeStateChanged = true; 3793 } 3794 } else if (remoteNode) { 3795 // The folder only exists remotely, so local children to merge. 3796 if (await this.mergeRemoteChildrenIntoMergedNode(mergedNode, remoteNode)) { 3797 mergeStateChanged = true; 3798 } 3799 } else { 3800 // Should never happen. 3801 throw new TypeError("Can't merge children for two nonexistent nodes"); 3802 } 3803 3804 // Update the merge state if we moved children orphaned on one side by a 3805 // deletion on the other side, if we kept newer locally moved children, 3806 // or if the child order changed. We already updated the merge state of the 3807 // orphans, but we also need to flag the containing folder so that it's 3808 // reuploaded to the server along with the new children. 3809 if (mergeStateChanged) { 3810 let newStructureNode = await mergedNode.toBookmarkNode(); 3811 let newMergeState = BookmarkMergeState.new(mergedNode.mergeState, 3812 newStructureNode); 3813 MirrorLog.trace("Merge state for ${mergedNode} has new structure " + 3814 "${newMergeState}", { mergedNode, newMergeState }); 3815 this.telemetryEvents.push({ 3816 value: "structure", 3817 extra: { type: "new" }, 3818 }); 3819 mergedNode.mergeState = newMergeState; 3820 } 3821 } 3822 3823 /** 3824 * Recursively merges the children of a remote folder node. 3825 * 3826 * @param {MergedBookmarkNode} mergedNode 3827 * The merged folder node. This method mutates the merged node to 3828 * append remote children. 3829 * @param {BookmarkNode} remoteNode 3830 * The remote folder node. 3831 * @return {Boolean} 3832 * `true` if the merge produced a new structure that should be 3833 * reuploaded to the server; `false` otherwise. 3834 */ 3835 async mergeRemoteChildrenIntoMergedNode(mergedNode, remoteNode) { 3836 MirrorLog.trace("Merging remote children of ${remoteNode} into " + 3837 "${mergedNode}", { remoteNode, mergedNode }); 3838 3839 let mergeStateChanged = false; 3840 for await (let remoteChildNode of yieldingIterator(remoteNode.children)) { 3841 let remoteChildrenChanged = await this.mergeRemoteChildIntoMergedNode( 3842 mergedNode, remoteNode, remoteChildNode); 3843 if (remoteChildrenChanged) { 3844 mergeStateChanged = true; 3845 } 3846 } 3847 return mergeStateChanged; 3848 } 3849 3850 /** 3851 * Recursively merges the children of a local folder node. 3852 * 3853 * @param {MergedBookmarkNode} mergedNode 3854 * The merged folder node. This method mutates the merged node to 3855 * append local children. 3856 * @param {BookmarkNode} localNode 3857 * The local folder node. 3858 * @return {Boolean} 3859 * `true` if the merge produced a new structure that should be 3860 * reuploaded to the server; `false` otherwise. 3861 */ 3862 async mergeLocalChildrenIntoMergedNode(mergedNode, localNode) { 3863 MirrorLog.trace("Merging local children of ${localNode} into " + 3864 "${mergedNode}", { localNode, mergedNode }); 3865 3866 let mergeStateChanged = false; 3867 for await (let localChildNode of yieldingIterator(localNode.children)) { 3868 let remoteChildrenChanged = await this.mergeLocalChildIntoMergedNode( 3869 mergedNode, localNode, localChildNode); 3870 if (remoteChildrenChanged) { 3871 mergeStateChanged = true; 3872 } 3873 } 3874 return mergeStateChanged; 3875 } 3876 3877 /** 3878 * Checks if a remote node is locally moved or deleted, and reparents any 3879 * descendants that aren't also remotely deleted to the merged node. 3880 * 3881 * This is the inverse of `checkForRemoteStructureChangeOfLocalNode`. 3882 * 3883 * @param {MergedBookmarkNode} mergedNode 3884 * The merged folder node to hold relocated remote orphans. 3885 * @param {BookmarkNode} remoteParentNode 3886 * The remote parent of the potentially deleted child node. 3887 * @param {BookmarkNode} remoteNode 3888 * The remote potentially deleted child node. 3889 * @return {BookmarkMerger.STRUCTURE} 3890 * A structure change type: `UNCHANGED` if the remote node is not 3891 * deleted or doesn't exist locally, `MOVED` if the node is moved 3892 * locally, or `DELETED` if the node is deleted locally. 3893 */ 3894 async checkForLocalStructureChangeOfRemoteNode(mergedNode, remoteParentNode, 3895 remoteNode) { 3896 if (!this.localTree.isDeleted(remoteNode.guid)) { 3897 let localNode = this.localTree.nodeForGuid(remoteNode.guid); 3898 if (!localNode) { 3899 return BookmarkMerger.STRUCTURE.UNCHANGED; 3900 } 3901 let localParentNode = this.localTree.parentNodeFor(localNode); 3902 if (!localParentNode) { 3903 // Should never happen. The local tree must be complete. 3904 throw new SyncedBookmarksMirror.ConsistencyError( 3905 "Can't check for structure changes of local orphan"); 3906 } 3907 if (localParentNode.guid != remoteParentNode.guid) { 3908 return BookmarkMerger.STRUCTURE.MOVED; 3909 } 3910 return BookmarkMerger.STRUCTURE.UNCHANGED; 3911 } 3912 3913 if (remoteNode.needsMerge) { 3914 if (!remoteNode.isFolder()) { 3915 // If a non-folder child is deleted locally and changed remotely, we 3916 // ignore the local deletion and take the remote child. 3917 MirrorLog.trace("Remote non-folder ${remoteNode} deleted locally " + 3918 "and changed remotely; taking remote change", 3919 { remoteNode }); 3920 this.telemetryEvents.push({ 3921 value: "structure", 3922 extra: { type: "delete", kind: "item", prefer: "remote" }, 3923 }); 3924 return BookmarkMerger.STRUCTURE.UNCHANGED; 3925 } 3926 // For folders, we always take the local deletion and relocate remotely 3927 // changed grandchildren to the merged node. We could use the mirror to 3928 // revive the child folder, but it's easier to relocate orphaned 3929 // grandchildren than to partially revive the child folder. 3930 MirrorLog.trace("Remote folder ${remoteNode} deleted locally " + 3931 "and changed remotely; taking local deletion", 3932 { remoteNode }); 3933 this.telemetryEvents.push({ 3934 value: "structure", 3935 extra: { type: "delete", kind: "folder", prefer: "local" }, 3936 }); 3937 } else { 3938 MirrorLog.trace("Remote node ${remoteNode} deleted locally and not " + 3939 "changed remotely; taking local deletion", 3940 { remoteNode }); 3941 } 3942 3943 this.deleteRemotely.add(remoteNode.guid); 3944 3945 let mergedOrphanNodes = await this.processRemoteOrphansForNode(mergedNode, 3946 remoteNode); 3947 await this.relocateOrphansTo(mergedNode, mergedOrphanNodes); 3948 MirrorLog.trace("Relocating remote orphans ${mergedOrphanNodes} to " + 3949 "${mergedNode}", { mergedOrphanNodes, mergedNode }); 3950 3951 return BookmarkMerger.STRUCTURE.DELETED; 3952 } 3953 3954 /** 3955 * Checks if a local node is remotely moved or deleted, and reparents any 3956 * descendants that aren't also locally deleted to the merged node. 3957 * 3958 * This is the inverse of `checkForLocalStructureChangeOfRemoteNode`. 3959 * 3960 * @param {MergedBookmarkNode} mergedNode 3961 * The merged folder node to hold relocated local orphans. 3962 * @param {BookmarkNode} localParentNode 3963 * The local parent of the potentially deleted child node. 3964 * @param {BookmarkNode} localNode 3965 * The local potentially deleted child node. 3966 * @return {BookmarkMerger.STRUCTURE} 3967 * A structure change type: `UNCHANGED` if the local node is not 3968 * deleted or doesn't exist remotely, `MOVED` if the node is moved 3969 * remotely, or `DELETED` if the node is deleted remotely. 3970 */ 3971 async checkForRemoteStructureChangeOfLocalNode(mergedNode, localParentNode, 3972 localNode) { 3973 if (!this.remoteTree.isDeleted(localNode.guid)) { 3974 let remoteNode = this.remoteTree.nodeForGuid(localNode.guid); 3975 if (!remoteNode) { 3976 return BookmarkMerger.STRUCTURE.UNCHANGED; 3977 } 3978 let remoteParentNode = this.remoteTree.parentNodeFor(remoteNode); 3979 if (!remoteParentNode) { 3980 // Should never happen. The remote tree must be complete. 3981 throw new SyncedBookmarksMirror.ConsistencyError( 3982 "Can't check for structure changes of remote orphan"); 3983 } 3984 if (remoteParentNode.guid != localParentNode.guid) { 3985 return BookmarkMerger.STRUCTURE.MOVED; 3986 } 3987 return BookmarkMerger.STRUCTURE.UNCHANGED; 3988 } 3989 3990 if (localNode.needsMerge) { 3991 if (!localNode.isFolder()) { 3992 MirrorLog.trace("Local non-folder ${localNode} deleted remotely and " + 3993 "changed locally; taking local change", { localNode }); 3994 this.telemetryEvents.push({ 3995 value: "structure", 3996 extra: { type: "delete", kind: "item", prefer: "local" }, 3997 }); 3998 return BookmarkMerger.STRUCTURE.UNCHANGED; 3999 } 4000 MirrorLog.trace("Local folder ${localNode} deleted remotely and " + 4001 "changed locally; taking remote deletion", { localNode }); 4002 this.telemetryEvents.push({ 4003 value: "structure", 4004 extra: { type: "delete", kind: "folder", prefer: "remote" }, 4005 }); 4006 } else { 4007 MirrorLog.trace("Local node ${localNode} deleted remotely and not " + 4008 "changed locally; taking remote deletion", { localNode }); 4009 } 4010 4011 MirrorLog.trace("Local node ${localNode} deleted remotely; taking remote " + 4012 "deletion", { localNode }); 4013 4014 this.deleteLocally.add(localNode.guid); 4015 4016 let mergedOrphanNodes = await this.processLocalOrphansForNode(mergedNode, 4017 localNode); 4018 await this.relocateOrphansTo(mergedNode, mergedOrphanNodes); 4019 MirrorLog.trace("Relocating local orphans ${mergedOrphanNodes} to " + 4020 "${mergedNode}", { mergedOrphanNodes, mergedNode }); 4021 4022 return BookmarkMerger.STRUCTURE.DELETED; 4023 } 4024 4025 /** 4026 * Recursively merges all remote children of a locally deleted folder that 4027 * haven't also been deleted remotely. This can happen if the user adds a 4028 * bookmark to a folder on another device, and deletes that folder locally. 4029 * This is the inverse of `processLocalOrphansForNode`. 4030 */ 4031 async processRemoteOrphansForNode(mergedNode, remoteNode) { 4032 let remoteOrphanNodes = []; 4033 4034 for await (let remoteChildNode of yieldingIterator(remoteNode.children)) { 4035 let structureChange = await this.checkForLocalStructureChangeOfRemoteNode( 4036 mergedNode, remoteNode, remoteChildNode); 4037 if (structureChange == BookmarkMerger.STRUCTURE.MOVED || 4038 structureChange == BookmarkMerger.STRUCTURE.DELETED) { 4039 // The remote child is already moved or deleted locally, so we should 4040 // ignore it instead of treating it as a remote orphan. 4041 continue; 4042 } 4043 remoteOrphanNodes.push(remoteChildNode); 4044 } 4045 4046 let mergedOrphanNodes = []; 4047 for await (let remoteOrphanNode of yieldingIterator(remoteOrphanNodes)) { 4048 let localOrphanNode = this.localTree.nodeForGuid(remoteOrphanNode.guid); 4049 let mergedOrphanNode = await this.mergeNode(remoteOrphanNode.guid, 4050 localOrphanNode, remoteOrphanNode); 4051 mergedOrphanNodes.push(mergedOrphanNode); 4052 } 4053 4054 return mergedOrphanNodes; 4055 } 4056 4057 /** 4058 * Recursively merges all local children of a remotely deleted folder that 4059 * haven't also been deleted locally. This is the inverse of 4060 * `processRemoteOrphansForNode`. 4061 */ 4062 async processLocalOrphansForNode(mergedNode, localNode) { 4063 if (!localNode.isFolder()) { 4064 // The local node isn't a folder, so it won't have orphans. 4065 return []; 4066 } 4067 4068 let localOrphanNodes = []; 4069 for await (let localChildNode of yieldingIterator(localNode.children)) { 4070 let structureChange = await this.checkForRemoteStructureChangeOfLocalNode( 4071 mergedNode, localNode, localChildNode); 4072 if (structureChange == BookmarkMerger.STRUCTURE.MOVED || 4073 structureChange == BookmarkMerger.STRUCTURE.DELETED) { 4074 // The local child is already moved or deleted remotely, so we should 4075 // ignore it instead of treating it as a local orphan. 4076 continue; 4077 } 4078 localOrphanNodes.push(localChildNode); 4079 } 4080 4081 let mergedOrphanNodes = []; 4082 for await (let localOrphanNode of yieldingIterator(localOrphanNodes)) { 4083 let remoteOrphanNode = this.remoteTree.nodeForGuid(localOrphanNode.guid); 4084 let mergedNode = await this.mergeNode(localOrphanNode.guid, 4085 localOrphanNode, remoteOrphanNode); 4086 mergedOrphanNodes.push(mergedNode); 4087 } 4088 4089 return mergedOrphanNodes; 4090 } 4091 4092 /** 4093 * Moves a list of merged orphan nodes to the closest surviving ancestor. 4094 * Changes the merge state of the moved orphans to new, so that we reupload 4095 * them along with their new parent on the next sync. 4096 * 4097 * @param {MergedBookmarkNode} mergedNode 4098 * The closest surviving ancestor. 4099 * @param {MergedBookmarkNode[]} mergedOrphanNodes 4100 * Merged orphans to relocate to the surviving ancestor. 4101 */ 4102 async relocateOrphansTo(mergedNode, mergedOrphanNodes) { 4103 for (let mergedOrphanNode of mergedOrphanNodes) { 4104 let newStructureNode = await mergedOrphanNode.toBookmarkNode(); 4105 let newMergeState = BookmarkMergeState.new(mergedOrphanNode.mergeState, 4106 newStructureNode); 4107 mergedOrphanNode.mergeState = newMergeState; 4108 mergedNode.mergedChildren.push(mergedOrphanNode); 4109 } 4110 } 4111 4112 /** 4113 * Finds a local node with a different GUID that matches the content of a 4114 * remote node. This is used to dedupe local items that haven't been uploaded 4115 * to remote items that don't exist locally. 4116 * 4117 * @param {MergedBookmarkNode} mergedNode 4118 * The merged folder node. 4119 * @param {BookmarkNode} remoteChildNode 4120 * The remote child node. 4121 * @return {BookmarkNode?} 4122 * A matching local child node, or `null` if there are no matching 4123 * local items. 4124 */ 4125 async findLocalNodeMatchingRemoteNode(mergedNode, remoteChildNode) { 4126 let localParentNode = mergedNode.localNode; 4127 if (!localParentNode) { 4128 MirrorLog.trace("Merged node ${mergedNode} doesn't exist locally; no " + 4129 "potential dupes for ${remoteChildNode}", 4130 { mergedNode, remoteChildNode }); 4131 return null; 4132 } 4133 let remoteChildContent = this.newRemoteContents.get(remoteChildNode.guid); 4134 if (!remoteChildContent) { 4135 // The node doesn't exist locally, but it's also flagged as merged in the 4136 // mirror. 4137 return null; 4138 } 4139 let newLocalNode = null; 4140 for await (let localChildNode of yieldingIterator(localParentNode.children)) { 4141 if (this.mergedGuids.has(localChildNode.guid)) { 4142 MirrorLog.trace("Not deduping ${localChildNode}; already seen in " + 4143 "another folder", { localChildNode }); 4144 continue; 4145 } 4146 if (!this.newLocalContents.has(localChildNode.guid)) { 4147 MirrorLog.trace("Not deduping ${localChildNode}; already uploaded", 4148 { localChildNode }); 4149 continue; 4150 } 4151 let remoteCandidate = this.remoteTree.nodeForGuid(localChildNode.guid); 4152 if (remoteCandidate) { 4153 MirrorLog.trace("Not deduping ${localChildNode}; already exists " + 4154 "remotely", { localChildNode }); 4155 continue; 4156 } 4157 if (this.remoteTree.isDeleted(localChildNode.guid)) { 4158 MirrorLog.trace("Not deduping ${localChildNode}; deleted on server", 4159 { localChildNode }); 4160 continue; 4161 } 4162 let localChildContent = this.newLocalContents.get(localChildNode.guid); 4163 if (!contentsMatch(localChildNode, localChildContent, remoteChildNode, 4164 remoteChildContent)) { 4165 MirrorLog.trace("${localChildNode} is not a dupe of ${remoteChildNode}", 4166 { localChildNode, remoteChildNode }); 4167 continue; 4168 } 4169 this.telemetryEvents.push({ value: "dupe" }); 4170 newLocalNode = localChildNode; 4171 break; 4172 } 4173 return newLocalNode; 4174 } 4175 4176 /** 4177 * Returns an array of local ("L: ~bookmarkAAAA, ~bookmarkBBBB") and remote 4178 * ("R: ~bookmarkCCCC, ~bookmarkDDDD") deletions for logging. 4179 * 4180 * @return {String[]} 4181 */ 4182 deletionsToStrings() { 4183 let infos = []; 4184 if (this.deleteLocally.size) { 4185 infos.push("L: " + Array.from(this.deleteLocally, 4186 guid => `~${guid}`).join(", ")); 4187 } 4188 if (this.deleteRemotely.size) { 4189 infos.push("R: " + Array.from(this.deleteRemotely, 4190 guid => `~${guid}`).join(", ")); 4191 } 4192 return infos; 4193 } 4194} 4195 4196/** 4197 * Structure change types, used to indicate if a node on one side is moved 4198 * or deleted on the other. 4199 */ 4200BookmarkMerger.STRUCTURE = { 4201 UNCHANGED: 1, 4202 MOVED: 2, 4203 DELETED: 3, 4204}; 4205 4206/** 4207 * Determines if two new local and remote nodes are of the same kind, and have 4208 * similar contents. 4209 * 4210 * - Bookmarks must have the same title and URL. 4211 * - Smart bookmarks must have the same smart bookmark name. Other queries 4212 * must have the same title and query URL. 4213 * - Folders and livemarks must have the same title. 4214 * - Separators must have the same position within their parents. 4215 * 4216 * @param {BookmarkNode} localNode 4217 * @param {BookmarkContent} localContent 4218 * @param {BookmarkNode} remoteNode 4219 * @param {BookmarkContent} remoteContent 4220 * @return {Boolean} 4221 */ 4222function contentsMatch(localNode, localContent, remoteNode, remoteContent) { 4223 if (localNode.kind != remoteNode.kind) { 4224 return false; 4225 } 4226 switch (localNode.kind) { 4227 case SyncedBookmarksMirror.KIND.BOOKMARK: 4228 return localContent.title == remoteContent.title && 4229 localContent.hasSameURL(remoteContent); 4230 4231 case SyncedBookmarksMirror.KIND.QUERY: 4232 if (localContent.smartBookmarkName || remoteContent.smartBookmarkName) { 4233 return localContent.smartBookmarkName == 4234 remoteContent.smartBookmarkName; 4235 } 4236 return localContent.title == remoteContent.title && 4237 localContent.hasSameURL(remoteContent); 4238 4239 case SyncedBookmarksMirror.KIND.FOLDER: 4240 case SyncedBookmarksMirror.KIND.LIVEMARK: 4241 return localContent.title == remoteContent.title; 4242 4243 case SyncedBookmarksMirror.KIND.SEPARATOR: 4244 return localContent.position == remoteContent.position; 4245 } 4246 return false; 4247} 4248 4249/** 4250 * Records bookmark, annotation, and keyword observer notifications for all 4251 * changes made during the merge, then fires the notifications after the merge 4252 * is done. 4253 * 4254 * Recording bookmark changes and deletions is somewhat expensive, because we 4255 * need to fetch all observer infos before writing. Making this more efficient 4256 * is tracked in bug 1340498. 4257 * 4258 * Annotation observers don't require the extra context, so they're cheap to 4259 * record and fire. 4260 */ 4261class BookmarkObserverRecorder { 4262 constructor(db) { 4263 this.db = db; 4264 this.bookmarkObserverNotifications = []; 4265 this.annoObserverNotifications = []; 4266 this.shouldInvalidateKeywords = false; 4267 this.shouldInvalidateLivemarks = false; 4268 } 4269 4270 /** 4271 * Fires all recorded observer notifications, invalidates the livemark cache 4272 * if necessary, and recalculates frecencies for changed URLs. This is called 4273 * outside the merge transaction. 4274 */ 4275 async notifyAll() { 4276 if (this.shouldInvalidateKeywords) { 4277 await PlacesUtils.keywords.invalidateCachedKeywords(); 4278 } 4279 await this.notifyBookmarkObservers(); 4280 await this.notifyAnnoObservers(); 4281 if (this.shouldInvalidateLivemarks) { 4282 await PlacesUtils.livemarks.invalidateCachedLivemarks(); 4283 } 4284 await this.updateFrecencies(); 4285 } 4286 4287 async updateFrecencies() { 4288 MirrorLog.debug("Recalculating frecencies for new URLs"); 4289 await this.db.execute(` 4290 UPDATE moz_places SET 4291 frecency = CALCULATE_FRECENCY(id) 4292 WHERE frecency = -1`); 4293 } 4294 4295 noteItemAdded(info) { 4296 let uri = info.urlHref ? Services.io.newURI(info.urlHref) : null; 4297 this.bookmarkObserverNotifications.push({ 4298 name: "onItemAdded", 4299 isTagging: info.isTagging, 4300 args: [info.id, info.parentId, info.position, info.type, uri, info.title, 4301 info.dateAdded, info.guid, info.parentGuid, 4302 PlacesUtils.bookmarks.SOURCES.SYNC], 4303 }); 4304 } 4305 4306 noteGuidChanged(info) { 4307 PlacesUtils.invalidateCachedGuidFor(info.id); 4308 this.bookmarkObserverNotifications.push({ 4309 name: "onItemChanged", 4310 isTagging: false, 4311 args: [info.id, "guid", /* isAnnotationProperty */ false, info.newGuid, 4312 info.lastModified, info.type, info.parentId, info.newGuid, 4313 info.parentGuid, info.oldGuid, PlacesUtils.bookmarks.SOURCES.SYNC], 4314 }); 4315 } 4316 4317 noteItemMoved(info) { 4318 this.bookmarkObserverNotifications.push({ 4319 name: "onItemMoved", 4320 isTagging: false, 4321 args: [info.id, info.oldParentId, info.oldPosition, info.newParentId, 4322 info.newPosition, info.type, info.guid, info.oldParentGuid, 4323 info.newParentGuid, PlacesUtils.bookmarks.SOURCES.SYNC], 4324 }); 4325 } 4326 4327 noteItemChanged(info) { 4328 if (info.oldTitle != info.newTitle) { 4329 this.bookmarkObserverNotifications.push({ 4330 name: "onItemChanged", 4331 isTagging: false, 4332 args: [info.id, "title", /* isAnnotationProperty */ false, 4333 info.newTitle, info.lastModified, info.type, info.parentId, 4334 info.guid, info.parentGuid, info.oldTitle, 4335 PlacesUtils.bookmarks.SOURCES.SYNC], 4336 }); 4337 } 4338 if (info.oldURLHref != info.newURLHref) { 4339 this.bookmarkObserverNotifications.push({ 4340 name: "onItemChanged", 4341 isTagging: false, 4342 args: [info.id, "uri", /* isAnnotationProperty */ false, 4343 info.newURLHref, info.lastModified, info.type, info.parentId, 4344 info.guid, info.parentGuid, info.oldURLHref, 4345 PlacesUtils.bookmarks.SOURCES.SYNC], 4346 }); 4347 } 4348 } 4349 4350 noteItemRemoved(info) { 4351 let uri = info.urlHref ? Services.io.newURI(info.urlHref) : null; 4352 this.bookmarkObserverNotifications.push({ 4353 name: "onItemRemoved", 4354 isTagging: info.isUntagging, 4355 args: [info.id, info.parentId, info.position, info.type, uri, info.guid, 4356 info.parentGuid, PlacesUtils.bookmarks.SOURCES.SYNC], 4357 }); 4358 } 4359 4360 noteAnnoSet(id, name) { 4361 if (isLivemarkAnno(name)) { 4362 this.shouldInvalidateLivemarks = true; 4363 } 4364 this.annoObserverNotifications.push({ 4365 name: "onItemAnnotationSet", 4366 args: [id, name, PlacesUtils.bookmarks.SOURCES.SYNC], 4367 }); 4368 } 4369 4370 noteAnnoRemoved(id, name) { 4371 if (isLivemarkAnno(name)) { 4372 this.shouldInvalidateLivemarks = true; 4373 } 4374 this.annoObserverNotifications.push({ 4375 name: "onItemAnnotationRemoved", 4376 args: [id, name, PlacesUtils.bookmarks.SOURCES.SYNC], 4377 }); 4378 } 4379 4380 async notifyBookmarkObservers() { 4381 MirrorLog.debug("Notifying bookmark observers"); 4382 let observers = PlacesUtils.bookmarks.getObservers(); 4383 for (let observer of observers) { 4384 this.notifyObserver(observer, "onBeginUpdateBatch"); 4385 for await (let info of yieldingIterator(this.bookmarkObserverNotifications)) { 4386 if (info.isTagging && observer.skipTags) { 4387 continue; 4388 } 4389 this.notifyObserver(observer, info.name, info.args); 4390 } 4391 this.notifyObserver(observer, "onEndUpdateBatch"); 4392 } 4393 } 4394 4395 async notifyAnnoObservers() { 4396 MirrorLog.debug("Notifying anno observers"); 4397 let observers = PlacesUtils.annotations.getObservers(); 4398 for (let observer of observers) { 4399 let wrapped = yieldingIterator(this.annoObserverNotifications); 4400 for await (let { name, args } of wrapped) { 4401 this.notifyObserver(observer, name, args); 4402 } 4403 } 4404 } 4405 4406 notifyObserver(observer, notification, args = []) { 4407 try { 4408 observer[notification](...args); 4409 } catch (ex) { 4410 MirrorLog.warn("Error notifying observer", ex); 4411 } 4412 } 4413} 4414 4415function isLivemarkAnno(name) { 4416 return name == PlacesUtils.LMANNO_FEEDURI || 4417 name == PlacesUtils.LMANNO_SITEURI; 4418} 4419 4420/** 4421 * Holds Sync metadata and the cleartext for a locally changed record. The 4422 * bookmarks engine inflates a Sync record from the cleartext, and updates the 4423 * `synced` property for successfully uploaded items. 4424 * 4425 * At the end of the sync, the engine writes the uploaded cleartext back to the 4426 * mirror, and passes the updated change record as part of the changeset to 4427 * `PlacesSyncUtils.bookmarks.pushChanges`. 4428 */ 4429class BookmarkChangeRecord { 4430 constructor(syncChangeCounter, cleartext) { 4431 this.tombstone = cleartext.deleted === true; 4432 this.counter = syncChangeCounter; 4433 this.cleartext = cleartext; 4434 this.synced = false; 4435 } 4436} 4437 4438// In conclusion, this is why bookmark syncing is hard. 4439