1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
let is_drive_letter = function 'A' .. 'Z' | 'a' .. 'z' -> true | _ -> false
let is_sep c = c = '\\' || c = '/'
let backslashes = String.map (fun c -> if c = '/' then '\\' else c)
type recognizer = string -> int -> int option
let charp f : recognizer =
fun s i -> if i < String.length s && f s.[i] then Some (i + 1) else None
let ( *> ) (p : recognizer) (q : recognizer) : recognizer =
fun s i -> Option.bind (p s i) (q s)
let ( <|> ) (p : recognizer) (q : recognizer) : recognizer =
fun s i -> match p s i with Some _ as r -> r | None -> q s i
let opt p : recognizer = p <|> (fun _ i -> Some i)
let rec many p : recognizer = fun s i ->
match p s i with Some j -> many p s j | None -> Some i
let matches (r : recognizer) s = Option.is_some (r s 0)
let chr c = charp (Char.equal c)
let eos : recognizer = fun s i -> if i = String.length s then Some i else None
let word w : recognizer = fun s i ->
let n = String.length w in
if i + n <= String.length s && String.lowercase_ascii (String.sub s i n) = w then Some (i + n) else None
let any_word ws = List.fold_left (fun r w -> r <|> word w) (fun _ _ -> None) ws
let sep = charp is_sep
let bslash = chr '\\'
let qmark = chr '?'
let component = many (charp (fun c -> not (is_sep c)))
let component_is f : recognizer = fun s i ->
match component s i with
| Some e when f (String.sub s i (e - i)) -> Some e
| _ -> None
let next = opt sep *> component
let drive = charp is_drive_letter *> chr ':'
let q_or_dot = component_is (fun c -> c = "?" || c = ".")
let unc_kw = component_is (fun c -> String.uppercase_ascii c = "UNC")
let volume_prefix =
drive
<|> (sep *> sep *> q_or_dot *> opt sep *> unc_kw
*> next *> next)
<|> (sep *> sep *> component *> next)
<|> (bslash *> qmark *> qmark *> component *> next)
let verbatim_prefix = bslash *> (bslash <|> qmark) *> qmark
let verbatim s = Option.is_some (verbatim_prefix s 0)
let nt_prefix = (verbatim_prefix <|> (bslash *> bslash *> chr '.')) *> bslash
type kind = [ `Relative | `Rooted | `Drive_relative | `Absolute | `Unc | `Device | `Verbatim ]
let pp_kind ppf : kind -> unit = function
| `Relative -> Fmt.string ppf "relative"
| `Rooted -> Fmt.string ppf "rooted"
| `Drive_relative -> Fmt.string ppf "drive-relative"
| `Absolute -> Fmt.string ppf "absolute"
| `Unc -> Fmt.string ppf "UNC"
| `Device -> Fmt.string ppf "device"
| `Verbatim -> Fmt.string ppf "verbatim"
let classify p : kind =
if verbatim p then `Verbatim
else if matches (sep *> sep *> q_or_dot) p then `Device
else if matches (sep *> sep) p then `Unc
else if matches (drive *> sep) p then `Absolute
else if matches drive p then `Drive_relative
else if matches sep p then `Rooted
else `Relative
let is_relative p = classify p = `Relative
let volume_end s = Option.value (volume_prefix s 0) ~default:0
let drop n s = String.sub s n (String.length s - n)
let split_volume p =
let n = volume_end p in
String.sub p 0 n, drop n p
let split p =
let vend = volume_end p in
let sep_char = if verbatim p then Char.equal '\\' else is_sep in
let sep_at i = sep_char p.[i] in
let rec trim i = if i > vend + 1 && sep_at (i - 1) then trim (i - 1) else i in
let stop = trim (String.length p) in
if stop <= vend || (stop = vend + 1 && sep_at vend) then None
else
let rec rsep i = if i < vend then None else if sep_at i then Some i else rsep (i - 1) in
match rsep (stop - 1) with
| None -> Some (String.sub p 0 vend, String.sub p vend (stop - vend))
| Some idx ->
let basename = String.sub p (idx + 1) (stop - idx - 1) in
let dirname =
String.sub p 0 (if idx = vend then vend + 1 else trim idx)
in
Some (dirname, basename)
let parent_and_leaf p =
match split p with
| Some ("", leaf) -> ".", leaf
| Some parts -> parts
| None -> ".", (if p = "" then "." else p)
let dirname p = fst (parent_and_leaf p)
let basename p = snd (parent_and_leaf p)
let concat a b =
let l = String.length a in
if l = 0 then b
else if (if verbatim a then a.[l - 1] = '\\' else is_sep a.[l - 1]) then a ^ b
else if drive a 0 = Some l then
a ^ b
else a ^ "\\" ^ b
let join p1 p2 =
match p1, p2 with
| p1, "" -> concat p1 p2
| _, p2 when not (is_relative p2) -> p2
| ".", p2 -> p2
| p1, p2 -> concat p1 p2
let chop s = String.sub s 0 (String.length s - 1)
let rec trim_end s =
if String.ends_with ~suffix:"." s || String.ends_with ~suffix:" " s then trim_end (chop s) else s
let normalise path =
let rec go acc = function
| [] -> "\\" ^ String.concat "\\" (List.rev acc)
| ("" | ".") :: xs -> go acc xs
| ".." :: xs -> go (match acc with _ :: acc -> acc | [] -> []) xs
| [x] -> go (match trim_end x with "" -> acc | x -> x :: acc) []
| x :: xs when String.ends_with ~suffix:"." x && not (String.ends_with ~suffix:".." x) -> go (chop x :: acc) xs
| x :: xs -> go (x :: acc) xs
in
go [] (String.split_on_char '\\' path)
let after r p = Option.map (fun i -> drop i p) (r p 0)
let qualify p =
"\\??\\" ^
match after nt_prefix p, after (bslash *> bslash) p with
| Some rest, _ -> rest
| None, Some share -> "UNC\\" ^ share
| None, None -> p
let to_nt ~cwd p =
let vol, rest = split_volume (backslashes p) in
let cwd_vol, cwd_rest = split_volume (backslashes cwd) in
let resolve vol base = qualify (vol ^ normalise (base ^ "\\" ^ rest)) in
match classify p with
| `Verbatim -> qualify p
| `Relative -> resolve cwd_vol cwd_rest
| `Rooted -> resolve cwd_vol ""
| `Drive_relative when String.uppercase_ascii vol = String.uppercase_ascii cwd_vol -> resolve cwd_vol cwd_rest
| `Drive_relative
| `Absolute | `Unc | `Device -> resolve vol ""
let reserved_name =
(any_word ["con"; "prn"; "aux"; "nul"]
<|> (any_word ["com"; "lpt"] *> any_word ["1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"; "9"; "¹"; "²"; "³"]))
*> many (chr ' ') *> (chr '.' <|> chr ':' <|> eos)
let to_win32 p =
match after (verbatim_prefix *> bslash) p with
| None -> p
| Some rest ->
let win32 =
match after (unc_kw *> bslash) rest with
| Some share -> "\\\\" ^ share
| None -> rest
in
if to_nt ~cwd:"" win32 = "\\??\\" ^ rest
&& not (List.exists (matches reserved_name) (String.split_on_char '\\' win32))
then win32
else "\\\\?\\" ^ rest
let relative_components path =
let rec go acc = function
| [] -> Some (String.concat "\\" (List.rev acc))
| ("" | ".") :: xs -> go acc xs
| ".." :: xs -> (match acc with _ :: acc -> go acc xs | [] -> None)
| x :: xs -> go (x :: acc) xs
in
go [] (String.split_on_char '\\' path)
let relative path =
if not (is_relative path) then None
else match relative_components (backslashes path) with
| Some p when is_relative p -> Some p
| _ -> None
let beneath ~root p =
let absolute p = match classify p with `Absolute | `Unc | `Verbatim -> true | _ -> false in
let valid p =
not (String.contains p '/') &&
not (List.exists (fun c -> c = "." || c = "..") (String.split_on_char '\\' p))
in
if not (absolute root && absolute p && valid root && valid p) then None
else
let rec trim p = if String.ends_with ~suffix:"\\" p then trim (chop p) else p in
let root = trim (qualify root) in
let p = qualify p in
let lower = String.lowercase_ascii in
if lower p = lower root then Some ""
else if String.starts_with ~prefix:(lower root ^ "\\") (lower p) then
let rest = drop (String.length root + 1) p in
if is_relative rest then Some rest else None
else None
type link_target = Relative of string | Absolute of string
let link_target ~cwd p =
match classify p with
| `Relative | `Rooted -> Relative (backslashes p)
| _ -> Absolute (to_nt ~cwd p)
let resolve_link ?root ~parent target =
let parent =
match root, target with
| Some root, Relative p when is_relative parent && classify p = `Rooted -> root
| _ -> parent
in
let resolved = match target with
| Absolute p -> if matches nt_prefix p then Some p else None
| Relative p ->
let leaf = basename p in
let ambiguous =
leaf <> "." && leaf <> ".." && String.contains leaf '.' &&
String.for_all (fun c -> c = '.' || c = ' ') leaf
in
if p = "" || String.contains p '/' || ambiguous then None
else match classify p with
| `Relative when is_relative parent -> relative (join parent p)
| (`Relative | `Rooted as kind) when not (is_relative parent) ->
let vol, base = split_volume (to_win32 parent) in
let base = if kind = `Rooted then "" else base in
Option.map (fun rest -> qualify (vol ^ "\\" ^ rest)) (relative_components (base ^ "\\" ^ p))
| _ -> None
in
match root, resolved with
| Some root, Some p when not (is_relative p) -> beneath ~root p
| _, result -> result