Repository: rust-itertools/itertools (language: rust)

Issue:
Permutations unnecessarily complex?
During my review of #739, I found `Permutations` quite complex.

As of now, it has four different states: `StartUnknownLen`, `OngoingUnknownLen`, `Complete` and `Empty`. Its cousin `Combinations`, on the other hand, only has fields `first`, `pool`, `indices`.

My gut feeling is that `Permutations` could be massaged into a simpler form that more resembles the one of `Combinations`.

@Philippe-Cholet Since you studied that code, can I have your two cents on this?


Discussion / hints:
I agree it's quite complex (but the states are clear thanks to the type system). It's probably because of this complexity that the size hint was incomplete until I fixed it.
I have a similar gut feeling, it's probably simplifiable into a single case since `UnknownLen` states are only transition until we have `CompleteState::Ongoing` (and `Empty` might be easily ditched?).
The _major difference_ though is the additional field `cycles`, which is currently defined only once we know `n` for sure.
Instead of `first: bool`, maybe a more complex type to represent the transition (until we know `n`). Well, I'm just thinking..

Do you want me to investigate changes further?
EDIT: Well, I'm investigating.
I just wanted to take time to appreciate what's currently done. Each `Iterator::next` step is `advance+item` in the below state diagram (I wanted to do some nice mermaid diagram for quite some time now):
```mermaid
stateDiagram-v2
    classDef rust color:orange

    state k_eq_0 <<choice>>
    k_eq_0: k == 0 ?
    state enough <<choice>>
    enough: Enough values ?
    state full <<choice>>
    full: pool.get_next() ?
    state end <<choice>>
    end: The end ?

    [*]
    [*] --> k_eq_0
    k_eq_0 --> enough: No
    k_eq_0 --> CompleteStart: Yes
    enough --> [*]: No
    enough --> StartUnknownLen: Yes
    CompleteStart --> [*]: NO item
    StartUnknownLen --> OngoingUnknownLen: advance
    full --> OngoingUnknownLen: No
    full --> CompleteStart: Yes, then advance X times...
    OngoingUnknownLen --> full: advance
    OngoingUnknownLen --> OngoingUnknownLen: item
    CompleteStart --> CompleteOngoing: advance
    CompleteOngoing --> CompleteOngoing: item
    CompleteOngoing --> end: advance
    end --> CompleteOngoing: No, mostly
    end --> CompleteStart: Yes, a single time

    class CompleteStart, StartUnknownLen, OngoingUnknownLen, CompleteOngoing rust
```
Once loaded, we are in `CompleteOngoing` state until the end.
Now in https://github.com/rust-itertools/itertools/compare/master...Philippe-Cholet:itertools:permutations-states , I have

    pub struct Permutations<I: Iterator> {
        vals: LazyBuffer<I>,
        state: PermutationState,
    }
    enum PermutationState {
        Start { k: usize },
        Ongoing { k: usize, min_n: usize },
        Complete { indices: Vec<usize>, cycles: Vec<usize> }, // CompleteState have been merged
        End,
    }

Maybe we can simplify this state further. `Option<PermutationState>` to get rid of `End`? Maybe merge `Ongoing` with another variant (but it would probably be less readable)?

The main commit has 80 additions and 143 deletions: nice simplification IMO.

<details>
<summary>Updated mermaid diagram</summary>

```mermaid
stateDiagram-v2
    classDef rust color:orange

    state enough <<choice>>
    enough: Enough values ?
    state k0 <<choice>>
    k0: k == 0 ?
    state full <<choice>>
    full: pool.get_next() ?
    state end <<choice>>
    end: The end ?

    [*] --> enough
    enough --> [*]: No
    enough --> Start: Yes
    Start --> k0: next
    k0 --> [*]: Yes
    k0 --> Ongoing: No
    full --> Ongoing: No
    full --> Complete: Yes, then advance X times...
    Ongoing --> full: next
    Complete --> end: next
    end --> Complete: No
    end --> [*]: Yes

    class Start, Ongoing, Complete rust
```
</details>
https://github.com/rust-itertools/itertools/compare/master...Philippe-Cholet:itertools:permutations-states
I flattened `PermutationState` variant by variant until it became a struct, which I merged into `Permutations` leading to

    pub struct Permutations<I: Iterator> {
        indices: Option<Vec<usize>>, // is None when there is no permutation left
        first: bool,
        cycles: Option<Vec<usize>>, // is None while n is still unknown
        vals: LazyBuffer<I>,
    }
`indices` starts with length `k` ; and once `n` is known, `cycles` is of length `k` while `indices` become of length `n`.

I'm not sure it's better than a more verbose structure, but it's definitely possible.

EDIT: Previous https://github.com/rust-itertools/itertools/commit/c17761ad83a9a7f6e68a2c67a8b0c05862b0c62a and https://github.com/rust-itertools/itertools/commit/486b3483f36345b14aaeafad7ba6d964dba14216 about `advance` function might be cherry-picked OUT because it is a bit slower (+10% on some huge test, but only in debug mode?!) with those changes. Apart from that, my changes do not speed things up or down.
@phimuemue Since you are around, I put a little remainder here.
Hi @Philippe-Cholet, I appreciate that you want to tackle the problem. I tried to review your commits, and I think most of it is really good.

Unfortunately I cannot point my finger at the exact places, but I think I've lost track of the possible states. It surely does not help that I'm not intricately familiar with the `cycles` logic in there and that I do not have enough time to do a proper review of this.

As much as I'd love to answer with "yeah, I saw and understood this", I can't offer a more thorough review at the moment.
@phimuemue
It's a huge rewrite with quite a few steps (as atomic as reasonable but each change is not straightforward).

Destroy the enum `PermutationState` variant by variant is possible but _it leads to having impossible but representable states_ (basically ignored with match patterns order and `..` ignoring stuff) and therefore lead to most of your (legitimate) questions. And after a big month, I have to understand some parts of the code again.
Having `first: bool` was easy enough to keep in mind but `indices` and `cycles` possibly being none is complex to easily remember (and `indices` length is k or n depending on having the lazy buffer is loading or filled).

**I really prefer `enum PermutationState`** after the second commit: the `Start { k }, Ongoing { k, min_n }, Complete { indices, cycles }, End` variants are way more explicit.
Below I quote one of my commit messages about `None` uses and comment it as I think it was better represented with the enum:

> indices being None means there is no permutation left. Even if first is true. // It was previously better represented by the `End` variant.
> cycles being None means the buffer is not full yet and n is still unknown. // It was previously better represented by the `Ongoing {k,min_n}` variant.

---
I think we should **only keep the first 3 commits** and simply discard the rest. The first and third are basic. The second that merges `CompleteState` into `PermutationsState` and hugely simplify `next` after #748 as it merges the two steps there was before and discard `panic!("unexpected iterator state")`.
Maybe I can simplify/split this second commit though.
Hi @Philippe-Cholet, sounds very reasonable.

Fix patch:
diff --git a/src/permutations.rs b/src/permutations.rs
index b6ff5c4fa..5dd3dbf9a 100644
--- a/src/permutations.rs
+++ b/src/permutations.rs
@@ -1,6 +1,7 @@
 use alloc::vec::Vec;
 use std::fmt;
 use std::iter::once;
+use std::iter::FusedIterator;
 
 use super::lazy_buffer::LazyBuffer;
 use crate::size_hint::{self, SizeHint};
@@ -26,22 +27,17 @@ where
 
 #[derive(Clone, Debug)]
 enum PermutationState {
-    StartUnknownLen { k: usize },
-    OngoingUnknownLen { k: usize, min_n: usize },
-    Complete(CompleteState),
-    Empty,
-}
-
-#[derive(Clone, Debug)]
-enum CompleteState {
-    Start {
-        n: usize,
-        k: usize,
-    },
-    Ongoing {
+    /// No permutation generated yet.
+    Start { k: usize },
+    /// Values from the iterator are not fully loaded yet so `n` is still unknown.
+    Buffered { k: usize, min_n: usize },
+    /// All values from the iterator are known so `n` is known.
+    Loaded {
         indices: Vec<usize>,
         cycles: Vec<usize>,
     },
+    /// No permutation left to generate.
+    End,
 }
 
 impl<I> fmt::Debug for Permutations<I>
@@ -55,20 +51,13 @@ where
 pub fn permutations<I: Iterator>(iter: I, k: usize) -> Permutations<I> {
     let mut vals = LazyBuffer::new(iter);
 
-    if k == 0 {
-        // Special case, yields single empty vec; `n` is irrelevant
-        let state = PermutationState::Complete(CompleteState::Start { n: 0, k: 0 });
-
-        return Permutations { vals, state };
-    }
-
     vals.prefill(k);
     let enough_vals = vals.len() == k;
 
     let state = if enough_vals {
-        PermutationState::StartUnknownLen { k }
+        PermutationState::Start { k }
     } else {
-        PermutationState::Empty
+        PermutationState::End
     };
 
     Permutations { vals, state }
@@ -82,169 +71,117 @@ where
     type Item = Vec<I::Item>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        {
-            let &mut Permutations {
-                ref mut vals,
-                ref mut state,
-            } = self;
-            match *state {
-                PermutationState::StartUnknownLen { k } => {
-                    *state = PermutationState::OngoingUnknownLen { k, min_n: k };
-                }
-                PermutationState::OngoingUnknownLen { k, min_n } => {
-                    if vals.get_next() {
-                        *state = PermutationState::OngoingUnknownLen {
-                            k,
-                            min_n: min_n + 1,
-                        };
-                    } else {
-                        let n = min_n;
-                        let prev_iteration_count = n - k + 1;
-                        let mut complete_state = CompleteState::Start { n, k };
-
-                        // Advance the complete-state iterator to the correct point
-                        for _ in 0..(prev_iteration_count + 1) {
-                            complete_state.advance();
+        let Self { vals, state } = self;
+        match state {
+            PermutationState::Start { k: 0 } => {
+                *state = PermutationState::End;
+                Some(Vec::new())
+            }
+            &mut PermutationState::Start { k } => {
+                *state = PermutationState::Buffered { k, min_n: k };
+                Some(vals[0..k].to_vec())
+            }
+            PermutationState::Buffered { ref k, min_n } => {
+                if vals.get_next() {
+                    let item = (0..*k - 1)
+                        .chain(once(*min_n))
+                        .map(|i| vals[i].clone())
+                        .collect();
+                    *min_n += 1;
+                    Some(item)
+                } else {
+                    let n = *min_n;
+                    let prev_iteration_count = n - *k + 1;
+                    let mut indices: Vec<_> = (0..n).collect();
+                    let mut cycles: Vec<_> = (n - k..n).rev().collect();
+                    // Advance the state to the correct point.
+                    for _ in 0..prev_iteration_count {
+                        if advance(&mut indices, &mut cycles) {
+                            *state = PermutationState::End;
+                            return None;
                         }
-
-                        *state = PermutationState::Complete(complete_state);
                     }
+                    let item = indices[0..*k].iter().map(|&i| vals[i].clone()).collect();
+                    *state = PermutationState::Loaded { indices, cycles };
+                    Some(item)
                 }
-                PermutationState::Complete(ref mut state) => {
-                    state.advance();
-                }
-                PermutationState::Empty => {}
-            };
-        }
-        let &mut Permutations {
-            ref vals,
-            ref state,
-        } = self;
-        match *state {
-            PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"),
-            PermutationState::OngoingUnknownLen { k, min_n } => {
-                let latest_idx = min_n - 1;
-                let indices = (0..(k - 1)).chain(once(latest_idx));
-
-                Some(indices.map(|i| vals[i].clone()).collect())
             }
-            PermutationState::Complete(CompleteState::Ongoing {
-                ref indices,
-                ref cycles,
-            }) => {
+            PermutationState::Loaded { indices, cycles } => {
+                if advance(indices, cycles) {
+                    *state = PermutationState::End;
+                    return None;
+                }
                 let k = cycles.len();
                 Some(indices[0..k].iter().map(|&i| vals[i].clone()).collect())
             }
-            PermutationState::Complete(CompleteState::Start { .. }) | PermutationState::Empty => {
-                None
-            }
+            PermutationState::End => None,
         }
     }
 
     fn count(self) -> usize {
-        fn from_complete(complete_state: CompleteState) -> usize {
-            complete_state
-                .remaining()
-                .expect("Iterator count greater than usize::MAX")
-        }
-
-        let Permutations { vals, state } = self;
-        match state {
-            PermutationState::StartUnknownLen { k } => {
-                let n = vals.count();
-                let complete_state = CompleteState::Start { n, k };
-
-                from_complete(complete_state)
-            }
-            PermutationState::OngoingUnknownLen { k, min_n } => {
-                let prev_iteration_count = min_n - k + 1;
-                let n = vals.count();
-                let complete_state = CompleteState::Start { n, k };
-
-                from_complete(complete_state) - prev_iteration_count
-            }
-            PermutationState::Complete(state) => from_complete(state),
-            PermutationState::Empty => 0,
-        }
+        let Self { vals, state } = self;
+        let n = vals.count();
+        state.size_hint_for(n).1.unwrap()
     }
 
     fn size_hint(&self) -> SizeHint {
-        let at_start = |k| {
-            // At the beginning, there are `n!/(n-k)!` items to come (see `remaining`) but `n` might be unknown.
-            let (mut low, mut upp) = self.vals.size_hint();
-            low = CompleteState::Start { n: low, k }
-                .remaining()
-                .unwrap_or(usize::MAX);
-            upp = upp.and_then(|n| CompleteState::Start { n, k }.remaining());
-            (low, upp)
-        };
-        match self.state {
-            PermutationState::StartUnknownLen { k } => at_start(k),
-            PermutationState::OngoingUnknownLen { k, min_n } => {
-                // Same as `StartUnknownLen` minus the previously generated items.
-                size_hint::sub_scalar(at_start(k), min_n - k + 1)
-            }
-            PermutationState::Complete(ref state) => match state.remaining() {
-                Some(count) => (count, Some(count)),
-                None => (::std::usize::MAX, None),
-            },
-            PermutationState::Empty => (0, Some(0)),
-        }
+        let (mut low, mut upp) = self.vals.size_hint();
+        low = self.state.size_hint_for(low).0;
+        upp = upp.and_then(|n| self.state.size_hint_for(n).1);
+        (low, upp)
     }
 }
 
-impl CompleteState {
-    fn advance(&mut self) {
-        *self = match *self {
-            CompleteState::Start { n, k } => {
-                let indices = (0..n).collect();
-                let cycles = ((n - k)..n).rev().collect();
-
-                CompleteState::Ongoing { cycles, indices }
-            }
-            CompleteState::Ongoing {
-                ref mut indices,
-                ref mut cycles,
-            } => {
-                let n = indices.len();
-                let k = cycles.len();
-
-                for i in (0..k).rev() {
-                    if cycles[i] == 0 {
-                        cycles[i] = n - i - 1;
-
-                        let to_push = indices.remove(i);
-                        indices.push(to_push);
-                    } else {
-                        let swap_index = n - cycles[i];
-                        indices.swap(i, swap_index);
-
-                        cycles[i] -= 1;
-                        return;
-                    }
-                }
+impl<I> FusedIterator for Permutations<I>
+where
+    I: Iterator,
+    I::Item: Clone,
+{
+}
 
-                CompleteState::Start { n, k }
-            }
+fn advance(indices: &mut [usize], cycles: &mut [usize]) -> bool {
+    let n = indices.len();
+    let k = cycles.len();
+    // NOTE: if `cycles` are only zeros, then we reached the last permutation.
+    for i in (0..k).rev() {
+        if cycles[i] == 0 {
+            cycles[i] = n - i - 1;
+            indices[i..].rotate_left(1);
+        } else {
+            let swap_index = n - cycles[i];
+            indices.swap(i, swap_index);
+            cycles[i] -= 1;
+            return false;
         }
     }
+    true
+}
 
-    /// Returns the count of remaining permutations, or None if it would overflow.
-    fn remaining(&self) -> Option<usize> {
+impl PermutationState {
+    fn size_hint_for(&self, n: usize) -> SizeHint {
+        // At the beginning, there are `n!/(n-k)!` items to come.
+        let at_start = |n, k| {
+            debug_assert!(n >= k);
+            let total = (n - k + 1..=n).try_fold(1usize, |acc, i| acc.checked_mul(i));
+            (total.unwrap_or(usize::MAX), total)
+        };
         match *self {
-            CompleteState::Start { n, k } => {
-                if n < k {
-                    return Some(0);
-                }
-                (n - k + 1..=n).try_fold(1usize, |acc, i| acc.checked_mul(i))
+            Self::Start { k } => at_start(n, k),
+            Self::Buffered { k, min_n } => {
+                // Same as `Start` minus the previously generated items.
+                size_hint::sub_scalar(at_start(n, k), min_n - k + 1)
             }
-            CompleteState::Ongoing {
+            Self::Loaded {
                 ref indices,
                 ref cycles,
-            } => cycles.iter().enumerate().try_fold(0usize, |acc, (i, &c)| {
-                acc.checked_mul(indices.len() - i)
-                    .and_then(|count| count.checked_add(c))
-            }),
+            } => {
+                let count = cycles.iter().enumerate().try_fold(0usize, |acc, (i, &c)| {
+                    acc.checked_mul(indices.len() - i)
+                        .and_then(|count| count.checked_add(c))
+                });
+                (count.unwrap_or(usize::MAX), count)
+            }
+            Self::End => (0, Some(0)),
         }
     }
 }


Test patch: