--- a/services/sync/modules/bookmark_validator.js
+++ b/services/sync/modules/bookmark_validator.js
@@ -218,94 +218,78 @@ class BookmarkProblemData {
 // 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,
 ]);
 
+// 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.
+XPCOMUtils.defineLazyGetter(this, "ROOT_GUID_TO_QUERY_FOLDER_NAME", () => ({
+  [PlacesUtils.bookmarks.rootGuid]: "PLACES_ROOT",
+  [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.
+  [PlacesUtils.bookmarks.tagsGuid]: "TAGS",
+
+  [PlacesUtils.bookmarks.unfiledGuid]: "UNFILED_BOOKMARKS",
+  [PlacesUtils.bookmarks.toolbarGuid]: "TOOLBAR",
+  [PlacesUtils.bookmarks.mobileGuid]: "MOBILE_BOOKMARKS",
+}));
+
 class BookmarkValidator {
 
   async canValidate() {
     return !await PlacesSyncUtils.bookmarks.havePendingChanges();
   }
 
-  async _followQueries(recordMap) {
-    for (let [guid, entry] of recordMap) {
+  _followQueries(recordsByQueryId) {
+    for (let entry of recordsByQueryId.values()) {
       if (entry.type !== "query" && (!entry.bmkUri || !entry.bmkUri.startsWith(QUERY_PROTOCOL))) {
         continue;
       }
-      // Might be worth trying to parse the place: query instead so that this
-      // works "automatically" with things like aboutsync.
-      let id;
-      try {
-        id = await PlacesUtils.promiseItemId(guid);
-      } catch (ex) {
-        // guid isn't found, so this doesn't exist locally.
-        continue;
-      }
-      let queryNodeParent = PlacesUtils.getFolderContents(id, false, true);
-      if (!queryNodeParent || !queryNodeParent.root.hasChildren) {
-        continue;
+      let params = new URLSearchParams(entry.bmkUri.slice(QUERY_PROTOCOL.length));
+      entry.concreteItems = [];
+      let queryIds = params.getAll("folder");
+      for (let queryId of queryIds) {
+        let concreteItem = recordsByQueryId.get(queryId);
+        if (concreteItem) {
+          entry.concreteItems.push(concreteItem);
+        }
       }
-      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;
     }
   }
 
   async createClientRecordsFromTree(clientTree) {
     // Iterate over the treeNode, converting it to something more similar to what
     // the server stores.
     let records = [];
-    let recordsByGuid = new Map();
+    // 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 = SYNCED_ROOTS;
     let yieldCounter = 0;
     async function traverse(treeNode, synced) {
       if (++yieldCounter % 50 === 0) {
         await new Promise(resolve => setTimeout(resolve, 50));
       }
       if (!synced) {
         synced = syncedRoots.includes(treeNode.guid);
       } else if (isNodeIgnored(treeNode)) {
         synced = false;
       }
+      let localId = treeNode.id;
       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(QUERY_PROTOCOL)) {
@@ -342,34 +326,43 @@ class BookmarkValidator {
         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.guid in ROOT_GUID_TO_QUERY_FOLDER_NAME) {
+        let queryId = 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 = [];
         }
         for (let child of treeNode.children) {
           await traverse(child, synced);
           child.parent = treeNode;
           child.parentid = guid;
           treeNode.childGUIDs.push(child.guid);
         }
       }
     }
     await traverse(clientTree, false);
     clientTree.id = "places";
-    await this._followQueries(recordsByGuid);
+    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.
    *
@@ -639,20 +632,20 @@ class BookmarkValidator {
         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 (node.concreteItems) {
+        children.push(...node.concreteItems);
       }
-      if (children) {
+      if (children.length) {
         pathLookup.add(node);
         currentPath.push(node);
         for (let child of children) {
           traverse(child);
         }
         currentPath.pop();
         pathLookup.delete(node);
       }

--- a/services/sync/tests/unit/test_bookmark_validator.js
+++ b/services/sync/tests/unit/test_bookmark_validator.js
@@ -1,14 +1,19 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 Components.utils.import("resource://services-sync/bookmark_validator.js");
 Components.utils.import("resource://services-sync/util.js");
 
+function run_test() {
+  do_get_profile();
+  run_next_test();
+}
+
 async function inspectServerRecords(data) {
   let validator = new BookmarkValidator();
   return validator.inspectServerRecords(data);
 }
 
 async function compareServerWithClient(server, client) {
   let validator = new BookmarkValidator();
   return validator.compareServerWithClient(server, client);
@@ -323,16 +328,78 @@ add_task(async function test_cswc_server
 
   let c = (await compareServerWithClient(server, client)).problemData;
   equal(c.clientMissing.length, 0);
   equal(c.serverMissing.length, 0);
   equal(c.serverUnexpected.length, 2);
   deepEqual(c.serverUnexpected, ["dddddddddddd", "eeeeeeeeeeee"]);
 });
 
+add_task(async function test_cswc_clientCycles() {
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.menuGuid,
+    children: [{
+      // A query for the menu, referenced by its local ID instead of
+      // `BOOKMARKS_MENU`. This should be reported as a cycle.
+      guid: "dddddddddddd",
+      url: `place:folder=${PlacesUtils.bookmarksMenuFolderId}`,
+      title: "Bookmarks Menu",
+    }],
+  });
+
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.toolbarGuid,
+    children: [{
+      guid: "eeeeeeeeeeee",
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      children: [{
+        // A query for the toolbar in a subfolder. This should still be reported
+        // as a cycle.
+        guid: "ffffffffffff",
+        url: "place:folder=TOOLBAR&sort=3",
+        title: "Bookmarks Toolbar",
+      }],
+    }],
+  });
+
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.unfiledGuid,
+    children: [{
+      // A query for the menu. This shouldn't be reported as a cycle, since it
+      // references a different root.
+      guid: "gggggggggggg",
+      url: "place:folder=BOOKMARKS_MENU&sort=5",
+      title: "Bookmarks Menu",
+    }],
+  });
+
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.mobileGuid,
+    children: [{
+      // A query referencing multiple roots, one of which forms a cycle by
+      // referencing mobile. This is extremely unlikely, but it's cheap to
+      // detect, so we still report it.
+      guid: "hhhhhhhhhhhh",
+      url: "place:folder=TOOLBAR&folder=MOBILE_BOOKMARKS&folder=UNFILED_BOOKMARKS&sort=1",
+      title: "Toolbar, Mobile, Unfiled",
+    }],
+  });
+
+  let clientTree = await PlacesUtils.promiseBookmarksTree("", {
+    includeItemIds: true
+  });
+
+  let c = (await compareServerWithClient([], clientTree)).problemData;
+  deepEqual(c.clientCycles, [
+    ["menu", "dddddddddddd"],
+    ["toolbar", "eeeeeeeeeeee", "ffffffffffff"],
+    ["mobile", "hhhhhhhhhhhh"],
+  ]);
+});
+
 async function validationPing(server, client, duration) {
   let pingPromise = wait_for_ping(() => {}, true); // Allow "failing" pings, since having validation info indicates failure.
   // fake this entirely
   Svc.Obs.notify("weave:service:sync:start");
   Svc.Obs.notify("weave:engine:sync:start", null, "bookmarks");
   Svc.Obs.notify("weave:engine:sync:finish", null, "bookmarks");
   let validator = new BookmarkValidator();
   let {problemData} = await validator.compareServerWithClient(server, client);