apple_bom/

format.rs

// Copyright 2022 Gregory Szorc.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! BOM file format primitives.
//!
//! Apple doesn't appear to have documented the BOM file format in any
//! publications or open source source code. So details of our understanding
//! of the BOM format could be wildly inaccurate.
//!
//! # File Format
//!
//! BOM files start with a header, [BomHeader]. The first 8 bytes of which
//! are magic `BOMStore`.
//!
//! BOM files logically consist of a collection of *blocks* and
//! *variables*. Each of these is defined by an *index*, the location of
//! which is defined in [BomHeader]. The *blocks* index is defined by
//! [BomBlocksIndex] and the *vars* index by [BomVarsIndex].
//!
//! Each *block* is simply an offset and length effectively denoting a
//! `&[u8]` from the source data. *Blocks* can be multiple types. These
//! types are represented by `BomBlock*` types in this module. The type
//! of each *block* is not explicitly captured by the blocks index. Rather,
//! block indices are referenced elsewhere and the block type is inferred
//! by the context of its reference.
//!
//! *Variables* define named content in the BOM, with each name denoting
//! special behavior. Each generic variable is defined by [BomVar] and
//! consists of a name and *block* index holding its data.
//!
//! # Block Types
//!
//! Here are the known block types:
//!
//! * [BomBlockBomInfo]
//! * [BomBlockFile]
//! * [BomBlockPathInfoIndex]
//! * [BomBlockPathRecord]
//! * [BomBlockPathRecordPointer]
//! * [BomBlockPaths]
//! * [BomBlockTree]
//! * [BomBlockTreePointer]
//! * [BomBlockVIndex]
//!
//! See the documentation for each type for more details.
//!
//! # Variables
//!
//! This section documents what we know about each named variable.
//!
//! ## BomInfo
//!
//! Defines high-level information about the BOM. Its block data is [BomBlockBomInfo].
//!
//! ## Paths
//!
//! Defines the paths tracked by the BOM. Its block data is [BomBlockTree].
//!
//! ## HLIndex
//!
//! Defines hard links. Its block data is [BomBlockTree].
//!
//! ## VIndex
//!
//! Unknown. Its block data is [BomBlockVIndex].
//!
//! ## Size64
//!
//! Unknown. Its block data is [BomBlockTree].
//!
//! # Layout
//!
//! In theory, the sequential ordering of blocks and variables can be random,
//! as variables refer to block indices and blocks also refer to block indices.
//! This section describes the layout seen in BOMs generated by Apple tools.
//!
//! Variables occur in the order `BomInfo`, `Paths`, `HLIndex`, `VIndex`,
//! `Size64`.
//!
//! The 1st block (index 0) appears to always be a NULL block with no
//! content.
//!
//! Block 1 is a [BomBlockBomInfo].
//!
//! Block 2 is a [BomBlockTree] holding the `Paths` root tree record.
//!
//! Block 3 is a [BomBlockPaths] holding initial paths for the `Paths` variable.
//!
//! Block 4 is a [BomBlockTree] holding the `HLIndex` root tree record.
//!
//! Block 5 is a [BomBlockPaths] holding initial paths for the `HLIndex` variable.
//!
//! Block 6 is a [BomBlockVIndex] holding the data structure for the `VIndex`
//! variable.
//!
//! Block 7 is a [BomBlockTree] holding the `VIndex` root tree.
//!
//! Block 8 is a [BomBlockPaths] holding initial paths for the `VIndex` tree.
//!
//! Block 9 is a [BomBlockTree] holding the `Size64` root tree.
//!
//! Block 10 is a [BomBlockPaths] holding initial paths for the `Size64` tree.
//!
//! Starting at block 11 are records describing paths. This starts with a
//! [BomBlockPathRecord] holding concrete path info (type, mode, size, owner,
//! checksum, etc). Its [BomBlockFile] and [BomBlockPathInfoIndex] follow.
//! Both [BomBlockFile] and [BomBlockPathInfoIndex] are pointed to by entries
//! in [BomBlockPaths]. [BomBlockPathInfoIndex] points to the block index of
//! the [BomBlockPathRecord] it is describing.
//!
//! These [BomBlockPathRecord], [BomBlockFile], and [BomBlockPathInfoIndex]
//! triplets repeat for every path described in the [BomBlockPaths].
//!
//! Multiple [BomBlockPaths] may be necessary to hold all file records. These
//! blocks may be located in the middle of the aforementioned sequence of
//! path blocks. The block order doesn't appear to be strict. For example,
//! single [BomBlockPaths] referencing blocks both before and after the
//! current block can occur.
//!
//! Following the final [BomBlockPathInfoIndex] are tuples of [BomBlockTree],
//! [BomBlockPaths], [BomBlockPathRecordPointer], [BomBlockTreePointer]. The
//! purpose of these is not fully known. The [BomBlockPaths] records always
//! appear to be empty. There appears to be a [BomBlockPathRecordPointer] for
//! every path in the BOM.
//!
//! The order of the blocks in the payload and in the blocks index may not
//! match. For example, Apple's BOM creation puts blocks with low block
//! numbers such as [BomBlockBomInfo] (block #1) and the [BomBlockPaths]
//! structures towards the end of the payload. It is likely that *index* data
//! is buffered and then written out at the end, once the state of the world
//! is fully known.

use {
    crate::{
        error::Error,
        path::{BomPath, BomPathType},
    },
    scroll::{IOwrite, Pread, Pwrite, SizeWith},
    std::{
        borrow::Cow,
        collections::HashMap,
        ffi::CStr,
        io::{Cursor, Write},
    },
};

/// The header for a BOM file.
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomHeader {
    /// Format magic. Always `BOMStore`
    pub magic: [u8; 8],

    /// File format version number.
    pub version: u32,

    /// Number of *blocks* in this BOM.
    pub number_of_blocks: u32,

    /// Start offset of blocks index relative to start of this header.
    pub blocks_index_offset: u32,

    /// Length of blocks index in bytes.
    pub blocks_index_length: u32,

    /// Start offset of variables index relative to start of this header.
    pub vars_index_offset: u32,

    /// Length of variables index in bytes.
    pub vars_index_length: u32,
}

impl BomHeader {
    /// Obtain the raw data holding the *blocks* index.
    pub fn blocks_index_data<'a>(&self, data: &'a [u8]) -> &'a [u8] {
        &data[self.blocks_index_offset as usize
            ..(self.blocks_index_offset + self.blocks_index_length) as usize]
    }

    /// Parse the *blocks* index.
    pub fn blocks_index(&self, data: &[u8]) -> Result<BomBlocksIndex, Error> {
        self.blocks_index_data(data)
            .pread_with::<BomBlocksIndex>(0, scroll::BE)
    }

    /// Obtain the raw data holding the *vars* index.
    pub fn vars_index_data<'a>(&self, data: &'a [u8]) -> &'a [u8] {
        &data[self.vars_index_offset as usize
            ..(self.vars_index_offset + self.vars_index_length) as usize]
    }

    /// Parse the *vars* index.
    pub fn vars_index(&self, data: &[u8]) -> Result<BomVarsIndex, Error> {
        self.vars_index_data(data)
            .pread_with::<BomVarsIndex>(0, scroll::BE)
    }
}

/// Defines *blocks* in the BOM file.
///
/// This is the data structure referred to by [BomHeader::blocks_index_offset] and
/// [BomHeader::blocks_index_length].
///
/// The 1st block appears to always be NULL (0 values in its entry).
///
/// The blocks count in this data structure and [BomHeader::number_of_blocks] may
/// disagree. The number of blocks in the file header appears to be the number of
/// populated blocks, not counting the initial NULL/empty/0 block. And the block
/// count in this data structure can be substantially larger than what is reported
/// by the file header.
#[derive(Clone, Default, Debug)]
pub struct BomBlocksIndex {
    /// The number of entries in this index.
    pub count: u32,

    /// The records defining individual blocks.
    pub blocks: Vec<BomBlocksEntry>,
}

impl BomBlocksIndex {
    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.count, scroll::BE)?;

        for entry in &self.blocks {
            writer.iowrite_with(*entry, scroll::BE)?;
        }

        Ok(())
    }

    /// Serialize this data structure to bytes.
    pub fn to_vec(&self) -> Result<Vec<u8>, Error> {
        let mut writer = Cursor::new(Vec::<u8>::new());
        self.write(&mut writer)?;
        Ok(writer.into_inner())
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomBlocksIndex {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let offset = &mut 0;

        let count = data.gread_with::<u32>(offset, le)?;
        let mut blocks = Vec::with_capacity(count as usize);

        for _ in 0..count {
            blocks.push(data.gread_with::<BomBlocksEntry>(offset, le)?);
        }

        Ok((Self { count, blocks }, *offset))
    }
}

/// Defines the location of a *block*.
///
/// This type is part of [BomBlocksIndex].
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomBlocksEntry {
    /// Start offset of block data relative to start of file / [BomHeader].
    pub file_offset: u32,

    /// Length in bytes of block data.
    pub length: u32,
}

/// Describes an individual BOM variable.
///
/// A variable consists of a string name and pointer to the block index
/// holding its variable-specific data.
#[derive(Clone, Debug)]
pub struct BomVar {
    /// Index of block holding data for this variable.
    pub block_index: u32,

    /// Length of name. Does not include NULL terminator.
    pub name_length: u8,

    /// Name of variable.
    pub name: String,
}

impl BomVar {
    /// Construct a new instance given a string.
    pub fn new(block_index: u32, name: impl ToString) -> Result<Self, Error> {
        let name = name.to_string();

        if name.as_bytes().len() > 254 {
            return Err(Error::BadVariableString);
        }

        Ok(Self {
            block_index,
            name_length: name.as_bytes().len() as u8 + 1,
            name,
        })
    }

    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.block_index, scroll::BE)?;
        writer.iowrite_with(self.name_length, scroll::BE)?;
        writer.write_all(self.name.as_bytes())?;
        writer.write_all(b"\0")?;

        Ok(())
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomVar {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let index = data.pread_with(0, le)?;
        let length = data.pread_with(4, le)?;

        let name_data = &data[5..5 + length as usize];
        let name = String::from_utf8(name_data.to_vec()).map_err(|_| Error::BadVariableString)?;

        Ok((
            Self {
                block_index: index,
                name_length: length,
                name,
            },
            5 + name_data.len(),
        ))
    }
}

/// Block type for `BomInfo` variable.
///
/// Describes high-level information about the BOM, notably the version and
/// number of paths.
#[repr(C)]
#[derive(Clone, Default, Debug)]
pub struct BomBlockBomInfo {
    /// BOM version.
    pub version: u32,

    /// Total number of paths tracked by this BOM.
    pub number_of_paths: u32,

    /// Number of [BomInfoEntry] records in this data structure.
    pub number_of_info_entries: u32,

    /// Further describes attributes of the BOM.
    pub entries: Vec<BomInfoEntry>,
}

impl BomBlockBomInfo {
    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.version, scroll::BE)?;
        writer.iowrite_with(self.number_of_paths, scroll::BE)?;
        writer.iowrite_with(self.number_of_info_entries, scroll::BE)?;

        for entry in &self.entries {
            writer.iowrite_with(*entry, scroll::BE)?;
        }

        Ok(())
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomBlockBomInfo {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let offset = &mut 0;

        let version = data.gread_with(offset, le)?;
        let number_of_paths = data.gread_with(offset, le)?;
        let number_of_info_entries = data.gread_with(offset, le)?;
        let mut entries = Vec::with_capacity(number_of_info_entries as usize);

        for _ in 0..number_of_info_entries {
            entries.push(data.gread_with(offset, le)?);
        }

        Ok((
            Self {
                version,
                number_of_paths,
                number_of_info_entries,
                entries,
            },
            *offset,
        ))
    }
}

/// Holds data records stored within [BomBlockBomInfo].
///
/// The fields have something to do with architecture information. But we don't
/// know what exactly.
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomInfoEntry {
    pub a: u32,
    pub b: u32,
    pub c: u32,
    pub d: u32,
}

/// Block describing a named file.
#[derive(Clone, Debug)]
pub struct BomBlockFile<'a> {
    /// Internal path ID of parent path.
    ///
    /// `0` means no parent (this file exists at the root).
    pub parent_path_id: u32,

    /// The name of this file.
    ///
    /// Only the leaf file or directory name. i.e. the final component in a
    /// path.
    pub name: Cow<'a, CStr>,
}

impl<'a> BomBlockFile<'a> {
    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.parent_path_id, scroll::BE)?;
        writer.write_all(self.name.to_bytes_with_nul())?;

        Ok(())
    }

    /// Obtain the file name as a [String].
    pub fn string_file_name(&self) -> String {
        self.name.to_string_lossy().to_string()
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomBlockFile<'a> {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let parent = data.pread_with(0, le)?;
        let name =
            Cow::from(CStr::from_bytes_with_nul(&data[4..]).map_err(|_| Error::BadVariableString)?);

        Ok((
            Self {
                parent_path_id: parent,
                name,
            },
            data.len(),
        ))
    }
}

/// A pointer to a block index holding a [BomBlockPathRecord].
///
/// We're unsure what this block type is used for. But instances appear to
/// follow [BomBlockTree] and [BomBlockPaths] entries for every given path.
/// Maybe it allows instances of [BomBlockTree] to easily obtain a reference
/// back to the [BomBlockPathRecord] since this pointer appears to always exist
/// at block index [BomBlockTree::block_paths_index] + 1.
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomBlockPathRecordPointer {
    /// Block index of corresponding [BomBlockPathRecord].
    pub block_path_record_index: u32,
}

impl BomBlockPathRecordPointer {
    pub fn path_record<'a>(&self, bom: &'a ParsedBom) -> Result<BomBlockPathRecord<'a>, Error> {
        bom.block_as_path_record(self.block_path_record_index as _)
    }
}

/// Block type describing a collection of paths.
///
/// Instances come in 2 flavors, denoted by [Self::is_path_info]. If this field
/// is `1`, the [BomPathsEntry] instances describe specific tracked poths by
/// pointing to blocks with [BomBlockPathInfoIndex] and [BomBlockFile] that
/// describe each path. If `0`, the [BomPathsEntry] is a pointer to another
/// [BomBlockPaths] instance.
///
/// Each logical path appears to have an internal numeric identifier uniquely
/// describing the path. This *path ID* is used for paths to refer to each
/// other. For example, [BomBlockFile] refers to its parent directory/path
/// via this ID.
#[repr(C)]
#[derive(Clone, Default, Debug)]
pub struct BomBlockPaths {
    /// Whether the block pointer in [BomPathsEntry] refers to [BomBlockPathInfoIndex].
    ///
    /// 0 means it is a pointer to [BomBlockPaths].
    pub is_path_info: u16,

    /// The number of [BomPathsEntry] in this data structure.
    pub count: u16,

    /// Block index of [BomBlockPaths] that is after this one.
    pub next_paths_block_index: u32,

    /// Block index of [BomBlockPaths] that is before this one.
    pub previous_paths_block_index: u32,

    /// The paths tracked by this instance.
    pub paths: Vec<BomPathsEntry>,
}

impl BomBlockPaths {
    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.is_path_info, scroll::BE)?;
        writer.iowrite_with(self.count, scroll::BE)?;
        writer.iowrite_with(self.next_paths_block_index, scroll::BE)?;
        writer.iowrite_with(self.previous_paths_block_index, scroll::BE)?;

        for entry in &self.paths {
            writer.iowrite_with(*entry, scroll::BE)?;
        }

        Ok(())
    }

    /// Resolve the [BomBlockFile] for a path at a given index.
    pub fn file_at<'a>(&self, bom: &'a ParsedBom, index: usize) -> Result<BomBlockFile<'a>, Error> {
        self.paths.get(index).ok_or(Error::BadIndex)?.file(bom)
    }

    /// Resolve the [BomBlockPathInfoIndex] for a path at a given index.
    pub fn path_info_at(
        &self,
        bom: &ParsedBom,
        index: usize,
    ) -> Result<BomBlockPathInfoIndex, Error> {
        self.paths.get(index).ok_or(Error::BadIndex)?.path_info(bom)
    }

    /// Resolve the internal path ID for a path at a given index.
    pub fn path_id_at(&self, bom: &ParsedBom, index: usize) -> Result<u32, Error> {
        Ok(self.path_info_at(bom, index)?.path_id)
    }

    /// Resolve the [BomBlockPathRecord] for a path at a given index.
    pub fn path_record_at<'a>(
        &self,
        bom: &'a ParsedBom,
        index: usize,
    ) -> Result<BomBlockPathRecord<'a>, Error> {
        self.path_info_at(bom, index)?.path_record(bom)
    }

    /// Resolve all meaningful path data for a path at a given index.
    pub fn path_entry_at<'a>(
        &self,
        bom: &'a ParsedBom,
        index: usize,
    ) -> Result<(u32, BomBlockFile<'a>, BomBlockPathRecord<'a>), Error> {
        let path_info = self.path_info_at(bom, index)?;
        let file = self.file_at(bom, index)?;
        let record = path_info.path_record(bom)?;

        Ok((path_info.path_id, file, record))
    }

    /// Obtain resolved records for each path defined on this instance.
    ///
    /// This will only yield records for the current block.
    ///
    /// See [BomBlockTree::bom_paths] for logic that iterates over paths
    /// across multiple block records.
    pub fn iter_path_entries<'a, 'b: 'a>(
        &'a self,
        bom: &'b ParsedBom,
    ) -> impl Iterator<Item = Result<(u32, BomBlockFile<'b>, BomBlockPathRecord<'b>), Error>> + 'a
    {
        self.paths
            .iter()
            .enumerate()
            .map(move |(i, _)| self.path_entry_at(bom, i))
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomBlockPaths {
    type Error = scroll::Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let offset = &mut 0;

        let is_path_info = data.gread_with::<u16>(offset, le)?;
        let count = data.gread_with::<u16>(offset, le)?;
        let forward = data.gread_with::<u32>(offset, le)?;
        let backward = data.gread_with::<u32>(offset, le)?;

        let mut paths = Vec::with_capacity(count as usize);
        for _ in 0..count {
            paths.push(data.gread_with::<BomPathsEntry>(offset, le)?);
        }

        Ok((
            Self {
                is_path_info,
                count,
                next_paths_block_index: forward,
                previous_paths_block_index: backward,
                paths,
            },
            *offset,
        ))
    }
}

/// Describes where to find metadata on a single path.
///
/// This type is contained within [BomBlockPaths].
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomPathsEntry {
    /// Block index of associated data structure.
    ///
    /// It appears this can refer to both a [BomBlockPathInfoIndex] or
    /// a [BomBlockPaths]. When referring to a [BomBlockPathInfoIndex],
    /// `file_index` is this path's [BomBlockFile] index. When referring
    /// to a [BomBlockPaths], `file_index` appears to refer to the final
    /// [BomBlockFile] referred to by the [BomBlockPaths].
    pub block_index: u32,

    ///
    /// Block index of [BomBlockFile].
    pub file_index: u32,
}

impl BomPathsEntry {
    /// Resolve the [BomBlockPathInfoIndex] this instance points to.
    pub fn path_info(&self, bom: &ParsedBom) -> Result<BomBlockPathInfoIndex, Error> {
        bom.block_as_path_info_index(self.block_index as _)
    }

    /// Resolve the [BomBlockPaths] this instance points to.
    pub fn paths(&self, bom: &ParsedBom) -> Result<BomBlockPaths, Error> {
        bom.block_as_paths(self.block_index as _)
    }

    /// Resolve the [BomBlockFile] this instance points to.
    pub fn file<'a>(&self, bom: &'a ParsedBom) -> Result<BomBlockFile<'a>, Error> {
        bom.block_as_file(self.file_index as _)
    }
}

/// Block type describing a single path.
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomBlockPathInfoIndex {
    /// Unique identifier for this path.
    ///
    /// This is not a block index.
    pub path_id: u32,

    /// Block index of [BomBlockPathRecord] holding metadata for this path.
    pub path_record_index: u32,
}

impl BomBlockPathInfoIndex {
    /// Resolve the [BomBlockPathRecord] this instance points to.
    pub fn path_record<'a>(&self, bom: &'a ParsedBom) -> Result<BomBlockPathRecord<'a>, Error> {
        bom.block_as_path_record(self.path_record_index as _)
    }
}

/// Block type defining low-level path information.
///
/// This is where most of the metadata defining a BOM path lives.
#[repr(C)]
#[derive(Clone, Default, Debug)]
pub struct BomBlockPathRecord<'a> {
    /// The type of the path.
    ///
    /// See [crate::BomPathType] for definitions.
    pub path_type: u8,

    /// Unknown.
    pub a: u8,

    /// File architecture.
    ///
    /// Probably corresponds to value in Mach-O header.
    pub architecture: u16,

    /// File mode.
    pub mode: u16,

    /// UID of owner.
    pub user: u32,

    /// GID of owner.
    pub group: u32,

    /// Modified time in seconds since UNIX epoch.
    pub mtime: u32,

    /// Size in bytes.
    pub size: u32,

    /// Unknown.
    pub b: u8,

    /// CRC32 checksum or device type.
    pub checksum_or_type: u32,

    /// Length of link name.
    ///
    /// May be non-0 for non-link path records.
    ///
    /// Includes NULL terminator.
    pub link_name_length: u32,

    /// Link path name.
    pub link_name: Option<Cow<'a, CStr>>,
}

impl<'a> BomBlockPathRecord<'a> {
    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.path_type, scroll::BE)?;
        writer.iowrite_with(self.a, scroll::BE)?;
        writer.iowrite_with(self.architecture, scroll::BE)?;
        writer.iowrite_with(self.mode, scroll::BE)?;
        writer.iowrite_with(self.user, scroll::BE)?;
        writer.iowrite_with(self.group, scroll::BE)?;
        writer.iowrite_with(self.mtime, scroll::BE)?;
        writer.iowrite_with(self.size, scroll::BE)?;
        writer.iowrite_with(self.b, scroll::BE)?;
        writer.iowrite_with(self.checksum_or_type, scroll::BE)?;
        writer.iowrite_with(self.link_name_length, scroll::BE)?;
        if let Some(link_name) = &self.link_name {
            writer.write_all(link_name.to_bytes_with_nul())?;
        }

        Ok(())
    }

    /// Obtain the link name of this record, if present.
    pub fn string_link_name(&self) -> Option<String> {
        self.link_name
            .as_ref()
            .map(|s| s.to_string_lossy().to_string())
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomBlockPathRecord<'a> {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let offset = &mut 0;

        let path_type = data.gread_with(offset, le)?;
        let a = data.gread_with(offset, le)?;
        let architecture = data.gread_with(offset, le)?;
        let mode = data.gread_with(offset, le)?;
        let user = data.gread_with(offset, le)?;
        let group = data.gread_with(offset, le)?;
        let mtime = data.gread_with(offset, le)?;
        let size = data.gread_with(offset, le)?;
        let b = data.gread_with(offset, le)?;
        let checksum_or_type = data.gread_with(offset, le)?;
        let link_name_length = data.gread_with(offset, le)?;

        let link_name = if path_type == BomPathType::Link.into() && link_name_length > 0 {
            let link_name_data = &data[*offset..*offset + link_name_length as usize];
            Some(Cow::from(
                CStr::from_bytes_with_nul(link_name_data).map_err(|_| Error::BadVariableString)?,
            ))
        } else {
            None
        };

        Ok((
            Self {
                path_type,
                a,
                architecture,
                mode,
                user,
                group,
                mtime,
                size,
                b,
                checksum_or_type,
                link_name_length,
                link_name,
            },
            *offset,
        ))
    }
}

/// Block type for various variables describing a collection/tree of paths.
#[repr(C)]
#[derive(Clone, Copy, Debug, IOwrite, Pwrite, SizeWith)]
pub struct BomBlockTree {
    /// Always `tree`.
    pub tree: [u8; 4],

    /// Version of this data structure.
    pub version: u32,

    /// Block index of [BomBlockPaths] describing paths.
    pub block_paths_index: u32,

    /// Block size. Always appears to be 4096.
    pub block_size: u32,

    /// Number of paths tracked by this tree.
    pub path_count: u32,

    /// Unknown.
    pub a: u8,
}

impl Default for BomBlockTree {
    fn default() -> Self {
        Self {
            tree: *b"tree",
            version: 1,
            block_paths_index: 0,
            block_size: 0,
            path_count: 0,
            a: 0,
        }
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomBlockTree {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let offset = &mut 4;

        let tree: [u8; 4] = [data[0], data[1], data[2], data[3]];
        let version = data.gread_with(offset, le)?;
        let block_paths_index = data.gread_with(offset, le)?;
        let block_size = data.gread_with(offset, le)?;
        let path_count = data.gread_with(offset, le)?;
        let a = data.gread_with(offset, le)?;

        if &tree != b"tree" {
            return Err(Error::Scroll(scroll::Error::Custom(
                "bad tree magic".into(),
            )));
        }

        Ok((
            Self {
                tree,
                version,
                block_paths_index,
                block_size,
                path_count,
                a,
            },
            *offset,
        ))
    }
}

impl BomBlockTree {
    /// Resolve the [BomBlockPaths] this instance points to.
    pub fn paths(&self, bom: &ParsedBom) -> Result<BomBlockPaths, Error> {
        bom.block_as_paths(self.block_paths_index as _)
    }

    /// Resolve the [BomBlockPaths] that is the root of the tree.
    pub fn root_paths(&self, bom: &ParsedBom) -> Result<BomBlockPaths, Error> {
        let mut paths = self.paths(bom)?;

        while paths.is_path_info == 0 {
            let entry = paths.paths.get(0).ok_or(Error::BadIndex)?;
            paths = entry.paths(bom)?;
        }

        Ok(paths)
    }

    /// Resolve all [BomPath] in this tree.
    ///
    /// This contains the logic for iterating over multiple [BomBlockPaths] instances.
    pub fn bom_paths(&self, bom: &ParsedBom) -> Result<Vec<BomPath>, Error> {
        let mut res = Vec::with_capacity(self.path_count as _);

        let mut paths = self.root_paths(bom)?;
        let mut files_by_id = HashMap::with_capacity(res.capacity());

        loop {
            for entry in paths.iter_path_entries(bom) {
                let (path_id, file, record) = entry?;

                // The full filename is resolved by traversing the file's parent path ID until
                // we get to a root.
                let mut resolve_file = &file;
                let mut filename = file.string_file_name();

                while resolve_file.parent_path_id != 0 {
                    resolve_file = files_by_id
                        .get(&resolve_file.parent_path_id)
                        .ok_or(Error::BadIndex)?;
                    filename = format!("{}/{}", resolve_file.string_file_name(), filename);
                }

                res.push(BomPath::from_record(filename, &record)?);

                files_by_id.insert(path_id, file);
            }

            if paths.next_paths_block_index != 0 {
                paths = bom.block_as_paths(paths.next_paths_block_index as _)?;
            } else {
                break;
            }
        }

        Ok(res)
    }
}

/// A pointer to a block index holding a [BomBlockTree].
///
/// We're unsure what this block type is used for. But instances appear to
/// follow [BomBlockPaths] / [BomBlockPathRecordPointer] entries for every given path.
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomBlockTreePointer {
    /// Block index of corresponding [BomBlockTree].
    pub block_tree_index: u32,
}

impl BomBlockTreePointer {
    pub fn tree(&self, bom: &ParsedBom) -> Result<BomBlockTree, Error> {
        bom.block_as_tree(self.block_tree_index as _)
    }
}

/// Block type for the `VIndex` variable data.
///
/// We don't know much about this data structure.
#[repr(C)]
#[derive(Clone, Copy, Default, Debug, IOwrite, Pread, Pwrite, SizeWith)]
pub struct BomBlockVIndex {
    /// Unknown.
    pub a: u32,

    /// Block index holding a [BomBlockTree].
    pub tree_block_index: u32,

    /// Unknown.
    pub b: u32,

    /// Unknown.
    pub c: u8,
}

impl BomBlockVIndex {
    /// Resolve the [BomBlockTree] this instance points to.
    pub fn tree(&self, bom: &ParsedBom) -> Result<BomBlockTree, Error> {
        bom.block_as_tree(self.tree_block_index as _)
    }
}

/// The collection of variables in a BOM file.
///
/// This structure is what [BomHeader::vars_index_offset] and
/// [BomHeader::vars_index_length] refers to.
#[derive(Clone, Debug)]
pub struct BomVarsIndex {
    /// Number of variables.
    pub count: u32,

    /// Records for each variable.
    pub vars: Vec<BomVar>,
}

impl BomVarsIndex {
    /// Write this data structure to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        writer.iowrite_with(self.count, scroll::BE)?;

        for var in &self.vars {
            var.write(writer)?;
        }

        Ok(())
    }

    /// Obtain the bytes representation of this data structure.
    pub fn to_vec(&self) -> Result<Vec<u8>, Error> {
        let mut writer = Cursor::new(Vec::<u8>::new());
        self.write(&mut writer)?;
        Ok(writer.into_inner())
    }
}

impl<'a> scroll::ctx::TryFromCtx<'a, scroll::Endian> for BomVarsIndex {
    type Error = Error;

    fn try_from_ctx(data: &'a [u8], le: scroll::Endian) -> Result<(Self, usize), Self::Error> {
        let offset = &mut 0;

        let count = data.gread_with::<u32>(offset, le)?;
        let mut vars = Vec::with_capacity(count as usize);

        for _ in 0..count {
            vars.push(data.gread_with::<BomVar>(offset, le)?);
        }

        Ok((Self { count, vars }, *offset))
    }
}

/// Enumeration over known block types.
#[derive(Clone, Debug)]
pub enum BomBlock<'a> {
    Empty,
    BomInfo(BomBlockBomInfo),
    File(BomBlockFile<'a>),
    PathInfoIndex(BomBlockPathInfoIndex),
    PathRecord(BomBlockPathRecord<'a>),
    PathRecordPointer(BomBlockPathRecordPointer),
    Paths(BomBlockPaths),
    Tree(BomBlockTree),
    TreePointer(BomBlockTreePointer),
    VIndex(BomBlockVIndex),
}

impl<'a> BomBlock<'a> {
    /// Attempt to resolve an instance from a [ParsedBom] and block index number.
    pub fn try_parse(bom: &'a ParsedBom, index: usize) -> Result<Self, Error> {
        if index == 1 {
            if let Ok(info) = bom.block_as_bom_info(index) {
                return Ok(Self::BomInfo(info));
            }
        }

        // Multiple block types may parse correctly. Our strategy to tease out
        // false positives is to recursively examine the parsed block and verify
        // all parts parse.
        if let Ok(tree) = bom.block_as_tree(index) {
            if tree.paths(bom).is_ok() {
                return Ok(Self::Tree(tree));
            }
        }

        if let Ok(paths) = bom.block_as_paths(index) {
            if paths.iter_path_entries(bom).all(|x| x.is_ok()) {
                return Ok(Self::Paths(paths));
            }
        }

        if let Ok(vindex) = bom.block_as_vindex(index) {
            if vindex.tree(bom).is_ok() {
                return Ok(Self::VIndex(vindex));
            }
        }

        if let Ok(index) = bom.block_as_path_info_index(index) {
            if index.path_record(bom).is_ok() {
                return Ok(Self::PathInfoIndex(index));
            }
        }

        // Path records are quite large.
        if let Ok(record) = bom.block_as_path_record(index) {
            return Ok(Self::PathRecord(record));
        }

        if let Ok(file) = bom.block_as_file(index) {
            return Ok(Self::File(file));
        }

        if let Ok(pointer) = bom.block_as_path_record_pointer(index) {
            if pointer.path_record(bom).is_ok() {
                return Ok(Self::PathRecordPointer(pointer));
            }
        }

        if let Ok(pointer) = bom.block_as_tree_pointer(index) {
            if pointer.tree(bom).is_ok() {
                return Ok(Self::TreePointer(pointer));
            }
        }

        if let Ok(info) = bom.block_as_bom_info(index) {
            return Ok(Self::BomInfo(info));
        }

        Err(Error::UnknownBlockType)
    }

    /// Write the block data to a writer.
    pub fn write(&self, writer: &mut impl Write) -> Result<(), Error> {
        match self {
            Self::Empty => {}
            Self::BomInfo(b) => {
                b.write(writer)?;
            }
            Self::File(b) => {
                b.write(writer)?;
            }
            Self::PathInfoIndex(b) => {
                writer.iowrite_with(*b, scroll::BE)?;
            }
            Self::PathRecord(b) => {
                b.write(writer)?;
            }
            Self::PathRecordPointer(b) => {
                writer.iowrite_with(*b, scroll::BE)?;
            }
            Self::Paths(b) => {
                b.write(writer)?;
            }
            Self::Tree(b) => {
                writer.iowrite_with(*b, scroll::BE)?;
            }
            Self::TreePointer(b) => {
                writer.iowrite_with(*b, scroll::BE)?;
            }
            Self::VIndex(b) => {
                writer.iowrite_with(*b, scroll::BE)?;
            }
        }

        Ok(())
    }

    /// Serialize this block to its bytes representation.
    pub fn to_vec(&self) -> Result<Vec<u8>, Error> {
        let mut writer = Cursor::new(Vec::<u8>::new());
        self.write(&mut writer)?;

        Ok(writer.into_inner())
    }
}

/// Parsed BOM data structure.
///
/// Instances hold references to the data they are backed by.
pub struct ParsedBom<'a> {
    /// Underlying data backing this BOM.
    pub data: Cow<'a, [u8]>,

    /// The file header.
    pub header: BomHeader,

    /// The blocks index.
    pub blocks: BomBlocksIndex,

    /// BOM variables.
    pub vars: BomVarsIndex,
}

impl<'a> ParsedBom<'a> {
    /// Parse BOM data into a data structure.
    ///
    /// Only the header and block and variable indices are parsed immediately.
    /// Everything else is lazily parsed.
    pub fn parse(data: &'a [u8]) -> Result<Self, Error> {
        let header = data.pread_with::<BomHeader>(0, scroll::BE)?;

        let blocks_index = header.blocks_index(data)?;
        let vars = header.vars_index(data)?;

        Ok(Self {
            data: Cow::Borrowed(data),
            header,
            blocks: blocks_index,
            vars,
        })
    }

    /// Convert to an instance that owns its backing data.
    pub fn to_owned(&self) -> ParsedBom<'static> {
        ParsedBom {
            data: Cow::Owned(self.data.clone().into_owned()),
            header: self.header,
            blocks: self.blocks.clone(),
            vars: self.vars.clone(),
        }
    }

    /// Attempt to locate a named variable.
    pub fn find_variable(&self, name: &str) -> Result<&BomVar, Error> {
        self.vars
            .vars
            .iter()
            .find(|v| v.name == name)
            .ok_or_else(|| Error::NoVar(name.to_string()))
    }

    /// Attempt to resolve the [BomBlockBomInfo] for this instance.
    pub fn bom_info(&self) -> Result<BomBlockBomInfo, Error> {
        let var = self.find_variable("BomInfo")?;

        self.block_as_bom_info(var.block_index as _)
    }

    pub fn hl_index(&self) -> Result<Vec<BomPath>, Error> {
        let var = self.find_variable("HLIndex")?;
        let tree = self.block_as_tree(var.block_index as _)?;

        tree.bom_paths(self)
    }

    pub fn paths(&self) -> Result<Vec<BomPath>, Error> {
        let index = self.find_variable("Paths")?;
        let tree = self.block_as_tree(index.block_index as _)?;

        tree.bom_paths(self)
    }

    /// Resolve the Size64 tree.
    pub fn size64(&self) -> Result<Vec<BomPath>, Error> {
        let var = self.find_variable("Size64")?;
        let tree = self.block_as_tree(var.block_index as _)?;

        tree.bom_paths(self)
    }

    /// Resolve the V Index.
    pub fn vindex(&self) -> Result<Vec<BomPath>, Error> {
        let var = self.find_variable("VIndex")?;
        let index = self.block_as_vindex(var.block_index as _)?;
        let tree = index.tree(self)?;

        tree.bom_paths(self)
    }

    /// Resolve the raw data backing a block given a block index.
    pub fn block_data(&self, index: usize) -> Result<&[u8], Error> {
        let entry = self.blocks.blocks.get(index).ok_or(Error::BadIndex)?;

        Ok(&self.data[entry.file_offset as usize..(entry.file_offset + entry.length) as usize])
    }

    /// Attempt to resolve a block at an index as a [BomBlockBomInfo].
    pub fn block_as_bom_info(&self, index: usize) -> Result<BomBlockBomInfo, Error> {
        self.block_data(index)?.pread_with(0, scroll::BE)
    }

    /// Attempt to resolve a block at an index as a [BomBlockFile].
    pub fn block_as_file(&self, index: usize) -> Result<BomBlockFile<'_>, Error> {
        self.block_data(index)?.pread_with(0, scroll::BE)
    }

    /// Attempt to resolve a block at an index as a [BomBlockPathInfoIndex].
    pub fn block_as_path_info_index(&self, index: usize) -> Result<BomBlockPathInfoIndex, Error> {
        Ok(self.block_data(index)?.pread_with(0, scroll::BE)?)
    }

    /// Attempt to resolve a block at an index as a [BomBlockPathRecord].
    pub fn block_as_path_record(&self, index: usize) -> Result<BomBlockPathRecord, Error> {
        self.block_data(index)?.pread_with(0, scroll::BE)
    }

    /// Attempt to resolve a block at an index as a [BomBlockPathRecordPointer].
    pub fn block_as_path_record_pointer(
        &self,
        index: usize,
    ) -> Result<BomBlockPathRecordPointer, Error> {
        Ok(self.block_data(index)?.pread_with(0, scroll::BE)?)
    }

    /// Attempt to resolve a block at an index as a [BomBlockPaths].
    pub fn block_as_paths(&self, index: usize) -> Result<BomBlockPaths, Error> {
        let data = self.block_data(index)?;
        Ok(data.pread_with(0, scroll::BE)?)
    }

    /// Attempt to resolve a black at an index as a [BomBlockTree].
    pub fn block_as_tree(&self, index: usize) -> Result<BomBlockTree, Error> {
        let data = self.block_data(index)?;
        data.pread_with(0, scroll::BE)
    }

    /// Attempt to resolve a block at an index as a [BomBlockTreePointer].
    pub fn block_as_tree_pointer(&self, index: usize) -> Result<BomBlockTreePointer, Error> {
        Ok(self.block_data(index)?.pread_with(0, scroll::BE)?)
    }

    /// Attempt to resolve a block at an index as a [BomBlockVIndex].
    pub fn block_as_vindex(&self, index: usize) -> Result<BomBlockVIndex, Error> {
        Ok(self.block_data(index)?.pread_with(0, scroll::BE)?)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    const PYTHON_DATA: &[u8] = include_bytes!("testdata/python-applications.bom");

    #[test]
    fn parse_python() -> Result<(), Error> {
        let bom = crate::format::ParsedBom::parse(PYTHON_DATA)?;

        bom.bom_info()?;

        // Forces recursive parsing
        for _ in bom.hl_index()? {}
        for _ in bom.paths()? {}
        for _ in bom.size64()? {}
        for _ in bom.vindex()? {}

        let root = bom.paths()?.into_iter().find(|p| p.path() == ".").unwrap();
        assert_eq!(root.symbolic_mode(), "drwxr-xr-x");

        let readme = bom
            .paths()?
            .into_iter()
            .find(|p| p.path() == "./Python 3.9/ReadMe.rtf")
            .unwrap();
        assert_eq!(readme.symbolic_mode(), "-rw-r--r--");

        Ok(())
    }
}