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