HTML Table of contents parser

Question

I've written a table of contents parser for a FOSS wiki project I maintain in my spare time. The class takes a HTML string, injects anchor takes before each H1,H2 etc. and then generates the contents for the headers.

My main concern is boundary checks within the code. I haven't got any unit tests for it as it's a bit hard to test without a slightly contrived set of example text.

I'm after any glaring issues, or easier ways of doing the tree parsing the way I've done it. I'm reluctant to wrap the InsertToc method in a giant try/catch but instead have all all edge cases catered for.

The source is here as well.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HtmlAgilityPack;

public class TocParser
{
    private Header _previousHeader;

    /// <summary>
    /// Replaces all {TOC} tokens with the HTML for the table of contents. This method also inserts
    /// anchored name tags before each H1,H2,H3 etc. tag that the contents references.
    /// </summary>
    public string InsertToc(string html)
    {
        HtmlDocument document = new HtmlDocument();
        document.LoadHtml(html);
        HtmlNodeCollection elements = document.DocumentNode.ChildNodes;

        // The headers are stored in a flat list to start with
        List<Header> rootHeaders = new List<Header>();
        ParseHtmlAddAnchors(document.DocumentNode, rootHeaders, "h1");

        // Try parsing all H2 headers (as H1 is technically the page title).
        if (rootHeaders.Count == 0)
            ParseHtmlAddAnchors(document.DocumentNode, rootHeaders, "h2");

        // Add a fake root for the tree
        Header rootHeader = new Header("","h0");
        rootHeader.Children.AddRange(rootHeaders);
        foreach (Header header in rootHeaders)
        {
            header.Parent = rootHeader;
        }

        StringBuilder builder = new StringBuilder();
        builder.AppendLine("<div class=\"toc\">");
        builder.AppendLine("<div class=\"toc-title\">Contents [<a class=\"toc-showhide\" href=\"#\">hide</a>]</div>");
        builder.AppendLine("<div class=\"toc-list\">");
        builder.AppendLine("<ul>");
        GenerateTocList(rootHeader, builder);
        builder.AppendLine("</ul>");
        builder.AppendLine("</div>");
        builder.AppendLine("</div>");

        return document.DocumentNode.InnerHtml.Replace("{TOC}",builder.ToString());
    }

    /// <summary>
    /// Generates the ToC contents HTML for the using the StringBuilder.
    /// </summary>
    private void GenerateTocList(Header parentHeader, StringBuilder htmlBuilder)
    {
        // Performs a level order traversal of the H1 (or H2) trees
        foreach (Header header in parentHeader.Children)
        {
            htmlBuilder.AppendLine("<li>");
            htmlBuilder.AppendFormat(@"<a href=""#{0}"">{1}&nbsp;{2}</a>", header.Id, header.GetTocNumber(), header.Title);

            if (header.Children.Count > 0)
            {
                htmlBuilder.AppendLine("<ul>");
                GenerateTocList(header, htmlBuilder);
                htmlBuilder.AppendLine("</ul>");
            }

            htmlBuilder.AppendLine("</li>");
        }
    }   

    /// <summary>
    /// Parses the HTML for H1,H2, H3 etc. elements, and adds them as Header trees, where
    /// rootHeaders contains the H1 root nodes.
    /// </summary>
    private void ParseHtmlAddAnchors(HtmlNode parentNode, List<Header> rootHeaders, string rootTag)
    {
        foreach (HtmlNode node in parentNode.ChildNodes)
        {
            if (node.Name.StartsWith("h"))
            {
                Header header = new Header(node.InnerText,node.Name);

                if (_previousHeader != null && header.Level > _previousHeader.Level)
                {
                    // Add as a new child
                    header.Parent = _previousHeader;
                    _previousHeader.Children.Add(header);
                }
                else if (_previousHeader != null)
                {
                    // Add as a sibling
                    while (_previousHeader.Parent != null && _previousHeader.Level > header.Level)
                    {
                        _previousHeader = _previousHeader.Parent;
                    }

                    header.Parent = _previousHeader.Parent;

                    if (header.Parent != null)
                        header.Parent.Children.Add(header);
                }

                // Add an achor tag after the header as a reference
                HtmlNode anchor = HtmlNode.CreateNode(string.Format(@"<a name=""{0}""></a>",header.Id));
                node.PrependChild(anchor);

                if (node.Name == rootTag)
                    rootHeaders.Add(header);

                _previousHeader = header;
            }
            else if (node.HasChildNodes)
            {
                ParseHtmlAddAnchors(node, rootHeaders, rootTag);
            }
        }
    }

    /// <summary>
    /// Represents a header and its child headers, a tree with many branches.
    /// </summary>
    private class Header
    {
        public string Id { get; set; }
        public string Tag { get; set; }
        public int Level { get; private set; }
        public List<Header> Children { get; set; }
        public Header Parent { get; set; }
        public string Title { get; set; }

        public Header(string title, string tag)
        {
            Children = new List<Header>();
            Title = title;
            Tag = tag;

            int level = 0;
            int.TryParse(tag.Replace("h", ""),out level); // lazy (aka hacky) way of tracking the level using HTML H number
            Level = level;

            ShortGuid guid = ShortGuid.NewGuid();
            Id = string.Format("{0}{1}", Title.EncodeTitle(), guid);
        }

        public string GetTocNumber()
        {
            string result = SiblingNumber().ToString();

            if (Parent != null && Level > 1)
            {
                Header parent = Parent;

                while (parent != null && parent.Level > 0)
                {
                    result += "." + parent.SiblingNumber();
                    parent = parent.Parent;
                }
            }

            return new String(result.ToArray().Reverse().ToArray<char>());
        }

        public int SiblingNumber()
        {
            if (Parent != null)
            {
                for (int i = 0; i < Parent.Children.Count; i++)
                {
                    if (Parent.Children[i] == this)
                        return i +1;
                }
            }

            return 1;
        }

        public override bool Equals(object obj)
        {
            Header header = obj as Header;
            if (header == null)
                return false;

            return header.Id.Equals(Id);
        }

        public override int GetHashCode()
        {
            return Id.GetHashCode();
        }
    }
}

Answer 1

I'd be weary of solutions that builds the HTML by hand. Work with the DOM and let it write out the HTML for you. HAP can do that for you.

Don't create one-time use extension methods. It appears you created an extension method for strings to encode your titles. If you can't use it anywhere else in your code, it doesn't belong as an extension. I'd argue that it should be a regular static method of your Header class as it might be specific to how you want your headers encoded. In this context, it is confusing to see that call there.

Your logic in your headers to get the "sibling number" and TOC prefix is more complicated than it needs to be. Especially the GetTocNumber() method, the logic is very confusing to glance at. I was having a hard enough time trying to figure out what it was doing. The string reversal at the end really killed it. They both could be done simpler. In fact, they could be calculated at once on construction with some refactoring.

That leads in to the critical thing that's missing in most of these methods, comments... there's not a lot of useful ones in there. Your comments should be explaining what is happening in the code that couldn't be determined at first glance. The code really should be self-documenting. When it isn't, you need to say what it's doing in comments. But no one cares that the next line will add some item to a list. You should me saying things like, "we need to ensure we don't have an empty list because..." or at least explain why some actions are needed.

I did a lot more that I thought I would do but I would rewrite it more like this.

p.s., I don't know what your HTML would look like so I don't know how the nesting actually worked. But this should give you an idea how it could be better implemented (IMHO).

//Does this really need to create instances of this class?
public static class TocParserEx
{
    //Does this really need to be an instance method?
    public static string InsertToc(string html)
    {
        var doc = new HtmlDocument();
        doc.LoadHtml(html);

        //only place the TOC if there is a TOC section labeled
        var tocPlaceholder = doc.DocumentNode
            .DescendantNodes()
            .OfType<HtmlTextNode>()
            .Where(t => t.Text == "{TOC}")
            .FirstOrDefault();
        if (tocPlaceholder != null)
        {
            var newToc = HtmlNode.CreateNode(@"<div class=""toc"">
  <div class=""toc-title"">Contents [<a class=""toc-showhide"" href=""#"">hide</a>]</div>
  <div class=""toc-list""></div>
</div>");
            tocPlaceholder.ParentNode.ReplaceChild(newToc, tocPlaceholder);

            AddHeaderAnchors(doc.DocumentNode, Header.Root);
            AddTocEntries(Header.Root, newToc.Descendants("div").Last());
        }

        return doc.DocumentNode.WriteTo();
    }

    /// <summary>
    /// Adds anchors to headers found in the node to the parent header.
    /// </summary>
    /// <param name="root">The root node which contains the headers</param>
    /// <param name="parentHeader">The parent header</param>
    private static void AddHeaderAnchors(HtmlNode root, Header parentHeader)
    {
        // Find all child headers
        var headerName = "h" + (parentHeader.Level + 1);
        var headers = root.ChildNodes
            .Where(e => Header.IsHeader(e) && e.Name == headerName)
            .Select(e => Header.FromNode(e, parentHeader))
            .ToList();

        foreach (var header in headers)
        {
            var replacement = HtmlNode.CreateNode(String.Format("<a name=\"{0}\"/>", header.Id));

            //populate any subheaders
            AddHeaderAnchors(header.Node, header);

            //replace the found header with the wrapper
            header.Node.ParentNode.ReplaceChild(replacement, header.Node);
            replacement.AppendChild(header.Node);
        }
    }

    /// <summary>
    /// Adds the child headers to the TOC section.
    /// </summary>
    /// <param name="rootHeader">The header which contains the sections to be added</param>
    /// <param name="tocSection">The TOC section to add to</param>
    private static void AddTocEntries(Header rootHeader, HtmlNode tocSection)
    {
        var ul = tocSection.AppendChild(HtmlNode.CreateNode("<ul/>"));
        foreach (var header in rootHeader.Children)
        {
            var entry = ul.AppendChild(CreateTocEntry(header));

            if (header.Children.Any())
            {
                AddTocEntries(header, entry);
            }
        }
    }

    private static HtmlNode CreateTocEntry(Header header)
    {
        return HtmlNode.CreateNode(String.Format(@"<li>
  <a href=""#{0}"">{1}&nbsp;{2}</a>
</li>", header.Id, header.Section, header.Title));
    }
}

//this class really should be lightweight
public class Header
{
    public static Header Root { get { return _root; } }
    private static readonly Header _root = new Header();

    public string Title { get; private set; }
    public string Tag { get; private set; }
    public string Id { get; private set; }
    public int Level { get; private set; }
    public HtmlNode Node { get; private set; }
    public Header Parent { get; private set; }
    public ReadOnlyCollection<Header> Children { get { return _children.AsReadOnly(); } }
    public int EntryNumber { get; private set; }
    public string Section { get; private set; }

    private List<Header> _children;

    private Header() : this(HtmlNode.CreateNode("<h0/>"), null) { }
    private Header(HtmlNode node, Header parent)
    {
        Title = node.InnerText;
        Tag = node.Name;
        Id = EncodeTitle(Title) + ShortGuid.NewGuid();
        Level = Int32.Parse(Tag.Substring(1));
        Node = node;
        Parent = parent ?? _root;
        _children = new List<Header>();

        if (parent == null)
        {
            EntryNumber = 1;
            Section = "1";
        }
        else
        {
            parent._children.Add(this);
            EntryNumber = parent.Children.Count;
            Section = parent.Section + "." + EntryNumber;
        }
    }

    public static Header FromNode(HtmlNode node, Header parent)
    {
        if (parent == null)
            return _root;
        if (node == null)
            throw new ArgumentNullException("node");
        return new Header(node, parent);
    }

    public static bool IsHeader(HtmlNode node)
    {
        return System.Text.RegularExpressions.Regex.IsMatch(node.Name, @"h\d");
    }

    private static string EncodeTitle(string title)
    {
        //encode the title (whatever your logic is)
        return String.Concat(title.Where(Char.IsLetterOrDigit));
    }
}

And the "HTML" I tested it on:

<p>{TOC}</p>
<h1>This is a title!!!</h1>
<h1>Here's another title!!!</h1>

Generates something like this:

<p><div class="toc">
  <div class="toc-title">Contents [<a class="toc-showhide" href="#">hide</a>]</div>
  <div class="toc-list"><ul><li>
  <a href="#ThisisatitlefyxTAeHYp0y2KaQOvD89JA">1.1&nbsp;This is a title!!!</a>
</li><li>
  <a href="#HeresanothertitleD3FHM3IpO0OAuNRRtmS1vw">1.2&nbsp;Here's another title!!!</a>
</li></ul></div>
</div></p>
<a name="ThisisatitlefyxTAeHYp0y2KaQOvD89JA"><h1>This is a title!!!</h1></a>
<a name="HeresanothertitleD3FHM3IpO0OAuNRRtmS1vw"><h1>Here's another title!!!</h1></a>