import { assert , arrayEquals , baseType , CompositeType , entityTypeName , Field , FieldSelection , FragmentElement , FragmentSelection , isAbstractType , isCompositeType , isListType , isObjectType , isNamedType , ListType , NonNullType , ObjectType , Operation , OperationPath , sameOperationPaths , Schema , SchemaRootKind , Selection , SelectionSet , selectionSetOf , selectionSetOfPath , Type , UnionType , Variable , VariableDefinition , VariableDefinitions , newDebugLogger , selectionOfElement , selectionSetOfElement , NamedFragments , operationToDocument , MapWithCachedArrays , } from "@apollo/federation-internals" ; import { advanceSimultaneousPathsWithOperation , Edge , emptyContext , ExcludedEdges , FieldCollection , QueryGraph , GraphPath , isPathContext , isRootPathTree , OpGraphPath , OpPathTree , OpRootPathTree , PathContext , PathTree , RootVertex , Vertex , isRootVertex , ExcludedConditions , advanceOptionsToString , ConditionResolution , unsatisfiedConditionsResolution , cachingConditionResolver , ConditionResolver , addConditionExclusion , SimultaneousPathsWithLazyIndirectPaths , simultaneousPathsToString , SimultaneousPaths , terminateWithNonRequestedTypenameField , getLocallySatisfiableKey , } from "@apollo/query-graphs" ; import { DocumentNode , stripIgnoredCharacters , print , GraphQLError , parse } from "graphql" ; import { QueryPlan , ResponsePath , SequenceNode , PlanNode , ParallelNode , FetchNode , trimSelectionNodes } from "./QueryPlan" ; const debug = newDebugLogger ( 'plan' ) ; export const MAX_COMPUTED_PLANS = 10000 ; function mapOptionsToSelections < RV extends Vertex > ( selectionSet , options ) { return selectionSet . selections ( true ) . map ( node => [ node , options ] ) ; } class QueryPlanningTaversal < RV extends Vertex > { private bestPlan : [ FetchDependencyGraph , OpPathTree < RV > , number ] | undefined ; private readonly isTopLevel : boolean ; private conditionResolver : ConditionResolver ; private stack : [ Selection , SimultaneousPathsWithLazyIndirectPaths < RV > [ ] ] [ ] ; private readonly closedBranches : SimultaneousPaths < RV > [ ] [ ] = [ ] ; constructor ( readonly supergraphSchema , readonly subgraphs , selectionSet , readonly variableDefinitions , private readonly startVertex , private readonly rootKind , readonly costFunction , initialContext , excludedEdges = [ ] , excludedConditions = [ ] ) { this . isTopLevel = isRootVertex ( startVertex ) ; this . conditionResolver = cachingConditionResolver ( subgraphs , ( edge , context , excludedEdges , excludedConditions ) => this . resolveConditionPlan ( edge , context , excludedEdges , excludedConditions ) ) ; const initialPath = GraphPath . create ( subgraphs , startVertex ) ; const initialOptions = [ new SimultaneousPathsWithLazyIndirectPaths ( [ initialPath ] , initialContext , this . conditionResolver , excludedEdges , excludedConditions ) ] ; this . stack = mapOptionsToSelections ( selectionSet , initialOptions ) ; } private debugStack ( ) { if ( this . isTopLevel && debug . enabled ) { debug . group ( 'Query planning open branches:' ) ; for ( const [ selection , options ] of this . stack ) { debug . groupedValues ( options , opt => `${ simultaneousPathsToString ( opt ) }` , `${ selection }:` ) ; } debug . groupEnd ( ) ; } } findBestPlan ( ) { while ( this . stack . length > 0 ) { this . debugStack ( ) ; const [ selection , options ] = this . stack . pop ( ) ! ; this . handleOpenBranch ( selection , options ) ; } this . computeBestPlanFromClosedBranches ( ) ; return this . bestPlan ; } private handleOpenBranch ( selection , options ) { const operation = selection . element ( ) ; let newOptions = [ ] ; for ( const option of options ) { const followupForOption = advanceSimultaneousPathsWithOperation ( this . supergraphSchema , option , operation ) ; if ( ! followupForOption ) { continue ; } if ( followupForOption . length === 0 ) { if ( operation . kind === 'FragmentElement' ) { this . closedBranches . push ( [ option . paths . map ( p => terminateWithNonRequestedTypenameField ( p ) ) ] ) ; } return ; } newOptions = newOptions . concat ( followupForOption ) ; } if ( newOptions . length === 0 ) { if ( this . isTopLevel ) { debug . log ( `No valid options to advance ${ selection } from ${ advanceOptionsToString ( options ) }` ) ; throw new Error ( `Was not able to find any options for ${ selection }: This shouldn't have happened.` ) ; } else { this . stack . splice ( 0 , this . stack . length ) ; this . closedBranches . splice ( 0 , this . closedBranches . length ) ; return ; } } if ( selection . selectionSet ) { for ( const branch of mapOptionsToSelections ( selection . selectionSet , newOptions ) ) { this . stack . push ( branch ) ; } } else { const updated = this . maybeEliminateStrictlyMoreCostlyPaths ( newOptions ) ; this . closedBranches . push ( updated ) ; } } private maybeEliminateStrictlyMoreCostlyPaths ( options ) { if ( options . length === 1 ) { return [ options [ 0 ] . paths ] ; } const singlePathOptions = options . filter ( opt => opt . paths . length === 1 ) ; if ( singlePathOptions . length === 0 ) { return options . map ( opt => opt . paths ) ; } let minJumps = Number . MAX_SAFE_INTEGER ; let withMinJumps = [ ] ; for ( const option of singlePathOptions ) { const jumps = option . paths [ 0 ] . subgraphJumps ( ) ; if ( jumps < minJumps ) { minJumps = jumps ; withMinJumps = [ option . paths ] ; } else if ( jumps === minJumps ) { withMinJumps . push ( option . paths ) ; } } for ( const option of singlePathOptions . filter ( opt => opt . paths . length > 1 ) ) { const jumps = option . paths . reduce ( ( acc , p ) => Math . min ( acc , p . subgraphJumps ( ) ) , Number . MAX_SAFE_INTEGER ) ; if ( jumps <= minJumps ) { withMinJumps . push ( option . paths ) ; } } return withMinJumps ; } private newDependencyGraph ( ) { return FetchDependencyGraph . create ( this . subgraphs ) ; } private reorderFirstBranch ( ) { const firstBranch = this . closedBranches [ 0 ] ; let i = 1 ; while ( i < this . closedBranches . length && this . closedBranches [ i ] . length > firstBranch . length ) { i ++ ; } this . closedBranches [ 0 ] = this . closedBranches [ i - 1 ] ; this . closedBranches [ i - 1 ] = firstBranch ; } private computeBestPlanFromClosedBranches ( ) { if ( this . closedBranches . length === 0 ) { return ; } this . closedBranches . sort ( ( b1 , b2 ) => b1 . length > b2 . length ? - 1 : ( b1 . length < b2 . length ? 1 : 0 ) ) ; let planCount = possiblePlans ( this . closedBranches ) ; debug . log ( ( ) => `Query has ${ planCount } possible plans` ) ; let firstBranch = this . closedBranches [ 0 ] ; while ( planCount > MAX_COMPUTED_PLANS && firstBranch . length > 1 ) { const prevSize = firstBranch . length ; firstBranch . pop ( ) ; planCount -= planCount / prevSize ; this . reorderFirstBranch ( ) ; firstBranch = this . closedBranches [ 0 ] ; debug . log ( ( ) => `Reduced plans to consider to ${ planCount } plans` ) ; } debug . log ( ( ) => `All branches:${ this . closedBranches . map ( ( opts , i ) => `\n${ i }:${ opts . map ( ( opt => `\n - ${ simultaneousPathsToString ( opt ) }` ) ) }` ) }` ) ; let idxFirstOfLengthOne = 0 ; while ( idxFirstOfLengthOne < this . closedBranches . length && this . closedBranches [ idxFirstOfLengthOne ] . length > 1 ) { idxFirstOfLengthOne ++ ; } let initialTree ; let initialDependencyGraph ; if ( idxFirstOfLengthOne === this . closedBranches . length ) { initialTree = PathTree . createOp ( this . subgraphs , this . startVertex ) ; initialDependencyGraph = this . newDependencyGraph ( ) ; } else { initialTree = PathTree . createFromOpPaths ( this . subgraphs , this . startVertex , this . closedBranches . slice ( idxFirstOfLengthOne ) . flat ( 2 ) ) ; initialDependencyGraph = this . updatedDependencyGraph ( this . newDependencyGraph ( ) , initialTree ) ; if ( idxFirstOfLengthOne === 0 ) { this . onNewPlan ( initialDependencyGraph , initialTree ) ; return ; } } const otherTrees = this . closedBranches . slice ( 0 , idxFirstOfLengthOne ) . map ( b => b . map ( opt => PathTree . createFromOpPaths ( this . subgraphs , this . startVertex , opt ) ) ) ; this . generateAllPlans ( initialDependencyGraph , initialTree , otherTrees ) ; } generateAllPlans ( initialDependencyGraph , initialTree , others ) { const eltIndexes = new Array < number > ( others . length ) ; let totalCombinations = 1 ; for ( let i = 0 ; i < others . length ; ++ i ) { const eltSize = others [ i ] . length ; assert ( eltSize , "Got empty option: this shouldn't have happened" ) ; if ( ! eltSize ) { totalCombinations = 0 ; break ; } eltIndexes [ i ] = 0 ; totalCombinations *= eltSize ; } for ( let i = 0 ; i < totalCombinations ; ++ i ) { const dependencyGraph = initialDependencyGraph . clone ( ) ; let tree = initialTree ; for ( let j = 0 ; j < others . length ; ++ j ) { const t = others [ j ] [ eltIndexes [ j ] ] ; this . updatedDependencyGraph ( dependencyGraph , t ) ; tree = tree . merge ( t ) ; } this . onNewPlan ( dependencyGraph , tree ) ; for ( let idx = 0 ; idx < others . length ; ++ idx ) { if ( eltIndexes [ idx ] == others [ idx ] . length - 1 ) { eltIndexes [ idx ] = 0 ; } else { eltIndexes [ idx ] += 1 ; break ; } } } } private cost ( dependencyGraph ) { return this . costFunction . finalize ( dependencyGraph . process ( this . costFunction ) , true ) ; } private updatedDependencyGraph ( dependencyGraph , tree ) { return isRootPathTree ( tree ) ? computeRootFetchGroups ( dependencyGraph , tree , this . rootKind ) : computeNonRootFetchGroups ( dependencyGraph , tree , this . rootKind ) ; } private resolveConditionPlan ( edge , context , excludedEdges , excludedConditions ) { const bestPlan = new QueryPlanningTaversal ( this . supergraphSchema , this . subgraphs , edge . conditions ! , this . variableDefinitions , edge . head , 'query' , this . costFunction , context , excludedEdges , addConditionExclusion ( excludedConditions , edge . conditions ) ) . findBestPlan ( ) ; return bestPlan ? { satisfied : true , cost : bestPlan [ 2 ] , pathTree : bestPlan [ 1 ] } : unsatisfiedConditionsResolution ; } private onNewPlan ( dependencyGraph , tree ) { const cost = this . cost ( dependencyGraph ) ; if ( ! this . bestPlan || cost < this . bestPlan [ 2 ] ) { debug . log ( ( ) => this . bestPlan ? `Found better with cost ${ cost } (previous had cost ${ this . bestPlan [ 2 ] }): ${ tree }` : `Computed plan with cost ${ cost }: ${ tree }` ) ; this . bestPlan = [ dependencyGraph , tree , cost ] ; } else { debug . log ( ( ) => `Ignoring plan with cost ${ cost } (a better plan with cost ${ this . bestPlan ! [ 2 ] } exists): ${ tree }` ) ; } } } function possiblePlans ( closedBranches ) { let totalCombinations = 1 ; for ( let i = 0 ; i < closedBranches . length ; ++ i ) { const eltSize = closedBranches [ i ] . length ; if ( ! eltSize ) { totalCombinations = 0 ; break ; } totalCombinations *= eltSize ; } return totalCombinations ; } function sum ( arr ) { return arr . reduce ( ( a , b ) => a + b , 0 ) ; } type CostFunction = FetchGroupProcessor < number , number [ ] , number > ; const fetchCost = 10000 ; const pipeliningCost = 100 ; const sameLevelFetchCost = 100 ; function selectionCost ( selection ? , depth = 1 ) { return selection ? selection . selections ( ) . reduce ( ( prev , curr ) => prev + depth + selectionCost ( curr . selectionSet , depth + 1 ) , 0 ) : 0 ; } const defaultCostFunction = { onFetchGroup : ( group ) => selectionCost ( group . selection ) , reduceParallel : ( values ) => values , reduceSequence : ( values ) => values . reduceRight ( ( acc , value , idx ) => { const valueArray = Array . isArray ( value ) ? value : [ value ] ; return acc + ( ( idx + 1 ) * pipeliningCost ) * ( fetchCost * valueArray . length ) * ( Math . max ( ... valueArray ) + ( valueArray . length - 1 ) * sameLevelFetchCost ) ; } , 0 ) , finalize : ( roots , rootsAreParallel ) => roots . length === 0 ? 0 : ( rootsAreParallel ? ( Math . max ( ... roots ) + ( roots . length - 1 ) * sameLevelFetchCost ) : sum ( roots ) ) } ; function isIntrospectionSelection ( selection ) { return selection . kind == 'FieldSelection' && selection . element ( ) . definition . isIntrospectionField ( ) ; } function withoutIntrospection ( operation ) { if ( ! operation . selectionSet . selections ( ) . some ( isIntrospectionSelection ) ) { return operation ; } const newSelections = operation . selectionSet . selections ( ) . filter ( s => ! isIntrospectionSelection ( s ) ) ; return new Operation ( operation . rootKind , new SelectionSet ( operation . selectionSet . parentType ) . addAll ( newSelections ) , operation . variableDefinitions , operation . name ) ; } export function computeQueryPlan ( supergraphSchema , federatedQueryGraph , operation ) { if ( operation . rootKind === 'subscription' ) { throw new GraphQLError ( 'Query planning does not support subscriptions for now.' , [ parse ( operation . toString ( ) ) ] ) ; } operation = operation . expandAllFragments ( ) ; operation = withoutIntrospection ( operation ) ; debug . group ( ( ) => `Computing plan for\n${ operation }` ) ; if ( operation . selectionSet . isEmpty ( ) ) { debug . groupEnd ( 'Empty plan' ) ; return { kind : 'QueryPlan' } ; } const root = federatedQueryGraph . root ( operation . rootKind ) ; assert ( root , ( ) => `Shouldn't have a ${ operation . rootKind } operation if the subgraphs don't have a ${ operation . rootKind } root` ) ; const processor = fetchGroupToPlanProcessor ( operation . variableDefinitions , operation . selectionSet . fragments ) ; if ( operation . rootKind === 'mutation' ) { const dependencyGraphs = computeRootSerialDependencyGraph ( supergraphSchema , operation , federatedQueryGraph , root ) ; const rootNode = processor . finalize ( dependencyGraphs . flatMap ( g => g . process ( processor ) ) , false ) ; debug . groupEnd ( 'Mutation plan computed' ) ; return { kind : 'QueryPlan' , node : rootNode } ; } else { const dependencyGraph = computeRootParallelDependencyGraph ( supergraphSchema , operation , federatedQueryGraph , root ) ; const rootNode = processor . finalize ( dependencyGraph . process ( processor ) , true ) ; debug . groupEnd ( 'Query plan computed' ) ; return { kind : 'QueryPlan' , node : rootNode } ; } } function computeRootParallelDependencyGraph ( supergraphSchema , operation , federatedQueryGraph , root ) { return computeRootParallelBestPlan ( supergraphSchema , operation . selectionSet , operation . variableDefinitions , federatedQueryGraph , root ) [ 0 ] ; } function computeRootParallelBestPlan ( supergraphSchema , selection , variables , federatedQueryGraph , root ) { const planningTraversal = new QueryPlanningTaversal ( supergraphSchema , federatedQueryGraph , selection , variables , root , root . rootKind , defaultCostFunction , emptyContext ) ; const plan = planningTraversal . findBestPlan ( ) ; return plan ?? createEmptyPlan ( federatedQueryGraph , root ) ; } function createEmptyPlan ( federatedQueryGraph , root ) { return [ FetchDependencyGraph . create ( federatedQueryGraph ) , PathTree . createOp ( federatedQueryGraph , root ) , 0 ] ; } function onlyRootSubgraph ( graph ) { const subgraphs = graph . rootSubgraphs ( ) ; assert ( subgraphs . length === 1 , ( ) => `${ graph } should have only one root, but has [${ graph . rootSubgraphs ( ) }]` ) ; return subgraphs [ 0 ] ; } function computeRootSerialDependencyGraph ( supergraphSchema , operation , federatedQueryGraph , root ) { const splittedRoots = splitTopLevelFields ( operation . selectionSet ) ; const graphs = [ ] ; let [ prevDepGraph , prevPaths ] = computeRootParallelBestPlan ( supergraphSchema , splittedRoots [ 0 ] , operation . variableDefinitions , federatedQueryGraph , root ) ; let prevSubgraph = onlyRootSubgraph ( prevDepGraph ) ; for ( let i = 1 ; i < splittedRoots . length ; i ++ ) { const [ newDepGraph , newPaths ] = computeRootParallelBestPlan ( supergraphSchema , splittedRoots [ i ] , operation . variableDefinitions , federatedQueryGraph , root ) ; const newSubgraph = onlyRootSubgraph ( newDepGraph ) ; if ( prevSubgraph === newSubgraph ) { prevPaths = prevPaths . concat ( newPaths ) ; prevDepGraph = computeRootFetchGroups ( FetchDependencyGraph . create ( federatedQueryGraph ) , prevPaths , root . rootKind ) ; } else { graphs . push ( prevDepGraph ) ; [ prevDepGraph , prevPaths , prevSubgraph ] = [ newDepGraph , newPaths , newSubgraph ] ; } } graphs . push ( prevDepGraph ) ; return graphs ; } function splitTopLevelFields ( selectionSet ) { return selectionSet . selections ( ) . flatMap ( selection => { if ( selection . kind === 'FieldSelection' ) { return [ selectionSetOf ( selectionSet . parentType , selection ) ] ; } else { return splitTopLevelFields ( selection . selectionSet ) . map ( s => selectionSetOfElement ( selection . element ( ) , s ) ) ; } } ) ; } function fetchGroupToPlanProcessor ( variableDefinitions , fragments ? ) { return { onFetchGroup : ( group ) => group . toPlanNode ( variableDefinitions , fragments ) , reduceParallel : ( values ) => flatWrap ( 'Parallel' , values ) , reduceSequence : ( values ) => flatWrap ( 'Sequence' , values ) , finalize : ( roots , rootsAreParallel ) => roots . length == 0 ? undefined : flatWrap ( rootsAreParallel ? 'Parallel' : 'Sequence' , roots ) } ; } function addToResponsePath ( path , responseName , type ) { path = path . concat ( responseName ) ; while ( ! isNamedType ( type ) ) { if ( isListType ( type ) ) { path . push ( '@' ) ; } type = type . ofType ; } return path ; } class LazySelectionSet { constructor ( private _computed ? , private readonly _toCloneOnWrite ? ) { assert ( _computed || _toCloneOnWrite , 'Should have one of the argument' ) ; } forRead ( ) { return this . _computed ? this . _computed : this . _toCloneOnWrite ! ; } forWrite ( ) { if ( ! this . _computed ) { this . _computed = this . _toCloneOnWrite ! . clone ( ) ; } return this . _computed ; } clone ( ) { if ( this . _computed ) { return new LazySelectionSet ( undefined , this . _computed ) ; } else { return this ; } } toString ( ) { return this . forRead ( ) . toString ( ) ; } } class FetchGroup { private constructor ( readonly dependencyGraph , public index , readonly subgraphName , readonly rootKind , readonly parentType , readonly isEntityFetch , private readonly _selection , private readonly _inputs ? , readonly mergeAt ? ) { } static create ( dependencyGraph , index , subgraphName , rootKind , parentType , isEntityFetch , mergeAt ? ) { return new FetchGroup ( dependencyGraph , index , subgraphName , rootKind , parentType , isEntityFetch , new LazySelectionSet ( new SelectionSet ( parentType ) ) , isEntityFetch ? new LazySelectionSet ( new SelectionSet ( parentType ) ) : undefined , mergeAt ) ; } clone ( newDependencyGraph ) { return new FetchGroup ( newDependencyGraph , this . index , this . subgraphName , this . rootKind , this . parentType , this . isEntityFetch , this . _selection . clone ( ) , this . _inputs ?. clone ( ) , this . mergeAt ) ; } get isTopLevel ( ) : boolean { return ! this . mergeAt ; } get selection ( ) : SelectionSet { return this . _selection . forRead ( ) ; } get inputs ( ) : SelectionSet | undefined { return this . _inputs ?. forRead ( ) ; } clonedInputs ( ) { return this . _inputs ?. clone ( ) ; } addDependencyOn ( groups ) { this . dependencyGraph . addDependency ( this , groups ) ; } removeDependencyOn ( groups ) { this . dependencyGraph . removeDependency ( this , groups ) ; } addInputs ( selection ) { assert ( this . _inputs , "Shouldn't try to add inputs to a root fetch group" ) ; if ( selection instanceof SelectionSet ) { this . _inputs . forWrite ( ) . mergeIn ( selection ) ; } else { this . _inputs . forWrite ( ) . add ( selection ) ; } } addSelection ( path ) { this . _selection . forWrite ( ) . addPath ( path ) ; } addSelections ( selection ) { this . _selection . forWrite ( ) . mergeIn ( selection ) ; } mergeIn ( toMerge , mergePath ) { assert ( ! toMerge . isTopLevel , ( ) => `Shouldn't merge top level group ${ toMerge } into ${ this }` ) ; const selectionSet = selectionSetOfPath ( mergePath , endOfPathSet => { assert ( endOfPathSet , ( ) => `Merge path ${ mergePath } ends on a non-selectable type` ) ; for ( const typeCastSel of toMerge . selection . selections ( ) ) { assert ( typeCastSel instanceof FragmentSelection , ( ) => `Unexpected field selection ${ typeCastSel } at top-level of ${ toMerge } selection.` ) ; endOfPathSet . mergeIn ( typeCastSel . selectionSet ) ; } } ) ; this . _selection . forWrite ( ) . mergeIn ( selectionSet ) ; this . dependencyGraph . onMergedIn ( this , toMerge ) ; } toPlanNode ( variableDefinitions , fragments ? ) { addTypenameFieldForAbstractTypes ( this . selection ) ; this . selection . validate ( ) ; const inputs = this . _inputs ?. forRead ( ) ; if ( inputs ) { inputs . validate ( ) ; } const inputNodes = inputs ? inputs . toSelectionSetNode ( ) : undefined ; const operation = this . isEntityFetch ? operationForEntitiesFetch ( this . dependencyGraph . subgraphSchemas . get ( this . subgraphName ) ! , this . selection , variableDefinitions , fragments ) : operationForQueryFetch ( this . rootKind , this . selection , variableDefinitions , fragments ) ; const fetchNode = { kind : 'Fetch' , serviceName : this . subgraphName , requires : inputNodes ? trimSelectionNodes ( inputNodes . selections ) : undefined , variableUsages : this . selection . usedVariables ( ) . map ( v => v . name ) , operation : stripIgnoredCharacters ( print ( operation ) ) , } ; return this . isTopLevel ? fetchNode : { kind : 'Flatten' , path : this . mergeAt ! , node : fetchNode , } ; } toString ( ) { return this . isTopLevel ? `[${ this . index }]${ this . subgraphName }[${ this . _selection }]` : `[${ this . index }]${ this . subgraphName }@(${ this . mergeAt })[${ this . _inputs } => ${ this . _selection }]` ; } } function removeInPlace < T > ( value , array ) { const idx = array . indexOf ( value ) ; if ( idx >= 0 ) { array . splice ( idx , 1 ) ; } } interface FetchGroupProcessor < G , P , F > { onFetchGroup ( group , isRootGroup ) : G ; reduceParallel ( values ) : P ; reduceSequence ( values ) : G ; finalize ( roots , isParallel ) : F ; } type UnhandledGroups = [ FetchGroup , UnhandledInEdges ] [ ] ; type UnhandledInEdges = number [ ] ; function sameMergeAt ( m1 , m2 ) { if ( ! m1 ) { return ! m2 ; } if ( ! m2 ) { return false ; } return arrayEquals ( m1 , m2 ) ; } class FetchDependencyGraph { private isReduced : boolean = false ; private constructor ( readonly subgraphSchemas , readonly federatedQueryGraph , private readonly rootGroups , private readonly groups , private readonly adjacencies , private readonly inEdges , private readonly pathsInParents ) { } static create ( federatedQueryGraph ) { return new FetchDependencyGraph ( federatedQueryGraph . sources , federatedQueryGraph , new MapWithCachedArrays ( ) , [ ] , [ ] , [ ] , [ ] ) ; } clone ( ) { const cloned = new FetchDependencyGraph ( this . subgraphSchemas , this . federatedQueryGraph , new MapWithCachedArrays < string , FetchGroup > ( ) , new Array ( this . groups . length ) , this . adjacencies . map ( a => a . concat ( ) ) , this . inEdges . map ( a => a . concat ( ) ) , this . pathsInParents . concat ( ) ) ; for ( let i = 0 ; i < this . groups . length ; i ++ ) { cloned . groups [ i ] = this . groups [ i ] . clone ( cloned ) ; } for ( const group of this . rootGroups . values ( ) ) { cloned . rootGroups . set ( group . subgraphName , cloned . groups [ group . index ] ) ; } return cloned ; } getOrCreateRootFetchGroup ( subgraphName , rootKind , parentType ) { let group = this . rootGroups . get ( subgraphName ) ; if ( ! group ) { group = this . createRootFetchGroup ( subgraphName , rootKind , parentType ) ; this . rootGroups . set ( subgraphName , group ) ; } return group ; } rootSubgraphs ( ) { return this . rootGroups . keys ( ) ; } createRootFetchGroup ( subgraphName , rootKind , parentType ) { const group = this . newFetchGroup ( subgraphName , parentType , false , rootKind ) ; this . rootGroups . set ( subgraphName , group ) ; return group ; } private newFetchGroup ( subgraphName , parentType , isEntityFetch , rootKind , mergeAt ? , directParent ? , pathInParent ? ) { this . onModification ( ) ; const newGroup = FetchGroup . create ( this , this . groups . length , subgraphName , rootKind , parentType , isEntityFetch , mergeAt ) ; this . groups . push ( newGroup ) ; this . adjacencies . push ( [ ] ) ; this . inEdges . push ( [ ] ) ; if ( directParent ) { this . addEdge ( directParent . index , newGroup . index , pathInParent ) ; } return newGroup ; } getOrCreateKeyFetchGroup ( subgraphName , mergeAt , directParent , pathInParent , conditionsGroups ) { for ( const existing of this . dependents ( directParent ) ) { if ( existing . subgraphName === subgraphName && existing . mergeAt && sameMergeAt ( existing . mergeAt , mergeAt ) && ! this . isDependedOn ( existing , conditionsGroups ) ) { const existingPathInParent = this . pathInParent ( existing ) ; if ( pathInParent && existingPathInParent && ! sameOperationPaths ( existingPathInParent , pathInParent ) ) { this . pathsInParents [ existing . index ] = undefined ; } return existing ; } } const entityType = this . subgraphSchemas . get ( subgraphName ) ! . type ( entityTypeName ) ! as UnionType ; return this . newFetchGroup ( subgraphName , entityType , true , 'query' , mergeAt , directParent , pathInParent ) ; } newRootTypeFetchGroup ( subgraphName , rootKind , parentType , mergeAt , directParent , pathInParent ) { return this . newFetchGroup ( subgraphName , parentType , false , rootKind , mergeAt , directParent , pathInParent ) ; } private isDependedOn ( toCheck , conditions ) { const stack = conditions . concat ( ) ; while ( stack . length > 0 ) { const group = stack . pop ( ) ! ; if ( toCheck . index === group . index ) { return true ; } stack . push ( ... this . dependencies ( group ) ) ; } return false ; } newKeyFetchGroup ( subgraphName , mergeAt ) { const entityType = this . subgraphSchemas . get ( subgraphName ) ! . type ( entityTypeName ) ! as UnionType ; return this . newFetchGroup ( subgraphName , entityType , true , 'query' , mergeAt ) ; } addDependency ( dependentGroup , dependentOn ) { this . onModification ( ) ; const groups = Array . isArray ( dependentOn ) ? dependentOn : [ dependentOn ] ; for ( const group of groups ) { this . addEdge ( group . index , dependentGroup . index ) ; } } removeDependency ( dependentGroup , dependentOn ) { this . onModification ( ) ; const groups = Array . isArray ( dependentOn ) ? dependentOn : [ dependentOn ] ; for ( const group of groups ) { this . removeEdge ( group . index , dependentGroup . index ) ; } } pathInParent ( group ) { return this . pathsInParents [ group . index ] ; } private addEdge ( from , to , pathInFrom ? ) { if ( ! this . adjacencies [ from ] . includes ( to ) ) { this . adjacencies [ from ] . push ( to ) ; this . inEdges [ to ] . push ( from ) ; const parentsCount = this . inEdges [ to ] . length ; if ( pathInFrom && parentsCount === 1 ) { this . pathsInParents [ to ] = pathInFrom ; } else if ( parentsCount > 1 ) { this . pathsInParents [ to ] = undefined ; } } } private removeEdge ( from , to ) { if ( this . adjacencies [ from ] . includes ( to ) ) { removeInPlace ( to , this . adjacencies [ from ] ) ; removeInPlace ( from , this . inEdges [ to ] ) ; this . pathsInParents [ to ] = undefined ; } } onMergedIn ( mergedInto , merged ) { assert ( ! merged . isTopLevel , "Shouldn't remove top level groups" ) ; this . onModification ( ) ; this . relocateDependentsOnMergedIn ( mergedInto , merged . index ) ; this . removeInternal ( merged . index ) ; } private relocateDependentsOnMergedIn ( mergedInto , mergedIndex ) { for ( const dependentIdx of this . adjacencies [ mergedIndex ] ) { this . addEdge ( mergedInto . index , dependentIdx ) ; const idxInIns = this . inEdges [ dependentIdx ] . indexOf ( mergedIndex ) ; if ( idxInIns >= 0 ) { this . inEdges [ dependentIdx ] . splice ( idxInIns , 1 ) ; } } } remove ( group ) { this . onModification ( ) ; const dependents = this . dependents ( group ) ; const dependencies = this . dependencies ( group ) ; assert ( dependents . length === 0 , ( ) => `Cannot remove group ${ group } with dependents [${ dependents }]` ) ; assert ( dependencies . length <= 1 , ( ) => `Cannot remove group ${ group } with more/less than one dependency: [${ dependencies }]` ) ; this . removeInternal ( group . index ) ; } private removeInternal ( mergedIndex ) { for ( const dependedIdx of this . inEdges [ mergedIndex ] ) { const idxInAdj = this . adjacencies [ dependedIdx ] . indexOf ( mergedIndex ) ; this . adjacencies [ dependedIdx ] . splice ( idxInAdj , 1 ) ; } this . groups . splice ( mergedIndex , 1 ) ; this . adjacencies . splice ( mergedIndex , 1 ) ; this . inEdges . splice ( mergedIndex , 1 ) ; this . groups . forEach ( g => { if ( g . index > mergedIndex ) { -- g . index ; } } ) ; this . adjacencies . forEach ( adj => { adj . forEach ( ( v , i ) => { if ( v > mergedIndex ) { adj [ i ] = v - 1 ; } } ) ; } ) ; this . inEdges . forEach ( ins => { ins . forEach ( ( v , i ) => { if ( v > mergedIndex ) { ins [ i ] = v - 1 ; } } ) ; } ) ; } private onModification ( ) { this . isReduced = false ; } private reduce ( ) { if ( this . isReduced ) { return ; } for ( const group of this . groups ) { for ( const adjacent of this . adjacencies [ group . index ] ) { this . dfsRemoveRedundantEdges ( group . index , adjacent ) ; } } for ( const group of this . rootGroups . values ( ) ) { this . removeEmptyGroups ( group ) ; } for ( const group of this . rootGroups . values ( ) ) { this . mergeDependentFetchesForSameSubgraphAndPath ( group ) ; } this . isReduced = true ; } private removeEmptyGroups ( group ) { const dependents = this . dependents ( group ) ; if ( group . selection . isEmpty ( ) ) { assert ( dependents . length === 0 , ( ) => `Empty group ${ group } has dependents: ${ dependents }` ) ; this . remove ( group ) ; } for ( const g of dependents ) { this . removeEmptyGroups ( g ) ; } } private mergeDependentFetchesForSameSubgraphAndPath ( group ) { const dependents = this . dependents ( group ) ; if ( dependents . length > 1 ) { for ( const g1 of dependents ) { for ( const g2 of dependents ) { if ( g1 . index !== g2 . index && g1 . subgraphName === g2 . subgraphName && sameMergeAt ( g1 . mergeAt , g2 . mergeAt ) && this . dependencies ( g1 ) . length === 1 && this . dependencies ( g2 ) . length === 1 ) { const merged = FetchGroup . create ( this , g1 . index , g1 . subgraphName , g1 . rootKind , g1 . selection . parentType , g1 . isEntityFetch , g1 . mergeAt ) ; this . pathsInParents [ g1 . index ] = undefined ; if ( g1 . inputs ) { merged . addInputs ( g1 . inputs ) ; } merged . addSelections ( g1 . selection ) ; this . groups [ merged . index ] = merged ; if ( g2 . inputs ) { merged . addInputs ( g2 . inputs ) ; } merged . addSelections ( g2 . selection ) ; this . onMergedIn ( merged , g2 ) ; this . mergeDependentFetchesForSameSubgraphAndPath ( group ) ; return ; } } } } for ( const g of dependents ) { this . mergeDependentFetchesForSameSubgraphAndPath ( g ) ; } } dependencies ( group ) { return this . inEdges [ group . index ] . map ( i => this . groups [ i ] ) ; } dependents ( group ) { return this . adjacencies [ group . index ] . map ( i => this . groups [ i ] ) ; } private dfsRemoveRedundantEdges ( parentVertex , startVertex ) { const parentAdjacencies = this . adjacencies [ parentVertex ] ; const stack = [ ... this . adjacencies [ startVertex ] ] ; while ( stack . length > 0 ) { const v = stack . pop ( ) ! ; removeInPlace ( v , parentAdjacencies ) ; removeInPlace ( parentVertex , this . inEdges [ v ] ) ; stack . push ( ... this . adjacencies [ v ] ) ; } } private outGroups ( group ) { return this . adjacencies [ group . index ] . map ( i => this . groups [ i ] ) ; } private inGroups ( group ) { return this . inEdges [ group . index ] . map ( i => this . groups [ i ] ) ; } private processGroup < G , P , F > ( processor , group , isRootGroup ) { const outGroups = this . outGroups ( group ) ; const processed = processor . onFetchGroup ( group , isRootGroup ) ; if ( outGroups . length == 0 ) { return [ processed , [ ] ] ; } const allOutGroupsHaveThisAsIn = outGroups . every ( g => this . inGroups ( g ) . length === 1 ) ; if ( allOutGroupsHaveThisAsIn ) { const nodes = [ processed ] ; let nextNodes = outGroups ; let remainingNext = [ ] ; while ( nextNodes . length > 0 ) { const [ node , toHandle , remaining ] = this . processParallelGroups ( processor , nextNodes , remainingNext ) ; nodes . push ( node ) ; const [ canHandle , newRemaining ] = this . mergeRemainings ( remainingNext , remaining ) ; remainingNext = newRemaining ; nextNodes = canHandle . concat ( toHandle ) ; } return [ processor . reduceSequence ( nodes ) , remainingNext ] ; } else { return [ processed , outGroups . map ( g => [ g , this . inEdges [ g . index ] . filter ( e => e !== group . index ) ] ) ] ; } } private processParallelGroups < G , P , F > ( processor , groups , remaining ) { const parallelNodes = [ ] ; let remainingNext = remaining ; const toHandleNext = [ ] ; for ( const group of groups ) { const [ node , remaining ] = this . processGroup ( processor , group , false ) ; parallelNodes . push ( node ) ; const [ canHandle , newRemaining ] = this . mergeRemainings ( remainingNext , remaining ) ; toHandleNext . push ( ... canHandle ) ; remainingNext = newRemaining ; } return [ processor . reduceParallel ( parallelNodes ) , toHandleNext , remainingNext ] ; } private mergeRemainings ( r1 , r2 ) { const unhandled = [ ] ; const toHandle = [ ] ; for ( const [ g , edges ] of r1 ) { const newEdges = this . mergeRemaingsAndRemoveIfFound ( g , edges , r2 ) ; if ( newEdges . length == 0 ) { toHandle . push ( g ) ; } else { unhandled . push ( [ g , newEdges ] ) ; } } unhandled . push ( ... r2 ) ; return [ toHandle , unhandled ] ; } private mergeRemaingsAndRemoveIfFound ( group , inEdges , otherGroups ) { const idx = otherGroups . findIndex ( g => g [ 0 ] . index === group . index ) ; if ( idx < 0 ) { return inEdges ; } else { const otherEdges = otherGroups [ idx ] [ 1 ] ; otherGroups . splice ( idx , 1 ) ; return inEdges . filter ( e => otherEdges . includes ( e ) ) ; } } process < G , P > ( processor ) { this . reduce ( ) ; const rootNodes = this . rootGroups . values ( ) . map ( rootGroup => { const [ node , remaining ] = this . processGroup ( processor , rootGroup , true ) ; assert ( remaining . length == 0 , `A root group should have no remaining groups unhandled` ) ; return node ; } ) ; return rootNodes ; } dumpOnConsole ( ) { console . log ( 'Groups:' ) ; for ( const group of this . groups ) { console . log ( `  ${ group }` ) ; } console . log ( 'Adjacencies:' ) ; for ( const [ i , adj ] of this . adjacencies . entries ( ) ) { console . log ( `  ${ i } => [${ adj . join ( ', ' ) }]` ) ; } console . log ( 'In-Edges:' ) ; for ( const [ i , ins ] of this . inEdges . entries ( ) ) { console . log ( `  ${ i } => [${ ins . join ( ', ' ) }]` ) ; } } toString ( ) { return this . rootGroups . values ( ) . map ( g => this . toStringInternal ( g , "" ) ) . join ( '\n' ) ; } toStringInternal ( group , indent ) { const groupDependents = this . adjacencies [ group . index ] ; return [ indent + group . subgraphName + ' <- ' + groupDependents . map ( i => this . groups [ i ] . subgraphName ) . join ( ', ' ) ] . concat ( groupDependents . flatMap ( g => this . adjacencies [ g ] . length == 0 ? [ ] : this . toStringInternal ( this . groups [ g ] , indent + "  " ) ) ) . join ( '\n' ) ; } } function computeRootFetchGroups ( dependencyGraph , pathTree , rootKind ) { for ( const [ edge , _trigger , _conditions , child ] of pathTree . childElements ( ) ) { assert ( edge !== null , `The root edge should not be null` ) ; const source = edge . tail . source ; const rootType = edge . tail . type as ObjectType ; const group = dependencyGraph . getOrCreateRootFetchGroup ( source , rootKind , rootType ) ; computeGroupsForTree ( dependencyGraph , child , group ) ; } return dependencyGraph ; } function computeNonRootFetchGroups ( dependencyGraph , pathTree , rootKind ) { const source = pathTree . vertex . source ; const rootType = pathTree . vertex . type ; assert ( isCompositeType ( rootType ) , ( ) => `Should not have condition on non-selectable type ${ rootType }` ) ; const group = dependencyGraph . getOrCreateRootFetchGroup ( source , rootKind , rootType ) ; computeGroupsForTree ( dependencyGraph , pathTree , group ) ; return dependencyGraph ; } function createNewFetchSelectionContext ( type , selections , context ) { const typeCast = new FragmentElement ( type , type . name ) ; let inputSelection = selectionOfElement ( typeCast , selections ) ; let path = [ typeCast ] ; if ( context . isEmpty ( ) ) { return [ inputSelection , path ] ; } const schema = type . schema ( ) ; const [ name0 , ifs0 ] = context . directives [ 0 ] ; typeCast . applyDirective ( schema . directive ( name0 ) ! , { 'if' : ifs0 } ) ; for ( let i = 1 ; i < context . directives . length ; i ++ ) { const [ name , ifs ] = context . directives [ i ] ; const fragment = new FragmentElement ( type , type . name ) ; fragment . applyDirective ( schema . directive ( name ) ! , { 'if' : ifs } ) ; inputSelection = selectionOfElement ( fragment , selectionSetOf ( type , inputSelection ) ) ; path = [ fragment ] . concat ( path ) ; } return [ inputSelection , path ] ; } function computeGroupsForTree ( dependencyGraph , pathTree , startGroup , initialMergeAt = [ ] , initialPath = [ ] ) { const stack = [ [ pathTree , startGroup , initialMergeAt , initialPath ] ] ; const createdGroups = [ ] ; while ( stack . length > 0 ) { const [ tree , group , mergeAt , path ] = stack . pop ( ) ! ; if ( tree . isLeaf ( ) ) { group . addSelection ( path ) ; } else { for ( const [ edge , operation , conditions , child ] of tree . childElements ( true ) ) { if ( isPathContext ( operation ) ) { assert ( edge !== null , ( ) => `Unexpected 'null' edge with no trigger at ${ path }` ) ; assert ( edge . head . source !== edge . tail . source , ( ) => `Key/Query edge ${ edge } should change the underlying subgraph` ) ; if ( edge . transition . kind === 'KeyResolution' ) { assert ( conditions , ( ) => `Key edge ${ edge } should have some conditions paths` ) ; const groupsForConditions = computeGroupsForTree ( dependencyGraph , conditions , group , mergeAt , path ) ; const newGroup = dependencyGraph . getOrCreateKeyFetchGroup ( edge . tail . source , mergeAt , group , path , groupsForConditions ) ; createdGroups . push ( newGroup ) ; newGroup . addDependencyOn ( groupsForConditions ) ; const type = edge . tail . type as CompositeType ; const inputSelections = new SelectionSet ( type ) ; inputSelections . add ( new FieldSelection ( new Field ( type . typenameField ( ) ! ) ) ) ; inputSelections . mergeIn ( edge . conditions ! ) ; const [ inputs , newPath ] = createNewFetchSelectionContext ( type , inputSelections , operation ) ; newGroup . addInputs ( inputs ) ; group . addSelection ( path . concat ( new Field ( ( edge . head . type as CompositeType ) . typenameField ( ) ! ) ) ) ; stack . push ( [ child , newGroup , mergeAt , newPath ] ) ; } else { assert ( edge . transition . kind === 'RootTypeResolution' , ( ) => `Unexpected non-collecting edge ${ edge }` ) ; const rootKind = edge . transition . rootKind ; assert ( ! conditions , ( ) => `Root type resolution edge ${ edge } should not have conditions` ) ; assert ( isObjectType ( edge . head . type ) && isObjectType ( edge . tail . type ) , ( ) => `Expected an objects for the vertices of ${ edge }` ) ; const type = edge . tail . type ; assert ( type === type . schema ( ) . schemaDefinition . rootType ( rootKind ) , ( ) => `Expected ${ type } to be the root ${ rootKind } type, but that is ${ type . schema ( ) . schemaDefinition . rootType ( rootKind ) }` ) ; group . addSelection ( path . concat ( new Field ( ( edge . head . type as CompositeType ) . typenameField ( ) ! ) ) ) ; const newGroup = dependencyGraph . newRootTypeFetchGroup ( edge . tail . source , rootKind , type , mergeAt , group , path ) ; const newPath = createNewFetchSelectionContext ( type , undefined , operation ) [ 1 ] ; stack . push ( [ child , newGroup , mergeAt , newPath ] ) ; } } else if ( edge === null ) { const newPath = operation . appliedDirectives . length === 0 ? path : path . concat ( operation ) ; stack . push ( [ child , group , mergeAt , newPath ] ) ; } else { assert ( edge . head . source === edge . tail . source , ( ) => `Collecting edge ${ edge } for ${ operation } should not change the underlying subgraph` ) ; let updatedGroup = group ; let updatedMergeAt = mergeAt ; let updatedPath = path ; if ( conditions ) { [ updatedGroup , updatedMergeAt , updatedPath ] = handleRequires ( dependencyGraph , edge , conditions , group , mergeAt , path ) ; } const newMergeAt = operation . kind === 'Field' ? addToResponsePath ( updatedMergeAt , operation . responseName ( ) , ( edge . transition as FieldCollection ) . definition . type ! ) : updatedMergeAt ; stack . push ( [ child , updatedGroup , newMergeAt , updatedPath . concat ( operation ) ] ) ; } } } } return createdGroups ; } function addTypenameFieldForAbstractTypes ( selectionSet ) { for ( const selection of selectionSet . selections ( ) ) { if ( selection . kind == 'FieldSelection' ) { const fieldBaseType = baseType ( selection . field . definition . type ! ) ; if ( isAbstractType ( fieldBaseType ) ) { selection . selectionSet ! . add ( new FieldSelection ( new Field ( fieldBaseType . typenameField ( ) ! ) ) ) ; } if ( selection . selectionSet ) { addTypenameFieldForAbstractTypes ( selection . selectionSet ) ; } } else { addTypenameFieldForAbstractTypes ( selection . selectionSet ) ; } } } function handleRequires ( dependencyGraph , edge , requiresConditions , group , mergeAt , path ) { const entityType = edge . head . type as ObjectType ; if ( ! group . isTopLevel && path . length == 1 && path [ 0 ] . kind === 'FragmentElement' ) { const originalInputs = group . clonedInputs ( ) ! ; const newGroup = dependencyGraph . newKeyFetchGroup ( group . subgraphName , group . mergeAt ! ) ; newGroup . addInputs ( originalInputs . forRead ( ) ) ; const createdGroups = computeGroupsForTree ( dependencyGraph , requiresConditions , newGroup , mergeAt , path ) ; if ( createdGroups . length == 0 ) { group . mergeIn ( newGroup , path ) ; return [ group , mergeAt , path ] ; } const newGroupIsUseless = newGroup . inputs ! . contains ( newGroup . selection ) ; const parents = dependencyGraph . dependencies ( group ) ; const pathInParent = dependencyGraph . pathInParent ( group ) ; const unmergedGroups = [ ] ; if ( newGroupIsUseless ) { for ( const created of createdGroups ) { if ( pathInParent && created . subgraphName === parents [ 0 ] . subgraphName && sameMergeAt ( created . mergeAt , group . mergeAt ) ) { parents [ 0 ] . mergeIn ( created , pathInParent ) ; } else { created . removeDependencyOn ( newGroup ) ; created . addDependencyOn ( parents ) ; unmergedGroups . push ( created ) ; } } dependencyGraph . remove ( newGroup ) ; } else { group . mergeIn ( newGroup , path ) ; for ( const created of createdGroups ) { if ( pathInParent && created . subgraphName === parents [ 0 ] . subgraphName && sameMergeAt ( created . mergeAt , group . mergeAt ) && originalInputs . forRead ( ) . contains ( created . inputs ! ) ) { parents [ 0 ] . mergeIn ( created , pathInParent ) ; } else { unmergedGroups . push ( created ) ; } } } if ( unmergedGroups . length == 0 ) { group . addInputs ( inputsForRequire ( dependencyGraph . federatedQueryGraph , entityType , edge , false ) [ 0 ] ) ; return [ group , mergeAt , path ] ; } const postRequireGroup = dependencyGraph . newKeyFetchGroup ( group . subgraphName , group . mergeAt ! ) ; postRequireGroup . addDependencyOn ( unmergedGroups ) ; const [ inputs , newPath ] = inputsForRequire ( dependencyGraph . federatedQueryGraph , entityType , edge ) ; postRequireGroup . addInputs ( inputs ) ; return [ postRequireGroup , mergeAt , newPath ] ; } else { const createdGroups = computeGroupsForTree ( dependencyGraph , requiresConditions , group , mergeAt , path ) ; if ( createdGroups . length == 0 ) { return [ group , mergeAt , path ] ; } const newGroup = dependencyGraph . newKeyFetchGroup ( group . subgraphName , mergeAt ) ; newGroup . addDependencyOn ( createdGroups ) ; const [ inputs , newPath ] = inputsForRequire ( dependencyGraph . federatedQueryGraph , entityType , edge ) ; debug . log ( `Trying to add ${ inputs } to ${ newGroup }` ) ; newGroup . addInputs ( inputs ) ; return [ newGroup , mergeAt , newPath ] ; } } function inputsForRequire ( graph , entityType , edge , includeKeyInputs = true ) { const typeCast = new FragmentElement ( entityType , entityType . name ) ; const fullSelectionSet = new SelectionSet ( entityType ) ; fullSelectionSet . add ( new FieldSelection ( new Field ( entityType . typenameField ( ) ! ) ) ) ; fullSelectionSet . mergeIn ( edge . conditions ! ) ; if ( includeKeyInputs ) { const keyCondition = getLocallySatisfiableKey ( graph , edge . head ) ; assert ( keyCondition , ( ) => `Due to @require, validation should have required a key to be present for ${ edge }` ) ; fullSelectionSet . mergeIn ( keyCondition ) ; } return [ selectionOfElement ( typeCast , fullSelectionSet ) , [ typeCast ] ] ; } const representationsVariable = new Variable ( 'representations' ) ; function representationsVariableDefinition ( schema ) { const anyType = schema . type ( '_Any' ) ; assert ( anyType , `Cannot find _Any type in schema` ) ; const representationsType = new NonNullType ( new ListType ( new NonNullType ( anyType ) ) ) ; return new VariableDefinition ( schema , representationsVariable , representationsType ) ; } function operationForEntitiesFetch ( subgraphSchema , selectionSet , allVariableDefinitions , fragments ? ) { const variableDefinitions = new VariableDefinitions ( ) ; variableDefinitions . add ( representationsVariableDefinition ( subgraphSchema ) ) ; variableDefinitions . addAll ( allVariableDefinitions . filter ( selectionSet . usedVariables ( ) ) ) ; const queryType = subgraphSchema . schemaDefinition . rootType ( 'query' ) ; assert ( queryType , `Subgraphs should always have a query root (they should at least provides _entities)` ) ; const entities = queryType . field ( '_entities' ) ; assert ( entities , `Subgraphs should always have the _entities field` ) ; const entitiesCall = new SelectionSet ( queryType ) ; entitiesCall . add ( new FieldSelection ( new Field ( entities , { 'representations' : representationsVariable } , variableDefinitions ) , selectionSet ) ) ; return operationToDocument ( new Operation ( 'query' , entitiesCall , variableDefinitions ) . optimize ( fragments ) ) ; } function flatWrap ( kind , nodes ) { assert ( nodes . length !== 0 , 'programming error: should always be called with nodes' ) ; if ( nodes . length === 1 ) { return nodes [ 0 ] ; } return { kind , nodes : nodes . flatMap ( n => ( n . kind === kind ? n . nodes : [ n ] ) ) , } ; } function operationForQueryFetch ( rootKind , selectionSet , allVariableDefinitions , fragments ? ) { const operation = new Operation ( rootKind , selectionSet , allVariableDefinitions . filter ( selectionSet . usedVariables ( ) ) ) . optimize ( fragments ) ; return operationToDocument ( operation ) ; }