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

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

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

View as plain text