Accidentally Quadratic

godoc is Go’s tool for extracting doc comments from source code and rendering HTML documentation (loosely parallel Java’s “javadoc”).

godoc processes Go struct definitions in two passes. First, it runs over the AST recursively building rendering documentation and declarations into a textual output buffer containing an HTML fragment. The walker for this pass is shared with the rest of godoc’s documentation rendering (so that e.g. top-level definitions and struct fields share the bulk of their rendering code).

Then, it performs a second pass, modifying the HTML to add anchors to field names, so that e.g. https://golang.org/pkg/net/http/#Response.Header links specifically to the Header field in the Response struct.

Unfortunately, previously, godoc implemented this with nested loops over the struct fields and over the rendered text:

for _, f := range st.Fields.List {
    foreachLine(buf.Bytes(), func(line []byte) {
        …
    }
}

Since each struct field added at least one line to the output, this turned into an O(n²) loop.

The fix walks the two lists sequentially, first building up a map of names that needs links, and then walking the text in a single pass, looking for lines that match any of the names.