8 ms·

Zig language server and cancellation

198 points by goranmoomin 3y ago

KRAKRISMOTT 3y ago
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?
- valenterry 3y ago
  Multi-colored? Google doesn't spit out anything meaningful and ChatGPT claims that Zig didn't exist in Sept 2021...
  - 59nadir 3y 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-your-function/ https://journal.stuffwithstuff.com/2015/02/01/what-color-is-...
    - valenterry 3y ago
      Oh yeah, I know about that. But that is commonly called "colored functions" not "multi colored functions" no? So I thought there was a difference.
      - littlestymaar 3y ago
        Zig aims to solve this “problem” by having functions that can be either async or not.
      - wtetzner 3y ago
        Right, colored functions are e.g. async or not async. In Zig, you can write a single function that works as both, which I assume is what multicolored means here.
        valenterry 3y ago
        That doesn't seem to make any sense to me - it should be then called uncolored functions no? Because they all look the same. But maybe that's what they ment to say.
        kps 3y ago
        They're generic over ‘color’ at compile time; the compiler generates code for normal and/or async contexts as necessary.
        valenterry 3y ago
        Right - so to the developer they all look the same, which means they are uncolored. If they are colored it means they look different (e.g. async vs sync).
  - a1369209993 3y 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-colors/ https://gavinhoward.com/2022/04/i-believe-zig-has-function-c...
  - hansvm 3y 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 3y 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 3y ago
  Nah, just a copying gc: http://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm 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 3y ago
    More specifically, semi space.
- esjeon 3y 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 3y 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).
ninepoints 3y 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.
- matklad 3y 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.
  - ninepoints 3y 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.
avgcorrection 3y ago
Should a language be designed with these things in mind? Or is it completely orthogonal?
- eptcyka 3y 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.
- matklad 3y 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-architectures-for-responsive-ide.html 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.
samsquire 3y 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 https://github.com/samsquire/preemptible-thread There is potential for a race, but that can be detected and worked around.
- girvo 3y 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 3y 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 https://man7.org/linux/man-pages/man7/epoll.7.html [2] https://dart.dev/articles/archive/zones https://dart.dev/articles/archive/zones [3] https://kotlinlang.org/docs/cancellation-and-timeouts.html#cancellation-is-cooperative https://kotlinlang.org/docs/cancellation-and-timeouts.html#c...`
tlarkworthy 3y 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 3y 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?

198 points by goranmoomin 3y ago

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?

valenterry 3y ago
Multi-colored? Google doesn't spit out anything meaningful and ChatGPT claims that Zig didn't exist in Sept 2021...
- 59nadir 3y 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-your-function/ https://journal.stuffwithstuff.com/2015/02/01/what-color-is-...
  - valenterry 3y ago
    Oh yeah, I know about that. But that is commonly called "colored functions" not "multi colored functions" no? So I thought there was a difference.
    - littlestymaar 3y ago
      Zig aims to solve this “problem” by having functions that can be either async or not.
    - wtetzner 3y ago
      Right, colored functions are e.g. async or not async. In Zig, you can write a single function that works as both, which I assume is what multicolored means here.
      - valenterry 3y ago
        That doesn't seem to make any sense to me - it should be then called uncolored functions no? Because they all look the same. But maybe that's what they ment to say.
        kps 3y ago
        They're generic over ‘color’ at compile time; the compiler generates code for normal and/or async contexts as necessary.
        valenterry 3y ago
        Right - so to the developer they all look the same, which means they are uncolored. If they are colored it means they look different (e.g. async vs sync).
- a1369209993 3y 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-colors/ https://gavinhoward.com/2022/04/i-believe-zig-has-function-c...
- hansvm 3y 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 3y 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 3y ago
Nah, just a copying gc: http://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm 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 3y ago
  More specifically, semi space.
esjeon 3y 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 3y 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).

ninepoints 3y 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.

matklad 3y 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.
- ninepoints 3y 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.

avgcorrection 3y ago

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

eptcyka 3y 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.
matklad 3y 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-architectures-for-responsive-ide.html 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.

samsquire 3y 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 https://github.com/samsquire/preemptible-thread There is potential for a race, but that can be detected and worked around.

girvo 3y 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 3y 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 https://man7.org/linux/man-pages/man7/epoll.7.html [2] https://dart.dev/articles/archive/zones https://dart.dev/articles/archive/zones [3] https://kotlinlang.org/docs/cancellation-and-timeouts.html#cancellation-is-cooperative https://kotlinlang.org/docs/cancellation-and-timeouts.html#c...`

tlarkworthy 3y 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 3y 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?