Reflection on Visitor Pattern in Typescript

Visitor Pattern

Visitor pattern is one of the twenty-three well-known Gang of Four design patterns:

Represent[ing] an operation to be performed on elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

The Visitor pattern is a natural fit for working with AST (Abstract Syntax Tree) data structures. For instance, if you've ever used Babel, you probably know that the @babel/traverse library utilizes a visitor pattern to enable you to traverse various nodes generated by @babel/parser quickly.

The pattern is typically built on the principle of double dispatch for OOP languages like Java or C#.

Although Typescript is attempting to bring OOP to the Javascript world, it's still constrained by the characteristics of Javascript. This makes the visitor pattern less elegant to some extent. But don't worry, I'll show you how to overcome these limitations and harness the true potential of the visitor pattern in Typescript.

Real-World Example

Let’s assume we were back at the time when HTML1.0 had just been released, and we were building a browser for it.

AST

Let’s say we only have 3 tags supported at the beginning so that the AST would look like the below:

interface HTMLElement {
  tagName: string;
}

class PElement implements HTMLElement {
  tagName: string = "p";
}

class AElement implements HTMLElement {
  tagName: string = "a";
}

class BodyElement implements HTMLElement {
  tagName: string = "body";

  children: HTMLElement[] = [];
}

Visitor Interface

The below interfaces are the core part of the visitor pattern:

interface IVisitable {
  accept(visitor: Visitor): void;
}

interface IVisitor {
  visit(element: PElement): void;
  visit(element: AElement): void;
  visit(element: BodyElement): void;
}

And we need to make sure all the HTMLElement implement IVisitable, so let’s make some changes to our AST:

abstract class AbstractHtmlElement implements HTMLElement, IVisitable {
  public abstract tagName: string;

  // double dispatch pattern
  public accept(visitor: IVisitor): void {
    visitor.visit(this);
  }
}

class PElement extends AbstractHtmlElement {
  tagName: string = "p";
}

class AElement extends AbstractHtmlElement {
  tagName: string = "a";
}

class BodyElement extends AbstractHtmlElement {
  tagName: string = "body";

  children: AbstractHtmlElement[] = [];
}

Concrete Visitor

So a real render implementation would be like the below:

class Render implements IVisitor {
  visit(element: PElement) {
    console.log("Render P");
  }
  visit(element: AElement) {
    console.log("Render A");
  }
  visit(element: BodyElement) {
    console.log("Render Body");
    element.children.forEach((child) => {
      child.accept(this);
    });
  }
}

and the client that actually runs it would be simple

  // Create a visitor
  const visitor: IVisitor = new Render();

  // Create an AST
  const body = new BodyElement();
  body.children.push(new AElement());
  body.children.push(new PElement());

  // Visit the node
  body.accept(visitor);

Extensibility

One of the great things about using Visitor pattern is how easy to add a new visitable element. Let’s say the new tag Table was added to the HTML2.0, let’s see what we need to do to support it.

Of course, the first thing to do is to define it in AST like below:

class TableElement extends AbstractHtmlElement {
  tagName: string = "table";
}

The next thing is to add the visit interface and implementation for the new element:

interface IVisitor {
  ...
  visit(element: TableElement): void;
}

class Render implements IVisitor {
  ...
  visit(element: TableElement) {
    console.log("Render Table");
  }
}

That’s all. See, the beauty here is that we only added the code exactly for the new element without touching the existing code at all.

Problem

It looks perfect, except it works for Java or C# but not for Typescript. Why? because the Render code won’t compile:

class Render implements IVisitor {
  visit(element: PElement) {
    console.log("Render P");
  }
  visit(element: AElement) {
    console.log("Render A");
  }
}

You will get the error below:

Duplicate function implementation.ts(2393)

That’s the limitation caused by the dynamic type system of Javascript, so the function name has to be unique regardless of the parameters.

There is an interesting part here that in interface IVisitor, it doesn’t have this restriction, I will leave it to you to think about why is that. 🤔

So to make it work, we have to make the visit function name unique for individual element types:

interface IVisitor {
  visitP(element: PElement): void;
  visitA(element: AElement): void;
  visitBody(element: BodyElement): void;
  visitTable(element: TableElement): void;
}

Because of this, the accept function can’t be implemented in the base class anymore. Instead, it has to be implemented in every type of HtmlElement like below:

abstract class AbstractHtmlElement implements HTMLElement, IVisitable {
  public abstract tagName: string;
  public abstract accept(visitor: IVisitor): void;
}

class PElement extends AbstractHtmlElement {
  public accept(visitor: IVisitor) {
    visitor.visitP(this);
  }
  tagName: string = "p";
}

class AElement extends AbstractHtmlElement {
  public accept(visitor: IVisitor) {
    visitor.visitA(this);
  }
  tagName: string = "a";
}

class BodyElement extends AbstractHtmlElement {
  public accept(visitor: IVisitor) {
    visitor.visitBody(this);
  }
  tagName: string = "body";

  children: AbstractHtmlElement[] = [];
}

There are three disadvantages then:

1. For every new tag added, like the Table, it has to be aware of the visitor pattern and implement the accept method for it.

2. The accept method has almost the same implementation as
   

     public accept(visitor: IVisitor) {
       visitor.visitA(this);
     }
   

3. Because Typescript is structural Typing, so you might accidentally write the below wrong code and pass the type checking if the two HTMLElement types are structurally equal:
   

   class PElement extends AbstractHtmlElement {
     public accept(visitor: IVisitor) {
       //Bug: it should call visitP instead 
       visitor.visitA(this);
     }
     tagName: string = "p";
   }
   

So is there a way that we don’t need to care about accept function?

Reflection

Reflection of Javascript

Since the unique function name is a hard restriction from language, there seems no way to let the compiler dispatch to the correct function for us, so we have to do that on our own. So simply put: we need to call the correct function based on the type of the input parameter.

Sounds doable in Javascript, right? Since we can get the class name of the parameter using constructor property, it’s easy to implement the logic in the Visit function below:

class Render implements IVisitor {
  visit(element: AbstractHtmlElement) {
    const typeName = element.constructor.name;
    const methodName = `visit${typeName}`;
    // @ts-ignore
    this[methodName].call(this, element);
  }

  visitPElement(element: PElement) {
    console.log("Render P");
  }
  visitAElement(element: AElement) {
    console.log("Render A");
  }
  visitBodyElement(element: BodyElement) {
    console.log("Render Body");
    element.children.forEach((child) => {
      this.visit(child);
    });
  }
}

If you're familiar with the Javascript world, this type of work may seem intuitive to you. In the realm of static type languages like Java or C#, it's known as Reflection.

Then we could get rid of accept totally and always go with the new visit function like below:

const visitor = new Render();
const body = new BodyElement();
body.children.push(new AElement());
body.children.push(new PElement());
// Visit the node
visitor.visit(body);

Pitfall

Although it looks like the original goal has been achieved, there is a big pitfall. Have you noticed the ts-ignore in the implementation? that’s it. Now we have an implied limitation that the name of the function has to be visit${typeName}. It means that if you accidentally write a different name like:

  // with an extra 's' at the end  
  visitPElements(element: PElement) {
    console.log("Render P");
  }

you will end up getting the error at runtime:

TypeError: Cannot read properties of undefined (reading 'call')

We went back to the unsafe Javascript world as we actively turned off the safety guard the TS compiler gives. So is there any way to achieve that in the Typescript world?

Reflection of Typescript

Although the type is fully erased after being compiled into Javascript, TypeScript includes experimental support for emitting certain types of metadata for declarations that have decorators. And we can use the reflection API provided by reflect-metadata library to retrieve the metadata at runtime.

Enable Metadata Reflection

To use it we need first to install this library via npm:

npm i reflect-metadata --save

Then set the compiler option in tsconfig.json as below:

{
  "compilerOptions": {
    "target": "ES5",
    "experimentalDecorators": true,
    "emitDecoratorMetadata": true
  }
}

Dispatcher Decorator

Let’s first define the Dispatcher map, the key is the type of HTMLElement, and the value is the corresponding visitor function.

const renderDispatcherMap = new Map<any, (element: HTMLElement) => void();

You can see that as long as the map is filled with the correct value, we can use it to replace the unsafe [function.call](http://function.call) like below:

visit(element: HTMLElement) {
    const method = renderDispatcherMap.get(element.constructor);
    if (method) {
      method.call(this, element);
    } else {
      throw new Error("No method found for " + element.constructor.name);
    }
}

Next, we need to do is to fill the map programmatically. That can be done by using the method decorator defined below:

function HtmlElementDispatcher() {
  return function (target: any, propertyKey: string, descriptor: PropertyDescriptor) {
    const htmlElementType = Reflect.getMetadata("design:paramtypes", target, propertyKey)[0];
    const originalMethod = descriptor.value;
    if (!renderDispatcherMap.has(htmlElementType)) {
      renderDispatcherMap.set(htmlElementType, originalMethod);
    }
    return descriptor;
  };
}

The last thing we need to do is to make sure to put the HtmlElementDispatcher decorator on every visit function, and no need to worry about the function name any more:

  @HtmlElementDispatcher()
  visitPElement(element: PElement) {
    console.log("Render P");
  }
  @HtmlElementDispatcher()
  visitAElement(element: AElement) {
    console.log("Render A");
  }
  @HtmlElementDispatcher()
  visitBodyElement(element: BodyElement) {
    console.log("Render Body");
    element.children.forEach((child) => {
      this.visit(child);
    });
  }

Conclusion

Everything comes with a price. The benefit of decoupling the visitor and element in this manner is that we don't have to worry about the accept method anymore. However, there is a downside to this approach as well. The visitor might not be updated when a new type of element is added to the object structure or if the HtmlElementDispatcher is carelessly overlooked.

So do you think it’s worthwhile? 😁

---

P.S. We're building ZenStack: a toolkit that supercharges Prisma with a powerful access control layer and unleashes its full potential for full-stack development

Comments

[Khoa Huỳnh]

Most viable double dispatch approach I've seen so far.
Thank you very much