LGTM.

Regarding the placement of the code, the (ideal) data structure you need for this is a lazy version of the DAG, because you need to only fetch the nodes that are different, and the only module that can do that for you is indeed swh.storage.
So I'm fine having this in swh.storage. I'm not sure I like "utils" (which sounds low-level), maybe "operations" or "algo" (which sound higher-level, like this functionality actually is) would be more appropriate here? I've no strong opinion either...
Either way, I'd like to uniform with what @seirl has done for toposort in swh.model. So whatever name we pick here, toposort in swh.model should go under swh.model.THATNAME.toposort .

On an unrelated note, isn't the Directory iterator you've implemented here something reusable for other needs?
If so, it might deserve its own model and to drop the leading underscore.

Regarding the placement of the code, the (ideal) data structure you need for this is a lazy version of the DAG, because you need to only fetch the nodes that are different, and the only module that can do that for you is indeed swh.storage.
So I'm fine having this in swh.storage.

From my point of view, this could have been implemented outside the swh.storage namespace (put in a swh.algos one for instance)
but for commodity of use and easy setup, it will stay in storage at the moment.

I'm not sure I like "utils" (which sounds low-level), maybe "operations" or "algo" (which sound higher-level, like this functionality actually is) would be more appropriate here? I've no strong opinion either...
Either way, I'd like to uniform with what @seirl has done for toposort in swh.model. So whatever name we pick here, toposort in swh.model should go under swh.model.THATNAME.toposort .

I would go for "swh.storage.algos" as it is concise and self explanatory.

On an unrelated note, isn't the Directory iterator you've implemented here something reusable for other needs?
If so, it might deserve its own model and to drop the leading underscore.

Sure, this could be reused. I could move the implemented iterators in a "swh.storage.algos.dir_iterators"
for instance.

I feel like this looks a lot like the diff tree algorithm that's already here: https://forge.softwareheritage.org/source/swh-vault/browse/master/swh/vault/cookers/revision_gitfast.py;bca66197586f31c10042d43897717d7aec90e797$21 but I don't think anyone cares enough to look at how we could merge those two algorithms now, so I guess we can just have both separately :-P

I think that the swh.storage.Storage API should expose at least the last two, and probably all three of the following operations:

• diff two directories (basic building block of this API)
• diff the directories for two arbitrary revisions
• get the diffs of a revision with (all) its parents

The last function is a superset of the current exposed API. In the case of a commit with a single parent, it would return the single diff representation. In case of a merge commit with several parents, it would give the diff to each parent, which would then allow frontends to show a git-like Combined Diff (https://git-scm.com/docs/diff-format#_combined_diff_format)