cue: fix reentrancy issue
even though this is not something we want to support
Change-Id: I84e986d4b8276d6258679ebc37625565f5fb5c25
diff --git a/cue/binop.go b/cue/binop.go
index a637f56..682dd89 100644
--- a/cue/binop.go
+++ b/cue/binop.go
@@ -450,7 +450,7 @@
return x
}
arcs := make(arcs, 0, len(x.arcs)+len(y.arcs))
- obj := &structLit{binSrc(src.Pos(), op, x, other), x.emit, nil, nil, arcs}
+ obj := &structLit{binSrc(src.Pos(), op, x, other), x.emit, nil, nil, arcs, nil}
defer ctx.pushForwards(x, obj, y, obj).popForwards()
tx, ex := evalLambda(ctx, x.template)
diff --git a/cue/copy.go b/cue/copy.go
index 39ef674..880c769 100644
--- a/cue/copy.go
+++ b/cue/copy.go
@@ -31,7 +31,7 @@
case *structLit:
arcs := make(arcs, len(x.arcs))
- obj := &structLit{x.baseValue, nil, nil, nil, arcs}
+ obj := &structLit{x.baseValue, nil, nil, nil, arcs, nil}
defer ctx.pushForwards(x, obj).popForwards()
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index f44da59..6c9032c 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -807,7 +807,7 @@
}
a x: "hey"
`,
- out: `<1>{a: <2>{x: _|_(((<0>.y + "?") & "hey"):constraint violated: _|_("hey":delayed constraint ((<0>.y + "?") & "hey") violated)), y: _|_(cycle detected)}}`,
+ out: `<0>{a: <1>{x: _|_(((<2>.y + "?") & "hey"):constraint violated: _|_(("hey!?" & "hey"):failed to unify: hey!? != hey)), y: "hey!"}}`,
}, {
desc: "resolved self-reference cycles with disjunctions",
in: `
@@ -1087,6 +1087,43 @@
`,
out: `<0>{res: [<1>{<>: <2>(X: string)-><3>{a: (<3>.c + <3>.b.str), c: "X", b: <4>{str: string}}, x: <5>{a: "XDDDD", c: "X", b: <6>{str: "DDDD"}}}], ` +
`t: <7>{<>: <2>(X: string)-><3>{a: (<3>.c + <3>.b.str), c: "X", b: <4>{str: string}}, x: <8>{a: "XDDDD", c: "X", b: <9>{str: "DDDD"}}}}`,
+ }, {
+ // TODO: A nice property for CUE to have would be that evaluation time
+ // is proportional to the number of output nodes (note that this is
+ // not the same as saying that the running time is O(n)).
+ // We should probably disallow shenanigans like the one below. But until
+ // this is allowed, it should at least be correct. At least we are not
+ // making reentrant coding easy.
+ desc: "reentrance",
+ in: `
+ // This indirection is needed to avoid binding references to fib
+ // within fib to the instantiated version.
+ fibRec: {nn: int, out: (fib & {n: nn}).out}
+ fib: {
+ n: int
+
+ out: (fibRec & {nn: n - 2}).out + (fibRec & {nn: n - 1}).out if n >= 2
+ out: n if n < 2
+ }
+ fib2: (fib & {n: 2}).out
+ fib7: (fib & {n: 7}).out
+ fib12: (fib & {n: 12}).out
+ `,
+ out: `<0>{fibRec: <1>{nn: int, out: _|_((<2>.fib & <3>{n: <4>.nn}).out:undefined field "out")}, fib: <5>{n: int}, ` +
+ `fib2: 1, ` +
+ `fib7: 13, ` +
+ `fib12: 144}`,
+ }}
+ rewriteHelper(t, testCases, evalFull)
+}
+
+func TestX(t *testing.T) {
+ t.Skip()
+
+ // Don't remove. For debugging.
+ testCases := []testCase{{
+ in: `
+ `,
}}
rewriteHelper(t, testCases, evalFull)
}
diff --git a/cue/rewrite_test.go b/cue/rewrite_test.go
index a6db968..19e8d8b 100644
--- a/cue/rewrite_test.go
+++ b/cue/rewrite_test.go
@@ -74,7 +74,7 @@
}
x = e.(*structLit)
}
- x.expand(ctx)
+ x = x.expandFields(ctx)
arcs := make(arcs, len(x.arcs))
for i, a := range x.arcs {
v := x.at(ctx, i)
@@ -89,7 +89,7 @@
t = v
}
emit := testResolve(ctx, x.emit, m)
- obj := &structLit{x.baseValue, emit, t, nil, arcs}
+ obj := &structLit{x.baseValue, emit, t, nil, arcs, nil}
return obj
case *list:
a := make([]value, len(x.a))
diff --git a/cue/strip.go b/cue/strip.go
index 3822ab2..aaf585a 100644
--- a/cue/strip.go
+++ b/cue/strip.go
@@ -30,7 +30,7 @@
eval := ctx.manifest(v)
switch x := eval.(type) {
case *structLit:
- x.expand(ctx)
+ x = x.expandFields(ctx)
if x.template != nil {
arcs := make(arcs, len(x.arcs))
for i, a := range x.arcs {
@@ -38,7 +38,7 @@
arcs[i] = arc{a.feature, v, nil}
}
// TODO: verify that len(x.comprehensions) == 0
- return &structLit{x.baseValue, x.emit, nil, nil, arcs}, false
+ return &structLit{x.baseValue, x.emit, nil, nil, arcs, nil}, false
}
}
return eval, true
diff --git a/cue/types.go b/cue/types.go
index 42a3a54..8f669e3 100644
--- a/cue/types.go
+++ b/cue/types.go
@@ -794,7 +794,8 @@
}
obj := v.eval(ctx).(*structLit)
- obj.expand(ctx) // expand comprehensions
+ // TODO: This is expansion appropriate?
+ obj = obj.expandFields(ctx) // expand comprehensions
// check if any labels are hidden
f := label(0)
@@ -818,6 +819,7 @@
obj.template,
nil,
arcs,
+ nil,
}
}
@@ -829,7 +831,7 @@
return structValue{}, err
}
obj := v.eval(ctx).(*structLit)
- obj.expand(ctx)
+ obj = obj.expandFields(ctx)
return structValue{ctx, v.path, obj}, nil
}
diff --git a/cue/validate.go b/cue/validate.go
index 336f411..7e17216 100644
--- a/cue/validate.go
+++ b/cue/validate.go
@@ -22,7 +22,7 @@
}
switch x := eval.(type) {
case *structLit:
- x.expand(ctx)
+ x = x.expandFields(ctx)
for i := range x.arcs {
if err := validate(ctx, x.at(ctx, i)); err != nil {
return err
diff --git a/cue/value.go b/cue/value.go
index 3be1282..b458284 100644
--- a/cue/value.go
+++ b/cue/value.go
@@ -563,7 +563,8 @@
comprehensions []*fieldComprehension
// TODO: consider hoisting the template arc to its own value.
- arcs []arc
+ arcs []arc
+ expanded *structLit
}
func newStruct(src source) *structLit {
@@ -580,7 +581,7 @@
// lookup returns the node for the given label f, if present, or nil otherwise.
func (x *structLit) lookup(ctx *context, f label) (v evaluated, raw value) {
- x.expand(ctx)
+ x = x.expandFields(ctx)
// Lookup is done by selector or index references. Either this is done on
// literal nodes or nodes obtained from references. In the later case,
// noderef will have ensured that the ancestors were evaluated.
@@ -593,7 +594,7 @@
}
func (x *structLit) iterAt(ctx *context, i int) (evaluated, value, label) {
- x.expand(ctx)
+ x = x.expandFields(ctx)
if i >= len(x.arcs) {
return nil, nil, 0
}
@@ -602,7 +603,7 @@
}
func (x *structLit) at(ctx *context, i int) evaluated {
- x.expand(ctx)
+ x = x.expandFields(ctx)
// if x.emit != nil && isBottom(x.emit) {
// return x.emit.(evaluated)
// }
@@ -642,15 +643,22 @@
return x.arcs[i].cache
}
-func (x *structLit) expand(ctx *context) {
+func (x *structLit) expandFields(ctx *context) *structLit {
+ if x.expanded != nil {
+ return x.expanded
+ }
if x.comprehensions == nil {
- return
+ x.expanded = x
+ return x
}
- comprehensions := x.comprehensions
- x.comprehensions = nil
+ x.expanded = x
+ comprehensions := x.comprehensions
+ emit := x.emit
+ template := x.template
newArcs := []arc{}
+
for _, c := range comprehensions {
result := c.clauses.yield(ctx, func(k, v evaluated) *bottom {
if !k.kind().isAnyOf(stringKind) {
@@ -658,10 +666,10 @@
}
if c.isTemplate {
// TODO: disallow altogether or only when it refers to fields.
- if x.template == nil {
- x.template = v
+ if template == nil {
+ template = v
} else {
- x.template = mkBin(ctx, c.Pos(), opUnify, x.template, v)
+ template = mkBin(ctx, c.Pos(), opUnify, template, v)
}
return nil
}
@@ -679,7 +687,7 @@
switch {
case result == nil:
case isBottom(result):
- x.emit = result
+ emit = result
default:
panic("should not happen")
}
@@ -688,6 +696,11 @@
// new arcs may be merged with old ones, but only if the old ones were not
// referred to in the evaluation of any of the arcs.
// TODO(perf): improve big O
+ arcs := make([]arc, 0, len(x.arcs)+len(newArcs))
+ arcs = append(arcs, x.arcs...)
+ x = &structLit{x.baseValue, emit, template, nil, arcs, nil}
+ x.expanded = x
+
outer:
for _, na := range newArcs {
f := na.feature
@@ -705,6 +718,7 @@
x.arcs = append(x.arcs, arc{feature: f, v: na.v})
}
sort.Stable(x)
+ return x
}
func (x *structLit) applyTemplate(ctx *context, i int, v evaluated) evaluated {
@@ -1130,7 +1144,7 @@
switch src := source.(type) {
case *structLit:
- src.expand(ctx)
+ src = src.expandFields(ctx)
for i, a := range src.arcs {
key := &stringLit{
x.baseValue,
diff --git a/doc/ref/spec.md b/doc/ref/spec.md
index 2d30c51..7e0691c 100644
--- a/doc/ref/spec.md
+++ b/doc/ref/spec.md
@@ -2073,6 +2073,23 @@
```
<!--
+Consider banning any construct that makes CUE not having a linear
+running time expressed in the number of nodes in the output.
+
+This would require restricting constructs like:
+
+(fib&{n:2}).out
+
+fib: {
+ n: int
+
+ out: (fib&{n:n-2}).out + (fib&{n:n-1}).out if n >= 2
+ out: fib({n:n-2}).out + fib({n:n-1}).out if n >= 2
+ out: n if n < 2
+}
+
+-->
+<!--
### Unused fields
TODO: rules for detection of unused fields
@@ -2081,7 +2098,6 @@
-->
-
## Modules, instances, and packages
CUE configurations are constructed combining _instances_.
