// Copyright Kani Contributors
// SPDX-License-Identifier: Apache-2.0 OR MIT
//! This module implements a cross-crate collector that allow us to find all items that
//! should be included in order to verify one or more proof harness.
//!
//! This module works as following:
//! - Traverse all reachable items starting at the given starting points.
//! - For every function, traverse its body and collect the following:
//! - Constants / Static objects.
//! - Functions that are called or have their address taken.
//! - VTable methods for types that are coerced as unsized types.
//! - For every static, collect initializer and drop functions.
//!
//! We have kept this module agnostic of any Kani code in case we can contribute this back to rustc.
use tracing::{debug, debug_span, trace, warn};
use rustc_data_structures::fingerprint::Fingerprint;
use rustc_data_structures::fx::FxHashSet;
use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
use rustc_hir::def::DefKind;
use rustc_hir::def_id::DefId;
use rustc_hir::ItemId;
use rustc_middle::mir::interpret::{AllocId, ConstValue, ErrorHandled, GlobalAlloc, Scalar};
use rustc_middle::mir::mono::MonoItem;
use rustc_middle::mir::visit::Visitor as MirVisitor;
use rustc_middle::mir::{
Body, CastKind, Constant, ConstantKind, Location, Rvalue, Terminator, TerminatorKind,
};
use rustc_middle::span_bug;
use rustc_middle::ty::adjustment::PointerCast;
use rustc_middle::ty::{
Closure, ClosureKind, ConstKind, EarlyBinder, Instance, InstanceDef, ParamEnv, Ty, TyCtxt,
TyKind, TypeFoldable, VtblEntry,
};
use crate::kani_middle::coercion;
use crate::kani_middle::stubbing::get_stub;
/// Collect all reachable items starting from the given starting points.
pub fn collect_reachable_items<'tcx>(
tcx: TyCtxt<'tcx>,
starting_points: &[MonoItem<'tcx>],
) -> Vec<MonoItem<'tcx>> {
// For each harness, collect items using the same collector.
// I.e.: This will return any item that is reachable from one or more of the starting points.
let mut collector = MonoItemsCollector::new(tcx);
for item in starting_points {
collector.collect(*item);
}
#[cfg(debug_assertions)]
collector
.call_graph
.dump_dot(tcx)
.unwrap_or_else(|e| tracing::error!("Failed to dump call graph: {e}"));
tcx.sess.abort_if_errors();
// Sort the result so code generation follows deterministic order.
// This helps us to debug the code, but it also provides the user a good experience since the
// order of the errors and warnings is stable.
let mut sorted_items: Vec<_> = collector.collected.into_iter().collect();
sorted_items.sort_by_cached_key(|item| to_fingerprint(tcx, item));
sorted_items
}
/// Collect all (top-level) items in the crate that matches the given predicate.
/// An item can only be a root if they are: non-generic Fn / Static / GlobalASM
pub fn filter_crate_items<F>(tcx: TyCtxt, predicate: F) -> Vec<MonoItem>
where
F: Fn(TyCtxt, DefId) -> bool,
{
let crate_items = tcx.hir_crate_items(());
// Filter regular items.
let root_items = crate_items.items().filter_map(|item| {
let def_id = item.owner_id.def_id.to_def_id();
if !is_generic(tcx, def_id) && predicate(tcx, def_id) {
to_mono_root(tcx, item, def_id)
} else {
None
}
});
// Filter items from implementation blocks.
let impl_items = crate_items.impl_items().filter_map(|impl_item| {
let def_id = impl_item.owner_id.def_id.to_def_id();
if matches!(tcx.def_kind(def_id), DefKind::AssocFn)
&& !is_generic(tcx, def_id)
&& predicate(tcx, def_id)
{
Some(MonoItem::Fn(Instance::mono(tcx, def_id)))
} else {
None
}
});
root_items.chain(impl_items).collect()
}
/// Use a predicate to find `const` declarations, then extract all items reachable from them.
///
/// Probably only specifically useful with a predicate to find `TestDescAndFn` const declarations from
/// tests and extract the closures from them.
pub fn filter_const_crate_items<F>(tcx: TyCtxt, mut predicate: F) -> Vec<MonoItem>
where
F: FnMut(TyCtxt, DefId) -> bool,
{
let mut roots = Vec::new();
for hir_id in tcx.hir_crate_items(()).items() {
let def_id = hir_id.owner_id.def_id.to_def_id();
let def_kind = tcx.def_kind(def_id);
if matches!(def_kind, DefKind::Const) && predicate(tcx, def_id) {
let instance = Instance::mono(tcx, def_id);
let body = tcx.instance_mir(InstanceDef::Item(def_id));
let mut collector =
MonoItemsFnCollector { tcx, body, instance, collected: FxHashSet::default() };
collector.visit_body(body);
roots.extend(collector.collected);
}
}
roots
}
fn is_generic(tcx: TyCtxt, def_id: DefId) -> bool {
let generics = tcx.generics_of(def_id);
generics.requires_monomorphization(tcx)
}
fn to_mono_root(tcx: TyCtxt, item_id: ItemId, def_id: DefId) -> Option<MonoItem> {
let kind = tcx.def_kind(def_id);
match kind {
DefKind::Static(..) => Some(MonoItem::Static(def_id)),
DefKind::Fn => Some(MonoItem::Fn(Instance::mono(tcx, def_id))),
DefKind::GlobalAsm => Some(MonoItem::GlobalAsm(item_id)),
_ => {
debug!(?def_id, ?kind, "Ignored item. Not a root type.");
None
}
}
}
struct MonoItemsCollector<'tcx> {
/// The compiler context.
tcx: TyCtxt<'tcx>,
/// Set of collected items used to avoid entering recursion loops.
collected: FxHashSet<MonoItem<'tcx>>,
/// Items enqueued for visiting.
queue: Vec<MonoItem<'tcx>>,
#[cfg(debug_assertions)]
call_graph: debug::CallGraph<'tcx>,
}
impl<'tcx> MonoItemsCollector<'tcx> {
pub fn new(tcx: TyCtxt<'tcx>) -> Self {
MonoItemsCollector {
tcx,
collected: FxHashSet::default(),
queue: vec![],
#[cfg(debug_assertions)]
call_graph: debug::CallGraph::default(),
}
}
/// Collects all reachable items starting from the given root.
pub fn collect(&mut self, root: MonoItem<'tcx>) {
debug!(?root, "collect");
self.queue.push(root);
self.reachable_items();
}
/// Traverses the call graph starting from the given root. For every function, we visit all
/// instruction looking for the items that should be included in the compilation.
fn reachable_items(&mut self) {
while let Some(to_visit) = self.queue.pop() {
if !self.collected.contains(&to_visit) {
self.collected.insert(to_visit);
let next_items = match to_visit {
MonoItem::Fn(instance) => self.visit_fn(instance),
MonoItem::Static(def_id) => self.visit_static(def_id),
MonoItem::GlobalAsm(_) => {
self.visit_asm(to_visit);
vec![]
}
};
#[cfg(debug_assertions)]
self.call_graph.add_edges(to_visit, &next_items);
self.queue
.extend(next_items.into_iter().filter(|item| !self.collected.contains(item)));
}
}
}
/// Visit a function and collect all mono-items reachable from its instructions.
fn visit_fn(&mut self, instance: Instance<'tcx>) -> Vec<MonoItem<'tcx>> {
let _guard = debug_span!("visit_fn", function=?instance).entered();
let body = self.tcx.instance_mir(instance.def);
let mut collector =
MonoItemsFnCollector { tcx: self.tcx, collected: FxHashSet::default(), instance, body };
collector.visit_body(body);
collector.collected.into_iter().collect()
}
/// Visit a static object and collect drop / initialization functions.
fn visit_static(&mut self, def_id: DefId) -> Vec<MonoItem<'tcx>> {
let _guard = debug_span!("visit_static", ?def_id).entered();
let instance = Instance::mono(self.tcx, def_id);
let mut next_items = vec![];
// Collect drop function.
let static_ty = instance.ty(self.tcx, ParamEnv::reveal_all());
let instance = Instance::resolve_drop_in_place(self.tcx, static_ty);
next_items.push(MonoItem::Fn(instance.polymorphize(self.tcx)));
// Collect initialization.
let alloc = self.tcx.eval_static_initializer(def_id).unwrap();
for id in alloc.inner().provenance().provenances() {
next_items.extend(collect_alloc_items(self.tcx, id).iter());
}
next_items
}
/// Visit global assembly and collect its item.
fn visit_asm(&mut self, item: MonoItem<'tcx>) {
debug!(?item, "visit_asm");
}
}
struct MonoItemsFnCollector<'a, 'tcx> {
tcx: TyCtxt<'tcx>,
collected: FxHashSet<MonoItem<'tcx>>,
instance: Instance<'tcx>,
body: &'a Body<'tcx>,
}
impl<'a, 'tcx> MonoItemsFnCollector<'a, 'tcx> {
fn monomorphize<T>(&self, value: T) -> T
where
T: TypeFoldable<TyCtxt<'tcx>>,
{
trace!(instance=?self.instance, ?value, "monomorphize");
self.instance.subst_mir_and_normalize_erasing_regions(
self.tcx,
ParamEnv::reveal_all(),
EarlyBinder::bind(value),
)
}
/// Collect the implementation of all trait methods and its supertrait methods for the given
/// concrete type.
fn collect_vtable_methods(&mut self, concrete_ty: Ty<'tcx>, trait_ty: Ty<'tcx>) {
trace!(?concrete_ty, ?trait_ty, "collect_vtable_methods");
assert!(!concrete_ty.is_trait(), "Expected a concrete type, but found: {concrete_ty:?}");
assert!(trait_ty.is_trait(), "Expected a trait: {trait_ty:?}");
if let TyKind::Dynamic(trait_list, ..) = trait_ty.kind() {
// A trait object type can have multiple trait bounds but up to one non-auto-trait
// bound. This non-auto-trait, named principal, is the only one that can have methods.
// https://doc.rust-lang.org/reference/special-types-and-traits.html#auto-traits
if let Some(principal) = trait_list.principal() {
let poly_trait_ref = principal.with_self_ty(self.tcx, concrete_ty);
// Walk all methods of the trait, including those of its supertraits
let entries = self.tcx.vtable_entries(poly_trait_ref);
let methods = entries.iter().filter_map(|entry| match entry {
VtblEntry::MetadataAlign
| VtblEntry::MetadataDropInPlace
| VtblEntry::MetadataSize
| VtblEntry::Vacant => None,
VtblEntry::TraitVPtr(_) => {
// all super trait items already covered, so skip them.
None
}
VtblEntry::Method(instance) if should_codegen_locally(self.tcx, instance) => {
Some(MonoItem::Fn(instance.polymorphize(self.tcx)))
}
VtblEntry::Method(..) => None,
});
trace!(methods=?methods.clone().collect::<Vec<_>>(), "collect_vtable_methods");
self.collected.extend(methods);
}
}
// Add the destructor for the concrete type.
let instance = Instance::resolve_drop_in_place(self.tcx, concrete_ty);
self.collect_instance(instance, false);
}
/// Collect an instance depending on how it is used (invoked directly or via fn_ptr).
fn collect_instance(&mut self, instance: Instance<'tcx>, is_direct_call: bool) {
let should_collect = match instance.def {
InstanceDef::Virtual(..) | InstanceDef::Intrinsic(_) => {
// Instance definition has no body.
assert!(is_direct_call, "Expected direct call {instance:?}");
false
}
InstanceDef::DropGlue(_, None) => {
// Only need the glue if we are not calling it directly.
!is_direct_call
}
InstanceDef::CloneShim(..)
| InstanceDef::ClosureOnceShim { .. }
| InstanceDef::DropGlue(_, Some(_))
| InstanceDef::FnPtrShim(..)
| InstanceDef::Item(..)
| InstanceDef::ReifyShim(..)
| InstanceDef::VTableShim(..) => true,
InstanceDef::ThreadLocalShim(_) | InstanceDef::FnPtrAddrShim(_, _) => true,
};
if should_collect && should_codegen_locally(self.tcx, &instance) {
trace!(?instance, "collect_instance");
self.collected.insert(MonoItem::Fn(instance.polymorphize(self.tcx)));
}
}
/// Collect constant values represented by static variables.
fn collect_const_value(&mut self, value: ConstValue<'tcx>) {
debug!(?value, "collect_const_value");
match value {
ConstValue::Scalar(Scalar::Ptr(ptr, _size)) => {
self.collected.extend(collect_alloc_items(self.tcx, ptr.provenance).iter());
}
ConstValue::Slice { data: alloc, start: _, end: _ }
| ConstValue::ByRef { alloc, .. } => {
for id in alloc.inner().provenance().provenances() {
self.collected.extend(collect_alloc_items(self.tcx, id).iter())
}
}
_ => {}
}
}
}
/// Visit every instruction in a function and collect the following:
/// 1. Every function / method / closures that may be directly invoked.
/// 2. Every function / method / closures that may have their address taken.
/// 3. Every method that compose the impl of a trait for a given type when there's a conversion
/// from the type to the trait.
/// - I.e.: If we visit the following code:
/// ```
/// let var = MyType::new();
/// let ptr : &dyn MyTrait = &var;
/// ```
/// We collect the entire implementation of `MyTrait` for `MyType`.
/// 4. Every Static variable that is referenced in the function or constant used in the function.
/// 5. Drop glue.
/// 6. Static Initialization
/// This code has been mostly taken from `rustc_monomorphize::collector::MirNeighborCollector`.
impl<'a, 'tcx> MirVisitor<'tcx> for MonoItemsFnCollector<'a, 'tcx> {
/// Collect the following:
/// - Trait implementations when casting from concrete to dyn Trait.
/// - Functions / Closures that have their address taken.
/// - Thread Local.
fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
trace!(rvalue=?*rvalue, "visit_rvalue");
match *rvalue {
Rvalue::Cast(CastKind::Pointer(PointerCast::Unsize), ref operand, target) => {
// Check if the conversion include casting a concrete type to a trait type.
// If so, collect items from the impl `Trait for Concrete {}`.
let target_ty = self.monomorphize(target);
let source_ty = self.monomorphize(operand.ty(self.body, self.tcx));
let base_coercion =
coercion::extract_unsize_casting(self.tcx, source_ty, target_ty);
if !base_coercion.src_ty.is_trait() && base_coercion.dst_ty.is_trait() {
debug!(?base_coercion, "collect_vtable_methods");
self.collect_vtable_methods(base_coercion.src_ty, base_coercion.dst_ty);
}
}
Rvalue::Cast(CastKind::Pointer(PointerCast::ReifyFnPointer), ref operand, _) => {
let fn_ty = operand.ty(self.body, self.tcx);
let fn_ty = self.monomorphize(fn_ty);
if let TyKind::FnDef(def_id, substs) = *fn_ty.kind() {
let instance = Instance::resolve_for_fn_ptr(
self.tcx,
ParamEnv::reveal_all(),
def_id,
substs,
)
.unwrap();
self.collect_instance(instance, false);
} else {
unreachable!("Expected FnDef type, but got: {:?}", fn_ty);
}
}
Rvalue::Cast(CastKind::Pointer(PointerCast::ClosureFnPointer(_)), ref operand, _) => {
let source_ty = operand.ty(self.body, self.tcx);
let source_ty = self.monomorphize(source_ty);
match *source_ty.kind() {
Closure(def_id, substs) => {
let instance = Instance::resolve_closure(
self.tcx,
def_id,
substs,
ClosureKind::FnOnce,
)
.expect("failed to normalize and resolve closure during codegen");
self.collect_instance(instance, false);
}
_ => unreachable!("Unexpected type: {:?}", source_ty),
}
}
Rvalue::ThreadLocalRef(def_id) => {
assert!(self.tcx.is_thread_local_static(def_id));
trace!(?def_id, "visit_rvalue thread_local");
let instance = Instance::mono(self.tcx, def_id);
if should_codegen_locally(self.tcx, &instance) {
trace!("collecting thread-local static {:?}", def_id);
self.collected.insert(MonoItem::Static(def_id));
}
}
_ => { /* not interesting */ }
}
self.super_rvalue(rvalue, location);
}
/// Collect constants that are represented as static variables.
fn visit_constant(&mut self, constant: &Constant<'tcx>, location: Location) {
let literal = self.monomorphize(constant.literal);
debug!(?constant, ?location, ?literal, "visit_constant");
let val = match literal {
ConstantKind::Val(const_val, _) => const_val,
ConstantKind::Ty(ct) => match ct.kind() {
ConstKind::Value(v) => self.tcx.valtree_to_const_val((ct.ty(), v)),
ConstKind::Unevaluated(_) => unreachable!(),
// Nothing to do
ConstKind::Param(..)
| ConstKind::Infer(..)
| ConstKind::Error(..)
| ConstKind::Expr(..) => return,
// Shouldn't happen
ConstKind::Placeholder(..) | ConstKind::Bound(..) => {
unreachable!("Unexpected constant type {:?} ({:?})", ct, ct.kind())
}
},
ConstantKind::Unevaluated(un_eval, _) => {
// Thread local fall into this category.
match self.tcx.const_eval_resolve(ParamEnv::reveal_all(), un_eval, None) {
// The `monomorphize` call should have evaluated that constant already.
Ok(const_val) => const_val,
Err(ErrorHandled::TooGeneric) => span_bug!(
self.body.source_info(location).span,
"Unexpected polymorphic constant: {:?}",
literal
),
Err(error) => {
warn!(?error, "Error already reported");
return;
}
}
}
};
self.collect_const_value(val);
}
/// Collect function calls.
fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
trace!(?terminator, ?location, "visit_terminator");
let tcx = self.tcx;
match terminator.kind {
TerminatorKind::Call { ref func, ref args, .. } => {
let callee_ty = func.ty(self.body, tcx);
let fn_ty = self.monomorphize(callee_ty);
if let TyKind::FnDef(def_id, substs) = *fn_ty.kind() {
let instance_opt =
Instance::resolve(self.tcx, ParamEnv::reveal_all(), def_id, substs)
.unwrap();
match instance_opt {
None => {
let caller = tcx.def_path_str(self.instance.def_id());
let callee = tcx.def_path_str(def_id);
// Check if the current function has been stubbed.
if let Some(stub) = get_stub(tcx, self.instance.def_id()) {
// During the MIR stubbing transformation, we do not
// force type variables in the stub's signature to
// implement the same traits as those in the
// original function/method. A trait mismatch shows
// up here, when we try to resolve a trait method
let generic_ty = args[0].ty(self.body, tcx).peel_refs();
let receiver_ty = tcx.subst_and_normalize_erasing_regions(
substs,
ParamEnv::reveal_all(),
EarlyBinder::bind(generic_ty),
);
let sep = callee.rfind("::").unwrap();
let trait_ = &callee[..sep];
tcx.sess.span_err(
terminator.source_info.span,
format!(
"`{receiver_ty}` doesn't implement \
`{trait_}`. The function `{caller}` \
cannot be stubbed by `{}` due to \
generic bounds not being met.",
tcx.def_path_str(stub)
),
);
} else {
panic!("unable to resolve call to `{callee}` in `{caller}`")
}
}
Some(instance) => self.collect_instance(instance, true),
};
} else {
assert!(
matches!(fn_ty.kind(), TyKind::FnPtr(..)),
"Unexpected type: {fn_ty:?}"
);
}
}
TerminatorKind::Drop { ref place, .. } => {
let place_ty = place.ty(self.body, self.tcx).ty;
let place_mono_ty = self.monomorphize(place_ty);
let instance = Instance::resolve_drop_in_place(self.tcx, place_mono_ty);
self.collect_instance(instance, true);
}
TerminatorKind::InlineAsm { .. } => {
// We don't support inline assembly. This shall be replaced by an unsupported
// construct during codegen.
}
TerminatorKind::Terminate { .. } | TerminatorKind::Assert { .. } => {
// We generate code for this without invoking any lang item.
}
TerminatorKind::Goto { .. }
| TerminatorKind::SwitchInt { .. }
| TerminatorKind::Resume
| TerminatorKind::Return
| TerminatorKind::Unreachable => {}
TerminatorKind::GeneratorDrop
| TerminatorKind::Yield { .. }
| TerminatorKind::FalseEdge { .. }
| TerminatorKind::FalseUnwind { .. } => {
unreachable!("Unexpected at this MIR level")
}
}
self.super_terminator(terminator, location);
}
}
/// Convert a `MonoItem` into a stable `Fingerprint` which can be used as a stable hash across
/// compilation sessions. This allow us to provide a stable deterministic order to codegen.
fn to_fingerprint(tcx: TyCtxt, item: &MonoItem) -> Fingerprint {
tcx.with_stable_hashing_context(|mut hcx| {
let mut hasher = StableHasher::new();
item.hash_stable(&mut hcx, &mut hasher);
hasher.finish()
})
}
/// Return whether we should include the item into codegen.
/// - We only skip foreign items.
///
/// Note: Ideally, we should be able to assert that the MIR for non-foreign items are available via
/// call to `tcx.is_mir_available (def_id)`.
/// However, we found an issue where this function was returning `false` for a mutable static
/// item with constant initializer from an upstream crate.
/// See <https://github.com/model-checking/kani/issues/1760> for an example.
fn should_codegen_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: &Instance<'tcx>) -> bool {
if let Some(def_id) = instance.def.def_id_if_not_guaranteed_local_codegen() {
// We cannot codegen foreign items.
!tcx.is_foreign_item(def_id)
} else {
// This will include things like VTableShim and other stuff. See the method
// def_id_if_not_guaranteed_local_codegen for the full list.
true
}
}
/// Scans the allocation type and collect static objects.
fn collect_alloc_items(tcx: TyCtxt, alloc_id: AllocId) -> Vec<MonoItem> {
trace!(alloc=?tcx.global_alloc(alloc_id), ?alloc_id, "collect_alloc_items");
let mut items = vec![];
match tcx.global_alloc(alloc_id) {
GlobalAlloc::Static(def_id) => {
// This differ from rustc's collector since rustc does not include static from
// upstream crates.
assert!(!tcx.is_thread_local_static(def_id));
let instance = Instance::mono(tcx, def_id);
should_codegen_locally(tcx, &instance).then(|| items.push(MonoItem::Static(def_id)));
}
GlobalAlloc::Function(instance) => {
should_codegen_locally(tcx, &instance)
.then(|| items.push(MonoItem::Fn(instance.polymorphize(tcx))));
}
GlobalAlloc::Memory(alloc) => {
items.extend(
alloc
.inner()
.provenance()
.provenances()
.flat_map(|id| collect_alloc_items(tcx, id)),
);
}
GlobalAlloc::VTable(ty, trait_ref) => {
let vtable_id = tcx.vtable_allocation((ty, trait_ref));
items.append(&mut collect_alloc_items(tcx, vtable_id));
}
};
items
}
#[cfg(debug_assertions)]
mod debug {
#![allow(dead_code)]
use std::{
collections::{HashMap, HashSet},
fs::File,
io::{BufWriter, Write},
};
use rustc_session::config::OutputType;
use super::*;
#[derive(Debug, Default)]
pub struct CallGraph<'tcx> {
// Nodes of the graph.
nodes: HashSet<Node<'tcx>>,
edges: HashMap<Node<'tcx>, Vec<Node<'tcx>>>,
back_edges: HashMap<Node<'tcx>, Vec<Node<'tcx>>>,
}
type Node<'tcx> = MonoItem<'tcx>;
impl<'tcx> CallGraph<'tcx> {
pub fn add_node(&mut self, item: Node<'tcx>) {
self.nodes.insert(item);
self.edges.entry(item).or_default();
self.back_edges.entry(item).or_default();
}
/// Add a new edge "from" -> "to".
pub fn add_edge(&mut self, from: Node<'tcx>, to: Node<'tcx>) {
self.add_node(from);
self.add_node(to);
self.edges.get_mut(&from).unwrap().push(to);
self.back_edges.get_mut(&to).unwrap().push(from);
}
/// Add multiple new edges for the "from" node.
pub fn add_edges(&mut self, from: Node<'tcx>, to: &[Node<'tcx>]) {
self.add_node(from);
for item in to {
self.add_edge(from, *item);
}
}
/// Print the graph in DOT format to a file.
/// See <https://graphviz.org/doc/info/lang.html> for more information.
pub fn dump_dot(&self, tcx: TyCtxt) -> std::io::Result<()> {
if let Ok(target) = std::env::var("KANI_REACH_DEBUG") {
debug!(?target, "dump_dot");
let outputs = tcx.output_filenames(());
let path = outputs.output_path(OutputType::Metadata).with_extension("dot");
let out_file = File::create(&path)?;
let mut writer = BufWriter::new(out_file);
writeln!(writer, "digraph ReachabilityGraph {{")?;
if target.is_empty() {
self.dump_all(&mut writer)?;
} else {
// Only dump nodes that led the reachability analysis to the target node.
self.dump_reason(&mut writer, &target)?;
}
writeln!(writer, "}}")?;
}
Ok(())
}
/// Write all notes to the given writer.
fn dump_all<W: Write>(&self, writer: &mut W) -> std::io::Result<()> {
tracing::info!(nodes=?self.nodes.len(), edges=?self.edges.len(), "dump_all");
for node in &self.nodes {
writeln!(writer, r#""{node}""#)?;
for succ in self.edges.get(node).unwrap() {
writeln!(writer, r#""{node}" -> "{succ}" "#)?;
}
}
Ok(())
}
/// Write all notes that may have led to the discovery of the given target.
fn dump_reason<W: Write>(&self, writer: &mut W, target: &str) -> std::io::Result<()> {
let mut queue = self
.nodes
.iter()
.filter(|item| item.to_string().contains(target))
.collect::<Vec<_>>();
let mut visited: HashSet<&MonoItem> = HashSet::default();
tracing::info!(target=?queue, nodes=?self.nodes.len(), edges=?self.edges.len(), "dump_reason");
while let Some(to_visit) = queue.pop() {
if !visited.contains(to_visit) {
visited.insert(to_visit);
queue.extend(self.back_edges.get(to_visit).unwrap());
}
}
for node in &visited {
writeln!(writer, r#""{node}""#)?;
for succ in
self.edges.get(node).unwrap().iter().filter(|item| visited.contains(item))
{
writeln!(writer, r#""{node}" -> "{succ}" "#)?;
}
}
Ok(())
}
}
}