Dependency resolution

dep_solve.cpp

#include <fstream>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>

#include "constraint_solver/constraint_solver.h"

// Unzip https://github.com/google/or-tools/releases/tag/v2015-12 next to this file

// Compiles with:
// g++ dep_solve.cpp -o solver --std=c++11 -Ior-tools.Linux64/include -Lor-tools.Linux64/lib -Wno-deprecated -lortools

// Run with:
// LD_LIBRARY_PATH=or-tools.Linux64/lib/ ./solver test_dep.txt

using namespace operations_research;

// Used to order versions based on their semver
bool semverCompare (const std::pair<std::string, int>& a, const std::pair<std::string, int>& b)
{
	// TODO: do semver compare
	return a.second > b.second;
}

class Database
{
public:
	std::vector<std::vector<int>> deps; // For each version the list of dependencies
	std::vector<std::vector<int>> versions; // For each library the list of versions
	std::vector<std::string> names; // Name of each version
	std::vector<int> distances; // Distance to the latest version, ie. index in a reverse sorted array of versions
	
private:
	std::unordered_map<std::string, int> lib2id;
	std::unordered_map<std::string, int> version2id;

public:
	Database (const std::string& file)
	{
		// Init
		std::ifstream stream(file);
	
		if (!stream.is_open()) 
		{
			std::cerr << "The file couldn't be opened." << std::endl;
			throw;
		}
		
		
		deps = std::vector<std::vector<int>>();
		versions = std::vector<std::vector<int>>();
		names = std::vector<std::string>();
		std::unordered_map<std::string, int> lib2id = std::unordered_map<std::string, int>();
		std::unordered_map<std::string, int> version2id = std::unordered_map<std::string, int>();
		
		// Parse the file
		std::string line;
		int state = 0;
		int curVersion;
		int nextLibId = 0;
		int nextVersionId = 0;
		
		while (getline(stream, line) && line != "")
		{
			std::istringstream iss(line);
			
			switch (state)
			{
				case 0: // New lib/version line
				{
					std::string name, version;
					iss >> name >> version;

					if (!isVersionKnown(line)) // First occurence of version
					{
						names.push_back(line);
						setVersionId(line, nextVersionId++);
						deps.push_back(std::vector<int>());
					}
					curVersion = getVersionId(line);

					if (isLibKnown(name)) // Not first occurence of lib, add version
					{
						versions[getLibId(name)].push_back(curVersion);
					}
					else
					{
						versions.push_back(std::vector<int>());
						setLibId(name, nextLibId++);
						versions[getLibId(name)].push_back(curVersion);
					}
					
					state = 1; // Next are dependencies
				}
				break;
				
				case 1: // Dependency line
				{
					std::string name, version;
					iss >> name;
					
					if (name == "/")
					{
						// List ended, next is a lib
						state = 0;
					}
					else
					{
						iss >> version;
						
						if (version == "any")
						{
							// All versions of this lib are in the file,
							// all lib from the file need to have a version,
							// safely ignore
							continue;
						}
						
						if (!isVersionKnown(line)) // First occurence of version
						{
							names.push_back(line);
							setVersionId(line, nextVersionId++);
							deps.push_back(std::vector<int>());
						}
						
						deps[curVersion].push_back(getVersionId(line));
					}
				}
				break;
			}
		}
		
		stream.close();
		
		// Calculate for each lib the distances of each version to the latest
		distances = std::vector<int>(names.size());
		for (auto lib : versions)
		{
			std::vector<std::pair<std::string, int>> link = std::vector<std::pair<std::string, int>>();
			
			for (int index : lib)
			{
				std::istringstream iss(names[index]);
				std::string name, version;
				iss >> name >> version;
				
				link.push_back(std::make_pair(version, index));
			}
			
			std::sort(link.begin(), link.end(), semverCompare);
			
			for (int i = 0 ; i < lib.size() ; i++)
			{
				distances[link[i].second] = i;
			}
		}
	}
	
private:
	// If you want to know why: because map is broken, never find my keys :(
	bool isLibKnown (std::string name) { return lib2id[name] != 0; }
	int getLibId (std::string name) { return lib2id[name] - 1; }
	void setLibId (std::string name, int value) { lib2id[name] = value + 1; }

	bool isVersionKnown (std::string name) { return version2id[name] != 0; }
	int getVersionId (std::string name) { return version2id[name] - 1; }
	void setVersionId (std::string name, int value) { version2id[name] = value + 1; }
};

int main (int argc, char** argv)
{
	if (argc == 1)
	{
		std::cout << argv[0] << " file.txt" << std::endl;
		return 0;
	}
	if (argc != 2)
	{
		std::cerr << "Wrong number of arguments." << std::endl;
		return 1;
	}
	
	Solver solver("Dependency solver");
	
	// Load "database"
	Database base(argv[1]);

	// Define decision variables: 0/1 all boolean
	std::vector<IntVar*> X = std::vector<IntVar*>();
	solver.MakeBoolVarArray(base.deps.size(), "X", &X);
	
	// Require the lib when want to install
	solver.AddConstraint(solver.MakeEquality(X[0], 1));

	// Each lib mentionned must have one and only one version to install
	for (auto lib : base.versions)
	{
		std::vector<IntVar*> versions = std::vector<IntVar*>();

		for (int version : lib)
		{
			versions.push_back(X[version]);
		}
		
		solver.AddConstraint(solver.MakeEquality(solver.MakeSum(versions)->Var(), 1));
	}

	// Add dependency constraint for each lib/version
	int i = -1;
	for (auto versionDeps : base.deps)
	{
		i++;
		
		if (versionDeps.size() == 0)
		{
			// no dependency, no constraint
			continue;
		}
		
		// version * (sum of dependencies) == version * |dependencies|
		// If version == 0 (all var are boolean) then 0 * _ == 0 * _ => 0 == 0 always true
		// If version == 1 then all its dependencies must be at 1 for the sum to equal the number of deps
		
		std::vector<IntVar*> deps = std::vector<IntVar*>();
		for (int d : versionDeps)
		{
			deps.push_back(X[d]);
		}
		IntVar* left = solver.MakeProd(X[i], solver.MakeSum(deps)->Var())->Var();
		IntVar* right = solver.MakeProd(X[i], versionDeps.size())->Var();
		solver.AddConstraint(solver.MakeEquality(left, right));
	}

	// Decision builder to search for solutions
	DecisionBuilder* const db = solver.MakePhase(X, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MAX_VALUE);
	
	// Objective: minimize the total distance between the latest version of a lib and the one we are installing
	OptimizeVar* const objective = solver.MakeWeightedMinimize(X, base.distances, 1);
	
	// Solve the problem, if there's no solution then lib cannot be installed and that's not ok, shouldn't be on haxelib
	solver.NewSearch(db, objective);
	
	if (solver.NextSolution())
	{
		// Print what library/version will be installed as dependencies
		std::cout << "Dependencies required to install " << base.names[0] << " :" << std::endl;
		for (int i = 1 ; i < base.deps.size() ; i++)
		{
			if (X[i]->Value() == 1)
			{
				std::cout << " * " << base.names[i] << std::endl;
			}
		}
	}

	// Done :)
	solver.EndSearch();
	std::cout << "Time to compute: " << solver.wall_time() << " s" << std::endl;

	return 0;
}

test_dep.txt

ufront 2.0.0
ufront-mvc 1.1.0
ufront-orm 1.1.0
ufront-easyauth 1.0.0
/
ufront-mvc 1.1.0
compiletime 2.6.0
minject 2.0.0-rc.1
tink_core 1.0.0-rc.11
tink_macro 0.6.4
/
ufront-orm 1.1.0
tink_core 1.0.0-rc.11
tink_macro 0.6.4
/
ufront-easyauth 1.0.0
PBKDF2 1.0.0
ufront-mvc 1.1.0
ufront-orm 1.1.0
/
compiletime 2.6.0
/
minject 2.0.0-rc.1
/
tink_macro 0.6.4
tink_core any
/
PBKDF2 1.0.0
/
tink_core 1.0.0-alpha
/
tink_core 1.0.0-beta.3
/
tink_core 1.0.0-beta.4
/
tink_core 1.0.0-rc.1
/
tink_core 1.0.0-rc.2
/
tink_core 1.0.0-rc.4
/
tink_core 1.0.0-rc.5
/
tink_core 1.0.0-rc.6
/
tink_core 1.0.0-rc.7
/
tink_core 1.0.0-rc.8
/
tink_core 1.0.0-rc.9
/
tink_core 1.0.0-rc.10
/
tink_core 1.0.0-rc.11
/
tink_core 1.0.0-rc.12
/