UI freeze when saving big file after find replace

[trancexpress]

To reproduce:

1. Generate a source file with: GenerateJava.zip
2. Copy it to a new Java project with default settings.
3. Find-replace in the file, replace "= 42" with "= 43" (this takes a while, another bug to report).
4. Save the file, this freezes the UI for about a minute (on a HP Z640 workstation).

[trancexpress]

I found 2 issues here:

1. SemanticHighlightingReconciler has hints about using a binary search in addPosition() and retainPositions() - those 2 methods will make work in a background thread run for a while. But its background work, its long but it doesn't block the UI.
2. SemanticHighlightingPresenterCore.update() is called once for every replacement. Within, it iterates over event.getDocument().getPositions(fCategory), for category SemanticHighlightingPresenterCore. There are many positions in this set (also linear to the amount of inner classes generated for the reproduction snippet). So this results in quadratic complexity, for that particular input snippet.

[trancexpress]

The binary search comments can be realized by something like this:

diff --git a/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java b/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java
index 72880716f8..b37468d960 100644
--- a/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java
+++ b/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java
@@ -15,6 +15,7 @@
 package org.eclipse.jdt.internal.ui.javaeditor;

 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.List;

 import org.eclipse.swt.widgets.Display;
@@ -265,15 +266,37 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
                private void addPosition(int offset, int length, Highlighting highlighting) {
                        boolean isExisting= false;
                        // TODO: use binary search
-                       for (int i= 0, n= fRemovedPositions.size(); i < n; i++) {
-                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
-                               if (position == null)
-                                       continue;
-                               if (position.isEqual(offset, length, highlighting)) {
-                                       isExisting= true;
-                                       fRemovedPositions.set(i, null);
-                                       fNOfRemovedPositions--;
-                                       break;
+                       if (!fOffsetIndices.isEmpty()) {
+                               boolean oob = false;
+                               if (offset < fOffsetIndices.get(0).offset) {
+                                       oob = true;
+                               } else if (offset > fOffsetIndices.get(fOffsetIndices.size() - 1).offset) {
+                                       oob = true;
+                               }
+                               if (!oob) {
+                                       int startIndex = Collections.binarySearch(fOffsetIndices, Integer.valueOf(offset));
+                                       startIndex = Math.max(startIndex, 0);
+                                       startIndex = Math.min(startIndex, fRemovedPositions.size());
+                                       int endIndex = Collections.binarySearch(fOffsetIndices, Integer.valueOf(offset + 1));
+                                       startIndex = Math.max(endIndex, 0);
+                                       startIndex = Math.min(endIndex, fRemovedPositions.size());
+//                                     System.out.println("addPosition() searching in interval: [" + startIndex + ", " + fRemovedPositions.size() + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+//                                     System.out.println("offset=" + offset + ", fOffsetIndices first=" + fOffsetIndices.get(0) + ", fOffsetIndices last=" + fOffsetIndices.get(fOffsetIndices.size() - 1)); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+
+                                       for (int i= startIndex, n= endIndex; i < n; i++) {
+                                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
+                                               if (position == null)
+                                                       continue;
+                                               if (position.offset > offset) {
+                                                       break;
+                                               }
+                                               if (position.isEqual(offset, length, highlighting)) {
+                                                       isExisting= true;
+                                                       fRemovedPositions.set(i, null);
+                                                       fNOfRemovedPositions--;
+                                                       break;
+                                               }
+                                       }
                                }
                        }

@@ -291,11 +314,26 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
                @Override
                protected void retainPositions(int offset, int length) {
                        // TODO: use binary search
-                       for (int i= 0, n= fRemovedPositions.size(); i < n; i++) {
-                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
-                               if (position != null && position.isContained(offset, length)) {
-                                       fRemovedPositions.set(i, null);
-                                       fNOfRemovedPositions--;
+                       if (!fOffsetIndices.isEmpty()) {
+                               boolean oob = false;
+                               if (offset + length < fOffsetIndices.get(0).offset) {
+                                       oob = true;
+                               } else if (offset > fOffsetIndices.get(fOffsetIndices.size() - 1).bound()) {
+                                       oob = true;
+                               }
+                               if (!oob) {
+                                       int endIndex = Collections.binarySearch(fOffsetIndices, Integer.valueOf(offset + length + 1));
+                                       endIndex = Math.max(endIndex, 0);
+                                       endIndex = Math.min(endIndex, fRemovedPositions.size());
+//                                     System.out.println("retainPositions() searching in interval: [" + 0 + ", " + endIndex + "), fRemovedPositions.size()=" + fRemovedPositions.size()); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+//                                     System.out.println("offset=" + offset + ", fOffsetIndices first=" + fOffsetIndices.get(0) + ", fOffsetIndices last=" + fOffsetIndices.get(fOffsetIndices.size() - 1)); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+                                       for (int i= 0, n= endIndex; i < n; i++) {
+                                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
+                                               if (position != null && position.isContained(offset, length)) {
+                                                       fRemovedPositions.set(i, null);
+                                                       fNOfRemovedPositions--;
+                                               }
+                                       }
                                }
                        }
                }
@@ -339,8 +377,16 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,

        /** Background job's added highlighted positions */
        private List<Position> fAddedPositions= new ArrayList<>();
-       /** Background job's removed highlighted positions */
+       /** Background job's removed highlighted positions, sorted by offset */
        private List<Position> fRemovedPositions= new ArrayList<>();
+
+       private record OffsetIndex(int offset, int index, int length) implements Comparable<Integer> {
+               int bound() { return offset + length; }
+               @Override
+               public int compareTo(Integer o) { return Integer.compare(offset, o.intValue()); }
+       }
+       private List<OffsetIndex> fOffsetIndices = new ArrayList<>();
+
        /** Number of removed positions */
        private int fNOfRemovedPositions;

@@ -456,7 +502,17 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
         * Start reconciling positions.
         */
        private void startReconcilingPositions() {
-               fJobPresenter.addAllPositions(fRemovedPositions);
+               fOffsetIndices.clear();
+               List<Position> positions = new ArrayList<>();
+               fJobPresenter.addAllPositions(positions);
+               Collections.sort(positions, (p1, p2) -> Integer.compare(p1.offset, p2.offset));
+               // go backward to overwrite indices for positions with equal offsets
+               for (int i = 0; i < positions.size(); ++i) {
+                       Position position = positions.get(i);
+                       fOffsetIndices.add(new OffsetIndex(Integer.valueOf(position.offset), i, Integer.valueOf(position.length)));
+               }
+               fRemovedPositions = positions;
+
                fNOfRemovedPositions= fRemovedPositions.size();
        }

@@ -523,6 +579,7 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
         */
        private void stopReconcilingPositions() {
                fRemovedPositions.clear();
+               fOffsetIndices.clear();
                fNOfRemovedPositions= 0;
                fAddedPositions.clear();
        }

That doesn't fix the problem though (since its background work).

The retain method will need another array to speed it up, with different contents. Since the background work is fast already with this change, its probably not needed to do more there.