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