| // Copyright 2018 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| package firestore |
| |
| import ( |
| "bytes" |
| "fmt" |
| "math" |
| "sort" |
| "strings" |
| |
| tspb "github.com/golang/protobuf/ptypes/timestamp" |
| pb "google.golang.org/genproto/googleapis/firestore/v1" |
| ) |
| |
| // Returns a negative number, zero, or a positive number depending on whether a is |
| // less than, equal to, or greater than b according to Firestore's ordering of |
| // values. |
| func compareValues(a, b *pb.Value) int { |
| ta := typeOrder(a) |
| tb := typeOrder(b) |
| if ta != tb { |
| return compareInt64s(int64(ta), int64(tb)) |
| } |
| switch a := a.ValueType.(type) { |
| case *pb.Value_NullValue: |
| return 0 // nulls are equal |
| |
| case *pb.Value_BooleanValue: |
| av := a.BooleanValue |
| bv := b.GetBooleanValue() |
| switch { |
| case av && !bv: |
| return 1 |
| case bv && !av: |
| return -1 |
| default: |
| return 0 |
| } |
| |
| case *pb.Value_IntegerValue: |
| return compareNumbers(float64(a.IntegerValue), toFloat(b)) |
| |
| case *pb.Value_DoubleValue: |
| return compareNumbers(a.DoubleValue, toFloat(b)) |
| |
| case *pb.Value_TimestampValue: |
| return compareTimestamps(a.TimestampValue, b.GetTimestampValue()) |
| |
| case *pb.Value_StringValue: |
| return strings.Compare(a.StringValue, b.GetStringValue()) |
| |
| case *pb.Value_BytesValue: |
| return bytes.Compare(a.BytesValue, b.GetBytesValue()) |
| |
| case *pb.Value_ReferenceValue: |
| return compareReferences(a.ReferenceValue, b.GetReferenceValue()) |
| |
| case *pb.Value_GeoPointValue: |
| ag := a.GeoPointValue |
| bg := b.GetGeoPointValue() |
| if ag.Latitude != bg.Latitude { |
| return compareFloat64s(ag.Latitude, bg.Latitude) |
| } |
| return compareFloat64s(ag.Longitude, bg.Longitude) |
| |
| case *pb.Value_ArrayValue: |
| return compareArrays(a.ArrayValue.Values, b.GetArrayValue().Values) |
| |
| case *pb.Value_MapValue: |
| return compareMaps(a.MapValue.Fields, b.GetMapValue().Fields) |
| |
| default: |
| panic(fmt.Sprintf("bad value type: %v", a)) |
| } |
| } |
| |
| // Treats NaN as less than any non-NaN. |
| func compareNumbers(a, b float64) int { |
| switch { |
| case math.IsNaN(a): |
| if math.IsNaN(b) { |
| return 0 |
| } |
| return -1 |
| case math.IsNaN(b): |
| return 1 |
| default: |
| return compareFloat64s(a, b) |
| } |
| } |
| |
| // Return v as a float64, assuming it's an Integer or Double. |
| func toFloat(v *pb.Value) float64 { |
| if x, ok := v.ValueType.(*pb.Value_IntegerValue); ok { |
| return float64(x.IntegerValue) |
| } |
| return v.GetDoubleValue() |
| } |
| |
| func compareTimestamps(a, b *tspb.Timestamp) int { |
| if c := compareInt64s(a.Seconds, b.Seconds); c != 0 { |
| return c |
| } |
| return compareInt64s(int64(a.Nanos), int64(b.Nanos)) |
| } |
| |
| func compareReferences(a, b string) int { |
| // Compare path components lexicographically. |
| pa := strings.Split(a, "/") |
| pb := strings.Split(b, "/") |
| return compareSequences(len(pa), len(pb), func(i int) int { |
| return strings.Compare(pa[i], pb[i]) |
| }) |
| } |
| |
| func compareArrays(a, b []*pb.Value) int { |
| return compareSequences(len(a), len(b), func(i int) int { |
| return compareValues(a[i], b[i]) |
| }) |
| } |
| |
| func compareMaps(a, b map[string]*pb.Value) int { |
| sortedKeys := func(m map[string]*pb.Value) []string { |
| var ks []string |
| for k := range m { |
| ks = append(ks, k) |
| } |
| sort.Strings(ks) |
| return ks |
| } |
| |
| aks := sortedKeys(a) |
| bks := sortedKeys(b) |
| return compareSequences(len(aks), len(bks), func(i int) int { |
| if c := strings.Compare(aks[i], bks[i]); c != 0 { |
| return c |
| } |
| k := aks[i] |
| return compareValues(a[k], b[k]) |
| }) |
| } |
| |
| func compareSequences(len1, len2 int, compare func(int) int) int { |
| for i := 0; i < len1 && i < len2; i++ { |
| if c := compare(i); c != 0 { |
| return c |
| } |
| } |
| return compareInt64s(int64(len1), int64(len2)) |
| } |
| |
| func compareFloat64s(a, b float64) int { |
| switch { |
| case a < b: |
| return -1 |
| case a > b: |
| return 1 |
| default: |
| return 0 |
| } |
| } |
| |
| func compareInt64s(a, b int64) int { |
| switch { |
| case a < b: |
| return -1 |
| case a > b: |
| return 1 |
| default: |
| return 0 |
| } |
| } |
| |
| // Return an integer corresponding to the type of value stored in v, such that |
| // comparing the resulting integers gives the Firestore ordering for types. |
| func typeOrder(v *pb.Value) int { |
| switch v.ValueType.(type) { |
| case *pb.Value_NullValue: |
| return 0 |
| case *pb.Value_BooleanValue: |
| return 1 |
| case *pb.Value_IntegerValue: |
| return 2 |
| case *pb.Value_DoubleValue: |
| return 2 |
| case *pb.Value_TimestampValue: |
| return 3 |
| case *pb.Value_StringValue: |
| return 4 |
| case *pb.Value_BytesValue: |
| return 5 |
| case *pb.Value_ReferenceValue: |
| return 6 |
| case *pb.Value_GeoPointValue: |
| return 7 |
| case *pb.Value_ArrayValue: |
| return 8 |
| case *pb.Value_MapValue: |
| return 9 |
| default: |
| panic(fmt.Sprintf("bad value type: %v", v)) |
| } |
| } |