Skip to main content

sealmap_dense/
lib.rs

1//! # sealmap-dense
2//!
3//! The compact **agent projection** of a [`sealmap_model::Codebase`]: what an
4//! LLM agent reads instead of the source, or instead of a Mermaid corpus,
5//! when it needs the shape of a codebase. Measured on sealmap's own tree it
6//! costs well under half the bytes of the source it describes, while carrying
7//! what source leaves implicit: the resolved call graph, with every edge
8//! marked exact, inferred or external.
9//!
10//! The projection is a pure function of the model: the same codebase and
11//! options give byte-identical text on every run and every machine.
12//!
13//! ## What it writes
14//!
15//! [`Dense::render`] produces two texts, normally written to
16//! [`TEXT_FILE`] and [`INDEX_FILE`]:
17//!
18//! ```text
19//! # sealmap-dense 1 warehouse: 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
20//! # symbols
21//! ## src/inventory.rs
22//! pub trait StockStore { fn reserve(&mut self, sku: &str, qty: u32) -> Result<(), StockError>, fn lookup(&self, sku: &str) -> u32 } L3-9 @StockStore
23//! pub struct InventoryLedger { levels: BTreeMap<String, u32>, journal: Vec<String> } : StockStore L17-20 @inventory/InventoryLedger
24//! pub fn reserve(&mut self, sku: &str, qty: u32) -> Result<(), StockError> L33-40 @InventoryLedger.reserve
25//! …
26//! # calls
27//! place
28//!  orders/validate(&order)
29//!   loop each via all
30//!    inventory/validate(&line.sku)
31//!  opt !validate(&order)
32//!   return Ok(0)
33//!  loop for line in &order.lines
34//!   InventoryLedger.reserve(&line.sku, line.qty)?
35//!    StockStore.available(sku)
36//!    opt have<qty
37//!     return Err(StockError::Short { sku: sku.into(), wanted:…
38//!    InventoryLedger.record(_)
39//!  notify(len()).await
40//!   ?serde_json::to_string(&count)
41//! ```
42//!
43//! * **Skeleton lines**, one per symbol, grouped by file and in source order:
44//!   visibility, the signature as written (or the kind and name), fields or
45//!   variants inline (field visibility is left out), implemented traits after
46//!   ` : `, the line span `L<start>-<end>`, and the short name after `@`.
47//! * **Call trees**, each call indented one space under its caller, with
48//!   `alt`/`else`, `opt`, `loop`, `par`/`and` and early-exit lines from the
49//!   flow. Every callable is expanded **once**: afterwards a call to it ends
50//!   in `^`, a call back into a callable still being expanded ends in `↺`,
51//!   and a call reached at the depth limit ends in `…`. So the trees grow
52//!   with the number of call sites, not the number of paths, and every call
53//!   site appears exactly once.
54//! * **Tree headers** (unindented lines) say why the tree exists: a bare name
55//!   is an *entry point*, which nothing in the codebase calls; `name …`
56//!   continues a call cut above; `name ↺` is a callable reached only through
57//!   a cycle.
58//! * **Confidence marks** prefix a call: nothing for exact, `~` for inferred,
59//!   `?` for external. A trailing `.await` or `?` is the call site's own.
60//!   Internal callees are named by short name, others by their path.
61//! * **The index** (`_index.txt`), one line per symbol ordered by short name:
62//!   `<short> <sym:id> <path>:L<start>-<end>`. The short name is the first
63//!   field and contains no whitespace; the location is the last field (`%`
64//!   and whitespace in a path are percent-encoded); the `sym:` id is
65//!   everything between.
66//!
67//! Short names are unique within an output and derived from the ids alone:
68//! `Db.insert` for a method, `connect` for a function, `db/` for a module.
69//! Where two symbols would share one, *both* are qualified, step by step:
70//! the trait-impl block (`Db[Store].put`), the module path (`db/Db.put`),
71//! the package (`shop:db/Db.put`), then a hash of the id.
72//!
73//! ## Slices
74//!
75//! [`Dense::slice`] is what a review pack (`sealmap_corpus::pack`) embeds: the dense text for a set of
76//! symbols plus their callers and callees to a depth, with its own index
77//! section, byte-identical for identical inputs. With a byte budget it
78//! **refuses** an oversized slice with [`SliceError::OverBudget`], naming the
79//! overflow and the size of each seed alone, rather than truncating.
80//!
81//! ## Example
82//!
83//! ```
84//! use sealmap_model::*;
85//! use sealmap_dense::{Dense, DenseOptions, SliceError, SliceOptions};
86//!
87//! let pkg = Package::current("cargo", "shop").unwrap();
88//! let root = SymbolId::package_root(pkg);
89//! let db = root.child(Descriptor::r#type("Db")).unwrap();
90//! let insert = db.child(Descriptor::method("insert")).unwrap();
91//! let place = root.child(Descriptor::method("place")).unwrap();
92//! let file = SourcePath::new("src/lib.rs").unwrap();
93//!
94//! let mut cb = Codebase::new("shop");
95//! cb.add_symbol(Symbol::new(db.clone(), "Db", SymbolKind::Struct, file.clone()));
96//! let mut m = Symbol::new(insert.clone(), "insert", SymbolKind::Method, file.clone());
97//! m.signature = Some("pub fn insert(&mut self, id: u64)".into());
98//! m.visibility = Visibility::Public;
99//! m.span = Span::new(4, 5, 6, 6);
100//! cb.add_symbol(m);
101//! let mut f = Symbol::new(place.clone(), "place", SymbolKind::Function, file.clone());
102//! f.signature = Some("fn place(db: &mut Db)".into());
103//! f.span = Span::new(8, 1, 10, 2);
104//! f.flow = Some(Flow::new(vec![Step::Call(Call::new(insert.clone(), "insert(7)", Confidence::Exact))]));
105//! cb.add_symbol(f);
106//!
107//! let dense = Dense::new(&cb);
108//! let out = dense.render(&DenseOptions::default());
109//! assert!(out.text.contains("pub fn insert(&mut self, id: u64) L4-6 @Db.insert\n"));
110//! assert!(out.text.ends_with("# calls\nplace\n Db.insert(7)\n"));
111//! assert_eq!(dense.resolve("Db.insert"), Some(&insert));
112//! assert!(out.index.contains("Db.insert sym:cargo shop . Db#insert(). src/lib.rs:L4-6\n"));
113//!
114//! // A slice around `insert`, refused when it does not fit.
115//! let slice = dense.slice([&insert], &SliceOptions::new(1)).unwrap();
116//! assert!(slice.contains("# callers\nDb.insert\n place\n"));
117//! let err = dense.slice([&insert], &SliceOptions::new(1).max_bytes(64)).unwrap_err();
118//! assert!(matches!(err, SliceError::OverBudget { budget: 64, .. }));
119//! ```
120
121#![forbid(unsafe_code)]
122#![deny(missing_docs)]
123
124mod short;
125mod skeleton;
126mod tree;
127
128use std::collections::BTreeSet;
129use std::fmt;
130
131use sealmap_model::{Codebase, SymbolId};
132
133use crate::short::ShortNames;
134use crate::skeleton::{one_line, order_key};
135use crate::tree::{CallerWriter, Graph, TreeWriter};
136
137/// Version of the dense text format, written in its first line.
138///
139/// Bumped whenever the meaning of a mark or the layout of a line changes, so
140/// a tool reading the text can refuse a version it does not know.
141pub const FORMAT_VERSION: u32 = 1;
142
143/// File name for [`DenseOutput::text`] in a generated directory.
144pub const TEXT_FILE: &str = "dense.txt";
145
146/// File name for [`DenseOutput::index`] in a generated directory.
147pub const INDEX_FILE: &str = "_index.txt";
148
149/// The legend after the first line's codebase name.
150const 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";
151
152/// Options for the full projection.
153#[derive(Debug, Clone, PartialEq, Eq)]
154#[non_exhaustive]
155pub struct DenseOptions {
156    /// Call levels expanded beneath a tree's root before a callee is cut
157    /// (`…`) and given a tree of its own. At least 1; default 3.
158    pub max_depth: usize,
159}
160
161impl Default for DenseOptions {
162    fn default() -> Self {
163        Self { max_depth: 3 }
164    }
165}
166
167impl DenseOptions {
168    /// Options with a given depth limit (clamped to at least 1).
169    ///
170    /// ```
171    /// assert_eq!(sealmap_dense::DenseOptions::with_max_depth(0).max_depth, 1);
172    /// ```
173    pub fn with_max_depth(max_depth: usize) -> Self {
174        Self { max_depth: max_depth.max(1) }
175    }
176}
177
178/// The two texts of a full projection.
179#[derive(Debug, Clone, PartialEq, Eq)]
180pub struct DenseOutput {
181    /// Skeletons and call trees ([`TEXT_FILE`]).
182    pub text: String,
183    /// One `<short> <sym:id> <path>:L<a>-<b>` line per symbol ([`INDEX_FILE`]).
184    pub index: String,
185}
186
187impl DenseOutput {
188    /// `(file name, contents)` pairs, in a fixed order, for writing to disk.
189    ///
190    /// ```
191    /// let cb = sealmap_model::Codebase::new("empty");
192    /// let out = sealmap_dense::render(&cb, &Default::default());
193    /// let names: Vec<&str> = out.files().iter().map(|(n, _)| *n).collect();
194    /// assert_eq!(names, ["_index.txt", "dense.txt"]);
195    /// ```
196    pub fn files(&self) -> [(&'static str, &str); 2] {
197        [(INDEX_FILE, &self.index), (TEXT_FILE, &self.text)]
198    }
199}
200
201/// Options for [`Dense::slice`].
202#[derive(Debug, Clone, PartialEq, Eq)]
203#[non_exhaustive]
204pub struct SliceOptions {
205    /// Call levels followed from each seed, both towards callees and towards
206    /// callers. 0 gives the seeds' skeleton lines only.
207    pub depth: usize,
208    /// Refuse a slice longer than this many bytes. `None`: no limit.
209    pub max_bytes: Option<usize>,
210}
211
212impl SliceOptions {
213    /// A slice to `depth` call levels, with no byte limit.
214    pub fn new(depth: usize) -> Self {
215        Self { depth, max_bytes: None }
216    }
217
218    /// The same options with a byte budget.
219    pub fn max_bytes(mut self, max_bytes: usize) -> Self {
220        self.max_bytes = Some(max_bytes);
221        self
222    }
223}
224
225impl Default for SliceOptions {
226    fn default() -> Self {
227        Self::new(1)
228    }
229}
230
231/// Why [`Dense::slice`] refused.
232#[derive(Debug, Clone, PartialEq, Eq)]
233#[non_exhaustive]
234pub enum SliceError {
235    /// Seeds that are not symbols of the codebase, in id order.
236    UnknownSymbols(Vec<SymbolId>),
237    /// The slice does not fit the budget. Nothing was truncated.
238    OverBudget {
239        /// Size of the whole slice in bytes.
240        bytes: usize,
241        /// The budget it exceeded.
242        budget: usize,
243        /// Each seed with the size of its slice alone (same depth), in id
244        /// order: what a caller needs to plan shards.
245        seeds: Vec<(SymbolId, usize)>,
246    },
247}
248
249impl fmt::Display for SliceError {
250    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
251        match self {
252            Self::UnknownSymbols(ids) => {
253                write!(f, "{} seed id(s) are not symbols of the codebase:", ids.len())?;
254                for id in ids {
255                    write!(f, " {id};")?;
256                }
257                Ok(())
258            }
259            Self::OverBudget { bytes, budget, seeds } => {
260                write!(
261                    f,
262                    "dense slice is {bytes} bytes, {} over the {budget}-byte budget; refusing rather than truncating",
263                    bytes - budget
264                )?;
265                if let Some((id, size)) = seeds.iter().max_by(|a, b| a.1.cmp(&b.1).then_with(|| b.0.cmp(&a.0))) {
266                    write!(f, " (largest seed alone: {id} at {size} bytes)")?;
267                }
268                Ok(())
269            }
270        }
271    }
272}
273
274impl std::error::Error for SliceError {}
275
276/// A codebase prepared for dense projection: short names and the call graph
277/// are computed once, then any number of renders and slices share them.
278#[derive(Debug, Clone)]
279pub struct Dense<'a> {
280    cb: &'a Codebase,
281    shorts: ShortNames<'a>,
282    graph: Graph<'a>,
283}
284
285impl<'a> Dense<'a> {
286    /// Index `cb`: assign short names and read the call graph from the flows.
287    pub fn new(cb: &'a Codebase) -> Self {
288        Self { cb, shorts: ShortNames::new(cb), graph: Graph::new(cb) }
289    }
290
291    /// The short name of a symbol, or `None` if `id` is not in the codebase.
292    pub fn short(&self, id: &SymbolId) -> Option<&str> {
293        self.shorts.get(id)
294    }
295
296    /// The symbol a short name stands for.
297    pub fn resolve(&self, short: &str) -> Option<&'a SymbolId> {
298        self.shorts.resolve(short)
299    }
300
301    /// The full projection: [`text`](Self::text) and [`index`](Self::index).
302    pub fn render(&self, options: &DenseOptions) -> DenseOutput {
303        DenseOutput { text: self.text(options), index: self.index() }
304    }
305
306    /// The `_index.txt` text: every symbol, ordered by short name.
307    pub fn index(&self) -> String {
308        let mut out = String::new();
309        for (short, id) in self.shorts.iter() {
310            self.index_line(&mut out, short, id);
311        }
312        out
313    }
314
315    /// Skeleton lines for every symbol, then the call trees.
316    pub fn text(&self, options: &DenseOptions) -> String {
317        let mut out = self.header("");
318        out.push_str("# symbols\n");
319        skeleton::write_files(&mut out, self.cb, &self.shorts, self.cb.symbols.values());
320        out.push_str("# calls\n");
321        let mut writer = TreeWriter::new(self.cb, &self.shorts, &self.graph, options.max_depth.max(1), true);
322        let callables = self.in_source_order(self.graph.flows.keys().copied());
323        // Entry points first, then whatever only cycles reach.
324        for &id in &callables {
325            if !self.graph.callers.contains_key(id) {
326                writer.root(id, "");
327            }
328        }
329        for &id in &callables {
330            if !writer.is_expanded(id) {
331                writer.root(id, " ↺");
332            }
333        }
334        out.push_str(&writer.out);
335        out
336    }
337
338    /// The dense text for `seeds` plus their callees and callers to
339    /// `options.depth` call levels: skeleton lines, call trees from each
340    /// seed, caller trees up to each seed, and an index section for every
341    /// symbol named. Seeds are a set: order and duplicates do not matter.
342    ///
343    /// # Errors
344    ///
345    /// [`SliceError::UnknownSymbols`] if a seed is not in the codebase, and
346    /// [`SliceError::OverBudget`] if the text exceeds `options.max_bytes`.
347    pub fn slice<'s, I>(&self, seeds: I, options: &SliceOptions) -> Result<String, SliceError>
348    where
349        I: IntoIterator<Item = &'s SymbolId>,
350    {
351        let mut known = BTreeSet::new();
352        let mut unknown = BTreeSet::new();
353        for id in seeds {
354            match self.cb.symbols.get_key_value(id) {
355                Some((k, _)) => {
356                    known.insert(k);
357                }
358                None => {
359                    unknown.insert(id.clone());
360                }
361            }
362        }
363        if !unknown.is_empty() {
364            return Err(SliceError::UnknownSymbols(unknown.into_iter().collect()));
365        }
366        let text = self.slice_text(&known, options.depth);
367        match options.max_bytes {
368            Some(budget) if text.len() > budget => {
369                let seeds = known
370                    .iter()
371                    .map(|id| ((*id).clone(), self.slice_text(&BTreeSet::from([*id]), options.depth).len()))
372                    .collect();
373                Err(SliceError::OverBudget { bytes: text.len(), budget, seeds })
374            }
375            _ => Ok(text),
376        }
377    }
378
379    fn slice_text(&self, seeds: &BTreeSet<&'a SymbolId>, depth: usize) -> String {
380        let callees = self.reach(seeds, depth, |id| self.graph.callees.get(id).map(|s| s.iter().copied().collect()));
381        let callers = self.reach(seeds, depth, |id| self.graph.callers.get(id).map(|m| m.keys().copied().collect()));
382        let members: BTreeSet<&'a SymbolId> = seeds.iter().chain(&callees).chain(&callers).copied().collect();
383
384        let mut out = self.header(&format!(" slice depth {depth}"));
385        out.push_str("# symbols\n");
386        skeleton::write_files(&mut out, self.cb, &self.shorts, members.iter().filter_map(|id| self.cb.symbol(id)));
387        let ordered = self.in_source_order(seeds.iter().copied());
388        if depth > 0 {
389            let mut calls = TreeWriter::new(self.cb, &self.shorts, &self.graph, depth, false);
390            for &id in &ordered {
391                calls.root(id, "");
392            }
393            if !calls.out.is_empty() {
394                out.push_str("# calls\n");
395                out.push_str(&calls.out);
396            }
397            let mut up = CallerWriter::new(self.cb, &self.shorts, &self.graph, depth);
398            for &id in &ordered {
399                up.root(id);
400            }
401            if !up.out.is_empty() {
402                out.push_str("# callers\n");
403                out.push_str(&up.out);
404            }
405        }
406        out.push_str("# index\n");
407        let mut named: Vec<(&str, &SymbolId)> =
408            members.iter().filter_map(|id| self.shorts.get(id).map(|s| (s, *id))).collect();
409        named.sort();
410        for (short, id) in named {
411            self.index_line(&mut out, short, id);
412        }
413        out
414    }
415
416    /// Every symbol within `depth` steps of `seeds` along `next`, seeds
417    /// excluded.
418    fn reach(
419        &self,
420        seeds: &BTreeSet<&'a SymbolId>,
421        depth: usize,
422        next: impl Fn(&SymbolId) -> Option<Vec<&'a SymbolId>>,
423    ) -> BTreeSet<&'a SymbolId> {
424        let mut seen: BTreeSet<&'a SymbolId> = seeds.clone();
425        let mut frontier: Vec<&'a SymbolId> = seeds.iter().copied().collect();
426        for _ in 0..depth {
427            let mut grown = Vec::new();
428            for id in frontier {
429                for n in next(id).unwrap_or_default() {
430                    if seen.insert(n) {
431                        grown.push(n);
432                    }
433                }
434            }
435            frontier = grown;
436        }
437        seen.retain(|id| !seeds.contains(id));
438        seen
439    }
440
441    fn in_source_order(&self, ids: impl Iterator<Item = &'a SymbolId>) -> Vec<&'a SymbolId> {
442        let mut v: Vec<&'a SymbolId> = ids.collect();
443        v.sort_by(|a, b| match (self.cb.symbol(a), self.cb.symbol(b)) {
444            (Some(x), Some(y)) => order_key(x).cmp(&order_key(y)),
445            _ => a.cmp(b),
446        });
447        v
448    }
449
450    fn header(&self, kind: &str) -> String {
451        format!("# sealmap-dense {FORMAT_VERSION}{kind} {}: {LEGEND}\n", one_line(&self.cb.name))
452    }
453
454    fn index_line(&self, out: &mut String, short: &str, id: &SymbolId) {
455        out.push_str(short);
456        out.push(' ');
457        out.push_str(id.as_str());
458        if let Some(sym) = self.cb.symbol(id) {
459            out.push(' ');
460            encode_path(out, sym.file.as_str());
461            out.push(':');
462            skeleton::span(out, sym);
463        }
464        out.push('\n');
465    }
466}
467
468/// The full projection of `codebase` in one call; see [`Dense::render`].
469pub fn render(codebase: &Codebase, options: &DenseOptions) -> DenseOutput {
470    Dense::new(codebase).render(options)
471}
472
473/// One slice of `codebase` in one call; see [`Dense::slice`]. Build a
474/// [`Dense`] once instead when taking several slices of the same codebase.
475///
476/// # Errors
477///
478/// As [`Dense::slice`].
479pub fn slice<'s, I>(codebase: &Codebase, seeds: I, options: &SliceOptions) -> Result<String, SliceError>
480where
481    I: IntoIterator<Item = &'s SymbolId>,
482{
483    Dense::new(codebase).slice(seeds, options)
484}
485
486/// A path with `%`, whitespace and control characters percent-encoded, so
487/// the location stays the last whitespace-free field of an index line.
488fn encode_path(out: &mut String, path: &str) {
489    for c in path.chars() {
490        if c == '%' || c.is_whitespace() || c.is_control() {
491            let mut buf = [0u8; 4];
492            for b in c.encode_utf8(&mut buf).bytes() {
493                out.push_str(&format!("%{b:02X}"));
494            }
495        } else {
496            out.push(c);
497        }
498    }
499}
500
501/// Compiles and runs the README examples as doctests.
502#[cfg(doctest)]
503#[doc = include_str!("../README.md")]
504struct ReadmeDoctests;
505
506#[cfg(test)]
507mod tests {
508    use super::*;
509
510    #[test]
511    fn paths_are_encoded_injectively() {
512        let mut s = String::new();
513        encode_path(&mut s, "a b/100%.rs");
514        assert_eq!(s, "a%20b/100%25.rs");
515    }
516}