3 ms·

Given how general Range is, how does it even implement a len() which has the behavior in the article? (I tried looking into the documentation for this and came

by saurik 6y ago

Given how general Range is, how does it even implement a len() which has the behavior in the article? (I tried looking into the documentation for this and came up short on Ranges even having len; I see it provides a TrustedLen to other things via a trait, but that seems unrelated, and it has some len related to an overload of one specific iterative type, but I feel like I must have misunderstood it.) Either it assumes subtraction, which should discover the negative length, or it would have to iterate the distance, which would take a ridiculous amount of work to get from 5 to 0. How is len() there at all, much less able to return 0 for 5...0? (FWIW, in my libraries like this, I have a different type for things that have a start/end for iteration from things which have a start/length for indexing, as they are often extremely different concepts and are used for different purposes, even if it feels like the former is a conceptual superset of the latter.)

ratww 6y ago
Range implements the ExactSizedIterator trait, and this is why you can call `(0..5).len()`. When you call len() the ExactSizeIterator just calls size_hint [1]. The size_hint is implemented here [2]. This is where the "start < end" check happens. [1] https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs.html#71-134 https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs... [2] https://doc.rust-lang.org/src/core/iter/range.rs.html#500-552 https://doc.rust-lang.org/src/core/iter/range.rs.html#500-55...
MaulingMonkey 6y ago
> Given how general Range is, how does it even implement a len() which has the behavior in the article? len() is hidden in ExactSizeIterator, which is implemented for a bunch of Range specializations: https://doc.rust-lang.org/std/ops/struct.Range.html#impl-ExactSizeIterator https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Exa... Expanding the docs node and following the [src] link for len, we can see it's using ExactSizeIterator's default implementation, which invokes size_hint: https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs.html#99-107 https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs... ExactSizeIterator only requires Iterator: https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs.html#71 https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs... And sure enough, that's where size_hint is implemented in Range: https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Iterator https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Ite... -> https://doc.rust-lang.org/src/core/iter/range.rs.html#515-522 https://doc.rust-lang.org/src/core/iter/range.rs.html#515-52... Which in turn relies on steps_between, which is implemented via macro for various integer types: https://doc.rust-lang.org/src/core/iter/range.rs.html#240-247 https://doc.rust-lang.org/src/core/iter/range.rs.html#240-24... https://doc.rust-lang.org/src/core/iter/range.rs.html#360-372 https://doc.rust-lang.org/src/core/iter/range.rs.html#360-37... https://doc.rust-lang.org/src/core/iter/range.rs.html#388-404 https://doc.rust-lang.org/src/core/iter/range.rs.html#388-40...
dathinab 6y ago
> how does it even implement a len() which has the behavior in the article? It's from `ExactSizedIterator.len()` and is a specialization of the case where `Iterator.size_hint()` returns known to be correct values. It's a bit confusing on `Range<>` as it's not the distance between start/end or anything like that (well it's the number of steps when iterating Range so kinda the distance). It also has the side-effect that it's not implemented for Range<u64> as I guess not to hinder 32bit compatibility (len/size_hint return a usize). Because it's the iteration length it also is calculated based on iterations criteria, simplified `if start < end { end- start } else { 0 }`. Except in practice it goes from `len` to `size_hint` to the `Steps.steps_between` API in-lining all the calls and optimizing away the unnecessary overhead.

by saurik 6y ago

ratww 6y ago

Range implements the ExactSizedIterator trait, and this is why you can call `(0..5).len()`. When you call len() the ExactSizeIterator just calls size_hint [1]. The size_hint is implemented here [2]. This is where the "start < end" check happens. [1] https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs.html#71-134 https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs... [2] https://doc.rust-lang.org/src/core/iter/range.rs.html#500-552 https://doc.rust-lang.org/src/core/iter/range.rs.html#500-55...

MaulingMonkey 6y ago

> Given how general Range is, how does it even implement a len() which has the behavior in the article? len() is hidden in ExactSizeIterator, which is implemented for a bunch of Range specializations: https://doc.rust-lang.org/std/ops/struct.Range.html#impl-ExactSizeIterator https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Exa... Expanding the docs node and following the [src] link for len, we can see it's using ExactSizeIterator's default implementation, which invokes size_hint: https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs.html#99-107 https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs... ExactSizeIterator only requires Iterator: https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs.html#71 https://doc.rust-lang.org/src/core/iter/traits/exact_size.rs... And sure enough, that's where size_hint is implemented in Range: https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Iterator https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Ite... -> https://doc.rust-lang.org/src/core/iter/range.rs.html#515-522 https://doc.rust-lang.org/src/core/iter/range.rs.html#515-52... Which in turn relies on steps_between, which is implemented via macro for various integer types: https://doc.rust-lang.org/src/core/iter/range.rs.html#240-247 https://doc.rust-lang.org/src/core/iter/range.rs.html#240-24... https://doc.rust-lang.org/src/core/iter/range.rs.html#360-372 https://doc.rust-lang.org/src/core/iter/range.rs.html#360-37... https://doc.rust-lang.org/src/core/iter/range.rs.html#388-404 https://doc.rust-lang.org/src/core/iter/range.rs.html#388-40...

dathinab 6y ago

> how does it even implement a len() which has the behavior in the article? It's from `ExactSizedIterator.len()` and is a specialization of the case where `Iterator.size_hint()` returns known to be correct values. It's a bit confusing on `Range<>` as it's not the distance between start/end or anything like that (well it's the number of steps when iterating Range so kinda the distance). It also has the side-effect that it's not implemented for Range<u64> as I guess not to hinder 32bit compatibility (len/size_hint return a usize). Because it's the iteration length it also is calculated based on iterations criteria, simplified `if start < end { end- start } else { 0 }`. Except in practice it goes from `len` to `size_hint` to the `Steps.steps_between` API in-lining all the calls and optimizing away the unnecessary overhead.