rustc_type_ir/search_graph/
global_cache.rs

1use derive_where::derive_where;
2
3use super::{AvailableDepth, Cx, NestedGoals};
4use crate::data_structures::HashMap;
5use crate::search_graph::EvaluationResult;
6
7struct Success<X: Cx> {
8    required_depth: usize,
9    nested_goals: NestedGoals<X>,
10    result: X::Tracked<X::Result>,
11}
12
13struct WithOverflow<X: Cx> {
14    nested_goals: NestedGoals<X>,
15    result: X::Tracked<X::Result>,
16}
17
18/// The cache entry for a given input.
19///
20/// This contains results whose computation never hit the
21/// recursion limit in `success`, and all results which hit
22/// the recursion limit in `with_overflow`.
23#[derive_where(Default; X: Cx)]
24struct CacheEntry<X: Cx> {
25    success: Option<Success<X>>,
26    with_overflow: HashMap<usize, WithOverflow<X>>,
27}
28
29#[derive_where(Debug; X: Cx)]
30pub(super) struct CacheData<'a, X: Cx> {
31    pub(super) result: X::Result,
32    pub(super) required_depth: usize,
33    pub(super) encountered_overflow: bool,
34    pub(super) nested_goals: &'a NestedGoals<X>,
35}
36#[derive_where(Default; X: Cx)]
37pub struct GlobalCache<X: Cx> {
38    map: HashMap<X::Input, CacheEntry<X>>,
39}
40
41impl<X: Cx> GlobalCache<X> {
42    /// Insert a final result into the global cache.
43    pub(super) fn insert(
44        &mut self,
45        cx: X,
46        input: X::Input,
47        evaluation_result: EvaluationResult<X>,
48        dep_node: X::DepNodeIndex,
49    ) {
50        let EvaluationResult { encountered_overflow, required_depth, heads, nested_goals, result } =
51            evaluation_result;
52        debug_assert!(heads.is_empty());
53        let result = cx.mk_tracked(result, dep_node);
54        let entry = self.map.entry(input).or_default();
55        if encountered_overflow {
56            let with_overflow = WithOverflow { nested_goals, result };
57            let prev = entry.with_overflow.insert(required_depth, with_overflow);
58            if let Some(prev) = &prev {
59                cx.assert_evaluation_is_concurrent();
60                assert_eq!(cx.get_tracked(&prev.result), evaluation_result.result);
61            }
62        } else {
63            let prev = entry.success.replace(Success { required_depth, nested_goals, result });
64            if let Some(prev) = &prev {
65                cx.assert_evaluation_is_concurrent();
66                assert_eq!(cx.get_tracked(&prev.result), evaluation_result.result);
67            }
68        }
69    }
70
71    /// Try to fetch a cached result, checking the recursion limit
72    /// and handling root goals of coinductive cycles.
73    ///
74    /// If this returns `Some` the cache result can be used.
75    pub(super) fn get<'a>(
76        &'a self,
77        cx: X,
78        input: X::Input,
79        available_depth: AvailableDepth,
80        mut candidate_is_applicable: impl FnMut(&NestedGoals<X>) -> bool,
81    ) -> Option<CacheData<'a, X>> {
82        let entry = self.map.get(&input)?;
83        if let Some(Success { required_depth, ref nested_goals, ref result }) = entry.success
84            && available_depth.cache_entry_is_applicable(required_depth)
85            && candidate_is_applicable(nested_goals)
86        {
87            return Some(CacheData {
88                result: cx.get_tracked(&result),
89                required_depth,
90                encountered_overflow: false,
91                nested_goals,
92            });
93        }
94
95        let additional_depth = available_depth.0;
96        if let Some(WithOverflow { nested_goals, result }) =
97            entry.with_overflow.get(&additional_depth)
98            && candidate_is_applicable(nested_goals)
99        {
100            return Some(CacheData {
101                result: cx.get_tracked(result),
102                required_depth: additional_depth,
103                encountered_overflow: true,
104                nested_goals,
105            });
106        }
107
108        None
109    }
110}
rustc_type_ir/search_graph/global_cache.rs

rustc_type_ir/search_graph/
global_cache.rs
