\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove()

piowin · 2016-05-20T18:39:23Z

I see a few problems in the class.

An infinite loop:

$queue = new FastPriorityQueue();
$queue->insert('a', 0);
$queue->insert('b', 1);
foreach ($queue as $value) {echo $value;} // here we fall into an infinite loop

Other problems are concerned with the implementation of the remove() method.

remove() changes a value of this->maxPriority:

$queue = new FastPriorityQueue();
$queue->insert('a1', 1);
$queue->insert('a2', 1);
$queue->insert('b2', 2);
$queue->remove('a1');
echo $queue->extract(); // it prints 'a2' but should 'b2'

remove() uses the next() method thus it changes the internal array pointer:

$queue = new FastPriorityQueue();
$queue->insert('a1', 1);
$queue->insert('a2', 1);
$queue->insert('a3', 1);
$queue->remove('a2');
echo $queue->extract(); // it prints 'a3' but should 'a1', 'a1' is lost

remove() doesn't destroy the unnecessary priority from the array of priorities which implies the following behaviour:

$queue = new FastPriorityQueue();
$queue->insert('a', 1);
$queue->insert('b', 2);
$queue->remove('b');
echo $queue->extract(); // it prints an empty string but should 'a'
echo $queue->count();   // it prints 0, but there is still one element in the queue
echo $queue->extract(); // it prints 'a' which should happen when the `extract()` method was called the first time

This PR fixes all these issues.

Inserting elements at 0 priority causes an infinite loop. For example, when we run the following snippet of code, we fall into an infinite loop: ```php $queue = new FastPriorityQueue(); $queue->insert('a', 0); $queue->insert('b', 1); foreach ($queue as $value) {echo $value;} ```

This commmit fixes the implementaion of the `\Zend\Stdlib\FastPriorityQueue::remove()` method.

vaclavvanik · 2016-05-21T06:00:37Z

Can you add tests?

weierophinney · 2016-09-13T14:15:01Z

@Peterr As noted by @vaclavvanik , we need tests demonstrating the infinite loop, so we can validate the fix, but also to ensure that the issue is not re-introduced.

Thanks in advance!

Ocramius · 2016-09-14T23:41:07Z

src/FastPriorityQueue.php

     */
-    protected $maxPriority = 0;
+    protected $maxPriority = null;


Possibly a BC break, since FastPriorityQueue is not final

\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove()

Close #60

weierophinney · 2018-04-12T15:57:58Z

Thanks, @Peterr!

piowin added 3 commits May 20, 2016 16:17

Fix remove()

f8a6f77

This commmit fixes the implementaion of the `\Zend\Stdlib\FastPriorityQueue::remove()` method.

fix whitespaces

06646f5

weierophinney added bug awaiting author updates labels Sep 13, 2016

piowin added 4 commits September 15, 2016 00:38

Tests

82ac5f0

Fix Tests

13e93b0

Fix Tests

7073822

Fix issue with Coding Standards in FastPriorityQueue

5f4b887

Ocramius reviewed Sep 14, 2016

View reviewed changes

weierophinney merged commit 5f4b887 into zendframework:master Apr 12, 2018

weierophinney added a commit that referenced this pull request Apr 12, 2018

Merge pull request #60 from peterr/fix/infinite-loop-and-remove-method

ad899a6

\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove()

weierophinney added a commit that referenced this pull request Apr 12, 2018

Added CHANGELOG entries for #60

e392d54

weierophinney added a commit that referenced this pull request Apr 12, 2018

Merge branch 'hotfix/60'

0a3a158

Close #60

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove() #60

\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove() #60

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove() #60

\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove() #60

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!