package validator
import (
"bytes"
"fmt"
"reflect"
"github.com/vektah/gqlparser/ast"
. "github.com/vektah/gqlparser/validator"
)
func init() {
AddRule("OverlappingFieldsCanBeMerged", func(observers *Events, addError AddErrFunc) {
/**
* 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.
*
*/
m := &overlappingFieldsCanBeMergedManager{
comparedFragmentPairs: pairSet{data: make(map[string]map[string]bool)},
}
observers.OnOperation(func(walker *Walker, operation *ast.OperationDefinition) {
m.walker = walker
conflicts := m.findConflictsWithinSelectionSet(operation.SelectionSet)
for _, conflict := range conflicts {
conflict.addFieldsConflictMessage(addError)
}
})
observers.OnField(func(walker *Walker, field *ast.Field) {
if walker.CurrentOperation == nil {
// When checking both Operation and Fragment, errors are duplicated when processing FragmentDefinition referenced from Operation
return
}
m.walker = walker
conflicts := m.findConflictsWithinSelectionSet(field.SelectionSet)
for _, conflict := range conflicts {
conflict.addFieldsConflictMessage(addError)
}
})
observers.OnInlineFragment(func(walker *Walker, inlineFragment *ast.InlineFragment) {
m.walker = walker
conflicts := m.findConflictsWithinSelectionSet(inlineFragment.SelectionSet)
for _, conflict := range conflicts {
conflict.addFieldsConflictMessage(addError)
}
})
observers.OnFragment(func(walker *Walker, fragment *ast.FragmentDefinition) {
m.walker = walker
conflicts := m.findConflictsWithinSelectionSet(fragment.SelectionSet)
for _, conflict := range conflicts {
conflict.addFieldsConflictMessage(addError)
}
})
})
}
type pairSet struct {
data map[string]map[string]bool
}
func (pairSet *pairSet) Add(a *ast.FragmentSpread, b *ast.FragmentSpread, areMutuallyExclusive bool) {
add := func(a *ast.FragmentSpread, b *ast.FragmentSpread) {
m := pairSet.data[a.Name]
if m == nil {
m = make(map[string]bool)
pairSet.data[a.Name] = m
}
m[b.Name] = areMutuallyExclusive
}
add(a, b)
add(b, a)
}
func (pairSet *pairSet) Has(a *ast.FragmentSpread, b *ast.FragmentSpread, areMutuallyExclusive bool) bool {
am, ok := pairSet.data[a.Name]
if !ok {
return false
}
result, ok := am[b.Name]
if !ok {
return false
}
// areMutuallyExclusive being false is a superset of being true,
// hence if we want to know if this PairSet "has" these two with no
// exclusivity, we have to ensure it was added as such.
if !areMutuallyExclusive {
return !result
}
return true
}
type sequentialFieldsMap struct {
// We can't use map[string][]*ast.Field. because map is not stable...
seq []string
data map[string][]*ast.Field
}
type fieldIterateEntry struct {
ResponseName string
Fields []*ast.Field
}
func (m *sequentialFieldsMap) Push(responseName string, field *ast.Field) {
fields, ok := m.data[responseName]
if !ok {
m.seq = append(m.seq, responseName)
}
fields = append(fields, field)
m.data[responseName] = fields
}
func (m *sequentialFieldsMap) Get(responseName string) ([]*ast.Field, bool) {
fields, ok := m.data[responseName]
return fields, ok
}
func (m *sequentialFieldsMap) Iterator() [][]*ast.Field {
fieldsList := make([][]*ast.Field, 0, len(m.seq))
for _, responseName := range m.seq {
fields := m.data[responseName]
fieldsList = append(fieldsList, fields)
}
return fieldsList
}
func (m *sequentialFieldsMap) KeyValueIterator() []*fieldIterateEntry {
fieldEntriesList := make([]*fieldIterateEntry, 0, len(m.seq))
for _, responseName := range m.seq {
fields := m.data[responseName]
fieldEntriesList = append(fieldEntriesList, &fieldIterateEntry{
ResponseName: responseName,
Fields: fields,
})
}
return fieldEntriesList
}
type conflictMessageContainer struct {
Conflicts []*ConflictMessage
}
type ConflictMessage struct {
Message string
ResponseName string
Names []string
SubMessage []*ConflictMessage
Position *ast.Position
}
func (m *ConflictMessage) String(buf *bytes.Buffer) {
if len(m.SubMessage) == 0 {
buf.WriteString(m.Message)
return
}
for idx, subMessage := range m.SubMessage {
buf.WriteString(`subfields "`)
buf.WriteString(subMessage.ResponseName)
buf.WriteString(`" conflict because `)
subMessage.String(buf)
if idx != len(m.SubMessage)-1 {
buf.WriteString(" and ")
}
}
}
func (m *ConflictMessage) addFieldsConflictMessage(addError AddErrFunc) {
var buf bytes.Buffer
m.String(&buf)
addError(
Message(`Fields "%s" conflict because %s. Use different aliases on the fields to fetch both if this was intentional.`, m.ResponseName, buf.String()),
At(m.Position),
)
}
type overlappingFieldsCanBeMergedManager struct {
walker *Walker
// per walker
comparedFragmentPairs pairSet
// cachedFieldsAndFragmentNames interface{}
// per selectionSet
comparedFragments map[string]bool
}
func (m *overlappingFieldsCanBeMergedManager) findConflictsWithinSelectionSet(selectionSet ast.SelectionSet) []*ConflictMessage {
if len(selectionSet) == 0 {
return nil
}
fieldsMap, fragmentSpreads := getFieldsAndFragmentNames(selectionSet)
var conflicts conflictMessageContainer
// (A) Find find all conflicts "within" the fieldMap of this selection set.
// Note: this is the *only place* `collectConflictsWithin` is called.
m.collectConflictsWithin(&conflicts, fieldsMap)
m.comparedFragments = make(map[string]bool)
for idx, fragmentSpreadA := range fragmentSpreads {
// (B) Then collect conflicts between these fieldMap and those represented by
// each spread fragment name found.
m.collectConflictsBetweenFieldsAndFragment(&conflicts, false, fieldsMap, fragmentSpreadA)
for _, fragmentSpreadB := range fragmentSpreads[idx+1:] {
// (C) Then compare this fragment with all other fragments found in this
// selection set to collect conflicts between fragments spread together.
// This compares each item in the list of fragment names to every other
// item in that same list (except for itself).
m.collectConflictsBetweenFragments(&conflicts, false, fragmentSpreadA, fragmentSpreadB)
}
}
return conflicts.Conflicts
}
func (m *overlappingFieldsCanBeMergedManager) collectConflictsBetweenFieldsAndFragment(conflicts *conflictMessageContainer, areMutuallyExclusive bool, fieldsMap *sequentialFieldsMap, fragmentSpread *ast.FragmentSpread) {
if m.comparedFragments[fragmentSpread.Name] {
return
}
m.comparedFragments[fragmentSpread.Name] = true
if fragmentSpread.Definition == nil {
return
}
fieldsMapB, fragmentSpreads := getFieldsAndFragmentNames(fragmentSpread.Definition.SelectionSet)
// Do not compare a fragment's fieldMap to itself.
if reflect.DeepEqual(fieldsMap, fieldsMapB) {
return
}
// (D) First collect any conflicts between the provided collection of fields
// and the collection of fields represented by the given fragment.
m.collectConflictsBetween(conflicts, areMutuallyExclusive, fieldsMap, fieldsMapB)
// (E) Then collect any conflicts between the provided collection of fields
// and any fragment names found in the given fragment.
baseFragmentSpread := fragmentSpread
for _, fragmentSpread := range fragmentSpreads {
if fragmentSpread.Name == baseFragmentSpread.Name {
continue
}
m.collectConflictsBetweenFieldsAndFragment(conflicts, areMutuallyExclusive, fieldsMap, fragmentSpread)
}
}
func (m *overlappingFieldsCanBeMergedManager) collectConflictsBetweenFragments(conflicts *conflictMessageContainer, areMutuallyExclusive bool, fragmentSpreadA *ast.FragmentSpread, fragmentSpreadB *ast.FragmentSpread) {
var check func(fragmentSpreadA *ast.FragmentSpread, fragmentSpreadB *ast.FragmentSpread)
check = func(fragmentSpreadA *ast.FragmentSpread, fragmentSpreadB *ast.FragmentSpread) {
if fragmentSpreadA.Name == fragmentSpreadB.Name {
return
}
if m.comparedFragmentPairs.Has(fragmentSpreadA, fragmentSpreadB, areMutuallyExclusive) {
return
}
m.comparedFragmentPairs.Add(fragmentSpreadA, fragmentSpreadB, areMutuallyExclusive)
if fragmentSpreadA.Definition == nil {
return
}
if fragmentSpreadB.Definition == nil {
return
}
fieldsMapA, fragmentSpreadsA := getFieldsAndFragmentNames(fragmentSpreadA.Definition.SelectionSet)
fieldsMapB, fragmentSpreadsB := getFieldsAndFragmentNames(fragmentSpreadB.Definition.SelectionSet)
// (F) First, collect all conflicts between these two collections of fields
// (not including any nested fragments).
m.collectConflictsBetween(conflicts, areMutuallyExclusive, fieldsMapA, fieldsMapB)
// (G) Then collect conflicts between the first fragment and any nested
// fragments spread in the second fragment.
for _, fragmentSpread := range fragmentSpreadsB {
check(fragmentSpreadA, fragmentSpread)
}
// (G) Then collect conflicts between the second fragment and any nested
// fragments spread in the first fragment.
for _, fragmentSpread := range fragmentSpreadsA {
check(fragmentSpread, fragmentSpreadB)
}
}
check(fragmentSpreadA, fragmentSpreadB)
}
func (m *overlappingFieldsCanBeMergedManager) findConflictsBetweenSubSelectionSets(areMutuallyExclusive bool, selectionSetA ast.SelectionSet, selectionSetB ast.SelectionSet) *conflictMessageContainer {
var conflicts conflictMessageContainer
fieldsMapA, fragmentSpreadsA := getFieldsAndFragmentNames(selectionSetA)
fieldsMapB, fragmentSpreadsB := getFieldsAndFragmentNames(selectionSetB)
// (H) First, collect all conflicts between these two collections of field.
m.collectConflictsBetween(&conflicts, areMutuallyExclusive, fieldsMapA, fieldsMapB)
// (I) Then collect conflicts between the first collection of fields and
// those referenced by each fragment name associated with the second.
for _, fragmentSpread := range fragmentSpreadsB {
m.comparedFragments = make(map[string]bool)
m.collectConflictsBetweenFieldsAndFragment(&conflicts, areMutuallyExclusive, fieldsMapA, fragmentSpread)
}
// (I) Then collect conflicts between the second collection of fields and
// those referenced by each fragment name associated with the first.
for _, fragmentSpread := range fragmentSpreadsA {
m.comparedFragments = make(map[string]bool)
m.collectConflictsBetweenFieldsAndFragment(&conflicts, areMutuallyExclusive, fieldsMapB, fragmentSpread)
}
// (J) Also collect conflicts between any fragment names by the first and
// fragment names by the second. This compares each item in the first set of
// names to each item in the second set of names.
for _, fragmentSpreadA := range fragmentSpreadsA {
for _, fragmentSpreadB := range fragmentSpreadsB {
m.collectConflictsBetweenFragments(&conflicts, areMutuallyExclusive, fragmentSpreadA, fragmentSpreadB)
}
}
if len(conflicts.Conflicts) == 0 {
return nil
}
return &conflicts
}
func (m *overlappingFieldsCanBeMergedManager) collectConflictsWithin(conflicts *conflictMessageContainer, fieldsMap *sequentialFieldsMap) {
for _, fields := range fieldsMap.Iterator() {
for idx, fieldA := range fields {
for _, fieldB := range fields[idx+1:] {
conflict := m.findConflict(false, fieldA, fieldB)
if conflict != nil {
conflicts.Conflicts = append(conflicts.Conflicts, conflict)
}
}
}
}
}
func (m *overlappingFieldsCanBeMergedManager) collectConflictsBetween(conflicts *conflictMessageContainer, parentFieldsAreMutuallyExclusive bool, fieldsMapA *sequentialFieldsMap, fieldsMapB *sequentialFieldsMap) {
for _, fieldsEntryA := range fieldsMapA.KeyValueIterator() {
fieldsB, ok := fieldsMapB.Get(fieldsEntryA.ResponseName)
if !ok {
continue
}
for _, fieldA := range fieldsEntryA.Fields {
for _, fieldB := range fieldsB {
conflict := m.findConflict(parentFieldsAreMutuallyExclusive, fieldA, fieldB)
if conflict != nil {
conflicts.Conflicts = append(conflicts.Conflicts, conflict)
}
}
}
}
}
func (m *overlappingFieldsCanBeMergedManager) findConflict(parentFieldsAreMutuallyExclusive bool, fieldA *ast.Field, fieldB *ast.Field) *ConflictMessage {
if fieldA.Definition == nil || fieldA.ObjectDefinition == nil || fieldB.Definition == nil || fieldB.ObjectDefinition == nil {
return nil
}
areMutuallyExclusive := parentFieldsAreMutuallyExclusive
if !areMutuallyExclusive {
tmp := fieldA.ObjectDefinition.Name != fieldB.ObjectDefinition.Name
tmp = tmp && fieldA.ObjectDefinition.Kind == ast.Object
tmp = tmp && fieldB.ObjectDefinition.Kind == ast.Object
areMutuallyExclusive = tmp
}
fieldNameA := fieldA.Name
if fieldA.Alias != "" {
fieldNameA = fieldA.Alias
}
if !areMutuallyExclusive {
// Two aliases must refer to the same field.
if fieldA.Name != fieldB.Name {
return &ConflictMessage{
ResponseName: fieldNameA,
Message: fmt.Sprintf(`%s and %s are different fields`, fieldA.Name, fieldB.Name),
Position: fieldB.Position,
}
}
// Two field calls must have the same arguments.
if !sameArguments(fieldA.Arguments, fieldB.Arguments) {
return &ConflictMessage{
ResponseName: fieldNameA,
Message: "they have differing arguments",
Position: fieldB.Position,
}
}
}
if doTypesConflict(m.walker, fieldA.Definition.Type, fieldB.Definition.Type) {
return &ConflictMessage{
ResponseName: fieldNameA,
Message: fmt.Sprintf(`they return conflicting types %s and %s`, fieldA.Definition.Type.String(), fieldB.Definition.Type.String()),
Position: fieldB.Position,
}
}
// Collect and compare sub-fields. Use the same "visited fragment names" list
// for both collections so fields in a fragment reference are never
// compared to themselves.
conflicts := m.findConflictsBetweenSubSelectionSets(areMutuallyExclusive, fieldA.SelectionSet, fieldB.SelectionSet)
if conflicts == nil {
return nil
}
return &ConflictMessage{
ResponseName: fieldNameA,
SubMessage: conflicts.Conflicts,
Position: fieldB.Position,
}
}
func sameArguments(args1 []*ast.Argument, args2 []*ast.Argument) bool {
if len(args1) != len(args2) {
return false
}
for _, arg1 := range args1 {
for _, arg2 := range args2 {
if arg1.Name != arg2.Name {
return false
}
if !sameValue(arg1.Value, arg2.Value) {
return false
}
}
}
return true
}
func sameValue(value1 *ast.Value, value2 *ast.Value) bool {
if value1.Kind != value2.Kind {
return false
}
if value1.Raw != value2.Raw {
return false
}
return true
}
func doTypesConflict(walker *Walker, type1 *ast.Type, type2 *ast.Type) bool {
if type1.Elem != nil {
if type2.Elem != nil {
return doTypesConflict(walker, type1.Elem, type2.Elem)
}
return true
}
if type2.Elem != nil {
return true
}
if type1.NonNull && !type2.NonNull {
return true
}
if !type1.NonNull && type2.NonNull {
return true
}
t1 := walker.Schema.Types[type1.NamedType]
t2 := walker.Schema.Types[type2.NamedType]
if (t1.Kind == ast.Scalar || t1.Kind == ast.Enum) && (t2.Kind == ast.Scalar || t2.Kind == ast.Enum) {
return t1.Name != t2.Name
}
return false
}
func getFieldsAndFragmentNames(selectionSet ast.SelectionSet) (*sequentialFieldsMap, []*ast.FragmentSpread) {
fieldsMap := sequentialFieldsMap{
data: make(map[string][]*ast.Field),
}
var fragmentSpreads []*ast.FragmentSpread
var walk func(selectionSet ast.SelectionSet)
walk = func(selectionSet ast.SelectionSet) {
for _, selection := range selectionSet {
switch selection := selection.(type) {
case *ast.Field:
responseName := selection.Name
if selection.Alias != "" {
responseName = selection.Alias
}
fieldsMap.Push(responseName, selection)
case *ast.InlineFragment:
walk(selection.SelectionSet)
case *ast.FragmentSpread:
fragmentSpreads = append(fragmentSpreads, selection)
}
}
}
walk(selectionSet)
return &fieldsMap, fragmentSpreads
}
