internal/core/eval: fix bug in cycle handling
Basically, the dereference list was grown incorrectly.
This was exposed when a cyclic structure is
referenced from within a more than 1 deeply
nested other cyclic structure.
Fixes #555
Fixes #534
Change-Id: I8aa71a37eb19b5efc75fc3bd75c8e00d254d88d7
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/7481
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 fabbba1..7c24827 100644
--- a/cue/testdata/cycle/structural.txtar
+++ b/cue/testdata/cycle/structural.txtar
@@ -61,6 +61,33 @@
a: [a]
}
+// Issue #555
+b8: {
+ x: a
+ a: f: b
+ b: a | string
+}
+
+// Issue #555
+b9: {
+ #a: string | #b | #ref
+ #b: {
+ c: [#a, #a, #a]
+ }
+ #ref: ref: string
+ x: #b | #ref
+}
+
+// Issue #534
+b10: {
+ a: close({
+ b: string | a | c
+ })
+ c: close({
+ d: string | a
+ })
+}
+
c1: {
a: {
b: {}
@@ -236,43 +263,43 @@
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:114:8
- ./in.cue:115:8
+ ./in.cue:141:8
+ ./in.cue:142:8
e3.a.0: conflicting values [a] and {c:a} (mismatched types list and struct):
- ./in.cue:114:8
- ./in.cue:115:8
+ ./in.cue:141:8
+ ./in.cue:142:8
e3.a.0: structural cycle
e3.a.c: conflicting values [a] and {c:a} (mismatched types list and struct):
- ./in.cue:114:8
- ./in.cue:115:8
+ ./in.cue:141:8
+ ./in.cue:142:8
e3.a.c: structural cycle
e3.b: conflicting values [b] and {c:b} (mismatched types list and struct):
- ./in.cue:117:8
- ./in.cue:118:8
+ ./in.cue:144:8
+ ./in.cue:145:8
e3.b.0: conflicting values [b] and {c:b} (mismatched types list and struct):
- ./in.cue:117:8
- ./in.cue:118:8
+ ./in.cue:144:8
+ ./in.cue:145:8
e3.b.0: structural cycle
e3.b.c: conflicting values [b] and {c:b} (mismatched types list and struct):
- ./in.cue:117:8
- ./in.cue:118:8
+ ./in.cue:144:8
+ ./in.cue:145:8
e3.b.c: structural cycle
e4.a.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- ./in.cue:122:13
- ./in.cue:123:9
+ ./in.cue:149:13
+ ./in.cue:150:9
e4.b.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- ./in.cue:125:9
- ./in.cue:126:13
+ ./in.cue:152:9
+ ./in.cue:153:13
z1.z.f.h.h: structural cycle
z1.z.g.h: structural cycle
b4.x.y.0: structural cycle:
./in.cue:41:8
d2.a.b.c.d.t: structural cycle:
- ./in.cue:79:8
+ ./in.cue:106:8
d2.r: structural cycle:
- ./in.cue:79:8
+ ./in.cue:106:8
0: structural cycle:
- ./in.cue:89:19
+ ./in.cue:116:19
Result:
(_|_){
@@ -420,6 +447,61 @@
}
}
}
+ b8: (struct){
+ x: (struct){
+ f: (string){ string }
+ }
+ a: (struct){
+ f: (string){ string }
+ }
+ b: (string){ string }
+ }
+ b9: (struct){
+ #a: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ #b: (#struct){
+ c: (#list){
+ 0: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ 1: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ 2: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ }
+ }
+ #ref: (#struct){
+ ref: (string){ string }
+ }
+ x: (struct){ |((#struct){
+ c: (#list){
+ 0: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ 1: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ 2: ((string|struct)){ |((string){ string }, (#struct){
+ ref: (string){ string }
+ }) }
+ }
+ }, (#struct){
+ ref: (string){ string }
+ }) }
+ }
+ b10: (struct){
+ a: (#struct){
+ b: ((string|struct)){ |((string){ string }, (#struct){
+ d: (string){ string }
+ }) }
+ }
+ c: (#struct){
+ d: (string){ string }
+ }
+ }
c1: (_|_){
// [structural cycle]
a: (_|_){
@@ -483,11 +565,11 @@
// [structural cycle]
x: (_|_){
// [structural cycle] d2.a.b.c.d.t: structural cycle:
- // ./in.cue:79:8
+ // ./in.cue:106:8
}
r: (_|_){
// [structural cycle] d2.r: structural cycle:
- // ./in.cue:79:8
+ // ./in.cue:106:8
c: (_|_){// {
// d: {
// h: int
@@ -530,13 +612,13 @@
// [structural cycle]
c: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:89:19
+ // ./in.cue:116:19
}
}
}
indirect: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:89:19
+ // ./in.cue:116:19
}
i: (int){ 1 }
}
@@ -548,13 +630,13 @@
// [structural cycle]
c: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:89:19
+ // ./in.cue:116:19
}
}
}
indirect: (_|_){
// [structural cycle] 0: structural cycle:
- // ./in.cue:89:19
+ // ./in.cue:116:19
}
i: (int){ 0 }
}
@@ -601,12 +683,12 @@
// [eval]
a: (_|_){
// [eval] e3.a: conflicting values [a] and {c:a} (mismatched types list and struct):
- // ./in.cue:114:8
- // ./in.cue:115:8
+ // ./in.cue:141:8
+ // ./in.cue:142:8
c: (_|_){
// [eval] e3.a.c: conflicting values [a] and {c:a} (mismatched types list and struct):
- // ./in.cue:114:8
- // ./in.cue:115:8
+ // ./in.cue:141:8
+ // ./in.cue:142:8
// e3.a.c: structural cycle
c: (_|_){// 〈1;a〉
}
@@ -615,8 +697,8 @@
}
0: (_|_){
// [eval] e3.a.0: conflicting values [a] and {c:a} (mismatched types list and struct):
- // ./in.cue:114:8
- // ./in.cue:115:8
+ // ./in.cue:141:8
+ // ./in.cue:142:8
// e3.a.0: structural cycle
c: (_|_){// 〈1;a〉
}
@@ -626,12 +708,12 @@
}
b: (_|_){
// [eval] e3.b: conflicting values [b] and {c:b} (mismatched types list and struct):
- // ./in.cue:117:8
- // ./in.cue:118:8
+ // ./in.cue:144:8
+ // ./in.cue:145:8
c: (_|_){
// [eval] e3.b.c: conflicting values [b] and {c:b} (mismatched types list and struct):
- // ./in.cue:117:8
- // ./in.cue:118:8
+ // ./in.cue:144:8
+ // ./in.cue:145:8
// e3.b.c: structural cycle
c: (_|_){// 〈1;b〉
}
@@ -640,8 +722,8 @@
}
0: (_|_){
// [eval] e3.b.0: conflicting values [b] and {c:b} (mismatched types list and struct):
- // ./in.cue:117:8
- // ./in.cue:118:8
+ // ./in.cue:144:8
+ // ./in.cue:145:8
// e3.b.0: structural cycle
c: (_|_){// 〈1;b〉
}
@@ -656,8 +738,8 @@
// [eval]
0: (_|_){
// [eval] e4.a.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- // ./in.cue:122:13
- // ./in.cue:123:9
+ // ./in.cue:149:13
+ // ./in.cue:150:9
0: (struct){
c: (int){ 1 }
}
@@ -667,8 +749,8 @@
// [eval]
0: (_|_){
// [eval] e4.b.0: conflicting values [{c:1}] and {} (mismatched types list and struct):
- // ./in.cue:125:9
- // ./in.cue:126:13
+ // ./in.cue:152:9
+ // ./in.cue:153:13
0: (struct){
c: (int){ 1 }
}
@@ -779,8 +861,6 @@
// [structural cycle]
h: (_|_){
// [structural cycle] z1.z.f.h.h: structural cycle
- h: (_|_){// 〈1;g〉
- }
}
}
}
@@ -932,6 +1012,35 @@
〈0;a〉,
]
}
+ b8: {
+ x: 〈0;a〉
+ a: {
+ f: 〈1;b〉
+ }
+ b: (〈0;a〉|string)
+ }
+ b9: {
+ #a: (string|〈0;#b〉|〈0;#ref〉)
+ #b: {
+ c: [
+ 〈1;#a〉,
+ 〈1;#a〉,
+ 〈1;#a〉,
+ ]
+ }
+ #ref: {
+ ref: string
+ }
+ x: (〈0;#b〉|〈0;#ref〉)
+ }
+ b10: {
+ a: close({
+ b: (string|〈1;a〉|〈1;c〉)
+ })
+ c: close({
+ d: (string|〈1;a〉)
+ })
+ }
c1: {
a: {
b: {}
diff --git a/internal/core/eval/closed.go b/internal/core/eval/closed.go
index ea96a32..8fbd14d 100644
--- a/internal/core/eval/closed.go
+++ b/internal/core/eval/closed.go
@@ -374,7 +374,7 @@
if n != nil {
for _, c := range v.Conjuncts {
- c = updateCyclic(c, cyclic, nil)
+ c = updateCyclic(c, cyclic, nil, nil)
c.CloseID += id
n.addExprConjunct(c)
}
diff --git a/internal/core/eval/eval.go b/internal/core/eval/eval.go
index ec45c9b..98ec358 100644
--- a/internal/core/eval/eval.go
+++ b/internal/core/eval/eval.go
@@ -1237,7 +1237,11 @@
ctx.Unify(ctx, arc, adt.Finalized)
for _, c := range arc.Conjuncts {
- c = updateCyclic(c, cyclic, arc)
+ var a []*adt.Vertex
+ if v.Env != nil {
+ a = v.Env.Deref
+ }
+ c = updateCyclic(c, cyclic, arc, a)
c.CloseID = closeID
n.addExprConjunct(c)
}
@@ -1298,12 +1302,11 @@
// a structural cycle.
func (n *nodeContext) updateCyclicStatus(env *adt.Environment) {
if env == nil || !env.Cyclic {
- // fmt.Printf("%p -- %d hasNonCycle\n", n.node, n.node.Label)
n.hasNonCycle = true
}
}
-func updateCyclic(c adt.Conjunct, cyclic bool, deref *adt.Vertex) adt.Conjunct {
+func updateCyclic(c adt.Conjunct, cyclic bool, deref *adt.Vertex, a []*adt.Vertex) adt.Conjunct {
env := c.Env
switch {
case env == nil:
@@ -1311,7 +1314,7 @@
return c
}
env = &adt.Environment{Cyclic: cyclic}
- case deref == nil && env.Cyclic == cyclic:
+ case deref == nil && env.Cyclic == cyclic && len(a) == 0:
return c
default:
// The conjunct may still be in use in other fields, so we should
@@ -1320,8 +1323,15 @@
e.Cyclic = e.Cyclic || cyclic
env = &e
}
+ if deref != nil || len(a) > 0 {
+ cp := make([]*adt.Vertex, 0, len(a)+1)
+ cp = append(cp, a...)
+ if deref != nil {
+ cp = append(cp, deref)
+ }
+ env.Deref = cp
+ }
if deref != nil {
- env.Deref = append(env.Deref, deref)
env.Cycles = append(env.Cycles, deref)
}
return adt.MakeConjunct(env, c.Expr(), c.CloseID)
@@ -1354,7 +1364,7 @@
}
for _, c := range x.Conjuncts {
- c = updateCyclic(c, cyclic, nil)
+ c = updateCyclic(c, cyclic, nil, nil)
c.CloseID = id
n.addExprConjunct(c) // TODO: Pass from eval
}
@@ -1370,7 +1380,7 @@
case *adt.StructMarker:
for _, a := range x.Arcs {
c := adt.MakeConjunct(nil, a, id)
- c = updateCyclic(c, cyclic, nil)
+ c = updateCyclic(c, cyclic, nil, nil)
n.insertField(a.Label, c)
}
