Bug 571844 - made AbstractTreeViewer::add deterministic
To prevent duplicate TreeItems, search not only forward but
also backward while trying to find an equal element as the initial
indexInItems will point to the middle element of three equal (equal by
the comparator) elements after binary search.
Change-Id: I656c9190dc1d33b409b6b2b8b4ff85c9842f98e8
Signed-off-by: Julian Jung <julian.jung@vector.com>
Reviewed-on: https://git.eclipse.org/r/c/platform/eclipse.platform.ui/+/188836
Tested-by: Platform Bot <platform-bot@eclipse.org>
Reviewed-by: Karsten Thoms <karsten.thoms@karakun.com>
diff --git a/bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/AbstractTreeViewer.java b/bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/AbstractTreeViewer.java
index ff26220..416ea87 100644
--- a/bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/AbstractTreeViewer.java
+++ b/bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/AbstractTreeViewer.java
@@ -138,20 +138,19 @@
}
/**
- * Adds the given child elements to this viewer as children of the given
- * parent element. If this viewer does not have a sorter, the elements are
- * added at the end of the parent's list of children in the order given;
- * otherwise, the elements are inserted at the appropriate positions.
+ * Adds the given child elements to this viewer as children of the given parent
+ * element. If this viewer does not have a sorter, the elements are added at the
+ * end of the parent's list of children in the order given; otherwise, the
+ * elements are inserted at the appropriate positions. If a child already exists
+ * under the given parent, the child gets refreshed and not added twice.
* <p>
* This method should be called (by the content provider) when elements have
- * been added to the model, in order to cause the viewer to accurately
- * reflect the model. This method only affects the viewer, not the model.
+ * been added to the model, in order to cause the viewer to accurately reflect
+ * the model. This method only affects the viewer, not the model.
* </p>
*
- * @param parentElementOrTreePath
- * the parent element
- * @param childElements
- * the child elements to add
+ * @param parentElementOrTreePath the parent element
+ * @param childElements the child elements to add
*/
public void add(Object parentElementOrTreePath, Object... childElements) {
Assert.isNotNull(parentElementOrTreePath);
@@ -331,12 +330,11 @@
}
/**
- * Create the new elements in the parent widget. If the child already exists
- * do nothing.
+ * Create the new elements in the parent widget. If the child already exists it
+ * will be refreshed to handle potential changes within its children.
*
* @param widget
- * @param elements
- * Sorted list of elements to add.
+ * @param elements Sorted list of elements to add.
*/
private void createAddedElements(Widget widget, Object[] elements) {
@@ -391,22 +389,38 @@
// Use a separate index variable to search within the existing
// elements that compare equally, see
// TreeViewerTestBug205700.testAddEquallySortedElements.
- int insertionIndexInItems = indexInItems;
- while( insertionIndexInItems < items.length
- && internalCompare(comparator, parentPath, element,
- items[insertionIndexInItems].getData()) == 0) {
- // As we cannot assume the sorter is consistent with
- // equals() - therefore we can
- // just check against the item prior to this index (if
- // any)
- if (items[insertionIndexInItems].getData().equals(element)) {
- // Found the item for the element.
- // Refresh the element in case it has new children.
- internalRefresh(element);
- // Do not create a new item - continue with the next element.
- continue elementloop;
+ int insertionIndexInItems = indexInItems - 1;
+ // Searching not only forward but also backward while trying to find an equal
+ // element.
+ // See https://bugs.eclipse.org/bugs/show_bug.cgi?id=571844.
+ int directionStep = -1;
+ while (insertionIndexInItems < items.length) {
+ if (insertionIndexInItems >= 0 && internalCompare(comparator, parentPath, element,
+ items[insertionIndexInItems].getData()) == 0) {
+ // As we cannot assume the sorter is consistent with
+ // equals() - therefore we can
+ // just check against the item prior to this index (if
+ // any)
+ if (items[insertionIndexInItems].getData().equals(element)) {
+ // Found the item for the element.
+ // Refresh the element in case it has new children.
+ internalRefresh(element);
+ // Do not create a new item - continue with the next element.
+ continue elementloop;
+ }
+ insertionIndexInItems += directionStep;
+ } else {
+ if (directionStep < 0) {
+ // Reached an non equal item or the first item in forwardDirection
+ // change search direction
+ directionStep = 1;
+ insertionIndexInItems = indexInItems;
+ } else {
+ // Reached an non equal item in forwardDirection, break the while loop
+ // The last item is detected by the while loop itself.
+ break;
+ }
}
- insertionIndexInItems++;
}
// Did we get to the end?
if (insertionIndexInItems == items.length) {
@@ -650,22 +664,21 @@
}
/**
- * Adds the given child element to this viewer as a child of the given
- * parent element. If this viewer does not have a sorter, the element is
- * added at the end of the parent's list of children; otherwise, the element
- * is inserted at the appropriate position.
+ * Adds the given child element to this viewer as a child of the given parent
+ * element. If this viewer does not have a sorter, the element is added at the
+ * end of the parent's list of children; otherwise, the element is inserted at
+ * the appropriate position. If the child already exists under the given parent,
+ * the child gets refreshed and not added twice.
* <p>
- * This method should be called (by the content provider) when a single
- * element has been added to the model, in order to cause the viewer to
- * accurately reflect the model. This method only affects the viewer, not
- * the model. Note that there is another method for efficiently processing
- * the simultaneous addition of multiple elements.
+ * This method should be called (by the content provider) when a single element
+ * has been added to the model, in order to cause the viewer to accurately
+ * reflect the model. This method only affects the viewer, not the model. Note
+ * that there is another method for efficiently processing the simultaneous
+ * addition of multiple elements.
* </p>
*
- * @param parentElementOrTreePath
- * the parent element or path
- * @param childElement
- * the child element
+ * @param parentElementOrTreePath the parent element or path
+ * @param childElement the child element
*/
public void add(Object parentElementOrTreePath, Object childElement) {
add(parentElementOrTreePath, new Object[] { childElement });
diff --git a/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/AbstractTreeViewerTest.java b/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/AbstractTreeViewerTest.java
index ed6348d..1c0711e 100644
--- a/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/AbstractTreeViewerTest.java
+++ b/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/AbstractTreeViewerTest.java
@@ -19,6 +19,7 @@
import org.eclipse.jface.viewers.AbstractTreeViewer;
import org.eclipse.jface.viewers.IStructuredSelection;
import org.eclipse.swt.widgets.Item;
+import org.eclipse.swt.widgets.Tree;
import org.eclipse.swt.widgets.Widget;
import org.eclipse.ui.tests.harness.util.DisplayHelper;
@@ -282,6 +283,33 @@
assertEquals("Same element added to a parent twice.", initialCount, postCount);
}
+ /**
+ * Test for Bug 571844 - assert that an item is not added twice if the
+ * comparator returns 0 = equal for more than one tree item. Problem was that
+ * the method AbstractTreeViewer#createAddedElements only searched forward but
+ * not backwards for an equal element, if the comparator returned 0. The example
+ * below is a case where the previous implementation would fail.
+ */
+ public void testChildIsNotDuplicatedWhenCompareEquals() {
+ fTreeViewer.setComparator(new TestLabelComparator());
+ fRootElement.deleteChildren();
+
+ TestElement child1 = fRootElement.addChild(TestModelChange.INSERT);
+ child1.setLabel("1");
+ TestElement child2 = fRootElement.addChild(TestModelChange.INSERT);
+ child2.setLabel("1");
+ TestElement child3 = fRootElement.addChild(TestModelChange.INSERT);
+ child3.setLabel("0");
+
+ // Every duplicated element must not be added as TreeItem.
+ fRootElement.addChild(child1, new TestModelChange(TestModelChange.INSERT, fRootElement, child1));
+ fRootElement.addChild(child2, new TestModelChange(TestModelChange.INSERT, fRootElement, child2));
+ fRootElement.addChild(child3, new TestModelChange(TestModelChange.INSERT, fRootElement, child3));
+
+ Tree tree = (Tree) fTreeViewer.getControl();
+ assertEquals("Same element added to parent twice.", 3, tree.getItems().length);
+ }
+
@Override
public void tearDown() {
super.tearDown();
diff --git a/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/VirtualLazyTreeViewerTest.java b/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/VirtualLazyTreeViewerTest.java
index e89a505..6bd1fc7 100644
--- a/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/VirtualLazyTreeViewerTest.java
+++ b/tests/org.eclipse.jface.tests/src/org/eclipse/jface/tests/viewers/VirtualLazyTreeViewerTest.java
@@ -74,7 +74,6 @@
assertTrue(fTreeViewer.isExpandable(nodeElement));
}
-
@Override
public void testRefreshWithDuplicateChild() {
// Test leads to infinite loop. Duplicate children are a bad idea in virtual trees.
@@ -130,6 +129,11 @@
// no need to test since virtual trees do not support sorting
}
+ @Override
+ public void testChildIsNotDuplicatedWhenCompareEquals() {
+ // test is not relevant for lazy tree viewer
+ }
+
// Temporary overrides for bug 347491:
@Override
public void testRefreshWithAddedChildren() {
