/* 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;