/*
 * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "DFGValidate.h"

#if ENABLE(DFG_JIT)

#include "CodeBlockWithJITType.h"
#include "DFGMayExit.h"
#include "JSCInlines.h"
#include <wtf/Assertions.h>
#include <wtf/BitVector.h>

namespace JSC { namespace DFG {

class Validate {
public:
    Validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
        : m_graph(graph)
        , m_graphDumpMode(graphDumpMode)
        , m_graphDumpBeforePhase(graphDumpBeforePhase)
    {
    }
    
    #define VALIDATE(context, assertion) do { \
        if (!(assertion)) { \
            startCrashing(); \
            dataLogF("\n\n\nAt "); \
            reportValidationContext context; \
            dataLogF(": validation failed: %s (%s:%d).\n", #assertion, __FILE__, __LINE__); \
            dumpGraphIfAppropriate(); \
            WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
            CRASH(); \
        } \
    } while (0)
    
    #define V_EQUAL(context, left, right) do { \
        if (left != right) { \
            startCrashing(); \
            dataLogF("\n\n\nAt "); \
            reportValidationContext context; \
            dataLogF(": validation failed: (%s = ", #left); \
            dataLog(left); \
            dataLogF(") == (%s = ", #right); \
            dataLog(right); \
            dataLogF(") (%s:%d).\n", __FILE__, __LINE__); \
            dumpGraphIfAppropriate(); \
            WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #left " == " #right); \
            CRASH(); \
        } \
    } while (0)

    #define notSet (static_cast<size_t>(-1))
        
    void validate()
    {
        // NB. This code is not written for performance, since it is not intended to run
        // in release builds.

        // Validate that all local variables at the head of the root block are dead.
        BasicBlock* root = m_graph.block(0);
        for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i)
            V_EQUAL((virtualRegisterForLocal(i), root), static_cast<Node*>(0), root->variablesAtHead.local(i));
        
        // Validate ref counts and uses.
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            VALIDATE((block), block->isReachable);
            for (size_t i = 0; i < block->numNodes(); ++i)
                m_myRefCounts.add(block->node(i), 0);
        }
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            for (size_t i = 0; i < block->numNodes(); ++i) {
                Node* node = block->node(i);
                m_acceptableNodes.add(node);
                if (!node->shouldGenerate())
                    continue;
                if (node->op() == Upsilon) {
                    VALIDATE((node), m_graph.m_form == SSA);
                    if (node->phi()->shouldGenerate())
                        m_myRefCounts.find(node)->value++;
                }
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    // Phi children in LoadStore form are invalid.
                    if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
                        continue;
                    
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    
                    m_myRefCounts.find(edge.node())->value++;

                    validateEdgeWithDoubleResultIfNecessary(node, edge);
                    VALIDATE((node, edge), edge->hasInt52Result() == (edge.useKind() == Int52RepUse));
                    
                    if (m_graph.m_form == SSA) {
                        // In SSA, all edges must hasResult().
                        VALIDATE((node, edge), edge->hasResult());
                        continue;
                    }
                    
                    // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
                    switch (node->op()) {
                    case Flush:
                    case GetLocal:
                        VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
                        VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                        break;
                    case PhantomLocal:
                        VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
                        VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                        VALIDATE((node, edge), edge->op() != SetLocal);
                        break;
                    case Phi:
                        VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
                        if (m_graph.m_unificationState == LocallyUnified)
                            break;
                        VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                        break;
                    case Phantom:
                        switch (m_graph.m_form) {
                        case LoadStore:
                            if (j) {
                                VALIDATE((node, edge), edge->hasResult());
                                break;
                            }
                            switch (edge->op()) {
                            case Phi:
                            case SetArgument:
                            case SetLocal:
                                break;
                            default:
                                VALIDATE((node, edge), edge->hasResult());
                                break;
                            }
                            break;
                        case ThreadedCPS:
                            VALIDATE((node, edge), edge->hasResult());
                            break;
                        case SSA:
                            RELEASE_ASSERT_NOT_REACHED();
                            break;
                        }
                        break;
                    default:
                        VALIDATE((node, edge), edge->hasResult());
                        break;
                    }
                }
            }
        }
        
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            for (size_t i = 0; i < block->numNodes(); ++i) {
                Node* node = block->node(i);
                if (m_graph.m_refCountState == ExactRefCount)
                    V_EQUAL((node), m_myRefCounts.get(node), node->adjustedRefCount());
            }
            
            for (size_t i = 0 ; i < block->size() - 1; ++i) {
                Node* node = block->at(i);
                VALIDATE((node), !node->isTerminal());
            }
            
            for (size_t i = 0; i < block->size(); ++i) {
                Node* node = block->at(i);
                
                VALIDATE((node), !mayExit(m_graph, node) || node->origin.forExit.isSet());
                VALIDATE((node), !node->hasStructure() || !!node->structure());
                VALIDATE((node), !node->hasCellOperand() || node->cellOperand()->value().isCell());
                VALIDATE((node), !node->hasCellOperand() || !!node->cellOperand()->value());
                 
                if (!(node->flags() & NodeHasVarArgs)) {
                    if (!node->child2())
                        VALIDATE((node), !node->child3());
                    if (!node->child1())
                        VALIDATE((node), !node->child2());
                }
                 
                switch (node->op()) {
                case Identity:
                    VALIDATE((node), canonicalResultRepresentation(node->result()) == canonicalResultRepresentation(node->child1()->result()));
                    break;
                case SetLocal:
                case PutStack:
                case Upsilon:
                    VALIDATE((node), !!node->child1());
                    switch (node->child1().useKind()) {
                    case UntypedUse:
                    case CellUse:
                    case Int32Use:
                    case Int52RepUse:
                    case DoubleRepUse:
                    case BooleanUse:
                        break;
                    default:
                        VALIDATE((node), !"Bad use kind");
                        break;
                    }
                    break;
                case MakeRope:
                case ValueAdd:
                case ArithAdd:
                case ArithSub:
                case ArithMul:
                case ArithIMul:
                case ArithDiv:
                case ArithMod:
                case ArithMin:
                case ArithMax:
                case ArithPow:
                case CompareLess:
                case CompareLessEq:
                case CompareGreater:
                case CompareGreaterEq:
                case CompareEq:
                case CompareEqConstant:
                case CompareStrictEq:
                    VALIDATE((node), !!node->child1());
                    VALIDATE((node), !!node->child2());
                    break;
                case PutStructure:
                    VALIDATE((node), !node->transition()->previous->dfgShouldWatch());
                    break;
                case MultiPutByOffset:
                    for (unsigned i = node->multiPutByOffsetData().variants.size(); i--;) {
                        const PutByIdVariant& variant = node->multiPutByOffsetData().variants[i];
                        if (variant.kind() != PutByIdVariant::Transition)
                            continue;
                        VALIDATE((node), !variant.oldStructureForTransition()->dfgShouldWatch());
                    }
                    break;
                default:
                    break;
                }
            }
        }
        
        switch (m_graph.m_form) {
        case LoadStore:
        case ThreadedCPS:
            validateCPS();
            break;
            
        case SSA:
            validateSSA();
            break;
        }
    }
    
private:
    Graph& m_graph;
    GraphDumpMode m_graphDumpMode;
    CString m_graphDumpBeforePhase;
    
    HashMap<Node*, unsigned> m_myRefCounts;
    HashSet<Node*> m_acceptableNodes;
    
    void validateCPS()
    {
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            
            HashSet<Node*> phisInThisBlock;
            HashSet<Node*> nodesInThisBlock;
            
            for (size_t i = 0; i < block->numNodes(); ++i) {
                Node* node = block->node(i);
                nodesInThisBlock.add(node);
                if (block->isPhiIndex(i))
                    phisInThisBlock.add(node);
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    VALIDATE((node, edge), m_acceptableNodes.contains(edge.node()));
                }
            }
            
            for (size_t i = 0; i < block->phis.size(); ++i) {
                Node* node = block->phis[i];
                ASSERT(phisInThisBlock.contains(node));
                VALIDATE((node), node->op() == Phi);
                VirtualRegister local = node->local();
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    // Phi children in LoadStore form are invalid.
                    if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
                        continue;
                    
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    
                    VALIDATE(
                        (node, edge),
                        edge->op() == SetLocal
                        || edge->op() == SetArgument
                        || edge->op() == Flush
                        || edge->op() == Phi);
                    
                    if (phisInThisBlock.contains(edge.node()))
                        continue;
                    
                    if (nodesInThisBlock.contains(edge.node())) {
                        VALIDATE(
                            (node, edge),
                            edge->op() == SetLocal
                            || edge->op() == SetArgument
                            || edge->op() == Flush);
                        
                        continue;
                    }
                    
                    // There must exist a predecessor block that has this node index in
                    // its tail variables.
                    bool found = false;
                    for (unsigned k = 0; k < block->predecessors.size(); ++k) {
                        BasicBlock* prevBlock = block->predecessors[k];
                        VALIDATE((block->predecessors[k]), prevBlock);
                        Node* prevNode = prevBlock->variablesAtTail.operand(local);
                        // If we have a Phi that is not referring to *this* block then all predecessors
                        // must have that local available.
                        VALIDATE((local, block, block->predecessors[k]), prevNode);
                        switch (prevNode->op()) {
                        case GetLocal:
                        case Flush:
                        case PhantomLocal:
                            prevNode = prevNode->child1().node();
                            break;
                        default:
                            break;
                        }
                        if (node->shouldGenerate()) {
                            VALIDATE((local, block->predecessors[k], prevNode),
                                     prevNode->shouldGenerate());
                        }
                        VALIDATE(
                            (local, block->predecessors[k], prevNode),
                            prevNode->op() == SetLocal
                            || prevNode->op() == SetArgument
                            || prevNode->op() == Phi);
                        if (prevNode == edge.node()) {
                            found = true;
                            break;
                        }
                        // At this point it cannot refer into this block.
                        VALIDATE((local, block->predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
                    }
                    
                    VALIDATE((node, edge), found);
                }
            }
            
            Operands<size_t> getLocalPositions(
                block->variablesAtHead.numberOfArguments(),
                block->variablesAtHead.numberOfLocals());
            Operands<size_t> setLocalPositions(
                block->variablesAtHead.numberOfArguments(),
                block->variablesAtHead.numberOfLocals());
            
            for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
                VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData(m_graph));
                if (m_graph.m_form == ThreadedCPS)
                    VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData(m_graph));
                
                getLocalPositions.argument(i) = notSet;
                setLocalPositions.argument(i) = notSet;
            }
            for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
                VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData(m_graph));
                if (m_graph.m_form == ThreadedCPS)
                    VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData(m_graph));

                getLocalPositions.local(i) = notSet;
                setLocalPositions.local(i) = notSet;
            }
            
            for (size_t i = 0; i < block->size(); ++i) {
                Node* node = block->at(i);
                ASSERT(nodesInThisBlock.contains(node));
                VALIDATE((node), node->op() != Phi);
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
                    switch (node->op()) {
                    case PhantomLocal:
                    case GetLocal:
                    case Flush:
                        break;
                    case Phantom:
                        if (m_graph.m_form == LoadStore && !j)
                            break;
                        FALLTHROUGH;
                    default:
                        VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
                        break;
                    }
                }
                
                switch (node->op()) {
                case Phi:
                case Upsilon:
                case CheckInBounds:
                case PhantomNewObject:
                case PutHint:
                case CheckStructureImmediate:
                case MaterializeNewObject:
                case PutStack:
                case KillStack:
                case GetStack:
                    VALIDATE((node), !"unexpected node type in CPS");
                    break;
                default:
                    break;
                }
                
                if (!node->shouldGenerate())
                    continue;
                switch (node->op()) {
                case GetLocal:
                    if (node->variableAccessData()->isCaptured())
                        break;
                    // Ignore GetLocal's that we know to be dead, but that the graph
                    // doesn't yet know to be dead.
                    if (!m_myRefCounts.get(node))
                        break;
                    if (m_graph.m_form == ThreadedCPS)
                        VALIDATE((node, block), getLocalPositions.operand(node->local()) == notSet);
                    getLocalPositions.operand(node->local()) = i;
                    break;
                case SetLocal:
                    if (node->variableAccessData()->isCaptured())
                        break;
                    // Only record the first SetLocal. There may be multiple SetLocals
                    // because of flushing.
                    if (setLocalPositions.operand(node->local()) != notSet)
                        break;
                    setLocalPositions.operand(node->local()) = i;
                    break;
                case SetArgument:
                    if (node->variableAccessData()->isCaptured())
                        break;
                    // This acts like a reset. It's ok to have a second GetLocal for a local in the same
                    // block if we had a SetArgument for that local.
                    getLocalPositions.operand(node->local()) = notSet;
                    setLocalPositions.operand(node->local()) = notSet;
                    break;
                default:
                    break;
                }
            }
            
            if (m_graph.m_form == LoadStore)
                continue;
            
            for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
                checkOperand(
                    block, getLocalPositions, setLocalPositions, virtualRegisterForArgument(i));
            }
            for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
                checkOperand(
                    block, getLocalPositions, setLocalPositions, virtualRegisterForLocal(i));
            }
        }
    }
    
    void validateSSA()
    {
        // FIXME: Add more things here.
        // https://bugs.webkit.org/show_bug.cgi?id=123471
        
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            
            VALIDATE((block), block->phis.isEmpty());
            
            unsigned nodeIndex = 0;
            for (; nodeIndex < block->size() && !block->at(nodeIndex)->origin.forExit.isSet(); nodeIndex++) { }
            
            VALIDATE((block), nodeIndex < block->size());
            
            for (; nodeIndex < block->size(); nodeIndex++)
                VALIDATE((block->at(nodeIndex)), block->at(nodeIndex)->origin.forExit.isSet());
            
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                Node* node = block->at(nodeIndex);
                switch (node->op()) {
                case Phi:
                    VALIDATE((node), !node->origin.forExit.isSet());
                    break;
                    
                case GetLocal:
                case SetLocal:
                case GetLocalUnlinked:
                case SetArgument:
                    VALIDATE((node), !"bad node type for SSA");
                    break;
                    
                default:
                    // FIXME: Add more things here.
                    // https://bugs.webkit.org/show_bug.cgi?id=123471
                    break;
                }
            }
        }
    }

    void validateEdgeWithDoubleResultIfNecessary(Node* node, Edge edge)
    {
        if (!edge->hasDoubleResult())
            return;

        if (m_graph.m_planStage < PlanStage::AfterFixup)
            VALIDATE((node, edge), edge.useKind() == UntypedUse);
        else
            VALIDATE((node, edge), edge.useKind() == DoubleRepUse || edge.useKind() == DoubleRepRealUse || edge.useKind() == DoubleRepMachineIntUse);
    }

    void checkOperand(
        BasicBlock* block, Operands<size_t>& getLocalPositions,
        Operands<size_t>& setLocalPositions, VirtualRegister operand)
    {
        if (getLocalPositions.operand(operand) == notSet)
            return;
        if (setLocalPositions.operand(operand) == notSet)
            return;
        
        VALIDATE(
            (block->at(getLocalPositions.operand(operand)),
             block->at(setLocalPositions.operand(operand)),
             block),
            getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
    }
    
    void reportValidationContext(Node* node)
    {
        dataLogF("@%u", node->index());
    }
    
    void reportValidationContext(BasicBlock* block)
    {
        dataLog("Block ", *block);
    }
    
    void reportValidationContext(Node* node, Edge edge)
    {
        dataLog(node, " -> ", edge);
    }
    
    void reportValidationContext(VirtualRegister local, BasicBlock* block)
    {
        if (!block) {
            dataLog(local, " in null Block ");
            return;
        }

        dataLog(local, " in Block ", *block);
    }
    
    void reportValidationContext(
        VirtualRegister local, BasicBlock* sourceBlock, BasicBlock* destinationBlock)
    {
        dataLog(local, " in Block ", *sourceBlock, " -> ", *destinationBlock);
    }
    
    void reportValidationContext(
        VirtualRegister local, BasicBlock* sourceBlock, Node* prevNode)
    {
        dataLog(prevNode, " for ", local, " in Block ", *sourceBlock);
    }
    
    void reportValidationContext(Node* node, BasicBlock* block)
    {
        dataLog(node, " in Block ", *block);
    }
    
    void reportValidationContext(Node* node, Node* node2, BasicBlock* block)
    {
        dataLog(node, " and ", node2, " in Block ", *block);
    }
    
    void reportValidationContext(
        Node* node, BasicBlock* block, Node* expectedNode, Edge incomingEdge)
    {
        dataLog(node, " in Block ", *block, ", searching for ", expectedNode, " from ", incomingEdge);
    }
    
    void dumpGraphIfAppropriate()
    {
        if (m_graphDumpMode == DontDumpGraph)
            return;
        dataLog("\n");
        if (!m_graphDumpBeforePhase.isNull()) {
            dataLog("Before phase:\n");
            dataLog(m_graphDumpBeforePhase);
        }
        dataLog("At time of failure:\n");
        m_graph.dump();
    }
};

void validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
{
    Validate validationObject(graph, graphDumpMode, graphDumpBeforePhase);
    validationObject.validate();
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)