cue: simplify cycle handlng for expressions
Errors need not mention that a constraint was delayed,
as this is an implementation detail.
Add tests for handling expression cycles in disjunctions.
This is now disallowed.
Change-Id: Ib8492b5a81b44448528f779249b48e779de26bb2
Reviewed-on: https://cue-review.googlesource.com/c/1528
Reviewed-by: Marcel van Lohuizen <mpvl@google.com>
diff --git a/cue/context.go b/cue/context.go
index 961b3b4..7bfaae5 100644
--- a/cue/context.go
+++ b/cue/context.go
@@ -28,10 +28,10 @@
oldSize []int
// constraints are to be evaluated at the end values to be evaluated later.
- constraints []value
- noDelay bool
+ constraints []*binaryExpr
exprDepth int // nesting of expression that are not unification
evalDepth int
+ inSum int
cycleErr bool
// for debug strings
@@ -60,10 +60,8 @@
// delayConstraint schedules constraint to be evaluated and returns ret. If
// delaying constraints is currently not allowed, it returns an error instead.
-func (c *context) delayConstraint(ret evaluated, constraint value) evaluated {
- if c.noDelay {
- return c.mkErr(ret, "delayed constraint %v violated", debugStr(c, constraint))
- }
+func (c *context) delayConstraint(ret evaluated, constraint *binaryExpr) evaluated {
+ c.cycleErr = true
c.constraints = append(c.constraints, constraint)
return ret
}
@@ -72,11 +70,9 @@
cons := c.constraints
c.constraints = c.constraints[:0]
for _, dc := range cons {
- c.noDelay = true
- v := c.manifest(dc)
- c.noDelay = false
+ v := binOp(c, dc, dc.op, dc.left.evalPartial(c), dc.right.evalPartial(c))
if isBottom(v) {
- return c.mkErr(dc, "constraint violated: %v", debugStr(c, v))
+ return v
}
}
return nil
diff --git a/cue/eval.go b/cue/eval.go
index 8832ffc..d7ee66a 100644
--- a/cue/eval.go
+++ b/cue/eval.go
@@ -288,6 +288,7 @@
defer func() { ctx.debugPrint("result:", result) }()
}
+ ctx.inSum++
dn := &disjunction{x.baseValue, make([]dValue, 0, len(x.values))}
changed := false
for _, v := range x.values {
@@ -307,6 +308,7 @@
if !changed {
dn = x
}
+ ctx.inSum--
return dn.normalize(ctx, x).val
}
@@ -322,7 +324,7 @@
case d.marked:
if marked != nil {
// TODO: allow disjunctions to be returned as is.
- return ctx.mkErr(x, "more than one default remaining (%v and %v)", debugStr(ctx, marked), debugStr(ctx, d.val))
+ return ctx.mkErr(x, codeIncomplete, "more than one default remaining (%v and %v)", debugStr(ctx, marked), debugStr(ctx, d.val))
}
marked = d.val.(evaluated)
case unmarked1 == nil:
@@ -336,7 +338,7 @@
return marked
case unmarked2 != nil:
- return ctx.mkErr(x, "more than one element remaining (%v and %v)",
+ return ctx.mkErr(x, codeIncomplete, "more than one element remaining (%v and %v)",
debugStr(ctx, unmarked1), debugStr(ctx, unmarked2))
case unmarked1 != nil:
@@ -358,8 +360,10 @@
var left, right evaluated
if x.op != opUnify {
+ ctx.exprDepth++
left = ctx.manifest(x.left)
right = ctx.manifest(x.right)
+ ctx.exprDepth--
// TODO: allow comparing to a literal bottom only. Find something more
// principled perhaps. One should especially take care that two values
@@ -379,13 +383,11 @@
left = x.left.evalPartial(ctx)
right = x.right.evalPartial(ctx)
- if err := cycleError(left); err != nil && right.kind().isAtom() {
- return ctx.delayConstraint(right,
- mkBin(ctx, x.Pos(), opUnify, x.left, right))
+ if err := cycleError(left); err != nil && ctx.inSum == 0 && right.kind().isAtom() {
+ return ctx.delayConstraint(right, x)
}
- if err := cycleError(right); err != nil && left.kind().isAtom() {
- return ctx.delayConstraint(left,
- mkBin(ctx, x.Pos(), opUnify, left, x.right))
+ if err := cycleError(right); err != nil && ctx.inSum == 0 && left.kind().isAtom() {
+ return ctx.delayConstraint(left, x)
}
// check if it is a cycle that can be unwrapped.
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index 3cce0cc..7b5a09d 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -468,7 +468,10 @@
x: 100
x: x + 1
`,
- 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))}`,
+ out: `<0>{` +
+ `a: _|_((210 & 200):cannot unify numbers 210 and 200), ` +
+ `b: _|_((210 & 200):cannot unify numbers 210 and 200), ` +
+ `x: _|_((100 & 101):cannot unify numbers 100 and 101)}`,
// TODO: find a way to mark error in data.
}}
rewriteHelper(t, testCases, evalPartial)
@@ -1059,7 +1062,7 @@
}
a x: "hey"
`,
- out: `<0>{a: <1>{x: _|_(((<2>.y + "?") & "hey"):constraint violated: _|_(("hey!?" & "hey"):failed to unify: hey!? != hey)), y: "hey!"}}`,
+ out: `<0>{a: <1>{x: _|_(("hey!?" & "hey"):failed to unify: hey!? != hey), y: "hey!"}}`,
}, {
desc: "resolved self-reference cycles with disjunctions",
in: `
@@ -1068,6 +1071,187 @@
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})}`,
+ }, {
+ // We take a very conservative stance on delaying arithmetic
+ // expressions within disjunctions. It should remain resolvable, though,
+ // once the user specifies one.
+ desc: "resolved self-reference cycles with disjunction",
+ in: `
+ // The disjunction in xa could be resolved, but as disjunctions
+ // are not resolved for expression, it remains unresolved.
+ xa1: (xa2 & 8) | (xa4 & 9)
+ xa2: xa3 + 2
+ xa3: 6 & xa1-2
+ xa4: xa2 + 2
+
+ // As xb3 is a disjunction, xb2 cannot be resolved and evaluating
+ // the cycle completely is broken. However, it is not an error
+ // as the user might still resolve the disjunction.
+ xb1: (xb2 & 8) | (xb4 & 9)
+ xb2: xb3 + 2
+ xb3: (6 & (xb1-2)) | (xb4 & 9)
+ xb4: xb2 + 2
+
+ // Another variant with more disjunctions. xc1 remains with two
+ // possibilities. Technically, only the first value is valid.
+ // However, to fully determine that, all options of the remaining
+ // disjunction will have to be evaluated algebraically, which is
+ // not done.
+ xc1: xc2 & 8 | xc4 & 9 | xc5 & 9
+ xc2: xc3 + 2
+ xc3: 6 & xc1-2
+ xc4: xc2 + 1
+ xc5: xc2 + 2
+
+ // The above is resolved by setting xd1 explicitly.
+ xd1: xd2 & 8 | xd4 & 9 | xd5 & 9
+ xd2: xd3 + 2
+ xd3: 6 & xd1-2
+ xd4: xd2 + 1
+ xd5: xd2 + 2
+ xd1: 8
+
+ // The above is resolved by setting xd1 explicitly to the wrong
+ // value, resulting in an error.
+ xe1: xe2 & 8 | xe4 & 9 | xe5 & 9
+ xe2: xe3 + 2
+ xe3: 6 & xe1-2
+ xe4: xe2 + 1
+ xe5: xe2 + 2
+ xe1: 9
+
+ // TODO: this is resolvable, but requires some detection logic
+ // in disjunctions.
+ // xf1: xf2 & 8 | xf4 & 9
+ // xf2: xf3 + 2
+ // xf3: 6 & xf1-2 | xf4 & 9
+ // xf4: xf2 + 2
+ // xf1: 8
+ // xf3: 6
+
+ z1: z2 + 1 | z3 + 5
+ z2: z3 + 2
+ z3: z1 - 3
+ z3: 8
+ `,
+ out: `<0>{` +
+ `xa1: (8 | 9), ` +
+ `xa2: (<1>.xa3 + 2), ` +
+ `xa4: (<1>.xa2 + 2), ` +
+ `xa3: (6 & (<1>.xa1 - 2)), ` +
+
+ `xb1: _|_(((<1>.xb2 & 8) | (<1>.xb4 & 9)):empty disjunction: empty disjunction: cycle detected), ` +
+ `xb2: _|_(((6 & (<1>.xb1 - 2)) | (<1>.xb4 & 9)):empty disjunction: cycle detected), ` +
+ `xb4: _|_(((6 & (<1>.xb1 - 2)) | (<1>.xb4 & 9)):empty disjunction: cycle detected), ` +
+ `xb3: _|_(((6 & (<1>.xb1 - 2)) | (<1>.xb4 & 9)):empty disjunction: cycle detected), ` +
+
+ `xc1: (8 | 9), ` +
+ `xc2: (<1>.xc3 + 2), ` +
+ `xc4: (<1>.xc2 + 1), ` +
+ `xc5: (<1>.xc2 + 2), ` +
+ `xc3: (6 & (<1>.xc1 - 2)), ` +
+
+ `xd1: 8, ` +
+ `xd2: 8, ` +
+ `xd4: 9, ` +
+ `xd5: 10, ` +
+ `xd3: 6, ` +
+
+ `xe1: 9, ` +
+ `xe2: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+ `xe4: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+ `xe5: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+ `xe3: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+
+ `z1: _|_(((<1>.z2 + 1) | (<1>.z3 + 5)):empty disjunction: cycle detected), ` +
+ `z2: _|_(((<1>.z2 + 1) | (<1>.z3 + 5)):empty disjunction: cycle detected), ` +
+ `z3: _|_(((<1>.z2 + 1) | (<1>.z3 + 5)):empty disjunction: cycle detected)}`,
+ }, {
+ // Defaults should not alter the result of the above disjunctions.
+ // The results may differ, but errors and resolution should be roughly
+ // the same.
+ desc: "resolved self-reference cycles with disjunction with defaults",
+ in: `
+ // The disjunction in xa could be resolved, but as disjunctions
+ // are not resolved for expression, it remains unresolved.
+ xa1: *(xa2 & 8) | (xa4 & 9)
+ xa2: xa3 + 2
+ xa3: 6 & xa1-2
+ xa4: xa2 + 2
+
+ // As xb3 is a disjunction, xb2 cannot be resolved and evaluating
+ // the cycle completely is broken. However, it is not an error
+ // as the user might still resolve the disjunction.
+ xb1: *(xb2 & 8) | (xb4 & 9)
+ xb2: xb3 + 2
+ xb3: *(6 & (xb1-2)) | (xb4 & 9)
+ xb4: xb2 + 2
+
+ // Another variant with more disjunctions. xc1 remains with two
+ // possibilities. Technically, only the first value is valid.
+ // However, to fully determine that, all options of the remaining
+ // disjunction will have to be evaluated algebraically, which is
+ // not done.
+ xc1: *(xc2 & 8) | xc4 & 9 | xc5 & 9
+ xc2: xc3 + 2
+ xc3: 6 & xc1-2
+ xc4: xc2 + 1
+ xc5: xc2 + 2
+
+ // The above is resolved by setting xd1 explicitly.
+ xd1: *(xd2 & 8) | xd4 & 9 | xd5 & 9
+ xd2: xd3 + 2
+ xd3: 6 & xd1-2
+ xd4: xd2 + 1
+ xd5: xd2 + 2
+ xd1: 8
+
+ // The above is resolved by setting xd1 explicitly to the wrong
+ // value, resulting in an error.
+ xe1: *(xe2 & 8) | xe4 & 9 | xe5 & 9
+ xe2: xe3 + 2
+ xe3: 6 & xe1-2
+ xe4: xe2 + 1
+ xe5: xe2 + 2
+ xe1: 9
+
+ z1: *(z2 + 1) | z3 + 5
+ z2: z3 + 2
+ z3: z1 - 3
+ z3: 8
+ `,
+ out: `<0>{` +
+ `xa1: (*8 | 9), ` + // TODO: should resolve. Just testing logic, so okay for now.
+ `xa2: 8, ` +
+ `xa4: 10, ` +
+ `xa3: 6, ` +
+
+ `xb1: _|_((*(<1>.xb2 & 8) | (<1>.xb4 & 9)):empty disjunction: empty disjunction: cycle detected), ` +
+ `xb2: _|_((*(6 & (<1>.xb1 - 2)) | (<1>.xb4 & 9)):empty disjunction: cycle detected), ` +
+ `xb4: _|_((*(6 & (<1>.xb1 - 2)) | (<1>.xb4 & 9)):empty disjunction: cycle detected), ` +
+ `xb3: _|_((*(6 & (<1>.xb1 - 2)) | (<1>.xb4 & 9)):empty disjunction: cycle detected), ` +
+
+ `xc1: (*8 | 9), ` + // TODO: resolve
+ `xc2: 8, ` +
+ `xc4: 9, ` +
+ `xc5: 10, ` +
+ `xc3: 6, ` +
+
+ `xd1: 8, ` +
+ `xd2: 8, ` +
+ `xd4: 9, ` +
+ `xd5: 10, ` +
+ `xd3: 6, ` +
+
+ `xe1: 9, ` +
+ `xe2: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+ `xe4: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+ `xe5: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+ `xe3: _|_((6 & 7):cannot unify numbers 6 and 7), ` +
+
+ `z1: _|_((*(<1>.z2 + 1) | (<1>.z3 + 5)):empty disjunction: cycle detected), ` +
+ `z2: _|_((*(<1>.z2 + 1) | (<1>.z3 + 5)):empty disjunction: cycle detected), ` +
+ `z3: _|_((*(<1>.z2 + 1) | (<1>.z3 + 5)):empty disjunction: cycle detected)}`,
}}
rewriteHelper(t, testCases, evalPartial)
}
diff --git a/cue/subsume_test.go b/cue/subsume_test.go
index 021fd54..34066d2 100644
--- a/cue/subsume_test.go
+++ b/cue/subsume_test.go
@@ -250,7 +250,7 @@
145: {subsumes: false, in: ` a: "s \(d) e", b: "s a e", d: _`},
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},
+ 147: {subsumes: true, in: ` a: 7080, b: *7080 | int`, mode: subChoose},
// Defaults
150: {subsumes: false, in: `a: number | *1, b: number | *2`},
