Google Git
Sign in
chromium/external/github.com/google/cel-go/refs/heads/pratt-parser-simplify^!/.
commit
bea75e02d8c1fa77f3e6958c0bed422a8ca0e4b0
[log]
author
dplotnikov <dplotnikov@google.com>
Thu Aug 27 16:58:10 2026
committer
dplotnikov <dplotnikov@google.com>
Thu Aug 27 22:25:12 2026
tree
e3ddd97d64b02bb438fd74a1602bbcab76b00ed0
parent
05f47385e82949e1576e33eefc1a5d7b44461ef8 [diff]
[Pratt parser] Simplify helper methods and inlining

Inline single-callsite helper functions (initTokenStream, parse,
newLogicManager, receiverCallOrMacro, globalCallOrMacro) to simplify
pratt_parser.go while preserving stack frame sizes and recursive descent
performance boundaries.

| Category | ANTLR (Max Depth OK) | Pratt (Max Depth OK) | Pratt Advantage |
| :--- | :--- | :--- | :--- |
| **Parens** (`(((...42...)))`) | 20 | unlimited | **unlimited** |
| **Unary** (`! ! ! ... true`) | unlimited | unlimited | **1.0x** |
| **Binary** (`1 + (1 + (...42...))`) | 21 | 93 | **~4.4x** |
| **List** (`[[[...42...]]]`) | 18 | 85 | **~4.7x** |

| Benchmark Category | ns/op | B/op | allocs/op |
| :--- | :--- | :--- | :--- |
| **Simple** | 27,429 ns/op | 13,535 B/op | 404 allocs/op |
| **Complex** | 107,297 ns/op | 51,864 B/op | 1,397 allocs/op |
| **Macros** | 50,519 ns/op | 23,883 B/op | 641 allocs/op |
| **Errors** | 83,839 ns/op | 37,764 B/op | 1,176 allocs/op |
| **Parallel/Simple** | 6,732 ns/op | 13,494 B/op | 404 allocs/op |
| **Parallel/Complex** | 26,721 ns/op | 51,865 B/op | 1,397 allocs/op |
| **Parallel/Macros** | 11,902 ns/op | 23,732 B/op | 641 allocs/op |
| **Parallel/Errors** | 21,489 ns/op | 37,659 B/op | 1,176 allocs/op |

diff --git a/parser/pratt_parser.go b/parser/pratt_parser.go
index f916332..1ab416a 100644
--- a/parser/pratt_parser.go
+++ b/parser/pratt_parser.go

@@ -131,7 +131,7 @@
 		accu = HiddenAccumulatorName
 	}
 	fac := ast.NewExprFactoryWithAccumulator(accu)
-	pratt := &prattParserWorker{
+	worker := &prattParserWorker{
 		content:                    buf,
 		length:                     int32(buf.Len()),
 		helper:                     newParserHelper(source, fac),
@@ -148,17 +148,23 @@
 		enableVariadicOperatorASTs: p.enableVariadicOperatorASTs,
 		enableIdentEscapeSyntax:    p.enableIdentEscapeSyntax,
 	}
-	pratt.initTokenStream()
-	out := pratt.parse()
+	worker.currTok = token{kind: tokError, start: 0, end: 0}
+	worker.peekTok = worker.nextSignificantToken(true)
+	out := worker.parseExpr()
+	if !worker.recursionLimitExceeded && !worker.isRecoveryLimitExceeded() {
+		if worker.peekTok.kind != tokEnd {
+			if worker.peekTok.kind != tokError {
+				worker.reportError(worker.peekTok, "Syntax error: mismatched input '%s' expecting <EOF>", worker.tokenText(worker.peekTok))
+			}
+			for worker.peekTok.kind != tokEnd && !worker.isRecoveryLimitExceeded() {
+				worker.nextToken()
+			}
+		}
+	}
 	if len(errs.GetErrors()) > 0 {
 		return nil, errs
 	}
-	return ast.NewAST(out, pratt.helper.getSourceInfo()), errs
-}
-
-func (p *prattParserWorker) initTokenStream() {
-	p.currTok = token{kind: tokError, start: 0, end: 0}
-	p.peekTok = p.nextSignificantToken(true)
+	return ast.NewAST(out, worker.helper.getSourceInfo()), errs
 }
 
 func (p *prattParserWorker) isRecoveryLimitExceeded() bool {
@@ -270,27 +276,6 @@
 	return err
 }
 
-func (p *prattParserWorker) newLogicManager(function string, term ast.Expr) *logicManager {
-	if p.enableVariadicOperatorASTs {
-		return newVariadicLogicManager(p.exprFactory, function, term)
-	}
-	return newBalancingLogicManager(p.exprFactory, function, term)
-}
-
-func (p *prattParserWorker) globalCallOrMacro(exprID int64, function string, args ...ast.Expr) ast.Expr {
-	if expr, found := p.expandMacro(exprID, function, nil, args...); found {
-		return expr
-	}
-	return p.helper.newGlobalCall(exprID, function, args...)
-}
-
-func (p *prattParserWorker) receiverCallOrMacro(exprID int64, function string, target ast.Expr, args ...ast.Expr) ast.Expr {
-	if expr, found := p.expandMacro(exprID, function, target, args...); found {
-		return expr
-	}
-	return p.helper.newReceiverCall(exprID, function, target, args...)
-}
-
 func (p *prattParserWorker) expandMacro(exprID int64, function string, target ast.Expr, args ...ast.Expr) (ast.Expr, bool) {
 	if len(p.macros) == 0 {
 		return nil, false
@@ -370,22 +355,6 @@
 	return text
 }
 
-func (p *prattParserWorker) parse() ast.Expr {
-	expr := p.parseExpr()
-	if p.recursionLimitExceeded || p.isRecoveryLimitExceeded() {
-		return expr
-	}
-	if p.peekTok.kind != tokEnd {
-		if p.peekTok.kind != tokError {
-			p.reportError(p.peekTok, "Syntax error: mismatched input '%s' expecting <EOF>", p.tokenText(p.peekTok))
-		}
-		for p.peekTok.kind != tokEnd && !p.isRecoveryLimitExceeded() {
-			p.nextToken()
-		}
-	}
-	return expr
-}
-
 func (p *prattParserWorker) parseExpr() ast.Expr {
 	if p.recursionLimitExceeded || p.isRecoveryLimitExceeded() {
 		return p.helper.newExpr(common.NoLocation)
@@ -440,7 +409,12 @@
 }
 
 func (p *prattParserWorker) parseLogicalChain(lhs ast.Expr, opInfo binaryOpInfo) ast.Expr {
-	l := p.newLogicManager(opInfo.name, lhs)
+	var l *logicManager
+	if p.enableVariadicOperatorASTs {
+		l = newVariadicLogicManager(p.exprFactory, opInfo.name, lhs)
+	} else {
+		l = newBalancingLogicManager(p.exprFactory, opInfo.name, lhs)
+	}
 	for p.peekTok.kind == opInfo.kind {
 		opTok := p.nextToken()
 		rhs := p.parseBinaryAndTernary(opInfo.precedence + 1)
@@ -486,7 +460,11 @@
 				lparen := p.nextToken()
 				callID := p.nextID(lparen)
 				args := p.parseArguments(tokRightParen)
-				lhs = p.receiverCallOrMacro(callID, field, lhs, args...)
+				if expr, found := p.expandMacro(callID, field, lhs, args...); found {
+					lhs = expr
+				} else {
+					lhs = p.helper.newReceiverCall(callID, field, lhs, args...)
+				}
 			} else {
 				dotID := p.nextID(dotTok)
 				lhs = p.helper.newSelect(dotID, lhs, field)
@@ -600,22 +578,20 @@
 		return p.parseUnaryOpsChain(op)
 	}
 
+	opID := p.nextID(op)
 	if op.kind == tokMinus {
 		if p.peekTok.kind == tokInt {
-			return p.parseNegativeIntLiteral(p.nextID(op))
+			return p.parseNegativeIntLiteral(opID)
 		}
 		if p.peekTok.kind == tokFloat {
-			return p.parseNegativeDoubleLiteral(p.nextID(op))
+			return p.parseNegativeDoubleLiteral(opID)
 		}
+		operand := p.parseSelectorChain()
+		return p.helper.newGlobalCall(opID, operators.Negate, operand)
+	} else { // op.kind == tokExclamation
+		operand := p.parseSelectorChain()
+		return p.helper.newGlobalCall(opID, operators.LogicalNot, operand)
 	}
-
-	opID := p.nextID(op)
-	operand := p.parseSelectorChain()
-	opName := operators.LogicalNot
-	if op.kind == tokMinus {
-		opName = operators.Negate
-	}
-	return p.globalCallOrMacro(opID, opName, operand)
 }
 
 func (p *prattParserWorker) parseUnaryOpsChain(firstOp token) ast.Expr {
@@ -649,11 +625,11 @@
 	}
 
 	for i := len(ops) - 1; i >= 0; i-- {
-		opName := operators.LogicalNot
 		if ops[i].kind == tokMinus {
-			opName = operators.Negate
+			operand = p.helper.newGlobalCall(ops[i].id, operators.Negate, operand)
+		} else {
+			operand = p.helper.newGlobalCall(ops[i].id, operators.LogicalNot, operand)
 		}
-		operand = p.helper.newGlobalCall(ops[i].id, opName, operand)
 	}
 	return operand
 }
@@ -850,7 +826,10 @@
 	if p.peekTok.kind == tokLeftParen {
 		p.nextToken()
 		args := p.parseArguments(tokRightParen)
-		return p.globalCallOrMacro(id, name, args...)
+		if expr, found := p.expandMacro(id, name, nil, args...); found {
+			return expr
+		}
+		return p.helper.newGlobalCall(id, name, args...)
 	}
 	return p.helper.newIdent(id, name)
 }