stark/tools/block.cpp

/* ResidualVM - A 3D game interpreter
 *
 * ResidualVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the AUTHORS
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 */

#include "engines/stark/tools/block.h"

#include "engines/stark/tools/command.h"

#include "common/debug.h"

namespace Stark {
namespace Tools {

Block::Block() :
		_follower(nullptr),
		_trueBranch(nullptr),
		_falseBranch(nullptr),
		_controlStructure(nullptr),
		_infiniteLoopStart(false) {

}

void Block::appendCommand(CFGCommand *command) {
	_commands.push_back(command);
	command->setBlock(this);
}

bool Block::isEmpty() const {
	return _commands.empty();
}

void Block::print() const {
	for (uint i = 0; i < _commands.size(); i++) {
		_commands[i]->printCall();
	}

	if (_controlStructure) {
		switch (_controlStructure->type) {
			case ControlStructure::kTypeIf:
				debug("if%s: %d else: %d next: %d",
				      _controlStructure->invertedCondition ? " not" : "",
				      _controlStructure->thenHead->getFirstCommandIndex(),
				      _controlStructure->elseHead ? _controlStructure->elseHead->getFirstCommandIndex() : -1,
				      _controlStructure->next ? _controlStructure->next->getFirstCommandIndex() : -1);
				break;
			case ControlStructure::kTypeWhile:
				debug("while%s: %d next: %d",
				      _controlStructure->invertedCondition ? " not" : "",
				      _controlStructure->loopHead->getFirstCommandIndex(),
				      _controlStructure->next->getFirstCommandIndex());
				break;
		}
	}

	if (_infiniteLoopStart) {
		debug("infinite loop start: %d", getFirstCommandIndex());
	}

	if (isCondition() && !_controlStructure) {
		debug("unrecognized control flow");
	}
}

void Block::setBranches(Block *trueBranch, Block *falseBranch) {
	_trueBranch = trueBranch;
	_falseBranch = falseBranch;

	trueBranch->addPredecessor(this);
	falseBranch->addPredecessor(this);
}

void Block::setFollower(Block *follower) {
	_follower = follower;
	follower->addPredecessor(this);
}

void Block::addPredecessor(Block *predecessor) {
	_predecessors.push_back(predecessor);
}

bool Block::isCondition() const {
	return _trueBranch != nullptr && _falseBranch != nullptr;
}

bool Block::hasPredecessor(Block *predecessor) const {
	Common::Array<const Block *> visited;
	return hasPredecessorIntern(visited, predecessor);
}

bool Block::hasPredecessorIntern(Common::Array<const Block *> &visited, Block *predecessor) const {
	visited.push_back(this);

	if (isInfiniteLoopStart()) {
		// Don't follow infinite loops
		return false;
	}

	for (uint i = 0; i < _predecessors.size(); i++) {
		if (_predecessors[i] == predecessor) {
			return true;
		}

		bool alreadyVisited = Common::find(visited.begin(), visited.end(), _predecessors[i]) != visited.end();
		if (!alreadyVisited && _predecessors[i]->hasPredecessorIntern(visited, predecessor)) {
			return true;
		}
	}

	return false;
}

bool Block::hasSuccessor(Block *successor) const {
	Common::Array<const Block *> visited;
	return hasSuccessorIntern(visited, successor);
}

bool Block::hasSuccessorIntern(Common::Array<const Block *> &visited, Block *successor) const {
	visited.push_back(this);

	if (this == successor) {
		return true;
	}

	bool followerHasSuccessor = hasChildSuccessorIntern(visited, _follower, successor);
	bool trueBranchHasSuccessor = hasChildSuccessorIntern(visited, _trueBranch, successor);
	bool falseBranchHasSuccessor = hasChildSuccessorIntern(visited, _falseBranch, successor);

	return followerHasSuccessor || trueBranchHasSuccessor || falseBranchHasSuccessor;
}

bool Block::hasChildSuccessorIntern(Common::Array<const Block *> &visited, Block *child, Block *successor) const {
	if (!child) {
		return false;
	}

	bool alreadyVisited = Common::find(visited.begin(), visited.end(), child) != visited.end();
	return !alreadyVisited && child->hasSuccessorIntern(visited, successor);
}

Block *Block::findMergePoint(Block *other) {
	// TODO: Find the closest merge point? How to define that notion?
	Common::Array<const Block *> visited;
	return findMergePointIntern(visited, other);
}

Block *Block::findMergePointIntern(Common::Array<const Block *> &visited, Block *other) {
	visited.push_back(this);

	if (other == this) {
		return this;
	}

	if (hasPredecessor(other)) {
		return this;
	}

	Block *mergePoint = findChildMergePoint(visited, _follower, other);
	if (mergePoint) {
		return mergePoint;
	}

	mergePoint = findChildMergePoint(visited, _trueBranch, other);
	if (mergePoint) {
		return mergePoint;
	}

	mergePoint = findChildMergePoint(visited, _falseBranch, other);
	if (mergePoint) {
		return mergePoint;
	}

	return nullptr;
}

Block *Block::findChildMergePoint(Common::Array<const Block *> &visited, Block *child, Block *other) const {
	if (child) {
		bool alreadyVisited = Common::find(visited.begin(), visited.end(), child) != visited.end();
		if (!alreadyVisited) {
			return child->findMergePointIntern(visited, other);
		}
	}

	return nullptr;
}

bool Block::checkAllBranchesConverge(Block *junction) const {
	// Check if there is at least one path to the junction node
	if (!hasSuccessor(junction)) {
		return false;
	}

	// Check all the successors go to the junction point or loop infinitely
	Common::Array<const Block *> visited;
	return checkAllBranchesConvergeIntern(visited, junction);
}

bool Block::checkAllBranchesConvergeIntern(Common::Array<const Block *> &visited, Block *junction) const {
	visited.push_back(this);

	if (this == junction) {
		return true;
	}

	if (!_follower && !_trueBranch && !_falseBranch) {
		return false;
	}

	if (isInfiniteLoopStart()) {
		// Don't follow infinite loops
		return false;
	}

	bool followerConverges = checkChildConvergeIntern(visited, _follower, junction);
	bool trueBranchConverges = checkChildConvergeIntern(visited, _trueBranch, junction);
	bool falseBranchConverges = checkChildConvergeIntern(visited, _falseBranch, junction);

	return followerConverges && trueBranchConverges && falseBranchConverges;
}

bool Block::checkChildConvergeIntern(Common::Array<const Block *> &visited, Block *child, Block *junction) const {
	if (child) {
		bool alreadyVisited = Common::find(visited.begin(), visited.end(), child) != visited.end();
		if (!alreadyVisited) {
			return child->checkAllBranchesConvergeIntern(visited, junction);
		}
	}

	return true;
}

Block *Block::getFollower() const {
	return _follower;
}

Block *Block::getTrueBranch() const {
	return _trueBranch;
}

Block *Block::getFalseBranch() const {
	return _falseBranch;
}

uint16 Block::getFirstCommandIndex() const {
	return _commands[0]->getIndex();
}

bool Block::hasControlStructure() const {
	return _controlStructure != nullptr;
}

void Block::setControlStructure(ControlStructure *controlStructure) {
	_controlStructure = controlStructure;
}

ControlStructure *Block::getControlStructure() const {
	return _controlStructure;
}

void Block::setInfiniteLoopStart(bool infiniteLoopStart) {
	_infiniteLoopStart = infiniteLoopStart;
}

bool Block::isInfiniteLoopStart() const {
	return _infiniteLoopStart;
}

Common::Array<CFGCommand *> Block::getLinearCommands() const {
	if (!hasControlStructure()) {
		return _commands;
	} else {
		Common::Array<CFGCommand *> commands;

		// The last command in the block is the condition.
		// Exclude it from the linear commands.
		for (uint i = 0; i < _commands.size() - 1; i ++) {
			commands.push_back(_commands[i]);
		}

		return commands;
	}
}

CFGCommand *Block::getConditionCommand() const {
	if (hasControlStructure()) {
		// The condition command is always the last one
		return _commands.back();
	} else {
		return nullptr;
	}
}

bool Block::allowDuplication() const {
	// Allow simple termination blocks to be duplicated in the decompiled output
	bool isScriptEnd = !_follower && !_trueBranch && !_falseBranch;
	bool isShort = _commands.size() < 5;

	return isScriptEnd && isShort;
}

ControlStructure::ControlStructure(ControlStructureType t) :
		type(t),
		condition(nullptr),
		invertedCondition(false),
		loopHead(nullptr),
		thenHead(nullptr),
		elseHead(nullptr),
		next(nullptr) {
}

} // End of namespace Tools
} // End of namespace Stark