blob: 860d6306e14bb5cccc36c9c5c99c314c26a2a0d9 [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)
20
21type valueSubsumer interface {
22 subsumesImpl(ctx *context, v value) bool
23}
24
25type subsumeMode int
26
27const (
28 // subChoose ensures values are elected before doing a subsumption. This
29 // feature is on the conservative side and may result in false negatives.
30 subChoose subsumeMode = 1 << iota
31)
32
33// subsumes checks gt subsumes lt. If any of the values contains references or
34// unevaluated expressions, structural subsumption is performed. This means
35// subsumption is conservative; it may return false when a guarantee for
36// subsumption could be proven. For concreted values it returns the exact
37// relation. It never returns a false positive.
38func subsumes(ctx *context, gt, lt value, mode subsumeMode) bool {
39 var v, w value
40 if mode&subChoose == 0 {
41 v = gt.evalPartial(ctx)
42 w = lt.evalPartial(ctx)
43 } else {
44 v = ctx.manifest(gt)
45 w = ctx.manifest(lt)
46 }
47 if !isIncomplete(v) && !isIncomplete(w) {
48 gt = v
49 lt = w
50 }
51 a := gt.kind()
52 b := lt.kind()
53 switch {
54 case b == bottomKind:
55 return true
56 case b&^(a&b) != 0:
57 // a does not have strictly more bits. This implies any ground kind
58 // subsuming a non-ground type.
59 return false
60 // TODO: consider not supporting references.
61 // case (a|b)&(referenceKind) != 0:
62 // // no resolution if references are in play.
63 // return false, false
64 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +010065 switch lt := lt.(type) {
66 case *unification:
67 if _, ok := gt.(*unification); !ok {
68 for _, x := range lt.values {
69 if subsumes(ctx, gt, x, mode) {
70 return true
71 }
72 }
73 return false
74 }
75
76 case *disjunction:
77 if _, ok := gt.(*disjunction); !ok {
78 for _, x := range lt.values {
79 if !subsumes(ctx, gt, x.val, mode) {
80 return false
81 }
82 }
83 return true
84 }
85 }
86
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010087 return gt.subsumesImpl(ctx, lt, mode)
88}
89
90func (x *structLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
91 if o, ok := v.(*structLit); ok {
Marcel van Lohuizen66db9202018-12-17 19:02:08 +010092 // TODO: consider what to do with templates. Perhaps we should always
93 // do subsumption on fully evaluated structs.
94 if len(x.comprehensions) > 0 { //|| x.template != nil {
95 return false
96 }
97
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010098 // all arcs in n must exist in v and its values must subsume.
99 for _, a := range x.arcs {
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100100 b := o.lookup(ctx, a.feature)
101 if !a.optional && b.optional {
102 return false
103 } else if b.val() == nil {
104 // If field a is optional and has value top, neither the
105 // omission of the field nor the field defined with any value
106 // may cause unification to fail.
107 return a.optional && isTop(a.v)
108 } else if !subsumes(ctx, a.v, b.val(), mode) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100109 return false
110 }
111 }
112 }
113 return !isBottom(v)
114}
115
116func (*top) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
117 return true
118}
119
120func (x *bottom) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
121 // never called.
122 return v.kind() == bottomKind
123}
124
125func (x *basicType) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
126 return true
127}
128
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100129func (x *bound) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
130 if isBottom(v) {
131 return true
132 }
133 kx := x.value.kind()
134 if !kx.isDone() || !kx.isGround() {
135 return false
136 }
137
138 switch y := v.(type) {
139 case *bound:
140 if ky := y.value.kind(); ky.isDone() && ky.isGround() {
141 if (kx&ky)&^kx != 0 {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100142 return false
143 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100144 // x subsumes y if
145 // x: >= a, y: >= b ==> a <= b
146 // x: >= a, y: > b ==> a <= b
147 // x: > a, y: > b ==> a <= b
148 // x: > a, y: >= b ==> a < b
149 //
150 // x: <= a, y: <= b ==> a >= b
151 //
152 // x: != a, y: != b ==> a != b
153 //
154 // false if types or op direction doesn't match
155
156 xv := x.value.(evaluated)
157 yv := y.value.(evaluated)
158 switch x.op {
159 case opGtr:
160 if y.op == opGeq {
161 return test(ctx, x, opLss, xv, yv)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100162 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100163 fallthrough
164 case opGeq:
165 if y.op == opGtr || y.op == opGeq {
166 return test(ctx, x, opLeq, xv, yv)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100167 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100168 case opLss:
169 if y.op == opLeq {
170 return test(ctx, x, opGtr, xv, yv)
171 }
172 fallthrough
173 case opLeq:
174 if y.op == opLss || y.op == opLeq {
175 return test(ctx, x, opGeq, xv, yv)
176 }
177 case opNeq:
178 switch y.op {
179 case opNeq:
180 return test(ctx, x, opEql, xv, yv)
181 case opGeq:
182 return test(ctx, x, opLss, xv, yv)
183 case opGtr:
184 return test(ctx, x, opLeq, xv, yv)
185 case opLss:
186 return test(ctx, x, opGeq, xv, yv)
187 case opLeq:
188 return test(ctx, x, opGtr, xv, yv)
189 }
190
Marcel van Lohuizen93bffe32019-03-13 16:11:24 +0100191 case opMat, opNMat:
192 // these are just approximations
193 if y.op == x.op {
194 return test(ctx, x, opEql, xv, yv)
195 }
196
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100197 default:
198 // opNeq already handled above.
199 panic("cue: undefined bound mode")
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100200 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100201 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100202 // structural equivalence
203 return false
204
205 case *numLit, *stringLit, *durationLit, *boolLit:
206 return test(ctx, x, x.op, y.(evaluated), x.value.(evaluated))
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100207 }
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100208 return false
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100209}
210
211func (x *nullLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
212 return true
213}
214
215func (x *boolLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
216 return x.b == v.(*boolLit).b
217}
218
219func (x *stringLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
220 return x.str == v.(*stringLit).str
221}
222
223func (x *bytesLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
224 return bytes.Equal(x.b, v.(*bytesLit).b)
225}
226
227func (x *numLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
228 b := v.(*numLit)
229 return x.v.Cmp(&b.v) == 0
230}
231
232func (x *durationLit) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
233 return x.d == v.(*durationLit).d
234}
235
236func (x *list) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
237 switch y := v.(type) {
238 case *list:
239 if !subsumes(ctx, x.len, y.len, mode) {
240 return false
241 }
Marcel van Lohuizenb134a502019-05-06 11:33:05 +0200242 // TODO: need to handle case where len(x.elem) > len(y.elem) explicitly
243 // if we introduce cap().
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200244 if !subsumes(ctx, x.elem, y.elem, mode) {
245 return false
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100246 }
Marcel van Lohuizenb134a502019-05-06 11:33:05 +0200247 // TODO: assuming continuous indices, use merge sort if we allow
248 // sparse arrays.
249 for _, a := range y.elem.arcs[len(x.elem.arcs):] {
Marcel van Lohuizen9ee652d2019-04-25 17:16:01 +0200250 if !subsumes(ctx, x.typ, a.v, mode) {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100251 return false
252 }
253 }
Marcel van Lohuizenb134a502019-05-06 11:33:05 +0200254 if y.isOpen() { // implies from first check that x.IsOpen.
255 return subsumes(ctx, x.typ, y.typ, 0)
256 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100257 return true
258 }
259 return isBottom(v)
260}
261
262func (x *params) subsumes(ctx *context, y *params, mode subsumeMode) bool {
263 // structural equivalence
264 // TODO: make agnostic to argument names.
265 if len(y.arcs) != len(x.arcs) {
266 return false
267 }
268 for i, a := range x.arcs {
269 if !subsumes(ctx, a.v, y.arcs[i].v, 0) {
270 return false
271 }
272 }
273 return true
274}
275
276func (x *lambdaExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
277 // structural equivalence
278 if y, ok := v.(*lambdaExpr); ok {
279 return x.params.subsumes(ctx, y.params, 0) &&
280 subsumes(ctx, x.value, y.value, 0)
281 }
282 return isBottom(v)
283}
284
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100285func (x *unification) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
286 if y, ok := v.(*unification); ok {
287 // A unification subsumes another unification if for all values a in x
288 // there is a value b in y such that a subsumes b.
289 //
290 // This assumes overlapping ranges in disjunctions are merged.If this is
291 // not the case, subsumes will return a false negative, which is
292 // allowed.
293 outer:
294 for _, vx := range x.values {
295 for _, vy := range y.values {
296 if subsumes(ctx, vx, vy, mode) {
297 continue outer
298 }
299 }
300 return false
301 }
302 return true
303 }
304 subsumed := true
305 for _, vx := range x.values {
306 subsumed = subsumed && subsumes(ctx, vx, v, mode)
307 }
308 return subsumed
309}
310
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100311// subsumes for disjunction is logically precise. However, just like with
312// structural subsumption, it should not have to be called after evaluation.
313func (x *disjunction) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100314 // A disjunction subsumes another disjunction if all values of v are
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100315 // subsumed by any of the values of x, and default values in v are subsumed
316 // by the default values of x.
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100317 //
318 // This assumes that overlapping ranges in x are merged. If this is not the
319 // case, subsumes will return a false negative, which is allowed.
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100320 if d, ok := v.(*disjunction); ok {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100321 // at least one value in x should subsume each value in d.
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100322 outer:
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100323 for _, vd := range d.values {
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100324 // v is subsumed if any value in x subsumes v.
325 for _, vx := range x.values {
326 if (vx.marked || !vd.marked) && subsumes(ctx, vx.val, vd.val, 0) {
327 continue outer
328 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100329 }
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100330 return false
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100331 }
332 return true
333 }
334 // v is subsumed if any value in x subsumes v.
335 for _, vx := range x.values {
336 if subsumes(ctx, vx.val, v, 0) {
337 return true
338 }
339 }
340 return false
341}
342
343// Structural subsumption operations. Should never have to be called after
344// evaluation.
345
346// structural equivalence
347func (x *nodeRef) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
348 if r, ok := v.(*nodeRef); ok {
349 return x.node == r.node
350 }
351 return isBottom(v)
352}
353
354// structural equivalence
355func (x *selectorExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
356 if r, ok := v.(*selectorExpr); ok {
357 return x.feature == r.feature && subsumes(ctx, x.x, r.x, subChoose)
358 }
359 return isBottom(v)
360}
361
362func (x *interpolation) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
363 switch v := v.(type) {
364 case *stringLit:
365 // Be conservative if not ground.
366 return false
367
368 case *interpolation:
369 // structural equivalence
370 if len(x.parts) != len(v.parts) {
371 return false
372 }
373 for i, p := range x.parts {
374 if !subsumes(ctx, p, v.parts[i], 0) {
375 return false
376 }
377 }
378 return true
379 }
380 return false
381}
382
383// structural equivalence
384func (x *indexExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
385 // TODO: what does it mean to subsume if the index value is not known?
386 if r, ok := v.(*indexExpr); ok {
387 // TODO: could be narrowed down if we know the exact value of the index
388 // and referenced value.
389 return subsumes(ctx, x.x, r.x, mode) && subsumes(ctx, x.index, r.index, 0)
390 }
391 return isBottom(v)
392}
393
394// structural equivalence
395func (x *sliceExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
396 // TODO: what does it mean to subsume if the index value is not known?
397 if r, ok := v.(*sliceExpr); ok {
398 // TODO: could be narrowed down if we know the exact value of the index
399 // and referenced value.
400 return subsumes(ctx, x.x, r.x, 0) &&
401 subsumes(ctx, x.lo, r.lo, 0) &&
402 subsumes(ctx, x.hi, r.hi, 0)
403 }
404 return isBottom(v)
405}
406
407// structural equivalence
408func (x *callExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
409 if c, ok := v.(*callExpr); ok {
410 if len(x.args) != len(c.args) {
411 return false
412 }
413 for i, a := range x.args {
414 if !subsumes(ctx, a, c.args[i], 0) {
415 return false
416 }
417 }
418 return subsumes(ctx, x.x, c.x, 0)
419 }
420 return isBottom(v)
421}
422
423// structural equivalence
424func (x *unaryExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
425 if b, ok := v.(*unaryExpr); ok {
426 return x.op == b.op && subsumes(ctx, x.x, b.x, 0)
427 }
428 return isBottom(v)
429}
430
431// structural equivalence
432func (x *binaryExpr) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
433 if b, ok := v.(*binaryExpr); ok {
434 return x.op == b.op &&
435 subsumes(ctx, x.left, b.left, 0) &&
436 subsumes(ctx, x.right, b.right, 0)
437 }
438 return isBottom(v)
439}
440
441// structural equivalence
442func (x *listComprehension) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
443 if b, ok := v.(*listComprehension); ok {
444 return subsumes(ctx, x.clauses, b.clauses, 0)
445 }
446 return isBottom(v)
447}
448
449// structural equivalence
Marcel van Lohuizen66db9202018-12-17 19:02:08 +0100450func (x *fieldComprehension) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
451 if b, ok := v.(*fieldComprehension); ok {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100452 return subsumes(ctx, x.clauses, b.clauses, 0)
453 }
454 return isBottom(v)
455}
456
457// structural equivalence
458func (x *yield) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
459 if b, ok := v.(*yield); ok {
460 return subsumes(ctx, x.key, b.key, 0) &&
461 subsumes(ctx, x.value, b.value, 0)
462 }
463 return isBottom(v)
464}
465
466// structural equivalence
467func (x *feed) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
468 if b, ok := v.(*feed); ok {
469 return subsumes(ctx, x.source, b.source, 0) &&
470 subsumes(ctx, x.fn, b.fn, 0)
471 }
472 return isBottom(v)
473}
474
475// structural equivalence
476func (x *guard) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
477 if b, ok := v.(*guard); ok {
478 return subsumes(ctx, x.condition, b.condition, 0) &&
479 subsumes(ctx, x.value, b.value, 0)
480 }
481 return isBottom(v)
482}