🥮 mooncakes.io
    Sign in

    piediff

    A MoonBit implementation of Bram Cohen's patience diff algorithm (also provides a basic Myers diff)

    Download zip
    Version
    0.1.1
    License
    Apache-2.0
    Repository
    Last updated
    3 months ago
    Downloads
    14K

    No dependencies

    #Piediff

    check

    Piediff is a MoonBit implementation of Bram Cohen's patience diff algorithm (also provides a basic Myers diff).

    #Compute A Diff

    Diff(old~, new~) computes the full sequence of Delete, Insert, and Equal operations, accessible via the edits field.

    ///|
    test "Diff computes deletes inserts and equals" {
      let old = ["apple", "pear", "banana"][:]
      let new = ["apple", "banana", "coconut"][:]

      let d = @piediff.Diff(old~, new~)

      assert_eq(d.edits.length(), 4)
      assert_true(
        d.edits[:]
        is [
          Equal(old_index=0, new_index=0, len=1),
          Delete(old_index=1, new_index=1, len=1),
          Equal(old_index=2, new_index=1, len=1),
          Insert(old_index=3, new_index=2, len=1),
        ],
      )
    }

    #Prefer Unique Anchors With Patience Diff

    Pass algorithm=@piediff.Patience to Diff(old~, new~, algorithm=@piediff.Patience) to enable patience diff. This first finds elements that appear exactly once in both inputs and uses them as anchors, then runs Myers diff on the unmatched ranges between those anchors. This can produce more stable result when repeated elements move around.

    ///|
    test "patience diff keeps unique anchors in place" {
      let old = ["unique", "dup", "dup"][:]
      let new = ["dup", "unique", "dup"][:]

      let myers = @piediff.Diff(old~, new~)
      let patience = @piediff.Diff(old~, new~, algorithm=@piediff.Patience)

      assert_true(
        myers.edits[:]
        is [
          Delete(old_index=0, new_index=0, len=1),
          Equal(old_index=1, new_index=0, len=1),
          Insert(old_index=2, new_index=1, len=1),
          Equal(old_index=2, new_index=2, len=1),
        ],
      )
      assert_true(
        patience.edits[:]
        is [
          Insert(old_index=0, new_index=0, len=1),
          Equal(old_index=0, new_index=1, len=2),
          Delete(old_index=2, new_index=3, len=1),
        ],
      )
    }

    #Group Into Hunks And Render

    group splits the edit script into Hunk[T] values, keeping radius lines of surrounding context (default 3). radius must be non-negative, and radius=0 emits hunks without surrounding context. Each Hunk[T] implements Show, so you can print it directly as unified-diff output.

    ///|
    test "group splits distant changes into separate hunks" {
      let old = [
          " aaaaaaaaaa", " bbbbbbbbbb", " cccccccccc", " dddddddddd", " eeeeeeeeee",
          " ffffffffff", " gggggggggg", " hhhhhhhhhh",
        ][:]
      let new = [
          " aaaaaaaaaa", " xxxxxxxxxx", " cccccccccc", " dddddddddd", " eeeeeeeeee",
          " ffffffffff", " yyyyyyyyyy", " hhhhhhhhhh",
        ][:]

      let hunks = @piediff.Diff(old~, new~).group(radius=1)

      assert_eq(hunks.length(), 2)
      assert_eq(
        hunks[0].to_string(),
        (
          #|@@ -1,3 +1,3 @@
          #|  aaaaaaaaaa
          #|- bbbbbbbbbb
          #|+ xxxxxxxxxx
          #|  cccccccccc
          #|
        ),
      )
      assert_eq(
        hunks[1].to_string(),
        (
          #|@@ -6,3 +6,3 @@
          #|  ffffffffff
          #|- gggggggggg
          #|+ yyyyyyyyyy
          #|  hhhhhhhhhh
          #|
        ),
      )
    }

    Diff

    source
    pub struct Diff[T] {
      old : ArrayView[T]
      new : ArrayView[T]
      edits : Array[Edit]
    }

    Diff::Diff

    source
    fn[T : Hash + Eq] Diff::Diff(old~ : ArrayView[T], new~ : ArrayView[T], cutoff? : Int, algorithm? : DiffAlgorithm) -> Diff[T]

    Diff::new(old~, new~, cutoff?, algorithm?) diffs old and new (as in /usr/bin/diff), and returns a Diff[T] bundling the source arrays with the edit script that transforms old into new.

    The cutoff is an upper bound on the minimum edit distance between old~ and new~. When cutoff is exceeded, the result is a correct, but not necessarily minimal diff. It defaults to about sqrt(old.length() + new.length()).

    The algorithm selects the diff strategy. Myers (the default) uses the classic Myers O(ND) algorithm. Patience first finds elements unique to both inputs as anchors, then runs Myers on the unmatched ranges between them.

    Diff::group

    source
    fn[T] Diff::group(self : Diff[T], radius? : Int) -> Array[Hunk[T]]

    DiffAlgorithm

    source
    pub(all) enum DiffAlgorithm {
      Myers
      Patience
    }

    Edit

    source
    pub enum Edit {
      Delete(old_index~ : Int, new_index~ : Int, len~ : Int)
      Insert(old_index~ : Int, new_index~ : Int, len~ : Int)
      Equal(old_index~ : Int, new_index~ : Int, len~ : Int)
    } derive(
    Debug    )

    One step in an edit script that transforms old into new.

    Every constructor stores the start positions of the affected range in both sequences. Length fields then describe how many elements are deleted, inserted, or shared. Storing both coordinates on every step keeps the edit self-contained, which simplifies deriving hunk headers and grouping edits into hunks.

    Hunk

    source
    pub struct Hunk[T] {
      edits : ArrayView[Edit]
      old : ArrayView[T]
      new : ArrayView[T]
    }

    impl Show for Hunk[T]

    Hunk::header

    source
    fn[T] Hunk::header(self : Hunk[T]) -> HunkHeader

    HunkHeader

    source
    pub struct HunkHeader {
      old : Range
      new : Range
    }

    impl Show for HunkHeader

    Range

    source
    pub struct Range(Int, Int)

    Range(, )
    impl Show for Range

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io