hybrid algorithm

[nikomatsakis]

As discussed in today's meeting, a simple starter issue for getting more understanding of how polonius works is to create a "hybrid" algorithm that first tries the location-insensitive analysis and -- if there are errors -- falls back to datafrog-opt.

[nikomatsakis]

In the meeting we said that @matthewjasper would try to write up some mentoring instructions and @AlbinS would try to fix this. =)

[nikomatsakis]

Zulip topic for discussing this issue here

[matthewjasper]

To add a new pass first add a new variant to the Algorithm enum here:

polonius/polonius-engine/src/output/mod.rs

Lines 20 to 51 in ecafafb

	#[derive(Debug, Clone, Copy)]
	pub enum Algorithm {
	Naive,
	DatafrogOpt,
	LocationInsensitive,
	/// Compare Naive and DatafrogOpt.
	Compare,
	}
	impl Algorithm {
	/// Optimized variants that ought to be equivalent to "naive"
	pub const OPTIMIZED: &'static [Algorithm] = &[Algorithm::DatafrogOpt];
	pub fn variants() -> [&'static str; 4] {
	["Naive", "DatafrogOpt", "LocationInsensitive", "Compare"]
	}
	}
	impl ::std::str::FromStr for Algorithm {
	type Err = String;
	fn from_str(s: &str) -> Result<Self, Self::Err> {
	match s.to_lowercase().as_ref() {
	"naive" => Ok(Algorithm::Naive),
	"datafrogopt" => Ok(Algorithm::DatafrogOpt),
	"locationinsensitive" => Ok(Algorithm::LocationInsensitive),
	"compare" => Ok(Algorithm::Compare),
	_ => Err(String::from(
	"valid values: Naive, DatafrogOpt, LocationInsensitive, Compare",
	)),
	}
	}
	}

also use the new pass in Algorithm::variants and Algorithm::from_str.

Then the new algorithm can be implemented by adding another arm here:

polonius/polonius-engine/src/output/mod.rs

Lines 116 to 135 in ecafafb

	match algorithm {
	Algorithm::Naive => naive::compute(dump_enabled, all_facts.clone()),
	Algorithm::DatafrogOpt => datafrog_opt::compute(dump_enabled, all_facts.clone()),
	Algorithm::LocationInsensitive => {
	location_insensitive::compute(dump_enabled, all_facts.clone())
	}
	Algorithm::Compare => {
	let naive_output = naive::compute(dump_enabled, all_facts.clone());
	let opt_output = datafrog_opt::compute(dump_enabled, all_facts.clone());
	if compare_errors(&naive_output.errors, &opt_output.errors) {
	panic!(concat!(
	"The errors reported by the naive algorithm differ from ",
	"the errors reported by the optimized algorithm. ",
	"See the error log for details."
	));
	} else {
	debug!("Naive and optimized algorithms reported the same errors.");
	}
	opt_output
	}

The pass just has to run the location insensitive pass, check if errors is non-empty, and if so run the optimized pass. It may be a good idea to have this in its own module so that it doesn't need to be moved when a more complicated hybrid algorithm is created.

Finally, the pass should be tested by adding a test here that runs that hybrid algorithm and asserts that it gets the same errors (only) as the naive algorithm:

polonius/src/test.rs

Lines 13 to 51 in ecafafb

	fn test_facts(all_facts: &AllFacts, algorithms: &[Algorithm]) {
	let naive = Output::compute(all_facts, Algorithm::Naive, true);
	// Check that the "naive errors" are a subset of the "insensitive
	// ones".
	let insensitive = Output::compute(all_facts, Algorithm::LocationInsensitive, false);
	for (naive_point, naive_loans) in &naive.errors {
	match insensitive.errors.get(&naive_point) {
	Some(insensitive_loans) => {
	for naive_loan in naive_loans {
	if !insensitive_loans.contains(naive_loan) {
	panic!(
	"naive analysis had error for `{:?}` at `{:?}` \
	but insensitive analysis did not \
	(loans = {:#?})",
	naive_loan, naive_point, insensitive_loans,
	);
	}
	}
	}
	None => {
	panic!(
	"naive analysis had errors at `{:?}` but insensitive analysis did not \
	(loans = {:#?})",
	naive_point, naive_loans,
	);
	}
	}
	}
	// The optimized checks should behave exactly the same as the naive check.
	for &optimized_algorithm in algorithms {
	println!("Algorithm {:?}", optimized_algorithm);
	let opt = Output::compute(all_facts, optimized_algorithm, true);
	assert_equal(&naive.borrow_live_at, &opt.borrow_live_at);
	assert_equal(&naive.errors, &opt.errors);
	}
	}