1 //===--------------------- filesystem/path.cpp ----------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 #include "experimental/filesystem" 10 #include "string_view" 11 #include "utility" 12 13 namespace { namespace parser 14 { 15 using namespace std; 16 using namespace std::experimental::filesystem; 17 18 using string_view_t = path::__string_view; 19 using string_view_pair = pair<string_view_t, string_view_t>; 20 using PosPtr = path::value_type const*; 21 22 struct PathParser { 23 enum ParserState : unsigned char { 24 // Zero is a special sentinel value used by default constructed iterators. 25 PS_BeforeBegin = 1, 26 PS_InRootName, 27 PS_InRootDir, 28 PS_InFilenames, 29 PS_InTrailingSep, 30 PS_AtEnd 31 }; 32 33 const string_view_t Path; 34 string_view_t RawEntry; 35 ParserState State; 36 37 private: 38 PathParser(string_view_t P, ParserState State) noexcept 39 : Path(P), State(State) {} 40 41 public: 42 PathParser(string_view_t P, string_view_t E, unsigned char S) 43 : Path(P), RawEntry(E), State(static_cast<ParserState>(S)) { 44 // S cannot be '0' or PS_BeforeBegin. 45 } 46 47 static PathParser CreateBegin(string_view_t P) noexcept { 48 PathParser PP(P, PS_BeforeBegin); 49 PP.increment(); 50 return PP; 51 } 52 53 static PathParser CreateEnd(string_view_t P) noexcept { 54 PathParser PP(P, PS_AtEnd); 55 return PP; 56 } 57 58 PosPtr peek() const noexcept { 59 auto TkEnd = getNextTokenStartPos(); 60 auto End = getAfterBack(); 61 return TkEnd == End ? nullptr : TkEnd; 62 } 63 64 void increment() noexcept { 65 const PosPtr End = getAfterBack(); 66 const PosPtr Start = getNextTokenStartPos(); 67 if (Start == End) 68 return makeState(PS_AtEnd); 69 70 switch (State) { 71 case PS_BeforeBegin: { 72 PosPtr TkEnd = consumeSeparator(Start, End); 73 // If we consumed exactly two separators we have a root name. 74 if (TkEnd && TkEnd == Start + 2) { 75 // FIXME Do we need to consume a name or is '//' a root name on its own? 76 // what about '//.', '//..', '//...'? 77 auto NameEnd = consumeName(TkEnd, End); 78 if (NameEnd) 79 TkEnd = NameEnd; 80 return makeState(PS_InRootName, Start, TkEnd); 81 } 82 else if (TkEnd) 83 return makeState(PS_InRootDir, Start, TkEnd); 84 else 85 return makeState(PS_InFilenames, Start, consumeName(Start, End)); 86 } 87 88 case PS_InRootName: 89 return makeState(PS_InRootDir, Start, consumeSeparator(Start, End)); 90 case PS_InRootDir: 91 return makeState(PS_InFilenames, Start, consumeName(Start, End)); 92 93 case PS_InFilenames: { 94 PosPtr SepEnd = consumeSeparator(Start, End); 95 if (SepEnd != End) { 96 PosPtr TkEnd = consumeName(SepEnd, End); 97 if (TkEnd) 98 return makeState(PS_InFilenames, SepEnd, TkEnd); 99 } 100 return makeState(PS_InTrailingSep, Start, SepEnd); 101 } 102 103 case PS_InTrailingSep: 104 return makeState(PS_AtEnd); 105 106 case PS_AtEnd: 107 _LIBCPP_UNREACHABLE(); 108 } 109 } 110 111 void decrement() noexcept { 112 const PosPtr REnd = getBeforeFront(); 113 const PosPtr RStart = getCurrentTokenStartPos() - 1; 114 115 switch (State) { 116 case PS_AtEnd: { 117 // Try to consume a trailing separator or root directory first. 118 if (PosPtr SepEnd = consumeSeparator(RStart, REnd)) { 119 if (SepEnd == REnd) 120 return makeState((RStart == REnd + 2) ? PS_InRootName : PS_InRootDir, 121 Path.data(), RStart + 1); 122 // Check if we're seeing the root directory separator 123 auto PP = CreateBegin(Path); 124 bool InRootDir = PP.State == PS_InRootName && 125 &PP.RawEntry.back() == SepEnd; 126 return makeState(InRootDir ? PS_InRootDir : PS_InTrailingSep, 127 SepEnd + 1, RStart + 1); 128 } else { 129 PosPtr TkStart = consumeName(RStart, REnd); 130 if (TkStart == REnd + 2 && consumeSeparator(TkStart, REnd) == REnd) 131 return makeState(PS_InRootName, Path.data(), RStart + 1); 132 else 133 return makeState(PS_InFilenames, TkStart + 1, RStart + 1); 134 } 135 } 136 case PS_InTrailingSep: 137 return makeState(PS_InFilenames, consumeName(RStart, REnd) + 1, RStart + 1); 138 case PS_InFilenames: { 139 PosPtr SepEnd = consumeSeparator(RStart, REnd); 140 if (SepEnd == REnd) 141 return makeState((RStart == REnd + 2) ? PS_InRootName : PS_InRootDir, 142 Path.data(), RStart + 1); 143 PosPtr TkEnd = consumeName(SepEnd, REnd); 144 if (TkEnd == REnd + 2 && consumeSeparator(TkEnd, REnd) == REnd) 145 return makeState(PS_InRootDir, SepEnd + 1, RStart + 1); 146 return makeState(PS_InFilenames, TkEnd + 1, SepEnd + 1); 147 } 148 case PS_InRootDir: 149 return makeState(PS_InRootName, Path.data(), RStart + 1); 150 case PS_InRootName: 151 case PS_BeforeBegin: 152 _LIBCPP_UNREACHABLE(); 153 } 154 } 155 156 /// \brief Return a view with the "preferred representation" of the current 157 /// element. For example trailing separators are represented as a '.' 158 string_view_t operator*() const noexcept { 159 switch (State) { 160 case PS_BeforeBegin: 161 case PS_AtEnd: 162 return ""; 163 case PS_InRootDir: 164 return "/"; 165 case PS_InTrailingSep: 166 return "."; 167 case PS_InRootName: 168 case PS_InFilenames: 169 return RawEntry; 170 } 171 _LIBCPP_UNREACHABLE(); 172 } 173 174 explicit operator bool() const noexcept { 175 return State != PS_BeforeBegin && State != PS_AtEnd; 176 } 177 178 PathParser& operator++() noexcept { 179 increment(); 180 return *this; 181 } 182 183 PathParser& operator--() noexcept { 184 decrement(); 185 return *this; 186 } 187 188 private: 189 void makeState(ParserState NewState, PosPtr Start, PosPtr End) noexcept { 190 State = NewState; 191 RawEntry = string_view_t(Start, End - Start); 192 } 193 void makeState(ParserState NewState) noexcept { 194 State = NewState; 195 RawEntry = {}; 196 } 197 198 PosPtr getAfterBack() const noexcept { 199 return Path.data() + Path.size(); 200 } 201 202 PosPtr getBeforeFront() const noexcept { 203 return Path.data() - 1; 204 } 205 206 /// \brief Return a pointer to the first character after the currently 207 /// lexed element. 208 PosPtr getNextTokenStartPos() const noexcept { 209 switch (State) { 210 case PS_BeforeBegin: 211 return Path.data(); 212 case PS_InRootName: 213 case PS_InRootDir: 214 case PS_InFilenames: 215 return &RawEntry.back() + 1; 216 case PS_InTrailingSep: 217 case PS_AtEnd: 218 return getAfterBack(); 219 } 220 _LIBCPP_UNREACHABLE(); 221 } 222 223 /// \brief Return a pointer to the first character in the currently lexed 224 /// element. 225 PosPtr getCurrentTokenStartPos() const noexcept { 226 switch (State) { 227 case PS_BeforeBegin: 228 case PS_InRootName: 229 return &Path.front(); 230 case PS_InRootDir: 231 case PS_InFilenames: 232 case PS_InTrailingSep: 233 return &RawEntry.front(); 234 case PS_AtEnd: 235 return &Path.back() + 1; 236 } 237 _LIBCPP_UNREACHABLE(); 238 } 239 240 PosPtr consumeSeparator(PosPtr P, PosPtr End) const noexcept { 241 if (P == End || *P != '/') 242 return nullptr; 243 const int Inc = P < End ? 1 : -1; 244 P += Inc; 245 while (P != End && *P == '/') 246 P += Inc; 247 return P; 248 } 249 250 PosPtr consumeName(PosPtr P, PosPtr End) const noexcept { 251 if (P == End || *P == '/') 252 return nullptr; 253 const int Inc = P < End ? 1 : -1; 254 P += Inc; 255 while (P != End && *P != '/') 256 P += Inc; 257 return P; 258 } 259 }; 260 261 string_view_pair separate_filename(string_view_t const & s) { 262 if (s == "." || s == ".." || s.empty()) return string_view_pair{s, ""}; 263 auto pos = s.find_last_of('.'); 264 if (pos == string_view_t::npos) return string_view_pair{s, string_view{}}; 265 return string_view_pair{s.substr(0, pos), s.substr(pos)}; 266 } 267 268 string_view_t createView(PosPtr S, PosPtr E) noexcept { 269 return {S, static_cast<size_t>(E - S) + 1}; 270 } 271 272 }} // namespace parser 273 274 _LIBCPP_BEGIN_NAMESPACE_EXPERIMENTAL_FILESYSTEM 275 276 using parser::string_view_t; 277 using parser::string_view_pair; 278 using parser::PathParser; 279 using parser::createView; 280 281 /////////////////////////////////////////////////////////////////////////////// 282 // path definitions 283 /////////////////////////////////////////////////////////////////////////////// 284 285 constexpr path::value_type path::preferred_separator; 286 287 path & path::replace_extension(path const & replacement) 288 { 289 path p = extension(); 290 if (not p.empty()) { 291 __pn_.erase(__pn_.size() - p.native().size()); 292 } 293 if (!replacement.empty()) { 294 if (replacement.native()[0] != '.') { 295 __pn_ += "."; 296 } 297 __pn_.append(replacement.__pn_); 298 } 299 return *this; 300 } 301 302 /////////////////////////////////////////////////////////////////////////////// 303 // path.decompose 304 305 string_view_t path::__root_name() const 306 { 307 auto PP = PathParser::CreateBegin(__pn_); 308 if (PP.State == PathParser::PS_InRootName) 309 return *PP; 310 return {}; 311 } 312 313 string_view_t path::__root_directory() const 314 { 315 auto PP = PathParser::CreateBegin(__pn_); 316 if (PP.State == PathParser::PS_InRootName) 317 ++PP; 318 if (PP.State == PathParser::PS_InRootDir) 319 return *PP; 320 return {}; 321 } 322 323 string_view_t path::__root_path_raw() const 324 { 325 auto PP = PathParser::CreateBegin(__pn_); 326 if (PP.State == PathParser::PS_InRootName) { 327 auto NextCh = PP.peek(); 328 if (NextCh && *NextCh == '/') { 329 ++PP; 330 return createView(__pn_.data(), &PP.RawEntry.back()); 331 } 332 return PP.RawEntry; 333 } 334 if (PP.State == PathParser::PS_InRootDir) 335 return *PP; 336 return {}; 337 } 338 339 string_view_t path::__relative_path() const 340 { 341 auto PP = PathParser::CreateBegin(__pn_); 342 while (PP.State <= PathParser::PS_InRootDir) 343 ++PP; 344 if (PP.State == PathParser::PS_AtEnd) 345 return {}; 346 return createView(PP.RawEntry.data(), &__pn_.back()); 347 } 348 349 string_view_t path::__parent_path() const 350 { 351 if (empty()) 352 return {}; 353 auto PP = PathParser::CreateEnd(__pn_); 354 --PP; 355 if (PP.RawEntry.data() == __pn_.data()) 356 return {}; 357 --PP; 358 return createView(__pn_.data(), &PP.RawEntry.back()); 359 } 360 361 string_view_t path::__filename() const 362 { 363 if (empty()) return {}; 364 return *(--PathParser::CreateEnd(__pn_)); 365 } 366 367 string_view_t path::__stem() const 368 { 369 return parser::separate_filename(__filename()).first; 370 } 371 372 string_view_t path::__extension() const 373 { 374 return parser::separate_filename(__filename()).second; 375 } 376 377 //////////////////////////////////////////////////////////////////////////// 378 // path.comparisons 379 int path::__compare(string_view_t __s) const { 380 auto PP = PathParser::CreateBegin(__pn_); 381 auto PP2 = PathParser::CreateBegin(__s); 382 while (PP && PP2) { 383 int res = (*PP).compare(*PP2); 384 if (res != 0) return res; 385 ++PP; ++PP2; 386 } 387 if (PP.State == PP2.State && PP.State == PathParser::PS_AtEnd) 388 return 0; 389 if (PP.State == PathParser::PS_AtEnd) 390 return -1; 391 return 1; 392 } 393 394 //////////////////////////////////////////////////////////////////////////// 395 // path.nonmembers 396 size_t hash_value(const path& __p) noexcept { 397 auto PP = PathParser::CreateBegin(__p.native()); 398 size_t hash_value = 0; 399 std::hash<string_view> hasher; 400 while (PP) { 401 hash_value = __hash_combine(hash_value, hasher(*PP)); 402 ++PP; 403 } 404 return hash_value; 405 } 406 407 //////////////////////////////////////////////////////////////////////////// 408 // path.itr 409 path::iterator path::begin() const 410 { 411 auto PP = PathParser::CreateBegin(__pn_); 412 iterator it; 413 it.__path_ptr_ = this; 414 it.__state_ = PP.State; 415 it.__entry_ = PP.RawEntry; 416 it.__stashed_elem_.__assign_view(*PP); 417 return it; 418 } 419 420 path::iterator path::end() const 421 { 422 iterator it{}; 423 it.__state_ = PathParser::PS_AtEnd; 424 it.__path_ptr_ = this; 425 return it; 426 } 427 428 path::iterator& path::iterator::__increment() { 429 static_assert(__at_end == PathParser::PS_AtEnd, ""); 430 PathParser PP(__path_ptr_->native(), __entry_, __state_); 431 ++PP; 432 __state_ = PP.State; 433 __entry_ = PP.RawEntry; 434 __stashed_elem_.__assign_view(*PP); 435 return *this; 436 } 437 438 path::iterator& path::iterator::__decrement() { 439 PathParser PP(__path_ptr_->native(), __entry_, __state_); 440 --PP; 441 __state_ = PP.State; 442 __entry_ = PP.RawEntry; 443 __stashed_elem_.__assign_view(*PP); 444 return *this; 445 } 446 447 _LIBCPP_END_NAMESPACE_EXPERIMENTAL_FILESYSTEM 448