@tangle/reduce
Advanced tools
Comparing version 1.0.3 to 2.0.0
199
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) | ||
} | ||
} |
{ | ||
"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" | ||
} | ||
} |
@@ -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. | ||
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: { |
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: { |
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: { |
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: { |
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() | ||
}) |
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
23577
10
755
126
6
+ Added@tangle/graph@2.1.0(transitive)
- Removed@tangle/graph@1.3.1(transitive)
Updated@tangle/graph@^2.1.0