Repository: openconfig/ygot
Pull request #787 (2023-02-17 00:36:23)

Add ComparePath func
i also broke the circular dependency by renaming the package in this file to util_test

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

Coverage: 90.397% (+0.03%) from 90.366% when pulling **052437c5ba02f92b4246c5cc4272bb3fe372fcb3 on DanG100:compare-path** into **48f2c80d17a2dac6a2794b751cd4ddc31ef1f856 on openconfig:master**.


Patch:
diff --git a/util/gnmi.go b/util/gnmi.go
index 8ef9771..b422c97 100644
--- a/util/gnmi.go
+++ b/util/gnmi.go
@@ -255,3 +255,101 @@ func JoinPaths(prefix, suffix *gpb.Path) (*gpb.Path, error) {
 	}
 	return joined, nil
 }
+
+// CompareRelation describes of the relation between to gNMI paths.
+type CompareRelation int
+
+const (
+	// Equal means the paths are the same.
+	Equal CompareRelation = iota
+	// Disjoint means the paths do not overlap at all.
+	Disjoint
+	// Subset means a path is strictly smaller than the other.
+	Subset
+	// Superset means a path is strictly larger than the other.
+	Superset
+	// PartialIntersect means a path partial overlaps the other.
+	PartialIntersect
+)
+
+// ComparePaths returns the set relation between two paths.
+// It returns an error if the paths are invalid or not one of the relations.
+func ComparePaths(a, b *gpb.Path) CompareRelation {
+	if a.Origin != b.Origin {
+		return Disjoint
+	}
+
+	shortestLen := len(a.Elem)
+
+	// If path a is longer than b, then we start by assuming a subset relationship, and vice versa.
+	// Otherwise assume paths are equal.
+	relation := Equal
+	if len(a.Elem) > len(b.Elem) {
+		relation = Subset
+		shortestLen = len(b.Elem)
+	} else if len(a.Elem) < len(b.Elem) {
+		relation = Superset
+	}
+
+	for i := 0; i < shortestLen; i++ {
+		elemRelation := comparePathElem(a.Elem[i], b.Elem[i])
+		switch elemRelation {
+		case PartialIntersect, Disjoint:
+			return elemRelation
+		case Superset, Subset:
+			if relation == Equal {
+				relation = elemRelation
+			} else if elemRelation != relation {
+				return PartialIntersect
+			}
+		}
+	}
+
+	return relation
+}
+
+// comparePathElem compare two path elements a, b and returns:
+// subset: if every definite key in a is wildcard in b.
+// superset: if every wildcard key in b is non-wildcard in b.
+// error: not two keys are both subset and superset.
+func comparePathElem(a, b *gpb.PathElem) CompareRelation {
+	if a.Name != b.Name {
+		return Disjoint
+	}
+
+	// Start by assuming a perfect match. Then relax this property as we scan through the key values.
+	setRelation := Equal
+	for k, aVal := range a.Key {
+		bVal, ok := b.Key[k]
+		switch {
+		case aVal == bVal, aVal == "*" && !ok: // Values are equal (possibly be implicit wildcards).
+			continue
+		case aVal == "*": // Values not equal, a value is superset of b value.
+			if setRelation == Subset {
+				return PartialIntersect
+			}
+			setRelation = Superset
+		case bVal == "*", !ok: // Values not equal, a value is subset of b value.
+			if setRelation == Superset {
+				return PartialIntersect
+			}
+			setRelation = Subset
+		default: // Values not equal, but of the same size.
+			return Disjoint
+		}
+	}
+	for k, bVal := range b.Key {
+		_, ok := a.Key[k]
+		switch {
+		case ok, bVal == "*": // Key has already been visited, or values are equal.
+			continue
+		case bVal != "*": // If a contains an implicit wildcard and b isn't.
+			if setRelation == Subset {
+				return PartialIntersect
+			}
+			setRelation = Superset
+		}
+	}
+
+	return setRelation
+}


Test patch:
diff --git a/util/gnmi_test.go b/util/gnmi_test.go
index a7cb91e..fbd832f 100644
--- a/util/gnmi_test.go
+++ b/util/gnmi_test.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package util
+package util_test
 
 import (
 	"strings"
@@ -21,6 +21,8 @@ import (
 	"github.com/google/go-cmp/cmp"
 	"github.com/openconfig/gnmi/errdiff"
 	"github.com/openconfig/goyang/pkg/yang"
+	"github.com/openconfig/ygot/util"
+	"github.com/openconfig/ygot/ygot"
 	"google.golang.org/protobuf/encoding/prototext"
 	"google.golang.org/protobuf/proto"
 	"google.golang.org/protobuf/testing/protocmp"
@@ -123,7 +125,7 @@ func TestPathMatchesPrefix(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got, want := PathMatchesPrefix(pathNoKeysToGNMIPath(tt.path), strings.Split(tt.prefix, "/")), tt.want; got != want {
+			if got, want := util.PathMatchesPrefix(pathNoKeysToGNMIPath(tt.path), strings.Split(tt.prefix, "/")), tt.want; got != want {
 				t.Errorf("%s: got: %v want: %v", tt.desc, got, want)
 			}
 		})
@@ -191,7 +193,7 @@ func TestTrimGNMIPathPrefix(t *testing.T) {
 		t.Run(tt.desc, func(t *testing.T) {
 			path := pathNoKeysToGNMIPath(tt.path)
 			prefix := strings.Split(tt.prefix, "/")
-			got := gnmiPathNoKeysToPath(TrimGNMIPathPrefix(path, prefix))
+			got := gnmiPathNoKeysToPath(util.TrimGNMIPathPrefix(path, prefix))
 			if got != tt.want {
 				t.Errorf("%s: got: %s want: %s", tt.desc, got, tt.want)
 			}
@@ -229,7 +231,7 @@ func TestPopGNMIPath(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got, want := gnmiPathNoKeysToPath(PopGNMIPath(pathNoKeysToGNMIPath(tt.path))), tt.want; got != want {
+			if got, want := gnmiPathNoKeysToPath(util.PopGNMIPath(pathNoKeysToGNMIPath(tt.path))), tt.want; got != want {
 				t.Errorf("%s: got: %s want: %s", tt.desc, got, want)
 			}
 		})
@@ -325,7 +327,7 @@ func TestPathElemsEqual(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got := PathElemsEqual(tt.lhs, tt.rhs); got != tt.want {
+			if got := util.PathElemsEqual(tt.lhs, tt.rhs); got != tt.want {
 				t.Fatalf("did not get expected result, got: %v, want: %v", got, tt.want)
 			}
 		})
@@ -424,7 +426,7 @@ func TestPathElemSlicesEqual(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got := PathElemSlicesEqual(tt.inElemsA, tt.inElemsB); got != tt.want {
+			if got := util.PathElemSlicesEqual(tt.inElemsA, tt.inElemsB); got != tt.want {
 				t.Fatalf("did not get expected result, got: %v, want: %v", got, tt.want)
 			}
 		})
@@ -519,7 +521,7 @@ func TestPathMatchesPathElemPrefix(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got := PathMatchesPathElemPrefix(tt.inPath, tt.inPrefix); got != tt.want {
+			if got := util.PathMatchesPathElemPrefix(tt.inPath, tt.inPrefix); got != tt.want {
 				t.Fatalf("did not get expected result, got: %v, want: %v", got, tt.want)
 			}
 		})
@@ -746,7 +748,7 @@ func TestPathMatchesQuery(t *testing.T) {
 	}}
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got := PathMatchesQuery(tt.inPath, tt.inQuery); got != tt.want {
+			if got := util.PathMatchesQuery(tt.inPath, tt.inQuery); got != tt.want {
 				t.Fatalf("did not get expected result, got: %v, want: %v", got, tt.want)
 			}
 		})
@@ -836,7 +838,7 @@ func TestTrimGNMIPathElemPrefix(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			if got := TrimGNMIPathElemPrefix(tt.inPath, tt.inPrefix); !proto.Equal(got, tt.want) {
+			if got := util.TrimGNMIPathElemPrefix(tt.inPath, tt.inPrefix); !proto.Equal(got, tt.want) {
 				t.Fatalf("did not get expected path, got: %s, want: %s", prototext.Format(got), prototext.Format(tt.want))
 			}
 		})
@@ -872,7 +874,7 @@ func TestFindPathElemPrefix(t *testing.T) {
 	}}
 
 	for _, tt := range tests {
-		if got := FindPathElemPrefix(tt.inPaths); !proto.Equal(got, tt.want) {
+		if got := util.FindPathElemPrefix(tt.inPaths); !proto.Equal(got, tt.want) {
 			t.Errorf("%s: FindPathElemPrefix(%v): did not get expected prefix, got: %s, want: %s", tt.name, tt.inPaths, prototext.Format(got), prototext.Format(tt.want))
 		}
 	}
@@ -979,7 +981,7 @@ func TestFindModelData(t *testing.T) {
 	}}
 
 	for _, tt := range tests {
-		got, err := FindModelData(tt.in)
+		got, err := util.FindModelData(tt.in)
 
 		if diff := errdiff.Substring(err, tt.wantErrSubstring); diff != "" {
 			t.Errorf("%s: FindModelData(%v): did not get expected error, %s", tt.name, tt.in, diff)
@@ -1039,7 +1041,7 @@ func TestJoinPaths(t *testing.T) {
 
 	for _, tt := range tests {
 		t.Run(tt.desc, func(t *testing.T) {
-			got, err := JoinPaths(tt.prefix, tt.suffix)
+			got, err := util.JoinPaths(tt.prefix, tt.suffix)
 			if diff := errdiff.Substring(err, tt.wantErrSubstring); diff != "" {
 				t.Errorf("JoinPaths(%v, %v) got unexpected error diff: %s", tt.prefix, tt.suffix, diff)
 			}
@@ -1052,3 +1054,132 @@ func TestJoinPaths(t *testing.T) {
 		})
 	}
 }
+
+func mustStringToPath(t testing.TB, path string) *gpb.Path {
+	p, err := ygot.StringToStructuredPath(path)
+	if err != nil {
+		t.Fatal(err)
+	}
+	return p
+}
+
+func TestComparePaths(t *testing.T) {
+	tests := []struct {
+		desc string
+		a, b *gpb.Path
+		want util.CompareRelation
+	}{{
+		desc: "different origins",
+		a:    &gpb.Path{Origin: "foo"},
+		b:    &gpb.Path{Origin: "bar"},
+		want: util.Disjoint,
+	}, {
+		desc: "disjoint paths",
+		a:    mustStringToPath(t, "/foo"),
+		b:    mustStringToPath(t, "/bar"),
+		want: util.Disjoint,
+	}, {
+		desc: "disjoint paths by list keys",
+		a:    mustStringToPath(t, "/foo[a=1][b=2]"),
+		b:    mustStringToPath(t, "/foo[a=1][b=3]"),
+		want: util.Disjoint,
+	}, {
+		desc: "equal paths",
+		a:    mustStringToPath(t, "/foo"),
+		b:    mustStringToPath(t, "/foo"),
+		want: util.Equal,
+	}, {
+		desc: "equal paths with list keys",
+		a:    mustStringToPath(t, "/foo[a=1]"),
+		b:    mustStringToPath(t, "/foo[a=1]"),
+		want: util.Equal,
+	}, {
+		desc: "equal paths with implicit wildcards",
+		a:    mustStringToPath(t, "/foo[a=*]"),
+		b:    mustStringToPath(t, "/foo"),
+		want: util.Equal,
+	}, {
+		desc: "equal paths with implicit wildcards",
+		a:    mustStringToPath(t, "/foo"),
+		b:    mustStringToPath(t, "/foo[a=*]"),
+		want: util.Equal,
+	}, {
+		desc: "superset by length",
+		a:    mustStringToPath(t, "/foo"),
+		b:    mustStringToPath(t, "/foo/bar"),
+		want: util.Superset,
+	}, {
+		desc: "superset by length and keys",
+		a:    mustStringToPath(t, "/foo[a=*]"),
+		b:    mustStringToPath(t, "/foo[b=1]/bar"),
+		want: util.Superset,
+	}, {
+		desc: "superset by list keys",
+		a:    mustStringToPath(t, "/foo[a=*]"),
+		b:    mustStringToPath(t, "/foo[a=1]"),
+		want: util.Superset,
+	}, {
+		desc: "superset by list keys implicit wildcard",
+		a:    mustStringToPath(t, "/foo"),
+		b:    mustStringToPath(t, "/foo[a=1]"),
+		want: util.Superset,
+	}, {
+		desc: "subset by length",
+		a:    mustStringToPath(t, "/foo/bar"),
+		b:    mustStringToPath(t, "/foo"),
+		want: util.Subset,
+	}, {
+		desc: "subset by length and keys",
+		a:    mustStringToPath(t, "/foo[a=1]/bar"),
+		b:    mustStringToPath(t, "/foo[b=*]"),
+		want: util.Subset,
+	}, {
+		desc: "subset by list keys",
+		a:    mustStringToPath(t, "/foo[a=1]"),
+		b:    mustStringToPath(t, "/foo[a=*]"),
+		want: util.Subset,
+	}, {
+		desc: "subset by list keys implicit wildcard",
+		a:    mustStringToPath(t, "/foo[a=1]"),
+		b:    mustStringToPath(t, "/foo"),
+		want: util.Subset,
+	}, {
+		desc: "error single elem is both subset and superset",
+		a:    mustStringToPath(t, "/foo[a=1][b=*]"),
+		b:    mustStringToPath(t, "/foo[a=*][b=1]"),
+		want: util.PartialIntersect,
+	}, {
+		desc: "error single elem is both subset and superset implicit wildcards",
+		a:    mustStringToPath(t, "/foo[a=1]"),
+		b:    mustStringToPath(t, "/foo[b=1]"),
+		want: util.PartialIntersect,
+	}, {
+		desc: "error path is both subset and superset",
+		a:    mustStringToPath(t, "/foo[a=*]/bar[b=1]"),
+		b:    mustStringToPath(t, "/foo[b=1]/bar[b=*]"),
+		want: util.PartialIntersect,
+	}, {
+		desc: "error path elem is both subset and superset",
+		a:    mustStringToPath(t, "/foo[a=1]/bar[b=*]"),
+		b:    mustStringToPath(t, "/foo[b=*]/bar[b=1]"),
+		want: util.PartialIntersect,
+	}, {
+		desc: "error shorter path is both subset and superset",
+		a:    mustStringToPath(t, "/foo[a=*]/bar"),
+		b:    mustStringToPath(t, "/foo[b=1]"),
+		want: util.PartialIntersect,
+	}, {
+		desc: "error path elem is both subset and superset",
+		a:    mustStringToPath(t, "/foo[a=1]"),
+		b:    mustStringToPath(t, "/foo[b=*]/bar"),
+		want: util.PartialIntersect,
+	}}
+	for _, tt := range tests {
+		t.Run(tt.desc, func(t *testing.T) {
+			got := util.ComparePaths(tt.a, tt.b)
+			if got != tt.want {
+				t.Errorf("ComparePaths(%v, %v) got unexpected result: got %v, want %v", tt.a, tt.b, got, tt.want)
+			}
+		})
+	}
+}