Skip to content

Commit 10814cd

Browse files
dmitriplotnikovcopybara-github
dmitriplotnikov
authored and
copybara-github
committed
[Pratt Parser] Optimize call stack depth via in-place AST mutation and lean dispatch
- In-place AST mutation in binary/ternary operations: - Updated some Parse* functions to accept ExprNode& lhs and mutate lhs in place instead of returning ExprNode by value. - Eliminated some intermediate named temporary rhs stack variables. - Lean ParseUnary and ParsePrimary dispatch: - Extracted prefix operator parsing (!, -) into ParseUnaryOps(), making ParseUnary() a fast single branch for standard non-prefix expressions. PiperOrigin-RevId: 963785455
1 parent d686b67 commit 10814cd

1 file changed

Lines changed: 89 additions & 83 deletions

File tree

‎parser/internal/pratt_parser_worker.h‎

Lines changed: 89 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -223,7 +223,7 @@ class PrattParserWorker : public ParserWorker {
223223

224224
// Parses ternary conditional expressions (`condition ? true_expr :
225225
// false_expr`).
226-
ExprNode ParseTernary(ExprNode lhs);
226+
void ParseTernary(ExprNode& lhs);
227227

228228
// Helper method for parsing a contiguous chain of same-precedence logical
229229
// operators (`&&` or `||`) iteratively into a list of terms and operator IDs.
@@ -234,7 +234,7 @@ class PrattParserWorker : public ParserWorker {
234234
// Example (`a && b && c && d`): Iteratively collects terms `[a, b, c, d]` and
235235
// builds `((a && b) && c) && d` without ascending/descending C++ stack
236236
// frames for each term.
237-
ExprNode ParseBalancedLogicalChain(ExprNode lhs, const BinaryOpInfo& op_info);
237+
void ParseBalancedLogicalChain(ExprNode& lhs, const BinaryOpInfo& op_info);
238238

239239
// Parses prefix unary operators (`!`, `-`) and trailing postfix
240240
// member/indexing operations (`.field`, `[index]`, `.method(args)`). First
@@ -252,7 +252,7 @@ class PrattParserWorker : public ParserWorker {
252252
// `Type{field: val}`).
253253
//
254254
// Processes continuous postfix operation chains iteratively.
255-
ExprNode ParseSelectorChainTail(ExprNode lhs);
255+
void ParseSelectorChainTail(ExprNode& lhs);
256256

257257
// Parses prefix unary operators (logical NOT `!` and negation `-`). If a
258258
// numeric literal immediately follows `-`, folds it directly into a negative
@@ -266,6 +266,9 @@ class PrattParserWorker : public ParserWorker {
266266
// wrapping `has(x.y)`.
267267
ExprNode ParseUnary();
268268

269+
// Parses unary operators (`!`, `-`).
270+
ExprNode ParseUnaryOps();
271+
269272
// Parses unary operator chains (`!`, `-`).
270273
ExprNode ParseUnaryOpsChain(Token first_op);
271274

@@ -284,7 +287,7 @@ class PrattParserWorker : public ParserWorker {
284287
// Example (`(a + b)`): Consumes `(`, recurses to `ParseExpr()`, and expects
285288
// `)`. Example (`has(x.y)`): Consumes `has`, parses arguments `(x.y)`, and
286289
// expands the `has` macro.
287-
ABSL_ATTRIBUTE_ALWAYS_INLINE inline ExprNode ParsePrimary();
290+
ExprNode ParsePrimary();
288291

289292
ExprNode ParseList();
290293
ExprNode ParseMap();
@@ -297,8 +300,8 @@ class PrattParserWorker : public ParserWorker {
297300
ExprNode ParseNegativeDoubleLiteral(int64_t node_id);
298301
ExprNode ParseStringLiteral();
299302
ExprNode ParseBytesLiteral();
300-
ExprNode BuildBinaryCall(int64_t op_id, absl::string_view op_name,
301-
ExprNode lhs, ExprNode rhs);
303+
void BuildBinaryCall(int64_t op_id, absl::string_view op_name, ExprNode& lhs,
304+
ExprNode rhs);
302305
ExprNode ParseIdentOrCall();
303306
std::string NormalizeIdent(const Token& tok, bool allow_quoted);
304307
std::optional<std::string> ExtractStructName(const ExprNode& expr);
@@ -353,34 +356,33 @@ ExprNode PrattParserWorker<ExprNode>::ParseExpr() {
353356
}
354357

355358
template <typename ExprNode>
356-
ExprNode PrattParserWorker<ExprNode>::ParseTernary(ExprNode lhs) {
359+
void PrattParserWorker<ExprNode>::ParseTernary(ExprNode& lhs) {
357360
NextToken();
358361
int64_t op_id = NextId();
359362
ExprNode true_expr = ParseBinaryAndTernary(1);
360363
if (!Expect(TokenType::kColon, "expected ':' in conditional expression")) {
361-
return lhs;
364+
return;
362365
}
363366
ExprNode false_expr = ParseBinaryAndTernary(0);
364367
std::vector<ExprNode> args;
365368
args.reserve(3);
366369
args.push_back(std::move(lhs));
367370
args.push_back(std::move(true_expr));
368371
args.push_back(std::move(false_expr));
369-
return ast_factory_.NewCall(op_id, CelOperator::CONDITIONAL, std::move(args));
372+
lhs = ast_factory_.NewCall(op_id, CelOperator::CONDITIONAL, std::move(args));
370373
}
371374

372375
const BinaryOpInfo& GetBinaryOpInfo(TokenType type);
373376

374377
template <typename ExprNode>
375-
ExprNode PrattParserWorker<ExprNode>::BuildBinaryCall(int64_t op_id,
376-
absl::string_view op_name,
377-
ExprNode lhs,
378-
ExprNode rhs) {
378+
void PrattParserWorker<ExprNode>::BuildBinaryCall(int64_t op_id,
379+
absl::string_view op_name,
380+
ExprNode& lhs, ExprNode rhs) {
379381
std::vector<ExprNode> args;
380382
args.reserve(2);
381383
args.push_back(std::move(lhs));
382384
args.push_back(std::move(rhs));
383-
return ast_factory_.NewCall(op_id, std::string(op_name), std::move(args));
385+
lhs = ast_factory_.NewCall(op_id, std::string(op_name), std::move(args));
384386
}
385387

386388
// Parses binary operator expressions and ternary conditional expressions
@@ -391,31 +393,31 @@ ExprNode PrattParserWorker<ExprNode>::ParseBinaryAndTernary(int min_prec) {
391393
while (true) {
392394
TokenType tok = peek_token_.type;
393395
if (tok == TokenType::kQuestion && min_prec <= 0) {
394-
lhs = ParseTernary(std::move(lhs));
396+
ParseTernary(lhs);
395397
continue;
396398
}
397399

398400
const BinaryOpInfo& op_info = GetBinaryOpInfo(tok);
399401
if (op_info.precedence < min_prec || op_info.precedence == 0) break;
400402

401403
if (op_info.is_logical) {
402-
lhs = ParseBalancedLogicalChain(std::move(lhs), op_info);
404+
ParseBalancedLogicalChain(lhs, op_info);
403405
continue;
404406
}
405407

406408
Token op_tok = NextToken();
407409
int64_t op_id = NextId(op_tok);
408-
ExprNode rhs = ParseBinaryAndTernary(op_info.precedence + 1);
409-
lhs = BuildBinaryCall(op_id, op_info.name, std::move(lhs), std::move(rhs));
410+
BuildBinaryCall(op_id, op_info.name, lhs,
411+
ParseBinaryAndTernary(op_info.precedence + 1));
410412
}
411413
return lhs;
412414
}
413415

414416
// Parses continuous chains of logical operators (`&&`, `||`) iteratively
415417
// (e.g., `a && b && c`) and constructs a balanced or variadic AST.
416418
template <typename ExprNode>
417-
ExprNode PrattParserWorker<ExprNode>::ParseBalancedLogicalChain(
418-
ExprNode lhs, const BinaryOpInfo& op_info) {
419+
void PrattParserWorker<ExprNode>::ParseBalancedLogicalChain(
420+
ExprNode& lhs, const BinaryOpInfo& op_info) {
419421
std::vector<ExprNode> terms;
420422
std::vector<int64_t> ops;
421423
terms.push_back(std::move(lhs));
@@ -425,8 +427,8 @@ ExprNode PrattParserWorker<ExprNode>::ParseBalancedLogicalChain(
425427
ops.push_back(NextId(op_tok));
426428
terms.push_back(std::move(rhs));
427429
}
428-
return BalanceLogical(op_info.name, std::move(terms), std::move(ops),
429-
options_.enable_variadic_logical_operators);
430+
lhs = BalanceLogical(op_info.name, std::move(terms), std::move(ops),
431+
options_.enable_variadic_logical_operators);
430432
}
431433

432434
template <typename ExprNode>
@@ -435,15 +437,15 @@ ExprNode PrattParserWorker<ExprNode>::ParseSelectorChain() {
435437
TokenType tok = peek_token_.type;
436438
if (tok == TokenType::kDot || tok == TokenType::kLeftBracket ||
437439
tok == TokenType::kLeftBrace) {
438-
return ParseSelectorChainTail(std::move(lhs));
440+
ParseSelectorChainTail(lhs);
439441
}
440442
return lhs;
441443
}
442444

443445
// Parses prefix and postfix member/indexing operations iteratively
444446
// (e.g., `!a.b[0].c(x)`).
445447
template <typename ExprNode>
446-
ExprNode PrattParserWorker<ExprNode>::ParseSelectorChainTail(ExprNode lhs) {
448+
void PrattParserWorker<ExprNode>::ParseSelectorChainTail(ExprNode& lhs) {
447449
while (true) {
448450
TokenType tok = peek_token_.type;
449451
if (tok == TokenType::kDot) {
@@ -463,7 +465,7 @@ ExprNode PrattParserWorker<ExprNode>::ParseSelectorChainTail(ExprNode lhs) {
463465
ReportError(id_tok, "expected identifier after '.'");
464466
}
465467
SynchronizeOnDelimiter();
466-
return lhs;
468+
return;
467469
}
468470
bool is_member_call = peek_token_.type == TokenType::kLeftParen;
469471
std::string id_text =
@@ -475,7 +477,8 @@ ExprNode PrattParserWorker<ExprNode>::ParseSelectorChainTail(ExprNode lhs) {
475477
args.push_back(std::move(lhs));
476478
args.push_back(
477479
ast_factory_.NewStringConst(NextId(id_tok), std::move(id_text)));
478-
lhs = ast_factory_.NewCall(op_id, "_?._", std::move(args));
480+
lhs = ast_factory_.NewCall(op_id, CelOperator::OPT_SELECT,
481+
std::move(args));
479482
} else if (peek_token_.type == TokenType::kLeftParen) {
480483
Token lparen = NextToken();
481484
int64_t call_id = NextId(lparen);
@@ -508,8 +511,9 @@ ExprNode PrattParserWorker<ExprNode>::ParseSelectorChainTail(ExprNode lhs) {
508511
args.reserve(2);
509512
args.push_back(std::move(lhs));
510513
args.push_back(std::move(index));
511-
lhs = ast_factory_.NewCall(op_id, optional ? "_[?_]" : CelOperator::INDEX,
512-
std::move(args));
514+
lhs = ast_factory_.NewCall(
515+
op_id, optional ? CelOperator::OPT_INDEX : CelOperator::INDEX,
516+
std::move(args));
513517
} else if (tok == TokenType::kLeftBrace) {
514518
int32_t struct_pos = GetLeftmostPosition(lhs);
515519
if (auto struct_name = ExtractStructName(lhs); struct_name.has_value()) {
@@ -521,7 +525,6 @@ ExprNode PrattParserWorker<ExprNode>::ParseSelectorChainTail(ExprNode lhs) {
521525
break;
522526
}
523527
}
524-
return lhs;
525528
}
526529

527530
template <typename ExprNode>
@@ -574,10 +577,14 @@ ExprNode PrattParserWorker<ExprNode>::ParseUnaryOpsChain(Token first_op) {
574577
template <typename ExprNode>
575578
ExprNode PrattParserWorker<ExprNode>::ParseUnary() {
576579
TokenType tok = peek_token_.type;
577-
if (tok != TokenType::kExclamation && tok != TokenType::kMinus) {
578-
return ParsePrimary();
580+
if (tok == TokenType::kExclamation || tok == TokenType::kMinus) {
581+
return ParseUnaryOps();
579582
}
583+
return ParsePrimary();
584+
}
580585

586+
template <typename ExprNode>
587+
ExprNode PrattParserWorker<ExprNode>::ParseUnaryOps() {
581588
Token op = NextToken();
582589
TokenType op_type = op.type;
583590
if (peek_token_.type == TokenType::kExclamation ||
@@ -650,57 +657,59 @@ ExprNode PrattParserWorker<ExprNode>::ParseIdentOrCall() {
650657
// (`[...]`, `{...}`), and identifiers/global function calls (`foo`,
651658
// `has(x.y)`).
652659
template <typename ExprNode>
653-
ABSL_ATTRIBUTE_ALWAYS_INLINE inline ExprNode
654-
PrattParserWorker<ExprNode>::ParsePrimary() {
655-
ExprNode expr;
656-
TokenType tok_type = peek_token_.type;
657-
if (tok_type == TokenType::kLeftParen) {
658-
int grouping_paren_count = CountGroupingParentheses();
659-
for (int i = 0; i < grouping_paren_count; ++i) {
660-
NextToken();
660+
ExprNode PrattParserWorker<ExprNode>::ParsePrimary() {
661+
switch (peek_token_.type) {
662+
case TokenType::kLeftParen: {
663+
int grouping_paren_count = CountGroupingParentheses();
664+
for (int i = 0; i < grouping_paren_count; ++i) {
665+
NextToken();
666+
}
667+
ExprNode expr = ParseExpr();
668+
for (int i = 0; i < grouping_paren_count; ++i) {
669+
Expect(TokenType::kRightParen);
670+
}
671+
return expr;
661672
}
662-
expr = ParseExpr();
663-
for (int i = 0; i < grouping_paren_count; ++i) {
664-
Expect(TokenType::kRightParen);
673+
case TokenType::kNull:
674+
return ast_factory_.NewNullConst(NextId(NextToken()));
675+
case TokenType::kTrue:
676+
case TokenType::kFalse: {
677+
Token tok = NextToken();
678+
return ast_factory_.NewBoolConst(NextId(tok),
679+
tok.type == TokenType::kTrue);
665680
}
666-
} else if (tok_type == TokenType::kNull) {
667-
Token tok = NextToken();
668-
expr = ast_factory_.NewNullConst(NextId(tok));
669-
} else if (tok_type == TokenType::kTrue || tok_type == TokenType::kFalse) {
670-
Token tok = NextToken();
671-
expr = ast_factory_.NewBoolConst(NextId(tok), tok_type == TokenType::kTrue);
672-
} else if (tok_type == TokenType::kInt) {
673-
expr = ParseIntLiteral();
674-
} else if (tok_type == TokenType::kUint) {
675-
expr = ParseUintLiteral();
676-
} else if (tok_type == TokenType::kFloat) {
677-
expr = ParseDoubleLiteral();
678-
} else if (tok_type == TokenType::kString) {
679-
expr = ParseStringLiteral();
680-
} else if (tok_type == TokenType::kBytes) {
681-
expr = ParseBytesLiteral();
682-
} else if (tok_type == TokenType::kLeftBracket) {
683-
expr = ParseList();
684-
} else if (tok_type == TokenType::kLeftBrace) {
685-
expr = ParseMap();
686-
} else if (tok_type == TokenType::kDot || tok_type == TokenType::kIdent ||
687-
tok_type == TokenType::kReservedWord) {
688-
expr = ParseIdentOrCall();
689-
} else {
690-
Token bad_tok = NextToken();
691-
if (bad_tok.type != TokenType::kError) {
692-
if (bad_tok.type == TokenType::kEnd) {
693-
ReportError(
694-
bad_tok,
695-
"Syntax error: mismatched input '<EOF>' expecting expression");
696-
} else {
697-
ReportError(bad_tok, "unexpected token");
681+
case TokenType::kInt:
682+
return ParseIntLiteral();
683+
case TokenType::kUint:
684+
return ParseUintLiteral();
685+
case TokenType::kFloat:
686+
return ParseDoubleLiteral();
687+
case TokenType::kString:
688+
return ParseStringLiteral();
689+
case TokenType::kBytes:
690+
return ParseBytesLiteral();
691+
case TokenType::kLeftBracket:
692+
return ParseList();
693+
case TokenType::kLeftBrace:
694+
return ParseMap();
695+
case TokenType::kDot:
696+
case TokenType::kIdent:
697+
case TokenType::kReservedWord:
698+
return ParseIdentOrCall();
699+
default: {
700+
Token bad_tok = NextToken();
701+
if (bad_tok.type != TokenType::kError) {
702+
if (bad_tok.type == TokenType::kEnd) {
703+
ReportError(
704+
bad_tok,
705+
"Syntax error: mismatched input '<EOF>' expecting expression");
706+
} else {
707+
ReportError(bad_tok, "unexpected token");
708+
}
698709
}
710+
return ast_factory_.NewUnspecified(NextId(bad_tok));
699711
}
700-
expr = ast_factory_.NewUnspecified(NextId(bad_tok));
701712
}
702-
703-
return expr;
704713
}
705714

706715
// Parses list creation literals (e.g., `[1, 2, ?3]`).
@@ -719,8 +728,7 @@ ExprNode PrattParserWorker<ExprNode>::ParseList() {
719728
ReportError(q, "unsupported syntax '?'");
720729
}
721730
}
722-
ExprNode elem = ParseExpr();
723-
builder.Add(std::move(elem), optional);
731+
builder.Add(ParseExpr(), optional);
724732
if (peek_token_.type == TokenType::kComma) {
725733
NextToken();
726734
} else {
@@ -757,8 +765,7 @@ ExprNode PrattParserWorker<ExprNode>::ParseMap() {
757765
break;
758766
}
759767
int64_t entry_id = NextId(colon);
760-
ExprNode val = ParseExpr();
761-
builder.Add(entry_id, std::move(key), std::move(val), optional);
768+
builder.Add(entry_id, std::move(key), ParseExpr(), optional);
762769
if (peek_token_.type == TokenType::kComma) {
763770
NextToken();
764771
} else {
@@ -801,8 +808,7 @@ ExprNode PrattParserWorker<ExprNode>::ParseStruct(
801808
break;
802809
}
803810
int64_t field_id = NextId(colon);
804-
ExprNode val = ParseExpr();
805-
builder.Add(field_id, std::move(field_name), std::move(val), optional);
811+
builder.Add(field_id, std::move(field_name), ParseExpr(), optional);
806812
if (peek_token_.type == TokenType::kComma) {
807813
NextToken();
808814
} else {

0 commit comments

Comments
 (0)