path: root/docs/design/fractional-indexing.md

# Fractional Indexing for Stable Cell Positions

**Last Updated:** 2025-11-13

## Overview

Fractional indexing provides stable, immutable identifiers for cell positions in an ordered sequence, enabling concurrent insertions without the coordination problems of array indices.

## The Problem with Array Indices

Consider this scenario with traditional array indices:

```
Initial state:
[0: A, 1: B, 2: C, 3: D]

Alice subdivides cells 1-2 (B, C)
Bob subdivides cells 2-3 (C, D)

After Alice's operation:
[0: A, 1: T1, 2: T2, 3: T3, 4: D]
Now "cell 2" means T2

After Bob's operation (he thinks "cell 2" is C):
[0: A, 1: T1, 2: T2, 3: T3, 4: Q1, 5: Q2, 6: Q3, 7: D]
But C is gone! Bob's operation is invalid.
```

**The problem:** Indices are relative positions that change when the array is modified. Concurrent operations reference different cells by the same index.

## Fractional Indexing Solution

Instead of indices, each cell has a **position string** that never changes:

```
Initial state:
Cell A: position="a0"
Cell B: position="a1"
Cell C: position="a2"
Cell D: position="a3"

Alice subdivides [B, C] (position="a1" and "a2")
Bob subdivides [C, D] (position="a2" and "a3")

Alice creates:
  T1: position="a1.2"  (between a1 and a2)
  T2: position="a1.5"
  T3: position="a1.8"

Bob creates:
  Q1: position="a2.2"  (between a2 and a3)
  Q2: position="a2.5"
  Q3: position="a2.8"

Merged result (sorted by position):
a0 (A), a1 (B, deleted), a1.2 (T1), a1.5 (T2), a1.8 (T3),
a2 (C, deleted), a2.2 (Q1), a2.5 (Q2), a2.8 (Q3), a3 (D, deleted)
```

**Key insight:** Position strings are immutable. Operations reference cells by their stable position, not their current index in the array.

## Position String Format

Positions are lexicographically sortable strings:

```
"a0" < "a0.5" < "a1" < "a1.25" < "a2"
```

### Base Structure

```
[prefix][integer].[fractional]
```

- **Prefix:** Letter(s) for global ordering (e.g., "a", "b", "z")
- **Integer:** Whole number part
- **Fractional:** Optional decimal part for insertions

### Generating Positions

```rust
pub struct FractionalIndex(String);

impl FractionalIndex {
    /// Create initial positions for a sequence
    pub fn initial_sequence(count: usize) -> Vec<Self> {
        (0..count)
            .map(|i| FractionalIndex(format!("a{}", i)))
            .collect()
    }

    /// Generate position between two existing positions
    pub fn between(before: &str, after: &str) -> Self {
        // Simplified version - production needs more robust logic
        let before_val = parse_position(before);
        let after_val = parse_position(after);
        let middle = (before_val + after_val) / 2.0;

        FractionalIndex(format_position(middle))
    }

    /// Generate position before the first element
    pub fn before_first(first: &str) -> Self {
        // e.g., "a0" → "a-1"
        let val = parse_position(first);
        FractionalIndex(format_position(val - 1.0))
    }

    /// Generate position after the last element
    pub fn after_last(last: &str) -> Self {
        // e.g., "a5" → "a6"
        let val = parse_position(last);
        FractionalIndex(format_position(val + 1.0))
    }
}

fn parse_position(pos: &str) -> f64 {
    // Strip prefix, parse number
    let num_part = pos.trim_start_matches(|c: char| c.is_alphabetic());
    num_part.parse().unwrap_or(0.0)
}

fn format_position(val: f64) -> String {
    if val.fract() == 0.0 {
        format!("a{}", val as i64)
    } else {
        format!("a{}", val)
    }
}
```

### Insertion Examples

```rust
// Insert between a0 and a1
FractionalIndex::between("a0", "a1")  // → "a0.5"

// Insert between a0.5 and a1
FractionalIndex::between("a0.5", "a1")  // → "a0.75"

// Insert between a0.75 and a1
FractionalIndex::between("a0.75", "a1")  // → "a0.875"

// Insert at beginning
FractionalIndex::before_first("a0")  // → "a-1"

// Insert at end
FractionalIndex::after_last("a3")  // → "a4"
```

## Subdivision Operation with Positions

```rust
pub struct Subdivide {
    pub deleted_cell_ids: Vec<Uuid>,
    pub new_cells: Vec<NewCell>,
}

pub struct NewCell {
    pub id: Uuid,
    pub position: String,  // Fractional position
    pub duration: f64,
}

impl Subdivide {
    /// Create a subdivide operation
    pub fn new(
        target_cells: &[Cell],
        new_durations: Vec<f64>,
    ) -> Self {
        // Find position range for new cells
        let first_pos = &target_cells.first().unwrap().position;
        let last_pos = &target_cells.last().unwrap().position;

        // Generate evenly spaced positions between first and last
        let new_cells = distribute_positions(
            first_pos,
            last_pos,
            new_durations.len(),
        )
        .into_iter()
        .zip(new_durations)
        .map(|(position, duration)| NewCell {
            id: Uuid::new_v7(),
            position,
            duration,
        })
        .collect();

        Subdivide {
            deleted_cell_ids: target_cells.iter().map(|c| c.id).collect(),
            new_cells,
        }
    }
}

fn distribute_positions(
    first: &str,
    last: &str,
    count: usize,
) -> Vec<String> {
    let start = parse_position(first);
    let end = parse_position(last);
    let step = (end - start) / (count as f64 + 1.0);

    (1..=count)
        .map(|i| format_position(start + step * i as f64))
        .collect()
}
```

**Example:**
```rust
// Subdivide cells at positions a1, a2, a3 into 5 new cells

// Position range: a1 to a3
// Generate 5 positions between them:
// a1.33, a1.67, a2.0, a2.33, a2.67

let subdivide = Subdivide {
    deleted_cell_ids: [id_a1, id_a2, id_a3],
    new_cells: [
        NewCell { id: new_id_1, position: "a1.33", duration: 0.15 },
        NewCell { id: new_id_2, position: "a1.67", duration: 0.15 },
        NewCell { id: new_id_3, position: "a2.0", duration: 0.15 },
        NewCell { id: new_id_4, position: "a2.33", duration: 0.15 },
        NewCell { id: new_id_5, position: "a2.67", duration: 0.15 },
    ],
};
```

## Applying Operations

```rust
impl Op {
    fn apply(&self, realized: &mut RealizedDoc) {
        match &self.payload {
            OpPayload::Subdivide { new_cells, deleted_cell_ids, .. } => {
                let row = realized.get_row_mut(self.row_id);

                // Mark deleted cells (tombstone)
                for cell_id in deleted_cell_ids {
                    if let Some(cell) = row.cells.iter_mut().find(|c| c.id == *cell_id) {
                        cell.deleted = true;
                    }
                }

                // Insert new cells
                for new_cell in new_cells {
                    row.cells.push(Cell {
                        id: new_cell.id,
                        position: new_cell.position.clone(),
                        duration: new_cell.duration,
                        created_by: self.id,
                        deleted: false,
                    });
                }

                // Sort by position for display
                row.cells.sort_by(|a, b| a.position.cmp(&b.position));
            }
            _ => {}
        }
    }
}
```

## Handling Concurrent Insertions

Fractional indexing ensures deterministic ordering even with concurrent insertions:

```
Initial: [a0: A, a1: B, a2: C]

Alice inserts between A and B: position = "a0.5"
Bob inserts between A and B: position = "a0.5"

Both generate the same position!
```

**Solution 1: Add randomness**
```rust
fn between_with_jitter(before: &str, after: &str, actor_id: &Uuid) -> String {
    let base = between(before, after);
    // Add tiny actor-specific offset
    let offset = (actor_id.as_bytes()[0] as f64) / 1000000.0;
    adjust_position(&base, offset)
}
```

**Solution 2: Use timestamp in position**
```rust
fn between_with_timestamp(before: &str, after: &str, timestamp: u64) -> String {
    let middle = between(before, after);
    format!("{}.{}", middle, timestamp % 1000)
}
```

**Solution 3: Accept ties (rely on cell ID for final ordering)**
```rust
impl Cell {
    fn compare_for_display(&self, other: &Cell) -> Ordering {
        // Primary: position
        match self.position.cmp(&other.position) {
            Ordering::Equal => {
                // Tie-breaker: cell ID (lexicographic)
                self.id.cmp(&other.id)
            }
            other => other,
        }
    }
}
```

## Position Space Exhaustion

**Problem:** Repeatedly inserting between two positions eventually runs out of precision:

```
a0, a0.5, a0.75, a0.875, a0.9375, a0.96875, ...
```

**Solutions:**

### 1. Rebalancing (Offline)
Periodically regenerate positions with even spacing:
```rust
fn rebalance_positions(cells: &mut [Cell]) {
    let count = cells.len();
    for (i, cell) in cells.iter_mut().enumerate() {
        cell.position = format!("a{}", i);
    }
}
```

### 2. Multi-level Positions
Use hierarchical structure:
```
"a0", "a0|b0", "a0|b1", "a1"
```

### 3. Arbitrary Precision
Use strings that can grow indefinitely:
```
"a0", "a0.5", "a0.5.5", "a0.5.5.5", ...
```

## Production Implementation

Consider using existing libraries:

- **fractional-index** (Rust) - Figma-style implementation
- **string-ordering** - Lexicographic ordering primitives

Example with `fractional-index`:
```rust
use fractional_index::{FractionalIndex, generate_key_between};

// Generate position between two cells
let pos = generate_key_between(
    Some(&cell_a.position),
    Some(&cell_b.position),
);
```

## Key Properties

1. **Immutable** - Positions never change after creation
2. **Lexicographic** - String comparison gives correct order
3. **Dense** - Can always insert between any two positions
4. **Deterministic** - Same inputs produce same outputs
5. **Conflict-Free** - Concurrent insertions at same position are handled gracefully

## Trade-offs

**Pros:**
- No coordination needed for insertions
- Stable references across replicas
- Simple to reason about

**Cons:**
- Positions can become long strings over time
- Requires periodic rebalancing in heavy-edit scenarios
- Slightly more complex than array indices

## References

- [Figma's Blog: Realtime Editing of Ordered Sequences](https://www.figma.com/blog/realtime-editing-of-ordered-sequences/)
- [fractional-index crate](https://crates.io/crates/fractional-index)
- [LSEQ CRDT](https://hal.archives-ouvertes.fr/hal-00921633/document)

## Related Documents

- See `crdt-design.md` for overall CRDT architecture
- See `branch-based-merge.md` for conflict detection and resolution