DimensionalDoors

DimensionalDoors

12M Downloads

[1.12.2] Wrongly implemented binarySearch algorithm causes gateway generation to fail when dim blacklists are used

Taschenmogul opened this issue ยท 0 comments

commented

Ok guys, I decided to reactivate my GitHub account and report a bug that I had discovered already some time ago - and give some directions on how to fix it.
I don't have a development environment set up anymore though, and won't go through the effort of fixing this myself and submitting a pull request, etc., so it's up to whatever developer wants to take it from here.

The bug:

When the dimension blacklist contains entries, the generation of gateways fails.
The same should go for rift clusters, though I haven't checked that.
This seems to go for all 1.12.2 versions, and maybe for other versions too.

The reason for the bug:

The bug is caused by the way that the Arrays.binarySearch method is used in the check for generating rift clusters and gateways. (Not sure where else in the repository it's used, so you might wanna check that.)
The issue is that apparently the developer assumed that this algorithm would return "-1" if it does not find the entry in the array, as it is in some other methods.
That however is not how this method works.
According to https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#binarySearch-int:A-int- the way it DOES work (unless I confused myself and did get this wrong, of course...) is:

If the entry is found, then the algo returns a non-negative number, i.e. the entry's index.
If the entry is NOT found, then it returns a negative number, i.e. (-(insertion point) - 1).
It is NOT however guaranteed that this negative number then is -1!
Also the array must be sorted before the search and must not contain duplicates, or else the results are undefined. From what I've experienced, this also is not done.
As a user you can do that by hand when adjusting the config, so this is not the biggest issue. But of course ideally the blacklists should be sorted via Arrays.sort, and duplicates should be deleted with whatever method exists for that.

Now if the list does contain no entry, then the "insertion point" is 0, so that -(0) - 1 results in -1.
In other words: This result just so happens to fulfill the prerequisite for generating the respective feature! Which is probably why this didn't catch the attention of the developer.

How to fix it quickly:

The basic fix for this issue is to go to org.dimdev.dimdoors.shared.world.gateways.GatewayGenerator and change in line 55 and line 85 the == -1 to < 0, i.e.:

if (Arrays.binarySearch(ModConfig.world.clusterDimBlacklist, world.provider.getDimensionType().getId()) == -1) {

to
if (Arrays.binarySearch(ModConfig.world.clusterDimBlacklist, world.provider.getDimensionType().getId()) < 0) {

and

if (!clusterGenerated && Arrays.binarySearch(ModConfig.world.gatewayDimBlacklist, world.provider.getDimensionType().getId()) == -1) {

to
if (!clusterGenerated && Arrays.binarySearch(ModConfig.world.gatewayDimBlacklist, world.provider.getDimensionType().getId()) < 0) {
respectively.

For a quick and dirty fix the sorting of the blacklist and the avoiding of duplicates could then be left to the user.
As said above, a more thorough fix would of course be preferable, but you could also just put a comment in the config, instructing the user on how to order the dimension IDs.