| 1 |
|
package prosediff |
| 2 |
|
|
| 3 |
|
import "strings" |
| 4 |
|
|
| 5 |
|
// LineWords is one source line of a modified block, with the part of the |
| 6 |
|
// block's word edit script that falls on it. |
| 7 |
|
type LineWords struct { |
| 8 |
|
// Line is the 1-based source line number, in the revision this side of the |
| 9 |
|
// diff came from. |
| 10 |
|
Line int |
| 11 |
|
// Spans is the slice of the block's edit script covering this line. A span |
| 12 |
|
// that straddled a line break is split, so every span here belongs wholly |
| 13 |
|
// to this line. |
| 14 |
|
Spans []Span |
| 15 |
|
} |
| 16 |
|
|
| 17 |
|
// WordsByLine attributes a modified block's word-level edit script to the |
| 18 |
|
// source lines it came from: the old side keeps equal and deleted runs, the new |
| 19 |
|
// side keeps equal and inserted ones. |
| 20 |
|
// |
| 21 |
|
// A word diff has no line information in it, and that is deliberate. [Tokenize] |
| 22 |
|
// drops whitespace — "\n" and " " both collapse to Token.Space — which is what |
| 23 |
|
// makes a rewrapped paragraph produce a byte-identical token stream and |
| 24 |
|
// therefore no diff at all. The cost of that property is this function: to draw |
| 25 |
|
// a line-numbered diff, the line each word sat on has to be recovered rather |
| 26 |
|
// than read off. |
| 27 |
|
// |
| 28 |
|
// It is recoverable because the script is ordered. The spans carrying equal and |
| 29 |
|
// deleted text reproduce the old block's tokens in sequence, and the equal and |
| 30 |
|
// inserted ones reproduce the new block's; walking each side in step with that |
| 31 |
|
// side's re-tokenized lines says which line every token belongs to. |
| 32 |
|
// |
| 33 |
|
// ok is false when a side's lines do not tokenize to the same sequence length |
| 34 |
|
// the script consumed. That means the block's Lines and Text disagree, and the |
| 35 |
|
// caller should fall back to rendering the block as one old/new pair labelled |
| 36 |
|
// by line range — a wrong line number is worse than an honest range, because it |
| 37 |
|
// invites a comment onto text that was never there. |
| 38 |
8 |
func WordsByLine(c BlockChange) (old, nw []LineWords, ok bool) { |
| 39 |
8 |
if c.Kind != ChangeModify || len(c.Words) == 0 || c.Old == nil || c.New == nil { |
| 40 |
3 |
return nil, nil, false |
| 41 |
3 |
} |
| 42 |
5 |
old, ok = spread(c.Old, c.Words, OpDelete) |
| 43 |
5 |
if !ok { |
| 44 |
0 |
return nil, nil, false |
| 45 |
0 |
} |
| 46 |
5 |
nw, ok = spread(c.New, c.Words, OpInsert) |
| 47 |
5 |
if !ok { |
| 48 |
0 |
return nil, nil, false |
| 49 |
0 |
} |
| 50 |
5 |
return old, nw, true |
| 51 |
|
} |
| 52 |
|
|
| 53 |
|
// spread walks one side of the edit script — the equal runs plus the runs of |
| 54 |
|
// side (OpDelete for the old side, OpInsert for the new) — and re-cuts it along |
| 55 |
|
// the block's own lines. |
| 56 |
|
// |
| 57 |
|
// The script supplies only the operation per token; the text and its spacing |
| 58 |
|
// come from re-tokenizing each source line. Taking the text from the spans |
| 59 |
|
// instead would drop separators: Span.Space is false on an insertion that |
| 60 |
|
// directly replaces a deletion, because in a combined rendering the deletion |
| 61 |
|
// before it already carried the space. Split onto one side that deletion is |
| 62 |
|
// gone, and "delta CHANGED zeta" renders as "deltaCHANGED zeta". The line's own |
| 63 |
|
// tokens carry the spacing that was actually written, so they are the authority. |
| 64 |
10 |
func spread(blk *Block, script []Span, side Op) ([]LineWords, bool) { |
| 65 |
10 |
// One op per token of this side, in order. |
| 66 |
10 |
var ops []Op |
| 67 |
42 |
for _, sp := range script { |
| 68 |
42 |
if sp.Op != OpEqual && sp.Op != side { |
| 69 |
12 |
continue |
| 70 |
|
} |
| 71 |
86 |
for range Tokenize(sp.Text) { |
| 72 |
86 |
ops = append(ops, sp.Op) |
| 73 |
86 |
} |
| 74 |
|
} |
| 75 |
|
|
| 76 |
10 |
out := make([]LineWords, len(blk.Lines)) |
| 77 |
10 |
at := 0 |
| 78 |
26 |
for i, ln := range blk.Lines { |
| 79 |
26 |
out[i] = LineWords{Line: blk.StartLine + i} |
| 80 |
26 |
toks := Tokenize(ln) |
| 81 |
46 |
for j := 0; j < len(toks); { |
| 82 |
46 |
if at >= len(ops) { |
| 83 |
0 |
return nil, false // the lines hold more tokens than the script |
| 84 |
0 |
} |
| 85 |
|
// Group the run of following tokens sharing this token's op. |
| 86 |
46 |
op, k := ops[at], j |
| 87 |
86 |
for k < len(toks) && at+(k-j) < len(ops) && ops[at+(k-j)] == op { |
| 88 |
86 |
k++ |
| 89 |
86 |
} |
| 90 |
46 |
out[i].Spans = append(out[i].Spans, Span{ |
| 91 |
46 |
Op: op, |
| 92 |
46 |
Text: joinTokens(toks[j:k]), |
| 93 |
46 |
Space: toks[j].Space, |
| 94 |
46 |
}) |
| 95 |
46 |
at += k - j |
| 96 |
46 |
j = k |
| 97 |
|
} |
| 98 |
|
} |
| 99 |
10 |
if at != len(ops) { |
| 100 |
0 |
return nil, false // the script holds more tokens than the lines |
| 101 |
0 |
} |
| 102 |
10 |
return out, true |
| 103 |
|
} |
| 104 |
|
|
| 105 |
|
// joinTokens rebuilds text from a run of tokens, restoring the single space |
| 106 |
|
// each token records as having preceded it. |
| 107 |
46 |
func joinTokens(toks []Token) string { |
| 108 |
46 |
var b strings.Builder |
| 109 |
86 |
for i, t := range toks { |
| 110 |
86 |
if i > 0 && t.Space { |
| 111 |
40 |
b.WriteByte(' ') |
| 112 |
40 |
} |
| 113 |
86 |
b.WriteString(t.Text) |
| 114 |
|
} |
| 115 |
46 |
return b.String() |
| 116 |
|
} |