src/util/filesystem.h

   1 /*
   2  * Copyright 2017 Jacob Lifshay
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in all
  12  * copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  *
  22  */
  23 #ifndef UTIL_FILESYSTEM_H_
  24 #define UTIL_FILESYSTEM_H_
  25
  26 #include <string>
  27 #include <utility>
  28 #include <new>
  29 #include <memory>
  30 #include <cassert>
  31 #include <limits>
  32 #include "bit_intrinsics.h"
  33 #include "string_view.h"
  34 #include "void_t.h"
  35 #include <type_traits>
  36 #include <iterator>
  37 #include "optional.h"
  38 #include "text.h"
  39 #include <cstdint>
  40 #include <iomanip>
  41 #include <istream>
  42 #include <ostream>
  43
  44 namespace vulkan_cpu
  45 {
  46 namespace util
  47 {
  48 namespace filesystem
  49 {
  50 namespace detail
  51 {
  52 enum class Path_traits_kind
  53 {
  54     posix,
  55     windows,
  56 };
  57
  58 #ifdef _WIN32
  59 constexpr Path_traits_kind default_path_traits_kind = Path_traits_kind::windows;
  60 #else
  61 constexpr Path_traits_kind default_path_traits_kind = Path_traits_kind::posix;
  62 #endif
  63
  64 template <Path_traits_kind Kind>
  65 struct Path_traits
  66 {
  67     typedef char value_type;
  68     static constexpr value_type preferred_separator = '/';
  69     static constexpr bool needs_root_name_to_be_absolute = false;
  70 };
  71
  72 template <>
  73 struct Path_traits<Path_traits_kind::windows>
  74 {
  75     typedef wchar_t value_type;
  76     static constexpr value_type preferred_separator = L'\\';
  77     static constexpr bool needs_root_name_to_be_absolute = true;
  78 };
  79
  80 enum class Path_part_kind
  81 {
  82     relative_root_name, // root name that has a current directory, like "C:" in windows
  83     absolute_root_name, // root name that can't have a current directory, like "\\ABC" in windows
  84     root_dir,
  85     file_name,
  86     multiple_parts,
  87     path_separator,
  88 };
  89
  90 template <typename T>
  91 struct Path_is_convertable_char_type
  92 {
  93     static constexpr bool value = false;
  94 };
  95
  96 template <typename T>
  97 struct Path_is_convertable_char_type<const T> : public Path_is_convertable_char_type<T>
  98 {
  99 };
 100
 101 template <>
 102 struct Path_is_convertable_char_type<char>
 103 {
 104     static constexpr bool value = true;
 105     typedef char Char_type;
 106 };
 107
 108 template <>
 109 struct Path_is_convertable_char_type<wchar_t>
 110 {
 111     static constexpr bool value = true;
 112     typedef wchar_t Char_type;
 113 };
 114
 115 template <>
 116 struct Path_is_convertable_char_type<char16_t>
 117 {
 118     static constexpr bool value = true;
 119     typedef char16_t Char_type;
 120 };
 121
 122 template <>
 123 struct Path_is_convertable_char_type<char32_t>
 124 {
 125     static constexpr bool value = true;
 126     typedef char32_t Char_type;
 127 };
 128
 129 template <typename T, typename = void>
 130 struct Path_is_convertable_iterator_type
 131 {
 132     static constexpr bool value = false;
 133 };
 134
 135 template <typename T>
 136 struct Path_is_convertable_iterator_type<T,
 137                                          typename std::enable_if<Path_is_convertable_char_type<
 138                                              typename std::iterator_traits<T>::value_type>::value>::
 139                                              type>
 140 {
 141     static constexpr bool value = true;
 142     typedef typename Path_is_convertable_char_type<
 143         typename std::iterator_traits<T>::value_type>::Char_type Char_type;
 144 };
 145
 146 struct Path_iterator_sentinel
 147 {
 148 };
 149
 150 template <typename Iterator>
 151 class Path_convert_single_iterator_adaptor
 152 {
 153 private:
 154     typedef std::iterator_traits<Iterator> Traits;
 155     optional<Iterator> base_iterator;
 156
 157 public:
 158     typedef typename Traits::value_type value_type;
 159     typedef typename Traits::pointer pointer;
 160     typedef typename Traits::reference reference;
 161     typedef typename Traits::difference_type difference_type;
 162     typedef std::input_iterator_tag iterator_category;
 163     constexpr Path_convert_single_iterator_adaptor() noexcept : base_iterator()
 164     {
 165     }
 166     constexpr explicit Path_convert_single_iterator_adaptor(Iterator iterator)
 167         : base_iterator(std::move(iterator))
 168     {
 169     }
 170     bool operator==(const Path_convert_single_iterator_adaptor &rt) const
 171     {
 172         if(base_iterator)
 173         {
 174             assert(!rt.base_iterator);
 175             return **base_iterator == value_type();
 176         }
 177         if(rt.base_iterator)
 178             return **rt.base_iterator == value_type();
 179         return true;
 180     }
 181     bool operator!=(const Path_convert_single_iterator_adaptor &rt) const
 182     {
 183         return !operator==(rt);
 184     }
 185     bool operator==(Path_iterator_sentinel) const
 186     {
 187         if(base_iterator)
 188             return **base_iterator == value_type();
 189         return true;
 190     }
 191     bool operator!=(Path_iterator_sentinel) const
 192     {
 193         return !operator==(Path_iterator_sentinel());
 194     }
 195     Path_convert_single_iterator_adaptor &operator++()
 196     {
 197         if(base_iterator)
 198             ++(*base_iterator);
 199         return *this;
 200     }
 201     Path_convert_single_iterator_adaptor operator++(int)
 202     {
 203         if(base_iterator)
 204             return Path_convert_single_iterator_adaptor((*base_iterator)++);
 205         return {};
 206     }
 207     reference operator*() const
 208     {
 209         return **base_iterator;
 210     }
 211     pointer operator->() const
 212     {
 213         return std::addressof(operator*());
 214     }
 215 };
 216
 217 template <typename Iterator, typename Sentinel>
 218 struct Iterator_and_sentinel
 219 {
 220     Iterator iterator;
 221     Sentinel sentinel;
 222     Iterator_and_sentinel(Iterator iterator, Sentinel sentinel)
 223         : iterator(std::move(iterator)), sentinel(std::move(sentinel))
 224     {
 225     }
 226 };
 227
 228 template <typename Dest_char_type,
 229           typename Iterator,
 230           typename Sentinel = Iterator,
 231           typename Source_char_type =
 232               typename Path_is_convertable_iterator_type<Iterator>::Char_type>
 233 class Path_convert_iterator
 234 {
 235 private:
 236     typedef decltype(text::Decode_encode_functions<Dest_char_type>::encode(
 237         char32_t(), text::Convert_options())) Encode_result;
 238     static_assert(std::is_same<typename Encode_result::Char_type, Dest_char_type>::value, "");
 239
 240 public:
 241     typedef Dest_char_type value_type;
 242     typedef const Dest_char_type *pointer;
 243     typedef const Dest_char_type &reference;
 244     typedef std::ptrdiff_t difference_type;
 245     typedef std::input_iterator_tag iterator_category;
 246
 247 private:
 248     Encode_result encode_result;
 249     std::size_t encode_result_index;
 250     util::optional<Iterator_and_sentinel<Iterator, Sentinel>> iterator_and_sentinel;
 251     void convert_next()
 252     {
 253         std::char_traits<char32_t>::int_type ch =
 254             text::Decode_encode_functions<Source_char_type>::decode(iterator_and_sentinel->iterator,
 255                                                                     iterator_and_sentinel->sentinel,
 256                                                                     text::Convert_options());
 257         if(ch == std::char_traits<char32_t>::eof())
 258             *this = Path_convert_iterator();
 259         else
 260         {
 261             encode_result =
 262                 text::Decode_encode_functions<Dest_char_type>::encode(ch, text::Convert_options());
 263             encode_result_index = 0;
 264         }
 265     }
 266
 267 public:
 268     constexpr Path_convert_iterator() noexcept : encode_result(),
 269                                                  encode_result_index(),
 270                                                  iterator_and_sentinel()
 271     {
 272     }
 273     Path_convert_iterator(Iterator iterator, Sentinel sentinel)
 274         : encode_result(),
 275           encode_result_index(),
 276           iterator_and_sentinel(in_place, std::move(iterator), std::move(sentinel))
 277     {
 278         convert_next();
 279     }
 280     Path_convert_iterator &operator++()
 281     {
 282         if(++encode_result_index >= encode_result.size())
 283             convert_next();
 284         return *this;
 285     }
 286     Path_convert_iterator operator++(int)
 287     {
 288         auto retval = *this;
 289         operator++();
 290         return retval;
 291     }
 292     const Dest_char_type &operator*() const noexcept
 293     {
 294         return encode_result[encode_result_index];
 295     }
 296     const Dest_char_type *operator->() const noexcept
 297     {
 298         return &encode_result[encode_result_index];
 299     }
 300     bool operator==(const Path_convert_iterator &rt) const noexcept
 301     {
 302         return iterator_and_sentinel.has_value() == rt.iterator_and_sentinel.has_value();
 303     }
 304     bool operator!=(const Path_convert_iterator &rt) const noexcept
 305     {
 306         return !operator==(rt);
 307     }
 308     bool operator==(Path_iterator_sentinel) const noexcept
 309     {
 310         return !iterator_and_sentinel;
 311     }
 312     bool operator!=(Path_iterator_sentinel) const noexcept
 313     {
 314         return !operator==(Path_iterator_sentinel());
 315     }
 316 };
 317
 318 template <typename Path_char_type, typename Iterator, typename = void>
 319 struct Path_convert_range
 320 {
 321     static constexpr bool is_convertible = false;
 322 };
 323
 324 template <typename Path_char_type, typename Iterator>
 325 struct Path_convert_range<Path_char_type,
 326                           Iterator,
 327                           typename std::
 328                               enable_if<Path_is_convertable_iterator_type<Iterator>::value>::type>
 329 {
 330     static constexpr bool is_convertible = true;
 331     template <typename Traits = std::char_traits<Path_char_type>,
 332               typename Allocator = std::allocator<Path_char_type>,
 333               typename Sentinel>
 334     static std::basic_string<Path_char_type, Traits, Allocator> to_string(
 335         Iterator iterator, Sentinel sentinel, const Allocator &a = Allocator())
 336     {
 337         typedef Path_convert_iterator<Path_char_type, Iterator, Sentinel> Convert_iterator;
 338         return std::basic_string<Path_char_type, Traits, Allocator>(
 339             Convert_iterator(iterator, sentinel), Convert_iterator(), a);
 340     }
 341 };
 342
 343 template <typename Iterator>
 344 struct Path_convert_range<typename Path_is_convertable_iterator_type<Iterator>::Char_type,
 345                           Iterator,
 346                           void>
 347 {
 348     static constexpr bool is_convertible = true;
 349     typedef typename Path_is_convertable_iterator_type<Iterator>::Char_type Char_type;
 350     static std::basic_string<Char_type> to_string(
 351         Iterator iterator,
 352         Iterator sentinel,
 353         const std::allocator<Char_type> &a = std::allocator<Char_type>())
 354     {
 355         return std::basic_string<Char_type>(iterator, sentinel, a);
 356     }
 357     template <typename Traits = std::char_traits<Char_type>,
 358               typename Allocator = std::allocator<Char_type>,
 359               typename Sentinel>
 360     static std::basic_string<Char_type, Traits, Allocator> to_string(
 361         Iterator iterator, Sentinel sentinel, const Allocator &a = Allocator())
 362     {
 363         std::basic_string<Char_type, Traits, Allocator> retval(a);
 364         while(iterator != sentinel)
 365             retval += *iterator++;
 366         return retval;
 367     }
 368 };
 369
 370 template <typename Path_char_type, typename Source, typename = void>
 371 struct Path_convert_source
 372 {
 373     static constexpr bool is_convertible = false;
 374 };
 375
 376 template <typename Path_char_type, typename Source_char_type, typename Traits, typename Allocator>
 377 struct Path_convert_source<Path_char_type,
 378                            std::basic_string<Source_char_type, Traits, Allocator>,
 379                            typename std::
 380                                enable_if<Path_convert_range<Path_char_type,
 381                                                             typename std::
 382                                                                 basic_string<Source_char_type,
 383                                                                              Traits,
 384                                                                              Allocator>::
 385                                                                     const_iterator>::
 386                                              is_convertible>::type>
 387 {
 388     typedef Path_convert_range<Path_char_type,
 389                                typename std::basic_string<Source_char_type, Traits, Allocator>::
 390                                    const_iterator> Convert_range;
 391     static constexpr bool is_convertible = true;
 392     template <typename Dest_traits = std::char_traits<Path_char_type>,
 393               typename Dest_allocator = std::allocator<Path_char_type>>
 394     static std::basic_string<Path_char_type, Dest_traits, Dest_allocator> to_string(
 395         const std::basic_string<Source_char_type, Traits, Allocator> &source,
 396         const Allocator &a = Allocator())
 397     {
 398         return Convert_range::template to_string<Dest_traits, Dest_allocator>(
 399             source.begin(), source.end(), a);
 400     }
 401 };
 402
 403 template <typename Path_char_type, typename Source_char_type, typename Traits>
 404 struct
 405     Path_convert_source<Path_char_type,
 406                         basic_string_view<Source_char_type, Traits>,
 407                         typename std::
 408                             enable_if<Path_convert_range<Path_char_type,
 409                                                          typename basic_string_view<Source_char_type,
 410                                                                                     Traits>::
 411                                                              const_iterator>::is_convertible>::type>
 412 {
 413     typedef Path_convert_range<Path_char_type,
 414                                typename basic_string_view<Source_char_type, Traits>::const_iterator>
 415         Convert_range;
 416     static constexpr bool is_convertible = true;
 417     template <typename Dest_traits = std::char_traits<Path_char_type>,
 418               typename Allocator = std::allocator<Path_char_type>>
 419     static std::basic_string<Path_char_type, Dest_traits, Allocator> to_string(
 420         const basic_string_view<Source_char_type, Traits> &source, const Allocator &a = Allocator())
 421     {
 422         return Convert_range::template to_string<Dest_traits, Allocator>(
 423             source.begin(), source.end(), a);
 424     }
 425 };
 426
 427 template <typename Char_type>
 428 struct Path_convert_source<Char_type, std::basic_string<Char_type>, void>
 429 {
 430     static constexpr bool is_convertible = true;
 431     template <typename Traits = std::char_traits<Char_type>,
 432               typename Allocator = std::allocator<Char_type>>
 433     static std::basic_string<Char_type, Traits, Allocator> to_string(
 434         const std::basic_string<Char_type> &source, const Allocator &a = Allocator())
 435     {
 436         return std::basic_string<Char_type, Traits, Allocator>(source.begin(), source.end(), a);
 437     }
 438     static std::basic_string<Char_type> to_string(
 439         const std::basic_string<Char_type> &source,
 440         const std::allocator<Char_type> & = std::allocator<Char_type>())
 441     {
 442         return source;
 443     }
 444 };
 445
 446 template <typename Char_type, typename Iterator>
 447 struct Path_convert_source<Char_type,
 448                            Iterator,
 449                            typename std::enable_if<!std::is_same<
 450                                typename Path_is_convertable_iterator_type<Iterator>::Char_type,
 451                                Char_type>::value>::type>
 452 {
 453     static constexpr bool is_convertible = true;
 454     typedef Path_convert_range<Char_type, Path_convert_single_iterator_adaptor<Iterator>>
 455         Convert_range;
 456     template <typename Traits = std::char_traits<Char_type>,
 457               typename Allocator = std::allocator<Char_type>>
 458     static std::basic_string<Char_type, Traits, Allocator> to_string(
 459         Iterator iterator, const Allocator &a = Allocator())
 460     {
 461         return Convert_range::template to_string<Traits, Allocator>(
 462             Path_convert_single_iterator_adaptor<Iterator>(iterator), Path_iterator_sentinel(), a);
 463     }
 464 };
 465
 466 template <typename Char_type>
 467 struct Path_convert_source<Char_type, const Char_type *, void>
 468 {
 469     static constexpr bool is_convertible = true;
 470     template <typename Traits = std::char_traits<Char_type>,
 471               typename Allocator = std::allocator<Char_type>>
 472     static std::basic_string<Char_type, Traits, Allocator> to_string(
 473         const Char_type *source, const Allocator &a = Allocator())
 474     {
 475         return {source, a};
 476     }
 477 };
 478
 479 template <typename Path_char_type, typename Source_char_type, std::size_t N>
 480 struct Path_convert_source<Path_char_type, Source_char_type[N], void>
 481     : public Path_convert_source<Path_char_type, const Source_char_type *, void>
 482 {
 483 };
 484
 485 struct Path_index_range
 486 {
 487     std::size_t begin;
 488     std::size_t end;
 489     constexpr Path_index_range() noexcept : begin(0), end(0)
 490     {
 491     }
 492     constexpr Path_index_range(std::size_t begin, std::size_t end) noexcept : begin(begin), end(end)
 493     {
 494     }
 495     template <typename Char_type, typename Traits>
 496     constexpr Path_index_range(basic_string_view<Char_type, Traits> str,
 497                                typename basic_string_view<Char_type, Traits>::iterator begin,
 498                                typename basic_string_view<Char_type, Traits>::iterator end) noexcept
 499         : begin(begin - str.begin()),
 500           end(end - str.begin())
 501     {
 502     }
 503     constexpr bool empty() const noexcept
 504     {
 505         return begin == end;
 506     }
 507     constexpr std::size_t size() const noexcept
 508     {
 509         return end - begin;
 510     }
 511 };
 512
 513 struct Path_tester;
 514 }
 515
 516 template <detail::Path_traits_kind Traits_kind = detail::default_path_traits_kind,
 517           typename Char_type = typename detail::Path_traits<Traits_kind>::value_type,
 518           Char_type Preferred_separator = detail::Path_traits<Traits_kind>::preferred_separator,
 519           bool Needs_root_name_to_be_absolute =
 520               detail::Path_traits<Traits_kind>::needs_root_name_to_be_absolute>
 521 class basic_path
 522 {
 523     friend struct detail::Path_tester;
 524     static_assert(std::is_same<Char_type, char>::value || std::is_same<Char_type, wchar_t>::value,
 525                   "");
 526
 527 private:
 528     typedef detail::Path_traits_kind Path_traits_kind;
 529     typedef detail::Path_part_kind Path_part_kind;
 530     typedef detail::Path_index_range Path_index_range;
 531
 532 public:
 533     typedef Char_type value_type;
 534     typedef std::basic_string<Char_type> string_type;
 535     enum format
 536     {
 537         native_format,
 538         generic_format,
 539         auto_format
 540     };
 541     static constexpr Char_type preferred_separator = Preferred_separator;
 542
 543 private:
 544     typedef basic_string_view<Char_type> string_view_type;
 545     class Parts
 546     {
 547     private:
 548         std::size_t allocated_count;
 549         std::size_t used_count;
 550         basic_path *values;
 551
 552     private:
 553         static basic_path *allocate(std::size_t count);
 554         template <typename... Args>
 555         static void construct(basic_path &value, Args &&... args)
 556         {
 557             ::new(static_cast<void *>(&value)) basic_path(std::forward<Args>(args)...);
 558         }
 559         static void destruct(basic_path &value) noexcept
 560         {
 561             value.~basic_path();
 562         }
 563         static void deallocate(basic_path *values, std::size_t count) noexcept;
 564         void reallocate(std::size_t new_allocated_count)
 565         {
 566             assert(new_allocated_count >= used_count);
 567             if(used_count == 0)
 568             {
 569                 deallocate(values, allocated_count);
 570                 values = nullptr;
 571                 allocated_count = 0; // set now in case allocate throws
 572                 values = allocate(new_allocated_count);
 573                 allocated_count = new_allocated_count;
 574             }
 575             else
 576             {
 577                 Parts new_parts;
 578                 new_parts.reserve(new_allocated_count);
 579                 for(std::size_t i = 0; i < used_count; i++)
 580                     new_parts.push_back(std::move(values[i]));
 581                 swap(new_parts);
 582             }
 583         }
 584         static constexpr std::uint64_t get_expanded_count_64(std::uint64_t count) noexcept
 585         {
 586             constexpr std::uint64_t high_bit = 1ULL << 63;
 587             if(count == 0 || count >= high_bit)
 588                 return count;
 589             return 1ULL << (64 - clz64(count - 1));
 590         }
 591         static constexpr std::uint32_t get_expanded_count_32(std::uint32_t count) noexcept
 592         {
 593             constexpr std::uint32_t high_bit = 1UL << 31;
 594             if(count == 0 || count >= high_bit)
 595                 return count;
 596             return 1UL << (32 - clz32(count - 1));
 597         }
 598         static constexpr std::size_t get_expanded_count(std::size_t count) noexcept
 599         {
 600             constexpr bool is_size_t_uint32_t = std::is_same<std::size_t, std::uint32_t>::value,
 601                            is_size_t_uint64_t = std::is_same<std::size_t, std::uint64_t>::value;
 602             static_assert(is_size_t_uint32_t || is_size_t_uint64_t, "");
 603             if(is_size_t_uint32_t)
 604                 return get_expanded_count_32(static_cast<std::uint32_t>(count));
 605             return static_cast<std::size_t>(get_expanded_count_64(count));
 606         }
 607
 608     public:
 609         constexpr Parts() noexcept : allocated_count(0), used_count(0), values(nullptr)
 610         {
 611         }
 612         Parts(const Parts &rt) : Parts()
 613         {
 614             Parts new_parts;
 615             new_parts.reserve(rt.used_count);
 616             for(std::size_t i = 0; i < rt.used_count; i++)
 617                 push_back(rt.values[i]);
 618             swap(new_parts);
 619         }
 620         Parts(Parts &&rt) noexcept : Parts()
 621         {
 622             swap(rt);
 623         }
 624         Parts &operator=(Parts &&rt) noexcept
 625         {
 626             Parts(std::move(rt)).swap(*this);
 627             return *this;
 628         }
 629         Parts &operator=(const Parts &rt)
 630         {
 631             if(this == &rt)
 632                 return *this;
 633             if(allocated_count < rt.used_count)
 634             {
 635                 Parts(rt).swap(*this);
 636                 return *this;
 637             }
 638             while(used_count > rt.used_count)
 639                 pop_back();
 640             for(std::size_t i = 0; i < used_count; i++)
 641                 values[i] = rt[i];
 642             while(used_count < rt.used_count)
 643                 push_back(rt[used_count]);
 644             return *this;
 645         }
 646         ~Parts() noexcept
 647         {
 648             while(used_count > 0)
 649                 destruct(values[--used_count]);
 650             deallocate(values, allocated_count);
 651         }
 652         void swap(Parts &rt) noexcept
 653         {
 654             using std::swap;
 655             swap(allocated_count, rt.allocated_count);
 656             swap(used_count, rt.used_count);
 657             swap(values, rt.values);
 658         }
 659         void reserve(std::size_t new_allocated_count)
 660         {
 661             if(new_allocated_count > allocated_count)
 662                 reallocate(new_allocated_count);
 663         }
 664         bool empty() const noexcept
 665         {
 666             return used_count == 0;
 667         }
 668         std::size_t size() const noexcept
 669         {
 670             return used_count;
 671         }
 672         std::size_t capacity() const noexcept
 673         {
 674             return allocated_count;
 675         }
 676         typedef basic_path *iterator;
 677         typedef const basic_path *const_iterator;
 678         iterator begin() noexcept
 679         {
 680             return values;
 681         }
 682         iterator end() noexcept
 683         {
 684             return values + used_count;
 685         }
 686         const_iterator begin() const noexcept
 687         {
 688             return values;
 689         }
 690         const_iterator end() const noexcept
 691         {
 692             return values + used_count;
 693         }
 694         const_iterator cbegin() const noexcept
 695         {
 696             return values;
 697         }
 698         const_iterator cend() const noexcept
 699         {
 700             return values + used_count;
 701         }
 702         template <typename... Args>
 703         void emplace_back(Args &&... args)
 704         {
 705             if(used_count >= allocated_count)
 706                 reallocate(get_expanded_count(used_count + 1));
 707             construct(values[used_count], std::forward<Args>(args)...);
 708             used_count++;
 709         }
 710         void push_back(const basic_path &v)
 711         {
 712             emplace_back(v);
 713         }
 714         void push_back(basic_path &&v)
 715         {
 716             emplace_back(v);
 717         }
 718         void pop_back() noexcept
 719         {
 720             assert(used_count > 0);
 721             destruct(values[--used_count]);
 722         }
 723         void clear() noexcept
 724         {
 725             while(used_count > 0)
 726                 pop_back();
 727         }
 728         basic_path &operator[](std::size_t index) noexcept
 729         {
 730             assert(index < used_count);
 731             return values[index];
 732         }
 733         const basic_path &operator[](std::size_t index) const noexcept
 734         {
 735             assert(index < used_count);
 736             return values[index];
 737         }
 738     };
 739
 740 private:
 741     Parts parts;
 742     string_type value;
 743     detail::Path_part_kind kind;
 744
 745 public:
 746     class iterator
 747     {
 748         template <detail::Path_traits_kind, typename Char_type2, Char_type2, bool>
 749         friend class basic_path;
 750
 751     public:
 752         typedef basic_path value_type;
 753         typedef const basic_path *pointer;
 754         typedef const basic_path &reference;
 755         typedef std::ptrdiff_t difference_type;
 756         typedef std::bidirectional_iterator_tag iterator_category;
 757
 758     private:
 759         const basic_path *path;
 760         std::size_t index;
 761         constexpr iterator(const basic_path *path, std::size_t index) noexcept : path(path),
 762                                                                                  index(index)
 763         {
 764         }
 765
 766     public:
 767         constexpr iterator() noexcept : path(nullptr), index()
 768         {
 769         }
 770         constexpr iterator &operator++() noexcept
 771         {
 772             index++;
 773             return *this;
 774         }
 775         constexpr iterator &operator--() noexcept
 776         {
 777             index--;
 778             return *this;
 779         }
 780         constexpr iterator operator++(int) noexcept
 781         {
 782             return iterator(path, index++);
 783         }
 784         constexpr iterator operator--(int) noexcept
 785         {
 786             return iterator(path, index--);
 787         }
 788         const basic_path *operator->() const
 789         {
 790             assert(path);
 791             if(path->kind == Path_part_kind::multiple_parts)
 792                 return &path->parts[index];
 793             return path;
 794         }
 795         const basic_path &operator*() const
 796         {
 797             return *operator->();
 798         }
 799         constexpr bool operator==(const iterator &rt) const noexcept
 800         {
 801             return index == rt.index;
 802         }
 803         constexpr bool operator!=(const iterator &rt) const noexcept
 804         {
 805             return index != rt.index;
 806         }
 807     };
 808     typedef iterator const_iterator;
 809
 810 private:
 811     static constexpr bool is_ascii_letter(Char_type v) noexcept
 812     {
 813         auto ch = static_cast<unsigned char>(v);
 814         if(static_cast<Char_type>(ch) != v)
 815             return false;
 816         if(ch >= 'a' && ch <= 'z')
 817             return true;
 818         if(ch >= 'A' && ch <= 'Z')
 819             return true;
 820         return false;
 821     }
 822     template <typename Char_type2>
 823     static constexpr bool is_separator(Char_type2 v) noexcept
 824     {
 825         return v == static_cast<Char_type2>('/')
 826                || v == static_cast<Char_type2>(preferred_separator);
 827     }
 828     template <bool Ignore_root_parts = false, typename Fn>
 829     static bool parse(string_view_type value, Fn callback, format fmt = auto_format) noexcept(
 830         noexcept(callback(Path_index_range(), Path_part_kind())))
 831     {
 832         constexpr Char_type colon = ':';
 833         typedef typename std::char_traits<Char_type>::int_type Int_type;
 834         constexpr Int_type eof = std::char_traits<Char_type>::eof();
 835         auto char_iter = value.begin();
 836         auto peek = [&]() -> Int_type
 837         {
 838             if(char_iter == value.end())
 839                 return eof;
 840             return std::char_traits<Char_type>::to_int_type(*char_iter);
 841         };
 842         auto get = [&]() -> Int_type
 843         {
 844             if(char_iter == value.end())
 845                 return eof;
 846             return std::char_traits<Char_type>::to_int_type(*char_iter++);
 847         };
 848         if(value.empty())
 849             return true;
 850         if(!Ignore_root_parts && Traits_kind == Path_traits_kind::windows && value.size() >= 2
 851            && is_ascii_letter(value[0])
 852            && value[1] == colon)
 853         {
 854             char_iter += 2;
 855             if(!callback(Path_index_range(value, value.begin(), char_iter),
 856                          Path_part_kind::relative_root_name))
 857                 return false;
 858         }
 859         else if(!Ignore_root_parts && Traits_kind == Path_traits_kind::windows && value.size() >= 2
 860                 && is_separator(value[0])
 861                 && is_separator(value[1]))
 862         {
 863             while(peek() != eof && is_separator(peek()))
 864                 get();
 865             while(peek() != eof && !is_separator(peek()))
 866                 get();
 867             if(!callback(Path_index_range(value, value.begin(), char_iter),
 868                          Path_part_kind::absolute_root_name))
 869                 return false;
 870         }
 871         if(!Ignore_root_parts && peek() != eof && is_separator(peek()))
 872         {
 873             auto start_iter = char_iter;
 874             do
 875             {
 876                 get();
 877             } while(peek() != eof && is_separator(peek()));
 878             if(!callback(Path_index_range(value, start_iter, char_iter), Path_part_kind::root_dir))
 879                 return false;
 880         }
 881         if(Ignore_root_parts && peek() != eof && is_separator(peek()))
 882         {
 883             if(!callback(Path_index_range(value, char_iter, char_iter), Path_part_kind::file_name))
 884                 return false;
 885         }
 886         if(peek() != eof && !is_separator(peek()))
 887         {
 888             auto start_iter = char_iter;
 889             do
 890             {
 891                 get();
 892             } while(peek() != eof && !is_separator(peek()));
 893             if(!callback(Path_index_range(value, start_iter, char_iter), Path_part_kind::file_name))
 894                 return false;
 895         }
 896         while(peek() != eof)
 897         {
 898             auto start_iter = char_iter;
 899             do
 900             {
 901                 get();
 902             } while(peek() != eof && is_separator(peek()));
 903             if(!callback(Path_index_range(value, start_iter, char_iter),
 904                          Path_part_kind::path_separator))
 905                 return false;
 906             start_iter = char_iter;
 907             while(peek() != eof && !is_separator(peek()))
 908                 get();
 909             if(!callback(Path_index_range(value, start_iter, char_iter), Path_part_kind::file_name))
 910                 return false;
 911         }
 912         return true;
 913     }
 914     void parse(format fmt = auto_format)
 915     {
 916         constexpr Char_type generic_separator = '/';
 917         auto last_part_kind = Path_part_kind::multiple_parts;
 918         std::size_t part_count = 0;
 919         bool need_generic_conversion = false;
 920         parse(value,
 921               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
 922               {
 923                   if(part_kind == Path_part_kind::path_separator)
 924                       return true;
 925                   if(generic_separator != preferred_separator && !need_generic_conversion)
 926                   {
 927                       for(std::size_t i = index_range.begin; i < index_range.end; i++)
 928                       {
 929                           if(is_separator(value[i]) && value[i] != generic_separator)
 930                           {
 931                               need_generic_conversion = true;
 932                               break;
 933                           }
 934                       }
 935                   }
 936                   last_part_kind = part_kind;
 937                   part_count++;
 938                   return true;
 939               },
 940               fmt);
 941         if(part_count == 1 && !need_generic_conversion)
 942         {
 943             kind = last_part_kind;
 944             parts.clear();
 945             return;
 946         }
 947         else
 948         {
 949             kind = Path_part_kind::multiple_parts;
 950         }
 951         while(parts.size() > part_count)
 952             parts.pop_back();
 953         parts.reserve(part_count);
 954         std::size_t part_index = 0;
 955         parse(value,
 956               [&](Path_index_range index_range, Path_part_kind part_kind)
 957               {
 958                   if(part_kind == Path_part_kind::path_separator)
 959                       return true;
 960                   if(part_index >= parts.size())
 961                       parts.emplace_back();
 962                   parts[part_index].value.assign(value.data() + index_range.begin,
 963                                                  index_range.size());
 964                   parts[part_index].kind = part_kind;
 965                   change_separator(parts[part_index].value, generic_separator);
 966                   part_index++;
 967                   return true;
 968               },
 969               fmt);
 970     }
 971     static Path_index_range get_filename_index_range(string_view_type value) noexcept
 972     {
 973         Path_index_range retval(value.size(), value.size());
 974         parse(value,
 975               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
 976               {
 977                   if(part_kind == Path_part_kind::file_name)
 978                       retval = index_range;
 979                   return true;
 980               });
 981         return retval;
 982     }
 983     static Path_index_range get_stem_index_range(string_view_type value) noexcept
 984     {
 985         return get_stem_index_range(value, get_filename_index_range(value));
 986     }
 987     static Path_index_range get_stem_index_range(string_view_type value,
 988                                                  Path_index_range filename_index_range) noexcept
 989     {
 990         constexpr Char_type dot = '.';
 991         if(filename_index_range.size() <= 1)
 992             return filename_index_range;
 993         for(std::size_t i = filename_index_range.end; i > filename_index_range.begin; i--)
 994         {
 995             if(value[i - 1] == dot)
 996             {
 997                 if(i == filename_index_range.begin + 1)
 998                     return filename_index_range;
 999                 if(i == filename_index_range.begin + 2 && value[filename_index_range.begin] == dot)
1000                     return filename_index_range;
1001                 return Path_index_range(filename_index_range.begin, i - 1);
1002             }
1003         }
1004         return filename_index_range;
1005     }
1006     static Path_index_range get_extension_index_range(string_view_type value) noexcept
1007     {
1008         return get_extension_index_range(value, get_filename_index_range(value));
1009     }
1010     static Path_index_range get_extension_index_range(
1011         string_view_type value, Path_index_range filename_index_range) noexcept
1012     {
1013         return get_extension_index_range(
1014             value, filename_index_range, get_stem_index_range(value, filename_index_range));
1015     }
1016     static Path_index_range get_extension_index_range([[gnu::unused]] string_view_type value,
1017                                                       Path_index_range filename_index_range,
1018                                                       Path_index_range stem_index_range) noexcept
1019     {
1020         return Path_index_range(stem_index_range.end, filename_index_range.end);
1021     }
1022     static Path_index_range get_root_name_index_range(string_view_type value) noexcept
1023     {
1024         Path_index_range retval(0, 0);
1025         parse(value,
1026               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1027               {
1028                   if(part_kind == Path_part_kind::absolute_root_name
1029                      || part_kind == Path_part_kind::relative_root_name)
1030                       retval = index_range;
1031                   return false;
1032               });
1033         return retval;
1034     }
1035     static Path_index_range get_root_dir_index_range(string_view_type value) noexcept
1036     {
1037         Path_index_range retval(0, 0);
1038         parse(value,
1039               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1040               {
1041                   if(part_kind == Path_part_kind::root_dir)
1042                   {
1043                       retval = index_range;
1044                   }
1045                   else if(part_kind == Path_part_kind::absolute_root_name
1046                           || part_kind == Path_part_kind::relative_root_name)
1047                   {
1048                       retval = Path_index_range(index_range.end, index_range.end);
1049                       return true;
1050                   }
1051                   return false;
1052               });
1053         return retval;
1054     }
1055     static Path_index_range get_root_path_index_range(string_view_type value) noexcept
1056     {
1057         Path_index_range retval(0, 0);
1058         parse(value,
1059               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1060               {
1061                   if(part_kind == Path_part_kind::absolute_root_name
1062                      || part_kind == Path_part_kind::relative_root_name)
1063                   {
1064                       retval = index_range;
1065                       return true;
1066                   }
1067                   else if(part_kind == Path_part_kind::root_dir)
1068                   {
1069                       retval.end = index_range.end;
1070                       return false;
1071                   }
1072                   return false;
1073               });
1074         return retval;
1075     }
1076     static Path_index_range get_relative_path_index_range(string_view_type value) noexcept
1077     {
1078         Path_index_range retval(value.size(), value.size());
1079         parse(value,
1080               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1081               {
1082                   if(part_kind == Path_part_kind::absolute_root_name
1083                      || part_kind == Path_part_kind::relative_root_name
1084                      || part_kind == Path_part_kind::root_dir)
1085                   {
1086                       return true;
1087                   }
1088                   retval.begin = index_range.begin;
1089                   return false;
1090               });
1091         return retval;
1092     }
1093     static Path_index_range get_parent_path_index_range(string_view_type value) noexcept
1094     {
1095         Path_index_range retval(0, 0);
1096         std::size_t last_file_name_end_index = 0;
1097         parse(value,
1098               [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1099               {
1100                   switch(part_kind)
1101                   {
1102                   case Path_part_kind::path_separator:
1103                       return true;
1104                   case Path_part_kind::absolute_root_name:
1105                   case Path_part_kind::relative_root_name:
1106                   case Path_part_kind::root_dir:
1107                       retval.end = index_range.end;
1108                       return true;
1109                   case Path_part_kind::file_name:
1110                       if(last_file_name_end_index != 0)
1111                           retval.end = last_file_name_end_index;
1112                       last_file_name_end_index = index_range.end;
1113                       return true;
1114                   case Path_part_kind::multiple_parts:
1115                       break;
1116                   }
1117                   assert(false);
1118                   return false;
1119               });
1120         return retval;
1121     }
1122
1123 public:
1124     basic_path() noexcept : parts(), value(), kind(Path_part_kind::multiple_parts)
1125     {
1126     }
1127     basic_path(const basic_path &) = default;
1128     basic_path(basic_path &&rt) noexcept : parts(), value(), kind()
1129     {
1130         swap(rt);
1131     }
1132     basic_path(string_type &&source, format fmt = auto_format)
1133         : parts(), value(std::move(source)), kind()
1134     {
1135         parse(fmt);
1136     }
1137     template <typename Source>
1138     basic_path(const Source &source, format fmt = auto_format)
1139         : basic_path(detail::Path_convert_source<Char_type, Source>::to_string(source), fmt)
1140     {
1141     }
1142     template <typename Input_iterator>
1143     basic_path(Input_iterator first, Input_iterator last, format fmt = auto_format)
1144         : basic_path(detail::Path_convert_range<Char_type, Input_iterator>::to_string(first, last),
1145                      fmt)
1146     {
1147     }
1148     basic_path &operator=(const basic_path &rt) = default;
1149     basic_path &operator=(basic_path &&rt) noexcept
1150     {
1151         basic_path(std::move(rt)).swap(*this);
1152         return *this;
1153     }
1154     basic_path &operator=(string_type &&new_value)
1155     {
1156         value = std::move(new_value);
1157         parse();
1158         return *this;
1159     }
1160     template <typename Source>
1161     basic_path &operator=(const Source &source)
1162     {
1163         assign(source);
1164         return *this;
1165     }
1166     basic_path &assign(string_type &&new_value)
1167     {
1168         return operator=(new_value);
1169     }
1170     basic_path &assign(const string_type &new_value)
1171     {
1172         value = new_value;
1173         parse();
1174         return *this;
1175     }
1176     basic_path &assign(const string_view_type &new_value)
1177     {
1178         // use assign to prevent allocating a temporary string_type
1179         value.assign(new_value.data(), new_value.size());
1180         parse();
1181         return *this;
1182     }
1183     template <typename Source>
1184     basic_path &assign(const Source &source)
1185     {
1186         assign(detail::Path_convert_source<Char_type, Source>::to_string(source));
1187         return *this;
1188     }
1189     template <typename Input_iterator>
1190     basic_path &assign(Input_iterator first, Input_iterator last)
1191     {
1192         assign(detail::Path_convert_range<Char_type, Input_iterator>::to_string(first, last));
1193         return *this;
1194     }
1195
1196 private:
1197     template <bool Check_for_shared_memory = true>
1198     void append_string(string_view_type str)
1199     {
1200         bool just_need_to_assign = is_absolute(str);
1201         if(!just_need_to_assign && !get_root_name_index_range(str).empty())
1202         {
1203             auto my_root_name_index_range = get_root_name_index_range(value);
1204             auto str_root_name_index_range = get_root_name_index_range(str);
1205             if(my_root_name_index_range.empty()
1206                || string_view_type(value)
1207                           .substr(my_root_name_index_range.begin, my_root_name_index_range.size())
1208                       == str.substr(str_root_name_index_range.begin,
1209                                     str_root_name_index_range.size()))
1210                 just_need_to_assign = true;
1211         }
1212         if(just_need_to_assign)
1213         {
1214             assign(str);
1215             return;
1216         }
1217         static_assert(std::is_same<typename string_view_type::iterator, const Char_type *>::value,
1218                       "");
1219         if(Check_for_shared_memory && str.begin() <= value.data() + value.size()
1220            && str.end() >= value.data())
1221         {
1222             // value and str share memory, reallocate str
1223             append_string<false>(static_cast<string_type>(str));
1224             return;
1225         }
1226         auto str_root_name_index_range = get_root_name_index_range(str);
1227         assert(str_root_name_index_range.begin == 0);
1228         str.remove_prefix(str_root_name_index_range.end);
1229         if(!get_root_dir_index_range(str).empty())
1230         {
1231             auto my_root_name_index_range = get_root_name_index_range(value);
1232             assert(my_root_name_index_range.begin == 0);
1233             value.resize(my_root_name_index_range.end);
1234         }
1235         else if(!get_filename_index_range(value).empty()
1236                 || (get_root_dir_index_range(value).empty() && is_absolute()))
1237         {
1238             value.reserve(value.size() + 1 + str.size());
1239             value += preferred_separator;
1240         }
1241         value += str;
1242         parse();
1243     }
1244
1245 public:
1246     basic_path &operator/=(const basic_path &p)
1247     {
1248         append_string(p.value);
1249         return *this;
1250     }
1251     basic_path &operator/=(const string_type &p)
1252     {
1253         append_string(p);
1254     }
1255     basic_path &operator/=(const string_view_type &p)
1256     {
1257         append_string(p);
1258     }
1259     template <typename Source>
1260     basic_path &operator/=(const Source &source)
1261     {
1262         append_string(detail::Path_convert_source<Char_type, Source>::to_string(source));
1263         return *this;
1264     }
1265     template <typename Source>
1266     basic_path &append(const Source &source)
1267     {
1268         operator/=(source);
1269         return *this;
1270     }
1271     template <typename Input_iterator>
1272     basic_path &append(Input_iterator first, Input_iterator last)
1273     {
1274         append_string(
1275             detail::Path_convert_range<Char_type, Input_iterator>::to_string(first, last));
1276         return *this;
1277     }
1278     basic_path &operator+=(const basic_path &p)
1279     {
1280         value += p.value;
1281         parse();
1282         return *this;
1283     }
1284     basic_path &operator+=(const string_type &p)
1285     {
1286         value += p;
1287         parse();
1288         return *this;
1289     }
1290     basic_path &operator+=(const string_view_type &p)
1291     {
1292         value += p;
1293         parse();
1294         return *this;
1295     }
1296     template <typename Source>
1297     basic_path &operator+=(const Source &source)
1298     {
1299         value += detail::Path_convert_source<Char_type, Source>::to_string(source);
1300         parse();
1301         return *this;
1302     }
1303     template <typename Source>
1304     basic_path &concat(const Source &source)
1305     {
1306         operator+=(source);
1307         return *this;
1308     }
1309     template <typename Input_iterator>
1310     basic_path &concat(Input_iterator first, Input_iterator last)
1311     {
1312         value += detail::Path_convert_range<Char_type, Input_iterator>::to_string(first, last);
1313         parse();
1314         return *this;
1315     }
1316     const Char_type *c_str() const noexcept
1317     {
1318         return value.c_str();
1319     }
1320     const string_type &native() const noexcept
1321     {
1322         return value;
1323     }
1324     operator string_type() const
1325     {
1326         return value;
1327     }
1328     void clear() noexcept
1329     {
1330         value.clear();
1331         parse();
1332     }
1333
1334 private:
1335     template <typename Char_type2, typename Traits, typename Allocator>
1336     static void change_separator(std::basic_string<Char_type2, Traits, Allocator> &str,
1337                                  Char_type2 separator) noexcept
1338     {
1339         for(auto &ch : str)
1340         {
1341             if(is_separator(ch))
1342                 ch = separator;
1343         }
1344     }
1345     basic_path &change_separator(Char_type separator) noexcept
1346     {
1347         change_separator(value, separator);
1348         for(auto &part : parts)
1349             change_separator(part.value, separator);
1350         return *this;
1351     }
1352
1353 public:
1354     basic_path &make_preferred() noexcept
1355     {
1356         change_separator(preferred_separator);
1357         return *this;
1358     }
1359     basic_path &remove_filename()
1360     {
1361         auto filename_index_range = get_filename_index_range(value);
1362         if(!filename_index_range.empty())
1363         {
1364             value.erase(filename_index_range.begin, filename_index_range.size());
1365             parse();
1366         }
1367         return *this;
1368     }
1369     basic_path &replace_filename(const basic_path &replacement)
1370     {
1371         remove_filename();
1372         operator/=(replacement);
1373         return *this;
1374     }
1375     basic_path &replace_extension(const basic_path &replacement = basic_path())
1376     {
1377         constexpr Char_type dot = '.';
1378         auto extension_index_range = get_extension_index_range(value);
1379         if(!extension_index_range.empty())
1380             value.erase(extension_index_range.begin, extension_index_range.size());
1381         else if(replacement.value.empty())
1382             return *this;
1383         if(!replacement.value.empty() && replacement.value.front() != dot)
1384         {
1385             value.reserve(value.size() + 1 + replacement.value.size());
1386             value += dot;
1387             value += replacement.value;
1388         }
1389         else
1390         {
1391             value += replacement.value;
1392         }
1393         parse();
1394         return *this;
1395     }
1396     void swap(basic_path &other) noexcept
1397     {
1398         using std::swap;
1399         swap(value, other.value);
1400         parts.swap(other.parts);
1401         swap(kind, other.kind);
1402     }
1403     bool has_root_path() const noexcept
1404     {
1405         return !get_root_path_index_range(value).empty();
1406     }
1407     bool has_root_name() const noexcept
1408     {
1409         return !get_root_name_index_range(value).empty();
1410     }
1411     bool has_root_directory() const noexcept
1412     {
1413         return !get_root_dir_index_range(value).empty();
1414     }
1415     bool has_relative_path() const noexcept
1416     {
1417         return !get_relative_path_index_range(value).empty();
1418     }
1419     bool has_parent_path() const noexcept
1420     {
1421         return !get_parent_path_index_range(value).empty();
1422     }
1423     bool has_filename() const noexcept
1424     {
1425         return !get_filename_index_range(value).empty();
1426     }
1427     bool has_stem() const noexcept
1428     {
1429         return !get_stem_index_range(value).empty();
1430     }
1431     bool has_extension() const noexcept
1432     {
1433         return !get_extension_index_range(value).empty();
1434     }
1435
1436 private:
1437     static bool is_absolute(string_view_type value) noexcept
1438     {
1439         bool has_root_dir = false;
1440         bool has_relative_root_name = false;
1441         bool has_absolute_root_name = false;
1442         parse(value,
1443               [&]([[gnu::unused]] Path_index_range index_range, Path_part_kind part_kind) noexcept
1444               {
1445                   if(part_kind == Path_part_kind::relative_root_name)
1446                   {
1447                       has_relative_root_name = true;
1448                       return true;
1449                   }
1450                   else if(part_kind == Path_part_kind::absolute_root_name)
1451                   {
1452                       has_absolute_root_name = true;
1453                       return false;
1454                   }
1455                   else if(part_kind == Path_part_kind::root_dir)
1456                   {
1457                       has_root_dir = true;
1458                   }
1459                   return false;
1460               });
1461         if(has_absolute_root_name)
1462             return true;
1463         if(has_root_dir)
1464         {
1465             if(Needs_root_name_to_be_absolute)
1466                 return has_relative_root_name;
1467             return true;
1468         }
1469         return false;
1470     }
1471
1472 public:
1473     bool is_absolute() const noexcept
1474     {
1475         return is_absolute(value);
1476     }
1477     bool is_relative() const noexcept
1478     {
1479         return !is_absolute(value);
1480     }
1481     template <typename String_char_type,
1482               typename String_traits_type = std::char_traits<String_char_type>,
1483               typename Allocator = std::allocator<String_char_type>>
1484     std::basic_string<String_char_type, String_traits_type, Allocator> string(
1485         const Allocator &a = Allocator()) const
1486     {
1487         return detail::Path_convert_source<String_char_type,
1488                                            string_type>::template to_string<String_traits_type,
1489                                                                             Allocator>(value, a);
1490     }
1491     std::string string() const
1492     {
1493         return string<char>();
1494     }
1495     std::wstring wstring() const
1496     {
1497         return string<wchar_t>();
1498     }
1499     std::string u8string() const
1500     {
1501         return string<char>();
1502     }
1503     std::u16string u16string() const
1504     {
1505         return string<char16_t>();
1506     }
1507     std::u32string u32string() const
1508     {
1509         return string<char32_t>();
1510     }
1511     template <typename String_char_type,
1512               typename String_traits_type = std::char_traits<String_char_type>,
1513               typename Allocator = std::allocator<String_char_type>>
1514     std::basic_string<String_char_type, String_traits_type, Allocator> generic_string(
1515         const Allocator &a = Allocator()) const
1516     {
1517         auto retval =
1518             detail::Path_convert_source<String_char_type,
1519                                         string_type>::template to_string<String_traits_type,
1520                                                                          Allocator>(value, a);
1521         change_separator(retval, static_cast<String_char_type>('/'));
1522         return retval;
1523     }
1524     std::string generic_string() const
1525     {
1526         return generic_string<char>();
1527     }
1528     std::wstring generic_wstring() const
1529     {
1530         return generic_string<wchar_t>();
1531     }
1532     std::string generic_u8string() const
1533     {
1534         return generic_string<char>();
1535     }
1536     std::u16string generic_u16string() const
1537     {
1538         return generic_string<char16_t>();
1539     }
1540     std::u32string generic_u32string() const
1541     {
1542         return generic_string<char32_t>();
1543     }
1544     template <typename Stream_char_type, typename Stream_traits_type>
1545     friend std::basic_ostream<Stream_char_type, Stream_traits_type> &operator<<(
1546         std::basic_ostream<Stream_char_type, Stream_traits_type> &os, const basic_path &p)
1547     {
1548         os << std::quoted(p.string<Stream_char_type, Stream_traits_type>());
1549         return os;
1550     }
1551     template <typename Stream_char_type, typename Stream_traits_type>
1552     friend std::basic_istream<Stream_char_type, Stream_traits_type> &operator>>(
1553         std::basic_istream<Stream_char_type, Stream_traits_type> &is, basic_path &p)
1554     {
1555         std::basic_string<Stream_char_type, Stream_traits_type> str;
1556         is >> std::quoted(str);
1557         p = std::move(str);
1558         return is;
1559     }
1560
1561 private:
1562     static int compare_part(string_view_type a,
1563                             Path_part_kind a_kind,
1564                             string_view_type b,
1565                             Path_part_kind b_kind) noexcept
1566     {
1567         constexpr Char_type generic_separator_char = '/';
1568         constexpr string_view_type generic_separator(&generic_separator_char, 1);
1569         if(a_kind == Path_part_kind::root_dir)
1570             a = generic_separator;
1571         if(b_kind == Path_part_kind::root_dir)
1572             b = generic_separator;
1573         for(std::size_t i = 0; i < a.size() && i < b.size(); i++)
1574         {
1575             Char_type a_char = a[i];
1576             Char_type b_char = b[i];
1577             if(a_char == preferred_separator)
1578                 a_char = generic_separator_char;
1579             if(b_char == preferred_separator)
1580                 b_char = generic_separator_char;
1581             if(a_char < b_char)
1582                 return -1;
1583             if(a_char > b_char)
1584                 return 1;
1585         }
1586         if(a.size() < b.size())
1587             return -1;
1588         if(a.size() > b.size())
1589             return 1;
1590         return 0;
1591     }
1592
1593 public:
1594     int compare(string_view_type str) const noexcept
1595     {
1596         int retval;
1597         if(kind != Path_part_kind::multiple_parts)
1598         {
1599             retval = 1; // non-empty is more than empty
1600             parse(str,
1601                   [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1602                   {
1603                       if(part_kind == Path_part_kind::path_separator)
1604                           return true;
1605                       if(retval == 1) // initial value
1606                           retval = compare_part(value,
1607                                                 kind,
1608                                                 str.substr(index_range.begin, index_range.size()),
1609                                                 part_kind);
1610                       else
1611                           retval = -1; // one-element is less than two-elements
1612                       return retval == 0;
1613                   });
1614         }
1615         else
1616         {
1617             retval = 0;
1618             auto part_iter = parts.begin();
1619             parse(str,
1620                   [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1621                   {
1622                       if(part_kind == Path_part_kind::path_separator)
1623                           return true;
1624                       if(part_iter == parts.end())
1625                       {
1626                           retval = -1; // empty is less than non-empty
1627                       }
1628                       else
1629                       {
1630                           retval = compare_part(part_iter->value,
1631                                                 part_iter->kind,
1632                                                 str.substr(index_range.begin, index_range.size()),
1633                                                 part_kind);
1634                           ++part_iter;
1635                       }
1636                       return retval == 0;
1637                   });
1638             if(retval == 0 && part_iter != parts.end())
1639                 retval = 1; // more-elements is more than fewer-elements
1640         }
1641         return retval;
1642     }
1643     int compare(const string_type &str) const noexcept
1644     {
1645         return compare(string_view_type(str));
1646     }
1647     int compare(const Char_type *str) const
1648     {
1649         return compare(string_view_type(str));
1650     }
1651     int compare(const basic_path &rt) const noexcept
1652     {
1653         return compare(rt.value);
1654     }
1655     iterator begin() const noexcept
1656     {
1657         return iterator(this, 0);
1658     }
1659     iterator end() const noexcept
1660     {
1661         return iterator(this, kind == Path_part_kind::multiple_parts ? parts.size() : 1);
1662     }
1663     basic_path root_name() const
1664     {
1665         auto iter = begin();
1666         if(iter == end())
1667             return {};
1668         if(iter->kind == Path_part_kind::relative_root_name
1669            || iter->kind == Path_part_kind::absolute_root_name)
1670             return *iter;
1671         return {};
1672     }
1673     basic_path root_directory() const
1674     {
1675         auto iter = begin();
1676         if(iter == end())
1677             return {};
1678         if(iter->kind == Path_part_kind::relative_root_name
1679            || iter->kind == Path_part_kind::absolute_root_name)
1680             ++iter;
1681         if(iter == end())
1682             return {};
1683         if(iter->kind == Path_part_kind::root_dir)
1684             return *iter;
1685         return {};
1686     }
1687     basic_path root_path() const
1688     {
1689         auto index_range = get_root_path_index_range(value);
1690         if(index_range.empty())
1691             return {};
1692         return value.substr(index_range.begin, index_range.size());
1693     }
1694     basic_path relative_path() const
1695     {
1696         auto index_range = get_relative_path_index_range(value);
1697         if(index_range.empty())
1698             return {};
1699         return value.substr(index_range.begin, index_range.size());
1700     }
1701     basic_path parent_path() const
1702     {
1703         auto index_range = get_parent_path_index_range(value);
1704         if(index_range.empty())
1705             return {};
1706         return value.substr(index_range.begin, index_range.size());
1707     }
1708     basic_path filename() const
1709     {
1710         auto iter = end();
1711         if(iter == begin())
1712             return {};
1713         --iter;
1714         if(iter->kind == Path_part_kind::file_name)
1715             return *iter;
1716         return {};
1717     }
1718     basic_path stem() const
1719     {
1720         auto index_range = get_stem_index_range(value);
1721         if(index_range.empty())
1722             return {};
1723         return value.substr(index_range.begin, index_range.size());
1724     }
1725     basic_path extension() const
1726     {
1727         auto index_range = get_extension_index_range(value);
1728         if(index_range.empty())
1729             return {};
1730         return value.substr(index_range.begin, index_range.size());
1731     }
1732     bool empty() const noexcept
1733     {
1734         return begin() == end();
1735     }
1736     basic_path lexically_normal() const
1737     {
1738         constexpr Char_type dot = '.';
1739         constexpr std::size_t dot_dot_size = 2;
1740         constexpr Char_type dot_dot_storage[dot_dot_size + 1] = {dot, dot};
1741         string_view_type dot_dot(dot_dot_storage, dot_dot_size);
1742         if(empty())
1743             return {};
1744         auto relative_path_index_range = get_relative_path_index_range(value);
1745         auto root_name_index_range = get_root_name_index_range(value);
1746         bool has_root_dir = has_root_directory();
1747         basic_path retval;
1748         retval.value.reserve(value.size());
1749         retval.value.assign(value.data() + relative_path_index_range.begin,
1750                             relative_path_index_range.size());
1751         std::size_t new_size = 0;
1752         for(std::size_t i = 0; i < retval.value.size(); i++)
1753         {
1754             if(is_separator(retval.value[i]))
1755             {
1756                 while(i + 1 < retval.value.size() && is_separator(retval.value[i + 1]))
1757                     i++;
1758                 retval.value[new_size++] = preferred_separator;
1759             }
1760             else
1761             {
1762                 retval.value[new_size++] = retval.value[i];
1763             }
1764         }
1765         retval.value.resize(new_size);
1766         new_size = 0;
1767         bool last_was_separator = true;
1768         for(std::size_t i = 0; i < retval.value.size(); i++)
1769         {
1770             if(last_was_separator && retval.value[i] == dot)
1771             {
1772                 if(i + 1 >= retval.value.size())
1773                     break; // don't write the dot
1774                 if(retval.value[i + 1] == preferred_separator)
1775                 {
1776                     i++;
1777                     last_was_separator = true;
1778                     continue; // skip the dot and separator
1779                 }
1780             }
1781             if(retval.value[i] == preferred_separator)
1782                 last_was_separator = true;
1783             else
1784                 last_was_separator = false;
1785             retval.value[new_size++] = retval.value[i];
1786         }
1787         retval.value.resize(new_size);
1788         retval.parts.reserve(parts.size());
1789         new_size = 0;
1790         parse<true>(retval.value,
1791                     [&](Path_index_range index_range, Path_part_kind part_kind) noexcept
1792                     {
1793                         if(part_kind == Path_part_kind::path_separator)
1794                             return true;
1795                         assert(part_kind == Path_part_kind::file_name);
1796                         if(index_range.size() == 2 && retval.value[index_range.begin] == dot
1797                            && retval.value[index_range.begin + 1] == dot)
1798                         {
1799                             if(new_size == 0 && has_root_dir)
1800                                 return true;
1801                             if(new_size != 0)
1802                             {
1803                                 new_size--;
1804                                 return true;
1805                             }
1806                         }
1807                         if(new_size >= retval.parts.size())
1808                             retval.parts.emplace_back();
1809                         retval.parts[new_size].value.assign(retval.value.data() + index_range.begin,
1810                                                             index_range.size());
1811                         retval.parts[new_size].kind = Path_part_kind::file_name;
1812                         new_size++;
1813                         return true;
1814                     });
1815         if(new_size >= 2 && retval.parts[new_size - 1].value.empty()
1816            && retval.parts[new_size - 2].value == dot_dot)
1817             new_size--;
1818         std::size_t needed_space = 0;
1819         if(!root_name_index_range.empty())
1820             needed_space++;
1821         if(has_root_dir)
1822             needed_space++;
1823         if(needed_space > 0)
1824         {
1825             while(retval.parts.size() < new_size + needed_space)
1826                 retval.parts.emplace_back();
1827             for(std::size_t source = new_size - 1, target = new_size + needed_space - 1, i = 0;
1828                 i < new_size;
1829                 source--, target--, i++)
1830                 retval.parts[target] = std::move(retval.parts[source]);
1831             std::size_t root_part_index = 0;
1832             if(!root_name_index_range.empty())
1833             {
1834                 retval.parts[root_part_index].value.assign(
1835                     value.data() + root_name_index_range.begin, root_name_index_range.size());
1836                 change_separator(retval.parts[root_part_index].value, static_cast<Char_type>('/'));
1837                 retval.parts[root_part_index].parts = Parts();
1838                 retval.parts[root_part_index].kind = begin()->kind;
1839                 root_part_index++;
1840             }
1841             if(has_root_dir)
1842             {
1843                 retval.parts[root_part_index].value.assign(1, static_cast<Char_type>('/'));
1844                 retval.parts[root_part_index].parts = Parts();
1845                 retval.parts[root_part_index].kind = Path_part_kind::root_dir;
1846             }
1847         }
1848         if(new_size + needed_space == 0)
1849         {
1850             if(retval.parts.empty())
1851                 retval.parts.emplace_back();
1852             retval.parts[new_size].value.assign(1, dot);
1853             retval.parts[new_size].parts = Parts();
1854             retval.parts[new_size].kind = Path_part_kind::file_name;
1855             new_size++;
1856         }
1857         while(retval.parts.size() > new_size + needed_space)
1858             retval.parts.pop_back();
1859         retval.value.clear();
1860         bool need_seperator = false;
1861         for(auto &part : retval.parts)
1862         {
1863             switch(part.kind)
1864             {
1865             case Path_part_kind::absolute_root_name:
1866             case Path_part_kind::relative_root_name:
1867                 retval.value += part.value;
1868                 change_separator(retval.value, preferred_separator);
1869                 need_seperator = false;
1870                 // absolute_root_name will be followed by root_dir if we need a seperator
1871                 continue;
1872             case Path_part_kind::file_name:
1873                 if(need_seperator)
1874                     retval.value += preferred_separator;
1875                 retval.value += part.value;
1876                 need_seperator = true;
1877                 continue;
1878             case Path_part_kind::root_dir:
1879                 retval.value += preferred_separator;
1880                 need_seperator = false;
1881                 continue;
1882             case Path_part_kind::path_separator:
1883             case Path_part_kind::multiple_parts:
1884                 break;
1885             }
1886             assert(false);
1887         }
1888         retval.parse();
1889         return retval;
1890     }
1891 #warning finish
1892 };
1893
1894 template <detail::Path_traits_kind Traits_kind,
1895           typename Char_type,
1896           Char_type Preferred_separator,
1897           bool Needs_root_name_to_be_absolute>
1898 void swap(
1899     basic_path<Traits_kind, Char_type, Preferred_separator, Needs_root_name_to_be_absolute> &l,
1900     basic_path<Traits_kind, Char_type, Preferred_separator, Needs_root_name_to_be_absolute>
1901         &r) noexcept
1902 {
1903     l.swap(r);
1904 }
1905
1906 template <detail::Path_traits_kind Traits_kind,
1907           typename Char_type,
1908           Char_type Preferred_separator,
1909           bool Needs_root_name_to_be_absolute>
1910 constexpr Char_type basic_path<Traits_kind,
1911                                Char_type,
1912                                Preferred_separator,
1913                                Needs_root_name_to_be_absolute>::preferred_separator;
1914
1915 template <detail::Path_traits_kind Traits_kind,
1916           typename Char_type,
1917           Char_type Preferred_separator,
1918           bool Needs_root_name_to_be_absolute>
1919 basic_path<Traits_kind, Char_type, Preferred_separator, Needs_root_name_to_be_absolute>
1920     *basic_path<Traits_kind, Char_type, Preferred_separator, Needs_root_name_to_be_absolute>::
1921         Parts::allocate(std::size_t count)
1922 {
1923     if(count == 0)
1924         return nullptr;
1925     return std::allocator<basic_path>().allocate(count);
1926 }
1927
1928 template <detail::Path_traits_kind Traits_kind,
1929           typename Char_type,
1930           Char_type Preferred_separator,
1931           bool Needs_root_name_to_be_absolute>
1932 void basic_path<Traits_kind, Char_type, Preferred_separator, Needs_root_name_to_be_absolute>::
1933     Parts::deallocate(basic_path *values, std::size_t count) noexcept
1934 {
1935     if(count != 0)
1936         std::allocator<basic_path>().deallocate(values, count);
1937 }
1938
1939 typedef basic_path<> path;
1940 }
1941 }
1942 }
1943
1944 #endif /* UTIL_FILESYSTEM_H_ */