Type Traverser

An organized way to traverse objects using typescript.

Installation

npm i @ldo/type-traverser

Why use this library?

Have you ever needed to traverse large, complex objects? Chances are you built traversers to recognize when something is an array or a certain kind of record.

Building traversers is an arduous process that involves a lot of repeated concepts and repeated code. Type-Traverser minimizes the repetition.

Tutorial

This tutorial walks you through how to set up a traverser. You can see the full runnable example at example/example.ts, or you can run the example by running npm run start.

Defining the type

The first step is defining what your type looks like. Let's say, for example, the following typescript typings represent what you need to traverse. These types represent characters from Avatar: The Last Airbender where there are special people called "Benders" who can manipulate the elements.

type Element = "Water" | "Earth" | "Fire" | "Air";
interface Bender {
  name: string;
  element: Element;
  friends: Person[];
}
interface NonBender {
  name: string;
  friends: Person[];
}
type Person = Bender | NonBender;

Some sample data that follows this type looks like this:

const aang: Bender = {
  name: "Aang",
  element: "Air",
  friends: [],
};
const sokka: NonBender = {
  name: "Sokka",
  friends: [],
};
const katara: Bender = {
  name: "Katara",
  element: "Water",
  friends: [],
};
aang.friends.push(sokka, katara);
sokka.friends.push(aang, katara);
katara.friends.push(aang, sokka);

Defining Traverser Types

Next, we need to define a traverser. A traverser has data that defines what your object looks like.

To define a traverser, you first need to set up a TraverserTypes type. You can validate the TraverserTypes type by using the ValidateTraverserTypes type and passing in your TraverserTypes as a generic.

type AvatarTraverserTypes = ValidateTraverserTypes<{
  Element: {
    kind: "primitive";
    type: Element;
  };
  Bender: {
    kind: "interface";
    type: Bender;
    properties: {
      element: "Element";
      friends: "Person";
    };
  };
  NonBender: {
    kind: "interface";
    type: Bender;
    properties: {
      friends: "Person";
    };
  };
  Person: {
    kind: "union";
    type: Person;
    typeNames: "Bender" | "NonBender";
  };
}>;

Let's break down what's happening here. We're telling typescript the kinds of "Sub-Traversers" each type uses.

Each sub-traverser has a name called a "TypeName". In this example we have four TypeNames: Element, Bender, NonBender, and Person. TypeNames can be any name you want, but it's best practice to match your TypeNames to the name of it's corresponding type. For example, the type Element is associated with the TypeName Element. Some sub-traversers will also require you to provide TypeNames as strings.

ValidateTraverserTypes is convenient way to check if you have made a valid TraverserTypes. If you make a mistake - for example, you provide an invalid TypeName as seen below - the resulting type will be never;

At the moment, there are three sub-traverser types:

Union

You should use a union sub-traverser for typescript union types - types that usually follow the form a | b | c where any element from the list is valid.

In the example, Person is a "Union" sub-traverser because a Person is a union of Bender and NonBender (Bender | NonBender).

Person: {
  kind: "union";
  type: Person;
  typeNames: "Bender" | "NonBender";
};

There are three fields for the union sub-traverser:

• kind: Must be "union" to denote that this defines a union sub-traverser.
• type: The typescript type corresponding to this union.
• typeNames: Defines a list of TypeNames that correspond to the actual type.

Interface

You should use a interface sub-traverser for interface or object types - any type that maps discrete keys to values.

In the example, Bender is an "Interface" sub-traverser because a Bender type is a map of discrete keys (like element and friends) to type values (like Element and Person[]).

Bender: {
  kind: "interface";
  type: Bender;
  properties: {
    element: "Element";
    friends: "Person";
  };
};

There are three fields for the interface sub-traverser:

• kind: Must be "interface" to denote that this defines a interface sub-traverser.
• type: The typescript type corresponding to this inteface or object type.
• properties: Defines the properties that should be traversed by mapping the property name to its corresponding TypeName. Not all interface properties need to be listed here, only the ones that should be traversed. If no properties from this interface need to be traversed, you either provide properties: Record<string, never> or use a "Primitive" sub-traverser.

Primitive

You should use a primitive sub-traverser for "leaf-types" - types that do not have any children.

In the example, Element is a "Primitive" sub-traverser because an Element type is just a collection of strings ("Water" | "Earth" | "Fire" | "Air").

Element: {
  kind: "primitive";
  type: Element;
};

Note: while it is common to use a primitive sub traverser for primitive types like string, boolean, number, etc. you may also use it for more complex types like interfaces and arrays if you do not care about traversing the children of those types.

There are two fields for the primitive sub-traverser:

• kind: Must be "primitive" to denote that this defines a primitive sub-traverser.
• type: The typescript type corresponding to this primitive.

Creating a traverser definition

Typescript typings aren't available at runtime, so the next step is to translate the TraverserTypes that we made into a standard JSON object called a "TraverserDefinition". But, don't worry! This will be easy. If you define a variable as a TraverserDefinition<TraverserType>, your IDE's IntelliSense will be able to direct you through exactly what to fill out, as seen below.

In our example, the TraverserDefinition looks like:

const avatarTraverserDefinition: TraverserDefinition<AvatarTraverserTypes> = {
  Element: {
    kind: "primitive",
  },
  Bender: {
    kind: "interface",
    properties: {
      element: "Element",
      friends: "Person",
    },
  },
  NonBender: {
    kind: "interface",
    properties: {
      friends: "Person",
    },
  },
  Person: {
    kind: "union",
    selector: (item) => {
      return (item as Bender).element ? "Bender" : "NonBender";
    },
  },
};

Defining a Union Selector

The only part of the TraverserDefinition that isn't just blindly following IntelliSense is the selector on a Union sub-traverser. A selector is given the item and should return the TypeName corresponding to the item.

In the above example, "Bender" is returned if the given item has a "element" property because a "NonBender" does not include an "element" property.

Instantiating a Traverser

Now that we've defined the traverser types, we're ready to instantiate the traverser itself. A Traverser is a class that lets you traverse the object you defined.

In our example, this is how we instantiate the traverser

const avatarTraverser = new Traverser<AvatarTraverserTypes>(
  avatarTraverserDefinition
);

Using a Traverser

At this point I'd like to welcome everyone who was linked to this section from another library. If this is you, someone else has already defined a traverser for you. You don't need to know how to create a traverser, but if you want to know, you can read the proceeding sections in this document.

From now on, we will detail how to use an already defined traverser using sample data about the fictional universe of "Avatar: The Last Airbender." If you came here from another library, your traverser will be different, but the concepts are the same. So far we have the following:

type Element = "Water" | "Earth" | "Fire" | "Air";
interface Bender {
  name: string;
  element: Element;
  friends: Person[];
}
interface NonBender {
  name: string;
  friends: Person[];
}
type Person = Bender | NonBender;

Some sample data that follows this type looks like this:

/**
 * The Type Definitions 
 */ 
type Element = "Water" | "Earth" | "Fire" | "Air";
interface Bender {
  name: string;
  element: Element;
  friends: Person[];
}
interface NonBender {
  name: string;
  friends: Person[];
}
type Person = Bender | NonBender;

/**
 * Some Raw Sample Data that follows our Types
 */
const aang: Bender = {
  name: "Aang",
  element: "Air",
  friends: [],
};
const sokka: NonBender = {
  name: "Sokka",
  friends: [],
};
const katara: Bender = {
  name: "Katara",
  element: "Water",
  friends: [],
};
aang.friends.push(sokka, katara);
sokka.friends.push(aang, katara);
katara.friends.push(aang, sokka);

/**
 * A Traverser to Traverse these type definitions
 */
avatarTraverser

Using a Visitor

The simplest way to traverse your object is using a Visitor. A visitor will trigger a given function when it finds an object that matches the corresponding TypeName.

In our Avatar example, our visitor could look like:

const avatarVisitor = avatarTraverser.createVisitor<undefined>({
  Element: async (item) => {
    console.log(`Element: ${item}`);
  },
  Bender: {
    visitor: async (item) => {
      console.log(`Bender: ${item.name}`);
    },
    properties: {
      element: async (item) => {
        console.log(`Bender.element: ${item}`);
      },
    },
  },
  NonBender: {
    visitor: async (item) => {
      console.log(`NonBender: ${item.name}`);
    },
  },
  Person: async (item) => {
    console.log(`Person: ${item.name}`);
  },
});

await avatarVisitor.visit(aang, "Bender", undefined);

Running this code will result in this log:

Bender: Aang
Bender.element: Air
Element: Air
Person: Sokka
NonBender: Sokka
Person: Aang
Person: Katara
Bender: Katara
Bender.element: Water
Element: Water

Let's break down what's happening here.

"Primitive" and "Union" sub-traverser types (Like Element and Person respectively) require only a function. That function is crafted for the specific item. For example:

• Element's visitor function: (item: Element, context: undefined) => Promise<void>;
• Person's visitor function: (item: Person, context: undefined) => Promise<void>;

"Interface" sub-traversers allow you to define a visitor function for the whole object AND each of its properties. Each of these, including the visitor function for the whole object is optional. For example, an interface visitor for "Bender" follows the following typing:

{
  visitor?: (item: Bender, context: undefined) => Promise<void>;
  properties?: {
    element?: (item: Element, context: undefined) => Promise<void>;
    friends?: (item: Person[], context: undefined) => Promise<void>;
  }
}

When we want to run the visitor we use the visit method.

await avatarVisitor.visit(aang, "Bender", undefined);

The visit method takes in three arguments:

• The data that should be traversed. In this example the "aang" object.
• The TypeName of the data. In this example "Bender" because the "aang" object is a Bender. "Person" would have also been acceptable.
• The context (described in the next section)

Note: You DO NOT need to define a visitor function for every TypeName, only the ones you care about.

Note: Notice that we see the same person's name appear in two logs. For example we see both "Person: Sokka" and "NonBender: Sokka". That's because we visit the same object as a Person type and as a NonBender type.

Using Context

Sometimes you want to pass a shared object that's accessible from all traversers. That's where "context" comes in. Here's an example that uses context with our AvatarTraverser:

interface AvatarCountingVisitorContext {
  numberOfBenders: number;
}
const avatarCountingVisitor =
  avatarTraverser.createVisitor<AvatarCountingVisitorContext>({
    Bender: {
      visitor: async (item, context) => {
        context.numberOfBenders++;
      },
    },
  });
const countContext: AvatarCountingVisitorContext = { numberOfBenders: 0 };
await avatarCountingVisitor.visit(aang, "Bender", countContext);
console.log(countContext.numberOfBenders); // Logs 2

In this example, we want to count the number of "Benders" we encounter while traversing our object.

traverser.createVisitor accepts one generic defining the type of the context.

Using a Transformer

Sometimes you don't want to just visit an object, you want to transform it into something else. A Transformer is the best way to do that.

In the following example, we want to transform our data into a graph of ActionablePerson as defined by this interface:

interface ActionablePerson {
  doAction(): void;
  friends: ActionablePerson[];
}

We still want to maintain the friendship connections, but the transformed object is completely different.

Let's first look at the full code, then we'll break it down into sections:

const avatarTransformer = avatarTraverser.createTransformer<
  {
    Element: {
      return: string;
    };
    Bender: {
      return: ActionablePerson;
      properties: {
        element: string;
      };
    };
    NonBender: {
      return: ActionablePerson;
    };
  },
  undefined
>({
  Element: async (item) => {
    return item.toUpperCase();
  },
  Bender: {
    transformer: async (item, getTransformedChildren) => {
      const transformedChildren = await getTransformedChildren();
      return {
        doAction: () => {
          console.log(`I can bend ${transformedChildren.element}`);
        },
        friends: transformedChildren.friends,
      };
    },
    properties: {
      element: async (item, getTransformedChildren) => {
        const transformedChildren = await getTransformedChildren();
        return `the element of ${transformedChildren}`;
      },
    },
  },
  NonBender: {
    transformer: async (item, getTransformedChildren) => {
      const transformedChildren = await getTransformedChildren();
      return {
        doAction: () => {
          console.log(`I can't bend.`);
        },
        friends: transformedChildren.friends,
      };
    },
  },
  Person: async (
    item,
    getTransformedChildren,
    setReturnPointer,
    _context
  ) => {
    const personToReturn: ActionablePerson = {} as ActionablePerson;
    setReturnPointer(personToReturn);
    const transformedChildren = await getTransformedChildren();
    personToReturn.doAction = transformedChildren.doAction;
    personToReturn.friends = transformedChildren.friends;
    return personToReturn;
  },
});

const result = await avatarTransformer.transform(aang, "Bender", undefined);
result.doAction();
result.friends[0].doAction();
result.friends[1].doAction();
// Logs:
// I can bend the element of AIR
// I can't bend.
// I can bend the element of WATER

Defining Transformer Return Types

The first step to working with transformers is defining the return types for each transformer. This is done by providing a generic to the createTransformer function:

const avatarTransformer = avatarTraverser.createTransformer<
  {
    Element: {
      return: string;
    };
    Bender: {
      return: ActionablePerson;
      properties: {
        element: string;
      };
    };
    NonBender: {
      return: ActionablePerson;
    };
  },
  undefined
>({
  // ...
});

For each TypeName you wish to transform, you can provide return type. In this example, the Element transformer must return a string, and the NonBender transformer must return an Actionable Person.

Interface types may also provide the return types for their individual properties, as seen in the Bender type. Though, this is not required.

Note: You don't need to define the return type for every TypeName and property. This library's typings will recursively search for the correct return type based on the input you have given and display that in the tooltip. In the example below, the "Bender" translator knows that the friends property is an ActionablePerson[] not because the friends property was defined in the return types, but because it has deduced that the friends field is linked the the Person type which itself is made up of the Bender and NonBender types, and both those types have a return type of ActionablePerson.

Note: the undefined at the end defines the context and is not associated with the return types. To learn how to use context see the "Using Context" section.

Primitive Transformer

A primitive transformer is the simplest of the transformers. In this example Element is a primitive:

const avatarTransformer = avatarTraverser.createTransformer<
  // ...
>({
  Element: async (item: Element, context: undefined): Promise<string> => {
    return item.toUpperCase();
  },
  // ...
});

A primitive transformer receives an "item" corresponding to its type and a context and must return its defined return type.

Interface Transformer

An interface transformer allows you to transform not only the base interface object, but the properties of that object as well. In this example, Bender is an interface:

const avatarTransformer = avatarTraverser.createTransformer<
  // ...
>({
  // ...
  Bender: {
    transformer: async (
      item: Bender,
      getTransformedChildren: GetTransformedChildrenFunction,
      setReturnPointer: SetReturnPointerFunction,
      context: undefined
    ): Promise<ActionablePerson> => {
      const transformedChildren: {
          element: string;
          friends: ActionablePerson[];
      } = await getTransformedChildren();
      return {
        doAction: () => {
          console.log(`I can bend ${transformedChildren.element}`);
        },
        friends: transformedChildren.friends,
      };
    },
    properties: {
      element: async (item, getTransformedChildren, setReturnProperty, context) => {
        const transformedChildren: string = await getTransformedChildren();
        return `the element of ${transformedChildren}`;
      },
    },
  },
  // ...
});

The base transformer (located at the transformer field) and the property transformers are functions with four arguments:

• item: The original item. In this example, the base transformer would receive a Bender and the "element" transformer would receive an Element.
• getTransformedChildren: runs the transformers corresponding to the children of this object and returns their result. In this example, the base transformer's getTransformedChildren function returns { element: string; friends: ActionablePerson[] } because the element property transformer returns a string and the transformers that eventually feed into the friend field (Person, Bender, and NonBender) return ActionablePerson. In the elements transformer, the getTransformedChildren function returns string because the Elements transformer returns string.
• setReturnProperty: A function used to prevent infinite recursion for circular data. See the "Preventing Circular Recursion" section for more.
• context: The context variable. See the "Using Context" section for more.

A transformer must return its defined return type. For example, the base transformer must return ActionablePerson because it was defined that way when creating the return types.

Union Transformer

A union transformer lets you transform a Union type. In this example "Person" is a union type.

const avatarTransformer = avatarTraverser.createTransformer<
  // ...
>({
  // ...
  Person: async (
    item: Person,
    getTransformedChildren: GetTransformedChildrenFunction,
    setReturnPointer: SetReturnPointerFunction,
    context: undefined
  ) => {
    const personToReturn: ActionablePerson = {} as ActionablePerson;
    const transformedChildren: ActionablePerson = await getTransformedChildren();
    personToReturn.doAction = transformedChildren.doAction;
    personToReturn.friends = transformedChildren.friends;
    return personToReturn;
  },
});

The transformer function has four arguments:

• item: The original item. In this example, the transformer would receive a Person.
• getTransformedChildren: runs the transformers corresponding to the indivual elements that make up the union and returns their result. In this example, the transformer's getTransformedChildren function returns ActionablePerson because this union is made up of Bender and NonBender and both are set to return an ActionablePerson.
• setReturnProperty: A function used to prevent infinite recursion for circular data. See the "Preventing Circular Recursion" section for more.
• context: The context variable. See the "Using Context" section for more.

A transformer must return its defined return type. For example, the transformer must return ActionablePerson because it was defined that way when creating the return types.

Note: The above example transformer is actually not needed as it simply returns a duplicate of the value provided by getTransformedChildren. If a transformer is not provided, by default, this library will pass on the values from getTransformedChildren.

Preventing Circular Recursion

Our example data is circular - it loops back on itself. If I were to call aang.friends[0].friends[0], I would once again be at the aang object. This is very useful when visiting the objects, but it poses a problem when we want to transform them. The aang transformer needs to wait for the sokka and katara objects to be transformed in order for it to transform itself. But the sokka object needs to wait for the aang and katara object to be transformed. The same is true for the katara object. So, if this is the case where do you begin?

Recall the way we defined this data in the first place:

const aang: Bender = {
  name: "Aang",
  element: "Air",
  friends: [],
};
const sokka: NonBender = {
  name: "Sokka",
  friends: [],
};
const katara: Bender = {
  name: "Katara",
  element: "Water",
  friends: [],
};
aang.friends.push(sokka, katara);
sokka.friends.push(aang, katara);
katara.friends.push(aang, sokka);

Note that we first defined an incomplete object, then once all of our objects were defined, we modified it to link them all together.

You can do the same thing using the setRetunPointer function:

const avatarTransformer = avatarTraverser.createTransformer<
  // ...
>({
  // ...
  Person: async (
    item: Person,
    getTransformedChildren: GetTransformedChildrenFunction,
    setReturnProinter: SetReturnPointerFunction,
    context: undefined
  ) => {
    const personToReturn: ActionablePerson = {} as ActionablePerson;
    setReturnPointer(personToReturn); // <------ HERE
    const transformedChildren: ActionablePerson = await getTransformedChildren();
    personToReturn.doAction = transformedChildren.doAction;
    personToReturn.friends = transformedChildren.friends;
    return personToReturn;
  },
});

In this example we call setReturnPointer and pass in an incomplete object. After that, we can safely call getTransformedChildren without worrying about hitting an infinite loop. Once we have the transformedChildren, we can attach them to the original object we passed to setReturnPointer;

setReturnPointer should be called by at least one of the transformers involved in a potential loop.

Running the Transform Function

Once you have defined all of your transformers, you can run the transform function:

const result = await avatarTransformer.transform(aang, "Bender", undefined);
result.doAction();
result.friends[0].doAction();
result.friends[1].doAction();
// Logs:
// I can bend the element of AIR
// I can't bend.
// I can bend the element of WATER

The transform function takes in three arguments:

• The data that should be traversed. In this example the aang object.
• The TypeName of the data. In this example "Bender" because the aang object is a Bender. "Person" would have also been acceptable.
• The context (see the "Using Context" section for more)

The transform method returns the return type corresponding to the TypeName. In this case, it returns ActionablePerson because that is the return type for Bender.

Sponsorship

This project was made possible by a grant from NGI Zero Entrust via nlnet. Learn more on the NLnet project page.

Liscense

MIT