belliottsmith commented on code in PR #50: URL: https://github.com/apache/cassandra-accord/pull/50#discussion_r1262256698
########## accord-core/src/test/java/accord/utils/SimpleBitSetTest.java: ########## @@ -0,0 +1,203 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package accord.utils; + +import java.util.ArrayList; +import java.util.BitSet; +import java.util.List; +import java.util.Random; +import java.util.function.BiConsumer; +import java.util.function.IntConsumer; + +import com.google.common.collect.Lists; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; + +public class SimpleBitSetTest +{ + private static final int NOT_FOUND = Integer.MAX_VALUE; + + private static class Check + { + final SimpleBitSet test; + final BitSet canon; + final int size; + + private Check(SimpleBitSet test, BitSet canon, int size) + { + this.test = test; + this.canon = canon; + this.size = size; + } + + void check(Random random) + { + assertEquals(canon.cardinality(), test.setBitCount()); + assertEquals(canon.nextSetBit(0), test.firstSetBit()); + assertEquals(normaliseNotFound(canon.nextSetBit(0)), test.firstSetBit(NOT_FOUND)); + assertEquals(canon.previousSetBit(size), test.lastSetBit()); + assertEquals(normaliseNotFound(canon.previousSetBit(size)), test.lastSetBit(NOT_FOUND)); + + forIndices(random, i -> assertEquals(canon.nextSetBit(i), test.nextSetBit(i))); + forIndices(random, i -> assertEquals(normaliseBefore(canon.nextSetBit(0), i), test.firstSetBitBefore(i))); + forIndices(random, i -> assertEquals(normaliseNotFoundBefore(canon.nextSetBit(0), i), test.firstSetBitBefore(i, NOT_FOUND))); + forRanges(random, (i, j) -> assertEquals(normaliseBefore(canon.nextSetBit(i), j), test.nextSetBitBefore(i, j))); + forRanges(random, (i, j) -> assertEquals(normaliseNotFoundBefore(canon.nextSetBit(i), j), test.nextSetBitBefore(i, j, NOT_FOUND))); + + forIndices(random, i -> assertEquals(i == 0 ? -1 : canon.previousSetBit(i - 1), test.prevSetBit(i))); + forIndices(random, i -> assertEquals(normaliseNotBefore(size == 0 ? -1 : canon.previousSetBit(size - 1), i), test.lastSetBitNotBefore(i))); + forIndices(random, i -> assertEquals(normaliseNotFoundNotBefore(size == 0 ? -1 : canon.previousSetBit(size - 1), i), test.lastSetBitNotBefore(i, NOT_FOUND))); + forRanges(random, (i, j) -> assertEquals(normaliseNotBefore(j == 0 ? -1 : canon.previousSetBit(j - 1), i), test.prevSetBitNotBefore(j, i))); + forRanges(random, (i, j) -> assertEquals(normaliseNotFoundNotBefore(j == 0 ? -1 : canon.previousSetBit(j - 1), i), test.prevSetBitNotBefore(j, i, NOT_FOUND))); + + List<Integer> canonCollect = new ArrayList<>(), testCollect = new ArrayList<>(); + canon.stream().forEachOrdered(canonCollect::add); + test.forEach(testCollect, List::add); + assertEquals(canonCollect, testCollect); + + canonCollect = Lists.reverse(canonCollect); + testCollect.clear(); + test.reverseForEach(testCollect, List::add); + assertEquals(canonCollect, testCollect); + } + + void forIndices(Random random, IntConsumer consumer) + { + for (int c = 0 ; c < 100 ; ++c) + { + int i = random.nextInt(size + 1); + consumer.accept(i); + } + } + + void forRanges(Random random, BiConsumer<Integer, Integer> consumer) + { + for (int c = 0 ; c < 100 ; ++c) + { + int i = random.nextInt(size + 1); + int j = random.nextInt(size + 1); + if (i > j) { int t = i; i = j; j = t; } + consumer.accept(i, j); + } + } + + static Check generate(Random random, int maxSize, int modCount, int runLength, float runChance, float clearChance) + { + int size = random.nextInt(maxSize); + runLength = Math.min(size, runLength); + BitSet canon = new BitSet(size); + SimpleBitSet test = new SimpleBitSet(size); + if (size > 0) + { + while (modCount-- > 0) + { + boolean set = random.nextFloat() >= clearChance; + boolean run = runLength > 1 && random.nextFloat() < runChance; + if (run) + { + int i = random.nextInt(size); + int j = random.nextInt(size); + if (j < i) { int t = i; i = j; j = t; } + j = Math.min(i + 1 + random.nextInt(runLength - 1), j); + + if (set) + { + canon.set(i, j); + test.setRange(i, j); + } + else + { + canon.clear(i, j); + while (i < j) + test.unset(i++); + } + } + else + { + int i = random.nextInt(size); + if (set) + { + assertEquals(!canon.get(i), test.set(i)); + canon.set(i); + } + else + { + assertEquals(canon.get(i), test.unset(i)); + canon.clear(i); + } + } + assertEquals(canon.cardinality(), test.setBitCount()); + } + } + return new Check(test, canon, size); + } + } + + @Test + public void testRandomBitSets() + { + Random random = new Random(); + long seed = random.nextLong(); + System.err.println("Seed: " + seed); + random.setSeed(seed); + testRandomBitSets(random, 100000); Review Comment: To be clear, I am not a fan either of quick theories itself _or_ the way in which the current abstraction on which it is based encourages tests to be written. My preferred approach is to create some class that pairs some `test` with some `canon`(ical) version, and to randomise the generation and verification of these within the class. There should then ideally be some meta-randomisation around the parameters to each of these phases, particularly the generation phase. I think the `qt` abstraction encourages relatively narrow tests, which does permit for a quicker broader array of unique tests to be written, but the tests themselves tend to each be comparatively narrow, so there is less multiplexing of behaviour. It also seems to make it less natural to express meta-randomisation, though in principle it might be possible to do that _for_ you, this is something that should really be expressed by the test author and any API we encourage should make that a core feature/requirement. I would be in favour of producing some better tools for meta-randomisation, where we want to declare not only the range of values but the ways in which they are randomised (rather than simply uniform over a statically defined range). I'm not sure exactly what that would look like, but this would be the most valuable tooling for improving fuzz testing IMO. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
