Source file src/github.com/vektah/gqlparser/v2/validator/rules/overlapping_fields_can_be_merged.go

Documentation: github.com/vektah/gqlparser/v2/validator/rules

     1  package validator
     2  
     3  import (
     4  	"bytes"
     5  	"fmt"
     6  	"reflect"
     7  
     8  	"github.com/vektah/gqlparser/v2/ast"
     9  
    10  	//nolint:revive // Validator rules each use dot imports for convenience.
    11  	. "github.com/vektah/gqlparser/v2/validator"
    12  )
    13  
    14  func init() {
    15  
    16  	AddRule("OverlappingFieldsCanBeMerged", func(observers *Events, addError AddErrFunc) {
    17  		/**
    18  		 * Algorithm:
    19  		 *
    20  		 * Conflicts occur when two fields exist in a query which will produce the same
    21  		 * response name, but represent differing values, thus creating a conflict.
    22  		 * The algorithm below finds all conflicts via making a series of comparisons
    23  		 * between fields. In order to compare as few fields as possible, this makes
    24  		 * a series of comparisons "within" sets of fields and "between" sets of fields.
    25  		 *
    26  		 * Given any selection set, a collection produces both a set of fields by
    27  		 * also including all inline fragments, as well as a list of fragments
    28  		 * referenced by fragment spreads.
    29  		 *
    30  		 * A) Each selection set represented in the document first compares "within" its
    31  		 * collected set of fields, finding any conflicts between every pair of
    32  		 * overlapping fields.
    33  		 * Note: This is the *only time* that a the fields "within" a set are compared
    34  		 * to each other. After this only fields "between" sets are compared.
    35  		 *
    36  		 * B) Also, if any fragment is referenced in a selection set, then a
    37  		 * comparison is made "between" the original set of fields and the
    38  		 * referenced fragment.
    39  		 *
    40  		 * C) Also, if multiple fragments are referenced, then comparisons
    41  		 * are made "between" each referenced fragment.
    42  		 *
    43  		 * D) When comparing "between" a set of fields and a referenced fragment, first
    44  		 * a comparison is made between each field in the original set of fields and
    45  		 * each field in the the referenced set of fields.
    46  		 *
    47  		 * E) Also, if any fragment is referenced in the referenced selection set,
    48  		 * then a comparison is made "between" the original set of fields and the
    49  		 * referenced fragment (recursively referring to step D).
    50  		 *
    51  		 * F) When comparing "between" two fragments, first a comparison is made between
    52  		 * each field in the first referenced set of fields and each field in the the
    53  		 * second referenced set of fields.
    54  		 *
    55  		 * G) Also, any fragments referenced by the first must be compared to the
    56  		 * second, and any fragments referenced by the second must be compared to the
    57  		 * first (recursively referring to step F).
    58  		 *
    59  		 * H) When comparing two fields, if both have selection sets, then a comparison
    60  		 * is made "between" both selection sets, first comparing the set of fields in
    61  		 * the first selection set with the set of fields in the second.
    62  		 *
    63  		 * I) Also, if any fragment is referenced in either selection set, then a
    64  		 * comparison is made "between" the other set of fields and the
    65  		 * referenced fragment.
    66  		 *
    67  		 * J) Also, if two fragments are referenced in both selection sets, then a
    68  		 * comparison is made "between" the two fragments.
    69  		 *
    70  		 */
    71  
    72  		m := &overlappingFieldsCanBeMergedManager{
    73  			comparedFragmentPairs: pairSet{data: make(map[string]map[string]bool)},
    74  		}
    75  
    76  		observers.OnOperation(func(walker *Walker, operation *ast.OperationDefinition) {
    77  			m.walker = walker
    78  			conflicts := m.findConflictsWithinSelectionSet(operation.SelectionSet)
    79  			for _, conflict := range conflicts {
    80  				conflict.addFieldsConflictMessage(addError)
    81  			}
    82  		})
    83  		observers.OnField(func(walker *Walker, field *ast.Field) {
    84  			if walker.CurrentOperation == nil {
    85  				// When checking both Operation and Fragment, errors are duplicated when processing FragmentDefinition referenced from Operation
    86  				return
    87  			}
    88  			m.walker = walker
    89  			conflicts := m.findConflictsWithinSelectionSet(field.SelectionSet)
    90  			for _, conflict := range conflicts {
    91  				conflict.addFieldsConflictMessage(addError)
    92  			}
    93  		})
    94  		observers.OnInlineFragment(func(walker *Walker, inlineFragment *ast.InlineFragment) {
    95  			m.walker = walker
    96  			conflicts := m.findConflictsWithinSelectionSet(inlineFragment.SelectionSet)
    97  			for _, conflict := range conflicts {
    98  				conflict.addFieldsConflictMessage(addError)
    99  			}
   100  		})
   101  		observers.OnFragment(func(walker *Walker, fragment *ast.FragmentDefinition) {
   102  			m.walker = walker
   103  			conflicts := m.findConflictsWithinSelectionSet(fragment.SelectionSet)
   104  			for _, conflict := range conflicts {
   105  				conflict.addFieldsConflictMessage(addError)
   106  			}
   107  		})
   108  	})
   109  }
   110  
   111  type pairSet struct {
   112  	data map[string]map[string]bool
   113  }
   114  
   115  func (pairSet *pairSet) Add(a *ast.FragmentSpread, b *ast.FragmentSpread, areMutuallyExclusive bool) {
   116  	add := func(a *ast.FragmentSpread, b *ast.FragmentSpread) {
   117  		m := pairSet.data[a.Name]
   118  		if m == nil {
   119  			m = make(map[string]bool)
   120  			pairSet.data[a.Name] = m
   121  		}
   122  		m[b.Name] = areMutuallyExclusive
   123  	}
   124  	add(a, b)
   125  	add(b, a)
   126  }
   127  
   128  func (pairSet *pairSet) Has(a *ast.FragmentSpread, b *ast.FragmentSpread, areMutuallyExclusive bool) bool {
   129  	am, ok := pairSet.data[a.Name]
   130  	if !ok {
   131  		return false
   132  	}
   133  	result, ok := am[b.Name]
   134  	if !ok {
   135  		return false
   136  	}
   137  
   138  	// areMutuallyExclusive being false is a superset of being true,
   139  	// hence if we want to know if this PairSet "has" these two with no
   140  	// exclusivity, we have to ensure it was added as such.
   141  	if !areMutuallyExclusive {
   142  		return !result
   143  	}
   144  
   145  	return true
   146  }
   147  
   148  type sequentialFieldsMap struct {
   149  	// We can't use map[string][]*ast.Field. because map is not stable...
   150  	seq  []string
   151  	data map[string][]*ast.Field
   152  }
   153  
   154  type fieldIterateEntry struct {
   155  	ResponseName string
   156  	Fields       []*ast.Field
   157  }
   158  
   159  func (m *sequentialFieldsMap) Push(responseName string, field *ast.Field) {
   160  	fields, ok := m.data[responseName]
   161  	if !ok {
   162  		m.seq = append(m.seq, responseName)
   163  	}
   164  	fields = append(fields, field)
   165  	m.data[responseName] = fields
   166  }
   167  
   168  func (m *sequentialFieldsMap) Get(responseName string) ([]*ast.Field, bool) {
   169  	fields, ok := m.data[responseName]
   170  	return fields, ok
   171  }
   172  
   173  func (m *sequentialFieldsMap) Iterator() [][]*ast.Field {
   174  	fieldsList := make([][]*ast.Field, 0, len(m.seq))
   175  	for _, responseName := range m.seq {
   176  		fields := m.data[responseName]
   177  		fieldsList = append(fieldsList, fields)
   178  	}
   179  	return fieldsList
   180  }
   181  
   182  func (m *sequentialFieldsMap) KeyValueIterator() []*fieldIterateEntry {
   183  	fieldEntriesList := make([]*fieldIterateEntry, 0, len(m.seq))
   184  	for _, responseName := range m.seq {
   185  		fields := m.data[responseName]
   186  		fieldEntriesList = append(fieldEntriesList, &fieldIterateEntry{
   187  			ResponseName: responseName,
   188  			Fields:       fields,
   189  		})
   190  	}
   191  	return fieldEntriesList
   192  }
   193  
   194  type conflictMessageContainer struct {
   195  	Conflicts []*ConflictMessage
   196  }
   197  
   198  type ConflictMessage struct {
   199  	Message      string
   200  	ResponseName string
   201  	Names        []string
   202  	SubMessage   []*ConflictMessage
   203  	Position     *ast.Position
   204  }
   205  
   206  func (m *ConflictMessage) String(buf *bytes.Buffer) {
   207  	if len(m.SubMessage) == 0 {
   208  		buf.WriteString(m.Message)
   209  		return
   210  	}
   211  
   212  	for idx, subMessage := range m.SubMessage {
   213  		buf.WriteString(`subfields "`)
   214  		buf.WriteString(subMessage.ResponseName)
   215  		buf.WriteString(`" conflict because `)
   216  		subMessage.String(buf)
   217  		if idx != len(m.SubMessage)-1 {
   218  			buf.WriteString(" and ")
   219  		}
   220  	}
   221  }
   222  
   223  func (m *ConflictMessage) addFieldsConflictMessage(addError AddErrFunc) {
   224  	var buf bytes.Buffer
   225  	m.String(&buf)
   226  	addError(
   227  		Message(`Fields "%s" conflict because %s. Use different aliases on the fields to fetch both if this was intentional.`, m.ResponseName, buf.String()),
   228  		At(m.Position),
   229  	)
   230  }
   231  
   232  type overlappingFieldsCanBeMergedManager struct {
   233  	walker *Walker
   234  
   235  	// per walker
   236  	comparedFragmentPairs pairSet
   237  	// cachedFieldsAndFragmentNames interface{}
   238  
   239  	// per selectionSet
   240  	comparedFragments map[string]bool
   241  }
   242  
   243  func (m *overlappingFieldsCanBeMergedManager) findConflictsWithinSelectionSet(selectionSet ast.SelectionSet) []*ConflictMessage {
   244  	if len(selectionSet) == 0 {
   245  		return nil
   246  	}
   247  
   248  	fieldsMap, fragmentSpreads := getFieldsAndFragmentNames(selectionSet)
   249  
   250  	var conflicts conflictMessageContainer
   251  
   252  	// (A) Find find all conflicts "within" the fieldMap of this selection set.
   253  	// Note: this is the *only place* `collectConflictsWithin` is called.
   254  	m.collectConflictsWithin(&conflicts, fieldsMap)
   255  
   256  	m.comparedFragments = make(map[string]bool)
   257  	for idx, fragmentSpreadA := range fragmentSpreads {
   258  		// (B) Then collect conflicts between these fieldMap and those represented by
   259  		// each spread fragment name found.
   260  		m.collectConflictsBetweenFieldsAndFragment(&conflicts, false, fieldsMap, fragmentSpreadA)
   261  
   262  		for _, fragmentSpreadB := range fragmentSpreads[idx+1:] {
   263  			// (C) Then compare this fragment with all other fragments found in this
   264  			// selection set to collect conflicts between fragments spread together.
   265  			// This compares each item in the list of fragment names to every other
   266  			// item in that same list (except for itself).
   267  			m.collectConflictsBetweenFragments(&conflicts, false, fragmentSpreadA, fragmentSpreadB)
   268  		}
   269  	}
   270  
   271  	return conflicts.Conflicts
   272  }
   273  
   274  func (m *overlappingFieldsCanBeMergedManager) collectConflictsBetweenFieldsAndFragment(conflicts *conflictMessageContainer, areMutuallyExclusive bool, fieldsMap *sequentialFieldsMap, fragmentSpread *ast.FragmentSpread) {
   275  	if m.comparedFragments[fragmentSpread.Name] {
   276  		return
   277  	}
   278  	m.comparedFragments[fragmentSpread.Name] = true
   279  
   280  	if fragmentSpread.Definition == nil {
   281  		return
   282  	}
   283  
   284  	fieldsMapB, fragmentSpreads := getFieldsAndFragmentNames(fragmentSpread.Definition.SelectionSet)
   285  
   286  	// Do not compare a fragment's fieldMap to itself.
   287  	if reflect.DeepEqual(fieldsMap, fieldsMapB) {
   288  		return
   289  	}
   290  
   291  	// (D) First collect any conflicts between the provided collection of fields
   292  	// and the collection of fields represented by the given fragment.
   293  	m.collectConflictsBetween(conflicts, areMutuallyExclusive, fieldsMap, fieldsMapB)
   294  
   295  	// (E) Then collect any conflicts between the provided collection of fields
   296  	// and any fragment names found in the given fragment.
   297  	baseFragmentSpread := fragmentSpread
   298  	for _, fragmentSpread := range fragmentSpreads {
   299  		if fragmentSpread.Name == baseFragmentSpread.Name {
   300  			continue
   301  		}
   302  		m.collectConflictsBetweenFieldsAndFragment(conflicts, areMutuallyExclusive, fieldsMap, fragmentSpread)
   303  	}
   304  }
   305  
   306  func (m *overlappingFieldsCanBeMergedManager) collectConflictsBetweenFragments(conflicts *conflictMessageContainer, areMutuallyExclusive bool, fragmentSpreadA *ast.FragmentSpread, fragmentSpreadB *ast.FragmentSpread) {
   307  
   308  	var check func(fragmentSpreadA *ast.FragmentSpread, fragmentSpreadB *ast.FragmentSpread)
   309  	check = func(fragmentSpreadA *ast.FragmentSpread, fragmentSpreadB *ast.FragmentSpread) {
   310  
   311  		if fragmentSpreadA.Name == fragmentSpreadB.Name {
   312  			return
   313  		}
   314  
   315  		if m.comparedFragmentPairs.Has(fragmentSpreadA, fragmentSpreadB, areMutuallyExclusive) {
   316  			return
   317  		}
   318  		m.comparedFragmentPairs.Add(fragmentSpreadA, fragmentSpreadB, areMutuallyExclusive)
   319  
   320  		if fragmentSpreadA.Definition == nil {
   321  			return
   322  		}
   323  		if fragmentSpreadB.Definition == nil {
   324  			return
   325  		}
   326  
   327  		fieldsMapA, fragmentSpreadsA := getFieldsAndFragmentNames(fragmentSpreadA.Definition.SelectionSet)
   328  		fieldsMapB, fragmentSpreadsB := getFieldsAndFragmentNames(fragmentSpreadB.Definition.SelectionSet)
   329  
   330  		// (F) First, collect all conflicts between these two collections of fields
   331  		// (not including any nested fragments).
   332  		m.collectConflictsBetween(conflicts, areMutuallyExclusive, fieldsMapA, fieldsMapB)
   333  
   334  		// (G) Then collect conflicts between the first fragment and any nested
   335  		// fragments spread in the second fragment.
   336  		for _, fragmentSpread := range fragmentSpreadsB {
   337  			check(fragmentSpreadA, fragmentSpread)
   338  		}
   339  		// (G) Then collect conflicts between the second fragment and any nested
   340  		// fragments spread in the first fragment.
   341  		for _, fragmentSpread := range fragmentSpreadsA {
   342  			check(fragmentSpread, fragmentSpreadB)
   343  		}
   344  	}
   345  
   346  	check(fragmentSpreadA, fragmentSpreadB)
   347  }
   348  
   349  func (m *overlappingFieldsCanBeMergedManager) findConflictsBetweenSubSelectionSets(areMutuallyExclusive bool, selectionSetA ast.SelectionSet, selectionSetB ast.SelectionSet) *conflictMessageContainer {
   350  	var conflicts conflictMessageContainer
   351  
   352  	fieldsMapA, fragmentSpreadsA := getFieldsAndFragmentNames(selectionSetA)
   353  	fieldsMapB, fragmentSpreadsB := getFieldsAndFragmentNames(selectionSetB)
   354  
   355  	// (H) First, collect all conflicts between these two collections of field.
   356  	m.collectConflictsBetween(&conflicts, areMutuallyExclusive, fieldsMapA, fieldsMapB)
   357  
   358  	// (I) Then collect conflicts between the first collection of fields and
   359  	// those referenced by each fragment name associated with the second.
   360  	for _, fragmentSpread := range fragmentSpreadsB {
   361  		m.comparedFragments = make(map[string]bool)
   362  		m.collectConflictsBetweenFieldsAndFragment(&conflicts, areMutuallyExclusive, fieldsMapA, fragmentSpread)
   363  	}
   364  
   365  	// (I) Then collect conflicts between the second collection of fields and
   366  	// those referenced by each fragment name associated with the first.
   367  	for _, fragmentSpread := range fragmentSpreadsA {
   368  		m.comparedFragments = make(map[string]bool)
   369  		m.collectConflictsBetweenFieldsAndFragment(&conflicts, areMutuallyExclusive, fieldsMapB, fragmentSpread)
   370  	}
   371  
   372  	// (J) Also collect conflicts between any fragment names by the first and
   373  	// fragment names by the second. This compares each item in the first set of
   374  	// names to each item in the second set of names.
   375  	for _, fragmentSpreadA := range fragmentSpreadsA {
   376  		for _, fragmentSpreadB := range fragmentSpreadsB {
   377  			m.collectConflictsBetweenFragments(&conflicts, areMutuallyExclusive, fragmentSpreadA, fragmentSpreadB)
   378  		}
   379  	}
   380  
   381  	if len(conflicts.Conflicts) == 0 {
   382  		return nil
   383  	}
   384  
   385  	return &conflicts
   386  }
   387  
   388  func (m *overlappingFieldsCanBeMergedManager) collectConflictsWithin(conflicts *conflictMessageContainer, fieldsMap *sequentialFieldsMap) {
   389  	for _, fields := range fieldsMap.Iterator() {
   390  		for idx, fieldA := range fields {
   391  			for _, fieldB := range fields[idx+1:] {
   392  				conflict := m.findConflict(false, fieldA, fieldB)
   393  				if conflict != nil {
   394  					conflicts.Conflicts = append(conflicts.Conflicts, conflict)
   395  				}
   396  			}
   397  		}
   398  	}
   399  }
   400  
   401  func (m *overlappingFieldsCanBeMergedManager) collectConflictsBetween(conflicts *conflictMessageContainer, parentFieldsAreMutuallyExclusive bool, fieldsMapA *sequentialFieldsMap, fieldsMapB *sequentialFieldsMap) {
   402  	for _, fieldsEntryA := range fieldsMapA.KeyValueIterator() {
   403  		fieldsB, ok := fieldsMapB.Get(fieldsEntryA.ResponseName)
   404  		if !ok {
   405  			continue
   406  		}
   407  		for _, fieldA := range fieldsEntryA.Fields {
   408  			for _, fieldB := range fieldsB {
   409  				conflict := m.findConflict(parentFieldsAreMutuallyExclusive, fieldA, fieldB)
   410  				if conflict != nil {
   411  					conflicts.Conflicts = append(conflicts.Conflicts, conflict)
   412  				}
   413  			}
   414  		}
   415  	}
   416  }
   417  
   418  func (m *overlappingFieldsCanBeMergedManager) findConflict(parentFieldsAreMutuallyExclusive bool, fieldA *ast.Field, fieldB *ast.Field) *ConflictMessage {
   419  	if fieldA.ObjectDefinition == nil || fieldB.ObjectDefinition == nil {
   420  		return nil
   421  	}
   422  
   423  	areMutuallyExclusive := parentFieldsAreMutuallyExclusive
   424  	if !areMutuallyExclusive {
   425  		tmp := fieldA.ObjectDefinition.Name != fieldB.ObjectDefinition.Name
   426  		tmp = tmp && fieldA.ObjectDefinition.Kind == ast.Object
   427  		tmp = tmp && fieldB.ObjectDefinition.Kind == ast.Object
   428  		tmp = tmp && fieldA.Definition != nil && fieldB.Definition != nil
   429  		areMutuallyExclusive = tmp
   430  	}
   431  
   432  	fieldNameA := fieldA.Name
   433  	if fieldA.Alias != "" {
   434  		fieldNameA = fieldA.Alias
   435  	}
   436  
   437  	if !areMutuallyExclusive {
   438  		// Two aliases must refer to the same field.
   439  		if fieldA.Name != fieldB.Name {
   440  			return &ConflictMessage{
   441  				ResponseName: fieldNameA,
   442  				Message:      fmt.Sprintf(`"%s" and "%s" are different fields`, fieldA.Name, fieldB.Name),
   443  				Position:     fieldB.Position,
   444  			}
   445  		}
   446  
   447  		// Two field calls must have the same arguments.
   448  		if !sameArguments(fieldA.Arguments, fieldB.Arguments) {
   449  			return &ConflictMessage{
   450  				ResponseName: fieldNameA,
   451  				Message:      "they have differing arguments",
   452  				Position:     fieldB.Position,
   453  			}
   454  		}
   455  	}
   456  
   457  	if fieldA.Definition != nil && fieldB.Definition != nil && doTypesConflict(m.walker, fieldA.Definition.Type, fieldB.Definition.Type) {
   458  		return &ConflictMessage{
   459  			ResponseName: fieldNameA,
   460  			Message:      fmt.Sprintf(`they return conflicting types "%s" and "%s"`, fieldA.Definition.Type.String(), fieldB.Definition.Type.String()),
   461  			Position:     fieldB.Position,
   462  		}
   463  	}
   464  
   465  	// Collect and compare sub-fields. Use the same "visited fragment names" list
   466  	// for both collections so fields in a fragment reference are never
   467  	// compared to themselves.
   468  	conflicts := m.findConflictsBetweenSubSelectionSets(areMutuallyExclusive, fieldA.SelectionSet, fieldB.SelectionSet)
   469  	if conflicts == nil {
   470  		return nil
   471  	}
   472  	return &ConflictMessage{
   473  		ResponseName: fieldNameA,
   474  		SubMessage:   conflicts.Conflicts,
   475  		Position:     fieldB.Position,
   476  	}
   477  }
   478  
   479  func sameArguments(args1 []*ast.Argument, args2 []*ast.Argument) bool {
   480  	if len(args1) != len(args2) {
   481  		return false
   482  	}
   483  	for _, arg1 := range args1 {
   484  		var matched bool
   485  		for _, arg2 := range args2 {
   486  			if arg1.Name == arg2.Name && sameValue(arg1.Value, arg2.Value) {
   487  				matched = true
   488  				break
   489  			}
   490  		}
   491  		if !matched {
   492  			return false
   493  		}
   494  	}
   495  	return true
   496  }
   497  
   498  func sameValue(value1 *ast.Value, value2 *ast.Value) bool {
   499  	if value1.Kind != value2.Kind {
   500  		return false
   501  	}
   502  	if value1.Raw != value2.Raw {
   503  		return false
   504  	}
   505  	return true
   506  }
   507  
   508  func doTypesConflict(walker *Walker, type1 *ast.Type, type2 *ast.Type) bool {
   509  	if type1.Elem != nil {
   510  		if type2.Elem != nil {
   511  			return doTypesConflict(walker, type1.Elem, type2.Elem)
   512  		}
   513  		return true
   514  	}
   515  	if type2.Elem != nil {
   516  		return true
   517  	}
   518  	if type1.NonNull && !type2.NonNull {
   519  		return true
   520  	}
   521  	if !type1.NonNull && type2.NonNull {
   522  		return true
   523  	}
   524  
   525  	t1 := walker.Schema.Types[type1.NamedType]
   526  	t2 := walker.Schema.Types[type2.NamedType]
   527  	if (t1.Kind == ast.Scalar || t1.Kind == ast.Enum) && (t2.Kind == ast.Scalar || t2.Kind == ast.Enum) {
   528  		return t1.Name != t2.Name
   529  	}
   530  
   531  	return false
   532  }
   533  
   534  func getFieldsAndFragmentNames(selectionSet ast.SelectionSet) (*sequentialFieldsMap, []*ast.FragmentSpread) {
   535  	fieldsMap := sequentialFieldsMap{
   536  		data: make(map[string][]*ast.Field),
   537  	}
   538  	var fragmentSpreads []*ast.FragmentSpread
   539  
   540  	var walk func(selectionSet ast.SelectionSet)
   541  	walk = func(selectionSet ast.SelectionSet) {
   542  		for _, selection := range selectionSet {
   543  			switch selection := selection.(type) {
   544  			case *ast.Field:
   545  				responseName := selection.Name
   546  				if selection.Alias != "" {
   547  					responseName = selection.Alias
   548  				}
   549  				fieldsMap.Push(responseName, selection)
   550  
   551  			case *ast.InlineFragment:
   552  				walk(selection.SelectionSet)
   553  
   554  			case *ast.FragmentSpread:
   555  				fragmentSpreads = append(fragmentSpreads, selection)
   556  			}
   557  		}
   558  	}
   559  	walk(selectionSet)
   560  
   561  	return &fieldsMap, fragmentSpreads
   562  }
   563  

View as plain text