Skip to content
This repository was archived by the owner on Jan 31, 2020. It is now read-only.

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

Merged

Conversation

piowin
Copy link
Contributor

@piowin piowin commented May 20, 2016

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.

piowin added 3 commits May 20, 2016 16:17
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
Copy link

Can you add tests?

@weierophinney
Copy link
Member

@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!

*/
protected $maxPriority = 0;
protected $maxPriority = null;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Possibly a BC break, since FastPriorityQueue is not final

@weierophinney weierophinney merged commit 5f4b887 into zendframework:master Apr 12, 2018
weierophinney added a commit that referenced this pull request Apr 12, 2018
\Zend\Stdlib\FastPriorityQueue - an infinite loop and bugs in remove()
weierophinney added a commit that referenced this pull request Apr 12, 2018
weierophinney added a commit that referenced this pull request Apr 12, 2018
@weierophinney
Copy link
Member

Thanks, @Peterr!

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants