versionspass.cpp
No OneTemporary
Actions

Subscribers

None

File Metadata

Created: Tue, Jul 7, 9:42 PM

versionspass.cpp
View Options

	/* This Source Code Form is subject to the terms of the Mozilla Public
	* License, v. 2.0. If a copy of the MPL was not distributed with this
	* file, You can obtain one at http://mozilla.org/MPL/2.0/.
	*
	* versionspass.cpp
	*
	* Author: pgess <v.melnychenko@xreate.org>
	* Created on January 4, 2017, 3:13 PM
	*/

	/** \class xreate::versions::VersionsPass
	* Has two parts:
	* - Validates correctness of versioned variables with regard to variables lifespan
	* - Determines versioned variables computation order
	* \sa VersionsScopeDecorator, VersionsGraph, [Versions Concept](/w/concepts/versions)
	*/

	#include <boost/optional/optional.hpp>
	#include "pass/versionspass.h"

	namespace std{
	std::size_t
	hash<xreate::versions::SymbolOrPlaceholder>::operator()(xreate::versions::SymbolOrPlaceholder const& s) const
	{return std::hash<xreate::Symbol>()(s.symbol) + (s.flagEndOfLifePlaceholder? 9849 : 1);}

	bool
	equal_to<xreate::versions::SymbolOrPlaceholder>::operator()(const xreate::versions::SymbolOrPlaceholder& __x, const xreate::versions::SymbolOrPlaceholder& __y) const
	{ return __x.flagEndOfLifePlaceholder == __y.flagEndOfLifePlaceholder && __x.symbol == __y.symbol; }
	}

	using namespace std;

	namespace xreate{ namespace versions{

	template<>
	std::list<Symbol>
	defaultValue<std::list<Symbol>>(){
	return std::list<Symbol>();
	};

	inline std::string
	printSymbol(const SymbolOrPlaceholder& s){
	switch(s.flagEndOfLifePlaceholder){
	case SYMBOL: return string("(") + std::to_string(s.symbol.identifier.id) + ", "+ std::to_string(s.symbol.identifier.version) + ")";
	case PLACEHOLDER: return string("(") + std::to_string(s.symbol.identifier.id) + ", "+ std::to_string(s.symbol.identifier.version) + ")+";
	}

	return "";
	}

	void
	VersionsGraph::__debug_print(std::ostream& output) const{
	for(auto entry: __inferiors){
	output << printSymbol(entry.second) << " <-" << printSymbol(entry.first) << "\n";
	}
	}

	void
	VersionsGraph::defineEndOfLife(const Symbol& symbol, const Symbol& symbolSuccessor){
	if(__dictSuccessors.count(symbol)){
	assert("No version branches allowed yet" && false);
	}

	const SymbolOrPlaceholder& placeholder = getEndOfLife(symbol);

	auto inferiorsDeferred = __inferiors.equal_range(placeholder);
	std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder> inferiorsReassigned;

	for (const auto& inf: boost::make_iterator_range(inferiorsDeferred)){
	inferiorsReassigned.emplace(SymbolOrPlaceholder{SYMBOL, symbolSuccessor}, inf.second);
	}

	__inferiors.erase(placeholder);
	__inferiors.insert(inferiorsReassigned.begin(), inferiorsReassigned.end());
	__inferiors.emplace(SymbolOrPlaceholder{SYMBOL, symbolSuccessor}, SymbolOrPlaceholder{SYMBOL, symbol});

	__dictSuccessors.emplace(symbol, symbolSuccessor);
	}

	SymbolOrPlaceholder
	VersionsGraph::getEndOfLife(const Symbol& s){
	if (__dictSuccessors.count(s)){
	return SymbolOrPlaceholder{SYMBOL, __dictSuccessors.at(s)}; }


	return SymbolOrPlaceholder{PLACEHOLDER, s};
	}

	void
	VersionsGraph::applyNatualDependencies(const Symbol& symbol, const std::list<Symbol>& dependencies){
	for (const Symbol& right: dependencies){
	__inferiorsNatural.emplace(symbol, right);
	}
	}

	void
	VersionsGraph::applyDependentEndOfLife(const SymbolOrPlaceholder& symbol, const list<Symbol>& dependencies){
	for (const Symbol& right: dependencies){
	auto rightEOF = getEndOfLife(right);

	__inferiors.emplace(rightEOF, symbol);
	}
	}

	bool
	VersionsGraph::tryEliminateEofAliases(const std::list<SymbolOrPlaceholder>& aliases){

	if (aliases.size()==1){
	return true;
	}

	boost::optional<Symbol> symbolActualEoF;
	for(const SymbolOrPlaceholder alias: aliases){
	switch(alias.flagEndOfLifePlaceholder){
	case SYMBOL:
	if(symbolActualEoF){
	return false;
	}

	symbolActualEoF = alias.symbol;
	break;

	case PLACEHOLDER:
	continue;
	}
	}

	if(!symbolActualEoF){
	return false;
	}

	for(const SymbolOrPlaceholder alias: aliases){
	switch(alias.flagEndOfLifePlaceholder){
	case SYMBOL:
	continue;

	case PLACEHOLDER:
	defineEndOfLife(alias.symbol, symbolActualEoF.get());
	break;
	}
	}

	return true;
	}

	std::list<SymbolOrPlaceholder>
	VersionsGraph::extractCycle(const Path& path, const SymbolOrPlaceholder& symbolBeginning){
	unsigned int posBeginning = path.at(symbolBeginning);

	std::list<SymbolOrPlaceholder> result;

	auto i=path.begin();
	while(true){
	i = std::find_if(i, path.end(), [&posBeginning](const auto& el){return el.second >=posBeginning;});

	if (i!= path.end()){
	result.push_back(i->first);
	++i;

	} else {break; }
	}

	return result;
	}

	bool
	VersionsGraph::validateCycles(const SymbolOrPlaceholder& s,
	std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder>& graph,
	std::unordered_set<SymbolOrPlaceholder>& symbolsVisited,
	Path& path)
	{
	if (symbolsVisited.count(s)) return true;

	symbolsVisited.insert(s);
	path.emplace(s, path.size());

	if (graph.count(s)){
	//iterate over imposed dependencies
	auto candidates = graph.equal_range(s);
	for (auto candidate = candidates.first; candidate != candidates.second; ++candidate){
	if (path.count(candidate->second)) {
	std::list<SymbolOrPlaceholder> cycle = extractCycle(path, candidate->second);
	if (!tryEliminateEofAliases(cycle)) return false;
	continue;
	}

	if(!validateCycles(candidate->second, graph, symbolsVisited, path)) return false;
	}
	}

	//iterate over natural dependencies
	if (s.flagEndOfLifePlaceholder == SYMBOL) {
	auto candidates = __inferiorsNatural.equal_range(s.symbol);
	for (auto candidate = candidates.first; candidate != candidates.second; ++candidate){
	if (path.count(SymbolOrPlaceholder{SYMBOL, candidate->second})){
	return false;
	}

	if(!validateCycles(SymbolOrPlaceholder{SYMBOL,candidate->second}, graph, symbolsVisited, path)) return false;
	}
	}

	//check previous version
	if (s.flagEndOfLifePlaceholder == PLACEHOLDER){
	const Symbol& candidate = s.symbol;

	if (path.count(SymbolOrPlaceholder{SYMBOL, candidate})){
	std::list<SymbolOrPlaceholder> cycle = extractCycle(path, SymbolOrPlaceholder{SYMBOL, candidate});
	if (!tryEliminateEofAliases(cycle)) return false;
	}

	if(!validateCycles(SymbolOrPlaceholder{SYMBOL,candidate}, graph, symbolsVisited, path)) return false;
	}

	path.erase(s);
	return true;
	}

	bool
	VersionsGraph::validateCycles(){
	std::unordered_set<SymbolOrPlaceholder> symbolsVisited;
	Path path;
	std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder> graph(__inferiors);

	std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder>::const_iterator s;
	for (s = graph.begin(); s != graph.end(); ++s){
	if(!validateCycles(s->first, graph, symbolsVisited, path)) return false;
	}

	return true;
	}

	bool
	VersionsGraph::validate(){
	return validateCycles();
	}

	std::list<Symbol>
	VersionsGraph::expandPlaceholder(const SymbolOrPlaceholder& symbol, const Symbol& symbolPrev) const{
	std::list<Symbol> result;

	switch (symbol.flagEndOfLifePlaceholder){
	case SYMBOL:
	//skip self-loops
	if (symbol.symbol == symbolPrev) return {};

	return {symbol.symbol};

	case PLACEHOLDER:
	for (const auto& entry: boost::make_iterator_range(__inferiors.equal_range(symbol))){
	list<Symbol>&& childResult = expandPlaceholder(entry.second, symbolPrev);
	result.insert(result.end(), childResult.begin(), childResult.end());
	}

	if (__dictSuccessors.count(symbol.symbol)){
	Symbol knownSuccessor = __dictSuccessors.at(symbol.symbol);

	//skip alias loop
	if (knownSuccessor == symbolPrev) return {};

	for (const auto& entry: boost::make_iterator_range(__inferiors.equal_range(SymbolOrPlaceholder{SYMBOL, knownSuccessor}))){
	list<Symbol>&& childResult = expandPlaceholder(entry.second, knownSuccessor);
	result.insert(result.end(), childResult.begin(), childResult.end());
	}
	}

	break;
	}

	return result;
	}

	AttachmentsContainerDefault<std::list<Symbol>>*
	VersionsGraph::representAsAttachments() const {
	AttachmentsContainerDefault<std::list<Symbol>>* container = new AttachmentsContainerDefault<std::list<Symbol>>();

	std::map<Symbol, std::list<Symbol>> containerData;

	for(const auto& entry: __inferiors){
	if(entry.first.flagEndOfLifePlaceholder == PLACEHOLDER) continue;

	list<Symbol>& infs = containerData[entry.first.symbol];
	list<Symbol>&& infsExpanded = expandPlaceholder(entry.second, entry.first.symbol);
	infs.insert(infs.begin(), infsExpanded.begin(), infsExpanded.end());
	}

	for(const auto& entry: containerData){
	container->put(entry.first, entry.second);
	}

	return container;
	}

	std::list<Symbol>
	VersionsPass::process(const Expression& expression, PassContext context, const std::string& hintSymbol){
	if (expression.__state == Expression::COMPOUND){
	std::list<Symbol> resultDependencies;

	for (const Expression &op: expression.getOperands()) {
	std::list<Symbol> deps = process(op, context);

	resultDependencies.insert(resultDependencies.end(), deps.begin(), deps.end());
	}

	for (CodeScope* scope: expression.blocks) {
	std::list<Symbol> deps = Parent::process(scope, context);

	resultDependencies.insert(resultDependencies.end(), deps.begin(), deps.end());
	}

	return resultDependencies;
	}

	if (expression.__state == Expression::IDENT){
	const Symbol symb = Attachments::get<IdentifierSymbol>(expression);

	return processSymbol(symb, context, expression.getValueString());
	}

	return {};
	}

	//TODO versions, check (declaration.isDefined()) before processing declaration
	list<Symbol>
	VersionsPass::processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol){
	list<Symbol> result{symbol};

	if (__symbolsVisited.exists(symbol)){
	return result;
	}
	enum {MODE_ALIAS, MODE_COPY } mode = MODE_ALIAS;

	const Expression& declaration = CodeScope::getDefinition(symbol);

	if (declaration.op == Operator::CALL_INTRINSIC){
	if (declaration.getValueString() == "copy"){
	mode = MODE_COPY;
	}
	}

	if (symbol.identifier.version != VERSION_NONE){
	mode = MODE_COPY;

	if (symbol.identifier.version > 0){
	Symbol versionPrev = Symbol{ScopedSymbol{symbol.identifier.id, symbol.identifier.version-1}, symbol.scope};
	__graph.defineEndOfLife(versionPrev, symbol);
	}
	}

	PassContext context2 = context.updateScope(symbol.scope);
	std::list<Symbol> dependencies = process(declaration, context2, hintSymbol);

	switch (mode) {
	case MODE_COPY: __graph.applyDependentEndOfLife(SymbolOrPlaceholder{SYMBOL, symbol}, dependencies); break;
	case MODE_ALIAS: __graph.applyDependentEndOfLife(__graph.getEndOfLife(symbol), dependencies); break;
	}

	__graph.applyNatualDependencies(symbol, dependencies);
	__symbolsVisited.put(symbol, true);
	return list<Symbol>{symbol};
	}

	VersionsGraph&
	VersionsPass::getResultGraph(){
	return __graph;
	}

	void
	VersionsPass::finish(){
	assert(__graph.validate() && "Can't validate versions graph");

	Attachments::init<VersionImposedDependency>(__graph.representAsAttachments());
	}

	}} //end of namespace xreate::versions

versionspass.cppNo OneTemporaryActions

File Metadata

versionspass.cppView Options

Event Timeline

versionspass.cpp
No OneTemporary
Actions

versionspass.cpp
View Options