1use crate::{
2 Error, ExGuid, IdStream, Node, PropertySets, Reference, RevisionIndex, Value, bytes::Cursor,
3};
4use std::{
5 collections::{BTreeMap, BTreeSet},
6 sync::Arc,
7};
8
9type Result<T> = std::result::Result<T, Error>;
10type GlobalIds = BTreeMap<u32, [u8; 16]>;
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum ObjectData<'a> {
14 Properties(&'a [u8]),
15 Encrypted(&'a [u8]),
16 File {
17 reference: &'a [u8],
18 extension: &'a [u8],
19 },
20}
21
22#[derive(Debug, Clone)]
23pub struct Object<'a> {
24 pub jcid: u32,
25 pub reference_count: u32,
26 pub data: ObjectData<'a>,
27 pub global_ids: Arc<GlobalIds>,
28}
29
30#[derive(Debug, Clone)]
31pub struct ResolvedRevision<'a> {
32 pub roots: BTreeMap<u32, ExGuid>,
33 pub objects: BTreeMap<ExGuid, Object<'a>>,
34}
35
36/// Occurrences retain multiplicity for native reference counts.
37/// Each stream follows property arena order, including nested sets.
38#[derive(Debug, Default)]
39pub struct ObjectReferences {
40 pub objects: Vec<ExGuid>,
41 pub object_spaces: Vec<ExGuid>,
42 pub contexts: Vec<ExGuid>,
43}
44
45impl Object<'_> {
46 pub fn references(&self) -> Result<ObjectReferences> {
47 let mut result = ObjectReferences::default();
48 let bytes = match self.data {
49 ObjectData::File { .. } => return Ok(result),
50 ObjectData::Properties(bytes) => bytes,
51 ObjectData::Encrypted(_) => {
52 return Err(Error {
53 offset: 0,
54 message: "Encrypted property references are unavailable",
55 });
56 }
57 };
58 let properties = PropertySets::parse(bytes)?;
59 for property in properties.sets.iter().flatten() {
60 if let Value::References {
61 stream,
62 compact_ids,
63 } = property.value
64 {
65 let targets = match stream {
66 IdStream::Objects => &mut result.objects,
67 IdStream::ObjectSpaces => &mut result.object_spaces,
68 IdStream::Contexts => &mut result.contexts,
69 };
70 let mut c = Cursor {
71 bytes: compact_ids,
72 offset: 0,
73 };
74 while !c.bytes.is_empty() {
75 targets.push(c.compact(&self.global_ids)?);
76 }
77 }
78 }
79 Ok(result)
80 }
81}
82
83impl ResolvedRevision<'_> {
84 pub fn reachable(&self) -> Result<BTreeSet<ExGuid>> {
85 Ok(self.checked_counts()?.into_keys().collect())
86 }
87
88 /// Incoming reference counts of the reachable objects, which must equal those stored.
89 pub(crate) fn checked_counts(&self) -> Result<BTreeMap<ExGuid, u32>> {
90 let incoming = self.reference_counts()?;
91 for (id, count) in &incoming {
92 if self.objects[id].reference_count != *count {
93 return Err(Error {
94 offset: 0,
95 message: "Stored object reference count disagrees with the reachable graph",
96 });
97 }
98 }
99 Ok(incoming)
100 }
101
102 pub(crate) fn reference_counts(&self) -> Result<BTreeMap<ExGuid, u32>> {
103 let mut pending: Vec<_> = self.roots.values().copied().collect();
104 let mut incoming = BTreeMap::<ExGuid, u32>::new();
105 for id in &pending {
106 if incoming.insert(*id, 1).is_some() {
107 return Err(Error {
108 offset: 0,
109 message: "Object is the root of multiple roles",
110 });
111 }
112 }
113 let mut edges = BTreeMap::new();
114 while let Some(id) = pending.pop() {
115 if edges.contains_key(&id) {
116 continue;
117 }
118 let object = self.objects.get(&id).ok_or(Error {
119 offset: 0,
120 message: "Reachable object has no declaration",
121 })?;
122 let references = object.references()?;
123 for child in &references.objects {
124 let count = incoming.entry(*child).or_default();
125 *count = count.checked_add(1).ok_or(Error {
126 offset: 0,
127 message: "Object reference count overflows",
128 })?;
129 pending.push(*child);
130 }
131 edges.insert(id, references.objects);
132 }
133 let mut remaining = incoming.clone();
134 for id in self.roots.values() {
135 *remaining.get_mut(id).unwrap() -= 1;
136 }
137 pending.extend(
138 remaining
139 .iter()
140 .filter_map(|(id, count)| (*count == 0).then_some(*id)),
141 );
142 let mut visited = 0;
143 while let Some(id) = pending.pop() {
144 visited += 1;
145 for child in &edges[&id] {
146 let count = remaining.get_mut(child).unwrap();
147 *count -= 1;
148 if *count == 0 {
149 pending.push(*child);
150 }
151 }
152 }
153 if visited != edges.len() {
154 return Err(Error {
155 offset: 0,
156 message: "Object references form a cycle",
157 });
158 }
159 Ok(incoming)
160 }
161}
162
163impl Cursor<'_> {
164 pub(crate) fn compact(&mut self, table: &GlobalIds) -> Result<ExGuid> {
165 let raw = u32::from_le_bytes(self.read()?);
166 let guid = *table.get(&(raw >> 8)).ok_or(Error {
167 offset: self.offset - 4,
168 message: "Compact ID refers to a missing global ID",
169 })?;
170 Ok(ExGuid {
171 guid,
172 n: raw & 0xff,
173 })
174 }
175}
176
177impl<'a> Cursor<'a> {
178 fn storage_string(&mut self) -> Result<&'a [u8]> {
179 let count = u32::from_le_bytes(self.read()?);
180 let size = usize::try_from(count)
181 .ok()
182 .and_then(|n| n.checked_mul(2))
183 .ok_or(Error {
184 offset: self.offset - 4,
185 message: "String length exceeds address space",
186 })?;
187 self.take(size)
188 }
189}
190
191impl<'a> RevisionIndex<'a> {
192 pub fn validate_current(&self) -> Result<()> {
193 self.validate_with(|space, rid| self.resolve(space, rid))
194 }
195
196 /// `validate_current`, each revision read through `resolve`, as a protected section's
197 /// decoded.
198 pub(crate) fn validate_with<'r>(
199 &self,
200 resolve: impl Fn(ExGuid, ExGuid) -> Result<ResolvedRevision<'r>>,
201 ) -> Result<()> {
202 let mut edges = BTreeMap::new();
203 let mut incoming = BTreeMap::<_, usize>::new();
204 for (osid, space) in &self.spaces {
205 for rid in space.labels.values().copied().collect::<BTreeSet<_>>() {
206 let revision = resolve(*osid, rid)?;
207 let mut targets = BTreeSet::new();
208 for oid in revision.reachable()? {
209 let references = revision.objects[&oid].references()?;
210 for target in references.object_spaces {
211 if target == *osid {
212 return Err(Error {
213 offset: 0,
214 message: "Object references its own object space",
215 });
216 }
217 let rid = self.active(target)?;
218 targets.insert((target, rid));
219 }
220 for context in references.contexts {
221 // OneNote's copy of a page version names a history it never wrote.
222 if !space.labels.contains_key(&(context, 1))
223 && context != crate::section::HISTORY
224 {
225 return Err(Error {
226 offset: 0,
227 message: "Context reference has no current revision",
228 });
229 }
230 }
231 }
232 for target in &targets {
233 *incoming.entry(*target).or_default() += 1;
234 }
235 incoming.entry((*osid, rid)).or_default();
236 edges.insert((*osid, rid), targets);
237 }
238 }
239 let mut pending: Vec<_> = incoming
240 .iter()
241 .filter_map(|(id, count)| (*count == 0).then_some(*id))
242 .collect();
243 let mut visited = 0;
244 while let Some(id) = pending.pop() {
245 visited += 1;
246 for target in &edges[&id] {
247 let count = incoming.get_mut(target).unwrap();
248 *count -= 1;
249 if *count == 0 {
250 pending.push(*target);
251 }
252 }
253 }
254 if visited != edges.len() {
255 return Err(Error {
256 offset: 0,
257 message: "Object-space references form a cycle",
258 });
259 }
260 Ok(())
261 }
262
263 pub fn resolve(&self, space: ExGuid, revision: ExGuid) -> Result<ResolvedRevision<'a>> {
264 let space = self.spaces.get(&space).ok_or(Error {
265 offset: 0,
266 message: "Unknown object space",
267 })?;
268 let mut chain = Vec::new();
269 let mut visited = BTreeSet::new();
270 let mut next = Some(revision);
271 while let Some(id) = next {
272 let revision = space.revisions.get(&id).ok_or(Error {
273 offset: 0,
274 message: "Unknown revision dependency",
275 })?;
276 if !visited.insert(id) {
277 return Err(Error {
278 offset: 0,
279 message: "Revision dependency cycle",
280 });
281 }
282 chain.push(revision);
283 next = revision.dependency;
284 }
285 let mut result = ResolvedRevision {
286 roots: BTreeMap::new(),
287 objects: BTreeMap::new(),
288 };
289 let mut table = Arc::new(GlobalIds::new());
290 let mut signed_data = BTreeMap::new();
291 for revision in chain.into_iter().rev() {
292 let dependency_table = table;
293 table = Arc::new(GlobalIds::new());
294 let mut pending: Vec<&Node<'a>> = revision.nodes.iter().rev().collect();
295 let mut groups = BTreeSet::new();
296 let mut defining_table = false;
297 // Entries of the table being defined; the map is built once, at its end.
298 let mut defining: Vec<(u32, [u8; 16])> = Vec::new();
299 let initial_crc = if self.store.header.file_type == crate::FileType::Section {
300 u32::MAX
301 } else {
302 0
303 };
304 let mut override_crc = initial_crc;
305 let mut in_group = false;
306 let mut signature = ExGuid::default();
307 while let Some(node) = pending.pop() {
308 let mut c = node.fields(self.store);
309 match node.id {
310 0xb0 => {
311 override_crc = initial_crc;
312 in_group = true;
313 let id = c.exguid()?;
314 if !groups.insert(id) {
315 return Err(Error {
316 offset: node.offset,
317 message: "Repeated object group",
318 });
319 }
320 let group = node.referenced_list(self.store)?;
321 let first = group.first().ok_or(Error {
322 offset: node.offset,
323 message: "Empty object group",
324 })?;
325 if first.id != 0xb4
326 || first.fields(self.store).exguid()? != id
327 || group.last().is_none_or(|node| node.id != 0xb8)
328 {
329 return Err(Error {
330 offset: node.offset,
331 message: "Object-group identity or boundaries do not match",
332 });
333 }
334 if group[1..group.len() - 1].iter().any(|node| {
335 !matches!(
336 node.id,
337 0x22 | 0x24 | 0x28 | 0x8c | 0xa4 | 0xa5 | 0xc4 | 0xc5 | 0x72 | 0x73
338 )
339 }) {
340 return Err(Error {
341 offset: node.offset,
342 message: "Unexpected node in an object group",
343 });
344 }
345 pending.extend(group[1..].iter().rev());
346 }
347 0x21 | 0x22 => {
348 if defining_table {
349 return Err(Error {
350 offset: node.offset,
351 message: "Unterminated global identification table",
352 });
353 }
354 table = Arc::new(GlobalIds::new());
355 defining_table = true;
356 }
357 0x24..=0x26 => {
358 if !defining_table {
359 return Err(Error {
360 offset: node.offset,
361 message: "Global ID entry outside a table",
362 });
363 }
364 let first = u32::from_le_bytes(c.read()?);
365 let start = defining.len();
366 match node.id {
367 0x24 => defining.push((first, c.read()?)),
368 0x25 | 0x26 => {
369 let count = if node.id == 0x26 {
370 u32::from_le_bytes(c.read()?)
371 } else {
372 1
373 };
374 let to = u32::from_le_bytes(c.read()?);
375 let end = first.checked_add(count).ok_or(Error {
376 offset: node.offset,
377 message: "Global ID import range overflows",
378 })?;
379 if u64::from(count) > dependency_table.len() as u64
380 || to.checked_add(count).is_none_or(|end| end > 0xffffff)
381 {
382 return Err(Error {
383 offset: node.offset,
384 message: "Global ID import range exceeds its table",
385 });
386 }
387 defining.extend(
388 dependency_table
389 .range(first..end)
390 .map(|(from, guid)| (to + from - first, *guid)),
391 );
392 if (defining.len() - start) as u64 != u64::from(count) {
393 return Err(Error {
394 offset: node.offset,
395 message: "Global ID import refers to a missing entry",
396 });
397 }
398 }
399 _ => unreachable!(),
400 }
401 // More entries than indices repeats one; checked here so imports
402 // cannot grow the list without bound.
403 if defining.len() > 0xffffff
404 || defining[start..]
405 .iter()
406 .any(|(index, guid)| *index >= 0xffffff || *guid == [0; 16])
407 {
408 return Err(Error {
409 offset: node.offset,
410 message: "Invalid or repeated global ID entry",
411 });
412 }
413 }
414 0x28 => {
415 if !defining_table {
416 return Err(Error {
417 offset: node.offset,
418 message: "Global ID table end without a start",
419 });
420 }
421 defining_table = false;
422 defining.sort_unstable();
423 if defining.windows(2).any(|pair| pair[0].0 == pair[1].0) {
424 return Err(Error {
425 offset: node.offset,
426 message: "Invalid or repeated global ID entry",
427 });
428 }
429 defining.sort_unstable_by_key(|(_, guid)| *guid);
430 if defining.windows(2).any(|pair| pair[0].1 == pair[1].1) {
431 return Err(Error {
432 offset: node.offset,
433 message: "Global ID table repeats a GUID",
434 });
435 }
436 table = Arc::new(defining.drain(..).collect());
437 }
438 0x59 | 0x5a => {
439 let id = if node.id == 0x5a {
440 c.exguid()?
441 } else {
442 c.compact(&table)?
443 };
444 let role = u32::from_le_bytes(c.read()?);
445 result.roots.insert(role, id);
446 }
447 0x2d | 0x2e | 0x41 | 0x42 | 0xa4 | 0xa5 | 0xc4 | 0xc5 | 0x72 | 0x73 => {
448 if defining_table {
449 return Err(Error {
450 offset: node.offset,
451 message: "Object declared inside a global ID table",
452 });
453 }
454 let id = c.compact(&table)?;
455 let jcid = match node.id {
456 0x2d | 0x2e => {
457 let bits = u16::from_le_bytes(c.read()?);
458 c.take(4)?;
459 if bits & 0x3fff != 1 {
460 return Err(Error {
461 offset: node.offset,
462 message: "Invalid table-of-contents object type",
463 });
464 }
465 0x20001
466 }
467 0x41 | 0x42 => {
468 result
469 .objects
470 .get(&id)
471 .ok_or(Error {
472 offset: node.offset,
473 message: "Object revision has no previous declaration",
474 })?
475 .jcid
476 }
477 _ => u32::from_le_bytes(c.read()?),
478 };
479 let reference_count = match node.id {
480 0x41 => u32::from(c.read::<1>()?[0] >> 2),
481 0x42 => {
482 c.take(4)?;
483 u32::from_le_bytes(c.read()?)
484 }
485 0x2d | 0x72 => u32::from(c.read::<1>()?[0]),
486 0x2e | 0x73 => u32::from_le_bytes(c.read()?),
487 0xa4 | 0xc4 => {
488 c.take(1)?;
489 u32::from(c.read::<1>()?[0])
490 }
491 _ => {
492 c.take(1)?;
493 u32::from_le_bytes(c.read()?)
494 }
495 };
496 if in_group
497 || self.store.header.file_type == crate::FileType::TableOfContents
498 {
499 override_crc = crate::store::crc(
500 override_crc,
501 &reference_count.to_le_bytes(),
502 self.store.header.file_type,
503 );
504 }
505 let data = if matches!(node.id, 0x72 | 0x73) {
506 if jcid & 0x1fffff != 0x80000 | (jcid & 0xffff) {
507 return Err(Error {
508 offset: node.offset,
509 message: "Invalid file-data object flags",
510 });
511 }
512 ObjectData::File {
513 reference: c.storage_string()?,
514 extension: c.storage_string()?,
515 }
516 } else {
517 let Some(Reference::Data(chunk)) = node.reference else {
518 return Err(Error {
519 offset: node.offset,
520 message: "Object lacks a data reference",
521 });
522 };
523 let bytes = self.store.chunk_data(chunk)?;
524 if jcid & 0x20000 == 0
525 || (jcid & 0x100000 != 0) != matches!(node.id, 0xc4 | 0xc5)
526 {
527 return Err(Error {
528 offset: node.offset,
529 message: "Object declaration does not match its property-set flags",
530 });
531 }
532 if matches!(node.id, 0xc4 | 0xc5) {
533 let expected = c.read::<16>()?;
534 if !revision.encrypted && md5::compute(bytes).0 != expected {
535 return Err(Error {
536 offset: node.offset,
537 message: "Read-only object checksum mismatch",
538 });
539 }
540 }
541 if revision.encrypted {
542 ObjectData::Encrypted(bytes)
543 } else {
544 ObjectData::Properties(bytes)
545 }
546 };
547 if let Some(previous) = result.objects.get(&id) {
548 if previous.jcid & 0x1bffff != jcid & 0x1bffff {
549 return Err(Error {
550 offset: node.offset,
551 message: "Object revision changes its type",
552 });
553 }
554 if jcid & 0x180000 != 0 && previous.data != data {
555 return Err(Error {
556 offset: node.offset,
557 message: "Immutable object data changed",
558 });
559 }
560 }
561 if signature != ExGuid::default()
562 && signed_data
563 .insert((id, signature), data)
564 .is_some_and(|previous| previous != data)
565 {
566 return Err(Error {
567 offset: node.offset,
568 message: "Object data changed under the same data signature",
569 });
570 }
571 result.objects.insert(
572 id,
573 Object {
574 jcid,
575 reference_count,
576 data,
577 global_ids: Arc::clone(&table),
578 },
579 );
580 }
581 0x84 => {
582 let Some(Reference::Data(chunk)) = node.reference else {
583 return Err(Error {
584 offset: node.offset,
585 message: "Reference-count override lacks its data reference",
586 });
587 };
588 if !chunk.absent() {
589 c = Cursor {
590 bytes: self.store.chunk_data(chunk)?,
591 offset: usize::try_from(chunk.offset).unwrap(),
592 };
593 }
594 let small = u32::from_le_bytes(c.read()?);
595 let large = u32::from_le_bytes(c.read()?);
596 let expected = u32::from_le_bytes(c.read()?);
597 let start = c.bytes;
598 for (count, width) in [(small, 1), (large, 4)] {
599 for _ in 0..count {
600 let id = c.compact(&table)?;
601 let value = if width == 1 {
602 u32::from(c.read::<1>()?[0])
603 } else {
604 u32::from_le_bytes(c.read()?)
605 };
606 let object = result.objects.get_mut(&id).ok_or(Error { offset: node.offset, message: "Reference-count override targets an undeclared object" })?;
607 object.reference_count = value;
608 }
609 }
610 override_crc = crate::store::crc(
611 override_crc,
612 &start[..start.len() - c.bytes.len()],
613 self.store.header.file_type,
614 );
615 let actual = if self.store.header.file_type == crate::FileType::Section {
616 !override_crc
617 } else {
618 override_crc
619 };
620 if expected != actual {
621 return Err(Error {
622 offset: node.offset,
623 message: "Reference-count override checksum mismatch",
624 });
625 }
626 override_crc = initial_crc;
627 }
628 0x7c => {}
629 0x8c => {
630 signature = c.exguid()?;
631 }
632 0xb8 => {
633 in_group = false;
634 signature = ExGuid::default();
635 }
636 _ => {
637 return Err(Error {
638 offset: node.offset,
639 message: "Unsupported node in a revision manifest",
640 });
641 }
642 }
643 }
644 if defining_table {
645 return Err(Error {
646 offset: 0,
647 message: "Unterminated global identification table",
648 });
649 }
650 }
651 Ok(result)
652 }
653}