diff options
Diffstat (limited to 'services/sync/tps/extensions/tps/resource/modules/bookmarkValidator.sys.mjs')
| -rw-r--r-- | services/sync/tps/extensions/tps/resource/modules/bookmarkValidator.sys.mjs | 1063 |
1 files changed, 1063 insertions, 0 deletions
diff --git a/services/sync/tps/extensions/tps/resource/modules/bookmarkValidator.sys.mjs b/services/sync/tps/extensions/tps/resource/modules/bookmarkValidator.sys.mjs new file mode 100644 index 0000000000..a7724c6aaa --- /dev/null +++ b/services/sync/tps/extensions/tps/resource/modules/bookmarkValidator.sys.mjs @@ -0,0 +1,1063 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// This file was moved to tps from the main production code as it was unused +// after removal of the non-mirror bookmarks engine. +// It used to have a test before it was moved: +// https://searchfox.org/mozilla-central/rev/b1a5802e0f73bfd6d2096e5fefc2b47831a50b2d/services/sync/tests/unit/test_bookmark_validator.js + +import { CommonUtils } from "resource://services-common/utils.sys.mjs"; +import { Utils } from "resource://services-sync/util.sys.mjs"; + +const lazy = {}; + +ChromeUtils.defineESModuleGetters(lazy, { + Async: "resource://services-common/async.sys.mjs", + PlacesSyncUtils: "resource://gre/modules/PlacesSyncUtils.sys.mjs", + PlacesUtils: "resource://gre/modules/PlacesUtils.sys.mjs", +}); + +const QUERY_PROTOCOL = "place:"; + +function areURLsEqual(a, b) { + if (a === b) { + return true; + } + if (a.startsWith(QUERY_PROTOCOL) != b.startsWith(QUERY_PROTOCOL)) { + return false; + } + // Tag queries are special because we rewrite them to point to the + // local tag folder ID. It's expected that the folders won't match, + // but all other params should. + let aParams = new URLSearchParams(a.slice(QUERY_PROTOCOL.length)); + let aType = +aParams.get("type"); + if (aType != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) { + return false; + } + let bParams = new URLSearchParams(b.slice(QUERY_PROTOCOL.length)); + let bType = +bParams.get("type"); + if (bType != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) { + return false; + } + let aKeys = new Set(aParams.keys()); + let bKeys = new Set(bParams.keys()); + if (aKeys.size != bKeys.size) { + return false; + } + // Tag queries shouldn't reference multiple folders, or named folders like + // "TOOLBAR" or "BOOKMARKS_MENU". Just in case, we make sure all folder IDs + // are numeric. If they are, we ignore them when comparing the query params. + if (aKeys.has("folder") && aParams.getAll("folder").every(isFinite)) { + aKeys.delete("folder"); + } + if (bKeys.has("folder") && bParams.getAll("folder").every(isFinite)) { + bKeys.delete("folder"); + } + for (let key of aKeys) { + if (!bKeys.has(key)) { + return false; + } + if ( + !CommonUtils.arrayEqual( + aParams.getAll(key).sort(), + bParams.getAll(key).sort() + ) + ) { + return false; + } + } + for (let key of bKeys) { + if (!aKeys.has(key)) { + return false; + } + } + return true; +} + +const BOOKMARK_VALIDATOR_VERSION = 1; + +/** + * Result of bookmark validation. Contains the following fields which describe + * server-side problems unless otherwise specified. + * + * - missingIDs (number): # of objects with missing ids + * - duplicates (array of ids): ids seen more than once + * - parentChildMismatches (array of {parent: parentid, child: childid}): + * instances where the child's parentid and the parent's children array + * do not match + * - cycles (array of array of ids). List of cycles found in the server-side tree. + * - clientCycles (array of array of ids). List of cycles found in the client-side tree. + * - orphans (array of {id: string, parent: string}): List of nodes with + * either no parentid, or where the parent could not be found. + * - missingChildren (array of {parent: id, child: id}): + * List of parent/children where the child id couldn't be found + * - deletedChildren (array of { parent: id, child: id }): + * List of parent/children where child id was a deleted item (but still showed up + * in the children array) + * - multipleParents (array of {child: id, parents: array of ids}): + * List of children that were part of multiple parent arrays + * - deletedParents (array of ids) : List of records that aren't deleted but + * had deleted parents + * - childrenOnNonFolder (array of ids): list of non-folders that still have + * children arrays + * - duplicateChildren (array of ids): list of records who have the same + * child listed multiple times in their children array + * - parentNotFolder (array of ids): list of records that have parents that + * aren't folders + * - rootOnServer (boolean): true if the root came from the server + * - badClientRoots (array of ids): Contains any client-side root ids where + * the root is missing or isn't a (direct) child of the places root. + * + * - clientMissing: Array of ids on the server missing from the client + * - serverMissing: Array of ids on the client missing from the server + * - serverDeleted: Array of ids on the client that the server had marked as deleted. + * - serverUnexpected: Array of ids that appear on the server but shouldn't + * because the client attempts to never upload them. + * - differences: Array of {id: string, differences: string array} recording + * the non-structural properties that are differente between the client and server + * - structuralDifferences: As above, but contains the items where the differences were + * structural, that is, they contained childGUIDs or parentid + */ +export class BookmarkProblemData { + constructor() { + this.rootOnServer = false; + this.missingIDs = 0; + + this.duplicates = []; + this.parentChildMismatches = []; + this.cycles = []; + this.clientCycles = []; + this.orphans = []; + this.missingChildren = []; + this.deletedChildren = []; + this.multipleParents = []; + this.deletedParents = []; + this.childrenOnNonFolder = []; + this.duplicateChildren = []; + this.parentNotFolder = []; + + this.badClientRoots = []; + this.clientMissing = []; + this.serverMissing = []; + this.serverDeleted = []; + this.serverUnexpected = []; + this.differences = []; + this.structuralDifferences = []; + } + + /** + * Convert ("difference", [{ differences: ["tags", "name"] }, { differences: ["name"] }]) into + * [{ name: "difference:tags", count: 1}, { name: "difference:name", count: 2 }], etc. + */ + _summarizeDifferences(prefix, diffs) { + let diffCounts = new Map(); + for (let { differences } of diffs) { + for (let type of differences) { + let name = prefix + ":" + type; + let count = diffCounts.get(name) || 0; + diffCounts.set(name, count + 1); + } + } + return [...diffCounts].map(([name, count]) => ({ name, count })); + } + + /** + * Produce a list summarizing problems found. Each entry contains {name, count}, + * where name is the field name for the problem, and count is the number of times + * the problem was encountered. + * + * Validation has failed if all counts are not 0. + * + * If the `full` argument is truthy, we also include information about which + * properties we saw structural differences in. Currently, this means either + * "sdiff:parentid" and "sdiff:childGUIDS" may be present. + */ + getSummary(full) { + let result = [ + { name: "clientMissing", count: this.clientMissing.length }, + { name: "serverMissing", count: this.serverMissing.length }, + { name: "serverDeleted", count: this.serverDeleted.length }, + { name: "serverUnexpected", count: this.serverUnexpected.length }, + + { + name: "structuralDifferences", + count: this.structuralDifferences.length, + }, + { name: "differences", count: this.differences.length }, + + { name: "missingIDs", count: this.missingIDs }, + { name: "rootOnServer", count: this.rootOnServer ? 1 : 0 }, + + { name: "duplicates", count: this.duplicates.length }, + { + name: "parentChildMismatches", + count: this.parentChildMismatches.length, + }, + { name: "cycles", count: this.cycles.length }, + { name: "clientCycles", count: this.clientCycles.length }, + { name: "badClientRoots", count: this.badClientRoots.length }, + { name: "orphans", count: this.orphans.length }, + { name: "missingChildren", count: this.missingChildren.length }, + { name: "deletedChildren", count: this.deletedChildren.length }, + { name: "multipleParents", count: this.multipleParents.length }, + { name: "deletedParents", count: this.deletedParents.length }, + { name: "childrenOnNonFolder", count: this.childrenOnNonFolder.length }, + { name: "duplicateChildren", count: this.duplicateChildren.length }, + { name: "parentNotFolder", count: this.parentNotFolder.length }, + ]; + if (full) { + let structural = this._summarizeDifferences( + "sdiff", + this.structuralDifferences + ); + result.push.apply(result, structural); + } + return result; + } +} + +// Defined lazily to avoid initializing PlacesUtils.bookmarks too soon. +ChromeUtils.defineLazyGetter(lazy, "SYNCED_ROOTS", () => [ + lazy.PlacesUtils.bookmarks.menuGuid, + lazy.PlacesUtils.bookmarks.toolbarGuid, + lazy.PlacesUtils.bookmarks.unfiledGuid, + lazy.PlacesUtils.bookmarks.mobileGuid, +]); + +// Maps root GUIDs to their query folder names from +// toolkit/components/places/nsNavHistoryQuery.cpp. We follow queries that +// reference existing folders in the client tree, and detect cycles where a +// query references its containing folder. +ChromeUtils.defineLazyGetter(lazy, "ROOT_GUID_TO_QUERY_FOLDER_NAME", () => ({ + [lazy.PlacesUtils.bookmarks.rootGuid]: "PLACES_ROOT", + [lazy.PlacesUtils.bookmarks.menuGuid]: "BOOKMARKS_MENU", + + // Tags should never show up in our client tree, and never form cycles, but we + // report them just in case. + [lazy.PlacesUtils.bookmarks.tagsGuid]: "TAGS", + + [lazy.PlacesUtils.bookmarks.unfiledGuid]: "UNFILED_BOOKMARKS", + [lazy.PlacesUtils.bookmarks.toolbarGuid]: "TOOLBAR", + [lazy.PlacesUtils.bookmarks.mobileGuid]: "MOBILE_BOOKMARKS", +})); + +async function detectCycles(records) { + // currentPath and pathLookup contain the same data. pathLookup is faster to + // query, but currentPath gives is the order of traversal that we need in + // order to report the members of the cycles. + let pathLookup = new Set(); + let currentPath = []; + let cycles = []; + let seenEver = new Set(); + const yieldState = lazy.Async.yieldState(); + + const traverse = async node => { + if (pathLookup.has(node)) { + let cycleStart = currentPath.lastIndexOf(node); + let cyclePath = currentPath.slice(cycleStart).map(n => n.id); + cycles.push(cyclePath); + return; + } else if (seenEver.has(node)) { + // If we're checking the server, this is a problem, but it should already be reported. + // On the client, this could happen due to including `node.concrete` in the child list. + return; + } + seenEver.add(node); + let children = node.children || []; + if (node.concreteItems) { + children.push(...node.concreteItems); + } + if (children.length) { + pathLookup.add(node); + currentPath.push(node); + await lazy.Async.yieldingForEach(children, traverse, yieldState); + currentPath.pop(); + pathLookup.delete(node); + } + }; + + await lazy.Async.yieldingForEach( + records, + async record => { + if (!seenEver.has(record)) { + await traverse(record); + } + }, + yieldState + ); + + return cycles; +} + +class ServerRecordInspection { + constructor() { + this.serverRecords = null; + this.liveRecords = []; + + this.folders = []; + + this.root = null; + + this.idToRecord = new Map(); + + this.deletedIds = new Set(); + this.deletedRecords = []; + + this.problemData = new BookmarkProblemData(); + + // These are handled outside of problemData + this._orphans = new Map(); + this._multipleParents = new Map(); + + this.yieldState = lazy.Async.yieldState(); + } + + static async create(records) { + return new ServerRecordInspection().performInspection(records); + } + + async performInspection(records) { + await this._setRecords(records); + await this._linkParentIDs(); + await this._linkChildren(); + await this._findOrphans(); + await this._finish(); + return this; + } + + // We don't set orphans in this.problemData. Instead, we walk the tree at the + // end to find unreachable items. + _noteOrphan(id, parentId = undefined) { + // This probably shouldn't be called with a parentId twice, but if it + // happens we take the most recent one. + if (parentId || !this._orphans.has(id)) { + this._orphans.set(id, parentId); + } + } + + noteParent(child, parent) { + let parents = this._multipleParents.get(child); + if (!parents) { + this._multipleParents.set(child, [parent]); + } else { + parents.push(parent); + } + } + + noteMismatch(child, parent) { + let exists = this.problemData.parentChildMismatches.some( + match => match.child == child && match.parent == parent + ); + if (!exists) { + this.problemData.parentChildMismatches.push({ child, parent }); + } + } + + // - Populates `this.deletedIds`, `this.folders`, and `this.idToRecord` + // - calls `_initRoot` (thus initializing `this.root`). + async _setRecords(records) { + if (this.serverRecords) { + // In general this class is expected to be created, have + // `performInspection` called, and then only read from from that point on. + throw new Error("Bug: ServerRecordInspection can't `setRecords` twice"); + } + this.serverRecords = records; + let rootChildren = []; + + await lazy.Async.yieldingForEach( + this.serverRecords, + async record => { + if (!record.id) { + ++this.problemData.missingIDs; + return; + } + + if (record.deleted) { + this.deletedIds.add(record.id); + } + if (this.idToRecord.has(record.id)) { + this.problemData.duplicates.push(record.id); + return; + } + + this.idToRecord.set(record.id, record); + + if (!record.deleted) { + this.liveRecords.push(record); + + if (record.parentid == "places") { + rootChildren.push(record); + } + } + + if (!record.children) { + return; + } + + if (record.type != "folder") { + // Due to implementation details in engines/bookmarks.js, (Livemark + // subclassing BookmarkFolder) Livemarks will have a children array, + // but it should still be empty. + if (!record.children.length) { + return; + } + // Otherwise we mark it as an error and still try to resolve the children + this.problemData.childrenOnNonFolder.push(record.id); + } + + this.folders.push(record); + + if (new Set(record.children).size !== record.children.length) { + this.problemData.duplicateChildren.push(record.id); + } + + // After we're through with them, folder records store 3 (ugh) arrays that + // represent their folder information. The final fields looks like: + // + // - childGUIDs: The original `children` array, which is an array of + // record IDs. + // + // - unfilteredChildren: Contains more or less `childGUIDs.map(id => + // idToRecord.get(id))`, without the nulls for missing children. It will + // still have deleted, duplicate, mismatching, etc. children. + // + // - children: This is the 'cleaned' version of the child records that are + // safe to iterate over, etc.. If there are no reported problems, it should + // be identical to unfilteredChildren. + // + // The last two are left alone until later `this._linkChildren`, however. + record.childGUIDs = record.children; + + await lazy.Async.yieldingForEach( + record.childGUIDs, + id => { + this.noteParent(id, record.id); + }, + this.yieldState + ); + + record.children = []; + }, + this.yieldState + ); + + // Finish up some parts we can easily do now that we have idToRecord. + this.deletedRecords = Array.from(this.deletedIds, id => + this.idToRecord.get(id) + ); + + this._initRoot(rootChildren); + } + + _initRoot(rootChildren) { + let serverRoot = this.idToRecord.get("places"); + if (serverRoot) { + this.root = serverRoot; + this.problemData.rootOnServer = true; + return; + } + + // Fabricate a root. We want to be able to remember that it's fake, but + // would like to avoid it needing too much special casing, so we come up + // with children for it too (we just get these while we're iterating over + // the records to avoid needing two passes over a potentially large number + // of records). + + this.root = { + id: "places", + fake: true, + children: rootChildren, + childGUIDs: rootChildren.map(record => record.id), + type: "folder", + title: "", + }; + this.liveRecords.push(this.root); + this.idToRecord.set("places", this.root); + } + + // Adds `parent` to all records it can that have `parentid` + async _linkParentIDs() { + await lazy.Async.yieldingForEach( + this.idToRecord, + ([id, record]) => { + if (record == this.root || record.deleted) { + return false; + } + + // Check and update our orphan map. + let parentID = record.parentid; + let parent = this.idToRecord.get(parentID); + if (!parentID || !parent) { + this._noteOrphan(id, parentID); + return false; + } + + record.parent = parent; + + if (parent.deleted) { + this.problemData.deletedParents.push(id); + return true; + } else if (parent.type != "folder") { + this.problemData.parentNotFolder.push(record.id); + return true; + } + + if (parent.id !== "place" || this.problemData.rootOnServer) { + if (!parent.childGUIDs.includes(record.id)) { + this.noteMismatch(record.id, parent.id); + } + } + + if (parent.deleted && !record.deleted) { + this.problemData.deletedParents.push(record.id); + } + + // Note: We used to check if the parentName on the server matches the + // actual local parent name, but given this is used only for de-duping a + // record the first time it is seen and expensive to keep up-to-date, we + // decided to just stop recording it. See bug 1276969 for more. + return false; + }, + this.yieldState + ); + } + + // Build the children and unfilteredChildren arrays, (which are of record + // objects, not ids) + async _linkChildren() { + // Check that we aren't missing any children. + await lazy.Async.yieldingForEach( + this.folders, + async folder => { + folder.children = []; + folder.unfilteredChildren = []; + + let idsThisFolder = new Set(); + + await lazy.Async.yieldingForEach( + folder.childGUIDs, + childID => { + let child = this.idToRecord.get(childID); + + if (!child) { + this.problemData.missingChildren.push({ + parent: folder.id, + child: childID, + }); + return; + } + + if (child.deleted) { + this.problemData.deletedChildren.push({ + parent: folder.id, + child: childID, + }); + return; + } + + if (child.parentid != folder.id) { + this.noteMismatch(childID, folder.id); + return; + } + + if (idsThisFolder.has(childID)) { + // Already recorded earlier, we just don't want to mess up `children` + return; + } + folder.children.push(child); + }, + this.yieldState + ); + }, + this.yieldState + ); + } + + // Finds the orphans in the tree using something similar to a `mark and sweep` + // strategy. That is, we iterate over the children from the root, remembering + // which items we've seen. Then, we iterate all items, and know the ones we + // haven't seen are orphans. + async _findOrphans() { + let seen = new Set([this.root.id]); + + const inCycle = await lazy.Async.yieldingForEach( + Utils.walkTree(this.root), + ([node]) => { + if (seen.has(node.id)) { + // We're in an infloop due to a cycle. + // Return early to avoid reporting false positives for orphans. + return true; + } + seen.add(node.id); + + return false; + }, + this.yieldState + ); + + if (inCycle) { + return; + } + + await lazy.Async.yieldingForEach( + this.liveRecords, + (record, i) => { + if (!seen.has(record.id)) { + // We intentionally don't record the parentid here, since we only record + // that if the record refers to a parent that doesn't exist, which we + // have already handled (when linking parentid's). + this._noteOrphan(record.id); + } + }, + this.yieldState + ); + + await lazy.Async.yieldingForEach( + this._orphans, + ([id, parent]) => { + this.problemData.orphans.push({ id, parent }); + }, + this.yieldState + ); + } + + async _finish() { + this.problemData.cycles = await detectCycles(this.liveRecords); + + for (const [child, recordedParents] of this._multipleParents) { + let parents = new Set(recordedParents); + if (parents.size > 1) { + this.problemData.multipleParents.push({ child, parents: [...parents] }); + } + } + // Dedupe simple arrays in the problem data, so that we don't have to worry + // about it in the code + const idArrayProps = [ + "duplicates", + "deletedParents", + "childrenOnNonFolder", + "duplicateChildren", + "parentNotFolder", + ]; + for (let prop of idArrayProps) { + this.problemData[prop] = [...new Set(this.problemData[prop])]; + } + } +} + +export class BookmarkValidator { + constructor() { + this.yieldState = lazy.Async.yieldState(); + } + + async canValidate() { + return !(await lazy.PlacesSyncUtils.bookmarks.havePendingChanges()); + } + + async _followQueries(recordsByQueryId) { + await lazy.Async.yieldingForEach( + recordsByQueryId.values(), + entry => { + if ( + entry.type !== "query" && + (!entry.bmkUri || !entry.bmkUri.startsWith(QUERY_PROTOCOL)) + ) { + return; + } + let params = new URLSearchParams( + entry.bmkUri.slice(QUERY_PROTOCOL.length) + ); + // Queries with `excludeQueries` won't form cycles because they'll + // exclude all queries, including themselves, from the result set. + let excludeQueries = params.get("excludeQueries"); + if (excludeQueries === "1" || excludeQueries === "true") { + // `nsNavHistoryQuery::ParseQueryBooleanString` allows `1` and `true`. + return; + } + entry.concreteItems = []; + let queryIds = params.getAll("folder"); + for (let queryId of queryIds) { + let concreteItem = recordsByQueryId.get(queryId); + if (concreteItem) { + entry.concreteItems.push(concreteItem); + } + } + }, + this.yieldState + ); + } + + async createClientRecordsFromTree(clientTree) { + // Iterate over the treeNode, converting it to something more similar to what + // the server stores. + let records = []; + // A map of local IDs and well-known query folder names to records. Unlike + // GUIDs, local IDs aren't synced, since they're not stable across devices. + // New Places APIs use GUIDs to refer to bookmarks, but the legacy APIs + // still use local IDs. We use this mapping to parse `place:` queries that + // refer to folders via their local IDs. + let recordsByQueryId = new Map(); + let syncedRoots = lazy.SYNCED_ROOTS; + + const traverse = async (treeNode, synced) => { + if (!synced) { + synced = syncedRoots.includes(treeNode.guid); + } + let localId = treeNode.id; + let guid = lazy.PlacesSyncUtils.bookmarks.guidToRecordId(treeNode.guid); + let itemType = "item"; + treeNode.ignored = !synced; + treeNode.id = guid; + switch (treeNode.type) { + case lazy.PlacesUtils.TYPE_X_MOZ_PLACE: + if (treeNode.uri.startsWith(QUERY_PROTOCOL)) { + itemType = "query"; + } else { + itemType = "bookmark"; + } + break; + case lazy.PlacesUtils.TYPE_X_MOZ_PLACE_CONTAINER: + let isLivemark = false; + if (treeNode.annos) { + for (let anno of treeNode.annos) { + if (anno.name === lazy.PlacesUtils.LMANNO_FEEDURI) { + isLivemark = true; + treeNode.feedUri = anno.value; + } else if (anno.name === lazy.PlacesUtils.LMANNO_SITEURI) { + isLivemark = true; + treeNode.siteUri = anno.value; + } + } + } + itemType = isLivemark ? "livemark" : "folder"; + break; + case lazy.PlacesUtils.TYPE_X_MOZ_PLACE_SEPARATOR: + itemType = "separator"; + break; + } + + if (treeNode.tags) { + treeNode.tags = treeNode.tags.split(","); + } else { + treeNode.tags = []; + } + treeNode.type = itemType; + treeNode.pos = treeNode.index; + treeNode.bmkUri = treeNode.uri; + records.push(treeNode); + if (treeNode.guid in lazy.ROOT_GUID_TO_QUERY_FOLDER_NAME) { + let queryId = lazy.ROOT_GUID_TO_QUERY_FOLDER_NAME[treeNode.guid]; + recordsByQueryId.set(queryId, treeNode); + } + if (localId) { + // Always add the ID, since it's still possible for a query to + // reference a root without using the well-known name. For example, + // `place:folder=${PlacesUtils.mobileFolderId}` and + // `place:folder=MOBILE_BOOKMARKS` are equivalent. + recordsByQueryId.set(localId.toString(10), treeNode); + } + if (treeNode.type === "folder") { + treeNode.childGUIDs = []; + if (!treeNode.children) { + treeNode.children = []; + } + + await lazy.Async.yieldingForEach( + treeNode.children, + async child => { + await traverse(child, synced); + child.parent = treeNode; + child.parentid = guid; + treeNode.childGUIDs.push(child.guid); + }, + this.yieldState + ); + } + }; + + await traverse(clientTree, false); + + clientTree.id = "places"; + await this._followQueries(recordsByQueryId); + return records; + } + + /** + * Process the server-side list. Mainly this builds the records into a tree, + * but it also records information about problems, and produces arrays of the + * deleted and non-deleted nodes. + * + * Returns an object containing: + * - records:Array of non-deleted records. Each record contains the following + * properties + * - childGUIDs (array of strings, only present if type is 'folder'): the + * list of child GUIDs stored on the server. + * - children (array of records, only present if type is 'folder'): + * each record has these same properties. This may differ in content + * from what you may expect from the childGUIDs list, as it won't + * contain any records that could not be found. + * - parent (record): The parent to this record. + * - Unchanged properties send down from the server: id, title, type, + * parentName, parentid, bmkURI, keyword, tags, pos, queryId + * - root: Root of the server-side bookmark tree. Has the same properties as + * above. + * - deletedRecords: As above, but only contains items that the server sent + * where it also sent indication that the item should be deleted. + * - problemData: a BookmarkProblemData object, with the caveat that + * the fields describing client/server relationship will not have been filled + * out yet. + */ + async inspectServerRecords(serverRecords) { + const data = await ServerRecordInspection.create(serverRecords); + return { + deletedRecords: data.deletedRecords, + records: data.liveRecords, + problemData: data.problemData, + root: data.root, + }; + } + + // Perform client-side sanity checking that doesn't involve server data + async _validateClient(problemData, clientRecords) { + problemData.clientCycles = await detectCycles(clientRecords); + for (let rootGUID of lazy.SYNCED_ROOTS) { + let record = clientRecords.find(record => record.guid === rootGUID); + if (!record || record.parentid !== "places") { + problemData.badClientRoots.push(rootGUID); + } + } + } + + async _computeUnifiedRecordMap(serverRecords, clientRecords) { + let allRecords = new Map(); + await lazy.Async.yieldingForEach( + serverRecords, + sr => { + if (sr.fake) { + return; + } + allRecords.set(sr.id, { client: null, server: sr }); + }, + this.yieldState + ); + + await lazy.Async.yieldingForEach( + clientRecords, + cr => { + let unified = allRecords.get(cr.id); + if (!unified) { + allRecords.set(cr.id, { client: cr, server: null }); + } else { + unified.client = cr; + } + }, + this.yieldState + ); + + return allRecords; + } + + _recordMissing(problems, id, clientRecord, serverRecord, serverTombstones) { + if (!clientRecord && serverRecord) { + problems.clientMissing.push(id); + } + if (!serverRecord && clientRecord) { + if (serverTombstones.has(id)) { + problems.serverDeleted.push(id); + } else if (!clientRecord.ignored && clientRecord.id != "places") { + problems.serverMissing.push(id); + } + } + } + + _compareRecords(client, server) { + let structuralDifferences = []; + let differences = []; + + // Don't bother comparing titles of roots. It's okay if locally it's + // "Mobile Bookmarks", but the server thinks it's "mobile". + // TODO: We probably should be handing other localized bookmarks (e.g. + // default bookmarks) here as well, see bug 1316041. + if (!lazy.SYNCED_ROOTS.includes(client.guid)) { + // We want to treat undefined, null and an empty string as identical + if ((client.title || "") !== (server.title || "")) { + differences.push("title"); + } + } + + if (client.parentid || server.parentid) { + if (client.parentid !== server.parentid) { + structuralDifferences.push("parentid"); + } + } + + if (client.tags || server.tags) { + let cl = client.tags ? [...client.tags].sort() : []; + let sl = server.tags ? [...server.tags].sort() : []; + if (!CommonUtils.arrayEqual(cl, sl)) { + differences.push("tags"); + } + } + + let sameType = client.type === server.type; + if (!sameType) { + if ( + server.type === "query" && + client.type === "bookmark" && + client.bmkUri.startsWith(QUERY_PROTOCOL) + ) { + sameType = true; + } + } + + if (!sameType) { + differences.push("type"); + } else { + switch (server.type) { + case "bookmark": + case "query": + if (!areURLsEqual(server.bmkUri, client.bmkUri)) { + differences.push("bmkUri"); + } + break; + case "separator": + if (server.pos != client.pos) { + differences.push("pos"); + } + break; + case "livemark": + if (server.feedUri != client.feedUri) { + differences.push("feedUri"); + } + if (server.siteUri != client.siteUri) { + differences.push("siteUri"); + } + break; + case "folder": + if (server.id === "places" && server.fake) { + // It's the fabricated places root. It won't have the GUIDs, but + // it doesn't matter. + break; + } + if (client.childGUIDs || server.childGUIDs) { + let cl = client.childGUIDs || []; + let sl = server.childGUIDs || []; + if (!CommonUtils.arrayEqual(cl, sl)) { + structuralDifferences.push("childGUIDs"); + } + } + break; + } + } + return { differences, structuralDifferences }; + } + + /** + * Compare the list of server records with the client tree. + * + * Returns the same data as described in the inspectServerRecords comment, + * with the following additional fields. + * - clientRecords: an array of client records in a similar format to + * the .records (ie, server records) entry. + * - problemData is the same as for inspectServerRecords, except all properties + * will be filled out. + */ + async compareServerWithClient(serverRecords, clientTree) { + let clientRecords = await this.createClientRecordsFromTree(clientTree); + let inspectionInfo = await this.inspectServerRecords(serverRecords); + inspectionInfo.clientRecords = clientRecords; + + // Mainly do this to remove deleted items and normalize child guids. + serverRecords = inspectionInfo.records; + let problemData = inspectionInfo.problemData; + + await this._validateClient(problemData, clientRecords); + + let allRecords = await this._computeUnifiedRecordMap( + serverRecords, + clientRecords + ); + + let serverDeleted = new Set(inspectionInfo.deletedRecords.map(r => r.id)); + + await lazy.Async.yieldingForEach( + allRecords, + ([id, { client, server }]) => { + if (!client || !server) { + this._recordMissing(problemData, id, client, server, serverDeleted); + return; + } + if (server && client && client.ignored) { + problemData.serverUnexpected.push(id); + } + let { differences, structuralDifferences } = this._compareRecords( + client, + server + ); + + if (differences.length) { + problemData.differences.push({ id, differences }); + } + if (structuralDifferences.length) { + problemData.structuralDifferences.push({ + id, + differences: structuralDifferences, + }); + } + }, + this.yieldState + ); + + return inspectionInfo; + } + + async _getServerState(engine) { + let collection = engine.itemSource(); + let collectionKey = engine.service.collectionKeys.keyForCollection( + engine.name + ); + collection.full = true; + let result = await collection.getBatched(); + if (!result.response.success) { + throw result.response; + } + let cleartexts = []; + await lazy.Async.yieldingForEach( + result.records, + async record => { + await record.decrypt(collectionKey); + cleartexts.push(record.cleartext); + }, + this.yieldState + ); + return cleartexts; + } + + async validate(engine) { + let start = Date.now(); + let clientTree = await lazy.PlacesUtils.promiseBookmarksTree("", { + includeItemIds: true, + }); + let serverState = await this._getServerState(engine); + let serverRecordCount = serverState.length; + let result = await this.compareServerWithClient(serverState, clientTree); + let end = Date.now(); + let duration = end - start; + + engine._log.debug(`Validated bookmarks in ${duration}ms`); + engine._log.debug(`Problem summary`); + for (let { name, count } of result.problemData.getSummary()) { + engine._log.debug(` ${name}: ${count}`); + } + + return { + duration, + version: this.version, + problems: result.problemData, + recordCount: serverRecordCount, + }; + } +} + +BookmarkValidator.prototype.version = BOOKMARK_VALIDATOR_VERSION; |