Fix stack-overflow in `lhs_expression`.
Currently when parsing `*` and `&` we recursively call into ourselves to
process the tokens. This can cause stack issues if there are an
excessive number of `*`s and `&`s.
This Cl changes `lhs_expression` to generate a list of UnaryOps to be
applied and does not recursively call `lhs_expression`.
Bug: chromium:1394972
Change-Id: I40caee05c9b7f71abb776d375cbf995c6a1fd36f
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/112580
Commit-Queue: Dan Sinclair <dsinclair@chromium.org>
Reviewed-by: Ben Clayton <bclayton@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
diff --git a/src/tint/reader/wgsl/parser_impl.cc b/src/tint/reader/wgsl/parser_impl.cc
index 49e266f..a04e548 100644
--- a/src/tint/reader/wgsl/parser_impl.cc
+++ b/src/tint/reader/wgsl/parser_impl.cc
@@ -43,6 +43,7 @@
#include "src/tint/sem/external_texture.h"
#include "src/tint/sem/multisampled_texture.h"
#include "src/tint/sem/sampled_texture.h"
+#include "src/tint/utils/reverse.h"
#include "src/tint/utils/string.h"
namespace tint::reader::wgsl {
@@ -3239,34 +3240,50 @@
return component_or_swizzle_specifier(core_expr.value);
}
- auto check_lhs = [&](ast::UnaryOp op) -> Maybe<const ast::Expression*> {
- auto& t = peek();
- auto expr = lhs_expression();
- if (expr.errored) {
- return Failure::kErrored;
- }
- if (!expr.matched) {
- return add_error(t, "missing expression");
- }
- return create<ast::UnaryOpExpression>(t.source(), op, expr.value);
+ // Gather up all the `*`, `&` and `&&` tokens into a list and create all of the unary ops at
+ // once instead of recursing. This handles the case where the fuzzer decides >8k `*`s would be
+ // fun.
+ struct LHSData {
+ Source source;
+ ast::UnaryOp op;
};
+ utils::Vector<LHSData, 4> ops;
+ while (true) {
+ auto& t = peek();
+ if (!t.Is(Token::Type::kAndAnd) && !t.Is(Token::Type::kAnd) && !t.Is(Token::Type::kStar)) {
+ break;
+ }
+ next(); // consume the peek
- // If an `&&` is encountered, split it into two `&`'s
- if (match(Token::Type::kAndAnd)) {
- // The first `&` is consumed as part of the `&&`, so this needs to run the check itself.
- split_token(Token::Type::kAnd, Token::Type::kAnd);
- return check_lhs(ast::UnaryOp::kAddressOf);
+ if (t.Is(Token::Type::kAndAnd)) {
+ // The first `&` is consumed as part of the `&&`, so we only push one of the two `&`s.
+ split_token(Token::Type::kAnd, Token::Type::kAnd);
+ ops.Push({t.source(), ast::UnaryOp::kAddressOf});
+ } else if (t.Is(Token::Type::kAnd)) {
+ ops.Push({t.source(), ast::UnaryOp::kAddressOf});
+ } else if (t.Is(Token::Type::kStar)) {
+ ops.Push({t.source(), ast::UnaryOp::kIndirection});
+ }
+ }
+ if (ops.IsEmpty()) {
+ return Failure::kNoMatch;
}
- if (match(Token::Type::kAnd)) {
- return check_lhs(ast::UnaryOp::kAddressOf);
+ auto& t = peek();
+ auto expr = lhs_expression();
+ if (expr.errored) {
+ return Failure::kErrored;
+ }
+ if (!expr.matched) {
+ return add_error(t, "missing expression");
}
- if (match(Token::Type::kStar)) {
- return check_lhs(ast::UnaryOp::kIndirection);
+ const ast::Expression* ret = expr.value;
+ // Consume the ops in reverse order so we have the correct AST ordering.
+ for (auto& info : utils::Reverse(ops)) {
+ ret = create<ast::UnaryOpExpression>(info.source, info.op, ret);
}
-
- return Failure::kNoMatch;
+ return ret;
}
// variable_updating_statement
diff --git a/src/tint/reader/wgsl/parser_impl_lhs_expression_test.cc b/src/tint/reader/wgsl/parser_impl_lhs_expression_test.cc
index 4e1e0db..a8a476b 100644
--- a/src/tint/reader/wgsl/parser_impl_lhs_expression_test.cc
+++ b/src/tint/reader/wgsl/parser_impl_lhs_expression_test.cc
@@ -75,17 +75,20 @@
}
TEST_F(ParserImplTest, LHSExpression_Multiple) {
- auto p = parser("*&**&&*a");
+ auto p = parser("*&********&&&&&&*a");
auto e = p->lhs_expression();
ASSERT_FALSE(p->has_error()) << p->error();
ASSERT_FALSE(e.errored);
EXPECT_TRUE(e.matched);
ASSERT_NE(e.value, nullptr);
- std::vector<ast::UnaryOp> results = {ast::UnaryOp::kIndirection, ast::UnaryOp::kAddressOf,
- ast::UnaryOp::kIndirection, ast::UnaryOp::kIndirection,
- ast::UnaryOp::kAddressOf, ast::UnaryOp::kAddressOf,
- ast::UnaryOp::kIndirection};
+ std::vector<ast::UnaryOp> results = {
+ ast::UnaryOp::kIndirection, ast::UnaryOp::kAddressOf, ast::UnaryOp::kIndirection,
+ ast::UnaryOp::kIndirection, ast::UnaryOp::kIndirection, ast::UnaryOp::kIndirection,
+ ast::UnaryOp::kIndirection, ast::UnaryOp::kIndirection, ast::UnaryOp::kIndirection,
+ ast::UnaryOp::kIndirection, ast::UnaryOp::kAddressOf, ast::UnaryOp::kAddressOf,
+ ast::UnaryOp::kAddressOf, ast::UnaryOp::kAddressOf, ast::UnaryOp::kAddressOf,
+ ast::UnaryOp::kAddressOf, ast::UnaryOp::kIndirection};
auto* expr = e.value;
for (auto op : results) {
