///|
// Cross each component in sequence. A split right edit crosses the unprocessed tail.
fn[A] transform_pair(
left : Array[A],
right : Array[A],
transform_one : (Array[A], A, A, Side) -> Unit raise OpError,
append : (Array[A], A) -> Unit raise OpError,
) -> (Array[A], Array[A]) raise OpError {
let mut current_left = left
let output_right = []
for r in right {
let mut pending = Some(r)
let output_left = []
for i in 0.. {
current_left[i + offset + 1]
})
let (rest_left, rest_right) = if next_right.is_empty() {
(tail, [])
} else {
transform_pair(tail, next_right, transform_one, append)
}
for c in rest_left {
append(output_left, c)
}
for c in rest_right {
append(output_right, c)
}
pending = None
break
}
if pending is Some(r) {
append(output_right, r)
}
current_left = output_left
}
(current_left, output_right)
}
///|
fn[A] transform_side(
op : Array[A],
other : Array[A],
side : Side,
transform_one : (Array[A], A, A, Side) -> Unit raise OpError,
append : (Array[A], A) -> Unit raise OpError,
) -> Array[A] raise OpError {
if other.is_empty() {
return op
}
if op.length() == 1 && other.length() == 1 {
let output = []
transform_one(output, op[0], other[0], side)
return output
}
match side {
Left => transform_pair(op, other, transform_one, append).0
Right => transform_pair(other, op, transform_one, append).1
}
}
///|
fn operand_length(component : Component) -> Int32 {
component.path.length() +
(match component.action {
Add(_) | SubtypeEdit(_, _) => 1
_ => 0
})
}
///|
fn common_length(
a : Array[PathSegment],
a_length : Int32,
b : Array[PathSegment],
b_length : Int32,
) -> Int32? {
if a_length == 0 {
return Some(-1)
}
if b_length == 0 {
return None
}
for i in 0..<(a_length - 1) {
if i >= b_length - 1 || a[i] != b[i] {
return None
}
}
Some(a_length - 1)
}
///|
fn segment(path : Array[PathSegment], index : Int32) -> PathSegment? {
if index >= 0 && index < path.length() {
Some(path[index])
} else {
None
}
}
///|
pub fn common_length_for_ops(a : Component, b : Component) -> Int32? {
common_length(a.path, operand_length(a), b.path, operand_length(b))
}
///|
pub fn Engine::transform_component(
self : Engine,
c : Component,
other : Component,
side : Side,
) -> Operation raise OpError {
self.ensure_registered(c)
self.ensure_registered(other)
let components = []
self.transform_one(components, c, other, side)
{ components, }
}
///|
pub fn can_op_affect_path(op : Operation, path : Array[PathSegment]) -> Bool {
op.components.any(c => {
common_length(path, path.length(), c.path, operand_length(c)) is Some(_)
})
}
///|
fn changed_index(c : Component, at : Int32, next : Int32) -> Component {
let path = c.path.copy()
path[at] = Index(next)
{ ..c, path, }
}
///|
fn shifted_index(
c : Component,
at : Int32,
index : Int32,
delta : Int32,
) -> Component raise OpError {
let next = index.to_int64() + delta.to_int64()
guard next >= 0L && next <= 2147483647L else {
raise InvalidPath(c.path.copy(), "transformed index is outside Int32")
}
changed_index(c, at, next.to_int())
}
///|
fn shifted_destination(
c : Component,
destination : Int32,
delta : Int32,
) -> Component raise OpError {
let next = destination.to_int64() + delta.to_int64()
guard next >= 0L && next <= 2147483647L else {
raise InvalidPath(
c.path.copy(),
"transformed move destination is outside Int32",
)
}
{ ..c, action: Move(next.to_int()), }
}
///|
fn is_insert(c : Component) -> Bool {
c.action is ListEdit(Some(_), None)
}
///|
fn move_against_move(
c : Component,
at : Int32,
source : Int32,
destination : Int32,
other_source : Int32,
other_destination : Int32,
side : Side,
) -> Component? raise OpError {
if other_source == other_destination {
return Some(c)
}
if source == other_source {
if side == Right {
return None
}
let moved = changed_index(c, at, other_destination)
return Some(
if source == destination {
{ ..moved, action: Move(other_destination), }
} else {
moved
},
)
}
// Follow the moved source through the removal and insertion.
let source_delta = (if source > other_source { -1 } else { 0 }) +
(if source > other_destination ||
(source == other_destination && other_source > other_destination) {
1
} else {
0
})
let mut destination_delta = if source == destination &&
source == other_destination &&
other_source > other_destination {
1
} else {
0
}
if destination > other_source ||
(destination == other_source && destination > source) {
destination_delta -= 1
}
if destination > other_destination {
destination_delta += 1
} else if destination == other_destination {
let same_direction = (
other_destination > other_source && destination > source
) ||
(other_destination < other_source && destination < source)
if same_direction {
if side == Right {
destination_delta += 1
}
} else if destination > source {
destination_delta += 1
} else if destination == other_source {
destination_delta -= 1
}
}
Some(
shifted_destination(
shifted_index(c, at, source, source_delta),
destination,
destination_delta,
),
)
}
///|
fn transform_list(
c : Component,
other : Component,
at : Int32,
same_operand : Bool,
side : Side,
) -> Component? raise OpError {
guard segment(c.path, at) is Some(Index(index)) &&
segment(other.path, at) is Some(Index(other_index)) else {
return Some(c)
}
match other.action {
ListEdit(Some(inserted), Some(_)) => {
if index != other_index {
return Some(c)
}
if !same_operand {
return None
}
match c.action {
ListEdit(Some(next), Some(_)) if side == Left =>
Some({ ..c, action: ListEdit(Some(next), Some(inserted)), })
ListEdit(_, Some(_)) => None
_ => Some(c)
}
}
ListEdit(Some(_), None) => {
let current = if same_operand && is_insert(c) && index == other_index {
if side == Right {
shifted_index(c, at, index, 1)
} else {
c
}
} else if other_index <= index {
shifted_index(c, at, index, 1)
} else {
c
}
if same_operand &&
c.action is Move(destination) &&
other_index <= destination {
return Some(shifted_destination(current, destination, 1))
}
Some(current)
}
ListEdit(None, Some(_)) => {
let mut current = c
if same_operand && c.action is Move(destination) {
if other_index == index {
return None
}
if other_index < destination ||
(other_index == destination && index < destination) {
current = shifted_destination(c, destination, -1)
}
}
if other_index < index {
return Some(shifted_index(current, at, index, -1))
}
if other_index != index {
return Some(current)
}
if !same_operand {
return None
}
match c.action {
ListEdit(Some(item), Some(_)) =>
Some({ ..c, action: ListEdit(Some(item), None), })
ListEdit(None, Some(_)) => None
_ => Some(current)
}
}
Move(destination) => {
if same_operand && c.action is Move(to) {
return move_against_move(
c, at, index, to, other_index, destination, side,
)
}
if same_operand && is_insert(c) {
let delta = (if index > other_index { -1 } else { 0 }) +
(if index > destination { 1 } else { 0 })
return Some(shifted_index(c, at, index, delta))
}
if index == other_index {
return Some(changed_index(c, at, destination))
}
let delta = (if index > other_index { -1 } else { 0 }) +
(if index > destination ||
(index == destination && other_index > destination) {
1
} else {
0
})
Some(shifted_index(c, at, index, delta))
}
_ => Some(c)
}
}
///|
fn Engine::preserve_deleted_value(
self : Engine,
c : Component,
other : Component,
) -> Component raise OpError {
let length = operand_length(c)
let other_length = operand_length(other)
guard other_length > length &&
common_length(c.path, length, other.path, other_length) is Some(at) &&
segment(c.path, at) == segment(other.path, at) else {
return c
}
let original = match c.action {
ObjectEdit(_, Some(old)) | ListEdit(_, Some(old)) => old
_ => return c
}
let nested = Array::makei(other.path.length() - length, i => {
other.path[i + length]
})
let payload = self.apply_component(Some(copy_json(original)), {
..other,
path: nested,
})
guard payload is Some(payload) else { raise MissingRoot }
let action = match c.action {
ObjectEdit(insert, _) => ObjectEdit(insert, Some(payload))
ListEdit(insert, _) => ListEdit(insert, Some(payload))
_ => c.action
}
{ ..c, action, }
}
///|
fn Engine::transform_subtype(
self : Engine,
kind : String,
a : Json,
b : Json,
side : Side,
) -> Json raise OpError {
match self.subtypes.get(kind) {
Some(subtype) =>
copy_checked_json((subtype.transform)(copy_json(a), copy_json(b), side))
None if kind == "text0" =>
encode_text0(
transform_side(
decode_text0(a),
decode_text0(b),
side,
transform_text0,
(dest, edit) => append_text0(dest, edit),
),
)
None => raise UnknownSubtype(kind)
}
}
///|
fn Engine::transform_one(
self : Engine,
dest : Array[Component],
component : Component,
other : Component,
side : Side,
) -> Unit raise OpError {
let c = self.preserve_deleted_value(component, other)
let length = operand_length(c)
let other_length = operand_length(other)
guard common_length(other.path, other_length, c.path, length) is Some(at) else {
self.append_component(dest, c)
return
}
let same_operand = length == other_length
if legacy_parts(c) is Some((parent, first)) &&
legacy_parts(other) is Some((_, second)) {
let edits = self.transform_subtype(
"text0",
encode_text0([first]),
encode_text0([second]),
side,
)
for edit in decode_text0(edits) {
self.append_component(dest, legacy_component(parent, edit))
}
return
}
let same_segment = segment(c.path, at) == segment(other.path, at)
let result = match other.action {
SubtypeEdit(kind, b) =>
if c.action is SubtypeEdit(current_kind, a) && current_kind == kind {
let payload = self.transform_subtype(kind, a, b, side)
if payload is Array(items) && items.is_empty() {
return
}
Some({ ..c, action: SubtypeEdit(kind, payload), })
} else {
Some(c)
}
ListEdit(_, _) | Move(_) => transform_list(c, other, at, same_operand, side)
ObjectEdit(Some(inserted), Some(_)) if same_segment =>
match c.action {
ObjectEdit(Some(next), _) if same_operand && side == Left =>
Some({ ..c, action: ObjectEdit(Some(next), Some(inserted)), })
_ => None
}
ObjectEdit(Some(inserted), None) if same_segment &&
c.action is ObjectEdit(Some(_), _) => {
if side == Right {
return
}
self.append_component(dest, {
path: c.path,
action: ObjectEdit(None, Some(inserted)),
})
Some(c)
}
ObjectEdit(None, Some(_)) if same_segment => {
if !same_operand {
return
}
match c.action {
ObjectEdit(Some(next), _) =>
Some({ ..c, action: ObjectEdit(Some(next), None), })
_ => None
}
}
_ => Some(c)
}
if result is Some(result) {
self.append_component(dest, result)
}
}
///|
/// Returns the left operation after the right, and the right operation after the left.
pub fn Engine::transform_x(
self : Engine,
left : Operation,
right : Operation,
) -> (Operation, Operation) raise OpError {
for c in left.components {
self.ensure_registered(c)
}
for c in right.components {
self.ensure_registered(c)
}
let (left, right) = transform_pair(
left.components,
right.components,
(dest, c, other, side) => self.transform_one(dest, c, other, side),
(dest, c) => self.append_component(dest, c),
)
({ components: left, }, { components: right, })
}
///|
pub fn Engine::transform(
self : Engine,
op : Operation,
other : Operation,
side : Side,
) -> Operation raise OpError {
for c in op.components {
self.ensure_registered(c)
}
for c in other.components {
self.ensure_registered(c)
}
let components = transform_side(
op.components,
other.components,
side,
(dest, c, other, side) => self.transform_one(dest, c, other, side),
(dest, c) => self.append_component(dest, c),
)
{ components, }
}
///|
pub fn transform_x(
left : Operation,
right : Operation,
) -> (Operation, Operation) raise OpError {
Engine::new().transform_x(left, right)
}
///|
pub fn transform(
op : Operation,
other : Operation,
side : Side,
) -> Operation raise OpError {
Engine::new().transform(op, other, side)
}