rapx/analysis/core/heap_analysis/
default.rs

1use rustc_abi::VariantIdx;
2use rustc_middle::{
3    mir::{
4        visit::{TyContext, Visitor},
5        BasicBlock, BasicBlockData, Body, Local, LocalDecl, Operand, TerminatorKind,
6    },
7    ty::{
8        self, EarlyBinder, GenericArgKind, InstanceKind::Item, Ty, TyCtxt, TyKind,
9        TypeSuperVisitable, TypeVisitable, TypeVisitor,
10    },
11};
12use rustc_span::def_id::DefId;
13use std::{collections::HashMap, ops::ControlFlow};
14
15use super::*;
16use crate::rap_debug;
17
18pub struct DefaultHeapAnalysis<'tcx> {
19    tcx: TyCtxt<'tcx>,
20    adt_heap: HAResult,
21    fn_set: HashSet<DefId>,
22    ty_map: HashMap<Ty<'tcx>, String>,
23    adt_recorder: HashSet<DefId>,
24}
25
26impl<'tcx> Analysis for DefaultHeapAnalysis<'tcx> {
27    fn name(&self) -> &'static str {
28        "Default heap analysis."
29    }
30    fn run(&mut self) {
31        self.start();
32    }
33    fn reset(&mut self) {
34        todo!();
35    }
36}
37
38impl<'tcx> HeapAnalysis for DefaultHeapAnalysis<'tcx> {
39    fn get_all_items(&mut self) -> HAResult {
40        self.adt_heap.clone()
41    }
42}
43
44// This function is aiming at resolving problems due to 'TyContext' not implementing 'Clone' trait,
45// thus we call function 'copy_ty_context' to simulate 'self.clone()'.
46#[inline(always)]
47pub(crate) fn copy_ty_context(tc: &TyContext) -> TyContext {
48    match tc {
49        TyContext::LocalDecl { local, source_info } => TyContext::LocalDecl {
50            local: local.clone(),
51            source_info: source_info.clone(),
52        },
53        _ => unreachable!(),
54    }
55}
56
57impl<'tcx> DefaultHeapAnalysis<'tcx> {
58    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
59        Self {
60            tcx,
61            adt_heap: HashMap::default(),
62            fn_set: HashSet::new(),
63            ty_map: HashMap::new(),
64            adt_recorder: HashSet::new(),
65        }
66    }
67
68    pub fn ty_map(&self) -> &HashMap<Ty<'tcx>, String> {
69        &self.ty_map
70    }
71
72    pub fn ty_map_mut(&mut self) -> &mut HashMap<Ty<'tcx>, String> {
73        &mut self.ty_map
74    }
75
76    pub fn fn_set(&self) -> &HashSet<DefId> {
77        &self.fn_set
78    }
79
80    pub fn fn_set_mut(&mut self) -> &mut HashSet<DefId> {
81        &mut self.fn_set
82    }
83
84    pub fn adt_recorder(&self) -> &HashSet<DefId> {
85        &self.adt_recorder
86    }
87
88    pub fn adt_recorder_mut(&mut self) -> &mut HashSet<DefId> {
89        &mut self.adt_recorder
90    }
91
92    pub fn adt_heap(&self) -> &HAResult {
93        &self.adt_heap
94    }
95
96    pub fn adt_heap_mut(&mut self) -> &mut HAResult {
97        &mut self.adt_heap
98    }
99
100    pub fn format_heap_unit(unit: &(HeapInfo, Vec<bool>)) -> String {
101        let (heap, flags) = unit;
102        let vec_str = flags
103            .iter()
104            .map(|&b| if b { "1" } else { "0" })
105            .collect::<Vec<_>>()
106            .join(",");
107        format!("({}, [{}])", heap, vec_str)
108    }
109
110    pub fn output(&mut self) {
111        for elem in self.adt_heap() {
112            let name = format!("{:?}", EarlyBinder::skip_binder(self.tcx.type_of(*elem.0)));
113            let owning = elem
114                .1
115                .iter()
116                .map(Self::format_heap_unit)
117                .collect::<Vec<_>>()
118                .join(", ");
119            rap_info!("{} {}", name, owning);
120        }
121    }
122
123    // From the top-down method of our approach, this 'visitor' is the set of several sub-phases
124    // which means it contains multiple sub-visitors to make whole method 'self.visitor()' work.
125    //
126    // For example, given an adtef (like Vec<T>), the result of 'visitor' contains two parts:
127    //
128    //     pt1 Enum:  {True / UnTrue} indicates whether it will directly have a heap data
129    //     pt2 Array: [bool;N] indicates whether each generic parameter will have a raw param
130    //
131    // Those 2 parts can accelerate heap-heap inference in the data-flow analysis.
132    pub fn start(&mut self) {
133        #[inline(always)]
134        fn start_channel<M>(mut method: M, v_did: &Vec<DefId>)
135        where
136            M: FnMut(DefId) -> (),
137        {
138            for did in v_did {
139                method(*did);
140            }
141        }
142
143        #[inline(always)]
144        fn show_heap(ref_type_analysis: &mut DefaultHeapAnalysis) {
145            for elem in ref_type_analysis.adt_heap() {
146                let name = format!(
147                    "{:?}",
148                    EarlyBinder::skip_binder(ref_type_analysis.tcx.type_of(*elem.0))
149                );
150                let owning = format!("{:?}", elem.1);
151                rap_debug!("ADT analysis: {} {}", name, owning);
152            }
153        }
154
155        // Get the Global TyCtxt from rustc
156        // Grasp all mir Keys defined in current crate
157        let tcx = self.tcx;
158        let mir_keys = tcx.mir_keys(());
159
160        for each_mir in mir_keys {
161            // Get the defid of current crate and get mir Body through this id
162            let def_id = each_mir.to_def_id();
163            let body = tcx.instance_mir(Item(def_id));
164
165            // Insert the defid to hashset if is not existed and visit the body
166            if self.fn_set_mut().insert(def_id) {
167                self.visit_body(body);
168            } else {
169                continue;
170            }
171        }
172
173        let dids: Vec<DefId> = self.adt_recorder.iter().map(|did| *did).collect();
174
175        start_channel(|did| self.extract_raw_generic(did), &dids);
176        start_channel(|did| self.extract_raw_generic_prop(did), &dids);
177        start_channel(|did| self.extract_phantom_unit(did), &dids);
178        start_channel(|did| self.extract_heap_prop(did), &dids);
179
180        show_heap(self);
181    }
182
183    // Extract params in adt types, the 'param' means one generic parameter acting like 'T', 'A', etc...
184    // In the sub-visitor RawGeneric, it will visit the given type recursively, and extract all params.
185    //
186    // Note that RAP is only interested in 'raw' params ('T' not like '*mut T').
187    // It lies in 'one-entire field' | recursive in tuple | recursive in array | mixed before
188    //
189    // Given a struct Example<A, B, T, S>:
190    //
191    // struct Example<A, B, T, S> {
192    //     a: A,
193    //     b: (i32, (f64, B)),
194    //     c: [[(S) ; 1] ; 2],
195    //     d: Vec<T>,
196    // }
197    //
198    // the final result for <A, B, T, S> is <true, true, false, true>.
199    #[inline(always)]
200    fn extract_raw_generic(&mut self, did: DefId) {
201        // Get the definition and subset reference from adt did
202        let ty = EarlyBinder::skip_binder(self.tcx.type_of(did));
203        let (adt_def, substs) = match ty.kind() {
204            TyKind::Adt(adt_def, substs) => (adt_def, substs),
205            _ => unreachable!(),
206        };
207
208        let mut v_res = Vec::new();
209
210        for variant in adt_def.variants().iter() {
211            let mut raw_generic = IsolatedParam::new(substs.len());
212
213            for field in &variant.fields {
214                let field_ty = field.ty(self.tcx, substs);
215                let _ = field_ty.visit_with(&mut raw_generic);
216            }
217            v_res.push((HeapInfo::False, raw_generic.record_mut().clone()));
218        }
219
220        self.adt_heap_mut().insert(did, v_res);
221    }
222
223    // Extract all params in the adt types like param 'T' and then propagate from the bottom to top.
224    // This procedural is the successor of `extract_raw_generic`, and the main idea of RawGenericPropagation
225    // is to propagate params from bottom adt to the top as well as updating Analysis Context.
226    //
227    // Note that it will thorough consider mono-morphization existed in adt-def.
228    // That means the type 'Vec<T>', 'Vec<Vec<T>>' and 'Vec<i32>' are totally different!!!!
229    //
230    // Given a struct Example<A, B, T, S>:
231    //
232    // struct X<A> {
233    //     a: A,
234    // }
235    // the final result for <A> is <true>.
236    //
237    // struct Y1<B> {
238    //     a: (i32, (f64, B)),
239    //     b: X<i32>,
240    // }
241    // the final result for <B> is <true>.
242    //
243    // struct Example<A, B, T, S> {
244    //     a: X<A>,
245    //     b: (i32, (f64, B)),
246    //     c: [[(S) ; 1] ; 2],
247    //     d: Vec<T>,
248    // }
249    //
250    // the final result for <A, B, T, S> is <true, true, false, true>.
251    #[inline(always)]
252    fn extract_raw_generic_prop(&mut self, did: DefId) {
253        // Get the definition and subset reference from adt did
254        let ty = EarlyBinder::skip_binder(self.tcx.type_of(did));
255        let (adt_def, substs) = match ty.kind() {
256            TyKind::Adt(adt_def, substs) => (adt_def, substs),
257            _ => unreachable!(),
258        };
259
260        let source_enum = adt_def.is_enum();
261
262        let mut v_res = self.adt_heap_mut().get_mut(&did).unwrap().clone();
263
264        for (variant_index, variant) in adt_def.variants().iter().enumerate() {
265            let res = v_res[variant_index as usize].clone();
266
267            let mut raw_generic_prop = IsolatedParamPropagation::new(
268                self.tcx,
269                res.1.clone(),
270                source_enum,
271                self.adt_heap(),
272            );
273
274            for field in &variant.fields {
275                let field_ty = field.ty(self.tcx, substs);
276                let _ = field_ty.visit_with(&mut raw_generic_prop);
277            }
278            v_res[variant_index as usize] =
279                (HeapInfo::False, raw_generic_prop.record_mut().clone());
280        }
281
282        self.adt_heap_mut().insert(did, v_res);
283    }
284
285    // Extract all types that include PhantomData<T> which T must be a raw Param
286    // Consider these types as a unit to guide the traversal over adt types
287    #[inline(always)]
288    fn extract_phantom_unit(&mut self, did: DefId) {
289        // Get ty from defid and the ty is made up with generic type
290        let ty = EarlyBinder::skip_binder(self.tcx.type_of(did));
291        let (adt_def, substs) = match ty.kind() {
292            TyKind::Adt(adt_def, substs) => (adt_def, substs),
293            _ => unreachable!(),
294        };
295
296        // As for one heap-allocation unit, only struct will contains the information that we want
297        // Example:
298        // struct Foo<T> {
299        //     NonNull<T>,      // this indicates a pointer
300        //     PhantomData<T>,  // this indicates a heap
301        // }
302        if adt_def.is_struct() {
303            let mut res = self.adt_heap_mut().get_mut(&did).unwrap()[0].clone();
304            // Extract all fields in one given struct
305            for field in adt_def.all_fields() {
306                let field_ty = field.ty(self.tcx, substs);
307                match field_ty.kind() {
308                    // Filter the field which is also a struct due to PhantomData<T> is struct
309                    TyKind::Adt(field_adt_def, field_substs) => {
310                        if field_adt_def.is_phantom_data() {
311                            // Extract all generic args in the type
312                            for generic_arg in *field_substs {
313                                match generic_arg.kind() {
314                                    GenericArgKind::Type(g_ty) => {
315                                        let mut raw_generic_field_subst =
316                                            IsolatedParamFieldSubst::new();
317                                        let _ = g_ty.visit_with(&mut raw_generic_field_subst);
318                                        if raw_generic_field_subst.contains_param() {
319                                            {
320                                                // To enhance the soundness of phantom unit, the struct should have a
321                                                // pointer to store T
322                                                let mut has_ptr = false;
323                                                for field in adt_def.all_fields() {
324                                                    let field_ty = field.ty(self.tcx, substs);
325                                                    let mut find_ptr = FindPtr::new(self.tcx);
326                                                    let _ = field_ty.visit_with(&mut find_ptr);
327                                                    if find_ptr.has_ptr() {
328                                                        has_ptr = true;
329                                                        break;
330                                                    }
331                                                }
332                                                if has_ptr == false {
333                                                    return;
334                                                }
335                                            }
336
337                                            res.0 = HeapInfo::True;
338                                            self.adt_heap_mut().insert(did, vec![res.clone()]);
339                                            return;
340                                        }
341                                    }
342                                    GenericArgKind::Lifetime(..) => {
343                                        return;
344                                    }
345                                    GenericArgKind::Const(..) => {
346                                        return;
347                                    }
348                                }
349                            }
350                        }
351                    }
352                    _ => continue,
353                }
354            }
355        }
356    }
357
358    #[inline(always)]
359    fn extract_heap_prop(&mut self, did: DefId) {
360        // Get the definition and subset reference from adt did
361        let ty = EarlyBinder::skip_binder(self.tcx.type_of(did));
362        let (adt_def, substs) = match ty.kind() {
363            TyKind::Adt(adt_def, substs) => (adt_def, substs),
364            _ => unreachable!(),
365        };
366
367        let mut v_res = self.adt_heap_mut().get_mut(&did).unwrap().clone();
368
369        for (variant_index, variant) in adt_def.variants().iter().enumerate() {
370            let res = v_res[variant_index as usize].clone();
371
372            let mut heap_prop = HeapPropagation::new(self.tcx, res.0, self.adt_heap());
373
374            for field in &variant.fields {
375                let field_ty = field.ty(self.tcx, substs);
376                let _ = field_ty.visit_with(&mut heap_prop);
377            }
378            v_res[variant_index as usize].0 = heap_prop.heap();
379        }
380
381        self.adt_heap_mut().insert(did, v_res);
382    }
383}
384
385impl<'tcx> Visitor<'tcx> for DefaultHeapAnalysis<'tcx> {
386    fn visit_body(&mut self, body: &Body<'tcx>) {
387        for (local, local_decl) in body.local_decls.iter().enumerate() {
388            self.visit_local_decl(Local::from(local), local_decl);
389        }
390
391        for (block, data) in body.basic_blocks.iter().enumerate() {
392            self.visit_basic_block_data(BasicBlock::from(block), data);
393        }
394    }
395
396    fn visit_basic_block_data(&mut self, _block: BasicBlock, data: &BasicBlockData<'tcx>) {
397        let term = data.terminator();
398        match &term.kind {
399            TerminatorKind::Call { func, .. } => match func {
400                Operand::Constant(constant) => match constant.ty().kind() {
401                    ty::FnDef(def_id, ..) => {
402                        if self.tcx.is_mir_available(*def_id) && self.fn_set_mut().insert(*def_id) {
403                            let body = self.tcx.instance_mir(Item(*def_id));
404                            self.visit_body(body);
405                        }
406                    }
407                    _ => (),
408                },
409                _ => (),
410            },
411            _ => (),
412        }
413    }
414
415    fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
416        match ty.kind() {
417            TyKind::Adt(adtdef, substs) => {
418                if self.ty_map().get(&ty).is_some() {
419                    return;
420                }
421                self.ty_map_mut().insert(ty, format!("{:?}", ty));
422                self.adt_recorder_mut().insert(adtdef.did());
423
424                for field in adtdef.all_fields() {
425                    self.visit_ty(field.ty(self.tcx, substs), copy_ty_context(&ty_context))
426                }
427
428                for ty in substs.types() {
429                    self.visit_ty(ty, copy_ty_context(&ty_context));
430                }
431            }
432            TyKind::Array(ty, ..) => {
433                self.visit_ty(*ty, ty_context);
434            }
435            TyKind::Slice(ty) => {
436                self.visit_ty(*ty, ty_context);
437            }
438            TyKind::RawPtr(ty, _) => {
439                self.visit_ty(*ty, ty_context);
440            }
441            TyKind::Ref(_, ty, ..) => {
442                self.visit_ty(*ty, ty_context);
443            }
444            TyKind::Tuple(tuple_fields) => {
445                for field in tuple_fields.iter() {
446                    self.visit_ty(field, copy_ty_context(&ty_context));
447                }
448            }
449            _ => return,
450        }
451    }
452
453    fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
454        let ty_context = TyContext::LocalDecl {
455            local,
456            source_info: local_decl.source_info,
457        };
458        self.visit_ty(local_decl.ty, ty_context);
459    }
460}
461
462impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for IsolatedParam {
463    type Result = ControlFlow<()>;
464    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
465        match ty.kind() {
466            TyKind::Array(..) => ty.super_visit_with(self),
467            TyKind::Tuple(..) => ty.super_visit_with(self),
468            TyKind::Param(param_ty) => {
469                self.record_mut()[param_ty.index as usize] = true;
470                ControlFlow::Continue(())
471            }
472            _ => ControlFlow::Continue(()),
473        }
474    }
475}
476
477impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for IsolatedParamFieldSubst {
478    type Result = ControlFlow<()>;
479    #[inline(always)]
480    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
481        match ty.kind() {
482            TyKind::Array(..) => ty.super_visit_with(self),
483            TyKind::Tuple(..) => ty.super_visit_with(self),
484            TyKind::Adt(..) => ty.super_visit_with(self),
485            TyKind::Param(param_ty) => {
486                self.parameters_mut().insert(param_ty.index as usize);
487                ControlFlow::Continue(())
488            }
489            _ => ControlFlow::Continue(()),
490        }
491    }
492}
493
494impl<'tcx, 'a> TypeVisitor<TyCtxt<'tcx>> for IsolatedParamPropagation<'tcx, 'a> {
495    // #[inline(always)]
496    // fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
497    //     Some(self.tcx)
498    // }
499    type Result = ControlFlow<()>;
500
501    #[inline(always)]
502    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
503        match ty.kind() {
504            TyKind::Adt(adtdef, substs) => {
505                if substs.len() == 0 {
506                    return ControlFlow::Break(());
507                }
508
509                if !self.source_enum() && adtdef.is_enum() {
510                    return ControlFlow::Break(());
511                }
512
513                if !self.unique_mut().insert(adtdef.did()) {
514                    return ControlFlow::Continue(());
515                }
516
517                let mut map_raw_generic_field_subst = HashMap::new();
518                for (index, subst) in substs.iter().enumerate() {
519                    match subst.kind() {
520                        GenericArgKind::Lifetime(..) => continue,
521                        GenericArgKind::Const(..) => continue,
522                        GenericArgKind::Type(g_ty) => {
523                            let mut raw_generic_field_subst = IsolatedParamFieldSubst::new();
524                            let _ = g_ty.visit_with(&mut raw_generic_field_subst);
525                            if !raw_generic_field_subst.contains_param() {
526                                continue;
527                            }
528                            map_raw_generic_field_subst
529                                .insert(index as usize, raw_generic_field_subst);
530                        }
531                    }
532                }
533                if map_raw_generic_field_subst.is_empty() {
534                    return ControlFlow::Break(());
535                }
536
537                let get_ans = self.heap().get(&adtdef.did()).unwrap();
538                if get_ans.len() == 0 {
539                    return ControlFlow::Break(());
540                }
541                let get_ans = get_ans[0].clone();
542
543                for (index, flag) in get_ans.1.iter().enumerate() {
544                    if *flag && map_raw_generic_field_subst.contains_key(&index) {
545                        for elem in map_raw_generic_field_subst
546                            .get(&index)
547                            .unwrap()
548                            .parameters()
549                        {
550                            self.record[*elem] = true;
551                        }
552                    }
553                }
554
555                for field in adtdef.all_fields() {
556                    let field_ty = field.ty(self.tcx, substs);
557                    let _ = field_ty.visit_with(self);
558                }
559
560                self.unique_mut().remove(&adtdef.did());
561
562                ty.super_visit_with(self)
563            }
564            TyKind::Array(..) => ty.super_visit_with(self),
565            TyKind::Tuple(..) => ty.super_visit_with(self),
566            _ => ControlFlow::Continue(()),
567        }
568    }
569}
570
571impl<'tcx, 'a> TypeVisitor<TyCtxt<'tcx>> for HeapPropagation<'tcx, 'a> {
572    // #[inline(always)]
573    // fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
574    //     Some(self.tcx)
575    // }
576    type Result = ControlFlow<()>;
577    #[inline(always)]
578    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
579        match ty.kind() {
580            TyKind::Adt(adtdef, substs) => {
581                if !self.unique_mut().insert(adtdef.did()) {
582                    return ControlFlow::Continue(());
583                }
584
585                if adtdef.is_enum() {
586                    return ControlFlow::Break(());
587                }
588
589                let get_ans = self.heap_res().get(&adtdef.did()).unwrap();
590                if get_ans.len() == 0 {
591                    return ControlFlow::Break(());
592                }
593                let get_ans = get_ans[0].clone();
594
595                match get_ans.0 {
596                    HeapInfo::True => {
597                        self.heap = HeapInfo::True;
598                        return ControlFlow::Break(());
599                    }
600                    _ => (),
601                };
602
603                for field in adtdef.all_fields() {
604                    let field_ty = field.ty(self.tcx, substs);
605                    let _ = field_ty.visit_with(self);
606                }
607
608                self.unique_mut().remove(&adtdef.did());
609
610                ty.super_visit_with(self)
611            }
612            TyKind::Array(..) => ty.super_visit_with(self),
613            TyKind::Tuple(..) => ty.super_visit_with(self),
614            _ => ControlFlow::Continue(()),
615        }
616    }
617}
618
619impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for FindPtr<'tcx> {
620    type Result = ControlFlow<()>;
621    #[inline(always)]
622    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
623        match ty.kind() {
624            TyKind::Adt(adtdef, substs) => {
625                if adtdef.is_struct() {
626                    if !self.unique_mut().insert(adtdef.did()) {
627                        return ControlFlow::Continue(());
628                    }
629
630                    for field in adtdef.all_fields() {
631                        let field_ty = field.ty(self.tcx, substs);
632                        let _ = field_ty.visit_with(self);
633                    }
634                    self.unique_mut().remove(&adtdef.did());
635                }
636                ControlFlow::Continue(())
637            }
638            TyKind::Tuple(..) => ty.super_visit_with(self),
639            TyKind::RawPtr(..) => {
640                self.set_ptr(true);
641                ControlFlow::Break(())
642            }
643            TyKind::Ref(..) => {
644                self.set_ptr(true);
645                ControlFlow::Break(())
646            }
647            _ => ControlFlow::Continue(()),
648        }
649    }
650}
651
652impl<'tcx, 'a> TypeVisitor<TyCtxt<'tcx>> for DefaultOwnership<'tcx, 'a> {
653    // #[inline(always)]
654    // fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
655    //     Some(self.tcx)
656    // }
657    type Result = ControlFlow<()>;
658    #[inline(always)]
659    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
660        match ty.kind() {
661            TyKind::Adt(adtdef, substs) => {
662                if adtdef.is_enum() {
663                    return ControlFlow::Break(());
664                }
665
666                if !self.unique_mut().insert(adtdef.did()) {
667                    return ControlFlow::Continue(());
668                }
669
670                let get_ans = self.heap().get(&adtdef.did()).unwrap();
671
672                // handle the secene of Zero Sized Types
673                if get_ans.len() == 0 {
674                    return ControlFlow::Break(());
675                }
676                let (unit_res, generic_list) = get_ans[0].clone();
677
678                match unit_res {
679                    HeapInfo::True => {
680                        self.set_res(HeapInfo::True);
681                        return ControlFlow::Break(());
682                    }
683                    HeapInfo::False => {
684                        for (index, each_generic) in generic_list.iter().enumerate() {
685                            if *each_generic == false {
686                                continue;
687                            } else {
688                                let subset_ty = substs[index].expect_ty();
689                                self.unique_mut().remove(&adtdef.did());
690                                let _ = subset_ty.visit_with(self);
691                            }
692                        }
693                    }
694                    _ => {
695                        unreachable!();
696                    }
697                }
698                ControlFlow::Continue(())
699            }
700            TyKind::Array(..) => ty.super_visit_with(self),
701            TyKind::Tuple(..) => ty.super_visit_with(self),
702            TyKind::Param(..) => {
703                self.set_param(true);
704                self.set_res(HeapInfo::True);
705                ControlFlow::Break(())
706            }
707            TyKind::RawPtr(..) => {
708                self.set_ptr(true);
709                ControlFlow::Continue(())
710            }
711            TyKind::Ref(..) => {
712                self.set_ptr(true);
713                ControlFlow::Continue(())
714            }
715            _ => ControlFlow::Continue(()),
716        }
717    }
718}
719
720#[derive(Debug, Clone, Hash, Eq, PartialEq, Default)]
721pub struct TyWithIndex<'tcx>(pub Option<(usize, &'tcx TyKind<'tcx>, Option<usize>, bool)>);
722
723impl<'tcx> TyWithIndex<'tcx> {
724    pub fn new(ty: Ty<'tcx>, vidx: Option<VariantIdx>) -> Self {
725        match &ty.kind() {
726            TyKind::Tuple(list) => TyWithIndex(Some((list.len(), &ty.kind(), None, true))),
727            TyKind::Adt(adtdef, ..) => {
728                if adtdef.is_enum() {
729                    if vidx.is_none() {
730                        return TyWithIndex(None);
731                    }
732                    let idx = vidx.unwrap();
733                    let len = adtdef.variants()[idx].fields.len();
734                    TyWithIndex(Some((len, &ty.kind(), Some(idx.index()), true)))
735                } else {
736                    let len = adtdef.variants()[VariantIdx::from_usize(0)].fields.len();
737                    TyWithIndex(Some((len, &ty.kind(), None, true)))
738                }
739            }
740            TyKind::Array(..) | TyKind::Param(..) | TyKind::RawPtr(..) | TyKind::Ref(..) => {
741                TyWithIndex(Some((1, &ty.kind(), None, true)))
742            }
743            TyKind::Bool
744            | TyKind::Char
745            | TyKind::Int(..)
746            | TyKind::Uint(..)
747            | TyKind::Float(..)
748            | TyKind::Str
749            | TyKind::Slice(..) => TyWithIndex(Some((1, &ty.kind(), None, false))),
750            _ => TyWithIndex(None),
751        }
752    }
753
754    // 0->unsupported, 1->trivial, 2-> needed
755    pub fn get_priority(&self) -> usize {
756        if self.0.is_none() {
757            return 0;
758        }
759        match self.0.unwrap().0 {
760            0 => 1,
761            _ => match self.0.unwrap().3 {
762                true => 2,
763                false => 1,
764            },
765        }
766    }
767}
768
769#[derive(Copy, Clone, Debug)]
770pub struct Encoder;
771
772impl<'tcx> Encoder {
773    pub fn encode(
774        tcx: TyCtxt<'tcx>,
775        ty: Ty<'tcx>,
776        adt_heap: HAResult,
777        variant: Option<VariantIdx>,
778    ) -> OwnershipLayoutResult {
779        match ty.kind() {
780            TyKind::Array(..) => {
781                let mut res = OwnershipLayoutResult::new();
782                let mut default_heap = DefaultOwnership::new(tcx, &adt_heap);
783
784                let _ = ty.visit_with(&mut default_heap);
785                res.update_from_default_heap_visitor(&mut default_heap);
786
787                res
788            }
789            TyKind::Tuple(tuple_ty_list) => {
790                let mut res = OwnershipLayoutResult::new();
791
792                for tuple_ty in tuple_ty_list.iter() {
793                    let mut default_heap = DefaultOwnership::new(tcx, &adt_heap);
794
795                    let _ = tuple_ty.visit_with(&mut default_heap);
796                    res.update_from_default_heap_visitor(&mut default_heap);
797                }
798
799                res
800            }
801            TyKind::Adt(adtdef, substs) => {
802                // check the ty is or is not an enum and the variant of this enum is or is not given
803                if adtdef.is_enum() && variant.is_none() {
804                    return OwnershipLayoutResult::new();
805                }
806
807                let mut res = OwnershipLayoutResult::new();
808
809                // check the ty if it is a struct or union
810                if adtdef.is_struct() || adtdef.is_union() {
811                    for field in adtdef.all_fields() {
812                        let field_ty = field.ty(tcx, substs);
813
814                        let mut default_heap = DefaultOwnership::new(tcx, &adt_heap);
815
816                        let _ = field_ty.visit_with(&mut default_heap);
817                        res.update_from_default_heap_visitor(&mut default_heap);
818                    }
819                }
820                // check the ty which is an enum with a exact variant idx
821                else if adtdef.is_enum() {
822                    let vidx = variant.unwrap();
823
824                    for field in &adtdef.variants()[vidx].fields {
825                        let field_ty = field.ty(tcx, substs);
826
827                        let mut default_heap = DefaultOwnership::new(tcx, &adt_heap);
828
829                        let _ = field_ty.visit_with(&mut default_heap);
830                        res.update_from_default_heap_visitor(&mut default_heap);
831                    }
832                }
833                res
834            }
835            TyKind::Param(..) => {
836                let mut res = OwnershipLayoutResult::new();
837                res.set_requirement(true);
838                res.set_param(true);
839                res.set_owned(true);
840                res.layout_mut().push(HeapInfo::True);
841                res
842            }
843            TyKind::RawPtr(..) => {
844                let mut res = OwnershipLayoutResult::new();
845                res.set_requirement(true);
846                res.layout_mut().push(HeapInfo::False);
847                res
848            }
849            TyKind::Ref(..) => {
850                let mut res = OwnershipLayoutResult::new();
851                res.set_requirement(true);
852                res.layout_mut().push(HeapInfo::False);
853                res
854            }
855            _ => OwnershipLayoutResult::new(),
856        }
857    }
858}
859
860#[derive(Clone)]
861struct IsolatedParamFieldSubst {
862    parameters: HashSet<usize>,
863}
864
865impl<'tcx> IsolatedParamFieldSubst {
866    pub fn new() -> Self {
867        Self {
868            parameters: HashSet::new(),
869        }
870    }
871
872    pub fn parameters(&self) -> &HashSet<usize> {
873        &self.parameters
874    }
875
876    pub fn parameters_mut(&mut self) -> &mut HashSet<usize> {
877        &mut self.parameters
878    }
879
880    pub fn contains_param(&self) -> bool {
881        !self.parameters.is_empty()
882    }
883}
884
885#[derive(Clone)]
886struct IsolatedParamPropagation<'tcx, 'a> {
887    tcx: TyCtxt<'tcx>,
888    record: Vec<bool>,
889    unique: HashSet<DefId>,
890    source_enum: bool,
891    ref_adt_heap: &'a HAResult,
892}
893
894impl<'tcx, 'a> IsolatedParamPropagation<'tcx, 'a> {
895    pub fn new(
896        tcx: TyCtxt<'tcx>,
897        record: Vec<bool>,
898        source_enum: bool,
899        ref_adt_heap: &'a HAResult,
900    ) -> Self {
901        Self {
902            tcx,
903            record,
904            unique: HashSet::new(),
905            source_enum,
906            ref_adt_heap,
907        }
908    }
909
910    pub fn record_mut(&mut self) -> &mut Vec<bool> {
911        &mut self.record
912    }
913
914    pub fn unique_mut(&mut self) -> &mut HashSet<DefId> {
915        &mut self.unique
916    }
917
918    pub fn source_enum(&mut self) -> bool {
919        self.source_enum
920    }
921
922    pub fn heap(&self) -> &'a HAResult {
923        self.ref_adt_heap
924    }
925}
926
927#[derive(Clone)]
928struct HeapPropagation<'tcx, 'a> {
929    tcx: TyCtxt<'tcx>,
930    heap: HeapInfo,
931    unique: HashSet<DefId>,
932    heap_res: &'a HAResult,
933}
934
935impl<'tcx, 'a> HeapPropagation<'tcx, 'a> {
936    pub fn new(tcx: TyCtxt<'tcx>, heap: HeapInfo, heap_res: &'a HAResult) -> Self {
937        Self {
938            tcx,
939            heap,
940            unique: HashSet::new(),
941            heap_res,
942        }
943    }
944
945    pub fn heap(&self) -> HeapInfo {
946        self.heap
947    }
948
949    pub fn unique_mut(&mut self) -> &mut HashSet<DefId> {
950        &mut self.unique
951    }
952
953    pub fn heap_res(&self) -> &'a HAResult {
954        self.heap_res
955    }
956}
957
958#[derive(Clone)]
959struct IsolatedParam {
960    record: Vec<bool>,
961}
962
963impl IsolatedParam {
964    pub fn new(len: usize) -> Self {
965        Self {
966            record: vec![false; len],
967        }
968    }
969
970    pub fn record_mut(&mut self) -> &mut Vec<bool> {
971        &mut self.record
972    }
973}
974
975#[derive(Clone)]
976pub struct DefaultOwnership<'tcx, 'a> {
977    tcx: TyCtxt<'tcx>,
978    unique: HashSet<DefId>,
979    ref_adt_heap: &'a HAResult,
980    res: HeapInfo,
981    param: bool,
982    ptr: bool,
983}
984
985impl<'tcx, 'a> DefaultOwnership<'tcx, 'a> {
986    pub fn new(tcx: TyCtxt<'tcx>, ref_adt_heap: &'a HAResult) -> Self {
987        Self {
988            tcx,
989            unique: HashSet::new(),
990            ref_adt_heap,
991            res: HeapInfo::False,
992            param: false,
993            ptr: false,
994        }
995    }
996
997    pub fn tcx(&self) -> TyCtxt<'tcx> {
998        self.tcx
999    }
1000
1001    pub fn unique(&self) -> &HashSet<DefId> {
1002        &self.unique
1003    }
1004
1005    pub fn unique_mut(&mut self) -> &mut HashSet<DefId> {
1006        &mut self.unique
1007    }
1008
1009    pub fn get_res(&self) -> HeapInfo {
1010        self.res
1011    }
1012
1013    pub fn set_res(&mut self, res: HeapInfo) {
1014        self.res = res;
1015    }
1016
1017    pub fn is_owning_true(&self) -> bool {
1018        self.res == HeapInfo::True
1019    }
1020
1021    pub fn get_param(&self) -> bool {
1022        self.param
1023    }
1024
1025    pub fn set_param(&mut self, p: bool) {
1026        self.param = p;
1027    }
1028
1029    pub fn is_param_true(&self) -> bool {
1030        self.param == true
1031    }
1032
1033    pub fn get_ptr(&self) -> bool {
1034        self.ptr
1035    }
1036
1037    pub fn set_ptr(&mut self, p: bool) {
1038        self.ptr = p;
1039    }
1040
1041    pub fn is_ptr_true(&self) -> bool {
1042        self.ptr == true
1043    }
1044
1045    pub fn heap(&self) -> &'a HAResult {
1046        self.ref_adt_heap
1047    }
1048}
1049
1050#[derive(Clone)]
1051pub struct FindPtr<'tcx> {
1052    tcx: TyCtxt<'tcx>,
1053    unique: HashSet<DefId>,
1054    ptr: bool,
1055}
1056
1057impl<'tcx> FindPtr<'tcx> {
1058    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
1059        Self {
1060            tcx,
1061            unique: HashSet::<DefId>::default(),
1062            ptr: false,
1063        }
1064    }
1065
1066    pub fn tcx(&self) -> TyCtxt<'tcx> {
1067        self.tcx
1068    }
1069
1070    pub fn unique(&self) -> &HashSet<DefId> {
1071        &self.unique
1072    }
1073
1074    pub fn unique_mut(&mut self) -> &mut HashSet<DefId> {
1075        &mut self.unique
1076    }
1077
1078    pub fn has_ptr(&self) -> bool {
1079        self.ptr
1080    }
1081
1082    pub fn set_ptr(&mut self, ptr: bool) {
1083        self.ptr = ptr;
1084    }
1085}
1086
1087pub fn is_display_verbose() -> bool {
1088    match env::var_os("ADT_DISPLAY") {
1089        Some(_) => true,
1090        _ => false,
1091    }
1092}
1093
1094#[derive(Debug, Clone, Hash, Eq, PartialEq, Default)]
1095pub struct IndexedTy<'tcx>(pub Option<(usize, &'tcx TyKind<'tcx>, Option<usize>, bool)>);
1096
1097impl<'tcx> IndexedTy<'tcx> {
1098    pub fn new(ty: Ty<'tcx>, vidx: Option<VariantIdx>) -> Self {
1099        match &ty.kind() {
1100            TyKind::Tuple(list) => IndexedTy(Some((list.len(), &ty.kind(), None, true))),
1101            TyKind::Adt(adtdef, ..) => {
1102                if adtdef.is_enum() {
1103                    if vidx.is_none() {
1104                        return IndexedTy(None);
1105                    }
1106                    let idx = vidx.unwrap();
1107                    let len = adtdef.variants()[idx].fields.len();
1108                    IndexedTy(Some((len, &ty.kind(), Some(idx.index()), true)))
1109                } else {
1110                    let len = adtdef.variants()[VariantIdx::from_usize(0)].fields.len();
1111                    IndexedTy(Some((len, &ty.kind(), None, true)))
1112                }
1113            }
1114            TyKind::Array(..) | TyKind::Param(..) | TyKind::RawPtr(..) | TyKind::Ref(..) => {
1115                IndexedTy(Some((1, &ty.kind(), None, true)))
1116            }
1117            TyKind::Bool
1118            | TyKind::Char
1119            | TyKind::Int(..)
1120            | TyKind::Uint(..)
1121            | TyKind::Float(..)
1122            | TyKind::Str
1123            | TyKind::Slice(..) => IndexedTy(Some((1, &ty.kind(), None, false))),
1124            _ => IndexedTy(None),
1125        }
1126    }
1127
1128    // 0->unsupported, 1->trivial, 2-> needed
1129    pub fn get_priority(&self) -> usize {
1130        if self.0.is_none() {
1131            return 0;
1132        }
1133        match self.0.unwrap().0 {
1134            0 => 1,
1135            _ => match self.0.unwrap().3 {
1136                true => 2,
1137                false => 1,
1138            },
1139        }
1140    }
1141}
1142
1143#[derive(Clone, Debug)]
1144pub struct OwnershipLayoutResult {
1145    layout: Vec<HeapInfo>,
1146    param: bool,
1147    requirement: bool,
1148    owned: bool,
1149}
1150
1151impl OwnershipLayoutResult {
1152    pub fn new() -> Self {
1153        Self {
1154            layout: Vec::new(),
1155            param: false,
1156            requirement: false,
1157            owned: false,
1158        }
1159    }
1160
1161    pub fn layout(&self) -> &Vec<HeapInfo> {
1162        &self.layout
1163    }
1164
1165    pub fn layout_mut(&mut self) -> &mut Vec<HeapInfo> {
1166        &mut self.layout
1167    }
1168
1169    pub fn get_param(&self) -> bool {
1170        self.param
1171    }
1172
1173    pub fn set_param(&mut self, p: bool) {
1174        self.param = p;
1175    }
1176
1177    pub fn is_param_true(&self) -> bool {
1178        self.param == true
1179    }
1180
1181    pub fn get_requirement(&self) -> bool {
1182        self.requirement
1183    }
1184
1185    pub fn set_requirement(&mut self, r: bool) {
1186        self.requirement = r;
1187    }
1188
1189    pub fn is_requirement_true(&self) -> bool {
1190        self.requirement == true
1191    }
1192
1193    pub fn is_empty(&self) -> bool {
1194        self.layout.is_empty()
1195    }
1196
1197    pub fn is_owned(&self) -> bool {
1198        self.owned == true
1199    }
1200
1201    pub fn set_owned(&mut self, o: bool) {
1202        self.owned = o;
1203    }
1204
1205    pub fn update_from_default_heap_visitor<'tcx, 'a>(
1206        &mut self,
1207        default_heap: &mut DefaultOwnership<'tcx, 'a>,
1208    ) {
1209        if default_heap.is_owning_true() || default_heap.is_ptr_true() {
1210            self.set_requirement(true);
1211        }
1212
1213        if default_heap.is_owning_true() {
1214            self.set_owned(true);
1215        }
1216
1217        self.layout_mut().push(default_heap.get_res());
1218
1219        self.set_param(default_heap.get_param());
1220    }
1221}
rapx/analysis/core/heap_analysis/default.rs

rapx/analysis/core/heap_analysis/
default.rs
