[RFC] Replace rebase with filtering

[RFC] Replace rebase with filtering

[Steven Grimm]

Blanket request, so I don't have to keep repeating it: Please correct me 
if I'm wrong about anything below. I'm more familiar with git than I was 
a month ago, but still not an expert, so I could be totally off (re)base 
here. With that note of confidence...

We have a setup like this:

    (external)
        |
   local master
        |
   integration
  /     |     \
dev1   dev2  dev3

We pull changes from the external repository (actually a Subversion 
repo) into a local master. The integration repo is a clone of that. 
That's our local setup, but the particulars don't matter here -- I'm 
just using it as an example.

Ideally, we'd rebase the integration area against changes pulled from 
master, then each dev repository would rebase against the changes from 
the integration area. That would keep our histories nice and clean as we 
pull changes down from the external repository.

But of course rebase will get confused and we'll end up re-applying 
changes in the dev sandboxes as soon as there are any existing change in 
the integration repo when we pull changes from master, because rebase 
will turn those existing changes into new revisions that don't match any 
previously known ones in the dev repositories.

So at the moment, as far as I can see, the only option is to use merge 
rather than rebase everywhere but the leaf nodes of our repository tree, 
and just live with the cluttered history. The developers will at least 
have clean *local* histories, but they'll be rebasing onto a cluttered 
history from the integration repo.

However, they may not want to, even if they can: as soon as I rebase, 
unless everyone is very careful, I have just prevented other developers 
from pulling my local commits into their local repositories before I've 
pushed my stuff up to the integration area. Sibling-to-sibling pulls  -- 
which I hope we all agree are a very useful feature of systems like git 
-- have exactly the same rebase problem as parent-to-child pulls: you'll 
end up re-applying the same changes if the target repo had an earlier 
version of a newly-rebased chain of commits. So even in our development 
repos, I suspect we'll want to avoid rebasing unless we're certain we 
won't ever need to share changes directly with each other, and just live 
with the clutter.

All of which made me think, gee, it'd sure be nice if there was a way to 
filter out those excess merges when we view our branch history. I think 
all it would take would be to mark a merge commit as a rebase-ish update 
(rather than an actual integration where the merge itself is an event 
that's important to us) and you could, if the user chose, discard those 
merges from views of the branch history.

And then it occurred to me: if we had that, would we actually need 
rebase at all? As far as I know, rebase is all about aesthetics, not 
functionality; the reason you rebase instead of merge is that you don't 
want to wade through zillions of irrelevant merges when you browse your 
project's history. But if those merges are simply not shown to you, it 
shouldn't matter that they exist. Yes, you will have more objects in 
your index, but with git's delta compression, you might not even notice 
the difference.

Rebase has an interesting undesirable property aside from messing up 
downstream clones when they try to pull your latest changes. Since 
rebase preserves the timestamps on your local commits, you almost always 
end up with a situation where the history says almost all your local 
commits happened before the commit they claim to have been branched 
from. That's not too big a problem in most cases, but it sure isn't very 
clean. The underlying problem is that when you rebase you lose not only 
the history of your intermediate updates, but also the history of your 
original branch creation.

Filtering rather than rewriting history would fix all of that. We could 
easily report that branch XYZ was forked from branch ABC on 01/03/2006 
and is up to date with all of ABC's changes up to 01/18/2006 (i.e., 
display information about the initial branch and the most recent update 
merge, but none of the ones in between.) The timestamps all make sense 
because you haven't lost the history. And if someone has cloned your 
repository, they can keep pulling updates without anything breaking.

It might also, be possible to implement an after-the-fact rebase to 
reduce the number of excess commits: a command that rebases all the 
update merges older than a certain age, on the theory that you can 
usually put an upper bound on how out-of-date someone's clone of your 
repo is allowed to get. That would rewrite just the ancient history, not 
touching anything recent, and would mark the newly-created revisions 
such that pull could skip fetching them if the target already has the 
more recent revisions. (The revision at which you stop rebasing should 
end up with the same revision ID as the one in the actual history, since 
the contents should match.) If that's not clear I can draw a picture. 
Haven't thought that bit through too much so it might not be feasible in 
the end, but it seems like in theory we have all the information we need 
to resolve conflicts, etc.

Comments? Am I fundamentally misunderstanding how rebase works and/or 
why the documentation warns people away from using it in repos that 
might be pulled from?

-Steve

Re: [RFC] Replace rebase with filtering

[Johannes Schindelin]

Hi,

On Mon, 15 Jan 2007, Steven Grimm wrote:

> Ideally, we'd rebase the integration area against changes pulled from 
> master, then each dev repository would rebase against the changes from 
> the integration area. That would keep our histories nice and clean as we 
> pull changes down from the external repository.
> 
> But of course rebase will get confused and we'll end up re-applying 
> changes in the dev sandboxes as soon as there are any existing change in 
> the integration repo when we pull changes from master, because rebase 
> will turn those existing changes into new revisions that don't match any 
> previously known ones in the dev repositories.

I had the impression that the use of "--ignore-if-in-upstream" in 
git-rebase avoids exactly this case: re-applying changes which are already 
in upstream.

Doesn't it work that way?

Ciao,
Dscho

Re: [RFC] Replace rebase with filtering

[Steven Grimm]

Johannes Schindelin wrote:
> I had the impression that the use of "--ignore-if-in-upstream" in 
> git-rebase avoids exactly this case: re-applying changes which are already 
> in upstream.
>
> Doesn't it work that way?
>   

Where's that option documented? The manpage makes no mention of it at all.

-Steve

Re: [RFC] Replace rebase with filtering

[Steven Grimm]

Steven Grimm wrote:
> Johannes Schindelin wrote:
>> I had the impression that the use of "--ignore-if-in-upstream" in 
>> git-rebase avoids exactly this case: re-applying changes which are 
>> already in upstream.  
> Where's that option documented? The manpage makes no mention of it at 
> all.

Ah, okay, poking around in the git-rebase source, I see you mean that 
git-format-patch is called with that option. Gotcha. The problem is that 
after a rebase, the revisions in question *aren't* in the upstream. 
Here's my understanding of why. Say I have this in my integration 
repository:

a---b---c---d (master)
 \
  e---f---g   (integration)

Now, I rebase the integration branch onto master:

a---b---c---d
             \
              e'---f'---g'

The problem is that, since e' contains all the changes in e *and* in 
b/c/d, it does not have the same SHA1 as the original e revision, nor in 
fact the same hash as any of the revisions in the pre-rebase tree. And 
after rebase succeeds, it wipes the original e, f, and g from the 
history of the integration branch.

When a clone fetches e', f', and g' from this repo and tries to rebase 
onto the integration branch, git-format-patch will think b, c, and d are 
new (correct) but also that e', f', and g' are new. Since they have 
previously unknown hashes and there's no record of the original e, f, 
and g or their relation to the new revisions -- at least, no record that 
gets pulled down to the clone when it fetches -- there's no way for 
git-format-patch to know that it has already applied those changes.

As always, correct me if I'm wrong -- that's my understanding of the 
problem with rebasing in a parent repository.

-Steve

Re: [RFC] Replace rebase with filtering

[Johannes Schindelin]

Hi,

On Tue, 16 Jan 2007, Steven Grimm wrote:

> Steven Grimm wrote:
> > Johannes Schindelin wrote:
> > > I had the impression that the use of "--ignore-if-in-upstream" in
> > > git-rebase avoids exactly this case: re-applying changes which are already
> > > in upstream.  
> > Where's that option documented? The manpage makes no mention of it at all.
> 
> Ah, okay, poking around in the git-rebase source, I see you mean that
> git-format-patch is called with that option. Gotcha. The problem is that after
> a rebase, the revisions in question *aren't* in the upstream. Here's my
> understanding of why. Say I have this in my integration repository:
> 
> a---b---c---d (master)
> \
>  e---f---g   (integration)
> 
> Now, I rebase the integration branch onto master:
> 
> a---b---c---d
>             \
>              e'---f'---g'
> 
> The problem is that, since e' contains all the changes in e *and* in 
> b/c/d, it does not have the same SHA1 as the original e revision, nor in 
> fact the same hash as any of the revisions in the pre-rebase tree. And 
> after rebase succeeds, it wipes the original e, f, and g from the 
> history of the integration branch.

That is correct, but --ignore-if-in-upstream actually tests the hash of 
the _diff_, not of the commit. So, if c really introduces the same change 
as f (i.e. the diffs are identical), git-rebase will ignore f:

a---b---c---d
             \
              e'---g'

Totally untested, of course. But this is what --ignore-if-in-upstream was 
written for.

Ciao,
Dscho

Re: [RFC] Replace rebase with filtering

[Steven Grimm]

Johannes Schindelin wrote:
> That is correct, but --ignore-if-in-upstream actually tests the hash of 
> the _diff_, not of the commit. So, if c really introduces the same change 
> as f (i.e. the diffs are identical), git-rebase will ignore f:
>
> a---b---c---d
>              \
>               e'---g'
>
> Totally untested, of course. But this is what --ignore-if-in-upstream was 
> written for.
>   

Okay, great, that is certainly an improvement over what I thought was 
happening. But it won't work if you had to manually resolve a conflict 
during the rebase, yes? In that case the diffs would presumably not match.

-Steve

Re: [RFC] Replace rebase with filtering

[Jakub Narebski]

Steven Grimm wrote:

> Johannes Schindelin wrote:
>> That is correct, but --ignore-if-in-upstream actually tests the hash of 
>> the _diff_, not of the commit. So, if c really introduces the same change 
>> as f (i.e. the diffs are identical), git-rebase will ignore f:
>>
>> a---b---c---d
>>              \
>>               e'---g'
>>
>> Totally untested, of course. But this is what --ignore-if-in-upstream was 
>> written for.
>>   
> 
> Okay, great, that is certainly an improvement over what I thought was 
> happening. But it won't work if you had to manually resolve a conflict 
> during the rebase, yes? In that case the diffs would presumably not match.

Then git-rerere would help, I think.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [RFC] Replace rebase with filtering

[Johannes Schindelin]

Hi,

On Tue, 16 Jan 2007, Steven Grimm wrote:

> Johannes Schindelin wrote:
> > That is correct, but --ignore-if-in-upstream actually tests the hash of the
> > _diff_, not of the commit. So, if c really introduces the same change as f
> > (i.e. the diffs are identical), git-rebase will ignore f:
> > 
> > a---b---c---d
> >              \
> >               e'---g'
> > 
> > Totally untested, of course. But this is what --ignore-if-in-upstream was
> > written for.
> >   
> 
> Okay, great, that is certainly an improvement over what I thought was
> happening. But it won't work if you had to manually resolve a conflict during
> the rebase, yes? In that case the diffs would presumably not match.

Correct. There is no automatic way any program could verify that such a 
patch is indeed what is already in upstream.

Usually, however, this results in a conflict which you have to resolve. 
And _you_ do not have a hard time verifying that the patch already went 
in, and you just say "git rebase --skip" and the rebasing will continue 
_without_ having committed the now obsolete patch.

Ciao,
Dscho

Re: [RFC] Replace rebase with filtering

[Shawn O. Pearce]

Jakub Narebski <jnareb@gmail.com> wrote:
> Steven Grimm wrote:
> > Okay, great, that is certainly an improvement over what I thought was 
> > happening. But it won't work if you had to manually resolve a conflict 
> > during the rebase, yes? In that case the diffs would presumably not match.
> 
> Then git-rerere would help, I think.

No, because rerere only helps to recall a prior conflict resolution.
Here Steven is talking about having rebase intelligently realize that
the upstream has accepted a patch, but did so by modifying it first.
There really isn't a solution to the problem.

pg tried to do this by applying several patches at once until
something matched.  If the upstream fixed a line like "a=b" to
be "a = b" then this would *never* match, and pg would abort.
StGIT runs the patches backwards.  A much smarter approach then
what pg tried to do, but again, "a = b" would never match.

-- 
Shawn.

Re: [RFC] Replace rebase with filtering

[Johannes Schindelin]

Hi,

On Tue, 16 Jan 2007, Jakub Narebski wrote:

> Steven Grimm wrote:
> 
> > Johannes Schindelin wrote:
> >> That is correct, but --ignore-if-in-upstream actually tests the hash of 
> >> the _diff_, not of the commit. So, if c really introduces the same change 
> >> as f (i.e. the diffs are identical), git-rebase will ignore f:
> >>
> >> a---b---c---d
> >>              \
> >>               e'---g'
> >>
> >> Totally untested, of course. But this is what --ignore-if-in-upstream was 
> >> written for.
> >>   
> > 
> > Okay, great, that is certainly an improvement over what I thought was 
> > happening. But it won't work if you had to manually resolve a conflict 
> > during the rebase, yes? In that case the diffs would presumably not match.
> 
> Then git-rerere would help, I think.

AFAICT no. First, git-rerere can only resolve conflicts for which it has 
seen a conflict resolution. Unlikely here.

Worse, the way git-rerere would _have_ to resolve the conflict, a commit 
would _fail_ (since no change should be committed if a munged version of 
it was already applied).

Ciao,
Dscho

Re: [RFC] Replace rebase with filtering

[Jakub Narebski]

Johannes Schindelin wrote:

> Usually, however, this results in a conflict which you have to resolve. 
> And _you_ do not have a hard time verifying that the patch already went 
> in, and you just say "git rebase --skip" and the rebasing will continue 
> _without_ having committed the now obsolete patch.

Unfortunately, at least with git 1.4.4.x, not quite. You have to have
index clean to do "git rebase --skip", while usually there would be
conflict when applying patch that is already present some deeper.

I think that is a bug in git-rebase.
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [RFC] Replace rebase with filtering

[Brian Gernhardt]

On Jan 16, 2007, at 4:49 PM, Jakub Narebski wrote:

> Johannes Schindelin wrote:
>
>> Usually, however, this results in a conflict which you have to  
>> resolve.
>> And _you_ do not have a hard time verifying that the patch already  
>> went
>> in, and you just say "git rebase --skip" and the rebasing will  
>> continue
>> _without_ having committed the now obsolete patch.
>
> Unfortunately, at least with git 1.4.4.x, not quite. You have to have
> index clean to do "git rebase --skip", while usually there would be
> conflict when applying patch that is already present some deeper.
>
> I think that is a bug in git-rebase.

Agreed.  I tend to "git checkout HEAD -- files" before a "git rebase  
--skip" to fix that, although I guess "git reset --hard" would work  
just the same.  But by saying "--skip" means "these changes are  
irrelevant", so it should clean up after itself.  It's a definite  
usability snafu.

I'd put a simple patch to add the reset to git-merge.sh, but I'm not  
sure I understand what --skip is doing in there with a 30 second  
peek.  Maybe if I get more tuits, I'll do it, but someone more  
familiar with it can probably do it much faster (and be more certain  
it's the right thing to do).

~~ Brian

Re: [RFC] Replace rebase with filtering

[Johannes Schindelin]

Hi,

On Tue, 16 Jan 2007, Brian Gernhardt wrote:

> I'd put a simple patch to add the reset to git-merge.sh, but I'm not sure I
> understand what --skip is doing in there with a 30 second peek.

Better put "git reset --hard" into git-rebase.sh... Just search for 
"--skip" and you will find where it has to go.

> Maybe if I get more tuits, I'll do it, but someone more familiar with it 
> can probably do it much faster (and be more certain it's the right thing 
> to do).

But if _you_ do it, you gain knowledge about git!

Ciao,
Dscho

Re: [RFC] Replace rebase with filtering

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

>> I'd put a simple patch to add the reset to git-merge.sh, but I'm not sure I
>> understand what --skip is doing in there with a 30 second peek.
>
> Better put "git reset --hard" into git-rebase.sh... Just search for 
> "--skip" and you will find where it has to go.

I'd later want to allow starting rebase from a dirty working
tree as long as the rebasing of the entire series would not
conflict with the local changes, so I would seriously prefer a
solution without "reset --hard".

Re: [RFC] Replace rebase with filtering

[Johannes Schindelin]

Hi,

On Tue, 16 Jan 2007, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> >> I'd put a simple patch to add the reset to git-merge.sh, but I'm not sure I
> >> understand what --skip is doing in there with a 30 second peek.
> >
> > Better put "git reset --hard" into git-rebase.sh... Just search for 
> > "--skip" and you will find where it has to go.
> 
> I'd later want to allow starting rebase from a dirty working
> tree as long as the rebasing of the entire series would not
> conflict with the local changes, so I would seriously prefer a
> solution without "reset --hard".

Fair enough.

Ciao,
Dscho

Re: [RFC] Replace rebase with filtering

[Steven Grimm]

  Johannes Schindelin wrote:
>> Okay, great, that is certainly an improvement over what I thought was
>> happening. But it won't work if you had to manually resolve a conflict during
>> the rebase, yes? In that case the diffs would presumably not match.
>>     
> Correct. There is no automatic way any program could verify that such a 
> patch is indeed what is already in upstream.
>   

Well, yes there is, in fact: don't forget the existing history like 
rebase currently does. Merge doesn't have the same problem. That's kind 
of the crux of what I'm proposing here: if you change the implementation 
of git's "Don't clutter my history with meaningless merges" feature from 
a history-lossy operation (rebase as it stands today) to a display-time 
filter (regular merge with an added "I'm just an update" marker) then 
this problem evaporates and it becomes safe to clone *any* repository 
and pull updates from it, not just ones where the owner is being careful 
never to run rebase when there are pending changes.

I think filtering is consistent with the way git does other things. 
Renames would be the big example; they are detected after the fact and 
dealt with at the point where they're actually relevant to what the user 
is doing (merging, etc.) rather than appearing as an explicit part of 
the repository's history. Why shouldn't no-op "sync with upstream" 
changes work the same way?

> Usually, however, this results in a conflict which you have to resolve. 
> And _you_ do not have a hard time verifying that the patch already went 
> in, and you just say "git rebase --skip" and the rebasing will continue 
> _without_ having committed the now obsolete patch.
>   

True enough, but if the computer can retain the information it needs to 
do that for me (which it does if I merge instead of rebase) then why 
shouldn't it?

-Steve