add .flatten_ok() #527

vadixidav · 2021-02-07T17:38:04Z

Closes #522

SkiFire13 · 2021-02-07T19:06:06Z

src/flatten_ok.rs

+                } else {
+                    self.inner = None;
+                }
+            } else {


Do you really need this else? The only case where it isn't executed is if self.inner is Some(_) and inner.next() is also Some(_), but in that case you have an early return. I would execute the contents of the else in any case, both if the if let succeeds or not.

@SkiFire13 Your point is sound. In fact, we shouldn't even need to assign it to None in that case as it will just automatically fall through. That might hurt performance in the case where next() is called on an empty iterator repeatedly, but I don't think that actually matters. So yes, let me make that change.

I think setting it to None might have a reason if you consider consistency in case next is called after the iterator ended. Should it try to advance the last inner iterator? Or the outer iterator? Currently the stdlib fuse both of them, but I guess it would be reasonable if you advance the outer iterator (in that case you need to set the self.inner to None)

I realize now that I should not change setting the inner to None as it might incur a performance penalty when hitting several Err values in a row.

SkiFire13 · 2021-02-07T19:17:00Z

A couple of other things you could also add:

Specialized methods of Iterator, for example size_hint and fold
Some integration tests
Implementations of DoubleEndedIterator, FusedIterator and Debug to match the std's FlatMap
Since the std's FlatMap fuses the outer iterator you might consider that as well for consistency. Note however that this is undocumented behaviour, so this might change in the future.

phimuemue · 2021-02-07T19:25:24Z

src/flatten_ok.rs

+    fn clone(&self) -> Self {
+        Self {
+            iter: self.iter.clone(),
+            inner: self.inner.clone(),
+        }
+    }


You could use clone_fields for consistency here.

Thank you. Fixed and will push shortly.

vadixidav · 2021-02-07T21:49:37Z

@SkiFire13

* Specialized methods of `Iterator`, for example `size_hint` and `fold`

I don't think we can implement size_hint because even if the inner iterator had thousands of Ok elements, there is no guarantee that we will even get a single element.

I could add a specialized implementation of fold, but that could be done in another PR if someone runs into a performance issue with it. I think it should be alright as-is.

* Some integration tests

I can add those.

* Implementations of `DoubleEndedIterator`, `FusedIterator` and `Debug` to match the std's `FlatMap`

I couldn't think of a way to implement DoubleEndedIterator effectively. It would require me to store the last Ok and the next Ok at the same time. If this is acceptable, I can do it, but it will make the iterator larger and add more logic to retrieve the final elements of the inner iterator.

I can definitely implement FusedIterator and Debug, so I will do that.

* Since the std's `FlatMap` fuses the outer iterator you might consider that as well for consistency. Note however that this is undocumented behaviour, so this might change in the future.

I think I will just allow the user to call .fuse() should they need that behavior. I will implement FusedIterator if the input iterator is fused, which should make it maximally flexible for the time being.

SkiFire13 · 2021-02-07T22:14:46Z

I don't think we can implement size_hint because even if the inner iterator had thousands of Ok elements, there is no guarantee that we will even get a single element.

I think you can use the current inner iterator's size_hint for the lower bound. Far from perfect, but better than nothing.

I could add a specialized implementation of fold, but that could be done in another PR if someone runs into a performance issue with it. I think it should be alright as-is.

I think it's good practice to provide specialized implementations of fold, especially if next contains complex logic because that can prevent LLVM from autovectorizing the loops. Anyway I can add it later.

I couldn't think of a way to implement DoubleEndedIterator effectively. It would require me to store the last Ok and the next Ok at the same time. If this is acceptable, I can do it, but it will make the iterator larger and add more logic to retrieve the final elements of the inner iterator.

The stdlib does exactly that. I don't think it's a big deal if the iterator is larger since it's supposed to be short lived and probably inlined. The additional check shouldn't matter that much since if you never call next_back it's only for the very last element.

vadixidav · 2021-02-07T22:26:28Z

@SkiFire13 Okay, in that case I will add a size_hint impl. It wont help in the case that the iterator hasn't already had next called on it at least once, since the inner iterator is None, but perhaps if someone partially consumes an iterator and then tries to collect it then it might help to a degree. I will hold off on adding a specialized fold impl for now, and that can be added later. I will also implement DoubleEndedIterator now based on your comment, since that is something that matters to the API.

vadixidav · 2021-02-07T22:34:44Z

The size_hint impl actually was able to glean more information than I originally thought, but only slightly. It should be helpful in some limited cases.

vadixidav · 2021-02-07T23:23:51Z

@SkiFire13 Okay, I believe I am done now. I did not add tests for size_hint because I couldn't think of any good way to test that, but if you would like me to do that, I can add some tests for size_hint. If there is some fuzzer I can hook it up to for testing size_hint, that would be great. I can produce random sequences of iterators that could be validated by the fuzzer to not violate size_hint's contract, if we have that (I only took a cursory look at other tests).

vadixidav · 2021-02-07T23:27:21Z

Okay, I just looked over my code and I think there may be an issue if the outer iterator is not fused. Notably, the call to next() on the outer iterator now happens multiple times in the case that you have to traverse the back iterator. I am going to fix that right now.

vadixidav · 2021-02-07T23:36:26Z

I actually made the "fix" which fuses the outer iterator, and then realized it's technically still correct the way it is because if the outer iterator isn't fused, neither is FlattenOk, so this is actually fine. I was just confused 😅. I am going to leave this as is. Let me know if its good. I will save the commit which fuses the iterator in another branch on my fork, but its a bit ugly.

Branch: https://github.com/vadixidav/itertools/tree/fused_flatten_ok

SkiFire13 · 2021-02-08T09:15:41Z

Okay, I just looked over my code and I think there may be an issue if the outer iterator is not fused. Notably, the call to next() on the outer iterator now happens multiple times in the case that you have to traverse the back iterator. I am going to fix that right now.

I guess that's why the stdlib decided to always fuse the outer iterator too.

its a bit ugly

You could use the Fuse adapter instead of that bool flag

vadixidav · 2021-02-08T18:27:23Z

@SkiFire13 That's alright, I think this is good to go if you think so. If you do want it to be fused to merge though let me know, but for now its only fused if the input iterator is fused.

SkiFire13 · 2021-02-08T22:00:02Z

For merging you should ask @phimuemue or @jswrenn

phimuemue

Hi there. I think there's really progress been made on this. Thank you for taking the time.

Unfortunately, I do not have enough capacity to review pull requests that ample right now.

However, one thing that might simplify review: As far as I can see, this somewhat resembles FlattenCompat - as suggested here (btw thanks @SkiFire13). Maybe we could document this somewhere and even adapt FlattenCompats structure (i.e. naming of fields, match vs if let) so that a reviewer can basically diff your implementation against std's FlattenCompat.

phimuemue · 2021-02-09T08:00:47Z

src/flatten_ok.rs

+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("FlattenOk")
+            .field("iter", &self.iter)
+            .field("inner_front", &self.inner_front)
+            .field("inner_back", &self.inner_back)
+            .finish()
+    }


Maybe you could use debug_fmt_fields for consistency here.

jswrenn

Thanks for the contribution! (And sorry for taking so long to merge it!)

bors r+

bors · 2021-04-21T15:07:02Z

Build succeeded:

bors build finished

add .flatten_ok()

80046c6

SkiFire13 reviewed Feb 7, 2021

View reviewed changes

phimuemue reviewed Feb 7, 2021

View reviewed changes

vadixidav added 2 commits February 7, 2021 17:17

address some flatten_ok() PR comments

8421d27

add FusedIterator impl for FlattenOk

2fb1784

add size_hint impl for FlattenOk

4c09d13

vadixidav added 3 commits February 7, 2021 17:59

add inner_front,inner_back to FlattenOk and update methods

38805c6

add impl of DoubleEndedIterator to FlattenOk

238578b

added basic integration tests for .flatten_ok() without size_hint tests

fedb59e

phimuemue reviewed Feb 9, 2021

View reviewed changes

jswrenn added this to the next milestone Apr 21, 2021

jswrenn approved these changes Apr 21, 2021

View reviewed changes

bors bot merged commit 1255025 into rust-itertools:master Apr 21, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

add .flatten_ok() #527

add .flatten_ok() #527

vadixidav commented Feb 7, 2021

SkiFire13 Feb 7, 2021

vadixidav Feb 7, 2021

SkiFire13 Feb 7, 2021

vadixidav Feb 7, 2021

SkiFire13 commented Feb 7, 2021

phimuemue Feb 7, 2021

vadixidav Feb 7, 2021

vadixidav commented Feb 7, 2021

SkiFire13 commented Feb 7, 2021

vadixidav commented Feb 7, 2021

vadixidav commented Feb 7, 2021

vadixidav commented Feb 7, 2021

vadixidav commented Feb 7, 2021 •

edited

vadixidav commented Feb 7, 2021 •

edited

SkiFire13 commented Feb 8, 2021

vadixidav commented Feb 8, 2021

SkiFire13 commented Feb 8, 2021 •

edited

phimuemue left a comment

phimuemue Feb 9, 2021

jswrenn left a comment

bors bot commented Apr 21, 2021

add .flatten_ok() #527

add .flatten_ok() #527

Conversation

vadixidav commented Feb 7, 2021

SkiFire13 Feb 7, 2021

Choose a reason for hiding this comment

vadixidav Feb 7, 2021

Choose a reason for hiding this comment

SkiFire13 Feb 7, 2021

Choose a reason for hiding this comment

vadixidav Feb 7, 2021

Choose a reason for hiding this comment

SkiFire13 commented Feb 7, 2021

phimuemue Feb 7, 2021

Choose a reason for hiding this comment

vadixidav Feb 7, 2021

Choose a reason for hiding this comment

vadixidav commented Feb 7, 2021

SkiFire13 commented Feb 7, 2021

vadixidav commented Feb 7, 2021

vadixidav commented Feb 7, 2021

vadixidav commented Feb 7, 2021

vadixidav commented Feb 7, 2021 • edited

vadixidav commented Feb 7, 2021 • edited

SkiFire13 commented Feb 8, 2021

vadixidav commented Feb 8, 2021

SkiFire13 commented Feb 8, 2021 • edited

phimuemue left a comment

Choose a reason for hiding this comment

phimuemue Feb 9, 2021

Choose a reason for hiding this comment

jswrenn left a comment

Choose a reason for hiding this comment

bors bot commented Apr 21, 2021

vadixidav commented Feb 7, 2021 •

edited

vadixidav commented Feb 7, 2021 •

edited

SkiFire13 commented Feb 8, 2021 •

edited