repo_description: A reference implementation of GraphQL for JavaScript
repo_topics: graphql graphql-js
code: import { devAssert } from '../jsutils/devAssert';
  import { inspect } from '../jsutils/inspect';
  
  import type { ASTNode } from './ast';
  import { isNode, QueryDocumentKeys } from './ast';
  import { Kind } from './kinds';
  
  /**
   * A visitor is provided to visit, it contains the collection of
   * relevant functions to be called during the visitor's traversal.
   */
  export type ASTVisitor = EnterLeaveVisitor<ASTNode> | KindVisitor;
  
  type KindVisitor = {
    readonly [NodeT in ASTNode as NodeT['kind']]?:
      | ASTVisitFn<NodeT>
      | EnterLeaveVisitor<NodeT>;
  };
  
  interface EnterLeaveVisitor<TVisitedNode extends ASTNode> {
    readonly enter?: ASTVisitFn<TVisitedNode>;
    readonly leave?: ASTVisitFn<TVisitedNode>;
  }
  
  /**
   * A visitor is comprised of visit functions, which are called on each node
   * during the visitor's traversal.
   */
  export type ASTVisitFn<TVisitedNode extends ASTNode> = (
    /** The current node being visiting. */
    node: TVisitedNode,
    /** The index or key to this node from the parent node or Array. */
    key: string | number | undefined,
    /** The parent immediately above this node, which may be an Array. */
    parent: ASTNode | ReadonlyArray<ASTNode> | undefined,
    /** The key path to get to this node from the root node. */
    path: ReadonlyArray<string | number>,
    /**
     * All nodes and Arrays visited before reaching parent of this node.
     * These correspond to array indices in `path`.
     * Note: ancestors includes arrays which contain the parent of visited node.
     */
    ancestors: ReadonlyArray<ASTNode | ReadonlyArray<ASTNode>>,
  ) => any;
  
  /**
   * A reducer is comprised of reducer functions which convert AST nodes into
   * another form.
   */
  export type ASTReducer<R> = {
    readonly [NodeT in ASTNode as NodeT['kind']]?: {
      readonly enter?: ASTVisitFn<NodeT>;
      readonly leave: ASTReducerFn<NodeT, R>;
    };
  };
  
  type ASTReducerFn<TReducedNode extends ASTNode, R> = (
    /** The current node being visiting. */
    node: { [K in keyof TReducedNode]: ReducedField<TReducedNode[K], R> },
    /** The index or key to this node from the parent node or Array. */
    key: string | number | undefined,
    /** The parent immediately above this node, which may be an Array. */
    parent: ASTNode | ReadonlyArray<ASTNode> | undefined,
    /** The key path to get to this node from the root node. */
    path: ReadonlyArray<string | number>,
    /**
     * All nodes and Arrays visited before reaching parent of this node.
     * These correspond to array indices in `path`.
     * Note: ancestors includes arrays which contain the parent of visited node.
     */
    ancestors: ReadonlyArray<ASTNode | ReadonlyArray<ASTNode>>,
  ) => R;
  
  type ReducedField<T, R> = T extends null | undefined
    ? T
    : T extends ReadonlyArray<any>
    ? ReadonlyArray<R>
    : R;
  
  /**
   * A KeyMap describes each the traversable properties of each kind of node.
   *
   * @deprecated Please inline it. Will be removed in v17
   */
  export type ASTVisitorKeyMap = {
    [NodeT in ASTNode as NodeT['kind']]?: ReadonlyArray<keyof NodeT>;
  };
  
  export const BREAK: unknown = Object.freeze({});
  
  /**
   * visit() will walk through an AST using a depth-first traversal, calling
   * the visitor's enter function at each node in the traversal, and calling the
   * leave function after visiting that node and all of its child nodes.
   *
   * By returning different values from the enter and leave functions, the
   * behavior of the visitor can be altered, including skipping over a sub-tree of
   * the AST (by returning false), editing the AST by returning a value or null
   * to remove the value, or to stop the whole traversal by returning BREAK.
   *
   * When using visit() to edit an AST, the original AST will not be modified, and
   * a new version of the AST with the changes applied will be returned from the
   * visit function.
   *
   * ```ts
   * const editedAST = visit(ast, {
   *   enter(node, key, parent, path, ancestors) {
   *     // @return
   *     //   undefined: no action
   *     //   false: skip visiting this node
   *     //   visitor.BREAK: stop visiting altogether
   *     //   null: delete this node
   *     //   any value: replace this node with the returned value
   *   },
   *   leave(node, key, parent, path, ancestors) {
   *     // @return
   *     //   undefined: no action
   *     //   false: no action
   *     //   visitor.BREAK: stop visiting altogether
   *     //   null: delete this node
   *     //   any value: replace this node with the returned value
   *   }
   * });
   * ```
   *
   * Alternatively to providing enter() and leave() functions, a visitor can
   * instead provide functions named the same as the kinds of AST nodes, or
   * enter/leave visitors at a named key, leading to three permutations of the
   * visitor API:
   *
   * 1) Named visitors triggered when entering a node of a specific kind.
   *
   * ```ts
   * visit(ast, {
   *   Kind(node) {
   *     // enter the "Kind" node
   *   }
   * })
   * ```
   *
   * 2) Named visitors that trigger upon entering and leaving a node of a specific kind.
   *
   * ```ts
   * visit(ast, {
   *   Kind: {
   *     enter(node) {
   *       // enter the "Kind" node
   *     }
   *     leave(node) {
   *       // leave the "Kind" node
   *     }
   *   }
   * })
   * ```
   *
   * 3) Generic visitors that trigger upon entering and leaving any node.
   *
   * ```ts
   * visit(ast, {
   *   enter(node) {
   *     // enter any node
   *   },
   *   leave(node) {
   *     // leave any node
   *   }
   * })
   * ```
   */
  export function visit<N extends ASTNode>(
    root: N,
    visitor: ASTVisitor,
    visitorKeys?: ASTVisitorKeyMap,
  ): N;
  export function visit<R>(
    root: ASTNode,
    visitor: ASTReducer<R>,
    visitorKeys?: ASTVisitorKeyMap,
  ): R;
  export function visit(
    root: ASTNode,
    visitor: ASTVisitor | ASTReducer<any>,
    visitorKeys: ASTVisitorKeyMap = QueryDocumentKeys,
  ): any {
    const enterLeaveMap = new Map<Kind, EnterLeaveVisitor<ASTNode>>();
    for (const kind of Object.values(Kind)) {
      enterLeaveMap.set(kind, getEnterLeaveForKind(visitor, kind));
    }
  
    /* eslint-disable no-undef-init */
    let stack: any = undefined;
    let inArray = Array.isArray(root);
    let keys: any = [root];
    let index = -1;
    let edits = [];
    let node: any = root;
    let key: any = undefined;
    let parent: any = undefined;
    const path: any = [];
    const ancestors = [];
    /* eslint-enable no-undef-init */
  
    do {
      index++;
      const isLeaving = index === keys.length;
      const isEdited = isLeaving && edits.length !== 0;
      if (isLeaving) {
        key = ancestors.length === 0 ? undefined : path[path.length - 1];
        node = parent;
        parent = ancestors.pop();
        if (isEdited) {
          if (inArray) {
            node = node.slice();
  
            let editOffset = 0;
            for (const [editKey, editValue] of edits) {
              const arrayKey = editKey - editOffset;
              if (editValue === null) {
                node.splice(arrayKey, 1);
                editOffset++;
              } else {
                node[arrayKey] = editValue;
              }
            }
          } else {
            node = { ...node };
            for (const [editKey, editValue] of edits) {
              node[editKey] = editValue;
            }
          }
        }
        index = stack.index;
        keys = stack.keys;
        edits = stack.edits;
        inArray = stack.inArray;
        stack = stack.prev;
      } else if (parent) {
        key = inArray ? index : keys[index];
        node = parent[key];
        if (node === null || node === undefined) {
          continue;
        }
        path.push(key);
      }
  
      let result;
      if (!Array.isArray(node)) {
        devAssert(isNode(node), `Invalid AST Node: ${inspect(node)}.`);
  
        const visitFn = isLeaving
          ? enterLeaveMap.get(node.kind)?.leave
          : enterLeaveMap.get(node.kind)?.enter;
  
        result = visitFn?.call(visitor, node, key, parent, path, ancestors);
  
        if (result === BREAK) {
          break;
        }
  
        if (result === false) {
          if (!isLeaving) {
            path.pop();
            continue;
          }
        } else if (result !== undefined) {
          edits.push([key, result]);
          if (!isLeaving) {
            if (isNode(result)) {
              node = result;
            } else {
              path.pop();
              continue;
            }
          }
        }
      }
  
      if (result === undefined && isEdited) {
        edits.push([key, node]);
      }
  
      if (isLeaving) {
        path.pop();
      } else {
        stack = { inArray, index, keys, edits, prev: stack };
        inArray = Array.isArray(node);
        keys = inArray ? node : (visitorKeys as any)[node.kind] ?? [];
        index = -1;
        edits = [];
        if (parent) {
          ancestors.push(parent);
        }
        parent = node;
      }
    } while (stack !== undefined);
  
    if (edits.length !== 0) {
      // New root
      return edits[edits.length - 1][1];
    }
  
    return root;
  }
  
  /**
   * Creates a new visitor instance which delegates to many visitors to run in
   * parallel. Each visitor will be visited for each node before moving on.
   *
   * If a prior visitor edits a node, no following visitors will see that node.
   */
  export function visitInParallel(
    visitors: ReadonlyArray<ASTVisitor>,
  ): ASTVisitor {
    const skipping = new Array(visitors.length).fill(null);
    const mergedVisitor = Object.create(null);
  
    for (const kind of Object.values(Kind)) {
      let hasVisitor = false;
      const enterList = new Array(visitors.length).fill(undefined);
      const leaveList = new Array(visitors.length).fill(undefined);
  
      for (let i = 0; i < visitors.length; ++i) {
        const { enter, leave } = getEnterLeaveForKind(visitors[i], kind);
        hasVisitor ||= enter != null || leave != null;
        enterList[i] = enter;
        leaveList[i] = leave;
      }
  
      if (!hasVisitor) {
        continue;
      }
  
      const mergedEnterLeave: EnterLeaveVisitor<ASTNode> = {
        enter(...args) {
          const node = args[0];
          for (let i = 0; i < visitors.length; i++) {
            if (skipping[i] === null) {
              const result = enterList[i]?.apply(visitors[i], args);
              if (result === false) {
                skipping[i] = node;
              } else if (result === BREAK) {
                skipping[i] = BREAK;
              } else if (result !== undefined) {
                return result;
              }
            }
          }
        },
        leave(...args) {
          const node = args[0];
          for (let i = 0; i < visitors.length; i++) {
            if (skipping[i] === null) {
              const result = leaveList[i]?.apply(visitors[i], args);
              if (result === BREAK) {
                skipping[i] = BREAK;
              } else if (result !== undefined && result !== false) {
                return result;
              }
            } else if (skipping[i] === node) {
              skipping[i] = null;
            }
          }
        },
      };
  
      mergedVisitor[kind] = mergedEnterLeave;
    }
  
    return mergedVisitor;
  }
  
  /**
   * Given a visitor instance and a node kind, return EnterLeaveVisitor for that kind.
   */
  export function getEnterLeaveForKind(
    visitor: ASTVisitor,
    kind: Kind,
  ): EnterLeaveVisitor<ASTNode> {
    const kindVisitor:
      | ASTVisitFn<ASTNode>
      | EnterLeaveVisitor<ASTNode>
      | undefined = (visitor as any)[kind];
  
    if (typeof kindVisitor === 'object') {
      // { Kind: { enter() {}, leave() {} } }
      return kindVisitor;
    } else if (typeof kindVisitor === 'function') {
      // { Kind() {} }
      return { enter: kindVisitor, leave: undefined };
    }
  
    // { enter() {}, leave() {} }
    return { enter: (visitor as any).enter, leave: (visitor as any).leave };
  }
  
  /**
   * Given a visitor instance, if it is leaving or not, and a node kind, return
   * the function the visitor runtime should call.
   *
   * @deprecated Please use `getEnterLeaveForKind` instead. Will be removed in v17
   */
  /* c8 ignore next 8 */
  export function getVisitFn(
    visitor: ASTVisitor,
    kind: Kind,
    isLeaving: boolean,
  ): ASTVisitFn<ASTNode> | undefined {
    const { enter, leave } = getEnterLeaveForKind(visitor, kind);
    return isLeaving ? leave : enter;
  }
  