bug?: stgit creates (unneccessary?) conflicts when pulling

bug?: stgit creates (unneccessary?) conflicts when pulling

[Karl Hasselström]

If I make a patch series where more than one patch touches the same
line, I get a lot of merge errors when upstream has accepted them and
I try to merge them back.

Suppose a line contained the string "0". Patch p1 changes that to "1",
patch p2 further changes that to "2". Upstream accept the patches, and
I later "stg pull" them. When reapplying p1 after the pull, stg
generates a merge conflict since upstream changed the "0" to "2" and
p1 changes the "0" to "1".

This situation arises for every line that's modified in more than one
patch, and for every such patch except the last one. And it's really
annoying, since it's intuitively obvious that there aren't actually
any conflicts, since upstream accepted my patches verbatim.

I suppose one way to fix it manually would be to first fetch, glance
at the new upstream commits and try to find any accepted patches, and
then "stg pull" the commit corresponding to the earliest patch in my
series; repeat for every patch in the series. The queston is, how can
we automate it?

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Sam Vilain]

Karl Hasselström wrote:
> If I make a patch series where more than one patch touches the same
> line, I get a lot of merge errors when upstream has accepted them and
> I try to merge them back.
> 
> Suppose a line contained the string "0". Patch p1 changes that to "1",
> patch p2 further changes that to "2". Upstream accept the patches, and
> I later "stg pull" them. When reapplying p1 after the pull, stg
> generates a merge conflict since upstream changed the "0" to "2" and
> p1 changes the "0" to "1".
> 
> This situation arises for every line that's modified in more than one
> patch, and for every such patch except the last one. And it's really
> annoying, since it's intuitively obvious that there aren't actually
> any conflicts, since upstream accepted my patches verbatim.
> 
> I suppose one way to fix it manually would be to first fetch, glance
> at the new upstream commits and try to find any accepted patches, and
> then "stg pull" the commit corresponding to the earliest patch in my
> series; repeat for every patch in the series. The queston is, how can
> we automate it?

I don't seem to suffer from this, using my "diff3 || 
ediff-merge-files-with-ancestor" script as a merge tool.  The diff3, or 
ediff, seem to DTRT so long as the change is cleanly applied.  Otherwise 
I just get a merge conflict difference and I just press A/B to pick 
which one I want.

Sam.

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

Karl Hasselström wrote:
> If I make a patch series where more than one patch touches the same
> line, I get a lot of merge errors when upstream has accepted them and
> I try to merge them back.

We discussed about this in the thread announcing pg
(http://article.gmane.org/gmane.comp.version-control.git/16247). This is
not easy to fix because StGIT pushes patches one by one and it stops at
the first conflict. Pg was trying to merge two patches at once but this
is not suitable for StGIT since the latter keeps the patches as single
commits.

There is another problem - the same line might have been modified by a
third-party patch merged into the kernel (and the conflict solved by the
maintainer).

> This situation arises for every line that's modified in more than one
> patch, and for every such patch except the last one. And it's really
> annoying, since it's intuitively obvious that there aren't actually
> any conflicts, since upstream accepted my patches verbatim.

Because I found the same situation a bit annoying, I added the --reset
option to resolved. If you know your patch was merged without
modifications, just use "stg resolved --all --reset local".

An idea (untested, I don't even know whether it's feasible) would be to
check which patches were merged by reverse-applying them starting with
the last. In this situation, all the merged patches should just revert
their changes. You only need to do a git-diff between the bottom and the
top of the patch and git-apply the output (maybe without even modifying
the tree). If this operation succeeds, the patch was integrated and you
don't even need to push it. The tool could even fold two consecutive
patches and reverse-apply them. The disadvantage might be the delay when
pushing patches but we could enable this test only if an option is
passed to the pull command.

If you really want to make StGIT behave intelligently, have a look at
the patch commuting theory in Darcs. It tends to handle this kind of
conflicts easily. StGIT also does some patch commuting but using the
diff3 algorithm and asks the user to fix different conflicts.

Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

[-- Attachment #1: Type: text/plain, Size: 833 bytes --]

On 27/02/06, Catalin Marinas <catalin.marinas@gmail.com> wrote:
> An idea (untested, I don't even know whether it's feasible) would be to
> check which patches were merged by reverse-applying them starting with
> the last. In this situation, all the merged patches should just revert
> their changes. You only need to do a git-diff between the bottom and the
> top of the patch and git-apply the output (maybe without even modifying
> the tree). If this operation succeeds, the patch was integrated and you
> don't even need to push it.

I tried some simple tests with the idea above. I attached a patch if
you'd like to try (I won't push it to the main StGIT repository yet.
For safety reasons, it only skips the merged patches when pushing
them. A future version could simply delete the merged patches.

--
Catalin

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: merged-test.diff --]
[-- Type: text/x-patch; name="merged-test.diff", Size: 5189 bytes --]

Add a merged upstream test for pull and push

From: Catalin Marinas <catalin.marinas@gmail.com>

This patch adds the --merged option to both pull and push commands. With
this option, these commands will first try to check which patches were
merged upstream by reverse-applying them in reverse order. This should
solve the situation where several patches modify the same line in a file.

Signed-off-by: Catalin Marinas <catalin.marinas@gmail.com>
---

 stgit/commands/pull.py |   20 +++++++++++++++++++-
 stgit/commands/push.py |   17 ++++++++++++++++-
 stgit/git.py           |   12 +++++++++---
 stgit/stack.py         |   20 ++++++++++++++++++++
 4 files changed, 64 insertions(+), 5 deletions(-)

diff --git a/stgit/commands/pull.py b/stgit/commands/pull.py
index 843b579..5d75530 100644
--- a/stgit/commands/pull.py
+++ b/stgit/commands/pull.py
@@ -39,6 +39,9 @@ format."""
 
 options = [make_option('-n', '--nopush',
                        help = 'do not push the patches back after pulling',
+                       action = 'store_true'),
+           make_option('-m', '--merged',
+                       help = 'check for patches merged upstream (slower)',
                        action = 'store_true')]
 
 def func(parser, options, args):
@@ -77,12 +80,27 @@ def func(parser, options, args):
     # push the patches back
     if options.nopush:
         applied = []
+
+    # check for patches merged upstream
+    if options.merged:
+        merged = crt_series.merged_patches(patches)
+    else:
+        merged = []
+
     for p in applied:
+        if p in merged:
+            print 'Patch "%s" merged upstream' % p
+            continue
+
         print 'Pushing patch "%s"...' % p,
         sys.stdout.flush()
-        crt_series.push_patch(p)
+
+        modified = crt_series.push_patch(p)
+
         if crt_series.empty_patch(p):
             print 'done (empty patch)'
+        elif modified:
+            print 'done (modified)'
         else:
             print 'done'
 
diff --git a/stgit/commands/push.py b/stgit/commands/push.py
index 9924a78..72b2663 100644
--- a/stgit/commands/push.py
+++ b/stgit/commands/push.py
@@ -49,6 +49,9 @@ options = [make_option('-a', '--all',
            make_option('--reverse',
                        help = 'push the patches in reverse order',
                        action = 'store_true'),
+           make_option('-m', '--merged',
+                       help = 'check for patches merged upstream (slower)',
+                       action = 'store_true'),
            make_option('--undo',
                        help = 'undo the last push operation',
                        action = 'store_true')]
@@ -134,9 +137,21 @@ def func(parser, options, args):
     elif forwarded == 1:
         print 'Fast-forwarded patch "%s"' % patches[0]
 
-    for p in patches[forwarded:]:
+    patches = patches[forwarded:]
+
+    # check for patches merged upstream
+    if options.merged:
+        merged = crt_series.merged_patches(patches)
+    else:
+        merged = []
+
+    for p in patches:
         is_patch_appliable(p)
 
+        if p in merged:
+            print 'Patch "%s" merged upstream' % p
+            continue
+
         print 'Pushing patch "%s"...' % p,
         sys.stdout.flush()
 
diff --git a/stgit/git.py b/stgit/git.py
index 016bc3a..66b8612 100644
--- a/stgit/git.py
+++ b/stgit/git.py
@@ -462,14 +462,20 @@ def commit(message, files = None, parent
 
     return commit_id
 
-def apply_diff(rev1, rev2):
+def apply_diff(rev1, rev2, check_index = True):
     """Apply the diff between rev1 and rev2 onto the current
     index. This function doesn't need to raise an exception since it
     is only used for fast-pushing a patch. If this operation fails,
     the pushing would fall back to the three-way merge.
     """
-    return os.system('git-diff-tree -p %s %s | git-apply --index 2> /dev/null'
-                     % (rev1, rev2)) == 0
+    if check_index:
+        index_opt = '--index'
+    else:
+        index_opt = ''
+    cmd = 'git-diff-tree -p %s %s | git-apply %s 2> /dev/null' \
+          % (rev1, rev2, index_opt)
+
+    return os.system(cmd) == 0
 
 def merge(base, head1, head2):
     """Perform a 3-way merge between base, head1 and head2 into the
diff --git a/stgit/stack.py b/stgit/stack.py
index e1c55f0..9d5f043 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -780,6 +780,26 @@ class Series:
 
         return forwarded
 
+    def merged_patches(self, names):
+        """Test which patches were merged upstream by reverse-applying
+        them in reverse order. The function returns the list of
+        patches detected to have been applied. The state of the tree
+        is restored to the original one
+        """
+        patches = [Patch(name, self.__patch_dir, self.__refs_dir)
+                   for name in names]
+        patches.reverse()
+
+        merged = []
+        for p in patches:
+            if git.apply_diff(p.get_top(), p.get_bottom(), False):
+                merged.append(p.get_name())
+        merged.reverse()
+
+        git.reset()
+
+        return merged
+
     def push_patch(self, name):
         """Pushes a patch on the stack
         """

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

On 28/02/06, Catalin Marinas <catalin.marinas@gmail.com> wrote:
> On 27/02/06, Catalin Marinas <catalin.marinas@gmail.com> wrote:
> > An idea (untested, I don't even know whether it's feasible) would be to
> > check which patches were merged by reverse-applying them starting with
> > the last. In this situation, all the merged patches should just revert
> > their changes. You only need to do a git-diff between the bottom and the
> > top of the patch and git-apply the output (maybe without even modifying
> > the tree). If this operation succeeds, the patch was integrated and you
> > don't even need to push it.
>
> I tried some simple tests with the idea above. I attached a patch if
> you'd like to try (I won't push it to the main StGIT repository yet.
> For safety reasons, it only skips the merged patches when pushing
> them. A future version could simply delete the merged patches.

Don't bother trying this patch. I just found a bug with git.reset()
and the caching of the git.__head variable. I'll post another patch in
a few hours.

--
Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

[-- Attachment #1: Type: text/plain, Size: 888 bytes --]

On 27/02/06, Catalin Marinas <catalin.marinas@gmail.com> wrote:
> An idea (untested, I don't even know whether it's feasible) would be to
> check which patches were merged by reverse-applying them starting with
> the last. In this situation, all the merged patches should just revert
> their changes. You only need to do a git-diff between the bottom and the
> top of the patch and git-apply the output (maybe without even modifying
> the tree). If this operation succeeds, the patch was integrated and you
> don't even need to push it.

I attached another patch that should work properly. It also pushes
empty patches on the stack if they were merged upstream (a 'stg clean'
is required to remove them). This is useful for the push --undo
command if you are not happy with the result.

I'll try this patch for a bit more before pushing into the repository.

--
Catalin

[-- Attachment #2: merged-test.diff --]
[-- Type: text/x-patch, Size: 8706 bytes --]

Add a merged upstream test for pull and push

From: Catalin Marinas <catalin.marinas@gmail.com>

This patch adds the --merged option to both pull and push commands. With
this option, these commands will first try to check which patches were
merged upstream by reverse-applying them in reverse order. This should
solve the situation where several patches modify the same line in a file.

Signed-off-by: Catalin Marinas <catalin.marinas@gmail.com>
---

 stgit/commands/common.py |   41 +++++++++++++++++++++++++++++++++++++++++
 stgit/commands/pull.py   |   15 +++++----------
 stgit/commands/push.py   |   28 ++++++----------------------
 stgit/git.py             |   12 +++++++++---
 stgit/stack.py           |   34 +++++++++++++++++++++++++++++++---
 5 files changed, 92 insertions(+), 38 deletions(-)

diff --git a/stgit/commands/common.py b/stgit/commands/common.py
index 2e1ba7a..2985379 100644
--- a/stgit/commands/common.py
+++ b/stgit/commands/common.py
@@ -132,6 +132,47 @@ def resolved_all(reset = None):
             resolved(filename, reset)
         os.remove(os.path.join(git.get_base_dir(), 'conflicts'))
 
+def push_patches(patches, check_merged = False):
+    """Push multiple patches onto the stack. This function is shared
+    between the push and pull commands
+    """
+    forwarded = crt_series.forward_patches(patches)
+    if forwarded > 1:
+        print 'Fast-forwarded patches "%s" - "%s"' % (patches[0],
+                                                      patches[forwarded - 1])
+    elif forwarded == 1:
+        print 'Fast-forwarded patch "%s"' % patches[0]
+
+    names = patches[forwarded:]
+
+    # check for patches merged upstream
+    if check_merged:
+        print 'Checking for patches merged upstream...',
+        sys.stdout.flush()
+
+        merged = crt_series.merged_patches(names)
+
+        print 'done (%d found)' % len(merged)
+    else:
+        merged = []
+
+    for p in names:
+        print 'Pushing patch "%s"...' % p,
+        sys.stdout.flush()
+
+        if p in merged:
+            crt_series.push_patch(p, empty = True)
+            print 'done (merged upstream)'
+        else:
+            modified = crt_series.push_patch(p)
+
+            if crt_series.empty_patch(p):
+                print 'done (empty patch)'
+            elif modified:
+                print 'done (modified)'
+            else:
+                print 'done'
+
 def name_email(address):
     """Return a tuple consisting of the name and email parsed from a
     standard 'name <email>' string
diff --git a/stgit/commands/pull.py b/stgit/commands/pull.py
index 843b579..8f26f4d 100644
--- a/stgit/commands/pull.py
+++ b/stgit/commands/pull.py
@@ -39,6 +39,9 @@ format."""
 
 options = [make_option('-n', '--nopush',
                        help = 'do not push the patches back after pulling',
+                       action = 'store_true'),
+           make_option('-m', '--merged',
+                       help = 'check for patches merged upstream',
                        action = 'store_true')]
 
 def func(parser, options, args):
@@ -75,15 +78,7 @@ def func(parser, options, args):
     print 'done'
 
     # push the patches back
-    if options.nopush:
-        applied = []
-    for p in applied:
-        print 'Pushing patch "%s"...' % p,
-        sys.stdout.flush()
-        crt_series.push_patch(p)
-        if crt_series.empty_patch(p):
-            print 'done (empty patch)'
-        else:
-            print 'done'
+    if not options.nopush:
+        push_patches(applied, options.merged)
 
     print_crt_patch()
diff --git a/stgit/commands/push.py b/stgit/commands/push.py
index 9924a78..90777c1 100644
--- a/stgit/commands/push.py
+++ b/stgit/commands/push.py
@@ -49,6 +49,9 @@ options = [make_option('-a', '--all',
            make_option('--reverse',
                        help = 'push the patches in reverse order',
                        action = 'store_true'),
+           make_option('-m', '--merged',
+                       help = 'check for patches merged upstream',
+                       action = 'store_true'),
            make_option('--undo',
                        help = 'undo the last push operation',
                        action = 'store_true')]
@@ -58,9 +61,9 @@ def is_patch_appliable(p):
     """See if patch exists, or is already applied.
     """
     if p in applied:
-        raise CmdException, 'Patch "%s" is already applied.' % p
+        raise CmdException, 'Patch "%s" is already applied' % p
     if p not in unapplied:
-        raise CmdException, 'Patch "%s" does not exist.' % p
+        raise CmdException, 'Patch "%s" does not exist' % p
 
 def func(parser, options, args):
     """Pushes the given patch or all onto the series
@@ -127,25 +130,6 @@ def func(parser, options, args):
     if options.reverse:
         patches.reverse()
 
-    forwarded = crt_series.forward_patches(patches)
-    if forwarded > 1:
-        print 'Fast-forwarded patches "%s" - "%s"' % (patches[0],
-                                                      patches[forwarded - 1])
-    elif forwarded == 1:
-        print 'Fast-forwarded patch "%s"' % patches[0]
-
-    for p in patches[forwarded:]:
-        is_patch_appliable(p)
-
-        print 'Pushing patch "%s"...' % p,
-        sys.stdout.flush()
+    push_patches(patches, options.merged)
 
-        modified = crt_series.push_patch(p)
-
-        if crt_series.empty_patch(p):
-            print 'done (empty patch)'
-        elif modified:
-            print 'done (modified)'
-        else:
-            print 'done'
     print_crt_patch()
diff --git a/stgit/git.py b/stgit/git.py
index a3488ff..40d54ef 100644
--- a/stgit/git.py
+++ b/stgit/git.py
@@ -465,14 +465,20 @@ def commit(message, files = None, parent
 
     return commit_id
 
-def apply_diff(rev1, rev2):
+def apply_diff(rev1, rev2, check_index = True):
     """Apply the diff between rev1 and rev2 onto the current
     index. This function doesn't need to raise an exception since it
     is only used for fast-pushing a patch. If this operation fails,
     the pushing would fall back to the three-way merge.
     """
-    return os.system('git-diff-tree -p %s %s | git-apply --index 2> /dev/null'
-                     % (rev1, rev2)) == 0
+    if check_index:
+        index_opt = '--index'
+    else:
+        index_opt = ''
+    cmd = 'git-diff-tree -p %s %s | git-apply %s 2> /dev/null' \
+          % (rev1, rev2, index_opt)
+
+    return os.system(cmd) == 0
 
 def merge(base, head1, head2):
     """Perform a 3-way merge between base, head1 and head2 into the
diff --git a/stgit/stack.py b/stgit/stack.py
index e1c55f0..165b5a7 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -780,7 +780,27 @@ class Series:
 
         return forwarded
 
-    def push_patch(self, name):
+    def merged_patches(self, names):
+        """Test which patches were merged upstream by reverse-applying
+        them in reverse order. The function returns the list of
+        patches detected to have been applied. The state of the tree
+        is restored to the original one
+        """
+        patches = [Patch(name, self.__patch_dir, self.__refs_dir)
+                   for name in names]
+        patches.reverse()
+
+        merged = []
+        for p in patches:
+            if git.apply_diff(p.get_top(), p.get_bottom(), False):
+                merged.append(p.get_name())
+        merged.reverse()
+
+        git.reset()
+
+        return merged
+
+    def push_patch(self, name, empty = False):
         """Pushes a patch on the stack
         """
         unapplied = self.get_unapplied()
@@ -798,7 +818,15 @@ class Series:
         modified = False
 
         # top != bottom always since we have a commit for each patch
-        if head == bottom:
+        if empty:
+            # just make an empty patch (top = bottom = HEAD). This
+            # option is useful to allow undoing already merged
+            # patches. The top is updated by refresh_patch since we
+            # need an empty commit
+            patch.set_bottom(head, backup = True)
+            patch.set_top(head, backup = True)
+            modified = True
+        elif head == bottom:
             # reset the backup information
             patch.set_bottom(bottom, backup = True)
             patch.set_top(top, backup = True)
@@ -835,7 +863,7 @@ class Series:
         self.__set_current(name)
 
         # head == bottom case doesn't need to refresh the patch
-        if head != bottom:
+        if empty or head != bottom:
             if not ex:
                 # if the merge was OK and no conflicts, just refresh the patch
                 # The GIT cache was already updated by the merge operation

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Chuck Lever]

[-- Attachment #1: Type: text/plain, Size: 1528 bytes --]

Catalin Marinas wrote:
> On 27/02/06, Catalin Marinas <catalin.marinas@gmail.com> wrote:
> 
>>An idea (untested, I don't even know whether it's feasible) would be to
>>check which patches were merged by reverse-applying them starting with
>>the last. In this situation, all the merged patches should just revert
>>their changes. You only need to do a git-diff between the bottom and the
>>top of the patch and git-apply the output (maybe without even modifying
>>the tree). If this operation succeeds, the patch was integrated and you
>>don't even need to push it.
> 
> 
> I attached another patch that should work properly. It also pushes
> empty patches on the stack if they were merged upstream (a 'stg clean'
> is required to remove them). This is useful for the push --undo
> command if you are not happy with the result.
> 
> I'll try this patch for a bit more before pushing into the repository.

i think this is a cool idea.  but it seems still to require a bit of 
convention on the part of the maintainer.

if maintainer X takes a patch "a" from developer Y, but modifies patch 
"a" before committing it, then your nifty automated mechanism will still 
have trouble merging developer Y's stack when Y pulls again.

the convention might be that maintainers who accept patches will always 
accept exactly what was sent, and then immediately apply another commit 
that addresses any issues they have with the original commit.  this is 
also a good idea so that the history contains the exact attribution of 
each change.

[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 451 bytes --]

begin:vcard
fn:Chuck Lever
n:Lever;Charles
org:Network Appliance, Incorporated;Open Source NFS Client Development
adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA
email;internet:cel@citi.umich.edu
title:Member of Technical Staff
tel;work:+1 734 763-4415
tel;fax:+1 734 763 4434
tel;home:+1 734 668-1089
x-mozilla-html:FALSE
url:http://troy.citi.umich.edu/u/cel/
version:2.1
end:vcard

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

On 01/03/06, Chuck Lever <cel@citi.umich.edu> wrote:
> Catalin Marinas wrote:
> > I attached another patch that should work properly. It also pushes
> > empty patches on the stack if they were merged upstream (a 'stg clean'
> > is required to remove them). This is useful for the push --undo
> > command if you are not happy with the result.
>
> if maintainer X takes a patch "a" from developer Y, but modifies patch
> "a" before committing it, then your nifty automated mechanism will still
> have trouble merging developer Y's stack when Y pulls again.
>
> the convention might be that maintainers who accept patches will always
> accept exactly what was sent, and then immediately apply another commit
> that addresses any issues they have with the original commit.

This won't solve the problem since testing whether patch "a" was
merged upstream will fail because its reverse won't apply cleanly onto
the upstream HEAD. Of course, you can try combination of upstream
commits and local patches but it's not really feasible.

As I said, this method doesn't solve all the upstream merge situations
but it is OK for most of them.

--
Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Karl Hasselström]

On 2006-03-01 17:53:53 +0000, Catalin Marinas wrote:

> This won't solve the problem since testing whether patch "a" was
> merged upstream will fail because its reverse won't apply cleanly
> onto the upstream HEAD. Of course, you can try combination of
> upstream commits and local patches but it's not really feasible.
>
> As I said, this method doesn't solve all the upstream merge
> situations but it is OK for most of them.

We could perhaps do a little better. Instead of just noting whether
the patch vanishes when reverse-applied, save the top and bottom of
the patch as reverse-applied, and then replace the patch with the
reverse of that. If the patch vanishes, this does what your patch does
right now. If the patch does not vanish, all that remains is the parts
that upstream didn't accept. (And as before, if the patch didn't
reverse-apply cleanly, assume upstream hasn't accepted it at all yet.)

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

Karl Hasselström wrote:
> We could perhaps do a little better. Instead of just noting whether
> the patch vanishes when reverse-applied, save the top and bottom of
> the patch as reverse-applied, and then replace the patch with the
> reverse of that. If the patch vanishes, this does what your patch does
> right now. If the patch does not vanish, all that remains is the parts
> that upstream didn't accept. (And as before, if the patch didn't
> reverse-apply cleanly, assume upstream hasn't accepted it at all yet.)

I don't fully understand this. If a patch reverse-applies cleanly, it
means that it was fully merged upstream. If it wasn't fully merged,
direct applying would fail and we should fall back to a three-way merge.
I'm not sure whether the latter would cause conflicts or not. The
disadvantage would be more time spent with trying two types of merges.

Anyway, I'll push the current patch but remain open to improvements. If
you get something working with your idea, please post a patch.

Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Karl Hasselström]

On 2006-02-28 22:45:56 +0000, Catalin Marinas wrote:

> On 27/02/06, Catalin Marinas <catalin.marinas@gmail.com> wrote:
>
> > An idea (untested, I don't even know whether it's feasible) would
> > be to check which patches were merged by reverse-applying them
> > starting with the last. In this situation, all the merged patches
> > should just revert their changes. You only need to do a git-diff
> > between the bottom and the top of the patch and git-apply the
> > output (maybe without even modifying the tree). If this operation
> > succeeds, the patch was integrated and you don't even need to push
> > it.
>
> I attached another patch that should work properly. It also pushes
> empty patches on the stack if they were merged upstream (a 'stg
> clean' is required to remove them). This is useful for the push
> --undo command if you are not happy with the result.
>
> I'll try this patch for a bit more before pushing into the
> repository.

It appears to work for me. I still had to fix things up manually when
pulling the uncommit patch though, since you had made a minor change
in "uncommit.py":

  Pushing patch "uncommit"...Error: File "stgit/commands/uncommit.py" added in branches but different

Is there a way to make stgit not fall on its face when faced with this
situation? Surely it ought to be possible to create a merged file with
conflict markers? (I realize this is harder when there is no common
ancestor, but these files are 95% identical!)

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

Karl Hasselström wrote:
> On 2006-02-28 22:45:56 +0000, Catalin Marinas wrote:
>>I attached another patch that should work properly. It also pushes
>>empty patches on the stack if they were merged upstream (a 'stg
>>clean' is required to remove them). This is useful for the push
>>--undo command if you are not happy with the result.
> 
> It appears to work for me. I still had to fix things up manually when
> pulling the uncommit patch though, since you had made a minor change
> in "uncommit.py":
> 
>   Pushing patch "uncommit"...Error: File "stgit/commands/uncommit.py" added in branches but different

Yes, I made some minor modifications (one of them was the copyright).

> Is there a way to make stgit not fall on its face when faced with this
> situation? Surely it ought to be possible to create a merged file with
> conflict markers? (I realize this is harder when there is no common
> ancestor, but these files are 95% identical!)

I've been thinking about this but it's not straight-forward. I tried
using /dev/null as the common ancestor but both diff3 and wiggle put the
whole file text in the conflict regions. These tools are not smart
enough to compare the conflict regions and reduce them.

Another approach would be to have a script that creates the common
ancestor only with the common lines between the two files and pass this
file as an argument to diff3. This wouldn't probably be that difficult,
maybe some combination of diff and sed and apply the result to one of
the files to remove the diff'ed lines.

Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Shawn Pearce]

Karl Hasselstr?m <kha@treskal.com> wrote:
> If I make a patch series where more than one patch touches the same
> line, I get a lot of merge errors when upstream has accepted them and
> I try to merge them back.
> 
> Suppose a line contained the string "0". Patch p1 changes that to "1",
> patch p2 further changes that to "2". Upstream accept the patches, and
> I later "stg pull" them. When reapplying p1 after the pull, stg
> generates a merge conflict since upstream changed the "0" to "2" and
> p1 changes the "0" to "1".

You should look at pg:

  http://www.spearce.org/2006/02/pg-version-0111-released.html

It has some of the features of StGIT and it (at least partially)
solves this problem.

Assume you had a patch stack of:

	PatchA : Change 0 to a 1
	PatchB : Change 1 to a 2
	PatchC : Change 2 to a 3

with each affecting the same line of the same file.

When pg grabs its (possibly remote) parent ("stg pull" aka pg-rebase)
we try to push down PatchA.  If PatchA fails to push cleanly we'll
pop it off and try to push PatchA + PatchB.  If that pushes cleanly
then we fold the content of PatchA into PatchB, effectively making
PatchA part of PatchB.  If PatchA + PatchB failed to push down
cleanly then we pop both and retry pushing PatchA + PatchB + PatchC.
If that pushes down cleanly then we make PatchA and PatchB officially
part of PatchC.

This required some ``hacks'' in pg-push.  Basically if we are
doing a non-fastforward push (as there are new commits we must
merge on top of) we run an external diff/patch to apply the change.
If that fails we reset the tree back to a clean state and try again.
Whenever patch rejects a hunk we examine the hunk to see if it is
already applied to the target file; if it is already applied we
skip the hunk.  If all hunks applied cleanly and/or are already
applied we accept the patch (or combination of patches) as merging
cleanly. Yea, its not very pretty.  But it works!

Where it falls down is if the upstream accepts all three of your
patches but then changes the line from a 3 to a 4.  pg won't look
at the GIT commit history to detect that the upstream accepted your
final change (PatchC) but then overwrite it with a newer change
(3->4).  I have thought about trying to implement this but the
current environment where I am using pg wouldn't benefit from it,
so it has not been high on my priority list.

-- 
Shawn.

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

Shawn Pearce <spearce@spearce.org> wrote:
> Karl Hasselstr?m <kha@treskal.com> wrote:
>> If I make a patch series where more than one patch touches the same
>> line, I get a lot of merge errors when upstream has accepted them and
>> I try to merge them back.
>
> When pg grabs its (possibly remote) parent ("stg pull" aka pg-rebase)
> we try to push down PatchA.  If PatchA fails to push cleanly we'll
> pop it off and try to push PatchA + PatchB.  If that pushes cleanly
> then we fold the content of PatchA into PatchB, effectively making
> PatchA part of PatchB.  If PatchA + PatchB failed to push down
> cleanly then we pop both and retry pushing PatchA + PatchB + PatchC.

How do you solve the situation where only PatchA, PatchC and PatchE
were merged, B and D still pending? Trying combinations of patches is
not a good idea.

As I said, if you have a big number of patches this might be pretty
slow. Have a look at my patch for trying the reversed patches in
reverse order. It seems to solve this problem for most of the
cases. There are cases when this method would fail like adjacent
changes made by third-party patches that break the context of the git
patches and git-apply would fail. An addition to this would be to try
a diff3 merge with the reversed patch but I don't think it's worth
since it would become much slower.

> If that pushes down cleanly then we make PatchA and PatchB officially
> part of PatchC.

I don't agree with this. For example, patches A, B and C change the
same line in file1 but patch A also changes file2 and patch B changed
file3. With your approach, merging A+B+C succeeds and you make A and B
part of C and hence move the changed to file2 and file3 in patch C.

The above can happen when the maintainer only merges part of the patch
or simply decides to merge patch C only and manually solve the
conflict in file1 (since patch C is based on the context from patches
A+B).

-- 
Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Shawn Pearce]

[Side Note: I've suddenly stopped receiving mail from vger.
 Even majordomo isn't replying to my pleas for help.  Arggh!
 Yet all other incoming email seems to be fine.]

Catalin Marinas <catalin.marinas@arm.com> wrote:
> Shawn Pearce <spearce@spearce.org> wrote:
> > Karl Hasselstr?m <kha@treskal.com> wrote:
> >> If I make a patch series where more than one patch touches the same
> >> line, I get a lot of merge errors when upstream has accepted them and
> >> I try to merge them back.
> >
> > When pg grabs its (possibly remote) parent ("stg pull" aka pg-rebase)
> > we try to push down PatchA.  If PatchA fails to push cleanly we'll
> > pop it off and try to push PatchA + PatchB.  If that pushes cleanly
> > then we fold the content of PatchA into PatchB, effectively making
> > PatchA part of PatchB.  If PatchA + PatchB failed to push down
> > cleanly then we pop both and retry pushing PatchA + PatchB + PatchC.
> 
> How do you solve the situation where only PatchA, PatchC and PatchE
> were merged, B and D still pending? Trying combinations of patches is
> not a good idea.

Yea, ouch.  pg would fold everything into E, destroying the B
and D boundary.  A (not so good) workaround right now would be to
undo the rebase, pop all patches, rebase, then push one by one.
I didn't even consider this case as its not my workflow style:
at least not right now.

> As I said, if you have a big number of patches this might be pretty
> slow. Have a look at my patch for trying the reversed patches in
> reverse order. It seems to solve this problem for most of the
> cases. There are cases when this method would fail like adjacent
> changes made by third-party patches that break the context of the git
> patches and git-apply would fail. An addition to this would be to try
> a diff3 merge with the reversed patch but I don't think it's worth
> since it would become much slower.

True.  The constant reapplication does really slow it down.  So does
grabbing the reverse patch and seeing if it applies backwards
cleanly.  Neither operation is fast, and neither is really going
to be fast.

BTW - I did read through your patch when it was posted: the reverse
apply idea is pretty slick and should work a large part of the time,
as you said.  Nice addition to StGIT.
 
> > If that pushes down cleanly then we make PatchA and PatchB officially
> > part of PatchC.
> 
> I don't agree with this. For example, patches A, B and C change the
> same line in file1 but patch A also changes file2 and patch B changed
> file3. With your approach, merging A+B+C succeeds and you make A and B
> part of C and hence move the changed to file2 and file3 in patch C.
> 
> The above can happen when the maintainer only merges part of the patch
> or simply decides to merge patch C only and manually solve the
> conflict in file1 (since patch C is based on the context from patches
> A+B).

Ah, yes.  The upstream maintainer who doesn't take everything.
Shame on them.  :-) Shame on me for also not dealing with this
case in pg, you are completely correct that folding these patches
together in this scenario is a really bad idea.

In the one environment where I really use pg the upstream is forced
to take the entire patch: I have my own foreign SCM interface to PVCS
VM (its heavily customized crap, so I'm not going to contribute it)
and in this interface the upstream is forced to take the entire patch
every time.  So right now its not a huge concern to me personally,
but if anyone else is trying to use pg it might be.

-- 
Shawn.

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

On 01/03/06, Shawn Pearce <spearce@spearce.org> wrote:
> [Side Note: I've suddenly stopped receiving mail from vger.
>  Even majordomo isn't replying to my pleas for help.  Arggh!
>  Yet all other incoming email seems to be fine.]

news.gmane.org

> True.  The constant reapplication does really slow it down.  So does
> grabbing the reverse patch and seeing if it applies backwards
> cleanly.  Neither operation is fast, and neither is really going
> to be fast.

I realised that, depending on the number of patches merged upstream,
using this option can make StGIT faster. That's because when pushing a
patch (without the --merged option), StGIT first tries a diff | apply
followed by a three-way merge (even slower) if the former method
fails. This means that for all the patches merged upstream, StGIT
tries both methods since diff | apply fails anyway. With the --merged
option, StGIT would only try the reverse-diff | apply and, if this
succeeds, it will skip the normal push methods.

--
Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Shawn Pearce]

Catalin Marinas <catalin.marinas@gmail.com> wrote:
> On 01/03/06, Shawn Pearce <spearce@spearce.org> wrote:
> > True.  The constant reapplication does really slow it down.  So does
> > grabbing the reverse patch and seeing if it applies backwards
> > cleanly.  Neither operation is fast, and neither is really going
> > to be fast.
> 
> I realised that, depending on the number of patches merged upstream,
> using this option can make StGIT faster. That's because when pushing a
> patch (without the --merged option), StGIT first tries a diff | apply
> followed by a three-way merge (even slower) if the former method
> fails. This means that for all the patches merged upstream, StGIT
> tries both methods since diff | apply fails anyway. With the --merged
> option, StGIT would only try the reverse-diff | apply and, if this
> succeeds, it will skip the normal push methods.

Speaking of making StGIT faster: earlier we were talking about how
git-diff|git-apply is faster than a 3 way git-read-tree on large
merges when there are many structural changes in the tree due to
the smaller number of process spawns required.

You might want to take a look at pg--merge-all: This is sort of based
on git-merge-recursive, but I've gotten it down to just a handful
of process spawns, aside from the stupidity of git-checkout-index.
(My recent git-checkout-index patches are working to correct that.)

-- 
Shawn.

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

On 01/03/06, Shawn Pearce <spearce@spearce.org> wrote:
> Speaking of making StGIT faster: earlier we were talking about how
> git-diff|git-apply is faster than a 3 way git-read-tree on large
> merges when there are many structural changes in the tree due to
> the smaller number of process spawns required.
>
> You might want to take a look at pg--merge-all: This is sort of based
> on git-merge-recursive, but I've gotten it down to just a handful
> of process spawns, aside from the stupidity of git-checkout-index.

Trying to implement this, I've just noticed that git-read-tree has a
--aggressive option which takes care of the file removals. Adding this
option lowered the pushing time in StGIT from ~2 min to under 2
seconds (merges between 2.6.14 and the latest kernel). There's
probably no need to deal with file removals in pg--merge-all anymore.

--
Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Junio C Hamano]

"Catalin Marinas" <catalin.marinas@gmail.com> writes:

> Trying to implement this, I've just noticed that git-read-tree has a
> --aggressive option which takes care of the file removals. Adding this
> option lowered the pushing time in StGIT from ~2 min to under 2
> seconds (merges between 2.6.14 and the latest kernel). There's
> probably no need to deal with file removals in pg--merge-all anymore.

Yup, it was originally done to improve the performance of
resolve merge strategy, but I am glad somebody else has found
use for it.

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Catalin Marinas]

On 09/03/06, Junio C Hamano <junkio@cox.net> wrote:
> "Catalin Marinas" <catalin.marinas@gmail.com> writes:
>
> > Trying to implement this, I've just noticed that git-read-tree has a
> > --aggressive option which takes care of the file removals. Adding this
> > option lowered the pushing time in StGIT from ~2 min to under 2
> > seconds (merges between 2.6.14 and the latest kernel). There's
> > probably no need to deal with file removals in pg--merge-all anymore.
>
> Yup, it was originally done to improve the performance of
> resolve merge strategy, but I am glad somebody else has found
> use for it.

Actually, I asked for it about 6 months ago:

http://marc.theaimsgroup.com/?l=git&m=112677889118711&w=2

and I got the reply from you :-):

http://marc.theaimsgroup.com/?l=git&m=112690084826630&w=2

Anyway, it's good we have it, it saved me some time with implementing
Shawn's merging algorithm.

--
Catalin

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Junio C Hamano]

"Catalin Marinas" <catalin.marinas@gmail.com> writes:

> On 09/03/06, Junio C Hamano <junkio@cox.net> wrote:
>
>> Yup, it was originally done to improve the performance of
>> resolve merge strategy, but I am glad somebody else has found
>> use for it.
>
> Actually, I asked for it about 6 months ago:
>
> http://marc.theaimsgroup.com/?l=git&m=112677889118711&w=2
>
> and I got the reply from you :-):
>
> http://marc.theaimsgroup.com/?l=git&m=112690084826630&w=2
>
> Anyway, it's good we have it...

I had this one in mind:

        http://marc.theaimsgroup.com/?t=113874460800001&r=1&w=2

Specifically, this message:

	http://marc.theaimsgroup.com/?l=git&m=113874886615202&w=2

It seems that this has been an recurring issue.

Re: bug?: stgit creates (unneccessary?) conflicts when pulling

[Shawn Pearce]

Catalin Marinas <catalin.marinas@gmail.com> wrote:
> On 01/03/06, Shawn Pearce <spearce@spearce.org> wrote:
> > Speaking of making StGIT faster: earlier we were talking about how
> > git-diff|git-apply is faster than a 3 way git-read-tree on large
> > merges when there are many structural changes in the tree due to
> > the smaller number of process spawns required.
> >
> > You might want to take a look at pg--merge-all: This is sort of based
> > on git-merge-recursive, but I've gotten it down to just a handful
> > of process spawns, aside from the stupidity of git-checkout-index.
> 
> Trying to implement this, I've just noticed that git-read-tree has a
> --aggressive option which takes care of the file removals. Adding this
> option lowered the pushing time in StGIT from ~2 min to under 2
> seconds (merges between 2.6.14 and the latest kernel). There's
> probably no need to deal with file removals in pg--merge-all anymore.


Thanks for the heads up.  I'll have to add that in.  In case you
didn't notice the list traffic I have added a --stage=all switch to
git-checkout-index to grab into temporary files all unmerged stages.

I'm still working on integrating that into pg--merge-all but the
idea is to save on the fork/exec of git-unpack-file when I get into
the diff portion of the merge process.  At least on Cygwin (a place
where I'm really using pg) it will save time as the forks are so
expensive there.  Linux users may not see any improvement from it.

I also added --stdin to git-checkout-index but pg--merge-all is
still using xargs.  I just haven't had time to convert it over and
push it up to my public repo.  Hopefully I'll get both of those
done this weekend.

I've started to get busy with an Eclipse plugin for GIT so my work
with pg is likely going to slow down a little (besides its doing
most of what I need at this point).  But the next thing I was going
to try to add to GIT to boost pg's performance was to integrate
a diff library, so we aren't forking out a diff process for every
file we need to extract a diff for.

-- 
Shawn.