1 /* ResidualVM - A 3D game interpreter 2 * 3 * ResidualVM is the legal property of its developers, whose names 4 * are too numerous to list here. Please refer to the AUTHORS 5 * file distributed with this source distribution. 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20 * 21 */ 22 23 #ifndef STARK_TOOLS_BLOCK_H 24 #define STARK_TOOLS_BLOCK_H 25 26 #include "common/array.h" 27 28 namespace Stark { 29 namespace Tools { 30 31 class CFGCommand; 32 struct ControlStructure; 33 34 /** 35 * An aggregate of script commands 36 * 37 * Commands in the same group are always executed in sequence. 38 * 39 * This class is a node in the disassembly node graph. 40 */ 41 class Block { 42 public: 43 Block(); 44 45 /** Add a command at the end of the block, and set it as the command's block */ 46 void appendCommand(CFGCommand *command); 47 48 /** Get the commands from the block that are not part of a condition */ 49 Common::Array<CFGCommand *> getLinearCommands() const; 50 51 /** Get the command from the block that plays as a condition in a control structure */ 52 CFGCommand *getConditionCommand() const; 53 54 /** Does the block contain commands? */ 55 bool isEmpty() const; 56 57 /** Can the block branch? */ 58 bool isCondition() const; 59 60 /** 61 * Blocks are linked together in the block graph with these relationships: 62 * - follower: The natural follower of the block. Used when the block is not a branch, nor an end point. 63 * - true branch: The next block when the block's condition evaluates to true. 64 * - false branch: The next block when the block's condition evaluates to false. 65 * - predecessors: A list of blocks whose execution can lead to this block. 66 */ 67 void setBranches(Block *trueBranch, Block *falseBranch); 68 void setFollower(Block *follower); 69 void addPredecessor(Block *predecessor); 70 Block *getTrueBranch() const; 71 Block *getFalseBranch() const; 72 Block *getFollower() const; 73 74 /** 75 * Print a list of this block's commands to the debug output 76 */ 77 void print() const; 78 79 /** 80 * The high level control structure this block has the main role in 81 */ 82 bool hasControlStructure() const; 83 ControlStructure *getControlStructure() const; 84 void setControlStructure(ControlStructure *controlStructure); 85 86 /** Flag to indicate this block is the first in an unconditional infinite loop */ 87 bool isInfiniteLoopStart() const; 88 void setInfiniteLoopStart(bool infiniteLoopStart); 89 90 /** Can this block appear multiple times in the decompiled output? */ 91 bool allowDuplication() const; 92 93 // Graph query methods 94 bool hasPredecessor(Block *predecessor) const; 95 bool hasSuccessor(Block *successor) const; 96 Block *findMergePoint(Block *other); 97 bool checkAllBranchesConverge(Block *junction) const; 98 99 private: 100 bool hasPredecessorIntern(Common::Array<const Block *> &visited, Block *predecessor) const; 101 bool hasSuccessorIntern(Common::Array<const Block *> &visited, Block *successor) const; 102 bool hasChildSuccessorIntern(Common::Array<const Block *> &visited, Block *child, Block *successor) const; 103 Block *findMergePointIntern(Common::Array<const Block *> &visited, Block *other); 104 Block *findChildMergePoint(Common::Array<const Block *> &visited, Block *child, Block *other) const; 105 bool checkAllBranchesConvergeIntern(Common::Array<const Block *> &visited, Block *junction) const; 106 bool checkChildConvergeIntern(Common::Array<const Block *> &visited, Block *child, Block *junction) const; 107 108 uint16 getFirstCommandIndex() const; 109 110 Common::Array<CFGCommand *> _commands; 111 112 Block *_follower; 113 Block *_trueBranch; 114 Block *_falseBranch; 115 Common::Array<Block *> _predecessors; 116 117 ControlStructure *_controlStructure; 118 bool _infiniteLoopStart; 119 }; 120 121 struct ControlStructure { 122 enum ControlStructureType { 123 kTypeIf, 124 kTypeWhile 125 }; 126 127 ControlStructureType type; 128 Block *condition; 129 bool invertedCondition; 130 Block *loopHead; 131 Block *thenHead; 132 Block *elseHead; 133 Block *next; 134 135 ControlStructure(ControlStructureType t); 136 }; 137 138 } // End of namespace Tools 139 } // End of namespace Stark 140 141 #endif // STARK_TOOLS_BLOCK_H 142