4 ms·
This article loses me when it gets to the "calculating the diff" section. >Autochrome and difftastic represent diffing as a shortest path problem on a directed
by _dain_ 4y ago
This article loses me when it gets to the "calculating the diff" section.
>Autochrome and difftastic represent diffing as a shortest path problem on a directed acyclic graph. A vertex represents a pair of positions: the position in the left-hand side s-expression (before), and the position in the right-hand side s-expression (after).
>The goal is to find the shortest route from the start vertex (where both positions are before the first item in the programs) to the end vertex (where both positions are after the last item in the program).
I don't understand what this means at all? What is a "position" here? Position of what? If it's a graph, what do the edges represent? The diagrams afterwards aren't very helpful either, I can't make head nor tail of them. They talk about a "start" vertex and an "end" vertex, but before that it said that a vertex is a pair of start-end positions ... I'm totally lost.
- Wilfred 4y agoThanks for the feedback. This is really hard to explain. Autochrome has a brilliant worked example https://fazzone.github.io/autochrome.html https://fazzone.github.io/autochrome.html and it still took me several readings before it clicked. Every graph vertex represents a pair of pointers (or positions) to AST nodes. So in the example, the start program is `A` and the end program is `X A`. The positions point to AST nodes in these programs. I try to use 'vertex' consistently for graph vertices, to avoid confusion with AST/s-expression nodes. If you have any suggestions for better terminology I'd be very interested too :)