-
Notifications
You must be signed in to change notification settings - Fork 4
Description
Problem: the DFS can re-arrive at an intermediate state node that has the same contents and pending reconciles list. Re-processing these already-seen nodes adds a lot of extra work that we should be skipping.
We don't want to skip an already-seen intermediate state the first time we re-encounter it, as there may be alternate convergence outcomes below that intermediate state that we won't identify unless we fully explore that subtree. So currently, our code does not skip over already-seen intermediate states.
However, if we've fully explored the subtree of possibilities below some intermediate state S, then we definitely don't want to explore S again! To achieve this, we have to be able to track when an intermediate state has been "fully processed". We should be able to do this with a stack data structure, but we'll need to think about the implementation carefully.