From 04d792fb7510e328f508bc81379ca15791af93e7 Mon Sep 17 00:00:00 2001
From: Dan Sinclair <dsinclair@chromium.org>
Date: Wed, 7 Mar 2018 20:44:47 +0000
Subject: [formcalc] Consider width along with depth of tree

When building the formcalc parser trees we need to limit on width along
with depth. It's possible to generate a tree of a single depth but is
more then 20k nodes wide. This will eventuall cause stack overflow
issues.

This CL re-uses the depth check for the grammar expressions in which
we're extending the width of the tree we count that against our depth
check.

Bug: chromium:813346
Change-Id: I01f6567a75776a75374465eacc1ff546db46cac1
Reviewed-on: https://pdfium-review.googlesource.com/28170
Reviewed-by: Ryan Harrison <rharrison@chromium.org>
Reviewed-by: Henrique Nakashima <hnakashima@chromium.org>
Commit-Queue: dsinclair <dsinclair@chromium.org>
---
 xfa/fxfa/fm2js/cxfa_fmparser.cpp          | 31 ++++++++++++++++++++++++++-----
 xfa/fxfa/fm2js/cxfa_fmparser_unittest.cpp | 19 +++++++++++++++++++
 2 files changed, 45 insertions(+), 5 deletions(-)

diff --git a/xfa/fxfa/fm2js/cxfa_fmparser.cpp b/xfa/fxfa/fm2js/cxfa_fmparser.cpp
index 20e0fa6d1c..5079ab110e 100644
--- a/xfa/fxfa/fm2js/cxfa_fmparser.cpp
+++ b/xfa/fxfa/fm2js/cxfa_fmparser.cpp
@@ -273,6 +273,9 @@ CXFA_FMParser::ParseLogicalOrExpression() {
 
   // TODO(dsinclair): Is this for() needed?
   for (;;) {
+    if (!IncrementParseDepthAndCheck())
+      return nullptr;
+
     switch (m_token.m_type) {
       case TOKor:
       case TOKksor: {
@@ -310,6 +313,9 @@ CXFA_FMParser::ParseLogicalAndExpression() {
 
   // TODO(dsinclair): Is this for() needed?
   for (;;) {
+    if (!IncrementParseDepthAndCheck())
+      return nullptr;
+
     switch (m_token.m_type) {
       case TOKand:
       case TOKksand: {
@@ -346,32 +352,38 @@ CXFA_FMParser::ParseEqualityExpression() {
 
   // TODO(dsinclair): Is this for() needed?
   for (;;) {
-    std::unique_ptr<CXFA_FMSimpleExpression> e2;
+    if (!IncrementParseDepthAndCheck())
+      return nullptr;
+
     switch (m_token.m_type) {
       case TOKeq:
-      case TOKkseq:
+      case TOKkseq: {
         if (!NextToken())
           return nullptr;
 
-        e2 = ParseRelationalExpression();
+        std::unique_ptr<CXFA_FMSimpleExpression> e2 =
+            ParseRelationalExpression();
         if (!e2)
           return nullptr;
 
         e1 = pdfium::MakeUnique<CXFA_FMEqualExpression>(TOKeq, std::move(e1),
                                                         std::move(e2));
         continue;
+      }
       case TOKne:
-      case TOKksne:
+      case TOKksne: {
         if (!NextToken())
           return nullptr;
 
-        e2 = ParseRelationalExpression();
+        std::unique_ptr<CXFA_FMSimpleExpression> e2 =
+            ParseRelationalExpression();
         if (!e2)
           return nullptr;
 
         e1 = pdfium::MakeUnique<CXFA_FMNotEqualExpression>(TOKne, std::move(e1),
                                                            std::move(e2));
         continue;
+      }
       default:
         break;
     }
@@ -394,6 +406,9 @@ CXFA_FMParser::ParseRelationalExpression() {
 
   // TODO(dsinclair): Is this for() needed?
   for (;;) {
+    if (!IncrementParseDepthAndCheck())
+      return nullptr;
+
     std::unique_ptr<CXFA_FMSimpleExpression> e2;
     switch (m_token.m_type) {
       case TOKlt:
@@ -466,6 +481,9 @@ CXFA_FMParser::ParseAddtiveExpression() {
 
   // TODO(dsinclair): Is this for() needed?
   for (;;) {
+    if (!IncrementParseDepthAndCheck())
+      return nullptr;
+
     std::unique_ptr<CXFA_FMSimpleExpression> e2;
     switch (m_token.m_type) {
       case TOKplus:
@@ -512,6 +530,9 @@ CXFA_FMParser::ParseMultiplicativeExpression() {
 
   // TODO(dsinclair): Is this for() needed?
   for (;;) {
+    if (!IncrementParseDepthAndCheck())
+      return nullptr;
+
     std::unique_ptr<CXFA_FMSimpleExpression> e2;
     switch (m_token.m_type) {
       case TOKmul:
diff --git a/xfa/fxfa/fm2js/cxfa_fmparser_unittest.cpp b/xfa/fxfa/fm2js/cxfa_fmparser_unittest.cpp
index 5ee27b189e..1eedebfcca 100644
--- a/xfa/fxfa/fm2js/cxfa_fmparser_unittest.cpp
+++ b/xfa/fxfa/fm2js/cxfa_fmparser_unittest.cpp
@@ -238,3 +238,22 @@ TEST(CXFA_FMParserTest, ParseBadElseIfExpression) {
   ASSERT_TRUE(ast == nullptr);
   EXPECT_TRUE(parser->HasError());
 }
+
+TEST(CXFA_FMParserTest, ParseDepthWithWideTree) {
+  const wchar_t input[] = {L"a <> b <> c <> d <> e <> f <> g <> h <> i <> j"};
+
+  {
+    auto parser = pdfium::MakeUnique<CXFA_FMParser>(input);
+    std::unique_ptr<CXFA_FMAST> ast = parser->Parse();
+    ASSERT_TRUE(ast);
+    EXPECT_TRUE(!parser->HasError());
+  }
+
+  {
+    auto parser = pdfium::MakeUnique<CXFA_FMParser>(input);
+    parser->SetMaxParseDepthForTest(5);
+    std::unique_ptr<CXFA_FMAST> ast = parser->Parse();
+    ASSERT_TRUE(ast == nullptr);
+    EXPECT_TRUE(parser->HasError());
+  }
+}
-- 
cgit v1.2.3