crates.sage_ir.solver.canonical_outputs

Goal-specific output is canonical solver knowledge. Prove(P) returns Proven, while input-only Normalize(Alias) returns a Type. The output’s variables participate in response binding, validation, caching, comparison, merging, and caller import; the caller’s expected type is related only after complete candidate answers are merged. This is the solver consequence of Solver operations return goal-specific semantic outputs.

Read in specification context · design/crates/sage_ir/solver.sage

Implementation

Implemented crates/sage-ir/src/check/infer_ctx.rs:1981–1986

sage_ir::check::infer_ctx · lib:sage_ir

#![allow(unused)]
fn main() {
    // {anchor}`crates.sage_ir.solver.canonical_outputs`
    fn apply_normalization_relation(
        &self,
        canonical_goal: &Stashed<super::solve::GoalQueryData<'db>>,
        mapping: &super::solve::CanonicalMapping<'db>,
        response: &Stashed<super::solve::QueryResult<'db>>,

}

See more source ↗

Implemented crates/sage-ir/src/check/solve/boundary.rs:108–113

sage_ir::check::solve::boundary · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.canonical_outputs`
pub fn extract_query_result_with_output<'db>(
    db: &'db dyn crate::Db,
    state: &QueryProofState<'db>,
    output: GoalOutput<'db>,
    result: GoalResult<'db>,

}

See more source ↗

Implemented crates/sage-ir/src/check/solve/goal.rs:41–46

sage_ir::check::solve::goal · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.canonical_outputs`
pub enum SolverGoal<'db> {
    Prove(Goal<'db>),
    Normalize(AliasTy<'db>),
}


}

See more source ↗

Implemented crates/sage-ir/src/check/solve/merge.rs:16–21

sage_ir::check::solve::merge · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.canonical_outputs`
pub(crate) fn merge_candidate_results<'db>(
    db: &'db dyn crate::Db,
    next_response_param: u32,
    input_universes: &FxHashMap<AlphaEquivParam<'db>, u32>,
    input_domains: &FxHashMap<AlphaEquivParam<'db>, InferDomain>,

}

See more source ↗

Implemented crates/sage-ir/src/check/solve/prove.rs:639–644

sage_ir::check::solve::prove · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.canonical_outputs`
async fn solve_normalize_frame<'db>(
    db: &'db dyn crate::Db,
    whiteboard: &Whiteboard<'db>,
    query: &Stashed<GoalQueryData<'db>>,
    frame: &mut QueryProofState<'db>,

}

See more source ↗

Implemented crates/sage-ir/src/check/solve/result.rs:34–39

sage_ir::check::solve::result · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.canonical_outputs`
pub enum GoalOutput<'db> {
    Proven,
    Type(Ptr<Ty<'db>>),
}


}

See more source ↗

Tests and review

Indexed tests and the implementation-completeness and test-adequacy review; no test run is implied.

TODO sage_meta::todo::solver_canonical_outputs

crates/sage-meta/tests/semantic_spec.rs · test:semantic_spec

#![allow(unused)]
fn main() {
#[test]
    #[sage::test(crates.sage_ir.solver.canonical_outputs)]
    fn solver_canonical_outputs() {
        // TODO: Complete the claim-specific verification matrix:
        // Operation/output mismatch is rejected; type outputs containing repeated response-local
        // variables round-trip with sharing and universes intact; incompatible candidate outputs remain
        // ambiguous even when the caller expects one of them; trait proof never exposes a selected impl
        // identity.
    }
}

See more source ↗

Implemented sage_test_harness::trait_solver_boundary_tests::canonical_response_rejects_an_output_for_the_wrong_operation

crates/sage-test-harness/src/lib.rs · lib:sage_test_harness

#![allow(unused)]
fn main() {
#[test]
    #[should_panic(expected = "solver operation returned an incompatible output kind")]
    #[sage::test(crates.sage_ir.solver.canonical_outputs)]
    fn canonical_response_rejects_an_output_for_the_wrong_operation() {
        with_test_crate("trait Marker {}", |db, root| {
            let krate = crate_from_root_items(db, root);
            let mut stash = Stash::new();
            let assumptions = stash.alloc_slice::<Assumption>(&[]);
            let goal = Goal::true_(&mut stash);
            let canonical = canonicalize_goal(
                db,
                &stash,
                &VersionedEGraph::new(),
                Version::ROOT,
                krate,
                Universe::ROOT,
                true,
                assumptions,
                goal,
            );
            let mut proof = instantiate_query(&canonical.data);
            let output = proof.stash.alloc(Ty::Bool);
            let modulo = Goal::true_(&mut proof.stash);
            let _ = extract_query_result_with_output(
                db,
                &proof,
                GoalOutput::Type(output),
                GoalResult::Yes { modulo },
            );
        });
    }
}

Conditional source: #[cfg(test)]

See more source ↗

Implemented sage_test_harness::trait_solver_proof_tests::local_associated_type_normalization_produces_a_type_output

crates/sage-test-harness/src/lib.rs · lib:sage_test_harness

#![allow(unused)]
fn main() {
#[test]
    #[sage::test(crates.sage_ir.solver.canonical_outputs)]
    fn local_associated_type_normalization_produces_a_type_output() {
        with_test_crate(
            "trait Iterable { type Item; }\n\
             struct Wrap<T> { value: T }\n\
             impl<T> Iterable for Wrap<T> { type Item = T; }",
            |db, root| {
                let (iterable, krate) = trait_and_crate(db, root, "Iterable");
                let wrap = root
                    .expanded_module_items(db)
                    .iter()
                    .find_map(|symbol| match symbol.data(db) {
                        SymbolData::StructSymbol(StructSymbol::Local(item))
                            if item.name(db).text(db) == "Wrap" =>
                        {
                            Some(item)
                        }
                        SymbolData::StructSymbol(_)
                        | SymbolData::FnSymbol(_)
                        | SymbolData::EnumSymbol(_)
                        | SymbolData::VariantSymbol(_)
                        | SymbolData::VariantCtorSymbol(_)
                        | SymbolData::TraitSymbol(_)
                        | SymbolData::TypeAliasSymbol(_)
                        | SymbolData::ConstSymbol(_)
                        | SymbolData::StaticSymbol(_)
                        | SymbolData::ImplSymbol(_)
                        | SymbolData::ModSymbol(_)
                        | SymbolData::MacroDefSymbol(_)
                        | SymbolData::UseSymbol(_)
                        | SymbolData::IntrinsicTypeSymbol(_)
                        | SymbolData::MacroInvocationSymbol(_) => None,
                    })
                    .unwrap();
                let items = iterable.items(db).unwrap();
                let (item_stash, items) = items.open();
                let associated_ty = item_stash[items.value]
                    .iter()
                    .find_map(|item| match item {
                        TraitItemDef::Type(item) => Some(*item),
                        TraitItemDef::Function(_) | TraitItemDef::Const(_) => None,
                    })
                    .unwrap();

                let mut stash = Stash::new();
                let bool_ty = stash.alloc(Ty::Bool);
                let self_args = stash.alloc_slice(&[bool_ty]);
                let self_ty = stash.alloc(Ty::Adt(wrap.into(), self_args));
                let trait_args = stash.alloc_slice(&[]);
                let projection = AliasTy::Associated(ProjectionTy {
                    associated_ty,
                    self_ty,
                    trait_ref: TraitRef {
                        trait_sym: iterable,
                        args: trait_args,
                    },
                    args: stash.alloc_slice(&[]),
                });
                let assumptions = stash.alloc_slice::<Assumption>(&[]);
                let egraph = VersionedEGraph::new();
                let canonical = canonicalize_solver_goal(
                    db,
                    &stash,
                    &egraph,
                    Version::ROOT,
                    krate,
                    Universe::ROOT,
                    true,
                    assumptions,
                    SolverGoal::Normalize(projection),
                );
                let result = GoalQuery::new(db, canonical.data).solve(db);
                let (result_stash, result) = result.open();
                let QueryResultData::Yes {
                    output: GoalOutput::Type(output),
                    subst,
                    modulo,
                } = result.value
                else {
                    panic!("normalization should produce a type")
                };
                assert_eq!(result_stash[output], Ty::Bool);
                assert!(result_stash[subst].is_empty());
                assert!(modulo.is_trivially_true(result_stash));
            },
        );
    }
}

Conditional source: #[cfg(test)]

See more source ↗

Review: Accepted · Codex /root/anchor_094.

Reviewed the complete canonical_outputs claim, all six implementation associations and all three test entries. Captured the solver design, accepted goal-specific-output RFD and crate/trait lookup plus in-memory setup helpers. Source inspection only; no tests rerun and no source changes.

The claim distinguishes Prove(P)->Proven from input-only Normalize(Alias)->Type, requires output variables to participate in all canonical-response operations and forbids expected-type-directed candidate choice before merging. goal.rs models the operation explicitly and normalization carries only the alias; result.rs includes GoalOutput in a successful canonical response alongside substitution and residual goal, with response-local binders carrying universe/domain metadata. boundary.rs checks operation/output kind compatibility before extraction, copies substitutions, output and residual through one extractor, binds response variables and validates that no proof-local InferVar escapes. Its caller import uses the response binder/mapping and imports the output with the rest of the answer. goal.rs's tracked solve result includes this output-bearing response, so output is part of cached semantic knowledge rather than a separately inferred caller convention.

prove.rs normalization constructs candidate type outputs and merges complete candidate answers. merge.rs restricts the unconditional-proof shortcut to Proven with empty substitution/trivial residual and compares Type outputs when checking candidate subsumption; an arbitrary unconditional type is not a universal proof. infer_ctx.rs apply_normalization_relation receives the solved response, imports it transactionally, and only then relates its Type output to the caller expectation; Maybe/No returns discard rather than choosing a candidate matching that expectation. These six files provide the intended output flow, but inspection alone does not prove every variable-sharing/universe/cache/merge edge case.

canonical_response_rejects_an_output_for_the_wrong_operation deliberately builds a Prove(true) state and tries to extract a successful Type(bool), requiring the exact incompatible-output panic. This tests extraction rejection, not every malformed caller-import combination. local_associated_type_normalization_produces_a_type_output constructs the actual Iterable::Item projection for Wrap<bool>, canonicalizes input-only Normalize, invokes the solver and requires Yes with Type(bool), empty substitution and trivially true residual. Captured helpers obtain real local crate/trait identities and parse source, so the test exercises actual associated-type normalization rather than a fabricated response.

The solver_canonical_outputs TODO retains repeated response-local variable round trips with sharing/universes, incompatible outputs staying ambiguous despite a caller preference, and proof outputs not exposing a selected impl identity, along with complete mismatch validation. Its prerequisite is that broader canonical-output matrix, including caching/comparison/import behavior beyond the concrete bool case. It has no assertions and remains deferred evidence. All implementations/tests and every claim category are accounted for; the two ordinary cases are not promoted to exhaustive canonical-boundary proof. No concrete defect was identified in these inspected paths and no additional edits are requested.

Browse crates anchors

139 anchors

Specification anchors and declared coverage
AnchorImplementationTests
crates (139)114 Implemented37 TODO2 N/A74 Implemented107 TODO
crates.sage_inspector (15)13 Implemented1 TODO2 N/A3 Implemented15 TODO
crates.sage_inspector.inspection (15)13 Implemented1 TODO2 N/A3 Implemented15 TODO
balanced_tracesImplementedTODO
canonical_ownershipImplementedImplementedTODO
derive_reflectionImplementedImplementedTODO
detail_free_indexImplementedTODO
deterministic_traceImplementedTODO
durable_navigationN/ATODO
generic_browserN/ATODO
owned_reflectionImplementedImplementedTODO
product_availabilityImplementedTODO
revision_and_demandImplementedTODO
semantic_phase_boundaryImplementedTODO
source_evidenceImplementedTODO
typed_serviceImplementedTODO
unknown_workImplementedTODOTODO
workspace_actorImplementedTODO
crates.sage_ir (90)67 Implemented34 TODO40 Implemented88 TODO
crates.sage_ir.checking (12)12 Implemented3 TODO5 Implemented12 TODO
crates.sage_ir.checking.body (5)5 Implemented2 TODO3 Implemented5 TODO
elaborationImplementedImplementedTODO
expected_typesImplementedTODOTODO
interface_dependenciesImplementedImplementedTODO
isolated_completionImplementedImplementedTODO
operator_callsImplementedTODOTODO
identity_mintingImplementedTODO
owned_productsImplementedImplementedTODO
crates.sage_ir.checking.signature (4)4 Implemented1 TODO1 Implemented4 TODO
body_independenceImplementedTODO
narrow_detailImplementedTODOTODO
owner_binderImplementedImplementedTODO
storageImplementedTODO
symbol_keyed_interfacesImplementedTODO
crates.sage_ir.crate (9)9 TODO9 TODO
explicit_restrictionsTODOTODO
identity_before_detailTODOTODO
incremental_evidenceTODOTODO
narrow_demandsTODOTODO
reexecution_and_invalidationTODOTODO
represented_completenessTODOTODO
restrictions_and_gapsTODOTODO
semantic_query_boundariesTODOTODO
terminal_incompletenessTODOTODO
crates.sage_ir.inference (8)8 Implemented6 Implemented8 TODO
atomic_checkingImplementedImplementedTODO
body_local_quiescenceImplementedImplementedTODO
canonical_boundaryImplementedImplementedTODO
completed_body_boundaryImplementedTODO
numeric_domainsImplementedImplementedTODO
subtyping_and_coercionImplementedImplementedTODO
terminal_obligationsImplementedTODO
transaction_isolationImplementedImplementedTODO
crates.sage_ir.metadata (4)4 Implemented1 TODO4 TODO
explicit_incompletenessImplementedTODO
keyed_reuseImplementedTODOTODO
product_boundariesImplementedTODO
provider_authorityImplementedTODO
crates.sage_ir.modules (8)7 Implemented1 TODO4 Implemented8 TODO
crates.sage_ir.modules.expand (4)4 Implemented2 Implemented4 TODO
completenessImplementedImplementedTODO
dependenciesImplementedTODO
direct_membersImplementedTODO
recursion_and_fixpointImplementedImplementedTODO
crates.sage_ir.modules.parse (4)3 Implemented1 TODO2 Implemented4 TODO
dependenciesImplementedTODO
detail_firewallImplementedImplementedTODO
recovery_completenessTODOTODO
syntax_identitiesImplementedImplementedTODO
crates.sage_ir.resolution (5)5 Implemented1 TODO3 Implemented4 TODO
crates.sage_ir.resolution.lookup (5)5 Implemented1 TODO3 Implemented4 TODO
completenessImplementedTODOImplementedTODO
dependenciesImplementedTODO
expansion_import_ambiguityImplementedImplemented
identity_onlyImplementedTODO
precedenceImplementedImplementedTODO
crates.sage_ir.solver (9)7 Implemented7 TODO5 Implemented9 TODO
alternative_isolationImplementedTODOImplementedTODO
bounded_completenessImplementedTODOTODO
candidate_completenessImplementedTODO
canonical_cyclesTODOTODO
canonical_outputsImplementedImplementedTODO
local_index_firewallTODOTODO
normalization_demandImplementedTODOImplementedTODO
schedule_independenceImplementedTODOImplementedTODO
shared_final_resultImplementedTODOImplementedTODO
crates.sage_ir.symbols (8)8 Implemented4 Implemented7 TODO
associated_identityImplementedImplemented
associated_interfacesImplementedTODO
body_interfacesImplementedImplementedTODO
definition_identityImplementedTODO
external_fact_queriesImplementedTODO
external_identityImplementedTODO
kind_wrappersImplementedImplementedTODO
local_identityImplementedImplementedTODO
crates.sage_ir.types (27)16 Implemented12 TODO13 Implemented27 TODO
crates.sage_ir.types.aliases (2)1 Implemented1 TODO1 Implemented2 TODO
identityImplementedImplementedTODO
revelationTODOTODO
crates.sage_ir.types.binder (1)1 Implemented1 TODO1 Implemented1 TODO
owner_parametersImplementedTODOImplementedTODO
crates.sage_ir.types.body (13)4 Implemented9 TODO3 Implemented13 TODO
awaitTODOTODO
closuresTODOTODO
conditional_patternsTODOTODO
coroutinesTODOTODO
diagnosed_recoveryImplementedImplementedTODO
elaboratedTODOImplementedTODO
for_iterationTODOTODO
indexingTODOTODO
macro_expansionTODOTODO
no_inferenceImplementedImplementedTODO
resolved_referencesImplementedTODO
try_residualTODOTODO
typed_provenanceImplementedTODO
crates.sage_ir.types.calls (2)1 Implemented1 TODO1 Implemented2 TODO
dispatch_familiesTODOTODO
selected_semanticsImplementedImplementedTODO
crates.sage_ir.types.lifetimes (2)2 Implemented2 Implemented2 TODO
dummyImplementedImplementedTODO
unchecked_borrowsImplementedImplementedTODO
crates.sage_ir.types.operators (2)2 Implemented1 Implemented2 TODO
lazy_control_flowImplementedTODO
trait_callsImplementedImplementedTODO
scoped_identitiesImplementedTODO
crates.sage_ir.types.spans (4)4 Implemented4 Implemented4 TODO
generated_identityImplementedImplementedTODO
item_originImplementedImplementedTODO
offset_reuseImplementedImplementedTODO
relative_compositionImplementedImplementedTODO
crates.sage_oracle_harness (4)4 Implemented2 TODO1 Implemented4 TODO
crates.sage_oracle_harness.crate (4)4 Implemented2 TODO1 Implemented4 TODO
deterministic_emissionImplementedTODO
exact_comparisonImplementedTODOImplementedTODO
fixed_projectionImplementedTODO
independent_coverageImplementedTODOTODO
crates.sage_stash (5)5 Implemented5 Implemented
crates.sage_stash.storage (5)5 Implemented5 Implemented
handle_ownershipImplementedImplemented
immutable_entriesImplementedImplemented
query_valueImplementedImplemented
rooted_equalityImplementedImplemented
typed_interningImplementedImplemented
crates.sage_test_harness (25)25 Implemented25 Implemented
crates.sage_test_harness.compile_tests (25)25 Implemented25 Implemented
annotation_validationImplementedImplemented
blessing_gateImplementedImplemented
callsite_updatesImplementedImplemented
checking_scopeImplementedImplemented
compiler_conditionsImplementedImplemented
completed_typesImplementedImplemented
coordinatesImplementedImplemented
dependenciesImplementedImplemented
diagnostic_countsImplementedImplemented
diagnostic_locationsImplementedImplemented
editionImplementedImplemented
fixturesImplementedImplemented
grouped_observationsImplementedImplemented
invocationImplementedImplemented
production_executionImplementedImplemented
project_isolationImplementedImplemented
query_captureImplementedImplemented
query_projectionImplementedImplemented
renderingImplementedImplemented
resolved_symbolsImplementedImplemented
review_visibilityImplementedImplemented
rustc_executionImplementedImplemented
rustc_lintsImplementedImplemented
starting_expressionsImplementedImplemented
target_lineImplementedImplemented