proto/equal.go

   1 // Go support for Protocol Buffers - Google's data interchange format
   2 //
   3 // Copyright 2011 Google Inc.  All rights reserved.
   4 // http://code.google.com/p/goprotobuf/
   5 //
   6 // Redistribution and use in source and binary forms, with or without
   7 // modification, are permitted provided that the following conditions are
   8 // met:
   9 //
  10 //     * Redistributions of source code must retain the above copyright
  11 // notice, this list of conditions and the following disclaimer.
  12 //     * Redistributions in binary form must reproduce the above
  13 // copyright notice, this list of conditions and the following disclaimer
  14 // in the documentation and/or other materials provided with the
  15 // distribution.
  16 //     * Neither the name of Google Inc. nor the names of its
  17 // contributors may be used to endorse or promote products derived from
  18 // this software without specific prior written permission.
  19 //
  20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  24 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  26 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  27 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  28 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  29 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31
  32 // Protocol buffer comparison.
  33 // TODO: MessageSet and RawMessage.
  34
  35 package proto
  36
  37 import (
  38         "bytes"
  39         "log"
  40         "os"
  41         "reflect"
  42         "strings"
  43 )
  44
  45 /*
  46 Equal returns true iff protocol buffers a and b are equal.
  47 The arguments must both be protocol buffer structs,
  48 or both be pointers to protocol buffer structs.
  49
  50 Equality is defined in this way:
  51   - Two messages are equal iff they are the same type,
  52     corresponding fields are equal, unknown field sets
  53     are equal, and extensions sets are equal.
  54   - Two set scalar fields are equal iff their values are equal.
  55     If the fields are of a floating-point type, remember that
  56     NaN != x for all x, including NaN.
  57   - Two repeated fields are equal iff their lengths are the same,
  58     and their corresponding elements are equal.
  59   - Two unset fields are equal.
  60   - Two unknown field sets are equal if their current
  61     encoded state is equal. (TODO)
  62   - Two extension sets are equal iff they have corresponding
  63     elements that are pairwise equal.
  64   - Every other combination of things are not equal.
  65
  66 The return value is undefined if a and b are not protocol buffers.
  67 */
  68 func Equal(a, b interface{}) bool {
  69         v1, v2 := reflect.ValueOf(a), reflect.ValueOf(b)
  70         if v1.Type() != v2.Type() {
  71                 return false
  72         }
  73         if v1.Kind() == reflect.Ptr {
  74                 v1, v2 = v1.Elem(), v2.Elem()
  75         }
  76         if v1.Kind() != reflect.Struct {
  77                 return false
  78         }
  79         return equalStruct(v1, v2)
  80 }
  81
  82 // v1 and v2 are known to have the same type.
  83 func equalStruct(v1, v2 reflect.Value) bool {
  84         for i := 0; i < v1.NumField(); i++ {
  85                 f := v1.Type().Field(i)
  86                 if strings.HasPrefix(f.Name, "XXX_") {
  87                         continue
  88                 }
  89                 f1, f2 := v1.Field(i), v2.Field(i)
  90                 if f.Type.Kind() == reflect.Ptr {
  91                         if n1, n2 := f1.IsNil(), f2.IsNil(); n1 && n2 {
  92                                 // both unset
  93                                 continue
  94                         } else if n1 != n2 {
  95                                 // set/unset mismatch
  96                                 return false
  97                         }
  98                         f1, f2 = f1.Elem(), f2.Elem()
  99                 }
 100                 if !equalAny(f1, f2) {
 101                         return false
 102                 }
 103         }
 104
 105         if em1 := v1.FieldByName("XXX_extensions"); em1.IsValid() {
 106                 em2 := v2.FieldByName("XXX_extensions")
 107                 if !equalExtensions(v1.Type(), em1.Interface().(map[int32]Extension), em2.Interface().(map[int32]Extension)) {
 108                         return false
 109                 }
 110         }
 111
 112         // TODO: Deal with XXX_unrecognized.
 113
 114         return true
 115 }
 116
 117 // v1 and v2 are known to have the same type.
 118 func equalAny(v1, v2 reflect.Value) bool {
 119         switch v1.Kind() {
 120         case reflect.Bool:
 121                 return v1.Bool() == v2.Bool()
 122         case reflect.Float32, reflect.Float64:
 123                 return v1.Float() == v2.Float()
 124         case reflect.Int32, reflect.Int64:
 125                 return v1.Int() == v2.Int()
 126         case reflect.Ptr:
 127                 return equalAny(v1.Elem(), v2.Elem())
 128         case reflect.Slice:
 129                 if n1, n2 := v1.IsNil(), v2.IsNil(); n1 && n2 {
 130                         return true
 131                 } else if n1 != n2 {
 132                         return false
 133                 }
 134                 if v1.Len() != v2.Len() {
 135                         return false
 136                 }
 137                 // short circuit: []byte
 138                 if v1.Type().Elem().Kind() == reflect.Uint8 {
 139                         return bytes.Equal(v1.Interface().([]byte), v2.Interface().([]byte))
 140                 }
 141                 for i := 0; i < v1.Len(); i++ {
 142                         if !equalAny(v1.Index(i), v2.Index(i)) {
 143                                 return false
 144                         }
 145                 }
 146                 return true
 147         case reflect.String:
 148                 return v1.Interface().(string) == v2.Interface().(string)
 149         case reflect.Struct:
 150                 return equalStruct(v1, v2)
 151         case reflect.Uint32, reflect.Uint64:
 152                 return v1.Uint() == v2.Uint()
 153         }
 154
 155         // unknown type, so not a protocol buffer
 156         log.Printf("proto: don't know how to compare %v", v1)
 157         return false
 158 }
 159
 160 // base is the struct type that the extensions are based on.
 161 // em1 and em2 are extension maps.
 162 func equalExtensions(base reflect.Type, em1, em2 map[int32]Extension) bool {
 163         if len(em1) != len(em2) {
 164                 return false
 165         }
 166
 167         for extNum, e1 := range em1 {
 168                 e2, ok := em2[extNum]
 169                 if !ok {
 170                         return false
 171                 }
 172
 173                 m1, m2 := e1.value, e2.value
 174
 175                 if m1 != nil && m2 != nil {
 176                         // Both are unencoded.
 177                         if !Equal(m1, m2) {
 178                                 return false
 179                         }
 180                         continue
 181                 }
 182
 183                 // At least one is encoded. To do a semantically correct comparison
 184                 // we need to unmarshal them first.
 185                 var desc *ExtensionDesc
 186                 if m := extensionMaps[base]; m != nil {
 187                         desc = m[extNum]
 188                 }
 189                 if desc == nil {
 190                         log.Printf("proto: don't know how to compare extension %d of %v", extNum, base)
 191                         continue
 192                 }
 193                 var err os.Error
 194                 if m1 == nil {
 195                         m1, err = decodeExtension(e1.enc, desc)
 196                 }
 197                 if m2 == nil && err == nil {
 198                         m2, err = decodeExtension(e2.enc, desc)
 199                 }
 200                 if err != nil {
 201                         // The encoded form is invalid.
 202                         log.Printf("proto: badly encoded extension %d of %v: %v", extNum, base, err)
 203                         return false
 204                 }
 205                 if !Equal(m1, m2) {
 206                         return false
 207                 }
 208         }
 209
 210         return true
 211 }