use super::Error;
use super::graph;
use graph::{BasicCoverageBlock, BcbBranch, CoverageGraph, TraverseCoverageGraphWithLoops};
use rustc_data_structures::fx::FxHashMap;
use rustc_data_structures::graph::WithNumNodes;
use rustc_index::bit_set::BitSet;
use rustc_index::IndexVec;
use rustc_middle::mir::coverage::*;
use std::fmt::{self, Debug};
const NESTED_INDENT: &str = " ";
#[derive(Clone)]
pub(super) enum BcbCounter {
Counter { id: CounterId },
Expression { id: ExpressionId, lhs: Operand, op: Op, rhs: Operand },
}
impl BcbCounter {
fn is_expression(&self) -> bool {
matches!(self, Self::Expression { .. })
}
pub(super) fn as_operand(&self) -> Operand {
match *self {
BcbCounter::Counter { id, .. } => Operand::Counter(id),
BcbCounter::Expression { id, .. } => Operand::Expression(id),
}
}
}
impl Debug for BcbCounter {
fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Counter { id, .. } => write!(fmt, "Counter({:?})", id.index()),
Self::Expression { id, lhs, op, rhs } => write!(
fmt,
"Expression({:?}) = {:?} {} {:?}",
id.index(),
lhs,
match op {
Op::Add => "+",
Op::Subtract => "-",
},
rhs,
),
}
}
}
pub(super) struct CoverageCounters {
next_counter_id: CounterId,
next_expression_id: ExpressionId,
bcb_counters: IndexVec<BasicCoverageBlock, Option<BcbCounter>>,
bcb_edge_counters: FxHashMap<(BasicCoverageBlock, BasicCoverageBlock), BcbCounter>,
bcb_has_incoming_edge_counters: BitSet<BasicCoverageBlock>,
pub(super) intermediate_expressions: Vec<BcbCounter>,
}
impl CoverageCounters {
pub(super) fn new(basic_coverage_blocks: &CoverageGraph) -> Self {
let num_bcbs = basic_coverage_blocks.num_nodes();
Self {
next_counter_id: CounterId::START,
next_expression_id: ExpressionId::START,
bcb_counters: IndexVec::from_elem_n(None, num_bcbs),
bcb_edge_counters: FxHashMap::default(),
bcb_has_incoming_edge_counters: BitSet::new_empty(num_bcbs),
intermediate_expressions: Vec::new(),
}
}
pub fn make_bcb_counters(
&mut self,
basic_coverage_blocks: &CoverageGraph,
bcb_has_coverage_spans: impl Fn(BasicCoverageBlock) -> bool,
) -> Result<(), Error> {
MakeBcbCounters::new(self, basic_coverage_blocks).make_bcb_counters(bcb_has_coverage_spans)
}
fn make_counter(&mut self) -> BcbCounter {
let id = self.next_counter();
BcbCounter::Counter { id }
}
fn make_expression(&mut self, lhs: Operand, op: Op, rhs: Operand) -> BcbCounter {
let id = self.next_expression();
BcbCounter::Expression { id, lhs, op, rhs }
}
fn next_counter(&mut self) -> CounterId {
let next = self.next_counter_id;
self.next_counter_id = self.next_counter_id + 1;
next
}
fn next_expression(&mut self) -> ExpressionId {
let next = self.next_expression_id;
self.next_expression_id = self.next_expression_id + 1;
next
}
fn set_bcb_counter(
&mut self,
bcb: BasicCoverageBlock,
counter_kind: BcbCounter,
) -> Result<Operand, Error> {
debug_assert!(
counter_kind.is_expression() || !self.bcb_has_incoming_edge_counters.contains(bcb),
"attempt to add a `Counter` to a BCB target with existing incoming edge counters"
);
let operand = counter_kind.as_operand();
if let Some(replaced) = self.bcb_counters[bcb].replace(counter_kind) {
Error::from_string(format!(
"attempt to set a BasicCoverageBlock coverage counter more than once; \
{bcb:?} already had counter {replaced:?}",
))
} else {
Ok(operand)
}
}
fn set_bcb_edge_counter(
&mut self,
from_bcb: BasicCoverageBlock,
to_bcb: BasicCoverageBlock,
counter_kind: BcbCounter,
) -> Result<Operand, Error> {
if level_enabled!(tracing::Level::DEBUG) {
if self.bcb_counter(to_bcb).is_some_and(|c| !c.is_expression()) {
return Error::from_string(format!(
"attempt to add an incoming edge counter from {from_bcb:?} when the target BCB already \
has a `Counter`"
));
}
}
self.bcb_has_incoming_edge_counters.insert(to_bcb);
let operand = counter_kind.as_operand();
if let Some(replaced) = self.bcb_edge_counters.insert((from_bcb, to_bcb), counter_kind) {
Error::from_string(format!(
"attempt to set an edge counter more than once; from_bcb: \
{from_bcb:?} already had counter {replaced:?}",
))
} else {
Ok(operand)
}
}
pub(super) fn bcb_counter(&self, bcb: BasicCoverageBlock) -> Option<&BcbCounter> {
self.bcb_counters[bcb].as_ref()
}
pub(super) fn take_bcb_counter(&mut self, bcb: BasicCoverageBlock) -> Option<BcbCounter> {
self.bcb_counters[bcb].take()
}
pub(super) fn drain_bcb_counters(
&mut self,
) -> impl Iterator<Item = (BasicCoverageBlock, BcbCounter)> + '_ {
self.bcb_counters
.iter_enumerated_mut()
.filter_map(|(bcb, counter)| Some((bcb, counter.take()?)))
}
pub(super) fn drain_bcb_edge_counters(
&mut self,
) -> impl Iterator<Item = ((BasicCoverageBlock, BasicCoverageBlock), BcbCounter)> + '_ {
self.bcb_edge_counters.drain()
}
}
struct MakeBcbCounters<'a> {
coverage_counters: &'a mut CoverageCounters,
basic_coverage_blocks: &'a CoverageGraph,
}
impl<'a> MakeBcbCounters<'a> {
fn new(
coverage_counters: &'a mut CoverageCounters,
basic_coverage_blocks: &'a CoverageGraph,
) -> Self {
Self { coverage_counters, basic_coverage_blocks }
}
fn make_bcb_counters(
&mut self,
bcb_has_coverage_spans: impl Fn(BasicCoverageBlock) -> bool,
) -> Result<(), Error> {
debug!("make_bcb_counters(): adding a counter or expression to each BasicCoverageBlock");
let mut traversal = TraverseCoverageGraphWithLoops::new(&self.basic_coverage_blocks);
while let Some(bcb) = traversal.next(self.basic_coverage_blocks) {
if bcb_has_coverage_spans(bcb) {
debug!("{:?} has at least one coverage span. Get or make its counter", bcb);
let branching_counter_operand = self.get_or_make_counter_operand(bcb)?;
if self.bcb_needs_branch_counters(bcb) {
self.make_branch_counters(&mut traversal, bcb, branching_counter_operand)?;
}
} else {
debug!(
"{:?} does not have any coverage spans. A counter will only be added if \
and when a covered BCB has an expression dependency.",
bcb,
);
}
}
if traversal.is_complete() {
Ok(())
} else {
Error::from_string(format!(
"`TraverseCoverageGraphWithLoops` missed some `BasicCoverageBlock`s: {:?}",
traversal.unvisited(),
))
}
}
fn make_branch_counters(
&mut self,
traversal: &mut TraverseCoverageGraphWithLoops,
branching_bcb: BasicCoverageBlock,
branching_counter_operand: Operand,
) -> Result<(), Error> {
let branches = self.bcb_branches(branching_bcb);
debug!(
"{:?} has some branch(es) without counters:\n {}",
branching_bcb,
branches
.iter()
.map(|branch| { format!("{:?}: {:?}", branch, self.branch_counter(branch)) })
.collect::<Vec<_>>()
.join("\n "),
);
let expression_branch = self.choose_preferred_expression_branch(traversal, &branches);
let mut some_sumup_counter_operand = None;
for branch in branches {
if branch != expression_branch {
let branch_counter_operand = if branch.is_only_path_to_target() {
debug!(
" {:?} has only one incoming edge (from {:?}), so adding a \
counter",
branch, branching_bcb
);
self.get_or_make_counter_operand(branch.target_bcb)?
} else {
debug!(" {:?} has multiple incoming edges, so adding an edge counter", branch);
self.get_or_make_edge_counter_operand(branching_bcb, branch.target_bcb)?
};
if let Some(sumup_counter_operand) =
some_sumup_counter_operand.replace(branch_counter_operand)
{
let intermediate_expression = self.coverage_counters.make_expression(
branch_counter_operand,
Op::Add,
sumup_counter_operand,
);
debug!(" [new intermediate expression: {:?}]", intermediate_expression);
let intermediate_expression_operand = intermediate_expression.as_operand();
self.coverage_counters.intermediate_expressions.push(intermediate_expression);
some_sumup_counter_operand.replace(intermediate_expression_operand);
}
}
}
let sumup_counter_operand =
some_sumup_counter_operand.expect("sumup_counter_operand should have a value");
debug!(
"Making an expression for the selected expression_branch: {:?} \
(expression_branch predecessors: {:?})",
expression_branch,
self.bcb_predecessors(expression_branch.target_bcb),
);
let expression = self.coverage_counters.make_expression(
branching_counter_operand,
Op::Subtract,
sumup_counter_operand,
);
debug!("{:?} gets an expression: {:?}", expression_branch, expression);
let bcb = expression_branch.target_bcb;
if expression_branch.is_only_path_to_target() {
self.coverage_counters.set_bcb_counter(bcb, expression)?;
} else {
self.coverage_counters.set_bcb_edge_counter(branching_bcb, bcb, expression)?;
}
Ok(())
}
fn get_or_make_counter_operand(&mut self, bcb: BasicCoverageBlock) -> Result<Operand, Error> {
self.recursive_get_or_make_counter_operand(bcb, 1)
}
fn recursive_get_or_make_counter_operand(
&mut self,
bcb: BasicCoverageBlock,
debug_indent_level: usize,
) -> Result<Operand, Error> {
if let Some(counter_kind) = &self.coverage_counters.bcb_counters[bcb] {
debug!(
"{}{:?} already has a counter: {:?}",
NESTED_INDENT.repeat(debug_indent_level),
bcb,
counter_kind,
);
return Ok(counter_kind.as_operand());
}
let one_path_to_target = self.bcb_has_one_path_to_target(bcb);
if one_path_to_target || self.bcb_predecessors(bcb).contains(&bcb) {
let counter_kind = self.coverage_counters.make_counter();
if one_path_to_target {
debug!(
"{}{:?} gets a new counter: {:?}",
NESTED_INDENT.repeat(debug_indent_level),
bcb,
counter_kind,
);
} else {
debug!(
"{}{:?} has itself as its own predecessor. It can't be part of its own \
Expression sum, so it will get its own new counter: {:?}. (Note, the compiled \
code will generate an infinite loop.)",
NESTED_INDENT.repeat(debug_indent_level),
bcb,
counter_kind,
);
}
return self.coverage_counters.set_bcb_counter(bcb, counter_kind);
}
let mut predecessors = self.bcb_predecessors(bcb).to_owned().into_iter();
debug!(
"{}{:?} has multiple incoming edges and will get an expression that sums them up...",
NESTED_INDENT.repeat(debug_indent_level),
bcb,
);
let first_edge_counter_operand = self.recursive_get_or_make_edge_counter_operand(
predecessors.next().unwrap(),
bcb,
debug_indent_level + 1,
)?;
let mut some_sumup_edge_counter_operand = None;
for predecessor in predecessors {
let edge_counter_operand = self.recursive_get_or_make_edge_counter_operand(
predecessor,
bcb,
debug_indent_level + 1,
)?;
if let Some(sumup_edge_counter_operand) =
some_sumup_edge_counter_operand.replace(edge_counter_operand)
{
let intermediate_expression = self.coverage_counters.make_expression(
sumup_edge_counter_operand,
Op::Add,
edge_counter_operand,
);
debug!(
"{}new intermediate expression: {:?}",
NESTED_INDENT.repeat(debug_indent_level),
intermediate_expression
);
let intermediate_expression_operand = intermediate_expression.as_operand();
self.coverage_counters.intermediate_expressions.push(intermediate_expression);
some_sumup_edge_counter_operand.replace(intermediate_expression_operand);
}
}
let counter_kind = self.coverage_counters.make_expression(
first_edge_counter_operand,
Op::Add,
some_sumup_edge_counter_operand.unwrap(),
);
debug!(
"{}{:?} gets a new counter (sum of predecessor counters): {:?}",
NESTED_INDENT.repeat(debug_indent_level),
bcb,
counter_kind
);
self.coverage_counters.set_bcb_counter(bcb, counter_kind)
}
fn get_or_make_edge_counter_operand(
&mut self,
from_bcb: BasicCoverageBlock,
to_bcb: BasicCoverageBlock,
) -> Result<Operand, Error> {
self.recursive_get_or_make_edge_counter_operand(from_bcb, to_bcb, 1)
}
fn recursive_get_or_make_edge_counter_operand(
&mut self,
from_bcb: BasicCoverageBlock,
to_bcb: BasicCoverageBlock,
debug_indent_level: usize,
) -> Result<Operand, Error> {
let successors = self.bcb_successors(from_bcb).iter();
if successors.len() == 1 {
return self.recursive_get_or_make_counter_operand(from_bcb, debug_indent_level + 1);
}
if let Some(counter_kind) =
self.coverage_counters.bcb_edge_counters.get(&(from_bcb, to_bcb))
{
debug!(
"{}Edge {:?}->{:?} already has a counter: {:?}",
NESTED_INDENT.repeat(debug_indent_level),
from_bcb,
to_bcb,
counter_kind
);
return Ok(counter_kind.as_operand());
}
let counter_kind = self.coverage_counters.make_counter();
debug!(
"{}Edge {:?}->{:?} gets a new counter: {:?}",
NESTED_INDENT.repeat(debug_indent_level),
from_bcb,
to_bcb,
counter_kind
);
self.coverage_counters.set_bcb_edge_counter(from_bcb, to_bcb, counter_kind)
}
fn choose_preferred_expression_branch(
&self,
traversal: &TraverseCoverageGraphWithLoops,
branches: &[BcbBranch],
) -> BcbBranch {
let branch_needs_a_counter = |branch: &BcbBranch| self.branch_has_no_counter(branch);
let some_reloop_branch = self.find_some_reloop_branch(traversal, &branches);
if let Some(reloop_branch_without_counter) =
some_reloop_branch.filter(branch_needs_a_counter)
{
debug!(
"Selecting reloop_branch={:?} that still needs a counter, to get the \
`Expression`",
reloop_branch_without_counter
);
reloop_branch_without_counter
} else {
let &branch_without_counter =
branches.iter().find(|&branch| self.branch_has_no_counter(branch)).expect(
"needs_branch_counters was `true` so there should be at least one \
branch",
);
debug!(
"Selecting any branch={:?} that still needs a counter, to get the \
`Expression` because there was no `reloop_branch`, or it already had a \
counter",
branch_without_counter
);
branch_without_counter
}
}
fn find_some_reloop_branch(
&self,
traversal: &TraverseCoverageGraphWithLoops,
branches: &[BcbBranch],
) -> Option<BcbBranch> {
let branch_needs_a_counter = |branch: &BcbBranch| self.branch_has_no_counter(branch);
let mut some_reloop_branch: Option<BcbBranch> = None;
for context in traversal.context_stack.iter().rev() {
if let Some((backedge_from_bcbs, _)) = &context.loop_backedges {
let mut found_loop_exit = false;
for &branch in branches.iter() {
if backedge_from_bcbs.iter().any(|&backedge_from_bcb| {
self.bcb_dominates(branch.target_bcb, backedge_from_bcb)
}) {
if let Some(reloop_branch) = some_reloop_branch {
if self.branch_has_no_counter(&reloop_branch) {
continue;
}
}
some_reloop_branch = Some(branch);
} else {
found_loop_exit = true;
}
if found_loop_exit
&& some_reloop_branch.filter(branch_needs_a_counter).is_some()
{
break;
}
}
if !found_loop_exit {
debug!(
"No branches exit the loop, so any branch without an existing \
counter can have the `Expression`."
);
break;
}
if some_reloop_branch.is_some() {
debug!(
"Found a branch that exits the loop and a branch the loops back to \
the top of the loop (`reloop_branch`). The `reloop_branch` will \
get the `Expression`, as long as it still needs a counter."
);
break;
}
}
}
some_reloop_branch
}
#[inline]
fn bcb_predecessors(&self, bcb: BasicCoverageBlock) -> &[BasicCoverageBlock] {
&self.basic_coverage_blocks.predecessors[bcb]
}
#[inline]
fn bcb_successors(&self, bcb: BasicCoverageBlock) -> &[BasicCoverageBlock] {
&self.basic_coverage_blocks.successors[bcb]
}
#[inline]
fn bcb_branches(&self, from_bcb: BasicCoverageBlock) -> Vec<BcbBranch> {
self.bcb_successors(from_bcb)
.iter()
.map(|&to_bcb| BcbBranch::from_to(from_bcb, to_bcb, &self.basic_coverage_blocks))
.collect::<Vec<_>>()
}
fn bcb_needs_branch_counters(&self, bcb: BasicCoverageBlock) -> bool {
let branch_needs_a_counter = |branch: &BcbBranch| self.branch_has_no_counter(branch);
let branches = self.bcb_branches(bcb);
branches.len() > 1 && branches.iter().any(branch_needs_a_counter)
}
fn branch_has_no_counter(&self, branch: &BcbBranch) -> bool {
self.branch_counter(branch).is_none()
}
fn branch_counter(&self, branch: &BcbBranch) -> Option<&BcbCounter> {
let to_bcb = branch.target_bcb;
if let Some(from_bcb) = branch.edge_from_bcb {
self.coverage_counters.bcb_edge_counters.get(&(from_bcb, to_bcb))
} else {
self.coverage_counters.bcb_counters[to_bcb].as_ref()
}
}
#[inline]
fn bcb_has_one_path_to_target(&self, bcb: BasicCoverageBlock) -> bool {
self.bcb_predecessors(bcb).len() <= 1
}
#[inline]
fn bcb_dominates(&self, dom: BasicCoverageBlock, node: BasicCoverageBlock) -> bool {
self.basic_coverage_blocks.dominates(dom, node)
}
}