cannam@147: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
cannam@147: // Licensed under the MIT License:
cannam@147: //
cannam@147: // Permission is hereby granted, free of charge, to any person obtaining a copy
cannam@147: // of this software and associated documentation files (the "Software"), to deal
cannam@147: // in the Software without restriction, including without limitation the rights
cannam@147: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
cannam@147: // copies of the Software, and to permit persons to whom the Software is
cannam@147: // furnished to do so, subject to the following conditions:
cannam@147: //
cannam@147: // The above copyright notice and this permission notice shall be included in
cannam@147: // all copies or substantial portions of the Software.
cannam@147: //
cannam@147: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
cannam@147: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
cannam@147: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
cannam@147: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
cannam@147: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
cannam@147: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
cannam@147: // THE SOFTWARE.
cannam@147: 
cannam@147: // This file contains parsers useful for character stream inputs, including parsers to parse
cannam@147: // common kinds of tokens like identifiers, numbers, and quoted strings.
cannam@147: 
cannam@147: #ifndef KJ_PARSE_CHAR_H_
cannam@147: #define KJ_PARSE_CHAR_H_
cannam@147: 
cannam@147: #if defined(__GNUC__) && !KJ_HEADER_WARNINGS
cannam@147: #pragma GCC system_header
cannam@147: #endif
cannam@147: 
cannam@147: #include "common.h"
cannam@147: #include "../string.h"
cannam@147: #include <inttypes.h>
cannam@147: 
cannam@147: namespace kj {
cannam@147: namespace parse {
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Exact char/string.
cannam@147: 
cannam@147: class ExactString_ {
cannam@147: public:
cannam@147:   constexpr inline ExactString_(const char* str): str(str) {}
cannam@147: 
cannam@147:   template <typename Input>
cannam@147:   Maybe<Tuple<>> operator()(Input& input) const {
cannam@147:     const char* ptr = str;
cannam@147: 
cannam@147:     while (*ptr != '\0') {
cannam@147:       if (input.atEnd() || input.current() != *ptr) return nullptr;
cannam@147:       input.next();
cannam@147:       ++ptr;
cannam@147:     }
cannam@147: 
cannam@147:     return Tuple<>();
cannam@147:   }
cannam@147: 
cannam@147: private:
cannam@147:   const char* str;
cannam@147: };
cannam@147: 
cannam@147: constexpr inline ExactString_ exactString(const char* str) {
cannam@147:   return ExactString_(str);
cannam@147: }
cannam@147: 
cannam@147: template <char c>
cannam@147: constexpr ExactlyConst_<char, c> exactChar() {
cannam@147:   // Returns a parser that matches exactly the character given by the template argument (returning
cannam@147:   // no result).
cannam@147:   return ExactlyConst_<char, c>();
cannam@147: }
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Char ranges / sets
cannam@147: 
cannam@147: class CharGroup_ {
cannam@147: public:
cannam@147:   constexpr inline CharGroup_(): bits{0, 0, 0, 0} {}
cannam@147: 
cannam@147:   constexpr inline CharGroup_ orRange(unsigned char first, unsigned char last) const {
cannam@147:     return CharGroup_(bits[0] | (oneBits(last +   1) & ~oneBits(first      )),
cannam@147:                       bits[1] | (oneBits(last -  63) & ~oneBits(first -  64)),
cannam@147:                       bits[2] | (oneBits(last - 127) & ~oneBits(first - 128)),
cannam@147:                       bits[3] | (oneBits(last - 191) & ~oneBits(first - 192)));
cannam@147:   }
cannam@147: 
cannam@147:   constexpr inline CharGroup_ orAny(const char* chars) const {
cannam@147:     return *chars == 0 ? *this : orChar(*chars).orAny(chars + 1);
cannam@147:   }
cannam@147: 
cannam@147:   constexpr inline CharGroup_ orChar(unsigned char c) const {
cannam@147:     return CharGroup_(bits[0] | bit(c),
cannam@147:                       bits[1] | bit(c - 64),
cannam@147:                       bits[2] | bit(c - 128),
cannam@147:                       bits[3] | bit(c - 256));
cannam@147:   }
cannam@147: 
cannam@147:   constexpr inline CharGroup_ orGroup(CharGroup_ other) const {
cannam@147:     return CharGroup_(bits[0] | other.bits[0],
cannam@147:                       bits[1] | other.bits[1],
cannam@147:                       bits[2] | other.bits[2],
cannam@147:                       bits[3] | other.bits[3]);
cannam@147:   }
cannam@147: 
cannam@147:   constexpr inline CharGroup_ invert() const {
cannam@147:     return CharGroup_(~bits[0], ~bits[1], ~bits[2], ~bits[3]);
cannam@147:   }
cannam@147: 
cannam@147:   constexpr inline bool contains(unsigned char c) const {
cannam@147:     return (bits[c / 64] & (1ll << (c % 64))) != 0;
cannam@147:   }
cannam@147: 
cannam@147:   template <typename Input>
cannam@147:   Maybe<char> operator()(Input& input) const {
cannam@147:     if (input.atEnd()) return nullptr;
cannam@147:     unsigned char c = input.current();
cannam@147:     if (contains(c)) {
cannam@147:       input.next();
cannam@147:       return c;
cannam@147:     } else {
cannam@147:       return nullptr;
cannam@147:     }
cannam@147:   }
cannam@147: 
cannam@147: private:
cannam@147:   typedef unsigned long long Bits64;
cannam@147: 
cannam@147:   constexpr inline CharGroup_(Bits64 a, Bits64 b, Bits64 c, Bits64 d): bits{a, b, c, d} {}
cannam@147:   Bits64 bits[4];
cannam@147: 
cannam@147:   static constexpr inline Bits64 oneBits(int count) {
cannam@147:     return count <= 0 ? 0ll : count >= 64 ? -1ll : ((1ll << count) - 1);
cannam@147:   }
cannam@147:   static constexpr inline Bits64 bit(int index) {
cannam@147:     return index < 0 ? 0 : index >= 64 ? 0 : (1ll << index);
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: constexpr inline CharGroup_ charRange(char first, char last) {
cannam@147:   // Create a parser which accepts any character in the range from `first` to `last`, inclusive.
cannam@147:   // For example: `charRange('a', 'z')` matches all lower-case letters.  The parser's result is the
cannam@147:   // character matched.
cannam@147:   //
cannam@147:   // The returned object has methods which can be used to match more characters.  The following
cannam@147:   // produces a parser which accepts any letter as well as '_', '+', '-', and '.'.
cannam@147:   //
cannam@147:   //     charRange('a', 'z').orRange('A', 'Z').orChar('_').orAny("+-.")
cannam@147:   //
cannam@147:   // You can also use `.invert()` to match the opposite set of characters.
cannam@147: 
cannam@147:   return CharGroup_().orRange(first, last);
cannam@147: }
cannam@147: 
cannam@147: #if _MSC_VER
cannam@147: #define anyOfChars(chars) CharGroup_().orAny(chars)
cannam@147: // TODO(msvc): MSVC ICEs on the proper definition of `anyOfChars()`, which in turn prevents us from
cannam@147: //   building the compiler or schema parser. We don't know why this happens, but Harris found that
cannam@147: //   this horrible, horrible hack makes things work. This is awful, but it's better than nothing.
cannam@147: //   Hopefully, MSVC will get fixed soon and we'll be able to remove this.
cannam@147: #else
cannam@147: constexpr inline CharGroup_ anyOfChars(const char* chars) {
cannam@147:   // Returns a parser that accepts any of the characters in the given string (which should usually
cannam@147:   // be a literal).  The returned parser is of the same type as returned by `charRange()` -- see
cannam@147:   // that function for more info.
cannam@147: 
cannam@147:   return CharGroup_().orAny(chars);
cannam@147: }
cannam@147: #endif
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: 
cannam@147: namespace _ {  // private
cannam@147: 
cannam@147: struct ArrayToString {
cannam@147:   inline String operator()(const Array<char>& arr) const {
cannam@147:     return heapString(arr);
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: }  // namespace _ (private)
cannam@147: 
cannam@147: template <typename SubParser>
cannam@147: constexpr inline auto charsToString(SubParser&& subParser)
cannam@147:     -> decltype(transform(kj::fwd<SubParser>(subParser), _::ArrayToString())) {
cannam@147:   // Wraps a parser that returns Array<char> such that it returns String instead.
cannam@147:   return parse::transform(kj::fwd<SubParser>(subParser), _::ArrayToString());
cannam@147: }
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Basic character classes.
cannam@147: 
cannam@147: constexpr auto alpha = charRange('a', 'z').orRange('A', 'Z');
cannam@147: constexpr auto digit = charRange('0', '9');
cannam@147: constexpr auto alphaNumeric = alpha.orGroup(digit);
cannam@147: constexpr auto nameStart = alpha.orChar('_');
cannam@147: constexpr auto nameChar = alphaNumeric.orChar('_');
cannam@147: constexpr auto hexDigit = charRange('0', '9').orRange('a', 'f').orRange('A', 'F');
cannam@147: constexpr auto octDigit = charRange('0', '7');
cannam@147: constexpr auto whitespaceChar = anyOfChars(" \f\n\r\t\v");
cannam@147: constexpr auto controlChar = charRange(0, 0x1f).invert().orGroup(whitespaceChar).invert();
cannam@147: 
cannam@147: constexpr auto whitespace = many(anyOfChars(" \f\n\r\t\v"));
cannam@147: 
cannam@147: constexpr auto discardWhitespace = discard(many(discard(anyOfChars(" \f\n\r\t\v"))));
cannam@147: // Like discard(whitespace) but avoids some memory allocation.
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Identifiers
cannam@147: 
cannam@147: namespace _ { // private
cannam@147: 
cannam@147: struct IdentifierToString {
cannam@147:   inline String operator()(char first, const Array<char>& rest) const {
cannam@147:     String result = heapString(rest.size() + 1);
cannam@147:     result[0] = first;
cannam@147:     memcpy(result.begin() + 1, rest.begin(), rest.size());
cannam@147:     return result;
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: }  // namespace _ (private)
cannam@147: 
cannam@147: constexpr auto identifier = transform(sequence(nameStart, many(nameChar)), _::IdentifierToString());
cannam@147: // Parses an identifier (e.g. a C variable name).
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Integers
cannam@147: 
cannam@147: namespace _ {  // private
cannam@147: 
cannam@147: inline char parseDigit(char c) {
cannam@147:   if (c < 'A') return c - '0';
cannam@147:   if (c < 'a') return c - 'A' + 10;
cannam@147:   return c - 'a' + 10;
cannam@147: }
cannam@147: 
cannam@147: template <uint base>
cannam@147: struct ParseInteger {
cannam@147:   inline uint64_t operator()(const Array<char>& digits) const {
cannam@147:     return operator()('0', digits);
cannam@147:   }
cannam@147:   uint64_t operator()(char first, const Array<char>& digits) const {
cannam@147:     uint64_t result = parseDigit(first);
cannam@147:     for (char digit: digits) {
cannam@147:       result = result * base + parseDigit(digit);
cannam@147:     }
cannam@147:     return result;
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: 
cannam@147: }  // namespace _ (private)
cannam@147: 
cannam@147: constexpr auto integer = sequence(
cannam@147:     oneOf(
cannam@147:       transform(sequence(exactChar<'0'>(), exactChar<'x'>(), oneOrMore(hexDigit)), _::ParseInteger<16>()),
cannam@147:       transform(sequence(exactChar<'0'>(), many(octDigit)), _::ParseInteger<8>()),
cannam@147:       transform(sequence(charRange('1', '9'), many(digit)), _::ParseInteger<10>())),
cannam@147:     notLookingAt(alpha.orAny("_.")));
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Numbers (i.e. floats)
cannam@147: 
cannam@147: namespace _ {  // private
cannam@147: 
cannam@147: struct ParseFloat {
cannam@147:   double operator()(const Array<char>& digits,
cannam@147:                     const Maybe<Array<char>>& fraction,
cannam@147:                     const Maybe<Tuple<Maybe<char>, Array<char>>>& exponent) const;
cannam@147: };
cannam@147: 
cannam@147: }  // namespace _ (private)
cannam@147: 
cannam@147: constexpr auto number = transform(
cannam@147:     sequence(
cannam@147:         oneOrMore(digit),
cannam@147:         optional(sequence(exactChar<'.'>(), many(digit))),
cannam@147:         optional(sequence(discard(anyOfChars("eE")), optional(anyOfChars("+-")), many(digit))),
cannam@147:         notLookingAt(alpha.orAny("_."))),
cannam@147:     _::ParseFloat());
cannam@147: 
cannam@147: // =======================================================================================
cannam@147: // Quoted strings
cannam@147: 
cannam@147: namespace _ {  // private
cannam@147: 
cannam@147: struct InterpretEscape {
cannam@147:   char operator()(char c) const {
cannam@147:     switch (c) {
cannam@147:       case 'a': return '\a';
cannam@147:       case 'b': return '\b';
cannam@147:       case 'f': return '\f';
cannam@147:       case 'n': return '\n';
cannam@147:       case 'r': return '\r';
cannam@147:       case 't': return '\t';
cannam@147:       case 'v': return '\v';
cannam@147:       default: return c;
cannam@147:     }
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: struct ParseHexEscape {
cannam@147:   inline char operator()(char first, char second) const {
cannam@147:     return (parseDigit(first) << 4) | parseDigit(second);
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: struct ParseHexByte {
cannam@147:   inline byte operator()(char first, char second) const {
cannam@147:     return (parseDigit(first) << 4) | parseDigit(second);
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: struct ParseOctEscape {
cannam@147:   inline char operator()(char first, Maybe<char> second, Maybe<char> third) const {
cannam@147:     char result = first - '0';
cannam@147:     KJ_IF_MAYBE(digit1, second) {
cannam@147:       result = (result << 3) | (*digit1 - '0');
cannam@147:       KJ_IF_MAYBE(digit2, third) {
cannam@147:         result = (result << 3) | (*digit2 - '0');
cannam@147:       }
cannam@147:     }
cannam@147:     return result;
cannam@147:   }
cannam@147: };
cannam@147: 
cannam@147: }  // namespace _ (private)
cannam@147: 
cannam@147: constexpr auto escapeSequence =
cannam@147:     sequence(exactChar<'\\'>(), oneOf(
cannam@147:         transform(anyOfChars("abfnrtv'\"\\\?"), _::InterpretEscape()),
cannam@147:         transform(sequence(exactChar<'x'>(), hexDigit, hexDigit), _::ParseHexEscape()),
cannam@147:         transform(sequence(octDigit, optional(octDigit), optional(octDigit)),
cannam@147:                   _::ParseOctEscape())));
cannam@147: // A parser that parses a C-string-style escape sequence (starting with a backslash).  Returns
cannam@147: // a char.
cannam@147: 
cannam@147: constexpr auto doubleQuotedString = charsToString(sequence(
cannam@147:     exactChar<'\"'>(),
cannam@147:     many(oneOf(anyOfChars("\\\n\"").invert(), escapeSequence)),
cannam@147:     exactChar<'\"'>()));
cannam@147: // Parses a C-style double-quoted string.
cannam@147: 
cannam@147: constexpr auto singleQuotedString = charsToString(sequence(
cannam@147:     exactChar<'\''>(),
cannam@147:     many(oneOf(anyOfChars("\\\n\'").invert(), escapeSequence)),
cannam@147:     exactChar<'\''>()));
cannam@147: // Parses a C-style single-quoted string.
cannam@147: 
cannam@147: constexpr auto doubleQuotedHexBinary = sequence(
cannam@147:     exactChar<'0'>(), exactChar<'x'>(), exactChar<'\"'>(),
cannam@147:     oneOrMore(transform(sequence(discardWhitespace, hexDigit, hexDigit), _::ParseHexByte())),
cannam@147:     discardWhitespace,
cannam@147:     exactChar<'\"'>());
cannam@147: // Parses a double-quoted hex binary literal. Returns Array<byte>.
cannam@147: 
cannam@147: }  // namespace parse
cannam@147: }  // namespace kj
cannam@147: 
cannam@147: #endif  // KJ_PARSE_CHAR_H_