9 ms·

Abstract Syntax Tree for Patching Code and Assessing Code Quality

163 points by sidcool 5y ago

the_mitsuhiko 5y ago
If someone wants to do something similar: it’s better to use the 2to3 machinery than ast as it can retain comments.
- ianlevesque 5y ago
  They address that with a bit of a hack. > One of the problems of patching code using ast package of Python is that it loses all the formatting and comments of the original source code. This can be solved by making the patch script a little smarter. Instead of having it unparse the entire patched AST and write that to disk, we can make it unparse only the nodes it modified and insert the modified code at the corresponding line number in the file. The ast nodes have lineno attribute that can be used to retrieve the line number of the file to be injected the patched code with.
- avinassh 5y ago
  > 2to3 machinery Are you referring to this one - https://docs.python.org/3.9/library/2to3.html#to3-reference https://docs.python.org/3.9/library/2to3.html#to3-reference ?
  - the_mitsuhiko 5y ago
    Yes. The black formatter maintains a fork called blib2to3 which works better.
1337shadow 5y ago
Python's ast module is fantastic, we use it both to compile Python to Michelson[0], an assembly language for the Tezos blockchain, and Python to JavaScript[1]. However, for refactoring one might want to consider redbaron[2]. [0] https://yourlabs.io/pyratzlabs/pymich https://yourlabs.io/pyratzlabs/pymich [1] https://yourlabs.io/oss/ryzom/#javascript https://yourlabs.io/oss/ryzom/#javascript [2] https://redbaron.readthedocs.io/en/latest/ https://redbaron.readthedocs.io/en/latest/
- heinrichhartman 5y ago
  > However, for refactoring one might want to consider redbaron[2]. > [2] https://redbaron.readthedocs.io/en/latest/ https://redbaron.readthedocs.io/en/latest/ Thanks for the link. This looks really cool!
  - codethief 5y ago
    It does! But it also looks really… dead? > For now, RedBaron can be considered in alpha, the core is quite stable but it is not battle tested yet and is still a bit rough. > RedBaron [supports] up to python 3.7 grammar > Last commit: 11 Aug 2019 Does anyone know what's going on with the project?
- anitil 5y ago
  I love it as well. I'm working on a Python AST viewer tool at the moment [0] so I've been spending a bit of time playing with it lately. I'm thinking of calling it Pasta (Python AST view....A? I don't have a word that starts with A). [0] I only really have a gif - https://imgur.com/a/4YYdfmZ https://imgur.com/a/4YYdfmZ
  - joshuamorton 5y ago
    https://github.com/google/pasta https://github.com/google/pasta has you beat :p
    - anitil 5y ago
      Nooooo I guess it was pretty low hanging food.
  - austinjp 5y ago
    Oh, nice. Based on the diagrams and the sibbling comment about Google's pasta, perhaps name it spaghetti? :)
    - anitil 5y ago
heinrichhartman 5y ago
For me, this is the critical bit here: > One of the problems of patching code using ast package of Python is that it loses all the formatting and comments of the original source code. This can be solved by making the patch script a little smarter. Instead of having it unparse the entire patched AST and write that to disk, we can make it unparse only the nodes it modified and insert the modified code at the corresponding line number in the file. The ast nodes have lineno attribute that can be used to retrieve the line number of the file to be injected the patched code with. Parsing & Patching the AST is relatively easy, with the provided tooling. I always struggled to write the modifications out in a minimal way. Looks like line-number information does get you over this hump. EDIT: Looks like the python community has already a package for this: https://github.com/PyCQA/redbaron https://github.com/PyCQA/redbaron
- shpx 5y ago
  Autoformatting the code with Black before and after unparsing is how I avoided this problem.
- trankas 5y ago
  Never used it but it appears that Facebook/Instagram have a format preserving CST library for Python: https://github.com/Instagram/LibCST https://github.com/Instagram/LibCST
- BiteCode_dev 5y ago
  For preserving comments, use redbaron: https://github.com/PyCQA/redbaron https://github.com/PyCQA/redbaron It's lossless, besides, the API is much nicer.
- megous 5y ago
  I wrote a tool for refactoring JS a few years ago, and the way I solved this was to not modify the AST and regenerate the code from it, but only to use position information from it, and patch source code directly based on that positional information.
grdvnl 5y ago
I have done something similar using https://pybowler.io/ https://pybowler.io/. This library wraps the LibCST library and abstracts away some of the refactoring operations into nice wrapper functions.
- codethief 5y ago
  Are you sure it wraps the LibCST library (https://github.com/Instagram/LibCST https://github.com/Instagram/LibCST)? > Bowler builds on top of the Concrete Syntax Tree (CST) provided by lib2to3 in the standard library.
  - grdvnl 5y ago
    My bad. I don't know why I remember it as wrapping around LibCST.
1nj3ct0r 5y ago
I hope it's better to use the 2to3 machinery as everyone said in comments Here 2to3 machinery doc -> https://docs.python.org/3.9/library/2to3.html https://docs.python.org/3.9/library/2to3.html
- punnerud 5y ago
  Isn't 2to3 only for converting Python2 to Python3 code? Could possibly be used for code replacement in Python3, but does not seem like that is the purpose. From the bottom of the page on your link: "The lib2to3 module may be removed from the standard library in a future Python version."
neilv 5y ago
This AST-based programmatic source code transformations is a very useful approach to have in your software engineering toolbox. The authors correctly identify in section "Limitations" that you want to `unparse` only minimal changes, and avoid losing comments and formatting. I wrote a library to support doing similar things, with this in mind: https://www.neilvandyke.org/racket/progedit/ https://www.neilvandyke.org/racket/progedit/ Not clear from the documentation, but, although this particular library runs in Racket, it uses Racket's "syntax objects", so it can process not only Racket source code, but pretty much any language with a parser implemented in Racket. Also not clear from the documentation is that (although the example doesn't use it), syntax objects can also represent comments, and exact positional information, and can be annotated with things like type information and identifier resolution, plus there's always pretty printers... so you can in theory do very nice programmatic source code manipulations. I originally wrote `progedit` in 2012, for updating a package metadata file that's updated both manually and automatically. (And then made a point to factor out this functionality into a separate generalized open source library, and release it, as good reuse practice.) I later got a nice email from someone who said they'd used `progedit` to refactor millions of lines of code, which they thought would've been nonviable using regexps.
flakiness 5y ago
This kind of programmatic transformation is believed to be easier with statically typed languages. It's interesting to see how this folks identified patterns to effectively figure out the types of the specific bit of the code. I guess "good code" in the dynamic language tends to have this kind of uniformity / unsurprising nature which helps navigate the code without the type's help. On the other hand, code in statically typed languages tends to gets smarter on types to make it shorter, sometimes ending up hard-to-read (or at least glance) lines. I don't say which is worse, but this is good counterexample against still-widely-believed idea that dynamically typed languages lead shorter code while statically typed languages have longer (verbose) code.
- radicalbyte 5y ago
  I've taken to writing statically typed code with the IDE in mind - I almost always use one and they've become amazing and are no slower than text editors nowadays (thanks electron making text editors slow).
- maxdw101 5y ago
  Absolutely agree! Doing this with dynamic languages are much harder. Unless, of course, one works on ASTs at run-time.
raverbashing 5y ago
The technique is good, but the rules are not so great "Non explicable variable" do I really need to explain what for i in range(10): Means? No Not to mention some people will then use names like blah, oops, zing, etc (believe me, I've seen it happen - not on my team of course, they would have been given a stern talking to if that was the case)
joshuamorton 5y ago
https://news.ycombinator.com/item?id=26904951 https://news.ycombinator.com/item?id=26904951 For some recent similar discussion.
Aissen 5y ago
I did this recently with both lua (luaparse) and javascript (babel), and this is a fundamental tool to have in your toolbox once working with large codebases. Javascript has great tooling for this (see AST explorer and all the different libs it supports). Before the 1.0 promise, Go used "go fix" to automatically update old code, and the standard library even has tools to manipulate an AST. The linux kernel uses coccinelle for C code, which goes one step further, and lets you write "semantic patches", which is a DSL to do this in a compact way and without having to write code.
- chgibb 5y ago
  What was your solution to writing out your parsed Lua AST?
  - Aissen 5y ago
    Just checked and I did not output lua code, but I used the AST to do custom static checks; only the js part did code output, and used babel-plugin-recast to get identical formatting.
- ievans 5y ago
  Sounds like you know the language-specific AST tooling for your stack well, but if you are looking for AST patching that uses a generic approach across many languages, I'm a maintainer for a project named Semgrep (https://en.wikipedia.org/wiki/Semgrep#History https://en.wikipedia.org/wiki/Semgrep#History) which was created by one of the original coccinelle authors. It supports many more languages (~17 at various stages of development) and being able to do AST patching as in the original is one of the capabilities we're experimenting with: https://semgrep.dev/docs/experiments/overview/#autofix https://semgrep.dev/docs/experiments/overview/#autofix Would love your feedback!
Agingcoder 5y ago
We do the same thing, but with a statically typed language. We had started by distributing the changes manually across the team, which was slow and introduced bugs. We then switched to the fully automated approach, which was significantly fastet, and bug free.
plafl 5y ago
I once used clang to extract all input/output structures of a big C project. In my case was about generating tests. It's very satisfactory when the computer saves you so much time.
eska 5y ago
Trivial AST editing is what I severly miss when using languages that aren't based on s-expressions. Diffing ASTs, searching for patterns in ASTs, patching ASTs, .. can literally be implemented from scratch in few lines of code. Meanwhile I tried the same with C++, but it was a pain every time. For example I remember using the LLVM for Python API and it was just unstable (functions were removed etc), and mostly undocumented.
- dasyatidprime 5y ago
  Tangential curiosity: S-expression languages with lexical binding seem like they still require context-sensitive codewalkers in order to reliably search for patterns that involve any literal symbol that isn't constrained out of that mechanism¹, don't they? What's your strategy for this, just ignore it and hope for the best, or punt to interactive handling for any cases that look slightly tricky? (Or is that still small enough to count as "few lines"?) ¹ For instance, I believe CL forbids lexically binding symbols from the CL package in ways that might conflict with the original definitions. But if you want to find uses of a particular library call from some other non-special package in a sound way, then you have to assume someone might flet that name, due to the way locals work. The underlying codewalker issue is roughly dual to the functioning of non-hygienic macros.
  - thelopa 5y ago
    A naive AST traversal might also interpret some bit of fancy macro DSL as being “regular” code and have a spurious match. Any reliable whole-program source transformation in CL needs to leverage compiler-specific extensions (code walker, environment, etc.).
    - dasyatidprime 5y ago
      I was assuming that at minimum the forms would be fully macroexpanded first (though macrolet is its own problem there). I also have the sense this might be easier in some Scheme dialects, but I don't know any of them well enough to say (thus that's part of my question).
efitz 5y ago
In the security space we frequently have to mitigate potential injection attacks and parser vulnerabilities. Often this takes the form of checking for unexpected keywords or patterns in input, a la web application firewalls. For the past few years I’ve been advising teams that I work with that using allow and deny lists against ASTs prior to execution is a more effective technique than scanning input for patterns, because you sidestep encoding and fragmentation issues, which are common TTPs in bypassing input filters.
dwheeler 5y ago
This is a useful technique. But it'd be nice if library developers would make it much less necessary. Removing interfaces makes it hard to update, even with ast based techniques, and encourages developers to never upgrade. Then when a vulnerability is found it's hard to upgrade.
mbar84 5y ago
I wrote a criminally underused library that does much the same kind of transformations: https://github.com/mbarkhau/lib3to6/tree/master/src/lib3to6 https://github.com/mbarkhau/lib3to6/tree/master/src/lib3to6
- s_gourichon 5y ago
  Isn't the shorter https://github.com/mbarkhau/lib3to6 https://github.com/mbarkhau/lib3to6 a better URL? Because that one shows a README, not only a list of file names. (I like and use Gitlab,too, yet the gitlab link is not better because without Javascript it shows a mostly blanc page.)
sausage_dog 5y ago
If you like this idea, take a look at Nim. It has a syntax familiar to Python users with very capable AST metaprogramming built in.
oefrha 5y ago
> One of the problems of patching code using ast package of Python is that it loses all the formatting and comments of the original source code. What you actually want here is a concrete syntax tree preserving all the comments and whitespace. There’s a sort of built-in one as part of lib2to3 used by the likes of black and yapf. There’s also a good third party options now in the form of https://github.com/Instagram/LibCST https://github.com/Instagram/LibCST. There’s been talks about adding a CST module to PSL, but I don’t think the proposal went anywhere. https://bugs.python.org/issue33337 https://bugs.python.org/issue33337
maxdw101 5y ago
How scalable is this approach of using ASTs? Can you scale this to a single codebase with 500K+ lines? The article talks about multiple different code bases that together added up to 100K. Second, does one need to worry about getting this right in dynamically typed languages?
- shados 5y ago
  For both your question, a lot of large companies do thousands of pull requests a month/year using this methodology, so millions++ of lines of code, in any and all programming languages (including JavaScript, so your typed language there). The tooling (generally built internally on top of a couple of open source package) matters a lot here. You generally don't want to create a single pull request with hundreds of thousands of changes. The way I've done it and seen it done, is using tools that stagger/schedule pull requests, generally across packages (libraries, apps). You build a database of every package in your system. If they're across multiple repositories (as opposed to a monorepo) you keep track of that. When you need to make a changeset, you first narrow down your target (By language, using Github Search, OpenGrok, SourceGraph, whatever). Then for each match, you run your AST transform. If the transform returns a non-null change, you create a pull request for each one (usually using some kind of cron job system or something clever on top of k8s) Then teams that own the package can then review and merge them, or the system can auto-merge after tests pass or something. You really want to go 80/20 with your AST transform at large scale (building a script that will get it 100% right in every case would take too long), then do dry runs to see where it gets it wrong. Either tweak things or handle those cases manually. For dynamic languages, you can rely on rich AST parsers to give you more info (eg: for JavaScript you can use TypeScript to infer some info, even if the original code is not in TypeScript). You also rely heavily on tests to know if you're breaking something or not.
archi42 5y ago
Neat! The comments are an issue, though. But it can be solved: Just parse the comments as AST nodes, too. I did just that for a converter/transpiler which "updated" code written in an old DSL into a much newer variant of that DSL: A lexer, a parser, a transformer and a printer. The result was not as perfect as doing a mindful, manual transformations for each individual case - but the result is still well maintainable. And, most important, the whole task took us merely months instead of years. Also, Perl/regexes are awesome for this: With a one-shot transformation it does not matter if transforming 100000 lines takes 5m or 10s, so I could save a lot of time by letting lexer & parser try regexes (essentially guessing and some backtracking = stupid long lookahead) instead of writing a minimal LR parser ;-)
rikatee 5y ago
We use python's AST to power https://pypi.org/project/django-doctor/ https://pypi.org/project/django-doctor/ - it's a Django linter that suggests the fix and makes the change it suggests if you approve the change. Eventually we will replace AST with a CST (Concrete Syntax Tree) because the tricks we used maintain new lines and comments indicate CST was actually needed.
ay 5y ago
I had a problem of applying patches to the files that got indented differently meantime. So I wrote a tool that takes a context diff, rebuilds the before and after text, then parses both as vectors of (leading whitespaces, token), then creates a diff of those vectors ignoring the whitespaces, parses the target file as a similar vector, and applies this diff to such a vector (again with ignoring/copying whitespaces) - after which it reconstructs the text. The results are surprisingly robust, despite the relatively naive tokenization heuristic. https://github.com/ayourtch/tbpatch https://github.com/ayourtch/tbpatch

163 points by sidcool 5y ago

the_mitsuhiko 5y ago

If someone wants to do something similar: it’s better to use the 2to3 machinery than ast as it can retain comments.

ianlevesque 5y ago
They address that with a bit of a hack. > One of the problems of patching code using ast package of Python is that it loses all the formatting and comments of the original source code. This can be solved by making the patch script a little smarter. Instead of having it unparse the entire patched AST and write that to disk, we can make it unparse only the nodes it modified and insert the modified code at the corresponding line number in the file. The ast nodes have lineno attribute that can be used to retrieve the line number of the file to be injected the patched code with.
avinassh 5y ago
> 2to3 machinery Are you referring to this one - https://docs.python.org/3.9/library/2to3.html#to3-reference https://docs.python.org/3.9/library/2to3.html#to3-reference ?
- the_mitsuhiko 5y ago
  Yes. The black formatter maintains a fork called blib2to3 which works better.

1337shadow 5y ago

Python's ast module is fantastic, we use it both to compile Python to Michelson[0], an assembly language for the Tezos blockchain, and Python to JavaScript[1]. However, for refactoring one might want to consider redbaron[2]. [0] https://yourlabs.io/pyratzlabs/pymich https://yourlabs.io/pyratzlabs/pymich [1] https://yourlabs.io/oss/ryzom/#javascript https://yourlabs.io/oss/ryzom/#javascript [2] https://redbaron.readthedocs.io/en/latest/ https://redbaron.readthedocs.io/en/latest/

heinrichhartman 5y ago
> However, for refactoring one might want to consider redbaron[2]. > [2] https://redbaron.readthedocs.io/en/latest/ https://redbaron.readthedocs.io/en/latest/ Thanks for the link. This looks really cool!
- codethief 5y ago
  It does! But it also looks really… dead? > For now, RedBaron can be considered in alpha, the core is quite stable but it is not battle tested yet and is still a bit rough. > RedBaron [supports] up to python 3.7 grammar > Last commit: 11 Aug 2019 Does anyone know what's going on with the project?
anitil 5y ago
I love it as well. I'm working on a Python AST viewer tool at the moment [0] so I've been spending a bit of time playing with it lately. I'm thinking of calling it Pasta (Python AST view....A? I don't have a word that starts with A). [0] I only really have a gif - https://imgur.com/a/4YYdfmZ https://imgur.com/a/4YYdfmZ
- joshuamorton 5y ago
  https://github.com/google/pasta https://github.com/google/pasta has you beat :p
  - anitil 5y ago
    Nooooo I guess it was pretty low hanging food.
- austinjp 5y ago
  Oh, nice. Based on the diagrams and the sibbling comment about Google's pasta, perhaps name it spaghetti? :)
  - anitil 5y ago

heinrichhartman 5y ago

For me, this is the critical bit here: > One of the problems of patching code using ast package of Python is that it loses all the formatting and comments of the original source code. This can be solved by making the patch script a little smarter. Instead of having it unparse the entire patched AST and write that to disk, we can make it unparse only the nodes it modified and insert the modified code at the corresponding line number in the file. The ast nodes have lineno attribute that can be used to retrieve the line number of the file to be injected the patched code with. Parsing & Patching the AST is relatively easy, with the provided tooling. I always struggled to write the modifications out in a minimal way. Looks like line-number information does get you over this hump. EDIT: Looks like the python community has already a package for this: https://github.com/PyCQA/redbaron https://github.com/PyCQA/redbaron

shpx 5y ago
Autoformatting the code with Black before and after unparsing is how I avoided this problem.
trankas 5y ago
Never used it but it appears that Facebook/Instagram have a format preserving CST library for Python: https://github.com/Instagram/LibCST https://github.com/Instagram/LibCST
BiteCode_dev 5y ago
For preserving comments, use redbaron: https://github.com/PyCQA/redbaron https://github.com/PyCQA/redbaron It's lossless, besides, the API is much nicer.
megous 5y ago
I wrote a tool for refactoring JS a few years ago, and the way I solved this was to not modify the AST and regenerate the code from it, but only to use position information from it, and patch source code directly based on that positional information.

grdvnl 5y ago

I have done something similar using https://pybowler.io/ https://pybowler.io/. This library wraps the LibCST library and abstracts away some of the refactoring operations into nice wrapper functions.

codethief 5y ago
Are you sure it wraps the LibCST library (https://github.com/Instagram/LibCST https://github.com/Instagram/LibCST)? > Bowler builds on top of the Concrete Syntax Tree (CST) provided by lib2to3 in the standard library.
- grdvnl 5y ago
  My bad. I don't know why I remember it as wrapping around LibCST.

1nj3ct0r 5y ago

I hope it's better to use the 2to3 machinery as everyone said in comments Here 2to3 machinery doc -> https://docs.python.org/3.9/library/2to3.html https://docs.python.org/3.9/library/2to3.html

punnerud 5y ago
Isn't 2to3 only for converting Python2 to Python3 code? Could possibly be used for code replacement in Python3, but does not seem like that is the purpose. From the bottom of the page on your link: "The lib2to3 module may be removed from the standard library in a future Python version."

neilv 5y ago

This AST-based programmatic source code transformations is a very useful approach to have in your software engineering toolbox. The authors correctly identify in section "Limitations" that you want to `unparse` only minimal changes, and avoid losing comments and formatting. I wrote a library to support doing similar things, with this in mind: https://www.neilvandyke.org/racket/progedit/ https://www.neilvandyke.org/racket/progedit/ Not clear from the documentation, but, although this particular library runs in Racket, it uses Racket's "syntax objects", so it can process not only Racket source code, but pretty much any language with a parser implemented in Racket. Also not clear from the documentation is that (although the example doesn't use it), syntax objects can also represent comments, and exact positional information, and can be annotated with things like type information and identifier resolution, plus there's always pretty printers... so you can in theory do very nice programmatic source code manipulations. I originally wrote `progedit` in 2012, for updating a package metadata file that's updated both manually and automatically. (And then made a point to factor out this functionality into a separate generalized open source library, and release it, as good reuse practice.) I later got a nice email from someone who said they'd used `progedit` to refactor millions of lines of code, which they thought would've been nonviable using regexps.

flakiness 5y ago

This kind of programmatic transformation is believed to be easier with statically typed languages. It's interesting to see how this folks identified patterns to effectively figure out the types of the specific bit of the code. I guess "good code" in the dynamic language tends to have this kind of uniformity / unsurprising nature which helps navigate the code without the type's help. On the other hand, code in statically typed languages tends to gets smarter on types to make it shorter, sometimes ending up hard-to-read (or at least glance) lines. I don't say which is worse, but this is good counterexample against still-widely-believed idea that dynamically typed languages lead shorter code while statically typed languages have longer (verbose) code.

radicalbyte 5y ago
I've taken to writing statically typed code with the IDE in mind - I almost always use one and they've become amazing and are no slower than text editors nowadays (thanks electron making text editors slow).
maxdw101 5y ago
Absolutely agree! Doing this with dynamic languages are much harder. Unless, of course, one works on ASTs at run-time.

raverbashing 5y ago

The technique is good, but the rules are not so great "Non explicable variable" do I really need to explain what for i in range(10): Means? No Not to mention some people will then use names like blah, oops, zing, etc (believe me, I've seen it happen - not on my team of course, they would have been given a stern talking to if that was the case)

joshuamorton 5y ago

https://news.ycombinator.com/item?id=26904951 https://news.ycombinator.com/item?id=26904951 For some recent similar discussion.

Aissen 5y ago

I did this recently with both lua (luaparse) and javascript (babel), and this is a fundamental tool to have in your toolbox once working with large codebases. Javascript has great tooling for this (see AST explorer and all the different libs it supports). Before the 1.0 promise, Go used "go fix" to automatically update old code, and the standard library even has tools to manipulate an AST. The linux kernel uses coccinelle for C code, which goes one step further, and lets you write "semantic patches", which is a DSL to do this in a compact way and without having to write code.

chgibb 5y ago
What was your solution to writing out your parsed Lua AST?
- Aissen 5y ago
  Just checked and I did not output lua code, but I used the AST to do custom static checks; only the js part did code output, and used babel-plugin-recast to get identical formatting.
ievans 5y ago
Sounds like you know the language-specific AST tooling for your stack well, but if you are looking for AST patching that uses a generic approach across many languages, I'm a maintainer for a project named Semgrep (https://en.wikipedia.org/wiki/Semgrep#History https://en.wikipedia.org/wiki/Semgrep#History) which was created by one of the original coccinelle authors. It supports many more languages (~17 at various stages of development) and being able to do AST patching as in the original is one of the capabilities we're experimenting with: https://semgrep.dev/docs/experiments/overview/#autofix https://semgrep.dev/docs/experiments/overview/#autofix Would love your feedback!

Agingcoder 5y ago

We do the same thing, but with a statically typed language. We had started by distributing the changes manually across the team, which was slow and introduced bugs. We then switched to the fully automated approach, which was significantly fastet, and bug free.

plafl 5y ago

I once used clang to extract all input/output structures of a big C project. In my case was about generating tests. It's very satisfactory when the computer saves you so much time.

eska 5y ago

Trivial AST editing is what I severly miss when using languages that aren't based on s-expressions. Diffing ASTs, searching for patterns in ASTs, patching ASTs, .. can literally be implemented from scratch in few lines of code. Meanwhile I tried the same with C++, but it was a pain every time. For example I remember using the LLVM for Python API and it was just unstable (functions were removed etc), and mostly undocumented.

dasyatidprime 5y ago
Tangential curiosity: S-expression languages with lexical binding seem like they still require context-sensitive codewalkers in order to reliably search for patterns that involve any literal symbol that isn't constrained out of that mechanism¹, don't they? What's your strategy for this, just ignore it and hope for the best, or punt to interactive handling for any cases that look slightly tricky? (Or is that still small enough to count as "few lines"?) ¹ For instance, I believe CL forbids lexically binding symbols from the CL package in ways that might conflict with the original definitions. But if you want to find uses of a particular library call from some other non-special package in a sound way, then you have to assume someone might flet that name, due to the way locals work. The underlying codewalker issue is roughly dual to the functioning of non-hygienic macros.
- thelopa 5y ago
  A naive AST traversal might also interpret some bit of fancy macro DSL as being “regular” code and have a spurious match. Any reliable whole-program source transformation in CL needs to leverage compiler-specific extensions (code walker, environment, etc.).
  - dasyatidprime 5y ago
    I was assuming that at minimum the forms would be fully macroexpanded first (though macrolet is its own problem there). I also have the sense this might be easier in some Scheme dialects, but I don't know any of them well enough to say (thus that's part of my question).

efitz 5y ago

In the security space we frequently have to mitigate potential injection attacks and parser vulnerabilities. Often this takes the form of checking for unexpected keywords or patterns in input, a la web application firewalls. For the past few years I’ve been advising teams that I work with that using allow and deny lists against ASTs prior to execution is a more effective technique than scanning input for patterns, because you sidestep encoding and fragmentation issues, which are common TTPs in bypassing input filters.

dwheeler 5y ago

This is a useful technique. But it'd be nice if library developers would make it much less necessary. Removing interfaces makes it hard to update, even with ast based techniques, and encourages developers to never upgrade. Then when a vulnerability is found it's hard to upgrade.

mbar84 5y ago

I wrote a criminally underused library that does much the same kind of transformations: https://github.com/mbarkhau/lib3to6/tree/master/src/lib3to6 https://github.com/mbarkhau/lib3to6/tree/master/src/lib3to6

s_gourichon 5y ago
Isn't the shorter https://github.com/mbarkhau/lib3to6 https://github.com/mbarkhau/lib3to6 a better URL? Because that one shows a README, not only a list of file names. (I like and use Gitlab,too, yet the gitlab link is not better because without Javascript it shows a mostly blanc page.)

sausage_dog 5y ago

If you like this idea, take a look at Nim. It has a syntax familiar to Python users with very capable AST metaprogramming built in.

oefrha 5y ago

> One of the problems of patching code using ast package of Python is that it loses all the formatting and comments of the original source code. What you actually want here is a concrete syntax tree preserving all the comments and whitespace. There’s a sort of built-in one as part of lib2to3 used by the likes of black and yapf. There’s also a good third party options now in the form of https://github.com/Instagram/LibCST https://github.com/Instagram/LibCST. There’s been talks about adding a CST module to PSL, but I don’t think the proposal went anywhere. https://bugs.python.org/issue33337 https://bugs.python.org/issue33337

maxdw101 5y ago

How scalable is this approach of using ASTs? Can you scale this to a single codebase with 500K+ lines? The article talks about multiple different code bases that together added up to 100K. Second, does one need to worry about getting this right in dynamically typed languages?

shados 5y ago
For both your question, a lot of large companies do thousands of pull requests a month/year using this methodology, so millions++ of lines of code, in any and all programming languages (including JavaScript, so your typed language there). The tooling (generally built internally on top of a couple of open source package) matters a lot here. You generally don't want to create a single pull request with hundreds of thousands of changes. The way I've done it and seen it done, is using tools that stagger/schedule pull requests, generally across packages (libraries, apps). You build a database of every package in your system. If they're across multiple repositories (as opposed to a monorepo) you keep track of that. When you need to make a changeset, you first narrow down your target (By language, using Github Search, OpenGrok, SourceGraph, whatever). Then for each match, you run your AST transform. If the transform returns a non-null change, you create a pull request for each one (usually using some kind of cron job system or something clever on top of k8s) Then teams that own the package can then review and merge them, or the system can auto-merge after tests pass or something. You really want to go 80/20 with your AST transform at large scale (building a script that will get it 100% right in every case would take too long), then do dry runs to see where it gets it wrong. Either tweak things or handle those cases manually. For dynamic languages, you can rely on rich AST parsers to give you more info (eg: for JavaScript you can use TypeScript to infer some info, even if the original code is not in TypeScript). You also rely heavily on tests to know if you're breaking something or not.

archi42 5y ago

Neat! The comments are an issue, though. But it can be solved: Just parse the comments as AST nodes, too. I did just that for a converter/transpiler which "updated" code written in an old DSL into a much newer variant of that DSL: A lexer, a parser, a transformer and a printer. The result was not as perfect as doing a mindful, manual transformations for each individual case - but the result is still well maintainable. And, most important, the whole task took us merely months instead of years. Also, Perl/regexes are awesome for this: With a one-shot transformation it does not matter if transforming 100000 lines takes 5m or 10s, so I could save a lot of time by letting lexer & parser try regexes (essentially guessing and some backtracking = stupid long lookahead) instead of writing a minimal LR parser ;-)

rikatee 5y ago

We use python's AST to power https://pypi.org/project/django-doctor/ https://pypi.org/project/django-doctor/ - it's a Django linter that suggests the fix and makes the change it suggests if you approve the change. Eventually we will replace AST with a CST (Concrete Syntax Tree) because the tricks we used maintain new lines and comments indicate CST was actually needed.

ay 5y ago

I had a problem of applying patches to the files that got indented differently meantime. So I wrote a tool that takes a context diff, rebuilds the before and after text, then parses both as vectors of (leading whitespaces, token), then creates a diff of those vectors ignoring the whitespaces, parses the target file as a similar vector, and applies this diff to such a vector (again with ignoring/copying whitespaces) - after which it reconstructs the text. The results are surprisingly robust, despite the relatively naive tokenization heuristic. https://github.com/ayourtch/tbpatch https://github.com/ayourtch/tbpatch