# Diff Layout Design

## Overview

This document describes the data structures and algorithms for rendering diffs as formatted XML (and eventually JSON, TOML, etc.) with proper alignment, coloring, and collapsing.

## Goals

- Format values once, measure once, emit once (no redundant work)
- Proper column alignment for changed attributes on -/+ lines
- Configurable line width with automatic wrapping
- Collapse long runs of unchanged elements
- No per-value allocations - use arenas

## Architecture

```
┌─────────────────────────────────────────────────────────────────┐
│                         Diff<'mem, 'facet>                       │
│                    (from facet-diff-core)                        │
└─────────────────────────────────────────────────────────────────┘
                                │
                                ▼
┌─────────────────────────────────────────────────────────────────┐
│                      Phase 1: Format                             │
│                                                                  │
│  Walk the Diff, format all scalar values into FormatArena.       │
│  Each value becomes a Span + width measurement.                  │
└─────────────────────────────────────────────────────────────────┘
                                │
                                ▼
┌─────────────────────────────────────────────────────────────────┐
│                      Phase 2: Layout                             │
│                                                                  │
│  Build LayoutNode tree (in indextree Arena).                     │
│  Group changed attrs into lines, calculate alignment.            │
│  Decide what to collapse.                                        │
└─────────────────────────────────────────────────────────────────┘
                                │
                                ▼
┌─────────────────────────────────────────────────────────────────┐
│                      Phase 3: Render                             │
│                                                                  │
│  Walk LayoutNode tree, emit to writer with proper                │
│  indentation, prefixes (-/+/←/→), colors, and padding.          │
└─────────────────────────────────────────────────────────────────┘
```

## Data Structures

### FormatArena

Single buffer for all formatted strings. Values are written once and referenced by `Span`.

```rust
pub struct Span {
    pub start: u32,
    pub end: u32,
}

pub struct FormatArena {
    buf: String,  // Pre-allocated with estimated capacity
}

impl FormatArena {
    pub fn with_capacity(cap: usize) -> Self;

    /// Format into arena, return span and display width
    pub fn format<F>(&mut self, f: F) -> (Span, usize)
    where
        F: FnOnce(&mut String) -> fmt::Result;

    /// Retrieve string for a span
    pub fn get(&self, span: Span) -> &str;
}
```

### FormattedValue

A formatted scalar value with its measurements.

```rust
pub struct FormattedValue {
    pub span: Span,       // Into FormatArena
    pub width: usize,     // Display width (unicode-aware)
}
```

### Attr and AttrStatus

Attributes with their change status.

```rust
pub enum AttrStatus {
    Unchanged { value: FormattedValue },
    Changed { old: FormattedValue, new: FormattedValue },
    Deleted { value: FormattedValue },
    Inserted { value: FormattedValue },
}

pub struct Attr {
    pub name: &'static str,
    pub name_width: usize,
    pub status: AttrStatus,
}
```

### ChangedGroup

A group of changed attributes that fit on one -/+ line pair, with alignment info.

```rust
pub struct ChangedGroup {
    pub attr_indices: Vec<usize>,  // Into parent's attrs vec
    pub max_name_width: usize,
    pub max_old_width: usize,
    pub max_new_width: usize,
}
```

### LayoutNode

Nodes in the layout tree, stored in `indextree::Arena`.

```rust
pub enum LayoutNode {
    Element {
        tag: &'static str,
        field_name: Option<&'static str>,  // For nested struct fields
        attrs: Vec<Attr>,
        changed_groups: Vec<ChangedGroup>,
        change: ElementChange,
    },
    Sequence {
        change: ElementChange,
        item_type: &'static str,  // Type name for XML wrapping
    },
    Collapsed { count: usize },
    Text { value: FormattedValue, change: ElementChange },
    ItemGroup {
        items: Vec<FormattedValue>,
        change: ElementChange,
        collapsed_suffix: Option<usize>,  // "...N more"
        item_type: &'static str,
    },
}

pub enum ElementChange {
    None,
    Deleted,
    Inserted,
    MovedFrom,
    MovedTo,
}
```

### Layout

The complete layout ready for rendering.

```rust
pub struct Layout {
    pub strings: FormatArena,
    pub tree: Arena<LayoutNode>,
    pub root: NodeId,
}
```

## Algorithms

### Attribute Grouping

Group changed attributes into lines that fit within max line width.

```
Input:  [fill: red→blue, x: 10→20, y: 5→15, stroke: black→white, ...]
Output: [
    Group { attrs: [fill, x], max_name=6, max_old=5, max_new=5 },
    Group { attrs: [y, stroke], max_name=6, max_old=5, max_new=5 },
]
```

Algorithm:
1. For each changed attr, calculate: `name_width + 2 (="") + max(old_width, new_width) + 1 (space)`
2. Greedy bin-pack into lines that fit `max_width - indent - 2 (prefix)`
3. For each group, compute max widths for alignment

### Collapse Detection

Collapse runs of unchanged siblings when `count > threshold`.

```
Input:  [unchanged, unchanged, unchanged, unchanged, unchanged, changed, unchanged]
         └──────────────────┬─────────────────────┘            └──┬───┘
                     collapse to "5 unchanged"              keep (context=1)
```

Algorithm:
1. Scan children, identify runs of unchanged elements
2. Keep `context` elements before/after each change
3. Collapse runs longer than `collapse_threshold`

### Alignment

For a group of changed attrs, the -/+ lines are aligned:

```
- fill="red"   x="10"
+ fill="blue"  x="20"
  ^^^^         ^
  name         name aligned, values padded to max width
```

Padding calculation:
- Name column: pad to `max_name_width`
- Old value: pad to `max_old_width` (only matters for - line alignment with + line)
- Between attrs: single space

## Rendering

### Element with Changed Attrs

```xml
<rect
- fill="red"   x="10"
+ fill="blue"  x="20"
  y="5" width="100" height="50"
/>
```

- Opening tag on its own line
- Each ChangedGroup emits a - line and a + line
- Unchanged attrs on a single line (dimmed)
- Self-closing or with children

### Deleted/Inserted Elements

```xml
- <circle cx="50" cy="50" r="25"/>
+ <ellipse cx="50" cy="50" rx="30" ry="20"/>
```

Entire element in red/green, prefix on every line of multi-line elements.

### Moved Elements

```xml
← <circle id="a" cx="50" cy="50" r="25"/>
  ... other elements ...
→ <circle id="a" cx="50" cy="50" r="25"/>
```

Blue color, ← at old position, → at new position.

### Collapsed Runs

```xml
<!-- 5 unchanged -->
```

Gray/dimmed comment.

## Dependencies

- `unicode-width` - for display width calculation
- `indextree` - for arena-allocated tree
- `owo-colors` - for ANSI coloring

## Files

- `facet-diff-core/src/layout/mod.rs` - Main types and Layout struct
- `facet-diff-core/src/layout/arena.rs` - FormatArena and Span
- `facet-diff-core/src/layout/attrs.rs` - Attr, AttrStatus, ChangedGroup
- `facet-diff-core/src/layout/node.rs` - LayoutNode, ElementChange
- `facet-diff-core/src/layout/build.rs` - Build Layout from Diff
- `facet-diff-core/src/layout/render.rs` - Render Layout to writer

## Current Status

**Implemented:**
- `FormatArena` - arena for pre-formatted strings with span tracking
- `Span` - reference into the arena
- `FormattedValue` - span + display width
- `Attr`, `AttrStatus` - attribute types with change status
- `ChangedGroup` - group of changed attrs for alignment
- `group_changed_attrs()` - bin-packing algorithm for grouping
- `LayoutNode`, `Layout` - tree structure using indextree
- `ElementChange` - enum for deleted/inserted/moved
- `render()`, `render_to_string()` - rendering to writer/String
- `RenderOptions` - colors, symbols, indent config
- `ColorBackend` trait - semantic colors → actual styling (ANSI, plain)
- `AnsiBackend`, `PlainBackend` - concrete backends
- `build_layout()`, `build_layout_without_context()` - Diff → Layout conversion
- Peek context passing for unchanged field values
- Collapse of unchanged struct fields when count > threshold
- `LayoutNode::Sequence` and `LayoutNode::ItemGroup` - sequence handling with type info
- Collapse of long sequence runs with "...N more" suffix
- XML sequence item wrapping (`<i32>value</i32>` via `item_type`)
- `DiffFlavor` trait - format-agnostic rendering (integrated into render phase)
- `RustFlavor`, `JsonFlavor`, `XmlFlavor` - three output styles
- `FieldPresentation` - how fields should be presented (Attribute, Child, TextContent, Children)
- XML attribute detection (`#[facet(xml::attribute)]`, etc.)
- Nested struct field names (`field_name` in Element nodes)
- XML nested elements rendered as child elements (not broken attribute syntax)
- Trailing commas with muted color for clean line endings

**Not yet implemented:**
- Move detection (←/→ markers)
- XML-specific escaping in format phase

## Known Limitations

1. **Nested diffs in sequences not supported for grouping**
   - When you have `Vec<Struct>` where struct fields changed, the nested diffs
     cannot be grouped into `ItemGroup` nodes
   - Currently only simple scalar sequences (e.g., `Vec<i32>`) support item grouping
   - See: `build.rs:collect_updates_group_items()` - ignores `_diffs` parameter

2. **XML namespace detection by string**
   - XML attributes are detected by namespace string "xml" (e.g., `field.has_attr(Some("xml"), "attribute")`)
   - This relies on the namespace being defined in `define_attr_grammar!` with `ns "xml"`
   - Even if someone imports `use facet_xml as html;`, the namespace stored is still "xml"
   - This should be tested to confirm

## Test Plan

### Unit Tests

- `arena.rs`: format values, retrieve spans, verify widths
- `attrs.rs`: grouping algorithm with various widths
- `build.rs`: convert simple Diff to Layout
- `render.rs`: render Layout to string, verify output

### Integration Tests

- Single attr change
- Multiple attr changes (fit on one line)
- Multiple attr changes (wrap to multiple lines)
- Attr added/removed
- Child element added/removed
- Element moved
- Element moved AND modified
- Deep nesting
- Collapse unchanged runs
- Full XML document diff

### Snapshot Tests

Use `insta` for snapshot testing of rendered output.
