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        self.reduce_unreachable_nodes();
638        self.reduce_obvious_nodes();
639        // TODO: unobvious root reduction with heaulistics
640    }
641
642    fn reduce_obvious_nodes(&mut self) {
643        let mut must_intern_nodes: Vec<_> = self.must_intern_nodes.iter().cloned().collect();
644        let mut root_nodes: Vec<_> = self.root_nodes.iter().cloned().collect();
645        let nodes: Vec<_> = self
646            .graph
647            .node_indices()
648            .filter_map(|n| {
649                let mut it = self.graph.edges(n.clone());
650                if let Some(edge) = it.next() {
651                    if let None = it.next() {
652                        return Some((edge.source(), edge.target(), edge.id()));
653                    }
654                }
655                None
656            })
657            .collect();
658        let mut removing_nodes = HashSet::new();
659        for (node1, node2, edge) in nodes {
660            self.graph.remove_edge(edge);
661            for (edge_in_source, edge_in) in self
662                .graph
663                .edges_directed(node1, petgraph::Direction::Incoming)
664                .map(|er| (er.source(), er.id()))
665                .collect::<Vec<_>>()
666            {
667                self.graph.update_edge(edge_in_source, node2, ());
668                self.graph.remove_edge(edge_in);
669            }
670            must_intern_nodes.iter_mut().for_each(|n| {
671                if n == &node1 {
672                    *n = node2.clone()
673                }
674            });
675            root_nodes.iter_mut().for_each(|n| {
676                if n == &node1 {
677                    *n = node2.clone()
678                }
679            });
680            removing_nodes.insert(node1);
681        }
682        let mut new_graph = Graph::new();
683        let mut node_map = HashMap::new();
684        for node in self.graph.node_indices() {
685            if !removing_nodes.contains(&node) {
686                let new_node = new_graph.add_node(self.graph[node].clone());
687                node_map.insert(node, new_node);
688            }
689        }
690        for edge in self.graph.edge_indices() {
691            let (n1, n2) = self.graph.edge_endpoints(edge).unwrap();
692            if let (Some(nn1), Some(nn2)) = (node_map.get(&n1), node_map.get(&n2)) {
693                new_graph.add_edge(*nn1, *nn2, ());
694            }
695        }
696        self.root_nodes = root_nodes
697            .iter()
698            .filter_map(|n| node_map.get(n).cloned())
699            .collect();
700        self.must_intern_nodes = must_intern_nodes
701            .iter()
702            .filter_map(|n| node_map.get(n).cloned())
703            .collect();
704        let _ = std::mem::replace(&mut self.graph, new_graph);
705    }
706
707    fn reduce_unreachable_nodes(&mut self) {
708        let reachable_forward = get_reachable_nodes(&self.graph, self.root_nodes.iter().cloned());
709        self.graph.reverse();
710        let reachable_backward =
711            get_reachable_nodes(&self.graph, self.must_intern_nodes.iter().cloned());
712        self.graph.reverse();
713        let reachable = reachable_forward
714            .intersection(&reachable_backward)
715            .cloned()
716            .collect::<HashSet<_>>();
717        // self.graph = self.graph.filter_map(
718        //     |ix, node| reachable.contains(&ix).then_some(node.clone()),
719        //     |ix, _| {
720        //         let (e1, e2) = self.graph.edge_endpoints(ix).unwrap();
721        //         (reachable.contains(&e1) && reachable.contains(&e2)).then_some(())
722        //     },
723        // );
724        let mut new_graph = Graph::new();
725        let mut node_map = HashMap::new();
726        for node in self.graph.node_indices() {
727            if reachable.contains(&node) {
728                let new_node = new_graph.add_node(self.graph[node].clone());
729                node_map.insert(node, new_node);
730            }
731        }
732        for edge in self.graph.edge_indices() {
733            let (n1, n2) = self.graph.edge_endpoints(edge).unwrap();
734            if let (Some(nn1), Some(nn2)) = (node_map.get(&n1), node_map.get(&n2)) {
735                new_graph.add_edge(*nn1, *nn2, ());
736            }
737        }
738        self.root_nodes = self
739            .root_nodes
740            .iter()
741            .filter_map(|n| node_map.get(n).cloned())
742            .collect();
743        self.must_intern_nodes = self
744            .must_intern_nodes
745            .iter()
746            .filter_map(|n| node_map.get(n).cloned())
747            .collect();
748        let _ = std::mem::replace(&mut self.graph, new_graph);
749    }
750}
751
752fn get_reachable_nodes<N, E>(
753    graph: &Graph<N, E>,
754    roots: impl IntoIterator<Item = NodeIndex<DefaultIx>>,
755) -> HashSet<NodeIndex<DefaultIx>> {
756    let mut ret: HashSet<_> = roots.into_iter().collect();
757    let mut frontier = ret.clone();
758    loop {
759        let mut buf: HashSet<_> = frontier
760            .iter()
761            .map(|node| graph.neighbors(node.clone()))
762            .flatten()
763            .collect();
764        let mut count = 0;
765        for node in &buf {
766            if ret.insert(node.clone()) {
767                count += 1;
768            }
769        }
770        if count == 0 {
771            break;
772        }
773        std::mem::swap(&mut frontier, &mut buf);
774    }
775    ret
776}
777
778#[derive(Clone, PartialEq, Eq, Debug)]
779pub struct Referrer {
780    map: HashMap<Type, usize>,
781}
782
783impl Referrer {
784    pub fn is_empty(&self) -> bool {
785        self.map.is_empty()
786    }
787
788    pub fn iter(&self) -> impl Iterator<Item = &Type> {
789        self.map.keys()
790    }
791
792    pub fn into_visitor<F: FnMut(usize) -> Path + Clone>(
793        self,
794        leaker_ty: Type,
795        repeater_path_fn: F,
796    ) -> Visitor<F> {
797        Visitor(self, leaker_ty, repeater_path_fn)
798    }
799
800    pub fn expand(
801        &self,
802        ty: Type,
803        leaker_ty: &Type,
804        repeater_path_fn: impl FnMut(usize) -> Path,
805    ) -> Type {
806        use syn::fold::Fold;
807
808        struct Folder<'a, F>(&'a Referrer, &'a Type, F);
809        impl<'a, F: FnMut(usize) -> Path> Fold for Folder<'a, F> {
810            fn fold_type(&mut self, ty: Type) -> Type {
811                if let Some(idx) = self.0.map.get(&ty) {
812                    parse2(quote! {
813                        <#{&self.1} as #{&self.2(*idx)}>::Type
814                    })
815                    .unwrap()
816                } else {
817                    syn::fold::fold_type(self, ty)
818                }
819            }
820        }
821        let mut folder = Folder(self, leaker_ty, repeater_path_fn);
822        folder.fold_type(ty)
823    }
824}
825
826#[derive(Clone, Debug)]
827pub struct Visitor<F>(Referrer, Type, F);
828
829impl<F: FnMut(usize) -> Path + Clone> Visitor<F> {
830    fn with_generics(&mut self, generics: &mut Generics) -> Self {
831        let mut visitor = self.clone();
832        for gp in generics.params.iter_mut() {
833            if let GenericParam::Type(TypeParam { ident, .. }) = gp {
834                visitor.0.map.remove(&parse_quote!(#ident));
835            }
836            visitor.visit_generic_param_mut(gp);
837        }
838        visitor
839    }
840
841    fn with_signature(&mut self, sig: &mut Signature) -> Self {
842        let mut visitor = self.with_generics(&mut sig.generics);
843        for input in sig.inputs.iter_mut() {
844            visitor.visit_fn_arg_mut(input);
845        }
846        visitor.visit_return_type_mut(&mut sig.output);
847        visitor
848    }
849}
850
851impl<F: FnMut(usize) -> Path + Clone> VisitMut for Visitor<F> {
852    fn visit_type_mut(&mut self, i: &mut Type) {
853        *i = self.0.expand(i.clone(), &self.1, &mut self.2);
854    }
855    fn visit_item_struct_mut(&mut self, i: &mut ItemStruct) {
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        visitor.visit_fields_mut(&mut i.fields);
861    }
862    fn visit_item_enum_mut(&mut self, i: &mut ItemEnum) {
863        for attr in i.attrs.iter_mut() {
864            self.visit_attribute_mut(attr);
865        }
866        let mut visitor = self.with_generics(&mut i.generics);
867        for variant in i.variants.iter_mut() {
868            visitor.visit_variant_mut(variant);
869        }
870    }
871    fn visit_item_trait_mut(&mut self, i: &mut ItemTrait) {
872        for attr in i.attrs.iter_mut() {
873            self.visit_attribute_mut(attr);
874        }
875        let mut visitor = self.with_generics(&mut i.generics);
876        for supertrait in i.supertraits.iter_mut() {
877            visitor.visit_type_param_bound_mut(supertrait);
878        }
879        for item in i.items.iter_mut() {
880            visitor.visit_trait_item_mut(item);
881        }
882    }
883    fn visit_item_union_mut(&mut self, i: &mut ItemUnion) {
884        for attr in i.attrs.iter_mut() {
885            self.visit_attribute_mut(attr);
886        }
887        let mut visitor = self.with_generics(&mut i.generics);
888        visitor.visit_fields_named_mut(&mut i.fields);
889    }
890    fn visit_item_type_mut(&mut self, i: &mut ItemType) {
891        for attr in i.attrs.iter_mut() {
892            self.visit_attribute_mut(attr);
893        }
894        let mut visitor = self.with_generics(&mut i.generics);
895        visitor.visit_type_mut(&mut i.ty);
896    }
897    fn visit_item_fn_mut(&mut self, i: &mut ItemFn) {
898        for attr in i.attrs.iter_mut() {
899            self.visit_attribute_mut(attr);
900        }
901        let mut visitor = self.with_signature(&mut i.sig);
902        visitor.visit_block_mut(i.block.as_mut());
903    }
904    fn visit_trait_item_fn_mut(&mut self, i: &mut TraitItemFn) {
905        for attr in i.attrs.iter_mut() {
906            self.visit_attribute_mut(attr);
907        }
908        let mut visitor = self.with_signature(&mut i.sig);
909        if let Some(block) = &mut i.default {
910            visitor.visit_block_mut(block);
911        }
912    }
913    fn visit_trait_item_type_mut(&mut self, i: &mut TraitItemType) {
914        for attr in i.attrs.iter_mut() {
915            self.visit_attribute_mut(attr);
916        }
917        let mut visitor = self.with_generics(&mut i.generics);
918        for bound in i.bounds.iter_mut() {
919            visitor.visit_type_param_bound_mut(bound);
920        }
921        if let Some((_, ty)) = &mut i.default {
922            visitor.visit_type_mut(ty);
923        }
924    }
925    fn visit_trait_item_const_mut(&mut self, i: &mut TraitItemConst) {
926        for attr in i.attrs.iter_mut() {
927            self.visit_attribute_mut(attr);
928        }
929        let mut visitor = self.with_generics(&mut i.generics);
930        visitor.visit_type_mut(&mut i.ty);
931        if let Some((_, expr)) = &mut i.default {
932            visitor.visit_expr_mut(expr);
933        }
934    }
935    fn visit_block_mut(&mut self, i: &mut Block) {
936        let mut visitor = self.clone();
937        for stmt in &i.stmts {
938            match stmt {
939                Stmt::Item(Item::Struct(ItemStruct { ident, .. }))
940                | Stmt::Item(Item::Enum(ItemEnum { ident, .. }))
941                | Stmt::Item(Item::Union(ItemUnion { ident, .. }))
942                | Stmt::Item(Item::Trait(ItemTrait { ident, .. }))
943                | Stmt::Item(Item::Type(ItemType { ident, .. })) => {
944                    visitor.0.map.remove(&parse_quote!(#ident));
945                }
946                _ => (),
947            }
948        }
949        for stmt in i.stmts.iter_mut() {
950            visitor.visit_stmt_mut(stmt);
951        }
952    }
953}
954
955impl Parse for Referrer {
956    fn parse(input: parse::ParseStream) -> Result<Self> {
957        let mut map = HashMap::new();
958        let map_content: syn::parse::ParseBuffer<'_>;
959        parenthesized!(map_content in input);
960        while !map_content.is_empty() {
961            let key: Type = map_content.parse()?;
962            map_content.parse::<Token![:]>()?;
963            let value: LitInt = map_content.parse()?;
964            map.insert(key, value.base10_parse()?);
965            if map_content.is_empty() {
966                break;
967            }
968            map_content.parse::<Token![,]>()?;
969        }
970        Ok(Self { map })
971    }
972}
973
974impl ToTokens for Referrer {
975    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
976        tokens.extend(quote! {
977            (
978                #(for (key, val) in &self.map), {
979                    #key: #val
980                }
981            )
982        })
983    }
984}
type_leak/lib.rs

type_leak/
lib.rs
