#![doc = include_str!("../README.md")]
use serde_json::Value;
use std::{fmt, sync::Arc};
mod delta;
mod diff;
mod export;
mod merge;
mod numbers;
mod patch;
mod text;
pub use merge::{compose_merge_patches, diff_merge_patch, merge_patch, merge_patch_in_place};
mod compare;
pub use compare::{
ArrayMove, CompareNodeFilter, CompareOptions, CompareReport, CustomEqual, Difference,
UnorderedArrays, compare,
};
mod rfc;
pub use rfc::{JsonPatchOptions, diff_json_patch, invert_json_patch, invert_json_patch_guarded};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Error {
pub path: String,
pub message: String,
}
impl Error {
pub(crate) fn new(path: &str, message: impl Into<String>) -> Self {
Self {
path: path.to_owned(),
message: message.into(),
}
}
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"{}: {}",
if self.path.is_empty() {
"<root>"
} else {
&self.path
},
self.message
)
}
}
impl std::error::Error for Error {}
pub type ObjectHash = Arc<dyn Fn(&Value, usize) -> Option<String> + Send + Sync>;
pub type PropertyFilter = Arc<dyn Fn(&str, &Value, &Value, &str) -> bool + Send + Sync>;
pub type NodeFilter = Arc<dyn Fn(&str, Option<&Value>, Option<&Value>) -> bool + Send + Sync>;
pub type ArrayItemMatcher = Arc<dyn Fn(&str, &Value, &Value) -> bool + Send + Sync>;
#[derive(Clone, Debug)]
pub struct TextPatchOptions {
pub max_distance: usize,
pub max_error_ratio: f64,
}
impl Default for TextPatchOptions {
fn default() -> Self {
Self {
max_distance: 1000,
max_error_ratio: 0.5,
}
}
}
impl TextPatchOptions {
pub(crate) fn validate(&self) -> Result<(), Error> {
if !self.max_error_ratio.is_finite() || !(0.0..=1.0).contains(&self.max_error_ratio) {
return Err(Error::new(
"",
"max_error_ratio must be finite and in 0..=1",
));
}
Ok(())
}
}
#[derive(Clone)]
pub struct DiffOptions {
pub object_hash: Option<ObjectHash>,
pub property_filter: Option<PropertyFilter>,
pub node_filter: Option<NodeFilter>,
pub array_item_matcher: Option<ArrayItemMatcher>,
pub match_by_position: bool,
pub detect_moves: bool,
pub include_value_on_move: bool,
pub text_diff_min_length: Option<usize>,
pub max_depth: usize,
}
impl Default for DiffOptions {
fn default() -> Self {
Self {
object_hash: None,
property_filter: None,
node_filter: None,
array_item_matcher: None,
match_by_position: true,
detect_moves: true,
include_value_on_move: false,
text_diff_min_length: Some(60),
max_depth: 128,
}
}
}
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
#[serde(transparent)]
pub struct Delta(pub(crate) Value);
impl Delta {
pub fn from_value(value: Value) -> Result<Self, Error> {
delta::validate(&value, "", 0)?;
delta::check_depth(&value, delta::MAX_DELTA_DEPTH)?;
Ok(Self(value))
}
pub fn as_value(&self) -> &Value {
&self.0
}
pub fn into_value(self) -> Value {
self.0
}
pub fn to_json_patch(&self, left: &Value) -> Result<json_patch::Patch, Error> {
export::export(left, self)
}
pub fn to_forward_only(&self) -> ForwardDelta {
ForwardDelta(delta::strip_old(&self.0))
}
}
impl<'de> serde::Deserialize<'de> for Delta {
fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
Self::from_value(Value::deserialize(deserializer)?).map_err(serde::de::Error::custom)
}
}
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
#[serde(transparent)]
pub struct ForwardDelta(Value);
impl ForwardDelta {
pub fn from_value(value: Value) -> Result<Self, Error> {
delta::validate(&value, "", 0)?;
delta::check_depth(&value, delta::MAX_DELTA_DEPTH)?;
Ok(Self(value))
}
pub fn as_value(&self) -> &Value {
&self.0
}
pub fn patch(&self, left: &Value) -> Result<Value, Error> {
patch::apply(left, &self.0, false)
}
}
impl<'de> serde::Deserialize<'de> for ForwardDelta {
fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
Self::from_value(Value::deserialize(deserializer)?).map_err(serde::de::Error::custom)
}
}
#[derive(Clone, Default)]
pub struct DiffPatcher {
options: DiffOptions,
}
impl DiffPatcher {
pub fn new(options: DiffOptions) -> Self {
Self { options }
}
pub fn by_key(key: impl Into<String>) -> Self {
let key = key.into();
Self::new(DiffOptions {
object_hash: Some(Arc::new(move |item, _| {
item.as_object()?.get(&key).map(Value::to_string)
})),
..Default::default()
})
}
pub fn diff(&self, left: &Value, right: &Value) -> Result<Option<Delta>, Error> {
self.check_inputs(left, right)?;
self.diff_validated(left, right)
}
fn check_inputs(&self, left: &Value, right: &Value) -> Result<usize, Error> {
if self.options.object_hash.is_some() && self.options.array_item_matcher.is_some() {
return Err(Error::new(
"",
"choose object_hash or array_item_matcher, not both",
));
}
if self.options.max_depth > 128 {
return Err(Error::new("", "max_depth must not exceed 128"));
}
let left_depth = delta::measure_depth(left, self.options.max_depth)?;
let right_depth = delta::measure_depth(right, self.options.max_depth)?;
Ok(left_depth.max(right_depth))
}
fn diff_validated(&self, left: &Value, right: &Value) -> Result<Option<Delta>, Error> {
let result = diff::node(left, right, &self.options, "")?;
if let Some(value) = &result {
delta::check_depth(value, delta::MAX_DELTA_DEPTH)?;
}
Ok(result.map(Delta))
}
pub fn patch(&self, left: &Value, delta: &Delta) -> Result<Value, Error> {
patch(left, delta)
}
pub fn reverse(&self, delta: &Delta) -> Result<Delta, Error> {
reverse(delta)
}
pub fn unpatch(&self, right: &Value, delta: &Delta) -> Result<Value, Error> {
unpatch(right, delta)
}
pub fn diff_json_patch(
&self,
left: &Value,
right: &Value,
options: &JsonPatchOptions,
) -> Result<Patch, Error> {
let input_depth = self.check_inputs(left, right)?;
if (!options.tests || (!options.factorize && !options.rationalize))
&& self.options.node_filter.is_none()
&& self.options.property_filter.is_none()
&& self.options.array_item_matcher.is_none()
{
if let Some(mut standard) =
export::disjoint_array_patch(left, right, !options.factorize)?
{
if options.tests && !standard.0.is_empty() {
standard.0.insert(
0,
PatchOperation::Test(json_patch::TestOperation {
path: json_patch::jsonptr::PointerBuf::new(),
value: export::copy_addition(left),
}),
);
}
return rfc::optimize(left, right, standard, options);
}
}
if self.options.node_filter.is_none() && self.options.property_filter.is_none() {
let mut matching = self.options.clone();
matching.text_diff_min_length = None;
let standard = export::direct_patch(left, right, &matching, options, input_depth)?;
if standard.0.is_empty() {
return Ok(standard);
}
return rfc::optimize(left, right, standard, options);
}
let change = if self.options.text_diff_min_length.is_some() {
let mut options = self.options.clone();
options.text_diff_min_length = None;
Self::new(options).diff_validated(left, right)?
} else {
self.diff_validated(left, right)?
};
let Some(change) = change else {
return Ok(Patch::default());
};
if self.options.property_filter.is_some() || self.options.node_filter.is_some() {
let projected = patch(left, &change)?;
let standard = export::export_known(
left,
&projected,
&change,
!options.factorize && !options.tests,
)?;
rfc::optimize(left, &projected, standard, options)
} else {
let standard =
export::export_known(left, right, &change, !options.factorize && !options.tests)?;
rfc::optimize(left, right, standard, options)
}
}
}
pub fn diff(left: &Value, right: &Value) -> Result<Option<Delta>, Error> {
DiffPatcher::default().diff(left, right)
}
pub fn patch(left: &Value, delta: &Delta) -> Result<Value, Error> {
patch::apply(left, &delta.0, true)
}
pub fn patch_owned(left: Value, delta: &Delta) -> Result<Value, Error> {
patch::apply_owned(left, &delta.0, true)
}
pub fn patch_in_place(left: &mut Value, delta: &Delta) -> Result<(), Error> {
let result = patch(left, delta)?;
*left = result;
Ok(())
}
pub fn apply_text_patch(
source: &str,
text_patch: &str,
options: &TextPatchOptions,
) -> Result<String, Error> {
options.validate()?;
text::apply_fuzzy(source, text_patch, "", options)
}
pub fn patch_fuzzy(
left: &Value,
delta: &Delta,
options: &TextPatchOptions,
) -> Result<Value, Error> {
options.validate()?;
patch::apply_fuzzy(left, &delta.0, options)
}
pub fn reverse(delta: &Delta) -> Result<Delta, Error> {
patch::invert(&delta.0, "").map(Delta)
}
pub fn unpatch(right: &Value, delta: &Delta) -> Result<Value, Error> {
patch(right, &reverse(delta)?)
}
pub use json_patch::{Patch, PatchOperation};
#[derive(Clone, Debug)]
pub struct JsonPatchApplyOptions {
pub max_copy_bytes: Option<usize>,
pub max_depth: usize,
}
impl Default for JsonPatchApplyOptions {
fn default() -> Self {
Self {
max_copy_bytes: None,
max_depth: 128,
}
}
}
pub fn apply_json_patch(left: &Value, patch: &Patch) -> Result<Value, Error> {
apply_json_patch_with_options(left, patch, &JsonPatchApplyOptions::default())
}
pub fn test_json_patch(left: &Value, patch: &Patch) -> Result<(), Error> {
let options = JsonPatchApplyOptions::default();
check_standard_source(left, &options)?;
for (index, op) in patch.0.iter().enumerate() {
let PatchOperation::Test(test) = op else {
return Err(standard_error(
index,
operation_path(op),
"only test operations are allowed",
));
};
test_standard(left, test, index, options.max_depth)?;
}
Ok(())
}
pub fn apply_json_patch_with_options(
left: &Value,
patch: &Patch,
options: &JsonPatchApplyOptions,
) -> Result<Value, Error> {
check_standard_source(left, options)?;
apply_standard_checked(left.clone(), patch, options)
}
pub fn apply_json_patch_owned(left: Value, patch: &Patch) -> Result<Value, Error> {
apply_standard(left, patch, &JsonPatchApplyOptions::default())
}
pub fn apply_json_patch_in_place(left: &mut Value, patch: &Patch) -> Result<(), Error> {
let result = apply_json_patch(left, patch)?;
*left = result;
Ok(())
}
fn standard_error(index: usize, path: &str, message: impl fmt::Display) -> Error {
Error::new(
path,
format!("operation '/{index}' failed at path '{path}': {message}"),
)
}
fn operation_path(op: &PatchOperation) -> &str {
match op {
PatchOperation::Add(op) => op.path.as_str(),
PatchOperation::Remove(op) => op.path.as_str(),
PatchOperation::Replace(op) => op.path.as_str(),
PatchOperation::Move(op) => op.path.as_str(),
PatchOperation::Copy(op) => op.path.as_str(),
PatchOperation::Test(op) => op.path.as_str(),
}
}
fn check_standard_source(left: &Value, options: &JsonPatchApplyOptions) -> Result<(), Error> {
if options.max_depth > 128 {
return Err(Error::new("", "max_depth must not exceed 128"));
}
delta::check_depth(left, options.max_depth)
}
fn apply_standard(
result: Value,
patch: &Patch,
options: &JsonPatchApplyOptions,
) -> Result<Value, Error> {
check_standard_source(&result, options)?;
apply_standard_checked(result, patch, options)
}
fn apply_standard_checked(
mut result: Value,
patch: &Patch,
options: &JsonPatchApplyOptions,
) -> Result<Value, Error> {
let mut copied = 0usize;
for (index, op) in patch.0.iter().enumerate() {
if let (Some(limit), PatchOperation::Copy(copy)) = (options.max_copy_bytes, op) {
let value = copy.from.resolve(&result).map_err(|_| {
standard_error(index, copy.path.as_str(), "\"from\" path is invalid")
})?;
let mut size = ByteCount(0);
serde_json::to_writer(&mut size, value)
.map_err(|e| standard_error(index, copy.path.as_str(), e))?;
copied = copied.checked_add(size.0).ok_or_else(|| {
standard_error(index, copy.path.as_str(), "copy byte count overflow")
})?;
if copied > limit {
return Err(standard_error(
index,
copy.path.as_str(),
"copy byte budget exceeded",
));
}
}
step_with_depth(&mut result, op, index, options.max_depth)?;
}
Ok(result)
}
struct ByteCount(usize);
impl std::io::Write for ByteCount {
fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
self.0 = self
.0
.checked_add(bytes.len())
.ok_or_else(|| std::io::Error::other("JSON size overflow"))?;
Ok(bytes.len())
}
fn flush(&mut self) -> std::io::Result<()> {
Ok(())
}
}
pub(crate) fn apply_json_patch_step(
result: &mut Value,
op: &PatchOperation,
index: usize,
) -> Result<(), Error> {
step_with_depth(result, op, index, 128)
}
fn step_with_depth(
result: &mut Value,
op: &PatchOperation,
index: usize,
max_depth: usize,
) -> Result<(), Error> {
if let PatchOperation::Test(test) = op {
return test_standard(result, test, index, max_depth);
}
let path = operation_path(op);
let payload_height = match op {
PatchOperation::Add(op) => Some(standard_subtree_height(&op.value, max_depth)),
PatchOperation::Replace(op) => Some(standard_subtree_height(&op.value, max_depth)),
_ => None,
}
.transpose()
.map_err(|e| standard_error(index, path, e.message))?;
if matches!(op, PatchOperation::Move(m) if m.from.as_str().is_empty() && m.path.as_str().is_empty())
{
return Ok(());
}
let target_depth = path.bytes().filter(|byte| *byte == b'/').count();
let inserted_height = match op {
PatchOperation::Move(op) => moved_subtree_height(result, &op.from, target_depth, max_depth),
PatchOperation::Copy(op) => moved_subtree_height(result, &op.from, target_depth, max_depth),
_ => Ok(payload_height),
}
.map_err(|e| standard_error(index, path, e.message))?;
json_patch::patch_unsafe(result, std::slice::from_ref(op)).map_err(|mut e| {
e.operation = index;
Error::new(e.path.as_str(), e.to_string())
})?;
if inserted_height.is_some_and(|height| {
target_depth
.checked_add(height)
.is_none_or(|depth| depth > max_depth)
}) {
return Err(standard_error(
index,
path,
"JSON nesting exceeds max_depth",
));
}
Ok(())
}
fn test_standard(
source: &Value,
test: &json_patch::TestOperation,
index: usize,
max_depth: usize,
) -> Result<(), Error> {
let path = test.path.as_str();
standard_subtree_height(&test.value, max_depth)
.map_err(|error| standard_error(index, path, error.message))?;
let current = test
.path
.resolve(source)
.map_err(|_| standard_error(index, path, "path is invalid"))?;
if !json_equal(current, &test.value) {
return Err(standard_error(index, path, "value did not match"));
}
Ok(())
}
fn moved_subtree_height(
result: &Value,
from: &json_patch::jsonptr::Pointer,
target_depth: usize,
max_depth: usize,
) -> Result<Option<usize>, Error> {
let source_depth = from.count();
if target_depth <= source_depth {
return Ok(None);
}
from.resolve(result)
.ok()
.map(|source| standard_subtree_height(source, max_depth))
.transpose()
}
fn standard_subtree_height(value: &Value, limit: usize) -> Result<usize, Error> {
if !value.is_array() && !value.is_object() {
return Ok(0);
}
let mut height = 0;
let mut pending = vec![(value, 0)];
while let Some((value, depth)) = pending.pop() {
if !value.is_array() && !value.is_object() {
continue;
}
if depth >= limit {
return Err(Error::new("", "JSON nesting exceeds max_depth"));
}
height = height.max(depth + 1);
match value {
Value::Array(values) => pending.extend(
values
.iter()
.filter(|value| value.is_array() || value.is_object())
.map(|value| (value, depth + 1)),
),
Value::Object(values) => pending.extend(
values
.values()
.filter(|value| value.is_array() || value.is_object())
.map(|value| (value, depth + 1)),
),
_ => {}
}
}
Ok(height)
}
pub(crate) fn json_equal(left: &Value, right: &Value) -> bool {
match (left, right) {
(Value::Number(a), Value::Number(b)) => numbers::numbers_equal(a, b),
(Value::Array(a), Value::Array(b)) => {
a.len() == b.len() && a.iter().zip(b).all(|(a, b)| json_equal(a, b))
}
(Value::Object(a), Value::Object(b)) => {
a.len() == b.len()
&& a.iter()
.all(|(key, a)| b.get(key).is_some_and(|b| json_equal(a, b)))
}
_ => left == right,
}
}
pub(crate) fn pointer(path: &str, key: impl fmt::Display) -> String {
let mut result = format!("{path}/{key}");
let start = path.len() + 1;
if result.as_bytes()[start..]
.iter()
.any(|byte| matches!(byte, b'~' | b'/'))
{
let escaped = result[start..].replace('~', "~0").replace('/', "~1");
result.truncate(start);
result.push_str(&escaped);
}
result
}