| /******************************************************************************* |
| * Copyright (c) 2000, 2003 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Common Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/cpl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| package org.eclipse.ui.internal.texteditor.quickdiff; |
| |
| import java.util.ArrayList; |
| import java.util.Iterator; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.ListIterator; |
| |
| import org.eclipse.core.runtime.CoreException; |
| import org.eclipse.core.runtime.IProgressMonitor; |
| import org.eclipse.core.runtime.IStatus; |
| import org.eclipse.core.runtime.OperationCanceledException; |
| import org.eclipse.core.runtime.Status; |
| import org.eclipse.core.runtime.jobs.Job; |
| |
| import org.eclipse.jface.util.Assert; |
| |
| import org.eclipse.jface.text.BadLocationException; |
| import org.eclipse.jface.text.Document; |
| import org.eclipse.jface.text.DocumentEvent; |
| import org.eclipse.jface.text.IDocument; |
| import org.eclipse.jface.text.IDocumentListener; |
| import org.eclipse.jface.text.IRegion; |
| import org.eclipse.jface.text.Position; |
| import org.eclipse.jface.text.Region; |
| import org.eclipse.jface.text.source.Annotation; |
| import org.eclipse.jface.text.source.AnnotationModelEvent; |
| import org.eclipse.jface.text.source.IAnnotationModel; |
| import org.eclipse.jface.text.source.IAnnotationModelListener; |
| import org.eclipse.jface.text.source.IAnnotationModelListenerExtension; |
| import org.eclipse.jface.text.source.ILineDiffInfo; |
| import org.eclipse.jface.text.source.ILineDiffer; |
| |
| import org.eclipse.ui.texteditor.quickdiff.IQuickDiffReferenceProvider; |
| |
| import org.eclipse.ui.internal.texteditor.TextEditorPlugin; |
| import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.DocLineComparator; |
| import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.RangeDifference; |
| import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.RangeDifferencer; |
| |
| /** |
| * Standard implementation of <code>ILineDiffer</code> as an incremental diff engine. A |
| * <code>DocumentLineDiffer</code> can be initialized to some start state. Once connected to a |
| * <code>IDocument</code> and a reference document has been set, changes reported via the |
| * <code>IDocumentListener</code> interface will be tracked and the incremental diff updated. |
| * |
| * <p>The diff state can be queried using the <code>ILineDiffer</code> interface.</p> |
| * |
| * <p>Since diff information is model information attached to a document, this class implements |
| * <code>IAnnotationModel</code> and can be attached to <code>IAnnotationModelExtension</code>s.</p> |
| * |
| * <p>This class is not supposed to be subclassed.</p> |
| * |
| * @since 3.0 |
| */ |
| public class DocumentLineDiffer implements ILineDiffer, IDocumentListener, IAnnotationModel { |
| |
| /** The provider for the reference document. */ |
| IQuickDiffReferenceProvider fReferenceProvider; |
| /** Whether this differ is in sync with the model. */ |
| private boolean fIsSynchronized; |
| /** The number of clients connected to this model. */ |
| private int fOpenConnections; |
| /** The current document being tracked. */ |
| private IDocument fLeftDocument; |
| /** The reference document. */ |
| private IDocument fRightDocument; |
| /** |
| * Flag to indicate whether a change has been made to the line table and any clients should |
| * update their presentation. |
| */ |
| private boolean fUpdateNeeded; |
| /** The listeners on this annotation model. */ |
| private List fAnnotationModelListeners= new ArrayList(); |
| /** The job currently initializing the differ, or <code>null</code> if there is none. */ |
| private Job fInitializationJob; |
| /** Stores <code>DocumentEvents</code> while an initialization is going on. */ |
| private List fStoredEvents= new ArrayList(); |
| /** |
| * The differences between <code>fLeftDocument</code> and <code>fRightDocument</code>. |
| * This is the model we work on. |
| */ |
| private List fDifferences= new ArrayList(); |
| /** |
| * The differences removed in one iteration. Stored to be able to send out differentiated |
| * annotation events. |
| */ |
| private List fRemoved= new ArrayList(); |
| /** |
| * The differences added in one iteration. Stored to be able to send out differentiated |
| * annotation events. |
| */ |
| private List fAdded= new ArrayList(); |
| /** |
| * The differences changed in one iteration. Stored to be able to send out differentiated |
| * annotation events. |
| */ |
| private List fChanged= new ArrayList(); |
| /** The first line affected by a document event. */ |
| private int fFirstLine; |
| /** The number of lines affected by a document event. */ |
| private int fNLines; |
| /** The most recent range difference returned in a getLineInfo call, so it can be recyled. */ |
| private RangeDifference fLastDifference; |
| |
| /** |
| * Creates a new differ. |
| */ |
| public DocumentLineDiffer() { |
| } |
| |
| /* ILineDiffer implementation */ |
| |
| /* |
| * @see org.eclipse.jface.text.source.ILineDiffer#getLineInfo(int) |
| */ |
| public ILineDiffInfo getLineInfo(int line) { |
| |
| // try cache first / speeds up linear search |
| RangeDifference last= fLastDifference; |
| if (last != null && last.rightStart() <= line && last.rightEnd() > line) |
| return new DiffRegion(last, line - last.rightStart(), fDifferences, fLeftDocument); |
| |
| fLastDifference= getRangeDifferenceForRightLine(line); |
| last= fLastDifference; |
| if (last != null) |
| return new DiffRegion(last, line - last.rightStart(), fDifferences, fLeftDocument); |
| else |
| return null; |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.ILineDiffer#revertLine(int) |
| */ |
| public synchronized void revertLine(int line) throws BadLocationException { |
| if (!isInitialized()) |
| throw new BadLocationException(QuickDiffMessages.getString("quickdiff.nonsynchronized")); //$NON-NLS-1$ |
| |
| DiffRegion region= (DiffRegion) getLineInfo(line); |
| if (region == null || fRightDocument == null || fLeftDocument == null) |
| return; |
| |
| RangeDifference diff= region.getDifference(); |
| int rOffset= fRightDocument.getLineOffset(line); |
| int rLength= fRightDocument.getLineLength(line); |
| int leftLine= diff.leftStart() + region.getOffset(); |
| String replacement; |
| if (leftLine >= diff.leftEnd()) // restoring a deleted line? |
| replacement= new String(); |
| else { |
| int lOffset= fLeftDocument.getLineOffset(leftLine); |
| int lLength= fLeftDocument.getLineLength(leftLine); |
| replacement= fLeftDocument.get(lOffset, lLength); |
| } |
| fRightDocument.replace(rOffset, rLength, replacement); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.ILineDiffer#revertBlock(int) |
| */ |
| public synchronized void revertBlock(int line) throws BadLocationException { |
| if (!isInitialized()) |
| throw new BadLocationException(QuickDiffMessages.getString("quickdiff.nonsynchronized")); //$NON-NLS-1$ |
| |
| DiffRegion region= (DiffRegion) getLineInfo(line); |
| if (region == null || fRightDocument == null || fLeftDocument == null) |
| return; |
| |
| RangeDifference diff= region.getDifference(); |
| int rOffset= fRightDocument.getLineOffset(diff.rightStart()); |
| int rLength= fRightDocument.getLineOffset(diff.rightEnd() - 1) + fRightDocument.getLineLength(diff.rightEnd() - 1) - rOffset; |
| int lOffset= fLeftDocument.getLineOffset(diff.leftStart()); |
| int lLength= fLeftDocument.getLineOffset(diff.leftEnd() - 1) + fLeftDocument.getLineLength(diff.leftEnd() - 1) - lOffset; |
| fRightDocument.replace(rOffset, rLength, fLeftDocument.get(lOffset, lLength)); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.ILineDiffer#revertSelection(int, int) |
| */ |
| public synchronized void revertSelection(int line, int nLines) throws BadLocationException { |
| if (!isInitialized()) |
| throw new BadLocationException(QuickDiffMessages.getString("quickdiff.nonsynchronized")); //$NON-NLS-1$ |
| |
| int rOffset= -1, rLength= -1, lOffset= -1, lLength= -1; |
| RangeDifference diff= null; |
| Iterator it= fDifferences.iterator(); |
| |
| // get start |
| while (it.hasNext()) { |
| diff= (RangeDifference) it.next(); |
| if (line < diff.rightEnd()) { |
| rOffset= fRightDocument.getLineOffset(line); |
| int leftLine= Math.min(diff.leftStart() + line - diff.rightStart(), diff.leftEnd() - 1); |
| lOffset= fLeftDocument.getLineOffset(leftLine); |
| break; |
| } |
| } |
| |
| if (rOffset == -1 || lOffset == -1) |
| return; |
| |
| // get end / length |
| int to= line + nLines - 1; |
| while (it.hasNext()) { |
| diff= (RangeDifference) it.next(); |
| if (to < diff.rightEnd()) { |
| int rEndOffset= fRightDocument.getLineOffset(to) + fRightDocument.getLineLength(to); |
| rLength= rEndOffset - rOffset; |
| int leftLine= Math.min(diff.leftStart() + to - diff.rightStart(), diff.leftEnd() - 1); |
| int lEndOffset= fLeftDocument.getLineOffset(leftLine) + fLeftDocument.getLineLength(leftLine); |
| lLength= lEndOffset - lOffset; |
| break; |
| } |
| } |
| |
| if (rLength == -1 || lLength == -1) |
| return; |
| |
| fRightDocument.replace(rOffset, rLength, fLeftDocument.get(lOffset, lLength)); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.ILineDiffer#restoreAfterLine(int) |
| */ |
| public synchronized int restoreAfterLine(int line) throws BadLocationException { |
| if (!isInitialized()) |
| throw new BadLocationException(QuickDiffMessages.getString("quickdiff.nonsynchronized")); //$NON-NLS-1$ |
| |
| DiffRegion region= (DiffRegion) getLineInfo(line); |
| if (region == null || fRightDocument == null || fLeftDocument == null) |
| return 0; |
| |
| if (region.getRemovedLinesBelow() < 1) |
| return 0; |
| |
| RangeDifference diff= null; |
| for (Iterator it= fDifferences.iterator(); it.hasNext();) { |
| diff= (RangeDifference) it.next(); |
| if (line >= diff.rightStart() && line < diff.rightEnd()) { |
| if (diff.kind() == RangeDifference.NOCHANGE && it.hasNext()) |
| diff= (RangeDifference) it.next(); |
| break; |
| } |
| } |
| |
| if (diff == null) |
| return 0; |
| |
| int rOffset= fRightDocument.getLineOffset(diff.rightEnd()); |
| int rLength= 0; |
| int leftLine= diff.leftStart() + diff.rightLength(); |
| int lOffset= fLeftDocument.getLineOffset(leftLine); |
| int lLength= fLeftDocument.getLineOffset(diff.leftEnd() - 1) + fLeftDocument.getLineLength(diff.leftEnd() - 1) - lOffset; |
| fRightDocument.replace(rOffset, rLength, fLeftDocument.get(lOffset, lLength)); |
| |
| return diff.leftLength() - diff.rightLength(); |
| } |
| |
| /** |
| * Returns the receivers initialization state. |
| * |
| * @return <code>true</code> if we are initialized and in sync with the document. |
| */ |
| private boolean isInitialized() { |
| return fIsSynchronized; |
| } |
| |
| /** |
| * Returns the receivers synchronization state. |
| * |
| * @return <code>true</code> if we are initialized and in sync with the document. |
| */ |
| public synchronized boolean isSynchronized() { |
| return fIsSynchronized; |
| } |
| |
| /** |
| * Sets the reference provider for this instance. If one has been installed before, it is |
| * disposed. |
| * |
| * @param provider the new provider |
| */ |
| public void setReferenceProvider(IQuickDiffReferenceProvider provider) { |
| Assert.isNotNull(provider); |
| if (provider != fReferenceProvider) { |
| if (fReferenceProvider != null) |
| fReferenceProvider.dispose(); |
| fReferenceProvider= provider; |
| initialize(); |
| } |
| } |
| |
| /** |
| * Returns the reference provider currently installed, or <code>null</code> if none is installed. |
| * |
| * @return the current reference provider. |
| */ |
| public IQuickDiffReferenceProvider getReferenceProvider() { |
| return fReferenceProvider; |
| } |
| |
| /** |
| * (Re-)initializes the differ using the current reference and <code>DiffInitializer</code> |
| */ |
| synchronized void initialize() { |
| // make new incoming changes go into the queue of stored events, plus signal we can't restore. |
| fIsSynchronized= false; |
| |
| if (fRightDocument == null) |
| return; |
| |
| // there is no point in receiving updates before the job we get a new copy of the document for diffing |
| fRightDocument.removeDocumentListener(this); |
| |
| if (fLeftDocument != null) { |
| fLeftDocument.removeDocumentListener(this); |
| fLeftDocument= null; |
| } |
| |
| // if there already is a job: |
| // return if it has not started yet, cancel it if already running |
| final Job oldJob= fInitializationJob; |
| if (oldJob != null) { |
| // don't chain up jobs if there is one waiting already. |
| if (oldJob.getState() == Job.WAITING) |
| return; |
| else |
| oldJob.cancel(); |
| } |
| |
| fInitializationJob= new Job(QuickDiffMessages.getString("quickdiff.initialize")) { //$NON-NLS-1$ |
| |
| /* |
| * This is run in a different thread. As the documents might be synchronized, never ever |
| * access the documents in a synchronized section or expect deadlocks. See |
| * https://bugs.eclipse.org/bugs/show_bug.cgi?id=44692 |
| */ |
| public IStatus run(IProgressMonitor monitor) { |
| |
| // 1: wait for any previous job that was canceled to avoid job flooding |
| // It will return relatively quickly as RangeDifferencer supports canceling |
| if (oldJob != null) |
| try { |
| oldJob.join(); |
| } catch (InterruptedException e) { |
| // will not happen as noone interrupst our thread |
| Assert.isTrue(false); |
| } |
| |
| |
| // 2: get the reference document |
| IQuickDiffReferenceProvider provider= fReferenceProvider; |
| final IDocument left; |
| try { |
| left= provider == null ? null : provider.getReference(monitor); |
| } catch (CoreException e) { |
| synchronized (DocumentLineDiffer.this) { |
| if (isCanceled(monitor)) |
| return Status.CANCEL_STATUS; |
| else { |
| clearModel(); |
| fireModelChanged(); |
| DocumentLineDiffer.this.notifyAll(); |
| return e.getStatus(); |
| } |
| } |
| } catch (OperationCanceledException e) { |
| return Status.CANCEL_STATUS; |
| } |
| |
| // Getting our own copies of the documents for offline diffing. |
| // |
| // We need to make sure that we do get all document modifications after |
| // copying the documents as we want to reinject them later on to become consistent. |
| // |
| // Now this is fun. The reference documents may be PartiallySynchronizedDocuments |
| // which will result in a deadlock if they get changed externally before we get |
| // our exclusive copies. |
| // Here's what we do: we try over and over (without synchronization) to get copies |
| // without interleaving modification. If there is a document change, we just repeat. |
| |
| IDocument right= fRightDocument; // fRightDocument, but not subject to change |
| IDocument actual= null; // the copy of the actual (right) document |
| IDocument reference= null; // the copy of the reference (left) document |
| |
| synchronized (DocumentLineDiffer.this) { |
| // 4: take an early exit if the documents are not valid |
| if (left == null || right == null) { |
| if (isCanceled(monitor)) |
| return Status.CANCEL_STATUS; |
| else { |
| clearModel(); |
| fireModelChanged(); |
| DocumentLineDiffer.this.notifyAll(); |
| return Status.OK_STATUS; |
| } |
| } |
| |
| // set the reference document |
| fLeftDocument= left; |
| } |
| |
| right.addDocumentListener(DocumentLineDiffer.this); |
| left.addDocumentListener(DocumentLineDiffer.this); |
| |
| do { |
| // clear events |
| synchronized (DocumentLineDiffer.this) { |
| if (isCanceled(monitor)) |
| return Status.CANCEL_STATUS; |
| |
| fStoredEvents.clear(); |
| } |
| |
| // access documents unsynched: |
| // get an exclusive copy of the actual document |
| reference= createCopy(left); |
| actual= createCopy(right); |
| |
| synchronized (DocumentLineDiffer.this) { |
| if (fStoredEvents.size() == 0) |
| break; |
| } |
| |
| |
| } while (true); |
| |
| // 6: Do Da Diffing |
| DocLineComparator ref= new DocLineComparator(reference, null, false); |
| DocLineComparator act= new DocLineComparator(actual, null, false); |
| List diffs= RangeDifferencer.findRanges(monitor, ref, act); |
| |
| // 7: Reset the model to the just gotten differences |
| // re-inject stored events to get up to date. |
| List storedEvents; |
| synchronized (DocumentLineDiffer.this) { |
| if (isCanceled(monitor)) |
| return Status.CANCEL_STATUS; |
| |
| // set the new differences so we can operate on them |
| fDifferences= diffs; |
| storedEvents= new ArrayList(fStoredEvents); |
| fStoredEvents.clear(); |
| } |
| |
| // reinject events accumulated in the meantime. |
| try { |
| for (ListIterator iter= storedEvents.listIterator(); iter.hasNext();) { |
| DocumentEvent event= (DocumentEvent) iter.next(); |
| // access documents unsynched: |
| handleAboutToBeChanged(event); |
| handleChanged(event); |
| |
| synchronized (DocumentLineDiffer.this) { |
| if (isCanceled(monitor)) |
| return Status.CANCEL_STATUS; |
| |
| if (fStoredEvents.size() > 0) { |
| // early leave on interfering change |
| left.removeDocumentListener(DocumentLineDiffer.this); |
| right.removeDocumentListener(DocumentLineDiffer.this); |
| clearModel(); |
| initialize(); |
| return Status.CANCEL_STATUS; |
| } |
| } |
| |
| } |
| } catch (BadLocationException e) { |
| left.removeDocumentListener(DocumentLineDiffer.this); |
| right.removeDocumentListener(DocumentLineDiffer.this); |
| clearModel(); |
| initialize(); |
| return Status.CANCEL_STATUS; |
| } |
| |
| synchronized (DocumentLineDiffer.this) { |
| // signal done |
| fInitializationJob= null; |
| fIsSynchronized= true; |
| fLastDifference= null; |
| |
| // inform blocking calls. |
| DocumentLineDiffer.this.notifyAll(); |
| } |
| |
| fireModelChanged(); |
| return Status.OK_STATUS; |
| } |
| |
| private boolean isCanceled(IProgressMonitor monitor) { |
| return fInitializationJob != this || monitor != null && monitor.isCanceled(); |
| } |
| |
| private void clearModel() { |
| fLeftDocument= null; |
| fInitializationJob= null; |
| fStoredEvents.clear(); |
| fLastDifference= null; |
| fDifferences.clear(); |
| } |
| |
| private IDocument createCopy(IDocument document) { |
| Assert.isNotNull(document); |
| // TODO needs for sure a safer synchronization method |
| // this is a temporary workaround for https://bugs.eclipse.org/bugs/show_bug.cgi?id=56091 |
| int count= 0; |
| while (count < 100) { |
| try { |
| return new Document(document.get()); |
| } catch (NullPointerException x) { |
| } catch (ArrayStoreException x) { |
| } catch (IndexOutOfBoundsException x) { |
| } |
| ++ count; |
| } |
| return new Document(); |
| } |
| }; |
| |
| fInitializationJob.setSystem(true); |
| fInitializationJob.setPriority(Job.DECORATE); |
| fInitializationJob.schedule(); |
| } |
| |
| /* IDocumentListener implementation */ |
| |
| /* |
| * @see org.eclipse.jface.text.IDocumentListener#documentAboutToBeChanged(org.eclipse.jface.text.DocumentEvent) |
| */ |
| public synchronized void documentAboutToBeChanged(DocumentEvent event) { |
| // if a initialization is going on, we just store the events in the meantime |
| if (!isInitialized() && fInitializationJob != null) { |
| fStoredEvents.add(event); |
| return; |
| } |
| |
| try { |
| handleAboutToBeChanged(event); |
| } catch (BadLocationException e) { |
| TextEditorPlugin.getDefault().getLog().log(new Status(IStatus.WARNING, TextEditorPlugin.PLUGIN_ID, IStatus.OK, "reinitializing quickdiff", e)); //$NON-NLS-1$ |
| initialize(); |
| } |
| } |
| |
| |
| /** |
| * Unsynchronized version of <code>documentAboutToBeChanged</code>, called by <code>documentAboutToBeChanged</code> |
| * and {@link #initialize(SortedMap, int)}. |
| * |
| * @param event the document event to be handled |
| */ |
| void handleAboutToBeChanged(DocumentEvent event) throws BadLocationException { |
| IDocument doc= event.getDocument(); |
| if (doc == null) |
| return; |
| |
| // store size of replaced region (never synchronized -> not a problem) |
| fFirstLine= doc.getLineOfOffset(event.getOffset()); // store change bounding lines |
| fNLines= doc.getLineOfOffset(event.getOffset() + event.getLength()) - fFirstLine + 1; |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.IDocumentListener#documentChanged(org.eclipse.jface.text.DocumentEvent) |
| */ |
| public synchronized void documentChanged(DocumentEvent event) { |
| if (!isInitialized()) |
| return; |
| |
| // https://bugs.eclipse.org/bugs/show_bug.cgi?id=44692 |
| // don't allow incremental update for changes from the reference document |
| // as this could deadlock |
| if (event.getDocument() == fLeftDocument) { |
| initialize(); |
| return; |
| } |
| |
| try { |
| handleChanged(event); |
| } catch (BadLocationException e) { |
| TextEditorPlugin.getDefault().getLog().log(new Status(IStatus.WARNING, TextEditorPlugin.PLUGIN_ID, IStatus.OK, "reinitializing quickdiff", e)); //$NON-NLS-1$ |
| initialize(); |
| return; |
| } |
| |
| // inform listeners about change |
| if (fUpdateNeeded) { |
| AnnotationModelEvent ame= new AnnotationModelEvent(this, false); |
| for (Iterator it= fAdded.iterator(); it.hasNext(); ) { |
| RangeDifference rd= (RangeDifference) it.next(); |
| ame.annotationAdded(rd.getDiffRegion(fDifferences, fLeftDocument)); |
| } |
| for (Iterator it= fRemoved.iterator(); it.hasNext(); ) { |
| RangeDifference rd= (RangeDifference) it.next(); |
| ame.annotationRemoved(rd.getDiffRegion(fDifferences, fLeftDocument)); |
| } |
| for (Iterator it= fChanged.iterator(); it.hasNext(); ) { |
| RangeDifference rd= (RangeDifference) it.next(); |
| ame.annotationChanged(rd.getDiffRegion(fDifferences, fLeftDocument)); |
| } |
| fireModelChanged(ame); |
| fUpdateNeeded= false; |
| } |
| } |
| |
| /** |
| * Implementation of documentChanged, non synchronized. |
| * |
| * @param event the document event |
| */ |
| void handleChanged(DocumentEvent event) throws BadLocationException { |
| /* |
| * Now, here we have a great example of object oriented programming. |
| */ |
| |
| // documents: left, right; modified and unchanged are either of both |
| IDocument left= fLeftDocument; |
| IDocument right= fRightDocument; |
| IDocument modified= event.getDocument(); |
| if (modified != left && modified != right) |
| Assert.isTrue(false); |
| |
| String insertion= event.getText(); |
| int added= insertion == null ? 1 : modified.computeNumberOfLines(insertion) + 1; |
| // size: the size of the document change in lines |
| |
| // put an upper bound to the delay we can afford |
| if (added > 50 || fNLines > 50) { |
| initialize(); |
| return; |
| } |
| |
| int size= Math.max(fNLines, added) + 1; |
| int lineDelta= added - fNLines; |
| int lastLine= fFirstLine + fNLines - 1; |
| |
| int repetitionField; |
| if (modified == left) { |
| int originalLine= getRightLine(lastLine + 1); |
| repetitionField= searchForRepetitionField(size - 1, right, originalLine); |
| } else { |
| int originalLine= getLeftLine(lastLine + 1); |
| repetitionField= searchForRepetitionField(size - 1, left, originalLine); |
| } |
| lastLine += repetitionField; |
| |
| |
| // get enclosing range: search for a consistent block of at least the size of our |
| // change before and after the change. |
| RangeDifference consistentBefore, consistentAfter; |
| if (modified == left) { |
| consistentBefore= findConsistentRangeBeforeLeft(fFirstLine, size); |
| consistentAfter= findConsistentRangeAfterLeft(lastLine, size); |
| } else { |
| consistentBefore= findConsistentRangeBeforeRight(fFirstLine, size); |
| consistentAfter= findConsistentRangeAfterRight(lastLine, size); |
| } |
| |
| // optimize unchanged blocks: if the consistent blocks around the change are larger than |
| // size, we redimension them (especially important when there are only very little changes. |
| int shiftBefore= 0; |
| if (consistentBefore.kind() == RangeDifference.NOCHANGE) { |
| int unchanged; |
| if (modified == left) |
| unchanged= Math.min(fFirstLine, consistentBefore.leftEnd()) - consistentBefore.leftStart(); |
| else |
| unchanged= Math.min(fFirstLine, consistentBefore.rightEnd()) - consistentBefore.rightStart(); |
| |
| shiftBefore= Math.max(0, unchanged - size); |
| } |
| |
| int shiftAfter= 0; |
| if (consistentAfter.kind() == RangeDifference.NOCHANGE) { |
| int unchanged; |
| if (modified == left) |
| unchanged= consistentAfter.leftEnd() - Math.max(lastLine + 1, consistentAfter.leftStart()); |
| else |
| unchanged= consistentAfter.rightEnd() - Math.max(lastLine + 1, consistentAfter.rightStart()); |
| |
| shiftAfter= Math.max(0, unchanged - size); |
| } |
| |
| // get the document regions that will be rediffed, take into account that on the |
| // document, the change has already happened. |
| // left (reference) document |
| int leftOffset= left.getLineOffset(consistentBefore.leftStart() + shiftBefore); |
| int leftLine= Math.max(consistentAfter.leftEnd() - 1, 0); |
| if (modified == left) |
| leftLine += lineDelta; |
| IRegion leftLastLine= left.getLineInformation(leftLine - shiftAfter); |
| int leftEndOffset= leftLastLine.getOffset() + leftLastLine.getLength(); |
| IRegion leftRegion= new Region(leftOffset, leftEndOffset - leftOffset); |
| DocLineComparator reference= new DocLineComparator(left, leftRegion, false); |
| |
| // right (actual) document |
| int rightOffset= right.getLineOffset(consistentBefore.rightStart() + shiftBefore); |
| int rightLine= Math.max(consistentAfter.rightEnd() - 1, 0); |
| if (modified == right) |
| rightLine += lineDelta; |
| IRegion rightLastLine= right.getLineInformation(rightLine - shiftAfter); |
| int rightEndOffset= rightLastLine.getOffset() + rightLastLine.getLength(); |
| IRegion rightRegion= new Region(rightOffset, rightEndOffset - rightOffset); |
| DocLineComparator change= new DocLineComparator(right, rightRegion, false); |
| |
| // put an upper bound to the delay we can afford |
| if (leftLine - shiftAfter - (consistentBefore.leftStart() + shiftBefore) > 50 || rightLine - shiftAfter - (consistentBefore.rightStart() + shiftBefore) > 50) { |
| initialize(); |
| return; |
| } |
| |
| // debug |
| // System.out.println("compare window: "+size+"\n\n<" + left.get(leftRegion.getOffset(), leftRegion.getLength()) + //$NON-NLS-1$//$NON-NLS-2$ |
| // ">\n\n<" + right.get(rightRegion.getOffset(), rightRegion.getLength()) + ">\n"); //$NON-NLS-1$ //$NON-NLS-2$ |
| |
| // compare |
| List diffs= RangeDifferencer.findRanges(reference, change); |
| if (diffs.size() == 0) { |
| diffs.add(new RangeDifference(RangeDifference.CHANGE, 0, 0, 0, 0)); |
| } |
| |
| |
| // shift the partial diffs to the absolute document positions |
| int leftShift= consistentBefore.leftStart() + shiftBefore; |
| int rightShift= consistentBefore.rightStart() + shiftBefore; |
| for (Iterator it= diffs.iterator(); it.hasNext();) { |
| RangeDifference d= (RangeDifference) it.next(); |
| d.shiftLeft(leftShift); |
| d.shiftRight(rightShift); |
| } |
| |
| // undo optimization shifting |
| if (shiftBefore > 0) { |
| RangeDifference first= (RangeDifference) diffs.get(0); |
| if (first.kind() == RangeDifference.NOCHANGE) |
| first.extendStart(-shiftBefore); |
| else |
| diffs.add(0, new RangeDifference(RangeDifference.NOCHANGE, first.rightStart() - shiftBefore, shiftBefore, first.leftStart() - shiftBefore, shiftBefore)); |
| } |
| |
| RangeDifference last= (RangeDifference) diffs.get(diffs.size() - 1); |
| if (shiftAfter > 0) { |
| if (last.kind() == RangeDifference.NOCHANGE) |
| last.extendEnd(shiftAfter); |
| else |
| diffs.add(new RangeDifference(RangeDifference.NOCHANGE, last.rightEnd(), shiftAfter , last.leftEnd(), shiftAfter)); |
| } |
| |
| // replace changed diff range |
| ListIterator it= fDifferences.listIterator(); |
| Iterator newIt= diffs.iterator(); |
| RangeDifference current; |
| boolean changed= false; |
| |
| // replace regions from consistentBefore to consistentAfter with new diffs |
| |
| // search for consistentBefore |
| do { |
| Assert.isTrue(it.hasNext()); |
| current= (RangeDifference) it.next(); |
| } while (current != consistentBefore); |
| Assert.isTrue(current == consistentBefore); |
| |
| fChanged.clear(); |
| fRemoved.clear(); |
| fAdded.clear(); |
| |
| // replace until consistentAfter |
| while (current != consistentAfter) { |
| if (newIt.hasNext()) { |
| Object o= newIt.next(); |
| if (!current.equals(o)) { |
| fRemoved.add(current); |
| fAdded.add(o); |
| changed= true; |
| it.set(o); |
| } |
| } else { |
| fRemoved.add(current); |
| it.remove(); |
| fUpdateNeeded= true; |
| } |
| Assert.isTrue(it.hasNext()); |
| current= (RangeDifference) it.next(); |
| } |
| |
| // replace consistentAfter |
| Assert.isTrue(current == consistentAfter); |
| if (newIt.hasNext()) { |
| Object o= newIt.next(); |
| if (!current.equals(o)) { |
| fRemoved.add(current); |
| fAdded.add(o); |
| changed= true; |
| it.set(o); |
| } |
| } else { |
| fRemoved.add(current); |
| it.remove(); |
| fUpdateNeeded= true; |
| } |
| |
| // add remaining new diffs |
| while (newIt.hasNext()) { |
| Object next= newIt.next(); |
| fAdded.add(next); |
| it.add(next); |
| changed= true; |
| } |
| |
| // shift the old remaining diffs |
| boolean init= true; |
| while (it.hasNext()) { |
| current= (RangeDifference) it.next(); |
| if (init) { |
| init= false; |
| leftShift= last.leftEnd() - current.leftStart(); |
| rightShift= last.rightEnd() - current.rightStart(); |
| if (leftShift != 0 || rightShift != 0) |
| changed= true; |
| else |
| break; |
| } |
| // fChanged.add(current); // not needed since positional shifting is not handled by an annotation model |
| current.shiftLeft(leftShift); |
| current.shiftRight(rightShift); |
| } |
| |
| fUpdateNeeded= changed; |
| fLastDifference= null; |
| |
| } |
| |
| /** |
| * Finds a consistent range of at least size before <code>line</code> in the left document. |
| * |
| * @param line the line before which the range has to occur |
| * @param size the minimal size of the range |
| * @return the first range found, or the first range in the differ if none can be found |
| */ |
| private RangeDifference findConsistentRangeBeforeLeft(int line, int size) { |
| RangeDifference found= null; |
| |
| for (ListIterator it= fDifferences.listIterator(); it.hasNext();) { |
| RangeDifference difference= (RangeDifference) it.next(); |
| if (found == null || difference.kind() == RangeDifference.NOCHANGE |
| && (difference.leftEnd() < line && difference.leftLength() >= size |
| || difference.leftEnd() >= line && line - difference.leftStart() >= size)) |
| found= difference; |
| |
| if (difference.leftEnd() >= line) |
| break; |
| } |
| |
| return found; |
| } |
| |
| /** |
| * Finds a consistent range of at least size after <code>line</code> in the left document. |
| * |
| * @param line the line after which the range has to occur |
| * @param size the minimal size of the range |
| * @return the first range found, or the last range in the differ if none can be found |
| */ |
| private RangeDifference findConsistentRangeAfterLeft(int line, int size) { |
| RangeDifference found= null; |
| |
| for (ListIterator it= fDifferences.listIterator(fDifferences.size()); it.hasPrevious();) { |
| RangeDifference difference= (RangeDifference) it.previous(); |
| if (found == null || difference.kind() == RangeDifference.NOCHANGE |
| && (difference.leftStart() > line && difference.leftLength() >= size |
| || difference.leftStart() <= line && difference.leftEnd() - line >= size)) |
| found= difference; |
| |
| if (difference.leftStart() <= line) |
| break; |
| |
| } |
| |
| return found; |
| } |
| |
| /** |
| * Finds a consistent range of at least size before <code>line</code> in the right document. |
| * |
| * @param line the line before which the range has to occur |
| * @param size the minimal size of the range |
| * @return the first range found, or the first range in the differ if none can be found |
| */ |
| private RangeDifference findConsistentRangeBeforeRight(int line, int size) { |
| RangeDifference found= null; |
| |
| int unchanged= -1; // the number of unchanged lines before line |
| for (ListIterator it= fDifferences.listIterator(); it.hasNext();) { |
| RangeDifference difference= (RangeDifference) it.next(); |
| if (found == null) |
| found= difference; |
| else if (difference.kind() == RangeDifference.NOCHANGE) { |
| unchanged= Math.min(line, difference.rightEnd()) - difference.rightStart(); |
| if (unchanged >= size) |
| found= difference; |
| } |
| |
| if (difference.rightEnd() >= line) |
| break; |
| } |
| |
| return found; |
| } |
| |
| /** |
| * Finds a consistent range of at least size after <code>line</code> in the right document. |
| * |
| * @param line the line after which the range has to occur |
| * @param size the minimal size of the range |
| * @return the first range found, or the last range in the differ if none can be found |
| */ |
| private RangeDifference findConsistentRangeAfterRight(int line, int size) { |
| RangeDifference found= null; |
| |
| int unchanged= -1; // the number of unchanged lines after line |
| for (ListIterator it= fDifferences.listIterator(fDifferences.size()); it.hasPrevious();) { |
| RangeDifference difference= (RangeDifference) it.previous(); |
| if (found == null) |
| found= difference; |
| else if (difference.kind() == RangeDifference.NOCHANGE) { |
| unchanged= difference.rightEnd() - Math.max(line + 1, difference.rightStart()); // + 1 to step over the changed line |
| if (unchanged >= size) |
| found= difference; |
| } |
| |
| if (difference.rightStart() <= line) |
| break; |
| } |
| |
| return found; |
| } |
| |
| /** |
| * Returns the size of a repetition field starting a <code>line</code>. |
| * |
| * @param size the maximal length of the repeat window |
| * @param doc the document to search |
| * @param line the line to start searching |
| * @return the size of a found repetition field, or zero |
| * @throws BadLocationException if <code>doc</code> is modified concurrently |
| */ |
| private int searchForRepetitionField(int size, IDocument doc, int line) throws BadLocationException { |
| /* |
| Repetition fields: a line wise repetition of maximal size <code>size</code> |
| can urge a change to come at its end, as diffing greedily takes the longest |
| unchanged range possible: |
| <pre> |
| before |
| repeat |
| repeat |
| repeat |
| repeat |
| repeat |
| repeat |
| repeat |
| repeat |
| after |
| </pre> |
| |
| Inserting another repeat element anywhere in the repetition field will create |
| an addition at its end. |
| |
| Size is one less than our window size (as this is already one more than the actual number |
| of affected lines. |
| */ |
| |
| /* |
| * Implementation: |
| * Window of maximum repetition size. Whenever the current matches the first in the window, |
| * we advance it by one. If there are more free slots in the window, the current line is |
| * appended. |
| * We terminate if the current line does not match and there are no more free slots. |
| * |
| * TODO what if we have a prefix to a repetition field? Probably does not matter. |
| */ |
| LinkedList window= new LinkedList(); |
| int nLines= doc.getNumberOfLines(); |
| int repetition= line - 1; |
| int l= line; |
| |
| while (l >= 0 && l < nLines) { |
| IRegion r= doc.getLineInformation(l); |
| String current= doc.get(r.getOffset(), r.getLength()); |
| |
| if (!window.isEmpty() && window.get(0).equals(current)) { |
| // repetition found, shift |
| window.removeFirst(); |
| window.addLast(current); |
| repetition= l; |
| } else { |
| // no repetition, add if there is room |
| // otherwise return |
| if (window.size() < size) |
| window.addLast(current); |
| else |
| break; |
| } |
| |
| l++; |
| } |
| |
| int fieldLength= repetition - line + 1; |
| Assert.isTrue(fieldLength >= 0); |
| return fieldLength; |
| } |
| |
| /** |
| * Gets the corresponding line on the left side for a line on the right. |
| * |
| * @param rightLine the line on the right side |
| * @return the corresponding left hand line, or <code>-1</code> |
| */ |
| private int getLeftLine(int rightLine) { |
| RangeDifference d= getRangeDifferenceForRightLine(rightLine); |
| if (d == null) |
| return -1; |
| return Math.min(d.leftEnd() - 1, d.leftStart() + rightLine - d.rightStart()); |
| } |
| |
| /** |
| * Gets the corresponding line on the right side for a line on the left. |
| * |
| * @param leftLine the line on the left side |
| * @return the corresponding right hand line, or <code>-1</code> |
| */ |
| private int getRightLine(int leftLine) { |
| RangeDifference d= getRangeDifferenceForLeftLine(leftLine); |
| if (d == null) |
| return -1; |
| return Math.min(d.rightEnd() - 1, d.rightStart() + leftLine - d.leftStart()); |
| } |
| |
| /** |
| * Gets the RangeDifference for a line on the left hand side. |
| * |
| * @param leftLine the line on the left side |
| * @return the corresponding RangeDifference, or <code>null</code> |
| */ |
| private RangeDifference getRangeDifferenceForLeftLine(int leftLine) { |
| for (Iterator it= fDifferences.iterator(); it.hasNext();) { |
| RangeDifference d= (RangeDifference) it.next(); |
| if (leftLine >= d.leftStart() && leftLine < d.leftEnd()) { |
| return d; |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Gets the RangeDifference for a line on the right hand side. |
| * |
| * @param rightLine the line on the right side |
| * @return the corresponding RangeDifference, or <code>null</code> |
| */ |
| private RangeDifference getRangeDifferenceForRightLine(int rightLine) { |
| for (Iterator it= fDifferences.iterator(); it.hasNext();) { |
| RangeDifference d= (RangeDifference) it.next(); |
| if (rightLine >= d.rightStart() && rightLine < d.rightEnd()) { |
| return d; |
| } |
| } |
| return null; |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#addAnnotationModelListener(org.eclipse.jface.text.source.IAnnotationModelListener) |
| */ |
| public void addAnnotationModelListener(IAnnotationModelListener listener) { |
| fAnnotationModelListeners.add(listener); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#removeAnnotationModelListener(org.eclipse.jface.text.source.IAnnotationModelListener) |
| */ |
| public void removeAnnotationModelListener(IAnnotationModelListener listener) { |
| fAnnotationModelListeners.remove(listener); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#connect(org.eclipse.jface.text.IDocument) |
| */ |
| public void connect(IDocument document) { |
| Assert.isTrue(fRightDocument == null || fRightDocument == document); |
| |
| ++fOpenConnections; |
| if (fOpenConnections == 1) { |
| fRightDocument= document; |
| initialize(); |
| } |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#disconnect(org.eclipse.jface.text.IDocument) |
| */ |
| public void disconnect(IDocument document) { |
| Assert.isTrue(fRightDocument == document); |
| |
| --fOpenConnections; |
| |
| if (fOpenConnections == 0) |
| uninstall(); |
| } |
| |
| /** |
| * Uninstalls all components and dereferences any objects. |
| */ |
| private void uninstall() { |
| synchronized (this) { |
| fIsSynchronized= false; |
| if (fInitializationJob != null) |
| fInitializationJob.cancel(); |
| fInitializationJob= null; |
| |
| if (fLeftDocument != null) |
| fLeftDocument.removeDocumentListener(this); |
| fLeftDocument= null; |
| |
| if (fRightDocument != null) |
| fRightDocument.removeDocumentListener(this); |
| fRightDocument= null; |
| } |
| |
| if (fReferenceProvider != null) { |
| fReferenceProvider.dispose(); |
| fReferenceProvider= null; |
| } |
| |
| fDifferences.clear(); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#addAnnotation(org.eclipse.jface.text.source.Annotation, org.eclipse.jface.text.Position) |
| */ |
| public void addAnnotation(Annotation annotation, Position position) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#removeAnnotation(org.eclipse.jface.text.source.Annotation) |
| */ |
| public void removeAnnotation(Annotation annotation) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#getAnnotationIterator() |
| */ |
| public Iterator getAnnotationIterator() { |
| final List copy= new ArrayList(fDifferences); |
| final Iterator iter= copy.iterator(); |
| return new Iterator() { |
| |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public boolean hasNext() { |
| return iter.hasNext(); |
| } |
| |
| public Object next() { |
| RangeDifference diff= (RangeDifference) iter.next(); |
| return diff.getDiffRegion(copy, fLeftDocument); |
| } |
| |
| }; |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.source.IAnnotationModel#getPosition(org.eclipse.jface.text.source.Annotation) |
| */ |
| public Position getPosition(Annotation annotation) { |
| if (fRightDocument != null && annotation instanceof DiffRegion) { |
| RangeDifference difference= ((DiffRegion)annotation).getDifference(); |
| try { |
| int offset= fRightDocument.getLineOffset(difference.rightStart()); |
| return new Position(offset, fRightDocument.getLineOffset(difference.rightEnd() - 1) + fRightDocument.getLineLength(difference.rightEnd() - 1) - offset); |
| } catch (BadLocationException e) { |
| // ignore and return null; |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Informs all annotation model listeners that this model has been changed. |
| */ |
| protected void fireModelChanged() { |
| fireModelChanged(new AnnotationModelEvent(this)); |
| } |
| |
| /** |
| * Informs all annotation model listeners that this model has been changed |
| * as described in the annotation model event. The event is sent out |
| * to all listeners implementing <code>IAnnotationModelListenerExtension</code>. |
| * All other listeners are notified by just calling <code>modelChanged(IAnnotationModel)</code>. |
| * |
| * @param event the event to be sent out to the listeners |
| */ |
| protected void fireModelChanged(AnnotationModelEvent event) { |
| ArrayList v= new ArrayList(fAnnotationModelListeners); |
| Iterator e= v.iterator(); |
| while (e.hasNext()) { |
| IAnnotationModelListener l= (IAnnotationModelListener)e.next(); |
| if (l instanceof IAnnotationModelListenerExtension) |
| ((IAnnotationModelListenerExtension)l).modelChanged(event); |
| else |
| l.modelChanged(this); |
| } |
| } |
| |
| /** |
| * Stops diffing of this differ. All differences are cleared. |
| */ |
| public synchronized void suspend() { |
| if (fInitializationJob != null) { |
| fInitializationJob.cancel(); |
| fInitializationJob= null; |
| } |
| if (fRightDocument != null) |
| fRightDocument.removeDocumentListener(this); |
| if (fLeftDocument != null) |
| fLeftDocument.removeDocumentListener(this); |
| |
| fDifferences.clear(); |
| |
| fIsSynchronized= false; |
| |
| fireModelChanged(); |
| } |
| |
| /** |
| * Resumes diffing of this differ. Must only be called after suspend. |
| */ |
| public synchronized void resume() { |
| if (fRightDocument != null) |
| fRightDocument.addDocumentListener(this); |
| initialize(); |
| } |
| } |