how to debug `Root package X reference Y cannot be satisfied` ?

[timotheecour]

@s-ludwig @MartinNowak
How do I debug cases where I'm getting things like:
Root package lhd reference mir-algorithm ~>0.6.6 cannot be satisfied. ?
Despite running dub via --vverbose I don't understand why dub can't pick up the version I'm asking for: longs include:

Configurations used for dependency resolution:
  dinotify (0, required): [0.2.1]
  mir-algorithm (2, required): [invalid]

why is mir-algorithm (2, required): [invalid] shown ? the previous mention of it in logs is:

Return for mir-algorithm: [0.6.6, 0.6.5, 0.6.4, 0.6.3, 0.6.2, 0.6.1, 0.6.0, 0.5.17, 0.5.16, 0.5.15, 0.5.14, 0.5.13, 0.5.12, 0.5.11, 0.5.10, 0.5.9, 0.5.8, 0.5.7, 0.5.6, 0.5.5, 0.5.4, 0.5.3, 0.5.2, 0.5.1, 0.5.0, 0.4.14, 0.4.13, 0.4.12, 0.4.11, 0.4.10, 0.4.9, 0.4.8, 0.4.7, 0.4.6, 0.4.5, 0.4.4, 0.4.3, 0.4.2, 0.4.1, 0.4.0, 0.3.0, 0.2.0, 0.1.1, 0.1.0, 0.0.39, 0.0.38, 0.0.37, 0.0.36, 0.0.35, 0.0.34, 0.0.33, 0.0.32, 0.0.31, 0.0.30, 0.0.29, 0.0.28, 0.0.27, 0.0.26, 0.0.25, 0.0.24, 0.0.23, 0.0.22, 0.0.21, 0.0.20, 0.0.19, 0.0.18, 0.0.17, 0.0.16, 0.0.15, 0.0.14, 0.0.13, 0.0.12, 0.0.11, 0.0.10, 0.0.9, 0.0.8, 0.0.7, 0.0.6, 0.0.5, 0.0.4, 0.0.3, 0.0.2, 0.0.1, ~master, ~ch2, ~bitpack-update]

so I would expect dub to pickup 0.6.6

[MartinNowak]

invalid is used as a placeholder for not selected optional dependencies, see

dub/source/dub/dependencyresolver.d

Line 111 in ba26490

// append an invalid configuration to denote an unchosen dependency

.
The output of unresolved dependencies isn't too nice atm. Looks like mir-algorithm wasn't included b/c it's an optional dependency.

[timotheecour]

why is it optional?
my project json.deps showed:

"dependencies": {
  "mir-algorithm": "~>0.6.6",
  // other stuff
}

The root cause ended up being that a (recursive) dependency had something like "mir-algorithm": "~>0.4.0", howeever nowhere in the dub logs (with --vverbose) did that show up as root cause, leaving the user to painfully look at each dependency's dependencies; dub should know this so it should print it

EDIT: maybe a (recursive) dependency listed mir-algorithm as optional so it became optional? if so that's a bug (looking at dub issues I see lots of issues related to optional dependencies)

[MartinNowak]

The placeholder is added early on and will be the last left when none of the available versions fullfill the requirements as in your case, so it didn't have anything to do with optional here.

It's somewhat tricky to record why a certain version of a package is not valid, even when capturing all conflicts wouldn't require lots of mem, they'd be hard to present to a user.
The core of the resolver is a very small loop (

dub/source/dub/dependencyresolver.d

Lines 233 to 238 in ba26490

	// find the next combination of configurations
	foreach_reverse (pi, ref i; config_indices) {
	if (pi > conflict_index) i = 0;
	else if (++i >= all_configs[pi].length) i = 0;
	else break;
	}

) testing different sets of versions from all available versions. The iteration works a bit like the Mengenlehreuhr.

[timotheecour]

i think #1154 fixed it with better diagnostics