11 var errBadJSONDoc = fmt.Errorf("invalid JSON Document")
13 type JsonPatchOperation = Operation
15 type Operation struct {
16 Operation string `json:"op"`
17 Path string `json:"path"`
18 Value interface{} `json:"value,omitempty"`
21 func (j *Operation) Json() string {
22 b, _ := json.Marshal(j)
26 func (j *Operation) MarshalJSON() ([]byte, error) {
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)
37 b.WriteString(`,"value":`)
44 type ByPath []Operation
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 }
50 func NewPatch(operation, path string, value interface{}) Operation {
51 return Operation{Operation: operation, Path: path, Value: value}
54 // CreatePatch creates a patch as specified in http://jsonpatch.com/
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
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)
65 return nil, errBadJSONDoc
67 err = json.Unmarshal(b, &bI)
69 return nil, errBadJSONDoc
71 return diff(aI, bI, "", []Operation{})
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) {
81 switch at := av.(type) {
88 bt, ok := bv.(float64)
97 case map[string]interface{}:
98 bt, ok := bv.(map[string]interface{})
102 for key := range at {
103 if !matchesValue(at[key], bt[key]) {
107 for key := range bt {
108 if !matchesValue(at[key], bt[key]) {
114 bt, ok := bv.([]interface{})
118 if len(bt) != len(at) {
121 for key := range at {
122 if !matchesValue(at[key], bt[key]) {
126 for key := range bt {
127 if !matchesValue(at[key], bt[key]) {
136 // From http://tools.ietf.org/html/rfc6901#section-4 :
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", "~")
145 var rfc6901Encoder = strings.NewReplacer("~", "~0", "/", "~1")
147 func makePath(path string, newPart interface{}) string {
148 key := rfc6901Encoder.Replace(fmt.Sprintf("%v", newPart))
152 if strings.HasSuffix(path, "/") {
155 return path + "/" + key
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)
165 patch = append(patch, NewPatch("add", p, bv))
168 // Types are the same, compare values
170 patch, err = handleValues(av, bv, p, patch)
175 // Now add all deleted values as nil
179 p := makePath(path, key)
181 patch = append(patch, NewPatch("remove", p, nil))
187 func handleValues(av, bv interface{}, p string, patch []Operation) ([]Operation, error) {
189 at := reflect.TypeOf(av)
190 bt := reflect.TypeOf(bv)
191 if at == nil && bt == nil {
194 } else if at == nil && bt != nil {
195 return append(patch, NewPatch("add", p, bv)), nil
197 // If types have changed, replace completely (preserves null in destination)
198 return append(patch, NewPatch("replace", p, bv)), nil
203 switch at := av.(type) {
204 case map[string]interface{}:
205 bt := bv.(map[string]interface{})
206 patch, err = diff(at, bt, p, patch)
210 case string, float64, bool:
211 if !matchesValue(av, bv) {
212 patch = append(patch, NewPatch("replace", p, bv))
215 bt := bv.([]interface{})
216 if isSimpleArray(at) && isSimpleArray(bt) {
217 patch = append(patch, compareEditDistance(at, bt, p)...)
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))
223 for i := n; i < len(bt); i++ {
224 patch = append(patch, NewPatch("add", makePath(p, i), bt[i]))
226 for i := 0; i < n; i++ {
228 patch, err = handleValues(at[i], bt[i], makePath(p, i), patch)
235 panic(fmt.Sprintf("Unknown type:%T ", av))
240 func isBasicType(a interface{}) bool {
242 case string, float64, bool:
249 func isSimpleArray(a []interface{}) bool {
252 case string, float64, bool:
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 {
264 if av.Kind() != reflect.String && av.Kind() != reflect.Float64 && av.Kind() != reflect.Bool {
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 {
282 d := make([][]int, m+1)
283 for i := 0; i <= m; i++ {
284 d[i] = make([]int, n+1)
287 for j := 0; j <= n; j++ {
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
298 rep := d[i-1][j-1] + 1
299 d[i][j] = min(rep, min(add, del))
304 return backtrace(s, t, p, m, n, d)
307 func min(x int, y int) int {
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)...)
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)...)
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)...)
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)...)
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)