cue: allow cyclic references in lists
This is done by making lists considerably less efficient,
but that is for later concern. Still better, probably,
than creating a linked list.
Errors are now retained at the value level within lists.
This is okay, as validation descends into list values
as well.
Change-Id: Ifcd35d383f061dab82164d8da36f693dbea64847
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/1900
Reviewed-by: Marcel van Lohuizen <mpvl@google.com>
diff --git a/cue/ast.go b/cue/ast.go
index 5246b30..6d6e8fa 100644
--- a/cue/ast.go
+++ b/cue/ast.go
@@ -421,10 +421,12 @@
}
case *ast.ListLit:
- list := &list{baseValue: newExpr(n)}
- for _, e := range n.Elts {
- list.a = append(list.a, v.walk(e))
+ arcs := []arc{}
+ for i, e := range n.Elts {
+ arcs = append(arcs, arc{feature: label(i), v: v.walk(e)})
}
+ s := &structLit{baseValue: newExpr(n), arcs: arcs}
+ list := &list{baseValue: newExpr(n), elem: s}
list.initLit()
if n.Ellipsis != token.NoPos || n.Type != nil {
list.len = &bound{list.baseValue, opGeq, list.len}
diff --git a/cue/binop.go b/cue/binop.go
index 2cbd9aa..82bb1c9 100644
--- a/cue/binop.go
+++ b/cue/binop.go
@@ -926,22 +926,20 @@
src = mkBin(ctx, src.Pos(), op, x, other)
return ctx.mkErr(src, "incompatible list lengths: %v", n)
}
- var a, rest []value
- var rtyp value
- nx, ny := len(x.a), len(y.a)
- if nx < ny {
- a = make([]value, nx, ny)
- rest = y.a[nx:]
- rtyp = x.typ
-
- } else {
- a = make([]value, ny, nx)
- rest = x.a[ny:]
- rtyp = y.typ
+ sx := x.elem.arcs
+ xa := sx
+ sy := y.elem.arcs
+ ya := sy
+ for len(xa) < len(ya) {
+ xa = append(xa, arc{feature: label(len(xa)), v: x.typ})
}
+ for len(ya) < len(xa) {
+ ya = append(ya, arc{feature: label(len(ya)), v: y.typ})
+ }
+
typ := x.typ
max, ok := n.(*numLit)
- if !ok || len(a)+len(rest) < max.intValue(ctx) {
+ if !ok || len(xa) < max.intValue(ctx) {
typ = unify(ctx, src, x.typ.(evaluated), y.typ.(evaluated))
if isBottom(typ) {
src = mkBin(ctx, src.Pos(), op, x, other)
@@ -949,31 +947,25 @@
}
}
- for i := range a {
- ai := unify(ctx, src, x.at(ctx, i).evalPartial(ctx), y.at(ctx, i).evalPartial(ctx))
- if isBottom(ai) {
- return ai
- }
- a[i] = ai
- }
- for _, n := range rest {
- an := unify(ctx, src, n.evalPartial(ctx), rtyp.(evaluated))
- if isBottom(an) {
- return an
- }
- a = append(a, an)
- }
- return &list{baseValue: binSrc(src.Pos(), op, x, other), a: a, typ: typ, len: n}
+ // TODO: use forwarding instead of this mild hack.
+ x.elem.arcs = xa
+ y.elem.arcs = ya
+ s := unify(ctx, src, x.elem, y.elem).(*structLit)
+ x.elem.arcs = sx
+ y.elem.arcs = sy
+
+ base := binSrc(src.Pos(), op, x, other)
+ return &list{baseValue: base, elem: s, typ: typ, len: n}
case opEql, opNeq:
y, ok := other.(*list)
if !ok {
break
}
- if len(x.a) != len(y.a) {
+ if len(x.elem.arcs) != len(y.elem.arcs) {
return boolTonode(src, false)
}
- for i := range x.a {
+ for i := range x.elem.arcs {
if !test(ctx, src, op, x.at(ctx, i), y.at(ctx, i)) {
return boolTonode(src, false)
}
@@ -986,17 +978,24 @@
break
}
n := &list{baseValue: binSrc(src.Pos(), op, x, other), typ: y.typ}
- n.a = append(x.a, y.a...)
+ arcs := []arc{}
+ for _, v := range x.elem.arcs {
+ arcs = append(arcs, arc{feature: label(len(arcs)), v: v.v})
+ }
+ for _, v := range y.elem.arcs {
+ arcs = append(arcs, arc{feature: label(len(arcs)), v: v.v})
+ }
switch v := y.len.(type) {
case *numLit:
// Closed list
ln := &numLit{numBase: v.numBase}
- ln.v.SetInt64(int64(len(n.a)))
+ ln.v.SetInt64(int64(len(arcs)))
n.len = ln
default:
// Open list
- n.len = y.len
+ n.len = y.len // TODO: add length of x?
}
+ n.elem = &structLit{baseValue: n.baseValue, arcs: arcs}
return n
case opMul:
@@ -1005,7 +1004,8 @@
panic("multiplication must be int type")
}
n := &list{baseValue: binSrc(src.Pos(), op, x, other), typ: x.typ}
- if len(x.a) > 0 {
+ arcs := []arc{}
+ if len(x.elem.arcs) > 0 {
if !k.isGround() {
// should never reach here.
break
@@ -1013,7 +1013,9 @@
if ln := other.(*numLit).intValue(ctx); ln > 0 {
for i := 0; i < ln; i++ {
// TODO: copy values
- n.a = append(n.a, x.a...)
+ for _, a := range x.elem.arcs {
+ arcs = append(arcs, arc{feature: label(len(arcs)), v: a.v})
+ }
}
} else if ln < 0 {
return ctx.mkErr(src, "negative number %d multiplies list", ln)
@@ -1023,12 +1025,13 @@
case *numLit:
// Closed list
ln := &numLit{numBase: v.numBase}
- ln.v.SetInt64(int64(len(n.a)))
+ ln.v.SetInt64(int64(len(arcs)))
n.len = ln
default:
// Open list
- n.len = x.len
+ n.len = x.len // TODO: multiply length?
}
+ n.elem = &structLit{baseValue: n.baseValue, arcs: arcs}
return n
}
return ctx.mkIncompatible(src, op, x, other)
diff --git a/cue/debug.go b/cue/debug.go
index 136379d..718040a 100644
--- a/cue/debug.go
+++ b/cue/debug.go
@@ -363,13 +363,13 @@
case *top, *basicType:
open = true
}
- if !ok || ln > len(x.a) {
+ if !ok || ln > len(x.elem.arcs) {
if !open && !isTop(x.typ) {
p.debugStr(x.len)
write("*[")
p.debugStr(x.typ)
write("]")
- if len(x.a) == 0 {
+ if len(x.elem.arcs) == 0 {
break
}
write("(")
@@ -378,9 +378,9 @@
ellipsis = true
}
write("[")
- for i, a := range x.a {
- p.debugStr(a)
- if i < len(x.a)-1 {
+ for i, a := range x.elem.arcs {
+ p.debugStr(a.v)
+ if i < len(x.elem.arcs)-1 {
write(",")
}
}
diff --git a/cue/eval.go b/cue/eval.go
index b908013..f627cee 100644
--- a/cue/eval.go
+++ b/cue/eval.go
@@ -219,34 +219,24 @@
if err := firstBottom(n, t); err != nil {
return err
}
- a := make([]value, len(x.a))
- changed := false
- for i, v := range x.a {
- // TODO: don't evaluate now. List elements may refer to other list
- // elements. Evaluating them here will cause a cycle evaluating the
- // struct field.
- e := v.evalPartial(ctx)
- changed = changed || e != v
- switch e.(type) {
- case *bottom:
- return e
- case value:
- a[i] = e
- }
- }
- if !changed && n == x.len && t == x.typ {
+ s := x.elem.evalPartial(ctx).(*structLit)
+ if s == x.elem && n == x.len && t == x.typ {
return x
}
- return &list{x.baseValue, a, t, n}
+ return &list{x.baseValue, s, t, n}
}
func (x *listComprehension) evalPartial(ctx *context) evaluated {
- list := &list{baseValue: x.baseValue}
+ s := &structLit{baseValue: x.baseValue}
+ list := &list{baseValue: x.baseValue, elem: s}
result := x.clauses.yield(ctx, func(k, v evaluated, _ bool) *bottom {
if !k.kind().isAnyOf(intKind) {
return ctx.mkErr(k, "key must be of type int")
}
- list.a = append(list.a, v.evalPartial(ctx))
+ list.elem.arcs = append(list.elem.arcs, arc{
+ feature: label(len(list.elem.arcs)),
+ v: v.evalPartial(ctx),
+ })
return nil
})
switch {
diff --git a/cue/export.go b/cue/export.go
index cd4e63c..a61131a 100644
--- a/cue/export.go
+++ b/cue/export.go
@@ -411,8 +411,12 @@
case *list:
list := &ast.ListLit{}
var expr ast.Expr = list
- for _, e := range x.a {
- list.Elts = append(list.Elts, p.expr(e))
+ for _, e := range x.elem.arcs {
+ if doEval(p.mode) {
+ list.Elts = append(list.Elts, p.expr(e.v.evalPartial(p.ctx)))
+ } else {
+ list.Elts = append(list.Elts, p.expr(e.v))
+ }
}
max := maxNum(x.len)
num, ok := max.(*numLit)
@@ -430,7 +434,7 @@
case *top, *basicType:
open = true
}
- if !ok || ln > len(x.a) {
+ if !ok || ln > len(x.elem.arcs) {
list.Type = p.expr(x.typ)
if !open && !isTop(x.typ) {
expr = &ast.BinaryExpr{
diff --git a/cue/go.go b/cue/go.go
index 491571a..c452228 100644
--- a/cue/go.go
+++ b/cue/go.go
@@ -346,13 +346,15 @@
case reflect.Slice, reflect.Array:
list := &list{baseValue: src.base()}
+ arcs := []arc{}
for i := 0; i < value.Len(); i++ {
x := convert(ctx, src, value.Index(i).Interface())
if isBottom(x) {
return x
}
- list.a = append(list.a, x)
+ arcs = append(arcs, arc{feature: label(len(arcs)), v: x})
}
+ list.elem = &structLit{baseValue: list.baseValue, arcs: arcs}
list.initLit()
// There is no need to set the type of the list, as the list will
// be of fixed size and all elements will already have a defined
@@ -522,7 +524,7 @@
if t.Kind() == reflect.Array {
ln = toInt(ctx, baseValue{}, int64(t.Len()))
}
- e = &list{typ: elem, len: ln}
+ e = &list{elem: &structLit{}, typ: elem, len: ln}
}
if k == reflect.Slice {
e = wrapOrNull(e)
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index 7b50370..1e58e59 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -337,7 +337,7 @@
e4: [1, 2, ...>=4 & <=5] & [1, 2, 4, 8]
e5: [1, 2, 4, 8] & [1, 2, ...>=4 & <=5]
`,
- out: `<0>{list: [1,2,3], index: 2, unify: [1,2,3], e: _|_(([] & 4):unsupported op &(list, number)), e2: _|_("d":invalid list index "d" (type string)), e3: _|_(-1:invalid list index -1 (index must be non-negative)), e4: _|_((<=5 & 8):8 not within bound <=5), e5: _|_((<=5 & 8):8 not within bound <=5)}`,
+ out: `<0>{list: [1,2,3], index: 2, unify: [1,2,3], e: _|_(([] & 4):unsupported op &(list, number)), e2: _|_("d":invalid list index "d" (type string)), e3: _|_(-1:invalid list index -1 (index must be non-negative)), e4: [1,2,4,_|_((<=5 & 8):8 not within bound <=5)], e5: [1,2,4,_|_((<=5 & 8):8 not within bound <=5)]}`,
}, {
desc: "list arithmetic",
in: `
@@ -473,7 +473,7 @@
c: [c[1], c[0]]
`,
- out: `<0>{a: _|_(cycle detected), b: _|_(cycle detected), c: _|_(cycle detected)}`,
+ out: `<0>{a: _|_(cycle detected), b: _|_(cycle detected), c: [_|_(cycle detected),_|_(cycle detected)]}`,
}, {
desc: "resolved self-reference cycles",
in: `
@@ -481,13 +481,13 @@
b: a + 100
b: 200
- c: [c[1], a] // TODO: should be allowed
+ c: [c[1], a]
s1: s2 & {a: 1}
s2: s3 & {b: 2}
s3: s1 & {c: 3}
`,
- out: `<0>{a: 100, b: 200, c: _|_(cycle detected), s1: <1>{a: 1, b: 2, c: 3}, s2: <2>{a: 1, b: 2, c: 3}, s3: <3>{a: 1, b: 2, c: 3}}`,
+ out: `<0>{a: 100, b: 200, c: [100,100], s1: <1>{a: 1, b: 2, c: 3}, s2: <2>{a: 1, b: 2, c: 3}, s3: <3>{a: 1, b: 2, c: 3}}`,
}, {
desc: "resolved self-reference cycles: Issue 19",
in: `
@@ -1029,6 +1029,16 @@
`feq0: false, feq1: false, feq2: false, feq3: false, feq4: false, feq5: false, feq6: false, feq7: false, feq8: false, feq9: false, feq10: false, feq11: false, ` +
`fne0: false, fne1: false, fne2: false, fne3: false, fne4: false, fne5: false, fne6: false, fne7: false, fne8: false, fne9: false, fne10: false, fne11: false}`,
}, {
+ desc: "list unification",
+ in: `
+ a: { l: ["foo", v], v: l[1] }
+ b: a & { l: [_, "bar"] }
+ `,
+ out: `<0>{` +
+ `a: <1>{l: ["foo",_|_(cycle detected)], ` +
+ `v: _|_(cycle detected)}, ` +
+ `b: <2>{l: ["foo","bar"], v: "bar"}}`,
+ }, {
desc: "correct error messages",
// Tests that it is okay to partially evaluate structs.
in: `
diff --git a/cue/rewrite.go b/cue/rewrite.go
index fe7faeb..9515d3c 100644
--- a/cue/rewrite.go
+++ b/cue/rewrite.go
@@ -105,18 +105,13 @@
}
func (x *list) rewrite(ctx *context, fn rewriteFunc) value {
- a := make([]value, len(x.a))
- changed := false
- for i, e := range x.a {
- a[i] = rewrite(ctx, e, fn)
- changed = changed || a[i] != e
- }
+ elem := rewrite(ctx, x.elem, fn).(*structLit)
typ := rewrite(ctx, x.typ, fn)
len := rewrite(ctx, x.len, fn)
- if !changed && typ == x.typ && len == x.len {
+ if elem == x.elem && typ == x.typ && len == x.len {
return x
}
- return &list{x.baseValue, a, typ, len}
+ return &list{x.baseValue, elem, typ, len}
}
func (x *sliceExpr) rewrite(ctx *context, fn rewriteFunc) value {
diff --git a/cue/rewrite_test.go b/cue/rewrite_test.go
index 5180509..adf3476 100644
--- a/cue/rewrite_test.go
+++ b/cue/rewrite_test.go
@@ -93,13 +93,10 @@
obj := &structLit{x.baseValue, emit, t, nil, arcs, nil}
return obj
case *list:
- a := make([]value, len(x.a))
- for i := range x.a {
- a[i] = rewriteRec(ctx, x.a[i], x.at(ctx, i), m)
- }
+ elm := rewriteRec(ctx, x.elem, x.elem, m).(*structLit)
len := rewriteRec(ctx, x.len, x.len.(evaluated), m)
typ := rewriteRec(ctx, x.typ, x.typ.(evaluated), m)
- return &list{x.baseValue, a, typ, len}
+ return &list{x.baseValue, elm, typ, len}
default:
return eval
}
diff --git a/cue/subsume.go b/cue/subsume.go
index 29df434..ffd70bf 100644
--- a/cue/subsume.go
+++ b/cue/subsume.go
@@ -239,20 +239,19 @@
if !subsumes(ctx, x.len, y.len, mode) {
return false
}
- n := len(x.a)
- if len(y.a) < n {
- n = len(y.a)
+ if !subsumes(ctx, x.elem, y.elem, mode) {
+ return false
}
- for i, a := range x.a[:n] {
- if !subsumes(ctx, a, y.a[i], 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 i := range y.a[n:] {
- if !subsumes(ctx, x.typ, y.a[i], mode) {
+ for _, a := range y.elem.arcs[n:] {
+ // TODO: evaluate?
+ if !subsumes(ctx, x.typ, a.v, mode) {
return false
}
}
diff --git a/cue/types.go b/cue/types.go
index 5184904..3bf6637 100644
--- a/cue/types.go
+++ b/cue/types.go
@@ -568,7 +568,7 @@
return json.Marshal(x.(*bytesLit).b)
case listKind:
l := x.(*list)
- i := Iterator{ctx: ctx, val: v, iter: l, len: len(l.a)}
+ i := Iterator{ctx: ctx, val: v, iter: l, len: len(l.elem.arcs)}
return marshalList(&i)
case structKind:
obj, _ := v.structVal(ctx)
@@ -730,7 +730,7 @@
return Iterator{ctx: ctx}, err
}
l := v.eval(ctx).(*list)
- return Iterator{ctx: ctx, val: v, iter: l, len: len(l.a)}, nil
+ return Iterator{ctx: ctx, val: v, iter: l, len: len(l.elem.arcs)}, nil
}
// Null reports an error if v is not null.
@@ -1096,7 +1096,7 @@
func isGroundRecursive(ctx *context, v value) error {
switch x := v.(type) {
case *list:
- for i := 0; i < len(x.a); i++ {
+ for i := 0; i < len(x.elem.arcs); i++ {
v := ctx.manifest(x.at(ctx, i))
if err := isGroundRecursive(ctx, v); err != nil {
return err
diff --git a/cue/validate.go b/cue/validate.go
index 7e17216..0379d71 100644
--- a/cue/validate.go
+++ b/cue/validate.go
@@ -29,11 +29,8 @@
}
}
case *list:
- for _, v := range x.a {
- if err := validate(ctx, v); err != nil {
- return err
- }
- }
+ // TODO: also validate types for open lists?
+ return validate(ctx, x.elem)
}
return nil
}
diff --git a/cue/value.go b/cue/value.go
index d1d8cf6..58a7738 100644
--- a/cue/value.go
+++ b/cue/value.go
@@ -438,8 +438,7 @@
type list struct {
baseValue
- // TODO: Elements in a list are nodes to allow for cycle detection.
- a []value // TODO: could be arc?
+ elem *structLit
typ value
@@ -451,7 +450,7 @@
// initLit initializes a literal list.
func (x *list) initLit() {
n := newNum(x, intKind)
- n.v.SetInt64(int64(len(x.a)))
+ n.v.SetInt64(int64(len(x.elem.arcs)))
x.len = n
x.typ = &top{x.baseValue}
}
@@ -481,8 +480,10 @@
v := ctx.mkErr(x, "index %d out of bounds", i)
return arc{cache: v}
}
- if i < len(x.a) {
- return arc{cache: x.a[i].evalPartial(ctx), v: x.a[i]}
+ if i < len(x.elem.arcs) {
+ a := x.elem.iterAt(ctx, i)
+ a.feature = 0
+ return a
}
max := maxNum(x.len.(evaluated))
if max.kind().isGround() {
@@ -504,7 +505,7 @@
// lo and hi must be nil or a ground integer.
func (x *list) slice(ctx *context, lo, hi *numLit) evaluated {
- a := x.a
+ a := x.elem.arcs
max := maxNum(x.len).evalPartial(ctx)
if hi != nil {
n := hi.intValue(ctx)
@@ -535,10 +536,15 @@
if n < len(a) {
a = a[n:]
} else {
- a = []value{}
+ a = []arc{}
}
}
- return &list{baseValue: x.baseValue, a: a, typ: x.typ, len: max}
+ arcs := make([]arc, len(a))
+ for i, a := range a {
+ arcs[i] = arc{feature: label(i), v: a.v}
+ }
+ s := &structLit{baseValue: x.baseValue, arcs: arcs}
+ return &list{baseValue: x.baseValue, elem: s, typ: x.typ, len: max}
}
// An structLit is a single structLit in the configuration tree.
@@ -1205,7 +1211,7 @@
return nil
case *list:
- for i := range src.a {
+ for i := range src.elem.arcs {
idx := newNum(x, intKind)
idx.v.SetInt64(int64(i))
v := fn.call(ctx, x, idx, src.at(ctx, i))
