michael@0: //
michael@0: // Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #include "compiler/DetectCallDepth.h"
michael@0: #include "compiler/InfoSink.h"
michael@0: 
michael@0: DetectCallDepth::FunctionNode::FunctionNode(const TString& fname)
michael@0:     : name(fname),
michael@0:       visit(PreVisit)
michael@0: {
michael@0: }
michael@0: 
michael@0: const TString& DetectCallDepth::FunctionNode::getName() const
michael@0: {
michael@0:     return name;
michael@0: }
michael@0: 
michael@0: void DetectCallDepth::FunctionNode::addCallee(
michael@0:     DetectCallDepth::FunctionNode* callee)
michael@0: {
michael@0:     for (size_t i = 0; i < callees.size(); ++i) {
michael@0:         if (callees[i] == callee)
michael@0:             return;
michael@0:     }
michael@0:     callees.push_back(callee);
michael@0: }
michael@0: 
michael@0: int DetectCallDepth::FunctionNode::detectCallDepth(DetectCallDepth* detectCallDepth, int depth)
michael@0: {
michael@0:     ASSERT(visit == PreVisit);
michael@0:     ASSERT(detectCallDepth);
michael@0: 
michael@0:     int maxDepth = depth;
michael@0:     visit = InVisit;
michael@0:     for (size_t i = 0; i < callees.size(); ++i) {
michael@0:         switch (callees[i]->visit) {
michael@0:             case InVisit:
michael@0:                 // cycle detected, i.e., recursion detected.
michael@0:                 return kInfiniteCallDepth;
michael@0:             case PostVisit:
michael@0:                 break;
michael@0:             case PreVisit: {
michael@0:                 // Check before we recurse so we don't go too depth
michael@0:                 if (detectCallDepth->checkExceedsMaxDepth(depth))
michael@0:                     return depth;
michael@0:                 int callDepth = callees[i]->detectCallDepth(detectCallDepth, depth + 1);
michael@0:                 // Check after we recurse so we can exit immediately and provide info.
michael@0:                 if (detectCallDepth->checkExceedsMaxDepth(callDepth)) {
michael@0:                     detectCallDepth->getInfoSink().info << "<-" << callees[i]->getName();
michael@0:                     return callDepth;
michael@0:                 }
michael@0:                 maxDepth = std::max(callDepth, maxDepth);
michael@0:                 break;
michael@0:             }
michael@0:             default:
michael@0:                 UNREACHABLE();
michael@0:                 break;
michael@0:         }
michael@0:     }
michael@0:     visit = PostVisit;
michael@0:     return maxDepth;
michael@0: }
michael@0: 
michael@0: void DetectCallDepth::FunctionNode::reset()
michael@0: {
michael@0:     visit = PreVisit;
michael@0: }
michael@0: 
michael@0: DetectCallDepth::DetectCallDepth(TInfoSink& infoSink, bool limitCallStackDepth, int maxCallStackDepth)
michael@0:     : TIntermTraverser(true, false, true, false),
michael@0:       currentFunction(NULL),
michael@0:       infoSink(infoSink),
michael@0:       maxDepth(limitCallStackDepth ? maxCallStackDepth : FunctionNode::kInfiniteCallDepth)
michael@0: {
michael@0: }
michael@0: 
michael@0: DetectCallDepth::~DetectCallDepth()
michael@0: {
michael@0:     for (size_t i = 0; i < functions.size(); ++i)
michael@0:         delete functions[i];
michael@0: }
michael@0: 
michael@0: bool DetectCallDepth::visitAggregate(Visit visit, TIntermAggregate* node)
michael@0: {
michael@0:     switch (node->getOp())
michael@0:     {
michael@0:         case EOpPrototype:
michael@0:             // Function declaration.
michael@0:             // Don't add FunctionNode here because node->getName() is the
michael@0:             // unmangled function name.
michael@0:             break;
michael@0:         case EOpFunction: {
michael@0:             // Function definition.
michael@0:             if (visit == PreVisit) {
michael@0:                 currentFunction = findFunctionByName(node->getName());
michael@0:                 if (currentFunction == NULL) {
michael@0:                     currentFunction = new FunctionNode(node->getName());
michael@0:                     functions.push_back(currentFunction);
michael@0:                 }
michael@0:             } else if (visit == PostVisit) {
michael@0:                 currentFunction = NULL;
michael@0:             }
michael@0:             break;
michael@0:         }
michael@0:         case EOpFunctionCall: {
michael@0:             // Function call.
michael@0:             if (visit == PreVisit) {
michael@0:                 FunctionNode* func = findFunctionByName(node->getName());
michael@0:                 if (func == NULL) {
michael@0:                     func = new FunctionNode(node->getName());
michael@0:                     functions.push_back(func);
michael@0:                 }
michael@0:                 if (currentFunction)
michael@0:                     currentFunction->addCallee(func);
michael@0:             }
michael@0:             break;
michael@0:         }
michael@0:         default:
michael@0:             break;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool DetectCallDepth::checkExceedsMaxDepth(int depth)
michael@0: {
michael@0:     return depth >= maxDepth;
michael@0: }
michael@0: 
michael@0: void DetectCallDepth::resetFunctionNodes()
michael@0: {
michael@0:     for (size_t i = 0; i < functions.size(); ++i) {
michael@0:         functions[i]->reset();
michael@0:     }
michael@0: }
michael@0: 
michael@0: DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepthForFunction(FunctionNode* func)
michael@0: {
michael@0:     currentFunction = NULL;
michael@0:     resetFunctionNodes();
michael@0: 
michael@0:     int maxCallDepth = func->detectCallDepth(this, 1);
michael@0: 
michael@0:     if (maxCallDepth == FunctionNode::kInfiniteCallDepth)
michael@0:         return kErrorRecursion;
michael@0: 
michael@0:     if (maxCallDepth >= maxDepth)
michael@0:         return kErrorMaxDepthExceeded;
michael@0: 
michael@0:     return kErrorNone;
michael@0: }
michael@0: 
michael@0: DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepth()
michael@0: {
michael@0:     if (maxDepth != FunctionNode::kInfiniteCallDepth) {
michael@0:         // Check all functions because the driver may fail on them
michael@0:         // TODO: Before detectingRecursion, strip unused functions.
michael@0:         for (size_t i = 0; i < functions.size(); ++i) {
michael@0:             ErrorCode error = detectCallDepthForFunction(functions[i]);
michael@0:             if (error != kErrorNone)
michael@0:                 return error;
michael@0:         }
michael@0:     } else {
michael@0:         FunctionNode* main = findFunctionByName("main(");
michael@0:         if (main == NULL)
michael@0:             return kErrorMissingMain;
michael@0: 
michael@0:         return detectCallDepthForFunction(main);
michael@0:     }
michael@0: 
michael@0:     return kErrorNone;
michael@0: }
michael@0: 
michael@0: DetectCallDepth::FunctionNode* DetectCallDepth::findFunctionByName(
michael@0:     const TString& name)
michael@0: {
michael@0:     for (size_t i = 0; i < functions.size(); ++i) {
michael@0:         if (functions[i]->getName() == name)
michael@0:             return functions[i];
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: