A generic framework for on-demand, incrementalized computation. Inspired by adapton, glimmer, and rustc's query system.

Related tags

Computation salsa
Overview

salsa

Test Book Released API docs Crates.io

A generic framework for on-demand, incrementalized computation.

Obligatory warning

Very much a WORK IN PROGRESS at this point. Ready for experimental use but expect frequent breaking changes.

Credits

This system is heavily inspired by adapton, glimmer, and rustc's query system. So credit goes to Eduard-Mihai Burtescu, Matthew Hammer, Yehuda Katz, and Michael Woerister.

Key idea

The key idea of salsa is that you define your program as a set of queries. Every query is used like function K -> V that maps from some key of type K to a value of type V. Queries come in two basic varieties:

  • Inputs: the base inputs to your system. You can change these whenever you like.
  • Functions: pure functions (no side effects) that transform your inputs into other values. The results of queries is memoized to avoid recomputing them a lot. When you make changes to the inputs, we'll figure out (fairly intelligently) when we can re-use these memoized values and when we have to recompute them.

Want to learn more?

To learn more about Salsa, try one of the following:

Getting in touch

The bulk of the discussion happens in the issues and pull requests, but we have a zulip chat as well.

Comments
  • Cleanup and fix cycle handling

    Cleanup and fix cycle handling

    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

    opened by nikomatsakis 23
  • [POC] Prototype async query functions

    [POC] Prototype async query functions

    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.

    opened by Marwes 20
  • Include user-readable query keys in cycle errors

    Include user-readable query keys in cycle errors

    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
    
    opened by jonas-schievink 17
  • [RFC] Dynamic databases

    [RFC] Dynamic databases

    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.
    opened by nikomatsakis 15
  • Allow creation of tracked methods

    Allow creation of tracked methods

    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).

    opened by Skepfyr 14
  • add `synthetic_write`

    add `synthetic_write`

    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.

    opened by XFFXFF 14
  • Include only identity fields by default in `DebugWithDb::debug` and add `DebugWithDb::debug_all`

    Include only identity fields by default in `DebugWithDb::debug` and add `DebugWithDb::debug_all`

    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.

    opened by vemoo 12
  • Allow

    Allow "constant" tracked functions

    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
    }
    
    
    opened by Skepfyr 11
  • feat: Allow queries to avoid panics on cycles

    feat: Allow queries to avoid panics on cycles

    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

    opened by Marwes 11
  • Allow lifetime annotations in `database_storage!` and `query_group!`

    Allow lifetime annotations in `database_storage!` and `query_group!`

    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.

    opened by fabianschuiki 11
  • make `fork` give you a `Frozen<DB>`

    make `fork` give you a `Frozen`

    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)
    opened by nikomatsakis 11
  • Do we want the `debug_all` method?

    Do we want the `debug_all` method?

    In #405, we added the debug_all method so that you can easily get a debug print out that includes all fields. But that may introduce unwanted dependencies. How often do people want it? Maybe we should not be encouraging this and have people write their own methods if they want to debug a bunch of fields.

    salsa-2022 bikeshed 🚴‍♀️ 
    opened by nikomatsakis 3
  • some way to include input fields in DebugWithDb output

    some way to include input fields in DebugWithDb output

    In #405, we made the DebugWithDb impl only include those fields that will not introduce additional dependencies when printed. This seems like a good default, but it's annoying for inputs, because right now all input fields are mutable and hence reading any field creates a dependency.

    It'd be nice if you could tag some input fields as 'immutable' in some way and then we include them, but it's not clear the best way to do it.

    salsa-2022 bikeshed 🚴‍♀️ 
    opened by nikomatsakis 4
  • Panic when reading fields of tracked structs from older revisions

    Panic when reading fields of tracked structs from older revisions

    use test_log::test;
    
    #[salsa::jar(db = Db)]
    struct Jar(MyInput, MyTracked, final_result, intermediate_result);
    
    trait Db: salsa::DbWithJar<Jar> {}
    
    #[salsa::input(jar = Jar)]
    struct MyInput {
        field: u32,
    }
    
    #[salsa::tracked(jar = Jar)]
    struct MyTracked {
        field: u32,
    }
    
    #[salsa::tracked(jar = Jar)]
    fn final_result(db: &dyn Db, tracked: MyTracked) -> u32 {
        tracked.field(db) * 2
    }
    
    #[salsa::tracked(jar = Jar)]
    fn intermediate_result(db: &dyn Db, input: MyInput) -> MyTracked {
        MyTracked::new(db, input.field(db) / 2)
    }
    
    #[salsa::db(Jar)]
    #[derive(Default)]
    struct Database {
        storage: salsa::Storage<Self>,
    }
    
    impl salsa::Database for Database {}
    
    impl Db for Database {}
    
    
    #[test]
    fn execute() {
        let mut db = Database::default();
    
        let input = MyInput::new(&mut db, 22);
        let tracked = intermediate_result(&db, input);
    
        dbg!(final_result(&db, tracked));
    
        input.set_field(&mut db).to(24);
        dbg!(final_result(&db, tracked));
    }
    

    it will output

    [salsa-2022-tests/tests/hello_world.rs:46] final_result(&db, tracked) = 22
    [salsa-2022-tests/tests/hello_world.rs:49] final_result(&db, tracked) = 22
    

    not sure if this is expected behavior, or if we should get

    [salsa-2022-tests/tests/hello_world.rs:46] final_result(&db, tracked) = 22
    [salsa-2022-tests/tests/hello_world.rs:49] final_result(&db, tracked) = 24
    
    salsa-2022 
    opened by XFFXFF 4
  • Salsa Book: some chapters exist but are not included in the book

    Salsa Book: some chapters exist but are not included in the book

    opened by zjp-CN 0
  • tutorial debug chapter: codeblock is empty

    tutorial debug chapter: codeblock is empty

    https://salsa-rs.github.io/salsa/tutorial/debug.html#forwarding-to-the-ordinary-debug-trait

    ANCHOR: op_debug_impl is missing, which indicates the debug tutorial might be outdated.

    Before:

    // ANCHOR: op_debug_impl
    impl DebugWithDb<dyn crate::Db + '_> for Op {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>, _db: &dyn crate::Db) -> std::fmt::Result {
            write!(f, "{:?}", self)
        }
    }
    // ANCHOR: op_debug_impl
    

    Now: https://github.com/salsa-rs/salsa/blob/657b85682b5371ce7b5ef5697ef0fcd96351406d/calc-example/calc/src/ir.rs

    opened by zjp-CN 0
Extendable HPC-Framework for CUDA, OpenCL and common CPU

Collenchyma • Collenchyma is an extensible, pluggable, backend-agnostic framework for parallel, high-performance computations on CUDA, OpenCL and comm

Autumn 462 Aug 12, 2022
User-friendly secure computation engine based on secure multi-party computation

CipherCore If you have any questions, or, more generally, would like to discuss CipherCore, please join the Slack community. See a vastly extended ver

CipherMode Labs 341 Sep 15, 2022
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

null 293 Sep 22, 2022
Statistical computation library for Rust

statrs Current Version: v0.13.0 Should work for both nightly and stable Rust. NOTE: While I will try to maintain backwards compatibility as much as po

Michael Ma 363 Sep 9, 2022
Extreme fast factor expression & computation library for quantitative trading in Python.

Extreme fast factor expression & computation library for quantitative trading in Python.

Weiyuan Wu 21 Sep 19, 2022
A simple mandelbrot-computation.

Mandelbrot set We consider the sequence $z_{n+1} = z_n^2 + c$, with $z_0=0$, where $c$ is a complex number. The Mandelbrot set are all $c$ such that t

Andreas Atle 1 Jan 27, 2022
Statistical computation library for Rust

statrs Current Version: v0.15.0 Should work for both nightly and stable Rust. NOTE: While I will try to maintain backwards compatibility as much as po

null 363 Sep 9, 2022
The language that eats the stack. Heavily inspired by porth which is inspired off of forth

Snack The language that eats the stack. Heavily inspired by porth which is inspired off of forth Install To use Snack you will need Rust and fasm Afte

Cowboy8625 2 Mar 20, 2022
a prototype crate for creating modular and performant 3D CPU particle systems, inspired by Unity's Shuriken Particle System.

bevy_prototype_particles This is a prototype crate for creating modular and performant 3D CPU particle systems, inspired by Unity's Shuriken Particle

James Liu 28 Sep 12, 2022
A system clipboard command line tools which inspired by pbcopy & pbpaste but better to use.

rclip A command line tool which supports copy a file contents to the system clipboard or copy the contents of the system clipboard to a file. Install

yahaa 3 May 30, 2022
An expressjs inspired web framework for Rust

nickel.rs nickel.rs is a simple and lightweight foundation for web applications written in Rust. Its API is inspired by the popular express framework

null 3k Sep 18, 2022
Sauron is an html web framework for building web-apps. It is heavily inspired by elm.

sauron Guide Sauron is an web framework for creating fast and interactive client side web application, as well as server-side rendering for back-end w

Jovansonlee Cesar 1.7k Sep 26, 2022
High performance I/O framework written by Rust inspired by Netty

Introduction Retty is a High performance I/O framework written by Rust inspired by Netty 基于mio的IO多路复用高并发、高性能网络通信开发框架 Feature Rayon 线程池包装 EventLoop / E

lgphp 8 Jul 30, 2022
Generic abstractions for combining and nesting reduction patterns for iterables.

reductor Generic abstractions for combining and nesting reduction patterns for iterables. Docs: https//docs.rs/reductor Before & After: Before fn proc

Yotam Ofek 2 Jul 9, 2022
archive-rs provides a generic way of dealing with multiple archive and compression formats in Rust

archive-rs A Rust crate that aims to provide a generic way of dealing with multiple archive and compression formats by providing a generic abstraction

S.J.R. van Schaik 2 Nov 21, 2021
Generic and extensible egui widgets to create analog synthesizer-like UI with data-oriented API

egui_cable A generic and extensible data-oriented widget for connecting ports by cables. I create this for the visual programming editor of Hihaheho/D

Ryo Hirayama 29 Sep 11, 2022
Online-statistics is crate 🦀 for Blazingly fast, generic and serializable online statistics

Online statistics in Rust ?? for Blazingly fast, generic and serializable online statistics. Quickstart Let's compute th

Adil Zouitine 21 Sep 2, 2022
A generic connection pool for Rust

r2d2 A generic connection pool for Rust. Documentation Opening a new database connection every time one is needed is both inefficient and can lead to

Steven Fackler 1.1k Sep 22, 2022
Generic array types in Rust

generic-array This crate implements generic array types for Rust. Requires minumum Rust version of 1.36.0, or 1.41.0 for From<[T; N]> implementations

Bartłomiej Kamiński 315 Sep 19, 2022
Parameterized routing for generic resources in Rust

Usher Usher provides an easy way to construct parameterized routing trees in Rust. The nodes of these trees is naturally generic, allowing Usher to le

Isaac Whitfield 33 Jun 27, 2022