use crate::{Delta, Error, delta, patch};
use json_patch::{
AddOperation, MoveOperation, Patch, PatchOperation, RemoveOperation, ReplaceOperation,
jsonptr::{PointerBuf, Token},
};
use serde_json::{Value, json};
use std::collections::HashSet;
pub(crate) fn disjoint_array_patch(
left: &Value,
right: &Value,
positional: bool,
) -> Result<Option<Patch>, Error> {
let (Some(source), Some(target)) = (left.as_array(), right.as_array()) else {
return Ok(None);
};
if let Some(first) = target.first() {
if first.is_array() || first.is_object() || source.contains(first) {
return Ok(None);
}
}
if let Some(first) = source.first() {
if first.is_array() || first.is_object() || target.contains(first) {
return Ok(None);
}
}
if source
.iter()
.chain(target)
.any(|value| value.is_array() || value.is_object())
{
return Ok(None);
}
crate::diff::check_array_capacity(source, target, "")?;
let originals: HashSet<_> = source.iter().collect();
if target.iter().any(|value| originals.contains(value)) {
return Ok(None);
}
let mut output = Vec::new();
if positional {
replace_disjoint(source, target, &PointerBuf::new(), &mut output);
} else {
output.reserve(source.len() + target.len());
for index in (0..source.len()).rev() {
output.push(PatchOperation::Remove(RemoveOperation {
path: child(&PointerBuf::new(), index),
}));
}
for (index, value) in target.iter().enumerate() {
output.push(PatchOperation::Add(AddOperation {
path: child(&PointerBuf::new(), index),
value: value.clone(),
}));
}
}
Ok(Some(Patch(output)))
}
fn replace_disjoint(
source: &[Value],
target: &[Value],
path: &PointerBuf,
out: &mut Vec<PatchOperation>,
) {
let overlap = source.len().min(target.len());
out.reserve(source.len().max(target.len()));
for (index, value) in target.iter().take(overlap).enumerate() {
out.push(PatchOperation::Replace(ReplaceOperation {
path: child(path, index),
value: value.clone(),
}));
}
for index in (overlap..source.len()).rev() {
out.push(PatchOperation::Remove(RemoveOperation {
path: child(path, index),
}));
}
for (index, value) in target.iter().enumerate().skip(overlap) {
out.push(PatchOperation::Add(AddOperation {
path: child(path, index),
value: value.clone(),
}));
}
}
pub(crate) fn export(left: &Value, change: &Delta) -> Result<Patch, Error> {
let right = patch::apply(left, &change.0, true)?;
export_known(left, &right, change, true)
}
pub(crate) fn export_known(
left: &Value,
right: &Value,
change: &Delta,
replace_disjoint_arrays: bool,
) -> Result<Patch, Error> {
let mut output = Vec::new();
walk(
left,
right,
&change.0,
&PointerBuf::new(),
&mut output,
replace_disjoint_arrays,
)?;
Ok(Patch(output))
}
fn child<'a>(path: &PointerBuf, token: impl Into<Token<'a>>) -> PointerBuf {
let mut result = path.clone();
result.push_back(token);
result
}
struct Ranks(Vec<usize>);
impl Ranks {
fn new(mut frequencies: Vec<usize>) -> Self {
for index in 0..frequencies.len() {
let parent = index | (index + 1);
if parent < frequencies.len() {
frequencies[parent] += frequencies[index];
}
}
Self(frequencies)
}
fn before(&self, mut end: usize) -> usize {
let mut rank = 0;
while end > 0 {
rank += self.0[end - 1];
end &= end - 1;
}
rank
}
fn occupy(&mut self, mut index: usize, occupied: bool) {
while index < self.0.len() {
if occupied {
self.0[index] += 1;
} else {
self.0[index] -= 1;
}
index |= index + 1;
}
}
}
fn walk(
left: &Value,
right: &Value,
change: &Value,
path: &PointerBuf,
out: &mut Vec<PatchOperation>,
replace_disjoint_arrays: bool,
) -> Result<(), Error> {
match change {
Value::Array(a) => match a.len() {
1 => out.push(PatchOperation::Add(AddOperation {
path: path.clone(),
value: a[0].clone(),
})),
2 => out.push(PatchOperation::Replace(ReplaceOperation {
path: path.clone(),
value: a[1].clone(),
})),
3 if a[2] == json!(0) => out.push(PatchOperation::Remove(RemoveOperation {
path: path.clone(),
})),
3 if a[2] == json!(2) => out.push(PatchOperation::Replace(ReplaceOperation {
path: path.clone(),
value: right.clone(),
})),
_ => {
return Err(Error::new(
path.as_str(),
"invalid delta in JSON Patch export",
));
}
},
Value::Object(map) if delta::is_array(map) => {
let source = left
.as_array()
.ok_or_else(|| Error::new(path.as_str(), "array delta requires an array"))?;
let target = right
.as_array()
.ok_or_else(|| Error::new(path.as_str(), "array target is missing"))?;
let parts = delta::parts(map, path.as_str())?;
if replace_disjoint_arrays
&& parts.moves.is_empty()
&& parts.changes.is_empty()
&& parts.removals.len() == source.len()
&& parts.additions.len() == target.len()
{
replace_disjoint(source, target, path, out);
return Ok(());
}
let mut moved = vec![false; source.len()];
let mut removed = vec![false; source.len()];
for &old in parts.removals.keys() {
removed[old] = true;
}
for &old in parts.moves.values() {
moved[old] = true;
}
for (&old, change) in parts.removals.iter().rev() {
if change[2] == json!(0) {
out.push(PatchOperation::Remove(RemoveOperation {
path: child(path, old),
}));
}
}
let mut remaining = (0..source.len()).filter(|&old| !removed[old]);
let mut desired = Vec::new();
let mut old_at_target = vec![None; target.len()];
for (&new, &old) in &parts.moves {
old_at_target[new] = Some(old);
}
let mut additions = parts.additions.keys().copied().peekable();
for (new, old_slot) in old_at_target.iter_mut().enumerate() {
if additions.peek() == Some(&new) {
additions.next();
continue;
}
let old = old_slot
.as_ref()
.copied()
.or_else(|| remaining.next())
.ok_or_else(|| Error::new(path.as_str(), "invalid array mapping"))?;
*old_slot = Some(old);
desired.push(old);
}
if !parts.moves.is_empty() {
let mut originals = vec![0; source.len()];
let mut finals = vec![0; source.len()];
let mut frequencies = Vec::with_capacity(desired.len() + parts.moves.len());
let mut cursor = 0;
for old in 0..source.len() {
if removed[old] && !moved[old] {
continue;
}
if !moved[old] {
while desired.get(cursor) != Some(&old) {
let pending = desired
.get(cursor)
.copied()
.filter(|&i| moved[i])
.ok_or_else(|| {
Error::new(path.as_str(), "inconsistent survivor order")
})?;
finals[pending] = frequencies.len();
frequencies.push(0);
cursor += 1;
}
cursor += 1;
}
originals[old] = frequencies.len();
frequencies.push(1);
}
for &old in &desired[cursor..] {
if !moved[old] {
return Err(Error::new(path.as_str(), "inconsistent survivor order"));
}
finals[old] = frequencies.len();
frequencies.push(0);
}
let mut ranks = Ranks::new(frequencies);
for &old in desired.iter().rev().filter(|&&old| moved[old]) {
let from = ranks.before(originals[old]);
ranks.occupy(originals[old], false);
let to = ranks.before(finals[old]);
ranks.occupy(finals[old], true);
if from != to {
out.push(PatchOperation::Move(MoveOperation {
from: child(path, from),
path: child(path, to),
}));
}
}
}
for (&new, value) in &parts.additions {
out.push(PatchOperation::Add(AddOperation {
path: child(path, new),
value: (*value).clone(),
}));
}
for (&new, change) in &parts.changes {
let old = old_at_target[new]
.ok_or_else(|| Error::new(path.as_str(), "cannot modify an added item"))?;
walk(
&source[old],
&target[new],
change,
&child(path, new),
out,
replace_disjoint_arrays,
)?;
}
}
Value::Object(map) => {
for (key, change) in map {
walk(
left.get(key).unwrap_or(&Value::Null),
right.get(key).unwrap_or(&Value::Null),
change,
&child(path, key.as_str()),
out,
replace_disjoint_arrays,
)?;
}
}
_ => {
return Err(Error::new(
path.as_str(),
"invalid delta in JSON Patch export",
));
}
}
Ok(())
}