Bug 489640 [GTK3] setting a lot of items to combobox is extremely slow

(Bug fix).

Setting wrap causes O(n^2) performance regression because after
every insert the drop-down list size is re-computed.

Solution:
1) Turn off wrap during insert (to fix bulk insert, e.g setItems(...))
2) Delay enabling (so that multiple single-insert calls [e.g add(.)] are
not delayed if called in a loop.

Tests:
- Attached snippets:
  Before fix: Gtk3: 1000ms
  After fix:  Gtk3:   10ms  (event faster than gtk2's 23ms).

- Child eclipse works well.
- All SWT jUnits pass.
- Combo box looks same as before.

Patchset 4:
- Implemented similar logic for removing items to fix performance.

Bug: https://bugs.eclipse.org/bugs/show_bug.cgi?id=4896403
Change-Id: Ibf14b35712277e068bc719d073a482ab5c04fb7f
Signed-off-by: Leo Ufimtsev <lufimtse@redhat.com>

6 files changed, 189 insertions, 51 deletions

diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c
index 674d32688d..cd4875fa87 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c
@@ -5391,6 +5391,18 @@ JNIEXPORT jintLong JNICALL GTK_NATIVE(_1gtk_1combo_1box_1get_1model)
 }
 #endif
 
+#ifndef NO__1gtk_1combo_1box_1get_1wrap_1width
+JNIEXPORT jint JNICALL GTK_NATIVE(_1gtk_1combo_1box_1get_1wrap_1width)
+	(JNIEnv *env, jclass that, jintLong arg0)
+{
+	jint rc = 0;
+	GTK_NATIVE_ENTER(env, that, _1gtk_1combo_1box_1get_1wrap_1width_FUNC);
+	rc = (jint)gtk_combo_box_get_wrap_width((GtkComboBox *)arg0);
+	GTK_NATIVE_EXIT(env, that, _1gtk_1combo_1box_1get_1wrap_1width_FUNC);
+	return rc;
+}
+#endif
+
 #ifndef NO__1gtk_1combo_1box_1popdown
 JNIEXPORT void JNICALL GTK_NATIVE(_1gtk_1combo_1box_1popdown)
 	(JNIEnv *env, jclass that, jintLong arg0)
diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c
index 1bd6a98e1f..c4c943401b 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c
@@ -403,6 +403,7 @@ char * GTK_nativeFunctionNames[] = {
 	"_1gtk_1color_1selection_1set_1has_1palette",
 	"_1gtk_1combo_1box_1get_1active",
 	"_1gtk_1combo_1box_1get_1model",
+	"_1gtk_1combo_1box_1get_1wrap_1width",
 	"_1gtk_1combo_1box_1popdown",
 	"_1gtk_1combo_1box_1popup",
 	"_1gtk_1combo_1box_1set_1active",
diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h
index c999193244..9bd4eb22c9 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h
@@ -401,6 +401,7 @@ typedef enum {
 	_1gtk_1color_1selection_1set_1has_1palette_FUNC,
 	_1gtk_1combo_1box_1get_1active_FUNC,
 	_1gtk_1combo_1box_1get_1model_FUNC,
+	_1gtk_1combo_1box_1get_1wrap_1width_FUNC,
 	_1gtk_1combo_1box_1popdown_FUNC,
 	_1gtk_1combo_1box_1popup_FUNC,
 	_1gtk_1combo_1box_1set_1active_FUNC,
diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java
index ef0023c904..855d78da93 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java
@@ -1540,6 +1540,7 @@ public class GTK extends OS {
 	}
 	/** @method flags=dynamic */
 	public static final native void _gtk_combo_box_text_insert(long /*int*/ combo_box, int position, byte[] id, byte[] text);
+	/** Do not call directly, instead use Combo.gtk_combo_box_insert(..) */
 	public static final void gtk_combo_box_text_insert(long /*int*/ combo_box, int position, byte[] id, byte[] text) {
 		lock.lock();
 		try {
@@ -1574,6 +1575,7 @@ public class GTK extends OS {
 	}
 	/** @method flags=dynamic */
 	public static final native void _gtk_combo_box_text_remove_all(long /*int*/ combo_box);
+	/** Do not call directly. Call Combo.gtk_combo_box_text_remove_all(..) instead). */
 	public static final void gtk_combo_box_text_remove_all(long /*int*/ combo_box) {
 		lock.lock();
 		try {
@@ -1624,6 +1626,9 @@ public class GTK extends OS {
 	 * @param width cast=(gint)
 	 */
 	public static final native void _gtk_combo_box_set_wrap_width(long /*int*/ combo_box, int width);
+	/**
+	 * Do not use directly. Instead use Combo.gtk_combo_box_toggle_wrap(..)
+	 */
 	public static final void gtk_combo_box_set_wrap_width(long /*int*/ combo_box, int width) {
 		lock.lock();
 		try {
@@ -1632,6 +1637,20 @@ public class GTK extends OS {
 			lock.unlock();
 		}
 	}
+
+	/**
+	 * @param combo_box cast=(GtkComboBox *)
+	 * @return cast=(gint)
+	 */
+	public static final native int _gtk_combo_box_get_wrap_width(long /*int*/ combo_box);
+	public static final int gtk_combo_box_get_wrap_width(long /*int*/ combo_box) {
+		lock.lock();
+		try {
+			return _gtk_combo_box_get_wrap_width(combo_box);
+		} finally {
+			lock.unlock();
+		}
+	}
 	/**
 	* @param combo_box cast=(GtkComboBox *)
 	*/
diff --git a/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Combo.java b/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Combo.java
index d9f95a3ad8..4718fa2440 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Combo.java
+++ b/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Combo.java
@@ -81,6 +81,8 @@ public class Combo extends Composite {
 		LIMIT = 0xFFFF;
 	}
 
+	private boolean delayedEnableWrap = false; // Bug 489640. Gtk3.
+
 /**
  * Constructs a new instance of this class given its parent
  * and a style value describing its behavior and appearance.
@@ -176,17 +178,80 @@ public void add (String string, int index) {
 	newItems [index] = string;
 	System.arraycopy (items, index, newItems, index + 1, items.length - index);
 	items = newItems;
-	byte [] buffer = Converter.wcsToMbcs (string, true);
-	if (GTK.GTK3) {
-		if (handle != 0) GTK.gtk_combo_box_text_insert (handle, index, null, buffer);
-	} else {
-		if (handle != 0) GTK.gtk_combo_box_text_insert_text (handle, index, buffer);
-	}
+	gtk_combo_box_insert(string, index);
 	if ((style & SWT.RIGHT_TO_LEFT) != 0 && popupHandle != 0) {
 		GTK.gtk_container_forall (popupHandle, display.setDirectionProc, GTK.GTK_TEXT_DIR_RTL);
 	}
 }
 
+private void gtk_combo_box_insert(String string, int index) {
+	byte [] buffer = Converter.wcsToMbcs (string, true);
+	if (handle != 0) {
+		if (GTK.GTK3) {
+			gtk_combo_box_toggle_wrap(false);
+			GTK.gtk_combo_box_text_insert (handle, index, null, buffer);
+			gtk_combo_box_toggle_wrap(true);
+		} else {
+			GTK.gtk_combo_box_text_insert_text (handle, index, buffer);
+		}
+	}
+}
+
+/**
+ * <p>Bug 489640, 438992. Drop-down appearance.</p>
+ *
+ * <p>In Gtk3, there is a lot of white space at the top of the combo drop-down.
+ *   It's meant to put the first item near the cursor (See screen shots in bug 438992), but makes eclipse look buggy.</p>
+ *
+ * <p>Solution (438992): gtk_combo_box_get_wrap_width(1) fixes this problem, but introduces a performance regression.
+ *    When multiple items are added in a loop, then if 'wrap' is enabled then after every insertion, gtk
+ *    traverses the entire list and greedily re-computes the drop-down list size.
+ *    This causes O(n^2) performance regression in that the longer the list, the longer the size computation takes.
+ *    E.g Adding 1000 items takes almost 30 seconds.</p>
+ *
+ * <p>Solution ^2 (489640): We enabled wrap in a delayed/lazy way, only when display event loop is ran.
+ *   This way the insertions occur at O(n) speed and we get the benefit of a neat drop-down list when the user launches the application.
+ *   Run-time insertions and combo.add(..) are also covered by this logic.</p>
+ *
+ * <p>Gtk4 port note:
+ *  - Note, Combo was re-written in Gtk3 and it will be re-written again in Gtk4. See:
+ *  https://mail.gnome.org/archives/gtk-list/2016-December/msg00036.html
+ *  https://raw.githubusercontent.com/gnome-design-team/gnome-mockups/master/theming/widgets/combobox-replacements.png     // mockup screen shot.
+ *  - So probably this workaround should be removed in Gtk4 port. Feel free to validate via Bug489640_SlowCombo and Bug489640_SlowComboSingleItem test snippets.</p>
+ *
+ * <p>CSS note: Do not use the CSS 'appears-as-list' style as done in:
+ *   https://git.eclipse.org/r/#/c/117681/6/bundles/org.eclipse.swt/Eclipse+SWT/gtk/org/eclipse/swt/widgets/Combo.java
+ *   It's a poorly working hack. If list has more than +-1000 entries, then we get visual cheese and jvm crashes. </p>
+ */
+private void gtk_combo_box_toggle_wrap (boolean wrap) {
+	if (handle == 0) return;
+	if (GTK.GTK3) {
+		if (!wrap) {
+			if (GTK.gtk_combo_box_get_wrap_width(handle) == 1) {
+				GTK.gtk_combo_box_set_wrap_width(handle, 0);
+			}
+		} else  {
+			if (delayedEnableWrap) {
+				return;
+			} else {
+				delayedEnableWrap = true;
+				display.asyncExec(() -> {
+					if (!isDisposed() && handle != 0) {
+						GTK.gtk_combo_box_set_wrap_width(handle, 1);
+						delayedEnableWrap = false;
+					}
+				});
+			}
+		}
+	} else { // GTK2
+		if (wrap) {
+			GTK.gtk_combo_box_set_wrap_width(handle, 1);
+		} else {
+			GTK.gtk_combo_box_set_wrap_width(handle, 0);
+		}
+	}
+}
+
 /**
  * Adds the listener to the collection of listeners who will
  * be notified when the receiver's text is modified, by sending
@@ -458,8 +523,7 @@ void createHandle (int index) {
 		if (handle == 0) error (SWT.ERROR_NO_HANDLES);
 		cellHandle = GTK.gtk_bin_get_child (handle);
 		if (cellHandle == 0) error (SWT.ERROR_NO_HANDLES);
-		// Setting wrap width has the side effect of removing the whitespace on top in popup bug#438992
-		GTK.gtk_combo_box_set_wrap_width(handle, 1);
+		gtk_combo_box_toggle_wrap(true);
 	} else {
 		handle = GTK.gtk_combo_box_text_new_with_entry();
 		if (handle == 0) error (SWT.ERROR_NO_HANDLES);
@@ -1766,9 +1830,12 @@ public void remove (int start, int end) {
 	items = newItems;
 	int index = GTK.gtk_combo_box_get_active (handle);
 	if (start <= index && index <= end) clearText();
+
+	if (GTK.GTK3) gtk_combo_box_toggle_wrap(false);
 	for (int i = end; i >= start; i--) {
 		if (handle != 0) GTK.gtk_combo_box_text_remove(handle, i);
 	}
+	if (GTK.GTK3) gtk_combo_box_toggle_wrap(true);
 }
 
 /**
@@ -1810,7 +1877,7 @@ public void removeAll () {
 	items = new String[0];
 	clearText ();
 	if (GTK.GTK3) {
-		if (handle != 0) GTK.gtk_combo_box_text_remove_all(handle);
+		gtk_combo_box_text_remove_all();
 	} else {
 		for (int i = count - 1; i >= 0; i--) {
 			if (handle != 0) GTK.gtk_combo_box_text_remove (handle, i);
@@ -2105,14 +2172,11 @@ public void setItem (int index, String string) {
 		error (SWT.ERROR_INVALID_ARGUMENT);
 	}
 	items [index] = string;
-	byte [] buffer = Converter.wcsToMbcs (string, true);
-	if (GTK.GTK3) {
-		if (handle != 0) GTK.gtk_combo_box_text_remove (handle, index);
-		if (handle != 0) GTK.gtk_combo_box_text_insert (handle, index, null, buffer);
-	} else {
-		if (handle != 0) GTK.gtk_combo_box_text_remove (handle, index);
-		if (handle != 0) GTK.gtk_combo_box_text_insert_text (handle, index, buffer);
+	if (handle != 0) {
+		GTK.gtk_combo_box_text_remove (handle, index);
 	}
+	gtk_combo_box_insert(string, index);
+
 	if ((style & SWT.RIGHT_TO_LEFT) != 0 && popupHandle != 0) {
 		GTK.gtk_container_forall (popupHandle, display.setDirectionProc, GTK.GTK_TEXT_DIR_RTL);
 	}
@@ -2143,7 +2207,7 @@ public void setItems (String... items) {
 	System.arraycopy (items, 0, this.items, 0, items.length);
 	clearText ();
 	if (GTK.GTK3) {
-		if (handle != 0) GTK.gtk_combo_box_text_remove_all(handle);
+		gtk_combo_box_text_remove_all();
 	} else {
 		for (int i = count - 1; i >= 0; i--) {
 			if (handle != 0) GTK.gtk_combo_box_text_remove (handle, i);
@@ -2151,18 +2215,19 @@ public void setItems (String... items) {
 	}
 	for (int i = 0; i < items.length; i++) {
 		String string = items [i];
-		byte [] buffer = Converter.wcsToMbcs (string, true);
-		if (GTK.GTK3) {
-			if (handle != 0) GTK.gtk_combo_box_text_insert (handle, i, null, buffer);
-		} else {
-			if (handle != 0) GTK.gtk_combo_box_text_insert_text (handle, i, buffer);
-		}
+		gtk_combo_box_insert(string, i);
 		if ((style & SWT.RIGHT_TO_LEFT) != 0 && popupHandle != 0) {
 			GTK.gtk_container_forall (popupHandle, display.setDirectionProc, GTK.GTK_TEXT_DIR_RTL);
 		}
 	}
 }
 
+private void gtk_combo_box_text_remove_all() {
+	gtk_combo_box_toggle_wrap(false);
+	if (handle != 0) GTK.gtk_combo_box_text_remove_all(handle);
+	gtk_combo_box_toggle_wrap(true);
+}
+
 /**
  * Marks the receiver's list as visible if the argument is <code>true</code>,
  * and marks it invisible otherwise.
diff --git a/tests/org.eclipse.swt.tests.gtk/ManualTests/org/eclipse/swt/tests/gtk/snippets/Bug489640_ComboPerformanceTest.java b/tests/org.eclipse.swt.tests.gtk/ManualTests/org/eclipse/swt/tests/gtk/snippets/Bug489640_ComboPerformanceTest.java
index 4d5b3a6d76..6d09b91656 100644
--- a/tests/org.eclipse.swt.tests.gtk/ManualTests/org/eclipse/swt/tests/gtk/snippets/Bug489640_ComboPerformanceTest.java
+++ b/tests/org.eclipse.swt.tests.gtk/ManualTests/org/eclipse/swt/tests/gtk/snippets/Bug489640_ComboPerformanceTest.java
@@ -11,44 +11,39 @@
 package org.eclipse.swt.tests.gtk.snippets;
 
 
-import java.nio.charset.*;
-import java.util.*;
+import java.nio.charset.Charset;
+import java.util.ArrayList;
+import java.util.Collections;
 import java.util.List;
+import java.util.Map;
 
-import org.eclipse.swt.*;
-import org.eclipse.swt.layout.*;
-import org.eclipse.swt.widgets.*;
+import org.eclipse.swt.SWT;
+import org.eclipse.swt.layout.GridData;
+import org.eclipse.swt.layout.GridLayout;
+import org.eclipse.swt.widgets.Button;
+import org.eclipse.swt.widgets.Combo;
+import org.eclipse.swt.widgets.Display;
+import org.eclipse.swt.widgets.Shell;
 
+/*
+ * Title: Adding items in combo box grows at O(n^2).
+ * how to run: Run on Gtk2/3 with/without fix to observe different run times.
+ * Gtk2,  +-20 ms
+ * Gtk3,  +- 1000ms
+ * Gtk3 with fix: += 10ms.
+ *
+ * Once snippet launched, try 'refill' button, which tests time it takes to remove entries.
+ *
+ */
 public class Bug489640_ComboPerformanceTest {
 
 	public static void main(String[] args) {
-		final Map<String, Charset> charSets = Charset.availableCharsets();
-		final List<String> encodings = new ArrayList<>(charSets.keySet());
-		Collections.sort(encodings);
-
 		final Display display = new Display();
-
 		final Shell shell = new Shell(display);
 		shell.setLayout(new GridLayout());
 
-		final Combo combo = new Combo(shell, SWT.BORDER | SWT.READ_ONLY);
-		combo.setLayoutData(new GridData(SWT.FILL, SWT.TOP, true, false));
-
-		final Button button = new Button(shell, SWT.PUSH);
-		button.setLayoutData(new GridData(SWT.RIGHT, SWT.TOP, false, false));
-		button.setText("Fill Combo");
-		button.addListener(SWT.Selection, new Listener() {
-			@Override
-			public void handleEvent(Event event) {
-				final String[] items = encodings.toArray(new String[encodings.size()]);
-				System.out.println("Setting widget.combo with " + items.length + " items");
-				final long start = System.currentTimeMillis();
-				combo.setItems(items);
-				final long end = System.currentTimeMillis();
-				System.out.println("took " + (end - start) + " ms.");
-				combo.select(0);
-			}
-		});
+		test_setItems(shell);
+		test_addItems(shell);
 
 		shell.setSize(400, 200);
 		shell.open();
@@ -61,4 +56,49 @@ public class Bug489640_ComboPerformanceTest {
 
 		display.dispose();
 	}
+
+	private static void test_addItems(final Shell shell) {
+		final Combo combo = new Combo(shell, SWT.BORDER | SWT.READ_ONLY);
+		combo.setLayoutData(new GridData(SWT.FILL, SWT.TOP, true, false));
+
+		final long start = System.currentTimeMillis();
+		int count = 200;
+		final String[] items = new String[count];
+		for (int i = 0; i < count; i++) {
+			combo.add("item " + i);     // <<< via add.
+		}
+		System.out.println("Combo.add(..)     took " + (System.currentTimeMillis() - start) + " ms.   (1000ms = bad.  20ms = good.)");
+		combo.select(0);
+	}
+
+	private static void test_setItems(final Shell shell) {
+		final Combo combo = new Combo(shell, SWT.BORDER | SWT.READ_ONLY);
+		combo.setLayoutData(new GridData(SWT.FILL, SWT.TOP, true, false));
+
+		int count = 200;
+		final String[] items = new String[count];
+		for (int i = 0; i < count; i++) {
+			items[i] = new String("item " + i);
+		}
+		final long start = System.currentTimeMillis();
+		combo.setItems(items);
+		System.out.println("Combo.setItems(.) took " + (System.currentTimeMillis() - start) + " ms.   (1000ms = bad.  20ms = good.)");
+		combo.select(0);
+
+		final Button button = new Button(shell, SWT.PUSH);
+		button.setLayoutData(new GridData(SWT.RIGHT, SWT.TOP, false, false));
+		button.setText("Refill Combo at runtime");
+		button.addListener(SWT.Selection, event -> {
+			final Map<String, Charset> charSets = Charset.availableCharsets();
+			final List<String> encodings = new ArrayList<>(charSets.keySet());
+			Collections.sort(encodings);
+			final String[] items1 = encodings.toArray(new String[encodings.size()]);
+			System.out.println("Setting widget.combo with " + items1.length + " items");
+			final long start1 = System.currentTimeMillis();
+			combo.setItems(items1);
+			final long end = System.currentTimeMillis();
+			System.out.println("took " + (end - start1) + " ms.");
+			combo.select(0);
+		});
+	}
 }