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 #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