cue: tighten subsumes for disjunction
now we have explicitly marked defaults, we can tighten
subsumption
Change-Id: I8d689d74b8c11924453ceeefd22dcd19b73c6f8a
diff --git a/cue/subsume.go b/cue/subsume.go
index 008e5ae..fccc07c 100644
--- a/cue/subsume.go
+++ b/cue/subsume.go
@@ -210,18 +210,23 @@
// subsumes for disjunction is logically precise. However, just like with
// structural subsumption, it should not have to be called after evaluation.
func (x *disjunction) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
+ // A disjunction subsumes another disjunction if all values of v are
+ // subsumed by the values of x, and default values in v are subsumed by the
+ // default values of x.
+ //
+ // This assumes that overlapping ranges in x are merged. If this is not the
+ // case, subsumes will return a false negative, which is allowed.
if d, ok := v.(*disjunction); ok {
- // TODO: the result of subsuming a value by a disjunction is logically
- // the subsumed value. However, since we have default semantics, we
- // should mark a resulting subsumed value as ambiguous if necessary.
- // Also, prove that the returned subsumed single value is always the
- // left-most matching value.
- return false
// at least one value in x should subsume each value in d.
+ outer:
for _, vd := range d.values {
- if !subsumes(ctx, x, vd.val, 0) {
- return false
+ // v is subsumed if any value in x subsumes v.
+ for _, vx := range x.values {
+ if (vx.marked || !vd.marked) && subsumes(ctx, vx.val, vd.val, 0) {
+ continue outer
+ }
}
+ return false
}
return true
}
diff --git a/cue/subsume_test.go b/cue/subsume_test.go
index 2781be5..b48f8ef 100644
--- a/cue/subsume_test.go
+++ b/cue/subsume_test.go
@@ -146,11 +146,8 @@
71: {subsumes: false, in: `a: {a:1, b:1}, b: {a:1}`},
72: {subsumes: false, in: `a: {s: { a:1} }, b: { s: {}}`},
- // Disjunction TODO: for now these two are false: unifying may result in
- // an ambiguity that we are currently not handling, so safer to not
- // unify.
- 84: {subsumes: false, in: `a: 1 | 2, b: 2 | 1`},
- 85: {subsumes: false, in: `a: 1 | 2, b: 1 | 2`},
+ 84: {subsumes: true, in: `a: 1 | 2, b: 2 | 1`},
+ 85: {subsumes: true, in: `a: 1 | 2, b: 1 | 2`},
86: {subsumes: true, in: `a: number, b: 2 | 1`},
87: {subsumes: true, in: `a: number, b: 2 | 1`},
@@ -254,6 +251,12 @@
146: {subsumes: false, in: ` a: "s \(d)m\(d) e", b: "s a e", d: _`},
147: {subsumes: true, in: ` a: 7080, b: 7080 | int`, mode: subChoose},
+
+ // Defaults
+ 150: {subsumes: false, in: `a: number | *1, b: number | *2`},
+ 151: {subsumes: true, in: `a: number | *2, b: number | *2`},
+ 152: {subsumes: true, in: `a: int | *float, b: int | *2.0`},
+ 154: {subsumes: true, in: `a: number, b: number | *2`},
}
re := regexp.MustCompile(`a: (.*).*b: ([^\n]*)`)
