tree.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 __TREE_H
#define __TREE_H

#include "compiler.h"
#include "../common/consts.h"
#include "../common/utils/FormatableString.h"
#include <vector>
#include <string>
#include <ostream>
#include <climits>
#include <cassert>

#include <iostream>

namespace Aseba
{

    std::wstring binaryOperatorToString(AsebaBinaryOperator op);
    
    std::wstring unaryOperatorToString(AsebaUnaryOperator op);
    
    struct Node
    {
        enum ReturnType
        {
            TYPE_UNIT = 0,
            TYPE_BOOL,
            TYPE_INT
        };
        
        Node(const SourcePos& sourcePos) : sourcePos(sourcePos) { }     
        virtual ~Node();
        virtual Node* shallowCopy() = 0;
        virtual Node* deepCopy();
        
        virtual void checkVectorSize() const;
        virtual Node* expandAbstractNodes(std::wostream* dump);
        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0);
        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump) = 0;
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const = 0;
        
        virtual std::wstring toWString() const = 0;
        virtual std::wstring toNodeName() const = 0;
        virtual void dump(std::wostream& dest, unsigned& indent) const;

        std::wstring typeName(const Node::ReturnType& type) const;
        void expectType(const Node::ReturnType& expected, const Node::ReturnType& type) const;

        enum MemoryErrorCode
        {
            E_NOVAL = UINT_MAX
        };
        virtual unsigned getVectorAddr() const;
        virtual unsigned getVectorSize() const;

        typedef std::vector<Node *> NodesVector;
        NodesVector children; 
        SourcePos sourcePos; 
    };
    
    struct BlockNode : Node
    {
        BlockNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        virtual BlockNode* shallowCopy() { return new BlockNode(*this); }

        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const { return L"Block"; }
        virtual std::wstring toNodeName() const { return L"block"; }
    };
    
    struct ProgramNode: BlockNode
    {
        ProgramNode(const SourcePos& sourcePos) : BlockNode(sourcePos) { }
        virtual ProgramNode* shallowCopy() { return new ProgramNode(*this); }

        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const { return L"ProgramBlock"; }
        virtual std::wstring toNodeName() const { return L"program block"; }
    };
    
    struct AssignmentNode : Node
    {
        AssignmentNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        AssignmentNode(const SourcePos& sourcePos, Node* left, Node* right);
        virtual AssignmentNode* shallowCopy() { return new AssignmentNode(*this); }

        virtual void checkVectorSize() const;
        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0);
        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const { return L"Assign"; }
        virtual std::wstring toNodeName() const { return L"assignment"; }
    };
    
    struct IfWhenNode : Node
    {
        bool edgeSensitive; 
        unsigned endLine; 
        
        IfWhenNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        virtual IfWhenNode* shallowCopy() { return new IfWhenNode(*this); }

        virtual void checkVectorSize() const;
        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"if/when"; }
    };
    
    struct FoldedIfWhenNode : Node
    {
        AsebaBinaryOperator op; 
        bool edgeSensitive; 
        unsigned endLine; 
        
        FoldedIfWhenNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        virtual FoldedIfWhenNode* shallowCopy() { return new FoldedIfWhenNode(*this); }

        virtual void checkVectorSize() const;
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"folded if/when"; }
    };
    
    struct WhileNode : Node
    {
        WhileNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        virtual WhileNode* shallowCopy() { return new WhileNode(*this); }

        virtual void checkVectorSize() const;
        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"while"; }
    };
    
    struct FoldedWhileNode : Node
    {
        AsebaBinaryOperator op; 
        
        FoldedWhileNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        virtual FoldedWhileNode* shallowCopy() { return new FoldedWhileNode(*this); }

        virtual void checkVectorSize() const;
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"folded while"; }
    };
    
    struct EventDeclNode : Node
    {
        unsigned eventId; 
        
        EventDeclNode(const SourcePos& sourcePos, unsigned eventId = 0);
        virtual EventDeclNode* shallowCopy() { return new EventDeclNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"event declaration"; }
    };
    
    struct EmitNode : Node
    {
        unsigned eventId; 
        unsigned arrayAddr; 
        unsigned arraySize; 
        
        EmitNode(const SourcePos& sourcePos) : Node(sourcePos), eventId(0), arrayAddr(0), arraySize(0) { }
        virtual EmitNode* shallowCopy() { return new EmitNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"emit"; }
    };
    
    struct SubDeclNode : Node
    {
        unsigned subroutineId; 
        
        SubDeclNode(const SourcePos& sourcePos, unsigned subroutineId);
        virtual SubDeclNode* shallowCopy() { return new SubDeclNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"subroutine declaration"; }
    };
    
    struct CallSubNode : Node
    {
        std::wstring subroutineName; 
        unsigned subroutineId;

        CallSubNode(const SourcePos& sourcePos, const std::wstring& subroutineName);
        virtual CallSubNode* shallowCopy() { return new CallSubNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"subroutine call"; }
    };
    
    struct BinaryArithmeticNode : Node
    {
        AsebaBinaryOperator op; 
        
        BinaryArithmeticNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        BinaryArithmeticNode(const SourcePos& sourcePos, AsebaBinaryOperator op, Node *left, Node *right);
        virtual BinaryArithmeticNode* shallowCopy() { return new BinaryArithmeticNode(*this); }

        void deMorganNotRemoval();
        
        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"binary function"; }
        
        static BinaryArithmeticNode *fromComparison(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
        static BinaryArithmeticNode *fromShiftExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
        static BinaryArithmeticNode *fromAddExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
        static BinaryArithmeticNode *fromMultExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
        static BinaryArithmeticNode *fromBinaryExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
    };
    
    struct UnaryArithmeticNode : Node
    {
        AsebaUnaryOperator op; 
        
        UnaryArithmeticNode(const SourcePos& sourcePos) : Node(sourcePos) { }
        UnaryArithmeticNode(const SourcePos& sourcePos, AsebaUnaryOperator op, Node *child);
        virtual UnaryArithmeticNode* shallowCopy() { return new UnaryArithmeticNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler);
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"unary function"; }
    };
    
    struct ImmediateNode : Node
    {
        int value; 
        
        ImmediateNode(const SourcePos& sourcePos, int value) : Node(sourcePos), value(value) { }
        virtual ImmediateNode* shallowCopy() { return new ImmediateNode(*this); }

        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0);
        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_INT; }
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"constant"; }

        virtual unsigned getVectorSize() const { return 1; }
    };
    
    struct StoreNode : Node
    {
        unsigned varAddr; 
        
        StoreNode(const SourcePos& sourcePos, unsigned varAddr) : Node(sourcePos), varAddr(varAddr) { }
        virtual StoreNode* shallowCopy() { return new StoreNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"variable access (write)"; }

        virtual unsigned getVectorAddr() const { return varAddr; }
        virtual unsigned getVectorSize() const { return 1; }
    };
    
    struct LoadNode : Node
    {
        unsigned varAddr; 

        LoadNode(const SourcePos& sourcePos, unsigned varAddr) : Node(sourcePos), varAddr(varAddr) { }
        virtual LoadNode* shallowCopy() { return new LoadNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_INT; }
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"variable access (read)"; }

        virtual unsigned getVectorAddr() const { return varAddr; }
        virtual unsigned getVectorSize() const { return 1; }
    };

    struct ArrayWriteNode : Node
    {
        unsigned arrayAddr; 
        unsigned arraySize; 
        std::wstring arrayName; 
        
        ArrayWriteNode(const SourcePos& sourcePos, unsigned arrayAddr, unsigned arraySize, const std::wstring &arrayName);
        virtual ArrayWriteNode* shallowCopy() { return new ArrayWriteNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"array access (write)"; }

        virtual unsigned getVectorAddr() const { return arrayAddr; }
        virtual unsigned getVectorSize() const { return 1; }
    };
    
    struct ArrayReadNode : Node
    {
        unsigned arrayAddr; 
        unsigned arraySize; 
        std::wstring arrayName; 

        ArrayReadNode(const SourcePos& sourcePos, unsigned arrayAddr, unsigned arraySize, const std::wstring &arrayName);
        virtual ArrayReadNode* shallowCopy() { return new ArrayReadNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_INT; }
        virtual Node* optimize(std::wostream* dump);
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"array access (read)"; }

        virtual unsigned getVectorAddr() const { return arrayAddr; }
        virtual unsigned getVectorSize() const { return 1; }
    };
    
    struct LoadNativeArgNode : Node
    {
        unsigned tempAddr; 
        unsigned arrayAddr; 
        unsigned arraySize; 
        std::wstring arrayName; 
        
        LoadNativeArgNode(MemoryVectorNode* memoryNode, unsigned tempAddr);
        virtual LoadNativeArgNode* shallowCopy() { return new LoadNativeArgNode(*this); }
        
        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_INT; }
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"load native arg"; }
    };

    struct CallNode : Node
    {
        unsigned funcId; 
        std::vector<unsigned> templateArgs; 
        
        CallNode(const SourcePos& sourcePos, unsigned funcId);
        virtual CallNode* shallowCopy() { return new CallNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump);
        virtual unsigned getStackDepth() const;
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"native function call"; }
    };
    
    struct ReturnNode : Node
    {
        ReturnNode(const SourcePos& sourcePos) : Node(sourcePos) {}
        virtual ReturnNode* shallowCopy() { return new ReturnNode(*this); }

        virtual ReturnType typeCheck(Compiler* compiler) { return TYPE_UNIT; }
        virtual Node* optimize(std::wostream* dump) { return this; }
        virtual unsigned getStackDepth() const { return 0; }
        virtual void emit(PreLinkBytecode& bytecodes) const;
        virtual std::wstring toWString() const { return L"Return"; }
        virtual std::wstring toNodeName() const { return L"return"; } 
    };

    /*** Nodes for abstract operations (e.g. vectors) ***/

    struct AbstractTreeNode : Node
    {
        AbstractTreeNode(const SourcePos& sourcePos) : Node(sourcePos) {}

        virtual Node* expandAbstractNodes(std::wostream* dump) = 0;

        // Following operations should not be performed on abstraction nodes
        virtual ReturnType typeCheck(Compiler* compiler) { abort(); }
        virtual Node* optimize(std::wostream* dump) { abort(); }
        virtual unsigned getStackDepth() const { abort(); }
        virtual void emit(PreLinkBytecode& bytecodes) const { abort(); }
    };

    struct TupleVectorNode : AbstractTreeNode
    {
        TupleVectorNode(const SourcePos& sourcePos) : AbstractTreeNode(sourcePos) {}
        TupleVectorNode(const SourcePos& sourcePos, int value) : AbstractTreeNode(sourcePos) { children.push_back(new ImmediateNode(sourcePos, value)); }
        virtual TupleVectorNode* shallowCopy() { return new TupleVectorNode(*this); }

        virtual Node* expandAbstractNodes(std::wostream* dump);
        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0);
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"array of constants"; }
        virtual void dump(std::wostream& dest, unsigned& indent) const;

        virtual unsigned getVectorSize() const;

        virtual bool isImmediateVector() const;
        virtual int getImmediateValue(unsigned index) const;
        virtual void addImmediateValue(int value) { children.push_back(new ImmediateNode(sourcePos, value)); }
    };

    struct MemoryVectorNode : AbstractTreeNode
    {
        unsigned arrayAddr; 
        unsigned arraySize; 
        std::wstring arrayName; 
        bool write; 

        MemoryVectorNode(const SourcePos& sourcePos, unsigned arrayAddr, unsigned arraySize, const std::wstring &arrayName);
        virtual MemoryVectorNode* shallowCopy() { return new MemoryVectorNode(*this); }

        virtual Node* expandAbstractNodes(std::wostream* dump);
        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0);
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"vector access"; }

        virtual unsigned getVectorAddr() const;
        virtual unsigned getVectorSize() const;
        bool isAddressStatic() const;

        virtual void setWrite(bool write) { this->write = write; }
    };

    struct ArithmeticAssignmentNode : AbstractTreeNode
    {
        AsebaBinaryOperator op; 

        ArithmeticAssignmentNode(const SourcePos& sourcePos, AsebaBinaryOperator op, Node *left, Node *right);
        virtual ArithmeticAssignmentNode* shallowCopy() { return new ArithmeticAssignmentNode(*this); }

        virtual void checkVectorSize() const;
        virtual Node* expandAbstractNodes(std::wostream* dump);
        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0) { abort(); } // should not happen
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"arithmetic assignment"; }

        static ArithmeticAssignmentNode* fromArithmeticAssignmentToken(const SourcePos& sourcePos, Compiler::Token::Type token, Node *left, Node *right);

    protected:
        const static AsebaBinaryOperator operatorMap[];
        static AsebaBinaryOperator getBinaryOperator(Compiler::Token::Type token);
    };

    struct UnaryArithmeticAssignmentNode : AbstractTreeNode
    {
        AsebaBinaryOperator arithmeticOp; 

        UnaryArithmeticAssignmentNode(const SourcePos& sourcePos, Compiler::Token::Type token, Node *memory);
        virtual UnaryArithmeticAssignmentNode* shallowCopy() { return new UnaryArithmeticAssignmentNode(*this); }

        virtual Node* expandAbstractNodes(std::wostream* dump);
        virtual Node* expandVectorialNodes(std::wostream* dump, Compiler* compiler=0, unsigned int index = 0) { abort(); } // should not happen
        virtual std::wstring toWString() const;
        virtual std::wstring toNodeName() const { return L"unary arithmetic assignment"; }
    };

} // namespace Aseba

#endif