@tangle/reduce - npm Package Compare versions

Comparing version 1.0.3 to 2.0.0

index.js

 const Graph = require('@tangle/graph')
 const Queue = require('./queue')
 
-module.exports = function reduce (nodes, strategy, opts = {}) {
-  const {
-    getTransformation = node => node,
-    getBacklinks = node => node.previous,
-    isValid
-  } = opts
+module.exports = class Reduce {
+  constructor (strategy, opts = {}) {
+    this.strategy = strategy
 
-  const graph = new Graph(nodes, { getBacklinks })
+    const {
+      nodes = [],
+      getTransformation = node => node,
+      getBacklinks = node => node.previous,
+      isValid
+    } = opts
+    // TODO prune time-travllers
+    this.graph = new Graph(nodes, { getBacklinks })
+    this.isValid = isValid
 
-  // TODO prune time-travllers
+    this.getT = (nodeId) => {
+      return strategy.pureTransformation(
+        getTransformation(this.graph.getNode(nodeId))
+      )
+    }
 
-  const { concat, pureTransformation } = strategy
-  const getT = (nodeId) => {
-    return pureTransformation(
-      getTransformation(graph.getNode(nodeId))
-    )
+    this._resolvedState = null
   }
 
-  var queue = new Queue()
-  // a queue made up of elements { nodeId, accT }
-  //   nodeId = the unique identifier for a node
-  //   accT = the accumulated (concat'd) Transformation up to and including the Transformation
-  //          described in node 'nodeId'
-
-  if (isValid) {
-    const initialContext = { accT: strategy.identity(), graph }
-
-    graph.rootNodes.forEach(node => {
-      if (!isValid(initialContext, node)) {
-        throw new Error('tangle starting node invalid!')
-      }
-    })
+  get state () {
+    return this.resolve()
   }
 
-  graph.rootNodeKeys.forEach(key => {
-    queue.add({
-      nodeId: key,
-      accT: getT(key)
-    })
-  })
+  resolve () {
+    if (this._state) return this._resolvedState
 
-  var tips = {
-    preMerge: new Map(),
-    // a Map of form { [nodeId]: accT }
-    // which describes the nodes immediately preceeding a merge-node
-    terminal: {}
-  }
+    const { graph, strategy, getT, isValid } = this
 
-  while (!queue.isEmpty()) {
-    var { nodeId, accT } = queue.next()
-    // accT is the accumulated Transformation so far
-    // (NOT including Transformation stored in key though, that's what we're )
+    const queue = new Queue()
+    // a queue made up of elements { nodeId, accT }
+    //   nodeId = the unique identifier for a node
+    //   accT = the accumulated (concat'd) Transformation up to and including the Transformation
+    //          described in node 'nodeId'
 
     if (isValid) {
-      // check if the next steps are valid before taking them
-      // prune here, because this migh change which nodes are new tips / tips
-      graph.getLinks(nodeId).forEach(nextId => {
-        const nextNodeValid = isValid({ accT, graph }, graph.getNode(nextId))
-        if (!nextNodeValid) graph.invalidateKeys([nextId])
+      const initialContext = { accT: strategy.identity(), graph }
+
+      graph.rootNodes.forEach(node => {
+        if (!isValid(initialContext, node)) {
+          throw new Error('tangle starting node invalid!')
+        }
       })
     }
 
-    if (graph.isHeadNode(nodeId)) {
-      tips.terminal[nodeId] = accT
-      continue
+    graph.rootNodeKeys.forEach(key => {
+      queue.add({
+        nodeId: key,
+        accT: getT(key)
+      })
+    })
+
+    const tips = {
+      preMerge: new Map(),
+      // a Map of form { [nodeId]: accT }
+      // which describes the nodes immediately preceeding a merge-node
+      terminal: {}
     }
 
-    graph.getLinks(nodeId).forEach(nextId => {
-      if (!graph.isMergeNode(nextId)) {
-        queue.add({
-          nodeId: nextId,
-          accT: concat(accT, getT(nextId))
+    while (!queue.isEmpty()) {
+      const { nodeId, accT } = queue.next()
+      // accT is the accumulated Transformation so far
+      // (NOT including Transformation stored in key though, that's what we're )
+
+      if (isValid) {
+      // check if the next steps are valid before taking them
+      // prune here, because this migh change which nodes are new tips / tips
+        graph.getLinks(nodeId).forEach(nextId => {
+          const nextNodeValid = isValid({ accT, graph }, graph.getNode(nextId))
+          if (!nextNodeValid) graph.invalidateKeys([nextId])
         })
+      }
+
+      if (graph.isTipNode(nodeId)) {
+        tips.terminal[nodeId] = accT
+        continue
+      }
+
+      graph.getLinks(nodeId).forEach(nextId => {
+        if (!graph.isMergeNode(nextId)) {
+          queue.add({
+            nodeId: nextId,
+            accT: strategy.concat(accT, getT(nextId))
+          })
         // queue up the another node to explore from
-      } else {
-        tips.preMerge.set(nodeId, accT)
+        } else {
+          tips.preMerge.set(nodeId, accT)
 
-        const requiredKeys = graph.getBacklinks(nextId)
-        const ready = requiredKeys.every(nodeId => tips.preMerge.has(nodeId))
-        // check tips.preMerge store to see if we now have the state needed to complete merge
+          const requiredKeys = graph.getBacklinks(nextId)
+          const ready = requiredKeys.every(nodeId => tips.preMerge.has(nodeId))
+          // check tips.preMerge store to see if we now have the state needed to complete merge
 
-        if (ready) {
+          if (ready) {
           // <----- WIP-start----->
-          console.warn('! WARNING ! - reducing merges safely is not yet fully working')
-          // const preMergeTransformations = requiredKeys.map(nodeId => tips.preMerge.get(nodeId))
-          const mergeTransformation = getT(nextId)
+            console.warn('! WARNING ! - reducing merges safely is not yet fully working')
+            // const preMergeTransformations = requiredKeys.map(nodeId => tips.preMerge.get(nodeId))
+            const mergeTransformation = getT(nextId)
 
-          // ALGORITHM:
-          // is there a conflict between tips (preMergeTransformations) ?
-          // - no: concat the tips, then concat result with mergeTransformation
-          // - yes: does mergeTransformation resolves tips conflict?
-          //    - yes: do it (TODO decide what merge is in the case of composition other than overwrite
-          //    - no: throw out the merge....
-          //
-          //  functions needed:
-          //  - [x] IsConflict(composition)(tips)
-          //  - [x] Concat(composition)(tips)
-          //  - [ ] IsValidMerge
-          //
-          //  intended direction:
-          //  - build ComposeRule(composition), which has concat+merge methods
+            // ALGORITHM:
+            // is there a conflict between tips (preMergeTransformations) ?
+            // - no: concat the tips, then concat result with mergeTransformation
+            // - yes: does mergeTransformation resolves tips conflict?
+            //    - yes: do it (TODO decide what merge is in the case of composition other than overwrite
+            //    - no: throw out the merge....
+            //
+            //  functions needed:
+            //  - [x] IsConflict(composition)(tips)
+            //  - [x] Concat(composition)(tips)
+            //  - [ ] IsValidMerge
+            //
+            //  intended direction:
+            //  - build ComposeRule(composition), which has concat+merge methods
 
-          queue.add({
-            nodeId: nextId,
-            // accT: nextT
-            accT: mergeTransformation
-          })
-          // this just treats merge like an overwrite (ignoring all transformations so far)
-          // and for all properties, which is wrong because it ignores invalid merges, and over-writes un-named values with identity
+            queue.add({
+              nodeId: nextId,
+              // accT: nextT
+              accT: mergeTransformation
+            })
+            // this just treats merge like an overwrite (ignoring all transformations so far)
+            // and for all properties, which is wrong because it ignores invalid merges, and over-writes un-named values with identity
 
           // <----- WIP-end----->
+          }
         }
-      }
-    })
+      })
+    }
+
+    this._resolvedState = tips.terminal
+    return this._resolvedState
   }
 
-  return tips.terminal
+  addNodes (nodes) {
+    this._resolvedState = null
+    this.graph.addNodes(nodes)
+  }
 }

package.json

 {
   "name": "@tangle/reduce",
-  "version": "1.0.3",
+  "version": "2.0.0",
   "description": "reduce tangles into their current state",
   "main": "index.js",
   "scripts": {
-    "test": "tape test/*.test.js | tap-spec"
+    "test": "tape test/*.test.js | faucet",
+    "lint": "standard --fix"
   },
@@ -25,11 +26,12 @@ "repository": {
   "devDependencies": {
-    "@tangle/overwrite": "^1.0.0",
-    "@tangle/simple-set": "^1.0.0",
-    "@tangle/strategy": "^1.0.0",
-    "tap-spec": "^5.0.0",
+    "@tangle/overwrite": "^1.2.0",
+    "@tangle/simple-set": "^1.2.2",
+    "@tangle/strategy": "^1.4.1",
+    "faucet": "0.0.1",
+    "standard": "^16.0.3",
     "tape": "^5.0.1"
   },
   "dependencies": {
-    "@tangle/graph": "^1.2.0"
+    "@tangle/graph": "^2.1.0"
   }
 }

README.md

@@ -47,3 +47,3 @@ # @tangle/reduce
 ```js
-const reduce = require('@tangle/reduce')
+const Reduce = require('@tangle/reduce')
 const Srategy = require('@tangle/strategy')
@@ -56,3 +56,3 @@
 
-const result = reduce(nodes, strategy)
+const result = new Reduce(strategy, { nodes })
 // => {
@@ -83,19 +83,19 @@ //   D: {
 
-### `reduce(nodes, strategy, opts) => tips`
+### `new Reduce(strategy, opts) => reduce`
 
-where:
+Instantiates a new reduce helper
 
-`nodes` *Array* is a collection of tangle nodes, where each expected to include:
-  - `node.key` - a unique identified for the node
-  - "backlinks"
-    - an Array of keys for nodes which this node extended from (or `null` if it's a root node)
-    - default location: `node.previous` (can be over-ridden, see opts)
-  - "transformation"
-    - an object which containing the transformation which the `strategy` describes
-    - default location: `node` (can be over-ridden, see opts)
-
 `strategy` *Object* defines how to reduce nodes. Produced by `@tangle/strategy`
 
 `opts` *Object* (optional) is an object which lets you to customise the reduce:
-  - `opts.getTransformation = fn(node): Object`
+- `opts.nodes` *Array* is a collection of tangle nodes, where each expected to include:
+    - `node.key` - a unique identified for the node
+    - "backlinks"
+      - an Array of keys for nodes which this node extended from (or `null` if it's a root node)
+      - default location: `node.previous` (can be over-ridden with `opts.getBacklinks`)
+    - "transformation"
+      - an object which containing the transformation which the `strategy` describes
+      - default location: `node` (can be over-ridden with `opts.getTransformation`)
+
+- `opts.getTransformation = fn(node): Object`
     - fetch the part of the node which contains the transformation
@@ -105,7 +105,7 @@ - default: `node => node`
 
-  - `opts.getBacklinks = fn(node): Array`
+- `opts.getBacklinks = fn(node): Array`
     - fetch the part of the node which contains the backlinks to the nodes it followed in the tangle
     - default: `node => node.previous`
 
-  - `opts.isValid = fn(context, node): Boolean`
+- `opts.isValid = fn(context, node): Boolean`
     - determine whether the next node `node` should be included in the tangle
@@ -117,1 +117,14 @@ - `context` is the context in the tangle immediately before `node`, and is an object `{ graph, accT }`
 
+
+### `reduce.resolve() => resolvedState`
+
+A getter which accesses the current resolved state for the
+
+_alias: `reduce.state` (a getter)_
+
+
+### `reduce.addNodes(nodes)`
+
+Register more nodes to include in the reducing.
+
+

test/get-backlinks.test.js

 const test = require('tape')
-const reduce = require('../')
+const Reduce = require('../index')
 
@@ -35,4 +35,5 @@ const Strategy = require('@tangle/strategy')
 
+  const reduce = new Reduce(strategy, { nodes: [A, B], getBacklinks })
   t.deepEqual(
-    reduce([A, B], strategy, { getBacklinks }),
+    reduce.state,
     {
@@ -39,0 +40,0 @@ B: {

test/get-transformation.test.js

 const test = require('tape')
-const reduce = require('../')
+const Reduce = require('../')
 
@@ -36,5 +36,4 @@ const Strategy = require('@tangle/strategy')
   const getTransformation = node => node.mutations
-
   t.deepEqual(
-    reduce([A, B], strategy, { getTransformation }),
+    new Reduce(strategy, { nodes: [A, B], getTransformation }).state,
     {
@@ -41,0 +40,0 @@ B: {

test/is-valid.test.js

 const test = require('tape')
-const reduce = require('../')
+const Reduce = require('../')
 
@@ -60,5 +60,4 @@ const Strategy = require('@tangle/strategy')
   }
-
   t.deepEqual(
-    reduce([A, B, C], strategy, { isValid }),
+    new Reduce(strategy, { nodes: [A, B, C], isValid }).state,
     {
@@ -88,3 +87,3 @@ A: {
   t.deepEqual(
-    reduce([X, Y], strategy, { isValid }),
+    new Reduce(strategy, { nodes: [X, Y], isValid }).state,
     {
@@ -91,0 +90,0 @@ Y: {

test/merge.test.js

 const test = require('tape')
-const reduce = require('../')
+const Reduce = require('../')
 
@@ -12,3 +12,4 @@ const Strategy = require('@tangle/strategy')
   // conflictMerge: (merge, heads) => merge,
-  reify: a => a
+  reify: a => a,
+  schema: { type: 'object' }
 })
@@ -43,5 +44,4 @@
   }
-
   t.deepEqual(
-    reduce([A, B, C], strategy),
+    new Reduce(strategy, { nodes: [A, B, C] }).state,
     {
@@ -65,3 +65,2 @@ B: {
   //     D
-
   const D = {
@@ -77,3 +76,3 @@ key: 'D',
   t.deepEqual(
-    reduce([A, B, C, D], strategy),
+    new Reduce(strategy, { nodes: [A, B, C, D] }).state,
     {
@@ -126,3 +125,3 @@ D: {
   t.deepEqual(
-    reduce([A, B, C, Dud], strategy),
+    new Reduce(strategy, { nodes: [A, B, C, Dud] }).state,
     {
@@ -187,3 +186,3 @@ B: {
   t.deepEqual(
-    reduce([A, B, C, D, E], strategy),
+    new Reduce(strategy, { nodes: [A, B, C, D, E] }).state,
     {
@@ -190,0 +189,0 @@ E: {

test/simple.test.js

 const test = require('tape')
-const reduce = require('../')
+const Reduce = require('../')
 
 const Strategy = require('@tangle/strategy')
 const Overwrite = require('@tangle/overwrite')
+const SimpleSet = require('@tangle/simple-set')
 
@@ -29,3 +30,3 @@ const strategy = new Strategy({
   t.deepEqual(
-    reduce([A], strategy),
+    new Reduce(strategy, { nodes: [A] }).state,
     {
@@ -39,3 +40,3 @@ A: {
   t.deepEqual(
-    reduce([A, B], strategy),
+    new Reduce(strategy, { nodes: [A, B] }).state,
     {
@@ -48,3 +49,144 @@ B: {
 
+  t.deepEqual(new Reduce(strategy).state, {}, 'can reduce an empty graph')
+
   t.end()
 })
+
+test('reduce (branches)', t => {
+//    A
+//   /  \
+//  B   C
+//      /\
+//     D  E
+  const menuStrategy = new Strategy({
+    title: Overwrite(),
+    menu: SimpleSet()
+  })
+
+  const A = {
+    key: 'A',
+    author: '@colin',
+    previous: null,
+    title: { set: 'What are people bringing to potluck?' }
+  }
+
+  const B = {
+    key: 'B',
+    author: '@rudeperson',
+    previous: ['A'],
+    menu: { pizza: 1 }
+  }
+  const C = {
+    key: 'C',
+    author: '@glutenintolerant',
+    previous: ['A'],
+    menu: { salad: 1 },
+    comment: 'Nothing with gluten'
+  }
+  const D = {
+    key: 'D',
+    author: '@rudeperson',
+    previous: ['C'],
+    menu: { pizza: -1 },
+    comment: 'whoops'
+  }
+  const E = {
+    key: 'E',
+    author: '@someoneelse',
+    previous: ['C'],
+    title: { set: 'final menu' },
+    menu: { drinks: 1 }
+  }
+  console.warn('Start test')
+  // Testing how the tangle reduces with branching nodes
+  t.deepEqual(
+    new Reduce(menuStrategy, { nodes: [A] }).state,
+    {
+      A: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: {} // Note that menu is included even though it was not in A.
+      }
+    },
+    'Just the root'
+  )
+
+  t.deepEqual(
+    new Reduce(menuStrategy, { nodes: [A, B] }).state,
+    {
+      B: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: { pizza: 1 }
+      }
+    },
+    'AB: a simple reduce that adds to the menu'
+  )
+  t.deepEqual(
+    new Reduce(menuStrategy, { nodes: [A, B, C] }).state,
+    {
+      B: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: { pizza: 1 }
+      },
+      C: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: { salad: 1 }
+      }
+    },
+    'ABC: A branch with two tips that add to menu'
+  )
+
+  t.deepEqual(
+    new Reduce(menuStrategy, { nodes: [A, B, C, D, E] }).state,
+    {
+      B: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: { pizza: 1 }
+      },
+      D: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: { salad: 1, pizza: -1 }
+      },
+      E: {
+        title: { set: 'final menu' },
+        menu: { salad: 1, drinks: 1 }
+      }
+    },
+    'ABCDE: Reduces whole graph. Changes title and removes item from menu'
+  )
+
+  t.deepEqual(
+    new Reduce(menuStrategy, { nodes: [A, C, E] }).state,
+    {
+      E: {
+        title: { set: 'final menu' },
+        menu: { salad: 1, drinks: 1 }
+      }
+    },
+    'ACE, missing the branch nodes'
+  )
+
+  t.deepEqual(
+    new Reduce(menuStrategy, { nodes: [A, B, D, E] }).state,
+    {
+    // Ignore nodes that are unconnected
+      B: {
+        title: { set: 'What are people bringing to potluck?' },
+        menu: { pizza: 1 }
+      }
+    },
+    'ABDE, missing connecting node C'
+  )
+  // After reducing the graph we can try to use strategy.reify
+  // But there may be multiple nodes after reducing
+  t.deepEqual(
+    menuStrategy.reify((new Reduce(menuStrategy, { nodes: [A, B, C, D, E] }).state).E),
+    {
+      title: 'final menu',
+      menu: ['drinks', 'salad']
+    }
+    ,
+    'Reify E in ABCDE'
+  )
+
+  t.end()
+})

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

23577

increased by38.4%

Number of package files

10

increased by11.11%

Lines of code

755

increased by52.53%

Number of lines in readme file

126

increased by11.5%

Worsened metrics

Dev dependency count

6

increased by20%

Dependency changes

• + Added@tangle/graph@2.1.0(transitive)

• - Removed@tangle/graph@1.3.1(transitive)

• Updated@tangle/graph@^2.1.0