// outline.go derives a document's heading structure from ALREADY-RENDERED,
// already-sanitized HTML, and gives every heading an anchor on the way
// past. It works on the output rather than on either parser because the
// two wiki formats disagree about headings: goldmark emits ids for
// markdown (WithAutoHeadingID), while Fossil wiki passes raw HTML
// through untouched, so `<h1>Cookbook</h1>` written by hand arrives with
// no id at all. Half of a fossil-born corpus is that second kind — 28 of
// fossil's own 83 wiki pages — and a page whose headings cannot be
// linked to cannot have a table of contents either.
package markup
import (
"html"
"regexp"
"strconv"
"strings"
)
// Heading is one entry in a document's outline.
type Heading struct {
Level int `json:"level"`
ID string `json:"id"`
Text string `json:"text"`
}
var (
// Opening tag only: Go's regexp is RE2 and has no backreference, so
// the closing tag is found by scanning for the level this one
// opened rather than by matching \1. That is the more honest read
// anyway — it cannot pair an <h2> with a stray </h3>.
headingOpen = regexp.MustCompile(`(?i)<h([1-6])([^>]*)>`)
idAttr = regexp.MustCompile(`(?i)\bid\s*=\s*"([^"]*)"`)
anyTag = regexp.MustCompile(`(?s)<[^>]*>`)
notSlug = regexp.MustCompile(`[^a-z0-9]+`)
)
// Outline returns h with every heading carrying an id, plus the outline
// those ids address. An id already present is kept: goldmark's slugs are
// what existing links point at, and rewriting them would break every
// deep link ever shared into a markdown page.
//
// Levels are reported as written. Callers decide which to show; this
// does not collapse or renumber them, because a document that opens at
// h3 is still a document with a shape.
func Outline(h []byte) ([]byte, []Heading) {
src := string(h)
// ASCII-only, because this string is indexed with offsets computed
// on src and the two must stay byte-for-byte aligned.
//
// strings.ToLower does not preserve length: it maps each rune to
// its lowercase rune, and some of those are wider or narrower in
// UTF-8. "Ⱥ" is two bytes and lowercases to three; "İ" is two and
// lowercases to one. A document containing either made lower a
// different length from src, every offset after it addressed a
// different byte in each, and the slice below eventually ran off
// the end -- a 500 for every reader of that page, which is how this
// was found: pkgsrc's own documentation, 545789 bytes, sliced to
// 546367.
//
// Nothing here needs Unicode folding. The only thing searched for
// is a closing heading tag, which is ASCII by definition.
lower := asciiLower(src)
var out []Heading
var b strings.Builder
b.Grow(len(src) + 256)
// One namespace for minted AND pre-existing ids, so a hand-written
// heading cannot be handed the slug goldmark already used above it.
seen := map[string]bool{}
for pos := 0; pos < len(src); {
loc := headingOpen.FindStringSubmatchIndex(src[pos:])
if loc == nil {
b.WriteString(src[pos:])
break
}
open, afterOpen := pos+loc[0], pos+loc[1]
level, _ := strconv.Atoi(src[pos+loc[2] : pos+loc[3]])
attrs := src[pos+loc[4] : pos+loc[5]]
shut := strings.Index(lower[afterOpen:], "</h"+strconv.Itoa(level))
if shut < 0 {
// An unclosed heading is not a heading we can address.
b.WriteString(src[pos:afterOpen])
pos = afterOpen
continue
}
inner := src[afterOpen : afterOpen+shut]
// The label is the heading's text with any markup inside it
// stripped: a heading may legitimately hold <code> or <em>, and
// a contents entry wants the words, not the tags.
text := strings.TrimSpace(html.UnescapeString(anyTag.ReplaceAllString(inner, "")))
b.WriteString(src[pos:open])
if got := idAttr.FindStringSubmatch(attrs); got != nil && got[1] != "" {
// An id already present is kept whatever else claims it:
// existing deep links point at it.
seen[got[1]] = true
out = append(out, Heading{Level: level, ID: got[1], Text: text})
b.WriteString(src[open:afterOpen])
} else {
id := uniqueID(slugify(text), seen)
seen[id] = true
out = append(out, Heading{Level: level, ID: id, Text: text})
b.WriteString("<h" + strconv.Itoa(level) + ` id="` + id + `"` + attrs + ">")
}
b.WriteString(inner)
pos = afterOpen + shut
}
return []byte(b.String()), out
}
// uniqueID suffixes until the slug is free, GitHub's -1, -2 convention.
func uniqueID(base string, seen map[string]bool) string {
if base == "" {
// A heading of punctuation, or an image alone, still needs a
// stable target to be linked by.
base = "section"
}
id := base
for n := 1; seen[id]; n++ {
id = base + "-" + strconv.Itoa(n)
}
return id
}
// slugify is GitHub's heading-anchor shape, which is also goldmark's, so
// a hand-written fossil heading and a markdown one of the same words
// address alike.
func slugify(s string) string {
s = strings.ToLower(strings.TrimSpace(s))
s = notSlug.ReplaceAllString(s, "-")
s = strings.Trim(s, "-")
if len(s) > 120 {
s = strings.Trim(s[:120], "-")
}
// The sanitizer's id pattern demands a leading alphanumeric, and a
// heading that begins with a digit-free symbol would otherwise mint
// an id the policy would reject on any later pass.
if s != "" && (s[0] < 'a' || s[0] > 'z') && (s[0] < '0' || s[0] > '9') {
s = "s" + s
}
return s
}
// asciiLower lowercases A-Z and leaves every other byte alone, so the
// result is the same length as the input and can be indexed with the
// same offsets. See Outline.
func asciiLower(s string) string {
var b []byte
for i := 0; i < len(s); i++ {
c := s[i]
if c >= 'A' && c <= 'Z' {
if b == nil {
b = []byte(s)
}
b[i] = c + ('a' - 'A')
}
}
if b == nil {
return s
}
return string(b)
}