/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/str_cat.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())) {
    at_end_ = true;
    done_ = true;
    return MakeToken(TokenType::kEnd, start, start);
  }
  char32_t c = content_.at(position_);
  switch (c) {
    case '\f':
      ABSL_FALLTHROUGH_INTENDED;
    case '\v':
      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`
// without interpreting backslashes as escapes.
// Returns true if `c` was found and consumed; false if end of input was
// reached.
bool Lexer::ConsumeUntilAfter(char32_t c) {
  ABSL_DCHECK_NE(c, '\n');
  for (int32_t pos = position_; pos < content_.size(); ++pos) {
    if (content_.at(pos) == c) {
      AdvanceProcessingNewLines(pos + 1);
      return true;
    }
  }
  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 `c` that is
// not preceded by an odd number of backslash ('\') escape characters. Returns
// true if an unescaped `c` was found and consumed; false if reached EOF.
bool Lexer::ConsumeUntilAfterUnescaped(char32_t c) {
  ABSL_DCHECK_NE(c, '\n');
  ABSL_DCHECK_NE(c, '\\');
  int32_t pos = position_;
  bool escaped = false;
  while (pos < content_.size()) {
    char32_t cc = content_.at(pos);
    if (cc == '\\') {
      escaped = !escaped;
    } else {
      if (cc == c && !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`
// 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 '\v':
        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('`')) {
    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 (is_raw ? !ConsumeUntilAfter(quote) : !ConsumeUntilAfterUnescaped(quote)) {
    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();
        if (ConsumeIf(IsIdentTrailing)) {
          return SetError(
              start, GetPosition(),
              absl::StrCat(TokenTypeToString(token_type),
                           " literal has unexpected trailing characters"));
        }
        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();
  if (ConsumeIf(IsIdentTrailing)) {
    return SetError(
        start, GetPosition(),
        absl::StrCat(TokenTypeToString(token_type),
                     " literal has unexpected trailing characters"));
  }
  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-09-14 06:52

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