StarBlog Extra Episode (2): In-depth Analysis of Markdig Source Code, Optimizing ToC Title Extraction and Article Directory Tree Generation Logic

Preface

Lately, I've been feeling a bit lost. After all, we're now in the era of AI, and the CPython source code analysis expert I used to follow has announced that they will no longer publish technical articles. This made me question the significance of grinding on code and tech skills for a while...

However, the power of habit is strong. Regardless, I've been in the tech field for so many years, and it's not easy to suddenly give up something I've been persistent about for so long...

OK, after a brief moment of confusion, let's get back to the main topic. Earlier, in the StarBlog Development Notes Part 19: Exploring Markdown Rendering Solutions, I introduced how I built my own solution for extracting the Table of Contents (ToC) from Markdown.

Although I spent considerable time designing this feature back then, due to limited technical skills and effort, it wasn't perfect. In some scenarios, the extracted IDs often didn't match those generated by Markdig.

Recently, while developing the StarBlog blog publishing tool, I encountered this problem again. I decided to take the time to resolve it completely!

Markdig is a great library, but it lacks documentation. To implement certain customization features, I had to dive into the source code.

This time, I refactored the Markdown ToC generation logic. I used Markdig's AutoIdentifiers extension to automatically generate heading IDs and optimized the establishment of parent-child relationships and the generation of the tree structure. I removed the manual slug generation logic, improving both code maintainability and accuracy.

Current Issues

The current Table of Contents (ToC) extraction feature is a relatively basic implementation I built myself. The specific approach and implementation are introduced in the 19th development notes. The issue encountered is that some characters that should not have been replaced were substituted.

The code for this implementation is located at: StarBlog.Share/Extensions/Markdown/ToC.cs

Here is an example:

The following heading2

## No.2 cookiecutter-django GitHub Stars: 5735

The ID generated using Markdig is: no.2-cookiecutter-django-github5735

Whereas my manually created implementation is: no2-cookiecutterdjango-github5735

This results in the problem that clicking the heading on the left side cannot navigate/jump to the corresponding section.

## Solution Approach

At first, I thought I could optimize my ToC (Table of Contents) extraction method implementation.

However, after several attempts, I found there were always edge cases slipping through.

In the end, I could only turn back to the approach I initially gave up on: directly using the same ToC extraction method as Markdig.

So why didn't I use it from the start?

The reason, as I mentioned earlier, is that Markdig's documentation is not detailed enough, and I was too lazy to dig through Markdig's source code.
## Diving Deep into Markdig Source Code

This time I can't help but dive into the source code

The following analysis applies only to version 0.40.0, which is the latest version at the time of writing this article: https://github.com/xoofx/markdig/tree/0.40.0
### Heading Processing Section

Let's first look at the code Markdig uses to process markdown headings

1. Core Data Structure: `src\Markdig\Syntax\HeadingBlock.cs`

- Defines the data structure representing headings
- Contains key attributes of headings:
  - Level: Heading level (1-6)
  - HeaderChar: Heading character (usually #)
  - IsSetext: Whether it is a Setext-style heading (using === or ---)

2. Parser: `src\Markdig\Parsers\HeadingBlockParser.cs`

- Responsible for parsing heading syntax in Markdown
- Supports two heading formats:
  - ATX style (#)
  - Setext style (=== or ---)
- Main parsing logic is in the TryOpen method

3. Renderer: `src\Markdig\Renderers\Html\HeadingRenderer.cs`

- Responsible for rendering HeadingBlock to HTML
- Converts headings of different levels to corresponding h1-h6 tags

Processing Flow:

1. When a line starting with # or a text line containing === / --- on the next line is encountered, the HeadingBlockParser is triggered
2. The parser creates a HeadingBlock instance and sets the corresponding properties (level, type, etc.)
3. Finally, the HeadingRenderer renders the HeadingBlock into the corresponding HTML tags
### Heading ID Generation

Now I've clarified the heading processing section.

I've also learned some good approaches. At this point, I could easily build a custom tool from scratch to handle Markdown headings.

However, the problem to solve this time is the ID for headings.

I'll need to continue digging through the code.

Based on code analysis, the ID generation for headings in Markdig is mainly implemented through the AutoIdentifier extension, with the concrete implementation in `src\Markdig\Extensions\AutoIdentifiers\AutoIdentifierExtension.cs`.

The main flow for ID generation is as follows:

#### Basic Generation Rules

- If a heading has an ID attribute manually set, it remains unchanged.
- If the heading content is empty, "section" is used as the ID.
- Otherwise, the heading's text content is converted into a URL-friendly format.

#### ID Conflict Handling

- When the generated ID conflicts with an existing one, a numeric suffix is automatically added.
- For example: if "my-heading" already exists, the new ID will become "my-heading-1", "my-heading-2", and so on.

#### Specific Processing Steps

```c#
// Get the original text of the heading
stripRenderer.Render(headingBlock.Inline);
ReadOnlySpan<char> rawHeadingText = ((FastStringWriter)stripRenderer.Writer).AsSpan();

// Convert the text to a URL-friendly format
string headingText = (_options & AutoIdentifierOptions.GitHub) != 0
    ? LinkHelper.UrilizeAsGfm(rawHeadingText)
    : LinkHelper.Urilize(rawHeadingText, (_options & AutoIdentifierOptions.AllowOnlyAscii) != 0);

// Handle the case of an empty heading
var baseHeadingId = string.IsNullOrEmpty(headingText) ? "section" : headingText;

// Handle ID conflicts
var headingId = baseHeadingId;
if (!identifiers.Add(headingId))
{
    var headingBuffer = new ValueStringBuilder(stackalloc char[ValueStringBuilder.StackallocThreshold]);
    headingBuffer.Append(baseHeadingId);
    headingBuffer.Append('-');
    uint index = 0;
    do
    {
        index++;
        headingBuffer.Append(index);
        headingId = headingBuffer.AsSpan().ToString();
        headingBuffer.Length = baseHeadingId.Length + 1;
    }
    while (!identifiers.Add(headingId));
}

Special Handling Rules

From the test cases, you can see how some special situations are handled:

# 1.0 This is a heading

会生成ID为"this-is-a-heading"，即会去掉开头的数字。

Summary

This ID generation mechanism ensures

• Uniqueness of IDs
• URL friendliness (no special characters)
• Maintains readability
• Automatic handling of duplicates

## How to Obtain the ID?

Now that we have a detailed understanding of the heading implementation in Markdig,

How can we obtain the generated heading ID when using the Markdig library?

By carefully analyzing the code, I found that the correct way to get the heading ID in Markdig is through the `GetAttributes()` method, but it can only be obtained after the rendering is complete. This is because the ID generation is completed during the `HeadingBlock_ProcessInlinesEnd` phase.

The correct way to obtain it is:

```c#
var pipeline = new MarkdownPipelineBuilder()
    .UseAutoIdentifiers()
    .Build();

// First, we need to parse the document
var document = Markdown.Parse(markdownText, pipeline);

// Important: We need to render the document first because the ID is generated during rendering
Markdown.ToHtml(document, pipeline);

// Then we can obtain the heading IDs
foreach (var heading in document.Descendants<HeadingBlock>())
{
    string? headingId = heading.GetAttributes().Id;
    Console.WriteLine($"Heading: {heading.Level}, ID: {headingId}");
}

Because in AutoIdentifierExtension.cs, the ID generation is done when processing the end of inline elements:

private void HeadingBlockParser_Closed(BlockProcessor processor, Block block)
{
    // ...
    // Then we register after inline have been processed to actually generate the proper #id
    headingBlock.ProcessInlinesEnd += HeadingBlock_ProcessInlinesEnd;
}

Therefore, if ToHtml() is not called first for rendering, the ProcessInlinesEnd event will not be triggered, and the ID will not be generated. This is why rendering must be performed first before the correct ID can be obtained.

This design is to ensure:

1. ID uniqueness (by collecting all headings during rendering)
2. Correct handling of inline elements within headings (such as links, emphasis, etc.)
3. Correct processing of duplicate headings in document order

Thus, when using Markdig, if you need to obtain the heading ID, you must perform the rendering first; otherwise, the obtained ID will be null.

Final Implementation

Code at: StarBlog.Share/Extensions/Markdown/ToC.cs

Here we primarily refactored the Markdown Table of Contents (ToC) generation logic. We utilized Markdig's AutoIdentifiers extension to automatically generate heading IDs, and optimized the establishment of parent-child relationships and tree structure generation. The logic for manually generating slugs was removed, enhancing code maintainability and accuracy.

private static string GetHeadingText(HeadingBlock heading) {
  if (heading.Inline == null) return string.Empty;

  var stringBuilder = new StringBuilder();
  foreach (var inline in heading.Inline.Descendants<LiteralInline>()) {
    stringBuilder.Append(inline.Content);
  }

  return stringBuilder.ToString();
}

public static List<TocNode>? ExtractToc(this Post post) {
  if (post.Content == null) return null;

  var pipeline = new MarkdownPipelineBuilder()
    .UseAutoIdentifiers()
    .Build();

  var document = Markdig.Markdown.Parse(post.Content, pipeline);

  // In Markdig, the correct way to get a heading's ID is via the GetAttributes() method, but it's only available after rendering is complete.
  // Because ID generation is completed during the HeadingBlock_ProcessInlinesEnd phase (see source: src\Markdig\Extensions\AutoIdentifiers\AutoIdentifierExtension.cs)
  _ = document.ToHtml(pipeline);

  // 1. First, convert all headings into a flat structure
  var headings = document.Descendants<HeadingBlock>()
    .Select((heading, index) => new Heading {
      Id = index,
      Text = GetHeadingText(heading),
      Slug = heading.GetAttributes().Id,
      Level = heading.Level
    })
    .ToList();

  // 2. Establish parent-child relationships
  for (var i = 0; i < headings.Count; i++) {
    var current = headings[i];
    // Look backwards for the first heading with a lower level than the current one to serve as its parent
    for (int j = i - 1; j >= 0; j--) {
      if (headings[j].Level < current.Level) {
        current.Pid = headings[j].Id;
        break;
      }
    }
  }

  // 3. Convert into a tree structure
  var tocNodes = new List<TocNode>();
  var nodeMap = new Dictionary<int, TocNode>();

  foreach (var heading in headings) {
    var node = new TocNode {
      Text = heading.Text,
      Href = $"#{heading.Slug}"
    };
    nodeMap[heading.Id] = node;

    if (heading.Pid == -1) {
      // Root node
      tocNodes.Add(node);
    }
    else {
      // Child node
      var parentNode = nodeMap[heading.Pid];
      if (parentNode.Nodes == null) {
        parentNode.Nodes = new List<TocNode>();
      }
      parentNode.Nodes.Add(node);
    }
  }

  return tocNodes;
}

With this approach, the extracted ToC will be fully consistent with Markdig's output.

Summary and Preview

Simple functionality, yet it’s still a significant pitfall. During the development of the blog, there have been countless such pitfalls that required time to resolve. It is a bit tiring, but since the project has been live for so long, some maintenance is always necessary.

Next, I will also release several new things related to StarBlog:

• StarBlogPublisher - An AI-driven one-click article publishing tool that has been completed and will be released soon.
• Blog automatic backup tool - Currently in development.
• More access log analysis features - Currently in development.