| 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 |