rapx/analysis/range/domain/constraint_graph/
graph.rs

1use crate::analysis::range::domain::domain::*;
2use crate::analysis::range::{Range, RangeType};
3
4use crate::analysis::range::domain::symbolic_expr::*;
5use crate::compat::Spanned;
6use rustc_abi::FieldIdx;
7use rustc_hir::def_id::DefId;
8use rustc_hir::def_id::LOCAL_CRATE;
9use rustc_index::IndexVec;
10use rustc_middle::{
11    mir::*,
12    ty::{self},
13};
14
15use std::{
16    collections::{HashMap, HashSet},
17    fmt::Debug,
18};
19
20use super::ConstraintGraph;
21
22impl<'tcx, T> ConstraintGraph<'tcx, T>
23where
24    T: IntervalArithmetic + ConstConvert + Debug,
25{
26    fn register_op(&mut self, op: BasicOpKind<'tcx, T>, sink: &'tcx Place<'tcx>) -> usize {
27        let idx = self.oprs.len();
28        self.oprs.push(op);
29        self.defmap.insert(sink, idx);
30        idx
31    }
32
33    pub fn add_varnode(&mut self, v: &'tcx Place<'tcx>) -> &mut VarNode<'tcx, T> {
34        let local_decls = &self.body.local_decls;
35
36        let node = VarNode::new(v);
37        let node_ref: &mut VarNode<'tcx, T> = self.vars.entry(v).or_insert(node);
38        self.usemap.entry(v).or_insert(HashSet::new());
39
40        let ty = local_decls[v.local].ty;
41        let place_ty = v.ty(local_decls, self.tcx);
42
43        if v.projection.is_empty() || self.defmap.contains_key(v) {
44            return node_ref;
45        }
46
47        if !v.projection.is_empty() {
48            let matches: Vec<(_, _)> = self
49                .defmap
50                .iter()
51                .filter(|(p, _)| p.local == v.local && p.projection.is_empty())
52                .map(|(p, def_op)| (*p, *def_op))
53                .collect();
54
55            for (base_place, def_op) in matches {
56                let mut v_op = self.oprs[def_op].clone();
57                v_op.set_sink(v);
58
59                for source in v_op.get_sources() {
60                    self.usemap
61                        .entry(source)
62                        .or_insert(HashSet::new())
63                        .insert(self.oprs.len());
64                }
65
66                self.oprs.push(v_op);
67                self.defmap.insert(v, self.oprs.len() - 1);
68            }
69        }
70
71        node_ref
72    }
73
74    pub fn use_add_varnode_sym(
75        &mut self,
76        v: &'tcx Place<'tcx>,
77        rvalue: &'tcx Rvalue<'tcx>,
78    ) -> &mut VarNode<'tcx, T> {
79        if !self.vars.contains_key(v) {
80            let place_ctx: Vec<&Place<'tcx>> = self.vars.keys().map(|p| *p).collect();
81            let node = VarNode::new_symb(v, SymbExpr::from_rvalue(rvalue, place_ctx.clone()));
82            rap_debug!("use node:{:?}", node);
83
84            self.vars.insert(v, node);
85            self.usemap.entry(v).or_insert(HashSet::new());
86
87            if !(v.projection.is_empty() || self.defmap.contains_key(v)) {
88                let matches: Vec<_> = self
89                    .defmap
90                    .iter()
91                    .filter(|(p, _)| p.local == v.local && p.projection.is_empty())
92                    .map(|(p, &def_op)| (*p, def_op))
93                    .collect();
94
95                for (base_place, def_op) in matches {
96                    let mut v_op = self.oprs[def_op].clone();
97                    v_op.set_sink(v);
98
99                    for source in v_op.get_sources() {
100                        self.usemap
101                            .entry(source)
102                            .or_insert(HashSet::new())
103                            .insert(self.oprs.len());
104                    }
105
106                    self.oprs.push(v_op);
107                    self.defmap.insert(v, self.oprs.len() - 1);
108                }
109            }
110        }
111
112        self.vars.get_mut(v).unwrap()
113    }
114
115    pub fn def_add_varnode_sym(
116        &mut self,
117        v: &'tcx Place<'tcx>,
118        rvalue: &'tcx Rvalue<'tcx>,
119    ) -> &mut VarNode<'tcx, T> {
120        let place_ctx: Vec<&Place<'tcx>> = self.vars.keys().map(|p| *p).collect();
121
122        let local_decls = &self.body.local_decls;
123        let node = VarNode::new_symb(v, SymbExpr::from_rvalue(rvalue, place_ctx.clone()));
124        rap_debug!("def node:{:?}", node);
125        let node_ref: &mut VarNode<'tcx, T> = self
126            .vars
127            .entry(v)
128            .and_modify(|old| *old = node.clone())
129            .or_insert(node);
130        self.usemap.entry(v).or_insert(HashSet::new());
131
132        let ty = local_decls[v.local].ty;
133        let place_ty = v.ty(local_decls, self.tcx);
134
135        if v.projection.is_empty() || self.defmap.contains_key(v) {
136            return node_ref;
137        }
138
139        if !v.projection.is_empty() {
140            let matches: Vec<(_, _)> = self
141                .defmap
142                .iter()
143                .filter(|(p, _)| p.local == v.local && p.projection.is_empty())
144                .map(|(p, &def_op)| (*p, def_op))
145                .collect();
146
147            for (base_place, def_op) in matches {
148                let mut v_op = self.oprs[def_op].clone();
149                v_op.set_sink(v);
150
151                for source in v_op.get_sources() {
152                    self.usemap
153                        .entry(source)
154                        .or_insert(HashSet::new())
155                        .insert(self.oprs.len());
156                }
157
158                self.oprs.push(v_op);
159                self.defmap.insert(v, self.oprs.len() - 1);
160            }
161        }
162        node_ref
163    }
164
165    pub fn resolve_all_symexpr(&mut self) {
166        let lookup_context = self.vars.clone();
167        let mut nodes: Vec<&mut VarNode<'tcx, T>> = self.vars.values_mut().collect();
168        nodes.sort_by(|a, b| a.v.local.as_usize().cmp(&b.v.local.as_usize()));
169        for node in nodes {
170            if let IntervalType::Basic(basic) = &mut node.interval {
171                rap_debug!("======{}=====", node.v.local.as_usize());
172                rap_debug!("Before resolve: lower_expr: {}\n", basic.lower);
173                basic.lower.resolve_lower_bound(&lookup_context);
174                basic.lower.simplify();
175                rap_debug!("After resolve: lower_expr: {}\n", basic.lower);
176                rap_debug!("Before resolve: upper_expr: {}\n", basic.upper);
177                basic.upper.resolve_upper_bound(&lookup_context);
178                basic.upper.simplify();
179
180                rap_debug!("After resolve: upper_expr: {}\n", basic.upper);
181            }
182        }
183    }
184
185    pub fn postprocess_defmap(&mut self) {
186        for place in self.vars.keys() {
187            if !place.projection.is_empty() {
188                if let Some((&base_place, &base_value)) = self
189                    .defmap
190                    .iter()
191                    .find(|(p, _)| p.local == place.local && p.projection.is_empty())
192                {
193                    self.defmap.insert(place, base_value);
194                } else {
195                    rap_trace!("postprocess_defmap: No base place found for {:?}", place);
196                }
197            }
198        }
199    }
200
201    pub fn build_graph(&mut self, body: &'tcx Body<'tcx>) {
202        self.build_value_maps(body);
203        for block in body.basic_blocks.indices() {
204            let block_data: &BasicBlockData<'tcx> = &body[block];
205            for statement in block_data.statements.iter() {
206                self.build_operations(statement, block, body);
207            }
208            self.build_terminator(block, block_data.terminator.as_ref().unwrap());
209        }
210        self.resolve_all_symexpr();
211        self.print_vars();
212        self.print_defmap();
213        self.print_usemap();
214        self.print_symbexpr();
215    }
216
217    pub fn build_value_maps(&mut self, body: &'tcx Body<'tcx>) {
218        for bb in body.basic_blocks.indices() {
219            let block_data = &body[bb];
220            if let Some(terminator) = &block_data.terminator {
221                if let TerminatorKind::SwitchInt { discr, targets } = &terminator.kind {
222                    if targets.iter().count() == 1 {
223                        self.build_value_branch_map(body, discr, targets, bb, block_data);
224                    }
225                }
226            }
227        }
228    }
229
230    fn trace_operand_origin(
231        &self,
232        body: &'tcx Body<'tcx>,
233        mut current_block: BasicBlock,
234        target_place: Place<'tcx>,
235        original: &'tcx Operand<'tcx>,
236    ) -> &'tcx Operand<'tcx> {
237        let mut visited = HashSet::new();
238        let target_local = target_place.local;
239        while visited.insert(current_block) {
240            let data = &body.basic_blocks[current_block];
241            for stmt in data.statements.iter().rev() {
242                if let StatementKind::Assign(assign) = &stmt.kind {
243                    let (lhs, rvalue) = &**assign;
244                    if lhs.local == target_local {
245                        return match rvalue {
246                            Rvalue::Use(op, ..) => op,
247                            _ => original,
248                        };
249                    }
250                }
251            }
252            let preds = &body.basic_blocks.predecessors()[current_block];
253            if preds.len() == 1 {
254                current_block = preds[0];
255            } else {
256                break;
257            }
258        }
259        original
260    }
261
262    pub fn build_value_branch_map(
263        &mut self,
264        body: &'tcx Body<'tcx>,
265        discr: &'tcx Operand<'tcx>,
266        targets: &'tcx SwitchTargets,
267        switch_block: BasicBlock,
268        block_data: &'tcx BasicBlockData<'tcx>,
269    ) {
270        if let Operand::Copy(place) | Operand::Move(place) = discr {
271            if let Some((op1, op2, cmp_op)) = self.extract_condition(place, block_data) {
272                rap_debug!(
273                    "extract_condition op1:{:?} op2:{:?} cmp_op:{:?}\n",
274                    op1,
275                    op2,
276                    cmp_op
277                );
278                let op1 = if let Some(p1) = op1.place() {
279                    self.trace_operand_origin(body, switch_block, p1, op1)
280                } else {
281                    op1
282                };
283
284                let op2 = if let Some(p2) = op2.place() {
285                    self.trace_operand_origin(body, switch_block, p2, op2)
286                } else {
287                    op2
288                };
289                rap_debug!(
290                    "build_value_branch_map op1:{:?} op2:{:?} cmp_op:{:?}\n",
291                    op1,
292                    op2,
293                    cmp_op
294                );
295                let const_op1 = op1.constant();
296                let const_op2 = op2.constant();
297                match (const_op1, const_op2) {
298                    (Some(_), Some(_)) => {}
299                    (Some(c), None) | (None, Some(c)) => {
300                        let const_in_left: bool;
301                        let variable;
302                        if const_op1.is_some() {
303                            const_in_left = true;
304                            variable = match op2 {
305                                Operand::Copy(p) | Operand::Move(p) => p,
306                                _ => panic!("Expected a place"),
307                            };
308                        } else {
309                            const_in_left = false;
310                            variable = match op1 {
311                                Operand::Copy(p) | Operand::Move(p) => p,
312                                _ => panic!("Expected a place"),
313                            };
314                        }
315                        self.add_varnode(variable);
316                        rap_trace!("add_vbm_varnode{:?}\n", variable.clone());
317
318                        let Some(value) = T::from_const(&c.const_) else {
319                            rap_trace!("from_const returned None for const {:?}, skipping VBM", c);
320                            return;
321                        };
322                        let const_range =
323                            Range::new(value.clone(), value.clone(), RangeType::Unknown);
324                        rap_trace!("cmp_op {:?}\n", cmp_op);
325                        rap_trace!("const_in_left {:?}\n", const_in_left);
326                        let mut true_range =
327                            self.apply_comparison(value.clone(), cmp_op, true, const_in_left);
328                        let mut false_range =
329                            self.apply_comparison(value.clone(), cmp_op, false, const_in_left);
330                        true_range.set_regular();
331                        false_range.set_regular();
332                        let target_vec = targets.all_targets();
333
334                        let vbm = ValueBranchMap::new(
335                            variable,
336                            &target_vec[0],
337                            &target_vec[1],
338                            IntervalType::Basic(BasicInterval::new(false_range)),
339                            IntervalType::Basic(BasicInterval::new(true_range)),
340                        );
341                        self.values_branchmap.insert(variable, vbm);
342                    }
343                    (None, None) => {
344                        let CR = Range::new(T::min_value(), T::max_value(), RangeType::Unknown);
345
346                        let p1 = match op1 {
347                            Operand::Copy(p) | Operand::Move(p) => p,
348                            _ => panic!("Expected a place"),
349                        };
350                        let p2 = match op2 {
351                            Operand::Copy(p) | Operand::Move(p) => p,
352                            _ => panic!("Expected a place"),
353                        };
354                        let target_vec = targets.all_targets();
355                        self.add_varnode(p1);
356                        rap_trace!("add_vbm_varnode{:?}\n", p1.clone());
357
358                        self.add_varnode(p2);
359                        rap_trace!("add_vbm_varnode{:?}\n", p2.clone());
360                        let flipped_cmp_op = match Self::flipped_binop(cmp_op) {
361                            Some(op) => op,
362                            None => {
363                                rap_debug!(
364                                    "build_value_branch_map: unsupported binop {:?}, skipping\n",
365                                    cmp_op
366                                );
367                                return;
368                            }
369                        };
370                        let reversed_cmp_op = match Self::reverse_binop(cmp_op) {
371                            Some(op) => op,
372                            None => {
373                                rap_debug!(
374                                    "build_value_branch_map: unsupported binop {:?}, skipping\n",
375                                    cmp_op
376                                );
377                                return;
378                            }
379                        };
380                        let reversed_flippedd_cmp_op = match Self::flipped_binop(reversed_cmp_op) {
381                            Some(op) => op,
382                            None => {
383                                rap_debug!(
384                                    "build_value_branch_map: unsupported binop {:?}, skipping\n",
385                                    reversed_cmp_op
386                                );
387                                return;
388                            }
389                        };
390                        let STOp1 = IntervalType::Symb(SymbInterval::new(CR.clone(), p2, cmp_op));
391                        let SFOp1 =
392                            IntervalType::Symb(SymbInterval::new(CR.clone(), p2, flipped_cmp_op));
393                        let STOp2 =
394                            IntervalType::Symb(SymbInterval::new(CR.clone(), p1, reversed_cmp_op));
395                        let SFOp2 = IntervalType::Symb(SymbInterval::new(
396                            CR.clone(),
397                            p1,
398                            reversed_flippedd_cmp_op,
399                        ));
400                        rap_trace!("SFOp1{:?}\n", SFOp1);
401                        rap_trace!("SFOp2{:?}\n", SFOp2);
402                        rap_trace!("STOp1{:?}\n", STOp1);
403                        rap_trace!("STOp2{:?}\n", STOp2);
404                        let vbm_1 =
405                            ValueBranchMap::new(p1, &target_vec[0], &target_vec[1], SFOp1, STOp1);
406                        let vbm_2 =
407                            ValueBranchMap::new(p2, &target_vec[0], &target_vec[1], SFOp2, STOp2);
408                        self.values_branchmap.insert(p1, vbm_1);
409                        self.values_branchmap.insert(p2, vbm_2);
410                        self.switchbbs.insert(switch_block, (*p1, *p2));
411                    }
412                }
413            };
414        }
415    }
416
417    pub fn flipped_binop(op: BinOp) -> Option<BinOp> {
418        use BinOp::*;
419        Some(match op {
420            Eq => Eq,
421            Ne => Ne,
422            Lt => Ge,
423            Le => Gt,
424            Gt => Le,
425            Ge => Lt,
426            Add => Add,
427            Mul => Mul,
428            BitXor => BitXor,
429            BitAnd => BitAnd,
430            BitOr => BitOr,
431            _ => {
432                return None;
433            }
434        })
435    }
436
437    fn reverse_binop(op: BinOp) -> Option<BinOp> {
438        use BinOp::*;
439        Some(match op {
440            Eq => Eq,
441            Ne => Ne,
442            Lt => Gt,
443            Le => Ge,
444            Gt => Lt,
445            Ge => Le,
446            Add => Add,
447            Mul => Mul,
448            BitXor => BitXor,
449            BitAnd => BitAnd,
450            BitOr => BitOr,
451            _ => {
452                return None;
453            }
454        })
455    }
456
457    fn extract_condition(
458        &mut self,
459        place: &'tcx Place<'tcx>,
460        switch_block: &'tcx BasicBlockData<'tcx>,
461    ) -> Option<(&'tcx Operand<'tcx>, &'tcx Operand<'tcx>, BinOp)> {
462        for stmt in &switch_block.statements {
463            if let StatementKind::Assign(assign) = &stmt.kind {
464                let (lhs, rvalue) = &**assign;
465                if let Rvalue::BinaryOp(bin_op, pair) = rvalue {
466                    let (op1, op2) = &**pair;
467                    if lhs == place {
468                        let return_op1: &Operand<'tcx> = op1;
469                        let return_op2: &Operand<'tcx> = op2;
470
471                        return Some((return_op1, return_op2, *bin_op));
472                    }
473                }
474            }
475        }
476        None
477    }
478
479    fn apply_comparison<U: IntervalArithmetic>(
480        &self,
481        constant: U,
482        cmp_op: BinOp,
483        is_true_branch: bool,
484        const_in_left: bool,
485    ) -> Range<U> {
486        match cmp_op {
487            BinOp::Lt => {
488                if is_true_branch ^ const_in_left {
489                    Range::new(U::min_value(), constant.sub(U::one()), RangeType::Unknown)
490                } else {
491                    Range::new(constant, U::max_value(), RangeType::Unknown)
492                }
493            }
494
495            BinOp::Le => {
496                if is_true_branch ^ const_in_left {
497                    Range::new(U::min_value(), constant, RangeType::Unknown)
498                } else {
499                    Range::new(constant.add(U::one()), U::max_value(), RangeType::Unknown)
500                }
501            }
502
503            BinOp::Gt => {
504                if is_true_branch ^ const_in_left {
505                    Range::new(U::min_value(), constant, RangeType::Unknown)
506                } else {
507                    Range::new(constant.add(U::one()), U::max_value(), RangeType::Unknown)
508                }
509            }
510
511            BinOp::Ge => {
512                if is_true_branch ^ const_in_left {
513                    Range::new(U::min_value(), constant, RangeType::Unknown)
514                } else {
515                    Range::new(constant, U::max_value().sub(U::one()), RangeType::Unknown)
516                }
517            }
518
519            BinOp::Eq => {
520                if is_true_branch ^ const_in_left {
521                    Range::new(U::min_value(), constant, RangeType::Unknown)
522                } else {
523                    Range::new(constant, U::max_value(), RangeType::Unknown)
524                }
525            }
526
527            _ => Range::new(constant.clone(), constant.clone(), RangeType::Empty),
528        }
529    }
530
531    pub fn build_symbolic_intersect_map(&mut self) {
532        for i in 0..self.oprs.len() {
533            if let BasicOpKind::Essa(essaop) = &self.oprs[i] {
534                if let IntervalType::Symb(symbi) = essaop.get_intersect() {
535                    let v = symbi.get_bound();
536                    self.symbmap.entry(v).or_insert_with(HashSet::new).insert(i);
537                    rap_trace!("symbmap insert {:?} {:?}\n", v, essaop);
538                }
539            }
540        }
541    }
542
543    pub fn build_use_map(
544        &mut self,
545        component: &HashSet<&'tcx Place<'tcx>>,
546    ) -> HashMap<&'tcx Place<'tcx>, HashSet<usize>> {
547        // Builds use map
548        let mut comp_use_map = HashMap::new();
549        for &place in component {
550            if let Some(uses) = self.usemap.get(place) {
551                for op in uses.iter() {
552                    let sink = self.oprs[*op].get_sink();
553                    if component.contains(&sink) {
554                        comp_use_map
555                            .entry(place)
556                            .or_insert_with(HashSet::new)
557                            .insert(*op);
558                    }
559                }
560            }
561        }
562
563        self.print_compusemap(component, &comp_use_map);
564        comp_use_map
565    }
566
567    pub fn build_terminator(&mut self, block: BasicBlock, terminator: &'tcx Terminator<'tcx>) {
568        match &terminator.kind {
569            TerminatorKind::Call {
570                func,
571                args,
572                destination,
573                target: _,
574                unwind: _,
575                fn_span: _,
576                call_source,
577            } => {
578                rap_trace!(
579                    "TerminatorKind::Call in block {:?} with function {:?} destination {:?} args {:?}\n",
580                    block,
581                    func,
582                    destination,
583                    args
584                );
585                // Handle the call operation
586                self.add_call_op(destination, args, terminator, func, block);
587            }
588            TerminatorKind::Return => {}
589            TerminatorKind::Goto { target } => {
590                rap_trace!(
591                    "TerminatorKind::Goto in block {:?} targeting block {:?}\n",
592                    block,
593                    target
594                );
595            }
596            TerminatorKind::SwitchInt { discr, targets } => {
597                rap_trace!(
598                    "TerminatorKind::SwitchInt in block {:?} with discr {:?} and targets {:?}\n",
599                    block,
600                    discr,
601                    targets
602                );
603            }
604            _ => {
605                rap_trace!(
606                    "Unsupported terminator kind in block {:?}: {:?}",
607                    block,
608                    terminator.kind
609                );
610            }
611        }
612    }
613
614    pub fn build_operations(
615        &mut self,
616        inst: &'tcx Statement<'tcx>,
617        block: BasicBlock,
618        body: &'tcx Body<'tcx>,
619    ) {
620        if let StatementKind::Assign(assign) = &inst.kind {
621            let (sink, rvalue) = &**assign;
622            match rvalue {
623                Rvalue::BinaryOp(op, pair) => {
624                    let (op1, op2) = &**pair;
625                    match op {
626                        BinOp::Add
627                        | BinOp::Sub
628                        | BinOp::Mul
629                        | BinOp::Div
630                        | BinOp::Rem
631                        | BinOp::AddUnchecked => {
632                            self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
633                        }
634                        BinOp::AddWithOverflow => {
635                            self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
636                        }
637                        BinOp::SubUnchecked => {
638                            self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
639                        }
640                        BinOp::SubWithOverflow => {
641                            self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
642                        }
643                        BinOp::MulUnchecked => {
644                            self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
645                        }
646                        BinOp::MulWithOverflow => {
647                            self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
648                        }
649
650                        _ => {}
651                    }
652                }
653                Rvalue::UnaryOp(unop, operand) => {
654                    self.add_unary_op(sink, inst, rvalue, operand, *unop);
655                }
656                Rvalue::Aggregate(kind, operends) => if let AggregateKind::Adt(def_id, _, _, _, _) = **kind { match def_id {
657                    _ if def_id == self.essa => {
658                        self.add_essa_op(sink, inst, rvalue, operends, block)
659                    }
660                    _ if def_id == self.ssa => {
661                        self.add_ssa_op(sink, inst, rvalue, operends)
662                    }
663                    _ => match self.unique_adt_handler(def_id) {
664                        1 => {
665                            self.add_aggregate_op(sink, inst, rvalue, operends, 1);
666                        }
667                        _ => {
668                            rap_trace!(
669                                "AggregateKind::Adt with def_id {:?} in statement {:?} is not handled specially.\n",
670                                def_id,
671                                inst
672                            );
673                        }
674                    },
675                } },
676                Rvalue::Use(operend, ..) => {
677                    self.add_use_op(sink, inst, rvalue, operend);
678                }
679                Rvalue::Ref(_, borrowkind, place) => {
680                    self.add_ref_op(sink, inst, rvalue, place, *borrowkind);
681                }
682                _ => {}
683            }
684        }
685    }
686
687    fn unique_adt_handler(&mut self, def_id: DefId) -> usize {
688        let adt_path = self.tcx.def_path_str(def_id);
689        rap_trace!("adt_path: {:?}\n", adt_path);
690        if self.unique_adt_path.contains_key(&adt_path) {
691            rap_trace!(
692                "unique_adt_handler for def_id: {:?} -> {}\n",
693                def_id,
694                adt_path
695            );
696            return *self.unique_adt_path.get(&adt_path).unwrap();
697        }
698        0
699    }
700    /// Adds a function call operation to the graph.
701
702    fn add_call_op(
703        &mut self,
704        sink: &'tcx Place<'tcx>,
705        args: &'tcx Box<[Spanned<Operand<'tcx>>]>,
706        terminator: &'tcx Terminator<'tcx>,
707        func: &'tcx Operand<'tcx>,
708        block: BasicBlock,
709    ) {
710        rap_trace!("add_call_op for sink: {:?} {:?}\n", sink, terminator);
711        let sink_node = self.add_varnode(sink);
712
713        // Convert Operand arguments to Place arguments.
714        // An Operand can be a Constant or a moved/copied Place.
715        // We only care about Places for our analysis.
716        let mut path = String::new();
717        let mut func_def_id = None;
718        if let Operand::Constant(c_box) = func {
719            let const_operand = &**c_box;
720            let fn_ty = const_operand.ty();
721            if let ty::TyKind::FnDef(def_id, _substs) = fn_ty.kind() {
722                // Found the DefId for a direct function call!
723                rap_debug!("fn_ty: {:?}\n", fn_ty);
724                if def_id.krate != LOCAL_CRATE {
725                    path = self.tcx.def_path_str(*def_id);
726
727                    rap_debug!("called external/no-MIR fn: {:?} -> {}", def_id, path);
728                }
729                func_def_id = Some(def_id);
730            }
731        }
732
733        if let Some(def_id) = func_def_id {
734            rap_trace!(
735                "TerminatorKind::Call in block {:?} with DefId {:?}\n",
736                block,
737                def_id
738            );
739            // You can now use the def_id
740        } else {
741            rap_trace!(
742                "TerminatorKind::Call in block {:?} is an indirect call (e.g., function pointer)\n",
743                block
744            );
745            // This handles cases where the call is not a direct one,
746            // such as calling a function pointer stored in a variable.
747        }
748        let mut constant_count = 0_usize;
749        let arg_count = args.len();
750        let mut arg_operands: Vec<Operand<'tcx>> = Vec::new();
751        let mut places = Vec::new();
752        for op in args.iter() {
753            match &op.node {
754                Operand::Copy(place) | Operand::Move(place) => {
755                    arg_operands.push(op.node.clone());
756                    places.push(place);
757                    self.add_varnode(place);
758                    self.usemap
759                        .entry(place)
760                        .or_default()
761                        .insert(self.oprs.len());
762                }
763
764                Operand::Constant(_) => {
765                    // If it's not a Place, we can still add it as an operand.
766                    // This is useful for constants or other non-place operands.
767                    arg_operands.push(op.node.clone());
768                    constant_count += 1;
769                }
770                #[cfg(rapx_ge_95)]
771                Operand::RuntimeChecks(_) => {}
772            }
773        }
774        {
775            let bi = BasicInterval::default();
776
777            let Some(def_id) = func_def_id else {
778                rap_debug!("Call to function without DefId, skipping\n");
779                return;
780            };
781            let call_op = CallOp::new(
782                IntervalType::Basic(bi),
783                sink,
784                terminator,
785                arg_operands,
786                *def_id,
787                path,
788                places,
789            );
790            rap_debug!("call_op: {:?}\n", call_op);
791            let bop_index = self.oprs.len();
792
793            // Insert the operation into the graph.
794            self.oprs.push(BasicOpKind::Call(call_op));
795
796            // Insert this definition in defmap
797            self.defmap.insert(sink, bop_index);
798            if constant_count == arg_count {
799                rap_trace!("all args are constants\n");
800                self.const_func_place.insert(sink, bop_index);
801            }
802        }
803    }
804
805    fn add_ssa_op(
806        &mut self,
807        sink: &'tcx Place<'tcx>,
808        inst: &'tcx Statement<'tcx>,
809        rvalue: &'tcx Rvalue<'tcx>,
810
811        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
812    ) {
813        rap_trace!("ssa_op{:?}\n", inst);
814
815        let sink_node: &mut VarNode<'_, T> = self.def_add_varnode_sym(sink, rvalue);
816        rap_trace!("addsink_in_ssa_op{:?}\n", sink_node);
817
818        let BI: BasicInterval<T> = BasicInterval::default();
819        let mut phiop = PhiOp::new(IntervalType::Basic(BI), sink, inst);
820        let bop_index = self.oprs.len();
821        for i in 0..operands.len() {
822            let source = match &operands[FieldIdx::from_usize(i)] {
823                Operand::Copy(place) | Operand::Move(place) => {
824                    self.use_add_varnode_sym(place, rvalue);
825                    Some(place)
826                }
827                _ => None,
828            };
829            if let Some(source) = source {
830                self.use_add_varnode_sym(source, rvalue);
831                phiop.add_source(source);
832                rap_trace!("addvar_in_ssa_op{:?}\n", source);
833                self.usemap.entry(source).or_default().insert(bop_index);
834            }
835        }
836        // Insert the operation in the graph.
837
838        self.oprs.push(BasicOpKind::Phi(phiop));
839
840        // Insert this definition in defmap
841
842        self.defmap.insert(sink, bop_index);
843    }
844
845    fn add_use_op(
846        &mut self,
847        sink: &'tcx Place<'tcx>,
848        inst: &'tcx Statement<'tcx>,
849        rvalue: &'tcx Rvalue<'tcx>,
850        op: &'tcx Operand<'tcx>,
851    ) {
852        rap_trace!("use_op{:?}\n", inst);
853
854        let BI: BasicInterval<T> = BasicInterval::default();
855        let source: Option<&'tcx Place<'tcx>> = None;
856
857        match op {
858            Operand::Copy(place) | Operand::Move(place) => {
859                if sink.local == RETURN_PLACE && sink.projection.is_empty() {
860                    self.rerurn_places.insert(place);
861
862                    let sink_node = self.def_add_varnode_sym(sink, rvalue);
863
864                    rap_debug!("add_return_place{:?}\n", place);
865                } else {
866                    self.use_add_varnode_sym(place, rvalue);
867                    rap_trace!("addvar_in_use_op{:?}\n", place);
868                    let sink_node = self.def_add_varnode_sym(sink, rvalue);
869                    let useop = UseOp::new(IntervalType::Basic(BI), sink, inst, Some(place), None);
870                    // Insert the operation in the graph.
871                    let bop_index = self.oprs.len();
872
873                    self.oprs.push(BasicOpKind::Use(useop));
874                    // Insert this definition in defmap
875                    self.usemap.entry(place).or_default().insert(bop_index);
876
877                    self.defmap.insert(sink, bop_index);
878                }
879            }
880            Operand::Constant(constant) => {
881                rap_trace!("add_constant_op{:?}\n", inst);
882                let Some(c) = op.constant() else {
883                    rap_trace!("add_constant_op: constant is None\n");
884                    return;
885                };
886                let useop = UseOp::new(IntervalType::Basic(BI), sink, inst, None, Some(c.const_));
887                // Insert the operation in the graph.
888                let bop_index = self.oprs.len();
889
890                self.oprs.push(BasicOpKind::Use(useop));
891                // Insert this definition in defmap
892
893                self.defmap.insert(sink, bop_index);
894                let sink_node = self.def_add_varnode_sym(sink, rvalue);
895
896                if let Some(value) = T::from_const(&c.const_) {
897                    sink_node.set_range(Range::new(
898                        value.clone(),
899                        value.clone(),
900                        RangeType::Regular,
901                    ));
902                    rap_trace!("set_const {:?} value: {:?}\n", sink_node, value);
903                } else {
904                    sink_node.set_range(Range::bottom());
905                };
906            }
907            #[cfg(rapx_ge_95)]
908            Operand::RuntimeChecks(_) => {}
909        }
910    }
911
912    fn add_essa_op(
913        &mut self,
914        sink: &'tcx Place<'tcx>,
915        inst: &'tcx Statement<'tcx>,
916        rvalue: &'tcx Rvalue<'tcx>,
917        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
918        block: BasicBlock,
919    ) {
920        let sink_node = self.def_add_varnode_sym(sink, rvalue);
921
922        let loc_1: usize = 0;
923        let loc_2: usize = 1;
924        let source1 = match &operands[FieldIdx::from_usize(loc_1)] {
925            Operand::Copy(place) | Operand::Move(place) => {
926                self.use_add_varnode_sym(place, rvalue);
927                Some(place)
928            }
929            _ => None,
930        };
931        let op = &operands[FieldIdx::from_usize(loc_2)];
932        let bop_index = self.oprs.len();
933        let BI: IntervalType<'_, T>;
934        rap_trace!("essa_op operand1 {:?}\n", source1.unwrap());
935        if let Operand::Constant(c) = op {
936            let vbm = self.values_branchmap.get(source1.unwrap()).unwrap();
937            if block == *vbm.get_bb_true() {
938                rap_trace!("essa_op true branch{:?}\n", block);
939                BI = vbm.get_itv_t();
940            } else {
941                rap_trace!("essa_op false branch{:?}\n", block);
942                BI = vbm.get_itv_f();
943            }
944            self.usemap
945                .entry(source1.unwrap())
946                .or_default()
947                .insert(bop_index);
948
949            let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), false);
950            rap_trace!(
951                "addvar_in_essa_op {:?} from const {:?}\n",
952                essaop,
953                source1.unwrap()
954            );
955
956            // Insert the operation in the graph.
957
958            self.oprs.push(BasicOpKind::Essa(essaop));
959            // Insert this definition in defmap
960
961            self.defmap.insert(sink, bop_index);
962        } else {
963            let vbm = self.values_branchmap.get(source1.unwrap()).unwrap();
964            if block == *vbm.get_bb_true() {
965                rap_trace!("essa_op true branch{:?}\n", block);
966                BI = vbm.get_itv_t();
967            } else {
968                rap_trace!("essa_op false branch{:?}\n", block);
969                BI = vbm.get_itv_f();
970            }
971            let source2 = match op {
972                Operand::Copy(place) | Operand::Move(place) => {
973                    self.use_add_varnode_sym(place, rvalue);
974                    Some(place)
975                }
976                _ => None,
977            };
978            self.usemap
979                .entry(source1.unwrap())
980                .or_default()
981                .insert(bop_index);
982            let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), true);
983            // Insert the operation in the graph.
984            rap_trace!(
985                "addvar_in_essa_op {:?} from {:?}\n",
986                essaop,
987                source1.unwrap()
988            );
989
990            self.oprs.push(BasicOpKind::Essa(essaop));
991
992            self.defmap.insert(sink, bop_index);
993        }
994    }
995
996    pub fn add_aggregate_op(
997        &mut self,
998        sink: &'tcx Place<'tcx>,
999        inst: &'tcx Statement<'tcx>,
1000        rvalue: &'tcx Rvalue<'tcx>,
1001        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
1002        unique_adt: usize,
1003    ) {
1004        rap_trace!("aggregate_op {:?}\n", inst);
1005
1006        let BI: BasicInterval<T> = BasicInterval::default();
1007        let mut agg_operands: Vec<AggregateOperand<'tcx>> = Vec::with_capacity(operands.len());
1008
1009        for operand in operands {
1010            match operand {
1011                Operand::Copy(place) | Operand::Move(place) => {
1012                    if sink.local == RETURN_PLACE && sink.projection.is_empty() {
1013                        self.rerurn_places.insert(place);
1014                        self.def_add_varnode_sym(sink, rvalue);
1015                        rap_debug!("add_return_place {:?}\n", place);
1016                    } else {
1017                        self.use_add_varnode_sym(place, rvalue);
1018                        rap_trace!("addvar_in_aggregate_op {:?}\n", place);
1019                        agg_operands.push(AggregateOperand::Place(place));
1020                    }
1021                }
1022                Operand::Constant(c) => {
1023                    rap_trace!("add_constant_aggregate_op {:?}\n", c);
1024                    agg_operands.push(AggregateOperand::Const(c.const_));
1025
1026                    let sink_node = self.def_add_varnode_sym(sink, rvalue);
1027                    if let Some(value) = T::from_const(&c.const_) {
1028                        sink_node.set_range(Range::new(
1029                            value.clone(),
1030                            value.clone(),
1031                            RangeType::Regular,
1032                        ));
1033                        rap_trace!("set_const {:?} value: {:?}\n", sink_node, value);
1034                    } else {
1035                        sink_node.set_range(Range::bottom());
1036                    }
1037                }
1038                #[cfg(rapx_ge_95)]
1039                Operand::RuntimeChecks(_) => {}
1040            }
1041        }
1042
1043        if agg_operands.is_empty() {
1044            rap_trace!("aggregate_op has no operands, skipping\n");
1045            return;
1046        }
1047
1048        let agg_op = AggregateOp::new(
1049            IntervalType::Basic(BI),
1050            sink,
1051            inst,
1052            agg_operands,
1053            unique_adt,
1054        );
1055        let bop_index = self.oprs.len();
1056        self.oprs.push(BasicOpKind::Aggregate(agg_op));
1057
1058        for operand in operands {
1059            if let Operand::Copy(place) | Operand::Move(place) = operand {
1060                self.usemap.entry(place).or_default().insert(bop_index);
1061            }
1062        }
1063
1064        self.defmap.insert(sink, bop_index);
1065
1066        self.def_add_varnode_sym(sink, rvalue);
1067    }
1068
1069    fn add_unary_op(
1070        &mut self,
1071        sink: &'tcx Place<'tcx>,
1072        inst: &'tcx Statement<'tcx>,
1073        rvalue: &'tcx Rvalue<'tcx>,
1074        operand: &'tcx Operand<'tcx>,
1075        op: UnOp,
1076    ) {
1077        rap_trace!("unary_op{:?}\n", inst);
1078
1079        let sink_node = self.def_add_varnode_sym(sink, rvalue);
1080        rap_trace!("addsink_in_unary_op{:?}\n", sink_node);
1081
1082        let BI: BasicInterval<T> = BasicInterval::default();
1083        let loc_1: usize = 0;
1084
1085        let source = match operand {
1086            Operand::Copy(place) | Operand::Move(place) => {
1087                self.add_varnode(place);
1088                Some(place)
1089            }
1090            _ => None,
1091        };
1092
1093        rap_trace!("addvar_in_unary_op{:?}\n", source.unwrap());
1094        self.use_add_varnode_sym(source.unwrap(), rvalue);
1095
1096        let unaryop = UnaryOp::new(IntervalType::Basic(BI), sink, inst, source.unwrap(), op);
1097        // Insert the operation in the graph.
1098        let bop_index = self.oprs.len();
1099
1100        self.oprs.push(BasicOpKind::Unary(unaryop));
1101        // Insert this definition in defmap
1102
1103        self.defmap.insert(sink, bop_index);
1104    }
1105
1106    fn add_binary_op(
1107        &mut self,
1108        sink: &'tcx Place<'tcx>,
1109        inst: &'tcx Statement<'tcx>,
1110        rvalue: &'tcx Rvalue<'tcx>,
1111        op1: &'tcx Operand<'tcx>,
1112        op2: &'tcx Operand<'tcx>,
1113        bin_op: BinOp,
1114    ) {
1115        rap_trace!("binary_op{:?}\n", inst);
1116
1117        // Define the sink node (Def)
1118        let sink_node = self.def_add_varnode_sym(sink, rvalue);
1119        rap_trace!("addsink_in_binary_op{:?}\n", sink_node);
1120
1121        let bop_index = self.oprs.len();
1122        let bi: BasicInterval<T> = BasicInterval::default();
1123
1124        // Match both operands simultaneously to handle all combinations.
1125        // Goal: Ensure source1 is always a Place if at least one Place exists.
1126        let (source1_place, source2_place, const_val) = match (op1, op2) {
1127            // Case 1: Place + Place
1128            (Operand::Copy(p1) | Operand::Move(p1), Operand::Copy(p2) | Operand::Move(p2)) => {
1129                self.use_add_varnode_sym(p1, rvalue);
1130                self.use_add_varnode_sym(p2, rvalue);
1131                rap_trace!("addvar_in_binary_op p1:{:?}, p2:{:?}\n", p1, p2);
1132
1133                (Some(p1), Some(p2), None)
1134            }
1135
1136            // Case 2: Place + Constant
1137            (Operand::Copy(p1) | Operand::Move(p1), Operand::Constant(c2)) => {
1138                self.use_add_varnode_sym(p1, rvalue);
1139                rap_trace!("addvar_in_binary_op p1:{:?}\n", p1);
1140
1141                (Some(p1), None, Some(c2.const_))
1142            }
1143
1144            // Case 3: Constant + Place
1145            // Here we normalize: Treat the Place (op2) as source1, and the Constant (op1) as the const value.
1146            // NOTE: Be careful with non-commutative operations (Sub, Div) in your interval logic later,
1147            // as the physical order is swapped here.
1148            (Operand::Constant(c1), Operand::Copy(p2) | Operand::Move(p2)) => {
1149                self.use_add_varnode_sym(p2, rvalue);
1150                rap_trace!("addvar_in_binary_op p2(as source1):{:?}\n", p2);
1151
1152                // Assign p2 to the first return position to make it source1
1153                (Some(p2), None, Some(c1.const_))
1154            }
1155
1156            // Case 4: Constant + Constant
1157            (Operand::Constant(c1), Operand::Constant(_)) => {
1158                // Logic depends on how you want to handle two constants.
1159                // Usually keeping one is sufficient for the struct signature.
1160                (None, None, Some(c1.const_))
1161            }
1162            #[cfg(rapx_ge_95)]
1163            _ => (None, None, None),
1164        };
1165
1166        // Construct the BinaryOp
1167        let bop = BinaryOp::new(
1168            IntervalType::Basic(bi),
1169            sink,
1170            inst,
1171            source1_place, // This is guaranteed to be the Place (if one exists)
1172            source2_place,
1173            const_val,
1174            bin_op.clone(),
1175        );
1176
1177        self.oprs.push(BasicOpKind::Binary(bop));
1178
1179        // Update DefMap
1180        self.defmap.insert(sink, bop_index);
1181
1182        // Update UseMap
1183        if let Some(place) = source1_place {
1184            self.usemap.entry(place).or_default().insert(bop_index);
1185        }
1186
1187        if let Some(place) = source2_place {
1188            self.usemap.entry(place).or_default().insert(bop_index);
1189        }
1190    }
1191
1192    fn add_ref_op(
1193        &mut self,
1194        sink: &'tcx Place<'tcx>,
1195        inst: &'tcx Statement<'tcx>,
1196        rvalue: &'tcx Rvalue<'tcx>,
1197        place: &'tcx Place<'tcx>,
1198        borrowkind: BorrowKind,
1199    ) {
1200        rap_trace!("ref_op {:?}\n", inst);
1201
1202        let BI: BasicInterval<T> = BasicInterval::default();
1203
1204        let source_node = self.use_add_varnode_sym(place, rvalue);
1205
1206        let sink_node = self.def_add_varnode_sym(sink, rvalue);
1207
1208        let refop = RefOp::new(IntervalType::Basic(BI), sink, inst, place, borrowkind);
1209        let bop_index = self.oprs.len();
1210        self.oprs.push(BasicOpKind::Ref(refop));
1211
1212        self.usemap.entry(place).or_default().insert(bop_index);
1213
1214        self.defmap.insert(sink, bop_index);
1215
1216        rap_trace!(
1217            "add_ref_op: created RefOp from {:?} to {:?} at {:?}\n",
1218            place,
1219            sink,
1220            inst
1221        );
1222    }
1223}
rapx/analysis/range/domain/constraint_graph/graph.rs

rapx/analysis/range/domain/constraint_graph/
graph.rs
