Wrong device reported missing

[byorgey]

Describe the bug
In certain situations with devices that don't exist, an error is generated saying that some other device is missing (even though it is not).

To Reproduce

• Start a classic mode game with --cheat
• Switch into creative mode and create "branch predictor"
• Switch back out of creative mode
• Type build {move; if (1 > 2) {} {}}
  • As expected we get an error saying no device provides the compare capability.
• Now type build {move; turn left; if (1 > 2) {} {}}
  • All we have done is add turn left; we would expect to get the same error. Instead we get an error like You do not have the devices required for: 'move; turn left; if (1 > 2) {noop} {noop}' please obtain: - branch predictor
  • But we do have a branch predictor, so this error is bogus. Not sure yet whether the capability checking or error reporting is to blame.

Additional context
First noticed this in #373 (comment) . Note that once #395 is merged then we will have a comparator device so the above example won't work any more.

[byorgey]

An example that still shows this problem now is build {move; teleport base (2,3)} vs build {move; turn left; teleport base (2,3)}. The first gives an appropriate error, whereas the second says we are missing treads.

[byorgey]

I've traced this as far as seeing that the Incapable exception given to formatExn is already bogus. formatExn seems to be doing its job properly, the problem is with wherever the Incapable exception is generated (probably the checkRequirements function).

[byorgey]

The example with teleport no longer works since we get an error about needing an ADT calculator instead. However, the problem still exists and can be illustrated by the difference between build {move; x <- whereami} (correct) vs build {move; turn left; x <- whereami} (incorrect).

[byorgey]

Strangely both move and turn left are required in the examples here. Omitting either one leads to the correct output. Including a single one of those commands twice (e.g. move; move) also leads to correct output. I've tried mixing other commands and the only thing so far that seems to trigger the incorrect output is to have both a call to move and a call to turn left before invoking a command without a device, such as whereami.

Hmm, breakthrough? Maybe it has to do with the fact that move; turn left requires two capabilities (CMove and CTurn) which are both provided by the same device (treads). Maybe there's a bug in checkRequirements related to that scenario. That would explain why it seems like the bug is only triggered when both of those specific commands are used.

I can also trigger the bug with build {give base "tree"; place "tree"; x <- whereami}, which seems to confirm my hypothesis (the give and place capabilities are both provided by a grabber or fast grabber).

However, build {grab; harvest; x <- whereami} does not trigger the bug. In this case grab and harvest capabilities are both provided by a harvester, but that's the only device that provides both. So perhaps the bug is only triggered when there are multiple devices that provide both capabilities...?

[byorgey]

I think the problem has to do with the fact that in this code:

swarm/src/Swarm/Game/Step.hs

Lines 1746 to 1752 in d62d8c5

	(deviceSets, missingDeviceSets) =
	Lens.over both (nubOrd . map S.fromList) . unzip $
	map (ignoreOK . L.partition deviceOK) capDevices
	formatDevices = T.intercalate " or " . map (^. entityName) . S.toList
	-- capabilities not provided by any device in inventory
	missingCaps = S.fromList . map fst . filter (null . snd) $ zip caps deviceSets

deviceSets is defined via nubOrd (hence it does not necessarily have the same length as the original capDevices) but yet we later do zip caps deviceSets, expecting the entries of deviceSets to still line up with caps.

I think this code

swarm/src/Swarm/Game/Step.hs

Lines 1729 to 1734 in d62d8c5

	let -- List of possible devices per requirement. Devices for
	-- required capabilities come first, then singleton devices
	-- that are required directly. This order is important since
	-- later we zip required capabilities with this list to figure
	-- out which capabilities are missing.
	capDevices = map (`deviceForCap` em) caps ++ map (: []) devs

is a bad idea: it creates an easy-to-get-wrong invariant that anything coming from that list must be kept in the same order and no duplicates dropped, since later it will get zipped with something. We should instead do the zip right here and carry along the capabilities through the rest of the process, safely paired up with their corresponding devices.

[xsebek]

@byorgey the lines have shifted a bit it seems - if you use a link with specific commit GitHub should even show a preview. 😉

swarm/src/Swarm/Game/Step.hs

Lines 1600 to 1606 in 1930fe6

	(deviceSets, missingDeviceSets) =
	Lens.over both (nubOrd . map S.fromList) . unzip $
	map (ignoreOK . L.partition deviceOK) capDevices
	formatDevices = T.intercalate " or " . map (^. entityName) . S.toList
	-- capabilities not provided by any device in inventory
	missingCaps = S.fromList . map fst . filter (null . snd) $ zip caps deviceSets

[byorgey]

@xsebek Thanks! I knew about that but forgot when I made those links. Pro tip (tm) for anyone reading this later --- when viewing some code you can hit the y key to turn the URL into a commit-specific URL.