Zig language server and cancellation

https://matklad.github.io/2023/05/06/zig-language-server-and-cancellation.html

by goranmoomin • 3 years ago

198 68 3 years ago

matklad.github.io

Can this be done on the runtime level? Zig, if I recall, supports multi-colored functions. Would it be possible to terminate an awaitable early?

valenterry9• 3 years ago

Multi-colored? Google doesn't spit out anything meaningful and ChatGPT claims that Zig didn't exist in Sept 2021...

59nadir3• 3 years ago

I think in popular parlance the terminology comes from the "What color is your function?" article[0]. The idea is that "normal" and async functions are different colors and they don't mix. When you call an async function from a normal one you make the normal one async, i.e. if it had no color it now takes on the color of the async one, etc.

Zig has a system where calling an async function is actually doable while still leaving the calling function non-async.

0 - https://journal.stuffwithstuff.com/2015/02/01/what-color-is-...

a1369209993• 3 years ago

They're (presumably) refering to "colorblind" functions. (Note that "blind" is apt here: the color isn't visible, but functions still have color and will break in subtle ways if you try to use them as if they don't.[0])

Zig's approach is probably a improvement over bare async/await, but pre-javascript languages already had more of a improvement in the form of not having async/await. Implementing async/await at all makes the language worse unless there's a (preferably provably) universally-applicable way for functions to be (explicitly) generic about whether they're async or not.

0: https://gavinhoward.com/2022/04/i-believe-zig-has-function-c...

hansvm• 3 years ago

ChatGPT isn't great for spitting out accurate facts, especially if you just ask once, especially if you don't add additional details and otherwise engineer the prompt, especially if you're asking questions involving digits and numerals, and you especially if small details matter. Zig was definitely far enough along to have multi-colored functions over a year prior to that.

riwsky• 3 years ago

We divide the available memory in two equal parts, use one half as a working copy which accumulates useful objects and garbage, and then at some point switch the halves, copying the live objects (but not the garbage) over

So, generational garbage collection?

spullara• 3 years ago

Nah, just a copying gc:

http://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec2...

Generational has more heaps where objects are promoted between them when they last longer.

dontlaugh• 3 years ago

More specifically, semi space.

esjeon• 3 years ago

There's no generation here. Just live or dead objects. It also sounds like they don't scan the pool, and instead just deep-copy the top-level state object.

tankenmate• 3 years ago

Think of it more like a blue / green object store; but each switch only copies over valid objects (for some definition of valid; in use, type checked, etc).

ninepoints7• 3 years ago

As someone actually working on some symbol indexing stuff at the moment, I can mention that this model is ignoring some pretty important details, and I think there's some classic overengineering happening here (easy trap to fall into when you're still in the design space).

Generally, when you need a code completion action, it's expected that you have an AST (post semantic analysis). This AST is still very useful even after a user continues to edit the code! Outside of where the cursor is, most of the symbols, definitions, and declarations are relevant, and source locations can be easily translated from a previous version of the document, provided that deltas are tracked. Cancelling an existing translation unit parse on edit is wasteful, because the majority of the time, that parse will produce meaningful results. The better approach (IMO) is to let the parse finish, but immediately enqueue a subsequent parse (with some debouncing timer to avoid overly consuming user resources). If you wanted to level this up further, you could perform incremental parsing/analysis, provided your language supports it. In the presence of a preprocessor, this can be very difficult, but it's the next "upgrade" from the previous approach mentioned in my opinion.

matklad5• 3 years ago

This depends on the compilation model in use. If that’s a traditional pipeline of phases, where the result is an AST data structure for the whole CU which gets annotated with types, then, yes, “enqueue new analysis” makes sense.

If the compilation model lazy & query based, then theres’s just no “enqueue a subsequent parse”, but rather “give me the type on this thing doing as little analysis as possible”. You got to re-use symbols and declarations not because you heuristicsly adjust offsets and assume they are otherwise valid, but because underlying analysis reasons, precisely, they they are valid and re-usable.

The two models are quite different at the core, and aren’t really an evolution of one into another.

Which of the two approaches to use, and, consequently, whether to think about cancellation at all, depends heavily on the language in question. If the language allows for lazy analysis, it’s probably a better bet, as that gives you correct results faster.

ninepoints7• 3 years ago

I only know a little bit about zig, but I would have assumed that the latter mechanism you are describing isn't really possible. Most languages with "advanced" features and type systems really need a full semantic tree to do anything meaningful due to the complexities of compile time code and type instantiation.

Even if we are using this latter model, the user is only editing one file at a time. What if the completion source is in a different file altogether? Generally, you're going to be indexing the entire codebase anyways, so we're splitting hairs over a potential optimization in just one facet of the indexer.

levodelellis2• 3 years ago

I pretty much entirely agree with you. Below is a copy/paste of what I said when I saw this article elsewhere. What language is your LSP for?

I written a LSP for my prototype compiler. I don't like any of the options you listed. My LSP didn't do any typechecking, it didn't build an AST, it didn't need immutable data structures etc.
Typically when a person is typing into the editor the code is in a broken state (incomplete variable name, missing semi colon, maybe an open but no close parenthesis etc). What I did was look around what part is being edited and using the previous 'build' (when a user saves or ask the compiler to build), I would look up vars and type names. There's no need to rebuild everything on every keystroke. Maybe you can do it on a newline if you really wanted to but midsentence sounds like a bad place to try and you're not really gaining anything from compiling/parsing a single line change

avgcorrection2• 3 years ago

Should a language be designed with these things in mind? Or is it completely orthogonal?

eptcyka• 3 years ago

Designing syntax and semantics that are easier to parse can also make the language easier to understand to humans, as long as optimizing for these goals doesn't impede on useful language features.

matklad5• 3 years ago

Descriptively, yes, the shape of the language determines how you can structure an interactive compiler. There are at least three wildly different ways to do that:

https://rust-analyzer.github.io/blog/2020/07/20/three-archit...

Which one can work depends on the language in question. Java, Rust, C++ lead to different answers, and that’s not because of the “interesting” differences like borrowchecker vs gc, but rather due to the “boring” differences in name resolution and module system.

Prescriptively, whether we _should_ do this (or, rather, how much), is unclear.

My biased answer is that, while language designers talk a lot about making languages tooling friendly, there’s little of that actually happening (at least with “current” languages, “next” ones seem to fare better). Like, it was said that “rust macros are designed with tooling friendliness in mind”, but overall the language is pretty tooling-hostile, mostly for accidental reasons. It seems to me that if we _actually_ co-design a tooling-first language, without trying to innovate too much, but by just ensuring that existing techniques work robustly, we might arrive at a close, but meaningfully different point in the design space.

Specifically, here’s my version of IDE-friendliness diff for language design:

Push conditional compilation far further in the pipeline, such that it is done after all semantic analysis. This is a pre-requisite for making automated refactors which are _guaranteed_ to work.

Similarly, push meta programming further down, such that code analysis doesn’t invoke user-defined code (which might be arbitrary slow), but, at the same time, meta parts can fully reflect on existing code, including resolved types. C#-style source generators are an interesting design here.

Have strong signatures on micro and macro level. Macro, have well-defined compilation units with explicitly specified dag of dependencies and signature files. Micro, annotate types of the functions. Use tooling to reduce double-annotation burden.

Ensure that each source file can be somewhat deeply analyzed in complete isolation. The last two points should unlock both embarrassingly parallel (distributed) compilation, and snappy completion.

avgcorrection2• 3 years ago

Thanks for that.

It seems that some newer languages (like in the last ten years) either care about (1) batch compilation speed or (2) language design mostly unconstrained from having to have fast batch compilation. It would be interesting to see a third way: language design that takes into account all kinds of future interactive tooling by laying a good groundwork. So maybe from-scratch batch compilation ends up slow, but then it turns out to be fine in practice since you can distribute builds and cache things so that you only pay at most a one-time large cost. And then what you mostly have to deal with is incremental stuff.

the_mitsuhiko3• 3 years ago

there’s little of that actually happening (at least with “current” languages, “next” ones seem to fare better).

I'm not too involved but I think the languages that actually develop the tooling as part of the language design have traditionally done quite well at it in language design. Delphi/C#/TypeScript all had tooling built alongside the language and it shows.

Rust sadly made a ton of choices in the language that just make a lot of things hard, but enabled the type of ecosystem that exists today. So it has different tradeoffs. I'm quite amazed how well RLS is doing considering how hostile the language is to fast iteration.

littlestymaar2• 3 years ago

Push conditional compilation far further in the pipeline, such that it is done after all semantic analysis

So much this. I've idea how this would work un practice (like how you're supposed to accomodate antagonistic semantics which depend on the conditionnal compilation), but I hate #[feature(X)] with passion because of how brittle they are.

ComputerGuru• 3 years ago

Alex, I've been reading all your posts on Zig and Rust LSPs with great fervor and appreciate everything you've done for the community with rust-analyzer. Can I ask you about clangd, the llvm/C++ lsp? It seems to work tremendously well, far better than I naively ever thought it would even on massive codebases. I was using it from its first release and the quality ramped up rather quickly. Can I bug you to write up about it from your perspective and with your insights sometime and where we could benefit from their design choices and where we can't? And of course, the limitations of their approach?

It's ostensibly driven by the `compile_commands.json` produced by the compiler during a run (mapping each source file to the output .o and the command (w/ all options) that was used to generate it) but in reality that's just because C++ doesn't have its own build system so the tooling has no other way of knowing how a project is wired up. But aside from that, it's extremely fast and has fairly low latency for a language that's got a lot of the same warts that rust has (generics, monomorphization, macros, strong types, (limited) type inference, etc) especially when compared to all the other LSP offerings (although I think C++ compilation units are smaller than rust's, which has to help).

lerno• 3 years ago

It’s hard to push down conditional compilation too far without compromising its value, but one can still stop at a much later point than Zig does. (In fact, the fundamental choices of Zig in regards to compile time necessarily makes it hard to create good IDEa for)

In my C-like (C3), I retained an #if-like construct, which while semantic (unlike C’s) still meant dealing with sections of conditional code that had to be resolved before semantic checking could commence. To simplify I removed the ability to conditionally include struct members etc.

Doing more research I found D’s `version` interesting. In particular the non-block variant where the version is attached to a declaration.

I ended up creating a more flexible (and therefore actually less good) version of it as an attribute (`@if(cond)`) which then may be attached to any declaration. The advantage here is that at most this leads to some symbols having two (or more) different declarations (resolvable using the `@if`), which allows a lot of analysis even if the attribute hasn’t had its argument resolved.

I think this might be the way forward at the top level.

Inside of functions / macros, $if and friends are fine as they often do not matter for the overall analysis.

levodelellis2• 3 years ago

I wrote my (prototype) LSP in a completely different way from the article and I got very good results (autocomplete took less than 10ms, IIRC was <5). I didn't intentionally design my language for it but I did have to write my compiler in a way that would keep the data around so I can support it

samsquire3• 3 years ago

I am deeply interested in the multithreading, parallelism, async and coroutine design space and I journal about it everyday in my ideas journal. I am also interested in cancellation.

I wrote a toy very simple 1 scheduler thread:M kernel threads:N lightweight thread runtime in terrible Rust, C and Java.

Hot loops use a structure for its limit and looping variable. Then to cancel the loop, you set the looping variable to the limit from a scheduling thread, cancelling the loop. This is used for process switching and scheduling but it can also be used for cancellation.

Can create very responsive code this way, it's even possible to cancel while (true) loops by replacing them with while (!preempted) {}.

https://github.com/samsquire/preemptible-thread

There is potential for a race, but that can be detected and worked around.

girvo2• 3 years ago

Silly question, because I’ve been dealing with exactly this complexity in FreeRTOS and haven’t been able to solve it, but if you’re doing while (!preempted) doesn’t that mean that the preemption can only stop the loop after the current iteration of it finishes? I’ll dig into your code, but I’ve not been able to think of a (user space) way of cancelling a blocked thread (such that the thread is properly cleaned up/scope closes and destructors are called) myself

brabel• 3 years ago

As far as I know, it' basically impossible to interrupt a blocking IO call unless you're using something designed for preemptive scheduling, like epoll[1].

A Java Thread can be interrupted, but only if the runnable implementation "cooperates"... if it's blocking on a synchronous socket "read", it's going to stay blocked even after the Thread has been interrupted.

In a language like Dart, where async is mostly the default, it's possible to cancel every job running on a "Zone"[2] because the mechanism used for creating a new Future is interceptable by application code, which is pretty cool.

Kotlin coroutines have a mechanism for cancellation built-in[3] and it's also "cooperative", i.e. all suspend functions will cancel within the coroutine context, but a rogue coroutine that blocks on a blocking IO call will remain blocked (as I understand it - not sure if Kotlin provides ways to completely avoid blocking IO).

So I guess whatever language you use, there has to be points of "yielding" control where cancellation can occur... the `while (!preempted)` check is just one of them.

[1] https://man7.org/linux/man-pages/man7/epoll.7.html

[2] https://dart.dev/articles/archive/zones

[3] https://kotlinlang.org/docs/cancellation-and-timeouts.html#c...`

samsquire3• 3 years ago

Yes that's right.

I think as the other commentator said that you would need to use signals to interrupt within between elements of a loop.

I try not interrupt a hot for loop or while true loop to reduce performance impact of an if statement in a loop.

  register_loop(loops, 0, 1000000);
  for (; loops[0].loop_variable < loops[0].limit ; loops[0].loop_variable++) 
  {
    // Hot loop here
  }

It's difficult from another thread to know where in the loop another thread is in.

Then from another thread

  loops[0].loop_variable = loops[0].limit

tlarkworthy• 3 years ago

I would probably go for immutability, which unlocks memoization, which unlocks reuse of parsing computation. Then do everything strictly (no cancellation) so the whole this is super fast for the common case. I do wonder if grabase collection is too hard to solve though for memory managed languages. Reference counting?

Szpadel• 3 years ago

We can think about applying something like that for cancellation — without going for full immutability, we can let cancelled analysis to work with the old half-state, while we switch to the new one

if we want to cancel analysis basin on old state why do we need garbage collection and two states?

And how is garage collection way different from full immutability? In my understanding this is the same thing but with extra steps, you have to copy element instead updating it in place because existing copy might be used by already running analysis. Reference counting should give you similar benefits with less work needed, usually everything have only single reference (no analysis is using anything) and we could optimize it to modify it in place in that case, otherwise you just need to copy it once without requiring garbage collection later.

Am I missing something?

Zig language server and cancellation

Related Stories