1use anyhow::{anyhow, Result};
2use indexmap::IndexMap;
3use serde_json::Value;
4use std::{
5 cell::RefCell,
6 mem,
7 rc::{Rc, Weak},
8};
9
10pub fn resolve_references(value: Value) -> Result<Value> {
11 let tree = Tree::from_json(value)?;
12 tree.resolve()?;
13 tree.to_json()
14}
15
16#[derive(Clone)]
17enum Node {
18 Reference {
19 path: String,
20 parent: Option<Weak<RefCell<Node>>>,
21 },
22 Object {
23 base: Option<String>,
24 children: IndexMap<String, Tree>,
25 resolved: bool,
26 parent: Option<Weak<RefCell<Node>>>,
27 },
28 Array {
29 children: Vec<Tree>,
30 resolved: bool,
31 parent: Option<Weak<RefCell<Node>>>,
32 },
33 String {
34 value: String,
35 parent: Option<Weak<RefCell<Node>>>,
36 },
37 Number {
38 value: serde_json::Number,
39 parent: Option<Weak<RefCell<Node>>>,
40 },
41 Bool {
42 value: bool,
43 parent: Option<Weak<RefCell<Node>>>,
44 },
45 Null {
46 parent: Option<Weak<RefCell<Node>>>,
47 },
48}
49
50#[derive(Clone)]
51struct Tree(Rc<RefCell<Node>>);
52
53impl Tree {
54 pub fn new(node: Node) -> Self {
55 Self(Rc::new(RefCell::new(node)))
56 }
57
58 fn from_json(value: Value) -> Result<Self> {
59 match value {
60 Value::String(value) => {
61 if let Some(path) = value.strip_prefix("$") {
62 Ok(Self::new(Node::Reference {
63 path: path.to_string(),
64 parent: None,
65 }))
66 } else {
67 Ok(Self::new(Node::String {
68 value,
69 parent: None,
70 }))
71 }
72 }
73 Value::Number(value) => Ok(Self::new(Node::Number {
74 value,
75 parent: None,
76 })),
77 Value::Bool(value) => Ok(Self::new(Node::Bool {
78 value,
79 parent: None,
80 })),
81 Value::Null => Ok(Self::new(Node::Null { parent: None })),
82 Value::Object(object) => {
83 let tree = Self::new(Node::Object {
84 base: Default::default(),
85 children: Default::default(),
86 resolved: false,
87 parent: None,
88 });
89 let mut children = IndexMap::new();
90 let mut resolved = true;
91 let mut base = None;
92 for (key, value) in object.into_iter() {
93 let value = if key == "extends" {
94 if value.is_string() {
95 if let Value::String(value) = value {
96 base = value.strip_prefix("$").map(str::to_string);
97 resolved = false;
98 Self::new(Node::String {
99 value,
100 parent: None,
101 })
102 } else {
103 unreachable!()
104 }
105 } else {
106 Tree::from_json(value)?
107 }
108 } else {
109 Tree::from_json(value)?
110 };
111 value
112 .0
113 .borrow_mut()
114 .set_parent(Some(Rc::downgrade(&tree.0)));
115 resolved &= value.is_resolved();
116 children.insert(key.clone(), value);
117 }
118
119 *tree.0.borrow_mut() = Node::Object {
120 base,
121 children,
122 resolved,
123 parent: None,
124 };
125 Ok(tree)
126 }
127 Value::Array(elements) => {
128 let tree = Self::new(Node::Array {
129 children: Default::default(),
130 resolved: false,
131 parent: None,
132 });
133
134 let mut children = Vec::new();
135 let mut resolved = true;
136 for element in elements {
137 let child = Tree::from_json(element)?;
138 child
139 .0
140 .borrow_mut()
141 .set_parent(Some(Rc::downgrade(&tree.0)));
142 resolved &= child.is_resolved();
143 children.push(child);
144 }
145
146 *tree.0.borrow_mut() = Node::Array {
147 children,
148 resolved,
149 parent: None,
150 };
151 Ok(tree)
152 }
153 }
154 }
155
156 fn to_json(&self) -> Result<Value> {
157 match &*self.0.borrow() {
158 Node::Reference { .. } => Err(anyhow!("unresolved tree")),
159 Node::String { value, .. } => Ok(Value::String(value.clone())),
160 Node::Number { value, .. } => Ok(Value::Number(value.clone())),
161 Node::Bool { value, .. } => Ok(Value::Bool(*value)),
162 Node::Null { .. } => Ok(Value::Null),
163 Node::Object { children, .. } => {
164 let mut json_children = serde_json::Map::new();
165 for (key, value) in children {
166 json_children.insert(key.clone(), value.to_json()?);
167 }
168 Ok(Value::Object(json_children))
169 }
170 Node::Array { children, .. } => {
171 let mut json_children = Vec::new();
172 for child in children {
173 json_children.push(child.to_json()?);
174 }
175 Ok(Value::Array(json_children))
176 }
177 }
178 }
179
180 fn parent(&self) -> Option<Tree> {
181 match &*self.0.borrow() {
182 Node::Reference { parent, .. }
183 | Node::Object { parent, .. }
184 | Node::Array { parent, .. }
185 | Node::String { parent, .. }
186 | Node::Number { parent, .. }
187 | Node::Bool { parent, .. }
188 | Node::Null { parent } => parent.as_ref().and_then(|p| p.upgrade()).map(Tree),
189 }
190 }
191
192 fn get(&self, path: &str) -> Result<Option<Tree>> {
193 let mut tree = self.clone();
194 for component in path.split('.') {
195 let node = tree.0.borrow();
196 match &*node {
197 Node::Object { children, .. } => {
198 if let Some(subtree) = children.get(component).cloned() {
199 drop(node);
200 tree = subtree;
201 } else {
202 return Err(anyhow!(
203 "key \"{}\" does not exist in path \"{}\"",
204 component,
205 path
206 ));
207 }
208 }
209 Node::Reference { .. } => return Ok(None),
210 Node::Array { .. }
211 | Node::String { .. }
212 | Node::Number { .. }
213 | Node::Bool { .. }
214 | Node::Null { .. } => {
215 return Err(anyhow!(
216 "key \"{}\" in path \"{}\" is not an object",
217 component,
218 path
219 ))
220 }
221 }
222 }
223
224 Ok(Some(tree))
225 }
226
227 fn is_resolved(&self) -> bool {
228 match &*self.0.borrow() {
229 Node::Reference { .. } => false,
230 Node::Object { resolved, .. } | Node::Array { resolved, .. } => *resolved,
231 Node::String { .. } | Node::Number { .. } | Node::Bool { .. } | Node::Null { .. } => {
232 true
233 }
234 }
235 }
236
237 fn update_resolved(&self) {
238 match &mut *self.0.borrow_mut() {
239 Node::Object {
240 resolved,
241 base,
242 children,
243 ..
244 } => {
245 *resolved = base.is_none() && children.values().all(|c| c.is_resolved());
246 }
247 Node::Array {
248 resolved, children, ..
249 } => {
250 *resolved = children.iter().all(|c| c.is_resolved());
251 }
252 _ => {}
253 }
254 }
255
256 pub fn resolve(&self) -> Result<()> {
257 let mut unresolved = vec![self.clone()];
258 let mut made_progress = true;
259
260 while made_progress && !unresolved.is_empty() {
261 made_progress = false;
262 for mut tree in mem::take(&mut unresolved) {
263 made_progress |= tree.resolve_subtree(self, &mut unresolved)?;
264 if tree.is_resolved() {
265 while let Some(parent) = tree.parent() {
266 parent.update_resolved();
267 if !parent.is_resolved() {
268 break;
269 }
270 tree = parent;
271 }
272 }
273 }
274 }
275
276 if unresolved.is_empty() {
277 Ok(())
278 } else {
279 Err(anyhow!("tree contains cycles"))
280 }
281 }
282
283 fn resolve_subtree(&self, root: &Tree, unresolved: &mut Vec<Tree>) -> Result<bool> {
284 let node = self.0.borrow();
285 match &*node {
286 Node::Reference { path, parent } => {
287 if let Some(subtree) = root.get(&path)? {
288 if subtree.is_resolved() {
289 let parent = parent.clone();
290 drop(node);
291 let mut new_node = subtree.0.borrow().clone();
292 new_node.set_parent(parent);
293 *self.0.borrow_mut() = new_node;
294 Ok(true)
295 } else {
296 unresolved.push(self.clone());
297 Ok(false)
298 }
299 } else {
300 unresolved.push(self.clone());
301 Ok(false)
302 }
303 }
304 Node::Object {
305 base,
306 children,
307 resolved,
308 ..
309 } => {
310 if *resolved {
311 Ok(false)
312 } else {
313 let mut made_progress = false;
314 let mut children_resolved = true;
315 for child in children.values() {
316 made_progress |= child.resolve_subtree(root, unresolved)?;
317 children_resolved &= child.is_resolved();
318 }
319
320 if children_resolved {
321 let mut has_base = false;
322 let mut resolved_base = None;
323 if let Some(base) = base {
324 has_base = true;
325 if let Some(base) = root.get(base)? {
326 if base.is_resolved() {
327 resolved_base = Some(base);
328 }
329 }
330 }
331
332 drop(node);
333
334 if let Some(base) = resolved_base.as_ref() {
335 self.extend_from(&base);
336 made_progress = true;
337 }
338
339 if let Node::Object { resolved, base, .. } = &mut *self.0.borrow_mut() {
340 if has_base {
341 if resolved_base.is_some() {
342 base.take();
343 *resolved = true;
344 } else {
345 unresolved.push(self.clone());
346 }
347 } else {
348 *resolved = true;
349 }
350 }
351 } else if base.is_some() {
352 unresolved.push(self.clone());
353 }
354
355 Ok(made_progress)
356 }
357 }
358 Node::Array {
359 children, resolved, ..
360 } => {
361 if *resolved {
362 Ok(false)
363 } else {
364 let mut made_progress = false;
365 let mut children_resolved = true;
366 for child in children.iter() {
367 made_progress |= child.resolve_subtree(root, unresolved)?;
368 children_resolved &= child.is_resolved();
369 }
370
371 if children_resolved {
372 drop(node);
373
374 if let Node::Array { resolved, .. } = &mut *self.0.borrow_mut() {
375 *resolved = true;
376 }
377 }
378
379 Ok(made_progress)
380 }
381 }
382 Node::String { .. } | Node::Number { .. } | Node::Bool { .. } | Node::Null { .. } => {
383 Ok(false)
384 }
385 }
386 }
387
388 fn extend_from(&self, base: &Tree) {
389 if Rc::ptr_eq(&self.0, &base.0) {
390 return;
391 }
392
393 if let (
394 Node::Object { children, .. },
395 Node::Object {
396 children: base_children,
397 ..
398 },
399 ) = (&mut *self.0.borrow_mut(), &*base.0.borrow())
400 {
401 for (key, base_value) in base_children {
402 if let Some(value) = children.get(key) {
403 value.extend_from(base_value);
404 } else {
405 let base_value = base_value.clone();
406 base_value
407 .0
408 .borrow_mut()
409 .set_parent(Some(Rc::downgrade(&self.0)));
410 children.insert(key.clone(), base_value);
411 }
412 }
413 }
414 }
415}
416
417impl Node {
418 fn set_parent(&mut self, new_parent: Option<Weak<RefCell<Node>>>) {
419 match self {
420 Node::Reference { parent, .. }
421 | Node::Object { parent, .. }
422 | Node::Array { parent, .. }
423 | Node::String { parent, .. }
424 | Node::Number { parent, .. }
425 | Node::Bool { parent, .. }
426 | Node::Null { parent } => *parent = new_parent,
427 }
428 }
429}
430
431#[cfg(test)]
432mod test {
433 use super::*;
434
435 #[test]
436 fn test_references() {
437 let json = serde_json::json!({
438 "a": {
439 "extends": "$g",
440 "x": "$b.d"
441 },
442 "b": {
443 "c": "$a",
444 "d": "$e.f"
445 },
446 "e": {
447 "extends": "$a",
448 "f": "1"
449 },
450 "g": {
451 "h": 2
452 }
453 });
454
455 assert_eq!(
456 resolve_references(json).unwrap(),
457 serde_json::json!({
458 "a": {
459 "extends": "$g",
460 "x": "1",
461 "h": 2
462 },
463 "b": {
464 "c": {
465 "extends": "$g",
466 "x": "1",
467 "h": 2
468 },
469 "d": "1"
470 },
471 "e": {
472 "extends": "$a",
473 "f": "1",
474 "x": "1",
475 "h": 2
476 },
477 "g": {
478 "h": 2
479 }
480 })
481 )
482 }
483
484 #[test]
485 fn test_cycles() {
486 let json = serde_json::json!({
487 "a": {
488 "b": "$c.d"
489 },
490 "c": {
491 "d": "$a.b",
492 },
493 });
494
495 assert!(resolve_references(json).is_err());
496 }
497}