Simpler diffing

[aslakhellesoy]

Currently we're using one library to generate a unified diff string, then parse it into a datastructure.

This is inefficient. We should use a lower level myers diff algorithm instead:

• https://github.com/hexops/gotextdiff/blob/main/myers/diff.go
• https://github.com/aymanbagabas/go-udiff
• https://github.com/pkg/diff/tree/main
• https://github.com/covrom/diff

It should be fast and memory efficient (check the issues and benchmarks)

This one looks promising: https://github.com/thepudds/patience-diff/blob/main/diff.go

It would have to be modified to output data structures instead of a unified diff script.

Trying this as it seems most uptodate: https://pkg.go.dev/github.com/rogpeppe/go-internal/diff@master

[aslakhellesoy]

Maybe use a diff-match-patch implementation instead for the initial diffing. It can be used for line diffing

For a SimHash alternative, maybe consider LSH

• https://github.com/RyuaNerin/go-krypto

Other articles:

• https://fservant.github.io/papers/Servant_Jones_ICSE17.pdf

• https://fservant.github.io/papers/Servant_Jones_FSE12.pdf

• https://fservant.github.io/papers/Servant_Jones_VISSOFT13.pdf

• https://eprints.lancs.ac.uk/id/eprint/148836/2/ICPC_2020_v1_CR_.pdf

• https://www.youtube.com/watch?v=ohwMvoZfj1E

  • SZZ algorithm

• SZZ Unleashed: An Open Implementation of the SZZ Algorithm

  • https://github.com/wogscpar/SZZUnleashed

• https://medium.com/carbon-consulting/explaining-lsh-minhash-simhash-c3cc33040030

[aslakhellesoy]

SZZ tools:

• https://github.com/ishepard/pydriller
• https://github.com/wogscpar/SZZUnleashed
  • http://mrksbrg.com/maltesque19-borg/
• https://github.com/clowee/OpenSZZ

A neural variant of SZZ: https://baolingfeng.github.io/papers/ASE2023.pdf

[aslakhellesoy]

Maybe useful for SZZ: https://commondatastorage.googleapis.com/chrome-infra-docs/flat/depot_tools/docs/html/git-hyper-blame.html

Built into git, but maybe not go-git? https://github.com/tpope/vim-fugitive/issues/1058#issuecomment-529038519