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>

12 files changed, 494 insertions, 0 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");
+		}
+
+	}
+}