How to construct tree pattern matching algorithm in JavaScript?

Okay this is a bit of an involved question, but tl;dr it's basically how do you parse an "actual tree" using a "pattern tree"? How do you check if a particular tree instance is matched by a specific pattern tree?

To start, we have the structure of our pattern tree. The pattern tree can generally contain these types of nodes:

• sequence node: Matches a sequence of items (zero or more).
• optional node: Matches one or zero items.
• class node: Delegates to another pattern tree to match.
• first node: Matches the first child pattern it finds out of a set.
• interlace node: Matches any of the child patterns in any order.
• text node: Matches direct text.

That should be good enough for this question. There are a few more node types, but these are the main ones. Essentially it is like a regular expression or grammar tree.

We can start with a simple pattern tree:

<sequence>
  <text value="foo">
    <text value="bar" />
  </text>
</sequence>

This should match any of the following trees of text.

<foo><bar/></foo><foo><bar/></foo><foo><bar/></foo>
<foo><bar/></foo>
<foo><bar/></foo><foo><bar/></foo>

More specifically, you should imagine that as JSON and the pattern tree as JSON as well.

{
  "tag": "foo",
  "children": [
    { "tag": "bar" }
  ]
}

And the sequence pattern tree is like this:

{
  "type": "sequence",
  "children": [
    {
      "type": "text",
      "value": "foo",
      "children": [
        {
          "type": "text",
          "value": "bar"
        }
      ]
    }
  ]
}

A more complex example would be like this for a pattern tree:

matchThing = <text name="thing">
  <text />
  <sequence>
    <first>
      <class name="value"/>
      <class name="function"/>
    </first>
  </sequence>
</text>

matchFunction = <text name="function">
  <text />
  <sequence>
    <text name="input">
      <text />
    </text>
  </sequence>
  <sequence>
    <text name="call">
      <text />
    </text>
  </sequence>
</text>

matchValue = <text name="value">
  <text />
</text>

It would match text like this:

<thing>
  <call-me-anything />
  <function>
    <input><foo/></input>
    <input><bar/></input>
    <call><foo/></call>
    <call><foo/></call>
    <call><bar/></call>
    <call><bar/></call>
  </function>
  <function>
    <call><baz/></call>
  </function>
  <value>
    <hello/>
  </value>
  <function>
    <input><hello/></input>
    <call><world/></input>
  </function>
</thing>

So imagine that as JSON as well.

Wondering how you go about creating an algorithm for this. I am stuck at the beginning, but it seems to require something like recursive descent of some sort, but on trees rather than on sequences.

So you have a function:

function checkIfMatch(actualTree, patternTree) {
  for (node in actualTree) {
    if (!checkIfMatchesSubtree(node, patternTree)) {
      return false
    }
  }
  return true
}

I don't really know how to begin this one, and am searching Google for "tree pattern matching algorithms" or "arbology". Going to take a lot of time to try and translate those mathematical abstractions into code, if I am even going in the right direction. Wondering if you could help construct a simple algorithm for this case. It's hard to figure out how you should be traversing the actual tree, while also traversing the pattern tree, and keeping track of the position you are in each tree.

• https://dml.cz/bitstream/handle/10338.dmlcz/147190/Kybernetika_54-2018-2_1.pdf

Spending quite a bit of time on it doesn't get me very far:

function parse(patternTree, textTree) {
  let state = { ti: 0, pi: 0 }
  while (state.ti < textTree.length) {
    let pattern = patternTree[state.pi]
    let result = parsePattern(pattern, textTree[state.ti])
    if (!result) {
      return
    }
  }
}

function parsePattern(patternNode, textNode, state) {
  if (patternNode.type == 'sequence') {
    return parseSequencePattern(patternNode, textNode, state)
  }
}

function parseSequencePattern(patternNode, textNode, state) {
  while (true) {
    let i = 0
    while (i < patternNode.children.length) {
      let childPattern = patternNode.children[i++]
      let result = parsePattern(childPattern, textNode)
      if (!result) {
        return false
      }

    }
  }
}


while (stack.length) {
  let {
    parents,
    node,
  } = stack.shift()

  stack.push({
    parents: [node, ...parents]
  })
}