use std::borrow::Cow;
use std::collections::HashMap;
use jsonschema::{Draft, ReferencingError, Registry};
use referencing::{Resolver, ResourceRef};
use serde_json::Value;
use super::{NOT_CHECKS, children};
pub(super) const MAX_SCHEMA_DEPTH: usize = 128;
const MAX_SCHEMA_SIZE: usize = 5_000_000;
const REF_KEYS: [&str; 3] = ["$ref", "$dynamicRef", "$recursiveRef"];
const UNEVALUATED: [&str; 2] = ["unevaluatedProperties", "unevaluatedItems"];
const IN_PLACE: [&str; 7] = [
"allOf",
"anyOf",
"oneOf",
"if",
"then",
"else",
"dependentSchemas",
];
const DEFAULT_BASE: &str = "json-schema:///";
pub(super) fn registry(schema: &Value) -> Result<Registry<'_>, ReferencingError> {
let resource = ResourceRef::new(schema, Draft::default().detect(schema));
Registry::new()
.draft(resource.draft())
.add(resource.id().unwrap_or(DEFAULT_BASE), resource)?
.prepare()
}
pub(super) struct Reach<'r> {
root: &'r Value,
parents: HashMap<*const Value, (&'r Value, Cow<'r, str>)>,
measured: HashMap<(*const Value, bool), Measure>,
open: HashMap<*const Value, usize>,
refs: Vec<(&'r Value, &'static str)>,
kept: bool,
}
#[derive(Clone, Copy)]
enum At<'a, 'r> {
Schema(&'a Resolver<'r>, Draft),
Under(&'a Resolver<'r>, Draft, &'a [*const Value]),
}
impl<'r> Reach<'r> {
pub(super) fn new(root: &'r Value) -> Self {
let mut reach = Reach {
root,
parents: HashMap::new(),
measured: HashMap::new(),
open: HashMap::new(),
refs: Vec::new(),
kept: true,
};
reach.collect(root);
reach
}
fn collect(&mut self, value: &'r Value) {
for (key, child) in children(value) {
if child.is_object() || child.is_array() {
self.parents.insert(child, (value, key));
self.collect(child);
}
}
}
fn path(&self, mut value: &'r Value) -> Option<Vec<String>> {
let mut path = Vec::new();
while !std::ptr::eq(value, self.root) {
let (parent, key) = self.parents.get(&std::ptr::from_ref(value))?;
path.push(key.clone().into_owned());
value = parent;
}
path.reverse();
Some(path)
}
pub(super) fn measure(mut self, registry: &'r Registry<'r>) -> Result<bool, Over> {
let draft = Draft::default().detect(self.root);
let resource = ResourceRef::new(self.root, draft);
let base = referencing::uri::from_str(resource.id().unwrap_or(DEFAULT_BASE))
.map_err(|error| self.over_at(None, Problem::Unresolved(error.to_string())))?;
let resolver = registry
.resolver(base)
.in_subresource(resource)
.map_err(|error| self.over_at(None, Problem::Unresolved(error.to_string())))?;
self.visit(self.root, 1, At::Schema(&resolver, draft))?;
Ok(self.kept)
}
fn over_at(&self, spot: Option<(&'r Value, &str)>, problem: Problem) -> Over {
let refs = self.refs.iter().rev().map(|&(at, key)| (at, key));
let (path, key) = spot
.into_iter()
.chain(refs)
.find_map(|(at, key)| Some((self.path(at)?, key.to_owned())))
.unwrap_or_else(|| (Vec::new(), "$ref".to_owned()));
Over { path, key, problem }
}
fn follow(
&mut self,
value: &'r Value,
level: usize,
resolver: &Resolver<'r>,
draft: Draft,
below: &mut Visit,
) -> Result<usize, Over> {
let mut size: usize = 0;
for key in REF_KEYS {
let Some(reference) = value.get(key).and_then(Value::as_str) else {
continue;
};
if key != "$ref" && !draft.is_known_keyword(key) {
continue;
}
let (target, target_resolver, target_draft) = match resolver.lookup(reference) {
Ok(target) => target.into_inner(),
Err(error) => {
let problem = Problem::Unresolved(error.to_string());
return Err(self.over_at(Some((value, key)), problem));
}
};
let top = self.path(target).and_then(|path| path.into_iter().next());
self.kept &= top.is_some_and(|top| NOT_CHECKS.contains(&top.as_str()));
if let Some(&open) = self.open.get(&std::ptr::from_ref(target)) {
below.cut = below.cut.min(open);
continue;
}
self.refs.push((value, key));
let child = self.visit(
target,
level + 1,
At::Schema(&target_resolver, target_draft),
)?;
size = size.saturating_add(child.measure.size);
if below.add(child) {
return Err(self.over_at(None, Problem::Big));
}
self.refs.pop();
}
Ok(size)
}
fn visit(&mut self, value: &'r Value, level: usize, at: At<'_, 'r>) -> Result<Visit, Over> {
if !(value.is_object() || value.is_array()) {
return Ok(Visit {
measure: Measure::default(),
cut: usize::MAX,
});
}
let address: *const Value = value;
let memo = (address, matches!(at, At::Schema(..)));
let known = self.measured.get(&memo).copied();
if level + known.map_or(1, |m| m.height) - 1 > MAX_SCHEMA_DEPTH {
return Err(self.over_at(None, Problem::Deep));
}
if let Some(measure) = known {
return Ok(Visit {
measure,
cut: usize::MAX,
});
}
self.open.insert(address, level);
let mut below = Visit {
measure: Measure { height: 0, size: 1 },
cut: usize::MAX,
};
let (resolver, draft, subs) = match at {
At::Schema(resolver, draft) => {
let mut subs: Vec<*const Value> = draft
.subresources_of(value)
.map(std::ptr::from_ref)
.collect();
subs.sort_unstable();
(resolver, draft, Cow::Owned(subs))
}
At::Under(resolver, draft, subs) => (resolver, draft, Cow::Borrowed(subs)),
};
let schema = matches!(at, At::Schema(..));
let mut again: usize = 0;
for (key, member) in children(value) {
let mut child = if subs.binary_search(&std::ptr::from_ref(member)).is_ok() {
let draft = draft.detect(member);
let resolver = resolver
.in_subresource(ResourceRef::new(member, draft))
.map_err(|e| {
self.over_at(Some((member, "$id")), Problem::Unresolved(e.to_string()))
})?;
self.visit(member, level + 1, At::Schema(&resolver, draft))?
} else {
self.visit(member, level + 1, At::Under(resolver, draft, &subs))?
};
if schema && matches!(key.as_ref(), "enum" | "const") {
child.measure.size = child.measure.size.saturating_add(scalars(member));
}
if schema && IN_PLACE.contains(&key.as_ref()) {
again = again.saturating_add(child.measure.size);
}
if below.add(child) {
let spot = self.refs.is_empty().then_some((value, key.as_ref()));
return Err(self.over_at(spot, Problem::Big));
}
}
if schema {
again = again.saturating_add(self.follow(value, level, resolver, draft, &mut below)?);
if let Some(key) = UNEVALUATED
.into_iter()
.find(|key| value.get(key).is_some() && draft.is_known_keyword(key))
{
let again = Visit {
measure: Measure {
height: 0,
size: again,
},
cut: usize::MAX,
};
if below.add(again) {
return Err(self.over_at(Some((value, key)), Problem::Twice));
}
}
}
self.open.remove(&address);
below.measure.height += 1;
if below.cut >= level {
below.cut = usize::MAX;
self.measured.insert(memo, below.measure);
}
Ok(below)
}
}
fn scalars(value: &Value) -> usize {
match value {
Value::Object(_) | Value::Array(_) => {
children(value).map(|(_, child)| scalars(child)).sum()
}
_ => 1,
}
}
#[derive(Clone, Copy, Default)]
struct Measure {
height: usize,
size: usize,
}
#[derive(Clone, Copy)]
struct Visit {
measure: Measure,
cut: usize,
}
impl Visit {
fn add(&mut self, child: Visit) -> bool {
self.measure.height = self.measure.height.max(child.measure.height);
self.measure.size = self.measure.size.saturating_add(child.measure.size);
self.cut = self.cut.min(child.cut);
self.measure.size > MAX_SCHEMA_SIZE
}
}
enum Problem {
Deep,
Big,
Twice,
Unresolved(String),
}
pub(super) struct Over {
pub(super) path: Vec<String>,
pub(super) key: String,
problem: Problem,
}
impl Over {
pub(super) fn message(&self) -> String {
let key = &self.key;
match &self.problem {
Problem::Deep => format!(
"this `{key}` leads more than {MAX_SCHEMA_DEPTH} levels deep, counting each \
`$ref` followed as a level"
),
Problem::Big => format!(
"this `{key}` takes the schema past {MAX_SCHEMA_SIZE} objects and arrays, \
counting what each `$ref` points at every time it is followed"
),
Problem::Twice => format!(
"this `{key}` takes the schema past {MAX_SCHEMA_SIZE} objects and arrays, \
counting twice the schemas beside it that jsonschema checks again for it"
),
Problem::Unresolved(error) => format!("this `{key}` cannot be resolved: {error}"),
}
}
}
#[cfg(test)]
mod tests {
use super::{DEFAULT_BASE, MAX_SCHEMA_SIZE, Measure, Over, Problem, Reach, Visit, registry};
use jsonschema::Draft;
use serde_json::{Value, json};
#[test]
fn a_schema_of_exactly_the_size_limit_fits() {
let visit = |size| Visit {
measure: Measure { height: 1, size },
cut: usize::MAX,
};
let mut schema = visit(MAX_SCHEMA_SIZE - 1);
assert!(!schema.add(visit(1)));
assert!(schema.add(visit(1)));
}
fn over(schema: &Value) -> Option<Over> {
let registry = registry(schema).expect("a registry");
Reach::new(schema).measure(®istry).err()
}
fn target(schema: &Value, reference: &str) -> Option<String> {
let registry = registry(schema).ok()?;
let resource = referencing::ResourceRef::new(schema, Draft::default().detect(schema));
let base = referencing::uri::from_str(resource.id().unwrap_or(DEFAULT_BASE)).ok()?;
let resolver = registry.resolver(base).in_subresource(resource).ok()?;
let lookup = resolver.lookup(reference).ok()?;
let path = Reach::new(schema).path(lookup.contents())?;
Some(path.join("/"))
}
#[test]
fn refs_resolve_by_pointer_anchor_and_id_against_their_base() {
let schema = json!({
"$id": "https://example.com/root.json",
"$defs": {
"a/b": {"anyOf": [{"$anchor": "x"}, {"type": "string"}]},
"%": {"type": "null"},
"sub": {"$id": "sub.json", "$defs": {"c": {}}},
"p": {"$id": "p/", "$defs": {"l": {"$id": "l", "type": "string"}}},
"q": {"$id": "q/", "$defs": {"l": {"$id": "l", "type": "number"}}},
},
});
let path = |reference| target(&schema, reference);
assert_eq!(path("#").as_deref(), Some(""));
assert_eq!(
path("#/$defs/a~1b/anyOf/1").as_deref(),
Some("$defs/a/b/anyOf/1")
);
assert_eq!(path("#/$defs/%25").as_deref(), Some("$defs/%"));
assert_eq!(path("#x").as_deref(), Some("$defs/a/b/anyOf/0"));
assert_eq!(path("root.json#/$defs").as_deref(), Some("$defs"));
assert_eq!(
path("https://example.com/sub.json#/$defs/c").as_deref(),
Some("$defs/sub/$defs/c")
);
assert_eq!(path("q/l").as_deref(), Some("$defs/q/$defs/l"));
assert_eq!(path("p/l").as_deref(), Some("$defs/p/$defs/l"));
assert_eq!(path("l"), None);
assert_eq!(path("#/$defs/none"), None);
assert_eq!(path("other.json"), None);
let old = json!({"$schema": "http://json-schema.org/draft-07/schema#", "definitions": {"%": {"$id": "#old"}}});
assert_eq!(target(&old, "#old").as_deref(), Some("definitions/%"));
}
fn nested(depth: usize, last: Value) -> Value {
(0..depth / 2).fold(last, |inner, _| json!({"allOf": [inner]}))
}
#[test]
fn ref_chains_count_through_arrays_and_from_each_place_they_are_reached() {
let too_deep = |schema: &Value| {
over(schema)
.filter(|over| matches!(over.problem, Problem::Deep))
.map(|over| (over.path.join("/"), over.key))
};
let long = nested(60, json!({"type": "integer"}));
let schema = json!({
"$defs": {"long": long},
"allOf": [nested(100, json!({"$ref": "#/$defs/long"}))],
});
let path = format!("allOf/0{}", "/allOf/0".repeat(50));
assert_eq!(too_deep(&schema), Some((path, "$ref".to_owned())));
let schema = json!({"$defs": {"long": nested(60, json!(true))}, "allOf": [{"$ref": "#/$defs/long"}]});
assert_eq!(too_deep(&schema), None);
let mut defs = serde_json::Map::new();
for i in 0..100 {
defs.insert(
format!("d%{i}"),
json!({"allOf": [{"$ref": format!("#/$defs/d%25{}", i + 1)}]}),
);
}
let schema = json!({"$defs": defs, "$ref": "#/$defs/d%250"});
assert!(too_deep(&schema).is_some());
}
fn cycles(k: usize) -> Value {
let mut defs = serde_json::Map::new();
for i in 0..k {
let end = match i {
0 => json!({"type": "integer"}),
_ => json!({"$ref": format!("#/$defs/y{}", i - 1)}),
};
defs.insert(
format!("x{i}"),
json!({"additionalProperties": {"$ref": format!("#/$defs/y{i}")}, "allOf": [nested(120, end)]}),
);
defs.insert(format!("y{i}"), json!({"$ref": format!("#/$defs/x{i}")}));
}
json!({"$defs": defs, "$ref": format!("#/$defs/y{}", k - 1)})
}
#[test]
fn a_height_measured_while_a_ref_back_up_was_skipped_is_not_reused() {
let deep = over(&cycles(2)).is_some_and(|over| matches!(over.problem, Problem::Deep));
assert!(deep);
assert!(over(&cycles(1)).is_none());
}
#[test]
fn a_schema_too_big_once_its_refs_are_followed_is_caught() {
type Shape = fn(String) -> Value;
let fan_out = |levels: usize, shape: Shape| {
let mut defs = serde_json::Map::new();
for i in 0..levels {
defs.insert(format!("d{i}"), shape(format!("#/$defs/d{}", i + 1)));
}
defs.insert(format!("d{levels}"), json!({"type": "string"}));
json!({"$defs": defs, "$ref": "#/$defs/d0"})
};
let shapes: [(Shape, &str); 4] = [
(
|next| json!({"anyOf": [{"$ref": next}, {"$ref": next}]}),
"$ref",
),
(
|next| json!({"allOf": [{"$ref": next}, {"$ref": next}]}),
"$ref",
),
(
|next| json!({"properties": {"a": {"$ref": next}, "b": {"$ref": next}}}),
"$ref",
),
(
|next| json!({"$ref": next, "$dynamicRef": next}),
"$dynamicRef",
),
];
for (shape, key) in shapes {
let big = over(&fan_out(24, shape))
.is_some_and(|over| matches!(over.problem, Problem::Big) && over.key == key);
assert!(big);
assert!(over(&fan_out(16, shape)).is_none());
}
}
#[test]
fn enum_and_const_values_count_toward_the_size() {
let fan_out = |last: Value| {
let mut defs = serde_json::Map::new();
for i in 0..16 {
let next = format!("#/$defs/d{}", i + 1);
defs.insert(
format!("d{i}"),
json!({"anyOf": [{"$ref": next}, {"$ref": next}]}),
);
}
defs.insert("d16".to_owned(), last);
json!({"$defs": defs, "$ref": "#/$defs/d0"})
};
let numbers: Vec<usize> = (0..100).collect();
for last in [json!({"enum": numbers}), json!({"const": [numbers]})] {
let big = over(&fan_out(last)).is_some_and(|over| matches!(over.problem, Problem::Big));
assert!(big);
}
assert!(over(&fan_out(json!({"type": "string"}))).is_none());
assert!(over(&fan_out(json!({"default": numbers}))).is_none());
}
#[test]
fn a_reference_keyword_of_another_draft_is_not_followed() {
for (draft, key) in [
("http://json-schema.org/draft-07/schema#", "$dynamicRef"),
("http://json-schema.org/draft-07/schema#", "$recursiveRef"),
(
"https://json-schema.org/draft/2019-09/schema",
"$dynamicRef",
),
] {
let schema = json!({"$schema": draft, "properties": {"a": {key: "#/nowhere"}}});
assert!(over(&schema).is_none(), "{draft} {key}");
}
let schema = json!({"properties": {"a": {"$dynamicRef": "#/nowhere"}}});
let unresolved = over(&schema).is_some_and(|over| {
matches!(over.problem, Problem::Unresolved(_)) && over.path == ["properties", "a"]
});
assert!(unresolved);
}
}