1use std::collections::BTreeMap;
23
24use crate::error::{Error, Result};
25use crate::index::{IndexBlob, IndexValue};
26use crate::schema::{AttributeFormat, RecordType, Relation, Schema};
27
28pub const SIGNATURE: &[u8; 4] = b"kych";
29
30pub const VERSION: u32 = 0x0001_0000;
32
33pub const HEADER_SIZE_FIELD: u32 = 16;
35
36pub const HEADER_LEN: usize = 20;
37pub const TABLE_HEADER_LEN: usize = 28;
38pub const RECORD_HEADER_LEN: usize = 24;
39
40const ATTRIBUTE_OFFSET_FLAG: u32 = 1;
42
43const SLOT_FREE_FLAG: u32 = 1;
48
49#[derive(Debug, Clone)]
51pub struct Keychain {
52 pub version: u32,
53 pub header_size: u32,
55 pub auth_offset: u32,
57 pub tables: Vec<Table>,
60 pub commit_version: Option<u32>,
66}
67
68#[derive(Debug, Clone)]
69pub struct Table {
70 pub record_type: RecordType,
71 pub free_list_head: u32,
80 pub slots: Vec<Slot>,
82 pub(crate) layout: Vec<usize>,
89 pub indexes: TableIndexes,
91}
92
93#[derive(Debug, Clone, PartialEq, Eq)]
95pub enum Slot {
96 Record(Record),
98 Free(u32),
101 Empty,
103}
104
105impl Slot {
106 pub fn record(&self) -> Option<&Record> {
107 match self {
108 Self::Record(record) => Some(record),
109 _ => None,
110 }
111 }
112
113 pub fn record_mut(&mut self) -> Option<&mut Record> {
114 match self {
115 Self::Record(record) => Some(record),
116 _ => None,
117 }
118 }
119
120 pub fn is_empty(&self) -> bool {
121 matches!(self, Self::Empty)
122 }
123}
124
125#[derive(Debug, Clone, PartialEq, Eq)]
127pub enum TableIndexes {
128 Parsed(IndexBlob),
129 Raw(Vec<u8>),
132}
133
134impl TableIndexes {
135 pub fn to_bytes(&self, table_offset: usize) -> Vec<u8> {
138 match self {
139 Self::Parsed(blob) => blob.to_bytes(table_offset),
140 Self::Raw(bytes) => bytes.clone(),
141 }
142 }
143
144 pub fn len(&self) -> usize {
145 match self {
146 Self::Parsed(blob) => blob.encoded_len(),
147 Self::Raw(bytes) => bytes.len(),
148 }
149 }
150
151 pub fn is_empty(&self) -> bool {
152 self.len() == 0
153 }
154
155 pub fn blob(&self) -> Option<&IndexBlob> {
156 match self {
157 Self::Parsed(blob) => Some(blob),
158 Self::Raw(_) => None,
159 }
160 }
161}
162
163#[derive(Debug, Clone, PartialEq, Eq)]
164pub struct Record {
165 pub number: u32,
167 pub version: u32,
172 pub unknown3: u32,
175 pub unknown5: u32,
177 pub key_data: Vec<u8>,
180 pub attributes: Vec<Option<Value>>,
183}
184
185#[derive(Debug, Clone, PartialEq, Eq)]
187pub enum Value {
188 String(Vec<u8>),
190 Sint32(i32),
191 Uint32(u32),
192 Date(Vec<u8>),
194 Blob(Vec<u8>),
197}
198
199impl Value {
200 pub fn as_bytes(&self) -> Option<&[u8]> {
201 match self {
202 Self::String(bytes) | Self::Blob(bytes) | Self::Date(bytes) => Some(bytes),
203 _ => None,
204 }
205 }
206
207 pub fn as_u32(&self) -> Option<u32> {
208 match self {
209 Self::Uint32(value) => Some(*value),
210 Self::Sint32(value) => Some(*value as u32),
211 _ => None,
212 }
213 }
214
215 pub fn to_display_string(&self) -> String {
217 match self {
218 Self::Sint32(value) => value.to_string(),
219 Self::Uint32(value) => value.to_string(),
220 Self::Date(bytes) | Self::String(bytes) | Self::Blob(bytes) => {
221 let trimmed = trim_nul(bytes);
222 match std::str::from_utf8(trimmed) {
223 Ok(text) if trimmed.iter().all(|b| !b.is_ascii_control()) => text.to_string(),
224 _ => format!("0x{}", hex::encode(trimmed)),
225 }
226 }
227 }
228 }
229
230 fn encoded_len(&self) -> usize {
231 match self {
232 Self::Sint32(_) | Self::Uint32(_) => 4,
233 Self::Date(_) => 16,
234 Self::String(bytes) | Self::Blob(bytes) => pad4(4 + bytes.len()),
235 }
236 }
237
238 fn write(&self, out: &mut Vec<u8>) {
239 match self {
240 Self::Sint32(value) => out.extend_from_slice(&value.to_be_bytes()),
241 Self::Uint32(value) => out.extend_from_slice(&value.to_be_bytes()),
242 Self::Date(bytes) => {
243 let mut field = [0u8; 16];
244 let take = bytes.len().min(16);
245 field[..take].copy_from_slice(&bytes[..take]);
246 out.extend_from_slice(&field);
247 }
248 Self::String(bytes) | Self::Blob(bytes) => {
249 out.extend_from_slice(&(bytes.len() as u32).to_be_bytes());
250 out.extend_from_slice(bytes);
251 out.resize(pad4(out.len()), 0);
252 }
253 }
254 }
255}
256
257pub fn trim_nul(bytes: &[u8]) -> &[u8] {
258 match bytes.iter().position(|b| *b == 0) {
259 Some(end) => &bytes[..end],
260 None => bytes,
261 }
262}
263
264fn pad4(len: usize) -> usize {
265 (len + 3) & !3
266}
267
268struct Cursor<'a> {
274 data: &'a [u8],
275}
276
277impl<'a> Cursor<'a> {
278 fn u32(&self, at: usize) -> Result<u32> {
279 let end = at.checked_add(4).ok_or_else(|| Error::truncated(at, 4))?;
280 let bytes = self
281 .data
282 .get(at..end)
283 .ok_or_else(|| Error::truncated(at, 4))?;
284 Ok(u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]))
285 }
286
287 fn bytes(&self, at: usize, len: usize) -> Result<&'a [u8]> {
288 let end = at
289 .checked_add(len)
290 .ok_or_else(|| Error::truncated(at, len))?;
291 self.data
292 .get(at..end)
293 .ok_or_else(|| Error::truncated(at, len))
294 }
295}
296
297impl Keychain {
298 pub fn parse(data: &[u8]) -> Result<Self> {
300 let cursor = Cursor { data };
301
302 if data.len() < HEADER_LEN {
303 return Err(Error::truncated(0, HEADER_LEN));
304 }
305 if &data[..4] != SIGNATURE {
306 return Err(Error::NotAKeychain);
307 }
308
309 let version = cursor.u32(4)?;
310 let header_size = cursor.u32(8)?;
311 let tables_offset = cursor.u32(12)? as usize;
312 let auth_offset = cursor.u32(16)?;
313
314 let tables_size = cursor.u32(tables_offset)? as usize;
318 let commit_version = cursor.u32(tables_offset + tables_size).ok();
319
320 let table_count = cursor.u32(tables_offset + 4)? as usize;
321 let mut table_offsets = Vec::with_capacity(table_count);
322 for index in 0..table_count {
323 table_offsets.push(cursor.u32(tables_offset + 8 + index * 4)? as usize);
324 }
325
326 let bootstrap = Schema::bootstrap();
331 let mut schema_tables = Vec::new();
332 for offset in &table_offsets {
333 let at = tables_offset + offset;
334 let record_type = RecordType(cursor.u32(at + 4)?);
335 if bootstrap.relation(record_type).is_some() {
336 schema_tables.push(Table::parse(&cursor, at, &bootstrap)?);
337 }
338 }
339 let schema = Schema::from_tables(&schema_tables)?;
340
341 let mut tables = Vec::with_capacity(table_count);
342 for offset in &table_offsets {
343 tables.push(Table::parse(&cursor, tables_offset + offset, &schema)?);
344 }
345
346 Ok(Self {
347 version,
348 header_size,
349 auth_offset,
350 tables,
351 commit_version,
352 })
353 }
354
355 pub fn schema(&self) -> Result<Schema> {
357 Schema::from_tables(&self.tables)
358 }
359
360 pub fn bump_commit_version(&mut self) {
362 self.commit_version = Some(self.commit_version.unwrap_or(0) + 1);
363 }
364
365 pub fn table(&self, record_type: RecordType) -> Option<&Table> {
366 self.tables
367 .iter()
368 .find(|table| table.record_type == record_type)
369 }
370
371 pub fn table_mut(&mut self, record_type: RecordType) -> Option<&mut Table> {
372 self.tables
373 .iter_mut()
374 .find(|table| table.record_type == record_type)
375 }
376
377 pub fn to_bytes(&self) -> Result<Vec<u8>> {
379 let mut tables = Vec::with_capacity(self.tables.len());
380 for table in &self.tables {
381 tables.push(table.to_bytes()?);
382 }
383
384 let array_header = 8 + 4 * tables.len();
386 let mut offsets = Vec::with_capacity(tables.len());
387 let mut running = array_header;
388 for table in &tables {
389 offsets.push(running as u32);
390 running += table.len();
391 }
392
393 let mut out = Vec::with_capacity(HEADER_LEN + running);
394 out.extend_from_slice(SIGNATURE);
395 out.extend_from_slice(&self.version.to_be_bytes());
396 out.extend_from_slice(&self.header_size.to_be_bytes());
397 out.extend_from_slice(&(HEADER_LEN as u32).to_be_bytes());
398 out.extend_from_slice(&self.auth_offset.to_be_bytes());
399
400 out.extend_from_slice(&(running as u32).to_be_bytes());
401 out.extend_from_slice(&(tables.len() as u32).to_be_bytes());
402 for offset in offsets {
403 out.extend_from_slice(&offset.to_be_bytes());
404 }
405 for table in tables {
406 out.extend_from_slice(&table);
407 }
408 if let Some(commit_version) = self.commit_version {
409 out.extend_from_slice(&commit_version.to_be_bytes());
410 }
411 Ok(out)
412 }
413}
414
415impl Table {
416 fn parse(cursor: &Cursor<'_>, at: usize, schema: &Schema) -> Result<Self> {
417 let _size = cursor.u32(at)?;
418 let record_type = RecordType(cursor.u32(at + 4)?);
419 let _record_count = cursor.u32(at + 8)?;
420 let _records_offset = cursor.u32(at + 12)?;
421 let indexes_offset = cursor.u32(at + 16)? as usize;
422 let free_list_head = cursor.u32(at + 20)?;
423 let slot_count = cursor.u32(at + 24)? as usize;
424 if slot_count > 1 << 20 {
425 return Err(Error::format(format!(
426 "table 0x{:08x} claims {slot_count} record slots",
427 record_type.0
428 )));
429 }
430
431 let mut slots = Vec::with_capacity(slot_count);
432 let mut layout: Vec<(usize, usize)> = Vec::new();
433 for index in 0..slot_count {
434 let offset = cursor.u32(at + TABLE_HEADER_LEN + index * 4)?;
435 if offset == 0 {
436 slots.push(Slot::Empty);
437 continue;
438 }
439 if offset & SLOT_FREE_FLAG != 0 {
440 slots.push(Slot::Free(offset));
441 continue;
442 }
443 layout.push((offset as usize, index));
444 let offset = offset as usize;
445 if offset < TABLE_HEADER_LEN || offset >= indexes_offset {
446 return Err(Error::format(format!(
447 "table 0x{:08x} slot {index} points to {offset}, outside its records",
448 record_type.0
449 )));
450 }
451 slots.push(Slot::Record(Record::parse(
452 cursor,
453 at + offset,
454 record_type,
455 schema,
456 )?));
457 }
458
459 let size = _size as usize;
460 if indexes_offset > size {
461 return Err(Error::format(format!(
462 "table 0x{:08x} index offset {indexes_offset} is past its {size}-byte extent",
463 record_type.0
464 )));
465 }
466 let index_data = cursor.bytes(at + indexes_offset, size - indexes_offset)?;
467
468 let relation = schema.relation(record_type);
471 let indexes = match IndexBlob::parse(index_data, indexes_offset, relation) {
472 Ok(blob) if blob.to_bytes(indexes_offset) == index_data => TableIndexes::Parsed(blob),
473 _ => TableIndexes::Raw(index_data.to_vec()),
474 };
475
476 layout.sort_unstable();
479
480 Ok(Self {
481 record_type,
482 free_list_head,
483 slots,
484 layout: layout.into_iter().map(|(_, index)| index).collect(),
485 indexes,
486 })
487 }
488
489 fn free_link(index: usize) -> u32 {
494 (TABLE_HEADER_LEN + 4 * index) as u32 | SLOT_FREE_FLAG
495 }
496
497 fn rebuild_free_list(&mut self) {
505 let mut head = 0u32;
506 for index in 0..self.slots.len() {
507 if self.slots[index].record().is_some() {
508 continue;
509 }
510 self.slots[index] = if head == 0 {
511 Slot::Empty
512 } else {
513 Slot::Free(head)
514 };
515 head = Self::free_link(index);
516 }
517 self.free_list_head = head;
518 }
519
520 fn free_head(&self) -> Option<usize> {
522 (0..self.slots.len())
523 .rev()
524 .find(|index| self.slots[*index].record().is_none())
525 }
526
527 pub fn records(&self) -> impl Iterator<Item = &Record> {
529 self.slots.iter().filter_map(Slot::record)
530 }
531
532 pub fn records_mut(&mut self) -> impl Iterator<Item = &mut Record> {
533 self.slots.iter_mut().filter_map(Slot::record_mut)
534 }
535
536 pub fn record_count(&self) -> usize {
537 self.records().count()
538 }
539
540 pub fn next_record_number(&self) -> u32 {
542 self.records()
543 .map(|record| record.number)
544 .max()
545 .map_or(0, |max| max + 1)
546 }
547
548 pub fn insert(&mut self, mut record: Record) -> u32 {
555 let index = match self.free_head() {
556 Some(index) => index,
557 None => {
558 self.slots.push(Slot::Empty);
559 self.slots.len() - 1
560 }
561 };
562 record.number = index as u32;
563 self.slots[index] = Slot::Record(record);
564 self.layout.push(index);
565 self.rebuild_free_list();
566 index as u32
567 }
568
569 pub fn delete(&mut self, number: u32) -> bool {
579 let Some(position) = self
580 .slots
581 .iter()
582 .position(|slot| slot.record().is_some_and(|record| record.number == number))
583 else {
584 return false;
585 };
586
587 self.slots[position] = Slot::Empty;
588 self.layout.retain(|index| *index != position);
589 if position + 1 == self.slots.len() && self.slots.len() > 1 {
590 self.slots.pop();
591 }
592 self.rebuild_free_list();
593
594 if let TableIndexes::Parsed(blob) = &mut self.indexes {
595 blob.remove_record(number);
596 }
597 true
598 }
599
600 pub fn unique_index_attribute_ids(&self) -> Option<&[u32]> {
605 self.indexes
606 .blob()?
607 .indexes
608 .iter()
609 .find(|index| index.kind == 1)
610 .map(|index| index.attribute_ids.as_slice())
611 }
612
613 pub fn has_record_with_unique_key(
622 &self,
623 relation: &Relation,
624 attributes: &[Option<Value>],
625 ) -> bool {
626 let Some(blob) = self.indexes.blob() else {
627 return false;
628 };
629 let Some(unique) = blob.indexes.iter().find(|index| index.kind == 1) else {
630 return false;
631 };
632 let positions: Vec<usize> = unique
635 .attribute_ids
636 .iter()
637 .filter_map(|id| {
638 relation
639 .attributes
640 .iter()
641 .position(|attribute| attribute.id == *id)
642 })
643 .collect();
644 if positions.len() != unique.attribute_ids.len() {
645 return false;
646 }
647
648 let key_of = |values: &[Option<Value>]| -> Vec<Option<Value>> {
649 positions
650 .iter()
651 .map(|position| values.get(*position).cloned().flatten())
652 .collect()
653 };
654 let wanted = key_of(attributes);
655 self.records()
656 .any(|record| key_of(&record.attributes) == wanted)
657 }
658
659 pub fn rebuild_indexes(&mut self, relation: &Relation) -> Result<()> {
665 let TableIndexes::Parsed(blob) = &mut self.indexes else {
666 return Err(Error::format(format!(
667 "table 0x{:08x} has an index region this build cannot rewrite",
668 self.record_type.0
669 )));
670 };
671
672 let positions: Vec<(u32, usize, AttributeFormat)> = relation
674 .attributes
675 .iter()
676 .enumerate()
677 .map(|(position, attribute)| (attribute.id, position, attribute.format))
678 .collect();
679
680 for index in &mut blob.indexes {
681 index.entries.clear();
682 }
683 for record in self.slots.iter().filter_map(Slot::record) {
684 let position_of = |attribute_id: u32| -> Option<usize> {
685 positions
686 .iter()
687 .find(|(id, _, _)| *id == attribute_id)
688 .map(|(_, position, _)| *position)
689 };
690 let key = |attribute_id: u32| -> IndexValue {
691 match positions.iter().find(|(id, _, _)| *id == attribute_id) {
692 Some((_, position, format)) => {
693 IndexValue::from_value(record.attribute(*position), *format)
694 }
695 None => IndexValue::Bytes(Vec::new()),
696 }
697 };
698 blob.insert_record_where(record.number, key, |attribute_ids: &[u32]| -> bool {
701 attribute_ids.iter().all(|id| {
702 position_of(*id).is_some_and(|position| record.attribute(position).is_some())
703 })
704 });
705 }
706 Ok(())
707 }
708
709 fn to_bytes(&self) -> Result<Vec<u8>> {
710 let records_offset = TABLE_HEADER_LEN + 4 * self.slots.len();
711 let mut slot_offsets = vec![0u32; self.slots.len()];
712 for (index, slot) in self.slots.iter().enumerate() {
713 if let Slot::Free(link) = slot {
714 slot_offsets[index] = *link;
715 }
716 }
717
718 let mut order: Vec<usize> = self
722 .layout
723 .iter()
724 .copied()
725 .filter(|index| {
726 self.slots
727 .get(*index)
728 .is_some_and(|slot| slot.record().is_some())
729 })
730 .collect();
731 for (index, slot) in self.slots.iter().enumerate() {
732 if slot.record().is_some() && !order.contains(&index) {
733 order.push(index);
734 }
735 }
736
737 let mut bodies = Vec::with_capacity(order.len());
738 let mut running = records_offset;
739 for index in &order {
740 let Some(Slot::Record(record)) = self.slots.get(*index) else {
741 continue;
742 };
743 let bytes = record.to_bytes()?;
744 slot_offsets[*index] = running as u32;
745 running += bytes.len();
746 bodies.push(bytes);
747 }
748 let records: Vec<Option<Vec<u8>>> = bodies.into_iter().map(Some).collect();
749 let indexes_offset = running;
750 let index_data = self.indexes.to_bytes(indexes_offset);
751 let size = indexes_offset + index_data.len();
752
753 let mut out = Vec::with_capacity(size);
754 out.extend_from_slice(&(size as u32).to_be_bytes());
755 out.extend_from_slice(&self.record_type.0.to_be_bytes());
756 out.extend_from_slice(&(self.record_count() as u32).to_be_bytes());
757 out.extend_from_slice(&(records_offset as u32).to_be_bytes());
758 out.extend_from_slice(&(indexes_offset as u32).to_be_bytes());
759 out.extend_from_slice(&self.free_list_head.to_be_bytes());
760 out.extend_from_slice(&(self.slots.len() as u32).to_be_bytes());
761 for offset in slot_offsets {
762 out.extend_from_slice(&offset.to_be_bytes());
763 }
764 for record in records.into_iter().flatten() {
765 out.extend_from_slice(&record);
766 }
767 out.extend_from_slice(&index_data);
768 Ok(out)
769 }
770}
771
772impl Record {
773 fn parse(
774 cursor: &Cursor<'_>,
775 at: usize,
776 record_type: RecordType,
777 schema: &Schema,
778 ) -> Result<Self> {
779 let size = cursor.u32(at)? as usize;
780 let number = cursor.u32(at + 4)?;
781 let version = cursor.u32(at + 8)?;
782 let unknown3 = cursor.u32(at + 12)?;
783 let key_data_size = cursor.u32(at + 16)? as usize;
784 let unknown5 = cursor.u32(at + 20)?;
785
786 let formats = schema.attribute_formats(record_type);
787 let mut attributes = Vec::with_capacity(formats.len());
788 let mut offsets = Vec::with_capacity(formats.len());
789 for index in 0..formats.len() {
790 offsets.push(cursor.u32(at + RECORD_HEADER_LEN + index * 4)?);
791 }
792
793 let key_data_at = at + RECORD_HEADER_LEN + 4 * formats.len();
794 let key_data = cursor.bytes(key_data_at, key_data_size)?.to_vec();
795
796 for (offset, format) in offsets.iter().zip(&formats) {
797 if *offset == 0 {
798 attributes.push(None);
799 continue;
800 }
801 let value_at = at + (*offset & !ATTRIBUTE_OFFSET_FLAG) as usize;
802 if value_at >= at + size {
803 return Err(Error::format(format!(
804 "record {number} in table 0x{:08x} points an attribute past its extent",
805 record_type.0
806 )));
807 }
808 attributes.push(Some(read_value(cursor, value_at, *format)?));
809 }
810
811 Ok(Self {
812 number,
813 version,
814 unknown3,
815 unknown5,
816 key_data,
817 attributes,
818 })
819 }
820
821 pub fn attribute(&self, index: usize) -> Option<&Value> {
822 self.attributes.get(index).and_then(Option::as_ref)
823 }
824
825 pub fn set_attribute(&mut self, index: usize, value: Option<Value>) {
830 if let Some(slot) = self.attributes.get_mut(index) {
831 *slot = value;
832 }
833 }
834
835 fn to_bytes(&self) -> Result<Vec<u8>> {
836 let count = self.attributes.len();
837 let header_and_offsets = RECORD_HEADER_LEN + 4 * count;
838 let key_data_len = pad4(self.key_data.len());
839
840 let mut offsets = Vec::with_capacity(count);
842 let mut running = header_and_offsets + key_data_len;
843 for attribute in &self.attributes {
844 match attribute {
845 Some(value) => {
846 offsets.push(running as u32 | ATTRIBUTE_OFFSET_FLAG);
847 running += value.encoded_len();
848 }
849 None => offsets.push(0),
850 }
851 }
852 let size = running;
853
854 let mut out = Vec::with_capacity(size);
855 out.extend_from_slice(&(size as u32).to_be_bytes());
856 out.extend_from_slice(&self.number.to_be_bytes());
857 out.extend_from_slice(&self.version.to_be_bytes());
858 out.extend_from_slice(&self.unknown3.to_be_bytes());
859 out.extend_from_slice(&(self.key_data.len() as u32).to_be_bytes());
860 out.extend_from_slice(&self.unknown5.to_be_bytes());
861 for offset in offsets {
862 out.extend_from_slice(&offset.to_be_bytes());
863 }
864 out.extend_from_slice(&self.key_data);
865 out.resize(header_and_offsets + key_data_len, 0);
866 for value in self.attributes.iter().flatten() {
867 value.write(&mut out);
868 }
869
870 debug_assert_eq!(
871 out.len(),
872 size,
873 "record serialization disagreed with its own layout"
874 );
875 Ok(out)
876 }
877}
878
879fn read_value(cursor: &Cursor<'_>, at: usize, format: AttributeFormat) -> Result<Value> {
880 Ok(match format {
881 AttributeFormat::Sint32 => Value::Sint32(cursor.u32(at)? as i32),
882 AttributeFormat::Uint32 => Value::Uint32(cursor.u32(at)?),
883 AttributeFormat::TimeDate => Value::Date(cursor.bytes(at, 16)?.to_vec()),
884 AttributeFormat::String => {
885 let len = cursor.u32(at)? as usize;
886 Value::String(cursor.bytes(at + 4, len)?.to_vec())
887 }
888 _ => {
890 let len = cursor.u32(at)? as usize;
891 Value::Blob(cursor.bytes(at + 4, len)?.to_vec())
892 }
893 })
894}
895
896pub fn records_by_type(keychain: &Keychain) -> BTreeMap<RecordType, Vec<&Record>> {
898 let mut out = BTreeMap::new();
899 for table in &keychain.tables {
900 out.insert(table.record_type, table.records().collect());
901 }
902 out
903}
904
905#[cfg(test)]
906mod tests {
907 use super::*;
908
909 #[test]
910 fn padding_rounds_up_to_four() {
911 assert_eq!(pad4(0), 0);
912 assert_eq!(pad4(1), 4);
913 assert_eq!(pad4(4), 4);
914 assert_eq!(pad4(13), 16);
915 }
916
917 #[test]
918 fn rejects_files_that_are_not_keychains() {
919 assert!(matches!(
920 Keychain::parse(b"not a keychain at all!!!"),
921 Err(Error::NotAKeychain)
922 ));
923 assert!(matches!(
924 Keychain::parse(b"kych"),
925 Err(Error::Truncated { .. })
926 ));
927 }
928
929 #[test]
930 fn value_encoding_lengths_match_the_layout_rules() {
931 assert_eq!(Value::Uint32(7).encoded_len(), 4);
932 assert_eq!(Value::Date(b"20260725095125Z\0".to_vec()).encoded_len(), 16);
933 assert_eq!(Value::Blob(b"alice".to_vec()).encoded_len(), 12);
935 assert_eq!(Value::Blob(b"myservice".to_vec()).encoded_len(), 16);
936 assert_eq!(Value::Blob(Vec::new()).encoded_len(), 4);
937 }
938
939 #[test]
940 fn values_serialize_with_prefix_and_padding() {
941 let mut out = Vec::new();
942 Value::Blob(b"alice".to_vec()).write(&mut out);
943 assert_eq!(out, b"\x00\x00\x00\x05alice\0\0\0");
944
945 let mut out = Vec::new();
946 Value::Date(b"20260725095125Z\0".to_vec()).write(&mut out);
947 assert_eq!(out.len(), 16);
948 assert_eq!(&out, b"20260725095125Z\0");
949
950 let mut out = Vec::new();
952 Value::Date(b"2026".to_vec()).write(&mut out);
953 assert_eq!(out, b"2026\0\0\0\0\0\0\0\0\0\0\0\0");
954 }
955
956 #[test]
957 fn display_prefers_text_and_falls_back_to_hex() {
958 assert_eq!(
959 Value::Blob(b"alice\0".to_vec()).to_display_string(),
960 "alice"
961 );
962 assert_eq!(Value::Uint32(8080).to_display_string(), "8080");
963 assert_eq!(Value::Blob(vec![0xff, 0xfe]).to_display_string(), "0xfffe");
964 assert_eq!(
965 Value::Date(b"20260725095125Z\0".to_vec()).to_display_string(),
966 "20260725095125Z"
967 );
968 }
969
970 #[test]
971 fn trim_nul_stops_at_the_first_terminator() {
972 assert_eq!(trim_nul(b"abc\0def"), b"abc");
973 assert_eq!(trim_nul(b"abc"), b"abc");
974 assert_eq!(trim_nul(b"\0"), b"");
975 }
976
977 #[test]
978 fn a_freed_slot_is_the_next_one_allocated() {
979 let record = |number| Record {
980 number,
981 version: 0,
982 unknown3: 0,
983 unknown5: 0,
984 key_data: Vec::new(),
985 attributes: vec![None],
986 };
987 let mut table = Table {
988 record_type: RecordType::GENERIC_PASSWORD,
989 free_list_head: 0,
990 slots: vec![
991 Slot::Record(record(0)),
992 Slot::Empty,
993 Slot::Record(record(2)),
994 ],
995 layout: vec![0, 2],
996 indexes: TableIndexes::Parsed(IndexBlob {
997 indexes: Vec::new(),
998 }),
999 };
1000
1001 assert_eq!(table.record_count(), 2);
1002
1003 assert_eq!(table.insert(record(99)), 1);
1005 assert_eq!(table.slots.len(), 3, "the hole was reused");
1006 assert_eq!(table.slots[1].record().map(|record| record.number), Some(1));
1007 assert_eq!(table.free_list_head, 0, "no free slots left");
1008
1009 assert_eq!(table.insert(record(99)), 3);
1011 assert_eq!(table.slots.len(), 4);
1012 }
1013
1014 #[test]
1015 fn the_free_list_is_a_chain_through_the_slot_array() {
1016 let record = |number| Record {
1017 number,
1018 version: 0,
1019 unknown3: 0,
1020 unknown5: 0,
1021 key_data: Vec::new(),
1022 attributes: vec![None],
1023 };
1024 let mut table = Table {
1025 record_type: RecordType::GENERIC_PASSWORD,
1026 free_list_head: 0,
1027 slots: (0..4).map(|number| Slot::Record(record(number))).collect(),
1028 layout: vec![0, 1, 2, 3],
1029 indexes: TableIndexes::Parsed(IndexBlob {
1030 indexes: Vec::new(),
1031 }),
1032 };
1033
1034 assert!(table.delete(2));
1038 assert!(table.delete(0));
1039 assert_eq!(table.free_list_head, (TABLE_HEADER_LEN as u32 + 8) | 1);
1040 assert_eq!(table.slots[2], Slot::Free(TABLE_HEADER_LEN as u32 | 1));
1041 assert_eq!(table.slots[0], Slot::Empty);
1042
1043 let mut other = Table {
1046 record_type: RecordType::GENERIC_PASSWORD,
1047 free_list_head: 0,
1048 slots: (0..4).map(|number| Slot::Record(record(number))).collect(),
1049 layout: vec![0, 1, 2, 3],
1050 indexes: TableIndexes::Parsed(IndexBlob {
1051 indexes: Vec::new(),
1052 }),
1053 };
1054 assert!(other.delete(0));
1055 assert!(other.delete(2));
1056 assert_eq!(other.slots, table.slots);
1057 assert_eq!(other.free_list_head, table.free_list_head);
1058
1059 assert!(table.delete(3));
1062 assert_eq!(table.slots.len(), 3);
1063 assert_eq!(table.record_count(), 1);
1064 assert!(table.delete(1));
1065 assert_eq!(table.slots.len(), 3, "slot 1 is not the last one");
1066 assert_eq!(table.record_count(), 0);
1067 }
1068
1069 #[test]
1070 fn records_keep_their_place_in_the_file_when_a_slot_is_reused() {
1071 let record = |number, data: &[u8]| Record {
1072 number,
1073 version: 0,
1074 unknown3: 0,
1075 unknown5: 0,
1076 key_data: data.to_vec(),
1077 attributes: vec![None],
1078 };
1079 let mut table = Table {
1080 record_type: RecordType::GENERIC_PASSWORD,
1081 free_list_head: 0,
1082 slots: vec![
1083 Slot::Record(record(0, b"first")),
1084 Slot::Record(record(1, b"second")),
1085 Slot::Record(record(2, b"third")),
1086 ],
1087 layout: vec![0, 1, 2],
1088 indexes: TableIndexes::Parsed(IndexBlob {
1089 indexes: Vec::new(),
1090 }),
1091 };
1092
1093 table.delete(1);
1097 table.insert(record(0, b"fourth"));
1098 assert_eq!(table.layout, vec![0, 2, 1]);
1099
1100 let bytes = table.to_bytes().unwrap();
1101 let offset = |slot: usize| {
1102 let at = TABLE_HEADER_LEN + slot * 4;
1103 u32::from_be_bytes(bytes[at..at + 4].try_into().unwrap())
1104 };
1105 assert!(
1106 offset(1) > offset(2),
1107 "the reused slot's record is last in the file"
1108 );
1109 }
1110}