") } @@ -404,22 +363,7 @@ func TestTableOfContentsWithCode(t *testing.T) { c.Assert(err, qt.IsNil) toc, ok := r.(converter.TableOfContentsProvider) c.Assert(ok, qt.Equals, true) - expected := tableofcontents.Root{ - Headings: tableofcontents.Headings{ - { - ID: "", - Text: "", - Headings: tableofcontents.Headings{ - { - ID: "_some_code_in_the_title", - Text: "Some code in the title", - Headings: nil, - }, - }, - }, - }, - } - c.Assert(toc.TableOfContents(), qt.DeepEquals, expected) + c.Assert(toc.TableOfContents().HeadingsMap["_some_code_in_the_title"].Title, qt.Equals, "Some code in the title") c.Assert(string(r.Bytes()), qt.Not(qt.Contains), "

") } @@ -443,21 +387,7 @@ func TestTableOfContentsPreserveTOC(t *testing.T) { c.Assert(err, qt.IsNil) toc, ok := r.(converter.TableOfContentsProvider) c.Assert(ok, qt.Equals, true) - expected := tableofcontents.Root{ - Headings: tableofcontents.Headings{ - { - ID: "", - Text: "", - Headings: tableofcontents.Headings{ - { - ID: "some-title", - Text: "Some title", - Headings: nil, - }, - }, - }, - }, - } - c.Assert(toc.TableOfContents(), qt.DeepEquals, expected) + + c.Assert(toc.TableOfContents().Identifiers, qt.DeepEquals, collections.SortedStringSlice{"some-title"}) c.Assert(string(r.Bytes()), qt.Contains, "

") } diff --git a/markup/converter/converter.go b/markup/converter/converter.go index c760381f4..7e5b56b07 100644 --- a/markup/converter/converter.go +++ b/markup/converter/converter.go @@ -101,7 +101,7 @@ type DocumentInfo interface { // TableOfContentsProvider provides the content as a ToC structure. type TableOfContentsProvider interface { - TableOfContents() tableofcontents.Root + TableOfContents() *tableofcontents.Fragments } // AnchorNameSanitizer tells how a converter sanitizes anchor names. diff --git a/markup/goldmark/convert.go b/markup/goldmark/convert.go index a179cd233..6c1c7ad0a 100644 --- a/markup/goldmark/convert.go +++ b/markup/goldmark/convert.go @@ -160,11 +160,11 @@ var _ identity.IdentitiesProvider = (*converterResult)(nil) type converterResult struct { converter.Result - toc tableofcontents.Root + toc *tableofcontents.Fragments ids identity.Identities } -func (c converterResult) TableOfContents() tableofcontents.Root { +func (c converterResult) TableOfContents() *tableofcontents.Fragments { return c.toc } @@ -228,9 +228,9 @@ type parserContext struct { parser.Context } -func (p *parserContext) TableOfContents() tableofcontents.Root { +func (p *parserContext) TableOfContents() *tableofcontents.Fragments { if v := p.Get(tocResultKey); v != nil { - return v.(tableofcontents.Root) + return v.(*tableofcontents.Fragments) } - return tableofcontents.Root{} + return nil } diff --git a/markup/goldmark/toc.go b/markup/goldmark/toc.go index 396c1d071..ac5040e85 100644 --- a/markup/goldmark/toc.go +++ b/markup/goldmark/toc.go @@ -41,8 +41,8 @@ func (t *tocTransformer) Transform(n *ast.Document, reader text.Reader, pc parse } var ( - toc tableofcontents.Root - tocHeading tableofcontents.Heading + toc tableofcontents.Builder + tocHeading = &tableofcontents.Heading{} level int row = -1 inHeading bool @@ -53,10 +53,10 @@ func (t *tocTransformer) Transform(n *ast.Document, reader text.Reader, pc parse s := ast.WalkStatus(ast.WalkContinue) if n.Kind() == ast.KindHeading { if inHeading && !entering { - tocHeading.Text = headingText.String() + tocHeading.Title = headingText.String() headingText.Reset() toc.AddAt(tocHeading, row, level-1) - tocHeading = tableofcontents.Heading{} + tocHeading = &tableofcontents.Heading{} inHeading = false return s, nil } @@ -106,7 +106,7 @@ func (t *tocTransformer) Transform(n *ast.Document, reader text.Reader, pc parse return s, nil }) - pc.Set(tocResultKey, toc) + pc.Set(tocResultKey, toc.Build()) } type tocExtension struct { diff --git a/markup/tableofcontents/tableofcontents.go b/markup/tableofcontents/tableofcontents.go index 2e7f47d20..bd0aaa801 100644 --- a/markup/tableofcontents/tableofcontents.go +++ b/markup/tableofcontents/tableofcontents.go @@ -14,35 +14,104 @@ package tableofcontents import ( + "sort" "strings" + + "github.com/gohugoio/hugo/common/collections" ) +// Empty is an empty ToC. +var Empty = &Fragments{ + Headings: Headings{}, + HeadingsMap: map[string]*Heading{}, +} + +// Builder is used to build the ToC data structure. +type Builder struct { + toc *Fragments +} + +// Add adds the heading to the ToC. +func (b *Builder) AddAt(h *Heading, row, level int) { + if b.toc == nil { + b.toc = &Fragments{} + } + b.toc.addAt(h, row, level) +} + +// Build returns the ToC. +func (b Builder) Build() *Fragments { + if b.toc == nil { + return Empty + } + b.toc.HeadingsMap = make(map[string]*Heading) + b.toc.walk(func(h *Heading) { + if h.ID != "" { + b.toc.HeadingsMap[h.ID] = h + b.toc.Identifiers = append(b.toc.Identifiers, h.ID) + } + }) + sort.Strings(b.toc.Identifiers) + return b.toc +} + // Headings holds the top level headings. -type Headings []Heading +type Headings []*Heading + +// FilterBy returns a new Headings slice with all headings that matches the given predicate. +// For internal use only. +func (h Headings) FilterBy(fn func(*Heading) bool) Headings { + var out Headings + + for _, h := range h { + h.walk(func(h *Heading) { + if fn(h) { + out = append(out, h) + } + }) + } + return out +} // Heading holds the data about a heading and its children. type Heading struct { - ID string - Text string + ID string + Title string Headings Headings } // IsZero is true when no ID or Text is set. func (h Heading) IsZero() bool { - return h.ID == "" && h.Text == "" + return h.ID == "" && h.Title == "" +} + +func (h *Heading) walk(fn func(*Heading)) { + fn(h) + for _, h := range h.Headings { + h.walk(fn) + } } -// Root implements AddAt, which can be used to build the -// data structure for the ToC. -type Root struct { +// Fragments holds the table of contents for a page. +type Fragments struct { + // Headings holds the top level headings. Headings Headings + + // Identifiers holds all the identifiers in the ToC as a sorted slice. + // Note that collections.SortedStringSlice has both a Contains and Count method + // that can be used to identify missing and duplicate IDs. + Identifiers collections.SortedStringSlice + + // HeadingsMap holds all the headings in the ToC as a map. + // Note that with duplicate IDs, the last one will win. + HeadingsMap map[string]*Heading } -// AddAt adds the heading into the given location. -func (toc *Root) AddAt(h Heading, row, level int) { +// addAt adds the heading into the given location. +func (toc *Fragments) addAt(h *Heading, row, level int) { for i := len(toc.Headings); i <= row; i++ { - toc.Headings = append(toc.Headings, Heading{}) + toc.Headings = append(toc.Headings, &Heading{}) } if level == 0 { @@ -50,19 +119,22 @@ func (toc *Root) AddAt(h Heading, row, level int) { return } - heading := &toc.Headings[row] + heading := toc.Headings[row] for i := 1; i < level; i++ { if len(heading.Headings) == 0 { - heading.Headings = append(heading.Headings, Heading{}) + heading.Headings = append(heading.Headings, &Heading{}) } - heading = &heading.Headings[len(heading.Headings)-1] + heading = heading.Headings[len(heading.Headings)-1] } heading.Headings = append(heading.Headings, h) } // ToHTML renders the ToC as HTML. -func (toc Root) ToHTML(startLevel, stopLevel int, ordered bool) string { +func (toc *Fragments) ToHTML(startLevel, stopLevel int, ordered bool) string { + if toc == nil { + return "" + } b := &tocBuilder{ s: strings.Builder{}, h: toc.Headings, @@ -74,6 +146,12 @@ func (toc Root) ToHTML(startLevel, stopLevel int, ordered bool) string { return b.s.String() } +func (toc Fragments) walk(fn func(*Heading)) { + for _, h := range toc.Headings { + h.walk(fn) + } +} + type tocBuilder struct { s strings.Builder h Headings @@ -133,11 +211,11 @@ func (b *tocBuilder) writeHeadings(level, indent int, h Headings) { } } -func (b *tocBuilder) writeHeading(level, indent int, h Heading) { +func (b *tocBuilder) writeHeading(level, indent int, h *Heading) { b.indent(indent) b.s.WriteString("

") if !h.IsZero() { - b.s.WriteString("" + h.Text + "") + b.s.WriteString("" + h.Title + "") } b.writeHeadings(level, indent, h.Headings) b.s.WriteString("

\n") diff --git a/markup/tableofcontents/tableofcontents_test.go b/markup/tableofcontents/tableofcontents_test.go index daeb9f991..adbda4b00 100644 --- a/markup/tableofcontents/tableofcontents_test.go +++ b/markup/tableofcontents/tableofcontents_test.go @@ -17,18 +17,33 @@ import ( "testing" qt "github.com/frankban/quicktest" + "github.com/gohugoio/hugo/common/collections" ) +var newTestTocBuilder = func() Builder { + var b Builder + b.AddAt(&Heading{Title: "Heading 1", ID: "h1-1"}, 0, 0) + b.AddAt(&Heading{Title: "1-H2-1", ID: "1-h2-1"}, 0, 1) + b.AddAt(&Heading{Title: "1-H2-2", ID: "1-h2-2"}, 0, 1) + b.AddAt(&Heading{Title: "1-H3-1", ID: "1-h2-2"}, 0, 2) + b.AddAt(&Heading{Title: "Heading 2", ID: "h1-2"}, 1, 0) + return b +} + +var newTestToc = func() *Fragments { + return newTestTocBuilder().Build() +} + func TestToc(t *testing.T) { c := qt.New(t) - toc := &Root{} + toc := &Fragments{} - toc.AddAt(Heading{Text: "Heading 1", ID: "h1-1"}, 0, 0) - toc.AddAt(Heading{Text: "1-H2-1", ID: "1-h2-1"}, 0, 1) - toc.AddAt(Heading{Text: "1-H2-2", ID: "1-h2-2"}, 0, 1) - toc.AddAt(Heading{Text: "1-H3-1", ID: "1-h2-2"}, 0, 2) - toc.AddAt(Heading{Text: "Heading 2", ID: "h1-2"}, 1, 0) + toc.addAt(&Heading{Title: "Heading 1", ID: "h1-1"}, 0, 0) + toc.addAt(&Heading{Title: "1-H2-1", ID: "1-h2-1"}, 0, 1) + toc.addAt(&Heading{Title: "1-H2-2", ID: "1-h2-2"}, 0, 1) + toc.addAt(&Heading{Title: "1-H3-1", ID: "1-h2-2"}, 0, 2) + toc.addAt(&Heading{Title: "Heading 2", ID: "h1-2"}, 1, 0) got := toc.ToHTML(1, -1, false) c.Assert(got, qt.Equals, `

@@ -97,11 +112,11 @@ func TestToc(t *testing.T) { func TestTocMissingParent(t *testing.T) { c := qt.New(t) - toc := &Root{} + toc := &Fragments{} - toc.AddAt(Heading{Text: "H2", ID: "h2"}, 0, 1) - toc.AddAt(Heading{Text: "H3", ID: "h3"}, 1, 2) - toc.AddAt(Heading{Text: "H3", ID: "h3"}, 1, 2) + toc.addAt(&Heading{Title: "H2", ID: "h2"}, 0, 1) + toc.addAt(&Heading{Title: "H3", ID: "h3"}, 1, 2) + toc.addAt(&Heading{Title: "H3", ID: "h3"}, 1, 2) got := toc.ToHTML(1, -1, false) c.Assert(got, qt.Equals, ``, qt.Commentf(got)) } + +func TestTocMisc(t *testing.T) { + c := qt.New(t) + + c.Run("Identifiers", func(c *qt.C) { + toc := newTestToc() + c.Assert(toc.Identifiers, qt.DeepEquals, collections.SortedStringSlice{"1-h2-1", "1-h2-2", "1-h2-2", "h1-1", "h1-2"}) + }) + + c.Run("HeadingsMap", func(c *qt.C) { + toc := newTestToc() + m := toc.HeadingsMap + c.Assert(m["h1-1"].Title, qt.Equals, "Heading 1") + c.Assert(m["doesnot exist"], qt.IsNil) + }) +} + +func BenchmarkToc(b *testing.B) { + + newTocs := func(n int) []*Fragments { + var tocs []*Fragments + for i := 0; i < n; i++ { + tocs = append(tocs, newTestToc()) + } + return tocs + } + + b.Run("Build", func(b *testing.B) { + var builders []Builder + for i := 0; i < b.N; i++ { + builders = append(builders, newTestTocBuilder()) + } + b.ResetTimer() + + for i := 0; i < b.N; i++ { + b := builders[i] + b.Build() + } + }) + + b.Run("ToHTML", func(b *testing.B) { + tocs := newTocs(b.N) + b.ResetTimer() + for i := 0; i < b.N; i++ { + toc := tocs[i] + toc.ToHTML(1, -1, false) + } + }) + +} -- cgit v1.2.3