Seems nice, but doesn't support mainstream languages e.g. C#, Java.
Ydiff: Structural Comparison of Programs
11–20 of 35 posts
Re: Ydiff: Structural Comparison of Programs
#12This is pretty damn cool, but I can think of a few things that I'm curious how you're going to address: 1) Your C++ example, we have "namespace 'v8'" -- which has been removed and reinserted. That made me scratch my head a bit. Has it been refactored enough that this is kind of a rewrite? If so, there might be a third or fourth color here for "hey, this part didn't /change/ per se, but everything under it did" 2) You…
> 3) I get your whole in-the-future-we-store-ASTs argument, but that's certainly not the case today. Today we store text, and I don't see that changing. Could there also be a diff, perhaps even another mode that, counter to just dealing with structure, deals with formatting? ie, find the ranges that contribute nothing to the AST and then diff those textually.
Agree. I think it's likely code will be stored as text, but parsed into ASTs easily. Consider Go standard library has a full language parser built right in, so to get an AST from a .go text source file is about 3 lines of code.
Because you can get the code back from AST easily (while maintaining spacing), it really doesn't matter what you save. You can use tools to edit the text form or AST form without any duplication.
Re: Ydiff: Structural Comparison of Programs
#13We use a similar thing internally at Wolfram to diff Wolfram Language expressions, though I believe it doesn't have the subexpression matcher. But the diffs are much clearer when you have full m-expressions instead of s-expressions.
The coder who wrote it (@wmacura) now works at Tumblr.
Re: Ydiff: Structural Comparison of Programs
#14This is great. I've wanted to build a similar tool for a couple of years, the distinction being that I want a structural grep utility. I'd pass in a pattern in the form of a code snippet (with pattern operators), and have the thing search for matching code structures. I suspect that this tool does 95% of what would be needed for that, very nice.
Re: Ydiff: Structural Comparison of Programs
#15Wonderful, although I would rather have the AST integrated with GIT and not as some other kind of version control.
Re: Ydiff: Structural Comparison of Programs
#16I was working on a very similar project myself recently [1], heavily inspired by ydiff. Unfortunately, I didn't implement the tree diff algorithm entirely correctly, and it's been on hiatus for over a year :(. The one interesting addition my project had was merging. The neat trick was that we reused the same tree diff algorithm to find conflicts :P. With a bit of work, we would have some very neat features, including…
I thought of a variant of this approach for distributed code storage/reuse. Store each function as AST with normalized variable names. Then, a cryptographic hash of this would uniquely identify algorithm. So, caching becomes quite easy and very scalable. Callers refer to specific version by hash also. Thus your entire program can be identified by a single hash. Nice to distribute and cache at web scale. What do you think ?
Re: Ydiff: Structural Comparison of Programs
#17Lovely to see Racket being used. Given the pure meta-ness of Racket hopefully ydiff will not only evolve into a full-fledged version control system but a completely configurable one at that, akin to the power of Emacs and it's Lisp. Having something like a .yinrc where I could quickly throw around and test out custom functionality would be awesome. I haven't gotten much into git's plumbing yet, but I don't see a cult…
That's why I love Mercurial. The API is great, people build great things with it, and it has a policy of "default to sane, simple and working; let users tweak stuff easily".
Re: Ydiff: Structural Comparison of Programs
#18This is pretty damn cool, but I can think of a few things that I'm curious how you're going to address: 1) Your C++ example, we have "namespace 'v8'" -- which has been removed and reinserted. That made me scratch my head a bit. Has it been refactored enough that this is kind of a rewrite? If so, there might be a third or fourth color here for "hey, this part didn't /change/ per se, but everything under it did" 2) You…
> 3) I get your whole in-the-future-we-store-ASTs argument, but that's certainly not the case today. Today we store text, and I don't see that changing. Could there also be a diff, perhaps even another mode that, counter to just dealing with structure, deals with formatting? ie, find the ranges that contribute nothing to the AST and then diff those textually. Agree. I think it's likely code will be stored as text, bu…
I've actually been trying to make 3) happen with a long-standing project of mine, because serializing AST to text discards information. In a (proper) AST, human-readable names are never used as pointer values.
When you bind something (reference a variable), you just point at that variable's node, rather than mentioning it by string. This removes a huge class of artificial problems brought on by plaintext source code (symbol name clashes, namespaces, overeager imports, var name typos, shadowing, and other programmer-compiler miscommunications), but introduces some editor UI concerns (e.g. indicating shadowing).
There are a whole host of other advantages of saving as ASTs directly. One of them is granular, semantic diffs like in the OP. I'm convinced it's the future... there are a lot of UI problems to solve in a solid, practical editor for it though.
Re: Ydiff: Structural Comparison of Programs
#19I was working on a very similar project myself recently [1], heavily inspired by ydiff. Unfortunately, I didn't implement the tree diff algorithm entirely correctly, and it's been on hiatus for over a year :(. The one interesting addition my project had was merging. The neat trick was that we reused the same tree diff algorithm to find conflicts :P. With a bit of work, we would have some very neat features, including…
I thought of a variant of this approach for distributed code storage/reuse. Store each function as AST with normalized variable names. Then, a cryptographic hash of this would uniquely identify algorithm. So, caching becomes quite easy and very scalable. Callers refer to specific version by hash also. Thus your entire program can be identified by a single hash. Nice to distribute and cache at web scale. What do you t…
It's what we need. This became clear shortly after learning git--it's the right data structure for the problem.
The hurdle is that hashes aren't user-friendly in a text-based code editor. We need an editor that lets us view and work at the right level of abstraction.
Re: Ydiff: Structural Comparison of Programs
#20Semantic Merge [1] is a product based around semantic diffs for C#/VB.NET. Their demo is quite impressive, and they're working on Java and C++ next.