binary search fails for lists of size 2

[OCsq]

Hi all!
I've been using pyrate-limiter for some weeks now and noticed a small bug (see below).

The reason for the bug seems to be that the binary_search function in utils fails when:

• the length of the list of RateItems is 2 AND
• the 'value' argument is > items[0].timestamp and <= items[-1].timestamp
  In this case it returns 0 when it should return 1.

For instance it fails when len(items) = 2, items[0].timestamp = 2, items[1].timestamp = 4 and value = 3: it return 0 while it should return 1.

There is an easy fix for this problem: just add

if len(items)==2:
    return 1

after line 24 of utils.py (so just before defining left_pointer, right_pointer and mid).
Then everything works again.

The bug that was caused by this error is that sometimes BucketFullExceptions are raised even when max_delay is not None in cases where Limiter.limit =2.

For instance the following code raises this issue:

from pyrate_limiter import Rate, Duration, Limiter
from time import sleep
mylimiter = Limiter( Rate(2,Duration.SECOND * 10), max_delay = Duration.SECOND * 100)
for i in range(10):
    mylimiter.try_acquire('foo')
    sleep(1)

What happens here is that after the first two items have been put into the (single) bucket, the third item doesn't fit. After waiting the calculated time (a bit less than 8 s + 50 ms), the program retries to put the item into the bucket. It then checks how many items are still in the bucket by using binary_search. However: there are still 2 items and even though one of them has a timestamp that is 'too old' and the binary_search function should return 1, it returns 0. This causes the retry to fail and a BucketFullException is raised (together with a logging.error stating that the bucket or clock might be unstable).
The sleep in between is necessary to cause the problem, because otherwise both items in the bucket are too old to be in the bucket (because of the 50 ms buffer) and binary_search correctly returns -1 in that case, emptying the bucket.

I know now that everything works as long as limit is not set to 2, but it would still be great if this small bug could be fixed.
Thanks!

[vutran1710]

Tks! Ill make it happen!

[OCsq]

Great, thanks!