internal/core/eval: handle structural cycles
Issue #29
Issue #42
Change-Id: I86191d7bf4fdcf8705d740171aedd81e04819dd5
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/6522
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/cycle/015_reference_across_tuples_and_back.txtar b/cue/testdata/cycle/015_reference_across_tuples_and_back.txtar
index 4550cd4..1496ff2 100644
--- a/cue/testdata/cycle/015_reference_across_tuples_and_back.txtar
+++ b/cue/testdata/cycle/015_reference_across_tuples_and_back.txtar
@@ -54,6 +54,6 @@
}
b: (struct){
e: (int){ 3 }
- f: (_){ _ }
+ f: (int){ 3 }
}
}
diff --git a/cue/testdata/cycle/023_reentrance.txtar b/cue/testdata/cycle/023_reentrance.txtar
index 1b6596e..57913b6 100644
--- a/cue/testdata/cycle/023_reentrance.txtar
+++ b/cue/testdata/cycle/023_reentrance.txtar
@@ -79,7 +79,8 @@
}).out
}
-- out/eval --
-(struct){
+(_|_){
+ // [structural cycle]
fibRec: (struct){
nn: (int){ int }
out: (_|_){
@@ -93,6 +94,10 @@
n: (int){ int }
}
fib2: (int){ 1 }
- fib7: (int){ 13 }
- fib12: (int){ 144 }
+ fib7: (_|_){
+ // [structural cycle]
+ }
+ fib12: (_|_){
+ // [structural cycle]
+ }
}
diff --git a/cue/testdata/cycle/025_cannot_resolve_references_that_would_be_ambiguous.txtar b/cue/testdata/cycle/025_cannot_resolve_references_that_would_be_ambiguous.txtar
index 94aba3e..412f416 100644
--- a/cue/testdata/cycle/025_cannot_resolve_references_that_would_be_ambiguous.txtar
+++ b/cue/testdata/cycle/025_cannot_resolve_references_that_would_be_ambiguous.txtar
@@ -56,22 +56,26 @@
-- out/eval --
(struct){
a1: (_|_){
- // [incomplete]
+ // [incomplete] incomplete cause disjunction
}
a2: (_|_){
- // [incomplete]
+ // [incomplete] incomplete cause disjunction
}
a3: (int){ 1 }
- b1: (_|_){
- // [incomplete] ambiguous disjunction
- }
- b2: (_|_){
- // [incomplete] ambiguous disjunction
- }
- c1: (_|_){
- // [incomplete] ambiguous disjunction
- }
- c2: (_|_){
- // [incomplete] ambiguous disjunction
- }
+ b1: (int){ |((int){ 0 }, (int){ 1 }) }
+ b2: (int){ |((int){ 1 }, (int){ 0 }) }
+ c1: (struct){ |((struct){
+ a: (int){ 1 }
+ b: (int){ 2 }
+ }, (struct){
+ b: (int){ 1 }
+ a: (int){ 2 }
+ }) }
+ c2: (struct){ |((struct){
+ a: (int){ 2 }
+ b: (int){ 1 }
+ }, (struct){
+ b: (int){ 2 }
+ a: (int){ 1 }
+ }) }
}
diff --git a/cue/testdata/cycle/051_resolved_self-reference_cycles_with_disjunction.txtar b/cue/testdata/cycle/051_resolved_self-reference_cycles_with_disjunction.txtar
index 1381f59..e346530 100644
--- a/cue/testdata/cycle/051_resolved_self-reference_cycles_with_disjunction.txtar
+++ b/cue/testdata/cycle/051_resolved_self-reference_cycles_with_disjunction.txtar
@@ -169,10 +169,14 @@
xa2: (int){ 8 }
xa3: (int){ 6 }
xa4: (int){ 10 }
- xb1: (int){ 8 }
- xb2: (int){ 8 }
- xb3: (int){ 6 }
- xb4: (int){ 10 }
+ xb1: (int){ |((int){ 8 }, (int){ 9 }) }
+ xb2: (_|_){
+ // [incomplete]
+ }
+ xb3: (int){ |((int){ 6 }, (int){ 9 }) }
+ xb4: (_|_){
+ // [cycle] cycle error
+ }
xc1: (int){ |((int){ 8 }, (int){ 9 }) }
xc2: (int){ 8 }
xc3: (int){ 6 }
@@ -202,10 +206,14 @@
// [eval] incompatible values 7 and 6:
// ./in.cue:44:6
}
- xf1: (int){ 8 }
- xf2: (int){ 8 }
- xf3: (int){ 6 }
- xf4: (int){ 10 }
+ xf1: (int){ |((int){ 8 }, (int){ 9 }) }
+ xf2: (_|_){
+ // [incomplete]
+ }
+ xf3: (int){ |((int){ 6 }, (int){ 9 }) }
+ xf4: (_|_){
+ // [cycle] cycle error
+ }
z1: (int){ |((int){ 11 }, (int){ 13 }) }
z2: (int){ 10 }
z3: (int){ 8 }
diff --git a/cue/testdata/cycle/052_resolved_self-reference_cycles_with_disjunction_with_defaults.txtar b/cue/testdata/cycle/052_resolved_self-reference_cycles_with_disjunction_with_defaults.txtar
index 8ff1abb..6295a4f 100644
--- a/cue/testdata/cycle/052_resolved_self-reference_cycles_with_disjunction_with_defaults.txtar
+++ b/cue/testdata/cycle/052_resolved_self-reference_cycles_with_disjunction_with_defaults.txtar
@@ -139,10 +139,14 @@
xa2: (int){ 8 }
xa3: (int){ 6 }
xa4: (int){ 10 }
- xb1: (int){ 8 }
- xb2: (int){ 8 }
+ xb1: (int){ |(*(int){ 8 }, (int){ 9 }) }
+ xb2: (_|_){
+ // [incomplete]
+ }
xb3: (int){ 6 }
- xb4: (int){ 10 }
+ xb4: (_|_){
+ // [cycle] cycle error
+ }
xc1: (int){ |(*(int){ 8 }, (int){ 9 }) }
xc2: (int){ 8 }
xc3: (int){ 6 }
diff --git a/cue/testdata/cycle/disjunction.txtar b/cue/testdata/cycle/disjunction.txtar
new file mode 100644
index 0000000..accdcfe
--- /dev/null
+++ b/cue/testdata/cycle/disjunction.txtar
@@ -0,0 +1,150 @@
+-- in.cue --
+
+// cycle is a structural cycle
+cycle: a: cycle
+
+// reference to outside structural cycle
+r1a: cycle | int
+r1b: int | cycle
+
+r2a: cycle | 1
+r2b: 1 | cycle
+
+r3a: cycle | null
+r3b: null | cycle
+
+r4a: cycle | {}
+r4b: {} | cycle
+
+r5a: cycle | []
+r5b: [] | cycle
+
+// reference to ancestor node
+s1a: x: s1a | int
+s1b: x: int | s1b
+
+s2a: x: s2a | 1
+s2b: x: 1 | s2b
+
+s3a: x: s3a | null
+s3b: x: null | s3b
+
+s4a: x: s4a | {}
+s4b: x: {} | s4b
+
+s5a: x: s5a | []
+s5b: x: [] | s5b
+
+
+
+-- out/eval --
+Errors:
+structural cycle
+
+Result:
+(_|_){
+ // [structural cycle]
+ cycle: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle] structural cycle
+ a: (_|_){// 〈1;cycle〉
+ }
+ }
+ }
+ r1a: (int){ int }
+ r1b: (int){ int }
+ r2a: (int){ 1 }
+ r2b: (int){ 1 }
+ r3a: (null){ null }
+ r3b: (null){ null }
+ r4a: (struct){
+ }
+ r4b: (struct){
+ }
+ r5a: (#list){
+ }
+ r5b: (#list){
+ }
+ s1a: (struct){
+ x: (int){ int }
+ }
+ s1b: (struct){
+ x: (int){ int }
+ }
+ s2a: (struct){
+ x: (int){ 1 }
+ }
+ s2b: (struct){
+ x: (int){ 1 }
+ }
+ s3a: (struct){
+ x: (null){ null }
+ }
+ s3b: (struct){
+ x: (null){ null }
+ }
+ s4a: (struct){
+ x: (struct){
+ }
+ }
+ s4b: (struct){
+ x: (struct){
+ }
+ }
+ s5a: (struct){
+ x: (#list){
+ }
+ }
+ s5b: (struct){
+ x: (#list){
+ }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ cycle: {
+ a: 〈1;cycle〉
+ }
+ r1a: (〈0;cycle〉|int)
+ r1b: (int|〈0;cycle〉)
+ r2a: (〈0;cycle〉|1)
+ r2b: (1|〈0;cycle〉)
+ r3a: (〈0;cycle〉|null)
+ r3b: (null|〈0;cycle〉)
+ r4a: (〈0;cycle〉|{})
+ r4b: ({}|〈0;cycle〉)
+ r5a: (〈0;cycle〉|[])
+ r5b: ([]|〈0;cycle〉)
+ s1a: {
+ x: (〈1;s1a〉|int)
+ }
+ s1b: {
+ x: (int|〈1;s1b〉)
+ }
+ s2a: {
+ x: (〈1;s2a〉|1)
+ }
+ s2b: {
+ x: (1|〈1;s2b〉)
+ }
+ s3a: {
+ x: (〈1;s3a〉|null)
+ }
+ s3b: {
+ x: (null|〈1;s3b〉)
+ }
+ s4a: {
+ x: (〈1;s4a〉|{})
+ }
+ s4b: {
+ x: ({}|〈1;s4b〉)
+ }
+ s5a: {
+ x: (〈1;s5a〉|[])
+ }
+ s5b: {
+ x: ([]|〈1;s5b〉)
+ }
+}
diff --git a/cue/testdata/cycle/issue429.txtar b/cue/testdata/cycle/issue429.txtar
index fb9aaff..6e487d1 100644
--- a/cue/testdata/cycle/issue429.txtar
+++ b/cue/testdata/cycle/issue429.txtar
@@ -1,72 +1,168 @@
+TODO: a bound value resolving to a disjunction should probably
+be an error. In this case #Size.amx should resolve.
+
-- in.cue --
-range1: {
- min: *1 | int
- range: >min
- range: 8
-}
-range2: {
- min: *1 | int
- max: int & >min
-}
-rg: range2 & {
-// min: 1
- max: 8
-}
+// Range disjunction without cycle (checks only one-way).
#Size : {
- res: uint | * 0
- num: > res | *(1 + res)
- max: > num | *num
+ res: uint | * 0
+ min: >res | *(1 + res)
+ max: >min | *min
}
-a: #Size & {
- num: 5
+s0: #Size & { res: 1 }
+// This discards the default for max. This is correct, but unfortunate.
+// TODO: is there a tweak to the default mechanism possible that would fix that?
+// Tread very carefully, though! Perhaps we could have a builtin that
+// discards any default, so that we can at least manually override this
+// behavior.
+s1: #Size & { min: 5 }
+s2: #Size & { max: 5 }
+s3: #Size & {
+ min: 5
+ max: 10
}
+es3: #Size & {
+ min: 10
+ max: 5
+}
+
+// Disjunctions with cycles
+// TODO: improve error message here. Logic is correct, though.
+#nonEmptyRange: {
+ min: *1 | int
+ min: <max
+ max: >min
+}
+r1: #nonEmptyRange & {
+ min: 3
+}
+r2: #nonEmptyRange & {
+ max: 5
+}
+r3: #nonEmptyRange & {
+ min: 3
+ max: 6
+}
+
+er3: #nonEmptyRange & {
+ min: 5
+ max: 5
+}
+
+
-- out/eval --
-(struct){
- range1: (struct){
- min: (int){ |(*(int){ 1 }, (int){ int }) }
- range: (int){ 8 }
- }
- range2: (struct){
- min: (int){ |(*(int){ 1 }, (int){ int }) }
- max: (int){ &(>1, int) }
- }
- rg: (struct){
- min: (int){ |(*(int){ 1 }, (int){ int }) }
- max: (int){ 8 }
- }
+Errors:
+invalid value 5 (out of bound <5)
+invalid value 5 (out of bound >10)
+
+Result:
+(_|_){
+ // [eval]
#Size: (#struct){
res: (int){ |(*(int){ 0 }, (int){ &(>=0, int) }) }
- num: (number){ |(*(int){ 1 }, (number){ >0 }) }
+ min: (number){ |(*(int){ 1 }, (number){ >0 }) }
max: (number){ |(*(int){ 1 }, (number){ >0 }, (number){ >1 }) }
}
- a: (#struct){
+ s0: (#struct){
+ res: (int){ 1 }
+ min: (number){ |(*(int){ 2 }, (number){ >1 }) }
+ max: (number){ |(*(int){ 2 }, (number){ >1 }, (number){ >2 }) }
+ }
+ s1: (#struct){
res: (int){ |(*(int){ 0 }, (int){ &(>=0, int) }) }
- num: (int){ 5 }
+ min: (int){ 5 }
max: (number){ |((int){ 5 }, (number){ >5 }) }
}
+ s2: (#struct){
+ res: (int){ |(*(int){ 0 }, (int){ &(>=0, int) }) }
+ min: (number){ |(*(int){ 1 }, (number){ >0 }) }
+ max: (int){ 5 }
+ }
+ s3: (#struct){
+ res: (int){ |(*(int){ 0 }, (int){ &(>=0, int) }) }
+ min: (int){ 5 }
+ max: (int){ 10 }
+ }
+ es3: (_|_){
+ // [eval]
+ res: (int){ |(*(int){ 0 }, (int){ &(>=0, int) }) }
+ min: (int){ 10 }
+ max: (_|_){
+ // [eval] invalid value 5 (out of bound >10)
+ }
+ }
+ #nonEmptyRange: (#struct){
+ min: (_|_){
+ // [incomplete] incomplete cause disjunction
+ }
+ max: (_|_){
+ // [incomplete] incomplete cause disjunction
+ }
+ }
+ r1: (#struct){
+ min: (int){ 3 }
+ max: (number){ >3 }
+ }
+ r2: (#struct){
+ min: (int){ |(*(int){ 1 }, (int){ &(<5, int) }) }
+ max: (int){ 5 }
+ }
+ r3: (#struct){
+ min: (int){ 3 }
+ max: (int){ 6 }
+ }
+ er3: (_|_){
+ // [eval]
+ min: (_|_){
+ // [eval] invalid value 5 (out of bound <5)
+ }
+ max: (_|_){
+ // [eval] invalid value 5 (out of bound <5)
+ }
+ }
}
-- out/compile --
--- in.cue
{
- range1: {
- min: (*1|int)
- range: >〈0;min〉
- range: 8
- }
- range2: {
- min: (*1|int)
- max: (int & >〈0;min〉)
- }
- rg: (〈0;range2〉 & {
- max: 8
- })
#Size: {
res: (&(int, >=0)|*0)
- num: (>〈0;res〉|*(1 + 〈0;res〉))
- max: (>〈0;num〉|*〈0;num〉)
+ min: (>〈0;res〉|*(1 + 〈0;res〉))
+ max: (>〈0;min〉|*〈0;min〉)
}
- a: (〈0;#Size〉 & {
- num: 5
+ s0: (〈0;#Size〉 & {
+ res: 1
+ })
+ s1: (〈0;#Size〉 & {
+ min: 5
+ })
+ s2: (〈0;#Size〉 & {
+ max: 5
+ })
+ s3: (〈0;#Size〉 & {
+ min: 5
+ max: 10
+ })
+ es3: (〈0;#Size〉 & {
+ min: 10
+ max: 5
+ })
+ #nonEmptyRange: {
+ min: (*1|int)
+ min: <〈0;max〉
+ max: >〈0;min〉
+ }
+ r1: (〈0;#nonEmptyRange〉 & {
+ min: 3
+ })
+ r2: (〈0;#nonEmptyRange〉 & {
+ max: 5
+ })
+ r3: (〈0;#nonEmptyRange〉 & {
+ min: 3
+ max: 6
+ })
+ er3: (〈0;#nonEmptyRange〉 & {
+ min: 5
+ max: 5
})
}
diff --git a/cue/testdata/cycle/patterns.txtar b/cue/testdata/cycle/patterns.txtar
new file mode 100644
index 0000000..dd25f14
--- /dev/null
+++ b/cue/testdata/cycle/patterns.txtar
@@ -0,0 +1,48 @@
+Lots of cycle-reference goodness.
+
+-- in.cue --
+{[!~"^[.]"]: c}
+a: b
+b: [string]: int
+c: a: int
+{[string]: c}
+a: b
+b: [string]: int
+c: a: int
+
+-- out/eval --
+(struct){
+ a: (struct){
+ a: (int){ int }
+ }
+ b: (struct){
+ a: (int){ int }
+ }
+ c: (struct){
+ a: (int){ int }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ {
+ [!~"^[.]"]: 〈1;c〉
+ }
+ a: 〈0;b〉
+ b: {
+ [string]: int
+ }
+ c: {
+ a: int
+ }
+ {
+ [string]: 〈1;c〉
+ }
+ a: 〈0;b〉
+ b: {
+ [string]: int
+ }
+ c: {
+ a: int
+ }
+}
diff --git a/cue/testdata/cycle/structural.txtar b/cue/testdata/cycle/structural.txtar
new file mode 100644
index 0000000..32b4d51
--- /dev/null
+++ b/cue/testdata/cycle/structural.txtar
@@ -0,0 +1,1073 @@
+-- in.cue --
+a1: {
+ f: [f]
+}
+
+a2: {
+ f: f
+}
+
+a3: {
+ f: { g: f }
+}
+
+a4: {
+ a: [a|int]
+}
+
+a5: {
+ a: b: a | int
+}
+
+a6: {
+ a: a | int
+}
+
+b1: {
+ b: a & [1]
+ a: [a|int]
+}
+
+b2: {
+ a: [a|int]
+ b: a & [1]
+}
+
+b3: {
+ x: a: [a|int]
+ b: x & {a: [1]}
+}
+
+b4: {
+ b: x.y & [1]
+ x: y: [y]
+}
+
+b5: {
+ b: x.y & {a: [1]}
+ x: y: a: [a|int]
+}
+
+b6: {
+ b: x & {a: [1]}
+ x: a: [a]
+}
+
+// TODO: erroneous: b should be an error. My suspicion is that `a` is detected
+// as a reference cycle, because list don't introduce a new scope, allowing
+// `1` to unify with the equivalent of `a: a` (which normally would be okay).
+b7: {
+ b: a & [[1]]
+ a: [a]
+}
+
+c1: {
+ a: {
+ b: {}
+ c: a & b
+ }
+}
+
+// indirection
+d1: {
+ a: b: c: d: { h: int, t: r }
+ r: a.b
+
+ x: a.b.c
+}
+
+d2: {
+ x: a.b.c
+
+ r: a.b
+ a: b: c: d: { h: int, t: r }
+}
+
+d3: {
+ config: {
+ a: b: c: indirect
+ indirect: [a.b, null][i]
+ i: int | *1
+ }
+ x: config & { i: 0 }
+}
+
+
+// combining structural with reference cycles
+e1: {
+ a: a
+ a: c: a
+
+ b: c: b
+ b: b
+}
+
+e2: {
+ a: {a}
+ a: c: a
+
+ b: c: b
+ b: {b}
+}
+
+e3: {
+ a: [a]
+ a: c: a
+
+ b: [b]
+ b: c: b
+}
+
+e4: {
+ a: [a | {}]
+ a: [[{c: 1}]]
+
+ b: [[{c: 1}]]
+ b: [b | {}]
+}
+
+
+e5: {
+ a: c: a | int
+ a: a | int
+
+ b: b | int
+ b: c: b | int
+}
+
+
+// validating values
+v1: {
+ x: [x | int, 1]
+ y: x & [[[2], 1], 1]
+}
+
+v2: {
+ y: x & [[[2], 1], 1]
+ x: [x | int, 1]
+}
+
+v3: {
+ list: {
+ head: int
+ tail: list | null
+ }
+
+ myList: list
+ myList: {
+ head: 2
+ tail: {
+ head: 3
+ tail: {
+ head: 4
+ }
+ }
+ }
+}
+
+v4: {
+ list: {
+ head: int
+ tail: list | 1
+ }
+
+ myList: list
+ myList: {
+ head: 2
+ tail: head: 3
+ }
+}
+
+v5: {
+ list: {
+ head: int
+ tail: list | {}
+ }
+
+ myList: list
+ myList: {
+ head: 2
+ tail: head: 3
+ }
+}
+
+
+
+// Example from "The Logic of Type Feature Structures" (Bob Carpenter)/
+z1: {
+ y: {
+ f: h: g
+ g: _
+ }
+ x: {
+ f: _
+ g: f
+ }
+ z: x & y
+}
+
+
+// Ensure these are NOT treated as structural errors.
+
+n1: a: b: int
+n2: n1 & { a: n1 }
+n3: n1 & { n1 }
+n4: n1 & { x: n1 & { y: n1 & { z: int }}}
+
+
+-- out/eval --
+Errors:
+conflicting types
+conflicting types list and struct
+structural cycle
+
+Result:
+(_|_){
+ // [eval]
+ a1: (_|_){
+ // [structural cycle]
+ f: (_|_){
+ // [structural cycle]
+ 0: (_|_){
+ // [structural cycle] structural cycle
+ 0: (_|_){// 〈0;f〉
+ }
+ }
+ }
+ }
+ a2: (struct){
+ f: (_){ _ }
+ }
+ a3: (_|_){
+ // [structural cycle]
+ f: (_|_){
+ // [structural cycle]
+ g: (_|_){
+ // [structural cycle] structural cycle
+ g: (_|_){// 〈1;f〉
+ }
+ }
+ }
+ }
+ a4: (struct){
+ a: (#list){
+ 0: (int){ int }
+ }
+ }
+ a5: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ }
+ a6: (struct){
+ a: (_){ |((_){ _ }, (int){ int }) }
+ }
+ b1: (struct){
+ b: (#list){
+ 0: (int){ 1 }
+ }
+ a: (#list){
+ 0: (int){ int }
+ }
+ }
+ b2: (struct){
+ a: (#list){
+ 0: (int){ int }
+ }
+ b: (#list){
+ 0: (int){ 1 }
+ }
+ }
+ b3: (struct){
+ x: (struct){
+ a: (#list){
+ 0: (int){ int }
+ }
+ }
+ b: (struct){
+ a: (#list){
+ 0: (int){ 1 }
+ }
+ }
+ }
+ b4: (_|_){
+ // [structural cycle]
+ b: (_|_){
+ // [structural cycle]
+ 0: (int){ 1 }
+ }
+ x: (_|_){
+ // [structural cycle]
+ y: (_|_){
+ // [structural cycle]
+ 0: (_|_){
+ // [structural cycle] structural cycle
+ 0: (_|_){// 〈0;y〉
+ }
+ }
+ }
+ }
+ }
+ b5: (struct){
+ b: (struct){
+ a: (#list){
+ 0: (int){ 1 }
+ }
+ }
+ x: (struct){
+ y: (struct){
+ a: (#list){
+ 0: (int){ int }
+ }
+ }
+ }
+ }
+ b6: (_|_){
+ // [eval]
+ b: (_|_){
+ // [eval]
+ a: (_|_){
+ // [eval]
+ 0: (_|_){
+ // [eval] conflicting types
+ 0: (_|_){
+ // [structural cycle] structural cycle
+ }
+ }
+ }
+ }
+ x: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle]
+ 0: (_|_){
+ // [structural cycle] structural cycle
+ 0: (_|_){// 〈0;a〉
+ }
+ }
+ }
+ }
+ }
+ b7: (_|_){
+ // [structural cycle]
+ b: (#list){
+ 0: (#list){
+ 0: (int){ 1 }
+ }
+ }
+ a: (_|_){
+ // [structural cycle]
+ 0: (_|_){
+ // [structural cycle] structural cycle
+ 0: (_|_){// 〈0;a〉
+ }
+ }
+ }
+ }
+ c1: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle]
+ b: (struct){
+ }
+ c: (_|_){
+ // [structural cycle]
+ b: (struct){
+ }
+ c: (_|_){
+ // [structural cycle] structural cycle
+ b: (_|_){// {}
+ }
+ c: (_|_){// (〈1;a〉 & 〈0;b〉)
+ }
+ }
+ }
+ }
+ }
+ d1: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle]
+ b: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle]
+ d: (_|_){
+ // [structural cycle]
+ h: (int){ int }
+ t: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// {
+ // d: {
+ // h: int
+ // t: 〈4;r〉
+ // }
+ // }
+ }
+ }
+ }
+ }
+ }
+ }
+ r: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// {
+ // d: {
+ // h: int
+ // t: 〈4;r〉
+ // }
+ // }
+ }
+ }
+ x: (_|_){
+ // [structural cycle]
+ }
+ }
+ d2: (_|_){
+ // [structural cycle]
+ x: (_|_){
+ // [structural cycle]
+ }
+ r: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// {
+ // d: {
+ // h: int
+ // t: 〈4;r〉
+ // }
+ // }
+ }
+ }
+ a: (_|_){
+ // [structural cycle]
+ b: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle]
+ d: (_|_){
+ // [structural cycle]
+ h: (int){ int }
+ t: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// {
+ // d: {
+ // h: int
+ // t: 〈4;r〉
+ // }
+ // }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ d3: (_|_){
+ // [structural cycle]
+ config: (struct){
+ a: (struct){
+ b: (struct){
+ c: (null){ null }
+ }
+ }
+ indirect: (null){ null }
+ i: (int){ 1 }
+ }
+ x: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle]
+ b: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// 〈2;indirect〉
+ }
+ }
+ }
+ }
+ indirect: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// 〈2;indirect〉
+ }
+ }
+ i: (int){ 0 }
+ }
+ }
+ e1: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// 〈1;a〉
+ }
+ }
+ }
+ b: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// 〈1;b〉
+ }
+ }
+ }
+ }
+ e2: (_|_){
+ // [structural cycle]
+ a: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// 〈1;a〉
+ }
+ }
+ }
+ b: (_|_){
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle] structural cycle
+ c: (_|_){// 〈1;b〉
+ }
+ }
+ }
+ }
+ e3: (_|_){
+ // [eval]
+ a: (_|_){
+ // [eval] conflicting types list and struct
+ c: (_|_){
+ // [eval] conflicting types list and struct
+ // structural cycle
+ c: (_|_){// 〈1;a〉
+ }
+ 0: (_|_){// 〈0;a〉
+ }
+ }
+ 0: (_|_){
+ // [eval] conflicting types list and struct
+ // structural cycle
+ c: (_|_){// 〈1;a〉
+ }
+ 0: (_|_){// 〈0;a〉
+ }
+ }
+ }
+ b: (_|_){
+ // [eval] conflicting types list and struct
+ c: (_|_){
+ // [eval] conflicting types list and struct
+ // structural cycle
+ c: (_|_){// 〈1;b〉
+ }
+ 0: (_|_){// 〈0;b〉
+ }
+ }
+ 0: (_|_){
+ // [eval] conflicting types list and struct
+ // structural cycle
+ c: (_|_){// 〈1;b〉
+ }
+ 0: (_|_){// 〈0;b〉
+ }
+ }
+ }
+ }
+ e4: (struct){
+ a: (#list){
+ 0: (#list){
+ 0: (struct){
+ c: (int){ 1 }
+ }
+ }
+ }
+ b: (#list){
+ 0: (#list){
+ 0: (struct){
+ c: (int){ 1 }
+ }
+ }
+ }
+ }
+ e5: (struct){
+ a: (struct){
+ c: (int){ int }
+ }
+ b: (struct){
+ c: (int){ int }
+ }
+ }
+ v1: (struct){
+ x: (#list){
+ 0: (int){ int }
+ 1: (int){ 1 }
+ }
+ y: (#list){
+ 0: (#list){
+ 0: (#list){
+ 0: (int){ 2 }
+ }
+ 1: (int){ 1 }
+ }
+ 1: (int){ 1 }
+ }
+ }
+ v2: (struct){
+ y: (#list){
+ 0: (#list){
+ 0: (#list){
+ 0: (int){ 2 }
+ }
+ 1: (int){ 1 }
+ }
+ 1: (int){ 1 }
+ }
+ x: (#list){
+ 0: (int){ int }
+ 1: (int){ 1 }
+ }
+ }
+ v3: (struct){
+ list: (struct){
+ head: (int){ int }
+ tail: (null){ null }
+ }
+ myList: (struct){
+ head: (int){ 2 }
+ tail: (struct){
+ head: (int){ 3 }
+ tail: (struct){
+ head: (int){ 4 }
+ tail: (null){ null }
+ }
+ }
+ }
+ }
+ v4: (struct){
+ list: (struct){
+ head: (int){ int }
+ tail: (int){ 1 }
+ }
+ myList: (struct){
+ head: (int){ 2 }
+ tail: (struct){
+ head: (int){ 3 }
+ tail: (int){ 1 }
+ }
+ }
+ }
+ v5: (struct){
+ list: (struct){
+ head: (int){ int }
+ tail: (struct){
+ }
+ }
+ myList: (struct){
+ head: (int){ 2 }
+ tail: (struct){ |((struct){
+ head: (int){ 3 }
+ tail: (struct){
+ }
+ }, (struct){
+ head: (int){ 3 }
+ }) }
+ }
+ }
+ z1: (_|_){
+ // [structural cycle]
+ y: (struct){
+ f: (struct){
+ h: (_){ _ }
+ }
+ g: (_){ _ }
+ }
+ x: (struct){
+ f: (_){ _ }
+ g: (_){ _ }
+ }
+ z: (_|_){
+ // [structural cycle]
+ f: (_|_){
+ // [structural cycle]
+ h: (_|_){
+ // [structural cycle]
+ h: (_|_){
+ // [structural cycle] structural cycle
+ h: (_|_){// 〈1;g〉
+ }
+ }
+ }
+ }
+ g: (_|_){
+ // [structural cycle]
+ h: (_|_){
+ // [structural cycle] structural cycle
+ h: (_|_){// 〈1;g〉
+ }
+ }
+ }
+ }
+ }
+ n1: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ }
+ n2: (struct){
+ a: (struct){
+ b: (int){ int }
+ a: (struct){
+ b: (int){ int }
+ }
+ }
+ }
+ n3: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ }
+ n4: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ x: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ y: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ z: (int){ int }
+ }
+ }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ a1: {
+ f: [
+ 〈0;f〉,
+ ]
+ }
+ a2: {
+ f: 〈0;f〉
+ }
+ a3: {
+ f: {
+ g: 〈1;f〉
+ }
+ }
+ a4: {
+ a: [
+ (〈0;a〉|int),
+ ]
+ }
+ a5: {
+ a: {
+ b: (〈1;a〉|int)
+ }
+ }
+ a6: {
+ a: (〈0;a〉|int)
+ }
+ b1: {
+ b: (〈0;a〉 & [
+ 1,
+ ])
+ a: [
+ (〈0;a〉|int),
+ ]
+ }
+ b2: {
+ a: [
+ (〈0;a〉|int),
+ ]
+ b: (〈0;a〉 & [
+ 1,
+ ])
+ }
+ b3: {
+ x: {
+ a: [
+ (〈0;a〉|int),
+ ]
+ }
+ b: (〈0;x〉 & {
+ a: [
+ 1,
+ ]
+ })
+ }
+ b4: {
+ b: (〈0;x〉.y & [
+ 1,
+ ])
+ x: {
+ y: [
+ 〈0;y〉,
+ ]
+ }
+ }
+ b5: {
+ b: (〈0;x〉.y & {
+ a: [
+ 1,
+ ]
+ })
+ x: {
+ y: {
+ a: [
+ (〈0;a〉|int),
+ ]
+ }
+ }
+ }
+ b6: {
+ b: (〈0;x〉 & {
+ a: [
+ 1,
+ ]
+ })
+ x: {
+ a: [
+ 〈0;a〉,
+ ]
+ }
+ }
+ b7: {
+ b: (〈0;a〉 & [
+ [
+ 1,
+ ],
+ ])
+ a: [
+ 〈0;a〉,
+ ]
+ }
+ c1: {
+ a: {
+ b: {}
+ c: (〈1;a〉 & 〈0;b〉)
+ }
+ }
+ d1: {
+ a: {
+ b: {
+ c: {
+ d: {
+ h: int
+ t: 〈4;r〉
+ }
+ }
+ }
+ }
+ r: 〈0;a〉.b
+ x: 〈0;a〉.b.c
+ }
+ d2: {
+ x: 〈0;a〉.b.c
+ r: 〈0;a〉.b
+ a: {
+ b: {
+ c: {
+ d: {
+ h: int
+ t: 〈4;r〉
+ }
+ }
+ }
+ }
+ }
+ d3: {
+ config: {
+ a: {
+ b: {
+ c: 〈2;indirect〉
+ }
+ }
+ indirect: [
+ 〈0;a〉.b,
+ null,
+ ][〈0;i〉]
+ i: (int|*1)
+ }
+ x: (〈0;config〉 & {
+ i: 0
+ })
+ }
+ e1: {
+ a: 〈0;a〉
+ a: {
+ c: 〈1;a〉
+ }
+ b: {
+ c: 〈1;b〉
+ }
+ b: 〈0;b〉
+ }
+ e2: {
+ a: {
+ 〈1;a〉
+ }
+ a: {
+ c: 〈1;a〉
+ }
+ b: {
+ c: 〈1;b〉
+ }
+ b: {
+ 〈1;b〉
+ }
+ }
+ e3: {
+ a: [
+ 〈0;a〉,
+ ]
+ a: {
+ c: 〈1;a〉
+ }
+ b: [
+ 〈0;b〉,
+ ]
+ b: {
+ c: 〈1;b〉
+ }
+ }
+ e4: {
+ a: [
+ (〈0;a〉|{}),
+ ]
+ a: [
+ [
+ {
+ c: 1
+ },
+ ],
+ ]
+ b: [
+ [
+ {
+ c: 1
+ },
+ ],
+ ]
+ b: [
+ (〈0;b〉|{}),
+ ]
+ }
+ e5: {
+ a: {
+ c: (〈1;a〉|int)
+ }
+ a: (〈0;a〉|int)
+ b: (〈0;b〉|int)
+ b: {
+ c: (〈1;b〉|int)
+ }
+ }
+ v1: {
+ x: [
+ (〈0;x〉|int),
+ 1,
+ ]
+ y: (〈0;x〉 & [
+ [
+ [
+ 2,
+ ],
+ 1,
+ ],
+ 1,
+ ])
+ }
+ v2: {
+ y: (〈0;x〉 & [
+ [
+ [
+ 2,
+ ],
+ 1,
+ ],
+ 1,
+ ])
+ x: [
+ (〈0;x〉|int),
+ 1,
+ ]
+ }
+ v3: {
+ list: {
+ head: int
+ tail: (〈1;list〉|null)
+ }
+ myList: 〈0;list〉
+ myList: {
+ head: 2
+ tail: {
+ head: 3
+ tail: {
+ head: 4
+ }
+ }
+ }
+ }
+ v4: {
+ list: {
+ head: int
+ tail: (〈1;list〉|1)
+ }
+ myList: 〈0;list〉
+ myList: {
+ head: 2
+ tail: {
+ head: 3
+ }
+ }
+ }
+ v5: {
+ list: {
+ head: int
+ tail: (〈1;list〉|{})
+ }
+ myList: 〈0;list〉
+ myList: {
+ head: 2
+ tail: {
+ head: 3
+ }
+ }
+ }
+ z1: {
+ y: {
+ f: {
+ h: 〈1;g〉
+ }
+ g: _
+ }
+ x: {
+ f: _
+ g: 〈0;f〉
+ }
+ z: (〈0;x〉 & 〈0;y〉)
+ }
+ n1: {
+ a: {
+ b: int
+ }
+ }
+ n2: (〈0;n1〉 & {
+ a: 〈1;n1〉
+ })
+ n3: (〈0;n1〉 & {
+ 〈1;n1〉
+ })
+ n4: (〈0;n1〉 & {
+ x: (〈1;n1〉 & {
+ y: (〈2;n1〉 & {
+ z: int
+ })
+ })
+ })
+}
diff --git "a/cue/testdata/definitions/033_Issue_\043153.txtar" "b/cue/testdata/definitions/033_Issue_\043153.txtar"
index 175494e..ddb37ff 100644
--- "a/cue/testdata/definitions/033_Issue_\043153.txtar"
+++ "b/cue/testdata/definitions/033_Issue_\043153.txtar"
@@ -79,7 +79,7 @@
listOfCloseds: (list){
}
}
- #Closed: (#struct){
+ #Closed: (struct){
a: (int){ |(*(int){ 0 }, (int){ int }) }
}
Junk: (struct){
diff --git a/cue/testdata/export/027.txtar b/cue/testdata/export/027.txtar
index fe2954c..7525d1d 100644
--- a/cue/testdata/export/027.txtar
+++ b/cue/testdata/export/027.txtar
@@ -1,5 +1,9 @@
# DO NOT EDIT; generated by go run testdata/gen.go
#
+
+TODO: Should #Bar result in string or #Foo | string?
+
+
raw: true
eval: true
-- in.cue --
@@ -27,3 +31,9 @@
}
}
}
+-- out/eval --
+(struct){
+ #Foo: (#struct){
+ #Bar: (string){ string }
+ }
+}
diff --git a/cue/testdata/export/028.txtar b/cue/testdata/export/028.txtar
index 5a7a661..70e40f3 100644
--- a/cue/testdata/export/028.txtar
+++ b/cue/testdata/export/028.txtar
@@ -38,3 +38,15 @@
]
}
}
+-- out/eval --
+(struct){
+ #FindInMap: (#struct){
+ #: (#struct){
+ "Fn::FindInMap": (#list){
+ 0: (string){ string }
+ }
+ }
+ }
+ a: (list){
+ }
+}
diff --git a/cue/testdata/export/030.txtar b/cue/testdata/export/030.txtar
index 834a1b7..03e96f0 100644
--- a/cue/testdata/export/030.txtar
+++ b/cue/testdata/export/030.txtar
@@ -53,3 +53,20 @@
#Bar: string
}
}
+-- out/eval --
+(struct){
+ #Foo: (#struct){
+ sgl: (string){ string }
+ ref: ((null|struct)){ |((null){ null }, (#struct){
+ sgl: (string){ string }
+ ref: (null){ null }
+ ext: ((null|string)){ |((string){ string }, (null){ null }) }
+ ref2: ((null|string)){ |((null){ null }, (string){ string }) }
+ "#Foo": (int){ 2 }
+ }) }
+ ext: ((null|string)){ |((string){ string }, (null){ null }) }
+ ref2: ((null|string)){ |((null){ null }, (string){ string }) }
+ "#Foo": (int){ 2 }
+ }
+ #Bar: (string){ string }
+}
diff --git a/internal/core/adt/composite.go b/internal/core/adt/composite.go
index d7c51ca..5e2f611 100644
--- a/internal/core/adt/composite.go
+++ b/internal/core/adt/composite.go
@@ -22,6 +22,61 @@
"cuelang.org/go/cue/token"
)
+// TODO: unanswered questions about structural cycles:
+//
+// 1. When detecting a structural cycle, should we consider this as:
+// a) an unevaluated value,
+// b) an incomplete error (which does not affect parent validity), or
+// c) a special value.
+//
+// Making it an error is the simplest way to ensure reentrancy is disallowed:
+// without an error it would require an additional mechanism to stop reentrancy
+// from continuing to process. Even worse, in some cases it may only partially
+// evaluate, resulting in unexpected results. For this reason, we are taking
+// approach `b` for now.
+//
+// This has some consequences of how disjunctions are treated though. Consider
+//
+// list: {
+// head: _
+// tail: list | null
+// }
+//
+// When making it an error, evaluating the above will result in
+//
+// list: {
+// head: _
+// tail: null
+// }
+//
+// because list will result in a structural cycle, and thus an error, it will be
+// stripped from the disjunction. This may or may not be a desirable property. A
+// nice thing is that it is not required to write `list | *null`. A disadvantage
+// is that this is perhaps somewhat inexplicit.
+//
+// When not making it an error (and simply cease evaluating child arcs upon
+// cycle detection), the result would be:
+//
+// list: {
+// head: _
+// tail: list | null
+// }
+//
+// In other words, an evaluation would result in a cycle and thus an error.
+// Implementations can recognize such cases by having unevaluated arcs. An
+// explicit structure cycle marker would probably be less error prone.
+//
+// Note that in both cases, a reference to list will still use the original
+// conjuncts, so the result will be the same for either method in this case.
+//
+//
+// 2. Structural cycle allowance.
+//
+// Structural cycle detection disallows reentrancy as well. This means one
+// cannot use structs for recursive computation. This will probably preclude
+// evaluation of some configuration. Given that there is no real alternative
+// yet, we could allow structural cycle detection to be optionally disabled.
+
// An Environment links the parent scopes for identifier lookup to a composite
// node. Each conjunct that make up node in the tree can be associated with
// a different environment (although some conjuncts may share an Environment).
@@ -33,10 +88,44 @@
// constraint. It is used to resolve label references.
DynamicLabel Feature
+ // TODO(perf): make the following public fields a shareable struct as it
+ // mostly is going to be the same for child nodes.
+
// CloseID is a unique number that tracks a group of conjuncts that need
// belong to a single originating definition.
CloseID uint32
+ // Cyclic indicates a structural cycle was detected for this conjunct or one
+ // of its ancestors.
+ Cyclic bool
+
+ // Deref keeps track of nodes that should dereference to Vertex. It is used
+ // for detecting structural cycle.
+ //
+ // The detection algorithm is based on Tomabechi's quasi-destructive graph
+ // unification. This detection requires dependencies to be resolved into
+ // fully dereferenced vertices. This is not the case in our algorithm:
+ // the result of evaluating conjuncts is placed into dereferenced vertices
+ // _after_ they are evaluated, but the Environment still points to the
+ // non-dereferenced context.
+ //
+ // In order to be able to detect structural cycles, we need to ensure that
+ // at least one node that is part of a cycle in the context in which
+ // conjunctions are evaluated dereferences correctly.
+ //
+ // The only field necessary to detect a structural cycle, however, is
+ // the Status field of the Vertex. So rather than dereferencing a node
+ // proper, it is sufficient to copy the Status of the dereferenced nodes
+ // to these nodes (will always be EvaluatingArcs).
+ Deref []*Vertex
+
+ // Cycles contains vertices for which cycles are detected. It is used
+ // for tracking self-references within structural cycles.
+ //
+ // Unlike Deref, Cycles is not incremented with child nodes.
+ // TODO: Cycles is always a tail end of Deref, so this can be optimized.
+ Cycles []*Vertex
+
cache map[Expr]Value
}
@@ -71,6 +160,8 @@
// Label is the feature leading to this vertex.
Label Feature
+ // TODO: move the following status fields to a separate struct.
+
// status indicates the evaluation progress of this vertex.
status VertexStatus
@@ -79,6 +170,13 @@
// ignored.
isData bool
+ // EvalCount keeps track of temporary dereferencing during evaluation.
+ // If EvalCount > 0, status should be considered to be EvaluatingArcs.
+ EvalCount int
+
+ // SelfCount is used for tracking self-references.
+ SelfCount int
+
// Value is the value associated with this vertex. For lists and structs
// this is a sentinel value indicating its kind.
Value Value
@@ -140,6 +238,9 @@
)
func (v *Vertex) Status() VertexStatus {
+ if v.EvalCount > 0 {
+ return EvaluatingArcs
+ }
return v.status
}
diff --git a/internal/core/adt/errors.go b/internal/core/adt/errors.go
index 58ddac5..ecfe359 100644
--- a/internal/core/adt/errors.go
+++ b/internal/core/adt/errors.go
@@ -51,6 +51,12 @@
// Mostly used for legacy reasons.
NotExistError
+ // StructuralCycleError means a structural cycle was found. Structural
+ // cycles are permanent errors, but they are not passed up recursively,
+ // as a unification of a value with a structural cycle with one that
+ // doesn't may still give a useful result.
+ StructuralCycleError
+
// IncompleteError means an evaluation could not complete because of
// insufficient information that may still be added later.
IncompleteError
@@ -67,6 +73,8 @@
return "eval"
case UserError:
return "user"
+ case StructuralCycleError:
+ return "structural cycle"
case IncompleteError:
return "incomplete"
case CycleError:
diff --git a/internal/core/eval/eval.go b/internal/core/eval/eval.go
index 596a62d..950f3aa 100644
--- a/internal/core/eval/eval.go
+++ b/internal/core/eval/eval.go
@@ -545,6 +545,8 @@
n.node.Closed = m
}
+ cyclic := n.hasCycle && !n.hasNonCycle
+
// Visit arcs recursively to validate and compute error.
for _, a := range n.node.Arcs {
if updated != nil {
@@ -560,13 +562,24 @@
}
// Call UpdateStatus here to be absolutely sure the status is set
// correctly and that we are not regressing.
- n.node.UpdateStatus(adt.EvaluatingArcs)
- n.eval.Unify(ctx, a, adt.Finalized)
- if err, _ := a.Value.(*adt.Bottom); err != nil {
- n.node.AddChildError(err)
+ if !cyclic {
+ n.node.UpdateStatus(adt.EvaluatingArcs)
+ n.eval.Unify(ctx, a, adt.Finalized)
+ if err, _ := a.Value.(*adt.Bottom); err != nil {
+ n.node.AddChildError(err)
+ }
}
}
+ if cyclic {
+ n.node.Value = adt.CombineErrors(nil, n.node.Value, &adt.Bottom{
+ Code: adt.StructuralCycleError,
+ Err: errors.Newf(token.NoPos, "structural cycle"),
+ Value: n.node.Value,
+ // TODO: probably, this should have the referenced arc.
+ })
+ }
+
n.node.UpdateStatus(adt.Finalized)
}
@@ -682,6 +695,9 @@
vLists []*adt.Vertex
exprs []conjunct
+ hasCycle bool // has conjunct with structural cycle
+ hasNonCycle bool // has conjunct without structural cycle
+
// Disjunction handling
disjunctions []envDisjunct
defaultMode defaultMode
@@ -867,6 +883,23 @@
// Require an Environment.
ctx := n.ctx
+ // TODO: see if we can do without these counters.
+ for _, d := range v.Env.Deref {
+ d.EvalCount++
+ }
+ for _, d := range v.Env.Cycles {
+ d.SelfCount++
+ }
+ defer func() {
+ for _, d := range v.Env.Deref {
+ d.EvalCount--
+ }
+ for _, d := range v.Env.Cycles {
+ d.SelfCount++
+ }
+ }()
+
+outer:
switch x := v.Expr().(type) {
case adt.Resolver:
arc, err := ctx.Resolve(v.Env, x)
@@ -883,30 +916,81 @@
break
}
- // If this is a cycle error, we have reached a fixed point and adding
- // conjuncts at this point will not change the value. Also, continuing
- // to pursue this value will result in an infinite loop.
- //
- // TODO: add a mechanism so that the computation will only have to be
- // one once?
- if isEvaluating(arc) {
- break
+ // Pass detection of structural cycles from parent to children.
+ cyclic := false
+ if v.Env != nil {
+ // If a reference is in a tainted set, so is the value it refers to.
+ cyclic = v.Env.Cyclic
}
- // TODO: detect structural cycles here. A structural cycle can occur
- // if it is not a reference cycle, but refers to a parent. node.
- // This should only be allowed if it is unified with a finite structure.
+ status := arc.Status()
+ for _, d := range v.Env.Deref {
+ if d == arc {
+ status = adt.EvaluatingArcs
+ }
+ }
+
+ switch status {
+ case adt.Evaluating:
+ // Reference cycle detected. We have reached a fixed point and
+ // adding conjuncts at this point will not change the value. Also,
+ // continuing to pursue this value will result in an infinite loop.
+
+ // TODO: add a mechanism so that the computation will only have to
+ // be done once?
+
+ if arc == n.node {
+ // TODO: we could use node sharing here. This may avoid an
+ // exponential blowup during evaluation, like is possible with
+ // YAML.
+ break outer
+ }
+
+ case adt.EvaluatingArcs:
+ // Structural cycle detected. Continue evaluation as usual, but
+ // keep track of whether any other conjuncts without structural
+ // cycles are added. If not, evaluation of child arcs will end
+ // with this node.
+
+ // For the purpose of determining whether at least one non-cyclic
+ // conjuncts exists, we consider all conjuncts of a cyclic conjuncts
+ // also cyclic.
+
+ cyclic = true
+ n.hasCycle = true
+
+ // As the adt.EvaluatingArcs mechanism bypasses the self-reference
+ // mechanism, we need to separately keep track of it here.
+ // If this (originally) is a self-reference node, adding them
+ // will result in recursively adding the same reference. For this
+ // we also mark the node as evaluating.
+ if arc.SelfCount > 0 {
+ break outer
+ }
+
+ // This count is added for values that are directly added below.
+ // The count is handled separately for delayed values.
+ arc.SelfCount++
+ defer func() { arc.SelfCount-- }()
+ }
+
+ // TODO: uncommenting the following almost works, but causes some
+ // faulty results in complex cycle handling between disjunctions.
+ // The reason is that disjunctions must be eliminated if checks in
+ // values on which they depend fail.
+ ctx.Unify(ctx, arc, adt.Finalized)
if arc.Label.IsDef() {
- n.insertClosed(arc)
+ n.insertClosed(arc, cyclic, arc)
} else {
for _, a := range arc.Conjuncts {
- n.addExprConjunct(a, closeID, top)
+ n.addExprConjunct(updateCyclic(a, cyclic, arc), closeID, top)
}
}
case adt.Evaluator:
// adt.Interpolation, adt.UnaryExpr, adt.BinaryExpr, adt.CallExpr
+ // Could be unify?
val, complete := ctx.Evaluate(v.Env, v.Expr())
if !complete {
n.exprs = append(n.exprs, conjunct{v, closeID, top})
@@ -933,7 +1017,40 @@
}
}
-func (n *nodeContext) insertClosed(arc *adt.Vertex) {
+// updateCyclicStatus looks for proof of non-cyclic conjuncts to override
+// 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 {
+ env := c.Env
+ switch {
+ case env == nil:
+ if !cyclic && deref == nil {
+ return c
+ }
+ env = &adt.Environment{Cyclic: cyclic}
+ case deref == nil && env.Cyclic == cyclic:
+ return c
+ default:
+ // The conjunct may still be in use in other fields, so we should
+ // make a new copy to mark Cyclic only for this case.
+ e := *env
+ e.Cyclic = e.Cyclic || cyclic
+ env = &e
+ }
+ if deref != nil {
+ env.Deref = append(env.Deref, deref)
+ env.Cycles = append(env.Cycles, deref)
+ }
+ return adt.MakeConjunct(env, c.Expr())
+}
+
+func (n *nodeContext) insertClosed(arc *adt.Vertex, cyclic bool, deref *adt.Vertex) {
id := n.eval.nextID()
n.needClose = true
@@ -941,7 +1058,7 @@
n.newClose = nil
for _, a := range arc.Conjuncts {
- n.addExprConjunct(a, id, false)
+ n.addExprConjunct(updateCyclic(a, cyclic, deref), id, false)
}
current, n.newClose = n.newClose, current
@@ -953,6 +1070,8 @@
}
func (n *nodeContext) addValueConjunct(env *adt.Environment, v adt.Value) {
+ n.updateCyclicStatus(env)
+
if x, ok := v.(*adt.Vertex); ok {
needClose := false
if isStruct(x) {
@@ -969,13 +1088,14 @@
n.node.AddStructs(x.Structs...)
}
- if len(x.Conjuncts) > 0 {
+ if !x.IsData() && len(x.Conjuncts) > 0 {
+ cyclic := env != nil && env.Cyclic
if needClose {
- n.insertClosed(x)
+ n.insertClosed(x, cyclic, nil)
return
}
for _, c := range x.Conjuncts {
- n.addExprConjunct(c, 0, false) // Pass from eval
+ n.addExprConjunct(updateCyclic(c, cyclic, nil), 0, false) // TODO: Pass from eval
}
return
}
@@ -1112,6 +1232,8 @@
newDef uint32,
top bool) {
+ n.updateCyclicStatus(env) // to handle empty structs.
+
ctx := n.ctx
n.node.AddStructs(s)
@@ -1138,6 +1260,10 @@
Vertex: n.node,
CloseID: closeID,
}
+ if env != nil {
+ childEnv.Cyclic = env.Cyclic
+ childEnv.Deref = env.Deref
+ }
var hasOther, hasBulk adt.Node
@@ -1422,6 +1548,8 @@
outer:
for i, l := range n.lists {
+ n.updateCyclicStatus(l.env)
+
index := int64(0)
hasComprehension := false
for j, elem := range l.list.Elems {
diff --git a/internal/core/eval/eval_test.go b/internal/core/eval/eval_test.go
index 604def6..96197b1 100644
--- a/internal/core/eval/eval_test.go
+++ b/internal/core/eval/eval_test.go
@@ -17,6 +17,7 @@
import (
"flag"
"fmt"
+ "strings"
"testing"
"cuelang.org/go/internal/core/debug"
@@ -24,7 +25,6 @@
"cuelang.org/go/internal/core/validate"
"cuelang.org/go/internal/cuetxtar"
"cuelang.org/go/internal/legacy/cue"
- "cuelang.org/go/pkg/strings"
"github.com/rogpeppe/go-internal/txtar"
)
@@ -85,12 +85,7 @@
}
var needFix = map[string]string{
- "export/027": "cycle",
- "export/028": "cycle",
- "export/030": "cycle",
-
- "cycle/025_cannot_resolve_references_that_would_be_ambiguous": "cycle",
- "compile/scope": "cycle",
+ "DIR/NAME": "reason",
}
// TestX is for debugging. Do not delete.
