jonaskruckenberg.de
Next Generation WASM Microkernel Operating System
1// Copyright 2025 Jonas Kruckenberg
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8// This Source Code Form is subject to the terms of the Mozilla Public
9// License, v. 2.0. If a copy of the MPL was not distributed with this
10// file, You can obtain one at https://mozilla.org/MPL/2.0/.
11
12//! Implements patching of TOML documents
13//!
14//! The `toml_edit` crate is great, but it has a major limitation: tables are
15//! ordered with a global `position`. This means that to insert a new table,
16//! you have to shift everything after that table downwards, and adjust relative
17//! positions within the new table.
18//!
19//! This crate exposes a single function [`merge_toml_documents`] which does
20//! this for you!
21
22use eyre::{Result, bail, eyre};
23use std::collections::BTreeMap;
24use toml_edit::{visit::Visit, visit_mut::VisitMut};
25
26pub fn merge_toml_documents(
27 original: &mut toml_edit::DocumentMut,
28 mut patches: toml_edit::DocumentMut,
29) -> Result<()> {
30 // Find offsets where we need to insert gaps for incoming patches
31 let mut offsets = BTreeMap::new();
32 compute_offsets(original, &patches, &mut offsets)?;
33
34 // Convert from single to cumulative offsets. Since this is in a BTreeMap,
35 // it's already sorted, so we accumulate in a single pass.
36 let mut sum = 0;
37 for i in offsets.values_mut() {
38 let prev = *i;
39 *i += sum;
40 sum += prev;
41 }
42
43 // Apply offsets, adding gaps to the original document
44 let mut visitor = OffsetVisitor { offsets: &offsets };
45 visitor.visit_document_mut(original);
46
47 // Now that we've opened up gaps, we can splice in the new data
48 merge_toml_tables(original.as_table_mut(), &mut patches)
49}
50
51/// Computes offsets that will be applied when `patches` is merged
52///
53/// Values are accumulated into `offsets`
54fn compute_offsets(
55 original: &toml_edit::Table,
56 patches: &toml_edit::Table,
57 offsets: &mut BTreeMap<usize, usize>,
58) -> Result<()> {
59 for (k, v) in patches.iter() {
60 if let Some(u) = original.get(k) {
61 if u.type_name() != v.type_name() {
62 bail!(
63 "type mismatch for '{k}': {} != {}",
64 u.type_name(),
65 v.type_name()
66 );
67 }
68 use toml_edit::Item;
69 match u {
70 Item::None | Item::Value(..) => (),
71 Item::Table(u) => {
72 // Recurse!
73 compute_offsets(u, v.as_table().unwrap(), offsets)?;
74 }
75 Item::ArrayOfTables(..) => {
76 let mut visitor = TableRangeVisitor::default();
77 visitor.visit_item(u);
78 let range_in = visitor
79 .range
80 .ok_or_else(|| eyre!("cannot append to an empty array of tables"))?;
81
82 // Find the range spanned by the incoming tables, which will
83 // be appended to the list `u`
84 let mut visitor = TableRangeVisitor::default();
85 visitor.visit_item(v);
86 let patch_span = visitor
87 .range
88 .ok_or_else(|| eyre!("cannot append empty array of tables"))?;
89
90 // Record the shift here
91 offsets.insert(range_in.end, patch_span.len());
92 }
93 }
94 } else {
95 // We are going to insert our new values after all of the old values
96 //
97 // First, we need to find the maximum position in our original table
98 let mut visitor = TableRangeVisitor::default();
99 visitor.visit_table(original);
100 let last = visitor.range.map(|r| r.end).unwrap_or_default();
101
102 // We'll be applying an offset based on the size of the incoming
103 // list of patches (in table positions)
104 let mut visitor = TableRangeVisitor::default();
105 visitor.visit_table(patches);
106 if let Some(r) = visitor.range {
107 offsets.insert(last + 1, r.len());
108 }
109 }
110 }
111 Ok(())
112}
113
114/// Accumulates the full range of table positions
115#[derive(Default)]
116struct TableRangeVisitor {
117 range: Option<std::ops::Range<usize>>,
118}
119
120impl<'doc> Visit<'doc> for TableRangeVisitor {
121 fn visit_table(&mut self, t: &'doc toml_edit::Table) {
122 if let Some(pos) = t.position() {
123 self.range = Some(match self.range.take() {
124 Some(r) => r.start.min(pos)..r.end.max(pos + 1),
125 None => pos..pos + 1,
126 });
127 }
128 // call the default implementation to recurse
129 self.visit_table_like(t);
130 }
131}
132
133/// Applies an offset to every table position
134#[derive(Default)]
135struct TableShiftVisitor {
136 offset: isize,
137}
138
139impl VisitMut for TableShiftVisitor {
140 fn visit_table_mut(&mut self, t: &mut toml_edit::Table) {
141 if let Some(pos) = t.position() {
142 let pos: isize = pos.try_into().unwrap();
143 t.set_position((pos + self.offset).try_into().unwrap())
144 }
145 // call the default implementation to recurse
146 self.visit_table_like_mut(t);
147 }
148}
149
150/// Applies an offset that varies based on table position
151struct OffsetVisitor<'a> {
152 /// Map from position in original table to offset
153 ///
154 /// This is a sparse map containing **cumulative** offsets.
155 ///
156 /// The offset at position `i` is `self.offsets[j]`, where `j` is the
157 /// largest key such that `j <= i`.
158 offsets: &'a BTreeMap<usize, usize>,
159}
160
161impl<'a> VisitMut for OffsetVisitor<'a> {
162 fn visit_table_mut(&mut self, t: &mut toml_edit::Table) {
163 if let Some(pos) = t.position() {
164 // Find the largest offset with a value <= pos, which determines
165 // the cumulative offset at this point in the document.
166 //
167 // If `pos` is _before_ the first offset in the table, then return a
168 // base case with no offset, i.e. (0, 0)
169 let (prev_pos, offset) = self.offsets.range(0..=pos).next_back().unwrap_or((&0, &0));
170 assert!(*prev_pos <= pos); // sanity-checking
171 t.set_position(offset + pos);
172 }
173 self.visit_table_like_mut(t);
174 }
175}
176
177/// Merges a pair of TOML tables
178///
179/// The incoming `patches` table is modified during execution to put its
180/// position at the end of the original table.
181///
182/// When this function is called, `original` must include gaps for `patches`
183fn merge_toml_tables(
184 original: &mut toml_edit::Table,
185 patches: &mut toml_edit::Table,
186) -> Result<()> {
187 for (k, v) in patches.iter_mut() {
188 if let Some(u) = original.get_mut(k.get()) {
189 assert_eq!(u.type_name(), v.type_name()); // already checked
190 use toml_edit::Item;
191 match u {
192 Item::None => bail!("can't patch `None`"),
193 Item::Value(u) => {
194 // I'm not sure whether it's possible for the Item
195 // type_name to match and Value type_name to *not*
196 // match, but better safe than sorry here.
197 let v = v.as_value().unwrap();
198 if u.type_name() != v.type_name() {
199 bail!(
200 "type mismatch for '{k}': {} != {}",
201 u.type_name(),
202 v.type_name()
203 );
204 }
205
206 use toml_edit::Value;
207 match u {
208 // Single values replace the previous value
209 Value::Float(..)
210 | Value::String(..)
211 | Value::Integer(..)
212 | Value::Boolean(..)
213 | Value::Datetime(..) => *u = v.clone(),
214
215 // Inline tables are not yet supported, but should be
216 // merged once we get around to implementing it
217 Value::InlineTable(..) => {
218 bail!("patching inline tables is not yet implemented");
219 }
220 // Arrays are extended
221 Value::Array(u) => {
222 u.extend(v.as_array().unwrap().iter().cloned());
223 }
224 }
225 }
226 Item::Table(u) => {
227 // Recurse!
228 merge_toml_tables(u, v.as_table_mut().unwrap())?;
229 }
230 Item::ArrayOfTables(arr) => {
231 // Compute an offset based on table position
232 let mut visitor = TableRangeVisitor::default();
233 visitor.visit_array_of_tables(arr);
234 let range_in = visitor.range.unwrap();
235 let last = range_in.end;
236
237 let mut visitor = TableRangeVisitor::default();
238 visitor.visit_item(v);
239 let start = visitor.range.map(|r| r.start as isize).unwrap();
240 let offset = last as isize - start;
241
242 // Apply that offset to the incoming tables
243 let mut visitor = TableShiftVisitor { offset };
244 visitor.visit_item_mut(v);
245
246 // Merge by extending the table array
247 arr.extend(v.as_array_of_tables().unwrap().iter().cloned());
248 }
249 }
250 } else {
251 let mut visitor = TableRangeVisitor::default();
252 visitor.visit_table(original);
253 let last = visitor.range.map(|r| r.end).unwrap_or_default();
254
255 let mut visitor = TableRangeVisitor::default();
256 visitor.visit_item(v);
257 let start = visitor.range.map(|r| r.start as isize).unwrap_or(0);
258 let offset = last as isize - start;
259
260 // Apply that offset to the incoming tables
261 let mut visitor = TableShiftVisitor { offset };
262 visitor.visit_item_mut(v);
263
264 // Merge by inserting the new element
265 original.insert(k.get(), v.clone());
266 }
267 }
268 Ok(())
269}
270
271#[cfg(test)]
272mod tests {
273 use super::*;
274 use indoc::indoc;
275
276 fn patch_and_compare(a: &str, b: &str, out: &str) {
277 let mut a: toml_edit::DocumentMut = a.parse().unwrap();
278 let b = b.parse().unwrap();
279 merge_toml_documents(&mut a, b).unwrap();
280 if a.to_string() != out {
281 eprintln!("patching failed. Got result:");
282 eprintln!("{}", a.to_string());
283 eprintln!("----------------");
284 eprintln!("{}", out);
285 }
286 assert_eq!(a.to_string(), out);
287 }
288 #[test]
289 fn test_patching() {
290 patch_and_compare(
291 indoc! {r#"
292 name = "foo"
293 age = 37
294 "#},
295 indoc! {r#"
296 age = 38
297 "#},
298 indoc! {r#"
299 name = "foo"
300 age = 38
301 "#},
302 );
303 patch_and_compare(
304 indoc! {r#"
305 name = "foo"
306 age = 37
307
308 [nested]
309 hi = "there"
310 "#},
311 indoc! {r#"
312 age = 38
313
314 [nested]
315 omg = "bbq"
316 "#},
317 indoc! {r#"
318 name = "foo"
319 age = 38
320
321 [nested]
322 hi = "there"
323 omg = "bbq"
324 "#},
325 );
326 patch_and_compare(
327 indoc! {r#"
328 name = "foo"
329 age = 37
330
331 [config]
332 [[config.i2c.buses]]
333 i2c0 = "fine"
334
335 [config.spi]
336 spi1 = "great"
337 "#},
338 indoc! {r#"
339 [[config.i2c.buses]]
340 i2c4 = { status = "running" }
341 [config.pcie]
342 presence = false
343 "#},
344 indoc! {r#"
345 name = "foo"
346 age = 37
347
348 [config]
349 [[config.i2c.buses]]
350 i2c0 = "fine"
351 [[config.i2c.buses]]
352 i2c4 = { status = "running" }
353
354 [config.spi]
355 spi1 = "great"
356 [config.pcie]
357 presence = false
358 "#},
359 );
360 // Same as above, but swap the order in the patch
361 patch_and_compare(
362 indoc! {r#"
363 name = "foo"
364 age = 37
365
366 [config]
367 [[config.i2c.buses]]
368 i2c0 = "fine"
369
370 [config.spi]
371 spi1 = "great"
372 "#},
373 indoc! {r#"
374 bar = "foo"
375 [config.pcie]
376 presence = false
377 [[config.i2c.buses]]
378 i2c4 = { status = "running" }
379 "#},
380 indoc! {r#"
381 name = "foo"
382 age = 37
383 bar = "foo"
384
385 [config]
386 [[config.i2c.buses]]
387 i2c0 = "fine"
388 [[config.i2c.buses]]
389 i2c4 = { status = "running" }
390
391 [config.spi]
392 spi1 = "great"
393 [config.pcie]
394 presence = false
395 "#},
396 );
397 patch_and_compare(
398 indoc! {r#"
399 name = "foo"
400 age = 37
401
402 [block]
403 great = true
404
405 [config]
406 [[config.i2c.buses]]
407 i2c0 = "fine"
408
409 [config.spi]
410 spi1 = "great"
411 "#},
412 indoc! {r#"
413 bar = "foo"
414 [config.pcie]
415 presence = false
416 [[config.i2c.buses]]
417 i2c4 = { status = "running" }
418 "#},
419 indoc! {r#"
420 name = "foo"
421 age = 37
422 bar = "foo"
423
424 [block]
425 great = true
426
427 [config]
428 [[config.i2c.buses]]
429 i2c0 = "fine"
430 [[config.i2c.buses]]
431 i2c4 = { status = "running" }
432
433 [config.spi]
434 spi1 = "great"
435 [config.pcie]
436 presence = false
437 "#},
438 );
439 patch_and_compare(
440 indoc! {r#"
441 name = "foo"
442
443 [tasks.jefe]
444 features = ["hello", "world"]
445 great = true
446
447 [config]
448 [[config.i2c.buses]]
449 i2c0 = "fine"
450
451 [config.spi]
452 spi1 = "great"
453 "#},
454 indoc! {r#"
455 tasks.jefe.features = ["aaaaahhhh!"]
456 [config.pcie]
457 presence = false
458 [[config.i2c.buses]]
459 i2c4 = { status = "running" }
460 "#},
461 indoc! {r#"
462 name = "foo"
463
464 [tasks.jefe]
465 features = ["hello", "world","aaaaahhhh!"]
466 great = true
467
468 [config]
469 [[config.i2c.buses]]
470 i2c0 = "fine"
471 [[config.i2c.buses]]
472 i2c4 = { status = "running" }
473
474 [config.spi]
475 spi1 = "great"
476 [config.pcie]
477 presence = false
478 "#},
479 );
480 }
481}