self contained item in array causes stack overflow

[Christian Marrocco]

[Bug now tracked at https://github.com/nunit/nunit-framework/issues/52]

using System.Collections;
using System.Collections.Generic;
using NUnit.Framework;

[TestFixture]
public class Reproduction {
 class SelfContainer : IEnumerable { public IEnumerator GetEnumerator() { yield return this; } }

 [Test]
 public void SelfContainedItemFoundInArray() {
  var item = new SelfContainer();
  var items = new SelfContainer[] { new SelfContainer(), item };

  // work around
  Assert.True(((ICollection<SelfContainer>)items).Contains(item));

  // causes StackOverflowException
  Assert.Contains(item, items);
 }
}

Reproduced in NUnit 2.6.1

See also bug #491300

[Simone Busoli (simone.busoli)]

The problem with the code above is not really in the comparison between the two references to item (the variable and the element in the array) but rather with the non-failing comparison between item and the new instance of SelfContainer in position 0 in the array, which causes the stack overflow. That is quite easy to fix, but while working on it and writing some tests I encountered an interesting scenario:

            object[] array1 = new object[2];
            array1[0] = 1;
            array1[1] = array1;

            object[] array2 = new object[2];
            array2[0] = 1;
            array2[1] = array2;

Should array1 and array2 be considered equal?

The first element is definitely equal, it's 1. What about the second element of each of them? They are self references to the arrays, which in turn contain 1 at the first element and another self reference, and so on forever.

We can implement it either way, but I'm not sure what is the "correct" one.

[Simone Busoli (simone.busoli)]

One additional observation: if you think the two arrays in the previous comment should be considered equal, how do you think these two should be handled instead?

            object[] array1 = new object[2];
            array1[0] = array1;
            array1[1] = 1;

            object[] array2 = new object[2];
            array2[0] = array2;
            array2[1] = 1;

These are the same arrays as above, just with the elements in the reverse order.

And what about these two?

            object[] array1 = new object[2];
            object[] array2 = new object[2];

            array1[0] = 1;
            array1[1] = array2;

            array2[0] = 1;
            array2[1] = array1;

[Charlie Poole (charlie.poole)]

It's clear that the stack overflow is bad and should be fixed.

Simone's comments introduce another issue around equality testing between two arrays or collections, which are potentially nested. One way to handle all three examples is to detect the recursion and return an error result. Note this is not the same as a Failure, since both
   Assert.That(array1, Is.EqualTo(array2));
and
   Assert.That(array1, Is.Not.EqualTo(array2));
would return errors - neither of them could succeed.

OTOH, if we think that actually making the comparison is reasonable, I think they should all pass. But implementation is a bit of an issue. We would need to keep track of all comparisons made so far, as a list of pairs of object references. This adds overhead that is generally not needed.

Personally, I'd rather not allow comparison of recursive arrays (and structures) at all, unless somebody can come up with a real-world example that requires it. If we had to do it, then I would want the user to mark all assertions that are potentially recursive to avoid the overhead, for example:
  Assert.That(array1, Is.EqualTo(array2).Recursive);

Charlie

[Simone Busoli (simone.busoli)]

I think your suggestion to return an error is reasonable, but I guess it's not what the OP expected as a result. The .Recursive specifier makes for a good compromise though.

[Christian Marrocco (gfaett)]

Thanks for your investigations.

Whatever you decide about equality testing, this bug indicates that you need to think about the consequences this has to other assertions like Contains.

BTW, does this bug really address equality testing? The documentation introduces Assert.Contains as identity assertion, not equality assertion. Perhaps NUnit is testing equality within the Contains assertion where it should test for identity.

[Simone Busoli (simone.busoli)]

Hello Christian, let me expand. There's one single way of comparing objects in NUnit, let's call it NUnit equality.
The qay it works is this: If the identity of the two objects being compared is the same (Object.ReferenceEquals) then the objects are equal, otherwise other mechanisms for comparing them take place.
With this I mean that what Contains does is check each element of the collection for NUnit equality with the expected item.

Are you suggesting that Contains should check only identity equality?

[Christian Marrocco (gfaett)]

Hello Simone

As I wrote, I'm trying to infer the correct behavior of Contains from the current documentation.
As Contains is now documented as identity assertion, yes, I expect it should check identity equality.

I guess that if it was implemented like this, this bug would disappear.

Whether Contains does identity or equality checking is a design decision. Apparently, equality checking is more difficult to do.

The implementation now seems to perform equality checking, where the documentation indicates it should do identity checking. If the final resolution was to stick with equality checking, I'd expect Contains to be documented in the equality asserts section, no longer in the identity asserts section.

Checking for identity is easier to implement. But doing so is a breaking change. So I cannot give a final suggestion.

[Simone Busoli (simone.busoli)]

Hi Christian, that's right, I didn't spot that the docs say that Contains would check for identity equality.
Complying to that now would indeed be a breaking change though.

[Charlie Poole (charlie.poole)]

The deviation from docs arose a long time back and it would indeed be
a breaking
change to modify the behavior now. The test for Contains is definitely
equality now,
so much so that you can provide your own comparer!

However, I wouldn't hesitate to provide a separate constraint that uses equality
and (possibly) modify the behavior for NUnit 3.0, using different syntax for
identity and equality.

Charlie

On Wed, Sep 19, 2012 at 2:45 AM, Simone Busoli
<email address hidden> wrote:
> Hi Christian, that's right, I didn't spot that the docs say that Contains would check for identity equality.
> Complying to that now would indeed be a breaking change though.
>
> --
> You received this bug notification because you are subscribed to NUnit
> Extended Testing Platform.
> https://bugs.launchpad.net/bugs/1051847
>
> Title:
> self contained item in array causes stack overflow
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/nunitv2/+bug/1051847/+subscriptions

[Simone Busoli (simone.busoli)]

I've done a simple implementation which allows for the usage specified by the OP and in general considers enumerables which introduce recursion as not equal.

Not sure it is really worth to add real support for recursive enumerables and for explicity identity comparison in Contains constraint, maybe the second is more desirable than the first though.

[Charlie Poole (charlie.poole)]

Sounds cool. If you don't want to do a separate branch just send me
the files you changed.

Charlie

On Wed, Sep 19, 2012 at 1:53 PM, Simone Busoli
<email address hidden> wrote:
> I've done a simple implementation which allows for the usage specified
> by the OP and in general considers enumerables which introduce recursion
> as not equal.
>
> Not sure it is really worth to add real support for recursive
> enumerables and for explicity identity comparison in Contains
> constraint, maybe the second is more desirable than the first though.
>
> --
> You received this bug notification because you are subscribed to NUnit
> Extended Testing Platform.
> https://bugs.launchpad.net/bugs/1051847
>
> Title:
> self contained item in array causes stack overflow
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/nunitv2/+bug/1051847/+subscriptions

[Charlie Poole (charlie.poole)]

Never mind... I see you did a branch.

Charlie

On Wed, Sep 19, 2012 at 3:13 PM, Charlie Poole <email address hidden> wrote:
> Sounds cool. If you don't want to do a separate branch just send me
> the files you changed.
>
> Charlie
>
> On Wed, Sep 19, 2012 at 1:53 PM, Simone Busoli
> <email address hidden> wrote:
>> I've done a simple implementation which allows for the usage specified
>> by the OP and in general considers enumerables which introduce recursion
>> as not equal.
>>
>> Not sure it is really worth to add real support for recursive
>> enumerables and for explicity identity comparison in Contains
>> constraint, maybe the second is more desirable than the first though.
>>
>> --
>> You received this bug notification because you are subscribed to NUnit
>> Extended Testing Platform.
>> https://bugs.launchpad.net/bugs/1051847
>>
>> Title:
>> self contained item in array causes stack overflow
>>
>> To manage notifications about this bug go to:
>> https://bugs.launchpad.net/nunitv2/+bug/1051847/+subscriptions

[Simone Busoli (simone.busoli)]

Yep, sorry!
On Sep 20, 2012 12:20 AM, "Charlie Poole" <email address hidden> wrote:

> Never mind... I see you did a branch.
>
> Charlie
>
> On Wed, Sep 19, 2012 at 3:13 PM, Charlie Poole <email address hidden> wrote:
> > Sounds cool. If you don't want to do a separate branch just send me
> > the files you changed.
> >
> > Charlie
> >
> > On Wed, Sep 19, 2012 at 1:53 PM, Simone Busoli
> > <email address hidden> wrote:
> >> I've done a simple implementation which allows for the usage specified
> >> by the OP and in general considers enumerables which introduce recursion
> >> as not equal.
> >>
> >> Not sure it is really worth to add real support for recursive
> >> enumerables and for explicity identity comparison in Contains
> >> constraint, maybe the second is more desirable than the first though.
> >>
> >> --
> >> You received this bug notification because you are subscribed to NUnit
> >> Extended Testing Platform.
> >> https://bugs.launchpad.net/bugs/1051847
> >>
> >> Title:
> >> self contained item in array causes stack overflow
> >>
> >> To manage notifications about this bug go to:
> >> https://bugs.launchpad.net/nunitv2/+bug/1051847/+subscriptions
>
> --
> You received this bug notification because you are a bug assignee.
> https://bugs.launchpad.net/bugs/1051847
>
> Title:
> self contained item in array causes stack overflow
>
> Status in NUnit V2 Test Framework:
> Confirmed
>
> Bug description:
> using System.Collections;
> using System.Collections.Generic;
> using NUnit.Framework;
>
> [TestFixture]
> public class Reproduction {
> class SelfContainer : IEnumerable { public IEnumerator
> GetEnumerator() { yield return this; } }
>
> [Test]
> public void SelfContainedItemFoundInArray() {
> var item = new SelfContainer();
> var items = new SelfContainer[] { new SelfContainer(),
> item };
>
> // work around
>
> Assert.True(((ICollection<SelfContainer>)items).Contains(item));
>
> // causes StackOverflowException
> Assert.Contains(item, items);
> }
> }
>
> Reproduced in NUnit 2.6.1
>
> See also bug #491300
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/nunitv2/+bug/1051847/+subscriptions
>

[Charlie Poole (charlie.poole)]

Bug was fixed and merged for NUnit V2. Needs to be ported to V3.