blob: e9bbd43682a26fd84049141aa2b6ba1ffcc65401 [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"
19 "math/big"
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +010020 "regexp"
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010021 "sort"
22 "strings"
23 "time"
24
25 "cuelang.org/go/cue/token"
26 "github.com/cockroachdb/apd"
27)
28
29// binSrc returns a baseValue representing a binary expression of the given
30// values.
31func binSrc(pos token.Pos, op op, a, b value) baseValue {
32 return baseValue{&computedSource{pos, op, a, b}}
33}
34
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010035func unify(ctx *context, src source, left, right evaluated) evaluated {
36 return binOp(ctx, src, opUnify, left, right)
37}
38
39func binOp(ctx *context, src source, op op, left, right evaluated) (result evaluated) {
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +020040 if b, ok := left.(*bottom); ok {
41 if op == opUnify && b.exprDepth == 0 && cycleError(b) != nil {
Marcel van Lohuizen004bef52019-01-30 14:07:06 +010042 ctx.cycleErr = true
43 return right
44 }
45 return left
46 }
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +020047 if b, ok := right.(*bottom); ok {
48 if op == opUnify && b.exprDepth == 0 && cycleError(b) != nil {
Marcel van Lohuizen004bef52019-01-30 14:07:06 +010049 ctx.cycleErr = true
50 return left
51 }
52 return right
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010053 }
54
55 leftKind := left.kind()
56 rightKind := right.kind()
57 kind, invert := matchBinOpKind(op, leftKind, rightKind)
58 if kind == bottomKind {
59 return ctx.mkIncompatible(src, op, left, right)
60 }
61 if kind.hasReferences() {
62 panic("unexpected references in expression")
63 }
64 if invert {
65 left, right = right, left
66 }
67 if op != opUnify {
Jonathan Amsterdam0500c312019-02-16 18:04:09 -050068 // Any operation other than unification or disjunction must be on
69 // concrete types. Disjunction is handled separately.
70 if !leftKind.isGround() || !rightKind.isGround() {
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +010071 return ctx.mkErr(src, codeIncomplete, "incomplete error")
72 }
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +020073 ctx.incEvalDepth()
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010074 v := left.binOp(ctx, src, op, right) // may return incomplete
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +020075 ctx.decEvalDepth()
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010076 return v
77 }
78
79 // op == opUnify
80
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010081 // TODO: unify type masks.
82 if left == right {
83 return left
84 }
85 if isTop(left) {
86 return right
87 }
88 if isTop(right) {
89 return left
90 }
91
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +010092 if dl, ok := left.(*disjunction); ok {
93 return distribute(ctx, src, dl, right)
94 } else if dr, ok := right.(*disjunction); ok {
95 return distribute(ctx, src, dr, left)
96 }
97
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +010098 if _, ok := right.(*unification); ok {
99 return right.binOp(ctx, src, opUnify, left)
100 }
101
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100102 // TODO: value may be incomplete if there is a cycle. Instead of an error
103 // schedule an assert and return the atomic value, if applicable.
104 v := left.binOp(ctx, src, op, right)
105 if isBottom(v) {
106 v := right.binOp(ctx, src, op, left)
107 // Return the original failure if both fail, as this will result in
108 // better error messages.
109 if !isBottom(v) {
110 return v
111 }
112 }
113 return v
114}
115
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100116type mVal struct {
117 val evaluated
118 mark bool
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100119}
120
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100121// distribute distributes a value over the element of a disjunction in a
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200122// unification operation.
123// TODO: this is an exponential algorithm. There is no reason to have to
124// resolve this early. Revise this to only do early pruning but not a full
125// evaluation.
126func distribute(ctx *context, src source, x, y evaluated) evaluated {
127 dn := &disjunction{baseValue: src.base()}
128 dist(ctx, dn, false, mVal{x, true}, mVal{y, true})
129 return dn.normalize(ctx, src).val
Marcel van Lohuizenc9b3cb22019-01-30 11:32:41 +0100130}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100131
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200132func dist(ctx *context, d *disjunction, mark bool, x, y mVal) {
133 if dx, ok := x.val.(*disjunction); ok {
134 if dx.hasDefaults {
135 mark = true
136 d.hasDefaults = true
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100137 }
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200138 for _, dxv := range dx.values {
139 m := dxv.marked || !dx.hasDefaults
140 dist(ctx, d, mark, mVal{dxv.val.evalPartial(ctx), m}, y)
141 }
142 return
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100143 }
Marcel van Lohuizen94d845d2019-05-10 00:28:03 +0200144 if dy, ok := y.val.(*disjunction); ok {
145 if dy.hasDefaults {
146 mark = true
147 d.hasDefaults = true
148 }
149 for _, dxy := range dy.values {
150 m := dxy.marked || !dy.hasDefaults
151 dist(ctx, d, mark, x, mVal{dxy.val.evalPartial(ctx), m})
152 }
153 return
154 }
155 src := binSrc(0, opUnify, x.val, y.val)
156 d.add(ctx, binOp(ctx, src, opUnify, x.val, y.val), mark && x.mark && y.mark)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100157}
158
159func (x *disjunction) binOp(ctx *context, src source, op op, other evaluated) evaluated {
160 panic("unreachable: special-cased")
161}
162
163func (x *bottom) binOp(ctx *context, src source, op op, other evaluated) evaluated {
164 panic("unreachable: special-cased")
165}
166
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100167func (x *unification) add(ctx *context, src source, v evaluated) evaluated {
168 for progress := true; progress; {
169 progress = false
170 k := 0
171
172 for i, vx := range x.values {
173 a := binOp(ctx, src, opUnify, vx, v)
174 switch _, isUnify := a.(*unification); {
175 case isBottom(a):
176 if !isIncomplete(a) {
177 return a
178 }
179 fallthrough
180 case isUnify:
181 x.values[k] = x.values[i]
182 k++
183 continue
184 }
185 // k will not be raised in this iteration. So the outer loop
186 // will ultimately terminate as k reaches 0.
187 // In practice it is seems unlikely that there will be more than
188 // two iterations for any addition.
189 // progress = true
190 v = a
191 }
192 if k == 0 {
193 return v
194 }
195 x.values = x.values[:k]
196 }
197 x.values = append(x.values, v)
198 return nil
199}
200
201func (x *unification) binOp(ctx *context, src source, op op, other evaluated) evaluated {
202 if op == opUnify {
203 u := &unification{baseValue: baseValue{src}}
204 u.values = append(u.values, x.values...)
205 if y, ok := other.(*unification); ok {
206 for _, vy := range y.values {
207 if v := u.add(ctx, src, vy); v != nil {
208 return v
209 }
210 }
211 } else if v := u.add(ctx, src, other); v != nil {
212 return v
213 }
214 return u
215 }
216 return ctx.mkIncompatible(src, op, x, other)
217}
218
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100219func (x *top) binOp(ctx *context, src source, op op, other evaluated) evaluated {
220 switch op {
221 case opUnify:
222 return other
223 }
224 src = mkBin(ctx, src.Pos(), op, x, other)
225 return ctx.mkErr(src, "binary operation on non-ground top value")
226}
227
228func (x *basicType) binOp(ctx *context, src source, op op, other evaluated) evaluated {
229 k := unifyType(x.kind(), other.kind())
230 switch y := other.(type) {
231 case *basicType:
232 switch op {
233 // TODO: other types.
234 case opUnify:
235 if k&typeKinds != bottomKind {
236 return &basicType{binSrc(src.Pos(), op, x, other), k & typeKinds}
237 }
238 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100239
240 case *bound:
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100241 src = mkBin(ctx, src.Pos(), op, x, other)
242 return ctx.mkErr(src, codeIncomplete, "%s with incomplete values", op)
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100243
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100244 case *numLit:
245 if op == opUnify {
246 if k == y.k {
247 return y
248 }
249 i := *y
250 i.k = k
251 return &i
252 }
253 src = mkBin(ctx, src.Pos(), op, x, other)
254 return ctx.mkErr(src, codeIncomplete, "%s with incomplete values", op)
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100255
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100256 default:
257 if k&typeKinds != bottomKind {
258 return other
259 }
260 }
261 return ctx.mkIncompatible(src, op, x, other)
262}
263
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100264func checkBounds(ctx *context, src source, r *bound, op op, a, b evaluated) evaluated {
265 v := binOp(ctx, src, op, a, b)
266 if isBottom(v) || !v.(*boolLit).b {
267 return errOutOfBounds(ctx, src.Pos(), r, a)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100268 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100269 return nil
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100270}
271
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100272func errOutOfBounds(ctx *context, pos token.Pos, r *bound, v evaluated) *bottom {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100273 if pos == token.NoPos {
274 pos = r.Pos()
275 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100276 e := mkBin(ctx, pos, opUnify, r, v)
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100277 msg := "%v not within bound %v"
278 switch r.op {
279 case opNeq, opNMat:
280 msg = "%v excluded by %v"
281 case opMat:
282 msg = "%v does not match %v"
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100283 }
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100284 return ctx.mkErr(e, msg, debugStr(ctx, v), debugStr(ctx, r))
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100285}
286
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100287func opInfo(op op) (cmp op, norm int) {
288 switch op {
289 case opGtr:
290 return opGeq, 1
291 case opGeq:
292 return opGtr, 1
293 case opLss:
294 return opLeq, -1
295 case opLeq:
296 return opLss, -1
297 case opNeq:
298 return opNeq, 0
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100299 case opMat:
300 return opMat, 2
301 case opNMat:
302 return opNMat, 3
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100303 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100304 panic("cue: unreachable")
305}
306
307func (x *bound) binOp(ctx *context, src source, op op, other evaluated) evaluated {
308 xv := x.value.(evaluated)
309
310 newSrc := binSrc(src.Pos(), op, x, other)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100311 switch op {
312 case opUnify:
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100313 k, _ := matchBinOpKind(opUnify, x.kind(), other.kind())
314 if k == bottomKind {
315 break
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100316 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100317 switch y := other.(type) {
318 case *basicType:
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200319 k := unifyType(x.k, y.kind())
320 if k == x.k {
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100321 return x
322 }
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200323 return newBound(newSrc.base(), x.op, k, xv)
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100324
325 case *bound:
326 yv := y.value.(evaluated)
327 if !xv.kind().isGround() || !yv.kind().isGround() {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100328 return ctx.mkErr(newSrc, codeIncomplete, "cannot add incomplete values")
329 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100330
331 cmp, xCat := opInfo(x.op)
332 _, yCat := opInfo(y.op)
333
334 switch {
335 case xCat == yCat:
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100336 if x.op == opNeq || x.op == opMat || x.op == opNMat {
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100337 if test(ctx, x, opEql, xv, yv) {
338 return x
339 }
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100340 break // unify the two bounds
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100341 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100342
343 // xCat == yCat && x.op != opNeq
344 // > a & >= b
345 // > a if a >= b
346 // >= b if a < b
347 // > a & > b
348 // > a if a >= b
349 // > b if a < b
350 // >= a & > b
351 // >= a if a > b
352 // > b if a <= b
353 // >= a & >= b
354 // >= a if a > b
355 // >= b if a <= b
356 // inverse is true as well.
357
358 // Tighten bound.
359 if test(ctx, x, cmp, xv, yv) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100360 return x
361 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100362 return y
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100363
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100364 case xCat == -yCat:
365 if xCat == -1 {
366 x, y = y, x
367 }
368 a, aOK := x.value.(evaluated).(*numLit)
369 b, bOK := y.value.(evaluated).(*numLit)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100370
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100371 if !aOK || !bOK {
372 break
373 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100374
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100375 var d apd.Decimal
376 cond, err := apd.BaseContext.Sub(&d, &b.v, &a.v)
377 if cond.Inexact() || err != nil {
378 break
379 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100380
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100381 // attempt simplification
382 // numbers
383 // >=a & <=b
384 // a if a == b
385 // _|_ if a < b
386 // >=a & <b
387 // _|_ if b <= a
388 // >a & <=b
389 // _|_ if b <= a
390 // >a & <b
391 // _|_ if b <= a
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100392
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100393 // integers
394 // >=a & <=b
395 // a if b-a == 0
396 // _|_ if a < b
397 // >=a & <b
398 // a if b-a == 1
399 // _|_ if b <= a
400 // >a & <=b
401 // b if b-a == 1
402 // _|_ if b <= a
403 // >a & <b
404 // a+1 if b-a == 2
405 // _|_ if b <= a
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100406
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100407 switch diff, err := d.Int64(); {
408 case err != nil:
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100409
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100410 case diff == 1:
411 if k&floatKind == 0 {
412 if x.op == opGeq && y.op == opLss {
413 return a
414 }
415 if x.op == opGtr && y.op == opLeq {
416 return b
417 }
418 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100419
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100420 case diff == 2:
421 if k&floatKind == 0 && x.op == opGtr && y.op == opLss {
422 apd.BaseContext.Add(&d, d.SetInt64(1), &a.v)
423 n := *a
424 n.k = k
425 n.v = d
426 return &n
427 }
428
429 case diff == 0:
430 if x.op == opGeq && y.op == opLeq {
431 return a
432 }
433 fallthrough
434
435 case d.Negative:
436 return ctx.mkErr(newSrc, "incompatible bounds %v and %v",
437 debugStr(ctx, x), debugStr(ctx, y))
438 }
439
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100440 case x.op == opNeq:
441 if !test(ctx, x, y.op, xv, yv) {
442 return y
443 }
444
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100445 case y.op == opNeq:
446 if !test(ctx, x, x.op, yv, xv) {
447 return x
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100448 }
449 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100450 return &unification{newSrc, []evaluated{x, y}}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100451
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100452 case *numLit:
453 if err := checkBounds(ctx, src, x, x.op, y, xv); err != nil {
454 return err
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100455 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100456 // Narrow down number type.
457 if y.k != k {
458 n := *y
459 n.k = k
460 return &n
461 }
462 return other
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100463
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100464 case *nullLit, *boolLit, *durationLit, *list, *structLit, *stringLit, *bytesLit:
465 // All remaining concrete types. This includes non-comparable types
466 // for comparison to null.
467 if err := checkBounds(ctx, src, x, x.op, y, xv); err != nil {
468 return err
469 }
470 return y
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100471 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100472 }
473 return ctx.mkIncompatible(src, op, x, other)
474}
475
476func evalLambda(ctx *context, a value) (l *lambdaExpr, err evaluated) {
477 if a == nil {
478 return nil, nil
479 }
480 // NOTE: the values of a lambda might still be a disjunction
481 e := ctx.manifest(a)
482 if isBottom(e) {
483 return nil, e
484 }
485 l, ok := e.(*lambdaExpr)
486 if !ok {
487 return nil, ctx.mkErr(a, "value must be lambda")
488 }
489 return ctx.deref(l).(*lambdaExpr), nil
490}
491
492func (x *structLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
493 y, ok := other.(*structLit)
494 if !ok || op != opUnify {
495 return ctx.mkIncompatible(src, op, x, other)
496 }
497
498 // TODO: unify emit
499
500 x = ctx.deref(x).(*structLit)
501 y = ctx.deref(y).(*structLit)
502 if x == y {
503 return x
504 }
505 arcs := make(arcs, 0, len(x.arcs)+len(y.arcs))
Marcel van Lohuizen7f48df72019-02-01 17:24:59 +0100506 obj := &structLit{binSrc(src.Pos(), op, x, other), x.emit, nil, nil, arcs, nil}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100507 defer ctx.pushForwards(x, obj, y, obj).popForwards()
508
509 tx, ex := evalLambda(ctx, x.template)
510 ty, ey := evalLambda(ctx, y.template)
511
512 var t *lambdaExpr
513 switch {
514 case ex != nil:
515 return ex
516 case ey != nil:
517 return ey
518 case tx != nil:
519 t = tx
520 case ty != nil:
521 t = ty
522 }
523 if tx != ty && tx != nil && ty != nil {
524 v := binOp(ctx, src, opUnify, tx, ty)
525 if isBottom(v) {
526 return v
527 }
528 t = v.(*lambdaExpr)
529 }
530 if t != nil {
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100531 obj.template = ctx.copy(t)
532 }
533
534 sz := len(x.comprehensions) + len(y.comprehensions)
535 obj.comprehensions = make([]*fieldComprehension, sz)
536 for i, c := range x.comprehensions {
537 obj.comprehensions[i] = ctx.copy(c).(*fieldComprehension)
538 }
539 for i, c := range y.comprehensions {
540 obj.comprehensions[i+len(x.comprehensions)] = ctx.copy(c).(*fieldComprehension)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100541 }
542
543 for _, a := range x.arcs {
544 cp := ctx.copy(a.v)
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100545 obj.arcs = append(obj.arcs,
546 arc{a.feature, a.optional, cp, nil, a.attrs})
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100547 }
548outer:
549 for _, a := range y.arcs {
550 v := ctx.copy(a.v)
551 for i, b := range obj.arcs {
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100552 if a.feature == b.feature {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100553 v = mkBin(ctx, src.Pos(), opUnify, b.v, v)
554 obj.arcs[i].v = v
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100555 obj.arcs[i].cache = nil
556 obj.arcs[i].optional = a.optional && b.optional
Marcel van Lohuizenb9b62d32019-03-14 23:50:15 +0100557 attrs, err := unifyAttrs(ctx, src, a.attrs, b.attrs)
558 if err != nil {
559 return err
560 }
561 obj.arcs[i].attrs = attrs
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100562 continue outer
563 }
564 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100565 a.setValue(v)
566 obj.arcs = append(obj.arcs, a)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100567 }
568 sort.Stable(obj)
569
570 return obj
571}
572
573func (x *nullLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
574 // TODO: consider using binSrc instead of src.base() for better traceability.
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100575 switch other.(type) {
576 case *nullLit:
577 switch op {
578 case opEql:
579 return &boolLit{baseValue: src.base(), b: true}
580 case opNeq:
581 return &boolLit{baseValue: src.base(), b: false}
582 case opUnify:
583 return x
584 }
585
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100586 case *bound:
587 // Not strictly necessary, but handling this results in better error
588 // messages.
589 if op == opUnify {
590 return other.binOp(ctx, src, opUnify, x)
591 }
592
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100593 default:
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100594 switch op {
595 case opEql:
596 return &boolLit{baseValue: src.base(), b: false}
597 case opNeq:
598 return &boolLit{baseValue: src.base(), b: true}
599 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100600 }
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100601 return ctx.mkIncompatible(src, op, x, other)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100602}
603
604func (x *boolLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
605 switch y := other.(type) {
606 case *basicType:
607 // range math
608 return x
609
610 case *boolLit:
611 switch op {
612 case opUnify:
613 if x.b != y.b {
614 return ctx.mkErr(x, "failed to unify: %v != %v", x.b, y.b)
615 }
616 return x
617 case opLand:
618 return boolTonode(src, x.b && y.b)
619 case opLor:
620 return boolTonode(src, x.b || y.b)
621 case opEql:
622 return boolTonode(src, x.b == y.b)
623 case opNeq:
624 return boolTonode(src, x.b != y.b)
625 }
626 }
627 return ctx.mkIncompatible(src, op, x, other)
628}
629
630func (x *stringLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100631 switch y := other.(type) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100632 // case *basicType:
633 // return x
634
635 // TODO: rangelit
636
637 case *stringLit:
638 str := other.strValue()
639 switch op {
640 case opUnify:
641 str := other.strValue()
642 if x.str != str {
643 src := mkBin(ctx, src.Pos(), op, x, other)
644 return ctx.mkErr(src, "failed to unify: %v != %v", x.str, str)
645 }
646 return x
647 case opLss, opLeq, opEql, opNeq, opGeq, opGtr:
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100648 return cmpTonode(src, op, strings.Compare(x.str, str))
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100649 case opAdd:
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100650 src := binSrc(src.Pos(), op, x, other)
651 return &stringLit{src, x.str + str}
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100652 case opMat:
653 b, err := regexp.MatchString(str, x.str)
654 if err != nil {
655 return ctx.mkErr(src, "error parsing regexp: %v", err)
656 }
657 return boolTonode(src, b)
658 case opNMat:
659 b, err := regexp.MatchString(str, x.str)
660 if err != nil {
661 return ctx.mkErr(src, "error parsing regexp: %v", err)
662 }
663 return boolTonode(src, !b)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100664 }
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100665 case *numLit:
666 switch op {
667 case opMul:
668 src := binSrc(src.Pos(), op, x, other)
669 return &stringLit{src, strings.Repeat(x.str, y.intValue(ctx))}
670 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100671 }
672 return ctx.mkIncompatible(src, op, x, other)
673}
674
675func (x *bytesLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
676 switch y := other.(type) {
677 // case *basicType:
678 // return x
679
680 // TODO: rangelit
681
682 case *bytesLit:
683 b := y.b
684 switch op {
685 case opUnify:
686 if !bytes.Equal(x.b, b) {
687 return ctx.mkErr(x, "failed to unify: %v != %v", x.b, b)
688 }
689 return x
690 case opLss, opLeq, opEql, opNeq, opGeq, opGtr:
691 return cmpTonode(src, op, bytes.Compare(x.b, b))
692 case opAdd:
693 copy := append([]byte(nil), x.b...)
694 copy = append(copy, b...)
695 return &bytesLit{binSrc(src.Pos(), op, x, other), copy}
696 }
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100697
698 case *numLit:
699 switch op {
700 case opMul:
701 src := binSrc(src.Pos(), op, x, other)
702 return &bytesLit{src, bytes.Repeat(x.b, y.intValue(ctx))}
703 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100704 }
705 return ctx.mkIncompatible(src, op, x, other)
706}
707
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100708func test(ctx *context, src source, op op, a, b evaluated) bool {
709 v := binOp(ctx, src, op, a, b)
710 if isBottom(v) {
711 return false
712 }
713 return v.(*boolLit).b
714}
715
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100716func leq(ctx *context, src source, a, b evaluated) bool {
717 if isTop(a) || isTop(b) {
718 return true
719 }
720 v := binOp(ctx, src, opLeq, a, b)
721 if isBottom(v) {
722 return false
723 }
724 return v.(*boolLit).b
725}
726
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100727// TODO: should these go?
728func maxNum(v value) value {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100729 switch x := v.(type) {
730 case *numLit:
731 return x
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100732 case *bound:
733 switch x.op {
734 case opLeq:
735 return x.value
736 case opLss:
737 return &binaryExpr{x.baseValue, opSub, x.value, one}
738 }
739 return &basicType{x.baseValue, intKind}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100740 }
741 return v
742}
743
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100744func minNum(v value) value {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100745 switch x := v.(type) {
746 case *numLit:
747 return x
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100748 case *bound:
749 switch x.op {
750 case opGeq:
751 return x.value
752 case opGtr:
753 return &binaryExpr{x.baseValue, opAdd, x.value, one}
754 }
755 return &basicType{x.baseValue, intKind}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100756 }
757 return v
758}
759
760func cmpTonode(src source, op op, r int) evaluated {
761 result := false
762 switch op {
763 case opLss:
764 result = r == -1
765 case opLeq:
766 result = r != 1
767 case opEql, opUnify:
768 result = r == 0
769 case opNeq:
770 result = r != 0
771 case opGeq:
772 result = r != -1
773 case opGtr:
774 result = r == 1
775 }
776 return boolTonode(src, result)
777}
778
779func (x *numLit) updateNumInfo(a, b *numLit) {
780 x.numInfo = unifyNuminfo(a.numInfo, b.numInfo)
781}
782
783func (x *numLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
784 switch y := other.(type) {
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200785 case *basicType, *bound: // for better error reporting
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100786 if op == opUnify {
787 return y.binOp(ctx, src, op, x)
788 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100789 case *numLit:
790 k := unifyType(x.kind(), y.kind())
791 n := newNumBin(k, x, y)
792 switch op {
793 case opUnify:
794 if x.v.Cmp(&y.v) != 0 {
795 src = mkBin(ctx, src.Pos(), op, x, other)
796 return ctx.mkErr(src, "cannot unify numbers %v and %v", x.strValue(), y.strValue())
797 }
798 if k != x.k {
799 n.v = x.v
800 return n
801 }
802 return x
803 case opLss, opLeq, opEql, opNeq, opGeq, opGtr:
804 return cmpTonode(src, op, x.v.Cmp(&y.v))
805 case opAdd:
806 ctx.Add(&n.v, &x.v, &y.v)
807 case opSub:
808 ctx.Sub(&n.v, &x.v, &y.v)
809 case opMul:
810 ctx.Mul(&n.v, &x.v, &y.v)
811 case opQuo:
812 ctx.Quo(&n.v, &x.v, &y.v)
813 ctx.Reduce(&n.v, &n.v)
814 n.k = floatKind
815 case opRem:
816 ctx.Rem(&n.v, &x.v, &y.v)
817 n.k = floatKind
818 case opIDiv:
819 intOp(ctx, n, (*big.Int).Div, x, y)
820 case opIMod:
821 intOp(ctx, n, (*big.Int).Mod, x, y)
822 case opIQuo:
823 intOp(ctx, n, (*big.Int).Quo, x, y)
824 case opIRem:
825 intOp(ctx, n, (*big.Int).Rem, x, y)
826 }
827 return n
828
829 case *durationLit:
830 if op == opMul {
831 fd := float64(y.d)
832 // TODO: check range
833 f, _ := x.v.Float64()
834 d := time.Duration(f * fd)
835 return &durationLit{binSrc(src.Pos(), op, x, other), d}
836 }
837 }
838 return ctx.mkIncompatible(src, op, x, other)
839}
840
841type intFunc func(z, x, y *big.Int) *big.Int
842
843func intOp(ctx *context, n *numLit, fn intFunc, a, b *numLit) {
844 var x, y apd.Decimal
845 ctx.RoundToIntegralValue(&x, &a.v)
846 if x.Negative {
847 x.Coeff.Neg(&x.Coeff)
848 }
849 ctx.RoundToIntegralValue(&y, &b.v)
850 if y.Negative {
851 y.Coeff.Neg(&y.Coeff)
852 }
853 fn(&n.v.Coeff, &x.Coeff, &y.Coeff)
854 if n.v.Coeff.Sign() < 0 {
855 n.v.Coeff.Neg(&n.v.Coeff)
856 n.v.Negative = true
857 }
858 n.k = intKind
859}
860
861// TODO: check overflow
862
863func (x *durationLit) binOp(ctx *context, src source, op op, other evaluated) evaluated {
864 switch y := other.(type) {
865 case *basicType:
866 // infinity math
867
868 case *durationLit:
869 switch op {
870 case opUnify:
871 if x.d != y.d {
872 return ctx.mkIncompatible(src, op, x, other)
873 }
874 return other
875 case opLss:
876 return boolTonode(src, x.d < y.d)
877 case opLeq:
878 return boolTonode(src, x.d <= y.d)
879 case opEql:
880 return boolTonode(src, x.d == y.d)
881 case opNeq:
882 return boolTonode(src, x.d != y.d)
883 case opGeq:
884 return boolTonode(src, x.d >= y.d)
885 case opGtr:
886 return boolTonode(src, x.d > y.d)
887 case opAdd:
888 return &durationLit{binSrc(src.Pos(), op, x, other), x.d + y.d}
889 case opSub:
890 return &durationLit{binSrc(src.Pos(), op, x, other), x.d - y.d}
891 case opQuo:
892 n := &numLit{
893 numBase: newNumBase(nil, newNumInfo(floatKind, 0, 10, false)),
894 }
895 n.v.SetInt64(int64(x.d))
896 d := apd.New(int64(y.d), 0)
897 ctx.Quo(&n.v, &n.v, d)
898 return n
899 case opRem:
900 n := &numLit{
901 numBase: newNumBase(nil, newNumInfo(intKind, 0, 10, false)),
902 }
903 n.v.SetInt64(int64(x.d % y.d))
904 n.v.Exponent = -9
905 return n
906 }
907
908 case *numLit:
909 switch op {
910 case opMul:
911 // TODO: check range
912 f, _ := y.v.Float64()
913 d := time.Duration(float64(x.d) * f)
914 return &durationLit{binSrc(src.Pos(), op, x, other), d}
915 case opQuo:
916 // TODO: check range
917 f, _ := y.v.Float64()
918 d := time.Duration(float64(x.d) * f)
919 return &durationLit{binSrc(src.Pos(), op, x, other), d}
920 case opRem:
921 d := x.d % time.Duration(y.intValue(ctx))
922 return &durationLit{binSrc(src.Pos(), op, x, other), d}
923 }
924 }
925 return ctx.mkIncompatible(src, op, x, other)
926}
927
928func (x *list) binOp(ctx *context, src source, op op, other evaluated) evaluated {
929 switch op {
930 case opUnify:
931 y, ok := other.(*list)
932 if !ok {
933 break
934 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100935
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100936 n := unify(ctx, src, x.len.(evaluated), y.len.(evaluated))
937 if isBottom(n) {
938 src = mkBin(ctx, src.Pos(), op, x, other)
939 return ctx.mkErr(src, "incompatible list lengths: %v", n)
940 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200941 sx := x.elem.arcs
942 xa := sx
943 sy := y.elem.arcs
944 ya := sy
945 for len(xa) < len(ya) {
946 xa = append(xa, arc{feature: label(len(xa)), v: x.typ})
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100947 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200948 for len(ya) < len(xa) {
949 ya = append(ya, arc{feature: label(len(ya)), v: y.typ})
950 }
951
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100952 typ := x.typ
953 max, ok := n.(*numLit)
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200954 if !ok || len(xa) < max.intValue(ctx) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100955 typ = unify(ctx, src, x.typ.(evaluated), y.typ.(evaluated))
956 if isBottom(typ) {
957 src = mkBin(ctx, src.Pos(), op, x, other)
958 return ctx.mkErr(src, "incompatible list types: %v: ", typ)
959 }
960 }
961
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200962 // TODO: use forwarding instead of this mild hack.
963 x.elem.arcs = xa
964 y.elem.arcs = ya
965 s := unify(ctx, src, x.elem, y.elem).(*structLit)
966 x.elem.arcs = sx
967 y.elem.arcs = sy
968
969 base := binSrc(src.Pos(), op, x, other)
970 return &list{baseValue: base, elem: s, typ: typ, len: n}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100971
Marcel van Lohuizen0aeeeaf2019-02-22 19:50:18 +0100972 case opEql, opNeq:
973 y, ok := other.(*list)
974 if !ok {
975 break
976 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200977 if len(x.elem.arcs) != len(y.elem.arcs) {
Marcel van Lohuizen0aeeeaf2019-02-22 19:50:18 +0100978 return boolTonode(src, false)
979 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200980 for i := range x.elem.arcs {
Marcel van Lohuizen0aeeeaf2019-02-22 19:50:18 +0100981 if !test(ctx, src, op, x.at(ctx, i), y.at(ctx, i)) {
982 return boolTonode(src, false)
983 }
984 }
985 return boolTonode(src, true)
986
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +0100987 case opAdd:
988 y, ok := other.(*list)
989 if !ok {
990 break
991 }
992 n := &list{baseValue: binSrc(src.Pos(), op, x, other), typ: y.typ}
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200993 arcs := []arc{}
994 for _, v := range x.elem.arcs {
995 arcs = append(arcs, arc{feature: label(len(arcs)), v: v.v})
996 }
997 for _, v := range y.elem.arcs {
998 arcs = append(arcs, arc{feature: label(len(arcs)), v: v.v})
999 }
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +01001000 switch v := y.len.(type) {
1001 case *numLit:
1002 // Closed list
1003 ln := &numLit{numBase: v.numBase}
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001004 ln.v.SetInt64(int64(len(arcs)))
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +01001005 n.len = ln
1006 default:
1007 // Open list
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001008 n.len = y.len // TODO: add length of x?
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +01001009 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001010 n.elem = &structLit{baseValue: n.baseValue, arcs: arcs}
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +01001011 return n
1012
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001013 case opMul:
1014 k := other.kind()
1015 if !k.isAnyOf(intKind) {
1016 panic("multiplication must be int type")
1017 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001018 n := &list{baseValue: binSrc(src.Pos(), op, x, other), typ: x.typ}
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001019 arcs := []arc{}
1020 if len(x.elem.arcs) > 0 {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001021 if !k.isGround() {
Jonathan Amsterdam0500c312019-02-16 18:04:09 -05001022 // should never reach here.
1023 break
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001024 }
1025 if ln := other.(*numLit).intValue(ctx); ln > 0 {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001026 for i := 0; i < ln; i++ {
1027 // TODO: copy values
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001028 for _, a := range x.elem.arcs {
1029 arcs = append(arcs, arc{feature: label(len(arcs)), v: a.v})
1030 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001031 }
Jonathan Amsterdam0500c312019-02-16 18:04:09 -05001032 } else if ln < 0 {
1033 return ctx.mkErr(src, "negative number %d multiplies list", ln)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001034 }
1035 }
1036 switch v := x.len.(type) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001037 case *numLit:
Jonathan Amsterdam0500c312019-02-16 18:04:09 -05001038 // Closed list
1039 ln := &numLit{numBase: v.numBase}
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001040 ln.v.SetInt64(int64(len(arcs)))
Jonathan Amsterdam0500c312019-02-16 18:04:09 -05001041 n.len = ln
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001042 default:
Jonathan Amsterdam0500c312019-02-16 18:04:09 -05001043 // Open list
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001044 n.len = x.len // TODO: multiply length?
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001045 }
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +02001046 n.elem = &structLit{baseValue: n.baseValue, arcs: arcs}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001047 return n
1048 }
1049 return ctx.mkIncompatible(src, op, x, other)
1050}
1051
1052func (x *lambdaExpr) binOp(ctx *context, src source, op op, other evaluated) evaluated {
1053 if y, ok := other.(*lambdaExpr); ok && op == opUnify {
1054 x = ctx.deref(x).(*lambdaExpr)
1055 y = ctx.deref(y).(*lambdaExpr)
1056 n, m := len(x.params.arcs), len(y.params.arcs)
1057 if n != m {
1058 src = mkBin(ctx, src.Pos(), op, x, other)
1059 return ctx.mkErr(src, "number of params of params should match in unification (%d != %d)", n, m)
1060 }
1061 arcs := make([]arc, len(x.arcs))
1062 lambda := &lambdaExpr{binSrc(src.Pos(), op, x, other), &params{arcs}, nil}
1063 defer ctx.pushForwards(x, lambda, y, lambda).popForwards()
1064
1065 xVal := ctx.copy(x.value)
1066 yVal := ctx.copy(y.value)
1067 lambda.value = mkBin(ctx, src.Pos(), opUnify, xVal, yVal)
1068
1069 for i := range arcs {
1070 xArg := ctx.copy(x.at(ctx, i)).(evaluated)
1071 yArg := ctx.copy(y.at(ctx, i)).(evaluated)
1072 v := binOp(ctx, src, op, xArg, yArg)
1073 if isBottom(v) {
1074 return v
1075 }
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +01001076 arcs[i] = arc{feature: x.arcs[i].feature, v: v}
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001077 }
1078
1079 return lambda
1080 }
1081 return ctx.mkIncompatible(src, op, x, other)
1082}
1083
1084func (x *builtin) binOp(ctx *context, src source, op op, other evaluated) evaluated {
1085 if op == opUnify && evaluated(x) == other {
1086 return x
1087 }
1088 return ctx.mkIncompatible(src, op, x, other)
1089}
1090
1091func (x *feed) binOp(ctx *context, src source, op op, other evaluated) evaluated {
1092 return ctx.mkIncompatible(src, op, x, other)
1093}
1094
1095func (x *guard) binOp(ctx *context, src source, op op, other evaluated) evaluated {
1096 return ctx.mkIncompatible(src, op, x, other)
1097}
1098
1099func (x *yield) binOp(ctx *context, src source, op op, other evaluated) evaluated {
1100 return ctx.mkIncompatible(src, op, x, other)
1101}
Marcel van Lohuizen66db9202018-12-17 19:02:08 +01001102
1103func (x *fieldComprehension) binOp(ctx *context, src source, op op, other evaluated) evaluated {
1104 return ctx.mkIncompatible(src, op, x, other)
1105}