Code-aware VCS

[bvisness]

Version control software generally doesn't actually understand code. For example, it's a well-known fact that simply indenting a bunch of code in Git will probably result in horrific merge conflicts, because the "lines have changed", despite it being an obviously trivial and mergeable change.

What could version control systems do if they actually understood the programs they were versioning? A few starter examples:

• Smarter merging and diffing
  • Distinguishing formatting from content changes
  • Detecting variable renames separate from actual behavior changes
  • Detecting when the contents of a file are rearranged but the semantics are the same (for example, this would enable you to merge changes inside a function even if that function was moved somewhere else)
• Per-function versioning - ability to roll a specific piece of your program back to a previous point without affecting the entire codebase

This is essentially an open area of research that someone should dig into!

It is worth noting, by the way, that Git actually allows for smarter "merge drivers", but these do not seem to be in widespread use. It's possible that programmers could get quite a quality-of-life boost even within current version control systems.

I'm sure this idea has been explored to some extent (it's a pretty obvious idea) but I'm not familiar with what's out there myself. If people know of existing research or tools in this space, please post them in the discussion below.

[bernardolk]

I had a similar idea a few weeks ago, but I thought of simply outputting what code changes happened as a helper string instead of using that data to build a new vcs system. You could do something like git code-changes --commit <hash> and get the smart diff you mentioned, I think that would be extremely helpful but I have no clue how hard it would be to implement. Also, might be worth to think how to make the feature easy to extend to multiple languages

[matu3ba]

I believe a customized rope to the AST qualifies for most of these things (except if wanted semantic information) as I understand as rope 1. AST of the program, 2. traversal info for efficient lookup to modify things in tree, 3. formatting specific info associated to the AST (if the formatting is not unambiguous).
See also https://blog.jetbrains.com/fleet/2022/02/fleet-below-deck-part-ii-breaking-down-the-editor/

For example, a lsp combines those info with semantic ones (lazily).
I am not sure, if a customized editor working on this representation with exceptions for "non-yet AST conform code" would be beneficial,
as only few work on a rope as basic data structure (I do only know of helix and jetbrains is working on it).

1. Distinguishing formatting from content changes
2. Detecting variable renames separate from actual behavior changes
3. Detecting when the contents of a file are rearranged but the semantics are the same (for example, this would enable you to merge changes inside a function even if that function was moved somewhere else)

This means 1+2 can be solved, as we are essentially only checking AST equality wrt. some property (leaving out some parts etc).
If 3 implies that input-output-wise the function is identical and the function change has no global side effects, then yes.
The yes also assumes that generics dont work like the C preprocessor, for generics order of symbols in scopes/namespaces does not matter (for perf) and generics are fully scoped/namespaced.
Unfortunately thats slow for generics unless you store the result of resolving them in some way (you would need all relevant inputs for that somehow to rule out semantics, which is infeasible for a fast versioning system).

Per-function versioning

Git can pull out function symbols for you with git log -L :myfunction:path/to/myfile.c https://stackoverflow.com/a/33953022
Its just the interface of git, which is very much not nice.

Does anybody have experience in AST based program minification?

UPDATE: add link and clarify assumptions.
UPDATE2: add other use case + nice rope link

[beanbrainbb]

I just found this paper by Jonathan Edwards, which addresses this very issue. Most of the content is too academic for my smooth brain as the sun comes up, but basically the idea is tracking document changes by the edit as the elemental unit of change, which are defined as 'Insertion' of a token at the position of another token, pushing the rest of the document forward, 'Conversion' of a token to another, 'Move' (which is basically REmove, keeping the removed token as a tombstone), and the 'Identity' edit which does nothing. A 'project' function takes a source and a diff and produces the modified source from it, 'retract' attempts to do the inverse, taking a source and diff and producing the prior source, but in the case of conflicts it can't.

The paper is really interesting, and I'll read the rest tomorrow with some good rest and hot coffee. The comments on Jonathan Edward's blog post link to some interesting resources as well. I'd like to work on this. Hopefully we can find a solution worth using ourselves.

Follow up: Here's a video of J. Edwards' prototype in action: HATRA’21 talk

[matu3ba]

I briefly talked to J. Edwards, but so far I have not seen any feasible suggestions from him on how to combine "graphical edits for documentation and multiple representation options" and AST-based edits.

This means, that any SCCS must provide both representations (git one and AST-based one), if there is the option to graphically describe code behavior within comments.

I sketched my ideas here: https://gist.github.com/matu3ba/edd5460181238b4ee0cb0c7a6106d9ca