blob: 0a7d79ab0866def0bc52c8474d0585e6fe345477 [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 "regexp"
19 "strconv"
20 "strings"
21 "testing"
22)
23
24func TestSubsume(t *testing.T) {
25 testCases := []struct {
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +010026 // the result of b ⊑ a, where a and b are defined in "in"
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010027 subsumes bool
28 in string
29 mode subsumeMode
30 }{
31 // Top subsumes everything
32 0: {subsumes: true, in: `a: _, b: _ `},
33 1: {subsumes: true, in: `a: _, b: null `},
34 2: {subsumes: true, in: `a: _, b: int `},
35 3: {subsumes: true, in: `a: _, b: 1 `},
36 4: {subsumes: true, in: `a: _, b: float `},
37 5: {subsumes: true, in: `a: _, b: "s" `},
38 6: {subsumes: true, in: `a: _, b: {} `},
39 7: {subsumes: true, in: `a: _, b: []`},
40 8: {subsumes: true, in: `a: _, b: _|_ `},
41
42 // Nothing besides top subsumed top
43 9: {subsumes: false, in: `a: null, b: _`},
44 10: {subsumes: false, in: `a: int, b: _`},
45 11: {subsumes: false, in: `a: 1, b: _`},
46 12: {subsumes: false, in: `a: float, b: _`},
47 13: {subsumes: false, in: `a: "s", b: _`},
48 14: {subsumes: false, in: `a: {}, b: _`},
49 15: {subsumes: false, in: `a: [], b: _`},
50 16: {subsumes: false, in: `a: _|_ , b: _`},
51
52 // Bottom subsumes nothing except bottom itself.
53 17: {subsumes: false, in: `a: _|_, b: null `},
54 18: {subsumes: false, in: `a: _|_, b: int `},
55 19: {subsumes: false, in: `a: _|_, b: 1 `},
56 20: {subsumes: false, in: `a: _|_, b: float `},
57 21: {subsumes: false, in: `a: _|_, b: "s" `},
58 22: {subsumes: false, in: `a: _|_, b: {} `},
59 23: {subsumes: false, in: `a: _|_, b: [] `},
60 24: {subsumes: true, in: ` a: _|_, b: _|_ `},
61
62 // All values subsume bottom
63 25: {subsumes: true, in: `a: null, b: _|_`},
64 26: {subsumes: true, in: `a: int, b: _|_`},
65 27: {subsumes: true, in: `a: 1, b: _|_`},
66 28: {subsumes: true, in: `a: float, b: _|_`},
67 29: {subsumes: true, in: `a: "s", b: _|_`},
68 30: {subsumes: true, in: `a: {}, b: _|_`},
69 31: {subsumes: true, in: `a: [], b: _|_`},
70 32: {subsumes: true, in: `a: true, b: _|_`},
71 33: {subsumes: true, in: `a: _|_, b: _|_`},
72
73 // null subsumes only null
74 34: {subsumes: true, in: ` a: null, b: null `},
75 35: {subsumes: false, in: `a: null, b: 1 `},
76 36: {subsumes: false, in: `a: 1, b: null `},
77
78 37: {subsumes: true, in: ` a: true, b: true `},
79 38: {subsumes: false, in: `a: true, b: false `},
80
81 39: {subsumes: true, in: ` a: "a", b: "a" `},
82 40: {subsumes: false, in: `a: "a", b: "b" `},
83 41: {subsumes: true, in: ` a: string, b: "a" `},
84 42: {subsumes: false, in: `a: "a", b: string `},
85
86 // Number typing (TODO)
87 //
88 // In principle, an "int" cannot assume an untyped "1", as "1" may
89 // still by typed as a float. They are two different type aspects. When
90 // considering, keep in mind that:
91 // Key requirement: if A subsumes B, it must not be possible to
92 // specialize B further such that A does not subsume B. HOWEVER,
93 // The type conversion rules for conversion are INDEPENDENT of the
94 // rules for subsumption!
95 // Consider:
96 // - only having number, but allowing user-defined types.
97 // Subsumption would still work the same, but it may be somewhat
98 // less weird.
99 // - making 1 always an int and 1.0 always a float.
100 // - the int type would subsume any derived type from int.
101 // - arithmetic would allow implicit conversions, but maybe not for
102 // types.
103 //
104 // TODO: irrational numbers: allow untyped, but require explicit
105 // trunking when assigning to float.
106 //
107 // a: number; cue.IsInteger(a) && a > 0
108 // t: (x) -> number; cue.IsInteger(a) && a > 0
109 // type x number: cue.IsInteger(x) && x > 0
110 // x: typeOf(number); cue.IsInteger(x) && x > 0
111 43: {subsumes: true, in: `a: 1, b: 1 `},
112 44: {subsumes: true, in: `a: 1.0, b: 1.0 `},
113 45: {subsumes: true, in: `a: 3.0, b: 3.0 `},
114 46: {subsumes: false, in: `a: 1.0, b: 1 `},
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200115 47: {subsumes: false, in: `a: 1, b: 1.0 `},
116 48: {subsumes: false, in: `a: 3, b: 3.0`},
117 49: {subsumes: true, in: `a: int, b: 1`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100118 50: {subsumes: true, in: `a: int, b: int & 1`},
119 51: {subsumes: true, in: `a: float, b: 1.0`},
120 52: {subsumes: false, in: `a: float, b: 1`},
121 53: {subsumes: false, in: `a: int, b: 1.0`},
122 54: {subsumes: true, in: `a: int, b: int`},
123 55: {subsumes: true, in: `a: number, b: int`},
124
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100125 // Structs
126 64: {subsumes: true, in: `a: {}, b: {}`},
127 65: {subsumes: true, in: `a: {}, b: {a: 1}`},
128 66: {subsumes: true, in: `a: {a:1}, b: {a:1, b:1}`},
129 67: {subsumes: true, in: `a: {s: { a:1} }, b: { s: { a:1, b:2 }}`},
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100130 68: {subsumes: true, in: `a: {}, b: {}`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100131 // TODO: allow subsumption of unevaluated values?
132 // ref not yet evaluated and not structurally equivalent
133 69: {subsumes: true, in: `a: {}, b: {} & c, c: {}`},
134
135 70: {subsumes: false, in: `a: {a:1}, b: {}`},
136 71: {subsumes: false, in: `a: {a:1, b:1}, b: {a:1}`},
137 72: {subsumes: false, in: `a: {s: { a:1} }, b: { s: {}}`},
138
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100139 84: {subsumes: true, in: `a: 1 | 2, b: 2 | 1`},
140 85: {subsumes: true, in: `a: 1 | 2, b: 1 | 2`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100141
142 86: {subsumes: true, in: `a: number, b: 2 | 1`},
143 87: {subsumes: true, in: `a: number, b: 2 | 1`},
144 88: {subsumes: false, in: `a: int, b: 1 | 2 | 3.1`},
145
Marcel van Lohuizene7e8f0d2019-02-06 12:29:58 +0100146 89: {subsumes: true, in: `a: float | number, b: 1 | 2 | 3.1`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100147
148 90: {subsumes: false, in: `a: int, b: 1 | 2 | 3.1`},
149 91: {subsumes: true, in: `a: 1 | 2, b: 1`},
150 92: {subsumes: true, in: `a: 1 | 2, b: 2`},
151 93: {subsumes: false, in: `a: 1 | 2, b: 3`},
152
153 // Structural
154 94: {subsumes: false, in: `a: int + int, b: int`},
155 95: {subsumes: true, in: `a: int + int, b: int + int`},
156 96: {subsumes: true, in: `a: int + number, b: int + int`},
157 97: {subsumes: true, in: `a: number + number, b: int + int`},
158 // TODO: allow subsumption of unevaluated values?
159 // TODO: may be false if we allow arithmetic on incomplete values.
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100160 98: {subsumes: false, in: `a: int + int, b: int * int`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100161
162 99: {subsumes: true, in: `a: !int, b: !int`},
163 100: {subsumes: true, in: `a: !number, b: !int`},
164 // TODO: allow subsumption of unevaluated values?
165 // true because both evaluate to bottom
166 101: {subsumes: true, in: `a: !int, b: !number`},
167 // TODO: allow subsumption of unevaluated values?
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100168 // May be true because both evaluate to bottom. false is always allowed.
169 102: {subsumes: false, in: `a: int + int, b: !number`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100170 // TODO: allow subsumption of unevaluated values?
171 // true because both evaluate to bool
172 103: {subsumes: true, in: `a: !bool, b: bool`},
173
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100174 // Call
175 113: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100176 a: fn(),
177 b: fn()`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100178 },
179 // TODO: allow subsumption of unevaluated values?
180 114: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100181 a: len(),
182 b: len(1)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100183 },
184 115: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100185 a: fn(2)
186 b: fn(2)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100187 },
188 // TODO: allow subsumption of unevaluated values?
189 116: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100190 a: fn(number)
191 b: fn(2)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100192 },
193 // TODO: allow subsumption of unevaluated values?
194 117: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100195 a: fn(2)
196 b: fn(number)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100197 },
198
199 // TODO: allow subsumption of unevaluated values?
200 // TODO: okay, but why false?
201 121: {subsumes: false, in: `a: c + d, b: int, c: int, d: int`},
202 // TODO: allow subsumption of unevaluated values?
203 122: {subsumes: true, in: `a: {}, b: c & {}, c: {}`},
204
205 // references
206 123: {subsumes: true, in: `a: c, b: c, c: {}`},
207 // TODO: allow subsumption of unevaluated values?
208 124: {subsumes: true, in: `a: c, b: d, c: {}, d: {}`},
209 125: {subsumes: false, in: `a: c, b: d, c: {a:1}, d: {}`},
210 // TODO: allow subsumption of unevaluated values?
211 126: {subsumes: true, in: `a: c, b: d, c: {a:1}, d: c & {b:1}`},
212 127: {subsumes: false, in: `a: d, b: c, c: {a:1}, d: c & {b:1}`},
213 128: {subsumes: false, in: `a: c.c, b: c, c: { d: number}`},
214
215 // type unification catches a reference error.
216 129: {subsumes: false, in: `a: c, b: d, c: 1, d: 2`},
217
218 130: {subsumes: true, in: ` a: [1][1], b: [1][1]`},
219 131: {subsumes: true, in: ` a: [1][number], b: [1][1]`},
220 132: {subsumes: true, in: ` a: [number][1], b: [1][1]`},
221 133: {subsumes: true, in: ` a: [number][number], b: [1][1]`},
222 134: {subsumes: false, in: ` a: [1][0], b: [1][number]`},
223 135: {subsumes: false, in: ` a: [1][0], b: [number][0]`},
224 136: {subsumes: true, in: ` a: [number][number], b: [1][number]`},
225 137: {subsumes: true, in: ` a: [number][number], b: [number][1]`},
226 // purely structural:
227 138: {subsumes: false, in: ` a: [number][number], b: number`},
228
229 // interpolations
230 139: {subsumes: true, in: ` a: "\(d)", b: "\(d)", d: _`},
231 // TODO: allow subsumption of unevaluated values?
232 140: {subsumes: true, in: ` a: "\(d)", b: "\(e)", d: _, e: _`},
233
234 141: {subsumes: true, in: ` a: "\(string)", b: "\("foo")"`},
235 // TODO: allow subsumption of unevaluated values?
236 142: {subsumes: true, in: ` a: "\(string)", b: "\(d)", d: "foo"`},
237 143: {subsumes: true, in: ` a: "\("foo")", b: "\("foo")"`},
238 144: {subsumes: false, in: ` a: "\("foo")", b: "\(1) \(2)"`},
239
240 145: {subsumes: false, in: ` a: "s \(d) e", b: "s a e", d: _`},
241 146: {subsumes: false, in: ` a: "s \(d)m\(d) e", b: "s a e", d: _`},
242
Marcel van Lohuizen50eea6b2019-02-19 18:30:15 +0100243 147: {subsumes: true, in: ` a: 7080, b: *7080 | int`, mode: subChoose},
Marcel van Lohuizen1ee36c82019-02-06 13:17:35 +0100244
245 // Defaults
246 150: {subsumes: false, in: `a: number | *1, b: number | *2`},
247 151: {subsumes: true, in: `a: number | *2, b: number | *2`},
248 152: {subsumes: true, in: `a: int | *float, b: int | *2.0`},
Marcel van Lohuizen4a360992019-05-11 18:18:31 +0200249 153: {subsumes: false, in: `a: int | *2, b: int | *2.0`},
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100250 154: {subsumes: true, in: `a: number | *2 | *3, b: number | *2`},
251 155: {subsumes: true, in: `a: number, b: number | *2`},
252
253 // Bounds
254 170: {subsumes: true, in: `a: >=2, b: >=2`},
255 171: {subsumes: true, in: `a: >=1, b: >=2`},
256 172: {subsumes: true, in: `a: >0, b: >=2`},
257 173: {subsumes: true, in: `a: >1, b: >1`},
258 174: {subsumes: true, in: `a: >=1, b: >1`},
259 175: {subsumes: false, in: `a: >1, b: >=1`},
260 176: {subsumes: true, in: `a: >=1, b: >=1`},
261 177: {subsumes: true, in: `a: <1, b: <1`},
262 178: {subsumes: true, in: `a: <=1, b: <1`},
263 179: {subsumes: false, in: `a: <1, b: <=1`},
264 180: {subsumes: true, in: `a: <=1, b: <=1`},
265
266 181: {subsumes: true, in: `a: !=1, b: !=1`},
267 182: {subsumes: false, in: `a: !=1, b: !=2`},
268
269 183: {subsumes: false, in: `a: !=1, b: <=1`},
270 184: {subsumes: true, in: `a: !=1, b: <1`},
271 185: {subsumes: false, in: `a: !=1, b: >=1`},
272 186: {subsumes: true, in: `a: !=1, b: <1`},
273
274 187: {subsumes: true, in: `a: !=1, b: <=0`},
275 188: {subsumes: true, in: `a: !=1, b: >=2`},
276 189: {subsumes: true, in: `a: !=1, b: >1`},
277
278 195: {subsumes: false, in: `a: >=2, b: !=2`},
279 196: {subsumes: false, in: `a: >2, b: !=2`},
280 197: {subsumes: false, in: `a: <2, b: !=2`},
281 198: {subsumes: false, in: `a: <=2, b: !=2`},
282
Marcel van Lohuizen93bffe32019-03-13 16:11:24 +0100283 200: {subsumes: true, in: `a: =~"foo", b: =~"foo"`},
284 201: {subsumes: false, in: `a: =~"foo", b: =~"bar"`},
285 202: {subsumes: false, in: `a: =~"foo1", b: =~"foo"`},
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100286
Marcel van Lohuizen93bffe32019-03-13 16:11:24 +0100287 203: {subsumes: true, in: `a: !~"foo", b: !~"foo"`},
288 204: {subsumes: false, in: `a: !~"foo", b: !~"bar"`},
289 205: {subsumes: false, in: `a: !~"foo", b: !~"foo1"`},
290
291 // The following is could be true, but we will not go down the rabbit
292 // hold of trying to prove subsumption of regular expressions.
293 210: {subsumes: false, in: `a: =~"foo", b: =~"foo1"`},
294 211: {subsumes: false, in: `a: !~"foo1", b: !~"foo"`},
295
296 220: {subsumes: true, in: `a: <5, b: 4`},
297 221: {subsumes: false, in: `a: <5, b: 5`},
298 222: {subsumes: true, in: `a: <=5, b: 5`},
299 223: {subsumes: false, in: `a: <=5.0, b: 5.00000001`},
300 224: {subsumes: true, in: `a: >5, b: 6`},
301 225: {subsumes: false, in: `a: >5, b: 5`},
302 226: {subsumes: true, in: `a: >=5, b: 5`},
303 227: {subsumes: false, in: `a: >=5, b: 4`},
304 228: {subsumes: true, in: `a: !=5, b: 6`},
305 229: {subsumes: false, in: `a: !=5, b: 5`},
306 230: {subsumes: false, in: `a: !=5.0, b: 5.0`},
307 231: {subsumes: false, in: `a: !=5.0, b: 5`},
308
309 250: {subsumes: true, in: `a: =~ #"^\d{3}$"#, b: "123"`},
310 251: {subsumes: false, in: `a: =~ #"^\d{3}$"#, b: "1234"`},
311 252: {subsumes: true, in: `a: !~ #"^\d{3}$"#, b: "1234"`},
312 253: {subsumes: false, in: `a: !~ #"^\d{3}$"#, b: "123"`},
313
314 // Conjunctions
315 300: {subsumes: true, in: `a: >0, b: >=2 & <=100`},
316 301: {subsumes: false, in: `a: >0, b: >=0 & <=100`},
317
318 310: {subsumes: true, in: `a: >=0 & <=100, b: 10`},
319 311: {subsumes: true, in: `a: >=0 & <=100, b: >=0 & <=100`},
320 312: {subsumes: false, in: `a: !=2 & !=4, b: >3`},
321 313: {subsumes: true, in: `a: !=2 & !=4, b: >5`},
Marcel van Lohuizen7d0797b2019-02-07 18:35:28 +0100322
323 // Disjunctions
Marcel van Lohuizen93bffe32019-03-13 16:11:24 +0100324 330: {subsumes: true, in: `a: >5, b: >10 | 8`},
325 331: {subsumes: false, in: `a: >8, b: >10 | 8`},
Marcel van Lohuizen08a0ef22019-03-28 09:12:19 +0100326
327 // Optional fields
328 // Optional fields defined constraints on fields that are not yet
329 // defined. So even if such a field is not part of the output, it
330 // influences the lattice structure.
331 // For a given A and B, where A and B unify and where A has an optional
332 // field that is not defined in B, the addition of an incompatible
333 // value of that field in B can cause A and B to no longer unify.
334 //
335 400: {subsumes: false, in: `a: {foo: 1}, b: {}`},
336 401: {subsumes: false, in: `a: {foo?: 1}, b: {}`},
337 402: {subsumes: true, in: `a: {}, b: {foo: 1}`},
338 403: {subsumes: true, in: `a: {}, b: {foo?: 1}`},
339
340 404: {subsumes: true, in: `a: {foo: 1}, b: {foo: 1}`},
341 405: {subsumes: true, in: `a: {foo?: 1}, b: {foo: 1}`},
342 406: {subsumes: true, in: `a: {foo?: 1}, b: {foo?: 1}`},
343 407: {subsumes: false, in: `a: {foo: 1}, b: {foo?: 1}`},
344
345 408: {subsumes: false, in: `a: {foo: 1}, b: {foo: 2}`},
346 409: {subsumes: false, in: `a: {foo?: 1}, b: {foo: 2}`},
347 410: {subsumes: false, in: `a: {foo?: 1}, b: {foo?: 2}`},
348 411: {subsumes: false, in: `a: {foo: 1}, b: {foo?: 2}`},
349
350 412: {subsumes: true, in: `a: {foo: number}, b: {foo: 2}`},
351 413: {subsumes: true, in: `a: {foo?: number}, b: {foo: 2}`},
352 414: {subsumes: true, in: `a: {foo?: number}, b: {foo?: 2}`},
353 415: {subsumes: false, in: `a: {foo: number}, b: {foo?: 2}`},
354
355 416: {subsumes: false, in: `a: {foo: 1}, b: {foo: number}`},
356 417: {subsumes: false, in: `a: {foo?: 1}, b: {foo: number}`},
357 418: {subsumes: false, in: `a: {foo?: 1}, b: {foo?: number}`},
358 419: {subsumes: false, in: `a: {foo: 1}, b: {foo?: number}`},
359
360 // The one exception of the rule: there is no value of foo that can be
361 // added to b which would cause the unification of a and b to fail.
362 420: {subsumes: true, in: `a: {foo?: _}, b: {}`},
Marcel van Lohuizenb134a502019-05-06 11:33:05 +0200363
364 // Lists
365 506: {subsumes: true, in: `a: [], b: [] `},
366 507: {subsumes: true, in: `a: [1], b: [1] `},
367 508: {subsumes: false, in: `a: [1], b: [2] `},
368 509: {subsumes: false, in: `a: [1], b: [2, 3] `},
369 510: {subsumes: true, in: `a: [{b: string}], b: [{b: "foo"}] `},
370 511: {subsumes: true, in: `a: [...{b: string}], b: [{b: "foo"}] `},
371 512: {subsumes: false, in: `a: [{b: "foo"}], b: [{b: string}] `},
372 513: {subsumes: false, in: `a: [{b: string}], b: [{b: "foo"}, ...{b: "foo"}] `},
373 520: {subsumes: false, in: `a: [_, int, ...], b: [int, string, ...string] `},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100374 }
375
376 re := regexp.MustCompile(`a: (.*).*b: ([^\n]*)`)
377 for i, tc := range testCases {
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100378 if tc.in == "" {
379 continue
380 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100381 m := re.FindStringSubmatch(strings.Join(strings.Split(tc.in, "\n"), ""))
382 const cutset = "\n ,"
383 key := strings.Trim(m[1], cutset) + " ⊑ " + strings.Trim(m[2], cutset)
384
385 t.Run(strconv.Itoa(i)+"/"+key, func(t *testing.T) {
386 ctx, root := compileFile(t, tc.in)
387
388 // Use low-level lookup to avoid evaluation.
389 var a, b value
390 for _, arc := range root.arcs {
391 switch arc.feature {
392 case ctx.strLabel("a"):
393 a = arc.v
394 case ctx.strLabel("b"):
395 b = arc.v
396 }
397 }
398 if got := subsumes(ctx, a, b, tc.mode); got != tc.subsumes {
399 t.Errorf("got %v; want %v (%v vs %v)", got, tc.subsumes, a.kind(), b.kind())
400 }
401 })
402 }
403}
404
405func TestTouchBottom(t *testing.T) {
406 // Just call this function to mark coverage. It is otherwise never called.
407 var x bottom
408 x.subsumesImpl(nil, &bottom{}, 0)
409}