00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
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
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
00206 if (!hasSuccessor(junction)) {
00207 return false;
00208 }
00209
00210
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
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
00292
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
00304 return _commands.back();
00305 } else {
00306 return nullptr;
00307 }
00308 }
00309
00310 bool Block::allowDuplication() const {
00311
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 }
00329 }