diff options
Diffstat (limited to 'services/sync/modules/bookmark_validator.js')
| -rw-r--r-- | services/sync/modules/bookmark_validator.js | 784 |
1 files changed, 0 insertions, 784 deletions
diff --git a/services/sync/modules/bookmark_validator.js b/services/sync/modules/bookmark_validator.js deleted file mode 100644 index 2a94ba043..000000000 --- a/services/sync/modules/bookmark_validator.js +++ /dev/null @@ -1,784 +0,0 @@ -/* 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/. */ - -"use strict"; - -const Cu = Components.utils; - -Cu.import("resource://gre/modules/PlacesUtils.jsm"); -Cu.import("resource://gre/modules/PlacesSyncUtils.jsm"); -Cu.import("resource://gre/modules/Task.jsm"); -Cu.import("resource://gre/modules/XPCOMUtils.jsm"); - - -this.EXPORTED_SYMBOLS = ["BookmarkValidator", "BookmarkProblemData"]; - -const LEFT_PANE_ROOT_ANNO = "PlacesOrganizer/OrganizerFolder"; -const LEFT_PANE_QUERY_ANNO = "PlacesOrganizer/OrganizerQuery"; - -// Indicates if a local bookmark tree node should be excluded from syncing. -function isNodeIgnored(treeNode) { - return treeNode.annos && treeNode.annos.some(anno => anno.name == LEFT_PANE_ROOT_ANNO || - anno.name == LEFT_PANE_QUERY_ANNO); -} -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 - */ -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. -XPCOMUtils.defineLazyGetter(this, "SYNCED_ROOTS", () => [ - PlacesUtils.bookmarks.menuGuid, - PlacesUtils.bookmarks.toolbarGuid, - PlacesUtils.bookmarks.unfiledGuid, - PlacesUtils.bookmarks.mobileGuid, -]); - -class BookmarkValidator { - - _followQueries(recordMap) { - for (let [guid, entry] of recordMap) { - if (entry.type !== "query" && (!entry.bmkUri || !entry.bmkUri.startsWith("place:"))) { - continue; - } - // Might be worth trying to parse the place: query instead so that this - // works "automatically" with things like aboutsync. - let queryNodeParent = PlacesUtils.getFolderContents(entry, false, true); - if (!queryNodeParent || !queryNodeParent.root.hasChildren) { - continue; - } - queryNodeParent = queryNodeParent.root; - let queryNode = null; - let numSiblings = 0; - let containerWasOpen = queryNodeParent.containerOpen; - queryNodeParent.containerOpen = true; - try { - try { - numSiblings = queryNodeParent.childCount; - } catch (e) { - // This throws when we can't actually get the children. This is the - // case for history containers, tag queries, ... - continue; - } - for (let i = 0; i < numSiblings && !queryNode; ++i) { - let child = queryNodeParent.getChild(i); - if (child && child.bookmarkGuid && child.bookmarkGuid === guid) { - queryNode = child; - } - } - } finally { - queryNodeParent.containerOpen = containerWasOpen; - } - if (!queryNode) { - continue; - } - - let concreteId = PlacesUtils.getConcreteItemGuid(queryNode); - if (!concreteId) { - continue; - } - let concreteItem = recordMap.get(concreteId); - if (!concreteItem) { - continue; - } - entry.concrete = concreteItem; - } - } - - createClientRecordsFromTree(clientTree) { - // Iterate over the treeNode, converting it to something more similar to what - // the server stores. - let records = []; - let recordsByGuid = new Map(); - let syncedRoots = SYNCED_ROOTS; - function traverse(treeNode, synced) { - if (!synced) { - synced = syncedRoots.includes(treeNode.guid); - } else if (isNodeIgnored(treeNode)) { - synced = false; - } - let guid = PlacesSyncUtils.bookmarks.guidToSyncId(treeNode.guid); - let itemType = 'item'; - treeNode.ignored = !synced; - treeNode.id = guid; - switch (treeNode.type) { - case PlacesUtils.TYPE_X_MOZ_PLACE: - let query = null; - if (treeNode.annos && treeNode.uri.startsWith("place:")) { - query = treeNode.annos.find(({name}) => - name === PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO); - } - if (query && query.value) { - itemType = 'query'; - } else { - itemType = 'bookmark'; - } - break; - case PlacesUtils.TYPE_X_MOZ_PLACE_CONTAINER: - let isLivemark = false; - if (treeNode.annos) { - for (let anno of treeNode.annos) { - if (anno.name === PlacesUtils.LMANNO_FEEDURI) { - isLivemark = true; - treeNode.feedUri = anno.value; - } else if (anno.name === PlacesUtils.LMANNO_SITEURI) { - isLivemark = true; - treeNode.siteUri = anno.value; - } - } - } - itemType = isLivemark ? "livemark" : "folder"; - break; - case 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); - // We want to use the "real" guid here. - recordsByGuid.set(treeNode.guid, treeNode); - if (treeNode.type === 'folder') { - treeNode.childGUIDs = []; - if (!treeNode.children) { - treeNode.children = []; - } - for (let child of treeNode.children) { - traverse(child, synced); - child.parent = treeNode; - child.parentid = guid; - treeNode.childGUIDs.push(child.guid); - } - } - } - traverse(clientTree, false); - clientTree.id = 'places'; - this._followQueries(recordsByGuid); - 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, loadInSidebar - * - 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. - */ - inspectServerRecords(serverRecords) { - let deletedItemIds = new Set(); - let idToRecord = new Map(); - let deletedRecords = []; - - let folders = []; - let problems = []; - - let problemData = new BookmarkProblemData(); - - let resultRecords = []; - - for (let record of serverRecords) { - if (!record.id) { - ++problemData.missingIDs; - continue; - } - if (record.deleted) { - deletedItemIds.add(record.id); - } else { - if (idToRecord.has(record.id)) { - problemData.duplicates.push(record.id); - continue; - } - } - idToRecord.set(record.id, record); - - if (record.children) { - 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) { - continue; - } - // Otherwise we mark it as an error and still try to resolve the children - problemData.childrenOnNonFolder.push(record.id); - } - folders.push(record); - - if (new Set(record.children).size !== record.children.length) { - problemData.duplicateChildren.push(record.id) - } - - // The children array stores special guids as their local guid values, - // e.g. 'menu________' instead of 'menu', but all other parts of the - // serverside bookmark info stores it as the special value ('menu'). - record.childGUIDs = record.children; - record.children = record.children.map(childID => { - return PlacesSyncUtils.bookmarks.guidToSyncId(childID); - }); - } - } - - for (let deletedId of deletedItemIds) { - let record = idToRecord.get(deletedId); - if (record && !record.isDeleted) { - deletedRecords.push(record); - record.isDeleted = true; - } - } - - let root = idToRecord.get('places'); - - if (!root) { - // Fabricate a root. We want to remember that it's fake so that we can - // avoid complaining about stuff like it missing it's childGUIDs later. - root = { id: 'places', children: [], type: 'folder', title: '', fake: true }; - resultRecords.push(root); - idToRecord.set('places', root); - } else { - problemData.rootOnServer = true; - } - - // Build the tree, find orphans, and record most problems having to do with - // the tree structure. - for (let [id, record] of idToRecord) { - if (record === root) { - continue; - } - - if (record.isDeleted) { - continue; - } - - let parentID = record.parentid; - if (!parentID) { - problemData.orphans.push({id: record.id, parent: parentID}); - continue; - } - - let parent = idToRecord.get(parentID); - if (!parent) { - problemData.orphans.push({id: record.id, parent: parentID}); - continue; - } - - if (parent.type !== 'folder') { - problemData.parentNotFolder.push(record.id); - if (!parent.children) { - parent.children = []; - } - if (!parent.childGUIDs) { - parent.childGUIDs = []; - } - } - - if (!record.isDeleted) { - resultRecords.push(record); - } - - record.parent = parent; - if (parent !== root || problemData.rootOnServer) { - let childIndex = parent.children.indexOf(id); - if (childIndex < 0) { - problemData.parentChildMismatches.push({parent: parent.id, child: record.id}); - } else { - parent.children[childIndex] = record; - } - } else { - parent.children.push(record); - } - - if (parent.isDeleted && !record.isDeleted) { - problemData.deletedParents.push(record.id); - } - - // 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. - } - - // Check that we aren't missing any children. - for (let folder of folders) { - folder.unfilteredChildren = folder.children; - folder.children = []; - for (let ci = 0; ci < folder.unfilteredChildren.length; ++ci) { - let child = folder.unfilteredChildren[ci]; - let childObject; - if (typeof child == "string") { - // This can happen the parent refers to a child that has a different - // parentid, or if it refers to a missing or deleted child. It shouldn't - // be possible with totally valid bookmarks. - childObject = idToRecord.get(child); - if (!childObject) { - problemData.missingChildren.push({parent: folder.id, child}); - } else { - folder.unfilteredChildren[ci] = childObject; - if (childObject.isDeleted) { - problemData.deletedChildren.push({ parent: folder.id, child }); - } - } - } else { - childObject = child; - } - - if (!childObject) { - continue; - } - - if (childObject.parentid === folder.id) { - folder.children.push(childObject); - continue; - } - - // The child is very probably in multiple `children` arrays -- - // see if we already have a problem record about it. - let currentProblemRecord = problemData.multipleParents.find(pr => - pr.child === child); - - if (currentProblemRecord) { - currentProblemRecord.parents.push(folder.id); - continue; - } - - let otherParent = idToRecord.get(childObject.parentid); - // it's really an ... orphan ... sort of. - if (!otherParent) { - // if we never end up adding to this parent's list, we filter it out after this loop. - problemData.multipleParents.push({ - child, - parents: [folder.id] - }); - if (!problemData.orphans.some(r => r.id === child)) { - problemData.orphans.push({ - id: child, - parent: childObject.parentid - }); - } - continue; - } - - if (otherParent.isDeleted) { - if (!problemData.deletedParents.includes(child)) { - problemData.deletedParents.push(child); - } - continue; - } - - if (otherParent.childGUIDs && !otherParent.childGUIDs.includes(child)) { - if (!problemData.parentChildMismatches.some(r => r.child === child)) { - // Might not be possible to get here. - problemData.parentChildMismatches.push({ child, parent: folder.id }); - } - } - - problemData.multipleParents.push({ - child, - parents: [childObject.parentid, folder.id] - }); - } - } - problemData.multipleParents = problemData.multipleParents.filter(record => - record.parents.length >= 2); - - problemData.cycles = this._detectCycles(resultRecords); - - return { - deletedRecords, - records: resultRecords, - problemData, - root, - }; - } - - // helper for inspectServerRecords - _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 traverse = 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.concrete) { - children.push(node.concrete); - } - if (children) { - pathLookup.add(node); - currentPath.push(node); - for (let child of children) { - traverse(child); - } - currentPath.pop(); - pathLookup.delete(node); - } - }; - for (let record of records) { - if (!seenEver.has(record)) { - traverse(record); - } - } - - return cycles; - } - - // Perform client-side sanity checking that doesn't involve server data - _validateClient(problemData, clientRecords) { - problemData.clientCycles = this._detectCycles(clientRecords); - for (let rootGUID of SYNCED_ROOTS) { - let record = clientRecords.find(record => - record.guid === rootGUID); - if (!record || record.parentid !== "places") { - problemData.badClientRoots.push(rootGUID); - } - } - } - - /** - * 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. - */ - compareServerWithClient(serverRecords, clientTree) { - - let clientRecords = this.createClientRecordsFromTree(clientTree); - let inspectionInfo = this.inspectServerRecords(serverRecords); - inspectionInfo.clientRecords = clientRecords; - - // Mainly do this to remove deleted items and normalize child guids. - serverRecords = inspectionInfo.records; - let problemData = inspectionInfo.problemData; - - this._validateClient(problemData, clientRecords); - - let matches = []; - - let allRecords = new Map(); - let serverDeletedLookup = new Set(inspectionInfo.deletedRecords.map(r => r.id)); - - for (let sr of serverRecords) { - if (sr.fake) { - continue; - } - allRecords.set(sr.id, {client: null, server: sr}); - } - - for (let cr of clientRecords) { - let unified = allRecords.get(cr.id); - if (!unified) { - allRecords.set(cr.id, {client: cr, server: null}); - } else { - unified.client = cr; - } - } - - - for (let [id, {client, server}] of allRecords) { - if (!client && server) { - problemData.clientMissing.push(id); - continue; - } - if (!server && client) { - if (serverDeletedLookup.has(id)) { - problemData.serverDeleted.push(id); - } else if (!client.ignored && client.id != "places") { - problemData.serverMissing.push(id); - } - continue; - } - if (server && client && client.ignored) { - problemData.serverUnexpected.push(id); - } - let differences = []; - let structuralDifferences = []; - - // 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 (!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 || []; - let sl = server.tags || []; - if (cl.length !== sl.length || !cl.every((tag, i) => sl.indexOf(tag) >= 0)) { - differences.push('tags'); - } - } - - let sameType = client.type === server.type; - if (!sameType) { - if (server.type === "query" && client.type === "bookmark" && client.bmkUri.startsWith("place:")) { - sameType = true; - } - } - - - if (!sameType) { - differences.push('type'); - } else { - switch (server.type) { - case 'bookmark': - case 'query': - if (server.bmkUri !== client.bmkUri) { - differences.push('bmkUri'); - } - 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' && !problemData.rootOnServer) { - // 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 (cl.length !== sl.length || !cl.every((id, i) => sl[i] === id)) { - structuralDifferences.push('childGUIDs'); - } - } - break; - } - } - - if (differences.length) { - problemData.differences.push({id, differences}); - } - if (structuralDifferences.length) { - problemData.structuralDifferences.push({ id, differences: structuralDifferences }); - } - } - return inspectionInfo; - } - - _getServerState(engine) { - let collection = engine.itemSource(); - let collectionKey = engine.service.collectionKeys.keyForCollection(engine.name); - collection.full = true; - let items = []; - collection.recordHandler = function(item) { - item.decrypt(collectionKey); - items.push(item.cleartext); - }; - let resp = collection.getBatched(); - if (!resp.success) { - throw resp; - } - return items; - } - - validate(engine) { - let self = this; - return Task.spawn(function*() { - let start = Date.now(); - let clientTree = yield PlacesUtils.promiseBookmarksTree("", { - includeItemIds: true - }); - let serverState = self._getServerState(engine); - let serverRecordCount = serverState.length; - let result = self.compareServerWithClient(serverState, clientTree); - let end = Date.now(); - let duration = end-start; - return { - duration, - version: self.version, - problems: result.problemData, - recordCount: serverRecordCount - }; - }); - } - -}; - -BookmarkValidator.prototype.version = BOOKMARK_VALIDATOR_VERSION; - |