type_leak/
lib.rs

1#![doc = include_str!("./README.md")]
2
3use petgraph::graph::{DefaultIx, NodeIndex};
4use petgraph::visit::EdgeRef;
5use petgraph::Graph;
6use proc_macro2::Span;
7use std::collections::{HashMap, HashSet};
8use syn::parse::Parse;
9use syn::spanned::Spanned;
10use syn::visit::Visit;
11use syn::visit_mut::VisitMut;
12use syn::*;
13use template_quote::{quote, ToTokens};
14
15pub use syn;
16
17/// The entry point of this crate.
18pub struct Leaker {
19    /// Referred by [`Leaker::finish()`]
20    generics: Generics,
21    graph: Graph<Type, ()>,
22    map: HashMap<Type, NodeIndex<DefaultIx>>,
23    must_intern_nodes: HashSet<NodeIndex<DefaultIx>>,
24    root_nodes: HashSet<NodeIndex<DefaultIx>>,
25    /// Marker path. It defaults to the type name when the input is enum or struct. When the input
26    /// is a trait, the marker path should refers a type called marker type.
27    ///
28    /// Referred by [`Leaker::finish()`].
29    pub implementor_type_fn: Box<dyn Fn(PathArguments) -> Type>,
30}
31
32/// Error represents that the type is not internable.
33#[derive(Debug, Clone)]
34pub struct NotInternableError(pub Span);
35
36impl std::fmt::Display for NotInternableError {
37    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
38        f.write_str("Not internable")
39    }
40}
41
42impl std::error::Error for NotInternableError {}
43
44/// Encode [`GenericParam`]s to a type.
45pub fn encode_generics_to_ty<'a>(iter: impl IntoIterator<Item = &'a GenericArgument>) -> Type {
46    Type::Tuple(TypeTuple {
47        paren_token: Default::default(),
48        elems: iter
49            .into_iter()
50            .map(|param| -> Type {
51                match param {
52                    GenericArgument::Lifetime(lifetime) => {
53                        parse_quote!(& #lifetime ())
54                    }
55                    GenericArgument::Const(expr) => {
56                        parse_quote!([(); #expr as usize])
57                    }
58                    GenericArgument::Type(ty) => ty.clone(),
59                    _ => panic!(),
60                }
61            })
62            .collect(),
63    })
64}
65
66/// Represents result of [`Leaker::check()`], holding the cause in its tuple item.
67#[derive(Clone, Debug)]
68pub enum CheckResult {
69    /// The type must be interned because it directly depends on the type context.
70    MustIntern(Span),
71    /// The type must be interned because one of the types which it constituted with must be
72    /// interned.
73    MustInternOrInherit(Span),
74    /// The type must not be interned, because `type_leak` cannot intern this. (e.g. `impl Trait`s,
75    /// `_`, trait bounds with relative trait path, ...)
76    MustNotIntern(Span),
77    /// Other.
78    Neutral,
79}
80
81struct AnalyzeVisitor<'a> {
82    leaker: &'a mut Leaker,
83    generics: Generics,
84    parent: Option<NodeIndex<DefaultIx>>,
85    error: Option<Span>,
86}
87
88impl<'a, 'ast> Visit<'ast> for AnalyzeVisitor<'a> {
89    fn visit_trait_item_fn(&mut self, i: &TraitItemFn) {
90        let mut visitor = AnalyzeVisitor {
91            leaker: &mut self.leaker,
92            generics: self.generics.clone(),
93            parent: self.parent.clone(),
94            error: self.error.clone(),
95        };
96        for g in &i.sig.generics.params {
97            visitor.generics.params.push(g.clone());
98        }
99        let mut i = i.clone();
100        i.default = None;
101        i.semi_token = Some(Default::default());
102        syn::visit::visit_trait_item_fn(&mut visitor, &mut i);
103        self.error = visitor.error;
104    }
105
106    fn visit_trait_item_type(&mut self, i: &TraitItemType) {
107        let mut visitor = AnalyzeVisitor {
108            leaker: &mut self.leaker,
109            generics: self.generics.clone(),
110            parent: self.parent.clone(),
111            error: self.error.clone(),
112        };
113        for g in &i.generics.params {
114            visitor.generics.params.push(g.clone());
115        }
116        syn::visit::visit_trait_item_type(&mut visitor, i);
117        self.error = visitor.error;
118    }
119
120    fn visit_type(&mut self, i: &Type) {
121        match self.leaker.check(&self.generics, i) {
122            Err((_, s)) | Ok(CheckResult::MustNotIntern(s)) => {
123                // Emit error and terminate searching
124                self.error = Some(s);
125            }
126            o => {
127                let child = self
128                    .leaker
129                    .map
130                    .entry(i.clone())
131                    .or_insert_with(|| self.leaker.graph.add_node(i.clone()))
132                    .clone();
133                if let Some(parent) = &self.parent {
134                    self.leaker
135                        .graph
136                        .add_edge(parent.clone(), child.clone(), ());
137                } else {
138                    self.leaker.root_nodes.insert(child.clone());
139                }
140                if let Ok(CheckResult::MustIntern(_)) = o {
141                    // Terminate searching
142                    self.leaker.must_intern_nodes.insert(child.clone());
143                } else {
144                    // Perform recuesive call
145                    let parent = self.parent;
146                    self.parent = Some(child);
147                    syn::visit::visit_type(self, i);
148                    self.parent = parent;
149                }
150            }
151        }
152    }
153
154    fn visit_trait_bound(&mut self, i: &TraitBound) {
155        if i.path.leading_colon.is_none() {
156            // Trait bounds with relative oath
157            self.error = Some(i.span());
158        } else {
159            syn::visit::visit_trait_bound(self, i)
160        }
161    }
162
163    fn visit_expr_path(&mut self, i: &ExprPath) {
164        if i.path.leading_colon.is_none() {
165            // Value or trait bounds with relative oath
166            self.error = Some(i.span());
167        } else {
168            syn::visit::visit_expr_path(self, i)
169        }
170    }
171}
172
173impl Leaker {
174    /// Initialize with [`ItemStruct`]
175    ///
176    /// ```
177    /// # use type_leak::*;
178    /// # use syn::*;
179    /// let test_struct: ItemStruct = parse_quote!(
180    ///     pub struct MyStruct<'a, T1, T2: ::path::to::MyType1<MyType4>> {
181    ///         field1: MyType1,
182    ///         field2: (MyType2, MyType3<MyType1>, MyType4, MyType5),
183    ///         field3: &'a (T1, T2),
184    ///     }
185    /// );
186    /// let leaker = Leaker::from_struct(&test_struct).unwrap();
187    /// ```
188    pub fn from_struct(input: &ItemStruct) -> std::result::Result<Self, NotInternableError> {
189        let name = input.ident.clone();
190        let mut leaker = Leaker::with_generics_and_implementor(
191            input.generics.clone(),
192            Box::new(move |args: PathArguments| parse_quote!(#name #args)),
193        );
194        let mut visitor = AnalyzeVisitor {
195            leaker: &mut leaker,
196            parent: None,
197            error: None,
198            generics: input.generics.clone(),
199        };
200        visitor.visit_item_struct(input);
201        if let Some(e) = visitor.error {
202            return Err(NotInternableError(e));
203        }
204        Ok(leaker)
205    }
206
207    /// Initialize with [`ItemEnum`]
208    pub fn from_enum(input: &ItemEnum) -> std::result::Result<Self, NotInternableError> {
209        let name = input.ident.clone();
210        let mut leaker = Self::with_generics_and_implementor(
211            input.generics.clone(),
212            Box::new(move |args: PathArguments| parse_quote!(#name #args)),
213        );
214        let mut visitor = AnalyzeVisitor {
215            leaker: &mut leaker,
216            parent: None,
217            error: None,
218            generics: input.generics.clone(),
219        };
220        visitor.visit_item_enum(input);
221        if let Some(e) = visitor.error {
222            return Err(NotInternableError(e));
223        }
224        Ok(leaker)
225    }
226
227    /// Build an [`Leaker`] with given trait.
228    ///
229    /// Unlike enum nor struct, it requires ~alternative path~, an absolute path of a struct
230    /// which is declared the same crate with the leaker trait and also visible from
231    /// [`Referrer`]s' context. That struct is used as an `impl` target of `Repeater`
232    /// instead of the Leaker's path.
233    ///
234    /// ```
235    /// # use syn::*;
236    /// # use type_leak::Leaker;
237    /// let s: ItemTrait = parse_quote!{
238    ///     pub trait MyTrait<T, U> {
239    ///         fn func(self, t: T) -> U;
240    ///     }
241    /// };
242    /// let alternate: ItemStruct = parse_quote!{
243    ///     pub struct MyAlternate;
244    /// };
245    /// let _ = Leaker::from_trait(&s, Box::new(|_| parse_quote!(::path::to::Implementor)));
246    /// ```
247    pub fn from_trait(
248        input: &ItemTrait,
249        implementor_type_fn: Box<dyn Fn(PathArguments) -> Type>,
250    ) -> std::result::Result<Self, NotInternableError> {
251        let mut leaker =
252            Self::with_generics_and_implementor(input.generics.clone(), implementor_type_fn);
253        let mut visitor = AnalyzeVisitor {
254            leaker: &mut leaker,
255            parent: None,
256            error: None,
257            generics: input.generics.clone(),
258        };
259        visitor.visit_item_trait(input);
260        if let Some(e) = visitor.error {
261            return Err(NotInternableError(e));
262        }
263        Ok(leaker)
264    }
265
266    /// Initialize empty [`Leaker`] with given generics.
267    ///
268    /// Types, consts, lifetimes defined in the [`Generics`] is treated as "no needs to be interned" although
269    /// they looks like relative path names.
270    pub fn with_generics_and_implementor(
271        generics: Generics,
272        implementor_type_fn: Box<dyn Fn(PathArguments) -> Type>,
273    ) -> Self {
274        Self {
275            generics,
276            graph: Graph::new(),
277            map: HashMap::new(),
278            must_intern_nodes: HashSet::new(),
279            root_nodes: HashSet::new(),
280            implementor_type_fn,
281        }
282    }
283
284    /// Intern the given type as a root node.
285    pub fn intern(
286        &mut self,
287        generics: Generics,
288        ty: &Type,
289    ) -> std::result::Result<&mut Self, NotInternableError> {
290        let mut visitor = AnalyzeVisitor {
291            leaker: self,
292            parent: None,
293            error: None,
294            generics,
295        };
296        visitor.visit_type(ty);
297        if let Some(e) = visitor.error {
298            Err(NotInternableError(e))
299        } else {
300            Ok(self)
301        }
302    }
303
304    /// Check that the internableness of give `ty`. It returns `Err` in contradiction (the type
305    /// must and must not be interned).
306    ///
307    ///
308    /// See [`CheckResult`].
309    pub fn check(
310        &self,
311        generics: &Generics,
312        ty: &Type,
313    ) -> std::result::Result<CheckResult, (Span, Span)> {
314        use syn::visit::Visit;
315        #[derive(Clone)]
316        struct Visitor {
317            generic_lifetimes: Vec<Lifetime>,
318            generic_idents: Vec<Ident>,
319            impossible: Option<Span>,
320            must: Option<(isize, Span)>,
321        }
322
323        const _: () = {
324            use syn::visit::Visit;
325            impl<'a> Visit<'a> for Visitor {
326                fn visit_type(&mut self, i: &Type) {
327                    match i {
328                        Type::BareFn(TypeBareFn {
329                            lifetimes,
330                            inputs,
331                            output,
332                            ..
333                        }) => {
334                            let mut visitor = self.clone();
335                            visitor.must = None;
336                            visitor.generic_lifetimes.extend(
337                                lifetimes
338                                    .as_ref()
339                                    .map(|ls| {
340                                        ls.lifetimes.iter().map(|gp| {
341                                            if let GenericParam::Lifetime(lt) = gp {
342                                                lt.lifetime.clone()
343                                            } else {
344                                                panic!()
345                                            }
346                                        })
347                                    })
348                                    .into_iter()
349                                    .flatten(),
350                            );
351                            for input in inputs {
352                                visitor.visit_type(&input.ty);
353                            }
354                            if let ReturnType::Type(_, output) = output {
355                                visitor.visit_type(output.as_ref());
356                            }
357                            if self.impossible.is_none() {
358                                self.impossible = visitor.impossible;
359                            }
360                            match (self.must.clone(), visitor.must.clone()) {
361                                (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
362                                    self.must = Some((v_l + 1, v_m))
363                                }
364                                (None, Some((v_l, v_m))) => self.must = Some((v_l + 1, v_m)),
365                                _ => (),
366                            }
367                            return;
368                        }
369                        Type::TraitObject(TypeTraitObject { bounds, .. }) => {
370                            for bound in bounds {
371                                match bound {
372                                    TypeParamBound::Trait(TraitBound {
373                                        lifetimes, path, ..
374                                    }) => {
375                                        let mut visitor = self.clone();
376                                        visitor.must = None;
377                                        visitor.generic_lifetimes.extend(
378                                            lifetimes
379                                                .as_ref()
380                                                .map(|ls| {
381                                                    ls.lifetimes.iter().map(|gp| {
382                                                        if let GenericParam::Lifetime(lt) = gp {
383                                                            lt.lifetime.clone()
384                                                        } else {
385                                                            panic!()
386                                                        }
387                                                    })
388                                                })
389                                                .into_iter()
390                                                .flatten(),
391                                        );
392                                        visitor.visit_path(path);
393                                        if self.impossible.is_none() {
394                                            self.impossible = visitor.impossible;
395                                        }
396                                        match (self.must.clone(), visitor.must.clone()) {
397                                            (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
398                                                self.must = Some((v_l + 1, v_m))
399                                            }
400                                            (None, Some((v_l, v_m))) => {
401                                                self.must = Some((v_l + 1, v_m))
402                                            }
403                                            _ => (),
404                                        }
405                                        return;
406                                    }
407                                    TypeParamBound::Verbatim(_) => {
408                                        self.impossible = Some(bound.span());
409                                        return;
410                                    }
411                                    _ => (),
412                                }
413                            }
414                        }
415                        Type::ImplTrait(_) | Type::Macro(_) | Type::Verbatim(_) => {
416                            self.impossible = Some(i.span());
417                        }
418                        _ => (),
419                    }
420                    let mut visitor = self.clone();
421                    visitor.must = None;
422                    syn::visit::visit_type(&mut visitor, i);
423                    if visitor.impossible.is_some() {
424                        self.impossible = visitor.impossible;
425                    }
426                    match (self.must.clone(), visitor.must.clone()) {
427                        (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
428                            self.must = Some((v_l + 1, v_m))
429                        }
430                        (None, Some((v_l, v_m))) => self.must = Some((v_l + 1, v_m)),
431                        _ => (),
432                    }
433                }
434                fn visit_qself(&mut self, i: &QSelf) {
435                    if i.as_token.is_none() {
436                        self.impossible = Some(i.span());
437                    }
438                    syn::visit::visit_qself(self, i)
439                }
440                fn visit_lifetime(&mut self, i: &Lifetime) {
441                    if i.to_string() != "'static"
442                        && i.to_string() != "'_"
443                        && !self.generic_lifetimes.iter().any(|lt| lt == i)
444                    {
445                        self.must = Some((-1, i.span()));
446                    }
447                    syn::visit::visit_lifetime(self, i)
448                }
449                fn visit_expr(&mut self, i: &Expr) {
450                    match i {
451                        Expr::Closure(_) | Expr::Assign(_) | Expr::Verbatim(_) | Expr::Macro(_) => {
452                            self.impossible = Some(i.span());
453                        }
454                        _ => (),
455                    }
456                    syn::visit::visit_expr(self, i)
457                }
458                fn visit_path(&mut self, i: &Path) {
459                    if matches!(i.segments.iter().next(), Some(PathSegment { ident, arguments }) if ident == "Self" && arguments.is_none())
460                    {
461                        // do nothing
462                    } else {
463                        match (i.leading_colon, i.get_ident()) {
464                            // i is a generic parameter
465                            (None, Some(ident))
466                                if self.generic_idents.contains(&ident) || ident == "Self" => {}
467                            // relative path, not a generic parameter
468                            (None, _) => {
469                                self.must = Some((-1, i.span()));
470                            }
471                            // absolute path
472                            (Some(_), _) => (),
473                        }
474                    }
475
476                    syn::visit::visit_path(self, i)
477                }
478            }
479        };
480        let mut visitor = Visitor {
481            generic_lifetimes: generics
482                .params
483                .iter()
484                .filter_map(|gp| {
485                    if let GenericParam::Lifetime(lt) = gp {
486                        Some(lt.lifetime.clone())
487                    } else {
488                        None
489                    }
490                })
491                .collect(),
492            generic_idents: generics
493                .params
494                .iter()
495                .filter_map(|gp| match gp {
496                    GenericParam::Type(TypeParam { ident, .. })
497                    | GenericParam::Const(ConstParam { ident, .. }) => Some(ident.clone()),
498                    _ => None,
499                })
500                .collect(),
501            impossible: None,
502            must: None,
503        };
504        visitor.visit_type(ty);
505        match (visitor.must, visitor.impossible) {
506            (None, None) => Ok(CheckResult::Neutral),
507            (Some((0, span)), None) => Ok(CheckResult::MustIntern(span)),
508            (Some((_, span)), None) => Ok(CheckResult::MustInternOrInherit(span)),
509            (None, Some(span)) => Ok(CheckResult::MustNotIntern(span)),
510            (Some((_, span0)), Some(span1)) => Err((span0, span1)),
511        }
512    }
513
514    /// Finish building the [`Leaker`] and convert it into [`Referrer`].
515    pub fn finish(
516        self,
517        mut repeater_path_fn: impl FnMut(usize) -> Path,
518    ) -> (Vec<ItemImpl>, Referrer) {
519        let (impl_generics, _, where_clause) = self.generics.split_for_impl();
520        let id_map: HashMap<_, _> = self
521            .root_nodes
522            .iter()
523            .enumerate()
524            .map(|(n, idx)| {
525                (
526                    self.graph.node_weight(idx.clone()).expect("hello3").clone(),
527                    n,
528                )
529            })
530            .collect();
531        let path_args = PathArguments::AngleBracketed(AngleBracketedGenericArguments {
532            colon2_token: None,
533            lt_token: Token![<](Span::call_site()),
534            args: self
535                .generics
536                .params
537                .iter()
538                .map(|param| match param {
539                    GenericParam::Lifetime(lifetime_param) => {
540                        GenericArgument::Lifetime(lifetime_param.lifetime.clone())
541                    }
542                    GenericParam::Type(TypeParam { ident, .. }) => {
543                        GenericArgument::Type(parse_quote!(#ident))
544                    }
545                    GenericParam::Const(ConstParam { ident, .. }) => {
546                        GenericArgument::Const(parse_quote!(#ident))
547                    }
548                })
549                .collect(),
550            gt_token: Token![>](Span::call_site()),
551        });
552        (
553            id_map
554                .iter()
555                .map(|(ty, n)| {
556                    parse2(quote! {
557                impl #impl_generics #{repeater_path_fn(*n)} for #{(*self.implementor_type_fn)(path_args.clone())} #where_clause {
558                    type Type = #ty;
559                }
560            }).expect("hello4")
561                })
562                .collect(),
563            Referrer { map: id_map },
564        )
565    }
566
567    #[cfg_attr(doc, aquamarine::aquamarine)]
568    /// Reduce nodes to decrease cost of {`Leaker`}'s implementation.
569    ///
570    /// # Algorithm
571    ///
572    /// To consult the algorithm, see the following [`Leaker`]'s input:
573    ///
574    /// ```ignore
575    /// pub struct MyStruct<'a, T1, T2: ::path::to::MyType1<MyType4>> {
576    ///     field1: MyType1,
577    ///     field2: (MyType2, MyType3<MyType1>, MyType4, MyType5),
578    ///     field3: &'a (T1, T2),
579    /// }
580    /// ```
581    ///
582    /// [`Leaker`], when initialized with [`Leaker::from_struct()`], analyze the AST and
583    /// construct a DAG which represents all (internable) types and the dependency relations like
584    /// this:
585    ///
586    /// ```mermaid
587    /// graph TD
588    ///   1["★MyType1
589    ///   (Node 1)"]
590    ///   2["★(MyType2, MyType3#lt;MyType1#gt;, MyType4, MyType5)
591    ///   (Node 2)"] -->3["MyType2
592    ///   (Node 3)"]
593    ///   2 -->4["MyType3#lt;MyType1#gt;
594    ///   (Node 4)"]
595    ///   2 -->0["★MyType4
596    ///   (Node 0)"]
597    ///   2 -->5["MyType5
598    ///   (Node 5)"]
599    ///   6["★&a (T1, T2)
600    ///   (Node 6)"] -->7["(T1, T2)
601    ///   (Node 7)"]
602    ///   7 -->8["T1
603    ///   (Node 8)"]
604    ///   7 -->9["T2
605    ///   (Node 9)"]
606    ///   classDef redNode stroke:#ff0000;
607    ///   class 0,1,3,4,5 redNode;
608    /// ```
609    ///
610    /// The **red** node is flagged as [`CheckResult::MustIntern`] by [`Leaker::check()`] (which means
611    /// the type literature depends on the type context, so it must be interned).
612    ///
613    /// This algorithm reduce the nodes, remaining that all root type (annotated with ★) can be
614    /// expressed with existing **red** nodes.
615    ///
616    /// Here, there are some choice in its freedom:
617    ///
618    /// - Intern all **red** nodes and ignore others (because other nodes are not needed to be
619    /// intern, or constructable with red nodes)
620    /// - Not directly intern **red** nodes; intern common ancessors instead if it is affordable.
621    ///
622    /// So finally, it results like:
623    ///
624    /// ```mermaid
625    /// graph TD
626    ///   0["MyType4
627    ///   (Node 0)"]
628    ///   1["MyType1
629    ///   (Node 1)"]
630    ///   2["(MyType2, MyType3 #lt; MyType1 #gt;, MyType4, MyType5)
631    ///   (Node 2)"]
632    ///   classDef redNode stroke:#ff0000;
633    ///   class 0,1,2 redNode;
634    /// ```
635    ///
636    pub fn reduce_roots(&mut self) {
637        // dbg!(&self.graph, &self.root_nodes);
638        self.reduce_unreachable_nodes();
639        // self.reduce_obvious_nodes();
640        // dbg!(&self.graph, &self.root_nodes);
641        // TODO: unobvious root reduction with heaulistics
642    }
643
644    fn reduce_obvious_nodes(&mut self) {
645        let mut must_intern_nodes: Vec<_> = self.must_intern_nodes.iter().cloned().collect();
646        let mut root_nodes: Vec<_> = self.root_nodes.iter().cloned().collect();
647        let nodes: Vec<_> = self
648            .graph
649            .node_indices()
650            .filter_map(|n| {
651                let mut it = self.graph.edges(n.clone());
652                if let Some(edge) = it.next() {
653                    if let None = it.next() {
654                        return Some((edge.source(), edge.target(), edge.id()));
655                    }
656                }
657                None
658            })
659            .collect();
660        for (node1, node2, edge) in nodes {
661            self.graph.remove_edge(edge);
662            for (edge_in_source, edge_in) in self
663                .graph
664                .edges_directed(node1, petgraph::Direction::Incoming)
665                .map(|er| (er.source(), er.id()))
666                .collect::<Vec<_>>()
667            {
668                self.graph.update_edge(edge_in_source, node2, ());
669                self.graph.remove_edge(edge_in);
670            }
671            must_intern_nodes.iter_mut().for_each(|n| {
672                if n == &node1 {
673                    *n = node2.clone()
674                }
675            });
676            root_nodes.iter_mut().for_each(|n| {
677                if n == &node1 {
678                    *n = node2.clone()
679                }
680            });
681            self.graph.remove_node(node1);
682        }
683        self.must_intern_nodes = must_intern_nodes.into_iter().collect();
684        self.root_nodes = root_nodes.into_iter().collect();
685    }
686
687    fn reduce_unreachable_nodes(&mut self) {
688        let reachable_forward = get_reachable_nodes(&self.graph, self.root_nodes.iter().cloned());
689        self.graph.reverse();
690        let reachable_backward =
691            get_reachable_nodes(&self.graph, self.must_intern_nodes.iter().cloned());
692        self.graph.reverse();
693        let reachable = reachable_forward
694            .intersection(&reachable_backward)
695            .cloned()
696            .collect::<HashSet<_>>();
697        // self.graph = self.graph.filter_map(
698        //     |ix, node| reachable.contains(&ix).then_some(node.clone()),
699        //     |ix, _| {
700        //         let (e1, e2) = self.graph.edge_endpoints(ix).unwrap();
701        //         (reachable.contains(&e1) && reachable.contains(&e2)).then_some(())
702        //     },
703        // );
704        let mut new_graph = Graph::new();
705        let mut node_map = HashMap::new();
706        for node in self.graph.node_indices() {
707            if reachable.contains(&node) {
708                let new_node = new_graph.add_node(self.graph[node].clone());
709                node_map.insert(node, new_node);
710            }
711        }
712        for edge in self.graph.edge_indices() {
713            let (n1, n2) = self.graph.edge_endpoints(edge).unwrap();
714            if let (Some(nn1), Some(nn2)) = (node_map.get(&n1), node_map.get(&n2)) {
715                new_graph.add_edge(*nn1, *nn2, ());
716            }
717        }
718        self.root_nodes = self
719            .root_nodes
720            .iter()
721            .filter_map(|n| node_map.get(n).cloned())
722            .collect();
723        self.must_intern_nodes = self
724            .must_intern_nodes
725            .iter()
726            .filter_map(|n| node_map.get(n).cloned())
727            .collect();
728        let _ = std::mem::replace(&mut self.graph, new_graph);
729    }
730}
731
732fn get_reachable_nodes<N, E>(
733    graph: &Graph<N, E>,
734    roots: impl IntoIterator<Item = NodeIndex<DefaultIx>>,
735) -> HashSet<NodeIndex<DefaultIx>> {
736    let mut ret: HashSet<_> = roots.into_iter().collect();
737    let mut frontier = ret.clone();
738    loop {
739        let mut buf: HashSet<_> = frontier
740            .iter()
741            .map(|node| graph.neighbors(node.clone()))
742            .flatten()
743            .collect();
744        let mut count = 0;
745        for node in &buf {
746            if ret.insert(node.clone()) {
747                count += 1;
748            }
749        }
750        if count == 0 {
751            break;
752        }
753        std::mem::swap(&mut frontier, &mut buf);
754    }
755    ret
756}
757
758#[derive(Clone, PartialEq, Eq, Debug)]
759pub struct Referrer {
760    map: HashMap<Type, usize>,
761}
762
763impl Referrer {
764    pub fn is_empty(&self) -> bool {
765        self.map.is_empty()
766    }
767
768    pub fn iter(&self) -> impl Iterator<Item = &Type> {
769        self.map.keys()
770    }
771
772    pub fn into_visitor<F: FnMut(usize) -> Path + Clone>(
773        self,
774        leaker_ty: Type,
775        repeater_path_fn: F,
776    ) -> Visitor<F> {
777        Visitor(self, leaker_ty, repeater_path_fn)
778    }
779
780    pub fn expand(
781        &self,
782        ty: Type,
783        leaker_ty: &Type,
784        repeater_path_fn: impl FnMut(usize) -> Path,
785    ) -> Type {
786        use syn::fold::Fold;
787
788        struct Folder<'a, F>(&'a Referrer, &'a Type, F);
789        impl<'a, F: FnMut(usize) -> Path> Fold for Folder<'a, F> {
790            fn fold_type(&mut self, ty: Type) -> Type {
791                if let Some(idx) = self.0.map.get(&ty) {
792                    parse2(quote! {
793                        <#{&self.1} as #{&self.2(*idx)}>::Type
794                    })
795                    .unwrap()
796                } else {
797                    syn::fold::fold_type(self, ty)
798                }
799            }
800        }
801        let mut folder = Folder(self, leaker_ty, repeater_path_fn);
802        folder.fold_type(ty)
803    }
804}
805
806#[derive(Clone, Debug)]
807pub struct Visitor<F>(Referrer, Type, F);
808
809impl<F: FnMut(usize) -> Path + Clone> Visitor<F> {
810    fn with_generics(&mut self, generics: &mut Generics) -> Self {
811        let mut visitor = self.clone();
812        for gp in generics.params.iter_mut() {
813            if let GenericParam::Type(TypeParam { ident, .. }) = gp {
814                visitor.0.map.remove(&parse_quote!(#ident));
815            }
816            visitor.visit_generic_param_mut(gp);
817        }
818        visitor
819    }
820
821    fn with_signature(&mut self, sig: &mut Signature) -> Self {
822        let mut visitor = self.with_generics(&mut sig.generics);
823        for input in sig.inputs.iter_mut() {
824            visitor.visit_fn_arg_mut(input);
825        }
826        visitor.visit_return_type_mut(&mut sig.output);
827        visitor
828    }
829}
830
831impl<F: FnMut(usize) -> Path + Clone> VisitMut for Visitor<F> {
832    fn visit_type_mut(&mut self, i: &mut Type) {
833        *i = self.0.expand(i.clone(), &self.1, &mut self.2);
834    }
835    fn visit_item_struct_mut(&mut self, i: &mut ItemStruct) {
836        for attr in i.attrs.iter_mut() {
837            self.visit_attribute_mut(attr);
838        }
839        let mut visitor = self.with_generics(&mut i.generics);
840        visitor.visit_fields_mut(&mut i.fields);
841    }
842    fn visit_item_enum_mut(&mut self, i: &mut ItemEnum) {
843        for attr in i.attrs.iter_mut() {
844            self.visit_attribute_mut(attr);
845        }
846        let mut visitor = self.with_generics(&mut i.generics);
847        for variant in i.variants.iter_mut() {
848            visitor.visit_variant_mut(variant);
849        }
850    }
851    fn visit_item_trait_mut(&mut self, i: &mut ItemTrait) {
852        for attr in i.attrs.iter_mut() {
853            self.visit_attribute_mut(attr);
854        }
855        let mut visitor = self.with_generics(&mut i.generics);
856        for supertrait in i.supertraits.iter_mut() {
857            visitor.visit_type_param_bound_mut(supertrait);
858        }
859        for item in i.items.iter_mut() {
860            visitor.visit_trait_item_mut(item);
861        }
862    }
863    fn visit_item_union_mut(&mut self, i: &mut ItemUnion) {
864        for attr in i.attrs.iter_mut() {
865            self.visit_attribute_mut(attr);
866        }
867        let mut visitor = self.with_generics(&mut i.generics);
868        visitor.visit_fields_named_mut(&mut i.fields);
869    }
870    fn visit_item_type_mut(&mut self, i: &mut ItemType) {
871        for attr in i.attrs.iter_mut() {
872            self.visit_attribute_mut(attr);
873        }
874        let mut visitor = self.with_generics(&mut i.generics);
875        visitor.visit_type_mut(&mut i.ty);
876    }
877    fn visit_item_fn_mut(&mut self, i: &mut ItemFn) {
878        for attr in i.attrs.iter_mut() {
879            self.visit_attribute_mut(attr);
880        }
881        let mut visitor = self.with_signature(&mut i.sig);
882        visitor.visit_block_mut(i.block.as_mut());
883    }
884    fn visit_trait_item_fn_mut(&mut self, i: &mut TraitItemFn) {
885        for attr in i.attrs.iter_mut() {
886            self.visit_attribute_mut(attr);
887        }
888        let mut visitor = self.with_signature(&mut i.sig);
889        if let Some(block) = &mut i.default {
890            visitor.visit_block_mut(block);
891        }
892    }
893    fn visit_trait_item_type_mut(&mut self, i: &mut TraitItemType) {
894        for attr in i.attrs.iter_mut() {
895            self.visit_attribute_mut(attr);
896        }
897        let mut visitor = self.with_generics(&mut i.generics);
898        for bound in i.bounds.iter_mut() {
899            visitor.visit_type_param_bound_mut(bound);
900        }
901        if let Some((_, ty)) = &mut i.default {
902            visitor.visit_type_mut(ty);
903        }
904    }
905    fn visit_trait_item_const_mut(&mut self, i: &mut TraitItemConst) {
906        for attr in i.attrs.iter_mut() {
907            self.visit_attribute_mut(attr);
908        }
909        let mut visitor = self.with_generics(&mut i.generics);
910        visitor.visit_type_mut(&mut i.ty);
911        if let Some((_, expr)) = &mut i.default {
912            visitor.visit_expr_mut(expr);
913        }
914    }
915    fn visit_block_mut(&mut self, i: &mut Block) {
916        let mut visitor = self.clone();
917        for stmt in &i.stmts {
918            match stmt {
919                Stmt::Item(Item::Struct(ItemStruct { ident, .. }))
920                | Stmt::Item(Item::Enum(ItemEnum { ident, .. }))
921                | Stmt::Item(Item::Union(ItemUnion { ident, .. }))
922                | Stmt::Item(Item::Trait(ItemTrait { ident, .. }))
923                | Stmt::Item(Item::Type(ItemType { ident, .. })) => {
924                    visitor.0.map.remove(&parse_quote!(#ident));
925                }
926                _ => (),
927            }
928        }
929        for stmt in i.stmts.iter_mut() {
930            visitor.visit_stmt_mut(stmt);
931        }
932    }
933}
934
935impl Parse for Referrer {
936    fn parse(input: parse::ParseStream) -> Result<Self> {
937        let mut map = HashMap::new();
938        let map_content: syn::parse::ParseBuffer<'_>;
939        parenthesized!(map_content in input);
940        while !map_content.is_empty() {
941            let key: Type = map_content.parse()?;
942            map_content.parse::<Token![:]>()?;
943            let value: LitInt = map_content.parse()?;
944            map.insert(key, value.base10_parse()?);
945            if map_content.is_empty() {
946                break;
947            }
948            map_content.parse::<Token![,]>()?;
949        }
950        Ok(Self { map })
951    }
952}
953
954impl ToTokens for Referrer {
955    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
956        tokens.extend(quote! {
957            (
958                #(for (key, val) in &self.map), {
959                    #key: #val
960                }
961            )
962        })
963    }
964}
type_leak/lib.rs

type_leak/
lib.rs
