import { inspect } from '../../jsutils/inspect' ; import type { Maybe } from '../../jsutils/Maybe' ; import type { ObjMap } from '../../jsutils/ObjMap' ; import { GraphQLError } from '../../error/GraphQLError' ; import type { ArgumentNode , FieldNode , FragmentDefinitionNode , SelectionSetNode , ValueNode , } from '../../language/ast' ; import { Kind } from '../../language/kinds' ; import { print } from '../../language/printer' ; import type { ASTVisitor } from '../../language/visitor' ; import type { GraphQLField , GraphQLNamedType , GraphQLOutputType , } from '../../type/definition' ; import { getNamedType , isInterfaceType , isLeafType , isListType , isNonNullType , isObjectType , } from '../../type/definition' ; import { sortValueNode } from '../../utilities/sortValueNode' ; import { typeFromAST } from '../../utilities/typeFromAST' ; import type { ValidationContext } from '../ValidationContext' ; function reasonMessage ( reason ) { if ( Array . isArray ( reason ) ) { return reason . map ( ( [ responseName , subReason ] ) => `subfields "${ responseName }" conflict because ` + reasonMessage ( subReason ) ) . join ( ' and ' ) ; } return reason ; } /**
 * Overlapping fields can be merged
 *
 * A selection set is only valid if all fields (including spreading any
 * fragments) either correspond to distinct response names or can be merged
 * without ambiguity.
 *
 * See https://spec.graphql.org/draft/#sec-Field-Selection-Merging
 */ export function OverlappingFieldsCanBeMergedRule ( context ) { const comparedFragmentPairs = new PairSet ( ) ; const cachedFieldsAndFragmentNames = new Map ( ) ; return { SelectionSet ( selectionSet ) { const conflicts = findConflictsWithinSelectionSet ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , context . getParentType ( ) , selectionSet ) ; for ( const [ [ responseName , reason ] , fields1 , fields2 ] of conflicts ) { const reasonMsg = reasonMessage ( reason ) ; context . reportError ( new GraphQLError ( `Fields "${ responseName }" conflict because ${ reasonMsg }. Use different aliases on the fields to fetch both if this was intentional.` , fields1 . concat ( fields2 ) ) ) ; } } , } ; } type Conflict = [ ConflictReason , Array < FieldNode > , Array < FieldNode > ] ; type ConflictReason = [ string , ConflictReasonMessage ] ; type ConflictReasonMessage = string | Array < ConflictReason > ; type NodeAndDef = [ Maybe < GraphQLNamedType > , FieldNode , Maybe < GraphQLField < unknown , unknown > > ] ; type NodeAndDefCollection = ObjMap < Array < NodeAndDef > > ; type FragmentNames = Array < string > ; type FieldsAndFragmentNames = readonly [ NodeAndDefCollection , FragmentNames ] ; /**
 * Algorithm:
 *
 * Conflicts occur when two fields exist in a query which will produce the same
 * response name, but represent differing values, thus creating a conflict.
 * The algorithm below finds all conflicts via making a series of comparisons
 * between fields. In order to compare as few fields as possible, this makes
 * a series of comparisons "within" sets of fields and "between" sets of fields.
 *
 * Given any selection set, a collection produces both a set of fields by
 * also including all inline fragments, as well as a list of fragments
 * referenced by fragment spreads.
 *
 * A) Each selection set represented in the document first compares "within" its
 * collected set of fields, finding any conflicts between every pair of
 * overlapping fields.
 * Note: This is the *only time* that a the fields "within" a set are compared
 * to each other. After this only fields "between" sets are compared.
 *
 * B) Also, if any fragment is referenced in a selection set, then a
 * comparison is made "between" the original set of fields and the
 * referenced fragment.
 *
 * C) Also, if multiple fragments are referenced, then comparisons
 * are made "between" each referenced fragment.
 *
 * D) When comparing "between" a set of fields and a referenced fragment, first
 * a comparison is made between each field in the original set of fields and
 * each field in the the referenced set of fields.
 *
 * E) Also, if any fragment is referenced in the referenced selection set,
 * then a comparison is made "between" the original set of fields and the
 * referenced fragment (recursively referring to step D).
 *
 * F) When comparing "between" two fragments, first a comparison is made between
 * each field in the first referenced set of fields and each field in the the
 * second referenced set of fields.
 *
 * G) Also, any fragments referenced by the first must be compared to the
 * second, and any fragments referenced by the second must be compared to the
 * first (recursively referring to step F).
 *
 * H) When comparing two fields, if both have selection sets, then a comparison
 * is made "between" both selection sets, first comparing the set of fields in
 * the first selection set with the set of fields in the second.
 *
 * I) Also, if any fragment is referenced in either selection set, then a
 * comparison is made "between" the other set of fields and the
 * referenced fragment.
 *
 * J) Also, if two fragments are referenced in both selection sets, then a
 * comparison is made "between" the two fragments.
 *
 */ function findConflictsWithinSelectionSet ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , parentType , selectionSet ) { const conflicts = [ ] ; const [ fieldMap , fragmentNames ] = getFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , parentType , selectionSet ) ; collectConflictsWithin ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , fieldMap ) ; if ( fragmentNames . length !== 0 ) { for ( let i = 0 ; i < fragmentNames . length ; i ++ ) { collectConflictsBetweenFieldsAndFragment ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , false , fieldMap , fragmentNames [ i ] ) ; for ( let j = i + 1 ; j < fragmentNames . length ; j ++ ) { collectConflictsBetweenFragments ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , false , fragmentNames [ i ] , fragmentNames [ j ] ) ; } } } return conflicts ; } function collectConflictsBetweenFieldsAndFragment ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap , fragmentName ) { const fragment = context . getFragment ( fragmentName ) ; if ( ! fragment ) { return ; } const [ fieldMap2 , referencedFragmentNames ] = getReferencedFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , fragment ) ; if ( fieldMap === fieldMap2 ) { return ; } collectConflictsBetween ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap , fieldMap2 ) ; for ( const referencedFragmentName of referencedFragmentNames ) { if ( comparedFragmentPairs . has ( referencedFragmentName , fragmentName , areMutuallyExclusive ) ) { continue ; } comparedFragmentPairs . add ( referencedFragmentName , fragmentName , areMutuallyExclusive ) ; collectConflictsBetweenFieldsAndFragment ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap , referencedFragmentName ) ; } } function collectConflictsBetweenFragments ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fragmentName1 , fragmentName2 ) { if ( fragmentName1 === fragmentName2 ) { return ; } if ( comparedFragmentPairs . has ( fragmentName1 , fragmentName2 , areMutuallyExclusive ) ) { return ; } comparedFragmentPairs . add ( fragmentName1 , fragmentName2 , areMutuallyExclusive ) ; const fragment1 = context . getFragment ( fragmentName1 ) ; const fragment2 = context . getFragment ( fragmentName2 ) ; if ( ! fragment1 || ! fragment2 ) { return ; } const [ fieldMap1 , referencedFragmentNames1 ] = getReferencedFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , fragment1 ) ; const [ fieldMap2 , referencedFragmentNames2 ] = getReferencedFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , fragment2 ) ; collectConflictsBetween ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap1 , fieldMap2 ) ; for ( const referencedFragmentName2 of referencedFragmentNames2 ) { collectConflictsBetweenFragments ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fragmentName1 , referencedFragmentName2 ) ; } for ( const referencedFragmentName1 of referencedFragmentNames1 ) { collectConflictsBetweenFragments ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , referencedFragmentName1 , fragmentName2 ) ; } } function findConflictsBetweenSubSelectionSets ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , parentType1 , selectionSet1 , parentType2 , selectionSet2 ) { const conflicts = [ ] ; const [ fieldMap1 , fragmentNames1 ] = getFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , parentType1 , selectionSet1 ) ; const [ fieldMap2 , fragmentNames2 ] = getFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , parentType2 , selectionSet2 ) ; collectConflictsBetween ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap1 , fieldMap2 ) ; for ( const fragmentName2 of fragmentNames2 ) { collectConflictsBetweenFieldsAndFragment ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap1 , fragmentName2 ) ; } for ( const fragmentName1 of fragmentNames1 ) { collectConflictsBetweenFieldsAndFragment ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fieldMap2 , fragmentName1 ) ; } for ( const fragmentName1 of fragmentNames1 ) { for ( const fragmentName2 of fragmentNames2 ) { collectConflictsBetweenFragments ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , fragmentName1 , fragmentName2 ) ; } } return conflicts ; } function collectConflictsWithin ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , fieldMap ) { for ( const [ responseName , fields ] of Object . entries ( fieldMap ) ) { if ( fields . length > 1 ) { for ( let i = 0 ; i < fields . length ; i ++ ) { for ( let j = i + 1 ; j < fields . length ; j ++ ) { const conflict = findConflict ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , false , responseName , fields [ i ] , fields [ j ] ) ; if ( conflict ) { conflicts . push ( conflict ) ; } } } } } } function collectConflictsBetween ( context , conflicts , cachedFieldsAndFragmentNames , comparedFragmentPairs , parentFieldsAreMutuallyExclusive , fieldMap1 , fieldMap2 ) { for ( const [ responseName , fields1 ] of Object . entries ( fieldMap1 ) ) { const fields2 = fieldMap2 [ responseName ] ; if ( fields2 ) { for ( const field1 of fields1 ) { for ( const field2 of fields2 ) { const conflict = findConflict ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , parentFieldsAreMutuallyExclusive , responseName , field1 , field2 ) ; if ( conflict ) { conflicts . push ( conflict ) ; } } } } } } function findConflict ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , parentFieldsAreMutuallyExclusive , responseName , field1 , field2 ) { const [ parentType1 , node1 , def1 ] = field1 ; const [ parentType2 , node2 , def2 ] = field2 ; const areMutuallyExclusive = parentFieldsAreMutuallyExclusive || ( parentType1 !== parentType2 && isObjectType ( parentType1 ) && isObjectType ( parentType2 ) ) ; if ( ! areMutuallyExclusive ) { const name1 = node1 . name . value ; const name2 = node2 . name . value ; if ( name1 !== name2 ) { return [ [ responseName , `"${ name1 }" and "${ name2 }" are different fields` ] , [ node1 ] , [ node2 ] , ] ; } const args1 = node1 . arguments ?? [ ] ; const args2 = node2 . arguments ?? [ ] ; if ( ! sameArguments ( args1 , args2 ) ) { return [ [ responseName , 'they have differing arguments' ] , [ node1 ] , [ node2 ] , ] ; } } const type1 = def1 ?. type ; const type2 = def2 ?. type ; if ( type1 && type2 && doTypesConflict ( type1 , type2 ) ) { return [ [ responseName , `they return conflicting types "${ inspect ( type1 ) }" and "${ inspect ( type2 ) }"` , ] , [ node1 ] , [ node2 ] , ] ; } const selectionSet1 = node1 . selectionSet ; const selectionSet2 = node2 . selectionSet ; if ( selectionSet1 && selectionSet2 ) { const conflicts = findConflictsBetweenSubSelectionSets ( context , cachedFieldsAndFragmentNames , comparedFragmentPairs , areMutuallyExclusive , getNamedType ( type1 ) , selectionSet1 , getNamedType ( type2 ) , selectionSet2 ) ; return subfieldConflicts ( conflicts , responseName , node1 , node2 ) ; } } function sameArguments ( arguments1 , arguments2 ) { if ( arguments1 . length !== arguments2 . length ) { return false ; } return arguments1 . every ( ( argument1 ) => { const argument2 = arguments2 . find ( ( argument ) => argument . name . value === argument1 . name . value ) ; if ( ! argument2 ) { return false ; } return stringifyValue ( argument1 . value ) === stringifyValue ( argument2 . value ) ; } ) ; } function stringifyValue ( value ) { return print ( sortValueNode ( value ) ) ; } function doTypesConflict ( type1 , type2 ) { if ( isListType ( type1 ) ) { return isListType ( type2 ) ? doTypesConflict ( type1 . ofType , type2 . ofType ) : true ; } if ( isListType ( type2 ) ) { return true ; } if ( isNonNullType ( type1 ) ) { return isNonNullType ( type2 ) ? doTypesConflict ( type1 . ofType , type2 . ofType ) : true ; } if ( isNonNullType ( type2 ) ) { return true ; } if ( isLeafType ( type1 ) || isLeafType ( type2 ) ) { return type1 !== type2 ; } return false ; } function getFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , parentType , selectionSet ) { const cached = cachedFieldsAndFragmentNames . get ( selectionSet ) ; if ( cached ) { return cached ; } const nodeAndDefs = Object . create ( null ) ; const fragmentNames = Object . create ( null ) ; _collectFieldsAndFragmentNames ( context , parentType , selectionSet , nodeAndDefs , fragmentNames ) ; const result = [ nodeAndDefs , Object . keys ( fragmentNames ) ] as const ; cachedFieldsAndFragmentNames . set ( selectionSet , result ) ; return result ; } function getReferencedFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , fragment ) { const cached = cachedFieldsAndFragmentNames . get ( fragment . selectionSet ) ; if ( cached ) { return cached ; } const fragmentType = typeFromAST ( context . getSchema ( ) , fragment . typeCondition ) ; return getFieldsAndFragmentNames ( context , cachedFieldsAndFragmentNames , fragmentType , fragment . selectionSet ) ; } function _collectFieldsAndFragmentNames ( context , parentType , selectionSet , nodeAndDefs , fragmentNames ) { for ( const selection of selectionSet . selections ) { switch ( selection . kind ) { case Kind . FIELD : { const fieldName = selection . name . value ; let fieldDef ; if ( isObjectType ( parentType ) || isInterfaceType ( parentType ) ) { fieldDef = parentType . getFields ( ) [ fieldName ] ; } const responseName = selection . alias ? selection . alias . value : fieldName ; if ( ! nodeAndDefs [ responseName ] ) { nodeAndDefs [ responseName ] = [ ] ; } nodeAndDefs [ responseName ] . push ( [ parentType , selection , fieldDef ] ) ; break ; } case Kind . FRAGMENT_SPREAD : fragmentNames [ selection . name . value ] = true ; break ; case Kind . INLINE_FRAGMENT : { const typeCondition = selection . typeCondition ; const inlineFragmentType = typeCondition ? typeFromAST ( context . getSchema ( ) , typeCondition ) : parentType ; _collectFieldsAndFragmentNames ( context , inlineFragmentType , selection . selectionSet , nodeAndDefs , fragmentNames ) ; break ; } } } } function subfieldConflicts ( conflicts , responseName , node1 , node2 ) { if ( conflicts . length > 0 ) { return [ [ responseName , conflicts . map ( ( [ reason ] ) => reason ) ] , [ node1 , ... conflicts . map ( ( [ , fields1 ] ) => fields1 ) . flat ( ) ] , [ node2 , ... conflicts . map ( ( [ , , fields2 ] ) => fields2 ) . flat ( ) ] , ] ; } } /**
 * A way to keep track of pairs of things when the ordering of the pair does not matter.
 */ class PairSet { _data : Map < string , Map < string , boolean > > ; constructor ( ) { this . _data = new Map ( ) ; } has ( a , b , areMutuallyExclusive ) { const [ key1 , key2 ] = a < b ? [ a , b ] : [ b , a ] ; const result = this . _data . get ( key1 ) ?. get ( key2 ) ; if ( result === undefined ) { return false ; } return areMutuallyExclusive ? true : areMutuallyExclusive === result ; } add ( a , b , areMutuallyExclusive ) { const [ key1 , key2 ] = a < b ? [ a , b ] : [ b , a ] ; const map = this . _data . get ( key1 ) ; if ( map === undefined ) { this . _data . set ( key1 , new Map ( [ [ key2 , areMutuallyExclusive ] ] ) ) ; } else { map . set ( key2 , areMutuallyExclusive ) ; } } }