WICKET-6021: consistent iteration even after modifications This commit fixes WICKET-6021 by implementing an improved iterator for markupcontainer that is able to act on changes in the implementation of the underlying data structure that stores the children without throwing a ConcurrentModificationException.
Project: http://git-wip-us.apache.org/repos/asf/wicket/repo Commit: http://git-wip-us.apache.org/repos/asf/wicket/commit/9f8f2f2f Tree: http://git-wip-us.apache.org/repos/asf/wicket/tree/9f8f2f2f Diff: http://git-wip-us.apache.org/repos/asf/wicket/diff/9f8f2f2f Branch: refs/heads/lambdas Commit: 9f8f2f2f5f7df873061679c80edd151c94afdd38 Parents: e0c2f1b Author: Martijn Dashorst <[email protected]> Authored: Fri Nov 6 23:32:45 2015 +0100 Committer: Martijn Dashorst <[email protected]> Committed: Sat Nov 7 00:36:41 2015 +0100 ---------------------------------------------------------------------- pom.xml | 5 + wicket-core/pom.xml | 4 + .../java/org/apache/wicket/MarkupContainer.java | 476 ++++++-- .../org/apache/wicket/MarkupContainerTest.java | 1085 +++++++++++++++++- 4 files changed, 1454 insertions(+), 116 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/wicket/blob/9f8f2f2f/pom.xml ---------------------------------------------------------------------- diff --git a/pom.xml b/pom.xml index dbfedb2..171f9b4 100644 --- a/pom.xml +++ b/pom.xml @@ -271,6 +271,11 @@ <optional>true</optional> </dependency> <dependency> + <groupId>org.apache.commons</groupId> + <artifactId>commons-collections4</artifactId> + <version>4.0</version> + </dependency> + <dependency> <groupId>org.apache.velocity</groupId> <artifactId>velocity</artifactId> <version>1.7</version> http://git-wip-us.apache.org/repos/asf/wicket/blob/9f8f2f2f/wicket-core/pom.xml ---------------------------------------------------------------------- diff --git a/wicket-core/pom.xml b/wicket-core/pom.xml index fdc1f4d..add921d 100644 --- a/wicket-core/pom.xml +++ b/wicket-core/pom.xml @@ -43,6 +43,10 @@ <scope>provided</scope> </dependency> <dependency> + <groupId>org.apache.commons</groupId> + <artifactId>commons-collections4</artifactId> + </dependency> + <dependency> <groupId>org.apache.wicket</groupId> <artifactId>wicket-request</artifactId> </dependency> http://git-wip-us.apache.org/repos/asf/wicket/blob/9f8f2f2f/wicket-core/src/main/java/org/apache/wicket/MarkupContainer.java ---------------------------------------------------------------------- diff --git a/wicket-core/src/main/java/org/apache/wicket/MarkupContainer.java b/wicket-core/src/main/java/org/apache/wicket/MarkupContainer.java index 3bef2a8..26fe0f9 100644 --- a/wicket-core/src/main/java/org/apache/wicket/MarkupContainer.java +++ b/wicket-core/src/main/java/org/apache/wicket/MarkupContainer.java @@ -16,14 +16,16 @@ */ package org.apache.wicket; +import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; -import java.util.LinkedHashMap; +import java.util.LinkedList; import java.util.List; import java.util.Map; +import org.apache.commons.collections4.map.LinkedMap; import org.apache.wicket.core.util.string.ComponentStrings; import org.apache.wicket.markup.ComponentTag; import org.apache.wicket.markup.IMarkupFragment; @@ -91,12 +93,11 @@ import org.slf4j.LoggerFactory; * * @see MarkupStream * @author Jonathan Locke - * */ public abstract class MarkupContainer extends Component implements Iterable<Component> { private static final long serialVersionUID = 1L; - + private static final int INITIAL_CHILD_LIST_CAPACITY = 12; /** @@ -108,12 +109,52 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp * We have focused on adding elements to a list, instead of indexed lookups because adding is an * action that is performed very often, and lookups often are done by component IDs, not index. */ - private static final int MAPIFY_THRESHOLD = 24; // 32 * 0.75 + static final int MAPIFY_THRESHOLD = 24; // 32 * 0.75 /** Log for reporting. */ private static final Logger log = LoggerFactory.getLogger(MarkupContainer.class); /** + * Metadata key for looking up the list of removed children necessary for tracking modifications + * during iteration of the children of this markup container. + * + * This is stored in meta data because it only is necessary when a child is removed, and this + * saves the memory necessary for a field on a widely used class. + */ + private static final MetaDataKey<LinkedList<RemovedChild>> REMOVALS_KEY = new MetaDataKey<LinkedList<RemovedChild>>() + { + private static final long serialVersionUID = 1L; + }; + + /** + * Administrative class for detecting removed children during child iteration. Not intended to + * be serializable but for e.g. determining the size of the component it has to be serializable. + */ + private static class RemovedChild implements Serializable + { + private static final long serialVersionUID = 1L; + + private transient final Component removedChild; + private transient final Component previousSibling; + + private RemovedChild(Component removedChild, Component previousSibling) + { + this.removedChild = removedChild; + this.previousSibling = previousSibling; + } + } + + /** + * Administrative counter to keep track of modifications to the list of children during + * iteration. + * + * When the {@link #children_size()} changes due to an addition or removal of a child component, + * the modCounter is increased. This way iterators that iterate over the children of this + * container can keep track when they need to change their iteration strategy. + */ + private transient int modCounter = 0; + + /** * The children of this markup container, if any. Can be a Component when there's only one * child, a List when the number of children is fewer than {@link #MAPIFY_THRESHOLD} or a Map * when there are more children. @@ -137,17 +178,17 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } /** - * Adds a child component to this container. + * Adds the child component(s) to this container. * - * @param childs + * @param children * The child(ren) to add. * @throws IllegalArgumentException * Thrown if a child with the same id is replaced by the add operation. * @return This */ - public MarkupContainer add(final Component... childs) + public MarkupContainer add(final Component... children) { - for (Component child : childs) + for (Component child : children) { Args.notNull(child, "child"); @@ -185,16 +226,9 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp log.debug("Add " + child.getId() + " to " + this); } - // remove child from existing parent - parent = child.getParent(); - if (parent != null) - { - parent.remove(child); - } - - // Add the child to my children - Component previousChild = put(child); - if (previousChild != null) + // Add the child to my children + Component previousChild = children_put(child); + if (previousChild != null && previousChild != child) { throw new IllegalArgumentException( exceptionMessage("A child '" + previousChild.getClass().getSimpleName() + @@ -211,13 +245,13 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp * Replaces a child component of this container with another or just adds it in case no child * with the same id existed yet. * - * @param childs - * The child(s) to be added or replaced - * @return This + * @param children + * The child(ren) to be added or replaced + * @return this markup container */ - public MarkupContainer addOrReplace(final Component... childs) + public MarkupContainer addOrReplace(final Component... children) { - for (Component child : childs) + for (Component child : children) { Args.notNull(child, "child"); @@ -273,12 +307,12 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp // that's all what most auto-components need. Unfortunately child.onDetach() will not / can // not be invoked, since the parent doesn't known its one of his children. Hence we need to // properly add it. - children_remove(component); + children_remove(component.getId()); add(component); - + return true; } - + /** * @param component * The component to check @@ -452,14 +486,14 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } /** - * Get the childs markup + * Get the markup of the child. * * @see Component#getMarkup() * * @param child * The child component. If null, the container's markup will be returned. See Border, * Panel or Enclosure where getMarkup(null) != getMarkup(). - * @return The childs markup + * @return The child's markup */ public IMarkupFragment getMarkup(final Component child) { @@ -468,12 +502,12 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } /** - * Get the type of associated markup for this component. + * Get the type of associated markup for this component. The markup type for a component is + * independent of whether or not the component actually has an associated markup resource file + * (which is determined at runtime). * * @return The type of associated markup for this component (for example, "html", "wml" or - * "vxml"). The markup type for a component is independent of whether or not the - * component actually has an associated markup resource file (which is determined at - * runtime). If there is no markup type for a component, null may be returned, but this + * "vxml"). If there is no markup type for a component, null may be returned, but this * means that no markup can be loaded for the class. Null is also returned if the * component, or any of its parents, has not been added to a Page. */ @@ -505,52 +539,128 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } // Add to map - put(child); + children_put(child); addedComponent(child); } /** + * Gives an iterator that allow you to iterate through the children of this markup container in + * the order the children were added. The iterator supports additions and removals from the list + * of children during iteration. + * * @return Iterator that iterates through children in the order they were added */ @Override - @SuppressWarnings("unchecked") public Iterator<Component> iterator() { - return new Iterator<Component>() - { - Component currentComponent = null; - Iterator<Component> internalIterator = copyChildren().iterator(); + /** + * Iterator that knows how to change between a single child, list of children and map of + * children. Keeps track when the iterator was last sync'd with the markup container's + * tracking of changes to the list of children. + */ + class MarkupChildIterator implements Iterator<Component> + { + private int indexInRemovalsSinceLastUpdate = removals_size(); + private int expectedModCounter = -1; + private Component currentComponent = null; + private Iterator<Component> internalIterator = null; @Override public boolean hasNext() { + refreshInternalIteratorIfNeeded(); return internalIterator.hasNext(); } @Override public Component next() { + refreshInternalIteratorIfNeeded(); return currentComponent = internalIterator.next(); } @Override public void remove() { - if (children instanceof Component) + MarkupContainer.this.remove(currentComponent); + refreshInternalIteratorIfNeeded(); + } + + private void refreshInternalIteratorIfNeeded() + { + if (modCounter != 0 && expectedModCounter >= modCounter) + return; + + if (children == null) + { + internalIterator = Collections.emptyIterator(); + } + else if (children instanceof Component) + { + internalIterator = Collections.singleton((Component)children).iterator(); + } + else if (children instanceof List) { - children = null; + List<Component> childrenList = children(); + internalIterator = childrenList.iterator(); } else { - internalIterator.remove(); + Map<String, Component> childrenMap = children(); + internalIterator = childrenMap.values().iterator(); + } + + // since we now have a new iterator, we need to set it to the last known position + currentComponent = findLastExistingChildAlreadyReturned(currentComponent); + expectedModCounter = modCounter; + indexInRemovalsSinceLastUpdate = removals_size(); + + if (currentComponent != null) + { + // move the new internal iterator to the place of the last processed component + while (internalIterator.hasNext() && + internalIterator.next() != currentComponent) + // noop + ; + } + } + + private Component findLastExistingChildAlreadyReturned(Component target) + { + while (true) + { + if (target == null) + return null; + + RemovedChild removedChild = null; + for (int i = indexInRemovalsSinceLastUpdate; i < removals_size(); i++) + { + RemovedChild curRemovedChild = removals_get(i); + if (curRemovedChild.removedChild == target || + curRemovedChild.removedChild == null) + { + removedChild = curRemovedChild; + break; + } + } + if (removedChild == null) + { + return target; + } + else + { + target = removedChild.previousSibling; + } } - checkHierarchyChange(currentComponent); - removedComponent(currentComponent); } }; + return new MarkupChildIterator(); } /** + * Creates an iterator that iterates over children in the order specified by comparator. This + * works on a copy of the children list. + * * @param comparator * The comparator * @return Iterator that iterates over children in the order specified by comparator @@ -563,6 +673,8 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } /** + * Removes a component from the children identified by the {@code component.getId()} + * * @param component * Component to remove from this container * @return {@code this} for chaining @@ -573,7 +685,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp Args.notNull(component, "component"); - children_remove(component); + children_remove(component.getId()); removedComponent(component); return this; @@ -618,7 +730,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp { addStateChange(); - for (Component child: this) + for (Component child : this) { // Do not call remove() because the state change would then be // recorded twice. @@ -628,6 +740,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } children = null; + removals_add(null, null); } return this; @@ -719,8 +832,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp if (child.getParent() != this) { - // Get the child component to replace - final Component replaced = children_get(child.getId()); + final Component replaced = children_put(child); // Look up to make sure it was already in the map if (replaced == null) @@ -729,10 +841,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp exceptionMessage("Cannot replace a component which has not been added: id='" + child.getId() + "', component=" + child)); } - - // Add to map - put(child); - + // first remove the component. removedComponent(replaced); @@ -881,7 +990,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp Args.notNull(child, "child"); MarkupContainer parent = child.getParent(); - if (parent != null) + if (parent != null && parent != this) { parent.remove(child); } @@ -957,13 +1066,58 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp }); } + /* + * === Internal management for keeping track of child components === + * + * A markup container is the base component for containing child objects. It is one of the most + * heavily used components so we should keep it's (memory and CPU) footprint small. + * + * The goals for the internal management of the list of child components are: + * + * - as low big-O complexity as possible, preferrably O(1) + * + * - as low memory consumption as possible (don't use more memory than strictly necessary) + * + * - ensure that iterating through the (list of) children be as consistent as possible + * + * - retain the order of addition in the iteration + * + * These goals are attained by storing the children in a single field that is implemented using: + * + * - a component when there's only one child + * + * - a list of components when there are more than 1 children + * + * - a map of components when the number of children makes looking up children by id more costly + * than an indexed search (see MAPIFY_THRESHOLD) + * + * To ensure that iterating through the list of children keeps working even when children are + * added, replaced and removed without throwing a ConcurrentModificationException a special + * iterator is used. The markup container tracks removals from and additions to the children + * during the request, enabling the iterator to skip over those items and adjust to changing + * internal data structures. + */ + /** + * A type washing accessor method for getting the children without having to cast the field + * explicitly. * - * @param id - * @return The child component + * @return the children as a T */ @SuppressWarnings("unchecked") - private Component children_get(final String id) + private <T> T children() + { + return (T)children; + } + + /** + * Gets the child with the given {@code childId} + * + * @param childId + * the component identifier + * @return The child component or {@code null} when no child with the given identifier exists + */ + private Component children_get(final String childId) { if (children == null) { @@ -971,77 +1125,88 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } if (children instanceof Component) { - return ((Component)children).getId().equals(id) ? (Component)children : null; + Component child = children(); + return child.getId().equals(childId) ? child : null; } if (children instanceof List) { - for (Component child : (List<Component>)children) + List<Component> kids = children(); + for (Component child : kids) { - if (child.getId().equals(id)) + if (child.getId().equals(childId)) { return child; } } return null; } - return ((Map<String, Component>)children).get(id); + Map<String, Component> kids = children(); + return kids.get(childId); } /** + * Removes the child component identified by {@code childId} from the list of children. * - * @param component - * @return The component that is removed. + * Will change the internal list or map to a single component when the number of children hits + * 1, but not change the internal map to a list when the threshold is reached (the memory was + * already claimed, so there's little to be gained other than wasting CPU cycles for the + * conversion). + * + * @param childId + * the id of the child component to remove */ - private Component children_remove(Component component) + private void children_remove(String childId) { - if (children == null) - { - return null; - } if (children instanceof Component) { - if (((Component)children).getId().equals(component.getId())) + Component oldChild = children(); + if (oldChild.getId().equals(childId)) { - Component oldChild = (Component)children; children = null; - return oldChild; + removals_add(oldChild, null); } - return null; } - if (children instanceof List) + else if (children instanceof List) { - @SuppressWarnings("unchecked") - List<Component> childrenList = (List<Component>)children; + List<Component> childrenList = children(); Iterator<Component> it = childrenList.iterator(); + Component prevChild = null; while (it.hasNext()) { Component child = it.next(); - if (child.getId().equals(component.getId())) + if (child.getId().equals(childId)) { it.remove(); + removals_add(child, prevChild); if (childrenList.size() == 1) { children = childrenList.get(0); } - return child; + return; } + prevChild = child; } - return null; } - - @SuppressWarnings("unchecked") - Map<String, Component> childrenMap = (Map<String, Component>)children; - Component oldChild = childrenMap.remove(component.getId()); - if (childrenMap.size() == 1) + else if (children instanceof LinkedMap) { - children = childrenMap.values().iterator().next(); + LinkedMap<String, Component> childrenMap = children(); + if (childrenMap.containsKey(childId)) + { + String prevSiblingId = childrenMap.previousKey(childId); + Component oldChild = childrenMap.remove(childId); + removals_add(oldChild, childrenMap.get(prevSiblingId)); + if (childrenMap.size() == 1) + { + children = childrenMap.values().iterator().next(); + } + } } - return oldChild; } /** + * Gets the number of child components of this markup container. * - * @return The size of the children + * @return The number of children */ private int children_size() { @@ -1055,29 +1220,42 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } if (children instanceof List) { - return ((List<?>)children).size(); + List<?> kids = children(); + return kids.size(); } return ((Map<?, ?>)children).size(); } /** - * Ensure that there is space in childForId map for a new entry before adding it. + * Puts the {@code child} component into the list of children of this markup container. If a + * component existed with the same {@code child.getId()} it is replaced and the old component is + * returned. + * + * When a component is replaced, the internal structure of the children is not modified, so we + * don't have to update the internal {@link #modCounter} in those circumstances. When a + * component is added, we do have to increase the {@link #modCounter} to notify iterators of + * this change. * * @param child - * The child to put into the map + * The child * @return Any component that was replaced */ - @SuppressWarnings("unchecked") - private Component put(final Component child) + private Component children_put(final Component child) { if (children == null) { children = child; + + // it is an addtion, so we need to notify the iterators of this change. + modCounter++; + return null; } + if (children instanceof Component) { - Component oldChild = (Component)children; + /* first see if the child replaces the existing child */ + Component oldChild = children(); if (oldChild.getId().equals(child.getId())) { children = child; @@ -1085,17 +1263,27 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } else { - Component originalChild = (Component)children; + /* + * the put doesn't replace the existing child, so we need to increase the children + * storage to a list and add the existing and new child to it + */ + Component originalChild = children(); List<Component> newChildren = new ArrayList<>(INITIAL_CHILD_LIST_CAPACITY); newChildren.add(originalChild); newChildren.add(child); children = newChildren; + + // it is an addtion, so we need to notify the iterators of this change. + modCounter++; return null; } } + if (children instanceof List) { - List<Component> childrenList = (List<Component>)children; + List<Component> childrenList = children(); + + // first see if the child replaces an existing child for (int i = 0; i < childrenList.size(); i++) { Component curChild = childrenList.get(i); @@ -1104,13 +1292,21 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp return childrenList.set(i, child); } } + + // it is an addtion, so we need to notify the iterators of this change. + modCounter++; + + /* + * If it still fits in the allotted number of items of a List, just add it, otherwise + * change the internal data structure to a Map for speedier lookups. + */ if (childrenList.size() < MAPIFY_THRESHOLD) { childrenList.add(child); } else { - Map<String, Component> newChildren = new LinkedHashMap<>(MAPIFY_THRESHOLD * 2); + Map<String, Component> newChildren = new LinkedMap<>(MAPIFY_THRESHOLD * 2); for (Component curChild : childrenList) { newChildren.put(curChild.getId(), curChild); @@ -1120,7 +1316,92 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp } return null; } - return ((Map<String, Component>)children).put(child.getId(), child); + + Map<String, Component> childrenMap = children(); + Component oldChild = childrenMap.put(child.getId(), child); + + if (oldChild == null) + { + // it is an addtion, so we need to notify the iterators of this change. + modCounter++; + } + return oldChild; + } + + /** + * Retrieves the during the request removed children. These are stored in the metadata and + * cleared at the end of the request {@link #onDetach()} + * + * @return the list of removed children, may be {@code null} + */ + private LinkedList<RemovedChild> removals_get() + { + return getMetaData(REMOVALS_KEY); + } + + /** + * Sets the during the request removed children. These are stored in the metadata and cleared at + * the end of the request, see {@link #onDetach()}. + * + * @param removals + * the new list of removals + */ + private void removals_set(LinkedList<RemovedChild> removals) + { + setMetaData(REMOVALS_KEY, removals); + } + + /** + * Removes the list of removals from the metadata. + */ + private void removals_clear() + { + setMetaData(REMOVALS_KEY, null); + } + + /** + * Adds the {@code removedChild} to the list of removals and links it to the + * {@code previousSibling} + * + * @param removedChild + * the child that was removed + * @param prevSibling + * the child that was the previous sibling of the removed child + */ + private void removals_add(Component removedChild, Component prevSibling) + { + modCounter++; + + LinkedList<RemovedChild> removals = removals_get(); + if (removals == null) + { + removals = new LinkedList<>(); + removals_set(removals); + } + removals.add(new RemovedChild(removedChild, prevSibling)); + } + + /** + * Gets the {@link RemovedChild} from the list of removals at given position. + * + * @param i + * the position + * @return the removed child + */ + private RemovedChild removals_get(int i) + { + return getMetaData(REMOVALS_KEY).get(i); + } + + /** + * Gets the number of removals that happened during the request. + * + * @return the number of removals + */ + private int removals_size() + { + LinkedList<RemovedChild> removals = removals_get(); + return removals == null ? 0 : removals.size(); } /** @@ -1135,7 +1416,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp { page.componentRemoved(component); } - + component.detach(); component.internalOnRemove(); @@ -1181,7 +1462,7 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp component.setMarkup(markupStream.getMarkupFragment()); } } - + // Failed to find it? if (component != null) { @@ -1551,6 +1832,9 @@ public abstract class MarkupContainer extends Component implements Iterable<Comp { super.onDetach(); + modCounter = 0; + removals_clear(); + if (queue != null && !queue.isEmpty()) { throw new WicketRuntimeException( http://git-wip-us.apache.org/repos/asf/wicket/blob/9f8f2f2f/wicket-core/src/test/java/org/apache/wicket/MarkupContainerTest.java ---------------------------------------------------------------------- diff --git a/wicket-core/src/test/java/org/apache/wicket/MarkupContainerTest.java b/wicket-core/src/test/java/org/apache/wicket/MarkupContainerTest.java index 4c24c02..aba2148 100644 --- a/wicket-core/src/test/java/org/apache/wicket/MarkupContainerTest.java +++ b/wicket-core/src/test/java/org/apache/wicket/MarkupContainerTest.java @@ -16,22 +16,39 @@ */ package org.apache.wicket; +import static org.hamcrest.CoreMatchers.equalToObject; +import static org.hamcrest.CoreMatchers.instanceOf; +import static org.hamcrest.CoreMatchers.is; +import static org.hamcrest.CoreMatchers.not; +import static org.hamcrest.CoreMatchers.nullValue; +import static org.hamcrest.CoreMatchers.sameInstance; +import static org.hamcrest.Matchers.greaterThanOrEqualTo; + +import java.lang.reflect.Field; +import java.util.ConcurrentModificationException; +import java.util.Iterator; +import java.util.List; +import java.util.Random; + +import org.apache.commons.collections4.map.LinkedMap; +import org.apache.wicket.core.util.lang.WicketObjects; import org.apache.wicket.markup.IMarkupResourceStreamProvider; import org.apache.wicket.markup.html.WebComponent; import org.apache.wicket.markup.html.WebMarkupContainer; import org.apache.wicket.markup.html.WebPage; +import org.apache.wicket.markup.html.basic.Label; +import org.apache.wicket.markup.html.panel.EmptyPanel; import org.apache.wicket.util.resource.IResourceStream; import org.apache.wicket.util.resource.StringResourceStream; import org.apache.wicket.util.tester.WicketTestCase; +import org.junit.Assert; import org.junit.Test; - -/** - * - * @author Juergen Donnerstag - */ +@SuppressWarnings({ "javadoc", "serial" }) public class MarkupContainerTest extends WicketTestCase { + private static final int NUMBER_OF_CHILDREN_FOR_A_MAP = MarkupContainer.MAPIFY_THRESHOLD + 1; + /** * Make sure components are iterated in the order they were added. Required e.g. for Repeaters */ @@ -50,18 +67,12 @@ public class MarkupContainerTest extends WicketTestCase } } - /** - * @throws Exception - */ @Test public void markupId() throws Exception { executeTest(MarkupIdTestPage.class, "MarkupIdTestPageExpectedResult.html"); } - /** - * - */ @Test public void get() { @@ -125,9 +136,12 @@ public class MarkupContainerTest extends WicketTestCase public void rerenderAfterRenderFailure() { FirstRenderFailsPage page = new FirstRenderFailsPage(); - try { + try + { tester.startPage(page); - } catch (WicketRuntimeException expected) { + } + catch (WicketRuntimeException expected) + { } tester.startPage(page); @@ -204,7 +218,9 @@ public class MarkupContainerTest extends WicketTestCase } } - private static class FirstRenderFailsPage extends WebPage implements IMarkupResourceStreamProvider + private static class FirstRenderFailsPage extends WebPage + implements + IMarkupResourceStreamProvider { private boolean firstRender = true; @@ -212,15 +228,17 @@ public class MarkupContainerTest extends WicketTestCase private FirstRenderFailsPage() { - - WebMarkupContainer a1 = new WebMarkupContainer("a1") { + WebMarkupContainer a1 = new WebMarkupContainer("a1") + { @Override - protected void onBeforeRender() { + protected void onBeforeRender() + { super.onBeforeRender(); beforeRenderCalls++; - if (firstRender) { + if (firstRender) + { firstRender = false; throw new WicketRuntimeException(); } @@ -233,8 +251,1035 @@ public class MarkupContainerTest extends WicketTestCase public IResourceStream getMarkupResourceStream(MarkupContainer container, Class<?> containerClass) { - return new StringResourceStream( - "<html><body><div wicket:id='a1'></div></body></html>"); + return new StringResourceStream("<html><body><div wicket:id='a1'></div></body></html>"); } } + + + /* + * Iterator tests + * + * The tests below are specific for testing addition and removal of children while maintaining + * the correct order of iterators without throwing ConcurrentModificationException. + */ + + @Test + public void noChildShouldNotIterate() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Iterator<Component> iterator = wmc.iterator(); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildAddingChildAfterIteratorAcquiredShouldIterateAndReturnNewChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Iterator<Component> iterator = wmc.iterator(); + + Label label1 = new Label("label1", "Label1"); + wmc.add(label1); + + assertThat(wmc.size(), is(1)); + + Assert.assertThat(iterator.hasNext(), is(true)); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildAddingNChildrenAfterIteratorAcquiredShouldIterateAndReturnNewChildren() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Iterator<Component> iterator = wmc.iterator(); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + assertThat(wmc.size(), is(NUMBER_OF_CHILDREN_FOR_A_MAP)); + + Label label1 = new Label("label1", "Label1"); + wmc.add(label1); + + Assert.assertThat(iterator.hasNext(), is(true)); + + takeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildAddingNChildrenAfterIteratorAcquiredShouldIterateAndReturnNewChildren2() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + assertThat(wmc.size(), is(NUMBER_OF_CHILDREN_FOR_A_MAP)); + + Iterator<Component> iterator = wmc.iterator(); + + takeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Label label1 = new Label("label1", "Label1"); + wmc.add(label1); + + Assert.assertThat(iterator.hasNext(), is(true)); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildAddingAndRemoveChildAfterIteratorAcquiredShouldNotIterate() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.add(label1); + wmc.remove(label1); + + assertThat(wmc.size(), is(0)); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void addingNewChildAfterIterationHasStartedShouldIterateNewChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + // add one child + addNChildren(wmc, 1); + + Iterator<Component> iterator = wmc.iterator(); + + // iterate + takeNChildren(iterator, 1); + + // there are no more children to iterate + Assert.assertThat(iterator.hasNext(), is(false)); + + // add the new child + Label newChild = new Label("label1", "Label1"); + wmc.add(newChild); + + assertThat(wmc.size(), is(2)); + + // ensure that the newChild is up next (as it was added) + Assert.assertThat(iterator.next(), is(equalToObject(newChild))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void replacingTheFirstChildAfterIteratingDoesntIterateTheNewChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + Component label2 = new Label("label2", "Label2"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + wmc.add(label1); + wmc.add(label2); + + Iterator<Component> iterator = wmc.iterator(); + + takeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP); + + iterator.next(); + + // replace the first child **after** we already passed the child with the iterator + Label newChild = new Label("label1", "newChild"); + wmc.replace(newChild); + + // the next child is still label 2 + assertThat(iterator.next(), is(sameInstance(label2))); + + // and the new child is not iterated (was replaced before the current position of the + // iterator). + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void removingComponentsDuringIterationDoesntFail() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Component label1 = new Label("label1", "Label1"); + Component label2 = new Label("label2", "Label2"); + Component label3 = new Label("label3", "Label3"); + Component label4 = new Label("label4", "Label4"); + Component label5 = new Label("label5", "Label5"); + + wmc.add(label1); + wmc.add(label2); + wmc.add(label3); + wmc.add(label4); + wmc.add(label5); + + // start iterating the 5 children + Iterator<Component> iterator = wmc.iterator(); + + assertThat(iterator.next(), is(sameInstance(label1))); + assertThat(iterator.next(), is(sameInstance(label2))); + assertThat(iterator.next(), is(sameInstance(label3))); + + // remove the current, previous and next children + wmc.remove(label3); + wmc.remove(label2); + wmc.remove(label4); + + // ensure that the next iterated child is the 5th label + assertThat(iterator.next(), is(sameInstance(label5))); + + // and that there are no more children to iterate + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void childrenBecomesListWhenMoreThanOneChild() throws Exception + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, 5); + + Field childrenField = MarkupContainer.class.getDeclaredField("children"); + childrenField.setAccessible(true); + Object field = childrenField.get(wmc); + assertThat(field, is(instanceOf(List.class))); + } + + @Test + public void childrenListBecomesMapWhenThresholdPassed() throws Exception + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP - 1); + assertChildrenType(wmc, List.class); + + addNChildren(wmc, 1); + assertChildrenType(wmc, LinkedMap.class); + } + + @Test + public void childrenBecomesLinkedMapWhenThresholdPassed() throws Exception + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP + 1); + + assertChildrenType(wmc, LinkedMap.class); + } + + @Test + public void linkedMapChildrenBecomesChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + wmc.add(new EmptyPanel("panel")); + + assertChildrenType(wmc, LinkedMap.class); + + Iterator<Component> iterator = wmc.iterator(); + removeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP); + + assertChildrenType(wmc, EmptyPanel.class); + } + + @Test + public void listChildrenBecomesChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP - 2); + wmc.add(new EmptyPanel("panel")); + + assertChildrenType(wmc, List.class); + + Iterator<Component> iterator = wmc.iterator(); + removeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP - 2); + + assertChildrenType(wmc, EmptyPanel.class); + } + + @Test + public void geenIdee3() throws Exception + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP + 1); + + Iterator<Component> iterator = wmc.iterator(); + + removeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP); + + assertThat(iterator.hasNext(), is(true)); + assertThat(wmc.size(), is(1)); + + iterator.next(); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildAddIterateAndRemoveChildShouldIterateChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.add(label1); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + + wmc.remove(label1); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildAddIterateAndRemoveAndAddSameChildShouldIterateChildTwice() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.add(label1); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + + Assert.assertThat(iterator.hasNext(), is(false)); + + wmc.remove(label1); + + Assert.assertThat(iterator.hasNext(), is(false)); + + wmc.add(label1); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + } + + @Test + public void noChildAddIterateAndRemoveAndAddDifferentChildShouldIterateNewChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + Label label2 = new Label("label1", "Label2"); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.add(label1); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + + Assert.assertThat(iterator.hasNext(), is(false)); + + wmc.remove(label1); + + Assert.assertThat(iterator.hasNext(), is(false)); + + wmc.add(label2); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + } + + @Test + public void noChildAddingAndReplaceChildAfterIteratorAcquiredShouldIterateAndReturnNewReplacementChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + Label label2 = new Label("label1", "Label2"); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.add(label1); + wmc.replace(label2); + + Assert.assertThat(iterator.hasNext(), is(true)); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void singleChildIterateOneChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + wmc.add(label1 = new Label("label1", "Label1")); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.hasNext(), is(true)); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void singleChildShouldAllowReplacingChildAfterIterationHasStarted() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Component label1 = new Label("label1", "Label1"); + Component label2 = new Label("label1", "Label2"); + + wmc.add(label1); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.replace(label2); + + Assert.assertThat(iterator.hasNext(), is(true)); + Assert.assertThat(iterator.next(), is(sameInstance(label2))); + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void singleChildShouldAllowReplacingVisitedChildButNotRevisitReplacementChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + Label label2 = new Label("label1", "Label2"); + wmc.add(label1); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.hasNext(), is(true)); + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + + wmc.replace(label2); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void multipleChildIteratorRetainsOrderOfAddition() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + wmc.add(label3 = new Label("label3", "Label3")); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowAddingComponentAfterIterationStarted() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + + wmc.add(label3 = new Label("label3", "Label3")); + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowRemovingComponentAfterIterationStarted0() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + wmc.add(label3 = new Label("label3", "Label3")); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.remove(label1); + + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowRemovingComponentAfterIterationStarted1() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1 = new Label("label1", "Label1"); + Label label2 = new Label("label2", "Label2"); + Label label3 = new Label("label3", "Label3"); + wmc.add(label1); + wmc.add(label2); + wmc.add(label3); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + wmc.remove(label1); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowRemovingComponentAfterIterationStarted2() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + wmc.add(label3 = new Label("label3", "Label3")); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + wmc.remove(label1); + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowRemovingComponentAfterIterationStarted3() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + wmc.add(label3 = new Label("label3", "Label3")); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + wmc.remove(label1); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowReplacingComponentAfterIterationStarted0() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.replace(label3 = new Label("label1", "Label3")); + + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowReplacingComponentAfterIterationStarted1() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.replace(label3 = new Label("label1", "Label3")); + + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowReplacingComponentAfterIterationStarted() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + Assert.assertThat(iterator.next(), is(equalToObject(label2))); + + wmc.replace(label3 = new Label("label1", "Label3")); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void iteratorShouldAllowReplacingComponentAfterIterationStarted24() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + Label label1; + Label label2; + Label label3; + wmc.add(label1 = new Label("label1", "Label1")); + wmc.add(label2 = new Label("label2", "Label2")); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Iterator<Component> iterator = wmc.iterator(); + + Assert.assertThat(iterator.next(), is(equalToObject(label1))); + + wmc.replace(label3 = new Label("label2", "Label3")); + + Assert.assertThat(iterator.next(), is(equalToObject(label3))); + + takeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Assert.assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildLeftBehindRemoveEach() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Iterator<Component> iterator = wmc.iterator(); + while (iterator.hasNext()) + { + iterator.next(); + iterator.remove(); + } + assertThat(wmc.size(), is(0)); + } + + @Test + public void noChildLeftBehindRemoveAll() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Iterator<Component> iterator = wmc.iterator(); + + wmc.removeAll(); + + assertThat(wmc.size(), is(0)); + assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void noChildLeftBehindRemoveAll2() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + Iterator<Component> iterator = wmc.iterator(); + + iterator.next(); + + wmc.removeAll(); + + assertThat(wmc.size(), is(0)); + assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void ensureSerializationDeserializationWorks() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Iterator<Component> iterator = wmc.iterator(); + + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + assertThat(wmc.size(), is(NUMBER_OF_CHILDREN_FOR_A_MAP)); + + assertThat(WicketObjects.cloneObject(wmc), is(not(nullValue()))); + + removeNChildren(iterator, 1); + assertThat(wmc.size(), is(NUMBER_OF_CHILDREN_FOR_A_MAP - 1)); + assertThat(WicketObjects.cloneObject(wmc), is(not(nullValue()))); + + removeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP - 2); + assertThat(WicketObjects.cloneObject(wmc), is(not(nullValue()))); + + assertThat(wmc.size(), is(1)); + removeNChildren(iterator, 1); + assertThat(wmc.size(), is(0)); + assertThat(WicketObjects.cloneObject(wmc), is(not(nullValue()))); + } + + @Test + public void detachDuringIterationWorks() + { + int halfOfChildren = NUMBER_OF_CHILDREN_FOR_A_MAP / 2; + int numberOfRemainingChildren = halfOfChildren + NUMBER_OF_CHILDREN_FOR_A_MAP % 2; + + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Iterator<Component> iterator = wmc.iterator(); + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP); + + takeNChildren(iterator, halfOfChildren); + + wmc.detach(); + + takeNChildren(iterator, numberOfRemainingChildren); + + assertThat(iterator.hasNext(), is(false)); + } + + @Test + public void detachDuringIterationWithRemovalsSucceeds() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + + Iterator<Component> iterator = wmc.iterator(); + + addNChildren(wmc, 2); + removeNChildren(iterator, 1); + wmc.detach(); + takeNChildren(iterator, 1); + + assertThat(iterator.hasNext(), is(false)); + assertThat(wmc.size(), is(1)); + } + + /** + * Tests whether two iterators being used simultaneously keep correct score of where they are. + */ + @Test + public void twoIteratorsWorkInTandem() + { + int n = NUMBER_OF_CHILDREN_FOR_A_MAP * 2; + + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, n); + + Iterator<Component> iterator1 = wmc.iterator(); + Iterator<Component> iterator2 = wmc.iterator(); + + Random r = new Random(); + + for (int i = 0; i < n; i++) + { + if (r.nextBoolean()) + { + iterator1.next(); + iterator1.remove(); + } + else + { + iterator2.next(); + iterator2.remove(); + } + } + + // after 2*N removals there should not be any child left + assertThat(iterator1.hasNext(), is(false)); + assertThat(iterator2.hasNext(), is(false)); + } + + /** + * Tests removing a child when an iterator is active, followed by a detach still has the correct + * state for the iterator. + */ + @Test + public void detachWithOneIteratorOneChild() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, 1); + + Iterator<Component> iterator1 = wmc.iterator(); + + iterator1.next(); + iterator1.remove(); + + wmc.detach(); + + assertThat(iterator1.hasNext(), is(false)); + } + + /** + * Tests removing and adding a component when an iterator is active, followed by a detach still + * has the correct state for the iterator. + */ + @Test + public void detachWithOneIteratorOneChildRemovedAndAdded() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, 1); + + Iterator<Component> iterator1 = wmc.iterator(); + + iterator1.next(); + iterator1.remove(); + + addNChildren(wmc, 1); + + assertThat(iterator1.hasNext(), is(true)); + + wmc.detach(); + + assertThat(iterator1.hasNext(), is(true)); + assertThat(iterator1.next(), is(not(nullValue()))); + } + + /** + * Tests the case when one child is removed from a list the iterator still works after a detach. + */ + @Test + public void detachWithOneIteratorTwoChildren() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, 2); + + Iterator<Component> iterator1 = wmc.iterator(); + + iterator1.next(); + iterator1.remove(); + + assertThat(iterator1.hasNext(), is(true)); + + wmc.detach(); + + assertThat(iterator1.hasNext(), is(true)); + assertThat(iterator1.next(), is(not(nullValue()))); + } + + /** + * Tests whether when the children is a list, removal and iteration still work after a detach. + */ + @Test + public void detachWithOneIteratorWithListForChildren() + { + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, NUMBER_OF_CHILDREN_FOR_A_MAP - 2); + + assertChildrenType(wmc, List.class); + + Iterator<Component> iterator = wmc.iterator(); + + takeNChildren(iterator, 1); + + removeNChildren(iterator, 1); + + wmc.detach(); + + takeNChildren(iterator, NUMBER_OF_CHILDREN_FOR_A_MAP - 4); + assertThat(iterator.hasNext(), is(false)); + } + + /** + * Tests whether when the children is a map, removal and iteration still work after a detach. + */ + @Test + public void detachWithOneIteratorsWithMapForChildren() + { + int n = NUMBER_OF_CHILDREN_FOR_A_MAP * 2; + + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, n); + + Iterator<Component> iterator1 = wmc.iterator(); + + Random r = new Random(); + + for (int i = 0; i < NUMBER_OF_CHILDREN_FOR_A_MAP; i++) + { + iterator1.next(); + iterator1.remove(); + } + wmc.detach(); + for (int i = 0; i < NUMBER_OF_CHILDREN_FOR_A_MAP; i++) + { + iterator1.next(); + iterator1.remove(); + } + assertThat(iterator1.hasNext(), is(false)); + } + + /** + * This tests a functional bug in the iterator implementation where you have multiple iterators + * traversing the children, a detach happens and one of the iterators removes a child component + * before the other iterator has a chance to update its internal state to the new world. This is + * a known bug and we expect that this doesn't pose a problem in real world usage. + */ + @Test(expected = ConcurrentModificationException.class) + public void knownBugForDetachWithTwoIteratorsAndRemovals() + { + int n = NUMBER_OF_CHILDREN_FOR_A_MAP * 2; + + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, n); + + Iterator<Component> iterator1 = wmc.iterator(); + Iterator<Component> iterator2 = wmc.iterator(); + + Random r = new Random(); + + for (int i = 0; i < NUMBER_OF_CHILDREN_FOR_A_MAP; i++) + { + if (r.nextBoolean()) + { + iterator1.next(); + iterator1.remove(); + } + else + { + iterator2.next(); + iterator2.remove(); + } + } + wmc.detach(); + iterator1.next(); + iterator1.remove(); + + // implementation detail that gets in the way of properly solving this exotic use case: at + // this moment iterator 2 doesn't know that the modification count was reset before the + // iterator 1 removed the component. + iterator2.next(); + + // code never reaches this point due to the ConcurrentModificationException + } + + /** + * This test is the working case for the above scenario where two iterators traverse the + * children, the component gets detached and in this case both iterators have a chance to update + * their internal state to the new world, before they continue to traverse the children. + */ + @Test + public void detachWithTwoIteratorsAndRemovalsWork() + { + int n = NUMBER_OF_CHILDREN_FOR_A_MAP * 2; + + WebMarkupContainer wmc = new WebMarkupContainer("id"); + addNChildren(wmc, n); + + Iterator<Component> iterator1 = wmc.iterator(); + Iterator<Component> iterator2 = wmc.iterator(); + + Random r = new Random(); + + for (int i = 0; i < NUMBER_OF_CHILDREN_FOR_A_MAP; i++) + { + Iterator<Component> iterator = r.nextBoolean() ? iterator1 : iterator2; + if (iterator.hasNext()) + { + iterator.next(); + iterator.remove(); + } + } + wmc.detach(); + iterator1.next(); + iterator2.next(); + iterator1.remove(); + while (iterator1.hasNext() || iterator2.hasNext()) + { + Iterator<Component> iterator = r.nextBoolean() ? iterator1 : iterator2; + if (iterator.hasNext()) + { + iterator.next(); + iterator.remove(); + } + } + assertThat(iterator1.hasNext(), is(false)); + assertThat(iterator2.hasNext(), is(false)); + } + + /** + * Asserts that the children property of the {@code wmc} is of a particular {@code type}. + * + * @param wmc + * the web markup container whose children property is to be checked + * @param type + * the expected type + */ + private void assertChildrenType(WebMarkupContainer wmc, Class<?> type) + { + try + { + Field childrenField = MarkupContainer.class.getDeclaredField("children"); + childrenField.setAccessible(true); + Object field = childrenField.get(wmc); + assertThat(field, is(instanceOf(type))); + } + catch (Exception e) + { + throw new AssertionError("Unable to read children", e); + } + } + + /** + * Adds {@code numberOfChildrenToAdd} anonymous children to the {@code parent}. + * + * @param parent + * the parent to add the children to + * @param numberOfChildrenToAdd + * the number of children + */ + private void addNChildren(WebMarkupContainer parent, int numberOfChildrenToAdd) + { + assertThat(numberOfChildrenToAdd, is(greaterThanOrEqualTo(0))); + int start = parent.size(); + for (int i = 0; i < numberOfChildrenToAdd; i++) + { + int index = start + i; + parent.add(new Label("padding" + index, "padding" + index)); + } + } + + /** + * Removes {@code numberOfChildrenToRemove} anonymous children from the parent using the + * {@code iterator}. + * + * @param iterator + * the iterator to remove the children with + * @param numberOfChildrenToAdd + * the number of children + */ + private void removeNChildren(Iterator<Component> iterator, int numberOfChildrenToRemove) + { + for (int i = 0; i < numberOfChildrenToRemove; i++) + { + iterator.next(); + iterator.remove(); + } + } + + /** + * Progresses the {@code iterator} with {@code numberOfChildrenToTake} anonymous children. + * + * @param iterator + * the iterator to progress + * @param numberOfChildrenToTake + * the number of children + */ + private void takeNChildren(Iterator<Component> iterator, int numberOfChildrenToTake) + { + for (int i = 0; i < numberOfChildrenToTake; i++) + iterator.next(); + } }
