diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_codegen_llvm/src/debuginfo/mod.rs | 81 | ||||
| -rw-r--r-- | compiler/rustc_codegen_llvm/src/debuginfo/utils.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_codegen_llvm/src/llvm/ffi.rs | 97 | ||||
| -rw-r--r-- | compiler/rustc_feature/src/unstable.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp | 53 | ||||
| -rw-r--r-- | compiler/rustc_mir_build/src/thir/pattern/check_match.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_next_trait_solver/src/solve/search_graph.rs | 26 | ||||
| -rw-r--r-- | compiler/rustc_type_ir/src/search_graph/mod.rs | 148 |
9 files changed, 225 insertions, 194 deletions
diff --git a/compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs b/compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs index 4ba72cd61a0..4b74c04ed7a 100644 --- a/compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs +++ b/compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs @@ -117,7 +117,7 @@ fn build_fixed_size_array_di_node<'ll, 'tcx>( .try_to_target_usize(cx.tcx) .expect("expected monomorphic const in codegen") as c_longlong; - let subrange = unsafe { llvm::LLVMRustDIBuilderGetOrCreateSubrange(DIB(cx), 0, upper_bound) }; + let subrange = unsafe { llvm::LLVMDIBuilderGetOrCreateSubrange(DIB(cx), 0, upper_bound) }; let subscripts = &[subrange]; let di_node = unsafe { diff --git a/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs b/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs index 126082aa3aa..af64e4ebed0 100644 --- a/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs +++ b/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs @@ -52,15 +52,6 @@ mod utils; use self::create_scope_map::compute_mir_scopes; pub(crate) use self::metadata::build_global_var_di_node; -// FIXME(Zalathar): These `DW_TAG_*` constants are fake values that were -// removed from LLVM in 2015, and are only used by our own `RustWrapper.cpp` -// to decide which C++ API to call. Instead, we should just have two separate -// FFI functions and choose the correct one on the Rust side. -#[allow(non_upper_case_globals)] -const DW_TAG_auto_variable: c_uint = 0x100; -#[allow(non_upper_case_globals)] -const DW_TAG_arg_variable: c_uint = 0x101; - /// A context object for maintaining all state needed by the debuginfo module. pub(crate) struct CodegenUnitDebugContext<'ll, 'tcx> { llmod: &'ll llvm::Module, @@ -174,35 +165,38 @@ impl<'ll> DebugInfoBuilderMethods for Builder<'_, 'll, '_> { if direct_offset.bytes() > 0 { addr_ops.push(DW_OP_plus_uconst); - addr_ops.push(direct_offset.bytes() as u64); + addr_ops.push(direct_offset.bytes()); } for &offset in indirect_offsets { addr_ops.push(DW_OP_deref); if offset.bytes() > 0 { addr_ops.push(DW_OP_plus_uconst); - addr_ops.push(offset.bytes() as u64); + addr_ops.push(offset.bytes()); } } if let Some(fragment) = fragment { // `DW_OP_LLVM_fragment` takes as arguments the fragment's // offset and size, both of them in bits. addr_ops.push(DW_OP_LLVM_fragment); - addr_ops.push(fragment.start.bits() as u64); - addr_ops.push((fragment.end - fragment.start).bits() as u64); + addr_ops.push(fragment.start.bits()); + addr_ops.push((fragment.end - fragment.start).bits()); } + let di_builder = DIB(self.cx()); + let addr_expr = unsafe { + llvm::LLVMDIBuilderCreateExpression(di_builder, addr_ops.as_ptr(), addr_ops.len()) + }; unsafe { // FIXME(eddyb) replace `llvm.dbg.declare` with `llvm.dbg.addr`. - llvm::LLVMRustDIBuilderInsertDeclareAtEnd( - DIB(self.cx()), + llvm::LLVMDIBuilderInsertDeclareRecordAtEnd( + di_builder, variable_alloca, dbg_var, - addr_ops.as_ptr(), - addr_ops.len() as c_uint, + addr_expr, dbg_loc, self.llbb(), - ); - } + ) + }; } fn set_dbg_loc(&mut self, dbg_loc: &'ll DILocation) { @@ -630,28 +624,39 @@ impl<'ll, 'tcx> DebugInfoCodegenMethods<'tcx> for CodegenCx<'ll, 'tcx> { let type_metadata = spanned_type_di_node(self, variable_type, span); - let (argument_index, dwarf_tag) = match variable_kind { - ArgumentVariable(index) => (index as c_uint, DW_TAG_arg_variable), - LocalVariable => (0, DW_TAG_auto_variable), - }; let align = self.align_of(variable_type); let name = variable_name.as_str(); - unsafe { - llvm::LLVMRustDIBuilderCreateVariable( - DIB(self), - dwarf_tag, - scope_metadata, - name.as_c_char_ptr(), - name.len(), - file_metadata, - loc.line, - type_metadata, - true, - DIFlags::FlagZero, - argument_index, - align.bits() as u32, - ) + + match variable_kind { + ArgumentVariable(arg_index) => unsafe { + llvm::LLVMDIBuilderCreateParameterVariable( + DIB(self), + scope_metadata, + name.as_ptr(), + name.len(), + arg_index as c_uint, + file_metadata, + loc.line, + type_metadata, + llvm::Bool::TRUE, // (preserve descriptor during optimizations) + DIFlags::FlagZero, + ) + }, + LocalVariable => unsafe { + llvm::LLVMDIBuilderCreateAutoVariable( + DIB(self), + scope_metadata, + name.as_ptr(), + name.len(), + file_metadata, + loc.line, + type_metadata, + llvm::Bool::TRUE, // (preserve descriptor during optimizations) + DIFlags::FlagZero, + align.bits() as u32, + ) + }, } } } diff --git a/compiler/rustc_codegen_llvm/src/debuginfo/utils.rs b/compiler/rustc_codegen_llvm/src/debuginfo/utils.rs index cc1d504b430..7e1e49310f6 100644 --- a/compiler/rustc_codegen_llvm/src/debuginfo/utils.rs +++ b/compiler/rustc_codegen_llvm/src/debuginfo/utils.rs @@ -28,7 +28,7 @@ pub(crate) fn create_DIArray<'ll>( builder: &DIBuilder<'ll>, arr: &[Option<&'ll DIDescriptor>], ) -> &'ll DIArray { - unsafe { llvm::LLVMRustDIBuilderGetOrCreateArray(builder, arr.as_ptr(), arr.len() as u32) } + unsafe { llvm::LLVMDIBuilderGetOrCreateArray(builder, arr.as_ptr(), arr.len()) } } #[inline] diff --git a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs index 38a6a311954..afd2991a09c 100644 --- a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs +++ b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs @@ -25,8 +25,8 @@ use rustc_target::spec::SymbolVisibility; use super::RustString; use super::debuginfo::{ DIArray, DIBuilder, DIDerivedType, DIDescriptor, DIEnumerator, DIFile, DIFlags, - DIGlobalVariableExpression, DILocation, DISPFlags, DIScope, DISubprogram, DISubrange, - DITemplateTypeParameter, DIType, DIVariable, DebugEmissionKind, DebugNameTableKind, + DIGlobalVariableExpression, DILocation, DISPFlags, DIScope, DISubprogram, + DITemplateTypeParameter, DIType, DebugEmissionKind, DebugNameTableKind, }; use crate::llvm; @@ -807,6 +807,8 @@ unsafe extern "C" { pub(crate) type Metadata; pub(crate) type BasicBlock; pub(crate) type Comdat; + /// `&'ll DbgRecord` represents `LLVMDbgRecordRef`. + pub(crate) type DbgRecord; } #[repr(C)] pub(crate) struct Builder<'a>(InvariantOpaque<'a>); @@ -891,7 +893,6 @@ pub(crate) mod debuginfo { pub(crate) type DIVariable = DIDescriptor; pub(crate) type DIGlobalVariableExpression = DIDescriptor; pub(crate) type DIArray = DIDescriptor; - pub(crate) type DISubrange = DIDescriptor; pub(crate) type DIEnumerator = DIDescriptor; pub(crate) type DITemplateTypeParameter = DIDescriptor; @@ -1992,6 +1993,59 @@ unsafe extern "C" { Scope: Option<&'ll Metadata>, AlignInBits: u32, // (optional; default is 0) ) -> &'ll Metadata; + + pub(crate) fn LLVMDIBuilderGetOrCreateSubrange<'ll>( + Builder: &DIBuilder<'ll>, + LowerBound: i64, + Count: i64, + ) -> &'ll Metadata; + + pub(crate) fn LLVMDIBuilderGetOrCreateArray<'ll>( + Builder: &DIBuilder<'ll>, + Data: *const Option<&'ll Metadata>, + NumElements: size_t, + ) -> &'ll Metadata; + + pub(crate) fn LLVMDIBuilderCreateExpression<'ll>( + Builder: &DIBuilder<'ll>, + Addr: *const u64, + Length: size_t, + ) -> &'ll Metadata; + + pub(crate) fn LLVMDIBuilderInsertDeclareRecordAtEnd<'ll>( + Builder: &DIBuilder<'ll>, + Storage: &'ll Value, + VarInfo: &'ll Metadata, + Expr: &'ll Metadata, + DebugLoc: &'ll Metadata, + Block: &'ll BasicBlock, + ) -> &'ll DbgRecord; + + pub(crate) fn LLVMDIBuilderCreateAutoVariable<'ll>( + Builder: &DIBuilder<'ll>, + Scope: &'ll Metadata, + Name: *const c_uchar, // See "PTR_LEN_STR". + NameLen: size_t, + File: &'ll Metadata, + LineNo: c_uint, + Ty: &'ll Metadata, + AlwaysPreserve: llvm::Bool, // "If true, this descriptor will survive optimizations." + Flags: DIFlags, + AlignInBits: u32, + ) -> &'ll Metadata; + + pub(crate) fn LLVMDIBuilderCreateParameterVariable<'ll>( + Builder: &DIBuilder<'ll>, + Scope: &'ll Metadata, + Name: *const c_uchar, // See "PTR_LEN_STR". + NameLen: size_t, + ArgNo: c_uint, + File: &'ll Metadata, + LineNo: c_uint, + Ty: &'ll Metadata, + AlwaysPreserve: llvm::Bool, // "If true, this descriptor will survive optimizations." + Flags: DIFlags, + ) -> &'ll Metadata; } #[link(name = "llvm-wrapper", kind = "static")] @@ -2358,43 +2412,6 @@ unsafe extern "C" { AlignInBits: u32, ) -> &'a DIGlobalVariableExpression; - pub(crate) fn LLVMRustDIBuilderCreateVariable<'a>( - Builder: &DIBuilder<'a>, - Tag: c_uint, - Scope: &'a DIDescriptor, - Name: *const c_char, - NameLen: size_t, - File: &'a DIFile, - LineNo: c_uint, - Ty: &'a DIType, - AlwaysPreserve: bool, - Flags: DIFlags, - ArgNo: c_uint, - AlignInBits: u32, - ) -> &'a DIVariable; - - pub(crate) fn LLVMRustDIBuilderGetOrCreateSubrange<'a>( - Builder: &DIBuilder<'a>, - Lo: i64, - Count: i64, - ) -> &'a DISubrange; - - pub(crate) fn LLVMRustDIBuilderGetOrCreateArray<'a>( - Builder: &DIBuilder<'a>, - Ptr: *const Option<&'a DIDescriptor>, - Count: c_uint, - ) -> &'a DIArray; - - pub(crate) fn LLVMRustDIBuilderInsertDeclareAtEnd<'a>( - Builder: &DIBuilder<'a>, - Val: &'a Value, - VarInfo: &'a DIVariable, - AddrOps: *const u64, - AddrOpsCount: c_uint, - DL: &'a DILocation, - InsertAtEnd: &'a BasicBlock, - ); - pub(crate) fn LLVMRustDIBuilderCreateEnumerator<'a>( Builder: &DIBuilder<'a>, Name: *const c_char, diff --git a/compiler/rustc_feature/src/unstable.rs b/compiler/rustc_feature/src/unstable.rs index b286ae3eb23..e63f29a9570 100644 --- a/compiler/rustc_feature/src/unstable.rs +++ b/compiler/rustc_feature/src/unstable.rs @@ -550,7 +550,7 @@ declare_features! ( /// Allows fused `loop`/`match` for direct intraprocedural jumps. (incomplete, loop_match, "1.90.0", Some(132306)), /// Allow `macro_rules!` attribute rules - (unstable, macro_attr, "1.91.0", Some(83527)), + (unstable, macro_attr, "1.91.0", Some(143547)), /// Allow `macro_rules!` derive rules (unstable, macro_derive, "1.91.0", Some(143549)), /// Give access to additional metadata about declarative macro meta-variables. diff --git a/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp b/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp index 9953f5e1731..2bfe3f7040c 100644 --- a/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp +++ b/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp @@ -990,14 +990,6 @@ extern "C" void LLVMRustGlobalAddMetadata(LLVMValueRef Global, unsigned Kind, unwrap<GlobalObject>(Global)->addMetadata(Kind, *unwrap<MDNode>(MD)); } -extern "C" LLVMDIBuilderRef LLVMRustDIBuilderCreate(LLVMModuleRef M) { - return wrap(new DIBuilder(*unwrap(M))); -} - -extern "C" void LLVMRustDIBuilderDispose(LLVMDIBuilderRef Builder) { - delete unwrap(Builder); -} - extern "C" LLVMMetadataRef LLVMRustDIBuilderCreateCompileUnit( LLVMDIBuilderRef Builder, unsigned Lang, LLVMMetadataRef FileRef, const char *Producer, size_t ProducerLen, bool isOptimized, @@ -1129,51 +1121,6 @@ extern "C" LLVMMetadataRef LLVMRustDIBuilderCreateStaticVariable( return wrap(VarExpr); } -extern "C" LLVMMetadataRef LLVMRustDIBuilderCreateVariable( - LLVMDIBuilderRef Builder, unsigned Tag, LLVMMetadataRef Scope, - const char *Name, size_t NameLen, LLVMMetadataRef File, unsigned LineNo, - LLVMMetadataRef Ty, bool AlwaysPreserve, LLVMDIFlags Flags, unsigned ArgNo, - uint32_t AlignInBits) { - if (Tag == 0x100) { // DW_TAG_auto_variable - return wrap(unwrap(Builder)->createAutoVariable( - unwrapDI<DIDescriptor>(Scope), StringRef(Name, NameLen), - unwrapDI<DIFile>(File), LineNo, unwrapDI<DIType>(Ty), AlwaysPreserve, - fromRust(Flags), AlignInBits)); - } else { - return wrap(unwrap(Builder)->createParameterVariable( - unwrapDI<DIDescriptor>(Scope), StringRef(Name, NameLen), ArgNo, - unwrapDI<DIFile>(File), LineNo, unwrapDI<DIType>(Ty), AlwaysPreserve, - fromRust(Flags))); - } -} - -extern "C" LLVMMetadataRef -LLVMRustDIBuilderGetOrCreateSubrange(LLVMDIBuilderRef Builder, int64_t Lo, - int64_t Count) { - return wrap(unwrap(Builder)->getOrCreateSubrange(Lo, Count)); -} - -extern "C" LLVMMetadataRef -LLVMRustDIBuilderGetOrCreateArray(LLVMDIBuilderRef Builder, - LLVMMetadataRef *Ptr, unsigned Count) { - Metadata **DataValue = unwrap(Ptr); - return wrap(unwrap(Builder) - ->getOrCreateArray(ArrayRef<Metadata *>(DataValue, Count)) - .get()); -} - -extern "C" void -LLVMRustDIBuilderInsertDeclareAtEnd(LLVMDIBuilderRef Builder, LLVMValueRef V, - LLVMMetadataRef VarInfo, uint64_t *AddrOps, - unsigned AddrOpsCount, LLVMMetadataRef DL, - LLVMBasicBlockRef InsertAtEnd) { - unwrap(Builder)->insertDeclare( - unwrap(V), unwrap<DILocalVariable>(VarInfo), - unwrap(Builder)->createExpression( - llvm::ArrayRef<uint64_t>(AddrOps, AddrOpsCount)), - DebugLoc(cast<MDNode>(unwrap(DL))), unwrap(InsertAtEnd)); -} - extern "C" LLVMMetadataRef LLVMRustDIBuilderCreateEnumerator(LLVMDIBuilderRef Builder, const char *Name, size_t NameLen, const uint64_t Value[2], diff --git a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs index ae67bb5075e..3929a97eed8 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/check_match.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/check_match.rs @@ -1275,13 +1275,13 @@ fn report_non_exhaustive_match<'p, 'tcx>( if ty.is_ptr_sized_integral() { if ty.inner() == cx.tcx.types.usize { err.note(format!( - "`{ty}` does not have a fixed maximum value, so half-open ranges are \ - necessary to match exhaustively", + "`{ty}::MAX` is not treated as exhaustive, \ + so half-open ranges are necessary to match exhaustively", )); } else if ty.inner() == cx.tcx.types.isize { err.note(format!( - "`{ty}` does not have fixed minimum and maximum values, so half-open \ - ranges are necessary to match exhaustively", + "`{ty}::MIN` and `{ty}::MAX` are not treated as exhaustive, \ + so half-open ranges are necessary to match exhaustively", )); } } else if ty.inner() == cx.tcx.types.str_ { diff --git a/compiler/rustc_next_trait_solver/src/solve/search_graph.rs b/compiler/rustc_next_trait_solver/src/solve/search_graph.rs index aa9dfc9a9a2..109c8476ccb 100644 --- a/compiler/rustc_next_trait_solver/src/solve/search_graph.rs +++ b/compiler/rustc_next_trait_solver/src/solve/search_graph.rs @@ -74,20 +74,28 @@ where } } - fn is_initial_provisional_result( - cx: Self::Cx, - kind: PathKind, - input: CanonicalInput<I>, - result: QueryResult<I>, - ) -> bool { - Self::initial_provisional_result(cx, kind, input) == result + fn is_initial_provisional_result(result: QueryResult<I>) -> Option<PathKind> { + match result { + Ok(response) => { + if has_no_inference_or_external_constraints(response) { + if response.value.certainty == Certainty::Yes { + return Some(PathKind::Coinductive); + } else if response.value.certainty == Certainty::overflow(false) { + return Some(PathKind::Unknown); + } + } + + None + } + Err(NoSolution) => Some(PathKind::Inductive), + } } - fn on_stack_overflow(cx: I, input: CanonicalInput<I>) -> QueryResult<I> { + fn stack_overflow_result(cx: I, input: CanonicalInput<I>) -> QueryResult<I> { response_no_constraints(cx, input, Certainty::overflow(true)) } - fn on_fixpoint_overflow(cx: I, input: CanonicalInput<I>) -> QueryResult<I> { + fn fixpoint_overflow_result(cx: I, input: CanonicalInput<I>) -> QueryResult<I> { response_no_constraints(cx, input, Certainty::overflow(false)) } diff --git a/compiler/rustc_type_ir/src/search_graph/mod.rs b/compiler/rustc_type_ir/src/search_graph/mod.rs index 8f8f019510f..7aa58d096d5 100644 --- a/compiler/rustc_type_ir/src/search_graph/mod.rs +++ b/compiler/rustc_type_ir/src/search_graph/mod.rs @@ -86,14 +86,12 @@ pub trait Delegate: Sized { kind: PathKind, input: <Self::Cx as Cx>::Input, ) -> <Self::Cx as Cx>::Result; - fn is_initial_provisional_result( + fn is_initial_provisional_result(result: <Self::Cx as Cx>::Result) -> Option<PathKind>; + fn stack_overflow_result( cx: Self::Cx, - kind: PathKind, input: <Self::Cx as Cx>::Input, - result: <Self::Cx as Cx>::Result, - ) -> bool; - fn on_stack_overflow(cx: Self::Cx, input: <Self::Cx as Cx>::Input) -> <Self::Cx as Cx>::Result; - fn on_fixpoint_overflow( + ) -> <Self::Cx as Cx>::Result; + fn fixpoint_overflow_result( cx: Self::Cx, input: <Self::Cx as Cx>::Input, ) -> <Self::Cx as Cx>::Result; @@ -215,6 +213,27 @@ impl HeadUsages { let HeadUsages { inductive, unknown, coinductive, forced_ambiguity } = self; inductive == 0 && unknown == 0 && coinductive == 0 && forced_ambiguity == 0 } + + fn is_single(self, path_kind: PathKind) -> bool { + match path_kind { + PathKind::Inductive => matches!( + self, + HeadUsages { inductive: _, unknown: 0, coinductive: 0, forced_ambiguity: 0 }, + ), + PathKind::Unknown => matches!( + self, + HeadUsages { inductive: 0, unknown: _, coinductive: 0, forced_ambiguity: 0 }, + ), + PathKind::Coinductive => matches!( + self, + HeadUsages { inductive: 0, unknown: 0, coinductive: _, forced_ambiguity: 0 }, + ), + PathKind::ForcedAmbiguity => matches!( + self, + HeadUsages { inductive: 0, unknown: 0, coinductive: 0, forced_ambiguity: _ }, + ), + } + } } #[derive(Debug, Default)] @@ -869,7 +888,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { } debug!("encountered stack overflow"); - D::on_stack_overflow(cx, input) + D::stack_overflow_result(cx, input) } /// When reevaluating a goal with a changed provisional result, all provisional cache entry @@ -888,7 +907,29 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { !entries.is_empty() }); } +} +/// We need to rebase provisional cache entries when popping one of their cycle +/// heads from the stack. This may not necessarily mean that we've actually +/// reached a fixpoint for that cycle head, which impacts the way we rebase +/// provisional cache entries. +enum RebaseReason { + NoCycleUsages, + Ambiguity, + Overflow, + /// We've actually reached a fixpoint. + /// + /// This either happens in the first evaluation step for the cycle head. + /// In this case the used provisional result depends on the cycle `PathKind`. + /// We store this path kind to check whether the the provisional cache entry + /// we're rebasing relied on the same cycles. + /// + /// In later iterations cycles always return `stack_entry.provisional_result` + /// so we no longer depend on the `PathKind`. We store `None` in that case. + ReachedFixpoint(Option<PathKind>), +} + +impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D, X> { /// A necessary optimization to handle complex solver cycles. A provisional cache entry /// relies on a set of cycle heads and the path towards these heads. When popping a cycle /// head from the stack after we've finished computing it, we can't be sure that the @@ -908,8 +949,9 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { /// to me. fn rebase_provisional_cache_entries( &mut self, + cx: X, stack_entry: &StackEntry<X>, - mut mutate_result: impl FnMut(X::Input, X::Result) -> X::Result, + rebase_reason: RebaseReason, ) { let popped_head_index = self.stack.next_index(); #[allow(rustc::potential_query_instability)] @@ -927,6 +969,10 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { return true; }; + let Some(new_highest_head_index) = heads.opt_highest_cycle_head_index() else { + return false; + }; + // We're rebasing an entry `e` over a head `p`. This head // has a number of own heads `h` it depends on. // @@ -977,22 +1023,37 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { let eph = ep.extend_with_paths(ph); heads.insert(head_index, eph, head.usages); } - } - let Some(head_index) = heads.opt_highest_cycle_head_index() else { - return false; - }; + // The provisional cache entry does depend on the provisional result + // of the popped cycle head. We need to mutate the result of our + // provisional cache entry in case we did not reach a fixpoint. + match rebase_reason { + // If the cycle head does not actually depend on itself, then + // the provisional result used by the provisional cache entry + // is not actually equal to the final provisional result. We + // need to discard the provisional cache entry in this case. + RebaseReason::NoCycleUsages => return false, + RebaseReason::Ambiguity => { + *result = D::propagate_ambiguity(cx, input, *result); + } + RebaseReason::Overflow => *result = D::fixpoint_overflow_result(cx, input), + RebaseReason::ReachedFixpoint(None) => {} + RebaseReason::ReachedFixpoint(Some(path_kind)) => { + if !popped_head.usages.is_single(path_kind) { + return false; + } + } + }; + } // We now care about the path from the next highest cycle head to the // provisional cache entry. *path_from_head = path_from_head.extend(Self::cycle_path_kind( &self.stack, stack_entry.step_kind_from_parent, - head_index, + new_highest_head_index, )); - // Mutate the result of the provisional cache entry in case we did - // not reach a fixpoint. - *result = mutate_result(input, *result); + true }); !entries.is_empty() @@ -1209,33 +1270,19 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { /// Whether we've reached a fixpoint when evaluating a cycle head. fn reached_fixpoint( &mut self, - cx: X, stack_entry: &StackEntry<X>, usages: HeadUsages, result: X::Result, - ) -> bool { + ) -> Result<Option<PathKind>, ()> { let provisional_result = stack_entry.provisional_result; - if usages.is_empty() { - true - } else if let Some(provisional_result) = provisional_result { - provisional_result == result + if let Some(provisional_result) = provisional_result { + if provisional_result == result { Ok(None) } else { Err(()) } + } else if let Some(path_kind) = D::is_initial_provisional_result(result) + .filter(|&path_kind| usages.is_single(path_kind)) + { + Ok(Some(path_kind)) } else { - let check = |k| D::is_initial_provisional_result(cx, k, stack_entry.input, result); - match usages { - HeadUsages { inductive: _, unknown: 0, coinductive: 0, forced_ambiguity: 0 } => { - check(PathKind::Inductive) - } - HeadUsages { inductive: 0, unknown: _, coinductive: 0, forced_ambiguity: 0 } => { - check(PathKind::Unknown) - } - HeadUsages { inductive: 0, unknown: 0, coinductive: _, forced_ambiguity: 0 } => { - check(PathKind::Coinductive) - } - HeadUsages { inductive: 0, unknown: 0, coinductive: 0, forced_ambiguity: _ } => { - check(PathKind::ForcedAmbiguity) - } - _ => false, - } + Err(()) } } @@ -1280,8 +1327,19 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { // is equal to the provisional result of the previous iteration, or because // this was only the head of either coinductive or inductive cycles, and the // final result is equal to the initial response for that case. - if self.reached_fixpoint(cx, &stack_entry, usages, result) { - self.rebase_provisional_cache_entries(&stack_entry, |_, result| result); + if let Ok(fixpoint) = self.reached_fixpoint(&stack_entry, usages, result) { + self.rebase_provisional_cache_entries( + cx, + &stack_entry, + RebaseReason::ReachedFixpoint(fixpoint), + ); + return EvaluationResult::finalize(stack_entry, encountered_overflow, result); + } else if usages.is_empty() { + self.rebase_provisional_cache_entries( + cx, + &stack_entry, + RebaseReason::NoCycleUsages, + ); return EvaluationResult::finalize(stack_entry, encountered_overflow, result); } @@ -1298,9 +1356,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { // we also taint all provisional cache entries which depend on the // current goal. if D::is_ambiguous_result(result) { - self.rebase_provisional_cache_entries(&stack_entry, |input, _| { - D::propagate_ambiguity(cx, input, result) - }); + self.rebase_provisional_cache_entries(cx, &stack_entry, RebaseReason::Ambiguity); return EvaluationResult::finalize(stack_entry, encountered_overflow, result); }; @@ -1309,10 +1365,8 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { i += 1; if i >= D::FIXPOINT_STEP_LIMIT { debug!("canonical cycle overflow"); - let result = D::on_fixpoint_overflow(cx, input); - self.rebase_provisional_cache_entries(&stack_entry, |input, _| { - D::on_fixpoint_overflow(cx, input) - }); + let result = D::fixpoint_overflow_result(cx, input); + self.rebase_provisional_cache_entries(cx, &stack_entry, RebaseReason::Overflow); return EvaluationResult::finalize(stack_entry, encountered_overflow, result); } |