Visitor that changes the structure of the objects it visits

Question

Brief summary:

The vanilla GoF visitor is great for altering items within a tree of elements, but when the visitor visits an element it can only change the children of that element not the element itself. For example, a visitor altering the DOM of a webpage could search for everything that contains an image and replace it with an ascii art version of that image. However, <dim>s can contains images, <table>s can contain images, paragraphs (<p>) can contain images. When the visitor is visiting the node for <image> tag itself it cannot change the type of the image node, though you could change the content of the image node - this is just how visitors work. Instead you would have to find everything that could conceivably contain an image and then visit that - and on top of that anytime W3C added another item that could contain an image you would have to update your visitor.

This isn't a perfect example - there a lots of tools for altering webpage DOMs - but hopefully it is an intuitive one.

Sorry - there is a wall of text in the more complete description below. I'm trying to walk the line between brevity and fully explaining everything, but it looks like this post same out quite wordy.

What I have:

I have a class hierarchy that can be represented by the simplified classes below:

Element is the abstract base class for all visitable classes, and has an Accept method.

LeafElementA and LeafElementB are concretes that are extremely simple. They don't do anything, but just represent that there can be different types of leaves.

MultiCompositeElement and BinaryCompositeElement are also concretes that can contain other Elements - either a collection, or a Left and Right (respectively). The Accept method overrides handle recursing to the contained Elements.

I also have some Visitors that visit each of the Elements. All vanilla GoF visitor so far...

(I'm not looking for feedback on this class hierarchy, I'm just setting the scene with a simplified version of the real classes that I am working with).

What I want:

I would like to use a visitor to alter the structure of the Element tree. For example, in this toy example I might want to append a LeafElementA to each composite element, and if the composite element is a BinaryCompositeElement to convert it to a MultiCompositeElement before (and also recursively visit all the children of each composite element too...).

The vanilla visitor does not cope with this well. When you visit an Element you can alter the content of that Element but not return a completely different Element.

I could check the children of each MultiCompositeElement and BinaryCompositeElement as I visit them to see if any of the children need to be transformed from a BinaryCompositeElement to a MultiCompositeElement. However, this would violate the DRY principle as the check would have to be in both visit methods. This would be compounded by the fact that in the 'real' implementation there are many composite type elements - not just 2.

Finally the code:

DotNetFiddle (sorry for the terrible ToString implementation on this one) or download csproj/zip from dropbox (no terrible ToString, just put a breakpoint in the the end of the main method).

I have left out some "clutter" bits of code from the snippets below. There is no error checking or null checking.

Base classes (I've not included IVisitor as it would also increase clutter. All of the methods on VisitorBase are on IVisitor):

// Element base class
public abstract class Element   {
  // I am returning an Element here (different from a "normal" GoF implementation)
  internal abstract Element Accept(IVisitor visitor);
}

// Visitor base class
public abstract class VisitorBase: IVisitor
{
  // Again, return an Element 
  // This is so that each visitor can choose to return a different type  
  // than the visited Element
  public virtual Element Visit(Element element)
  {
    element = element.Accept(this);
    return element;
  }

  // Another departure from vanilla visitor: Visit just this element  
  // (and don't recurse)
  public virtual Element VisitNonRecursive(Element element)
  {
    return element;
  }

  // These can be individually overridden, and I have added these for transforming 
  // one type of Element into another
  public virtual Element VisitNonRecursive(LeafElementA leafElementA)
  {
    return VisitNonRecursive(leafElementA as Element);
  }

  public virtual Element VisitNonRecursive(LeafElementB leafElementB)
  {
    return VisitNonRecursive(leafElementB as Element);
  }

  // ...similar methods for the other elements (removed to reduce clutter in the snippet) 
}

Some concrete elements (I'm not including LeafElementB as it is virtually identical to LeafElementA):

public class LeafElementA : Element
{
  internal override Element Accept(IVisitor visitor)
  {
    return visitor.VisitNonRecursive(this);
  }
}

// Implementation of Element that contains multiple other Elements
public class CompositeElement : Element
{
  public CompositeElement(params Element[] containedElements)
  {
    ContainedElements = containedElements.ToList();
  }

  public ICollection<Element> ContainedElements { get; private set; } 

  internal override Element Accept(IVisitor visitor)
  {
    ContainedElements = ContainedElements
      // Recursively visit each child
      .Select(visitor.Visit)
      .ToList();

    // And non-recursively visit this
    return visitor.VisitNonRecursive(this);
  }
}

// Implementation of Element that contains exactly two other Elements
public class BinaryElement : Element
{
  public BinaryElement(Element left, Element right)
  {
    Left = left;
    Right = right;
  }

  public Element Left { get; private set; }

  public Element Right { get; private set; }

  internal override Element Accept(IVisitor visitor)
  {
    // Recursively visit the children
    Left = visitor.Visit(Left);
    Right = visitor.Visit(Right);

    // And non-recursively visit this
    return visitor.VisitNonRecursive(this);
  }
}

And the concrete visitor:

// Implementation of Visitor that adds a LeafElementA to any composite element
public class AddOneMoreVisitor : VisitorBase
{
  public override Element VisitNonRecursive(MultiCompositeElement multiCompositeElement)
  {
    multiCompositeElement.ContainedElements.Add(new LeafElementA());
    return multiCompositeElement;
  }

  public override Element VisitNonRecursive(BinaryCompositeElement binaryCompositeElement)
  {
    // Here we are able to change the returned type from the visitor
    var result = new MultiCompositeElement(
      binaryCompositeElement.Left,
      binaryCompositeElement.Right,
      new LeafElementA()
    );
    return result;
  }

  // The rest of the recursion-based visiting can be delegated to the base
}

So, did you actually have a question?

Yes, I did.

Firstly, is there a name for this variant of the visitor pattern? I assume that I will not be the first person in the whole world to think of or implement this. And I assume that with the collective wisdom of all those who have gone before that this class can be done better.

Secondly, if this is not the case, then is there a way I can do this better? Doubling up the visit methods seems wasteful, but I always get stack overflow exceptions when I try an implementation without it.

Thirdly, I am concerned about type safety. In the toy example all the composites contain base Elements. In the real-life code most Elements that contain another hold a derived type. Is there a way of making the visitor type safe so that no upcasting is needed? I couldn't find one - but that does not mean that it doesn't exists. And if not, is there a way to make it easier for a developer to write correct code. This looks like a powerful pattern and as Uncle Ben* said: "With great power comes great responsibility". If it is not possible to make it provably typesafe according to the compiler, then the code should not get in the way of writing correct code.

---

^{*The Spiderman uncle, not the rice uncle}

Answer 1

Review

Firstly, is there a name for this variant of the visitor pattern?

You have made what I like to call the inviting visitor pattern. I'm not sure this pattern is common, but I have seen it before, disguised and usually involves 3 (types of) classes instead of 2, each with their own concern.

• inviter: let visitee invite visitor
• visitee: let visitor accept me
• visitor: visit reference

As in contrast of the visitor pattern as we all know it:

• visitee: let visitor accept me
• visitor: visit visitee

Your visitor is also the (self-)inviter. This part is what I would rename if using the augmented visitor pattern. However, your problem is solvable with a regular visitor pattern.

 public virtual Element Visit(Element element)
 {
    element = element.Accept(this);
    return element;
 }

 public virtual Element Invite(Element element)
 {
    element = element.Accept(this);
    return element;
 }

---

Secondly, if this is not the case, then is there a way I can do this better? Doubling up the visit methods seems wasteful.

Since you never override Visit(Element element), I don't see its purpose. If you would have a situation where you could override, consider moving this functionality to another class. You shouldn't let the visitor decide both (A) how the reference can accept the visitor and (B) how to visit the reference, these are two different concerns.

---

Proposed Solution

Your situation allows for a regular visitor pattern.

Change the flow in the reference:

internal override Element Accept(IVisitor visitor)
{
    // Recursively visit the children
    Left = visitor.Visit(Left);
    Right = visitor.Visit(Right);

    // And non-recursively visit this
    return visitor.VisitNonRecursive(this);
}

internal override Element Accept(IVisitor visitor)
{
    Left = Left.Accept(visitor);
    Right = Right.Accept(visitor);

    return visitor.Visit(this);
}

Change the flow in the visitor and renameVisitNonRecursive to Visit.

public virtual Element Visit(Element element)
{
    element = element.Accept(this);
    return element;
}

public virtual Element Visit(Element element)
{
     if (element is LeafElementA) return Visit(element as LeafElementA);
     if (element is LeafElementB) return Visit(element as LeafElementB);
     // ..
     return element;
}

Answer 2

You can improve naming. Names like IVisitor are good to illustrate the pattern, but in production code I would rather have a name that tells me the purpose of the interface, not which pattern it represents. For example, this looks a lot better, IMHO:

internal abstract Element Transform(ITransformer transformer);

---

It looks like you assume that BinaryElement.Left and BinaryElement.Right are not null. Yet nothing stops me from executing this line of code:

new BinaryElement(null, null).Accept(...) 

You should validate constructor parameters to catch such mistakes early.

---

VisitorBase.Visit makes no sense. Why would Visit method call Accept internally? Shouldn't it be the other way around? Shouldn't Accept method call Visit instead? Those methods calling each other is the reason stack overflows. You can remove Visit method, and call Left.Accept(visitor) instead of visitor.Visit(Left). It will work just fine.

---

I think there are two main ways to implement visitor pattern.

• You either provide a method for every concrete implementation:

  interface IVisitor
  {
     //removed from interface
     //(you can still have this method as `protected virtual` in base implementation)
     //Element Visit(Element element);
  
     Element Visit(BinaryElement element);
     Element Visit(CompositeElement element);
     //etc...
  }
  

  Note, that there is no Visit method, that takes base Element, only concrete implementations are included. This gives you some sort of type safety at compilation time, making sure that you do not forget to modify your visitors as you add new elements. But it also bloats the interface as the number of elements grow.

• Or you keep your interface simple by only including base type:

  interface IVisitor
  {
     Element Visit(Element element);
  
     //removed from interface 
     //(you can still have those methods as `protected virtual` in base implementation)
     //Element Visit(BinaryElement element);
     //Element Visit(CompositeElement element);
  }
  

  This prevents visitor interface from bloating, but you lose type safety.

My point is that there is always some sort of trade-off, and one approach might be better than the other depending on use case. However, by combining those two approaches, as you do, you are likely to get the downsides of them both AND gain non of the benefits. So I suggest you pick one or the other, and stick to it.

---

AddOneMoreVisitor has inconsistent behavior. Sometimes it creates new elements, and sometimes it does not. This can produce all sorts of weird side effects associated with shallow cloning. Modifications that are done to transformed tree in some cases will affect the initial tree. To avoid that you will have to do deep cloning during transformation. However, if initial tree is always discarded after transformation, then it does not matter, I guess.