Abstract Syntax Tree

This library uses a doubly-linked list Abstract Syntax Tree (AST) to represent the parsed block and inline elements. All such elements extend from the Node class.

Document

The root node of the AST will always be a Document object. You can obtain this node a few different ways:

Visualization

Even with an interactive debugger it can be tricky to view an entire tree at once. Consider using the XmlRenderer to provide a simple text-based representation of the AST for debugging purposes.

Node Traversal

There are four different ways to traverse/iterate the Nodes within the AST:

Method Pros Cons
Manual Traversal Best way to access/check direct relatives of nodes Not useful for iteration
Iterating the Tree Fast and efficient Possible unexpected behavior when adding/removing sibling nodes while iterating
Walking the Tree Full control over iteration Up to twice as slow as iteration; adding/removing nodes while iterating can lead to weird behaviors
Querying Nodes Easier to write and understand; no weird behaviors Not memory efficient

Each is described in more detail below

Manual Traversal

The following methods can be used to manually traverse from one Node to any of its direct relatives:

This is best suited for situations when you need to know information about those relatives.

Iterating the Tree

If you’d like to iterate through all the nodes, use the iterator() method to obtain an iterator that will loop through each node in the tree (using pre-order traversal):

foreach ($document->iterator() as $node) {
    echo 'Current node: ' . get_class($node) . "\n";
}

Given an AST like this (XML representation):

<document>
  <heading level="1">
    <text>Hello World!</text>
  </heading>
  <paragraph>
    <text>This is an example of </text>
    <strong>
      <text>CommonMark</text>
    </strong>
    <text>.</text>
  </paragraph>
</document>

The code above will output:

Current node: League\CommonMark\Node\Block\Document
Current node: League\CommonMark\Extension\CommonMark\Node\Block\Heading
Current node: League\CommonMark\Node\Inline\Text
Current node: League\CommonMark\Node\Block\Paragraph
Current node: League\CommonMark\Node\Inline\Text
Current node: League\CommonMark\Extension\CommonMark\Node\Inline\Strong
Current node: League\CommonMark\Node\Inline\Text
Current node: League\CommonMark\Node\Inline\Text

This iterator doesn’t use recursion, so you won’t blow the stack when working with deeply-nested nodes. It’s also very CPU and memory-efficient.

Be careful when modifying nodes while iterating the tree as some of those changes may affect the current iteration process, especially for sibling nodes that come after the current one. For example, if you remove the current node’s next() sibling, the next loop of that iteration will still include the removed sibling even though it was successfully removed from the AST. Similarly, any new siblings that are added won’t be visited on the next loop.

Walking the Tree

If you’d like to walk through all the nodes, visiting each one as you enter and leave it, use the walker() method to obtain an instance of NodeWalker. This also uses pre-order traversal but emitting NodeWalkerEvents along the way:

use League\CommonMark\Node\NodeWalker;

/** @var NodeWalker $walker */
$walker = $document->walker();
while ($event = $walker->next()) {
    echo 'Now ' . ($event->isEntering() ? 'entering' : 'leaving') . ' a ' . get_class($event->getNode()) . ' node' . "\n";
}

Using the same example AST in the previous section, this code will output:

Now entering a League\CommonMark\Node\Block\Document node
Now entering a League\CommonMark\Extension\CommonMark\Node\Block\Heading node
Now entering a League\CommonMark\Node\Inline\Text node
Now leaving a League\CommonMark\Extension\CommonMark\Node\Block\Heading node
Now entering a League\CommonMark\Node\Block\Paragraph node
Now entering a League\CommonMark\Node\Inline\Text node
Now entering a League\CommonMark\Extension\CommonMark\Node\Inline\Strong node
Now entering a League\CommonMark\Node\Inline\Text node
Now leaving a League\CommonMark\Extension\CommonMark\Node\Inline\Strong node
Now entering a League\CommonMark\Node\Inline\Text node
Now leaving a League\CommonMark\Node\Block\Paragraph node
Now leaving a League\CommonMark\Node\Block\Document node

This approach offers many of the same benefits as the simple iteration shown in the previous section such as memory efficiency and no recursion. The key differences come from how you enter and leave nodes:

  1. Iteration can potentially take twice as long - not ideal for performance
  2. Provides you with more control over exactly when an action is taken on a node which is sometimes needed for certain AST manipulations
  3. Also provides a resumeAt() method to override where it should iterate next

But like with the iterator, be careful when adding/removing nodes while walking the tree, as there are even more subtle cases where the walker could even lose track of where it was, which may result in some nodes being visited multiple times or not at all.

Querying Nodes

If you’re trying to locate certain nodes to perform actions on them, querying the nodes from the AST might be easier to implement. This can be done with the Query class:

use League\CommonMark\Extension\CommonMark\Node\Block\BlockQuote;
use League\CommonMark\Extension\CommonMark\Node\Inline\Link;
use League\CommonMark\Node\Block\Paragraph;
use League\CommonMark\Node\Query;

// Find all paragraphs and blockquotes that contain links
$matchingNodes = (new Query())
    ->where(Query::type(Paragraph::class))
    ->orWhere(Query::type(BlockQuote::class))
    ->andWhere(Query::hasChild(Query::type(Link::class)))
    ->findAll($document);

foreach ($matchingNodes as $node) {
    // TODO: Do something with them
}

Each condition passed into where(), orWhere(), or andWhere() must be a callable “filter” that accepts a Node and returns true or false. We provide several methods that can help create these filters for you:

Method Description
Query::type(string $class) Creates a filter that matches nodes with the given class name
Query::hasChild() Creates a filter that matches nodes which contain at least one child
Query::hasChild(callable $condition) Creates a filter that matches nodes which contain at least one child that matches the inner $condition
Query::hasParent() Creates a filter that matches nodes which have a parent
Query::hasParent(callable $condition) Creates a filter that matches nodes which have a parent that matches the inner $condition

You can of course create your own custom filters/conditions using an anonymous function or by implementing ExpressionInterface:

use League\CommonMark\Node\Node;
use League\CommonMark\Node\Query;
use League\CommonMark\Node\Query\ExpressionInterface;

class ChildCountGreaterThan implements ExpressionInterface
{
    private $count;

    public function __construct(int $count)
    {
        $this->count = $count;
    }

    public function __invoke(Node $node) : bool{
        return count($node->children()) > $this->count;
    }
}

$query = (new Query())
    ->where(function (Node $node): bool { return $node->data->has('attributes/class'); })
    ->andWhere(new ChildCountGreaterThan(3));

Modification

The following methods can be used to modify the AST:

DocumentParsedEvent

The best way to access and manipulate the AST is by adding an event listener for the DocumentParsedEvent.

Data Storage

Each Node has a property called data which is a Data (array-like) object. This can be used to store any arbitrary data you’d like on the node:

use League\CommonMark\Node\Inline\Text;

$text1 = new Text('Hello, world!');
$text1->data->set('language', 'English');
$text1->data->set('is_good_translation', true);

$text2 = new Text('Bonjour monde!');
$text2->data->set('language', 'French');
$text2->data->set('is_good_translation', false);

foreach ([$text1, $text2] as $text) {
    if ($text->data->get('is_good_translation')) {
        sprintf('In %s we would say: "%s"', $text->data->get('language'), $text->getLiteral());
    } else {
        sprintf('I think they would say "%s" in %s, but I\'m not sure.', $text->getLiteral(), $text->data->get('language'));
    }
}

You can also access deeply-nested paths using / or . as delimiters:

use League\CommonMark\Node\Inline\Text;

$text = new Text('Hello, world!');
$text->data->set('info', ['language' => 'English', 'is_good_translation' => true]);

var_dump($text->data->get('info/language'));
var_dump($text->data->get('info.is_good_translation'));

$text->data->set('info/is_example', true);

HTML Attributes

The data property comes pre-instantiated with a single data element called attributes which is used to store any HTML attributes that need to be rendered. For example:

use League\CommonMark\Extension\CommonMark\Node\Inline\Link;

$link = new Link('https://twitter.com/colinodell', '@colinodell');
$link->data->append('attributes/class', 'social-link');
$link->data->append('attributes/class', 'twitter');
$link->data->set('attributes/target', '_blank');
$link->data->set('attributes/rel', 'noopener');

Edit this page