tarp/

traces.rs

use serde::{Deserialize, Serialize};
use std::cmp::{Ord, Ordering};
use std::collections::btree_map::Iter;
use std::collections::{BTreeMap, HashMap};
use std::fmt::{Display, Formatter, Result};
use std::ops::Add;
use std::path::{Path, PathBuf};

/// Used to track the state of logical conditions
#[derive(Debug, Clone, Copy, Default, Hash, PartialEq, Eq, PartialOrd, Deserialize, Serialize)]
pub struct LogicState {
    /// Whether the condition has been observed as true
    pub been_true: bool,
    /// Whether the condition has been observed as false
    pub been_false: bool,
}

impl<'a> Add for &'a LogicState {
    type Output = LogicState;

    fn add(self, other: &'a LogicState) -> LogicState {
        LogicState {
            been_true: self.been_true || other.been_true,
            been_false: self.been_false || other.been_false,
        }
    }
}

/// Shows what type of coverage data is being collected by a given trace
#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Deserialize, Serialize)]
pub enum CoverageStat {
    /// Line coverage data (whether line has been hit)
    Line(u64),
    /// Branch coverage data (whether branch has been true and false
    Branch(LogicState),
    /// Condition coverage data (each boolean subcondition true and false)
    Condition(Vec<LogicState>),
}

impl Add for CoverageStat {
    type Output = CoverageStat;

    fn add(self, other: CoverageStat) -> CoverageStat {
        match (self, other) {
            (CoverageStat::Line(ref l), CoverageStat::Line(ref r)) => CoverageStat::Line(l + r),
            (CoverageStat::Branch(ref l), CoverageStat::Branch(ref r)) => {
                CoverageStat::Branch(l + r)
            }
            t => t.0,
        }
    }
}

impl Display for CoverageStat {
    fn fmt(&self, f: &mut Formatter) -> Result {
        match *self {
            CoverageStat::Line(x) => write!(f, "hits: {}", x),
            _ => write!(f, ""),
        }
    }
}

#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Deserialize, Serialize)]
pub struct Trace {
    /// Line the trace is on in the file
    pub line: u64,
    /// Optional address showing location in the test artefact
    pub address: Option<u64>,
    /// Length of the instruction (useful to get entire condition/branch)
    pub length: usize,
    /// Coverage stats
    pub stats: CoverageStat,
}

/// Implemented to allow Traces to be sorted by line number
impl Ord for Trace {
    fn cmp(&self, other: &Trace) -> Ordering {
        self.line.cmp(&other.line)
    }
    fn max(self, other: Trace) -> Trace {
        if self.line > other.line {
            self
        } else {
            other
        }
    }
    fn min(self, other: Trace) -> Trace {
        if self.line < other.line {
            self
        } else {
            other
        }
    }
}

/// Amount of data coverable in the provided slice traces
pub fn amount_coverable(traces: &[&Trace]) -> usize {
    let mut result = 0usize;
    for t in traces {
        result += match t.stats {
            CoverageStat::Branch(_) => 2usize,
            CoverageStat::Condition(ref x) => x.len() * 2usize,
            _ => 1usize,
        };
    }
    result
}

/// Amount of data covered in the provided trace slice
pub fn amount_covered(traces: &[&Trace]) -> usize {
    let mut result = 0usize;
    for t in traces {
        result += match t.stats {
            CoverageStat::Branch(ref x) => (x.been_true as usize) + (x.been_false as usize),
            CoverageStat::Condition(ref x) => x.iter().fold(0, |acc, ref x| {
                acc + (x.been_true as usize) + (x.been_false as usize)
            }),
            CoverageStat::Line(ref x) => (*x > 0) as usize,
        };
    }
    result
}

pub fn coverage_percentage(traces: &[&Trace]) -> f64 {
    (amount_covered(traces) as f64) / (amount_coverable(traces) as f64)
}

/// Stores all the program traces mapped to files and provides an interface to
/// add, query and change traces.
#[derive(Debug, Default, Deserialize, Serialize)]
pub struct TraceMap {
    /// Traces in the program mapped to the given file
    traces: BTreeMap<PathBuf, Vec<Trace>>,
}

impl TraceMap {
    /// Create a new TraceMap
    pub fn new() -> TraceMap {
        TraceMap {
            traces: BTreeMap::new(),
        }
    }

    /// Returns true if there are no traces
    pub fn is_empty(&self) -> bool {
        self.traces.is_empty()
    }

    /// Provides an interator to the underlying map of PathBufs to Vec<Trace>
    pub fn iter(&self) -> Iter<PathBuf, Vec<Trace>> {
        self.traces.iter()
    }

    /// Merges the results of one tracemap into the current one.
    /// This adds records which are missing and adds the statistics gathered to
    /// existing records
    pub fn merge(&mut self, other: &TraceMap) {
        for (k, values) in other.iter() {
            if !self.traces.contains_key(k) {
                self.traces.insert(k.to_path_buf(), values.to_vec());
            } else {
                let existing = self.traces.get_mut(k).unwrap();
                for ref v in values.iter() {
                    let mut added = false;
                    if let Some(ref mut t) = existing
                        .iter_mut()
                        .find(|ref x| x.line == v.line && x.address == v.address)
                    {
                        t.stats = t.stats.clone() + v.stats.clone();
                        added = true;
                    }
                    if !added {
                        existing.push((*v).clone());
                        existing.sort_unstable();
                    }
                }
            }
        }
    }

    /// This will collapse duplicate Traces into a single trace. Warning this
    /// will lose the addresses of the duplicate traces but increment the results
    /// should be called only if you don't need those addresses from then on
    /// TODO possibly not the cleanest solution
    pub fn dedup(&mut self) {
        for values in self.traces.values_mut() {
            // Map of lines and stats, merge duplicated stats here
            let mut lines: HashMap<u64, CoverageStat> = HashMap::new();
            // Duplicated traces need cleaning up. Maintain a list of them!
            let mut dirty: Vec<u64> = Vec::new();
            for v in values.iter() {
                lines
                    .entry(v.line)
                    .and_modify(|e| {
                        dirty.push(v.line);
                        *e = e.clone() + v.stats.clone();
                    })
                    .or_insert_with(|| v.stats.clone());
            }
            for d in &dirty {
                let mut first = true;
                values.retain(|x| {
                    let res = x.line != *d;
                    if !res {
                        if first {
                            first = false;
                            true
                        } else {
                            false
                        }
                    } else {
                        res
                    }
                });
                if let Some(new_stat) = lines.remove(&d) {
                    if let Some(ref mut t) = values.iter_mut().find(|x| x.line == *d) {
                        t.stats = new_stat;
                    }
                }
            }
        }
    }

    /// Add a trace to the tracemap for the given file
    pub fn add_trace(&mut self, file: &Path, trace: Trace) {
        if self.traces.contains_key(file) {
            if let Some(trace_vec) = self.traces.get_mut(file) {
                trace_vec.push(trace);
                trace_vec.sort_unstable();
            }
        } else {
            self.traces.insert(file.to_path_buf(), vec![trace]);
        }
    }

    /// Gets an immutable reference to a trace from an address. Returns None if
    /// there is no trace at that address
    pub fn get_trace(&self, address: u64) -> Option<&Trace> {
        self.all_traces()
            .iter()
            .find(|x| x.address == Some(address))
            .map(|x| *x)
    }

    /// Gets a mutable reference to a trace at a given address
    /// Returns None if there is no trace at that address
    pub fn get_trace_mut(&mut self, address: u64) -> Option<&mut Trace> {
        for val in self.all_traces_mut() {
            if val.address == Some(address) {
                return Some(val);
            }
        }
        None
    }

    /// Returns true if the location described by file and line number is present
    /// in the tracemap
    pub fn contains_location(&self, file: &Path, line: u64) -> bool {
        match self.traces.get(file) {
            Some(traces) => traces.iter().any(|x| x.line == line),
            None => false,
        }
    }

    /// Returns true if the file is among the traces
    pub fn contains_file(&self, file: &Path) -> bool {
        self.traces.contains_key(file)
    }

    /// Gets all traces below a certain path
    pub fn get_child_traces(&self, root: &Path) -> Vec<&Trace> {
        self.traces
            .iter()
            .filter(|&(ref k, _)| k.starts_with(root))
            .flat_map(|(_, ref v)| v.iter())
            .collect()
    }

    /// Gets all traces in folder, doesn't go into other folders for that you
    /// want get_child_traces
    pub fn get_traces(&self, root: &Path) -> Vec<&Trace> {
        if root.is_file() {
            self.get_child_traces(root)
        } else {
            self.traces
                .iter()
                .filter(|&(ref k, _)| k.parent() == Some(root))
                .flat_map(|(_, ref v)| v.iter())
                .collect()
        }
    }

    /// Gets all traces
    pub fn all_traces(&self) -> Vec<&Trace> {
        self.traces.values().flat_map(|ref x| x.iter()).collect()
    }

    /// Gets a vector of all the traces to mutate
    fn all_traces_mut(&mut self) -> Vec<&mut Trace> {
        self.traces
            .values_mut()
            .flat_map(|x| x.iter_mut())
            .collect()
    }

    pub fn files(&self) -> Vec<&PathBuf> {
        self.traces.keys().collect()
    }

    pub fn coverable_in_path(&self, path: &Path) -> usize {
        amount_coverable(self.get_child_traces(path).as_slice())
    }

    pub fn covered_in_path(&self, path: &Path) -> usize {
        amount_covered(self.get_child_traces(path).as_slice())
    }

    /// Give the total amount of coverable points in the code. This will vary
    /// based on the statistics available for line coverage it will be total
    /// lines whereas for condition or decision it will count the number of
    /// conditions available
    pub fn total_coverable(&self) -> usize {
        amount_coverable(self.all_traces().as_slice())
    }

    /// From all the coverable data return the amount covered
    pub fn total_covered(&self) -> usize {
        amount_covered(self.all_traces().as_slice())
    }

    /// Returns coverage percentage ranging from 0.0-1.0
    pub fn coverage_percentage(&self) -> f64 {
        coverage_percentage(self.all_traces().as_slice())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::path::Path;

    #[test]
    fn stat_addition() {
        let x = CoverageStat::Line(0);
        let y = CoverageStat::Line(5);
        let z = CoverageStat::Line(7);
        let xy = x.clone() + y.clone();
        let yx = y.clone() + x.clone();
        let yy = y.clone() + y.clone();
        let zy = z.clone() + y.clone();
        assert_eq!(&xy, &CoverageStat::Line(5));
        assert_eq!(&yx, &xy);
        assert_eq!(&yy, &CoverageStat::Line(10));
        assert_eq!(&zy, &CoverageStat::Line(12));

        let tf = LogicState {
            been_true: true,
            been_false: true,
        };
        let t = LogicState {
            been_true: true,
            been_false: false,
        };
        let f = LogicState {
            been_true: false,
            been_false: true,
        };
        let n = LogicState {
            been_true: false,
            been_false: false,
        };

        assert_eq!(&t + &f, tf);
        assert_eq!(&t + &t, t);
        assert_eq!(&tf + &f, tf);
        assert_eq!(&tf + &t, tf);
        assert_eq!(&t + &n, t);
        assert_eq!(&n + &f, f);
        assert_eq!(&n + &n, n);
    }

    #[test]
    fn merge_address_mismatch_and_dedup() {
        let mut t1 = TraceMap::new();
        let mut t2 = TraceMap::new();

        let a_trace = Trace {
            line: 1,
            address: Some(5),
            length: 0,
            stats: CoverageStat::Line(1),
        };
        t1.add_trace(Path::new("file.rs"), a_trace.clone());
        t2.add_trace(
            Path::new("file.rs"),
            Trace {
                line: 1,
                address: None,
                length: 0,
                stats: CoverageStat::Line(2),
            },
        );

        t1.merge(&t2);
        assert_eq!(t1.all_traces().len(), 2);
        assert_eq!(t1.get_trace(5), Some(&a_trace));
        t1.dedup();
        let all = t1.all_traces();
        assert_eq!(all.len(), 1);
        assert_eq!(all[0].stats, CoverageStat::Line(3));
    }

    #[test]
    fn no_merge_dedup_needed() {
        let mut t1 = TraceMap::new();
        let mut t2 = TraceMap::new();

        let a_trace = Trace {
            line: 1,
            address: Some(5),
            length: 0,
            stats: CoverageStat::Line(1),
        };
        t1.add_trace(Path::new("file.rs"), a_trace.clone());
        t2.add_trace(
            Path::new("file.rs"),
            Trace {
                line: 2,
                address: None,
                length: 0,
                stats: CoverageStat::Line(2),
            },
        );

        t1.merge(&t2);
        assert_eq!(t1.all_traces().len(), 2);
        assert_eq!(t1.get_trace(5), Some(&a_trace));
        t1.dedup();
        let all = t1.all_traces();
        assert_eq!(all.len(), 2);
    }

    #[test]
    fn merge_needed() {
        let mut t1 = TraceMap::new();
        let mut t2 = TraceMap::new();

        t1.add_trace(
            Path::new("file.rs"),
            Trace {
                line: 2,
                address: Some(1),
                length: 0,
                stats: CoverageStat::Line(5),
            },
        );
        t2.add_trace(
            Path::new("file.rs"),
            Trace {
                line: 2,
                address: Some(1),
                length: 0,
                stats: CoverageStat::Line(2),
            },
        );
        t1.merge(&t2);
        assert_eq!(t1.all_traces().len(), 1);
        assert_eq!(
            t1.get_trace(1),
            Some(&Trace {
                line: 2,
                address: Some(1),
                length: 0,
                stats: CoverageStat::Line(7)
            })
        );
        // Deduplicating should have no effect.
        t1.dedup();
        assert_eq!(t1.all_traces().len(), 1);
        assert_eq!(
            t1.get_trace(1),
            Some(&Trace {
                line: 2,
                address: Some(1),
                length: 0,
                stats: CoverageStat::Line(7)
            })
        );
    }
}