blob: 67944a2e998ae29cd462984f7f3d1df916f6c61f [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 (
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010018 "math/big"
19 "sort"
20 "strconv"
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010021 "time"
22
23 "cuelang.org/go/cue/ast"
24 "cuelang.org/go/cue/token"
25 "github.com/cockroachdb/apd"
26)
27
28type value interface {
29 source
30
31 rewrite(*context, rewriteFunc) value
32
33 // evalPartial evaluates a value without choosing default values.
34 evalPartial(*context) evaluated
35
36 kind() kind
37
38 // subsumesImpl is only defined for non-reference types.
39 // It should only be called by the subsumes function.
40 subsumesImpl(*context, value, subsumeMode) bool
41}
42
43type evaluated interface {
44 value
45 binOp(*context, source, op, evaluated) evaluated
46 strValue() string
47}
48
49type scope interface {
50 value
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +010051 lookup(*context, label) arc
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010052}
53
54type atter interface {
55 // at returns the evaluated and its original value at the given position.
56 // If the original could not be found, it returns an error and nil.
57 at(*context, int) evaluated
58}
59
60type iterAtter interface {
61 // at returns the evaluated and its original value at the given position.
62 // If the original could not be found, it returns an error and nil.
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +010063 iterAt(*context, int) arc
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010064}
65
66// caller must be implemented by any concrete lambdaKind
67type caller interface {
68 call(ctx *context, src source, args ...evaluated) value
69 returnKind() kind
70}
71
72func checkKind(ctx *context, x value, want kind) *bottom {
73 if b, ok := x.(*bottom); ok {
74 return b
75 }
76 got := x.kind()
77 if got&want&concreteKind == bottomKind && want != bottomKind {
78 return ctx.mkErr(x, "not of right kind (%v vs %v)", got, want)
79 }
80 if !got.isGround() {
81 return ctx.mkErr(x, codeIncomplete,
82 "non-concrete value %v", got)
83 }
84 return nil
85}
86
87func newDecl(n ast.Decl) baseValue {
88 if n == nil {
89 panic("empty node")
90 }
91 return baseValue{n}
92}
93
94func newExpr(n ast.Expr) baseValue {
95 if n == nil {
96 panic("empty node")
97 }
98 return baseValue{n}
99}
100
101func newNode(n ast.Node) baseValue {
102 if n == nil {
103 panic("empty node")
104 }
105 return baseValue{n}
106}
107
108type source interface {
109 // syntax returns the parsed file of the underlying node or a computed
110 // node indicating that it is a computed binary expression.
111 syntax() ast.Node
112 computed() *computedSource
113 Pos() token.Pos
114 base() baseValue
115}
116
117type computedSource struct {
118 pos token.Pos
119 op op
120 x value
121 y value
122}
123
124func (s *computedSource) Pos() token.Pos {
125 return s.pos
126}
127
128type posser interface {
129 Pos() token.Pos
130}
131
132type baseValue struct {
133 pos posser
134}
135
136func (b baseValue) Pos() token.Pos {
137 if b.pos == nil {
138 return token.NoPos
139 }
140 return b.pos.Pos()
141}
142
143func (b baseValue) computed() *computedSource {
144 switch x := b.pos.(type) {
145 case *computedSource:
146 return x
147 }
148 return nil
149}
150
151func (b baseValue) syntax() ast.Node {
152 switch x := b.pos.(type) {
153 case ast.Node:
154 return x
155 }
156 return nil
157}
158
159func (b baseValue) base() baseValue {
160 return b
161}
162
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100163func (b baseValue) strValue() string { panic("unimplemented") }
164func (b baseValue) returnKind() kind { panic("unimplemented") }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100165
166// top is the top of the value lattice. It subsumes all possible values.
167type top struct{ baseValue }
168
169func (x *top) kind() kind { return topKind }
170
171// basicType represents the root class of any specific type.
172type basicType struct {
173 baseValue
174 k kind
175}
176
177func (x *basicType) kind() kind { return x.k | nonGround }
178
179// Literals
180
181type nullLit struct{ baseValue }
182
183func (x *nullLit) kind() kind { return nullKind }
184
185type boolLit struct {
186 baseValue
187 b bool
188}
189
190func (x *boolLit) kind() kind { return boolKind }
191
192func boolTonode(src source, b bool) evaluated {
193 return &boolLit{src.base(), b}
194}
195
196type bytesLit struct {
197 baseValue
198 b []byte
199 // TODO: maintain extended grapheme index cache.
200}
201
202func (x *bytesLit) kind() kind { return bytesKind }
203func (x *bytesLit) strValue() string { return string(x.b) }
204
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100205func (x *bytesLit) iterAt(ctx *context, i int) arc {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100206 if i >= len(x.b) {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100207 return arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100208 }
209 v := x.at(ctx, i)
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100210 return arc{v: v, cache: v}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100211}
212
213func (x *bytesLit) at(ctx *context, i int) evaluated {
214 if i < 0 || i >= len(x.b) {
215 return ctx.mkErr(x, "index %d out of bounds", i)
216 }
217 // TODO: this is incorrect.
218 n := newNum(x, intKind)
219 n.v.SetInt64(int64(x.b[i]))
220 return n
221}
222
223func (x *bytesLit) len() int { return len(x.b) }
224
225func (x *bytesLit) slice(ctx *context, lo, hi *numLit) evaluated {
226 lox := 0
227 hix := len(x.b)
228 if lo != nil {
229 lox = lo.intValue(ctx)
230 }
231 if hi != nil {
232 hix = hi.intValue(ctx)
233 }
234 if lox < 0 {
235 return ctx.mkErr(x, "invalid slice index %d (must be non-negative)", lox)
236 }
237 if hix < 0 {
238 return ctx.mkErr(x, "invalid slice index %d (must be non-negative)", hix)
239 }
240 if hix < lox {
241 return ctx.mkErr(x, "invalid slice index: %d > %d", lox, hix)
242 }
243 if len(x.b) < hix {
244 return ctx.mkErr(hi, "slice bounds out of range")
245 }
246 return &bytesLit{x.baseValue, x.b[lox:hix]}
247}
248
249type stringLit struct {
250 baseValue
251 str string
252
253 // TODO: maintain extended grapheme index cache.
254}
255
256func (x *stringLit) kind() kind { return stringKind }
257func (x *stringLit) strValue() string { return x.str }
258
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100259func (x *stringLit) iterAt(ctx *context, i int) arc {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100260 runes := []rune(x.str)
261 if i >= len(runes) {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100262 return arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100263 }
264 v := x.at(ctx, i)
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100265 return arc{v: v, cache: v}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100266}
267
268func (x *stringLit) at(ctx *context, i int) evaluated {
269 runes := []rune(x.str)
270 if i < 0 || i >= len(runes) {
271 return ctx.mkErr(x, "index %d out of bounds", i)
272 }
273 // TODO: this is incorrect.
274 return &stringLit{x.baseValue, string(runes[i : i+1])}
275}
276func (x *stringLit) len() int { return len([]rune(x.str)) }
277
278func (x *stringLit) slice(ctx *context, lo, hi *numLit) evaluated {
279 runes := []rune(x.str)
280 lox := 0
281 hix := len(runes)
282 if lo != nil {
283 lox = lo.intValue(ctx)
284 }
285 if hi != nil {
286 hix = hi.intValue(ctx)
287 }
288 if lox < 0 {
289 return ctx.mkErr(x, "invalid slice index %d (must be non-negative)", lox)
290 }
291 if hix < 0 {
292 return ctx.mkErr(x, "invalid slice index %d (must be non-negative)", hix)
293 }
294 if hix < lox {
295 return ctx.mkErr(x, "invalid slice index: %d > %d", lox, hix)
296 }
297 if len(runes) < hix {
298 return ctx.mkErr(hi, "slice bounds out of range")
299 }
300 return &stringLit{x.baseValue, string(runes[lox:hix])}
301}
302
303type numBase struct {
304 baseValue
305 numInfo
306}
307
308func newNumBase(n ast.Expr, info numInfo) numBase {
309 return numBase{newExpr(n), info}
310}
311
312func newNumBin(k kind, a, b *numLit) *numLit {
313 n := &numLit{
314 numBase: numBase{
315 baseValue: a.baseValue,
316 numInfo: unifyNuminfo(a.numInfo, b.numInfo),
317 },
318 }
319 return n
320}
321
322func resultNumBase(a, b numBase) numBase {
323 return numBase{
324 baseValue: a.baseValue,
325 numInfo: unifyNuminfo(a.numInfo, b.numInfo),
326 }
327}
328
329type numLit struct {
330 numBase
331 v apd.Decimal
332}
333
334func parseInt(k kind, s string) *numLit {
335 n := &ast.BasicLit{
336 Kind: token.INT,
337 Value: s,
338 }
339 num := newNum(newExpr(n), k)
340 _, _, err := num.v.SetString(s)
341 if err != nil {
342 panic(err)
343 }
344 return num
345}
346
Marcel van Lohuizend572bb62019-05-06 12:08:10 +0200347func parseFloat(s string) *numLit {
348 n := &ast.BasicLit{
349 Kind: token.FLOAT,
350 Value: s,
351 }
352 num := newNum(newExpr(n), floatKind)
353 _, _, err := num.v.SetString(s)
354 if err != nil {
355 panic(err)
356 }
357 return num
358}
359
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100360func newNum(src source, k kind) *numLit {
361 n := &numLit{numBase: numBase{baseValue: src.base()}}
362 n.k = k
363 return n
364}
365
366var ten = big.NewInt(10)
367
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100368var one = parseInt(intKind, "1")
369
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100370func (x *numLit) kind() kind { return x.k }
371func (x *numLit) strValue() string { return x.v.String() }
372
373func (x *numLit) isInt(ctx *context) bool {
374 return x.kind()&intKind != 0
375}
376
377func (x *numLit) intValue(ctx *context) int {
378 v, err := x.v.Int64()
379 if err != nil {
380 ctx.mkErr(x, "intValue: %v", err)
381 return 0
382 }
383 return int(v)
384}
385
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100386type durationLit struct {
387 baseValue
388 d time.Duration
389}
390
391func (x *durationLit) kind() kind { return durationKind }
392func (x *durationLit) strValue() string { return x.d.String() }
393
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100394type bound struct {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100395 baseValue
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200396 op op // opNeq, opLss, opLeq, opGeq, or opGtr
397 k kind // mostly used for number kind
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100398 value value
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100399}
400
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200401func newBound(base baseValue, op op, k kind, v value) *bound {
402 kv := v.kind()
403 if kv.isAnyOf(numKind) {
404 kv |= numKind
405 } else if op == opNeq && kv&atomKind == nullKind {
406 kv = typeKinds &^ nullKind
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100407 }
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200408 return &bound{base, op, unifyType(k&topKind, kv) | nonGround, v}
409}
410
411func (x *bound) kind() kind {
412 return x.k
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100413}
414
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100415func mkIntRange(a, b string) evaluated {
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200416 from := newBound(baseValue{}, opGeq, intKind, parseInt(intKind, a))
417 to := newBound(baseValue{}, opLeq, intKind, parseInt(intKind, b))
Marcel van Lohuizen0e2bcd52019-04-03 22:33:14 +0200418 e := &unification{
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100419 binSrc(token.NoPos, opUnify, from, to),
420 []evaluated{from, to},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100421 }
Marcel van Lohuizen0e2bcd52019-04-03 22:33:14 +0200422 // TODO: make this an integer
423 // int := &basicType{k: intKind}
424 // e = &unification{
425 // binSrc(token.NoPos, opUnify, int, e),
426 // []evaluated{int, e},
427 // }
428 return e
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100429}
430
Marcel van Lohuizend572bb62019-05-06 12:08:10 +0200431func mkFloatRange(a, b string) evaluated {
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200432 from := newBound(baseValue{}, opGeq, numKind, parseFloat(a))
433 to := newBound(baseValue{}, opLeq, numKind, parseFloat(b))
Marcel van Lohuizend572bb62019-05-06 12:08:10 +0200434 e := &unification{
435 binSrc(token.NoPos, opUnify, from, to),
436 []evaluated{from, to},
437 }
438 // TODO: make this an integer
439 // int := &basicType{k: intKind}
440 // e = &unification{
441 // binSrc(token.NoPos, opUnify, int, e),
442 // []evaluated{int, e},
443 // }
444 return e
445}
446
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100447var predefinedRanges = map[string]evaluated{
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100448 "rune": mkIntRange("0", strconv.Itoa(0x10FFFF)),
449 "int8": mkIntRange("-128", "127"),
450 "int16": mkIntRange("-32768", "32767"),
451 "int32": mkIntRange("-2147483648", "2147483647"),
452 "int64": mkIntRange("-9223372036854775808", "9223372036854775807"),
453 "int128": mkIntRange(
454 "-170141183460469231731687303715884105728",
455 "170141183460469231731687303715884105727"),
456
457 // Do not include an alias for "byte", as it would be too easily confused
458 // with the builtin "bytes".
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200459 "uint": newBound(baseValue{}, opGeq, intKind, parseInt(intKind, "0")),
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100460 "uint8": mkIntRange("0", "255"),
461 "uint16": mkIntRange("0", "65535"),
462 "uint32": mkIntRange("0", "4294967295"),
463 "uint64": mkIntRange("0", "18446744073709551615"),
464 "uint128": mkIntRange("0", "340282366920938463463374607431768211455"),
Marcel van Lohuizend572bb62019-05-06 12:08:10 +0200465
466 // 2**127 * (2**24 - 1) / 2**23
467 "float32": mkFloatRange(
468 "-3.40282346638528859811704183484516925440e+38",
469 "+3.40282346638528859811704183484516925440e+38",
470 ),
471 // 2**1023 * (2**53 - 1) / 2**52
472 "float64": mkFloatRange(
473 "-1.797693134862315708145274237317043567981e+308",
474 "+1.797693134862315708145274237317043567981e+308",
475 ),
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100476}
477
478type interpolation struct {
479 baseValue
480 k kind // string or bytes
481 parts []value // odd: strings, even expressions
482}
483
484func (x *interpolation) kind() kind { return x.k | nonGround }
485
486type list struct {
487 baseValue
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200488 elem *structLit
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100489
490 typ value
Jonathan Amsterdam0500c312019-02-16 18:04:09 -0500491
492 // TODO: consider removing len. Currently can only be len(a) or >= len(a)
493 // and could be replaced with a bool.
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100494 len value
495}
496
497// initLit initializes a literal list.
498func (x *list) initLit() {
499 n := newNum(x, intKind)
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200500 n.v.SetInt64(int64(len(x.elem.arcs)))
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100501 x.len = n
502 x.typ = &top{x.baseValue}
503}
504
Marcel van Lohuizenb134a502019-05-06 11:33:05 +0200505func (x *list) manifest(ctx *context) evaluated {
506 if x.kind().isGround() {
507 return x
508 }
509 // A list is ground if its length is ground, or if the current length
510 // meets matches the cap.
511 n := newNum(x, intKind)
512 n.v.SetInt64(int64(len(x.elem.arcs)))
513 if n := binOp(ctx, x, opUnify, n, x.len.evalPartial(ctx)); !isBottom(n) {
514 return &list{
515 baseValue: x.baseValue,
516 elem: x.elem,
517 len: n,
518 typ: &top{x.baseValue},
519 }
520 }
521 return x
522}
523
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100524func (x *list) kind() kind {
Marcel van Lohuizenb134a502019-05-06 11:33:05 +0200525 k := listKind
526 if _, ok := x.len.(*numLit); ok {
527 return k
528 }
529 return k | nonGround
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100530}
531
532// at returns the evaluated and original value of position i. List x must
533// already have been evaluated. It returns an error and nil if there was an
534// issue evaluating the list itself.
535func (x *list) at(ctx *context, i int) evaluated {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100536 arc := x.iterAt(ctx, i)
537 if arc.cache == nil {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100538 return ctx.mkErr(x, "index %d out of bounds", i)
539 }
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100540 return arc.cache
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100541}
542
543// iterAt returns the evaluated and original value of position i. List x must
544// already have been evaluated. It returns an error and nil if there was an
545// issue evaluating the list itself.
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100546func (x *list) iterAt(ctx *context, i int) arc {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100547 if i < 0 {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100548 v := ctx.mkErr(x, "index %d out of bounds", i)
549 return arc{cache: v}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100550 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200551 if i < len(x.elem.arcs) {
552 a := x.elem.iterAt(ctx, i)
553 a.feature = 0
554 return a
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100555 }
556 max := maxNum(x.len.(evaluated))
557 if max.kind().isGround() {
558 if max.kind()&intKind == bottomKind {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100559 v := ctx.mkErr(max, "length indicator of list not of type int")
560 return arc{cache: v}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100561 }
562 n := max.(*numLit).intValue(ctx)
563 if i >= n {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100564 return arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100565 }
566 }
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100567 return arc{cache: x.typ.(evaluated), v: x.typ}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100568}
569
570func (x *list) isOpen() bool {
571 return !x.len.kind().isGround()
572}
573
574// lo and hi must be nil or a ground integer.
575func (x *list) slice(ctx *context, lo, hi *numLit) evaluated {
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200576 a := x.elem.arcs
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100577 max := maxNum(x.len).evalPartial(ctx)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100578 if hi != nil {
579 n := hi.intValue(ctx)
580 if n < 0 {
581 return ctx.mkErr(x, "negative slice index")
582 }
583 if max.kind().isGround() && !leq(ctx, hi, hi, max) {
584 return ctx.mkErr(hi, "slice bounds out of range")
585 }
586 max = hi
587 if n < len(a) {
588 a = a[:n]
589 }
590 }
591
592 if lo != nil {
593 n := lo.intValue(ctx)
594 if n < 0 {
595 return ctx.mkErr(x, "negative slice index")
596 }
597 if n > 0 && max.kind().isGround() {
598 if !leq(ctx, lo, lo, max) {
599 max := max.(*numLit).intValue(ctx)
600 return ctx.mkErr(x, "invalid slice index: %v > %v", n, max)
601 }
602 max = binOp(ctx, lo, opSub, max, lo)
603 }
604 if n < len(a) {
605 a = a[n:]
606 } else {
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200607 a = []arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100608 }
609 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200610 arcs := make([]arc, len(a))
611 for i, a := range a {
612 arcs[i] = arc{feature: label(i), v: a.v}
613 }
614 s := &structLit{baseValue: x.baseValue, arcs: arcs}
615 return &list{baseValue: x.baseValue, elem: s, typ: x.typ, len: max}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100616}
617
618// An structLit is a single structLit in the configuration tree.
619//
620// An structLit may have multiple arcs. There may be only one arc per label. Use
621// insertRaw to insert arcs to ensure this invariant holds.
622type structLit struct {
623 baseValue
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100624
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100625 // TODO(perf): separate out these infrequent values to save space.
626 emit value // currently only supported at top level.
627 template value
628 comprehensions []*fieldComprehension
629
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100630 // TODO: consider hoisting the template arc to its own value.
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100631 arcs []arc
632 expanded *structLit
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100633}
634
635func newStruct(src source) *structLit {
636 return &structLit{baseValue: src.base()}
637}
638
639func (x *structLit) kind() kind { return structKind }
640
641type arcs []arc
642
643func (x *structLit) Len() int { return len(x.arcs) }
644func (x *structLit) Less(i, j int) bool { return x.arcs[i].feature < x.arcs[j].feature }
645func (x *structLit) Swap(i, j int) { x.arcs[i], x.arcs[j] = x.arcs[j], x.arcs[i] }
646
647// lookup returns the node for the given label f, if present, or nil otherwise.
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100648func (x *structLit) lookup(ctx *context, f label) arc {
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100649 x = x.expandFields(ctx)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100650 // Lookup is done by selector or index references. Either this is done on
651 // literal nodes or nodes obtained from references. In the later case,
652 // noderef will have ensured that the ancestors were evaluated.
653 for i, a := range x.arcs {
654 if a.feature == f {
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100655 a.cache = x.at(ctx, i)
656 return a
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100657 }
658 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100659 return arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100660}
661
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100662func (x *structLit) iterAt(ctx *context, i int) arc {
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100663 x = x.expandFields(ctx)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100664 if i >= len(x.arcs) {
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100665 return arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100666 }
Marcel van Lohuizen9bf93c02019-03-26 21:40:25 +0100667 a := x.arcs[i]
668 a.cache = x.at(ctx, i) // TODO: return template & v for original?
669 return a
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100670}
671
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100672func (x *structLit) at(ctx *context, i int) evaluated {
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100673 x = x.expandFields(ctx)
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100674 // if x.emit != nil && isBottom(x.emit) {
675 // return x.emit.(evaluated)
676 // }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100677 // Lookup is done by selector or index references. Either this is done on
678 // literal nodes or nodes obtained from references. In the later case,
679 // noderef will have ensured that the ancestors were evaluated.
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200680 if v := x.arcs[i].cache; v == nil {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100681
682 // cycle detection
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100683
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200684 popped := ctx.evalStack
685 ctx.evalStack = append(ctx.evalStack, bottom{
686 baseValue: x.base(),
687 index: ctx.index,
688 code: codeCycle,
689 value: x.arcs[i].v,
690 msg: "cycle detected",
691 })
692 x.arcs[i].cache = &(ctx.evalStack[len(ctx.evalStack)-1])
693
Marcel van Lohuizen004bef52019-01-30 14:07:06 +0100694 v := x.arcs[i].v.evalPartial(ctx)
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200695 ctx.evalStack = popped
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100696
697 v = x.applyTemplate(ctx, i, v)
Marcel van Lohuizen004bef52019-01-30 14:07:06 +0100698
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200699 if (len(ctx.evalStack) > 0 && ctx.cycleErr) || cycleError(v) != nil {
Marcel van Lohuizen004bef52019-01-30 14:07:06 +0100700 // Don't cache while we're in a evaluation cycle as it will cache
701 // partial results. Each field involved in the cycle will have to
702 // reevaluated the values from scratch. As the result will be
703 // cached after one cycle, it will evaluate the cycle at most twice.
704 x.arcs[i].cache = nil
705 return v
706 }
Marcel van Lohuizen89601442019-02-19 00:24:06 +0100707
708 // If there as a cycle error, we have by now evaluated a full cycle and
Marcel van Lohuizen004bef52019-01-30 14:07:06 +0100709 // it is safe to cache the result.
710 ctx.cycleErr = false
711
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100712 x.arcs[i].cache = v
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200713 if len(ctx.evalStack) == 0 {
Marcel van Lohuizen004bef52019-01-30 14:07:06 +0100714 if err := ctx.processDelayedConstraints(); err != nil {
715 x.arcs[i].cache = err
716 }
717 }
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200718 } else if b := cycleError(v); b != nil {
719 copy := *b
720 return &copy
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100721 }
722 return x.arcs[i].cache
723}
724
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100725func (x *structLit) expandFields(ctx *context) *structLit {
726 if x.expanded != nil {
727 return x.expanded
728 }
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100729 if x.comprehensions == nil {
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100730 x.expanded = x
731 return x
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100732 }
733
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100734 x.expanded = x
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100735
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100736 comprehensions := x.comprehensions
737 emit := x.emit
738 template := x.template
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100739 newArcs := []arc{}
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100740 optional := false
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100741
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100742 for _, c := range comprehensions {
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100743 result := c.clauses.yield(ctx, func(k, v evaluated, opt bool) *bottom {
744 optional = opt
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100745 if !k.kind().isAnyOf(stringKind) {
746 return ctx.mkErr(k, "key must be of type string")
747 }
748 if c.isTemplate {
749 // TODO: disallow altogether or only when it refers to fields.
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100750 if template == nil {
751 template = v
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100752 } else {
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100753 template = mkBin(ctx, c.Pos(), opUnify, template, v)
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100754 }
755 return nil
756 }
757 // TODO(perf): improve big O
758 f := ctx.label(k.strValue(), true)
759 for i, a := range newArcs {
760 if a.feature == f {
761 newArcs[i].v = mkBin(ctx, x.Pos(), opUnify, a.v, v)
762 return nil
763 }
764 }
765 newArcs = append(newArcs, arc{feature: f, v: v})
766 return nil
767 })
768 switch {
769 case result == nil:
770 case isBottom(result):
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100771 emit = result
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100772 default:
773 panic("should not happen")
774 }
775 }
776
777 // new arcs may be merged with old ones, but only if the old ones were not
778 // referred to in the evaluation of any of the arcs.
779 // TODO(perf): improve big O
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100780 arcs := make([]arc, 0, len(x.arcs)+len(newArcs))
781 arcs = append(arcs, x.arcs...)
Marcel van Lohuizen3d30a782019-02-18 23:32:10 +0100782 orig := x
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100783 x = &structLit{x.baseValue, emit, template, nil, arcs, nil}
784 x.expanded = x
Marcel van Lohuizen3d30a782019-02-18 23:32:10 +0100785 orig.expanded = x
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100786
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100787outer:
788 for _, na := range newArcs {
789 f := na.feature
790 for i, a := range x.arcs {
791 if a.feature == f {
792 if x.arcs[i].cache != nil {
793 x.arcs[i].cache = ctx.mkErr(na.v, "field %s both generated by and referred to by field comprehension in same struct",
794 ctx.labelStr(f))
795 } else {
796 x.arcs[i].v = mkBin(ctx, x.Pos(), opUnify, a.v, na.v)
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100797 x.arcs[i].optional = x.arcs[i].optional && optional
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100798 }
799 continue outer
800 }
801 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100802 x.arcs = append(x.arcs, arc{feature: f, optional: optional, v: na.v})
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100803 }
804 sort.Stable(x)
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100805 return x
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100806}
807
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100808func (x *structLit) applyTemplate(ctx *context, i int, v evaluated) evaluated {
809 if x.template != nil {
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100810 fn, err := evalLambda(ctx, x.template)
811 if err != nil {
812 return err
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100813 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100814 name := ctx.labelStr(x.arcs[i].feature)
815 arg := &stringLit{x.baseValue, name}
816 w := fn.call(ctx, x, arg).evalPartial(ctx)
817 v = binOp(ctx, x, opUnify, v, w)
818 }
819 return v
820}
821
822// A label is a canonicalized feature name.
823type label uint32
824
825const hidden label = 0x01 // only set iff identifier starting with $
826
827// An arc holds the label-value pair.
828//
829// A fully evaluated arc has either a node or a value. An unevaluated arc,
830// however, may have both. In this case, the value must ultimately evaluate
831// to a node, which will then be merged with the existing one.
832type arc struct {
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100833 feature label
834 optional bool
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200835 // TODO: add index to preserve approximate order within a struct and use
836 // topological sort to compute new struct order when unifying. This could
837 // also be achieved by not sorting labels on features and doing
838 // a linear search in fields.
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100839
840 v value
841 cache evaluated // also used as newValue during unification.
Marcel van Lohuizenb9b62d32019-03-14 23:50:15 +0100842 attrs *attributes
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100843}
844
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100845func (a *arc) val() evaluated {
846 return a.cache
847}
848
849func (a *arc) setValue(v value) {
850 a.v = v
851 a.cache = nil
852}
853
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100854type arcInfo struct {
855 hidden bool
856 tags []string // name:string
857}
858
859var hiddenArc = &arcInfo{hidden: true}
860
861// insertValue is used during initialization but never during evaluation.
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100862func (x *structLit) insertValue(ctx *context, f label, optional bool, value value, a *attributes) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100863 for i, p := range x.arcs {
864 if f != p.feature {
865 continue
866 }
867 x.arcs[i].v = mkBin(ctx, token.NoPos, opUnify, p.v, value)
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100868 // TODO: should we warn if there is a mixed mode of optional and non
869 // optional fields at this point?
870 x.arcs[i].optional = x.arcs[i].optional && optional
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100871 return
872 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100873 x.arcs = append(x.arcs, arc{f, optional, value, nil, a})
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100874 sort.Stable(x)
875}
876
877// A nodeRef is a reference to a node.
878type nodeRef struct {
879 baseValue
880 node scope
881}
882
883func (x *nodeRef) kind() kind {
884 // TODO(REWORK): no context available
885 // n := x.node.deref(nil)
886 n := x.node
887 return n.kind() | nonGround | referenceKind
888}
889
890type selectorExpr struct {
891 baseValue
892 x value
893 feature label
894}
895
896// TODO: could this be narrowed down?
897func (x *selectorExpr) kind() kind {
898 isRef := x.x.kind() & referenceKind
899 return topKind | isRef
900}
901
902type indexExpr struct {
903 baseValue
904 x value
905 index value
906}
907
908// TODO: narrow this down when we have list types.
909func (x *indexExpr) kind() kind { return topKind | referenceKind }
910
911type sliceExpr struct {
912 baseValue
913 x value
914 lo value
915 hi value
916}
917
918// TODO: narrow this down when we have list types.
919func (x *sliceExpr) kind() kind { return topKind | referenceKind }
920
921type callExpr struct {
922 baseValue
923 x value
924 args []value
925}
926
927func (x *callExpr) kind() kind {
928 // TODO: could this be narrowed down?
929 if l, ok := x.x.(*lambdaExpr); ok {
930 return l.returnKind() | nonGround
931 }
932 return topKind | referenceKind
933}
934
935type params struct {
936 arcs []arc
937}
938
939func (x *params) add(f label, v value) {
940 if v == nil {
941 panic("nil node")
942 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100943 x.arcs = append(x.arcs, arc{feature: f, v: v})
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100944}
945
946func (x *params) iterAt(ctx *context, i int) (evaluated, value) {
947 if i >= len(x.arcs) {
948 return nil, nil
949 }
950 return x.at(ctx, i), x.arcs[i].v
951}
952
953// lookup returns the node for the given label f, if present, or nil otherwise.
954func (x *params) at(ctx *context, i int) evaluated {
955 // Lookup is done by selector or index references. Either this is done on
956 // literal nodes or nodes obtained from references. In the later case,
957 // noderef will have ensured that the ancestors were evaluated.
958 if x.arcs[i].cache == nil {
959 x.arcs[i].cache = x.arcs[i].v.evalPartial(ctx)
960 }
961 return x.arcs[i].cache
962}
963
964// lookup returns the node for the given label f, if present, or nil otherwise.
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100965func (x *params) lookup(ctx *context, f label) arc {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100966 // Lookup is done by selector or index references. Either this is done on
967 // literal nodes or nodes obtained from references. In the later case,
968 // noderef will have ensured that the ancestors were evaluated.
969 for i, a := range x.arcs {
970 if a.feature == f {
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100971 a.cache = x.at(ctx, i)
972 return a
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100973 }
974 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100975 return arc{}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100976}
977
978type lambdaExpr struct {
979 baseValue
980 *params
981 value value
982}
983
984// TODO: could this be narrowed down?
985func (x *lambdaExpr) kind() kind { return lambdaKind }
986func (x *lambdaExpr) returnKind() kind { return x.value.kind() }
987
988// call calls and evaluates a lambda expression. It is assumed that x may be
989// destroyed, either because it is copied as a result of a reference or because
990// it is invoked as a literal.
991func (x *lambdaExpr) call(ctx *context, p source, args ...evaluated) value {
992 // fully evaluated.
993 if len(x.params.arcs) != len(args) {
994 return ctx.mkErr(p, x, "number of arguments does not match (%d vs %d)",
995 len(x.params.arcs), len(args))
996 }
997
998 // force parameter substitution. It is important that the result stands on
999 // its own and does not depend on its input parameters.
1000 arcs := make(arcs, len(x.arcs))
1001 for i, a := range x.arcs {
1002 v := unify(ctx, p, a.v.evalPartial(ctx), args[i])
1003 if isBottom(v) {
1004 return v
1005 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +01001006 arcs[i] = arc{feature: a.feature, v: v, cache: v}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001007 }
1008 lambda := &lambdaExpr{x.baseValue, &params{arcs}, nil}
1009 defer ctx.pushForwards(x, lambda).popForwards()
Marcel van Lohuizen66db9202018-12-17 19:02:08 +01001010 obj := ctx.copy(x.value)
1011 return obj
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001012}
1013
1014// Operations
1015
1016type unaryExpr struct {
1017 baseValue
1018 op op
1019 x value
1020}
1021
1022func (x *unaryExpr) kind() kind { return x.x.kind() }
1023
1024type binaryExpr struct {
1025 baseValue
1026 op op
1027 left value
1028 right value
1029}
1030
1031func mkBin(ctx *context, pos token.Pos, op op, left, right value) value {
1032 if left == nil || right == nil {
1033 panic("operands may not be nil")
1034 }
1035 if op == opUnify {
1036 if left == right {
1037 return left
1038 }
1039 if _, ok := left.(*top); ok {
1040 return right
1041 }
1042 if _, ok := right.(*top); ok {
1043 return left
1044 }
1045 // TODO(perf): consider adding a subsumption filter.
1046 // if subsumes(ctx, left, right) {
1047 // return right
1048 // }
1049 // if subsumes(ctx, right, left) {
1050 // return left
1051 // }
1052 }
1053 return &binaryExpr{binSrc(pos, op, left, right), op, left, right}
1054}
1055
1056func (x *binaryExpr) kind() kind {
1057 // TODO: cache results
1058 kind, _ := matchBinOpKind(x.op, x.left.kind(), x.right.kind())
1059 return kind | nonGround
1060}
1061
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +01001062// unification collects evaluated values that are not mutually exclusive
1063// but cannot be represented as a single value. It allows doing the bookkeeping
1064// on accumulating conjunctions, simplifying them along the way, until they do
1065// resolve into a single value.
1066type unification struct {
1067 baseValue
1068 values []evaluated
1069}
1070
1071func (x *unification) kind() kind {
1072 k := topKind
1073 for _, v := range x.values {
1074 k &= v.kind()
1075 }
1076 return k | nonGround
1077}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001078
1079type disjunction struct {
1080 baseValue
1081
1082 values []dValue
1083
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +02001084 hasDefaults bool // also true if it had elminated defaults.
1085
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001086 // bind is the node that a successful disjunction will bind to. This
1087 // allows other arcs to point to this node before the disjunction is
1088 // completed. For early failure, this node can be set to the glb of all
1089 // disjunctions. Otherwise top will suffice.
1090 // bind node
1091}
1092
1093type dValue struct {
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001094 val value
1095 marked bool
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001096}
1097
1098func (x *disjunction) kind() kind {
1099 k := kind(0)
1100 for _, v := range x.values {
1101 k |= v.val.kind()
1102 }
1103 if k != bottomKind {
1104 k |= nonGround
1105 }
1106 return k
1107}
1108
1109func (x *disjunction) Pos() token.Pos { return x.values[0].val.Pos() }
1110
1111// add add a value to the disjunction. It is assumed not to be a disjunction.
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001112func (x *disjunction) add(ctx *context, v value, marked bool) {
1113 x.values = append(x.values, dValue{v, marked})
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001114}
1115
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001116// normalize removes redundant element from unification.
1117// x must already have been evaluated.
1118func (x *disjunction) normalize(ctx *context, src source) mVal {
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +01001119 leq := func(ctx *context, lt, gt dValue) bool {
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001120 if isBottom(lt.val) {
1121 return true
1122 }
1123 return (!lt.marked || gt.marked) && subsumes(ctx, gt.val, lt.val, 0)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001124 }
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001125 k := 0
Marcel van Lohuizen0e2bcd52019-04-03 22:33:14 +02001126
1127 // manifesting values should be disabled for recursive evaluation as
1128 // these values may still be bound to another value later on, for instance
1129 // when the result of this value is unified with another value.
1130 noManifest := ctx.noManifest
1131 ctx.noManifest = true
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001132outer:
1133 for i, v := range x.values {
Marcel van Lohuizen004bef52019-01-30 14:07:06 +01001134 // TODO: this is pre-evaluation is quite aggressive. Verify whether
1135 // this does not trigger structural cycles. If so, this can check for
1136 // bottom and the validation can be delayed to as late as picking
1137 // defaults. The drawback of this approach is that printed intermediate
1138 // results will not look great.
1139 if err := validate(ctx, v.val); err != nil {
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001140 continue
1141 }
1142 for j, w := range x.values {
1143 if i == j {
1144 continue
1145 }
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +01001146 if leq(ctx, v, w) && (!leq(ctx, w, v) || j < i) {
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001147 // strictly subsumed, or equal and and the equal element was
1148 // processed earlier.
1149 continue outer
1150 }
1151 }
1152 // If there was a three-way equality, an element w, where w == v could
1153 // already have been added.
1154 for j := 0; j < k; j++ {
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +01001155 if leq(ctx, v, x.values[j]) {
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001156 continue outer
1157 }
1158 }
1159 x.values[k] = v
1160 k++
1161 }
Marcel van Lohuizen0e2bcd52019-04-03 22:33:14 +02001162 ctx.noManifest = noManifest
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001163
1164 switch k {
1165 case 0:
1166 // Empty disjunction. All elements must be errors.
1167 // Take the first error as an example.
Marcel van Lohuizen2601ab82019-04-03 23:04:16 +02001168 err := x.values[0].val
1169 if !isBottom(err) {
1170 err = ctx.mkErr(src, debugStr(ctx, err))
1171 }
1172 return mVal{ctx.mkErr(src, "empty disjunction: %v", err), false}
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +01001173 case 1:
1174 v := x.values[0]
1175 return mVal{v.val.(evaluated), v.marked}
1176 }
1177 x.values = x.values[:k]
1178 return mVal{x, false}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001179}
1180
1181type listComprehension struct {
1182 baseValue
1183 clauses yielder
1184}
1185
1186func (x *listComprehension) kind() kind {
1187 return listKind | nonGround | referenceKind
1188}
1189
Marcel van Lohuizen66db9202018-12-17 19:02:08 +01001190type fieldComprehension struct {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001191 baseValue
1192 clauses yielder
1193 isTemplate bool
1194}
1195
Marcel van Lohuizen66db9202018-12-17 19:02:08 +01001196func (x *fieldComprehension) kind() kind {
1197 return topKind | nonGround
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001198}
1199
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +01001200type yieldFunc func(k, v evaluated, optional bool) *bottom
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001201
1202type yielder interface {
1203 value
1204 yield(*context, yieldFunc) evaluated
1205}
1206
1207type yield struct {
1208 baseValue
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +01001209 opt bool
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001210 key value
1211 value value
1212}
1213
1214func (x *yield) kind() kind { return topKind | referenceKind }
1215
1216func (x *yield) yield(ctx *context, fn yieldFunc) evaluated {
1217 var k evaluated
1218 if x.key != nil {
1219 k = ctx.manifest(x.key)
1220 if isBottom(k) {
1221 return k
1222 }
1223 } else {
1224 k = &top{}
1225 }
1226 v := x.value.evalPartial(ctx)
1227 if isBottom(v) {
1228 return v
1229 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +01001230 if err := fn(k, v, x.opt); err != nil {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001231 return err
1232 }
1233 return nil
1234}
1235
1236type guard struct { // rename to guard
1237 baseValue
1238 condition value
1239 value yielder
1240}
1241
1242func (x *guard) kind() kind { return topKind | referenceKind }
1243
1244func (x *guard) yield(ctx *context, fn yieldFunc) evaluated {
1245 filter := ctx.manifest(x.condition)
1246 if isBottom(filter) {
1247 return filter
1248 }
1249 if err := checkKind(ctx, filter, boolKind); err != nil {
1250 return err
1251 }
1252 if filter.(*boolLit).b {
1253 if err := x.value.yield(ctx, fn); err != nil {
1254 return err
1255 }
1256 }
1257 return nil
1258}
1259
1260type feed struct {
1261 baseValue
1262 source value
1263 fn *lambdaExpr
1264}
1265
1266func (x *feed) kind() kind { return topKind | referenceKind }
1267
1268func (x *feed) yield(ctx *context, yfn yieldFunc) (result evaluated) {
1269 if ctx.trace {
1270 defer uni(indent(ctx, "feed", x))
1271 }
1272 source := ctx.manifest(x.source)
1273 fn := x.fn // no need to evaluate eval
1274
1275 switch src := source.(type) {
1276 case *structLit:
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +01001277 src = src.expandFields(ctx)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001278 for i, a := range src.arcs {
1279 key := &stringLit{
1280 x.baseValue,
1281 ctx.labelStr(a.feature),
1282 }
1283 val := src.at(ctx, i)
1284 v := fn.call(ctx, x, key, val)
1285 if isBottom(v) {
1286 return v.evalPartial(ctx)
1287 }
1288 if err := v.(yielder).yield(ctx, yfn); err != nil {
1289 return err
1290 }
1291 }
1292 return nil
1293
1294 case *list:
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001295 for i := range src.elem.arcs {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001296 idx := newNum(x, intKind)
1297 idx.v.SetInt64(int64(i))
1298 v := fn.call(ctx, x, idx, src.at(ctx, i))
1299 if isBottom(v) {
1300 return v.evalPartial(ctx)
1301 }
1302 if err := v.(yielder).yield(ctx, yfn); err != nil {
1303 return err
1304 }
1305 }
1306 return nil
1307
1308 default:
1309 if isBottom(source) {
1310 return source
1311 }
1312 if k := source.kind(); k&(structKind|listKind) == bottomKind {
1313 return ctx.mkErr(x, x.source, "feed source must be list or struct, found %s", k)
1314 }
1315 return ctx.mkErr(x, "feed source not fully evaluated to struct or list")
1316 }
1317}