Tracking issue for sorted collection ranges

[Gankra]

This covers btree_range and collections_bound. Both try to address the combinatorics over inclusive/exclusive/none bounds on ordered queries. I am significantly unsatisfied with the current solution, which is btree.range(Bound(&K), Bound(&K)). This pushes all the combinatorics into a nasty calling convention. Instead, I believe we would be better served by a build pattern:

for x in btree.range().ge(&min).lt(&max) { .. }

This allows you to avoid importing and dispatching on enum. It also has the advantage of making simpler queries simpler. Compare:

// today (assuming you've totally imported the bound variants)
for x in btree.range(Unbounded, Inclusive(&max)) {

// tomorrow?
for x in btree.range().le(&max) { .. }

This also could potentially address rust-lang/rfcs#1195

let pred = btree.range().le(&max).get();

And can be extended to support drain or remove similarly;

for x in btree.range_mut().gt(&min).drain() { .. }

ler pred = btree.range_mut().le(&max).remove();

Which if desirable can be sugarred to direct methods on btree in the future.

[Gankra]

CC @bluss @apasel422

[apasel422]

Will this still allow for efficient implementations of things like just the
predecessor (without iteration)?

On Wednesday, August 12, 2015, Alexis Beingessner notifications@github.com
wrote:

CC @bluss https://github.com/bluss @apasel422
https://github.com/apasel422

—
Reply to this email directly or view it on GitHub
#27787 (comment).

[Gankra]

@apasel422 Yes the builder is completely lazy -- get would just extract the one set bound and do lt/le/gt/whatever as appropriate.

[Gankra]

I should note the builder API is considerably more hairy internally. Basically requires converting all the static types into dynamic types and then dispatching to the existing impls (for IntoIter) or those proposed in rust-lang/rfcs#1195

[Gankra]

Holy shit it actually works:

• https://play.rust-lang.org/?gist=bfa0493e0e11cbfceda7&version=nightly
• https://gist.github.com/bfa0493e0e11cbfceda7

[Gankra]

Shoutouts to @zentner-kyle for proposing this API. Big improvement.

[Gankra]

In practice, with the parent pointer design I anticipate the guts of BTreeMap having the query API just do raw pointers and be an internal impl detail: get_lt(&BTreeMap, &Q) -> Handle<*mut Node>

A range knows how to compute handles from bounds by dispatching to the query API, and then get or into_iter are just munging up handles into a (K, V) pair or Iter(Handle, Handle).

[Gankra]

@apasel422 does this sound good to you?

[Gankra]

CC @cgaebel @glaebhoerl @jooert

[Gankra]

I have made an RFC to this affect: rust-lang/rfcs#1254

[alexcrichton]

Removing the B-unstable tag as I believe these haven't been implemented.

[Gankra]

@alexcrichton range and range_mut have been around since 1.0, I think. But they won't be stabilized as-is.

[alexcrichton]

Oh oops there are indeed some unstable APIs tagged with this.

[naktinis]

What's the state of this? I'm using btree ranges in production code and would be happy to help as much as I can to stabilize this feature.

[calebmer]

I also would like to know the status as I'm building a program which uses ranges and if there is an idiomatic rust solution I'd love to use that over my own implementation.

[apasel422]

My understanding is that we're waiting on a new RFC in lieu of rust-lang/rfcs#1254.

[naktinis]

How can we contribute to the discussion or at least keep track of the remaining issues?

[apasel422]

@naktinis A pre-RFC or general discussion thread on https://internals.rust-lang.org/ would probably work.

[alexcrichton]

cc #33197, a case where the APIs currently segfault apparently

[ticki]

It seems to me that the extension Bound provides over Range is very small. I wonder why .range() doesn't take Range instead.

[apasel422]

@ticki Range is [start, end), but Bound provides inclusive/exclusive/unbounded on both ends.

[aturon]

Now that the changes to the surface API have landed, I think we're ready to consider stabilization.

@rfcbot rfc merge

[aturon]

Grr:

@rfcbot fcp merge

[rfcbot]

Team member @aturon has proposed to merge this. The next step is review by the rest of the tagged teams:

• @BurntSushi
• @Kimundi
• @alexcrichton
• @aturon
• @brson
• @sfackler

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[alexcrichton]

@aturon, to clarify, what APIs are you thinking of stabilizing as part of this? Just BTreeMap::range{,_mut} or also the RangeArgument trait and associated types?

[aturon]

@alexcrichton I think we should start with just the method for now, and let the trait bake a while longer.

[alexcrichton]

In that case you have my checkmark!

[djzin]

There is a small ergonomic issue I came across while writing tests for this relating to taking a range by borrowed key; say you have a map with strings as keys, then it would be nice to just use range syntax to specify the range. Unfortunately this doesn't work, because you would need a Range<str> which is unsized. Changing the bounds required type annotations in the common case. Instead what I did is implement RangeArgument<T> for (Bound<&T>, Bound<&T>), allowing you to do this, but it still requires type annotations.

#![feature(btree_range)]
#![feature(collections_bound)]

use std::collections::btree_map::BTreeMap;
use std::collections::Bound::*;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("key".to_string(), "value".to_string());
    map.insert("lee".to_string(), "walue".to_string());
    map.insert("me".to_string(), "xalue".to_string());
    // let range = map.range("key".."me"); // doesn't work
    // let range = map.range((Included("key"), Excluded("me"))); // type annotations required
    let range = map.range::<str, _>((Included("key"), Excluded("me"))); // finally
    for (key, value) in range {
        println!("({}, {})", key, value);
    }
}

I suppose this is covered by not stabilizing RangeArgument, though?

[aturon]

@djzin We have to be a bit careful: once the range method is stabilized, we're committing to it working for at least all of the arguments allowed by today's definition of RangeArgument. That is, we can change the definition and impls for RangeArgument but only if all uses of range will continue to work.

[bluss]

I propose that #33197 should be fixed before stabilization (unfortunately), but it's being fixed.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[djzin]

The first issue I listed above (not being able to use range syntax) may be fixed at a later time by adding impls such as

impl<'a, T: ?Sized> RangeArgument<T> for Range<&'a T> {
    fn start(&self) -> Bound<&T> { Included(self.start) }
    fn end(&self) -> Bound<&T> { Excluded(self.end) }
}

Then one may use map.range::<str, _>("a".."z").
A similar impl could be provided for &'a mut T if that were a thing.

For some reason, even though there is only one type that can fit here (as far as I can tell), rust still requires type annotations for the str. This seems to me like improvements in rust's type inference down the line may fix this ergonomic issue.

A related problem occurs with RangeFull aka .. - rust cannot derive the type for a String key. In this case there are multiple options, all with the same result. I feel as though this is a non-issue as selecting the whole range is a no-op.

None of these issues affect BTreeMaps with an i64 key (or any key that has no nontrivial implementation of Borrow), and the main ones are solvable in future backwards-compatibly. So I think, as this feature has been in unstable limbo for so long, it's due its chance to shine in stable rust-land :)

[rfcbot]

The final comment period is now complete.

[Gankra]

!?!? REALLY?

[solson]

@gankro I was shocked too: rust-lang/miri#155 :)

this feature has been stable since ____. Attribute no longer needed is the best warning in rustc.

[cgaebel]

wow

…

On Wed, Mar 29, 2017 at 7:35 PM Scott Olson ***@***.***> wrote: @gankro <https://github.com/Gankro> I was shocked too: ***@***.*** #diff-b4aea3e418ccdb71239b96952d9cddb6L2 <rust-lang/miri@c6a18ce#diff-b4aea3e418ccdb71239b96952d9cddb6L2> :) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#27787 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAH3yVetV_d9Radh_Efyx_wJP4PucsrDks5rqurGgaJpZM4FqpeG> .