| // Copyright 2020 CUE Authors |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // Package eval contains the high level CUE evaluation strategy. |
| // |
| // CUE allows for a significant amount of freedom in order of evaluation due to |
| // the commutativity of the unification operation. This package implements one |
| // of the possible strategies. |
| package eval |
| |
| // TODO: |
| // - result should be nodeContext: this allows optionals info to be extracted |
| // and computed. |
| // |
| |
| import ( |
| "fmt" |
| "html/template" |
| "strings" |
| |
| "cuelang.org/go/cue/ast" |
| "cuelang.org/go/cue/errors" |
| "cuelang.org/go/cue/token" |
| "cuelang.org/go/internal/core/adt" |
| "cuelang.org/go/internal/core/debug" |
| ) |
| |
| var Debug = false |
| |
| // TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO |
| // |
| // - Reuse work from previous cycles. For instance, if we can guarantee that a |
| // value is always correct for partial results, we can just process the arcs |
| // going from Partial to Finalized, without having to reevaluate the value. |
| // |
| // - Test closedness far more thoroughly. |
| // |
| |
| func Evaluate(r adt.Runtime, v *adt.Vertex) { |
| format := func(n adt.Node) string { |
| return debug.NodeString(r, n, printConfig) |
| } |
| e := New(r) |
| c := adt.New(v, &adt.Config{ |
| Runtime: r, |
| Unifier: e, |
| Format: format, |
| }) |
| e.Unify(c, v, adt.Finalized) |
| } |
| |
| func New(r adt.Runtime) *Evaluator { |
| return &Evaluator{r: r, index: r} |
| } |
| |
| type Stats struct { |
| DisjunctCount int |
| UnifyCount int |
| |
| Freed int |
| Reused int |
| Allocs int |
| } |
| |
| var stats = template.Must(template.New("stats").Parse(`{{"" -}} |
| Freed: {{.Freed}} |
| Reused: {{.Reused}} |
| Allocs: {{.Allocs}} |
| |
| Unifications: {{.UnifyCount}} |
| Disjuncts: {{.DisjunctCount}}`)) |
| |
| func (s *Stats) String() string { |
| buf := &strings.Builder{} |
| _ = stats.Execute(buf, s) |
| return buf.String() |
| } |
| |
| func (e *Evaluator) Stats() *Stats { |
| return &e.stats |
| } |
| |
| // TODO: Note: NewContext takes essentially a cue.Value. By making this |
| // type more central, we can perhaps avoid context creation. |
| |
| func NewContext(r adt.Runtime, v *adt.Vertex) *adt.OpContext { |
| e := New(r) |
| return e.NewContext(v) |
| } |
| |
| var printConfig = &debug.Config{Compact: true} |
| |
| func (e *Evaluator) NewContext(v *adt.Vertex) *adt.OpContext { |
| format := func(n adt.Node) string { |
| return debug.NodeString(e.r, n, printConfig) |
| } |
| return adt.New(v, &adt.Config{ |
| Runtime: e.r, |
| Unifier: e, |
| Format: format, |
| }) |
| } |
| |
| var structSentinel = &adt.StructMarker{} |
| |
| var incompleteSentinel = &adt.Bottom{ |
| Code: adt.IncompleteError, |
| Err: errors.Newf(token.NoPos, "incomplete"), |
| } |
| |
| type Evaluator struct { |
| r adt.Runtime |
| index adt.StringIndexer |
| |
| stats Stats |
| |
| freeListNode *nodeContext |
| freeListShared *nodeShared |
| } |
| |
| func (e *Evaluator) Eval(v *adt.Vertex) errors.Error { |
| if v.BaseValue == nil { |
| ctx := adt.NewContext(e.r, e, v) |
| e.Unify(ctx, v, adt.Partial) |
| } |
| |
| // extract error if needed. |
| return nil |
| } |
| |
| // Evaluate is used to evaluate a sub expression while evaluating a Vertex |
| // with Unify. It may or may not return the original Vertex. It may also |
| // terminate evaluation early if it has enough evidence that a certain value |
| // can be the only value in a valid configuration. This means that an error |
| // may go undetected at this point, as long as it is caught later. |
| // |
| // TODO: return *adt.Vertex |
| func (e *Evaluator) Evaluate(c *adt.OpContext, v *adt.Vertex) adt.Value { |
| var result adt.Vertex |
| |
| if b, _ := v.BaseValue.(*adt.Bottom); b != nil { |
| return b |
| } |
| |
| if v.BaseValue == nil { |
| save := *v |
| // Use node itself to allow for cycle detection. |
| s := e.evalVertex(c, v, adt.Partial, nil) |
| 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.(*adt.Bottom); ok { |
| *v = save |
| return b |
| } else { |
| *v = save |
| } |
| |
| switch { |
| case !s.touched: |
| |
| case len(s.disjunct.Values) == 1 || s.disjunct.NumDefaults == 1: |
| // TODO: this seems unnecessary as long as we have a better way |
| // to handle incomplete, and perhaps referenced. nodes. |
| 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 |
| // marker to accumulate results. As this only happens within |
| // comprehensions, the effect is likely minimal, though. |
| arcs := v.Arcs |
| w := &adt.Vertex{ |
| Parent: v.Parent, |
| BaseValue: &adt.StructMarker{}, |
| Arcs: arcs, |
| Conjuncts: v.Conjuncts, |
| Closed: s.result_.Closed, |
| } |
| w.UpdateStatus(v.Status()) |
| *v = save |
| return w |
| } |
| |
| default: |
| d := s.createDisjunct() |
| last := len(d.Values) - 1 |
| clone := *(d.Values[last]) |
| d.Values[last] = &clone |
| |
| 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 |
| } |
| } |
| } |
| } |
| |
| return d |
| } |
| |
| err, _ := result.BaseValue.(*adt.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.(*adt.Bottom); b != nil { |
| *v = save |
| return b |
| } |
| // TODO: Only use result when not a cycle. |
| v = s.result() |
| } |
| // TODO: Store if concrete and fully resolved. |
| } |
| |
| // 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 { |
| return &result |
| } |
| return v |
| } |
| |
| // Unify implements adt.Unifier. |
| // |
| // May not evaluate the entire value, but just enough to be able to compute. |
| // |
| // Phase one: record everything concrete |
| // Phase two: record incomplete |
| // Phase three: record cycle. |
| func (e *Evaluator) Unify(c *adt.OpContext, v *adt.Vertex, state adt.VertexStatus) { |
| e.UnifyAccept(c, v, state, nil) //v.Closed) |
| } |
| |
| // UnifyAccept is like Unify, but takes an extra argument to override the |
| // accepted set of fields. |
| // |
| // Instead of deriving the allowed set of fields, it verifies this set by |
| // consulting the given Acceptor. This can be useful when splitting an existing |
| // values into individual conjuncts and then unifying some of its components |
| // back into a new value. Under normal circumstances, this may not always |
| // succeed as the missing context may result in stricter closedness rules. |
| func (e *Evaluator) UnifyAccept(c *adt.OpContext, v *adt.Vertex, state adt.VertexStatus, accept adt.Acceptor) { |
| |
| // defer c.PopVertex(c.PushVertex(v)) |
| |
| if state <= v.Status() { |
| return |
| } |
| |
| if x := v.BaseValue; x != nil { |
| // if state == adt.Partial || x == cycle { |
| // return |
| // } |
| return |
| } |
| |
| n := e.evalVertex(c, v, state, accept) |
| defer e.freeSharedNode(n) |
| |
| switch { |
| case len(n.disjunct.Values) == 1: |
| *v = *(n.disjunct.Values[0]) |
| |
| case len(n.disjunct.Values) > 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 |
| |
| // 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? |
| v.Closed = newDisjunctionAcceptor(d) // TODO: remove? |
| |
| default: |
| if r := n.result(); r.BaseValue != nil { |
| *v = *r |
| } |
| } |
| |
| // 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 |
| // adt.Finalized or adt.Partial. |
| func (e *Evaluator) evalVertex(c *adt.OpContext, v *adt.Vertex, state adt.VertexStatus, accept adt.Acceptor) *nodeShared { |
| shared := e.newSharedNode(c, v, accept) |
| saved := *v |
| |
| var closedInfo *acceptor |
| if v.Parent != nil { |
| closedInfo, _ = v.Parent.Closed.(*acceptor) |
| } |
| |
| if !v.Label.IsInt() && closedInfo != nil && !closedInfo.ignore { |
| ci := closedInfo |
| // Visit arcs recursively to validate and compute error. |
| switch ok, err := ci.verifyArc(c, v.Label, v); { |
| case 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.BaseValue = err |
| v.SetValue(c, adt.Finalized, err) |
| return shared |
| |
| case !ok: // hidden field |
| // A hidden field is exempt from checking. Ensure that the |
| // closedness doesn't carry over into children. |
| // TODO: make this more fine-grained per package, allowing |
| // checked restrictions to be defined within the package. |
| closedInfo = closedInfo.clone() |
| for i := range closedInfo.Canopy { |
| closedInfo.Canopy[i].IsDef = false |
| } |
| } |
| } |
| |
| defer c.PopArc(c.PushArc(v)) |
| |
| e.stats.UnifyCount++ |
| for i := 0; ; i++ { |
| e.stats.DisjunctCount++ |
| |
| // 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 = saved |
| v.BaseValue = cycle |
| |
| if closedInfo != nil { |
| ci := closedInfo.clone() |
| v.Closed = ci |
| // TODO(performance): use closedInfo.Compact. |
| // TODO: should be clear the list flag here? |
| } |
| |
| v.UpdateStatus(adt.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) |
| n.needClose = v.Label.IsDef() |
| |
| for _, x := range v.Conjuncts { |
| // TODO: needed for reentrancy. Investigate usefulness for cycle |
| // detection. |
| n.addExprConjunct(x) |
| } |
| |
| if i == 0 { |
| // Use maybeSetCache for cycle breaking |
| for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() { |
| } |
| if v.Status() > adt.Evaluating && state <= adt.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 = adt.IncompleteError |
| v.SetValue(n.ctx, adt.Finalized, b) |
| shared.setResult(v) |
| e.freeNodeContext(n) |
| return shared |
| } |
| } |
| |
| // Handle disjunctions. If there are no disjunctions, this call is |
| // equivalent to calling n.postDisjunct. |
| if n.tryDisjuncts(state) { |
| if v.BaseValue == nil { |
| v.BaseValue = n.getValidators() |
| } |
| |
| e.freeNodeContext(n) |
| break |
| } |
| } |
| |
| return shared |
| } |
| |
| func isStruct(v *adt.Vertex) bool { |
| _, ok := v.BaseValue.(*adt.StructMarker) |
| return ok |
| } |
| |
| func (n *nodeContext) postDisjunct(state adt.VertexStatus) { |
| ctx := n.ctx |
| |
| for { |
| // Use maybeSetCache for cycle breaking |
| for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() { |
| } |
| |
| if aList, id := n.addLists(ctx); aList != nil { |
| n.updateNodeType(adt.ListKind, aList, id) |
| } else { |
| break |
| } |
| } |
| |
| if n.aStruct != nil { |
| n.updateNodeType(adt.StructKind, n.aStruct, n.aStructID) |
| } |
| |
| switch err := n.getErr(); { |
| case err != nil: |
| n.node.BaseValue = err |
| n.errs = nil |
| |
| default: |
| if isEvaluating(n.node) { |
| if !n.done() { // && !ctx.IsTentative() { |
| // collect incomplete errors. |
| var err *adt.Bottom // n.incomplete |
| for _, d := range n.dynamicFields { |
| err = adt.CombineErrors(nil, err, d.err) |
| } |
| for _, c := range n.forClauses { |
| err = adt.CombineErrors(nil, err, c.err) |
| } |
| for _, c := range n.ifClauses { |
| err = adt.CombineErrors(nil, err, c.err) |
| } |
| for _, x := range n.exprs { |
| err = adt.CombineErrors(nil, err, x.err) |
| } |
| if err == nil { |
| // safeguard. |
| err = incompleteSentinel |
| } |
| n.node.BaseValue = err |
| } else { |
| n.node.BaseValue = nil |
| } |
| } |
| |
| // We are no longer evaluating. |
| n.node.UpdateStatus(adt.Partial) |
| |
| // Either set to Conjunction or error. |
| // TODO: verify and simplify the below code to determine whether |
| // something is a struct. |
| markStruct := false |
| if n.aStruct != nil { |
| markStruct = true |
| } else if len(n.node.Structs) > 0 { |
| markStruct = n.kind&adt.StructKind != 0 && !n.hasTop |
| } |
| v := n.node.Value() |
| if n.node.BaseValue == nil && markStruct { |
| n.node.BaseValue = &adt.StructMarker{} |
| v = n.node |
| } |
| if v != nil && adt.IsConcrete(v) { |
| // Also check when we already have errors as we may find more |
| // serious errors and would like to know about all errors anyway. |
| |
| if n.lowerBound != nil { |
| if b := ctx.Validate(n.lowerBound, v); b != nil { |
| // TODO(errors): make Validate return boolean and generate |
| // optimized conflict message. Also track and inject IDs |
| // to determine origin location.s |
| if e, _ := b.Err.(*adt.ValueError); e != nil { |
| e.AddPosition(n.lowerBound) |
| e.AddPosition(v) |
| } |
| n.addBottom(b) |
| } |
| } |
| if n.upperBound != nil { |
| if b := ctx.Validate(n.upperBound, v); b != nil { |
| // TODO(errors): make Validate return boolean and generate |
| // optimized conflict message. Also track and inject IDs |
| // to determine origin location.s |
| if e, _ := b.Err.(*adt.ValueError); e != nil { |
| e.AddPosition(n.upperBound) |
| e.AddPosition(v) |
| } |
| 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) |
| } |
| } |
| |
| } else if !ctx.IsTentative() { |
| n.node.BaseValue = n.getValidators() |
| } |
| // else if v == nil { |
| // n.node.Value = incompleteSentinel |
| // } |
| |
| if v == nil { |
| break |
| } |
| |
| switch { |
| case v.Kind() == adt.ListKind: |
| for _, a := range n.node.Arcs { |
| if a.Label.Typ() == adt.StringLabel { |
| n.addErr(ctx.Newf("list may not have regular fields")) |
| // TODO(errors): add positions for list and arc definitions. |
| |
| } |
| } |
| |
| // case !isStruct(n.node) && v.Kind() != adt.BottomKind: |
| // for _, a := range n.node.Arcs { |
| // if a.Label.IsRegular() { |
| // n.addErr(errors.Newf(token.NoPos, |
| // // TODO(errors): add positions of non-struct values and arcs. |
| // "cannot combine scalar values with arcs")) |
| // } |
| // } |
| } |
| } |
| |
| n.updateClosedInfo() |
| |
| n.completeArcs(state) |
| } |
| |
| func (n *nodeContext) completeArcs(state adt.VertexStatus) { |
| ctx := n.ctx |
| |
| if cyclic := n.hasCycle && !n.hasNonCycle; cyclic { |
| n.node.BaseValue = adt.CombineErrors(nil, |
| n.node.Value(), |
| &adt.Bottom{ |
| Code: adt.StructuralCycleError, |
| Err: ctx.Newf("structural cycle"), |
| Value: n.node.Value(), |
| // TODO: probably, this should have the referenced arc. |
| }) |
| } else { |
| // Visit arcs recursively to validate and compute error. |
| 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 == adt.Finalized { |
| n.node.UpdateStatus(adt.EvaluatingArcs) |
| } |
| n.eval.Unify(ctx, a, adt.Finalized) |
| if err, _ := a.BaseValue.(*adt.Bottom); err != nil { |
| n.node.AddChildError(err) |
| } |
| } |
| } |
| |
| n.node.UpdateStatus(adt.Finalized) |
| } |
| |
| func (n *nodeContext) updateClosedInfo() { |
| if err := n.getErr(); err != nil { |
| if b, _ := n.node.BaseValue.(*adt.Bottom); b != nil { |
| err = adt.CombineErrors(nil, b, err) |
| } |
| n.node.BaseValue = err |
| // TODO: add return: if evaluation of arcs is important it can be done |
| // later. Logically we're done. |
| } |
| |
| a, _ := n.node.Closed.(*acceptor) |
| if a == nil { |
| if !n.node.IsList() && !n.needClose { |
| return |
| } |
| a = closedInfo(n.node) |
| } |
| |
| // TODO: set this earlier. |
| n.needClose = n.needClose || a.isClosed |
| a.isClosed = n.needClose |
| |
| // TODO: consider removing this. Now checking is done at the top of |
| // evalVertex, skipping one level of checks happens naturally again |
| // for Value.Unify (API). |
| ctx := n.ctx |
| |
| // TODO: record the list length for the acceptor, possibly. But the |
| // length matching should already have been done. |
| if accept := n.nodeShared.accept; accept != nil && !n.node.IsList() { |
| for _, a := range n.node.Arcs { |
| if !accept.Accept(n.ctx, a.Label) { |
| label := a.Label.SelectorString(ctx) |
| n.node.BaseValue = ctx.NewErrf( |
| "field `%s` not allowed by Acceptor", label) |
| } |
| } |
| } |
| } |
| |
| // TODO: this is now a sentinel. Use a user-facing error that traces where |
| // the cycle originates. |
| var cycle = &adt.Bottom{ |
| Err: errors.Newf(token.NoPos, "cycle error"), |
| Code: adt.CycleError, |
| } |
| |
| func isEvaluating(v *adt.Vertex) bool { |
| isCycle := v.Status() == adt.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 *Evaluator |
| ctx *adt.OpContext |
| node *adt.Vertex |
| |
| // Disjunction handling |
| touched bool |
| disjunct adt.Disjunction |
| disjunctErrs []*adt.Bottom |
| |
| result_ adt.Vertex |
| isDone bool |
| stack []int |
| |
| // Closedness override. |
| accept adt.Acceptor |
| } |
| |
| func (e *Evaluator) newSharedNode(ctx *adt.OpContext, node *adt.Vertex, accept adt.Acceptor) *nodeShared { |
| if n := e.freeListShared; n != nil { |
| e.stats.Reused++ |
| e.freeListShared = n.nextFree |
| |
| *n = nodeShared{ |
| eval: e, |
| ctx: ctx, |
| node: node, |
| accept: accept, |
| |
| stack: n.stack[:0], |
| disjunct: adt.Disjunction{Values: n.disjunct.Values[:0]}, |
| disjunctErrs: n.disjunctErrs[:0], |
| } |
| |
| return n |
| } |
| e.stats.Allocs++ |
| |
| return &nodeShared{ |
| ctx: ctx, |
| eval: e, |
| node: node, |
| accept: accept, |
| } |
| } |
| |
| func (e *Evaluator) freeSharedNode(n *nodeShared) { |
| e.stats.Freed++ |
| n.nextFree = e.freeListShared |
| e.freeListShared = n |
| } |
| |
| func (n *nodeShared) createDisjunct() *adt.Disjunction { |
| a := make([]*adt.Vertex, len(n.disjunct.Values)) |
| copy(a, n.disjunct.Values) |
| return &adt.Disjunction{ |
| Values: a, |
| NumDefaults: n.disjunct.NumDefaults, |
| } |
| } |
| |
| func (n *nodeShared) result() *adt.Vertex { |
| return &n.result_ |
| } |
| |
| func (n *nodeShared) setResult(v *adt.Vertex) { |
| n.result_ = *v |
| } |
| |
| func (n *nodeShared) hasResult() bool { |
| return len(n.disjunct.Values) > 1 |
| } |
| |
| func (n *nodeShared) done() bool { |
| return n.isDone |
| } |
| |
| func (n *nodeShared) isDefault() bool { |
| return n.disjunct.NumDefaults > 0 |
| } |
| |
| type arcKey struct { |
| arc *adt.Vertex |
| id adt.ID |
| } |
| |
| // A nodeContext is used to collate all conjuncts of a value to facilitate |
| // unification. Conceptually order of unification does not matter. However, |
| // order has relevance when performing checks of non-monotic properities. Such |
| // checks should only be performed once the full value is known. |
| type nodeContext struct { |
| nextFree *nodeContext |
| |
| *nodeShared |
| |
| // TODO: |
| // filter *adt.Vertex a subset of composite with concrete fields for |
| // bloom-like filtering of disjuncts. We should first verify, however, |
| // whether some breath-first search gives sufficient performance, as this |
| // should already ensure a quick-fail for struct disjunctions with |
| // discriminators. |
| |
| arcMap map[arcKey]bool |
| |
| // Current value (may be under construction) |
| scalar adt.Value // TODO: use Value in node. |
| scalarID adt.ID |
| |
| // Concrete conjuncts |
| kind adt.Kind |
| kindExpr adt.Expr // expr that adjust last value (for error reporting) |
| kindID adt.ID // for error tracing |
| lowerBound *adt.BoundValue // > or >= |
| upperBound *adt.BoundValue // < or <= |
| checks []adt.Validator // BuiltinValidator, other bound values. |
| errs *adt.Bottom |
| incomplete *adt.Bottom |
| |
| // Struct information |
| dynamicFields []envDynamic |
| ifClauses []envYield |
| forClauses []envYield |
| // TODO: remove this and annotate directly in acceptor. |
| needClose bool |
| aStruct adt.Expr |
| aStructID adt.ID |
| hasTop bool |
| |
| // Expression conjuncts |
| lists []envList |
| vLists []*adt.Vertex |
| exprs []envExpr |
| |
| hasCycle bool // has conjunct with structural cycle |
| hasNonCycle bool // has conjunct without structural cycle |
| |
| // Disjunction handling |
| disjunctions []envDisjunct |
| subDisjunctions []envDisjunct |
| defaultMode defaultMode |
| isFinal bool |
| } |
| |
| func (e *Evaluator) newNodeContext(shared *nodeShared) *nodeContext { |
| if n := e.freeListNode; n != nil { |
| e.stats.Reused++ |
| e.freeListNode = n.nextFree |
| |
| *n = nodeContext{ |
| // TODO(perf): use another technique that doesn't require allocation. |
| // arcMap: map[arcKey]bool{}, |
| |
| kind: adt.TopKind, |
| nodeShared: shared, |
| isFinal: true, |
| |
| checks: n.checks[:0], |
| dynamicFields: n.dynamicFields[:0], |
| ifClauses: n.ifClauses[:0], |
| forClauses: n.forClauses[:0], |
| lists: n.lists[:0], |
| vLists: n.vLists[:0], |
| exprs: n.exprs[:0], |
| disjunctions: n.disjunctions[:0], |
| subDisjunctions: n.subDisjunctions[:0], |
| } |
| |
| return n |
| } |
| e.stats.Allocs++ |
| |
| return &nodeContext{ |
| // arcMap: map[arcKey]bool{}, |
| kind: adt.TopKind, |
| nodeShared: shared, |
| |
| // These get cleared upon proof to the contrary. |
| isFinal: true, |
| } |
| } |
| |
| func (e *Evaluator) freeNodeContext(n *nodeContext) { |
| e.stats.Freed++ |
| n.nextFree = e.freeListNode |
| e.freeListNode = n |
| } |
| |
| func closedInfo(n *adt.Vertex) *acceptor { |
| a, _ := n.Closed.(*acceptor) |
| if a == nil { |
| a = &acceptor{} |
| n.Closed = a |
| } |
| return a |
| } |
| |
| // TODO(errors): return a dedicated ConflictError that can track original |
| // positions on demand. |
| // |
| // Fully detailed origin tracking could be created on the back of CloseIDs |
| // tracked in acceptor.Canopy. To make this fully functional, the following |
| // still needs to be implemented: |
| // |
| // - We need to know the ID for every value involved in the conflict. |
| // (There may be multiple if the result comes from a simplification). |
| // - CloseIDs should be forked not only for definitions, but all references. |
| // - Upon forking a CloseID, it should keep track of its enclosing CloseID |
| // as well (probably as a pointer to the origin so that the reference |
| // persists after compaction). |
| // |
| // The modifications to the CloseID algorithm may also benefit the computation |
| // of `{ #A } == #A`, which currently is not done. |
| // |
| func (n *nodeContext) addConflict( |
| v1, v2 adt.Node, |
| k1, k2 adt.Kind, |
| id1, id2 adt.ID) { |
| |
| ctx := n.ctx |
| |
| var err *adt.ValueError |
| if k1 == k2 { |
| err = ctx.NewPosf(token.NoPos, |
| "conflicting values %s and %s", ctx.Str(v1), ctx.Str(v2)) |
| } else { |
| err = ctx.NewPosf(token.NoPos, |
| "conflicting values %s and %s (mismatched types %s and %s)", |
| ctx.Str(v1), ctx.Str(v2), k1, k2) |
| } |
| |
| ci := closedInfo(n.node) |
| err.AddPosition(v1) |
| err.AddPosition(v2) |
| err.AddPosition(ci.node(id1).Src) |
| err.AddPosition(ci.node(id2).Src) |
| |
| n.addErr(err) |
| } |
| |
| func (n *nodeContext) updateNodeType(k adt.Kind, v adt.Expr, id adt.ID) bool { |
| ctx := n.ctx |
| kind := n.kind & k |
| |
| switch { |
| case n.kind == adt.BottomKind, |
| k == adt.BottomKind: |
| return false |
| |
| case kind == adt.BottomKind: |
| if n.kindExpr != nil { |
| n.addConflict(n.kindExpr, v, n.kind, k, n.kindID, id) |
| } else { |
| n.addErr(ctx.Newf( |
| "conflicting value %s (mismatched types %s and %s)", |
| ctx.Str(v), n.kind, k)) |
| } |
| } |
| |
| if n.kind != kind || n.kindExpr == nil { |
| n.kindExpr = v |
| } |
| n.kind = kind |
| return kind != adt.BottomKind |
| } |
| |
| func (n *nodeContext) done() bool { |
| return len(n.dynamicFields) == 0 && |
| len(n.ifClauses) == 0 && |
| len(n.forClauses) == 0 && |
| len(n.exprs) == 0 |
| } |
| |
| // hasErr is used to determine if an evaluation path, for instance a single |
| // path after expanding all disjunctions, has an error. |
| func (n *nodeContext) hasErr() bool { |
| if n.node.ChildErrors != nil { |
| return true |
| } |
| if n.node.Status() > adt.Evaluating && n.node.IsErr() { |
| return true |
| } |
| return n.ctx.HasErr() || n.errs != nil |
| } |
| |
| func (n *nodeContext) getErr() *adt.Bottom { |
| n.errs = adt.CombineErrors(nil, n.errs, n.ctx.Err()) |
| return n.errs |
| } |
| |
| // getValidators sets the vertex' Value in case there was no concrete value. |
| func (n *nodeContext) getValidators() adt.BaseValue { |
| ctx := n.ctx |
| |
| a := []adt.Value{} |
| // if n.node.Value != nil { |
| // a = append(a, n.node.Value) |
| // } |
| kind := adt.TopKind |
| if n.lowerBound != nil { |
| a = append(a, n.lowerBound) |
| kind &= n.lowerBound.Kind() |
| } |
| if n.upperBound != nil { |
| a = append(a, n.upperBound) |
| kind &= n.upperBound.Kind() |
| } |
| for _, c := range n.checks { |
| // Drop !=x if x is out of bounds with another bound. |
| if b, _ := c.(*adt.BoundValue); b != nil && b.Op == adt.NotEqualOp { |
| if n.upperBound != nil && |
| adt.SimplifyBounds(ctx, n.kind, n.upperBound, b) != nil { |
| continue |
| } |
| if n.lowerBound != nil && |
| adt.SimplifyBounds(ctx, n.kind, n.lowerBound, b) != nil { |
| continue |
| } |
| } |
| a = append(a, c) |
| kind &= c.Kind() |
| } |
| if kind&^n.kind != 0 { |
| a = append(a, &adt.BasicType{K: n.kind}) |
| } |
| |
| var v adt.BaseValue |
| switch len(a) { |
| case 0: |
| // Src is the combined input. |
| v = &adt.BasicType{K: n.kind} |
| |
| if len(n.node.Structs) > 0 { |
| v = structSentinel |
| |
| } |
| |
| case 1: |
| v = a[0].(adt.Value) // remove cast |
| |
| default: |
| v = &adt.Conjunction{Values: a} |
| } |
| |
| return v |
| } |
| |
| func (n *nodeContext) maybeSetCache() { |
| if n.node.Status() > adt.Evaluating { // n.node.Value != nil |
| return |
| } |
| if n.scalar != nil { |
| n.node.SetValue(n.ctx, adt.Partial, n.scalar) |
| } |
| if n.errs != nil { |
| n.node.SetValue(n.ctx, adt.Partial, n.errs) |
| } |
| } |
| |
| type envExpr struct { |
| c adt.Conjunct |
| err *adt.Bottom |
| } |
| |
| type envDynamic struct { |
| env *adt.Environment |
| field *adt.DynamicField |
| id adt.ID |
| err *adt.Bottom |
| } |
| |
| type envYield struct { |
| env *adt.Environment |
| yield adt.Yielder |
| id adt.ID |
| err *adt.Bottom |
| } |
| |
| type envList struct { |
| env *adt.Environment |
| list *adt.ListLit |
| n int64 // recorded length after evaluator |
| elipsis *adt.Ellipsis |
| id adt.ID |
| } |
| |
| func (n *nodeContext) addBottom(b *adt.Bottom) { |
| n.errs = adt.CombineErrors(nil, n.errs, b) |
| // TODO(errors): consider doing this |
| // n.kindExpr = n.errs |
| // n.kind = 0 |
| } |
| |
| func (n *nodeContext) addErr(err errors.Error) { |
| if err != nil { |
| n.addBottom(&adt.Bottom{Err: err}) |
| } |
| } |
| |
| // addExprConjuncts will attempt to evaluate an adt.Expr and insert the value |
| // into the nodeContext if successful or queue it for later evaluation if it is |
| // incomplete or is not value. |
| func (n *nodeContext) addExprConjunct(v adt.Conjunct) { |
| env := v.Env |
| id := v.CloseID |
| |
| switch x := v.Expr().(type) { |
| case *adt.Vertex: |
| if x.IsData() { |
| n.addValueConjunct(env, x, id) |
| } else { |
| n.addVertexConjuncts(env, id, x, x) |
| } |
| |
| case adt.Value: |
| n.addValueConjunct(env, x, id) |
| |
| case *adt.BinaryExpr: |
| if x.Op == adt.AndOp { |
| n.addExprConjunct(adt.MakeConjunct(env, x.X, id)) |
| n.addExprConjunct(adt.MakeConjunct(env, x.Y, id)) |
| } else { |
| n.evalExpr(v) |
| } |
| |
| case *adt.StructLit: |
| n.addStruct(env, x, id) |
| |
| case *adt.ListLit: |
| n.lists = append(n.lists, envList{env: env, list: x, id: id}) |
| |
| case *adt.DisjunctionExpr: |
| if n.disjunctions != nil { |
| _ = n.disjunctions |
| } |
| n.addDisjunction(env, x, id) |
| |
| default: |
| // Must be Resolver or Evaluator. |
| n.evalExpr(v) |
| } |
| } |
| |
| // evalExpr is only called by addExprConjunct. If an error occurs, it records |
| // the error in n and returns nil. |
| func (n *nodeContext) evalExpr(v adt.Conjunct) { |
| // Require an Environment. |
| ctx := n.ctx |
| |
| closeID := v.CloseID |
| |
| // TODO: see if we can do without these counters. |
| for _, d := range v.Env.Deref { |
| d.EvalCount++ |
| } |
| for _, d := range v.Env.Cycles { |
| d.SelfCount++ |
| } |
| defer func() { |
| for _, d := range v.Env.Deref { |
| d.EvalCount-- |
| } |
| for _, d := range v.Env.Cycles { |
| d.SelfCount++ |
| } |
| }() |
| |
| switch x := v.Expr().(type) { |
| case adt.Resolver: |
| arc, err := ctx.Resolve(v.Env, x) |
| if err != nil && !err.IsIncomplete() { |
| n.addBottom(err) |
| break |
| } |
| if arc == nil { |
| n.exprs = append(n.exprs, envExpr{v, err}) |
| break |
| } |
| |
| n.addVertexConjuncts(v.Env, v.CloseID, v.Expr(), arc) |
| |
| case adt.Evaluator: |
| // adt.Interpolation, adt.UnaryExpr, adt.BinaryExpr, adt.CallExpr |
| // Could be unify? |
| val, complete := ctx.Evaluate(v.Env, v.Expr()) |
| if !complete { |
| b, _ := val.(*adt.Bottom) |
| n.exprs = append(n.exprs, envExpr{v, b}) |
| break |
| } |
| |
| if v, ok := val.(*adt.Vertex); ok { |
| // Handle generated disjunctions (as in the 'or' builtin). |
| // These come as a Vertex, but should not be added as a value. |
| b, ok := v.BaseValue.(*adt.Bottom) |
| if ok && b.IsIncomplete() && len(v.Conjuncts) > 0 { |
| for _, c := range v.Conjuncts { |
| c.CloseID = closeID |
| n.addExprConjunct(c) |
| } |
| break |
| } |
| } |
| |
| // TODO: also to through normal Vertex handling here. At the moment |
| // addValueConjunct handles StructMarker.NeedsClose, as this is always |
| // only needed when evaluation an Evaluator, and not a Resolver. |
| // The two code paths should ideally be merged once this separate |
| // mechanism is eliminated. |
| // |
| // if arc, ok := val.(*adt.Vertex); ok && !arc.IsData() { |
| // n.addVertexConjuncts(v.Env, closeID, v.Expr(), arc) |
| // break |
| // } |
| |
| // TODO: insert in vertex as well |
| n.addValueConjunct(v.Env, val, closeID) |
| |
| default: |
| panic(fmt.Sprintf("unknown expression of type %T", x)) |
| } |
| } |
| |
| func (n *nodeContext) addVertexConjuncts(env *adt.Environment, closeID adt.ID, x adt.Expr, arc *adt.Vertex) { |
| |
| // We need to ensure that each arc is only unified once (or at least) a |
| // bounded time, witch each conjunct. Comprehensions, for instance, may |
| // distribute a value across many values that get unified back into the |
| // same value. If such a value is a disjunction, than a disjunction of N |
| // disjuncts will result in a factor N more unifications for each |
| // occurrence of such value, resulting in exponential running time. This |
| // is especially common values that are used as a type. |
| // |
| // However, unification is idempotent, so each such conjunct only needs |
| // to be unified once. This cache checks for this and prevents an |
| // exponential blowup in such case. |
| // |
| // TODO(perf): this cache ensures the conjuncts of an arc at most once |
| // per ID. However, we really need to add the conjuncts of an arc only |
| // once total, and then add the close information once per close ID |
| // (pointer can probably be shared). Aside from being more performant, |
| // this is probably the best way to guarantee that conjunctions are |
| // linear in this case. |
| if n.arcMap == nil { |
| n.arcMap = map[arcKey]bool{} |
| } |
| if n.arcMap[arcKey{arc, closeID}] { |
| return |
| } |
| n.arcMap[arcKey{arc, closeID}] = true |
| |
| // Pass detection of structural cycles from parent to children. |
| cyclic := false |
| if env != nil { |
| // If a reference is in a tainted set, so is the value it refers to. |
| cyclic = env.Cyclic |
| } |
| |
| status := arc.Status() |
| |
| switch status { |
| case adt.Evaluating: |
| // Reference cycle detected. We have reached a fixed point and |
| // adding conjuncts at this point will not change the value. Also, |
| // continuing to pursue this value will result in an infinite loop. |
| |
| // TODO: add a mechanism so that the computation will only have to |
| // be done once? |
| |
| if arc == n.node { |
| // TODO: we could use node sharing here. This may avoid an |
| // exponential blowup during evaluation, like is possible with |
| // YAML. |
| return |
| } |
| |
| case adt.EvaluatingArcs: |
| // Structural cycle detected. Continue evaluation as usual, but |
| // keep track of whether any other conjuncts without structural |
| // cycles are added. If not, evaluation of child arcs will end |
| // with this node. |
| |
| // For the purpose of determining whether at least one non-cyclic |
| // conjuncts exists, we consider all conjuncts of a cyclic conjuncts |
| // also cyclic. |
| |
| cyclic = true |
| n.hasCycle = true |
| |
| // As the adt.EvaluatingArcs mechanism bypasses the self-reference |
| // mechanism, we need to separately keep track of it here. |
| // If this (originally) is a self-reference node, adding them |
| // will result in recursively adding the same reference. For this |
| // we also mark the node as evaluating. |
| if arc.SelfCount > 0 { |
| return |
| } |
| |
| // This count is added for values that are directly added below. |
| // The count is handled separately for delayed values. |
| arc.SelfCount++ |
| defer func() { arc.SelfCount-- }() |
| } |
| |
| if isDef(x) { // should test whether closed, not isDef? |
| c := closedInfo(n.node) |
| closeID = c.InsertDefinition(closeID, x) |
| n.needClose = true // TODO: is this still necessary? |
| } |
| |
| // TODO: uncommenting the following almost works, but causes some |
| // faulty results in complex cycle handling between disjunctions. |
| // The reason is that disjunctions must be eliminated if checks in |
| // values on which they depend fail. |
| ctx := n.ctx |
| ctx.Unify(ctx, arc, adt.Finalized) |
| |
| for _, c := range arc.Conjuncts { |
| var a []*adt.Vertex |
| if env != nil { |
| a = env.Deref |
| } |
| c = updateCyclic(c, cyclic, arc, a) |
| c.CloseID = closeID |
| n.addExprConjunct(c) |
| } |
| } |
| |
| // isDef reports whether an expressions is a reference that references a |
| // definition anywhere in its selection path. |
| // |
| // TODO(performance): this should be merged with resolve(). But for now keeping |
| // this code isolated makes it easier to see what it is for. |
| func isDef(x adt.Expr) bool { |
| switch r := x.(type) { |
| case *adt.FieldReference: |
| return r.Label.IsDef() |
| |
| case *adt.SelectorExpr: |
| if r.Sel.IsDef() { |
| return true |
| } |
| return isDef(r.X) |
| |
| case *adt.IndexExpr: |
| return isDef(r.X) |
| } |
| return false |
| } |
| |
| // updateCyclicStatus looks for proof of non-cyclic conjuncts to override |
| // a structural cycle. |
| func (n *nodeContext) updateCyclicStatus(env *adt.Environment) { |
| if env == nil || !env.Cyclic { |
| n.hasNonCycle = true |
| } |
| } |
| |
| func updateCyclic(c adt.Conjunct, cyclic bool, deref *adt.Vertex, a []*adt.Vertex) adt.Conjunct { |
| env := c.Env |
| switch { |
| case env == nil: |
| if !cyclic && deref == nil { |
| return c |
| } |
| env = &adt.Environment{Cyclic: cyclic} |
| case deref == nil && env.Cyclic == cyclic && len(a) == 0: |
| return c |
| default: |
| // The conjunct may still be in use in other fields, so we should |
| // make a new copy to mark Cyclic only for this case. |
| e := *env |
| e.Cyclic = e.Cyclic || cyclic |
| env = &e |
| } |
| if deref != nil || len(a) > 0 { |
| cp := make([]*adt.Vertex, 0, len(a)+1) |
| cp = append(cp, a...) |
| if deref != nil { |
| cp = append(cp, deref) |
| } |
| env.Deref = cp |
| } |
| if deref != nil { |
| env.Cycles = append(env.Cycles, deref) |
| } |
| return adt.MakeConjunct(env, c.Expr(), c.CloseID) |
| } |
| |
| func (n *nodeContext) addValueConjunct(env *adt.Environment, v adt.Value, id adt.ID) { |
| n.updateCyclicStatus(env) |
| |
| ctx := n.ctx |
| |
| if x, ok := v.(*adt.Vertex); ok { |
| if m, ok := x.BaseValue.(*adt.StructMarker); ok { |
| n.aStruct = x |
| n.aStructID = id |
| if m.NeedClose { |
| ci := closedInfo(n.node) |
| ci.isClosed = true // TODO: remove |
| id = ci.InsertDefinition(id, x) |
| ci.Canopy[id].IsClosed = true |
| ci.Canopy[id].IsDef = false |
| } |
| } |
| |
| cyclic := env != nil && env.Cyclic |
| |
| if !x.IsData() { |
| // TODO: this really shouldn't happen anymore. |
| if isComplexStruct(x) { |
| // This really shouldn't happen, but just in case. |
| n.addVertexConjuncts(env, id, x, x) |
| return |
| } |
| |
| for _, c := range x.Conjuncts { |
| c = updateCyclic(c, cyclic, nil, nil) |
| c.CloseID = id |
| n.addExprConjunct(c) // TODO: Pass from eval |
| } |
| return |
| } |
| |
| // TODO: evaluate value? |
| switch v := x.BaseValue.(type) { |
| default: |
| panic("invalid value") |
| |
| case *adt.ListMarker: |
| n.vLists = append(n.vLists, x) |
| return |
| |
| case *adt.StructMarker: |
| // TODO: this would not be necessary if acceptor.isClose were |
| // not used. See comment at acceptor. |
| opt := fieldSet{env: env, id: id} |
| |
| // Keep ordering of Go struct for topological sort. |
| n.node.Structs = append(n.node.Structs, x.Structs...) |
| for _, a := range x.Arcs { |
| c := adt.MakeConjunct(nil, a, id) |
| c = updateCyclic(c, cyclic, nil, nil) |
| n.insertField(a.Label, c) |
| opt.MarkField(ctx, a.Label) |
| } |
| |
| closedInfo(n.node).insertFieldSet(id, &opt) |
| |
| case adt.Value: |
| n.addValueConjunct(env, v, id) |
| |
| // TODO: this would not be necessary if acceptor.isClose were |
| // not used. See comment at acceptor. |
| opt := fieldSet{env: env, id: id} |
| |
| for _, a := range x.Arcs { |
| // TODO(errors): report error when this is a regular field. |
| c := adt.MakeConjunct(nil, a, id) |
| c = updateCyclic(c, cyclic, nil, nil) |
| n.insertField(a.Label, c) |
| opt.MarkField(ctx, a.Label) |
| } |
| |
| closedInfo(n.node).insertFieldSet(id, &opt) |
| } |
| |
| return |
| // TODO: Use the Closer to close other fields as well? |
| } |
| |
| switch b := v.(type) { |
| case *adt.Bottom: |
| n.addBottom(b) |
| return |
| case *adt.Builtin: |
| if v := b.BareValidator(); v != nil { |
| n.addValueConjunct(env, v, id) |
| return |
| } |
| } |
| |
| if !n.updateNodeType(v.Kind(), v, id) { |
| return |
| } |
| |
| switch x := v.(type) { |
| case *adt.Disjunction: |
| n.addDisjunctionValue(env, x, id) |
| |
| case *adt.Conjunction: |
| for _, x := range x.Values { |
| n.addValueConjunct(env, x, id) |
| } |
| |
| case *adt.Top: |
| n.hasTop = true |
| // TODO: Is this correct? Needed for elipsis, but not sure for others. |
| // n.optionals = append(n.optionals, fieldSet{env: env, id: id, isOpen: true}) |
| if a, _ := n.node.Closed.(*acceptor); a != nil { |
| // Embedding top indicates that now all possible values are allowed |
| // and that we should no longer enforce closedness within this |
| // conjunct. |
| a.node(id).IsDef = false |
| } |
| |
| case *adt.BasicType: |
| // handled above |
| |
| case *adt.BoundValue: |
| switch x.Op { |
| case adt.LessThanOp, adt.LessEqualOp: |
| if y := n.upperBound; y != nil { |
| n.upperBound = nil |
| v := adt.SimplifyBounds(ctx, n.kind, x, y) |
| if err := valueError(v); err != nil { |
| err.AddPosition(v) |
| err.AddPosition(n.upperBound) |
| err.AddPosition(closedInfo(n.node).node(id).Src) |
| } |
| n.addValueConjunct(env, v, id) |
| return |
| } |
| n.upperBound = x |
| |
| case adt.GreaterThanOp, adt.GreaterEqualOp: |
| if y := n.lowerBound; y != nil { |
| n.lowerBound = nil |
| v := adt.SimplifyBounds(ctx, n.kind, x, y) |
| if err := valueError(v); err != nil { |
| err.AddPosition(v) |
| err.AddPosition(n.lowerBound) |
| err.AddPosition(closedInfo(n.node).node(id).Src) |
| } |
| n.addValueConjunct(env, v, id) |
| return |
| } |
| n.lowerBound = x |
| |
| case adt.EqualOp, adt.NotEqualOp, adt.MatchOp, adt.NotMatchOp: |
| // This check serves as simplifier, but also to remove duplicates. |
| k := 0 |
| match := false |
| for _, c := range n.checks { |
| if y, ok := c.(*adt.BoundValue); ok { |
| switch z := adt.SimplifyBounds(ctx, n.kind, x, y); { |
| case z == y: |
| match = true |
| case z == x: |
| continue |
| } |
| } |
| n.checks[k] = c |
| k++ |
| } |
| n.checks = n.checks[:k] |
| if !match { |
| n.checks = append(n.checks, x) |
| } |
| return |
| } |
| |
| case adt.Validator: |
| // This check serves as simplifier, but also to remove duplicates. |
| for i, y := range n.checks { |
| if b := adt.SimplifyValidator(ctx, x, y); b != nil { |
| n.checks[i] = b |
| return |
| } |
| } |
| n.updateNodeType(x.Kind(), x, id) |
| n.checks = append(n.checks, x) |
| |
| case *adt.Vertex: |
| // handled above. |
| |
| case adt.Value: // *NullLit, *BoolLit, *NumLit, *StringLit, *BytesLit, *Builtin |
| if y := n.scalar; y != nil { |
| if b, ok := adt.BinOp(ctx, adt.EqualOp, x, y).(*adt.Bool); !ok || !b.B { |
| n.addConflict(x, y, x.Kind(), y.Kind(), n.scalarID, id) |
| } |
| // TODO: do we need to explicitly add again? |
| // n.scalar = nil |
| // n.addValueConjunct(c, adt.BinOp(c, adt.EqualOp, x, y)) |
| break |
| } |
| n.scalar = x |
| n.scalarID = id |
| |
| default: |
| panic(fmt.Sprintf("unknown value type %T", x)) |
| } |
| |
| if n.lowerBound != nil && n.upperBound != nil { |
| if u := adt.SimplifyBounds(ctx, n.kind, n.lowerBound, n.upperBound); u != nil { |
| if err := valueError(u); err != nil { |
| err.AddPosition(n.lowerBound) |
| err.AddPosition(n.upperBound) |
| err.AddPosition(closedInfo(n.node).node(id).Src) |
| } |
| n.lowerBound = nil |
| n.upperBound = nil |
| n.addValueConjunct(env, u, id) |
| } |
| } |
| } |
| |
| func valueError(v adt.Value) *adt.ValueError { |
| if v == nil { |
| return nil |
| } |
| b, _ := v.(*adt.Bottom) |
| if b == nil { |
| return nil |
| } |
| err, _ := b.Err.(*adt.ValueError) |
| if err == nil { |
| return nil |
| } |
| return err |
| } |
| |
| // addStruct collates the declarations of a struct. |
| // |
| // addStruct fulfills two additional pivotal functions: |
| // 1) Implement vertex unification (this happens through De Bruijn indices |
| // combined with proper set up of Environments). |
| // 2) Implied closedness for definitions. |
| // |
| func (n *nodeContext) addStruct( |
| env *adt.Environment, |
| s *adt.StructLit, |
| closeID adt.ID) { |
| |
| n.updateCyclicStatus(env) // to handle empty structs. |
| |
| ctx := n.ctx |
| n.node.AddStructs(s) |
| |
| // NOTE: This is a crucial point in the code: |
| // Unification derferencing happens here. The child nodes are set to |
| // an Environment linked to the current node. Together with the De Bruijn |
| // indices, this determines to which Vertex a reference resolves. |
| |
| // TODO(perf): consider using environment cache: |
| // var childEnv *adt.Environment |
| // for _, s := range n.nodeCache.sub { |
| // if s.Up == env { |
| // childEnv = s |
| // } |
| // } |
| childEnv := &adt.Environment{ |
| Up: env, |
| Vertex: n.node, |
| } |
| if env != nil { |
| childEnv.Cyclic = env.Cyclic |
| childEnv.Deref = env.Deref |
| } |
| |
| hasEmbed := false |
| |
| opt := fieldSet{pos: s, env: childEnv, id: closeID} |
| |
| for _, d := range s.Decls { |
| switch x := d.(type) { |
| case *adt.Field: |
| opt.MarkField(ctx, x.Label) |
| // handle in next iteration. |
| |
| case *adt.OptionalField: |
| if x.Label.IsString() { |
| n.aStruct = s |
| n.aStructID = closeID |
| } |
| opt.AddOptional(ctx, x) |
| |
| case *adt.DynamicField: |
| n.aStruct = s |
| n.aStructID = closeID |
| n.dynamicFields = append(n.dynamicFields, envDynamic{childEnv, x, closeID, nil}) |
| opt.AddDynamic(ctx, childEnv, x) |
| |
| case *adt.ForClause: |
| n.forClauses = append(n.forClauses, envYield{childEnv, x, closeID, nil}) |
| |
| case adt.Yielder: |
| n.ifClauses = append(n.ifClauses, envYield{childEnv, x, closeID, nil}) |
| |
| case adt.Expr: |
| hasEmbed = true |
| |
| // add embedding to optional |
| |
| // TODO(perf): only do this if addExprConjunct below will result in |
| // a fieldSet. Otherwise the entry will just be removed next. |
| id := closedInfo(n.node).InsertEmbed(closeID, x) |
| |
| // push and opo embedding type. |
| n.addExprConjunct(adt.MakeConjunct(childEnv, x, id)) |
| |
| case *adt.BulkOptionalField: |
| n.aStruct = s |
| n.aStructID = closeID |
| opt.AddBulk(ctx, x) |
| |
| case *adt.Ellipsis: |
| n.aStruct = s |
| n.aStructID = closeID |
| opt.AddEllipsis(ctx, x) |
| |
| default: |
| panic("unreachable") |
| } |
| } |
| |
| if !hasEmbed { |
| n.aStruct = s |
| n.aStructID = closeID |
| } |
| |
| // Apply existing fields |
| for _, arc := range n.node.Arcs { |
| // Reuse adt.Acceptor interface. |
| opt.MatchAndInsert(ctx, arc) |
| } |
| |
| closedInfo(n.node).insertFieldSet(closeID, &opt) |
| |
| for _, d := range s.Decls { |
| switch x := d.(type) { |
| case *adt.Field: |
| if x.Label.IsString() { |
| n.aStruct = s |
| n.aStructID = closeID |
| } |
| n.insertField(x.Label, adt.MakeConjunct(childEnv, x, closeID)) |
| } |
| } |
| } |
| |
| func (n *nodeContext) insertField(f adt.Feature, x adt.Conjunct) *adt.Vertex { |
| ctx := n.ctx |
| arc, isNew := n.node.GetArc(f) |
| |
| // TODO: disallow adding conjuncts when cache set? |
| arc.AddConjunct(x) |
| |
| adt.Assertf(x.CloseID == 0 || int(x.CloseID) < len(closedInfo(n.node).Canopy), "invalid adt.ID") |
| |
| if isNew { |
| closedInfo(n.node).visitAllFieldSets(func(o *fieldSet) { |
| o.MatchAndInsert(ctx, arc) |
| }) |
| } |
| return arc |
| } |
| |
| // expandOne adds dynamic fields to a node until a fixed point is reached. |
| // On each iteration, dynamic fields that cannot resolve due to incomplete |
| // values are skipped. They will be retried on the next iteration until no |
| // progress can be made. Note that a dynamic field may add more dynamic fields. |
| // |
| // forClauses are processed after all other clauses. A struct may be referenced |
| // before it is complete, meaning that fields added by other forms of injection |
| // may influence the result of a for clause _after_ it has already been |
| // processed. We could instead detect such insertion and feed it to the |
| // ForClause to generate another entry or have the for clause be recomputed. |
| // This seems to be too complicated and lead to iffy edge cases. |
| // TODO(errors): detect when a field is added to a struct that is already used |
| // in a for clause. |
| func (n *nodeContext) expandOne() (done bool) { |
| // Don't expand incomplete expressions if we detected a cycle. |
| if n.done() || (n.hasCycle && !n.hasNonCycle) { |
| return false |
| } |
| |
| var progress bool |
| |
| if progress = n.injectDynamic(); progress { |
| return true |
| } |
| |
| if progress = n.injectEmbedded(&(n.ifClauses)); progress { |
| return true |
| } |
| |
| if progress = n.injectEmbedded(&(n.forClauses)); progress { |
| return true |
| } |
| |
| // Do expressions after comprehensions, as comprehensions can never |
| // refer to embedded scalars, whereas expressions may refer to generated |
| // fields if we were to allow attributes to be defined alongside |
| // scalars. |
| exprs := n.exprs |
| n.exprs = n.exprs[:0] |
| for _, x := range exprs { |
| n.addExprConjunct(x.c) |
| |
| // collect and and or |
| } |
| if len(n.exprs) < len(exprs) { |
| return true |
| } |
| |
| // No progress, report error later if needed: unification with |
| // disjuncts may resolve this later later on. |
| return false |
| } |
| |
| // injectDynamic evaluates and inserts dynamic declarations. |
| func (n *nodeContext) injectDynamic() (progress bool) { |
| ctx := n.ctx |
| k := 0 |
| |
| a := n.dynamicFields |
| for _, d := range n.dynamicFields { |
| var f adt.Feature |
| v, complete := ctx.Evaluate(d.env, d.field.Key) |
| if !complete { |
| d.err, _ = v.(*adt.Bottom) |
| a[k] = d |
| k++ |
| continue |
| } |
| if b, _ := v.(*adt.Bottom); b != nil { |
| n.addValueConjunct(nil, b, d.id) |
| continue |
| } |
| f = ctx.Label(d.field.Key, v) |
| n.insertField(f, adt.MakeConjunct(d.env, d.field, d.id)) |
| } |
| |
| progress = k < len(n.dynamicFields) |
| |
| n.dynamicFields = a[:k] |
| |
| return progress |
| } |
| |
| // injectEmbedded evaluates and inserts embeddings. It first evaluates all |
| // embeddings before inserting the results to ensure that the order of |
| // evaluation does not matter. |
| func (n *nodeContext) injectEmbedded(all *[]envYield) (progress bool) { |
| ctx := n.ctx |
| type envStruct struct { |
| env *adt.Environment |
| s *adt.StructLit |
| } |
| var sa []envStruct |
| f := func(env *adt.Environment, st *adt.StructLit) { |
| sa = append(sa, envStruct{env, st}) |
| } |
| |
| k := 0 |
| for i := 0; i < len(*all); i++ { |
| d := (*all)[i] |
| sa = sa[:0] |
| |
| if err := ctx.Yield(d.env, d.yield, f); err != nil { |
| if err.IsIncomplete() { |
| d.err = err |
| (*all)[k] = d |
| k++ |
| } else { |
| // continue to collect other errors. |
| n.addBottom(err) |
| } |
| continue |
| } |
| |
| for _, st := range sa { |
| n.addStruct(st.env, st.s, d.id) |
| } |
| } |
| |
| progress = k < len(*all) |
| |
| *all = (*all)[:k] |
| |
| return progress |
| } |
| |
| // addLists |
| // |
| // TODO: association arrays: |
| // If an association array marker was present in a struct, create a struct node |
| // instead of a list node. In either case, a node may only have list fields |
| // or struct fields and not both. |
| // |
| // addLists should be run after the fixpoint expansion: |
| // - it enforces that comprehensions may not refer to the list itself |
| // - there may be no other fields within the list. |
| // |
| // TODO(embeddedScalars): for embedded scalars, there should be another pass |
| // of evaluation expressions after expanding lists. |
| func (n *nodeContext) addLists(c *adt.OpContext) (oneOfTheLists adt.Expr, anID adt.ID) { |
| if len(n.lists) == 0 && len(n.vLists) == 0 { |
| return nil, 0 |
| } |
| |
| isOpen := true |
| max := 0 |
| var maxNode adt.Expr |
| |
| if m, ok := n.node.BaseValue.(*adt.ListMarker); ok { |
| isOpen = m.IsOpen |
| max = len(n.node.Arcs) |
| } |
| |
| for _, l := range n.vLists { |
| oneOfTheLists = l |
| |
| elems := l.Elems() |
| isClosed := l.IsClosed(c) |
| |
| switch { |
| case len(elems) < max: |
| if isClosed { |
| n.invalidListLength(len(elems), max, l, maxNode) |
| continue |
| } |
| |
| case len(elems) > max: |
| if !isOpen { |
| n.invalidListLength(max, len(elems), maxNode, l) |
| continue |
| } |
| isOpen = !isClosed |
| max = len(elems) |
| maxNode = l |
| |
| case isClosed: |
| isOpen = false |
| maxNode = l |
| } |
| |
| for _, a := range elems { |
| if a.Conjuncts == nil { |
| x := a.BaseValue.(adt.Value) |
| n.insertField(a.Label, adt.MakeConjunct(nil, x, 0)) |
| continue |
| } |
| for _, c := range a.Conjuncts { |
| n.insertField(a.Label, c) |
| } |
| } |
| } |
| |
| outer: |
| for i, l := range n.lists { |
| n.updateCyclicStatus(l.env) |
| |
| index := int64(0) |
| hasComprehension := false |
| for j, elem := range l.list.Elems { |
| switch x := elem.(type) { |
| case adt.Yielder: |
| err := c.Yield(l.env, x, func(e *adt.Environment, st *adt.StructLit) { |
| label, err := adt.MakeLabel(x.Source(), index, adt.IntLabel) |
| n.addErr(err) |
| index++ |
| c := adt.MakeConjunct(e, st, l.id) |
| n.insertField(label, c) |
| }) |
| hasComprehension = true |
| if err != nil { |
| n.addBottom(err) |
| continue outer |
| } |
| |
| case *adt.Ellipsis: |
| if j != len(l.list.Elems)-1 { |
| n.addErr(c.Newf("ellipsis must be last element in list")) |
| } |
| |
| n.lists[i].elipsis = x |
| |
| default: |
| label, err := adt.MakeLabel(x.Source(), index, adt.IntLabel) |
| n.addErr(err) |
| index++ // TODO: don't use insertField. |
| n.insertField(label, adt.MakeConjunct(l.env, x, l.id)) |
| } |
| |
| // Terminate early n case of runaway comprehension. |
| if !isOpen && int(index) > max { |
| n.invalidListLength(max, int(index), maxNode, l.list) |
| continue outer |
| } |
| } |
| |
| oneOfTheLists = l.list |
| anID = l.id |
| |
| switch closed := n.lists[i].elipsis == nil; { |
| case int(index) < max: |
| if closed { |
| n.invalidListLength(int(index), max, l.list, maxNode) |
| continue |
| } |
| |
| case int(index) > max, |
| closed && isOpen, |
| (!closed == isOpen) && !hasComprehension: |
| max = int(index) |
| maxNode = l.list |
| isOpen = !closed |
| } |
| |
| n.lists[i].n = index |
| } |
| |
| // add additionalItem values to list and construct optionals. |
| elems := n.node.Elems() |
| for _, l := range n.vLists { |
| a, _ := l.Closed.(*acceptor) |
| if a == nil { |
| continue |
| } |
| |
| newElems := l.Elems() |
| if len(newElems) >= len(elems) { |
| continue // error generated earlier, if applicable. |
| } |
| |
| // TODO: why not necessary? |
| // n.optionals = append(n.optionals, a.fields...) |
| |
| for _, arc := range elems[len(newElems):] { |
| l.MatchAndInsert(c, arc) |
| } |
| } |
| |
| for _, l := range n.lists { |
| if l.elipsis == nil { |
| continue |
| } |
| |
| f := &fieldSet{pos: l.list, env: l.env, id: l.id} |
| f.AddEllipsis(c, l.elipsis) |
| |
| closedInfo(n.node).insertFieldSet(l.id, f) |
| |
| for _, arc := range elems[l.n:] { |
| f.MatchAndInsert(c, arc) |
| } |
| } |
| |
| sources := []ast.Expr{} |
| // Add conjuncts for additional items. |
| for _, l := range n.lists { |
| if l.elipsis == nil { |
| continue |
| } |
| if src, _ := l.elipsis.Source().(ast.Expr); src != nil { |
| sources = append(sources, src) |
| } |
| } |
| |
| ci := closedInfo(n.node) |
| ci.isList = true |
| ci.openList = isOpen |
| |
| if m, ok := n.node.BaseValue.(*adt.ListMarker); !ok { |
| n.node.SetValue(c, adt.Partial, &adt.ListMarker{ |
| Src: ast.NewBinExpr(token.AND, sources...), |
| IsOpen: isOpen, |
| }) |
| } else { |
| if expr, _ := m.Src.(ast.Expr); expr != nil { |
| sources = append(sources, expr) |
| } |
| m.Src = ast.NewBinExpr(token.AND, sources...) |
| m.IsOpen = m.IsOpen && isOpen |
| } |
| |
| n.lists = n.lists[:0] |
| n.vLists = n.vLists[:0] |
| |
| return oneOfTheLists, anID |
| } |
| |
| func (n *nodeContext) invalidListLength(na, nb int, a, b adt.Expr) { |
| n.addErr(n.ctx.Newf("incompatible list lengths (%d and %d)", na, nb)) |
| } |