//
// Copyright (c) 2002-2010 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/ValidateLimitations.h"
#include "compiler/InfoSink.h"
#include "compiler/InitializeParseContext.h"
#include "compiler/ParseHelper.h"

namespace {
bool IsLoopIndex(const TIntermSymbol* symbol, const TLoopStack& stack) {
    for (TLoopStack::const_iterator i = stack.begin(); i != stack.end(); ++i) {
        if (i->index.id == symbol->getId())
            return true;
    }
    return false;
}

void MarkLoopForUnroll(const TIntermSymbol* symbol, TLoopStack& stack) {
    for (TLoopStack::iterator i = stack.begin(); i != stack.end(); ++i) {
        if (i->index.id == symbol->getId()) {
            ASSERT(i->loop != NULL);
            i->loop->setUnrollFlag(true);
            return;
        }
    }
    UNREACHABLE();
}

// Traverses a node to check if it represents a constant index expression.
// Definition:
// constant-index-expressions are a superset of constant-expressions.
// Constant-index-expressions can include loop indices as defined in
// GLSL ES 1.0 spec, Appendix A, section 4.
// The following are constant-index-expressions:
// - Constant expressions
// - Loop indices as defined in section 4
// - Expressions composed of both of the above
class ValidateConstIndexExpr : public TIntermTraverser {
public:
    ValidateConstIndexExpr(const TLoopStack& stack)
        : mValid(true), mLoopStack(stack) {}

    // Returns true if the parsed node represents a constant index expression.
    bool isValid() const { return mValid; }

    virtual void visitSymbol(TIntermSymbol* symbol) {
        // Only constants and loop indices are allowed in a
        // constant index expression.
        if (mValid) {
            mValid = (symbol->getQualifier() == EvqConst) ||
                     IsLoopIndex(symbol, mLoopStack);
        }
    }

private:
    bool mValid;
    const TLoopStack& mLoopStack;
};

// Traverses a node to check if it uses a loop index.
// If an int loop index is used in its body as a sampler array index,
// mark the loop for unroll.
class ValidateLoopIndexExpr : public TIntermTraverser {
public:
    ValidateLoopIndexExpr(TLoopStack& stack)
        : mUsesFloatLoopIndex(false),
          mUsesIntLoopIndex(false),
          mLoopStack(stack) {}

    bool usesFloatLoopIndex() const { return mUsesFloatLoopIndex; }
    bool usesIntLoopIndex() const { return mUsesIntLoopIndex; }

    virtual void visitSymbol(TIntermSymbol* symbol) {
        if (IsLoopIndex(symbol, mLoopStack)) {
            switch (symbol->getBasicType()) {
              case EbtFloat:
                mUsesFloatLoopIndex = true;
                break;
              case EbtInt:
                mUsesIntLoopIndex = true;
                MarkLoopForUnroll(symbol, mLoopStack);
                break;
              default:
                UNREACHABLE();
            }
        }
    }

private:
    bool mUsesFloatLoopIndex;
    bool mUsesIntLoopIndex;
    TLoopStack& mLoopStack;
};
}  // namespace

ValidateLimitations::ValidateLimitations(ShShaderType shaderType,
                                         TInfoSinkBase& sink)
    : mShaderType(shaderType),
      mSink(sink),
      mNumErrors(0)
{
}

bool ValidateLimitations::visitBinary(Visit, TIntermBinary* node)
{
    // Check if loop index is modified in the loop body.
    validateOperation(node, node->getLeft());

    // Check indexing.
    switch (node->getOp()) {
      case EOpIndexDirect:
        validateIndexing(node);
        break;
      case EOpIndexIndirect:
#if defined(__APPLE__)
        // Loop unrolling is a work-around for a Mac Cg compiler bug where it
        // crashes when a sampler array's index is also the loop index.
        // Once Apple fixes this bug, we should remove the code in this CL.
        // See http://codereview.appspot.com/4331048/.
        if ((node->getLeft() != NULL) && (node->getRight() != NULL) &&
            (node->getLeft()->getAsSymbolNode())) {
            TIntermSymbol* symbol = node->getLeft()->getAsSymbolNode();
            if (IsSampler(symbol->getBasicType()) && symbol->isArray()) {
                ValidateLoopIndexExpr validate(mLoopStack);
                node->getRight()->traverse(&validate);
                if (validate.usesFloatLoopIndex()) {
                    error(node->getLine(),
                          "sampler array index is float loop index",
                          "for");
                }
            }
        }
#endif
        validateIndexing(node);
        break;
      default: break;
    }
    return true;
}

bool ValidateLimitations::visitUnary(Visit, TIntermUnary* node)
{
    // Check if loop index is modified in the loop body.
    validateOperation(node, node->getOperand());

    return true;
}

bool ValidateLimitations::visitAggregate(Visit, TIntermAggregate* node)
{
    switch (node->getOp()) {
      case EOpFunctionCall:
        validateFunctionCall(node);
        break;
      default:
        break;
    }
    return true;
}

bool ValidateLimitations::visitLoop(Visit, TIntermLoop* node)
{
    if (!validateLoopType(node))
        return false;

    TLoopInfo info;
    memset(&info, 0, sizeof(TLoopInfo));
    info.loop = node;
    if (!validateForLoopHeader(node, &info))
        return false;

    TIntermNode* body = node->getBody();
    if (body != NULL) {
        mLoopStack.push_back(info);
        body->traverse(this);
        mLoopStack.pop_back();
    }

    // The loop is fully processed - no need to visit children.
    return false;
}

void ValidateLimitations::error(TSourceLoc loc,
                                const char *reason, const char* token)
{
    mSink.prefix(EPrefixError);
    mSink.location(loc);
    mSink << "'" << token << "' : " << reason << "\n";
    ++mNumErrors;
}

bool ValidateLimitations::withinLoopBody() const
{
    return !mLoopStack.empty();
}

bool ValidateLimitations::isLoopIndex(const TIntermSymbol* symbol) const
{
    return IsLoopIndex(symbol, mLoopStack);
}

bool ValidateLimitations::validateLoopType(TIntermLoop* node) {
    TLoopType type = node->getType();
    if (type == ELoopFor)
        return true;

    // Reject while and do-while loops.
    error(node->getLine(),
          "This type of loop is not allowed",
          type == ELoopWhile ? "while" : "do");
    return false;
}

bool ValidateLimitations::validateForLoopHeader(TIntermLoop* node,
                                                TLoopInfo* info)
{
    ASSERT(node->getType() == ELoopFor);

    //
    // The for statement has the form:
    //    for ( init-declaration ; condition ; expression ) statement
    //
    if (!validateForLoopInit(node, info))
        return false;
    if (!validateForLoopCond(node, info))
        return false;
    if (!validateForLoopExpr(node, info))
        return false;

    return true;
}

bool ValidateLimitations::validateForLoopInit(TIntermLoop* node,
                                              TLoopInfo* info)
{
    TIntermNode* init = node->getInit();
    if (init == NULL) {
        error(node->getLine(), "Missing init declaration", "for");
        return false;
    }

    //
    // init-declaration has the form:
    //     type-specifier identifier = constant-expression
    //
    TIntermAggregate* decl = init->getAsAggregate();
    if ((decl == NULL) || (decl->getOp() != EOpDeclaration)) {
        error(init->getLine(), "Invalid init declaration", "for");
        return false;
    }
    // To keep things simple do not allow declaration list.
    TIntermSequence& declSeq = decl->getSequence();
    if (declSeq.size() != 1) {
        error(decl->getLine(), "Invalid init declaration", "for");
        return false;
    }
    TIntermBinary* declInit = declSeq[0]->getAsBinaryNode();
    if ((declInit == NULL) || (declInit->getOp() != EOpInitialize)) {
        error(decl->getLine(), "Invalid init declaration", "for");
        return false;
    }
    TIntermSymbol* symbol = declInit->getLeft()->getAsSymbolNode();
    if (symbol == NULL) {
        error(declInit->getLine(), "Invalid init declaration", "for");
        return false;
    }
    // The loop index has type int or float.
    TBasicType type = symbol->getBasicType();
    if ((type != EbtInt) && (type != EbtFloat)) {
        error(symbol->getLine(),
              "Invalid type for loop index", getBasicString(type));
        return false;
    }
    // The loop index is initialized with constant expression.
    if (!isConstExpr(declInit->getRight())) {
        error(declInit->getLine(),
              "Loop index cannot be initialized with non-constant expression",
              symbol->getSymbol().c_str());
        return false;
    }

    info->index.id = symbol->getId();
    return true;
}

bool ValidateLimitations::validateForLoopCond(TIntermLoop* node,
                                              TLoopInfo* info)
{
    TIntermNode* cond = node->getCondition();
    if (cond == NULL) {
        error(node->getLine(), "Missing condition", "for");
        return false;
    }
    //
    // condition has the form:
    //     loop_index relational_operator constant_expression
    //
    TIntermBinary* binOp = cond->getAsBinaryNode();
    if (binOp == NULL) {
        error(node->getLine(), "Invalid condition", "for");
        return false;
    }
    // Loop index should be to the left of relational operator.
    TIntermSymbol* symbol = binOp->getLeft()->getAsSymbolNode();
    if (symbol == NULL) {
        error(binOp->getLine(), "Invalid condition", "for");
        return false;
    }
    if (symbol->getId() != info->index.id) {
        error(symbol->getLine(),
              "Expected loop index", symbol->getSymbol().c_str());
        return false;
    }
    // Relational operator is one of: > >= < <= == or !=.
    switch (binOp->getOp()) {
      case EOpEqual:
      case EOpNotEqual:
      case EOpLessThan:
      case EOpGreaterThan:
      case EOpLessThanEqual:
      case EOpGreaterThanEqual:
        break;
      default:
        error(binOp->getLine(),
              "Invalid relational operator",
              getOperatorString(binOp->getOp()));
        break;
    }
    // Loop index must be compared with a constant.
    if (!isConstExpr(binOp->getRight())) {
        error(binOp->getLine(),
              "Loop index cannot be compared with non-constant expression",
              symbol->getSymbol().c_str());
        return false;
    }

    return true;
}

bool ValidateLimitations::validateForLoopExpr(TIntermLoop* node,
                                              TLoopInfo* info)
{
    TIntermNode* expr = node->getExpression();
    if (expr == NULL) {
        error(node->getLine(), "Missing expression", "for");
        return false;
    }

    // for expression has one of the following forms:
    //     loop_index++
    //     loop_index--
    //     loop_index += constant_expression
    //     loop_index -= constant_expression
    //     ++loop_index
    //     --loop_index
    // The last two forms are not specified in the spec, but I am assuming
    // its an oversight.
    TIntermUnary* unOp = expr->getAsUnaryNode();
    TIntermBinary* binOp = unOp ? NULL : expr->getAsBinaryNode();

    TOperator op = EOpNull;
    TIntermSymbol* symbol = NULL;
    if (unOp != NULL) {
        op = unOp->getOp();
        symbol = unOp->getOperand()->getAsSymbolNode();
    } else if (binOp != NULL) {
        op = binOp->getOp();
        symbol = binOp->getLeft()->getAsSymbolNode();
    }

    // The operand must be loop index.
    if (symbol == NULL) {
        error(expr->getLine(), "Invalid expression", "for");
        return false;
    }
    if (symbol->getId() != info->index.id) {
        error(symbol->getLine(),
              "Expected loop index", symbol->getSymbol().c_str());
        return false;
    }

    // The operator is one of: ++ -- += -=.
    switch (op) {
        case EOpPostIncrement:
        case EOpPostDecrement:
        case EOpPreIncrement:
        case EOpPreDecrement:
            ASSERT((unOp != NULL) && (binOp == NULL));
            break;
        case EOpAddAssign:
        case EOpSubAssign:
            ASSERT((unOp == NULL) && (binOp != NULL));
            break;
        default:
            error(expr->getLine(), "Invalid operator", getOperatorString(op));
            return false;
    }

    // Loop index must be incremented/decremented with a constant.
    if (binOp != NULL) {
        if (!isConstExpr(binOp->getRight())) {
            error(binOp->getLine(),
                  "Loop index cannot be modified by non-constant expression",
                  symbol->getSymbol().c_str());
            return false;
        }
    }

    return true;
}

bool ValidateLimitations::validateFunctionCall(TIntermAggregate* node)
{
    ASSERT(node->getOp() == EOpFunctionCall);

    // If not within loop body, there is nothing to check.
    if (!withinLoopBody())
        return true;

    // List of param indices for which loop indices are used as argument.
    typedef std::vector<size_t> ParamIndex;
    ParamIndex pIndex;
    TIntermSequence& params = node->getSequence();
    for (TIntermSequence::size_type i = 0; i < params.size(); ++i) {
        TIntermSymbol* symbol = params[i]->getAsSymbolNode();
        if (symbol && isLoopIndex(symbol))
            pIndex.push_back(i);
    }
    // If none of the loop indices are used as arguments,
    // there is nothing to check.
    if (pIndex.empty())
        return true;

    bool valid = true;
    TSymbolTable& symbolTable = GetGlobalParseContext()->symbolTable;
    TSymbol* symbol = symbolTable.find(node->getName());
    ASSERT(symbol && symbol->isFunction());
    TFunction* function = static_cast<TFunction*>(symbol);
    for (ParamIndex::const_iterator i = pIndex.begin();
         i != pIndex.end(); ++i) {
        const TParameter& param = function->getParam(*i);
        TQualifier qual = param.type->getQualifier();
        if ((qual == EvqOut) || (qual == EvqInOut)) {
            error(params[*i]->getLine(),
                  "Loop index cannot be used as argument to a function out or inout parameter",
                  params[*i]->getAsSymbolNode()->getSymbol().c_str());
            valid = false;
        }
    }

    return valid;
}

bool ValidateLimitations::validateOperation(TIntermOperator* node,
                                            TIntermNode* operand) {
    // Check if loop index is modified in the loop body.
    if (!withinLoopBody() || !node->modifiesState())
        return true;

    const TIntermSymbol* symbol = operand->getAsSymbolNode();
    if (symbol && isLoopIndex(symbol)) {
        error(node->getLine(),
              "Loop index cannot be statically assigned to within the body of the loop",
              symbol->getSymbol().c_str());
    }
    return true;
}

bool ValidateLimitations::isConstExpr(TIntermNode* node)
{
    ASSERT(node != NULL);
    return node->getAsConstantUnion() != NULL;
}

bool ValidateLimitations::isConstIndexExpr(TIntermNode* node)
{
    ASSERT(node != NULL);

    ValidateConstIndexExpr validate(mLoopStack);
    node->traverse(&validate);
    return validate.isValid();
}

bool ValidateLimitations::validateIndexing(TIntermBinary* node)
{
    ASSERT((node->getOp() == EOpIndexDirect) ||
           (node->getOp() == EOpIndexIndirect));

    bool valid = true;
    TIntermTyped* index = node->getRight();
    // The index expression must have integral type.
    if (!index->isScalar() || (index->getBasicType() != EbtInt)) {
        error(index->getLine(),
              "Index expression must have integral type",
              index->getCompleteString().c_str());
        valid = false;
    }
    // The index expession must be a constant-index-expression unless
    // the operand is a uniform in a vertex shader.
    TIntermTyped* operand = node->getLeft();
    bool skip = (mShaderType == SH_VERTEX_SHADER) &&
                (operand->getQualifier() == EvqUniform);
    if (!skip && !isConstIndexExpr(index)) {
        error(index->getLine(), "Index expression must be constant", "[]");
        valid = false;
    }
    return valid;
}