Debian Codegraph @

vendor/re/src/ast.ml

raw
1 open Import
2
3 type ('a, _) ast =
4 | Alternative : 'a list -> ('a, [> `Uncased ]) ast
5 | No_case : 'a -> ('a, [> `Cased ]) ast
6 | Case : 'a -> ('a, [> `Cased ]) ast
7
8 let empty_alternative : ('a, 'b) ast = Alternative []
9
10 let equal_ast (type a) eq (x : (a, [ `Uncased ]) ast) (y : (a, [ `Uncased ]) ast) =
11 match x, y with
12 | Alternative a, Alternative b -> List.equal ~eq a b
13 ;;
14
15 let pp_ast (type a b) f fmt (ast : (a, b) ast) =
16 let open Fmt in
17 let var s re = sexp fmt s f re in
18 match ast with
19 | Alternative alt -> sexp fmt "Alternative" (list f) alt
20 | Case c -> var "Case" c
21 | No_case c -> var "No_case" c
22 ;;
23
24 type cset =
25 | Cset of Cset.t
26 | Intersection of cset list
27 | Complement of cset list
28 | Difference of cset * cset
29 | Cast of (cset, [ `Cased | `Uncased ]) ast
30
31 type ('a, 'case) gen =
32 | Set of 'a
33 | Ast of (('a, 'case) gen, 'case) ast
34 | Sequence of ('a, 'case) gen list
35 | Repeat of ('a, 'case) gen * int * int option
36 | Beg_of_line
37 | End_of_line
38 | Beg_of_word
39 | End_of_word
40 | Not_bound
41 | Beg_of_str
42 | End_of_str
43 | Last_end_of_line
44 | Start
45 | Stop
46 | Group of string option * ('a, 'case) gen
47 | No_group of ('a, 'case) gen
48 | Nest of ('a, 'case) gen
49 | Pmark of Pmark.t * ('a, 'case) gen
50 | Sem of Automata.Sem.t * ('a, 'case) gen
51 | Sem_greedy of Automata.Rep_kind.t * ('a, 'case) gen
52
53 let rec pp_gen pp_cset fmt t =
54 let open Format in
55 let open Fmt in
56 let pp = pp_gen pp_cset in
57 let var s re = sexp fmt s pp re in
58 let seq s rel = sexp fmt s (list pp) rel in
59 match t with
60 | Set cset -> pp_cset fmt cset
61 | Sequence sq -> seq "Sequence" sq
62 | Repeat (re, start, stop) ->
63 let pp' fmt () = fprintf fmt "%a@ %d%a" pp re start optint stop in
64 sexp fmt "Repeat" pp' ()
65 | Beg_of_line -> str fmt "Beg_of_line"
66 | End_of_line -> str fmt "End_of_line"
67 | Beg_of_word -> str fmt "Beg_of_word"
68 | End_of_word -> str fmt "End_of_word"
69 | Not_bound -> str fmt "Not_bound"
70 | Beg_of_str -> str fmt "Beg_of_str"
71 | End_of_str -> str fmt "End_of_str"
72 | Last_end_of_line -> str fmt "Last_end_of_line"
73 | Start -> str fmt "Start"
74 | Stop -> str fmt "Stop"
75 | Group (None, c) -> var "Group" c
76 | Group (Some n, c) -> sexp fmt "Named_group" (pair str pp) (n, c)
77 | Nest c -> var "Nest" c
78 | Pmark (m, r) -> sexp fmt "Pmark" (pair Pmark.pp pp) (m, r)
79 | Ast a -> pp_ast pp fmt a
80 | Sem (sem, a) -> sexp fmt "Sem" (pair Automata.Sem.pp pp) (sem, a)
81 | Sem_greedy (k, re) -> sexp fmt "Sem_greedy" (pair Automata.Rep_kind.pp pp) (k, re)
82 | No_group c -> var "No_group" c
83 ;;
84
85 let rec pp_cset fmt cset =
86 let open Fmt in
87 let seq s rel = sexp fmt s (list pp_cset) rel in
88 match cset with
89 | Cast s -> pp_ast pp_cset fmt s
90 | Cset s -> sexp fmt "Set" Cset.pp s
91 | Intersection c -> seq "Intersection" c
92 | Complement c -> seq "Complement" c
93 | Difference (a, b) -> sexp fmt "Difference" (pair pp_cset pp_cset) (a, b)
94 ;;
95
96 let rec equal cset x1 x2 =
97 match x1, x2 with
98 | Set s1, Set s2 -> cset s1 s2
99 | Sequence l1, Sequence l2 -> List.equal ~eq:(equal cset) l1 l2
100 | Repeat (x1', i1, j1), Repeat (x2', i2, j2) ->
101 Int.equal i1 i2 && Option.equal Int.equal j1 j2 && equal cset x1' x2'
102 | Beg_of_line, Beg_of_line
103 | End_of_line, End_of_line
104 | Beg_of_word, Beg_of_word
105 | End_of_word, End_of_word
106 | Not_bound, Not_bound
107 | Beg_of_str, Beg_of_str
108 | End_of_str, End_of_str
109 | Last_end_of_line, Last_end_of_line
110 | Start, Start
111 | Stop, Stop -> true
112 | Group _, Group _ ->
113 (* Do not merge groups! *)
114 false
115 | Pmark (m1, r1), Pmark (m2, r2) -> Pmark.equal m1 m2 && equal cset r1 r2
116 | Nest x, Nest y -> equal cset x y
117 | Ast x, Ast y -> equal_ast (equal cset) x y
118 | Sem (sem, a), Sem (sem', a') -> Poly.equal sem sem' && equal cset a a'
119 | Sem_greedy (rep, a), Sem_greedy (rep', a') -> Poly.equal rep rep' && equal cset a a'
120 | _ -> false
121 ;;
122
123 type t = (cset, [ `Cased | `Uncased ]) gen
124 type no_case = (Cset.t, [ `Uncased ]) gen
125
126 let pp = pp_gen pp_cset
127 let cset cset = Set (Cset cset)
128
129 let rec handle_case_cset ign_case = function
130 | Cset s -> if ign_case then Cset.case_insens s else s
131 | Cast (Alternative l) -> List.map ~f:(handle_case_cset ign_case) l |> Cset.union_all
132 | Complement l ->
133 List.map ~f:(handle_case_cset ign_case) l |> Cset.union_all |> Cset.diff Cset.cany
134 | Difference (r, r') ->
135 Cset.inter
136 (handle_case_cset ign_case r)
137 (Cset.diff Cset.cany (handle_case_cset ign_case r'))
138 | Intersection l -> List.map ~f:(handle_case_cset ign_case) l |> Cset.intersect_all
139 | Cast (No_case a) -> handle_case_cset true a
140 | Cast (Case a) -> handle_case_cset false a
141 ;;
142
143 let rec handle_case ign_case : t -> (Cset.t, [ `Uncased ]) gen = function
144 | Set s -> Set (handle_case_cset ign_case s)
145 | Sequence l -> Sequence (List.map ~f:(handle_case ign_case) l)
146 | Ast (Alternative l) ->
147 let l = List.map ~f:(handle_case ign_case) l in
148 Ast (Alternative l)
149 | Repeat (r, i, j) -> Repeat (handle_case ign_case r, i, j)
150 | ( Beg_of_line
151 | End_of_line
152 | Beg_of_word
153 | End_of_word
154 | Not_bound
155 | Beg_of_str
156 | End_of_str
157 | Last_end_of_line
158 | Start
159 | Stop ) as r -> r
160 | Sem (k, r) -> Sem (k, handle_case ign_case r)
161 | Sem_greedy (k, r) -> Sem_greedy (k, handle_case ign_case r)
162 | Group (n, r) -> Group (n, handle_case ign_case r)
163 | No_group r -> No_group (handle_case ign_case r)
164 | Nest r -> Nest (handle_case ign_case r)
165 | Ast (Case r) -> handle_case false r
166 | Ast (No_case r) -> handle_case true r
167 | Pmark (i, r) -> Pmark (i, handle_case ign_case r)
168 ;;
169
170 module Export = struct
171 type nonrec t = t
172
173 let pp = pp
174
175 let seq = function
176 | [ r ] -> r
177 | l -> Sequence l
178 ;;
179
180 let char c : t = cset (Cset.csingle c)
181 let any = cset Cset.cany
182
183 let str s : t =
184 let l = ref [] in
185 for i = String.length s - 1 downto 0 do
186 l := char s.[i] :: !l
187 done;
188 seq !l
189 ;;
190
191 let as_set_elems elems =
192 match
193 List.map elems ~f:(function
194 | Set e -> e
195 | _ -> raise_notrace Exit)
196 with
197 | exception Exit -> None
198 | e -> Some e
199 ;;
200
201 let empty : t = Ast empty_alternative
202
203 let alt (elems : t list) : t =
204 match elems with
205 | [] -> empty
206 | [ x ] -> x
207 | _ ->
208 (match as_set_elems elems with
209 | None -> Ast (Alternative elems)
210 | Some elems -> Set (Cast (Alternative elems)))
211 ;;
212
213 let epsilon = seq []
214
215 let repn r i j =
216 if i < 0 then invalid_arg "Re.repn";
217 match j, i with
218 | Some j, _ when j < i -> invalid_arg "Re.repn"
219 | Some 0, 0 -> epsilon
220 | Some 1, 1 -> r
221 | _ -> Repeat (r, i, j)
222 ;;
223
224 let rep r = repn r 0 None
225 let rep1 r = repn r 1 None
226 let opt r = repn r 0 (Some 1)
227 let bol = Beg_of_line
228 let eol = End_of_line
229 let bow = Beg_of_word
230 let eow = End_of_word
231 let word r = seq [ bow; r; eow ]
232 let not_boundary = Not_bound
233 let bos = Beg_of_str
234 let eos = End_of_str
235 let whole_string r = seq [ bos; r; eos ]
236 let leol = Last_end_of_line
237 let start = Start
238 let stop = Stop
239
240 type 'b f = { f : 'a. 'a -> ('a, 'b) ast }
241
242 let make_set f t =
243 match t with
244 | Set x -> Set (Cast (f.f x))
245 | _ -> Ast (f.f t)
246 ;;
247
248 let preserve_set f t =
249 match t with
250 | Set _ -> t
251 | _ -> f t
252 ;;
253
254 let longest = preserve_set (fun t -> Sem (`Longest, t))
255 let shortest = preserve_set (fun t -> Sem (`Shortest, t))
256 let first = preserve_set (fun t -> Sem (`First, t))
257 let greedy = preserve_set (fun t -> Sem_greedy (`Greedy, t))
258 let non_greedy = preserve_set (fun t -> Sem_greedy (`Non_greedy, t))
259 let group ?name r = Group (name, r)
260 let no_group = preserve_set (fun t -> No_group t)
261 let nest r = Nest r
262 let set str = cset (Cset.set str)
263
264 let mark r =
265 let i = Pmark.gen () in
266 i, Pmark (i, r)
267 ;;
268
269 (**** Character sets ****)
270 let as_set_or_error name elems =
271 match as_set_elems elems with
272 | None -> invalid_arg name
273 | Some s -> s
274 ;;
275
276 let inter elems = Set (Intersection (as_set_or_error "Re.inter" elems))
277 let compl elems = Set (Complement (as_set_or_error "Re.compl" elems))
278
279 let diff r r' =
280 match r, r' with
281 | Set r, Set r' -> Set (Difference (r, r'))
282 | _, _ -> invalid_arg "Re.diff"
283 ;;
284
285 let case =
286 let f = { f = (fun r -> Case r) } in
287 fun t -> make_set f t
288 ;;
289
290 let no_case =
291 let f = { f = (fun r -> No_case r) } in
292 fun t -> make_set f t
293 ;;
294
295 let witness t =
296 let rec witness (t : no_case) =
297 match t with
298 | Set c -> String.make 1 (Cset.to_char (Cset.pick c))
299 | Sequence xs -> String.concat "" (List.map ~f:witness xs)
300 | Ast (Alternative (x :: _)) -> witness x
301 | Ast (Alternative []) -> assert false
302 | Repeat (r, from, _to) ->
303 let w = witness r in
304 let b = Buffer.create (String.length w * from) in
305 for _i = 1 to from do
306 Buffer.add_string b w
307 done;
308 Buffer.contents b
309 | No_group r -> witness r
310 | Sem_greedy (_, r) | Sem (_, r) | Nest r | Pmark (_, r) | Group (_, r) -> witness r
311 | Beg_of_line
312 | End_of_line
313 | Beg_of_word
314 | End_of_word
315 | Not_bound
316 | Beg_of_str
317 | Last_end_of_line
318 | Start
319 | Stop
320 | End_of_str -> ""
321 in
322 witness (handle_case false t)
323 ;;
324 end
325
326 open Export
327
328 let rec merge_sequences = function
329 | [] -> []
330 | Ast (Alternative l') :: r -> merge_sequences (l' @ r)
331 | Sequence (x :: y) :: r ->
332 (match merge_sequences r with
333 | Sequence (x' :: y') :: r' when equal Cset.equal x x' ->
334 Sequence [ x; Ast (Alternative [ seq y; seq y' ]) ] :: r'
335 | r' -> Sequence (x :: y) :: r')
336 | x :: r -> x :: merge_sequences r
337 ;;
338
339 (*XXX Use a better algorithm allowing non-contiguous regions? *)
340
341 let colorize color_map (regexp : no_case) =
342 let lnl = ref false in
343 let rec colorize regexp =
344 match (regexp : no_case) with
345 | Set s -> Color_map.split color_map s
346 | Sequence l -> List.iter ~f:colorize l
347 | Ast (Alternative l) -> List.iter ~f:colorize l
348 | Repeat (r, _, _) -> colorize r
349 | Beg_of_line | End_of_line -> Color_map.split color_map Cset.nl
350 | Beg_of_word | End_of_word | Not_bound -> Color_map.split color_map Cset.cword
351 | Beg_of_str | End_of_str | Start | Stop -> ()
352 | Last_end_of_line -> lnl := true
353 | No_group r | Group (_, r) | Nest r | Pmark (_, r) -> colorize r
354 | Sem (_, r) | Sem_greedy (_, r) -> colorize r
355 in
356 colorize regexp;
357 !lnl
358 ;;
359
360 let rec anchored_ast : (t, _) ast -> bool = function
361 | Alternative als -> List.for_all ~f:anchored als
362 | No_case r | Case r -> anchored r
363
364 and anchored : t -> bool = function
365 | Ast a -> anchored_ast a
366 | Sequence l -> List.exists ~f:anchored l
367 | Repeat (r, i, _) -> i > 0 && anchored r
368 | No_group r | Sem (_, r) | Sem_greedy (_, r) | Group (_, r) | Nest r | Pmark (_, r) ->
369 anchored r
370 | Set _
371 | Beg_of_line
372 | End_of_line
373 | Beg_of_word
374 | End_of_word
375 | Not_bound
376 | End_of_str
377 | Last_end_of_line
378 | Stop -> false
379 | Beg_of_str | Start -> true
380 ;;
381
382 let t_of_cset x = Set x