blob: b8b3b376e7de44a1bda844e1075328e783cd94ff [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 "fmt"
19
20 "cuelang.org/go/cue/token"
21)
22
23func unifyType(a, b kind) kind {
24 const mask = topKind
25 isRef := (a &^ mask) | (b &^ mask)
26 return isRef | (a & b)
27}
28
29type kind uint16
30
31const (
32 unknownKind kind = (1 << iota)
33 nullKind
34 boolKind
35 intKind
36 floatKind
37 stringKind
38 bytesKind
39 durationKind
40 listKind
41 structKind
42
43 lambdaKind
44 // customKind
45
46 // nonGround means that a value is not specific enough to be emitted.
47 // Structs and lists are indicated as ground even when their values are not.
48 nonGround
49
50 // TODO: distinguish beteween nonGround and disjunctions?
51
52 // a referenceKind is typically top and nonGround, but is indicated with an
53 // additional bit. If reference is set and nonGround is not, it is possible
54 // to move the reference to an assertion clause.
55 referenceKind
56
Marcel van Lohuizen855243e2019-02-07 18:00:55 +010057 atomKind = (listKind - 1) &^ unknownKind
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +010058 addableKind = (structKind - 1) &^ unknownKind
Marcel van Lohuizen855243e2019-02-07 18:00:55 +010059 concreteKind = (lambdaKind - 1) &^ unknownKind
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010060
61 // doneKind indicates a value can not further develop on its own (i.e. not a
62 // reference). If doneKind is not set, but the result is ground, it
63 // typically possible to hoist the reference out of a unification operation.
64
65 // For rational numbers, typically both intKind and floatKind are set,
66 // unless the range is restricted by a root type.
67 numKind = intKind | floatKind
68
Marcel van Lohuizen855243e2019-02-07 18:00:55 +010069 comparableKind = (listKind - 1) &^ unknownKind
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010070 stringableKind = scalarKinds | stringKind
71 topKind = (referenceKind - 1) // all kinds, but not references
Marcel van Lohuizen855243e2019-02-07 18:00:55 +010072 typeKinds = (nonGround - 1) &^ unknownKind
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010073 okKinds = typeKinds &^ bottomKind
74 fixedKinds = okKinds &^ (structKind | lambdaKind)
75 scalarKinds = numKind | durationKind
76
77 bottomKind = 0
78)
79
80func isTop(v value) bool {
81 return v.kind() == topKind
82}
83
84// isDone means that the value will not evaluate further.
85func (k kind) isDone() bool { return k&referenceKind == bottomKind }
86func (k kind) hasReferences() bool { return k&referenceKind != bottomKind }
87func (k kind) isGround() bool { return k&nonGround == bottomKind }
88func (k kind) isAtom() bool { return k.isGround() && k&atomKind != bottomKind }
89func (k kind) isAnyOf(of kind) bool {
90 return k&of != bottomKind
91}
92func (k kind) stringable() bool {
93 return k.isGround() && k&stringKind|scalarKinds != bottomKind
94}
95
96func (k kind) String() string {
97 str := ""
98 if k&topKind == topKind {
99 str = "_"
100 goto finalize
101 }
102 for i := kind(1); i < referenceKind; i <<= 1 {
103 t := ""
104 switch k & i {
105 case bottomKind:
106 continue
107 case nullKind:
108 t = "null"
109 case boolKind:
110 t = "bool"
111 case intKind:
112 if k&floatKind != 0 {
113 t = "number"
114 } else {
115 t = "int"
116 }
117 case floatKind:
118 if k&intKind != 0 {
119 continue
120 }
121 t = "float"
122 case stringKind:
123 t = "string"
124 case bytesKind:
125 t = "bytes"
126 case durationKind:
127 t = "duration"
128 case listKind:
129 t = "list"
130 case structKind:
131 t = "struct"
132 case lambdaKind:
133 t = "lambda"
134 case nonGround, referenceKind:
135 continue
136 default:
137 t = fmt.Sprintf("<unknown> %x", int(i))
138 }
139 if str != "" {
140 str += "|"
141 }
142 str += t
143 }
144finalize:
145 if str == "" {
146 return "_|_"
147 }
148 if k&nonGround != 0 {
149 str = "(" + str + ")*"
150 }
151 if k&referenceKind != 0 {
152 str = "&" + str
153 }
154 return str
155}
156
157type kindInfo struct {
158 kind
159 subsumes []*kindInfo
160 subsumedBy []*kindInfo
161 unary []token.Token
162 binary []token.Token
163}
164
165var toKindInfo = map[kind]*kindInfo{}
166
Jonathan Amsterdam35f029d2019-02-10 07:17:14 -0500167// matchBinOpKind returns the result kind of applying the given op to operands with
168// the given kinds. The operation is disallowed if the return value is bottomKind. If
169// the second return value is true, the operands should be swapped before evaluation.
170//
171// Evaluating binary expressions uses this to
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100172// - fail incompatible operations early, even if the concrete types are
173// not known,
174// - check the result type of unification,
175//
176// Secondary goals:
177// - keep type compatibility mapped at a central place
178// - reduce the amount op type switching.
179// - simplifies testing
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400180func matchBinOpKind(op op, a, b kind) (k kind, swap bool) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100181 if op == opDisjunction {
182 return a | b, false
183 }
184 u := unifyType(a, b)
185 valBits := u & typeKinds
186 catBits := u &^ typeKinds
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100187 aGround := a&nonGround == 0
188 bGround := b&nonGround == 0
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100189 a = a & typeKinds
190 b = b & typeKinds
191 if valBits == bottomKind {
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400192 k := nullKind
193 switch op {
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200194 case opLss, opLeq, opGtr, opGeq:
195 if a.isAnyOf(numKind) && b.isAnyOf(numKind) {
196 return boolKind, false
197 }
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400198 case opEql, opNeq:
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200199 if a.isAnyOf(numKind) && b.isAnyOf(numKind) {
200 return boolKind, false
201 }
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400202 fallthrough
203 case opUnify:
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100204 if a&nullKind != 0 {
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400205 return k, false
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100206 }
207 if b&nullKind != 0 {
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400208 return k, true
Marcel van Lohuizen855243e2019-02-07 18:00:55 +0100209 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100210 return bottomKind, false
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200211 case opRem, opQuo, opMul, opAdd, opSub:
212 if a.isAnyOf(numKind) && b.isAnyOf(numKind) {
213 return floatKind, false
214 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100215 }
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100216 if op == opMul {
217 if a.isAnyOf(listKind|stringKind|bytesKind) && b.isAnyOf(intKind) {
Jonathan Amsterdam0500c312019-02-16 18:04:09 -0500218 return a | catBits, false
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100219 }
220 if b.isAnyOf(listKind|stringKind|bytesKind) && a.isAnyOf(intKind) {
Jonathan Amsterdam0500c312019-02-16 18:04:09 -0500221 return b | catBits, true
Marcel van Lohuizend401e722019-02-21 22:59:31 +0100222 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100223 }
224 // non-overlapping types
225 if a&scalarKinds == 0 || b&scalarKinds == 0 {
226 return bottomKind, false
227 }
228 // a and b have different numeric types.
229 switch {
230 case b.isAnyOf(durationKind):
231 // a must be a numeric, non-duration type.
232 if op == opMul {
233 return durationKind | catBits, true
234 }
235 case a.isAnyOf(durationKind):
236 if opIn(op, opMul, opQuo, opRem) {
237 return durationKind | catBits, false
238 }
239 case op.isCmp():
240 return boolKind, false
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100241 }
242 return bottomKind, false
243 }
244 switch {
245 case a&nonGround == 0 && b&nonGround == 0:
246 // both ground values: nothing to do
247
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100248 case op != opUnify && op != opLand && op != opLor && op != opNeq:
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100249
250 default:
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400251 swap = aGround && !bGround
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100252 }
253 // a and b have overlapping types.
254 switch op {
255 case opUnify:
256 // Increase likelihood of unification succeeding on first try.
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400257 return u, swap
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100258
259 case opLand, opLor:
260 if u.isAnyOf(boolKind) {
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400261 return boolKind | catBits, swap
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100262 }
Marcel van Lohuizen706e69c2019-02-11 18:21:14 +0100263 case opEql, opNeq, opMat, opNMat:
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100264 if u.isAnyOf(fixedKinds) {
265 return boolKind | catBits, false
266 }
267 case opLss, opLeq, opGeq, opGtr:
268 if u.isAnyOf(fixedKinds) {
269 return boolKind | catBits, false
270 }
271 case opAdd:
Marcel van Lohuizen09d814d2019-02-22 19:14:33 +0100272 if u.isAnyOf(addableKind) {
273 return u&(addableKind) | catBits, false
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100274 }
275 case opSub:
276 if u.isAnyOf(scalarKinds) {
277 return u&scalarKinds | catBits, false
278 }
279 case opRem:
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200280 if u.isAnyOf(numKind) {
Marcel van Lohuizen0a7717d2019-02-13 17:36:32 +0400281 return floatKind | catBits, false
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100282 }
283 case opQuo:
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200284 if u.isAnyOf(numKind) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100285 return floatKind | catBits, false
286 }
287 case opIRem, opIMod:
288 if u.isAnyOf(intKind) {
289 return u&(intKind) | catBits, false
290 }
291 case opIQuo, opIDiv:
292 if u.isAnyOf(intKind) {
293 return intKind | catBits, false
294 }
295 case opMul:
296 if u.isAnyOf(numKind) {
297 return u&numKind | catBits, false
298 }
299 default:
300 panic("unimplemented")
301 }
302 return bottomKind, false
303}