cargo_tarpaulin/
traces.rs

1use crate::source_analysis::Function;
2use serde::{Deserialize, Serialize};
3use std::cmp::{Ord, Ordering};
4use std::collections::btree_map::Iter;
5use std::collections::{BTreeMap, HashMap, HashSet};
6use std::ops::Add;
7use std::path::{Path, PathBuf};
8use tracing::trace;
9
10/// Used to track the state of logical conditions
11#[derive(Debug, Clone, Copy, Default, Hash, PartialEq, Eq, PartialOrd, Deserialize, Serialize)]
12pub struct LogicState {
13    /// Whether the condition has been observed as true
14    pub been_true: bool,
15    /// Whether the condition has been observed as false
16    pub been_false: bool,
17}
18
19impl<'a> Add for &'a LogicState {
20    type Output = LogicState;
21
22    fn add(self, other: &'a LogicState) -> LogicState {
23        LogicState {
24            been_true: self.been_true || other.been_true,
25            been_false: self.been_false || other.been_false,
26        }
27    }
28}
29
30/// Shows what type of coverage data is being collected by a given trace
31#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Deserialize, Serialize)]
32pub enum CoverageStat {
33    /// Line coverage data (whether line has been hit)
34    Line(u64),
35    /// Branch coverage data (whether branch has been true and false
36    Branch(LogicState),
37    /// Condition coverage data (each boolean subcondition true and false)
38    Condition(Vec<LogicState>),
39}
40
41impl Add for CoverageStat {
42    type Output = CoverageStat;
43
44    fn add(self, other: CoverageStat) -> CoverageStat {
45        match (self, other) {
46            (CoverageStat::Line(ref l), CoverageStat::Line(ref r)) => CoverageStat::Line(l + r),
47            (CoverageStat::Branch(ref l), CoverageStat::Branch(ref r)) => {
48                CoverageStat::Branch(l + r)
49            }
50            t => t.0,
51        }
52    }
53}
54
55#[derive(Debug, Clone, PartialEq, Eq, Deserialize, Serialize)]
56pub struct Trace {
57    /// Line the trace is on in the file
58    pub line: u64,
59    /// Optional address showing location in the test artefact
60    pub address: HashSet<u64>,
61    /// Length of the instruction (useful to get entire condition/branch)
62    pub length: usize,
63    /// Coverage stats
64    pub stats: CoverageStat,
65}
66
67#[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
68pub struct Location {
69    /// Source file
70    pub file: PathBuf,
71    /// Source line
72    pub line: u64,
73}
74
75impl Trace {
76    pub fn new(line: u64, address: HashSet<u64>, length: usize) -> Self {
77        Self {
78            line,
79            address,
80            length,
81            stats: CoverageStat::Line(0),
82        }
83    }
84
85    pub fn new_stub(line: u64) -> Self {
86        Self {
87            line,
88            address: HashSet::new(),
89            length: 0,
90            stats: CoverageStat::Line(0),
91        }
92    }
93}
94
95impl PartialOrd for Trace {
96    fn partial_cmp(&self, other: &Trace) -> Option<Ordering> {
97        // Not sure if I care about the others
98        self.line.partial_cmp(&other.line)
99    }
100}
101
102/// Implemented to allow Traces to be sorted by line number
103impl Ord for Trace {
104    fn cmp(&self, other: &Trace) -> Ordering {
105        self.line.cmp(&other.line)
106    }
107    fn max(self, other: Trace) -> Trace {
108        if self.line > other.line {
109            self
110        } else {
111            other
112        }
113    }
114    fn min(self, other: Trace) -> Trace {
115        if self.line < other.line {
116            self
117        } else {
118            other
119        }
120    }
121}
122
123/// Amount of data coverable in the provided slice traces
124pub fn amount_coverable<'a>(traces: impl Iterator<Item = &'a Trace>) -> usize {
125    let mut result = 0usize;
126    for t in traces {
127        result += match t.stats {
128            CoverageStat::Branch(_) => 2usize,
129            CoverageStat::Condition(ref x) => x.len() * 2usize,
130            _ => 1usize,
131        };
132    }
133    result
134}
135
136/// Amount of data covered in the provided trace slice
137pub fn amount_covered<'a>(traces: impl Iterator<Item = &'a Trace>) -> usize {
138    let mut result = 0usize;
139    for t in traces {
140        result += match t.stats {
141            CoverageStat::Branch(ref x) => usize::from(x.been_true) + usize::from(x.been_false),
142            CoverageStat::Condition(ref x) => x.iter().fold(0, |acc, x| {
143                acc + usize::from(x.been_true) + usize::from(x.been_false)
144            }),
145            CoverageStat::Line(ref x) => (*x > 0).into(),
146        };
147    }
148    result
149}
150
151pub fn coverage_percentage<'a>(traces: impl Iterator<Item = &'a Trace>) -> f64 {
152    let t: Vec<_> = traces.collect();
153    (amount_covered(t.iter().copied()) as f64) / (amount_coverable(t.iter().copied()) as f64)
154}
155
156/// Stores all the program traces mapped to files and provides an interface to
157/// add, query and change traces.
158#[derive(Debug, Default, Deserialize, Serialize)]
159pub struct TraceMap {
160    ///rTraces in the program mapped to the given file
161    traces: BTreeMap<PathBuf, Vec<Trace>>,
162    functions: HashMap<PathBuf, Vec<Function>>,
163}
164
165impl TraceMap {
166    /// Create a new TraceMap
167    pub fn new() -> TraceMap {
168        Self::default()
169    }
170
171    pub fn set_functions(&mut self, functions: HashMap<PathBuf, Vec<Function>>) {
172        self.functions = functions;
173    }
174
175    /// Returns true if there are no traces
176    pub fn is_empty(&self) -> bool {
177        self.traces.is_empty()
178    }
179
180    /// Provides an iterator to the underlying map of PathBufs to Vec<Trace>
181    pub fn iter(&self) -> Iter<PathBuf, Vec<Trace>> {
182        self.traces.iter()
183    }
184
185    /// Merges the results of one tracemap into the current one.
186    /// This adds records which are missing and adds the statistics gathered to
187    /// existing records
188    pub fn merge(&mut self, other: &TraceMap) {
189        self.functions
190            .extend(other.functions.iter().map(|(k, v)| (k.clone(), v.clone())));
191        for (k, values) in other.iter() {
192            if !self.traces.contains_key(k) {
193                self.traces.insert(k.clone(), values.clone());
194            } else {
195                let existing = self.traces.get_mut(k).unwrap();
196                for v in values.iter() {
197                    let mut added = false;
198                    if let Some(ref mut t) = existing
199                        .iter_mut()
200                        .find(|x| x.line == v.line && x.address == v.address)
201                    {
202                        t.stats = t.stats.clone() + v.stats.clone();
203                        added = true;
204                    }
205                    if !added {
206                        existing.push((*v).clone());
207                        existing.sort_unstable();
208                    }
209                }
210            }
211        }
212    }
213
214    /// This will collapse duplicate Traces into a single trace. Warning this
215    /// will lose the addresses of the duplicate traces but increment the results
216    /// should be called only if you don't need those addresses from then on
217    /// TODO possibly not the cleanest solution
218    pub fn dedup(&mut self) {
219        for values in self.traces.values_mut() {
220            // Map of lines and stats, merge duplicated stats here
221            let mut lines: HashMap<u64, CoverageStat> = HashMap::new();
222            // Duplicated traces need cleaning up. Maintain a list of them!
223            let mut dirty: Vec<u64> = Vec::new();
224            for v in values.iter() {
225                lines
226                    .entry(v.line)
227                    .and_modify(|e| {
228                        dirty.push(v.line);
229                        *e = e.clone() + v.stats.clone();
230                    })
231                    .or_insert_with(|| v.stats.clone());
232            }
233            for d in &dirty {
234                let mut first = true;
235                values.retain(|x| {
236                    let res = x.line != *d;
237                    if !res {
238                        if first {
239                            first = false;
240                            true
241                        } else {
242                            false
243                        }
244                    } else {
245                        res
246                    }
247                });
248                if let Some(new_stat) = lines.remove(d) {
249                    if let Some(ref mut t) = values.iter_mut().find(|x| x.line == *d) {
250                        t.stats = new_stat;
251                    }
252                }
253            }
254        }
255    }
256
257    /// Add a trace to the tracemap for the given file
258    pub fn add_trace(&mut self, file: &Path, trace: Trace) {
259        if self.traces.contains_key(file) {
260            if let Some(trace_vec) = self.traces.get_mut(file) {
261                trace_vec.push(trace);
262                trace_vec.sort_unstable();
263            }
264        } else {
265            self.traces.insert(file.to_path_buf(), vec![trace]);
266        }
267    }
268
269    pub fn add_file(&mut self, file: &Path) {
270        if !self.traces.contains_key(file) {
271            self.traces.insert(file.to_path_buf(), vec![]);
272        }
273    }
274
275    /// Gets an immutable reference to a trace from an address. Returns None if
276    /// there is no trace at that address
277    pub fn get_trace(&self, address: u64) -> Option<&Trace> {
278        self.all_traces().find(|x| x.address.contains(&address))
279    }
280
281    pub fn increment_hit(&mut self, address: u64) {
282        for trace in self
283            .all_traces_mut()
284            .filter(|x| x.address.contains(&address))
285        {
286            if let CoverageStat::Line(ref mut x) = trace.stats {
287                trace!("Incrementing hit count for trace");
288                *x += 1;
289            }
290        }
291    }
292
293    pub fn get_location(&self, address: u64) -> Option<Location> {
294        for (k, v) in &self.traces {
295            if let Some(s) = v
296                .iter()
297                .find(|x| x.address.iter().any(|x| (*x & !0x7u64) == address))
298            {
299                return Some(Location {
300                    file: k.clone(),
301                    line: s.line,
302                });
303            }
304        }
305        None
306    }
307
308    /// Returns true if the location described by file and line number is present
309    /// in the tracemap
310    pub fn contains_location(&self, file: &Path, line: u64) -> bool {
311        match self.traces.get(file) {
312            Some(traces) => traces.iter().any(|x| x.line == line),
313            None => false,
314        }
315    }
316
317    /// Returns true if the file is among the traces
318    pub fn contains_file(&self, file: &Path) -> bool {
319        self.traces.contains_key(file)
320    }
321
322    /// Gets all traces below a certain path
323    pub fn get_child_traces<'a>(&'a self, root: &'a Path) -> impl Iterator<Item = &'a Trace> + 'a {
324        self.traces
325            .iter()
326            .filter(move |&(k, _)| k.starts_with(root))
327            .flat_map(|(_, v)| v.iter())
328    }
329
330    pub fn get_functions(&self, file: &Path) -> impl Iterator<Item = &Function> {
331        let i: Box<dyn Iterator<Item = &Function>> = match self.functions.get(file) {
332            Some(f) => Box::new(f.iter()),
333            None => Box::new(std::iter::empty()),
334        };
335        i
336    }
337
338    pub fn file_traces_mut(&mut self, file: &Path) -> Option<&mut Vec<Trace>> {
339        self.traces.get_mut(file)
340    }
341
342    /// Gets all traces
343    pub fn all_traces(&self) -> impl Iterator<Item = &Trace> {
344        self.traces.values().flat_map(|x| x.iter())
345    }
346
347    /// Gets a vector of all the traces to mutate
348    fn all_traces_mut(&mut self) -> impl Iterator<Item = &mut Trace> {
349        self.traces.values_mut().flat_map(|x| x.iter_mut())
350    }
351
352    pub fn files(&self) -> Vec<&PathBuf> {
353        self.traces.keys().collect()
354    }
355
356    pub fn coverable_in_path(&self, path: &Path) -> usize {
357        amount_coverable(self.get_child_traces(path))
358    }
359
360    pub fn covered_in_path(&self, path: &Path) -> usize {
361        amount_covered(self.get_child_traces(path))
362    }
363
364    /// Give the total amount of coverable points in the code. This will vary
365    /// based on the statistics available for line coverage it will be total
366    /// lines whereas for condition or decision it will count the number of
367    /// conditions available
368    pub fn total_coverable(&self) -> usize {
369        amount_coverable(self.all_traces())
370    }
371
372    /// From all the coverable data return the amount covered
373    pub fn total_covered(&self) -> usize {
374        amount_covered(self.all_traces())
375    }
376
377    /// Returns coverage percentage ranging from 0.0-1.0
378    pub fn coverage_percentage(&self) -> f64 {
379        coverage_percentage(self.all_traces())
380    }
381}
382
383#[cfg(test)]
384mod tests {
385    use super::*;
386    use std::path::Path;
387
388    #[test]
389    #[allow(clippy::many_single_char_names)]
390    fn stat_addition() {
391        let x = CoverageStat::Line(0);
392        let y = CoverageStat::Line(5);
393        let z = CoverageStat::Line(7);
394        let xy = x.clone() + y.clone();
395        let yx = y.clone() + x;
396        let yy = y.clone() + y.clone();
397        let zy = z + y;
398        assert_eq!(&xy, &CoverageStat::Line(5));
399        assert_eq!(&yx, &xy);
400        assert_eq!(&yy, &CoverageStat::Line(10));
401        assert_eq!(&zy, &CoverageStat::Line(12));
402
403        let tf = LogicState {
404            been_true: true,
405            been_false: true,
406        };
407        let t = LogicState {
408            been_true: true,
409            been_false: false,
410        };
411        let f = LogicState {
412            been_true: false,
413            been_false: true,
414        };
415        let n = LogicState {
416            been_true: false,
417            been_false: false,
418        };
419
420        assert_eq!(&t + &f, tf);
421        assert_eq!(&t + &t, t);
422        assert_eq!(&tf + &f, tf);
423        assert_eq!(&tf + &t, tf);
424        assert_eq!(&t + &n, t);
425        assert_eq!(&n + &f, f);
426        assert_eq!(&n + &n, n);
427    }
428
429    #[test]
430    fn multiple_traces_per_line() {
431        let mut t1 = TraceMap::new();
432        let mut address = HashSet::new();
433        address.insert(0);
434        address.insert(128);
435        let trace_1 = Trace {
436            line: 1,
437            address,
438            length: 0,
439            stats: CoverageStat::Line(1),
440        };
441        t1.add_trace(Path::new("file.rs"), trace_1);
442
443        let coverable = t1.total_coverable();
444        assert_eq!(coverable, 1);
445        let total_covered = t1.total_covered();
446        assert_eq!(total_covered, 1);
447    }
448
449    #[test]
450    fn merge_address_mismatch_and_dedup() {
451        let mut t1 = TraceMap::new();
452        let mut t2 = TraceMap::new();
453
454        let mut address = HashSet::new();
455        address.insert(5);
456        let a_trace = Trace {
457            line: 1,
458            address,
459            length: 0,
460            stats: CoverageStat::Line(1),
461        };
462        t1.add_trace(Path::new("file.rs"), a_trace.clone());
463        t2.add_trace(
464            Path::new("file.rs"),
465            Trace {
466                line: 1,
467                address: HashSet::new(),
468                length: 0,
469                stats: CoverageStat::Line(2),
470            },
471        );
472
473        t1.merge(&t2);
474        assert_eq!(t1.all_traces().count(), 2);
475        assert_eq!(t1.get_trace(5), Some(&a_trace));
476        t1.dedup();
477        let all = t1.all_traces().collect::<Vec<_>>();
478        assert_eq!(all.len(), 1);
479        assert_eq!(all[0].stats, CoverageStat::Line(3));
480    }
481
482    #[test]
483    fn no_merge_dedup_needed() {
484        let mut t1 = TraceMap::new();
485        let mut t2 = TraceMap::new();
486
487        let mut address = HashSet::new();
488        address.insert(5);
489        let a_trace = Trace {
490            line: 1,
491            address,
492            length: 0,
493            stats: CoverageStat::Line(1),
494        };
495        t1.add_trace(Path::new("file.rs"), a_trace.clone());
496        t2.add_trace(
497            Path::new("file.rs"),
498            Trace {
499                line: 2,
500                address: HashSet::new(),
501                length: 0,
502                stats: CoverageStat::Line(2),
503            },
504        );
505
506        t1.merge(&t2);
507        assert_eq!(t1.all_traces().count(), 2);
508        assert_eq!(t1.get_trace(5), Some(&a_trace));
509        t1.dedup();
510        let all = t1.all_traces();
511        assert_eq!(all.count(), 2);
512    }
513
514    #[test]
515    fn merge_needed() {
516        let mut t1 = TraceMap::new();
517        let mut t2 = TraceMap::new();
518
519        let mut address = HashSet::new();
520        address.insert(1);
521        t1.add_trace(
522            Path::new("file.rs"),
523            Trace {
524                line: 2,
525                address: address.clone(),
526                length: 0,
527                stats: CoverageStat::Line(5),
528            },
529        );
530        t2.add_trace(
531            Path::new("file.rs"),
532            Trace {
533                line: 2,
534                address: address.clone(),
535                length: 0,
536                stats: CoverageStat::Line(2),
537            },
538        );
539        t1.merge(&t2);
540        assert_eq!(t1.all_traces().count(), 1);
541        assert_eq!(
542            t1.get_trace(1),
543            Some(&Trace {
544                line: 2,
545                address: address.clone(),
546                length: 0,
547                stats: CoverageStat::Line(7),
548            })
549        );
550        // Deduplicating should have no effect.
551        t1.dedup();
552        assert_eq!(t1.all_traces().count(), 1);
553        assert_eq!(
554            t1.get_trace(1),
555            Some(&Trace {
556                line: 2,
557                address,
558                length: 0,
559                stats: CoverageStat::Line(7),
560            })
561        );
562    }
563}
cargo_tarpaulin/traces.rs

cargo_tarpaulin/
traces.rs
