blob: 68056ab2c2e33c4ab2270533fb7ed38b1ceb3f05 [file] [log] [blame]
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001// Copyright 2018 The CUE Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package cue
16
17import (
18 "bytes"
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010019)
20
21func eval(idx *index, v value) evaluated {
22 ctx := idx.newContext()
23 return v.evalPartial(ctx)
24}
25
26func (x *nodeRef) evalPartial(ctx *context) (result evaluated) {
27 return x.node.evalPartial(ctx)
28}
29
30// Atoms
31
32func (x *top) evalPartial(ctx *context) evaluated { return x }
33func (x *bottom) evalPartial(ctx *context) evaluated { return x }
34
35func (x *basicType) evalPartial(ctx *context) evaluated { return x }
36func (x *nullLit) evalPartial(ctx *context) evaluated { return x }
37func (x *boolLit) evalPartial(ctx *context) evaluated { return x }
38func (x *stringLit) evalPartial(ctx *context) evaluated { return x }
39func (x *bytesLit) evalPartial(ctx *context) evaluated { return x }
40func (x *numLit) evalPartial(ctx *context) evaluated { return x }
41func (x *durationLit) evalPartial(ctx *context) evaluated { return x }
42
43func (x *lambdaExpr) evalPartial(ctx *context) evaluated {
44 return ctx.deref(x).(*lambdaExpr)
45}
46
47func (x *selectorExpr) evalPartial(ctx *context) (result evaluated) {
48 if ctx.trace {
49 defer uni(indent(ctx, "selectorExpr", x))
50 defer func() { ctx.debugPrint("result:", result) }()
51 }
52
53 e := newEval(ctx, true)
54
55 const msgType = "invalid operation: %[5]s (type %[3]s does not support selection)"
56 v := e.eval(x.x, structKind|lambdaKind, msgType, x)
57
58 if e.is(v, structKind|lambdaKind, "") {
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +010059 n := v.(scope).lookup(ctx, x.feature)
60 if n.val() == nil {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010061 field := ctx.labelStr(x.feature)
62 // m.foo undefined (type map[string]bool has no field or method foo)
63 return ctx.mkErr(x, "undefined field %q", field)
64 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +010065 // TODO: do we need to evaluate here?
66 return n.cache.evalPartial(ctx)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010067 }
68 return e.err(&selectorExpr{x.baseValue, v, x.feature})
69}
70
71func (x *indexExpr) evalPartial(ctx *context) (result evaluated) {
72 if ctx.trace {
73 defer uni(indent(ctx, "indexExpr", x))
74 defer func() { ctx.debugPrint("result:", result) }()
75 }
76
77 e := newEval(ctx, true)
78
79 const msgType = "invalid operation: %[5]s (type %[3]s does not support indexing)"
80 const msgIndexType = "invalid %[5]s index %[1]s (type %[3]s)"
81
82 val := e.eval(x.x, listKind|structKind|stringKind|bytesKind, msgType, x)
83 k := val.kind()
84 index := e.eval(x.index, stringKind|intKind, msgIndexType, k)
85
86 switch v := val.(type) {
87 case *structLit:
88 if e.is(index, stringKind, msgIndexType, k) {
89 s := index.strValue()
90 // TODO: must lookup
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +010091 n := v.lookup(ctx, ctx.strLabel(s))
92 if n.val() == nil {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010093 return ctx.mkErr(x, index, "undefined field %q", s)
94 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +010095 return n.cache
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010096 }
97 case atter:
98 if e.is(index, intKind, msgIndexType, k) {
99 i := index.(*numLit).intValue(ctx)
100 if i < 0 {
101 const msg = "invalid %[4]s index %[1]s (index must be non-negative)"
102 return e.mkErr(x.index, index, 0, k, msg)
103 }
104 return v.at(ctx, i)
105 }
106 }
107 return e.err(&indexExpr{x.baseValue, val, index})
108}
109
110// Composit
111
112func (x *sliceExpr) evalPartial(ctx *context) (result evaluated) {
113 if ctx.trace {
114 defer uni(indent(ctx, "sliceExpr", x))
115 defer func() { ctx.debugPrint("result:", result) }()
116 }
117
118 e := newEval(ctx, true)
119 const msgType = "cannot slice %[2]s (type %[3]s)"
120 const msgInvalidIndex = "invalid slice index %[1]s (type %[3]s)"
121 val := e.eval(x.x, listKind|stringKind, msgType)
122 lo := e.evalAllowNil(x.lo, intKind, msgInvalidIndex)
123 hi := e.evalAllowNil(x.hi, intKind, msgInvalidIndex)
124 var low, high *numLit
125 if lo != nil && e.is(lo, intKind, msgInvalidIndex) {
126 low = lo.(*numLit)
127 }
128 if hi != nil && e.is(hi, intKind, msgInvalidIndex) {
129 high = hi.(*numLit)
130 }
131 if !e.hasErr() {
132 switch x := val.(type) {
133 case *list:
134 return x.slice(ctx, low, high)
135 case *stringLit:
136 return x.slice(ctx, low, high)
137 }
138 }
139 return e.err(&sliceExpr{x.baseValue, val, lo, hi})
140}
141
142// TODO: make a callExpr a binary expression
143func (x *callExpr) evalPartial(ctx *context) (result evaluated) {
144 if ctx.trace {
145 defer uni(indent(ctx, "callExpr", x))
146 defer func() {
147 ctx.debugPrint("result:", result)
148 }()
149 }
150
151 e := newEval(ctx, true)
152
153 fn := e.eval(x.x, lambdaKind, "cannot call non-function %[1]s (type %[3]s)")
154 args := make([]evaluated, len(x.args))
155 for i, a := range x.args {
156 args[i] = e.evalPartial(a, typeKinds, "never triggers")
157 }
158 if !e.hasErr() {
159 // If we have a template expression, it is either already copied it as
160 // result of a references, or it is a literal, in which case it is
161 // trivially fully evaluated.
162 return fn.(caller).call(ctx, x, args...).evalPartial(ctx)
163 }
164 // Construct a simplified call for reporting purposes.
165 err := &callExpr{x.baseValue, fn, nil}
166 for _, a := range args {
167 err.args = append(err.args, a)
168 }
169 return e.err(err)
170}
171
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100172func (x *bound) evalPartial(ctx *context) (result evaluated) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100173 if ctx.trace {
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100174 defer uni(indent(ctx, "bound", x))
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100175 defer func() { ctx.debugPrint("result:", result) }()
176 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100177 v := x.value.evalPartial(ctx)
178 if isBottom(v) {
179 return ctx.mkErr(x, v, "error evaluating bound")
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100180 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100181 if v == x.value {
182 return x
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100183 }
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200184 return newBound(x.baseValue, x.op, x.k, v)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100185}
186
187func (x *interpolation) evalPartial(ctx *context) (result evaluated) {
188 if ctx.trace {
189 defer uni(indent(ctx, "interpolation", x))
190 defer func() { ctx.debugPrint("result:", result) }()
191 }
192 buf := bytes.Buffer{}
193 for _, v := range x.parts {
194 switch e := ctx.manifest(v).(type) {
195 case *bottom:
196 return e
197 case *stringLit, *numLit, *durationLit:
198 buf.WriteString(e.strValue())
199 default:
200 k := e.kind()
201 if k&stringableKind == bottomKind {
202 return ctx.mkErr(e, "expression in interpolation must evaluate to a number kind or string (found %v)", k)
203 }
204 if !k.isGround() {
205 return ctx.mkErr(e, codeIncomplete, "incomplete")
206 }
207 }
208 }
209 return &stringLit{x.baseValue, buf.String()}
210}
211
212func (x *list) evalPartial(ctx *context) (result evaluated) {
213 if ctx.trace {
214 defer uni(indent(ctx, "list", x))
215 defer func() { ctx.debugPrint("result:", result) }()
216 }
217 n := x.len.evalPartial(ctx)
218 t := x.typ.evalPartial(ctx)
219 if err := firstBottom(n, t); err != nil {
220 return err
221 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200222 s := x.elem.evalPartial(ctx).(*structLit)
223 if s == x.elem && n == x.len && t == x.typ {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100224 return x
225 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200226 return &list{x.baseValue, s, t, n}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100227}
228
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100229func (x *listComprehension) evalPartial(ctx *context) evaluated {
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200230 s := &structLit{baseValue: x.baseValue}
231 list := &list{baseValue: x.baseValue, elem: s}
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100232 result := x.clauses.yield(ctx, func(k, v evaluated, _ bool) *bottom {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100233 if !k.kind().isAnyOf(intKind) {
234 return ctx.mkErr(k, "key must be of type int")
235 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200236 list.elem.arcs = append(list.elem.arcs, arc{
237 feature: label(len(list.elem.arcs)),
238 v: v.evalPartial(ctx),
239 })
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100240 return nil
241 })
242 switch {
243 case result == nil:
244 case isBottom(result):
245 return result
246 default:
247 panic("should not happen")
248 }
249 list.initLit()
250 return list
251}
252
253func (x *feed) evalPartial(ctx *context) evaluated { return x }
254func (x *guard) evalPartial(ctx *context) evaluated { return x }
255func (x *yield) evalPartial(ctx *context) evaluated { return x }
256
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100257func (x *fieldComprehension) evalPartial(ctx *context) evaluated { return x }
258
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100259func (x *structLit) evalPartial(ctx *context) (result evaluated) {
260 if ctx.trace {
261 defer uni(indent(ctx, "struct eval", x))
262 defer func() { ctx.debugPrint("result:", result) }()
263 }
264 x = ctx.deref(x).(*structLit)
265
266 // TODO: Handle cycle?
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100267
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100268 return x
269}
270
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100271func (x *unification) evalPartial(ctx *context) (result evaluated) {
272 // By definition, all of the values in this type are already evaluated.
273 return x
274}
275
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100276func (x *disjunction) evalPartial(ctx *context) (result evaluated) {
277 if ctx.trace {
278 defer uni(indent(ctx, "disjunction", x))
279 defer func() { ctx.debugPrint("result:", result) }()
280 }
281
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200282 // decSum := false
283 if len(ctx.evalStack) > 1 {
284 ctx.inSum++
285 }
286 dn := &disjunction{x.baseValue, make([]dValue, 0, len(x.values)), x.hasDefaults}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100287 changed := false
288 for _, v := range x.values {
289 n := v.val.evalPartial(ctx)
290 changed = changed || n != v.val
Marcel van Lohuizen94b5ccc2019-01-31 07:54:24 +0100291 // Including elements of disjunctions recursively makes default handling
292 // associative (*a | (*b|c)) == ((*a|*b) | c).
293 if d, ok := n.(*disjunction); ok {
294 changed = true
295 for _, dv := range d.values {
296 dn.add(ctx, dv.val, dv.marked)
297 }
298 } else {
299 dn.add(ctx, n, v.marked)
300 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100301 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100302 if !changed {
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +0100303 dn = x
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100304 }
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200305 if len(ctx.evalStack) > 1 {
306 ctx.inSum--
307 }
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100308 return dn.normalize(ctx, x).val
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100309}
310
311func (x *disjunction) manifest(ctx *context) (result evaluated) {
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100312 var err, marked, unmarked1, unmarked2 evaluated
313 for _, d := range x.values {
314 // Because of the lazy evaluation strategy, we may still have
315 // latent unification.
316 if err := validate(ctx, d.val); err != nil {
317 continue
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100318 }
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100319 switch {
320 case d.marked:
321 if marked != nil {
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +0100322 // TODO: allow disjunctions to be returned as is.
Marcel van Lohuizen50eea6b2019-02-19 18:30:15 +0100323 return ctx.mkErr(x, codeIncomplete, "more than one default remaining (%v and %v)", debugStr(ctx, marked), debugStr(ctx, d.val))
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100324 }
325 marked = d.val.(evaluated)
326 case unmarked1 == nil:
327 unmarked1 = d.val.(evaluated)
328 default:
329 unmarked2 = d.val.(evaluated)
330 }
331 }
332 switch {
333 case marked != nil:
334 return marked
335
336 case unmarked2 != nil:
Marcel van Lohuizen50eea6b2019-02-19 18:30:15 +0100337 return ctx.mkErr(x, codeIncomplete, "more than one element remaining (%v and %v)",
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100338 debugStr(ctx, unmarked1), debugStr(ctx, unmarked2))
339
340 case unmarked1 != nil:
341 return unmarked1
342
343 case err != nil:
344 return err
345
346 default:
347 return ctx.mkErr(x, "empty disjunction")
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100348 }
349}
350
351func (x *binaryExpr) evalPartial(ctx *context) (result evaluated) {
352 if ctx.trace {
353 defer uni(indent(ctx, "binaryExpr", x))
354 defer func() { ctx.debugPrint("result:", result) }()
355 }
356 var left, right evaluated
357
358 if x.op != opUnify {
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200359 ctx.incEvalDepth()
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100360 left = ctx.manifest(x.left)
361 right = ctx.manifest(x.right)
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200362 ctx.decEvalDepth()
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100363
364 // TODO: allow comparing to a literal bottom only. Find something more
365 // principled perhaps. One should especially take care that two values
366 // evaluating to bottom don't evaluate to true. For now we check for
367 // bottom here and require that one of the values be a bottom literal.
368 if l, r := isBottom(x.left), isBottom(x.right); l || r {
369 leftBottom := isBottom(left)
370 rightBottom := isBottom(right)
371 switch x.op {
372 case opEql:
373 return &boolLit{x.baseValue, leftBottom == rightBottom}
374 case opNeq:
375 return &boolLit{x.baseValue, leftBottom != rightBottom}
376 }
377 }
378 } else {
379 left = x.left.evalPartial(ctx)
380 right = x.right.evalPartial(ctx)
381
Marcel van Lohuizen50eea6b2019-02-19 18:30:15 +0100382 if err := cycleError(left); err != nil && ctx.inSum == 0 && right.kind().isAtom() {
383 return ctx.delayConstraint(right, x)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100384 }
Marcel van Lohuizen50eea6b2019-02-19 18:30:15 +0100385 if err := cycleError(right); err != nil && ctx.inSum == 0 && left.kind().isAtom() {
386 return ctx.delayConstraint(left, x)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100387 }
388
389 // check if it is a cycle that can be unwrapped.
390 // If other value is a cycle or list, return the original forwarded,
391 // but ensure the value is not cached. Object/list error?
392 }
393 return binOp(ctx, x, x.op, left, right)
394}
395
396func (x *unaryExpr) evalPartial(ctx *context) (result evaluated) {
397 if ctx.trace {
398 defer uni(indent(ctx, "unaryExpr", x))
399 defer func() { ctx.debugPrint("result:", result) }()
400 }
401
402 return evalUnary(ctx, x, x.op, x.x)
403}
404
405func evalUnary(ctx *context, src source, op op, x value) evaluated {
406 v := ctx.manifest(x)
407
408 const numeric = numKind | durationKind
409 kind := v.kind()
410 switch op {
411 case opSub:
412 if kind&numeric == bottomKind {
413 return ctx.mkErr(src, "unary '-' requires numeric value, found %s", kind)
414 }
415 switch v := v.(type) {
416 case *numLit:
417 f := *v
418 f.v.Neg(&v.v)
419 return &f
420 case *durationLit:
421 d := *v
422 d.d = -d.d
423 return &d
424 }
425 fallthrough
426
427 case opAdd:
428 if kind&numeric == bottomKind {
429 return ctx.mkErr(src, "unary '+' requires numeric value, found %s", kind)
430 }
431 if kind&^(numeric|nonGround|referenceKind) == bottomKind {
432 return v
433 }
434 switch v := v.(type) {
435 case *numLit, *durationLit:
436 return v
437 case *top:
438 return &basicType{v.baseValue, numeric | nonGround}
439 case *basicType:
440 return &basicType{v.baseValue, (v.k & numeric) | nonGround}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100441 }
442
443 case opNot:
444 if kind&boolKind == bottomKind {
445 return ctx.mkErr(src, "unary '!' requires bool value, found %s", kind)
446 }
447 switch v := v.(type) {
448 case *top:
449 return &basicType{v.baseValue, boolKind | nonGround}
450 case *basicType:
451 return v
452 case *boolLit:
453 return &boolLit{src.base(), !v.b}
454 }
455 }
456 return ctx.mkErr(src, "invalid operand type %v for unary operator %v", v, op)
457}