1package diff23import (4 "encoding/json"5 "fmt"6 "strings"7)89// A notebook tab keeps its cells in the file as a list, each with its10// source and what its last run left (see docs/files/format.md). Cells11// have no names of their own to match them by, so comparing lines them12// up by their sources, and merging treats the list of sources as one13// part, whose outputs follow the side it's taken from.1415// KindNotebook is a Change to a notebook tab's cell: its source, or16// what its last run left.17const KindNotebook = "notebook"1819// nbCell is a notebook cell as the file has it.20type nbCell struct {21 raw json.RawMessage22 fields map[string]json.RawMessage23 source string24}2526func nbCells(raw json.RawMessage) []nbCell {27 var list []json.RawMessage28 json.Unmarshal(raw, &list)29 out := make([]nbCell, len(list))30 for i, e := range list {31 out[i].raw = compact(e)32 out[i].fields, _ = object(e)33 json.Unmarshal(out[i].fields["source"], &out[i].source)34 }35 return out36}3738// sources is the part of a notebook merging compares: each cell's kind39// and source, without the outputs runs leave.40func sources(raw json.RawMessage) json.RawMessage {41 if raw == nil {42 return nil43 }44 var parts []string45 for _, c := range nbCells(raw) {46 parts = append(parts, string(c.fields["kind"])+" "+c.source)47 }48 out, _ := json.Marshal(parts)49 return out50}5152// notebookChanges compares two notebooks' cells: those whose sources53// match, in order, by what their runs left; the others as sources54// changed, added or removed.55func notebookChanges(sheetName string, a, b json.RawMessage) []Change {56 ca, cb := nbCells(a), nbCells(b)57 var out []Change58 i, j := 0, 059 for _, m := range commonSources(ca, cb) {60 out = append(out, unmatched(sheetName, ca[i:m[0]], cb[j:m[1]], i, j)...)61 out = append(out, cellFields(sheetName, m[1], ca[m[0]], cb[m[1]])...)62 i, j = m[0]+1, m[1]+163 }64 return append(out, unmatched(sheetName, ca[i:], cb[j:], i, j)...)65}6667// unmatched compares the cells between two matched ones: side by side68// as sources changed, the rest added or removed. i and j are where they69// start on each side.70func unmatched(sheetName string, a, b []nbCell, i, j int) []Change {71 var out []Change72 for k := 0; k < len(a) || k < len(b); k++ {73 switch {74 case k >= len(a):75 out = append(out, nbChange(sheetName, j+k, "added", nil, b[k].fields["source"]))76 case k >= len(b):77 out = append(out, nbChange(sheetName, i+k, "removed", a[k].fields["source"], nil))78 default:79 out = append(out, cellFields(sheetName, j+k, a[k], b[k])...)80 }81 }82 return out83}8485// cellFields compares two cells field by field.86func cellFields(sheetName string, at int, a, b nbCell) []Change {87 var out []Change88 for _, k := range unionKeys(a.fields, b.fields) {89 if !equal(a.fields[k], b.fields[k]) {90 out = append(out, nbChange(sheetName, at, k, a.fields[k], b.fields[k]))91 }92 }93 return out94}9596func nbChange(sheetName string, at int, field string, a, b json.RawMessage) Change {97 return rawChange(KindNotebook, sheetName, fmt.Sprintf("cell %d", at+1), field, a, b)98}99100// commonSources pairs the cells of a and b whose sources are the same,101// as many as keep their order (a longest common subsequence), by index.102func commonSources(a, b []nbCell) [][2]int {103 n, m := len(a), len(b)104 lcs := make([][]int, n+1)105 for i := range lcs {106 lcs[i] = make([]int, m+1)107 }108 for i := n - 1; i >= 0; i-- {109 for j := m - 1; j >= 0; j-- {110 if a[i].source == b[j].source {111 lcs[i][j] = lcs[i+1][j+1] + 1112 } else {113 lcs[i][j] = max(lcs[i+1][j], lcs[i][j+1])114 }115 }116 }117 var out [][2]int118 for i, j := 0, 0; i < n && j < m; {119 switch {120 case a[i].source == b[j].source:121 out = append(out, [2]int{i, j})122 i, j = i+1, j+1123 case lcs[i+1][j] >= lcs[i][j+1]:124 i++125 default:126 j++127 }128 }129 return out130}131132// dumpNotebook writes a notebook's cells as Dump's lines: the source,133// and the first line of what the last run printed or said.134func dumpNotebook(sheetName string, raw json.RawMessage) []string {135 var out []string136 for i, c := range nbCells(raw) {137 line := fmt.Sprintf("%s cell %d %s", sheetName, i+1, quoted(c.source))138 var s string139 switch {140 case json.Unmarshal(c.fields["error"], &s) == nil && s != "":141 line += " error: " + firstLine(s)142 case json.Unmarshal(c.fields["output"], &s) == nil && s != "":143 line += " = " + firstLine(s)144 }145 out = append(out, line)146 }147 return out148}149150// firstLine is s's first line, at most 120 characters of it.151func firstLine(s string) string {152 s, _, cut := strings.Cut(s, "\n")153 if r := []rune(s); len(r) > 120 {154 s, cut = string(r[:120]), true155 }156 if cut {157 s += "…"158 }159 return s160}