new file mode 100644
--- /dev/null
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/validation/BookmarkValidationResults.java
@@ -0,0 +1,175 @@
+/* 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/. */
+
+package org.mozilla.gecko.sync.validation;
+
+import org.json.simple.JSONArray;
+import org.json.simple.JSONObject;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Stores data that describes the set of problems found during bookmark validation.
+ * It stores enough info so that meaningful action to repair or visualize the problems could
+ * be taken in the future, although at the moment the primary use is to generate data for
+ * telemetry.
+ *
+ * Currently it only holds a subset of what is stored by desktop's implementation.
+ */
+public class BookmarkValidationResults extends ValidationResults {
+    /**
+     * Simple class used to store a pair of guids that refer to a parent/child relationship.
+     */
+    public static class ParentChildPair {
+        public String parent;
+        public String child;
+
+        public ParentChildPair(String parentID, String childID) {
+            this.parent = parentID;
+            this.child = childID;
+        }
+
+        // There are a few cases where it's difficult for the validator to guarantee uniqueness of
+        // it's complaints, and so it helps to be able to store these in a Map/Set by value.
+        // The implementations were automatically generated.
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) {
+                return true;
+            }
+            if (o == null || getClass() != o.getClass()) {
+                return false;
+            }
+
+            ParentChildPair that = (ParentChildPair) o;
+
+            if (!parent.equals(that.parent)) {
+                return false;
+            }
+            return child.equals(that.child);
+
+        }
+
+        @Override
+        public int hashCode() {
+            int result = parent.hashCode();
+            result = 31 * result + child.hashCode();
+            return result;
+        }
+    }
+
+    /**
+     * True if we saw the root record (the record with a guid of "places") on the server.
+     */
+    public boolean rootOnServer = false;
+
+    /**
+     * List of records where the parent refers to a child that does not exist.
+     */
+    public List<ParentChildPair> missingChildren = new ArrayList<>();
+
+    /**
+     * List of records where the parent refers to a child that was deleted.
+     */
+    public List<ParentChildPair> deletedChildren = new ArrayList<>();
+
+    /**
+     * List of records where the parent was deleted but the child was not.
+     */
+    public List<ParentChildPair> deletedParents = new ArrayList<>();
+
+    /**
+     * List of records with either no parent, or where the parent could not be found.
+     */
+    public List<ParentChildPair> orphans = new ArrayList<>();
+
+    /**
+     * List of records who have the same child listed multiple times in their children array.
+     */
+    public List<ParentChildPair> duplicateChildren = new ArrayList<>();
+
+    /**
+     * List of records who refer to parents that are not folders.
+     */
+    public List<ParentChildPair> parentNotFolder = new ArrayList<>();
+
+    /**
+     * List of server-side records where the child's parentid and parent's children array disagree
+     * with each-other.
+     */
+    public Set<ParentChildPair> parentChildMismatches = new HashSet<>();
+
+    /**
+     * Map of child guid to list of parent guids for records that show up in multiple parents.
+     */
+    public Map<String, List<String>> multipleParents = new HashMap<>();
+
+    /**
+     * Set of ids of records present on the server but missing from the client.
+     */
+    public Set<String> clientMissing = new HashSet<>();
+
+    /**
+     * Set of ids of records present on the client but missing from the server.
+     */
+    public Set<String> serverMissing = new HashSet<>();
+
+    /**
+     * List of ids of records present on the client, with tombstones on the server.
+     */
+    public Set<String> serverDeleted = new HashSet<>();
+
+    /**
+     * List of ids of items where the child guids differ between client and server.
+     * Represents sdiff:childGUIDs, and part of structuralDifferences in the summary.
+     */
+    public Set<String> structuralDifferenceChildGUIDs = new HashSet<>();
+
+    /**
+     * List of ids of items where parentIDs differ between client and server.
+     * Represents sdiff:parentid, and part of structuralDifferences in the summary.
+     */
+    public Set<String> structuralDifferenceParentIDs = new HashSet<>();
+
+    /**
+     * List of ids where the client and server disagree about something not covered by a structural
+     * difference.
+     */
+    public Set<String> differences = new HashSet<>();
+
+
+    private static void addProp(Map<String, Integer> m, String propName, int count) {
+        if (count != 0) {
+            m.put(propName, count);
+        }
+    }
+
+    public Map<String, Integer> summarizeResults() {
+        Map<String, Integer> m = new HashMap<>();
+        if (rootOnServer) {
+            addProp(m, "rootOnServer", 1);
+        }
+        addProp(m, "parentChildMismatches", parentChildMismatches.size());
+        addProp(m, "missingChildren", missingChildren.size());
+        addProp(m, "deletedChildren", deletedChildren.size());
+        addProp(m, "deletedParents", deletedParents.size());
+        addProp(m, "multipleParents", multipleParents.size());
+        addProp(m, "orphans", orphans.size());
+        addProp(m, "duplicateChildren", duplicateChildren.size());
+        addProp(m, "parentNotFolder", parentNotFolder.size());
+        addProp(m, "clientMissing", clientMissing.size());
+        addProp(m, "serverMissing", serverMissing.size());
+        addProp(m, "serverDeleted", serverDeleted.size());
+        addProp(m, "sdiff:childGUIDs", structuralDifferenceChildGUIDs.size());
+        addProp(m, "sdiff:parentid", structuralDifferenceParentIDs.size());
+        addProp(m, "structuralDifferences", structuralDifferenceParentIDs.size() + structuralDifferenceChildGUIDs.size());
+        addProp(m, "differences", differences.size());
+        return m;
+    }
+}

new file mode 100644
--- /dev/null
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/validation/BookmarkValidator.java
@@ -0,0 +1,287 @@
+/* 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/. */
+
+package org.mozilla.gecko.sync.validation;
+
+import org.json.simple.JSONArray;
+import org.mozilla.gecko.sync.repositories.domain.BookmarkRecord;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+
+public class BookmarkValidator {
+    private List<BookmarkRecord> localRecords;
+    private List<BookmarkRecord> remoteRecords;
+
+    private Map<String, BookmarkRecord> remoteGUIDToRecord = new HashMap<>();
+
+
+    /**
+     * Construct a bookmark validator from local and remote records
+     * */
+    public BookmarkValidator(List<BookmarkRecord> localRecords, List<BookmarkRecord> remoteRecords) {
+        this.localRecords = localRecords;
+        this.remoteRecords = remoteRecords;
+        for (BookmarkRecord r : remoteRecords) {
+            remoteGUIDToRecord.put(r.guid, r);
+        }
+    }
+
+    private void checkServerFolder(BookmarkRecord r, BookmarkValidationResults results) {
+        if (r.children == null) {
+            return;
+        }
+        HashSet<String> seenChildGUIDs = new HashSet<>();
+
+        for (int i = 0; i < r.children.size(); ++i) {
+            String childGUID = (String) r.children.get(i);
+            if (seenChildGUIDs.contains(childGUID)) {
+                results.duplicateChildren.add(
+                        new BookmarkValidationResults.ParentChildPair(r.guid, childGUID)
+                );
+                continue;
+            }
+            seenChildGUIDs.add(childGUID);
+
+            BookmarkRecord child = remoteGUIDToRecord.get(childGUID);
+
+            if (child == null) {
+                results.missingChildren.add(
+                        new BookmarkValidationResults.ParentChildPair(r.guid, childGUID)
+                );
+                continue;
+            }
+
+            List<String> parentsContainingChild = results.multipleParents.get(childGUID);
+            if (parentsContainingChild == null) {
+                // Common case, we've never seen a parent with this child before, so we add a
+                // record indicating we've seen one, and what the id was. If there aren't any
+                // other parents of this record, we clean this up before returning the results
+                // to the validator's caller (in cleanupValidationResults).
+                parentsContainingChild = new ArrayList<>();
+                parentsContainingChild.add(r.guid);
+                results.multipleParents.put(childGUID, parentsContainingChild);
+            } else {
+                parentsContainingChild.add(r.guid);
+            }
+
+            if (child.deleted) {
+                results.deletedChildren.add(
+                        new BookmarkValidationResults.ParentChildPair(r.guid, childGUID)
+                );
+                continue;
+            }
+
+            if (!child.parentID.equals(r.guid)) {
+                results.parentChildMismatches.add(
+                        new BookmarkValidationResults.ParentChildPair(r.guid, childGUID)
+                );
+            }
+        }
+    }
+
+    // Check for errors with the parent that aren't covered (or that might only be partially
+    // covered) by the checks in `checkServerFolder`.
+    private void checkServerParent(BookmarkRecord record, BookmarkValidationResults results) {
+        String parentID = record.parentID;
+        if (parentID.equals("places")) {
+            // Parent is the places root, so we don't care.
+            return;
+        }
+        BookmarkRecord listedParent = remoteGUIDToRecord.get(parentID);
+        if (listedParent == null) {
+            results.orphans.add(
+                    new BookmarkValidationResults.ParentChildPair(parentID, record.guid)
+            );
+            return;
+        }
+        if (listedParent.deleted) {
+            results.deletedParents.add(
+                    new BookmarkValidationResults.ParentChildPair(parentID, record.guid)
+            );
+        } else if (!listedParent.isFolder()) {
+            results.parentNotFolder.add(
+                    new BookmarkValidationResults.ParentChildPair(parentID, record.guid)
+            );
+        } else {
+            boolean foundChild = false;
+            for (int i = 0; i < listedParent.children.size() && !foundChild; ++i) {
+                String childGUID = (String) listedParent.children.get(i);
+                foundChild = childGUID.equals(record.guid);
+            }
+            if (!foundChild) {
+                results.parentChildMismatches.add(
+                        new BookmarkValidationResults.ParentChildPair(parentID, record.guid)
+                );
+            }
+        }
+    }
+
+    private void inspectServerRecords(BookmarkValidationResults results) {
+        for (BookmarkRecord record : remoteRecords) {
+            if (record.deleted) {
+                continue;
+            }
+            if (record.guid.equals("places")) {
+                results.rootOnServer = true;
+                continue;
+            }
+            if (record.isFolder()) {
+                checkServerFolder(record, results);
+            }
+            checkServerParent(record, results);
+        }
+    }
+
+    private static class ClientServerPair {
+        BookmarkRecord client;
+        BookmarkRecord server;
+        ClientServerPair(BookmarkRecord client, BookmarkRecord server) {
+            this.client = client;
+            this.server = server;
+        }
+    }
+
+    // Should return false if one or both are missing (and so further comparisons are meaningless.
+    // If they're inconsistent, the error should be recorded in `results`.
+    private boolean checkMissing(ClientServerPair p, BookmarkValidationResults results) {
+
+        boolean clientExists = p.client != null && !p.client.deleted;
+        boolean serverExists = p.server != null && !p.server.deleted;
+
+        boolean serverTombstone = p.server != null && p.server.deleted;
+
+        if (clientExists && !serverExists) {
+            if (serverTombstone) {
+                results.serverDeleted.add(p.client.guid);
+            } else {
+                results.serverMissing.add(p.client.guid);
+            }
+        } else if (serverExists && !clientExists) {
+            results.clientMissing.add(p.server.guid);
+            // Should we distinguish between deleted and missing here? Desktop doesn't,
+            // so to keep consistent metrics we don't either, but maybe both should?
+        }
+
+        return clientExists && serverExists;
+    }
+
+    // Returns true if it found any structural differences, and records them in `results.
+    private boolean checkStructuralDifferences(ClientServerPair p, BookmarkValidationResults results) {
+        boolean sawDiff = false;
+        if (!p.client.parentID.equals(p.server.parentID)) {
+            results.structuralDifferenceParentIDs.add(p.client.guid);
+            // Just record we saw it, since we still want to check the childGUIDs
+            sawDiff = true;
+        }
+
+        if (p.client.children != null && p.server.children != null) {
+            if (p.client.children.size() == p.server.children.size()) {
+                for (int i = 0; i < p.client.children.size(); ++i) {
+                    String clientChildGUID = (String) p.client.children.get(i);
+                    String serverChildGUID = (String) p.server.children.get(i);
+                    if (!clientChildGUID.equals(serverChildGUID)) {
+                        results.structuralDifferenceChildGUIDs.add(p.client.guid);
+                        sawDiff = true;
+                        break;
+                    }
+                }
+            } else {
+                // They have different sizes, so the contents must be different.
+                sawDiff = true;
+                results.structuralDifferenceChildGUIDs.add(p.client.guid);
+            }
+        }
+
+        return sawDiff;
+    }
+
+    // Avoid false positive entries in "differences" caused by our use of congruentWith
+    private BookmarkRecord normalizeRecord(BookmarkRecord r) {
+        if (r.collection == null) {
+            r.collection = "bookmarks";
+        }
+        if (r.tags == null) {
+            // Desktop considers these the same and android doesn't. It's unclear if this is a bug.
+            r.tags = new JSONArray();
+        }
+        return r;
+    }
+
+    private void compareClientWithServer(BookmarkValidationResults results) {
+        Map<String, ClientServerPair> pairsById = new HashMap<>();
+        for (BookmarkRecord r : remoteRecords) {
+            pairsById.put(r.guid, new ClientServerPair(null, normalizeRecord(r)));
+        }
+        for (BookmarkRecord r : localRecords) {
+            if (r.deleted) {
+                continue;
+            }
+            ClientServerPair p = pairsById.get(r.guid);
+            if (p != null) {
+                p.client = normalizeRecord(r);
+            } else {
+                pairsById.put(r.guid, new ClientServerPair(normalizeRecord(r), null));
+            }
+        }
+        for (Entry<String, ClientServerPair> e : pairsById.entrySet()) {
+            ClientServerPair p = e.getValue();
+            if (!checkMissing(p, results)) {
+                continue;
+            }
+
+            // Skip checking for differences if we see a structural difference, since congruentWith
+            // checks structural differences as well.
+            boolean sawStructuralDifference = checkStructuralDifferences(p, results);
+
+            if (!sawStructuralDifference &&
+                    (!p.client.congruentWith(p.server) || !p.server.congruentWith(p.client))) {
+                results.differences.add(p.client.guid);
+            }
+        }
+    }
+
+    // Remove anything in the validation results that shouldn't be reported as an error,
+    // e.g. "multipleParents" with only one item in the list
+    private void cleanupValidationResults(BookmarkValidationResults results) {
+        Map<String, List<String>> filteredMultipleParents = new HashMap<>();
+        for (Entry<String, List<String>> entry : results.multipleParents.entrySet()) {
+            if (entry.getValue().size() >= 2) {
+                filteredMultipleParents.put(entry.getKey(), entry.getValue());
+            }
+        }
+        results.multipleParents = filteredMultipleParents;
+    }
+
+    private BookmarkValidationResults validate() {
+        BookmarkValidationResults results = new BookmarkValidationResults();
+        inspectServerRecords(results);
+        compareClientWithServer(results);
+        cleanupValidationResults(results);
+        return results;
+    }
+
+    /**
+     * Instantiate a validator from client and server records, and perform validation.
+     */
+    public static BookmarkValidationResults validateClientAgainstServer(List<BookmarkRecord> client, List<BookmarkRecord> server) {
+        BookmarkValidator v = new BookmarkValidator(client, server);
+        return v.validate();
+    }
+
+    /**
+     * Perform the server-side portion of the validation only.
+     */
+    public static BookmarkValidationResults validateServer(List<BookmarkRecord> server) {
+        BookmarkValidator v = new BookmarkValidator(new ArrayList<BookmarkRecord>(), server);
+        BookmarkValidationResults results = new BookmarkValidationResults();
+        v.inspectServerRecords(results);
+        v.compareClientWithServer(results);
+        return v.validate();
+    }
+}

new file mode 100644
--- /dev/null
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/validation/CollectionValidator.java
@@ -0,0 +1,9 @@
+/* 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/. */
+
+package org.mozilla.gecko.sync.validation;
+
+public interface CollectionValidator {
+    public ValidationResults validate();
+}

new file mode 100644
--- /dev/null
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/validation/ValidationResults.java
@@ -0,0 +1,39 @@
+/* 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/. */
+
+package org.mozilla.gecko.sync.validation;
+
+import org.json.simple.JSONArray;
+import org.json.simple.JSONObject;
+
+import java.util.List;
+import java.util.Map;
+
+public abstract class ValidationResults {
+    /**
+     * Get the problems found by the validator. Must not contain numbers less than or equal to zero.
+     * Must use the same names for problems as other platforms!
+     */
+    public abstract Map<String, Integer> summarizeResults();
+
+    /**
+     * Get the summary as JSON suitable for including in telemetry
+     */
+    @SuppressWarnings("unchecked")
+    public JSONArray jsonSummary() {
+        Map<String, Integer> problems = summarizeResults();
+        JSONArray result = new JSONArray();
+        for (Map.Entry<String, Integer> problem : problems.entrySet()) {
+            JSONObject o = new JSONObject();
+            o.put("name", problem.getKey());
+            o.put("count", problem.getValue());
+            result.add(o);
+        }
+        return result;
+    }
+
+    public boolean anyProblemsExist() {
+        return summarizeResults().size() > 0;
+    }
+}

new file mode 100644
--- /dev/null
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/sync/test/TestBookmarkValidator.java
@@ -0,0 +1,165 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+package org.mozilla.gecko.sync.test;
+
+import org.json.simple.JSONArray;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mozilla.gecko.background.testhelpers.TestRunner;
+import org.mozilla.gecko.sync.repositories.domain.BookmarkRecord;
+import org.mozilla.gecko.sync.validation.BookmarkValidationResults;
+import org.mozilla.gecko.sync.validation.BookmarkValidator;
+
+import static org.junit.Assert.*;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+@RunWith(TestRunner.class)
+public class TestBookmarkValidator {
+
+    private List<BookmarkRecord> getDummyRecords() {
+        List<BookmarkRecord> l = new ArrayList<>();
+        {
+            BookmarkRecord r = new BookmarkRecord();
+            r.guid = "menu";
+            r.parentID = "places";
+            r.type = "folder";
+            r.title = "foo";
+            r.children = childrenFromGUIDs("aaaaaaaaaaaa", "bbbbbbbbbbbb", "cccccccccccc");
+            l.add(r);
+        }
+        {
+            BookmarkRecord r = new BookmarkRecord();
+            r.guid = "aaaaaaaaaaaa";
+            r.parentID = "menu";
+            r.type = "folder";
+            r.title = "stuff";
+            r.children = new JSONArray();
+            l.add(r);
+        }
+        {
+            BookmarkRecord r = new BookmarkRecord();
+            r.guid = "bbbbbbbbbbbb";
+            r.parentID = "menu";
+            r.type = "bookmark";
+            r.title = "bar";
+            r.bookmarkURI = "http://baz.com";
+            l.add(r);
+        }
+        {
+            BookmarkRecord r = new BookmarkRecord();
+            r.guid = "cccccccccccc";
+            r.parentID = "menu";
+            r.type = "query";
+            r.title = "";
+            r.bookmarkURI = "place:type=6&sort=14&maxResults=10";
+            l.add(r);
+        }
+        return l;
+    }
+
+    @Test
+    public void testMatching() {
+        List<BookmarkRecord> client = getDummyRecords();
+        List<BookmarkRecord> server = getDummyRecords();
+        BookmarkValidationResults v = BookmarkValidator.validateClientAgainstServer(client, server);
+        assertFalse(v.anyProblemsExist());
+    }
+
+    @Test
+    public void testClientMissing() {
+        List<BookmarkRecord> client = getDummyRecords();
+        List<BookmarkRecord> server = getDummyRecords();
+        BookmarkRecord removed = client.remove(client.size() - 1);
+        BookmarkValidationResults v = BookmarkValidator.validateClientAgainstServer(client, server);
+        assertTrue(v.anyProblemsExist());
+        assertEquals(v.clientMissing.size(), 1);
+        assertTrue(v.clientMissing.contains(removed.guid));
+    }
+
+    @Test
+    public void testServerMissing() {
+        // Also tests some other server validation
+        List<BookmarkRecord> client = getDummyRecords();
+        List<BookmarkRecord> server = getDummyRecords();
+        BookmarkRecord removed = server.remove(server.size() - 1);
+        BookmarkValidationResults v = BookmarkValidator.validateClientAgainstServer(client, server);
+        assertTrue(v.anyProblemsExist());
+        assertEquals(v.serverMissing.size(), 1);
+        assertTrue(v.serverMissing.contains(removed.guid));
+        assertEquals(v.missingChildren.size(), 1);
+        assertTrue(v.missingChildren.contains(
+                new BookmarkValidationResults.ParentChildPair("menu", removed.guid)));
+    }
+
+    @Test
+    public void testOrphans() {
+        List<BookmarkRecord> server = getDummyRecords();
+        BookmarkRecord last = server.get(server.size() - 1);
+        last.parentID = "asdfasdfasdf";
+        BookmarkValidationResults v = BookmarkValidator.validateServer(server);
+        assertTrue(v.anyProblemsExist());
+
+        assertEquals(v.orphans.size(), 1);
+        assertTrue(v.orphans.contains(
+                new BookmarkValidationResults.ParentChildPair("asdfasdfasdf", last.guid)));
+
+        assertEquals(v.parentChildMismatches.size(), 1);
+        assertTrue(v.parentChildMismatches.contains(
+                new BookmarkValidationResults.ParentChildPair("menu", last.guid)));
+    }
+
+    @Test
+    public void testServerDeleted() {
+        List<BookmarkRecord> client = getDummyRecords();
+        List<BookmarkRecord> server = getDummyRecords();
+        BookmarkRecord removed = server.remove(server.size() - 1);
+        server.add(createTombstone(removed.guid));
+        BookmarkValidationResults v = BookmarkValidator.validateClientAgainstServer(client, server);
+        assertTrue(v.anyProblemsExist());
+
+        assertEquals(v.serverDeleted.size(), 1);
+        assertTrue(v.serverDeleted.contains(removed.guid));
+        assertEquals(v.serverMissing.size(), 0);
+
+        assertEquals(v.deletedChildren.size(), 1);
+        assertTrue(v.deletedChildren.contains(
+                new BookmarkValidationResults.ParentChildPair(removed.parentID, removed.guid)));
+
+        assertEquals(v.missingChildren.size(), 0);
+    }
+
+    @Test
+    public void testMultipleParents() {
+        List<BookmarkRecord> server = getDummyRecords();
+        BookmarkRecord otherFolder = server.get(1);
+        assertEquals(otherFolder.type, "folder");
+        otherFolder.children = childrenFromGUIDs("bbbbbbbbbbbb");
+
+        BookmarkValidationResults v = BookmarkValidator.validateServer(server);
+        assertTrue(v.anyProblemsExist());
+
+        assertEquals(v.parentChildMismatches.size(), 1);
+        assertTrue(v.parentChildMismatches.contains(
+                new BookmarkValidationResults.ParentChildPair(otherFolder.guid, "bbbbbbbbbbbb")));
+
+        assertEquals(v.multipleParents.size(), 1);
+        assertTrue(v.multipleParents.containsKey("bbbbbbbbbbbb"));
+        List<String> parentGUIDs = v.multipleParents.get("bbbbbbbbbbbb");
+        assertEquals(parentGUIDs.size(), 2);
+        assertTrue(parentGUIDs.contains("menu"));
+        assertTrue(parentGUIDs.contains("aaaaaaaaaaaa"));
+    }
+
+    private BookmarkRecord createTombstone(String guid) {
+        return new BookmarkRecord(guid, BookmarkRecord.COLLECTION_NAME, 0, true);
+    }
+
+    @SuppressWarnings("unchecked")
+    private JSONArray childrenFromGUIDs(String... guids) {
+        JSONArray children = new JSONArray();
+        children.addAll(Arrays.asList(guids));
+        return children;
+    }
+}