5 ms·

I've been keeping an eye on Pijul for a while, but assumed that (when it eventually stabilised) it personally wouldn't be worth the effort to switch from git.

I've been keeping an eye on Pijul for a while, but assumed that (when it eventually stabilised) it personally wouldn't be worth the effort to switch from git. I've changed my mind now that they're tracking byte ranges instead of lines, with ranges decided in a customisable way at commit time. Semantic/format-aware versioning would be really nice. The easiest plugins to write would be s-expressions and JSON, and I could definitely see myself choosing Pijul for such repos in the future. If the patch-based approach is truly as nice as it appears, that might push me to use it more generally. In fact, making an s-expression plugin which is robust across various Lisp dialects might be a good way to bootstrap the user community. It would be nice to have for other languages too (C, Python, etc.), but they'd (a) be more complicated and (b) more subject to churn.

the_duke 6y ago
Encoding a generic, potentially versioned AST in S-expressions seems feasible. I believe the Unison language [1] does this for their code storage system. (Unison does not use traditional text storage but stores code in a normalized repository) [1] https://github.com/unisonweb/unison https://github.com/unisonweb/unison
- chriswarbo 6y ago
  There are multiple ways to do it, e.g. spreading data and parentheses across multiple lines to work better with line-based tools like git, or keeping revisions in the files themselves, etc. but most approaches require translation back and forth, which is a burden on those trying to handle the data (e.g. viewing diffs, bisecting to pin down a bug, etc.).
cb321 6y ago
The Haskell DVC system that pijul "sort of" evolved from (theory of patches-wise mostly, just being careful given the stringent IP/credit language afoot), darcs, had this sort of semantic concept. It could track, e.g., symbol renames very early on in darcs' history. I haven't looked at darcs in many years, but it would be unsurprising if it had evolved to similar generality like pluggable byte ranges.
- pmeunier 6y ago
  I'm the author, I understand how that comment of mine could be misinterpreted, which is why I removed it. It was just a reaction to a number of plagiarism events that have happened to me in recent years. At some point I've even been asked to review papers claiming to prove my own results.
  - cb321 6y ago
    No big deal from my perspective. I was just explaining my cautious wording. I know you've been open about working with/from "ideas/people" in the darcs community, and good about the shoulders [1] the pijul work stands on/improves, and I also dislike people not giving credit where it is due. Sometimes a few bad apples ruin many things. FWIW, I liked the name "Anu" better. :-/ EDIT: and thanks for all your hard work on Pijul! [1] https://arxiv.org/abs/1311.3903 https://arxiv.org/abs/1311.3903
WorldMaker 6y ago
I explored this idea back in the day with darcs (though I don't think darcs' proposed character-based patch format "chunks" ever made it past the proposal stage), as some back and forth discussions led me to what I think is a perfect compromise on power, time (to compute), and universality. I explored using an off the shelf syntax highlighting tokenizer (Pygments specifically as a it was a Python prototype) [1] to build character-based diffs. Got surprisingly good results from what I tested. Most off the shelf syntax highlighters support a huge variety of languages. One advantage to using a syntax highlighting tokenizer/lexer is that they are designed to be fast (many of them need to be real time in text editors after all), and handle "degenerate cases" very well (text editors spend a lot of time on work in progress code that doesn't fully describe a complete compilable unit; version control systems just as well need to be good at storing work in progress states). The finished prototype I built created standard character-based unidiffs, and it sounds like could possibly be slotted directly into Pijul now. I'd be very interested to experiment further with it now that one of the patch algebra VCSes has finally adopted a "chunk" option. [1] https://github.com/WorldMaker/tokdiff https://github.com/WorldMaker/tokdiff (ETA: Suppose the first step is that it is time to get the band back together and update the prototype to Python 3.)
- chriswarbo 6y ago
  Very cool. I suppose these days tree-sitter would be one way to support a lot of languages at once ( https://tree-sitter.github.io/tree-sitter/#available-parsers https://tree-sitter.github.io/tree-sitter/#available-parsers )
  - WorldMaker 6y ago
    Still a tiny fraction compared to available tokenizers in Pygments: https://pygments.org/languages/ https://pygments.org/languages/ (Or the vast number of TextMate grammars in the wild, such as editors like VS Code have standardized on.) The "universality" of tokenizers is tough to beat, and though the tokenizers seem "dumber" than parser brethren, it's at a nice maxima for "good enough" for things like character-based diffs.
- pmeunier 6y ago
BlueTemplar 6y ago
Does that make working with it harder ? Can we still default to lines ? Am I misunderstanding ?
- chriswarbo 6y ago
  No. Yes. Not sure. From my understanding of the post: - Pijul patches were storing raw lines of text - Word-based diffing was suggested as an option - This option wasn't implemented due to complexity, and having to decide at repo creation time whether to store lines or words - Unrelated improvements to Pijul's performance resulted in patches storing offsets into a byte array, rather than raw text - Since offsets can point anywhere, patches are no longer limited to being line-based Lines are still the default.
jack_h 6y ago
My idea that I’ve bandied about here a few times would be to create some kind of a semantic database (not based on relational algebra). All tooling could deal with this rather than the text of the source code.
waterofclear 6y ago
Note that you could implement a Token or AST aware merging strategy for git as how you merge is an implementation detail that is not encoded into the repo.
- chriswarbo 6y ago
  Merging is only one aspect of version control. Also, merging (especially automatically) is limited by the quality of the data. For example, it's common for git to mix up function definitions by fixating on common lines (e.g. braces), e.g. -def foo() -{ +def bar() +{ + doBarThing; - doFooThing; } There are many ways to represent the same diff, but this sort of half-and-half result happens so often, and is such a minor problem, that it's usually not worth bothering to fix when committing. Yet it's the sort of weird input that can complicate later merges, cherry-picking, etc. A semantic-aware diff could do better. Again, there are many ways to represent the diff, but it could be as fine-grained as the token-level, e.g. def -foo+bar() { -doFooThing+doBarThing; } Or as coarse-grained as the definition level, e.g. -def foo() -{ - doFooThing; -} +def bar() +{ + doBarThing; +} Either way (or something in-between), these represent more meaningful changes, and hence provide more useful input to subsequent processing (e.g. merging).
  - waterofclear 6y ago
    I'm not sure what you mean. Git is snapshot based. There is nothing to fix when committing, you just commit the result of the merge. Any diff you see is just for display purposes or for input to the three-way merge algorithm. Other users might see a different result if they "git show" your commit if they have a different diff algorithm configured. Pijul is not immune from diff algorithm problems you are talking about except with Pijul it is part of the repo encoding unlike Git. IOW, git already has the freedom to use a merging strategy that understands tokens or AST since it is not hard-coded into the repo encoding.
dan-robertson 6y ago
I think this sounds nice but it feels difficult to me. One property you might want would be that, in some sense, parentheses would always remain balanced. I think this would be very hard if not impossible to get from the graph-of-byte-ranges representation. But I’d be excited if someone figured out how to do it. I think a particular part of the problem is to get the diff algorithm to match parentheses correctly. Consider some changes from A to B: 1A (a b) 1B (a b) (c d) 2A (define p () (a) (b) (c)) 2B (define q () (a) (b) ) (define q () (p) (c)) 3A (a b c d) 3B (a b) (c d) 4A (a b c ) 4B (a b) (c d) 5A (a b c) 5B (a b) (d) I think in these examples it’s relatively easy to pair up parentheses in a reasonable way though there are already some tricky cases. As you get more of a tree structure and want a diff algorithm that can think of operations like wrapping, splitting, and spreading as basic operations as well as appending and deleting, I think it becomes even harder to make the right call. Indeed I think computing this kind of diff of s-expressions is computationally a harder search problem than diffing files.

the_duke 6y ago

Encoding a generic, potentially versioned AST in S-expressions seems feasible. I believe the Unison language [1] does this for their code storage system. (Unison does not use traditional text storage but stores code in a normalized repository) [1] https://github.com/unisonweb/unison https://github.com/unisonweb/unison

chriswarbo 6y ago
There are multiple ways to do it, e.g. spreading data and parentheses across multiple lines to work better with line-based tools like git, or keeping revisions in the files themselves, etc. but most approaches require translation back and forth, which is a burden on those trying to handle the data (e.g. viewing diffs, bisecting to pin down a bug, etc.).

cb321 6y ago

The Haskell DVC system that pijul "sort of" evolved from (theory of patches-wise mostly, just being careful given the stringent IP/credit language afoot), darcs, had this sort of semantic concept. It could track, e.g., symbol renames very early on in darcs' history. I haven't looked at darcs in many years, but it would be unsurprising if it had evolved to similar generality like pluggable byte ranges.

pmeunier 6y ago
I'm the author, I understand how that comment of mine could be misinterpreted, which is why I removed it. It was just a reaction to a number of plagiarism events that have happened to me in recent years. At some point I've even been asked to review papers claiming to prove my own results.
- cb321 6y ago
  No big deal from my perspective. I was just explaining my cautious wording. I know you've been open about working with/from "ideas/people" in the darcs community, and good about the shoulders [1] the pijul work stands on/improves, and I also dislike people not giving credit where it is due. Sometimes a few bad apples ruin many things. FWIW, I liked the name "Anu" better. :-/ EDIT: and thanks for all your hard work on Pijul! [1] https://arxiv.org/abs/1311.3903 https://arxiv.org/abs/1311.3903

WorldMaker 6y ago

I explored this idea back in the day with darcs (though I don't think darcs' proposed character-based patch format "chunks" ever made it past the proposal stage), as some back and forth discussions led me to what I think is a perfect compromise on power, time (to compute), and universality. I explored using an off the shelf syntax highlighting tokenizer (Pygments specifically as a it was a Python prototype) [1] to build character-based diffs. Got surprisingly good results from what I tested. Most off the shelf syntax highlighters support a huge variety of languages. One advantage to using a syntax highlighting tokenizer/lexer is that they are designed to be fast (many of them need to be real time in text editors after all), and handle "degenerate cases" very well (text editors spend a lot of time on work in progress code that doesn't fully describe a complete compilable unit; version control systems just as well need to be good at storing work in progress states). The finished prototype I built created standard character-based unidiffs, and it sounds like could possibly be slotted directly into Pijul now. I'd be very interested to experiment further with it now that one of the patch algebra VCSes has finally adopted a "chunk" option. [1] https://github.com/WorldMaker/tokdiff https://github.com/WorldMaker/tokdiff (ETA: Suppose the first step is that it is time to get the band back together and update the prototype to Python 3.)

chriswarbo 6y ago
Very cool. I suppose these days tree-sitter would be one way to support a lot of languages at once ( https://tree-sitter.github.io/tree-sitter/#available-parsers https://tree-sitter.github.io/tree-sitter/#available-parsers )
- WorldMaker 6y ago
  Still a tiny fraction compared to available tokenizers in Pygments: https://pygments.org/languages/ https://pygments.org/languages/ (Or the vast number of TextMate grammars in the wild, such as editors like VS Code have standardized on.) The "universality" of tokenizers is tough to beat, and though the tokenizers seem "dumber" than parser brethren, it's at a nice maxima for "good enough" for things like character-based diffs.
pmeunier 6y ago

BlueTemplar 6y ago

Does that make working with it harder ? Can we still default to lines ? Am I misunderstanding ?

chriswarbo 6y ago
No. Yes. Not sure. From my understanding of the post: - Pijul patches were storing raw lines of text - Word-based diffing was suggested as an option - This option wasn't implemented due to complexity, and having to decide at repo creation time whether to store lines or words - Unrelated improvements to Pijul's performance resulted in patches storing offsets into a byte array, rather than raw text - Since offsets can point anywhere, patches are no longer limited to being line-based Lines are still the default.

jack_h 6y ago

My idea that I’ve bandied about here a few times would be to create some kind of a semantic database (not based on relational algebra). All tooling could deal with this rather than the text of the source code.

waterofclear 6y ago

Note that you could implement a Token or AST aware merging strategy for git as how you merge is an implementation detail that is not encoded into the repo.

chriswarbo 6y ago
Merging is only one aspect of version control. Also, merging (especially automatically) is limited by the quality of the data. For example, it's common for git to mix up function definitions by fixating on common lines (e.g. braces), e.g. -def foo() -{ +def bar() +{ + doBarThing; - doFooThing; } There are many ways to represent the same diff, but this sort of half-and-half result happens so often, and is such a minor problem, that it's usually not worth bothering to fix when committing. Yet it's the sort of weird input that can complicate later merges, cherry-picking, etc. A semantic-aware diff could do better. Again, there are many ways to represent the diff, but it could be as fine-grained as the token-level, e.g. def -foo+bar() { -doFooThing+doBarThing; } Or as coarse-grained as the definition level, e.g. -def foo() -{ - doFooThing; -} +def bar() +{ + doBarThing; +} Either way (or something in-between), these represent more meaningful changes, and hence provide more useful input to subsequent processing (e.g. merging).
- waterofclear 6y ago
  I'm not sure what you mean. Git is snapshot based. There is nothing to fix when committing, you just commit the result of the merge. Any diff you see is just for display purposes or for input to the three-way merge algorithm. Other users might see a different result if they "git show" your commit if they have a different diff algorithm configured. Pijul is not immune from diff algorithm problems you are talking about except with Pijul it is part of the repo encoding unlike Git. IOW, git already has the freedom to use a merging strategy that understands tokens or AST since it is not hard-coded into the repo encoding.

dan-robertson 6y ago

I think this sounds nice but it feels difficult to me. One property you might want would be that, in some sense, parentheses would always remain balanced. I think this would be very hard if not impossible to get from the graph-of-byte-ranges representation. But I’d be excited if someone figured out how to do it. I think a particular part of the problem is to get the diff algorithm to match parentheses correctly. Consider some changes from A to B: 1A (a b) 1B (a b) (c d) 2A (define p () (a) (b) (c)) 2B (define q () (a) (b) ) (define q () (p) (c)) 3A (a b c d) 3B (a b) (c d) 4A (a b c ) 4B (a b) (c d) 5A (a b c) 5B (a b) (d) I think in these examples it’s relatively easy to pair up parentheses in a reasonable way though there are already some tricky cases. As you get more of a tree structure and want a diff algorithm that can think of operations like wrapping, splitting, and spreading as basic operations as well as appending and deleting, I think it becomes even harder to make the right call. Indeed I think computing this kind of diff of s-expressions is computationally a harder search problem than diffing files.