collate.go

Documentation: github.com/go-kivik/kivik/v4/x/collate

     1  // Licensed under the Apache License, Version 2.0 (the "License"); you may not
     2  // use this file except in compliance with the License. You may obtain a copy of
     3  // the License at
     4  //
     5  //  http://www.apache.org/licenses/LICENSE-2.0
     6  //
     7  // Unless required by applicable law or agreed to in writing, software
     8  // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
     9  // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
    10  // License for the specific language governing permissions and limitations under
    11  // the License.
    12  
    13  // Package collate provides (near) CouchDB-compatible collation functions.
    14  //
    15  // The collation order provided by this package differs slightly from that
    16  // described by the [CouchDB documentation]. In particular:
    17  //
    18  //   - The Unicode UCI algorithm supported natively by Go sorts the backtick (`)
    19  //     and caret (^) after other symbols, not before.
    20  //   - Because Go's maps are unordered, this implementation does not honor the
    21  //     order of object key members when collating.  That is to say, the object
    22  //     `{b:2,a:1}` is treated as equivalent to `{a:1,b:2}` for collation
    23  //     purposes. This is tracked in [issue #952]. Please leave a comment there
    24  //     if this is affecting you.
    25  //
    26  // [CouchDB documentation]: https://docs.couchdb.org/en/stable/ddocs/views/collation.html#collation-specification
    27  // [issue #952]: https://github.com/go-kivik/kivik/issues/952
    28  package collate
    29  
    30  import (
    31  	"sort"
    32  	"sync"
    33  
    34  	"golang.org/x/text/collate"
    35  	"golang.org/x/text/language"
    36  )
    37  
    38  var (
    39  	collatorMu = new(sync.Mutex)
    40  	collator   = collate.New(language.Und)
    41  )
    42  
    43  // CompareString returns an integer comparing the two strings.
    44  // The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
    45  func CompareString(a, b string) int {
    46  	collatorMu.Lock()
    47  	defer collatorMu.Unlock()
    48  	return collator.CompareString(a, b)
    49  }
    50  
    51  // CompareObject compares two unmarshaled JSON objects. The function will panic
    52  // if it encounters an unexpected type. The comparison is performed recursively,
    53  // with keys sorted before comparison. The result will be 0 if a==b, -1 if a < b,
    54  // and +1 if a > b.
    55  func CompareObject(a, b interface{}) int {
    56  	aType := jsonTypeOf(a)
    57  	switch bType := jsonTypeOf(b); {
    58  	case aType < bType:
    59  		return -1
    60  	case aType > bType:
    61  		return 1
    62  	}
    63  
    64  	switch aType {
    65  	case jsonTypeBool:
    66  		aBool := a.(bool)
    67  		bBool := b.(bool)
    68  		if aBool == bBool {
    69  			return 0
    70  		}
    71  		// false before true
    72  		if !aBool {
    73  			return -1
    74  		}
    75  		return 1
    76  	case jsonTypeNull:
    77  		if b == nil {
    78  			return 0
    79  		}
    80  		return -1
    81  	case jsonTypeNumber:
    82  		return int(a.(float64) - b.(float64))
    83  	case jsonTypeString:
    84  		return CompareString(a.(string), b.(string))
    85  	case jsonTypeArray:
    86  		aArray := a.([]interface{})
    87  		bArray := b.([]interface{})
    88  		for i := 0; i < len(aArray) && i < len(bArray); i++ {
    89  			if cmp := CompareObject(aArray[i], bArray[i]); cmp != 0 {
    90  				return cmp
    91  			}
    92  		}
    93  		return len(aArray) - len(bArray)
    94  	case jsonTypeObject:
    95  		aObject := a.(map[string]interface{})
    96  		bObject := b.(map[string]interface{})
    97  		keyMap := make(map[string]struct{}, len(aObject))
    98  		for k := range aObject {
    99  			keyMap[k] = struct{}{}
   100  		}
   101  		for k := range bObject {
   102  			keyMap[k] = struct{}{}
   103  		}
   104  		keys := make([]string, 0, len(keyMap))
   105  		for k := range keyMap {
   106  			keys = append(keys, k)
   107  		}
   108  		sort.Slice(keys, func(i, j int) bool {
   109  			return CompareString(keys[i], keys[j]) < 0
   110  		})
   111  
   112  		for i, k := range keys {
   113  			av, aok := aObject[k]
   114  			if !aok {
   115  				return 1
   116  			}
   117  			bv, bok := bObject[k]
   118  			if !bok {
   119  				return -1
   120  			}
   121  			if cmp := CompareObject(av, bv); cmp != 0 {
   122  				return cmp
   123  			}
   124  			if i+1 == len(aObject) || i+1 == len(bObject) {
   125  				return len(aObject) - len(bObject)
   126  			}
   127  		}
   128  	}
   129  	panic("unexpected JSON type")
   130  }
   131
View as plain text