cue: close lists on operations
Implements spec change.
Not closing lists on operations results in some
unintuitive behavior (albeit correct).
As open lists are disjunctions, they also need to
be manifested.
This does not yet implement cap.
Change-Id: I6558ab0641e4a7c73f1102e320da6ba565e44513
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/1962
Reviewed-by: Marcel van Lohuizen <mpvl@google.com>
diff --git a/cue/evaluator.go b/cue/evaluator.go
index 37b306c..c277a6a 100644
--- a/cue/evaluator.go
+++ b/cue/evaluator.go
@@ -19,12 +19,18 @@
if c.noManifest {
return evaluated
}
+outer:
for {
- x, ok := evaluated.(*disjunction)
- if !ok {
- break
+ switch x := evaluated.(type) {
+ case *disjunction:
+ evaluated = x.manifest(c)
+
+ case *list:
+ return x.manifest(c)
+
+ default:
+ break outer
}
- evaluated = x.manifest(c)
}
return evaluated
}
diff --git a/cue/export_test.go b/cue/export_test.go
index dad7d3a..c4289e6 100644
--- a/cue/export_test.go
+++ b/cue/export_test.go
@@ -91,7 +91,31 @@
b: <=5*[int] & [1, 2, ...]
c: (>=3 & <=5)*[int] & [1, 2, ...]
d: >=2*[int] & [1, 2, ...]
- e: [1, 2, ...int]
+ e: [1, 2]
+ f: [1, 2]
+ }`),
+ }, {
+ raw: true,
+ in: `{
+ a: 5*[int]
+ a: [1, 2, ...]
+ b: <=5*[int]
+ b: [1, 2, ...]
+ c: (>=3 & <=5)*[int]
+ c: [1, 2, ...]
+ d: >=2*[int]
+ d: [1, 2, ...]
+ e: [...int]
+ e: [1, 2, ...]
+ f: [1, 2, ...]
+ }`,
+ out: unindent(`
+ {
+ a: 5*[int] & [1, 2, ...]
+ b: <=5*[int] & [1, 2, ...]
+ c: (>=3 & <=5)*[int] & [1, 2, ...]
+ d: >=2*[int] & [1, 2, ...]
+ e: [...int] & [1, 2, ...]
f: [1, 2, ...]
}`),
}, {
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index 24d2b8c..82e9cf6 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -861,6 +861,9 @@
`e1: _|_(([, ...int] & [, ...float]):incompatible list types: unsupported op &((int)*, (float)*): )` +
`}`,
}, {
+ // TODO: consider removing list arithmetic altogether. It is no longer
+ // needed to indicate the allowed capacity of a list and that didn't
+ // work anyway.
desc: "list arithmetic",
in: `
l0: 3*[1, 2, 3]
@@ -917,9 +920,9 @@
`l3: (<=2 * []), ` +
`l4: (<=2 * [int]), ` +
`l5: (<=2 * (int * [int])), ` +
- `l6: [, ...int], ` +
- `l7: [1,1,1, ...int], ` +
- `l8: [1,2,1,2,1,2, ...int], ` +
+ `l6: [], ` +
+ `l7: [1,1,1], ` +
+ `l8: [1,2,1,2,1,2], ` +
`s0: [], ` +
`s1: [1], ` +
@@ -930,15 +933,15 @@
`s6: [1,1,2], ` +
`s7: [1,2,1], ` +
`s8: [1,2,1,2], ` +
- `s9: [, ...], ` +
- `s10: [1, ...], ` +
- `s11: [2, ...], ` +
- `s12: [1,2, ...], ` +
- `s13: [1,2, ...], ` +
- `s14: [1,2, ...], ` +
- `s15: [1,1,2, ...], ` +
- `s16: [1,2,1, ...], ` +
- `s17: [1,2,1,2, ...], ` +
+ `s9: [], ` +
+ `s10: [1], ` +
+ `s11: [2], ` +
+ `s12: [1,2], ` +
+ `s13: [1,2], ` +
+ `s14: [1,2], ` +
+ `s15: [1,1,2], ` +
+ `s16: [1,2,1], ` +
+ `s17: [1,2,1,2], ` +
`s18: [], ` +
`s19: [1], ` +
@@ -949,15 +952,15 @@
`s24: [1,1,2], ` +
`s25: [1,2,1], ` +
`s26: [1,2,1,2], ` +
- `s27: [, ...], ` +
- `s28: [1, ...], ` +
- `s29: [2, ...], ` +
- `s30: [1,2, ...], ` +
- `s31: [1,2, ...], ` +
- `s32: [1,2, ...], ` +
- `s33: [1,1,2, ...], ` +
- `s34: [1,2,1, ...], ` +
- `s35: [1,2,1,2, ...]` +
+ `s27: [], ` +
+ `s28: [1], ` +
+ `s29: [2], ` +
+ `s30: [1,2], ` +
+ `s31: [1,2], ` +
+ `s32: [1,2], ` +
+ `s33: [1,1,2], ` +
+ `s34: [1,2,1], ` +
+ `s35: [1,2,1,2]` +
`}`,
}, {
diff --git a/cue/subsume.go b/cue/subsume.go
index ffd70bf..860d630 100644
--- a/cue/subsume.go
+++ b/cue/subsume.go
@@ -239,22 +239,21 @@
if !subsumes(ctx, x.len, y.len, mode) {
return false
}
+ // TODO: need to handle case where len(x.elem) > len(y.elem) explicitly
+ // if we introduce cap().
if !subsumes(ctx, x.elem, y.elem, mode) {
return false
}
- n := len(x.elem.arcs)
- if len(y.elem.arcs) < n {
- n = len(y.elem.arcs)
- }
- if y.isOpen() {
- return subsumes(ctx, x.typ, y.typ, 0)
- }
- for _, a := range y.elem.arcs[n:] {
- // TODO: evaluate?
+ // TODO: assuming continuous indices, use merge sort if we allow
+ // sparse arrays.
+ for _, a := range y.elem.arcs[len(x.elem.arcs):] {
if !subsumes(ctx, x.typ, a.v, mode) {
return false
}
}
+ if y.isOpen() { // implies from first check that x.IsOpen.
+ return subsumes(ctx, x.typ, y.typ, 0)
+ }
return true
}
return isBottom(v)
diff --git a/cue/subsume_test.go b/cue/subsume_test.go
index 70aeaee..e5f3f8c 100644
--- a/cue/subsume_test.go
+++ b/cue/subsume_test.go
@@ -122,16 +122,6 @@
54: {subsumes: true, in: `a: int, b: int`},
55: {subsumes: true, in: `a: number, b: int`},
- // Lists
- 56: {subsumes: true, in: `a: [], b: [] `},
- 57: {subsumes: true, in: `a: [1], b: [1] `},
- 58: {subsumes: false, in: `a: [1], b: [2] `},
- 59: {subsumes: false, in: `a: [1], b: [2, 3] `},
- 60: {subsumes: true, in: `a: [{b: string}], b: [{b: "foo"}] `},
- 61: {subsumes: true, in: `a: [...{b: string}], b: [{b: "foo"}] `},
- 62: {subsumes: false, in: `a: [{b: "foo"}], b: [{b: string}] `},
- 63: {subsumes: false, in: `a: [{b: string}], b: [{b: "foo"}, ...{b: "foo"}] `},
-
// Structs
64: {subsumes: true, in: `a: {}, b: {}`},
65: {subsumes: true, in: `a: {}, b: {a: 1}`},
@@ -370,6 +360,17 @@
// The one exception of the rule: there is no value of foo that can be
// added to b which would cause the unification of a and b to fail.
420: {subsumes: true, in: `a: {foo?: _}, b: {}`},
+
+ // Lists
+ 506: {subsumes: true, in: `a: [], b: [] `},
+ 507: {subsumes: true, in: `a: [1], b: [1] `},
+ 508: {subsumes: false, in: `a: [1], b: [2] `},
+ 509: {subsumes: false, in: `a: [1], b: [2, 3] `},
+ 510: {subsumes: true, in: `a: [{b: string}], b: [{b: "foo"}] `},
+ 511: {subsumes: true, in: `a: [...{b: string}], b: [{b: "foo"}] `},
+ 512: {subsumes: false, in: `a: [{b: "foo"}], b: [{b: string}] `},
+ 513: {subsumes: false, in: `a: [{b: string}], b: [{b: "foo"}, ...{b: "foo"}] `},
+ 520: {subsumes: false, in: `a: [_, int, ...], b: [int, string, ...string] `},
}
re := regexp.MustCompile(`a: (.*).*b: ([^\n]*)`)
diff --git a/cue/value.go b/cue/value.go
index 58a7738..c28e461 100644
--- a/cue/value.go
+++ b/cue/value.go
@@ -455,10 +455,31 @@
x.typ = &top{x.baseValue}
}
+func (x *list) manifest(ctx *context) evaluated {
+ if x.kind().isGround() {
+ return x
+ }
+ // A list is ground if its length is ground, or if the current length
+ // meets matches the cap.
+ n := newNum(x, intKind)
+ n.v.SetInt64(int64(len(x.elem.arcs)))
+ if n := binOp(ctx, x, opUnify, n, x.len.evalPartial(ctx)); !isBottom(n) {
+ return &list{
+ baseValue: x.baseValue,
+ elem: x.elem,
+ len: n,
+ typ: &top{x.baseValue},
+ }
+ }
+ return x
+}
+
func (x *list) kind() kind {
- // Any open list has a default manifestation and can thus always be
- // interpreted as ground (ignoring non-ground elements).
- return listKind
+ k := listKind
+ if _, ok := x.len.(*numLit); ok {
+ return k
+ }
+ return k | nonGround
}
// at returns the evaluated and original value of position i. List x must
