Debian Codegraph @

vendor/re/src/str.ml

raw
1 (***********************************************************************)
2 (* *)
3 (* Objective Caml *)
4 (* *)
5 (* Xavier Leroy, projet Cristal, INRIA Rocquencourt *)
6 (* *)
7 (* Copyright 1996 Institut National de Recherche en Informatique et *)
8 (* en Automatique. All rights reserved. This file is distributed *)
9 (* under the terms of the GNU Library General Public License, with *)
10 (* linking exception. *)
11 (* *)
12 (***********************************************************************)
13
14 (* Modified by [email protected] for integration in RE *)
15
16 (* $Id: re_str.ml,v 1.3 2002/07/03 15:47:54 vouillon Exp $ *)
17
18 module Ast = Ast.Export
19
20 include struct
21 open Core
22
23 let exec = exec
24 let exec_partial = exec_partial
25 end
26
27 type regexp =
28 { mtch : Compile.re Lazy.t
29 ; srch : Compile.re Lazy.t
30 }
31
32 let compile_regexp s c =
33 let re = Emacs.re ~case:(not c) s in
34 { mtch = lazy (Compile.compile (Ast.seq [ Ast.start; re ]))
35 ; srch = lazy (Compile.compile re)
36 }
37 ;;
38
39 let state = ref None
40
41 let string_match re s p =
42 match exec ~pos:p (Lazy.force re.mtch) s with
43 | res ->
44 state := Some res;
45 true
46 | exception Not_found ->
47 state := None;
48 false
49 ;;
50
51 let string_partial_match re s p =
52 match exec_partial ~pos:p (Lazy.force re.mtch) s with
53 | `Full -> string_match re s p
54 | `Partial -> true
55 | `Mismatch -> false
56 ;;
57
58 let search_forward re s p =
59 match exec ~pos:p (Lazy.force re.srch) s with
60 | res ->
61 state := Some res;
62 fst (Group.offset res 0)
63 | exception Not_found ->
64 state := None;
65 raise Not_found
66 ;;
67
68 let rec search_backward re s p =
69 match exec ~pos:p (Lazy.force re.mtch) s with
70 | res ->
71 state := Some res;
72 p
73 | exception Not_found ->
74 state := None;
75 if p = 0 then raise Not_found else search_backward re s (p - 1)
76 ;;
77
78 let valid_group n =
79 n >= 0
80 && n < 10
81 &&
82 match !state with
83 | None -> false
84 | Some m -> n < Group.nb_groups m
85 ;;
86
87 let offset_group i =
88 match !state with
89 | Some m -> Group.offset m i
90 | None -> raise Not_found
91 ;;
92
93 let group_len i =
94 match offset_group i with
95 | b, e -> e - b
96 | exception Not_found -> 0
97 ;;
98
99 let rec repl_length repl p q len =
100 if p < len
101 then
102 if repl.[p] <> '\\'
103 then repl_length repl (p + 1) (q + 1) len
104 else (
105 let p = p + 1 in
106 if p = len then failwith "Str.replace: illegal backslash sequence";
107 let q =
108 match repl.[p] with
109 | '\\' -> q + 1
110 | '0' .. '9' as c -> q + group_len (Char.code c - Char.code '0')
111 | _ -> q + 2
112 in
113 repl_length repl (p + 1) q len)
114 else q
115 ;;
116
117 let rec replace orig repl p res q len =
118 if p < len
119 then (
120 let c = repl.[p] in
121 if c <> '\\'
122 then (
123 Bytes.set res q c;
124 replace orig repl (p + 1) res (q + 1) len)
125 else (
126 match repl.[p + 1] with
127 | '\\' ->
128 Bytes.set res q '\\';
129 replace orig repl (p + 2) res (q + 1) len
130 | '0' .. '9' as c ->
131 let d =
132 let group = Char.code c - Char.code '0' in
133 match offset_group group with
134 | exception Not_found -> 0
135 | b, e ->
136 let d = e - b in
137 if d > 0 then String.blit orig b res q d;
138 d
139 in
140 replace orig repl (p + 2) res (q + d) len
141 | c ->
142 Bytes.set res q '\\';
143 Bytes.set res (q + 1) c;
144 replace orig repl (p + 2) res (q + 2) len))
145 ;;
146
147 let replacement_text repl orig =
148 let len = String.length repl in
149 let res = Bytes.create (repl_length repl 0 0 len) in
150 replace orig repl 0 res 0 (String.length repl);
151 Bytes.unsafe_to_string res
152 ;;
153
154 let quote s =
155 let len = String.length s in
156 let buf = Buffer.create (2 * len) in
157 for i = 0 to len - 1 do
158 match s.[i] with
159 | ('[' | ']' | '*' | '.' | '\\' | '?' | '+' | '^' | '$') as c ->
160 Buffer.add_char buf '\\';
161 Buffer.add_char buf c
162 | c -> Buffer.add_char buf c
163 done;
164 Buffer.contents buf
165 ;;
166
167 let string_before s n = String.sub s 0 n
168 let string_after s n = String.sub s n (String.length s - n)
169 let first_chars s n = String.sub s 0 n
170 let last_chars s n = String.sub s (String.length s - n) n
171 let regexp e = compile_regexp e false
172 let regexp_case_fold e = compile_regexp e true
173 let regexp_string s = compile_regexp (quote s) false
174 let regexp_string_case_fold s = compile_regexp (quote s) true
175
176 let group_beginning n =
177 if not (valid_group n) then invalid_arg "Str.group_beginning";
178 let pos = fst (offset_group n) in
179 if pos = -1 then raise Not_found else pos
180 ;;
181
182 let group_end n =
183 if not (valid_group n) then invalid_arg "Str.group_end";
184 let pos = snd (offset_group n) in
185 if pos = -1 then raise Not_found else pos
186 ;;
187
188 let matched_group n txt =
189 let b, e = offset_group n in
190 String.sub txt b (e - b)
191 ;;
192
193 let replace_matched repl matched = replacement_text repl matched
194
195 let match_beginning () = group_beginning 0
196 and match_end () = group_end 0
197 and matched_string txt = matched_group 0 txt
198
199 let substitute_first expr repl_fun text =
200 try
201 let pos = search_forward expr text 0 in
202 String.concat
203 ""
204 [ string_before text pos; repl_fun text; string_after text (match_end ()) ]
205 with
206 | Not_found -> text
207 ;;
208
209 let global_substitute expr repl_fun text =
210 let rec replace accu start last_was_empty =
211 let startpos = if last_was_empty then start + 1 else start in
212 if startpos > String.length text
213 then string_after text start :: accu
214 else (
215 match search_forward expr text startpos with
216 | pos ->
217 let end_pos = match_end () in
218 let repl_text = repl_fun text in
219 replace
220 (repl_text :: String.sub text start (pos - start) :: accu)
221 end_pos
222 (end_pos = pos)
223 | exception Not_found -> string_after text start :: accu)
224 in
225 String.concat "" (List.rev (replace [] 0 false))
226 ;;
227
228 let global_replace expr repl text = global_substitute expr (replacement_text repl) text
229 and replace_first expr repl text = substitute_first expr (replacement_text repl) text
230
231 let search_forward_progress re s p =
232 let pos = search_forward re s p in
233 if match_end () > p
234 then pos
235 else if p < String.length s
236 then search_forward re s (p + 1)
237 else raise Not_found
238 ;;
239
240 let bounded_split expr text num =
241 let start = if string_match expr text 0 then match_end () else 0 in
242 let rec split accu start n =
243 if start >= String.length text
244 then accu
245 else if n = 1
246 then string_after text start :: accu
247 else (
248 try
249 let pos = search_forward_progress expr text start in
250 split (String.sub text start (pos - start) :: accu) (match_end ()) (n - 1)
251 with
252 | Not_found -> string_after text start :: accu)
253 in
254 List.rev (split [] start num)
255 ;;
256
257 let split expr text = bounded_split expr text 0
258
259 let bounded_split_delim expr text num =
260 let rec split accu start n =
261 if start > String.length text
262 then accu
263 else if n = 1
264 then string_after text start :: accu
265 else (
266 try
267 let pos = search_forward_progress expr text start in
268 split (String.sub text start (pos - start) :: accu) (match_end ()) (n - 1)
269 with
270 | Not_found -> string_after text start :: accu)
271 in
272 if text = "" then [] else List.rev (split [] 0 num)
273 ;;
274
275 let split_delim expr text = bounded_split_delim expr text 0
276
277 type split_result =
278 | Text of string
279 | Delim of string
280
281 let bounded_full_split expr text num =
282 let rec split accu start n =
283 if start >= String.length text
284 then accu
285 else if n = 1
286 then Text (string_after text start) :: accu
287 else (
288 try
289 let pos = search_forward_progress expr text start in
290 let s = matched_string text in
291 if pos > start
292 then
293 split
294 (Delim s :: Text (String.sub text start (pos - start)) :: accu)
295 (match_end ())
296 (n - 1)
297 else split (Delim s :: accu) (match_end ()) (n - 1)
298 with
299 | Not_found -> Text (string_after text start) :: accu)
300 in
301 List.rev (split [] 0 num)
302 ;;
303
304 let full_split expr text = bounded_full_split expr text 0