src/compiler/DetectCallDepth.cpp

//
// 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;
}