The future of the tree adapter architecture

[43081j]

Currently, tree adapters exist as a concept so we can instruct the parser on how to build up an AST, any AST.

This allows us to have parse5 produce its own AST or a htmlparser2 AST for example.

Sounds like an outcome we may want, but im feeling more and more like its definitely the wrong solution to the problem.

It isn't possible to strongly type it

Our current types, and the ones in DT (which i wrote) are wrong.

All along, we thought this pattern worked:

interface TypeMap {
  element: unknown;
  comment: unknown;
}

interface Adapter<T extends TypeMap> {
  getAttribute(el: T['element'], name: string): string;
}

but it doesn't. all the types narrow to unknown, the compiler will allow you to getAttribute(commentNode, 'foo') because T['comment'] and T['element'] both ultimately resolve to unknown.

This isn't fixable.

Type maps won't work, tuples of types won't work.

I talked to a few people on typescript discord and we came up with this:

interface Adapter<
  TDocument,
  TElement,
  TComment,
  ...
> {
  getAttribute(el: TElement, name: string): string;
  isElement(node: TNode): node is TElement;
}

but this doesn't work either. because TNode can't be defined. where/how can we define it? it can't be a type parameter, because then it could be anything (yet again) which means TElement may not necessarily be assignable to it, so tsc will fail.

we would have to repeat ourselves with the full union every time we reference TNode, and no longer have a TNode. craziness.

It increases complexity, bugs, etc

JS parsers generally implement an esprima-compatible AST, because having a bunch of unrelated, incompatible ASTs would be a terrible idea. They did the right thing.

By not having one standard AST like this, we have a crazy amount of over-genericised complexity trying to handle the fact that everything can be anything. This means we definitely have more bugs, more complexity and lower performance than if we had a well known data structure.

Consumers need to read docs in at least two places

A consumer needs to read the docs for the parser and the tree adapter to find out what will happen.

Solution

We should remove tree adapters entirely, making parse5 produce a single, standard AST.

We can then introduce the concept of an 'output transform' which can consume the parse5 AST and output something else.

This would lead to types like so:

import {htmlparser2Transform} from 'wherever';

const doc = parse(source: string): Document; // so simple

htmlparser2Transform; // (doc: Document) => T

const htmlparser2Doc = htmlparser2Transform(doc); // T

meaning we don't care anymore about all this over-generic nonsense until the very end, and even then its just a simple mapper function.

cc @fb55

[43081j]

A friend did point out that this would be less efficient. If we do stick with the adapter pattern, I'm happy with that but we really need to figure the strong typing out. It is currently broken

[fb55]

I agree that removing adapters will likely make things slower, plus increase memory usage. I have a preference to to keep them around.

[43081j]

alternatives attempted so far:

typed adapter (Adapter<TDocument, TElement, TComment, ...>)

works, i think, but causes hell for us as every function in the parser has to list all these individual type parameters. every place that has a Parser needs to do the same, and every place that has an adapter, etc, etc.

[43081j]

@wooorm @fb55 i know i have shot down almost every comment so far but thats just because this is a difficult problem. im happy with us keeping adapters, if we can fix the types.

i've spent a lot of time already trying to figure this out, with various people too. there is no way we can make "type maps" work, they were wrong from the start (my fault, i wrote them before this fork existed).

if we go with passing every type parameter, it does work but we lose Node, which is unacceptable.

so i don't have any suggestions left yet, this is a tough problem..

[43081j]

To summarise, rather than the several on going threads at once:

Adapter<TDoc, TEl, TComm, ...>

Will work, but means everything has to have all of these type parameters. Including:

• Parser<TDoc, TEl, TComm, ...>
• Serializer<TDoc, TEl, TComm, ...>
• ParserOptions<TDoc, TEl, TComm, ...>
• All internal parser functions
• etc

This solution also means we lose Node. That is unacceptable but there may be a middle ground:

• Lose Node on tree adapters (specify the full union every time)
• But still expose it in each tree adapter's types (i.e. Document would still contain Node[], a type the tree adapter exports)

So this solution may work at the expense of us writing and repeating an a LOT of parameters.

Type maps

They won't work.

One way or another, the map has to have a type, which means any or unknown (since we can't expect any kind of base type all adapters implement). Due to this, we lose most of our type strength because everything becomes the base type (any/unknown), so most methods begin accepting anything rather than being strongly typed.

I'm not aware of a way to ever make this work.

Dumb ParserOptions['treeAdapter'] types

Another option is to massively dumb down the tree adapter of the parser options.

This means each tree adapter would be strongly typed, but would not implement any kind of common interface.

The tree adapter property in our options object would then be "whatever" (impossible to strongly type at that point really:

parse<T>(
  code: string,
  options: {
    adapter: T
  }
): T extends {createDocument(): infer TDocument} ? TDocument : unknown;

basically this

@wooorm this one is my suggestion, i think. this way we can keep things simple and all we lose is some internal typing.

[wooorm]

I don’t really understand what would be impossible in TypeScript?
And if the only thing is isElement(node: TNode) vs isElement(node: unknown), that sounds rather small to me? Not a good reason to change everything?

---

I’m assuming that removing adapters will cut down on bundle size and likely will improve performance as well: just building an object model instead of calling functions for everything should be faster (although this needs to be verified).
I’d recommend not changing too many things in one major version, though.

[wooorm]

T['element'] should indeed internally be unknown? If a (typed) adapter is used, then the user would get a typed output?

The fact that countless parse5 consumers and parse5 itself depends heavily on the Node type.

But, as the types are currently broken, and we’re looking at a major release and fixing them, that’d be an acceptable trade off?

meaning we have to cast or type guard in many places. anyway thats only one of the currently wrong types.

A tuple can be used for that right?

type Stack = [1, ...2[]]

function x(list: Stack): void {
    const head = list[0] // 1
    const t1 = list[1] // 2
    const t2 = list[2] // 2
    console.log(head, t1, t2)
}

[43081j]

TElement should be a generic type, and TDocument should be a generic type, both defined by the adapter. neither are unknown, they are well known types by the adapter.

we want to ensure we are passing the right types to the right methods. getAttribute(TComment) shouldn't be possible but would be if we lazily called everything unknown. we'd be vastly reducing our type strength throughout the parser and covering up countless places for bugs to happen.

But, as the types are currently broken, and we’re looking at a major release and fixing them, that’d be an acceptable trade off?

No. in google's repos alone (which use parse5), the Node type is used heavily for representing "some node from the AST". there's no way we should be making them change that to having to specify the union every time or create their own Node type around it. 100% we need to define what Node is for consumers, there's no way we can drop that, its a fundamental type.

in my repos, modern web, and a whole bunch of others too we all use the node type heavily.

A tuple can be used for that right?

It wouldn't help, the logic is currently already broken. in almost every place we use the open element stack, we have assumed the current node on the stack is a TElement. this has never been true, because the first node is a TDocument. it just didn't trip us up so far because we did all this inside conditions like "if tagname == something" (which would exclude documents).

we should just have far better type inference and those conditions would automatically have narrowed the type to TElement.

[wooorm]

I don’t understand this conversation anymore. Whether it’s about unions or about stacks.
Everything is apparently broken, but we can’t change types (because they’re being used), instead we should remove frequently used code? (adapters, which are used a lot).

---

To reiterate my stance: if the current DT types are broken, and we’re creating a major to fix a bunch of stuff and add TypeScript, then stuff is going to break anyway, we might as well ship proper, working, types.

[43081j]

no, as i've mentioned a few times i don't care if we keep the adapters or not. i care that we fix our very broken types.

yes, we should ship proper, working types. know how to write them? that's what we're currently stuck with! 😂

[wooorm]

Maybe it’s better then to have this discussion when the code is working?
It feels rather theoretical right now. Perhaps it’s better to have practical examples to look at?

[fb55]

My current thoughts — let me know if this makes sense.

Afaict what we are looking for is opaque default types for the type map. TS doesn't support that, but one way to simulate opaque types is to make the default types unique objects. Node etc. would still have to be defined as unions:

export interface TreeAdapterTypeMap<
    Document = { type?: 'Document' },
    DocumentFragment = { type?: 'DocumentFragment' },
    Element = { type?: 'Element' },
    CommentNode = { type?: 'CommentNode' },
    TextNode = { type?: 'TextNode' },
    Template = { type?: 'Template' },
    DocumentType = { type?: 'DocumentType' },
    ParentNode = Document | DocumentFragment | Element | Template,
    ChildNode = Element | Template | CommentNode | TextNode | DocumentType,
    Node = ParentNode | ChildNode
> {
    document: Document;
    documentFragment: DocumentFragment;
    element: Element;
    commentNode: CommentNode;
    textNode: TextNode;
    template: Template;
    documentType: DocumentType;
    parentNode: ParentNode;
    childNode: ChildNode;
    node: Node;
}

This seems to do the job in terms of getting good types throughout the codebase. Of course, there is a lot to fix up afterwards, but that's a separate issue.

[43081j]

yeah you are using a union as the default, of a type which can be anything. the default is irrelevant.

in fact the only reason this would build is because T extends TypeMap is telling it that it is always the default types. which of course is a lie, since the real types could be of any structure. its essentially tricking the compiler into always casting to the defaults as a way to get some useful types.

for example:

type CustomTypeMap = TypeMap<
  {nodeType: 'doc'},
  {nodeType: 'frag'},
  {nodeType: 'el'},
  ...
>;

declare const adapter: Adapter<CustomTypeMap>; // ERROR, of course.
// because `{nodeType: 'doc'}` doesn't extend `{type?: 'Document'}`, our made up type
// Adapter<T extends TypeMap> === Adapter<T extends TypeMap<{type?: 'Document'}, ...>>

type maps don't work.

[wooorm]

Why not T extends TypeMapWithAnys = TypeMapWithUnknowns?
(Or, instead of anys, some minimum required object form?)

[43081j]

thats what we do now, except with unknown, hence the problems we're having. the same would happen with any.

interface AdapterMap {
  document: any;
  element: any;
}

interface Adapter<T extends AdapterMap> {
  getAttribute(node: T['element'], name: string): string;
}

function parse<T extends AdapterMap>(adapter: Adapter<T>): void {
    adapter.getAttribute({} as T['document'], 'x');
}

what its default type is doesn't matter anymore, because that isn't the type. the type defines that they're all the same type (any, unknown, whatever). so you can pass any of the types as each other, i.e. no type checking happens anymore.

the only reason Felix's code worked is because he said T extends Adapter which will resolve to T extends Adapter<T1, T2, ...>. this means his constraint wasn't saying "something which extends Adapter", it was saying "something which extends the default adapter" (which none do, it was wrongly typed, i.e. a bad cast).

in his case the defaults were made up types: Adapter<{type?: 'document'}, {type?: 'element'}, ...>. so the code was constraining to adapters which inherit those models, not any or unknown.

[wooorm]

thats what we do now, except with unknown, hence the problems we're having.

So they’re not the same. And that difference is exactly what I’m trying to get at.
Using any for what something extends, allows adapters to type what they return.
Using unknown as the default means that internally, or when untyped, unknown is used.

[43081j]

i am aware they're not the same, but they make no difference here. if you use any, you have the exact same problem: every type is assignable to each other.

nothing to stop you doing getAttribute(node as TComment, 'foo') if we do what you're saying. type maps don't work, because no matter what we do, we have to supply a base type of any or unknown which will result in all types being equivalent/interchangeable.

do you understand that assigning a default type doesn't solve the problem?

interface Adapter<T extends TypeMap<{
  document: {type: 'doc'};
  element: {type: 'element'};
}>> {
  getAttribute(node: T['element'], name: string): string;
  createDocument(): T['document'];
}

is (roughly) what felix's original suggestion actually results in. which is of course wrong, since not all adapters will use that model.

if you go any change it to extends TypeMap<{document: any; element: any;}>, that allows you to pass documents into methods which consume elements, etc etc.

does that make sense?

[fb55]

I have opened #42 with how I think the types should work. Mostly what I posted before, with some fixes. I am struggling to find a way to sneak bad code through this anymore — @43081j please let me know if you can think of anything.