1use indexmap::IndexMap;
5use std::{
6 borrow::Cow,
7 io::{self, Write},
8 num::NonZeroUsize,
9};
10
11use crate::{
12 error::{self, Error, ErrorKind, EventKind},
13 stream::Writer,
14 Date, Integer, Uid,
15};
16
17pub struct BinaryWriter<W: Write> {
18 writer: PosWriter<W>,
19 events: Vec<Event>,
20 dictionary_key_events: Vec<usize>,
21 values: IndexMap<Value<'static>, ValueState>,
22 collection_stack: Vec<usize>,
24 num_objects: usize,
26}
27
28struct PosWriter<W: Write> {
29 writer: W,
30 pos: usize,
31}
32
33#[derive(Clone)]
34struct ObjectRef(NonZeroUsize);
35
36enum Event {
68 Collection(Collection),
69 Value(usize),
71 DictionaryKeys(usize),
73}
74
75struct Collection {
76 ty: CollectionType,
77 len: usize,
81 skip: usize,
83 object_ref: Option<ObjectRef>,
84}
85
86#[derive(Eq, PartialEq)]
87enum CollectionType {
88 Array,
89 Dictionary,
90}
91
92#[derive(Eq, Hash, PartialEq)]
93enum Value<'a> {
94 Boolean(bool),
95 Data(Cow<'a, [u8]>),
96 Date(Date),
97 Integer(Integer),
98 Real(u64),
100 String(Cow<'a, str>),
101 Uid(Uid),
102}
103
104enum ValueState {
105 Unassigned,
107 Unwritten(ObjectRef),
109 Written(ObjectRef),
111}
112
113impl<W: Write> BinaryWriter<W> {
114 pub fn new(writer: W) -> BinaryWriter<W> {
115 BinaryWriter {
116 writer: PosWriter { writer, pos: 0 },
117 events: Vec::new(),
118 dictionary_key_events: Vec::new(),
119 values: IndexMap::new(),
120 collection_stack: Vec::new(),
121 num_objects: 0,
122 }
123 }
124
125 fn write_start_collection(&mut self, ty: CollectionType) -> Result<(), Error> {
126 if self.expecting_dictionary_key() {
127 let ty_event_kind = match ty {
128 CollectionType::Array => EventKind::StartArray,
129 CollectionType::Dictionary => EventKind::StartDictionary,
130 };
131 return Err(ErrorKind::UnexpectedEventType {
132 expected: EventKind::DictionaryKeyOrEndCollection,
133 found: ty_event_kind,
134 }
135 .without_position());
136 }
137 self.increment_current_collection_len();
138 self.collection_stack.push(self.events.len());
139 self.events.push(Event::Collection(Collection {
140 ty,
141 len: 0,
142 skip: 0,
143 object_ref: None,
144 }));
145 self.num_objects += 1;
146 Ok(())
147 }
148
149 fn write_end_collection(&mut self) -> Result<(), Error> {
150 let collection_event_index = self.collection_stack.pop().ok_or_else(|| {
151 ErrorKind::UnexpectedEventType {
152 expected: EventKind::ValueOrStartCollection,
153 found: EventKind::EndCollection,
154 }
155 .without_position()
156 })?;
157
158 let current_event_index = self.events.len() - 1;
159 let c = if let Event::Collection(c) = &mut self.events[collection_event_index] {
160 c
161 } else {
162 unreachable!("items in `collection_stack` always point to a collection event");
163 };
164
165 c.skip = current_event_index - collection_event_index;
166
167 if let CollectionType::Dictionary = c.ty {
168 if !is_even(c.len) {
170 return Err(ErrorKind::UnexpectedEventType {
171 expected: EventKind::DictionaryKeyOrEndCollection,
172 found: EventKind::EndCollection,
173 }
174 .without_position());
175 }
176
177 c.len /= 2;
180
181 c.skip += 1 + c.len;
184 let len = c.len;
185 self.events.push(Event::DictionaryKeys(len));
186
187 let keys_start_index = self.dictionary_key_events.len() - len;
189 self.events.extend(
190 self.dictionary_key_events
191 .drain(keys_start_index..)
192 .map(Event::Value),
193 );
194 }
195
196 if self.collection_stack.is_empty() {
197 self.write_plist()?;
198 }
199
200 Ok(())
201 }
202
203 fn write_value(&mut self, value: Value) -> Result<(), Error> {
204 let expecting_dictionary_key = self.expecting_dictionary_key();
205
206 match (&value, expecting_dictionary_key) {
208 (Value::String(_), true) | (_, false) => (),
209 (_, true) => {
210 return Err(ErrorKind::UnexpectedEventType {
211 expected: EventKind::DictionaryKeyOrEndCollection,
212 found: value.event_kind(),
213 }
214 .without_position())
215 }
216 }
217
218 let value_index = if let Some((value_index, _, _)) = self.values.get_full(&value) {
221 value_index
222 } else {
223 self.num_objects += 1;
224 let value = value.into_owned();
225 let (value_index, _) = self.values.insert_full(value, ValueState::Unassigned);
226 value_index
227 };
228
229 if expecting_dictionary_key {
232 self.dictionary_key_events.push(value_index);
233 } else {
234 self.events.push(Event::Value(value_index));
235 }
236
237 self.increment_current_collection_len();
238
239 if self.collection_stack.is_empty() {
240 self.write_plist()?;
241 }
242
243 Ok(())
244 }
245
246 fn expecting_dictionary_key(&self) -> bool {
247 if let Some(&event_index) = self.collection_stack.last() {
248 if let Event::Collection(c) = &self.events[event_index] {
249 c.ty == CollectionType::Dictionary && is_even(c.len)
250 } else {
251 unreachable!("items in `collection_stack` always point to a collection event");
252 }
253 } else {
254 false
255 }
256 }
257
258 fn increment_current_collection_len(&mut self) {
259 if let Some(&event_index) = self.collection_stack.last() {
260 if let Event::Collection(c) = &mut self.events[event_index] {
261 c.len += 1;
262 } else {
263 unreachable!("items in `collection_stack` always point to a collection event");
264 }
265 }
266 }
267
268 fn write_plist(&mut self) -> Result<(), Error> {
269 assert!(self.collection_stack.is_empty());
270
271 self.writer.write_exact(b"bplist00")?;
273
274 let mut events_vec = std::mem::take(&mut self.events);
276 let mut events = &mut events_vec[..];
277 let ref_size = plist_ref_size(self.num_objects - 1);
278 let mut offset_table = vec![0; self.num_objects];
279
280 let mut next_object_ref = ObjectRef::zero();
282 match &mut events[0] {
283 Event::Value(value_index) => {
284 let (_, value_state) = value_mut(&mut self.values, *value_index);
285 *value_state = ValueState::Unwritten(next_object_ref.clone_and_increment_self());
286 }
287 Event::Collection(c) => {
288 c.object_ref = Some(next_object_ref.clone_and_increment_self());
289 }
290 Event::DictionaryKeys(_) => {
291 unreachable!("`events` starts with a value or collection event")
292 }
293 }
294
295 while let Some((event, rest)) = events.split_first_mut() {
296 events = rest;
297 match event {
298 Event::Collection(c) => {
299 let collection_events = &mut events[..c.skip];
300 self.write_plist_collection(
301 c,
302 collection_events,
303 ref_size,
304 &mut next_object_ref,
305 &mut offset_table,
306 )?;
307 }
308 Event::Value(value_index) => {
309 self.write_plist_value(*value_index, &mut offset_table)?;
310 }
311 Event::DictionaryKeys(len) => {
314 events = &mut events[*len..];
315 }
316 }
317 }
318
319 let offset_table_offset = self.writer.pos;
321 let offset_size = plist_ref_size(offset_table_offset);
322 for &offset in &offset_table {
323 write_plist_ref(&mut self.writer, offset_size, offset)?;
324 }
325
326 let mut trailer = [0; 32];
334 trailer[6] = offset_size;
335 trailer[7] = ref_size;
336 trailer[8..16].copy_from_slice(&(self.num_objects as u64).to_be_bytes());
337 trailer[24..32].copy_from_slice(&(offset_table_offset as u64).to_be_bytes());
338 self.writer.write_exact(&trailer)?;
339
340 self.writer
341 .flush()
342 .map_err(error::from_io_without_position)?;
343
344 self.writer.pos = 0;
346 events_vec.clear();
347 self.events = events_vec;
348 self.values.clear();
349 self.num_objects = 0;
350
351 Ok(())
352 }
353
354 fn write_plist_collection(
355 &mut self,
356 collection: &Collection,
357 events: &mut [Event],
358 ref_size: u8,
359 next_object_ref: &mut ObjectRef,
360 offset_table: &mut [usize],
361 ) -> Result<(), Error> {
362 if let Some(object_ref) = &collection.object_ref {
363 offset_table[object_ref.value()] = self.writer.pos;
364 } else {
365 unreachable!("collection object refs are assigned before this function is called");
366 }
367
368 let (keys, values, ty) = match collection.ty {
372 CollectionType::Array => (&mut [][..], events, 0xa0),
373 CollectionType::Dictionary => {
374 let keys_start_offset = events.len() - collection.len - 1;
375 let (values, keys) = events.split_at_mut(keys_start_offset);
376 (&mut keys[1..], values, 0xd0)
377 }
378 };
379 let mut collection_events = keys.iter_mut().chain(values);
380
381 write_plist_value_ty_and_size(&mut self.writer, ty, collection.len)?;
385 while let Some(event) = collection_events.next() {
386 let object_ref = match event {
387 Event::Collection(c) => {
388 if c.skip > 0 {
391 let _ = collection_events.nth(c.skip - 1);
392 }
393
394 assert!(c.object_ref.is_none());
397 let object_ref = next_object_ref.clone_and_increment_self();
398 c.object_ref = Some(object_ref.clone());
399 object_ref
400 }
401 Event::Value(value_index) => {
402 let (_, value_state) = value_mut(&mut self.values, *value_index);
405 match value_state {
406 ValueState::Unassigned => {
407 let object_ref = next_object_ref.clone_and_increment_self();
408 *value_state = ValueState::Unwritten(object_ref.clone());
409 object_ref
410 }
411 ValueState::Unwritten(object_ref) | ValueState::Written(object_ref) => {
412 object_ref.clone()
413 }
414 }
415 }
416 Event::DictionaryKeys(_) => unreachable!(
417 "`DictionaryKeys` events are specifically excluded from the iterator"
418 ),
419 };
420 write_plist_ref(&mut self.writer, ref_size, object_ref.value())?;
421 }
422
423 for key in keys {
426 if let Event::Value(value_index) = key {
427 self.write_plist_value(*value_index, offset_table)?;
428 } else {
429 unreachable!("dictionary keys are assigned as values in `write_end_collection`");
430 }
431 }
432
433 Ok(())
434 }
435
436 fn write_plist_value(
437 &mut self,
438 value_index: usize,
439 offset_table: &mut [usize],
440 ) -> Result<(), Error> {
441 let (value, value_state) = value_mut(&mut self.values, value_index);
442
443 let object_ref = match value_state {
444 ValueState::Unassigned => {
445 unreachable!("value object refs are assigned before this function is called");
446 }
447 ValueState::Unwritten(object_ref) => object_ref.clone(),
448 ValueState::Written(_) => return Ok(()),
449 };
450
451 offset_table[object_ref.value()] = self.writer.pos;
452 *value_state = ValueState::Written(object_ref);
453
454 match value {
455 Value::Boolean(true) => {
456 self.writer.write_exact(&[0x09])?;
457 }
458 Value::Boolean(false) => {
459 self.writer.write_exact(&[0x08])?;
460 }
461 Value::Data(v) => {
462 write_plist_value_ty_and_size(&mut self.writer, 0x40, v.len())?;
463 self.writer.write_exact(&v[..])?;
464 }
465 Value::Date(v) => {
466 let secs = v.as_seconds_since_plist_epoch();
467 let mut buf: [_; 9] = [0x33, 0, 0, 0, 0, 0, 0, 0, 0];
468 buf[1..].copy_from_slice(&secs.to_bits().to_be_bytes());
469 self.writer.write_exact(&buf)?;
470 }
471 Value::Integer(v) => {
472 if let Some(v) = v.as_signed() {
473 if v >= 0 && v <= i64::from(u8::max_value()) {
474 self.writer.write_exact(&[0x10, v as u8])?;
475 } else if v >= 0 && v <= i64::from(u16::max_value()) {
476 let mut buf: [_; 3] = [0x11, 0, 0];
477 buf[1..].copy_from_slice(&(v as u16).to_be_bytes());
478 self.writer.write_exact(&buf)?;
479 } else if v >= 0 && v <= i64::from(u32::max_value()) {
480 let mut buf: [_; 5] = [0x12, 0, 0, 0, 0];
481 buf[1..].copy_from_slice(&(v as u32).to_be_bytes());
482 self.writer.write_exact(&buf)?;
483 } else {
484 let mut buf: [_; 9] = [0x13, 0, 0, 0, 0, 0, 0, 0, 0];
485 buf[1..].copy_from_slice(&v.to_be_bytes());
486 self.writer.write_exact(&buf)?;
487 }
488 } else if let Some(v) = v.as_unsigned() {
489 let mut buf: [_; 17] = [0x14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
492 buf[1..].copy_from_slice(&i128::from(v).to_be_bytes());
493 self.writer.write_exact(&buf)?;
494 } else {
495 unreachable!("an integer can be represented as either an i64 or u64");
496 }
497 }
498 Value::Real(v) => {
499 let mut buf: [_; 9] = [0x23, 0, 0, 0, 0, 0, 0, 0, 0];
500 buf[1..].copy_from_slice(&v.to_be_bytes());
501 self.writer.write_exact(&buf)?;
502 }
503 Value::String(v) if v.is_ascii() => {
504 let ascii = v.as_bytes();
505 write_plist_value_ty_and_size(&mut self.writer, 0x50, ascii.len())?;
506 self.writer.write_exact(ascii)?;
507 }
508 Value::String(v) => {
509 let utf16_len = v.encode_utf16().count();
510 write_plist_value_ty_and_size(&mut self.writer, 0x60, utf16_len)?;
511 for c in v.encode_utf16() {
512 self.writer.write_exact(&c.to_be_bytes())?;
513 }
514 }
515 Value::Uid(v) => {
516 let v = v.get();
517 if v <= u64::from(u8::max_value()) {
518 self.writer.write_exact(&[0x80, v as u8])?;
519 } else if v <= u64::from(u16::max_value()) {
520 let mut buf: [_; 3] = [0x81, 0, 0];
521 buf[1..].copy_from_slice(&(v as u16).to_be_bytes());
522 self.writer.write_exact(&buf)?;
523 } else if v <= u64::from(u32::max_value()) {
524 let mut buf: [_; 5] = [0x83, 0, 0, 0, 0];
525 buf[1..].copy_from_slice(&(v as u32).to_be_bytes());
526 self.writer.write_exact(&buf)?;
527 } else {
528 let mut buf: [_; 9] = [0x87, 0, 0, 0, 0, 0, 0, 0, 0];
529 #[allow(clippy::unnecessary_cast)]
531 buf[1..].copy_from_slice(&(v as u64).to_be_bytes());
532 self.writer.write_exact(&buf)?;
533 }
534 }
535 }
536 Ok(())
537 }
538}
539
540impl<W: Write> Writer for BinaryWriter<W> {
541 fn write_start_array(&mut self, _len: Option<u64>) -> Result<(), Error> {
542 self.write_start_collection(CollectionType::Array)
543 }
544 fn write_start_dictionary(&mut self, _len: Option<u64>) -> Result<(), Error> {
545 self.write_start_collection(CollectionType::Dictionary)
546 }
547 fn write_end_collection(&mut self) -> Result<(), Error> {
548 self.write_end_collection()
549 }
550
551 fn write_boolean(&mut self, value: bool) -> Result<(), Error> {
552 self.write_value(Value::Boolean(value))
553 }
554 fn write_data(&mut self, value: Cow<[u8]>) -> Result<(), Error> {
555 self.write_value(Value::Data(value))
556 }
557 fn write_date(&mut self, value: Date) -> Result<(), Error> {
558 self.write_value(Value::Date(value))
559 }
560 fn write_integer(&mut self, value: Integer) -> Result<(), Error> {
561 self.write_value(Value::Integer(value))
562 }
563 fn write_real(&mut self, value: f64) -> Result<(), Error> {
564 self.write_value(Value::Real(value.to_bits()))
565 }
566 fn write_string(&mut self, value: Cow<str>) -> Result<(), Error> {
567 self.write_value(Value::String(value))
568 }
569 fn write_uid(&mut self, value: Uid) -> Result<(), Error> {
570 self.write_value(Value::Uid(value))
571 }
572}
573
574fn is_even(value: usize) -> bool {
575 value & 1 == 0
576}
577
578fn value_mut<'a>(
579 values: &'a mut IndexMap<Value<'static>, ValueState>,
580 value_index: usize,
581) -> (&'a Value<'static>, &'a mut ValueState) {
582 values
583 .get_index_mut(value_index)
584 .expect("internal consistency error")
585}
586
587fn write_plist_value_ty_and_size(
588 writer: &mut PosWriter<impl Write>,
589 token: u8,
590 size: usize,
591) -> Result<(), Error> {
592 if size < 0x0f {
593 writer.write_exact(&[token | (size as u8)])?;
594 } else if size <= u8::max_value() as usize {
595 writer.write_exact(&[token | 0x0f, 0x10, size as u8])?;
596 } else if size <= u16::max_value() as usize {
597 let mut buf: [_; 4] = [token | 0x0f, 0x11, 0, 0];
598 buf[2..].copy_from_slice(&(size as u16).to_be_bytes());
599 writer.write_exact(&buf)?;
600 } else if size <= u32::max_value() as usize {
601 let mut buf: [_; 6] = [token | 0x0f, 0x12, 0, 0, 0, 0];
602 buf[2..].copy_from_slice(&(size as u32).to_be_bytes());
603 writer.write_exact(&buf)?;
604 } else {
605 let mut buf: [_; 10] = [token | 0x0f, 0x13, 0, 0, 0, 0, 0, 0, 0, 0];
606 buf[2..].copy_from_slice(&(size as u64).to_be_bytes());
607 writer.write_exact(&buf)?;
608 }
609 Ok(())
610}
611
612fn plist_ref_size(max_value: usize) -> u8 {
613 let significant_bits = 64 - (max_value as u64).leading_zeros() as u8;
614 let significant_bytes = (significant_bits + 7) / 8;
616 significant_bytes.next_power_of_two()
618}
619
620fn write_plist_ref(
621 writer: &mut PosWriter<impl Write>,
622 ref_size: u8,
623 value: usize,
624) -> Result<(), Error> {
625 match ref_size {
626 1 => writer.write_exact(&[value as u8]),
627 2 => writer.write_exact(&(value as u16).to_be_bytes()),
628 4 => writer.write_exact(&(value as u32).to_be_bytes()),
629 8 => writer.write_exact(&(value as u64).to_be_bytes()),
630 _ => unreachable!("`ref_size` is a power of two less than or equal to 8"),
631 }
632}
633
634impl<W: Write> PosWriter<W> {
635 fn write_exact(&mut self, buf: &[u8]) -> Result<(), Error> {
636 self.write_all(buf)
637 .map_err(error::from_io_without_position)?;
638 Ok(())
639 }
640}
641
642impl<W: Write> Write for PosWriter<W> {
643 fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
644 let count = self.writer.write(buf)?;
645 self.pos = self
646 .pos
647 .checked_add(count)
648 .expect("binary plist cannot be larger than `usize::max_value()` bytes");
649 Ok(count)
650 }
651
652 fn flush(&mut self) -> io::Result<()> {
653 self.writer.flush()
654 }
655}
656
657impl ObjectRef {
658 fn zero() -> ObjectRef {
659 ObjectRef(NonZeroUsize::new(1).unwrap())
660 }
661
662 fn clone_and_increment_self(&mut self) -> ObjectRef {
663 let current = self.0;
664 self.0 = NonZeroUsize::new(current.get() + 1).unwrap();
665 ObjectRef(current)
666 }
667
668 fn value(&self) -> usize {
669 self.0.get() - 1
670 }
671}
672
673impl<'a> Value<'a> {
674 fn into_owned(self) -> Value<'static> {
675 match self {
676 Value::Boolean(v) => Value::Boolean(v),
677 Value::Data(v) => Value::Data(Cow::Owned(v.into_owned())),
678 Value::Date(v) => Value::Date(v),
679 Value::Integer(v) => Value::Integer(v),
680 Value::Real(v) => Value::Real(v),
681 Value::String(v) => Value::String(Cow::Owned(v.into_owned())),
682 Value::Uid(v) => Value::Uid(v),
683 }
684 }
685
686 fn event_kind(&self) -> EventKind {
687 match self {
688 Value::Boolean(_) => EventKind::Boolean,
689 Value::Data(_) => EventKind::Data,
690 Value::Date(_) => EventKind::Date,
691 Value::Integer(_) => EventKind::Integer,
692 Value::Real(_) => EventKind::Real,
693 Value::String(_) => EventKind::String,
694 Value::Uid(_) => EventKind::Uid,
695 }
696 }
697}
698
699#[cfg(test)]
700mod tests {
701 use std::{fs::File, io::Cursor, path::Path};
702
703 use crate::{stream::BinaryReader, Value};
704
705 fn test_roundtrip<P: AsRef<Path>>(path: P) {
706 let reader = File::open(path).unwrap();
707 let streaming_parser = BinaryReader::new(reader);
708 let value_to_encode = Value::from_events(streaming_parser).unwrap();
709
710 let mut buf = Cursor::new(Vec::new());
711 value_to_encode.to_writer_binary(&mut buf).unwrap();
712
713 let buf_inner = buf.into_inner();
714
715 let streaming_parser = BinaryReader::new(Cursor::new(buf_inner));
716
717 let events: Vec<Result<_, _>> = streaming_parser.collect();
718 let value_decoded_from_encode = Value::from_events(events).unwrap();
719
720 assert_eq!(value_to_encode, value_decoded_from_encode);
721 }
722
723 #[test]
724 fn bplist_roundtrip() {
725 test_roundtrip("./tests/data/binary.plist")
726 }
727
728 #[test]
729 fn utf16_roundtrip() {
730 test_roundtrip("./tests/data/utf16_bplist.plist")
731 }
732
733 #[test]
734 fn nskeyedarchiver_roundtrip() {
735 test_roundtrip("./tests/data/binary_NSKeyedArchiver.plist")
736 }
737}