1// Package diff compares and merges .012 workbooks cell by cell, for2// 012 diff and 012 merge-driver (see docs/files/git.md). Compare lists3// what changed between two workbooks: sheets added, removed, renamed or4// moved, each cell's input, value, format and note, notebook cells,5// regions, named ranges, macros and the other fields of sheets and6// workbooks. Merge7// combines two workbooks changed from a common one, and conflicts only8// where both changed the same part of the same cell or field.9//10// Both read files as their JSON fields (raw.go), so nothing a file holds11// goes unseen, and use the engine only to compute formulas' values,12// which the file doesn't store. Nothing here runs a notebook cell or13// asks JEV: values come from what the formulas compute alone.14package diff1516import (17 "bytes"18 "fmt"1920 "src.rest/cat/012/internal/nuon"21 "src.rest/cat/012/internal/sheet"22)2324// Book is a workbook read for comparing: its file's fields and the25// workbook they make.26type Book struct {27 raw *rawBook28 wb *sheet.Workbook // nil for a workbook without sheets29 vol map[*sheet.Sheet]map[sheet.Addr]bool30}3132// Read reads a workbook file's contents. Empty contents are a workbook33// without sheets, which is what git hands over for a file that doesn't34// exist on one side.35func Read(data []byte) (*Book, error) {36 raw, err := parseRaw(data)37 if err != nil {38 return nil, err39 }40 b := &Book{raw: raw}41 if len(raw.sheets) > 0 {42 if b.wb, err = sheet.ReadBook(bytes.NewReader(data)); err != nil {43 return nil, err44 }45 b.vol = volatiles(b.wb)46 }47 return b, nil48}4950// Kinds of Change.51const (52 KindSheet = "sheet" // a sheet added, removed, renamed or moved53 KindCell = "cell" // a cell's input, value, format or note54 KindRegion = "region" // a notebook region or linked file55 KindTable = "table" // a table56 KindLayout = "layout" // another field of a sheet: widths, rules, charts57 KindName = "name" // a named range58 KindMacro = "macro" // a macro59 KindWorkbook = "workbook" // a field of the workbook: locale, arithmetic60)6162// Change is one difference. Old or New is null where the thing isn't on63// that side.64type Change struct {65 Kind string66 Sheet string // the sheet, by its name in the second workbook where it has one67 Item string // the cell, region, name, macro or field that changed68 // Field is what about it changed: for a cell input, value, format or69 // note; for a sheet added, removed, renamed or moved; for a region,70 // name or macro added, removed or its field's name; for a layout71 // field, its key when it has keys (a column's width), else "".72 Field string73 Old, New nuon.Value74 // oldText and newText are Old and New as the text output shows them.75 oldText, newText string76}7778// Where names the change's place as the text output does: Q3!B7,79// sheet Q3, Q3 region r1, Q3 table Sales, Q3 widths, name Sales.80func (c Change) Where() string {81 switch c.Kind {82 case KindCell:83 return sheet.QuoteSheet(c.Sheet) + "!" + c.Item84 case KindSheet:85 return "sheet " + c.Sheet86 case KindRegion:87 return c.Sheet + " region " + c.Item88 case KindTable:89 return c.Sheet + " table " + c.Item90 case KindLayout, KindNotebook:91 return c.Sheet + " " + c.Item92 }93 return c.Kind + " " + c.Item94}9596// Compare lists what changed from a to b: sheets first, then each97// sheet's cells in row order, a notebook tab's cells, its regions and98// other fields, then the workbook's names, macros and settings.99func Compare(a, b *Book) []Change {100 var out []Change101 p := matchSheets(a.raw, b.raw)102 out = append(out, sheetChanges(a.raw, b.raw, p)...)103 empty := &rawSheet{fields: nil, cells: nil}104 for _, i := range p.onlyA {105 sa := a.raw.sheets[i]106 out = append(out, sheetDiff(a.side(sa), side{raw: empty}, sa.name)...)107 }108 for _, pr := range p.pairs {109 sa, sb := a.raw.sheets[pr[0]], b.raw.sheets[pr[1]]110 out = append(out, sheetDiff(a.side(sa), b.side(sb), sb.name)...)111 }112 for _, j := range p.onlyB {113 sb := b.raw.sheets[j]114 out = append(out, sheetDiff(side{raw: empty}, b.side(sb), sb.name)...)115 }116 return append(out, bookChanges(a.raw, b.raw)...)117}118119// side is one sheet of a comparison: its fields, and the sheet the120// engine made of them, nil for a sheet that isn't there.121type side struct {122 raw *rawSheet123 s *sheet.Sheet124 vol map[sheet.Addr]bool // its cells whose values change on every recalculation125}126127func (b *Book) side(s *rawSheet) side {128 sd := side{raw: s}129 if b.wb != nil {130 sd.s = b.wb.Lookup(s.name)131 sd.vol = b.vol[sd.s]132 }133 return sd134}135136// sheetChanges are the sheets added, removed, renamed and moved.137func sheetChanges(a, b *rawBook, p pairing) []Change {138 var out []Change139 for _, i := range p.onlyA {140 name := a.sheets[i].name141 out = append(out, textChange(KindSheet, name, "", "removed", name, ""))142 }143 for _, j := range p.onlyB {144 name := b.sheets[j].name145 out = append(out, textChange(KindSheet, name, "", "added", "", name))146 }147 for _, pr := range p.pairs {148 na, nb := a.sheets[pr[0]].name, b.sheets[pr[1]].name149 if na != nb {150 out = append(out, textChange(KindSheet, nb, "", "renamed", na, nb))151 }152 }153 // Moves: the fewest sheets that, taken out, leave the rest in the154 // same order on both sides.155 var orderB []int156 for _, pr := range p.pairs {157 orderB = append(orderB, pr[1])158 }159 stay := increasing(orderB)160 for k, pr := range p.pairs {161 if !stay[k] {162 nb := b.sheets[pr[1]].name163 c := textChange(KindSheet, nb, "", "moved", fmt.Sprint(pr[0]+1), fmt.Sprint(pr[1]+1))164 c.Old, c.New = nuon.IntValue(int64(pr[0]+1)), nuon.IntValue(int64(pr[1]+1))165 out = append(out, c)166 }167 }168 return out169}170171// increasing marks a longest increasing run (not necessarily adjacent)172// of vs.173func increasing(vs []int) []bool {174 n := len(vs)175 length, prev := make([]int, n), make([]int, n)176 best := -1177 for i := range vs {178 length[i], prev[i] = 1, -1179 for j := range i {180 if vs[j] < vs[i] && length[j]+1 > length[i] {181 length[i], prev[i] = length[j]+1, j182 }183 }184 if best < 0 || length[i] > length[best] {185 best = i186 }187 }188 out := make([]bool, n)189 for i := best; i >= 0; i = prev[i] {190 out[i] = true191 }192 return out193}194195// textChange is a change whose sides are text, "" for none.196func textChange(kind, sheetName, item, field, old, new string) Change {197 return Change{Kind: kind, Sheet: sheetName, Item: item, Field: field,198 Old: textValue(old), New: textValue(new), oldText: old, newText: new}199}200201func textValue(s string) nuon.Value {202 if s == "" {203 return nuon.NullValue()204 }205 return nuon.StringValue(s)206}