composeWalker - Composable Graph Walker

composeWalker.js

// Copyright 2017 Adam Laughlin (github.com/a-laughlin).
// License - MIT

const _ = require('lodash');
// Temporarily abstracting this to a gist from private functions in another repo.
// Eventually destined for its own repo with documentation and testing given its usefulness.
// TBD notes are scattered through the code, and need creation as GH issues on transfer.

/**
 * composeWalker
 * extension-based inversion-of-control graph walking function
 * walks a graph of any shape, calling extension lifecycle methods during the walk.
 * Extensions can perform operations like transforming a node list into a tree, testing for cycles,
 * topologically sorting nodes, etc.
 *
 * @param {object,array} one or more extension objects with lifecycle methods to inject (line 46)
 * @returns {function} a walker fn that accepts an iterable collection (object or array)
 * @example composeWalker({getRelated:fn})(collection) // single extension as object
 * @example composeWalker({getRelated:fn},{onVisit:fn})(collection) // extensions as arguments
 * @example composeWalker([{getRelated:fn},{onVisit:fn}])(collection) // extensions as array
 */
function composeWalker(){
  const lifecycleFns = applyDefaultValues(combineExtensions(_.flatten(arguments)));

  return function composedWalkers(collection){
    if (!Array.isArray(collection) && !_.isPlainObject(collection)){collectionErr();}
    const collectionMeta = {}; // TBD wrap in a get/set api to prevent namespace conflicts
    const walkFn = lifecycleFns.getWalkerFn(lifecycleFns, collectionMeta);
    lifecycleFns.preWalk(collection, collectionMeta);
    _.each(collection, (val, key)=>{
      lifecycleFns.spreadNode(val, key, collectionMeta).forEach(walkFn);
    });
    lifecycleFns.postWalk(collection, collectionMeta);
    return collectionMeta;
  };


  function combineExtensions(rawExts){
    // TBD: These lifecycle fns work in a depthFirst traverse.  A DFT currently
    //      satisfies all my use cases.  May need to add additional fns for other cases.
    //      Standardizing lifecycle methods across traversal functions would be ideal
    //      for extension api simplicity/learnability.  However, need more use cases
    //      before standardizing args makes sense.
    const combined = {
      // Exactly one extension must defined a getRelated function in order to walk graph
      getRelated:undefined, // return an array of 0-n nodes to walk
      // optional fns definable 0-1 times across all extensions
      setResolved:undefined, // default is resolvedMap.set(node, relatedNodesArray)
      getResolved:undefined, // default is resolvedMap.get(node) -> relatedNodesArray
      spreadNode:undefined, // default is (node)=>[node] - should return a 1-n nodes array to iterate over
      getWalkerFn:undefined, // traversal function getter. Default is walkerExtensions.depthFirst
                             // Note: walk modification functions, e.g., stop/skip are currently
                             // implemented by whatever function getWalkerFn returns

      // optional fns definable 0-n times across all extensions
      // TBD: Each lifecycle method merits its own params documentation once the API is stable.
      //      Including default depthFirst args for reference.
      preWalk:[], // (collection, collectionMeta)
      postWalk:[], // (collection, collectionMeta)
      onVisit:[], // (node, walkModifiers, depth, collectionMeta)=>{}
      onVisitRelated:[], // (node, related, walkModifiers, depth, collectionMeta)=>{}
      afterVisitRelated:[], // (node, related, walkModifiers, subRelated, depth, collectionMeta)=>{}
      onResolve:[], // (node, immediateRelated, walkModifiers, depth, allRelated, collectionMeta)
    };
    rawExts.forEach((extObj)=>{
      extObj = _.isFunction(extObj) ? extObj() : extObj;
      if (!_.isPlainObject(extObj)){extShapeErr(extObj);}
      _.each(extObj, (val, key)=>{
        if (!(key in combined)){extErr('unrecognized', key, val);}
        if (val === undefined){extErr('missing value for', key, val);}
        else if (Array.isArray(combined[key])){combined[key].push(..._.castArray(val));}
        else if (combined[key] === undefined){combined[key] = extObj[key];}
        else {extErr('cannot set duplicate', key, val);}
      });
    });
    const gr = 'getRelated';
    if (!_.isFunction(combined[gr])){extErr(`missing valid function for`, gr, combined[gr]);}
    // convert arrays of functions to functions that call the arrays' functions with identical arguments
    _.forOwn(combined, (fnVal, fnKey)=>{
      if (!Array.isArray(fnVal)){return;}
      const L = fnVal.length;
      combined[fnKey] = function(){
        let i = -1;
        let lastArg;
        while (++i < L){lastArg = fnVal[i](...arguments, lastArg);}
        return lastArg;
      };
    });
    return combined;
  }

  function applyDefaultValues(combined){
    return _.defaults(combined, walkerExtensions.defaults); // eslint-disable-line no-use-before-define
  }

  function extErr(msg, key, val){throw new Error(`${msg} walker extension ${key}:${val}.`);}
  function extShapeErr(arg){
    throw new Error(`Extensions must be objects {}, received:${JSON.stringify(arg)}`);
  }
  function collectionErr(){throw new Error(`collection must be {} or []`);}
}

const walkerExtensions = {
  cycleChecker:{
    preWalk:(collection, collectionMeta)=>{
      collectionMeta._cycleChecker = new WeakSet();
    },
    onVisit:(node, walkModifiers, depth, {_cycleChecker})=>{
      if (_cycleChecker.has(node)){throw new Error('cycle error in packages');}
      _cycleChecker.add(node);
    },
    postWalk:(collection, collectionMeta)=>{
      delete collectionMeta._cycleChecker;
    },
  },
  topoSortAndDedupRelatedArrayInPlace:{
    // TBD: Making the name ugly since mutating related array is not ideal.
    // Need to think more on strategies to dedupe the recursive allRelated array that won't
    // break other extensions that depend on sort order or duplicate existence.
    // Maybe composeWalker users need to define a single onResolve function and compose the
    // extensions' onResolve fns manually.
    // Then each extension's lifecycle methods would need to return a value for consistency...
    // Hmm.  The value of moving on is greater than the value of fixing it for now.
    onResolve:(next, immediateRelated, walkModifiers, depth, allRelated, resolvedMap)=>{
      // given related nodes like A<CB & B<C, A's allRelated is [C,B,C], so uniq + sort to [B,C]
      if (allRelated.length <= 1){return;}
      let relA, relB;
      const sorted = Array.from(new Set(allRelated)).sort((a, b)=>{
        relA = resolvedMap.get(a);
        if (relA.length === 0){return 1;}
        if (relA.includes(b)){return -1;}
        relB = resolvedMap.get(b);
        if (relB.length === 0){return -1;}
        if (relB.includes(a)){return 1;}
        return 0;
      });
      allRelated.length = 0;
      allRelated.push(...sorted);
    }
  },
  defaults:{
    spreadNode:(node)=>[node],
    getResolved:(node, resolvedMap)=>resolvedMap.get(node),
    setResolved:(node, allRelated, resolvedMap)=>{resolvedMap.set(node, allRelated);},
    getWalkerFn(combinedExtensions, collectionMeta){
      let resolved = new WeakMap();
      const {
        getResolved, setResolved, getRelated, onVisit, onVisitRelated, afterVisitRelated, onResolve
      } = combinedExtensions;

      let stopWalk = false;
      let skipWalk = false;
      const walkModifiers = {
        stopWalkingImmediate(){stopWalk = true;},
        skipWalking(){skipWalk = true;},
        unSkipWalking(){skipWalk = false;},
        isWalkingSkipped(){return skipWalk;}
      };

      return function depthFirst(node, depth = 0){
        let allRelated = getResolved(node, resolved, collectionMeta);
        if (allRelated){return allRelated;}
        onVisit(node, walkModifiers, depth, collectionMeta);
        if (stopWalk === true){return allRelated;}
        allRelated = [];
        let j = -1;
        let immediateRelated = getRelated(node, collectionMeta) || [];
        let relatedLen = immediateRelated.length;
        let related, subRelated;
        while (++j < relatedLen){
          related = immediateRelated[j];
          onVisitRelated(node, related, walkModifiers, depth, collectionMeta);
          if (stopWalk === true){break;}
          if (skipWalk === true){continue;}
          allRelated.push(related);
          subRelated = depthFirst(related, depth + 1, collectionMeta);
          allRelated.push(...subRelated);
          afterVisitRelated(node, related, walkModifiers, subRelated, depth, collectionMeta);
        }
        onResolve(node, immediateRelated, walkModifiers, depth, allRelated, resolved, collectionMeta);
        setResolved(node, allRelated, resolved, collectionMeta);
        return allRelated;
      };
    }
  },
  breadthFirst:{
    // TBD - potentially remove.  Ended up not needing it for my use cases.
    getWalkerFn(combinedExtensions, collectionMeta){
      let resolved = new WeakMap();
      const {
        getResolved, setResolved, getRelated, onVisit, onVisitRelated, onResolve
      } = combinedExtensions;

      let stopWalk = false;
      let skipWalk = false;
      const walkModifiers = {
        stopWalkingImmediate(){stopWalk = true;},
        skipWalking(){skipWalk = true;},
        unSkipWalking(){skipWalk = false;}
      };

      return function breadthFirst(obj){
        let nextArray = [obj];
        let next;
        while ((next = nextArray.shift()) !== undefined){
          if (getResolved(next, resolved, collectionMeta)){continue;}
          onVisit(next, walkModifiers, collectionMeta);
          if (stopWalk === true){break;}
          if (skipWalk === true){continue;}
          let related;
          let relatedArray = getRelated(next, collectionMeta) || [];
          let relatedLen = relatedArray.length;
          let j = -1;
          while (++j < relatedLen){
            related = relatedArray[j];
            onVisitRelated(next, related, walkModifiers, collectionMeta);
            if (stopWalk === true){break;}
            if (skipWalk === true){continue;}
            nextArray.push(related);
          }
          onResolve(next, relatedArray, walkModifiers, collectionMeta);
          setResolved(next, relatedArray, resolved, collectionMeta);
        }
      };
    }
  },
};

module.exports = {composeWalker, walkerExtensions};





// refactor for improved functional structure and simplicity
// once - util for defaults
var once = (fn)=>{let result,called;return (...args)=>((called && result) || [called=true,result=fn(...args),result][2])};
function getDepthFirstWalker({
  afterVisitRelated=(node, related, subRelated, depth, cdata)=>{},
  isWalkingStopped=(node, related, depth, cdata)=>{},
  isWalkingSkipped=(node, related, depth, cdata)=>{},
  getCollectionMeta=once(()=>({adjacencyList:[]})),
  getRelated=(node, cdata)=>node.children,
  getResolved=(node, resolvedMap)=>resolvedMap.get(node),
  getResolvedContainer=once(()=>(new WeakMap())),
  onResolve=(node, adjacentNodes, depth, allRelated, resolved, cdata)=>{
    cdata.adjacencyList.push([node,adjacentNodes])
  },
  onVisit=(node, depth, cdata)=>{},
  onVisitRelated=(fromNode, relatedNode, depth, cdata)=>{},
  setResolved=(node, allRelated, resolvedMap)=>{resolvedMap.set(node, allRelated);},
}={}){
  const resolved = getResolvedContainer();
  const cdata = getCollectionMeta();
  return function depthFirst(node, depth = 0){
    let allRelated = getResolved(node, resolved, cdata);
    if (allRelated){return allRelated;}
    onVisit(node, depth, cdata);
    allRelated = [];
    let j = -1;
    let immediateRelated = getRelated(node, cdata) || [];
    let relatedLen = immediateRelated.length;
    let related, subRelated;
    while (++j < relatedLen){
      related = immediateRelated[j];
      onVisitRelated(node, related, depth, cdata);
      if (isWalkingStopped(node, related, depth, cdata)){break;}
      if (isWalkingSkipped(node, related, depth, cdata)){continue;}
      allRelated.push(related);
      subRelated = depthFirst(related, depth + 1, cdata);
      allRelated.push(...subRelated);
      afterVisitRelated(node, related, subRelated, depth, cdata);
    }
    onResolve(node, immediateRelated, depth, allRelated, resolved, cdata);
    setResolved(node, allRelated, resolved, cdata);
    return allRelated;
  };
}

function composeWalker({
  getCollectionMeta=once(()=>({adjacencyList:[]})),
  getWalkerFn=getDepthFirstWalker,
  preWalk=(collection,cdata)=>{},
  postWalk=(collection,cdata)=>{},
  spreadNode=(node)=>([node])
}={}){
  const lifecycleFns = {getCollectionMeta,getWalkerFn,preWalk,postWalk,spreadNode};
  const each = (o,fn)=>Array.isArray(o) ? o.forEach(fn) : Object.entries(o).forEach(([key,val])=>fn(key,val));
  const ensureArray = val=>Array.isArray(val)?val:[val];
  return function composedWalker(collection){
    const walkFn = getWalkerFn(lifecycleFns);
    preWalk(collection, getCollectionMeta());
    each(ensureArray(collection), (val, key)=>{
      spreadNode(val, key, getCollectionMeta()).forEach(walkFn);
    });
    postWalk(collection, getCollectionMeta());
    return getCollectionMeta();
  }
}
var data = [{
  name:'1',
  children:[
    {name:'1.1',children:[{name:'1.1.1'},{name:'1.1.2'}]},
    {name:'1.2',children:[{name:'1.2.1'},{name:'1.2.2'}]}
  ]
}]
var dataWalker = composeWalker();
var result = dataWalker(data);
result