001: /*
002: * ====================================================================
003: * Copyright (c) 2004-2008 TMate Software Ltd. All rights reserved.
004: *
005: * This software is licensed as described in the file COPYING, which
006: * you should have received as part of this distribution. The terms
007: * are also available at http://svnkit.com/license.html
008: * If newer versions of this license are posted there, you may use a
009: * newer version instead, at your option.
010: * ====================================================================
011: */
012:
013: package org.tmatesoft.svn.core.internal.wc;
014:
015: import java.io.*;
016: import java.util.*;
017: import org.tmatesoft.svn.core.wc.*;
018:
019: import de.regnis.q.sequence.*;
020: import de.regnis.q.sequence.core.*;
021: import de.regnis.q.sequence.line.*;
022: import de.regnis.q.sequence.line.simplifier.*;
023:
024: /**
025: * @version 1.1.1
026: * @author TMate Software Ltd.
027: */
028: public class FSMergerBySequence {
029:
030: // Constants ==============================================================
031:
032: public static final String DEFAULT_EOL = System
033: .getProperty("line.separator");
034: public static final int NOT_MODIFIED = 0;
035: public static final int MERGED = 4;
036: public static final int CONFLICTED = 2;
037:
038: // Fields =================================================================
039:
040: private final byte[] myConflictStart;
041: private final byte[] myConflictSeparator;
042: private final byte[] myConflictEnd;
043:
044: // Setup ==================================================================
045:
046: public FSMergerBySequence(byte[] conflictStart,
047: byte[] conflictSeparator, byte[] conflictEnd) {
048: myConflictStart = conflictStart;
049: myConflictSeparator = conflictSeparator;
050: myConflictEnd = conflictEnd;
051: }
052:
053: // Accessing ==============================================================
054:
055: public int merge(QSequenceLineRAData baseData,
056: QSequenceLineRAData localData,
057: QSequenceLineRAData latestData, SVNDiffOptions options,
058: OutputStream result) throws IOException {
059:
060: // dump("base", baseData);
061: // dump("latest", latestData);
062: // dump("local", localData);
063:
064: final QSequenceLineResult localResult;
065: final QSequenceLineResult latestResult;
066: final QSequenceLineTeeSimplifier mySimplifer = createSimplifier(options);
067: try {
068: localResult = QSequenceLineMedia.createBlocks(baseData,
069: localData, mySimplifer);
070: latestResult = QSequenceLineMedia.createBlocks(baseData,
071: latestData, mySimplifer);
072: } catch (QSequenceException ex) {
073: throw new IOException(ex.getMessage());
074: }
075:
076: try {
077: final QSequenceLineCache baseLines = localResult
078: .getLeftCache();
079: final QSequenceLineCache localLines = localResult
080: .getRightCache();
081: final QSequenceLineCache latestLines = latestResult
082: .getRightCache();
083: final FSMergerBySequenceList local = new FSMergerBySequenceList(
084: localResult.getBlocks());
085: final FSMergerBySequenceList latest = new FSMergerBySequenceList(
086: latestResult.getBlocks());
087: final List transformedLocalLines = transformLocalLines(
088: localResult.getBlocks(), localLines);
089:
090: int baseLineIndex = -1;
091: boolean conflict = false;
092: boolean merged = false;
093:
094: while (local.hasCurrent() || latest.hasCurrent()) {
095: if (local.hasCurrent()
096: && latest.hasCurrent()
097: && isEqualChange(local.current(), latest
098: .current(), localLines, latestLines)) {
099: baseLineIndex = appendLines(result,
100: local.current(), localLines, baseLineIndex,
101: transformedLocalLines);
102: local.forward();
103: latest.forward();
104: continue;
105: }
106:
107: if (local.hasCurrent() && latest.hasCurrent()) {
108: final QSequenceDifferenceBlock localStartBlock = local
109: .current();
110: final QSequenceDifferenceBlock latestStartBlock = latest
111: .current();
112: if (checkConflict(local, latest, localLines,
113: latestLines, baseLines.getLineCount())) {
114: baseLineIndex = createConflict(result,
115: localStartBlock, local.current(),
116: latestStartBlock, latest.current(),
117: localLines, latestLines, baseLineIndex,
118: transformedLocalLines);
119: local.forward();
120: latest.forward();
121: conflict = true;
122: continue;
123: }
124: }
125:
126: if (local.hasCurrent()
127: && isBefore(local.current(), latest
128: .hasCurrent() ? latest.current() : null)) {
129: baseLineIndex = appendLines(result,
130: local.current(), localLines, baseLineIndex,
131: transformedLocalLines);
132: local.forward();
133: merged = true;
134: continue;
135: }
136:
137: if (latest.hasCurrent()) {
138: baseLineIndex = appendLines(result, latest
139: .current(), latestLines, baseLineIndex,
140: transformedLocalLines);
141: latest.forward();
142: merged = true;
143: }
144: }
145:
146: appendTransformedLocalLines(baseLineIndex, baseLines
147: .getLineCount(), transformedLocalLines, result);
148:
149: if (conflict) {
150: return CONFLICTED;
151: } else if (merged) {
152: return MERGED;
153: } else {
154: return NOT_MODIFIED;
155: }
156: } finally {
157: latestResult.close();
158: localResult.close();
159: }
160: }
161:
162: // Utils ==================================================================
163:
164: private List transformLocalLines(List blocks,
165: QSequenceLineCache localLines) throws IOException {
166: final List transformedLocalLines = new ArrayList();
167: final FSMergerBySequenceList blockList = new FSMergerBySequenceList(
168: blocks);
169:
170: int localIndex = 0;
171: int baseIndex = 0;
172:
173: for (; localIndex < localLines.getLineCount();) {
174: final int baseTo;
175: if (blockList.hasCurrent()) {
176: final QSequenceDifferenceBlock block = blockList
177: .current();
178: baseTo = block.getLeftFrom() - 1;
179: } else {
180: baseTo = Integer.MAX_VALUE;
181: }
182:
183: while (localIndex < localLines.getLineCount()
184: && baseIndex <= baseTo) {
185: transformedLocalLines.add(localLines
186: .getLine(localIndex));
187: localIndex++;
188: baseIndex++;
189: }
190:
191: if (blockList.hasCurrent()) {
192: for (int index = 0; index < blockList.current()
193: .getLeftSize(); index++) {
194: transformedLocalLines.add(null);
195: }
196:
197: baseIndex += blockList.current().getLeftSize();
198: localIndex += blockList.current().getRightSize();
199:
200: blockList.forward();
201: }
202: }
203:
204: return transformedLocalLines;
205: }
206:
207: private boolean isBefore(QSequenceDifferenceBlock block1,
208: QSequenceDifferenceBlock block2) {
209: return block1 != null
210: && (block2 == null || block1.getLeftTo() < block2
211: .getLeftFrom());
212: }
213:
214: private boolean intersect(QSequenceDifferenceBlock block1,
215: QSequenceDifferenceBlock block2, int baseLineCount) {
216: final int from1 = block1.getLeftFrom();
217: final int from2 = block2.getLeftFrom();
218: final int to1 = block1.getLeftTo();
219: final int to2 = block2.getLeftTo();
220:
221: if (to1 < from1) {
222: if (to2 < from2) {
223: return from1 == from2;
224: }
225: if (from1 == baseLineCount && to2 >= baseLineCount - 1) {
226: return true;
227: }
228: return from1 >= from2 && from1 <= to2;
229: } else if (to2 < from2) {
230: if (from2 == baseLineCount && to1 >= baseLineCount - 1) {
231: return true;
232: }
233: return from2 >= from1 && from2 <= to1;
234: } else {
235: return (from1 >= from2 && from1 <= to2)
236: || (from2 >= from1 && from2 <= to1);
237: }
238: }
239:
240: private int appendLines(OutputStream result,
241: QSequenceDifferenceBlock block,
242: QSequenceLineCache changedLines, int baseLineIndex,
243: List transformedLocalLines) throws IOException {
244: appendTransformedLocalLines(baseLineIndex, block.getLeftFrom(),
245: transformedLocalLines, result);
246:
247: for (int changedLineIndex = block.getRightFrom(); changedLineIndex <= block
248: .getRightTo(); changedLineIndex++) {
249: writeLine(result, changedLines.getLine(changedLineIndex));
250: }
251:
252: return block.getLeftTo();
253: }
254:
255: private boolean isEqualChange(QSequenceDifferenceBlock localBlock,
256: QSequenceDifferenceBlock latestBlock,
257: QSequenceLineCache localLines,
258: QSequenceLineCache latestLines) throws IOException {
259: if (localBlock.getLeftFrom() != latestBlock.getLeftFrom()
260: || localBlock.getLeftTo() != latestBlock.getLeftTo()) {
261: return false;
262: }
263:
264: if (localBlock.getRightTo() - localBlock.getRightFrom() != latestBlock
265: .getRightTo()
266: - latestBlock.getRightFrom()) {
267: return false;
268: }
269:
270: for (int index = 0; index < localBlock.getRightTo()
271: - localBlock.getRightFrom() + 1; index++) {
272: final QSequenceLine localLine = localLines
273: .getLine(localBlock.getRightFrom() + index);
274: final QSequenceLine latestLine = latestLines
275: .getLine(latestBlock.getRightFrom() + index);
276: if (!localLine.equals(latestLine)) {
277: return false;
278: }
279: }
280:
281: return true;
282: }
283:
284: private boolean checkConflict(FSMergerBySequenceList localChanges,
285: FSMergerBySequenceList latestChanges,
286: QSequenceLineCache localLines,
287: QSequenceLineCache latestLines, int baseLineCount)
288: throws IOException {
289: boolean conflict = false;
290: while (intersect(localChanges.current(), latestChanges
291: .current(), baseLineCount)
292: && !isEqualChange(localChanges.current(), latestChanges
293: .current(), localLines, latestLines)) {
294: conflict = true;
295:
296: if (localChanges.current().getLeftTo() <= latestChanges
297: .current().getLeftTo()) {
298: if (localChanges.hasNext()
299: && intersect(localChanges.peekNext(),
300: latestChanges.current(), baseLineCount)) {
301: localChanges.forward();
302: } else {
303: break;
304: }
305: } else {
306: if (latestChanges.hasNext()
307: && intersect(localChanges.current(),
308: latestChanges.peekNext(), baseLineCount)) {
309: latestChanges.forward();
310: } else {
311: break;
312: }
313: }
314: }
315: return conflict;
316: }
317:
318: private int createConflict(OutputStream result,
319: QSequenceDifferenceBlock localStart,
320: QSequenceDifferenceBlock localEnd,
321: QSequenceDifferenceBlock latestStart,
322: QSequenceDifferenceBlock latestEnd,
323: QSequenceLineCache localLines,
324: QSequenceLineCache latestLines, int baseLineIndex,
325: List transformedLocalLines) throws IOException {
326: final int minBaseFrom = Math.min(localStart.getLeftFrom(),
327: latestStart.getLeftFrom());
328: final int maxBaseTo = Math.max(localEnd.getLeftTo(), latestEnd
329: .getLeftTo());
330:
331: appendTransformedLocalLines(baseLineIndex, minBaseFrom,
332: transformedLocalLines, result);
333:
334: final int localFrom = Math.max(0, localStart.getRightFrom()
335: - (localStart.getLeftFrom() - minBaseFrom));
336: final int localTo = Math.min(localLines.getLineCount() - 1,
337: localEnd.getRightTo()
338: + (maxBaseTo - localEnd.getLeftTo()));
339: final int latestFrom = Math.max(0, latestStart.getRightFrom()
340: - (latestStart.getLeftFrom() - minBaseFrom));
341: final int latestTo = Math.min(latestLines.getLineCount() - 1,
342: latestEnd.getRightTo()
343: + (maxBaseTo - latestEnd.getLeftTo()));
344:
345: writeBytesAndEol(result, myConflictStart);
346: for (int index = localFrom; index <= localTo; index++) {
347: writeLine(result, localLines.getLine(index));
348: }
349: writeBytesAndEol(result, myConflictSeparator);
350: for (int index = latestFrom; index <= latestTo; index++) {
351: writeLine(result, latestLines.getLine(index));
352: }
353: writeBytesAndEol(result, myConflictEnd);
354:
355: return maxBaseTo;
356: }
357:
358: private void appendTransformedLocalLines(int baseLineIndex, int to,
359: List transformedLocalLines, OutputStream result)
360: throws IOException {
361: for (baseLineIndex++; baseLineIndex < to; baseLineIndex++) {
362: final QSequenceLine sequenceLine = (QSequenceLine) transformedLocalLines
363: .get(baseLineIndex);
364: if (sequenceLine == null) {
365: throw new RuntimeException();
366: }
367: writeLine(result, sequenceLine);
368: }
369: }
370:
371: private void writeLine(OutputStream os, QSequenceLine line)
372: throws IOException {
373: final byte[] bytes = line.getContentBytes();
374: if (bytes.length == 0) {
375: return;
376: }
377:
378: os.write(bytes);
379: }
380:
381: private void writeBytesAndEol(OutputStream os, final byte[] bytes)
382: throws IOException {
383: if (bytes.length > 0) {
384: os.write(bytes);
385: os.write(DEFAULT_EOL.getBytes());
386: }
387: }
388:
389: private QSequenceLineTeeSimplifier createSimplifier(
390: SVNDiffOptions options) {
391: final QSequenceLineSimplifier eolSimplifier = options != null
392: && options.isIgnoreEOLStyle() ? (QSequenceLineSimplifier) new QSequenceLineEOLUnifyingSimplifier()
393: : (QSequenceLineSimplifier) new QSequenceLineDummySimplifier();
394:
395: QSequenceLineSimplifier spaceSimplifier = new QSequenceLineDummySimplifier();
396: if (options != null) {
397: if (options.isIgnoreAllWhitespace()) {
398: spaceSimplifier = new QSequenceLineWhiteSpaceSkippingSimplifier();
399: } else if (options.isIgnoreAmountOfWhitespace()) {
400: spaceSimplifier = new QSequenceLineWhiteSpaceReducingSimplifier();
401: }
402: }
403: return new QSequenceLineTeeSimplifier(eolSimplifier,
404: spaceSimplifier);
405: }
406: }
|