aseba: tree.h Source File

Go to the documentation of this file.
00001 /*
00002         Aseba - an event-based framework for distributed robot control
00003         Copyright (C) 2007--2012:
00004                 Stephane Magnenat <stephane at magnenat dot net>
00005                 (http://stephane.magnenat.net)
00006                 and other contributors, see authors.txt for details
00007         
00008         This program is free software: you can redistribute it and/or modify
00009         it under the terms of the GNU Lesser General Public License as published
00010         by the Free Software Foundation, version 3 of the License.
00011         
00012         This program is distributed in the hope that it will be useful,
00013         but WITHOUT ANY WARRANTY; without even the implied warranty of
00014         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015         GNU Lesser General Public License for more details.
00016         
00017         You should have received a copy of the GNU Lesser General Public License
00018         along with this program. If not, see <http://www.gnu.org/licenses/>.
00019 */
00020 
00021 #ifndef __TREE_H
00022 #define __TREE_H
00023 
00024 #include "compiler.h"
00025 #include "../common/consts.h"
00026 #include "../utils/FormatableString.h"
00027 #include <vector>
00028 #include <string>
00029 #include <ostream>
00030 #include <climits>
00031 #include <cassert>
00032 
00033 
00034 namespace Aseba
00035 {
00038 
00040         std::wstring binaryOperatorToString(AsebaBinaryOperator op);
00041         
00043         std::wstring unaryOperatorToString(AsebaUnaryOperator op);
00044         
00046         struct Node
00047         {
00049                 enum ReturnType
00050                 {
00051                         TYPE_UNIT = 0,
00052                         TYPE_BOOL,
00053                         TYPE_INT
00054                 };
00055                 
00057                 Node(const SourcePos& sourcePos) : sourcePos(sourcePos) { }             
00058                 virtual ~Node();
00060                 virtual Node* shallowCopy() = 0;
00062                 virtual Node* deepCopy();
00063                 
00065                 virtual void checkVectorSize() const;
00067                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00069                 virtual ReturnType typeCheck() const;
00071                 virtual Node* optimize(std::wostream* dump) = 0;
00073                 virtual unsigned getStackDepth() const;
00075                 virtual void emit(PreLinkBytecode& bytecodes) const = 0;
00076                 
00078                 virtual std::wstring toWString() const = 0;
00080                 virtual std::wstring toNodeName() const = 0;
00082                 virtual void dump(std::wostream& dest, unsigned& indent) const;
00083 
00085                 std::wstring typeName(const Node::ReturnType& type) const;
00087                 void expectType(const Node::ReturnType& expected, const Node::ReturnType& type) const;
00088 
00089                 enum MemoryErrorCode
00090                 {
00091                         E_NOVAL = UINT_MAX
00092                 };
00093                 virtual unsigned getVectorAddr() const;
00094                 virtual unsigned getVectorSize() const;
00095 
00097                 typedef std::vector<Node *> NodesVector;
00098                 NodesVector children; 
00099                 SourcePos sourcePos; 
00100         };
00101         
00103         struct BlockNode : Node
00104         {
00106                 BlockNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00107                 virtual BlockNode* shallowCopy() { return new BlockNode(*this); }
00108 
00109                 virtual Node* optimize(std::wostream* dump);
00110                 virtual void emit(PreLinkBytecode& bytecodes) const;
00111                 virtual std::wstring toWString() const { return L"Block"; }
00112                 virtual std::wstring toNodeName() const { return L"block"; }
00113         };
00114         
00116         struct ProgramNode: BlockNode
00117         {
00119                 ProgramNode(const SourcePos& sourcePos) : BlockNode(sourcePos) { }
00120                 virtual ProgramNode* shallowCopy() { return new ProgramNode(*this); }
00121 
00122                 virtual void emit(PreLinkBytecode& bytecodes) const;
00123                 virtual std::wstring toWString() const { return L"ProgramBlock"; }
00124                 virtual std::wstring toNodeName() const { return L"program block"; }
00125         };
00126         
00130         struct AssignmentNode : Node
00131         {
00133                 AssignmentNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00134                 virtual AssignmentNode* shallowCopy() { return new AssignmentNode(*this); }
00135 
00136                 virtual void checkVectorSize() const;
00137                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index);
00138                 virtual ReturnType typeCheck() const;
00139                 virtual Node* optimize(std::wostream* dump);
00140                 virtual void emit(PreLinkBytecode& bytecodes) const;
00141                 virtual std::wstring toWString() const { return L"Assign"; }
00142                 virtual std::wstring toNodeName() const { return L"assignment"; }
00143         };
00144         
00149         struct IfWhenNode : Node
00150         {
00151                 bool edgeSensitive; 
00152                 unsigned endLine; 
00153                 
00155                 IfWhenNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00156                 virtual IfWhenNode* shallowCopy() { return new IfWhenNode(*this); }
00157 
00158                 virtual void checkVectorSize() const;
00159                 virtual ReturnType typeCheck() const;
00160                 virtual Node* optimize(std::wostream* dump);
00161                 virtual void emit(PreLinkBytecode& bytecodes) const;
00162                 virtual std::wstring toWString() const;
00163                 virtual std::wstring toNodeName() const { return L"if/when"; }
00164         };
00165         
00171         struct FoldedIfWhenNode : Node
00172         {
00173                 AsebaBinaryOperator op; 
00174                 bool edgeSensitive; 
00175                 unsigned endLine; 
00176                 
00178                 FoldedIfWhenNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00179                 virtual FoldedIfWhenNode* shallowCopy() { return new FoldedIfWhenNode(*this); }
00180 
00181                 virtual void checkVectorSize() const;
00182                 virtual Node* optimize(std::wostream* dump);
00183                 virtual unsigned getStackDepth() const;
00184                 virtual void emit(PreLinkBytecode& bytecodes) const;
00185                 virtual std::wstring toWString() const;
00186                 virtual std::wstring toNodeName() const { return L"folded if/when"; }
00187         };
00188         
00192         struct WhileNode : Node
00193         {
00195                 WhileNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00196                 virtual WhileNode* shallowCopy() { return new WhileNode(*this); }
00197 
00198                 virtual void checkVectorSize() const;
00199                 virtual ReturnType typeCheck() const;
00200                 virtual Node* optimize(std::wostream* dump);
00201                 virtual void emit(PreLinkBytecode& bytecodes) const;
00202                 virtual std::wstring toWString() const;
00203                 virtual std::wstring toNodeName() const { return L"while"; }
00204         };
00205         
00210         struct FoldedWhileNode : Node
00211         {
00212                 AsebaBinaryOperator op; 
00213                 
00215                 FoldedWhileNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00216                 virtual FoldedWhileNode* shallowCopy() { return new FoldedWhileNode(*this); }
00217 
00218                 virtual void checkVectorSize() const;
00219                 virtual Node* optimize(std::wostream* dump);
00220                 virtual unsigned getStackDepth() const;
00221                 virtual void emit(PreLinkBytecode& bytecodes) const;
00222                 virtual std::wstring toWString() const;
00223                 virtual std::wstring toNodeName() const { return L"folded while"; }
00224         };
00225         
00228         struct EventDeclNode : Node
00229         {
00230                 unsigned eventId; 
00231                 
00232                 EventDeclNode(const SourcePos& sourcePos, unsigned eventId = 0);
00233                 virtual EventDeclNode* shallowCopy() { return new EventDeclNode(*this); }
00234 
00235                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00236                 virtual Node* optimize(std::wostream* dump);
00237                 virtual void emit(PreLinkBytecode& bytecodes) const;
00238                 virtual std::wstring toWString() const;
00239                 virtual std::wstring toNodeName() const { return L"event declaration"; }
00240         };
00241         
00244         struct EmitNode : Node
00245         {
00246                 unsigned eventId; 
00247                 unsigned arrayAddr; 
00248                 unsigned arraySize; 
00249                 
00251                 EmitNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00252                 virtual EmitNode* shallowCopy() { return new EmitNode(*this); }
00253 
00254                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00255                 virtual Node* optimize(std::wostream* dump);
00256                 virtual void emit(PreLinkBytecode& bytecodes) const;
00257                 virtual std::wstring toWString() const;
00258                 virtual std::wstring toNodeName() const { return L"emit"; }
00259         };
00260         
00263         struct SubDeclNode : Node
00264         {
00265                 unsigned subroutineId; 
00266                 
00267                 SubDeclNode(const SourcePos& sourcePos, unsigned subroutineId);
00268                 virtual SubDeclNode* shallowCopy() { return new SubDeclNode(*this); }
00269 
00270                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00271                 virtual Node* optimize(std::wostream* dump);
00272                 virtual void emit(PreLinkBytecode& bytecodes) const;
00273                 virtual std::wstring toWString() const;
00274                 virtual std::wstring toNodeName() const { return L"subroutine declaration"; }
00275         };
00276         
00279         struct CallSubNode : Node
00280         {
00281                 unsigned subroutineId; 
00282                 
00283                 CallSubNode(const SourcePos& sourcePos, unsigned subroutineId);
00284                 virtual CallSubNode* shallowCopy() { return new CallSubNode(*this); }
00285 
00286                 virtual Node* optimize(std::wostream* dump);
00287                 virtual void emit(PreLinkBytecode& bytecodes) const;
00288                 virtual std::wstring toWString() const;
00289                 virtual std::wstring toNodeName() const { return L"subroutine call"; }
00290         };
00291         
00295         struct BinaryArithmeticNode : Node
00296         {
00297                 AsebaBinaryOperator op; 
00298                 
00299                 BinaryArithmeticNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00300                 BinaryArithmeticNode(const SourcePos& sourcePos, AsebaBinaryOperator op, Node *left, Node *right);
00301                 virtual BinaryArithmeticNode* shallowCopy() { return new BinaryArithmeticNode(*this); }
00302 
00303                 void deMorganNotRemoval();
00304                 
00305                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00306                 virtual ReturnType typeCheck() const;
00307                 virtual Node* optimize(std::wostream* dump);
00308                 virtual unsigned getStackDepth() const;
00309                 virtual void emit(PreLinkBytecode& bytecodes) const;
00310                 virtual std::wstring toWString() const;
00311                 virtual std::wstring toNodeName() const { return L"binary function"; }
00312                 
00313                 static BinaryArithmeticNode *fromComparison(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
00314                 static BinaryArithmeticNode *fromShiftExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
00315                 static BinaryArithmeticNode *fromAddExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
00316                 static BinaryArithmeticNode *fromMultExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
00317                 static BinaryArithmeticNode *fromBinaryExpression(const SourcePos& sourcePos, Compiler::Token::Type op, Node *left, Node *right);
00318         };
00319         
00322         struct UnaryArithmeticNode : Node
00323         {
00324                 AsebaUnaryOperator op; 
00325                 
00327                 UnaryArithmeticNode(const SourcePos& sourcePos) : Node(sourcePos) { }
00328                 UnaryArithmeticNode(const SourcePos& sourcePos, AsebaUnaryOperator op, Node *child);
00329                 virtual UnaryArithmeticNode* shallowCopy() { return new UnaryArithmeticNode(*this); }
00330 
00331                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00332                 virtual ReturnType typeCheck() const;
00333                 virtual Node* optimize(std::wostream* dump);
00334                 virtual void emit(PreLinkBytecode& bytecodes) const;
00335                 virtual std::wstring toWString() const;
00336                 virtual std::wstring toNodeName() const { return L"unary function"; }
00337         };
00338         
00343         struct ImmediateNode : Node
00344         {
00345                 int value; 
00346                 
00348                 ImmediateNode(const SourcePos& sourcePos, int value) : Node(sourcePos), value(value) { }
00349                 virtual ImmediateNode* shallowCopy() { return new ImmediateNode(*this); }
00350 
00351                 virtual Node* expandToAsebaTree(std::wostream *dump, unsigned int index = 0) { assert(index == 0); return shallowCopy(); }
00352                 virtual ReturnType typeCheck() const { return TYPE_INT; }
00353                 virtual Node* optimize(std::wostream* dump);
00354                 virtual unsigned getStackDepth() const;
00355                 virtual void emit(PreLinkBytecode& bytecodes) const;
00356                 virtual std::wstring toWString() const;
00357                 virtual std::wstring toNodeName() const { return L"constant"; }
00358 
00359                 virtual unsigned getVectorSize() const { return 1; }
00360         };
00361         
00364         struct StoreNode : Node
00365         {
00366                 unsigned varAddr; 
00367                 
00369                 StoreNode(const SourcePos& sourcePos, unsigned varAddr) : Node(sourcePos), varAddr(varAddr) { }
00370                 virtual StoreNode* shallowCopy() { return new StoreNode(*this); }
00371 
00372                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00373                 virtual Node* optimize(std::wostream* dump);
00374                 virtual void emit(PreLinkBytecode& bytecodes) const;
00375                 virtual std::wstring toWString() const;
00376                 virtual std::wstring toNodeName() const { return L"variable access (write)"; }
00377 
00378                 virtual unsigned getVectorAddr() const { return varAddr; }
00379                 virtual unsigned getVectorSize() const { return 1; }
00380         };
00381         
00384         struct LoadNode : Node
00385         {
00386                 unsigned varAddr; 
00387 
00389                 LoadNode(const SourcePos& sourcePos, unsigned varAddr) : Node(sourcePos), varAddr(varAddr) { }
00390                 virtual LoadNode* shallowCopy() { return new LoadNode(*this); }
00391 
00392                 virtual ReturnType typeCheck() const { return TYPE_INT; }
00393                 virtual Node* optimize(std::wostream* dump);
00394                 virtual unsigned getStackDepth() const;
00395                 virtual void emit(PreLinkBytecode& bytecodes) const;
00396                 virtual std::wstring toWString() const;
00397                 virtual std::wstring toNodeName() const { return L"variable access (read)"; }
00398 
00399                 virtual unsigned getVectorAddr() const { return varAddr; }
00400                 virtual unsigned getVectorSize() const { return 1; }
00401         };
00402 
00405         struct ArrayWriteNode : Node
00406         {
00407                 unsigned arrayAddr; 
00408                 unsigned arraySize; 
00409                 std::wstring arrayName; 
00410                 
00411                 ArrayWriteNode(const SourcePos& sourcePos, unsigned arrayAddr, unsigned arraySize, const std::wstring &arrayName);
00412                 virtual ArrayWriteNode* shallowCopy() { return new ArrayWriteNode(*this); }
00413 
00414                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00415                 virtual Node* optimize(std::wostream* dump);
00416                 virtual void emit(PreLinkBytecode& bytecodes) const;
00417                 virtual std::wstring toWString() const;
00418                 virtual std::wstring toNodeName() const { return L"array access (write)"; }
00419 
00420                 virtual unsigned getVectorAddr() const { return arrayAddr; }
00421                 virtual unsigned getVectorSize() const { return 1; }
00422         };
00423         
00426         struct ArrayReadNode : Node
00427         {
00428                 unsigned arrayAddr; 
00429                 unsigned arraySize; 
00430                 std::wstring arrayName; 
00431 
00432                 ArrayReadNode(const SourcePos& sourcePos, unsigned arrayAddr, unsigned arraySize, const std::wstring &arrayName);
00433                 virtual ArrayReadNode* shallowCopy() { return new ArrayReadNode(*this); }
00434 
00435                 virtual ReturnType typeCheck() const { return TYPE_INT; }
00436                 virtual Node* optimize(std::wostream* dump);
00437                 virtual void emit(PreLinkBytecode& bytecodes) const;
00438                 virtual std::wstring toWString() const;
00439                 virtual std::wstring toNodeName() const { return L"array access (read)"; }
00440 
00441                 virtual unsigned getVectorAddr() const { return arrayAddr; }
00442                 virtual unsigned getVectorSize() const { return 1; }
00443         };
00444 
00447         struct CallNode : Node
00448         {
00449                 unsigned funcId; 
00450                 std::vector<unsigned> argumentsAddr; 
00451                 
00452                 CallNode(const SourcePos& sourcePos, unsigned funcId);
00453                 virtual CallNode* shallowCopy() { return new CallNode(*this); }
00454 
00455                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00456                 virtual Node* optimize(std::wostream* dump);
00457                 virtual unsigned getStackDepth() const;
00458                 virtual void emit(PreLinkBytecode& bytecodes) const;
00459                 virtual std::wstring toWString() const;
00460                 virtual std::wstring toNodeName() const { return L"native function call"; }
00461         };
00462         
00465         struct ReturnNode : Node
00466         {
00467                 ReturnNode(const SourcePos& sourcePos) : Node(sourcePos) {}
00468                 virtual ReturnNode* shallowCopy() { return new ReturnNode(*this); }
00469 
00470                 virtual ReturnType typeCheck() const { return TYPE_UNIT; }
00471                 virtual Node* optimize(std::wostream* dump) { return this; }
00472                 virtual unsigned getStackDepth() const { return 0; }
00473                 virtual void emit(PreLinkBytecode& bytecodes) const;
00474                 virtual std::wstring toWString() const { return L"Return"; }
00475                 virtual std::wstring toNodeName() const { return L"return"; } 
00476         };
00477 
00478         /*** Nodes for abstract operations (e.g. vectors) ***/
00479 
00483         struct AbstractTreeNode : Node
00484         {
00486                 AbstractTreeNode(const SourcePos& sourcePos) : Node(sourcePos) {}
00487 
00488                 // Following operations should not be performed on abstraction nodes
00489                 virtual ReturnType typeCheck() const { abort(); }
00490                 virtual Node* optimize(std::wostream* dump) { abort(); }
00491                 virtual unsigned getStackDepth() const { abort(); }
00492                 virtual void emit(PreLinkBytecode& bytecodes) const { abort(); }
00493         };
00494 
00497         struct TupleVectorNode : AbstractTreeNode
00498         {
00500                 TupleVectorNode(const SourcePos& sourcePos) : AbstractTreeNode(sourcePos) {}
00501                 TupleVectorNode(const SourcePos& sourcePos, int value) : AbstractTreeNode(sourcePos) { children.push_back(new ImmediateNode(sourcePos, value)); }
00502                 virtual TupleVectorNode* shallowCopy() { return new TupleVectorNode(*this); }
00503 
00504                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00505                 virtual std::wstring toWString() const;
00506                 virtual std::wstring toNodeName() const { return L"array of constants"; }
00507                 virtual void dump(std::wostream& dest, unsigned& indent) const;
00508 
00509                 virtual unsigned getVectorSize() const;
00510 
00511                 virtual bool isImmediateVector() const;
00512                 virtual int getImmediateValue(unsigned index) const;
00513                 virtual void addImmediateValue(int value) { children.push_back(new ImmediateNode(sourcePos, value)); }
00514         };
00515 
00524         struct MemoryVectorNode : AbstractTreeNode
00525         {
00526                 unsigned arrayAddr; 
00527                 unsigned arraySize; 
00528                 std::wstring arrayName; 
00529                 bool write; 
00530 
00531                 MemoryVectorNode(const SourcePos& sourcePos, unsigned arrayAddr, unsigned arraySize, const std::wstring &arrayName);
00532                 virtual MemoryVectorNode* shallowCopy() { return new MemoryVectorNode(*this); }
00533 
00534                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00535                 virtual std::wstring toWString() const;
00536                 virtual std::wstring toNodeName() const { return L"vector access"; }
00537 
00538                 virtual unsigned getVectorAddr() const;
00539                 virtual unsigned getVectorSize() const;
00540                 bool isAddressStatic() const;
00541 
00542                 virtual void setWrite(bool write) { this->write = write; }
00543         };
00544 
00549         struct ArithmeticAssignmentNode : AbstractTreeNode
00550         {
00551                 AsebaBinaryOperator op; 
00552 
00554                 ArithmeticAssignmentNode(const SourcePos& sourcePos, AsebaBinaryOperator op, Node *left, Node *right);
00555                 virtual ArithmeticAssignmentNode* shallowCopy() { return new ArithmeticAssignmentNode(*this); }
00556 
00557                 virtual void checkVectorSize() const;
00558                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00559                 virtual std::wstring toWString() const;
00560                 virtual std::wstring toNodeName() const { return L"arithmetic assignment"; }
00561 
00562                 static ArithmeticAssignmentNode* fromArithmeticAssignmentToken(const SourcePos& sourcePos, Compiler::Token::Type token, Node *left, Node *right);
00563 
00564         protected:
00565                 const static AsebaBinaryOperator operatorMap[];
00566                 static AsebaBinaryOperator getBinaryOperator(Compiler::Token::Type token);
00567         };
00568 
00572         struct UnaryArithmeticAssignmentNode : AbstractTreeNode
00573         {
00574                 AsebaBinaryOperator arithmeticOp; 
00575 
00577                 UnaryArithmeticAssignmentNode(const SourcePos& sourcePos, Compiler::Token::Type token, Node *memory);
00578                 virtual UnaryArithmeticAssignmentNode* shallowCopy() { return new UnaryArithmeticAssignmentNode(*this); }
00579 
00580                 virtual Node* expandToAsebaTree(std::wostream* dump, unsigned int index = 0);
00581                 virtual std::wstring toWString() const;
00582                 virtual std::wstring toNodeName() const { return L"unary arithmetic assignment"; }
00583         };
00584 
00587 }; // Aseba
00588 
00589 #endif