( )⚙ D10370 dirstate-tree: Add tree traversal/iteration

This is an archive of the discontinued Mercurial Phabricator instance.

dirstate-tree: Add tree traversal/iteration
ClosedPublic

Authored by SimonSapin on Apr 12 2021, 8:23 AM.

Details

Summary

Like Python’s, Rust’s iterators are "external" in that they are driven
by a caller who calls a next method. This is as opposed to "internal"
iterators who drive themselves and call a callback for each item.

Writing an internal iterator traversing a tree is easy with recursion,
but internal iterators cannot rely on the call stack in that way,
they must save in an explicit object all state that they need to be
preserved across two next calls.

This algorithm uses a Vec as a stack that contains what would be
local variables on the call stack if we could use recursion.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

SimonSapin created this revision.Apr 12 2021, 8:23 AM
baymax updated this revision to Diff 27053.Apr 19 2021, 11:02 AM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

Alphare accepted this revision.Apr 19 2021, 12:00 PM
This revision was not accepted when it landed; it landed in state Needs Review.
This revision was automatically updated to reflect the committed changes.