0001: /*******************************************************************************
0002: * Copyright (c) 2000, 2006 IBM Corporation and others.
0003: * All rights reserved. This program and the accompanying materials
0004: * are made available under the terms of the Eclipse Public License v1.0
0005: * which accompanies this distribution, and is available at
0006: * http://www.eclipse.org/legal/epl-v10.html
0007: *
0008: * Contributors:
0009: * IBM Corporation - initial API and implementation
0010: *******************************************************************************/package org.eclipse.ui.internal.texteditor.quickdiff;
0011:
0012: import java.util.ArrayList;
0013: import java.util.ConcurrentModificationException;
0014: import java.util.Iterator;
0015: import java.util.LinkedList;
0016: import java.util.List;
0017: import java.util.ListIterator;
0018:
0019: import org.eclipse.core.runtime.Assert;
0020: import org.eclipse.core.runtime.CoreException;
0021: import org.eclipse.core.runtime.IProgressMonitor;
0022: import org.eclipse.core.runtime.IStatus;
0023: import org.eclipse.core.runtime.OperationCanceledException;
0024: import org.eclipse.core.runtime.Platform;
0025: import org.eclipse.core.runtime.Status;
0026: import org.eclipse.core.runtime.jobs.Job;
0027:
0028: import org.eclipse.jface.text.BadLocationException;
0029: import org.eclipse.jface.text.Document;
0030: import org.eclipse.jface.text.DocumentEvent;
0031: import org.eclipse.jface.text.DocumentRewriteSessionEvent;
0032: import org.eclipse.jface.text.DocumentRewriteSessionType;
0033: import org.eclipse.jface.text.IDocument;
0034: import org.eclipse.jface.text.IDocumentExtension4;
0035: import org.eclipse.jface.text.IDocumentListener;
0036: import org.eclipse.jface.text.IDocumentRewriteSessionListener;
0037: import org.eclipse.jface.text.IRegion;
0038: import org.eclipse.jface.text.ISynchronizable;
0039: import org.eclipse.jface.text.Position;
0040: import org.eclipse.jface.text.source.Annotation;
0041: import org.eclipse.jface.text.source.AnnotationModelEvent;
0042: import org.eclipse.jface.text.source.IAnnotationModel;
0043: import org.eclipse.jface.text.source.IAnnotationModelListener;
0044: import org.eclipse.jface.text.source.IAnnotationModelListenerExtension;
0045: import org.eclipse.jface.text.source.ILineDiffInfo;
0046: import org.eclipse.jface.text.source.ILineDiffer;
0047: import org.eclipse.jface.text.source.ILineDifferExtension;
0048: import org.eclipse.jface.text.source.ILineDifferExtension2;
0049: import org.eclipse.jface.text.source.ILineRange;
0050: import org.eclipse.jface.text.source.LineRange;
0051:
0052: import org.eclipse.ui.internal.texteditor.NLSUtility;
0053: import org.eclipse.ui.internal.texteditor.TextEditorPlugin;
0054: import org.eclipse.ui.internal.texteditor.quickdiff.compare.equivalence.DJBHashFunction;
0055: import org.eclipse.ui.internal.texteditor.quickdiff.compare.equivalence.DocEquivalenceComparator;
0056: import org.eclipse.ui.internal.texteditor.quickdiff.compare.equivalence.DocumentEquivalenceClass;
0057: import org.eclipse.ui.internal.texteditor.quickdiff.compare.equivalence.IHashFunction;
0058: import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.IRangeComparator;
0059: import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.RangeDifference;
0060: import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.RangeDifferencer;
0061: import org.eclipse.ui.progress.IProgressConstants;
0062: import org.eclipse.ui.texteditor.quickdiff.IQuickDiffReferenceProvider;
0063:
0064: /**
0065: * Standard implementation of <code>ILineDiffer</code> as an incremental diff engine. A
0066: * <code>DocumentLineDiffer</code> can be initialized to some start state. Once connected to a
0067: * <code>IDocument</code> and a reference document has been set, changes reported via the
0068: * <code>IDocumentListener</code> interface will be tracked and the incremental diff updated.
0069: *
0070: * <p>The diff state can be queried using the <code>ILineDiffer</code> interface.</p>
0071: *
0072: * <p>Since diff information is model information attached to a document, this class implements
0073: * <code>IAnnotationModel</code> and can be attached to <code>IAnnotationModelExtension</code>s.</p>
0074: *
0075: * <p>This class is not supposed to be subclassed.</p>
0076: *
0077: * @since 3.0
0078: */
0079: public class DocumentLineDiffer implements ILineDiffer,
0080: IDocumentListener, IAnnotationModel, ILineDifferExtension,
0081: ILineDifferExtension2 {
0082:
0083: /**
0084: * Artificial line difference information indicating a change with an empty line as original text.
0085: */
0086: private static class LineChangeInfo implements ILineDiffInfo {
0087:
0088: private static final String[] ORIGINAL_TEXT = new String[] { "\n" }; //$NON-NLS-1$
0089:
0090: /*
0091: * @see org.eclipse.jface.text.source.ILineDiffInfo#getRemovedLinesBelow()
0092: */
0093: public int getRemovedLinesBelow() {
0094: return 0;
0095: }
0096:
0097: /*
0098: * @see org.eclipse.jface.text.source.ILineDiffInfo#getRemovedLinesAbove()
0099: */
0100: public int getRemovedLinesAbove() {
0101: return 0;
0102: }
0103:
0104: /*
0105: * @see org.eclipse.jface.text.source.ILineDiffInfo#getChangeType()
0106: */
0107: public int getChangeType() {
0108: return CHANGED;
0109: }
0110:
0111: /*
0112: * @see org.eclipse.jface.text.source.ILineDiffInfo#hasChanges()
0113: */
0114: public boolean hasChanges() {
0115: return true;
0116: }
0117:
0118: /*
0119: * @see org.eclipse.jface.text.source.ILineDiffInfo#getOriginalText()
0120: */
0121: public String[] getOriginalText() {
0122: return ORIGINAL_TEXT;
0123: }
0124: }
0125:
0126: /** Tells whether this class is in debug mode. */
0127: private static boolean DEBUG = "true".equalsIgnoreCase(Platform.getDebugOption("org.eclipse.ui.workbench.texteditor/debug/DocumentLineDiffer")); //$NON-NLS-1$//$NON-NLS-2$
0128:
0129: /** The delay after which the initialization job is triggered. */
0130: private static final int INITIALIZE_DELAY = 500;
0131:
0132: /** Suspended state */
0133: private static final int SUSPENDED = 0;
0134: /** Initializing state */
0135: private static final int INITIALIZING = 1;
0136: /** Synchronized state */
0137: private static final int SYNCHRONIZED = 2;
0138:
0139: /** This differ's state */
0140: private int fState = SUSPENDED;
0141: /** Artificial line difference information indicating a change with an empty line as original text. */
0142: private final ILineDiffInfo fLineChangeInfo = new LineChangeInfo();
0143:
0144: /** The provider for the reference document. */
0145: IQuickDiffReferenceProvider fReferenceProvider;
0146: /** The number of clients connected to this model. */
0147: private int fOpenConnections;
0148: /** The current document being tracked. */
0149: private IDocument fLeftDocument;
0150: /**
0151: * The equivalence class of the left document.
0152: * @since 3.2
0153: */
0154: private DocumentEquivalenceClass fLeftEquivalent;
0155: /** The reference document. */
0156: private IDocument fRightDocument;
0157: /**
0158: * The equivalence class of the right document.
0159: * @since 3.2
0160: */
0161: private DocumentEquivalenceClass fRightEquivalent;
0162: /**
0163: * Flag to indicate whether a change has been made to the line table and any clients should
0164: * update their presentation.
0165: */
0166: private boolean fUpdateNeeded;
0167: /** The listeners on this annotation model. */
0168: private List fAnnotationModelListeners = new ArrayList();
0169: /** The job currently initializing the differ, or <code>null</code> if there is none. */
0170: private Job fInitializationJob;
0171: /** Stores <code>DocumentEvents</code> while an initialization is going on. */
0172: private List fStoredEvents = new ArrayList();
0173: /**
0174: * The differences between <code>fLeftDocument</code> and <code>fRightDocument</code>.
0175: * This is the model we work on.
0176: */
0177: private List fDifferences = new ArrayList();
0178: /**
0179: * The differences removed in one iteration. Stored to be able to send out differentiated
0180: * annotation events.
0181: */
0182: private List fRemoved = new ArrayList();
0183: /**
0184: * The differences added in one iteration. Stored to be able to send out differentiated
0185: * annotation events.
0186: */
0187: private List fAdded = new ArrayList();
0188: /**
0189: * The differences changed in one iteration. Stored to be able to send out differentiated
0190: * annotation events.
0191: */
0192: private List fChanged = new ArrayList();
0193: /** The first line affected by a document event. */
0194: private int fFirstLine;
0195: /** The number of lines affected by a document event. */
0196: private int fNLines;
0197: /** The most recent range difference returned in a getLineInfo call, so it can be recyled. */
0198: private RangeDifference fLastDifference;
0199: /**
0200: * <code>true</code> if incoming document events should be ignored,
0201: * <code>false</code> if not.
0202: */
0203: private boolean fIgnoreDocumentEvents = true;
0204: /**
0205: * The listener for document rewrite sessions.
0206: * @since 3.2
0207: */
0208: private final IDocumentRewriteSessionListener fSessionListener = new IDocumentRewriteSessionListener() {
0209: public void documentRewriteSessionChanged(
0210: DocumentRewriteSessionEvent event) {
0211: if (event.getSession().getSessionType() == DocumentRewriteSessionType.UNRESTRICTED_SMALL)
0212: return;
0213: if (DocumentRewriteSessionEvent.SESSION_START.equals(event
0214: .getChangeType()))
0215: suspend();
0216: else if (DocumentRewriteSessionEvent.SESSION_STOP
0217: .equals(event.getChangeType()))
0218: resume();
0219: }
0220: };
0221:
0222: private Thread fThread;
0223: private DocumentEvent fLastUIEvent;
0224:
0225: /**
0226: * Creates a new differ.
0227: */
0228: public DocumentLineDiffer() {
0229: }
0230:
0231: /* ILineDiffer implementation */
0232:
0233: /*
0234: * @see org.eclipse.jface.text.source.ILineDiffer#getLineInfo(int)
0235: */
0236: public ILineDiffInfo getLineInfo(int line) {
0237:
0238: if (isSuspended())
0239: return fLineChangeInfo;
0240:
0241: // try cache first / speeds up linear search
0242: RangeDifference last = fLastDifference;
0243: if (last != null && last.rightStart() <= line
0244: && last.rightEnd() > line)
0245: return new DiffRegion(last, line - last.rightStart(),
0246: fDifferences, fLeftDocument);
0247:
0248: fLastDifference = getRangeDifferenceForRightLine(line);
0249: last = fLastDifference;
0250: if (last != null)
0251: return new DiffRegion(last, line - last.rightStart(),
0252: fDifferences, fLeftDocument);
0253:
0254: return null;
0255: }
0256:
0257: /*
0258: * @see org.eclipse.jface.text.source.ILineDiffer#revertLine(int)
0259: */
0260: public synchronized void revertLine(int line)
0261: throws BadLocationException {
0262: if (!isInitialized())
0263: throw new BadLocationException(
0264: QuickDiffMessages.quickdiff_nonsynchronized);
0265:
0266: DiffRegion region = (DiffRegion) getLineInfo(line);
0267: if (region == null || fRightDocument == null
0268: || fLeftDocument == null)
0269: return;
0270:
0271: RangeDifference diff = region.getDifference();
0272: int rOffset = fRightDocument.getLineOffset(line);
0273: int rLength = fRightDocument.getLineLength(line);
0274: int leftLine = diff.leftStart() + region.getOffset();
0275: String replacement;
0276: if (leftLine >= diff.leftEnd()) // restoring a deleted line?
0277: replacement = ""; //$NON-NLS-1$
0278: else {
0279: int lOffset = fLeftDocument.getLineOffset(leftLine);
0280: int lLength = fLeftDocument.getLineLength(leftLine);
0281: replacement = fLeftDocument.get(lOffset, lLength);
0282: }
0283: fRightDocument.replace(rOffset, rLength, replacement);
0284: }
0285:
0286: /*
0287: * @see org.eclipse.jface.text.source.ILineDiffer#revertBlock(int)
0288: */
0289: public synchronized void revertBlock(int line)
0290: throws BadLocationException {
0291: if (!isInitialized())
0292: throw new BadLocationException(
0293: QuickDiffMessages.quickdiff_nonsynchronized);
0294:
0295: DiffRegion region = (DiffRegion) getLineInfo(line);
0296: if (region == null || fRightDocument == null
0297: || fLeftDocument == null)
0298: return;
0299:
0300: RangeDifference diff = region.getDifference();
0301: int rOffset = fRightDocument.getLineOffset(diff.rightStart());
0302: int rLength = fRightDocument.getLineOffset(diff.rightEnd() - 1)
0303: + fRightDocument.getLineLength(diff.rightEnd() - 1)
0304: - rOffset;
0305: int lOffset = fLeftDocument.getLineOffset(diff.leftStart());
0306: int lLength = fLeftDocument.getLineOffset(diff.leftEnd() - 1)
0307: + fLeftDocument.getLineLength(diff.leftEnd() - 1)
0308: - lOffset;
0309: fRightDocument.replace(rOffset, rLength, fLeftDocument.get(
0310: lOffset, lLength));
0311: }
0312:
0313: /*
0314: * @see org.eclipse.jface.text.source.ILineDiffer#revertSelection(int, int)
0315: */
0316: public synchronized void revertSelection(int line, int nLines)
0317: throws BadLocationException {
0318: if (!isInitialized())
0319: throw new BadLocationException(
0320: QuickDiffMessages.quickdiff_nonsynchronized);
0321:
0322: if (fRightDocument == null || fLeftDocument == null)
0323: return;
0324:
0325: int rOffset = -1, rLength = -1, lOffset = -1, lLength = -1;
0326: RangeDifference diff = null;
0327: final List differences = fDifferences;
0328: synchronized (differences) {
0329: Iterator it = differences.iterator();
0330:
0331: // get start
0332: while (it.hasNext()) {
0333: diff = (RangeDifference) it.next();
0334: if (line < diff.rightEnd()) {
0335: rOffset = fRightDocument.getLineOffset(line);
0336: int leftLine = Math.min(diff.leftStart() + line
0337: - diff.rightStart(), diff.leftEnd() - 1);
0338: lOffset = fLeftDocument.getLineOffset(leftLine);
0339: break;
0340: }
0341: }
0342:
0343: if (rOffset == -1 || lOffset == -1)
0344: return;
0345:
0346: // get end / length
0347: int to = line + nLines - 1;
0348: while (it.hasNext()) {
0349: diff = (RangeDifference) it.next();
0350: if (to < diff.rightEnd()) {
0351: int rEndOffset = fRightDocument.getLineOffset(to)
0352: + fRightDocument.getLineLength(to);
0353: rLength = rEndOffset - rOffset;
0354: int leftLine = Math.min(diff.leftStart() + to
0355: - diff.rightStart(), diff.leftEnd() - 1);
0356: int lEndOffset = fLeftDocument
0357: .getLineOffset(leftLine)
0358: + fLeftDocument.getLineLength(leftLine);
0359: lLength = lEndOffset - lOffset;
0360: break;
0361: }
0362: }
0363: }
0364:
0365: if (rLength == -1 || lLength == -1)
0366: return;
0367:
0368: fRightDocument.replace(rOffset, rLength, fLeftDocument.get(
0369: lOffset, lLength));
0370: }
0371:
0372: /*
0373: * @see org.eclipse.jface.text.source.ILineDiffer#restoreAfterLine(int)
0374: */
0375: public synchronized int restoreAfterLine(int line)
0376: throws BadLocationException {
0377: if (!isInitialized())
0378: throw new BadLocationException(
0379: QuickDiffMessages.quickdiff_nonsynchronized);
0380:
0381: DiffRegion region = (DiffRegion) getLineInfo(line);
0382: if (region == null || fRightDocument == null
0383: || fLeftDocument == null)
0384: return 0;
0385:
0386: if (region.getRemovedLinesBelow() < 1)
0387: return 0;
0388:
0389: RangeDifference diff = null;
0390: final List differences = fDifferences;
0391: synchronized (differences) {
0392: for (Iterator it = differences.iterator(); it.hasNext();) {
0393: diff = (RangeDifference) it.next();
0394: if (line >= diff.rightStart() && line < diff.rightEnd()) {
0395: if (diff.kind() == RangeDifference.NOCHANGE
0396: && it.hasNext())
0397: diff = (RangeDifference) it.next();
0398: break;
0399: }
0400: }
0401: }
0402:
0403: if (diff == null)
0404: return 0;
0405:
0406: int rOffset = fRightDocument.getLineOffset(diff.rightEnd());
0407: int rLength = 0;
0408: int leftLine = diff.leftStart() + diff.rightLength();
0409: int lOffset = fLeftDocument.getLineOffset(leftLine);
0410: int lLength = fLeftDocument.getLineOffset(diff.leftEnd() - 1)
0411: + fLeftDocument.getLineLength(diff.leftEnd() - 1)
0412: - lOffset;
0413: fRightDocument.replace(rOffset, rLength, fLeftDocument.get(
0414: lOffset, lLength));
0415:
0416: return diff.leftLength() - diff.rightLength();
0417: }
0418:
0419: /**
0420: * Returns the receivers initialization state.
0421: *
0422: * @return <code>true</code> if we are initialized and in sync with the document.
0423: */
0424: private boolean isInitialized() {
0425: return fState == SYNCHRONIZED;
0426: }
0427:
0428: /**
0429: * Returns the receivers synchronization state.
0430: *
0431: * @return <code>true</code> if we are initialized and in sync with the document.
0432: */
0433: public synchronized boolean isSynchronized() {
0434: return fState == SYNCHRONIZED;
0435: }
0436:
0437: /**
0438: * Returns <code>true</code> if the differ is suspended.
0439: *
0440: * @return <code>true</code> if the differ is suspended
0441: */
0442: public synchronized boolean isSuspended() {
0443: return fState == SUSPENDED;
0444: }
0445:
0446: /**
0447: * Sets the reference provider for this instance. If one has been installed before, it is
0448: * disposed.
0449: *
0450: * @param provider the new provider
0451: */
0452: public void setReferenceProvider(
0453: IQuickDiffReferenceProvider provider) {
0454: Assert.isNotNull(provider);
0455: if (provider != fReferenceProvider) {
0456: if (fReferenceProvider != null)
0457: fReferenceProvider.dispose();
0458: fReferenceProvider = provider;
0459: initialize();
0460: }
0461: }
0462:
0463: /**
0464: * Returns the reference provider currently installed, or <code>null</code> if none is installed.
0465: *
0466: * @return the current reference provider.
0467: */
0468: public IQuickDiffReferenceProvider getReferenceProvider() {
0469: return fReferenceProvider;
0470: }
0471:
0472: /**
0473: * (Re-)initializes the differ using the current reference and <code>DiffInitializer</code>.
0474: *
0475: * @since 3.2 protected for testing reasons, package visible before
0476: */
0477: protected synchronized void initialize() {
0478: // make new incoming changes go into the queue of stored events, plus signal we can't restore.
0479: fState = INITIALIZING;
0480:
0481: if (fRightDocument == null)
0482: return;
0483:
0484: // there is no point in receiving updates before the job we get a new copy of the document for diffing
0485: fIgnoreDocumentEvents = true;
0486:
0487: if (fLeftDocument != null) {
0488: fLeftDocument.removeDocumentListener(this );
0489: fLeftDocument = null;
0490: fLeftEquivalent = null;
0491: }
0492:
0493: // if there already is a job:
0494: // return if it has not started yet, cancel it if already running
0495: final Job oldJob = fInitializationJob;
0496: if (oldJob != null) {
0497: // don't chain up jobs if there is one waiting already.
0498: if (oldJob.getState() == Job.WAITING) {
0499: oldJob.wakeUp(INITIALIZE_DELAY);
0500: return;
0501: }
0502: oldJob.cancel();
0503: }
0504:
0505: fInitializationJob = new Job(
0506: QuickDiffMessages.quickdiff_initialize) {
0507:
0508: /*
0509: * This is run in a different thread. As the documents might be synchronized, never ever
0510: * access the documents in a synchronized section or expect deadlocks. See
0511: * https://bugs.eclipse.org/bugs/show_bug.cgi?id=44692
0512: */
0513: public IStatus run(IProgressMonitor monitor) {
0514:
0515: // 1: wait for any previous job that was canceled to avoid job flooding
0516: // It will return relatively quickly as RangeDifferencer supports canceling
0517: if (oldJob != null)
0518: try {
0519: oldJob.join();
0520: } catch (InterruptedException e) {
0521: // will not happen as no one interrupts our thread
0522: Assert.isTrue(false);
0523: }
0524:
0525: // 2: get the reference document
0526: IQuickDiffReferenceProvider provider = fReferenceProvider;
0527: final IDocument left;
0528: try {
0529: left = provider == null ? null : provider
0530: .getReference(monitor);
0531: } catch (CoreException e) {
0532: synchronized (DocumentLineDiffer.this ) {
0533: if (isCanceled(monitor))
0534: return Status.CANCEL_STATUS;
0535:
0536: clearModel();
0537: fireModelChanged();
0538: return e.getStatus();
0539: }
0540: } catch (OperationCanceledException e) {
0541: return Status.CANCEL_STATUS;
0542: }
0543:
0544: // Getting our own copies of the documents for offline diffing.
0545: //
0546: // We need to make sure that we do get all document modifications after
0547: // copying the documents as we want to re-inject them later on to become consistent.
0548:
0549: IDocument right = fRightDocument; // fRightDocument, but not subject to change
0550: IDocument actual = null; // the copy of the actual (right) document
0551: IDocument reference = null; // the copy of the reference (left) document
0552:
0553: synchronized (DocumentLineDiffer.this ) {
0554: // 4: take an early exit if the documents are not valid
0555: if (left == null || right == null) {
0556: if (isCanceled(monitor))
0557: return Status.CANCEL_STATUS;
0558:
0559: clearModel();
0560: fireModelChanged();
0561: return Status.OK_STATUS;
0562: }
0563:
0564: // set the reference document
0565: fLeftDocument = left;
0566: // start listening to document events.
0567: fIgnoreDocumentEvents = false;
0568: }
0569:
0570: // accessing the reference document from a different thread - reference providers need
0571: // to be able to deal with this.
0572: left.addDocumentListener(DocumentLineDiffer.this );
0573:
0574: // create the reference copy - note that any changes on the
0575: // reference will trigger re-initialization anyway
0576: reference = createCopy(left);
0577: if (reference == null)
0578: return Status.CANCEL_STATUS;
0579:
0580: // create the actual copy
0581:
0582: Object lock = null;
0583: if (right instanceof ISynchronizable)
0584: lock = ((ISynchronizable) right).getLockObject();
0585:
0586: if (lock != null) {
0587: // a) if we can, acquire locks in proper order and copy
0588: // the document
0589: synchronized (lock) {
0590: synchronized (DocumentLineDiffer.this ) {
0591: if (isCanceled(monitor))
0592: return Status.CANCEL_STATUS;
0593: fStoredEvents.clear();
0594: actual = createUnprotectedCopy(right);
0595: }
0596: }
0597: } else {
0598: // b) cannot lock the document
0599: // Now this is fun. The reference documents may be PartiallySynchronizedDocuments
0600: // which will result in a deadlock if they get changed externally before we get
0601: // our exclusive copies.
0602: // Here's what we do: we try over and over (without synchronization) to get copies
0603: // without interleaving modification. If there is a document change, we just repeat.
0604: int i = 0;
0605: do {
0606: // this is an arbitrary emergency exit in case a referenced document goes nuts
0607: if (i++ == 100)
0608: return new Status(
0609: IStatus.ERROR,
0610: TextEditorPlugin.PLUGIN_ID,
0611: IStatus.OK,
0612: NLSUtility
0613: .format(
0614: QuickDiffMessages.quickdiff_error_getting_document_content,
0615: new Object[] {
0616: left
0617: .getClass(),
0618: right
0619: .getClass() }),
0620: null);
0621:
0622: synchronized (DocumentLineDiffer.this ) {
0623: if (isCanceled(monitor))
0624: return Status.CANCEL_STATUS;
0625:
0626: fStoredEvents.clear();
0627: }
0628:
0629: // access documents non synchronized:
0630: // get an exclusive copy of the actual document
0631: actual = createCopy(right);
0632:
0633: synchronized (DocumentLineDiffer.this ) {
0634: if (isCanceled(monitor))
0635: return Status.CANCEL_STATUS;
0636: if (fStoredEvents.size() == 0
0637: && actual != null)
0638: break;
0639: }
0640: } while (true);
0641: }
0642:
0643: IHashFunction hash = new DJBHashFunction();
0644: DocumentEquivalenceClass leftEquivalent = new DocumentEquivalenceClass(
0645: reference, hash);
0646: fLeftEquivalent = leftEquivalent;
0647: IRangeComparator ref = new DocEquivalenceComparator(
0648: leftEquivalent, null);
0649:
0650: DocumentEquivalenceClass rightEquivalent = new DocumentEquivalenceClass(
0651: actual, hash);
0652: fRightEquivalent = rightEquivalent;
0653: IRangeComparator act = new DocEquivalenceComparator(
0654: rightEquivalent, null);
0655: List diffs = RangeDifferencer.findRanges(monitor, ref,
0656: act);
0657: // 7: Reset the model to the just gotten differences
0658: // re-inject stored events to get up to date.
0659: synchronized (DocumentLineDiffer.this ) {
0660: if (isCanceled(monitor))
0661: return Status.CANCEL_STATUS;
0662:
0663: // set the new differences so we can operate on them
0664: fDifferences = diffs;
0665: }
0666:
0667: // re-inject events accumulated in the meantime.
0668: try {
0669: do {
0670: DocumentEvent event;
0671: synchronized (DocumentLineDiffer.this ) {
0672: if (isCanceled(monitor))
0673: return Status.CANCEL_STATUS;
0674:
0675: if (fStoredEvents.isEmpty()) {
0676: // we are back in sync with the life documents
0677: fInitializationJob = null;
0678: fState = SYNCHRONIZED;
0679: fLastDifference = null;
0680:
0681: // replace the private documents with the actual
0682: leftEquivalent.setDocument(left);
0683: rightEquivalent.setDocument(right);
0684:
0685: break;
0686: }
0687:
0688: event = (DocumentEvent) fStoredEvents
0689: .remove(0);
0690: }
0691:
0692: // access documents non synchronized:
0693: IDocument copy = null;
0694: if (event.fDocument == right)
0695: copy = actual;
0696: else if (event.fDocument == left)
0697: copy = reference;
0698: else
0699: Assert.isTrue(false);
0700:
0701: // copy the event to inject it into our diff copies
0702: // don't modify the original event! See https://bugs.eclipse.org/bugs/show_bug.cgi?id=134227
0703: event = new DocumentEvent(copy, event.fOffset,
0704: event.fLength, event.fText);
0705: handleAboutToBeChanged(event);
0706:
0707: // inject the event into our private copy
0708: actual.replace(event.fOffset, event.fLength,
0709: event.fText);
0710:
0711: handleChanged(event);
0712:
0713: } while (true);
0714:
0715: } catch (BadLocationException e) {
0716: left
0717: .removeDocumentListener(DocumentLineDiffer.this );
0718: clearModel();
0719: initialize();
0720: return Status.CANCEL_STATUS;
0721: }
0722:
0723: fireModelChanged();
0724: return Status.OK_STATUS;
0725: }
0726:
0727: private boolean isCanceled(IProgressMonitor monitor) {
0728: return fInitializationJob != this || monitor != null
0729: && monitor.isCanceled();
0730: }
0731:
0732: private void clearModel() {
0733: synchronized (DocumentLineDiffer.this ) {
0734: fLeftDocument = null;
0735: fLeftEquivalent = null;
0736: fInitializationJob = null;
0737: fStoredEvents.clear();
0738: fLastDifference = null;
0739: fDifferences.clear();
0740: }
0741: }
0742:
0743: /**
0744: * Creates a copy of <code>document</code> and catches any
0745: * exceptions that may occur if the document is modified concurrently.
0746: * Only call this method in a synchronized block if the document is
0747: * an ISynchronizable and has been locked, as document.get() is called
0748: * and may result in a deadlock otherwise.
0749: *
0750: * @param document the document to create a copy of
0751: * @return a copy of the document, or <code>null</code> if an exception was thrown
0752: */
0753: private IDocument createCopy(IDocument document) {
0754: Assert.isNotNull(document);
0755: // this fixes https://bugs.eclipse.org/bugs/show_bug.cgi?id=56091
0756: try {
0757: return createUnprotectedCopy(document);
0758: } catch (NullPointerException e) {
0759: } catch (ArrayStoreException e) {
0760: } catch (IndexOutOfBoundsException e) {
0761: } catch (ConcurrentModificationException e) {
0762: } catch (NegativeArraySizeException e) {
0763: }
0764: return null;
0765: }
0766:
0767: private IDocument createUnprotectedCopy(IDocument document) {
0768: return new Document(document.get());
0769: }
0770: };
0771:
0772: fInitializationJob.setSystem(true);
0773: fInitializationJob.setPriority(Job.DECORATE);
0774: fInitializationJob.setProperty(
0775: IProgressConstants.NO_IMMEDIATE_ERROR_PROMPT_PROPERTY,
0776: Boolean.TRUE);
0777: fInitializationJob.schedule(INITIALIZE_DELAY);
0778: }
0779:
0780: /* IDocumentListener implementation */
0781:
0782: /*
0783: * @see org.eclipse.jface.text.IDocumentListener#documentAboutToBeChanged(org.eclipse.jface.text.DocumentEvent)
0784: */
0785: public synchronized void documentAboutToBeChanged(
0786: DocumentEvent event) {
0787: if (fIgnoreDocumentEvents)
0788: return;
0789:
0790: if (event.getDocument() == fLeftDocument) { // TODO twoside
0791: initialize();
0792: return;
0793: }
0794:
0795: // if a initialization is going on, we just store the events in the meantime
0796: if (!isInitialized()) {
0797: if (fInitializationJob != null)
0798: fStoredEvents.add(event);
0799: return;
0800: }
0801:
0802: fLastUIEvent = event;
0803: try {
0804: handleAboutToBeChanged(event);
0805: } catch (BadLocationException e) {
0806: reinitOnError(e);
0807: return;
0808: } catch (NullPointerException e) {
0809: reinitOnError(e);
0810: return;
0811: } catch (ArrayStoreException e) {
0812: reinitOnError(e);
0813: return;
0814: } catch (IndexOutOfBoundsException e) {
0815: reinitOnError(e);
0816: return;
0817: } catch (ConcurrentModificationException e) {
0818: reinitOnError(e);
0819: return;
0820: } catch (NegativeArraySizeException e) {
0821: reinitOnError(e);
0822: return;
0823: }
0824: }
0825:
0826: /**
0827: * Unsynchronized version of <code>documentAboutToBeChanged</code>, called by <code>documentAboutToBeChanged</code>
0828: * and {@link #initialize()}.
0829: *
0830: * @param event the document event to be handled
0831: * @throws BadLocationException if document access fails
0832: */
0833: void handleAboutToBeChanged(DocumentEvent event)
0834: throws BadLocationException {
0835: Assert.isTrue(fThread == null);
0836: fThread = Thread.currentThread();
0837:
0838: IDocument doc = event.getDocument();
0839: DocumentEquivalenceClass rightEquivalent = fRightEquivalent;
0840:
0841: if (doc == null || rightEquivalent == null)
0842: return;
0843:
0844: // store size of replaced region (never synchronized -> not a problem)
0845: fFirstLine = doc.getLineOfOffset(event.getOffset()); // store change bounding lines
0846: fNLines = doc.getLineOfOffset(event.getOffset()
0847: + event.getLength())
0848: - fFirstLine + 1;
0849: rightEquivalent.update(event);
0850: }
0851:
0852: /*
0853: * @see org.eclipse.jface.text.IDocumentListener#documentChanged(org.eclipse.jface.text.DocumentEvent)
0854: */
0855: public synchronized void documentChanged(DocumentEvent event) {
0856: final Thread lastCurrentThread = fThread;
0857: fThread = null;
0858:
0859: if (fIgnoreDocumentEvents)
0860: return;
0861:
0862: // https://bugs.eclipse.org/bugs/show_bug.cgi?id=44692
0863: // don't allow incremental update for changes from the reference document
0864: // as this could deadlock
0865: if (event.getDocument() == fLeftDocument) { // TODO twoside
0866: initialize();
0867: return;
0868: }
0869:
0870: if (event != fLastUIEvent) {
0871: fLastUIEvent = null;
0872: return;
0873: }
0874: fLastUIEvent = null;
0875:
0876: if (!isInitialized())
0877: return;
0878:
0879: try {
0880: fThread = lastCurrentThread;
0881: handleChanged(event);
0882: } catch (BadLocationException e) {
0883: reinitOnError(e);
0884: return;
0885: } catch (NullPointerException e) {
0886: reinitOnError(e);
0887: return;
0888: } catch (ArrayStoreException e) {
0889: reinitOnError(e);
0890: return;
0891: } catch (IndexOutOfBoundsException e) {
0892: reinitOnError(e);
0893: return;
0894: } catch (ConcurrentModificationException e) {
0895: reinitOnError(e);
0896: return;
0897: } catch (NegativeArraySizeException e) {
0898: reinitOnError(e);
0899: return;
0900: }
0901:
0902: // inform listeners about change
0903: if (fUpdateNeeded) {
0904: AnnotationModelEvent ame = new AnnotationModelEvent(this ,
0905: false);
0906: for (Iterator it = fAdded.iterator(); it.hasNext();) {
0907: RangeDifference rd = (RangeDifference) it.next();
0908: ame.annotationAdded(rd.getDiffRegion(fDifferences,
0909: fLeftDocument));
0910: }
0911: for (Iterator it = fRemoved.iterator(); it.hasNext();) {
0912: RangeDifference rd = (RangeDifference) it.next();
0913: ame.annotationRemoved(rd.getDiffRegion(fDifferences,
0914: fLeftDocument));
0915: }
0916: for (Iterator it = fChanged.iterator(); it.hasNext();) {
0917: RangeDifference rd = (RangeDifference) it.next();
0918: ame.annotationChanged(rd.getDiffRegion(fDifferences,
0919: fLeftDocument));
0920: }
0921: fireModelChanged(ame);
0922: fUpdateNeeded = false;
0923: }
0924: }
0925:
0926: /**
0927: * Re-initializes the differ if an exception is thrown upon accessing the documents. This can
0928: * happen if the documents get concurrently modified from a background thread.
0929: *
0930: * @param e the exception thrown, which is logged in debug mode
0931: */
0932: private void reinitOnError(Exception e) {
0933: if (DEBUG)
0934: System.err
0935: .println("reinitializing quickdiff:\n" + e.getLocalizedMessage() + "\n" + e.getStackTrace()); //$NON-NLS-1$//$NON-NLS-2$
0936: initialize();
0937: }
0938:
0939: /**
0940: * Implementation of documentChanged, non synchronized.
0941: *
0942: * @param event the document event
0943: * @throws BadLocationException if document access fails somewhere
0944: */
0945: void handleChanged(DocumentEvent event) throws BadLocationException {
0946: Assert.isTrue(fThread == Thread.currentThread());
0947: fThread = null;
0948:
0949: // see https://bugs.eclipse.org/bugs/show_bug.cgi?id=132125
0950: IDocument left = fLeftDocument;
0951: DocumentEquivalenceClass leftEquivalent = fLeftEquivalent;
0952: DocumentEquivalenceClass rightEquivalent = fRightEquivalent;
0953: if (left == null || leftEquivalent == null
0954: || rightEquivalent == null)
0955: return;
0956:
0957: // documents: left, right; modified and unchanged are either of both
0958: IDocument right = event.getDocument(); // TODO two-side
0959: IDocument modified = event.getDocument();
0960: if (modified != left && modified != right)
0961: Assert.isTrue(false);
0962:
0963: boolean leftToRight = modified == left;
0964:
0965: String insertion = event.getText();
0966: int added = insertion == null ? 1 : modified
0967: .computeNumberOfLines(insertion) + 1;
0968: // size: the size of the document change in lines
0969:
0970: // put an upper bound to the delay we can afford
0971: if (added > 50 || fNLines > 50) {
0972: initialize();
0973: return;
0974: }
0975:
0976: int size = Math.max(fNLines, added) + 1;
0977: int lineDelta = added - fNLines;
0978: int lastLine = fFirstLine + fNLines - 1;
0979:
0980: int repetitionField;
0981: if (leftToRight) {
0982: int originalLine = getRightLine(lastLine + 1);
0983: repetitionField = searchForRepetitionField(size - 1, right,
0984: originalLine);
0985: } else {
0986: int originalLine = getLeftLine(lastLine + 1);
0987: repetitionField = searchForRepetitionField(size - 1, left,
0988: originalLine);
0989: }
0990: lastLine += repetitionField;
0991:
0992: // get enclosing range: search for a consistent block of at least the size of our
0993: // change before and after the change.
0994: final RangeDifference consistentBefore, consistentAfter;
0995: if (leftToRight) {
0996: consistentBefore = findConsistentRangeBeforeLeft(
0997: fFirstLine, size);
0998: consistentAfter = findConsistentRangeAfterLeft(lastLine,
0999: size);
1000: } else {
1001: consistentBefore = findConsistentRangeBeforeRight(
1002: fFirstLine, size);
1003: consistentAfter = findConsistentRangeAfterRight(lastLine,
1004: size);
1005: }
1006:
1007: // optimize unchanged blocks: if the consistent blocks around the change are larger than
1008: // size, we redimension them (especially important when there are only few changes.
1009: int shiftBefore = 0;
1010: if (consistentBefore.kind() == RangeDifference.NOCHANGE) {
1011: int unchanged;
1012: if (leftToRight)
1013: unchanged = Math.min(fFirstLine, consistentBefore
1014: .leftEnd())
1015: - consistentBefore.leftStart();
1016: else
1017: unchanged = Math.min(fFirstLine, consistentBefore
1018: .rightEnd())
1019: - consistentBefore.rightStart();
1020:
1021: shiftBefore = Math.max(0, unchanged - size);
1022: }
1023:
1024: int shiftAfter = 0;
1025: if (consistentAfter.kind() == RangeDifference.NOCHANGE) {
1026: int unchanged;
1027: if (leftToRight)
1028: unchanged = consistentAfter.leftEnd()
1029: - Math.max(lastLine + 1, consistentAfter
1030: .leftStart());
1031: else
1032: unchanged = consistentAfter.rightEnd()
1033: - Math.max(lastLine + 1, consistentAfter
1034: .rightStart());
1035:
1036: shiftAfter = Math.max(0, unchanged - size);
1037: }
1038:
1039: // get the document regions that will be rediffed, take into account that on the
1040: // document, the change has already happened.
1041: // left (reference) document
1042: int leftStartLine = consistentBefore.leftStart() + shiftBefore;
1043: int leftLine = consistentAfter.leftEnd();
1044: if (leftToRight)
1045: leftLine += lineDelta;
1046: int leftEndLine = leftLine - shiftAfter;
1047: ILineRange leftRange = new LineRange(leftStartLine, leftEndLine
1048: - leftStartLine);
1049: IRangeComparator reference = new DocEquivalenceComparator(
1050: leftEquivalent, leftRange);
1051:
1052: // right (actual) document
1053: int rightStartLine = consistentBefore.rightStart()
1054: + shiftBefore;
1055: int rightLine = consistentAfter.rightEnd();
1056: if (!leftToRight)
1057: rightLine += lineDelta;
1058: int rightEndLine = rightLine - shiftAfter;
1059: ILineRange rightRange = new LineRange(rightStartLine,
1060: rightEndLine - rightStartLine);
1061: IRangeComparator change = new DocEquivalenceComparator(
1062: rightEquivalent, rightRange);
1063:
1064: // put an upper bound to the delay we can afford
1065: if (leftLine - shiftAfter - leftStartLine > 50
1066: || rightLine - shiftAfter - rightStartLine > 50) {
1067: initialize();
1068: return;
1069: }
1070:
1071: // debug
1072: // System.out.println("compare window: "+size+"\n\n<" + left.get(leftRegion.getOffset(), leftRegion.getLength()) + //$NON-NLS-1$//$NON-NLS-2$
1073: // ">\n\n<" + right.get(rightRegion.getOffset(), rightRegion.getLength()) + ">\n"); //$NON-NLS-1$ //$NON-NLS-2$
1074:
1075: // compare
1076: List diffs = RangeDifferencer.findRanges(reference, change);
1077: if (diffs.size() == 0) {
1078: diffs.add(new RangeDifference(RangeDifference.CHANGE, 0, 0,
1079: 0, 0));
1080: }
1081:
1082: // shift the partial diffs to the absolute document positions
1083: for (Iterator it = diffs.iterator(); it.hasNext();) {
1084: RangeDifference d = (RangeDifference) it.next();
1085: d.shiftLeft(leftStartLine);
1086: d.shiftRight(rightStartLine);
1087: }
1088:
1089: // undo optimization shifting
1090: if (shiftBefore > 0) {
1091: RangeDifference first = (RangeDifference) diffs.get(0);
1092: if (first.kind() == RangeDifference.NOCHANGE)
1093: first.extendStart(-shiftBefore);
1094: else
1095: diffs.add(0, new RangeDifference(
1096: RangeDifference.NOCHANGE, first.rightStart()
1097: - shiftBefore, shiftBefore, first
1098: .leftStart()
1099: - shiftBefore, shiftBefore));
1100: }
1101:
1102: RangeDifference last = (RangeDifference) diffs
1103: .get(diffs.size() - 1);
1104: if (shiftAfter > 0) {
1105: if (last.kind() == RangeDifference.NOCHANGE)
1106: last.extendEnd(shiftAfter);
1107: else
1108: diffs.add(new RangeDifference(RangeDifference.NOCHANGE,
1109: last.rightEnd(), shiftAfter, last.leftEnd(),
1110: shiftAfter));
1111: }
1112:
1113: // replace changed diff range
1114: synchronized (fDifferences) {
1115: final ListIterator it = fDifferences.listIterator();
1116: Iterator newIt = diffs.iterator();
1117: RangeDifference current;
1118: boolean changed = false;
1119:
1120: // replace regions from consistentBefore to consistentAfter with new diffs
1121:
1122: // search for consistentBefore
1123: do {
1124: Assert.isTrue(it.hasNext());
1125: current = (RangeDifference) it.next();
1126: } while (current != consistentBefore);
1127: Assert.isTrue(current == consistentBefore);
1128:
1129: fChanged.clear();
1130: fRemoved.clear();
1131: fAdded.clear();
1132:
1133: // replace until consistentAfter
1134: while (current != consistentAfter) {
1135: if (newIt.hasNext()) {
1136: Object o = newIt.next();
1137: if (!current.equals(o)) {
1138: fRemoved.add(current);
1139: fAdded.add(o);
1140: changed = true;
1141: it.set(o);
1142: }
1143: } else {
1144: fRemoved.add(current);
1145: it.remove();
1146: changed = true;
1147: }
1148: Assert.isTrue(it.hasNext());
1149: current = (RangeDifference) it.next();
1150: }
1151:
1152: // replace consistentAfter
1153: Assert.isTrue(current == consistentAfter);
1154: if (newIt.hasNext()) {
1155: Object o = newIt.next();
1156: if (!current.equals(o)) {
1157: fRemoved.add(current);
1158: fAdded.add(o);
1159: changed = true;
1160: it.set(o);
1161: }
1162: } else {
1163: fRemoved.add(current);
1164: it.remove();
1165: changed = true;
1166: }
1167:
1168: // add remaining new diffs
1169: while (newIt.hasNext()) {
1170: Object next = newIt.next();
1171: fAdded.add(next);
1172: it.add(next);
1173: changed = true;
1174: }
1175:
1176: // shift the old remaining diffs
1177: boolean init = true;
1178: int leftShift = 0;
1179: int rightShift = 0;
1180: while (it.hasNext()) {
1181: current = (RangeDifference) it.next();
1182: if (init) {
1183: init = false;
1184: leftShift = last.leftEnd() - current.leftStart();
1185: rightShift = last.rightEnd() - current.rightStart();
1186: if (leftShift != 0 || rightShift != 0)
1187: changed = true;
1188: else
1189: break;
1190: }
1191: // fChanged.add(current); // not needed since positional shifting is not handled by an annotation model
1192: current.shiftLeft(leftShift);
1193: current.shiftRight(rightShift);
1194: }
1195:
1196: fUpdateNeeded = changed;
1197: }
1198:
1199: fLastDifference = null;
1200: }
1201:
1202: /**
1203: * Finds a consistent range of at least size before <code>line</code> in the left document.
1204: *
1205: * @param line the line before which the range has to occur
1206: * @param size the minimal size of the range
1207: * @return the first range found, or the first range in the differ if none can be found
1208: */
1209: private RangeDifference findConsistentRangeBeforeLeft(int line,
1210: int size) {
1211: RangeDifference found = null;
1212:
1213: for (ListIterator it = fDifferences.listIterator(); it
1214: .hasNext();) {
1215: RangeDifference difference = (RangeDifference) it.next();
1216: if (found == null
1217: || difference.kind() == RangeDifference.NOCHANGE
1218: && (difference.leftEnd() < line
1219: && difference.leftLength() >= size || difference
1220: .leftEnd() >= line
1221: && line - difference.leftStart() >= size))
1222: found = difference;
1223:
1224: if (difference.leftEnd() >= line)
1225: break;
1226: }
1227:
1228: return found;
1229: }
1230:
1231: /**
1232: * Finds a consistent range of at least size after <code>line</code> in the left document.
1233: *
1234: * @param line the line after which the range has to occur
1235: * @param size the minimal size of the range
1236: * @return the first range found, or the last range in the differ if none can be found
1237: */
1238: private RangeDifference findConsistentRangeAfterLeft(int line,
1239: int size) {
1240: RangeDifference found = null;
1241:
1242: for (ListIterator it = fDifferences.listIterator(fDifferences
1243: .size()); it.hasPrevious();) {
1244: RangeDifference difference = (RangeDifference) it
1245: .previous();
1246: if (found == null
1247: || difference.kind() == RangeDifference.NOCHANGE
1248: && (difference.leftStart() > line
1249: && difference.leftLength() >= size || difference
1250: .leftStart() <= line
1251: && difference.leftEnd() - line >= size))
1252: found = difference;
1253:
1254: if (difference.leftStart() <= line)
1255: break;
1256:
1257: }
1258:
1259: return found;
1260: }
1261:
1262: /**
1263: * Finds a consistent range of at least size before <code>line</code> in the right document.
1264: *
1265: * @param line the line before which the range has to occur
1266: * @param size the minimal size of the range
1267: * @return the first range found, or the first range in the differ if none can be found
1268: */
1269: private RangeDifference findConsistentRangeBeforeRight(int line,
1270: int size) {
1271: RangeDifference found = null;
1272:
1273: int unchanged = -1; // the number of unchanged lines before line
1274: for (ListIterator it = fDifferences.listIterator(); it
1275: .hasNext();) {
1276: RangeDifference difference = (RangeDifference) it.next();
1277: if (found == null)
1278: found = difference;
1279: else if (difference.kind() == RangeDifference.NOCHANGE) {
1280: unchanged = Math.min(line, difference.rightEnd())
1281: - difference.rightStart();
1282: if (unchanged >= size)
1283: found = difference;
1284: }
1285:
1286: if (difference.rightEnd() >= line)
1287: break;
1288: }
1289:
1290: return found;
1291: }
1292:
1293: /**
1294: * Finds a consistent range of at least size after <code>line</code> in the right document.
1295: *
1296: * @param line the line after which the range has to occur
1297: * @param size the minimal size of the range
1298: * @return the first range found, or the last range in the differ if none can be found
1299: */
1300: private RangeDifference findConsistentRangeAfterRight(int line,
1301: int size) {
1302: RangeDifference found = null;
1303:
1304: int unchanged = -1; // the number of unchanged lines after line
1305: for (ListIterator it = fDifferences.listIterator(fDifferences
1306: .size()); it.hasPrevious();) {
1307: RangeDifference difference = (RangeDifference) it
1308: .previous();
1309: if (found == null)
1310: found = difference;
1311: else if (difference.kind() == RangeDifference.NOCHANGE) {
1312: unchanged = difference.rightEnd()
1313: - Math.max(line + 1, difference.rightStart()); // + 1 to step over the changed line
1314: if (unchanged >= size)
1315: found = difference;
1316: }
1317:
1318: if (difference.rightStart() <= line)
1319: break;
1320: }
1321:
1322: return found;
1323: }
1324:
1325: /**
1326: * Returns the size of a repetition field starting a <code>line</code>.
1327: *
1328: * @param size the maximal length of the repeat window
1329: * @param doc the document to search
1330: * @param line the line to start searching
1331: * @return the size of a found repetition field, or zero
1332: * @throws BadLocationException if <code>doc</code> is modified concurrently
1333: */
1334: private int searchForRepetitionField(int size, IDocument doc,
1335: int line) throws BadLocationException {
1336: /*
1337: Repetition fields: a line wise repetition of maximal size <code>size</code>
1338: can urge a change to come at its end, as diffing greedily takes the longest
1339: unchanged range possible:
1340: <pre>
1341: before
1342: repeat
1343: repeat
1344: repeat
1345: repeat
1346: repeat
1347: repeat
1348: repeat
1349: repeat
1350: after
1351: </pre>
1352:
1353: Inserting another repeat element anywhere in the repetition field will create
1354: an addition at its end.
1355:
1356: Size is one less than our window size (as this is already one more than the actual number
1357: of affected lines.
1358: */
1359:
1360: /*
1361: * Implementation:
1362: * Window of maximum repetition size. Whenever the current matches the first in the window,
1363: * we advance it by one. If there are more free slots in the window, the current line is
1364: * appended.
1365: * We terminate if the current line does not match and there are no more free slots.
1366: *
1367: * Q: what if we have a prefix to a repetition field? Probably does not matter.
1368: */
1369: LinkedList window = new LinkedList();
1370: int nLines = doc.getNumberOfLines();
1371: int repetition = line - 1;
1372: int l = line;
1373:
1374: while (l >= 0 && l < nLines) {
1375: IRegion r = doc.getLineInformation(l);
1376: String current = doc.get(r.getOffset(), r.getLength());
1377:
1378: if (!window.isEmpty() && window.get(0).equals(current)) {
1379: // repetition found, shift
1380: window.removeFirst();
1381: window.addLast(current);
1382: repetition = l;
1383: } else {
1384: // no repetition, add if there is room
1385: // otherwise return
1386: if (window.size() < size)
1387: window.addLast(current);
1388: else
1389: break;
1390: }
1391:
1392: l++;
1393: }
1394:
1395: int fieldLength = repetition - line + 1;
1396: Assert.isTrue(fieldLength >= 0);
1397: return fieldLength;
1398: }
1399:
1400: /**
1401: * Gets the corresponding line on the left side for a line on the right.
1402: *
1403: * @param rightLine the line on the right side
1404: * @return the corresponding left hand line, or <code>-1</code>
1405: */
1406: private int getLeftLine(int rightLine) {
1407: RangeDifference d = getRangeDifferenceForRightLine(rightLine);
1408: if (d == null)
1409: return -1;
1410: return Math.min(d.leftEnd() - 1, d.leftStart() + rightLine
1411: - d.rightStart());
1412: }
1413:
1414: /**
1415: * Gets the corresponding line on the right side for a line on the left.
1416: *
1417: * @param leftLine the line on the left side
1418: * @return the corresponding right hand line, or <code>-1</code>
1419: */
1420: private int getRightLine(int leftLine) {
1421: RangeDifference d = getRangeDifferenceForLeftLine(leftLine);
1422: if (d == null)
1423: return -1;
1424: return Math.min(d.rightEnd() - 1, d.rightStart() + leftLine
1425: - d.leftStart());
1426: }
1427:
1428: /**
1429: * Gets the RangeDifference for a line on the left hand side.
1430: *
1431: * @param leftLine the line on the left side
1432: * @return the corresponding RangeDifference, or <code>null</code>
1433: */
1434: private RangeDifference getRangeDifferenceForLeftLine(int leftLine) {
1435: for (Iterator it = fDifferences.iterator(); it.hasNext();) {
1436: RangeDifference d = (RangeDifference) it.next();
1437: if (leftLine >= d.leftStart() && leftLine < d.leftEnd()) {
1438: return d;
1439: }
1440: }
1441: return null;
1442: }
1443:
1444: /**
1445: * Gets the RangeDifference for a line on the right hand side.
1446: *
1447: * @param rightLine the line on the right side
1448: * @return the corresponding RangeDifference, or <code>null</code>
1449: */
1450: private RangeDifference getRangeDifferenceForRightLine(int rightLine) {
1451: final List differences = fDifferences;
1452: synchronized (differences) {
1453: for (Iterator it = differences.iterator(); it.hasNext();) {
1454: RangeDifference d = (RangeDifference) it.next();
1455: if (rightLine >= d.rightStart()
1456: && rightLine < d.rightEnd()) {
1457: return d;
1458: }
1459: }
1460: }
1461: return null;
1462: }
1463:
1464: /*
1465: * @see org.eclipse.jface.text.source.IAnnotationModel#addAnnotationModelListener(org.eclipse.jface.text.source.IAnnotationModelListener)
1466: */
1467: public void addAnnotationModelListener(
1468: IAnnotationModelListener listener) {
1469: fAnnotationModelListeners.add(listener);
1470: }
1471:
1472: /*
1473: * @see org.eclipse.jface.text.source.IAnnotationModel#removeAnnotationModelListener(org.eclipse.jface.text.source.IAnnotationModelListener)
1474: */
1475: public void removeAnnotationModelListener(
1476: IAnnotationModelListener listener) {
1477: fAnnotationModelListeners.remove(listener);
1478: }
1479:
1480: /*
1481: * @see org.eclipse.jface.text.source.IAnnotationModel#connect(org.eclipse.jface.text.IDocument)
1482: */
1483: public void connect(IDocument document) {
1484: Assert.isTrue(fRightDocument == null
1485: || fRightDocument == document);
1486:
1487: ++fOpenConnections;
1488: if (fOpenConnections == 1) {
1489: fRightDocument = document;
1490: fRightDocument.addDocumentListener(this );
1491: if (document instanceof IDocumentExtension4) {
1492: IDocumentExtension4 ext = (IDocumentExtension4) document;
1493: ext.addDocumentRewriteSessionListener(fSessionListener);
1494: }
1495: initialize();
1496: }
1497: }
1498:
1499: /*
1500: * @see org.eclipse.jface.text.source.IAnnotationModel#disconnect(org.eclipse.jface.text.IDocument)
1501: */
1502: public void disconnect(IDocument document) {
1503: Assert.isTrue(fRightDocument == document);
1504:
1505: --fOpenConnections;
1506:
1507: if (fOpenConnections == 0)
1508: uninstall();
1509: }
1510:
1511: /**
1512: * Uninstalls all components and dereferences any objects.
1513: */
1514: private void uninstall() {
1515: Job job = fInitializationJob;
1516: if (job != null)
1517: job.cancel();
1518:
1519: synchronized (this ) {
1520: fState = SUSPENDED;
1521: fIgnoreDocumentEvents = true;
1522: fInitializationJob = null;
1523:
1524: if (fLeftDocument != null)
1525: fLeftDocument.removeDocumentListener(this );
1526: fLeftDocument = null;
1527: fLeftEquivalent = null;
1528:
1529: if (fRightDocument != null) {
1530: fRightDocument.removeDocumentListener(this );
1531: if (fRightDocument instanceof IDocumentExtension4) {
1532: IDocumentExtension4 ext = (IDocumentExtension4) fRightDocument;
1533: ext
1534: .removeDocumentRewriteSessionListener(fSessionListener);
1535: }
1536: }
1537: fRightDocument = null;
1538: fRightEquivalent = null;
1539:
1540: fDifferences.clear();
1541: }
1542:
1543: if (fReferenceProvider != null) {
1544: fReferenceProvider.dispose();
1545: fReferenceProvider = null;
1546: }
1547: }
1548:
1549: /*
1550: * @see org.eclipse.jface.text.source.IAnnotationModel#addAnnotation(org.eclipse.jface.text.source.Annotation, org.eclipse.jface.text.Position)
1551: */
1552: public void addAnnotation(Annotation annotation, Position position) {
1553: throw new UnsupportedOperationException();
1554: }
1555:
1556: /*
1557: * @see org.eclipse.jface.text.source.IAnnotationModel#removeAnnotation(org.eclipse.jface.text.source.Annotation)
1558: */
1559: public void removeAnnotation(Annotation annotation) {
1560: throw new UnsupportedOperationException();
1561: }
1562:
1563: /*
1564: * @see org.eclipse.jface.text.source.IAnnotationModel#getAnnotationIterator()
1565: */
1566: public Iterator getAnnotationIterator() {
1567: final List copy;
1568: List differences = fDifferences; // atomic
1569: synchronized (differences) {
1570: copy = new ArrayList(differences);
1571: }
1572: final Iterator iter = copy.iterator();
1573: return new Iterator() {
1574:
1575: public void remove() {
1576: throw new UnsupportedOperationException();
1577: }
1578:
1579: public boolean hasNext() {
1580: return iter.hasNext();
1581: }
1582:
1583: public Object next() {
1584: RangeDifference diff = (RangeDifference) iter.next();
1585: return diff.getDiffRegion(copy, fLeftDocument);
1586: }
1587:
1588: };
1589: }
1590:
1591: /*
1592: * @see org.eclipse.jface.text.source.IAnnotationModel#getPosition(org.eclipse.jface.text.source.Annotation)
1593: */
1594: public Position getPosition(Annotation annotation) {
1595: if (fRightDocument != null && annotation instanceof DiffRegion) {
1596: RangeDifference difference = ((DiffRegion) annotation)
1597: .getDifference();
1598: try {
1599: int offset = fRightDocument.getLineOffset(difference
1600: .rightStart());
1601: return new Position(offset, fRightDocument
1602: .getLineOffset(difference.rightEnd() - 1)
1603: + fRightDocument.getLineLength(difference
1604: .rightEnd() - 1) - offset);
1605: } catch (BadLocationException e) {
1606: // ignore and return null;
1607: }
1608: }
1609: return null;
1610: }
1611:
1612: /**
1613: * Informs all annotation model listeners that this model has been changed.
1614: */
1615: protected void fireModelChanged() {
1616: fireModelChanged(new AnnotationModelEvent(this ));
1617: }
1618:
1619: /**
1620: * Informs all annotation model listeners that this model has been changed
1621: * as described in the annotation model event. The event is sent out
1622: * to all listeners implementing <code>IAnnotationModelListenerExtension</code>.
1623: * All other listeners are notified by just calling <code>modelChanged(IAnnotationModel)</code>.
1624: *
1625: * @param event the event to be sent out to the listeners
1626: */
1627: protected void fireModelChanged(AnnotationModelEvent event) {
1628: ArrayList v = new ArrayList(fAnnotationModelListeners);
1629: Iterator e = v.iterator();
1630: while (e.hasNext()) {
1631: IAnnotationModelListener l = (IAnnotationModelListener) e
1632: .next();
1633: if (l instanceof IAnnotationModelListenerExtension)
1634: ((IAnnotationModelListenerExtension) l)
1635: .modelChanged(event);
1636: else
1637: l.modelChanged(this );
1638: }
1639: }
1640:
1641: /*
1642: * @see org.eclipse.ui.internal.texteditor.quickdiff.ILineDifferExtension#suspend()
1643: */
1644: public void suspend() {
1645: Job job = fInitializationJob;
1646: if (job != null)
1647: job.cancel();
1648:
1649: synchronized (this ) {
1650: fInitializationJob = null;
1651: if (fRightDocument != null)
1652: fRightDocument.removeDocumentListener(this );
1653: if (fLeftDocument != null)
1654: fLeftDocument.removeDocumentListener(this );
1655: fLeftDocument = null;
1656: fLeftEquivalent = null;
1657:
1658: fLastDifference = null;
1659: fStoredEvents.clear();
1660: fDifferences.clear();
1661:
1662: fState = SUSPENDED;
1663:
1664: fireModelChanged();
1665: }
1666: }
1667:
1668: /*
1669: * @see org.eclipse.ui.internal.texteditor.quickdiff.ILineDifferExtension#resume()
1670: */
1671: public synchronized void resume() {
1672: if (fRightDocument != null)
1673: fRightDocument.addDocumentListener(this);
1674: initialize();
1675: }
1676: }
|