The life and times of an Abstract Syntax Tree
blog.trailofbits.com
blog.trailofbits.com
It needs to be
> auto &lhs = *node_storage.emplace_back(make_unique(...));
instead of dereferencing lhs on the third line: emplace_back returns a reference to the inserted item, so it's a &unique_ptr...and that reference is invalidated by the rhs emplace_back reallocating the vector.
Rust also has a number of easy to use ways to do the same thing - slotmap or typed_arena are the standard, or just doing the vector indices scheme manually like at the bottom: this post is talking in circles around the fact the vector is really being used as an arena allocator without saying that, and so has obvious problems with it being extremely fragile to anyone who reads the type and expects it to be vector-like. It would probably do better explicitly saying that and linking to the wikipedia page or whatever, so the reader can look into the proper way of doing the code pattern.
Correct but only under the assumption that growing the backing storage of std::vector is implemented through a completely new instance of malloc, which indeed seems to be the case with libstdc++ implementation AFAICS.
Otherwise, if realloc had been used, such condition wouldn't be guaranteed since realloc can grow from existing memory and thus not invalidating all other references to it.
That said, I wonder if this behavior is mandated by the standard. https://en.cppreference.com/w/cpp/container/vector/emplace_b... implies that it is but I didn't check
If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise only the end() iterator is invalidated.The references also won't be invalidated if there's no need to reallocate, because the vector has enough space. Enumerating the cases in which this wouldn't cause UB does not change the fact that there are cases in which it would cause UB.
I'm sure it feels good to make comments like this, but it's a disservice to newer developers who may be misled by your comment about whether or not this code contains UB.
There surely could exist std::vector implementation with std::realloc implementation under the hood where the issue described wouldn't always be reproducible? I think that MSVC actually uses this technique AFAIR.
In that case, realloc will either
(1) grow the existing memory, perhaps default initialize it, and call it a day
(2) Or if growing the memory is not possible, (a) allocate a new region of memory, (b) memcpy the contents from the old block and (c) free the old block.
Perhaps I am missing something but I think those are all the guarantees that realloc is giving to you.
You either have to explicitly mark every node in the tree with a Box<T>, or nodes in the tree has to share lifetimes.
But since you're building the tree gradually by recursively scanning over some concrete syntax, that won't work.
Box<T> generally ruins your ability to do pattern matching, which is a deal-breaker when working with ASTs.
You can overcome some of the inconveniency by using a compiler extension called box patterns:
https://doc.rust-lang.org/beta/unstable-book/language-featur...
But the nicest solution I've found is to use a bump allocator (specifically, bumpalo).
You allocate a big chunk of memory for your AST, for which the lifetime is that of the bump allocator's handle.
And you tie the lifetime of all nodes of your AST with that lifetime.
The "drawback" is that you must free your entire AST at once. But you probably were going to anyways.
https://manishearth.github.io/blog/2021/03/15/arenas-in-rust...
> Box<T> generally ruins your ability to do pattern matching, which is a deal-breaker when working with ASTs.
For what it's worth I find that I never want to pass ownership when traversing ASTs with pattern matching, so I just bind everything by reference and don't experience this problem. YMMV.
The article capitulates:
> last time I asked how to do that in my company’s Slack channel, the responses I received were something like “don’t” and “why would you do that?” and “someone please call security.” It should not have been a surprise, as an AST is basically a linked list with extra steps, and Rust hates linked lists.
If I didn't tell myself "go find a good solution", I might have not found someone suggesting "Just use a bump allocator and make your nodes live until one exact, shared lifetime."
The article does agree in principle with this solution:
> In my experience, it’s quite easy to do away with the ceremony of making each node hold a reference count altogether, and instead decide on a more disciplined approach to ownership.
I think this is one of those examples where you get a principled, elegant and safe solution.
You just gotta find it first.
But here it is.
(Also, I read about it on a forum when searching for a better solution than box_patterns.)
You can get 90% of the way there by expanding the `vector`+`reserve` approach to keep a list of vectors, and allocate a new one whenever the previous one fills up. Replace the vectors with untyped byte buffers, and you can fill them with objects of different sizes.
This is quite reasonable to do even in Rust, e.g. with bumpalo: https://docs.rs/bumpalo/latest/bumpalo/.
raku’s killer app is its built-in Grammars … now you can write Actions that build AST right in your code. What does this mean? You can define your own Domain Specific Language (DSL) in your code and then just tag the blocks that use it. (Well raku is anyway a collaborative set of DSLs - eg for regexes, quoting constructs - but AST now makes this extensible by user code)
The first examples of this are Brainf*k and BASIC interpreters.
Checkout this introduction… https://dev.to/lizmat/rakuast-for-early-adopters-576n
- Don't have to think about this stuff, no matter how the AST is manipulated.
- Get locality for free from live objects being compacted together
A pretty good deal!
Feel free to add others
Additonally, is essential to provide an API to transform trees or even construct new ones using immutable ASTs like implemented in many compilers eg .NET Roslin or typescript TSC.
It only introduces parent pointers in a convenience wrapper layer, built on-demand as you traverse the tree - you could equivalently just pass the parent down as an argument to your tree walking functions.
(The ownership problem of parent pointers also goes away when you use the arena allocation approach that the post arrives at.)
Maybe it's a bit of Baader–Meinhof phenomenon at play?
tl:dr; use indices in Rust, they work pretty well, and proper use of the type-system helps with reducing overhead without sacrificing safety.
You still have to read and validate the code that an LLM emits, and some code will be faster for you to type than it is to prompt,wait,correct,test,adapt etc. It may even help in describing the problem to the LLM, as knowledge of the appropriate language terms will guide the context along the right lines.
And it's also fulfilling to design programming languages, whether general purpose or DSLs, at least in my opinion.
Don't fall for hype, this is not happening. We only got some okay snippet generators and some semi-adequate translators of simple pieces of code, from a limited set of languages to another.
There's nothing else. AI is not replacing programming yet. Or even soon.
You'd have thought they'd at least have cherry-picked an example where "Devin" did something useful, but in fact the Upwork job they set it loose on was just asking for a repository to be updated to build correctly (with latest tool versions), and Devin ignored this and went and introduced a bunch of bugs by making coding changes .. and then came back and fixed it's own bugs! (See Yannic Kilcher YouTube channel).
This tells me that anyone asserting what you said is either 1) not a developer, 2) taking buggy code at face value, or 3) taking 10x the time it would take an average developer to patiently guide the LLM to a working solution.
I think pipeline_peak's remark is unwarranted, but we probably should be trying to look ahead a number of decades (depending on how long you have left in your career) rather than only considering what's possible with today's LLMs. Two years ago, before ChatGPT and DALL-E 2, many would've considered what's being done now with generative AI as infeasible.
But even with current LLMs, I've been surprised at GPT-4 Turbo's ability to produce working scripts for problems that, though maybe not the most challenging, weren't entirely trivial. I'd speculate there are a number of useful tasks within the LLM's capacity and just needing a good integration. Maybe Microsoft releases a designer tool that allows creating static company websites, iterating based on client prompts and the model's vision capability, for example.
There's a ton of work to be done before we get to the stage of AI replacing actual jobs - in the shorter term things like planning/reasoning, working memory and factuality need to be addressed, and to learn to do an actual job then you need online (incremental real-time) learning too. These all need architectural innovation - they are not a matter of scaling up.
Bear in mind that in the 7 years(!) since the Transformer was invented, all we've done is basically a bunch of engineering work to scale them up... The pace of AI improvement may seem fast, but here we are after 7 years with SOTA $100M AIs still struggling to do very basic logical tasks like the recent Twitter A::B 4-rule letter replacement challenge! It seems pretty clear that AI isn't going to be replacing developers any time soon!
If you came to programming because you liked computers you'll find building an interpreter a fascinating topic in its own right. Building a compiler frontend is comprehensible and reading a modern/practical textbook (e.g. based on ANTLR or whatever is the latest parser generator in the wild) will illuminate so much for you.
You're highly unlikely to find a job with this skillset though. There are very few companies that do it, very small core teams, and there's competition with PhDs from top tier schools. The current leetcode fashion will ignore your niche knowledge right off the bat. So from this perspective the utility of knowing this stuff has always been a grey area regardless of the AI.
If you like money more than you like computers surely aim for an MLE position instead of SE/DE. But that's kind of a selective club too I imagine.