Right now, if a query were to invoke fork on its database and then perform other queries, those dependencies would not be tracked. Seems bad!

UPDATE: We rule out using fork within queries, but we still need some way to invoke queries in parallel. I imagined something like db.query(Foo).for_all(keys), which would execute keys across a thread-pool, but we have to think about it.

I was thinking that it would be useful if queries could get access to the old, invalidated value and be allowed to "mine it for spare parts" -- at minimum this would permit vectors to be truncated and hence re-use the memory, but one can also imagine scenarios where we want to do "delicate", hand-coded incremental updates.

Some examples:

• Incremental re-parse after a diff is applied
• Trait matching, chalk-style, where we can generally keep the tables in between queries but if the set of impls etc changes we may want to throw them away

I suppose incremental re-parse could be done by having the inputs to the system not be raw text but rather the parse trees.

The trait matching integration is a bit trickier. I have to think about how that would best work. The most naive thing would be to use a "volatile" query and just recreate the cached state on each revision; a trickier question would be whether we ever know which bits can be re-used.

This is a sister issue to #6 to handle the case of "fixed-point computations" or other cases where a cycles are expected and do not represent user error.

Some examples that have arisen in the context of rustc:

• Inlining when tracing across call graphs
• Trait resolution
• ...

I think we should punt on this issue for a while. It's an area of active research in the incremental computation community, to start, and I've found that in most instances, it's desirable to reframe the issue in a different way. e.g., to handle inlining, you can have one query that finds the call graph, then other queries that traverse it, avoiding cycles.

That said, if we did want some semantics, we could probably implement a Prolog-like tabling semantics fairly easily. This is specific to a "fixed-point" computation where you are trying to find a set of things. The idea would be that when we detect a cycle we return an empty set to start, but we mark the cycle participants. Then, when the last participant in the cycle finishes, we save the result R we got and re-execute the cycle. This time, when we return that last result R. We again mark the participants in the cycle though and we keep re-executing as long as the result is changing (it should be growing each time).

I am seeing an assertion error in salsa's from this code:

rust-lang/rust-analyzer@3680ce5

This snippet has everything:

• it execute queries in parallel using rayon
• it launches gc afterwards
• it gets cancelled

This is the line that triggers assertion error:

https://github.com/salsa-rs/salsa/blob/v0.6.2/src/derived.rs#L537

Here's what I see in the logs:

ERROR [ra_analysis::imp] start RootDatabase { runtime: Runtime { id: RuntimeId { counter: 10 }, revision: R26902 } }
ERROR [ra_analysis::imp] files, symbols = 13450 13450
ERROR [ra_analysis::imp] end RootDatabase { runtime: Runtime { id: RuntimeId { counter: 10 }, revision: R26903 } }
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: RecvError', libcore/result.rs:1009:5
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `RuntimeId { counter: 279 }`,
 right: `RuntimeId { counter: 281 }`', /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:537:21
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:477
   5: std::panicking::continue_panic_fmt
             at libstd/panicking.rs:391
   6: rust_begin_unwind
             at libstd/panicking.rs:326
   7: core::panicking::panic_fmt
             at libcore/panicking.rs:77
   8: core::result::unwrap_failed
             at libcore/macros.rs:26
   9: <salsa::derived::DerivedStorage<DB, Q, MP>>::read_upgrade
             at libcore/result.rs:808
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:457
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:285
  10: <salsa::derived::DerivedStorage<DB, Q, MP> as salsa::plumbing::QueryStorageOps<DB, Q>>::try_fetch
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:266
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:612
  11: <salsa::QueryTable<'_, DB, Q>>::get
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/lib.rs:131
  12: ra_analysis::Analysis::on_enter
             at /home/matklad/projects/rust-analyzer/<::salsa::query_group macros>:25
             at crates/ra_analysis/src/imp.rs:178
             at crates/ra_analysis/src/lib.rs:224
  13: ra_lsp_server::main_loop::handlers::handle_on_enter
             at crates/ra_lsp_server/src/main_loop/handlers.rs:91
  14: std::panicking::try::do_call
             at crates/ra_lsp_server/src/main_loop/mod.rs:374
             at libstd/panic.rs:313
             at libstd/panicking.rs:310
  15: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  16: <rayon_core::job::HeapJob<BODY> as rayon_core::job::Job>::execute
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/unwind.rs:18
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/spawn/mod.rs:72
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/job.rs:156
  17: rayon_core::registry::WorkerThread::wait_until_cold
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/job.rs:60
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:584
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:568
  18: rayon_core::registry::main_loop
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:544
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:666
  19: std::panicking::try::do_call
             at libstd/thread/mod.rs:409
             at libstd/panic.rs:313
             at libstd/panicking.rs:310
  20: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  21: <F as alloc::boxed::FnBox<A>>::call_box
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at libstd/thread/mod.rs:408
             at liballoc/boxed.rs:646
  22: std::sys_common::thread::start_thread
             at liballoc/boxed.rs:656
             at libstd/sys_common/thread.rs:24
  23: std::sys::unix::thread::Thread::new::thread_start
             at libstd/sys/unix/thread.rs:90
  24: start_thread
  25: __GI___clone
ERROR [ra_lsp_server::main_loop] thread panicked :(
stack backtrace:
   0: ERRORstd [::ra_analysis::impsys] ::start unix::RootDatabasebacktrace {:: tracingruntime::: impRuntime:: {unwind_backtrace 
id: RuntimeId            {   at counter: libstd/sys/unix/backtrace/tracing/gcc_s.rs283: }49,
 revision  :  R126903 }:  }
std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:477
   5: std::panicking::continue_panic_fmt
             at libstd/panicking.rs:391
   6: std::panicking::begin_panic_fmt
             at libstd/panicking.rs:346
   7: <salsa::derived::DerivedStorage<DB, Q, MP>>::overwrite_placeholder
             at /home/matklad/projects/rust-analyzer/<::std::macros::panic macros>:8
   8: <salsa::derived::DerivedStorage<DB, Q, MP>>::read_upgrade
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:397
   9: <salsa::derived::DerivedStorage<DB, Q, MP> as salsa::plumbing::QueryStorageOps<DB, Q>>::try_fetch
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:266
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:612
  10: <salsa::QueryTable<'_, DB, Q>>::get
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/lib.rs:131
  11: ra_analysis::Analysis::folding_ranges
             at /home/matklad/projects/rust-analyzer/<::salsa::query_group macros>:25
             at crates/ra_analysis/src/imp.rs:178
             at crates/ra_analysis/src/lib.rs:242
  12: ra_lsp_server::main_loop::handlers::handle_folding_range
             at crates/ra_lsp_server/src/main_loop/handlers.rs:422
  13: std::panicking::try::do_call
             at crates/ra_lsp_server/src/main_loop/mod.rs:374
             at libstd/panic.rs:313
             at libstd/panicking.rs:310
  14: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  15: <rayon_core::job::HeapJob<BODY> as rayon_core::job::Job>::execute
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/unwind.rs:18
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/spawn/mod.rs:72
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/job.rs:156
  16: rayon_core::registry::WorkerThread::wait_until_cold
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/job.rs:60
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:584
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:568
  17: rayon_core::registry::main_loop
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:544
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:666
  18: std::panicking::try::do_call
             at libstd/thread/mod.rs:409
             at libstd/panic.rs:313
             at libstd/panicking.rs:310
  19: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  20: <F as alloc::boxed::FnBox<A>>::call_box
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at libstd/thread/mod.rs:408
             at liballoc/boxed.rs:646
  21: std::sys_common::thread::start_thread
             at liballoc/boxed.rs:656
             at libstd/sys_common/thread.rs:24
  22: std::sys::unix::thread::Thread::new::thread_start
             at libstd/sys/unix/thread.rs:90
  23: start_thread
  24: __GI___clone
ERROR [ra_lsp_server::main_loop] thread 'thread panicked :(<unnamed>
' panicked at 'expected in-progress state', /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:551:22
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:477
   5: std::panicking::begin_panic
             at libstd/panicking.rs:411
   6: <salsa::derived::DerivedStorage<DB, Q, MP>>::overwrite_placeholder
             at /home/matklad/projects/rust-analyzer/<::std::macros::panic macros>:3
   7: <salsa::derived::DerivedStorage<DB, Q, MP>>::read_upgrade
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:397
   8: <salsa::derived::DerivedStorage<DB, Q, MP> as salsa::plumbing::QueryStorageOps<DB, Q>>::try_fetch
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:266
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:612
   9: ra_analysis::db::SyntaxDatabase::file_syntax
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/lib.rs:131
             at /home/matklad/projects/rust-analyzer/<::salsa::query_group macros>:25
  10: ra_analysis::descriptors::module::imp::submodules
             at crates/ra_analysis/src/descriptors/module/imp.rs:22
  11: <salsa::runtime::Runtime<DB>>::execute_query_implementation
             at /home/matklad/projects/rust-analyzer/<::salsa::query_group macros>:58
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:338
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/runtime.rs:255
  12: <salsa::derived::DerivedStorage<DB, Q, MP>>::read_upgrade
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:331
  13: <salsa::derived::DerivedStorage<DB, Q, MP> as salsa::plumbing::QueryStorageOps<DB, Q>>::maybe_changed_since
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:703
  14: <salsa::derived::DerivedStorage<DB, Q, MP>>::read_upgrade
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:900
             at libcore/iter/mod.rs:1506
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:898
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:310
  15: <salsa::derived::DerivedStorage<DB, Q, MP> as salsa::plumbing::QueryStorageOps<DB, Q>>::try_fetch
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:266
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/derived.rs:612
  16: ra_analysis::descriptors::module::ModulesDatabase::module_tree
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.6.2/src/lib.rs:131
             at /home/matklad/projects/rust-analyzer/<::salsa::query_group macros>:25
  17: ra_analysis::imp::AnalysisImpl::diagnostics
             at crates/ra_analysis/src/imp.rs:206
             at crates/ra_analysis/src/imp.rs:349
  18: ra_analysis::Analysis::diagnostics
             at crates/ra_analysis/src/lib.rs:283
  19: ra_lsp_server::main_loop::handlers::publish_diagnostics
             at crates/ra_lsp_server/src/main_loop/handlers.rs:594
  20: std::panicking::try::do_call
             at crates/ra_lsp_server/src/main_loop/mod.rs:410
             at libstd/panic.rs:313
             at libstd/panicking.rs:310
  21: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  22: <rayon_core::job::HeapJob<BODY> as rayon_core::job::Job>::execute
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/unwind.rs:18
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/spawn/mod.rs:72
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/job.rs:156
  23: rayon_core::registry::WorkerThread::wait_until_cold
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/job.rs:60
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:584
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:568
  24: rayon_core::registry::main_loop
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:544
             at /home/matklad/.cargo/registry/src/github.com-1ecc6299db9ec823/rayon-core-1.4.1/src/registry.rs:666
  25: std::panicking::try::do_call
             at libstd/thread/mod.rs:409
             at libstd/panic.rs:313
             at libstd/panicking.rs:310
  26: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  27: <F as alloc::boxed::FnBox<A>>::call_box
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at libstd/thread/mod.rs:408
             at liballoc/boxed.rs:646
  28: std::sys_common::thread::start_thread
             at liballoc/boxed.rs:656
             at libstd/sys_common/thread.rs:24
  29: std::sys::unix::thread::Thread::new::thread_start
             at libstd/sys/unix/thread.rs:90
  30: start_thread
  31: __GI___clone
ERROR [ra_lsp_server::main_loop] thread panicked :(
ERROR [ra_analysis::imp] files, symbols = 13450 13450
ERROR [ra_analysis::imp] end RootDatabase { runtime: Runtime { id: RuntimeId { counter: 283 }, revision: R26903 } }

We have the Hello World example, which serves as a basic tutorial, but it does not show off some of salsa's other features, like set_constant or parallel snapshots.

I think the first step here is actually adding a mdbook setup to the repository and configuring travis to publish it (along with the "master" rustdocs, I imagine).

I am seeing canceled queries in Rust analyzer, and I want to blame salsa for them, though I am not sure :-)

Here's the code where I am seeing the issue:

rust-lang/rust-analyzer@54c8907

The most interesting file is the log. In the log, we see a single query which is canceled:

https://github.com/rust-analyzer/rust-analyzer/blob/54c89073b2e6b3abb74f6b2695a31a4f94a50d66/log/ra_lsp_server_2018-10-25_15-49-51.log#L9

Here's the source of the log entry.

And, at a much higher revisions, we see that some quires return an Err(Canceled) result:

https://github.com/rust-analyzer/rust-analyzer/blob/54c89073b2e6b3abb74f6b2695a31a4f94a50d66/log/ra_lsp_server_2018-10-25_15-49-51.log#L588-L591

I am observing a deadlock. Not sure who is to blame, will investigate (probably next week), so just dumping the stack trace here for now:

https://gist.github.com/matklad/5b797c243d2dac288732601c4e8c7b89

I was thinking that we should refactor the query_prototype macro so that it also generates a storage struct for all the queries defined within the trait. So something like this:

query_prototype! {
    trait Foo: salsa::QueryContext {
        fn bar() for Bar();
        fn baz() for Baz();
    } in struct FooStorage; // <-- give the name of the storage struct here
}

Here the FooStorage struct would define fields bar and baz with the storage for those queries. Then when we define the complete query context storage, we need only reference the FooStorage type:

query_context_storage! {
    struct QueryContextStorage {
        FooStorage
    }
}

In particular, we don't have to list out all the queries in Foo again. This is nice for two reasons:

• More DRY
• You can implement two "query context traits" (query groups, whatever) that have overlapping names for methods -- only the query groups have to have unique names.

I remember that in the shower I had a sort of elaborate scheme involving a generic Get<T> trait as well, that would allow you to get the storage fields without having to name the actual field, but I can't remember exactly what I was thinking.

Anyway, I'm not sure 100% of the setup — I'd like to avoid having to give a name to the storage type, for example, though I don't see an obvious alternative — but I feel like something in this direction would be nice.

Right now, for incremental computation, we verify that the return value of a query is the same as its previous value by using a full equality comparison. In Rustc, we often just rely on hashing instead, which is useful as values can sometimes grow to be quite big. Relying on hashing also has advantages if we ever want to support serialization to disk (#10). It can also be used to support a new incremental mode, where we store the hash but not the actual value (which we recompute on demand).

Supporting hashing isn't hard but it requires a bit of work. I imagine we'd define a stable-hash trait -- I'd love to use the digest-hash crate but it seems to be too specialized for cryptography. e.g., it's not implemented for usize or vectors.

Another option is to use the Hash trait, of course. In Rustc, we opted not to, because many hash implementations are not stable. A common example is interned data: it's convenient to hash the pointer or index, but that's not stable across implementations (though there is another option: you can compute the hash once, when the value is interned, and reuse that; not sure why we don't do that).

This might be useful for “per-request” allocators: each runtime can store an Arena, which allocates cheaply and deallocates when the top-level query ends.

I don’t need this feature right now, just something to think about: this looks like another (weak) argument for having a separate “query is in progress” type.

Pull request #63 added a salsa_event callback that fires at particular times. It would be nice, I imagine, to have an event that fires when a particular descriptor is collected by the garbage collector. This is a touch tricky though because we have to create the descriptor and the code doesn't currently have enough information on hand to do that.

I don't think the Send bounds on keys/values are really needed right now:

The motivation was that we wanted to ensure cross-thread compatibility. But so long as the queries are all statically typed (which is true right now), auto traits take care of that, and including these bounds prevent people from using "thread-local types" (e.g., Rc) if they so choose.

As currently implemented, old query results are going to pile up in the hash tables. We need a method that allows users to specify a root set of query results -- that is, queries plus keys. We can then trace all the values reachable from there and evict the rest.

Currently, we have MemoizedStorage which, for each query, remembers a list of dependencies and the result value, and DependencyStorage, which remembers only dependencies (to save storage).

They could be merged into an Storage which remembers deps and "optional" result. That way, we'll be able to implement smart strategies for evicting large unused results (something like LRU).

cc https://github.com/nikomatsakis/salsa/issues/7#issuecomment-425893534 and https://github.com/nikomatsakis/salsa/pull/14

Continuing nikomatsakis#4 (comment) discussion.

This is what I expecteded to start:
Query computation runs async from main input (perhaps we'll use a Future setup or something)
When user input arrives, we process it after current query completes.

This is definitely a good start, but, for IDEs, I think we'll need something better eventually. Let me present a couple of important IDE interaction patterns.

Async Annotations

These are the cases when IDE reacts on user's input or external changes. Examples: syntax highlighting, warnings and errors (which all are various text decorations). It's OK if they appear with a noticeable delay after the user types. However, for syntax highlighting and syntax errors specifically, a noticeable delay is noticeably annoying. For this reason, in IntelliJ they are computed in phases: first, lexical analysis is used to apply basic highlighting, then, parsing is done to report syntax errors, then, precise syntax highlighting is done (which uses some semantic information), and, lastly, errors and warnings are computed.

For this case, it's important to be able to apply changes and compute syntax highlighting without waiting for previous semantic analysis results (which might take some time to calculate, especially if we have a mode that computes errors across the whole project, and not only opened files). Failure to do so will be annoying (why I sometimes get syntax errors immediately, and sometimes after a delay?), but most certainly not a deal breaker.

Sync Actions

These are the cases when IDE reacts to the explicit user's request. Examples: indenting cursor after Enter, re-indenting lines on } typed, extend selection. Most of these things need only a syntax tree, but sometimes semantic is useful as well, for example, in postfix-templates case. Postfix template is this thing: user has an expression, whose value is an enum: compute_thing(stuff), user types .match and pressed tab: compute_thing(stuff).match, and gets a match statement with filled variants: match compute_thing(stuff) { Ok(think) => ... }.

For such "sync" actions, latency directly affects the user, so being able to apply changes while a long-running computation on the old state is running, is not simply a QoL improvement, but rather a question of "can we do this feature at all?".

Now that we are using procedural macros, before we call salsa-rs/salsa-rfcs#1 complete, we really ought to have tests checking that we get an error in various illegal conditions. Ideally, we'd also have a tolerable error message. =)

Some examples:

#[salsa::query_group(foo)] // <-- no `foo` etc permitted here
trait QueryGroup { .. }

We can make tests like these by using compile-fail doc tests:

However, for comprehensive tests, we don't necessarily want them to appear in publicly visible docs. Therefore, we can attach them to dummy functions, e.g. the query_group implementation function:

I would like eventually to support the ability to extend the set of queries dynamically (e.g., for plugins). I imagine that said queries would have to store their data in some kind of AnyMap though..? This seems like far future stuff, but maybe worth noodling and thinking about.

It might be helpful to implement Debug for runtime, so that eprintln!("{:?}") and derive works.

On the other hand, just deriving Debug for runtime probably won't be helpful: it stores a lot of data. Perhaps we should add an unconditional Debug impl which prints just Runtime { ... }?

The 'simple' (without all the more complex variants depending on the environment) cache verification function is

expected_cost = read_cost + (1 - hit_rate)*(write_cost + base_cost)

where it's only worth it to cache if the amortized values obey base_cost > expected_cost (i think that's it).

I was thinking that people could annotate code for this at the call sites (not sure if function macros would be better to check pathological cases, or both), run in Debug code for a while to estimate the hit rate and start outputting things that are not faster.

It'd be cool if there was a global switch to turn this on in debug mode without the user writing anything else.

If two run times execute interleaveingly on the same thread, we can get an undetected deadlock.

We can detect the deadlocks if we store a pair of (RuntimeId, ThreadId) in the DependencyGraph, and not just RuntimeId. This should be correct even if ThreadId's can be reused across threads: all threads in the graph has to be alive.

If we detect such a deadlock, we should panic (returning a cycle error is another solution).

To write a test for this, we should make a database with two queries, A, and B, where query A forks the databse and asks for B on the fork, and the B asks for A.

#33 landed a very simple extension (set_unchecked) to support "fixing" the value of certain input queries for testing purposes. But as @matklad said in the comments of that PR:

I expect it would be useful to get some sort of the trace of the query, to make sure it does’t eval too much after invalidation, for example?

In general, one can imagine wanting to do fancier things than what set_unchecked permits, such as mocking up some inputs, test that you get the output you expect, and then alter the mocked inputs, and test (e.g.) that the output doesn't wind up being recomputed. This issue exists to record things we want and brainstorm on what that might look like.

Right now we give queries a &impl QueryContext, but that is kind of a pain if you want to store it into a struct. You would have to do

struct Foo<'me, Q: QueryContext> {
    query: &'me Q,
}

I was thinking of three options (not all mutually exclusive):

Give a &Rc<QueryContext> to the query implementations. Now you can write the struct like so:

struct Foo<Q: QueryContext> {
    query: Rc<Q>,
}

(Note that QueryContext values are not meant to be passed across threads, hence the Rc.)

Make it so that &Q: QueryConvention. We can do this automatically for all salsa-generated traits. Then you can write the struct like so:

struct Foo<Q: QueryContext> {
    query: Q,
}

where Q will be the entire &impl QueryContext value.

Define QueryContext clone to preserve identity. One final thing I was wondering is if we could say that contexts must always be cloneable (while preserving identity). In terms of the salsa runtime, this would mean putting the thread-local state into an Rc, basically. Then you could change query definitions to just take a impl QueryContext by value -- or they could still take a reference, but they know they can clone() it. This is basically the same as the Rc<QueryContext> approach except we move the Rc inside the query context.

The first approach is a bit more "obvious" but imposes a bit more tax elsewhere, since all query definitions now have to write &Arc<impl QueryContext>. The second approach might lead to &&&&impl QueryContext values being passed around. The third approach imposes a "not entirely obvious" convention that all query context implementors must follow for whatever custom state they put into the query context, but seems to be the best otherwise.

Right now, query groups depend on one another by declaring supertraits. My original plan was to support "private queries" by making two groups: a private query group Priv, and a public query group Pub: Priv. The idea was that most code would only import that Pub trait and would thus be prevented (by convention) from using private queries. However, this doesn't work, because Rust automatically makes supertrait methods invokable, so if you import Pub, you get Priv.

@matklad suggested permitting declaring "private dependencies" in the query group. This would look something like this (bikeshed welcome):

salsa::query_group!
    trait Pub {
        where Self: Priv;

        fn some_pub_query() -> u32 { ... }
    }
}

Note that the where Priv is inside the trait. (@matklad's original proposal was use trait Priv;.)

The effect of this would be to move the "where clause" from the trait declaration (where it is public) to the impl. So instead of making

trait Pub: Priv { .. }
impl<DB: Pub> QueryFunction<DB> for SomePubQuery { .. }

we would move the Priv dependency onto the impl, sort of like this

trait Pub { .. }
impl<DB: Pub> QueryFunction<DB> for SomePubQuery 
where 
    Self: Priv,
{ .. }

I think this would work, anyway...

We have a set method to associate a value with a key, but we don't have a corresponding remove method. I need this because I try to model a set of files, known to rust-analyzer, as two queries:

salsa::query_group! {
    trait FilesDatabase: salsa::Database {
        fn file_text(key: FileId) -> Arc<String> {
            type FileText;
            storage input;
        }
        fn file_set(key: ()) -> Arc<Vec<File>> {
            type FileSet;
            storage input;
        }
    }
}

One query returns text, given file id. Another query returns a set of file ids. Currently, I can add and change files, but removing files is not really possible: a file can be removed from FileSet, but not from FileText.

Perhaps this all should be left to GC though?

Following up on #7, I imagine that in many scenarios there will be global interners that are used to help cache values between query results. Of course those interners can use Arc to figure out how long their results live, but another option would be -- in between query executions -- to trace all the values that are live in the tables and then evict the rest. This would require that all cached values implement some sort of tracing trait, though — but we might be able to rig up a serializer for it and use Serde.

Note that this is not technically a memory safety issue -- those interners can be implemented using vectors and indices (ideally, generational indices) so that if we get the tracing wrong, we detect the failure.

We should support some way to serialize the state of our queries to disk and then reload them for a future session. This is a lot of work and we can learn from rustc, of course. We'd want to do the reloading lazilly, for example.

I definitely want to punt on this.

If I have a side-effectful query:

fn update(&self, scope: ScopeId) -> ()

clippy warns me:

warning: unneeded unit return type
   --> src/lib.rs:107:40
    |
107 |     fn update(&self, scope: ScopeId) -> ();
    |                                        ^^^^^ help: remove the `-> ()`
    |

and if I remove the explicit unit return, salsa can't parse my query group definition:

error: custom attribute panicked
  --> src/lib.rs:99:1
   |
99 | #[salsa::query_group(ComponentStorage)]
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: message: unsupported return type `Default` of `surface`

I can ignore this clippy lint on this particular item, but it would be nice to be able to type the function signatures similarly to what I would do outside of salsa. Is there something different I should be doing?

Right now, each storage winds up notifying the active task of a read. This seems repetitive. I'd like to factor it out, but I'm not 100% sure where to factor it out to. Moving the logic into the QueryTable::get method is one possibility, but somehow doesn't "feel right" to me. I expect that code to kind of be a "convenience wrapper" around the QueryStorageOps trait. Perhaps implement QueryStorageOps::try_fetch in terms of some inner method, which is the only actually implemented? (And have try_fetch return a StampedValue...)

Right now, input queries have no way to specify their initial value (value at revision zero).

It would be useful to be able to supply a function to do so. One case where I have found this to be true is if you have a query all_files() -> Set that returns the set of "all" your inputs -- it should start out returning the empty set.

In the general case, this feature interacts with the desire to support a remove on queries, because we need an extra bit of state now to distinguish whether a query was removed, so that we can accurately reflect when the value of the query changed (otherwise, remove can simply remove the key, since any attempt to access a removed key will panic). One option: don't support remove on queries that have an initial value -- for my query all_files above, removing doesn't really make any sense anyway.

When a query panics due to a bug during execution, the panic should be propagated to the caller, but the runtime should be left in a consistent state.

This is important for IDE use-case: language server is a long-lived process, and it is being exposed to incomplete code comparatively more often than a command-line compiler. As a result, panics due to bugs are expected to be both more numerous and more annoying.

Currently, I believe we leave InProgress marks in the storage in the case of a panic, which effectively poisons the query, and can't be fixed by changing inputs.

So handling cycles has traditionally been a thorny issue. Right now the code panics in the event of a cycle. We probably want this to stay an option, but it's probably not the best choice long term — particularly since it often happens that the order of queries is determined by user input (and hence that cycles are somewhat out of our control).

This issue is focused on the case where a cycle represents an error. I'm going to open a sister issue to focus on the case of "succesful cyclic computations".

One challenge with cycles is that they can easily lead to non-determinism. For example, imagine that we return a Result — if that is not faithfully propagated up the entire cycle, that implies that foo.query().get(K) could sometimes yield Ok (the root call) and other times yield Err (the cyclic call). This somewhat invalidates all the memoized results in the middle, since they are dependent upon the Err result. But if we had executed things in another order, things might have turned out differently. This is undesirable. It's particularly bad if we cache such results.

It would be useful to support none storage variation, which bypasses all the salsa machinery, both value and dependecy storage. "None" queries should also not be present directly in the dep-graphs.

A call to a none-query should work exactly like a function call. Why not make it a function call? To make an API nicer and to make it easier to change you mind later and elevate the function to a query (or, vice-verse, to downgrade query to a function).

Ideally none queries should allow not to define the query struct at all: basically, they are a sugar for adding arbitrary methods to the query group trait.

Currently, InputStorage returns a Default value if the key is missing:

I would think that asking for a missing key is most likely an error, so perhaps we should make this somehow more visible?

Currently, we detect cycles by storing QueryState::InProgress inside of MemoizedStorage.

I think this could be problematic for two reasons:

• we won't detect cycles for transparent queries
• if MemoizedStorage is shared by concurrently executing queries, we can get CycleDetected if two threads execute the same query simultaneously.

I think that perhaps we need to move cycle tracking from storage to Runtime? The fix I have in mind is

• remove QueryState and use map: RwLock<FxHashMap<Q::Key, Q::Value>> in the storage,
• add in_progress: FxHashSet<QC::QueryDescriptor>, to Runtime, which stores the same info as execution_stack, but with an O(1) "contains" check.

Today, to set the value of a query, you do db.query(Q).set(...).

To build on #78, we would like to change this to db.query_mut(Q).set(...). This would then require an &mut self on the database.

Together with #78, this moves us completely to the model of "one mutator thread" (which owns the main database handle, of type DB) and various "reader threads" (which own Frozen<DB> handles). Only the mutator thread can get &mut self access to the DB, so only it can invoke set.

I'll follow up with mentoring instructions perhaps.

Not sure how to do this, but we should permit:

salsa::query_definition! {
    fn foo() -> T { .. }
}

which would be equivalent to () -> T. We should also permit multiple arguments in the key:

salsa::query_definition! {
    fn foo(k1: K1, k2: K2) -> T { .. }
}

which would generate a key type of (k1, k2): (K1, K2).

This shouldn't I suppose be that hard, but it'll require us to rework the macro.

As part of salsa-rs/salsa-rfcs#1, we need to convert the salsa::database_storage macro to a procedural macro, presumably living alongside the existing salsa::query_group macro:

The idea here is to retain roughly the current input format (in particular, we will still list out individual queries). We can make some changes however. Currently salsa::database_storage looks like this:

The DatabaseStorage struct name is never explicitly used by the user, though, so I would propose that we auto-generate it. The rest could stay as is. One challenge however is that we can't use syn to readily parse such a setup, since it doesn't match Rust syntax. What to do about this? I'm not sure how easy it is to parse alternative structures in syn, but we should feel free to adapt the syntax to make it easier to parse.

Discuss in the #rfcs/salsa-query-group stream on Zulip, topic is database_storage macro (#118)

Currently, applying any change advances the global revision and "marks" all queries as potentially invalid (because their verified_at becomes smaller than current revision). The "marking" process is O(1) (we only bump one atomic usize), but subsequent validation can be O(N). Validation is on-demand (pull-based) and cheap because we don't execute queries and just compare hashes, but it still must walk large parts of the query graphs.

Here are two examples where we might want something more efficient.

function body modification

In IDEs, a lot of typing happens inside a single function body. On the first sight, this seems like it could be implemented very efficiently: changing a body can't (in most cases) have any globally effects, so we should be able to recompute types inside function's body very efficiently. However, in the current setup, types inside functions indirectly depend on the all source files (b/c, to infer types, you need to know all of the impls, which might be anywhere), so, after a change to a function, we need to check if all inputs are up to date, and this is O(N) in the number of files in the project.

unrelated crates modification

Suppose we have two independent crates, A and B, and a third crate C, which depends on A and B. Ideally, any modification of A should invalidate queries for C, but all queries for B should remain fresh. In the current setup, because there's a single global revision counter, we will have to re validate B's queries anyway.

It seems like we could achieve better big-O here, if we move validation work from query time (pull) to modification time (push).

In the second example we, for example, can define a per-crate revision counter, which is the sum of dependent-crates revisions + the revision of crate's source. During modification, we'll have to update the revision of all the reverse-dependencies of the current crate, but, during query, we can skip validation altogether, if crate-local revision hasn't change.

In the first example, we can define a "set of item declarations" query, whose results should not be affected by modification of function bodies. As "set of all items" is a union of per-files set of items (more or less, macros make everything complicated), we should be able to update when a single file is modified without checking if all other files are fresh.

Current implementation of freeze revision is susceptible to a live-lock:

If one thread tries to advance the revision, and n other threads continuously execute queries, then the revision might never be incremented.

To fix this, I think we'll need to block in freeze_revision if pending_revision_increments is greater then zero. Not sure what's the best way to do that, though? Something like this could work I guess?

while shared_state
          .pending_revision_increments
          .get(SeqCst) > 0 {
    let _ = self.shared_state.query_lock.upgradable_read();
}

I also wonder if pending_revision_increments duplicates some internal state of the shared_state.query_lock: it is essentially the number of blocked threads, so perhaps there's an API to get that?

Continuing the conversation with @kleimkuhler from #81, I think we should not attempt to make an individual database handle panic safe, but we should instead poision the handles so that -- if they are used again -- you get an immediate panic. You can still recover from panics by using snapshots.

What I wrote in #81 was as follows:

It seems "ok" to say that we recover from panics at the level of snapshots but not within a thread. In fact, this makes some sense -- if the thread with the mutable handle panics, we don't know if all of the input queries etc are in a coherent state.

For example, you might be doing:

db.query_mut(Input1).set(...);
let old_value = db.bar(); // read bar query, which panics unexpectedly
db.query_mut(Input2).set(...); // this will never execute!

However, if we are not going to recover from panics -- and I am now thinking we should not -- then perhaps we want to at least poison the database so we "fail fast". The idea would be to have some panic-guard that sets a "poisoned" flag in the runtime to true when unwinding, and any attempt to use that database handle again will panic quickly with "poisoned".

https://docs.rs/crate/salsa/0.10.0-alpha5/builds/139182

It looks to be a docs.rs problem, so I reported it there, but I thought it would be good to mention it here as well.

Now that we have converted from macro-rules macros to procedural macros (#108, #118), the next step in implementing salsa-rs/salsa-rfcs#1 is probably to try and convert from the current setup, where we have a "struct per query", to the setup of a "struct per query group that is described in the RFC.

I'll try to update the issue with a vague plan in a bit.

Most of the tests are still using .query_mut(Foo).set(...). They should probably move to the new setters.

Examples of this sort of change can be found in PR #126.

As part of salsa-rs/salsa-rfcs#1, the plan is for inputs to be expressed like so:

#[salsa::query_group]
trait MyQueryGroup {
    fn input(&self, key: K) -> V;
    fn set_input(&mut self, key: K, value: V);
}

Right now, they are expressed instead through a #[salsa::input] attribute:

In order to do this, we have to modify the query_group procedural macro:

Currently it iterates over the trait items in this loop:

And checks for &self methods here:

It needs to check for &mut self methods and, if it finds one, add that method to a separate list of "mutator methods". Each mutator method should have name like set_XXX and there should be a query named XXX with compatible key/value types.

We can remove the existing code that looks for #[salsa::input], but of course we want to do roughly the same thing if we see a set_ method.

We also need to generate a method in the trait impl like so:

fn set_my_query(&mut self, key1: K, ..., keyN: K, value: V) {
    self.query_mut(MyQueryQuery.set((key1,...,keyN), value);
}

(Eventually, we may invoke this another way, but this will do as a start.)

Currently we write things like:

This has the downside that the contents are sort of "opaque" to tools like rustfmt etc, despite being obviously Rust code. Perhaps we should use a custom derive:

#[derive(salsa::query_definition)]
crate fn Memoized2(query: &impl MemoizedDepInputsContext, (): ()) -> usize {
    query.log().add("Memoized2 invoked");
    query.dep_memoized1().read()
}

The only sort of weird thing is that the result would not, in fact, be a function.

For that matter, we could go further and apply the derive at other levels.

We have a fair amount of stuff exported from the root that probably belongs in a "plumbing" module of some kind, since people shouldn't have to interact with it directly.

This includes basically everything but (a) the macros, (b) the QueryContext trait, and (c) the DefaultKey trait (assuming we keep that).

OTOH we might want to pub use the Runtime so that people can write salsa::Runtime and not salsa::runtime::Runtime.

Currently, we track that revision is frozen while a single query is in progress, but we don't have a way to freeze the revision for consecutive queries. I think this might be important for correctness for clients which issue multiple queries for a single high-level op.

For example, IDE might ask for types (one query) and control flow info (other query) for syntax highlighting. If a revision bump happens in-between, the end result might be an inconsistent highlighting.

One way to solve this is to turn "highlighting" itself into a query.

Another way is to place onus on consumers to check that revision haven't advanced before merging results of the consecutive queries.

The third way is to provide some explicit API for freezing revisions. This could work with a drop-guard style API, and means turning this dynamic choice of None vs Some into a static one.

There are a few things I'd like to bikeshed about:

• I've been using the name query to represent the query context, but I think it may not be the best choice. It suggests that this is a query when indeed it is not, it is the overall context. Perhaps context? But that's so vague. salsa? q? I am trying not to wind up with something obscure like tcx from the compiler.
• What should we call the salsa::query_prototype! macro etc. When writing up the "hello world README" I felt like the overall terminology wasn't ideal.
  • For query_prototype in particular, we don't use the term prototype anywhere else.

I think I'd prefer some name -- maybe "query context" is good -- that consistent refers to the traits and some other name for the struct that implements them. I had been calling that struct the "storage" but that's really just a "subpart" of the struct. "Query context implementation" is a bit verbose.

Thoughts?

Currently, every "value" must implement Eq, so that we can compare if the value produced in revision R+1 differs from the value in revision R. For volatile queries, though, this isn't strictly needed -- it might be nice to offer a variant on volatile queries that does not require the value to implement Eq. Such a variant would always be assumed to change, even if it produces an "equal" value.

To implement this, we would move the "equality comparison" into the MemoizationPolicy, yielding something like this:

pub trait MemoizationPolicy<DB, Q>
where
    Q: QueryFunction<DB>,
    DB: Database,
{
    fn should_memoize_value(key: &Q::Key) -> bool;

    fn memoized_value_eq(old_value: &Q::Value, new_value: &Q::Value) -> bool;

    fn should_track_inputs(key: &Q::Key) -> bool;
}

Instead of doing old_value == new_value, we would invoke memoized_value_eq. Next, we remove the Eq (and Hash etc) bounds from the Query trait. Those bounds would rather move into the MemoizationPolicy.

Then we can offer a untracked memoization policy (which requires Eq and does comparisons) and a volatile (which is always assumed to change). Or something like that.