libstdc++-v3/src/c++17/fs_path.cc

   1 // Class filesystem::path -*- C++ -*-
   2
   3 // Copyright (C) 2014-2019 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 #ifndef _GLIBCXX_USE_CXX11_ABI
  26 # define _GLIBCXX_USE_CXX11_ABI 1
  27 #endif
  28
  29 #ifdef __CYGWIN__
  30 // Interpret "//x" as a root-name, not root-dir + filename
  31 # define SLASHSLASH_IS_ROOTNAME 1
  32 #endif
  33
  34 #include <filesystem>
  35 #include <algorithm>
  36 #include <bits/stl_uninitialized.h>
  37
  38 namespace fs = std::filesystem;
  39 using fs::path;
  40
  41 static inline bool is_dir_sep(path::value_type ch)
  42 {
  43 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  44     return ch == L'/' || ch == path::preferred_separator;
  45 #else
  46     return ch == '/';
  47 #endif
  48 }
  49
  50 struct path::_Parser
  51 {
  52   using string_view_type = std::basic_string_view<value_type>;
  53
  54   struct cmpt
  55   {
  56     string_view_type str;
  57     _Type type = _Type::_Multi;
  58
  59     bool valid() const { return type != _Type::_Multi; }
  60   };
  61
  62   string_view_type input;
  63   string_view_type::size_type pos = 0;
  64   size_t origin;
  65   _Type last_type = _Type::_Multi;
  66
  67   _Parser(string_view_type s, size_t o = 0) : input(s), origin(o) { }
  68
  69   pair<cmpt, cmpt> root_path() noexcept
  70   {
  71     pos = 0;
  72     pair<cmpt, cmpt> root;
  73
  74     const size_t len = input.size();
  75
  76     // look for root name or root directory
  77     if (is_dir_sep(input[0]))
  78       {
  79 #if SLASHSLASH_IS_ROOTNAME
  80         // look for root name, such as "//foo"
  81         if (len > 2 && input[1] == input[0])
  82           {
  83             if (!is_dir_sep(input[2]))
  84               {
  85                 // got root name, find its end
  86                 pos = 3;
  87                 while (pos < len && !is_dir_sep(input[pos]))
  88                   ++pos;
  89                 root.first.str = input.substr(0, pos);
  90                 root.first.type = _Type::_Root_name;
  91
  92                 if (pos < len) // also got root directory
  93                   {
  94                     root.second.str = input.substr(pos, 1);
  95                     root.second.type = _Type::_Root_dir;
  96                     ++pos;
  97                   }
  98               }
  99             else
 100               {
 101                 // got something like "///foo" which is just a root directory
 102                 // composed of multiple redundant directory separators
 103                 root.first.str = input.substr(0, 1);
 104                 root.first.type = _Type::_Root_dir;
 105                 pos += 2;
 106               }
 107           }
 108         else
 109 #endif
 110           {
 111             root.first.str = input.substr(0, 1);
 112             root.first.type = _Type::_Root_dir;
 113             ++pos;
 114           }
 115         // Find the start of the first filename
 116         while (pos < len && is_dir_sep(input[pos]))
 117           ++pos;
 118       }
 119 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 120     else if (len > 1 && input[1] == L':')
 121       {
 122         // got disk designator
 123         root.first.str = input.substr(0, 2);
 124         root.first.type = _Type::_Root_name;
 125         if (len > 2 && is_dir_sep(input[2]))
 126           {
 127             root.second.str = input.substr(2, 1);
 128             root.second.type = _Type::_Root_dir;
 129           }
 130         pos = input.find_first_not_of(L"/\\", 2);
 131       }
 132 #endif
 133
 134     if (root.second.valid())
 135       last_type = root.second.type;
 136     else
 137       last_type = root.first.type;
 138
 139     return root;
 140   }
 141
 142   cmpt next() noexcept
 143   {
 144 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 145     string_view_type sep = L"/\\";
 146 #else
 147     char sep = '/';
 148 #endif
 149
 150     const int last_pos = pos;
 151
 152     cmpt f;
 153     if (pos != input.npos)
 154       {
 155         pos = input.find_first_not_of(sep, pos);
 156         if (pos != input.npos)
 157           {
 158             const auto end = input.find_first_of(sep, pos);
 159             f.str = input.substr(pos, end - pos);
 160             f.type = _Type::_Filename;
 161             pos = end;
 162           }
 163         else if (last_type == _Type::_Filename
 164             || (last_pos == 0 && !input.empty()))
 165           {
 166             // [fs.path.itr]/4 An empty element, if trailing non-root
 167             // directory-separator present.
 168             __glibcxx_assert(is_dir_sep(input.back()));
 169             f.str = input.substr(input.length(), 0);
 170             f.type = _Type::_Filename;
 171           }
 172       }
 173     last_type = f.type;
 174     return f;
 175   }
 176
 177   string_view_type::size_type
 178   offset(const cmpt& c) const noexcept
 179   { return origin + c.str.data() - input.data(); }
 180 };
 181
 182 struct path::_List::_Impl
 183 {
 184   using value_type = _Cmpt;
 185
 186   _Impl(int cap) : _M_size(0), _M_capacity(cap) { }
 187
 188   alignas(value_type) int _M_size;
 189   int _M_capacity;
 190
 191   using iterator = value_type*;
 192   using const_iterator = const value_type*;
 193
 194   iterator begin() { return reinterpret_cast<value_type*>(this + 1); }
 195   iterator end() { return begin() + size(); }
 196
 197   const_iterator begin() const
 198   { return reinterpret_cast<const value_type*>(this + 1); }
 199   const_iterator end() const { return begin() + size(); }
 200
 201   const value_type& front() const { return *begin(); }
 202   const value_type& back() const { return end()[-1]; }
 203
 204   int size() const { return _M_size; }
 205   int capacity() const { return _M_capacity; }
 206   bool empty() const { return _M_size == 0; }
 207
 208   void clear() { std::destroy_n(begin(), _M_size); _M_size = 0; }
 209
 210   void pop_back()
 211   {
 212     back().~_Cmpt();
 213     --_M_size;
 214   }
 215
 216   void _M_erase_from(const_iterator pos)
 217   {
 218     iterator first = begin() + (pos - begin());
 219     iterator last = end();
 220     std::destroy(first, last);
 221     _M_size -= last - first;
 222   }
 223
 224   unique_ptr<_Impl, _Impl_deleter> copy() const
 225   {
 226     const auto n = size();
 227     void* p = ::operator new(sizeof(_Impl) + n * sizeof(value_type));
 228     unique_ptr<_Impl, _Impl_deleter> newptr(::new (p) _Impl{n});
 229     std::uninitialized_copy_n(begin(), n, newptr->begin());
 230     newptr->_M_size = n;
 231     return newptr;
 232   }
 233
 234   // Clear the lowest two bits from the pointer (i.e. remove the _Type value)
 235   static _Impl* notype(_Impl* p)
 236   {
 237     constexpr uintptr_t mask = ~(uintptr_t)0x3;
 238     return reinterpret_cast<_Impl*>(reinterpret_cast<uintptr_t>(p) & mask);
 239   }
 240 };
 241
 242 void path::_List::_Impl_deleter::operator()(_Impl* p) const noexcept
 243 {
 244   p = _Impl::notype(p);
 245   if (p)
 246     {
 247       __glibcxx_assert(p->_M_size <= p->_M_capacity);
 248       p->clear();
 249       ::operator delete(p, sizeof(*p) + p->_M_capacity * sizeof(value_type));
 250     }
 251 }
 252
 253 path::_List::_List() : _M_impl(reinterpret_cast<_Impl*>(_Type::_Filename)) { }
 254
 255 path::_List::_List(const _List& other)
 256 {
 257   if (!other.empty())
 258     _M_impl = other._M_impl->copy();
 259   else
 260     type(other.type());
 261 }
 262
 263 path::_List&
 264 path::_List::operator=(const _List& other)
 265 {
 266   if (!other.empty())
 267     {
 268       // copy in-place if there is capacity
 269       const int newsize = other._M_impl->size();
 270       auto impl = _Impl::notype(_M_impl.get());
 271       if (impl && impl->capacity() >= newsize)
 272         {
 273           const int oldsize = impl->_M_size;
 274           auto to = impl->begin();
 275           auto from = other._M_impl->begin();
 276           const int minsize = std::min(newsize, oldsize);
 277           for (int i = 0; i < minsize; ++i)
 278             to[i]._M_pathname.reserve(from[i]._M_pathname.length());
 279           if (newsize > oldsize)
 280             {
 281               std::uninitialized_copy_n(to + oldsize, newsize - oldsize,
 282                                         from + oldsize);
 283               impl->_M_size = newsize;
 284             }
 285           else if (newsize < oldsize)
 286             impl->_M_erase_from(impl->begin() + newsize);
 287           std::copy_n(from, minsize, to);
 288           type(_Type::_Multi);
 289         }
 290       else
 291         _M_impl = other._M_impl->copy();
 292     }
 293   else
 294     {
 295       clear();
 296       type(other.type());
 297     }
 298   return *this;
 299 }
 300
 301 inline void
 302 path::_List::type(_Type t) noexcept
 303 {
 304   auto val = reinterpret_cast<uintptr_t>(_Impl::notype(_M_impl.release()));
 305   _M_impl.reset(reinterpret_cast<_Impl*>(val | (unsigned char)t));
 306 }
 307
 308 inline int
 309 path::_List::size() const noexcept
 310 {
 311   if (auto* ptr = _Impl::notype(_M_impl.get()))
 312     return ptr->size();
 313   return 0;
 314 }
 315
 316 inline int
 317 path::_List::capacity() const noexcept
 318 {
 319   if (auto* ptr = _Impl::notype(_M_impl.get()))
 320     return ptr->capacity();
 321   return 0;
 322 }
 323
 324 inline bool
 325 path::_List::empty() const noexcept
 326 {
 327   return size() == 0;
 328 }
 329
 330 inline auto
 331 path::_List::begin() noexcept
 332 -> iterator
 333 {
 334   __glibcxx_assert(!empty());
 335   if (auto* ptr = _Impl::notype(_M_impl.get()))
 336     return ptr->begin();
 337   return nullptr;
 338 }
 339
 340 inline auto
 341 path::_List::end() noexcept
 342 -> iterator
 343 {
 344   __glibcxx_assert(!empty());
 345   if (auto* ptr = _Impl::notype(_M_impl.get()))
 346     return ptr->end();
 347   return nullptr;
 348 }
 349
 350 auto
 351 path::_List::begin() const noexcept
 352 -> const_iterator
 353 {
 354   __glibcxx_assert(!empty());
 355   if (auto* ptr = _Impl::notype(_M_impl.get()))
 356     return ptr->begin();
 357   return nullptr;
 358 }
 359
 360 auto
 361 path::_List::end() const noexcept
 362 -> const_iterator
 363 {
 364   __glibcxx_assert(!empty());
 365   if (auto* ptr = _Impl::notype(_M_impl.get()))
 366     return ptr->end();
 367   return nullptr;
 368 }
 369
 370 inline auto
 371 path::_List::front() noexcept
 372 -> value_type&
 373 {
 374   return *_M_impl->begin();
 375 }
 376
 377 inline auto
 378 path::_List::back() noexcept
 379 -> value_type&
 380 {
 381   return _M_impl->begin()[_M_impl->size() - 1];
 382 }
 383
 384 inline auto
 385 path::_List::front() const noexcept
 386 -> const value_type&
 387 {
 388   return *_M_impl->begin();
 389 }
 390
 391 inline auto
 392 path::_List::back() const noexcept
 393 -> const value_type&
 394 {
 395   return _M_impl->begin()[_M_impl->size() - 1];
 396 }
 397
 398 inline void
 399 path::_List::pop_back()
 400 {
 401   __glibcxx_assert(size() > 0);
 402   _M_impl->pop_back();
 403 }
 404
 405 inline void
 406 path::_List::_M_erase_from(const_iterator pos)
 407 {
 408   _M_impl->_M_erase_from(pos);
 409 }
 410
 411 inline void
 412 path::_List::clear()
 413 {
 414   if (auto ptr = _Impl::notype(_M_impl.get()))
 415     ptr->clear();
 416 }
 417
 418 void
 419 path::_List::reserve(int newcap, bool exact = false)
 420 {
 421   // __glibcxx_assert(type() == _Type::_Multi);
 422
 423   _Impl* curptr = _Impl::notype(_M_impl.get());
 424
 425   int curcap = curptr ? curptr->capacity() : 0;
 426
 427   if (curcap < newcap)
 428     {
 429       if (!exact && newcap < int(1.5 * curcap))
 430         newcap = 1.5 * curcap;
 431
 432       void* p = ::operator new(sizeof(_Impl) + newcap * sizeof(value_type));
 433       std::unique_ptr<_Impl, _Impl_deleter> newptr(::new(p) _Impl{newcap});
 434       const int cursize = curptr ? curptr->size() : 0;
 435       if (cursize)
 436         {
 437           std::uninitialized_move_n(curptr->begin(), cursize, newptr->begin());
 438           newptr->_M_size = cursize;
 439         }
 440       std::swap(newptr, _M_impl);
 441     }
 442 }
 443
 444 path&
 445 path::operator=(const path& p)
 446 {
 447   _M_pathname.reserve(p._M_pathname.length());
 448   _M_cmpts = p._M_cmpts;        // might throw
 449   _M_pathname = p._M_pathname;  // won't throw because we reserved enough space
 450   return *this;
 451 }
 452
 453 path&
 454 path::operator/=(const path& __p)
 455 {
 456 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 457   if (__p.is_absolute()
 458       || (__p.has_root_name() && __p.root_name() != root_name()))
 459     return operator=(__p);
 460
 461   basic_string_view<value_type> __lhs = _M_pathname;
 462   bool __add_sep = false;
 463
 464   if (__p.has_root_directory())
 465     {
 466       // Remove any root directory and relative path
 467       if (_M_type() != _Type::_Root_name)
 468         {
 469           if (!_M_cmpts.empty()
 470               && _M_cmpts.front()._M_type() == _Type::_Root_name)
 471             __lhs = _M_cmpts.front()._M_pathname;
 472           else
 473             __lhs = {};
 474         }
 475     }
 476   else if (has_filename() || (!has_root_directory() && is_absolute()))
 477     __add_sep = true;
 478
 479   basic_string_view<value_type> __rhs = __p._M_pathname;
 480   // Omit any root-name from the generic format pathname:
 481   if (__p._M_type() == _Type::_Root_name)
 482     __rhs = {};
 483   else if (!__p._M_cmpts.empty()
 484       && __p._M_cmpts.front()._M_type() == _Type::_Root_name)
 485     __rhs.remove_prefix(__p._M_cmpts.front()._M_pathname.size());
 486
 487   const size_t __len = __lhs.size() + (int)__add_sep + __rhs.size();
 488   const int __maxcmpts = _M_cmpts.size() + __p._M_cmpts.size();
 489   if (_M_pathname.capacity() < __len || _M_cmpts.capacity() < __maxcmpts)
 490     {
 491       // Construct new path and swap (strong exception-safety guarantee).
 492       string_type __tmp;
 493       __tmp.reserve(__len);
 494       __tmp = __lhs;
 495       if (__add_sep)
 496         __tmp += preferred_separator;
 497       __tmp += __rhs;
 498       path __newp = std::move(__tmp);
 499       swap(__newp);
 500     }
 501   else
 502     {
 503       _M_pathname = __lhs;
 504       if (__add_sep)
 505         _M_pathname += preferred_separator;
 506       _M_pathname += __rhs;
 507       __try
 508         {
 509           _M_split_cmpts();
 510         }
 511       __catch (...)
 512         {
 513           __try
 514             {
 515               // try to restore original state
 516               _M_pathname.resize(__lhs.length());
 517               _M_split_cmpts();
 518             }
 519           __catch (...)
 520             {
 521               // give up, basic exception safety guarantee only:
 522               clear();
 523               __throw_exception_again;
 524             }
 525         }
 526     }
 527 #else
 528   // POSIX version is simpler than the specification in the standard,
 529   // as any path with root-name or root-dir is absolute.
 530
 531   if (__p.is_absolute() || this->empty())
 532     {
 533       return operator=(__p);
 534     }
 535
 536   using string_view_type = basic_string_view<value_type>;
 537
 538   string_view_type sep;
 539   if (has_filename())
 540     sep = { &preferred_separator, 1 };  // need to add a separator
 541 #if SLASHSLASH_IS_ROOTNAME
 542   else if (_M_type() == _Type::_Root_name) // root-name with no root-dir
 543     sep = { &preferred_separator, 1 };  // need to add a separator
 544 #endif
 545   else if (__p.empty())
 546     return *this;                           // nothing to do
 547
 548   const auto orig_pathlen = _M_pathname.length();
 549   const auto orig_size = _M_cmpts.size();
 550   const auto orig_type = _M_type();
 551
 552   int capacity = 0;
 553   if (_M_type() == _Type::_Multi)
 554     capacity += _M_cmpts.size();
 555   else if (!empty())
 556     capacity += 1;
 557   if (__p._M_type() == _Type::_Multi)
 558     capacity += __p._M_cmpts.size();
 559   else if (!__p.empty() || !sep.empty())
 560     capacity += 1;
 561 #if SLASHSLASH_IS_ROOTNAME
 562   if (orig_type == _Type::_Root_name)
 563     ++capacity; // Need to insert root-directory after root-name
 564 #endif
 565
 566   if (orig_type == _Type::_Multi)
 567     {
 568       const int curcap = _M_cmpts._M_impl->capacity();
 569       if (capacity > curcap)
 570         capacity = std::max(capacity, (int) (curcap * 1.5));
 571     }
 572
 573   _M_pathname.reserve(_M_pathname.length() + sep.length()
 574                       + __p._M_pathname.length());
 575
 576   __try
 577     {
 578       _M_pathname += sep;
 579       const auto basepos = _M_pathname.length();
 580       _M_pathname += __p.native();
 581
 582       _M_cmpts.type(_Type::_Multi);
 583       _M_cmpts.reserve(capacity);
 584       _Cmpt* output = _M_cmpts._M_impl->end();
 585
 586       if (orig_type == _Type::_Multi)
 587         {
 588           // Remove empty final component
 589           if (_M_cmpts._M_impl->back().empty())
 590             {
 591               _M_cmpts.pop_back();
 592               --output;
 593             }
 594         }
 595       else if (orig_pathlen != 0)
 596         {
 597           // Create single component from original path
 598           string_view_type s(_M_pathname.data(), orig_pathlen);
 599           ::new(output++) _Cmpt(s, orig_type, 0);
 600           ++_M_cmpts._M_impl->_M_size;
 601 #if SLASHSLASH_IS_ROOTNAME
 602           if (orig_type == _Type::_Root_name)
 603             {
 604               ::new(output++) _Cmpt(sep, _Type::_Root_dir,
 605                                     orig_pathlen + sep.length());
 606               ++_M_cmpts._M_impl->_M_size;
 607             }
 608 #endif
 609         }
 610
 611       if (__p._M_type() == _Type::_Multi)
 612         {
 613           for (auto& c : *__p._M_cmpts._M_impl)
 614             {
 615               ::new(output++) _Cmpt(c._M_pathname, _Type::_Filename,
 616                                     c._M_pos + basepos);
 617               ++_M_cmpts._M_impl->_M_size;
 618             }
 619         }
 620       else if (!__p.empty() || !sep.empty())
 621         {
 622           __glibcxx_assert(__p._M_type() == _Type::_Filename);
 623           ::new(output) _Cmpt(__p._M_pathname, __p._M_type(), basepos);
 624           ++_M_cmpts._M_impl->_M_size;
 625         }
 626     }
 627   __catch (...)
 628     {
 629       _M_pathname.resize(orig_pathlen);
 630       if (orig_type == _Type::_Multi)
 631         _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
 632       else
 633         _M_cmpts.clear();
 634       _M_cmpts.type(orig_type);
 635       __throw_exception_again;
 636     }
 637 #endif
 638   return *this;
 639 }
 640
 641 // [fs.path.append]
 642 void
 643 path::_M_append(basic_string_view<value_type> s)
 644 {
 645   _Parser parser(s);
 646   auto root_path = parser.root_path();
 647
 648 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 649   bool is_absolute = root_path.second.type == _Type::_Root_dir;
 650   bool has_root_name = root_path.first.type == _Type::_Root_name;
 651   if (is_absolute || (has_root_name && root_path.first.str != root_name()))
 652     {
 653       operator=(s);
 654       return;
 655     }
 656
 657   basic_string_view<value_type> lhs = _M_pathname;
 658   bool add_sep = false;
 659
 660   bool has_root_directory = root_path.first.type == _Type::_Root_dir
 661     || root_path.second.type == _Type::_Root_dir;
 662
 663   if (has_root_directory)
 664     {
 665       // Remove any root directory and relative path
 666       if (_M_type() != _Type::_Root_name)
 667         {
 668           if (!_M_cmpts.empty()
 669               && _M_cmpts.front()._M_type() == _Type::_Root_name)
 670             lhs = _M_cmpts.front()._M_pathname;
 671           else
 672             lhs = {};
 673         }
 674     }
 675   else if (has_filename() || (!has_root_directory && is_absolute))
 676     add_sep = true;
 677
 678   basic_string_view<value_type> rhs = s;
 679   // Omit any root-name from the generic format pathname:
 680   if (has_root_name)
 681     rhs.remove_prefix(root_path.first.str.length());
 682
 683   // Construct new path and swap (strong exception-safety guarantee).
 684   string_type tmp;
 685   tmp.reserve(lhs.size() + (int)add_sep + rhs.size());
 686   tmp = lhs;
 687   if (add_sep)
 688     tmp += preferred_separator;
 689   tmp += rhs;
 690   path newp = std::move(tmp);
 691   swap(newp);
 692 #else
 693
 694   bool is_absolute = root_path.first.type == _Type::_Root_dir
 695     || root_path.second.type == _Type::_Root_dir;
 696   if (is_absolute || this->empty())
 697     {
 698       operator=(s);
 699       return;
 700     }
 701
 702   const auto orig_pathlen = _M_pathname.length();
 703   const auto orig_size = _M_cmpts.size();
 704   const auto orig_type = _M_type();
 705
 706   basic_string_view<value_type> sep;
 707   if (has_filename())
 708     sep = { &preferred_separator, 1 };  // need to add a separator
 709 #if SLASHSLASH_IS_ROOTNAME
 710   else if (_M_type() == _Type::_Root_name) // root-name with no root-dir
 711     sep = { &preferred_separator, 1 };  // need to add a separator
 712 #endif
 713   else if (s.empty())
 714     return;                         // nothing to do
 715
 716   // Copy the input into _M_pathname:
 717   _M_pathname += s;
 718   _M_pathname.insert(orig_pathlen, sep);
 719   // Update s to refer to the new copy (this ensures s is not a dangling
 720   // reference to deallocated characters, in the case where it was referring
 721   // into _M_pathname or a member of _M_cmpts).
 722   s = _M_pathname;
 723   const auto orig_pathname = s.substr(0, orig_pathlen);
 724   s.remove_prefix(orig_pathlen + sep.length());
 725
 726   parser.input = s; // reset parser to use updated string view
 727   const auto basepos = orig_pathname.length() + sep.length();
 728   parser.origin = basepos;
 729
 730   std::array<_Parser::cmpt, 64> buf;
 731   auto next = buf.begin();
 732
 733   int capacity = 0;
 734   if (_M_type() == _Type::_Multi)
 735     capacity += _M_cmpts.size();
 736   else if (!empty())
 737     capacity += 1;
 738
 739   auto cmpt = parser.next();
 740   if (cmpt.valid())
 741     {
 742       do
 743         {
 744           *next++ = cmpt;
 745           cmpt = parser.next();
 746         }
 747       while (cmpt.valid() && next != buf.end());
 748
 749       capacity += next - buf.begin();
 750       if (cmpt.valid()) // filled buffer before parsing whole input
 751         {
 752           ++capacity;
 753           _Parser parser2(parser);
 754           while (parser2.next().valid())
 755             ++capacity;
 756         }
 757     }
 758   else if (!sep.empty())
 759     ++capacity;
 760
 761 #if SLASHSLASH_IS_ROOTNAME
 762   if (orig_type == _Type::_Root_name)
 763     ++capacity; // Need to insert root-directory after root-name
 764 #endif
 765
 766   __try
 767     {
 768       _M_cmpts.type(_Type::_Multi);
 769       _M_cmpts.reserve(capacity);
 770       _Cmpt* output = _M_cmpts._M_impl->end();
 771
 772       if (orig_type == _Type::_Multi)
 773         {
 774           // Remove empty final component
 775           if (_M_cmpts._M_impl->back().empty())
 776             {
 777               _M_cmpts.pop_back();
 778               --output;
 779             }
 780         }
 781       else if (orig_pathlen != 0)
 782         {
 783           // Create single component from original path
 784           ::new(output++) _Cmpt(orig_pathname, orig_type, 0);
 785           ++_M_cmpts._M_impl->_M_size;
 786
 787 #if SLASHSLASH_IS_ROOTNAME
 788           if (!sep.empty() && orig_type == _Type::_Root_name)
 789             {
 790               ::new(output++) _Cmpt(sep, _Type::_Root_dir,
 791                                     orig_pathlen + sep.length());
 792               ++_M_cmpts._M_impl->_M_size;
 793             }
 794 #endif
 795         }
 796
 797       if (next != buf.begin())
 798         {
 799           for (auto it = buf.begin(); it != next; ++it)
 800             {
 801               auto c = *it;
 802               ::new(output++) _Cmpt(c.str, c.type, parser.offset(c));
 803               ++_M_cmpts._M_impl->_M_size;
 804             }
 805           while (cmpt.valid())
 806             {
 807               ::new(output++) _Cmpt(cmpt.str, cmpt.type, parser.offset(cmpt));
 808               ++_M_cmpts._M_impl->_M_size;
 809               cmpt = parser.next();
 810             }
 811         }
 812       else if (!sep.empty())
 813         {
 814           // Empty filename at the end:
 815           ::new(output) _Cmpt({}, _Type::_Filename, basepos);
 816           ++_M_cmpts._M_impl->_M_size;
 817         }
 818     }
 819   __catch (...)
 820     {
 821       _M_pathname.resize(orig_pathlen);
 822       if (orig_type == _Type::_Multi)
 823         _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
 824       else
 825         _M_cmpts.clear();
 826       _M_cmpts.type(orig_type);
 827       __throw_exception_again;
 828     }
 829 #endif
 830 }
 831
 832 // [fs.path.concat]
 833 path&
 834 path::operator+=(const path& p)
 835 {
 836   if (p.empty())
 837     return *this;
 838
 839   if (this->empty())
 840     {
 841       operator=(p);
 842       return *this;
 843     }
 844
 845   const auto orig_pathlen = _M_pathname.length();
 846   const auto orig_type = _M_type();
 847   const auto orig_size = _M_cmpts.size();
 848   int orig_filenamelen = -1;
 849   basic_string_view<value_type> extra;
 850
 851   // Ensure that '_M_pathname += p._M_pathname' won't throw:
 852   _M_pathname.reserve(orig_pathlen + p._M_pathname.length());
 853
 854   _Cmpt c;
 855   _Cmpt* it = nullptr;
 856   _Cmpt* last = nullptr;
 857   if (p._M_type() == _Type::_Multi)
 858     {
 859       it = p._M_cmpts._M_impl->begin();
 860       last = p._M_cmpts._M_impl->end();
 861     }
 862   else
 863     {
 864       c = _Cmpt(p._M_pathname, p._M_type(), 0);
 865       it = &c;
 866       last = it + 1;
 867     }
 868
 869   if (it->_M_type() == _Type::_Filename)
 870     {
 871       // See if there's a filename or root-name at the end of the original path
 872       // that we can add to.
 873       if (_M_type() == _Type::_Filename
 874 #if SLASHSLASH_IS_ROOTNAME
 875           || _M_type() == _Type::_Root_name
 876 #endif
 877           )
 878         {
 879           if (p._M_type() == _Type::_Filename)
 880             {
 881               // Simplest case where we just add the whole of p to the
 882               // original path.
 883               _M_pathname += p._M_pathname;
 884               return *this;
 885             }
 886           // Only the first component of s should be appended, do so below:
 887           extra = it->_M_pathname;
 888           ++it;
 889         }
 890       else if (_M_type() == _Type::_Multi
 891           && _M_cmpts.back()._M_type() == _Type::_Filename)
 892         {
 893           auto& back = _M_cmpts.back();
 894           if (p._M_type() == _Type::_Filename)
 895             {
 896               basic_string_view<value_type> s = p._M_pathname;
 897               back._M_pathname += s;
 898               _M_pathname += s;
 899               return *this;
 900             }
 901
 902           orig_filenamelen = back._M_pathname.length();
 903           back._M_pathname += it->_M_pathname;
 904           extra = it->_M_pathname;
 905           ++it;
 906         }
 907     }
 908   else if (is_dir_sep(_M_pathname.back()) && _M_type() == _Type::_Multi
 909       && _M_cmpts.back()._M_type() == _Type::_Filename)
 910     orig_filenamelen = 0; // current path has empty filename at end
 911
 912   int capacity = 0;
 913   if (_M_type() == _Type::_Multi)
 914     capacity += _M_cmpts.size();
 915   else
 916     capacity += 1;
 917   if (p._M_type() == _Type::_Multi)
 918     capacity += p._M_cmpts.size();
 919   else
 920     capacity += 1;
 921
 922   __try
 923     {
 924       _M_cmpts.type(_Type::_Multi);
 925       _M_cmpts.reserve(capacity);
 926       _Cmpt* output = _M_cmpts._M_impl->end();
 927
 928       if (orig_type != _Type::_Multi)
 929         {
 930           // Create single component from original path
 931           auto ptr = ::new(output++) _Cmpt({}, orig_type, 0);
 932           ++_M_cmpts._M_impl->_M_size;
 933           ptr->_M_pathname.reserve(_M_pathname.length() + extra.length());
 934           ptr->_M_pathname = _M_pathname;
 935           ptr->_M_pathname += extra;
 936
 937 #if SLASHSLASH_IS_ROOTNAME
 938           if (orig_type == _Type::_Root_name)
 939             {
 940               basic_string_view<value_type> s(p._M_pathname);
 941               ::new(output++) _Cmpt(s.substr(extra.length(), 1),
 942                   _Type::_Root_dir, orig_pathlen + extra.length());
 943               ++_M_cmpts._M_impl->_M_size;
 944             }
 945 #endif
 946         }
 947       else if (orig_filenamelen == 0 && it != last)
 948         {
 949           // Remove empty filename at end of original path.
 950           _M_cmpts.pop_back();
 951           --output;
 952         }
 953
 954       if (it != last && it->_M_type() == _Type::_Root_name)
 955         {
 956           basic_string_view<value_type> s = it->_M_pathname;
 957           auto pos = orig_pathlen;
 958 #if SLASHSLASH_IS_ROOTNAME
 959           s.remove_prefix(2);
 960           pos += 2;
 961 #endif
 962           ::new(output++) _Cmpt(s, _Type::_Filename, pos);
 963           ++_M_cmpts._M_impl->_M_size;
 964           ++it;
 965         }
 966
 967       if (it != last && it->_M_type() == _Type::_Root_dir)
 968         {
 969           ++it;
 970           if (it == last)
 971             {
 972               // This root-dir becomes a trailing slash
 973               auto pos = _M_pathname.length() + p._M_pathname.length();
 974               ::new(output++) _Cmpt({}, _Type::_Filename, pos);
 975               ++_M_cmpts._M_impl->_M_size;
 976             }
 977         }
 978
 979       while (it != last)
 980         {
 981           auto pos = it->_M_pos + orig_pathlen;
 982           ::new(output++) _Cmpt(it->_M_pathname, _Type::_Filename, pos);
 983           ++_M_cmpts._M_impl->_M_size;
 984           ++it;
 985         }
 986
 987       _M_pathname += p._M_pathname;
 988
 989       if (is_dir_sep(_M_pathname.back()))
 990         {
 991           ::new(output++) _Cmpt({}, _Type::_Filename, _M_pathname.length());
 992           ++_M_cmpts._M_impl->_M_size;
 993         }
 994       }
 995   __catch (...)
 996     {
 997       _M_pathname.resize(orig_pathlen);
 998       if (orig_type == _Type::_Multi)
 999         {
1000           if (_M_cmpts.size() > orig_size)
1001             _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
1002           if (orig_filenamelen != -1)
1003             {
1004               if (_M_cmpts.size() == orig_size)
1005                 {
1006                   auto& back = _M_cmpts.back();
1007                   back._M_pathname.resize(orig_filenamelen);
1008                   if (orig_filenamelen == 0)
1009                     back._M_pos = orig_pathlen;
1010                 }
1011               else
1012                 {
1013                   auto output = _M_cmpts._M_impl->end();
1014                   ::new(output) _Cmpt({}, _Type::_Filename, orig_pathlen);
1015                   ++_M_cmpts._M_impl->_M_size;
1016                 }
1017             }
1018         }
1019       else
1020         _M_cmpts.clear();
1021       _M_cmpts.type(orig_type);
1022       __throw_exception_again;
1023     }
1024   return *this;
1025 }
1026
1027 // [fs.path.concat]
1028 void
1029 path::_M_concat(basic_string_view<value_type> s)
1030 {
1031   if (s.empty())
1032     return;
1033
1034   if (this->empty())
1035     {
1036       operator=(s);
1037       return;
1038     }
1039
1040   const auto orig_pathlen = _M_pathname.length();
1041   const auto orig_type = _M_type();
1042   const auto orig_size = _M_cmpts.size();
1043   int orig_filenamelen = -1;
1044   basic_string_view<value_type> extra;
1045
1046   // Copy the input into _M_pathname:
1047   _M_pathname += s;
1048   // Update s to refer to the new copy (this ensures s is not a dangling
1049   // reference to deallocated characters, in the case where it was referring
1050   // into _M_pathname or a member of _M_cmpts).
1051   s = _M_pathname;
1052   const auto orig_pathname = s.substr(0, orig_pathlen);
1053   s.remove_prefix(orig_pathlen);
1054
1055   _Parser parser(s, orig_pathlen);
1056   auto cmpt = parser.next();
1057
1058   if (cmpt.str.data() == s.data())
1059     {
1060       // See if there's a filename or root-name at the end of the original path
1061       // that we can add to.
1062       if (_M_type() == _Type::_Filename
1063 #if SLASHSLASH_IS_ROOTNAME
1064           || _M_type() == _Type::_Root_name
1065 #endif
1066           )
1067         {
1068           if (cmpt.str.length() == s.length())
1069             {
1070               // Simplest case where we just need to add the whole of s
1071               // to the original path, which was already done above.
1072               return;
1073             }
1074           // Only the first component of s should be appended, do so below:
1075           extra = cmpt.str;
1076           cmpt = {}; // so we don't process it again
1077         }
1078       else if (_M_type() == _Type::_Multi
1079           && _M_cmpts.back()._M_type() == _Type::_Filename)
1080         {
1081           auto& back = _M_cmpts.back();
1082           if (cmpt.str.length() == s.length())
1083             {
1084               back._M_pathname += s;
1085               return;
1086             }
1087
1088           orig_filenamelen = back._M_pathname.length();
1089           back._M_pathname += cmpt.str;
1090           extra = cmpt.str;
1091           cmpt = {};
1092         }
1093     }
1094   else if (is_dir_sep(orig_pathname.back()) && _M_type() == _Type::_Multi
1095       && _M_cmpts.back()._M_type() == _Type::_Filename)
1096     orig_filenamelen = 0; // original path had empty filename at end
1097
1098   std::array<_Parser::cmpt, 64> buf;
1099   auto next = buf.begin();
1100
1101   if (cmpt.valid())
1102     *next++ = cmpt;
1103
1104   cmpt = parser.next();
1105   while (cmpt.valid() && next != buf.end())
1106     {
1107       *next++ = cmpt;
1108       cmpt = parser.next();
1109     }
1110
1111   int capacity = 0;
1112   if (_M_type() == _Type::_Multi)
1113     capacity += _M_cmpts.size();
1114   else
1115     capacity += 1;
1116
1117   capacity += next - buf.begin();
1118
1119   if (cmpt.valid()) // filled buffer before parsing whole input
1120     {
1121       ++capacity;
1122       _Parser parser2(parser);
1123       while (parser2.next().valid())
1124         ++capacity;
1125     }
1126
1127 #if SLASHSLASH_IS_ROOTNAME
1128   if (orig_type == _Type::_Root_name)
1129     ++capacity; // Need to insert root-directory after root-name
1130 #endif
1131
1132   __try
1133     {
1134       _M_cmpts.type(_Type::_Multi);
1135       _M_cmpts.reserve(capacity);
1136       _Cmpt* output = _M_cmpts._M_impl->end();
1137       auto it = buf.begin();
1138
1139       if (orig_type != _Type::_Multi)
1140         {
1141           // Create single component from original path
1142           auto p = ::new(output++) _Cmpt({}, orig_type, 0);
1143           ++_M_cmpts._M_impl->_M_size;
1144           p->_M_pathname.reserve(orig_pathname.length() + extra.length());
1145           p->_M_pathname = orig_pathname;
1146           p->_M_pathname += extra;
1147
1148 #if SLASHSLASH_IS_ROOTNAME
1149           if (orig_type == _Type::_Root_name)
1150             {
1151               ::new(output++) _Cmpt(s.substr(extra.length(), 1),
1152                   _Type::_Root_dir, orig_pathlen + extra.length());
1153               ++_M_cmpts._M_impl->_M_size;
1154             }
1155 #endif
1156         }
1157       else if (orig_filenamelen == 0 && extra.empty())
1158         {
1159           // Replace empty filename at end of original path.
1160           std::prev(output)->_M_pathname = it->str;
1161           std::prev(output)->_M_pos = parser.offset(*it);
1162           ++it;
1163         }
1164
1165       while (it != next)
1166         {
1167           ::new(output++) _Cmpt(it->str, _Type::_Filename, parser.offset(*it));
1168           ++_M_cmpts._M_impl->_M_size;
1169           ++it;
1170         }
1171
1172       if (next == buf.end())
1173         {
1174           while (cmpt.valid())
1175             {
1176               auto pos = parser.offset(cmpt);
1177               ::new(output++) _Cmpt(cmpt.str, _Type::_Filename, pos);
1178               ++_M_cmpts._M_impl->_M_size;
1179               cmpt = parser.next();
1180             }
1181         }
1182     }
1183   __catch (...)
1184     {
1185       _M_pathname.resize(orig_pathlen);
1186       if (orig_type == _Type::_Multi)
1187         {
1188           _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
1189           if (orig_filenamelen != -1)
1190             {
1191               auto& back = _M_cmpts.back();
1192               back._M_pathname.resize(orig_filenamelen);
1193               if (orig_filenamelen == 0)
1194                 back._M_pos = orig_pathlen;
1195             }
1196         }
1197       else
1198         _M_cmpts.clear();
1199       _M_cmpts.type(orig_type);
1200       __throw_exception_again;
1201     }
1202 }
1203
1204 path&
1205 path::remove_filename()
1206 {
1207   if (_M_type() == _Type::_Multi)
1208     {
1209       if (!_M_cmpts.empty())
1210         {
1211           auto cmpt = std::prev(_M_cmpts.end());
1212           if (cmpt->_M_type() == _Type::_Filename && !cmpt->empty())
1213             {
1214               _M_pathname.erase(cmpt->_M_pos);
1215               auto prev = std::prev(cmpt);
1216               if (prev->_M_type() == _Type::_Root_dir
1217                   || prev->_M_type() == _Type::_Root_name)
1218                 {
1219                   _M_cmpts.pop_back();
1220                   if (_M_cmpts.size() == 1)
1221                     {
1222                       _M_cmpts.type(_M_cmpts.front()._M_type());
1223                       _M_cmpts.clear();
1224                     }
1225                 }
1226               else
1227                 cmpt->clear();
1228             }
1229         }
1230     }
1231   else if (_M_type() == _Type::_Filename)
1232     clear();
1233   return *this;
1234 }
1235
1236 path&
1237 path::replace_filename(const path& replacement)
1238 {
1239   remove_filename();
1240   operator/=(replacement);
1241   return *this;
1242 }
1243
1244 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
1245 const fs::path::value_type dot = L'.';
1246 #else
1247 const fs::path::value_type dot = '.';
1248 #endif
1249
1250 path&
1251 path::replace_extension(const path& replacement)
1252 {
1253   auto ext = _M_find_extension();
1254   // Any existing extension() is removed
1255   if (ext.first && ext.second != string_type::npos)
1256     {
1257       if (ext.first == &_M_pathname)
1258         _M_pathname.erase(ext.second);
1259       else
1260         {
1261           const auto& back = _M_cmpts.back();
1262           if (ext.first != &back._M_pathname)
1263             _GLIBCXX_THROW_OR_ABORT(
1264                 std::logic_error("path::replace_extension failed"));
1265           _M_pathname.erase(back._M_pos + ext.second);
1266         }
1267     }
1268    // If replacement is not empty and does not begin with a dot character,
1269    // a dot character is appended
1270   if (!replacement.empty() && replacement.native()[0] != dot)
1271     _M_pathname += dot;
1272   operator+=(replacement);
1273   return *this;
1274 }
1275
1276 int
1277 path::compare(const path& p) const noexcept
1278 {
1279   if (_M_pathname == p._M_pathname)
1280     return 0;
1281
1282   basic_string_view<value_type> lroot, rroot;
1283   if (_M_type() == _Type::_Root_name)
1284     lroot = _M_pathname;
1285   else if (_M_type() == _Type::_Multi
1286       && _M_cmpts.front()._M_type() == _Type::_Root_name)
1287     lroot = _M_cmpts.front()._M_pathname;
1288   if (p._M_type() == _Type::_Root_name)
1289     rroot = p._M_pathname;
1290   else if (p._M_type() == _Type::_Multi
1291       && p._M_cmpts.front()._M_type() == _Type::_Root_name)
1292     rroot = p._M_cmpts.front()._M_pathname;
1293   if (int rootNameComparison = lroot.compare(rroot))
1294     return rootNameComparison;
1295
1296   if (!this->has_root_directory() && p.has_root_directory())
1297     return -1;
1298   else if (this->has_root_directory() && !p.has_root_directory())
1299     return +1;
1300
1301   using Iterator = const _Cmpt*;
1302   Iterator begin1, end1, begin2, end2;
1303   if (_M_type() == _Type::_Multi)
1304     {
1305       begin1 = _M_cmpts.begin();
1306       end1 = _M_cmpts.end();
1307       // Find start of this->relative_path()
1308       while (begin1 != end1 && begin1->_M_type() != _Type::_Filename)
1309         ++begin1;
1310     }
1311   else
1312     begin1 = end1 = nullptr;
1313
1314   if (p._M_type() == _Type::_Multi)
1315     {
1316       begin2 = p._M_cmpts.begin();
1317       end2 = p._M_cmpts.end();
1318       // Find start of p.relative_path()
1319       while (begin2 != end2 && begin2->_M_type() != _Type::_Filename)
1320         ++begin2;
1321     }
1322   else
1323     begin2 = end2 = nullptr;
1324
1325   if (_M_type() == _Type::_Filename)
1326     {
1327       if (p._M_type() == _Type::_Filename)
1328         return native().compare(p.native());
1329       else if (begin2 != end2)
1330         {
1331           if (int ret = native().compare(begin2->native()))
1332             return ret;
1333           else
1334             return ++begin2 == end2 ? 0 : -1;
1335         }
1336       else
1337         return +1;
1338     }
1339   else if (p._M_type() == _Type::_Filename)
1340     {
1341       if (begin1 != end1)
1342         {
1343           if (int ret = begin1->native().compare(p.native()))
1344             return ret;
1345           else
1346             return ++begin1 == end1 ? 0 : +1;
1347         }
1348       else
1349         return -1;
1350     }
1351
1352   int count = 1;
1353   while (begin1 != end1 && begin2 != end2)
1354     {
1355       if (int i = begin1->native().compare(begin2->native()))
1356         return i;
1357       ++begin1;
1358       ++begin2;
1359       ++count;
1360     }
1361   if (begin1 == end1)
1362     {
1363       if (begin2 == end2)
1364         return 0;
1365       return -count;
1366     }
1367   return count;
1368 }
1369
1370 int
1371 path::compare(basic_string_view<value_type> s) const noexcept
1372 {
1373   if (_M_pathname == s)
1374     return 0;
1375
1376   _Parser parser(s);
1377
1378   basic_string_view<value_type> lroot, rroot;
1379   if (_M_type() == _Type::_Root_name)
1380     lroot = _M_pathname;
1381   else if (_M_type() == _Type::_Multi
1382       && _M_cmpts.front()._M_type() == _Type::_Root_name)
1383     lroot = _M_cmpts.front()._M_pathname;
1384   auto root_path = parser.root_path();
1385   if (root_path.first.type == _Type::_Root_name)
1386     rroot = root_path.first.str;
1387   if (int rootNameComparison = lroot.compare(rroot))
1388     return rootNameComparison;
1389
1390   const bool has_root_dir = root_path.first.type == _Type::_Root_dir
1391     || root_path.second.type == _Type::_Root_dir;
1392   if (!this->has_root_directory() && has_root_dir)
1393     return -1;
1394   else if (this->has_root_directory() && !has_root_dir)
1395     return +1;
1396
1397   using Iterator = const _Cmpt*;
1398   Iterator begin1, end1;
1399   if (_M_type() == _Type::_Filename)
1400     {
1401       auto cmpt = parser.next();
1402       if (cmpt.valid())
1403         {
1404           if (int ret = this->native().compare(cmpt.str))
1405             return ret;
1406           return parser.next().valid() ? -1 : 0;
1407         }
1408       else
1409         return +1;
1410     }
1411   else if (_M_type() == _Type::_Multi)
1412     {
1413       begin1 = _M_cmpts.begin();
1414       end1 = _M_cmpts.end();
1415       while (begin1 != end1 && begin1->_M_type() != _Type::_Filename)
1416         ++begin1;
1417     }
1418   else
1419     begin1 = end1 = nullptr;
1420
1421   int count = 1;
1422   auto cmpt = parser.next();
1423   while (begin1 != end1 && cmpt.valid())
1424     {
1425       if (int i = begin1->native().compare(cmpt.str))
1426         return i;
1427       ++begin1;
1428       cmpt = parser.next();
1429       ++count;
1430     }
1431   if (begin1 == end1)
1432     {
1433       if (!cmpt.valid())
1434         return 0;
1435       return -count;
1436     }
1437   return +count;
1438 }
1439
1440 path
1441 path::root_name() const
1442 {
1443   path __ret;
1444   if (_M_type() == _Type::_Root_name)
1445     __ret = *this;
1446   else if (_M_cmpts.size() && _M_cmpts.begin()->_M_type() == _Type::_Root_name)
1447     __ret = *_M_cmpts.begin();
1448   return __ret;
1449 }
1450
1451 path
1452 path::root_directory() const
1453 {
1454   path __ret;
1455   if (_M_type() == _Type::_Root_dir)
1456     {
1457       __ret._M_cmpts.type(_Type::_Root_dir);
1458       __ret._M_pathname.assign(1, preferred_separator);
1459     }
1460   else if (!_M_cmpts.empty())
1461     {
1462       auto __it = _M_cmpts.begin();
1463       if (__it->_M_type() == _Type::_Root_name)
1464         ++__it;
1465       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1466         __ret = *__it;
1467     }
1468   return __ret;
1469 }
1470
1471 path
1472 path::root_path() const
1473 {
1474   path __ret;
1475   if (_M_type() == _Type::_Root_name)
1476     __ret = *this;
1477   else if (_M_type() == _Type::_Root_dir)
1478     {
1479       __ret._M_pathname.assign(1, preferred_separator);
1480       __ret._M_cmpts.type(_Type::_Root_dir);
1481     }
1482   else if (!_M_cmpts.empty())
1483     {
1484       auto __it = _M_cmpts.begin();
1485       if (__it->_M_type() == _Type::_Root_name)
1486         {
1487           __ret = *__it++;
1488           if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1489             __ret /= *__it;
1490         }
1491       else if (__it->_M_type() == _Type::_Root_dir)
1492         __ret = *__it;
1493     }
1494   return __ret;
1495 }
1496
1497 path
1498 path::relative_path() const
1499 {
1500   path __ret;
1501   if (_M_type() == _Type::_Filename)
1502     __ret = *this;
1503   else if (!_M_cmpts.empty())
1504     {
1505       auto __it = _M_cmpts.begin();
1506       if (__it->_M_type() == _Type::_Root_name)
1507         ++__it;
1508       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1509         ++__it;
1510       if (__it != _M_cmpts.end())
1511         __ret.assign(_M_pathname.substr(__it->_M_pos));
1512     }
1513   return __ret;
1514 }
1515
1516 path
1517 path::parent_path() const
1518 {
1519   path __ret;
1520   if (!has_relative_path())
1521     __ret = *this;
1522   else if (_M_cmpts.size() >= 2)
1523     {
1524       for (auto __it = _M_cmpts.begin(), __end = std::prev(_M_cmpts.end());
1525            __it != __end; ++__it)
1526         {
1527           __ret /= *__it;
1528         }
1529     }
1530   return __ret;
1531 }
1532
1533 bool
1534 path::has_root_name() const
1535 {
1536   if (_M_type() == _Type::_Root_name)
1537     return true;
1538   if (!_M_cmpts.empty() && _M_cmpts.begin()->_M_type() == _Type::_Root_name)
1539     return true;
1540   return false;
1541 }
1542
1543 bool
1544 path::has_root_directory() const
1545 {
1546   if (_M_type() == _Type::_Root_dir)
1547     return true;
1548   if (!_M_cmpts.empty())
1549     {
1550       auto __it = _M_cmpts.begin();
1551       if (__it->_M_type() == _Type::_Root_name)
1552         ++__it;
1553       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1554         return true;
1555     }
1556   return false;
1557 }
1558
1559 bool
1560 path::has_root_path() const
1561 {
1562   if (_M_type() == _Type::_Root_name || _M_type() == _Type::_Root_dir)
1563     return true;
1564   if (!_M_cmpts.empty())
1565     {
1566       auto __type = _M_cmpts.front()._M_type();
1567       if (__type == _Type::_Root_name || __type == _Type::_Root_dir)
1568         return true;
1569     }
1570   return false;
1571 }
1572
1573 bool
1574 path::has_relative_path() const
1575 {
1576   if (_M_type() == _Type::_Filename && !_M_pathname.empty())
1577     return true;
1578   if (!_M_cmpts.empty())
1579     {
1580       auto __it = _M_cmpts.begin();
1581       if (__it->_M_type() == _Type::_Root_name)
1582         ++__it;
1583       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1584         ++__it;
1585       if (__it != _M_cmpts.end() && !__it->_M_pathname.empty())
1586         return true;
1587     }
1588   return false;
1589 }
1590
1591
1592 bool
1593 path::has_parent_path() const
1594 {
1595   if (!has_relative_path())
1596     return !empty();
1597   return _M_cmpts.size() >= 2;
1598 }
1599
1600 bool
1601 path::has_filename() const
1602 {
1603   if (empty())
1604     return false;
1605   if (_M_type() == _Type::_Filename)
1606     return !_M_pathname.empty();
1607   if (_M_type() == _Type::_Multi)
1608     {
1609       if (_M_pathname.back() == preferred_separator)
1610         return false;
1611       return _M_cmpts.back().has_filename();
1612     }
1613   return false;
1614 }
1615
1616 namespace
1617 {
1618   inline bool is_dot(fs::path::value_type c) { return c == dot; }
1619
1620   inline bool is_dot(const fs::path& path)
1621   {
1622     const auto& filename = path.native();
1623     return filename.size() == 1 && is_dot(filename[0]);
1624   }
1625
1626   inline bool is_dotdot(const fs::path& path)
1627   {
1628     const auto& filename = path.native();
1629     return filename.size() == 2 && is_dot(filename[0]) && is_dot(filename[1]);
1630   }
1631 } // namespace
1632
1633 path
1634 path::lexically_normal() const
1635 {
1636   /*
1637   C++17 [fs.path.generic] p6
1638   - If the path is empty, stop.
1639   - Replace each slash character in the root-name with a preferred-separator.
1640   - Replace each directory-separator with a preferred-separator.
1641   - Remove each dot filename and any immediately following directory-separator.
1642   - As long as any appear, remove a non-dot-dot filename immediately followed
1643     by a directory-separator and a dot-dot filename, along with any immediately
1644     following directory-separator.
1645   - If there is a root-directory, remove all dot-dot filenames and any
1646     directory-separators immediately following them.
1647   - If the last filename is dot-dot, remove any trailing directory-separator.
1648   - If the path is empty, add a dot.
1649   */
1650   path ret;
1651   // If the path is empty, stop.
1652   if (empty())
1653     return ret;
1654   for (auto& p : *this)
1655     {
1656 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
1657       // Replace each slash character in the root-name
1658       if (p._M_type() == _Type::_Root_name || p._M_type() == _Type::_Root_dir)
1659         {
1660           string_type s = p.native();
1661           std::replace(s.begin(), s.end(), L'/', L'\\');
1662           ret /= s;
1663           continue;
1664         }
1665 #endif
1666       if (is_dotdot(p))
1667         {
1668           if (ret.has_filename())
1669             {
1670               // remove a non-dot-dot filename immediately followed by /..
1671               if (!is_dotdot(ret.filename()))
1672                 ret.remove_filename();
1673               else
1674                 ret /= p;
1675             }
1676           else if (!ret.has_relative_path())
1677             {
1678               // remove a dot-dot filename immediately after root-directory
1679               if (!ret.has_root_directory())
1680                 ret /= p;
1681             }
1682           else
1683             {
1684               // Got a path with a relative path (i.e. at least one non-root
1685               // element) and no filename at the end (i.e. empty last element),
1686               // so must have a trailing slash. See what is before it.
1687               auto elem = ret._M_cmpts.end() - 2;
1688               if (elem->has_filename() && !is_dotdot(*elem))
1689                 {
1690                   // Remove the filename before the trailing slash
1691                   // (equiv. to ret = ret.parent_path().remove_filename())
1692
1693                   if (elem == ret._M_cmpts.begin())
1694                     ret.clear();
1695                   else
1696                     {
1697                       ret._M_pathname.erase(elem->_M_pos);
1698                       // Remove empty filename at the end:
1699                       ret._M_cmpts.pop_back();
1700                       // If we still have a trailing non-root dir separator
1701                       // then leave an empty filename at the end:
1702                       if (std::prev(elem)->_M_type() == _Type::_Filename)
1703                         elem->clear();
1704                       else // remove the component completely:
1705                         ret._M_cmpts.pop_back();
1706                     }
1707                 }
1708               else
1709                 // Append the ".." to something ending in "../" which happens
1710                 // when normalising paths like ".././.." and "../a/../.."
1711                 ret /= p;
1712             }
1713         }
1714       else if (is_dot(p))
1715         ret /= path();
1716 #if SLASHSLASH_IS_ROOTNAME
1717       else if (p._M_type() == _Type::_Root_dir)
1718         ret += '/'; // using operator/=('/') would replace whole of ret
1719 #endif
1720       else
1721         ret /= p;
1722     }
1723
1724   if (ret._M_cmpts.size() >= 2)
1725     {
1726       auto back = std::prev(ret.end());
1727       // If the last filename is dot-dot, ...
1728       if (back->empty() && is_dotdot(*std::prev(back)))
1729         // ... remove any trailing directory-separator.
1730         ret = ret.parent_path();
1731     }
1732   // If the path is empty, add a dot.
1733   else if (ret.empty())
1734     ret = ".";
1735
1736   return ret;
1737 }
1738
1739 path
1740 path::lexically_relative(const path& base) const
1741 {
1742   path ret;
1743   if (root_name() != base.root_name())
1744     return ret;
1745   if (is_absolute() != base.is_absolute())
1746     return ret;
1747   if (!has_root_directory() && base.has_root_directory())
1748     return ret;
1749   auto [a, b] = std::mismatch(begin(), end(), base.begin(), base.end());
1750   if (a == end() && b == base.end())
1751     ret = ".";
1752   else
1753   {
1754     int n = 0;
1755     for (; b != base.end(); ++b)
1756     {
1757       const path& p = *b;
1758       if (is_dotdot(p))
1759         --n;
1760       else if (!p.empty() && !is_dot(p))
1761         ++n;
1762     }
1763     if (n == 0 && (a == end() || a->empty()))
1764       ret = ".";
1765     else if (n >= 0)
1766     {
1767       const path dotdot("..");
1768       while (n--)
1769         ret /= dotdot;
1770       for (; a != end(); ++a)
1771         ret /= *a;
1772     }
1773   }
1774   return ret;
1775 }
1776
1777 path
1778 path::lexically_proximate(const path& base) const
1779 {
1780   path rel = lexically_relative(base);
1781   if (rel.empty())
1782     rel = *this;
1783   return rel;
1784 }
1785
1786 std::pair<const path::string_type*, std::size_t>
1787 path::_M_find_extension() const
1788 {
1789   const string_type* s = nullptr;
1790
1791   if (_M_type() == _Type::_Filename)
1792     s = &_M_pathname;
1793   else if (_M_type() == _Type::_Multi && !_M_cmpts.empty())
1794     {
1795       const auto& c = _M_cmpts.back();
1796       if (c._M_type() == _Type::_Filename)
1797         s = &c._M_pathname;
1798     }
1799
1800   if (s)
1801     {
1802       if (auto sz = s->size())
1803         {
1804           if (sz <= 2 && (*s)[0] == dot)
1805             return { s, string_type::npos };
1806           const auto pos = s->rfind(dot);
1807           return { s, pos ? pos : string_type::npos };
1808         }
1809     }
1810   return {};
1811 }
1812
1813 void
1814 path::_M_split_cmpts()
1815 {
1816   _M_cmpts.clear();
1817
1818   if (_M_pathname.empty())
1819     {
1820       _M_cmpts.type(_Type::_Filename);
1821       return;
1822     }
1823   if (_M_pathname.length() == 1 && _M_pathname[0] == preferred_separator)
1824     {
1825       _M_cmpts.type(_Type::_Root_dir);
1826       return;
1827     }
1828
1829   _Parser parser(_M_pathname);
1830
1831   std::array<_Parser::cmpt, 64> buf;
1832   auto next = buf.begin();
1833
1834   // look for root name or root directory
1835   auto root_path = parser.root_path();
1836   if (root_path.first.valid())
1837     {
1838       *next++ = root_path.first;
1839       if (root_path.second.valid())
1840         *next++ = root_path.second;
1841     }
1842
1843   auto cmpt = parser.next();
1844   while (cmpt.valid())
1845     {
1846       do
1847         {
1848           *next++ = cmpt;
1849           cmpt = parser.next();
1850         }
1851       while (cmpt.valid() && next != buf.end());
1852
1853       if (next == buf.end())
1854         {
1855           _M_cmpts.type(_Type::_Multi);
1856           _M_cmpts.reserve(_M_cmpts.size() + buf.size());
1857           auto output = _M_cmpts._M_impl->end();
1858           for (auto& c : buf)
1859             {
1860               auto pos = c.str.data() - _M_pathname.data();
1861               ::new(output++) _Cmpt(c.str, c.type, pos);
1862               ++_M_cmpts._M_impl->_M_size;
1863             }
1864           next = buf.begin();
1865         }
1866     }
1867
1868   if (auto n = next - buf.begin())
1869     {
1870       if (n == 1 && _M_cmpts.empty())
1871         {
1872           _M_cmpts.type(buf.front().type);
1873           return;
1874         }
1875
1876       _M_cmpts.type(_Type::_Multi);
1877       _M_cmpts.reserve(_M_cmpts.size() + n, true);
1878       auto output = _M_cmpts._M_impl->end();
1879       for (int i = 0; i < n; ++i)
1880         {
1881           auto c = buf[i];
1882           auto pos = c.str.data() - _M_pathname.data();
1883           ::new(output++) _Cmpt(c.str, c.type, pos);
1884           ++_M_cmpts._M_impl->_M_size;
1885         }
1886     }
1887 }
1888
1889 path::string_type
1890 path::_S_convert_loc(const char* __first, const char* __last,
1891                      const std::locale& __loc)
1892 {
1893 #if _GLIBCXX_USE_WCHAR_T
1894   auto& __cvt = std::use_facet<codecvt<wchar_t, char, mbstate_t>>(__loc);
1895   basic_string<wchar_t> __ws;
1896   if (!__str_codecvt_in(__first, __last, __ws, __cvt))
1897     _GLIBCXX_THROW_OR_ABORT(filesystem_error(
1898           "Cannot convert character sequence",
1899           std::make_error_code(errc::illegal_byte_sequence)));
1900 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
1901   return __ws;
1902 #else
1903   return _Cvt<wchar_t>::_S_convert(__ws.data(), __ws.data() + __ws.size());
1904 #endif
1905 #else
1906   return {__first, __last};
1907 #endif
1908 }
1909
1910 std::size_t
1911 fs::hash_value(const path& p) noexcept
1912 {
1913   // [path.non-member]
1914   // "If for two paths, p1 == p2 then hash_value(p1) == hash_value(p2)."
1915   // Equality works as if by traversing the range [begin(), end()), meaning
1916   // e.g. path("a//b") == path("a/b"), so we cannot simply hash _M_pathname
1917   // but need to iterate over individual elements. Use the hash_combine from
1918   // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf
1919   size_t seed = 0;
1920   for (const auto& x : p)
1921     {
1922       seed ^= std::hash<path::string_type>()(x.native()) + 0x9e3779b9
1923         + (seed<<6) + (seed>>2);
1924     }
1925   return seed;
1926 }
1927
1928 struct fs::filesystem_error::_Impl
1929 {
1930   _Impl(const string& what_arg, const path& p1, const path& p2)
1931   : path1(p1), path2(p2), what(make_what(what_arg, &p1, &p2))
1932   { }
1933
1934   _Impl(const string& what_arg, const path& p1)
1935   : path1(p1), path2(), what(make_what(what_arg, &p1, nullptr))
1936   { }
1937
1938   _Impl(const string& what_arg)
1939   : what(make_what(what_arg, nullptr, nullptr))
1940   { }
1941
1942   static std::string
1943   make_what(const std::string& s, const path* p1, const path* p2)
1944   {
1945     const std::string pstr1 = p1 ? p1->u8string() : std::string{};
1946     const std::string pstr2 = p2 ? p2->u8string() : std::string{};
1947     const size_t len = 18 + s.length()
1948       + (pstr1.length() ? pstr1.length() + 3 : 0)
1949       + (pstr2.length() ? pstr2.length() + 3 : 0);
1950     std::string w;
1951     w.reserve(len);
1952     w = "filesystem error: ";
1953     w += s;
1954     if (p1)
1955       {
1956         w += " [";
1957         w += pstr1;
1958         w += ']';
1959         if (p2)
1960           {
1961             w += " [";
1962             w += pstr2;
1963             w += ']';
1964           }
1965       }
1966     return w;
1967   }
1968
1969   path path1;
1970   path path2;
1971   std::string what;
1972 };
1973
1974 template class std::__shared_ptr<const fs::filesystem_error::_Impl>;
1975
1976 fs::filesystem_error::
1977 filesystem_error(const string& what_arg, error_code ec)
1978 : system_error(ec, what_arg),
1979   _M_impl(std::__make_shared<_Impl>(what_arg))
1980 { }
1981
1982 fs::filesystem_error::
1983 filesystem_error(const string& what_arg, const path& p1, error_code ec)
1984 : system_error(ec, what_arg),
1985   _M_impl(std::__make_shared<_Impl>(what_arg, p1))
1986 { }
1987
1988 fs::filesystem_error::
1989 filesystem_error(const string& what_arg, const path& p1, const path& p2,
1990                  error_code ec)
1991 : system_error(ec, what_arg),
1992   _M_impl(std::__make_shared<_Impl>(what_arg, p1, p2))
1993 { }
1994
1995 fs::filesystem_error::~filesystem_error() = default;
1996
1997 const fs::path&
1998 fs::filesystem_error::path1() const noexcept
1999 { return _M_impl->path1; }
2000
2001 const fs::path&
2002 fs::filesystem_error::path2() const noexcept
2003 { return _M_impl->path2; }
2004
2005 const char*
2006 fs::filesystem_error::what() const noexcept
2007 { return _M_impl->what.c_str(); }