Build order determination for boulder.

baskit.d

import std.stdio, std.array, std.container, std.string, std.file, std.conv, std.algorithm, std.parallelism, std.path;
import moss.deps.dependency;
import moss.format.binary.reader;
import moss.format.binary.payload;
import moss.format.binary.payload.meta;
import moss.format.binary.payload.meta.record_pair;
import moss.format.binary.payload.layout;

void mkuniq(T)(ref T[] arr)
{
	arr = arr.sort!().uniq().array;
	// arr.length -= arr.uniq().copy(arr).length;
}

void dfs(int pkg)
{
	if (visited[pkg])
	{
		return;
	}
	visited[pkg] = true;

	foreach (child; children[pkg])
	{
		dfs(child);
	}
}

string[string] providerToPkg;
string[][string] deps;
int[] indeg;
string[int] idxToPkg;
int[string] pkgToIdx;
int[][] children;
bool[] visited;

void main(string[] args)
{
	auto manifestFiles = dirEntries(args[1], SpanMode.depth).filter!(f => f.name.endsWith(".bin"));

	write("Searching directory " ~ args[1] ~ " for potential packages...");
	foreach(DirEntry manifest; manifestFiles)
	{
		assert(manifest.isFile);
		string id = baseName(dirName(manifest.name));
		synchronized
		{
			if ((id in pkgToIdx) is null)
			{
				int idx = cast(int)idxToPkg.length;
				pkgToIdx[id] = idx;
				idxToPkg[idx] = id;
			}
		}
		Reader reader = new Reader(File(manifest.name));
		scope(exit) reader.close();
		string[] mydeps;

		foreach (ref payload; reader.payloads!MetaPayload)
		{
		    MetaPayload mp = cast(MetaPayload) payload;

			foreach (ref pair; mp)
			{
				if (pair.type() == RecordType.Provider)
				{
					Provider prvd = pair.get!Provider();
					providerToPkg[prvd.toString] = id;
				}
				else if (pair.type() == RecordType.Dependency)
				{
					Dependency dep = pair.get!Dependency();
					mydeps ~= dep.toString();
				}
			}
		}

		mkuniq(mydeps);
		deps[id] = mydeps[0 .. $];
	}
	writeln(" Done, found " ~ to!string(idxToPkg.length) ~ " packages.");
	writeln("Enter packages you want to rebuild. Enter \"end\" or Ctrl+D to finish.");

	// Get all the packages we want to rebuild
	string[] candidates;
	while (true)
	{
		write("> ");
		string line = chomp(readln());
		if (line is null || line == "end")
		{
			break;
		}

		if ((line in pkgToIdx) is null)
		{
			writeln("WARNING: cannot find [" ~ line ~ "] in existing packages!");
		}
		candidates ~= line;
		writeln(candidates);
	}
	mkuniq(candidates);

	int N = cast(int)idxToPkg.length;
	// Start filtering out duplicate dependencies
	int[][] parent;
	parent.length = N;
	children.length = N;
	visited.length = N;
	indeg.length = N;

	foreach (pkg, parents; deps)
	{
		int idx = pkgToIdx[pkg];

		if (parents.length > 0)
		{
			foreach (a; parents.filter!(p => (p in providerToPkg) !is null && providerToPkg[p] != p).map!(p => pkgToIdx[providerToPkg[p]]))
			{
				parent[idx] ~= a;
			}
			mkuniq(parent[idx]);
			indeg[idx] = cast(int)parent[idx].length;
			foreach(p; parent[idx])
			{
				children[p] ~= idx;
			}
		}
	}

	// Marking dependencies of packages we want to rebuild.
	foreach(c; candidates)
	{
		dfs(pkgToIdx[c]);
	}

	writeln("Here is the correct rebuild order:");

	auto q = DList!int();
	foreach(int i, deg; indeg)
	{
		if (deg == 0)
		{
			q.insert(i);
		}
	}

	while (!q.empty())
	{
		int pkg = q.front();
		if (visited[pkg])
		{
			writeln(idxToPkg[pkg]);
		}
		q.removeFront();

		foreach(int child; children[pkg])
		{
			indeg[child]--;
			if (indeg[child] == 0)
			{
				q.insert(child);
			}
		}
	}
}