Auto merge of #39457 - bvinc:master, r=alexcrichton

Dont segfault if btree range is not in order

This is a first attempt to fix issue #33197.  The issue is that the BTree iterator uses next_unchecked for fast iteration, but it can be tricked into running off the end of the tree and segfaulting if range is called with a maximum that is less than the minimum.

Since a user defined Ord should not determine the safety of BTreeMap, and we still want fast iteration, I've implemented the idea of @gereeter and walk the tree simultaneously searching for both keys to make sure that if our keys diverge, the min key is to the left of our max key.  I currently panic if that is not the case.

Open questions:

1.  Do we want to panic in this error case or do we want to return an empty iterator?  The drain API panics if the range is bad, but drain is given a range of index values, while this is a generic key type.  Panicking is brittle and returning an empty iterator is probably the most flexible and matches what people would want it to do... but artificially returning a BTreeMap::Range with start==end seems like a pretty weird and unnatural thing to do, although it's doable since those fields are not accessible.

The same question for other weird cases:
2.  (Included(101), Excluded(100)) on a map that contains [1,2,3].  Both BTree edges end up on the same part of the map, but comparing the keys shows the range is backwards.
3.  (Excluded(5), Excluded(5)).  The keys are equal but BTree edges end up backwards if the map contains 5.
4.  (Included(5), Excluded(5)).  Should naturally produce an empty iterator, right?

0 files changed, 0 insertions, 0 deletions