internal/core/adt: remove problematic Ref deletion
This is no longer necessary with the latest tweaks in the
cycle detection algorithm. Also, it could cause a hang
in some cases.
Oddly, this seems to deepen some of the cycles. Unity shows
no performance impact, though.
This is related to, although not a full solution for,
Issue #1940
Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com>
Change-Id: Iaeee44a7652fa1dbf2e52dc91a1f62e582bf93c6
Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/543656
Reviewed-by: Roger Peppe <rogpeppe@gmail.com>
Unity-Result: CUEcueckoo <cueckoo@cuelang.org>
TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>
diff --git a/cue/testdata/cycle/constraints.txtar b/cue/testdata/cycle/constraints.txtar
index 8580290..98f595e 100644
--- a/cue/testdata/cycle/constraints.txtar
+++ b/cue/testdata/cycle/constraints.txtar
@@ -439,7 +439,7 @@
noCancelSelfInvoke.t1.x.c.b.b.b: structural cycle
noCancelSelfInvoke.t1.x.c.c: structural cycle
selfTriggerCycle.issue1503.#T.a.b.link: structural cycle
-selfTriggerCycle.long1.a.c.b.c.b.c.b: structural cycle
+selfTriggerCycle.long1.a.c.b.c.b.c.b.c.b: structural cycle
selfTriggerCycle.t1.#T.b.b: structural cycle
selfTriggerCycle.t2.b.c.a: structural cycle
@@ -699,7 +699,13 @@
c: (_|_){
// [structural cycle]
b: (_|_){
- // [structural cycle] selfTriggerCycle.long1.a.c.b.c.b.c.b: structural cycle
+ // [structural cycle]
+ c: (_|_){
+ // [structural cycle]
+ b: (_|_){
+ // [structural cycle] selfTriggerCycle.long1.a.c.b.c.b.c.b.c.b: structural cycle
+ }
+ }
}
}
}
diff --git a/cue/testdata/disjunctions/elimination.txtar b/cue/testdata/disjunctions/elimination.txtar
index 6ee1550..bde16e6 100644
--- a/cue/testdata/disjunctions/elimination.txtar
+++ b/cue/testdata/disjunctions/elimination.txtar
@@ -233,7 +233,17 @@
}
issue1838: t2: {
p?: []
- a: null | [for k in p {k}]
+ a: null | [for k in p {k}]
+}
+
+noHang: {
+ // This should terminate.
+ #T: ["a", #T] | ["d", ...#T]
+
+ x: #T
+
+ #X: x
+ #X: #T
}
-- out/eval --
@@ -605,6 +615,27 @@
a: (null){ null }
}
}
+ noHang: (struct){
+ #T: (list){
+ 0: (string){ "d" }
+ }
+ x: (#list){ |((#list){
+ 0: (string){ "a" }
+ 1: (list){
+ 0: (string){ "d" }
+ }
+ }, (list){
+ 0: (string){ "d" }
+ }) }
+ #X: (#list){ |((#list){
+ 0: (string){ "a" }
+ 1: (list){
+ 0: (string){ "d" }
+ }
+ }, (list){
+ 0: (string){ "d" }
+ }) }
+ }
}
-- out/compile --
--- in.cue
@@ -1282,4 +1313,16 @@
])
}
}
+ noHang: {
+ #T: ([
+ "a",
+ 〈1;#T〉,
+ ]|[
+ "d",
+ ...〈1;#T〉,
+ ])
+ x: 〈0;#T〉
+ #X: 〈0;x〉
+ #X: 〈0;#T〉
+ }
}
diff --git a/internal/core/adt/cycle.go b/internal/core/adt/cycle.go
index cfd5ec9..79cf6dc 100644
--- a/internal/core/adt/cycle.go
+++ b/internal/core/adt/cycle.go
@@ -218,9 +218,6 @@
// {x: out, out: x}.out
Inline bool
- // IsPattern indicates whether this conjunct was inserted by a pattern.
- IsPattern bool
-
// TODO(perf): pack this in with CloseInfo. Make an uint32 pointing into
// a buffer maintained in OpContext, using a mark-release mechanism.
Refs *RefNode
diff --git a/internal/core/adt/optional.go b/internal/core/adt/optional.go
index ba92dda..af1ad85 100644
--- a/internal/core/adt/optional.go
+++ b/internal/core/adt/optional.go
@@ -22,17 +22,6 @@
closeInfo := o.CloseInfo
closeInfo.IsClosed = false
- for _, v := range arc.Conjuncts {
- // TODO: This is not entirely correct. It could be that a pattern is
- // "feeding" new conjuncts without it being a cycle just yet.
- // Perhaps we allow a reference to be discarded only once.
- // Needed for Issue #990.
- // TODO: eliminate the need for IsPattern.
- if !v.CloseInfo.IsCyclic && !v.CloseInfo.IsPattern {
- closeInfo.CycleInfo.Refs = nil
- break
- }
- }
// Match normal fields
matched := false
@@ -71,7 +60,6 @@
if matchBulk(c, env, b, f, label) {
matched = true
info := closeInfo.SpawnSpan(b.Value, ConstraintSpan)
- info.IsPattern = true
arc.AddConjunct(MakeConjunct(&bulkEnv, b, info))
}
}
@@ -130,9 +118,9 @@
}
n := Vertex{}
- m := MakeRootConjunct(env, v)
+ m := MakeConjunct(env, v, c.ci)
n.AddConjunct(m)
- n.AddConjunct(MakeRootConjunct(m.Env, label))
+ n.AddConjunct(MakeConjunct(m.Env, label, c.ci))
c.inConstraint++
n.Finalize(c)