commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Vahrst (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (COLLECTIONS-310) Modifications of a SetUniqueList.subList() invalidate the parent list
Date Sat, 02 Feb 2013 13:04:12 GMT

    [ https://issues.apache.org/jira/browse/COLLECTIONS-310?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13569532#comment-13569532
] 

Thomas Vahrst edited comment on COLLECTIONS-310 at 2/2/13 1:02 PM:
-------------------------------------------------------------------

I took a deeper look on this issue and the suggested behavior/junit tests and tried to understand
the problem(s). It seems, there a two issues with the current implementation regarding modifications
of sublists:
# Modifications of sublist items are delegated to the underlying backing list (which is the
default sublist implementation) but *not* to the internal set of the parent SetUniqueList.
 So a new entry is added to the list, but the contains() method of the parent SetUniqueList
returns false
# Modifications of the sublist may result in changes *outside* the range of the sublist. For
example adding an element which is not in the sublist but somewhere in the backing list should
result in *moving* the item from its current position to the new position defined by the subset.
This move may corrupt the internal range offsets of the sublist. 

The first issue seems easy to solve, for example by holding a reference of the parent set
in the subset. But if another subset is created based on the first subset, we have to maintain
a collections of parent sets.

The second issue is similar to a direct modification of a backing list - which is not supported.
The javadoc of sublist states
{quote}
The semantics of the list returned by this method become undefined if the backing list (i.e.,
this list) is structurally modified in any way other than via the returned list. (Structural
modifications are those that change the size of this list, or otherwise perturb it in such
a fashion that iterations in progress may yield incorrect results.)
{quote}

To solve this problem, the subList implementation has to track all modifications of the backing
list and adjust it's internal range offsets accordingly. For example adding a duplicate item
to a sublist, which exists  'in front' of the sublist will result 
- moving the item to the new sublist position 
- decrement the range offsets of the sublist. 

So first of all I wrote a short javadoc comment for the sublist method:
{code}
    /**
     * Returns a view of the portion of this list between the specified 
     * fromIndex, inclusive, and toIndex, exclusive.
     * <p>
     * <i>(Violation)</i> According to the <code>List</code> interface
the returned
     * sublist has to be backed by the original list. Because a <code>SetUniqueList</code>
     * requires both a defined ordering of the list items <i>and</i> uniqueness
of
     * all list items, modifications cannot garantee consistant behavior of both
     * the backing list and the sub list. It is strongly recommended not to modify
     * the sublist. 
     * <p>
     * 
     * @param fromIndex
     * @param toIndex
     * @return 
     */

{code}

Should we perhaps return the sublist as a UnmodifiableList?




                
      was (Author: t.vahrst):
    I took a deeper look on this issue and the suggested behavior/junit tests and tried to
understand the problem(s). It seems, there a two issues with the current implementation regarding
modifications of sublists:
# Modifications of sublist items are delegated to the underlying backing list (which is the
default sublist implementation) but *not* to the internal set of the parent SetUniqueList.
 So a new entry is added to the list, but the contains() method of the parent SetUniqueList
returns false
# Modifications of the sublist may result in changes outside the range of the sublist. For
example adding an element which is not in the sublist but somewhere in the backing list should
result in *moving* the item from its current position to the new position defined by the subset.
This move may corrupt the internal range offsets of the sublist. 

The first issue seems easy to solve, for example by holding a reference of the parent set
in the subset. But if another subset is created based on the first subset, we have to maintain
a collections of parent sets.

The second issue is similar to a direct modification of a backing list - which is not supported.
The javadoc of sublist states
{quote}
The semantics of the list returned by this method become undefined if the backing list (i.e.,
this list) is structurally modified in any way other than via the returned list. (Structural
modifications are those that change the size of this list, or otherwise perturb it in such
a fashion that iterations in progress may yield incorrect results.)
{quote}

To solve this problem, the subList implementation has to track all modifications of the backing
list and adjust it's internal range offsets accordingly. For example adding a duplicate item
to a sublist, which exists  'in front' of the sublist will result 
- moving the item to the new sublist position 
- decrement the range offsets of the sublist. 

So first of all I wrote a short javadoc comment for the sublist method:
{code}
    /**
     * Returns a view of the portion of this list between the specified 
     * fromIndex, inclusive, and toIndex, exclusive.
     * <p>
     * <i>(Violation)</i> According to the <code>List</code> interface
the returned
     * sublist has to be backed by the original list. Because a <code>SetUniqueList</code>
     * requires both a defined ordering of the list items <i>and</i> uniqueness
of
     * all list items, modifications cannot garantee consistant behavior of both
     * the backing list and the sub list. It is strongly recommended not to modify
     * the sublist. 
     * <p>
     * 
     * @param fromIndex
     * @param toIndex
     * @return 
     */

{code}

Should we perhaps return the sublist as a UnmodifiableList?




                  
> Modifications of a SetUniqueList.subList() invalidate the parent list
> ---------------------------------------------------------------------
>
>                 Key: COLLECTIONS-310
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-310
>             Project: Commons Collections
>          Issue Type: Bug
>          Components: List
>    Affects Versions: 3.2, Nightly Builds
>            Reporter: Christian Semrau
>            Priority: Minor
>             Fix For: 4.0
>
>
> The List returned by SetUniqueList.subList() is again a SetUniqueList. The contract for
List.subList() says that the returned list supports all the operations of the parent list,
and it is backed by the parent list.
> We have a SetUniqueList uniqueList equal to {"Hello", "World"}. We get a subList containing
the last element. Now we add the element "Hello", contained in the uniqueList but not in the
subList, to the subList.
> What should happen?
> Should the subList behave like a SetUniqueList and add the element - meaning that it
changes position in the uniqueList because at the old place it gets removed, so now uniqueList
equals {"World", "Hello"} (which fails)?
> Or should the element not be added, because it is already contained in the parent list,
thereby violating the SetUniqueList-ness of the subList (which fails)?
> I prefer the former behaviour, because modifications should only be made through the
subList and not through the parent list (as explained in List.subList()).
> What should happen if we replace (using set) the subList element "World" with "Hello"
instead of adding an element?
> The subList should contain only "Hello", and for the parent list, the old element 0 (now
a duplicate of the just set element 1) should be removed (which fails).
> And of course the parent list should know what happens to it (specifically, its uniqueness
Set) (which fails in the current snapshot).
> 	public void testSubListAddNew() {
> 		List uniqueList = SetUniqueList.decorate(new ArrayList());
> 		uniqueList.add("Hello");
> 		uniqueList.add("World");
> 		List subList = uniqueList.subList(1, 2);
> 		subList.add("Goodbye");
> 		List expectedSubList = Arrays.asList(new Object[] { "World", "Goodbye" });
> 		List expectedParentList = Arrays.asList(new Object[] { "Hello", "World", "Goodbye"
});
> 		assertEquals(expectedSubList, subList);
> 		assertEquals(expectedParentList, uniqueList);
> 		assertTrue(uniqueList.contains("Goodbye")); // fails
> 	}
> 	public void testSubListAddDuplicate() {
> 		List uniqueList = SetUniqueList.decorate(new ArrayList());
> 		uniqueList.add("Hello");
> 		uniqueList.add("World");
> 		List subList = uniqueList.subList(1, 2);
> 		subList.add("Hello");
> 		List expectedSubList = Arrays.asList(new Object[] { "World", "Hello" });
> 		List expectedParentList = Arrays.asList(new Object[] { "World", "Hello" });
> 		assertEquals(expectedSubList, subList);
> 		assertEquals(expectedParentList, uniqueList); // fails
> 	}
> 	public void testSubListSetDuplicate() {
> 		List uniqueList = SetUniqueList.decorate(new ArrayList());
> 		uniqueList.add("Hello");
> 		uniqueList.add("World");
> 		List subList = uniqueList.subList(1, 2);
> 		subList.set(0, "Hello");
> 		List expectedSubList = Arrays.asList(new Object[] { "Hello" });
> 		List expectedParentList = Arrays.asList(new Object[] { "Hello" });
> 		assertEquals(expectedSubList, subList);
> 		assertEquals(expectedParentList, uniqueList); // fails
> 	}

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira

Mime
View raw message