treeIterator.js

//@flow
export type Tree = {
  /*::+*/ id: ID,
  /*::+*/ kind: 'tree',
  /*::+*/ refs: Array<Tree>,
  /*::+*/ head: Array<StepValue>,
  /*::+*/ tail: Array<Tree>,
  /*::+*/ config: {
    runInBand: boolean,
  },
}

export function iterateTree(treeRaw: Tree, firstCtx, fn) {
  let releasePoint = stack(
    {
      tree: treeRaw,
      innerWalk: {
        need: treeRaw.head.length > 0,
        index: 0,
      },
      childWalk: {
        need: treeRaw.tail.length > 0,
        index: 0,
      },
      breadcrumbs: {
        ctx: stack(firstCtx, {depth: 0, value: null, parent: null}),
        done: false,
      },
    },
    {depth: 0, value: null, parent: null},
  )
  let returnInfo = {
    fastExit: false,
  }
  do {
    fastExit: {
      noFastExit: {
        const layer = releasePoint.value
        const breadcrumbs = layer.breadcrumbs
        const tree = layer.tree
        if (returnInfo.fastExit) {
          if (tree.config.runInBand) {
            break noFastExit
          } else {
            returnInfo = {
              fastExit: false,
            }
          }
        }
        innerWalk: {
          const innerWalk = layer.innerWalk
          if (!innerWalk.need) break innerWalk
          for (; innerWalk.index < tree.head.length; innerWalk.index++) {
            const data = tree.head[innerWalk.index]
            fn(data, breadcrumbs)
            if (breadcrumbs.done) break noFastExit
          }
          innerWalk.need = false
        }
        childWalk: {
          const childWalk = layer.childWalk
          if (!childWalk.need) break childWalk
          if (childWalk.index >= tree.tail.length) {
            childWalk.need = false
            break childWalk
          }
          const childTree = tree.tail[childWalk.index]
          const newReleasePoint = {
            tree: childTree,
            innerWalk: {
              need: childTree.head.length > 0,
              index: 0,
            },
            childWalk: {
              need: childTree.tail.length > 0,
              index: 0,
            },
            breadcrumbs: {
              ctx: stack(breadcrumbs.ctx.value, breadcrumbs.ctx),
              done: false,
            },
          }
          releasePoint = stack(newReleasePoint, releasePoint)
          childWalk.index += 1
          continue
        }
        returnInfo = {
          fastExit: false,
        }
        break fastExit
      }
      returnInfo = {
        fastExit: true,
      }
    }
    releasePoint = releasePoint.parent
  } while (releasePoint.depth)
}

function stack<T>(value: T, parent: {depth: number, ...}): Stack<T> {
  return {
    depth: parent.depth + 1,
    value,
    parent,
  }
}


type Stack<T = mixed> = {
  depth: number,
  value: T,
  parent: Stack<T>,
}

export function iterateStack<T>(
  stack: Stack<T>,
  fn: (value: T, depth: number) => any,
) {
  while (stack.depth) {
    fn(stack.value, stack.depth)
    stack = stack.parent
  }
}