Bug: Arbitraries.strings().uniqueChars() will sometimes shrink to values with duplicate chars

[mattiacolucci]

Hi, I am using a Provide metod to generate some data like a random string withCharsRange and with no duplicates (using uniqueChars). The problem is that if I put an always true assert in the thest method (like an assertTrue(true)) the data generated is correct and the string "iniial String" doesn't present any duplicate char. But If I use the assertEquals(expected,actual) that I will use to test my method, jqwik generate a string that presents duplicates. In details, going on with the number of the test genrated, the string will contain more chars duplicated, expecially the first char of the range specified into the Arbitrary withCharsRange.

Here is the code:

   @Property
    @Report(Reporting.GENERATED)
    void testMethod(@ForAll("provideMethod") Homework2Object obj){
        String initialString= obj.getInitialString();
        int subStringLength=obj.getSubStringLength();
        Map<String,Integer> palindrome=new HashMap<>(obj.getPalindromeToPut());

        String finalstring="";
        Map<String,Integer> expectedResult=new HashMap<>();

        System.out.println("initial string="+initialString);
        System.out.println("Length="+subStringLength);
        System.out.println("Palindrome="+palindrome.toString());

        int currIndex=0;
        int step=(subStringLength>5)?subStringLength-5:subStringLength;
        boolean firstPalindroma=subStringLength > 5;

        for(String key:palindrome.keySet()){
            String keyReverse=String.valueOf(new StringBuilder(key).reverse());
            expectedResult.put(key+keyReverse,palindrome.get(key));
            for(int i=0;i<palindrome.get(key);i++) {
                if(firstPalindroma){
                    finalstring=finalstring.concat(initialString.substring(currIndex,currIndex+step)+key+keyReverse);
                }else{
                    finalstring=finalstring.concat(key+keyReverse+initialString.substring(currIndex,currIndex+step));
                }
                currIndex+=step;
            }
        }

        System.out.println("FINAL STRING = "+finalstring);

        Map<String,Integer> result=Homework2.howManyTimesIsPalindrome(finalstring,subStringLength);

        //assertTrue(true);
        assertEquals(expectedResult, result);
    }

    @Provide
    Arbitrary<Homework2Object> provideMethod(){
        Arbitrary<String> initialString= Arbitraries.strings().withCharRange('A', 'Z').ofMaxLength(50).ofMinLength(10).uniqueChars();

        Arbitrary<Integer> subStringLength=Arbitraries.integers().between(1,10).filter(e->(e%2)==0);

        MapArbitrary<String, Integer> mapOfPalindrome=Arbitraries.maps(
                Arbitraries.strings().withCharRange('a','z').ofMaxLength(5),
                Arbitraries.integers().between(1,3)
        ).ofSize(3);

        return Combinators.combine(initialString,subStringLength,mapOfPalindrome).as(Homework2Object::new).filter(o->checkStringsLength(o.palindromeToPut,o.subStringLength/2));

    }

    private boolean checkStringsLength(Map<String,Integer> palindrome,Integer len){
        boolean res=true;
        for(String key:palindrome.keySet()){
            if(key.length()!=len)
                return false;
        }
        return res;
    } 

The output with the assert(expected,actual) is the following:

initial string=!!!!!!!!!!!!!!!!!!!!!@*AGU?V(T$#ZW5&PJ/,0XN3O;"L!Y
Length=10
Palindrome={tnpgf=3, tayvv=1, jujar=2}
FINAL STRING = !!!!!tnpgffgpnt!!!!!tnpgffgpnt!!!!!tnpgffgpnt!!!!!tayvvvvyat!@*AGjujarrajujU?V(Tjujarrajuj

initial string=!!!!!!!!!!!!!!!!!!!!!!*AGU?V(T$#ZW5&PJ/,0XN3O;"L!Y
Length=10
Palindrome={tnpgf=3, tayvv=1, jujar=2}
FINAL STRING = !!!!!tnpgffgpnt!!!!!tnpgffgpnt!!!!!tnpgffgpnt!!!!!tayvvvvyat!!*AGjujarrajujU?V(Tjujarrajuj
initial string=!!!!!!!!!!!!!!!!!!!!!!!AGU?V(T$#ZW5&PJ/,0XN3O;"L!Y
Length=10
Palindrome={tnpgf=3, tayvv=1, jujar=2}
FINAL STRING = !!!!!tnpgffgpnt!!!!!tnpgffgpnt!!!!!tnpgffgpnt!!!!!tayvvvvyat!!!AGjujarrajujU?V(Tjujarrajuj

and so on....

[jlink]

@mattiacolucci Without your implementation of Homework2Object I cannot really check what's happening here. So you may want to provide it. Or, even better, reduce the example to the bare bones, ie remove everything that's not necessary for reproducing the phenomenon.

[mattiacolucci]

The code of the class is the following:

    class Homework2Object{
        private String initialString;
        private int subStringLength;
        private Map<String,Integer> palindromeToPut;

        public Homework2Object(String i, int l, Map<String,Integer> p){
            initialString=i;
            subStringLength=l;
            palindromeToPut=p;
        }

        public String getInitialString() {
            return initialString;
        }

        public int getSubStringLength() {
            return subStringLength;
        }

        public Map<String,Integer> getPalindromeToPut() {
            return palindromeToPut;
        }
    }

It's basically a class just to generate different types of data: an initilString, a random int and a map of integers and random strings as keys

[jlink]

@mattiacolucci The problem you are observing is not a generation problem but a shrinking bug. Thanks for catching and reporting it!

What I noticed, though, is that this line:

finalstring=finalstring.concat(initialString.substring(currIndex,currIndex+step)+key+keyReverse);

will sometimes fail with a StringIndexOutOfBoundsException which then leads to shrinking and revealing the bug.

I suggest that I will work on the shrinking bug - and you on the failing tests logic ;-)

[jlink]

Fixed in https://github.com/jqwik-team/jqwik/commit/c779a9d7d4ab94b04708e32b1a995e2d73ae33a7

[jlink]

Released in 1.8.3-SNAPSHOT

@mattiacolucci If you want you can try your example with the snapshot release