| // Copyright 2018 The 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 cue |
| |
| import ( |
| "bytes" |
| ) |
| |
| func eval(idx *index, v value) evaluated { |
| ctx := idx.newContext() |
| return v.evalPartial(ctx) |
| } |
| |
| func (x *nodeRef) evalPartial(ctx *context) (result evaluated) { |
| return x.node.evalPartial(ctx) |
| } |
| |
| // Atoms |
| |
| func (x *top) evalPartial(ctx *context) evaluated { return x } |
| func (x *bottom) evalPartial(ctx *context) evaluated { return x } |
| |
| func (x *basicType) evalPartial(ctx *context) evaluated { return x } |
| func (x *nullLit) evalPartial(ctx *context) evaluated { return x } |
| func (x *boolLit) evalPartial(ctx *context) evaluated { return x } |
| func (x *stringLit) evalPartial(ctx *context) evaluated { return x } |
| func (x *bytesLit) evalPartial(ctx *context) evaluated { return x } |
| func (x *numLit) evalPartial(ctx *context) evaluated { return x } |
| func (x *durationLit) evalPartial(ctx *context) evaluated { return x } |
| |
| func (x *lambdaExpr) evalPartial(ctx *context) evaluated { |
| return ctx.deref(x).(*lambdaExpr) |
| } |
| |
| func (x *selectorExpr) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "selectorExpr", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| |
| e := newEval(ctx, true) |
| |
| const msgType = "invalid operation: %[5]s (type %[3]s does not support selection)" |
| v := e.eval(x.x, structKind|lambdaKind, msgType, x) |
| |
| if e.is(v, structKind|lambdaKind, "") { |
| sc, ok := v.(scope) |
| if !ok { |
| return ctx.mkErr(x, "invalid subject to selector (found %v)", v.kind()) |
| } |
| n := sc.lookup(ctx, x.feature) |
| if n.optional { |
| field := ctx.labelStr(x.feature) |
| return ctx.mkErr(x, codeIncomplete, "field %q is optional", field) |
| } |
| if n.val() == nil { |
| field := ctx.labelStr(x.feature) |
| if st, ok := sc.(*structLit); ok && !st.isClosed { |
| return ctx.mkErr(x, codeIncomplete, "undefined field %q", field) |
| } |
| // m.foo undefined (type map[string]bool has no field or method foo) |
| // TODO: mention x.x in error message? |
| return ctx.mkErr(x, "undefined field %q", field) |
| } |
| // TODO: do we need to evaluate here? |
| return n.cache.evalPartial(ctx) |
| } |
| return e.err(&selectorExpr{x.baseValue, v, x.feature}) |
| } |
| |
| func (x *indexExpr) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "indexExpr", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| |
| e := newEval(ctx, true) |
| |
| const msgType = "invalid operation: %[5]s (type %[3]s does not support indexing)" |
| const msgIndexType = "invalid %[5]s index %[1]s (type %[3]s)" |
| |
| val := e.eval(x.x, listKind|structKind, msgType, x) |
| k := val.kind() |
| index := e.eval(x.index, stringKind|intKind, msgIndexType, k) |
| |
| switch v := val.(type) { |
| case *structLit: |
| if e.is(index, stringKind, msgIndexType, k) { |
| s := index.strValue() |
| // TODO: must lookup |
| n := v.lookup(ctx, ctx.strLabel(s)) |
| if n.optional { |
| return ctx.mkErr(x, index, codeIncomplete, "field %q is optional", s) |
| } |
| if n.val() == nil { |
| if !v.isClosed { |
| return ctx.mkErr(x, index, codeIncomplete, "undefined field %q", s) |
| } |
| return ctx.mkErr(x, index, "undefined field %q", s) |
| } |
| return n.cache |
| } |
| case atter: |
| if e.is(index, intKind, msgIndexType, k) { |
| i := index.(*numLit).intValue(ctx) |
| if i < 0 { |
| const msg = "invalid %[4]s index %[1]s (index must be non-negative)" |
| return e.mkErr(x.index, index, 0, k, msg) |
| } |
| return v.at(ctx, i) |
| } |
| } |
| return e.err(&indexExpr{x.baseValue, val, index}) |
| } |
| |
| // Composit |
| |
| func (x *sliceExpr) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "sliceExpr", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| |
| e := newEval(ctx, true) |
| const msgType = "cannot slice %[2]s (type %[3]s)" |
| const msgInvalidIndex = "invalid slice index %[1]s (type %[3]s)" |
| val := e.eval(x.x, listKind, msgType) |
| lo := e.evalAllowNil(x.lo, intKind, msgInvalidIndex) |
| hi := e.evalAllowNil(x.hi, intKind, msgInvalidIndex) |
| var low, high *numLit |
| if lo != nil && e.is(lo, intKind, msgInvalidIndex) { |
| low = lo.(*numLit) |
| } |
| if hi != nil && e.is(hi, intKind, msgInvalidIndex) { |
| high = hi.(*numLit) |
| } |
| if !e.hasErr() { |
| switch x := val.(type) { |
| case *list: |
| return x.slice(ctx, low, high) |
| case *stringLit: |
| return x.slice(ctx, low, high) |
| } |
| } |
| return e.err(&sliceExpr{x.baseValue, val, lo, hi}) |
| } |
| |
| // TODO: make a callExpr a binary expression |
| func (x *callExpr) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "callExpr", x)) |
| defer func() { |
| ctx.debugPrint("result:", result) |
| }() |
| } |
| |
| e := newEval(ctx, true) |
| |
| fn := e.eval(x.x, lambdaKind, "cannot call non-function %[2]s (type %[3]s)") |
| args := make([]evaluated, len(x.args)) |
| for i, a := range x.args { |
| args[i] = e.evalPartial(a, typeKinds, "never triggers") |
| } |
| if !e.hasErr() { |
| // If we have a template expression, it is either already copied it as |
| // result of a references, or it is a literal, in which case it is |
| // trivially fully evaluated. |
| return fn.(caller).call(ctx, x, args...).evalPartial(ctx) |
| } |
| // Construct a simplified call for reporting purposes. |
| err := &callExpr{x.baseValue, fn, nil} |
| for _, a := range args { |
| err.args = append(err.args, a) |
| } |
| return e.err(err) |
| } |
| |
| func (x *customValidator) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "custom", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| return x |
| } |
| |
| func (x *bound) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "bound", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| v := x.value.evalPartial(ctx) |
| if isBottom(v) { |
| if isIncomplete(v) { |
| return v |
| } |
| return ctx.mkErr(x, v, "error evaluating bound") |
| } |
| if v == x.value { |
| return x |
| } |
| return newBound(ctx, x.baseValue, x.op, x.k, v) |
| } |
| |
| func (x *interpolation) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "interpolation", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| buf := bytes.Buffer{} |
| for _, v := range x.parts { |
| switch e := ctx.manifest(v).(type) { |
| case *bottom: |
| return e |
| case *stringLit, *numLit, *durationLit: |
| buf.WriteString(e.strValue()) |
| default: |
| k := e.kind() |
| if k&stringableKind == bottomKind { |
| return ctx.mkErr(e, "expression in interpolation must evaluate to a number kind or string (found %v)", k) |
| } |
| if !k.isGround() { |
| return ctx.mkErr(e, codeIncomplete, "incomplete") |
| } |
| } |
| } |
| return &stringLit{x.baseValue, buf.String(), nil} |
| } |
| |
| func (x *list) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "list", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| n := x.len.evalPartial(ctx) |
| t := x.typ.evalPartial(ctx) |
| if err := firstBottom(n, t); err != nil { |
| return err |
| } |
| s := x.elem.evalPartial(ctx).(*structLit) |
| if s == x.elem && n == x.len && t == x.typ { |
| return x |
| } |
| return &list{x.baseValue, s, t, n} |
| } |
| |
| func (x *listComprehension) evalPartial(ctx *context) evaluated { |
| s := &structLit{baseValue: x.baseValue} |
| list := &list{baseValue: x.baseValue, elem: s} |
| result := x.clauses.yield(ctx, func(k, v evaluated, _, _ bool) *bottom { |
| if !k.kind().isAnyOf(intKind) { |
| return ctx.mkErr(k, "key must be of type int") |
| } |
| list.elem.arcs = append(list.elem.arcs, arc{ |
| feature: label(len(list.elem.arcs)), |
| v: v.evalPartial(ctx), |
| }) |
| return nil |
| }) |
| switch { |
| case result == nil: |
| case isBottom(result): |
| return result |
| default: |
| panic("should not happen") |
| } |
| list.initLit() |
| return list |
| } |
| |
| func (x *feed) evalPartial(ctx *context) evaluated { return x } |
| func (x *guard) evalPartial(ctx *context) evaluated { return x } |
| func (x *yield) evalPartial(ctx *context) evaluated { return x } |
| |
| func (x *fieldComprehension) evalPartial(ctx *context) evaluated { return x } |
| |
| func (x *structLit) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "struct eval", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| x = ctx.deref(x).(*structLit) |
| |
| // TODO: Handle cycle? |
| |
| return x |
| } |
| |
| func (x *unification) evalPartial(ctx *context) (result evaluated) { |
| // By definition, all of the values in this type are already evaluated. |
| return x |
| } |
| |
| func (x *disjunction) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "disjunction", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| |
| // decSum := false |
| if len(ctx.evalStack) > 1 { |
| ctx.inSum++ |
| } |
| dn := &disjunction{x.baseValue, make([]dValue, 0, len(x.values)), x.hasDefaults} |
| changed := false |
| for _, v := range x.values { |
| n := v.val.evalPartial(ctx) |
| changed = changed || n != v.val |
| // Including elements of disjunctions recursively makes default handling |
| // associative (*a | (*b|c)) == ((*a|*b) | c). |
| if d, ok := n.(*disjunction); ok { |
| changed = true |
| for _, dv := range d.values { |
| dn.add(ctx, dv.val, dv.marked) |
| } |
| } else { |
| dn.add(ctx, n, v.marked) |
| } |
| } |
| if !changed { |
| dn = x |
| } |
| if len(ctx.evalStack) > 1 { |
| ctx.inSum-- |
| } |
| return dn.normalize(ctx, x).val |
| } |
| |
| func (x *disjunction) manifest(ctx *context) (result evaluated) { |
| values := make([]dValue, 0, len(x.values)) |
| validValue := false |
| for _, dv := range x.values { |
| switch { |
| case isBottom(dv.val): |
| case dv.marked: |
| values = append(values, dv) |
| default: |
| validValue = true |
| } |
| } |
| |
| switch { |
| case len(values) > 0: |
| // values contains all the valid defaults |
| case !validValue: |
| return x |
| default: |
| for _, dv := range x.values { |
| dv.marked = false |
| values = append(values, dv) |
| } |
| } |
| |
| switch len(values) { |
| case 0: |
| return x |
| |
| case 1: |
| return values[0].val.evalPartial(ctx) |
| } |
| |
| x = &disjunction{x.baseValue, values, true} |
| return x.normalize(ctx, x).val |
| } |
| |
| func (x *binaryExpr) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "binaryExpr", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| var left, right evaluated |
| |
| if _, isUnify := x.op.unifyType(); !isUnify { |
| ctx.incEvalDepth() |
| left = ctx.manifest(x.left) |
| right = ctx.manifest(x.right) |
| ctx.decEvalDepth() |
| |
| // TODO: allow comparing to a literal bottom only. Find something more |
| // principled perhaps. One should especially take care that two values |
| // evaluating to bottom don't evaluate to true. For now we check for |
| // bottom here and require that one of the values be a bottom literal. |
| if l, r := isBottom(x.left), isBottom(x.right); l || r { |
| leftBottom := isBottom(left) |
| rightBottom := isBottom(right) |
| switch x.op { |
| case opEql: |
| return &boolLit{x.baseValue, leftBottom == rightBottom} |
| case opNeq: |
| return &boolLit{x.baseValue, leftBottom != rightBottom} |
| } |
| } |
| } else { |
| left = x.left.evalPartial(ctx) |
| right = x.right.evalPartial(ctx) |
| |
| if err := cycleError(left); err != nil && ctx.inSum == 0 && right.kind().isAtom() { |
| return ctx.delayConstraint(right, x) |
| } |
| if err := cycleError(right); err != nil && ctx.inSum == 0 && left.kind().isAtom() { |
| return ctx.delayConstraint(left, x) |
| } |
| |
| // check if it is a cycle that can be unwrapped. |
| // If other value is a cycle or list, return the original forwarded, |
| // but ensure the value is not cached. Object/list error? |
| } |
| return binOp(ctx, x, x.op, left, right) |
| } |
| |
| func (x *unaryExpr) evalPartial(ctx *context) (result evaluated) { |
| if ctx.trace { |
| defer uni(indent(ctx, "unaryExpr", x)) |
| defer func() { ctx.debugPrint("result:", result) }() |
| } |
| |
| return evalUnary(ctx, x, x.op, x.x) |
| } |
| |
| func evalUnary(ctx *context, src source, op op, x value) evaluated { |
| v := ctx.manifest(x) |
| |
| const numeric = numKind | durationKind |
| kind := v.kind() |
| switch op { |
| case opSub: |
| if kind&numeric == bottomKind { |
| return ctx.mkErr(src, "invalid operation -%s (- %s)", ctx.str(x), kind) |
| } |
| switch v := v.(type) { |
| case *numLit: |
| f := *v |
| f.v.Neg(&v.v) |
| return &f |
| case *durationLit: |
| d := *v |
| d.d = -d.d |
| return &d |
| } |
| return ctx.mkErr(src, codeIncomplete, "operand %s of '-' not concrete (was %s)", ctx.str(x), kind) |
| |
| case opAdd: |
| if kind&numeric == bottomKind { |
| return ctx.mkErr(src, "invalid operation +%s (+ %s)", ctx.str(x), kind) |
| } |
| switch v := v.(type) { |
| case *numLit, *durationLit: |
| return v |
| case *top: |
| return &basicType{v.baseValue, numeric | nonGround} |
| case *basicType: |
| return &basicType{v.baseValue, (v.k & numeric) | nonGround} |
| } |
| return ctx.mkErr(src, codeIncomplete, "operand %s of '+' not concrete (was %s)", ctx.str(x), kind) |
| |
| case opNot: |
| if kind&boolKind == bottomKind { |
| return ctx.mkErr(src, "invalid operation !%s (! %s)", ctx.str(x), kind) |
| } |
| switch v := v.(type) { |
| case *boolLit: |
| return &boolLit{src.base(), !v.b} |
| } |
| return ctx.mkErr(src, codeIncomplete, "operand %s of '!' not concrete (was %s)", ctx.str(x), kind) |
| } |
| return ctx.mkErr(src, "invalid operation %s%s (%s %s)", op, ctx.str(x), op, kind) |
| } |