Maybe improve shrinking algorithm?

[waterlink]

For integer/float values it is possible to do shrinking not by 1, but using kind of binary search:

1. initialize step = 1
2. change value by step, is property still failing with new value?
   • yes: multiply step by 2;
   • no: divide step by 2;
3. is step == 0?
   • yes: return last seen failing value
   • no: go to step 2

For arrays, currently last element is removed if it is shrinked to its "zero" value (0, "", etc.). This is not the most useful strategy, since usually properties on arrays verify relationship between different elements. That means that if some relation is failing between only 3 items, potentially all but these 3 items can be safely removed, so the algorithm for this is:

1. new_value = []
2. head = current_value.shift
3. if property with current_value still failing?
   • no: append head to new_value
4. if current_value is empty?
   • yes: return new_value
   • no: go to step 2

This algorithm works really well, it is very fast and still allows for individual shrinking for each element after it is done.

---

@abargnesi So what do you think? I could implement these (or one of these) over this weekend.

[abargnesi]

@waterlink Great ideas here. Thanks for taking the time to explain in pseudo code.

👍 for your binary search approach to shrinking Numeric ruby classes. With the Array algorithm it was unclear (to me) when an element shrinks.

[waterlink]

About the Array, I can provide you a simple example:

Lets assume, we are writing a sorting algorithm of some kind, it is still incomplete and incorrect, but returns some valid array, not necessary ordered. And the next property we want to write is the one, that would check the order:

property_of do
  # get random array here
end.check do |array|
  expect(ordered?(array)).to eq(true)
end

Lets assume, that generated array looked like [71, 15, 17, .. lots of items .., 98, 54, 42].

Lets assume, that our incorrect algorithm has returned everything sorted properly, except pair of 71 and 98 is out of order.

Current shrinking algorithm will remove only 2 last elements, and shrink 98 to 72. That happens, because current shrinking strategy for arrays, tries to shrink last element, and if it shrunk to 0, it removes it. It proceeds doing so, until next element didn't shrink to 0.

Proposed algorithm will try to run property without each element one by one. If removing element k causes property to stop failing, this element will stay in the final shrinked array, all other elements will be removed.

Only when all elements, that being removed do not turn property into successful one, are removed, then algorithm will proceed and try to shrink individual elements. In this case it will try to shrink every element that has survived removal.

This algorithm (depending on our incorrect sort implementation) can remove everything except key elements that cause problem: [71, 98] in one swoop.

[waterlink]

Shrink guessing order will look like that:

value: [71, 15, 17, 19, 42, 98, 54, 42]
property: ordered? [15, 17, 19, 42, 42, 54, 98, 71] == false

guess: remove 71
value: [15, 17, 19, 42, 98, 54, 42]
property: ordered? [15, 17, 19, 42, 42, 54, 98] == true
result: invalid guess, property will not fail

guess: remove 15
value: [71, 17, 19, 42, 98, 54, 42]
property: ordered? [17, 19, 42, 42, 54, 98, 71] == false
result: valid guess, property still fails
apply guess!

# .. the same for 17, 19, 42 ..

guess: remove 98
value: [71, 54, 42]
property: ordered? [42, 54, 71] == true
result: invalid guess, property will not fail

guess: remove 54
value: [71, 98, 42]
property: ordered? [42, 98, 71] == false
result: valid guess, property still fails
apply guess!

# .. same for 42 ..

Out of items to remove
Shrinked array is: [71, 98]

return shrinked_array.map { |item| item.try_to_shrink }

[waterlink]

Updated last comment with actual values.