Reflection on Visitor Pattern in Typescript
Tags: typescript, webdev, designpatterns, javascript
Published: 2023-01-26 10:34:51

# Visitor Pattern

Visitor pattern is one of the twenty-three well-known *[Gang of Four design patterns](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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:

```tsx
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:

```tsx
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:

```tsx
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:

```tsx
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 

```tsx
  // 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:

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

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

```tsx
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:

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

You will get the error below:

```bash
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:

```tsx

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:

```tsx
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 
    
    ```tsx
      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:
    
    ```tsx
    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:

```tsx
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:

```tsx
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:

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

 you will end up getting the error at runtime: 

```tsx
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:

```bash
npm i reflect-metadata --save
```

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

```json
{
  "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.  

```tsx
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:

```tsx
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:

```tsx
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:

```tsx
  @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](https://zenstack.dev/?utm_campaign=devto&utm_medium=organic&utm_content=visitor): a toolkit that supercharges Prisma with a powerful access control layer and unleashes its full potential for full-stack development