contrib/libc++/src/experimental/filesystem/path.cpp

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