|Re: [jgit-dev] Implementing shallow clones|
On Tue, Aug 3, 2010 at 2:18 PM, Matt Fischer <mattfischer84@xxxxxxxxx> wrote: > The most efficient way to do this (and what C git does) is the following: > > 1. Set up a queue (FIFORevQueue in jgit parlance), and seed it with > all the root commits. Mark them as depth 0. > 2. Pop a commit from the front of the queue, and examine its depth. > 3. Set all parents of this commit to depth n + 1, unless their depth > is already less than this. > 4. Add any parents whose depth is less than the cutoff to the back of > the queue. > 5. Produce the popped commit, and repeat from 2 until the queue is empty. > > This works because it's basically a breadth-first descent into the > graph. If you have a commit that can be arrived at by two different > routes, you'll always get there by the shortest route first, because > the queue is FIFO. Oh, great idea. I knew we had a reason for FIFORevQueue. :-) (IIRC right now its unused.) > PendingGenerator almost does this, but it's built around a > DateRevQueue, so it's not guaranteed to get the ordering right. It > kind of feels like the right way to do this would just be to > completely forgo use of the PendingGenerator, and have DepthGenerator > start directly from the root commits and spin out its own tree. I agree. > That's kind of an invasive change to StartGenerator, though--would > something like that be ok with you, or is there some other way to > integrate this algorithm into the existing structure? Yes, its fine. But IIRC it shouldn't be that bad to insert into StartGenerator. Most of the pipeline doesn't care that its a PendingGenerator or some other type of Generator... just that a Generator exists for it to wrap its stage around. So you should be able to conditionally create your new DepthGenerator or the PendingGenerator based on the type of walk being done. -- Shawn.
Back to the top