1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include <__config>
10#include <filesystem>
11#include <vector>
12
13#include "error.h"
14#include "path_parser.h"
15
16_LIBCPP_BEGIN_NAMESPACE_FILESYSTEM
17_LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS
18
19using detail::ErrorHandler;
20using parser::createView;
21using parser::PathParser;
22using parser::string_view_t;
23
24///////////////////////////////////////////////////////////////////////////////
25// path definitions
26///////////////////////////////////////////////////////////////////////////////
27
28_LIBCPP_DIAGNOSTIC_PUSH
29_LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wdeprecated")
30constexpr path::value_type path::preferred_separator;
31_LIBCPP_DIAGNOSTIC_POP
32
33path& path::replace_extension(path const& replacement) {
34 path p = extension();
35 if (not p.empty()) {
36 __pn_.erase(pos: __pn_.size() - p.native().size());
37 }
38 if (!replacement.empty()) {
39 if (replacement.native()[0] != '.') {
40 __pn_ += PATHSTR(".");
41 }
42 __pn_.append(str: replacement.__pn_);
43 }
44 return *this;
45}
46
47///////////////////////////////////////////////////////////////////////////////
48// path.decompose
49
50string_view_t path::__root_name() const {
51 auto PP = PathParser::CreateBegin(P: __pn_);
52 if (PP.State_ == PathParser::PS_InRootName)
53 return *PP;
54 return {};
55}
56
57string_view_t path::__root_directory() const {
58 auto PP = PathParser::CreateBegin(P: __pn_);
59 if (PP.State_ == PathParser::PS_InRootName)
60 ++PP;
61 if (PP.State_ == PathParser::PS_InRootDir)
62 return *PP;
63 return {};
64}
65
66string_view_t path::__root_path_raw() const {
67 auto PP = PathParser::CreateBegin(P: __pn_);
68 if (PP.State_ == PathParser::PS_InRootName) {
69 auto NextCh = PP.peek();
70 if (NextCh && isSeparator(C: *NextCh)) {
71 ++PP;
72 return createView(S: __pn_.data(), E: &PP.RawEntry.back());
73 }
74 return PP.RawEntry;
75 }
76 if (PP.State_ == PathParser::PS_InRootDir)
77 return *PP;
78 return {};
79}
80
81static bool ConsumeRootName(PathParser* PP) {
82 static_assert(PathParser::PS_BeforeBegin == 1 && PathParser::PS_InRootName == 2, "Values for enums are incorrect");
83 while (PP->State_ <= PathParser::PS_InRootName)
84 ++(*PP);
85 return PP->State_ == PathParser::PS_AtEnd;
86}
87
88static bool ConsumeRootDir(PathParser* PP) {
89 static_assert(PathParser::PS_BeforeBegin == 1 && PathParser::PS_InRootName == 2 && PathParser::PS_InRootDir == 3,
90 "Values for enums are incorrect");
91 while (PP->State_ <= PathParser::PS_InRootDir)
92 ++(*PP);
93 return PP->State_ == PathParser::PS_AtEnd;
94}
95
96string_view_t path::__relative_path() const {
97 auto PP = PathParser::CreateBegin(P: __pn_);
98 if (ConsumeRootDir(PP: &PP))
99 return {};
100 return createView(S: PP.RawEntry.data(), E: &__pn_.back());
101}
102
103string_view_t path::__parent_path() const {
104 if (empty())
105 return {};
106 // Determine if we have a root path but not a relative path. In that case
107 // return *this.
108 {
109 auto PP = PathParser::CreateBegin(P: __pn_);
110 if (ConsumeRootDir(PP: &PP))
111 return __pn_;
112 }
113 // Otherwise remove a single element from the end of the path, and return
114 // a string representing that path
115 {
116 auto PP = PathParser::CreateEnd(P: __pn_);
117 --PP;
118 if (PP.RawEntry.data() == __pn_.data())
119 return {};
120 --PP;
121 return createView(S: __pn_.data(), E: &PP.RawEntry.back());
122 }
123}
124
125string_view_t path::__filename() const {
126 if (empty())
127 return {};
128 {
129 PathParser PP = PathParser::CreateBegin(P: __pn_);
130 if (ConsumeRootDir(PP: &PP))
131 return {};
132 }
133 return *(--PathParser::CreateEnd(P: __pn_));
134}
135
136string_view_t path::__stem() const { return parser::separate_filename(s: __filename()).first; }
137
138string_view_t path::__extension() const { return parser::separate_filename(s: __filename()).second; }
139
140////////////////////////////////////////////////////////////////////////////
141// path.gen
142
143enum PathPartKind : unsigned char { PK_None, PK_RootName, PK_RootSep, PK_Filename, PK_Dot, PK_DotDot, PK_TrailingSep };
144
145static PathPartKind ClassifyPathPart(const PathParser& PP) {
146 if (PP.inRootName())
147 return PK_RootName;
148 if (PP.inRootDir())
149 return PK_RootSep;
150 string_view_t Part = *PP;
151 if (Part.empty())
152 return PK_TrailingSep;
153 if (Part == PATHSTR("."))
154 return PK_Dot;
155 if (Part == PATHSTR(".."))
156 return PK_DotDot;
157 return PK_Filename;
158}
159
160path path::lexically_normal() const {
161 if (__pn_.empty())
162 return *this;
163
164 using PartKindPair = pair<string_view_t, PathPartKind>;
165 vector<PartKindPair> Parts;
166 // Guess as to how many elements the path has to avoid reallocating.
167 Parts.reserve(n: 32);
168
169 // Track the total size of the parts as we collect them. This allows the
170 // resulting path to reserve the correct amount of memory.
171 size_t NewPathSize = 0;
172 auto AddPart = [&](PathPartKind K, string_view_t P) {
173 NewPathSize += P.size();
174 Parts.emplace_back(args&: P, args&: K);
175 };
176 auto LastPartKind = [&]() {
177 if (Parts.empty())
178 return PK_None;
179 return Parts.back().second;
180 };
181
182 bool MaybeNeedTrailingSep = false;
183 // Build a stack containing the remaining elements of the path, popping off
184 // elements which occur before a '..' entry.
185 for (auto PP = PathParser::CreateBegin(P: __pn_); PP; ++PP) {
186 PathPartKind Kind = ClassifyPathPart(PP);
187 switch (Kind) {
188 case PK_Filename:
189 case PK_RootName:
190 case PK_RootSep: {
191 // Add all non-dot and non-dot-dot elements to the stack of elements.
192 AddPart(Kind, *PP);
193 MaybeNeedTrailingSep = false;
194 break;
195 }
196 case PK_DotDot: {
197 // Only push a ".." element if there are no elements preceding the "..",
198 // or if the preceding element is itself "..".
199 auto LastKind = LastPartKind();
200 if (LastKind == PK_Filename) {
201 NewPathSize -= Parts.back().first.size();
202 Parts.pop_back();
203 } else if (LastKind != PK_RootSep)
204 AddPart(PK_DotDot, PATHSTR(".."));
205 MaybeNeedTrailingSep = LastKind == PK_Filename;
206 break;
207 }
208 case PK_Dot:
209 case PK_TrailingSep: {
210 MaybeNeedTrailingSep = true;
211 break;
212 }
213 case PK_None:
214 __libcpp_unreachable();
215 }
216 }
217 // [fs.path.generic]p6.8: If the path is empty, add a dot.
218 if (Parts.empty())
219 return PATHSTR(".");
220
221 // [fs.path.generic]p6.7: If the last filename is dot-dot, remove any
222 // trailing directory-separator.
223 bool NeedTrailingSep = MaybeNeedTrailingSep && LastPartKind() == PK_Filename;
224
225 path Result;
226 Result.__pn_.reserve(requested_capacity: Parts.size() + NewPathSize + NeedTrailingSep);
227 for (auto& PK : Parts)
228 Result /= PK.first;
229
230 if (NeedTrailingSep)
231 Result /= PATHSTR("");
232
233 Result.make_preferred();
234 return Result;
235}
236
237static int DetermineLexicalElementCount(PathParser PP) {
238 int Count = 0;
239 for (; PP; ++PP) {
240 auto Elem = *PP;
241 if (Elem == PATHSTR(".."))
242 --Count;
243 else if (Elem != PATHSTR(".") && Elem != PATHSTR(""))
244 ++Count;
245 }
246 return Count;
247}
248
249path path::lexically_relative(const path& base) const {
250 { // perform root-name/root-directory mismatch checks
251 auto PP = PathParser::CreateBegin(P: __pn_);
252 auto PPBase = PathParser::CreateBegin(P: base.__pn_);
253 auto CheckIterMismatchAtBase = [&]() {
254 return PP.State_ != PPBase.State_ && (PP.inRootPath() || PPBase.inRootPath());
255 };
256 if (PP.inRootName() && PPBase.inRootName()) {
257 if (*PP != *PPBase)
258 return {};
259 } else if (CheckIterMismatchAtBase())
260 return {};
261
262 if (PP.inRootPath())
263 ++PP;
264 if (PPBase.inRootPath())
265 ++PPBase;
266 if (CheckIterMismatchAtBase())
267 return {};
268 }
269
270 // Find the first mismatching element
271 auto PP = PathParser::CreateBegin(P: __pn_);
272 auto PPBase = PathParser::CreateBegin(P: base.__pn_);
273 while (PP && PPBase && PP.State_ == PPBase.State_ && (*PP == *PPBase || PP.inRootDir())) {
274 ++PP;
275 ++PPBase;
276 }
277
278 // If there is no mismatch, return ".".
279 if (!PP && !PPBase)
280 return ".";
281
282 // Otherwise, determine the number of elements, 'n', which are not dot or
283 // dot-dot minus the number of dot-dot elements.
284 int ElemCount = DetermineLexicalElementCount(PP: PPBase);
285 if (ElemCount < 0)
286 return {};
287
288 // if n == 0 and (a == end() || a->empty()), returns path("."); otherwise
289 if (ElemCount == 0 && (PP.atEnd() || *PP == PATHSTR("")))
290 return PATHSTR(".");
291
292 // return a path constructed with 'n' dot-dot elements, followed by the
293 // elements of '*this' after the mismatch.
294 path Result;
295 constexpr size_t ElemSize = 2; // ".."
296 constexpr size_t SeparatorSize = 1; // separator is always a single char
297 Result.__reserve(s: ElemCount * (ElemSize + SeparatorSize) + SeparatorSize + PP.Path.size());
298 while (ElemCount--)
299 Result /= PATHSTR("..");
300 for (; PP; ++PP)
301 Result /= *PP;
302 return Result;
303}
304
305////////////////////////////////////////////////////////////////////////////
306// path.comparisons
307static int CompareRootName(PathParser* LHS, PathParser* RHS) {
308 if (!LHS->inRootName() && !RHS->inRootName())
309 return 0;
310
311 auto GetRootName = [](PathParser* Parser) -> string_view_t { return Parser->inRootName() ? **Parser : PATHSTR(""); };
312 int res = GetRootName(LHS).compare(sv: GetRootName(RHS));
313 ConsumeRootName(PP: LHS);
314 ConsumeRootName(PP: RHS);
315 return res;
316}
317
318static int CompareRootDir(PathParser* LHS, PathParser* RHS) {
319 if (!LHS->inRootDir() && RHS->inRootDir())
320 return -1;
321 else if (LHS->inRootDir() && !RHS->inRootDir())
322 return 1;
323 else {
324 ConsumeRootDir(PP: LHS);
325 ConsumeRootDir(PP: RHS);
326 return 0;
327 }
328}
329
330static int CompareRelative(PathParser* LHSPtr, PathParser* RHSPtr) {
331 auto& LHS = *LHSPtr;
332 auto& RHS = *RHSPtr;
333
334 int res;
335 while (LHS && RHS) {
336 if ((res = (*LHS).compare(sv: *RHS)) != 0)
337 return res;
338 ++LHS;
339 ++RHS;
340 }
341 return 0;
342}
343
344static int CompareEndState(PathParser* LHS, PathParser* RHS) {
345 if (LHS->atEnd() && !RHS->atEnd())
346 return -1;
347 else if (!LHS->atEnd() && RHS->atEnd())
348 return 1;
349 return 0;
350}
351
352int path::__compare(string_view_t __s) const {
353 auto LHS = PathParser::CreateBegin(P: __pn_);
354 auto RHS = PathParser::CreateBegin(P: __s);
355 int res;
356
357 if ((res = CompareRootName(LHS: &LHS, RHS: &RHS)) != 0)
358 return res;
359
360 if ((res = CompareRootDir(LHS: &LHS, RHS: &RHS)) != 0)
361 return res;
362
363 if ((res = CompareRelative(LHSPtr: &LHS, RHSPtr: &RHS)) != 0)
364 return res;
365
366 return CompareEndState(LHS: &LHS, RHS: &RHS);
367}
368
369////////////////////////////////////////////////////////////////////////////
370// path.nonmembers
371size_t hash_value(const path& __p) noexcept {
372 auto PP = PathParser::CreateBegin(P: __p.native());
373 size_t hash_value = 0;
374 hash<string_view_t> hasher;
375 while (PP) {
376 string_view_t Part = PP.inRootDir() ? PATHSTR("/") : *PP;
377 hash_value = __hash_combine(lhs: hash_value, rhs: hasher(Part));
378 ++PP;
379 }
380 return hash_value;
381}
382
383////////////////////////////////////////////////////////////////////////////
384// path.itr
385path::iterator path::begin() const {
386 auto PP = PathParser::CreateBegin(P: __pn_);
387 iterator it;
388 it.__path_ptr_ = this;
389 it.__state_ = static_cast<path::iterator::_ParserState>(PP.State_);
390 it.__entry_ = PP.RawEntry;
391 it.__stashed_elem_.__assign_view(s: *PP);
392 return it;
393}
394
395path::iterator path::end() const {
396 iterator it{};
397 it.__state_ = path::iterator::_AtEnd;
398 it.__path_ptr_ = this;
399 return it;
400}
401
402path::iterator& path::iterator::__increment() {
403 PathParser PP(__path_ptr_->native(), __entry_, __state_);
404 ++PP;
405 __state_ = static_cast<_ParserState>(PP.State_);
406 __entry_ = PP.RawEntry;
407 __stashed_elem_.__assign_view(s: *PP);
408 return *this;
409}
410
411path::iterator& path::iterator::__decrement() {
412 PathParser PP(__path_ptr_->native(), __entry_, __state_);
413 --PP;
414 __state_ = static_cast<_ParserState>(PP.State_);
415 __entry_ = PP.RawEntry;
416 __stashed_elem_.__assign_view(s: *PP);
417 return *this;
418}
419
420#if defined(_LIBCPP_WIN32API)
421////////////////////////////////////////////////////////////////////////////
422// Windows path conversions
423size_t __wide_to_char(const wstring& str, char* out, size_t outlen) {
424 if (str.empty())
425 return 0;
426 ErrorHandler<size_t> err("__wide_to_char", nullptr);
427 UINT codepage = AreFileApisANSI() ? CP_ACP : CP_OEMCP;
428 BOOL used_default = FALSE;
429 int ret = WideCharToMultiByte(codepage, 0, str.data(), str.size(), out, outlen, nullptr, &used_default);
430 if (ret <= 0 || used_default)
431 return err.report(errc::illegal_byte_sequence);
432 return ret;
433}
434
435size_t __char_to_wide(const string& str, wchar_t* out, size_t outlen) {
436 if (str.empty())
437 return 0;
438 ErrorHandler<size_t> err("__char_to_wide", nullptr);
439 UINT codepage = AreFileApisANSI() ? CP_ACP : CP_OEMCP;
440 int ret = MultiByteToWideChar(codepage, MB_ERR_INVALID_CHARS, str.data(), str.size(), out, outlen);
441 if (ret <= 0)
442 return err.report(errc::illegal_byte_sequence);
443 return ret;
444}
445#endif
446
447_LIBCPP_END_EXPLICIT_ABI_ANNOTATIONS
448_LIBCPP_END_NAMESPACE_FILESYSTEM
449