compiler.h

/*
    Aseba - an event-based framework for distributed robot control
    Copyright (C) 2007--2016:
        Stephane Magnenat <stephane at magnenat dot net>
        (http://stephane.magnenat.net)
        and other contributors, see authors.txt for details
    
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation, version 3 of the License.
    
    This program 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 Lesser General Public License for more details.
    
    You should have received a copy of the GNU Lesser General Public License
    along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef __ASEBA_COMPILER_H
#define __ASEBA_COMPILER_H

#include <vector>
#include <deque>
#include <string>
#include <map>
#include <set>
#include <utility>
#include <istream>

#include "errors_code.h"
#include "../common/types.h"
#include "../common/utils/FormatableString.h"

namespace Aseba
{

    // pre-declaration
    struct Node;
    struct ProgramNode;
    struct StatementNode;
    struct BinaryArithmeticNode;
    struct AssignmentNode;
    struct TupleVectorNode;
    struct MemoryVectorNode;
    
    typedef std::map<std::wstring, std::pair<unsigned, unsigned> > VariablesMap;
    typedef std::map<std::wstring, unsigned> FunctionsMap;
    
    struct TargetDescription
    {
        struct NamedVariable
        {
            NamedVariable(const std::wstring &name, unsigned size) : size(size), name(name) {}
            NamedVariable() : size(0) {}
            
            unsigned size; 
            std::wstring name; 
        };
        
        struct LocalEvent
        {
            std::wstring name; 
            std::wstring description; 
        };
        
        struct NativeFunctionParameter
        {
            NativeFunctionParameter(const std::wstring &name, int size) : size(size), name(name) {}
            NativeFunctionParameter() : size(0) {}

            int size; 
            std::wstring name; 
        };
        
        struct NativeFunction
        {
            NativeFunction(const std::wstring &name, const std::wstring &description) : name(name), description(description) {}
            NativeFunction() {}

            std::wstring name; 
            std::wstring description; 
            std::vector<NativeFunctionParameter> parameters; 
        };
        
        std::wstring name; 
        unsigned protocolVersion; 
        
        unsigned bytecodeSize; 
        unsigned variablesSize; 
        unsigned stackSize; 
        
        std::vector<NamedVariable> namedVariables; 
        std::vector<LocalEvent> localEvents; 
        std::vector<NativeFunction> nativeFunctions; 
        
        TargetDescription() : protocolVersion(0), bytecodeSize(0), variablesSize(0), stackSize(0) { }
        uint16 crc() const;
        VariablesMap getVariablesMap(unsigned& freeVariableIndex) const;
        FunctionsMap getFunctionsMap() const;
    };
    
    struct BytecodeElement
    {
        BytecodeElement();
        BytecodeElement(unsigned short bytecode) : bytecode(bytecode), line(0) { }
        BytecodeElement(unsigned short bytecode, unsigned short line) : bytecode(bytecode), line(line) { }
        operator unsigned short () const { return bytecode; }
        unsigned getWordSize() const;
        
        unsigned short bytecode; 
        unsigned short line; 
    };
    
    struct BytecodeVector: std::deque<BytecodeElement>
    {
        BytecodeVector() : maxStackDepth(0), callDepth(0), lastLine(0) { }
        
        unsigned maxStackDepth; 
        unsigned callDepth; 
        unsigned lastLine; 
        
        void push_back(const BytecodeElement& be)
        {
            std::deque<BytecodeElement>::push_back(be);
            lastLine = be.line;
        }
        
        void changeStopToRetSub();
        unsigned short getTypeOfLast() const;
        
        typedef std::map<unsigned, unsigned> EventAddressesToIdsMap;
        EventAddressesToIdsMap getEventAddressesToIds() const;
    };
    
    // predeclaration
    struct PreLinkBytecode;
    
    struct SourcePos
    {
        unsigned character; 
        unsigned row; 
        unsigned column; 
        bool valid; 
        
        SourcePos(unsigned character, unsigned row, unsigned column) : character(character - 1), row(row), column(column - 1) { valid = true; }
        SourcePos() : character(0), row(0), column(0), valid(false) { }
        std::wstring toWString() const;
    };
    
    class ErrorMessages
    {
        public:
            ErrorMessages();

            typedef const std::wstring (*ErrorCallback)(ErrorCode error);
            static const std::wstring defaultCallback(ErrorCode error);
    };

    struct Error
    {
        SourcePos pos; 
        std::wstring message; 
        Error(const SourcePos& pos, const std::wstring& message) : pos(pos), message(message) { }
        Error() { message = L"not defined"; }

        std::wstring toWString() const;
    };

    struct TranslatableError : public Error
    {
        TranslatableError() : Error() {}
        TranslatableError(const SourcePos& pos, ErrorCode error);
        TranslatableError &arg(int value, int fieldWidth = 0, int base = 10, wchar_t fillChar = ' ');
        TranslatableError &arg(long int value, int fieldWidth = 0, int base = 10, wchar_t fillChar = ' ');
        TranslatableError &arg(unsigned value, int fieldWidth = 0, int base = 10, wchar_t fillChar = ' ');
        TranslatableError &arg(float value, int fieldWidth = 0, int precision = 6, wchar_t fillChar = ' ');
        TranslatableError &arg(const std::wstring& value);

        Error toError(void);
        static void setTranslateCB(ErrorMessages::ErrorCallback newCB);

        static ErrorMessages::ErrorCallback translateCB;
        WFormatableString message;
    };

    typedef std::vector<std::wstring> VariablesNamesVector;
    
    struct NamedValue
    {
        NamedValue(const std::wstring& name, int value) : name(name), value(value) {}
        
        std::wstring name; 
        int value; 
    };
    
    typedef NamedValue EventDescription;
    
    typedef NamedValue ConstantDefinition;
    
    struct NamedValuesVector: public std::vector<NamedValue>
    {
        bool contains(const std::wstring& s, size_t* position = 0) const;
    };
    
    typedef NamedValuesVector EventsDescriptionsVector;
    
    typedef NamedValuesVector ConstantsDefinitions;
    
    struct CommonDefinitions
    {
        EventsDescriptionsVector events;
        ConstantsDefinitions constants;
        
        void clear() { events.clear(); constants.clear(); }
    };
    
    typedef std::vector<short int> VariablesDataVector;
    
    class Compiler
    {
    public:
        struct Token
        {
            enum Type
            {
                TOKEN_END_OF_STREAM = 0,
                TOKEN_STR_when,
                TOKEN_STR_emit,
                TOKEN_STR_hidden_emit,
                TOKEN_STR_for,
                TOKEN_STR_in,
                TOKEN_STR_step,
                TOKEN_STR_while,
                TOKEN_STR_do,
                TOKEN_STR_if,
                TOKEN_STR_then,
                TOKEN_STR_else,
                TOKEN_STR_elseif,
                TOKEN_STR_end,
                TOKEN_STR_var,
                TOKEN_STR_const,
                TOKEN_STR_call,
                TOKEN_STR_sub,
                TOKEN_STR_callsub,
                TOKEN_STR_onevent,
                TOKEN_STR_abs,
                TOKEN_STR_return,
                TOKEN_STRING_LITERAL,
                TOKEN_INT_LITERAL,
                TOKEN_PAR_OPEN,
                TOKEN_PAR_CLOSE,
                TOKEN_BRACKET_OPEN,
                TOKEN_BRACKET_CLOSE,
                TOKEN_COLON,
                TOKEN_COMMA,
                TOKEN_ASSIGN,
                TOKEN_OP_OR,
                TOKEN_OP_AND,
                TOKEN_OP_NOT,

                TOKEN_OP_EQUAL,         // group of tokens, don't split or mess up
                TOKEN_OP_NOT_EQUAL,     //
                TOKEN_OP_BIGGER,        //
                TOKEN_OP_BIGGER_EQUAL,      //
                TOKEN_OP_SMALLER,       //
                TOKEN_OP_SMALLER_EQUAL,     //

                TOKEN_OP_ADD,           // group of 2 tokens, don't split or mess up
                TOKEN_OP_NEG,           //
                TOKEN_OP_MULT,          // group of 3 tokens, don't split or mess up
                TOKEN_OP_DIV,           //
                TOKEN_OP_MOD,           //
                TOKEN_OP_SHIFT_LEFT,        // group of 2 tokens, don't split or mess up
                TOKEN_OP_SHIFT_RIGHT,       //
                TOKEN_OP_BIT_OR,        // group of 4 tokens, don't split or mess up
                TOKEN_OP_BIT_XOR,       //
                TOKEN_OP_BIT_AND,       //
                TOKEN_OP_BIT_NOT,       //

                TOKEN_OP_ADD_EQUAL,     // group of 12 tokens, don't split or mess up
                TOKEN_OP_NEG_EQUAL,     //
                TOKEN_OP_MULT_EQUAL,        //
                TOKEN_OP_DIV_EQUAL,     //
                TOKEN_OP_MOD_EQUAL,     //
                TOKEN_OP_SHIFT_LEFT_EQUAL,  //
                TOKEN_OP_SHIFT_RIGHT_EQUAL, //
                TOKEN_OP_BIT_OR_EQUAL,      //
                TOKEN_OP_BIT_XOR_EQUAL,     //
                TOKEN_OP_BIT_AND_EQUAL,     //

                TOKEN_OP_PLUS_PLUS,
                TOKEN_OP_MINUS_MINUS

            } type; 
            std::wstring sValue; 
            int iValue; 
            SourcePos pos;
            
            Token() : type(TOKEN_END_OF_STREAM), iValue(0) {}
            Token(Type type, SourcePos pos = SourcePos(), const std::wstring& value = L"");
            const std::wstring typeName() const;
            std::wstring toWString() const;
            operator Type () const { return type; }
        };
        
        struct SubroutineDescriptor
        {
            std::wstring name;
            unsigned address;
            unsigned line;
            
            SubroutineDescriptor(const std::wstring& name, unsigned address, unsigned line) : name(name), address(address), line(line) {}
        };
        typedef std::vector<SubroutineDescriptor> SubroutineTable;
        typedef std::map<std::wstring, unsigned> SubroutineReverseTable;
        typedef std::set<unsigned> ImplementedEvents;
        typedef std::map<std::wstring, int> ConstantsMap;
        typedef std::map<std::wstring, unsigned> EventsMap;

        friend struct AssignmentNode;
        friend struct CallSubNode;
    
    public:
        Compiler();
        void setTargetDescription(const TargetDescription *description);
        const TargetDescription *getTargetDescription() const { return targetDescription;}
        const VariablesMap *getVariablesMap() const { return &variablesMap; }
        const SubroutineTable *getSubroutineTable() const { return &subroutineTable; }
        void setCommonDefinitions(const CommonDefinitions *definitions);
        bool compile(std::wistream& source, BytecodeVector& bytecode, unsigned& allocatedVariablesCount, Error &errorDescription, std::wostream* dump = 0);
        void setTranslateCallback(ErrorMessages::ErrorCallback newCB) { TranslatableError::setTranslateCB(newCB); }
        static std::wstring translate(ErrorCode error) { return TranslatableError::translateCB(error); }
        static bool isKeyword(const std::wstring& word);
        
    protected:
        void internalCompilerError() const;
        void expect(const Token::Type& type) const;
        unsigned expectUInt12Literal() const;
        unsigned expectUInt16Literal() const;
        unsigned expectPositiveInt16Literal() const;
        int expectAbsoluteInt16Literal(bool negative) const;
        unsigned expectPositiveConstant() const;
        int expectConstant() const;
        unsigned expectPositiveInt16LiteralOrConstant() const;
        int expectInt16Literal();
        int expectInt16LiteralOrConstant();
        unsigned expectGlobalEventId() const;
        unsigned expectAnyEventId() const;
        std::wstring eventName(unsigned eventId) const;
        template <int length>
        bool isOneOf(const Token::Type types[length]) const;
        template <int length>
        void expectOneOf(const Token::Type types[length]) const;

        void freeTemporaryMemory();
        unsigned allocateTemporaryMemory(const SourcePos varPos, const unsigned size);
        AssignmentNode* allocateTemporaryVariable(const SourcePos varPos, Node* rValue);

        VariablesMap::const_iterator findVariable(const std::wstring& name, const SourcePos& pos) const;
        FunctionsMap::const_iterator findFunction(const std::wstring& name, const SourcePos& pos) const;
        ConstantsMap::const_iterator findConstant(const std::wstring& name, const SourcePos& pos) const;
        EventsMap::const_iterator findGlobalEvent(const std::wstring& name, const SourcePos& pos) const;
        EventsMap::const_iterator findAnyEvent(const std::wstring& name, const SourcePos& pos) const;
        SubroutineReverseTable::const_iterator findSubroutine(const std::wstring& name, const SourcePos& pos) const;
        bool constantExists(const std::wstring& name) const;
        void buildMaps();
        void tokenize(std::wistream& source);
        wchar_t getNextCharacter(std::wistream& source, SourcePos& pos);
        bool testNextCharacter(std::wistream& source, SourcePos& pos, wchar_t test, Token::Type tokenIfTrue);
        void dumpTokens(std::wostream &dest) const;
        bool verifyStackCalls(PreLinkBytecode& preLinkBytecode);
        bool link(const PreLinkBytecode& preLinkBytecode, BytecodeVector& bytecode);
        void disassemble(BytecodeVector& bytecode, const PreLinkBytecode& preLinkBytecode, std::wostream& dump) const;
        
    protected:
        Node* parseProgram();
        
        Node* parseStatement();
        
        Node* parseBlockStatement();
        
        Node* parseReturn();
        void parseConstDef();
        Node* parseVarDef();
        AssignmentNode* parseVarDefInit(MemoryVectorNode* lValue);
        Node* parseAssignment();
        Node* parseIfWhen(bool edgeSensitive);
        Node* parseFor();
        Node* parseWhile();
        Node* parseOnEvent();
        Node* parseEmit(bool shorterArgsAllowed = false);
        Node* parseSubDecl();
        Node* parseCallSub();
        
        Node* parseOr();
        Node* parseAnd();
        Node* parseNot();
        
        Node* parseCondition();
        
        Node *parseBinaryOrExpression();
        Node *parseBinaryXorExpression();
        Node *parseBinaryAndExpression();
        
        Node* parseShiftExpression();
        Node* parseAddExpression();
        Node* parseMultExpression();
        Node* parseUnaryExpression();
        Node* parseFunctionCall();

        TupleVectorNode* parseTupleVector(bool compatibility = false);
        Node* parseConstantAndVariable();
        MemoryVectorNode* parseVariable();
        unsigned parseVariableDefSize();
        Node* tryParsingConstantExpression(SourcePos pos, int& constantResult);
        int expectConstantExpression(SourcePos pos, Node* tree);
    
    protected:
        std::deque<Token> tokens; 
        VariablesMap variablesMap; 
        ImplementedEvents implementedEvents; 
        FunctionsMap functionsMap; 
        ConstantsMap constantsMap; 
        EventsMap globalEventsMap; 
        EventsMap allEventsMap; 
        SubroutineTable subroutineTable; 
        SubroutineReverseTable subroutineReverseTable; 
        unsigned freeVariableIndex; 
        unsigned endVariableIndex; 
        const TargetDescription *targetDescription; 
        const CommonDefinitions *commonDefinitions; 

        ErrorMessages translator;
    }; // Compiler
    
    struct PreLinkBytecode
    {
        typedef std::map<unsigned, BytecodeVector> EventsBytecode;
        EventsBytecode events; 
        
        typedef std::map<unsigned, BytecodeVector> SubroutinesBytecode;
        SubroutinesBytecode subroutines; 
        
        BytecodeVector *current; 
        
        PreLinkBytecode();
        
        void fixup(const Compiler::SubroutineTable &subroutineTable);
    };
    
} // namespace Aseba

#endif