Debian Codegraph @

vendor/re/src/automata.ml

raw
1 open Import
2
3 (*
4 RE - A regular expression library
5
6 Copyright (C) 2001 Jerome Vouillon
7 email: [email protected]
8
9 This library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Lesser General Public
11 License as published by the Free Software Foundation, with
12 linking exception; either version 2.1 of the License, or (at
13 your option) any later version.
14
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
19
20 You should have received a copy of the GNU Lesser General Public
21 License along with this library; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 *)
24
25 let hash_combine h accu = (accu * 65599) + h
26
27 module Ids : sig
28 module Id : sig
29 type t
30
31 val equal : t -> t -> bool
32 val zero : t
33 val hash : t -> int
34 val pp : t Fmt.t
35
36 module Hash_set : sig
37 type id := t
38 type t
39
40 val create : unit -> t
41 val mem : t -> id -> bool
42 val add : t -> id -> unit
43 val clear : t -> unit
44 end
45 end
46
47 type t
48
49 val create : unit -> t
50 val next : t -> Id.t
51 end = struct
52 module Id = struct
53 type t = int
54
55 module Hash_set = Hash_set
56
57 let equal = Int.equal
58 let zero = 0
59 let hash x = x
60 let pp = Fmt.int
61 end
62
63 type t = int ref
64
65 let create () = ref 0
66
67 let next t =
68 incr t;
69 !t
70 ;;
71 end
72
73 module Id = Ids.Id
74
75 module Sem = struct
76 type t =
77 [ `Longest
78 | `Shortest
79 | `First
80 ]
81
82 let equal = Poly.equal
83
84 let pp ch k =
85 Format.pp_print_string
86 ch
87 (match k with
88 | `Shortest -> "short"
89 | `Longest -> "long"
90 | `First -> "first")
91 ;;
92 end
93
94 module Rep_kind = struct
95 type t =
96 [ `Greedy
97 | `Non_greedy
98 ]
99
100 let pp fmt = function
101 | `Greedy -> Format.pp_print_string fmt "Greedy"
102 | `Non_greedy -> Format.pp_print_string fmt "Non_greedy"
103 ;;
104 end
105
106 module Mark : sig
107 type t = private int
108
109 val compare : t -> t -> int
110 val equal : t -> t -> bool
111 val pp : t Fmt.t
112 val start : t
113 val prev : t -> t
114 val next : t -> t
115 val next2 : t -> t
116 val group_count : t -> int
117 val outside_range : t -> start_inclusive:t -> stop_inclusive:t -> bool
118 end = struct
119 type t = int
120
121 let equal = Int.equal
122 let compare = Int.compare
123 let pp = Format.pp_print_int
124 let start = 0
125 let prev x = pred x
126 let next x = succ x
127 let next2 x = x + 2
128 let group_count x = x / 2
129
130 let outside_range t ~start_inclusive ~stop_inclusive =
131 t < start_inclusive || t > stop_inclusive
132 ;;
133 end
134
135 module Idx : sig
136 type t = private int
137
138 val pp : t Fmt.t
139 val to_int : t -> int
140 val unknown : t
141 val initial : t
142 val used : t -> bool
143 val make : int -> t
144 val equal : t -> t -> bool
145 end = struct
146 type t = int
147
148 let to_int x = x
149 let pp = Format.pp_print_int
150 let used t = t >= 0
151 let make x = x
152 let equal = Int.equal
153 let unknown = -1
154 let initial = 0
155 end
156
157 module Expr = struct
158 type t =
159 { id : Id.t
160 ; def : def
161 }
162
163 and def =
164 | Cst of Cset.t
165 | Alt of t list
166 | Seq of Sem.t * t * t
167 | Eps
168 | Rep of Rep_kind.t * Sem.t * t
169 | Mark of Mark.t
170 | Erase of Mark.t * Mark.t
171 | Before of Category.t
172 | After of Category.t
173 | Pmark of Pmark.t
174
175 let rec pp ch e =
176 let open Fmt in
177 match e.def with
178 | Cst l -> sexp ch "cst" Cset.pp l
179 | Alt l -> sexp ch "alt" (list pp) l
180 | Seq (k, e, e') -> sexp ch "seq" (triple Sem.pp pp pp) (k, e, e')
181 | Eps -> str ch "eps"
182 | Rep (_rk, k, e) -> sexp ch "rep" (pair Sem.pp pp) (k, e)
183 | Mark i -> sexp ch "mark" Mark.pp i
184 | Pmark i -> sexp ch "pmark" Pmark.pp i
185 | Erase (b, e) -> sexp ch "erase" (pair Mark.pp Mark.pp) (b, e)
186 | Before c -> sexp ch "before" Category.pp c
187 | After c -> sexp ch "after" Category.pp c
188 ;;
189
190 let eps_expr = { id = Id.zero; def = Eps }
191 let mk ids def = { id = Ids.next ids; def }
192 let empty ids = mk ids (Alt [])
193 let cst ids s = if Cset.is_empty s then empty ids else mk ids (Cst s)
194 let eps ids = mk ids Eps
195 let rep ids kind sem x = mk ids (Rep (kind, sem, x))
196 let mark ids m = mk ids (Mark m)
197 let pmark ids i = mk ids (Pmark i)
198 let erase ids m m' = mk ids (Erase (m, m'))
199 let before ids c = mk ids (Before c)
200 let after ids c = mk ids (After c)
201
202 let alt ids = function
203 | [] -> empty ids
204 | [ c ] -> c
205 | l -> mk ids (Alt l)
206 ;;
207
208 let seq ids (kind : Sem.t) x y =
209 match x.def, y.def with
210 | Alt [], _ -> x
211 | _, Alt [] -> y
212 | Eps, _ -> y
213 | _, Eps when Sem.equal kind `First -> x
214 | _ -> mk ids (Seq (kind, x, y))
215 ;;
216
217 let is_eps expr =
218 match expr.def with
219 | Eps -> true
220 | _ -> false
221 ;;
222
223 let rec rename ids x =
224 match x.def with
225 | Cst _ | Eps | Mark _ | Pmark _ | Erase _ | Before _ | After _ -> mk ids x.def
226 | Alt l -> mk ids (Alt (List.map ~f:(rename ids) l))
227 | Seq (k, y, z) -> mk ids (Seq (k, rename ids y, rename ids z))
228 | Rep (g, k, y) -> mk ids (Rep (g, k, rename ids y))
229 ;;
230 end
231
232 type expr = Expr.t
233
234 include Expr
235
236 module Marks = struct
237 type t =
238 { marks : (Mark.t * Idx.t) list
239 ; pmarks : Pmark.Set.t
240 }
241
242 let equal { marks; pmarks } t =
243 List.equal
244 ~eq:(fun (x, y) (x', y') -> Mark.equal x x' && Idx.equal y y')
245 marks
246 t.marks
247 && Pmark.Set.equal pmarks t.pmarks
248 ;;
249
250 let empty = { marks = []; pmarks = Pmark.Set.empty }
251
252 let hash_marks_offset =
253 let f acc ((a : Mark.t), (i : Idx.t)) =
254 hash_combine (a :> int) (hash_combine (i :> int) acc)
255 in
256 fun l init -> List.fold_left l ~init ~f
257 ;;
258
259 let hash m accu = hash_marks_offset m.marks (hash_combine (Hashtbl.hash m.pmarks) accu)
260
261 let marks_set_idx =
262 let rec marks_set_idx idx marks =
263 match marks with
264 | [] -> []
265 | (a, idx') :: rem ->
266 if Idx.equal idx' Idx.unknown then (a, idx) :: marks_set_idx idx rem else marks
267 in
268 fun marks idx -> { marks with marks = marks_set_idx idx marks.marks }
269 ;;
270
271 let filter t (b : Mark.t) (e : Mark.t) =
272 { t with
273 marks =
274 List.filter t.marks ~f:(fun ((i : Mark.t), _) ->
275 Mark.outside_range i ~start_inclusive:b ~stop_inclusive:e)
276 }
277 ;;
278
279 let set_mark t (i : Mark.t) =
280 { t with marks = (i, Idx.unknown) :: List.remove_assq i t.marks }
281 ;;
282
283 let set_pmark t i = { t with pmarks = Pmark.Set.add i t.pmarks }
284
285 let pp fmt { marks; pmarks } =
286 Format.pp_open_box fmt 1;
287 (match marks with
288 | [] -> ()
289 | _ :: _ ->
290 Format.fprintf
291 fmt
292 "@[<2>marks@ %a@]"
293 (Format.pp_print_list (fun fmt (a, i) ->
294 Format.fprintf fmt "%a-%a" Mark.pp a Idx.pp i))
295 marks);
296 (match Pmark.Set.to_list pmarks with
297 | [] -> ()
298 | pmarks ->
299 Format.fprintf fmt "@[<2>pmarks %a@]" (Format.pp_print_list Pmark.pp) pmarks);
300 Format.pp_close_box fmt ()
301 ;;
302 end
303
304 module Status = struct
305 type t =
306 | Failed
307 | Match of Mark_infos.t * Pmark.Set.t
308 | Running
309 end
310
311 module Desc : sig
312 module E : sig
313 type t = private
314 | TSeq of Sem.t * t list * Expr.t
315 | TExp of Marks.t * Expr.t
316 | TMatch of Marks.t
317
318 val tmatch : Marks.t -> t
319 val tseq : Sem.t -> t list -> Expr.t -> t list -> t list
320 val initial : Expr.t -> t
321 val eps : Marks.t -> t
322 end
323
324 type t = E.t list
325
326 val set_idx : Idx.t -> t -> t
327 val hash : t -> int -> int
328 val equal : t -> t -> bool
329 val status : t -> Status.t
330 val first_match : t -> Marks.t option
331 val remove_matches : t -> t
332 val split_at_match : t -> t * t
333 end = struct
334 module E = struct
335 type t =
336 | TSeq of Sem.t * t list * Expr.t
337 | TExp of Marks.t * Expr.t
338 | TMatch of Marks.t
339
340 let tmatch marks = TMatch marks
341 let initial expr = TExp (Marks.empty, expr)
342 let eps marks = TExp (marks, eps_expr)
343
344 let rec equal_list l1 l2 = List.equal ~eq:equal l1 l2
345
346 and equal x y =
347 match x, y with
348 | TSeq (_, l1, e1), TSeq (_, l2, e2) -> Id.equal e1.id e2.id && equal_list l1 l2
349 | TExp (marks1, e1), TExp (marks2, e2) ->
350 Id.equal e1.id e2.id && Marks.equal marks1 marks2
351 | TMatch marks1, TMatch marks2 -> Marks.equal marks1 marks2
352 | _, _ -> false
353 ;;
354
355 let rec hash (t : t) accu =
356 match t with
357 | TSeq (_, l, e) ->
358 hash_combine 0x172a1bce (hash_combine (Id.hash e.id) (hash_list l accu))
359 | TExp (marks, e) ->
360 hash_combine 0x2b4c0d77 (hash_combine (Id.hash e.id) (Marks.hash marks accu))
361 | TMatch marks -> hash_combine 0x1c205ad5 (Marks.hash marks accu)
362
363 and hash_list =
364 let f acc x = hash x acc in
365 fun l init -> List.fold_left l ~init ~f
366 ;;
367
368 let tseq' kind x y =
369 match x with
370 | [] -> []
371 | [ TExp (marks, { def = Eps; _ }) ] -> [ TExp (marks, y) ]
372 | _ -> [ TSeq (kind, x, y) ]
373 ;;
374
375 let tseq kind x y rem = tseq' kind x y @ rem
376 end
377
378 type t = E.t list
379
380 open E
381
382 let equal = E.equal_list
383 let hash = E.hash_list
384
385 let rec print_state_rec ch e (y : Expr.t) =
386 match e with
387 | TMatch marks -> Format.fprintf ch "@[<2>(Match@ %a)@]" Marks.pp marks
388 | TSeq (_kind, l', x) ->
389 Format.fprintf ch "@[<2>(Seq@ ";
390 print_state_lst ch l' x;
391 Format.fprintf ch "@ %a)@]" Expr.pp x
392 | TExp (marks, { def = Eps; _ }) ->
393 Format.fprintf ch "@[<2>(Exp@ %a@ (%a)@ (eps))@]" Id.pp y.id Marks.pp marks
394 | TExp (marks, x) ->
395 Format.fprintf ch "@[<2>(Exp@ %a@ (%a)@ %a)@]" Id.pp x.id Marks.pp marks Expr.pp x
396
397 and print_state_lst ch l y =
398 match l with
399 | [] -> Format.fprintf ch "()"
400 | e :: rem ->
401 print_state_rec ch e y;
402 List.iter rem ~f:(fun e ->
403 Format.fprintf ch "@ | ";
404 print_state_rec ch e y)
405 ;;
406
407 let pp ch t = print_state_lst ch [ t ] { id = Id.zero; def = Eps }
408
409 let rec first_match = function
410 | [] -> None
411 | TMatch marks :: _ -> Some marks
412 | _ :: r -> first_match r
413 ;;
414
415 let remove_matches =
416 List.filter ~f:(function
417 | TMatch _ -> false
418 | _ -> true)
419 ;;
420
421 let split_at_match =
422 let rec split_at_match_rec l = function
423 | [] -> assert false
424 | TMatch _ :: r -> List.rev l, remove_matches r
425 | x :: r -> split_at_match_rec (x :: l) r
426 in
427 fun l -> split_at_match_rec [] l
428 ;;
429
430 let status : _ -> Status.t = function
431 | [] -> Failed
432 | TMatch m :: _ -> Match (Mark_infos.make (m.marks :> (int * int) list), m.pmarks)
433 | _ -> Running
434 ;;
435
436 let set_idx =
437 let rec f idx = function
438 | TMatch marks -> TMatch (Marks.marks_set_idx marks idx)
439 | TSeq (kind, l, x) -> TSeq (kind, set_idx idx l, x)
440 | TExp (marks, x) -> TExp (Marks.marks_set_idx marks idx, x)
441 and set_idx idx xs = List.map xs ~f:(f idx) in
442 set_idx
443 ;;
444
445 let[@ocaml.warning "-32"] pp fmt t =
446 Format.fprintf fmt "[%a]" (Format.pp_print_list ~pp_sep:(Fmt.lit "; ") pp) t
447 ;;
448 end
449
450 module E = Desc.E
451
452 module State = struct
453 type t =
454 { idx : Idx.t
455 ; category : Category.t
456 ; desc : Desc.t
457 ; mutable status : Status.t Option.Unboxed.t
458 ; hash : int
459 }
460
461 let[@inline] idx t = t.idx
462
463 let dummy =
464 { idx = Idx.unknown
465 ; category = Category.dummy
466 ; desc = []
467 ; status = Option.Unboxed.none
468 ; hash = -1
469 }
470 ;;
471
472 let hash idx cat desc =
473 Desc.hash desc (hash_combine idx (hash_combine (Category.to_int cat) 0))
474 land 0x3FFFFFFF
475 ;;
476
477 let mk idx cat desc =
478 { idx
479 ; category = cat
480 ; desc
481 ; status = Option.Unboxed.none
482 ; hash = hash (idx :> int) cat desc
483 }
484 ;;
485
486 let create cat e = mk Idx.initial cat [ E.initial e ]
487
488 let equal { idx; category; desc; status = _; hash } t =
489 Int.equal hash t.hash
490 && Idx.equal idx t.idx
491 && Category.equal category t.category
492 && Desc.equal desc t.desc
493 ;;
494
495 let status s =
496 let status = s.status in
497 match Option.Unboxed.is_some status with
498 | true -> Option.Unboxed.value_exn status
499 | false ->
500 let st = Desc.status s.desc in
501 s.status <- Option.Unboxed.some st;
502 st
503 ;;
504
505 module Table = Hashtbl.Make (struct
506 type nonrec t = t
507
508 let equal = equal
509 let hash t = t.hash
510 end)
511 end
512
513 (**** Find a free index ****)
514
515 module Working_area = struct
516 type t =
517 { mutable ids : Bit_vector.t
518 ; seen : Id.Hash_set.t
519 }
520
521 let create () = { ids = Bit_vector.create_zero 1; seen = Id.Hash_set.create () }
522 let index_count w = Bit_vector.length w.ids
523
524 let rec mark_used_indices tbl =
525 List.iter ~f:(fun (e : E.t) ->
526 match e with
527 | TSeq (_, l, _) -> mark_used_indices tbl l
528 | TExp (marks, _) | TMatch marks ->
529 List.iter marks.marks ~f:(fun (_, i) ->
530 if Idx.used i then Bit_vector.set tbl (i :> int) true))
531 ;;
532
533 let rec find_free tbl idx len =
534 if idx = len || not (Bit_vector.get tbl idx) then idx else find_free tbl (idx + 1) len
535 ;;
536
537 let free_index t l =
538 Bit_vector.reset_zero t.ids;
539 mark_used_indices t.ids l;
540 let len = Bit_vector.length t.ids in
541 let idx = find_free t.ids 0 len in
542 if idx = len then t.ids <- Bit_vector.create_zero (2 * len);
543 Idx.make idx
544 ;;
545 end
546
547 (**** Computation of the next state ****)
548
549 let remove_duplicates =
550 let rec loop seen (l : Desc.t) y =
551 match l with
552 | [] -> []
553 | (TMatch _ as x) :: _ ->
554 (* Truncate after first match *)
555 [ x ]
556 | TSeq (kind, l, x) :: r ->
557 let l = loop seen l x in
558 let r = loop seen r y in
559 E.tseq kind l x r
560 | (TExp (_marks, { def = Eps; _ }) as e) :: r ->
561 if Id.Hash_set.mem seen y.id
562 then loop seen r y
563 else (
564 Id.Hash_set.add seen y.id;
565 e :: loop seen r y)
566 | (TExp (_marks, x) as e) :: r ->
567 if Id.Hash_set.mem seen x.id
568 then loop seen r y
569 else (
570 Id.Hash_set.add seen x.id;
571 e :: loop seen r y)
572 in
573 fun seen l y ->
574 Id.Hash_set.clear seen;
575 loop seen l y
576 ;;
577
578 type ctx =
579 { c : Cset.c
580 ; prev_cat : Category.t
581 ; next_cat : Category.t
582 }
583
584 let rec delta_expr ({ c; _ } as ctx) marks (x : Expr.t) rem =
585 (*Format.eprintf "%d@." x.id;*)
586 match x.def with
587 | Cst s -> if Cset.mem c s then E.eps marks :: rem else rem
588 | Alt l -> delta_alt ctx marks l rem
589 | Seq (kind, y, z) ->
590 let y = delta_expr ctx marks y [] in
591 delta_seq ctx kind y z rem
592 | Rep (rep_kind, kind, y) ->
593 let y, marks' =
594 let y = delta_expr ctx marks y [] in
595 match Desc.first_match y with
596 | None -> y, marks
597 | Some marks -> Desc.remove_matches y, marks
598 in
599 (match rep_kind with
600 | `Greedy -> E.tseq kind y x (E.tmatch marks' :: rem)
601 | `Non_greedy -> E.tmatch marks :: E.tseq kind y x rem)
602 | Eps -> E.tmatch marks :: rem
603 | Mark i -> E.tmatch (Marks.set_mark marks i) :: rem
604 | Pmark i -> E.tmatch (Marks.set_pmark marks i) :: rem
605 | Erase (b, e) -> E.tmatch (Marks.filter marks b e) :: rem
606 | Before cat ->
607 if Category.intersect ctx.next_cat cat then E.tmatch marks :: rem else rem
608 | After cat ->
609 if Category.intersect ctx.prev_cat cat then E.tmatch marks :: rem else rem
610
611 and delta_alt ctx marks l rem =
612 match l with
613 | [] -> rem
614 | y :: r -> delta_expr ctx marks y (delta_alt ctx marks r rem)
615
616 and delta_seq ctx (kind : Sem.t) y z rem =
617 match Desc.first_match y with
618 | None -> E.tseq kind y z rem
619 | Some marks ->
620 (match kind with
621 | `Longest -> E.tseq kind (Desc.remove_matches y) z (delta_expr ctx marks z rem)
622 | `Shortest -> delta_expr ctx marks z (E.tseq kind (Desc.remove_matches y) z rem)
623 | `First ->
624 let y, y' = Desc.split_at_match y in
625 E.tseq kind y z (delta_expr ctx marks z (E.tseq kind y' z rem)))
626 ;;
627
628 let rec delta_e ctx marks (x : E.t) rem =
629 match x with
630 | TSeq (kind, y, z) ->
631 let y = delta_desc ctx marks y [] in
632 delta_seq ctx kind y z rem
633 | TExp (marks, e) -> delta_expr ctx marks e rem
634 | TMatch _ -> x :: rem
635
636 and delta_desc ctx marks l rem =
637 match l with
638 | [] -> rem
639 | y :: r -> delta_e ctx marks y (delta_desc ctx marks r rem)
640 ;;
641
642 let delta (tbl_ref : Working_area.t) next_cat char (st : State.t) =
643 let expr =
644 let prev_cat = st.category in
645 let ctx = { c = char; next_cat; prev_cat } in
646 remove_duplicates tbl_ref.seen (delta_desc ctx Marks.empty st.desc []) Expr.eps_expr
647 in
648 let idx = Working_area.free_index tbl_ref expr in
649 let expr = Desc.set_idx idx expr in
650 State.mk idx next_cat expr
651 ;;