apk/res/

table.rs

//! The resource table (`resources.arsc`).
//!
//! [`ResourceTable`] reads a table in place: parsing checks every chunk,
//! offset, and entry once, and lookups then borrow from the input. Dense,
//! sparse, 16-bit offset, and compact entries are understood, as are split
//! packages and type ID offsets. Tables are written only by the resource
//! compiler, in aapt2's dense layout.

use std::borrow::Cow;
use std::collections::BTreeSet;
use std::fmt;

use binrw::binrw;

use super::chunk::{Chunk, ChunkError, ChunkType, Chunks, Header, Put, read_padded, write_chunk};
use super::config::{Config, RawConfig};
use super::id::{ResourceId, ResourceLookup, ResourceName, ResourceType};
use super::string_pool::{Encoding, StringPool, StringPoolBuilder, StringPoolError};
use super::value::{RawValue, Value};

/// A malformed or unencodable resource table.
#[derive(Clone, Debug, Eq, PartialEq, thiserror::Error)]
#[non_exhaustive]
pub enum TableError {
    #[error(transparent)]
    Chunk(#[from] ChunkError),
    #[error(transparent)]
    StringPool(#[from] StringPoolError),
    #[error("package chunk precedes the table's value string pool")]
    MissingValuePool,
    #[error("resource table declares {expected} packages but contains {found} package chunks")]
    PackageCountMismatch { expected: u32, found: u32 },
    #[error("package ID {id} does not fit in a byte")]
    PackageIdOutOfRange { id: u32 },
    #[error("package string pool offset {offset:#x} is invalid")]
    PoolOffsetOutOfRange { offset: u32 },
    #[error("type ID {id} (offset by {offset}) is zero, too large, or declared twice")]
    InvalidTypeId { id: u8, offset: u32 },
    #[error("type {type_id} has no name in its package's type string pool")]
    UnnamedType { type_id: u8 },
    #[error("type {type_id} has entries but no preceding type spec")]
    TypeWithoutSpec { type_id: u8 },
    #[error("type {type_id} declares {count} entries, more than its chunk or a type can hold")]
    EntryCountOutOfRange { type_id: u8, count: u32 },
    #[error("sparse entries of type {type_id} are not in ascending order")]
    UnsortedSparseEntries { type_id: u8 },
    #[error("entry {index} of type {type_id} lies outside its type spec")]
    EntryOutsideSpec { type_id: u8, index: u16 },
    #[error("type {type_id} entries start at {offset:#x}, outside the chunk")]
    EntriesOutOfRange { type_id: u8, offset: u32 },
    #[error("entry {index} of type {type_id} is truncated or lies outside its chunk")]
    TruncatedEntry { type_id: u8, index: u16 },
    #[error("entry {index} of type {type_id} names key {key}, which is not in the key pool")]
    KeyOutOfRange { type_id: u8, index: u16, key: u32 },
    #[error("type `{ty}` has more than 65535 entries")]
    TooManyEntries { ty: ResourceType },
    #[error("package name {name:?} exceeds 127 UTF-16 code units")]
    PackageNameTooLong { name: String },
}

#[binrw]
#[brw(little)]
struct TableHeader {
    package_count: u32,
}

impl Header for TableHeader {
    const MIN_SIZE: usize = 4;
}

#[binrw]
#[brw(little)]
struct PackageHeader {
    id: u32,
    name: [u16; 128],
    type_strings: u32,
    last_public_type: u32,
    key_strings: u32,
    last_public_key: u32,
    /// Added in Android 7; older packages end before it.
    type_id_offset: u32,
}

impl Header for PackageHeader {
    const MIN_SIZE: usize = 4 + 256 + 16;
}

#[binrw]
#[brw(little)]
struct TypeSpecHeader {
    id: u8,
    res0: u8,
    types_count: u16,
    entry_count: u32,
}

impl Header for TypeSpecHeader {
    const MIN_SIZE: usize = 8;
}

/// `ResTable_type` up to its configuration, which has its own size field.
#[binrw]
#[brw(little)]
struct TypeHeader {
    id: u8,
    flags: u8,
    reserved: u16,
    entry_count: u32,
    entries_start: u32,
}

impl Header for TypeHeader {
    /// The fixed fields and the configuration's size field.
    const MIN_SIZE: usize = 12 + 4;
}

/// A `ResTable_type` header as written, with its configuration.
#[binrw::binwrite]
#[bw(little)]
struct TypeHeaderWithConfig {
    fixed: TypeHeader,
    config: RawConfig,
}

#[binrw]
#[brw(little)]
struct EntryHeader {
    size: u16,
    flags: u16,
    key: u32,
}

const TYPE_FLAG_SPARSE: u8 = 0x01;
const TYPE_FLAG_OFFSET16: u8 = 0x02;
const ENTRY_FLAG_COMPLEX: u16 = 0x0001;
const ENTRY_FLAG_COMPACT: u16 = 0x0008;
const NO_ENTRY: u32 = u32::MAX;
const SPEC_PUBLIC: u32 = 0x4000_0000;
/// Entry indices are 16 bits wide.
const MAX_ENTRIES: usize = 1 << 16;
// Specs can reserve every 16-bit ID; Android limits each configuration's count to 65535.
const MAX_CONFIG_ENTRIES: usize = u16::MAX as usize;

/// A parsed `resources.arsc`, borrowing from its bytes.
///
/// ```no_run
/// use apk::res::{ResourceTable, ResourceType};
///
/// let bytes = apk::Apk::open("app.apk")?.read("resources.arsc")?;
/// let table = ResourceTable::parse(&bytes)?;
/// let id = table.find(0x7f, ResourceType::String, "app_name").expect("app_name");
/// println!("{}", table.get(id).unwrap().default_value().unwrap());
/// # Ok::<(), apk::Error>(())
/// ```
#[derive(Clone, Debug)]
pub struct ResourceTable<'a> {
    strings: StringPool<'a>,
    packages: Vec<Package<'a>>,
}

/// A package (`ResTable_package`), typically `0x7f` for an app. Package
/// chunks with the same ID are merged.
#[derive(Clone, Debug)]
pub struct Package<'a> {
    id: u8,
    name: String,
    types: Vec<TypeSpec<'a>>,
}

/// All configurations of one resource type within a package.
#[derive(Clone, Debug)]
pub struct TypeSpec<'a> {
    id: u8,
    name: Cow<'a, str>,
    /// `ResTable_typeSpec` flags, one per entry.
    flags: &'a [[u8; 4]],
    configs: Vec<TypeConfig<'a>>,
}

/// The entries of one type for one configuration (`ResTable_type`).
#[derive(Clone, Debug)]
struct TypeConfig<'a> {
    config: Config,
    offsets: Offsets<'a>,
    /// The chunk from `entries_start` on.
    entries: &'a [u8],
    /// The key pool of the package chunk this configuration came from.
    keys: StringPool<'a>,
}

/// Where the entries of a [`TypeConfig`] start.
#[derive(Clone, Copy, Debug)]
enum Offsets<'a> {
    /// A byte offset per entry, `NO_ENTRY` when absent.
    Dense(&'a [[u8; 4]]),
    /// An offset in 4-byte words per entry, `0xffff` when absent.
    Offset16(&'a [[u8; 2]]),
    /// `(index, offset in words)` for the defined entries, by index.
    Sparse(&'a [[u8; 4]]),
}

impl<'a> Offsets<'a> {
    fn slots(self) -> usize {
        match self {
            Self::Dense(offsets) | Self::Sparse(offsets) => offsets.len(),
            Self::Offset16(offsets) => offsets.len(),
        }
    }

    /// The entry index and byte offset in `slot`, unless the slot is empty.
    fn slot(self, slot: usize) -> Option<(u16, usize)> {
        match self {
            Self::Dense(offsets) => {
                let offset = u32::from_le_bytes(offsets[slot]);
                (offset != NO_ENTRY).then_some((slot as u16, offset as usize))
            }
            Self::Offset16(offsets) => {
                let words = u16::from_le_bytes(offsets[slot]);
                (words != u16::MAX).then_some((slot as u16, usize::from(words) * 4))
            }
            Self::Sparse(pairs) => Some(sparse(pairs[slot])),
        }
    }

    /// Every defined entry: its index and byte offset.
    fn iter(self) -> impl Iterator<Item = (u16, usize)> + 'a {
        (0..self.slots()).filter_map(move |slot| self.slot(slot))
    }

    /// The byte offset of entry `index`, if it is defined.
    fn get(self, index: u16) -> Option<usize> {
        match self {
            Self::Sparse(pairs) => {
                let slot = pairs.binary_search_by_key(&index, |&pair| sparse(pair).0).ok()?;
                Some(sparse(pairs[slot]).1)
            }
            dense => {
                let slot = usize::from(index);
                (slot < dense.slots()).then(|| dense.slot(slot)).flatten().map(|(_, offset)| offset)
            }
        }
    }
}

/// A `ResTable_sparseTypeEntry`: an entry index and an offset in words.
fn sparse(pair: [u8; 4]) -> (u16, usize) {
    (u16::from_le_bytes([pair[0], pair[1]]), usize::from(u16::from_le_bytes([pair[2], pair[3]])) * 4)
}

/// A `ResTable_entry` and its value, read in place.
#[derive(Clone, Copy, Debug)]
enum RawEntry<'a> {
    Simple {
        key: u32,
        value: RawValue,
    },
    /// A style, attribute, array, or plural: `(name, value)` items.
    Bag {
        key: u32,
        parent: u32,
        items: &'a [[u8; 12]],
    },
}

impl<'a> RawEntry<'a> {
    fn read(bytes: &'a [u8]) -> Option<Self> {
        let header: EntryHeader = read_padded(bytes.get(..8)?);
        if header.flags & ENTRY_FLAG_COMPACT != 0 {
            // The key is in `size`, and the data type in the high byte of `flags`.
            let value = RawValue::new((header.flags >> 8) as u8, header.key);
            return Some(Self::Simple { key: header.size.into(), value });
        }
        if header.size < 8 {
            return None;
        }
        let body = bytes.get(usize::from(header.size)..)?;
        if header.flags & ENTRY_FLAG_COMPLEX == 0 {
            return Some(Self::Simple { key: header.key, value: RawValue::read(body)? });
        }
        let bag = bytes.get(8..16).filter(|_| header.size >= 16)?;
        let parent = u32::from_le_bytes(bag[..4].try_into().ok()?);
        let count = u32::from_le_bytes(bag[4..].try_into().ok()?);
        let items = body.as_chunks::<12>().0.get(..count as usize)?;
        Some(Self::Bag { key: header.key, parent, items })
    }

    fn key(self) -> u32 {
        match self {
            Self::Simple { key, .. } | Self::Bag { key, .. } => key,
        }
    }
}

/// A resource's value in one configuration.
#[derive(Clone, Debug, PartialEq)]
pub enum EntryValue<'a> {
    Simple(Value),
    /// A style, attribute, array, or plural.
    Bag(Bag<'a>),
}

impl fmt::Display for EntryValue<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Simple(value) => write!(f, "{value}"),
            Self::Bag(bag) => write!(f, "{bag}"),
        }
    }
}

/// A bag of keyed values, read in place: items are decoded only as they
/// are iterated.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Bag<'a> {
    parent: u32,
    items: &'a [[u8; 12]],
    strings: StringPool<'a>,
}

impl<'a> Bag<'a> {
    /// The bag this one inherits from, such as a style's parent.
    pub fn parent(&self) -> Option<ResourceId> {
        (self.parent != 0).then_some(ResourceId(self.parent))
    }

    pub fn len(&self) -> usize {
        self.items.len()
    }

    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    /// Each item's key (an attribute or index) and value.
    pub fn items(&self) -> impl ExactSizeIterator<Item = (ResourceId, Value)> + 'a {
        let strings = self.strings;
        self.items.iter().map(move |item| {
            let (key, value) = item.split_at(4);
            let key = ResourceId(u32::from_le_bytes(key.try_into().expect("four bytes")));
            (key, decode(strings, RawValue::read(value).expect("items are value-sized")))
        })
    }
}

impl fmt::Display for Bag<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("{")?;
        if let Some(parent) = self.parent() {
            write!(f, "parent={parent} ")?;
        }
        for (i, (key, value)) in self.items().enumerate() {
            write!(f, "{}{key}={value}", if i == 0 { "" } else { ", " })?;
        }
        f.write_str("}")
    }
}

/// Decodes a value whose strings index `strings`. A string missing from the
/// pool stays raw.
fn decode(strings: StringPool<'_>, raw: RawValue) -> Value {
    let string = |index| strings.get(index).map(Cow::into_owned).ok_or(());
    Value::from_raw(raw, string).unwrap_or(Value::Raw { data_type: raw.data_type, data: raw.data })
}

impl<'a> ResourceTable<'a> {
    /// Parses and checks a `resources.arsc` file.
    pub fn parse(bytes: &'a [u8]) -> Result<Self, TableError> {
        let root = Chunk::parse_root(bytes, ChunkType::TABLE)?;
        let header = root.header::<TableHeader>()?;
        let mut package_count = 0;
        let mut strings = None;
        let mut packages: Vec<Package<'a>> = Vec::new();
        for child in root.children() {
            let child = child?;
            match child.ty {
                ChunkType::STRING_POOL if strings.is_none() => strings = Some(StringPool::parse(&child)?),
                ChunkType::TABLE_PACKAGE if strings.is_none() => return Err(TableError::MissingValuePool),
                ChunkType::TABLE_PACKAGE => {
                    parse_package(&child, &mut packages)?;
                    package_count += 1;
                }
                _ => {}
            }
        }
        if package_count != header.package_count {
            return Err(TableError::PackageCountMismatch { expected: header.package_count, found: package_count });
        }
        Ok(Self { strings: strings.unwrap_or_default(), packages })
    }

    pub fn packages(&self) -> &[Package<'a>] {
        &self.packages
    }

    /// The resource with ID `id`, if any configuration defines it.
    pub fn get(&self, id: ResourceId) -> Option<Resource<'_, 'a>> {
        let package = self.packages.iter().find(|p| p.id == id.package())?;
        let spec = package.types.iter().find(|t| t.id == id.type_id())?;
        let resource = Resource { table: self, package, spec, index: id.entry() };
        resource.entries().next().is_some().then_some(resource)
    }

    /// Looks up a resource by type and name in package `package_id`.
    pub fn find(&self, package_id: u8, ty: ResourceType, name: &str) -> Option<ResourceId> {
        let package = self.packages.iter().find(|p| p.id == package_id)?;
        let spec = package.types.iter().find(|t| t.name == ty.as_str())?;
        let index = spec.configs.iter().find_map(|config| {
            config.offsets.iter().find_map(|(index, offset)| {
                let entry = RawEntry::read(config.entries.get(offset..)?)?;
                config.keys.equals(entry.key(), name).then_some(index)
            })
        })?;
        Some(ResourceId::new(package.id, spec.id, index))
    }

    /// Every defined resource, by package, type, and entry.
    pub fn resources(&self) -> impl Iterator<Item = Resource<'_, 'a>> {
        self.packages.iter().flat_map(move |package| {
            package.types.iter().flat_map(move |spec| {
                // Indices fit in 16 bits: specs hold at most `MAX_ENTRIES`.
                let indices = (0..spec.entry_count()).map(|index| index as u16);
                let defined = indices.filter(|&index| spec.configs.iter().any(|c| c.offsets.get(index).is_some()));
                defined.map(move |index| Resource { table: self, package, spec, index })
            })
        })
    }
}

impl ResourceLookup for ResourceTable<'_> {
    fn lookup(&self, ty: ResourceType, name: &ResourceName) -> Option<ResourceId> {
        self.find(ResourceId::APP_PACKAGE, ty, name.as_ref())
    }
}

impl fmt::Display for ResourceTable<'_> {
    /// Lists every resource, in the spirit of `aapt2 dump resources`.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for resource in self.resources() {
            writeln!(f, "{} {resource}", resource.id())?;
            for (config, value) in resource.values() {
                match config.is_default() {
                    true => writeln!(f, "  (default): {value}")?,
                    false => writeln!(f, "  {config}: {value}")?,
                }
            }
        }
        Ok(())
    }
}

impl<'a> Package<'a> {
    pub fn id(&self) -> u8 {
        self.id
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    /// The package's types, by ID.
    pub fn types(&self) -> &[TypeSpec<'a>] {
        &self.types
    }
}

impl TypeSpec<'_> {
    pub fn id(&self) -> u8 {
        self.id
    }

    /// The type name, e.g. `string`.
    pub fn name(&self) -> &str {
        &self.name
    }

    /// The number of entry IDs in this type.
    pub fn entry_count(&self) -> usize {
        self.flags.len()
    }

    /// Whether entry `index` is public (declared in `public.xml`).
    pub fn is_public(&self, index: u16) -> bool {
        self.flags.get(usize::from(index)).is_some_and(|&flags| u32::from_le_bytes(flags) & SPEC_PUBLIC != 0)
    }

    /// The configurations this type has values for.
    pub fn configs(&self) -> impl Iterator<Item = &Config> {
        self.configs.iter().map(|c| &c.config)
    }
}

/// One resource of a [`ResourceTable`], across all its configurations.
#[derive(Clone, Copy, Debug)]
pub struct Resource<'t, 'a> {
    table: &'t ResourceTable<'a>,
    package: &'t Package<'a>,
    spec: &'t TypeSpec<'a>,
    index: u16,
}

impl<'t, 'a> Resource<'t, 'a> {
    pub fn id(&self) -> ResourceId {
        ResourceId::new(self.package.id, self.spec.id, self.index)
    }

    /// The entry name, from the first configuration that defines it.
    pub fn name(&self) -> Cow<'a, str> {
        let name = self.entries().next().and_then(|(config, entry)| config.keys.get(entry.key()));
        name.unwrap_or_default()
    }

    pub fn type_name(&self) -> &'t str {
        &self.spec.name
    }

    pub fn is_public(&self) -> bool {
        self.spec.is_public(self.index)
    }

    fn entries(&self) -> impl Iterator<Item = (&'t TypeConfig<'a>, RawEntry<'a>)> + 't {
        let index = self.index;
        self.spec.configs.iter().filter_map(move |c| Some((c, entry_at(c, index)?)))
    }

    /// The defined values, one per configuration.
    pub fn values(&self) -> impl Iterator<Item = (&'t Config, EntryValue<'a>)> + 't {
        let strings = self.table.strings;
        self.entries().map(move |(config, entry)| (&config.config, entry_value(strings, entry)))
    }

    /// The value for exactly `config`, if defined.
    pub fn value(&self, config: &Config) -> Option<EntryValue<'a>> {
        let (_, entry) = self.entries().find(|(c, _)| c.config == *config)?;
        Some(entry_value(self.table.strings, entry))
    }

    /// The value in the default configuration.
    pub fn default_value(&self) -> Option<EntryValue<'a>> {
        self.value(&Config::default())
    }
}

impl fmt::Display for Resource<'_, '_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}:{}/{}", self.package.name, self.type_name(), self.name())
    }
}

/// Entry `index` of `config`; entries were checked when the table was parsed.
fn entry_at<'a>(config: &TypeConfig<'a>, index: u16) -> Option<RawEntry<'a>> {
    RawEntry::read(config.entries.get(config.offsets.get(index)?..)?)
}

fn entry_value<'a>(strings: StringPool<'a>, entry: RawEntry<'a>) -> EntryValue<'a> {
    match entry {
        RawEntry::Simple { value, .. } => EntryValue::Simple(decode(strings, value)),
        RawEntry::Bag { parent, items, .. } => EntryValue::Bag(Bag { parent, items, strings }),
    }
}

/// Parses one package chunk, merging it into `packages` by ID.
fn parse_package<'a>(chunk: &Chunk<'a>, packages: &mut Vec<Package<'a>>) -> Result<(), TableError> {
    let header: PackageHeader = chunk.header()?;
    let id = u8::try_from(header.id).map_err(|_| TableError::PackageIdOutOfRange { id: header.id })?;
    let header_end = chunk.bytes.len() - chunk.body.len();
    let pool_at = |offset: u32| -> Result<StringPool<'a>, TableError> {
        let bytes = chunk.bytes.get(offset as usize..).filter(|_| offset as usize >= header_end);
        let pool = Chunks::new(bytes.ok_or(TableError::PoolOffsetOutOfRange { offset })?).next();
        Ok(StringPool::parse(&pool.ok_or(ChunkError::Missing)??)?)
    };
    let (type_names, keys) = (pool_at(header.type_strings)?, pool_at(header.key_strings)?);
    let package = match packages.iter().position(|p| p.id == id) {
        Some(index) => &mut packages[index],
        None => {
            let name_len = header.name.iter().position(|&c| c == 0).unwrap_or(header.name.len());
            let name = String::from_utf16_lossy(&header.name[..name_len]);
            packages.push(Package { id, name, types: Vec::new() });
            packages.last_mut().expect("just pushed")
        }
    };
    for child in chunk.children() {
        let child = child?;
        match child.ty {
            ChunkType::TABLE_TYPE_SPEC => {
                let spec: TypeSpecHeader = child.header()?;
                // Type IDs in a chunk are relative to the package's offset;
                // the type name pool is indexed by the relative ID.
                let invalid = TableError::InvalidTypeId { id: spec.id, offset: header.type_id_offset };
                let type_id = u32::from(spec.id)
                    .checked_add(header.type_id_offset)
                    .and_then(|id| u8::try_from(id).ok())
                    .filter(|_| spec.id != 0)
                    .ok_or(invalid.clone())?;
                if package.types.iter().any(|t| t.id == type_id) {
                    return Err(invalid);
                }
                let name = type_names.get(u32::from(spec.id) - 1).ok_or(TableError::UnnamedType { type_id })?;
                let count = spec.entry_count as usize;
                let overflow = TableError::EntryCountOutOfRange { type_id, count: spec.entry_count };
                let flags = child.body.as_chunks::<4>().0.get(..count).filter(|_| count <= MAX_ENTRIES);
                package.types.push(TypeSpec { id: type_id, name, flags: flags.ok_or(overflow)?, configs: Vec::new() });
            }
            ChunkType::TABLE_TYPE => {
                let type_header: TypeHeader = child.header()?;
                let missing = TableError::TypeWithoutSpec { type_id: type_header.id };
                let type_id = u32::from(type_header.id)
                    .checked_add(header.type_id_offset)
                    .and_then(|id| u8::try_from(id).ok())
                    .filter(|_| type_header.id != 0)
                    .ok_or(missing.clone())?;
                let spec = package.types.iter_mut().find(|t| t.id == type_id).ok_or(missing)?;
                let config = parse_type(&child, &type_header, type_id, keys)?;
                check_entries(&config, spec, type_id)?;
                spec.configs.push(config);
            }
            _ => {}
        }
    }
    package.types.sort_by_key(|t| t.id);
    Ok(())
}

fn parse_type<'a>(
    chunk: &Chunk<'a>,
    header: &TypeHeader,
    type_id: u8,
    keys: StringPool<'a>,
) -> Result<TypeConfig<'a>, TableError> {
    let config = Config::read(&chunk.header[12..]);
    let count = header.entry_count as usize;
    let overflow = TableError::EntryCountOutOfRange { type_id, count: header.entry_count };
    if count > MAX_CONFIG_ENTRIES {
        return Err(overflow);
    }
    let offsets = if header.flags & TYPE_FLAG_SPARSE != 0 {
        let pairs = chunk.body.as_chunks::<4>().0.get(..count).ok_or(overflow)?;
        if !pairs.windows(2).all(|w| sparse(w[0]).0 < sparse(w[1]).0) {
            return Err(TableError::UnsortedSparseEntries { type_id });
        }
        Offsets::Sparse(pairs)
    } else if header.flags & TYPE_FLAG_OFFSET16 != 0 {
        Offsets::Offset16(chunk.body.as_chunks::<2>().0.get(..count).ok_or(overflow)?)
    } else {
        Offsets::Dense(chunk.body.as_chunks::<4>().0.get(..count).ok_or(overflow)?)
    };
    let offset_width =
        if header.flags & TYPE_FLAG_OFFSET16 != 0 && header.flags & TYPE_FLAG_SPARSE == 0 { 2 } else { 4 };
    let metadata_end = chunk.bytes.len() - chunk.body.len() + count * offset_width;
    let entries = chunk
        .bytes
        .get(header.entries_start as usize..)
        .filter(|_| header.entries_start as usize >= metadata_end)
        .ok_or(TableError::EntriesOutOfRange { type_id, offset: header.entries_start })?;
    Ok(TypeConfig { config, offsets, entries, keys })
}

/// Checks that every entry of `config` is inside its spec and chunk and
/// names a key that exists, in constant time per entry. (String values are
/// checked when they are read.)
fn check_entries(config: &TypeConfig<'_>, spec: &TypeSpec<'_>, type_id: u8) -> Result<(), TableError> {
    for (index, offset) in config.offsets.iter() {
        if usize::from(index) >= spec.entry_count() {
            return Err(TableError::EntryOutsideSpec { type_id, index });
        }
        let entry = config.entries.get(offset..).and_then(RawEntry::read);
        let key = entry.ok_or(TableError::TruncatedEntry { type_id, index })?.key();
        if !config.keys.contains(key) {
            return Err(TableError::KeyOutOfRange { type_id, index, key });
        }
    }
    Ok(())
}

/// One type of a table being written: its entries' names and, per
/// configuration, their encoded values.
pub(crate) struct TypeData<'a> {
    pub ty: ResourceType,
    pub entries: Vec<EntryData<'a>>,
}

pub(crate) struct EntryData<'a> {
    pub name: &'a str,
    pub values: Vec<(Config, RawValue)>,
}

/// Writes a one-package table in aapt2's dense layout. Type IDs are
/// assigned in order from 1; string values index `strings`.
pub(crate) fn write(
    package_id: u8,
    package_name: &str,
    strings: &StringPoolBuilder<'_>,
    types: &[TypeData<'_>],
) -> Result<Vec<u8>, TableError> {
    let mut type_names = StringPoolBuilder::default();
    let mut keys = StringPoolBuilder::default();
    let mut body = Vec::new();
    for (index, data) in types.iter().enumerate() {
        type_names.push(data.ty.as_str());
        write_type(index as u8 + 1, data, &mut keys, &mut body)?;
    }
    let mut pools = Vec::new();
    type_names.write(&mut pools, Encoding::Utf16)?;
    let key_offset = pools.len();
    keys.write(&mut pools, Encoding::Utf8)?;

    let mut name = [0u16; 128];
    let units: Vec<u16> = package_name.encode_utf16().collect();
    if units.len() >= name.len() {
        return Err(TableError::PackageNameTooLong { name: package_name.to_owned() });
    }
    name[..units.len()].copy_from_slice(&units);
    const HEADER_SIZE: u32 = 288;
    let package = PackageHeader {
        id: package_id.into(),
        name,
        type_strings: HEADER_SIZE,
        last_public_type: types.len() as u32,
        key_strings: HEADER_SIZE + key_offset as u32,
        last_public_key: keys.len() as u32,
        type_id_offset: 0,
    };
    let mut out = Vec::new();
    write_chunk(&mut out, ChunkType::TABLE, &TableHeader { package_count: 1 }, |out| {
        strings.write(out, Encoding::Utf8)?;
        write_chunk(out, ChunkType::TABLE_PACKAGE, &package, |out| {
            out.extend_from_slice(&pools);
            out.extend_from_slice(&body);
            Ok::<_, TableError>(())
        })
    })?;
    Ok(out)
}

fn write_type<'a>(
    id: u8,
    data: &TypeData<'a>,
    keys: &mut StringPoolBuilder<'a>,
    out: &mut Vec<u8>,
) -> Result<(), TableError> {
    let count = data.entries.len();
    if count > MAX_CONFIG_ENTRIES {
        return Err(TableError::TooManyEntries { ty: data.ty });
    }
    let configs: BTreeSet<&Config> = data.entries.iter().flat_map(|e| e.values.iter().map(|(c, _)| c)).collect();
    let spec = TypeSpecHeader { id, res0: 0, types_count: configs.len() as u16, entry_count: count as u32 };
    write_chunk(out, ChunkType::TABLE_TYPE_SPEC, &spec, |out| {
        // Each entry's flags: the configuration axes its values vary along.
        for entry in &data.entries {
            out.put_u32(entry.values.iter().fold(0, |flags, (config, _)| flags | config.change_flags()));
        }
        Ok::<_, TableError>(())
    })?;
    let keys: Vec<u32> = data.entries.iter().map(|e| keys.intern(e.name)).collect();
    for config in configs {
        let mut offsets = Vec::with_capacity(count);
        let mut entries = Vec::new();
        for (entry, &key) in data.entries.iter().zip(&keys) {
            let Some((_, value)) = entry.values.iter().find(|(c, _)| c == config) else {
                offsets.put_u32(NO_ENTRY);
                continue;
            };
            offsets.put_u32(u32::try_from(entries.len()).map_err(|_| ChunkError::TooLarge)?);
            entries.put(&EntryHeader { size: 8, flags: 0, key });
            entries.put(value);
        }
        let entries_start = (8 + 12 + Config::SIZE + offsets.len()) as u32;
        let fixed = TypeHeader { id, flags: 0, reserved: 0, entry_count: count as u32, entries_start };
        write_chunk(out, ChunkType::TABLE_TYPE, &TypeHeaderWithConfig { fixed, config: config.0 }, |out| {
            out.extend_from_slice(&offsets);
            out.extend_from_slice(&entries);
            Ok::<_, TableError>(())
        })?;
    }
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::res::value::data_type;

    /// Two strings (one localized) and a boolean resource.
    fn sample() -> Vec<u8> {
        let fr: Config = "fr".parse().unwrap();
        let mut strings = StringPoolBuilder::default();
        let mut string = |s| RawValue::new(data_type::STRING, strings.intern(s));
        let types = vec![
            TypeData {
                ty: ResourceType::String,
                entries: vec![
                    EntryData {
                        name: "app_name",
                        values: vec![(Config::default(), string("Hello")), (fr, string("Bonjour"))],
                    },
                    EntryData { name: "other", values: vec![(Config::default(), string("x"))] },
                ],
            },
            TypeData {
                ty: ResourceType::Bool,
                entries: vec![EntryData {
                    name: "enabled",
                    values: vec![(Config::default(), RawValue::new(data_type::INT_BOOLEAN, u32::MAX))],
                }],
            },
        ];
        write(0x7f, "org.example", &strings, &types).unwrap()
    }

    #[test]
    fn writes_and_reads_back() {
        let bytes = sample();
        let table = ResourceTable::parse(&bytes).unwrap();
        let id = table.find(0x7f, ResourceType::String, "app_name").unwrap();
        assert_eq!(id, ResourceId(0x7f01_0000));
        let resource = table.get(id).unwrap();
        assert_eq!(resource.to_string(), "org.example:string/app_name");
        assert!(matches!(resource.name(), Cow::Borrowed("app_name")));
        assert_eq!(resource.value(&"fr".parse().unwrap()), Some(EntryValue::Simple("Bonjour".into())));
        assert_eq!(resource.default_value(), Some(EntryValue::Simple("Hello".into())));
        let enabled = table.find(0x7f, ResourceType::Bool, "enabled").unwrap();
        assert_eq!(table.get(enabled).unwrap().default_value(), Some(EntryValue::Simple(Value::Bool(true))));
        assert_eq!(table.resources().count(), 3);
        assert!(table.get(ResourceId(0x7f01_0002)).is_none());
    }

    #[test]
    fn dense_writer_respects_androids_16_bit_entry_count() {
        let data = TypeData {
            ty: ResourceType::String,
            entries: (0..65_536).map(|_| EntryData { name: "reserved", values: Vec::new() }).collect(),
        };
        assert_eq!(
            write(0x7f, "org.example", &StringPoolBuilder::default(), &[data]),
            Err(TableError::TooManyEntries { ty: ResourceType::String })
        );
    }

    #[test]
    fn entries_outside_their_type_spec_are_rejected() {
        let mut bytes = sample();
        // Shrink the first type spec (`string`, two entries) to one entry.
        let spec = bytes.windows(4).position(|w| w == [0x02, 0x02, 0x10, 0x00]).unwrap();
        bytes[spec + 12..spec + 16].copy_from_slice(&1u32.to_le_bytes());
        assert!(matches!(ResourceTable::parse(&bytes), Err(TableError::EntryOutsideSpec { type_id: 1, index: 1 })));
    }

    #[test]
    fn entries_cannot_overlap_type_metadata() {
        let original = sample();
        let root = Chunk::parse_root(&original, ChunkType::TABLE).unwrap();
        let package = root.children().map(Result::unwrap).find(|c| c.ty == ChunkType::TABLE_PACKAGE).unwrap();
        let ty = package.children().map(Result::unwrap).find(|c| c.ty == ChunkType::TABLE_TYPE).unwrap();
        let at = ty.bytes.as_ptr() as usize - original.as_ptr() as usize;
        for offset in [0u32, 8, 84, 88] {
            let mut bytes = original.clone();
            bytes[at + 16..at + 20].copy_from_slice(&offset.to_le_bytes());
            assert!(matches!(ResourceTable::parse(&bytes), Err(TableError::EntriesOutOfRange { .. })), "{offset}");
        }
    }

    #[test]
    fn simple_entry_headers_must_cover_their_fixed_fields() {
        for size in 0u16..8 {
            let mut bytes = vec![0; 16];
            bytes[..2].copy_from_slice(&size.to_le_bytes());
            assert!(RawEntry::read(&bytes).is_none(), "{size}");
        }
    }

    #[test]
    fn type_id_offsets_shift_ids_but_not_names() {
        let mut bytes = sample();
        let package = bytes.windows(4).position(|w| w == [0x00, 0x02, 0x20, 0x01]).unwrap();
        // typeIdOffset is the package header's last field.
        bytes[package + 284..package + 288].copy_from_slice(&2u32.to_le_bytes());
        let table = ResourceTable::parse(&bytes).unwrap();
        let types: Vec<(u8, &str)> = table.packages()[0].types().iter().map(|t| (t.id(), t.name())).collect();
        assert_eq!(types, [(3, "string"), (4, "bool")]);
        assert_eq!(table.find(0x7f, ResourceType::String, "app_name"), Some(ResourceId(0x7f03_0000)));
    }

    #[test]
    fn mandatory_headers_must_be_present() {
        let empty_table = [0x02, 0x00, 0x08, 0x00, 0x08, 0x00, 0x00, 0x00];
        assert!(matches!(
            ResourceTable::parse(&empty_table),
            Err(TableError::Chunk(ChunkError::HeaderTooShort { size: 8, min: 12, .. }))
        ));
    }

    #[test]
    fn truncated_tables_fail_cleanly() {
        let bytes = sample();
        for len in 0..bytes.len() {
            let mut truncated = bytes[..len].to_vec();
            if truncated.len() >= 8 {
                // Keep the outer size consistent so inner chunks are exercised.
                let size = truncated.len() as u32;
                truncated[4..8].copy_from_slice(&size.to_le_bytes());
            }
            assert!(ResourceTable::parse(&truncated).is_err(), "truncation at {len} parsed");
        }
    }

    #[test]
    fn declared_packages_must_exist() {
        let mut bytes = sample();
        bytes[8..12].copy_from_slice(&2u32.to_le_bytes());
        assert!(matches!(
            ResourceTable::parse(&bytes),
            Err(TableError::PackageCountMismatch { expected: 2, found: 1 })
        ));
    }
}