Skip to main content

code_atlas/
layout.rs

1use std::cmp::Ordering;
2
3use anyhow::{Result, ensure};
4
5use crate::model::{Atlas, Callsite, NodeId, Point, Rect};
6
7#[derive(Debug, Clone)]
8pub struct LayoutOptions {
9    pub width: u32,
10    pub height: u32,
11    pub margin_fraction: f64,
12    pub directory_padding: f64,
13    pub texture_seed: u64,
14    pub bundle_strength: f64,
15}
16
17impl Default for LayoutOptions {
18    fn default() -> Self {
19        Self {
20            width: 1920,
21            height: 1080,
22            margin_fraction: 0.045,
23            directory_padding: 1.5,
24            texture_seed: 932,
25            bundle_strength: 0.96,
26        }
27    }
28}
29
30pub fn layout_repository(atlas: &mut Atlas, options: &LayoutOptions) -> Result<()> {
31    ensure!(
32        options.width > 0 && options.height > 0,
33        "output dimensions must be positive"
34    );
35    ensure!(!atlas.nodes.is_empty(), "repository has no hierarchy nodes");
36    let margin = (options.width.min(options.height) as f64
37        * options.margin_fraction.clamp(0.0, 0.20))
38    .round();
39    atlas.nodes[0].rect = Rect {
40        x0: margin,
41        y0: margin,
42        x1: options.width as f64 - margin,
43        y1: options.height as f64 - margin,
44    };
45    layout_children(atlas, 0, options);
46    Ok(())
47}
48
49fn layout_children(atlas: &mut Atlas, parent: NodeId, options: &LayoutOptions) {
50    let mut children = atlas.nodes[parent].children.clone();
51    if children.is_empty() {
52        return;
53    }
54    children.sort_by(|left, right| {
55        atlas.nodes[*right]
56            .weight
57            .partial_cmp(&atlas.nodes[*left].weight)
58            .unwrap_or(Ordering::Equal)
59            .then_with(|| atlas.nodes[*left].path.cmp(&atlas.nodes[*right].path))
60    });
61
62    let depth = atlas.nodes[parent].depth;
63    let padding = if parent == 0 {
64        0.0
65    } else {
66        options.directory_padding / (depth as f64).sqrt().max(1.0)
67    };
68    let area = atlas.nodes[parent].rect.inset(padding);
69    let rectangles = squarify(
70        &children
71            .iter()
72            .map(|id| atlas.nodes[*id].weight.max(0.0001))
73            .collect::<Vec<_>>(),
74        area,
75    );
76
77    for (child, rect) in children.into_iter().zip(rectangles) {
78        atlas.nodes[child].rect = rect;
79        layout_children(atlas, child, options);
80    }
81}
82
83pub fn squarify(weights: &[f64], rect: Rect) -> Vec<Rect> {
84    if weights.is_empty() {
85        return Vec::new();
86    }
87    let total = weights.iter().sum::<f64>().max(f64::EPSILON);
88    let scale = rect.area() / total;
89    let areas: Vec<f64> = weights.iter().map(|weight| weight * scale).collect();
90    let mut output = vec![Rect::default(); weights.len()];
91    let mut remaining = rect;
92    let mut row: Vec<usize> = Vec::new();
93
94    for index in 0..areas.len() {
95        let short_side = remaining.width().min(remaining.height()).max(f64::EPSILON);
96        if row.is_empty()
97            || worst_ratio(&row_with(&row, index), &areas, short_side)
98                <= worst_ratio(&row, &areas, short_side)
99        {
100            row.push(index);
101        } else {
102            layout_row(&row, &areas, &mut remaining, &mut output);
103            row.clear();
104            row.push(index);
105        }
106    }
107    if !row.is_empty() {
108        layout_row(&row, &areas, &mut remaining, &mut output);
109    }
110    output
111}
112
113fn row_with(row: &[usize], index: usize) -> Vec<usize> {
114    let mut candidate = row.to_vec();
115    candidate.push(index);
116    candidate
117}
118
119fn worst_ratio(row: &[usize], areas: &[f64], side: f64) -> f64 {
120    if row.is_empty() {
121        return f64::INFINITY;
122    }
123    let sum = row.iter().map(|index| areas[*index]).sum::<f64>();
124    let min = row
125        .iter()
126        .map(|index| areas[*index])
127        .fold(f64::INFINITY, f64::min)
128        .max(f64::EPSILON);
129    let max = row
130        .iter()
131        .map(|index| areas[*index])
132        .fold(0.0, f64::max)
133        .max(f64::EPSILON);
134    ((side * side * max) / (sum * sum)).max((sum * sum) / (side * side * min))
135}
136
137fn layout_row(row: &[usize], areas: &[f64], remaining: &mut Rect, output: &mut [Rect]) {
138    let row_area = row.iter().map(|index| areas[*index]).sum::<f64>();
139    if remaining.width() <= remaining.height() {
140        let height = (row_area / remaining.width().max(f64::EPSILON)).min(remaining.height());
141        let mut x = remaining.x0;
142        for (position, index) in row.iter().enumerate() {
143            let width = if position + 1 == row.len() {
144                remaining.x1 - x
145            } else {
146                areas[*index] / height.max(f64::EPSILON)
147            };
148            output[*index] = Rect {
149                x0: x,
150                y0: remaining.y0,
151                x1: x + width,
152                y1: remaining.y0 + height,
153            };
154            x += width;
155        }
156        remaining.y0 += height;
157    } else {
158        let width = (row_area / remaining.height().max(f64::EPSILON)).min(remaining.width());
159        let mut y = remaining.y0;
160        for (position, index) in row.iter().enumerate() {
161            let height = if position + 1 == row.len() {
162                remaining.y1 - y
163            } else {
164                areas[*index] / width.max(f64::EPSILON)
165            };
166            output[*index] = Rect {
167                x0: remaining.x0,
168                y0: y,
169                x1: remaining.x0 + width,
170                y1: y + height,
171            };
172            y += height;
173        }
174        remaining.x0 += width;
175    }
176}
177
178pub fn call_curve(atlas: &Atlas, call: &Callsite, options: &LayoutOptions) -> Vec<Point> {
179    let mut controls = call_control_points(atlas, call);
180
181    let first = controls[0];
182    let last = *controls.last().expect("target control point");
183    let denominator = controls.len().saturating_sub(1).max(1) as f64;
184    let bundle_strength = options.bundle_strength.clamp(0.0, 1.0);
185    for (index, point) in controls.iter_mut().enumerate() {
186        let t = index as f64 / denominator;
187        let direct = Point {
188            x: lerp(first.x, last.x, t),
189            y: lerp(first.y, last.y, t),
190        };
191        point.x = lerp(direct.x, point.x, bundle_strength);
192        point.y = lerp(direct.y, point.y, bundle_strength);
193    }
194    clamped_bspline(&controls)
195}
196
197/// Build the unbundled source-line -> file -> directory hierarchy -> file ->
198/// target-line control polygon. Line anchors are the leaves; file centers are
199/// the first shared hierarchy level, so calls from different lines diverge
200/// locally before joining the same bundled route.
201pub fn call_control_points(atlas: &Atlas, call: &Callsite) -> Vec<Point> {
202    let source_file = &atlas.nodes[call.source];
203    let target_file = &atlas.nodes[call.target];
204    let source = line_anchor(source_file.rect, source_file.loc, call.source_line);
205    let target = call
206        .target_line
207        .map(|line| line_anchor(target_file.rect, target_file.loc, line))
208        .unwrap_or_else(|| target_file.rect.center());
209    let hierarchy = atlas.hierarchy_path(call.source, call.target);
210    let mut controls = Vec::with_capacity(hierarchy.len() + 2);
211    controls.push(source);
212    controls.extend(hierarchy.iter().map(|id| atlas.nodes[*id].rect.center()));
213    controls.push(target);
214    controls
215}
216
217/// Map a one-based source line to the center of its deterministic raster cell
218/// inside a file parcel. Cells follow a serpentine scanline, keeping adjacent
219/// line ranges spatially adjacent at row boundaries. If multiple pixels map to
220/// one line, the center of that pixel range is used; if multiple lines share a
221/// pixel, they intentionally share that pixel center.
222pub fn line_anchor(rect: Rect, line_count: u64, line: u32) -> Point {
223    let min_x = rect.x0.ceil() as i64;
224    let min_y = rect.y0.ceil() as i64;
225    let max_x = rect.x1.floor() as i64;
226    let max_y = rect.y1.floor() as i64;
227    let width = max_x.saturating_sub(min_x) as u64;
228    let height = max_y.saturating_sub(min_y) as u64;
229    if width == 0 || height == 0 {
230        return rect.center();
231    }
232
233    let pixel_count = width.saturating_mul(height).max(1);
234    let line_count = line_count.max(1);
235    let line_index = u64::from(line.saturating_sub(1)).min(line_count - 1);
236    let region_start = scale_ratio_floor(line_index, pixel_count, line_count);
237    let region_end = scale_ratio_ceil(line_index + 1, pixel_count, line_count)
238        .max(region_start + 1)
239        .min(pixel_count);
240    let pixel_index = region_start + (region_end - region_start - 1) / 2;
241    let row = pixel_index / width;
242    let scan_column = pixel_index % width;
243    let column = if row.is_multiple_of(2) {
244        scan_column
245    } else {
246        width - 1 - scan_column
247    };
248    Point {
249        x: min_x as f64 + column as f64 + 0.5,
250        y: min_y as f64 + row as f64 + 0.5,
251    }
252}
253
254fn scale_ratio_floor(value: u64, scale: u64, denominator: u64) -> u64 {
255    ((u128::from(value) * u128::from(scale)) / u128::from(denominator)) as u64
256}
257
258fn scale_ratio_ceil(value: u64, scale: u64, denominator: u64) -> u64 {
259    let numerator = u128::from(value) * u128::from(scale);
260    numerator.div_ceil(u128::from(denominator)) as u64
261}
262
263pub fn sample_rect(rect: Rect, samples_per_side: usize) -> Vec<Point> {
264    let samples = samples_per_side.max(1);
265    let mut points = Vec::with_capacity(samples * 4);
266    for index in 0..samples {
267        let t = index as f64 / samples as f64;
268        points.push(Point {
269            x: lerp(rect.x0, rect.x1, t),
270            y: rect.y0,
271        });
272    }
273    for index in 0..samples {
274        let t = index as f64 / samples as f64;
275        points.push(Point {
276            x: rect.x1,
277            y: lerp(rect.y0, rect.y1, t),
278        });
279    }
280    for index in 0..samples {
281        let t = index as f64 / samples as f64;
282        points.push(Point {
283            x: lerp(rect.x1, rect.x0, t),
284            y: rect.y1,
285        });
286    }
287    for index in 0..samples {
288        let t = index as f64 / samples as f64;
289        points.push(Point {
290            x: rect.x0,
291            y: lerp(rect.y1, rect.y0, t),
292        });
293    }
294    points
295}
296
297fn clamped_bspline(controls: &[Point]) -> Vec<Point> {
298    if controls.len() < 2 {
299        return controls.to_vec();
300    }
301    let degree = controls.len().saturating_sub(1).min(3);
302    let knots = clamped_uniform_knots(controls.len(), degree);
303    let knot_spans = controls.len().saturating_sub(degree).max(1);
304    let line_segments = (knot_spans * 16).max(64);
305    let mut output = Vec::with_capacity(line_segments + 1);
306    for sample in 0..=line_segments {
307        let t = sample as f64 / line_segments as f64;
308        output.push(de_boor(controls, degree, &knots, t));
309    }
310    output
311}
312
313fn clamped_uniform_knots(control_count: usize, degree: usize) -> Vec<f64> {
314    let interior_count = control_count.saturating_sub(degree + 1);
315    let mut knots = Vec::with_capacity(control_count + degree + 1);
316    knots.extend(std::iter::repeat_n(0.0, degree + 1));
317    let denominator = (interior_count + 1) as f64;
318    for index in 1..=interior_count {
319        knots.push(index as f64 / denominator);
320    }
321    knots.extend(std::iter::repeat_n(1.0, degree + 1));
322    knots
323}
324
325fn de_boor(controls: &[Point], degree: usize, knots: &[f64], t: f64) -> Point {
326    let last_control = controls.len() - 1;
327    let span = if t >= 1.0 {
328        last_control
329    } else {
330        (degree..=last_control)
331            .find(|index| t >= knots[*index] && t < knots[*index + 1])
332            .unwrap_or(last_control)
333    };
334    let mut points: Vec<Point> = (0..=degree)
335        .map(|index| controls[span - degree + index])
336        .collect();
337
338    for level in 1..=degree {
339        for index in (level..=degree).rev() {
340            let knot_index = span - degree + index;
341            let denominator = knots[knot_index + degree + 1 - level] - knots[knot_index];
342            let alpha = if denominator.abs() <= f64::EPSILON {
343                0.0
344            } else {
345                (t - knots[knot_index]) / denominator
346            };
347            points[index] = Point {
348                x: lerp(points[index - 1].x, points[index].x, alpha),
349                y: lerp(points[index - 1].y, points[index].y, alpha),
350            };
351        }
352    }
353    points[degree]
354}
355
356fn lerp(start: f64, end: f64, amount: f64) -> f64 {
357    start + (end - start) * amount
358}
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363
364    #[test]
365    fn squarify_preserves_total_area() {
366        let root = Rect {
367            x0: 0.0,
368            y0: 0.0,
369            x1: 1600.0,
370            y1: 900.0,
371        };
372        let rectangles = squarify(&[8.0, 5.0, 3.0, 2.0, 1.0], root);
373        let total = rectangles.iter().map(|rect| rect.area()).sum::<f64>();
374        assert!((total - root.area()).abs() < 0.01);
375        assert!(
376            rectangles
377                .iter()
378                .all(|rect| rect.width() > 0.0 && rect.height() > 0.0)
379        );
380    }
381
382    #[test]
383    fn default_bundle_strength_is_tight_but_not_fully_confluent() {
384        assert_eq!(LayoutOptions::default().bundle_strength, 0.96);
385    }
386
387    #[test]
388    fn clamped_spline_interpolates_endpoints_and_reduces_degree() {
389        let linear = clamped_bspline(&[Point { x: 0.0, y: 0.0 }, Point { x: 2.0, y: 2.0 }]);
390        assert_eq!(linear.first(), Some(&Point { x: 0.0, y: 0.0 }));
391        assert_eq!(linear.last(), Some(&Point { x: 2.0, y: 2.0 }));
392        assert_point_near(linear[32], Point { x: 1.0, y: 1.0 });
393
394        let quadratic = clamped_bspline(&[
395            Point { x: 0.0, y: 0.0 },
396            Point { x: 1.0, y: 1.0 },
397            Point { x: 2.0, y: 0.0 },
398        ]);
399        assert_point_near(quadratic[32], Point { x: 1.0, y: 0.5 });
400
401        let cubic = clamped_bspline(&[
402            Point { x: 0.0, y: 0.0 },
403            Point { x: 0.0, y: 1.0 },
404            Point { x: 1.0, y: 1.0 },
405            Point { x: 1.0, y: 0.0 },
406        ]);
407        assert_point_near(cubic[32], Point { x: 0.5, y: 0.75 });
408    }
409
410    #[test]
411    fn line_anchors_follow_a_serpentine_pixel_scan() {
412        let rect = Rect {
413            x0: 0.0,
414            y0: 0.0,
415            x1: 4.0,
416            y1: 2.0,
417        };
418        assert_eq!(line_anchor(rect, 8, 1), Point { x: 0.5, y: 0.5 });
419        assert_eq!(line_anchor(rect, 8, 4), Point { x: 3.5, y: 0.5 });
420        assert_eq!(line_anchor(rect, 8, 5), Point { x: 3.5, y: 1.5 });
421        assert_eq!(line_anchor(rect, 8, 8), Point { x: 0.5, y: 1.5 });
422        assert_eq!(
423            line_anchor(rect, 8, 999),
424            Point { x: 0.5, y: 1.5 },
425            "out-of-range analyzer lines clamp to the final line cell"
426        );
427    }
428
429    #[test]
430    fn every_pixel_maps_to_a_line_range_when_pixels_outnumber_lines() {
431        let rect = Rect {
432            x0: 10.0,
433            y0: 20.0,
434            x1: 18.0,
435            y1: 21.0,
436        };
437        let anchors: Vec<_> = (1..=4).map(|line| line_anchor(rect, 4, line)).collect();
438        assert_eq!(anchors[0], Point { x: 10.5, y: 20.5 });
439        assert_eq!(anchors[1], Point { x: 12.5, y: 20.5 });
440        assert_eq!(anchors[2], Point { x: 14.5, y: 20.5 });
441        assert_eq!(anchors[3], Point { x: 16.5, y: 20.5 });
442    }
443
444    fn assert_point_near(actual: Point, expected: Point) {
445        assert!((actual.x - expected.x).abs() < 1e-9, "x: {actual:?}");
446        assert!((actual.y - expected.y).abs() < 1e-9, "y: {actual:?}");
447    }
448}