rustc_type_ir/search_graph/
global_cache.rs

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

rustc_type_ir/search_graph/
global_cache.rs
