Fix infinite loop in PatchScriptBuilder

Under certain conditions PatchScriptBuilder can get stuck inside of
the packContent() method and is unable to advance past the current
Edit position.  If the edit list structure has the right shape,
any RPC trying to access that patch script will lock up the web
handler thread in an infinite loop, and never terminate.  If too
many calls do this, the database pool may be exhausted as each of
these threads is holding onto a database connection.

One fix is to rewrite the PatchScriptBuilder in terms of the Hunk
list used by the frontend UI.  Because the loop uses an iterator
over the hunks rather than iterating over the edits we are certain
to eventually break out.

A nice effect of this refactoring is we can reduce our code size
by sharing this common logic with the client UI.  But really this
code should get moved down into JGit in the near future; its quite
generic and useful for almost any application that wants to present
a 2 way difference.

The new EditList class differs from its parent PatchScript source
slightly because we need to handle the EMPTY edit instances that
appear where comments are.  Bug GERRIT-220 described a case where
the EMPTY edit instance threw off the display by showing the same
line twice.  Since the server is now using the client code, we must
correctly account for these EMPTY edit instances during iteration.
Since the client can now correctly handle these EMPTY edit instances,
we no longer prune them out before sending the edit list down to
the client.

Bug: GERRIT-220
Signed-off-by: Shawn O. Pearce <sop@google.com>

5 files changed, 199 insertions, 203 deletions

diff --git a/src/main/java/com/google/gerrit/client/data/EditList.java b/src/main/java/com/google/gerrit/client/data/EditList.java
new file mode 100644
index 0000000000..48b2984173
--- /dev/null
+++ b/src/main/java/com/google/gerrit/client/data/EditList.java
@@ -0,0 +1,167 @@
+// Copyright (C) 2009 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.client.data;
+
+import org.spearce.jgit.diff.Edit;
+
+import java.util.Iterator;
+import java.util.List;
+
+public class EditList {
+  private final List<Edit> edits;
+  private final int context;
+  private final int aSize;
+  private final int bSize;
+
+  public EditList(final List<Edit> edits, final int contextLines,
+      final int aSize, final int bSize) {
+    this.edits = edits;
+    this.context = contextLines;
+    this.aSize = aSize;
+    this.bSize = bSize;
+  }
+
+  public List<Edit> getEdits() {
+    return edits;
+  }
+
+  public Iterable<Hunk> getHunks() {
+    return new Iterable<Hunk>() {
+      public Iterator<Hunk> iterator() {
+        return new Iterator<Hunk>() {
+          private int curIdx;
+
+          public boolean hasNext() {
+            return curIdx < edits.size();
+          }
+
+          public Hunk next() {
+            final int c = curIdx;
+            final int e = findCombinedEnd(c);
+            curIdx = e + 1;
+            return new Hunk(c, e);
+          }
+
+          public void remove() {
+            throw new UnsupportedOperationException();
+          }
+        };
+      }
+    };
+  }
+
+  private int findCombinedEnd(final int i) {
+    int end = i + 1;
+    while (end < edits.size() && (combineA(end) || combineB(end)))
+      end++;
+    return end - 1;
+  }
+
+  private boolean combineA(final int i) {
+    final Edit s = edits.get(i);
+    final Edit e = edits.get(i - 1);
+    return s.getBeginA() - e.getEndA() <= 2 * context;
+  }
+
+  private boolean combineB(final int i) {
+    final int s = edits.get(i).getBeginB();
+    final int e = edits.get(i - 1).getEndB();
+    return s - e <= 2 * context;
+  }
+
+  public class Hunk {
+    private int curIdx;
+    private Edit curEdit;
+    private final int endIdx;
+    private final Edit endEdit;
+
+    private int aCur;
+    private int bCur;
+    private final int aEnd;
+    private final int bEnd;
+
+    private Hunk(final int ci, final int ei) {
+      curIdx = ci;
+      endIdx = ei;
+      curEdit = edits.get(curIdx);
+      endEdit = edits.get(endIdx);
+
+      aCur = Math.max(0, curEdit.getBeginA() - context);
+      bCur = Math.max(0, curEdit.getBeginB() - context);
+      aEnd = Math.min(aSize, endEdit.getEndA() + context);
+      bEnd = Math.min(bSize, endEdit.getEndB() + context);
+    }
+
+    public int getCurA() {
+      return aCur;
+    }
+
+    public int getCurB() {
+      return bCur;
+    }
+
+    public int getEndA() {
+      return aEnd;
+    }
+
+    public int getEndB() {
+      return bEnd;
+    }
+
+    public void incA() {
+      aCur++;
+    }
+
+    public void incB() {
+      bCur++;
+    }
+
+    public void incBoth() {
+      incA();
+      incB();
+    }
+
+    public boolean isStartOfFile() {
+      return aCur == 0 && bCur == 0;
+    }
+
+    public boolean isContextLine() {
+      return !isModifiedLine() || endIdx + 1 < curIdx;
+    }
+
+    public boolean isDeletedA() {
+      return curEdit.getBeginA() <= aCur && aCur < curEdit.getEndA();
+    }
+
+    public boolean isInsertedB() {
+      return curEdit.getBeginB() <= bCur && bCur < curEdit.getEndB();
+    }
+
+    public boolean isModifiedLine() {
+      return isDeletedA() || isInsertedB();
+    }
+
+    public boolean next() {
+      if (!in(curEdit) && ++curIdx < edits.size()) {
+        curEdit = edits.get(curIdx);
+      }
+      return aCur < aEnd || bCur < bEnd;
+    }
+
+    private boolean in(final Edit edit) {
+      return aCur < edit.getEndA() || bCur < edit.getEndB();
+    }
+  }
+}
diff --git a/src/main/java/com/google/gerrit/client/data/PatchScript.java b/src/main/java/com/google/gerrit/client/data/PatchScript.java
index c1fd7e8253..2945b59490 100644
--- a/src/main/java/com/google/gerrit/client/data/PatchScript.java
+++ b/src/main/java/com/google/gerrit/client/data/PatchScript.java
@@ -20,7 +20,6 @@ import com.google.gerrit.client.data.PatchScriptSettings.Whitespace;
 
 import org.spearce.jgit.diff.Edit;
 
-import java.util.Iterator;
 import java.util.List;
 
 public class PatchScript {
@@ -36,9 +35,8 @@ public class PatchScript {
   protected DisplayMethod displayMethodA;
   protected DisplayMethod displayMethodB;
 
-  public PatchScript(final List<String> h, final PatchScriptSettings s,
-      final SparseFileContent ca, final SparseFileContent cb,
-      final List<Edit> e, final DisplayMethod ma, final DisplayMethod mb) {
+  public PatchScript(final List<String> h, final PatchScriptSettings s, final SparseFileContent ca,
+      final SparseFileContent cb, final List<Edit> e, final DisplayMethod ma, final DisplayMethod mb) {
     header = h;
     settings = s;
     a = ca;
@@ -83,134 +81,7 @@ public class PatchScript {
     return edits;
   }
 
-  public Iterable<Hunk> getHunks() {
-    return new Iterable<Hunk>() {
-      public Iterator<Hunk> iterator() {
-        return new Iterator<Hunk>() {
-          private int curIdx;
-
-          public boolean hasNext() {
-            return curIdx < edits.size();
-          }
-
-          public Hunk next() {
-            final int c = curIdx;
-            final int e = findCombinedEnd(c);
-            curIdx = e + 1;
-            return new Hunk(c, e);
-          }
-
-          public void remove() {
-            throw new UnsupportedOperationException();
-          }
-        };
-      }
-    };
-  }
-
-  private int findCombinedEnd(final int i) {
-    int end = i + 1;
-    while (end < edits.size() && (combineA(end) || combineB(end)))
-      end++;
-    return end - 1;
-  }
-
-  private boolean combineA(final int i) {
-    final Edit s = edits.get(i);
-    final Edit e = edits.get(i - 1);
-    return s.getBeginA() - e.getEndA() <= 2 * getContext();
-  }
-
-  private boolean combineB(final int i) {
-    final int s = edits.get(i).getBeginB();
-    final int e = edits.get(i - 1).getEndB();
-    return s - e <= 2 * getContext();
-  }
-
-  private static boolean end(final Edit edit, final int a, final int b) {
-    return edit.getEndA() <= a && edit.getEndB() <= b;
-  }
-
-  public class Hunk {
-    private int curIdx;
-    private Edit curEdit;
-    private final int endIdx;
-    private final Edit endEdit;
-
-    private int aCur;
-    private int bCur;
-    private final int aEnd;
-    private final int bEnd;
-
-    private Hunk(final int ci, final int ei) {
-      curIdx = ci;
-      endIdx = ei;
-      curEdit = edits.get(curIdx);
-      endEdit = edits.get(endIdx);
-
-      aCur = Math.max(0, curEdit.getBeginA() - getContext());
-      bCur = Math.max(0, curEdit.getBeginB() - getContext());
-      aEnd = Math.min(a.size(), endEdit.getEndA() + getContext());
-      bEnd = Math.min(b.size(), endEdit.getEndB() + getContext());
-    }
-
-    public int getCurA() {
-      return aCur;
-    }
-
-    public int getCurB() {
-      return bCur;
-    }
-
-    public int getEndA() {
-      return aEnd;
-    }
-
-    public int getEndB() {
-      return bEnd;
-    }
-
-    public void incA() {
-      aCur++;
-    }
-
-    public void incB() {
-      bCur++;
-    }
-
-    public void incBoth() {
-      incA();
-      incB();
-    }
-
-    public boolean isStartOfFile() {
-      return aCur == 0 && bCur == 0;
-    }
-
-    public boolean hasNextLine() {
-      return aCur < aEnd || bCur < bEnd;
-    }
-
-    public boolean isContextLine() {
-      return aCur < curEdit.getBeginA() || endIdx + 1 < curIdx;
-    }
-
-    public boolean isDeletedA() {
-      return aCur < curEdit.getEndA();
-    }
-
-    public boolean isInsertedB() {
-      return bCur < curEdit.getEndB();
-    }
-
-    public boolean isModifiedLine() {
-      return isDeletedA() || isInsertedB();
-    }
-
-    public void next() {
-      if (end(curEdit, aCur, bCur) && ++curIdx < edits.size()) {
-        curEdit = edits.get(curIdx);
-      }
-    }
+  public Iterable<EditList.Hunk> getHunks() {
+    return new EditList(edits, getContext(), a.size(), b.size()).getHunks();
   }
 }
diff --git a/src/main/java/com/google/gerrit/client/patches/SideBySideTable.java b/src/main/java/com/google/gerrit/client/patches/SideBySideTable.java
index 82074f1ad6..fa54d22cf7 100644
--- a/src/main/java/com/google/gerrit/client/patches/SideBySideTable.java
+++ b/src/main/java/com/google/gerrit/client/patches/SideBySideTable.java
@@ -19,6 +19,7 @@ import static com.google.gerrit.client.patches.PatchLine.Type.DELETE;
 import static com.google.gerrit.client.patches.PatchLine.Type.INSERT;
 import static com.google.gerrit.client.patches.PatchLine.Type.REPLACE;
 
+import com.google.gerrit.client.data.EditList;
 import com.google.gerrit.client.data.PatchScript;
 import com.google.gerrit.client.data.SparseFileContent;
 import com.google.gerrit.client.reviewdb.PatchLineComment;
@@ -74,13 +75,13 @@ public class SideBySideTable extends AbstractPatchContentTable {
 
     int lastB = 0;
     final boolean ignoreWS = script.isIgnoreWhitespace();
-    for (final PatchScript.Hunk hunk : script.getHunks()) {
+    for (final EditList.Hunk hunk : script.getHunks()) {
       if (!hunk.isStartOfFile()) {
         appendSkipLine(nc, hunk.getCurB() - lastB);
         lines.add(null);
       }
 
-      while (hunk.hasNextLine()) {
+      while (hunk.next()) {
         if (hunk.isContextLine()) {
           openLine(nc);
           final SafeHtml ctx = fmtA.format(a.get(hunk.getCurA()));
@@ -123,8 +124,6 @@ public class SideBySideTable extends AbstractPatchContentTable {
             lines.add(new PatchLine(INSERT, 0, hunk.getCurB()));
           }
         }
-
-        hunk.next();
       }
       lastB = hunk.getCurB();
     }
diff --git a/src/main/java/com/google/gerrit/client/patches/UnifiedDiffTable.java b/src/main/java/com/google/gerrit/client/patches/UnifiedDiffTable.java
index ffbba1f148..667d86bc26 100644
--- a/src/main/java/com/google/gerrit/client/patches/UnifiedDiffTable.java
+++ b/src/main/java/com/google/gerrit/client/patches/UnifiedDiffTable.java
@@ -18,10 +18,11 @@ import static com.google.gerrit.client.patches.PatchLine.Type.CONTEXT;
 import static com.google.gerrit.client.patches.PatchLine.Type.DELETE;
 import static com.google.gerrit.client.patches.PatchLine.Type.INSERT;
 
+import com.google.gerrit.client.data.EditList;
 import com.google.gerrit.client.data.PatchScript;
 import com.google.gerrit.client.data.SparseFileContent;
+import com.google.gerrit.client.data.EditList.Hunk;
 import com.google.gerrit.client.data.PatchScript.DisplayMethod;
-import com.google.gerrit.client.data.PatchScript.Hunk;
 import com.google.gerrit.client.reviewdb.Patch;
 import com.google.gerrit.client.reviewdb.PatchLineComment;
 import com.google.gwt.core.client.GWT;
@@ -134,9 +135,9 @@ public class UnifiedDiffTable extends AbstractPatchContentTable {
     }
 
     final ArrayList<PatchLine> lines = new ArrayList<PatchLine>();
-    for (final PatchScript.Hunk hunk : script.getHunks()) {
+    for (final EditList.Hunk hunk : script.getHunks()) {
       appendHunkHeader(nc, hunk);
-      while (hunk.hasNextLine()) {
+      while (hunk.next()) {
         if (hunk.isContextLine()) {
           openLine(nc);
           appendLineNumber(nc, hunk.getCurA());
@@ -168,8 +169,6 @@ public class UnifiedDiffTable extends AbstractPatchContentTable {
           if (b.size() == hunk.getCurB() && b.isMissingNewlineAtEnd())
             appendNoLF(nc);
         }
-
-        hunk.next();
       }
     }
     resetHtml(nc);
diff --git a/src/main/java/com/google/gerrit/server/patch/PatchScriptBuilder.java b/src/main/java/com/google/gerrit/server/patch/PatchScriptBuilder.java
index eb9c5418a2..b47a29c8ea 100644
--- a/src/main/java/com/google/gerrit/server/patch/PatchScriptBuilder.java
+++ b/src/main/java/com/google/gerrit/server/patch/PatchScriptBuilder.java
@@ -14,6 +14,7 @@
 
 package com.google.gerrit.server.patch;
 
+import com.google.gerrit.client.data.EditList;
 import com.google.gerrit.client.data.PatchScript;
 import com.google.gerrit.client.data.PatchScriptSettings;
 import com.google.gerrit.client.data.SparseFileContent;
@@ -302,67 +303,6 @@ class PatchScriptBuilder {
     }
   }
 
-  private void packContent() {
-    for (int curIdx = 0; curIdx < edits.size();) {
-      Edit curEdit = edits.get(curIdx);
-      final int endIdx = findCombinedEnd(edits, curIdx);
-      final Edit endEdit = edits.get(endIdx);
-
-      int aCur = Math.max(0, curEdit.getBeginA() - context());
-      int bCur = Math.max(0, curEdit.getBeginB() - context());
-      final int aEnd = Math.min(a.src.size(), endEdit.getEndA() + context());
-      final int bEnd = Math.min(b.src.size(), endEdit.getEndB() + context());
-
-      while (aCur < aEnd || bCur < bEnd) {
-        if (aCur < curEdit.getBeginA() || endIdx + 1 < curIdx) {
-          a.src.addLineTo(a.dst, aCur);
-          aCur++;
-          bCur++;
-
-        } else if (aCur < curEdit.getEndA()) {
-          a.src.addLineTo(a.dst, aCur++);
-
-        } else if (bCur < curEdit.getEndB()) {
-          b.src.addLineTo(b.dst, bCur++);
-        }
-
-        if (end(curEdit, aCur, bCur) && ++curIdx < edits.size()) {
-          curEdit = edits.get(curIdx);
-          while (curEdit.getType() == Edit.Type.EMPTY) {
-            if (aEnd <= curEdit.getBeginA() || bEnd <= curEdit.getEndB()) {
-              break;
-            }
-            edits.remove(curIdx);
-            if (curIdx < edits.size()) {
-              curEdit = edits.get(curIdx);
-            } else {
-              break;
-            }
-          }
-        }
-      }
-    }
-  }
-
-  private int findCombinedEnd(final List<Edit> edits, final int i) {
-    int end = i + 1;
-    while (end < edits.size() && (combineA(edits, end) || combineB(edits, end)))
-      end++;
-    return end - 1;
-  }
-
-  private boolean combineA(final List<Edit> e, final int i) {
-    return e.get(i).getBeginA() - e.get(i - 1).getEndA() <= 2 * context();
-  }
-
-  private boolean combineB(final List<Edit> e, final int i) {
-    return e.get(i).getBeginB() - e.get(i - 1).getEndB() <= 2 * context();
-  }
-
-  private static boolean end(final Edit edit, final int a, final int b) {
-    return edit.getEndA() <= a && edit.getEndB() <= b;
-  }
-
   private static int end(final FileHeader h) {
     if (h instanceof CombinedFileHeader) {
       return h.getEndOffset();
@@ -373,6 +313,26 @@ class PatchScriptBuilder {
     return h.getEndOffset();
   }
 
+  private void packContent() {
+    EditList list = new EditList(edits, context(), a.src.size(), b.src.size());
+    for (final EditList.Hunk hunk : list.getHunks()) {
+      while (hunk.next()) {
+        if (hunk.isContextLine()) {
+          a.src.addLineTo(a.dst, hunk.getCurA());
+          hunk.incBoth();
+
+        } else if (hunk.isDeletedA()) {
+          a.src.addLineTo(a.dst, hunk.getCurA());
+          hunk.incA();
+
+        } else if (hunk.isInsertedB()) {
+          b.src.addLineTo(b.dst, hunk.getCurB());
+          hunk.incB();
+        }
+      }
+    }
+  }
+
   private class Side {
     String path;
     ObjectId id;