blob: b0d93826be80cbf1e44d5fb152313689c60642f1 [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 {
26 // the result of a ⊑ b, where a and b are defined in "in"
27 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 `},
115 47: {subsumes: true, in: `a: 1, b: 1.0 `},
116 48: {subsumes: true, in: `a: 3, b: 3.0`},
117 49: {subsumes: false, in: `a: int, b: 1`},
118 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
125 // Lists
126 56: {subsumes: true, in: `a: [], b: [] `},
127 57: {subsumes: true, in: `a: [1], b: [1] `},
128 58: {subsumes: false, in: `a: [1], b: [2] `},
129 59: {subsumes: false, in: `a: [1], b: [2, 3] `},
130 60: {subsumes: true, in: `a: [{b: string}], b: [{b: "foo"}] `},
131 61: {subsumes: true, in: `a: [...{b: string}], b: [{b: "foo"}] `},
132 62: {subsumes: false, in: `a: [{b: "foo"}], b: [{b: string}] `},
133 63: {subsumes: false, in: `a: [{b: string}], b: [{b: "foo"}, ...{b: "foo"}] `},
134
135 // Structs
136 64: {subsumes: true, in: `a: {}, b: {}`},
137 65: {subsumes: true, in: `a: {}, b: {a: 1}`},
138 66: {subsumes: true, in: `a: {a:1}, b: {a:1, b:1}`},
139 67: {subsumes: true, in: `a: {s: { a:1} }, b: { s: { a:1, b:2 }}`},
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100140 68: {subsumes: true, in: `a: {}, b: {}`},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100141 // TODO: allow subsumption of unevaluated values?
142 // ref not yet evaluated and not structurally equivalent
143 69: {subsumes: true, in: `a: {}, b: {} & c, c: {}`},
144
145 70: {subsumes: false, in: `a: {a:1}, b: {}`},
146 71: {subsumes: false, in: `a: {a:1, b:1}, b: {a:1}`},
147 72: {subsumes: false, in: `a: {s: { a:1} }, b: { s: {}}`},
148
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100149 // Disjunction TODO: for now these two are false: unifying may result in
150 // an ambiguity that we are currently not handling, so safer to not
151 // unify.
152 84: {subsumes: false, in: `a: 1 | 2, b: 2 | 1`},
153 85: {subsumes: false, in: `a: 1 | 2, b: 1 | 2`},
154
155 86: {subsumes: true, in: `a: number, b: 2 | 1`},
156 87: {subsumes: true, in: `a: number, b: 2 | 1`},
157 88: {subsumes: false, in: `a: int, b: 1 | 2 | 3.1`},
158
159 // Disjunction TODO: for now these two are false: unifying may result in
160 // an ambiguity that we are currently not handling, so safer to not
161 // unify.
162 89: {subsumes: false, in: `a: float | number, b: 1 | 2 | 3.1`},
163
164 90: {subsumes: false, in: `a: int, b: 1 | 2 | 3.1`},
165 91: {subsumes: true, in: `a: 1 | 2, b: 1`},
166 92: {subsumes: true, in: `a: 1 | 2, b: 2`},
167 93: {subsumes: false, in: `a: 1 | 2, b: 3`},
168
169 // Structural
170 94: {subsumes: false, in: `a: int + int, b: int`},
171 95: {subsumes: true, in: `a: int + int, b: int + int`},
172 96: {subsumes: true, in: `a: int + number, b: int + int`},
173 97: {subsumes: true, in: `a: number + number, b: int + int`},
174 // TODO: allow subsumption of unevaluated values?
175 // TODO: may be false if we allow arithmetic on incomplete values.
176 98: {subsumes: true, in: `a: int + int, b: int * int`},
177
178 99: {subsumes: true, in: `a: !int, b: !int`},
179 100: {subsumes: true, in: `a: !number, b: !int`},
180 // TODO: allow subsumption of unevaluated values?
181 // true because both evaluate to bottom
182 101: {subsumes: true, in: `a: !int, b: !number`},
183 // TODO: allow subsumption of unevaluated values?
184 // true because both evaluate to bottom
185 102: {subsumes: true, in: `a: int + int, b: !number`},
186 // TODO: allow subsumption of unevaluated values?
187 // true because both evaluate to bool
188 103: {subsumes: true, in: `a: !bool, b: bool`},
189
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100190 // Call
191 113: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100192 a: fn(),
193 b: fn()`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100194 },
195 // TODO: allow subsumption of unevaluated values?
196 114: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100197 a: len(),
198 b: len(1)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100199 },
200 115: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100201 a: fn(2)
202 b: fn(2)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100203 },
204 // TODO: allow subsumption of unevaluated values?
205 116: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100206 a: fn(number)
207 b: fn(2)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100208 },
209 // TODO: allow subsumption of unevaluated values?
210 117: {subsumes: true, in: `
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100211 a: fn(2)
212 b: fn(number)`,
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100213 },
214
215 // TODO: allow subsumption of unevaluated values?
216 // TODO: okay, but why false?
217 121: {subsumes: false, in: `a: c + d, b: int, c: int, d: int`},
218 // TODO: allow subsumption of unevaluated values?
219 122: {subsumes: true, in: `a: {}, b: c & {}, c: {}`},
220
221 // references
222 123: {subsumes: true, in: `a: c, b: c, c: {}`},
223 // TODO: allow subsumption of unevaluated values?
224 124: {subsumes: true, in: `a: c, b: d, c: {}, d: {}`},
225 125: {subsumes: false, in: `a: c, b: d, c: {a:1}, d: {}`},
226 // TODO: allow subsumption of unevaluated values?
227 126: {subsumes: true, in: `a: c, b: d, c: {a:1}, d: c & {b:1}`},
228 127: {subsumes: false, in: `a: d, b: c, c: {a:1}, d: c & {b:1}`},
229 128: {subsumes: false, in: `a: c.c, b: c, c: { d: number}`},
230
231 // type unification catches a reference error.
232 129: {subsumes: false, in: `a: c, b: d, c: 1, d: 2`},
233
234 130: {subsumes: true, in: ` a: [1][1], b: [1][1]`},
235 131: {subsumes: true, in: ` a: [1][number], b: [1][1]`},
236 132: {subsumes: true, in: ` a: [number][1], b: [1][1]`},
237 133: {subsumes: true, in: ` a: [number][number], b: [1][1]`},
238 134: {subsumes: false, in: ` a: [1][0], b: [1][number]`},
239 135: {subsumes: false, in: ` a: [1][0], b: [number][0]`},
240 136: {subsumes: true, in: ` a: [number][number], b: [1][number]`},
241 137: {subsumes: true, in: ` a: [number][number], b: [number][1]`},
242 // purely structural:
243 138: {subsumes: false, in: ` a: [number][number], b: number`},
244
245 // interpolations
246 139: {subsumes: true, in: ` a: "\(d)", b: "\(d)", d: _`},
247 // TODO: allow subsumption of unevaluated values?
248 140: {subsumes: true, in: ` a: "\(d)", b: "\(e)", d: _, e: _`},
249
250 141: {subsumes: true, in: ` a: "\(string)", b: "\("foo")"`},
251 // TODO: allow subsumption of unevaluated values?
252 142: {subsumes: true, in: ` a: "\(string)", b: "\(d)", d: "foo"`},
253 143: {subsumes: true, in: ` a: "\("foo")", b: "\("foo")"`},
254 144: {subsumes: false, in: ` a: "\("foo")", b: "\(1) \(2)"`},
255
256 145: {subsumes: false, in: ` a: "s \(d) e", b: "s a e", d: _`},
257 146: {subsumes: false, in: ` a: "s \(d)m\(d) e", b: "s a e", d: _`},
258
259 147: {subsumes: true, in: ` a: 7080, b: 7080 | int`, mode: subChoose},
260 }
261
262 re := regexp.MustCompile(`a: (.*).*b: ([^\n]*)`)
263 for i, tc := range testCases {
Marcel van Lohuizen2bf066f2018-12-16 11:43:49 +0100264 if tc.in == "" {
265 continue
266 }
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100267 m := re.FindStringSubmatch(strings.Join(strings.Split(tc.in, "\n"), ""))
268 const cutset = "\n ,"
269 key := strings.Trim(m[1], cutset) + " ⊑ " + strings.Trim(m[2], cutset)
270
271 t.Run(strconv.Itoa(i)+"/"+key, func(t *testing.T) {
272 ctx, root := compileFile(t, tc.in)
273
274 // Use low-level lookup to avoid evaluation.
275 var a, b value
276 for _, arc := range root.arcs {
277 switch arc.feature {
278 case ctx.strLabel("a"):
279 a = arc.v
280 case ctx.strLabel("b"):
281 b = arc.v
282 }
283 }
284 if got := subsumes(ctx, a, b, tc.mode); got != tc.subsumes {
285 t.Errorf("got %v; want %v (%v vs %v)", got, tc.subsumes, a.kind(), b.kind())
286 }
287 })
288 }
289}
290
291func TestTouchBottom(t *testing.T) {
292 // Just call this function to mark coverage. It is otherwise never called.
293 var x bottom
294 x.subsumesImpl(nil, &bottom{}, 0)
295}