tree-expand.cpp
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 #include "compiler.h"
00022 #include "tree.h"
00023 #include "../utils/FormatableString.h"
00024 
00025 #include <cassert>
00026 #include <memory>
00027 #include <iostream>
00028 
00029 namespace Aseba
00030 {
00031         Node* Node::expandToAsebaTree(std::wostream *dump, unsigned int index)
00032         {
00033                 // recursively walk the tree and expand children
00034                 for (NodesVector::iterator it = children.begin(); it != children.end();)
00035                 {
00036                         *(it) = (*it)->expandToAsebaTree(dump, index);
00037                         ++it;
00038                 }
00039                 return this;
00040         }
00041 
00042 
00043         Node* AssignmentNode::expandToAsebaTree(std::wostream *dump, unsigned int index)
00044         {
00045                 assert(children.size() == 2);
00046 
00047                 MemoryVectorNode* leftVector = dynamic_cast<MemoryVectorNode*>(children[0]);
00048                 if (!leftVector)
00049                         throw TranslatableError(sourcePos, ERROR_INCORRECT_LEFT_VALUE).arg(children[0]->toNodeName());
00050                 leftVector->setWrite(true);
00051                 Node* rightVector = children[1];
00052 
00053                 std::auto_ptr<BlockNode> block(new BlockNode(sourcePos));
00054                 for (unsigned int i = 0; i < leftVector->getVectorSize(); i++)
00055                 {
00056                         // expand to left[i] = right[i]
00057                         std::auto_ptr<AssignmentNode> assignment(new AssignmentNode(sourcePos));
00058                         assignment->children.push_back(leftVector->expandToAsebaTree(dump, i));
00059                         assignment->children.push_back(rightVector->expandToAsebaTree(dump, i));
00060                         block->children.push_back(assignment.release());
00061                 }
00062 
00063                 delete this;
00064                 return block.release();
00065         }
00066 
00067 
00069         Node* BinaryArithmeticNode::expandToAsebaTree(std::wostream *dump, unsigned int index)
00070         {
00071                 std::auto_ptr<Node> left(children[0]->expandToAsebaTree(dump, index));
00072                 std::auto_ptr<Node> right(children[1]->expandToAsebaTree(dump, index));
00073                 return new BinaryArithmeticNode(sourcePos, op, left.release(), right.release());
00074         }
00075 
00076 
00078         Node* UnaryArithmeticNode::expandToAsebaTree(std::wostream *dump, unsigned int index)
00079         {
00080                 std::auto_ptr<Node> left(children[0]->expandToAsebaTree(dump, index));
00081                 return new UnaryArithmeticNode(sourcePos, op, left.release());
00082         }
00083 
00084 
00086         Node* TupleVectorNode::expandToAsebaTree(std::wostream *dump, unsigned int index)
00087         {
00088                 size_t total = 0;
00089                 size_t prevTotal = 0;
00090                 for (size_t i = 0; i < children.size(); i++)
00091                 {
00092                         prevTotal = total;
00093                         total += children[i]->getVectorSize();
00094                         if (index < total)
00095                         {
00096                                 return children[i]->expandToAsebaTree(dump, index-prevTotal);
00097                         }
00098                 }
00099                 assert(0);
00100                 return 0;
00101         }
00102 
00103 
00104         Node* MemoryVectorNode::expandToAsebaTree(std::wostream *dump, unsigned int index)
00105         {
00106                 assert(index < getVectorSize());
00107 
00108                 // get the optional index given in the Aseba code
00109                 TupleVectorNode* accessIndex = NULL;
00110                 if (children.size() > 0)
00111                         accessIndex = dynamic_cast<TupleVectorNode*>(children[0]);
00112 
00113                 if (accessIndex || children.size() == 0)
00114                 {
00115                         // immediate index "foo[n]" or "foo[n:m]" / full array access "foo"
00116                         unsigned pointer = getVectorAddr() + index;
00117                         // check if index is within bounds
00118                         if (pointer >= arrayAddr + arraySize)
00119                                 throw TranslatableError(sourcePos, ERROR_ARRAY_OUT_OF_BOUND).arg(arrayName).arg(index).arg(arraySize);
00120 
00121                         if (write == true)
00122                                 return new StoreNode(sourcePos, pointer);
00123                         else
00124                                 return new LoadNode(sourcePos, pointer);
00125                 }
00126                 else
00127                 {
00128                         // indirect access foo[expr]
00129                         std::auto_ptr<Node> array;
00130                         if (write == true)
00131                                 array.reset(new ArrayWriteNode(sourcePos, arrayAddr, arraySize, arrayName));
00132                         else
00133                                 array.reset(new ArrayReadNode(sourcePos, arrayAddr, arraySize, arrayName));
00134 
00135                         array->children.push_back(children[0]->expandToAsebaTree(dump, index));
00136                         children[0] = 0;
00137                         return array.release();
00138                 }
00139         }
00140         
00141         Node* ArithmeticAssignmentNode::expandToAsebaTree(std::wostream* dump, unsigned int index)
00142         {
00143                 assert(children.size() == 2);
00144 
00145                 Node* leftVector = children[0];
00146                 Node* rightVector = children[1];
00147 
00148                 // expand to left = left + right
00149                 std::auto_ptr<AssignmentNode> assignment(new AssignmentNode(sourcePos));
00150                 std::auto_ptr<BinaryArithmeticNode> binary(new BinaryArithmeticNode(sourcePos, op, leftVector->deepCopy(), rightVector->deepCopy()));
00151                 assignment->children.push_back(leftVector->deepCopy());
00152                 assignment->children.push_back(binary.release());
00153 
00154                 std::auto_ptr<Node> finalBlock(assignment->expandToAsebaTree(dump, index));
00155 
00156                 assignment.release();
00157                 delete this;
00158 
00159                 return finalBlock.release();
00160         }
00161 
00162 
00163         Node* UnaryArithmeticAssignmentNode::expandToAsebaTree(std::wostream* dump, unsigned int index)
00164         {
00165                 assert(children.size() == 1);
00166 
00167                 Node* memoryVector = children[0];
00168 
00169                 // create a vector of 1's
00170                 std::auto_ptr<TupleVectorNode> constant(new TupleVectorNode(sourcePos));
00171                 for (unsigned int i = 0; i < memoryVector->getVectorSize(); i++)
00172                         constant->addImmediateValue(1);
00173 
00174                 // expand to "vector (op)= 1"
00175                 std::auto_ptr<ArithmeticAssignmentNode> assignment(new ArithmeticAssignmentNode(sourcePos, arithmeticOp, memoryVector->deepCopy(), constant.release()));
00176                 std::auto_ptr<Node> finalBlock(assignment->expandToAsebaTree(dump, index));
00177 
00178                 assignment.release();
00179                 delete this;
00180 
00181                 return finalBlock.release();
00182         }
00183 
00184 
00185         void Node::checkVectorSize() const
00186         {
00187                 // recursively walk the tree and expand children
00188                 for (NodesVector::const_iterator it = children.begin(); it != children.end();)
00189                 {
00190                         (*it)->checkVectorSize();
00191                         ++it;
00192                 }
00193         }
00194 
00195 
00196         void AssignmentNode::checkVectorSize() const
00197         {
00198                 assert(children.size() == 2);
00199 
00200                 // will recursively check the whole tree belonging to "="
00201                 unsigned lSize = children[0]->getVectorSize();
00202                 unsigned rSize = children[1]->getVectorSize();
00203 
00204                 // top-level check
00205                 if (lSize != rSize)
00206                         throw TranslatableError(sourcePos, ERROR_ARRAY_SIZE_MISMATCH).arg(lSize).arg(rSize);
00207         }
00208 
00209         void ArithmeticAssignmentNode::checkVectorSize() const
00210         {
00211                 assert(children.size() == 2);
00212 
00213                 // will recursively check the whole tree belonging to "="
00214                 unsigned lSize = children[0]->getVectorSize();
00215                 unsigned rSize = children[1]->getVectorSize();
00216 
00217                 // top-level check
00218                 if (lSize != rSize)
00219                         throw TranslatableError(sourcePos, ERROR_ARRAY_SIZE_MISMATCH).arg(lSize).arg(rSize);
00220         }
00221 
00222 
00223         void IfWhenNode::checkVectorSize() const
00224         {
00225                 assert(children.size() > 0);
00226 
00227                 unsigned conditionSize = children[0]->getVectorSize();
00228                 if (conditionSize != 1)
00229                         throw TranslatableError(sourcePos, ERROR_IF_VECTOR_CONDITION);
00230                 // check true block
00231                 if (children.size() > 1 && children[1])
00232                         children[1]->checkVectorSize();
00233                 // check false block
00234                 if (children.size() > 2 && children[2])
00235                         children[2]->checkVectorSize();
00236         }
00237 
00238         void FoldedIfWhenNode::checkVectorSize() const
00239         {
00240                 assert(children.size() > 1);
00241 
00242                 unsigned conditionLeftSize = children[0]->getVectorSize();
00243                 unsigned conditionRightSize = children[1]->getVectorSize();
00244                 if (conditionLeftSize != 1 || conditionRightSize != 1)
00245                         throw TranslatableError(sourcePos, ERROR_IF_VECTOR_CONDITION);
00246                 // check true block
00247                 if (children.size() > 2 && children[2])
00248                         children[2]->checkVectorSize();
00249                 // check false block
00250                 if (children.size() > 3 && children[3])
00251                         children[3]->checkVectorSize();
00252         }
00253 
00254         void WhileNode::checkVectorSize() const
00255         {
00256                 assert(children.size() > 0);
00257 
00258                 unsigned conditionSize = children[0]->getVectorSize();
00259                 if (conditionSize != 1)
00260                         throw TranslatableError(sourcePos, ERROR_WHILE_VECTOR_CONDITION);
00261                 // check inner block
00262                 if (children.size() > 1 && children[1])
00263                         children[1]->checkVectorSize();
00264         }
00265 
00266         void FoldedWhileNode::checkVectorSize() const
00267         {
00268                 assert(children.size() > 1);
00269 
00270                 unsigned conditionLeftSize = children[0]->getVectorSize();
00271                 unsigned conditionRightSize = children[1]->getVectorSize();
00272                 if (conditionLeftSize != 1 || conditionRightSize != 1)
00273                         throw TranslatableError(sourcePos, ERROR_WHILE_VECTOR_CONDITION);
00274                 // check inner block
00275                 if (children.size() > 2 && children[2])
00276                         children[2]->checkVectorSize();
00277         }
00278 
00279 
00281         unsigned Node::getVectorAddr() const
00282         {
00283                 if (children.size() > 0)
00284                         return children[0]->getVectorAddr();
00285                 else
00286                         return E_NOVAL;
00287         }
00288 
00289 
00291         unsigned Node::getVectorSize() const
00292         {
00293                 unsigned size = E_NOVAL;
00294                 unsigned new_size = E_NOVAL;
00295 
00296                 for (NodesVector::const_iterator it = children.begin(); it != children.end(); ++it)
00297                 {
00298                         new_size = (*it)->getVectorSize();
00299                         if (size == E_NOVAL)
00300                                 size = new_size;
00301                         else if (size != new_size)
00302                                 throw TranslatableError(sourcePos, ERROR_ARRAY_SIZE_MISMATCH).arg(size).arg(new_size);
00303                 }
00304 
00305                 return size;
00306         }
00307 
00308 
00309         unsigned TupleVectorNode::getVectorSize() const
00310         {
00311                 unsigned size = 0;
00312                 NodesVector::const_iterator it;
00313                 for (it = children.begin(); it != children.end(); it++)
00314                         size += (*it)->getVectorSize();
00315                 return size;
00316         }
00317 
00318 
00322         unsigned MemoryVectorNode::getVectorAddr() const
00323         {
00324                 assert(children.size() <= 1);
00325 
00326                 int shift = 0;
00327 
00328                 // index(es) given?
00329                 if (children.size() == 1)
00330                 {
00331                         TupleVectorNode* index = dynamic_cast<TupleVectorNode*>(children[0]);
00332                         if (index)
00333                         {
00334                                 shift = index->getImmediateValue(0);
00335                         }
00336                         else
00337                                 // not know at compile time
00338                                 return E_NOVAL;
00339                 }
00340 
00341                 if (shift < 0 || shift >= int(arraySize))
00342                         throw TranslatableError(sourcePos, ERROR_ARRAY_OUT_OF_BOUND).arg(arrayName).arg(shift).arg(arraySize);
00343                 return arrayAddr + shift;
00344         }
00345 
00346 
00348         unsigned MemoryVectorNode::getVectorSize() const
00349         {
00350                 assert(children.size() <= 1);
00351 
00352                 if (children.size() == 1)
00353                 {
00354                         TupleVectorNode* index = dynamic_cast<TupleVectorNode*>(children[0]);
00355                         if (index)
00356                         {
00357                                 unsigned numberOfIndex = index->getVectorSize();
00358                                 // immediate indexes
00359                                 if (numberOfIndex == 1)
00360                                 {
00361                                         // foo[n] -> 1 dimension
00362                                         return 1;
00363                                 }
00364                                 else if (numberOfIndex == 2)
00365                                 {
00366                                         const int im0(index->getImmediateValue(0));
00367                                         const int im1(index->getImmediateValue(1));
00368                                         if (im1 < 0 || im1 >= int(arraySize))
00369                                                 throw TranslatableError(sourcePos, ERROR_ARRAY_OUT_OF_BOUND).arg(arrayName).arg(im1).arg(arraySize);
00370                                         // foo[n:m] -> compute the span
00371                                         return im1 - im0 + 1;
00372                                 }
00373                                 else
00374                                         // whaaaaat? Are you trying foo[[1,2,3]]?
00375                                         throw TranslatableError(sourcePos, ERROR_ARRAY_ILLEGAL_ACCESS);
00376                         }
00377                         else
00378                                 // random access foo[expr]
00379                                 return 1;
00380                 }
00381                 else
00382                         // full array access
00383                         return arraySize;
00384         }
00385         
00387         bool MemoryVectorNode::isAddressStatic() const
00388         {
00389                 if (children.empty())
00390                         return true;
00391                 TupleVectorNode* index = dynamic_cast<TupleVectorNode*>(children[0]);
00392                 if (index && index->children.size() <= 2 && index->isImmediateVector())
00393                         return true;
00394                 return false;
00395         }
00396 
00397         bool TupleVectorNode::isImmediateVector() const
00398         {
00399                 NodesVector::const_iterator it;
00400                 for (it = children.begin(); it != children.end(); it++)
00401                 {
00402                         ImmediateNode* node = dynamic_cast<ImmediateNode*>(*it);
00403                         if (!node)
00404                                 return false;
00405                 }
00406                 return true;
00407         }
00408 
00410         int TupleVectorNode::getImmediateValue(unsigned index) const
00411         {
00412                 assert(index < getVectorSize());
00413                 assert(isImmediateVector());
00414                 ImmediateNode* node = dynamic_cast<ImmediateNode*>(children[index]);
00415                 assert(node);
00416                 return node->value;
00417         }
00418 }


aseba
Author(s): Stéphane Magnenat
autogenerated on Thu Jan 2 2014 11:17:17