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}