001: /**
002: * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE, version 2.1, dated February 1999.
003: *
004: * This program is free software; you can redistribute it and/or modify
005: * it under the terms of the latest version of the GNU Lesser General
006: * Public License as published by the Free Software Foundation;
007: *
008: * This program is distributed in the hope that it will be useful,
009: * but WITHOUT ANY WARRANTY; without even the implied warranty of
010: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
011: * GNU Lesser General Public License for more details.
012: *
013: * You should have received a copy of the GNU Lesser General Public License
014: * along with this program (LICENSE.txt); if not, write to the Free Software
015: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
016: */package org.jamwiki.utils;
017:
018: import java.util.Collection;
019: import java.util.List;
020: import java.util.Vector;
021: import org.apache.commons.lang.StringUtils;
022: import org.incava.util.diff.Diff;
023: import org.incava.util.diff.Difference;
024: import org.jamwiki.WikiBase;
025: import org.jamwiki.model.TopicVersion;
026: import org.jamwiki.model.WikiDiff;
027:
028: /**
029: * Utility class for processing the difference between two topics and returing a Vector
030: * of WikiDiff objects that can be used to display the diff.
031: */
032: public class DiffUtil {
033:
034: protected static WikiLogger logger = WikiLogger
035: .getLogger(DiffUtil.class.getName());
036: /** The number of lines of unchanged text to display before and after each diff. */
037: // FIXME - make this a property value
038: private static final int DIFF_UNCHANGED_LINE_DISPLAY = 2;
039:
040: /**
041: *
042: */
043: private DiffUtil() {
044: }
045:
046: /**
047: * Split up a large String into an array of Strings made up of each line (indicated
048: * by a newline) of the original String.
049: */
050: private static String[] buildArray(String original) {
051: if (original == null) {
052: return null;
053: }
054: return original.split("\n");
055: }
056:
057: /**
058: * Utility method for determining whether or not a difference can be post-buffered.
059: */
060: private static boolean canPostBuffer(Difference nextDiff,
061: int current, String[] replacementArray, boolean adding) {
062: if (current < 0 || current >= replacementArray.length) {
063: // if out of a valid range, don't buffer
064: return false;
065: }
066: if (nextDiff == null) {
067: // if in a valid range and no next diff, buffer away
068: return true;
069: }
070: int nextStart = nextDiff.getDeletedStart();
071: if (adding) {
072: nextStart = nextDiff.getAddedStart();
073: }
074: if (nextStart > current) {
075: // if in a valid range and no next diff starts several lines away, buffer away
076: return true;
077: }
078: // default is don't buffer
079: return false;
080: }
081:
082: /**
083: * Utility method for determining whether or not a difference can be pre-buffered.
084: */
085: private static boolean canPreBuffer(Difference previousDiff,
086: int current, int currentStart, String[] replacementArray,
087: boolean adding) {
088: if (current < 0 || current >= replacementArray.length) {
089: // current position is out of range for buffering
090: return false;
091: }
092: if (previousDiff == null) {
093: // if no previous diff, buffer away
094: return true;
095: }
096: int previousEnd = previousDiff.getDeletedEnd();
097: int previousStart = previousDiff.getDeletedStart();
098: if (adding) {
099: previousEnd = previousDiff.getAddedEnd();
100: previousStart = previousDiff.getAddedStart();
101: }
102: if (previousEnd != -1) {
103: // if there was a previous diff but it was several lines previous, buffer away.
104: // if there was a previous diff, and it overlaps with the current diff, don't buffer.
105: return (current > (previousEnd + DIFF_UNCHANGED_LINE_DISPLAY));
106: }
107: if (current <= (previousStart + DIFF_UNCHANGED_LINE_DISPLAY)) {
108: // the previous diff did not specify an end, and the current diff would overlap with
109: // buffering from its start, don't buffer
110: return false;
111: }
112: if (current >= 0 && currentStart > current) {
113: // the previous diff did not specify an end, and the current diff will not overlap
114: // with buffering from its start, buffer away
115: return true;
116: }
117: // default is don't buffer
118: return false;
119: }
120:
121: /**
122: * Return a Vector of WikiDiff objects that can be used to create a display of the
123: * diff content.
124: *
125: * @param newVersion The String that is to be compared to, ie the later version of a topic.
126: * @param oldVersion The String that is to be considered as having changed, ie the earlier
127: * version of a topic.
128: * @return Returns a Vector of WikiDiff objects that correspond to the changed text.
129: */
130: public static Vector diff(String newVersion, String oldVersion) {
131: if (oldVersion == null) {
132: oldVersion = "";
133: }
134: if (newVersion == null) {
135: newVersion = "";
136: }
137: // remove line-feeds to avoid unnecessary noise in the diff due to
138: // cut & paste or other issues
139: oldVersion = StringUtils.remove(oldVersion, '\r');
140: newVersion = StringUtils.remove(newVersion, '\r');
141: if (newVersion.equals(oldVersion)) {
142: return new Vector();
143: }
144: return DiffUtil.process(newVersion, oldVersion);
145: }
146:
147: /**
148: * Execute a diff between two versions of a topic, returning a collection
149: * of WikiDiff objects indicating what has changed between the versions.
150: *
151: * @param topicName The name of the topic for which a diff is being
152: * performed.
153: * @param topicVersionId1 The version ID for the old version being
154: * compared against.
155: * @param topicVersionId2 The version ID for the old version being
156: * compared to.
157: * @return A collection of WikiDiff objects indicating what has changed
158: * between the versions. An empty collection is returned if there are
159: * no differences.
160: * @throws Exception Thrown if any error occurs during method execution.
161: */
162: public static Collection diffTopicVersions(String topicName,
163: int topicVersionId1, int topicVersionId2) throws Exception {
164: TopicVersion version1 = WikiBase.getDataHandler()
165: .lookupTopicVersion(topicVersionId1, null);
166: TopicVersion version2 = WikiBase.getDataHandler()
167: .lookupTopicVersion(topicVersionId2, null);
168: if (version1 == null && version2 == null) {
169: String msg = "Versions " + topicVersionId1 + " and "
170: + topicVersionId2 + " not found for " + topicName;
171: logger.severe(msg);
172: throw new Exception(msg);
173: }
174: String contents1 = null;
175: if (version1 != null) {
176: contents1 = version1.getVersionContent();
177: }
178: String contents2 = null;
179: if (version2 != null) {
180: contents2 = version2.getVersionContent();
181: }
182: if (contents1 == null && contents2 == null) {
183: String msg = "No versions found for " + topicVersionId1
184: + " against " + topicVersionId2;
185: logger.severe(msg);
186: throw new Exception(msg);
187: }
188: return DiffUtil.diff(contents1, contents2);
189: }
190:
191: /**
192: *
193: */
194: private static boolean hasMoreDiffLines(int addedCurrent,
195: int deletedCurrent, Difference currentDiff) {
196: if (addedCurrent == -1) {
197: addedCurrent = 0;
198: }
199: if (deletedCurrent == -1) {
200: deletedCurrent = 0;
201: }
202: return (addedCurrent <= currentDiff.getAddedEnd() || deletedCurrent <= currentDiff
203: .getDeletedEnd());
204: }
205:
206: /**
207: * If possible, try to append a few lines of unchanged text to the diff output to
208: * be used for context.
209: */
210: private static void postBufferDifference(Difference currentDiff,
211: Difference nextDiff, Vector wikiDiffs, String[] oldArray,
212: String[] newArray) {
213: if (DIFF_UNCHANGED_LINE_DISPLAY <= 0) {
214: return;
215: }
216: int deletedCurrent = (currentDiff.getDeletedEnd() + 1);
217: int addedCurrent = (currentDiff.getAddedEnd() + 1);
218: if (currentDiff.getDeletedEnd() == -1) {
219: deletedCurrent = (currentDiff.getDeletedStart());
220: }
221: if (currentDiff.getAddedEnd() == -1) {
222: addedCurrent = (currentDiff.getAddedStart());
223: }
224: for (int i = 0; i < DIFF_UNCHANGED_LINE_DISPLAY; i++) {
225: int lineNumber = ((deletedCurrent < 0) ? 0 : deletedCurrent);
226: String oldLine = null;
227: String newLine = null;
228: boolean buffered = false;
229: if (canPostBuffer(nextDiff, deletedCurrent, oldArray, false)) {
230: oldLine = oldArray[deletedCurrent];
231: deletedCurrent++;
232: buffered = true;
233: }
234: if (canPostBuffer(nextDiff, addedCurrent, newArray, true)) {
235: newLine = newArray[addedCurrent];
236: addedCurrent++;
237: buffered = true;
238: }
239: if (!buffered) {
240: continue;
241: }
242: WikiDiff wikiDiff = new WikiDiff(oldLine, newLine,
243: lineNumber + 1, false);
244: wikiDiffs.add(wikiDiff);
245: }
246: }
247:
248: /**
249: * If possible, try to prepend a few lines of unchanged text to the diff output to
250: * be used for context.
251: */
252: private static void preBufferDifference(Difference currentDiff,
253: Difference previousDiff, Vector wikiDiffs,
254: String[] oldArray, String[] newArray) {
255: if (DIFF_UNCHANGED_LINE_DISPLAY <= 0) {
256: return;
257: }
258: int deletedCurrent = (currentDiff.getDeletedStart() - DIFF_UNCHANGED_LINE_DISPLAY);
259: int addedCurrent = (currentDiff.getAddedStart() - DIFF_UNCHANGED_LINE_DISPLAY);
260: if (previousDiff != null) {
261: deletedCurrent = Math.max(previousDiff.getDeletedEnd() + 1,
262: deletedCurrent);
263: addedCurrent = Math.max(previousDiff.getAddedEnd() + 1,
264: addedCurrent);
265: }
266: for (int i = 0; i < DIFF_UNCHANGED_LINE_DISPLAY; i++) {
267: int lineNumber = ((deletedCurrent < 0) ? 0 : deletedCurrent);
268: String oldLine = null;
269: String newLine = null;
270: boolean buffered = false;
271: // if diffs are close together, do not allow buffers to overlap
272: if (canPreBuffer(previousDiff, deletedCurrent, currentDiff
273: .getDeletedStart(), oldArray, false)) {
274: oldLine = oldArray[deletedCurrent];
275: deletedCurrent++;
276: buffered = true;
277: }
278: if (canPreBuffer(previousDiff, addedCurrent, currentDiff
279: .getAddedStart(), newArray, true)) {
280: newLine = newArray[addedCurrent];
281: addedCurrent++;
282: buffered = true;
283: }
284: if (!buffered) {
285: continue;
286: }
287: WikiDiff wikiDiff = new WikiDiff(oldLine, newLine,
288: lineNumber + 1, false);
289: wikiDiffs.add(wikiDiff);
290: }
291: }
292:
293: /**
294: *
295: */
296: private static Vector process(String newVersion, String oldVersion) {
297: logger.fine("Diffing: " + oldVersion + " against: "
298: + newVersion);
299: String[] oldArray = buildArray(oldVersion);
300: String[] newArray = buildArray(newVersion);
301: Diff diffObject = new Diff(oldArray, newArray);
302: List diffs = diffObject.diff();
303: Vector wikiDiffs = new Vector();
304: Difference currentDiff = null;
305: Difference previousDiff = null;
306: Difference nextDiff = null;
307: for (int i = 0; i < diffs.size(); i++) {
308: currentDiff = (Difference) diffs.get(i);
309: preBufferDifference(currentDiff, previousDiff, wikiDiffs,
310: oldArray, newArray);
311: processDifference(currentDiff, wikiDiffs, oldArray,
312: newArray);
313: nextDiff = null;
314: if ((i + 1) < diffs.size()) {
315: nextDiff = (Difference) diffs.get(i + 1);
316: }
317: postBufferDifference(currentDiff, nextDiff, wikiDiffs,
318: oldArray, newArray);
319: previousDiff = currentDiff;
320: }
321: return wikiDiffs;
322: }
323:
324: /**
325: * Process the diff object and add it to the output.
326: */
327: private static void processDifference(Difference currentDiff,
328: Vector wikiDiffs, String[] oldArray, String[] newArray) {
329: int deletedCurrent = currentDiff.getDeletedStart();
330: int addedCurrent = currentDiff.getAddedStart();
331: int count = 0;
332: while (hasMoreDiffLines(addedCurrent, deletedCurrent,
333: currentDiff)) {
334: int lineNumber = ((deletedCurrent < 0) ? 0 : deletedCurrent);
335: String oldLine = null;
336: String newLine = null;
337: if (currentDiff.getDeletedEnd() >= 0
338: && currentDiff.getDeletedEnd() >= deletedCurrent) {
339: oldLine = oldArray[deletedCurrent];
340: deletedCurrent++;
341: }
342: if (currentDiff.getAddedEnd() >= 0
343: && currentDiff.getAddedEnd() >= addedCurrent) {
344: newLine = newArray[addedCurrent];
345: addedCurrent++;
346: }
347: WikiDiff wikiDiff = new WikiDiff(oldLine, newLine,
348: lineNumber + 1, true);
349: wikiDiffs.add(wikiDiff);
350: // FIXME - this shouldn't be necessary
351: count++;
352: if (count > 5000) {
353: logger
354: .warning("Infinite loop in DiffUtils.processDifference");
355: break;
356: }
357: }
358: }
359: }
|