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(_)
416                        | Type::Infer(_)
417                        | Type::Macro(_)
418                        | Type::Verbatim(_) => {
419                            self.impossible = Some(i.span());
420                        }
421                        _ => (),
422                    }
423                    let mut visitor = self.clone();
424                    visitor.must = None;
425                    syn::visit::visit_type(&mut visitor, i);
426                    if visitor.impossible.is_some() {
427                        self.impossible = visitor.impossible;
428                    }
429                    match (self.must.clone(), visitor.must.clone()) {
430                        (Some((s_l, _)), Some((v_l, v_m))) if v_l + 1 < s_l => {
431                            self.must = Some((v_l + 1, v_m))
432                        }
433                        (None, Some((v_l, v_m))) => self.must = Some((v_l + 1, v_m)),
434                        _ => (),
435                    }
436                }
437                fn visit_qself(&mut self, i: &QSelf) {
438                    if i.as_token.is_none() {
439                        self.impossible = Some(i.span());
440                    }
441                    syn::visit::visit_qself(self, i)
442                }
443                fn visit_lifetime(&mut self, i: &Lifetime) {
444                    if i.to_string() != "'static"
445                        && !self.generic_lifetimes.iter().any(|lt| lt == i)
446                    {
447                        self.must = Some((-1, i.span()));
448                    }
449                    syn::visit::visit_lifetime(self, i)
450                }
451                fn visit_expr(&mut self, i: &Expr) {
452                    match i {
453                        Expr::Closure(_)
454                        | Expr::Assign(_)
455                        | Expr::Verbatim(_)
456                        | Expr::Macro(_)
457                        | Expr::Infer(_) => {
458                            self.impossible = Some(i.span());
459                        }
460                        _ => (),
461                    }
462                    syn::visit::visit_expr(self, i)
463                }
464                fn visit_path(&mut self, i: &Path) {
465                    if matches!(i.segments.iter().next(), Some(PathSegment { ident, arguments }) if ident == "Self" && arguments.is_none())
466                    {
467                        // do nothing
468                    } else {
469                        match (i.leading_colon, i.get_ident()) {
470                            // i is a generic parameter
471                            (None, Some(ident))
472                                if self.generic_idents.contains(&ident) || ident == "Self" => {}
473                            // relative path, not a generic parameter
474                            (None, _) => {
475                                self.must = Some((-1, i.span()));
476                            }
477                            // absolute path
478                            (Some(_), _) => (),
479                        }
480                    }
481
482                    syn::visit::visit_path(self, i)
483                }
484            }
485        };
486        let mut visitor = Visitor {
487            generic_lifetimes: generics
488                .params
489                .iter()
490                .filter_map(|gp| {
491                    if let GenericParam::Lifetime(lt) = gp {
492                        Some(lt.lifetime.clone())
493                    } else {
494                        None
495                    }
496                })
497                .collect(),
498            generic_idents: generics
499                .params
500                .iter()
501                .filter_map(|gp| match gp {
502                    GenericParam::Type(TypeParam { ident, .. })
503                    | GenericParam::Const(ConstParam { ident, .. }) => Some(ident.clone()),
504                    _ => None,
505                })
506                .collect(),
507            impossible: None,
508            must: None,
509        };
510        visitor.visit_type(ty);
511        match (visitor.must, visitor.impossible) {
512            (None, None) => Ok(CheckResult::Neutral),
513            (Some((0, span)), None) => Ok(CheckResult::MustIntern(span)),
514            (Some((_, span)), None) => Ok(CheckResult::MustInternOrInherit(span)),
515            (None, Some(span)) => Ok(CheckResult::MustNotIntern(span)),
516            (Some((_, span0)), Some(span1)) => Err((span0, span1)),
517        }
518    }
519
520    /// Finish building the [`Leaker`] and convert it into [`Referrer`].
521    pub fn finish(
522        self,
523        mut repeater_path_fn: impl FnMut(usize) -> Path,
524    ) -> (Vec<ItemImpl>, Referrer) {
525        let (impl_generics, _, where_clause) = self.generics.split_for_impl();
526        let id_map: HashMap<_, _> = self
527            .root_nodes
528            .iter()
529            .enumerate()
530            .map(|(n, idx)| {
531                (
532                    self.graph.node_weight(idx.clone()).expect("hello3").clone(),
533                    n,
534                )
535            })
536            .collect();
537        let path_args = PathArguments::AngleBracketed(AngleBracketedGenericArguments {
538            colon2_token: None,
539            lt_token: Token![<](Span::call_site()),
540            args: self
541                .generics
542                .params
543                .iter()
544                .map(|param| match param {
545                    GenericParam::Lifetime(lifetime_param) => {
546                        GenericArgument::Lifetime(lifetime_param.lifetime.clone())
547                    }
548                    GenericParam::Type(TypeParam { ident, .. }) => {
549                        GenericArgument::Type(parse_quote!(#ident))
550                    }
551                    GenericParam::Const(ConstParam { ident, .. }) => {
552                        GenericArgument::Const(parse_quote!(#ident))
553                    }
554                })
555                .collect(),
556            gt_token: Token![>](Span::call_site()),
557        });
558        (
559            id_map
560                .iter()
561                .map(|(ty, n)| {
562                    parse2(quote! {
563                impl #impl_generics #{repeater_path_fn(*n)} for #{(*self.implementor_type_fn)(path_args.clone())} #where_clause {
564                    type Type = #ty;
565                }
566            }).expect("hello4")
567                })
568                .collect(),
569            Referrer { map: id_map },
570        )
571    }
572
573    #[cfg_attr(doc, aquamarine::aquamarine)]
574    /// Reduce nodes to decrease cost of {`Leaker`}'s implementation.
575    ///
576    /// # Algorithm
577    ///
578    /// To consult the algorithm, see the following [`Leaker`]'s input:
579    ///
580    /// ```ignore
581    /// pub struct MyStruct<'a, T1, T2: ::path::to::MyType1<MyType4>> {
582    ///     field1: MyType1,
583    ///     field2: (MyType2, MyType3<MyType1>, MyType4, MyType5),
584    ///     field3: &'a (T1, T2),
585    /// }
586    /// ```
587    ///
588    /// [`Leaker`], when initialized with [`Leaker::from_struct()`], analyze the AST and
589    /// construct a DAG which represents all (internable) types and the dependency relations like
590    /// this:
591    ///
592    /// ```mermaid
593    /// graph TD
594    ///   1["★MyType1
595    ///   (Node 1)"]
596    ///   2["★(MyType2, MyType3#lt;MyType1#gt;, MyType4, MyType5)
597    ///   (Node 2)"] -->3["MyType2
598    ///   (Node 3)"]
599    ///   2 -->4["MyType3#lt;MyType1#gt;
600    ///   (Node 4)"]
601    ///   2 -->0["★MyType4
602    ///   (Node 0)"]
603    ///   2 -->5["MyType5
604    ///   (Node 5)"]
605    ///   6["★&a (T1, T2)
606    ///   (Node 6)"] -->7["(T1, T2)
607    ///   (Node 7)"]
608    ///   7 -->8["T1
609    ///   (Node 8)"]
610    ///   7 -->9["T2
611    ///   (Node 9)"]
612    ///   classDef redNode stroke:#ff0000;
613    ///   class 0,1,3,4,5 redNode;
614    /// ```
615    ///
616    /// The **red** node is flagged as [`CheckResult::MustIntern`] by [`Leaker::check()`] (which means
617    /// the type literature depends on the type context, so it must be interned).
618    ///
619    /// This algorithm reduce the nodes, remaining that all root type (annotated with ★) can be
620    /// expressed with existing **red** nodes.
621    ///
622    /// Here, there are some choice in its freedom:
623    ///
624    /// - Intern all **red** nodes and ignore others (because other nodes are not needed to be
625    /// intern, or constructable with red nodes)
626    /// - Not directly intern **red** nodes; intern common ancessors instead if it is affordable.
627    ///
628    /// So finally, it results like:
629    ///
630    /// ```mermaid
631    /// graph TD
632    ///   0["MyType4
633    ///   (Node 0)"]
634    ///   1["MyType1
635    ///   (Node 1)"]
636    ///   2["(MyType2, MyType3 #lt; MyType1 #gt;, MyType4, MyType5)
637    ///   (Node 2)"]
638    ///   classDef redNode stroke:#ff0000;
639    ///   class 0,1,2 redNode;
640    /// ```
641    ///
642    pub fn reduce_roots(&mut self) {
643        self.reduce_unreachable_nodes();
644        self.reduce_obvious_nodes();
645        // TODO: unobvious root reduction with heaulistics
646    }
647
648    fn reduce_obvious_nodes(&mut self) {
649        let mut must_intern_nodes: Vec<_> = self.must_intern_nodes.iter().cloned().collect();
650        let mut root_nodes: Vec<_> = self.root_nodes.iter().cloned().collect();
651        let nodes: Vec<_> = self
652            .graph
653            .node_indices()
654            .filter_map(|n| {
655                let mut it = self.graph.edges(n.clone());
656                if let Some(edge) = it.next() {
657                    if let None = it.next() {
658                        return Some((edge.source(), edge.target(), edge.id()));
659                    }
660                }
661                None
662            })
663            .collect();
664        for (node1, node2, edge) in nodes {
665            self.graph.remove_edge(edge);
666            for (edge_in_source, edge_in) in self
667                .graph
668                .edges_directed(node1, petgraph::Direction::Incoming)
669                .map(|er| (er.source(), er.id()))
670                .collect::<Vec<_>>()
671            {
672                self.graph.update_edge(edge_in_source, node2, ());
673                self.graph.remove_edge(edge_in);
674            }
675            must_intern_nodes.iter_mut().for_each(|n| {
676                if n == &node1 {
677                    *n = node2.clone()
678                }
679            });
680            root_nodes.iter_mut().for_each(|n| {
681                if n == &node1 {
682                    *n = node2.clone()
683                }
684            });
685            self.graph.remove_node(node1);
686        }
687        self.must_intern_nodes = must_intern_nodes.into_iter().collect();
688        self.root_nodes = root_nodes.into_iter().collect();
689    }
690
691    fn reduce_unreachable_nodes(&mut self) {
692        let reachable_forward = get_reachable_nodes(&self.graph, self.root_nodes.iter().cloned());
693        self.graph.reverse();
694        let reachable_backward =
695            get_reachable_nodes(&self.graph, self.must_intern_nodes.iter().cloned());
696        self.graph.reverse();
697        let reachable = reachable_forward
698            .intersection(&reachable_backward)
699            .cloned()
700            .collect::<HashSet<_>>();
701        // self.graph = self.graph.filter_map(
702        //     |ix, node| reachable.contains(&ix).then_some(node.clone()),
703        //     |ix, _| {
704        //         let (e1, e2) = self.graph.edge_endpoints(ix).unwrap();
705        //         (reachable.contains(&e1) && reachable.contains(&e2)).then_some(())
706        //     },
707        // );
708        let mut new_graph = Graph::new();
709        let mut node_map = HashMap::new();
710        for node in self.graph.node_indices() {
711            if reachable.contains(&node) {
712                let new_node = new_graph.add_node(self.graph[node].clone());
713                node_map.insert(node, new_node);
714            }
715        }
716        for edge in self.graph.edge_indices() {
717            let (n1, n2) = self.graph.edge_endpoints(edge).unwrap();
718            if let (Some(nn1), Some(nn2)) = (node_map.get(&n1), node_map.get(&n2)) {
719                new_graph.add_edge(*nn1, *nn2, ());
720            }
721        }
722        self.root_nodes = self
723            .root_nodes
724            .iter()
725            .filter_map(|n| node_map.get(n).cloned())
726            .collect();
727        self.must_intern_nodes = self
728            .must_intern_nodes
729            .iter()
730            .filter_map(|n| node_map.get(n).cloned())
731            .collect();
732        let _ = std::mem::replace(&mut self.graph, new_graph);
733    }
734}
735
736fn get_reachable_nodes<N, E>(
737    graph: &Graph<N, E>,
738    roots: impl IntoIterator<Item = NodeIndex<DefaultIx>>,
739) -> HashSet<NodeIndex<DefaultIx>> {
740    let mut ret: HashSet<_> = roots.into_iter().collect();
741    let mut frontier = ret.clone();
742    loop {
743        let mut buf: HashSet<_> = frontier
744            .iter()
745            .map(|node| graph.neighbors(node.clone()))
746            .flatten()
747            .collect();
748        let mut count = 0;
749        for node in &buf {
750            if ret.insert(node.clone()) {
751                count += 1;
752            }
753        }
754        if count == 0 {
755            break;
756        }
757        std::mem::swap(&mut frontier, &mut buf);
758    }
759    ret
760}
761
762#[derive(Clone, PartialEq, Eq, Debug)]
763pub struct Referrer {
764    map: HashMap<Type, usize>,
765}
766
767impl Referrer {
768    pub fn is_empty(&self) -> bool {
769        self.map.is_empty()
770    }
771
772    pub fn iter(&self) -> impl Iterator<Item = &Type> {
773        self.map.keys()
774    }
775
776    pub fn into_visitor<F: FnMut(usize) -> Path + Clone>(
777        self,
778        leaker_ty: Type,
779        repeater_path_fn: F,
780    ) -> Visitor<F> {
781        Visitor(self, leaker_ty, repeater_path_fn)
782    }
783
784    pub fn expand(
785        &self,
786        ty: Type,
787        leaker_ty: &Type,
788        repeater_path_fn: impl FnMut(usize) -> Path,
789    ) -> Type {
790        use syn::fold::Fold;
791
792        struct Folder<'a, F>(&'a Referrer, &'a Type, F);
793        impl<'a, F: FnMut(usize) -> Path> Fold for Folder<'a, F> {
794            fn fold_type(&mut self, ty: Type) -> Type {
795                if let Some(idx) = self.0.map.get(&ty) {
796                    parse2(quote! {
797                        <#{&self.1} as #{&self.2(*idx)}>::Type
798                    })
799                    .unwrap()
800                } else {
801                    syn::fold::fold_type(self, ty)
802                }
803            }
804        }
805        let mut folder = Folder(self, leaker_ty, repeater_path_fn);
806        folder.fold_type(ty)
807    }
808}
809
810#[derive(Clone, Debug)]
811pub struct Visitor<F>(Referrer, Type, F);
812
813impl<F: FnMut(usize) -> Path + Clone> Visitor<F> {
814    fn with_generics(&mut self, generics: &mut Generics) -> Self {
815        let mut visitor = self.clone();
816        for gp in generics.params.iter_mut() {
817            if let GenericParam::Type(TypeParam { ident, .. }) = gp {
818                visitor.0.map.remove(&parse_quote!(#ident));
819            }
820            visitor.visit_generic_param_mut(gp);
821        }
822        visitor
823    }
824
825    fn with_signature(&mut self, sig: &mut Signature) -> Self {
826        let mut visitor = self.with_generics(&mut sig.generics);
827        for input in sig.inputs.iter_mut() {
828            visitor.visit_fn_arg_mut(input);
829        }
830        visitor.visit_return_type_mut(&mut sig.output);
831        visitor
832    }
833}
834
835impl<F: FnMut(usize) -> Path + Clone> VisitMut for Visitor<F> {
836    fn visit_type_mut(&mut self, i: &mut Type) {
837        *i = self.0.expand(i.clone(), &self.1, &mut self.2);
838    }
839    fn visit_item_struct_mut(&mut self, i: &mut ItemStruct) {
840        for attr in i.attrs.iter_mut() {
841            self.visit_attribute_mut(attr);
842        }
843        let mut visitor = self.with_generics(&mut i.generics);
844        visitor.visit_fields_mut(&mut i.fields);
845    }
846    fn visit_item_enum_mut(&mut self, i: &mut ItemEnum) {
847        for attr in i.attrs.iter_mut() {
848            self.visit_attribute_mut(attr);
849        }
850        let mut visitor = self.with_generics(&mut i.generics);
851        for variant in i.variants.iter_mut() {
852            visitor.visit_variant_mut(variant);
853        }
854    }
855    fn visit_item_trait_mut(&mut self, i: &mut ItemTrait) {
856        for attr in i.attrs.iter_mut() {
857            self.visit_attribute_mut(attr);
858        }
859        let mut visitor = self.with_generics(&mut i.generics);
860        for supertrait in i.supertraits.iter_mut() {
861            visitor.visit_type_param_bound_mut(supertrait);
862        }
863        for item in i.items.iter_mut() {
864            visitor.visit_trait_item_mut(item);
865        }
866    }
867    fn visit_item_union_mut(&mut self, i: &mut ItemUnion) {
868        for attr in i.attrs.iter_mut() {
869            self.visit_attribute_mut(attr);
870        }
871        let mut visitor = self.with_generics(&mut i.generics);
872        visitor.visit_fields_named_mut(&mut i.fields);
873    }
874    fn visit_item_type_mut(&mut self, i: &mut ItemType) {
875        for attr in i.attrs.iter_mut() {
876            self.visit_attribute_mut(attr);
877        }
878        let mut visitor = self.with_generics(&mut i.generics);
879        visitor.visit_type_mut(&mut i.ty);
880    }
881    fn visit_item_fn_mut(&mut self, i: &mut ItemFn) {
882        for attr in i.attrs.iter_mut() {
883            self.visit_attribute_mut(attr);
884        }
885        let mut visitor = self.with_signature(&mut i.sig);
886        visitor.visit_block_mut(i.block.as_mut());
887    }
888    fn visit_trait_item_fn_mut(&mut self, i: &mut TraitItemFn) {
889        for attr in i.attrs.iter_mut() {
890            self.visit_attribute_mut(attr);
891        }
892        let mut visitor = self.with_signature(&mut i.sig);
893        if let Some(block) = &mut i.default {
894            visitor.visit_block_mut(block);
895        }
896    }
897    fn visit_trait_item_type_mut(&mut self, i: &mut TraitItemType) {
898        for attr in i.attrs.iter_mut() {
899            self.visit_attribute_mut(attr);
900        }
901        let mut visitor = self.with_generics(&mut i.generics);
902        for bound in i.bounds.iter_mut() {
903            visitor.visit_type_param_bound_mut(bound);
904        }
905        if let Some((_, ty)) = &mut i.default {
906            visitor.visit_type_mut(ty);
907        }
908    }
909    fn visit_trait_item_const_mut(&mut self, i: &mut TraitItemConst) {
910        for attr in i.attrs.iter_mut() {
911            self.visit_attribute_mut(attr);
912        }
913        let mut visitor = self.with_generics(&mut i.generics);
914        visitor.visit_type_mut(&mut i.ty);
915        if let Some((_, expr)) = &mut i.default {
916            visitor.visit_expr_mut(expr);
917        }
918    }
919    fn visit_block_mut(&mut self, i: &mut Block) {
920        let mut visitor = self.clone();
921        for stmt in &i.stmts {
922            match stmt {
923                Stmt::Item(Item::Struct(ItemStruct { ident, .. }))
924                | Stmt::Item(Item::Enum(ItemEnum { ident, .. }))
925                | Stmt::Item(Item::Union(ItemUnion { ident, .. }))
926                | Stmt::Item(Item::Trait(ItemTrait { ident, .. }))
927                | Stmt::Item(Item::Type(ItemType { ident, .. })) => {
928                    visitor.0.map.remove(&parse_quote!(#ident));
929                }
930                _ => (),
931            }
932        }
933        for stmt in i.stmts.iter_mut() {
934            visitor.visit_stmt_mut(stmt);
935        }
936    }
937}
938
939impl Parse for Referrer {
940    fn parse(input: parse::ParseStream) -> Result<Self> {
941        let mut map = HashMap::new();
942        let map_content: syn::parse::ParseBuffer<'_>;
943        parenthesized!(map_content in input);
944        while !map_content.is_empty() {
945            let key: Type = map_content.parse()?;
946            map_content.parse::<Token![:]>()?;
947            let value: LitInt = map_content.parse()?;
948            map.insert(key, value.base10_parse()?);
949            if map_content.is_empty() {
950                break;
951            }
952            map_content.parse::<Token![,]>()?;
953        }
954        Ok(Self { map })
955    }
956}
957
958impl ToTokens for Referrer {
959    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
960        tokens.extend(quote! {
961            (
962                #(for (key, val) in &self.map), {
963                    #key: #val
964                }
965            )
966        })
967    }
968}
type_leak/lib.rs

type_leak/
lib.rs
