Fork me on GitHub
#cursive
<
2018-03-06
>
Drew Verlee00:03:48

Random suggestion. What about integrating in something like https://github.com/ladderlife/autochrome into cursive? I feel like intelliji diff options are already better then anything out there, having syntax aware changes would be pretty awesome.

cfleming01:03:04

@drewverlee Yeah, I saw that and made a mental note to check whether the diff algorithm is pluggable. I haven’t got around to actually checking it though. I also think that that diff algorithm is pretty expensive for large files with multiple change locations.

cfleming01:03:50

> For example, If you split a 100-line function into two pieces and also make a bunch of changes, it might take like 30 seconds to diff. That’s not great, but you’ll probably spend more than 30 seconds looking at a diff like that anyway.

cfleming01:03:25

While that’s true, people will probably get upset if they have to wait 30 seconds to then spend more than 30 seconds looking at it 🙂

cfleming01:03:17

I suspect that there are a lot of degenerate cases that might cause that sort of behaviour. It might be possible to do something like put a time bound on the diff and if it’s violated then default to the previous behaviour though.

cfleming01:03:12

Looking at it, I can’t immediately tell how easy that would be.

cfleming01:03:24

(swapping the algorithm, that is)

Drew Verlee01:03:29

@cfleming Yea, there are a lot of unknowns here for me at least. It seems like a topic that would be well researched but here we are in 2018 without structural diffs? Or i’m i missing something? So i’m not sure what all the dark corners are. If its just a performance issue, then It would be exciting to see what sort of options were out there to make it go faster. Algorithms, etc…

cfleming01:03:25

Both the associated webpage (https://fazzone.github.io/autochrome.html) and the original blog (http://thume.ca/2017/06/17/tree-diffing/) are well worth a read.

cfleming01:03:10

tl;dr is that general tree diffing is hard (O(n^3) in the naive case IIRC)

Drew Verlee01:03:03

Good point! He did put out a lot of material, i just say this yesterday so i haven’t had time to dig in. I just thought i would mention it here in case it hadn’t caught your eye as it seems like a potentially great addition.

cfleming01:03:40

Yes, definitely!

cfleming01:03:55

Do read the tree-diffing blog post, it’s pretty great.

cfleming01:03:06

You’ll need a cup of coffee though.

Drew Verlee01:03:16

Yea. I’ll have to give it a read. If anything It will probably be highly educational. What i remember from algorithms is that even if that truly is the big O you might be able to get away with some combination of algorithms to keep the average acceptable to users.

cfleming01:03:22

Also, interesting HN comments on the original submission: https://news.ycombinator.com/item?id=15101373

cfleming01:03:01

Sure, he talks about using A* to prune the search space, and dynamic programming to keep the runtime under control (at the cost of memory)

Drew Verlee01:03:34

Cool, the one algorithm i have ever employed in building something 🙂

Drew Verlee01:03:29

Bookmarked it all. Thanks!

cfleming01:03:03

> The tree differencing problem has been largely investigated when considering only the add node, delete node and update node actions [4]. For this problem, many optimal algorithms have are described in the literature. The fastest algorithms of this family [27] run in O(n^3), which can result in significantly long edit script computation time for large source code files. The other issue faced by these algorithms is their inability to uncover moved nodes, which is a frequent action in sourcecode files. It results in unnecessarily big edit scripts which are hard to understand. > When considering move node actions, the problem of finding the shortest edit script between two trees becomes NP-hard.

cfleming02:03:12

But there are heuristics available.

genekim05:03:38

@cfleming Awesome news on supporting Lumo or Planck — I’m indifferent to either… I chose Lumo because it was the first one where I found support for easy file I/O. FWIW, I loved using it because it was so fast and the fan stayed off on my MacBook Pro. 🙂 (Not complaining about Clojure JVM or CLJS compile times… But it was refreshing! :)

genekim05:03:11

(Not a high priority for me at all… Was wonderful to solve a small problem today with Lumo, though!)

cfleming06:03:45

@genekim Indeed, I use Lumo for a couple of release scripting tasks - the lack of symbol resolution is a pain but for small things it’s still nice. I definitely want good support for it though!