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

decompiler.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/decompiler.h"
00024 
00025 #include "engines/stark/resources/command.h"
00026 
00027 #include "engines/stark/tools/abstractsyntaxtree.h"
00028 #include "engines/stark/tools/block.h"
00029 
00030 #include "common/debug.h"
00031 
00032 namespace Stark {
00033 namespace Tools {
00034 
00035 Decompiler::Decompiler(Resources::Script *script) :
00036         _entryPoint(nullptr),
00037         _astHead(nullptr),
00038         _definitionRegistry(nullptr) {
00039     // Convert the script commands to decompiler commands
00040     Common::Array<Resources::Command *> resourceCommands = script->listChildren<Resources::Command>();
00041     for (uint i = 0; i < resourceCommands.size(); i++) {
00042         _commands.push_back(new CFGCommand(resourceCommands[i]));
00043     }
00044     if (_commands.empty()) {
00045         return;
00046     }
00047     if (!checkCommands()) {
00048         return;
00049     }
00050 
00051     _entryPoint = findEntryPoint();
00052 
00053     linkCommandBranches();
00054     buildBlocks();
00055     analyseControlFlow();
00056 
00057     _definitionRegistry = new DefinitionRegistry();
00058     _astHead = buildAST();
00059     verifyAST();
00060 }
00061 
00062 void Decompiler::printCommands() const {
00063     for (uint i = 0; i < _commands.size(); i++) {
00064         _commands[i]->printCall();
00065     }
00066 }
00067 
00068 void Decompiler::printBlocks() const {
00069     for (uint i = 0; i < _blocks.size(); i++) {
00070         _blocks[i]->print();
00071         debug("- - - -");
00072     }
00073 }
00074 
00075 void Decompiler::printDecompiled() {
00076     if (_astHead) {
00077         _definitionRegistry->printAll();
00078         debug(" "); // Empty line
00079         _astHead->print(0, _definitionRegistry);
00080     }
00081 }
00082 
00083 Decompiler::~Decompiler() {
00084     for (uint i = 0; i < _commands.size(); i++) {
00085         delete _commands[i];
00086     }
00087 
00088     for (uint i = 0; i < _blocks.size(); i++) {
00089         delete _blocks[i];
00090     }
00091 
00092     for (uint i = 0; i < _controlStructures.size(); i++) {
00093         delete _controlStructures[i];
00094     }
00095 
00096     delete _astHead;
00097     delete _definitionRegistry;
00098 }
00099 
00100 void Decompiler::linkCommandBranches() {
00101     for (uint i = 0; i < _commands.size(); i++) {
00102         _commands[i]->linkBranches(_commands);
00103     }
00104 }
00105 
00106 CFGCommand *Decompiler::findEntryPoint() {
00107     for (uint i = 0; i < _commands.size(); i++) {
00108         if (_commands[i]->isEntryPoint()) {
00109             return _commands[i];
00110         }
00111     }
00112 
00113     error("Unable to find an entry point");
00114 }
00115 
00116 void Decompiler::buildBlocks() {
00117     Block *entryPointBlock = new Block();
00118     _blocks.push_back(entryPointBlock);
00119 
00120     buildBlocks(entryPointBlock, _entryPoint);
00121 }
00122 
00123 void Decompiler::buildBlocks(Block *block, CFGCommand *command) {
00124     CFGCommand *blockCommand = command;
00125     while (blockCommand) {
00126         if (blockCommand->getBlock()) {
00127             block->setFollower(blockCommand->getBlock());
00128             break;
00129         }
00130 
00131         if (blockCommand->isBranchTarget() && !block->isEmpty()) {
00132             Block *follower = buildBranchBlocks(blockCommand);
00133 
00134             block->setFollower(follower);
00135             break;
00136         }
00137 
00138         block->appendCommand(blockCommand);
00139 
00140         if (blockCommand->isBranch()) {
00141             Block *falseBranch = buildBranchBlocks(blockCommand->getFalseBranch());
00142             Block *trueBranch = buildBranchBlocks(blockCommand->getTrueBranch());
00143 
00144             block->setBranches(trueBranch, falseBranch);
00145             break;
00146         }
00147 
00148         blockCommand = blockCommand->getFollower();
00149     }
00150 }
00151 
00152 Block *Decompiler::buildBranchBlocks(CFGCommand *command) {
00153     if (command->getBlock()) {
00154         // The command already has a block. No need to go through this path again.
00155         return command->getBlock();
00156     }
00157 
00158     Block *branchBlock = new Block();
00159     _blocks.push_back(branchBlock);
00160 
00161     buildBlocks(branchBlock, command);
00162 
00163     return branchBlock;
00164 }
00165 
00166 void Decompiler::analyseControlFlow() {
00167     detectInfiniteLoop();
00168     detectWhile();
00169     detectIf();
00170 }
00171 
00172 void Decompiler::detectInfiniteLoop() {
00173     for (uint i = 0; i < _blocks.size(); i++) {
00174         Block *block = _blocks[i];
00175 
00176         // Check all paths from the block go back to itself
00177         if (block->getFollower()) {
00178             bool followerConvergesBack = block->getFollower()->checkAllBranchesConverge(block);
00179 
00180             if (followerConvergesBack) {
00181                 block->setInfiniteLoopStart(true);
00182             }
00183         } else if (block->isCondition()) {
00184             bool trueBranchConvergesBack = block->getTrueBranch()->checkAllBranchesConverge(block);
00185             bool falseBranchConvergesBack = block->getFalseBranch()->checkAllBranchesConverge(block);
00186 
00187             if (trueBranchConvergesBack && falseBranchConvergesBack) {
00188                 block->setInfiniteLoopStart(true);
00189             }
00190         }
00191     }
00192 }
00193 
00194 void Decompiler::detectWhile() {
00195     for (uint i = 0; i < _blocks.size(); i++) {
00196         Block *block = _blocks[i];
00197 
00198         if (block->hasControlStructure()) continue;
00199         if (!block->isCondition()) continue;
00200         if (block->isInfiniteLoopStart()) continue; // TODO: This should be handled by checkAllBranchesConverge already
00201 
00202         // Check all paths from the body branch go back to the condition
00203         // TODO: If the original had "break" statement, this will not work
00204         bool trueBranchConvergesToCondition = block->getTrueBranch()->checkAllBranchesConverge(block);
00205         bool falseBranchConvergesToCondition = block->getFalseBranch()->checkAllBranchesConverge(block);
00206 
00207         if (!trueBranchConvergesToCondition && !falseBranchConvergesToCondition) continue;
00208         if (trueBranchConvergesToCondition && falseBranchConvergesToCondition) {
00209             warning("Both branches of a condition converge back to the condition");
00210         }
00211 
00212         ControlStructure *controlStructure = new ControlStructure(ControlStructure::kTypeWhile);
00213         if (trueBranchConvergesToCondition) {
00214             controlStructure->invertedCondition = false;
00215             controlStructure->loopHead = block->getTrueBranch();
00216             controlStructure->next = block->getFalseBranch();
00217         } else {
00218             controlStructure->invertedCondition = true;
00219             controlStructure->loopHead = block->getFalseBranch();
00220             controlStructure->next = block->getTrueBranch();
00221         }
00222 
00223         block->setControlStructure(controlStructure);
00224         _controlStructures.push_back(controlStructure);
00225     }
00226 }
00227 
00228 void Decompiler::detectIf() {
00229     for (uint i = 0; i < _blocks.size(); i++) {
00230         Block *block = _blocks[i];
00231 
00232         if (block->hasControlStructure()) continue;
00233         if (!block->isCondition()) continue;
00234 
00235         ControlStructure *controlStructure = new ControlStructure(ControlStructure::kTypeIf);
00236         controlStructure->next = block->getTrueBranch()->findMergePoint(block->getFalseBranch());
00237 
00238         if (!controlStructure->next) {
00239             // When one (or both) of the branches return, there is no merge point
00240             controlStructure->invertedCondition = false;
00241             controlStructure->thenHead = block->getTrueBranch();
00242             controlStructure->elseHead = block->getFalseBranch();
00243         } else if (block->getTrueBranch() != controlStructure->next) {
00244             // Use the "true" branch as the "then" block ...
00245             controlStructure->invertedCondition = false;
00246             controlStructure->thenHead = block->getTrueBranch();
00247             controlStructure->elseHead = controlStructure->next != block->getFalseBranch() ? block->getFalseBranch() : nullptr;
00248         } else {
00249             // ... unless the true branch is empty.
00250             // In which case use the false branch and invert the condition.
00251             controlStructure->invertedCondition = true;
00252             controlStructure->thenHead = block->getFalseBranch();
00253             controlStructure->elseHead = nullptr;
00254         }
00255 
00256         block->setControlStructure(controlStructure);
00257         _controlStructures.push_back(controlStructure);
00258     }
00259 }
00260 
00261 bool Decompiler::checkCommands() {
00262     for (uint i = 0; i < _commands.size(); i++) {
00263         Command *command = _commands[i];
00264         if (!command->hasSubtypeDescription()) {
00265             _error = Common::String::format("Command subtype %d is not described", command->getSubType());
00266             return false;
00267         }
00268     }
00269 
00270     return true;
00271 }
00272 
00273 Common::String Decompiler::getError() const {
00274     return _error;
00275 }
00276 
00277 ASTNode *Decompiler::buildAST() {
00278     Block *entryPoint = _entryPoint->getBlock();
00279 
00280     ASTBlock *head = new ASTBlock(nullptr);
00281     buildASTFromBlock(head, entryPoint, nullptr);
00282     return head;
00283 }
00284 
00285 void Decompiler::buildASTFromBlock(ASTBlock *parent, Block *block, Block *stopBlock) {
00286     if (block->isInfiniteLoopStart()) {
00287         bool alreadyVisited = Common::find(_visitedInfiniteLoopStarts.begin(), _visitedInfiniteLoopStarts.end(), block)
00288                               != _visitedInfiniteLoopStarts.end();
00289         if (alreadyVisited) {
00290             // Don't add the same loop multiple times in the AST
00291             return;
00292         }
00293 
00294         _visitedInfiniteLoopStarts.push_back(block);
00295 
00296         ASTLoop *loop = new ASTLoop(parent);
00297         loop->loopBlock = new ASTBlock(loop);
00298         parent->addNode(loop);
00299 
00300         // Hijack the parameters to add the current block to the loop body and continue
00301         parent = loop->loopBlock;
00302         stopBlock = block;
00303     }
00304 
00305     {
00306         bool alreadyVisited = Common::find(_visitedBlocks.begin(), _visitedBlocks.end(), block) != _visitedBlocks.end();
00307         if (alreadyVisited && !block->allowDuplication()) {
00308             // FIXME: We just return for now when an already visited block is visited again.
00309             // Obviously, this leads to invalid decompiled code, which is caught by the verification step.
00310             // To fix, either handle the cases leading to multiple visits, or generate gotos.
00311             return;
00312         }
00313     }
00314 
00315     _visitedBlocks.push_back(block);
00316 
00317     Common::Array<CFGCommand *> commands = block->getLinearCommands();
00318     for (uint i = 0; i < commands.size(); i++) {
00319         parent->addNode(new ASTCommand(parent, commands[i], _definitionRegistry));
00320     }
00321 
00322     if (block->hasControlStructure()) {
00323         ControlStructure *cfgControlStructure = block->getControlStructure();
00324         ASTNode *astControlStructure;
00325         switch (cfgControlStructure->type) {
00326             case ControlStructure::kTypeIf:
00327                 astControlStructure = buildASTConditionFromBlock(parent, block);
00328                 break;
00329             case ControlStructure::kTypeWhile:
00330                 astControlStructure = buildASTLoopFromBlock(parent, block);
00331                 break;
00332             default:
00333                 error("Unknown control structure type %d", cfgControlStructure->type);
00334         }
00335 
00336         parent->addNode(astControlStructure);
00337 
00338         if (cfgControlStructure->next && cfgControlStructure->next != stopBlock) {
00339             buildASTFromBlock(parent, cfgControlStructure->next, stopBlock);
00340         }
00341     } else {
00342         Block *follower = block->getFollower();
00343         if (follower && follower != stopBlock) {
00344             buildASTFromBlock(parent, follower, stopBlock);
00345         }
00346     }
00347 }
00348 
00349 ASTCondition *Decompiler::buildASTConditionFromBlock(ASTNode *parent, Block *block) {
00350     ControlStructure *controlStructure = block->getControlStructure();
00351 
00352     ASTCondition *condition = new ASTCondition(parent);
00353     condition->condition = new ASTCommand(condition, block->getConditionCommand(), _definitionRegistry);
00354     condition->invertedCondition = controlStructure->invertedCondition;
00355 
00356     condition->thenBlock = new ASTBlock(condition);
00357     buildASTFromBlock(condition->thenBlock, controlStructure->thenHead, controlStructure->next);
00358 
00359     if (controlStructure->elseHead) {
00360         condition->elseBlock = new ASTBlock(condition);
00361         buildASTFromBlock(condition->elseBlock, controlStructure->elseHead, controlStructure->next);
00362     }
00363 
00364     return condition;
00365 }
00366 
00367 ASTLoop *Decompiler::buildASTLoopFromBlock(ASTNode *parent, Block *block) {
00368     ControlStructure *controlStructure = block->getControlStructure();
00369 
00370     ASTLoop *loop = new ASTLoop(parent);
00371     loop->condition = new ASTCommand(loop, block->getConditionCommand(), _definitionRegistry);
00372     loop->invertedCondition = controlStructure->invertedCondition;
00373 
00374     loop->loopBlock = new ASTBlock(loop);
00375     buildASTFromBlock(loop->loopBlock, controlStructure->loopHead, block);
00376 
00377     return loop;
00378 }
00379 
00380 void Decompiler::verifyAST() {
00381     for (uint i = 0; i < _commands.size(); i++) {
00382         CFGCommand *command = _commands[i];
00383         if (!verifyCommandInAST(command)) {
00384             return;
00385         }
00386     }
00387 }
00388 
00389 bool Decompiler::verifyCommandInAST(CFGCommand *cfgCommand) {
00390     Common::Array<const ASTCommand *> list = _astHead->listCommands(cfgCommand->getIndex());
00391 
00392     if (list.empty()) {
00393         _error = Common::String::format("Command %d not found in the AST", cfgCommand->getIndex());
00394         return false;
00395     }
00396 
00397     if (list.size() > 1 && !cfgCommand->getBlock()->allowDuplication()) {
00398         _error = Common::String::format("Command %d found %d times in the AST", cfgCommand->getIndex(), list.size());
00399         return false;
00400     }
00401 
00402     const ASTCommand *astCommand = list[0];
00403 
00404     ASTNode *follower = nullptr, *trueBranch = nullptr, *falseBranch = nullptr;
00405     astCommand->findSuccessors(&follower, &trueBranch, &falseBranch);
00406 
00407     if (!verifyCommandSuccessorInAST(cfgCommand, cfgCommand->getFollower(), follower, "follower")) {
00408         return false;
00409     }
00410 
00411     if (!verifyCommandSuccessorInAST(cfgCommand, cfgCommand->getTrueBranch(), trueBranch, "trueBranch")) {
00412         return false;
00413     }
00414 
00415     if (!verifyCommandSuccessorInAST(cfgCommand, cfgCommand->getFalseBranch(), falseBranch, "falseBranch")) {
00416         return false;
00417     }
00418 
00419     return true;
00420 }
00421 
00422 bool Decompiler::verifyCommandSuccessorInAST(CFGCommand *cfgCommand, CFGCommand *cfgSuccessor, ASTNode *astSuccessor, const char *successorType) {
00423     if (cfgSuccessor) {
00424         if (!astSuccessor) {
00425             _error = Common::String::format("Command %d does not have a %s in the AST",
00426                                             cfgCommand->getIndex(), successorType);
00427             return false;
00428         }
00429 
00430         const ASTCommand *astSuccessorCommand = astSuccessor->getFirstCommand();
00431         if (!astSuccessorCommand) {
00432             _error = Common::String::format("Command %d has an empty %s in the AST",
00433                                             cfgCommand->getIndex(), successorType);
00434             return false;
00435         }
00436 
00437         int16 expectedSuccessorIndex = cfgSuccessor->getIndex();
00438         if (astSuccessorCommand->getIndex() != expectedSuccessorIndex) {
00439             _error = Common::String::format("Command %d has an unexpected %s %d in the AST, should be %d",
00440                                             cfgCommand->getIndex(), successorType, astSuccessorCommand->getIndex(), expectedSuccessorIndex);
00441             return false;
00442         }
00443     }
00444 
00445     return true;
00446 }
00447 
00448 } // End of namespace Tools
00449 } // End of namespace Stark


Generated on Sat Mar 16 2019 05:01:24 for ResidualVM by doxygen 1.7.1
curved edge   curved edge