internal/core/eval: fix spurious cycle detection
When evaluating a Vertex for a selector, outside the usual
arc evaluation path, it is not necessarily on a cycle path.
Delay marking such a Vertex as "EvaluatingArcs" to prevent
spurious cycle detection. If there is indeed a cycle, then
this will be marked as such as the cycle will be triggered
at the usual path anyway.
Fixes #588
Change-Id: Ieae3eebd0157847537cfd02c06d3ffe64e04987d
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/7622
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/cycle/structural.txtar b/cue/testdata/cycle/structural.txtar
index ddc4ad5..2734599 100644
--- a/cue/testdata/cycle/structural.txtar
+++ b/cue/testdata/cycle/structural.txtar
@@ -23,6 +23,18 @@
a: a | int
}
+a7: {
+ a: c.x
+ b: {
+ x: c
+ y: "foo"
+ }
+ c: {
+ x: b.y
+ y: 3
+ }
+}
+
b1: {
b: a & [1]
a: [a|int]
@@ -387,8 +399,8 @@
b14.root.b.1.1: structural cycle
b4.x.y.0: structural cycle
b6.b.a.0: conflicting values 1 and [1] (mismatched types int and list):
- ./in.cue:51:16
- ./in.cue:51:17
+ ./in.cue:63:16
+ ./in.cue:63:17
b6.b.a.0.0: structural cycle
b6.x.a.0: structural cycle
b7.a.0: structural cycle
@@ -401,46 +413,46 @@
e2.a.c: structural cycle
e2.b.c: structural cycle
e3.a: conflicting values [a] and {c:a} (mismatched types list and struct):
- ./in.cue:277:8
- ./in.cue:278:8
+ ./in.cue:289:8
+ ./in.cue:290:8
e3.a.0: conflicting values [a] and {c:a} (mismatched types list and struct):
- ./in.cue:277:8
- ./in.cue:278:8
+ ./in.cue:289:8
+ ./in.cue:290:8
e3.a.0: structural cycle
e3.a.c: conflicting values [a] and {c:a} (mismatched types list and struct):
- ./in.cue:277:8
- ./in.cue:278:8
+ ./in.cue:289:8
+ ./in.cue:290:8
e3.a.c: structural cycle
e3.b: conflicting values [b] and {c:b} (mismatched types list and struct):
- ./in.cue:280:8
- ./in.cue:281:8
+ ./in.cue:292:8
+ ./in.cue:293:8
e3.b.0: conflicting values [b] and {c:b} (mismatched types list and struct):
- ./in.cue:280:8
- ./in.cue:281:8
+ ./in.cue:292:8
+ ./in.cue:293:8
e3.b.0: structural cycle
e3.b.c: conflicting values [b] and {c:b} (mismatched types list and struct):
- ./in.cue:280:8
- ./in.cue:281:8
+ ./in.cue:292:8
+ ./in.cue:293:8
e3.b.c: structural cycle
e4.a.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- ./in.cue:285:13
- ./in.cue:286:9
+ ./in.cue:297:13
+ ./in.cue:298:9
e4.b.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- ./in.cue:288:9
- ./in.cue:289:13
+ ./in.cue:300:9
+ ./in.cue:301:13
p2.#T.a.b.link: structural cycle
p3.#U.#T.a.b.link: structural cycle
p5.#T.a.0.link: structural cycle
p6.#U.#T.a.0.link: structural cycle
z1.z.g.h: structural cycle
b4.x.y.0: structural cycle:
- ./in.cue:41:8
+ ./in.cue:53:8
d2.a.b.c.d.t: structural cycle:
- ./in.cue:242:8
+ ./in.cue:254:8
d2.r: structural cycle:
- ./in.cue:242:8
+ ./in.cue:254:8
0: structural cycle:
- ./in.cue:252:19
+ ./in.cue:264:19
Result:
(_|_){
@@ -483,6 +495,20 @@
a6: (struct){
a: (_){ |((_){ _ }, (int){ int }) }
}
+ a7: (struct){
+ a: (string){ "foo" }
+ b: (struct){
+ x: (struct){
+ x: (string){ "foo" }
+ y: (int){ 3 }
+ }
+ y: (string){ "foo" }
+ }
+ c: (struct){
+ x: (string){ "foo" }
+ y: (int){ 3 }
+ }
+ }
b1: (struct){
b: (#list){
0: (int){ 1 }
@@ -515,7 +541,7 @@
// [structural cycle]
b: (_|_){
// [structural cycle] b4.x.y.0: structural cycle:
- // ./in.cue:41:8
+ // ./in.cue:53:8
0: (int){ 1 }
}
x: (_|_){
@@ -552,8 +578,8 @@
// [eval]
0: (_|_){
// [eval] b6.b.a.0: conflicting values 1 and [1] (mismatched types int and list):
- // ./in.cue:51:16
- // ./in.cue:51:17
+ // ./in.cue:63:16
+ // ./in.cue:63:17
0: (_|_){
// [structural cycle] b6.b.a.0.0: structural cycle
}
@@ -997,11 +1023,11 @@
// [structural cycle]
x: (_|_){
// [structural cycle] d2.a.b.c.d.t: structural cycle:
- // ./in.cue:242:8
+ // ./in.cue:254:8
}
r: (_|_){
// [structural cycle] d2.r: structural cycle:
- // ./in.cue:242:8
+ // ./in.cue:254:8
c: (_|_){// {
// d: {
// h: int
@@ -1044,19 +1070,19 @@
// [structural cycle]
c: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:252:19
+ // ./in.cue:264:19
}
}
}
indirect: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:252:19
+ // ./in.cue:264:19
}
i: (int){ 1 }
}
x: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:252:19
+ // ./in.cue:264:19
i: (int){ 0 }
}
}
@@ -1102,12 +1128,12 @@
// [eval]
a: (_|_){
// [eval] e3.a: conflicting values [a] and {c:a} (mismatched types list and struct):
- // ./in.cue:277:8
- // ./in.cue:278:8
+ // ./in.cue:289:8
+ // ./in.cue:290:8
c: (_|_){
// [eval] e3.a.c: conflicting values [a] and {c:a} (mismatched types list and struct):
- // ./in.cue:277:8
- // ./in.cue:278:8
+ // ./in.cue:289:8
+ // ./in.cue:290:8
// e3.a.c: structural cycle
c: (_|_){// 〈1;a〉
}
@@ -1116,8 +1142,8 @@
}
0: (_|_){
// [eval] e3.a.0: conflicting values [a] and {c:a} (mismatched types list and struct):
- // ./in.cue:277:8
- // ./in.cue:278:8
+ // ./in.cue:289:8
+ // ./in.cue:290:8
// e3.a.0: structural cycle
c: (_|_){// 〈1;a〉
}
@@ -1127,12 +1153,12 @@
}
b: (_|_){
// [eval] e3.b: conflicting values [b] and {c:b} (mismatched types list and struct):
- // ./in.cue:280:8
- // ./in.cue:281:8
+ // ./in.cue:292:8
+ // ./in.cue:293:8
c: (_|_){
// [eval] e3.b.c: conflicting values [b] and {c:b} (mismatched types list and struct):
- // ./in.cue:280:8
- // ./in.cue:281:8
+ // ./in.cue:292:8
+ // ./in.cue:293:8
// e3.b.c: structural cycle
c: (_|_){// 〈1;b〉
}
@@ -1141,8 +1167,8 @@
}
0: (_|_){
// [eval] e3.b.0: conflicting values [b] and {c:b} (mismatched types list and struct):
- // ./in.cue:280:8
- // ./in.cue:281:8
+ // ./in.cue:292:8
+ // ./in.cue:293:8
// e3.b.0: structural cycle
c: (_|_){// 〈1;b〉
}
@@ -1157,8 +1183,8 @@
// [eval]
0: (_|_){
// [eval] e4.a.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- // ./in.cue:285:13
- // ./in.cue:286:9
+ // ./in.cue:297:13
+ // ./in.cue:298:9
0: (struct){
c: (int){ 1 }
}
@@ -1168,8 +1194,8 @@
// [eval]
0: (_|_){
// [eval] e4.b.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- // ./in.cue:288:9
- // ./in.cue:289:13
+ // ./in.cue:300:9
+ // ./in.cue:301:13
0: (struct){
c: (int){ 1 }
}
@@ -1357,6 +1383,17 @@
a6: {
a: (〈0;a〉|int)
}
+ a7: {
+ a: 〈0;c〉.x
+ b: {
+ x: 〈1;c〉
+ y: "foo"
+ }
+ c: {
+ x: 〈1;b〉.y
+ y: 3
+ }
+ }
b1: {
b: (〈0;a〉 & [
1,
diff --git a/internal/core/adt/composite.go b/internal/core/adt/composite.go
index e5aeba4..2e8806c 100644
--- a/internal/core/adt/composite.go
+++ b/internal/core/adt/composite.go
@@ -228,6 +228,10 @@
// nodeContext to allow reusing the computations done so far.
Partial
+ // FieldSetDefined indicates that the value and conjuncts of all fields have
+ // been completed, but that the individual arcs are not yet evaluated.
+ FieldSetDefined
+
// EvaluatingArcs indicates that the arcs of the Vertex are currently being
// evaluated. If this is encountered it indicates a structural cycle.
// Value does not have to be nil
diff --git a/internal/core/adt/expr.go b/internal/core/adt/expr.go
index d8c4876..e0f7819 100644
--- a/internal/core/adt/expr.go
+++ b/internal/core/adt/expr.go
@@ -585,7 +585,7 @@
}
func (x *SelectorExpr) resolve(c *OpContext) *Vertex {
- n := c.node(x.X, EvaluatingArcs)
+ n := c.node(x.X, FieldSetDefined)
return c.lookup(n, x.Src.Sel.Pos(), x.Sel)
}
diff --git a/internal/core/eval/disjunct.go b/internal/core/eval/disjunct.go
index 2faa272..057e596 100644
--- a/internal/core/eval/disjunct.go
+++ b/internal/core/eval/disjunct.go
@@ -126,8 +126,8 @@
envDisjunct{env, a, x.NumDefaults, cloneID})
}
-func (n *nodeContext) updateResult() (isFinal bool) {
- n.postDisjunct()
+func (n *nodeContext) updateResult(state adt.VertexStatus) (isFinal bool) {
+ n.postDisjunct(state)
if n.hasErr() {
return n.isFinal
@@ -182,8 +182,8 @@
return n.isFinal
}
-func (n *nodeContext) tryDisjuncts() (finished bool) {
- if !n.insertDisjuncts() || !n.updateResult() {
+func (n *nodeContext) tryDisjuncts(state adt.VertexStatus) (finished bool) {
+ if !n.insertDisjuncts() || !n.updateResult(state) {
if !n.isFinal {
return false // More iterations to do.
}
diff --git a/internal/core/eval/eval.go b/internal/core/eval/eval.go
index 006ee26..079550c 100644
--- a/internal/core/eval/eval.go
+++ b/internal/core/eval/eval.go
@@ -132,7 +132,7 @@
func (e *Evaluator) Eval(v *adt.Vertex) errors.Error {
if v.Value == nil {
ctx := adt.NewContext(e.r, e, v)
- e.Unify(ctx, v, adt.Finalized)
+ e.Unify(ctx, v, adt.Partial)
}
// extract error if needed.
@@ -268,7 +268,7 @@
// defer c.PopVertex(c.PushVertex(v))
- if state <= v.Status()+1 {
+ if state <= v.Status() {
return
}
@@ -434,7 +434,7 @@
// Handle disjunctions. If there are no disjunctions, this call is
// equivalent to calling n.postDisjunct.
- if n.tryDisjuncts() {
+ if n.tryDisjuncts(state) {
if v.Value == nil {
v.Value = n.getValidators()
}
@@ -452,7 +452,7 @@
return ok
}
-func (n *nodeContext) postDisjunct() {
+func (n *nodeContext) postDisjunct(state adt.VertexStatus) {
ctx := n.ctx
for {
@@ -595,6 +595,12 @@
n.updateClosedInfo()
+ n.completeArcs(state)
+}
+
+func (n *nodeContext) completeArcs(state adt.VertexStatus) {
+ ctx := n.ctx
+
if cyclic := n.hasCycle && !n.hasNonCycle; cyclic {
n.node.Value = adt.CombineErrors(nil, n.node.Value, &adt.Bottom{
Code: adt.StructuralCycleError,
@@ -607,7 +613,9 @@
for _, a := range n.node.Arcs {
// Call UpdateStatus here to be absolutely sure the status is set
// correctly and that we are not regressing.
- n.node.UpdateStatus(adt.EvaluatingArcs)
+ if state == adt.Finalized {
+ n.node.UpdateStatus(adt.EvaluatingArcs)
+ }
n.eval.Unify(ctx, a, adt.Finalized)
if err, _ := a.Value.(*adt.Bottom); err != nil {
n.node.AddChildError(err)
