Debian Codegraph @

src/nekoml/Match.nml

raw
1 /*
2 * Copyright (C)2005-2022 Haxe Foundation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 */
22
23 /* -----
24 We're using the same algorithm and source code as described in
25 chapter 5.2.4 of "The Zinc experiment" by X. Leroy
26 ( https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.6772 )
27 also described in "The Implementation of Functional Programming Languages"
28 by Simon Peyton Jones, in the Chapter 5 by Philip Wadler
29 ( https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/ )
30 */
31
32 open Nekoml.Ast;
33 open Nekoml.Type;
34
35 type complete {
36 Total;
37 Partial;
38 Dubious;
39 }
40
41 type lambda = match_op
42
43 type matching = ((pattern list , lambda) list , lambda list)
44
45 var fully_matched_ref = &(function(cl) { false })
46 var error_ref = &(function(msg : string,p : pos) { assert() })
47
48 function error(msg,p) {
49 (*error_ref) msg p;
50 }
51
52 var failure = MFailure
53
54 function handle(l1,l2) {
55 if l2 == MFailure then
56 l1
57 else if l1 == MFailure then
58 l2
59 else
60 MHandle l1 l2
61 }
62
63 function exec(e) {
64 MExecute e true
65 }
66
67 function cond(path,lambdas) {
68 MConstants path lambdas
69 }
70
71 function rec mswitch(path,lambdas) {
72 match lambdas {
73 | (TVoid,m1) :: [] -> m1
74 | (TVoid,m1) :: l -> MNext m1 (mswitch path l)
75 | _ -> MSwitch path lambdas
76 }
77 }
78
79 function ewhen(e,e2) {
80 MWhen e e2
81 }
82
83 function rec bind(v,p,m) {
84 match m {
85 | MBind (v2,p2,m) -> MBind v2 p2 (bind v p m)
86 | act -> if v == "_" then act else MBind v p act
87 }
88 }
89
90 function rec junk(p,k,m) {
91 match m {
92 | MBind (v,m,m2) -> MBind v m (junk p k m2)
93 | act -> if k == 0 then act else MJunk p k act
94 }
95 }
96
97 function rec stream_pattern((p,pos)) {
98 (match p {
99 | PIdent i -> PConst (Ident i)
100 | PConst c -> PConst c
101 | PTuple pl -> PTuple (List.map stream_pattern pl)
102 | PRecord (pr,t) -> PRecord (List.map (function((s,p)) { (s , stream_pattern p) }) pr) t
103 | PConstr (path,name,param) -> PConstr path name (match param { None -> None | Some p -> Some (stream_pattern p) })
104 | PAlias (s,p) -> PAlias s (stream_pattern p)
105 | PTyped (p,t) -> PTyped (stream_pattern p) t
106 | PStream (s,k) -> PStream s k
107 } , pos)
108 }
109
110 function rec have_when(m) {
111 match m {
112 | MWhen _ -> true
113 | MBind (_,_,e) -> have_when e
114 | _ -> false
115 }
116 }
117
118 function t_const(c) {
119 match c {
120 | Int i -> TInt i
121 | String s -> TString s
122 | Float f -> TFloat f
123 | Char c -> TChar c
124 | Ident i -> TIdent i
125 | Bool b -> TBool b
126 | _ -> assert()
127 }
128 }
129
130 function total(p1,p2) {
131 match (p1 , p2) {
132 | (Total , Total) -> Total
133 | (Partial , _) -> Partial
134 | (_ , Partial) -> Partial
135 | _ -> Dubious
136 }
137 }
138
139 function partial(p1,p2) {
140 match (p1 , p2) {
141 | (Total , _) -> p2
142 | (_ , Total) -> Total
143 | _ -> Dubious
144 }
145 }
146
147 function rec start_by_a_variable((p,_)) {
148 match p {
149 | PAlias (_,p) -> start_by_a_variable p
150 | PIdent _ -> true
151 | _ -> false
152 }
153 }
154
155 function add_to_match((casel,pathl),cas) {
156 (cas :: casel , pathl)
157 }
158
159 function make_constant_match(path,cas) {
160 match path {
161 | [] -> assert()
162 | _ :: pathl -> ([cas] , pathl)
163 }
164 }
165
166 function make_token_match(path,cas) {
167 ([cas] , path)
168 }
169
170 function make_construct_match(tuple,nargs,pathl,cas) {
171 match pathl {
172 | [] -> assert()
173 | path :: pathl ->
174 function rec make_path(i) {
175 if i >= nargs then
176 pathl
177 else {
178 var k = if tuple then MTuple path i else MField path i;
179 k :: make_path (i + 1)
180 }
181 }
182 ([cas] , make_path 0)
183 }
184 }
185
186 function make_record_match(args,pathl,t,cas) {
187 match pathl {
188 | [] -> assert()
189 | path :: pathl ->
190 var l = List.fold (function(acc,(f,_)) { MRecordField(path,f,t) :: acc }) pathl (List.rev args);
191 ([cas] , l)
192 }
193 }
194
195 function add_to_division(make_match,divlist,key,cas) {
196 try {
197 var matchref = List.assoc key divlist;
198 matchref := add_to_match (*matchref) cas;
199 divlist
200 } catch {
201 Not_found ->
202 (key , &(make_match cas)) :: divlist
203 }
204 }
205
206 function always_add(make_match,divlist,cas) {
207 (TVoid , &(make_match cas)) :: divlist
208 }
209
210 var lines_of_matching = fst
211
212 function fully_matched(cl) {
213 (*fully_matched_ref) cl
214 }
215
216 function flatten(a) {
217 match a {
218 | None -> []
219 | Some p ->
220 match p {
221 | (PTuple l,_) -> l
222 | _ -> [p]
223 }
224 }
225 }
226
227 function split_matching(m) {
228 match m {
229 | (_ , []) ->
230 assert()
231 | (casel, (curpath :: endpathl) as pathl) ->
232 function rec split_rec(l) {
233 match l {
234 | ((PTyped (p,_),_) :: l , act) :: rest ->
235 split_rec ((p :: l, act) :: rest)
236 | ((PAlias (v,p),_) :: l , act) :: rest ->
237 split_rec ((p :: l, bind v curpath act) :: rest)
238 | ((PIdent v,_) :: l , act) :: rest ->
239 var vars , others = split_rec rest;
240 (add_to_match vars (l, bind v curpath act) , others)
241 | casel ->
242 (([] , endpathl) , (casel , pathl))
243 }
244 }
245 split_rec casel
246 }
247 }
248
249 function divide_matching(m) {
250 match m {
251 | (_ , []) ->
252 assert()
253 | (casel , (curpath :: tailpathl) as pathl) ->
254 function rec divide_rec(l) {
255 match l {
256 | [] ->
257 ([] , [] , ([] , pathl))
258 | ([],_) :: _ ->
259 assert()
260 | ((PTyped (p,_),_) :: l , act) :: rest ->
261 divide_rec ((p :: l , act) :: rest)
262 | ((PAlias (v,p),_) :: l, act) :: rest ->
263 divide_rec ((p :: l , bind v curpath act) :: rest)
264 | ((PConst c,_) :: l, act) :: rest ->
265 var constant , constrs, others = divide_rec rest;
266 (add_to_division (make_constant_match pathl) constant (t_const c) (l, act), constrs , others)
267 | ((PConstr (path,c,arg),_) :: l,act) :: rest ->
268 var constants , constrs, others = divide_rec rest;
269 var args = flatten arg;
270 (constants , add_to_division (make_construct_match false (List.length args) pathl) constrs (TModule path TConstr(c)) (List.append args l,act) , others)
271 | ((PTuple [],_) :: l,act) :: rest ->
272 var constants , constrs, others = divide_rec rest;
273 (constants , add_to_division (make_constant_match pathl) constrs TVoid (l, act), others)
274 | ((PTuple args,_) :: l,act) :: rest ->
275 var constants , constrs, others = divide_rec rest;
276 (constants , add_to_division (make_construct_match true (List.length args) pathl) constrs TVoid (List.append args l,act) , others)
277 | ((PRecord (args,t),_) :: l,act) :: rest ->
278 var constants , constrs, others = divide_rec rest;
279 (constants , add_to_division (make_record_match args pathl magic(t)) constrs TVoid (List.append (List.map snd args) l,act) , others)
280 | ((PStream ((SPattern p) :: sl,k),pp) :: l,act) :: rest ->
281 var constants , constrs, others = divide_rec rest;
282 (constants , always_add (make_token_match ((MToken curpath k) :: pathl)) constrs (stream_pattern p :: (PStream sl (k+1),pp) :: l, act) , others)
283 | ((PStream ((SMagicExpr ((PTuple _,_) as p,e)) :: sl,k),pp) :: l,act) :: rest ->
284 var constants , constrs, others = divide_rec rest;
285 var ebind = MExecute (mk TConst(TIdent "@tmp") t_void pp) false;
286 (constants , always_add (make_token_match (junk curpath k (MExecute magic(e) false) :: ebind :: pathl)) constrs ((PConst (Ident "@tmp"),pp) :: stream_pattern p :: (PStream sl 0,pp) :: l, act) , others)
287 | ((PStream ((SMagicExpr (p,e)) :: sl,k),pp) :: l,act) :: rest ->
288 var constants , constrs, others = divide_rec rest;
289 (constants , always_add (make_token_match (junk curpath k (MExecute magic(e) false) :: pathl)) constrs (stream_pattern p :: (PStream sl 0,pp) :: l, act) , others)
290 | ((PStream ([],k),pp) :: l,act) :: rest ->
291 var constants , constrs, others = divide_rec rest;
292 (constants , always_add (make_constant_match pathl) constrs (l, junk curpath k act) , others)
293 | casel ->
294 ([] , [] , (casel,pathl))
295 }
296 }
297 divide_rec casel
298 }
299 }
300
301 function rec conquer_divided_matching(m) {
302 match m {
303 | [] ->
304 ([], Total, [])
305 | (key, matchref) :: rest ->
306 var l1, p1, u1 = conquer_matching (*matchref);
307 var l2, p2, u2 = conquer_divided_matching rest;
308 ((key , l1) :: l2 , total p1 p2 , List.append u1 u2)
309 }
310 }
311
312 function rec conquer_matching(m) {
313 match m {
314 | ([] , _) ->
315 (failure , Partial , [])
316 | (([],action) :: rest , k) ->
317 if have_when action then {
318 var a , p , r = conquer_matching (rest,k);
319 (handle action a , p , r)
320 } else
321 (action , Total, rest)
322 | (_ , []) ->
323 assert()
324 | ((p :: _,_) :: _ , _ :: _) when start_by_a_variable p ->
325 var vars , rest = split_matching m;
326 var l1, p1, u1 = conquer_matching vars;
327 var l2, p2, u2 = conquer_matching rest;
328 if p1 == Total then
329 (l1 , Total, List.append u1 lines_of_matching(rest))
330 else
331 (handle l1 l2 , (if p2 == Total then Total else Dubious) , List.append u1 u2)
332 | (_ , path :: _) ->
333 match divide_matching m {
334 | ([] , [] , vars) ->
335 conquer_matching vars
336 | (consts , [] , vars) ->
337 var l1, _ , u1 = conquer_divided_matching consts;
338 var l2, p2, u2 = conquer_matching vars;
339 (handle (cond path l1) l2 , p2 , List.append u1 u2)
340 | ([] , constrs , vars) ->
341 var l1, p1, u1 = conquer_divided_matching constrs;
342 var l2, p2, u2 = conquer_matching vars;
343 if fully_matched (List.map fst constrs) && p1 == Total then
344 (mswitch path l1 , Total , List.append u1 lines_of_matching(vars))
345 else
346 (handle (mswitch path l1) l2 , partial p1 p2 , List.append u1 u2)
347 | _ ->
348 assert()
349 }
350 | _ ->
351 assert()
352 }
353 }
354
355
356 function make(cases : (pattern list, texpr option, texpr) list,p) {
357 var cases = List.concat (List.map (function((pl,wcond,e)) {
358 var e = exec e;
359 var e = match wcond { None -> e | Some e2 -> ewhen e2 e };
360 List.map (function(p) { ([p] , e) }) pl
361 }) cases);
362 var m = (cases , [MRoot]);
363 var lambda, partial, unused = conquer_matching m;
364 match unused {
365 | [] -> ()
366 | ([] , _ ) :: _ -> error "Some pattern are never matched" p
367 | ((_,p) :: _ , _) :: _ -> error "This pattern is never matched" p};
368 (partial != Total , lambda)
369 }