//
// Copyright 2002 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/translator/tree_util/IntermTraverse.h"

#include "compiler/translator/Compiler.h"
#include "compiler/translator/InfoSink.h"
#include "compiler/translator/SymbolTable.h"
#include "compiler/translator/tree_util/IntermNode_util.h"
#include "compiler/translator/util.h"

namespace sh
{

// Traverse the intermediate representation tree, and call a node type specific visit function for
// each node. Traversal is done recursively through the node member function traverse(). Nodes with
// children can have their whole subtree skipped if preVisit is turned on and the type specific
// function returns false.
template <typename T>
void TIntermTraverser::traverse(T *node)
{
    ScopedNodeInTraversalPath addToPath(this, node);
    if (!addToPath.isWithinDepthLimit())
        return;

    bool visit = true;

    // Visit the node before children if pre-visiting.
    if (preVisit)
        visit = node->visit(PreVisit, this);

    if (visit)
    {
        size_t childIndex = 0;
        size_t childCount = node->getChildCount();

        while (childIndex < childCount && visit)
        {
            mCurrentChildIndex = childIndex;
            node->getChildNode(childIndex)->traverse(this);
            mCurrentChildIndex = childIndex;

            if (inVisit && childIndex != childCount - 1)
            {
                visit = node->visit(InVisit, this);
            }
            ++childIndex;
        }

        if (visit && postVisit)
            node->visit(PostVisit, this);
    }
}

// Instantiate template for RewriteAtomicFunctionExpressions, in case this gets inlined thus not
// exported from the TU.
template void TIntermTraverser::traverse(TIntermNode *);

void TIntermNode::traverse(TIntermTraverser *it)
{
    it->traverse(this);
}

void TIntermSymbol::traverse(TIntermTraverser *it)
{
    TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
    it->visitSymbol(this);
}

void TIntermConstantUnion::traverse(TIntermTraverser *it)
{
    TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
    it->visitConstantUnion(this);
}

void TIntermFunctionPrototype::traverse(TIntermTraverser *it)
{
    TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
    it->visitFunctionPrototype(this);
}

void TIntermBinary::traverse(TIntermTraverser *it)
{
    it->traverseBinary(this);
}

void TIntermUnary::traverse(TIntermTraverser *it)
{
    it->traverseUnary(this);
}

void TIntermFunctionDefinition::traverse(TIntermTraverser *it)
{
    it->traverseFunctionDefinition(this);
}

void TIntermBlock::traverse(TIntermTraverser *it)
{
    it->traverseBlock(this);
}

void TIntermAggregate::traverse(TIntermTraverser *it)
{
    it->traverseAggregate(this);
}

void TIntermLoop::traverse(TIntermTraverser *it)
{
    it->traverseLoop(this);
}

void TIntermPreprocessorDirective::traverse(TIntermTraverser *it)
{
    it->visitPreprocessorDirective(this);
}

bool TIntermSymbol::visit(Visit visit, TIntermTraverser *it)
{
    it->visitSymbol(this);
    return false;
}

bool TIntermConstantUnion::visit(Visit visit, TIntermTraverser *it)
{
    it->visitConstantUnion(this);
    return false;
}

bool TIntermFunctionPrototype::visit(Visit visit, TIntermTraverser *it)
{
    it->visitFunctionPrototype(this);
    return false;
}

bool TIntermFunctionDefinition::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitFunctionDefinition(visit, this);
}

bool TIntermUnary::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitUnary(visit, this);
}

bool TIntermSwizzle::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitSwizzle(visit, this);
}

bool TIntermBinary::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitBinary(visit, this);
}

bool TIntermTernary::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitTernary(visit, this);
}

bool TIntermAggregate::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitAggregate(visit, this);
}

bool TIntermDeclaration::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitDeclaration(visit, this);
}

bool TIntermGlobalQualifierDeclaration::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitGlobalQualifierDeclaration(visit, this);
}

bool TIntermBlock::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitBlock(visit, this);
}

bool TIntermIfElse::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitIfElse(visit, this);
}

bool TIntermLoop::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitLoop(visit, this);
}

bool TIntermBranch::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitBranch(visit, this);
}

bool TIntermSwitch::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitSwitch(visit, this);
}

bool TIntermCase::visit(Visit visit, TIntermTraverser *it)
{
    return it->visitCase(visit, this);
}

bool TIntermPreprocessorDirective::visit(Visit visit, TIntermTraverser *it)
{
    it->visitPreprocessorDirective(this);
    return false;
}

TIntermTraverser::TIntermTraverser(bool preVisit,
                                   bool inVisit,
                                   bool postVisit,
                                   TSymbolTable *symbolTable)
    : preVisit(preVisit),
      inVisit(inVisit),
      postVisit(postVisit),
      mMaxDepth(0),
      mMaxAllowedDepth(std::numeric_limits<int>::max()),
      mInGlobalScope(true),
      mSymbolTable(symbolTable),
      mCurrentChildIndex(0)
{
    // Only enabling inVisit is not supported.
    ASSERT(!(inVisit && !preVisit && !postVisit));
}

TIntermTraverser::~TIntermTraverser() {}

void TIntermTraverser::setMaxAllowedDepth(int depth)
{
    mMaxAllowedDepth = depth;
}

const TIntermBlock *TIntermTraverser::getParentBlock() const
{
    if (!mParentBlockStack.empty())
    {
        return mParentBlockStack.back().node;
    }
    return nullptr;
}

void TIntermTraverser::pushParentBlock(TIntermBlock *node)
{
    mParentBlockStack.push_back(ParentBlock(node, 0));
}

void TIntermTraverser::incrementParentBlockPos()
{
    ++mParentBlockStack.back().pos;
}

void TIntermTraverser::popParentBlock()
{
    ASSERT(!mParentBlockStack.empty());
    mParentBlockStack.pop_back();
}

void TIntermTraverser::insertStatementsInParentBlock(const TIntermSequence &insertions)
{
    TIntermSequence emptyInsertionsAfter;
    insertStatementsInParentBlock(insertions, emptyInsertionsAfter);
}

void TIntermTraverser::insertStatementsInParentBlock(const TIntermSequence &insertionsBefore,
                                                     const TIntermSequence &insertionsAfter)
{
    ASSERT(!mParentBlockStack.empty());
    ParentBlock &parentBlock = mParentBlockStack.back();
    if (mPath.back() == parentBlock.node)
    {
        ASSERT(mParentBlockStack.size() >= 2u);
        // The current node is a block node, so the parent block is not the topmost one in the block
        // stack, but the one below that.
        parentBlock = mParentBlockStack.at(mParentBlockStack.size() - 2u);
    }
    NodeInsertMultipleEntry insert(parentBlock.node, parentBlock.pos, insertionsBefore,
                                   insertionsAfter);
    mInsertions.push_back(insert);
}

void TIntermTraverser::insertStatementInParentBlock(TIntermNode *statement)
{
    TIntermSequence insertions;
    insertions.push_back(statement);
    insertStatementsInParentBlock(insertions);
}

void TIntermTraverser::insertStatementsInBlockAtPosition(TIntermBlock *parent,
                                                         size_t position,
                                                         const TIntermSequence &insertionsBefore,
                                                         const TIntermSequence &insertionsAfter)
{
    ASSERT(parent);
    ASSERT(position >= 0);
    ASSERT(position < parent->getChildCount());

    mInsertions.emplace_back(parent, position, insertionsBefore, insertionsAfter);
}

void TLValueTrackingTraverser::setInFunctionCallOutParameter(bool inOutParameter)
{
    mInFunctionCallOutParameter = inOutParameter;
}

bool TLValueTrackingTraverser::isInFunctionCallOutParameter() const
{
    return mInFunctionCallOutParameter;
}

void TIntermTraverser::traverseBinary(TIntermBinary *node)
{
    traverse(node);
}

void TLValueTrackingTraverser::traverseBinary(TIntermBinary *node)
{
    ScopedNodeInTraversalPath addToPath(this, node);
    if (!addToPath.isWithinDepthLimit())
        return;

    bool visit = true;

    // visit the node before children if pre-visiting.
    if (preVisit)
        visit = node->visit(PreVisit, this);

    // Visit the children, in the right order.
    if (visit)
    {
        if (node->isAssignment())
        {
            ASSERT(!isLValueRequiredHere());
            setOperatorRequiresLValue(true);
        }

        node->getLeft()->traverse(this);

        if (node->isAssignment())
            setOperatorRequiresLValue(false);

        if (inVisit)
            visit = node->visit(InVisit, this);

        if (visit)
        {
            // Some binary operations like indexing can be inside an expression which must be an
            // l-value.
            bool parentOperatorRequiresLValue     = operatorRequiresLValue();
            bool parentInFunctionCallOutParameter = isInFunctionCallOutParameter();

            // Index is not required to be an l-value even when the surrounding expression is
            // required to be an l-value.
            TOperator op = node->getOp();
            if (op == EOpIndexDirect || op == EOpIndexDirectInterfaceBlock ||
                op == EOpIndexDirectStruct || op == EOpIndexIndirect)
            {
                setOperatorRequiresLValue(false);
                setInFunctionCallOutParameter(false);
            }

            node->getRight()->traverse(this);

            setOperatorRequiresLValue(parentOperatorRequiresLValue);
            setInFunctionCallOutParameter(parentInFunctionCallOutParameter);

            // Visit the node after the children, if requested and the traversal
            // hasn't been cancelled yet.
            if (postVisit)
                visit = node->visit(PostVisit, this);
        }
    }
}

void TIntermTraverser::traverseUnary(TIntermUnary *node)
{
    traverse(node);
}

void TLValueTrackingTraverser::traverseUnary(TIntermUnary *node)
{
    ScopedNodeInTraversalPath addToPath(this, node);
    if (!addToPath.isWithinDepthLimit())
        return;

    bool visit = true;

    if (preVisit)
        visit = node->visit(PreVisit, this);

    if (visit)
    {
        ASSERT(!operatorRequiresLValue());
        switch (node->getOp())
        {
            case EOpPostIncrement:
            case EOpPostDecrement:
            case EOpPreIncrement:
            case EOpPreDecrement:
                setOperatorRequiresLValue(true);
                break;
            default:
                break;
        }

        node->getOperand()->traverse(this);

        setOperatorRequiresLValue(false);

        if (postVisit)
            visit = node->visit(PostVisit, this);
    }
}

// Traverse a function definition node. This keeps track of global scope.
void TIntermTraverser::traverseFunctionDefinition(TIntermFunctionDefinition *node)
{
    ScopedNodeInTraversalPath addToPath(this, node);
    if (!addToPath.isWithinDepthLimit())
        return;

    bool visit = true;

    if (preVisit)
        visit = node->visit(PreVisit, this);

    if (visit)
    {
        mCurrentChildIndex = 0;
        node->getFunctionPrototype()->traverse(this);
        mCurrentChildIndex = 0;

        if (inVisit)
            visit = node->visit(InVisit, this);
        if (visit)
        {
            mInGlobalScope     = false;
            mCurrentChildIndex = 1;
            node->getBody()->traverse(this);
            mCurrentChildIndex = 1;
            mInGlobalScope     = true;
            if (postVisit)
                visit = node->visit(PostVisit, this);
        }
    }
}

// Traverse a block node. This keeps track of the position of traversed child nodes within the block
// so that nodes may be inserted before or after them.
void TIntermTraverser::traverseBlock(TIntermBlock *node)
{
    ScopedNodeInTraversalPath addToPath(this, node);
    if (!addToPath.isWithinDepthLimit())
        return;

    pushParentBlock(node);

    bool visit = true;

    TIntermSequence *sequence = node->getSequence();

    if (preVisit)
        visit = node->visit(PreVisit, this);

    if (visit)
    {
        for (size_t childIndex = 0; childIndex < sequence->size(); ++childIndex)
        {
            TIntermNode *child = (*sequence)[childIndex];
            if (visit)
            {
                mCurrentChildIndex = childIndex;
                child->traverse(this);
                mCurrentChildIndex = childIndex;

                if (inVisit)
                {
                    if (child != sequence->back())
                        visit = node->visit(InVisit, this);
                }

                incrementParentBlockPos();
            }
        }

        if (visit && postVisit)
            visit = node->visit(PostVisit, this);
    }

    popParentBlock();
}

void TIntermTraverser::traverseAggregate(TIntermAggregate *node)
{
    traverse(node);
}

bool TIntermTraverser::CompareInsertion(const NodeInsertMultipleEntry &a,
                                        const NodeInsertMultipleEntry &b)
{
    if (a.parent != b.parent)
    {
        return a.parent < b.parent;
    }
    return a.position < b.position;
}

bool TIntermTraverser::updateTree(TCompiler *compiler, TIntermNode *node)
{
    // Sort the insertions so that insertion position is increasing and same position insertions are
    // not reordered. The insertions are processed in reverse order so that multiple insertions to
    // the same parent node are handled correctly.
    std::stable_sort(mInsertions.begin(), mInsertions.end(), CompareInsertion);
    for (size_t ii = 0; ii < mInsertions.size(); ++ii)
    {
        // If two insertions are to the same position, insert them in the order they were specified.
        // The std::stable_sort call above will automatically guarantee this.
        const NodeInsertMultipleEntry &insertion = mInsertions[mInsertions.size() - ii - 1];
        ASSERT(insertion.parent);
        if (!insertion.insertionsAfter.empty())
        {
            bool inserted = insertion.parent->insertChildNodes(insertion.position + 1,
                                                               insertion.insertionsAfter);
            ASSERT(inserted);
        }
        if (!insertion.insertionsBefore.empty())
        {
            bool inserted =
                insertion.parent->insertChildNodes(insertion.position, insertion.insertionsBefore);
            ASSERT(inserted);
        }
    }
    for (size_t ii = 0; ii < mReplacements.size(); ++ii)
    {
        const NodeUpdateEntry &replacement = mReplacements[ii];
        ASSERT(replacement.parent);
        bool replaced =
            replacement.parent->replaceChildNode(replacement.original, replacement.replacement);
        ASSERT(replaced);

        // Make sure the precision is not accidentally dropped.  It's ok if the precision is not the
        // same, as the transformations are allowed to replace an expression with one that is
        // temporarily evaluated at a different (likely higher) precision.
        TIntermTyped *originalAsTyped = replacement.original->getAsTyped();
        TIntermTyped *replacementAsTyped =
            replacement.replacement ? replacement.replacement->getAsTyped() : nullptr;
        if (originalAsTyped != nullptr && replacementAsTyped != nullptr)
        {
            const TType &originalType    = originalAsTyped->getType();
            const TType &replacementType = replacementAsTyped->getType();
            ASSERT(!IsPrecisionApplicableToType(originalType.getBasicType()) ||
                   !IsPrecisionApplicableToType(replacementType.getBasicType()) ||
                   originalType.getPrecision() == EbpUndefined ||
                   replacementType.getPrecision() != EbpUndefined);
        }

        if (!replacement.originalBecomesChildOfReplacement)
        {
            // In AST traversing, a parent is visited before its children.
            // After we replace a node, if its immediate child is to
            // be replaced, we need to make sure we don't update the replaced
            // node; instead, we update the replacement node.
            for (size_t jj = ii + 1; jj < mReplacements.size(); ++jj)
            {
                NodeUpdateEntry &replacement2 = mReplacements[jj];
                if (replacement2.parent == replacement.original)
                    replacement2.parent = replacement.replacement;
            }
        }
    }
    for (size_t ii = 0; ii < mMultiReplacements.size(); ++ii)
    {
        const NodeReplaceWithMultipleEntry &replacement = mMultiReplacements[ii];
        ASSERT(replacement.parent);
        bool replaced = replacement.parent->replaceChildNodeWithMultiple(replacement.original,
                                                                         replacement.replacements);
        ASSERT(replaced);
    }

    clearReplacementQueue();

    return compiler->validateAST(node);
}

void TIntermTraverser::clearReplacementQueue()
{
    mReplacements.clear();
    mMultiReplacements.clear();
    mInsertions.clear();
}

void TIntermTraverser::queueReplacement(TIntermNode *replacement, OriginalNode originalStatus)
{
    queueReplacementWithParent(getParentNode(), mPath.back(), replacement, originalStatus);
}

void TIntermTraverser::queueReplacementWithParent(TIntermNode *parent,
                                                  TIntermNode *original,
                                                  TIntermNode *replacement,
                                                  OriginalNode originalStatus)
{
    bool originalBecomesChild = (originalStatus == OriginalNode::BECOMES_CHILD);
    mReplacements.push_back(NodeUpdateEntry(parent, original, replacement, originalBecomesChild));
}

void TIntermTraverser::queueAccessChainReplacement(TIntermTyped *replacement)
{
    uint32_t ancestorIndex  = 0;
    TIntermTyped *toReplace = nullptr;
    while (true)
    {
        TIntermNode *ancestor = getAncestorNode(ancestorIndex);
        ASSERT(ancestor != nullptr);

        TIntermBinary *asBinary = ancestor->getAsBinaryNode();
        if (asBinary == nullptr ||
            (asBinary->getOp() != EOpIndexDirect && asBinary->getOp() != EOpIndexIndirect))
        {
            break;
        }

        replacement = new TIntermBinary(asBinary->getOp(), replacement, asBinary->getRight());
        toReplace   = asBinary;

        ++ancestorIndex;
    }

    if (toReplace == nullptr)
    {
        queueReplacement(replacement, OriginalNode::IS_DROPPED);
    }
    else
    {
        queueReplacementWithParent(getAncestorNode(ancestorIndex), toReplace, replacement,
                                   OriginalNode::IS_DROPPED);
    }
}

TLValueTrackingTraverser::TLValueTrackingTraverser(bool preVisitIn,
                                                   bool inVisitIn,
                                                   bool postVisitIn,
                                                   TSymbolTable *symbolTable)
    : TIntermTraverser(preVisitIn, inVisitIn, postVisitIn, symbolTable),
      mOperatorRequiresLValue(false),
      mInFunctionCallOutParameter(false)
{
    ASSERT(symbolTable);
}

void TLValueTrackingTraverser::traverseAggregate(TIntermAggregate *node)
{
    ScopedNodeInTraversalPath addToPath(this, node);
    if (!addToPath.isWithinDepthLimit())
        return;

    bool visit = true;

    TIntermSequence *sequence = node->getSequence();

    if (preVisit)
        visit = node->visit(PreVisit, this);

    if (visit)
    {
        size_t paramIndex = 0u;
        for (auto *child : *sequence)
        {
            if (visit)
            {
                if (node->getFunction())
                {
                    // Both built-ins and user defined functions should have the function symbol
                    // set.
                    ASSERT(paramIndex < node->getFunction()->getParamCount());
                    TQualifier qualifier =
                        node->getFunction()->getParam(paramIndex)->getType().getQualifier();
                    setInFunctionCallOutParameter(qualifier == EvqParamOut ||
                                                  qualifier == EvqParamInOut);
                    ++paramIndex;
                }
                else
                {
                    ASSERT(node->isConstructor());
                }
                child->traverse(this);
                if (inVisit)
                {
                    if (child != sequence->back())
                        visit = node->visit(InVisit, this);
                }
            }
        }
        setInFunctionCallOutParameter(false);

        if (visit && postVisit)
            visit = node->visit(PostVisit, this);
    }
}

void TIntermTraverser::traverseLoop(TIntermLoop *node)
{
    traverse(node);
}
}  // namespace sh