pouchdb-merge - npm Package Compare versions

Comparing version 7.3.1 to 8.0.0

lib/index.es.js

@@ -0,1 +1,3 @@
+import { clone } from 'pouchdb-utils';
+
 // We fetch all leafs of the revision tree, and sort them based on tree length
@@ -104,2 +106,58 @@ // and whether they were deleted, undeleted documents with the longest revision
 
+// `findPathToLeaf()` returns an array of revs that goes from the specified
+// leaf rev to the root of that leaf’s branch.
+//
+// eg. for this rev tree:
+// 1-9692 ▶ 2-37aa ▶ 3-df22 ▶ 4-6e94 ▶ 5-df4a ▶ 6-6a3a ▶ 7-57e5
+//          ┃                 ┗━━━━━━▶ 5-8d8c ▶ 6-65e0
+//          ┗━━━━━━▶ 3-43f6 ▶ 4-a3b4
+//
+// For a `targetRev` of '7-57e5', `findPathToLeaf()` would return ['7-57e5', '6-6a3a', '5-df4a']
+// The `revs` arument has the same structure as what `revs_tree` has on e.g.
+// the IndexedDB representation of the rev tree datastructure. Please refer to
+// tests/unit/test.purge.js for examples of what these look like.
+//
+// This function will throw an error if:
+// - The requested revision does not exist
+// - The requested revision is not a leaf
+function findPathToLeaf(revs, targetRev) {
+  let path = [];
+  const toVisit = revs.slice();
+
+  let node;
+  while ((node = toVisit.pop())) {
+    const { pos, ids: tree } = node;
+    const rev = `${pos}-${tree[0]}`;
+    const branches = tree[2];
+
+    // just assuming we're already working on the path up towards our desired leaf.
+    path.push(rev);
+
+    // we've reached the leaf of our dreams, so return the computed path.
+    if (rev === targetRev) {
+      //…unleeeeess
+      if (branches.length !== 0) {
+        throw new Error('The requested revision is not a leaf');
+      }
+      return path.reverse();
+    }
+
+    // this is based on the assumption that after we have a leaf (`branches.length == 0`), we handle the next
+    // branch. this is true for all branches other than the path leading to the winning rev (which is 7-57e5 in
+    // the example above. i've added a reset condition for branching nodes (`branches.length > 1`) as well.
+    if (branches.length === 0 || branches.length > 1) {
+      path = [];
+    }
+
+    // as a next step, we push the branches of this node to `toVisit` for visiting it during the next iteration
+    for (let i = 0, len = branches.length; i < len; i++) {
+      toVisit.push({ pos: pos + 1, ids: branches[i] });
+    }
+  }
+  if (path.length === 0) {
+    throw new Error('The requested revision does not exist');
+  }
+  return path.reverse();
+}
+
 // build up a list of all the paths to the leafs in this revision tree
@@ -370,2 +428,41 @@ function rootToLeaf(revs) {
 
+// this method removes a leaf from a rev tree, independent of its status.
+// e.g., by removing an available leaf, it could leave its predecessor as
+// a missing leaf and corrupting the tree.
+function removeLeafFromRevTree(tree, leafRev) {
+  return tree.flatMap((path) => {
+    path = removeLeafFromPath(path, leafRev);
+    return path ? [path] : [];
+  });
+}
+
+function removeLeafFromPath(path, leafRev) {
+  const tree = clone(path);
+  const toVisit = [tree];
+  let node;
+
+  while ((node = toVisit.pop())) {
+    const { pos, ids: [id, , branches], parent } = node;
+    const isLeaf = branches.length === 0;
+    const hash = `${pos}-${id}`;
+
+    if (isLeaf && hash === leafRev) {
+      if (!parent) {
+        // FIXME: we're facing the root, and probably shouldn't just return an empty array (object? null?).
+        return null;
+      }
+
+      parent.ids[2] = parent.ids[2].filter(function (branchNode) {
+        return branchNode[0] !== id;
+      });
+      return tree;
+    }
+
+    for (let i = 0, len = branches.length; i < len; i++) {
+      toVisit.push({ pos: pos + 1, ids: branches[i], parent: node });
+    }
+  }
+  return tree;
+}
+
 // return true if a rev exists in the rev tree, false otherwise
@@ -454,2 +551,2 @@ function revExists(revs, rev) {
 
-export { collectConflicts, collectLeaves, compactTree, isDeleted, isLocalId, merge, revExists, rootToLeaf, traverseRevTree, winningRev, latest };
+export { collectConflicts, collectLeaves, compactTree, findPathToLeaf, isDeleted, isLocalId, merge, removeLeafFromRevTree as removeLeafFromTree, revExists, rootToLeaf, traverseRevTree, winningRev, latest };

lib/index.js

@@ -5,2 +5,4 @@ 'use strict';
 
+var pouchdbUtils = require('pouchdb-utils');
+
 // We fetch all leafs of the revision tree, and sort them based on tree length
@@ -109,2 +111,58 @@ // and whether they were deleted, undeleted documents with the longest revision
 
+// `findPathToLeaf()` returns an array of revs that goes from the specified
+// leaf rev to the root of that leaf’s branch.
+//
+// eg. for this rev tree:
+// 1-9692 ▶ 2-37aa ▶ 3-df22 ▶ 4-6e94 ▶ 5-df4a ▶ 6-6a3a ▶ 7-57e5
+//          ┃                 ┗━━━━━━▶ 5-8d8c ▶ 6-65e0
+//          ┗━━━━━━▶ 3-43f6 ▶ 4-a3b4
+//
+// For a `targetRev` of '7-57e5', `findPathToLeaf()` would return ['7-57e5', '6-6a3a', '5-df4a']
+// The `revs` arument has the same structure as what `revs_tree` has on e.g.
+// the IndexedDB representation of the rev tree datastructure. Please refer to
+// tests/unit/test.purge.js for examples of what these look like.
+//
+// This function will throw an error if:
+// - The requested revision does not exist
+// - The requested revision is not a leaf
+function findPathToLeaf(revs, targetRev) {
+  let path = [];
+  const toVisit = revs.slice();
+
+  let node;
+  while ((node = toVisit.pop())) {
+    const { pos, ids: tree } = node;
+    const rev = `${pos}-${tree[0]}`;
+    const branches = tree[2];
+
+    // just assuming we're already working on the path up towards our desired leaf.
+    path.push(rev);
+
+    // we've reached the leaf of our dreams, so return the computed path.
+    if (rev === targetRev) {
+      //…unleeeeess
+      if (branches.length !== 0) {
+        throw new Error('The requested revision is not a leaf');
+      }
+      return path.reverse();
+    }
+
+    // this is based on the assumption that after we have a leaf (`branches.length == 0`), we handle the next
+    // branch. this is true for all branches other than the path leading to the winning rev (which is 7-57e5 in
+    // the example above. i've added a reset condition for branching nodes (`branches.length > 1`) as well.
+    if (branches.length === 0 || branches.length > 1) {
+      path = [];
+    }
+
+    // as a next step, we push the branches of this node to `toVisit` for visiting it during the next iteration
+    for (let i = 0, len = branches.length; i < len; i++) {
+      toVisit.push({ pos: pos + 1, ids: branches[i] });
+    }
+  }
+  if (path.length === 0) {
+    throw new Error('The requested revision does not exist');
+  }
+  return path.reverse();
+}
+
 // build up a list of all the paths to the leafs in this revision tree
@@ -375,2 +433,41 @@ function rootToLeaf(revs) {
 
+// this method removes a leaf from a rev tree, independent of its status.
+// e.g., by removing an available leaf, it could leave its predecessor as
+// a missing leaf and corrupting the tree.
+function removeLeafFromRevTree(tree, leafRev) {
+  return tree.flatMap((path) => {
+    path = removeLeafFromPath(path, leafRev);
+    return path ? [path] : [];
+  });
+}
+
+function removeLeafFromPath(path, leafRev) {
+  const tree = pouchdbUtils.clone(path);
+  const toVisit = [tree];
+  let node;
+
+  while ((node = toVisit.pop())) {
+    const { pos, ids: [id, , branches], parent } = node;
+    const isLeaf = branches.length === 0;
+    const hash = `${pos}-${id}`;
+
+    if (isLeaf && hash === leafRev) {
+      if (!parent) {
+        // FIXME: we're facing the root, and probably shouldn't just return an empty array (object? null?).
+        return null;
+      }
+
+      parent.ids[2] = parent.ids[2].filter(function (branchNode) {
+        return branchNode[0] !== id;
+      });
+      return tree;
+    }
+
+    for (let i = 0, len = branches.length; i < len; i++) {
+      toVisit.push({ pos: pos + 1, ids: branches[i], parent: node });
+    }
+  }
+  return tree;
+}
+
 // return true if a rev exists in the rev tree, false otherwise
@@ -462,5 +559,7 @@ function revExists(revs, rev) {
 exports.compactTree = compactTree;
+exports.findPathToLeaf = findPathToLeaf;
 exports.isDeleted = isDeleted;
 exports.isLocalId = isLocalId;
 exports.merge = merge;
+exports.removeLeafFromTree = removeLeafFromRevTree;
 exports.revExists = revExists;
@@ -467,0 +566,0 @@ exports.rootToLeaf = rootToLeaf;

package.json

 {
   "name": "pouchdb-merge",
-  "version": "7.3.1",
+  "version": "8.0.0",
   "description": "PouchDB's document merge algorithm.",
@@ -15,3 +15,5 @@ "main": "./lib/index.js",
   "jsnext:main": "./lib/index.es.js",
-  "dependencies": {},
+  "dependencies": {
+    "pouchdb-utils": "8.0.0"
+  },
   "module": "./lib/index.es.js",
@@ -18,0 +20,0 @@ "files": [

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

45302

increased by18.11%

Lines of code

986

increased by20.83%

Worsened metrics

Dependency count

1

increased byInfinity%

Dependency changes

• + Addedpouchdb-utils@8.0.0

• + Addedbuffer-from@1.1.2(transitive)

• + Addedclone-buffer@1.0.0(transitive)

• + Addedimmediate@3.3.0(transitive)

• + Addedpouchdb-binary-utils@8.0.0(transitive)

• + Addedpouchdb-collections@8.0.0(transitive)

• + Addedpouchdb-errors@8.0.0(transitive)

• + Addedpouchdb-md5@8.0.0(transitive)

• + Addedpouchdb-utils@8.0.0(transitive)

• + Addedspark-md5@3.0.2(transitive)

• + Addeduuid@8.3.2(transitive)