On Fri, Sep 08, 2017 at 02:33:35PM +0200, Michael J Gruber wrote: > Looking at it more closely, the solution in cbc60b6720 ("git tag > --contains: avoid stack overflow", 2014-04-24) seems to be a bit "ad > hoc" to me: > > First of all, there is more than "tag --contains" that may exceed the > stack by recursion. So I would expect the solution to be more general, > and not localised and specialised to builtin/tag.c
At the time, tag was the only one using this depth-first contains algorithm. It's since been adapted to ref-filter.c, but of course the stack handling went with it. Most traversals have a date-sorted queue, so are effectively doing a breadth-first iteration with no recursion. > Second, this is a walk, so I'm wondering whether our revision walk > machinery should be the place to add missing functionality (if any). > That way, everything would benefit from possible or existing > improvements there. For example, I think some of our "extra walkers" > don't heed object replacements. (I need to test more.) It's possible that name-rev could make better use of the existing traversal machinery. It's often tough to do so, though, because that machinery gives you a linearized ordering of the commits. Whereas something like name-rev really cares about the order that it visits the commits, because it's building up the names. It's the same for this "tag --contains" traversal. It _used_ to be a series of merge-base computations. But by doing a custom traversal, we can cache incremental results through the graph and avoid walking over the same bits multiple times. There actually is a way to do it with the regular breadth-first traversal, but you have to store one bit per ref you're checking for each commit. I played around with that a bit a while ago, and it did seem to work. I can dig up the patches if you're interested. But one downside is that one bit per ref per commit adds up if you have a lot of refs. A large number of those bitfields will be the same, so you could probably get by with a copy-on-write scheme, but I never implemented that. Of course somebody may have a more clever algorithm, too. I don't claim the above is a proof. ;) -Peff