
/* Compiler implementation of the D programming language
 * Copyright (c) 1999-2014 by Digital Mars
 * All Rights Reserved
 * written by Walter Bright
 * http://www.digitalmars.com
 * Distributed under the Boost Software License, Version 1.0.
 * http://www.boost.org/LICENSE_1_0.txt
 * https://github.com/D-Programming-Language/dmd/blob/master/src/arrayop.c
 */

#include <stdio.h>
#include <string.h>
#include <assert.h>

#include "rmem.h"

#include "aav.h"

#include "expression.h"
#include "statement.h"
#include "mtype.h"
#include "declaration.h"
#include "scope.h"
#include "id.h"
#include "module.h"
#include "init.h"

extern int binary(const char *p , const char **tab, int high);
void buildArrayIdent(Expression *e, OutBuffer *buf, Expressions *arguments);
Expression *buildArrayLoop(Expression *e, Parameters *fparams);

/**************************************
 * Hash table of array op functions already generated or known about.
 */

AA *arrayfuncs;

/**************************************
 * Structure to contain information needed to insert an array op call
 */

FuncDeclaration *buildArrayOp(Identifier *ident, BinExp *exp, Scope *sc, Loc loc)
{
    Parameters *fparams = new Parameters();
    Expression *loopbody = buildArrayLoop(exp, fparams);

    /* Construct the function body:
     *  foreach (i; 0 .. p.length)    for (size_t i = 0; i < p.length; i++)
     *      loopbody;
     *  return p;
     */

    Parameter *p = (*fparams)[0];
    // foreach (i; 0 .. p.length)
    Statement *s1 = new ForeachRangeStatement(Loc(), TOKforeach,
        new Parameter(0, NULL, Id::p, NULL),
        new IntegerExp(Loc(), 0, Type::tsize_t),
        new ArrayLengthExp(Loc(), new IdentifierExp(Loc(), p->ident)),
        new ExpStatement(Loc(), loopbody));
    //printf("%s\n", s1->toChars());
    Statement *s2 = new ReturnStatement(Loc(), new IdentifierExp(Loc(), p->ident));
    //printf("s2: %s\n", s2->toChars());
    Statement *fbody = new CompoundStatement(Loc(), s1, s2);

    // Built-in array ops should be @trusted, pure, nothrow and nogc
    StorageClass stc = STCtrusted | STCpure | STCnothrow | STCnogc;

    /* Construct the function
     */
    TypeFunction *ftype = new TypeFunction(fparams, exp->type, 0, LINKc, stc);
    //printf("ftype: %s\n", ftype->toChars());
    FuncDeclaration *fd = new FuncDeclaration(Loc(), Loc(), ident, STCundefined, ftype);
    fd->fbody = fbody;
    fd->protection = PROTpublic;
    fd->linkage = LINKc;
    fd->isArrayOp = 1;

    sc->module->importedFrom->members->push(fd);

    sc = sc->push();
    sc->parent = sc->module->importedFrom;
    sc->stc = 0;
    sc->linkage = LINKc;
    fd->semantic(sc);
    fd->semantic2(sc);
    unsigned errors = global.startGagging();
    fd->semantic3(sc);
    if (global.endGagging(errors))
    {
        fd->type = Type::terror;
        fd->errors = true;
        fd->fbody = NULL;
    }
    sc->pop();

    return fd;
}

/**********************************************
 * Check that there are no uses of arrays without [].
 */
bool isArrayOpValid(Expression *e)
{
    if (e->op == TOKslice)
        return true;
    if (e->op == TOKarrayliteral)
    {
        Type *t = e->type->toBasetype();
        while (t->ty == Tarray || t->ty == Tsarray)
            t = t->nextOf()->toBasetype();
        return (t->ty != Tvoid);
    }
    Type *tb = e->type->toBasetype();

    BinExp *be;
    if (tb->ty == Tarray || tb->ty == Tsarray)
    {
        switch (e->op)
        {
            case TOKadd:
            case TOKmin:
            case TOKmul:
            case TOKdiv:
            case TOKmod:
            case TOKxor:
            case TOKand:
            case TOKor:
            case TOKassign:
            case TOKaddass:
            case TOKminass:
            case TOKmulass:
            case TOKdivass:
            case TOKmodass:
            case TOKxorass:
            case TOKandass:
            case TOKorass:
            case TOKpow:
            case TOKpowass:
                be = (BinExp *)e;
                return isArrayOpValid(be->e1) && isArrayOpValid(be->e2);

            case TOKconstruct:
                be = (BinExp *)e;
                return be->e1->op == TOKslice && isArrayOpValid(be->e2);

            case TOKcall:
                 return false; // TODO: Decide if [] is required after arrayop calls.

            case TOKneg:
            case TOKtilde:
                 return isArrayOpValid(((UnaExp *)e)->e1);

            default:
                return false;
        }
    }
    return true;
}

bool isNonAssignmentArrayOp(Expression *e)
{
    if (e->op == TOKslice)
        return isNonAssignmentArrayOp(((SliceExp *)e)->e1);
    Type *tb = e->type->toBasetype();

    if (tb->ty == Tarray || tb->ty == Tsarray)
    {
        switch (e->op)
        {
            case TOKadd:
            case TOKmin:
            case TOKmul:
            case TOKdiv:
            case TOKmod:
            case TOKxor:
            case TOKand:
            case TOKor:
            case TOKpow:
            case TOKneg:
            case TOKtilde:
                return true;

            default:
                return false;
        }
    }
    return false;
}

/***********************************
 * Construct the array operation expression.
 */

Expression *arrayOp(BinExp *e, Scope *sc)
{
    //printf("BinExp::arrayOp() %s\n", toChars());

    Type *tb = e->type->toBasetype();
    assert(tb->ty == Tarray || tb->ty == Tsarray);
    Type *tbn = tb->nextOf()->toBasetype();
    if (tbn->ty == Tvoid)
    {
        e->error("Cannot perform array operations on void[] arrays");
        return new ErrorExp();
    }
    if (!isArrayOpValid(e))
    {
        e->error("invalid array operation %s (did you forget a [] ?)", e->toChars());
        return new ErrorExp();
    }

    Expressions *arguments = new Expressions();

    /* The expression to generate an array operation for is mangled
     * into a name to use as the array operation function name.
     * Mangle in the operands and operators in RPN order, and type.
     */
    OutBuffer buf;
    buf.writestring("_array");
    buildArrayIdent(e, &buf, arguments);
    buf.writeByte('_');

    /* Append deco of array element type
     */
    buf.writestring(e->type->toBasetype()->nextOf()->toBasetype()->mutableOf()->deco);

    char *name = buf.peekString();
    Identifier *ident = Lexer::idPool(name);

    FuncDeclaration **pFd = (FuncDeclaration **)dmd_aaGet(&arrayfuncs, (void *)ident);
    FuncDeclaration *fd = *pFd;

    if (!fd)
        fd = buildArrayOp(ident, e, sc, e->loc);

    if (fd && fd->errors)
    {
        const char *fmt;
        if (tbn->ty == Tstruct || tbn->ty == Tclass)
            fmt = "invalid array operation '%s' because %s doesn't support necessary arithmetic operations";
        else if (!tbn->isscalar())
            fmt = "invalid array operation '%s' because %s is not a scalar type";
        else
            fmt = "invalid array operation '%s' for element type %s";

        e->error(fmt, e->toChars(), tbn->toChars());
        return new ErrorExp();
    }

    *pFd = fd;

    Expression *ev = new VarExp(e->loc, fd);
    Expression *ec = new CallExp(e->loc, ev, arguments);

    return ec->semantic(sc);
}

Expression *arrayOp(BinAssignExp *e, Scope *sc)
{
    //printf("BinAssignExp::arrayOp() %s\n", toChars());

    /* Check that the elements of e1 can be assigned to
     */
    Type *tn = e->e1->type->toBasetype()->nextOf();

    if (tn && (!tn->isMutable() || !tn->isAssignable()))
    {
        e->error("slice %s is not mutable", e->e1->toChars());
        return new ErrorExp();
    }
    if (e->e1->op == TOKarrayliteral)
    {
        return e->e1->modifiableLvalue(sc, e->e1);
    }

    return arrayOp((BinExp *)e, sc);
}

/******************************************
 * Construct the identifier for the array operation function,
 * and build the argument list to pass to it.
 */

void buildArrayIdent(Expression *e, OutBuffer *buf, Expressions *arguments)
{
    class BuildArrayIdentVisitor : public Visitor
    {
        OutBuffer *buf;
        Expressions *arguments;
    public:
        BuildArrayIdentVisitor(OutBuffer *buf, Expressions *arguments)
            : buf(buf), arguments(arguments)
        {
        }

        void visit(Expression *e)
        {
            buf->writestring("Exp");
            arguments->shift(e);
        }

        void visit(CastExp *e)
        {
            Type *tb = e->type->toBasetype();
            if (tb->ty == Tarray || tb->ty == Tsarray)
            {
                e->e1->accept(this);
            }
            else
                visit((Expression *)e);
        }

        void visit(ArrayLiteralExp *e)
        {
            buf->writestring("Slice");
            arguments->shift(e);
        }

        void visit(SliceExp *e)
        {
            buf->writestring("Slice");
            arguments->shift(e);
        }

        void visit(AssignExp *e)
        {
            /* Evaluate assign expressions right to left
             */
            e->e2->accept(this);
            e->e1->accept(this);
            buf->writestring("Assign");
        }

        void visit(BinAssignExp *e)
        {
            /* Evaluate assign expressions right to left
             */
            e->e2->accept(this);
            e->e1->accept(this);
            const char *s;
            switch(e->op)
            {
            case TOKaddass: s = "Addass"; break;
            case TOKminass: s = "Subass"; break;
            case TOKmulass: s = "Mulass"; break;
            case TOKdivass: s = "Divass"; break;
            case TOKmodass: s = "Modass"; break;
            case TOKxorass: s = "Xorass"; break;
            case TOKandass: s = "Andass"; break;
            case TOKorass:  s = "Orass";  break;
            case TOKpowass: s = "Powass"; break;
            default: assert(0);
            }
            buf->writestring(s);
        }

        void visit(NegExp *e)
        {
            e->e1->accept(this);
            buf->writestring("Neg");
        }

        void visit(ComExp *e)
        {
            e->e1->accept(this);
            buf->writestring("Com");
        }

        void visit(BinExp *e)
        {
            /* Evaluate assign expressions left to right
             */
            const char *s = NULL;
            switch(e->op)
            {
            case TOKadd: s = "Add"; break;
            case TOKmin: s = "Sub"; break;
            case TOKmul: s = "Mul"; break;
            case TOKdiv: s = "Div"; break;
            case TOKmod: s = "Mod"; break;
            case TOKxor: s = "Xor"; break;
            case TOKand: s = "And"; break;
            case TOKor:  s = "Or";  break;
            case TOKpow: s = "Pow"; break;
            default: break;
            }
            if (s)
            {
                e->e1->accept(this);
                e->e2->accept(this);
                buf->writestring(s);
            }
            else
                visit((Expression *)e);
        }
    };

    BuildArrayIdentVisitor v(buf, arguments);
    e->accept(&v);
}

/******************************************
 * Construct the inner loop for the array operation function,
 * and build the parameter list.
 */

Expression *buildArrayLoop(Expression *e, Parameters *fparams)
{
    class BuildArrayLoopVisitor : public Visitor
    {
        Parameters *fparams;
        Expression *result;

    public:
        BuildArrayLoopVisitor(Parameters *fparams)
            : fparams(fparams), result(NULL)
        {
        }

        void visit(Expression *e)
        {
            Identifier *id = Identifier::generateId("c", fparams->dim);
            Parameter *param = new Parameter(0, e->type, id, NULL);
            fparams->shift(param);
            result = new IdentifierExp(Loc(), id);
        }

        void visit(CastExp *e)
        {
            Type *tb = e->type->toBasetype();
            if (tb->ty == Tarray || tb->ty == Tsarray)
            {
                e->e1->accept(this);
            }
            else
                visit((Expression *)e);
        }

        void visit(ArrayLiteralExp *e)
        {
            Identifier *id = Identifier::generateId("p", fparams->dim);
            Parameter *param = new Parameter(STCconst, e->type, id, NULL);
            fparams->shift(param);
            Expression *ie = new IdentifierExp(Loc(), id);
            Expressions *arguments = new Expressions();
            Expression *index = new IdentifierExp(Loc(), Id::p);
            arguments->push(index);
            result = new ArrayExp(Loc(), ie, arguments);
        }

        void visit(SliceExp *e)
        {
            Identifier *id = Identifier::generateId("p", fparams->dim);
            Parameter *param = new Parameter(STCconst, e->type, id, NULL);
            fparams->shift(param);
            Expression *ie = new IdentifierExp(Loc(), id);
            Expressions *arguments = new Expressions();
            Expression *index = new IdentifierExp(Loc(), Id::p);
            arguments->push(index);
            result = new ArrayExp(Loc(), ie, arguments);
        }

        void visit(AssignExp *e)
        {
            /* Evaluate assign expressions right to left
             */
            Expression *ex2 = buildArrayLoop(e->e2);
            /* Need the cast because:
             *   b = c + p[i];
             * where b is a byte fails because (c + p[i]) is an int
             * which cannot be implicitly cast to byte.
             */
            ex2 = new CastExp(Loc(), ex2, e->e1->type->nextOf());
            Expression *ex1 = buildArrayLoop(e->e1);
            Parameter *param = (*fparams)[0];
            param->storageClass = 0;
            result = new AssignExp(Loc(), ex1, ex2);
        }

        void visit(BinAssignExp *e)
        {
            /* Evaluate assign expressions right to left
             */
            Expression *ex2 = buildArrayLoop(e->e2);
            Expression *ex1 = buildArrayLoop(e->e1);
            Parameter *param = (*fparams)[0];
            param->storageClass = 0;
            switch(e->op)
            {
            case TOKaddass: result = new AddAssignExp(e->loc, ex1, ex2); return;
            case TOKminass: result = new MinAssignExp(e->loc, ex1, ex2); return;
            case TOKmulass: result = new MulAssignExp(e->loc, ex1, ex2); return;
            case TOKdivass: result = new DivAssignExp(e->loc, ex1, ex2); return;
            case TOKmodass: result = new ModAssignExp(e->loc, ex1, ex2); return;
            case TOKxorass: result = new XorAssignExp(e->loc, ex1, ex2); return;
            case TOKandass: result = new AndAssignExp(e->loc, ex1, ex2); return;
            case TOKorass:  result = new OrAssignExp(e->loc, ex1, ex2); return;
            case TOKpowass: result = new PowAssignExp(e->loc, ex1, ex2); return;
            default:
                assert(0);
            }
        }

        void visit(NegExp *e)
        {
            Expression *ex1 = buildArrayLoop(e->e1);
            result = new NegExp(Loc(), ex1);
        }

        void visit(ComExp *e)
        {
            Expression *ex1 = buildArrayLoop(e->e1);
            result = new ComExp(Loc(), ex1);
        }

        void visit(BinExp *e)
        {
            switch(e->op)
            {
            case TOKadd:
            case TOKmin:
            case TOKmul:
            case TOKdiv:
            case TOKmod:
            case TOKxor:
            case TOKand:
            case TOKor:
            case TOKpow:
            {
                /* Evaluate assign expressions left to right
                 */
                BinExp *be = (BinExp *)e->copy();
                be->e1 = buildArrayLoop(be->e1);
                be->e2 = buildArrayLoop(be->e2);
                be->type = NULL;
                result = be;
                return;
            }
            default:
                visit((Expression *)e);
                return;
            }
        }

        Expression *buildArrayLoop(Expression *e)
        {
            e->accept(this);
            return result;
        }
    };

    BuildArrayLoopVisitor v(fparams);
    return v.buildArrayLoop(e);
}

/***********************************************
 * Test if operand is a valid array op operand.
 */

bool isArrayOperand(Expression *e)
{
    //printf("Expression::isArrayOperand() %s\n", e->toChars());
    if (e->op == TOKslice)
        return true;
    if (e->op == TOKarrayliteral)
    {
        Type *t = e->type->toBasetype();
        while (t->ty == Tarray || t->ty == Tsarray)
            t = t->nextOf()->toBasetype();
        return (t->ty != Tvoid);
    }
    if (e->type->toBasetype()->ty == Tarray)
    {
        switch (e->op)
        {
        case TOKadd:
        case TOKmin:
        case TOKmul:
        case TOKdiv:
        case TOKmod:
        case TOKxor:
        case TOKand:
        case TOKor:
        case TOKassign:
        case TOKaddass:
        case TOKminass:
        case TOKmulass:
        case TOKdivass:
        case TOKmodass:
        case TOKxorass:
        case TOKandass:
        case TOKorass:
        case TOKpow:
        case TOKpowass:
        case TOKneg:
        case TOKtilde:
            return true;

        default:
            break;
        }
    }
    return false;
}
