Bug 547064 - [console] Unnecessary linear search in IOConsolePartitionerI20190617-1800

getPartition can use binary search like computePartitioning already
does. Also computePartitioning fails if no partitions available or
requested range is behind known partitions.

Change-Id: I54b120e91a696412bf9466f5a2f10d7bac154b0c
Signed-off-by: Paul Pazderski <paul-eclipse@ppazderski.de>

2 files changed, 103 insertions, 66 deletions

diff --git a/org.eclipse.debug.tests/src/org/eclipse/debug/tests/console/IOConsoleTests.java b/org.eclipse.debug.tests/src/org/eclipse/debug/tests/console/IOConsoleTests.java
index b82bfb3a7..18971d36f 100644
--- a/org.eclipse.debug.tests/src/org/eclipse/debug/tests/console/IOConsoleTests.java
+++ b/org.eclipse.debug.tests/src/org/eclipse/debug/tests/console/IOConsoleTests.java
@@ -216,6 +216,7 @@ public class IOConsoleTests extends AbstractDebugTest {
 		final IOConsoleTestUtil c = getTestUtil("Test input");
 		final List<String> expectedInput = new ArrayList<>();
 
+		c.insertAndVerify("RR").backspace(3).verifyContent("").verifyPartitions();
 		c.insertAndVerify("remove").select(0, c.getContentLength()).verifyPartitions();
 		c.insertTypingAndVerify("abc").insertAndVerify("123").verifyContent("abc123");
 		c.moveCaret(-3).insertAndVerify("foo").insertTypingAndVerify("bar").verifyContentByOffset("123", c.getCaretOffset());
diff --git a/org.eclipse.ui.console/src/org/eclipse/ui/internal/console/IOConsolePartitioner.java b/org.eclipse.ui.console/src/org/eclipse/ui/internal/console/IOConsolePartitioner.java
index cc3f8c54b..f2efa092e 100644
--- a/org.eclipse.ui.console/src/org/eclipse/ui/internal/console/IOConsolePartitioner.java
+++ b/org.eclipse.ui.console/src/org/eclipse/ui/internal/console/IOConsolePartitioner.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2000, 2018 IBM Corporation and others.
+ * Copyright (c) 2000, 2019 IBM Corporation and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -10,11 +10,14 @@
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
+ *     Paul Pazderski - Bug 547064: use binary search for getPartition
  *******************************************************************************/
 package org.eclipse.ui.internal.console;
 
 import java.io.IOException;
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
 
@@ -45,12 +48,22 @@ import org.eclipse.ui.progress.WorkbenchJob;
  *
  */
 public class IOConsolePartitioner implements IConsoleDocumentPartitioner, IDocumentPartitionerExtension {
+
+	/**
+	 * Comparator to sort or search {@link IRegion}s by {@link IRegion#getOffset()}.
+	 */
+	private static final Comparator<IRegion> CMP_REGION_BY_OFFSET = Comparator.comparing(IRegion::getOffset);
+
 	private PendingPartition consoleClosedPartition;
+	/** The connected {@link IDocument} this partitioner manages. */
 	private IDocument document;
-	private ArrayList<IOConsolePartition> partitions;
 	/**
-	 * Blocks of data that have not yet been appended to the document.
+	 * List of all partitions. Must always be sorted ascending by
+	 * {@link IRegion#getOffset()} and not contain <code>null</code> or 0-length
+	 * elements.
 	 */
+	private ArrayList<IOConsolePartition> partitions;
+	/** Blocks of data that have not yet been appended to the document. */
 	private ArrayList<PendingPartition> pendingPartitions;
 	/**
 	 * A list of PendingPartitions to be appended by the updateJob
@@ -73,22 +86,21 @@ public class IOConsolePartitioner implements IConsoleDocumentPartitioner, IDocum
 	 */
 	private boolean updateInProgress;
 	/**
-	 * A list of partitions containing input from the console, that have
-	 * not been appended to the input stream yet.
+	 * A list of partitions containing input from the console, that have not been
+	 * appended to the input stream yet. No guarantees on element order.
 	 */
 	private ArrayList<IOConsolePartition> inputPartitions;
 	/**
 	 * offset used by updateJob
 	 */
 	private int firstOffset;
-	/**
-	 * An array of legal line delimiters
-	 */
+	/** An array of legal line delimiters. */
 	private String[] lld;
 	private int highWaterMark = -1;
 	private int lowWaterMark = -1;
 	private boolean connected = false;
 
+	/** The partitioned {@link IOConsole}. */
 	private IOConsole console;
 
 	private TrimJob trimJob = new TrimJob();
@@ -108,6 +120,11 @@ public class IOConsolePartitioner implements IConsoleDocumentPartitioner, IDocum
 		trimJob.setRule(console.getSchedulingRule());
 	}
 
+	/**
+	 * Get partitioned document or <code>null</code> if none connected.
+	 *
+	 * @return partitioned document
+	 */
 	public IDocument getDocument() {
 		return document;
 	}
@@ -186,75 +203,46 @@ public class IOConsolePartitioner implements IConsoleDocumentPartitioner, IDocum
 
 	@Override
 	public ITypedRegion[] computePartitioning(int offset, int length) {
-		int rangeEnd = offset + length;
-		int left= 0;
-		int right= partitions.size() - 1;
-		int mid= 0;
-		IOConsolePartition position= null;
-
-		if (left == right) {
-			return new IOConsolePartition[]{partitions.get(0)};
-		}
-		while (left < right) {
-
-			mid= (left + right) / 2;
+		return computeIOPartitioning(offset, length);
+	}
 
-			position= partitions.get(mid);
-			if (rangeEnd < position.getOffset()) {
-				if (left == mid) {
-					right= left;
-				} else {
-					right= mid -1;
-				}
-			} else if (offset > (position.getOffset() + position.getLength() - 1)) {
-				if (right == mid) {
-					left= right;
-				} else {
-					left= mid  +1;
-				}
-			} else {
-				left= right= mid;
+	/**
+	 * Same as {@link #computePartitioning(int, int)} but with more specific return
+	 * type.
+	 *
+	 * @param offset the offset of the range of interest
+	 * @param length the length of the range of interest
+	 * @return the partitioning of the requested range (never <code>null</code>)
+	 */
+	private IOConsolePartition[] computeIOPartitioning(int offset, int length) {
+		final List<IOConsolePartition> result = new ArrayList<>();
+		synchronized (partitions) {
+			int index = findPartitionCandidate(offset);
+			if (index < 0) { // requested range starts before any known partition offset
+				index = 0; // so we start collecting at first known partition
 			}
-		}
 
-
-		List<IOConsolePartition> list = new ArrayList<>();
-		int index = left - 1;
-		if (index >= 0) {
-			position= partitions.get(index);
-			while (index >= 0 && (position.getOffset() + position.getLength()) > offset) {
-				index--;
-				if (index >= 0) {
-					position= partitions.get(index);
+			final int end = offset + length;
+			for (; index < partitions.size(); index++) {
+				final IOConsolePartition partition = partitions.get(index);
+				if (partition.getOffset() >= end) {
+					break;
 				}
+				result.add(partition);
 			}
 		}
-		index++;
-		position= partitions.get(index);
-		while (index < partitions.size() && (position.getOffset() < rangeEnd)) {
-			list.add(position);
-			index++;
-			if (index < partitions.size()) {
-				position= partitions.get(index);
-			}
-		}
-
-		return list.toArray(new IOConsolePartition[list.size()]);
+		return result.toArray(new IOConsolePartition[0]);
 	}
 
 	@Override
 	public ITypedRegion getPartition(int offset) {
-		for (int i = 0; i < partitions.size(); i++) {
-			ITypedRegion partition = partitions.get(i);
-			int start = partition.getOffset();
-			int end = start + partition.getLength();
-			if (offset >= start && offset < end) {
-				return partition;
-			}
+		final ITypedRegion partition = getIOPartition(offset);
+		if (partition != null) {
+			return partition;
 		}
 
-		if (lastPartition == null)  {
-			synchronized(partitions) {
+		if (lastPartition == null) {
+			synchronized (partitions) {
 				lastPartition = new IOConsolePartition(inputStream, ""); //$NON-NLS-1$
 				lastPartition.setOffset(offset);
 				partitions.add(lastPartition);
@@ -265,6 +253,54 @@ public class IOConsolePartitioner implements IConsoleDocumentPartitioner, IDocum
 	}
 
 	/**
+	 * Like {@link #getPartition(int)} but returns <code>null</code> for
+	 * unpartitioned or invalid offsets.
+	 *
+	 * @param offset the offset for which to determine the partition
+	 * @return the partition containing this offset or <code>null</code> if offset
+	 *         is not partitioned
+	 */
+	private IOConsolePartition getIOPartition(int offset) {
+		synchronized (partitions) {
+			final int index = findPartitionCandidate(offset);
+			if (index >= 0) {
+				final IOConsolePartition partition = partitions.get(index);
+				if (partition.getOffset() + partition.getLength() > offset) {
+					return partition;
+				}
+			}
+			return null;
+		}
+	}
+
+	/**
+	 * Search {@link #partitions} for the partition which is most likely containing
+	 * the requested offset.
+	 * <p>
+	 * This (index + 1) can be used to insert a new partition with this offset. The
+	 * resulting {@link #partitions} list is guaranteed to still be sorted. (as long
+	 * as you do proper synchronization and consider concurrency problems)
+	 * </p>
+	 *
+	 * @param offset the offset for which to determine the partition candidate
+	 * @return index of partition element with partition offset closest to requested
+	 *         offset or <code>-1</code> if requested offset is lower than offset of
+	 *         any known partition
+	 */
+	private int findPartitionCandidate(int offset) {
+		final Region target = new Region(offset, 0);
+		final int index = Collections.binarySearch(partitions, target, CMP_REGION_BY_OFFSET);
+		if (index >= 0) {
+			// found partition whose offset equals the requested offset
+			return index;
+		}
+		// no exact offset match. Adjust index to point at partition which is closest to
+		// requested offset but whose offset is still lower than requested offset.
+		// Results in -1 if all known offsets are greater.
+		return (-index) - 2;
+	}
+
+	/**
 	 * Enforces the buffer size.
 	 * When the number of lines in the document exceeds the high water mark, the
 	 * beginning of the document is trimmed until the number of lines equals the
@@ -636,7 +672,7 @@ public class IOConsolePartitioner implements IConsoleDocumentPartitioner, IDocum
 		if (!connected) {
 			return new StyleRange[0];
 		}
-		IOConsolePartition[] computedPartitions = (IOConsolePartition[])computePartitioning(offset, length);
+		IOConsolePartition[] computedPartitions = computeIOPartitioning(offset, length);
 		StyleRange[] styles = new StyleRange[computedPartitions.length];
 		for (int i = 0; i < computedPartitions.length; i++) {
 			int rangeStart = Math.max(computedPartitions[i].getOffset(), offset);