I think its easier than you think.

When using DepthWalk.ObjectWalk we need some additional state.  The client has already told us its old shallow boundary, and we know the new shallow boundary.  What you want to do is  color every object in the have (aka commonBase / uninterestingObjects) list up to but not including the old shallow boundary with the flag UNINTERESTING.

To do this, we can add a new flag, UNSHALLOW, at the old shallow boundary.  In DepthGenerator as you loop through the parents of a commit do something like this:

  if (c.has(UNSHALLOW))
    p.add(UNSHALLOW);

  if (c.has(UNINTERESTING)) {
    if (p.has(UNSHALLOW))
      c.add(BOUNDARY);
    else
      p.add(UNINTERESTING);
  }

This block replaces the standard walker.carryFlagsImpl logic with something more specific.  We only carry UNINTERESTING up until the edge, and then we cut over to carrying UNSHALLOW instead.

Now we shouldn't output every UNINTERESTING commit, not all of them are relevant.  Instead the produce logic (after deciding depth as that's cheap) is something like:

  if (produce)
    produce = c.has(UNINTERESTING) ? c.has(BOUNDARY) : false;

Basically what I am doing here is coloring everything up to the boundary as UNINTERESTING, and we don't normally produce that.  But when we find a commit that was UNINTERESTING and has a parent that is UNSHALLOW, that commit is on the boundary edge.  The client has it, the server has it, but the client doesn't have its parents.  This is an excellent point to return the UNINTERESTING commit to PackWriter so it can use these trees and blobs as delta bases for the returned pack.

Above in the carrying logic it may seem odd that we add BOUNDARY to "c" when we are looking at "p", but its the right thing to do.  We can only tag a given commit as BOUNDARY once we discover its parent is at the edge.

To do all of this you need 2 extra flags in your DepthWalk.ObjectWalk.  You can allocate these using newFlag("BOUNDARY"), newFlag("UNSHALLOW").  Unfortunately you also need the unshallow set from UploadPack to be pushed down through here, and the whole thing is getting very specialized to the shallow clone case.  But I think that's OK, this stuff is really only useful for the shallow clone logic.