ApplyCommand: use context lines to determine hunk location

If a hunk does not apply at the position stated in the hunk header
try to determine its position using the old lines (context and
deleted lines).

This is still a far cry from a full git apply: it doesn't do binary
patches, it doesn't handle git's whitespace options, and it's perhaps
not the fastest on big patches. C git hashes the lines and uses these
hashes to speed up matching hunks (and to do its whitespace magic).

Bug: 562348
Change-Id: Id0796bba059d84e648769d5896f497fde0b787dd
Signed-off-by: Thomas Wolf <thomas.wolf@paranor.ch>

13 files changed, 535 insertions, 1 deletions

diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown.patch b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown.patch
new file mode 100644
index 0000000000..74c33714b1
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown.patch
@@ -0,0 +1,14 @@
+diff --git a/ShiftDown b/ShiftDown
+index 8b9727b..25dc192 100644
+--- a/ShiftDown
++++ b/ShiftDown
+@@ -16,6 +16,9 @@
+ 			something("A.b", "bar");
+ 		}
+ 
++		public void methodC() {
++			something("A.c", "bar");
++		}
+ 	}
+ 
+ 	public class B {
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2.patch b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2.patch
new file mode 100644
index 0000000000..a2b34b354c
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2.patch
@@ -0,0 +1,24 @@
+diff --git a/ShiftDown2 b/ShiftDown2
+index 8b9727b..63353aa 100644
+--- a/ShiftDown2
++++ b/ShiftDown2
+@@ -16,6 +16,9 @@
+ 			something("A.b", "bar");
+ 		}
+ 
++		public void methodC() {
++			something("A.c", "bar");
++		}
+ 	}
+ 
+ 	public class B {
+@@ -28,5 +31,9 @@
+ 			something("B.b", "bar");
+ 		}
+ 
++		public void methodC() {
++			something("B.c", "bar");
++		}
++
+ 	}
+ }
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2_PostImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2_PostImage
new file mode 100644
index 0000000000..738484eefd
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2_PostImage
@@ -0,0 +1,75 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class D {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class E {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class F {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+		public void methodC() {
+			something("A.c", "bar");
+		}
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+		public void methodC() {
+			something("B.c", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2_PreImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2_PreImage
new file mode 100644
index 0000000000..e1ee19c4dc
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown2_PreImage
@@ -0,0 +1,68 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class D {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class E {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class F {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown_PostImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown_PostImage
new file mode 100644
index 0000000000..5c6e9bccb2
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown_PostImage
@@ -0,0 +1,71 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class D {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class E {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class F {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+		public void methodC() {
+			something("A.c", "bar");
+		}
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown_PreImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown_PreImage
new file mode 100644
index 0000000000..e1ee19c4dc
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftDown_PreImage
@@ -0,0 +1,68 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class D {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class E {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class F {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp.patch b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp.patch
new file mode 100644
index 0000000000..aa994a12e6
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp.patch
@@ -0,0 +1,14 @@
+diff --git a/ShiftUp b/ShiftUp
+index e1ee19c..5c6e9bc 100644
+--- a/ShiftUp
++++ b/ShiftUp
+@@ -52,6 +52,9 @@
+ 			something("A.b", "bar");
+ 		}
+ 
++		public void methodC() {
++			something("A.c", "bar");
++		}
+ 	}
+ 
+ 	public class B {
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2.patch b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2.patch
new file mode 100644
index 0000000000..eca99714c2
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2.patch
@@ -0,0 +1,23 @@
+diff --git a/ShiftUp2 b/ShiftUp2
+index e1ee19c..f010144 100644
+--- a/ShiftUp2
++++ b/ShiftUp2
+@@ -52,6 +52,9 @@
+ 			something("A.b", "bar");
+ 		}
+ 
++		public void methodC() {
++			something("A.c", "bar");
++		}
+ 	}
+ 
+ 	public class B {
+@@ -64,5 +67,8 @@
+ 			something("B.b", "bar");
+ 		}
+ 
++		public void methodC() {
++			something("B.c", "bar");
++		}
+ 	}
+ }
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2_PostImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2_PostImage
new file mode 100644
index 0000000000..e279eceddd
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2_PostImage
@@ -0,0 +1,38 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+		public void methodC() {
+			something("A.c", "bar");
+		}
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+		public void methodC() {
+			something("B.c", "bar");
+		}
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2_PreImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2_PreImage
new file mode 100644
index 0000000000..8b9727b015
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp2_PreImage
@@ -0,0 +1,32 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp_PostImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp_PostImage
new file mode 100644
index 0000000000..25dc192b0b
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp_PostImage
@@ -0,0 +1,35 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+		public void methodC() {
+			something("A.c", "bar");
+		}
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp_PreImage b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp_PreImage
new file mode 100644
index 0000000000..8b9727b015
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/diff/ShiftUp_PreImage
@@ -0,0 +1,32 @@
+package org.eclipse.jgit.test.apply;
+
+public class TestClass {
+
+	private void something(String prefix, String msg) {
+		System.out.println(prefix + ": " + msg);
+	}
+
+	public class A {
+
+		public void methodA() {
+			something("A.a", "foo");
+		}
+
+		public void methodB() {
+			something("A.b", "bar");
+		}
+
+	}
+
+	public class B {
+
+		public void methodA() {
+			something("B.a", "foo");
+		}
+
+		public void methodB() {
+			something("B.b", "bar");
+		}
+
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/ApplyCommandTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/ApplyCommandTest.java
index 63cd21f59d..055eba7184 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/ApplyCommandTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/ApplyCommandTest.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2012, IBM Corporation and others. and others
+ * Copyright (C) 2011, 2020 IBM Corporation and others
  *
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Distribution License v. 1.0 which is available at
@@ -280,6 +280,46 @@ public class ApplyCommandTest extends RepositoryTestCase {
 				b.getString(0, b.size(), false));
 	}
 
+	@Test
+	public void testShiftUp() throws Exception {
+		ApplyResult result = init("ShiftUp");
+		assertEquals(1, result.getUpdatedFiles().size());
+		assertEquals(new File(db.getWorkTree(), "ShiftUp"),
+				result.getUpdatedFiles().get(0));
+		checkFile(new File(db.getWorkTree(), "ShiftUp"),
+				b.getString(0, b.size(), false));
+	}
+
+	@Test
+	public void testShiftUp2() throws Exception {
+		ApplyResult result = init("ShiftUp2");
+		assertEquals(1, result.getUpdatedFiles().size());
+		assertEquals(new File(db.getWorkTree(), "ShiftUp2"),
+				result.getUpdatedFiles().get(0));
+		checkFile(new File(db.getWorkTree(), "ShiftUp2"),
+				b.getString(0, b.size(), false));
+	}
+
+	@Test
+	public void testShiftDown() throws Exception {
+		ApplyResult result = init("ShiftDown");
+		assertEquals(1, result.getUpdatedFiles().size());
+		assertEquals(new File(db.getWorkTree(), "ShiftDown"),
+				result.getUpdatedFiles().get(0));
+		checkFile(new File(db.getWorkTree(), "ShiftDown"),
+				b.getString(0, b.size(), false));
+	}
+
+	@Test
+	public void testShiftDown2() throws Exception {
+		ApplyResult result = init("ShiftDown2");
+		assertEquals(1, result.getUpdatedFiles().size());
+		assertEquals(new File(db.getWorkTree(), "ShiftDown2"),
+				result.getUpdatedFiles().get(0));
+		checkFile(new File(db.getWorkTree(), "ShiftDown2"),
+				b.getString(0, b.size(), false));
+	}
+
 	private static byte[] readFile(String patchFile) throws IOException {
 		final InputStream in = getTestResource(patchFile);
 		if (in == null) {