ruifeng/diff/algorithms

ruifeng/diff/algorithms does not have a README file

DiffHook

pub(open) trait DiffHook {
  equal(Self, old_index : Int, new_index : Int, len : Int) -> Result[Unit, Error] = _
  delete(Self, old_index : Int, old_len : Int, new_index : Int) -> Result[Unit, Error] = _
  insert(Self, old_index : Int, new_index : Int, new_len : Int) -> Result[Unit, Error] = _
  replace(Self, old_index : Int, old_len : Int, new_index : Int, new_len : Int) -> Result[Unit, Error] = _
  finish(Self) -> Result[Unit, Error] = _
}

Different hooks can be implemented to process or store the diff results.

Capture

source

type Capture

================================================================================ CAPTURE STRUCTURE

A simple wrapper around Array[DiffOp] that implements the DiffHook interface This allows it to collect operations from any diff algorithm

impl Default for Capture

impl DiffHook for Capture

fn delete(self : Capture, old_index : Int, old_len : Int, new_index : Int) -> Result[Unit, Error]

source

Captures a Delete operation indicating removed content

@param old_index Starting index in old sequence @param old_len Number of deleted elements @param new_index Position in new sequence where deletion occurred

fn equal(self : Capture, old_index : Int, new_index : Int, len : Int) -> Result[Unit, Error]

source

Captures an Equal operation indicating unchanged content

@param old_index Starting index in old sequence @param new_index Starting index in new sequence @param len Number of equal elements

fn finish(self : Capture) -> Result[Unit, Error]

source

Final processing step - sorts operations for consistent output

ALGORITHM: Sorts operations by old sequence position, then new sequence position This ensures deterministic output regardless of algorithm execution order

fn insert(self : Capture, old_index : Int, new_index : Int, new_len : Int) -> Result[Unit, Error]

source

Captures an Insert operation indicating added content

@param old_index Position in old sequence where insertion occurred @param new_index Starting index in new sequence @param new_len Number of inserted elements

fn replace(self : Capture, old_index : Int, old_len : Int, new_index : Int, new_len : Int) -> Result[Unit, Error]

source

Captures a Replace operation indicating changed content

@param old_index Starting index in old sequence @param old_len Number of elements replaced @param new_index Starting index in new sequence @param new_len Number of replacement elements

Capture::into_ops

source

fn Capture::into_ops(self : Capture) -> Array[DiffOp]

Consumes the Capture hook and returns the collected operations

@return Array of all captured diff operations

Capture::new

source

fn Capture::new() -> Capture

Creates a new empty Capture hook

@return New Capture instance ready to collect operations

Capture::ops

source

fn Capture::ops(self : Capture) -> Array[DiffOp]

Returns a reference to the captured operations without consuming

@return Reference to the underlying operations array

Capture::sort

source

fn Capture::sort(self : Capture) -> Unit

================================================================================ SORTING ALGORITHM

Sorts captured operations to ensure consistent and predictable output

SORTING STRATEGY:

Primary sort key: position in old sequence (ascending)
Secondary sort key: position in new sequence (ascending)
Tertiary rule: Delete operations come before other operations at same position

This ordering produces diffs that read naturally from top to bottom

Capture::to_iter

source

fn Capture::to_iter(self : Capture) -> Iter[DiffOp]

Returns an iterator over the captured operations

@return Iterator yielding each captured operation in order

Compact

source

pub(all) struct Compact[D, T] {
  d : D
  ops : Array[DiffOp]
  old : Array[T]
  new : Array[T]
}

================================================================================ COMPACT DIFF STRUCTURE

A diff hook that wraps another hook and performs compaction on the operations before passing them through.

impl DiffHook for Compact[D, T]

fn[D : DiffHook, T : Eq] delete(self : Compact[D, T], old_index : Int, old_len : Int, new_index : Int) -> Result[Unit, Error]

source

Captures a Delete operation for later compaction

fn[D : DiffHook, T : Eq] equal(self : Compact[D, T], old_index : Int, new_index : Int, len : Int) -> Result[Unit, Error]

source

Captures an Equal operation for later compaction

fn[D : DiffHook, T : Eq] finish(self : Compact[D, T]) -> Result[Unit, Error]

source

Final processing step - applies compaction algorithms

PROCESSING PIPELINE:

Clean up operations using shift algorithms
Sort operations for consistent ordering
Apply operations to inner hook

fn[D : DiffHook, T : Eq] insert(self : Compact[D, T], old_index : Int, new_index : Int, new_len : Int) -> Result[Unit, Error]

source

Captures an Insert operation for later compaction

Compact::into_inner

source

fn[D, T] Compact::into_inner(self : Compact[D, T]) -> D

Consumes the Compact hook and returns the inner hook

Compact::into_ops

source

fn[D, T] Compact::into_ops(self : Compact[D, T]) -> Array[DiffOp]

Returns collected operations (for testing purposes)

Compact::new

source

fn[D, T] Compact::new(d : D, old : Array[T], new : Array[T]) -> Compact[D, T]

Creates a new Compact hook that wraps the provided diff hook

Compact::sort

source

fn[D, T] Compact::sort(self : Compact[D, T]) -> Unit

================================================================================ SORTING ALGORITHM

Ensures consistent ordering of operations for predictable output Sorts primarily by old sequence position, secondarily by new sequence position

DiffOp

source

pub(all) enum DiffOp {
  Equal(Int, Int, Int)
  Delete(Int, Int, Int)
  Insert(Int, Int, Int)
  Replace(Int, Int, Int, Int)
}

Represents the different types of operations in a diff.

impl Compare for DiffOp

impl Eq for DiffOp

impl Hash for DiffOp

impl Show for DiffOp

DiffOp::apply_to_hook

source

fn[D : DiffHook] DiffOp::apply_to_hook(self : DiffOp, d : D) -> Result[Unit, Error]

Applies the given DiffOp to a DiffHook.

DiffOp::grow_left

source

fn DiffOp::grow_left(self : DiffOp, adjust : Int) -> Unit

Used by the Compact hook to merge operations.

DiffOp::grow_right

source

fn DiffOp::grow_right(self : DiffOp, adjust : Int) -> Unit

Used by the Compact hook to merge operations.

DiffOp::is_empty

source

fn DiffOp::is_empty(self : DiffOp) -> Bool

Checks if the operation is empty (i.e., has a length of zero).

DiffOp::new_range

source

fn DiffOp::new_range(self : DiffOp) -> Range

Returns the range of the operation in the new sequence.

DiffOp::old_range

source

fn DiffOp::old_range(self : DiffOp) -> Range

Returns the range of the operation in the old sequence.

DiffOp::shift_left

source

fn DiffOp::shift_left(self : DiffOp, adjust : Int) -> Unit

Used by the Compact hook to merge operations.

DiffOp::shift_right

source

fn DiffOp::shift_right(self : DiffOp, adjust : Int) -> Unit

Used by the Compact hook to merge operations.

DiffOp::shrink_left

source

fn DiffOp::shrink_left(self : DiffOp, adjust : Int) -> Unit

Used by the Compact hook to merge operations.

DiffOp::shrink_right

source

fn DiffOp::shrink_right(self : DiffOp, adjust : Int) -> Unit

Used by the Compact hook to merge operations.

Myers

source

pub type Myers

The Myers diff algorithm implementation type

Myers::diff

source

fn[T : Eq, D : DiffHook] Myers::diff(d : D, old : Array[T], old_range : Range, new : Array[T], new_range : Range) -> Result[Unit, Error]

================================================================================ MAIN ALGORITHM ENTRY POINT

Computes the diff between two sequences using Myers algorithm

ALGORITHM STEPS:

Initialize data structures (V vectors for forward/backward search)
Use divide-and-conquer to recursively find optimal diffs
Report results through the provided DiffHook

NoFinishHook

source

pub(all) struct NoFinishHook[D] {
  d : D
}

Useful for chaining hooks where only the outermost hook's finish should be called.

NoFinishHook::into_inner

source

fn[D] NoFinishHook::into_inner(self : NoFinishHook[D]) -> D

Consumes the NoFinishHook and returns the inner hook.

NoFinishHook::new

source

fn[D] NoFinishHook::new(d : D) -> NoFinishHook[D]

Creates a new NoFinishHook.

Patience

source

pub(all) struct Patience[T, D] {
  d : D
  old : Array[T]
  old_current : Int
  old_end : Int
  old_indexes : Array[UniqueItem[T]]
  new : Array[T]
  new_current : Int
  new_end : Int
  new_indexes : Array[UniqueItem[T]]
}

================================================================================ PATIENCE DIFF STRUCTURE

The Patience diff algorithm implementation that wraps another diff hook to provide enhanced human-readable diffs.

Patience::diff

source

fn[T : Eq + Hash, D : DiffHook] Patience::diff(d : D, old : Array[T], old_range : Range, new : Array[T], new_range : Range) -> Result[Unit, Error]

================================================================================ MAIN ALGORITHM ENTRY POINT

Computes the diff using the Patience algorithm

ALGORITHM STEPS:

Extract unique items from both sequences
Find LCS of unique items using Myers algorithm
Use matching unique items as anchors for recursive diffing
Apply Myers algorithm between anchors for detailed differences

Range

source

pub(all) struct Range {
  start : Int
  end : Int
}

================================================================================ RANGE STRUCTURE

Represents a contiguous range of indices [start, end) where:

start is inclusive (first index in range)
end is exclusive (one past the last index)

This half-open interval design allows clean empty ranges (start == end) and simplifies length calculations (end - start)

impl Show for Range

Range::contains

source

fn Range::contains(self : Range, i : Int) -> Bool

Checks if a specific index falls within the range

ALGORITHM: index is in range when start <= index < end This follows the half-open interval definition

@param i The index to check @return true if index is within range, false otherwise

Range::is_empty

source

fn Range::is_empty(self : Range) -> Bool

Checks if the range contains no elements

ALGORITHM: A range is empty when start >= end This is the mathematical property of half-open intervals

@return true if range contains no elements, false otherwise

Range::iter

source

fn Range::iter(self : Range) -> Iter[Int]

================================================================================ RANGE ITERATION ALGORITHM

Creates an iterator over all indices in the range

ALGORITHM: Generates indices from start to end-1 inclusive This provides a convenient way to iterate over array indices

@return Iterator yielding all indices in the range

Range::len

source

fn Range::len(self : Range) -> Int

Calculates the number of elements in the range

ALGORITHM: length = max(0, end - start) The max ensures we never return negative length for invalid ranges

@return Number of elements in the range (0 for empty ranges)

Range::new

source

fn Range::new(start : Int, end : Int) -> Range

Creates a new Range with specified start and end indices

@param start Inclusive start index @param end Exclusive end index @return New Range instance

Replace

source

pub(all) struct Replace[D] {
  d : D
  del : (Int, Int, Int)?
  ins : (Int, Int, Int)?
  eq : (Int, Int, Int)?
}

into a single Replace operation.

impl DiffHook for Replace[D]

fn[D : DiffHook] delete(self : Replace[D], old_index : Int, old_len : Int, new_index : Int) -> Result[Unit, Error]

source

Flushes any pending equal ops and merges consecutive delete ops.

fn[D : DiffHook] equal(self : Replace[D], old_index : Int, new_index : Int, len : Int) -> Result[Unit, Error]

source

Flushes any pending insert/delete ops and merges consecutive equal ops.

fn[D : DiffHook] finish(self : Replace[D]) -> Result[Unit, Error]

source

Finishes the diffing process by flushing any remaining pending operations.

fn[D : DiffHook] insert(self : Replace[D], old_index : Int, new_index : Int, new_len : Int) -> Result[Unit, Error]

source

Flushes any pending equal ops and merges consecutive insert ops.

fn[D : DiffHook] replace(self : Replace[D], old_index : Int, old_len : Int, new_index : Int, new_len : Int) -> Result[Unit, Error]

source

Flushes any pending operations and forwards the replace to the inner hook.

Replace::flush_del_ins

source

fn[D : DiffHook] Replace::flush_del_ins(self : Replace[D]) -> Result[Unit, Error]

If both are present, they are merged into a Replace operation.

Replace::flush_eq

source

fn[D : DiffHook] Replace::flush_eq(self : Replace[D]) -> Result[Unit, Error]

Flushes any pending Equal operation to the inner hook.

Replace::into_inner

source

fn[D] Replace::into_inner(self : Replace[D]) -> D

Consumes the Replace hook and returns the inner hook.

Replace::new

source

fn[D] Replace::new(d : D) -> Replace[D]

Creates a new Replace hook.

UniqueItem

source

type UniqueItem[T]

Wrapper structure that associates an item with its original index Used to track positions after filtering unique items

V

source

type V

The V vector for tracking furthest-reaching paths in the edit graph

V::len

source

fn V::len(self : V) -> Int

Returns the total capacity of the V vector

V::new

source

fn V::new(max_d : Int) -> V

Creates a new V vector with capacity for diagonals from -max_d to +max_d

V::op_get

source

fn V::op_get(self : V, i : Int) -> Int

Gets the x-coordinate for diagonal k

V::op_set

source

fn V::op_set(self : V, i : Int, value : Int) -> Unit

Sets the x-coordinate for diagonal k

cleanup_diff_ops

source

fn[T : Eq] cleanup_diff_ops(old : Array[T], new : Array[T], ops : Array[DiffOp]) -> Unit

Main compaction algorithm that coordinates the cleanup process

STRATEGY:

First pass: shift and merge delete operations
Second pass: shift and merge insert operations
Each pass applies both upward and downward shifts

common_prefix_len

source

fn[T : Eq] common_prefix_len(old : Array[T], old_range : Range, new : Array[T], new_range : Range) -> Int

Calculates the length of the common prefix between two sequence ranges

@param old First sequence array @param old_range Range within the first sequence @param new Second sequence array @param new_range Range within the second sequence @return Length of the common prefix (0 if no common prefix)

common_suffix_len

source

fn[T : Eq] common_suffix_len(old : Array[T], old_range : Range, new : Array[T], new_range : Range) -> Int

Calculates the length of the common suffix between two sequence ranges

shift_diff_ops_down

source

fn[T : Eq] shift_diff_ops_down(ops : Array[DiffOp], old : Array[T], new : Array[T], pointer : Int) -> Int

Shifts operations downward (later) to merge with following operations

Similar to shift_diff_ops_up but operates in the downward direction Uses common prefixes instead of suffixes for alignment

shift_diff_ops_up

source

fn[T : Eq] shift_diff_ops_up(ops : Array[DiffOp], old : Array[T], new : Array[T], pointer : Int) -> Int

Shifts operations upward (earlier) to merge with previous operations

SHIFTING RULES:

Swap insert/delete operations to group similar operations
Merge adjacent operations of the same type
Align operations with common prefixes/suffixes
Remove empty operations

unique

source

fn[T : Eq + Hash] unique(array : Array[T], range : Range) -> Array[UniqueItem[T]]

Finds all unique items in a specified range of an array

ALGORITHM STEPS:

Build frequency map: count occurrences of each value
Filter unique values: keep only items with count = 1
Create tracking objects: wrap unique items with original indices
Sort by position: maintain original sequence order

@param array The source array to scan @param range The range within the array to examine @return Array of unique items with their original indices

Source Files

Site source Report issue Packages Build queue Skills Statistics

#DiffHook

#Capture

================================================================================ CAPTURE STRUCTURE

#Capture::into_ops

#Capture::new

#Capture::ops

#Capture::sort

================================================================================ SORTING ALGORITHM

#Capture::to_iter

#Compact

================================================================================ COMPACT DIFF STRUCTURE

#Compact::into_inner

#Compact::into_ops

#Compact::new

#Compact::sort

================================================================================ SORTING ALGORITHM

#DiffOp

#DiffOp::apply_to_hook

#DiffOp::grow_left

#DiffOp::grow_right

#DiffOp::is_empty

#DiffOp::new_range

#DiffOp::old_range

#DiffOp::shift_left

#DiffOp::shift_right

#DiffOp::shrink_left

#DiffOp::shrink_right

#Myers

#Myers::diff

================================================================================ MAIN ALGORITHM ENTRY POINT

#NoFinishHook

#NoFinishHook::into_inner

#NoFinishHook::new

#Patience

================================================================================ PATIENCE DIFF STRUCTURE

#Patience::diff

================================================================================ MAIN ALGORITHM ENTRY POINT

#Range

================================================================================ RANGE STRUCTURE

#Range::contains

#Range::is_empty

#Range::iter

================================================================================ RANGE ITERATION ALGORITHM

#Range::len

#Range::new

#Replace

#Replace::flush_del_ins

#Replace::flush_eq

#Replace::into_inner

#Replace::new

#UniqueItem

#V

#V::len

#V::new

#V::op_get

#V::op_set

#cleanup_diff_ops

#common_prefix_len

#common_suffix_len

#shift_diff_ops_down

#shift_diff_ops_up

#unique

Source Files

DiffHook

Capture

Capture::into_ops

Capture::new

Capture::ops

Capture::sort

Capture::to_iter

Compact

Compact::into_inner

Compact::into_ops

Compact::new

Compact::sort

DiffOp

DiffOp::apply_to_hook

DiffOp::grow_left

DiffOp::grow_right

DiffOp::is_empty

DiffOp::new_range

DiffOp::old_range

DiffOp::shift_left

DiffOp::shift_right

DiffOp::shrink_left

DiffOp::shrink_right

Myers

Myers::diff

NoFinishHook

NoFinishHook::into_inner

NoFinishHook::new

Patience

Patience::diff

Range

Range::contains

Range::is_empty

Range::iter

Range::len

Range::new

Replace

Replace::flush_del_ins

Replace::flush_eq

Replace::into_inner

Replace::new

UniqueItem

V

V::len

V::new

V::op_get

V::op_set

cleanup_diff_ops

common_prefix_len

common_suffix_len

shift_diff_ops_down

shift_diff_ops_up

unique