This PR is...kind of long. It reshapes the core logic of salsa to fix various bugs in cycle handling and generally simplify how we handle cross-thread coordination.

Best read commit by commit: every commit passes all tests, afaik.

The core bug I was taking aim at was the fact that, when you invoke maybe_changed_since, you can sometimes wind up detecting a cycle without having pushed some of the relevant queries onto the stack. This is now fixed.

From a user's POV, ~~nothing changes from this PR~~, there are only minimal changes to the public interface. The biggest one is that recover functions now get a &salsa::Cycle which has methods for accessing the participants; the other is that queries that are participating in cycle fallback will use unwinding to avoid executing past the point where the cycle is discovered. Otherwise, things work the same as before:

• If you encounter a cycle and all participant queries are marked with #[salsa::recover], then they will take on the recovery value. (At the moment, they continue executing after the cycle is observed, but their final result is ignored; I plan to change this in a follow-up PR, or maybe some future commit to this PR.)
• If you encounter a cycle and some or all participants are NOT marked with #[salsa::recover], then the code panics. This is treated like any other panic, cancelling all other work.

Along the way, I made... a few... other changes:

• Cross-thread handling is simplified. When we block on another thread, it no longer sends us a final result. Instead, it just gets re-awoken and then it retries the original request. This is helpful when you encounter cycles in maybe_changed_since vs read, but it's also more compatible with some of the directions I have in mind.
• Cycle detection is simplified and more centrally coordinated. Previously, when a cycle was detected, we would mark all the participants on the current thread, but then we would mark other threads 'lazilly'. Now, threads move ownership of their stack into the shared dep graph when they block, so that we can mark all the stack frames at once. This also means less cloning on blocking, so it should be mildly more efficient.
• The code is DRY-er, since maybe_changed_since has been re-implemented in terms of the same core building blocks as read (probe and friends). I originally tried to unify them, but I realized that they behave somewhat differently from one another and both of them make sense. (In particular, we want to be able to free values with the LRU cache while still checking if they are up to date.)

Ah, I realize now that I had planned to write a bunch of docs in the salsa book before I landed this. Well, I'm going to open the PR anyway, as I've let this branch go far too long.

r? @matklad

Wanted to check how much code would need to be added/duplicated to support async queries. This isn't a a full implementation (I haven't even tested to call async functions) but the normal sync implementation still work with this with what shouldn't be too much overhead.

Not really interested in this until async/await gets to stable but figured a PR with this could still be useful.

Previous output:

---- nameres::tests::macros::unexpanded_macro_should_expand_by_fixedpoint_loop stdout ----
thread 'nameres::tests::macros::unexpanded_macro_should_expand_by_fixedpoint_loop' panicked at 'Internal error, cycle detected:

DatabaseKeyIndex { group_index: 2, query_index: 11, key_index: 1 }
', /home/jonas/.cargo/registry/src/github.com-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:48

Output after this PR:

---- nameres::tests::macros::unexpanded_macro_should_expand_by_fixedpoint_loop stdout ----
thread 'nameres::tests::macros::unexpanded_macro_should_expand_by_fixedpoint_loop' panicked at 'Internal error, cycle detected:

hygiene_frame(HirFileId(MacroFile(MacroFile { macro_call_id: LazyMacro(LazyMacroId(0)) })))
', /home/jonas/dev/salsa/src/lib.rs:492:35

This PR introduces an RFC describing a shift to dyn-capable databases. The primary goal is to make it so that query-group code can be compiled in the query-group crate, rather than waiting to be monomorphized in the final database crate.

The main user-visible effect of this proposal is that it requires all salsa query group traits to be dyn-safe.

Rendered form of the RFC

Current status

Largely implemented.

Pending work:

• [x] Refactor slots and dependencies and try to minimize code generic over Q in the derived impl -- the current branch doesn't match the RFC in that it still creates slots that store the values.
• [x] Update the salsa book
• [x] Test effectiveness perhaps?

Pending updates the RFC text itself:

• [x] Describe the 'static limitation on databases and how it might be overcome
• [x] I removed the db.query(Q) methods entirely in favor of Q.in_db(&db). This does not require an extension trait and also works better with dyn Db coercions.
• [x] Describe how we are adding salsa::Database and HasQueryGroup<G> as an automatic supertrait to each query-group trait.

Fixes #319.

This allows users to annotate impl blocks with #[salsa::tracked] and then create tracked methods by marking individual functions with #[salsa::tracked].

Note this requires your code that looks like:

#[salsa::tracked(jar = Jar)]
impl MyInput {
    #[salsa::tracked]
    fn tracked_fn(self, db: &dyn Db) -> u32 {
        self.field(db) * 2
    }
}

You get an error if you annotate a method with #[salsa::tracked] but forget to mark the impl block.

It got messier than I was hoping but I think it turned out alright, this would look really pretty if we had inherent associated types, but we don't. Annoyingly even if that landed I think we'd still need the attribute on the impl block just so that it was possible to create the associated struct somewhere as you can't put types inside an impl block (and they aren't accessible if placed inside a function).

fixes #364

add synthetic_write and use it in test lru_keeps_dependency_info, the test will now be broken. We can use lru_keeps_dependency_info as a test for https://github.com/salsa-rs/salsa/issues/365, which already has a pr https://github.com/salsa-rs/salsa/pull/371.

This addresses a couple of items of #397

I initially added a separate DebugWithDb::fmt_all method but then changed it to an extra parameter to make it easier to propagate to inner fields. Also tried introducing something like:

pub struct FormatterWithDb<'me, 'f, Db: ?Sized>{
  fmt: &'me mut std::fmt::Formatter<'f>,
  db: &'me Db,
  include_all_fields: bool
}

to pass to fmt, but I gave up because the lifetimes got a bit unwieldy.

Fixes #323.

This adds support for tracked functions with only a database as input, that is, it does not take a salsa struct.

I'm not entirely convinced by this, it feels like it works somewhat accidentally and may be fragile to changes. I'm happy if this just get closed as I was mostly playing around to see how this worked.

This change has the odd side-effect of making this code work:

#[salsa::tracked]
fn tracked_fn(db: &dyn Db, unit: ()) -> u32 {
    44
}

The default behavior when salsa detects a cycle is to panic. This is fine behavior when the cycle occurs as a programmer error but in some instances cycles can be expected to occur. To allow this case while still keeping "programmer error" as the default assumption on cycles a salsa::cycle is added which can be attached to any function which could naturally appear in a cycle.

The salsa::cycle takes a function which takes the keys of the query as well as description of all the queries that were part of the cycle (currently a slice of Debug formatted strings for simplicity's sake). When a cycle is detected salsa invokes the cycle function to produce the result for the query instead of panicking. Furthermore, every other query in the cycle will discard whatever value they produced normally and invoke their own cycle function (if a function in the cycle lacks the attribute salsa will panic as usual). All values produced from a cycle function is memoized in the same way as if the query executed normally.

This has been tested to work well in gluon's import system which needs to error if modules import each other in a cycle (a programmer error for the one writing gluon programs, but not in the salsa query usage in gluon) https://github.com/gluon-lang/gluon/pull/683 . The only nasty part is that the cycle information needs to be parsed out of the Debug formatted string but currently I don't have a good abstraction for solving that.

cc #6

Extend the database_storage! macro such that it allows for lifetimes to be added to the generated struct. This is necessary if the database itself has lifetime parameters that need to be threaded through to the queries being invoked.

The main goal is to allow arena allocation to be used in your database struct, and to pass those references around as query inputs and outputs.

Not sure this is the best solution -- I'd love to hear your thoughts.

This is the first step towards the "fewer footguns" API.

Opening for discussion.

Some to do items:

• [x] Move set to a query_mut method that requires &mut self (https://github.com/salsa-rs/salsa/issues/79)
• [x] Add tests for the "recursive read lock" case; I think i understand well enough now to be able to trigger the deadlock deterministically (and show that we are avoiding it)

Hi, I'm using salsa_2022, and I want to create a snapshot in a tracked salsa function. All the examples I found are creating snapshots directly from database struct, but in a salsa function the only thing I got is a db trait, and I it doesn't have asnapshot function.

This example is an analogy of a calculation with multiple inputs that depend on each other by a unique id. The calc example can handle multiple inputs, but its inputs are not referred to each other.

• FlatNode represents an input.
• usize represents an input id.
• Tree represents an intermediate or final result of a computation.
• fn construct_tree represents an internal recursive computation.
• fn entrypoint represents an entrypoint of a computation.

Problem Statement Salsa is verbosely logging query and computation events at the INFO level which makes it hard to find info from client libraries or applications in the logs.

Background and Motivation I am using citeproc-rs to render bibliographic citations into HTML; citeproc-rs uses salsa for computation of the citation style language (CSL).

I've written a service that accepts CSL and renders the citation to HTML and returns it. Below is an example of a single query for a single reference: (note that all but the first 3 lines originate in salsa)

2022-11-24T15:53:00.829653Z  INFO alexandria::style: FAST_STYLES is set; loading only 4 styles
2022-11-24T15:53:00.864827Z  INFO alexandria::style: Loaded 4 styles
2022-11-24T15:53:00.865803Z  INFO alexandria: Alexandria refmgr listening on 0.0.0.0:8048
2022-11-24T15:53:21.972674Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: GetBibliographyMapQuery(()): invoked at R17
2022-11-24T15:53:21.973018Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: GetBibliographyMapQuery(()): executing query
2022-11-24T15:53:21.973217Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: SortedRefsQuery(()): invoked at R17
2022-11-24T15:53:21.973384Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: SortedRefsQuery(()): executing query
2022-11-24T15:53:21.973539Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: CitedKeysQuery(()): invoked at R17
2022-11-24T15:53:21.973792Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: CitedKeysQuery(()): executing query
2022-11-24T15:53:21.973858Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: AllCiteIdsQuery(()): invoked at R17
2022-11-24T15:53:21.973902Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: AllCiteIdsQuery(()): executing query
2022-11-24T15:53:21.973933Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ClustersSortedQuery(()): invoked at R17
2022-11-24T15:53:21.975951Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ClustersSortedQuery(()): executing query
2022-11-24T15:53:21.976147Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DisambParticipantsQuery(()): invoked at R17
2022-11-24T15:53:21.976192Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DisambParticipantsQuery(()): executing query
2022-11-24T15:53:21.976214Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: CitedKeysQuery(()): invoked at R17
2022-11-24T15:53:21.976234Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: CitedKeysQuery(()): returning memoized value changed at R16
2022-11-24T15:53:21.976674Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: BibItemGen0Query(Atom('alexandria/pubmed/4599080' type=dynamic)): invoked at R17
2022-11-24T15:53:21.976804Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: BibItemGen0Query(Atom('alexandria/pubmed/4599080' type=dynamic)): executing query
2022-11-24T15:53:21.976858Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: SortedRefsQuery(()): invoked at R17
2022-11-24T15:53:21.976878Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: SortedRefsQuery(()): returning memoized value changed at R17
2022-11-24T15:53:21.976907Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ReferenceQuery(Atom('alexandria/pubmed/4599080' type=dynamic)): invoked at R17
2022-11-24T15:53:21.976927Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ReferenceQuery(Atom('alexandria/pubmed/4599080' type=dynamic)): executing query
2022-11-24T15:53:21.976982Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DefaultLocaleQuery(()): invoked at R17
2022-11-24T15:53:21.977014Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DefaultLocaleQuery(()): executing query
2022-11-24T15:53:21.977051Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(Inline(Some(Iso(English, Some(US))))): invoked at R17
2022-11-24T15:53:21.977073Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(Inline(Some(Iso(English, Some(US))))): executing query
2022-11-24T15:53:21.977104Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(Inline(Some(Iso(English, None)))): invoked at R17
2022-11-24T15:53:21.977121Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(Inline(Some(Iso(English, None)))): executing query
2022-11-24T15:53:21.977149Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(Inline(None)): invoked at R17
2022-11-24T15:53:21.977166Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(Inline(None)): executing query
2022-11-24T15:53:21.977194Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(File(Iso(English, Some(US)))): invoked at R17
2022-11-24T15:53:21.977212Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: ParsedLocaleQuery(File(Iso(English, Some(US)))): executing query
2022-11-24T15:53:21.983379Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: NameInfoBibliographyQuery(()): invoked at R17
2022-11-24T15:53:21.983436Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: NameInfoBibliographyQuery(()): executing query
2022-11-24T15:53:21.984405Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DisambiguatedPersonNamesQuery(()): invoked at R17
2022-11-24T15:53:21.984439Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DisambiguatedPersonNamesQuery(()): executing query
2022-11-24T15:53:21.984517Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DisambiguatedPersonNamesQuery(()): invoked at R17
2022-11-24T15:53:21.984536Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DisambiguatedPersonNamesQuery(()): returning memoized value changed at R12
2022-11-24T15:53:21.985416Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: YearSuffixForQuery(Atom('alexandria/pubmed/4599080' type=dynamic)): invoked at R17
2022-11-24T15:53:21.985468Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: YearSuffixForQuery(Atom('alexandria/pubmed/4599080' type=dynamic)): executing query
2022-11-24T15:53:21.985492Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: YearSuffixesQuery(()): invoked at R17
2022-11-24T15:53:21.985533Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: YearSuffixesQuery(()): executing query
2022-11-24T15:53:21.985579Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: AllCiteIdsQuery(()): invoked at R17
2022-11-24T15:53:21.985595Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: AllCiteIdsQuery(()): returning memoized value changed at R7
2022-11-24T15:53:21.985783Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DefaultLocaleQuery(()): invoked at R17
2022-11-24T15:53:21.985802Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: DefaultLocaleQuery(()): returning memoized value changed at R13
2022-11-24T15:53:21.985960Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: SortedRefsQuery(()): invoked at R17
2022-11-24T15:53:21.985982Z  INFO render_csl{render_params=Query(RenderParams { style: "nature", locale: Some("en-US"), format: Some(Html) })}: salsa::derived::slot: SortedRefsQuery(()): returning memoized value changed at R17

Question Are you amenable to decreasing these messages to the TRACING or DEBUG level? If yes, is the current, non-2022 salsa accepting changes?

Thanks in advance

While working on crubit/cc_bindings_from_rs experiment, I hoped to use salsa to memoize results of a lifetime-generic function like the one below:

use anyhow::Result;
use rustc_middle::ty::{self, Ty, TyCtxt};
use rustc_span::def_id::DefId;
struct AdtCoreBindings { ... }
fn format_adt_core<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> Result<AdtCoreBindings>

It seems that one way to achieve this would be to treat tcx as an input of a salsa query group (suggestions about alternative approaches are welcomed). Unfortunately using TyCtxt<'tcx> as salsa input doesn't seem to work. Consider the following, simplified example:

#[salsa::query_group(HelloWorldStorage)]
trait HelloWorld<'db> {  // <-- GENERIC LIFETIME PARAMETER
    #[salsa::input]
    fn input_string(&self) -> &'db str;  // <-- LIFETIME-BOUND `salsa` INPUT

    fn char_count(&self, c: char) -> usize;
}

fn char_count<'db>(db: &dyn HelloWorld<'db>, c: char) -> usize {
    let input_string = db.input_string();
    input_string.chars().filter(|x| *x == c).count()
}

#[salsa::database(HelloWorldStorage)]
#[derive(Default)]
struct DatabaseStruct {
    storage: salsa::Storage<Self>,
}

impl salsa::Database for DatabaseStruct {}

fn main() {
    let mut db = DatabaseStruct::default();
    db.set_input_string("aaabbbccc".to_string());
    println!("char_count('a') = {}", db.char_count('a'));
}

Attempting to build the code above results in:

error[E0261]: use of undeclared lifetime name `'db`
  --> src/main.rs:20:32
   |
20 |     fn input_string(&self) -> &'db str;
   |                                ^^^ undeclared lifetime
   |
help: consider introducing lifetime `'db` here
   |
20 |     fn input_string<'db>(&self) -> &'db str;
   |                    +++++
help: consider introducing lifetime `'db` here
   |
18 | trait HelloWorld<'db><'db> {
   |                 +++++

Do you think supporting databases with generic lifetime parameters is a valid feature request for salsa?

Hi!

Excited about salsa, I was reading the calc tutorial in the book and thought that would be useful to contribute the small fixes I would make.

Most of the changes are typos, updating according to the code or rephrasing for a smoother reading flow. Feel free to accept or reject any of the changes: there is no such thing as the "best writing style".