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