fractional_index

This crate implements fractional indexing, a term coined by Figma in their blog post Realtime Editing of Ordered Sequences.

Specifically, this crate provides a type called FractionalIndex. A FractionalIndex acts as a “black box” that is only useful for comparing to another FractionalIndex. A FractionalIndex can only be constructed from a default constructor or by reference to an existing FractionalIndex.

This is useful as a key in a BTreeMap when we want to be able to arbitrarily insert or re-order elements in a collection, but don't actually care what the key is. It’s also useful for resloving conflicts when a list is modified concurrently by multiple users.

Usage

The API of FractionalIndex is very simple:

• FractionalIndex::default() creates a new fractional index.
• FractionalIndex::new_before(a) creates a fractional index before another.
• FractionalIndex::new_after(a) creates a fractional index after another.
• FractionalIndex::new_between(a, b) creates a fractional index between two others.

use fractional_index::FractionalIndex;

fn main() {
  // Construct a fractional index.
  let index = FractionalIndex::default();

  // Construct another fractional index that comes before it.
  let before_index = FractionalIndex::new_before(&index);
  assert!(before_index < index);

  // Construct a third fractional index between the other two.
  let between_index = FractionalIndex::new_between(
    &before_index,
    &index
  ).unwrap();
  assert!(before_index < between_index);
  assert!(between_index < index);
}

Stringification

FractionalIndexes are stored as byte strings, but they can be converted to and from strings.

use fractional_index::FractionalIndex;

fn main() {
  let a = FractionalIndex::default();
  let b = FractionalIndex::new_after(&a);
  let c = FractionalIndex::new_between(&a, &b).unwrap();
  
  let c_str = c.to_string();
  assert_eq!("817f80", c_str);
  let c = FractionalIndex::new_between(&a, &b).unwrap();
}

The lexicographical order of two stringified FractionalIndex values is the same as the order of the unstringified version.

use fractional_index::FractionalIndex;

fn main() {
  let a = FractionalIndex::default();
  let b = FractionalIndex::new_after(&a);
  let c = FractionalIndex::new_between(&a, &b).unwrap();
  
  assert!(a.to_string() < c.to_string());
  assert!(c.to_string() < b.to_string());
}

This is mostly useful when constructing indexes that you need to be able to compare in a language with native string comparison but not bytestring comparison, like JavaScript.

::new() constructor

The ::new() constructor generalizes over ::default(), ::new_before(), ::new_after(), and ::new_between().

use fractional_index::FractionalIndex;

fn main() {
  let a = FractionalIndex::default();
  let a2 = FractionalIndex::new(None, None).unwrap();
  assert_eq!(a, a2);

  let b = FractionalIndex::new_after(&a);
  let b2 = FractionalIndex::new(Some(&a), None).unwrap();
  assert_eq!(b, b2);
  
  let c = FractionalIndex::new_between(&a, &b).unwrap();
  let c2 = FractionalIndex::new(Some(&a), Some(&b)).unwrap();
  assert_eq!(c, c2);
}

Serialization

With the serde feature (enabled by default), FractionalIndexes can be serialized.

use fractional_index::FractionalIndex;
use serde::{Serialize, Deserialize};

#[derive(Serialize, Deserialize, Debug, PartialEq)]
struct MyStruct {
  a: FractionalIndex,
  b: FractionalIndex,
  c: FractionalIndex,
}

fn main() {
  let a = FractionalIndex::default();
  let b = FractionalIndex::new_after(&a);
  let c = FractionalIndex::new_between(&a, &b).unwrap();

  let my_struct = MyStruct {
    a: a.clone(),
    b: b.clone(),
    c: c.clone(),
  };

  let json_string = serde_json::to_string(&my_struct).unwrap();
  let my_struct_de = serde_json::from_str(&json_string).unwrap();

  assert_eq!(my_struct, my_struct_de);
}

By default, FractionalIndexes are serialized as byte arrays, which can be serialized efficiently in formats like bincode.

These byte arrays are less useful when using a format like JSON to send data to a non-Rust programming language.

For these use cases, we provide a stringifying serializer which can be enabled by annotating a field with #[serde(with="fractional_index::stringify")].

use fractional_index::FractionalIndex;
use serde::{Serialize, Deserialize};
use serde_json::json;

#[derive(Serialize, Deserialize, Debug, PartialEq)]
struct MyStruct {
  #[serde(with="fractional_index::stringify")]
  a: FractionalIndex,
  #[serde(with="fractional_index::stringify")]
  b: FractionalIndex,
  #[serde(with="fractional_index::stringify")]
  c: FractionalIndex,
}

fn main() {
  let a = FractionalIndex::default();
  let b = FractionalIndex::new_after(&a);
  let c = FractionalIndex::new_between(&a, &b).unwrap();

  let my_struct = MyStruct {
    a: a.clone(),
    b: b.clone(),
    c: c.clone(),
  };

  let json_value = serde_json::to_value(&my_struct).unwrap();

  let expected = json!({
    "a": "80",
    "b": "8180",
    "c": "817f80",
  });

  assert_eq!(expected, json_value);
}

Stability

The byte representation of a FractionalIndex can be relied upon to be fully forward- and backward-compatible with future versions of this crate, meaning that the serialized representation of two FractionalIndexes produced by any version of this crate will compare the same way when deserialized in any other version.

The actual byte representation of FractionalIndexes created by new_before, new_after, and new_between may differ between versions, but the result will always compare appropriately with the reference FractionalIndex(es) used for construction regardless of version.

The byte representation of a FractionalIndex is not meant to be compatible with the byte representaiton of a ZenoIndex, nor are their serialized counterparts.

Version 2.x.x note

In version 1.x.x of this crate, fractional indexing was implemented through a struct called ZenoIndex. The implementation of ZenoIndex is similar to FractionalIndex, and they both represent the underlying data as a byte string, but ZenoIndex requires a custom comparison function to be used with that byte string. FractionalIndex changes the byte representation so that a lexicographical comparison of the underlying byte data is all that is required to compare two FractionalIndexes.

The ZenoIndex struct is still available in version 2.x.x of this crate, but it is deprecated. New code should use FractionalIndex instead, which implements the same functionality.