choco-solver icon indicating copy to clipboard operation
choco-solver copied to clipboard

[BUG] OneWord*SBitSet.nextClearBit() is incorrect + safety issue

Open fhermeni opened this issue 2 years ago • 1 comments

The following snippet illustrates 2/3 issues with choco 4.10.8:

        final IEnvironment env = new EnvironmentTrailing();
        final IStateBitSet b64 = new OneWordS64BitSet(env, 12);
        final IStateBitSet b32 = new OneWordS32BitSet(env, 1);
        final IStateBitSet b = new S64BitSet(env, 1);
        b.set(63);
        b64.set(63);
        System.out.printf("nextClear(63): b64=%d, b=%d%n", b64.nextClearBit(63), b.nextClearBit(63));
        b32.set(31);
        System.out.printf("b32.nextClear(31): %d%n", b32.nextClearBit(31));
        b.clear();
        b64.clear();
        b32.clear();
        // Write outside the word length, I expect an error or at minimum no change.
        b32.set(32);
        b64.set(64);
        System.out.printf("b32: %s, b64: %s%n", b32, b64);
  1. nextClearBit() is incorrect when the highest bit is set. size() should be returned. The issue is clear when we compare the output between OneWord64 and S64BitSet.
  2. There are no guardrails to prevent from manipulating bits outside the word length. This may be for performance reasons but this is dangerous as other bits are set. In terms of consistency, there is a check for a negative value, accordingly an additional one wrt. the word length may be helpful as well.
  3. (Nit): the nBits argument in the constructor for OneWord*BitSet is useless.

fhermeni avatar Sep 08 '22 06:09 fhermeni

Hello One additional point:

        b64 = new OneWordS64BitSet(env, 12);
        b32 = new OneWordS32BitSet(env, 1);
        b32.set(3);
        b64.set(3);
        System.out.printf("b32:%s b64:%s equals:%s", b32, b64, b32.equals(b64));

equals() are implementation specific so despite the content may be the same wrt. the interface specification, the practical implementation impacts the result. Given users are likely to create them from an IEnvironment, the implementation is hidden which may lead to bugs in case equals() is required.

In theory, equals() should be robust against the interface implementation

fhermeni avatar Sep 08 '22 14:09 fhermeni