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