1pub mod inter_visitor;
2pub mod intra_visitor;
3pub mod order;
4pub mod ownership;
5
6use rustc_middle::mir::{Body, Terminator};
7use rustc_middle::ty::{
8 TyCtxt,
9 InstanceKind::Item,
10};
11use rustc_span::def_id::DefId;
12
13use crate::analysis::core::heap_analysis::RawTypeOwner;
14use crate::analysis::core::heap_analysis::{
15 default::TyWithIndex, HAResult,
16};
17use super::{rCanary, IcxMut, IcxSliceMut, Rcx, RcxMut};
18use ownership::{IntraVar, Taint};
19
20use std::{
21 env,
22 fmt::{Debug, Formatter},
23 collections::{HashMap, HashSet}
24};
25
26pub type MirGraph = HashMap<DefId, Graph>;
27pub type ToPo = Vec<usize>;
28pub type Edges = Vec<Vec<usize>>;
29
30#[derive(Debug, Clone)]
31pub struct Graph {
32 e: Edges,
33 pre: Edges,
34 topo: ToPo,
35}
36
37impl Default for Graph {
38 fn default() -> Self {
39 Self {
40 e: Vec::default(),
41 pre: Vec::default(),
42 topo: Vec::default(),
43 }
44 }
45}
46
47impl Graph {
48 pub fn new(len: usize) -> Self {
49 Graph {
50 e: vec![Vec::new(); len],
51 pre: vec![Vec::new(); len],
52 topo: Vec::new(),
53 }
54 }
55
56 pub fn get_edges(&self) -> &Edges {
57 &self.e
58 }
59
60 pub fn get_edges_mut(&mut self) -> &mut Edges {
61 &mut self.e
62 }
63
64 pub fn get_pre(&self) -> &Edges {
65 &self.pre
66 }
67
68 pub fn get_pre_mut(&mut self) -> &mut Edges {
69 &mut self.pre
70 }
71
72 pub fn get_topo(&self) -> &ToPo {
73 &self.topo
74 }
75
76 pub fn get_topo_mut(&mut self) -> &mut ToPo {
77 &mut self.topo
78 }
79}
80
81pub struct FlowAnalysis<'tcx, 'a> {
82 rcx: &'a mut rCanary<'tcx>,
83 fn_set: HashSet<DefId>,
84}
85
86impl<'tcx, 'a> FlowAnalysis<'tcx, 'a> {
87 pub fn new(rcx: &'a mut rCanary<'tcx>) -> Self {
88 Self {
89 rcx,
90 fn_set: HashSet::new(),
91 }
92 }
93
94 pub fn fn_set(&self) -> &HashSet<DefId> {
95 &self.fn_set
96 }
97
98 pub fn fn_set_mut(&mut self) -> &mut HashSet<DefId> {
99 &mut self.fn_set
100 }
101
102 pub fn mir_graph(&self) -> &MirGraph {
103 self.rcx().mir_graph()
104 }
105
106 pub fn mir_graph_mut(&mut self) -> &mut MirGraph {
107 self.rcx_mut().mir_graph_mut()
108 }
109
110 pub fn start(&mut self) {
111 self.order();
114 self.intra_run();
117
118 }
119}
120
121impl<'tcx, 'o, 'a> RcxMut<'tcx, 'o, 'a> for FlowAnalysis<'tcx, 'a> {
122 #[inline(always)]
123 fn rcx(&'o self) -> &'o rCanary<'tcx> {
124 self.rcx
125 }
126
127 #[inline(always)]
128 fn rcx_mut(&'o mut self) -> &'o mut rCanary<'tcx> {
129 &mut self.rcx
130 }
131
132 #[inline(always)]
133 fn tcx(&'o self) -> TyCtxt<'tcx> {
134 self.rcx().tcx()
135 }
136}
137
138#[derive(Clone, Debug)]
139pub struct NodeOrder<'tcx> {
140 body: &'tcx Body<'tcx>,
141 graph: Graph,
142}
143
144impl<'tcx> NodeOrder<'tcx> {
145 pub fn new(body: &'tcx Body<'tcx>) -> Self {
146 let len = body.basic_blocks.len();
147 Self {
148 body,
149 graph: Graph::new(len),
150 }
151 }
152
153 #[inline(always)]
154 pub fn body(&self) -> &'tcx Body<'tcx> {
155 self.body
156 }
157
158 #[inline(always)]
159 pub fn graph(&self) -> &Graph {
160 &self.graph
161 }
162
163 #[inline(always)]
164 pub fn graph_mut(&mut self) -> &mut Graph {
165 &mut self.graph
166 }
167}
168
169struct IntraFlowAnalysis<'tcx, 'ctx, 'a> {
170 pub rcx: &'a rCanary<'tcx>,
171 icx: IntraFlowContext<'tcx, 'ctx>,
172 icx_slice: IcxSliceFroBlock<'tcx, 'ctx>,
173 pub def_id: DefId,
174 pub body: &'a Body<'tcx>,
175 pub graph: &'a Graph,
176 taint_flag: bool,
177 taint_source: Vec<Terminator<'tcx>>,
178}
179
180impl<'tcx, 'ctx, 'a> IntraFlowAnalysis<'tcx, 'ctx, 'a> {
181 pub fn new(
182 rcx: &'a rCanary<'tcx>,
183 def_id: DefId,
184 ) -> Self {
186 let body = rcx.tcx.instance_mir(Item(def_id));
187 let v_len = body.local_decls.len();
188 let b_len = body.basic_blocks.len();
189 let graph = rcx.mir_graph().get(&def_id).unwrap();
190
191 Self {
192 rcx,
193 icx: IntraFlowContext::new(b_len, v_len),
194 icx_slice: IcxSliceFroBlock::new_for_block_0(v_len),
195 def_id,
196 body,
197 graph,
198 taint_flag: false,
199 taint_source: Vec::default(),
200 }
201 }
202
203 pub fn owner(&self) -> &HAResult {
204 self.rcx.adt_owner()
205 }
206
207 pub fn add_taint(&mut self, terminator: Terminator<'tcx>) {
208 self.taint_source.push(terminator);
209 }
210}
211
212impl<'tcx, 'ctx, 'o, 'a> Rcx<'tcx, 'o, 'a> for IntraFlowAnalysis<'tcx, 'ctx, 'a> {
213 #[inline(always)]
214 fn rcx(&'o self) -> &'a rCanary<'tcx> {
215 self.rcx
216 }
217
218 #[inline(always)]
219 fn tcx(&'o self) -> TyCtxt<'tcx> {
220 self.rcx.tcx()
221 }
222}
223
224impl<'tcx, 'ctx, 'o, 'a> IcxMut<'tcx, 'ctx, 'o> for IntraFlowAnalysis<'tcx, 'ctx, 'a> {
225 #[inline(always)]
226 fn icx(&'o self) -> &'o IntraFlowContext<'tcx, 'ctx> {
227 &self.icx
228 }
229
230 #[inline(always)]
231 fn icx_mut(&'o mut self) -> &'o mut IntraFlowContext<'tcx, 'ctx> {
232 &mut self.icx
233 }
234}
235
236impl<'tcx, 'ctx, 'o, 'a> IcxSliceMut<'tcx, 'ctx, 'o> for IntraFlowAnalysis<'tcx, 'ctx, 'a> {
237 #[inline(always)]
238 fn icx_slice(&'o self) -> &'o IcxSliceFroBlock<'tcx, 'ctx> {
239 &self.icx_slice
240 }
241
242 #[inline(always)]
243 fn icx_slice_mut(&'o mut self) -> &'o mut IcxSliceFroBlock<'tcx, 'ctx> {
244 &mut self.icx_slice
245 }
246}
247
248#[derive(Debug, Clone)]
249pub struct IntraFlowContext<'tcx, 'ctx> {
250 taint: IOPairForGraph<Taint<'tcx>>,
251 var: IOPairForGraph<IntraVar<'ctx>>,
252 len: IOPairForGraph<usize>,
253 ty: IOPairForGraph<TyWithIndex<'tcx>>,
256 layout: IOPairForGraph<Vec<RawTypeOwner>>,
257}
258
259impl<'tcx, 'ctx, 'icx> IntraFlowContext<'tcx, 'ctx> {
260 pub fn new(b_len: usize, v_len: usize) -> Self {
261 Self {
262 taint: IOPairForGraph::new(b_len, v_len),
263 var: IOPairForGraph::new(b_len, v_len),
264 len: IOPairForGraph::new(b_len, v_len),
265 ty: IOPairForGraph::new(b_len, v_len),
266 layout: IOPairForGraph::new(b_len, v_len),
267 }
268 }
269
270 pub fn taint(&self) -> &IOPairForGraph<Taint<'tcx>> {
271 &self.taint
272 }
273
274 pub fn taint_mut(&mut self) -> &mut IOPairForGraph<Taint<'tcx>> {
275 &mut self.taint
276 }
277
278 pub fn var(&self) -> &IOPairForGraph<IntraVar<'ctx>> {
279 &self.var
280 }
281
282 pub fn var_mut(&mut self) -> &mut IOPairForGraph<IntraVar<'ctx>> {
283 &mut self.var
284 }
285
286 pub fn len(&self) -> &IOPairForGraph<usize> {
287 &self.len
288 }
289
290 pub fn len_mut(&mut self) -> &mut IOPairForGraph<usize> {
291 &mut self.len
292 }
293
294 pub fn ty(&self) -> &IOPairForGraph<TyWithIndex<'tcx>> {
295 &self.ty
296 }
297
298 pub fn ty_mut(&mut self) -> &mut IOPairForGraph<TyWithIndex<'tcx>> {
299 &mut self.ty
300 }
301
302 pub fn layout(&self) -> &IOPairForGraph<Vec<RawTypeOwner>> {
303 &self.layout
304 }
305
306 pub fn layout_mut(&mut self) -> &mut IOPairForGraph<Vec<RawTypeOwner>> {
307 &mut self.layout
308 }
309
310 pub fn derive_from_pre_node(&mut self, from: usize, to: usize) {
311 *self.taint_mut().get_g_mut()[to].get_i_mut() =
313 self.taint_mut().get_g_mut()[from].get_o_mut().clone();
314
315 *self.var_mut().get_g_mut()[to].get_i_mut() =
317 self.var_mut().get_g_mut()[from].get_o_mut().clone();
318
319 *self.len_mut().get_g_mut()[to].get_i_mut() =
321 self.len_mut().get_g_mut()[from].get_o_mut().clone();
322
323 *self.ty_mut().get_g_mut()[to].get_i_mut() =
325 self.ty_mut().get_g_mut()[from].get_o_mut().clone();
326
327 *self.layout_mut().get_g_mut()[to].get_i_mut() =
329 self.layout_mut().get_g_mut()[from].get_o_mut().clone();
330 }
331
332 pub fn derive_from_icx_slice(&mut self, from: IcxSliceFroBlock<'tcx, 'ctx>, to: usize) {
333 *self.taint_mut().get_g_mut()[to].get_o_mut() = from.taint;
334
335 *self.var_mut().get_g_mut()[to].get_o_mut() = from.var;
336
337 *self.len_mut().get_g_mut()[to].get_o_mut() = from.len;
338
339 *self.ty_mut().get_g_mut()[to].get_o_mut() = from.ty;
340
341 *self.layout_mut().get_g_mut()[to].get_o_mut() = from.layout;
342 }
343}
344
345#[derive(Debug, Clone, Default)]
346pub struct InOutPair<T: Debug + Clone + Default> {
347 i: Vec<T>,
348 o: Vec<T>,
349}
350
351impl<T> InOutPair<T>
352where
353 T: Debug + Clone + Default,
354{
355 pub fn new(len: usize) -> Self {
356 Self {
357 i: vec![T::default(); len],
358 o: vec![T::default(); len],
359 }
360 }
361
362 pub fn get_i(&self) -> &Vec<T> {
363 &self.i
364 }
365
366 pub fn get_o(&self) -> &Vec<T> {
367 &self.o
368 }
369
370 pub fn get_i_mut(&mut self) -> &mut Vec<T> {
371 &mut self.i
372 }
373
374 pub fn get_o_mut(&mut self) -> &mut Vec<T> {
375 &mut self.o
376 }
377
378 pub fn len(&self) -> usize {
379 self.i.len()
380 }
381}
382
383#[derive(Debug, Clone, Default)]
384pub struct IOPairForGraph<T: Debug + Clone + Default> {
385 pair_graph: Vec<InOutPair<T>>,
386}
387
388impl<T> IOPairForGraph<T>
389where
390 T: Debug + Clone + Default,
391{
392 pub fn new(b_len: usize, v_len: usize) -> Self {
393 Self {
394 pair_graph: vec![InOutPair::new(v_len); b_len],
395 }
396 }
397
398 pub fn get_g(&self) -> &Vec<InOutPair<T>> {
399 &self.pair_graph
400 }
401
402 pub fn get_g_mut(&mut self) -> &mut Vec<InOutPair<T>> {
403 &mut self.pair_graph
404 }
405}
406
407#[derive(Clone, Default)]
408pub struct IcxSliceFroBlock<'tcx, 'ctx> {
409 taint: Vec<Taint<'tcx>>,
410 var: Vec<IntraVar<'ctx>>,
411 len: Vec<usize>,
412 ty: Vec<TyWithIndex<'tcx>>,
415 layout: Vec<Vec<RawTypeOwner>>,
416}
417
418impl<'tcx, 'ctx> IcxSliceFroBlock<'tcx, 'ctx> {
419 pub fn new_in(icx: &mut IntraFlowContext<'tcx, 'ctx>, idx: usize) -> Self {
420 Self {
421 taint: icx.taint_mut().get_g_mut()[idx].get_i_mut().clone(),
422 var: icx.var_mut().get_g_mut()[idx].get_i_mut().clone(),
423 len: icx.len_mut().get_g_mut()[idx].get_i_mut().clone(),
424 ty: icx.ty_mut().get_g_mut()[idx].get_i_mut().clone(),
425 layout: icx.layout_mut().get_g_mut()[idx].get_i_mut().clone(),
426 }
427 }
428
429 pub fn new_out(icx: &mut IntraFlowContext<'tcx, 'ctx>, idx: usize) -> Self {
430 Self {
431 taint: icx.taint_mut().get_g_mut()[idx].get_o_mut().clone(),
432 var: icx.var_mut().get_g_mut()[idx].get_o_mut().clone(),
433 len: icx.len_mut().get_g_mut()[idx].get_o_mut().clone(),
434 ty: icx.ty_mut().get_g_mut()[idx].get_o_mut().clone(),
435 layout: icx.layout_mut().get_g_mut()[idx].get_o_mut().clone(),
436 }
437 }
438
439 pub fn new_for_block_0(len: usize) -> Self {
440 Self {
441 taint: vec![Taint::default(); len],
442 var: vec![IntraVar::default(); len],
443 len: vec![0; len],
444 ty: vec![TyWithIndex::default(); len],
445 layout: vec![Vec::new(); len],
446 }
447 }
448
449 pub fn taint(&self) -> &Vec<Taint<'tcx>> {
450 &self.taint
451 }
452
453 pub fn taint_mut(&mut self) -> &mut Vec<Taint<'tcx>> {
454 &mut self.taint
455 }
456
457 pub fn var(&self) -> &Vec<IntraVar<'ctx>> {
458 &self.var
459 }
460
461 pub fn var_mut(&mut self) -> &mut Vec<IntraVar<'ctx>> {
462 &mut self.var
463 }
464
465 pub fn len(&self) -> &Vec<usize> {
466 &self.len
467 }
468
469 pub fn len_mut(&mut self) -> &mut Vec<usize> {
470 &mut self.len
471 }
472
473 pub fn ty(&self) -> &Vec<TyWithIndex<'tcx>> {
474 &self.ty
475 }
476
477 pub fn ty_mut(&mut self) -> &mut Vec<TyWithIndex<'tcx>> {
478 &mut self.ty
479 }
480
481 pub fn layout(&self) -> &Vec<Vec<RawTypeOwner>> {
482 &self.layout
483 }
484
485 pub fn layout_mut(&mut self) -> &mut Vec<Vec<RawTypeOwner>> {
486 &mut self.layout
487 }
488
489 pub fn taint_merge(&mut self, another: &IcxSliceFroBlock<'tcx, 'ctx>, u: usize) {
490 if another.taint()[u].is_untainted() {
491 return;
492 }
493
494 if self.taint()[u].is_untainted() {
495 self.taint_mut()[u] = another.taint()[u].clone();
496 } else {
497 for elem in another.taint()[u].set().clone() {
498 self.taint_mut()[u].insert(elem);
499 }
500 }
501 }
502}
503
504impl<'tcx, 'ctx> Debug for IcxSliceFroBlock<'tcx, 'ctx> {
505 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
506 write!(
507 f,
508 "IcxSliceForBlock\n {:?}\n {:?}\n {:?}\n {:?}\n {:?}",
509 self.taint(),
510 self.len(),
511 self.var(),
512 self.layout(),
513 self.ty(),
514 )
515 }
516}
517
518#[derive(Debug, Copy, Clone, Hash)]
519pub enum Z3GoalDisplay {
520 Verbose,
521 Disabled,
522}
523
524pub fn is_z3_goal_verbose() -> bool {
525 match env::var_os("Z3") {
526 Some(_) => true,
527 _ => false,
528 }
529}
530
531#[derive(Debug, Copy, Clone, Hash)]
532pub enum IcxSliceDisplay {
533 Verbose,
534 Disabled,
535}
536
537pub fn is_icx_slice_verbose() -> bool {
538 match env::var_os("ICX_SLICE") {
539 Some(_) => true,
540 _ => false,
541 }
542}