Debian Codegraph @

src/core/LexEngine.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 most of this code is taken from the ULex lexer by Alain Frish,
25 originaly written as an OCaml library.
26 */
27
28 type charset = (int , int) list
29
30 type node {
31 mutable id : int;
32 mutable trans : (charset , node) list;
33 mutable epsilon : node list;
34 }
35
36 type state = node list
37
38 type tables = (int array array , int array)
39
40 type t {
41 Empty;
42 Match : charset;
43 Star : t;
44 Plus : t;
45 Next : (t , t);
46 Choice : (t , t);
47 }
48
49 /* ------- charset ------ */
50
51 var max_code = 255;
52
53 var cempty = [];
54 var call = [(0,max_code)];
55
56 function is_empty(c) {
57 c == []
58 }
59
60 function rec cunion(c1,c2) {
61 match (c1 , c2) {
62 | ([] , _) -> c2
63 | (_ , []) -> c1
64 | (((i1,j1) as s1)::r1, (i2,j2)::r2) ->
65 if i1 <= i2 then
66 if j1 + 1 < i2 then s1::(cunion r1 c2)
67 else if (j1 < j2) then cunion r1 ((i1,j2)::r2)
68 else cunion c1 r2
69 else
70 cunion c2 c1
71 | _ -> assert()
72 }
73 }
74
75 function ccomplement(c) {
76 function rec loop(start,l) {
77 match l {
78 | [] -> if start <= max_code then [(start,max_code)] else []
79 | (i,j) :: l -> (start,i-1) :: (loop (j + 1) l)
80 }
81 };
82 match c {
83 | (-1,j) :: l -> loop (j + 1) l
84 | l -> loop (-1) l
85 }
86 }
87
88 function cinter(c1,c2) {
89 ccomplement (cunion (ccomplement c1) (ccomplement c2))
90 }
91
92 function cdiff(c1,c2) {
93 ccomplement (cunion (ccomplement c1) c2)
94 }
95
96 /* ------- nodes -------- */
97
98 function node(g) {
99 {
100 id = g();
101 trans = [];
102 epsilon = [];
103 }
104 }
105
106 function rec add_node(state,node) {
107 if List.exists (function(k) { k === node }) state then
108 state
109 else
110 add_nodes (node::state) node.epsilon
111 }
112
113 function rec add_nodes(state,nodes) {
114 List.fold add_node state nodes
115 }
116
117 function nodes(nfa) {
118 var g = &0;
119 var gen = function() { g := *g + 1; *g };
120 function rec loop(n,final) {
121 match n {
122 | Empty ->
123 final
124 | Match c ->
125 var n = node gen;
126 n.trans := [(c,final)];
127 n
128 | Star a ->
129 var n = node gen;
130 var an = loop a n;
131 n.epsilon := [an; final];
132 n
133 | Plus a ->
134 var n = node gen;
135 var an = loop a n;
136 n.epsilon := [an; final];
137 an
138 | Next (a,b) ->
139 loop a (loop b final)
140 | Choice (a,b) ->
141 var n = node gen;
142 n.epsilon := [loop a final; loop b final];
143 n
144 }
145 };
146 Array.map (function(n) { var f = node gen; (loop n f,f) }) nfa
147 }
148
149 /* ------- NFA -> DFA -------- */
150
151 function transitions(state : state) {
152 // Merge transition with the same target
153 function rec norm(l) {
154 match l {
155 | (t1,n1) :: (((t2,n2) :: q) as l) ->
156 if n1 === n2 then norm ((cunion t1 t2,n1) :: q) else (t1,n1) :: (norm l)
157 | _ -> l
158 }
159 };
160
161 var t = List.concat (List.map (function(n) { n.trans }) state);
162 var t = norm (List.sort (function((t1,n1),(t2,n2)) {
163 n1.id - n2.id
164 }) t);
165
166
167 // Split char sets so as to make them disjoint
168 function rec split((all,t),(c0,n0)) {
169 var t =
170 (cdiff c0 all, [n0]) ::
171 List.append
172 (List.map (function((c,ns)) { (cinter c c0, n0::ns) }) t)
173 (List.map (function((c,ns)) { (cdiff c c0, ns) }) t);
174 (cunion all c0, List.filter (function((c,ns)) { !is_empty c }) t)
175 };
176
177 var _ , t = List.fold split (cempty,[]) t;
178
179 // Epsilon closure of targets
180 var t = List.map (function((t,ns)) { (t,add_nodes [] ns) }) t;
181
182 // Canonical ordering
183 var t = List.array t;
184 Array.sort (function((c1,ns1),(c2,ns2)) { compare c1 c2 }) t;
185 (Array.map fst t, Array.map snd t)
186 }
187
188 function determinize(nfa : t array) {
189 var nfa = nodes nfa;
190 var h = Hashtbl.create();
191 var parts = Hashtbl.create();
192 var state_counter = &0;
193 var part_counter = &0;
194 var lparts = &[];
195 var states = &[];
196 function get_part(p) {
197 try
198 Hashtbl.find parts p
199 catch {
200 Not_found ->
201 var pid = *part_counter;
202 part_counter := *part_counter + 1;
203 Hashtbl.add parts p pid;
204 lparts := p :: *lparts;
205 pid
206 }
207 };
208 function rec loop(state) {
209 var sid = List.map (function(s) { s.id }) state;
210 try
211 Hashtbl.find h sid
212 catch {
213 Not_found ->
214 var id = *state_counter;
215 state_counter := *state_counter + 1;
216 Hashtbl.add h sid id;
217 var part, targets = transitions state;
218 var part = get_part part;
219 var targets = Array.map loop targets;
220 var finals = Array.map (function((_,f)) { List.mem f state }) nfa;
221 states := (id, (part,targets,finals)) :: *states;
222 id
223 }
224 };
225 var init : node list ref = &[];
226 Array.iter (function((i,_)) { init := add_node (*init) i }) nfa;
227 ignore(loop (*init));
228 var dfa = Array.init (*state_counter) (function(id) { List.assoc id (*states) });
229 function loop(part) {
230 var seg = &[];
231 Array.iteri (function(i,c) {
232 List.iter (function((a,b)) { seg := (a,b,i) :: *seg }) c
233 }) part;
234 List.sort (function((a1,_,_),(a2,_,_)) { compare a1 a2 }) (*seg);
235 };
236 var trans = List.array (List.map loop (List.rev (*lparts)));
237 (dfa , trans)
238 }
239
240 /* ---- DFA -> Tables ---- */
241 // this expands memory but is better since all accesses are O(1)
242
243 function make_trans(trans,tbl) {
244 var a = Array.make 256 (-1);
245 List.iter (function((min,max,n)) {
246 var i = &min;
247 while *i <= max {
248 a.[*i] := tbl.[n];
249 i := *i + 1;
250 }
251 }) trans;
252 a
253 }
254
255 function make_tables((dfa,trans)) {
256 function rec first(p,a) {
257 if p == Array.length a then
258 -1
259 else if a.[p] then
260 p
261 else
262 first (p + 1) a
263 };
264 var exits = Array.map (function((_,_,states)) { first 0 states }) dfa;
265 var tbls = Array.map (function((tid,tbl,_)) {
266 make_trans trans.[tid] tbl
267 }) dfa;
268 (tbls , exits)
269 }
270
271
272 /* ---- Regexp Parsing ---- */
273
274 exception InvalidRegexp : string
275
276 function single(c) {
277 var n = ord c;
278 [(n,n)]
279 }
280
281 function group(chars) {
282 var chars = List.map (function((c1,c2)) { [(ord c1,ord c2)] }) chars;
283 List.fold cunion cempty chars
284 }
285
286 function invalid(s) {
287 throw InvalidRegexp(s)
288 }
289
290 function escaped(s,i) {
291 var c = String.get s (*i);
292 i := *i + 1;
293 match c {
294 | '\\'
295 | '+'
296 | '*'
297 | '?'
298 | '['
299 | ']'
300 | '-' -> c
301 | _ -> invalid s
302 }
303 }
304
305 function rec plus(r) {
306 match r {
307 | Next (r1,r2) -> Next(r1,plus r2)
308 | _ -> Plus r
309 }
310 }
311
312 function rec star(r) {
313 match r {
314 | Next (r1,r2) -> Next(r1,star r2)
315 | _ -> Star r
316 }
317 }
318
319 function rec opt(r) {
320 match r {
321 | Next(r1,r2) -> Next(r1,opt r2)
322 | _ -> Choice(r,Empty)
323 }
324 }
325
326 function next(r,r2) {
327 match r {
328 | Empty -> r2
329 | _ -> Next r r2
330 }
331 }
332
333 function parse( s : string ) : t {
334 var i = &0;
335 var r = &Empty;
336 var l = String.length s;
337 while *i < l {
338 var c = String.get s (*i);
339 i := *i + 1;
340 match c {
341 | '+' -> r := plus (*r)
342 | '*' -> r := star (*r)
343 | '?' -> r := opt (*r)
344 | '[' ->
345 var range = &None;
346 function rec loop(acc) {
347 var c = String.get s (*i);
348 i := *i + 1;
349 if c == ']' then {
350 if *range != None then invalid s;
351 acc
352 } else if c == '-' then {
353 if *range != None then invalid s;
354 match acc {
355 | [] -> loop ((c,c) :: acc)
356 | (x1,x2) :: l ->
357 if x1 != x2 then invalid s;
358 range := Some x1;
359 loop l
360 }
361 } else {
362 var c = (if c == '\\' then escaped s i else c);
363 match *range {
364 | None -> loop ((c,c) :: acc)
365 | Some c2 ->
366 range := None;
367 loop ((c2,c) :: acc)
368 }
369 }
370 };
371 var c = String.get s (*i);
372 var g = if c == '^' then {
373 i := *i + 1;
374 cdiff call (group (loop []))
375 } else
376 group (loop []);
377 r := next (*r) Match(g)
378 | '\\' -> r := next (*r) Match(single (escaped s i))
379 | _ -> r := next (*r) Match(single c)
380 }
381 };
382 *r
383 }