/proc/self/cwd/parser/internal/lexer.cc

Source
// Copyright 2026 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "parser/internal/lexer.h"

#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <string_view>

#include "absl/base/attributes.h"
#include "absl/base/no_destructor.h"
#include "absl/base/optimization.h"
#include "absl/container/flat_hash_map.h"
#include "absl/functional/function_ref.h"
#include "absl/log/absl_check.h"
#include "absl/strings/ascii.h"
#include "absl/strings/string_view.h"

namespace cel::parser_internal {

namespace {

[[nodiscard]] bool IsIdentTrailing(char32_t c) {
  return c <= 0x7f && (absl::ascii_isdigit(static_cast<char>(c)) ||
                       absl::ascii_isalpha(static_cast<char>(c)) || c == '_');
}

[[nodiscard]] bool IsPlusOrMinus(char32_t c) { return c == '+' || c == '-'; }

[[nodiscard]] const absl::flat_hash_map<std::string_view, TokenType>&
Keywords() {
  static const absl::NoDestructor<
      absl::flat_hash_map<std::string_view, TokenType>>
      kKeywords({
          {"false", TokenType::kFalse},
          {"true", TokenType::kTrue},
          {"null", TokenType::kNull},
          {"in", TokenType::kIn},
          {"as", TokenType::kReservedWord},
          {"break", TokenType::kReservedWord},
          {"const", TokenType::kReservedWord},
          {"continue", TokenType::kReservedWord},
          {"else", TokenType::kReservedWord},
          {"for", TokenType::kReservedWord},
          {"function", TokenType::kReservedWord},
          {"if", TokenType::kReservedWord},
          {"import", TokenType::kReservedWord},
          {"let", TokenType::kReservedWord},
          {"loop", TokenType::kReservedWord},
          {"package", TokenType::kReservedWord},
          {"namespace", TokenType::kReservedWord},
          {"return", TokenType::kReservedWord},
          {"var", TokenType::kReservedWord},
          {"void", TokenType::kReservedWord},
          {"while", TokenType::kReservedWord},
      });
  return *kKeywords;
}

}  // namespace

std::string_view TokenTypeToString(TokenType type) {
  switch (type) {
    case TokenType::kError:
      return "error";
    case TokenType::kEnd:
      return "end";
    case TokenType::kWhitespace:
      return "whitespace";
    case TokenType::kComment:
      return "comment";
    case TokenType::kNull:
      return "null";
    case TokenType::kFalse:
      return "false";
    case TokenType::kTrue:
      return "true";
    case TokenType::kIn:
      return "in";
    case TokenType::kReservedWord:
      return "reserved_word";
    case TokenType::kInt:
      return "int";
    case TokenType::kUint:
      return "uint";
    case TokenType::kFloat:
      return "float";
    case TokenType::kString:
      return "string";
    case TokenType::kBytes:
      return "bytes";
    case TokenType::kIdent:
      return "ident";
    case TokenType::kLeftBracket:
      return "[";
    case TokenType::kRightBracket:
      return "]";
    case TokenType::kLeftBrace:
      return "{";
    case TokenType::kRightBrace:
      return "}";
    case TokenType::kLeftParen:
      return "(";
    case TokenType::kRightParen:
      return ")";
    case TokenType::kDot:
      return ".";
    case TokenType::kComma:
      return ",";
    case TokenType::kMinus:
      return "-";
    case TokenType::kPlus:
      return "+";
    case TokenType::kAsterisk:
      return "*";
    case TokenType::kSlash:
      return "/";
    case TokenType::kPercent:
      return "%";
    case TokenType::kQuestion:
      return "?";
    case TokenType::kColon:
      return ":";
    case TokenType::kExclamation:
      return "!";
    case TokenType::kEqual:
      return "=";
    case TokenType::kEqualEqual:
      return "==";
    case TokenType::kExclamationEqual:
      return "!=";
    case TokenType::kLess:
      return "<";
    case TokenType::kLessEqual:
      return "<=";
    case TokenType::kGreater:
      return ">";
    case TokenType::kGreaterEqual:
      return ">=";
    case TokenType::kLogicalAnd:
      return "&&";
    case TokenType::kLogicalOr:
      return "||";
    default:
      return "<unknown>";
  }
}

Token Lexer::Lex() {
  int32_t start = GetPosition();
  if (ABSL_PREDICT_FALSE(position_ >= content_size_)) {
    return MakeToken(TokenType::kEnd, start, start);
  }
  char32_t c = content_.at(position_);
  switch (c) {
    case '\f':
      ABSL_FALLTHROUGH_INTENDED;
    case '\t':
      ABSL_FALLTHROUGH_INTENDED;
    case '\r':
      ABSL_FALLTHROUGH_INTENDED;
    case '\n':
      ABSL_FALLTHROUGH_INTENDED;
    case ' ': {
      ConsumeWhitespace();
      return MakeToken(TokenType::kWhitespace, start, GetPosition());
    }
    case '.': {
      if (position_ + 1 < content_size_ && content_.at(position_ + 1) <= 0x7f &&
          absl::ascii_isdigit(static_cast<char>(content_.at(position_ + 1)))) {
        return ConsumeNumericLiteral();
      }
      Advance(1);
      return MakeToken(TokenType::kDot, start, GetPosition());
    }
    case ',': {
      Advance(1);
      return MakeToken(TokenType::kComma, start, GetPosition());
    }
    case '!': {
      Advance(1);
      if (Consume('=')) {
        return MakeToken(TokenType::kExclamationEqual, start, GetPosition());
      }
      return MakeToken(TokenType::kExclamation, start, GetPosition());
    }
    case '?': {
      Advance(1);
      return MakeToken(TokenType::kQuestion, start, GetPosition());
    }
    case '(': {
      Advance(1);
      return MakeToken(TokenType::kLeftParen, start, GetPosition());
    }
    case ')': {
      Advance(1);
      return MakeToken(TokenType::kRightParen, start, GetPosition());
    }
    case '{': {
      Advance(1);
      return MakeToken(TokenType::kLeftBrace, start, GetPosition());
    }
    case '}': {
      Advance(1);
      return MakeToken(TokenType::kRightBrace, start, GetPosition());
    }
    case '[': {
      Advance(1);
      return MakeToken(TokenType::kLeftBracket, start, GetPosition());
    }
    case ']': {
      Advance(1);
      return MakeToken(TokenType::kRightBracket, start, GetPosition());
    }
    case '=': {
      Advance(1);
      if (Consume('=')) {
        return MakeToken(TokenType::kEqualEqual, start, GetPosition());
      }
      return MakeToken(TokenType::kEqual, start, GetPosition());
    }
    case '<': {
      Advance(1);
      if (Consume('=')) {
        return MakeToken(TokenType::kLessEqual, start, GetPosition());
      }
      return MakeToken(TokenType::kLess, start, GetPosition());
    }
    case '>': {
      Advance(1);
      if (Consume('=')) {
        return MakeToken(TokenType::kGreaterEqual, start, GetPosition());
      }
      return MakeToken(TokenType::kGreater, start, GetPosition());
    }
    case ':': {
      Advance(1);
      return MakeToken(TokenType::kColon, start, GetPosition());
    }
    case '%': {
      Advance(1);
      return MakeToken(TokenType::kPercent, start, GetPosition());
    }
    case '+': {
      Advance(1);
      return MakeToken(TokenType::kPlus, start, GetPosition());
    }
    case '-': {
      Advance(1);
      return MakeToken(TokenType::kMinus, start, GetPosition());
    }
    case '*': {
      Advance(1);
      return MakeToken(TokenType::kAsterisk, start, GetPosition());
    }
    case '/': {
      Advance(1);
      if (Consume('/')) {
        ConsumeLine();
        return MakeToken(TokenType::kComment, start, GetPosition());
      }
      return MakeToken(TokenType::kSlash, start, GetPosition());
    }
    case '&': {
      Advance(1);
      if (Consume('&')) {
        return MakeToken(TokenType::kLogicalAnd, start, GetPosition());
      }
      return SetError(start, GetPosition(),
                      "unexpected single '&', expected '&&'");
    }
    case '|': {
      Advance(1);
      if (Consume('|')) {
        return MakeToken(TokenType::kLogicalOr, start, GetPosition());
      }
      return SetError(start, GetPosition(),
                      "unexpected single '|', expected '||'");
    }
    case '_': {
      return ConsumeIdent();
    }
    case '`': {
      return ConsumeQuotedIdent();
    }
    case '\'': {
      return ConsumeStringLiteral(start, '\'');
    }
    case '"': {
      return ConsumeStringLiteral(start, '"');
    }
    case 'r':
      ABSL_FALLTHROUGH_INTENDED;
    case 'R':
      ABSL_FALLTHROUGH_INTENDED;
    case 'b':
      ABSL_FALLTHROUGH_INTENDED;
    case 'B': {
      if (auto token = ConsumePrefixedStringLiteral(); token.has_value()) {
        return *token;
      }
      break;
    }
    default:
      break;
  }
  if (c <= 0x7f && absl::ascii_isdigit(static_cast<char>(c))) {
    return ConsumeNumericLiteral();
  }
  if (c <= 0x7f && absl::ascii_isalpha(static_cast<char>(c))) {
    // Root identifiers (the ones starting with a period) are returned as
    // a sequence of kDot and kIdent tokens.
    return ConsumeIdent();
  }
  Advance(1);
  return SetError(start, GetPosition(), "unexpected character");
}

// Consumes characters up to and including the first occurrence of character
// `c`. If `is_raw` is false, backslashes are interpreted as escapes. Returns
// true if `c` was found and consumed; false if end of input or an unescaped
// newline was reached.
bool Lexer::ConsumeUntilAfter(char32_t c, bool is_raw) {
  ABSL_DCHECK_NE(c, '\n');
  ABSL_DCHECK_NE(c, '\r');
  int32_t pos = position_;
  bool escaped = false;
  while (pos < content_size_) {
    char32_t cc = content_.at(pos);
    if (cc == '\n' || cc == '\r') {
      AdvanceProcessingNewLines(pos);
      return false;
    }
    if (!is_raw && cc == '\\') {
      escaped = !escaped;
    } else {
      if (cc == c && (is_raw || !escaped)) {
        AdvanceProcessingNewLines(pos + 1);
        return true;
      }
      escaped = false;
    }
    ++pos;
  }
  AdvanceProcessingNewLines(content_size_);
  return false;
}

// Consumes characters up to and including the first occurrence of substring `s`
// without interpreting backslashes as escapes (`s` must not contain newlines).
// Returns true if `s` was found and consumed; false if end of input was
// reached.
bool Lexer::ConsumeUntilAfterString(std::u32string_view s) {
  ABSL_DCHECK(s.find(U'\n') == std::u32string_view::npos);
  int32_t pos = position_;
  while (pos + static_cast<int32_t>(s.size()) <= content_size_) {
    bool match = true;
    for (size_t i = 0; i < s.size(); ++i) {
      if (content_.at(pos + static_cast<int32_t>(i)) != s[i]) {
        match = false;
        break;
      }
    }
    if (match) {
      AdvanceProcessingNewLines(pos + static_cast<int32_t>(s.size()));
      return true;
    }
    ++pos;
  }
  AdvanceProcessingNewLines(content_size_);
  return false;
}

// Consumes characters up to and including the first occurrence of substring `s`
// where the first character of `s` is not preceded by an odd number of
// backslashes. Returns true if an unescaped `s` was found and consumed; false
// if reached EOF.
bool Lexer::ConsumeUntilAfterUnescapedString(std::u32string_view s) {
  ABSL_DCHECK(s.find(U'\n') == std::u32string_view::npos);
  int32_t pos = position_;
  bool escaped = false;
  while (pos < content_size_) {
    char32_t cc = content_.at(pos);
    if (cc == '\\') {
      escaped = !escaped;
    } else {
      if (!escaped && pos + static_cast<int32_t>(s.size()) <= content_size_) {
        bool match = true;
        for (size_t j = 0; j < s.size(); ++j) {
          if (content_.at(pos + static_cast<int32_t>(j)) != s[j]) {
            match = false;
            break;
          }
        }
        if (match) {
          AdvanceProcessingNewLines(pos + static_cast<int32_t>(s.size()));
          return true;
        }
      }
      escaped = false;
    }
    ++pos;
  }
  AdvanceProcessingNewLines(content_size_);
  return false;
}

bool Lexer::MatchString(std::u32string_view s) const {
  if (position_ + static_cast<int32_t>(s.size()) > content_size_) {
    return false;
  }
  for (size_t i = 0; i < s.size(); ++i) {
    if (content_.at(position_ + static_cast<int32_t>(i)) != s[i]) {
      return false;
    }
  }
  return true;
}

std::optional<char32_t> Lexer::MatchIf(
    absl::FunctionRef<bool(char32_t)> predicate) const {
  if (position_ < content_size_) {
    char32_t cp = content_.at(position_);
    if (predicate(cp)) {
      return cp;
    }
  }
  return std::nullopt;
}

void Lexer::ConsumeLine() {
  while (position_ < content_size_) {
    if (content_.at(position_) == '\n') {
      Advance(1);
      return;
    }
    Advance(1);
  }
}

void Lexer::ConsumeWhitespace() {
  while (position_ < content_size_) {
    char32_t c = content_.at(position_);
    switch (c) {
      case '\f':
        ABSL_FALLTHROUGH_INTENDED;
      case '\n':
        ABSL_FALLTHROUGH_INTENDED;
      case ' ':
        ABSL_FALLTHROUGH_INTENDED;
      case '\r':
        ABSL_FALLTHROUGH_INTENDED;
      case '\t':
        Advance(1);
        break;
      default:
        return;
    }
  }
}

bool Lexer::Consume(char32_t c) {
  ABSL_DCHECK_NE(c, '\n');
  if (Match(c)) {
    Advance(1);
    return true;
  }
  return false;
}

bool Lexer::ConsumeIgnoreCase(char32_t c) {
  ABSL_DCHECK_NE(c, '\n');
  if (MatchIgnoreCase(c)) {
    Advance(1);
    return true;
  }
  return false;
}

bool Lexer::ConsumeString(std::u32string_view s) {
  ABSL_DCHECK(s.find(U'\n') == std::u32string_view::npos);
  if (MatchString(s)) {
    Advance(s.size());
    return true;
  }
  return false;
}

std::optional<char32_t> Lexer::ConsumeIf(
    absl::FunctionRef<bool(char32_t)> predicate) {
  std::optional<char32_t> match = MatchIf(predicate);
  if (match.has_value()) {
    ABSL_DCHECK_NE(*match, '\n');
    Advance(1);
  }
  return match;
}

bool Lexer::ConsumeDigits() {
  bool advanced = false;
  while (position_ < content_size_) {
    char32_t c = content_.at(position_);
    if (c > 0x7f || !absl::ascii_isdigit(static_cast<char>(c))) {
      break;
    }
    Advance(1);
    advanced = true;
  }
  return advanced;
}

bool Lexer::ConsumeHexDigits() {
  bool advanced = false;
  while (position_ < content_size_) {
    char32_t c = content_.at(position_);
    if (c > 0x7f || !absl::ascii_isxdigit(static_cast<char>(c))) {
      break;
    }
    Advance(1);
    advanced = true;
  }
  return advanced;
}

TokenType Lexer::ConsumeIntegralSuffix() {
  if (ConsumeIgnoreCase('u')) {
    return TokenType::kUint;
  }
  return TokenType::kInt;
}

Token Lexer::ConsumeQuotedIdent() {
  int32_t start = GetPosition();
  Advance(1);
  if (!ConsumeUntilAfter('`', /*is_raw=*/true)) {
    return SetError(start, GetPosition(), "unterminated quoted identifier");
  }
  return MakeToken(TokenType::kIdent, start, GetPosition());
}

Token Lexer::ConsumeStringLiteral(int32_t start, char32_t quote, bool is_bytes,
                                  bool is_raw) {
  Advance(1);
  std::u32string triple_quote(3, quote);
  if (ConsumeString(std::u32string_view(triple_quote.data(), 2))) {
    if (is_raw ? !ConsumeUntilAfterString(triple_quote)
               : !ConsumeUntilAfterUnescapedString(triple_quote)) {
      return SetError(start, GetPosition(),
                      is_bytes ? "unterminated bytes literal"
                               : "unterminated string literal");
    }
    return MakeToken(is_bytes ? TokenType::kBytes : TokenType::kString, start,
                     GetPosition());
  }
  if (!ConsumeUntilAfter(quote, is_raw)) {
    return SetError(start, GetPosition(),
                    is_bytes ? "unterminated bytes literal"
                             : "unterminated string literal");
  }
  return MakeToken(is_bytes ? TokenType::kBytes : TokenType::kString, start,
                   GetPosition());
}

// Consumes prefixed string and bytes literals.
// Handles the following prefix sequences (case-insensitive for 'r' and 'b'):
// - Raw strings: r"...", r'...', r"""...""", r'''...'''
// - Bytes: b"...", b'...', b"""...""", b'''...'''
// - Raw bytes: br"...", br'...', br"""...""", br'''...''', rb"...", rb'...',
//              rb"""...""", rb'''...'''
std::optional<Token> Lexer::ConsumePrefixedStringLiteral() {
  int32_t start = GetPosition();
  if (position_ >= content_size_) return std::nullopt;
  char32_t c = content_.at(position_);
  bool is_bytes = (c == 'b' || c == 'B');
  bool is_raw = (c == 'r' || c == 'R');
  size_t lookahead = 1;
  if (position_ + 1 < content_size_) {
    char32_t c2 = content_.at(position_ + 1);
    if ((is_bytes && (c2 == 'r' || c2 == 'R')) ||
        (!is_bytes && (c2 == 'b' || c2 == 'B'))) {
      is_bytes = true;
      is_raw = true;
      lookahead = 2;
    }
  }
  if (position_ + static_cast<int32_t>(lookahead) < content_size_) {
    char32_t quote = content_.at(position_ + static_cast<int32_t>(lookahead));
    if (quote == '"' || quote == '\'') {
      Advance(lookahead);
      return ConsumeStringLiteral(start, quote, is_bytes, is_raw);
    }
  }
  return std::nullopt;
}

// Consumes a numeric literal token and returns its TokenType (kInt, kUint, or
// kFloat). Recognizes the following literal formats:
// - Hexadecimal integers (kInt / kUint): 0x1A, 0XFFu, 0x0U
// - Decimal integers (kInt / kUint): 0, 45U, 123456
// - Floating-point numbers (kFloat): .12345, 1.23, 1e6, 1.5e+10, .5e-3
Token Lexer::ConsumeNumericLiteral() {
  int32_t start = GetPosition();
  char32_t c = content_.at(position_);
  bool floating_point = false;
  if (c == '.') {
    floating_point = true;
    Advance(1);
    if (!ConsumeDigits()) {
      return SetError(
          start, GetPosition(),
          "floating point literal missing digits after decimal separator");
    }
  } else {
    Advance(1);
    if (c == '0') {
      if (ConsumeIgnoreCase('x')) {
        if (!ConsumeHexDigits()) {
          return SetError(
              start, GetPosition(),
              "integral literal missing digits after hexadecimal separator");
        }
        auto token_type = ConsumeIntegralSuffix();
        return MakeToken(token_type, start, GetPosition());
      }
    }
    static_cast<void>(ConsumeDigits());
    if (position_ < content_size_ && content_.at(position_) == '.' &&
        position_ + 1 < content_size_ && content_.at(position_ + 1) <= 0x7f &&
        absl::ascii_isdigit(static_cast<char>(content_.at(position_ + 1)))) {
      floating_point = true;
      Advance(1);
      static_cast<void>(ConsumeDigits());
    }
  }
  if (ConsumeIgnoreCase('e')) {
    floating_point = true;
    static_cast<void>(ConsumeIf(IsPlusOrMinus));
    if (!ConsumeDigits()) {
      return SetError(
          start, GetPosition(),
          "floating point literal missing digits after exponent separator");
    }
  }
  auto token_type =
      floating_point ? TokenType::kFloat : ConsumeIntegralSuffix();
  return MakeToken(token_type, start, GetPosition());
}

Token Lexer::ConsumeIdent() {
  int32_t start = GetPosition();
  while (position_ < content_size_) {
    char32_t c = content_.at(position_);
    if (!IsIdentTrailing(c)) {
      break;
    }
    Advance(1);
  }
  int32_t end = GetPosition();
  std::string word = content_.ToString(start, end);
  const auto& keywords = Keywords();
  if (auto it = keywords.find(word); it != keywords.end()) {
    return MakeToken(it->second, start, end);
  }
  return MakeToken(TokenType::kIdent, start, end);
}

}  // namespace cel::parser_internal

Coverage Report

Created: 2026-10-09 06:57

Line	Count	Source
1		// Copyright 2026 Google LLC
2		//
3		// Licensed under the Apache License, Version 2.0 (the "License");
4		// you may not use this file except in compliance with the License.
5		// You may obtain a copy of the License at
6		//
7		// https://www.apache.org/licenses/LICENSE-2.0
8		//
9		// Unless required by applicable law or agreed to in writing, software
10		// distributed under the License is distributed on an "AS IS" BASIS,
11		// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12		// See the License for the specific language governing permissions and
13		// limitations under the License.
14
15		#include "parser/internal/lexer.h"
16
17		#include <cstddef>
18		#include <cstdint>
19		#include <optional>
20		#include <string>
21		#include <string_view>
22
23		#include "absl/base/attributes.h"
24		#include "absl/base/no_destructor.h"
25		#include "absl/base/optimization.h"
26		#include "absl/container/flat_hash_map.h"
27		#include "absl/functional/function_ref.h"
28		#include "absl/log/absl_check.h"
29		#include "absl/strings/ascii.h"
30		#include "absl/strings/string_view.h"
31
32		namespace cel::parser_internal {
33
34		namespace {
35
36	0	[[nodiscard]] bool IsIdentTrailing(char32_t c) {
37	0	return c <= 0x7f && (absl::ascii_isdigit(static_cast<char>(c)) \|\|
38	0	absl::ascii_isalpha(static_cast<char>(c)) \|\| c == '_');
39	0	}
40
41	0	[[nodiscard]] bool IsPlusOrMinus(char32_t c) { return c == '+' \|\| c == '-'; }
42
43		[[nodiscard]] const absl::flat_hash_map<std::string_view, TokenType>&
44	0	Keywords() {
45	0	static const absl::NoDestructor<
46	0	absl::flat_hash_map<std::string_view, TokenType>>
47	0	kKeywords({
48	0	{"false", TokenType::kFalse},
49	0	{"true", TokenType::kTrue},
50	0	{"null", TokenType::kNull},
51	0	{"in", TokenType::kIn},
52	0	{"as", TokenType::kReservedWord},
53	0	{"break", TokenType::kReservedWord},
54	0	{"const", TokenType::kReservedWord},
55	0	{"continue", TokenType::kReservedWord},
56	0	{"else", TokenType::kReservedWord},
57	0	{"for", TokenType::kReservedWord},
58	0	{"function", TokenType::kReservedWord},
59	0	{"if", TokenType::kReservedWord},
60	0	{"import", TokenType::kReservedWord},
61	0	{"let", TokenType::kReservedWord},
62	0	{"loop", TokenType::kReservedWord},
63	0	{"package", TokenType::kReservedWord},
64	0	{"namespace", TokenType::kReservedWord},
65	0	{"return", TokenType::kReservedWord},
66	0	{"var", TokenType::kReservedWord},
67	0	{"void", TokenType::kReservedWord},
68	0	{"while", TokenType::kReservedWord},
69	0	});
70	0	return *kKeywords;
71	0	}
72
73		} // namespace
74
75	0	std::string_view TokenTypeToString(TokenType type) {
76	0	switch (type) {
77	0	case TokenType::kError:
78	0	return "error";
79	0	case TokenType::kEnd:
80	0	return "end";
81	0	case TokenType::kWhitespace:
82	0	return "whitespace";
83	0	case TokenType::kComment:
84	0	return "comment";
85	0	case TokenType::kNull:
86	0	return "null";
87	0	case TokenType::kFalse:
88	0	return "false";
89	0	case TokenType::kTrue:
90	0	return "true";
91	0	case TokenType::kIn:
92	0	return "in";
93	0	case TokenType::kReservedWord:
94	0	return "reserved_word";
95	0	case TokenType::kInt:
96	0	return "int";
97	0	case TokenType::kUint:
98	0	return "uint";
99	0	case TokenType::kFloat:
100	0	return "float";
101	0	case TokenType::kString:
102	0	return "string";
103	0	case TokenType::kBytes:
104	0	return "bytes";
105	0	case TokenType::kIdent:
106	0	return "ident";
107	0	case TokenType::kLeftBracket:
108	0	return "[";
109	0	case TokenType::kRightBracket:
110	0	return "]";
111	0	case TokenType::kLeftBrace:
112	0	return "{";
113	0	case TokenType::kRightBrace:
114	0	return "}";
115	0	case TokenType::kLeftParen:
116	0	return "(";
117	0	case TokenType::kRightParen:
118	0	return ")";
119	0	case TokenType::kDot:
120	0	return ".";
121	0	case TokenType::kComma:
122	0	return ",";
123	0	case TokenType::kMinus:
124	0	return "-";
125	0	case TokenType::kPlus:
126	0	return "+";
127	0	case TokenType::kAsterisk:
128	0	return "*";
129	0	case TokenType::kSlash:
130	0	return "/";
131	0	case TokenType::kPercent:
132	0	return "%";
133	0	case TokenType::kQuestion:
134	0	return "?";
135	0	case TokenType::kColon:
136	0	return ":";
137	0	case TokenType::kExclamation:
138	0	return "!";
139	0	case TokenType::kEqual:
140	0	return "=";
141	0	case TokenType::kEqualEqual:
142	0	return "==";
143	0	case TokenType::kExclamationEqual:
144	0	return "!=";
145	0	case TokenType::kLess:
146	0	return "<";
147	0	case TokenType::kLessEqual:
148	0	return "<=";
149	0	case TokenType::kGreater:
150	0	return ">";
151	0	case TokenType::kGreaterEqual:
152	0	return ">=";
153	0	case TokenType::kLogicalAnd:
154	0	return "&&";
155	0	case TokenType::kLogicalOr:
156	0	return "\|\|";
157	0	default:
158	0	return "<unknown>";
159	0	}
160	0	}
161
162	0	Token Lexer::Lex() {
163	0	int32_t start = GetPosition();
164	0	if (ABSL_PREDICT_FALSE(position_ >= content_size_)) {
165	0	return MakeToken(TokenType::kEnd, start, start);
166	0	}
167	0	char32_t c = content_.at(position_);
168	0	switch (c) {
169	0	case '\f':
170	0	ABSL_FALLTHROUGH_INTENDED;
171	0	case '\t':
172	0	ABSL_FALLTHROUGH_INTENDED;
173	0	case '\r':
174	0	ABSL_FALLTHROUGH_INTENDED;
175	0	case '\n':
176	0	ABSL_FALLTHROUGH_INTENDED;
177	0	case ' ': {
178	0	ConsumeWhitespace();
179	0	return MakeToken(TokenType::kWhitespace, start, GetPosition());
180	0	}
181	0	case '.': {
182	0	if (position_ + 1 < content_size_ && content_.at(position_ + 1) <= 0x7f &&
183	0	absl::ascii_isdigit(static_cast<char>(content_.at(position_ + 1)))) {
184	0	return ConsumeNumericLiteral();
185	0	}
186	0	Advance(1);
187	0	return MakeToken(TokenType::kDot, start, GetPosition());
188	0	}
189	0	case ',': {
190	0	Advance(1);
191	0	return MakeToken(TokenType::kComma, start, GetPosition());
192	0	}
193	0	case '!': {
194	0	Advance(1);
195	0	if (Consume('=')) {
196	0	return MakeToken(TokenType::kExclamationEqual, start, GetPosition());
197	0	}
198	0	return MakeToken(TokenType::kExclamation, start, GetPosition());
199	0	}
200	0	case '?': {
201	0	Advance(1);
202	0	return MakeToken(TokenType::kQuestion, start, GetPosition());
203	0	}
204	0	case '(': {
205	0	Advance(1);
206	0	return MakeToken(TokenType::kLeftParen, start, GetPosition());
207	0	}
208	0	case ')': {
209	0	Advance(1);
210	0	return MakeToken(TokenType::kRightParen, start, GetPosition());
211	0	}
212	0	case '{': {
213	0	Advance(1);
214	0	return MakeToken(TokenType::kLeftBrace, start, GetPosition());
215	0	}
216	0	case '}': {
217	0	Advance(1);
218	0	return MakeToken(TokenType::kRightBrace, start, GetPosition());
219	0	}
220	0	case '[': {
221	0	Advance(1);
222	0	return MakeToken(TokenType::kLeftBracket, start, GetPosition());
223	0	}
224	0	case ']': {
225	0	Advance(1);
226	0	return MakeToken(TokenType::kRightBracket, start, GetPosition());
227	0	}
228	0	case '=': {
229	0	Advance(1);
230	0	if (Consume('=')) {
231	0	return MakeToken(TokenType::kEqualEqual, start, GetPosition());
232	0	}
233	0	return MakeToken(TokenType::kEqual, start, GetPosition());
234	0	}
235	0	case '<': {
236	0	Advance(1);
237	0	if (Consume('=')) {
238	0	return MakeToken(TokenType::kLessEqual, start, GetPosition());
239	0	}
240	0	return MakeToken(TokenType::kLess, start, GetPosition());
241	0	}
242	0	case '>': {
243	0	Advance(1);
244	0	if (Consume('=')) {
245	0	return MakeToken(TokenType::kGreaterEqual, start, GetPosition());
246	0	}
247	0	return MakeToken(TokenType::kGreater, start, GetPosition());
248	0	}
249	0	case ':': {
250	0	Advance(1);
251	0	return MakeToken(TokenType::kColon, start, GetPosition());
252	0	}
253	0	case '%': {
254	0	Advance(1);
255	0	return MakeToken(TokenType::kPercent, start, GetPosition());
256	0	}
257	0	case '+': {
258	0	Advance(1);
259	0	return MakeToken(TokenType::kPlus, start, GetPosition());
260	0	}
261	0	case '-': {
262	0	Advance(1);
263	0	return MakeToken(TokenType::kMinus, start, GetPosition());
264	0	}
265	0	case '*': {
266	0	Advance(1);
267	0	return MakeToken(TokenType::kAsterisk, start, GetPosition());
268	0	}
269	0	case '/': {
270	0	Advance(1);
271	0	if (Consume('/')) {
272	0	ConsumeLine();
273	0	return MakeToken(TokenType::kComment, start, GetPosition());
274	0	}
275	0	return MakeToken(TokenType::kSlash, start, GetPosition());
276	0	}
277	0	case '&': {
278	0	Advance(1);
279	0	if (Consume('&')) {
280	0	return MakeToken(TokenType::kLogicalAnd, start, GetPosition());
281	0	}
282	0	return SetError(start, GetPosition(),
283	0	"unexpected single '&', expected '&&'");
284	0	}
285	0	case '\|': {
286	0	Advance(1);
287	0	if (Consume('\|')) {
288	0	return MakeToken(TokenType::kLogicalOr, start, GetPosition());
289	0	}
290	0	return SetError(start, GetPosition(),
291	0	"unexpected single '\|', expected '\|\|'");
292	0	}
293	0	case '_': {
294	0	return ConsumeIdent();
295	0	}
296	0	case '`': {
297	0	return ConsumeQuotedIdent();
298	0	}
299	0	case '\'': {
300	0	return ConsumeStringLiteral(start, '\'');
301	0	}
302	0	case '"': {
303	0	return ConsumeStringLiteral(start, '"');
304	0	}
305	0	case 'r':
306	0	ABSL_FALLTHROUGH_INTENDED;
307	0	case 'R':
308	0	ABSL_FALLTHROUGH_INTENDED;
309	0	case 'b':
310	0	ABSL_FALLTHROUGH_INTENDED;
311	0	case 'B': {
312	0	if (auto token = ConsumePrefixedStringLiteral(); token.has_value()) {
313	0	return *token;
314	0	}
315	0	break;
316	0	}
317	0	default:
318	0	break;
319	0	}
320	0	if (c <= 0x7f && absl::ascii_isdigit(static_cast<char>(c))) {
321	0	return ConsumeNumericLiteral();
322	0	}
323	0	if (c <= 0x7f && absl::ascii_isalpha(static_cast<char>(c))) {
324		// Root identifiers (the ones starting with a period) are returned as
325		// a sequence of kDot and kIdent tokens.
326	0	return ConsumeIdent();
327	0	}
328	0	Advance(1);
329	0	return SetError(start, GetPosition(), "unexpected character");
330	0	}
331
332		// Consumes characters up to and including the first occurrence of character
333		// `c`. If `is_raw` is false, backslashes are interpreted as escapes. Returns
334		// true if `c` was found and consumed; false if end of input or an unescaped
335		// newline was reached.
336	0	bool Lexer::ConsumeUntilAfter(char32_t c, bool is_raw) {
337	0	ABSL_DCHECK_NE(c, '\n');
338	0	ABSL_DCHECK_NE(c, '\r');
339	0	int32_t pos = position_;
340	0	bool escaped = false;
341	0	while (pos < content_size_) {
342	0	char32_t cc = content_.at(pos);
343	0	if (cc == '\n' \|\| cc == '\r') {
344	0	AdvanceProcessingNewLines(pos);
345	0	return false;
346	0	}
347	0	if (!is_raw && cc == '\\') {
348	0	escaped = !escaped;
349	0	} else {
350	0	if (cc == c && (is_raw \|\| !escaped)) {
351	0	AdvanceProcessingNewLines(pos + 1);
352	0	return true;
353	0	}
354	0	escaped = false;
355	0	}
356	0	++pos;
357	0	}
358	0	AdvanceProcessingNewLines(content_size_);
359	0	return false;
360	0	}
361
362		// Consumes characters up to and including the first occurrence of substring `s`
363		// without interpreting backslashes as escapes (`s` must not contain newlines).
364		// Returns true if `s` was found and consumed; false if end of input was
365		// reached.
366	0	bool Lexer::ConsumeUntilAfterString(std::u32string_view s) {
367	0	ABSL_DCHECK(s.find(U'\n') == std::u32string_view::npos);
368	0	int32_t pos = position_;
369	0	while (pos + static_cast<int32_t>(s.size()) <= content_size_) {
370	0	bool match = true;
371	0	for (size_t i = 0; i < s.size(); ++i) {
372	0	if (content_.at(pos + static_cast<int32_t>(i)) != s[i]) {
373	0	match = false;
374	0	break;
375	0	}
376	0	}
377	0	if (match) {
378	0	AdvanceProcessingNewLines(pos + static_cast<int32_t>(s.size()));
379	0	return true;
380	0	}
381	0	++pos;
382	0	}
383	0	AdvanceProcessingNewLines(content_size_);
384	0	return false;
385	0	}
386
387		// Consumes characters up to and including the first occurrence of substring `s`
388		// where the first character of `s` is not preceded by an odd number of
389		// backslashes. Returns true if an unescaped `s` was found and consumed; false
390		// if reached EOF.
391	0	bool Lexer::ConsumeUntilAfterUnescapedString(std::u32string_view s) {
392	0	ABSL_DCHECK(s.find(U'\n') == std::u32string_view::npos);
393	0	int32_t pos = position_;
394	0	bool escaped = false;
395	0	while (pos < content_size_) {
396	0	char32_t cc = content_.at(pos);
397	0	if (cc == '\\') {
398	0	escaped = !escaped;
399	0	} else {
400	0	if (!escaped && pos + static_cast<int32_t>(s.size()) <= content_size_) {
401	0	bool match = true;
402	0	for (size_t j = 0; j < s.size(); ++j) {
403	0	if (content_.at(pos + static_cast<int32_t>(j)) != s[j]) {
404	0	match = false;
405	0	break;
406	0	}
407	0	}
408	0	if (match) {
409	0	AdvanceProcessingNewLines(pos + static_cast<int32_t>(s.size()));
410	0	return true;
411	0	}
412	0	}
413	0	escaped = false;
414	0	}
415	0	++pos;
416	0	}
417	0	AdvanceProcessingNewLines(content_size_);
418	0	return false;
419	0	}
420
421	0	bool Lexer::MatchString(std::u32string_view s) const {
422	0	if (position_ + static_cast<int32_t>(s.size()) > content_size_) {
423	0	return false;
424	0	}
425	0	for (size_t i = 0; i < s.size(); ++i) {
426	0	if (content_.at(position_ + static_cast<int32_t>(i)) != s[i]) {
427	0	return false;
428	0	}
429	0	}
430	0	return true;
431	0	}
432
433		std::optional<char32_t> Lexer::MatchIf(
434	0	absl::FunctionRef<bool(char32_t)> predicate) const {
435	0	if (position_ < content_size_) {
436	0	char32_t cp = content_.at(position_);
437	0	if (predicate(cp)) {
438	0	return cp;
439	0	}
440	0	}
441	0	return std::nullopt;
442	0	}
443
444	0	void Lexer::ConsumeLine() {
445	0	while (position_ < content_size_) {
446	0	if (content_.at(position_) == '\n') {
447	0	Advance(1);
448	0	return;
449	0	}
450	0	Advance(1);
451	0	}
452	0	}
453
454	0	void Lexer::ConsumeWhitespace() {
455	0	while (position_ < content_size_) {
456	0	char32_t c = content_.at(position_);
457	0	switch (c) {
458	0	case '\f':
459	0	ABSL_FALLTHROUGH_INTENDED;
460	0	case '\n':
461	0	ABSL_FALLTHROUGH_INTENDED;
462	0	case ' ':
463	0	ABSL_FALLTHROUGH_INTENDED;
464	0	case '\r':
465	0	ABSL_FALLTHROUGH_INTENDED;
466	0	case '\t':
467	0	Advance(1);
468	0	break;
469	0	default:
470	0	return;
471	0	}
472	0	}
473	0	}
474
475	0	bool Lexer::Consume(char32_t c) {
476	0	ABSL_DCHECK_NE(c, '\n');
477	0	if (Match(c)) {
478	0	Advance(1);
479	0	return true;
480	0	}
481	0	return false;
482	0	}
483
484	0	bool Lexer::ConsumeIgnoreCase(char32_t c) {
485	0	ABSL_DCHECK_NE(c, '\n');
486	0	if (MatchIgnoreCase(c)) {
487	0	Advance(1);
488	0	return true;
489	0	}
490	0	return false;
491	0	}
492
493	0	bool Lexer::ConsumeString(std::u32string_view s) {
494	0	ABSL_DCHECK(s.find(U'\n') == std::u32string_view::npos);
495	0	if (MatchString(s)) {
496	0	Advance(s.size());
497	0	return true;
498	0	}
499	0	return false;
500	0	}
501
502		std::optional<char32_t> Lexer::ConsumeIf(
503		absl::FunctionRef<bool(char32_t)> predicate) {
504		std::optional<char32_t> match = MatchIf(predicate);
505		if (match.has_value()) {
506		ABSL_DCHECK_NE(*match, '\n');
507		Advance(1);
508		}
509		return match;
510		}
511
512	0	bool Lexer::ConsumeDigits() {
513	0	bool advanced = false;
514	0	while (position_ < content_size_) {
515	0	char32_t c = content_.at(position_);
516	0	if (c > 0x7f \|\| !absl::ascii_isdigit(static_cast<char>(c))) {
517	0	break;
518	0	}
519	0	Advance(1);
520	0	advanced = true;
521	0	}
522	0	return advanced;
523	0	}
524
525	0	bool Lexer::ConsumeHexDigits() {
526	0	bool advanced = false;
527	0	while (position_ < content_size_) {
528	0	char32_t c = content_.at(position_);
529	0	if (c > 0x7f \|\| !absl::ascii_isxdigit(static_cast<char>(c))) {
530	0	break;
531	0	}
532	0	Advance(1);
533	0	advanced = true;
534	0	}
535	0	return advanced;
536	0	}
537
538	0	TokenType Lexer::ConsumeIntegralSuffix() {
539	0	if (ConsumeIgnoreCase('u')) {
540	0	return TokenType::kUint;
541	0	}
542	0	return TokenType::kInt;
543	0	}
544
545	0	Token Lexer::ConsumeQuotedIdent() {
546	0	int32_t start = GetPosition();
547	0	Advance(1);
548	0	if (!ConsumeUntilAfter('`', /is_raw=/true)) {
549	0	return SetError(start, GetPosition(), "unterminated quoted identifier");
550	0	}
551	0	return MakeToken(TokenType::kIdent, start, GetPosition());
552	0	}
553
554		Token Lexer::ConsumeStringLiteral(int32_t start, char32_t quote, bool is_bytes,
555	0	bool is_raw) {
556	0	Advance(1);
557	0	std::u32string triple_quote(3, quote);
558	0	if (ConsumeString(std::u32string_view(triple_quote.data(), 2))) {
559	0	if (is_raw ? !ConsumeUntilAfterString(triple_quote)
560	0	: !ConsumeUntilAfterUnescapedString(triple_quote)) {
561	0	return SetError(start, GetPosition(),
562	0	is_bytes ? "unterminated bytes literal"
563	0	: "unterminated string literal");
564	0	}
565	0	return MakeToken(is_bytes ? TokenType::kBytes : TokenType::kString, start,
566	0	GetPosition());
567	0	}
568	0	if (!ConsumeUntilAfter(quote, is_raw)) {
569	0	return SetError(start, GetPosition(),
570	0	is_bytes ? "unterminated bytes literal"
571	0	: "unterminated string literal");
572	0	}
573	0	return MakeToken(is_bytes ? TokenType::kBytes : TokenType::kString, start,
574	0	GetPosition());
575	0	}
576
577		// Consumes prefixed string and bytes literals.
578		// Handles the following prefix sequences (case-insensitive for 'r' and 'b'):
579		// - Raw strings: r"...", r'...', r"""...""", r'''...'''
580		// - Bytes: b"...", b'...', b"""...""", b'''...'''
581		// - Raw bytes: br"...", br'...', br"""...""", br'''...''', rb"...", rb'...',
582		// rb"""...""", rb'''...'''
583	0	std::optional<Token> Lexer::ConsumePrefixedStringLiteral() {
584	0	int32_t start = GetPosition();
585	0	if (position_ >= content_size_) return std::nullopt;
586	0	char32_t c = content_.at(position_);
587	0	bool is_bytes = (c == 'b' \|\| c == 'B');
588	0	bool is_raw = (c == 'r' \|\| c == 'R');
589	0	size_t lookahead = 1;
590	0	if (position_ + 1 < content_size_) {
591	0	char32_t c2 = content_.at(position_ + 1);
592	0	if ((is_bytes && (c2 == 'r' \|\| c2 == 'R')) \|\|
593	0	(!is_bytes && (c2 == 'b' \|\| c2 == 'B'))) {
594	0	is_bytes = true;
595	0	is_raw = true;
596	0	lookahead = 2;
597	0	}
598	0	}
599	0	if (position_ + static_cast<int32_t>(lookahead) < content_size_) {
600	0	char32_t quote = content_.at(position_ + static_cast<int32_t>(lookahead));
601	0	if (quote == '"' \|\| quote == '\'') {
602	0	Advance(lookahead);
603	0	return ConsumeStringLiteral(start, quote, is_bytes, is_raw);
604	0	}
605	0	}
606	0	return std::nullopt;
607	0	}
608
609		// Consumes a numeric literal token and returns its TokenType (kInt, kUint, or
610		// kFloat). Recognizes the following literal formats:
611		// - Hexadecimal integers (kInt / kUint): 0x1A, 0XFFu, 0x0U
612		// - Decimal integers (kInt / kUint): 0, 45U, 123456
613		// - Floating-point numbers (kFloat): .12345, 1.23, 1e6, 1.5e+10, .5e-3
614	0	Token Lexer::ConsumeNumericLiteral() {
615	0	int32_t start = GetPosition();
616	0	char32_t c = content_.at(position_);
617	0	bool floating_point = false;
618	0	if (c == '.') {
619	0	floating_point = true;
620	0	Advance(1);
621	0	if (!ConsumeDigits()) {
622	0	return SetError(
623	0	start, GetPosition(),
624	0	"floating point literal missing digits after decimal separator");
625	0	}
626	0	} else {
627	0	Advance(1);
628	0	if (c == '0') {
629	0	if (ConsumeIgnoreCase('x')) {
630	0	if (!ConsumeHexDigits()) {
631	0	return SetError(
632	0	start, GetPosition(),
633	0	"integral literal missing digits after hexadecimal separator");
634	0	}
635	0	auto token_type = ConsumeIntegralSuffix();
636	0	return MakeToken(token_type, start, GetPosition());
637	0	}
638	0	}
639	0	static_cast<void>(ConsumeDigits());
640	0	if (position_ < content_size_ && content_.at(position_) == '.' &&
641	0	position_ + 1 < content_size_ && content_.at(position_ + 1) <= 0x7f &&
642	0	absl::ascii_isdigit(static_cast<char>(content_.at(position_ + 1)))) {
643	0	floating_point = true;
644	0	Advance(1);
645	0	static_cast<void>(ConsumeDigits());
646	0	}
647	0	}
648	0	if (ConsumeIgnoreCase('e')) {
649	0	floating_point = true;
650	0	static_cast<void>(ConsumeIf(IsPlusOrMinus));
651	0	if (!ConsumeDigits()) {
652	0	return SetError(
653	0	start, GetPosition(),
654	0	"floating point literal missing digits after exponent separator");
655	0	}
656	0	}
657	0	auto token_type =
658	0	floating_point ? TokenType::kFloat : ConsumeIntegralSuffix();
659	0	return MakeToken(token_type, start, GetPosition());
660	0	}
661
662	0	Token Lexer::ConsumeIdent() {
663	0	int32_t start = GetPosition();
664	0	while (position_ < content_size_) {
665	0	char32_t c = content_.at(position_);
666	0	if (!IsIdentTrailing(c)) {
667	0	break;
668	0	}
669	0	Advance(1);
670	0	}
671	0	int32_t end = GetPosition();
672	0	std::string word = content_.ToString(start, end);
673	0	const auto& keywords = Keywords();
674	0	if (auto it = keywords.find(word); it != keywords.end()) {
675	0	return MakeToken(it->second, start, end);
676	0	}
677	0	return MakeToken(TokenType::kIdent, start, end);
678	0	}
679
680		} // namespace cel::parser_internal