Test to see if function produces same accumulator values

[nikomatsakis]

When executed, a function F can produce "push" onto accumulators, as described here.

When another function G reads the accumulated values, that is considered a read of F. So when we decide if G is red in a given revision, we will look to see if F is red. To do that, we will look at F's inputs, but then we'll compare F's output -- and here, we don't take into account accumulated values! This is a problem. This could cause us to fail to re-execute G even though the errors or other values pushed by F have changed.

I'm not entirely sure the best way to fix this! We can track the places that a function pushes during its execution easily enough, but I don't want to store all the values in the Memo. This would be a lot easier to fix if we were using hashes to compare for equality instead of Eq, and that'd be nice for some other reasons too, I wonder if that's the way to go...

[nikomatsakis]

Comment from #351:

PR #350 made accumulators return the right results, but as described in the PR heading (and demonstrated by the test accumulate-reuse.md) it doesn't get as much re-use as you would like. There is a workaround (see accumulate-reuse-workaround.rs), but this issue tracks the problem of improving salsa's implementation so that the reuse is not necessary.

[Skepfyr]

I believe this issue corresponds to this FIXME comment:

salsa/components/salsa-2022/src/accumulator.rs

Lines 74 to 85 in e99e45d

	pub(crate) fn produced_by(
	&self,
	runtime: &Runtime,
	query: DatabaseKeyIndex,
	output: &mut Vec<Data>,
	) {
	let current_revision = runtime.current_revision();
	if let Some(v) = self.map.get(&query) {
	// FIXME: We don't currently have a good way to identify the value that was read.
	// You can't report is as a tracked read of `query`, because the return value of query is not being read here --
	// instead it is the set of values accumuated by `query`.
	runtime.report_untracked_read();

The issue is explained reasonably well in this commit message: 9df075b

I have a branch attempting to fix this issue here: master...Skepfyr:salsa:accumulator-reuse

Some thoughts:

• Accumulators act like a second output of a function but they aren't tracked by the function ingredient so you end up having to duplicate the function's maybe_changed_after code.
• Accumulators are shared across all functions so they must create a salsa::Id for each function DependencyIndex that calls them (so you have to intern all of them).

[nikomatsakis]

@Skepfyr I was thinking about it and I don't think I ever jotted down my thoughts here.

The workaround for this problem today is to introduce a tracked function for reading the accumulator, e.g.

#[salsa::accumulator]
struct Diagnostics(Diagnostic);

#[salsa::tracked]
fn type_check_errors(db: &dyn crate::Db, function: Function) -> Vec<Diagnostic> {
    type_check::accumulated::<Diagnostic>(function)
}

#[salsa::tracked]
fn type_check(db: &dyn crate::Db, function: Function) { }

This got me to wondering if the right way to address this is to say that we don't allow you to read accumulated from any old function (or maybe we do, but it's not recommended).

Instead, you should declare the outputs, perhaps with something like this:

#[salsa::accumulator]
struct Diagnostics(Diagnostic);

#[salsa::tracked(accumulates(Diagnostics))]
fn type_check(db: &dyn crate::Db, function: Function) { }

and we will generate a type_check::diagnostics(db, function) helper function for you (I'm assuming a cute-sy "rename to snake-case thing"). This function can use an untracked read internally, that's fine, it will basically do the right thing -- in each new revision, it will re-check all the data that was generated and compare it against the old result.

[nikomatsakis]

@Skepfyr I was thinking about it and I don't think I ever jotted down my thoughts here.

The workaround for this problem today is to introduce a tracked function for reading the accumulator, e.g.

#[salsa::accumulator]
struct Diagnostics(Diagnostic);

#[salsa::tracked]
fn type_check_errors(db: &dyn crate::Db, function: Function) -> Vec<Diagnostic> {
    type_check::accumulated::<Diagnostic>(function)
}

#[salsa::tracked]
fn type_check(db: &dyn crate::Db, function: Function) { }

This got me to wondering if the right way to address this is to say that we don't allow you to read accumulated from any old function (or maybe we do, but it's not recommended).

Instead, you should declare the outputs, perhaps with something like this:

#[salsa::accumulator]
struct Diagnostics(Diagnostic);

#[salsa::tracked(accumulates(Diagnostics))]
fn type_check(db: &dyn crate::Db, function: Function) { }

and we will generate a type_check::diagnostics(db, function) helper function for you (I'm assuming a cute-sy "rename to snake-case thing"). This function can use an untracked read internally, that's fine, it will basically do the right thing -- in each new revision, it will re-check all the data that was generated and compare it against the old result.

[nikomatsakis]

(The name accumulates may not be ideal since the diagnostics could be pushed from other tracked functions; this is just used for those points where you want to read the result out.)