import { assert , CompositeType , Field , FieldDefinition , FieldSelection , firstOf , FragmentElement , InputType , isLeafType , isNullableType , MultiMap , newDebugLogger , Operation , operationToDocument , Schema , SchemaRootKind , Selection , selectionOfElement , SelectionSet , typenameFieldName , VariableDefinitions } from "@apollo/federation-internals" ; import { Edge , federatedGraphRootTypeName , QueryGraph , subgraphEnteringTransition , GraphPath , RootPath , advancePathWithTransition , Transition , OpGraphPath , advanceSimultaneousPathsWithOperation , ExcludedEdges , QueryGraphState , ExcludedConditions , Unadvanceables , isUnadvanceable , Unadvanceable , noConditionsResolution , ConditionResolution , unsatisfiedConditionsResolution , ConditionResolver , cachingConditionResolver , PathContext , addConditionExclusion , SimultaneousPathsWithLazyIndirectPaths , advanceOptionsToString , } from "@apollo/query-graphs" ; import { print } from "graphql" ; const debug = newDebugLogger ( 'validation' ) ; export class ValidationError extends Error { constructor ( message , readonly supergraphUnsatisfiablePath , readonly subgraphsPaths , readonly witness ) { super ( message ) ; this . name = 'ValidationError' ; } } function validationError ( unsatisfiablePath , subgraphsPaths , subgraphsPathsUnadvanceables ) { const witness = buildWitnessOperation ( unsatisfiablePath ) ; const operation = print ( operationToDocument ( witness ) ) ; const message = `The following supergraph API query:\n${ operation }\n` + 'cannot be satisfied by the subgraphs because:\n' + displayReasons ( subgraphsPathsUnadvanceables ) ; return new ValidationError ( message , unsatisfiablePath , subgraphsPaths , witness ) ; } function isValidationError ( e ) { return e instanceof ValidationError ; } function displayReasons ( reasons ) { const bySubgraph = new MultiMap < string , Unadvanceable > ( ) ; for ( const reason of reasons ) { for ( const unadvanceable of reason . reasons ) { bySubgraph . add ( unadvanceable . sourceSubgraph , unadvanceable ) ; } } return [ ... bySubgraph . entries ( ) ] . map ( ( [ subgraph , reasons ] ) => { let msg = `- from subgraph "${ subgraph }":` ; if ( reasons . length === 1 ) { msg += ' ' + reasons [ 0 ] . details + '.' ; } else { for ( const reason of reasons ) { msg += '\n  - ' + reason . details + '.' ; } } return msg ; } ) . join ( '\n' ) ; } function buildWitnessOperation ( witness ) { assert ( witness . size > 0 , "unsatisfiablePath should contain at least one edge/transition" ) ; const root = witness . root ; return new Operation ( root . rootKind , buildWitnessNextStep ( [ ... witness ] . map ( e => e [ 0 ] ) , 0 ) ! , new VariableDefinitions ( ) ) ; } function buildWitnessNextStep ( edges , index ) { if ( index >= edges . length ) { const lastType = edges [ edges . length - 1 ] . tail . type ; return isLeafType ( lastType ) ? undefined : new SelectionSet ( lastType as CompositeType ) ; } const edge = edges [ index ] ; let selection ; const subSelection = buildWitnessNextStep ( edges , index + 1 ) ; switch ( edge . transition . kind ) { case 'DownCast' : const type = edge . transition . castedType ; selection = selectionOfElement ( new FragmentElement ( edge . transition . sourceType , type . name ) , subSelection ! ) ; break ; case 'FieldCollection' : const field = edge . transition . definition ; selection = new FieldSelection ( buildWitnessField ( field ) , subSelection ) ; break ; case 'SubgraphEnteringTransition' : case 'KeyResolution' : case 'RootTypeResolution' : return subSelection ; } const selectionSet = new SelectionSet ( edge . head . type as CompositeType ) ; selectionSet . add ( selection ) ; return selectionSet ; } function buildWitnessField ( definition ) { const args = Object . create ( null ) ; for ( const argDef of definition . arguments ( ) ) { args [ argDef . name ] = generateWitnessValue ( argDef . type ! ) ; } return new Field ( definition , args , new VariableDefinitions ( ) ) ; } function generateWitnessValue ( type ) { switch ( type . kind ) { case 'ScalarType' : switch ( type . name ) { case 'Int' : return 0 ; case 'Float' : return 3.14 ; case 'Boolean' : return true ; case 'String' : return 'A string value' ; case 'ID' : return '<any id>' ; default : return '<some value>' ; } case 'EnumType' : return type . values [ 0 ] . name ; case 'InputObjectType' : const obj = Object . create ( null ) ; for ( const field of type . fields ( ) ) { if ( field . defaultValue || isNullableType ( field . type ! ) ) { continue ; } obj [ field . name ] = generateWitnessValue ( field . type ! ) ; } return obj ; case 'ListType' : return [ ] ; case 'NonNullType' : return generateWitnessValue ( type . ofType ) ; default : assert ( false , `Unhandled input type ${ type }` ) ; } } export function validateGraphComposition ( supergraph , subgraphs ) { const errors = new ValidationTraversal ( supergraph , subgraphs ) . validate ( ) ; return errors . length > 0 ? { errors } : { } ; } export function computeSubgraphPaths ( supergraphPath , subgraphs ) { try { assert ( ! supergraphPath . hasAnyEdgeConditions ( ) , ( ) => `A supergraph path should not have edge condition paths (as supergraph edges should not have conditions): ${ supergraphPath }` ) ; const supergraphSchema = firstOf ( supergraphPath . graph . sources . values ( ) ) ! ; const initialState = ValidationState . initial ( supergraphPath . graph , supergraphPath . root . rootKind , subgraphs ) ; const conditionResolver = new ConditionValidationResolver ( supergraphSchema , subgraphs ) ; let state = initialState ; let isIncomplete = false ; for ( const [ edge ] of supergraphPath ) { const updated = state . validateTransition ( supergraphSchema , edge , conditionResolver ) ; if ( ! updated ) { isIncomplete = true ; break ; } if ( isValidationError ( updated ) ) { throw updated ; } state = updated ; } return { traversal : state , isComplete : ! isIncomplete } ; } catch ( error ) { if ( error instanceof ValidationError ) { return { error } ; } throw error ; } } function initialSubgraphPaths ( kind , subgraphs ) { const root = subgraphs . root ( kind ) ; assert ( root , ( ) => `The supergraph shouldn't have a ${ kind } root if no subgraphs have one` ) ; assert ( root . type . name == federatedGraphRootTypeName ( kind ) , ( ) => `Unexpected type ${ root . type } for subgraphs root type (expected ${ federatedGraphRootTypeName ( kind ) }` ) ; const initialState = GraphPath . fromGraphRoot < Transition > ( subgraphs , kind ) ! ; return subgraphs . outEdges ( root ) . map ( e => initialState . add ( subgraphEnteringTransition , e , noConditionsResolution ) ) ; } export class ValidationState { constructor ( public readonly supergraphPath , public readonly subgraphPaths ) { } static initial ( supergraph , kind , subgraphs ) { return new ValidationState ( GraphPath . fromGraphRoot ( supergraph , kind ) ! , initialSubgraphPaths ( kind , subgraphs ) ) ; } validateTransition ( supergraphSchema , supergraphEdge , conditionResolver ) { assert ( ! supergraphEdge . conditions , ( ) => `Supergraph edges should not have conditions (${ supergraphEdge })` ) ; const transition = supergraphEdge . transition ; const targetType = supergraphEdge . tail . type ; const newSubgraphPaths = [ ] ; const deadEnds = [ ] ; for ( const path of this . subgraphPaths ) { const options = advancePathWithTransition ( supergraphSchema , path , transition , targetType , conditionResolver . resolver ) ; if ( isUnadvanceable ( options ) ) { deadEnds . push ( options ) ; continue ; } if ( options . length === 0 ) { return undefined ; } newSubgraphPaths . push ( ... options ) ; } const newPath = this . supergraphPath . add ( transition , supergraphEdge , noConditionsResolution ) ; if ( newSubgraphPaths . length === 0 ) { return validationError ( newPath , this . subgraphPaths , deadEnds ) ; } return new ValidationState ( newPath , newSubgraphPaths ) ; } currentSubgraphs ( ) { const subgraphs = [ ] ; for ( const path of this . subgraphPaths ) { const source = path . tail . source ; if ( ! subgraphs . includes ( source ) ) { subgraphs . push ( source ) ; } } return subgraphs ; } toString ( ) { return `${ this . supergraphPath } <=> [${ this . subgraphPaths . map ( s => s . toString ( ) ) . join ( ', ' ) }]` ; } } function isSupersetOrEqual ( maybeSuperset , other ) { return other . every ( v => maybeSuperset . includes ( v ) ) ; } class ValidationTraversal { private readonly supergraphSchema : Schema ; private readonly conditionResolver : ConditionValidationResolver ; private readonly stack : ValidationState [ ] = [ ] ; private readonly previousVisits : QueryGraphState < string [ ] [ ] > ; private readonly validationErrors : ValidationError [ ] = [ ] ; constructor ( supergraph , subgraphs ) { this . supergraphSchema = firstOf ( supergraph . sources . values ( ) ) ! ; this . conditionResolver = new ConditionValidationResolver ( this . supergraphSchema , subgraphs ) ; supergraph . rootKinds ( ) . forEach ( k => this . stack . push ( ValidationState . initial ( supergraph , k , subgraphs ) ) ) ; this . previousVisits = new QueryGraphState ( supergraph ) ; } validate ( ) { while ( this . stack . length > 0 ) { this . handleState ( this . stack . pop ( ) ! ) ; } return this . validationErrors ; } private handleState ( state ) { debug . group ( ( ) => `Validation: ${ this . stack . length + 1 } open states. Validating ${ state }` ) ; const vertex = state . supergraphPath . tail ; const currentSources = state . currentSubgraphs ( ) ; const previousSeenSources = this . previousVisits . getVertexState ( vertex ) ; if ( previousSeenSources ) { for ( const previousSources of previousSeenSources ) { if ( isSupersetOrEqual ( currentSources , previousSources ) ) { debug . groupEnd ( `Has already validated this vertex.` ) ; return ; } } previousSeenSources . push ( currentSources ) ; } else { this . previousVisits . setVertexState ( vertex , [ currentSources ] ) ; } for ( const edge of state . supergraphPath . nextEdges ( ) ) { if ( edge . isEdgeForField ( typenameFieldName ) ) { continue ; } debug . group ( ( ) => `Validating supergraph edge ${ edge }` ) ; const newState = state . validateTransition ( this . supergraphSchema , edge , this . conditionResolver ) ; if ( isValidationError ( newState ) ) { debug . groupEnd ( `Validation error!` ) ; this . validationErrors . push ( newState ) ; continue ; } if ( newState && ! newState . supergraphPath . isTerminal ( ) ) { this . stack . push ( newState ) ; debug . groupEnd ( ( ) => `Reached new state ${ newState }` ) ; } else { debug . groupEnd ( `Reached terminal vertex/cycle` ) ; } } debug . groupEnd ( ) ; } } class ConditionValidationState { constructor ( readonly selection , readonly subgraphOptions ) { } toString ( ) { return `${ this . selection } <=> ${ advanceOptionsToString ( this . subgraphOptions ) }` ; } } class ConditionValidationResolver { readonly resolver : ConditionResolver ; constructor ( private readonly supergraphSchema , private readonly federatedQueryGraph ) { this . resolver = cachingConditionResolver ( federatedQueryGraph , ( edge , context , excludedEdges , excludedConditions ) => this . validateConditions ( edge , context , excludedEdges , excludedConditions ) ) ; } private validateConditions ( edge , context , excludedEdges , excludedConditions ) { const conditions = edge . conditions ! ; excludedConditions = addConditionExclusion ( excludedConditions , conditions ) ; const initialPath = GraphPath . create ( this . federatedQueryGraph , edge . head ) ; const initialOptions = [ new SimultaneousPathsWithLazyIndirectPaths ( [ initialPath ] , context , this . resolver , excludedEdges , excludedConditions ) ] ; const stack = [ ] ; for ( const selection of conditions . selections ( ) ) { stack . push ( new ConditionValidationState ( selection , initialOptions ) ) ; } while ( stack . length > 0 ) { const state = stack . pop ( ) ! ; const newStates = this . advanceState ( state ) ; if ( newStates === null ) { return unsatisfiedConditionsResolution ; } newStates . forEach ( s => stack . push ( s ) ) ; } return { satisfied : true , cost : 1 } ; } private advanceState ( state ) { let newOptions = [ ] ; for ( const paths of state . subgraphOptions ) { const pathsOptions = advanceSimultaneousPathsWithOperation ( this . supergraphSchema , paths , state . selection . element ( ) ) ; if ( ! pathsOptions ) { continue ; } newOptions = newOptions . concat ( pathsOptions ) ; } if ( newOptions . length === 0 ) { return null ; } return state . selection . selectionSet ? state . selection . selectionSet . selections ( ) . map ( s => new ConditionValidationState ( s , newOptions ) ) : [ ] ; } }