On Thu, Oct 11, 2018 at 12:21:44PM -0400, Derrick Stolee wrote: > > > 2. INDEGREE: using the indegree_queue priority queue (ordered > > > by maximizing the generation number), add one to the in- > > > degree of each parent for each commit that is walked. Since > > > we walk in order of decreasing generation number, we know > > > that discovering an in-degree value of 0 means the value for > > > that commit was not initialized, so should be initialized to > > > two. (Recall that in-degree value "1" is what we use to say a > > > commit is ready for output.) As we iterate the parents of a > > > commit during this walk, ensure the EXPLORE walk has walked > > > beyond their generation numbers. > > I wondered how this would work for INFINITY. We can't know the order of > > a bunch of INFINITY nodes at all, so we never know when their in-degree > > values are "done". But if I understand the EXPLORE walk, we'd basically > > walk all of INFINITY down to something with a real generation number. Is > > that right? > > > > But after that, I'm not totally clear on why we need this INDEGREE walk. > > The INDEGREE walk is an important element for Kahn's algorithm. The final > output order is dictated by peeling commits of "indegree zero" to ensure all > children are output before their parents. (Note: since we use literal 0 to > mean "uninitialized", we peel commits when the indegree slab has value 1.) > > This walk replaces the indegree logic from sort_in_topological_order(). That > method performs one walk that fills the indegree slab, then another walk > that peels the commits with indegree 0 and inserts them into a list. I guess my big question here was: if we have generation numbers, do we need Kahn's algorithm? That is, in a fully populated set of generation numbers (i.e., no INFINITY), we could always just pick a commit with the highest generation number to show. So if we EXPLORE down to a real generation number in phase 1, why do we need to care about INDEGREE anymore? Or am I wrong that we always have a real generation number (i.e., not INFINITY) after EXPLORE? (And if so, why is exploring to a real generation number a bad idea; presumably it's due to a worst-case that goes deeper than we'd otherwise need to here). > [...] Everything else you said here made perfect sense. -Peff
