1// Perform a breadth-first walk of a tree, either logical or physical 2// This one only visits, it doesn't leave. That's because 3// in a breadth-first traversal, children may be visited long 4// after their parent, so the "exit" pass ends up being just 5// another breadth-first walk. 6// 7// Breadth-first traversals are good for either creating a tree (ie, 8// reifying a dep graph based on a package.json without a node_modules 9// or package-lock), or mutating it in-place. For a map-reduce type of 10// walk, it doesn't make a lot of sense, and is very expensive. 11const breadth = ({ 12 visit, 13 filter = () => true, 14 getChildren, 15 tree, 16}) => { 17 const queue = [] 18 const seen = new Map() 19 20 const next = () => { 21 while (queue.length) { 22 const node = queue.shift() 23 const res = visitNode(node) 24 if (isPromise(res)) { 25 return res.then(() => next()) 26 } 27 } 28 return seen.get(tree) 29 } 30 31 const visitNode = (visitTree) => { 32 if (seen.has(visitTree)) { 33 return seen.get(visitTree) 34 } 35 36 seen.set(visitTree, null) 37 const res = visit ? visit(visitTree) : visitTree 38 if (isPromise(res)) { 39 const fullResult = res.then(resThen => { 40 seen.set(visitTree, resThen) 41 return kidNodes(visitTree) 42 }) 43 seen.set(visitTree, fullResult) 44 return fullResult 45 } else { 46 seen.set(visitTree, res) 47 return kidNodes(visitTree) 48 } 49 } 50 51 const kidNodes = (kidTree) => { 52 const kids = getChildren(kidTree, seen.get(kidTree)) 53 return isPromise(kids) ? kids.then(processKids) : processKids(kids) 54 } 55 56 const processKids = (kids) => { 57 kids = (kids || []).filter(filter) 58 queue.push(...kids) 59 } 60 61 queue.push(tree) 62 return next() 63} 64 65const isPromise = p => p && typeof p.then === 'function' 66 67module.exports = breadth 68