@apollo/query-graphs - npm Package Compare versions

Comparing version 2.0.0-preview.8 to 2.0.0-preview.9

CHANGELOG.md

 # CHANGELOG for `@apollo/query-graphs`
 
+## v2.0.0-preview.9
+
+- Support for Node 17 [PR #1541](https://github.com/apollographql/federation/pull/1541).
+
 ## v2.0.0-preview.8
@@ -4,0 +8,0 @@

dist/graphPath.d.ts

@@ -84,4 +84,15 @@ import { NamedType, OperationElement, Schema, SchemaRootKind, SelectionSet, ObjectType } from "@apollo/federation-internals";
 }
-export declare function isUnadvanceable<V extends Vertex>(result: GraphPath<Transition, V>[] | Unadvanceables): result is Unadvanceables;
-export declare function advancePathWithTransition<V extends Vertex>(supergraph: Schema, subgraphPath: GraphPath<Transition, V>, transition: Transition, targetType: NamedType, conditionResolver: ConditionResolver): GraphPath<Transition, V>[] | Unadvanceables;
+export declare function isUnadvanceable(result: any[] | Unadvanceables): result is Unadvanceables;
+export declare class TransitionPathWithLazyIndirectPaths<V extends Vertex = Vertex> {
+    readonly path: GraphPath<Transition, V>;
+    readonly conditionResolver: ConditionResolver;
+    readonly pathTransitionToEdge: (graph: QueryGraph, vertex: Vertex, transition: Transition) => Edge | null | undefined;
+    private lazilyComputedIndirectPaths;
+    constructor(path: GraphPath<Transition, V>, conditionResolver: ConditionResolver, pathTransitionToEdge: (graph: QueryGraph, vertex: Vertex, transition: Transition) => Edge | null | undefined);
+    static initial<V extends Vertex = Vertex>(supergraph: Schema, initialPath: GraphPath<Transition, V>, conditionResolver: ConditionResolver): TransitionPathWithLazyIndirectPaths<V>;
+    indirectOptions(): IndirectPaths<Transition, V>;
+    private computeIndirectPaths;
+    toString(): string;
+}
+export declare function advancePathWithTransition<V extends Vertex>(supergraph: Schema, subgraphPath: TransitionPathWithLazyIndirectPaths<V>, transition: Transition, targetType: NamedType): TransitionPathWithLazyIndirectPaths<V>[] | Unadvanceables;
 export declare type ExcludedEdges = readonly [number, number][];
@@ -88,0 +99,0 @@ export declare function sameExcludedEdges(ex1: ExcludedEdges, ex2: ExcludedEdges): boolean;

dist/graphPath.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.advanceSimultaneousPathsWithOperation = exports.advanceOptionsToString = exports.simultaneousPathsToString = exports.SimultaneousPathsWithLazyIndirectPaths = exports.getLocallySatisfiableKey = exports.addConditionExclusion = exports.sameExcludedEdges = exports.advancePathWithTransition = exports.isUnadvanceable = exports.Unadvanceables = exports.UnadvanceableReason = exports.unsatisfiedConditionsResolution = exports.noConditionsResolution = exports.UnsatisfiedConditionReason = exports.traversePath = exports.terminateWithNonRequestedTypenameField = exports.isRootPath = exports.GraphPath = void 0;
+exports.advanceSimultaneousPathsWithOperation = exports.advanceOptionsToString = exports.simultaneousPathsToString = exports.SimultaneousPathsWithLazyIndirectPaths = exports.getLocallySatisfiableKey = exports.addConditionExclusion = exports.sameExcludedEdges = exports.advancePathWithTransition = exports.TransitionPathWithLazyIndirectPaths = exports.isUnadvanceable = exports.Unadvanceables = exports.UnadvanceableReason = exports.unsatisfiedConditionsResolution = exports.noConditionsResolution = exports.UnsatisfiedConditionReason = exports.traversePath = exports.terminateWithNonRequestedTypenameField = exports.isRootPath = exports.GraphPath = void 0;
 const federation_internals_1 = require("@apollo/federation-internals");
@@ -185,3 +185,6 @@ const pathTree_1 = require("./pathTree");
     nextEdges() {
-        return this.graph.outEdges(this.tail);
+        const tailEdge = this.edgeToTail;
+        return tailEdge
+            ? this.graph.nonTrivialFollowupEdges(tailEdge)
+            : this.graph.outEdges(this.tail);
     }
@@ -365,6 +368,29 @@ isTerminal() {
 }
-function advancePathWithTransition(supergraph, subgraphPath, transition, targetType, conditionResolver) {
+class TransitionPathWithLazyIndirectPaths {
+    constructor(path, conditionResolver, pathTransitionToEdge) {
+        this.path = path;
+        this.conditionResolver = conditionResolver;
+        this.pathTransitionToEdge = pathTransitionToEdge;
+    }
+    static initial(supergraph, initialPath, conditionResolver) {
+        return new TransitionPathWithLazyIndirectPaths(initialPath, conditionResolver, createPathTransitionToEdgeFct(supergraph));
+    }
+    indirectOptions() {
+        if (!this.lazilyComputedIndirectPaths) {
+            this.lazilyComputedIndirectPaths = this.computeIndirectPaths();
+        }
+        return this.lazilyComputedIndirectPaths;
+    }
+    computeIndirectPaths() {
+        return advancePathWithNonCollectingAndTypePreservingTransitions(this.path, pathContext_1.emptyContext, this.conditionResolver, [], [], t => t, this.pathTransitionToEdge);
+    }
+    toString() {
+        return this.path.toString();
+    }
+}
+exports.TransitionPathWithLazyIndirectPaths = TransitionPathWithLazyIndirectPaths;
+function advancePathWithTransition(supergraph, subgraphPath, transition, targetType) {
     if (transition.kind === 'DownCast') {
         const supergraphRuntimeTypes = (0, federation_internals_1.possibleRuntimeTypes)(targetType);
-        const subgraphRuntimeTypes = subgraphPath.tailPossibleRuntimeTypes();
+        const subgraphRuntimeTypes = subgraphPath.path.tailPossibleRuntimeTypes();
         const intersection = supergraphRuntimeTypes.filter(t1 => subgraphRuntimeTypes.some(t2 => t1.name === t2.name)).map(t => t.name);
@@ -378,3 +404,3 @@ if (intersection.length === 0) {
     debug.group('Direct options:');
-    const directOptions = advancePathWithDirectTransition(supergraph, subgraphPath, transition, conditionResolver);
+    const directOptions = advancePathWithDirectTransition(supergraph, subgraphPath.path, transition, subgraphPath.conditionResolver);
     let options;
@@ -391,3 +417,3 @@ const deadEnds = [];
             debug.groupEnd(() => `reached leaf type ${targetType} so not trying indirect paths`);
-            return directOptions;
+            return createLazyTransitionOptions(directOptions, subgraphPath);
         }
@@ -397,4 +423,3 @@ options = directOptions;
     debug.group(`Computing indirect paths:`);
-    const pathTransitionToEdge = createPathTransitionToEdgeFct(supergraph);
-    const pathsWithNonCollecting = advancePathWithNonCollectingAndTypePreservingTransitions(subgraphPath, pathContext_1.emptyContext, conditionResolver, [], [], t => t, pathTransitionToEdge);
+    const pathsWithNonCollecting = subgraphPath.indirectOptions();
     if (pathsWithNonCollecting.paths.length > 0) {
@@ -405,3 +430,3 @@ debug.groupEnd(() => `${pathsWithNonCollecting.paths.length} indirect paths`);
             debug.group(() => `For indirect path ${nonCollectingPath}:`);
-            const pathsWithTransition = advancePathWithDirectTransition(supergraph, nonCollectingPath, transition, conditionResolver);
+            const pathsWithTransition = advancePathWithDirectTransition(supergraph, nonCollectingPath, transition, subgraphPath.conditionResolver);
             if (isUnadvanceable(pathsWithTransition)) {
@@ -423,3 +448,3 @@ debug.groupEnd(() => `Cannot be advanced with ${transition}`);
     if (options.length > 0) {
-        return options;
+        return createLazyTransitionOptions(options, subgraphPath);
     }
@@ -431,3 +456,3 @@ const allDeadEnds = deadEnds.concat(pathsWithNonCollecting.deadEnds.reasons);
         const subgraphsWithDeadEnd = new Set(allDeadEnds.map(e => e.destSubgraph));
-        for (const [subgraph, schema] of subgraphPath.graph.sources.entries()) {
+        for (const [subgraph, schema] of subgraphPath.path.graph.sources.entries()) {
             if (subgraphsWithDeadEnd.has(subgraph)) {
@@ -446,3 +471,3 @@ continue;
                 allDeadEnds.push({
-                    sourceSubgraph: subgraphPath.tail.source,
+                    sourceSubgraph: subgraphPath.path.tail.source,
                     destSubgraph: subgraph,
@@ -458,2 +483,5 @@ reason: UnadvanceableReason.UNREACHABLE_TYPE,
 exports.advancePathWithTransition = advancePathWithTransition;
+function createLazyTransitionOptions(options, origin) {
+    return options.map(option => new TransitionPathWithLazyIndirectPaths(option, origin.conditionResolver, origin.pathTransitionToEdge));
+}
 function isEdgeExcluded(edge, excluded) {
@@ -515,3 +543,3 @@ return excluded.some(([vIdx, eIdx]) => edge.head.index === vIdx && edge.index === eIdx);
         if (nextEdges.length === 0) {
-            debug.log(`Nothing to try for ${toAdvance}: it has no non-collecting outbound edges`);
+            debug.log(() => `Nothing to try for ${toAdvance}: it has no non-collecting outbound edges`);
             continue;
@@ -527,6 +555,2 @@ }
             excludedEdges = addEdgeExclusion(excludedEdges, edge);
-            if (isConditionExcluded(edge.conditions, excludedConditions)) {
-                debug.groupEnd(`Ignored: edge condition is excluded`);
-                continue;
-            }
             const target = edge.tail;
@@ -553,5 +577,9 @@ if (target.source === originalSource) {
                     || (prevForSource[0].size == toAdvance.size + 1 && prevForSource[1] <= 1))) {
-                debug.groupEnd(`Ignored: a better path to the same subgraph already added`);
+                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}`);
@@ -562,3 +590,3 @@ const conditionResolution = canSatisfyConditions(toAdvance, edge, conditionResolver, context, excludedEdges, excludedConditions);
                 if (prevForSource && prevForSource[0].size === toAdvance.size + 1 && prevForSource[1] <= conditionResolution.cost) {
-                    debug.groupEnd('Ignored: a better path to the same subgraph already added');
+                    debug.groupEnd('Ignored: a better (less costly) path to the same subgraph already added');
                     continue;
@@ -596,7 +624,13 @@ }
                 debug.groupEnd('Condition unsatisfiable');
+                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}")`
+                    : "";
                 deadEnds.push({
-                    sourceSubgraph: toAdvance.tail.source,
-                    destSubgraph: edge.tail.source,
+                    sourceSubgraph: source,
+                    destSubgraph: dest,
                     reason: UnadvanceableReason.UNSATISFIABLE_KEY_CONDITION,
-                    details: `cannot move to subgraph "${edge.tail.source}" using @key(fields: "${(_b = edge.conditions) === null || _b === void 0 ? void 0 : _b.toString(true, false)}") of "${edge.head.type}", the key field(s) cannot be resolved from subgraph "${toAdvance.tail.source}"`
+                    details: `cannot move to subgraph "${dest}" using @key(fields: "${(_b = edge.conditions) === null || _b === void 0 ? void 0 : _b.toString(true, false)}") of "${edge.head.type}", the key field(s) cannot be resolved from subgraph "${source}"${extraMsg}`
                 });
@@ -613,2 +647,11 @@ }
 }
+function conditionHasOverriddenFieldsInSource(schema, condition) {
+    const externalDirective = (0, federation_internals_1.federationMetadata)(schema).externalDirective();
+    return (0, federation_internals_1.allFieldDefinitionsInSelectionSet)(condition).some((field) => {
+        var _a, _b;
+        const typeInSource = schema.type(field.parent.name);
+        const fieldInSource = typeInSource && (0, federation_internals_1.isObjectType)(typeInSource) && typeInSource.field(field.name);
+        return fieldInSource && ((_b = (_a = fieldInSource.appliedDirectivesOf(externalDirective)) === null || _a === void 0 ? void 0 : _a.pop()) === null || _b === void 0 ? void 0 : _b.arguments().reason) === '[overridden]';
+    });
+}
 function hasValidDirectKeyEdge(graph, from, to, conditionResolver, maxCost) {
@@ -671,4 +714,13 @@ for (const edge of graph.outEdges(from)) {
             if (fieldInSubgraph) {
-                (0, federation_internals_1.assert)(fieldInSubgraph.hasAppliedDirective('external'), () => `${fieldInSubgraph.coordinate} in ${subgraph} is not external but there is no corresponding edge (edges from ${path} = [${path.nextEdges().join(', ')}])`);
-                details = `field "${transition.definition.coordinate}" is not resolvable because marked @external`;
+                const externalDirective = fieldInSubgraph.appliedDirectivesOf((0, federation_internals_1.federationMetadata)(fieldInSubgraph.schema()).externalDirective()).pop();
+                (0, federation_internals_1.assert)(externalDirective, () => `${fieldInSubgraph.coordinate} in ${subgraph} is not external but there is no corresponding edge (edges from ${path} = [${path.nextEdges().join(', ')}])`);
+                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 ${(0, federation_internals_1.printSubgraphNames)(overriddingSources)}`;
+                }
+                else {
+                    details = `field "${transition.definition.coordinate}" is not resolvable because marked @external`;
+                }
             }
@@ -691,2 +743,20 @@ else {
 }
+function findOverriddingSourcesIfOverridden(field, fieldSource, sources) {
+    return [...sources.entries()]
+        .map(([name, schema]) => {
+        var _a, _b, _c;
+        if (name === querygraph_1.FEDERATED_GRAPH_ROOT_SOURCE || name === fieldSource) {
+            return undefined;
+        }
+        const sourceMetadata = (0, federation_internals_1.federationMetadata)(schema);
+        const typeInSource = schema.type(field.parent.name);
+        if (!typeInSource || !(0, federation_internals_1.isObjectType)(typeInSource)) {
+            return undefined;
+        }
+        const fieldInSource = typeInSource.field(field.name);
+        const isOverriddingSource = ((_c = (_b = (_a = fieldInSource === null || fieldInSource === void 0 ? void 0 : fieldInSource.appliedDirectivesOf(sourceMetadata.overrideDirective())) === null || _a === void 0 ? void 0 : _a.pop()) === null || _b === void 0 ? void 0 : _b.arguments()) === null || _c === void 0 ? void 0 : _c.from) === fieldSource;
+        return isOverriddingSource ? name : undefined;
+    })
+        .filter((name) => !!name);
+}
 function warnOnKeyFieldsMarkedExternal(type) {
@@ -693,0 +763,0 @@ const metadata = (0, federation_internals_1.federationMetadata)(type.schema());

dist/querygraph.d.ts

 import { MultiMap, NamedType, Schema, SchemaRootKind, SelectionSet, MapWithCachedArrays } from '@apollo/federation-internals';
 import { Transition } from './transition';
+export declare const FEDERATED_GRAPH_ROOT_SOURCE = "_";
 export declare function federatedGraphRootTypeName(rootKind: SchemaRootKind): string;
@@ -40,2 +41,3 @@ export declare function isFederatedGraphRootType(type: NamedType): boolean;
     readonly sources: ReadonlyMap<string, Schema>;
+    readonly nonTrivialFollowupEdges: (edge: Edge) => readonly Edge[];
     constructor(name: string, vertices: Vertex[], adjacencies: Edge[][], typesToVertices: MultiMap<string, number>, rootVertices: MapWithCachedArrays<SchemaRootKind, RootVertex>, sources: ReadonlyMap<string, Schema>);
@@ -42,0 +44,0 @@ verticesCount(): number;

dist/querygraph.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.simpleTraversal = exports.buildFederatedQueryGraph = exports.buildSupergraphAPIQueryGraph = exports.buildQueryGraph = exports.QueryGraphState = exports.QueryGraph = exports.Edge = exports.isRootVertex = exports.RootVertex = exports.Vertex = exports.isFederatedGraphRootType = exports.federatedGraphRootTypeName = void 0;
+exports.simpleTraversal = exports.buildFederatedQueryGraph = exports.buildSupergraphAPIQueryGraph = exports.buildQueryGraph = exports.QueryGraphState = exports.QueryGraph = exports.Edge = exports.isRootVertex = exports.RootVertex = exports.Vertex = exports.isFederatedGraphRootType = exports.federatedGraphRootTypeName = exports.FEDERATED_GRAPH_ROOT_SOURCE = void 0;
 const federation_internals_1 = require("@apollo/federation-internals");
@@ -8,3 +8,4 @@ const util_1 = require("util");
 const structuralSubtyping_1 = require("./structuralSubtyping");
-const FEDERATED_GRAPH_ROOT_SOURCE = federation_internals_1.FEDERATION_RESERVED_SUBGRAPH_NAME;
+const nonTrivialEdgePrecomputing_1 = require("./nonTrivialEdgePrecomputing");
+exports.FEDERATED_GRAPH_ROOT_SOURCE = federation_internals_1.FEDERATION_RESERVED_SUBGRAPH_NAME;
 const FEDERATED_GRAPH_ROOT_SCHEMA = new federation_internals_1.Schema();
@@ -105,2 +106,3 @@ function federatedGraphRootTypeName(rootKind) {
         this.sources = sources;
+        this.nonTrivialFollowupEdges = (0, nonTrivialEdgePrecomputing_1.preComputeNonTrivialFollowupEdges)(this);
     }
@@ -214,3 +216,3 @@ verticesCount() {
     const builder = new GraphBuilder(verticesCount);
-    rootKinds.forEach(k => builder.createRootVertex(k, new federation_internals_1.ObjectType(federatedGraphRootTypeName(k)), FEDERATED_GRAPH_ROOT_SOURCE, FEDERATED_GRAPH_ROOT_SCHEMA));
+    rootKinds.forEach(k => builder.createRootVertex(k, new federation_internals_1.ObjectType(federatedGraphRootTypeName(k)), exports.FEDERATED_GRAPH_ROOT_SOURCE, FEDERATED_GRAPH_ROOT_SCHEMA));
     const copyPointers = new Array(subgraphs.length);
@@ -306,3 +308,3 @@ for (const [i, subgraph] of subgraphs.entries()) {
     }
-    return builder.build(FEDERATED_GRAPH_ROOT_SOURCE);
+    return builder.build(exports.FEDERATED_GRAPH_ROOT_SOURCE);
 }
@@ -309,0 +311,0 @@ function addProvidesEdges(schema, builder, from, provided) {

package.json

 {
   "name": "@apollo/query-graphs",
-  "version": "2.0.0-preview.8",
+  "version": "2.0.0-preview.9",
   "description": "Apollo Federation library to work with 'query graphs'",
@@ -23,6 +23,6 @@ "main": "dist/index.js",
   "engines": {
-    "node": ">=12.13.0 <17.0"
+    "node": ">=12.13.0 <18.0"
   },
   "dependencies": {
-    "@apollo/federation-internals": "^2.0.0-preview.8",
+    "@apollo/federation-internals": "^2.0.0-preview.9",
     "deep-equal": "^2.0.5",
@@ -37,3 +37,3 @@ "ts-graphviz": "^0.16.0"
   },
-  "gitHead": "516a30d879b4bde5945adb55b80d0f64118c322f"
+  "gitHead": "dd5ea3a7675af3e19e82d8150f72fe217074ae02"
 }

src/querygraph.ts

@@ -38,2 +38,3 @@ import {
 import { isStructuralFieldSubtype } from './structuralSubtyping';
+import { preComputeNonTrivialFollowupEdges } from './nonTrivialEdgePrecomputing';
 
@@ -43,3 +44,3 @@ // We use our federation reserved subgraph name to avoid risk of conflict with other subgraph names (wouldn't be a huge
 // without taking space.
-const FEDERATED_GRAPH_ROOT_SOURCE = FEDERATION_RESERVED_SUBGRAPH_NAME;
+export const FEDERATED_GRAPH_ROOT_SOURCE = FEDERATION_RESERVED_SUBGRAPH_NAME;
 const FEDERATED_GRAPH_ROOT_SCHEMA = new Schema();
@@ -248,2 +249,25 @@
   /**
+   * Given an edge, returns the possible edges that can follow it "productively", that is without creating
+   * a trivially inefficient path.
+   *
+   * More precisely, `nonTrivialFollowupEdges(e)` is equivalent calling `outEdges(e.tail)` and filtering
+   * the edges that "never make sense" after `e`, which mainly amounts to avoiding chaining key edges
+   * when we know there is guaranteed to be a better option. As an example, suppose we have 3 subgraphs
+   * A, B and C which all defined a `@key(fields: "id")` on some entity type `T`. Then it is never
+   * interesting to take that key edge from B -> C after A -> B because if we're in A and want to get
+   * to C, we can always do A -> C (of course, this is only true because it's the "same" key).
+   *
+   * See `preComputeNonTrivialFollowupEdges` for more details on which exact edges are filtered.
+   *
+   * Lastly, note that the main reason for exposing this method is that its result is pre-computed.
+   * Which in turn is done for performance reasons: having the same key defined in multiple subgraphs
+   * is _the_ most common pattern, and while our later algorithms (composition validation and query
+   * planning) would know to not select those trivially inefficient "detour", they might have to redo
+   * those checks many times and pre-computing once it is significantly faster (and pretty easy).
+   * Fwiw, when originally introduced, this optimization lowered composition validation on a big
+   * composition (100+ subgraphs) from ~4 "minutes" to ~10 seconds.
+   */
+  readonly nonTrivialFollowupEdges: (edge: Edge) => readonly Edge[];
+
+  /**
    * Creates a new query graph.
@@ -278,2 +302,3 @@ *
   ) {
+    this.nonTrivialFollowupEdges = preComputeNonTrivialFollowupEdges(this);
   }
@@ -280,0 +305,0 @@

src/transition.ts

@@ -16,6 +16,6 @@ import { FieldDefinition, CompositeType, SchemaRootKind } from "@apollo/federation-internals";
   *   with key transition _must_ have `conditions` corresponding to the key fields.
-  * - a query (`QueryResolution`), only found in "federated" query graphs: the edge goes from
-  *   the query root type of a subgraph to the query subgraph of another subgraph. It encodes
-  *   the fact that if a subgraph field returns the query type, any subgraph can be queried
-  *   from there.
+  * - a root type (`RootTypeResolution`), only found in "federated" query graphs: the edge goes from
+  *   a root type (query, mutation or subscription) of a subgraph to the (same) root type of another
+  *   subgraph. It encodes the fact that if a subgraph field returns a root type, any subgraph
+  *   can be queried from there.
   * - a "subgraph entering" edge: this is a special case only used for the edges out of the root
@@ -22,0 +22,0 @@ *   vertices of "federated" query graphs. It does not correspond to any physical graphQL elements

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

521790

increased by4.94%

Number of package files

61

increased by8.93%

Lines of code

6728

increased by4.86%

Dependency changes

• Updated@apollo/federation-internals@^2.0.0-preview.9