cmd/bpa-operator/vendor/github.com/appscode/jsonpatch/jsonpatch.go

   1 package jsonpatch
   2
   3 import (
   4         "bytes"
   5         "encoding/json"
   6         "fmt"
   7         "reflect"
   8         "strings"
   9 )
  10
  11 var errBadJSONDoc = fmt.Errorf("invalid JSON Document")
  12
  13 type JsonPatchOperation = Operation
  14
  15 type Operation struct {
  16         Operation string      `json:"op"`
  17         Path      string      `json:"path"`
  18         Value     interface{} `json:"value,omitempty"`
  19 }
  20
  21 func (j *Operation) Json() string {
  22         b, _ := json.Marshal(j)
  23         return string(b)
  24 }
  25
  26 func (j *Operation) MarshalJSON() ([]byte, error) {
  27         var b bytes.Buffer
  28         b.WriteString("{")
  29         b.WriteString(fmt.Sprintf(`"op":"%s"`, j.Operation))
  30         b.WriteString(fmt.Sprintf(`,"path":"%s"`, j.Path))
  31         // Consider omitting Value for non-nullable operations.
  32         if j.Value != nil || j.Operation == "replace" || j.Operation == "add" {
  33                 v, err := json.Marshal(j.Value)
  34                 if err != nil {
  35                         return nil, err
  36                 }
  37                 b.WriteString(`,"value":`)
  38                 b.Write(v)
  39         }
  40         b.WriteString("}")
  41         return b.Bytes(), nil
  42 }
  43
  44 type ByPath []Operation
  45
  46 func (a ByPath) Len() int           { return len(a) }
  47 func (a ByPath) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
  48 func (a ByPath) Less(i, j int) bool { return a[i].Path < a[j].Path }
  49
  50 func NewPatch(operation, path string, value interface{}) Operation {
  51         return Operation{Operation: operation, Path: path, Value: value}
  52 }
  53
  54 // CreatePatch creates a patch as specified in http://jsonpatch.com/
  55 //
  56 // 'a' is original, 'b' is the modified document. Both are to be given as json encoded content.
  57 // The function will return an array of JsonPatchOperations
  58 //
  59 // An error will be returned if any of the two documents are invalid.
  60 func CreatePatch(a, b []byte) ([]Operation, error) {
  61         aI := map[string]interface{}{}
  62         bI := map[string]interface{}{}
  63         err := json.Unmarshal(a, &aI)
  64         if err != nil {
  65                 return nil, errBadJSONDoc
  66         }
  67         err = json.Unmarshal(b, &bI)
  68         if err != nil {
  69                 return nil, errBadJSONDoc
  70         }
  71         return diff(aI, bI, "", []Operation{})
  72 }
  73
  74 // Returns true if the values matches (must be json types)
  75 // The types of the values must match, otherwise it will always return false
  76 // If two map[string]interface{} are given, all elements must match.
  77 func matchesValue(av, bv interface{}) bool {
  78         if reflect.TypeOf(av) != reflect.TypeOf(bv) {
  79                 return false
  80         }
  81         switch at := av.(type) {
  82         case string:
  83                 bt, ok := bv.(string)
  84                 if ok && bt == at {
  85                         return true
  86                 }
  87         case float64:
  88                 bt, ok := bv.(float64)
  89                 if ok && bt == at {
  90                         return true
  91                 }
  92         case bool:
  93                 bt, ok := bv.(bool)
  94                 if ok && bt == at {
  95                         return true
  96                 }
  97         case map[string]interface{}:
  98                 bt, ok := bv.(map[string]interface{})
  99                 if !ok {
 100                         return false
 101                 }
 102                 for key := range at {
 103                         if !matchesValue(at[key], bt[key]) {
 104                                 return false
 105                         }
 106                 }
 107                 for key := range bt {
 108                         if !matchesValue(at[key], bt[key]) {
 109                                 return false
 110                         }
 111                 }
 112                 return true
 113         case []interface{}:
 114                 bt, ok := bv.([]interface{})
 115                 if !ok {
 116                         return false
 117                 }
 118                 if len(bt) != len(at) {
 119                         return false
 120                 }
 121                 for key := range at {
 122                         if !matchesValue(at[key], bt[key]) {
 123                                 return false
 124                         }
 125                 }
 126                 for key := range bt {
 127                         if !matchesValue(at[key], bt[key]) {
 128                                 return false
 129                         }
 130                 }
 131                 return true
 132         }
 133         return false
 134 }
 135
 136 // From http://tools.ietf.org/html/rfc6901#section-4 :
 137 //
 138 // Evaluation of each reference token begins by decoding any escaped
 139 // character sequence.  This is performed by first transforming any
 140 // occurrence of the sequence '~1' to '/', and then transforming any
 141 // occurrence of the sequence '~0' to '~'.
 142 //   TODO decode support:
 143 //   var rfc6901Decoder = strings.NewReplacer("~1", "/", "~0", "~")
 144
 145 var rfc6901Encoder = strings.NewReplacer("~", "~0", "/", "~1")
 146
 147 func makePath(path string, newPart interface{}) string {
 148         key := rfc6901Encoder.Replace(fmt.Sprintf("%v", newPart))
 149         if path == "" {
 150                 return "/" + key
 151         }
 152         if strings.HasSuffix(path, "/") {
 153                 return path + key
 154         }
 155         return path + "/" + key
 156 }
 157
 158 // diff returns the (recursive) difference between a and b as an array of JsonPatchOperations.
 159 func diff(a, b map[string]interface{}, path string, patch []Operation) ([]Operation, error) {
 160         for key, bv := range b {
 161                 p := makePath(path, key)
 162                 av, ok := a[key]
 163                 // value was added
 164                 if !ok {
 165                         patch = append(patch, NewPatch("add", p, bv))
 166                         continue
 167                 }
 168                 // Types are the same, compare values
 169                 var err error
 170                 patch, err = handleValues(av, bv, p, patch)
 171                 if err != nil {
 172                         return nil, err
 173                 }
 174         }
 175         // Now add all deleted values as nil
 176         for key := range a {
 177                 _, found := b[key]
 178                 if !found {
 179                         p := makePath(path, key)
 180
 181                         patch = append(patch, NewPatch("remove", p, nil))
 182                 }
 183         }
 184         return patch, nil
 185 }
 186
 187 func handleValues(av, bv interface{}, p string, patch []Operation) ([]Operation, error) {
 188         {
 189                 at := reflect.TypeOf(av)
 190                 bt := reflect.TypeOf(bv)
 191                 if at == nil && bt == nil {
 192                         // do nothing
 193                         return patch, nil
 194                 } else if at == nil && bt != nil {
 195                         return append(patch, NewPatch("add", p, bv)), nil
 196                 } else if at != bt {
 197                         // If types have changed, replace completely (preserves null in destination)
 198                         return append(patch, NewPatch("replace", p, bv)), nil
 199                 }
 200         }
 201
 202         var err error
 203         switch at := av.(type) {
 204         case map[string]interface{}:
 205                 bt := bv.(map[string]interface{})
 206                 patch, err = diff(at, bt, p, patch)
 207                 if err != nil {
 208                         return nil, err
 209                 }
 210         case string, float64, bool:
 211                 if !matchesValue(av, bv) {
 212                         patch = append(patch, NewPatch("replace", p, bv))
 213                 }
 214         case []interface{}:
 215                 bt := bv.([]interface{})
 216                 if isSimpleArray(at) && isSimpleArray(bt) {
 217                         patch = append(patch, compareEditDistance(at, bt, p)...)
 218                 } else {
 219                         n := min(len(at), len(bt))
 220                         for i := len(at) - 1; i >= n; i-- {
 221                                 patch = append(patch, NewPatch("remove", makePath(p, i), nil))
 222                         }
 223                         for i := n; i < len(bt); i++ {
 224                                 patch = append(patch, NewPatch("add", makePath(p, i), bt[i]))
 225                         }
 226                         for i := 0; i < n; i++ {
 227                                 var err error
 228                                 patch, err = handleValues(at[i], bt[i], makePath(p, i), patch)
 229                                 if err != nil {
 230                                         return nil, err
 231                                 }
 232                         }
 233                 }
 234         default:
 235                 panic(fmt.Sprintf("Unknown type:%T ", av))
 236         }
 237         return patch, nil
 238 }
 239
 240 func isBasicType(a interface{}) bool {
 241         switch a.(type) {
 242         case string, float64, bool:
 243         default:
 244                 return false
 245         }
 246         return true
 247 }
 248
 249 func isSimpleArray(a []interface{}) bool {
 250         for i := range a {
 251                 switch a[i].(type) {
 252                 case string, float64, bool:
 253                 default:
 254                         val := reflect.ValueOf(a[i])
 255                         if val.Kind() == reflect.Map {
 256                                 for _, k := range val.MapKeys() {
 257                                         av := val.MapIndex(k)
 258                                         if av.Kind() == reflect.Ptr || av.Kind() == reflect.Interface {
 259                                                 if av.IsNil() {
 260                                                         continue
 261                                                 }
 262                                                 av = av.Elem()
 263                                         }
 264                                         if av.Kind() != reflect.String && av.Kind() != reflect.Float64 && av.Kind() != reflect.Bool {
 265                                                 return false
 266                                         }
 267                                 }
 268                                 return true
 269                         }
 270                         return false
 271                 }
 272         }
 273         return true
 274 }
 275
 276 // https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
 277 // Adapted from https://github.com/texttheater/golang-levenshtein
 278 func compareEditDistance(s, t []interface{}, p string) []Operation {
 279         m := len(s)
 280         n := len(t)
 281
 282         d := make([][]int, m+1)
 283         for i := 0; i <= m; i++ {
 284                 d[i] = make([]int, n+1)
 285                 d[i][0] = i
 286         }
 287         for j := 0; j <= n; j++ {
 288                 d[0][j] = j
 289         }
 290
 291         for j := 1; j <= n; j++ {
 292                 for i := 1; i <= m; i++ {
 293                         if reflect.DeepEqual(s[i-1], t[j-1]) {
 294                                 d[i][j] = d[i-1][j-1] // no op required
 295                         } else {
 296                                 del := d[i-1][j] + 1
 297                                 add := d[i][j-1] + 1
 298                                 rep := d[i-1][j-1] + 1
 299                                 d[i][j] = min(rep, min(add, del))
 300                         }
 301                 }
 302         }
 303
 304         return backtrace(s, t, p, m, n, d)
 305 }
 306
 307 func min(x int, y int) int {
 308         if y < x {
 309                 return y
 310         }
 311         return x
 312 }
 313
 314 func backtrace(s, t []interface{}, p string, i int, j int, matrix [][]int) []Operation {
 315         if i > 0 && matrix[i-1][j]+1 == matrix[i][j] {
 316                 op := NewPatch("remove", makePath(p, i-1), nil)
 317                 return append([]Operation{op}, backtrace(s, t, p, i-1, j, matrix)...)
 318         }
 319         if j > 0 && matrix[i][j-1]+1 == matrix[i][j] {
 320                 op := NewPatch("add", makePath(p, i), t[j-1])
 321                 return append([]Operation{op}, backtrace(s, t, p, i, j-1, matrix)...)
 322         }
 323         if i > 0 && j > 0 && matrix[i-1][j-1]+1 == matrix[i][j] {
 324                 if isBasicType(s[0]) {
 325                         op := NewPatch("replace", makePath(p, i-1), t[j-1])
 326                         return append([]Operation{op}, backtrace(s, t, p, i-1, j-1, matrix)...)
 327                 }
 328
 329                 p2, _ := handleValues(s[j-1], t[j-1], makePath(p, i-1), []Operation{})
 330                 return append(p2, backtrace(s, t, p, i-1, j-1, matrix)...)
 331         }
 332         if i > 0 && j > 0 && matrix[i-1][j-1] == matrix[i][j] {
 333                 return backtrace(s, t, p, i-1, j-1, matrix)
 334         }
 335         return []Operation{}
 336 }