Repository: google/starlark-go
Pull request #457 (2023-02-27 20:07:53)

Adding new ThreeWayComparable interface
Re: https://github.com/google/starlark-go/issues/356

This adds a new `TotallyOrdered` interface, similar to `Comparable` which returns an integer representing the <, ==, > relation between values. The `CompareDepth` function has been to updated check for this interface and handle this return style if applicable.

Also refactors `int`, `float`, `time.Time` and `time.Duration` types to use the new interface.

The previous `Comparable` interface will have to be maintained, not just for API compatibility but also for types which define equality/inequality but not ordering (for example, [structs](https://github.com/google/starlark-go/blob/c52844e64a10fb0a67ae99619ee98a49de4f8210/starlarkstruct/struct.go#L247))

#### Open questions:

 - Is the ThreeWayCompareSameType name too verbose? I was thinking about overloading the name CompareSameType but that felt like it would get confusing. -> Yes, change to `TotallyOrdered`
 - Should I also update the other orderable types (float, str, list, etc) to use this interface in this PR? -> Yes.





Patch:
diff --git a/lib/time/time.go b/lib/time/time.go
index 7316333..0f78142 100644
--- a/lib/time/time.go
+++ b/lib/time/time.go
@@ -209,16 +209,15 @@ func (d Duration) AttrNames() []string {
 	}
 }
 
-// CompareSameType implements comparison of two Duration values. required by
-// starlark.Comparable interface.
-func (d Duration) CompareSameType(op syntax.Token, v starlark.Value, depth int) (bool, error) {
-	cmp := 0
+// Cmp implements comparison of two Duration values. required by
+// starlark.TotallyOrdered interface.
+func (d Duration) Cmp(v starlark.Value, depth int) (int, error) {
 	if x, y := d, v.(Duration); x < y {
-		cmp = -1
+		return -1, nil
 	} else if x > y {
-		cmp = 1
+		return 1, nil
 	}
-	return threeway(op, cmp), nil
+	return 0, nil
 }
 
 // Binary implements binary operators, which satisfies the starlark.HasBinary
@@ -392,18 +391,17 @@ func (t Time) AttrNames() []string {
 	)
 }
 
-// CompareSameType implements comparison of two Time values. required by
-// starlark.Comparable interface.
-func (t Time) CompareSameType(op syntax.Token, yV starlark.Value, depth int) (bool, error) {
+// Cmp implements comparison of two Time values. Required by
+// starlark.TotallyOrdered interface.
+func (t Time) Cmp(yV starlark.Value, depth int) (int, error) {
 	x := time.Time(t)
 	y := time.Time(yV.(Time))
-	cmp := 0
 	if x.Before(y) {
-		cmp = -1
+		return -1, nil
 	} else if x.After(y) {
-		cmp = 1
+		return 1, nil
 	}
-	return threeway(op, cmp), nil
+	return 0, nil
 }
 
 // Binary implements binary operators, which satisfies the starlark.HasBinary
@@ -485,23 +483,3 @@ func builtinAttrNames(methods map[string]builtinMethod) []string {
 	sort.Strings(names)
 	return names
 }
-
-// Threeway interprets a three-way comparison value cmp (-1, 0, +1)
-// as a boolean comparison (e.g. x < y).
-func threeway(op syntax.Token, cmp int) bool {
-	switch op {
-	case syntax.EQL:
-		return cmp == 0
-	case syntax.NEQ:
-		return cmp != 0
-	case syntax.LE:
-		return cmp <= 0
-	case syntax.LT:
-		return cmp < 0
-	case syntax.GE:
-		return cmp >= 0
-	case syntax.GT:
-		return cmp > 0
-	}
-	panic(op)
-}
diff --git a/resolve/resolve.go b/resolve/resolve.go
index 56e33ba..09b9acd 100644
--- a/resolve/resolve.go
+++ b/resolve/resolve.go
@@ -746,7 +746,7 @@ func (r *resolver) expr(e syntax.Expr) {
 				}
 				x := binop.X.(*syntax.Ident)
 				if seenName[x.Name] {
-					r.errorf(x.NamePos, "keyword argument %s repeated", x.Name)
+					r.errorf(x.NamePos, "keyword argument %q is repeated", x.Name)
 				} else {
 					if seenName == nil {
 						seenName = make(map[string]bool)
diff --git a/starlark/int.go b/starlark/int.go
index 5c5ea12..a264e9d 100644
--- a/starlark/int.go
+++ b/starlark/int.go
@@ -190,14 +190,16 @@ func (i Int) Hash() (uint32, error) {
 	}
 	return 12582917 * uint32(lo+3), nil
 }
-func (x Int) CompareSameType(op syntax.Token, v Value, depth int) (bool, error) {
+
+// Required by the TotallyOrdered interface
+func (x Int) Cmp(v Value, depth int) (int, error) {
 	y := v.(Int)
 	xSmall, xBig := x.get()
 	ySmall, yBig := y.get()
 	if xBig != nil || yBig != nil {
-		return threeway(op, x.bigInt().Cmp(y.bigInt())), nil
+		return x.bigInt().Cmp(y.bigInt()), nil
 	}
-	return threeway(op, signum64(xSmall-ySmall)), nil
+	return signum64(xSmall - ySmall), nil // safe: int32 operands
 }
 
 // Float returns the float value nearest i.
diff --git a/starlark/value.go b/starlark/value.go
index 7dc0cba..da21795 100644
--- a/starlark/value.go
+++ b/starlark/value.go
@@ -131,15 +131,41 @@ type Comparable interface {
 	CompareSameType(op syntax.Token, y Value, depth int) (bool, error)
 }
 
+// A TotallyOrdered is a type whose values form a total order:
+// if x and y are of the same TotallyOrdered type, then x must be less than y,
+// greater than y, or equal to y.
+//
+// It is simpler than Comparable and should be preferred in new code,
+// but if a type implements both interfaces, Comparable takes precedence.
+type TotallyOrdered interface {
+	Value
+	// Cmp compares two values x and y of the same totally ordered type.
+	// It returns negative if x < y, positive if x > y, and zero if the values are equal.
+	//
+	// Implementations that recursively compare subcomponents of
+	// the value should use the CompareDepth function, not Cmp, to
+	// avoid infinite recursion on cyclic structures.
+	//
+	// The depth parameter is used to bound comparisons of cyclic
+	// data structures.  Implementations should decrement depth
+	// before calling CompareDepth and should return an error if depth
+	// < 1.
+	//
+	// Client code should not call this method.  Instead, use the
+	// standalone Compare or Equals functions, which are defined for
+	// all pairs of operands.
+	Cmp(y Value, depth int) (int, error)
+}
+
 var (
-	_ Comparable = Int{}
-	_ Comparable = False
-	_ Comparable = Float(0)
-	_ Comparable = String("")
-	_ Comparable = (*Dict)(nil)
-	_ Comparable = (*List)(nil)
-	_ Comparable = Tuple(nil)
-	_ Comparable = (*Set)(nil)
+	_ TotallyOrdered = Int{}
+	_ TotallyOrdered = Float(0)
+	_ Comparable     = False
+	_ Comparable     = String("")
+	_ Comparable     = (*Dict)(nil)
+	_ Comparable     = (*List)(nil)
+	_ Comparable     = Tuple(nil)
+	_ Comparable     = (*Set)(nil)
 )
 
 // A Callable value f may be the operand of a function call, f(x).
@@ -439,9 +465,9 @@ func isFinite(f float64) bool {
 	return math.Abs(f) <= math.MaxFloat64
 }
 
-func (x Float) CompareSameType(op syntax.Token, y_ Value, depth int) (bool, error) {
+func (x Float) Cmp(y_ Value, depth int) (int, error) {
 	y := y_.(Float)
-	return threeway(op, floatCmp(x, y)), nil
+	return floatCmp(x, y), nil
 }
 
 // floatCmp performs a three-valued comparison on floats,
@@ -1299,6 +1325,14 @@ func CompareDepth(op syntax.Token, x, y Value, depth int) (bool, error) {
 			return xcomp.CompareSameType(op, y, depth)
 		}
 
+		if xcomp, ok := x.(TotallyOrdered); ok {
+			t, err := xcomp.Cmp(y, depth)
+			if err != nil {
+				return false, err
+			}
+			return threeway(op, t), nil
+		}
+
 		// use identity comparison
 		switch op {
 		case syntax.EQL:


Test patch:
diff --git a/resolve/testdata/resolve.star b/resolve/testdata/resolve.star
index ce67110..4fca831 100644
--- a/resolve/testdata/resolve.star
+++ b/resolve/testdata/resolve.star
@@ -340,7 +340,7 @@ U = 1 # ok (legacy)
 ---
 # https://github.com/bazelbuild/starlark/starlark/issues/21
 def f(**kwargs): pass
-f(a=1, a=1) ### `keyword argument a repeated`
+f(a=1, a=1) ### `keyword argument "a" is repeated`
 
 
 ---