facebookarchive/mononoke

intermediate HashSet not needed

windwardly opened this issue · 0 comments

In the file common/topo_sort/src/lib.rs:

The computation following for node in dag creates a HashSet containing the keys and parents, which extends the list of dag keys with parents not in the dag as keys. I'll call those non-key parents. Adding the non-key parents doesn't look like it can alter the output.

Non-key parents look like they are already being added to the stack to be processed. See the for child in children { loop. Note that what are referred to as parents in other files are referred to as children here.

Aside:

  1. Cool code. I liked reading through and seeing how it worked.
  2. It's not clear to me why non-key parents are part of the output, as there is not enough information to correctly topo-sort them. If there are non-key parents, then they could be
    out of order.