| 1 |
module List = struct end |
| 2 |
open Import |
| 3 |
|
| 4 |
(* |
| 5 |
RE - A regular expression library |
| 6 |
|
| 7 |
Copyright (C) 2001 Jerome Vouillon |
| 8 |
email: [email protected] |
| 9 |
|
| 10 |
This library is free software; you can redistribute it and/or |
| 11 |
modify it under the terms of the GNU Lesser General Public |
| 12 |
License as published by the Free Software Foundation, with |
| 13 |
linking exception; either version 2.1 of the License, or (at |
| 14 |
your option) any later version. |
| 15 |
|
| 16 |
This library is distributed in the hope that it will be useful, |
| 17 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 18 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 19 |
Lesser General Public License for more details. |
| 20 |
|
| 21 |
You should have received a copy of the GNU Lesser General Public |
| 22 |
License along with this library; if not, write to the Free Software |
| 23 |
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
| 24 |
*) |
| 25 |
|
| 26 |
type c = int |
| 27 |
|
| 28 |
let equal_c = Int.equal |
| 29 |
let to_int x = x |
| 30 |
let of_int x = x |
| 31 |
let to_char t = Char.chr t |
| 32 |
let of_char c = Char.code c |
| 33 |
let null_char = -1 |
| 34 |
|
| 35 |
type t = (c * c) list |
| 36 |
|
| 37 |
let compare_pair (x, y) (x', y') = |
| 38 |
match Int.compare x x' with |
| 39 |
| 0 -> Int.compare y y' |
| 40 |
| x -> x |
| 41 |
;; |
| 42 |
|
| 43 |
let equal_pair (x, y) (x', y') = Int.equal x x' && Int.equal y y' |
| 44 |
let equal = List.equal ~eq:equal_pair |
| 45 |
let compare : t -> t -> int = List.compare ~cmp:compare_pair |
| 46 |
|
| 47 |
let rec union l l' = |
| 48 |
match l, l' with |
| 49 |
| _, [] -> l |
| 50 |
| [], _ -> l' |
| 51 |
| (c1, c2) :: r, (c1', c2') :: r' -> |
| 52 |
if c2 + 1 < c1' |
| 53 |
then (c1, c2) :: union r l' |
| 54 |
else if c2' + 1 < c1 |
| 55 |
then (c1', c2') :: union l r' |
| 56 |
else if c2 < c2' |
| 57 |
then union r ((min c1 c1', c2') :: r') |
| 58 |
else union ((min c1 c1', c2) :: r) r' |
| 59 |
;; |
| 60 |
|
| 61 |
let rec inter l l' = |
| 62 |
match l, l' with |
| 63 |
| _, [] -> [] |
| 64 |
| [], _ -> [] |
| 65 |
| (c1, c2) :: r, (c1', c2') :: r' -> |
| 66 |
if c2 < c1' |
| 67 |
then inter r l' |
| 68 |
else if c2' < c1 |
| 69 |
then inter l r' |
| 70 |
else if c2 < c2' |
| 71 |
then (max c1 c1', c2) :: inter r l' |
| 72 |
else (max c1 c1', c2') :: inter l r' |
| 73 |
;; |
| 74 |
|
| 75 |
let rec diff l l' = |
| 76 |
match l, l' with |
| 77 |
| _, [] -> l |
| 78 |
| [], _ -> [] |
| 79 |
| (c1, c2) :: r, (c1', c2') :: r' -> |
| 80 |
if c2 < c1' |
| 81 |
then (c1, c2) :: diff r l' |
| 82 |
else if c2' < c1 |
| 83 |
then diff l r' |
| 84 |
else ( |
| 85 |
let r'' = if c2' < c2 then (c2' + 1, c2) :: r else r in |
| 86 |
if c1 < c1' then (c1, c1' - 1) :: diff r'' r' else diff r'' r') |
| 87 |
;; |
| 88 |
|
| 89 |
let single c = [ c, c ] |
| 90 |
let add c l = union (single c) l |
| 91 |
let seq c c' = if c <= c' then [ c, c' ] else [ c', c ] |
| 92 |
|
| 93 |
let rec offset o l = |
| 94 |
match l with |
| 95 |
| [] -> [] |
| 96 |
| (c1, c2) :: r -> (c1 + o, c2 + o) :: offset o r |
| 97 |
;; |
| 98 |
|
| 99 |
let empty = [] |
| 100 |
let cany = [ 0, 255 ] |
| 101 |
let union_all : t list -> t = List.fold_left ~init:empty ~f:union |
| 102 |
let intersect_all : t list -> t = List.fold_left ~init:cany ~f:inter |
| 103 |
|
| 104 |
let rec mem (c : int) s = |
| 105 |
match s with |
| 106 |
| [] -> false |
| 107 |
| (c1, c2) :: rem -> if c <= c2 then c >= c1 else mem c rem |
| 108 |
;; |
| 109 |
|
| 110 |
(****) |
| 111 |
|
| 112 |
let rec hash_rec = function |
| 113 |
| [] -> 0 |
| 114 |
| (i, j) :: r -> i + (13 * j) + (257 * hash_rec r) |
| 115 |
;; |
| 116 |
|
| 117 |
let hash l = hash_rec l land 0x3FFFFFFF |
| 118 |
|
| 119 |
(****) |
| 120 |
|
| 121 |
let print_one ch (c1, c2) = |
| 122 |
if Int.equal c1 c2 then Format.fprintf ch "%d" c1 else Format.fprintf ch "%d-%d" c1 c2 |
| 123 |
;; |
| 124 |
|
| 125 |
let pp = Fmt.list ~pp_sep:(Fmt.lit ", ") print_one |
| 126 |
|
| 127 |
let rec iter t ~f = |
| 128 |
match t with |
| 129 |
| [] -> () |
| 130 |
| (x, y) :: xs -> |
| 131 |
f x y; |
| 132 |
iter xs ~f |
| 133 |
;; |
| 134 |
|
| 135 |
let one_char = function |
| 136 |
| [ (i, j) ] when Int.equal i j -> Some i |
| 137 |
| _ -> None |
| 138 |
;; |
| 139 |
|
| 140 |
module CSetMap = Map.Make (struct |
| 141 |
type t = int * (int * int) list |
| 142 |
|
| 143 |
let compare (i, u) (j, v) = |
| 144 |
let c = Int.compare i j in |
| 145 |
if c <> 0 then c else compare u v |
| 146 |
;; |
| 147 |
end) |
| 148 |
|
| 149 |
let fold_right t ~init ~f = List.fold_right ~f:(fun (x, y) acc -> f x y acc) t ~init |
| 150 |
let csingle c = single (Char.code c) |
| 151 |
|
| 152 |
let is_empty = function |
| 153 |
| [] -> true |
| 154 |
| _ -> false |
| 155 |
;; |
| 156 |
|
| 157 |
let rec prepend s x l = |
| 158 |
match s, l with |
| 159 |
| [], _ -> l |
| 160 |
| _r, [] -> [] |
| 161 |
| (_c, c') :: r, ([ (d, _d') ], _x') :: _r' when c' < d -> prepend r x l |
| 162 |
| (c, c') :: r, ([ (d, d') ], x') :: r' -> |
| 163 |
if c <= d |
| 164 |
then |
| 165 |
if c' < d' |
| 166 |
then ([ d, c' ], x @ x') :: prepend r x (([ c' + 1, d' ], x') :: r') |
| 167 |
else ([ d, d' ], x @ x') :: prepend s x r' |
| 168 |
else if c > d' |
| 169 |
then ([ d, d' ], x') :: prepend s x r' |
| 170 |
else ([ d, c - 1 ], x') :: prepend s x (([ c, d' ], x') :: r') |
| 171 |
| _ -> assert false |
| 172 |
;; |
| 173 |
|
| 174 |
let pick = function |
| 175 |
| [] -> invalid_arg "Re_cset.pick" |
| 176 |
| (x, _) :: _ -> x |
| 177 |
;; |
| 178 |
|
| 179 |
let cseq c c' = seq (of_char c) (of_char c') |
| 180 |
let rg = cseq |
| 181 |
let char = csingle |
| 182 |
let upper = union_all [ cseq 'A' 'Z'; cseq '\192' '\214'; cseq '\216' '\222' ] |
| 183 |
let clower = offset 32 upper |
| 184 |
let cdigit = cseq '0' '9' |
| 185 |
let ascii = cseq '\000' '\127' |
| 186 |
let cadd c s = add (of_char c) s |
| 187 |
let space = add (of_char ' ') (cseq '\009' '\013') |
| 188 |
let xdigit = union_all [ cdigit; cseq 'a' 'f'; cseq 'A' 'F' ] |
| 189 |
|
| 190 |
let calpha = |
| 191 |
List.fold_right |
| 192 |
~f:cadd |
| 193 |
[ '\170'; '\181'; '\186'; '\223'; '\255' ] |
| 194 |
~init:(union clower upper) |
| 195 |
;; |
| 196 |
|
| 197 |
let calnum = union calpha cdigit |
| 198 |
|
| 199 |
let case_insens s = |
| 200 |
union_all [ s; offset 32 (inter s upper); offset (-32) (inter s clower) ] |
| 201 |
;; |
| 202 |
|
| 203 |
let cword = cadd '_' calnum |
| 204 |
let notnl = diff cany (csingle '\n') |
| 205 |
let nl = csingle '\n' |
| 206 |
|
| 207 |
let set str = |
| 208 |
let s = ref empty in |
| 209 |
for i = 0 to String.length str - 1 do |
| 210 |
s := union (csingle str.[i]) !s |
| 211 |
done; |
| 212 |
!s |
| 213 |
;; |
| 214 |
|
| 215 |
let blank = set "\t " |
| 216 |
|
| 217 |
(* CR-someday rgrinberg: this [lower] doesn't match [clower] *) |
| 218 |
let lower = union_all [ rg 'a' 'z'; char '\181'; rg '\223' '\246'; rg '\248' '\255' ] |
| 219 |
let alpha = union_all [ lower; upper; char '\170'; char '\186' ] |
| 220 |
let alnum = union_all [ alpha; cdigit ] |
| 221 |
let wordc = union_all [ alnum; char '_' ] |
| 222 |
let cntrl = union_all [ rg '\000' '\031'; rg '\127' '\159' ] |
| 223 |
let graph = union_all [ rg '\033' '\126'; rg '\160' '\255' ] |
| 224 |
let print = union_all [ rg '\032' '\126'; rg '\160' '\255' ] |
| 225 |
|
| 226 |
let punct = |
| 227 |
union_all |
| 228 |
[ rg '\033' '\047' |
| 229 |
; rg '\058' '\064' |
| 230 |
; rg '\091' '\096' |
| 231 |
; rg '\123' '\126' |
| 232 |
; rg '\160' '\169' |
| 233 |
; rg '\171' '\180' |
| 234 |
; rg '\182' '\185' |
| 235 |
; rg '\187' '\191' |
| 236 |
; char '\215' |
| 237 |
; char '\247' |
| 238 |
] |
| 239 |
;; |