Compiler Explorer

Source code

#include <atomic>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iostream>
#include <memory>
#include <optional>
#include <string>
#include <utility>
#include <vector>

using std::move;
  using std::optional;
  using std::ostream;
  using std::pair;
  using std::reference_wrapper;
  using std::string;
  using std::unique_ptr;

using std::atomic;
  using std::memory_order;
  using std::memory_order_relaxed;
  using std::memory_order_consume;
  using std::memory_order_acquire;
  using std::memory_order_release;
  using std::memory_order_acq_rel;
  using std::memory_order_seq_cst;
  using atomic_count = atomic<size_t>;
  template <typename T>
  struct relaxed_atomic: atomic<T>
  {
    using atomic<T>::atomic;
    relaxed_atomic (const relaxed_atomic& a) noexcept
        : atomic<T> (a.load (memory_order_relaxed)) {}
    operator T () const noexcept {return this->load (memory_order_relaxed);}
    T operator= (T v) noexcept {
      this->store (v, memory_order_relaxed); return v;}
    T operator= (const relaxed_atomic& a) noexcept {
      return *this = a.load (memory_order_relaxed);}
  };
  template <typename T>
  struct relaxed_atomic<T*>: atomic<T*>
  {
    using atomic<T*>::atomic;
    relaxed_atomic (const relaxed_atomic& a) noexcept
        : atomic<T*> (a.load (memory_order_relaxed)) {}
    operator T* () const noexcept {return this->load (memory_order_relaxed);}
    T& operator* () const noexcept {return *this->load (memory_order_relaxed);}
    T* operator-> () const noexcept {return this->load (memory_order_relaxed);}
    T* operator= (T* v) noexcept {
      this->store (v, memory_order_relaxed); return v;}
    T* operator= (const relaxed_atomic& a) noexcept {
      return *this = a.load (memory_order_relaxed);}
  };

template <typename T, std::size_t N>
  struct small_allocator_buffer
  {
    using value_type = T;
    alignas (alignof (value_type)) char data_[sizeof (value_type) * N];
    bool free_ = true;
    small_allocator_buffer () = default;
    small_allocator_buffer (small_allocator_buffer&&) = delete;
    small_allocator_buffer (const small_allocator_buffer&) = delete;
    small_allocator_buffer& operator= (small_allocator_buffer&&) = delete;
    small_allocator_buffer& operator= (const small_allocator_buffer&) = delete;
  };
  template <typename T,
            std::size_t N,
            typename B = small_allocator_buffer<T, N>>
  class small_allocator
  {
  public:
    using buffer_type = B;
    explicit
    small_allocator (buffer_type* b) noexcept: buf_ (b) {}
  public:
    using value_type = T;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reference = value_type&;
    using const_reference = const value_type&;
    static void destroy (T* p) {p->~T ();}
    template <typename... A>
    static void construct (T* p, A&&... a)
    {
      ::new (static_cast<void*> (p)) T (std::forward<A> (a)...);
    }
    template <typename U>
    struct rebind {using other = small_allocator<U, N, B>;};
    template <typename U>
    explicit
    small_allocator (const small_allocator<U, N, B>& x) noexcept
      : buf_ (x.buf_) {}
    T*
    allocate (std::size_t n)
    {
      if (std::is_same<T, typename buffer_type::value_type>::value)
      {
        if (buf_->free_)
        {
         (static_cast <bool> (
         n >= N
	     ) ? void (0) : void (0) )
                        ;
          if (n == N)
          {
            buf_->free_ = false;
            return reinterpret_cast<T*> (buf_->data_);
          }
        }
      }
      return static_cast<T*> (::operator new (sizeof (T) * n));
    }
    void
    deallocate (void* p, std::size_t) noexcept
    {
      if (p == buf_->data_)
        buf_->free_ = true;
      else
        ::operator delete (p);
    }
    friend bool
    operator== (small_allocator x, small_allocator y) noexcept
    {
      return (x.buf_ == y.buf_) || (x.buf_->free_ && y.buf_->free_);
    }
    friend bool
    operator!= (small_allocator x, small_allocator y) noexcept
    {
      return !(x == y);
    }
    small_allocator
    select_on_container_copy_construction () const noexcept
    {
     (static_cast <bool> (
     false
	 ) ? void (0) : void (0) )
                   ;
      return small_allocator (nullptr);
    }
    using propagate_on_container_swap = std::true_type;
    void
    swap (small_allocator&) = delete;
  private:
    template <typename, std::size_t, typename>
    friend class small_allocator;
    buffer_type* buf_;
  };

template <typename T, std::size_t N>
  class small_vector: private small_allocator_buffer<T, N>,
                      public std::vector<T, small_allocator<T, N>>
  {
  public:
    static constexpr const std::size_t small_size = N;
    using buffer_type = small_allocator_buffer<T, N>;
    using allocator_type = small_allocator<T, N>;
    using base_type = std::vector<T, allocator_type>;
    small_vector ()
      : base_type (allocator_type (this))
    {
      reserve ();
    }
    small_vector (std::initializer_list<T> v)
      : base_type (allocator_type (this))
    {
      if (v.size () <= N)
        reserve ();
      static_cast<base_type&> (*this) = v;
    }
    template <typename I>
    small_vector (I b, I e)
      : base_type (allocator_type (this))
    {
      std::size_t n (0);
      for (I i (b); i != e && n <= N; ++i) ++n;
      if (n <= N)
        reserve ();
      this->assign (b, e);
    }
    explicit
    small_vector (std::size_t n)
      : base_type (allocator_type (this))
    {
      if (n <= N)
        reserve ();
      this->resize (n);
    }
    small_vector (std::size_t n, const T& x)
      : base_type (allocator_type (this))
    {
      if (n <= N)
        reserve ();
      this->assign (n, x);
    }
    small_vector (const small_vector& v)
      : buffer_type (), base_type (allocator_type (this))
    {
      if (v.size () <= N)
        reserve ();
      static_cast<base_type&> (*this) = v;
    }
    small_vector&
    operator= (const small_vector& v)
    {
      static_cast<base_type&> (*this) = v;
      return *this;
    }
    small_vector (small_vector&& v)
      : base_type (allocator_type (this))
    {
      if (v.size () <= N)
        reserve ();
      *this = std::move (v);
    }
    small_vector&
    operator= (small_vector&& v)
    {
      static_cast<base_type&> (*this) = std::move (v);
      return *this;
    }
    small_vector&
    operator= (std::initializer_list<T> v)
    {
      static_cast<base_type&> (*this) = v;
      return *this;
    }
    void
    swap (small_vector&) = delete;
    void
    reserve (std::size_t n = N)
    {
      base_type::reserve (n < N ? N : n);
    }
    void
    shrink_to_fit ()
    {
      if (this->capacity () > N)
        base_type::shrink_to_fit ();
    }
  };

template <typename T>
  class vector_view
  {
  public:
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using const_pointer = const T*;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using iterator = T*;
    using const_iterator = const T*;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    vector_view (): data_ (nullptr), size_ (0) {}
    vector_view (T* d, size_type s): data_ (d), size_ (s) {}
    template <typename T1, typename A>
    vector_view (std::vector<T1, A>& v)
        : data_ (v.data ()), size_ (v.size ()) {}
    template <typename T1, typename A>
    vector_view (const std::vector<T1, A>& v)
        : data_ (v.data ()), size_ (v.size ()) {}
    template <typename T1>
    vector_view (const vector_view<T1>& v)
        : data_ (v.data ()), size_ (v.size ()) {}
    vector_view (vector_view&&) = default;
    vector_view (const vector_view&) = default;
    vector_view& operator= (vector_view&&) = default;
    vector_view& operator= (const vector_view&) = default;
    iterator begin() const {return data_;}
    iterator end() const {return data_ + size_;}
    const_iterator cbegin() const {return data_;}
    const_iterator cend() const {return data_ + size_;}
    reverse_iterator rbegin() const {return reverse_iterator (end ());}
    reverse_iterator rend() const {return reverse_iterator (begin ());}
    const_reverse_iterator crbegin() const {
      return const_reverse_iterator (cend ());}
    const_reverse_iterator crend() const {
      return const_reverse_iterator (cbegin ());}
    size_type size() const {return size_;}
    bool empty() const {return size_ == 0;}
    reference operator[](size_type n) const {return data_[n];}
    reference front() const {return data_[0];}
    reference back() const {return data_[size_ - 1];}
    reference at(size_type n) const
    {
      if (n >= size_)
        throw std::out_of_range ("index out of range");
      return data_[n];
    }
    T* data() const {return data_;}
    void assign (T* d, size_type s) {data_ = d; size_ = s;}
    void clear () {data_ = nullptr; size_ = 0;}
    void swap (vector_view& v) {
      std::swap (data_, v.data_); std::swap (size_, v.size_);}
  private:
    T* data_;
    size_type size_;
  };
  template<typename T> bool operator== (vector_view<T> l, vector_view<T> r);
  template<typename T> bool operator!= (vector_view<T> l, vector_view<T> r);
  template<typename T> bool operator< (vector_view<T> l, vector_view<T> r);
  template<typename T> bool operator> (vector_view<T> l, vector_view<T> r);
  template<typename T> bool operator<= (vector_view<T> l, vector_view<T> r);
  template<typename T> bool operator>= (vector_view<T> l, vector_view<T> r);

struct invalid_path_base: public std::invalid_argument
  {
    invalid_path_base ();
  };
  template <typename C>
  struct invalid_basic_path: invalid_path_base
  {
    using string_type = std::basic_string<C>;
    using size_type = typename string_type::size_type;
    string_type path;
    explicit
    invalid_basic_path (const string_type& p): path (p) {}
    explicit
    invalid_basic_path (const C* p): path (p) {}
    invalid_basic_path (const C* p, size_type n): path (p, n) {}
  };
  enum class path_abnormality: std::uint16_t
  {
    none = 0x00,
    separator = 0x01,
    current = 0x02,
    parent = 0x04
  };
  inline path_abnormality operator& (path_abnormality, path_abnormality);
  inline path_abnormality operator| (path_abnormality, path_abnormality);
  inline path_abnormality operator&= (path_abnormality&, path_abnormality);
  inline path_abnormality operator|= (path_abnormality&, path_abnormality);
  template <typename C>
  struct path_traits
  {
    using string_type = std::basic_string<C>;
    using char_traits_type = typename string_type::traits_type;
    using size_type = typename string_type::size_type;
    static constexpr const C directory_separator = '/';
    static constexpr const C path_separator = ':';
    static constexpr const char* const directory_separators = "/";
    static bool
    is_separator (C c)
    {
      return c == '/';
    }
    static size_type
    separator_index (C c)
    {
      return c == '/' ? 1 : 0;
    }
    static bool
    absolute (const string_type& s)
    {
      return absolute (s.c_str (), s.size ());
    }
    static bool
    absolute (const C* s)
    {
      return absolute (s, char_traits_type::length (s));
    }
    static bool
    absolute (const C* s, size_type n)
    {
      return n != 0 && is_separator (s[0]);
    }
    static bool
    current (const string_type& s)
    {
      return current (s.c_str (), s.size ());
    }
    static bool
    current (const C* s)
    {
      return current (s, char_traits_type::length (s));
    }
    static bool
    current (const C* s, size_type n)
    {
      return n == 1 && s[0] == '.';
    }
    static bool
    parent (const string_type& s)
    {
      return parent (s.c_str (), s.size ());
    }
    static bool
    parent (const C* s)
    {
      return parent (s, char_traits_type::length (s));
    }
    static bool
    parent (const C* s, size_type n)
    {
      return n == 2 && s[0] == '.' && s[1] == '.';
    }
    static bool
    normalized (const string_type& s, bool sep)
    {
      return normalized (s.c_str (), s.size (), sep);
    }
    static bool
    normalized (const C* s, bool sep)
    {
      return normalized (s, char_traits_type::length (s), sep);
    }
    static bool
    normalized (const C*, size_type, bool);
    static path_abnormality
    abnormalities (const string_type& s)
    {
      return abnormalities (s.c_str (), s.size ());
    }
    static path_abnormality
    abnormalities (const C* s)
    {
      return abnormalities (s, char_traits_type::length (s));
    }
    static path_abnormality
    abnormalities (const C*, size_type);
    static bool
    root (const string_type& s)
    {
      return root (s.c_str (), s.size ());
    }
    static bool
    root (const C* s)
    {
      return root (s, char_traits_type::length (s));
    }
    static bool
    root (const C* s, size_type n)
    {
    return n == 1 && is_separator (s[0]);
    }
    static size_type
    find_separator (string_type const& s,
                    size_type pos = 0,
                    size_type n = string_type::npos)
    {
      if (n == string_type::npos)
        n = s.size ();
      const C* r (find_separator (s.c_str () + pos, n - pos));
      return r != nullptr ? r - s.c_str () : string_type::npos;
    }
    static const C*
    find_separator (const C* s)
    {
      return find_separator (s, char_traits_type::length (s));
    }
    static const C*
    find_separator (const C* s, size_type n)
    {
      for (const C* e (s + n); s != e; ++s)
      {
        if (is_separator (*s))
          return s;
      }
      return nullptr;
    }
    static size_type
    rfind_separator (string_type const& s, size_type pos = string_type::npos)
    {
      if (pos == string_type::npos)
        pos = s.size ();
      else
        pos++;
      const C* r (rfind_separator (s.c_str (), pos));
      return r != nullptr ? r - s.c_str () : string_type::npos;
    }
    static const C*
    rfind_separator (const C* s)
    {
      return rfind_separator (s, char_traits_type::length (s));
    }
    static const C*
    rfind_separator (const C* s, size_type n)
    {
      for (; n != 0; --n)
      {
        if (is_separator (s[n - 1]))
          return s + n - 1;
      }
      return nullptr;
    }
    static size_type
    find_extension (string_type const& s, size_type n = string_type::npos)
    {
      if (n == string_type::npos)
        n = s.size ();
      const C* r (find_extension (s.c_str (), n));
      return r != nullptr ? r - s.c_str () : string_type::npos;
    }
    static const C*
    find_extension (const C* s)
    {
      return find_extension (s, char_traits_type::length (s));
    }
    static const C*
    find_extension (const C* s, size_type n)
    {
      size_type i (n);
      for (; i > 0; --i)
      {
        C c (s[i - 1]);
        if (c == '.')
          break;
        if (is_separator (c))
        {
          i = 0;
          break;
        }
      }
      if (i > 1 && !is_separator (s[i - 2]) && i != n)
        return s + i - 1;
      else
        return nullptr;
    }
    static size_type
    find_leaf (string_type const& s)
    {
      const C* r (find_leaf (s.c_str (), s.size ()));
      return r != nullptr ? r - s.c_str () : string_type::npos;
    }
    static const C*
    find_leaf (const C* s)
    {
      return find_leaf (s, char_traits_type::length (s));
    }
    static const C*
    find_leaf (const C* s, size_type n)
    {
      const C* p;
      return n == 0
        ? nullptr
        : (p = rfind_separator (s, n - 1)) == nullptr ? s : ++p;
    }
    static int
    compare (string_type const& l,
             string_type const& r,
             size_type n = string_type::npos)
    {
      return compare (l.c_str (), n < l.size () ? n : l.size (),
                      r.c_str (), n < r.size () ? n : r.size ());
    }
    static int
    compare (const C* l, size_type ln, const C* r, size_type rn)
    {
      for (size_type i (0), n (ln < rn ? ln : rn); i != n; ++i)
      {
        C lc (l[i]), rc (r[i]);
        if (is_separator (lc) && is_separator (rc))
          continue;
        if (lc < rc) return -1;
        if (lc > rc) return 1;
      }
      return ln < rn ? -1 : (ln > rn ? 1 : 0);
    }
    static void
    canonicalize (string_type& s, char ds = '\0')
    {
      if (ds == '\0')
        ds = directory_separator;
      for (size_t i (0), n (s.size ()); i != n; ++i)
        if (is_separator (s[i]) && s[i] != ds)
          s[i] = ds;
    }
    static void
    canonicalize (C* s, size_type n, char ds = '\0')
    {
      if (ds == '\0')
        ds = directory_separator;
      for (const C* e (s + n); s != e; ++s)
        if (is_separator (*s) && *s != ds)
          *s = ds;
    }
    static string_type
    current_directory ();
    static void
    current_directory (string_type const&);
    static string_type
    home_directory ();
    static string_type
    temp_directory ();
    static string_type
    temp_name (string_type const& prefix);
    static void
    realize (string_type&);
  };
  template <typename C, typename K>
  class basic_path;
  template <typename C> struct any_path_kind;
  template <typename C> struct dir_path_kind;
  using path = basic_path<char, any_path_kind<char>>;
  using dir_path = basic_path<char, dir_path_kind<char>>;
  using invalid_path = invalid_basic_path<char>;
  template <class P, class C, class K> P path_cast (const basic_path<C, K>&);
  template <class P, class C, class K> P path_cast (basic_path<C, K>&&);
  template <typename P>
  struct basic_path_name;
  using path_name = basic_path_name<path>;
  using dir_path_name = basic_path_name<dir_path>;
  template <typename P>
  struct basic_path_name_value;
  using path_name_value = basic_path_name_value<path>;
  using dir_name_value = basic_path_name_value<dir_path>;
  template <typename P>
  struct basic_path_name_view;
  using path_name_view = basic_path_name_view<path>;
  using dir_name_view = basic_path_name_view<dir_path>;
  template <typename C>
  struct path_data
  {
    using string_type = std::basic_string<C>;
    using size_type = typename string_type::size_type;
    using difference_type = typename string_type::difference_type;
    string_type path_;
    difference_type tsep_;
    size_type
    _size () const {return path_.size () + (tsep_ < 0 ? -1 : 0);}
    void
    _swap (path_data& d) {path_.swap (d.path_); std::swap (tsep_, d.tsep_);}
    void
    _clear () {path_.clear (); tsep_ = 0;}
    path_data ()
        : tsep_ (0) {}
    path_data (string_type&& p, difference_type ts)
        : path_ (std::move (p)), tsep_ (path_.empty () ? 0 : ts) {}
    explicit
    path_data (string_type&& p)
        : path_ (std::move (p)) { _init (); }
    void
    _init ()
    {
      size_type n (path_.size ()), i;
      if (n != 0 && (i = path_traits<C>::separator_index (path_[n - 1])) != 0)
      {
        if (n == 1)
          tsep_ = -1;
        else
        {
          tsep_ = i;
          path_.pop_back ();
        }
      }
      else
        tsep_ = 0;
    }
  };
  template <typename C>
  struct any_path_kind
  {
    class base_type: public path_data<C>
    {
    protected:
      using path_data<C>::path_data;
      base_type () = default;
      base_type (path_data<C>&& d): path_data<C> (std::move (d)) {}
    };
    using dir_type = basic_path<C, dir_path_kind<C>>;
    using data_type = path_data<C>;
    using string_type = std::basic_string<C>;
    static data_type
    init (string_type&&, bool exact = false);
    static void
    cast (data_type&) {}
  };
  template <typename C>
  struct dir_path_kind
  {
    using base_type = basic_path<C, any_path_kind<C>>;
    using dir_type = basic_path<C, dir_path_kind<C>>;
    using data_type = path_data<C>;
    using string_type = std::basic_string<C>;
    static data_type
    init (string_type&&, bool exact = false);
    static void
    cast (data_type&);
  };
  template <typename C, typename K>
  class basic_path: public K::base_type
  {
  public:
    using string_type = std::basic_string<C>;
    using size_type = typename string_type::size_type;
    using difference_type = typename string_type::difference_type;
    using traits_type = path_traits<C>;
    struct iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using base_type = typename K::base_type;
    using dir_type = typename K::dir_type;
    basic_path () {}
    explicit
    basic_path (C const* s): base_type (K::init (s)) {}
    basic_path (C const* s, size_type n)
        : base_type (K::init (string_type (s, n))) {}
    explicit
    basic_path (string_type s): base_type (K::init (std::move (s))) {}
    basic_path (const string_type& s, size_type n)
        : base_type (K::init (string_type (s, 0, n))) {}
    basic_path (const string_type& s, size_type p, size_type n)
        : base_type (K::init (string_type (s, p, n))) {}
    enum exact_type {exact};
    basic_path (string_type&& s, exact_type)
        : base_type (K::init (std::move (s), true)) {}
    basic_path (const iterator& begin, const iterator& end);
    basic_path (const reverse_iterator& rbegin, const reverse_iterator& rend)
        : basic_path (rend.base (), rbegin.base ()) {}
    void
    swap (basic_path& p) {this->_swap (p);}
    void
    clear () {this->_clear ();}
    static dir_type
    current_directory () {
      return dir_type (traits_type::current_directory ());}
    static void
    current_directory (basic_path const&);
    static dir_type
    home_directory () {return dir_type (traits_type::home_directory ());}
    static dir_type
    temp_directory () {return dir_type (traits_type::temp_directory ());}
    static basic_path
    temp_path (const string_type& prefix)
    {
      basic_path r (temp_directory ());
      r /= traits_type::temp_name (prefix);
      return r;
    }
  public:
    bool
    empty () const {return this->path_.empty ();}
    size_type
    size () const {return this->path_.size ();}
    bool
    simple () const;
    bool
    absolute () const;
    bool
    relative () const {return !absolute ();}
    bool
    root () const;
    bool
    current () const;
    bool
    parent () const;
    bool
    normalized (bool sep = true) const;
    path_abnormality
    abnormalities () const;
    bool
    to_directory () const {return this->tsep_ != 0;}
    bool
    sub (const basic_path&) const;
    bool
    sup (const basic_path&) const;
  public:
    basic_path
    leaf () const;
    basic_path&
    make_leaf ();
    basic_path
    leaf (basic_path const&) const;
    dir_type
    directory () const;
    basic_path&
    make_directory ();
    dir_type
    directory (basic_path const&) const;
    dir_type
    root_directory () const;
    basic_path
    base () const;
    basic_path&
    make_base ();
    string_type
    extension () const;
    const C*
    extension_cstring () const;
    basic_path
    relative (basic_path) const;
  public:
    struct iterator
    {
      using value_type = string_type ;
      using pointer = string_type*;
      using reference = string_type ;
      using size_type = typename string_type::size_type;
      using difference_type = std::ptrdiff_t ;
      using iterator_category = std::bidirectional_iterator_tag ;
      using data_type = path_data<C>;
      iterator (): p_ (nullptr) {}
      iterator (const data_type* p, size_type b, size_type e)
          : p_ (p), b_ (b), e_ (e) {}
      iterator (const basic_path& p, const iterator& i)
          : p_ (&p), b_ (i.b_), e_ (i.e_) {}
      iterator&
      operator++ ()
      {
        const string_type& s (p_->path_);
        b_ = e_ != string_type::npos && ++e_ != s.size ()
          ? e_
          : string_type::npos;
        e_ = b_ != string_type::npos
             ? traits_type::find_separator (s, b_)
             : b_;
        return *this;
      }
      iterator&
      operator-- ()
      {
        const string_type& s (p_->path_);
        e_ = b_ == string_type::npos
          ? (traits_type::is_separator (s.back ())
             ? s.size () - 1
             : string_type::npos)
          : b_ - 1;
        b_ = e_ == 0
          ? string_type::npos
          : traits_type::rfind_separator (s,
                                          e_ != string_type::npos
                                          ? e_ - 1
                                          : e_);
        b_ = b_ == string_type::npos
          ? 0
          : b_ + 1;
        return *this;
      }
      iterator
      operator++ (int) {iterator r (*this); operator++ (); return r;}
      iterator
      operator-- (int) {iterator r (*this); operator-- (); return r;}
      string_type
      operator* () const
      {
        return string_type (p_->path_,
                            b_,
                            e_ != string_type::npos ? e_ - b_ : e_);
      }
      C
      separator () const
      {
        return e_ != string_type::npos
          ? p_->path_[e_]
          : (p_->tsep_ > 0
             ? path_traits<C>::directory_separators[p_->tsep_ - 1]
             : 0);
      }
      pointer operator-> () const = delete;
      friend bool
      operator== (const iterator& x, const iterator& y)
      {
        return x.p_ == y.p_ && x.b_ == y.b_ && x.e_ == y.e_;
      }
      friend bool
      operator!= (const iterator& x, const iterator& y) {return !(x == y);}
    private:
      friend class basic_path;
      const data_type* p_;
      size_type b_;
      size_type e_;
    };
    iterator begin () const;
    iterator end () const;
    reverse_iterator rbegin () const {return reverse_iterator (end ());}
    reverse_iterator rend () const {return reverse_iterator (begin ());}
  public:
    basic_path&
    canonicalize (char dir_sep = '\0');
    basic_path&
    normalize (bool actual = false, bool cur_empty = false);
    basic_path&
    complete ();
    basic_path&
    realize ();
  public:
    basic_path&
    operator/= (basic_path const&);
    basic_path&
    operator/= (string_type const&);
    basic_path&
    operator/= (const C*);
    void
    combine (string_type const&, C separator);
    void
    combine (const C*, C separator);
    void
    combine (const C*, size_type, C separator);
    basic_path&
    operator+= (string_type const&);
    basic_path&
    operator+= (const C*);
    basic_path&
    operator+= (C);
    void
    append (const C*, size_type);
    template <typename K1>
    int
    compare (const basic_path<C, K1>& x) const {
      return traits_type::compare (this->path_, x.path_);}
  public:
    const string_type&
    string () const& {return this->path_;}
    string_type
    representation () const&;
    string_type
    string () && {string_type r; r.swap (this->path_); return r;}
    string_type
    representation () &&;
    C
    separator () const;
    string_type
    separator_string () const;
    string_type
    posix_string () const&;
    string_type
    posix_representation () const&;
    string_type
    posix_string () &&;
    string_type
    posix_representation () &&;
  protected:
    using data_type = path_data<C>;
    explicit
    basic_path (data_type&& d): base_type (std::move (d)) {}
    using base_type::_size;
    using base_type::_init;
    void
    combine_impl (const C*, size_type, difference_type);
    void
    combine_impl (const C*, size_type);
    template <class C1, class K1>
    friend class basic_path;
    template <class C1, class K1, class K2>
    friend basic_path<C1, K1>
    path_cast_impl (const basic_path<C1, K2>&, basic_path<C1, K1>*);
    template <class C1, class K1, class K2>
    friend basic_path<C1, K1>
    path_cast_impl (basic_path<C1, K2>&&, basic_path<C1, K1>*);
  };

std::string ucase (const char*, std::size_t n = std::string::npos);
  std::string ucase (const std::string&,
                     std::size_t p = 0,
                     std::size_t n = std::string::npos);
  std::string& ucase (std::string&,
                      std::size_t p = 0,
                      std::size_t n = std::string::npos);
  void ucase (char*, std::size_t);
  char lcase (char);
  std::string lcase (const char*, std::size_t n = std::string::npos);
  std::string lcase (const std::string&,
                     std::size_t p = 0,
                     std::size_t n = std::string::npos);
  std::string& lcase (std::string&,
                      std::size_t p = 0,
                      std::size_t n = std::string::npos);
  void lcase (char*, std::size_t);
  int icasecmp (char, char);
  int icasecmp (const std::string&, const std::string&,
                std::size_t = std::string::npos);
  int icasecmp (const std::string&, const char*,
                std::size_t = std::string::npos);
  int icasecmp (const char*, const char*, std::size_t = std::string::npos);
  struct icase_compare_string
  {
    bool operator() (const std::string& x, const std::string& y) const
    {
      return icasecmp (x, y) < 0;
    }
  };
  struct icase_compare_c_string
  {
    bool operator() (const char* x, const char* y) const
    {
      return icasecmp (x, y) < 0;
    }
  };
  std::string&
  trim (std::string&);
  inline std::string
  trim (std::string&& s)
  {
    return move (trim (s));
  }
  std::size_t
  next_word (const std::string&, std::size_t& b, std::size_t& e,
             char d1 = ' ', char d2 = '\0');
  std::size_t
  next_word (const std::string&, std::size_t n, std::size_t& b, std::size_t& e,
             char d1 = ' ', char d2 = '\0');
  inline char
  ucase (char c)
  {
    return std::toupper (c);
  }
  inline void
  ucase (char* s, std::size_t n)
  {
    for (const char* e (s + n); s != e; ++s)
      *s = ucase (*s);
  }
  inline std::string&
  ucase (std::string& s, std::size_t p, std::size_t n)
  {
    if (n == std::string::npos)
      n = s.size () - p;
    if (n != 0)
    {
      s.front () = s.front ();
      ucase (const_cast<char*> (s.data ()) + p, n);
    }
    return s;
  }
  inline std::string
  ucase (const char* s, std::size_t n)
  {
    std::string r (s, n == std::string::npos ? std::strlen (s) : n);
    return ucase (r);
  }
  inline std::string
  ucase (const std::string& s, std::size_t p, std::size_t n)
  {
    return ucase (s.c_str () + p, n != std::string::npos ? n : s.size () - p);
  }
  inline char
  lcase (char c)
  {
    return std::tolower (c);
  }
  inline void
  lcase (char* s, std::size_t n)
  {
    for (const char* e (s + n); s != e; ++s)
      *s = lcase (*s);
  }
  inline std::string&
  lcase (std::string& s, std::size_t p, std::size_t n)
  {
    if (n == std::string::npos)
      n = s.size () - p;
    if (n != 0)
    {
      s.front () = s.front ();
      lcase (const_cast<char*> (s.data ()) + p, n);
    }
    return s;
  }
  inline std::string
  lcase (const char* s, std::size_t n)
  {
    std::string r (s, n == std::string::npos ? std::strlen (s) : n);
    return lcase (r);
  }
  inline std::string
  lcase (const std::string& s, std::size_t p, std::size_t n)
  {
    return lcase (s.c_str () + p, n != std::string::npos ? n : s.size () - p);
  }
  inline int
  icasecmp (char l, char r)
  {
    l = lcase (l);
    r = lcase (r);
    return l < r ? -1 : (l > r ? 1 : 0);
  }
  inline int
  icasecmp (const char* l, const char* r, std::size_t n)
  {
    return n == std::string::npos ? strcasecmp (l, r) : strncasecmp (l, r, n);
  }
  inline int
  icasecmp (const std::string& l, const std::string& r, std::size_t n)
  {
    return icasecmp (l.c_str (), r.c_str (), n);
  }
  inline int
  icasecmp (const std::string& l, const char* r, std::size_t n)
  {
    return icasecmp (l.c_str (), r, n);
  }
  inline bool
  alpha (char c)
  {
    return std::isalpha (c);
  }
  inline bool
  digit (char c)
  {
    return std::isdigit (c);
  }
  inline bool
  alnum (char c)
  {
    return std::isalnum (c);
  }
  inline bool
  xdigit (char c)
  {
    return std::isxdigit (c);
  }
  inline bool
  alpha (wchar_t c)
  {
    return std::iswalpha (c);
  }
  inline bool
  digit (wchar_t c)
  {
    return std::iswdigit (c);
  }
  inline bool
  alnum (wchar_t c)
  {
    return std::iswalnum (c);
  }
  inline bool
  xdigit (wchar_t c)
  {
    return std::iswxdigit (c);
  }
  inline std::size_t
  next_word (const std::string& s, std::size_t& b, std::size_t& e,
             char d1, char d2)
  {
    return next_word (s, s.size (), b, e, d1, d2);
  }
  inline size_t
  next_word (const std::string& s,
             std::size_t n, std::size_t& b, std::size_t& e,
             char d1, char d2)
  {
    if (b != e)
      b = e;
    for (; b != n && (s[b] == d1 || s[b] == d2); ++b) ;
    if (b == n)
    {
      e = n;
      return 0;
    }
    for (e = b + 1; e != n && s[e] != d1 && s[e] != d2; ++e) ;
    return e - b;
  }
  inline std::string&
  sanitize_identifier (std::string& s)
  {
    std::for_each (s.begin (), s.end (), [] (char& c)
                   {
                     if (!alnum (c) && c != '_')
                       c = '_';
                   });
    return s;
  }
  inline std::string
  sanitize_identifier (std::string&& s)
  {
    sanitize_identifier (s);
    return std::move (s);
  }
  inline std::string
  sanitize_identifier (const std::string& s)
  {
    return sanitize_identifier (std::string (s));
  }

class project_name
  {
  public:
    explicit
    project_name (const std::string& s): project_name (std::string (s)) {}
    explicit
    project_name (std::string&&);
    project_name () {}
    enum raw_string_type {raw_string};
    project_name (std::string s, raw_string_type): value_ (std::move (s)) {}
    bool
    empty () const noexcept {return value_.empty ();}
    const std::string&
    string () const& noexcept {return value_;}
    std::string
    string () && {std::string r; r.swap (this->value_); return r;}
    std::string
    base (const char* ext = nullptr) const;
    std::string
    extension () const;
    std::string
    variable () const {return sanitize_identifier (value_);}
    int compare (const project_name& n) const {return compare (n.value_);}
    int compare (const std::string& n) const {return compare (n.c_str ());}
    int compare (const char* n) const {return icasecmp (value_, n);}
  private:
    std::string value_;
  };

struct name
  {
    optional<project_name> proj;
    dir_path dir;
    string type;
    string value;
    char pair = '\0';
    name () {}
    name (string v): value (move (v)) {}
    name (dir_path d): dir (move (d)) {}
    name (string t, string v): type (move (t)), value (move (v)) {}
    name (dir_path d, string v): dir (move (d)), value (move (v)) {}
    name (dir_path d, string t, string v)
        : dir (move (d)), type (move (t)), value (move (v)) {}
    name (string p, dir_path d, string t, string v)
        : proj (project_name (move (p))), dir (move (d)), type (move (t)),
          value (move (v)) {}
    name (optional<project_name> p, dir_path d, string t, string v)
        : proj (move (p)), dir (move (d)), type (move (t)), value (move (v)) {}
    bool
    qualified () const {return proj.has_value ();}
    bool
    unqualified () const {return !qualified ();}
    bool
    typed () const {return !type.empty ();}
    bool
    untyped () const {return type.empty ();}
    bool
    empty () const {return dir.empty () && value.empty ();}
    bool
    simple (bool ignore_qual = false) const
    {
      return (ignore_qual || unqualified ()) && untyped () && dir.empty ();
    }
    bool
    directory (bool ignore_qual = false) const
    {
      return (ignore_qual || unqualified ()) &&
        untyped () && !dir.empty () && value.empty ();
    }
    bool
    file (bool ignore_qual = false) const
    {
      return (ignore_qual || unqualified ()) && untyped () && !value.empty ();
    }
    bool
    absolute () const
    {
      return !dir.empty () && dir.absolute ();
    }
    bool
    relative () const
    {
      return dir.empty () || dir.relative ();
    }
    int
    compare (const name&) const;
  };
  extern const name empty_name;
  inline bool
  operator== (const name& x, const name& y) {return x.compare (y) == 0;}
  inline bool
  operator!= (const name& x, const name& y) {return !(x == y);}
  inline bool
  operator< (const name& x, const name& y) {return x.compare (y) < 0;}
  string
  to_string (const name&);
  template <typename T>
  inline void
  to_checksum (T& cs, const name& n)
  {
    if (n.proj)
      cs.append (n.proj->string ());
    cs.append (n.dir.string ());
    cs.append (n.type);
    cs.append (n.value);
    cs.append (n.pair);
  }
  name
  to_name (string);
  ostream&
  to_stream (ostream&,
             const name&,
             bool quote,
             char pair = '\0',
             bool escape = false);
  inline ostream&
  operator<< (ostream& os, const name& n) {return to_stream (os, n, false);}
  using names = small_vector<name, 1>;
  using names_view = vector_view<const name>;
  extern const names empty_names;
  ostream&
  to_stream (ostream&,
             const names_view&,
             bool quote,
             char pair = '\0',
             bool escape = false);
  inline ostream&
  operator<< (ostream& os, const names_view& ns) {
    return to_stream (os, ns, false);}
  inline ostream&
  operator<< (ostream& os, const names& ns) {return os << names_view (ns);}
  using name_pair = pair<name, name>;

enum class variable_visibility: uint8_t
  {
    global,
    project,
    scope,
    target,
    prereq
  };
  inline bool
  operator> (variable_visibility l, variable_visibility r)
  {
    return static_cast<uint8_t> (l) > static_cast<uint8_t> (r);
  }
  inline bool
  operator>= (variable_visibility l, variable_visibility r)
  {
    return static_cast<uint8_t> (l) >= static_cast<uint8_t> (r);
  }
  inline bool
  operator< (variable_visibility l, variable_visibility r)
  {
    return r > l;
  }
  inline bool
  operator<= (variable_visibility l, variable_visibility r)
  {
    return r >= l;
  }
  string
  to_string (variable_visibility);
  inline ostream&
  operator<< (ostream& o, variable_visibility v)
  {
    return o << to_string (v);
  }

class value;
  struct variable;
  struct value_type
  {
    const char* name;
    const size_t size;
    const value_type* base_type;
    template <typename T> const value_type* is_a () const;
    const value_type* element_type;
    void (*const dtor) (value&);
    void (*const copy_ctor) (value&, const value&, bool move);
    void (*const copy_assign) (value&, const value&, bool move);
    void (*const assign) (value&, names&&, const variable*);
    void (*const append) (value&, names&&, const variable*);
    void (*const prepend) (value&, names&&, const variable*);
    names_view (*const reverse) (const value&, names& storage);
    const void* (*const cast) (const value&, const value_type*);
    int (*const compare) (const value&, const value&);
    bool (*const empty) (const value&);
  };

struct variable
  {
    string name;
    const variable* aliases;
    const value_type* type;
    unique_ptr<const variable> overrides;
    variable_visibility visibility;
    bool
    alias (const variable& var) const
    {
      const variable* v (aliases);
      for (; v != &var && v != this; v = v->aliases) ;
      return v == &var;
    }
    size_t
    override (const char* k = nullptr) const
    {
      size_t p (name.rfind ('.'));
      if (p != string::npos)
      {
        auto cmp = [this, p] (const char* k)
        {
          return name.compare (p + 1, string::npos, k) == 0;
        };
        if (k != nullptr
            ? (cmp (k))
            : (cmp ("__override") || cmp ("__prefix") || cmp ("__suffix")))
        {
          p = name.rfind ('.', p - 1);
         (static_cast <bool> (
         p != string::npos && p != 0
	     ) ? void (0) : void (0) )
                                             ;
          return p;
        }
      }
      return 0;
    }
  };

class value
  {
  public:
    relaxed_atomic<const value_type*> type;
    bool null;
    uint16_t extra;
    explicit operator bool () const {return !null;}
    bool operator== (nullptr_t) const {return null;}
    bool operator!= (nullptr_t) const {return !null;}
    bool
    empty () const;
  public:
    ~value () {*this = nullptr;}
    explicit
    value (nullptr_t = nullptr): type (nullptr), null (true), extra (0) {}
    explicit
    value (const value_type* t): type (t), null (true), extra (0) {}
    explicit
    value (names);
    explicit
    value (optional<names>);
    template <typename T>
    explicit
    value (T);
    template <typename T>
    explicit
    value (optional<T>);
    value&
    operator= (nullptr_t) {if (!null) reset (); return *this;}
    value (value&&);
    explicit value (const value&);
    value& operator= (value&&);
    value& operator= (const value&);
    value& operator= (reference_wrapper<value>);
    value& operator= (reference_wrapper<const value>);
  public:
    template <typename T> value& operator= (T);
    template <typename T> value& operator+= (T);
    value& operator= (names);
    value& operator+= (names);
    template <typename T> value& operator= (T* v) {
      return v != nullptr ? *this = *v : *this = nullptr;}
    template <typename T> value& operator+= (T* v) {
      return v != nullptr ? *this += *v : *this;}
    value& operator= (const char* v) {return *this = string (v);}
    value& operator+= (const char* v) {return *this += string (v);}
    void assign (names&&, const variable*);
    void assign (name&&, const variable*);
    void append (names&&, const variable*);
    void prepend (names&&, const variable*);
  public:
    template <typename T> T& as () & {return reinterpret_cast<T&> (data_);}
    template <typename T> T&& as () && {return move (as<T> ());}
    template <typename T> const T& as () const& {
      return reinterpret_cast<const T&> (data_);}
  public:
    static constexpr size_t size_ = sizeof (name_pair);
    std::aligned_storage<size_>::type data_;
    static_assert (sizeof (names) <= size_, "insufficient space");
  private:
    void
    reset ();
  };

void f()
{
    struct expr
    {
      value value_;
      optional<string> func;
      names arg;
    };
    small_vector<expr, 1> exprs;
    expr e;
    exprs.push_back ( e );
}