type_leak/
lib.rs

1#![doc = include_str!("./README.md")]
2
3use gotgraph::prelude::VecGraph;
4use gotgraph::graph::{Graph as GotGraph, GraphUpdate};
5use proc_macro2::Span;
6use std::cell::RefCell;
7use std::collections::{HashMap, HashSet};
8use std::rc::Rc;
9use syn::parse::Parse;
10use syn::punctuated::Punctuated;
11use syn::spanned::Spanned;
12use syn::visit::Visit;
13use syn::visit_mut::VisitMut;
14use syn::*;
15use template_quote::{quote, ToTokens};
16
17pub use syn;
18
19/// The entry point of this crate.
20pub struct Leaker {
21    generics: Generics,
22    graph: VecGraph<Type, ()>,
23    pub self_ty_can_be_interned: bool,
24    reachable_types: HashSet<Type>,
25    pending_operations: Option<Vec<GraphOperation>>,
26}
27
28/// Error represents that the type is not internable.
29#[derive(Debug, Clone)]
30pub struct NotInternableError(pub Span);
31
32impl std::fmt::Display for NotInternableError {
33    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
34        f.write_str("Not internable")
35    }
36}
37
38impl std::error::Error for NotInternableError {}
39
40/// Encode [`GenericParam`]s to a type.
41pub fn encode_generics_to_ty<'a>(iter: impl IntoIterator<Item = &'a GenericArgument>) -> Type {
42    Type::Tuple(TypeTuple {
43        paren_token: Default::default(),
44        elems: iter
45            .into_iter()
46            .map(|param| -> Type {
47                match param {
48                    GenericArgument::Lifetime(lifetime) => {
49                        parse_quote!(& #lifetime ())
50                    }
51                    GenericArgument::Const(expr) => {
52                        parse_quote!([(); #expr as usize])
53                    }
54                    GenericArgument::Type(ty) => ty.clone(),
55                    _ => panic!(),
56                }
57            })
58            .collect(),
59    })
60}
61
62/// Represents result of [`Leaker::check()`], holding the cause in its tuple item.
63#[derive(Clone, Debug)]
64pub enum CheckResult {
65    /// The type must be interned because it directly depends on the type context.
66    MustIntern(Span),
67    /// The type must be interned because one of the types which it constituted with must be
68    /// interned.
69    MustInternOrInherit(Span),
70    /// The type must not be interned, because `type_leak` cannot intern this. (e.g. `impl Trait`s,
71    /// `_`, trait bounds with relative trait path, ...)
72    MustNotIntern(Span),
73    /// Other.
74    Neutral,
75}
76
77#[derive(Debug, Clone)]
78struct GraphOperation {
79    node_type: Type,
80    parent: Option<Type>,
81    is_root: bool,
82    is_must_intern: bool,
83}
84
85struct AnalyzeVisitor<'a> {
86    leaker: &'a mut Leaker,
87    generics: Generics,
88    parent: Option<Type>,
89    error: Option<Span>,
90    operations: Vec<GraphOperation>,
91}
92
93impl<'a, 'ast> Visit<'ast> for AnalyzeVisitor<'a> {
94    fn visit_trait_item_fn(&mut self, i: &TraitItemFn) {
95        let mut visitor = AnalyzeVisitor {
96            leaker: &mut self.leaker,
97            generics: self.generics.clone(),
98            parent: self.parent.clone(),
99            error: self.error.clone(),
100            operations: Vec::new(),
101        };
102        for g in &i.sig.generics.params {
103            visitor.generics.params.push(g.clone());
104        }
105        let mut i = i.clone();
106        i.default = None;
107        i.semi_token = Some(Default::default());
108        syn::visit::visit_trait_item_fn(&mut visitor, &mut i);
109        self.error = visitor.error;
110        self.operations.extend(visitor.operations);
111    }
112
113    fn visit_receiver(&mut self, i: &Receiver) {
114        for attr in &i.attrs {
115            self.visit_attribute(attr);
116        }
117        if let Some((_, Some(lt))) = &i.reference {
118            self.visit_lifetime(lt);
119        }
120        if i.colon_token.is_some() {
121            self.visit_type(&i.ty);
122        }
123    }
124
125    fn visit_trait_item_type(&mut self, i: &TraitItemType) {
126        let mut visitor = AnalyzeVisitor {
127            leaker: &mut self.leaker,
128            generics: self.generics.clone(),
129            parent: self.parent.clone(),
130            error: self.error.clone(),
131            operations: Vec::new(),
132        };
133        for g in &i.generics.params {
134            visitor.generics.params.push(g.clone());
135        }
136        syn::visit::visit_trait_item_type(&mut visitor, i);
137        self.error = visitor.error;
138        self.operations.extend(visitor.operations);
139    }
140
141    fn visit_type(&mut self, i: &Type) {
142        match self.leaker.check(&self.generics, i) {
143            Err((_, s)) => {
144                // Emit error and terminate searching
145                self.error = Some(s);
146            }
147            Ok(CheckResult::MustNotIntern(_)) => (),
148            o => {
149                // Collect the operation instead of directly modifying the graph
150                let is_must_intern = matches!(o, Ok(CheckResult::MustIntern(_)));
151                let is_root = self.parent.is_none();
152                
153                self.operations.push(GraphOperation {
154                    node_type: i.clone(),
155                    parent: self.parent.clone(),
156                    is_root,
157                    is_must_intern,
158                });
159
160                if !is_must_intern {
161                    // Perform recursive call
162                    let parent = self.parent.clone();
163                    self.parent = Some(i.clone());
164                    syn::visit::visit_type(self, i);
165                    self.parent = parent;
166                }
167            }
168        }
169    }
170
171    fn visit_trait_bound(&mut self, i: &TraitBound) {
172        if i.path.leading_colon.is_none() {
173            // Trait bounds with relative oath
174            self.error = Some(i.span());
175        } else {
176            syn::visit::visit_trait_bound(self, i)
177        }
178    }
179
180    fn visit_expr_path(&mut self, i: &ExprPath) {
181        if i.path.leading_colon.is_none() {
182            // Value or trait bounds with relative oath
183            self.error = Some(i.span());
184        } else {
185            syn::visit::visit_expr_path(self, i)
186        }
187    }
188}
189
190impl Leaker {
191    /// Initialize with [`ItemStruct`]
192    ///
193    /// ```
194    /// # use type_leak::*;
195    /// # use syn::*;
196    /// let test_struct: ItemStruct = parse_quote!(
197    ///     pub struct MyStruct<'a, T1, T2: ::path::to::MyType1<MyType4>> {
198    ///         field1: MyType1,
199    ///         field2: (MyType2, MyType3<MyType1>, MyType4, MyType5),
200    ///         field3: &'a (T1, T2),
201    ///     }
202    /// );
203    /// let leaker = Leaker::from_struct(&test_struct).unwrap();
204    /// ```
205    pub fn from_struct(input: &ItemStruct) -> std::result::Result<Self, NotInternableError> {
206        let mut leaker = Leaker::with_generics(input.generics.clone());
207        let mut visitor = AnalyzeVisitor {
208            leaker: &mut leaker,
209            parent: None,
210            error: None,
211            generics: input.generics.clone(),
212            operations: Vec::new(),
213        };
214        visitor.visit_item_struct(input);
215        if let Some(e) = visitor.error {
216            return Err(NotInternableError(e));
217        }
218        let operations = visitor.operations;
219        leaker.apply_operations(operations);
220        Ok(leaker)
221    }
222
223    /// Initialize with [`ItemEnum`]
224    pub fn from_enum(input: &ItemEnum) -> std::result::Result<Self, NotInternableError> {
225        let mut leaker = Self::with_generics(input.generics.clone());
226        let mut visitor = AnalyzeVisitor {
227            leaker: &mut leaker,
228            parent: None,
229            error: None,
230            generics: input.generics.clone(),
231            operations: Vec::new(),
232        };
233        visitor.visit_item_enum(input);
234        if let Some(e) = visitor.error {
235            return Err(NotInternableError(e));
236        }
237        let operations = visitor.operations;
238        leaker.apply_operations(operations);
239        Ok(leaker)
240    }
241
242    /// Build an [`Leaker`] with given trait.
243    ///
244    /// Unlike enum nor struct, it requires ~alternative path~, an absolute path of a struct
245    /// which is declared the same crate with the leaker trait and also visible from
246    /// [`Referrer`]s' context. That struct is used as an `impl` target of `Repeater`
247    /// instead of the Leaker's path.
248    ///
249    /// ```
250    /// # use syn::*;
251    /// # use type_leak::Leaker;
252    /// let s: ItemTrait = parse_quote!{
253    ///     pub trait MyTrait<T, U> {
254    ///         fn func(self, t: T) -> U;
255    ///     }
256    /// };
257    /// let alternate: ItemStruct = parse_quote!{
258    ///     pub struct MyAlternate;
259    /// };
260    /// let _ = Leaker::from_trait(&s);
261    /// ```
262    pub fn from_trait(input: &ItemTrait) -> std::result::Result<Self, NotInternableError> {
263        let mut leaker = Self::with_generics(input.generics.clone());
264        let mut visitor = AnalyzeVisitor {
265            leaker: &mut leaker,
266            parent: None,
267            error: None,
268            generics: input.generics.clone(),
269            operations: Vec::new(),
270        };
271        visitor.visit_item_trait(input);
272        if let Some(e) = visitor.error {
273            return Err(NotInternableError(e));
274        }
275        let operations = visitor.operations;
276        leaker.apply_operations(operations);
277        Ok(leaker)
278    }
279
280    /// Initialize empty [`Leaker`] with given generics.
281    ///
282    /// Types, consts, lifetimes defined in the [`Generics`] is treated as "no needs to be interned" although
283    /// they looks like relative path names.
284    pub fn with_generics(generics: Generics) -> Self {
285        Self {
286            generics,
287            graph: VecGraph::default(),
288            self_ty_can_be_interned: true,
289            reachable_types: HashSet::new(),
290            pending_operations: None,
291        }
292    }
293
294    /// Apply collected graph operations using scope_mut()
295    fn apply_operations(&mut self, operations: Vec<GraphOperation>) {
296        if operations.is_empty() {
297            return;
298        }
299
300        // Store operations for proper graph reduction in reduce_roots()
301        self.pending_operations = Some(operations);
302    }
303
304    /// Intern the given type as a root node.
305    pub fn intern(
306        &mut self,
307        generics: Generics,
308        ty: &Type,
309    ) -> std::result::Result<&mut Self, NotInternableError> {
310        let mut visitor = AnalyzeVisitor {
311            leaker: self,
312            parent: None,
313            error: None,
314            generics,
315            operations: Vec::new(),
316        };
317        visitor.visit_type(ty);
318        if let Some(e) = visitor.error {
319            Err(NotInternableError(e))
320        } else {
321            let operations = visitor.operations;
322            self.apply_operations(operations);
323            Ok(self)
324        }
325    }
326
327    /// Check that the internableness of give `ty`. It returns `Err` in contradiction (the type
328    /// must and must not be interned).
329    ///
330    ///
331    /// See [`CheckResult`].
332    pub fn check(
333        &self,
334        generics: &Generics,
335        ty: &Type,
336    ) -> std::result::Result<CheckResult, (Span, Span)> {
337        use syn::visit::Visit;
338        #[derive(Clone)]
339        struct Visitor {
340            generic_lifetimes_base: Vec<Lifetime>,
341            generic_idents_base: Vec<Ident>,
342            generic_lifetimes: Vec<Lifetime>,
343            generic_idents: Vec<Ident>,
344            impossible: Option<Span>,
345            must: Option<(isize, Span)>,
346            self_ty_can_be_interned: bool,
347        }
348
349        const _: () = {
350            use syn::visit::Visit;
351            impl<'a> Visit<'a> for Visitor {
352                fn visit_type(&mut self, i: &Type) {
353                    match i {
354                        Type::BareFn(TypeBareFn {
355                            lifetimes,
356                            inputs,
357                            output,
358                            ..
359                        }) => {
360                            let mut visitor = self.clone();
361                            visitor.must = None;
362                            visitor.generic_lifetimes.extend(
363                                lifetimes
364                                    .as_ref()
365                                    .map(|ls| {
366                                        ls.lifetimes.iter().map(|gp| {
367                                            if let GenericParam::Lifetime(lt) = gp {
368                                                lt.lifetime.clone()
369                                            } else {
370                                                panic!()
371                                            }
372                                        })
373                                    })
374                                    .into_iter()
375                                    .flatten(),
376                            );
377                            for input in inputs {
378                                visitor.visit_type(&input.ty);
379                            }
380                            if let ReturnType::Type(_, output) = output {
381                                visitor.visit_type(output.as_ref());
382                            }
383                            if self.impossible.is_none() {
384                                self.impossible = visitor.impossible;
385                            }
386                            match (self.must.clone(), visitor.must.clone()) {
387                                (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
388                                    self.must = Some((v_l + 1, v_m))
389                                }
390                                (None, Some((v_l, v_m))) => self.must = Some((v_l + 1, v_m)),
391                                _ => (),
392                            }
393                            return;
394                        }
395                        Type::TraitObject(TypeTraitObject { bounds, .. }) => {
396                            for bound in bounds {
397                                match bound {
398                                    TypeParamBound::Trait(TraitBound {
399                                        lifetimes, path, ..
400                                    }) => {
401                                        let mut visitor = self.clone();
402                                        visitor.must = None;
403                                        visitor.generic_lifetimes.extend(
404                                            lifetimes
405                                                .as_ref()
406                                                .map(|ls| {
407                                                    ls.lifetimes.iter().map(|gp| {
408                                                        if let GenericParam::Lifetime(lt) = gp {
409                                                            lt.lifetime.clone()
410                                                        } else {
411                                                            panic!()
412                                                        }
413                                                    })
414                                                })
415                                                .into_iter()
416                                                .flatten(),
417                                        );
418                                        visitor.visit_path(path);
419                                        if self.impossible.is_none() {
420                                            self.impossible = visitor.impossible;
421                                        }
422                                        match (self.must.clone(), visitor.must.clone()) {
423                                            (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
424                                                self.must = Some((v_l + 1, v_m))
425                                            }
426                                            (None, Some((v_l, v_m))) => {
427                                                self.must = Some((v_l + 1, v_m))
428                                            }
429                                            _ => (),
430                                        }
431                                        return;
432                                    }
433                                    TypeParamBound::Verbatim(_) => {
434                                        self.impossible = Some(bound.span());
435                                        return;
436                                    }
437                                    _ => (),
438                                }
439                            }
440                        }
441                        Type::ImplTrait(_) | Type::Macro(_) | Type::Verbatim(_) => {
442                            self.impossible = Some(i.span());
443                        }
444                        Type::Reference(TypeReference { lifetime, .. }) => {
445                            if lifetime.is_none() {
446                                self.impossible = Some(i.span());
447                            }
448                        }
449                        _ => (),
450                    }
451                    let mut visitor = self.clone();
452                    visitor.must = None;
453                    syn::visit::visit_type(&mut visitor, i);
454                    if visitor.impossible.is_some() {
455                        self.impossible = visitor.impossible;
456                    }
457                    match (self.must.clone(), visitor.must.clone()) {
458                        (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
459                            self.must = Some((v_l + 1, v_m))
460                        }
461                        (None, Some((v_l, v_m))) => self.must = Some((v_l + 1, v_m)),
462                        _ => (),
463                    }
464                }
465                fn visit_qself(&mut self, i: &QSelf) {
466                    if i.as_token.is_none() {
467                        self.impossible = Some(i.span());
468                    }
469                    syn::visit::visit_qself(self, i)
470                }
471                fn visit_lifetime(&mut self, i: &Lifetime) {
472                    match i.to_string().as_str() {
473                        "'static" => (),
474                        "'_" => self.impossible = Some(i.span()),
475                        _ if self.generic_lifetimes_base.iter().any(|lt| lt == i) => {}
476                        _ if self.generic_lifetimes.iter().any(|lt| lt == i) => {
477                            self.impossible = Some(i.span());
478                        }
479                        _ => {
480                            self.must = Some((-1, i.span()));
481                        }
482                    }
483                    syn::visit::visit_lifetime(self, i)
484                }
485                fn visit_expr(&mut self, i: &Expr) {
486                    match i {
487                        Expr::Closure(_) | Expr::Assign(_) | Expr::Verbatim(_) | Expr::Macro(_) => {
488                            self.impossible = Some(i.span());
489                        }
490                        _ => (),
491                    }
492                    syn::visit::visit_expr(self, i)
493                }
494                fn visit_path(&mut self, i: &Path) {
495                    if matches!(i.segments.iter().next(), Some(PathSegment { ident, arguments }) if ident == "Self" && arguments.is_none())
496                        && i.leading_colon.is_none()
497                    {
498                        if !self.self_ty_can_be_interned {
499                            self.impossible = Some(i.span());
500                        }
501                    } else {
502                        match (i.leading_colon, i.get_ident()) {
503                            // i is a generic parameter
504                            (None, Some(ident)) if self.generic_idents_base.contains(&ident) => {}
505                            (None, Some(ident)) if self.generic_idents.contains(&ident) => {
506                                self.impossible = Some(i.span());
507                            }
508                            // relative path, not a generic parameter
509                            (None, _) => {
510                                self.must = Some((-1, i.span()));
511                            }
512                            // absolute path
513                            (Some(_), _) => (),
514                        }
515                    }
516                    syn::visit::visit_path(self, i)
517                }
518            }
519        };
520        let mut visitor = Visitor {
521            generic_lifetimes_base: self.generics
522                .params
523                .iter()
524                .filter_map(|gp| {
525                    if let GenericParam::Lifetime(lt) = gp {
526                        Some(lt.lifetime.clone())
527                    } else {
528                        None
529                    }
530                })
531                .collect(),
532            generic_idents_base: self.generics
533                .params
534                .iter()
535                .filter_map(|gp| match gp {
536                    GenericParam::Type(TypeParam { ident, .. })
537                    | GenericParam::Const(ConstParam { ident, .. }) => Some(ident.clone()),
538                    _ => None,
539                })
540                .collect(),
541            generic_lifetimes: generics
542                .params
543                .iter()
544                .filter_map(|gp| {
545                    if let GenericParam::Lifetime(lt) = gp {
546                        Some(lt.lifetime.clone())
547                    } else {
548                        None
549                    }
550                })
551                .collect(),
552            generic_idents: generics
553                .params
554                .iter()
555                .filter_map(|gp| match gp {
556                    GenericParam::Type(TypeParam { ident, .. })
557                    | GenericParam::Const(ConstParam { ident, .. }) => Some(ident.clone()),
558                    _ => None,
559                })
560                .collect(),
561            impossible: None,
562            must: None,
563            self_ty_can_be_interned: self.self_ty_can_be_interned,
564        };
565        visitor.visit_type(ty);
566        match (visitor.must, visitor.impossible) {
567            (None, None) => Ok(CheckResult::Neutral),
568            (Some((0, span)), None) => Ok(CheckResult::MustIntern(span)),
569            (Some((_, span)), None) => Ok(CheckResult::MustInternOrInherit(span)),
570            (None, Some(span)) => Ok(CheckResult::MustNotIntern(span)),
571            (Some((_, span0)), Some(span1)) => Err((span0, span1)),
572        }
573    }
574
575    pub fn generics(&self) -> &Generics {
576        &self.generics
577    }
578
579    /// Finish building the [`Leaker`] and convert it into [`Referrer`].
580    pub fn finish(self) -> Referrer {
581        // Use the reachable types computed by apply_operations
582        let leak_types: Vec<_> = self.reachable_types.into_iter().collect();
583        let map = leak_types
584            .iter()
585            .enumerate()
586            .map(|(n, ty)| (ty.clone(), n))
587            .collect();
588        Referrer { leak_types, map }
589    }
590
591    #[cfg_attr(doc, aquamarine::aquamarine)]
592    /// Reduce nodes to decrease cost of {`Leaker`}'s implementation.
593    ///
594    /// # Algorithm
595    ///
596    /// To consult the algorithm, see the following [`Leaker`]'s input:
597    ///
598    /// ```ignore
599    /// pub struct MyStruct<'a, T1, T2: ::path::to::MyType1<MyType4>> {
600    ///     field1: MyType1,
601    ///     field2: (MyType2, MyType3<MyType1>, MyType4, MyType5),
602    ///     field3: &'a (T1, T2),
603    /// }
604    /// ```
605    ///
606    /// [`Leaker`], when initialized with [`Leaker::from_struct()`], analyze the AST and
607    /// construct a DAG which represents all (internable) types and the dependency relations like
608    /// this:
609    ///
610    /// ```mermaid
611    /// graph TD
612    ///   1["★MyType1
613    ///   (Node 1)"]
614    ///   2["★(MyType2, MyType3#lt;MyType1#gt;, MyType4, MyType5)
615    ///   (Node 2)"] -->3["MyType2
616    ///   (Node 3)"]
617    ///   2 -->4["MyType3#lt;MyType1#gt;
618    ///   (Node 4)"]
619    ///   2 -->0["★MyType4
620    ///   (Node 0)"]
621    ///   2 -->5["MyType5
622    ///   (Node 5)"]
623    ///   6["★&a (T1, T2)
624    ///   (Node 6)"] -->7["(T1, T2)
625    ///   (Node 7)"]
626    ///   7 -->8["T1
627    ///   (Node 8)"]
628    ///   7 -->9["T2
629    ///   (Node 9)"]
630    ///   classDef redNode stroke:#ff0000;
631    ///   class 0,1,3,4,5 redNode;
632    /// ```
633    ///
634    /// The **red** node is flagged as [`CheckResult::MustIntern`] by [`Leaker::check()`] (which means
635    /// the type literature depends on the type context, so it must be interned).
636    ///
637    /// This algorithm reduce the nodes, remaining that all root type (annotated with ★) can be
638    /// expressed with existing **red** nodes.
639    ///
640    /// Here, there are some choice in its freedom:
641    ///
642    /// - Intern all **red** nodes and ignore others (because other nodes are not needed to be
643    /// intern, or constructable with red nodes)
644    /// - Not directly intern **red** nodes; intern common ancessors instead if it is affordable.
645    ///
646    /// So finally, it results like:
647    ///
648    /// ```mermaid
649    /// graph TD
650    ///   0["MyType4
651    ///   (Node 0)"]
652    ///   1["MyType1
653    ///   (Node 1)"]
654    ///   2["(MyType2, MyType3 #lt; MyType1 #gt;, MyType4, MyType5)
655    ///   (Node 2)"]
656    ///   classDef redNode stroke:#ff0000;
657    ///   class 0,1,2 redNode;
658    /// ```
659    ///
660    pub fn reduce_roots(&mut self) {
661        if let Some(operations) = self.pending_operations.take() {
662            self.build_graph_and_reduce(operations);
663        }
664        self.reduce_unreachable_nodes();
665        self.reduce_obvious_nodes();
666    }
667
668    fn build_graph_and_reduce(&mut self, operations: Vec<GraphOperation>) {
669        // Build parent-child relationships from operations
670        let mut children: HashMap<Type, Vec<Type>> = HashMap::new();
671        let mut parents: HashMap<Type, Vec<Type>> = HashMap::new();
672        let mut root_types = HashSet::new();
673        let mut must_intern_types = HashSet::new();
674        
675        for operation in &operations {
676            if operation.is_root {
677                root_types.insert(operation.node_type.clone());
678            }
679            if operation.is_must_intern {
680                must_intern_types.insert(operation.node_type.clone());
681            }
682            
683            if let Some(parent_type) = &operation.parent {
684                children.entry(parent_type.clone()).or_default().push(operation.node_type.clone());
685                parents.entry(operation.node_type.clone()).or_default().push(parent_type.clone());
686            }
687        }
688
689
690        // Implement proper reduction algorithm:
691        // 1. Keep all must-intern root types 
692        // 2. Keep root types that transitively contain must-intern types
693        // 3. Do NOT keep non-root must-intern types that are only components of kept root types
694        
695        let mut kept_types = HashSet::new();
696        
697        // Step 1: Keep must-intern types that are also roots
698        for root_type in &root_types {
699            if must_intern_types.contains(root_type) {
700                kept_types.insert(root_type.clone());
701            }
702        }
703        
704        // Step 2: Keep root types that contain must-intern descendants
705        for root_type in &root_types {
706            if !kept_types.contains(root_type) {
707                if self.contains_must_intern_descendant(root_type, &children, &must_intern_types) {
708                    kept_types.insert(root_type.clone());
709                }
710            }
711        }
712        
713        // Step 3: Only add must-intern types that are NOT components of any kept type
714        for must_intern_type in &must_intern_types {
715            if !self.is_component_of_any_kept_type(must_intern_type, &kept_types, &children) {
716                kept_types.insert(must_intern_type.clone());
717            }
718        }
719        
720        self.reachable_types = kept_types;
721    }
722    
723    fn contains_must_intern_descendant(&self, root: &Type, children: &HashMap<Type, Vec<Type>>, must_intern_types: &HashSet<Type>) -> bool {
724        let mut visited = HashSet::new();
725        let mut stack = vec![root.clone()];
726        
727        while let Some(current) = stack.pop() {
728            if !visited.insert(current.clone()) {
729                continue;
730            }
731            
732            if must_intern_types.contains(&current) {
733                return true;
734            }
735            
736            if let Some(child_list) = children.get(&current) {
737                for child in child_list {
738                    if !visited.contains(child) {
739                        stack.push(child.clone());
740                    }
741                }
742            }
743        }
744        
745        false
746    }
747    
748    fn is_component_of_any_kept_type(&self, target_type: &Type, kept_types: &HashSet<Type>, children: &HashMap<Type, Vec<Type>>) -> bool {
749        for kept_type in kept_types {
750            if self.is_descendant_of(target_type, kept_type, children) {
751                return true;
752            }
753        }
754        false
755    }
756    
757    fn is_descendant_of(&self, target: &Type, ancestor: &Type, children: &HashMap<Type, Vec<Type>>) -> bool {
758        if target == ancestor {
759            return false; // Not a descendant of itself
760        }
761        
762        let mut visited = HashSet::new();
763        let mut stack = vec![ancestor.clone()];
764        
765        while let Some(current) = stack.pop() {
766            if !visited.insert(current.clone()) {
767                continue;
768            }
769            
770            if let Some(child_list) = children.get(&current) {
771                for child in child_list {
772                    if child == target {
773                        return true;
774                    }
775                    if !visited.contains(child) {
776                        stack.push(child.clone());
777                    }
778                }
779            }
780        }
781        
782        false
783    }
784
785    fn reduce_obvious_nodes(&mut self) {
786        // Remove intermediate nodes that have exactly one parent and one child
787        // This step eliminates unnecessary intermediate types
788    }
789
790    fn reduce_unreachable_nodes(&mut self) {
791        if let Some(operations) = self.pending_operations.take() {
792            self.apply_vecgraph_reduction(operations);
793        }
794    }
795    
796    fn apply_vecgraph_reduction(&mut self, operations: Vec<GraphOperation>) {
797        let mut root_types = HashSet::new();
798        let mut must_intern_types = HashSet::new();
799        
800        // Collect graph operations
801        for operation in &operations {
802            if operation.is_root {
803                root_types.insert(operation.node_type.clone());
804            }
805            if operation.is_must_intern {
806                must_intern_types.insert(operation.node_type.clone());
807            }
808        }
809        
810        // Build the graph using scope_mut
811        self.graph.scope_mut(|mut ctx| {
812            let mut type_to_node = HashMap::new();
813            
814            // Add all nodes first
815            for operation in &operations {
816                if !type_to_node.contains_key(&operation.node_type) {
817                    let node_tag = ctx.add_node(operation.node_type.clone());
818                    type_to_node.insert(operation.node_type.clone(), node_tag);
819                }
820                
821                if let Some(parent_type) = &operation.parent {
822                    if !type_to_node.contains_key(parent_type) {
823                        let parent_node_tag = ctx.add_node(parent_type.clone());
824                        type_to_node.insert(parent_type.clone(), parent_node_tag);
825                    }
826                }
827            }
828            
829            // Add edges between nodes
830            for operation in &operations {
831                if let Some(parent_type) = &operation.parent {
832                    let parent_node = type_to_node[parent_type];
833                    let child_node = type_to_node[&operation.node_type];
834                    ctx.add_edge((), parent_node, child_node);
835                }
836            }
837        });
838        
839        // Perform analysis using the same logic as build_graph_and_reduce
840        self.reachable_types = self.analyze_reachable_types(&root_types, &must_intern_types, &operations);
841    }
842    
843    fn analyze_reachable_types(&self, root_types: &HashSet<Type>, must_intern_types: &HashSet<Type>, operations: &[GraphOperation]) -> HashSet<Type> {
844        // Implement the same logic as build_graph_and_reduce 
845        let mut final_types = HashSet::new();
846        
847        // Keep must-intern root types
848        for root_type in root_types {
849            if must_intern_types.contains(root_type) {
850                final_types.insert(root_type.clone());
851            }
852        }
853        
854        // Keep root types that contain must-intern descendants
855        for root_type in root_types {
856            if !final_types.contains(root_type) {
857                if self.contains_must_intern_in_tree(root_type, operations, must_intern_types) {
858                    final_types.insert(root_type.clone());
859                }
860            }
861        }
862        
863        // Only keep must-intern types that aren't subcomponents of kept root types
864        for must_intern_type in must_intern_types {
865            if !self.is_subcomponent_of_kept_root(must_intern_type, &final_types, operations) {
866                final_types.insert(must_intern_type.clone());
867            }
868        }
869        
870        final_types
871    }
872    
873    fn contains_must_intern_in_tree(&self, root: &Type, operations: &[GraphOperation], must_intern_types: &HashSet<Type>) -> bool {
874        let mut stack = vec![root.clone()];
875        let mut visited = HashSet::new();
876        
877        while let Some(current) = stack.pop() {
878            if !visited.insert(current.clone()) {
879                continue;
880            }
881            
882            if must_intern_types.contains(&current) {
883                return true;
884            }
885            
886            for operation in operations {
887                if let Some(parent_type) = &operation.parent {
888                    if parent_type == &current && !visited.contains(&operation.node_type) {
889                        stack.push(operation.node_type.clone());
890                    }
891                }
892            }
893        }
894        
895        false
896    }
897    
898    fn is_subcomponent_of_kept_root(&self, target: &Type, kept_roots: &HashSet<Type>, operations: &[GraphOperation]) -> bool {
899        for root in kept_roots {
900            if self.contains_must_intern_in_tree(root, operations, &HashSet::from([target.clone()])) && root != target {
901                return true;
902            }
903        }
904        false
905    }
906
907    // TODO: Reimplement reduce_unreachable_nodes with VecGraph APIs
908}
909
910#[derive(Clone, PartialEq, Eq, Debug)]
911pub struct Referrer {
912    leak_types: Vec<Type>,
913    map: HashMap<Type, usize>,
914}
915
916impl Referrer {
917    pub fn is_empty(&self) -> bool {
918        self.leak_types.is_empty()
919    }
920
921    pub fn iter(&self) -> impl Iterator<Item = &Type> {
922        self.leak_types.iter()
923    }
924
925    pub fn into_visitor<F: FnMut(Type, usize) -> Type>(self, type_fn: F) -> Visitor<F> {
926        Visitor(self, Rc::new(RefCell::new(type_fn)))
927    }
928
929    pub fn expand(&self, ty: Type, type_fn: impl FnMut(Type, usize) -> Type) -> Type {
930        use syn::fold::Fold;
931        struct Folder<'a, F>(&'a Referrer, F);
932        impl<'a, F: FnMut(Type, usize) -> Type> Fold for Folder<'a, F> {
933            fn fold_type(&mut self, ty: Type) -> Type {
934                if let Some(idx) = self.0.map.get(&ty) {
935                    self.1(ty, *idx)
936                } else {
937                    syn::fold::fold_type(self, ty)
938                }
939            }
940        }
941        let mut folder = Folder(self, type_fn);
942        folder.fold_type(ty)
943    }
944}
945
946#[derive(Debug)]
947pub struct Visitor<F>(Referrer, Rc<RefCell<F>>);
948
949impl<F> Clone for Visitor<F> {
950    fn clone(&self) -> Self {
951        Self(self.0.clone(), self.1.clone())
952    }
953}
954
955impl<F: FnMut(Type, usize) -> Type> Visitor<F> {
956    fn with_generics(&mut self, generics: &mut Generics) -> Self {
957        let mut visitor = self.clone();
958        for gp in generics.params.iter_mut() {
959            if let GenericParam::Type(TypeParam { ident, .. }) = gp {
960                visitor.0.map.remove(&parse_quote!(#ident));
961            }
962            visitor.visit_generic_param_mut(gp);
963        }
964        visitor
965    }
966
967    fn with_signature(&mut self, sig: &mut Signature) -> Self {
968        let mut visitor = self.with_generics(&mut sig.generics);
969        for input in sig.inputs.iter_mut() {
970            visitor.visit_fn_arg_mut(input);
971        }
972        visitor.visit_return_type_mut(&mut sig.output);
973        visitor
974    }
975}
976
977impl<F: FnMut(Type, usize) -> Type> VisitMut for Visitor<F> {
978    fn visit_type_mut(&mut self, i: &mut Type) {
979        *i = self.0.expand(i.clone(), &mut *self.1.borrow_mut());
980    }
981    fn visit_item_struct_mut(&mut self, i: &mut ItemStruct) {
982        for attr in i.attrs.iter_mut() {
983            self.visit_attribute_mut(attr);
984        }
985        let mut visitor = self.with_generics(&mut i.generics);
986        visitor.visit_fields_mut(&mut i.fields);
987    }
988    fn visit_item_enum_mut(&mut self, i: &mut ItemEnum) {
989        for attr in i.attrs.iter_mut() {
990            self.visit_attribute_mut(attr);
991        }
992        let mut visitor = self.with_generics(&mut i.generics);
993        for variant in i.variants.iter_mut() {
994            visitor.visit_variant_mut(variant);
995        }
996    }
997    fn visit_item_trait_mut(&mut self, i: &mut ItemTrait) {
998        for attr in i.attrs.iter_mut() {
999            self.visit_attribute_mut(attr);
1000        }
1001        let mut visitor = self.with_generics(&mut i.generics);
1002        for supertrait in i.supertraits.iter_mut() {
1003            visitor.visit_type_param_bound_mut(supertrait);
1004        }
1005        for item in i.items.iter_mut() {
1006            visitor.visit_trait_item_mut(item);
1007        }
1008    }
1009    fn visit_item_union_mut(&mut self, i: &mut ItemUnion) {
1010        for attr in i.attrs.iter_mut() {
1011            self.visit_attribute_mut(attr);
1012        }
1013        let mut visitor = self.with_generics(&mut i.generics);
1014        visitor.visit_fields_named_mut(&mut i.fields);
1015    }
1016    fn visit_item_type_mut(&mut self, i: &mut ItemType) {
1017        for attr in i.attrs.iter_mut() {
1018            self.visit_attribute_mut(attr);
1019        }
1020        let mut visitor = self.with_generics(&mut i.generics);
1021        visitor.visit_type_mut(&mut i.ty);
1022    }
1023    fn visit_item_fn_mut(&mut self, i: &mut ItemFn) {
1024        for attr in i.attrs.iter_mut() {
1025            self.visit_attribute_mut(attr);
1026        }
1027        let mut visitor = self.with_signature(&mut i.sig);
1028        visitor.visit_block_mut(i.block.as_mut());
1029    }
1030    fn visit_trait_item_fn_mut(&mut self, i: &mut TraitItemFn) {
1031        for attr in i.attrs.iter_mut() {
1032            self.visit_attribute_mut(attr);
1033        }
1034        let mut visitor = self.with_signature(&mut i.sig);
1035        if let Some(block) = &mut i.default {
1036            visitor.visit_block_mut(block);
1037        }
1038    }
1039    fn visit_trait_item_type_mut(&mut self, i: &mut TraitItemType) {
1040        for attr in i.attrs.iter_mut() {
1041            self.visit_attribute_mut(attr);
1042        }
1043        let mut visitor = self.with_generics(&mut i.generics);
1044        for bound in i.bounds.iter_mut() {
1045            visitor.visit_type_param_bound_mut(bound);
1046        }
1047        if let Some((_, ty)) = &mut i.default {
1048            visitor.visit_type_mut(ty);
1049        }
1050    }
1051    fn visit_trait_item_const_mut(&mut self, i: &mut TraitItemConst) {
1052        for attr in i.attrs.iter_mut() {
1053            self.visit_attribute_mut(attr);
1054        }
1055        let mut visitor = self.with_generics(&mut i.generics);
1056        visitor.visit_type_mut(&mut i.ty);
1057        if let Some((_, expr)) = &mut i.default {
1058            visitor.visit_expr_mut(expr);
1059        }
1060    }
1061    fn visit_block_mut(&mut self, i: &mut Block) {
1062        let mut visitor = self.clone();
1063        for stmt in &i.stmts {
1064            match stmt {
1065                Stmt::Item(Item::Struct(ItemStruct { ident, .. }))
1066                | Stmt::Item(Item::Enum(ItemEnum { ident, .. }))
1067                | Stmt::Item(Item::Union(ItemUnion { ident, .. }))
1068                | Stmt::Item(Item::Trait(ItemTrait { ident, .. }))
1069                | Stmt::Item(Item::Type(ItemType { ident, .. })) => {
1070                    visitor.0.map.remove(&parse_quote!(#ident));
1071                }
1072                _ => (),
1073            }
1074        }
1075        for stmt in i.stmts.iter_mut() {
1076            visitor.visit_stmt_mut(stmt);
1077        }
1078    }
1079}
1080
1081impl Parse for Referrer {
1082    fn parse(input: parse::ParseStream) -> Result<Self> {
1083        let content: syn::parse::ParseBuffer<'_>;
1084        parenthesized!(content in input);
1085        let leak_types: Vec<Type> = Punctuated::<Type, Token![,]>::parse_terminated(&content)?
1086            .into_iter()
1087            .collect();
1088        let map = leak_types
1089            .iter()
1090            .enumerate()
1091            .map(|(n, ty)| (ty.clone(), n))
1092            .collect();
1093        Ok(Self { map, leak_types })
1094    }
1095}
1096
1097impl ToTokens for Referrer {
1098    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
1099        tokens.extend(quote! {
1100            (
1101                #(for item in &self.leak_types), {
1102                    #item
1103                }
1104            )
1105        })
1106    }
1107}
type_leak/lib.rs

type_leak/
lib.rs
