-
Notifications
You must be signed in to change notification settings - Fork 5
/
matchcontinue.jl
463 lines (438 loc) · 15.1 KB
/
matchcontinue.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
"""
Copyright 2019-CurrentYear: Open Source Modelica Consortium (OSMC)
Copyright 2018: RelationalAI, Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may
not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
The code is based on https://github.com/RelationalAI-oss/Rematch.jl with
changes to allow keyword argument matching on structs along with
matching on the immutable list construct accompanying MetaModelica + some other improvements and bug fixes.
It also provides @matchcontinue macro (try the next case when any exception is thrown).
"""
include("fixLines.jl")
macro splice(iterator, body)
@assert iterator.head === :call
@assert iterator.args[1] === :in
Expr(:..., :(($(esc(body)) for $(esc(iterator.args[2])) in $(esc(iterator.args[3])))))
end
struct MatchFailure <: MetaModelicaException
msg::Any
value::Any
end
"""
Statically get the fieldcount of a type. Useful to avoid runtime calls to
fieldcount.
"""
@generated function evaluated_fieldcount(t::Type{T}) where {T}
res = T !== NONE ? fieldcount(T) : 0
end
"""
Statically get the fieldnames of a type. Useful to avoid runtime calls to
fieldnames (which includes many allocations).
"""
@generated function evaluated_fieldnames(t::Type{T}) where {T}
fieldnames(T)
end
"""
Handles the deconstruction of fields
"""
function handle_destruct_fields(value::Symbol, pattern, subpatterns, len, get::Symbol,
bound::Set{Symbol}, asserts::Vector{Expr}; allow_splat=true)
# NOTE we assume `len` is cheap
fields = []
seen_splat = false
for (i, subpattern) in enumerate(subpatterns)
if (subpattern isa Expr) && (subpattern.head === :(...))
@assert allow_splat && !seen_splat "Too many ... in pattern $pattern"
@assert length(subpattern.args) == 1
seen_splat = true
push!(fields, (:($i:($len-$(length(subpatterns) - i))), subpattern.args[1]))
elseif seen_splat
push!(fields, (:($len - $(length(subpatterns) - i)), subpattern))
elseif (subpattern isa Expr) && (subpattern.head === :kw)
T_sym = Meta.quot(subpattern.args[1])
push!(fields, (:($T_sym), subpattern.args[2]))
else
push!(fields, (i, subpattern))
end
end
Expr(:&&, if seen_splat
:($len >= $(length(subpatterns) - 1))
else
:($len == $(length(subpatterns)))
end, @splice (i, (field, subpattern)) in enumerate(fields) quote
$(Symbol("$(value)_$i")) = $get($value, $field)
$(handle_destruct(Symbol("$(value)_$i"), subpattern, bound, asserts))
end)
end
"""
Top level utility function.
Handles deconstruction of patterns together with the value symbol.
"""
function handle_destruct(value::Symbol, pattern, bound::Set{Symbol}, asserts::Vector{Expr})
if pattern === :(_)
# wildcard
true
elseif !(pattern isa Expr || pattern isa Symbol) ||
pattern === :nothing ||
@capture(pattern, _quote_macrocall) ||
@capture(pattern, Symbol(_))
# constant
# TODO do we have to be careful about QuoteNode etc?
#Probably not //John
quote
$value === $pattern
end
elseif @capture(pattern, subpattern_Symbol)
# variable
# if the pattern doesn't match, we don't want to set the variable
# so for now just set a temp variable
our_sym = Symbol("variable_", pattern)
if pattern in bound
# already bound, check that this value matches
quote
$our_sym == $value
end
else
# bind
push!(bound, pattern)
quote
$our_sym = $value
true
end
end
elseif @capture(pattern, subpattern1_ || subpattern2_) ||
(@capture(pattern, f_(subpattern1_, subpattern2_)) && f === :|)
# disjunction
# need to only bind variables which exist in both branches
bound1 = copy(bound)
bound2 = copy(bound)
body1 = handle_destruct(value, subpattern1, bound1, asserts)
body2 = handle_destruct(value, subpattern2, bound2, asserts)
union!(bound, intersect(bound1, bound2))
quote
$body1 || $body2
end
elseif @capture(pattern, subpattern1_ && subpattern2_) ||
(@capture(pattern, f_(subpattern1_, subpattern2_)) && f === :&)
# conjunction
body1 = handle_destruct(value, subpattern1, bound, asserts)
body2 = handle_destruct(value, subpattern2, bound, asserts)
quote
$body1 && $body2
end
elseif @capture(pattern, _where)
# guard
@assert length(pattern.args) == 2
subpattern = pattern.args[1]
guard = pattern.args[2]
quote
$(handle_destruct(value, subpattern, bound, asserts)) && let $(bound...)
# bind variables locally so they can be used in the guard
$(@splice variable in bound quote
$(esc(variable)) = $(Symbol("variable_", variable))
end)
$(esc(guard))
end
end
elseif @capture(pattern, T_(subpatterns__)) #= All wild =#
if length(subpatterns) == 1 && subpatterns[1] === :(__)
#=
Fields not interesting when matching against a wildcard.
NONE() matched against a wildcard is also true
=#
quote
$value isa $(esc(T))
end
else
T = handleSugar(T)
len = length(subpatterns)
named_fields = [pat.args[1]
for pat in subpatterns if (pat isa Expr) && pat.head === :(kw)]
nNamed = length(named_fields)
@assert length(named_fields) == length(unique(named_fields)) "Pattern $pattern has duplicate named arguments: $(named_fields)"
@assert nNamed == 0 || len == nNamed "Pattern $pattern mixes named and positional arguments"
# struct
if false
elseif nNamed == 0
push!(asserts,
quote
a = typeof($(esc(T)))
#= NONE is a function. However, we treat it a bit special=#
if $(esc(T)) !== NONE && typeof($(esc(T))) <: Function
func = $(esc(T))
throw(LoadError("Attempted to match on a function", @__LINE__,
AssertionError("Incorrect match usage attempted to match on: $func")))
end
if !(isstructtype(typeof($(esc(T)))) || issabstracttype(typeof($(esc(T)))))
throw(LoadError("Attempted to match on a pattern that is not a struct",
@__LINE__,
AssertionError("Incorrect match usage. Attempted to match on a pattern that is not a struct")))
end
pattern = $(esc(T))
if $(esc(T)) !== NONE
if evaluated_fieldcount($(esc(T))) < $(esc(len))
error("Field count for pattern of type: $pattern is $($(esc(len))) expected $(evaluated_fieldcount($(esc(T))))")
end
end
end)
else # Uses keyword arguments
struct_name = gensym("$(T)_match")
type_name = string(T)
assertcond = true
for field in named_fields
local tmp
tmp = quote
$(Meta.quot(field)) in $struct_name
end
assertcond = Expr(:&&, tmp, assertcond)
end
push!(asserts, quote
if !(let
$struct_name = evaluated_fieldnames($(esc(T)))
$assertcond
end)
error("Pattern contains named argument not in the type at: ")
end
end)
end
quote
$value === nothing && $(esc(T)) === Nothing ||
$value isa $(esc(T)) &&
$(handle_destruct_fields(value, pattern, subpatterns, length(subpatterns),
:getfield, bound, asserts; allow_splat=false))
end
end
elseif @capture(pattern, (subpatterns__,)) # Tuple
quote
($value isa Tuple) &&
$(handle_destruct_fields(value, pattern, subpatterns, :(length($value)), :getindex,
bound, asserts; allow_splat=true))
end
elseif @capture(pattern, [subpatterns__]) # Array
quote
($value isa AbstractArray) &&
$(handle_destruct_fields(value, pattern, subpatterns, :(length($value)), :getindex,
bound, asserts; allow_splat=true))
end
elseif @capture(pattern, subpattern_::T_) #ImmutableList
quote
# typeassert
($value isa $(esc(T))) && $(handle_destruct(value, subpattern, bound, asserts))
end
elseif @capture(pattern, _.__) #Sub member of a variable
quote
$value == $(esc(pattern))
end
else
println(pattern)
error("Unrecognized pattern syntax: $pattern")
end
end
"""
Handle syntactic sugar for MetaModelica mode.
Mostly lists but also for the optional type.
Parenthesis for these expressions are skipped
"""
function handleSugar(T)
T = if T === :(<|)
# Syntactic sugar cons.
:Cons
elseif T === :_cons
#= This is legacy for the code generator. For match equation we need to allow this as well =#
:Cons
elseif T === :nil
# Syntactic sugar for Nil
:Nil
elseif T === :NONE
# Syntactic sugar for Nothing
:Nothing
else
T
end
end
"""
Handles match equations such as
@match x = 4
"""
function handle_match_eq(expr)
if @capture(expr, pattern_ = value_)
asserts = Expr[]
bound = Set{Symbol}()
body = handle_destruct(:value, pattern, bound, asserts)
quote
$(asserts...)
value = $(esc(value))
__omc_match_done = false
$body || throw(MatchFailure("no match", value))
$(@splice variable in bound quote
$(esc(variable)) = $(Symbol("variable_$variable"))
end)
value
end
else
error("Unrecognized match syntax: $expr")
end
end
"""
Handles match cases both for the matchcontinue and regular match case
calls handle_destruct. See handle_destruct for more details.
"""
function handle_match_case(value, case, tail, asserts, matchcontinue::Bool)
if @capture(case, pattern_ => result_)
bound = Set{Symbol}()
body = handle_destruct(:value, pattern, bound, asserts)
if matchcontinue
quote
if (!__omc_match_done) && $body
try
res = let $(bound...)
# export bindings
$(@splice variable in bound quote
$(esc(variable)) = $(Symbol("variable_", variable))
end)
$(esc(result))
end
__omc_match_done = true
catch e
#=
We only rethrow for two kinds of exceptions currently.
One for list, and one for generic MetaModelicaExceptions.
=#
#if isa(e, MetaModelicaException) || isa(e, ImmutableListException)
# println(e.msg)
#else
# showerror(stderr, e, catch_backtrace())
#end
if !isa(e, MetaModelicaException) && !isa(e, ImmutableListException)
if isa(e, MatchFailure)
println("MatchFailure:" + e.msg)
else
showerror(stderr, e, catch_backtrace())
end
rethrow(e)
end
__omc_match_done = false
end
end
$tail
end
else
quote
if (!__omc_match_done) && $body
res = let $(bound...)
# export bindings
$(@splice variable in bound quote
$(esc(variable)) = $(Symbol("variable_", variable))
end)
$(esc(result))
end
__omc_match_done = true
end
$tail
end
end
else
error("Unrecognized case syntax: $case")
end
end
"""
Top level function for all match macros except
the match equation macro.
"""
function handle_match_cases(value, match::Expr; mathcontinue::Bool=false)
tail = nothing
if match.head != :block
error("Unrecognized match syntax: Expected begin block $match")
end
line = nothing
cases = Expr[]
asserts = Expr[]
for arg in match.args
if isa(arg, LineNumberNode)
line = arg
continue
elseif isa(arg, Expr)
push!(cases, arg)
end
end
for case in reverse(cases)
tail = handle_match_case(:value, case, tail, asserts, mathcontinue)
if line !== nothing
replaceLineNum(tail, @__FILE__, line)
end
end
quote
$(asserts...)
local value = $(esc(value))
local __omc_match_done::Bool = false
local res
$tail
if !__omc_match_done
throw(MatchFailure("unfinished", value))
end
res
end
end
"""
@match pattern = value
If `value` matches `pattern`, bind variables and return `value`. Otherwise, throw `MatchFailure`.
"""
macro match(expr)
res = handle_match_eq(expr)
replaceLineNum(res, @__FILE__, __source__)
res
end
"""
@matchcontinue value begin
pattern1 => result1
pattern2 => result2
...
end
Return `result` for the first matching `pattern`. If there are no matches, throw `MatchFailure`.
"""
macro matchcontinue(value, cases)
res = handle_match_cases(value, cases; mathcontinue=true)
replaceLineNum(res, @__FILE__, __source__)
res
end
"""
@match value begin
pattern1 => result1
pattern2 => result2
...
end
Return `result` for the first matching `pattern`. If there are no matches, throw `MatchFailure`.
"""
macro match(value, cases)
res = handle_match_cases(value, cases; mathcontinue=false)
replaceLineNum(res, @__FILE__, __source__)
res
end
"""
Patterns:
* `_` matches anything
* `foo` matches anything, binds value to `foo`
* `foo(__)` wildcard match on all subfields of foo, binds value to `foo`
* `Foo(x,y,z)` matches structs of type `Foo` with fields matching `x,y,z`
* `Foo(x=y)` matches structs of type `Foo` with a field named `x` matching `y`
* `[x,y,z]` matches `AbstractArray`s with 3 entries matching `x,y,z`
* `(x,y,z)` matches `Tuple`s with 3 entries matching `x,y,z`
* `[x,y...,z]` matches `AbstractArray`s with at least 2 entries, where `x` matches the first entry, `z` matches the last entry and `y` matches the remaining entries.
* `(x,y...,z)` matches `Tuple`s with at least 2 entries, where `x` matches the first entry, `z` matches the last entry and `y` matches the remaining entries.
* `_::T` matches any subtype (`isa`) of T
* `x || y` matches values which match either `x` or `y` (only variables which exist in both branches will be bound)
* `x && y` matches values which match both `x` and `y`
* `x where condition` matches only if `condition` is true (`condition` may use any variables that occur earlier in the pattern eg `(x, y, z where x + y > z)`)
* `x => y` is syntactic sugar for `cons(x,y)` [Preliminary]
* Anything else is treated as a constant and tested for equality
Patterns can be nested arbitrarily.
Repeated variables only match if they are `==` eg `(x,x)` matches `(1,1)` but not `(1,2)`.
"""
:(@matchcontinue)