This is an automated email from the ASF dual-hosted git repository.
dcapwell pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
The following commit(s) were added to refs/heads/trunk by this push:
new 29270f5b Fixed LargeBitSet and SmallBitSet to have the same semantics
with inbound and out of bound inputs. This was detected first by Cassandras
SimpleBitSetSerializersTest#any test (#264)
29270f5b is described below
commit 29270f5b3460fa6eb23b97abe93363ddf6c54bee
Author: dcapwell <[email protected]>
AuthorDate: Wed Jan 7 12:36:24 2026 -0800
Fixed LargeBitSet and SmallBitSet to have the same semantics with inbound
and out of bound inputs. This was detected first by Cassandras
SimpleBitSetSerializersTest#any test (#264)
patch by David Capwell; reviewed by Benedict Elliott Smith for
CASSANDRA-21077
---
.../main/java/accord/utils/ImmutableBitSet.java | 2 +-
.../src/main/java/accord/utils/LargeBitSet.java | 37 +++++---
.../src/main/java/accord/utils/SimpleBitSet.java | 2 +-
.../src/main/java/accord/utils/SmallBitSet.java | 37 +++++++-
.../test/java/accord/utils/SimpleBitSetTest.java | 102 ++++++++++++++++++++-
5 files changed, 161 insertions(+), 19 deletions(-)
diff --git a/accord-core/src/main/java/accord/utils/ImmutableBitSet.java
b/accord-core/src/main/java/accord/utils/ImmutableBitSet.java
index bdc4a3f4..0a9e4598 100644
--- a/accord-core/src/main/java/accord/utils/ImmutableBitSet.java
+++ b/accord-core/src/main/java/accord/utils/ImmutableBitSet.java
@@ -67,7 +67,7 @@ public class ImmutableBitSet extends LargeBitSet
}
@Override
- public void setRange(int from, int to)
+ public void setRange(int fromInclusive, int toExclusive)
{
throw new UnsupportedOperationException();
}
diff --git a/accord-core/src/main/java/accord/utils/LargeBitSet.java
b/accord-core/src/main/java/accord/utils/LargeBitSet.java
index fbeae5bf..60a07438 100644
--- a/accord-core/src/main/java/accord/utils/LargeBitSet.java
+++ b/accord-core/src/main/java/accord/utils/LargeBitSet.java
@@ -87,6 +87,7 @@ public class LargeBitSet implements SimpleBitSet
Arrays.fill(bits, 0, length, 0L);
}
+ @Override
public boolean set(int i)
{
int index = indexOf(i);
@@ -98,36 +99,38 @@ public class LargeBitSet implements SimpleBitSet
return true;
}
- public void setRange(int from, int to)
+ @Override
+ public void setRange(int fromInclusive, int toExclusive)
{
- Invariants.requireArgument(from <= to, "from > to (%s > %s)", from,
to);
- if (from == to)
+ int fromIndex = indexOf(fromInclusive); // validates input so call
early
+ validateExclusive(toExclusive);
+ Invariants.requireArgument(fromInclusive <= toExclusive, "from > to
(%s > %s)", fromInclusive, toExclusive);
+ if (fromInclusive == toExclusive)
return;
- int fromIndex = from >>> 6;
- int toIndex = (to + 63) >>> 6;
+ int toIndex = (toExclusive + 63) >>> 6;
if (fromIndex + 1 == toIndex)
{
- long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ long addBits = (-1L >>> (64 - (toExclusive & 63))) & (-1L <<
(fromInclusive & 63));
orBitsAtIndex(fromIndex, addBits);
}
else if (count == 0)
{
- bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ bits[toIndex - 1] = -1L >>> (64 - (toExclusive & 63));
for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
bits[i] = -1L;
- bits[fromIndex] = -1L << (from & 63);
- count = to - from;
+ bits[fromIndex] = -1L << (fromInclusive & 63);
+ count = toExclusive - fromInclusive;
}
else
{
- orBitsAtIndex(fromIndex, -1L << (from & 63));
+ orBitsAtIndex(fromIndex, -1L << (fromInclusive & 63));
for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
{
count += 64 - Long.bitCount(bits[i]);
bits[i] = -1L;
}
- orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (toExclusive & 63)));
}
}
@@ -163,6 +166,7 @@ public class LargeBitSet implements SimpleBitSet
count += Long.bitCount(nextBits) - Long.bitCount(prevBits);
}
+ @Override
public boolean unset(int i)
{
int index = indexOf(i);
@@ -174,6 +178,7 @@ public class LargeBitSet implements SimpleBitSet
return true;
}
+ @Override
public final boolean get(int i)
{
int index = indexOf(i);
@@ -320,7 +325,7 @@ public class LargeBitSet implements SimpleBitSet
private int nextSetBitInternal(int i, int exclIndexBound, int ifNotFound)
{
Invariants.requireArgument(i >= 0);
- Invariants.requireArgument(i <= size());
+ validateExclusive(i);
if (count == 0)
return ifNotFound;
@@ -443,10 +448,16 @@ public class LargeBitSet implements SimpleBitSet
{
int index = i >>> 6;
if (index >= length)
- throw new IndexOutOfBoundsException(String.format("%d >= %d",
index, length));
+ throw new IndexOutOfBoundsException(String.format("Unable to
access bit %d; must be between 0 and %d", i, size() - 1));
return index;
}
+ private void validateExclusive(int i)
+ {
+ if (i > size())
+ throw new IndexOutOfBoundsException(String.format("Unable to
access bit %d; must be between 0 and %d", i, size()));
+ }
+
private int lowerLimitOf(int i)
{
return i >>> 6;
diff --git a/accord-core/src/main/java/accord/utils/SimpleBitSet.java
b/accord-core/src/main/java/accord/utils/SimpleBitSet.java
index 4380e3c8..695ca935 100644
--- a/accord-core/src/main/java/accord/utils/SimpleBitSet.java
+++ b/accord-core/src/main/java/accord/utils/SimpleBitSet.java
@@ -22,7 +22,7 @@ public interface SimpleBitSet
{
boolean get(int i);
boolean set(int i);
- void setRange(int from, int to);
+ void setRange(int fromInclusive, int toExclusive);
boolean unset(int i);
void clear();
boolean isEmpty();
diff --git a/accord-core/src/main/java/accord/utils/SmallBitSet.java
b/accord-core/src/main/java/accord/utils/SmallBitSet.java
index 2deb43b3..e4cdeb64 100644
--- a/accord-core/src/main/java/accord/utils/SmallBitSet.java
+++ b/accord-core/src/main/java/accord/utils/SmallBitSet.java
@@ -18,7 +18,6 @@
package accord.utils;
-import static accord.utils.LargeBitSet.bit;
import static accord.utils.LargeBitSet.bitsEqualOrGreater;
import static java.lang.Long.numberOfTrailingZeros;
@@ -40,6 +39,25 @@ public class SmallBitSet implements SimpleBitSet
return bits;
}
+ private static long bit(int i)
+ {
+ validateInclusive(i);
+ return 1L << i;
+ }
+
+ private static void validateInclusive(int i)
+ {
+ if (i >>> 6 > 0) // i >= 64 || i < 0
+ throw new IndexOutOfBoundsException("Unable to access bit " + i +
"; must be between 0 and 63");
+ }
+
+ private static void validateExclusive(int i)
+ {
+ if (i >= 65 || i < 0)
+ throw new IndexOutOfBoundsException("Unable to access bit " + i +
"; must be between 0 and 64");
+ }
+
+ @Override
public boolean set(int i)
{
long bit = bit(i);
@@ -49,17 +67,25 @@ public class SmallBitSet implements SimpleBitSet
}
@Override
- public void setRange(int from, int to)
+ public void setRange(int fromInclusive, int toExclusive)
{
- bits |= ~(-1L << to) & (-1L << from);
+ validateInclusive(fromInclusive);
+ validateExclusive(toExclusive);
+ Invariants.requireArgument(fromInclusive <= toExclusive, "from > to
(%s > %s)", fromInclusive, toExclusive);
+ if (fromInclusive == toExclusive)
+ return;
+
+ bits |= (-1L >>> (64 - (toExclusive & 63))) & (-1L << (fromInclusive &
63));
}
+ @Override
public boolean get(int i)
{
long bit = bit(i);
return 0 != (bits & bit);
}
+ @Override
public boolean unset(int i)
{
long bit = bit(i);
@@ -83,6 +109,11 @@ public class SmallBitSet implements SimpleBitSet
@Override
public int nextSetBit(int fromIndex)
{
+ if (fromIndex >= 64)
+ {
+ validateExclusive(fromIndex);
+ return -1;
+ }
long bits = this.bits & bitsEqualOrGreater(fromIndex);
if (bits == 0)
return -1;
diff --git a/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
b/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
index 96deea32..69976ad5 100644
--- a/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
+++ b/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
@@ -20,6 +20,8 @@ package accord.utils;
import java.util.BitSet;
+import java.util.List;
+import java.util.function.Consumer;
import org.junit.jupiter.api.Test;
@@ -42,6 +44,21 @@ class SimpleBitSetTest
return new Property.SimpleCommand<>("Set(" + idx + ')', s2 ->
s2.set(idx));
}
+ private static Property.Command<State, Void, ?> setRange(RandomSource rs,
State state)
+ {
+ int from = rs.nextInt(0, state.size);
+ int to = rs.nextInt(0, state.size + 1); // do not filter from == to as
this "must" no-op
+ if (from > to)
+ {
+ int tmp = from;
+ from = to;
+ to = tmp;
+ }
+ int finalFrom = from;
+ int finalTo = to;
+ return new Property.SimpleCommand<>("setRange(" + from + ", " + to +
')', s2 -> s2.setRange(finalFrom, finalTo));
+ }
+
private static Property.Command<State, Void, ?> unset(RandomSource rs,
State state)
{
int idx = rs.nextInt(0, state.size);
@@ -64,19 +81,81 @@ class SimpleBitSetTest
return new Property.SimpleCommand<>("NextSetBit(" + idx + ')', s2 ->
s2.nextSetBit(idx));
}
+ private static Property.Command<State, Void, ?>
getSetBitCount(RandomSource rs, State state)
+ {
+ return new Property.SimpleCommand<>("getSetBitCount()", s2 ->
s2.getSetBitCount());
+ }
+
@Test
public void test()
{
stateful().withExamples(1000).check(commands(() -> State::new)
.add(SimpleBitSetTest::get)
.add(SimpleBitSetTest::set)
+ .add(SimpleBitSetTest::setRange)
.add(SimpleBitSetTest::unset)
.add(SimpleBitSetTest::clear)
.add(SimpleBitSetTest::isEmpty)
.add(SimpleBitSetTest::nextSetBit)
+
.add(SimpleBitSetTest::getSetBitCount)
.build());
}
+ @Test
+ public void outOfRange()
+ {
+ SmallBitSet model = new SmallBitSet();
+ LargeBitSet target = new LargeBitSet(64);
+
+ for (var set : List.of(model, target))
+ set.setRange(0, 64);
+
+ // get methods do not reject, but return false or -1
+
Assertions.assertThat(target.getSetBitCount()).isEqualTo(model.getSetBitCount());
+ Assertions.assertThat(target.isEmpty()).isEqualTo(model.isEmpty());
+
+ Assertions.assertThat(target.nextSetBit(64))
+ .describedAs("nextSetBit(%s)", 64)
+ .isEqualTo(model.nextSetBit(64))
+ .isEqualTo(-1);
+
+ // set methods reject
+ for (int index : new int[] {64, 65, Integer.MAX_VALUE})
+ {
+ asertThrownSameWay(model, target, bs -> bs.get(index));
+ asertThrownSameWay(model, target, bs -> bs.set(index));
+ asertThrownSameWay(model, target, bs -> bs.setRange(index, 100));
// from/index gets rejected
+ asertThrownSameWay(model, target, bs -> bs.setRange(0, 100));
// to gets rejected
+ asertThrownSameWay(model, target, bs -> bs.unset(index));
+
+ if (index > 64)
+ asertThrownSameWay(model, target, bs -> bs.nextSetBit(index));
+ }
+
+ asertThrownSameWay(model, target, bs -> bs.setRange(1, 0));
+ }
+
+ private static void asertThrownSameWay(SimpleBitSet model, SimpleBitSet
target, Consumer<SimpleBitSet> fn)
+ {
+ Throwable expected = assertThrown(() -> fn.accept(target));
+ Throwable actual = assertThrown(() -> fn.accept(model));
+
+
Assertions.assertThat(actual).hasSameClassAs(expected).hasMessage(expected.getMessage());
+ }
+
+ private static Throwable assertThrown(Runnable fn)
+ {
+ try
+ {
+ fn.run();
+ }
+ catch (Throwable t)
+ {
+ return t;
+ }
+ throw new AssertionError("Expected logic to throw but did not");
+ }
+
private static class State implements SimpleBitSet
{
private final BitSet model;
@@ -114,7 +193,10 @@ class SimpleBitSetTest
@Override
public void setRange(int from, int to)
{
- throw new UnsupportedOperationException();
+ model.set(from, to);
+ sut.setRange(from, to);
+
+ getSetBitCount();
}
@Override
@@ -167,9 +249,27 @@ class SimpleBitSetTest
@Override
public int getSetBitCount()
{
+ Assertions.assertThat(sut.getSetBitCount())
+ .describedAs(toBinaryString())
+ .isEqualTo(model.cardinality());
return sut.getSetBitCount();
}
+ public String toBinaryString()
+ {
+ StringBuilder sb = new StringBuilder();
+ for (int i = 0; i < size; i++)
+ {
+ boolean m = model.get(i);
+ boolean s = sut.get(i);
+ if (m == s)
+ sb.append(m ? 1 : 0);
+ else
+ sb.append("(expected=").append(m ? 1 : 0).append(",
actual=").append(s ? 1 : 0).append(')');
+ }
+ return sb.toString();
+ }
+
@Override
public String toString()
{
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
