diff options
Diffstat (limited to 'services/sync/modules/bookmark_validator.js')
| -rw-r--r-- | services/sync/modules/bookmark_validator.js | 784 |
1 files changed, 784 insertions, 0 deletions
diff --git a/services/sync/modules/bookmark_validator.js b/services/sync/modules/bookmark_validator.js new file mode 100644 index 000000000..2a94ba043 --- /dev/null +++ b/services/sync/modules/bookmark_validator.js @@ -0,0 +1,784 @@ +/* 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; + |