typr_core/components/context/
graph.rs

1use crate::components::context::Context;
2use crate::components::r#type::type_system::TypeSystem;
3use serde::Deserialize;
4use serde::Serialize;
5use std::collections::HashMap;
6use std::collections::HashSet;
7use std::fmt::Debug;
8use std::ops::Add;
9use std::sync::Arc;
10
11/// `memory`/`root` hold the whole-program subtype registry (grows with every
12/// distinct type seen — stdlib signatures included), and used to be
13/// deep-cloned on every `Graph::clone()` (in turn triggered by every
14/// `Context::clone()`). `Arc`-wrapping makes that clone O(1); mutators
15/// (`add_type`, `cache_subtype`) recover an owned value via
16/// `Arc::unwrap_or_clone`, which only actually copies when another live
17/// `Arc` still shares the allocation.
18#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
19#[serde(bound = "T: Serialize + for<'a> Deserialize<'a>")]
20pub struct Graph<T: TypeSystem> {
21    memory: Arc<HashSet<T>>,
22    root: Arc<Node<T>>,
23    #[serde(skip)]
24    subtype_cache: Arc<HashMap<(T, T), bool>>,
25}
26
27impl<T: TypeSystem> Default for Graph<T> {
28    fn default() -> Self {
29        Self::new()
30    }
31}
32
33impl<T: TypeSystem> Graph<T> {
34    pub fn new() -> Self {
35        Graph {
36            memory: Arc::new(HashSet::new()),
37            root: Arc::new(Node::new()),
38            subtype_cache: Arc::new(HashMap::new()),
39        }
40    }
41
42    /// Vérifie si le résultat de sous-typage est en cache
43    pub fn check_subtype_cache(&self, t1: &T, t2: &T) -> Option<bool> {
44        self.subtype_cache.get(&(t1.clone(), t2.clone())).copied()
45    }
46
47    /// Enregistre un résultat de sous-typage dans le cache
48    pub fn cache_subtype(self, t1: T, t2: T, result: bool) -> Self {
49        let mut subtype_cache = Arc::unwrap_or_clone(self.subtype_cache);
50        subtype_cache.insert((t1, t2), result);
51        Graph {
52            memory: self.memory,
53            root: self.root,
54            subtype_cache: Arc::new(subtype_cache),
55        }
56    }
57
58    pub fn add_type(self, typ: T, context: &Context) -> Self {
59        if self.memory.contains(&typ) {
60            self
61        } else {
62            let root = Arc::unwrap_or_clone(self.root);
63            let new_root = root.add_type(typ.clone(), context);
64            let mut new_memory = Arc::unwrap_or_clone(self.memory);
65            new_memory.insert(typ);
66            Graph {
67                memory: Arc::new(new_memory),
68                root: Arc::new(new_root),
69                subtype_cache: self.subtype_cache,
70            }
71        }
72    }
73
74    pub fn get_hierarchy(&self) -> String {
75        self.root.get_hierarchy()
76    }
77
78    /// Deterministic rendering of the graph for fingerprinting: only the
79    /// insertion-ordered node tree. `memory` (a `HashSet`) and the subtype
80    /// cache iterate in random order and must not reach a fingerprint.
81    pub fn structure_debug(&self) -> String {
82        format!("{:?}", self.root)
83    }
84
85    // Deduplicates while preserving the walk order: the result feeds R class
86    // vectors (`struct(c(...))` in types.R), where order drives S3 dispatch
87    // and must be stable from one build to the next.
88    pub fn get_supertypes(&self, typ: &T, context: &Context) -> Vec<T> {
89        self.get_ordered_supertypes(typ, context)
90    }
91
92    pub fn get_ordered_supertypes(&self, typ: &T, context: &Context) -> Vec<T> {
93        let raw = self.root.get_supertypes(typ, context);
94        let mut seen = HashSet::new();
95        let mut result = Vec::new();
96        for item in raw {
97            if seen.insert(item.clone()) {
98                result.push(item);
99            }
100        }
101        result
102    }
103
104    pub fn add_types(self, typs: &[T], context: &Context) -> Self {
105        typs.iter()
106            .cloned()
107            .fold(self, |acc, x| acc.add_type(x, context))
108    }
109}
110
111#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
112#[serde(bound = "T: Serialize + for<'a> Deserialize<'a>")]
113pub struct Node<T: TypeSystem> {
114    value: T,
115    subtypes: Vec<Node<T>>,
116}
117
118impl<T: TypeSystem> From<T> for Node<T> {
119    fn from(val: T) -> Self {
120        Node {
121            value: val,
122            subtypes: vec![],
123        }
124    }
125}
126
127impl<T: TypeSystem> Default for Node<T> {
128    fn default() -> Self {
129        Self::new()
130    }
131}
132
133impl<T: TypeSystem> Node<T> {
134    pub fn new() -> Self {
135        Node {
136            value: T::default(),
137            subtypes: vec![],
138        }
139    }
140
141    pub fn propagate(self, typ: T, context: &Context) -> Self {
142        let graph = Node {
143            value: self.value.clone(),
144            subtypes: self
145                .subtypes
146                .iter()
147                .cloned()
148                .map(|x| x.add_type(typ.clone(), context))
149                .collect(),
150        };
151        if graph == self {
152            self.add_subtype(typ)
153        } else {
154            graph
155        }
156    }
157
158    pub fn add_subtype(self, typ: T) -> Self {
159        Node {
160            value: self.value,
161            subtypes: self
162                .subtypes
163                .iter()
164                .chain([Node::from(typ)].iter())
165                .cloned()
166                .collect(),
167        }
168    }
169
170    pub fn set_subtypes(self, subtypes: Vec<Node<T>>) -> Self {
171        Node {
172            value: self.value,
173            subtypes,
174        }
175    }
176
177    fn switch_if_reverse_subtype(self, typ: T, context: &Context) -> Self {
178        if self.value.is_subtype_raw(&typ, context) {
179            Node {
180                value: typ,
181                subtypes: vec![Node::from(self.value).set_subtypes(self.subtypes)],
182            }
183        } else {
184            self
185        }
186    }
187
188    pub fn add_type(self, typ: T, context: &Context) -> Self {
189        if self.value == typ {
190            self
191        } else {
192            match (
193                typ.is_subtype_raw(&self.value, context),
194                self.subtypes.len(),
195            ) {
196                (true, 0) => self.add_subtype(typ),
197                (true, _) => self.propagate(typ, context),
198                _ => self.switch_if_reverse_subtype(typ, context),
199            }
200        }
201    }
202
203    pub fn get_supertypes(&self, target_type: &T, context: &Context) -> Vec<T> {
204        if target_type == &self.value {
205            vec![]
206        } else if target_type.is_subtype_raw(&self.value, context) {
207            self.subtypes
208                .iter()
209                .flat_map(|x| x.get_supertypes(target_type, context))
210                .chain([self.value.clone()].iter().cloned())
211                .collect::<Vec<T>>()
212        } else {
213            vec![]
214        }
215    }
216
217    pub fn get_hierarchy(&self) -> String {
218        self.get_hierarchy_helper(0)
219    }
220
221    fn tabulation_from_level(level: i32) -> String {
222        (0..level).map(|_| "  ").collect::<Vec<_>>().join("")
223    }
224
225    pub fn get_hierarchy_helper(&self, level: i32) -> String {
226        let tab = Node::<T>::tabulation_from_level(level);
227        let children = self
228            .subtypes
229            .iter()
230            .map(|x| x.get_hierarchy_helper(level + 1))
231            .collect::<Vec<_>>()
232            .join("\n");
233        tab + &self.value.pretty() + "\n" + &children
234    }
235}
236
237use std::fmt;
238impl<T: TypeSystem> fmt::Display for Node<T> {
239    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
240        write!(f, "{}", self.get_hierarchy())
241    }
242}
243
244impl<T: TypeSystem> Add for Graph<T> {
245    type Output = Self;
246
247    fn add(self, other: Self) -> Self {
248        let context = Context::default(); // Or apply a parameter if necessary
249        let merged = other
250            .memory
251            .iter()
252            .cloned()
253            .fold(self.clone(), |acc, typ| acc.add_type(typ, &context));
254        // Fusionner les caches de sous-typage
255        let mut new_cache = Arc::unwrap_or_clone(self.subtype_cache);
256        new_cache.extend(other.subtype_cache.iter().map(|(k, v)| (k.clone(), *v)));
257        Graph {
258            subtype_cache: Arc::new(new_cache),
259            ..merged
260        }
261    }
262}
typr_core/components/context/graph.rs

typr_core/components/context/
graph.rs
