Compiler... hanging?

[forfrancissake]

Hey, I'm fairly new to rust, but using Advent of Code to go deeper into the language.

I wrote this solution to today's problem (advent-of-code-2021/1.rs at main · frankiethekneeman/advent-of-code-2021 · GitHub), and when I try to compile it (rustc -o 14/1.rxe 14/1.rs)... the compiler just hangs. No output of any kind... not even when I add -v and -g flags. I... don't have any Idea where to go from here. I feel like the problem probably lies with the recursive inject function at the bottom of the file... but no idea what's going on. I'm turning here for help as a sort of last resort.

[steffahn]

I can confirm the behavior, and it seems wrong/buggy to me. Let me try to understand the code a bit and see if there's any "reason" for this behavior and/or a way to make the example slower smaller while maintaining the hanging behavior.

[quinedot]

It's getting stuck in a recursion when trying to compile your recursive inject function. Probably it doesn't understand the base case and recurses forever (still spinning on a 512 limit though). (Even if it works, such a deeply nested structure wouldn't be great.) ((I haven't tried to figure out how deep it would be in practice.))

error[E0275]: overflow evaluating the requirement `Vec<char>: vec::spec_from_iter::SpecFromIter<char, &mut FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, FlatMap<TwopleWindows<char, std::vec::IntoIter<char>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>, Vec<char>, [closure@src/main.rs:149:19: 155:10]>>`
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`one`)

[quinedot]

@quinedot

(still spinning on a 512 limit though)

Didn't work. You'll likely have to rethink your approach. You could build your own stack in inject iteratively but I think it would be a bit gnarly since you'd probably need type erasure and mutable references to put into TwopleWindows.

[forfrancissake]

I mean, seems like I could just always collect to a Vec in between iterations, but that seems like a waste of allocations.

Just to be clear - the compiler's trying to what... figure out just how deep the type tree could ever possibly go?

[steffahn]

So your code cannot compile successfully since inject contains a recursive call to inject<FlatMap<TwopleWindows<'-, char, T>, Vec<char>, [... some closure type...]>>, i.e. a more complicated type that contains T itself again.

I'm unhappy with the compiler behavior though, it's really slow; possibly the type size/complexity somehow grows exponentially?

In order to fix this, all you'd need is properly to switch to dyn Iterator in the right place... let me give this a try.

[steffahn]

@steffahn

In order to fix this, all you'd need is properly to switch to dyn Iterator in the right place... let me give this a try.

Right, so e.g. something like

    return inject(&mut (&mut iter as &mut dyn Iterator<Item = char>), rules, n - 1);

makes it compile. (There's probably cleaner alternative solutions, in particular the double indirection could be avoided.)

[quinedot]

-struct TwopleWindows<'a, T: Copy, I: Iterator<Item=T>> {
+struct TwopleWindows<'a, T: Copy, I: ?Sized + Iterator<Item=T>> {
// ...
-impl<'a, T: Copy, I: Iterator<Item=T>> TwopleWindows<'a, T, I> {
+impl<'a, T: Copy, I: ?Sized + Iterator<Item=T>> TwopleWindows<'a, T, I> {
// ...
-impl<'a, T: Copy, I: Iterator<Item=T>> Iterator for TwopleWindows<'a, T, I> {
+impl<'a, T: Copy, I: ?Sized + Iterator<Item=T>> Iterator for TwopleWindows<'a, T, I> {
// ...
 fn inject<T>(elements: &mut T, rules: &HashMap<(char, char), char>, n: u8) -> Vec<char>
-where T: Iterator<Item = char>
+where T: ?Sized + Iterator<Item = char>
 {
     if n == 0 {
         return elements.collect();
     }
     let mut iter = TwopleWindows::new(elements)
         .flat_map(|t| match t {
             Twople::Pair(l, r) => match rules.get(&(l, r)) {
                 Some(i) => vec![l, *i],
                 None => vec![l]
             },
             Twople::Last(last) => vec![last]
         });

+    let iter_ref: &mut dyn Iterator<Item = char> = &mut iter;
+    return inject(iter_ref, rules, n - 1);
-    return inject(&mut iter, rules, n - 1);
}

[steffahn]

@steffahn

There's probably cleaner alternative solutions, in particular the double indirection could be avoided.)

For example, you can generalize a few instances of &mut T T: Iterator... into T, T: Iterator. It could be

struct TwopleWindows<T: Copy, I: Iterator<Item=T>> {
    done: bool,
    prev: Option<T>,
    backer: I
}

and

fn inject<T>(elements: T, rules: &HashMap<(char, char), char>, n: u8) -> Vec<char>
where T: Iterator<Item = char>

and then something like

inject(&mut iter as &mut dyn Iterator<Item = char>, rules, n - 1)

works

use std::fs;
use std::collections::HashMap;

type ParseTarget = (Vec<char>, HashMap<(char, char), char>);
type Solution = usize;

const EXAMPLES: [(&str, Solution); 1] = [
    ("1", 1588)
];

const DAY: u8 = 14;

fn main() {
    let results = EXAMPLES.iter()
        .zip(
            EXAMPLES.iter()
                .map(|t| format!("{}/{}.ie", DAY, t.0))
                .map(operation)
        )
        .map(|((name, expected), result)| 
            (
                *name,
                result
                    .and_then(|actual| if *expected == actual {
                        return Ok(());
                    } else {
                        return Err(format!("Expected {} but got {}", expected, actual));
                    })
            )
        )
        .collect::<Vec<(&str, Result<(), String>)>>();
    results.iter()
        .for_each(|(name, result)| match result {
            Ok(()) => println!("Example {} passed.", name),
            Err(msg) => println!("Example {} failed: {}.", name, msg)
        });

    if results.iter().any(|t| t.1.is_err()) {
        panic!("Please address errors before attempting the problem.")
    }

    println!(
        "{}",
        operation(format!("{}/input", DAY)).expect("Unexpected Error in main input.")
    );
}

fn error<T>(msg: &str) -> Result<T, String> {
    return Err(String::from(msg));
}

fn operation(filename: String) -> Result<Solution, String> {
    return fs::read_to_string(filename)
        .map_err(|io_error| format!("{}", io_error))
        .and_then(parse)
        .and_then(solve);
}

fn parse(contents: String) -> Result<ParseTarget, String> {
    let mut lines = contents.lines();
    let template: Vec<char> = lines.next()
        .ok_or("No lines?")?
        .chars()
        .collect();

    if lines.next().is_none() {
        return error("No empty line");
    }
    
    let mut insertion_rules = HashMap::new();

    for l in lines {
        let first = l.chars().nth(0).ok_or("Malformed line".to_string())?;
        let second = l.chars().nth(1).ok_or("Malformed line".to_string())?;
        let insertion = l.chars().nth(6).ok_or("Malformed line".to_string())?;

        insertion_rules.insert(
            (first, second),
            insertion
        );
    }
        
    return Ok((template, insertion_rules));
}
enum Twople<T> {
    Pair(T, T),
    Last(T)
}

struct TwopleWindows<T: Copy, I: Iterator<Item=T>> {
    done: bool,
    prev: Option<T>,
    backer: I
}

impl<T: Copy, I: Iterator<Item=T>> TwopleWindows<T, I> {
    fn new(backer: I) -> TwopleWindows<T, I> {
        return TwopleWindows {
            done: false,
            prev: None,
            backer: backer
        };
    }
}

impl<T: Copy, I: Iterator<Item=T>> Iterator for TwopleWindows<T, I> {
    type Item = Twople<T>;
    fn next(&mut self) -> Option<Twople<T>> {
        if self.done {
            return None;
        }
        let first = self.prev.or_else(|| self.backer.next())?;
        match self.backer.next() {
            Some(second) => {
                self.prev = Some(second);
                return Some(Twople::Pair(first, second));
            }
            None => {
                self.done = true;
                return Some(Twople::Last(first))
            }
        }
    }
}

fn solve(parsed: ParseTarget) -> Result<Solution, String> {
    let (template, rules) = parsed;
    let result = inject(template.into_iter(), &rules, 10);
    let mut counts: HashMap<char, usize> = HashMap::new(); 
    for c in result.iter() {
        counts.insert(
            *c,
            *counts.get(c).unwrap_or(&0) + 1
        );
    }

    let max = counts.values().max().ok_or("No maximum".to_string())?;
    let min = counts.values().min().ok_or("No minimum".to_string())?;
    return Ok(*max - *min);
}

fn inject<T>(elements: T, rules: &HashMap<(char, char), char>, n: u8) -> Vec<char>
where T: Iterator<Item = char>
{
    if n == 0 {
        return elements.collect();
    }
    let mut iter = TwopleWindows::new(elements)
        .flat_map(|t| match t {
            Twople::Pair(l, r) => match rules.get(&(l, r)) {
                Some(i) => vec![l, *i],
                None => vec![l]
            },
            Twople::Last(last) => vec![last]
        });

    return inject(&mut iter as &mut dyn Iterator<Item = char>, rules, n - 1);
}

---

Right.. the approach that @quinedot presents above works, too, but then you'd need to get into things involving ?Sized.

[quinedot]

@steffahn

I'm unhappy with the compiler behavior though, it's really slow; possibly the type size/complexity somehow grows exponentially?

Back to this, I was running on rustc 1.54.0 (a178d0322 2021-07-26). It was slow but not "forever". It's also a pretty old computer. Perhaps a regression sometime in the last few versions?

[quinedot]

@forfrancissake

Just to be clear - the compiler's trying to what... figure out just how deep the type tree could ever possibly go?

Something like that...

Compiler:

• Hmm, they call inject with T=IntoIter, better monomorphize that
  • Hmm, they call inject with T=Map<Twople<closure...>>, better monomorphize that
    • Hmm, they call inject with T=Map<Twople<Map<Twople<...>>>>, better...

(n.b.: just an educated guess at the exact process.)

By calling with T=dyn Iterator<Item=Char> instead, there's no endless monomorphizing with a more deeply nested type.

[forfrancissake]

I... have a lot more reading to do, it seems, because I really have no idea why ?Sized changes things, nor really how dyn works. Thanks for your help, though!

[scottmcm]

Here's the rust issue tracking trying to give better pre-emptive lints here:
https://github.com/rust-lang/rust/issues/90289

[steffahn]

The simple version is: You can turn every &mut T with T: Iterator<Item = char> into a single type &mut dyn Iterator<Item = char>. This means that values of a lot of types &mut Foo, &mut Bar, &mut Baz, &mut Complicated<Whatever, Qux> can all be be unified under a single type.

---

What's to solve here? Well...

When you call a function foo<T>() where T: Iterator<Item = char> then every call to foo<Bar> or foo<Baz> is compiled to a so-called "monomorphized" special version of the function foo, just for that type. This can lead to very good optimization, but you can naturally only monomorphize for finitely many types during compilation.

If a recursive function foo<T> calls foo<SomeType<T>>, then that call will call to

foo<SomeType<SomeType<T>>>

recursively, which in turn will call

foo<SomeType<SomeType<SomeType<T>>>>

and this will call

foo<SomeType<SomeType<SomeType<SomeType<T>>>>>

and so on.. There's no end to this. Note that the compilation of such a recursive function cannot terminate on some kind of base case either; the fact that some - potentially unreachable - branch of foo<T> can potentially call foo<SomeType<T>> is enough for this infinite "explosion" of function instances to monomorphize.

---

Now, if instead, every foo<T> only calls something like foo<&mut dyn Iterator<Item = char>> recursively, then this new instance of foo doesn't call any more complicated type, it too will just call foo<&mut dyn Iterator<Item = char>>. The compiler is happy ^^. The crucial part was that the type &mut dyn Iterator<Item = char> does not "mention" T anymore; the fact that SomeType<T> contains T is what makes the type become more and more complicated for each recursive call in the example above.

The program will still build up some increasingly deeply nested values at run-time, but on each recursive call, a new layer of dyn Iterator<...> basically introduces some "dynamic" abstraction that allows your compiled code to treat all the increasingly complicated values uniformly in the same way without any need to generate an infinitude of more and more specialized / monomorphized code.

[quinedot]

Yeah, read up on dyn Trait sometime, and you'll learn about ?Sized as part of that. A whirlwind version follows (but you'll want to read some real documentation / guide eventually).

• Types that implement Trait can coerce into dyn Trait
  • If the trait is dyn-safe, and the type is Sized, ...
  • dyn Trait performs dynamic dispatch but is not a dynamic (runtime) type
• So this is a static type too, but erases the type of the base type
  • The erasure "breaks" the recursion of nested types in your OP, which we want

@steffahn's reply right before this one covers this motivation as it relates to your OP in more detail. As for the ?Sized stuff...

• The dyn Trait type has no static size (each base type might have a different size)
  • In Rust terms, it does not implement the Sized trait
  • The Sized trait is an implicit bound in many places
  • You opt out of that bound by using ?Sized
• Also because of this not-Sized nature, it always lives behind a pointer of some kind when being stored or passed
  • &dyn Trait, &mut dyn Trait, Box<dyn Trait>, ...

And putting them together, the diff I supplied was generated by...

• Passing &mut iter to inject as a &mut dyn Iterator<...>
• Getting a bunch of "this has to be Sized" errors due to the implicit bounds
• Subsequently putting ?Sized bounds to opt out of Sized where needed
  • This turned out to be straight-forward because your iterators were all behind a &mut already
• And that was it, it compiled. (I didn't try running it on anything.)

[steffahn]

@steffahn

a way to make the example slower smaller while maintaining the hanging behavior

Here we go

fn main() {
    recurse([].into_iter());
}

struct Wrapped<T>(T);

struct IteratorOfWrapped<T, I: Iterator<Item = T>>(I);

impl<T, I: Iterator<Item = T>> Iterator for IteratorOfWrapped<T, I> {
    type Item = Wrapped<T>;
    fn next(&mut self) -> Option<Wrapped<T>> {
        self.0.next().map(Wrapped)
    }
}

fn recurse<T>(elements: T) -> Vec<char>
where
    T: Iterator<Item = ()>,
{
    recurse(IteratorOfWrapped(elements).map(|t| t.0))
}

This seems to slow down exponentially with increasing recursion_limit, a limit of 30 already takes several seconds on my machine.

[steffahn]

Using

#![recursion_limit = "30"]

fn main() {
    recurse(std::iter::empty());
}

struct Wrapped<T>(T);

struct IteratorOfWrapped<T, I: Iterator<Item = T>>(I);

impl<T, I: Iterator<Item = T>> Iterator for IteratorOfWrapped<T, I> {
    type Item = Wrapped<T>;
    fn next(&mut self) -> Option<Wrapped<T>> {
        self.0.next().map(Wrapped)
    }
}

fn recurse<T>(elements: T) -> Vec<char>
where
    T: Iterator<Item = ()>,
{
    recurse(IteratorOfWrapped(elements).map(|t| t.0))
}

since it doesn't use editon 2021, this clearly seems to be a performance regression in 1.56.

In the compiler explorer on 1.55, #![recursion_limit = "800"] works, and on 1.56 not even #![recursion_limit = "30"] works without timeout.

[steffahn]

Opened

https://github.com/rust-lang/rust/issues/91949