Merge pull request #205 from jiahuif-forks/feature/merge-new-algorithm
new algorithm for structural merge
diff --git a/typed/merge.go b/typed/merge.go
index afec9f3..75244ef 100644
--- a/typed/merge.go
+++ b/typed/merge.go
@@ -17,8 +17,6 @@
package typed
import (
- "math"
-
"sigs.k8s.io/structured-merge-diff/v4/fieldpath"
"sigs.k8s.io/structured-merge-diff/v4/schema"
"sigs.k8s.io/structured-merge-diff/v4/value"
@@ -170,74 +168,94 @@
if lhs != nil {
lLen = lhs.Length()
}
- out := make([]interface{}, 0, int(math.Max(float64(rLen), float64(lLen))))
+ outLen := lLen
+ if outLen < rLen {
+ outLen = rLen
+ }
+ out := make([]interface{}, 0, outLen)
- lhsOrder := make([]fieldpath.PathElement, 0, lLen)
+ rhsOrder, observedRHS, rhsErrs := w.indexListPathElements(t, rhs)
+ errs = append(errs, rhsErrs...)
+ lhsOrder, observedLHS, lhsErrs := w.indexListPathElements(t, lhs)
+ errs = append(errs, lhsErrs...)
- // First, collect all LHS children.
- observedLHS := fieldpath.MakePathElementValueMap(lLen)
- if lhs != nil {
- for i := 0; i < lhs.Length(); i++ {
- child := lhs.At(i)
- pe, err := listItemToPathElement(w.allocator, w.schema, t, i, child)
- if err != nil {
- errs = append(errs, errorf("lhs: element %v: %v", i, err.Error())...)
- // If we can't construct the path element, we can't
- // even report errors deeper in the schema, so bail on
- // this element.
- continue
- }
- if _, ok := observedLHS.Get(pe); ok {
- errs = append(errs, errorf("lhs: duplicate entries for key %v", pe.String())...)
- }
- observedLHS.Insert(pe, child)
- lhsOrder = append(lhsOrder, pe)
+ sharedOrder := make([]*fieldpath.PathElement, 0, rLen)
+ for i := range rhsOrder {
+ pe := &rhsOrder[i]
+ if _, ok := observedLHS.Get(*pe); ok {
+ sharedOrder = append(sharedOrder, pe)
}
}
- // Then merge with RHS children.
- observedRHS := fieldpath.MakePathElementSet(rLen)
- if rhs != nil {
- for i := 0; i < rhs.Length(); i++ {
- child := rhs.At(i)
- pe, err := listItemToPathElement(w.allocator, w.schema, t, i, child)
- if err != nil {
- errs = append(errs, errorf("rhs: element %v: %v", i, err.Error())...)
- // If we can't construct the path element, we can't
- // even report errors deeper in the schema, so bail on
- // this element.
- continue
- }
- if observedRHS.Has(pe) {
- errs = append(errs, errorf("rhs: duplicate entries for key %v", pe.String())...)
- continue
- }
- observedRHS.Insert(pe)
- w2 := w.prepareDescent(pe, t.ElementType)
- w2.rhs = child
- if lchild, ok := observedLHS.Get(pe); ok {
- w2.lhs = lchild
- }
- errs = append(errs, w2.merge(pe.String)...)
- if w2.out != nil {
- out = append(out, *w2.out)
- }
- w.finishDescent(w2)
- }
+ var nextShared *fieldpath.PathElement
+ if len(sharedOrder) > 0 {
+ nextShared = sharedOrder[0]
+ sharedOrder = sharedOrder[1:]
}
- for _, pe := range lhsOrder {
- if observedRHS.Has(pe) {
- continue
+ lLen, rLen = len(lhsOrder), len(rhsOrder)
+ for lI, rI := 0, 0; lI < lLen || rI < rLen; {
+ if lI < lLen && rI < rLen {
+ pe := lhsOrder[lI]
+ if pe.Equals(rhsOrder[rI]) {
+ // merge LHS & RHS items
+ lChild, _ := observedLHS.Get(pe)
+ rChild, _ := observedRHS.Get(pe)
+ mergeOut, errs := w.mergeListItem(t, pe, lChild, rChild)
+ errs = append(errs, errs...)
+ if mergeOut != nil {
+ out = append(out, *mergeOut)
+ }
+ lI++
+ rI++
+
+ nextShared = nil
+ if len(sharedOrder) > 0 {
+ nextShared = sharedOrder[0]
+ sharedOrder = sharedOrder[1:]
+ }
+ continue
+ }
+ if _, ok := observedRHS.Get(pe); ok && nextShared != nil && !nextShared.Equals(lhsOrder[lI]) {
+ // shared item, but not the one we want in this round
+ lI++
+ continue
+ }
}
- value, _ := observedLHS.Get(pe)
- w2 := w.prepareDescent(pe, t.ElementType)
- w2.lhs = value
- errs = append(errs, w2.merge(pe.String)...)
- if w2.out != nil {
- out = append(out, *w2.out)
+ if lI < lLen {
+ pe := lhsOrder[lI]
+ if _, ok := observedRHS.Get(pe); !ok {
+ // take LHS item
+ lChild, _ := observedLHS.Get(pe)
+ mergeOut, errs := w.mergeListItem(t, pe, lChild, nil)
+ errs = append(errs, errs...)
+ if mergeOut != nil {
+ out = append(out, *mergeOut)
+ }
+ lI++
+ continue
+ }
}
- w.finishDescent(w2)
+ if rI < rLen {
+ // Take the RHS item, merge with matching LHS item if possible
+ pe := rhsOrder[rI]
+ lChild, _ := observedLHS.Get(pe) // may be nil
+ rChild, _ := observedRHS.Get(pe)
+ mergeOut, errs := w.mergeListItem(t, pe, lChild, rChild)
+ errs = append(errs, errs...)
+ if mergeOut != nil {
+ out = append(out, *mergeOut)
+ }
+ rI++
+ // Advance nextShared, if we are merging nextShared.
+ if nextShared != nil && nextShared.Equals(pe) {
+ nextShared = nil
+ if len(sharedOrder) > 0 {
+ nextShared = sharedOrder[0]
+ sharedOrder = sharedOrder[1:]
+ }
+ }
+ }
}
if len(out) > 0 {
@@ -248,6 +266,46 @@
return errs
}
+func (w *mergingWalker) indexListPathElements(t *schema.List, list value.List) ([]fieldpath.PathElement, fieldpath.PathElementValueMap, ValidationErrors) {
+ var errs ValidationErrors
+ length := 0
+ if list != nil {
+ length = list.Length()
+ }
+ observed := fieldpath.MakePathElementValueMap(length)
+ pes := make([]fieldpath.PathElement, 0, length)
+ for i := 0; i < length; i++ {
+ child := list.At(i)
+ pe, err := listItemToPathElement(w.allocator, w.schema, t, i, child)
+ if err != nil {
+ errs = append(errs, errorf("element %v: %v", i, err.Error())...)
+ // If we can't construct the path element, we can't
+ // even report errors deeper in the schema, so bail on
+ // this element.
+ continue
+ }
+ if _, found := observed.Get(pe); found {
+ errs = append(errs, errorf("duplicate entries for key %v", pe.String())...)
+ continue
+ }
+ observed.Insert(pe, child)
+ pes = append(pes, pe)
+ }
+ return pes, observed, errs
+}
+
+func (w *mergingWalker) mergeListItem(t *schema.List, pe fieldpath.PathElement, lChild, rChild value.Value) (out *interface{}, errs ValidationErrors) {
+ w2 := w.prepareDescent(pe, t.ElementType)
+ w2.lhs = lChild
+ w2.rhs = rChild
+ errs = append(errs, w2.merge(pe.String)...)
+ if w2.out != nil {
+ out = w2.out
+ }
+ w.finishDescent(w2)
+ return
+}
+
func (w *mergingWalker) derefList(prefix string, v value.Value) (value.List, ValidationErrors) {
if v == nil {
return nil, nil
diff --git a/typed/merge_test.go b/typed/merge_test.go
index bb1e0a3..63745cd 100644
--- a/typed/merge_test.go
+++ b/typed/merge_test.go
@@ -281,14 +281,63 @@
`{"setStr":["a","b","c"]}`,
`{"setStr":["a","b","c"]}`,
}, {
+ `{"setStr":["a","b"]}`,
+ `{"setStr":["b","a"]}`,
+ `{"setStr":["b","a"]}`,
+ }, {
+ `{"setStr":["a","b","c"]}`,
+ `{"setStr":["d","e","f"]}`,
+ `{"setStr":["a","b","c","d","e","f"]}`,
+ }, {
+ `{"setStr":["a","b","c"]}`,
+ `{"setStr":["c","d","e","f"]}`,
+ `{"setStr":["a","b","c","d","e","f"]}`,
+ }, {
+ `{"setStr":["a","b","c","g","f"]}`,
+ `{"setStr":["c","d","e","f"]}`,
+ `{"setStr":["a","b","c","g","d","e","f"]}`,
+ }, {
+ `{"setStr":["a","b","c"]}`,
+ `{"setStr":["d","e","f","x","y","z"]}`,
+ `{"setStr":["a","b","c","d","e","f","x","y","z"]}`,
+ }, {
+ `{"setStr":["c","d","e","f"]}`,
+ `{"setStr":["a","c","e"]}`,
+ `{"setStr":["a","c","d","e","f"]}`,
+ }, {
+ `{"setStr":["a","b","c","x","y","z"]}`,
+ `{"setStr":["d","e","f"]}`,
+ `{"setStr":["a","b","c","x","y","z","d","e","f"]}`,
+ }, {
+ `{"setStr":["a","b","c","x","y","z"]}`,
+ `{"setStr":["d","e","f","x","y","z"]}`,
+ `{"setStr":["a","b","c","d","e","f","x","y","z"]}`,
+ }, {
+ `{"setStr":["c","a","g","f"]}`,
+ `{"setStr":["c","f","a","g"]}`,
+ `{"setStr":["c","f","a","g"]}`,
+ }, {
+ `{"setStr":["a","b","c","d"]}`,
+ `{"setStr":["d","e","f","a"]}`,
+ `{"setStr":["b","c","d","e","f","a"]}`,
+ }, {
+ `{"setStr":["c","d","e","f","g","h","i","j"]}`,
+ `{"setStr":["2","h","3","e","4","k","l"]}`,
+ `{"setStr":["c","d","f","g","2","h","i","j","3","e","4","k","l"]}`,
+ }, {
+ `{"setStr":["a","b","c","d","e","f","g","h","i","j"]}`,
+ `{"setStr":["1","b","2","h","3","e","4","k","l"]}`,
+ `{"setStr":["a","1","b","c","d","f","g","2","h","i","j","3","e","4","k","l"]}`,
+ }, {
`{"setBool":[true]}`,
`{"setBool":[false]}`,
- `{"setBool":[false,true]}`,
+ `{"setBool":[true, false]}`,
}, {
`{"setNumeric":[1,2,3.14159]}`,
`{"setNumeric":[1,2,3]}`,
- `{"setNumeric":[1,2,3,3.14159]}`,
- }},
+ `{"setNumeric":[1,2,3.14159,3]}`,
+ },
+ },
}, {
name: "associative list",
rootTypeName: "myRoot",
@@ -345,11 +394,11 @@
}, {
`{"list":[{"key":"a","id":1,"value":{"a":"a"}}]}`,
`{"list":[{"key":"a","id":2,"value":{"a":"a"}}]}`,
- `{"list":[{"key":"a","id":2,"value":{"a":"a"}},{"key":"a","id":1,"value":{"a":"a"}}]}`,
+ `{"list":[{"key":"a","id":1,"value":{"a":"a"}},{"key":"a","id":2,"value":{"a":"a"}}]}`,
}, {
`{"list":[{"key":"a","id":1},{"key":"b","id":1}]}`,
`{"list":[{"key":"a","id":1},{"key":"a","id":2}]}`,
- `{"list":[{"key":"a","id":1},{"key":"a","id":2},{"key":"b","id":1}]}`,
+ `{"list":[{"key":"a","id":1},{"key":"b","id":1},{"key":"a","id":2}]}`,
}, {
`{"list":[{"key":"b","id":2}]}`,
`{"list":[{"key":"a","id":1},{"key":"b","id":2},{"key":"c","id":3}]}`,
@@ -357,11 +406,11 @@
}, {
`{"list":[{"key":"a","id":1},{"key":"b","id":2},{"key":"c","id":3}]}`,
`{"list":[{"key":"c","id":3},{"key":"b","id":2}]}`,
- `{"list":[{"key":"c","id":3},{"key":"b","id":2},{"key":"a","id":1}]}`,
+ `{"list":[{"key":"a","id":1},{"key":"c","id":3},{"key":"b","id":2}]}`,
}, {
`{"list":[{"key":"a","id":1},{"key":"b","id":2},{"key":"c","id":3}]}`,
`{"list":[{"key":"c","id":3},{"key":"a","id":1}]}`,
- `{"list":[{"key":"c","id":3},{"key":"a","id":1},{"key":"b","id":2}]}`,
+ `{"list":[{"key":"b","id":2},{"key":"c","id":3},{"key":"a","id":1}]}`,
}, {
`{"atomicList":["a","a","a"]}`,
`{"atomicList":null}`,
