314 lines
9.4 KiB
JavaScript
314 lines
9.4 KiB
JavaScript
/**
|
||
* @typedef {import('unist').Node} UnistNode
|
||
* @typedef {import('unist').Parent} UnistParent
|
||
* @typedef {import('unist-util-visit-parents').VisitorResult} VisitorResult
|
||
*/
|
||
|
||
/**
|
||
* @typedef {Exclude<import('unist-util-is').Test, undefined> | undefined} Test
|
||
* Test from `unist-util-is`.
|
||
*
|
||
* Note: we have remove and add `undefined`, because otherwise when generating
|
||
* automatic `.d.ts` files, TS tries to flatten paths from a local perspective,
|
||
* which doesn’t work when publishing on npm.
|
||
*/
|
||
|
||
// To do: use types from `unist-util-visit-parents` when it’s released.
|
||
|
||
/**
|
||
* @typedef {(
|
||
* Fn extends (value: any) => value is infer Thing
|
||
* ? Thing
|
||
* : Fallback
|
||
* )} Predicate
|
||
* Get the value of a type guard `Fn`.
|
||
* @template Fn
|
||
* Value; typically function that is a type guard (such as `(x): x is Y`).
|
||
* @template Fallback
|
||
* Value to yield if `Fn` is not a type guard.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* Check extends null | undefined // No test.
|
||
* ? Value
|
||
* : Value extends {type: Check} // String (type) test.
|
||
* ? Value
|
||
* : Value extends Check // Partial test.
|
||
* ? Value
|
||
* : Check extends Function // Function test.
|
||
* ? Predicate<Check, Value> extends Value
|
||
* ? Predicate<Check, Value>
|
||
* : never
|
||
* : never // Some other test?
|
||
* )} MatchesOne
|
||
* Check whether a node matches a primitive check in the type system.
|
||
* @template Value
|
||
* Value; typically unist `Node`.
|
||
* @template Check
|
||
* Value; typically `unist-util-is`-compatible test, but not arrays.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* Check extends Array<any>
|
||
* ? MatchesOne<Value, Check[keyof Check]>
|
||
* : MatchesOne<Value, Check>
|
||
* )} Matches
|
||
* Check whether a node matches a check in the type system.
|
||
* @template Value
|
||
* Value; typically unist `Node`.
|
||
* @template Check
|
||
* Value; typically `unist-util-is`-compatible test.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10} Uint
|
||
* Number; capped reasonably.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {I extends 0 ? 1 : I extends 1 ? 2 : I extends 2 ? 3 : I extends 3 ? 4 : I extends 4 ? 5 : I extends 5 ? 6 : I extends 6 ? 7 : I extends 7 ? 8 : I extends 8 ? 9 : 10} Increment
|
||
* Increment a number in the type system.
|
||
* @template {Uint} [I=0]
|
||
* Index.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* Node extends UnistParent
|
||
* ? Node extends {children: Array<infer Children>}
|
||
* ? Child extends Children ? Node : never
|
||
* : never
|
||
* : never
|
||
* )} InternalParent
|
||
* Collect nodes that can be parents of `Child`.
|
||
* @template {UnistNode} Node
|
||
* All node types in a tree.
|
||
* @template {UnistNode} Child
|
||
* Node to search for.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {InternalParent<InclusiveDescendant<Tree>, Child>} Parent
|
||
* Collect nodes in `Tree` that can be parents of `Child`.
|
||
* @template {UnistNode} Tree
|
||
* All node types in a tree.
|
||
* @template {UnistNode} Child
|
||
* Node to search for.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* Depth extends Max
|
||
* ? never
|
||
* :
|
||
* | InternalParent<Node, Child>
|
||
* | InternalAncestor<Node, InternalParent<Node, Child>, Max, Increment<Depth>>
|
||
* )} InternalAncestor
|
||
* Collect nodes in `Tree` that can be ancestors of `Child`.
|
||
* @template {UnistNode} Node
|
||
* All node types in a tree.
|
||
* @template {UnistNode} Child
|
||
* Node to search for.
|
||
* @template {Uint} [Max=10]
|
||
* Max; searches up to this depth.
|
||
* @template {Uint} [Depth=0]
|
||
* Current depth.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* Tree extends UnistParent
|
||
* ? Depth extends Max
|
||
* ? Tree
|
||
* : Tree | InclusiveDescendant<Tree['children'][number], Max, Increment<Depth>>
|
||
* : Tree
|
||
* )} InclusiveDescendant
|
||
* Collect all (inclusive) descendants of `Tree`.
|
||
*
|
||
* > 👉 **Note**: for performance reasons, this seems to be the fastest way to
|
||
* > recurse without actually running into an infinite loop, which the
|
||
* > previous version did.
|
||
* >
|
||
* > Practically, a max of `2` is typically enough assuming a `Root` is
|
||
* > passed, but it doesn’t improve performance.
|
||
* > It gets higher with `List > ListItem > Table > TableRow > TableCell`.
|
||
* > Using up to `10` doesn’t hurt or help either.
|
||
* @template {UnistNode} Tree
|
||
* Tree type.
|
||
* @template {Uint} [Max=10]
|
||
* Max; searches up to this depth.
|
||
* @template {Uint} [Depth=0]
|
||
* Current depth.
|
||
*/
|
||
|
||
/**
|
||
* @callback Visitor
|
||
* Handle a node (matching `test`, if given).
|
||
*
|
||
* Visitors are free to transform `node`.
|
||
* They can also transform `parent`.
|
||
*
|
||
* Replacing `node` itself, if `SKIP` is not returned, still causes its
|
||
* descendants to be walked (which is a bug).
|
||
*
|
||
* When adding or removing previous siblings of `node` (or next siblings, in
|
||
* case of reverse), the `Visitor` should return a new `Index` to specify the
|
||
* sibling to traverse after `node` is traversed.
|
||
* Adding or removing next siblings of `node` (or previous siblings, in case
|
||
* of reverse) is handled as expected without needing to return a new `Index`.
|
||
*
|
||
* Removing the children property of `parent` still results in them being
|
||
* traversed.
|
||
* @param {Visited} node
|
||
* Found node.
|
||
* @param {Visited extends UnistNode ? number | undefined : never} index
|
||
* Index of `node` in `parent`.
|
||
* @param {Ancestor extends UnistParent ? Ancestor | undefined : never} parent
|
||
* Parent of `node`.
|
||
* @returns {VisitorResult}
|
||
* What to do next.
|
||
*
|
||
* An `Index` is treated as a tuple of `[CONTINUE, Index]`.
|
||
* An `Action` is treated as a tuple of `[Action]`.
|
||
*
|
||
* Passing a tuple back only makes sense if the `Action` is `SKIP`.
|
||
* When the `Action` is `EXIT`, that action can be returned.
|
||
* When the `Action` is `CONTINUE`, `Index` can be returned.
|
||
* @template {UnistNode} [Visited=UnistNode]
|
||
* Visited node type.
|
||
* @template {UnistParent} [Ancestor=UnistParent]
|
||
* Ancestor type.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {Visitor<Visited, Parent<Ancestor, Visited>>} BuildVisitorFromMatch
|
||
* Build a typed `Visitor` function from a node and all possible parents.
|
||
*
|
||
* It will infer which values are passed as `node` and which as `parent`.
|
||
* @template {UnistNode} Visited
|
||
* Node type.
|
||
* @template {UnistParent} Ancestor
|
||
* Parent type.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* BuildVisitorFromMatch<
|
||
* Matches<Descendant, Check>,
|
||
* Extract<Descendant, UnistParent>
|
||
* >
|
||
* )} BuildVisitorFromDescendants
|
||
* Build a typed `Visitor` function from a list of descendants and a test.
|
||
*
|
||
* It will infer which values are passed as `node` and which as `parent`.
|
||
* @template {UnistNode} Descendant
|
||
* Node type.
|
||
* @template {Test} Check
|
||
* Test type.
|
||
*/
|
||
|
||
/**
|
||
* @typedef {(
|
||
* BuildVisitorFromDescendants<
|
||
* InclusiveDescendant<Tree>,
|
||
* Check
|
||
* >
|
||
* )} BuildVisitor
|
||
* Build a typed `Visitor` function from a tree and a test.
|
||
*
|
||
* It will infer which values are passed as `node` and which as `parent`.
|
||
* @template {UnistNode} [Tree=UnistNode]
|
||
* Node type.
|
||
* @template {Test} [Check=Test]
|
||
* Test type.
|
||
*/
|
||
|
||
import {visitParents} from 'unist-util-visit-parents'
|
||
|
||
export {CONTINUE, EXIT, SKIP} from 'unist-util-visit-parents'
|
||
|
||
/**
|
||
* Visit nodes.
|
||
*
|
||
* This algorithm performs *depth-first* *tree traversal* in *preorder*
|
||
* (**NLR**) or if `reverse` is given, in *reverse preorder* (**NRL**).
|
||
*
|
||
* You can choose for which nodes `visitor` is called by passing a `test`.
|
||
* For complex tests, you should test yourself in `visitor`, as it will be
|
||
* faster and will have improved type information.
|
||
*
|
||
* Walking the tree is an intensive task.
|
||
* Make use of the return values of the visitor when possible.
|
||
* Instead of walking a tree multiple times, walk it once, use `unist-util-is`
|
||
* to check if a node matches, and then perform different operations.
|
||
*
|
||
* You can change the tree.
|
||
* See `Visitor` for more info.
|
||
*
|
||
* @overload
|
||
* @param {Tree} tree
|
||
* @param {Check} check
|
||
* @param {BuildVisitor<Tree, Check>} visitor
|
||
* @param {boolean | null | undefined} [reverse]
|
||
* @returns {undefined}
|
||
*
|
||
* @overload
|
||
* @param {Tree} tree
|
||
* @param {BuildVisitor<Tree>} visitor
|
||
* @param {boolean | null | undefined} [reverse]
|
||
* @returns {undefined}
|
||
*
|
||
* @param {UnistNode} tree
|
||
* Tree to traverse.
|
||
* @param {Visitor | Test} testOrVisitor
|
||
* `unist-util-is`-compatible test (optional, omit to pass a visitor).
|
||
* @param {Visitor | boolean | null | undefined} [visitorOrReverse]
|
||
* Handle each node (when test is omitted, pass `reverse`).
|
||
* @param {boolean | null | undefined} [maybeReverse=false]
|
||
* Traverse in reverse preorder (NRL) instead of the default preorder (NLR).
|
||
* @returns {undefined}
|
||
* Nothing.
|
||
*
|
||
* @template {UnistNode} Tree
|
||
* Node type.
|
||
* @template {Test} Check
|
||
* `unist-util-is`-compatible test.
|
||
*/
|
||
export function visit(tree, testOrVisitor, visitorOrReverse, maybeReverse) {
|
||
/** @type {boolean | null | undefined} */
|
||
let reverse
|
||
/** @type {Test} */
|
||
let test
|
||
/** @type {Visitor} */
|
||
let visitor
|
||
|
||
if (
|
||
typeof testOrVisitor === 'function' &&
|
||
typeof visitorOrReverse !== 'function'
|
||
) {
|
||
test = undefined
|
||
visitor = testOrVisitor
|
||
reverse = visitorOrReverse
|
||
} else {
|
||
// @ts-expect-error: assume the overload with test was given.
|
||
test = testOrVisitor
|
||
// @ts-expect-error: assume the overload with test was given.
|
||
visitor = visitorOrReverse
|
||
reverse = maybeReverse
|
||
}
|
||
|
||
visitParents(tree, test, overload, reverse)
|
||
|
||
/**
|
||
* @param {UnistNode} node
|
||
* @param {Array<UnistParent>} parents
|
||
*/
|
||
function overload(node, parents) {
|
||
const parent = parents[parents.length - 1]
|
||
const index = parent ? parent.children.indexOf(node) : undefined
|
||
return visitor(node, index, parent)
|
||
}
|
||
}
|