diff options
Diffstat (limited to 'vendor/github.com/vektah/gqlparser/validator/rules/overlapping_fields_can_be_merged.go')
| -rw-r--r-- | vendor/github.com/vektah/gqlparser/validator/rules/overlapping_fields_can_be_merged.go | 557 |
1 files changed, 0 insertions, 557 deletions
diff --git a/vendor/github.com/vektah/gqlparser/validator/rules/overlapping_fields_can_be_merged.go b/vendor/github.com/vektah/gqlparser/validator/rules/overlapping_fields_can_be_merged.go deleted file mode 100644 index bb2f1831..00000000 --- a/vendor/github.com/vektah/gqlparser/validator/rules/overlapping_fields_can_be_merged.go +++ /dev/null @@ -1,557 +0,0 @@ -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 -} |