How Salsa Works (2019.01).md

How Salsa Works (2019.01)

What is Salsa?

• Incremental recomputation

  fn foo(input1: A, input2: B) -> Output

  let x1 = foo(a, b1) // reuse some of the work we did let x2 = foo(a, b2)

• “Automatic”

• “Sound / Correct” — you get the same result as if we did not re-use at all

Salsa’s actual model is richer

• IDE:
  • Inputs:
    • manifest (Cargo.toml)
    • source files (foo.rs => "``…``")
  • Outputs:
    • Binary executable
    • Completions at this point?
    • What should I show the user when the mouse is hovering on this line?

How does it work?

• Identify the “base inputs” to your computation
• Identify intermediate “derived” values
  • deterministic, “pure” function that computes them
• Inputs:
  • manifest manifest() → Vec<Path>
  • source text source_text(x: Path) → String
• Derived values:
  • for each source file X, we might have a derived value ast(x: Path) → AST
  • completion(path: Path, line: usize, column: usize)
• Track:
  • in the course of computing (say) ast(Path),
    • which inputs did we access?
    • which derived values?
• When an input changes:

  • these derived values are still valid (because none of the inputs that they touch changed)

  • these derived values may be invalid (because some of the inputs that they touch changed)

    manifest() <------------------------ whole_program_ast() <-- type-checking | source_text("a.rs") <- ast("a.rs") <-------+ | source_text("b.rs") <- ast("b.rs") <-------+

Key Salsa concepts

Query

• manifest() → Manifest — (input) query
• whole_program_ast() → Ast — (derived) query
• source_text(p: Path) → String — (derived) query
• ast(p: Path) → Ast — (derived) query
• my_query(a: u32, b: u32) → f32 (u32, u32) as the key)

Database

• Store all of salsa’s internal state
• Has to know all the queries that you will do
  • but you don’t list them all in one place
• db.manifest() — I get a Manifest returned to me
  • db.ast(``"``foo.rs``"``) — ast returned to me for foo.rs
    • if I invoke twice, I just get the result cloned (don’t recompute)
    • even once the inputs change, I may just get the result cloned
• db.set_manifest(Manifest { .. }) —
  • triggers previous memoized values to be potentially invalidated

Query groups

• “Salsa modules”

  #[salsa::query_group(InputsStorage)] pub trait Inputs { #[salsa::input] // set_manifest is auto-generated fn manifest(&self) -> Manifest;

  #[salsa::input] // `set_source_text` is auto-generated
  fn source_text(&self, name: String) -> String;
  

  }

  #[salsa::query_group(ParserStorage)] pub trait Parser: Inputs { fn ast(&self, name: String) -> Ast;

  fn whole_program_ast(&self) -> Ast;
  

  }

  fn ast(db: &dyn Parser, name: String) -> Ast { let source_text = db.source_text(name);

  // do the actual parser on `source_text`
  
  return ast;
  

  }

  fn whole_program_ast(db: &dyn Parser, name: String) -> Ast { let mut ast = Ast::default(); for source_file in db.manifest() { let ast_source_file = db.ast(name); ast.extend(ast_source_file); } return ast; }

  #[salsa::query_group(TypeCheckerStorage)] pub trait TypeChecker: Parser { fn type_check(&self) -> Vec; }

  #[salsa::database(InputsStorage, ParserStorage, TypeCheckerStorage)] #[derive(Default)] struct MyDatabase { runtime: salsa::Runtime, }

  impl salsa::Database for MyDatabase { fn salsa_runtime(&self) -> &salsa::Runtime { &self.runtime } }

  fn main() { let mut db = MyDatabase::default(); db.set_manifest(..); db.set_source_text(...); loop { db.type_check(); // will reuse results db.set_source_text(...); // edit } }

In

whole_program_ast() → Ast — (derived) query

should that be whole_program_ast(Manifest)?