#![forbid(unsafe_code)]
#![deny(missing_docs)]
mod short;
mod skeleton;
mod tree;
use std::collections::BTreeSet;
use std::fmt;
use sealmap_model::{Codebase, SymbolId};
use crate::short::ShortNames;
use crate::skeleton::{one_line, order_key};
use crate::tree::{CallerWriter, Graph, TreeWriter};
pub const FORMAT_VERSION: u32 = 1;
pub const TEXT_FILE: &str = "dense.txt";
pub const INDEX_FILE: &str = "_index.txt";
const LEGEND: &str = "L<a>-<b> source lines; @name short names (see _index.txt); calls ~inferred ?external, ^ expanded above, ↺ cycle, … cut; tree roots: bare = entry point, … = continued, ↺ = cycle-only";
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct DenseOptions {
pub max_depth: usize,
}
impl Default for DenseOptions {
fn default() -> Self {
Self { max_depth: 3 }
}
}
impl DenseOptions {
pub fn with_max_depth(max_depth: usize) -> Self {
Self { max_depth: max_depth.max(1) }
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DenseOutput {
pub text: String,
pub index: String,
}
impl DenseOutput {
pub fn files(&self) -> [(&'static str, &str); 2] {
[(INDEX_FILE, &self.index), (TEXT_FILE, &self.text)]
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct SliceOptions {
pub depth: usize,
pub max_bytes: Option<usize>,
}
impl SliceOptions {
pub fn new(depth: usize) -> Self {
Self { depth, max_bytes: None }
}
pub fn max_bytes(mut self, max_bytes: usize) -> Self {
self.max_bytes = Some(max_bytes);
self
}
}
impl Default for SliceOptions {
fn default() -> Self {
Self::new(1)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum SliceError {
UnknownSymbols(Vec<SymbolId>),
OverBudget {
bytes: usize,
budget: usize,
seeds: Vec<(SymbolId, usize)>,
},
}
impl fmt::Display for SliceError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::UnknownSymbols(ids) => {
write!(f, "{} seed id(s) are not symbols of the codebase:", ids.len())?;
for id in ids {
write!(f, " {id};")?;
}
Ok(())
}
Self::OverBudget { bytes, budget, seeds } => {
write!(
f,
"dense slice is {bytes} bytes, {} over the {budget}-byte budget; refusing rather than truncating",
bytes - budget
)?;
if let Some((id, size)) = seeds.iter().max_by(|a, b| a.1.cmp(&b.1).then_with(|| b.0.cmp(&a.0))) {
write!(f, " (largest seed alone: {id} at {size} bytes)")?;
}
Ok(())
}
}
}
}
impl std::error::Error for SliceError {}
#[derive(Debug, Clone)]
pub struct Dense<'a> {
cb: &'a Codebase,
shorts: ShortNames<'a>,
graph: Graph<'a>,
}
impl<'a> Dense<'a> {
pub fn new(cb: &'a Codebase) -> Self {
Self { cb, shorts: ShortNames::new(cb), graph: Graph::new(cb) }
}
pub fn short(&self, id: &SymbolId) -> Option<&str> {
self.shorts.get(id)
}
pub fn resolve(&self, short: &str) -> Option<&'a SymbolId> {
self.shorts.resolve(short)
}
pub fn render(&self, options: &DenseOptions) -> DenseOutput {
DenseOutput { text: self.text(options), index: self.index() }
}
pub fn index(&self) -> String {
let mut out = String::new();
for (short, id) in self.shorts.iter() {
self.index_line(&mut out, short, id);
}
out
}
pub fn text(&self, options: &DenseOptions) -> String {
let mut out = self.header("");
out.push_str("# symbols\n");
skeleton::write_files(&mut out, self.cb, &self.shorts, self.cb.symbols.values());
out.push_str("# calls\n");
let mut writer = TreeWriter::new(self.cb, &self.shorts, &self.graph, options.max_depth.max(1), true);
let callables = self.in_source_order(self.graph.flows.keys().copied());
for &id in &callables {
if !self.graph.callers.contains_key(id) {
writer.root(id, "");
}
}
for &id in &callables {
if !writer.is_expanded(id) {
writer.root(id, " ↺");
}
}
out.push_str(&writer.out);
out
}
pub fn slice<'s, I>(&self, seeds: I, options: &SliceOptions) -> Result<String, SliceError>
where
I: IntoIterator<Item = &'s SymbolId>,
{
let mut known = BTreeSet::new();
let mut unknown = BTreeSet::new();
for id in seeds {
match self.cb.symbols.get_key_value(id) {
Some((k, _)) => {
known.insert(k);
}
None => {
unknown.insert(id.clone());
}
}
}
if !unknown.is_empty() {
return Err(SliceError::UnknownSymbols(unknown.into_iter().collect()));
}
let text = self.slice_text(&known, options.depth);
match options.max_bytes {
Some(budget) if text.len() > budget => {
let seeds = known
.iter()
.map(|id| ((*id).clone(), self.slice_text(&BTreeSet::from([*id]), options.depth).len()))
.collect();
Err(SliceError::OverBudget { bytes: text.len(), budget, seeds })
}
_ => Ok(text),
}
}
fn slice_text(&self, seeds: &BTreeSet<&'a SymbolId>, depth: usize) -> String {
let callees = self.reach(seeds, depth, |id| self.graph.callees.get(id).map(|s| s.iter().copied().collect()));
let callers = self.reach(seeds, depth, |id| self.graph.callers.get(id).map(|m| m.keys().copied().collect()));
let members: BTreeSet<&'a SymbolId> = seeds.iter().chain(&callees).chain(&callers).copied().collect();
let mut out = self.header(&format!(" slice depth {depth}"));
out.push_str("# symbols\n");
skeleton::write_files(&mut out, self.cb, &self.shorts, members.iter().filter_map(|id| self.cb.symbol(id)));
let ordered = self.in_source_order(seeds.iter().copied());
if depth > 0 {
let mut calls = TreeWriter::new(self.cb, &self.shorts, &self.graph, depth, false);
for &id in &ordered {
calls.root(id, "");
}
if !calls.out.is_empty() {
out.push_str("# calls\n");
out.push_str(&calls.out);
}
let mut up = CallerWriter::new(self.cb, &self.shorts, &self.graph, depth);
for &id in &ordered {
up.root(id);
}
if !up.out.is_empty() {
out.push_str("# callers\n");
out.push_str(&up.out);
}
}
out.push_str("# index\n");
let mut named: Vec<(&str, &SymbolId)> =
members.iter().filter_map(|id| self.shorts.get(id).map(|s| (s, *id))).collect();
named.sort();
for (short, id) in named {
self.index_line(&mut out, short, id);
}
out
}
fn reach(
&self,
seeds: &BTreeSet<&'a SymbolId>,
depth: usize,
next: impl Fn(&SymbolId) -> Option<Vec<&'a SymbolId>>,
) -> BTreeSet<&'a SymbolId> {
let mut seen: BTreeSet<&'a SymbolId> = seeds.clone();
let mut frontier: Vec<&'a SymbolId> = seeds.iter().copied().collect();
for _ in 0..depth {
let mut grown = Vec::new();
for id in frontier {
for n in next(id).unwrap_or_default() {
if seen.insert(n) {
grown.push(n);
}
}
}
frontier = grown;
}
seen.retain(|id| !seeds.contains(id));
seen
}
fn in_source_order(&self, ids: impl Iterator<Item = &'a SymbolId>) -> Vec<&'a SymbolId> {
let mut v: Vec<&'a SymbolId> = ids.collect();
v.sort_by(|a, b| match (self.cb.symbol(a), self.cb.symbol(b)) {
(Some(x), Some(y)) => order_key(x).cmp(&order_key(y)),
_ => a.cmp(b),
});
v
}
fn header(&self, kind: &str) -> String {
format!("# sealmap-dense {FORMAT_VERSION}{kind} {}: {LEGEND}\n", one_line(&self.cb.name))
}
fn index_line(&self, out: &mut String, short: &str, id: &SymbolId) {
out.push_str(short);
out.push(' ');
out.push_str(id.as_str());
if let Some(sym) = self.cb.symbol(id) {
out.push(' ');
encode_path(out, sym.file.as_str());
out.push(':');
skeleton::span(out, sym);
}
out.push('\n');
}
}
pub fn render(codebase: &Codebase, options: &DenseOptions) -> DenseOutput {
Dense::new(codebase).render(options)
}
pub fn slice<'s, I>(codebase: &Codebase, seeds: I, options: &SliceOptions) -> Result<String, SliceError>
where
I: IntoIterator<Item = &'s SymbolId>,
{
Dense::new(codebase).slice(seeds, options)
}
fn encode_path(out: &mut String, path: &str) {
for c in path.chars() {
if c == '%' || c.is_whitespace() || c.is_control() {
let mut buf = [0u8; 4];
for b in c.encode_utf8(&mut buf).bytes() {
out.push_str(&format!("%{b:02X}"));
}
} else {
out.push(c);
}
}
}
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct ReadmeDoctests;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn paths_are_encoded_injectively() {
let mut s = String::new();
encode_path(&mut s, "a b/100%.rs");
assert_eq!(s, "a%20b/100%25.rs");
}
}