D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 17314 - BinaryHeap crashes upon insertion if heapified with an array of length 1
Summary: BinaryHeap crashes upon insertion if heapified with an array of length 1
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P1 normal
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2017-04-09 12:42 UTC by kirsybuu
Modified: 2018-01-05 13:28 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description kirsybuu 2017-04-09 12:42:41 UTC
Bug report for: https://forum.dlang.org/post/cavtukhpddgoilredilk@forum.dlang.org

This code throws a Range violation:

import std.stdio, std.container;
void main() {
  auto pq = heapify([5]);
  pq.insert(8);
}

because the insert method fails to increases length in the case of length == 1:

static if (isDynamicArray!Store)
{
    if (_store.length == 0)
        _store.length = 8;
    else if (length == _store.length)
        _store.length = length * 3 / 2; // problem: 1 * 3 / 2 = 3 / 2 = 1
    _store[_length] = value; // out-of-bounds!
}
Comment 1 github-bugzilla 2017-04-11 20:14:01 UTC
Commits pushed to master at https://github.com/dlang/phobos

https://github.com/dlang/phobos/commit/0912b243026e733db3b18c2c650d1809e5cb52dc
fix issue 17314

https://github.com/dlang/phobos/commit/ef9f4b9fee9277dfb0ad049a1806579eeaaa2042
fix issue 17314

https://github.com/dlang/phobos/commit/3b5ab7bec230b0d15d4fbd233323997291039040
Merge pull request #5329 from kirsybuu/issue_17314

Fix Issue 17314 - BinaryHeap crashes upon insertion if heapified with an array of length 1
merged-on-behalf-of: Steven Schveighoffer <schveiguy@users.noreply.github.com>