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

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

     1  package validator
     2  
     3  import (
     4  	"math"
     5  	"sort"
     6  	"strings"
     7  
     8  	"github.com/agnivade/levenshtein"
     9  )
    10  
    11  // Given an invalid input string and a list of valid options, returns a filtered
    12  // list of valid options sorted based on their similarity with the input.
    13  func SuggestionList(input string, options []string) []string {
    14  	var results []string
    15  	optionsByDistance := map[string]int{}
    16  
    17  	for _, option := range options {
    18  		distance := lexicalDistance(input, option)
    19  		threshold := calcThreshold(input)
    20  		if distance <= threshold {
    21  			results = append(results, option)
    22  			optionsByDistance[option] = distance
    23  		}
    24  	}
    25  
    26  	sort.Slice(results, func(i, j int) bool {
    27  		return optionsByDistance[results[i]] < optionsByDistance[results[j]]
    28  	})
    29  	return results
    30  }
    31  
    32  func calcThreshold(a string) (threshold int) {
    33  	// the logic is copied from here
    34  	// https://github.com/graphql/graphql-js/blob/47bd8c8897c72d3efc17ecb1599a95cee6bac5e8/src/jsutils/suggestionList.ts#L14
    35  	threshold = int(math.Floor(float64(len(a))*0.4) + 1)
    36  
    37  	if threshold < 1 {
    38  		threshold = 1
    39  	}
    40  	return
    41  }
    42  
    43  // Computes the lexical distance between strings A and B.
    44  //
    45  // The "distance" between two strings is given by counting the minimum number
    46  // of edits needed to transform string A into string B. An edit can be an
    47  // insertion, deletion, or substitution of a single character, or a swap of two
    48  // adjacent characters.
    49  //
    50  // Includes a custom alteration from Damerau-Levenshtein to treat case changes
    51  // as a single edit which helps identify mis-cased values with an edit distance
    52  // of 1.
    53  //
    54  // This distance can be useful for detecting typos in input or sorting
    55  func lexicalDistance(a, b string) int {
    56  	if a == b {
    57  		return 0
    58  	}
    59  
    60  	a = strings.ToLower(a)
    61  	b = strings.ToLower(b)
    62  
    63  	// Any case change counts as a single edit
    64  	if a == b {
    65  		return 1
    66  	}
    67  
    68  	return levenshtein.ComputeDistance(a, b)
    69  }
    70  

View as plain text