patchwork

package diff

import (
	"strings"

	"git.pablomurad.com/pablo/patchwork/internal/doc"
)

// Op kinds of a block diff.
const (
	OpEq     = "eq"
	OpInsert = "insert"
	OpDelete = "delete"
	OpModify = "modify"
	OpMove   = "move"
	OpGap    = "gap"
)

// Op is one entry of a block diff, in reading order of the new version.
// Deleted blocks sit where they used to be; a moved block sits at its new
// place and records the old one.
type Op struct {
	Op       string    `json:"op"`
	Kind     string    `json:"kind,omitempty"`
	Text     string    `json:"text,omitempty"`
	Segments []Segment `json:"segments,omitempty"`
	// Replaced marks a modify so changed that word highlights would be
	// noise; its segments are the whole old text and the whole new text.
	Replaced bool `json:"replaced,omitempty"`
	From     *int `json:"from,omitempty"`
	To       *int `json:"to,omitempty"`
	Count    int  `json:"count,omitempty"`
	// Removed marks a gap that stands for deleted blocks an excerpt left
	// out, rather than unchanged ones.
	Removed bool `json:"removed,omitempty"`
}

// Stats summarize a diff.
type Stats struct {
	WordsAdded    int `json:"words_added"`
	WordsRemoved  int `json:"words_removed"`
	BlocksChanged int `json:"blocks_changed"`
}

// Result is a full block diff: every block of the new version appears, with
// unchanged ones as eq ops.
type Result struct {
	Ops   []Op  `json:"ops"`
	Stats Stats `json:"stats"`
}

// Version identifies the diff algorithm and encoding. Bump it whenever the
// output for the same input changes; rebuild-diffs then refreshes the cache.
const Version = 1

// Full is what Patchwork caches for a revision: the block diff against the
// previous public version plus changes to visible frontmatter.
type Full struct {
	Ops   []Op         `json:"ops"`
	Stats Stats        `json:"stats"`
	Meta  []MetaChange `json:"meta_changes,omitempty"`
}

// Compare diffs two parsed versions of a document.
func Compare(old, new *doc.Doc, metaKeys []string) Full {
	r := Blocks(old.Blocks, new.Blocks)
	return Full{Ops: r.Ops, Stats: r.Stats, Meta: Meta(old, new, metaKeys)}
}

// pairThreshold is the word-set similarity (Dice) above which a deleted and
// an inserted block are read as one edited block.
const pairThreshold = 0.5

type item struct {
	kind EditKind
	a, b int // block indexes; -1 when absent
}

// Blocks diffs two block lists.
func Blocks(old, new []doc.Block) Result {
	ha := make([]string, len(old))
	for i, b := range old {
		ha[i] = b.Hash
	}
	hb := make([]string, len(new))
	for i, b := range new {
		hb[i] = b.Hash
	}

	var items []item
	for _, e := range Myers(ha, hb) {
		switch e.Kind {
		case Eq:
			for k := 0; k < e.A1-e.A0; k++ {
				items = append(items, item{Eq, e.A0 + k, e.B0 + k})
			}
		case Del:
			for i := e.A0; i < e.A1; i++ {
				items = append(items, item{Del, i, -1})
			}
		case Ins:
			for j := e.B0; j < e.B1; j++ {
				items = append(items, item{Ins, -1, j})
			}
		}
	}

	// Moves first: an inserted block identical to a deleted one anywhere.
	movedFrom := map[int]int{} // new index -> old index
	moved := map[int]bool{}    // old indexes consumed by a move
	byHash := map[string][]int{}
	for _, it := range items {
		if it.kind == Del {
			byHash[old[it.a].Hash] = append(byHash[old[it.a].Hash], it.a)
		}
	}
	for _, it := range items {
		if it.kind != Ins {
			continue
		}
		if cands := byHash[new[it.b].Hash]; len(cands) > 0 {
			movedFrom[it.b] = cands[0]
			moved[cands[0]] = true
			byHash[new[it.b].Hash] = cands[1:]
		}
	}

	var res Result
	for i := 0; i < len(items); {
		if items[i].kind == Eq {
			res.Ops = append(res.Ops, Op{Op: OpEq, Kind: new[items[i].b].Kind, Text: new[items[i].b].Text})
			i++
			continue
		}
		j := i
		for j < len(items) && items[j].kind != Eq {
			j++
		}
		res.Ops = append(res.Ops, hunk(old, new, items[i:j], movedFrom, moved, &res.Stats)...)
		i = j
	}
	return res
}

// hunk orders one run of deletions and insertions, pairing similar blocks
// into modify ops.
func hunk(old, new []doc.Block, items []item, movedFrom map[int]int, moved map[int]bool, st *Stats) []Op {
	var dels, ins []int
	for _, it := range items {
		if it.kind == Del && !moved[it.a] {
			dels = append(dels, it.a)
		}
		if it.kind == Ins {
			ins = append(ins, it.b)
		}
	}

	var plainIns []int
	for _, j := range ins {
		if _, isMove := movedFrom[j]; !isMove {
			plainIns = append(plainIns, j)
		}
	}

	pairOf := map[int]int{} // new index -> old index
	if len(dels) == 1 && len(plainIns) == 1 {
		// One block replaced by one block in the same place reads as an
		// edit however much it changed; Words decides between highlights
		// and a whole replacement.
		pairOf[plainIns[0]] = dels[0]
	} else {
		// Greedy pairing that keeps order: each insertion takes the most
		// similar later deletion.
		next := 0
		for _, j := range plainIns {
			best, bestScore := -1, pairThreshold
			for k := next; k < len(dels); k++ {
				if s := dice(old[dels[k]].Text, new[j].Text); s >= bestScore {
					best, bestScore = k, s
				}
			}
			if best >= 0 {
				pairOf[j] = dels[best]
				next = best + 1
			}
		}
	}
	// nextPaired[j]: the old index of the first pairing at or after
	// insertion j, so deletions print before the insertions that follow
	// them, the way diffs are read.
	nextPaired := map[int]int{}
	upcoming := len(old)
	for k := len(ins) - 1; k >= 0; k-- {
		if d, ok := pairOf[ins[k]]; ok {
			upcoming = d
		}
		nextPaired[ins[k]] = upcoming
	}

	var out []Op
	emitted := map[int]bool{}
	flushDels := func(upTo int) {
		for _, d := range dels {
			if d >= upTo {
				break
			}
			if paired(pairOf, d) || emitted[d] {
				continue
			}
			emitted[d] = true
			out = append(out, Op{Op: OpDelete, Kind: old[d].Kind, Text: old[d].Text})
			st.WordsRemoved += countWords(old[d].Text)
			st.BlocksChanged++
		}
	}
	for _, j := range ins {
		if from, isMove := movedFrom[j]; isMove {
			f, t := from, j
			out = append(out, Op{Op: OpMove, Kind: new[j].Kind, Text: new[j].Text, From: &f, To: &t})
			st.BlocksChanged++
			continue
		}
		if d, ok := pairOf[j]; ok {
			flushDels(d)
			segs, replaced, added, removed := Words(old[d].Text, new[j].Text)
			out = append(out, Op{Op: OpModify, Kind: new[j].Kind, Segments: segs, Replaced: replaced})
			st.WordsAdded += added
			st.WordsRemoved += removed
			st.BlocksChanged++
			continue
		}
		flushDels(nextPaired[j])
		out = append(out, Op{Op: OpInsert, Kind: new[j].Kind, Text: new[j].Text})
		st.WordsAdded += countWords(new[j].Text)
		st.BlocksChanged++
	}
	flushDels(len(old))
	return out
}

func paired(pairOf map[int]int, d int) bool {
	for _, v := range pairOf {
		if v == d {
			return true
		}
	}
	return false
}

// dice is 2|A∩B| / (|A|+|B|) over the lowercase word sets of two texts.
func dice(a, b string) float64 {
	sa, sb := wordSet(a), wordSet(b)
	if len(sa)+len(sb) == 0 {
		if a == b {
			return 1
		}
		return 0
	}
	common := 0
	for w := range sa {
		if sb[w] {
			common++
		}
	}
	return 2 * float64(common) / float64(len(sa)+len(sb))
}

func wordSet(s string) map[string]bool {
	set := map[string]bool{}
	for _, t := range doc.Tokenize(s) {
		if doc.IsWord(t) {
			set[strings.ToLower(t)] = true
		}
	}
	return set
}

func countWords(s string) int {
	n := 0
	for _, t := range doc.Tokenize(s) {
		if doc.IsWord(t) {
			n++
		}
	}
	return n
}