cue: implementation of reference cycle handling
Supported:
- delayed constraints for scalare expressions
- field-level cycles, including disjunctions
Not yet supported:
- reference cycles in lists
- structural cycles
Change-Id: I3300193181b24bbb77447dc7648f9bd81b351f48
diff --git a/cue/binop.go b/cue/binop.go
index dec382e..a637f56 100644
--- a/cue/binop.go
+++ b/cue/binop.go
@@ -36,8 +36,19 @@
}
func binOp(ctx *context, src source, op op, left, right evaluated) (result evaluated) {
- if err := firstBottom(left, right); err != nil {
- return err
+ if isBottom(left) {
+ if op == opUnify && ctx.exprDepth == 0 && cycleError(left) != nil {
+ ctx.cycleErr = true
+ return right
+ }
+ return left
+ }
+ if isBottom(right) {
+ if op == opUnify && ctx.exprDepth == 0 && cycleError(right) != nil {
+ ctx.cycleErr = true
+ return left
+ }
+ return right
}
leftKind := left.kind()
@@ -53,7 +64,9 @@
left, right = right, left
}
if op != opUnify {
+ ctx.exprDepth++
v := left.binOp(ctx, src, op, right) // may return incomplete
+ ctx.exprDepth--
return v
}
diff --git a/cue/context.go b/cue/context.go
index 99a1e1c..961b3b4 100644
--- a/cue/context.go
+++ b/cue/context.go
@@ -30,6 +30,9 @@
// constraints are to be evaluated at the end values to be evaluated later.
constraints []value
noDelay bool
+ exprDepth int // nesting of expression that are not unification
+ evalDepth int
+ cycleErr bool
// for debug strings
nodeRefs map[scope]string
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index aab3081..f44da59 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -16,7 +16,6 @@
import (
"flag"
- "fmt"
"testing"
"cuelang.org/go/cue/errors"
@@ -70,9 +69,6 @@
root := testResolve(ctx, obj, r)
got := debugStr(ctx, root)
- if v := ctx.processDelayedConstraints(); v != nil {
- got += fmt.Sprintf("\n%s", debugStr(ctx, v))
- }
// Copy the result
if got != tc.out {
@@ -353,29 +349,31 @@
c: [c[1], c[0]]
`,
out: `<0>{a: _|_(cycle detected), b: _|_(cycle detected), c: _|_(cycle detected)}`,
- // }, {
- // desc: "resolved self-reference cycles",
- // in: `
- // a: b - 100
- // b: a + 100
- // b: 200
+ }, {
+ desc: "resolved self-reference cycles",
+ in: `
+ a: b - 100
+ b: a + 100
+ b: 200
- // c: [c[1], a] // TODO: should be allowed
+ c: [c[1], a] // TODO: should be allowed
- // s1: s2 & {a: 1}
- // s2: s3 & {b: 2}
- // s3: s1 & {c: 3}
- // `,
- // out: `<0>{a: 100, b: 200, c: _|_(cycle detected)}`,
+ 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}}`,
}, {
desc: "delayed constraint failure",
in: `
a: b - 100
b: a + 110
b: 200
+
+ x: 100
+ x: x + 1
`,
- out: `<0>{a: 100, b: 200}
-_|_(((<1>.a + 110) & 200):constraint violated: _|_((210 & 200):cannot unify numbers 210 and 200))`,
+ out: `<0>{a: _|_(((<1>.a + 110) & 200):constraint violated: _|_((210 & 200):cannot unify numbers 210 and 200)), b: 200, x: _|_((100 & (<1>.x + 1)):constraint violated: _|_((100 & 101):cannot unify numbers 100 and 101))}`,
// TODO: find a way to mark error in data.
}}
rewriteHelper(t, testCases, evalPartial)
@@ -800,26 +798,24 @@
`,
out: `<0>{obj: <1>{<>: <2>(Name: string)-><3>{a: ("dummy" | string) if true yield ("sub"): <4>{as: <3>.a}}, ` +
`foo: <5>{a: "bar", sub: <6>{as: "bar"}}}}`,
- // TODO(P3): if two fields are evaluating to the same field, their
- // values could be bound.
- // nodes: use a shared node
- // other: change to where clause
- // unknown: change to where clause.
- // in: `
- // a: b
- // b: a
- // a: { d: 1 }
- // `,
- // out: `<0>{a: {d:1}, b: {d:1}}`,
-
- // TODO(P2): circular references in expressions can be resolved when
- // unified with complete values.
- // in: `
- // a: 20
- // a: b + 10 // 20 & b+10 ==> 20; where a == b+10
- // b: a - 10 // 10-10 = 10 ==> 20 == 10+10
- // `
- // out: `<0>{a_0:20, b_1:10}`
+ }, {
+ desc: "self-reference cycles conflicts with strings",
+ in: `
+ a: {
+ x: y+"?"
+ y: x+"!"
+ }
+ a x: "hey"
+ `,
+ out: `<1>{a: <2>{x: _|_(((<0>.y + "?") & "hey"):constraint violated: _|_("hey":delayed constraint ((<0>.y + "?") & "hey") violated)), y: _|_(cycle detected)}}`,
+ }, {
+ desc: "resolved self-reference cycles with disjunctions",
+ in: `
+ a: b&{x:1} | {y:1} // {x:1,y:3,z:2} | {y:1}
+ b: {x:2} | c&{z:2} // {x:2} | {x:1,y:3,z:2}
+ c: a&{y:3} | {z:3} // {x:1,y:3,z:2} | {z:3}
+ `,
+ out: `<0>{a: (<1>{x: 1, y: 3, z: 2} | <2>{y: 1}), b: (<3>{x: 2} | <4>{x: 1, y: 3, z: 2}), c: (<5>{x: 1, y: 3, z: 2} | <6>{z: 3})}`,
}}
rewriteHelper(t, testCases, evalPartial)
}
diff --git a/cue/value.go b/cue/value.go
index 4397b74..3be1282 100644
--- a/cue/value.go
+++ b/cue/value.go
@@ -601,86 +601,6 @@
return v, x.arcs[i].v, x.arcs[i].feature // TODO: return template & v for original?
}
-// Cycle Handling
-//
-// Structs (and thus lists)
-//
-// Unresolved cycle
-// a: b // _|_
-// b: a // _|_
-//
-// a: b | {c:1} // _|_
-// b: a | {d:1} // _|_
-//
-// Resolved cycles
-// a: b // {c:1} : b -> a&{c:1} ->a&{c:1}[a:cycle error] -> {c:1}
-// b: a & { c: 1 } // {c:1}
-//
-// a: b & { d: 1 } // {c:1, d:1}
-// b: a & { c: 1 } // {c:1, d:1}
-//
-// To resolve cycles in disjunctions, the unification operations need to be
-// rewritten before that disjunction values are unified. This is optional for
-// CUE implementations.
-// a: b | {d:1} // {c:1} | {d:1}
-// b: a & {c:1} // b & {c:1} | {d:1}&{c:1} -> {c:1} | {c:1,d:1}
-//
-//
-// Atoms
-// a: b + 100 // _|_
-// b: a - 100 // _|_
-//
-// a: b + 100 // 200
-// b: a - 100 // 100 + check 100 & (a-100)
-// b: 100
-//
-// a: b+100 | b+50 // 200 | 150
-// b: a-100 | a-50 // 100 + check 100 & (a-100 | a-50)
-// b: 100
-
-// TODO: Question: defining an interpration of a constraint structure with no
-// default resolution applied versus one there is. And given a substitution that
-// is valid for both interpretation, resulting in a an b, respectively. Is there
-// any expression in which a an b can be substituted for which the fully
-// evaluated interpretation can yield different results? If so, can we define
-// disjunction in a way that it does not?
-// ANSWER: NO. But is it sufficient to only require this for direct references?
-// Maybe, but at least it holds in that case.
-// f1: a1 | ... | an
-// f2: f1
-// f2: b1 | ... | bm | ... | bn
-// -- Suppose the element that unifies with a1 in f2 is bm.
-// Is a1 & bm the same answer if f2 referencing f1 referred to the
-// disjunction?
-// Assume that some ax, x > 1 unifies with a by, y < m.
-// This would be an ambiguous disjunction, and by definition invalid.
-// The first valid disjunction is one where bm is the first to match
-// any of the values in f1. The result will therefore be the same.
-//
-// Case 1
-// replicas: 1 | int
-//
-// foo: 1 | 2 // interpretations must be equal or else the value crosses
-// foo: replicas
-//
-// Case 2
-// a: {
-// replicas: 1 | int
-// b: {chk: 0, num: 4 } | { chk: int, e: 5, f: int } | { chk: 1, e: 6, f: 7 }
-// b chk: replicas // { chk: 1, num: 5 }
-// c: 1/(replicas-1) | 0 // 0
-// }
-//
-// b: {
-// b chk f: 7
-// }
-//
-// This may be an issue, but by defining all expressions to be lazily evaluated,
-// this is not a surprise. We could have a cue.Choose() builtin to pick
-// the disjunctions recursively. Note that within a single struct, though, the
-// selection for a field is always unique. It may only vary if a substructure
-// is referred to in a new substructure.
-
func (x *structLit) at(ctx *context, i int) evaluated {
x.expand(ctx)
// if x.emit != nil && isBottom(x.emit) {
@@ -693,15 +613,31 @@
// cycle detection
x.arcs[i].cache = cycleSentinel
- v := x.arcs[i].v.evalPartial(ctx)
- if err := cycleError(v); err != nil {
- x.arcs[i].cache = nil
- return err
- }
+ ctx.evalDepth++
+ v := x.arcs[i].v.evalPartial(ctx)
+ ctx.evalDepth--
v = x.applyTemplate(ctx, i, v)
+
+ if ctx.evalDepth > 0 && ctx.cycleErr {
+ // Don't cache while we're in a evaluation cycle as it will cache
+ // partial results. Each field involved in the cycle will have to
+ // reevaluated the values from scratch. As the result will be
+ // cached after one cycle, it will evaluate the cycle at most twice.
+ x.arcs[i].cache = nil
+ return v
+ }
+ // If there as a cycle error, we have by now evaluated full cycle and
+ // it is safe to cache the result.
+ ctx.cycleErr = false
+
x.arcs[i].cache = v
+ if ctx.evalDepth == 0 {
+ if err := ctx.processDelayedConstraints(); err != nil {
+ x.arcs[i].cache = err
+ }
+ }
}
return x.arcs[i].cache
}
@@ -1056,7 +992,12 @@
k := 0
outer:
for i, v := range x.values {
- if isBottom(v.val) {
+ // TODO: this is pre-evaluation is quite aggressive. Verify whether
+ // this does not trigger structural cycles. If so, this can check for
+ // bottom and the validation can be delayed to as late as picking
+ // defaults. The drawback of this approach is that printed intermediate
+ // results will not look great.
+ if err := validate(ctx, v.val); err != nil {
continue
}
for j, w := range x.values {
