[gcc.git] / libstdc++-v3 / src / c++17 / fs_path.cc

// Class filesystem::path -*- C++ -*-

// Copyright (C) 2014-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

#ifndef _GLIBCXX_USE_CXX11_ABI
# define _GLIBCXX_USE_CXX11_ABI 1
#endif

#ifdef __CYGWIN__
// Interpret "//x" as a root-name, not root-dir + filename
# define SLASHSLASH_IS_ROOTNAME 1
#endif

#include <filesystem>
#include <algorithm>
#include <bits/stl_uninitialized.h>

namespace fs = std::filesystem;
using fs::path;

static inline bool is_dir_sep(path::value_type ch)
{
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
    return ch == L'/' || ch == path::preferred_separator;
#else
    return ch == '/';
#endif
}

#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
static inline bool is_disk_designator(std::wstring_view s)
{
  return s.length() == 2 && s[1] == L':';
}
#endif

struct path::_Parser
{
  using string_view_type = std::basic_string_view<value_type>;

  struct cmpt
  {
    string_view_type str;
    _Type type = _Type::_Multi;

    bool valid() const { return type != _Type::_Multi; }
  };

  string_view_type input;
  string_view_type::size_type pos = 0;
  size_t origin;
  _Type last_type = _Type::_Multi;

  _Parser(string_view_type s, size_t o = 0) : input(s), origin(o) { }

  pair<cmpt, cmpt> root_path() noexcept
  {
    pos = 0;
    pair<cmpt, cmpt> root;

    const size_t len = input.size();

    // look for root name or root directory
    if (is_dir_sep(input[0]))
      {
#if SLASHSLASH_IS_ROOTNAME
        // look for root name, such as "//foo"
        if (len > 2 && input[1] == input[0])
          {
            if (!is_dir_sep(input[2]))
              {
                // got root name, find its end
                pos = 3;
                while (pos < len && !is_dir_sep(input[pos]))
                  ++pos;
                root.first.str = input.substr(0, pos);
                root.first.type = _Type::_Root_name;

                if (pos < len) // also got root directory
                  {
                    root.second.str = input.substr(pos, 1);
                    root.second.type = _Type::_Root_dir;
                    ++pos;
                  }
              }
            else
              {
                // got something like "///foo" which is just a root directory
                // composed of multiple redundant directory separators
                root.first.str = input.substr(0, 1);
                root.first.type = _Type::_Root_dir;
                pos += 2;
              }
          }
        else
#endif
          {
            root.first.str = input.substr(0, 1);
            root.first.type = _Type::_Root_dir;
            ++pos;
          }
        // Find the start of the first filename
        while (pos < len && is_dir_sep(input[pos]))
          ++pos;
      }
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
    else if (is_disk_designator(input.substr(0, 2)))
      {
        // got disk designator
        root.first.str = input.substr(0, 2);
        root.first.type = _Type::_Root_name;
        if (len > 2 && is_dir_sep(input[2]))
          {
            root.second.str = input.substr(2, 1);
            root.second.type = _Type::_Root_dir;
          }
        pos = input.find_first_not_of(L"/\\", 2);
      }
#endif

    if (root.second.valid())
      last_type = root.second.type;
    else
      last_type = root.first.type;

    return root;
  }

  cmpt next() noexcept
  {
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
    string_view_type sep = L"/\\";
#else
    char sep = '/';
#endif

    const int last_pos = pos;

    cmpt f;
    if (pos != input.npos)
      {
        pos = input.find_first_not_of(sep, pos);
        if (pos != input.npos)
          {
            const auto end = input.find_first_of(sep, pos);
            f.str = input.substr(pos, end - pos);
            f.type = _Type::_Filename;
            pos = end;
          }
        else if (last_type == _Type::_Filename
            || (last_pos == 0 && !input.empty()))
          {
            // [fs.path.itr]/4 An empty element, if trailing non-root
            // directory-separator present.
            __glibcxx_assert(is_dir_sep(input.back()));
            f.str = input.substr(input.length(), 0);
            f.type = _Type::_Filename;
          }
      }
    last_type = f.type;
    return f;
  }

  string_view_type::size_type
  offset(const cmpt& c) const noexcept
  { return origin + c.str.data() - input.data(); }
};

struct path::_List::_Impl
{
  using value_type = _Cmpt;

  _Impl(int cap) : _M_size(0), _M_capacity(cap) { }

  alignas(value_type) int _M_size;
  int _M_capacity;

  using iterator = value_type*;
  using const_iterator = const value_type*;

  iterator begin() { return reinterpret_cast<value_type*>(this + 1); }
  iterator end() { return begin() + size(); }

  const_iterator begin() const
  { return reinterpret_cast<const value_type*>(this + 1); }
  const_iterator end() const { return begin() + size(); }

  const value_type& front() const { return *begin(); }
  const value_type& back() const { return end()[-1]; }

  int size() const { return _M_size; }
  int capacity() const { return _M_capacity; }
  bool empty() const { return _M_size == 0; }

  void clear() { std::destroy_n(begin(), _M_size); _M_size = 0; }

  void pop_back()
  {
    back().~_Cmpt();
    --_M_size;
  }

  void _M_erase_from(const_iterator pos)
  {
    iterator first = begin() + (pos - begin());
    iterator last = end();
    std::destroy(first, last);
    _M_size -= last - first;
  }

  unique_ptr<_Impl, _Impl_deleter> copy() const
  {
    const auto n = size();
    void* p = ::operator new(sizeof(_Impl) + n * sizeof(value_type));
    unique_ptr<_Impl, _Impl_deleter> newptr(::new (p) _Impl{n});
    std::uninitialized_copy_n(begin(), n, newptr->begin());
    newptr->_M_size = n;
    return newptr;
  }

  // Clear the lowest two bits from the pointer (i.e. remove the _Type value)
  static _Impl* notype(_Impl* p)
  {
    constexpr uintptr_t mask = ~(uintptr_t)0x3;
    return reinterpret_cast<_Impl*>(reinterpret_cast<uintptr_t>(p) & mask);
  }
};

void path::_List::_Impl_deleter::operator()(_Impl* p) const noexcept
{
  p = _Impl::notype(p);
  if (p)
    {
      __glibcxx_assert(p->_M_size <= p->_M_capacity);
      p->clear();
      ::operator delete(p, sizeof(*p) + p->_M_capacity * sizeof(value_type));
    }
}

path::_List::_List() : _M_impl(reinterpret_cast<_Impl*>(_Type::_Filename)) { }

path::_List::_List(const _List& other)
{
  if (!other.empty())
    _M_impl = other._M_impl->copy();
  else
    type(other.type());
}

path::_List&
path::_List::operator=(const _List& other)
{
  if (!other.empty())
    {
      // copy in-place if there is capacity
      const int newsize = other._M_impl->size();
      auto impl = _Impl::notype(_M_impl.get());
      if (impl && impl->capacity() >= newsize)
        {
          const int oldsize = impl->_M_size;
          auto to = impl->begin();
          auto from = other._M_impl->begin();
          const int minsize = std::min(newsize, oldsize);
          for (int i = 0; i < minsize; ++i)
            to[i]._M_pathname.reserve(from[i]._M_pathname.length());
          if (newsize > oldsize)
            {
              std::uninitialized_copy_n(from + oldsize, newsize - oldsize,
                                        to + oldsize);
              impl->_M_size = newsize;
            }
          else if (newsize < oldsize)
            impl->_M_erase_from(impl->begin() + newsize);
          std::copy_n(from, minsize, to);
          type(_Type::_Multi);
        }
      else
        _M_impl = other._M_impl->copy();
    }
  else
    {
      clear();
      type(other.type());
    }
  return *this;
}

inline void
path::_List::type(_Type t) noexcept
{
  auto val = reinterpret_cast<uintptr_t>(_Impl::notype(_M_impl.release()));
  _M_impl.reset(reinterpret_cast<_Impl*>(val | (unsigned char)t));
}

inline int
path::_List::size() const noexcept
{
  if (auto* ptr = _Impl::notype(_M_impl.get()))
    return ptr->size();
  return 0;
}

inline int
path::_List::capacity() const noexcept
{
  if (auto* ptr = _Impl::notype(_M_impl.get()))
    return ptr->capacity();
  return 0;
}

inline bool
path::_List::empty() const noexcept
{
  return size() == 0;
}

inline auto
path::_List::begin() noexcept
-> iterator
{
  __glibcxx_assert(!empty());
  if (auto* ptr = _Impl::notype(_M_impl.get()))
    return ptr->begin();
  return nullptr;
}

inline auto
path::_List::end() noexcept
-> iterator
{
  __glibcxx_assert(!empty());
  if (auto* ptr = _Impl::notype(_M_impl.get()))
    return ptr->end();
  return nullptr;
}

auto
path::_List::begin() const noexcept
-> const_iterator
{
  __glibcxx_assert(!empty());
  if (auto* ptr = _Impl::notype(_M_impl.get()))
    return ptr->begin();
  return nullptr;
}

auto
path::_List::end() const noexcept
-> const_iterator
{
  __glibcxx_assert(!empty());
  if (auto* ptr = _Impl::notype(_M_impl.get()))
    return ptr->end();
  return nullptr;
}

inline auto
path::_List::front() noexcept
-> value_type&
{
  return *_M_impl->begin();
}

inline auto
path::_List::back() noexcept
-> value_type&
{
  return _M_impl->begin()[_M_impl->size() - 1];
}

inline auto
path::_List::front() const noexcept
-> const value_type&
{
  return *_M_impl->begin();
}

inline auto
path::_List::back() const noexcept
-> const value_type&
{
  return _M_impl->begin()[_M_impl->size() - 1];
}

inline void
path::_List::pop_back()
{
  __glibcxx_assert(size() > 0);
  _M_impl->pop_back();
}

inline void
path::_List::_M_erase_from(const_iterator pos)
{
  _M_impl->_M_erase_from(pos);
}

inline void
path::_List::clear()
{
  if (auto ptr = _Impl::notype(_M_impl.get()))
    ptr->clear();
}

void
path::_List::reserve(int newcap, bool exact = false)
{
  // __glibcxx_assert(type() == _Type::_Multi);

  _Impl* curptr = _Impl::notype(_M_impl.get());

  int curcap = curptr ? curptr->capacity() : 0;

  if (curcap < newcap)
    {
      if (!exact && newcap < int(1.5 * curcap))
        newcap = 1.5 * curcap;

      void* p = ::operator new(sizeof(_Impl) + newcap * sizeof(value_type));
      std::unique_ptr<_Impl, _Impl_deleter> newptr(::new(p) _Impl{newcap});
      const int cursize = curptr ? curptr->size() : 0;
      if (cursize)
        {
          std::uninitialized_move_n(curptr->begin(), cursize, newptr->begin());
          newptr->_M_size = cursize;
        }
      std::swap(newptr, _M_impl);
    }
}

path&
path::operator=(const path& p)
{
  if (&p == this) [[__unlikely__]]
    return *this;

  _M_pathname.reserve(p._M_pathname.length());
  _M_cmpts = p._M_cmpts;        // might throw
  _M_pathname = p._M_pathname;  // won't throw because we reserved enough space
  return *this;
}

path&
path::operator/=(const path& __p)
{
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  if (__p.is_absolute()
      || (__p.has_root_name() && __p.root_name() != root_name()))
    return operator=(__p);

  basic_string_view<value_type> __lhs = _M_pathname;
  bool __add_sep = false;

  if (__p.has_root_directory())
    {
      // Remove any root directory and relative path
      if (_M_type() != _Type::_Root_name)
        {
          if (!_M_cmpts.empty()
              && _M_cmpts.front()._M_type() == _Type::_Root_name)
            __lhs = _M_cmpts.front()._M_pathname;
          else
            __lhs = {};
        }
    }
  else if (has_filename() || (!has_root_directory() && is_absolute()))
    __add_sep = true;

  basic_string_view<value_type> __rhs = __p._M_pathname;
  // Omit any root-name from the generic format pathname:
  if (__p._M_type() == _Type::_Root_name)
    __rhs = {};
  else if (!__p._M_cmpts.empty()
      && __p._M_cmpts.front()._M_type() == _Type::_Root_name)
    __rhs.remove_prefix(__p._M_cmpts.front()._M_pathname.size());

  const size_t __len = __lhs.size() + (int)__add_sep + __rhs.size();
  const int __maxcmpts = _M_cmpts.size() + __p._M_cmpts.size();
  if (_M_pathname.capacity() < __len || _M_cmpts.capacity() < __maxcmpts)
    {
      // Construct new path and swap (strong exception-safety guarantee).
      string_type __tmp;
      __tmp.reserve(__len);
      __tmp = __lhs;
      if (__add_sep)
        __tmp += preferred_separator;
      __tmp += __rhs;
      path __newp = std::move(__tmp);
      swap(__newp);
    }
  else
    {
      _M_pathname = __lhs;
      if (__add_sep)
        _M_pathname += preferred_separator;
      _M_pathname += __rhs;
      __try
        {
          _M_split_cmpts();
        }
      __catch (...)
        {
          __try
            {
              // try to restore original state
              _M_pathname.resize(__lhs.length());
              _M_split_cmpts();
            }
          __catch (...)
            {
              // give up, basic exception safety guarantee only:
              clear();
              __throw_exception_again;
            }
        }
    }
#else
  // POSIX version is simpler than the specification in the standard,
  // as any path with root-name or root-dir is absolute.

  if (__p.is_absolute() || this->empty())
    {
      return operator=(__p);
    }

  using string_view_type = basic_string_view<value_type>;

  string_view_type sep;
  if (has_filename())
    sep = { &preferred_separator, 1 };  // need to add a separator
#if SLASHSLASH_IS_ROOTNAME
  else if (_M_type() == _Type::_Root_name) // root-name with no root-dir
    sep = { &preferred_separator, 1 };  // need to add a separator
#endif
  else if (__p.empty())
    return *this;                           // nothing to do

  const auto orig_pathlen = _M_pathname.length();
  const auto orig_size = _M_cmpts.size();
  const auto orig_type = _M_type();

  int capacity = 0;
  if (_M_type() == _Type::_Multi)
    capacity += _M_cmpts.size();
  else if (!empty())
    capacity += 1;
  if (__p._M_type() == _Type::_Multi)
    capacity += __p._M_cmpts.size();
  else if (!__p.empty() || !sep.empty())
    capacity += 1;
#if SLASHSLASH_IS_ROOTNAME
  if (orig_type == _Type::_Root_name)
    ++capacity; // Need to insert root-directory after root-name
#endif

  if (orig_type == _Type::_Multi)
    {
      const int curcap = _M_cmpts._M_impl->capacity();
      if (capacity > curcap)
        capacity = std::max(capacity, (int) (curcap * 1.5));
    }

  _M_pathname.reserve(_M_pathname.length() + sep.length()
                      + __p._M_pathname.length());

  __try
    {
      _M_pathname += sep;
      const auto basepos = _M_pathname.length();
      _M_pathname += __p.native();

      _M_cmpts.type(_Type::_Multi);
      _M_cmpts.reserve(capacity);
      _Cmpt* output = _M_cmpts._M_impl->end();

      if (orig_type == _Type::_Multi)
        {
          // Remove empty final component
          if (_M_cmpts._M_impl->back().empty())
            {
              _M_cmpts.pop_back();
              --output;
            }
        }
      else if (orig_pathlen != 0)
        {
          // Create single component from original path
          string_view_type s(_M_pathname.data(), orig_pathlen);
          ::new(output++) _Cmpt(s, orig_type, 0);
          ++_M_cmpts._M_impl->_M_size;
#if SLASHSLASH_IS_ROOTNAME
          if (orig_type == _Type::_Root_name)
            {
              ::new(output++) _Cmpt(sep, _Type::_Root_dir,
                                    orig_pathlen + sep.length());
              ++_M_cmpts._M_impl->_M_size;
            }
#endif
        }

      if (__p._M_type() == _Type::_Multi)
        {
          for (auto& c : *__p._M_cmpts._M_impl)
            {
              ::new(output++) _Cmpt(c._M_pathname, _Type::_Filename,
                                    c._M_pos + basepos);
              ++_M_cmpts._M_impl->_M_size;
            }
        }
      else if (!__p.empty() || !sep.empty())
        {
          __glibcxx_assert(__p._M_type() == _Type::_Filename);
          ::new(output) _Cmpt(__p._M_pathname, __p._M_type(), basepos);
          ++_M_cmpts._M_impl->_M_size;
        }
    }
  __catch (...)
    {
      _M_pathname.resize(orig_pathlen);
      if (orig_type == _Type::_Multi)
        _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
      else
        _M_cmpts.clear();
      _M_cmpts.type(orig_type);
      __throw_exception_again;
    }
#endif
  return *this;
}

// [fs.path.append]
void
path::_M_append(basic_string_view<value_type> s)
{
  _Parser parser(s);
  auto root_path = parser.root_path();

#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  bool is_absolute = root_path.second.type == _Type::_Root_dir;
  bool has_root_name = root_path.first.type == _Type::_Root_name;
  if (is_absolute || (has_root_name && root_path.first.str != root_name()))
    {
      operator=(s);
      return;
    }

  basic_string_view<value_type> lhs = _M_pathname;
  bool add_sep = false;

  bool has_root_directory = root_path.first.type == _Type::_Root_dir
    || root_path.second.type == _Type::_Root_dir;

  if (has_root_directory)
    {
      // Remove any root directory and relative path
      if (_M_type() != _Type::_Root_name)
        {
          if (!_M_cmpts.empty()
              && _M_cmpts.front()._M_type() == _Type::_Root_name)
            lhs = _M_cmpts.front()._M_pathname;
          else
            lhs = {};
        }
    }
  else if (has_filename() || (!has_root_directory && is_absolute))
    add_sep = true;

  basic_string_view<value_type> rhs = s;
  // Omit any root-name from the generic format pathname:
  if (has_root_name)
    rhs.remove_prefix(root_path.first.str.length());

  // Construct new path and swap (strong exception-safety guarantee).
  string_type tmp;
  tmp.reserve(lhs.size() + (int)add_sep + rhs.size());
  tmp = lhs;
  if (add_sep)
    tmp += preferred_separator;
  tmp += rhs;
  path newp = std::move(tmp);
  swap(newp);
#else

  bool is_absolute = root_path.first.type == _Type::_Root_dir
    || root_path.second.type == _Type::_Root_dir;
  if (is_absolute || this->empty())
    {
      operator=(s);
      return;
    }

  const auto orig_pathlen = _M_pathname.length();
  const auto orig_size = _M_cmpts.size();
  const auto orig_type = _M_type();

  basic_string_view<value_type> sep;
  if (has_filename())
    sep = { &preferred_separator, 1 };  // need to add a separator
#if SLASHSLASH_IS_ROOTNAME
  else if (_M_type() == _Type::_Root_name) // root-name with no root-dir
    sep = { &preferred_separator, 1 };  // need to add a separator
#endif
  else if (s.empty())
    return;                         // nothing to do

  // Copy the input into _M_pathname:
  _M_pathname += s;
  _M_pathname.insert(orig_pathlen, sep);
  // Update s to refer to the new copy (this ensures s is not a dangling
  // reference to deallocated characters, in the case where it was referring
  // into _M_pathname or a member of _M_cmpts).
  s = _M_pathname;
  const auto orig_pathname = s.substr(0, orig_pathlen);
  s.remove_prefix(orig_pathlen + sep.length());

  parser.input = s; // reset parser to use updated string view
  const auto basepos = orig_pathname.length() + sep.length();
  parser.origin = basepos;

  std::array<_Parser::cmpt, 64> buf;
  auto next = buf.begin();

  int capacity = 0;
  if (_M_type() == _Type::_Multi)
    capacity += _M_cmpts.size();
  else if (!empty())
    capacity += 1;

  auto cmpt = parser.next();
  if (cmpt.valid())
    {
      do
        {
          *next++ = cmpt;
          cmpt = parser.next();
        }
      while (cmpt.valid() && next != buf.end());

      capacity += next - buf.begin();
      if (cmpt.valid()) // filled buffer before parsing whole input
        {
          ++capacity;
          _Parser parser2(parser);
          while (parser2.next().valid())
            ++capacity;
        }
    }
  else if (!sep.empty())
    ++capacity;

#if SLASHSLASH_IS_ROOTNAME
  if (orig_type == _Type::_Root_name)
    ++capacity; // Need to insert root-directory after root-name
#endif

  __try
    {
      _M_cmpts.type(_Type::_Multi);
      _M_cmpts.reserve(capacity);
      _Cmpt* output = _M_cmpts._M_impl->end();

      if (orig_type == _Type::_Multi)
        {
          // Remove empty final component
          if (_M_cmpts._M_impl->back().empty())
            {
              _M_cmpts.pop_back();
              --output;
            }
        }
      else if (orig_pathlen != 0)
        {
          // Create single component from original path
          ::new(output++) _Cmpt(orig_pathname, orig_type, 0);
          ++_M_cmpts._M_impl->_M_size;

#if SLASHSLASH_IS_ROOTNAME
          if (!sep.empty() && orig_type == _Type::_Root_name)
            {
              ::new(output++) _Cmpt(sep, _Type::_Root_dir,
                                    orig_pathlen + sep.length());
              ++_M_cmpts._M_impl->_M_size;
            }
#endif
        }

      if (next != buf.begin())
        {
          for (auto it = buf.begin(); it != next; ++it)
            {
              auto c = *it;
              ::new(output++) _Cmpt(c.str, c.type, parser.offset(c));
              ++_M_cmpts._M_impl->_M_size;
            }
          while (cmpt.valid())
            {
              ::new(output++) _Cmpt(cmpt.str, cmpt.type, parser.offset(cmpt));
              ++_M_cmpts._M_impl->_M_size;
              cmpt = parser.next();
            }
        }
      else if (!sep.empty())
        {
          // Empty filename at the end:
          ::new(output) _Cmpt({}, _Type::_Filename, basepos);
          ++_M_cmpts._M_impl->_M_size;
        }
    }
  __catch (...)
    {
      _M_pathname.resize(orig_pathlen);
      if (orig_type == _Type::_Multi)
        _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
      else
        _M_cmpts.clear();
      _M_cmpts.type(orig_type);
      __throw_exception_again;
    }
#endif
}

// [fs.path.concat]
path&
path::operator+=(const path& p)
{
  if (p.empty())
    return *this;

  if (this->empty())
    {
      operator=(p);
      return *this;
    }

#if _GLIBCXX_FILESYSTEM_IS_WINDOWS
  if (_M_type() == _Type::_Root_name
      || (_M_type() == _Type::_Filename && _M_pathname.size() == 1))
    {
      // Handle path("C") += path(":") and path("C:") += path("/x")
      // FIXME: do this more efficiently
      *this = path(_M_pathname + p._M_pathname);
      return *this;
    }
#endif
#if SLASHSLASH_IS_ROOTNAME
  if (_M_type() == _Type::_Root_dir)
    {
      // Handle path("/") += path("/x") and path("//") += path("x")
      // FIXME: do this more efficiently
      *this = path(_M_pathname + p._M_pathname);
      return *this;
    }
#endif

  const auto orig_pathlen = _M_pathname.length();
  const auto orig_type = _M_type();
  const auto orig_size = _M_cmpts.size();
  int orig_filenamelen = -1;
  basic_string_view<value_type> extra;

  // Ensure that '_M_pathname += p._M_pathname' won't throw:
  _M_pathname.reserve(orig_pathlen + p._M_pathname.length());

  _Cmpt c;
  _Cmpt* it = nullptr;
  _Cmpt* last = nullptr;
  if (p._M_type() == _Type::_Multi)
    {
      it = p._M_cmpts._M_impl->begin();
      last = p._M_cmpts._M_impl->end();
    }
  else
    {
      c = _Cmpt(p._M_pathname, p._M_type(), 0);
      it = &c;
      last = it + 1;
    }

  if (it->_M_type() == _Type::_Filename)
    {
      // See if there's a filename or root-name at the end of the original path
      // that we can add to.
      if (_M_type() == _Type::_Filename
#if SLASHSLASH_IS_ROOTNAME
          || _M_type() == _Type::_Root_name
#endif
          )
        {
          if (p._M_type() == _Type::_Filename)
            {
              // Simplest case where we just add the whole of p to the
              // original path.
              _M_pathname += p._M_pathname;
              return *this;
            }
          // Only the first component of s should be appended, do so below:
          extra = it->_M_pathname;
          ++it;
        }
      else if (_M_type() == _Type::_Multi
          && _M_cmpts.back()._M_type() == _Type::_Filename)
        {
          auto& back = _M_cmpts.back();
          if (p._M_type() == _Type::_Filename)
            {
              basic_string_view<value_type> s = p._M_pathname;
              back._M_pathname += s;
              _M_pathname += s;
              return *this;
            }

          orig_filenamelen = back._M_pathname.length();
          back._M_pathname += it->_M_pathname;
          extra = it->_M_pathname;
          ++it;
        }
    }
  else if (is_dir_sep(_M_pathname.back()) && _M_type() == _Type::_Multi
      && _M_cmpts.back()._M_type() == _Type::_Filename)
    orig_filenamelen = 0; // current path has empty filename at end

  int capacity = 0;
  if (_M_type() == _Type::_Multi)
    capacity += _M_cmpts.size();
  else
    capacity += 1;
  if (p._M_type() == _Type::_Multi)
    capacity += p._M_cmpts.size();
  else
    capacity += 1;

  __try
    {
      _M_cmpts.type(_Type::_Multi);
      _M_cmpts.reserve(capacity);
      _Cmpt* output = _M_cmpts._M_impl->end();

      if (orig_type != _Type::_Multi)
        {
          // Create single component from original path
          auto ptr = ::new(output++) _Cmpt({}, orig_type, 0);
          ++_M_cmpts._M_impl->_M_size;
          ptr->_M_pathname.reserve(_M_pathname.length() + extra.length());
          ptr->_M_pathname = _M_pathname;
          ptr->_M_pathname += extra;

#if SLASHSLASH_IS_ROOTNAME
          if (orig_type == _Type::_Root_name)
            {
              basic_string_view<value_type> s(p._M_pathname);
              ::new(output++) _Cmpt(s.substr(extra.length(), 1),
                  _Type::_Root_dir, orig_pathlen + extra.length());
              ++_M_cmpts._M_impl->_M_size;
            }
#endif
        }
      else if (orig_filenamelen == 0 && it != last)
        {
          // Remove empty filename at end of original path.
          _M_cmpts.pop_back();
          --output;
        }

      if (it != last && it->_M_type() == _Type::_Root_name)
        {
          basic_string_view<value_type> s = it->_M_pathname;
          auto pos = orig_pathlen;
#if SLASHSLASH_IS_ROOTNAME
          s.remove_prefix(2);
          pos += 2;
#endif
          ::new(output++) _Cmpt(s, _Type::_Filename, pos);
          ++_M_cmpts._M_impl->_M_size;
          ++it;
        }

      if (it != last && it->_M_type() == _Type::_Root_dir)
        ++it;

      while (it != last)
        {
          auto pos = it->_M_pos + orig_pathlen;
          ::new(output++) _Cmpt(it->_M_pathname, _Type::_Filename, pos);
          ++_M_cmpts._M_impl->_M_size;
          ++it;
        }

      _M_pathname += p._M_pathname;

      if (is_dir_sep(_M_pathname.back()))
        {
          ::new(output++) _Cmpt({}, _Type::_Filename, _M_pathname.length());
          ++_M_cmpts._M_impl->_M_size;
        }
      }
  __catch (...)
    {
      _M_pathname.resize(orig_pathlen);
      if (orig_type == _Type::_Multi)
        {
          if (_M_cmpts.size() > orig_size)
            _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
          if (orig_filenamelen != -1)
            {
              if (_M_cmpts.size() == orig_size)
                {
                  auto& back = _M_cmpts.back();
                  back._M_pathname.resize(orig_filenamelen);
                  if (orig_filenamelen == 0)
                    back._M_pos = orig_pathlen;
                }
              else
                {
                  auto output = _M_cmpts._M_impl->end();
                  ::new(output) _Cmpt({}, _Type::_Filename, orig_pathlen);
                  ++_M_cmpts._M_impl->_M_size;
                }
            }
        }
      else
        _M_cmpts.clear();
      _M_cmpts.type(orig_type);
      __throw_exception_again;
    }
  return *this;
}

// [fs.path.concat]
void
path::_M_concat(basic_string_view<value_type> s)
{
  if (s.empty())
    return;

  if (this->empty())
    {
      operator=(s);
      return;
    }

#if _GLIBCXX_FILESYSTEM_IS_WINDOWS
  if (_M_type() == _Type::_Root_name
      || (_M_type() == _Type::_Filename && _M_pathname.size() == 1))
    {
      // Handle path("C") += ":" and path("C:") += "/x"
      // FIXME: do this more efficiently
      *this = path(_M_pathname + string_type(s));
      return;
    }
#endif
#if SLASHSLASH_IS_ROOTNAME
  if (_M_type() == _Type::_Root_dir)
    {
      // Handle path("/") += "/x" and path("//") += "x"
      // FIXME: do this more efficiently
      *this = path(_M_pathname + string_type(s));
      return;
    }
#endif

  const auto orig_pathlen = _M_pathname.length();
  const auto orig_type = _M_type();
  const auto orig_size = _M_cmpts.size();
  int orig_filenamelen = -1;
  basic_string_view<value_type> extra;

  // Copy the input into _M_pathname:
  _M_pathname += s;
  // Update s to refer to the new copy (this ensures s is not a dangling
  // reference to deallocated characters, in the case where it was referring
  // into _M_pathname or a member of _M_cmpts).
  s = _M_pathname;
  const auto orig_pathname = s.substr(0, orig_pathlen);
  s.remove_prefix(orig_pathlen);

  _Parser parser(s, orig_pathlen);
  auto cmpt = parser.next();

  if (cmpt.str.data() == s.data())
    {
      // See if there's a filename or root-name at the end of the original path
      // that we can add to.
      if (_M_type() == _Type::_Filename
#if SLASHSLASH_IS_ROOTNAME
          || _M_type() == _Type::_Root_name
#endif
          )
        {
          if (cmpt.str.length() == s.length())
            {
              // Simplest case where we just need to add the whole of s
              // to the original path, which was already done above.
              return;
            }
          // Only the first component of s should be appended, do so below:
          extra = cmpt.str;
          cmpt = {}; // so we don't process it again
        }
      else if (_M_type() == _Type::_Multi
          && _M_cmpts.back()._M_type() == _Type::_Filename)
        {
          auto& back = _M_cmpts.back();
          if (cmpt.str.length() == s.length())
            {
              back._M_pathname += s;
              return;
            }

          orig_filenamelen = back._M_pathname.length();
          back._M_pathname += cmpt.str;
          extra = cmpt.str;
          cmpt = {};
        }
    }
  else if (is_dir_sep(orig_pathname.back()) && _M_type() == _Type::_Multi
      && _M_cmpts.back()._M_type() == _Type::_Filename)
    orig_filenamelen = 0; // original path had empty filename at end

  std::array<_Parser::cmpt, 64> buf;
  auto next = buf.begin();

  if (cmpt.valid())
    *next++ = cmpt;

  cmpt = parser.next();
  while (cmpt.valid() && next != buf.end())
    {
      *next++ = cmpt;
      cmpt = parser.next();
    }

  int capacity = 0;
  if (_M_type() == _Type::_Multi)
    capacity += _M_cmpts.size();
  else
    capacity += 1;

  capacity += next - buf.begin();

  if (cmpt.valid()) // filled buffer before parsing whole input
    {
      ++capacity;
      _Parser parser2(parser);
      while (parser2.next().valid())
        ++capacity;
    }

#if SLASHSLASH_IS_ROOTNAME
  if (orig_type == _Type::_Root_name)
    ++capacity; // Need to insert root-directory after root-name
#endif

  __try
    {
      _M_cmpts.type(_Type::_Multi);
      _M_cmpts.reserve(capacity);
      _Cmpt* output = _M_cmpts._M_impl->end();
      auto it = buf.begin();

      if (orig_type != _Type::_Multi)
        {
          // Create single component from original path
          auto p = ::new(output++) _Cmpt({}, orig_type, 0);
          ++_M_cmpts._M_impl->_M_size;
          p->_M_pathname.reserve(orig_pathname.length() + extra.length());
          p->_M_pathname = orig_pathname;
          p->_M_pathname += extra;

#if SLASHSLASH_IS_ROOTNAME
          if (orig_type == _Type::_Root_name)
            {
              ::new(output++) _Cmpt(s.substr(extra.length(), 1),
                  _Type::_Root_dir, orig_pathlen + extra.length());
              ++_M_cmpts._M_impl->_M_size;
            }
#endif
        }
      else if (orig_filenamelen == 0 && extra.empty())
        {
          // Replace empty filename at end of original path.
          std::prev(output)->_M_pathname = it->str;
          std::prev(output)->_M_pos = parser.offset(*it);
          ++it;
        }

      while (it != next)
        {
          ::new(output++) _Cmpt(it->str, _Type::_Filename, parser.offset(*it));
          ++_M_cmpts._M_impl->_M_size;
          ++it;
        }

      if (next == buf.end())
        {
          while (cmpt.valid())
            {
              auto pos = parser.offset(cmpt);
              ::new(output++) _Cmpt(cmpt.str, _Type::_Filename, pos);
              ++_M_cmpts._M_impl->_M_size;
              cmpt = parser.next();
            }
        }
    }
  __catch (...)
    {
      _M_pathname.resize(orig_pathlen);
      if (orig_type == _Type::_Multi)
        {
          _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
          if (orig_filenamelen != -1)
            {
              auto& back = _M_cmpts.back();
              back._M_pathname.resize(orig_filenamelen);
              if (orig_filenamelen == 0)
                back._M_pos = orig_pathlen;
            }
        }
      else
        _M_cmpts.clear();
      _M_cmpts.type(orig_type);
      __throw_exception_again;
    }
}

path&
path::remove_filename()
{
  if (_M_type() == _Type::_Multi)
    {
      if (!_M_cmpts.empty())
        {
          auto cmpt = std::prev(_M_cmpts.end());
          if (cmpt->_M_type() == _Type::_Filename && !cmpt->empty())
            {
              _M_pathname.erase(cmpt->_M_pos);
              auto prev = std::prev(cmpt);
              if (prev->_M_type() == _Type::_Root_dir
                  || prev->_M_type() == _Type::_Root_name)
                {
                  _M_cmpts.pop_back();
                  if (_M_cmpts.size() == 1)
                    {
                      _M_cmpts.type(_M_cmpts.front()._M_type());
                      _M_cmpts.clear();
                    }
                }
              else
                cmpt->clear();
            }
        }
    }
  else if (_M_type() == _Type::_Filename)
    clear();
  return *this;
}

path&
path::replace_filename(const path& replacement)
{
  remove_filename();
  operator/=(replacement);
  return *this;
}

#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
const fs::path::value_type dot = L'.';
#else
const fs::path::value_type dot = '.';
#endif

path&
path::replace_extension(const path& replacement)
{
  auto ext = _M_find_extension();
  // Any existing extension() is removed
  if (ext.first && ext.second != string_type::npos)
    {
      if (ext.first == &_M_pathname)
        _M_pathname.erase(ext.second);
      else
        {
          auto& back = _M_cmpts.back();
          __glibcxx_assert( ext.first == &back._M_pathname );
          back._M_pathname.erase(ext.second);
          _M_pathname.erase(back._M_pos + ext.second);
        }
    }
   // If replacement is not empty and does not begin with a dot character,
   // a dot character is appended
  if (!replacement.empty() && replacement.native()[0] != dot)
    operator+=(".");
  operator+=(replacement);
  return *this;
}

int
path::compare(const path& p) const noexcept
{
  if (_M_pathname == p._M_pathname)
    return 0;

  basic_string_view<value_type> lroot, rroot;
  if (_M_type() == _Type::_Root_name)
    lroot = _M_pathname;
  else if (_M_type() == _Type::_Multi
      && _M_cmpts.front()._M_type() == _Type::_Root_name)
    lroot = _M_cmpts.front()._M_pathname;
  if (p._M_type() == _Type::_Root_name)
    rroot = p._M_pathname;
  else if (p._M_type() == _Type::_Multi
      && p._M_cmpts.front()._M_type() == _Type::_Root_name)
    rroot = p._M_cmpts.front()._M_pathname;
  if (int rootNameComparison = lroot.compare(rroot))
    return rootNameComparison;

  if (!this->has_root_directory() && p.has_root_directory())
    return -1;
  else if (this->has_root_directory() && !p.has_root_directory())
    return +1;

  using Iterator = const _Cmpt*;
  Iterator begin1, end1, begin2, end2;
  if (_M_type() == _Type::_Multi)
    {
      begin1 = _M_cmpts.begin();
      end1 = _M_cmpts.end();
      // Find start of this->relative_path()
      while (begin1 != end1 && begin1->_M_type() != _Type::_Filename)
        ++begin1;
    }
  else
    begin1 = end1 = nullptr;

  if (p._M_type() == _Type::_Multi)
    {
      begin2 = p._M_cmpts.begin();
      end2 = p._M_cmpts.end();
      // Find start of p.relative_path()
      while (begin2 != end2 && begin2->_M_type() != _Type::_Filename)
        ++begin2;
    }
  else
    begin2 = end2 = nullptr;

  if (_M_type() == _Type::_Filename)
    {
      if (p._M_type() == _Type::_Filename)
        return native().compare(p.native());
      else if (begin2 != end2)
        {
          if (int ret = native().compare(begin2->native()))
            return ret;
          else
            return ++begin2 == end2 ? 0 : -1;
        }
      else
        return +1;
    }
  else if (p._M_type() == _Type::_Filename)
    {
      if (begin1 != end1)
        {
          if (int ret = begin1->native().compare(p.native()))
            return ret;
          else
            return ++begin1 == end1 ? 0 : +1;
        }
      else
        return -1;
    }

  int count = 1;
  while (begin1 != end1 && begin2 != end2)
    {
      if (int i = begin1->native().compare(begin2->native()))
        return i;
      ++begin1;
      ++begin2;
      ++count;
    }
  if (begin1 == end1)
    {
      if (begin2 == end2)
        return 0;
      return -count;
    }
  return count;
}

int
path::compare(basic_string_view<value_type> s) const noexcept
{
  if (_M_pathname == s)
    return 0;

  _Parser parser(s);

  basic_string_view<value_type> lroot, rroot;
  if (_M_type() == _Type::_Root_name)
    lroot = _M_pathname;
  else if (_M_type() == _Type::_Multi
      && _M_cmpts.front()._M_type() == _Type::_Root_name)
    lroot = _M_cmpts.front()._M_pathname;
  auto root_path = parser.root_path();
  if (root_path.first.type == _Type::_Root_name)
    rroot = root_path.first.str;
  if (int rootNameComparison = lroot.compare(rroot))
    return rootNameComparison;

  const bool has_root_dir = root_path.first.type == _Type::_Root_dir
    || root_path.second.type == _Type::_Root_dir;
  if (!this->has_root_directory() && has_root_dir)
    return -1;
  else if (this->has_root_directory() && !has_root_dir)
    return +1;

  using Iterator = const _Cmpt*;
  Iterator begin1, end1;
  if (_M_type() == _Type::_Filename)
    {
      auto cmpt = parser.next();
      if (cmpt.valid())
        {
          if (int ret = this->native().compare(cmpt.str))
            return ret;
          return parser.next().valid() ? -1 : 0;
        }
      else
        return +1;
    }
  else if (_M_type() == _Type::_Multi)
    {
      begin1 = _M_cmpts.begin();
      end1 = _M_cmpts.end();
      while (begin1 != end1 && begin1->_M_type() != _Type::_Filename)
        ++begin1;
    }
  else
    begin1 = end1 = nullptr;

  int count = 1;
  auto cmpt = parser.next();
  while (begin1 != end1 && cmpt.valid())
    {
      if (int i = begin1->native().compare(cmpt.str))
        return i;
      ++begin1;
      cmpt = parser.next();
      ++count;
    }
  if (begin1 == end1)
    {
      if (!cmpt.valid())
        return 0;
      return -count;
    }
  return +count;
}

path
path::root_name() const
{
  path __ret;
  if (_M_type() == _Type::_Root_name)
    __ret = *this;
  else if (_M_cmpts.size() && _M_cmpts.begin()->_M_type() == _Type::_Root_name)
    __ret = *_M_cmpts.begin();
  return __ret;
}

path
path::root_directory() const
{
  path __ret;
  if (_M_type() == _Type::_Root_dir)
    {
      __ret._M_cmpts.type(_Type::_Root_dir);
      __ret._M_pathname.assign(1, preferred_separator);
    }
  else if (!_M_cmpts.empty())
    {
      auto __it = _M_cmpts.begin();
      if (__it->_M_type() == _Type::_Root_name)
        ++__it;
      if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
        __ret = *__it;
    }
  return __ret;
}

path
path::root_path() const
{
  path __ret;
  if (_M_type() == _Type::_Root_name)
    __ret = *this;
  else if (_M_type() == _Type::_Root_dir)
    {
      __ret._M_pathname.assign(1, preferred_separator);
      __ret._M_cmpts.type(_Type::_Root_dir);
    }
  else if (!_M_cmpts.empty())
    {
      auto __it = _M_cmpts.begin();
      if (__it->_M_type() == _Type::_Root_name)
        {
          __ret = *__it++;
          if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
            __ret /= *__it;
        }
      else if (__it->_M_type() == _Type::_Root_dir)
        __ret = *__it;
    }
  return __ret;
}

path
path::relative_path() const
{
  path __ret;
  if (_M_type() == _Type::_Filename)
    __ret = *this;
  else if (!_M_cmpts.empty())
    {
      auto __it = _M_cmpts.begin();
      if (__it->_M_type() == _Type::_Root_name)
        ++__it;
      if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
        ++__it;
      if (__it != _M_cmpts.end())
        __ret.assign(_M_pathname.substr(__it->_M_pos));
    }
  return __ret;
}

path
path::parent_path() const
{
  path __ret;
  if (!has_relative_path())
    __ret = *this;
  else if (_M_cmpts.size() >= 2)
    {
      const auto parent = std::prev(_M_cmpts.end(), 2);
      const auto len = parent->_M_pos + parent->_M_pathname.length();
      __ret.assign(_M_pathname.substr(0, len));
    }
  return __ret;
}

bool
path::has_root_name() const noexcept
{
  if (_M_type() == _Type::_Root_name)
    return true;
  if (!_M_cmpts.empty() && _M_cmpts.begin()->_M_type() == _Type::_Root_name)
    return true;
  return false;
}

bool
path::has_root_directory() const noexcept
{
  if (_M_type() == _Type::_Root_dir)
    return true;
  if (!_M_cmpts.empty())
    {
      auto __it = _M_cmpts.begin();
      if (__it->_M_type() == _Type::_Root_name)
        ++__it;
      if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
        return true;
    }
  return false;
}

bool
path::has_root_path() const noexcept
{
  if (_M_type() == _Type::_Root_name || _M_type() == _Type::_Root_dir)
    return true;
  if (!_M_cmpts.empty())
    {
      auto __type = _M_cmpts.front()._M_type();
      if (__type == _Type::_Root_name || __type == _Type::_Root_dir)
        return true;
    }
  return false;
}

bool
path::has_relative_path() const noexcept
{
  if (_M_type() == _Type::_Filename && !_M_pathname.empty())
    return true;
  if (!_M_cmpts.empty())
    {
      auto __it = _M_cmpts.begin();
      if (__it->_M_type() == _Type::_Root_name)
        ++__it;
      if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
        ++__it;
      if (__it != _M_cmpts.end() && !__it->_M_pathname.empty())
        return true;
    }
  return false;
}


bool
path::has_parent_path() const noexcept
{
  if (!has_relative_path())
    return !empty();
  return _M_cmpts.size() >= 2;
}

bool
path::has_filename() const noexcept
{
  if (empty())
    return false;
  if (_M_type() == _Type::_Filename)
    return !_M_pathname.empty();
  if (_M_type() == _Type::_Multi)
    {
      if (_M_pathname.back() == preferred_separator)
        return false;
      return _M_cmpts.back().has_filename();
    }
  return false;
}

namespace
{
  inline bool is_dot(fs::path::value_type c) { return c == dot; }

  inline bool is_dot(const fs::path& path)
  {
    const auto& filename = path.native();
    return filename.size() == 1 && is_dot(filename[0]);
  }

  inline bool is_dotdot(const fs::path& path)
  {
    const auto& filename = path.native();
    return filename.size() == 2 && is_dot(filename[0]) && is_dot(filename[1]);
  }
} // namespace

path
path::lexically_normal() const
{
  /*
  C++17 [fs.path.generic] p6
  - If the path is empty, stop.
  - Replace each slash character in the root-name with a preferred-separator.
  - Replace each directory-separator with a preferred-separator.
  - Remove each dot filename and any immediately following directory-separator.
  - As long as any appear, remove a non-dot-dot filename immediately followed
    by a directory-separator and a dot-dot filename, along with any immediately
    following directory-separator.
  - If there is a root-directory, remove all dot-dot filenames and any
    directory-separators immediately following them.
  - If the last filename is dot-dot, remove any trailing directory-separator.
  - If the path is empty, add a dot.
  */
  path ret;
  // If the path is empty, stop.
  if (empty())
    return ret;
  for (auto& p : *this)
    {
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
      // Replace each slash character in the root-name
      if (p._M_type() == _Type::_Root_name || p._M_type() == _Type::_Root_dir)
        {
          string_type s = p.native();
          std::replace(s.begin(), s.end(), L'/', L'\\');
          ret /= s;
          continue;
        }
#endif
      if (is_dotdot(p))
        {
          if (ret.has_filename())
            {
              // remove a non-dot-dot filename immediately followed by /..
              if (!is_dotdot(ret.filename()))
                ret.remove_filename();
              else
                ret /= p;
            }
          else if (!ret.has_relative_path())
            {
              // remove a dot-dot filename immediately after root-directory
              if (!ret.has_root_directory())
                ret /= p;
            }
          else
            {
              // Got a path with a relative path (i.e. at least one non-root
              // element) and no filename at the end (i.e. empty last element),
              // so must have a trailing slash. See what is before it.
              auto elem = ret._M_cmpts.end() - 2;
              if (elem->has_filename() && !is_dotdot(*elem))
                {
                  // Remove the filename before the trailing slash
                  // (equiv. to ret = ret.parent_path().remove_filename())

                  if (elem == ret._M_cmpts.begin())
                    ret.clear();
                  else
                    {
                      ret._M_pathname.erase(elem->_M_pos);
                      // Remove empty filename at the end:
                      ret._M_cmpts.pop_back();
                      // If we still have a trailing non-root dir separator
                      // then leave an empty filename at the end:
                      if (std::prev(elem)->_M_type() == _Type::_Filename)
                        elem->clear();
                      else // remove the component completely:
                        ret._M_cmpts.pop_back();
                    }
                }
              else
                // Append the ".." to something ending in "../" which happens
                // when normalising paths like ".././.." and "../a/../.."
                ret /= p;
            }
        }
      else if (is_dot(p))
        ret /= path();
#if SLASHSLASH_IS_ROOTNAME
      else if (p._M_type() == _Type::_Root_dir)
        ret += '/'; // using operator/=('/') would replace whole of ret
#endif
      else
        ret /= p;
    }

  if (ret._M_cmpts.size() >= 2)
    {
      auto back = std::prev(ret.end());
      // If the last filename is dot-dot, ...
      if (back->empty() && is_dotdot(*std::prev(back)))
        // ... remove any trailing directory-separator.
        ret = ret.parent_path();
    }
  // If the path is empty, add a dot.
  else if (ret.empty())
    ret = ".";

  return ret;
}

path
path::lexically_relative(const path& base) const
{
  path ret;
  if (root_name() != base.root_name())
    return ret;
  if (is_absolute() != base.is_absolute())
    return ret;
  if (!has_root_directory() && base.has_root_directory())
    return ret;
  auto [a, b] = std::mismatch(begin(), end(), base.begin(), base.end());
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 3070. path::lexically_relative causes surprising results if a filename
  // can also be a root-name
  if (!empty())
    for (auto& p : _M_cmpts)
      if (p._M_type() == _Type::_Filename && is_disk_designator(p.native()))
        return ret;
  if (!base.empty())
    for (auto i = b, end = base.end(); i != end; ++i)
      if (i->_M_type() == _Type::_Filename && is_disk_designator(i->native()))
        return ret;
#endif
  if (a == end() && b == base.end())
    ret = ".";
  else
  {
    int n = 0;
    for (; b != base.end(); ++b)
    {
      const path& p = *b;
      if (is_dotdot(p))
        --n;
      else if (!p.empty() && !is_dot(p))
        ++n;
    }
    if (n == 0 && (a == end() || a->empty()))
      ret = ".";
    else if (n >= 0)
    {
      const path dotdot("..");
      while (n--)
        ret /= dotdot;
      for (; a != end(); ++a)
        ret /= *a;
    }
  }
  return ret;
}

path
path::lexically_proximate(const path& base) const
{
  path rel = lexically_relative(base);
  if (rel.empty())
    rel = *this;
  return rel;
}

std::pair<const path::string_type*, std::size_t>
path::_M_find_extension() const noexcept
{
  const string_type* s = nullptr;

  if (_M_type() == _Type::_Filename)
    s = &_M_pathname;
  else if (_M_type() == _Type::_Multi && !_M_cmpts.empty())
    {
      const auto& c = _M_cmpts.back();
      if (c._M_type() == _Type::_Filename)
        s = &c._M_pathname;
    }

  if (s)
    {
      if (auto sz = s->size())
        {
          if (sz <= 2 && (*s)[0] == dot)
            return { s, string_type::npos };
          if (const auto pos = s->rfind(dot))
            return { s , pos };
          return { s, string_type::npos };
        }
    }
  return {};
}

void
path::_M_split_cmpts()
{
  _M_cmpts.clear();

  if (_M_pathname.empty())
    {
      _M_cmpts.type(_Type::_Filename);
      return;
    }
  if (_M_pathname.length() == 1 && _M_pathname[0] == preferred_separator)
    {
      _M_cmpts.type(_Type::_Root_dir);
      return;
    }

  _Parser parser(_M_pathname);

  std::array<_Parser::cmpt, 64> buf;
  auto next = buf.begin();

  // look for root name or root directory
  auto root_path = parser.root_path();
  if (root_path.first.valid())
    {
      *next++ = root_path.first;
      if (root_path.second.valid())
        *next++ = root_path.second;
    }

  auto cmpt = parser.next();
  while (cmpt.valid())
    {
      do
        {
          *next++ = cmpt;
          cmpt = parser.next();
        }
      while (cmpt.valid() && next != buf.end());

      if (next == buf.end())
        {
          _M_cmpts.type(_Type::_Multi);
          _M_cmpts.reserve(_M_cmpts.size() + buf.size());
          auto output = _M_cmpts._M_impl->end();
          for (auto& c : buf)
            {
              auto pos = c.str.data() - _M_pathname.data();
              ::new(output++) _Cmpt(c.str, c.type, pos);
              ++_M_cmpts._M_impl->_M_size;
            }
          next = buf.begin();
        }
    }

  if (auto n = next - buf.begin())
    {
      if (n == 1 && _M_cmpts.empty())
        {
          _M_cmpts.type(buf.front().type);
          return;
        }

      _M_cmpts.type(_Type::_Multi);
      _M_cmpts.reserve(_M_cmpts.size() + n, true);
      auto output = _M_cmpts._M_impl->end();
      for (int i = 0; i < n; ++i)
        {
          auto c = buf[i];
          auto pos = c.str.data() - _M_pathname.data();
          ::new(output++) _Cmpt(c.str, c.type, pos);
          ++_M_cmpts._M_impl->_M_size;
        }
    }
}

path::string_type
path::_S_convert_loc(const char* __first, const char* __last,
                     const std::locale& __loc)
{
#if _GLIBCXX_USE_WCHAR_T
  auto& __cvt = std::use_facet<codecvt<wchar_t, char, mbstate_t>>(__loc);
  basic_string<wchar_t> __ws;
  if (!__str_codecvt_in_all(__first, __last, __ws, __cvt))
    _GLIBCXX_THROW_OR_ABORT(filesystem_error(
          "Cannot convert character sequence",
          std::make_error_code(errc::illegal_byte_sequence)));
#ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  return __ws;
#else
  return _Cvt<wchar_t>::_S_convert(__ws.data(), __ws.data() + __ws.size());
#endif
#else
  return {__first, __last};
#endif
}

std::size_t
fs::hash_value(const path& p) noexcept
{
  // [path.non-member]
  // "If for two paths, p1 == p2 then hash_value(p1) == hash_value(p2)."
  // Equality works as if by traversing the range [begin(), end()), meaning
  // e.g. path("a//b") == path("a/b"), so we cannot simply hash _M_pathname
  // but need to iterate over individual elements. Use the hash_combine from
  // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf
  size_t seed = 0;
  for (const auto& x : p)
    {
      seed ^= std::hash<path::string_type>()(x.native()) + 0x9e3779b9
        + (seed<<6) + (seed>>2);
    }
  return seed;
}

struct fs::filesystem_error::_Impl
{
  _Impl(string_view what_arg, const path& p1, const path& p2)
  : path1(p1), path2(p2), what(make_what(what_arg, &p1, &p2))
  { }

  _Impl(string_view what_arg, const path& p1)
  : path1(p1), path2(), what(make_what(what_arg, &p1, nullptr))
  { }

  _Impl(string_view what_arg)
  : what(make_what(what_arg, nullptr, nullptr))
  { }

  static std::string
  make_what(string_view s, const path* p1, const path* p2)
  {
    const std::string pstr1 = p1 ? p1->u8string() : std::string{};
    const std::string pstr2 = p2 ? p2->u8string() : std::string{};
    const size_t len = 18 + s.length()
      + (pstr1.length() ? pstr1.length() + 3 : 0)
      + (pstr2.length() ? pstr2.length() + 3 : 0);
    std::string w;
    w.reserve(len);
    w = "filesystem error: ";
    w += s;
    if (p1)
      {
        w += " [";
        w += pstr1;
        w += ']';
        if (p2)
          {
            w += " [";
            w += pstr2;
            w += ']';
          }
      }
    return w;
  }

  path path1;
  path path2;
  std::string what;
};

template class std::__shared_ptr<const fs::filesystem_error::_Impl>;

fs::filesystem_error::
filesystem_error(const string& what_arg, error_code ec)
: system_error(ec, what_arg),
  _M_impl(std::__make_shared<_Impl>(system_error::what()))
{ }

fs::filesystem_error::
filesystem_error(const string& what_arg, const path& p1, error_code ec)
: system_error(ec, what_arg),
  _M_impl(std::__make_shared<_Impl>(system_error::what(), p1))
{ }

fs::filesystem_error::
filesystem_error(const string& what_arg, const path& p1, const path& p2,
                 error_code ec)
: system_error(ec, what_arg),
  _M_impl(std::__make_shared<_Impl>(system_error::what(), p1, p2))
{ }

fs::filesystem_error::~filesystem_error() = default;

const fs::path&
fs::filesystem_error::path1() const noexcept
{ return _M_impl->path1; }

const fs::path&
fs::filesystem_error::path2() const noexcept
{ return _M_impl->path2; }

const char*
fs::filesystem_error::what() const noexcept
{ return _M_impl->what.c_str(); }