path: root/libbuild2/script/regex.hxx

// file      : libbuild2/script/regex.hxx -*- C++ -*-
// license   : MIT; see accompanying LICENSE file

#ifndef LIBBUILD2_SCRIPT_REGEX_HXX
#define LIBBUILD2_SCRIPT_REGEX_HXX

#include <list>
#include <regex>
#include <locale>
#include <string>        // basic_string
#include <type_traits>   // make_unsigned, enable_if, is_*
#include <unordered_set>

#include <libbuild2/types.hxx>
#include <libbuild2/utility.hxx>

namespace build2
{
  namespace script
  {
    namespace regex
    {
      using char_string = std::basic_string<char>;

      enum class char_flags: uint16_t
      {
        icase = 0x1, // Case-insensitive match.
          idot  = 0x2, // Invert '.' escaping.

          none = 0
          };

      // Restricts valid standard flags to just {icase}, extends with custom
      // flags {idot}.
      //
      class char_regex: public std::basic_regex<char>
      {
      public:
        using base_type = std::basic_regex<char>;

        char_regex (const char_string&, char_flags = char_flags::none);
      };

      // Newlines are line separators and are not part of the line:
      //
      // line<newline>line<newline>
      //
      // Specifically, this means that a customary trailing newline creates a
      // trailing blank line.
      //
      // All characters can inter-compare (though there cannot be regex
      // characters in the output, only in line_regex).
      //
      // Note that we assume that line_regex and the input to regex_match()
      // use the same pool.
      //
      struct line_pool
      {
        // Note that we assume the pool can be moved without invalidating
        // pointers to any already pooled entities.
        //
        std::unordered_set<char_string> strings;
        std::list<char_regex> regexes;
      };

      enum class line_type
      {
        special,
          literal,
          regex
          };

      struct line_char
      {
        // Steal last two bits from the pointer to store the type.
        //
      private:
        std::uintptr_t data_;

      public:
        line_type
        type () const {return static_cast<line_type> (data_ & 0x3);}

        int
        special () const
        {
          // Stored as (shifted) int16_t. Perform steps reversed to those
          // that are described in the comment for the corresponding ctor.
          // Note that the intermediate cast to uint16_t is required to
          // portably preserve the -1 special character.
          //
          return static_cast<int16_t> (static_cast<uint16_t> (data_ >> 2));
        }

        const char_string*
        literal () const
        {
          // Note that 2 rightmost bits are used for packaging line_char
          // type. Read the comment for the corresponding ctor for details.
          //
          return reinterpret_cast<const char_string*> (
            data_ & ~std::uintptr_t (0x3));
        }

        const char_regex*
        regex () const
        {
          // Note that 2 rightmost bits are used for packaging line_char
          // type. Read the comment for the corresponding ctor for details.
          //
          return reinterpret_cast<const char_regex*> (
            data_ & ~std::uintptr_t (0x3));
        }

        static const line_char nul;
        static const line_char eof;

        // Note: creates an uninitialized value.
        //
        line_char () = default;

        // Create a special character. The argument value must be one of the
        // following ones:
        //
        // 0 (nul character)
        // -1 (EOF)
        // [()|.*+?{}\0123456789,=!] (excluding [])
        //
        // Note that the constructor is implicit to allow basic_regex to
        // implicitly construct line_chars from special char literals (in
        // particular libstdc++ appends them to an internal line_string).
        //
        // Also note that we extend the valid characters set (see above) with
        // 'p', 'n' (used by libstdc++ for positive/negative look-ahead
        // tokens representation), and '\n', '\r', u'\u2028', u'\u2029' (used
        // by libstdc++ for newline/newparagraph matching).
        //
        line_char (int);

        // Create a literal character.
        //
        // Don't copy string if already pooled.
        //
        explicit
        line_char (const char_string&, line_pool&);

        explicit
        line_char (char_string&&, line_pool&);

        explicit
        line_char (const char_string* s) // Assume already pooled.
            //
            // Steal two bits from the pointer to package line_char type.
            // Assume (and statically assert) that char_string address is a
            // multiple of four.
            //
            : data_ (reinterpret_cast <std::uintptr_t> (s) |
                     static_cast <std::uintptr_t> (line_type::literal)) {}

        // Create a regex character.
        //
        explicit
        line_char (char_regex, line_pool&);

        explicit
        line_char (const char_regex* r) // Assume already pooled.
            //
            // Steal two bits from the pointer to package line_char type.
            // Assume (and statically assert) that char_regex address is a
            // multiple of four.
            //
            : data_ (reinterpret_cast <std::uintptr_t> (r) |
                     static_cast <std::uintptr_t> (line_type::regex)) {}

        // Provide basic_regex with the ability to use line_char in a context
        // where a char value is expected (e.g., as a function argument).
        //
        // libstdc++ seems to cast special line_chars only (and such a
        // conversion is meanigfull).
        //
        // msvcrt casts line_chars of arbitrary types instead. The only
        // reasonable strategy is to return a value that differs from any
        // other that can be encountered in a regex expression and so will
        // unlikelly be misinterpreted.
        //
        operator char () const
        {
          return type () == line_type::special ? special () : '\a'; // BELL.
        }

        // Return true if the character is a syntax (special) one.
        //
        static bool
        syntax (char);

        // Provide basic_regex (such as from msvcrt) with the ability to
        // explicitly cast line_chars to implementation-specific numeric
        // types (enums, msvcrt's _Uelem, etc).
        //
        template <typename T>
        explicit
        operator T () const
        {
          assert (type () == line_type::special);
          return static_cast<T> (special ());
        }
      };

      // Perform "deep" characters comparison (for example match literal
      // character with a regex character), rather than just compare them
      // literally. At least one argument must be of a type other than regex
      // as there is no operator==() defined to compare regexes. Characters
      // of the literal type must share the same pool (strings are compared
      // by pointers not by values).
      //
      bool
      operator== (const line_char&, const line_char&);

      // Return false if arguments are equal (operator==() returns true).
      // Otherwise if types are different return the value implying that
      // special < literal < regex. If types are special or literal return
      // the result of the respective characters or strings comparison. At
      // least one argument must be of a type other than regex as there is no
      // operator<() defined to compare regexes.
      //
      // While not very natural operation for the class we have, we have to
      // provide some meaningfull semantics for such a comparison as it is
      // required by the char_traits<line_char> specialization. While we
      // could provide it right in that specialization, let's keep it here
      // for basic_regex implementations that potentially can compare
      // line_chars as they compare them with expressions of other types (see
      // below).
      //
      bool
      operator< (const line_char&, const line_char&);

      inline bool
      operator!= (const line_char& l, const line_char& r)
      {
        return !(l == r);
      }

      inline bool
      operator<= (const line_char& l, const line_char& r)
      {
        return l < r || l == r;
      }

      // Provide basic_regex (such as from msvcrt) with the ability to
      // compare line_char to a value of an integral or
      // implementation-specific enum type. In the absense of the following
      // template operators, such a comparisons would be ambigious for
      // integral types (given that there are implicit conversions
      // int->line_char and line_char->char) and impossible for enums.
      //
      // Note that these == and < operators can succeed only for a line_char
      // of the special type. For other types they always return false. That
      // in particular leads to the following case:
      //
      // (lc != c) != (lc < c || c < lc).
      //
      // Note that we can not assert line_char is of the special type as
      // basic_regex (such as from libc++) may need the ability to check if
      // arbitrary line_char belongs to some special characters range (like
      // ['0', '9']).
      //
      template <typename T>
      struct line_char_cmp
        : public std::enable_if<std::is_integral<T>::value ||
      (std::is_enum<T>::value &&
       !std::is_same<T, char_flags>::value)> {};

      template <typename T, typename = typename line_char_cmp<T>::type>
      bool
      operator== (const line_char& l, const T& r)
      {
        return l.type () == line_type::special &&
          static_cast<T> (l.special ()) == r;
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      bool
      operator== (const T& l, const line_char& r)
      {
        return r.type () == line_type::special &&
          static_cast<T> (r.special ()) == l;
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      bool
      operator!= (const line_char& l, const T& r)
      {
        return !(l == r);
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      bool
      operator!= (const T& l, const line_char& r)
      {
        return !(l == r);
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      bool
      operator< (const line_char& l, const T& r)
      {
        return l.type () == line_type::special &&
          static_cast<T> (l.special ()) < r;
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      bool
      operator< (const T& l, const line_char& r)
      {
        return r.type () == line_type::special &&
          l < static_cast<T> (r.special ());
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      inline bool
      operator<= (const line_char& l, const T& r)
      {
        return l < r || l == r;
      }

      template <typename T, typename = typename line_char_cmp<T>::type>
      inline bool
      operator<= (const T& l, const line_char& r)
      {
        return l < r || l == r;
      }

      using line_string = std::basic_string<line_char>;

      // Locale that has ctype<line_char> facet installed. Used in the
      // regex_traits<line_char> specialization (see below).
      //
      class line_char_locale: public std::locale
      {
      public:
        // Create a copy of the global C++ locale.
        //
        line_char_locale ();
      };

      // Initialize the script regex global state. Should be called once
      // prior to creating objects of types from this namespace. Note: not
      // thread-safe.
      //
      void
      init ();
    }
  }
}

// Standard template specializations for line_char that are required for the
// basic_regex<line_char> instantiation.
//
namespace std
{
  template <>
  class char_traits<build2::script::regex::line_char>
  {
  public:
    using char_type  = build2::script::regex::line_char;
    using int_type   = char_type;
    using off_type   = char_traits<char>::off_type;
    using pos_type   = char_traits<char>::pos_type;
    using state_type = char_traits<char>::state_type;

    static void
    assign (char_type& c1, const char_type& c2) {c1 = c2;}

    static char_type*
    assign (char_type*, size_t, char_type);

    // Note that eq() and lt() are not constexpr (as required by C++11)
    // because == and < operators for char_type are not constexpr.
    //
    static bool
    eq (const char_type& l, const char_type& r) {return l == r;}

    static bool
    lt (const char_type& l, const char_type& r) {return l < r;}

    static char_type*
    move (char_type*, const char_type*, size_t);

    static char_type*
    copy (char_type*, const char_type*, size_t);

    static int
    compare (const char_type*, const char_type*, size_t);

    static size_t
    length (const char_type*);

    static const char_type*
    find (const char_type*, size_t, const char_type&);

    static constexpr char_type
    to_char_type (const int_type& c) {return c;}

    static constexpr int_type
    to_int_type (const char_type& c) {return int_type (c);}

    // Note that the following functions are not constexpr (as required by
    // C++11) because their return expressions are not constexpr.
    //
    static bool
    eq_int_type (const int_type& l, const int_type& r) {return l == r;}

    static int_type eof () {return char_type::eof;}

    static int_type
    not_eof (const int_type& c)
    {
      return c != char_type::eof ? c : char_type::nul;
    }
  };

  // ctype<> must be derived from both ctype_base and locale::facet (the later
  // supports ref-counting used by the std::locale implementation internally).
  //
  // msvcrt for some reason also derives ctype_base from locale::facet which
  // produces "already a base-class" warning and effectivelly breaks the
  // reference counting. So we derive from ctype_base only in this case.
  //
  template <>
  class ctype<build2::script::regex::line_char>: public ctype_base
#if !defined(_MSC_VER) || _MSC_VER >= 2000
                                              , public locale::facet
#endif
  {
    // Used by the implementation only.
    //
    using line_type = build2::script::regex::line_type;

  public:
    using char_type = build2::script::regex::line_char;

    static locale::id id;

#if !defined(_MSC_VER) || _MSC_VER >= 2000
    explicit
    ctype (size_t refs = 0): locale::facet (refs) {}
#else
    explicit
    ctype (size_t refs = 0): ctype_base (refs) {}
#endif

    // While unnecessary, let's keep for completeness.
    //
    virtual
    ~ctype () override = default;

    // The C++ standard requires the following functions to call their virtual
    // (protected) do_*() counterparts that provide the real implementations.
    // The only purpose for this indirection is to provide a user with the
    // ability to customize existing (standard) ctype facets. As we do not
    // provide such an ability, for simplicity we will omit the do_*()
    // functions and provide the implementations directly. This should be safe
    // as nobody except us could call those protected functions.
    //
    bool
    is (mask m, char_type c) const
    {
      return m ==
        (c.type () == line_type::special && c.special () >= 0 &&
         build2::digit (static_cast<char> (c.special ()))
         ? digit
         : 0);
    }

    const char_type*
    is (const char_type*, const char_type*, mask*) const;

    const char_type*
    scan_is (mask, const char_type*, const char_type*) const;

    const char_type*
    scan_not (mask, const char_type*, const char_type*) const;

    char_type
    toupper (char_type c) const {return c;}

    const char_type*
    toupper (char_type*, const char_type* e) const {return e;}

    char_type
    tolower (char_type c) const {return c;}

    const char_type*
    tolower (char_type*, const char_type* e) const {return e;}

    char_type
    widen (char c) const {return char_type (c);}

    const char*
    widen (const char*, const char*, char_type*) const;

    char
    narrow (char_type c, char def) const
    {
      return c.type () == line_type::special ? c.special () : def;
    }

    const char_type*
    narrow (const char_type*, const char_type*, char, char*) const;
  };

  // Note: the current application locale must be POSIX. Otherwise the
  // behavior is undefined.
  //
  template <>
  class regex_traits<build2::script::regex::line_char>
  {
  public:
    using char_type       = build2::script::regex::line_char;
    using string_type     = build2::script::regex::line_string;
    using locale_type     = build2::script::regex::line_char_locale;
    using char_class_type = regex_traits<char>::char_class_type;

    // Workaround for msvcrt bugs. For some reason it assumes such a members
    // to be present in a regex_traits specialization.
    //
#if defined(_MSC_VER) && _MSC_VER < 2000
    static const ctype_base::mask _Ch_upper = ctype_base::upper;
    static const ctype_base::mask _Ch_alpha = ctype_base::alpha;

    // Unsigned numeric type. msvcrt normally casts characters to this type
    // for comparing with some numeric values or for calculating an index in
    // some bit array. Luckily that all relates to the character class
    // handling that we don't support.
    //
    using _Uelem = unsigned int;
#endif

    regex_traits () = default; // Unnecessary but let's keep for completeness.

    static size_t
    length (const char_type* p) {return string_type::traits_type::length (p);}

    char_type
    translate (char_type c) const {return c;}

    // Case-insensitive matching is not supported by line_regex. So there is no
    // reason for the function to be called.
    //
    char_type
    translate_nocase (char_type c) const {assert (false); return c;}

    // Return a sort-key - the exact copy of [b, e).
    //
    template <typename I>
    string_type
    transform (I b, I e) const {return string_type (b, e);}

    // Return a case-insensitive sort-key. Case-insensitive matching is not
    // supported by line_regex. So there is no reason for the function to be
    // called.
    //
    template <typename I>
    string_type
    transform_primary (I b, I e) const
    {
      assert (false);
      return string_type (b, e);
    }

    // POSIX regex grammar and collating elements (e.g., [.tilde.]) in
    // particular are not supported. So there is no reason for the function to
    // be called.
    //
    template <typename I>
    string_type
    lookup_collatename (I, I) const {assert (false); return string_type ();}

    // Character classes (e.g., [:lower:]) are not supported. So there is no
    // reason for the function to be called.
    //
    template <typename I>
    char_class_type
    lookup_classname (I, I, bool = false) const
    {
      assert (false);
      return char_class_type ();
    }

    // Return false as we don't support character classes (e.g., [:lower:]).
    //
    bool
    isctype (char_type, char_class_type) const {return false;}

    int
    value (char_type, int) const;

    // Return the locale passed as an argument as we do not expect anything
    // other than POSIX locale, that we also assume to be imbued by default.
    //
    locale_type
    imbue (locale_type l) {return l;}

    locale_type
    getloc () const {return locale_type ();}
  };

  // We assume line_char to be an unsigned type and express that with the
  // following specialization used by basic_regex implementations.
  //
  // libstdc++ defines unsigned CharT type (regex_traits template parameter)
  // to use as an index in some internal cache regardless if the cache is used
  // for this specialization (and the cache is used only if CharT is char).
  //
  template <>
  struct make_unsigned<build2::script::regex::line_char>
  {
    using type = build2::script::regex::line_char;
  };

  // When used with libc++ the linker complains that it can't find
  // __match_any_but_newline<line_char>::__exec() function. The problem is
  // that the function is only specialized for char and wchar_t
  // (LLVM bug #31409). As line_char has no notion of the newline character we
  // specialize the class template to behave as the __match_any<line_char>
  // instantiation does (that luckily has all the functions in place).
  //
#if defined(_LIBCPP_VERSION) && _LIBCPP_VERSION <= 11000
  template <>
  class __match_any_but_newline<build2::script::regex::line_char>
    : public __match_any<build2::script::regex::line_char>
  {
  public:
    using base = __match_any<build2::script::regex::line_char>;
    using base::base;
  };
#endif
}

namespace build2
{
  namespace script
  {
    namespace regex
    {
      class line_regex: public std::basic_regex<line_char>
      {
      public:
        using base_type = std::basic_regex<line_char>;

        using base_type::base_type;

        line_regex () = default;

        // Move string regex together with the pool used to create it.
        //
        line_regex (line_string&& s, line_pool&& p)
            // No move-string ctor for base_type, so emulate it.
            //
            : base_type (s), pool (move (p)) {s.clear ();}

        // Move constuctible/assignable-only type.
        //
        line_regex (line_regex&&) = default;
        line_regex (const line_regex&) = delete;
        line_regex& operator= (line_regex&&) = default;
        line_regex& operator= (const line_regex&) = delete;

      public:
        line_pool pool;
      };
    }
  }
}

#include <libbuild2/script/regex.ixx>

#endif // LIBBUILD2_SCRIPT_REGEX_HXX