internal/core/adt: more fixes to cycle handling
Note that this also fixes some regressions from v0.2.2:
cue/testdata/fulleval/046_non-structural_direct_cycles.txtar:
c1: was a cycle erorr whereas it really was correct
c2: reported a cycle error, whereas it really was a permanent conflict
This test was ported from v0.2.2 and its v0.2.2. results can be found
in the sections out/legacy-debug and out/def.
Also note that this reverts some of the "fixes" made in Issue #667:
although most reported cycle mis-handling, there were some
other cycles that got inadvertently resolved. Most notably,
to resolve checking the existence of fields, a Vertex needs to
be evaluated to a certain state before a conclusive decision
can be made. If two fields mutually depend on reaching such
a state it cannot be determined. The file
cue/testdata/cycle/compbottomnofinal.txtar
describes the essence of this. This is arguably a type of
reference cycle, but maybe this should be considered a
different kind of cycle.
Fixes #695
The solution traces references that are used in
nonMonotonic situations (compare against bottom)
and compares the against other evaluation results,
setting traps for conflicts.
This is likely not covering all cases. A true fix to
this issue would require a more recursive evaluation.
This is planned, but will not be done for now.
Change-Id: I0d98cf60eb7757daa9ceda99fcfd01757203b3b7
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/8441
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Paul Jolly <paul@myitcv.org.uk>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/builtins/incomplete.txtar b/cue/testdata/builtins/incomplete.txtar
index f8d346f..20a2703 100644
--- a/cue/testdata/builtins/incomplete.txtar
+++ b/cue/testdata/builtins/incomplete.txtar
@@ -45,26 +45,26 @@
list1: (struct){
Out1: (#list){
0: (_|_){
- // [incomplete] list1._Sub: undefined field b:
- // ./in.cue:16:13
+ // [cycle] cycle error:
+ // ./in.cue:13:23
}
}
Out2: (#list){
0: (_|_){
- // [incomplete] list1._Sub: undefined field b:
- // ./in.cue:16:13
+ // [cycle] cycle error:
+ // ./in.cue:13:23
}
}
Out3: (#list){
0: (_|_){
- // [incomplete] list1._Sub: undefined field b:
- // ./in.cue:16:13
+ // [cycle] cycle error:
+ // ./in.cue:13:23
}
}
Top: (#list){
0: (_|_){
- // [incomplete] list1._Sub: undefined field b:
- // ./in.cue:16:13
+ // [cycle] cycle error:
+ // ./in.cue:13:23
}
}
_Sub: (_|_){
@@ -76,20 +76,20 @@
}
list2: (struct){
Out1: (_|_){
- // [incomplete] list2.#Sub: undefined field b:
- // ./in.cue:30:13
+ // [cycle] cycle error:
+ // ./in.cue:27:21
}
Out2: (_|_){
- // [incomplete] list2.#Sub: undefined field b:
- // ./in.cue:30:13
+ // [cycle] cycle error:
+ // ./in.cue:27:21
}
Out3: (_|_){
- // [incomplete] list2.#Sub: undefined field b:
- // ./in.cue:30:13
+ // [cycle] cycle error:
+ // ./in.cue:27:21
}
_Top: (_|_){
- // [incomplete] list2.#Sub: undefined field b:
- // ./in.cue:30:13
+ // [cycle] cycle error:
+ // ./in.cue:27:21
}
#Sub: (_|_){
// [incomplete] list2.#Sub: undefined field b:
diff --git a/cue/testdata/cycle/compbottom.txtar b/cue/testdata/cycle/compbottom.txtar
index 1daa0f4..f55529e 100644
--- a/cue/testdata/cycle/compbottom.txtar
+++ b/cue/testdata/cycle/compbottom.txtar
@@ -1,3 +1,5 @@
+// Issues: #667, #695, #622
+
// Comparing against bottom is not officially supported by the spec.
// In practice it is used for a variety of purposes.
//
@@ -26,10 +28,7 @@
// evaluation.
-- in.cue --
-import (
- "strconv"
- "regexp"
-)
+import "regexp"
simple: {
#message: #"^(message: (?P<message>.*))?$"#
@@ -76,6 +75,51 @@
}
Y: regexp.FindNamedSubmatch(#message, X)
+ X: "message: hello"
+ X: #aux.message
+ }
+
+ p4: {
+ X: #aux.message
+ #aux: {
+ if Y.message == _|_ {
+ message: ""
+ }
+ if Y.message != _|_ {
+ message: "message: " + Y.message
+ }
+ }
+
+ Y: regexp.FindNamedSubmatch(#message, X)
+ X: "message: hello"
+ }
+
+ p5: {
+ #aux: {
+ if Y.message == _|_ {
+ message: ""
+ }
+ if Y.message != _|_ {
+ message: "message: " + Y.message
+ }
+ }
+
+ X: #aux.message
+ Y: regexp.FindNamedSubmatch(#message, X)
+ X: "message: hello"
+ }
+
+ p6: {
+ #aux: {
+ if Y.message == _|_ {
+ message: ""
+ }
+ if Y.message != _|_ {
+ message: "message: " + Y.message
+ }
+ }
+
+ Y: regexp.FindNamedSubmatch(#message, X)
X: #aux.message
X: "message: hello"
}
@@ -105,7 +149,7 @@
Y: {
if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo + "v"
+ userinfo: #Y.userinfo
}
host: #Y.host
@@ -135,7 +179,7 @@
Y: {
if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo + "v"
+ userinfo: #Y.userinfo
}
host: #Y.host
@@ -165,7 +209,7 @@
Y: {
if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo + "v"
+ userinfo: #Y.userinfo
}
host: #Y.host
@@ -190,7 +234,7 @@
Y: {
if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo + "v"
+ userinfo: #Y.userinfo
}
host: #Y.host
@@ -204,174 +248,6 @@
}
}
}
-
-large: {
- #userHostPort: #"^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)(:(?P<port>\d+))?$"#
-
- p1: {
- Y: {
- userinfo: "user"
- host: "example.com"
- }
-
- X: #X.userinfo + #X.host + #X.port
-
- #X: {
- if Y.userinfo == _|_ {
- userinfo: ""
- }
- if Y.userinfo != _|_ {
- userinfo: Y.userinfo + "@"
- }
-
- host: Y.host
-
- if Y.port == _|_ {
- port: ""
- }
- if Y.port != _|_ {
- port: ":" + strconv.FormatInt(Y.port, 10)
- }
- }
-
- Y: {
- if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo
- }
-
- host: #Y.host
-
- if #Y.port != _|_ {
- port: strconv.Atoi(#Y.port)
- }
- }
-
- #Y: regexp.FindNamedSubmatch(#userHostPort, X)
- }
-
- p2: {
- X: #X.userinfo + #X.host + #X.port
-
- Y: {
- userinfo: "user"
- host: "example.com"
- }
-
- #X: {
- if Y.userinfo == _|_ {
- userinfo: ""
- }
- if Y.userinfo != _|_ {
- userinfo: Y.userinfo + "@"
- }
-
- host: Y.host
-
- if Y.port == _|_ {
- port: ""
- }
- if Y.port != _|_ {
- port: ":" + strconv.FormatInt(Y.port, 10)
- }
- }
-
- Y: {
- if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo
- }
-
- host: #Y.host
-
- if #Y.port != _|_ {
- port: strconv.Atoi(#Y.port)
- }
- }
-
- #Y: regexp.FindNamedSubmatch(#userHostPort, X)
- }
-
- p3: {
- X: #X.userinfo + #X.host + #X.port
-
- #X: {
- if Y.userinfo == _|_ {
- userinfo: ""
- }
- if Y.userinfo != _|_ {
- userinfo: Y.userinfo + "@"
- }
-
- host: Y.host
-
- if Y.port == _|_ {
- port: ""
- }
- if Y.port != _|_ {
- port: ":" + strconv.FormatInt(Y.port, 10)
- }
- }
-
- Y: {
- userinfo: "user"
- host: "example.com"
- }
-
- Y: {
- if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo
- }
-
- host: #Y.host
-
- if #Y.port != _|_ {
- port: strconv.Atoi(#Y.port)
- }
- }
-
- #Y: regexp.FindNamedSubmatch(#userHostPort, X)
- }
-
- p4: {
- X: #X.userinfo + #X.host + #X.port
-
- #X: {
- if Y.userinfo == _|_ {
- userinfo: ""
- }
- if Y.userinfo != _|_ {
- userinfo: Y.userinfo + "@"
- }
-
- host: Y.host
-
- if Y.port == _|_ {
- port: ""
- }
- if Y.port != _|_ {
- port: ":" + strconv.FormatInt(Y.port, 10)
- }
- }
-
- #Y: regexp.FindNamedSubmatch(#userHostPort, X)
-
- Y: {
- userinfo: "user"
- host: "example.com"
- }
-
- Y: {
- if #Y.userinfo != _|_ {
- userinfo: #Y.userinfo
- }
-
- host: #Y.host
-
- if #Y.port != _|_ {
- port: strconv.Atoi(#Y.port)
- }
- }
- }
-}
-- out/eval --
(struct){
simple: (struct){
@@ -403,6 +279,33 @@
}
X: (string){ "message: hello" }
}
+ p4: (struct){
+ X: (string){ "message: hello" }
+ #aux: (#struct){
+ message: (string){ "message: hello" }
+ }
+ Y: (struct){
+ message: (string){ "hello" }
+ }
+ }
+ p5: (struct){
+ #aux: (#struct){
+ message: (string){ "message: hello" }
+ }
+ X: (string){ "message: hello" }
+ Y: (struct){
+ message: (string){ "hello" }
+ }
+ }
+ p6: (struct){
+ #aux: (#struct){
+ message: (string){ "message: hello" }
+ }
+ Y: (struct){
+ message: (string){ "hello" }
+ }
+ X: (string){ "message: hello" }
+ }
}
medium: (struct){
#userHostPort: (string){ "^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)$" }
@@ -467,77 +370,6 @@
}
}
}
- large: (struct){
- #userHostPort: (string){ "^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)(:(?P<port>\\d+))?$" }
- p1: (struct){
- Y: (struct){
- userinfo: (string){ "user" }
- host: (string){ "example.com" }
- }
- X: (string){ "user@example.com" }
- #X: (#struct){
- host: (string){ "example.com" }
- userinfo: (string){ "user@" }
- port: (string){ "" }
- }
- #Y: (#struct){
- host: (string){ "example.com" }
- port: (string){ "" }
- userinfo: (string){ "user" }
- }
- }
- p2: (struct){
- X: (string){ "user@example.com" }
- Y: (struct){
- userinfo: (string){ "user" }
- host: (string){ "example.com" }
- }
- #X: (#struct){
- host: (string){ "example.com" }
- userinfo: (string){ "user@" }
- port: (string){ "" }
- }
- #Y: (#struct){
- host: (string){ "example.com" }
- port: (string){ "" }
- userinfo: (string){ "user" }
- }
- }
- p3: (struct){
- X: (string){ "user@example.com" }
- #X: (#struct){
- host: (string){ "example.com" }
- userinfo: (string){ "user@" }
- port: (string){ "" }
- }
- Y: (struct){
- userinfo: (string){ "user" }
- host: (string){ "example.com" }
- }
- #Y: (#struct){
- host: (string){ "example.com" }
- port: (string){ "" }
- userinfo: (string){ "user" }
- }
- }
- p4: (struct){
- X: (string){ "user@example.com" }
- #X: (#struct){
- host: (string){ "example.com" }
- userinfo: (string){ "user@" }
- port: (string){ "" }
- }
- #Y: (#struct){
- host: (string){ "example.com" }
- port: (string){ "" }
- userinfo: (string){ "user" }
- }
- Y: (struct){
- userinfo: (string){ "user" }
- host: (string){ "example.com" }
- }
- }
- }
}
-- out/compile --
--- in.cue
@@ -580,6 +412,45 @@
}
}
Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#message〉, 〈0;X〉)
+ X: "message: hello"
+ X: 〈0;#aux〉.message
+ }
+ p4: {
+ X: 〈0;#aux〉.message
+ #aux: {
+ if (〈1;Y〉.message == _|_(explicit error (_|_ literal) in source)) {
+ message: ""
+ }
+ if (〈1;Y〉.message != _|_(explicit error (_|_ literal) in source)) {
+ message: ("message: " + 〈2;Y〉.message)
+ }
+ }
+ Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#message〉, 〈0;X〉)
+ X: "message: hello"
+ }
+ p5: {
+ #aux: {
+ if (〈1;Y〉.message == _|_(explicit error (_|_ literal) in source)) {
+ message: ""
+ }
+ if (〈1;Y〉.message != _|_(explicit error (_|_ literal) in source)) {
+ message: ("message: " + 〈2;Y〉.message)
+ }
+ }
+ X: 〈0;#aux〉.message
+ Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#message〉, 〈0;X〉)
+ X: "message: hello"
+ }
+ p6: {
+ #aux: {
+ if (〈1;Y〉.message == _|_(explicit error (_|_ literal) in source)) {
+ message: ""
+ }
+ if (〈1;Y〉.message != _|_(explicit error (_|_ literal) in source)) {
+ message: ("message: " + 〈2;Y〉.message)
+ }
+ }
+ Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#message〉, 〈0;X〉)
X: 〈0;#aux〉.message
X: "message: hello"
}
@@ -603,7 +474,7 @@
}
Y: {
if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;#Y〉.userinfo + "v")
+ userinfo: 〈2;#Y〉.userinfo
}
host: 〈1;#Y〉.host
}
@@ -626,7 +497,7 @@
}
Y: {
if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;#Y〉.userinfo + "v")
+ userinfo: 〈2;#Y〉.userinfo
}
host: 〈1;#Y〉.host
}
@@ -649,7 +520,7 @@
}
Y: {
if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;#Y〉.userinfo + "v")
+ userinfo: 〈2;#Y〉.userinfo
}
host: 〈1;#Y〉.host
}
@@ -668,146 +539,15 @@
}
Y: {
if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;#Y〉.userinfo + "v")
- }
- host: 〈1;#Y〉.host
- }
- #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
- Y: {
- userinfo: "user"
- host: "example.com"
- }
- }
- }
- large: {
- #userHostPort: "^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)(:(?P<port>\\d+))?$"
- p1: {
- Y: {
- userinfo: "user"
- host: "example.com"
- }
- X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
- #X: {
- if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
- userinfo: ""
- }
- if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;Y〉.userinfo + "@")
- }
- host: 〈1;Y〉.host
- if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
- port: ""
- }
- if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
- }
- }
- Y: {
- if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
userinfo: 〈2;#Y〉.userinfo
}
host: 〈1;#Y〉.host
- if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
- }
- }
- #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
- }
- p2: {
- X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
- Y: {
- userinfo: "user"
- host: "example.com"
- }
- #X: {
- if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
- userinfo: ""
- }
- if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;Y〉.userinfo + "@")
- }
- host: 〈1;Y〉.host
- if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
- port: ""
- }
- if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
- }
- }
- Y: {
- if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: 〈2;#Y〉.userinfo
- }
- host: 〈1;#Y〉.host
- if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
- }
- }
- #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
- }
- p3: {
- X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
- #X: {
- if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
- userinfo: ""
- }
- if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;Y〉.userinfo + "@")
- }
- host: 〈1;Y〉.host
- if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
- port: ""
- }
- if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
- }
- }
- Y: {
- userinfo: "user"
- host: "example.com"
- }
- Y: {
- if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: 〈2;#Y〉.userinfo
- }
- host: 〈1;#Y〉.host
- if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
- }
- }
- #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
- }
- p4: {
- X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
- #X: {
- if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
- userinfo: ""
- }
- if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: (〈2;Y〉.userinfo + "@")
- }
- host: 〈1;Y〉.host
- if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
- port: ""
- }
- if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
- }
}
#Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
Y: {
userinfo: "user"
host: "example.com"
}
- Y: {
- if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
- userinfo: 〈2;#Y〉.userinfo
- }
- host: 〈1;#Y〉.host
- if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
- port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
- }
- }
}
}
}
diff --git a/cue/testdata/cycle/compbottom2.txtar b/cue/testdata/cycle/compbottom2.txtar
new file mode 100644
index 0000000..13fc773
--- /dev/null
+++ b/cue/testdata/cycle/compbottom2.txtar
@@ -0,0 +1,511 @@
+-- in.cue --
+
+self: {
+ fail: {
+ a: {
+ if a.b == _|_ {
+ b: 1
+ }
+ }
+ }
+ isConcreteFail: {
+ a: {
+ if a.b == _|_ {
+ b: 1
+ }
+ b: int
+ }
+ }
+ isNotConcrete: {
+ a: {
+ if a.b != _|_ {
+ b: 1
+ }
+ b: int
+ }
+ }
+}
+
+mutual: {
+ noConflicts: {
+ a: { if b.foo == _|_ { new: "" } }
+ b: { if a.bar == _|_ { new: "" } }
+ }
+
+ mutualCycleFail: {
+ b: { if a.bar == _|_ { foo: "" } }
+ a: { if b.foo == _|_ { bar: "" } }
+ }
+
+ brokenCycleSuccess: {
+ a: { if b.foo == _|_ { foo: "" } }
+ b: { if a.bar == _|_ { bar: "" } }
+ a: bar: ""
+ }
+
+ oneDirectionalConflictFail: {
+ p1: {
+ a: { if b.foo == _|_ { bar: "" } }
+ b: { if a.bar == _|_ { new: "" } }
+ }
+ p2: {
+ a: { if b.foo == _|_ { new: "" } }
+ b: { if a.bar == _|_ { foo: "" } }
+ }
+ }
+
+ oneDirectionalBrokenConflictSuccess: {
+ a: { if b.foo == _|_ { bar: "" } }
+ b: { if a.bar == _|_ { new: "" } }
+ b: foo: ""
+ }
+}
+
+sameStruct: {
+ chainSuccess: {
+ raises?: {}
+ if raises == _|_ {
+ ret: a: 1
+ }
+ ret?: {}
+ if ret != _|_ {
+ foo: a: 1
+ }
+ }
+
+ cycleFail: {
+ raises?: {}
+ if raises == _|_ {
+ ret: a: 1
+ }
+ ret?: {}
+ if ret != _|_ {
+ raises: a: 1
+ }
+ }
+
+ defCloseSuccess: {
+ #Example: {
+ raises?: {
+ runtime?: string
+ }
+
+ if raises == _|_ {
+ ret?: _
+ }
+ }
+
+ expr: #Example & {
+ ret: 2
+ }
+ }
+}
+
+// Issue
+nestedChain: {
+ cycleFail: {
+ if #E.x != _|_ {
+ #E: y: true
+ }
+ if #E.y == _|_ {
+ #E: x: true
+ }
+ #E: [_]: bool
+ }
+
+ brokenCycleSuccess: {
+ if #E.x != _|_ {
+ #E: y: true
+ }
+ if #E.y == _|_ {
+ #E: x: true
+ }
+ #E: [_]: bool
+ #E: x: true
+ }
+
+ // TODO: the current algorithm does _not_ handle checking fields that were
+ // not added in certain situations.
+ doubleAddfail: {
+ if #E.x == _|_ {
+ #E: y: true
+ }
+ if #E.y == _|_ {
+ #E: x: true
+ }
+ #E: [_]: bool
+ }
+
+ trippleSuccess: {
+ if #E.x != _|_ {
+ #E: y: true
+ }
+ if #E.y != _|_ {
+ z: true
+ }
+ #E: x: true
+ }
+}
+-- out/eval --
+Errors:
+mutual.mutualCycleFail.a: cycle: new field bar inserted by if clause that was previously evaluated by another if clause
+mutual.oneDirectionalConflictFail.p1.a: cycle: new field bar inserted by if clause that was previously evaluated by another if clause
+mutual.oneDirectionalConflictFail.p2.b: cycle: new field foo inserted by if clause that was previously evaluated by another if clause
+nestedChain.cycleFail.#E: cycle: new field x inserted by if clause that was previously evaluated by another if clause
+sameStruct.cycleFail: cycle: new field raises inserted by if clause that was previously evaluated by another if clause
+self.fail.a: cycle: new field b inserted by if clause that was previously evaluated by another if clause
+
+Result:
+(_|_){
+ // [eval]
+ self: (_|_){
+ // [eval]
+ fail: (_|_){
+ // [eval]
+ a: (_|_){
+ // [eval] self.fail.a: cycle: new field b inserted by if clause that was previously evaluated by another if clause
+ b: (int){ 1 }
+ }
+ }
+ isConcreteFail: (struct){
+ a: (struct){
+ b: (int){ 1 }
+ }
+ }
+ isNotConcrete: (struct){
+ a: (struct){
+ b: (int){ int }
+ }
+ }
+ }
+ mutual: (_|_){
+ // [eval]
+ noConflicts: (struct){
+ a: (struct){
+ new: (string){ "" }
+ }
+ b: (struct){
+ new: (string){ "" }
+ }
+ }
+ mutualCycleFail: (_|_){
+ // [eval]
+ b: (struct){
+ }
+ a: (_|_){
+ // [eval] mutual.mutualCycleFail.a: cycle: new field bar inserted by if clause that was previously evaluated by another if clause
+ bar: (string){ "" }
+ }
+ }
+ brokenCycleSuccess: (struct){
+ a: (struct){
+ bar: (string){ "" }
+ foo: (string){ "" }
+ }
+ b: (struct){
+ }
+ }
+ oneDirectionalConflictFail: (_|_){
+ // [eval]
+ p1: (_|_){
+ // [eval]
+ a: (_|_){
+ // [eval] mutual.oneDirectionalConflictFail.p1.a: cycle: new field bar inserted by if clause that was previously evaluated by another if clause
+ bar: (string){ "" }
+ }
+ b: (struct){
+ new: (string){ "" }
+ }
+ }
+ p2: (_|_){
+ // [eval]
+ a: (struct){
+ }
+ b: (_|_){
+ // [eval] mutual.oneDirectionalConflictFail.p2.b: cycle: new field foo inserted by if clause that was previously evaluated by another if clause
+ foo: (string){ "" }
+ }
+ }
+ }
+ oneDirectionalBrokenConflictSuccess: (struct){
+ a: (struct){
+ }
+ b: (struct){
+ foo: (string){ "" }
+ new: (string){ "" }
+ }
+ }
+ }
+ sameStruct: (_|_){
+ // [eval]
+ chainSuccess: (struct){
+ ret: (struct){
+ a: (int){ 1 }
+ }
+ foo: (struct){
+ a: (int){ 1 }
+ }
+ }
+ cycleFail: (_|_){
+ // [eval] sameStruct.cycleFail: cycle: new field raises inserted by if clause that was previously evaluated by another if clause
+ ret: (struct){
+ a: (int){ 1 }
+ }
+ raises: (struct){
+ a: (int){ 1 }
+ }
+ }
+ defCloseSuccess: (struct){
+ #Example: (#struct){
+ }
+ expr: (#struct){
+ ret: (int){ 2 }
+ }
+ }
+ }
+ nestedChain: (_|_){
+ // [eval]
+ cycleFail: (_|_){
+ // [eval]
+ #E: (_|_){
+ // [eval] nestedChain.cycleFail.#E: cycle: new field x inserted by if clause that was previously evaluated by another if clause
+ x: (bool){ true }
+ }
+ }
+ brokenCycleSuccess: (struct){
+ #E: (#struct){
+ x: (bool){ true }
+ y: (bool){ true }
+ }
+ }
+ doubleAddfail: (struct){
+ #E: (#struct){
+ y: (bool){ true }
+ }
+ }
+ trippleSuccess: (struct){
+ #E: (#struct){
+ x: (bool){ true }
+ y: (bool){ true }
+ }
+ z: (bool){ true }
+ }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ self: {
+ fail: {
+ a: {
+ if (〈1;a〉.b == _|_(explicit error (_|_ literal) in source)) {
+ b: 1
+ }
+ }
+ }
+ isConcreteFail: {
+ a: {
+ if (〈1;a〉.b == _|_(explicit error (_|_ literal) in source)) {
+ b: 1
+ }
+ b: int
+ }
+ }
+ isNotConcrete: {
+ a: {
+ if (〈1;a〉.b != _|_(explicit error (_|_ literal) in source)) {
+ b: 1
+ }
+ b: int
+ }
+ }
+ }
+ mutual: {
+ noConflicts: {
+ a: {
+ if (〈1;b〉.foo == _|_(explicit error (_|_ literal) in source)) {
+ new: ""
+ }
+ }
+ b: {
+ if (〈1;a〉.bar == _|_(explicit error (_|_ literal) in source)) {
+ new: ""
+ }
+ }
+ }
+ mutualCycleFail: {
+ b: {
+ if (〈1;a〉.bar == _|_(explicit error (_|_ literal) in source)) {
+ foo: ""
+ }
+ }
+ a: {
+ if (〈1;b〉.foo == _|_(explicit error (_|_ literal) in source)) {
+ bar: ""
+ }
+ }
+ }
+ brokenCycleSuccess: {
+ a: {
+ if (〈1;b〉.foo == _|_(explicit error (_|_ literal) in source)) {
+ foo: ""
+ }
+ }
+ b: {
+ if (〈1;a〉.bar == _|_(explicit error (_|_ literal) in source)) {
+ bar: ""
+ }
+ }
+ a: {
+ bar: ""
+ }
+ }
+ oneDirectionalConflictFail: {
+ p1: {
+ a: {
+ if (〈1;b〉.foo == _|_(explicit error (_|_ literal) in source)) {
+ bar: ""
+ }
+ }
+ b: {
+ if (〈1;a〉.bar == _|_(explicit error (_|_ literal) in source)) {
+ new: ""
+ }
+ }
+ }
+ p2: {
+ a: {
+ if (〈1;b〉.foo == _|_(explicit error (_|_ literal) in source)) {
+ new: ""
+ }
+ }
+ b: {
+ if (〈1;a〉.bar == _|_(explicit error (_|_ literal) in source)) {
+ foo: ""
+ }
+ }
+ }
+ }
+ oneDirectionalBrokenConflictSuccess: {
+ a: {
+ if (〈1;b〉.foo == _|_(explicit error (_|_ literal) in source)) {
+ bar: ""
+ }
+ }
+ b: {
+ if (〈1;a〉.bar == _|_(explicit error (_|_ literal) in source)) {
+ new: ""
+ }
+ }
+ b: {
+ foo: ""
+ }
+ }
+ }
+ sameStruct: {
+ chainSuccess: {
+ raises?: {}
+ if (〈0;raises〉 == _|_(explicit error (_|_ literal) in source)) {
+ ret: {
+ a: 1
+ }
+ }
+ ret?: {}
+ if (〈0;ret〉 != _|_(explicit error (_|_ literal) in source)) {
+ foo: {
+ a: 1
+ }
+ }
+ }
+ cycleFail: {
+ raises?: {}
+ if (〈0;raises〉 == _|_(explicit error (_|_ literal) in source)) {
+ ret: {
+ a: 1
+ }
+ }
+ ret?: {}
+ if (〈0;ret〉 != _|_(explicit error (_|_ literal) in source)) {
+ raises: {
+ a: 1
+ }
+ }
+ }
+ defCloseSuccess: {
+ #Example: {
+ raises?: {
+ runtime?: string
+ }
+ if (〈0;raises〉 == _|_(explicit error (_|_ literal) in source)) {
+ ret?: _
+ }
+ }
+ expr: (〈0;#Example〉 & {
+ ret: 2
+ })
+ }
+ }
+ nestedChain: {
+ cycleFail: {
+ if (〈0;#E〉.x != _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ y: true
+ }
+ }
+ if (〈0;#E〉.y == _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ x: true
+ }
+ }
+ #E: {
+ [_]: bool
+ }
+ }
+ brokenCycleSuccess: {
+ if (〈0;#E〉.x != _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ y: true
+ }
+ }
+ if (〈0;#E〉.y == _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ x: true
+ }
+ }
+ #E: {
+ [_]: bool
+ }
+ #E: {
+ x: true
+ }
+ }
+ doubleAddfail: {
+ if (〈0;#E〉.x == _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ y: true
+ }
+ }
+ if (〈0;#E〉.y == _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ x: true
+ }
+ }
+ #E: {
+ [_]: bool
+ }
+ }
+ trippleSuccess: {
+ if (〈0;#E〉.x != _|_(explicit error (_|_ literal) in source)) {
+ #E: {
+ y: true
+ }
+ }
+ if (〈0;#E〉.y != _|_(explicit error (_|_ literal) in source)) {
+ z: true
+ }
+ #E: {
+ x: true
+ }
+ }
+ }
+}
diff --git a/cue/testdata/cycle/compbottomnofinal.txtar b/cue/testdata/cycle/compbottomnofinal.txtar
new file mode 100644
index 0000000..0c264fc
--- /dev/null
+++ b/cue/testdata/cycle/compbottomnofinal.txtar
@@ -0,0 +1,869 @@
+// Issues: #667, #695, #622
+-- in.cue --
+import (
+ "strconv"
+ "regexp"
+)
+
+// In these test, it is impossible to determine the existence of some arcs due
+// to mutual dependence on becoming concrete.
+//
+// This tests shows the essences of when an existence check cannot be resolved.
+minimal: {
+ a: {
+ if b.port == _|_ {
+ port: ""
+ }
+ }
+
+ b: {
+ if a.port == _|_ {
+ port: ""
+ }
+ }
+}
+
+small: {
+ #userHostPort: #"^(:(?P<port>\d+))?$"#
+
+ p1: {
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+
+ #X: {
+ if #Y.port == _|_ {
+ port: ""
+ }
+ if #Y.port != _|_ {
+ port: ":" + strconv.FormatInt(#Y.port, 10)
+ }
+ }
+ }
+
+ p2: {
+ #X: {
+ if #Y.port == _|_ {
+ port: ""
+ }
+ if #Y.port != _|_ {
+ port: ":" + strconv.FormatInt(#Y.port, 10)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+ }
+}
+
+medium: {
+ #userHostPort: #"^(:(?P<port>\d+))?$"#
+
+ p1: {
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+
+ Y: {
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #X: {
+ // Can never determine whether Y.port exists as it's resolution
+ // depends on #Y becoming finalized, which, in turn, depends on #X
+ // becoming finalized.
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+ }
+
+ p2: {
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+
+ #X: {
+ // Can never determine whether Y.port exists as it's resolution
+ // depends on #Y becoming finalized, which, in turn, depends on #X
+ // becoming finalized.
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ Y: {
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+ }
+
+ p3: {
+ Y: {
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+
+ #X: {
+ // Can never determine whether Y.port exists as it's resolution
+ // depends on #Y becoming finalized, which, in turn, depends on #X
+ // becoming finalized.
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+ }
+
+ p4: {
+ Y: {
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #X: {
+ // Can never determine whether Y.port exists as it's resolution
+ // depends on #Y becoming finalized, which, in turn, depends on #X
+ // becoming finalized.
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+ }
+
+ p5: {
+ #X: {
+ // Can never determine whether Y.port exists as it's resolution
+ // depends on #Y becoming finalized, which, in turn, depends on #X
+ // becoming finalized.
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+
+ Y: {
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+ }
+
+ p6: {
+ #X: {
+ // Can never determine whether Y.port exists as it's resolution
+ // depends on #Y becoming finalized, which, in turn, depends on #X
+ // becoming finalized.
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ Y: {
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, #X.port)
+ }
+}
+
+
+large: {
+ #userHostPort: #"^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)(:(?P<port>\d+))?$"#
+
+ p1: {
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+
+ X: #X.userinfo + #X.host + #X.port
+
+ #X: {
+ if Y.userinfo == _|_ {
+ userinfo: ""
+ }
+ if Y.userinfo != _|_ {
+ userinfo: Y.userinfo + "@"
+ }
+
+ host: Y.host
+
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ Y: {
+ if #Y.userinfo != _|_ {
+ userinfo: #Y.userinfo
+ }
+
+ host: #Y.host
+
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, X)
+ }
+
+ p2: {
+ X: #X.userinfo + #X.host + #X.port
+
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+
+ #X: {
+ if Y.userinfo == _|_ {
+ userinfo: ""
+ }
+ if Y.userinfo != _|_ {
+ userinfo: Y.userinfo + "@"
+ }
+
+ host: Y.host
+
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ Y: {
+ if #Y.userinfo != _|_ {
+ userinfo: #Y.userinfo
+ }
+
+ host: #Y.host
+
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, X)
+ }
+
+ p3: {
+ X: #X.userinfo + #X.host + #X.port
+
+ #X: {
+ if Y.userinfo == _|_ {
+ userinfo: ""
+ }
+ if Y.userinfo != _|_ {
+ userinfo: Y.userinfo + "@"
+ }
+
+ host: Y.host
+
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+
+ Y: {
+ if #Y.userinfo != _|_ {
+ userinfo: #Y.userinfo
+ }
+
+ host: #Y.host
+
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, X)
+ }
+
+ p4: {
+ X: #X.userinfo + #X.host + #X.port
+
+ #X: {
+ if Y.userinfo == _|_ {
+ userinfo: ""
+ }
+ if Y.userinfo != _|_ {
+ userinfo: Y.userinfo + "@"
+ }
+
+ host: Y.host
+
+ if Y.port == _|_ {
+ port: ""
+ }
+ if Y.port != _|_ {
+ port: ":" + strconv.FormatInt(Y.port, 10)
+ }
+ }
+
+ #Y: regexp.FindNamedSubmatch(#userHostPort, X)
+
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+
+ Y: {
+ if #Y.userinfo != _|_ {
+ userinfo: #Y.userinfo
+ }
+
+ host: #Y.host
+
+ if #Y.port != _|_ {
+ port: strconv.Atoi(#Y.port)
+ }
+ }
+ }
+}
+-- out/eval --
+Errors:
+error in call to strconv.Atoi: strconv.Atoi: parsing "": invalid syntax
+large.p1.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+large.p2.#Y: cycle: field userinfo was added after an if clause evaluated it
+large.p2.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+large.p3.#Y: cycle: field userinfo was added after an if clause evaluated it
+large.p3.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+large.p4.#Y: cycle: field userinfo was added after an if clause evaluated it
+medium.p1.#Y: cycle: field port was added after an if clause evaluated it
+medium.p2.#Y: cycle: field port was added after an if clause evaluated it
+medium.p3.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+medium.p4.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+medium.p5.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+medium.p6.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+minimal.b: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+small.p1.#Y: cycle: field port was added after an if clause evaluated it
+small.p2.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+small.p2.#Y: cycle: field port was added after an if clause evaluated it
+small.p2.#X: cannot use "" (type string) as int in argument 1 to strconv.FormatInt:
+ ./in.cue:50:7
+
+Result:
+(_|_){
+ // [eval]
+ minimal: (_|_){
+ // [eval]
+ a: (struct){
+ }
+ b: (_|_){
+ // [eval] minimal.b: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ port: (string){ "" }
+ }
+ }
+ small: (_|_){
+ // [eval]
+ #userHostPort: (string){ "^(:(?P<port>\\d+))?$" }
+ p1: (_|_){
+ // [eval]
+ #Y: (_|_){
+ // [eval] small.p1.#Y: cycle: field port was added after an if clause evaluated it
+ port: (string){ "" }
+ }
+ #X: (#struct){
+ port: (string){ "" }
+ }
+ }
+ p2: (_|_){
+ // [eval]
+ #X: (_|_){
+ // [eval] small.p2.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ port: (_|_){
+ // [eval] small.p2.#X: cannot use "" (type string) as int in argument 1 to strconv.FormatInt:
+ // ./in.cue:50:7
+ }
+ }
+ #Y: (_|_){
+ // [eval] small.p2.#Y: cycle: field port was added after an if clause evaluated it
+ port: (string){ "" }
+ }
+ }
+ }
+ medium: (_|_){
+ // [eval]
+ #userHostPort: (string){ "^(:(?P<port>\\d+))?$" }
+ p1: (_|_){
+ // [eval]
+ #Y: (_|_){
+ // [eval] medium.p1.#Y: cycle: field port was added after an if clause evaluated it
+ port: (string){ "" }
+ }
+ Y: (struct){
+ }
+ #X: (#struct){
+ port: (string){ "" }
+ }
+ }
+ p2: (_|_){
+ // [eval]
+ #Y: (_|_){
+ // [eval] medium.p2.#Y: cycle: field port was added after an if clause evaluated it
+ port: (string){ "" }
+ }
+ #X: (#struct){
+ port: (string){ "" }
+ }
+ Y: (struct){
+ }
+ }
+ p3: (_|_){
+ // [eval]
+ Y: (_|_){
+ // [eval] medium.p3.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ port: (_|_){
+ // [eval] error in call to strconv.Atoi: strconv.Atoi: parsing "": invalid syntax
+ }
+ }
+ #Y: (#struct){
+ port: (string){ "" }
+ }
+ #X: (#struct){
+ port: (string){ "" }
+ }
+ }
+ p4: (_|_){
+ // [eval]
+ Y: (_|_){
+ // [eval] medium.p4.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ port: (_|_){
+ // [eval] error in call to strconv.Atoi: strconv.Atoi: parsing "": invalid syntax
+ }
+ }
+ #X: (#struct){
+ port: (string){ "" }
+ }
+ #Y: (#struct){
+ port: (string){ "" }
+ }
+ }
+ p5: (_|_){
+ // [eval]
+ #X: (_|_){
+ // [eval] medium.p5.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ port: (string){ "" }
+ }
+ #Y: (_|_){
+ // [eval] medium.p5.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ }
+ Y: (struct){
+ }
+ }
+ p6: (_|_){
+ // [eval]
+ #X: (_|_){
+ // [eval] medium.p6.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ port: (string){ "" }
+ }
+ Y: (struct){
+ }
+ #Y: (_|_){
+ // [eval] medium.p6.#X: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ }
+ }
+ }
+ large: (_|_){
+ // [eval]
+ #userHostPort: (string){ "^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)(:(?P<port>\\d+))?$" }
+ p1: (_|_){
+ // [eval]
+ Y: (_|_){
+ // [eval] large.p1.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ userinfo: (string){ "user" }
+ host: (string){ "example.com" }
+ port: (_|_){
+ // [eval] error in call to strconv.Atoi: strconv.Atoi: parsing "": invalid syntax
+ }
+ }
+ X: (string){ "user@example.com" }
+ #X: (#struct){
+ host: (string){ "example.com" }
+ userinfo: (string){ "user@" }
+ port: (string){ "" }
+ }
+ #Y: (#struct){
+ host: (string){ "example.com" }
+ port: (string){ "" }
+ userinfo: (string){ "user" }
+ }
+ }
+ p2: (_|_){
+ // [eval]
+ X: (string){ "user@example.com" }
+ Y: (_|_){
+ // [eval] large.p2.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ userinfo: (string){ "user" }
+ host: (string){ "example.com" }
+ port: (_|_){
+ // [eval] error in call to strconv.Atoi: strconv.Atoi: parsing "": invalid syntax
+ }
+ }
+ #X: (#struct){
+ host: (string){ "example.com" }
+ userinfo: (string){ "user@" }
+ port: (string){ "" }
+ }
+ #Y: (_|_){
+ // [eval] large.p2.#Y: cycle: field userinfo was added after an if clause evaluated it
+ host: (string){ "example.com" }
+ port: (string){ "" }
+ userinfo: (string){ "user" }
+ }
+ }
+ p3: (_|_){
+ // [eval]
+ X: (string){ "user@example.com" }
+ #X: (#struct){
+ host: (string){ "example.com" }
+ userinfo: (string){ "user@" }
+ port: (string){ "" }
+ }
+ Y: (_|_){
+ // [eval] large.p3.Y: cycle: new field port inserted by if clause that was previously evaluated by another if clause
+ userinfo: (string){ "user" }
+ host: (string){ "example.com" }
+ port: (_|_){
+ // [eval] error in call to strconv.Atoi: strconv.Atoi: parsing "": invalid syntax
+ }
+ }
+ #Y: (_|_){
+ // [eval] large.p3.#Y: cycle: field userinfo was added after an if clause evaluated it
+ host: (string){ "example.com" }
+ port: (string){ "" }
+ userinfo: (string){ "user" }
+ }
+ }
+ p4: (_|_){
+ // [eval]
+ X: (string){ "user@example.com" }
+ #X: (#struct){
+ host: (string){ "example.com" }
+ userinfo: (string){ "user@" }
+ port: (string){ "" }
+ }
+ #Y: (_|_){
+ // [eval] large.p4.#Y: cycle: field userinfo was added after an if clause evaluated it
+ host: (string){ "example.com" }
+ port: (string){ "" }
+ userinfo: (string){ "user" }
+ }
+ Y: (_|_){
+ // [eval]
+ userinfo: (string){ "user" }
+ host: (_|_){
+ // [eval] large.p4.#Y: cycle: field userinfo was added after an if clause evaluated it
+ }
+ }
+ }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ minimal: {
+ a: {
+ if (〈1;b〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ }
+ b: {
+ if (〈1;a〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ }
+ }
+ small: {
+ #userHostPort: "^(:(?P<port>\\d+))?$"
+ p1: {
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ #X: {
+ if (〈1;#Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;#Y〉.port, 10))
+ }
+ }
+ }
+ p2: {
+ #X: {
+ if (〈1;#Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;#Y〉.port, 10))
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ }
+ }
+ medium: {
+ #userHostPort: "^(:(?P<port>\\d+))?$"
+ p1: {
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ Y: {
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #X: {
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ }
+ p2: {
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ #X: {
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ Y: {
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ }
+ p3: {
+ Y: {
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ #X: {
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ }
+ p4: {
+ Y: {
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #X: {
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ }
+ p5: {
+ #X: {
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ Y: {
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ }
+ p6: {
+ #X: {
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ Y: {
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;#X〉.port)
+ }
+ }
+ large: {
+ #userHostPort: "^((?P<userinfo>[[:alnum:]]*)@)?(?P<host>[[:alnum:].]+)(:(?P<port>\\d+))?$"
+ p1: {
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+ X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
+ #X: {
+ if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
+ userinfo: ""
+ }
+ if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: (〈2;Y〉.userinfo + "@")
+ }
+ host: 〈1;Y〉.host
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ Y: {
+ if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: 〈2;#Y〉.userinfo
+ }
+ host: 〈1;#Y〉.host
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
+ }
+ p2: {
+ X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+ #X: {
+ if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
+ userinfo: ""
+ }
+ if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: (〈2;Y〉.userinfo + "@")
+ }
+ host: 〈1;Y〉.host
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ Y: {
+ if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: 〈2;#Y〉.userinfo
+ }
+ host: 〈1;#Y〉.host
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
+ }
+ p3: {
+ X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
+ #X: {
+ if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
+ userinfo: ""
+ }
+ if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: (〈2;Y〉.userinfo + "@")
+ }
+ host: 〈1;Y〉.host
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+ Y: {
+ if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: 〈2;#Y〉.userinfo
+ }
+ host: 〈1;#Y〉.host
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
+ }
+ p4: {
+ X: ((〈0;#X〉.userinfo + 〈0;#X〉.host) + 〈0;#X〉.port)
+ #X: {
+ if (〈1;Y〉.userinfo == _|_(explicit error (_|_ literal) in source)) {
+ userinfo: ""
+ }
+ if (〈1;Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: (〈2;Y〉.userinfo + "@")
+ }
+ host: 〈1;Y〉.host
+ if (〈1;Y〉.port == _|_(explicit error (_|_ literal) in source)) {
+ port: ""
+ }
+ if (〈1;Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: (":" + 〈import;strconv〉.FormatInt(〈2;Y〉.port, 10))
+ }
+ }
+ #Y: 〈import;regexp〉.FindNamedSubmatch(〈1;#userHostPort〉, 〈0;X〉)
+ Y: {
+ userinfo: "user"
+ host: "example.com"
+ }
+ Y: {
+ if (〈1;#Y〉.userinfo != _|_(explicit error (_|_ literal) in source)) {
+ userinfo: 〈2;#Y〉.userinfo
+ }
+ host: 〈1;#Y〉.host
+ if (〈1;#Y〉.port != _|_(explicit error (_|_ literal) in source)) {
+ port: 〈import;strconv〉.Atoi(〈2;#Y〉.port)
+ }
+ }
+ }
+ }
+}
diff --git a/cue/testdata/cycle/issue429.txtar b/cue/testdata/cycle/issue429.txtar
index 876994b..8b9ddb6 100644
--- a/cue/testdata/cycle/issue429.txtar
+++ b/cue/testdata/cycle/issue429.txtar
@@ -74,6 +74,9 @@
er3.min: invalid value 5 (out of bound <5):
./in.cue:29:10
./in.cue:44:10
+er3.max: invalid value 5 (out of bound >5):
+ ./in.cue:30:10
+ ./in.cue:45:10
Result:
(_|_){
@@ -157,14 +160,9 @@
// ./in.cue:44:10
}
max: (_|_){
- // [eval] er3.min: 2 errors in empty disjunction:
- // er3.min: conflicting values 1 and 5:
- // ./in.cue:28:11
- // ./in.cue:43:6
- // ./in.cue:44:10
- // er3.min: invalid value 5 (out of bound <5):
- // ./in.cue:29:10
- // ./in.cue:44:10
+ // [eval] er3.max: invalid value 5 (out of bound >5):
+ // ./in.cue:30:10
+ // ./in.cue:45:10
}
}
}
diff --git a/cue/testdata/eval/incomplete.txtar b/cue/testdata/eval/incomplete.txtar
index daa5c6e..5d8e170 100644
--- a/cue/testdata/eval/incomplete.txtar
+++ b/cue/testdata/eval/incomplete.txtar
@@ -47,8 +47,7 @@
// ./in.cue:3:5
}
e5: (_|_){
- // [cycle] cycle error:
- // ./in.cue:9:6
+ // [cycle] cycle error
}
E: (struct){
a: (_|_){
@@ -57,8 +56,6 @@
}
b: (_|_){
// [cycle] cycle error:
- // ./in.cue:12:6
- // cycle error:
// ./in.cue:13:6
}
c: (_|_){
diff --git a/cue/testdata/fulleval/026_dont_convert_incomplete_errors_to_non-incomplete.txtar b/cue/testdata/fulleval/026_dont_convert_incomplete_errors_to_non-incomplete.txtar
index 377d3e3..121daaf 100644
--- a/cue/testdata/fulleval/026_dont_convert_incomplete_errors_to_non-incomplete.txtar
+++ b/cue/testdata/fulleval/026_dont_convert_incomplete_errors_to_non-incomplete.txtar
@@ -48,12 +48,10 @@
(struct){
n1: (struct){
min: (_|_){
- // [cycle] cycle error:
- // ./in.cue:3:12
+ // [cycle] cycle error
}
max: (_|_){
- // [cycle] cycle error:
- // ./in.cue:3:12
+ // [cycle] cycle error
}
}
n2: (_|_){
diff --git a/cue/testdata/fulleval/046_non-structural_direct_cycles.txtar b/cue/testdata/fulleval/046_non-structural_direct_cycles.txtar
index 72099dc..2fbf34c 100644
--- a/cue/testdata/fulleval/046_non-structural_direct_cycles.txtar
+++ b/cue/testdata/fulleval/046_non-structural_direct_cycles.txtar
@@ -27,17 +27,24 @@
} & 〈0;c2〉.bar)
}
-- out/eval --
-(struct){
- c1: (_|_){
- // [cycle] cycle error:
- // ./in.cue:1:21
+Errors:
+c2: conflicting values 1 and {bar:1} (mismatched types int and struct):
+ ./in.cue:2:5
+ ./in.cue:2:16
+
+Result:
+(_|_){
+ // [eval]
+ c1: (struct){
bar: (struct){
baz: (int){ 2 }
}
+ baz: (int){ 2 }
}
c2: (_|_){
- // [cycle] cycle error:
- // ./in.cue:2:21
+ // [eval] c2: conflicting values 1 and {bar:1} (mismatched types int and struct):
+ // ./in.cue:2:5
+ // ./in.cue:2:16
bar: (int){ 1 }
}
}
diff --git a/internal/core/adt/adt.go b/internal/core/adt/adt.go
index f67f1cb..7c670a4 100644
--- a/internal/core/adt/adt.go
+++ b/internal/core/adt/adt.go
@@ -44,6 +44,7 @@
v = err
break
}
+ // r.Finalize(ctx) // TODO: Finalize here?
return r
case Evaluator:
diff --git a/internal/core/adt/composite.go b/internal/core/adt/composite.go
index 893ea32..b476662 100644
--- a/internal/core/adt/composite.go
+++ b/internal/core/adt/composite.go
@@ -175,15 +175,18 @@
// isData indicates that this Vertex is to be interepreted as data: pattern
// and additional constraints, as well as optional fields, should be
// ignored.
- isData bool
- Closed bool
+ isData bool
+ Closed bool
+ nonMonotonicReject bool
+ nonMonotonicInsertGen int32
+ nonMonotonicLookupGen int32
// EvalCount keeps track of temporary dereferencing during evaluation.
// If EvalCount > 0, status should be considered to be EvaluatingArcs.
- EvalCount int
+ EvalCount int32
// SelfCount is used for tracking self-references.
- SelfCount int
+ SelfCount int32
// BaseValue is the value associated with this vertex. For lists and structs
// this is a sentinel value indicating its kind.
@@ -315,6 +318,15 @@
}
}
+// isUndefined reports whether a vertex does not have a useable BaseValue yet.
+func (v *Vertex) isUndefined() bool {
+ switch v.BaseValue {
+ case nil, cycle:
+ return true
+ }
+ return false
+}
+
func (x *Vertex) IsConcrete() bool {
return x.Concreteness() <= Concrete
}
@@ -458,7 +470,7 @@
return v
}
// b, _ := x.BaseValue.(*Bottom)
- if n := x.state; n != nil && x.BaseValue == cycle {
+ if n := x.state; n != nil && isCyclePlaceholder(x.BaseValue) {
if n.errs != nil && !n.errs.IsIncomplete() {
return n.errs
}
@@ -596,12 +608,31 @@
// GetArc returns a Vertex for the outgoing arc with label f. It creates and
// ads one if it doesn't yet exist.
-func (v *Vertex) GetArc(f Feature) (arc *Vertex, isNew bool) {
+func (v *Vertex) GetArc(c *OpContext, f Feature) (arc *Vertex, isNew bool) {
arc = v.Lookup(f)
if arc == nil {
+ for _, a := range v.state.usedArcs {
+ if a.Label == f {
+ arc = a
+ v.Arcs = append(v.Arcs, arc)
+ isNew = true
+ if c.nonMonotonicInsertNest > 0 {
+ a.nonMonotonicInsertGen = c.nonMonotonicGeneration
+ }
+ break
+ }
+ }
+ }
+ if arc == nil {
arc = &Vertex{Parent: v, Label: f}
v.Arcs = append(v.Arcs, arc)
isNew = true
+ if c.nonMonotonicInsertNest > 0 {
+ arc.nonMonotonicInsertGen = c.nonMonotonicGeneration
+ }
+ }
+ if c.nonMonotonicInsertNest == 0 {
+ arc.nonMonotonicInsertGen = 0
}
return arc, isNew
}
diff --git a/internal/core/adt/context.go b/internal/core/adt/context.go
index d730ca2..8a7d4ea 100644
--- a/internal/core/adt/context.go
+++ b/internal/core/adt/context.go
@@ -167,6 +167,11 @@
// structural cycle errors.
vertex *Vertex
+ nonMonotonicLookupNest int32
+ nonMonotonicRejectNest int32
+ nonMonotonicInsertNest int32
+ nonMonotonicGeneration int32
+
// These fields are used associate scratch fields for computing closedness
// of a Vertex. These fields could have been included in StructInfo (like
// Tomabechi's unification algorithm), but we opted for an indirection to
@@ -386,8 +391,7 @@
func (c *OpContext) Resolve(env *Environment, r Resolver) (*Vertex, *Bottom) {
s := c.PushState(env, r.Source())
- arc := r.resolve(c, AllArcs)
- // TODO: check for cycle errors?
+ arc := r.resolve(c, Partial)
err := c.PopState(s)
if err != nil {
@@ -563,16 +567,34 @@
defer func() {
c.errs = CombineErrors(c.src, c.errs, err)
- // TODO: remove this when we handle errors more principally.
- if b, ok := result.(*Bottom); ok && c.src != nil &&
- b.Code == CycleError &&
- b.Err.Position() == token.NoPos &&
- len(b.Err.InputPositions()) == 0 {
- bb := *b
- bb.Err = errors.Wrapf(b.Err, c.src.Pos(), "")
- result = &bb
+
+ if v, ok := result.(*Vertex); ok {
+ if b, _ := v.BaseValue.(*Bottom); b != nil {
+ switch b.Code {
+ case IncompleteError:
+ case CycleError:
+ if state == Partial {
+ break
+ }
+ fallthrough
+ default:
+ result = b
+ }
+ }
}
- c.errs = CombineErrors(c.src, c.errs, result)
+
+ // TODO: remove this when we handle errors more principally.
+ if b, ok := result.(*Bottom); ok {
+ if c.src != nil &&
+ b.Code == CycleError &&
+ b.Err.Position() == token.NoPos &&
+ len(b.Err.InputPositions()) == 0 {
+ bb := *b
+ bb.Err = errors.Wrapf(b.Err, c.src.Pos(), "")
+ result = &bb
+ }
+ c.errs = CombineErrors(c.src, c.errs, result)
+ }
if c.errs != nil {
result = c.errs
}
@@ -668,7 +690,7 @@
return nil
}
- if v.BaseValue == nil || v.BaseValue == cycle {
+ if v.isUndefined() {
// Use node itself to allow for cycle detection.
c.Unify(v, AllArcs)
}
@@ -681,7 +703,7 @@
}
}
-func (c *OpContext) lookup(x *Vertex, pos token.Pos, l Feature) *Vertex {
+func (c *OpContext) lookup(x *Vertex, pos token.Pos, l Feature, state VertexStatus) *Vertex {
if l == InvalidLabel || x == nil {
// TODO: is it possible to have an invalid label here? Maybe through the
// API?
@@ -739,10 +761,50 @@
}
a := x.Lookup(l)
+
+ var hasCycle bool
+outer:
+ switch {
+ case c.nonMonotonicLookupNest == 0 && c.nonMonotonicRejectNest == 0:
+ case a != nil:
+ if state == Partial {
+ a.nonMonotonicLookupGen = c.nonMonotonicGeneration
+ }
+
+ case x.state != nil && state == Partial:
+ for _, e := range x.state.exprs {
+ if isCyclePlaceholder(e.err) {
+ hasCycle = true
+ }
+ }
+ for _, a := range x.state.usedArcs {
+ if a.Label == l {
+ a.nonMonotonicLookupGen = c.nonMonotonicGeneration
+ if c.nonMonotonicRejectNest > 0 {
+ a.nonMonotonicReject = true
+ }
+ break outer
+ }
+ }
+ a := &Vertex{Label: l, nonMonotonicLookupGen: c.nonMonotonicGeneration}
+ if c.nonMonotonicRejectNest > 0 {
+ a.nonMonotonicReject = true
+ }
+ x.state.usedArcs = append(x.state.usedArcs, a)
+ }
if a == nil {
+ if x.state != nil {
+ for _, e := range x.state.exprs {
+ if isCyclePlaceholder(e.err) {
+ hasCycle = true
+ }
+ }
+ }
code := IncompleteError
if !x.Accept(c, l) {
code = 0
+ } else if hasCycle {
+ code = CycleError
}
// TODO: if the struct was a literal struct, we can also treat it as
// closed and make this a permanent error.
@@ -824,13 +886,13 @@
// annotated cycle error that could be taken as is.
// TODO: do something simpler.
if scalar {
- if w := Unwrap(v); w != cycle {
+ if w := Unwrap(v); !isCyclePlaceholder(w) {
v = w
}
}
node, ok := v.(*Vertex)
- if ok && node.BaseValue != cycle {
+ if ok && !isCyclePlaceholder(node.BaseValue) {
v = node.Value()
}
diff --git a/internal/core/adt/errors.go b/internal/core/adt/errors.go
index 002ecc7..1b20606 100644
--- a/internal/core/adt/errors.go
+++ b/internal/core/adt/errors.go
@@ -174,6 +174,9 @@
a, _ := Unwrap(x).(*Bottom)
b, _ := Unwrap(y).(*Bottom)
+ if a == b && isCyclePlaceholder(a) {
+ return a
+ }
switch {
case a != nil && b != nil:
case a != nil:
diff --git a/internal/core/adt/eval.go b/internal/core/adt/eval.go
index 394cd49..253b02f 100644
--- a/internal/core/adt/eval.go
+++ b/internal/core/adt/eval.go
@@ -111,7 +111,7 @@
//
// TODO: return *Vertex
func (c *OpContext) evaluate(v *Vertex, state VertexStatus) Value {
- if v.BaseValue == nil || v.BaseValue == cycle {
+ if v.isUndefined() {
// Use node itself to allow for cycle detection.
c.Unify(v, state)
}
@@ -120,13 +120,17 @@
if n.errs != nil && !n.errs.IsIncomplete() {
return n.errs
}
- if n.scalar != nil && v.BaseValue == cycle {
+ if n.scalar != nil && isCyclePlaceholder(v.BaseValue) {
return n.scalar
}
}
switch x := v.BaseValue.(type) {
case *Bottom:
+ if x.IsIncomplete() {
+ c.AddBottom(x)
+ return nil
+ }
return x
case nil:
@@ -176,6 +180,7 @@
switch v.Status() {
case Evaluating:
+ n.insertConjuncts()
return
case EvaluatingArcs:
@@ -238,21 +243,15 @@
// non-expression references. The cycle error may also be removed as soon
// as there is evidence what a correct value must be, but before all
// validation has taken place.
+ //
+ // TODO(cycle): having a more recursive algorithm would make this
+ // special cycle handling unnecessary.
v.BaseValue = cycle
v.UpdateStatus(Evaluating)
- // If the result is a struct, it needs to be closed if:
- // 1) this node introduces a definition
- // 2) this node is a child of a node that introduces a definition,
- // recursively.
- // 3) this node embeds a closed struct.
-
- for _, x := range v.Conjuncts {
- // TODO: needed for reentrancy. Investigate usefulness for cycle
- // detection.
- n.addExprConjunct(x)
- }
+ n.conjuncts = v.Conjuncts
+ n.insertConjuncts()
fallthrough
@@ -269,7 +268,7 @@
if !n.done() {
switch {
- case len(n.disjunctions) > 0 && v.BaseValue == cycle:
+ case len(n.disjunctions) > 0 && isCyclePlaceholder(v.BaseValue):
// We disallow entering computations of disjunctions with
// incomplete data.
if state == Finalized {
@@ -282,12 +281,7 @@
}
return
- case state <= Partial:
- n.node.UpdateStatus(Partial)
- return
-
case state <= AllArcs:
- c.AddBottom(n.incompleteErrors())
n.node.UpdateStatus(Partial)
return
}
@@ -382,6 +376,15 @@
}
}
+// insertConjuncts inserts conjuncts previously uninserted.
+func (n *nodeContext) insertConjuncts() {
+ for len(n.conjuncts) > 0 {
+ x := n.conjuncts[0]
+ n.conjuncts = n.conjuncts[1:]
+ n.addExprConjunct(x)
+ }
+}
+
// finalizeIncomplete collects all uncompleted expressions and adds them as
// errors. As disjuncts are always evaluated with Finalized, care should be
// taken to only call this after all disjunctions in a path have been completed.
@@ -436,7 +439,7 @@
n.errs = nil
default:
- if n.node.BaseValue == cycle {
+ if isCyclePlaceholder(n.node.BaseValue) {
if !n.done() {
n.node.BaseValue = n.incompleteErrors()
} else {
@@ -602,6 +605,19 @@
} else {
// Visit arcs recursively to validate and compute error.
for _, a := range n.node.Arcs {
+ if a.nonMonotonicInsertGen >= a.nonMonotonicLookupGen && a.nonMonotonicLookupGen > 0 {
+ err := ctx.Newf(
+ "cycle: new field %s inserted by if clause that was previously evaluated by another if clause", a.Label.SelectorString(ctx))
+ err.AddPosition(n.node)
+ n.node.BaseValue = &Bottom{Err: err}
+ } else if a.nonMonotonicReject {
+ err := ctx.Newf(
+ "cycle: field %s was added after an if clause evaluated it",
+ a.Label.SelectorString(ctx))
+ err.AddPosition(n.node)
+ n.node.BaseValue = &Bottom{Err: err}
+ }
+
// Call UpdateStatus here to be absolutely sure the status is set
// correctly and that we are not regressing.
n.node.UpdateStatus(EvaluatingArcs)
@@ -626,6 +642,10 @@
Code: CycleError,
}
+func isCyclePlaceholder(v BaseValue) bool {
+ return v == cycle
+}
+
func (n *nodeContext) createDisjunct() *Disjunction {
a := make([]*Vertex, len(n.disjuncts))
p := 0
@@ -671,6 +691,9 @@
ctx *OpContext
node *Vertex
+ // usedArcs is a list of arcs that were looked up during non-monotonic operations, but do not exist yet.
+ usedArcs []*Vertex
+
// TODO: (this is CL is first step)
// filter *Vertex a subset of composite with concrete fields for
// bloom-like filtering of disjuncts. We should first verify, however,
@@ -700,6 +723,10 @@
checks []Validator // BuiltinValidator, other bound values.
errs *Bottom
+ // Conjuncts holds a reference to the Vertex Arcs that still need
+ // processing. It does NOT need to be copied.
+ conjuncts []Conjunct
+
// notify is used to communicate errors in cyclic dependencies.
// TODO: also use this to communicate increasingly more concrete values.
notify []*Vertex
@@ -759,6 +786,7 @@
d.hasNonCycle = n.hasNonCycle
// d.arcMap = append(d.arcMap, n.arcMap...) // XXX add?
+ // d.usedArcs = append(d.usedArcs, n.usedArcs...) // XXX: add?
d.notify = append(d.notify, n.notify...)
d.checks = append(d.checks, n.checks...)
d.dynamicFields = append(d.dynamicFields, n.dynamicFields...)
@@ -781,6 +809,7 @@
ctx: c,
node: node,
kind: TopKind,
+ usedArcs: n.usedArcs[:0],
arcMap: n.arcMap[:0],
notify: n.notify[:0],
checks: n.checks[:0],
@@ -1677,7 +1706,7 @@
// disjunctions.
func (n *nodeContext) insertField(f Feature, x Conjunct) *Vertex {
ctx := n.ctx
- arc, isNew := n.node.GetArc(f)
+ arc, isNew := n.node.GetArc(ctx, f)
arc.addConjunct(x)
@@ -1837,9 +1866,12 @@
continue
}
id := d.id.SpawnSpan(d.yield, ComprehensionSpan)
+
+ n.ctx.nonMonotonicInsertNest++
for _, st := range sa {
n.addStruct(st.env, st.s, id)
}
+ n.ctx.nonMonotonicInsertNest--
}
progress = k < len(*all)
diff --git a/internal/core/adt/expr.go b/internal/core/adt/expr.go
index ac9b5ed..12d0b6f 100644
--- a/internal/core/adt/expr.go
+++ b/internal/core/adt/expr.go
@@ -654,7 +654,7 @@
func (x *FieldReference) resolve(c *OpContext, state VertexStatus) *Vertex {
n := c.relNode(x.UpCount)
pos := pos(x)
- return c.lookup(n, pos, x.Label)
+ return c.lookup(n, pos, x.Label, state)
}
// A LabelReference refers to the string or integer value of a label.
@@ -720,7 +720,7 @@
v := ctx.value(x.Label)
ctx.PopState(frame)
f := ctx.Label(x.Label, v)
- return ctx.lookup(e.Vertex, pos(x), f)
+ return ctx.lookup(e.Vertex, pos(x), f, state)
}
// An ImportReference refers to an imported package.
@@ -805,7 +805,7 @@
if n == emptyNode {
return n
}
- return c.lookup(n, x.Src.Sel.Pos(), x.Sel)
+ return c.lookup(n, x.Src.Sel.Pos(), x.Sel, state)
}
// IndexExpr is like a selector, but selects an index.
@@ -833,7 +833,7 @@
return n
}
f := ctx.Label(x.Index, i)
- return ctx.lookup(n, x.Src.Index.Pos(), f)
+ return ctx.lookup(n, x.Src.Index.Pos(), f, state)
}
// A SliceExpr represents a slice operation. (Not currently in spec.)
@@ -1091,22 +1091,57 @@
return BinOp(c, x.Op, left, right)
}
-func (c *OpContext) validate(env *Environment, src ast.Node, x Expr, op Op) Value {
+func (c *OpContext) validate(env *Environment, src ast.Node, x Expr, op Op) (r Value) {
s := c.PushState(env, src)
- defer c.PopState(s)
-
- for v := c.evalState(x, Partial); ; {
- switch x := v.(type) {
- case *Vertex:
- v, _ = x.BaseValue.(Value)
-
- case *Bottom:
- return &Bool{src, op == EqualOp}
-
- default:
- return &Bool{src, op != EqualOp}
- }
+ if c.nonMonotonicLookupNest == 0 {
+ c.nonMonotonicGeneration++
}
+
+ var match bool
+ v := c.evalState(x, Partial)
+ // NOTE: using Unwrap is maybe note entirely accurate, as it may discard
+ // a future error. However, if it does so, the error will at least be
+ // reported elsewhere.
+ switch b := Unwrap(v).(type) {
+ case nil:
+ case *Bottom:
+ if b.Code == CycleError {
+ c.PopState(s)
+ c.AddBottom(b)
+ return nil
+ }
+ match = op == EqualOp
+ // We have a nonmonotonic use of a failure. Referenced fields should
+ // not be added anymore.
+ c.nonMonotonicRejectNest++
+ c.evalState(x, Partial)
+ c.nonMonotonicRejectNest--
+
+ default:
+ // TODO(cycle): if EqualOp:
+ // - ensure to pass special status to if clause or keep a track of "hot"
+ // paths.
+ // - evaluate hypothetical struct
+ // - walk over all fields and verify that fields are not contradicting
+ // previously marked fields.
+ //
+ switch {
+ case b.Concreteness() > Concrete:
+ // TODO: mimic comparison to bottom semantics. If it is a valid
+ // value, check for concreteness that this level only. This
+ // should ultimately be replaced with an exists and valid
+ // builtin.
+ match = op == EqualOp
+ default:
+ match = op != EqualOp
+ }
+ c.nonMonotonicLookupNest++
+ c.evalState(x, Partial)
+ c.nonMonotonicLookupNest--
+ }
+
+ c.PopState(s)
+ return &Bool{src, match}
}
// A CallExpr represents a call to a builtin.
