path: root/butl/path

// file      : butl/path -*- C++ -*-
// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
// license   : MIT; see accompanying LICENSE file

#ifndef BUTL_PATH
#define BUTL_PATH

#include <string>
#include <cstddef>    // ptrdiff_t
#include <utility>    // move()
#include <iterator>
#include <exception>
#include <functional> // hash

namespace butl
{
  template <typename C>
  struct path_traits
  {
    typedef std::basic_string<C> string_type;
    typedef typename string_type::size_type size_type;

    // Canonical directory and path seperators.
    //
#ifdef _WIN32
    static C const directory_separator = '\\';
    static C const path_separator = ';';
#else
    static C const directory_separator = '/';
    static C const path_separator = ':';
#endif

    // Directory separator tests. On some platforms there
    // could be multiple seperators. For example, on Windows
    // we check for both '/' and '\'.
    //
    static bool
    is_separator (C c)
    {
#ifdef _WIN32
      return c == '\\' || c == '/';
#else
      return c == '/';
#endif
    }

    static size_type
    find_separator (string_type const& s, size_type pos = 0)
    {
      for (size_type n (s.size ()); pos < n; ++pos)
      {
        if (is_separator (s[pos]))
          return pos;
      }

      return string_type::npos;
    }

    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++;

      for (; pos > 0; --pos)
      {
        if (is_separator (s[pos - 1]))
          return pos - 1;
      }

      return string_type::npos;
    }

    // Return the position of '.' or npos if there is no extension.
    //
    static size_type
    find_extension (string_type const& s)
    {
      size_type i (s.size ());

      for (; i > 0; --i)
      {
        C c (s[i - 1]);

        if (c == '.')
          break;

        if (is_separator (c))
        {
          i = 0;
          break;
        }
      }

      // Weed out paths like ".txt" (and "/.txt") and "txt.".
      //
      if (i > 1 && !is_separator (s[i - 2]) && i != s.size ())
        return i - 1;
      else
        return string_type::npos;
    }

    static int
    compare (string_type const& l, string_type const& r)
    {
      size_type ln (l.size ()), rn (r.size ()), n (ln < rn ? ln : rn);
      for (size_type i (0); i != n; ++i)
      {
#ifdef _WIN32
        C lc (tolower (l[i])), rc (tolower (r[i]));
#else
        C lc (l[i]), rc (r[i]);
#endif
        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);
    }

    // Get/set current working directory. Throw std::system_error
    // to report the underlying OS errors.
    //
    static string_type
    current ();

    static void
    current (string_type const&);

  private:
#ifdef _WIN32
    static C
    tolower (C);
#endif
  };

  template <typename C>
  class invalid_basic_path;

  template <typename C, typename K>
  class basic_path;

  // Cast from one path kind to another without any checking or
  // processing.
  //
  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 C>
  class path_data;

  template <typename C>
  struct dir_path_kind;

  template <typename C>
  struct any_path_kind
  {
    typedef path_data<C> base_type;
    typedef basic_path<C, dir_path_kind<C>> dir_type;
  };

  template <typename C>
  struct dir_path_kind
  {
    typedef basic_path<C, any_path_kind<C>> base_type;
    typedef basic_path<C, dir_path_kind<C>> dir_type;
  };

  typedef basic_path<char, any_path_kind<char>> path;
  typedef basic_path<char, dir_path_kind<char>> dir_path;
  typedef invalid_basic_path<char> invalid_path;

  typedef basic_path<wchar_t, any_path_kind<wchar_t>> wpath;
  typedef basic_path<wchar_t, dir_path_kind<wchar_t>> dir_wpath;
  typedef invalid_basic_path<wchar_t> invalid_wpath;

  //
  //
  class invalid_path_base: std::exception
  {
  public:
    virtual char const*
    what () const throw ();
  };

  template <typename C>
  class invalid_basic_path: public invalid_path_base
  {
  public:
    typedef std::basic_string<C> string_type;

    invalid_basic_path (C const* p): path_ (p) {}
    invalid_basic_path (string_type const& p): path_ (p) {}
    ~invalid_basic_path () throw () {}

    string_type const&
    path () const
    {
      return path_;
    }

  private:
    string_type path_;
  };

  template <typename C>
  class path_data
  {
  public:
    typedef std::basic_string<C> string_type;

    path_data () = default;

    explicit
    path_data (string_type s): path_ (std::move (s)) {}

  protected:
    string_type path_;
  };

  template <typename C, typename K>
  class basic_path: public K::base_type
  {
  public:
    typedef std::basic_string<C> string_type;
    typedef typename string_type::size_type size_type;

    typedef typename K::base_type base_type;
    typedef typename K::dir_type dir_type;

    typedef path_traits<C> traits;

    struct iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;

    // Construct special empty path. Note that we have to provide our
    // own implementation rather than using '=default' to make clang
    // allow default-initialized const instances of this type.
    //
    basic_path () {};

    explicit
    basic_path (C const* s): base_type (s) {init ();}

    basic_path (C const* s, size_type n)
        : base_type (string_type (s, n)) {init ();}

    explicit
    basic_path (string_type s): base_type (std::move (s)) {init ();}

    basic_path (const string_type& s, size_type n)
        : base_type (string_type (s, 0, n)) {init ();}

    basic_path (const string_type& s, size_type p, size_type n)
        : base_type (string_type (s, p, n)) {init ();}

    // Create a path as a sub-path identified by the [begin, end)
    // range of components.
    //
    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->path_.swap (p.path_);
    }

    void
    clear ()
    {
      this->path_.clear ();
    }

    // Get/set current working directory. Throw std::system_error
    // to report the underlying OS errors.
    //
    static dir_type
    current () {return dir_type (traits::current ());}

    static void
    current (basic_path const&);

  public:
    bool
    empty () const
    {
      return this->path_.empty ();
    }

    // Return true if this path doesn't have any directories. Note
    // that "/foo" is not a simple path (it is "foo" in root directory)
    // while "/" is (it is the root directory).
    //
    bool
    simple () const;

    bool
    absolute () const;

    bool
    relative () const
    {
      return !absolute ();
    }

    bool
    root () const;

    // Return true if *this is a sub-path of the specified path (i.e.,
    // the specified path is a prefix). Expects both paths to be
    // normalized. Note that this function returns true if the paths
    // are equal. Empty path is considered a prefix of any path.
    //
    bool
    sub (const basic_path&) const;

    // Return true if *this is a super-path of the specified path (i.e.,
    // the specified path is a suffix). Expects both paths to be
    // normalized. Note that this function returns true if the paths
    // are equal. Empty path is considered a suffix of any path.
    //
    bool
    sup (const basic_path&) const;

  public:
    // Return the path without the directory part.
    //
    basic_path
    leaf () const;

    // Return the path without the specified directory part. Throws
    // invalid_path if the directory is not a prefix of *this. Expects
    // both paths to be normalized.
    //
    basic_path
    leaf (basic_path const&) const;

    // Return the directory part of the path or empty path if
    // there is no directory.
    //
    dir_type
    directory () const;

    // Return the directory part of the path without the specified
    // leaf part. Throws invalid_path if the leaf is not a suffix of
    // *this. Expects both paths to be normalized.
    //
    dir_type
    directory (basic_path const&) const;

    // Return the root directory of the path or empty path if
    // the directory is not absolute.
    //
    dir_type
    root_directory () const;

    // Return the path without the extension, if any.
    //
    basic_path
    base () const;

    // Return the extension or NULL if not present. If not NULL, then
    // the result points to the character past the dot but it is legal
    // to decrement it once to obtain the value with the dot.
    //
    const C*
    extension () const;

    // Return a path relative to the specified path that is equivalent
    // to *this. Throws invalid_path if a relative path cannot be derived
    // (e.g., paths are on different drives on Windows).
    //
    basic_path
    relative (basic_path) const;

    // Iteration over path components.
    //
  public:
    struct iterator
    {
      typedef string_type value_type;
      typedef string_type* pointer;
      typedef string_type reference;
      typedef std::ptrdiff_t difference_type;
      typedef std::bidirectional_iterator_tag iterator_category;

      typedef typename string_type::size_type size_type;

      iterator (): p_ (nullptr) {}
      iterator (const string_type& p, size_type b, size_type e)
          : p_ (&p), b_ (b), e_ (e) {}

      iterator&
      operator++ ()
      {
        b_ = e_;

        if (b_ != string_type::npos)
          e_ = traits::find_separator (*p_, ++b_);

        return *this;
      }

      iterator&
      operator-- ()
      {
        e_ = b_;

        b_ = e_ == string_type::npos // Last component?
          ? traits::rfind_separator (*p_)
          : (--e_ == 0 // First empty component?
             ? string_type::npos
             : traits::rfind_separator (*p_, e_ - 1));

        b_ = b_ == string_type::npos // First component?
          ? 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_, b_, (e_ != string_type::npos ? e_ - b_ : e_));
      }

      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;

      // b != npos && e == npos - last component
      // b == npos && e == npos - one past last component (end)
      //
      const string_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:
    // Normalize the path. This includes collapsing the '.' and '..'
    // directories if possible, collapsing multiple directory
    // separators, and converting all directory separators to the
    // canonical form. Returns *this.
    //
    basic_path&
    normalize ();

    // Make the path absolute using the current directory unless
    // it is already absolute.
    //
    basic_path&
    complete ();

  public:
    basic_path&
    operator/= (basic_path const&);

    basic_path
    operator+ (string_type const& s) const
    {
      return basic_path (this->path_ + s);
    }

    basic_path
    operator+ (C c) const
    {
      return basic_path (this->path_ + c);
    }

    basic_path&
    operator+= (string_type const& s)
    {
      this->path_ += s;
      return *this;
    }

    basic_path&
    operator+= (C c)
    {
      this->path_ += c;
      return *this;
    }

    // Note that comparison is case-insensitive if the filesystem is
    // not case-sensitive (e.g., Windows).
    //
    bool
    operator== (basic_path const& x) const
    {
      return traits::compare (this->path_, x.path_) == 0;
    }

    bool
    operator!= (basic_path const& x) const
    {
      return !(*this == x);
    }

    bool
    operator< (basic_path const& x) const
    {
      return traits::compare (this->path_, x.path_) < 0;
    }

  public:
    const string_type&
    string () const& {return this->path_;}

    // Moves the underlying path string out of the path object. The
    // path object becomes empty. Usage: std::move (p).string ().
    //
    string_type
    string () && {string_type r; r.swap (this->path_); return r;}

    // If possible, return a POSIX representation of the path. For example,
    // for a Windows path in the form foo\bar this function will return
    // foo/bar. If it is not possible to create a POSIX representation for
    // this path (e.g., c:\foo), this function will throw the invalid_path
    // exception.
    //
    string_type
    posix_string () const;

  private:
    template <class P, class C1, class K1>
    friend P butl::path_cast (const basic_path<C1, K1>&);

    template <class P, class C1, class K1>
    friend P butl::path_cast (basic_path<C1, K1>&&);

    basic_path (string_type s, bool i): base_type (std::move (s))
    {
      if (i)
        init ();
    }

    void
    init ();
  };

  template <typename C, typename K>
  inline basic_path<C, K>
  operator/ (basic_path<C, K> const& x, basic_path<C, K> const& y)
  {
    basic_path<C, K> r (x);
    r /= y;
    return r;
  }

  // Additional operators for certain path kind combinations.
  //
  template <typename C>
  inline basic_path<C, any_path_kind<C>>
  operator/ (basic_path<C, dir_path_kind<C>> const& x,
             basic_path<C, any_path_kind<C>> const& y)
  {
    basic_path<C, any_path_kind<C>> r (x);
    r /= y;
    return r;
  }

  // For operator<< (ostream) see the path-io header.
}

namespace std
{
  template <typename C, typename K>
  struct hash<butl::basic_path<C, K>>: hash<basic_string<C>>
  {
    size_t
    operator() (const butl::basic_path<C, K>& p) const noexcept
    {
      return hash<basic_string<C>>::operator() (p.string ());
    }
  };
}

#include <butl/path.ixx>
#include <butl/path.txx>

#endif // BUTL_PATH