Creating recursive tree with AutoFixture

Question

I have just started using AutoFixture and have this semi-complex data structure that I would like to create some specimen for. In the tests I am working with I don't care too much about content of the data structure. I just want reasonable default values.

Part of this data structure is a recursive tree. More specific, one class holds a collection of some other class that contains a list of children of itself. Something akin to:

public class A
{
   private IEnumerable<B> bNodes;
   public A(IEnumerable<B> bNodes)
   {
      this.bNodes = bNodes;
   }
}

public class B
{
   private IEnumerable<B> children;
   public B(IEnumerable<B> children)
   {
      this.children = children;
   }
}

Lets assume I cannot easily change this structure for various reasons.

If I ask my fixture to create A ThrowingRecursionBehavior will start barking about B being recursive.

If I replace ThrowingRecursionBehavior with OmitOnRecursionBehavior I get an ObjectCreateException.

If I try something like: fixture.Inject(Enumerable.Empty()); I get "An item with the same key has already been added" from the DictionaryFiller. The same thing happens if I replace ThrowingRecursionBehavior with NullRecursionBehavior.

There are several things I would like to.

• What would be the best way to create a specimen of A with an empty list of Bs?
• What would be the best way to create a specimen of A with a few Bs containing a few B-children with a few children (a small tree)?

For my last wish it could be nice to specify some recursion depth after which Enumerable.Empty was used (or a zero sized array / List or even null). I know that AutoFixture is very flexible to extend. So I suppose it should be possible to create some specimen builder that does exactly this. In fact I will try fooling around with a custom ISpecimenBuilder, but perhaps someone has a smarter solution already. For example, would it make sense to modify this line in RecursionGuard:

public object Create(object request, ISpecimenContext context)
{
   if (this.monitoredRequests.Any(x => this.comparer.Equals(x, request)))
   ...

to

public object Create(object request, ISpecimenContext context)
{
   if (this.monitoredRequests.Count(x => this.comparer.Equals(x, request)) > maxAllowedRecursions)
   ...

Swerve

For all the ones still interested in the same problem, see here: github.com/AutoFixture/AutoFixture/wiki/… – Elute

Answer 1

Creating A with an empty list of Bs

It's easy to create an instance of A with an empty list of Bs:

var fixture = new Fixture();
fixture.Inject(Enumerable.Empty<B>());

var a = fixture.Create<A>();

Creating a small tree

It's much more difficult to create a small tree, but it's possible. You're already on track with your thinking about RecursionGuard. In order to verify if this could work, I copied most of the code from RecursionGuard and created this DepthRecursionGuard as a proof of concept:

public class DepthRecursionGuard : ISpecimenBuilderNode
{
    private readonly ISpecimenBuilder builder;
    private readonly Stack<object> monitoredRequests;

    public DepthRecursionGuard(ISpecimenBuilder builder)
    {
        if (builder == null)
        {
            throw new ArgumentNullException("builder");
        }

        this.monitoredRequests = new Stack<object>();
        this.builder = builder;
    }

    public object Create(object request, ISpecimenContext context)
    {
        if (this.monitoredRequests.Count(request.Equals) > 1)
            return this.HandleRecursiveRequest(request);

        this.monitoredRequests.Push(request);
        var specimen = this.builder.Create(request, context);
        this.monitoredRequests.Pop();
        return specimen;
    }

    private object HandleRecursiveRequest(object request)
    {
        if (typeof(IEnumerable<B>).Equals(request))
            return Enumerable.Empty<B>();

        throw new InvalidOperationException("boo hiss!");
    }

    public ISpecimenBuilderNode Compose(IEnumerable<ISpecimenBuilder> builders)
    {
        var builder = ComposeIfMultiple(builders);
        return new DepthRecursionGuard(builder);
    }

    public virtual IEnumerator<ISpecimenBuilder> GetEnumerator()
    {
        yield return this.builder;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private static ISpecimenBuilder ComposeIfMultiple(
        IEnumerable<ISpecimenBuilder> builders)
    {
        var isSingle = builders.Take(2).Count() == 1;
        if (isSingle)
            return builders.Single();

        return new CompositeSpecimenBuilder(builders);
    }
}

Notice the changed implementation of the Create method, as well as the specific handling of IEnumerable<B> in HandleRecursiveRequest.

In order to make this usable from a Fixture instance, I also added this DepthRecursionBehavior:

public class DepthRecursionBehavior : ISpecimenBuilderTransformation
{
    public ISpecimenBuilder Transform(ISpecimenBuilder builder)
    {
        return new DepthRecursionGuard(builder);
    }
}

This enabled me to create a small tree:

var fixture = new Fixture();
fixture.Behaviors.OfType<ThrowingRecursionBehavior>()
    .ToList().ForEach(b => fixture.Behaviors.Remove(b));
fixture.Behaviors.Add(new DepthRecursionBehavior());

var a = fixture.Create<A>();

While this is possible, it's, in my opinion, too hard, so I've created a work item to make it easier in the future.

---

Update 2013.11.13: From AutoFixture 3.13.0, the recursion depth can be configured via that API.

Pochard

Interestingly fixture.Inject(Enumerable.Empty<B>()) works, but doing the same thing in my real world code makes DictionaryFiller fail with "An item with the same key has already been added". – Swerve

Not quite obvious to me how to control the recursion depth, could you supply an example... – Bartlet

As always, very easy when you first figure it out... fixture.Behaviors.Remove(new ThrowingRecursionBehavior()); fixture.Behaviors.Add(new OmitOnRecursionBehavior(1)); //Recursion of 1 – Bartlet

That looks about right, although I'd remove the existing behaviour with fixture.Behaviors.OfType<ThrowingRecursionBehavior>().ToList().ForEach(b => fixture.Behaviors.Remove(b));... – Pochard

DepthRecursionBehavior doesn't exist. Do you mean the OmitOnRecursionBehavior? – Phonsa

@Phonsa DepthRecursionBehavior is the name of the proof-of-concept implementation here. Are you asking about the API in the released version? If so, what are you asking about that @smolesen's comment from 2014 doesn't answer? – Pochard

@MarkSeemann yes, Mark, I'm asking about the name in the current version :) I think DepthRecursionBehavior is now OmitOnRecursionBehavior. Isn't it? Thank you! – Phonsa

@MarkSeemann OmitOnRecursionBehavior does not seem to work with the customization for LazyEntityGraph, but seems like it should. – Lyns

@SubjectiveReality File an issue if you think this is a defect. – Pochard

I have tried NullRecursionBehavior for list structures, and I really can't get it to work properly. With list structures I mean class Node { public Node(Node child) { ... } }. Is it not possible to use behaviors on constructor parameters? (I can see the "black hole" recursion, almost like left recursion in a recursive descent parser, but if someone can stop black holes it's you @MarkSeemann :D). – Nyctaginaceous

@JörgenSigvardsson I've been away from AutoFixture for years, now, and I don't recall. You may have more luck if you ask a new question. – Pochard