diff --git a/.travis.yml b/.travis.yml
index d6b50cc..86f505a 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -30,8 +30,6 @@
       env: [FRONTEND=2.068]
     - d: dmd-2.067.1
       env: [FRONTEND=2.067]
-    - d: dmd-2.066.1
-      env: [FRONTEND=2.066]
     - d: ldc-beta
       env: [FRONTEND=2.073]
     - d: ldc
@@ -48,10 +46,8 @@
       env: [FRONTEND=2.068]
     - d: gdc
       env: [FRONTEND=2.068]
-    - d: gdc-5.2.0
-      env: [FRONTEND=2.066]
-    - d: gdc-4.9.2
-      env: [FRONTEND=2.066]
+    - d: gdc-4.8.5
+      env: [FRONTEND=2.068]
 
   allow_failures:
     - d: gdc
diff --git a/source/dub/dependency.d b/source/dub/dependency.d
index 40b4863..a38a411 100644
--- a/source/dub/dependency.d
+++ b/source/dub/dependency.d
@@ -369,9 +369,14 @@
 	/// ditto
 	hash_t toHash() const nothrow @trusted  {
 		try {
-			auto strhash = &typeid(string).getHash;
-			auto str = this.toString();
-			return strhash(&str);
+			size_t hash = 0;
+			hash = m_inclusiveA.hashOf(hash);
+			hash = m_versA.toString().hashOf(hash);
+			hash = m_inclusiveB.hashOf(hash);
+			hash = m_versB.toString().hashOf(hash);
+			hash = m_optional.hashOf(hash);
+			hash = m_default.hashOf(hash);
+			return hash;
 		} catch (Exception) assert(false);
 	}
 
@@ -387,11 +392,18 @@
 
 		This is true in particular for the `any` constant.
 	*/
-	bool matchesAny() const {
-		auto cmp = Dependency("*");
-		cmp.optional = m_optional;
-		cmp.default_ = m_default;
-		return cmp == this;
+	bool matchesAny()
+	const {
+		return m_inclusiveA && m_inclusiveB
+			&& m_versA.toString() == "0.0.0"
+			&& m_versB == Version.maxRelease;
+	}
+
+	unittest {
+		assert(Dependency("*").matchesAny);
+		assert(!Dependency(">0.0.0").matchesAny);
+		assert(!Dependency(">=1.0.0").matchesAny);
+		assert(!Dependency("<1.0.0").matchesAny);
 	}
 
 	/** Tests if the specification matches a specific version.
@@ -427,20 +439,19 @@
 	const {
 		if (this.matchesAny) return o;
 		if (o.matchesAny) return this;
-		if (!this.valid || !o.valid) return invalid;
 		if (m_versA.isBranch != o.m_versA.isBranch) return invalid;
 		if (m_versB.isBranch != o.m_versB.isBranch) return invalid;
 		if (m_versA.isBranch) return m_versA == o.m_versA ? this : invalid;
 		if (this.path != o.path) return invalid;
 
-		Version a = m_versA > o.m_versA ? m_versA : o.m_versA;
-		Version b = m_versB < o.m_versB ? m_versB : o.m_versB;
+		int acmp = m_versA.opCmp(o.m_versA);
+		int bcmp = m_versB.opCmp(o.m_versB);
 
 		Dependency d = this;
-		d.m_inclusiveA = !m_inclusiveA && m_versA >= o.m_versA ? false : o.m_inclusiveA;
-		d.m_versA = a;
-		d.m_inclusiveB = !m_inclusiveB && m_versB <= o.m_versB ? false : o.m_inclusiveB;
-		d.m_versB = b;
+		d.m_inclusiveA = !m_inclusiveA && acmp >= 0 ? false : o.m_inclusiveA;
+		d.m_versA = acmp > 0 ? m_versA : o.m_versA;
+		d.m_inclusiveB = !m_inclusiveB && bcmp <= 0 ? false : o.m_inclusiveB;
+		d.m_versB = bcmp < 0 ? m_versB : o.m_versB;
 		d.m_optional = m_optional && o.m_optional;
 		if (!d.valid) return invalid;
 
@@ -640,24 +651,24 @@
 struct Version {
 @safe:
 	private {
-		enum MAX_VERS = "99999.0.0";
-		enum UNKNOWN_VERS = "unknown";
+		static immutable MAX_VERS = "99999.0.0";
+		static immutable UNKNOWN_VERS = "unknown";
+		static immutable masterString = "~master";
 		enum branchPrefix = '~';
-		enum masterString = "~master";
 		string m_version;
 	}
 
-	static @property Version minRelease() { return Version("0.0.0"); }
-	static @property Version maxRelease() { return Version(MAX_VERS); }
-	static @property Version masterBranch() { return Version(masterString); }
-	static @property Version unknown() { return Version(UNKNOWN_VERS); }
+	static immutable Version minRelease = Version("0.0.0");
+	static immutable Version maxRelease = Version(MAX_VERS);
+	static immutable Version masterBranch = Version(masterString);
+	static immutable Version unknown = Version(UNKNOWN_VERS);
 
 	/** Constructs a new `Version` from its string representation.
 	*/
 	this(string vers)
 	{
 		enforce(vers.length > 1, "Version strings must not be empty.");
-		if (vers[0] != branchPrefix && vers != UNKNOWN_VERS)
+		if (vers[0] != branchPrefix && vers.ptr !is UNKNOWN_VERS.ptr)
 			enforce(vers.isValidVersion(), "Invalid SemVer format: " ~ vers);
 		m_version = vers;
 	}
@@ -669,15 +680,10 @@
 	*/
 	static Version fromString(string vers) { return Version(vers); }
 
-	bool opEquals(const Version oth) const {
-		if (isUnknown || oth.isUnknown) {
-			throw new Exception("Can't compare unknown versions! (this: %s, other: %s)".format(this, oth));
-		}
-		return opCmp(oth) == 0;
-	}
+	bool opEquals(const Version oth) const { return opCmp(oth) == 0; }
 
 	/// Tests if this represents a branch instead of a version.
-	@property bool isBranch() const { return !m_version.empty && m_version[0] == branchPrefix; }
+	@property bool isBranch() const { return m_version.length > 0 && m_version[0] == branchPrefix; }
 
 	/// Tests if this represents the master branch "~master".
 	@property bool isMaster() const { return m_version == masterString; }
diff --git a/source/dub/dependencyresolver.d b/source/dub/dependencyresolver.d
index a2102bd..6b42d80 100644
--- a/source/dub/dependencyresolver.d
+++ b/source/dub/dependencyresolver.d
@@ -14,6 +14,7 @@
 import std.array : appender, array;
 import std.conv : to;
 import std.exception : enforce;
+import std.typecons : Nullable;
 import std.string : format, indexOf, lastIndexOf;
 
 
@@ -41,7 +42,8 @@
 		CONFIG config;
 
 		hash_t toHash() const nothrow @trusted {
-			size_t ret = typeid(string).getHash(&pack);
+			size_t ret = pack.hashOf();
+			//size_t ret = typeid(string).getHash(&pack);
 			ret ^= typeid(CONFIG).getHash(&config);
 			return ret;
 		}
@@ -123,7 +125,7 @@
 		config_indices[] = 0;
 
 		visited = null;
-		sizediff_t validateConfigs(TreeNode parent, ref string error)
+		sizediff_t validateConfigs(TreeNode parent, ref ConflictError error)
 		{
 			import std.algorithm : max;
 
@@ -141,7 +143,7 @@
 
 				// get the current config/version of the current dependency
 				sizediff_t childidx = package_indices[basepack];
-				if (all_configs[childidx] == [CONFIG.invalid]) {
+				if (all_configs[childidx].length == 1 && all_configs[childidx][0] == CONFIG.invalid) {
 					// ignore invalid optional dependencies
 					if (ch.depType != DependencyType.required)
 						continue;
@@ -160,7 +162,7 @@
 					}
 					// choose another parent config to avoid the invalid child
 					if (parentidx > maxcpi) {
-						error = format("Package %s contains invalid dependency %s (no version candidates)", parent.pack, ch.pack);
+						error = ConflictError(ConflictError.Kind.invalidDependency, parent, ch, CONFIG.invalid);
 						logDiagnostic("%s (ci=%s)", error, parentidx);
 						maxcpi = parentidx;
 					}
@@ -175,13 +177,13 @@
 
 						// if we are at the root level, we can safely skip the maxcpi computation and instead choose another childidx config
 						if (parentbase == root_base_pack) {
-							error = format("No match for dependency %s %s of %s", ch.pack, ch.configs, parent.pack);
+							error = ConflictError(ConflictError.Kind.noRootMatch, parent, ch, config);
 							return childidx;
 						}
 
 						if (childidx > maxcpi) {
 							maxcpi = max(childidx, parentidx);
-							error = format("Dependency %s -> %s %s mismatches with selected version %s", parent.pack, ch.pack, ch.configs, config);
+							error = ConflictError(ConflictError.Kind.childMismatch, parent, ch, config);
 							logDebug("%s (ci=%s)", error, maxcpi);
 						}
 
@@ -196,14 +198,26 @@
 			return maxcpi;
 		}
 
-		string first_error;
+		Nullable!ConflictError first_error;
+		size_t loop_counter = 0;
+
+		// Leave the possibility to opt-out from the loop limit
+		import std.process : environment;
+		bool no_loop_limit = environment.get("DUB_NO_RESOLVE_LIMIT") !is null;
 
 		while (true) {
+			assert(no_loop_limit || loop_counter++ < 1_000_000,
+				"The dependency resolution process is taking too long. The"
+				~ " dependency graph is likely hitting a pathological case in"
+				~ " the resolution algorithm. Please file a bug report at"
+				~ " https://github.com/dlang/dub/issues and mention the package"
+				~ " recipe that reproduces this error.");
+
 			// check if the current combination of configurations works out
 			visited = null;
-			string error;
+			ConflictError error;
 			auto conflict_index = validateConfigs(root, error);
-			if (first_error is null) first_error = error;
+			if (first_error.isNull) first_error = error;
 
 			// print out current iteration state
 			logDebug("Interation (ci=%s) %s", conflict_index, {
@@ -237,7 +251,7 @@
 				else break;
 			}
 			if (config_indices.all!"a==0") {
-				if (throw_on_failure) throw new Exception("Could not find a valid dependency tree configuration: "~first_error);
+				if (throw_on_failure) throw new Exception(format("Could not find a valid dependency tree configuration: %s", first_error.get));
 				else return null;
 			}
 		}
@@ -271,6 +285,36 @@
 			if (p !in required)
 				configs.remove(p);
 	}
+
+	private struct ConflictError {
+		enum Kind {
+			none,
+			noRootMatch,
+			childMismatch,
+			invalidDependency
+		}
+
+		Kind kind;
+		TreeNode parent;
+		TreeNodes child;
+		CONFIG config;
+
+		string toString()
+		const {
+			final switch (kind) {
+				case Kind.none: return "no error";
+				case Kind.noRootMatch:
+					return "No match for dependency %s %s of %s"
+						.format(child.pack, child.configs, parent.pack);
+				case Kind.childMismatch:
+					return "Dependency %s -> %s %s mismatches with selected version %s"
+						.format(parent.pack, child.pack, child.configs, config);
+				case Kind.invalidDependency:
+					return "Package %s contains invalid dependency %s (no version candidates)"
+						.format(parent.pack, child.pack);
+			}
+		}
+	}
 }
 
 enum DependencyType {
@@ -281,7 +325,7 @@
 
 private string basePackage(string p)
 {
-	auto idx = indexOf(p, ":");
+	auto idx = indexOf(p, ':');
 	if (idx < 0) return p;
 	return p[0 .. idx];
 }
diff --git a/source/dub/dub.d b/source/dub/dub.d
index c236d3d..45f862d 100644
--- a/source/dub/dub.d
+++ b/source/dub/dub.d
@@ -1243,6 +1243,8 @@
 		SelectedVersions m_selectedVersions;
 		Package m_rootPackage;
 		bool[string] m_packagesToUpgrade;
+		Package[PackageDependency] m_packages;
+		TreeNodes[][TreeNode] m_children;
 	}
 
 
@@ -1334,6 +1336,15 @@
 
 	protected override TreeNodes[] getChildren(TreeNode node)
 	{
+		if (auto pc = node in m_children)
+			return *pc;
+		auto ret = getChildrenRaw(node);
+		m_children[node] = ret;
+		return ret;
+	}
+
+	private final TreeNodes[] getChildrenRaw(TreeNode node)
+	{
 		import std.array : appender;
 		auto ret = appender!(TreeNodes[]);
 		auto pack = getPackage(node.pack, node.config);
@@ -1344,7 +1355,7 @@
 		}
 		auto basepack = pack.basePackage;
 
-		foreach (d; pack.getAllDependencies()) {
+		foreach (d; pack.getAllDependenciesRange()) {
 			auto dbasename = getBasePackageName(d.name);
 
 			// detect dependencies to the root package (or sub packages thereof)
@@ -1396,6 +1407,16 @@
 
 	private Package getPackage(string name, Dependency dep)
 	{
+		auto key = PackageDependency(name, dep);
+		if (auto pp = key in m_packages)
+			return *pp;
+		auto p = getPackageRaw(name, dep);
+		m_packages[key] = p;
+		return p;
+	}
+
+	private Package getPackageRaw(string name, Dependency dep)
+	{
 		auto basename = getBasePackageName(name);
 
 		// for sub packages, first try to get them from the base package
diff --git a/source/dub/package_.d b/source/dub/package_.d
index 98d0dc9..5197a45 100644
--- a/source/dub/package_.d
+++ b/source/dub/package_.d
@@ -526,14 +526,24 @@
 	PackageDependency[] getAllDependencies()
 	const {
 		auto ret = appender!(PackageDependency[]);
-		foreach (n, d; this.recipe.buildSettings.dependencies)
-			ret ~= PackageDependency(n, d);
-		foreach (ref c; this.recipe.configurations)
-			foreach (n, d; c.buildSettings.dependencies)
-				ret ~= PackageDependency(n, d);
+		getAllDependenciesRange().copy(ret);
 		return ret.data;
 	}
 
+	// Left as package until the final API for this has been found
+	package auto getAllDependenciesRange()
+	const {
+		return this.recipe.buildSettings.dependencies.byKeyValue
+			.map!(bs => PackageDependency(bs.key, bs.value))
+			.chain(
+				this.recipe.configurations
+					.map!(c => c.buildSettings.dependencies.byKeyValue
+						.map!(bs => PackageDependency(bs.key, bs.value))
+					)
+					.joiner()
+			);
+	}
+
 
 	/** Returns a description of the package for use in IDEs or build tools.
 	*/
diff --git a/source/dub/semver.d b/source/dub/semver.d
index ac8f6e7..dd68102 100644
--- a/source/dub/semver.d
+++ b/source/dub/semver.d
@@ -26,7 +26,7 @@
 	Validates a version string according to the SemVer specification.
 */
 bool isValidVersion(string ver)
-{
+pure @nogc {
 	// NOTE: this is not by spec, but to ensure sane input
 	if (ver.length > 256) return false;
 
@@ -102,7 +102,7 @@
 /**
 	Determines if a given valid SemVer version has a pre-release suffix.
 */
-bool isPreReleaseVersion(string ver)
+bool isPreReleaseVersion(string ver) pure @nogc
 in { assert(isValidVersion(ver)); }
 body {
 	foreach (i; 0 .. 2) {
@@ -136,14 +136,14 @@
 		equal, and a positive number otherwise.
 */
 int compareVersions(string a, string b)
-{
+pure @nogc {
 	// compare a.b.c numerically
 	if (auto ret = compareNumber(a, b)) return ret;
 	assert(a[0] == '.' && b[0] == '.');
-	a.popFront(); b.popFront();
+	a = a[1 .. $]; b = b[1 .. $];
 	if (auto ret = compareNumber(a, b)) return ret;
 	assert(a[0] == '.' && b[0] == '.');
-	a.popFront(); b.popFront();
+	a = a[1 .. $]; b = b[1 .. $];
 	if (auto ret = compareNumber(a, b)) return ret;
 
 	// give precedence to non-prerelease versions
@@ -154,7 +154,7 @@
 
 	// compare the prerelease tail lexicographically
 	do {
-		a.popFront(); b.popFront();
+		a = a[1 .. $]; b = b[1 .. $];
 		if (auto ret = compareIdentifier(a, b)) return ret;
 	} while (a.length > 0 && b.length > 0 && a[0] != '+' && b[0] != '+');
 
@@ -225,7 +225,8 @@
 
 	See_Also: `expandVersion`
 */
-string bumpVersion(string ver) {
+string bumpVersion(string ver)
+pure {
 	// Cut off metadata and prerelease information.
 	auto mi = ver.indexOfAny("+-");
 	if (mi > 0) ver = ver[0..mi];
@@ -258,7 +259,8 @@
 
 	See_Also: `bumpVersion`
 */
-string expandVersion(string ver) {
+string expandVersion(string ver)
+pure {
 	auto mi = ver.indexOfAny("+-");
 	auto sub = "";
 	if (mi > 0) {
@@ -282,18 +284,18 @@
 }
 
 private int compareIdentifier(ref string a, ref string b)
-{
+pure @nogc {
 	bool anumber = true;
 	bool bnumber = true;
 	bool aempty = true, bempty = true;
 	int res = 0;
 	while (true) {
-		if (a.front != b.front && res == 0) res = a.front - b.front;
-		if (anumber && (a.front < '0' || a.front > '9')) anumber = false;
-		if (bnumber && (b.front < '0' || b.front > '9')) bnumber = false;
-		a.popFront(); b.popFront();
-		aempty = a.empty || a.front == '.' || a.front == '+';
-		bempty = b.empty || b.front == '.' || b.front == '+';
+		if (a[0] != b[0] && res == 0) res = a[0] - b[0];
+		if (anumber && (a[0] < '0' || a[0] > '9')) anumber = false;
+		if (bnumber && (b[0] < '0' || b[0] > '9')) bnumber = false;
+		a = a[1 .. $]; b = b[1 .. $];
+		aempty = !a.length || a[0] == '.' || a[0] == '+';
+		bempty = !b.length || b[0] == '.' || b[0] == '+';
 		if (aempty || bempty) break;
 	}
 
@@ -312,20 +314,20 @@
 }
 
 private int compareNumber(ref string a, ref string b)
-{
+pure @nogc {
 	int res = 0;
 	while (true) {
-		if (a.front != b.front && res == 0) res = a.front - b.front;
-		a.popFront(); b.popFront();
-		auto aempty = a.empty || (a.front < '0' || a.front > '9');
-		auto bempty = b.empty || (b.front < '0' || b.front > '9');
+		if (a[0] != b[0] && res == 0) res = a[0] - b[0];
+		a = a[1 .. $]; b = b[1 .. $];
+		auto aempty = !a.length || (a[0] < '0' || a[0] > '9');
+		auto bempty = !b.length || (b[0] < '0' || b[0] > '9');
 		if (aempty != bempty) return bempty - aempty;
 		if (aempty) return res;
 	}
 }
 
 private bool isValidIdentifierChain(string str, bool allow_leading_zeros = false)
-{
+pure @nogc {
 	if (str.length == 0) return false;
 	while (str.length) {
 		auto end = str.indexOf('.');
@@ -338,7 +340,7 @@
 }
 
 private bool isValidIdentifier(string str, bool allow_leading_zeros = false)
-{
+pure @nogc {
 	if (str.length < 1) return false;
 
 	bool numeric = true;
@@ -361,7 +363,7 @@
 }
 
 private bool isValidNumber(string str)
-{
+pure @nogc {
 	if (str.length < 1) return false;
 	foreach (ch; str)
 		if (ch < '0' || ch > '9')
@@ -374,7 +376,7 @@
 }
 
 private sizediff_t indexOfAny(string str, in char[] chars)
-{
+pure @nogc {
 	sizediff_t ret = -1;
 	foreach (ch; chars) {
 		auto idx = str.indexOf(ch);