internal/core/adt: keep nodeContext in Vertex
This allows reusing the nodeContext in different phases
and better control over prevendting duplicate work.
Change-Id: I54223595ea69320c96c7e3d3fbd68d96d138cfb1
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/8106
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/basicrewrite/018_self-reference_cycles.txtar b/cue/testdata/basicrewrite/018_self-reference_cycles.txtar
index 8bb44c9..e65c857 100644
--- a/cue/testdata/basicrewrite/018_self-reference_cycles.txtar
+++ b/cue/testdata/basicrewrite/018_self-reference_cycles.txtar
@@ -27,11 +27,11 @@
(struct){
a: (_|_){
// [cycle] cycle error:
- // ./in.cue:2:4
+ // ./in.cue:1:4
}
b: (_|_){
// [cycle] cycle error:
- // ./in.cue:2:4
+ // ./in.cue:1:4
}
c: (#list){
0: (_){ _ }
diff --git a/cue/testdata/cycle/021_delayed_constraint_failure.txtar b/cue/testdata/cycle/021_delayed_constraint_failure.txtar
index 8e769c7..72b64a5 100644
--- a/cue/testdata/cycle/021_delayed_constraint_failure.txtar
+++ b/cue/testdata/cycle/021_delayed_constraint_failure.txtar
@@ -26,7 +26,7 @@
}
-- out/eval --
Errors:
-b: conflicting values 200 and 210:
+b: conflicting values 210 and 200:
./in.cue:2:4
./in.cue:3:4
x: conflicting values 101 and 100:
@@ -38,7 +38,7 @@
// [eval]
a: (int){ 100 }
b: (_|_){
- // [eval] b: conflicting values 200 and 210:
+ // [eval] b: conflicting values 210 and 200:
// ./in.cue:2:4
// ./in.cue:3:4
}
diff --git a/cue/testdata/cycle/049_self-reference_cycles_conflicts_with_strings.txtar b/cue/testdata/cycle/049_self-reference_cycles_conflicts_with_strings.txtar
index 875d6e0..e764e84 100644
--- a/cue/testdata/cycle/049_self-reference_cycles_conflicts_with_strings.txtar
+++ b/cue/testdata/cycle/049_self-reference_cycles_conflicts_with_strings.txtar
@@ -42,10 +42,6 @@
// ./in.cue:2:5
// ./in.cue:5:7
}
- y: (_|_){
- // [eval] a.x: conflicting values "hey!?" and "hey":
- // ./in.cue:2:5
- // ./in.cue:5:7
- }
+ y: (string){ "hey!" }
}
}
diff --git a/cue/testdata/cycle/structural.txtar b/cue/testdata/cycle/structural.txtar
index 4a19c49..798e68c 100644
--- a/cue/testdata/cycle/structural.txtar
+++ b/cue/testdata/cycle/structural.txtar
@@ -409,6 +409,7 @@
c1.a.c.c: structural cycle
d1.a.b.c.d.t: structural cycle
d1.r: structural cycle
+d2.r.c.d.t: structural cycle
e1.a.c: structural cycle
e1.b.c: structural cycle
e2.a.c: structural cycle
@@ -468,10 +469,6 @@
p5.#T.a.0.link: structural cycle
p6.#U.#T.a.0.link: structural cycle
z1.z.g.h: structural cycle
-b4.x.y.0.0: structural cycle:
- ./in.cue:53:8
-d2.r.c.d.t: structural cycle:
- ./in.cue:254:8
0: structural cycle:
./in.cue:264:19
@@ -561,9 +558,10 @@
b4: (_|_){
// [structural cycle]
b: (_|_){
- // [structural cycle] b4.x.y.0.0: structural cycle:
- // ./in.cue:53:8
- 0: (int){ 1 }
+ // [structural cycle]
+ 0: (_|_){
+ // [structural cycle] b4.x.y.0: structural cycle
+ }
}
x: (_|_){
// [structural cycle]
@@ -586,9 +584,7 @@
x: (struct){
y: (struct){
a: (#list){
- 0: ((int|list)){ |((#list){
- 0: (int){ int }
- }, (int){ int }) }
+ 0: (int){ int }
}
}
}
@@ -1053,8 +1049,14 @@
d2: (_|_){
// [structural cycle]
x: (_|_){
- // [structural cycle] d2.r.c.d.t: structural cycle:
- // ./in.cue:254:8
+ // [structural cycle]
+ d: (_|_){
+ // [structural cycle]
+ h: (int){ int }
+ t: (_|_){
+ // [structural cycle]
+ }
+ }
}
r: (_|_){
// [structural cycle]
@@ -1064,8 +1066,7 @@
// [structural cycle]
h: (int){ int }
t: (_|_){
- // [structural cycle] d2.r.c.d.t: structural cycle:
- // ./in.cue:254:8
+ // [structural cycle] d2.r.c.d.t: structural cycle
c: (_|_){// {
// d: {
// h: int
@@ -1088,6 +1089,16 @@
h: (int){ int }
t: (_|_){
// [structural cycle]
+ c: (_|_){
+ // [structural cycle]
+ d: (_|_){
+ // [structural cycle]
+ h: (int){ int }
+ t: (_|_){
+ // [structural cycle]
+ }
+ }
+ }
}
}
}
diff --git a/cue/testdata/eval/incomplete.txtar b/cue/testdata/eval/incomplete.txtar
index b72808d..2fb31ea 100644
--- a/cue/testdata/eval/incomplete.txtar
+++ b/cue/testdata/eval/incomplete.txtar
@@ -48,21 +48,19 @@
E: (struct){
a: (_|_){
// [cycle] cycle error:
- // ./in.cue:12:6
- // cycle error:
- // ./in.cue:13:6
+ // ./in.cue:11:6
}
b: (_|_){
// [cycle] cycle error:
- // ./in.cue:12:6
+ // ./in.cue:11:6
// cycle error:
- // ./in.cue:13:6
+ // ./in.cue:12:6
}
c: (_|_){
// [cycle] cycle error:
- // ./in.cue:12:6
+ // ./in.cue:11:6
// cycle error:
- // ./in.cue:13:6
+ // ./in.cue:12:6
}
}
permanentlyIncompleteOperands: (_|_){
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 22fbe13..377d3e3 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
@@ -49,11 +49,11 @@
n1: (struct){
min: (_|_){
// [cycle] cycle error:
- // ./in.cue:3:23
+ // ./in.cue:3:12
}
max: (_|_){
// [cycle] cycle error:
- // ./in.cue:3:23
+ // ./in.cue:3:12
}
}
n2: (_|_){
diff --git a/internal/core/adt/composite.go b/internal/core/adt/composite.go
index 13b4472..1915932 100644
--- a/internal/core/adt/composite.go
+++ b/internal/core/adt/composite.go
@@ -137,7 +137,7 @@
}
env, src := c.e, c.src
c.e, c.src = e, x.Source()
- v = c.eval(x)
+ v = c.evalState(x, Partial)
c.e, c.src = env, src
e.cache[x] = v
}
@@ -161,7 +161,13 @@
// Label is the feature leading to this vertex.
Label Feature
- // TODO: move the following status fields to a separate struct.
+ // State:
+ // eval: nil, BaseValue: nil -- unevaluated
+ // eval: *, BaseValue: nil -- evaluating
+ // eval: *, BaseValue: * -- finalized
+ //
+ state *nodeContext
+ // TODO: move the following status fields to nodeContext.
// status indicates the evaluation progress of this vertex.
status VertexStatus
@@ -245,6 +251,10 @@
// nodeContext to allow reusing the computations done so far.
Partial
+ // AllArcs is request only. It must be past Partial, but
+ // before recursively resolving arcs.
+ AllArcs
+
// EvaluatingArcs indicates that the arcs of the Vertex are currently being
// evaluated. If this is encountered it indicates a structural cycle.
// Value does not have to be nil
@@ -274,7 +284,6 @@
// Value returns the Value of v without definitions if it is a scalar
// or itself otherwise.
func (v *Vertex) Value() Value {
- // TODO: rename to Value.
switch x := v.BaseValue.(type) {
case nil:
return nil
@@ -425,6 +434,15 @@
if !ok {
return v
}
+ // b, _ := x.BaseValue.(*Bottom)
+ if n := x.state; n != nil && x.BaseValue == cycle {
+ if n.errs != nil && !n.errs.IsIncomplete() {
+ return n.errs
+ }
+ if n.scalar != nil {
+ return n.scalar
+ }
+ }
return x.Value()
}
@@ -575,13 +593,17 @@
// This is likely a bug in the evaluator and should not happen.
return &Bottom{Err: errors.Newf(token.NoPos, "cannot add conjunct")}
}
+ v.addConjunct(c)
+ return nil
+}
+
+func (v *Vertex) addConjunct(c Conjunct) {
for _, x := range v.Conjuncts {
if x == c {
- return nil
+ return
}
}
v.Conjuncts = append(v.Conjuncts, c)
- return nil
}
func (v *Vertex) AddStruct(s *StructLit, env *Environment, ci CloseInfo) *StructInfo {
diff --git a/internal/core/adt/context.go b/internal/core/adt/context.go
index 57d6446..37e62ec 100644
--- a/internal/core/adt/context.go
+++ b/internal/core/adt/context.go
@@ -504,7 +504,7 @@
func (c *OpContext) Evaluate(env *Environment, x Expr) (result Value, complete bool) {
s := c.PushState(env, x.Source())
- val := c.eval(x)
+ val := c.evalState(x, Partial)
complete = true
@@ -541,11 +541,6 @@
return v
}
-func (c *OpContext) eval(x Expr) (result Value) {
- v := c.evalState(x, Partial)
- return v
-}
-
func (c *OpContext) evalState(v Expr, state VertexStatus) (result Value) {
savedSrc := c.src
c.src = v.Source()
@@ -583,14 +578,11 @@
if c.HasErr() {
return nil
}
- if isIncomplete(arc) {
- if arc != nil {
- return arc.Value() // *Bottom
- }
+ if arc == nil {
return nil
}
- v := c.Unifier.Evaluate(c, arc)
+ v := c.Unifier.evaluate(c, arc, state)
return v
default:
@@ -728,7 +720,9 @@
func (c *OpContext) node(orig Node, x Expr, scalar bool) *Vertex {
// TODO: always get the vertex. This allows a whole bunch of trickery
// down the line.
- v := c.evalState(x, EvaluatingArcs)
+ // This must be partial, because
+ // TODO: this should always be "AllArcs"
+ v := c.evalState(x, AllArcs)
v, ok := c.getDefault(v)
if !ok {
diff --git a/internal/core/adt/disjunct.go b/internal/core/adt/disjunct.go
index 4772396..b47c32c 100644
--- a/internal/core/adt/disjunct.go
+++ b/internal/core/adt/disjunct.go
@@ -133,11 +133,16 @@
m defaultMode,
recursive bool) {
- n.eval.stats.DisjunctCount++
+ n.ctx.stats.DisjunctCount++
for n.expandOne() {
}
+ errNode := n
+ if parent != nil {
+ errNode = parent
+ }
+
// save node to snapShot in nodeContex
// save nodeContext.
@@ -165,25 +170,20 @@
err = x.ChildErrors
}
if err != nil {
- n.disjunctErrs = append(n.disjunctErrs, err)
+ errNode.disjunctErrs = append(errNode.disjunctErrs, err)
}
if recursive || len(n.disjunctions) > 0 {
- n.eval.freeNodeContext(n)
+ n.ctx.Unifier.freeNodeContext(n)
}
return
}
// TODO: clean up this mess:
- n.touched = true // move result setting here
result := *n.node // XXX: n.result = snapshotVertex(n.node)?
if result.BaseValue == nil {
result.BaseValue = n.getValidators()
}
- n.nodeShared.setResult(n.node)
- if n.node.BaseValue == nil {
- n.node.BaseValue = result.BaseValue
- }
if state < Finalized {
*n = m
}
@@ -191,6 +191,9 @@
n.disjuncts = append(n.disjuncts, n)
case len(n.disjunctions) > 0:
+ // Process full disjuncts to ensure that erroneous disjuncts are
+ // eliminated.
+ state = Finalized
n.disjuncts = append(n.disjuncts, n)
@@ -226,7 +229,7 @@
if i > 0 {
for _, d := range a {
- n.eval.freeNodeContext(d)
+ n.ctx.freeNodeContext(d)
}
}
@@ -251,12 +254,15 @@
// TODO: if only one value is left, set to maybeDefault.
switch p := parent; {
case p != nil:
+ p.disjunctErrs = append(p.disjunctErrs, n.disjunctErrs...)
+ n.disjunctErrs = n.disjunctErrs[:0]
+
k := 0
outer:
for _, d := range n.disjuncts {
for _, v := range p.disjuncts {
if Equal(n.ctx, &v.result, &d.result) {
- n.eval.freeNodeContext(n)
+ n.ctx.Unifier.freeNodeContext(n)
continue outer
}
}
@@ -270,11 +276,11 @@
n.disjuncts = n.disjuncts[:0]
case n.done():
- n.nodeShared.isDone = true
+ n.isDone = true
}
}
-func (n *nodeShared) makeError() {
+func (n *nodeContext) makeError() {
code := IncompleteError
if len(n.disjunctErrs) > 0 {
@@ -401,7 +407,7 @@
//
// TODO(perf): the set of errors is now computed during evaluation. Eventually,
// this could be done lazily.
-func (n *nodeShared) disjunctError() (errs errors.Error) {
+func (n *nodeContext) disjunctError() (errs errors.Error) {
ctx := n.ctx
disjuncts := selectErrors(n.disjunctErrs)
diff --git a/internal/core/adt/eval.go b/internal/core/adt/eval.go
index 960bb00..fc62de6 100644
--- a/internal/core/adt/eval.go
+++ b/internal/core/adt/eval.go
@@ -51,9 +51,10 @@
DisjunctCount int
UnifyCount int
- Freed int
- Reused int
- Allocs int
+ Freed int
+ Retained int
+ Reused int
+ Allocs int
}
var stats = template.Must(template.New("stats").Parse(`{{"" -}}
@@ -102,8 +103,7 @@
stats Stats
- freeListNode *nodeContext
- freeListShared *nodeShared
+ freeListNode *nodeContext
}
func (e *Unifier) Eval(v *Vertex) errors.Error {
@@ -129,36 +129,30 @@
//
// TODO: return *Vertex
func (e *Unifier) Evaluate(c *OpContext, v *Vertex) Value {
- var result Vertex
+ return e.evaluate(c, v, Partial)
+}
- if b, _ := v.BaseValue.(*Bottom); b != nil {
- return b
+func (e *Unifier) evaluate(c *OpContext, v *Vertex, state VertexStatus) Value {
+ if v.BaseValue == nil || v.BaseValue == cycle {
+ // Use node itself to allow for cycle detection.
+ e.Unify(c, v, state)
}
- if v.BaseValue == nil {
- save := *v
- // Use node itself to allow for cycle detection.
- s := e.evalVertex(c, v, Partial)
- defer e.freeSharedNode(s)
-
- result = *v
-
- if s.result_.BaseValue != nil { // There is a complete result.
- *v = s.result_
- // result = *v
- } else if b, ok := v.BaseValue.(*Bottom); ok {
- *v = save
- return b
- } else {
- *v = save
+ if n := v.state; n != nil {
+ if n.errs != nil && !n.errs.IsIncomplete() {
+ return n.errs
}
+ // TODO: consider enabling this
+ // if n.scalar != nil {
+ // return n.scalar
+ // }
+ }
- switch {
- case !s.touched:
-
- case len(s.disjuncts) == 1 || s.numDefaults == 1:
- // TODO: this seems unnecessary as long as we have a better way
- // to handle incomplete, and perhaps referenced. nodes.
+ switch x := v.BaseValue.(type) {
+ case *Bottom:
+ return x
+ case *Disjunction:
+ if x.NumDefaults == 1 {
if c.IsTentative() && isStruct(v) {
// TODO(perf): do something more efficient perhaps? This discards
// the computed arcs so far. Instead, we could have a separate
@@ -172,67 +166,25 @@
Conjuncts: v.Conjuncts,
}
w.UpdateStatus(v.Status())
- *v = save
return w
}
+ }
+ return x
- default:
- d := s.createDisjunct()
- last := len(d.Values) - 1
- clone := *(d.Values[last])
- d.Values[last] = &clone
-
- v.UpdateStatus(Finalized)
- v.BaseValue = d
- v.Arcs = nil
- v.Structs = nil // TODO: maybe not do this.
- // The conjuncts will have too much information. Better have no
- // information than incorrect information.
- for _, d := range d.Values {
- d.Conjuncts = nil
- for _, a := range d.Arcs {
- for _, x := range a.Conjuncts {
- // All the environments for embedded structs need to be
- // dereferenced.
- for env := x.Env; env != nil && env.Vertex == v; env = env.Up {
- env.Vertex = d
- }
- }
- }
+ case nil:
+ if v.state != nil {
+ switch x := v.state.getValidators().(type) {
+ case Value:
+ return x
+ default:
+ w := *v
+ w.BaseValue = x
+ return &w
}
-
- return d
}
-
- err, _ := result.BaseValue.(*Bottom)
- // BEFORE RESTORING, copy the value to return one
- // with the temporary arcs.
- if !s.done() && (err == nil || err.IsIncomplete()) {
- // Clear values afterwards
- *v = save
- }
- if s.hasResult() {
- if b, _ := v.BaseValue.(*Bottom); b != nil {
- *v = save
- return b
- }
- // TODO: Only use result when not a cycle.
- w := s.result()
- v = &w
- }
- // TODO: Store if concrete and fully resolved.
+ panic("nil value")
}
- // TODO: Use this and ensure that each use of Evaluate handles
- // struct numbers correctly. E.g. by using a function that
- // gets the concrete value.
- //
- if v.BaseValue == nil {
- if result.BaseValue == nil {
- panic("nil basevalue")
- }
- return &result
- }
return v
}
@@ -243,157 +195,174 @@
// defer c.PopVertex(c.PushVertex(v))
if state <= v.Status() {
- return
+ if v.Status() != Partial && state != Partial {
+ return
+ }
}
- if x := v.BaseValue; x != nil {
- // if state == Partial || x == cycle {
- // return
- // }
+ n := v.state
+
+ switch v.Status() {
+ case Evaluating:
return
- }
- n := e.evalVertex(c, v, state)
- defer e.freeSharedNode(n)
+ case EvaluatingArcs:
+ return
- switch {
- case len(n.disjuncts) == 1:
- *v = n.disjuncts[0].result
+ case 0:
+ // from state 0
+ n = e.newNodeContext(c, v)
- case len(n.disjuncts) > 0:
- d := n.createDisjunct()
- v.BaseValue = d
- // The conjuncts will have too much information. Better have no
- // information than incorrect information.
- for _, d := range d.Values {
- // We clear the conjuncts for now. As these disjuncts are for API
- // use only, we will fill them out when necessary (using Defaults).
- d.Conjuncts = nil
+ v.state = n
- // TODO: use a more principled form of dereferencing. For instance,
- // disjuncts could already be assumed to be the given Vertex, and
- // the the main vertex could be dereferenced during evaluation.
- for _, a := range d.Arcs {
- for _, x := range a.Conjuncts {
- // All the environments for embedded structs need to be
- // dereferenced.
- for env := x.Env; env != nil && env.Vertex == v; env = env.Up {
- env.Vertex = d
+ if v.Label.IsDef() {
+ v.Closed = true
+ }
+
+ ignore := false
+ if v.Parent != nil {
+ if v.Parent.Closed {
+ v.Closed = true
+ }
+ }
+
+ if !v.Label.IsInt() && v.Parent != nil && !ignore && state == Finalized {
+ // Visit arcs recursively to validate and compute error.
+ if _, err := verifyArc2(c, v.Label, v, v.Closed); err != nil {
+ // Record error in child node to allow recording multiple
+ // conflicts at the appropriate place, to allow valid fields to
+ // be represented normally and, most importantly, to avoid
+ // recursive processing of a disallowed field.
+ v.SetValue(c, Finalized, err)
+ return
+ }
+ }
+
+ defer c.PopArc(c.PushArc(v))
+
+ e.stats.UnifyCount++
+
+ // Clear any remaining error.
+ if err := c.Err(); err != nil {
+ panic("uncaught error")
+ }
+
+ // Set the cache to a cycle error to ensure a cyclic reference will result
+ // in an error if applicable. A cyclic error may be ignored for
+ // 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.
+ 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)
+ }
+
+ fallthrough
+
+ case Partial:
+ defer c.PopArc(c.PushArc(v))
+
+ // Use maybeSetCache for cycle breaking
+ for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() {
+ }
+
+ if !n.done() {
+ if len(n.disjunctions) > 0 && v.BaseValue == cycle {
+ // We disallow entering computations of disjunctions with
+ // incomplete data.
+ if state == Finalized {
+ b := c.NewErrf("incomplete cause disjunction")
+ b.Code = IncompleteError
+ n.errs = CombineErrors(nil, n.errs, b)
+ v.SetValue(n.ctx, Finalized, b)
+ } else {
+ n.node.UpdateStatus(Partial)
+ }
+ return
+ }
+ }
+
+ if !n.done() && state <= Partial {
+ n.node.UpdateStatus(Partial)
+ return
+ }
+
+ if s := v.Status(); state <= s {
+ // We have found a partial result. There may still be errors
+ // down the line which may result from further evaluating this
+ // field, but that will be caught when evaluating this field
+ // for real.
+
+ // This also covers the case where a recursive evaluation triggered
+ // this field to become finalized in the mean time. In that case
+ // we can avoid running another expandDisjuncts.
+ return
+ }
+
+ n.expandDisjuncts(state, nil, maybeDefault, false)
+
+ switch len(n.disjuncts) {
+ case 0:
+ case 1:
+ *v = n.disjuncts[0].result
+
+ default:
+ d := n.createDisjunct()
+ v.BaseValue = d
+ // The conjuncts will have too much information. Better have no
+ // information than incorrect information.
+ for _, d := range d.Values {
+ // We clear the conjuncts for now. As these disjuncts are for API
+ // use only, we will fill them out when necessary (using Defaults).
+ d.Conjuncts = nil
+
+ // TODO: use a more principled form of dereferencing. For instance,
+ // disjuncts could already be assumed to be the given Vertex, and
+ // the the main vertex could be dereferenced during evaluation.
+ for _, a := range d.Arcs {
+ for _, x := range a.Conjuncts {
+ // All the environments for embedded structs need to be
+ // dereferenced.
+ for env := x.Env; env != nil && env.Vertex == v; env = env.Up {
+ env.Vertex = d
+ }
}
}
}
+ v.Arcs = nil
+ // v.Structs = nil // TODO: should we keep or discard the Structs?
+ // TODO: how to represent closedness information? Do we need it?
}
- v.Arcs = nil
- // v.Structs = nil // TODO: should we keep or discard the Structs?
- // TODO: how to represent closedness information? Do we need it?
- default:
- if r := n.result(); r.BaseValue != nil {
- *v = r
+ if state != Finalized {
+ return
}
- }
- // Else set it to something.
-
- if v.BaseValue == nil {
- panic("error")
- }
-
- // Check whether result is done.
-}
-
-// evalVertex computes the vertex results. The state indicates the minimum
-// status to which this vertex should be evaluated. It should be either
-// Finalized or Partial.
-func (e *Unifier) evalVertex(c *OpContext, v *Vertex, state VertexStatus) *nodeShared {
- shared := e.newSharedNode(c, v)
-
- if v.Label.IsDef() {
- v.Closed = true
- }
-
- ignore := false
- if v.Parent != nil {
- if v.Parent.Closed {
- v.Closed = true
+ if v.BaseValue == nil {
+ v.BaseValue = n.getValidators()
}
+
+ // Free memory here?
+ v.UpdateStatus(Finalized)
+
+ case AllArcs:
+ defer c.PopArc(c.PushArc(v))
+
+ n.completeArcs(state)
+
+ case Finalized:
}
-
- if !v.Label.IsInt() && v.Parent != nil && !ignore && state == Finalized {
- // Visit arcs recursively to validate and compute error.
- if _, err := verifyArc2(c, v.Label, v, v.Closed); err != nil {
- // Record error in child node to allow recording multiple
- // conflicts at the appropriate place, to allow valid fields to
- // be represented normally and, most importantly, to avoid
- // recursive processing of a disallowed field.
- v.SetValue(c, Finalized, err)
- return shared
- }
- }
-
- defer c.PopArc(c.PushArc(v))
-
- e.stats.UnifyCount++
-
- // Clear any remaining error.
- if err := c.Err(); err != nil {
- panic("uncaught error")
- }
-
- // Set the cache to a cycle error to ensure a cyclic reference will result
- // in an error if applicable. A cyclic error may be ignored for
- // 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.
- 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.
- n := e.newNodeContext(shared)
-
- for _, x := range v.Conjuncts {
- // TODO: needed for reentrancy. Investigate usefulness for cycle
- // detection.
- n.addExprConjunct(x)
- }
-
- // Use maybeSetCache for cycle breaking
- for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() {
- }
- if v.Status() > Evaluating && state <= Partial {
- // We have found a partial result. There may still be errors
- // down the line which may result from further evaluating this
- // field, but that will be caught when evaluating this field
- // for real.
- shared.setResult(v)
- e.freeNodeContext(n)
- return shared
- }
-
- if !n.done() && len(n.disjunctions) > 0 && isEvaluating(v) {
- // We disallow entering computations of disjunctions with
- // incomplete data.
- b := c.NewErrf("incomplete cause disjunction")
- b.Code = IncompleteError
- v.SetValue(n.ctx, Finalized, b)
- shared.setResult(v)
- e.freeNodeContext(n)
- return shared
- }
-
- n.expandDisjuncts(state, nil, maybeDefault, false)
- // TODO: reorganize nodeShared and nodeContext
- n.nodeShared.disjuncts = append(n.nodeShared.disjuncts, n.disjuncts...)
- if v.BaseValue == nil {
- v.BaseValue = n.getValidators()
- }
- // e.freeNodeContext(n) freed in freeSharedNode
- return shared
}
func isStruct(v *Vertex) bool {
@@ -426,7 +395,7 @@
n.errs = nil
default:
- if isEvaluating(n.node) {
+ if n.node.BaseValue == cycle {
if !n.done() { // && !ctx.IsTentative() {
// collect incomplete errors.
var err *Bottom // n.incomplete
@@ -453,7 +422,8 @@
}
// We are no longer evaluating.
- n.node.UpdateStatus(Partial)
+ // n.node.UpdateStatus(Partial)
+ n.node.UpdateStatus(Evaluating)
// Either set to Conjunction or error.
// TODO: verify and simplify the below code to determine whether
@@ -497,21 +467,20 @@
n.addBottom(b)
}
}
- for _, v := range n.checks {
- // TODO(errors): make Validate return bottom and generate
- // optimized conflict message. Also track and inject IDs
- // to determine origin location.s
- if b := ctx.Validate(v, n.node); b != nil {
- n.addBottom(b)
+ // MOVE BELOW
+ if v := n.node.Value(); v != nil && IsConcrete(v) {
+ for _, v := range n.checks {
+ // TODO(errors): make Validate return bottom and generate
+ // optimized conflict message. Also track and inject IDs
+ // to determine origin location.s
+ if b := ctx.Validate(v, n.node); b != nil {
+ n.addBottom(b)
+ }
}
}
-
- } else if !ctx.IsTentative() {
+ } else if state == Finalized {
n.node.BaseValue = n.getValidators()
}
- // else if v == nil {
- // n.node.Value = incompleteSentinel
- // }
if v == nil {
break
@@ -551,6 +520,14 @@
}
func (n *nodeContext) completeArcs(state VertexStatus) {
+
+ if state <= AllArcs {
+ n.node.UpdateStatus(AllArcs)
+ return
+ }
+
+ n.node.UpdateStatus(EvaluatingArcs)
+
ctx := n.ctx
if cyclic := n.hasCycle && !n.hasNonCycle; cyclic {
@@ -567,17 +544,19 @@
for _, a := range n.node.Arcs {
// Call UpdateStatus here to be absolutely sure the status is set
// correctly and that we are not regressing.
- if state == Finalized {
- n.node.UpdateStatus(EvaluatingArcs)
+ n.node.UpdateStatus(EvaluatingArcs)
+ n.ctx.Unifier.Unify(ctx, a, state)
+ // Don't set the state to Finalized if the child arcs are not done.
+ if state == Finalized && a.status < Finalized {
+ state = AllArcs
}
- n.eval.Unify(ctx, a, state)
if err, _ := a.BaseValue.(*Bottom); err != nil {
n.node.AddChildError(err)
}
}
}
- n.node.UpdateStatus(Finalized)
+ n.node.UpdateStatus(state)
}
// TODO: this is now a sentinel. Use a user-facing error that traces where
@@ -587,79 +566,18 @@
Code: CycleError,
}
-func isEvaluating(v *Vertex) bool {
- isCycle := v.Status() == Evaluating
- if isCycle != (v.BaseValue == cycle) {
- panic(fmt.Sprintf("cycle data of sync %d vs %#v", v.Status(), v.BaseValue))
- }
- return isCycle
-}
-
-// TODO(perf): merge this type with nodeContext once we're certain we can
-// remove the distinction (after other optimizations).
-type nodeShared struct {
- nextFree *nodeShared
-
- eval *Unifier
- ctx *OpContext
- node *Vertex
-
- // Disjunction handling
- touched bool
- disjuncts []*nodeContext
- disjunctErrs []*Bottom
- numDefaults int
-
- result_ Vertex
- isDone bool
-}
-
-func (e *Unifier) newSharedNode(ctx *OpContext, node *Vertex) *nodeShared {
- if n := e.freeListShared; n != nil {
- e.stats.Reused++
- e.freeListShared = n.nextFree
-
- *n = nodeShared{
- eval: e,
- ctx: ctx,
- node: node,
-
- disjuncts: n.disjuncts[:0],
- disjunctErrs: n.disjunctErrs[:0],
- }
-
- return n
- }
- e.stats.Allocs++
-
- return &nodeShared{
- ctx: ctx,
- eval: e,
- node: node,
- }
-}
-
-func (e *Unifier) freeSharedNode(n *nodeShared) {
- e.stats.Freed++
- n.nextFree = e.freeListShared
- e.freeListShared = n
-
- for _, d := range n.disjuncts {
- e.freeNodeContext(d)
- }
-}
-
-func (n *nodeShared) createDisjunct() *Disjunction {
+func (n *nodeContext) createDisjunct() *Disjunction {
a := make([]*Vertex, len(n.disjuncts))
p := 0
for i, x := range n.disjuncts {
- v := x.result
+ v := new(Vertex)
+ *v = x.result
if x.defaultMode == isDefault {
a[i] = a[p]
- a[p] = &v
+ a[p] = v
p++
} else {
- a[i] = &v
+ a[i] = v
}
}
return &Disjunction{
@@ -668,22 +586,6 @@
}
}
-func (n *nodeShared) result() Vertex {
- return n.result_
-}
-
-func (n *nodeShared) setResult(v *Vertex) {
- n.result_ = *v
-}
-
-func (n *nodeShared) hasResult() bool {
- return len(n.disjuncts) > 0
-}
-
-func (n *nodeShared) done() bool {
- return n.isDone
-}
-
type arcKey struct {
arc *Vertex
id CloseInfo
@@ -696,7 +598,8 @@
type nodeContext struct {
nextFree *nodeContext
- *nodeShared
+ ctx *OpContext
+ node *Vertex
// TODO: (this is CL is first step)
// filter *Vertex a subset of composite with concrete fields for
@@ -742,16 +645,21 @@
hasTop bool
hasCycle bool // has conjunct with structural cycle
hasNonCycle bool // has conjunct without structural cycle
+ isDone bool
// Disjunction handling
disjunctions []envDisjunct
defaultMode defaultMode
disjuncts []*nodeContext
buffer []*nodeContext
+ disjunctErrs []*Bottom
}
func (n *nodeContext) clone() *nodeContext {
- d := n.eval.newNodeContext(n.nodeShared)
+ d := n.ctx.Unifier.newNodeContext(n.ctx, n.node)
+
+ d.ctx = n.ctx
+ d.node = n.node
d.scalar = n.scalar
d.scalarID = n.scalarID
@@ -782,14 +690,15 @@
return d
}
-func (e *Unifier) newNodeContext(shared *nodeShared) *nodeContext {
+func (e *Unifier) newNodeContext(ctx *OpContext, node *Vertex) *nodeContext {
if n := e.freeListNode; n != nil {
e.stats.Reused++
e.freeListNode = n.nextFree
*n = nodeContext{
+ ctx: ctx,
+ node: node,
kind: TopKind,
- nodeShared: shared,
arcMap: n.arcMap[:0],
checks: n.checks[:0],
dynamicFields: n.dynamicFields[:0],
@@ -799,6 +708,7 @@
vLists: n.vLists[:0],
exprs: n.exprs[:0],
disjunctions: n.disjunctions[:0],
+ disjunctErrs: n.disjunctErrs[:0],
disjuncts: n.disjuncts[:0],
buffer: n.buffer[:0],
}
@@ -808,15 +718,28 @@
e.stats.Allocs++
return &nodeContext{
- kind: TopKind,
- nodeShared: shared,
+ ctx: ctx,
+ node: node,
+ kind: TopKind,
}
}
+func (v *Vertex) getNodeContext(c *OpContext) *nodeContext {
+ if v.state != nil {
+ if v.status == Finalized {
+ panic("dangling node")
+ }
+ return v.state
+ }
+ v.state = c.Unifier.newNodeContext(c, v)
+ return v.state
+}
+
func (e *Unifier) freeNodeContext(n *nodeContext) {
- e.stats.Freed++
- n.nextFree = e.freeListNode
- e.freeListNode = n
+ // TODO: re-enable memory management.
+ // e.stats.Freed++
+ // n.nextFree = e.freeListNode
+ // e.freeListNode = n
}
// TODO(perf): return a dedicated ConflictError that can track original
@@ -953,16 +876,18 @@
return v
}
+// TODO: this function can probably go as this is now handled in the nodeContext.
func (n *nodeContext) maybeSetCache() {
- if n.node.Status() > Evaluating { // n.node.BaseValue != nil
+ if n.node.Status() > Partial { // n.node.BaseValue != nil
return
}
if n.scalar != nil {
n.node.SetValue(n.ctx, Partial, n.scalar)
}
- if n.errs != nil {
- n.node.SetValue(n.ctx, Partial, n.errs)
- }
+ // NOTE: this is now handled by associating the nodeContext
+ // if n.errs != nil {
+ // n.node.SetValue(n.ctx, Partial, n.errs)
+ // }
}
type envExpr struct {
@@ -1641,16 +1566,41 @@
ctx := n.ctx
arc, isNew := n.node.GetArc(f)
- // TODO: disallow adding conjuncts when cache set?
- arc.AddConjunct(x)
+ arc.addConjunct(x)
- if isNew {
+ switch {
+ case isNew:
for _, s := range n.node.Structs {
if s.Disable {
continue
}
s.MatchAndInsert(ctx, arc)
}
+
+ case arc.state != nil:
+ s := arc.state
+ switch {
+ case arc.Status() <= AllArcs:
+ // This may happen when a struct has multiple comprehensions, where
+ // the insertion of one of which depends on the outcome of another.
+
+ // TODO: to something more principled by allowing values to
+ // monotonically increase.
+ arc.status = Partial
+ arc.BaseValue = nil
+ s.disjuncts = s.disjuncts[:0]
+ s.disjunctErrs = s.disjunctErrs[:0]
+
+ fallthrough
+
+ default:
+ arc.state.addExprConjunct(x)
+ }
+
+ case arc.Status() == 0:
+ default:
+ // TODO: handle adding to finalized conjunct
+ panic("unhandled")
}
return arc
}
diff --git a/internal/core/adt/expr.go b/internal/core/adt/expr.go
index 7bbe8dc..4563e88 100644
--- a/internal/core/adt/expr.go
+++ b/internal/core/adt/expr.go
@@ -1071,7 +1071,7 @@
if result == nil {
return nil
}
- return c.eval(result)
+ return c.evalState(result, Partial)
}
// A Builtin is a value representing a native function call.
diff --git a/internal/core/eval/eval.go b/internal/core/eval/eval.go
index ccbfd0c..238db33 100644
--- a/internal/core/eval/eval.go
+++ b/internal/core/eval/eval.go
@@ -39,10 +39,6 @@
e *adt.Unifier
}
-func (e *Unifier) Evaluate(ctx *adt.OpContext, v *adt.Vertex) adt.Value {
- return e.e.Evaluate(ctx, v)
-}
-
func (e *Unifier) Unify(ctx *adt.OpContext, v *adt.Vertex, state adt.VertexStatus) {
e.e.Unify(ctx, v, state)
}
diff --git a/internal/core/validate/validate_test.go b/internal/core/validate/validate_test.go
index 0ca51fa..f23f6fe 100644
--- a/internal/core/validate/validate_test.go
+++ b/internal/core/validate/validate_test.go
@@ -121,7 +121,7 @@
y: x + 1
x: y - 1
`,
- out: "cycle\ncycle error:\n test:3:6",
+ out: "cycle\ncycle error:\n test:2:6",
}, {
desc: "disallow cycle",
cfg: &Config{DisallowCycles: true},
@@ -129,7 +129,7 @@
a: b - 100
b: a + 100
c: [c[1], c[0]] `,
- out: "cycle\ncycle error:\n test:3:6",
+ out: "cycle\ncycle error:\n test:2:6",
}, {
desc: "treat cycles as incomplete when not disallowing",
cfg: &Config{},
