Add expression complexity and call stack depth limits.
git-svn-id: https://angleproject.googlecode.com/svn/trunk@2242 736b8ea6-26fd-11df-bfd4-992fa37f6226
TRAC #23333
Authored-by: gman@chromium.org
Signed-off-by: Shannon Woods
Signed-off-by Nicolas Capens
Merged-by: Jamie Madill
Conflicts:
src/common/version.h
diff --git a/src/compiler/DetectCallDepth.cpp b/src/compiler/DetectCallDepth.cpp
new file mode 100644
index 0000000..60df52c
--- /dev/null
+++ b/src/compiler/DetectCallDepth.cpp
@@ -0,0 +1,185 @@
+//
+// Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+
+#include "compiler/DetectCallDepth.h"
+#include "compiler/InfoSink.h"
+
+DetectCallDepth::FunctionNode::FunctionNode(const TString& fname)
+ : name(fname),
+ visit(PreVisit)
+{
+}
+
+const TString& DetectCallDepth::FunctionNode::getName() const
+{
+ return name;
+}
+
+void DetectCallDepth::FunctionNode::addCallee(
+ DetectCallDepth::FunctionNode* callee)
+{
+ for (size_t i = 0; i < callees.size(); ++i) {
+ if (callees[i] == callee)
+ return;
+ }
+ callees.push_back(callee);
+}
+
+int DetectCallDepth::FunctionNode::detectCallDepth(DetectCallDepth* detectCallDepth, int depth)
+{
+ ASSERT(visit == PreVisit);
+ ASSERT(detectCallDepth);
+
+ int maxDepth = depth;
+ visit = InVisit;
+ for (size_t i = 0; i < callees.size(); ++i) {
+ switch (callees[i]->visit) {
+ case InVisit:
+ // cycle detected, i.e., recursion detected.
+ return kInfiniteCallDepth;
+ case PostVisit:
+ break;
+ case PreVisit: {
+ // Check before we recurse so we don't go too depth
+ if (detectCallDepth->checkExceedsMaxDepth(depth))
+ return depth;
+ int callDepth = callees[i]->detectCallDepth(detectCallDepth, depth + 1);
+ // Check after we recurse so we can exit immediately and provide info.
+ if (detectCallDepth->checkExceedsMaxDepth(callDepth)) {
+ detectCallDepth->getInfoSink().info << "<-" << callees[i]->getName();
+ return callDepth;
+ }
+ maxDepth = std::max(callDepth, maxDepth);
+ break;
+ }
+ default:
+ UNREACHABLE();
+ break;
+ }
+ }
+ visit = PostVisit;
+ return maxDepth;
+}
+
+void DetectCallDepth::FunctionNode::reset()
+{
+ visit = PreVisit;
+}
+
+DetectCallDepth::DetectCallDepth(TInfoSink& infoSink, bool limitCallStackDepth, int maxCallStackDepth)
+ : TIntermTraverser(true, false, true, false),
+ currentFunction(NULL),
+ infoSink(infoSink),
+ maxDepth(limitCallStackDepth ? maxCallStackDepth : FunctionNode::kInfiniteCallDepth)
+{
+}
+
+DetectCallDepth::~DetectCallDepth()
+{
+ for (size_t i = 0; i < functions.size(); ++i)
+ delete functions[i];
+}
+
+bool DetectCallDepth::visitAggregate(Visit visit, TIntermAggregate* node)
+{
+ switch (node->getOp())
+ {
+ case EOpPrototype:
+ // Function declaration.
+ // Don't add FunctionNode here because node->getName() is the
+ // unmangled function name.
+ break;
+ case EOpFunction: {
+ // Function definition.
+ if (visit == PreVisit) {
+ currentFunction = findFunctionByName(node->getName());
+ if (currentFunction == NULL) {
+ currentFunction = new FunctionNode(node->getName());
+ functions.push_back(currentFunction);
+ }
+ } else if (visit == PostVisit) {
+ currentFunction = NULL;
+ }
+ break;
+ }
+ case EOpFunctionCall: {
+ // Function call.
+ if (visit == PreVisit) {
+ FunctionNode* func = findFunctionByName(node->getName());
+ if (func == NULL) {
+ func = new FunctionNode(node->getName());
+ functions.push_back(func);
+ }
+ if (currentFunction)
+ currentFunction->addCallee(func);
+ }
+ break;
+ }
+ default:
+ break;
+ }
+ return true;
+}
+
+bool DetectCallDepth::checkExceedsMaxDepth(int depth)
+{
+ return depth >= maxDepth;
+}
+
+void DetectCallDepth::resetFunctionNodes()
+{
+ for (size_t i = 0; i < functions.size(); ++i) {
+ functions[i]->reset();
+ }
+}
+
+DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepthForFunction(FunctionNode* func)
+{
+ currentFunction = NULL;
+ resetFunctionNodes();
+
+ int maxCallDepth = func->detectCallDepth(this, 1);
+
+ if (maxCallDepth == FunctionNode::kInfiniteCallDepth)
+ return kErrorRecursion;
+
+ if (maxCallDepth >= maxDepth)
+ return kErrorMaxDepthExceeded;
+
+ return kErrorNone;
+}
+
+DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepth()
+{
+ if (maxDepth != FunctionNode::kInfiniteCallDepth) {
+ // Check all functions because the driver may fail on them
+ // TODO: Before detectingRecursion, strip unused functions.
+ for (size_t i = 0; i < functions.size(); ++i) {
+ ErrorCode error = detectCallDepthForFunction(functions[i]);
+ if (error != kErrorNone)
+ return error;
+ }
+ } else {
+ FunctionNode* main = findFunctionByName("main(");
+ if (main == NULL)
+ return kErrorMissingMain;
+
+ return detectCallDepthForFunction(main);
+ }
+
+ return kErrorNone;
+}
+
+DetectCallDepth::FunctionNode* DetectCallDepth::findFunctionByName(
+ const TString& name)
+{
+ for (size_t i = 0; i < functions.size(); ++i) {
+ if (functions[i]->getName() == name)
+ return functions[i];
+ }
+ return NULL;
+}
+