Debian Codegraph @

vendor/re/src/glob.ml

raw
1 (*
2 RE - A regular expression library
3
4 Copyright (C) 2001 Jerome Vouillon
5 email: [email protected]
6
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation, with
10 linking exception; either version 2.1 of the License, or (at
11 your option) any later version.
12
13 This library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
17
18 You should have received a copy of the GNU Lesser General Public
19 License along with this library; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 *)
22
23 module Re = Core
24
25 exception Parse_error
26
27 type enclosed =
28 | Char of char
29 | Range of char * char
30
31 type piece =
32 | Exactly of char
33 | Any_of of enclosed list
34 | Any_but of enclosed list
35 | One
36 | Many
37 | ManyMany
38
39 type t = piece list
40
41 let of_string ~double_asterisk s : t =
42 let buf = Parse_buffer.create s in
43 let eos () = Parse_buffer.eos buf in
44 let read c = Parse_buffer.accept buf c in
45 let char () =
46 ignore (read '\\' : bool);
47 if eos () then raise Parse_error;
48 Parse_buffer.get buf
49 in
50 let enclosed () : enclosed list =
51 let rec loop s =
52 (* This returns the list in reverse order, but order isn't important
53 anyway *)
54 if s <> [] && read ']'
55 then s
56 else (
57 let c = char () in
58 if not (read '-')
59 then loop (Char c :: s)
60 else if read ']'
61 then Char c :: Char '-' :: s
62 else (
63 let c' = char () in
64 loop (Range (c, c') :: s)))
65 in
66 loop []
67 in
68 let piece acc =
69 if double_asterisk && Parse_buffer.accept_s buf "/**"
70 then ManyMany :: (if eos () then Exactly '/' :: acc else acc)
71 else if read '*'
72 then (if double_asterisk && read '*' then ManyMany else Many) :: acc
73 else if read '?'
74 then One :: acc
75 else if not (read '[')
76 then Exactly (char ()) :: acc
77 else if read '^' || read '!'
78 then Any_but (enclosed ()) :: acc
79 else Any_of (enclosed ()) :: acc
80 in
81 let rec loop pieces = if eos () then List.rev pieces else loop (piece pieces) in
82 loop []
83 ;;
84
85 let mul l l' = List.flatten (List.map (fun s -> List.map (fun s' -> s ^ s') l') l)
86
87 let explode str =
88 let l = String.length str in
89 let rec expl inner s i acc beg =
90 if i >= l
91 then (
92 if inner then raise Parse_error;
93 mul beg [ String.sub str s (i - s) ], i)
94 else (
95 match str.[i] with
96 | '\\' -> expl inner s (i + 2) acc beg
97 | '{' ->
98 let t, i' = expl true (i + 1) (i + 1) [] [ "" ] in
99 expl inner i' i' acc (mul beg (mul [ String.sub str s (i - s) ] t))
100 | ',' when inner ->
101 expl inner (i + 1) (i + 1) (mul beg [ String.sub str s (i - s) ] @ acc) [ "" ]
102 | '}' when inner -> mul beg [ String.sub str s (i - s) ] @ acc, i + 1
103 | _ -> expl inner s (i + 1) acc beg)
104 in
105 List.rev (fst (expl false 0 0 [] [ "" ]))
106 ;;
107
108 module State = struct
109 type t =
110 { re_pieces : Re.t list (* last piece at head of list. *)
111 ; remaining : piece list (* last piece at tail of list. *)
112 ; am_at_start_of_pattern : bool (* true at start of pattern *)
113 ; am_at_start_of_component : bool
114 (* true at start of pattern or immediately
115 after '/' *)
116 ; pathname : bool
117 ; match_backslashes : bool
118 ; period : bool
119 }
120
121 let create ~period ~pathname ~match_backslashes remaining =
122 { re_pieces = []
123 ; am_at_start_of_pattern = true
124 ; am_at_start_of_component = true
125 ; pathname
126 ; match_backslashes
127 ; period
128 ; remaining
129 }
130 ;;
131
132 let explicit_period t =
133 t.period && (t.am_at_start_of_pattern || (t.am_at_start_of_component && t.pathname))
134 ;;
135
136 let explicit_slash t = t.pathname
137 let slashes t = if t.match_backslashes then [ '/'; '\\' ] else [ '/' ]
138
139 let append ?(am_at_start_of_component = false) t piece =
140 { t with
141 re_pieces = piece :: t.re_pieces
142 ; am_at_start_of_pattern = false
143 ; am_at_start_of_component
144 }
145 ;;
146
147 let to_re t = Re.seq (List.rev t.re_pieces)
148
149 let next t =
150 match t.remaining with
151 | [] -> None
152 | piece :: remaining -> Some (piece, { t with remaining })
153 ;;
154 end
155
156 let one ~explicit_slash ~slashes ~explicit_period =
157 Re.compl
158 (List.concat
159 [ (if explicit_slash then List.map Re.char slashes else [])
160 ; (if explicit_period then [ Re.char '.' ] else [])
161 ])
162 ;;
163
164 let enclosed enclosed =
165 match enclosed with
166 | Char c -> Re.char c
167 | Range (low, high) -> Re.rg low high
168 ;;
169
170 let enclosed_set ~explicit_slash ~slashes ~explicit_period kind set =
171 let set = List.map enclosed set in
172 let enclosure =
173 match kind with
174 | `Any_of -> Re.alt set
175 | `Any_but -> Re.compl set
176 in
177 Re.inter [ enclosure; one ~explicit_slash ~slashes ~explicit_period ]
178 ;;
179
180 let exactly state c =
181 let slashes = State.slashes state in
182 let am_at_start_of_component = List.mem c slashes in
183 let chars = if am_at_start_of_component then slashes else [ c ] in
184 State.append state (Re.alt (List.map Re.char chars)) ~am_at_start_of_component
185 ;;
186
187 let many_many state =
188 let explicit_period = state.State.period && state.State.pathname in
189 let first_explicit_period = State.explicit_period state in
190 let slashes = State.slashes state in
191 let match_component ~explicit_period =
192 Re.seq
193 [ one ~explicit_slash:true ~slashes ~explicit_period
194 ; Re.rep (one ~explicit_slash:true ~slashes ~explicit_period:false)
195 ]
196 in
197 (* We must match components individually when [period] flag is set,
198 making sure to not match ["foo/.bar"]. *)
199 State.append
200 state
201 (Re.seq
202 [ Re.opt (match_component ~explicit_period:first_explicit_period)
203 ; Re.rep
204 (Re.seq
205 [ Re.alt (List.map Re.char slashes)
206 ; Re.opt (match_component ~explicit_period)
207 ])
208 ])
209 ;;
210
211 let many (state : State.t) =
212 let explicit_slash = State.explicit_slash state in
213 let explicit_period = State.explicit_period state in
214 let slashes = State.slashes state in
215 (* Whether we must explicitly match period depends on the surrounding
216 characters, but slashes are easy to explicit match. This conditional
217 splits out some simple cases. *)
218 if not explicit_period
219 then State.append state (Re.rep (one ~explicit_slash ~slashes ~explicit_period))
220 else if not explicit_slash
221 then
222 (* In this state, we explicitly match periods only at the very beginning *)
223 State.append
224 state
225 (Re.opt
226 (Re.seq
227 [ one ~explicit_slash:false ~slashes ~explicit_period
228 ; Re.rep (one ~explicit_slash:false ~slashes ~explicit_period:false)
229 ]))
230 else (
231 let not_empty =
232 Re.seq
233 [ one ~explicit_slash:true ~slashes ~explicit_period:true
234 ; Re.rep (one ~explicit_slash:true ~slashes ~explicit_period:false)
235 ]
236 in
237 (* [maybe_empty] is the default translation of Many, except in some special
238 cases. *)
239 let maybe_empty = Re.opt not_empty in
240 let enclosed_set state kind set =
241 State.append
242 state
243 (Re.alt
244 [ enclosed_set kind set ~explicit_slash:true ~slashes ~explicit_period:true
245 ; Re.seq
246 [ not_empty
247 ; (* Since [not_empty] matched, subsequent dots are not leading. *)
248 enclosed_set
249 kind
250 set
251 ~explicit_slash:true
252 ~slashes
253 ~explicit_period:false
254 ]
255 ])
256 in
257 let rec lookahead state =
258 match State.next state with
259 | None -> State.append state maybe_empty
260 (* glob ** === glob * . *)
261 | Some (Many, state) -> lookahead state
262 | Some (Exactly c, state) ->
263 let state = State.append state (if c = '.' then not_empty else maybe_empty) in
264 exactly state c
265 (* glob *? === glob ?* *)
266 | Some (One, state) -> State.append state not_empty
267 | Some (Any_of enclosed, state) -> enclosed_set state `Any_of enclosed
268 | Some (Any_but enclosed, state) -> enclosed_set state `Any_but enclosed
269 (* * then ** === ** *)
270 | Some (ManyMany, state) -> many_many state
271 in
272 lookahead state)
273 ;;
274
275 let piece state piece =
276 let explicit_slash = State.explicit_slash state in
277 let explicit_period = State.explicit_period state in
278 let slashes = State.slashes state in
279 match piece with
280 | One -> State.append state (one ~explicit_slash ~slashes ~explicit_period)
281 | Many -> many state
282 | Any_of enclosed ->
283 State.append
284 state
285 (enclosed_set `Any_of ~explicit_slash ~slashes ~explicit_period enclosed)
286 | Any_but enclosed ->
287 State.append
288 state
289 (enclosed_set `Any_but ~explicit_slash ~slashes ~explicit_period enclosed)
290 | Exactly c -> exactly state c
291 | ManyMany -> many_many state
292 ;;
293
294 let glob ~pathname ~match_backslashes ~period glob =
295 let rec loop state =
296 match State.next state with
297 | None -> State.to_re state
298 | Some (p, state) -> loop (piece state p)
299 in
300 loop (State.create ~pathname ~match_backslashes ~period glob)
301 ;;
302
303 let glob
304 ?(anchored = false)
305 ?(pathname = true)
306 ?(match_backslashes = false)
307 ?(period = true)
308 ?(expand_braces = false)
309 ?(double_asterisk = true)
310 s
311 =
312 let to_re s =
313 let re = glob ~pathname ~match_backslashes ~period (of_string ~double_asterisk s) in
314 if anchored then Re.whole_string re else re
315 in
316 if expand_braces then Re.alt (List.map to_re (explode s)) else to_re s
317 ;;
318
319 let glob' ?anchored period s = glob ?anchored ~period s
320 let globx ?anchored s = glob ?anchored ~expand_braces:true s
321 let globx' ?anchored period s = glob ?anchored ~expand_braces:true ~period s