Repository: openconfig/ygot
Pull request #860 (2023-06-05 17:23:02)

Support `ForEachDataField`, `DeepCopy`, `Merge` for ordered maps.
For merge if there is any overlap it simply errors out -- I don't think there is a clear way of merging them if there is a partial overlap.

For overlaps where the second ordered list is a subset of the first, then I can see it as a valid merge -- however I'm opting for simplicity for now since this seems like a more advanced use case.

coveralls: 
[![Coverage Status](https://coveralls.io/builds/60532596/badge)](https://coveralls.io/builds/60532596)

coverage: 89.729% (-0.1%) from 89.838% when pulling **43ef242a5023e0f85051555c9d131f3a2010fdae on orderedmap-helper0** into **02091d38ddb705adb3b6ee1c6f415f1d22e1af6d on master**.


Patch:
diff --git a/internal/yreflect/reflect_orderedmap.go b/internal/yreflect/reflect_orderedmap.go
index 840a8fc..abe3e65 100644
--- a/internal/yreflect/reflect_orderedmap.go
+++ b/internal/yreflect/reflect_orderedmap.go
@@ -42,7 +42,7 @@ func MethodByName(v reflect.Value, name string) (reflect.Value, error) {
 // AppendIntoOrderedMap appends a populated value into the ordered map.
 //
 // There must not exist an existing element with the same key.
-func AppendIntoOrderedMap(orderedMap goOrderedList, value interface{}) error {
+func AppendIntoOrderedMap(orderedMap goOrderedList, value any) error {
 	appendMethod, err := MethodByName(reflect.ValueOf(orderedMap), "Append")
 	if err != nil {
 		return err
diff --git a/util/reflect.go b/util/reflect.go
index e2bed90..a13925f 100644
--- a/util/reflect.go
+++ b/util/reflect.go
@@ -824,10 +824,34 @@ func forEachDataFieldInternal(ni *NodeInfo, in, out interface{}, iterFunction Fi
 	v := ni.FieldValue
 	t := v.Type()
 
+	orderedMap, isOrderedMap := v.Interface().(goOrderedList)
+
 	// Determine whether we need to recurse into the field, or whether it is
 	// a leaf or leaf-list, which are not recursed into when traversing the
 	// data tree.
 	switch {
+	case isOrderedMap:
+		// Handle the case of a keyed map, which is a YANG list.
+		if IsNilOrInvalidValue(v) {
+			return errs
+		}
+		nn := *ni
+		nn.Parent = ni
+		var err error
+		nn.FieldKeys, err = yreflect.OrderedMapKeys(orderedMap)
+		if err != nil {
+			errs = AppendErr(errs, err)
+			return errs
+		}
+		if err := yreflect.RangeOrderedMap(orderedMap, func(k, v reflect.Value) bool {
+			nn := nn
+			nn.FieldValue = v
+			nn.FieldKey = k
+			errs = AppendErrs(errs, forEachDataFieldInternal(&nn, in, out, iterFunction))
+			return true
+		}); err != nil {
+			errs = AppendErr(errs, err)
+		}
 	case IsTypeStructPtr(t):
 		// A struct pointer in a GoStruct is a pointer to another container within
 		// the YANG, therefore we dereference the pointer and then recurse. If the
diff --git a/ygot/struct_validation_map.go b/ygot/struct_validation_map.go
index ea31daa..9bb9073 100644
--- a/ygot/struct_validation_map.go
+++ b/ygot/struct_validation_map.go
@@ -30,6 +30,7 @@ import (
 	"strings"
 
 	"github.com/openconfig/gnmi/errlist"
+	"github.com/openconfig/ygot/internal/yreflect"
 	"github.com/openconfig/ygot/util"
 )
 
@@ -680,9 +681,14 @@ func copyStruct(dstVal, srcVal reflect.Value, accessPath string, opts ...MergeOp
 		dstField := dstVal.Field(i)
 		accessPath := accessPath + "." + srcVal.Type().Field(i).Name
 
+		orderedMap, isOrderedMap := srcField.Interface().(GoOrderedList)
 		switch srcField.Kind() {
 		case reflect.Ptr:
-			errs.Add(copyPtrField(dstField, srcField, accessPath, opts...))
+			if isOrderedMap {
+				errs.Add(copyOrderedMap(dstField, orderedMap, accessPath, opts...))
+			} else {
+				errs.Add(copyPtrField(dstField, srcField, accessPath, opts...))
+			}
 		case reflect.Interface:
 			errs.Add(copyInterfaceField(dstField, srcField, accessPath, opts...))
 		case reflect.Map:
@@ -906,6 +912,74 @@ func validateMap(srcField, dstField reflect.Value) (*mapType, error) {
 	return &mapType{key: st.Key(), value: st.Elem()}, nil
 }
 
+// copyOrderedMap copies srcOrderedMap into dstField. Both srcOrderedMap and
+// dstField (this is a reflect.Value for convenience) are ordered list values.
+// If both srcOrderedMap and dstField are populated, and have non-overlapping
+// keys, then the keys in the src are appended to the dst. If there are
+// overlapping values, then an ereror is returned since the behaviour is not
+// well-defined.
+func copyOrderedMap(dstField reflect.Value, srcOrderedMap GoOrderedList, accessPath string, opts ...MergeOpt) error {
+	dstOrderedMap, dstIsOrderedMap := dstField.Interface().(GoOrderedList)
+	srcField := reflect.ValueOf(srcOrderedMap)
+	if dstType, srcType := srcField.Type(), dstField.Type(); dstType != srcType || !dstIsOrderedMap {
+		return fmt.Errorf("source and destination ordered map types not matching: src: %s, dst: %s", dstType.Name(), srcType.Name())
+	}
+
+	// Skip cases where there are empty maps in both src and dst.
+	// Exception: user wants an empty map to be merged as well.
+	if srcOrderedMap.Len() == 0 && dstOrderedMap.Len() == 0 {
+		if !mergeEmptyMapsEnabled(opts) || srcField.IsNil() {
+			return nil
+		}
+	}
+
+	if dstOrderedMap.Len() == 0 {
+		dstField.Set(reflect.New(dstField.Type().Elem()))
+		dstOrderedMap = dstField.Interface().(GoOrderedList)
+	}
+
+	srcKeys := map[any]struct{}{}
+	keys, err := yreflect.OrderedMapKeys(srcOrderedMap)
+	if err != nil {
+		return err
+	}
+	for _, k := range keys {
+		srcKeys[k.Interface()] = struct{}{}
+	}
+	keys, err = yreflect.OrderedMapKeys(dstOrderedMap)
+	if err != nil {
+		return err
+	}
+	for _, k := range keys {
+		if _, ok := srcKeys[k.Interface()]; ok {
+			return fmt.Errorf("ordered map keys overlap at %v -- merge behaviour is not well defined", k)
+		}
+	}
+
+	elemType, err := yreflect.OrderedMapElementType(dstOrderedMap)
+	if err != nil {
+		return err
+	}
+
+	errs := &errlist.Error{}
+	errs.Separator = "\n"
+	if err := yreflect.RangeOrderedMap(srcOrderedMap, func(k, v reflect.Value) bool {
+		d := reflect.New(elemType.Elem())
+		if err := copyStruct(d.Elem(), v.Elem(), fmt.Sprintf("%s[%#v]", accessPath, k.Interface()), opts...); err != nil {
+			errs.Add(err)
+			return true
+		}
+		if err := yreflect.AppendIntoOrderedMap(dstOrderedMap, d.Interface()); err != nil {
+			errs.Add(err)
+		}
+		return true
+	}); err != nil {
+		errs.Add(err)
+	}
+
+	return errs.Err()
+}
+
 // copySliceField copies srcField into dstField. Both srcField and dstField
 // must have a kind of reflect.Slice kind and contain pointers to structs. If
 // the slice in dstField is populated an error is returned.


Test patch:
diff --git a/integration_tests/schemaops/schemaops_compressed_test.go b/integration_tests/schemaops/schemaops_compressed_test.go
index 0ed69d1..ffc63d8 100644
--- a/integration_tests/schemaops/schemaops_compressed_test.go
+++ b/integration_tests/schemaops/schemaops_compressed_test.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package schemaops
+package schemaops_test
 
 import (
 	"testing"
diff --git a/integration_tests/schemaops/schemaops_test.go b/integration_tests/schemaops/schemaops_test.go
index 17c9b52..818b929 100644
--- a/integration_tests/schemaops/schemaops_test.go
+++ b/integration_tests/schemaops/schemaops_test.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package schemaops
+package schemaops_test
 
 import (
 	"testing"
diff --git a/util/reflect_exported_test.go b/util/reflect_exported_test.go
index cd16d15..0588d14 100644
--- a/util/reflect_exported_test.go
+++ b/util/reflect_exported_test.go
@@ -292,3 +292,87 @@ func TestForEachFieldOrderedMap(t *testing.T) {
 		}
 	}
 }
+
+func TestForEachDataField(t *testing.T) {
+	tests := []struct {
+		desc       string
+		inParent   any
+		in         any
+		out        any
+		inIterFunc util.FieldIteratorFunc
+		wantOut    string
+		wantErr    string
+	}{{
+		desc: "single-keyed list",
+		inParent: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap(t),
+		},
+		in:         nil,
+		inIterFunc: util.PrintMapKeysSchemaAnnotationFunc,
+		wantOut: `foo (string)/ordered-lists : 
+{ΛMetadata:    [],
+ Key:           "foo",
+ ΛKey:         [],
+ OrderedList:   nil,
+ ΛOrderedList: [],
+ ParentKey:     nil,
+ ΛParentKey:   [],
+ RoVa...
+, bar (string)/ordered-lists : 
+{ΛMetadata:    [],
+ Key:           "bar",
+ ΛKey:         [],
+ OrderedList:   nil,
+ ΛOrderedList: [],
+ ParentKey:     nil,
+ ΛParentKey:   [],
+ RoVa...
+, `,
+	}, {
+		desc: "multi-keyed list",
+		inParent: &ctestschema.Device{
+			OrderedMultikeyedList: ctestschema.GetOrderedMapMultikeyed(t),
+		},
+		in:         nil,
+		inIterFunc: util.PrintMapKeysSchemaAnnotationFunc,
+		wantOut: `{ foo (string), 42 (uint64) }/ordered-multikeyed-lists : 
+{ΛMetadata: [],
+ Key1:       "foo",
+ ΛKey1:     [],
+ Key2:       42,
+ ΛKey2:     [],
+ Value:      "foo-val",
+ ΛValue:    []} (string)
+, { bar (string), 42 (uint64) }/ordered-multikeyed-lists : 
+{ΛMetadata: [],
+ Key1:       "bar",
+ ΛKey1:     [],
+ Key2:       42,
+ ΛKey2:     [],
+ Value:      "bar-val",
+ ΛValue:    []} (string)
+, { baz (string), 84 (uint64) }/ordered-multikeyed-lists : 
+{ΛMetadata: [],
+ Key1:       "baz",
+ ΛKey1:     [],
+ Key2:       84,
+ ΛKey2:     [],
+ Value:      "baz-val",
+ ΛValue:    []} (string)
+, `,
+	}}
+
+	for _, tt := range tests {
+		outStr := ""
+		var errs util.Errors = util.ForEachDataField(tt.inParent, tt.in, &outStr, tt.inIterFunc)
+		if diff := cmp.Diff(errs.String(), tt.wantErr); diff != "" {
+			t.Errorf("error (-got, +want):\n%s", diff)
+		}
+		if len(errs) > 0 {
+			continue
+		}
+		if diff := cmp.Diff(outStr, tt.wantOut); diff != "" {
+			t.Errorf("%s (-got, +want):\n%s", tt.desc, diff)
+		}
+	}
+}
diff --git a/util/reflect_test.go b/util/reflect_test.go
index 13a4ff4..4bc8cf2 100644
--- a/util/reflect_test.go
+++ b/util/reflect_test.go
@@ -938,7 +938,7 @@ var (
 		return
 	}
 
-	printMapKeysSchemaAnnotationFunc = func(ni *NodeInfo, in, out interface{}) (errs Errors) {
+	PrintMapKeysSchemaAnnotationFunc = func(ni *NodeInfo, in, out interface{}) (errs Errors) {
 		if IsNilOrInvalidValue(ni.FieldKey) {
 			return
 		}
@@ -1255,7 +1255,7 @@ func TestForEachDataField(t *testing.T) {
 			desc:         "map keys with no struct schema",
 			in:           nil,
 			parentStruct: &StructOfMapOfStructs{BasicStructMapField: map[string]BasicStruct{"basicStruct1": basicStruct1}, BasicStructPtrMapField: map[string]*BasicStruct{"basicStruct2": &basicStruct2}},
-			iterFunc:     printMapKeysSchemaAnnotationFunc,
+			iterFunc:     PrintMapKeysSchemaAnnotationFunc,
 			wantOut: `basicStruct1 (string)/basic-struct : 
 {Int32Field:     42,
  StringField:    "forty two",
diff --git a/ygot/struct_validation_map_exported_test.go b/ygot/struct_validation_map_exported_test.go
index e77898a..d151796 100644
--- a/ygot/struct_validation_map_exported_test.go
+++ b/ygot/struct_validation_map_exported_test.go
@@ -22,8 +22,11 @@ import (
 	"strings"
 	"testing"
 
+	"github.com/google/go-cmp/cmp"
 	"github.com/kylelemons/godebug/pretty"
+	"github.com/openconfig/gnmi/errdiff"
 	"github.com/openconfig/ygot/integration_tests/schemaops/ctestschema"
+	"github.com/openconfig/ygot/internal/ytestutil"
 	"github.com/openconfig/ygot/testutil"
 	"github.com/openconfig/ygot/ygot"
 )
@@ -303,3 +306,180 @@ func TestEmitJSON(t *testing.T) {
 		})
 	}
 }
+
+func TestDeepCopyOrderedMap(t *testing.T) {
+	tests := []struct {
+		name             string
+		in               func() *ctestschema.Device
+		inKey            string
+		wantErrSubstring string
+	}{{
+		name: "single-keyed",
+		in:   func() *ctestschema.Device { return &ctestschema.Device{OrderedList: ctestschema.GetOrderedMap(t)} },
+	}, {
+		name: "multi-keyed",
+		in: func() *ctestschema.Device {
+			return &ctestschema.Device{OrderedMultikeyedList: ctestschema.GetOrderedMapMultikeyed(t)}
+		},
+	}, {
+		name: "nested",
+		in: func() *ctestschema.Device {
+			return &ctestschema.Device{OrderedList: ctestschema.GetNestedOrderedMap(t)}
+		},
+	}}
+
+	for _, tt := range tests {
+		got, err := ygot.DeepCopy(tt.in())
+		gotRoot, ok := got.(*ctestschema.Device)
+		if !ok {
+			t.Fatalf("Got object that's not root device: %T", got)
+		}
+
+		in := tt.in()
+		if err != nil {
+			if diff := errdiff.Substring(err, tt.wantErrSubstring); diff != "" {
+				t.Errorf("%s: DeepCopy(%#v): did not get expected error, %s", tt.name, in, diff)
+			}
+			continue
+		}
+
+		if diff := cmp.Diff(got, in, ytestutil.OrderedMapCmpOptions...); diff != "" {
+			t.Errorf("did not get identical copy, diff(-got,+want):\n%s", diff)
+		}
+
+		gotValues := gotRoot.OrderedList.Values()
+		for i, inV := range in.OrderedList.Values() {
+			gotV := gotValues[i]
+			if inV == gotV {
+				t.Errorf("%s: DeepCopy: after copy, input and copy have same memory address: %v", tt.name, inV)
+			}
+			if gotV == nil {
+				continue
+			}
+			if inV.Key != nil && inV.Key == gotV.Key {
+				t.Errorf("%s: DeepCopy: key have same address", tt.name)
+			}
+			if inV.ParentKey != nil && inV.ParentKey == gotV.ParentKey {
+				t.Errorf("%s: DeepCopy: ParentKey have same address", tt.name)
+			}
+			if inV.RoValue != nil && inV.RoValue == gotV.RoValue {
+				t.Errorf("%s: DeepCopy: RoValue have same address", tt.name)
+			}
+			if inV.Value != nil && inV.Value == gotV.Value {
+				t.Errorf("%s: DeepCopy: Value have same address", tt.name)
+			}
+			for j, inV := range inV.OrderedList.Values() {
+				gotV := gotValues[i].OrderedList.Values()[j]
+				if inV == gotV {
+					t.Errorf("%s: DeepCopy: after copy, input and copy have same memory address: %v", tt.name, inV)
+				}
+				if gotV == nil {
+					continue
+				}
+				if inV.Key != nil && inV.Key == gotV.Key {
+					t.Errorf("%s: DeepCopy: key have same address", tt.name)
+				}
+				if inV.ParentKey != nil && inV.ParentKey == gotV.ParentKey {
+					t.Errorf("%s: DeepCopy: ParentKey have same address", tt.name)
+				}
+				if inV.Value != nil && inV.Value == gotV.Value {
+					t.Errorf("%s: DeepCopy: Value have same address", tt.name)
+				}
+			}
+		}
+
+		gotMultikeyedValues := gotRoot.OrderedMultikeyedList.Values()
+		for i, inV := range in.OrderedMultikeyedList.Values() {
+			gotV := gotMultikeyedValues[i]
+			if inV == gotV {
+				t.Errorf("%s: DeepCopy: after copy, input and copy have same memory address: %v", tt.name, inV)
+			}
+			if gotV == nil {
+				continue
+			}
+			if inV.Key1 != nil && inV.Key1 == gotV.Key1 {
+				t.Errorf("%s: DeepCopy: key have same address", tt.name)
+			}
+			if inV.Key2 != nil && inV.Key2 == gotV.Key2 {
+				t.Errorf("%s: DeepCopy: RoValue have same address", tt.name)
+			}
+			if inV.Value != nil && inV.Value == gotV.Value {
+				t.Errorf("%s: DeepCopy: Value have same address", tt.name)
+			}
+		}
+	}
+}
+
+func TestMergeStructsOrderedMap(t *testing.T) {
+	tests := []struct {
+		name          string
+		inA           *ctestschema.Device
+		inB           *ctestschema.Device
+		inOpts        []ygot.MergeOpt
+		want          *ctestschema.Device
+		wantErrSubstr string
+	}{{
+		name: "non-overlapping ordered lists",
+		inA: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap(t),
+		},
+		inB: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap2(t),
+		},
+		want: &ctestschema.Device{
+			OrderedList: func() *ctestschema.OrderedList_OrderedMap {
+				list := ctestschema.GetOrderedMap(t)
+				for _, v := range ctestschema.GetOrderedMap2(t).Values() {
+					list.Append(v)
+				}
+				return list
+			}(),
+		},
+	}, {
+		name: "merge from non-empty to empty",
+		inA:  &ctestschema.Device{},
+		inB: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap2(t),
+		},
+		want: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap2(t),
+		},
+	}, {
+		name: "merge from empty to non-empty",
+		inA: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap2(t),
+		},
+		inB: &ctestschema.Device{},
+		want: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap2(t),
+		},
+	}, {
+		// NOTE: For overlaps where the second ordered list is a subset
+		// of the first, then this may be a valid merge and we may want
+		// to implement this if there is a use case.
+		name: "overlapping ordered lists",
+		inA: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap(t),
+		},
+		inB: &ctestschema.Device{
+			OrderedList: ctestschema.GetOrderedMap(t),
+		},
+		wantErrSubstr: "ordered map keys overlap at foo -- merge behaviour is not well defined",
+	}}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			got, err := ygot.MergeStructs(tt.inA, tt.inB, tt.inOpts...)
+			if diff := errdiff.Substring(err, tt.wantErrSubstr); diff != "" {
+				t.Errorf("%s: MergeStructs(%v, %v): did not get expected error status, %s", tt.name, tt.inA, tt.inB, diff)
+			}
+			if err != nil {
+				return
+			}
+
+			if diff := cmp.Diff(got, tt.want, ytestutil.OrderedMapCmpOptions...); diff != "" {
+				t.Errorf("%s: MergeStructs(%v, %v): did not get expected returned struct, diff(-got,+want):\n%s", tt.name, tt.inA, tt.inB, diff)
+			}
+		})
+	}
+}