crates.sage_ir.solver.candidate_completeness

Candidate discovery is global, trait-keyed, conservative, and completeness-carrying. A proof considers represented impls in the local crate and every reachable dependency, keyed first by the fixed trait. Any self-head refinement retains blanket and unclassifiable fallback candidates, and a missing or incomplete source prevents exhaustive No. This is the solver consequence of Trait impl discovery is global and trait-keyed and Incompleteness is an explicit terminal outcome.

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

Implementation

Implemented crates/sage-ir/src/check/solve/clauses.rs:37–42

sage_ir::check::solve::clauses · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.candidate_completeness`
// {anchor}`crates.sage_ir.modules.expand.completeness`
pub(crate) fn assemble_candidates<'db>(
    db: &'db dyn crate::Db,
    state: &QueryProofState<'db>,
    version: Version,

}

See more source ↗

Implemented crates/sage-ir/src/check/solve/merge.rs:15–20

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

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.candidate_completeness`
// {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>,

}

See more source ↗

Implemented crates/sage-ir/src/check/solve/prove.rs:982–987

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

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.candidate_completeness`
async fn solve_trait_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/external_syms.rs:174–179

sage_ir::external_syms · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.candidate_completeness`
pub fn external_relevant_impls<'db>(
    db: &'db dyn crate::Db,
    trait_sym: SymExt<'db>,
    self_head: Option<SimplifiedSelfType<'db>>,
) -> ExternalImplCandidates<'db> {

}

See more source ↗

Implemented crates/sage-ir/src/local_syms/impls.rs:252–257

sage_ir::local_syms::impls · lib:sage_ir

#![allow(unused)]
fn main() {
// {anchor}`crates.sage_ir.solver.candidate_completeness`
pub fn local_impl_candidates<'db>(
    db: &'db dyn crate::Db,
    krate: crate::scope::LocalCrateSymbol<'db>,
    target_trait: crate::symbol::TraitSymbol<'db>,
) -> LocalImplCandidates<'db> {

}

See more source ↗

Implemented crates/sage-rustc-bridge/src/tcx_impl.rs:688–693

sage_rustc_bridge::tcx_impl · lib:sage_rustc_bridge

#![allow(unused)]
fn main() {
    // {anchor}`crates.sage_ir.solver.candidate_completeness`
    pub fn relevant_trait_impls(
        &self,
        crate_num: CrateNum,
        def_index: DefIndex,
        self_head: Option<sage_ir::tcx::RawSelfTypeHead>,

}

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_candidate_completeness

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

#![allow(unused)]
fn main() {
#[test]
    #[sage::test(crates.sage_ir.solver.candidate_completeness)]
    fn solver_candidate_completeness() {
        // TODO: Complete the claim-specific verification matrix:
        // Local, upstream, blanket, and unsimplifiable fixtures show that indexed discovery loses no
        // exhaustive candidate; unrelated traits and provably disjoint rigid heads are absent; indexed
        // and exhaustive enumeration produce identical canonical responses; incomplete sources never
        // manufacture `No`; and a primitive operator proof reads its ordinary `core` impl metadata rather
        // than a synthetic operator candidate.
    }
}

See more source ↗

Review: Accepted · Codex /root/macro_fix_anchor.

Freshly reviewed the complete candidate_completeness claim, all six ordinary implementation associations and the sole explicit TODO test. Captured current module expansion/completeness helpers as a whole file rather than retaining shifted/truncated line fragments, anti-unification, builtin derive support, metadata-provider contract, solver guide and both architectural rationales. An out-of-bounds initial module range was rejected and replaced with that whole-file capture. No production edits.

The claim requires the local compilation plus reachable dependency metadata, fixed-trait primary lookup, conservative self-head refinement retaining blanket/unclassified cases, and incomplete sources preventing exhaustive No. clauses.rs assemble_candidates includes matching environment facts, tracks incomplete assumptions, and retains uncertainty for unknown self shapes or missing/ineligible trait signatures. Ordinary traits request trait-keyed local candidates and, for external traits, external candidates optionally refined by a coarse self head. Missing/ineligible impl signatures propagate incompleteness. Structural Sized/MetaSized candidates remain separate; ordinary operator traits are not synthesized here. The orphan shortcut requires a foreign trait with no trait arguments and a definitely non-fundamental foreign nominal self; unavailable metadata does not authorize pruning.

impls.rs local_impl_candidates scans expanded local modules under a fixed trait query, retaining matching impl identities and marking unresolved headers, unsupported transformations and expansion hazards incomplete. It does not implement the separately planned private local index; the captured RFD explicitly retains that incremental work. Module completeness checks conservatively retain failed/unresolved/depth-limited item macros and relevant unsupported derives. An unrelated known builtin derive can be complete for a different hygienic trait, while unresolved derive identities remain incomplete. The current symbol_local_item visibility change does not alter these checks.

external_syms.rs preserves provider completeness, returns empty-incomplete on unavailable data, and downgrades wrongly tagged impl identities. Its self simplifier leaves aliases/parameters/unknown shapes unrefined. The rustc bridge requests all_impls for the fixed trait, excludes rustc-local identities owned by Sage source, retains unclassifiable/blanket heads and removes only classified unequal heads, then sorts/deduplicates identities. Its classifier returns None for parameter/alias and unsupported forms. It withholds completeness for auto traits and unmodeled builtin sources, with explicit operator impls and the rigid-ADT Iterator case handled deliberately. The captured TcxDb interface states the same conservative provider contract. This is inspection of source behavior, not an independent proof of external metadata exhaustiveness.

prove.rs carries candidate completeness through isolated proof execution to merge_candidate_results. merge.rs emits No only with no surviving Yes/Maybe and a complete source; otherwise anti_unify.rs adds an unconstrained possible source and returns conservative Maybe. A genuinely unconditional Proven answer can establish Yes without exhaustive enumeration, which does not manufacture a negative conclusion or a type-valued result.

The sole associated solver_candidate_completeness test is assertion-free TODO. It explicitly retains local/upstream/blanket/unclassifiable fixtures, unrelated trait/disjoint head exclusion, indexed-versus-exhaustive canonical response equivalence, incomplete-source negative prevention and primitive operator metadata provenance. Prerequisites are source/dependency fixtures, an exhaustive comparison observation path and query/provenance assertions. Nearby tests are not silently counted as associated evidence, and inspection does not discharge these runtime comparisons. No N/A entries apply.

No behavior tests were executed for this anchor review, because its only associated test is deferred; commands used were review start/read and source inspection before recording. Every implementation entry and qualification is accounted for, with the explicit verification TODO preserved. No additional edits 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