Debian Codegraph @

vendor/re/src/cset.ml

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