4 ms·

I'm working on what I call "semantic version control". Namely, instead of diffing and merging text, the goal is to parse the program and diff/merge the AST. ED

by tikhonj 14y ago

I'm working on what I call "semantic version control". Namely, instead of diffing and merging text, the goal is to parse the program and diff/merge the AST. EDIT: A better way to state the goal: I want to take advantage of the underlying structure of a computer program to inform the diff/merge. The first step just happens to be diffing ASTs, but I go beyond this. I already have some neat features--for example, I can detect moves fairly robustly. That is, if you move a function, I can see that as a single action even if you modify the function a little bit when moving it (e.g. rename the parameters). Also, there is already more information for resolving conflicts in a three-way merge. Unfortuntely, the performance is currently horrible, which makes it completely unusable. Once I fix that (I just need to memoize the diff function properly) and fiddle around with some of the algorithms a bit, I'll have something interesting (I hope :)). After that, I'll probably add a UI. Also, I should add that I'm not the only person with this idea. A lot of the early design and features are based on YDiff[1], although I used no code from there. The merging and some of the other stuff I'm working on right now is more original though (I think). [1]: http://yinwang0.wordpress.com/2012/01/03/ydiff/ http://yinwang0.wordpress.com/2012/01/03/ydiff/

franciscoapinto 14y ago
That is a great idea, if you can get it to work. I think your nomenclature's wrong, though. If you are comparing via the AST, it's lexical version control. However, on your second paragraph: > That is, if you move a function, I can see that as a single action even if you modify the function a little bit when moving it That already seems a bit more semantic than lexical.
- tikhonj 14y ago
  Well, I'm using the AST to power most of the analysis. So the first-order diff is lexical--it works on syntax ignoring whitespace and the like. The second-order stuff, like matching substructures, is based on the first-order diff, but is semantic. I'm also planning to add more semantic features. In the short-term, I'd like to detect other simple refactorings (particularly renamed variables). In the long run, I might even add very language-specific features (like trying to use type information to help with merging).
kamaal 14y ago
I was just wondering what would be the use cases of this. I mean to say code version control really is text version control. The whole idea is to track the changes, the cause for the change and who changed with some history. Added with this ability to do other code release related changes like revert, merge etc. What is the use of semantic version control?
- tikhonj 14y ago
  Right now it's just a better diff/merge tool. It's more accurate than a normal diff or merge, doesn't get confused by meaningless changes, can resolve more conflicts (theoretically) and should be able to produce a much better interactive merge experience. I don't have any features beyond that right now--it does not actually manage different versions itself right now. Once I have the client finished, you will be able to use it along with a normal VCS like Git. However, there are certain advantages to using an approach like this to manage commits as well as diffs and merges. For example, given the information I'm gathering, you would be able to automatically mark commits that only changed comments but not actual code. Additionally, you would be able to perform some fairly sophisticated queries on history--for example, you would be able to track a function across renames or just list all the names it ever had, which would be useful. This is all possible, but writing a complete version control system is outside the scope of this side project. Additionally, it would be much easier to get users if this tool just augmented their existing workflow (e.g. Git) rather than trying to replace it altogether. Hopefully this gives you a good idea of the sort of things I want to do. I have some other ideas as well, but some of them are probably too difficult to implement. I have to admit that even the relatively simple coffee I have so far turned out to be much more difficult to write than I exit expected. Your question is actually very useful--it reminds me that I need to come up with a good elevator pitch for the system. I'll worry about it when I actually have a working prototype rather than a loose collection of slow functions :-).
- vermasque 14y ago
  The biggest benefit is more clear understanding of changes in development teams over significant periods of time. For example, when was this function changed? That's very hard to answer when the diffs are not semantic. The Eclipse IDE provides semantic diffs on top of version control when viewing specific commits (pending or already committed) but this is obviously not part of the underlying version control system and is limited.
yinwang0 14y ago
Hey, glad you are working on this. I have later given a talk on structural version control together with demos of structural editing and ydiff. Here are the slides: http://yinwang0.wordpress.com/2012/02/12/structural-version-control http://yinwang0.wordpress.com/2012/02/12/structural-version-... I think structural version control can open lots of possibilities that are not accessible by text-base version control systems. I'm not really focused on this area, but I'd be happen to to see more people getting interested in this and work on it. As for the performance of diffing, I think the bottleneck is with detection of moving. That's something that text-based diff doesn't do at all, so not a big drawback. But with structural editors, those moves can be instantly detected and logically merged by the editors. That's too far into the future though. But I think structural diffing without move detection can be of good use already. Another direction that's possible to detecting moving more efficiently is to use hashing, the same trick used to eliminate redundant expressions in a compiler.

by tikhonj 14y ago

franciscoapinto 14y ago

That is a great idea, if you can get it to work. I think your nomenclature's wrong, though. If you are comparing via the AST, it's lexical version control. However, on your second paragraph: > That is, if you move a function, I can see that as a single action even if you modify the function a little bit when moving it That already seems a bit more semantic than lexical.

tikhonj 14y ago
Well, I'm using the AST to power most of the analysis. So the first-order diff is lexical--it works on syntax ignoring whitespace and the like. The second-order stuff, like matching substructures, is based on the first-order diff, but is semantic. I'm also planning to add more semantic features. In the short-term, I'd like to detect other simple refactorings (particularly renamed variables). In the long run, I might even add very language-specific features (like trying to use type information to help with merging).

kamaal 14y ago

I was just wondering what would be the use cases of this. I mean to say code version control really is text version control. The whole idea is to track the changes, the cause for the change and who changed with some history. Added with this ability to do other code release related changes like revert, merge etc. What is the use of semantic version control?

tikhonj 14y ago
Right now it's just a better diff/merge tool. It's more accurate than a normal diff or merge, doesn't get confused by meaningless changes, can resolve more conflicts (theoretically) and should be able to produce a much better interactive merge experience. I don't have any features beyond that right now--it does not actually manage different versions itself right now. Once I have the client finished, you will be able to use it along with a normal VCS like Git. However, there are certain advantages to using an approach like this to manage commits as well as diffs and merges. For example, given the information I'm gathering, you would be able to automatically mark commits that only changed comments but not actual code. Additionally, you would be able to perform some fairly sophisticated queries on history--for example, you would be able to track a function across renames or just list all the names it ever had, which would be useful. This is all possible, but writing a complete version control system is outside the scope of this side project. Additionally, it would be much easier to get users if this tool just augmented their existing workflow (e.g. Git) rather than trying to replace it altogether. Hopefully this gives you a good idea of the sort of things I want to do. I have some other ideas as well, but some of them are probably too difficult to implement. I have to admit that even the relatively simple coffee I have so far turned out to be much more difficult to write than I exit expected. Your question is actually very useful--it reminds me that I need to come up with a good elevator pitch for the system. I'll worry about it when I actually have a working prototype rather than a loose collection of slow functions :-).
vermasque 14y ago
The biggest benefit is more clear understanding of changes in development teams over significant periods of time. For example, when was this function changed? That's very hard to answer when the diffs are not semantic. The Eclipse IDE provides semantic diffs on top of version control when viewing specific commits (pending or already committed) but this is obviously not part of the underlying version control system and is limited.

yinwang0 14y ago

Hey, glad you are working on this. I have later given a talk on structural version control together with demos of structural editing and ydiff. Here are the slides: http://yinwang0.wordpress.com/2012/02/12/structural-version-control http://yinwang0.wordpress.com/2012/02/12/structural-version-... I think structural version control can open lots of possibilities that are not accessible by text-base version control systems. I'm not really focused on this area, but I'd be happen to to see more people getting interested in this and work on it. As for the performance of diffing, I think the bottleneck is with detection of moving. That's something that text-based diff doesn't do at all, so not a big drawback. But with structural editors, those moves can be instantly detected and logically merged by the editors. That's too far into the future though. But I think structural diffing without move detection can be of good use already. Another direction that's possible to detecting moving more efficiently is to use hashing, the same trick used to eliminate redundant expressions in a compiler.