package prosediff
import (
"fmt"
"hash/fnv"
"sort"
"strings"
"github.com/yuin/goldmark"
"github.com/yuin/goldmark/ast"
"github.com/yuin/goldmark/extension"
extast "github.com/yuin/goldmark/extension/ast"
"github.com/yuin/goldmark/text"
)
// BlockKind is the structural role of a block. It is part of a block's
// identity: a paragraph that becomes a list item is not a modified paragraph.
type BlockKind string
const (
KindFrontmatter BlockKind = "frontmatter"
KindHeading BlockKind = "heading"
KindParagraph BlockKind = "paragraph"
KindListItem BlockKind = "list_item"
KindCode BlockKind = "code"
KindTableHeader BlockKind = "table_header"
KindTableRow BlockKind = "table_row"
KindThematicBreak BlockKind = "rule"
KindHTML BlockKind = "html"
)
// Prose reports whether this kind diffs word-by-word. Everything else diffs
// line-by-line, which is the code-fence distinction the design calls for.
func (k BlockKind) Prose() bool {
switch k {
case KindCode, KindFrontmatter, KindHTML:
return false
}
return true
}
// Block is one addressable unit of a document: a paragraph, a heading, a
// single list item, a whole code fence, one table row.
//
// The tuple (HeadingPath, Kind, Ordinal, Hash) is deliberately the anchor
// tuple the design names for inline comments; nothing here is diff-only.
type Block struct {
Kind BlockKind
Ordinal int // 0-based position in the document
Level int // heading level, or list nesting depth for list items
QuoteDepth int // blockquote nesting, 0 outside any quote
HeadingPath []string // enclosing headings, outermost first
Text string // source text of the block, as written
Lines []string // source lines; the diff unit for non-prose kinds
Info string // code fence language, list marker, table column count
StartLine int // 1-based, inclusive
EndLine int // 1-based, inclusive
Hash string // structure + normalized content
}
// Empty reports whether the block carries no content at all.
func (b Block) Empty() bool { return strings.TrimSpace(b.Text) == "" }
// Label is a short human description, used by the text renderer and usable
// as-is by a future web layer.
func (b Block) Label() string {
s := string(b.Kind)
switch b.Kind {
case KindHeading:
s = fmt.Sprintf("h%d", b.Level)
case KindListItem:
if b.Level > 1 {
s = fmt.Sprintf("list item (depth %d)", b.Level)
} else {
s = "list item"
}
case KindCode:
if b.Info != "" {
s = "code:" + b.Info
}
}
if b.QuoteDepth > 0 {
s = strings.Repeat("quoted ", b.QuoteDepth) + s
}
return s
}
// Segment splits a markdown document into blocks in document order.
func Segment(src []byte) []Block {
body, fm, lineOffset := splitFrontmatter(src)
s := &segmenter{src: body, lineStarts: lineStarts(body), lineOffset: lineOffset}
if fm != nil {
s.blocks = append(s.blocks, finishBlock(Block{
Kind: KindFrontmatter,
Lines: fm,
Text: strings.Join(fm, "\n"),
StartLine: 1,
EndLine: len(fm),
}))
}
md := goldmark.New(goldmark.WithExtensions(extension.Table))
doc := md.Parser().Parse(text.NewReader(body))
s.walk(doc, ctx{})
for i := range s.blocks {
s.blocks[i].Ordinal = i
}
return s.blocks
}
// splitFrontmatter peels a leading YAML frontmatter fence off the document.
// goldmark would otherwise parse "---" as a thematic break and the keys as a
// paragraph, which diffs badly and is not what the block is.
func splitFrontmatter(src []byte) (body []byte, fm []string, lineOffset int) {
s := string(src)
// The opening fence must be a whole line. A document that is nothing but
// "---" used to be admitted here as well and then sliced at [4:] on three
// bytes; it is not frontmatter under any reading — there is no line after it
// to hold a key and no closing fence — it is a thematic break, and goldmark
// is left to say so.
if !strings.HasPrefix(s, "---\n") {
return src, nil, 0
}
rest := s[4:]
end := strings.Index(rest, "\n---")
if end < 0 {
return src, nil, 0
}
tail := rest[end+4:]
if tail != "" && !strings.HasPrefix(tail, "\n") {
return src, nil, 0
}
fm = strings.Split(s[:end+8], "\n")
if tail != "" {
tail = tail[1:]
}
return []byte(tail), fm, len(fm)
}
type ctx struct {
headings []string
quoteDepth int
listDepth int
marker string
}
type segmenter struct {
src []byte
lineStarts []int
lineOffset int
blocks []Block
// headingStack holds (level, text) of the currently open headings.
headingStack []headingEntry
// ruleFrom is the byte offset just past the last thematic break located —
// see thematicBreakLine, which has no other way to tell two adjacent rules
// apart.
ruleFrom int
}
type headingEntry struct {
level int
text string
}
func (s *segmenter) walk(n ast.Node, c ctx) {
for child := n.FirstChild(); child != nil; child = child.NextSibling() {
s.node(child, c)
}
}
func (s *segmenter) node(n ast.Node, c ctx) {
switch v := n.(type) {
case *ast.Heading:
txt := s.linesText(v.Lines())
start, end := s.segLines(v.Lines())
s.emit(Block{
Kind: KindHeading,
Level: v.Level,
QuoteDepth: c.quoteDepth,
HeadingPath: s.currentPath(),
Text: txt,
Lines: splitLines(txt),
StartLine: start,
EndLine: end,
})
s.pushHeading(v.Level, txt)
case *ast.Paragraph, *ast.TextBlock:
lines := n.Lines()
txt := s.linesText(lines)
if strings.TrimSpace(txt) == "" {
return
}
start, end := s.segLines(lines)
kind := KindParagraph
level := 0
if c.listDepth > 0 {
kind = KindListItem
level = c.listDepth
}
s.emit(Block{
Kind: kind,
Level: level,
QuoteDepth: c.quoteDepth,
HeadingPath: s.currentPath(),
Text: txt,
Lines: splitLines(txt),
Info: c.marker,
StartLine: start,
EndLine: end,
})
case *ast.FencedCodeBlock:
txt := s.linesText(v.Lines())
start, end := s.segLines(v.Lines())
info := ""
if v.Info != nil {
seg := v.Info.Segment
info = string(seg.Value(s.src))
}
s.emit(Block{
Kind: KindCode,
QuoteDepth: c.quoteDepth,
Level: c.listDepth,
HeadingPath: s.currentPath(),
Text: txt,
Lines: splitLines(txt),
Info: info,
StartLine: start,
EndLine: end,
})
case *ast.CodeBlock:
txt := s.linesText(v.Lines())
start, end := s.segLines(v.Lines())
s.emit(Block{
Kind: KindCode,
QuoteDepth: c.quoteDepth,
Level: c.listDepth,
HeadingPath: s.currentPath(),
Text: txt,
Lines: splitLines(txt),
Info: "indented",
StartLine: start,
EndLine: end,
})
case *ast.HTMLBlock:
txt := s.linesText(v.Lines())
start, end := s.segLines(v.Lines())
s.emit(Block{
Kind: KindHTML,
QuoteDepth: c.quoteDepth,
HeadingPath: s.currentPath(),
Text: txt,
Lines: splitLines(txt),
StartLine: start,
EndLine: end,
})
case *ast.ThematicBreak:
line := s.thematicBreakLine(n)
s.emit(Block{
Kind: KindThematicBreak,
QuoteDepth: c.quoteDepth,
HeadingPath: s.currentPath(),
Text: "---",
Lines: []string{"---"},
StartLine: line,
EndLine: line,
})
case *ast.List:
inner := c
inner.listDepth = c.listDepth + 1
inner.marker = string(rune(v.Marker))
if v.IsOrdered() {
inner.marker = "ordered"
}
s.walk(v, inner)
case *ast.ListItem:
s.walk(v, c)
case *ast.Blockquote:
inner := c
inner.quoteDepth = c.quoteDepth + 1
s.walk(v, inner)
case *extast.Table:
s.table(v, c)
default:
// Containers we do not model explicitly still get descended into,
// so no content is silently dropped.
if n.Type() == ast.TypeBlock && n.HasChildren() {
s.walk(n, c)
}
}
}
func (s *segmenter) table(t *extast.Table, c ctx) {
cols := len(t.Alignments)
for row := t.FirstChild(); row != nil; row = row.NextSibling() {
kind := KindTableRow
if row.Kind() == extast.KindTableHeader {
kind = KindTableHeader
}
start, stop := nodeSpan(row)
if start < 0 {
continue
}
txt := strings.TrimRight(s.sourceLineRange(start, stop), "\n")
line := s.lineOf(start)
s.emit(Block{
Kind: kind,
QuoteDepth: c.quoteDepth,
HeadingPath: s.currentPath(),
Text: txt,
Lines: splitLines(txt),
Info: fmt.Sprintf("%d cols", cols),
StartLine: line,
EndLine: s.lineOf(stop),
})
}
}
func (s *segmenter) emit(b Block) {
s.blocks = append(s.blocks, finishBlock(b))
}
// finishBlock computes the identity hash: structure plus normalized content.
// Prose normalizes through the tokenizer (so wrapping does not count); code
// and frontmatter keep their lines verbatim (so whitespace does count).
func finishBlock(b Block) Block {
h := fnv.New64a()
fmt.Fprintf(h, "%s\x00%d\x00%d\x00", b.Kind, b.Level, b.QuoteDepth)
if b.Kind.Prose() {
h.Write([]byte(Normalize(b.Text)))
} else {
h.Write([]byte(b.Info))
h.Write([]byte{0})
h.Write([]byte(strings.Join(b.Lines, "\n")))
}
b.Hash = fmt.Sprintf("%016x", h.Sum64())
return b
}
func (s *segmenter) pushHeading(level int, txt string) {
for len(s.headingStack) > 0 && s.headingStack[len(s.headingStack)-1].level >= level {
s.headingStack = s.headingStack[:len(s.headingStack)-1]
}
s.headingStack = append(s.headingStack, headingEntry{level: level, text: strings.TrimSpace(txt)})
}
func (s *segmenter) currentPath() []string {
if len(s.headingStack) == 0 {
return nil
}
out := make([]string, len(s.headingStack))
for i, e := range s.headingStack {
out[i] = e.text
}
return out
}
func (s *segmenter) linesText(segs *text.Segments) string {
if segs == nil || segs.Len() == 0 {
return ""
}
var sb strings.Builder
for i := 0; i < segs.Len(); i++ {
seg := segs.At(i)
sb.Write(seg.Value(s.src))
}
return strings.TrimRight(sb.String(), "\n")
}
func (s *segmenter) segLines(segs *text.Segments) (int, int) {
if segs == nil || segs.Len() == 0 {
return 0, 0
}
return s.lineOf(segs.At(0).Start), s.lineOf(segs.At(segs.Len()-1).Stop - 1)
}
// thematicBreakLine finds the source line a rule sits on.
//
// A thematic break is the one block with nothing in it: goldmark records no
// text segment and no line segment for it, because there is no text to record.
// nodeStart therefore answered 0 for every rule in a document, and every rule
// reported line 1 — harmless while the renderers printed no line numbers, and a
// lie the moment one of them did. Two rules in a document then also shared a
// number, which is the one thing a line-numbered view must never do.
//
// So the position is recovered from the source instead, bounded by the two
// neighbours that do carry offsets: the search starts after whatever the
// previous sibling covered and stops where the next one begins, and takes the
// first line in that window that is a rule. ruleFrom carries the floor forward
// across a run of consecutive rules, which have no offsets of their own to tell
// them apart.
//
// A rule the scan cannot place reports line 0, not line 1. A renderer shows an
// empty gutter cell for 0; showing 1 would invite a comment onto whatever is at
// the top of the document.
func (s *segmenter) thematicBreakLine(n ast.Node) int {
from := s.ruleFrom
if prev := n.PreviousSibling(); prev != nil {
if _, stop := nodeSpan(prev); stop > from {
from = stop
}
}
to := len(s.src)
if next := n.NextSibling(); next != nil {
if start, _ := nodeSpan(next); start >= 0 && start < to {
to = start
}
}
for i := sort.SearchInts(s.lineStarts, from+1) - 1; i >= 0 && i < len(s.lineStarts); i++ {
start := s.lineStarts[i]
if start > to {
break
}
stop := len(s.src)
if i+1 < len(s.lineStarts) {
stop = s.lineStarts[i+1] - 1
}
if !isThematicBreakLine(string(s.src[start:stop])) {
continue
}
// Past the newline, not at it: an offset inside a line resolves back to
// that same line, and the next rule would find this one again.
s.ruleFrom = stop + 1
return i + 1 + s.lineOffset
}
return 0
}
// isThematicBreakLine recognises the line goldmark has already decided is a
// rule: three or more of -, _ or * with only spaces between them, under any
// number of blockquote markers.
func isThematicBreakLine(line string) bool {
t := strings.TrimSpace(line)
for strings.HasPrefix(t, ">") {
t = strings.TrimSpace(t[1:])
}
if t == "" {
return false
}
c := t[0]
if c != '-' && c != '_' && c != '*' {
return false
}
n := 0
for i := 0; i < len(t); i++ {
switch t[i] {
case c:
n++
case ' ', '\t':
default:
return false
}
}
return n >= 3
}
// sourceLineRange expands a byte span to whole source lines, which is how a
// table row (whose AST node carries only inline segments) recovers the pipe
// syntax the reviewer actually wrote.
func (s *segmenter) sourceLineRange(start, stop int) string {
if start < 0 || stop > len(s.src) || start > stop {
return ""
}
for start > 0 && s.src[start-1] != '\n' {
start--
}
for stop < len(s.src) && s.src[stop] != '\n' {
stop++
}
return string(s.src[start:stop])
}
func (s *segmenter) lineOf(off int) int {
i := sort.SearchInts(s.lineStarts, off+1) - 1
if i < 0 {
i = 0
}
return i + 1 + s.lineOffset
}
func lineStarts(src []byte) []int {
out := []int{0}
for i, c := range src {
if c == '\n' {
out = append(out, i+1)
}
}
return out
}
func splitLines(s string) []string {
if s == "" {
return nil
}
return strings.Split(s, "\n")
}
// nodeSpan returns the byte range covered by a node's descendant text
// segments, or (-1, -1) when the node carries none.
func nodeSpan(n ast.Node) (int, int) {
start, stop := -1, -1
consider := func(a, b int) {
if start < 0 || a < start {
start = a
}
if b > stop {
stop = b
}
}
var visit func(ast.Node)
visit = func(n ast.Node) {
if t, ok := n.(*ast.Text); ok {
consider(t.Segment.Start, t.Segment.Stop)
}
// Lines() panics on inline nodes, so it is only asked of blocks.
if n.Type() == ast.TypeBlock {
if lines := n.Lines(); lines != nil && lines.Len() > 0 {
consider(lines.At(0).Start, lines.At(lines.Len()-1).Stop)
}
}
for c := n.FirstChild(); c != nil; c = c.NextSibling() {
visit(c)
}
}
visit(n)
return start, stop
}
func nodeStart(n ast.Node) int {
start, _ := nodeSpan(n)
if start < 0 {
return 0
}
return start
}