Can an infinite recursive dart generator(yield*) stack overflow?

user_18308245 0
Viewed 93

I am trying to know if an infinite recursive generator can cause a stack overflow error. I'm not sure if infinite recursion is a correct use case for generators, but I couldn't find any clues about it in the documentation.

Let's take this example:

import 'dart:async';

Stream<bool> infiniteStream(bool t) async* {
  yield t;
  await Future.delayed(Duration(milliseconds: 1));
  yield* infiniteStream(!t);
}

void main() async {
  await for (final value in infiniteStream(true)) {
    print(value);
  }
}

Is this a correct use of generators? Or will it cause error/performance problems after a long period of time? If this is not correct, what is the correct way to implement an infinite stream that can add events to itself in response to received events?

Also I've noticed that without Future.delayed(), dartpad crashes.

dart infinite stack-overflow generator recursion
1 Answers

It can definitely overflow something, but in this case it's likely the heap, so that's unlikely to happen quickly. (It will happen if you let it keep running long enough, though.)

Because the code is asynchronous, the actual stack traces only go from the event loop to the continuation of the asynchronous computation. It doesn't retain the stack which initiated the asynchronous computation (because that stack has already has a stream or future returned to it a long time ago). It probably has to propagate the yielded value back through a chain of Stream listeners linear in the depth of the recursion, but those will be heap-allocated.

That's based on the current implementation strategy. There is nothing preventing an implementation based on separate stacks for asynchronous computations, which could reuse the same stack for the yield* operation (or an await asyncFunction() call). If such an implementation happens, it's no longer guaranteed that you won't see a stack overflow for code like this.

Similarly, a sync* function may lead to stack overflows if you do unbounded recursive yield*s, but currently also only uses heap space.

user_21566210
Related