import {
  assert,
  Field,
  FragmentElement,
  InterfaceType,
  NamedType,
  OperationElement,
  Schema,
  SchemaRootKind,
  SelectionSet,
  typenameFieldName,
  isLeafType,
  baseType,
  CompositeType,
  isAbstractType,
  newDebugLogger,
  isCompositeType,
  parseFieldSetArgument,
  possibleRuntimeTypes,
  ObjectType,
  isObjectType,
  mapValues,
  federationMetadata,
  isSchemaRootType,
  Directive,
  FieldDefinition,
  printSubgraphNames,
  allFieldDefinitionsInSelectionSet,
  DeferDirectiveArgs,
  isInterfaceType,
  isSubset,
  parseSelectionSet,
  Variable,
  Type,
  isScalarType,
  isEnumType,
  isUnionType,
  Selection,
} from "@apollo/federation-internals";
import { OpPathTree, traversePathTree } from "./pathTree";
import { Vertex, QueryGraph, Edge, RootVertex, isRootVertex, isFederatedGraphRootType, FEDERATED_GRAPH_ROOT_SOURCE } from "./querygraph";
import { DownCast, Transition } from "./transition";
import { PathContext, emptyContext, isPathContext } from "./pathContext";
import { v4 as uuidv4 } from 'uuid';

const debug = newDebugLogger('path');

export type ContextAtUsageEntry = { 
  contextId: string, 
  relativePath: string[],
  selectionSet: SelectionSet,
  subgraphArgType: Type,
};

function updateRuntimeTypes(currentRuntimeTypes: readonly ObjectType[], edge: Edge | null): readonly ObjectType[] {
  if (!edge) {
    return currentRuntimeTypes;
  }

  switch (edge.transition.kind) {
    case 'FieldCollection':
      const field = edge.transition.definition;
      if (!isCompositeType(baseType(field.type!))) {
        return [];
      }
      const newRuntimeTypes: ObjectType[] = [];
      for (const parentType of currentRuntimeTypes) {
        const fieldType = parentType.field(field.name)?.type;
        if (fieldType) {
          for (const type of possibleRuntimeTypes(baseType(fieldType) as CompositeType)) {
            if (!newRuntimeTypes.includes(type)) {
              newRuntimeTypes.push(type);
            }
          }
        }
      }
      return newRuntimeTypes;
    case 'DownCast':
      const castedType = edge.transition.castedType;
      const castedRuntimeTypes = possibleRuntimeTypes(castedType);
      return currentRuntimeTypes.filter(t => castedRuntimeTypes.includes(t));
    case 'InterfaceObjectFakeDownCast':
      return currentRuntimeTypes;
    case 'KeyResolution':
      const currentType = edge.tail.type as CompositeType;
      // We've taken a key into a new subgraph, so any of the possible runtime types of the new subgraph could be returned.
      return possibleRuntimeTypes(currentType);
    case 'RootTypeResolution':
    case 'SubgraphEnteringTransition':
      assert(isObjectType(edge.tail.type), () => `Query edge should be between object type but got ${edge}`);
      return [ edge.tail.type ];
  }
}

function withReplacedLastElement<T>(arr: readonly T[], newLast: T): T[] {
  assert(arr.length > 0, 'Should not have been called on empty array');
  const newArr = new Array<T>(arr.length);
  for (let i = 0; i < arr.length - 1; i++) {
    newArr[i] = arr[i];
  }
  newArr[arr.length - 1] = newLast;
  return newArr;
}

/**
 * An immutable path in a query graph.
 *
 * Path is mostly understood in the graph theoretical sense of the term, that is as "a connected series of edges"
 * and a `GraphPath` is generated by traversing a graph query.
 * However, as query graph edges may have conditions, a `GraphPath` also records, for reach edges it is composed of,
 * the set of paths (an `OpPathTree` in practice) that were taken to fulfill the edge conditions (when the edge has
 * one).
 *
 * Additionally, for each edge of the path, a `GraphPath` records the "trigger" that made the traversal take that
 * edge. In practice, the "trigger" can be seen as a way to decorate a path with some additional metadata for each
 * elements of the path. In practice, that trigger is used in 2 main ways (corresponding to our 2 main query graph
 * traversals):
 *  - for composition validation, the traversal of the federated query graph is driven by other transitions into the
 *    supergraph API query graphs (essentially, composition validation is about finding, for every supergraph API
 *    query graph path, a "matching" traversal of the federated query graph). In that case, for the graph paths
 *    we build on the federated query graph, the "trigger" will be one of the `Transition` from the supergraph
 *    API graph (which, granted, will be fairly similar to the one of the edge we're taking in the federated query
 *    graph; in practice, triggers are more useful in the query planning case).
 *  - for query planning, the traversal of the federated query graph is driven by the elements of the query we are
 *    planning. Which means that the "trigger" for taking an edge in this case will be an `OperationElement`
 *    (or null). See the specialized `OpGraphPath` that is defined for this use case.
 *
 * Lastly, some `GraphPath` can actually encode "null" edges: this is used during query planning in the (rare)
 * case where the query we plan for has fragment spread without type condition (or a "useless" one, on that doesn't
 * restrict the possible types anymore than they already were) but with some directives. In that case, we want
 * to preserve the information about the directive (to properly rebuild query plans later) but it doesn't correspond
 * to taking any edges, so we add a "null" edge and use the trigger to store the fragment spread.
 *
 * @param TTrigger - the type of the paths "triggers", metadata that can associated to each element of the path (see
 *   above for more details).
 * @param RV - the type of the vertex starting the path. This simply default to `Vertex` but is used in `RootPath`/`OpRootPath`
 *   to easily distinguish those paths that starts from a root of a query graph.
 * @param TNullEdge - typing information to indicate whether the path can have "null" edges or not. Either `null` (
 *   meaning that the path may have null edges) or `never` (the path cannot have null edges).
 */
type PathProps<TTrigger, RV extends Vertex = Vertex, TNullEdge extends null | never = never> = {
  /** The query graph of which this is a path. */
  readonly graph: QueryGraph,
  /** The vertex at which the path starts (the head vertex of the first edge in path, aliased here for convenience). */
  readonly root: RV,
  /** The vertex at which the path stops (the tail vertex of the last edge in path, aliased here for convenience). */
  readonly tail: Vertex,
  /** The triggers associated to each edges in the paths (see `GraphPath` for more details on triggers). */
  readonly edgeTriggers: readonly TTrigger[],
  /** The edges (stored by edge index) composing the path. */
  readonly edgeIndexes: readonly (number | TNullEdge)[],
  /**
  * For each edge in the path, if the edge has conditions, the set of paths that fulfill that condition.
  * Note that no matter which kind of traversal we are doing, fulfilling the conditions is always driven by
  * the conditions themselves, and as conditions are a graphQL result set, the resulting set of paths are
  * `OpGraphPath` (and as they are all rooted at the edge head vertex, we use the `OpPathTree` representation
    * for that set of paths).
  */
  readonly edgeConditions: readonly (OpPathTree | null)[],

  readonly subgraphEnteringEdge?: {
    index: number,
    edge: Edge,
    cost: number,
  },

  readonly ownPathIds: readonly string[],
  readonly overriddingPathIds: readonly string[],

  readonly edgeToTail?: Edge | TNullEdge,
  /** Names of the all the possible runtime types the tail of the path can be. */
  readonly runtimeTypesOfTail: readonly ObjectType[],
  /** If the last edge (the one getting to tail) was a DownCast, the runtime types before that edge. */
  readonly runtimeTypesBeforeTailIfLastIsCast?: readonly ObjectType[],

  readonly deferOnTail?: DeferDirectiveArgs,
  
  /** We may have a map of selections that get mapped to a context */
  readonly contextToSelection: readonly (Set<string> | null)[],
  
  /** This parameter is for mapping contexts back to the parameter used to collect the field */
  readonly parameterToContext: readonly (Map<string, ContextAtUsageEntry> | null)[],
}

export class GraphPath<TTrigger, RV extends Vertex = Vertex, TNullEdge extends null | never = never> implements Iterable<[Edge | TNullEdge, TTrigger, OpPathTree | null, Set<string> | null, Map<string, ContextAtUsageEntry> | null]> {
  private constructor(
    private readonly props: PathProps<TTrigger, RV, TNullEdge>,
  ) {
  }

  get graph(): QueryGraph {
    return this.props.graph;
  }

  get root(): RV {
    return this.props.root;
  }

  get tail(): Vertex {
    return this.props.tail;
  }

  get deferOnTail(): DeferDirectiveArgs | undefined {
    return this.props.deferOnTail;
  }

  get subgraphEnteringEdge(): { index: number, edge: Edge, cost: number } | undefined {
    return this.props.subgraphEnteringEdge;
  }

  /**
   * Creates a new (empty) path starting at the provided vertex.
   */
  static create<TTrigger, RV extends Vertex = Vertex, TNullEdge extends null | never = never>(
    graph: QueryGraph,
    root: RV
  ): GraphPath<TTrigger, RV, TNullEdge> {
    // If 'graph' is a federated query graph, federation renames all root type to their default names, so we rely on this here.
    const runtimeTypes = isFederatedGraphRootType(root.type) ? [] : possibleRuntimeTypes(root.type as CompositeType);
    return new GraphPath({
      graph,
      root,
      tail: root,
      edgeTriggers: [],
      edgeIndexes: [],
      edgeConditions: [],
      ownPathIds: [],
      overriddingPathIds: [],
      runtimeTypesOfTail: runtimeTypes,
      contextToSelection: [],
      parameterToContext: [],
    });
  }

  /**
   * Creates a new (empty) path starting from the root vertex in `graph` corresponding to the provide `rootKind`.
   */
  static fromGraphRoot<TTrigger, TNullEdge extends null | never = never>(
    graph: QueryGraph,
    rootKind: SchemaRootKind
  ): RootPath<TTrigger, TNullEdge> | undefined {
    const root = graph.root(rootKind);
    return root ? this.create(graph, root) : undefined;
  }

  /**
   * The size of the path, that is the number of edges composing it.
   *
   * Note that this only the "main" edges composing the path: some of those edges may have conditions for which the
   * path will also store the "sub-paths" necessary to fulfill said conditions, but the edges of those sub-paths are
   * _not_ counted here.
   */
  get size(): number {
    return this.props.edgeIndexes.length;
  }

  /**
   * That method first look for the biggest common prefix to `this` and `that` (assuming that both path are build as choices
   * of the same "query path"), and the count how many subgraph jumps each of the path has after said prefix.
   *
   * Note that this method always returns something but the biggest common prefix considered might well be empty.
   *
   * Please note that this method assumes that the 2 paths have the same root, and will fail if that's not the case.
   */
  countSubgraphJumpsAfterLastCommonVertex(that: GraphPath<TTrigger, RV, TNullEdge>): {
    thisJumps: number,
    thatJumps: number
  } {
    const { vertex, index } = this.findLastCommonVertex(that);
    return {
      thisJumps: this.subgraphJumpsAtIdx(vertex, index),
      thatJumps: that.subgraphJumpsAtIdx(vertex, index),
    };
  }

  private findLastCommonVertex(that: GraphPath<TTrigger, RV, TNullEdge>): { vertex: Vertex, index: number } {
    let vertex: Vertex = this.root;
    assert(that.root === vertex, () => `Expected both path to start on the same root, but 'this' has root ${vertex} while 'that' has ${that.root}`);

    const minSize = Math.min(this.size, that.size);
    let index = 0;
    for (; index < minSize; index++) {
      const thisEdge = this.edgeAt(index, vertex);
      const thatEdge = that.edgeAt(index, vertex);
      if (thisEdge !== thatEdge) {
        break;
      }
      if (thisEdge) {
        vertex = thisEdge.tail;
      }
    }
    return { vertex, index};
  }

  private subgraphJumpsAtIdx(vertex: Vertex, index: number): number {
    let jumps = 0;
    let v: Vertex = vertex;
    for (let i = index; i < this.size; i++) {
      const edge = this.edgeAt(i, v);
      if (!edge) {
        continue;
      }
      if (edge.changesSubgraph()) {
        ++jumps;
      }
      v = edge.tail;
    }
    return jumps;
  }

  subgraphJumps(): number {
    return this.subgraphJumpsAtIdx(this.root, 0);
  }

  isEquivalentSaveForTypeExplosionTo(that: GraphPath<TTrigger, RV, TNullEdge>): boolean {
    // We're looking a the specific case were both path are basically equivalent except
    // for a single step of type-explosion, so if either the paths don't start and end in the
    // same vertex, or if `other` is not exactly 1 more step than `this`, we're done.
    if (this.root !== that.root || this.tail !== that.tail || this.size !== that.size - 1) {
      return false;
    }

    // If that's true, then we get to our comparison.
    let thisV: Vertex = this.root;
    let thatV: Vertex = that.root;
    for (let i = 0; i < this.size; i++) {
      let thisEdge = this.edgeAt(i, thisV);
      let thatEdge = that.edgeAt(i, thatV);
      if (thisEdge !== thatEdge) {
        // First difference. If it's not a "type-explosion", that is `that` is a cast from an
        // interface to one of the implementation, then we're not in the case we're looking for.
        if (!thisEdge || !thatEdge || !isInterfaceType(thatV.type) || thatEdge.transition.kind !== 'DownCast') {
          return false;
        }
        thatEdge = that.edgeAt(i+1, thatEdge.tail);
        if (!thatEdge) {
          return false;
        }
        thisV = thisEdge.tail;
        thatV = thatEdge.tail;

        // At that point, we want both path to take the "same" key, but because one is starting
        // from the interface while the other one from an implementation, they won't be technically
        // the "same" edge object. So we check that both are key, to the same subgraph and type,
        // and with the same condition.
        if (thisEdge.transition.kind !== 'KeyResolution'
          || thatEdge.transition.kind !== 'KeyResolution'
          || thisEdge.tail.source !== thatEdge.tail.source
          || thisV !== thatV
          || !thisEdge.conditions!.equals(thatEdge.conditions!)
        ) {
          return false;
        }

        // So far, so good. `thisV` and `thatV` are positioned on the vertex after which the path
        // must be equal again. So check that it's true, and if it is, we're good.
        // Note that for `this`, the last edge we looked at was `i`, so the next is `i+1`. And
        // for `that`, we've skipped over one more edge, so need to use `j+1`.
        for (let j = i + 1; j < this.size; j++) {
          thisEdge = this.edgeAt(j, thisV);
          thatEdge = that.edgeAt(j+1, thatV);
          if (thisEdge !== thatEdge) {
            return false;
          }
          if (thisEdge) {
            thisV = thisEdge.tail;
            thatV = thatEdge!.tail;
          }
        }
        return true;
      }
      if (thisEdge) {
        thisV = thisEdge.tail;
        thatV = thatEdge!.tail;
      }
    }
    // If we get here, both path are actually exactly the same. So technically there is not additional
    // type explosion, but they are equivalent and we can return `true`.
    return true;
  }

  [Symbol.iterator](): PathIterator<TTrigger, TNullEdge> {
    const path = this;
    return {
      currentIndex: 0,
      currentVertex: this.root,
      next(): IteratorResult<[Edge | TNullEdge, TTrigger, OpPathTree | null, Set<string> | null, Map<string, ContextAtUsageEntry> | null]> {
        if (this.currentIndex >= path.size) {
          return { done: true, value: undefined };
        }
        const idx = this.currentIndex++;
        const edge = path.edgeAt(idx, this.currentVertex);
        if (edge) {
          this.currentVertex = edge.tail;
        }
        return { done: false, value: [
          edge, 
          path.props.edgeTriggers[idx],
          path.props.edgeConditions[idx],
          path.props.contextToSelection[idx],
          path.props.parameterToContext[idx],
        ] };
      }
    };
  }

  /**
   * The last edge in the path (if it isn't empty).
   */
  lastEdge(): Edge | TNullEdge | undefined {
    return this.props.edgeToTail;
  }

  lastTrigger(): TTrigger | undefined {
    return this.props.edgeTriggers[this.size - 1];
  }

  /** The possible runtime types the tail of the path can be (this is deduplicated). */
  tailPossibleRuntimeTypes(): readonly ObjectType[] {
    return this.props.runtimeTypesOfTail;
  }

  /**
   * Returns `true` if the last edge of the path correspond to an @interfaceObject "fake cast" while the the previous edge was an edge that "entered" the subgraph (a key edge from another subgraph).
   */
  lastIsIntefaceObjectFakeDownCastAfterEnteringSubgraph(): boolean {
    return this.lastIsInterfaceObjectFakeDownCast()
      && this.subgraphEnteringEdge?.index === this.size - 2; // size - 1 is the last index (the fake cast), so size - 2 is the previous edge.
  }

  private lastIsInterfaceObjectFakeDownCast(): boolean {
    return this.lastEdge()?.transition.kind === 'InterfaceObjectFakeDownCast';
  }

  /**
   * Creates the new path corresponding to appending to this path the provided `edge`.
   *
   * @param trigger - the trigger for taking the edge in the created path.
   * @param edge - the edge to add (which may be 'null' if this type of path allows it, but if it isn't should be an out-edge
   *   for `s.tail`).
   * @param conditionsResolution - the result of resolving the conditions for this edge.
   * @param defer - if the trigger is an operation with a @defer on it, the arguments of this @defer.
   * @returns the newly created path.
   */
  add(trigger: TTrigger, edge: Edge | TNullEdge, conditionsResolution: ConditionResolution, defer?: DeferDirectiveArgs): GraphPath<TTrigger, RV, TNullEdge> {
    assert(!edge || this.tail.index === edge.head.index, () => `Cannot add edge ${edge} to path ending at ${this.tail}`);
    assert(conditionsResolution.satisfied, 'Should add to a path if the conditions cannot be satisfied');
    assert(!edge || edge.conditions || edge.requiredContexts.length > 0 || !conditionsResolution.pathTree, () => `Shouldn't have conditions paths (got ${conditionsResolution.pathTree}) for edge without conditions (edge: ${edge})`);

    // We clear `subgraphEnteringEdge` as we enter a @defer: that is because `subgraphEnteringEdge` is used to eliminate some
    // non-optimal paths, but we don't want those optimizations to bypass a defer.
    let subgraphEnteringEdge = defer ? undefined : this.subgraphEnteringEdge;

    if (edge) {
      if (edge.transition.kind === 'DownCast' && this.props.edgeToTail) {
        const previousOperation = this.lastTrigger();
        if (previousOperation instanceof FragmentElement && previousOperation.appliedDirectives.length === 0) {
          // This mean we have 2 type-cast back-to-back and that means the previous operation might not be
          // useful on this path. More precisely, the previous type-cast was only useful if it restricted
          // the possible runtime types of the type on which it applied more than the current type-cast
          // does (but note that if the previous type-cast had directives, we keep it no matter what in
          // case those directives are important).
          // That is, we're in the case where we have (somewhere potentially deep in a query):
          //   f {  # field 'f' of type A
          //     ... on B {
          //       ... on C {
          //          # more stuffs
          //       }
          //     }
          //   }
          // If the intersection of A and C is non empty and included (or equal) to the intersection of A and B,
          // then there is no reason to have `... on B` at all because:
          //  1. you can do `... on C` on `f` directly since the intersection of A and C is non-empty.
          //  2. `... on C` restricts strictly more than `... on B` and so the latter can't impact the result.
          // So if we detect that we're in that situation, we remove the `... on B` (but note that this is an
          // optimization, keeping `... on B` wouldn't be incorrect, just useless).
          const runtimeTypesWithoutPreviousCast = updateRuntimeTypes(this.props.runtimeTypesBeforeTailIfLastIsCast!, edge);
          if (runtimeTypesWithoutPreviousCast.length > 0
            && runtimeTypesWithoutPreviousCast.every(t => this.props.runtimeTypesOfTail.includes(t))
          ) {
            // Note that edge is from the vertex we've eliminating from the path. So we need to get the edge goes
            // directly from the prior vertex to the new tail for that path.
            const updatedEdge = this.graph.outEdges(this.props.edgeToTail!.head).find(e => e.tail.type === edge.tail.type);
            if (updatedEdge) {
              // We replace the previous operation by the new one.
              debug.log(() => `Previous cast ${previousOperation} is made obsolete by new cast ${trigger}, removing from path.`);
              return new GraphPath({
                ...this.props,
                tail: updatedEdge.tail,
                edgeTriggers: withReplacedLastElement(this.props.edgeTriggers, trigger),
                edgeIndexes: withReplacedLastElement(this.props.edgeIndexes, updatedEdge.index),
                edgeConditions: withReplacedLastElement(this.props.edgeConditions, conditionsResolution.pathTree ?? null),
                edgeToTail: updatedEdge,
                runtimeTypesOfTail: runtimeTypesWithoutPreviousCast,
                // We know the edge is a DownCast, so if there is no new `defer` taking precedence, we just inherit the
                // prior version.
                deferOnTail: defer ?? this.props.deferOnTail,
              });
            }
          }
        }
      }

      // Again, we don't want to set `subgraphEnteringEdge` if we're entering a @defer (see above).
      if (!defer && edge.changesSubgraph()) {
        subgraphEnteringEdge = {
          index: this.size,
          edge,
          cost: conditionsResolution.cost,
        };
      }

      if (edge.transition.kind === 'KeyResolution') {
        // We're adding a key edge. If the last edge to that point is an @interfaceObject fake downcast, and if our destination
        // type is not an @interfaceObject itself, then we can eliminate that last edge as it does nothing useful, but also,
        // it has conditions and we don't need/want the key we're following to depend on those conditions, since it doesn't have
        // to.
        if (this.lastIsInterfaceObjectFakeDownCast() && isInterfaceType(edge.tail.type)) {
          return new GraphPath({
            ...this.props,
            tail: edge.tail,
            edgeTriggers: withReplacedLastElement(this.props.edgeTriggers, trigger),
            edgeIndexes: withReplacedLastElement(this.props.edgeIndexes, edge.index),
            edgeConditions: withReplacedLastElement(this.props.edgeConditions, conditionsResolution.pathTree ?? null),
            subgraphEnteringEdge,
            edgeToTail: edge,
            runtimeTypesOfTail: updateRuntimeTypes(this.props.runtimeTypesOfTail, edge),
            runtimeTypesBeforeTailIfLastIsCast: undefined, // we know last is not a cast
            deferOnTail: defer,
          });
        }
      }
    }
    
    const { edgeConditions, contextToSelection, parameterToContext } = this.mergeEdgeConditionsWithResolution(conditionsResolution);
    const lastParameterToContext = parameterToContext[parameterToContext.length-1];
    let newTrigger = trigger;
    if (lastParameterToContext !== null && (trigger as any).kind === 'Field') {
      // If this is the last edge that reaches a contextual element, we should update the trigger to use the contextual arguments
      const args = Array.from(lastParameterToContext).reduce((acc: {[key: string]: any}, [key, value]: [string, ContextAtUsageEntry]) => {
        acc[key] = new Variable(value.contextId);
        return acc;
      }, {});
      newTrigger = (trigger as Field).withUpdatedArguments(args) as TTrigger;
    }
      
    return new GraphPath({
      ...this.props,
      tail: edge ? edge.tail : this.tail,
      edgeTriggers: this.props.edgeTriggers.concat(newTrigger),
      edgeIndexes: this.props.edgeIndexes.concat((edge ? edge.index : null) as number | TNullEdge),
      edgeConditions,
      subgraphEnteringEdge,
      edgeToTail: edge,
      runtimeTypesOfTail: updateRuntimeTypes(this.props.runtimeTypesOfTail, edge),
      runtimeTypesBeforeTailIfLastIsCast: edge?.transition?.kind === 'DownCast' ? this.props.runtimeTypesOfTail : undefined,
      // If there is no new `defer` taking precedence, and the edge is downcast, then we inherit the prior version. This
      // is because we only try to re-enter subgraphs for @defer on concrete fields, and so as long as we add downcasts,
      // we should remember that we still need to try re-entering the subgraph.
      deferOnTail: defer ?? (edge && edge.transition.kind === 'DownCast' ? this.props.deferOnTail : undefined),
      contextToSelection,
      parameterToContext,
    });
  }
  
  /**
   * We are going to grow the conditions by one element with the pathTree on the resolution. Additionally, we may need to merge or replace
   * the existing elements with elements from the ContextMap
   */
  private mergeEdgeConditionsWithResolution(conditionsResolution: ConditionResolution): {
    edgeConditions: (OpPathTree | null)[],
    contextToSelection: (Set<string> | null)[],
    parameterToContext: (Map<string, ContextAtUsageEntry> | null)[],
  }{
    const edgeConditions = this.props.edgeConditions.concat(conditionsResolution.pathTree ?? null);
    const contextToSelection = this.props.contextToSelection.concat(null);
    const parameterToContext = this.props.parameterToContext.concat(null);
    
    if (conditionsResolution.contextMap === undefined || conditionsResolution.contextMap.size === 0) {
      return {
        edgeConditions,
        contextToSelection,
        parameterToContext,
      };
    }
    
    parameterToContext[parameterToContext.length-1] = new Map();
    
    for (const [_, entry] of conditionsResolution.contextMap) {
      const idx = edgeConditions.length - entry.levelsInQueryPath -1;
      assert(idx >= 0, 'calculated condition index must be positive');
      
      
      if (entry.pathTree) {
        edgeConditions[idx] = edgeConditions[idx]?.merge(entry.pathTree) ?? entry.pathTree;
      }
      if (contextToSelection[idx] === null) {
        contextToSelection[idx] = new Set();
      }
      contextToSelection[idx]?.add(entry.id);
      
      parameterToContext[parameterToContext.length-1]?.set(entry.paramName, { contextId: entry.id, relativePath: Array(entry.levelsInDataPath).fill(".."), selectionSet: entry.selectionSet, subgraphArgType: entry.argType } );
    }
    return {
      edgeConditions,
      contextToSelection,
      parameterToContext,
    };
  }
  
  /**
   * Creates a new path corresponding to concatenating the provide path _after_ this path.
   *
   * @param tailPath - the path to concatenate at the end of this path. That path must start on the vertex at which
   *   this path ends.
   * @returns the newly created path.
   */
  concat(tailPath: GraphPath<TTrigger, Vertex, TNullEdge>): GraphPath<TTrigger, RV, TNullEdge> {
    assert(this.tail.index === tailPath.root.index, () => `Cannot concat ${tailPath} after ${this}`);
    if (tailPath.size === 0) {
      return this;
    }

    let prevRuntimeTypes = this.props.runtimeTypesBeforeTailIfLastIsCast;
    let runtimeTypes = this.props.runtimeTypesOfTail;
    for (const [edge] of tailPath) {
      prevRuntimeTypes = runtimeTypes;
      runtimeTypes = updateRuntimeTypes(runtimeTypes, edge);
    }
    return new GraphPath({
      ...this.props,
      tail: tailPath.tail,
      edgeTriggers: this.props.edgeTriggers.concat(tailPath.props.edgeTriggers),
      edgeIndexes: this.props.edgeIndexes.concat(tailPath.props.edgeIndexes),
      edgeConditions: this.props.edgeConditions.concat(tailPath.props.edgeConditions),
      subgraphEnteringEdge: tailPath.subgraphEnteringEdge ? tailPath.subgraphEnteringEdge : this.subgraphEnteringEdge,
      ownPathIds: this.props.ownPathIds.concat(tailPath.props.ownPathIds),
      overriddingPathIds: this.props.overriddingPathIds.concat(tailPath.props.overriddingPathIds),
      edgeToTail: tailPath.props.edgeToTail,
      runtimeTypesOfTail: runtimeTypes,
      runtimeTypesBeforeTailIfLastIsCast: tailPath.props.edgeToTail?.transition?.kind === 'DownCast' ? prevRuntimeTypes : undefined,
      deferOnTail: tailPath.deferOnTail,
    });
  }

  checkDirectPathFromPreviousSubgraphTo(
    typeName: string,
    triggerToEdge: (graph: QueryGraph, vertex: Vertex, t: TTrigger, overrideConditions: Map<string, boolean>) => Edge | null | undefined,
    overrideConditions: Map<string, boolean>,
    prevSubgraphStartingVertex?: Vertex,
  ): Vertex | undefined {
    const enteringEdge = this.subgraphEnteringEdge;
    if (!enteringEdge) {
      return undefined;
    }
    
    // TODO: Temporary fix to avoid optimization if context exists.
    // permanent fix is described here: https://github.com/apollographql/federation/pull/3017#pullrequestreview-2083949094
    if (this.graph.subgraphToArgs.size > 0) {
      return undefined;
    }

    // Usually, the starting subgraph in which we want to look for a direct path is the head of
    // `subgraphEnteringEdge`, that is, where we were just before coming to the current subgraph.
    // But for subgraph entering edges, we're not coming from a subgraph, so instead we pass the
    // "root" vertex of the subgraph of interest in `prevSubgraphStartingVertex`. And if that
    // is undefined (for a subgraph entering edge), then that means the subgraph does not have
    // the root type in question (say, no mutation type), and so there can be no direct path in
    // that subgraph.
    if (enteringEdge.edge.transition.kind === 'SubgraphEnteringTransition' && !prevSubgraphStartingVertex) {
      return undefined;
    }

    let prevSubgraphVertex = prevSubgraphStartingVertex ?? enteringEdge.edge.head;
    for (let i = enteringEdge.index + 1; i < this.size; i++) {
      const triggerToMatch = this.props.edgeTriggers[i];
      const prevSubgraphMatchingEdge = triggerToEdge(this.graph, prevSubgraphVertex, triggerToMatch, overrideConditions);
      if (prevSubgraphMatchingEdge === null) {
        // This means the trigger doesn't make us move (it's typically an inline fragment with no conditions, just directive), which we can always match.
        continue;
      }
      // If the edge has conditions, we don't consider it a direct path as we don't know if that condition can be satisfied and at what cost.
      if (!prevSubgraphMatchingEdge || prevSubgraphMatchingEdge.conditions) {
        return undefined;
      }
      prevSubgraphVertex = prevSubgraphMatchingEdge.tail;
    }
    // If we got here, that mean we were able to match all the triggers from the path since we switched from the previous graph directly into
    // the previous graph, and so, assuming we're on the proper type, we have a direct path in that previous graph.
    return prevSubgraphVertex.type.name === typeName ? prevSubgraphVertex : undefined;
  }

  /**
   * The set of edges that may legally continue this path.
   */
  nextEdges(): readonly Edge[] {
    if (this.deferOnTail) {
      // If we path enters a @defer (meaning that what comes after needs to be deferred), then it's the one special case where we
      // explicitly need to ask for edges-to-self, as we _will_ force the use of a @key edge (so we can send the non-deferred part
      // immediately) and we may have to resume the deferred part in the same subgraph than the one in which we were (hence the need
      // for edges to self).
      return this.graph.outEdges(this.tail, true);
    }

    // In theory, we could always return `this.graph.outEdges(this.tail)` here. But in practice, `nonTrivialFollowupEdges` may give us a subset
    // of those "out edges" that avoids some of the edges that we know we don't need to check because they are guaranteed to be inefficient
    // after the previous `tailEdge`. Note that is purely an optimization (see https://github.com/apollographql/federation/pull/1653 for more details).
    const tailEdge = this.props.edgeToTail;
    return tailEdge
      ? this.graph.nonTrivialFollowupEdges(tailEdge)
      : this.graph.outEdges(this.tail);
  }

  /**
   * Whether the path is terminal, that is ends on a terminal vertex.
   */
  isTerminal() {
    return this.graph.isTerminal(this.tail);
  }

  /**
   * Whether this path is a `RootPath`, that is one whose starting vertex is one of the underlying query graph root.
   */
  isRootPath(): this is RootPath<TTrigger, TNullEdge> {
    return isRootVertex(this.root);
  }

  mapMainPath<T>(mapper: (e: Edge | TNullEdge, pathIdx: number) => T): T[] {
    const result = new Array(this.size);
    let v: Vertex = this.root;
    for (let i = 0; i < this.size; i++) {
      const edge = this.edgeAt(i, v);
      result[i] = mapper(edge, i);
      if (edge) {
        v = edge.tail;
      }
    }
    return result;
  }

  private edgeAt(index: number, v: Vertex): Edge | TNullEdge {
    const edgeIdx = this.props.edgeIndexes[index];
    return (edgeIdx !== null ? this.graph.outEdge(v, edgeIdx) : null) as Edge | TNullEdge;
  }

  reduceMainPath<T>(reducer: (accumulator: T, edge: Edge | TNullEdge, pathIdx: number) => T, initialValue: T): T {
    let value = initialValue;
    let v: Vertex = this.root;
    for (let i = 0; i < this.size; i++) {
      const edge = this.edgeAt(i, v);
      value = reducer(value, edge, i);
      if (edge) {
        v = edge.tail;
      }
    }
    return value;
  }

  /**
   * Whether the path forms a cycle on the its end vertex, that is if the end vertex of this path has already been encountered earlier in the path.
   */
  hasJustCycled(): boolean {
    if (this.root.index == this.tail.index) {
      return true;
    }
    let v: Vertex = this.root;
    // We ignore the last edge since it's the one leading to the current vertex.
    for (let i = 0; i < this.size - 1; i++) {
      const edge = this.edgeAt(i, v);
      if (!edge) {
        continue;
      }
      v = edge.tail;
      if (v.index == this.tail.index) {
        return true;
      }
    }
    return false;
  }

  /**
   * Whether any of the edge in the path has associated conditions paths.
   */
  hasAnyEdgeConditions(): boolean {
    return this.props.edgeConditions.some(c => c !== null);
  }

  isOnTopLevelQueryRoot(): boolean {
    if (!isRootVertex(this.root)) {
      return false;
    }
    // We walk the vertices and as soon as we take a field (or move out of the root type),
    // we know we're not on the top-level query/mutation/subscription root anymore. The reason we don't
    // just check that size <= 1 is that we could have top-level `... on Query`
    // conditions that don't actually move us.
    let vertex: Vertex = this.root;
    for (let i = 0; i < this.size; i++) {
      const edge = this.edgeAt(i, vertex);
      if (!edge) {
        continue;
      }
      if (edge.transition.kind === 'FieldCollection' || !isSchemaRootType(edge.tail.type)) {
        return false;
      }
      vertex = edge.tail;
    }
    return true;
  }

  truncateTrailingDowncasts(): GraphPath<TTrigger, RV, TNullEdge> {
    let lastNonDowncastIdx = -1;
    let v: Vertex = this.root;
    let lastNonDowncastVertex = v;
    let lastNonDowncastEdge: Edge | undefined;
    let runtimeTypes = isFederatedGraphRootType(this.root.type) ? [] : possibleRuntimeTypes(this.root.type as CompositeType);
    let runtimeTypesAtLastNonDowncastEdge = runtimeTypes;
    for (let i = 0; i < this.size; i++) {
      const edge = this.edgeAt(i, v);
      runtimeTypes = updateRuntimeTypes(runtimeTypes, edge);
      if (edge) {
        v = edge.tail;
        if (edge.transition.kind !== 'DownCast') {
          lastNonDowncastIdx = i;
          lastNonDowncastVertex = v;
          lastNonDowncastEdge = edge;
          runtimeTypesAtLastNonDowncastEdge = runtimeTypes;
        }
      }
    }
    if (lastNonDowncastIdx < 0 || lastNonDowncastIdx === this.size -1) {
      return this;
    }

    const newSize = lastNonDowncastIdx + 1;
    return new GraphPath({
      ...this.props,
      tail: lastNonDowncastVertex,
      edgeTriggers: this.props.edgeTriggers.slice(0, newSize),
      edgeIndexes: this.props.edgeIndexes.slice(0, newSize),
      edgeConditions: this.props.edgeConditions.slice(0, newSize),
      edgeToTail: lastNonDowncastEdge,
      runtimeTypesOfTail: runtimeTypesAtLastNonDowncastEdge,
      runtimeTypesBeforeTailIfLastIsCast: undefined,
    });
  }

  markOverridding(otherOptions: GraphPath<TTrigger, RV, TNullEdge>[][]): {
    thisPath: GraphPath<TTrigger, RV, TNullEdge>,
    otherOptions: GraphPath<TTrigger, RV, TNullEdge>[][],
  } {
    const newId = uuidv4();
    return {
      thisPath: new GraphPath({
        ...this.props,
        ownPathIds: this.props.ownPathIds.concat(newId),
      }),
      otherOptions: otherOptions.map((paths) => paths.map((p) => new GraphPath({
        ...p.props,
        overriddingPathIds: p.props.overriddingPathIds.concat(newId),
      }))),
    };
  }

  isOverriddenBy(otherPath: GraphPath<TTrigger, RV, TNullEdge>): boolean {
    for (const overriddingId of this.props.overriddingPathIds) {
      if (otherPath.props.ownPathIds.includes(overriddingId)) {
        return true;
      }
    }
    return false;
  }

  tailIsInterfaceObject(): boolean {
    if (!isObjectType(this.tail.type)) {
      return false;
    }

    const schema = this.graph.sources.get(this.tail.source);
    const metadata = federationMetadata(schema!);
    return metadata?.isInterfaceObjectType(this.tail.type) ?? false;
  }

  toString(): string {
    const isRoot = isRootVertex(this.root);
    if (isRoot && this.size === 0) {
      return '_';
    }
    const pathStr = this.mapMainPath((edge, idx) => {
      if (edge) {
        if (isRoot && idx == 0) {
          return edge.tail.toString();
        }
        const label = edge.label();
        return ` -${label === "" ? "" : '-[' + label + ']-'}-> ${edge.tail}`
      }
      return ` (${this.props.edgeTriggers[idx]}) `;
    }).join('');
    const deferStr = this.deferOnTail ? ` <defer='${this.deferOnTail.label}'>` : '';
    const typeStr = this.props.runtimeTypesOfTail.length > 0 ? ` (types: [${this.props.runtimeTypesOfTail.join(', ')}])` : '';
    return `${isRoot ? '' : this.root}${pathStr}${deferStr}${typeStr}`;
  }
}

export interface PathIterator<TTrigger, TNullEdge extends null | never = never> extends Iterator<[Edge | TNullEdge, TTrigger, OpPathTree | null, Set<string> | null, Map<string, ContextAtUsageEntry> | null]> {
  currentIndex: number,
  currentVertex: Vertex
}

/**
 * A `GraphPath` that starts on a vertex that is a root vertex (of the query graph of which this is a path).
 */
export type RootPath<TTrigger, TNullEdge extends null | never = never> = GraphPath<TTrigger, RootVertex, TNullEdge>;

export type OpTrigger = OperationElement | PathContext;

/**
 * A `GraphPath` whose triggers are `OperationElement` (essentially meaning that the path has been guided by a graphQL query).
 */
export type OpGraphPath<RV extends Vertex = Vertex> = GraphPath<OpTrigger, RV, null>;

/**
 * An `OpGraphPath` that starts on a vertex that is a root vertex (of the query graph of which this is a path).
 */
export type OpRootPath = OpGraphPath<RootVertex>;

export function isRootPath(path: OpGraphPath<any>): path is OpRootPath {
  return isRootVertex(path.root);
}

export function terminateWithNonRequestedTypenameField<V extends Vertex>(path: OpGraphPath<V>, overrideConditions: Map<string, boolean>): OpGraphPath<V> {
  // If the last step of the path was a fragment/type-condition, we want to remove it before we get __typename.
  // The reason is that this avoid cases where this method would make us build plans like:
  // {
  //   foo {
  //     __typename
  //     ... on A {
  //       __typename
  //     }
  //     ... on B {
  //       __typename
  //     }
  // }
  // Instead, we just generate:
  // {
  //   foo {
  //     __typename
  //   }
  // }
  // Note it's ok to do this because the __typename we add is _not_ requested, it is just added in cases where we
  // need to ensure a selection is not empty, and so this transformation is fine to do.
  path = path.truncateTrailingDowncasts();
  if (!isCompositeType(path.tail.type)) {
    return path;
  }
  const typenameField = new Field(path.tail.type.typenameField()!);
  const edge = edgeForField(path.graph, path.tail, typenameField, overrideConditions);
  assert(edge, () => `We should have an edge from ${path.tail} for ${typenameField}`);
  return path.add(typenameField, edge, noConditionsResolution);
}

export function traversePath(
  path: GraphPath<any>,
  onEdges: (edge: Edge) => void
){
  for (const [edge, _, conditions] of path) {
    if (conditions) {
      traversePathTree(conditions, onEdges);
    }
    onEdges(edge);
  }
}

// Note that ConditionResolver are guaranteed to be only called for edge with conditions.
export type ConditionResolver =
  (edge: Edge, context: PathContext, excludedDestinations: ExcludedDestinations, excludedConditions: ExcludedConditions, extraConditions?: SelectionSet) => ConditionResolution;


type ContextMapEntry = {
  levelsInDataPath: number,
  levelsInQueryPath: number,
  pathTree?: OpPathTree,
  selectionSet: SelectionSet,
  inboundEdge: Edge,
  paramName: string,
  argType: Type,
  id: string,
}
  
export type ConditionResolution = {
  satisfied: boolean,
  cost: number,
  pathTree?: OpPathTree,
  contextMap?: Map<string, ContextMapEntry>,
  // Note that this is not guaranteed to be set even if satistied === false.
  unsatisfiedConditionReason?: UnsatisfiedConditionReason
}

export enum UnsatisfiedConditionReason {
  NO_POST_REQUIRE_KEY,
  NO_CONTEXT_SET
}

export const noConditionsResolution: ConditionResolution = { satisfied: true, cost: 0 };
export const unsatisfiedConditionsResolution: ConditionResolution = { satisfied: false, cost: -1 };

export enum UnadvanceableReason {
  UNSATISFIABLE_KEY_CONDITION,
  UNSATISFIABLE_REQUIRES_CONDITION,
  UNRESOLVABLE_INTERFACE_OBJECT,
  NO_MATCHING_TRANSITION,
  UNREACHABLE_TYPE,
  IGNORED_INDIRECT_PATH,
  UNSATISFIABLE_OVERRIDE_CONDITION,
}

export type Unadvanceable = {
  sourceSubgraph: string,
  destSubgraph: string,
  reason: UnadvanceableReason,
  details: string
};

export class Unadvanceables {
  constructor(readonly reasons: Unadvanceable[]) {}

  toString() {
    return '[' + this.reasons.map((r) => `[${r.reason}](${r.sourceSubgraph}->${r.destSubgraph}) ${r.details}`).join(', ') + ']';
  }
}

export type UnadvanceableClosure = () => Unadvanceable | Unadvanceable[];

export class UnadvanceableClosures {
  private _unadvanceables: Unadvanceables | undefined;
  readonly closures: UnadvanceableClosure[];
  constructor(closures: UnadvanceableClosure | UnadvanceableClosure[]) {
    if (Array.isArray(closures)) {
      this.closures = closures;
    } else {
      this.closures = [closures];
    }
  }

  toUnadvanceables(): Unadvanceables {
    if (!this._unadvanceables) {
      this._unadvanceables = new Unadvanceables(this.closures.map((c) => c()).flat());
    }
    return this._unadvanceables;
  }
}

export function isUnadvanceableClosures(result: any[] | UnadvanceableClosures): result is UnadvanceableClosures {
  return result instanceof UnadvanceableClosures;
}

function pathTransitionToEdge(graph: QueryGraph, vertex: Vertex, transition: Transition, overrideConditions: Map<string, boolean>): Edge | null | undefined {
  for (const edge of graph.outEdges(vertex)) {
    // The edge must match the transition.
    if (!edge.matchesSupergraphTransition(transition)) {
      continue;
    }

    if (edge.satisfiesOverrideConditions(overrideConditions)) {
      return edge;
    }
  }
  return undefined;
}

/**
 * Wraps a 'composition validation' path (one built from `Transition`) along with the information necessary to compute
 * the indirect paths following that path, and cache the result of that computation when triggered.
 *
 * In other words, this is a `GraphPath<Transition, V>` plus lazy memoization of the computation of its following indirect
 * options.
 *
 * The rational is that after we've reached a given path, we might never need to compute the indirect paths following it
 * (maybe all the fields we'll care about are available "directive" (from the same subgraph)), or we might need to compute
 * it once, or we might need them multiple times, but the way the algorithm work, we don't know this in advance. So
 * this abstraction ensure that we only compute such indirect paths lazily, if we ever need them, but while ensuring
 * we don't recompute them multiple times if we do need them multiple times.
 */
export class TransitionPathWithLazyIndirectPaths<V extends Vertex = Vertex> {
  private lazilyComputedIndirectPaths: IndirectPaths<Transition, V> | undefined;

  constructor(
    readonly path: GraphPath<Transition, V>,
    readonly conditionResolver: ConditionResolver,
    readonly overrideConditions: Map<string, boolean>,
  ) {
  }

  static initial<V extends Vertex = Vertex>(
    initialPath: GraphPath<Transition, V>,
    conditionResolver: ConditionResolver,
    overrideConditions: Map<string, boolean>,
  ): TransitionPathWithLazyIndirectPaths<V> {
    return new TransitionPathWithLazyIndirectPaths(initialPath, conditionResolver, overrideConditions);
  }

  indirectOptions(): IndirectPaths<Transition, V> {
    if (!this.lazilyComputedIndirectPaths) {
      this.lazilyComputedIndirectPaths = this.computeIndirectPaths();
    }
    return this.lazilyComputedIndirectPaths;
  }

  private computeIndirectPaths(): IndirectPaths<Transition, V>  {
    return advancePathWithNonCollectingAndTypePreservingTransitions(
      this.path,
      emptyContext,
      this.conditionResolver,
      [],
      [],
      (t) => t,
      pathTransitionToEdge,
      this.overrideConditions,
      getFieldParentTypeForEdge,
    );
  }

  toString(): string {
    return this.path.toString();
  }
}

// Note: conditions resolver should return `null` if the condition cannot be satisfied. If it is satisfied, it has the choice of computing
// the actual tree, which we need for query planning, or simply returning "undefined" which means "The condition can be satisfied but I didn't
// bother computing a tree for it", which we use for simple validation.

// Returns some a `Unadvanceables` object if there is no way to advance the path with this transition. Otherwise, it returns a list of options (paths) we can be in after advancing the transition.
// The lists of options can be empty, which has the special meaning that the transition is guaranteed to have no results (it corresponds to unsatisfiable conditions),
// meaning that as far as composition validation goes, we can ignore that transition (and anything that follows) and otherwise continue.
export function advancePathWithTransition<V extends Vertex>(
  subgraphPath: TransitionPathWithLazyIndirectPaths<V>,
  transition: Transition,
  targetType: NamedType,
  overrideConditions: Map<string, boolean>,
) : TransitionPathWithLazyIndirectPaths<V>[] | UnadvanceableClosures {
  // The `transition` comes from the supergraph. Now, it is possible that a transition can be expressed on the supergraph, but correspond
  // to an 'unsatisfiable' condition on the subgraph. Let's consider:
  // - Subgraph A:
  //    type Query {
  //       get: [I]
  //    }
  //
  //    interface I {
  //      k: Int
  //    }
  //
  //    type T1 implements I @key(fields: "k") {
  //      k: Int
  //      a: String
  //    }
  //
  //    type T2 implements I @key(fields: "k") {
  //      k: Int
  //      b: String
  //    }
  //
  // - Subgraph B:
  //    interface I {
  //      k: Int
  //    }
  //
  //    type T1 implements I @key(fields: "k") {
  //      k: Int
  //      myself: I
  //    }
  //
  // On the resulting supergraph, we will have a path for:
  //   {
  //     get {
  //       ... on T1 {
  //         myself {
  //           ... on T2 {
  //             b
  //           }
  //         }
  //       }
  //     }
  //   }
  //
  // However, as we compute possible subgraph paths, the `myself` field will get us
  // in subgraph `B` through `T1`'s key. But then, as we look at transition `... on T2`
  // from subgraph `B`, we have no such type/transition. But this does not mean that
  // the subgraphs shouldn't compose. What it really means is that the corresponding
  // query above can be done, but is guaranteed to never return anything (essentially,
  // we can query subgraph 'B' but will never get a `T2` so the result of the query
  // should be empty).
  //
  // So we need to handle this case and we do this first. Note that the only kind of
  // transition that can give use this is a 'DownCast' transition.
  // Also note that if the subgraph type we're on is an @interfaceObject type, then we
  // also can't be in this situation as an @interfaceObject type "stands in" for all
  // the possible implementations of that interface. And one way to detect if the subgraph
  // type an @interfaceObject is to check if the subgraph type is an object type while the
  // supergraph type is an interface one.
  if (transition.kind === 'DownCast' && !(isInterfaceType(transition.sourceType) && isObjectType(subgraphPath.path.tail.type))) {
    // If we consider a 'downcast' transition, it means that the target of that cast is composite, but also that the
    // last type of the subgraph path also is (that type is essentially the "source" of the cast).
    const supergraphRuntimeTypes = possibleRuntimeTypes(targetType as CompositeType);
    const subgraphRuntimeTypes = subgraphPath.path.tailPossibleRuntimeTypes();
    const intersection = supergraphRuntimeTypes.filter(t1 => subgraphRuntimeTypes.some(t2 => t1.name === t2.name)).map(t => t.name);
    // if we intersection is empty, it means whatever field got us here can never resolve into an object of the type we're casting
    // into. Essentially, we're good building a plan for this transition and whatever comes next: it'll just return nothing.
    if (intersection.length === 0) {
      debug.log(() => `No intersection between casted type ${targetType} and the possible types in this subgraph`);
      return [];
    }
  }

  debug.group(() => `Trying to advance ${subgraphPath} for ${transition}`);
  debug.group('Direct options:');
  const directOptions = advancePathWithDirectTransition(
    subgraphPath.path,
    transition,
    subgraphPath.conditionResolver,
    overrideConditions,
  );
  let options: GraphPath<Transition, V>[];
  const deadEndClosures: UnadvanceableClosure[] = [];
  if (isUnadvanceableClosures(directOptions)) {
    options = [];
    debug.groupEnd(() => 'No direct options');
    deadEndClosures.push(...directOptions.closures);
  } else {
    debug.groupEnd(() => advanceOptionsToString(directOptions));
    // If we can fulfill the transition directly (without taking an edge) and the target type is "terminal", then there is
    // no point in computing all the options.
    if (directOptions.length > 0 && isLeafType(targetType)) {
      debug.groupEnd(() => `reached leaf type ${targetType} so not trying indirect paths`);
      return createLazyTransitionOptions(directOptions, subgraphPath, overrideConditions);
    }
    options = directOptions;
  }
  // Otherwise, let's try non-collecting edges and see if we can find some (more) options there.
  debug.group(`Computing indirect paths:`);
  const pathsWithNonCollecting = subgraphPath.indirectOptions();
  if (pathsWithNonCollecting.paths.length > 0) {
    debug.groupEnd(() => `${pathsWithNonCollecting.paths.length} indirect paths: ${pathsWithNonCollecting.paths}`);
    debug.group('Validating indirect options:');
    for (const nonCollectingPath of pathsWithNonCollecting.paths) {
      debug.group(() => `For indirect path ${nonCollectingPath}:`);
      const pathsWithTransition = advancePathWithDirectTransition(
        nonCollectingPath,
        transition,
        subgraphPath.conditionResolver,
        overrideConditions,
      );
      if (isUnadvanceableClosures(pathsWithTransition)) {
        debug.groupEnd(() => `Cannot be advanced with ${transition}`);
        deadEndClosures.push(...pathsWithTransition.closures);
      } else {
        debug.groupEnd(() => `Adding valid option: ${pathsWithTransition}`);
        options = options.concat(pathsWithTransition);
      }
    }
    debug.groupEnd();
  } else {
    debug.groupEnd('no indirect paths');
  }
  debug.groupEnd(() => options.length > 0 ? advanceOptionsToString(options) : `Cannot advance ${transition} for this path`);
  if (options.length > 0) {
    return createLazyTransitionOptions(options, subgraphPath, overrideConditions);
  }

  const indirectDeadEndClosures = pathsWithNonCollecting.deadEnds.closures;
  return new UnadvanceableClosures(() => {
    const allDeadEnds = new UnadvanceableClosures(deadEndClosures.concat(indirectDeadEndClosures))
      .toUnadvanceables().reasons;
    if (transition.kind === 'FieldCollection') {
      const typeName = transition.definition.parent.name;
      const fieldName = transition.definition.name;
      const subgraphsWithDeadEnd = new Set(allDeadEnds.map(e => e.destSubgraph));
      for (const [subgraph, schema] of subgraphPath.path.graph.sources.entries()) {
        if (subgraphsWithDeadEnd.has(subgraph)) {
          continue;
        }
        const type = schema.type(typeName);
        if (type && isCompositeType(type) && type.field(fieldName)) {
          // That subgraph has the type we look for, but we have recorded no dead-ends. This means there is no edge to that type,
          // and thus that either:
          // - it has no keys.
          // - the path to advance it an @interfaceObject type, the type we look for is an implementation of that interface, and
          //   there no key on the interface.
          const typenameOfTail = subgraphPath.path.tail.type.name;
          const typeOfTailInSubgraph = schema.type(typenameOfTail);
          if (!typeOfTailInSubgraph) {
            // This means that 1) the type of the path we're trying to advance is different from the transition we're considering,
            // and that should only happen if the path is on an @interfaceObject type, and 2) the subgraph we're looking at
            // actually doesn't have that interface. To be able to jump to that subgraph, we would need the interface and it
            // would need to have a resolvable key, but it has neither.
            allDeadEnds.push({
              sourceSubgraph: subgraphPath.path.tail.source,
              destSubgraph: subgraph,
              reason: UnadvanceableReason.UNREACHABLE_TYPE,
              details: `cannot move to subgraph "${subgraph}", which has field "${transition.definition.coordinate}", because interface "${typenameOfTail}" is not defined in this subgraph (to jump to "${subgraph}", it would need to both define interface "${typenameOfTail}" and have a @key on it)`,
            });
          } else {
            // `typeOfTailInSubgraph` exists, so it's either equal to `type`, or it's an interface of it. In any case, it's composite.
            assert(isCompositeType(typeOfTailInSubgraph), () => `Type ${typeOfTailInSubgraph} in ${subgraph} should be composite`);
            const metadata = federationMetadata(schema);
            const keys: Directive<CompositeType, {fields: any, resolvable?: boolean}>[] = metadata ? typeOfTailInSubgraph.appliedDirectivesOf(metadata.keyDirective()) : [];
            const allNonResolvable = keys.length > 0 && keys.every((k) => !(k.arguments().resolvable ?? true));
            assert(keys.length === 0 || allNonResolvable, () => `After ${subgraphPath} and for transition ${transition}, expected type ${type} in ${subgraph} to have no resolvable keys`);
            const kindOfType = typeOfTailInSubgraph === type ? 'type' : 'interface';
            const explanation = keys.length === 0
              ? `${kindOfType} "${typenameOfTail}" has no @key defined in subgraph "${subgraph}"`
              : `none of the @key defined on ${kindOfType} "${typenameOfTail}" in subgraph "${subgraph}" are resolvable (they are all declared with their "resolvable" argument set to false)`;
            allDeadEnds.push({
              sourceSubgraph: subgraphPath.path.tail.source,
              destSubgraph: subgraph,
              reason: UnadvanceableReason.UNREACHABLE_TYPE,
              details: `cannot move to subgraph "${subgraph}", which has field "${transition.definition.coordinate}", because ${explanation}`
            });
          }
        }
      }
    }
  
    return allDeadEnds;
  });
}

function createLazyTransitionOptions<V extends Vertex>(
  options: GraphPath<Transition, V>[],
  origin: TransitionPathWithLazyIndirectPaths<V>,
  overrideConditions: Map<string, boolean>,
) : TransitionPathWithLazyIndirectPaths<V>[] {
  return options.map(option => new TransitionPathWithLazyIndirectPaths(
    option,
    origin.conditionResolver,
    overrideConditions,
  ));
}

// A "set" of excluded destinations, that is subgraph name. Note that we use an array instead of set because this is used
// in pretty hot paths (the whole path computation is CPU intensive) and will basically always be tiny (it's bounded
// by the number of distinct key on a given type, so usually 2-3 max; even in completely unrealistic cases, it's hard bounded
// by the number of subgraph), so array is going to perform a lot better than `Set` in practice.
export type ExcludedDestinations = readonly string[];

function isDestinationExcluded(destination: string, excluded: ExcludedDestinations): boolean {
  return excluded.includes(destination);
}

export function sameExcludedDestinations(ex1: ExcludedDestinations, ex2: ExcludedDestinations): boolean {
  if (ex1 === ex2) {
    return true;
  }
  if (ex1.length !== ex2.length) {
    return false;
  }
  return ex1.every((d) => ex2.includes(d));
}

function addDestinationExclusion(excluded: ExcludedDestinations, destination: string): ExcludedDestinations {
  return excluded.includes(destination) ? excluded : excluded.concat(destination);
}

export type ExcludedConditions = readonly SelectionSet[];

function isConditionExcluded(condition: SelectionSet | undefined, excluded: ExcludedConditions): boolean {
  if (!condition) {
    return false;
  }
  return excluded.find(e => condition.equals(e)) !== undefined;
}

export function addConditionExclusion(excluded: ExcludedConditions, newExclusion: SelectionSet | undefined): ExcludedConditions {
  return newExclusion ? excluded.concat(newExclusion) : excluded;
}

function popMin<TTrigger, V extends Vertex, TNullEdge extends null | never = never>(
  stack: GraphPath<TTrigger, V, TNullEdge>[]
): GraphPath<TTrigger, V, TNullEdge> {
  let minIdx = 0;
  let minSize = stack[0].size;
  for (let i = 1; i < stack.length; i++) {
    if (stack[i].size < minSize) {
      minSize = stack[i].size;
      minIdx = i;
    }
  }
  const min = stack[minIdx];
  stack.splice(minIdx, 1);
  return min;
}

export type IndirectPaths<TTrigger, V extends Vertex = Vertex, TNullEdge extends null | never = never, TDeadEnds extends UnadvanceableClosures | never = UnadvanceableClosures> = {
  paths: GraphPath<TTrigger, V, TNullEdge>[],
  deadEnds: TDeadEnds
}

function advancePathWithNonCollectingAndTypePreservingTransitions<TTrigger, V extends Vertex, TNullEdge extends null | never = never, TDeadEnds extends UnadvanceableClosures | never = UnadvanceableClosures>(
  path: GraphPath<TTrigger, V, TNullEdge>,
  context: PathContext,
  conditionResolver: ConditionResolver,
  excludedDestinations: ExcludedDestinations,
  excludedConditions: ExcludedConditions,
  convertTransitionWithCondition: (transition: Transition, context: PathContext) => TTrigger,
  triggerToEdge: (graph: QueryGraph, vertex: Vertex, t: TTrigger, overrideConditions: Map<string, boolean>) => Edge | null | undefined,
  overrideConditions: Map<string, boolean>,
  getFieldParentType: (trigger: TTrigger) => CompositeType | null,
): IndirectPaths<TTrigger, V, TNullEdge, TDeadEnds>  {
  // If we're asked for indirect paths after an "@interfaceObject fake down cast" but that down cast comes just after a non-collecting edges, then
  // we can ignore it (skip indirect paths from there). The reason is that the presence of the non-collecting just before the fake down-cast means
  // we add looked at indirect paths just before that down cast, but that fake downcast really does nothing in practice with the subgraph it's on,
  // so any indirect path from that fake down cast will have a valid indirect path _before_ it, and so will have been taken into account independently.
  if (path.lastIsIntefaceObjectFakeDownCastAfterEnteringSubgraph()) {
    // Note: we need to register a dead-end for every subgraphs we "could" be going to, or the code calling this may try to infer a reason on its own
    // and we'll run into some assertion.
    return {
      paths: [],
      deadEnds: new UnadvanceableClosures(() => {
        const reachableSubgraphs = new Set(path.nextEdges().filter((e) => !e.transition.collectOperationElements && e.tail.source !== path.tail.source).map((e) => e.tail.source));
        return Array.from(reachableSubgraphs).map((s) => ({
          sourceSubgraph: path.tail.source,
          destSubgraph: s,
          reason: UnadvanceableReason.IGNORED_INDIRECT_PATH,
          details: `ignoring moving from "${path.tail.source}" to "${s}" as a more direct option exists`,
        }))
      }) as TDeadEnds,
    };
  }

  const isTopLevelPath = path.isOnTopLevelQueryRoot();
  const typeName = isFederatedGraphRootType(path.tail.type) ? undefined : path.tail.type.name;
  const originalSource = path.tail.source;
  // For each source, we store the best path we find for that source with the score, or `null` if we can
  // decide that we should try going to that source (typically because we can prove that this create an
  // inefficient detour for which a more direct path exists and will be found).
  const bestPathBySource = new Map<string, [GraphPath<TTrigger, V, TNullEdge>, number] | null>();
  const deadEndClosures: UnadvanceableClosure[] = [];
  const toTry: GraphPath<TTrigger, V, TNullEdge>[] = [ path ];
  while (toTry.length > 0) {
    // Note that through `excluded` we avoid taking the same edge from multiple options. But that means it's important we try
    // the smallest paths first. That is, if we could in theory have path A -> B and A -> C -> B, and we can do B -> D,
    // then we want to keep A -> B -> D, not A -> C -> B -> D.
    const toAdvance = popMin(toTry);
    const nextEdges =  toAdvance.nextEdges().filter(e => !e.transition.collectOperationElements);
    if (nextEdges.length === 0) {
      // The subtlety here is that this may either mean that there is no non-collecting edges from the tail of
      // this path, _or_ that there is some but they "trivial" since `nextEdges` above may end up calling
      // `QueryGraph.nonTrivialFollowupEdges()`. In the later, this means there is a key we could use, but
      // it get us back to the previous vertex in the path, which is useless. But we distinguish that case
      // to 1) make the debug more "true" and 2) much more importantly, record a "dead-end" for this path.
      const outEdges = toAdvance.graph.outEdges(toAdvance.tail).filter(e => !e.transition.collectOperationElements);
      if (outEdges.length > 0) {
        debug.log(() => `Nothing to try for ${toAdvance}: it only has "trivial" non-collecting outbound edges`);
        deadEndClosures.push(() => {
          const unadvanceables = [];
          for (const edge of outEdges) {
            if (edge.tail.source !== toAdvance.tail.source && edge.tail.source !== originalSource) {
              unadvanceables.push({
                sourceSubgraph: toAdvance.tail.source,
                destSubgraph: edge.tail.source,
                reason: UnadvanceableReason.IGNORED_INDIRECT_PATH,
                details: `ignoring moving to subgraph "${edge.tail.source}" using @key(fields: "${edge.conditions?.toString(true, false)}") of "${edge.head.type}" because there is a more direct path in ${edge.tail.source} that avoids ${toAdvance.tail.source} altogether`
              });
            }
          }
          return unadvanceables;
        })
      } else {
        debug.log(() => `Nothing to try for ${toAdvance}: it has no non-collecting outbound edges`);
      }
      continue;
    }
    debug.group(() => `From ${toAdvance}:`);
    for (const edge of nextEdges) {
      debug.group(() => `Testing edge ${edge}`);
      const target = edge.tail;

      if (isDestinationExcluded(target.source, excludedDestinations)) {
        debug.groupEnd(`Ignored: edge is excluded`);
        continue;
      }

      // If the edge takes us back to the subgraph in which we started, we're not really interested
      // (we've already checked for direct transition from that original subgraph). On exception though
      // is if we're just after a @defer, in which case re-entering the current subgraph is actually
      // a thing.
      if (target.source === originalSource && !toAdvance.deferOnTail) {
        debug.groupEnd('Ignored: edge get us back to our original source');
        continue;
      }

      // We have edges between Query objects so that if a field returns a query object, we can jump to any subgraph
      // at that point. However, there is no point of using those edges at the beginning of a path, except for when
      // we have a @defer, in which case we want to allow re-jumping to the same subgraph.
      if (isTopLevelPath
        && (edge.transition.kind === 'RootTypeResolution' || edge.transition.kind === 'KeyResolution')
        && !(toAdvance.deferOnTail && edge.isKeyOrRootTypeEdgeToSelf())
      ) {
        debug.groupEnd(`Ignored: edge is a top-level "RootTypeResolution" or "KeyResolution"`);
        continue;
      }

      const prevForSource = bestPathBySource.get(target.source);
      if (prevForSource === null) {
        debug.groupEnd(() => `Ignored: we've shown before than going to ${target.source} is not productive`);
        continue;
      }

      if (prevForSource
        && (prevForSource[0].size < toAdvance.size + 1
          || (prevForSource[0].size == toAdvance.size + 1 && prevForSource[1] <= 1)
        )
      ) {
        // We've already found another path that gets us to the same subgraph than the edge we're
        // about to check. If that previous path is strictly shorter than the path we'd obtain
        // with the new edge, then we don't consider this edge (it's a longer way to get to the same place).
        // And if the previous path is the same size (as the one obtained with that edge), but
        // that the previous path cost for getting the condition was 0 or 1, then the new edge cannot
        // really improve on this and we don't bother with it. Note that a cost of 0 can only happen
        // during composition validation where all costs are 0 to mean "we don't care about costs".
        // Meaning effectively that for validation, as soon as we have a path to a subgraph, we ignore
        // other options even if they may be "faster".
        debug.groupEnd(() => `Ignored: a better (shorter) path to the same subgraph already added`);
        continue;
      }

      if (isConditionExcluded(edge.conditions, excludedConditions)) {
        debug.groupEnd(`Ignored: edge condition is excluded`);
        continue;
      }

      debug.group(() => `Validating conditions ${edge.conditions}`);
      // As we validate the condition for this edge, it might be necessary to jump to another subgraph, but if for that
      // we need to jump to the same subgraph we're trying to get to, then it means there is another, shorter way to
      // go to our destination and we can return that shorter path, not the one with the edge we're trying.
      const conditionResolution = canSatisfyConditions(
        toAdvance,
        edge,
        conditionResolver,
        context,
        addDestinationExclusion(excludedDestinations, target.source),
        excludedConditions,
        getFieldParentType,
      );
      if (conditionResolution.satisfied) {
        debug.groupEnd('Condition satisfied');
        // We _can_ get to `target.source` with that edge. But if we had already found another path to
        // the same subgraph, we want to replace it by this one only if either 1) it is shorter or 2) if
        // it's of equal size, only if the condition cost are lower than the previous one.
        if (prevForSource && prevForSource[0].size === toAdvance.size + 1 && prevForSource[1] <= conditionResolution.cost) {
          debug.groupEnd('Ignored: a better (less costly) path to the same subgraph already added');
          continue;
        }

        // It's important we minimize the number of options this method returns, because during query planning
        // with many fields, options here translate to state explosion. This is why we eliminated above
        // edges that provably have better options.
        // But we can do a slightly more involved check. Suppose we have a few subgraph A, B and C,
        // and suppose that we're considering an edge from B to C. We can then look at which subgraph we
        // were into before reaching B (which can be "none" if the query starts at B), and let say that
        // it is A. In other words, if we use the edge we're considering, we'll be looking at a path doing:
        //   ... -> A -> B -> <some fields in B> -> C
        // and `toAdvance` is currently just before that last step.
        // Now, we can fairly easily check if the fields we collected in B (the `<some fields in B>`) can
        // be also collected *directly* (without keys, nor requires) from A and if after that we could take
        // an edge to C. If we can do all that, then we know that the path we're considering is strictly
        // less efficient than doing:
        //   .. -> A -> <same fields but in A> -> C
        // and we've just validated that path exists and so will be found by another branch of the algorithm.
        // In that case, we can ignore the edge, knowing a better path exists.
        // Doing this drastically reduce state explosion in a number of cases.
        const subgraphEnteringEdge = toAdvance.subgraphEnteringEdge;
        // Note that we ignore the case where the "entering edge" is the "current" type as we might end up in an infinite
        // loop when calling `hasValidDirectKeyEdge` in that case without additional care and it's not useful because this
        // very method already ensure we don't create unnecessary chains of keys for the "current type"
        if (subgraphEnteringEdge && subgraphEnteringEdge.edge.tail.type.name !== typeName) {
          let prevSubgraphEnteringVertex: Vertex | undefined = undefined;
          let backToPreviousSubgraph: boolean;
          if (subgraphEnteringEdge.edge.transition.kind === 'SubgraphEnteringTransition') {
            assert(toAdvance.root instanceof RootVertex, () => `${toAdvance} should be a root path if it starts with subgraph entering edge ${subgraphEnteringEdge.edge}`);
            // Since mutation options need to originate from the same subgraph, we pretend we cannot find a root vertex
            // in another subgraph (effectively skipping the optimization).
            prevSubgraphEnteringVertex = toAdvance.root.rootKind !== 'mutation'
              ? rootVertexForSubgraph(toAdvance.graph, edge.tail.source, toAdvance.root.rootKind)
              : undefined;
            // If the entering edge is the root entering of subgraphs, then the "prev subgraph" is really `edge.tail.source` and
            // so `edge` always get us back to that (but `subgraphEnteringEdge.edge.head.source` would be `FEDERATED_GRAPH_ROOT_SOURCE`,
            // so the test we do in the `else` branch would not work here).
            backToPreviousSubgraph = true;
          } else {
            backToPreviousSubgraph = subgraphEnteringEdge.edge.head.source === edge.tail.source;
          }
          const prevSubgraphVertex = toAdvance.checkDirectPathFromPreviousSubgraphTo(edge.tail.type.name, triggerToEdge, overrideConditions, prevSubgraphEnteringVertex);
          const maxCost = toAdvance.subgraphEnteringEdge.cost + (backToPreviousSubgraph ? 0 : conditionResolution.cost);
          if (prevSubgraphVertex
            && (
              backToPreviousSubgraph
              || hasValidDirectKeyEdge(toAdvance.graph, prevSubgraphVertex, edge.tail.source, conditionResolver, maxCost)
            )
          ) {
            debug.groupEnd(
              () => `Ignored: edge correspond to a detour by subgraph ${edge.head.source} from subgraph ${subgraphEnteringEdge.edge.head.source}: `
              + `we have a direct path from ${subgraphEnteringEdge.edge.head.type} to ${edge.tail.type} in ${subgraphEnteringEdge.edge.head.source}`
              + (backToPreviousSubgraph ? '.' : ` and can move to ${edge.tail.source} from there`)
            );
            // Note that we just found that going to the previous subgraph is useless because there is a more direct path.
            // But we record that this previous subgraph should be avoid altogether because other some longer path
            // could try to get back to that same source but defeat this specific check due to having taken another
            // edge first (and thus the entering edge is different).
            // What we mean here is that if the path is A -> B -> <some fields> and we just found that we don't want to keep
            // A -> B -> <some fields> -> A because we know A -> <some fields> is possible directly, then we don't want this
            // method to later add A -> B -> <some fields> -> C -> A, as that is equally not useful.
            bestPathBySource.set(edge.tail.source, null);
            // We also record a dead-end because this optimization might make us return no path at all, and having
            // recorded no-dead ends would break an assertion in `advancePathWithTransition` that assumes that if
            // we have recorded no-dead end, that's because we have no key edges. But note that this 'dead end'
            // message shouldn't really ever reach users.
            deadEndClosures.push(() => {
              return {
                sourceSubgraph: toAdvance.tail.source,
                destSubgraph: edge.tail.source,
                reason: UnadvanceableReason.IGNORED_INDIRECT_PATH,
                details: `ignoring moving to subgraph "${edge.tail.source}" using @key(fields: "${edge.conditions?.toString(true, false)}") of "${edge.head.type}" because there is a more direct path in ${edge.tail.source} that avoids ${toAdvance.tail.source} altogether`
              };
            });
            continue;
          }
        }

        const updatedPath = toAdvance.add(convertTransitionWithCondition(edge.transition, context), edge, conditionResolution);
        debug.log(() => `Using edge, advance path: ${updatedPath}`);
        bestPathBySource.set(target.source, [updatedPath, conditionResolution.cost]);
        // It can be necessary to "chain" keys, because different subgraphs may have different keys exposed, and so we when we took
        // a key, we want to check if there is new key we can now take that take us to other subgraphs. For other 'non-collecting'
        // edges ('QueryResolution' and 'SubgraphEnteringTransition') however, chaining never give us additional value.
        // Note: one exception is the case of self-edges (which stay on the same vertex/subgraph): those will only be
        // looked at just after a @defer to handle potentially re-entering the same subgraph. When we take this, no point in
        // looking for chaining since we'll independently check the other edges already.
        if (edge.transition.kind === 'KeyResolution' && edge.head.source !== edge.tail.source) {
          toTry.push(updatedPath);
        }
      } else {
        debug.groupEnd('Condition unsatisfiable');
        deadEndClosures.push(() => {
          const source = toAdvance.tail.source;
          const dest = edge.tail.source;
          const hasOverriddenField = conditionHasOverriddenFieldsInSource(path.graph.sources.get(toAdvance.tail.source)!, edge.conditions!);
          const extraMsg = hasOverriddenField
            ? ` (note that some of those key fields are overridden in "${source}")`
            : "";
          return {
            sourceSubgraph: source,
            destSubgraph: dest,
            reason: UnadvanceableReason.UNSATISFIABLE_KEY_CONDITION,
            details: `cannot move to subgraph "${dest}" using @key(fields: "${edge.conditions?.toString(true, false)}") of "${edge.head.type}", the key field(s) cannot be resolved from subgraph "${source}"${extraMsg}`
          };
        });
      }
      debug.groupEnd(); // End of edge
    }
    debug.groupEnd();
  }
  return {
    paths: mapValues(bestPathBySource).filter(p => p !== null).map(b => b![0]),
    deadEnds: new UnadvanceableClosures(deadEndClosures) as TDeadEnds
  }
}

function rootVertexForSubgraph(graph: QueryGraph, subgraphName: string, rootKind: SchemaRootKind): Vertex | undefined {
  const root = graph.root(rootKind);
  assert(root, () => `Should not have ask for ${rootKind} as the graph does not have one`);
  const subgraphRootEdge = graph.outEdges(root).find((e) => e.tail.source === subgraphName);
  return subgraphRootEdge?.tail;
}

function conditionHasOverriddenFieldsInSource(schema: Schema, condition: SelectionSet): boolean {
  const externalDirective = federationMetadata(schema)!.externalDirective();
  return allFieldDefinitionsInSelectionSet(condition).some((field) => {
    // The subtlety here is that the definition of the fields in the condition are not the one of the subgraph we care
    // about here in general, because the conditions on key edge are those of the destination of the edge, and here
    // we want to check if the field is overridden in the source of the edge. Hence us getting the matching
    // definition in the input schema.
    const typeInSource = schema.type(field.parent.name)
    const fieldInSource = typeInSource && isObjectType(typeInSource) && typeInSource.field(field.name);
    return fieldInSource && fieldInSource.appliedDirectivesOf(externalDirective)?.pop()?.arguments().reason === '[overridden]';
  });
}

function hasValidDirectKeyEdge(
  graph: QueryGraph,
  from: Vertex,
  to: string,
  conditionResolver: ConditionResolver,
  maxCost: number
): boolean {
  for (const edge of graph.outEdges(from)) {
    if (edge.transition.kind !== 'KeyResolution' || edge.tail.source !== to) {
      continue;
    }
    const resolution = conditionResolver(edge, emptyContext, [], []);
    if (!resolution.satisfied) {
      continue;
    }
    // During composition validation, we consider all conditions to have cost 1.
    if (resolution.cost <= maxCost) {
      return true;
    }
  }
  return false;
}

function advancePathWithDirectTransition<V extends Vertex>(
  path: GraphPath<Transition, V>,
  transition: Transition,
  conditionResolver: ConditionResolver,
  overrideConditions: Map<string, boolean>,
) : GraphPath<Transition, V>[] | UnadvanceableClosures {
  assert(transition.collectOperationElements, "Supergraphs shouldn't have transitions that don't collect elements");

  if (
    transition.kind === 'FieldCollection'
    && transition.definition.parent.name !== path.tail.type.name
    && isCompositeType(path.tail.type)
    && !path.tailIsInterfaceObject()
  ) {
    // Usually, when we collect a field, the path should already be on the type of that field.
    // But one exception is due to the fact that a type condition may be "absorbed" by an
    // @interfaceObject, and once we'we taken a key on the interface to another subgraph
    // (the tail is not the interface object anymore), we need to "restore" the type condition
    // first.
    const updatedPath = advancePathWithDirectTransition(
      path,
      new DownCast(path.tail.type, transition.definition.parent),
      conditionResolver,
      overrideConditions,
    );
    // The case we described above should be the only case we capture here, and so the current
    // subgraph must have the implementation type (it may not have the field we want, but it
    // must have the type) and so we should be able to advance to it.
    assert(!isUnadvanceableClosures(updatedPath), () => `Advancing ${path} for ${transition} gave ${updatedPath}`);
    // Also note that there is currently no case where we should have more that one option.
    assert(updatedPath.length === 1, () => `Expect one path, got ${updatedPath.length}`)
    path = updatedPath[0];
    // We can now continue on dealing with the actual field.
  }

  if (
    transition.kind === 'DownCast'
    && transition.castedType.name === path.tail.type.name
  ) {
    // Due to output type covariance, a downcast supergraph transition may be a no-op on the
    // subgraph path. In these cases, we effectively ignore the type condition.
    return [path];
  }

  const options: GraphPath<Transition, V>[] = [];
  const deadEndClosures: UnadvanceableClosure[] = [];

  for (const edge of path.nextEdges()) {
    // The edge must match the transition. If it doesn't, we cannot use it.
    if (!edge.matchesSupergraphTransition(transition)) {
      continue;
    }

    if (
      edge.overrideCondition
      && !edge.satisfiesOverrideConditions(overrideConditions)
    ) {
      deadEndClosures.push(() => {
        return {
          destSubgraph: edge.tail.source,
          sourceSubgraph: edge.head.source,
          reason: UnadvanceableReason.UNSATISFIABLE_OVERRIDE_CONDITION,
          // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
          details: `Unable to take edge ${edge.toString()} because override condition "${edge.overrideCondition!.label}" is ${overrideConditions.get(edge.overrideCondition!.label)}`,
        };
      });
      continue;
    }

    // Additionally, we can only take an edge if we can satisfy its conditions.
    const conditionResolution = canSatisfyConditions(path, edge, conditionResolver, emptyContext, [], [], getFieldParentTypeForEdge);
    if (conditionResolution.satisfied) {
      options.push(path.add(transition, edge, conditionResolution));
    } else {
      deadEndClosures.push(() => {
        switch (edge.transition.kind) {
          case 'FieldCollection':
            {
              // Condition on a field means a @require
              const field = edge.transition.definition;
              const parentTypeInSubgraph = path.graph.sources.get(edge.head.source)!.type(field.parent.name)! as CompositeType;
              const details = conditionResolution.unsatisfiedConditionReason === UnsatisfiedConditionReason.NO_POST_REQUIRE_KEY
                ? `@require condition on field "${field.coordinate}" can be satisfied but missing usable key on "${parentTypeInSubgraph}" in subgraph "${edge.head.source}" to resume query`
                : conditionResolution.unsatisfiedConditionReason === UnsatisfiedConditionReason.NO_CONTEXT_SET
                ? `could not find a match for required context for field "${field.coordinate}"`
                // TODO: This isn't necessarily just because an @requires
                // condition was unsatisfied, but could also be because a
                // @fromContext condition was unsatisfied.
                : `cannot satisfy @require conditions on field "${field.coordinate}"${warnOnKeyFieldsMarkedExternal(parentTypeInSubgraph)}`;
              return {
                sourceSubgraph: edge.head.source,
                destSubgraph: edge.head.source,
                reason: UnadvanceableReason.UNSATISFIABLE_REQUIRES_CONDITION,
                details
              };
            }
          case 'InterfaceObjectFakeDownCast':
            {
              // The condition on such edge is only __typename, so it essentially means that an @interfaceObject exists but there is no reachable subgraph
              // with a @key on an interface to find out proper implementations.
              const details = conditionResolution.unsatisfiedConditionReason === UnsatisfiedConditionReason.NO_POST_REQUIRE_KEY
                ? `@interfaceObject type "${edge.transition.sourceType.coordinate}" misses a resolvable key to resume query once the implementation type has been resolved`
                : `no subgraph can be reached to resolve the implementation type of @interfaceObject type "${edge.transition.sourceType.coordinate}"`;
              return {
                sourceSubgraph: edge.head.source,
                destSubgraph: edge.head.source,
                reason: UnadvanceableReason.UNRESOLVABLE_INTERFACE_OBJECT,
                details
              };
            }
          default:
            assert(false, () => `Shouldn't have conditions on direct transition ${transition}`);
        }
      });
    }
  }
  if (options.length > 0) {
    return options;
  }

  return new UnadvanceableClosures(() => {
    const deadEnds = new UnadvanceableClosures(deadEndClosures).toUnadvanceables().reasons;
    if (deadEnds.length > 0) {
      return deadEnds;
    } else {
      let details: string;
      const subgraph = path.tail.source;
      if (transition.kind === 'FieldCollection') {
        const schema = path.graph.sources.get(subgraph)!;
        const fieldTypeName = transition.definition.parent.name;
        const typeInSubgraph = schema.type(fieldTypeName);
        if (!typeInSubgraph && path.tail.type.name !== fieldTypeName) {
          // This is due to us looking for an implementation field, but the subgraph not having that implementation because
          // it uses @interfaceObject on an interface of that implementation.
          details = `cannot find implementation type "${fieldTypeName}" (supergraph interface "${path.tail.type.name}" is declared with @interfaceObject in "${subgraph}")`;
        } else {
          const fieldInSubgraph = typeInSubgraph && isCompositeType(typeInSubgraph)
            ? typeInSubgraph.field(transition.definition.name)
            : undefined;
  
          if (fieldInSubgraph) {
            // the subgraph has the field but no corresponding edge. This should only happen if the field is external.
            const externalDirective = fieldInSubgraph.appliedDirectivesOf(federationMetadata(fieldInSubgraph.schema())!.externalDirective()).pop();
            assert(
              externalDirective,
              () => `${fieldInSubgraph.coordinate} in ${subgraph} is not external but there is no corresponding edge (edges from ${path} = [${path.nextEdges().join(', ')}])`
            );
            // but the field is external in the "subgraph-extracted-from-the-supergraph", but it might have been forced to an external
            // due to being a used-overriden field, in which case we want to amend the message to avoid confusing the user.
            // Note that the subgraph extraction marks such "forced external due to being overriden" by setting the "reason" to "[overridden]".
            const overriddingSources = externalDirective.arguments().reason === '[overridden]'
              ? findOverriddingSourcesIfOverridden(fieldInSubgraph, subgraph, path.graph.sources)
              : [];
            if (overriddingSources.length > 0) {
              details = `field "${transition.definition.coordinate}" is not resolvable because it is overridden by ${printSubgraphNames(overriddingSources)}`;
            } else {
              details = `field "${transition.definition.coordinate}" is not resolvable because marked @external`;
            }
          } else {
            details = `cannot find field "${transition.definition.coordinate}"`;
          }
        }
      } else {
        assert(transition.kind === 'DownCast', () => `Unhandled direct transition ${transition} of kind ${transition.kind}`);
        details = `cannot find type "${transition.castedType}"`;
      }
      return {
        sourceSubgraph: subgraph,
        destSubgraph: subgraph,
        reason: UnadvanceableReason.NO_MATCHING_TRANSITION,
        details
      };
    }
  });

}

function findOverriddingSourcesIfOverridden(
  field: FieldDefinition<CompositeType>,
  fieldSource: string,
  sources: ReadonlyMap<string, Schema>,
): string[] {
  return [...sources.entries()]
    .map(([name, schema]) => {
      if (name === FEDERATED_GRAPH_ROOT_SOURCE || name === fieldSource) {
        return undefined;
      }
      const sourceMetadata = federationMetadata(schema)!;
      const typeInSource = schema.type(field.parent.name);
      if (!typeInSource || !isObjectType(typeInSource)) {
        return undefined;
      }
      const fieldInSource = typeInSource.field(field.name);
      const isOverriddingSource = fieldInSource?.appliedDirectivesOf(sourceMetadata.overrideDirective())?.pop()?.arguments()?.from === fieldSource;
      return isOverriddingSource ? name : undefined;
    })
    .filter((name) => !!name) as string[];
}

function warnOnKeyFieldsMarkedExternal(type: CompositeType): string {
  // Because fed 1 used to (somewhat wrongly) require @external on key fields of type extension and because fed 2 allows you
  // to avoid type extensions, users upgrading might try to remove `extend` from their schema, but forgot to remove the @external
  // on their key field. The problem is that doing that make the key field truly external, and that could easily make @require
  // condition no satisfiable (because the key you'd need to get the require is now external). To help user locate that mistake
  // we add a specific pointer to this potential problem is the type is indeed an entity.
  const metadata = federationMetadata(type.schema());
  assert(metadata, "Type should originate from a federation subgraph schema");
  const keyDirective = metadata.keyDirective();
  const keys = type.appliedDirectivesOf(keyDirective);
  if (keys.length === 0) {
    return "";
  }
  const keyFieldMarkedExternal: string[] = [];
  for (const key of keys) {
    const fieldSet = parseFieldSetArgument({ parentType: type, directive: key });
    for (const selection of fieldSet.selections()) {
      if (selection.kind === 'FieldSelection' && selection.element.definition.hasAppliedDirective(metadata.externalDirective())) {
        const fieldName = selection.element.name;
        if (!keyFieldMarkedExternal.includes(fieldName)) {
          keyFieldMarkedExternal.push(fieldName);
        }
      }
    }
  }
  if (keyFieldMarkedExternal.length === 0) {
    return "";
  }
  const printedFields = keyFieldMarkedExternal.map(f => `"${f}"`).join(', ');
  const fieldWithPlural = keyFieldMarkedExternal.length === 1 ? 'field' : 'fields';
  return ` (please ensure that this is not due to key ${fieldWithPlural} ${printedFields} being accidentally marked @external)`;
}

export function getLocallySatisfiableKey(graph: QueryGraph, typeVertex: Vertex): SelectionSet | undefined  {
  const type = typeVertex.type as CompositeType;
  const schema = graph.sources.get(typeVertex.source);
  const metadata = schema ? federationMetadata(schema) : undefined;
  assert(metadata, () => `Could not find federation metadata for source ${typeVertex.source}`);
  const keyDirective = metadata.keyDirective();
  for (const key of type.appliedDirectivesOf(keyDirective)) {
    const selection = parseFieldSetArgument({ parentType: type, directive: key });
    if (!metadata.selectionSelectsAnyExternalField(selection)) {
      return selection;
    }
  }
  return undefined;
}

function canSatisfyConditions<TTrigger, V extends Vertex, TNullEdge extends null | never = never>(
  path: GraphPath<TTrigger, V, TNullEdge>,
  edge: Edge,
  conditionResolver: ConditionResolver,
  context: PathContext,
  excludedEdges: ExcludedDestinations,
  excludedConditions: ExcludedConditions,
  getFieldParentType: (trigger: TTrigger) => CompositeType | null,
): ConditionResolution {
  const { conditions, requiredContexts } = edge;
  if (!conditions && requiredContexts.length === 0) {
    return noConditionsResolution;
  }
  
  let totalCost = 0;
  const contextMap = new Map<string, ContextMapEntry>();
  
  if (requiredContexts.length > 0) {
    // if one of the conditions fails to satisfy, it's ok to bail
    let someSelectionUnsatisfied = false;
    for (const cxt of requiredContexts) {
      let levelsInQueryPath = 0;
      let levelsInDataPath = 0;
      for (const [e, trigger] of [...path].reverse()) {
        const parentType = getFieldParentType(trigger);
        levelsInQueryPath += 1;
        if (parentType) {
          levelsInDataPath += 1;
        }
        if (e !== null && !contextMap.has(cxt.namedParameter) && !someSelectionUnsatisfied) {
          const matches = Array.from(cxt.typesWithContextSet).some(t => {
            if (parentType) {
              const parentInSupergraph = path.graph.schema.type(parentType.name)!;
              if (parentInSupergraph.name === t) {
                return true;
              }
              if (isObjectType(parentInSupergraph) || isInterfaceType(parentInSupergraph)) {
                if (parentInSupergraph.interfaces().some(i => i.name === t)) {
                  return true;
                }
              }
              const tInSupergraph = parentInSupergraph.schema().type(t);
              if (tInSupergraph && isUnionType(tInSupergraph)) {
                return tInSupergraph.types().some(t => t.name === parentType.name);              
              }
            }
            return false;
          });
          if (parentType && matches) {
            const parentInSupergraph = path.graph.schema.type(parentType.name)!;
            assert(isCompositeType(parentInSupergraph), "Parent type should be composite type");
            let selectionSet = parseSelectionSet({ parentType: parentInSupergraph, source: cxt.selection });
            
            // We want to ignore type conditions that are impossible/don't intersect with the parent type
            selectionSet = selectionSet.lazyMap((selection): Selection | undefined => {
              if (selection.kind === 'FragmentSelection') {
                if (selection.element.typeCondition && isObjectType(selection.element.typeCondition)) {
                  if (!possibleRuntimeTypes(parentInSupergraph).includes(selection.element.typeCondition)) {
                    return undefined;
                  }
                }
              }
              return selection;
            })
            const resolution = conditionResolver(e, context, excludedEdges, excludedConditions, selectionSet);
            assert(edge.transition.kind === 'FieldCollection', () => `Expected edge to be a FieldCollection edge, got ${edge.transition.kind}`);
            
            const argIndices = path.graph.subgraphToArgIndices.get(cxt.subgraphName);
            assert(argIndices, () => `Expected to find arg indices for subgraph ${cxt.subgraphName}`);
            
            const id = argIndices.get(cxt.coordinate);
            assert(id !== undefined, () => `Expected to find arg index for ${cxt.coordinate}`);
            contextMap.set(cxt.namedParameter, { selectionSet, levelsInDataPath, levelsInQueryPath, inboundEdge: e, pathTree: resolution.pathTree, paramName: cxt.namedParameter, id, argType: cxt.argType });
            someSelectionUnsatisfied = someSelectionUnsatisfied || !resolution.satisfied;
            if (resolution.cost === -1 || totalCost === -1) {
              totalCost = -1;
            } else {
              totalCost += resolution.cost;            
            }
          }
        }
      }
    }
    
    if (requiredContexts.some(c => !contextMap.has(c.namedParameter))) {
      // in this case there is a context that is unsatisfied. Return no path.
      debug.groupEnd('@fromContext requires a context that is not set in graph path');
      return { ...unsatisfiedConditionsResolution, unsatisfiedConditionReason: UnsatisfiedConditionReason.NO_CONTEXT_SET };
    }
    
    if (someSelectionUnsatisfied) {
      debug.groupEnd('@fromContext selection set is unsatisfied');
      return { ...unsatisfiedConditionsResolution };
    }
    
    // it's possible that we will need to create a new fetch group at this point, in which case we'll need to collect the keys
    // to jump back to this object as a precondition for satisfying it.    
    debug.log('@fromContext conditions are satisfied, but validating post-context key.');
    const postContextKeyCondition = getLocallySatisfiableKey(path.graph, edge.head);
    if (!postContextKeyCondition) {
      debug.groupEnd('Post-context conditions cannot be satisfied');
      return { ...unsatisfiedConditionsResolution, unsatisfiedConditionReason: UnsatisfiedConditionReason.NO_POST_REQUIRE_KEY };
    }

    if (!conditions) {
      return { contextMap, cost: totalCost, satisfied: true };
    }
  }
  
  debug.group(() => `Checking conditions ${conditions} on edge ${edge}`);
  const resolution = conditionResolver(edge, context, excludedEdges, excludedConditions);
  if (!resolution.satisfied) {
    debug.groupEnd('Conditions are not satisfied');
    return unsatisfiedConditionsResolution;
  }
  const pathTree = resolution.pathTree;
  const lastEdge = path.lastEdge();
  if (edge.transition.kind === 'FieldCollection'
    && lastEdge !== null
    && lastEdge?.transition.kind !== 'KeyResolution'
    && (!pathTree || pathTree.isAllInSameSubgraph())) {

    debug.log('@requires conditions are satisfied, but validating post-require key.');
    const postRequireKeyCondition = getLocallySatisfiableKey(path.graph, edge.head);
    if (!postRequireKeyCondition) {
      debug.groupEnd('Post-require conditions cannot be satisfied');
      return { ...unsatisfiedConditionsResolution, unsatisfiedConditionReason: UnsatisfiedConditionReason.NO_POST_REQUIRE_KEY };
    }

    // We're in a case where we have a `@require` (we have a condition but we're a 'FieldCollection') and we
    // have to jump to other subgraph to satisfy the require, which means we need to use a key on "the current
    // subgraph" to resume collecting the field with the require. `getLocallySatisfiableKey` essentially tells
    // us that we have such key, and that's good enough here. Not that the way the code is organised, we don't
    // use an actual edge of the query graph, so we cannot use `conditionResolver` and so it's not easy to
    // get a proper cost or tree. That's ok in the sense that the cost of the key is negligible because we
    // know it's a "local" one (there is no subgraph jump) and the code to build plan will deal with adding
    // that key anyway (so not having the tree is ok).
    // TODO(Sylvain): the whole hanlding of @require is a bit too complex and hopefully we might be able to
    // clean that up, but it's unclear to me how at the moment and it may not be a small change so this will
    // have to do for now.
  }

  debug.groupEnd('Conditions satisfied');
  return { ...resolution, contextMap, cost: totalCost + resolution.cost };
}

function isTerminalOperation(operation: OperationElement): boolean {
  return operation.kind === 'Field' && isLeafType(baseType(operation.definition.type!));
}

export type SimultaneousPaths<V extends Vertex = Vertex> = OpGraphPath<V>[];

type OpIndirectPaths<V extends Vertex> = IndirectPaths<OpTrigger, V, null, never>;

/**
 * Memoize the computation of indirect paths, like `TransitionPathWithLazyIndirectPaths` does, but for query planning.
 *
 * Here again, this is an optimization that avoids computing indirect paths eagerly (since we may not need them) but
  * ensures we don't re-do their computation multiple times when we do need them multiple times.
 */
export class SimultaneousPathsWithLazyIndirectPaths<V extends Vertex = Vertex> {
  private lazilyComputedIndirectPaths: OpIndirectPaths<V>[];

  constructor(
    readonly paths: SimultaneousPaths<V>,
    readonly context: PathContext,
    readonly conditionResolver: ConditionResolver,
    readonly excludedNonCollectingEdges: ExcludedDestinations = [],
    readonly excludedConditionsOnNonCollectingEdges: ExcludedConditions = [],
    readonly overrideConditions: Map<string, boolean>,
  ) {
    this.lazilyComputedIndirectPaths = new Array(paths.length);
  }

  // For a given "input" path (identified by an idx in `paths`), each of its indirect options.
  indirectOptions(updatedContext: PathContext, pathIdx: number): OpIndirectPaths<V> {
    // Note that the provided context will usually be one we had during construction (the `updatedContext` will be `this.context` updated
    // by whichever operation we're looking at, but only operation with a @skip/@include will change the context so it's pretty rare),
    // which is why we save recomputation by caching the computed value in that case, but in case it's different, we compute without caching.
    if (updatedContext !== this.context) {
      return this.computeIndirectPaths(pathIdx);
    }
    if (!this.lazilyComputedIndirectPaths[pathIdx]) {
      this.lazilyComputedIndirectPaths[pathIdx] = this.computeIndirectPaths(pathIdx);
    }
    return this.lazilyComputedIndirectPaths[pathIdx];
  }

  private computeIndirectPaths(idx: number): OpIndirectPaths<V>  {
    return advancePathWithNonCollectingAndTypePreservingTransitions(
      this.paths[idx],
      this.context,
      this.conditionResolver,
      this.excludedNonCollectingEdges,
      this.excludedConditionsOnNonCollectingEdges,
      // the transitions taken by this function are non collecting transitions, and we ship the context as trigger (a slight hack admittedly,
      // but as we'll need the context handy for keys ...).
      (_t, context) => context,
      opPathTriggerToEdge,
      this.overrideConditions,
      getFieldParentTypeForOpTrigger,
    );
  }

  toString(): string {
    return simultaneousPathsToString(this.paths);
  }
}

export function simultaneousPathsToString(simultaneousPaths: SimultaneousPaths<any> | SimultaneousPathsWithLazyIndirectPaths<any>, indentOnNewLine: string=""): string {
  const paths = Array.isArray(simultaneousPaths) ? simultaneousPaths : simultaneousPaths.paths;
  if (paths.length === 0) {
    return '<no path>';
  }
  if (paths.length === 1) {
    return paths[0].toString();
  }
  return `{\n${indentOnNewLine}  ` + paths.join(`\n${indentOnNewLine}  `) + `\n${indentOnNewLine}}`;
}

export function advanceOptionsToString(options: (SimultaneousPaths<any> | SimultaneousPathsWithLazyIndirectPaths<any> | GraphPath<any>)[] | undefined): string {
  if (!options) {
    return '<no options>';
  }
  if (options.length === 0) {
    return '<unsatisfiable branch>';
  }
  if (options.length === 1) {
    return '[' + options[0] + ']';
  }
  return '[\n  ' + options.map(opt => Array.isArray(opt) ? simultaneousPathsToString(opt, "  ") : opt.toString()).join('\n  ') + '\n]';
}

// Given a list of just computed indirect paths and a field that we're trying to advance after those paths, this
// method fields any path that should note be considered.
//
// Currently, this handle the case where the key used at the end of the indirect path contains (at top level) the field
// being queried. Or to make this more concrete, if we're trying to collect field `id`, and the path last edge was using
// key `id`, then we can ignore that path because this imply that there is a way to `id` "some other way" (also see
// the `does not evaluate plans relying on a key field to fetch that same field` test in `buildPlan` for more details).
function filterNonCollectingPathsForField<V extends Vertex>(
  paths: OpIndirectPaths<V>,
  field: Field,
): OpIndirectPaths<V> {
  // We only handle leafs. Things are more complex non-leaf.
  if (!field.isLeafField()) {
    return paths;
  }

  const filtered = paths.paths.filter((p) => {
    const lastEdge = p.lastEdge();
    if (!lastEdge || lastEdge.transition.kind !== 'KeyResolution') {
      return true;
    }

    const conditions = lastEdge.conditions;
    return !(conditions && conditions.containsTopLevelField(field));
  });
  return filtered.length === paths.paths.length
    ? paths
    : {
      ...paths,
      paths: filtered
    };

}

// Returns undefined if the operation cannot be dealt with/advanced. Otherwise, it returns a list of options we can be in after advancing the operation, each option
// being a set of simultaneous paths in the subgraphs (a single path in the simple case, but type exploding may make us explore multiple paths simultaneously).
// The lists of options can be empty, which has the special meaning that the operation is guaranteed to have no results (it corresponds to unsatisfiable conditions),
// meaning that as far as query planning goes, we can just ignore the operation but otherwise continue.
export function advanceSimultaneousPathsWithOperation<V extends Vertex>(
  supergraphSchema: Schema,
  subgraphSimultaneousPaths: SimultaneousPathsWithLazyIndirectPaths<V>,
  operation: OperationElement,
  overrideConditions: Map<string, boolean>,
) : SimultaneousPathsWithLazyIndirectPaths<V>[] | undefined {
  debug.group(() => `Trying to advance ${simultaneousPathsToString(subgraphSimultaneousPaths)} for ${operation}`);
  const updatedContext = subgraphSimultaneousPaths.context.withContextOf(operation);
  const optionsForEachPath: SimultaneousPaths<V>[][] = [];
  for (const [i, path] of subgraphSimultaneousPaths.paths.entries()) {
    let options: SimultaneousPaths<V>[] | undefined = undefined;

    debug.group(() => `Computing options for ${path}`);
    const shouldReenterSubgraph = path.deferOnTail && operation.kind === 'Field';
    // If we're just entering a deferred section, then we will need to re-enter subgraphs, so we should not consider
    // direct options and instead force an indirect path.
    if (!shouldReenterSubgraph) {
      debug.group(() => `Direct options`);
      const { options: advanceOptions, hasOnlyTypeExplodedResults } = advanceWithOperation(
        supergraphSchema,
        path,
        operation,
        updatedContext,
        subgraphSimultaneousPaths.conditionResolver,
        overrideConditions,
      );
      options = advanceOptions;
      debug.groupEnd(() => advanceOptionsToString(options));
      // If we got some options, there is number of cases where there is no point looking for indirect paths:
      // - if the operation is terminal: this mean we just found a direct edge that is terminal, so no
      //   indirect options could be better (this is no true for non-terminal where the direct route may
      //   end up being a dead end later). One exception however is when `advanceWithOperation` type-exploded (meaning
      //   that're on an interface), because in that case, the type-exploded options have already taken indirect edges
      //   into account, so it's possible that an indirect edge _from the interface_ could be better, but only if
      //   there wasn't a "true" direct edge on the interface, which is what `hasOnlyTypeExplodedResults` tells us.
      // - if we get options, but an empty set of them, which signifies the operation correspond to unsatisfiable
      //   conditions and we can essentially ignore it.
      // - if the operation is a fragment in general: if we were able to find a direct option, that means the type
      //   is known in the "current" subgraph, and so we'll still be able to take any indirect edges that we could
      //   take now later, for the follow-up operation. And pushing the decision will give us more context and may
      //   avoid a bunch of state explosion in practice.
      if (options && (options.length === 0 || (isTerminalOperation(operation) && !hasOnlyTypeExplodedResults) || operation.kind === 'FragmentElement')) {
        debug.groupEnd(() => `Final options for ${path}: ${advanceOptionsToString(options)}`);
        // Note that options is empty, that means this particular "branch" is unsatisfiable, so we should just ignore it.
        if (options.length > 0) {
          optionsForEachPath.push(options);
        }
        continue;
      }
    }

    // If there was not valid direct path (or we didn't check those because we enter a defer), that's ok, we'll just try with non-collecting edges.
    options = options ?? [];
    if (operation.kind === 'Field') {
      debug.group(`Computing indirect paths:`);
      // Then adds whatever options can be obtained by taking some non-collecting edges first.
      const pathsWithNonCollecting = filterNonCollectingPathsForField(
        subgraphSimultaneousPaths.indirectOptions(updatedContext, i),
        operation
      );
      debug.groupEnd(() => pathsWithNonCollecting.paths.length == 0 ? `no indirect paths` : `${pathsWithNonCollecting.paths.length} indirect paths`);
      if (pathsWithNonCollecting.paths.length > 0) {
        debug.group('Validating indirect options:');
        for (const pathWithNonCollecting of pathsWithNonCollecting.paths) {
          debug.group(() => `For indirect path ${pathWithNonCollecting}:`);
          const { options: pathWithOperation } = advanceWithOperation(
            supergraphSchema,
            pathWithNonCollecting,
            operation,
            updatedContext,
            subgraphSimultaneousPaths.conditionResolver,
            overrideConditions,
          );
          // If we can't advance the operation after that path, ignore it, it's just not an option.
          if (!pathWithOperation) {
            debug.groupEnd(() => `Ignoring: cannot be advanced with ${operation}`);
            continue;
          }
          debug.groupEnd(() => `Adding valid option: ${pathWithOperation}`);
          // advancedWithOperation can return an empty list only if the operation if a fragment with a condition that, on top of the "current" type
          // is unsatisfiable. But as we've only taken type preserving transitions, we cannot get an empty results at this point if we haven't
          // had one when testing direct transitions above (in which case we have exited the method early).
          assert(pathWithOperation.length > 0, () => `Unexpected empty options after non-collecting path ${pathWithNonCollecting} for ${operation}`);

          // There is a special case we can deal with now. Namely, suppose we have a case where a query
          // is reaching an interface I in a subgraph S1, we query some field of that interface x, and
          // say that x is provided in subgraph S2 but by an @interfaceObject for I.
          // As we look for direct options for I.x in S1 initially, as we didn't found `x`, we will have tried
          // to type-explode I (in say implementation A and B). And in some case doing so is necessary, but
          // it may also lead for the type-exploding option to look like:
          //  [
          //    I(S1) -[... on A]-> A(S1) -[key]-> I(S2) -[x] -> Int(S2),
          //    I(S1) -[... on B]-> B(S1) -[key]-> I(S2) -[x] -> Int(S2),
          //  ]
          // But as we look at indirect option now (still from I in S1), we will note that we can also
          // do:
          //    I(S1) -[key]-> I(S2) -[x] -> Int(S2),
          // And while both options are technically valid, the new one really subsume the first one: there
          // is no point in type-exploding to take a key to the same exact subgraph if using the key
          // on the interface directly works.
          //
          // So here, we look for that case and remove any type-exploding option that the new path
          // render unecessary.
          // Do note that we only make that check when the new option is a single-path option, because
          // this gets kind of complicated otherwise.
          if (pathWithNonCollecting.tailIsInterfaceObject()) {
            for (const indirectOption of pathWithOperation) {
              if (indirectOption.length === 1) {
                options = options.filter((opt) => !opt.every((p) => indirectOption[0].isEquivalentSaveForTypeExplosionTo(p)));
              }
            }
          }
          options = options.concat(pathWithOperation);
        }
        debug.groupEnd();
      }
    }

    // If we were entering a @defer, we've skipped the potential "direct" options because we need an "indirect" one (a key/root query)
    // to be able to actualy defer. But in rare cases, it's possible we actually couldn't resolve the key fields needed to take a key
    // but could still find a direct path. If so, it means it's a corner case where we cannot do query-planner-based-@defer and have
    // to fall back on not deferring.
    if (options.length === 0 && shouldReenterSubgraph) {
      debug.group(() => `Cannot defer (no indirect options); falling back to direct options`);
      const { options: advanceOptions } = advanceWithOperation(
        supergraphSchema,
        path,
        operation,
        updatedContext,
        subgraphSimultaneousPaths.conditionResolver,
        overrideConditions,
      );
      options = advanceOptions ?? [];
      debug.groupEnd(() => advanceOptionsToString(options));
    }

    // At this point, if options is empty, it means we found no ways to advance the operation for this path, so we should return undefined.
    if (options.length === 0) {
      debug.groupEnd(); // end of this input path
      debug.groupEnd(() => `No valid options for ${operation}, aborting operation ${operation}`);
      return undefined;
    } else {
      debug.groupEnd(() => advanceOptionsToString(options));
      optionsForEachPath.push(options);
    }
  }

  const allOptions: SimultaneousPaths<V>[] = flatCartesianProduct(optionsForEachPath);
  debug.groupEnd(() => advanceOptionsToString(allOptions));
  return createLazyOptions(
    allOptions,
    subgraphSimultaneousPaths,
    updatedContext,
    subgraphSimultaneousPaths.overrideConditions,
  );
}


export function createInitialOptions<V extends Vertex>(
  initialPath: OpGraphPath<V>,
  initialContext: PathContext,
  conditionResolver: ConditionResolver,
  excludedEdges: ExcludedDestinations,
  excludedConditions: ExcludedConditions,
  overrideConditions: Map<string, boolean>,
  initialSubgraphConstraint: string | null,
): SimultaneousPathsWithLazyIndirectPaths<V>[] {
  const lazyInitialPath = new SimultaneousPathsWithLazyIndirectPaths(
    [initialPath],
    initialContext,
    conditionResolver,
    excludedEdges,
    excludedConditions,
    overrideConditions,
  );
  if (isFederatedGraphRootType(initialPath.tail.type)) {
    let initialOptions = lazyInitialPath.indirectOptions(initialContext, 0);
    if (initialSubgraphConstraint !== null) {
      initialOptions.paths = initialOptions
        .paths
        .filter((path) => path.tail.source === initialSubgraphConstraint);
    }
    return createLazyOptions(initialOptions.paths.map(p => [p]), lazyInitialPath, initialContext, overrideConditions);
  } else {
    return [lazyInitialPath];
  }
}

function createLazyOptions<V extends Vertex>(
  options: SimultaneousPaths<V>[],
  origin: SimultaneousPathsWithLazyIndirectPaths<V>,
  context: PathContext,
  overrideConditions: Map<string, boolean>,
) : SimultaneousPathsWithLazyIndirectPaths<V>[] {
  return options.map(option => new SimultaneousPathsWithLazyIndirectPaths(
    option,
    context,
    origin.conditionResolver,
    origin.excludedNonCollectingEdges,
    origin.excludedConditionsOnNonCollectingEdges,
    overrideConditions,
  ));
}

function opPathTriggerToEdge(graph: QueryGraph, vertex: Vertex, trigger: OpTrigger, overrideConditions: Map<string, boolean>): Edge | null | undefined {
  if (trigger instanceof PathContext) {
    return undefined;
  }
  if (trigger.kind === 'Field') {
    return edgeForField(graph, vertex, trigger, overrideConditions);
  } else {
    return trigger.typeCondition ? edgeForTypeCast(graph, vertex, trigger.typeCondition.name) : null;
  }
}

// This can be written more tersely with a bunch of reduce/flatMap and friends, but when interfaces type-explode into many
// implementations, this can end up with fairly large arrays and be a bottleneck, and a more iterative version that pre-allocate
// arrays is quite a bit faster.
function flatCartesianProduct<V>(arr:V[][][]): V[][] {
  const size = arr.length;
  if (size === 0) {
    return [];
  }

  // Track, for each element, at which index we are
  const eltIndexes = new Array<number>(size);
  let totalCombinations = 1;
  for (let i = 0; i < size; ++i){
    const eltSize = arr[i].length;
    if(!eltSize) {
      totalCombinations = 0;
      break;
    }
    eltIndexes[i] = 0;
    totalCombinations *= eltSize;
  }

  const product = new Array<V[]>(totalCombinations);
  for (let i = 0; i < totalCombinations; ++i){
    let itemSize = 0;
    for (let j = 0; j < size; ++j) {
      itemSize += arr[j][eltIndexes[j]].length;
    }
    const item = new Array<V>(itemSize);
    let k = 0;
    for (let j = 0; j < size; ++j) {
      for (const v of arr[j][eltIndexes[j]]) {
        item[k++] = v;
      }
    }
    product[i] = item;

    for (let idx = 0; idx < size; ++idx) {
      if (eltIndexes[idx] == arr[idx].length - 1) {
        eltIndexes[idx] = 0;
      } else {
        eltIndexes[idx] += 1;
        break;
      }
    }
  }
  return product;
}

function anImplementationHasAProvides(fieldName: string, itf: InterfaceType): boolean {
  const metadata = federationMetadata(itf.schema());
  assert(metadata, "Interface should have come from a federation subgraph");
  for (const implem of itf.possibleRuntimeTypes()) {
    const field = implem.field(fieldName);
    // Note that this should only be called if field exists, but no reason to fail otherwise.
    if (field && field.hasAppliedDirective(metadata.providesDirective())) {
      return true;
    }
  }
  return false;
}

/*
 * This method is used to detect the case where using an interface field "directly" could fail (lead to a dead end later for the quer path)
 * _while_ type-exploding may succeed.
 *
 * In general, taking a field from an interface directly or through it's implementation by type-exploding leads to the same option, and so
 * taking one or the other is more of a matter of "which is more efficient". But there is a special case where this may not be the case,
 * and this is:
 *  1. when the interface is implemented by an entity type.
 *  2. the field being looked at is @shareable.
 *  3. the field type has a different set of fields (and less fields) in the "current" subgraph than in another one.
 *
 * Consider for instance:
 * ```
 *   # Subgraph A
 *   type Query {
 *     i: I
 *   }
  *
 *   interface I {
 *     s: S
 *   }
 *
 *   type T implements I @key(fields: "id") {
 *     id: ID!
 *     s: S @shareable
 *   }
 *
 *   type S @shareable {
 *     x: Int
 *   }
 * ```
 * ```
 *   # Subgraph B
 *   type T @key(fields: "id") {
 *     id: ID!
 *     s: S @shareable
 *   }
 *
 *   type S @shareable {
 *     x: Int
 *     y: Int
 *   }
 * ```
 * and suppose that `{ i { s { y } } }` is queried. If we follow `I.s` in subgraph A, then the `y` field
 * cannot be found, because `S` is not an entity (not that it could also be an entity but not have a usable
 * key between the 2 subgraphs) and so we cannot "jump" to subgraph B. However, if we "type-explode" into
 * implementation `T`, then we can jump to subgraph B from that, at which point we can reach `y`.
 *
 * So the goal of this method is to detect when we might be in such a case: when we are, we will have to
 * consider type-explosion on top of the direct route in case that direct route ends up "not panning out"
 * (note that by the time this method is called, we're only looking at the options for type `I.s`; we
 * do not know yet if `y` is queried next and so cannot tell if type-explosion will be necessary or not).
 */
function anImplementationIsEntityWithFieldShareable<V extends Vertex>(path: OpGraphPath<V>, fieldName: string, itf: InterfaceType): boolean {
  const metadata = federationMetadata(itf.schema());
  assert(metadata, "Interface should have come from a federation subgraph");
  for (const implem of itf.possibleRuntimeTypes()) {
    if (!implem.hasAppliedDirective(metadata.keyDirective())) {
      continue;
    }
    const field = implem.field(fieldName);
    // Note that this should only be called if field exists, but no reason to fail otherwise.
    if (!field || !field.hasAppliedDirective(metadata.shareableDirective())) {
      continue;
    }

    // Returning `true` for this method has a cost: it will make us consider type-explosion for `itf`, and this can
    // sometime lead to a large number of additional path to explore, which can have a substantial cost. So we want
    // to limit it if we can avoid it. As it happens, we should return `true` if it is possible that "something"
    // (some field) in the type of `field` is reachable in _another_ subgraph but no in the one of the current path.
    // And while it's not trivial to check this in general, there is some easy case we can elimiate. For instance,
    // if the type in the current subgraph has only leaf fields, we can check that all other subgraphs reachable
    // from the implementation have the same set of leafs.
    const type = baseType(field.type!);
    if (isLeafType(type)) {
      continue;
    }
    if (isObjectType(type) && type.fields().every((f) => isLeafType(baseType(f.type!)))) {
      const fieldNames = new Set(type.fields().map((f) => f.name));
      for (const v of path.graph.verticesForType(implem.name)) {
        if (v.source === path.tail.source) {
          continue;
        }
        const otherMetadata = federationMetadata(v.type.schema());
        assert(otherMetadata, "Type should have come from a federation subgraph");
        assert(isObjectType(v.type) || isInterfaceType(v.type), () => `${implem} is an object in ${path.tail.source} but a ${v.type.kind} in ${v.source}`);
        const fieldInOther = v.type.field(fieldName);
        if (!fieldInOther || !fieldInOther.hasAppliedDirective(otherMetadata.shareableDirective())) {
          // The shareable field is actually not shared here (it's either not declared, or external), so we can ignore that subgraph.
          continue;
        }
        const typeInOther = baseType(fieldInOther.type!);
        if (typeInOther.name !== type.name || !(isObjectType(typeInOther) || isInterfaceType(typeInOther))) {
          // We have a genuine difference here, so we should explore type explosion.
          return true;
        }
        const otherNames = new Set(typeInOther.fields().map((f) => f.name));
        if (!isSubset(fieldNames, otherNames)) {
          // Same, we have a genuine difference.
          return true;
        }
        // Note that if the type is the same and the fields too, then we know the type of those fields must be leaf type,
        // or merging would have complained.
      }
      // So every other instance of the type
      return false;
    }
    // Alright, we officially "don't know", so we return "true" so type-explosion is tested.
    return true;
  }
  return false;
}

function isProvidedEdge(edge: Edge): boolean {
  return edge.transition.kind === 'FieldCollection' && edge.transition.isPartOfProvide;
}

// The result has the same meaning than in advanceSimultaneousPathsWithOperation.
// We also actually need to return a set of options of simultaneous paths. Cause when we type explode, we create simultaneous paths, but
// as a field might be resolve by multiple subgraphs, we may have options created.
function advanceWithOperation<V extends Vertex>(
  supergraphSchema: Schema,
  path: OpGraphPath<V>,
  operation: OperationElement,
  context: PathContext,
  conditionResolver: ConditionResolver,
  overrideConditions: Map<string, boolean>,
) : {
  options: SimultaneousPaths<V>[] | undefined,
  hasOnlyTypeExplodedResults?: boolean,
} {
  debug.group(() => `Trying to advance ${path} directly with ${operation}`);

  const currentType = path.tail.type;
  if (isFederatedGraphRootType(currentType)) {
    // We cannot advance any operation from there: we need to take the initial non-collecting edges first.
    debug.groupEnd('Cannot advance federated graph root with direct operations');
    return { options: undefined };
  }

  if (operation.kind === 'Field') {
    const field = operation.definition;
    switch (currentType.kind) {
      case 'ObjectType':
        // Just take the edge corresponding to the field, if it exists and can be used.
        const edge = nextEdgeForField(path, operation, overrideConditions);
        if (!edge) {
          debug.groupEnd(() => `No edge for field ${field} on object type ${currentType}`);
          return { options: undefined };
        }

        // If the current type is an @interfaceObject, it's possible that the requested field
        // is a field of an implementation of the interface. Because we found an edge, we
        // know that the interface has the field and we can use the edge, but we should redact
        // the `operation` to use the current type field, so the operation does not continue
        // referring to a type that is not in the current subgraph.
        if (path.tailIsInterfaceObject() && field.parent.name !== currentType.name) {
          const fieldOnCurrentType = currentType.field(field.name);
          assert(fieldOnCurrentType, () => `We should not have found edge ${edge} for ${field} from ${path}`)
          operation = operation.withUpdatedDefinition(fieldOnCurrentType);
        }

        const fieldPath = addFieldEdge(path, operation, edge, conditionResolver, context);
        debug.groupEnd(() => fieldPath
          ? `Collected field ${field} on object type ${currentType}`
          : `Cannot satisfy @requires on field ${field} for object type ${currentType}`
        );
        return { options: pathAsOptions(fieldPath) };
      case 'InterfaceType':
        // Due to @interfaceObject, we could be in a case where the field asked is not on the interface but
        // rather on one of it's implementation. This can happen if we just entered the subgraph on an interface @key
        // and coming from an @interfaceObject. In that case, we'll skip checking for an interface direct edge and
        // simply cast into that implementation below.
        const fieldIsOfAnImplementation = field.parent.name !== currentType.name;

        // First, we check if there is a direct edge from the interface (which only happens if we're in a subgraph that knows all of the
        // implementations of that interface globally and all of them resolve the field).
        // If there is one, then we have 2 options:
        //  - either we take that edge,
        //  - or we type-explode (like when we don't have a direct interface edge).
        // We want to avoid looking at both options if we can avoid it because it multiplies planning work quickly if
        // we always check both options. And in general, taking the interface edge is better than type explosion "if it works",
        // so we distinguish a number of cases where we know that:
        // - either type-exploding cannot work unless taking the interface edge also do (the `anImplementationIsEntityWithFieldShareable`)
        // - or that type-exploding cannot be more efficient than the direct path (when no @provides are involved; if a provide is involved
        //   in one of the implementation, then type-exploding may lead to a shorter overall plan thanks to that @provides)
        const itfEdge = fieldIsOfAnImplementation ? undefined : nextEdgeForField(path, operation, overrideConditions);
        let itfPath: OpGraphPath<V> | undefined = undefined;
        let directPathOverrideTypeExplosion = false;
        if (itfEdge) {
          itfPath = addFieldEdge(path, operation, itfEdge, conditionResolver, context);
          assert(itfPath, () => `Interface edge ${itfEdge} shouldn't have conditions`);
          // There is 2 separate case where we going to do _both_ "direct" and "type-exploding" options:
          // 1. if there is a @provides: in that case the "type-exploding" case can legit be more efficient and we want to
          //   consider it "all the way"
          // 2. in the sub-case of `!anImplementationIsEntityWithFieldShareable(...)`, where we want to have the type-exploding
          //   option only for the case where the "direct" one fails later. But in that case, we'll remember that if the direct
          //   option pan out, then we can ignore the type-exploding one.
          // `directPathOverrideTypeExplosion` indicates that we're in the 2nd case above, not the 1st one.
          directPathOverrideTypeExplosion =
            field.name === typenameFieldName
            || (!isProvidedEdge(itfEdge) && !anImplementationHasAProvides(field.name, currentType));
          // We can special case terminal (leaf) fields: as long they have no @provides, then the path ends there and there is no need
          // to check type explosion "in case the direct path don't pan out". Additionally, if we're not in the case where an implementation
          // is an entity and the field is shareable, then there is no case where the direct case wouldn't "pan out" but the type-explosion
          // would, so we can ignore type-exploding there too.
          // TODO: We should re-assess this when we support @requires on interface fields (typically, should we even try to type-explode
          // if the direct edge cannot be satisfied? Probably depends on the exact semantic of @requires on interface fields).
          if (directPathOverrideTypeExplosion && (isLeafType(field.type!) || !anImplementationIsEntityWithFieldShareable(path, field.name, currentType))) {
            debug.groupEnd(() => `Collecting (leaf) field ${field} on interface ${currentType} without type-exploding`);
            return { options: pathAsOptions(itfPath) };
          }
          debug.log(() => `Collecting field ${field} on interface ${currentType} as 1st option`);
        }

        // There is 2 main cases to handle here:
        // - the most common is that it's a field of the interface that is queried, and
        //   so we should type-explode because either didn't had a direct edge, or @provides
        //   makes it potentially worthwhile to check with type explosion.
        // - but, as mentioned earlier, we could be in the case where the field queried is actually of one
        //   of the implementation of the interface. In that case, we only want to consider that one
        //   implementation.
        let implementations: readonly ObjectType[];
        if (fieldIsOfAnImplementation) {
          assert(
            isObjectType(field.parent) && path.tailPossibleRuntimeTypes().some((t) => t.name === field.parent.name),
            () => `${field.coordinate} requested on ${currentType}, but ${field.parent} is not an implementation`
          );
          implementations = [ field.parent ];
          debug.log(() => `Casting into requested type ${field.parent}`);
        } else {
          implementations = path.tailPossibleRuntimeTypes();
          debug.log(() => !itfPath
            ? `No direct edge: type exploding interface ${currentType} into possible runtime types [${implementations.join(', ')}]`
            : `Type exploding interface ${currentType} into possible runtime types [${implementations.join(', ')}] as 2nd option`
          );
        }

        // For all implementations, We need to call advanceSimultaneousPathsWithOperation on a made-up Fragment. If any
        // gives use empty options, we bail.
        const optionsByImplems: OpGraphPath<V>[][][] = [];
        for (const implemType of implementations) {
          const castOp = new FragmentElement(currentType, implemType.name);
          debug.group(() => `Handling implementation ${implemType}`);
          const implemOptions = advanceSimultaneousPathsWithOperation(
            supergraphSchema,
            new SimultaneousPathsWithLazyIndirectPaths([path], context, conditionResolver, [], [], overrideConditions),
            castOp,
            overrideConditions,
          );
          // If we find no option for that implementation, we bail (as we need to simultaneously advance all implementations).
          if (!implemOptions) {
            debug.groupEnd();
            debug.groupEnd(() => `Cannot collect field ${field} from ${implemType}: stopping with options [${itfPath}]`);
            return { options: pathAsOptions(itfPath) };
          }
          // If the new fragment makes it so that we're on an unsatisfiable branch, we just ignore that implementation.
          if (implemOptions.length === 0) {
            debug.groupEnd(() => `Cannot ever get ${implemType} from this branch, ignoring it`);
            continue;
          }
          // For each option, we call advanceSimultaneousPathsWithOperation again on our own operation (the field),
          // which gives us some options (or not and we bail).
          let withField: SimultaneousPaths<V>[] = [];
          debug.log(() => `Trying to collect ${field} from options ${advanceOptionsToString(implemOptions)}`);
          for (const optPaths of implemOptions) {
            debug.group(() => `For ${simultaneousPathsToString(optPaths)}`);
            const withFieldOptions = advanceSimultaneousPathsWithOperation(
              supergraphSchema,
              optPaths,
              operation,
              overrideConditions,
            );
            if (!withFieldOptions) {
              debug.groupEnd(() => `Cannot collect ${field}`);
              continue;
            }
            // Advancing a field should never get us into an unsatisfiable condition. Only fragments can.
            assert(withFieldOptions.length > 0, () => `Unexpected unsatisfiable path after ${optPaths} for ${operation}`);
            debug.groupEnd(() => `Collected field ${field}: adding ${advanceOptionsToString(withFieldOptions)}`);
            withField = withField.concat(withFieldOptions.map(opt => opt.paths));
          }
          // If we find no option to advance that implementation, we bail (as we need to simultaneously advance all implementations).
          if (withField.length === 0) {
            debug.groupEnd(); // implem group
            debug.groupEnd(() => `Cannot collect field ${field} from ${implemType}: stopping with options [${itfPath}]`);
            return { options: pathAsOptions(itfPath) };
          }
          debug.groupEnd(() => `Collected field ${field} from ${implemType}`);
          optionsByImplems.push(withField);
        }
        let allOptions = flatCartesianProduct(optionsByImplems);
        if (itfPath) {
          if (directPathOverrideTypeExplosion) {
            ({ thisPath: itfPath, otherOptions: allOptions } = itfPath.markOverridding(allOptions));
          }
          allOptions = pathAsOptions(itfPath)!.concat(allOptions);
        }
        debug.groupEnd(() => `With type-exploded options: ${advanceOptionsToString(allOptions)}`);
        return { options: allOptions, hasOnlyTypeExplodedResults: !itfPath };
      case 'UnionType':
        assert(field.name === typenameFieldName, () => `Invalid field selection ${operation} for union type ${currentType}`);
        const typenameEdge = nextEdgeForField(path, operation, overrideConditions);
        assert(typenameEdge, `Should always have an edge for __typename edge on an union`);
        debug.groupEnd(() => `Trivial collection of __typename for union ${currentType}`);
        return { options: pathAsOptions(addFieldEdge(path, operation, typenameEdge, conditionResolver, context)) };
      default:
        // Only object, interfaces and unions (only for __typename) have fields so the query should have been flagged invalid if a field was selected on something else.
        assert(false, `Unexpected ${currentType.kind} type ${currentType} from ${path.tail} given operation ${operation}`);
    }
  } else {
    assert(operation.kind === 'FragmentElement', () => "Unhandled operation kind: " + operation.kind);
    if (!operation.typeCondition || currentType.name === operation.typeCondition.name) {
      // If there is no typename (or the condition is the type we're already one), it means we're essentially
      // just applying some directives (could be a @skip/@include for instance). This doesn't make us take any
      // edge but if operation does have directives, we record it.
      debug.groupEnd(() => `No edge to take for condition ${operation} from current type ${currentType}`);
      const updatedPath = operation.appliedDirectives.length > 0
        ? path.add(operation, null, noConditionsResolution, operation.deferDirectiveArgs())
        : path;
      return { options: [[ updatedPath ]] };
    }
    const typeName = operation.typeCondition.name;
    switch (currentType.kind) {
      case 'InterfaceType':
      case 'UnionType':
        // If we have an edge for the type case, take that.
        const edge = nextEdgeForTypeCast(path, typeName);
        if (edge) {
          assert(!edge.conditions, "TypeCast collecting edges shouldn't have conditions");
          debug.groupEnd(() => `Using type-casting edge for ${typeName} from current type ${currentType}`);
          return { options: [[path.add(operation, edge, noConditionsResolution, operation.deferDirectiveArgs())]] };
        }
        // Otherwise, checks what is the intersection between the possible runtime types of the current type
        // and the ones of the cast. We need to be able to go into all those types simultaneously.
        const parentTypes = path.tailPossibleRuntimeTypes() ;
        const castedTypes = possibleRuntimeTypes(supergraphSchema.type(typeName) as CompositeType);
        const intersection = parentTypes.filter(t1 => castedTypes.some(t2 => t1.name === t2.name)).map(t => t.name);
        debug.log(() => `Trying to type-explode into intersection between ${currentType} and ${typeName} = [${intersection}]`);
        const optionsByImplems: OpGraphPath<V>[][][] = [];
        for (const tName of intersection) {
          debug.group(() => `Trying ${tName}`);
          const castOp = new FragmentElement(currentType, tName, operation.appliedDirectives);
          const implemOptions = advanceSimultaneousPathsWithOperation(
            supergraphSchema,
            new SimultaneousPathsWithLazyIndirectPaths([path], context, conditionResolver, [], [], overrideConditions),
            castOp,
            overrideConditions,
          );
          if (!implemOptions) {
            debug.groupEnd();
            debug.groupEnd(() => `Cannot advance into ${tName} from ${currentType}: no options for ${operation}.`);
            return { options: undefined };
          }
          // If the new fragment makes it so that we're on an unsatisfiable branch, we just ignore that implementation.
          if (implemOptions.length === 0) {
            debug.groupEnd(() => `Cannot ever get ${tName} from this branch, ignoring it`);
            continue;
          }
          debug.groupEnd(() => `Advanced into ${tName} from ${currentType}: ${advanceOptionsToString(implemOptions)}`);
          optionsByImplems.push(implemOptions.map(opt => opt.paths));
        }
        const allCastOptions = flatCartesianProduct(optionsByImplems);
        debug.groupEnd(() => `Type-exploded options: ${advanceOptionsToString(allCastOptions)}`);
        return { options: allCastOptions };
      case 'ObjectType':
        // We've already handled the case of a fragment whose condition is this type. But the fragment might
        // be for either:
        // - a super-type of the current type: in which case, we're pretty much in the same case than if there
        //   were no particular condition.
        // - if the current type is an @interfaceObject, then this can be an implementation type of
        //   the interface in the supergraph. In that case, the type of the condition is not a
        //   type known of the subgraph, but the subgraph might still be able to handle some of
        //   fields, so in that case, we essentially "ignore" the fragment for now. We will re-add
        //   it back later for fields that are not in the current subgraph after we've taken
        //   a @key for the interface.
        // - another, incompatible type. This can happen for a type that intersects a super-type of the
        //   current type (since graphQL allows a fragment as long as there is an intersection). In that
        //   case, the whole operation simply cannot ever return anything.
        const conditionType = supergraphSchema.type(typeName)!;
        if (isAbstractType(conditionType) && possibleRuntimeTypes(conditionType).some(t => t.name == currentType.name)) {
          debug.groupEnd(() => `${typeName} is a super-type of current type ${currentType}: no edge to take`);
          // Operation type condition is applicable on the current type, so the types are already exploded but the
          // condition can reference types from the supergraph that are not present in the local subgraph.
          //
          // If operation has applied directives we need to convert to inline fragment without type condition, otherwise
          // we ignore the fragment altogether.
          const updatedPath = operation.appliedDirectives.length > 0
            ? path.add(operation.withUpdatedTypes(currentType, undefined), null, noConditionsResolution, operation.deferDirectiveArgs())
            : path;
          return { options: [[ updatedPath ]] };
        }

        if (path.tailIsInterfaceObject()) {
          const fakeDownCastEdge = path.nextEdges().find((e) => e.transition.kind === 'InterfaceObjectFakeDownCast' && e.transition.castedTypeName === typeName);
          if (fakeDownCastEdge) {
            const conditionResolution = canSatisfyConditions(path, fakeDownCastEdge, conditionResolver, context, [], [], getFieldParentTypeForOpTrigger);
            if (!conditionResolution.satisfied) {
              return { options: undefined };
            }
            const updatedPath = path.add(operation, fakeDownCastEdge, conditionResolution, operation.deferDirectiveArgs());
            return { options: [[ updatedPath ]] };
          }
        }

        // The operation we're dealing with can never return results (the type conditions applies have no intersection).
        // This means we _can_ fulfill this operation (by doing nothing and returning an empty result), which we indicate
        // by return an empty list of options.
        debug.groupEnd(() => `Cannot ever get ${typeName} from current type ${currentType}: returning empty branch`);
        return { options: [] };
      default:
        // We shouldn't have a fragment on a non-selectable type
        assert(false, `Unexpected ${currentType.kind} type ${currentType} from ${path.tail} given operation ${operation}`);
    }
  }
}

function addFieldEdge<V extends Vertex>(
  path: OpGraphPath<V>,
  fieldOperation: Field<any>,
  edge: Edge,
  conditionResolver: ConditionResolver,
  context: PathContext
): OpGraphPath<V> | undefined {
  const conditionResolution = canSatisfyConditions(path, edge, conditionResolver, context, [], [], getFieldParentTypeForOpTrigger);
  return conditionResolution.satisfied ? path.add(fieldOperation, edge, conditionResolution) : undefined;
}

function pathAsOptions<V extends Vertex>(path: OpGraphPath<V> | undefined): SimultaneousPaths<V>[] | undefined {
  return path ? [[path]] : undefined;
}

function nextEdgeForField<V extends Vertex>(
  path: OpGraphPath<V>,
  field: Field<any>,
  overrideConditions: Map<string, boolean>
): Edge | undefined {
  return edgeForField(path.graph, path.tail, field, overrideConditions);
}

function edgeForField(
  graph: QueryGraph,
  vertex: Vertex,
  field: Field<any>,
  overrideConditions: Map<string, boolean>
): Edge | undefined {
  const candidates = graph.outEdges(vertex)
    .filter(e =>
      e.transition.kind === 'FieldCollection'
      && field.selects(e.transition.definition, true, undefined, e.requiredContexts?.map(c => c.namedParameter))
      && e.satisfiesOverrideConditions(overrideConditions)
  );
  assert(candidates.length <= 1, () => `Vertex ${vertex} has multiple edges matching ${field} (${candidates})`);
  return candidates.length === 0 ? undefined : candidates[0];
}

function nextEdgeForTypeCast<V extends Vertex>(
  path: OpGraphPath<V>,
  typeName: string
): Edge | undefined {
  return edgeForTypeCast(path.graph, path.tail, typeName);
}

function edgeForTypeCast(
  graph: QueryGraph,
  vertex: Vertex,
  typeName: string
): Edge | undefined {
  const candidates = graph.outEdges(vertex).filter(e => e.transition.kind === 'DownCast' && typeName === e.transition.castedType.name);
  assert(candidates.length <= 1, () => `Vertex ${vertex} has multiple edges matching ${typeName} (${candidates})`);
  return candidates.length === 0 ? undefined : candidates[0];
}

const getFieldParentTypeForOpTrigger = (trigger: OpTrigger): CompositeType | null => {
  if (!isPathContext(trigger)) {
    if (trigger.kind === 'Field') {
      return trigger.definition.parent;
    }
  }
  return null;
};

const getFieldParentTypeForEdge = (transition: Transition): CompositeType | null => {
  if (transition.kind === 'FieldCollection') {
    const type = transition.definition.parent;
    if (!type || isScalarType(type) || isEnumType(type)) {
      return null;
    }
    if (isObjectType(type) || isInterfaceType(type) || isUnionType(type)) {
      return type;
    }
  }
  return null;
}