jbellis 12 hours ago

If you're looking for something more complete and actively maintained, check out https://github.com/GumTreeDiff/gumtree.

(I evaluated semantic diff tools for use in Brokk but I ultimately went with standard textual diff; the main hangup that I couldn't get past is that semantic diff understandably works very poorly when you have a syntactically invalid file due to an in-progress edit.)

  • affyboi 6 hours ago

    Note that diffsitter isn’t abandoned or anything. I took a year off working and just started a new job so I’ve been busy. I’ve got a laundry list of stuff I want to do with this project that will get done (at some point)

  • pfdietz 11 hours ago

    The interesting problem here would be how do you produce a robust parse tree for invalid inputs, in the sense of stably parsing large sections of the text in ways that don't change too much. The tree would have to be an extension of an actual parse tree, with nodes indicating sections that couldn't be fully parsed or had errors. The diff algorithm would have to also be robust in the face of such error nodes.

    For the parsing problem, maybe something like Early's algorithm that tries to minimize an error term?

    You need this kind of robust parser for languages with preprocessors.

    • o11c 6 hours ago

      Unfortunately, this depends on making good decisions during language design; it's not something you can retrofit with a new lexer and parser.

      One very important rule is: no token can span more than one (possibly backslash-extended) line. This means having neither delimited comments (use multiple single-line comments; if your editor is too dumb for this you really need a new editor) nor multi-line strings (but you can do implicit concatenation of a string literal flavor that implicitly includes the newline; as a side-effect this fixes the indentation problem).

      If you don't follow this rule, you might as well give up on robustness, because how else are you going to ever resynchronize after an error?

      For parsing you can generally just aggressively pop on mismatched parens, unexpected semicolons, or on keywords only allowed in a top-ish level context. Of course, if your language is insane (like C typedefs), you might not be able to parse the next top-level function/class anyway. GNU statement-expressions, by contrast, are an actually useful thing that requires some thought. But again, language design choices can mitigate this (such as making classes values, template argument equivalent to array indexing, and statements expressions).

      • pfdietz 6 hours ago

        > how else are you going to ever resynchronize after an error?

        An error-cost-minimizing dynamic programming parser could do this.

        • o11c 4 hours ago

          That fundamentally misunderstands the problem in multiple ways:

          * this is still during lexing, not yet to parsing

          * there are multiple valid token sequences that vary only with a single character at the start of the file. This is very common with Python multi-line strings in particular, since they are widely used as docstrings.

  • pests 11 hours ago

    I watched a video long ago about how the Roslyn C# compiler handled this but I forget the details.

mertleee 2 hours ago

This is really cool.

Although - for more exotic applications parsing structural data I've found langium is far more capable as a platform. Typescript is also a pleasant departure from common AST tools.

vrm 9 hours ago

This is neat! I think in general there are really deep connections between semantically meaningful diffs (across modalities) and supervision of AI models. You might imagine a human-in-the-loop workflow where the human makes edits to a particular generation and then those edits are used as supervision for a future implementation of that thing. We did some related work here: https://www.tensorzero.com/blog/automatically-evaluating-ai-... on the coding use case but I'm interested in all the different approaches to the problem and especially on less structured domains.

esafak 10 hours ago

Some make a semantic diff splitter please! Break up big commits into small, atomic, meaningful ones.

  • 0x457 9 hours ago
    • esafak 8 hours ago

      I can't make sense of that link. How many parts was the diff split up into, and along what lines?

      • 0x457 8 hours ago

        Yeah, I don't know why I linked that as an example. Wanted to show structure of a patch. Each commit of a patch already has everything ready to be processed and chunked IF you keep them - small, atomic, semantically meaningful. As in do smaller commits.

        • mdaniel 10 minutes ago

          > > Some make a semantic diff splitter please! Break up big commits into small, atomic, meaningful ones.

          > Each commit of a patch already has everything ready to be processed and chunked IF you keep them - small, atomic, semantically meaningful. As in do smaller commits.

          Reads like:

          User1: I need help with my colleagues who do not make independent, small, semantically intact commits

          User2: well, have you tried making smaller, more independent, semantically intact commits?

          ---

          My interpretation of the wish is to convert this, where they have intermixed two semantically independent changes in one diff:

              +++ a/alpha.py
              --- b/alpha.py
          
               def doit():
              -    awesome = 3.14
              +    awesome = 4.56
          
              -    print("my dog is fluffy")
              +    print("my cat is fluffy")
          
          into this

              +++ a/alpha.py
              --- b/alpha.py
          
               def doit():
              -    awesome = 3.14
              +    awesome = 4.56
          
                   print("my dog is fluffy")
          
              +++ a/alpha.py
              --- b/alpha.py
          
               def doit():
                   awesome = 3.14
          
              -    print("my dog is fluffy")
              +    print("my cat is fluffy")
          
          where each one could be cherry-picked at will because they don't semantically collide

          The semantics part would be knowing that this one could not be split in that manner, because the cherry-pick would change more than just a few lines, it would change the behavior

              +++ a/alpha.py
              --- b/alpha.py
          
               def doit():
              -    the_weight = 3.14
              +    the_weight = 4.56
          
              -    print("my dog weighs %f", the_weight)
              +    print("my cat weighs %f", the_weight)
          
          I'm sure these are very contrived examples, but it's the smallest one I could whip up offhand
pmkary 9 hours ago

What a genius idea.

  • affyboi 6 hours ago

    Nah I think most people could make something like this in a weekend

the__alchemist 11 hours ago

Is there an anti-tree-sitter version too?

  • davepeck 11 hours ago

    yes, although it's sort of the same as Context-Free-Typing-sitter