Coverage Report - org.crosswire.common.diff.Patch
 
Classes in this File Line Coverage Branch Coverage Complexity
Patch
0%
0/186
0%
0/92
4.917
Patch$PatchResults
0%
0/6
N/A
4.917
 
 1  
 /**
 2  
  * Distribution License:
 3  
  * JSword is free software; you can redistribute it and/or modify it under
 4  
  * the terms of the GNU Lesser General Public License, version 2.1 or later
 5  
  * as published by the Free Software Foundation. This program is distributed
 6  
  * in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
 7  
  * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 8  
  * See the GNU Lesser General Public License for more details.
 9  
  *
 10  
  * The License is available on the internet at:
 11  
  *      http://www.gnu.org/copyleft/lgpl.html
 12  
  * or by writing to:
 13  
  *      Free Software Foundation, Inc.
 14  
  *      59 Temple Place - Suite 330
 15  
  *      Boston, MA 02111-1307, USA
 16  
  *
 17  
  * © CrossWire Bible Society, 2007 - 2016
 18  
  *
 19  
  */
 20  
 package org.crosswire.common.diff;
 21  
 
 22  
 import java.util.ArrayList;
 23  
 import java.util.List;
 24  
 import java.util.ListIterator;
 25  
 import java.util.regex.Matcher;
 26  
 import java.util.regex.Pattern;
 27  
 
 28  
 /**
 29  
  * Marshals a patch to a list of Differences, Differences to a patch and applies
 30  
  * a list of differences to text to patch it.
 31  
  * 
 32  
  * Based on the LGPL Diff_Match_Patch v1.5 javascript of Neil Fraser, Copyright (C) 2006<br>
 33  
  * <a href="http://neil.fraser.name/software/diff_match_patch/">http://neil.fraser.name/software/diff_match_patch/</a>
 34  
  * 
 35  
  * @see gnu.lgpl.License The GNU Lesser General Public License for details.
 36  
  * @author DM Smith
 37  
  */
 38  
 public class Patch {
 39  
     /**
 40  
      * Create an empty patch.
 41  
      */
 42  0
     public Patch() {
 43  0
         patches = new ArrayList<PatchEntry>();
 44  0
         margin = PatchEntry.getMargin();
 45  0
     }
 46  
 
 47  
     /**
 48  
      * Create a Patch from a textual representation,
 49  
      * 
 50  
      * @param input
 51  
      *            Text representation of patches
 52  
      */
 53  
     public Patch(String input) {
 54  0
         this();
 55  0
         fromText(input);
 56  0
     }
 57  
 
 58  
     /**
 59  
      * Create a patch that can turn text1 into text2.
 60  
      * 
 61  
      * @param source
 62  
      *            Old text
 63  
      * @param target
 64  
      *            New text
 65  
      */
 66  
     public Patch(String source, String target) {
 67  0
         this(source, target, null);
 68  0
     }
 69  
 
 70  
     /**
 71  
      * Create a patch that can turn text1 into text2. Use the diffs provided, if
 72  
      * not null. Compute diffs otherwise.
 73  
      * 
 74  
      * @param source
 75  
      *            Old text
 76  
      * @param target
 77  
      *            New text
 78  
      * @param diffs
 79  
      *            Optional array of diff tuples for text1 to text2.
 80  
      */
 81  
     public Patch(String source, String target, List<Difference> diffs) {
 82  0
         this();
 83  0
         make(source, target, diffs);
 84  0
     }
 85  
 
 86  
     /**
 87  
      * Compute a list of patches to turn text1 into text2. Use the diffs
 88  
      * provided.
 89  
      * 
 90  
      * @param source
 91  
      *            Old text
 92  
      * @param target
 93  
      *            New text
 94  
      * @param diffList
 95  
      *            Optional array of diff tuples for text1 to text2.
 96  
      * @return this patch
 97  
      */
 98  
     public Patch make(String source, String target, List<Difference> diffList) {
 99  0
         List<Difference> diffs = diffList;
 100  0
         if (diffs == null) {
 101  0
             Diff diff = new Diff(source, target);
 102  0
             diffs = diff.compare();
 103  0
             if (diffs.size() > 2) {
 104  0
                 DiffCleanup.cleanupSemantic(diffs);
 105  0
                 DiffCleanup.cleanupEfficiency(diffs);
 106  
             }
 107  
         }
 108  
 
 109  0
         patches.clear();
 110  
 
 111  0
         if (diffs.isEmpty()) {
 112  0
             return this; // Get rid of the null case.
 113  
         }
 114  
 
 115  0
         PatchEntry patch = new PatchEntry();
 116  0
         int charCount1 = 0; // Number of characters into the text1 string.
 117  0
         int charCount2 = 0; // Number of characters into the text2 string.
 118  
         // Recreate the patches to determine context info.
 119  0
         String prePatchText = source;
 120  0
         String postPatchText = source;
 121  0
         int x = 0;
 122  0
         for (Difference diff : diffs) {
 123  0
             EditType editType = diff.getEditType();
 124  0
             String diffText = diff.getText();
 125  0
             int len = diffText.length();
 126  
 
 127  0
             if (!patch.hasDifferences() && !EditType.EQUAL.equals(editType)) {
 128  
                 // A new patch starts here.
 129  0
                 patch.setSourceStart(charCount1);
 130  0
                 patch.setTargetStart(charCount2);
 131  
             }
 132  
 
 133  0
             if (EditType.INSERT.equals(editType)) {
 134  
                 // Insertion
 135  0
                 patch.addDifference(diff);
 136  0
                 patch.adjustTargetLength(len);
 137  0
                 postPatchText = postPatchText.substring(0, charCount2) + diffText + postPatchText.substring(charCount2);
 138  0
             } else if (EditType.DELETE.equals(editType)) {
 139  
                 // Deletion.
 140  0
                 patch.adjustSourceLength(len);
 141  0
                 patch.addDifference(diff);
 142  0
                 postPatchText = postPatchText.substring(0, charCount2) + postPatchText.substring(charCount2 + len);
 143  0
             } else if (EditType.EQUAL.equals(editType) && len <= 2 * margin && patch.hasDifferences() && diffs.size() != x + 1) {
 144  
                 // Small equality inside a patch.
 145  0
                 patch.addDifference(diff);
 146  0
                 patch.adjustSourceLength(len);
 147  0
                 patch.adjustTargetLength(len);
 148  
             }
 149  
 
 150  
             // Time for a new patch.
 151  0
             if (EditType.EQUAL.equals(editType) && len >= 2 * margin && patch.hasDifferences()) {
 152  0
                 patch.addContext(prePatchText);
 153  0
                 patches.add(patch);
 154  0
                 patch = new PatchEntry();
 155  0
                 prePatchText = postPatchText;
 156  
             }
 157  
 
 158  
             // Update the current character count.
 159  0
             if (!EditType.INSERT.equals(editType)) {
 160  0
                 charCount1 += len;
 161  
             }
 162  
 
 163  0
             if (!EditType.DELETE.equals(editType)) {
 164  0
                 charCount2 += len;
 165  
             }
 166  
 
 167  0
             x++;
 168  0
         }
 169  
 
 170  
         // Pick up the leftover patch if not empty.
 171  0
         if (patch.hasDifferences()) {
 172  0
             patch.addContext(prePatchText);
 173  0
             patches.add(patch);
 174  
         }
 175  
 
 176  0
         return this;
 177  
     }
 178  
 
 179  
     /**
 180  
      * Merge this patch onto the text. Return a patched text, as well as an
 181  
      * array of true/false values indicating which patches were applied.
 182  
      * 
 183  
      * @param text
 184  
      *            Old text
 185  
      * @return the patch result
 186  
      */
 187  
     public PatchResults apply(String text) {
 188  0
         splitMax();
 189  0
         boolean[] results = new boolean[patches.size()];
 190  0
         String resultText = text;
 191  0
         int delta = 0;
 192  0
         int expectedLoc = 0;
 193  0
         int startLoc = -1;
 194  0
         String text1 = "";
 195  0
         String text2 = "";
 196  
         List<Difference> diffs;
 197  0
         int index1 = 0;
 198  0
         int index2 = 0;
 199  0
         int x = 0;
 200  0
         for (PatchEntry aPatch : patches) {
 201  0
             expectedLoc = aPatch.getTargetStart() + delta;
 202  0
             text1 = aPatch.getSourceText();
 203  0
             Match match = new Match(resultText, text1, expectedLoc);
 204  0
             startLoc = match.locate();
 205  0
             if (startLoc == -1) {
 206  
                 // No match found. :(
 207  0
                 results[x] = false;
 208  
             } else {
 209  
                 // Found a match. :)
 210  0
                 results[x] = true;
 211  0
                 delta = startLoc - expectedLoc;
 212  0
                 text2 = resultText.substring(startLoc, startLoc + text1.length());
 213  0
                 if (text1.equals(text2)) {
 214  
                     // Perfect match, just shove the replacement text in.
 215  0
                     resultText = resultText.substring(0, startLoc) + aPatch.getTargetText() + resultText.substring(startLoc + text1.length());
 216  
                 } else {
 217  
                     // Imperfect match. Run a diff to get a framework of
 218  
                     // equivalent indicies.
 219  0
                     Diff diff = new Diff(text1, text2, false);
 220  0
                     diffs = diff.compare();
 221  0
                     index1 = 0;
 222  0
                     for (Difference aDiff : aPatch) {
 223  0
                         EditType editType = aDiff.getEditType();
 224  0
                         if (!EditType.EQUAL.equals(editType)) {
 225  0
                             index2 = diff.xIndex(diffs, index1);
 226  
                         }
 227  
 
 228  0
                         if (EditType.INSERT.equals(editType)) {
 229  
                             // Insertion
 230  0
                             resultText = resultText.substring(0, startLoc + index2) + aDiff.getText() + resultText.substring(startLoc + index2);
 231  0
                         } else if (EditType.DELETE.equals(editType)) {
 232  
                             // Deletion
 233  0
                             resultText = resultText.substring(0, startLoc + index2)
 234  
                                     + resultText.substring(startLoc + diff.xIndex(diffs, index1 + aDiff.getText().length()));
 235  
                         }
 236  
 
 237  0
                         if (!EditType.DELETE.equals(editType)) {
 238  0
                             index1 += aDiff.getText().length();
 239  
                         }
 240  0
                     }
 241  
                 }
 242  
             }
 243  0
             x++;
 244  0
         }
 245  0
         return new PatchResults(resultText, results);
 246  
     }
 247  
 
 248  
     /**
 249  
      * Look through the patches and break up any which are longer than the
 250  
      * maximum limit of the match algorithm.
 251  
      */
 252  
     public void splitMax() {
 253  0
         int maxPatternLength = new Match().maxPatternLength();
 254  0
         ListIterator<PatchEntry> pointer = patches.listIterator();
 255  0
         PatchEntry bigPatch = pointer.hasNext() ? pointer.next() : null;
 256  0
         while (bigPatch != null) {
 257  0
             if (bigPatch.getSourceLength() <= maxPatternLength) {
 258  0
                 if (!pointer.hasNext()) {
 259  0
                     break;
 260  
                 }
 261  
 
 262  0
                 bigPatch = pointer.next();
 263  
             }
 264  
 
 265  
             // Remove the big old patch.
 266  0
             pointer.remove();
 267  0
             int patchSize = maxPatternLength;
 268  0
             int start1 = bigPatch.getSourceStart();
 269  0
             int start2 = bigPatch.getTargetStart();
 270  0
             String preContext = "";
 271  0
             while (bigPatch.hasDifferences()) {
 272  
                 // Create one of several smaller patches.
 273  0
                 PatchEntry patch = new PatchEntry();
 274  0
                 boolean empty = true;
 275  
 
 276  0
                 int len = preContext.length();
 277  0
                 patch.setSourceStart(start1 - len);
 278  0
                 patch.setTargetStart(start2 - len);
 279  0
                 if (len > 0) {
 280  0
                     patch.setSourceLength(len);
 281  0
                     patch.setTargetLength(len);
 282  0
                     patch.addDifference(new Difference(EditType.EQUAL, preContext));
 283  
                 }
 284  
 
 285  0
                 while (bigPatch.hasDifferences() && patch.getSourceLength() < patchSize - margin) {
 286  0
                     Difference bigDiff = bigPatch.getFirstDifference();
 287  0
                     EditType editType = bigDiff.getEditType();
 288  0
                     String diffText = bigDiff.getText();
 289  0
                     if (EditType.INSERT.equals(editType)) {
 290  
                         // Insertions are harmless.
 291  0
                         len = diffText.length();
 292  0
                         patch.adjustTargetLength(len);
 293  0
                         start2 += len;
 294  0
                         patch.addDifference(bigPatch.removeFirstDifference());
 295  0
                         empty = false;
 296  
                     } else {
 297  
                         // Deletion or equality. Only take as much as we can
 298  
                         // stomach.
 299  0
                         diffText = diffText.substring(0, Math.min(diffText.length(), patchSize - patch.getSourceLength() - margin));
 300  0
                         len = diffText.length();
 301  0
                         patch.adjustSourceLength(len);
 302  0
                         start1 += len;
 303  0
                         if (EditType.EQUAL.equals(editType)) {
 304  0
                             patch.adjustTargetLength(len);
 305  0
                             start2 += len;
 306  
                         } else {
 307  0
                             empty = false;
 308  
                         }
 309  
 
 310  0
                         patch.addDifference(new Difference(editType, diffText));
 311  
 
 312  0
                         if (diffText.equals(bigDiff.getText())) {
 313  0
                             bigPatch.removeFirstDifference();
 314  
                         } else {
 315  0
                             bigDiff.setText(bigDiff.getText().substring(len));
 316  
                         }
 317  
                     }
 318  0
                 }
 319  
 
 320  
                 // Compute the head context for the next patch.
 321  0
                 preContext = patch.getTargetText();
 322  0
                 preContext = preContext.substring(Math.max(0, preContext.length() - margin));
 323  
 
 324  
                 // Append the end context for this patch.
 325  0
                 String postcontext = null;
 326  0
                 if (bigPatch.getSourceText().length() > margin) {
 327  0
                     postcontext = bigPatch.getSourceText().substring(0, margin);
 328  
                 } else {
 329  0
                     postcontext = bigPatch.getSourceText();
 330  
                 }
 331  0
                 if (postcontext.length() > 0) {
 332  0
                     patch.adjustSourceLength(postcontext.length());
 333  0
                     patch.adjustTargetLength(postcontext.length());
 334  0
                     if (patch.getDifferenceCount() > 0 && EditType.EQUAL.equals(patch.getLastDifference().getEditType())) {
 335  0
                         Difference diff = patch.getLastDifference();
 336  0
                         diff.appendText(postcontext);
 337  0
                     } else {
 338  0
                         patch.addDifference(new Difference(EditType.EQUAL, postcontext));
 339  
                     }
 340  
                 }
 341  
 
 342  0
                 if (!empty) {
 343  0
                     pointer.add(patch);
 344  
                 }
 345  0
             }
 346  
 
 347  0
             bigPatch = pointer.hasNext() ? pointer.next() : null;
 348  0
         }
 349  0
     }
 350  
 
 351  
     /**
 352  
      * Take a list of patches and return a textual representation.
 353  
      * 
 354  
      * @return Text representation of patches.
 355  
      */
 356  
     public String toText() {
 357  0
         StringBuilder text = new StringBuilder();
 358  0
         for (PatchEntry entry : patches) {
 359  0
             text.append(entry);
 360  
         }
 361  0
         return text.toString();
 362  
     }
 363  
 
 364  
     /**
 365  
      * Parse a textual representation of patches and return a List of Patch
 366  
      * objects.
 367  
      * 
 368  
      * @param input
 369  
      *            Text representation of patches
 370  
      * @return List of Patch objects
 371  
      */
 372  
     public Patch fromText(String input) {
 373  0
         patches.clear();
 374  
 
 375  0
         Matcher m = patchBoundaryPattern.matcher(input);
 376  
 
 377  
         // Add segments before each match found
 378  0
         int index = 0;
 379  0
         while (m.find()) {
 380  0
             int start = m.start();
 381  0
             String match = input.substring(index, start);
 382  0
             patches.add(new PatchEntry(match));
 383  0
             index = start + 1;
 384  0
         }
 385  
 
 386  0
         if (index == 0) {
 387  
             // No match was found, the patch consists of the entire string
 388  0
             patches.add(new PatchEntry(input));
 389  
         } else {
 390  
             // Add remaining segment
 391  0
             patches.add(new PatchEntry(input.substring(index)));
 392  
         }
 393  
 
 394  0
         return this;
 395  
     }
 396  
 
 397  
     /**
 398  
      * A holder of the results of a patch, with a results indicating which patch
 399  
      * entries were able to be applied.
 400  
      */
 401  
     public static class PatchResults {
 402  
         /**
 403  
          * @param text the text
 404  
          * @param results the results
 405  
          */
 406  0
         public PatchResults(String text, boolean[] results) {
 407  0
             this.text = text;
 408  0
             this.results = results.clone();
 409  0
         }
 410  
 
 411  
         /**
 412  
          * @return the results
 413  
          */
 414  
         public boolean[] getResults() {
 415  0
             return results.clone();
 416  
         }
 417  
 
 418  
         /**
 419  
          * @return the text
 420  
          */
 421  
         public String getText() {
 422  0
             return text;
 423  
         }
 424  
 
 425  
         private String text;
 426  
         private boolean[] results;
 427  
     }
 428  
 
 429  
     // Ideally we'd like to have the @@ be merely a look-ahead, but it doesn't
 430  
     // work that way with split.
 431  0
     private static Pattern patchBoundaryPattern = Pattern.compile("\n@@");
 432  
 
 433  
     private List<PatchEntry> patches;
 434  
     private int margin;
 435  
 }