Debian Codegraph @

vendor/re/src/compile.ml

raw
1 open Import
2
3 let rec iter n f v = if Int.equal n 0 then v else iter (n - 1) f (f v)
4
5 module Idx : sig
6 type t [@@immediate]
7
8 val unknown : t
9 val make_break : Automata.Idx.t -> t
10 val of_idx : Automata.Idx.t -> t
11 val is_idx : t -> bool
12 val is_break : t -> bool
13 val idx : t -> int
14 val break_idx : t -> int
15 end = struct
16 type t = int
17
18 let unknown = -2
19 let break = -3
20 let of_idx (x : Automata.Idx.t) = Automata.Idx.to_int x [@@inline always]
21 let is_idx t = t >= 0 [@@inline always]
22 let is_break x = x <= break [@@inline always]
23 let idx t = t [@@inline always]
24 let make_break (idx : Automata.Idx.t) = -5 - Automata.Idx.to_int idx [@@inline always]
25 let break_idx t = (t + 5) * -1 [@@inline always]
26 end
27
28 type match_info =
29 | Match of Group.t
30 | Failed
31 | Running of { no_match_starts_before : int }
32
33 type state_info =
34 { idx : Idx.t
35 ; (* Index of the current position in the position table.
36 Not yet computed transitions point to a dummy state where
37 [idx] is set to [unknown];
38 If [idx] is set to [break] for states that either always
39 succeed or always fail. *)
40 mutable final : (Category.t * (Automata.Idx.t * Automata.Status.t)) list
41 ; (* Mapping from the category of the next character to
42 - the index where the next position should be saved
43 - possibly, the list of marks (and the corresponding indices)
44 corresponding to the best match *)
45 desc : Automata.State.t (* Description of this state of the automata *)
46 }
47
48 (* A state [t] is a pair composed of some information about the
49 state [state_info] and a transition table [t array], indexed by
50 color. For performance reason, to avoid an indirection, we manually
51 unbox the transition table: we allocate a single array, with the
52 state information at index 0, followed by the transitions. *)
53 module State : sig
54 type t
55
56 val make : ncol:int -> state_info -> t
57 val make_break : state_info -> t
58 val get_info : t -> state_info
59 val follow_transition : t -> color:Cset.c -> t
60 val set_transition : t -> color:Cset.c -> t -> unit
61 end = struct
62 type t = Table of t array [@@unboxed]
63
64 let get_info (Table st) : state_info = Obj.magic (Array.unsafe_get st 0)
65 [@@inline always]
66 ;;
67
68 let set_info (Table st) (info : state_info) = st.(0) <- Obj.magic info
69
70 let follow_transition (Table st) ~color = Array.unsafe_get st (1 + Cset.to_int color)
71 [@@inline always]
72 ;;
73
74 let set_transition (Table st) ~color st' = st.(1 + Cset.to_int color) <- st'
75 let dummy (info : state_info) = Table [| Obj.magic info |]
76 let unknown_state = dummy { idx = Idx.unknown; final = []; desc = Automata.State.dummy }
77
78 let make ~ncol state =
79 let st = Table (Array.make (ncol + 1) unknown_state) in
80 set_info st state;
81 st
82 ;;
83
84 let make_break state = Table [| Obj.magic state |]
85 end
86
87 (* Automata (compiled regular expression) *)
88 type re =
89 { initial : Automata.expr
90 ; (* The whole regular expression *)
91 mutable initial_states : (Category.t * State.t) list
92 ; (* Initial states, indexed by initial category *)
93 colors : Color_map.Table.t
94 ; (* Color table *)
95 color_repr : Color_map.Repr.t
96 ; (* Table from colors to one character of this color *)
97 ncolor : int
98 ; (* Number of colors. *)
99 lnl : Cset.c
100 ; (* Color of the last newline. [Cset.null_char] if unnecessary *)
101 tbl : Automata.Working_area.t
102 ; (* Temporary table used to compute the first available index
103 when computing a new state *)
104 states : State.t Automata.State.Table.t
105 ; (* States of the deterministic automata *)
106 group_names : (string * int) list
107 ; (* Named groups in the regular expression *)
108 group_count : int (* Number of groups in the regular expression *)
109 }
110
111 let pp_re ch re = Automata.pp ch re.initial
112 let group_count re = re.group_count
113 let group_names re = re.group_names
114
115 module Positions = struct
116 (* Information used during matching *)
117 type t =
118 { mutable positions : int array
119 (* Array of mark positions
120 The mark are off by one for performance reasons *)
121 }
122
123 let empty = { positions = [||] }
124 let length t = Array.length t.positions
125 let set t idx pos = Array.unsafe_set t.positions idx pos
126
127 let resize t =
128 let len = Array.length t.positions in
129 let pos = t.positions in
130 t.positions <- Array.make (2 * len) 0;
131 Array.blit pos 0 t.positions 0 len
132 ;;
133
134 let all t = t.positions
135 let first t = t.positions.(0)
136
137 let make ~groups re =
138 if groups
139 then
140 { positions =
141 (let n = Automata.Working_area.index_count re.tbl + 1 in
142 if n <= 10 then [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0 |] else Array.make n 0)
143 }
144 else empty
145 ;;
146 end
147
148 (****)
149
150 let category re ~color =
151 if Cset.equal_c color Cset.null_char
152 then Category.inexistant (* Special category for the last newline *)
153 else if Cset.equal_c color re.lnl
154 then Category.(lastnewline ++ newline ++ not_letter)
155 else Category.from_char (Color_map.Repr.repr re.color_repr color)
156 ;;
157
158 (****)
159
160 let find_state re desc =
161 try Automata.State.Table.find re.states desc with
162 | Not_found ->
163 let st =
164 let break_state =
165 match Automata.State.status desc with
166 | Running -> false
167 | Failed | Match _ -> true
168 in
169 let st =
170 { idx =
171 (let idx = Automata.State.idx desc in
172 if break_state then Idx.make_break idx else Idx.of_idx idx)
173 ; final = []
174 ; desc
175 }
176 in
177 if break_state then State.make_break st else State.make ~ncol:re.ncolor st
178 in
179 Automata.State.Table.add re.states desc st;
180 st
181 ;;
182
183 (**** Match with marks ****)
184
185 let delta re positions cat ~color st =
186 let desc = Automata.delta re.tbl cat color st.desc in
187 let len = Positions.length positions in
188 if len > 0 && Automata.State.idx desc |> Automata.Idx.to_int = len
189 then Positions.resize positions;
190 desc
191 ;;
192
193 let validate re positions (s : string) ~pos st =
194 let color = Color_map.Table.get re.colors s.[pos] in
195 let st' =
196 let desc' =
197 let cat = category re ~color in
198 delta re positions cat ~color (State.get_info st)
199 in
200 find_state re desc'
201 in
202 State.set_transition st ~color st'
203 ;;
204
205 let next colors st s pos =
206 State.follow_transition st ~color:(Color_map.Table.get colors (String.unsafe_get s pos))
207 ;;
208
209 let rec loop re ~colors ~positions s ~pos ~last st0 st =
210 if pos < last
211 then (
212 let st' = next colors st s pos in
213 let idx = (State.get_info st').idx in
214 if Idx.is_idx idx
215 then (
216 Positions.set positions (Idx.idx idx) pos;
217 loop re ~colors ~positions s ~pos:(pos + 1) ~last st' st')
218 else if Idx.is_break idx
219 then (
220 Positions.set positions (Idx.break_idx idx) pos;
221 st')
222 else (
223 (* Unknown *)
224 validate re positions s ~pos st0;
225 loop re ~colors ~positions s ~pos ~last st0 st0))
226 else st
227 ;;
228
229 let rec loop_no_mark re ~colors s ~pos ~last st0 st =
230 if pos < last
231 then (
232 let st' = next colors st s pos in
233 let idx = (State.get_info st').idx in
234 if Idx.is_idx idx
235 then loop_no_mark re ~colors s ~pos:(pos + 1) ~last st' st'
236 else if Idx.is_break idx
237 then st'
238 else (
239 (* Unknown *)
240 validate re Positions.empty s ~pos st0;
241 loop_no_mark re ~colors s ~pos ~last st0 st0))
242 else st
243 ;;
244
245 let final re positions st cat =
246 try List.assq cat st.final with
247 | Not_found ->
248 let st' = delta re positions cat ~color:Cset.null_char st in
249 let res = Automata.State.idx st', Automata.State.status st' in
250 st.final <- (cat, res) :: st.final;
251 res
252 ;;
253
254 let find_initial_state re cat =
255 try List.assq cat re.initial_states with
256 | Not_found ->
257 let st = find_state re (Automata.State.create cat re.initial) in
258 re.initial_states <- (cat, st) :: re.initial_states;
259 st
260 ;;
261
262 let get_color re (s : string) pos =
263 if pos < 0
264 then Cset.null_char
265 else (
266 let slen = String.length s in
267 if pos >= slen
268 then Cset.null_char
269 else if pos = slen - 1
270 && (not (Cset.equal_c re.lnl Cset.null_char))
271 && Char.equal (String.unsafe_get s pos) '\n'
272 then (* Special case for the last newline *)
273 re.lnl
274 else Color_map.Table.get re.colors (String.unsafe_get s pos))
275 ;;
276
277 let rec handle_last_newline re positions ~pos st ~groups =
278 let st' = State.follow_transition st ~color:re.lnl in
279 let info = State.get_info st' in
280 if Idx.is_idx info.idx
281 then (
282 if groups then Positions.set positions (Idx.idx info.idx) pos;
283 st')
284 else if Idx.is_break info.idx
285 then (
286 if groups then Positions.set positions (Idx.break_idx info.idx) pos;
287 st')
288 else (
289 (* Unknown *)
290 let color = re.lnl in
291 let st' =
292 let desc =
293 let cat = category re ~color in
294 let real_c = Color_map.Table.get re.colors '\n' in
295 delta re positions cat ~color:real_c (State.get_info st)
296 in
297 find_state re desc
298 in
299 State.set_transition st ~color st';
300 handle_last_newline re positions ~pos st ~groups)
301 ;;
302
303 let rec scan_str re positions (s : string) initial_state ~last ~pos ~groups =
304 if last = String.length s
305 && (not (Cset.equal_c re.lnl Cset.null_char))
306 && last > pos
307 && Char.equal (String.get s (last - 1)) '\n'
308 then (
309 let last = last - 1 in
310 let st = scan_str re positions ~pos s initial_state ~last ~groups in
311 if Idx.is_break (State.get_info st).idx
312 then st
313 else handle_last_newline re positions ~pos:last st ~groups)
314 else if groups
315 then loop re ~colors:re.colors ~positions s ~pos ~last initial_state initial_state
316 else loop_no_mark re ~colors:re.colors s ~pos ~last initial_state initial_state
317 ;;
318
319 (* This function adds a final boundary check on the input.
320 This is useful to indicate that the output failed because
321 of insufficient input, or to verify that the output actually
322 matches for regex that have boundary conditions with respect
323 to the input string.
324 *)
325 let final_boundary_check re positions ~last ~slen s state_info ~groups =
326 let idx, res =
327 let final_cat =
328 Category.(
329 search_boundary
330 ++ if last = slen then inexistant else category re ~color:(get_color re s last))
331 in
332 final re positions state_info final_cat
333 in
334 (match groups, res with
335 | true, Match _ -> Positions.set positions (Automata.Idx.to_int idx) last
336 | _ -> ());
337 res
338 ;;
339
340 let make_match_str re positions ~len ~groups ~partial s ~pos =
341 let slen = String.length s in
342 let last = if len = -1 then slen else pos + len in
343 let st =
344 let initial_state =
345 let initial_cat =
346 Category.(
347 search_boundary
348 ++ if pos = 0 then inexistant else category re ~color:(get_color re s (pos - 1)))
349 in
350 find_initial_state re initial_cat
351 in
352 scan_str re positions s initial_state ~pos ~last ~groups
353 in
354 let state_info = State.get_info st in
355 if Idx.is_break state_info.idx || (partial && not groups)
356 then Automata.State.status state_info.desc
357 else if partial && groups
358 then (
359 match Automata.State.status state_info.desc with
360 | (Match _ | Failed) as status -> status
361 | Running ->
362 (* This could be because it's still not fully matched, or it
363 could be that because we need to run special end of input
364 checks. *)
365 (match final_boundary_check re positions ~last ~slen s state_info ~groups with
366 | Match _ as status -> status
367 | Failed | Running ->
368 (* A failure here just means that we need more data, i.e.
369 it's a partial match. *)
370 Running))
371 else final_boundary_check re positions ~last ~slen s state_info ~groups
372 ;;
373
374 let match_str_no_bounds ~groups ~partial re s ~pos ~len =
375 let positions = Positions.make ~groups re in
376 match make_match_str re positions ~len ~groups ~partial s ~pos with
377 | Match (marks, pmarks) ->
378 Match
379 (Group.create s marks pmarks ~gpos:(Positions.all positions) ~gcount:re.group_count)
380 | Failed -> Failed
381 | Running ->
382 let no_match_starts_before = if groups then Positions.first positions else 0 in
383 Running { no_match_starts_before }
384 ;;
385
386 let match_str_p re s ~pos ~len =
387 if pos < 0 || len < -1 || pos + len > String.length s
388 then invalid_arg "Re.exec: out of bounds";
389 match make_match_str re Positions.empty ~len ~groups:false ~partial:false s ~pos with
390 | Match _ -> true
391 | _ -> false
392 ;;
393
394 let match_str ~groups ~partial re s ~pos ~len =
395 if pos < 0 || len < -1 || pos + len > String.length s
396 then invalid_arg "Re.exec: out of bounds";
397 match_str_no_bounds ~groups ~partial re s ~pos ~len
398 ;;
399
400 let mk_re ~initial ~colors ~color_repr ~ncolor ~lnl ~group_names ~group_count =
401 { initial
402 ; initial_states = []
403 ; colors
404 ; color_repr
405 ; ncolor
406 ; lnl
407 ; tbl = Automata.Working_area.create ()
408 ; states = Automata.State.Table.create 97
409 ; group_names
410 ; group_count
411 }
412 ;;
413
414 (**** Compilation ****)
415
416 module A = Automata
417
418 let enforce_kind ids kind kind' cr =
419 match kind, kind' with
420 | `First, `First -> cr
421 | `First, k -> A.seq ids k cr (A.eps ids)
422 | _ -> cr
423 ;;
424
425 type context =
426 { ids : A.Ids.t
427 ; kind : A.Sem.t
428 ; ign_group : bool
429 ; greedy : A.Rep_kind.t
430 ; pos : A.Mark.t ref
431 ; names : (string * int) list ref
432 ; cache : Cset.t Cset.CSetMap.t ref
433 ; colors : Color_map.Table.t
434 }
435
436 let trans_set cache (cm : Color_map.Table.t) s =
437 match Cset.one_char s with
438 | Some i -> Cset.csingle (Color_map.Table.get_char cm i)
439 | None ->
440 let v = Cset.hash s, s in
441 (try Cset.CSetMap.find v !cache with
442 | Not_found ->
443 let l = Color_map.Table.translate_colors cm s in
444 cache := Cset.CSetMap.add v l !cache;
445 l)
446 ;;
447
448 let make_repeater ids cr kind greedy =
449 match greedy with
450 | `Greedy -> fun rem -> A.alt ids [ A.seq ids kind (A.rename ids cr) rem; A.eps ids ]
451 | `Non_greedy ->
452 fun rem -> A.alt ids [ A.eps ids; A.seq ids kind (A.rename ids cr) rem ]
453 ;;
454
455 (* XXX should probably compute a category mask *)
456 let rec translate
457 ({ ids; kind; ign_group; greedy; pos; names; cache; colors } as ctx)
458 (ast : Ast.no_case)
459 =
460 match ast with
461 | Set s -> A.cst ids (trans_set cache colors s), kind
462 | Sequence l -> trans_seq ctx l, kind
463 | Ast (Alternative l) ->
464 (match Ast.merge_sequences l with
465 | [ r' ] ->
466 let cr, kind' = translate ctx r' in
467 enforce_kind ids kind kind' cr, kind
468 | merged_sequences ->
469 ( A.alt
470 ids
471 (List.map merged_sequences ~f:(fun r' ->
472 let cr, kind' = translate ctx r' in
473 enforce_kind ids kind kind' cr))
474 , kind ))
475 | Repeat (r', i, j) ->
476 let cr, kind' = translate ctx r' in
477 let rem =
478 match j with
479 | None -> A.rep ids greedy kind' cr
480 | Some j ->
481 let f = make_repeater ids cr kind' greedy in
482 iter (j - i) f (A.eps ids)
483 in
484 iter i (fun rem -> A.seq ids kind' (A.rename ids cr) rem) rem, kind
485 | Beg_of_line -> A.after ids Category.(inexistant ++ newline), kind
486 | End_of_line -> A.before ids Category.(inexistant ++ newline), kind
487 | Beg_of_word ->
488 ( A.seq
489 ids
490 `First
491 (A.after ids Category.(inexistant ++ not_letter))
492 (A.before ids Category.letter)
493 , kind )
494 | End_of_word ->
495 ( A.seq
496 ids
497 `First
498 (A.after ids Category.letter)
499 (A.before ids Category.(inexistant ++ not_letter))
500 , kind )
501 | Not_bound ->
502 ( A.alt
503 ids
504 [ A.seq ids `First (A.after ids Category.letter) (A.before ids Category.letter)
505 ; (let cat = Category.(inexistant ++ not_letter) in
506 A.seq ids `First (A.after ids cat) (A.before ids cat))
507 ]
508 , kind )
509 | Beg_of_str -> A.after ids Category.inexistant, kind
510 | End_of_str -> A.before ids Category.inexistant, kind
511 | Last_end_of_line -> A.before ids Category.(inexistant ++ lastnewline), kind
512 | Start -> A.after ids Category.search_boundary, kind
513 | Stop -> A.before ids Category.search_boundary, kind
514 | Sem (kind', r') ->
515 let cr, kind'' = translate { ctx with kind = kind' } r' in
516 enforce_kind ids kind' kind'' cr, kind'
517 | Sem_greedy (greedy', r') -> translate { ctx with greedy = greedy' } r'
518 | Group (n, r') ->
519 if ign_group
520 then translate ctx r'
521 else (
522 let p = !pos in
523 let () =
524 match n with
525 | Some name -> names := (name, A.Mark.group_count p) :: !names
526 | None -> ()
527 in
528 pos := A.Mark.next2 !pos;
529 let cr, kind' = translate ctx r' in
530 ( A.seq ids `First (A.mark ids p) (A.seq ids `First cr (A.mark ids (A.Mark.next p)))
531 , kind' ))
532 | No_group r' -> translate { ctx with ign_group = true } r'
533 | Nest r' ->
534 let b = !pos in
535 let cr, kind' = translate ctx r' in
536 let e = A.Mark.prev !pos in
537 if A.Mark.compare e b = -1
538 then cr, kind'
539 else A.seq ids `First (A.erase ids b e) cr, kind'
540 | Pmark (i, r') ->
541 let cr, kind' = translate ctx r' in
542 A.seq ids `First (A.pmark ids i) cr, kind'
543
544 and trans_seq ({ ids; kind; _ } as ctx) = function
545 | [] -> A.eps ids
546 | [ r ] ->
547 let cr', kind' = translate ctx r in
548 enforce_kind ids kind kind' cr'
549 | r :: rem ->
550 let cr', kind' = translate ctx r in
551 let cr'' = trans_seq ctx rem in
552 if A.is_eps cr'' then cr' else if A.is_eps cr' then cr'' else A.seq ids kind' cr' cr''
553 ;;
554
555 let compile_1 regexp =
556 let regexp = Ast.handle_case false regexp in
557 let color_map = Color_map.make () in
558 let need_lnl = Ast.colorize color_map regexp in
559 let colors, color_repr = Color_map.flatten color_map in
560 let ncolor = Color_map.Repr.length color_repr in
561 let lnl = if need_lnl then Cset.of_int ncolor else Cset.null_char in
562 let ncolor = if need_lnl then ncolor + 1 else ncolor in
563 let ctx =
564 { ids = A.Ids.create ()
565 ; kind = `First
566 ; ign_group = false
567 ; greedy = `Greedy
568 ; pos = ref A.Mark.start
569 ; names = ref []
570 ; cache = ref Cset.CSetMap.empty
571 ; colors
572 }
573 in
574 let r, kind = translate ctx regexp in
575 let r = enforce_kind ctx.ids `First kind r in
576 (*Format.eprintf "<%d %d>@." !ids ncol;*)
577 mk_re
578 ~initial:r
579 ~colors
580 ~color_repr
581 ~ncolor
582 ~lnl
583 ~group_names:(List.rev !(ctx.names))
584 ~group_count:(A.Mark.group_count !(ctx.pos))
585 ;;
586
587 let compile r =
588 let open Ast.Export in
589 compile_1 (if Ast.anchored r then group r else seq [ shortest (rep any); group r ])
590 ;;