coverage — ~bigbes/sr-ht-spec — 3cb1c03d — prosediff/segment.go

Coverage
87.4% 174/199 statements
Δ
—
Blob
8b38166
Uncovered L62L133-L134L194-L195L235-L248L250-L261L280-L281L295-L300L313L371-L372L383-L384L424L438L462-L463L474-L475L488-L489L505-L506L541-L546
1 package prosediff
2
3 import (
4 "fmt"
5 "hash/fnv"
6 "sort"
7 "strings"
8
9 "github.com/yuin/goldmark"
10 "github.com/yuin/goldmark/ast"
11 "github.com/yuin/goldmark/extension"
12 extast "github.com/yuin/goldmark/extension/ast"
13 "github.com/yuin/goldmark/text"
14 )
15
16 // BlockKind is the structural role of a block. It is part of a block's
17 // identity: a paragraph that becomes a list item is not a modified paragraph.
18 type BlockKind string
19
20 const (
21 KindFrontmatter BlockKind = "frontmatter"
22 KindHeading BlockKind = "heading"
23 KindParagraph BlockKind = "paragraph"
24 KindListItem BlockKind = "list_item"
25 KindCode BlockKind = "code"
26 KindTableHeader BlockKind = "table_header"
27 KindTableRow BlockKind = "table_row"
28 KindThematicBreak BlockKind = "rule"
29 KindHTML BlockKind = "html"
30 )
31
32 // Prose reports whether this kind diffs word-by-word. Everything else diffs
33 // line-by-line, which is the code-fence distinction the design calls for.
34 301 func (k BlockKind) Prose() bool {
35 301 switch k {
36 34 case KindCode, KindFrontmatter, KindHTML:
37 34 return false
38 }
39 267 return true
40 }
41
42 // Block is one addressable unit of a document: a paragraph, a heading, a
43 // single list item, a whole code fence, one table row.
44 //
45 // The tuple (HeadingPath, Kind, Ordinal, Hash) is deliberately the anchor
46 // tuple the design names for inline comments; nothing here is diff-only.
47 type Block struct {
48 Kind BlockKind
49 Ordinal int // 0-based position in the document
50 Level int // heading level, or list nesting depth for list items
51 QuoteDepth int // blockquote nesting, 0 outside any quote
52 HeadingPath []string // enclosing headings, outermost first
53 Text string // source text of the block, as written
54 Lines []string // source lines; the diff unit for non-prose kinds
55 Info string // code fence language, list marker, table column count
56 StartLine int // 1-based, inclusive
57 EndLine int // 1-based, inclusive
58 Hash string // structure + normalized content
59 }
60
61 // Empty reports whether the block carries no content at all.
62 0 func (b Block) Empty() bool { return strings.TrimSpace(b.Text) == "" }
63
64 // Label is a short human description, used by the text renderer and usable
65 // as-is by a future web layer.
66 47 func (b Block) Label() string {
67 47 s := string(b.Kind)
68 47 switch b.Kind {
69 16 case KindHeading:
70 16 s = fmt.Sprintf("h%d", b.Level)
71 5 case KindListItem:
72 5 if b.Level > 1 {
73 2 s = fmt.Sprintf("list item (depth %d)", b.Level)
74 3 } else {
75 3 s = "list item"
76 3 }
77 4 case KindCode:
78 4 if b.Info != "" {
79 4 s = "code:" + b.Info
80 4 }
81 }
82 47 if b.QuoteDepth > 0 {
83 1 s = strings.Repeat("quoted ", b.QuoteDepth) + s
84 1 }
85 47 return s
86 }
87
88 // Segment splits a markdown document into blocks in document order.
89 89 func Segment(src []byte) []Block {
90 89 body, fm, lineOffset := splitFrontmatter(src)
91 89
92 89 s := &segmenter{src: body, lineStarts: lineStarts(body), lineOffset: lineOffset}
93 89 if fm != nil {
94 5 s.blocks = append(s.blocks, finishBlock(Block{
95 5 Kind: KindFrontmatter,
96 5 Lines: fm,
97 5 Text: strings.Join(fm, "\n"),
98 5 StartLine: 1,
99 5 EndLine: len(fm),
100 5 }))
101 5 }
102
103 89 md := goldmark.New(goldmark.WithExtensions(extension.Table))
104 89 doc := md.Parser().Parse(text.NewReader(body))
105 89 s.walk(doc, ctx{})
106 89
107 219 for i := range s.blocks {
108 219 s.blocks[i].Ordinal = i
109 219 }
110 89 return s.blocks
111 }
112
113 // splitFrontmatter peels a leading YAML frontmatter fence off the document.
114 // goldmark would otherwise parse "---" as a thematic break and the keys as a
115 // paragraph, which diffs badly and is not what the block is.
116 89 func splitFrontmatter(src []byte) (body []byte, fm []string, lineOffset int) {
117 89 s := string(src)
118 89 // The opening fence must be a whole line. A document that is nothing but
119 89 // "---" used to be admitted here as well and then sliced at [4:] on three
120 89 // bytes; it is not frontmatter under any reading — there is no line after it
121 89 // to hold a key and no closing fence — it is a thematic break, and goldmark
122 89 // is left to say so.
123 89 if !strings.HasPrefix(s, "---\n") {
124 83 return src, nil, 0
125 83 }
126 6 rest := s[4:]
127 6 end := strings.Index(rest, "\n---")
128 6 if end < 0 {
129 1 return src, nil, 0
130 1 }
131 5 tail := rest[end+4:]
132 5 if tail != "" && !strings.HasPrefix(tail, "\n") {
133 0 return src, nil, 0
134 0 }
135 5 fm = strings.Split(s[:end+8], "\n")
136 5 if tail != "" {
137 5 tail = tail[1:]
138 5 }
139 5 return []byte(tail), fm, len(fm)
140 }
141
142 type ctx struct {
143 headings []string
144 quoteDepth int
145 listDepth int
146 marker string
147 }
148
149 type segmenter struct {
150 src []byte
151 lineStarts []int
152 lineOffset int
153 blocks []Block
154 // headingStack holds (level, text) of the currently open headings.
155 headingStack []headingEntry
156 // ruleFrom is the byte offset just past the last thematic break located —
157 // see thematicBreakLine, which has no other way to tell two adjacent rules
158 // apart.
159 ruleFrom int
160 }
161
162 type headingEntry struct {
163 level int
164 text string
165 }
166
167 130 func (s *segmenter) walk(n ast.Node, c ctx) {
168 244 for child := n.FirstChild(); child != nil; child = child.NextSibling() {
169 244 s.node(child, c)
170 244 }
171 }
172
173 244 func (s *segmenter) node(n ast.Node, c ctx) {
174 244 switch v := n.(type) {
175 51 case *ast.Heading:
176 51 txt := s.linesText(v.Lines())
177 51 start, end := s.segLines(v.Lines())
178 51 s.emit(Block{
179 51 Kind: KindHeading,
180 51 Level: v.Level,
181 51 QuoteDepth: c.quoteDepth,
182 51 HeadingPath: s.currentPath(),
183 51 Text: txt,
184 51 Lines: splitLines(txt),
185 51 StartLine: start,
186 51 EndLine: end,
187 51 })
188 51 s.pushHeading(v.Level, txt)
189
190 121 case *ast.Paragraph, *ast.TextBlock:
191 121 lines := n.Lines()
192 121 txt := s.linesText(lines)
193 121 if strings.TrimSpace(txt) == "" {
194 0 return
195 0 }
196 121 start, end := s.segLines(lines)
197 121 kind := KindParagraph
198 121 level := 0
199 121 if c.listDepth > 0 {
200 23 kind = KindListItem
201 23 level = c.listDepth
202 23 }
203 121 s.emit(Block{
204 121 Kind: kind,
205 121 Level: level,
206 121 QuoteDepth: c.quoteDepth,
207 121 HeadingPath: s.currentPath(),
208 121 Text: txt,
209 121 Lines: splitLines(txt),
210 121 Info: c.marker,
211 121 StartLine: start,
212 121 EndLine: end,
213 121 })
214
215 13 case *ast.FencedCodeBlock:
216 13 txt := s.linesText(v.Lines())
217 13 start, end := s.segLines(v.Lines())
218 13 info := ""
219 13 if v.Info != nil {
220 10 seg := v.Info.Segment
221 10 info = string(seg.Value(s.src))
222 10 }
223 13 s.emit(Block{
224 13 Kind: KindCode,
225 13 QuoteDepth: c.quoteDepth,
226 13 Level: c.listDepth,
227 13 HeadingPath: s.currentPath(),
228 13 Text: txt,
229 13 Lines: splitLines(txt),
230 13 Info: info,
231 13 StartLine: start,
232 13 EndLine: end,
233 13 })
234
235 0 case *ast.CodeBlock:
236 0 txt := s.linesText(v.Lines())
237 0 start, end := s.segLines(v.Lines())
238 0 s.emit(Block{
239 0 Kind: KindCode,
240 0 QuoteDepth: c.quoteDepth,
241 0 Level: c.listDepth,
242 0 HeadingPath: s.currentPath(),
243 0 Text: txt,
244 0 Lines: splitLines(txt),
245 0 Info: "indented",
246 0 StartLine: start,
247 0 EndLine: end,
248 0 })
249
250 0 case *ast.HTMLBlock:
251 0 txt := s.linesText(v.Lines())
252 0 start, end := s.segLines(v.Lines())
253 0 s.emit(Block{
254 0 Kind: KindHTML,
255 0 QuoteDepth: c.quoteDepth,
256 0 HeadingPath: s.currentPath(),
257 0 Text: txt,
258 0 Lines: splitLines(txt),
259 0 StartLine: start,
260 0 EndLine: end,
261 0 })
262
263 11 case *ast.ThematicBreak:
264 11 line := s.thematicBreakLine(n)
265 11 s.emit(Block{
266 11 Kind: KindThematicBreak,
267 11 QuoteDepth: c.quoteDepth,
268 11 HeadingPath: s.currentPath(),
269 11 Text: "---",
270 11 Lines: []string{"---"},
271 11 StartLine: line,
272 11 EndLine: line,
273 11 })
274
275 12 case *ast.List:
276 12 inner := c
277 12 inner.listDepth = c.listDepth + 1
278 12 inner.marker = string(rune(v.Marker))
279 12 if v.IsOrdered() {
280 0 inner.marker = "ordered"
281 0 }
282 12 s.walk(v, inner)
283
284 23 case *ast.ListItem:
285 23 s.walk(v, c)
286
287 6 case *ast.Blockquote:
288 6 inner := c
289 6 inner.quoteDepth = c.quoteDepth + 1
290 6 s.walk(v, inner)
291
292 7 case *extast.Table:
293 7 s.table(v, c)
294
295 0 default:
296 0 // Containers we do not model explicitly still get descended into,
297 0 // so no content is silently dropped.
298 0 if n.Type() == ast.TypeBlock && n.HasChildren() {
299 0 s.walk(n, c)
300 0 }
301 }
302 }
303
304 7 func (s *segmenter) table(t *extast.Table, c ctx) {
305 7 cols := len(t.Alignments)
306 18 for row := t.FirstChild(); row != nil; row = row.NextSibling() {
307 18 kind := KindTableRow
308 18 if row.Kind() == extast.KindTableHeader {
309 7 kind = KindTableHeader
310 7 }
311 18 start, stop := nodeSpan(row)
312 18 if start < 0 {
313 0 continue
314 }
315 18 txt := strings.TrimRight(s.sourceLineRange(start, stop), "\n")
316 18 line := s.lineOf(start)
317 18 s.emit(Block{
318 18 Kind: kind,
319 18 QuoteDepth: c.quoteDepth,
320 18 HeadingPath: s.currentPath(),
321 18 Text: txt,
322 18 Lines: splitLines(txt),
323 18 Info: fmt.Sprintf("%d cols", cols),
324 18 StartLine: line,
325 18 EndLine: s.lineOf(stop),
326 18 })
327 }
328 }
329
330 214 func (s *segmenter) emit(b Block) {
331 214 s.blocks = append(s.blocks, finishBlock(b))
332 214 }
333
334 // finishBlock computes the identity hash: structure plus normalized content.
335 // Prose normalizes through the tokenizer (so wrapping does not count); code
336 // and frontmatter keep their lines verbatim (so whitespace does count).
337 219 func finishBlock(b Block) Block {
338 219 h := fnv.New64a()
339 219 fmt.Fprintf(h, "%s\x00%d\x00%d\x00", b.Kind, b.Level, b.QuoteDepth)
340 219 if b.Kind.Prose() {
341 201 h.Write([]byte(Normalize(b.Text)))
342 201 } else {
343 18 h.Write([]byte(b.Info))
344 18 h.Write([]byte{0})
345 18 h.Write([]byte(strings.Join(b.Lines, "\n")))
346 18 }
347 219 b.Hash = fmt.Sprintf("%016x", h.Sum64())
348 219 return b
349 }
350
351 51 func (s *segmenter) pushHeading(level int, txt string) {
352 51 for len(s.headingStack) > 0 && s.headingStack[len(s.headingStack)-1].level >= level {
353 6 s.headingStack = s.headingStack[:len(s.headingStack)-1]
354 6 }
355 51 s.headingStack = append(s.headingStack, headingEntry{level: level, text: strings.TrimSpace(txt)})
356 }
357
358 214 func (s *segmenter) currentPath() []string {
359 214 if len(s.headingStack) == 0 {
360 123 return nil
361 123 }
362 91 out := make([]string, len(s.headingStack))
363 119 for i, e := range s.headingStack {
364 119 out[i] = e.text
365 119 }
366 91 return out
367 }
368
369 185 func (s *segmenter) linesText(segs *text.Segments) string {
370 185 if segs == nil || segs.Len() == 0 {
371 0 return ""
372 0 }
373 185 var sb strings.Builder
374 231 for i := 0; i < segs.Len(); i++ {
375 231 seg := segs.At(i)
376 231 sb.Write(seg.Value(s.src))
377 231 }
378 185 return strings.TrimRight(sb.String(), "\n")
379 }
380
381 185 func (s *segmenter) segLines(segs *text.Segments) (int, int) {
382 185 if segs == nil || segs.Len() == 0 {
383 0 return 0, 0
384 0 }
385 185 return s.lineOf(segs.At(0).Start), s.lineOf(segs.At(segs.Len()-1).Stop - 1)
386 }
387
388 // thematicBreakLine finds the source line a rule sits on.
389 //
390 // A thematic break is the one block with nothing in it: goldmark records no
391 // text segment and no line segment for it, because there is no text to record.
392 // nodeStart therefore answered 0 for every rule in a document, and every rule
393 // reported line 1 — harmless while the renderers printed no line numbers, and a
394 // lie the moment one of them did. Two rules in a document then also shared a
395 // number, which is the one thing a line-numbered view must never do.
396 //
397 // So the position is recovered from the source instead, bounded by the two
398 // neighbours that do carry offsets: the search starts after whatever the
399 // previous sibling covered and stops where the next one begins, and takes the
400 // first line in that window that is a rule. ruleFrom carries the floor forward
401 // across a run of consecutive rules, which have no offsets of their own to tell
402 // them apart.
403 //
404 // A rule the scan cannot place reports line 0, not line 1. A renderer shows an
405 // empty gutter cell for 0; showing 1 would invite a comment onto whatever is at
406 // the top of the document.
407 11 func (s *segmenter) thematicBreakLine(n ast.Node) int {
408 11 from := s.ruleFrom
409 11 if prev := n.PreviousSibling(); prev != nil {
410 8 if _, stop := nodeSpan(prev); stop > from {
411 6 from = stop
412 6 }
413 }
414 11 to := len(s.src)
415 11 if next := n.NextSibling(); next != nil {
416 5 if start, _ := nodeSpan(next); start >= 0 && start < to {
417 3 to = start
418 3 }
419 }
420
421 25 for i := sort.SearchInts(s.lineStarts, from+1) - 1; i >= 0 && i < len(s.lineStarts); i++ {
422 25 start := s.lineStarts[i]
423 25 if start > to {
424 0 break
425 }
426 25 stop := len(s.src)
427 25 if i+1 < len(s.lineStarts) {
428 23 stop = s.lineStarts[i+1] - 1
429 23 }
430 25 if !isThematicBreakLine(string(s.src[start:stop])) {
431 14 continue
432 }
433 // Past the newline, not at it: an offset inside a line resolves back to
434 // that same line, and the next rule would find this one again.
435 11 s.ruleFrom = stop + 1
436 11 return i + 1 + s.lineOffset
437 }
438 0 return 0
439 }
440
441 // isThematicBreakLine recognises the line goldmark has already decided is a
442 // rule: three or more of -, _ or * with only spaces between them, under any
443 // number of blockquote markers.
444 25 func isThematicBreakLine(line string) bool {
445 25 t := strings.TrimSpace(line)
446 25 for strings.HasPrefix(t, ">") {
447 3 t = strings.TrimSpace(t[1:])
448 3 }
449 25 if t == "" {
450 8 return false
451 8 }
452 17 c := t[0]
453 17 if c != '-' && c != '_' && c != '*' {
454 6 return false
455 6 }
456 11 n := 0
457 34 for i := 0; i < len(t); i++ {
458 34 switch t[i] {
459 34 case c:
460 34 n++
461 case ' ', '\t':
462 0 default:
463 0 return false
464 }
465 }
466 11 return n >= 3
467 }
468
469 // sourceLineRange expands a byte span to whole source lines, which is how a
470 // table row (whose AST node carries only inline segments) recovers the pipe
471 // syntax the reviewer actually wrote.
472 18 func (s *segmenter) sourceLineRange(start, stop int) string {
473 18 if start < 0 || stop > len(s.src) || start > stop {
474 0 return ""
475 0 }
476 36 for start > 0 && s.src[start-1] != '\n' {
477 36 start--
478 36 }
479 36 for stop < len(s.src) && s.src[stop] != '\n' {
480 36 stop++
481 36 }
482 18 return string(s.src[start:stop])
483 }
484
485 406 func (s *segmenter) lineOf(off int) int {
486 406 i := sort.SearchInts(s.lineStarts, off+1) - 1
487 406 if i < 0 {
488 0 i = 0
489 0 }
490 406 return i + 1 + s.lineOffset
491 }
492
493 89 func lineStarts(src []byte) []int {
494 89 out := []int{0}
495 5517 for i, c := range src {
496 5517 if c == '\n' {
497 398 out = append(out, i+1)
498 398 }
499 }
500 89 return out
501 }
502
503 203 func splitLines(s string) []string {
504 203 if s == "" {
505 0 return nil
506 0 }
507 203 return strings.Split(s, "\n")
508 }
509
510 // nodeSpan returns the byte range covered by a node's descendant text
511 // segments, or (-1, -1) when the node carries none.
512 31 func nodeSpan(n ast.Node) (int, int) {
513 31 start, stop := -1, -1
514 90 consider := func(a, b int) {
515 90 if start < 0 || a < start {
516 27 start = a
517 27 }
518 90 if b > stop {
519 45 stop = b
520 45 }
521 }
522 31 var visit func(ast.Node)
523 114 visit = func(n ast.Node) {
524 114 if t, ok := n.(*ast.Text); ok {
525 45 consider(t.Segment.Start, t.Segment.Stop)
526 45 }
527 // Lines() panics on inline nodes, so it is only asked of blocks.
528 114 if n.Type() == ast.TypeBlock {
529 69 if lines := n.Lines(); lines != nil && lines.Len() > 0 {
530 45 consider(lines.At(0).Start, lines.At(lines.Len()-1).Stop)
531 45 }
532 }
533 114 for c := n.FirstChild(); c != nil; c = c.NextSibling() {
534 83 visit(c)
535 83 }
536 }
537 31 visit(n)
538 31 return start, stop
539 }
540
541 0 func nodeStart(n ast.Node) int {
542 0 start, _ := nodeSpan(n)
543 0 if start < 0 {
544 0 return 0
545 0 }
546 0 return start
547 }