commit cdc65b52c615c41c3d31ee509b844643c1d9513a
author Daniel Hosseinian <dhoss@chromium.org> Thu Feb 27 08:10:47 2020 +0000
committer Chromium commit bot <commit-bot@chromium.org> Thu Feb 27 08:10:47 2020 +0000
tree b9001f01007f20171c178201bb4b0dcf41da49cb
parent c388093a05fa250e588ae0a4ba0b6ccab65486d9

Space-efficiently destroy chained CXFA_FMSimpleExpression instances

Destroy CXFA_FMChainableExpression objects iteratively in linear time
and constant space.

Currently, chainable CXFA_FMSimpleExpression objects are destroyed
recursively, allowing the stack to overflow if the chain is long
enough. This change allows for efficient destruction without the need
to lower the FM2JS parser depth limit.

Fixed: chromium:1052724
Change-Id: I44753693910230d961c8d4ea9aeb7a6305f9d1e5
Reviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/66990
Commit-Queue: Daniel Hosseinian <dhoss@chromium.org>
Reviewed-by: Lei Zhang <thestig@chromium.org>

xfa/fxfa/fm2js/cxfa_fmsimpleexpression.cpp

diff --git a/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.cpp b/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.cpp
index ac91d94..e29e5dc 100644
--- a/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.cpp
+++ b/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.cpp
@@ -89,7 +89,10 @@
       m_pExp1(std::move(pExp1)),
       m_pExp2(std::move(pExp2)) {}
 
-CXFA_FMChainableExpression::~CXFA_FMChainableExpression() = default;
+CXFA_FMChainableExpression::~CXFA_FMChainableExpression() {
+  DeleteChain(std::move(m_pExp1));
+  DeleteChain(std::move(m_pExp2));
+}
 
 CXFA_FMSimpleExpression* CXFA_FMChainableExpression::GetFirstExpression() {
   return m_pExp1.get();
@@ -99,6 +102,40 @@
   return m_pExp2.get();
 }
 
+// static
+void CXFA_FMChainableExpression::DeleteChain(
+    std::unique_ptr<CXFA_FMSimpleExpression> pRoot) {
+  while (pRoot && pRoot->chainable()) {
+    auto* pRootChain = static_cast<CXFA_FMChainableExpression*>(pRoot.get());
+
+    // If either child is not a chainable expression (i.e. a leaf node), simply
+    // delete it.
+    if (pRootChain->m_pExp1 && !pRootChain->m_pExp1->chainable())
+      pRootChain->m_pExp1.reset();
+    if (pRootChain->m_pExp2 && !pRootChain->m_pExp2->chainable())
+      pRootChain->m_pExp2.reset();
+
+    // If the root is missing either child, delete the root and promote the only
+    // child to the root.
+    if (!pRootChain->m_pExp1) {
+      pRoot = std::move(pRootChain->m_pExp2);
+      continue;
+    }
+    if (!pRootChain->m_pExp2) {
+      pRoot = std::move(pRootChain->m_pExp1);
+      continue;
+    }
+
+    // Otherwise, perform a right tree rotation.
+    std::unique_ptr<CXFA_FMSimpleExpression> pPivot(
+        std::move(pRootChain->m_pExp1));
+    auto* pPivotChain = static_cast<CXFA_FMChainableExpression*>(pPivot.get());
+    pRootChain->m_pExp1 = std::move(pPivotChain->m_pExp2);
+    pPivotChain->m_pExp2 = std::move(pRoot);
+    pRoot = std::move(pPivot);
+  }
+}
+
 CXFA_FMNullExpression::CXFA_FMNullExpression()
     : CXFA_FMSimpleExpression(TOKnull) {}
 

xfa/fxfa/fm2js/cxfa_fmsimpleexpression.h

diff --git a/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.h b/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.h
index 49e2560..a970029 100644
--- a/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.h
+++ b/xfa/fxfa/fm2js/cxfa_fmsimpleexpression.h
@@ -54,6 +54,10 @@
   CXFA_FMSimpleExpression* GetSecondExpression();
 
  private:
+  // Iteratively delete a chainable expression tree in linear time and constant
+  // space.
+  static void DeleteChain(std::unique_ptr<CXFA_FMSimpleExpression> pRoot);
+
   std::unique_ptr<CXFA_FMSimpleExpression> m_pExp1;
   std::unique_ptr<CXFA_FMSimpleExpression> m_pExp2;
 };