ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

block.cpp

Go to the documentation of this file.
00001 /* ResidualVM - A 3D game interpreter
00002  *
00003  * ResidualVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the AUTHORS
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
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 General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #include "engines/stark/tools/block.h"
00024 
00025 #include "engines/stark/tools/command.h"
00026 
00027 #include "common/debug.h"
00028 
00029 namespace Stark {
00030 namespace Tools {
00031 
00032 Block::Block() :
00033         _follower(nullptr),
00034         _trueBranch(nullptr),
00035         _falseBranch(nullptr),
00036         _controlStructure(nullptr),
00037         _infiniteLoopStart(false) {
00038 
00039 }
00040 
00041 void Block::appendCommand(CFGCommand *command) {
00042     _commands.push_back(command);
00043     command->setBlock(this);
00044 }
00045 
00046 bool Block::isEmpty() const {
00047     return _commands.empty();
00048 }
00049 
00050 void Block::print() const {
00051     for (uint i = 0; i < _commands.size(); i++) {
00052         _commands[i]->printCall();
00053     }
00054 
00055     if (_controlStructure) {
00056         switch (_controlStructure->type) {
00057             case ControlStructure::kTypeIf:
00058                 debug("if%s: %d else: %d next: %d",
00059                       _controlStructure->invertedCondition ? " not" : "",
00060                       _controlStructure->thenHead->getFirstCommandIndex(),
00061                       _controlStructure->elseHead ? _controlStructure->elseHead->getFirstCommandIndex() : -1,
00062                       _controlStructure->next ? _controlStructure->next->getFirstCommandIndex() : -1);
00063                 break;
00064             case ControlStructure::kTypeWhile:
00065                 debug("while%s: %d next: %d",
00066                       _controlStructure->invertedCondition ? " not" : "",
00067                       _controlStructure->loopHead->getFirstCommandIndex(),
00068                       _controlStructure->next->getFirstCommandIndex());
00069                 break;
00070         }
00071     }
00072 
00073     if (_infiniteLoopStart) {
00074         debug("infinite loop start: %d", getFirstCommandIndex());
00075     }
00076 
00077     if (isCondition() && !_controlStructure) {
00078         debug("unrecognized control flow");
00079     }
00080 }
00081 
00082 void Block::setBranches(Block *trueBranch, Block *falseBranch) {
00083     _trueBranch = trueBranch;
00084     _falseBranch = falseBranch;
00085 
00086     trueBranch->addPredecessor(this);
00087     falseBranch->addPredecessor(this);
00088 }
00089 
00090 void Block::setFollower(Block *follower) {
00091     _follower = follower;
00092     follower->addPredecessor(this);
00093 }
00094 
00095 void Block::addPredecessor(Block *predecessor) {
00096     _predecessors.push_back(predecessor);
00097 }
00098 
00099 bool Block::isCondition() const {
00100     return _trueBranch != nullptr && _falseBranch != nullptr;
00101 }
00102 
00103 bool Block::hasPredecessor(Block *predecessor) const {
00104     Common::Array<const Block *> visited;
00105     return hasPredecessorIntern(visited, predecessor);
00106 }
00107 
00108 bool Block::hasPredecessorIntern(Common::Array<const Block *> &visited, Block *predecessor) const {
00109     visited.push_back(this);
00110 
00111     if (isInfiniteLoopStart()) {
00112         // Don't follow infinite loops
00113         return false;
00114     }
00115 
00116     for (uint i = 0; i < _predecessors.size(); i++) {
00117         if (_predecessors[i] == predecessor) {
00118             return true;
00119         }
00120 
00121         bool alreadyVisited = Common::find(visited.begin(), visited.end(), _predecessors[i]) != visited.end();
00122         if (!alreadyVisited && _predecessors[i]->hasPredecessorIntern(visited, predecessor)) {
00123             return true;
00124         }
00125     }
00126 
00127     return false;
00128 }
00129 
00130 bool Block::hasSuccessor(Block *successor) const {
00131     Common::Array<const Block *> visited;
00132     return hasSuccessorIntern(visited, successor);
00133 }
00134 
00135 bool Block::hasSuccessorIntern(Common::Array<const Block *> &visited, Block *successor) const {
00136     visited.push_back(this);
00137 
00138     if (this == successor) {
00139         return true;
00140     }
00141 
00142     bool followerHasSuccessor = hasChildSuccessorIntern(visited, _follower, successor);
00143     bool trueBranchHasSuccessor = hasChildSuccessorIntern(visited, _trueBranch, successor);
00144     bool falseBranchHasSuccessor = hasChildSuccessorIntern(visited, _falseBranch, successor);
00145 
00146     return followerHasSuccessor || trueBranchHasSuccessor || falseBranchHasSuccessor;
00147 }
00148 
00149 bool Block::hasChildSuccessorIntern(Common::Array<const Block *> &visited, Block *child, Block *successor) const {
00150     if (!child) {
00151         return false;
00152     }
00153 
00154     bool alreadyVisited = Common::find(visited.begin(), visited.end(), child) != visited.end();
00155     return !alreadyVisited && child->hasSuccessorIntern(visited, successor);
00156 }
00157 
00158 Block *Block::findMergePoint(Block *other) {
00159     // TODO: Find the closest merge point? How to define that notion?
00160     Common::Array<const Block *> visited;
00161     return findMergePointIntern(visited, other);
00162 }
00163 
00164 Block *Block::findMergePointIntern(Common::Array<const Block *> &visited, Block *other) {
00165     visited.push_back(this);
00166 
00167     if (other == this) {
00168         return this;
00169     }
00170 
00171     if (hasPredecessor(other)) {
00172         return this;
00173     }
00174 
00175     Block *mergePoint = findChildMergePoint(visited, _follower, other);
00176     if (mergePoint) {
00177         return mergePoint;
00178     }
00179 
00180     mergePoint = findChildMergePoint(visited, _trueBranch, other);
00181     if (mergePoint) {
00182         return mergePoint;
00183     }
00184 
00185     mergePoint = findChildMergePoint(visited, _falseBranch, other);
00186     if (mergePoint) {
00187         return mergePoint;
00188     }
00189 
00190     return nullptr;
00191 }
00192 
00193 Block *Block::findChildMergePoint(Common::Array<const Block *> &visited, Block *child, Block *other) const {
00194     if (child) {
00195         bool alreadyVisited = Common::find(visited.begin(), visited.end(), child) != visited.end();
00196         if (!alreadyVisited) {
00197             return child->findMergePointIntern(visited, other);
00198         }
00199     }
00200 
00201     return nullptr;
00202 }
00203 
00204 bool Block::checkAllBranchesConverge(Block *junction) const {
00205     // Check if there is at least one path to the junction node
00206     if (!hasSuccessor(junction)) {
00207         return false;
00208     }
00209 
00210     // Check all the successors go to the junction point or loop infinitely
00211     Common::Array<const Block *> visited;
00212     return checkAllBranchesConvergeIntern(visited, junction);
00213 }
00214 
00215 bool Block::checkAllBranchesConvergeIntern(Common::Array<const Block *> &visited, Block *junction) const {
00216     visited.push_back(this);
00217 
00218     if (this == junction) {
00219         return true;
00220     }
00221 
00222     if (!_follower && !_trueBranch && !_falseBranch) {
00223         return false;
00224     }
00225 
00226     if (isInfiniteLoopStart()) {
00227         // Don't follow infinite loops
00228         return false;
00229     }
00230 
00231     bool followerConverges = checkChildConvergeIntern(visited, _follower, junction);
00232     bool trueBranchConverges = checkChildConvergeIntern(visited, _trueBranch, junction);
00233     bool falseBranchConverges = checkChildConvergeIntern(visited, _falseBranch, junction);
00234 
00235     return followerConverges && trueBranchConverges && falseBranchConverges;
00236 }
00237 
00238 bool Block::checkChildConvergeIntern(Common::Array<const Block *> &visited, Block *child, Block *junction) const {
00239     if (child) {
00240         bool alreadyVisited = Common::find(visited.begin(), visited.end(), child) != visited.end();
00241         if (!alreadyVisited) {
00242             return child->checkAllBranchesConvergeIntern(visited, junction);
00243         }
00244     }
00245 
00246     return true;
00247 }
00248 
00249 Block *Block::getFollower() const {
00250     return _follower;
00251 }
00252 
00253 Block *Block::getTrueBranch() const {
00254     return _trueBranch;
00255 }
00256 
00257 Block *Block::getFalseBranch() const {
00258     return _falseBranch;
00259 }
00260 
00261 uint16 Block::getFirstCommandIndex() const {
00262     return _commands[0]->getIndex();
00263 }
00264 
00265 bool Block::hasControlStructure() const {
00266     return _controlStructure != nullptr;
00267 }
00268 
00269 void Block::setControlStructure(ControlStructure *controlStructure) {
00270     _controlStructure = controlStructure;
00271 }
00272 
00273 ControlStructure *Block::getControlStructure() const {
00274     return _controlStructure;
00275 }
00276 
00277 void Block::setInfiniteLoopStart(bool infiniteLoopStart) {
00278     _infiniteLoopStart = infiniteLoopStart;
00279 }
00280 
00281 bool Block::isInfiniteLoopStart() const {
00282     return _infiniteLoopStart;
00283 }
00284 
00285 Common::Array<CFGCommand *> Block::getLinearCommands() const {
00286     if (!hasControlStructure()) {
00287         return _commands;
00288     } else {
00289         Common::Array<CFGCommand *> commands;
00290 
00291         // The last command in the block is the condition.
00292         // Exclude it from the linear commands.
00293         for (uint i = 0; i < _commands.size() - 1; i ++) {
00294             commands.push_back(_commands[i]);
00295         }
00296 
00297         return commands;
00298     }
00299 }
00300 
00301 CFGCommand *Block::getConditionCommand() const {
00302     if (hasControlStructure()) {
00303         // The condition command is always the last one
00304         return _commands.back();
00305     } else {
00306         return nullptr;
00307     }
00308 }
00309 
00310 bool Block::allowDuplication() const {
00311     // Allow simple termination blocks to be duplicated in the decompiled output
00312     bool isScriptEnd = !_follower && !_trueBranch && !_falseBranch;
00313     bool isShort = _commands.size() < 5;
00314 
00315     return isScriptEnd && isShort;
00316 }
00317 
00318 ControlStructure::ControlStructure(ControlStructureType t) :
00319         type(t),
00320         condition(nullptr),
00321         invertedCondition(false),
00322         loopHead(nullptr),
00323         thenHead(nullptr),
00324         elseHead(nullptr),
00325         next(nullptr) {
00326 }
00327 
00328 } // End of namespace Tools
00329 } // End of namespace Stark


Generated on Sat Sep 14 2019 05:01:24 for ResidualVM by doxygen 1.7.1
curved edge   curved edge