path: root/libsolidity/analysis/ControlFlowAnalyzer.cpp

/*
    This file is part of solidity.

    solidity is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    solidity is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with solidity.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <libsolidity/analysis/ControlFlowAnalyzer.h>
#include <liblangutil/SourceLocation.h>

using namespace std;
using namespace langutil;
using namespace dev::solidity;

bool ControlFlowAnalyzer::analyze(ASTNode const& _astRoot)
{
    _astRoot.accept(*this);
    return Error::containsOnlyWarnings(m_errorReporter.errors());
}

bool ControlFlowAnalyzer::visit(FunctionDefinition const& _function)
{
    if (_function.isImplemented())
    {
        auto const& functionFlow = m_cfg.functionFlow(_function);
        checkUnassignedStorageReturnValues(_function, functionFlow.entry, functionFlow.exit);
    }
    return false;
}

set<VariableDeclaration const*> ControlFlowAnalyzer::variablesAssignedInNode(CFGNode const *node)
{
    set<VariableDeclaration const*> result;
    for (auto expression: node->block.expressions)
    {
        if (auto const* assignment = dynamic_cast<Assignment const*>(expression))
        {
            stack<Expression const*> expressions;
            expressions.push(&assignment->leftHandSide());
            while (!expressions.empty())
            {
                Expression const* expression = expressions.top();
                expressions.pop();

                if (auto const *tuple = dynamic_cast<TupleExpression const*>(expression))
                    for (auto const& component: tuple->components())
                        expressions.push(component.get());
                else if (auto const* identifier = dynamic_cast<Identifier const*>(expression))
                    if (auto const* variableDeclaration = dynamic_cast<VariableDeclaration const*>(
                        identifier->annotation().referencedDeclaration
                    ))
                        result.insert(variableDeclaration);
            }
        }
    }
    return result;
}

void ControlFlowAnalyzer::checkUnassignedStorageReturnValues(
    FunctionDefinition const& _function,
    CFGNode const* _functionEntry,
    CFGNode const* _functionExit
) const
{
    if (_function.returnParameterList()->parameters().empty())
        return;

    map<CFGNode const*, set<VariableDeclaration const*>> unassigned;

    {
        auto& unassignedAtFunctionEntry = unassigned[_functionEntry];
        for (auto const& returnParameter: _function.returnParameterList()->parameters())
            if (
                returnParameter->type()->dataStoredIn(DataLocation::Storage) ||
                returnParameter->type()->category() == Type::Category::Mapping
            )
                unassignedAtFunctionEntry.insert(returnParameter.get());
    }

    stack<CFGNode const*> nodesToTraverse;
    nodesToTraverse.push(_functionEntry);

    // walk all paths from entry with maximal set of unassigned return values
    while (!nodesToTraverse.empty())
    {
        auto node = nodesToTraverse.top();
        nodesToTraverse.pop();

        auto& unassignedAtNode = unassigned[node];

        if (node->block.returnStatement != nullptr)
            if (node->block.returnStatement->expression())
                unassignedAtNode.clear();
        if (!unassignedAtNode.empty())
        {
            // kill all return values to which a value is assigned
            for (auto const* variableDeclaration: variablesAssignedInNode(node))
                unassignedAtNode.erase(variableDeclaration);

            // kill all return values referenced in inline assembly
            // a reference is enough, checking whether there actually was an assignment might be overkill
            for (auto assembly: node->block.inlineAssemblyStatements)
                for (auto const& ref: assembly->annotation().externalReferences)
                    if (auto variableDeclaration = dynamic_cast<VariableDeclaration const*>(ref.second.declaration))
                        unassignedAtNode.erase(variableDeclaration);
        }

        for (auto const& exit: node->exits)
        {
            auto& unassignedAtExit = unassigned[exit];
            auto oldSize = unassignedAtExit.size();
            unassignedAtExit.insert(unassignedAtNode.begin(), unassignedAtNode.end());
            // (re)traverse an exit, if we are on a path with new unassigned return values to consider
            // this will terminate, since there is only a finite number of unassigned return values
            if (unassignedAtExit.size() > oldSize)
                nodesToTraverse.push(exit);
        }
    }

    if (!unassigned[_functionExit].empty())
    {
        vector<VariableDeclaration const*> unassignedOrdered(
            unassigned[_functionExit].begin(),
            unassigned[_functionExit].end()
        );
        sort(
            unassignedOrdered.begin(),
            unassignedOrdered.end(),
            [](VariableDeclaration const* lhs, VariableDeclaration const* rhs) -> bool {
                return lhs->id() < rhs->id();
            }
        );
        for (auto const* returnVal: unassignedOrdered)
        {
            SecondarySourceLocation ssl;
            for (CFGNode* lastNodeBeforeExit: _functionExit->entries)
                if (unassigned[lastNodeBeforeExit].count(returnVal))
                {
                    if (!!lastNodeBeforeExit->block.returnStatement)
                        ssl.append("Problematic return:", lastNodeBeforeExit->block.returnStatement->location());
                    else
                        ssl.append("Problematic end of function:", _function.location());
                }

            m_errorReporter.typeError(
                returnVal->location(),
                ssl,
                "This variable is of storage pointer type and might be returned without assignment and "
                "could be used uninitialized. Assign the variable (potentially from itself) "
                "to fix this error."
            );
        }
    }
}