1// Perform a depth-first walk of a tree, ONLY doing the descent (visit) 2// 3// This uses a stack rather than recursion, so that it can handle deeply 4// nested trees without call stack overflows. (My kingdom for proper TCO!) 5// 6// This is only used for cases where leave() is not specified. 7// 8// a 9// +-- b 10// | +-- 1 11// | +-- 2 12// +-- c 13// +-- 3 14// +-- 4 15// 16// Expect: 17// visit a 18// visit b 19// visit 1 20// visit 2 21// visit c 22// visit 3 23// visit 4 24// 25// stack.push(tree) 26// while stack not empty 27// pop T from stack 28// VISIT(T) 29// get children C of T 30// push each C onto stack 31 32const depth = ({ 33 visit, 34 filter, 35 getChildren, 36 tree, 37}) => { 38 const stack = [] 39 const seen = new Map() 40 41 const next = () => { 42 while (stack.length) { 43 const node = stack.pop() 44 const res = visitNode(node) 45 if (isPromise(res)) { 46 return res.then(() => next()) 47 } 48 } 49 return seen.get(tree) 50 } 51 52 const visitNode = (visitTree) => { 53 if (seen.has(visitTree)) { 54 return seen.get(visitTree) 55 } 56 57 seen.set(visitTree, null) 58 const res = visit ? visit(visitTree) : visitTree 59 if (isPromise(res)) { 60 const fullResult = res.then(resThen => { 61 seen.set(visitTree, resThen) 62 return kidNodes(visitTree) 63 }) 64 seen.set(visitTree, fullResult) 65 return fullResult 66 } else { 67 seen.set(visitTree, res) 68 return kidNodes(visitTree) 69 } 70 } 71 72 const kidNodes = (kidTree) => { 73 const kids = getChildren(kidTree, seen.get(kidTree)) 74 return isPromise(kids) ? kids.then(processKids) : processKids(kids) 75 } 76 77 const processKids = (kids) => { 78 kids = (kids || []).filter(filter) 79 stack.push(...kids) 80 } 81 82 stack.push(tree) 83 return next() 84} 85 86const isPromise = p => p && typeof p.then === 'function' 87 88module.exports = depth 89