hadris_iso/write/

mod.rs

use alloc::{collections::BTreeMap, sync::Arc};
use core::fmt;

pub mod estimator;
/// APIs for writer.
pub mod writer;

use super::super::boot::{
    BootCatalog, BootInfoTable, BootSectionEntry, ElToritoWriter, Grub2BootInfoTable, PlatformId,
};
use super::super::directory::{DirectoryRecord, DirectoryRef, FileFlags};
use super::super::io::{self, Read, Seek, SeekFrom, Write};
use super::super::io::{IsoCursor, LogicalSector};
use super::super::path::PathTableRef;
use super::super::read::PathSeparator;
use super::super::rrip::{RripBuilder, RripOptions};
use super::super::susp::SplitSu;
use super::super::volume::{
    BootRecordVolumeDescriptor, PrimaryVolumeDescriptor, SupplementaryVolumeDescriptor,
    VolumeDescriptor, VolumeDescriptorHeader, VolumeDescriptorList, VolumeDescriptorType,
};
use crate::file::EntryType;
use crate::joliet::JolietLevel;
use crate::types::{Charset, IsoStr};
use hadris_common::types::{
    endian::{Endian, EndianType},
    number::U32,
};
use hadris_part::{
    GptDisk, GptDiskWriteExt, Le,
    gpt::{GptPartitionEntry, Guid},
    hybrid::HybridMbrBuilder,
    mbr::{Chs, MasterBootRecord, MbrPartition, MbrPartitionType},
};
use options::PartitionScheme;
use writer::{DirectoryRelocation, PathTableWriter, WrittenDirectory, WrittenFile, WrittenFiles};

use alloc::{collections::VecDeque, string::String, vec, vec::Vec};

/// APIs for options.
pub mod options;
use options::IsoFormatOptions;

#[derive(Debug, thiserror::Error)]
/// Identifies a FileConversionError value.
pub enum FileConversionError {
    #[error("I/O error: {0}")]
    /// The `Io` variant.
    Io(#[from] std::io::Error),
    #[error("Path {0:?} is not a valid UTF-8 string")]
    /// The `InvalidUtf8Path` variant.
    InvalidUtf8Path(std::path::PathBuf),
    #[error("Unsupported filesystem entry type at {0:?}")]
    /// The `UnsupportedFileType` variant.
    UnsupportedFileType(std::path::PathBuf),
}

/// A compact input tree for callers that do not need per-entry metadata.
///
/// [`InputTree`] is the richer model for Rock Ridge metadata and host
/// filesystem imports. Both models are accepted by [`IsoImageWriter::create`].
pub struct InputFiles {
    /// Separator used by paths referenced from writer options.
    pub path_separator: PathSeparator,
    /// Root-level files and directories.
    pub files: Vec<File>,
}

#[derive(Clone, PartialEq, Eq)]
/// A file or directory in the compact [`InputFiles`] model.
pub enum File {
    /// The `File` variant.
    File {
        /// The `name` field.
        name: Arc<String>,
        /// The `contents` field.
        contents: Vec<u8>,
    },
    /// The `Directory` variant.
    Directory {
        /// The `name` field.
        name: Arc<String>,
        /// The `children` field.
        children: Vec<File>,
    },
}

impl core::fmt::Debug for File {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut dbg = f.debug_struct("File");
        match self {
            Self::Directory { name, children } => {
                dbg.field("name", name);
                dbg.field("children", children);
            }
            Self::File { name, contents } => {
                dbg.field("name", name);
                dbg.field("data_len", &contents.len());
            }
        }
        dbg.finish()
    }
}

impl File {
    /// Performs the `name` operation.
    pub fn name(&self) -> Arc<String> {
        match self {
            File::File { name, .. } => name.clone(),
            File::Directory { name, .. } => name.clone(),
        }
    }
}

/// A metadata-aware tree used to create an ISO image.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct InputTree {
    /// The `path_separator` field.
    pub path_separator: PathSeparator,
    /// The `entries` field.
    pub entries: Vec<InputEntry>,
}

/// Optional POSIX metadata for an input entry.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct InputMetadata {
    /// The `mode` field.
    pub mode: Option<u32>,
    /// The `uid` field.
    pub uid: Option<u32>,
    /// The `gid` field.
    pub gid: Option<u32>,
    /// Creation time as seconds since the Unix epoch.
    pub created: Option<i64>,
    /// Modification time as seconds since the Unix epoch.
    pub modified: Option<i64>,
    /// Access time as seconds since the Unix epoch.
    pub accessed: Option<i64>,
}

/// The data represented by an [`InputEntry`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum InputEntryKind {
    /// The `File` variant.
    File(Vec<u8>),
    /// The `Directory` variant.
    Directory(Vec<InputEntry>),
    /// The `Symlink` variant.
    Symlink(String),
    /// A POSIX character device.
    CharacterDevice {
        /// Device-class identifier.
        major: u32,
        /// Device identifier within the class.
        minor: u32,
    },
    /// A POSIX block device.
    BlockDevice {
        /// Device-class identifier.
        major: u32,
        /// Device identifier within the class.
        minor: u32,
    },
}

/// A named input entry and its optional host metadata.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct InputEntry {
    /// The `name` field.
    pub name: Arc<String>,
    /// The `kind` field.
    pub kind: InputEntryKind,
    /// The `metadata` field.
    pub metadata: InputMetadata,
}

impl InputEntry {
    /// Performs the `file` operation.
    pub fn file(name: impl Into<String>, contents: impl Into<Vec<u8>>) -> Self {
        Self::new(name, InputEntryKind::File(contents.into()))
    }

    /// Performs the `directory` operation.
    pub fn directory(name: impl Into<String>, children: Vec<Self>) -> Self {
        Self::new(name, InputEntryKind::Directory(children))
    }

    /// Performs the `symlink` operation.
    pub fn symlink(name: impl Into<String>, target: impl Into<String>) -> Self {
        Self::new(name, InputEntryKind::Symlink(target.into()))
    }

    /// Performs the `character_device` operation.
    pub fn character_device(name: impl Into<String>, major: u32, minor: u32) -> Self {
        Self::new(name, InputEntryKind::CharacterDevice { major, minor })
    }

    /// Performs the `block_device` operation.
    pub fn block_device(name: impl Into<String>, major: u32, minor: u32) -> Self {
        Self::new(name, InputEntryKind::BlockDevice { major, minor })
    }

    /// Performs the `with_metadata` operation.
    pub fn with_metadata(mut self, metadata: InputMetadata) -> Self {
        self.metadata = metadata;
        self
    }

    /// Performs the `name` operation.
    pub fn name(&self) -> Arc<String> {
        self.name.clone()
    }

    fn new(name: impl Into<String>, kind: InputEntryKind) -> Self {
        Self {
            name: Arc::new(name.into()),
            kind,
            metadata: InputMetadata::default(),
        }
    }
}

impl InputTree {
    /// Performs the `new` operation.
    pub fn new(path_separator: PathSeparator, entries: Vec<InputEntry>) -> Self {
        Self {
            path_separator,
            entries,
        }
    }

    /// Performs the `from_fs` operation.
    pub fn from_fs(
        root_path: &std::path::Path,
        path_separator: PathSeparator,
    ) -> core::result::Result<Self, FileConversionError> {
        if !root_path.is_dir() {
            return Err(FileConversionError::Io(std::io::Error::new(
                std::io::ErrorKind::InvalidInput,
                alloc::format!("Root path '{root_path:?}' is not a directory"),
            )));
        }
        Ok(Self::new(
            path_separator,
            read_input_directory_recursively(root_path)?,
        ))
    }
}

impl From<InputFiles> for InputTree {
    fn from(value: InputFiles) -> Self {
        fn convert(file: File) -> InputEntry {
            match file {
                File::File { name, contents } => InputEntry {
                    name,
                    kind: InputEntryKind::File(contents),
                    metadata: InputMetadata::default(),
                },
                File::Directory { name, children } => InputEntry {
                    name,
                    kind: InputEntryKind::Directory(children.into_iter().map(convert).collect()),
                    metadata: InputMetadata::default(),
                },
            }
        }
        Self::new(
            value.path_separator,
            value.files.into_iter().map(convert).collect(),
        )
    }
}

fn system_time_seconds(value: std::io::Result<std::time::SystemTime>) -> Option<i64> {
    value
        .ok()?
        .duration_since(std::time::UNIX_EPOCH)
        .ok()
        .and_then(|duration| i64::try_from(duration.as_secs()).ok())
}

fn read_input_directory_recursively(
    current_path: &std::path::Path,
) -> core::result::Result<Vec<InputEntry>, FileConversionError> {
    use alloc::string::ToString;
    let mut children = Vec::new();
    for entry in std::fs::read_dir(current_path)? {
        let entry = entry?;
        let path = entry.path();
        let name = path
            .file_name()
            .and_then(|value| value.to_str())
            .ok_or_else(|| FileConversionError::InvalidUtf8Path(path.clone()))?
            .to_string();
        let fs_metadata = std::fs::symlink_metadata(&path)?;
        let file_type = fs_metadata.file_type();
        let mut metadata = InputMetadata {
            created: system_time_seconds(fs_metadata.created()),
            modified: system_time_seconds(fs_metadata.modified()),
            accessed: system_time_seconds(fs_metadata.accessed()),
            ..InputMetadata::default()
        };
        #[cfg(unix)]
        {
            use std::os::unix::fs::MetadataExt;
            metadata.mode = Some(fs_metadata.mode() & 0o7777);
            metadata.uid = Some(fs_metadata.uid());
            metadata.gid = Some(fs_metadata.gid());
        }
        let kind = if file_type.is_file() {
            InputEntryKind::File(std::fs::read(&path)?)
        } else if file_type.is_dir() {
            InputEntryKind::Directory(read_input_directory_recursively(&path)?)
        } else if file_type.is_symlink() {
            let target = std::fs::read_link(&path)?;
            InputEntryKind::Symlink(
                target
                    .to_str()
                    .ok_or_else(|| FileConversionError::InvalidUtf8Path(target.clone()))?
                    .to_string(),
            )
        } else {
            #[cfg(unix)]
            {
                use std::os::unix::fs::{FileTypeExt, MetadataExt};
                let device = fs_metadata.rdev();
                let major = ((device >> 8) & 0xfff) | ((device >> 32) & 0xfffff000);
                let minor = (device & 0xff) | ((device >> 12) & 0xffffff00);
                if file_type.is_char_device() {
                    InputEntryKind::CharacterDevice {
                        major: major as u32,
                        minor: minor as u32,
                    }
                } else if file_type.is_block_device() {
                    InputEntryKind::BlockDevice {
                        major: major as u32,
                        minor: minor as u32,
                    }
                } else {
                    return Err(FileConversionError::UnsupportedFileType(path));
                }
            }
            #[cfg(not(unix))]
            return Err(FileConversionError::UnsupportedFileType(path));
        };
        children.push(InputEntry {
            name: Arc::new(name),
            kind,
            metadata,
        });
    }
    children.sort_by_key(|entry| entry.name.to_ascii_lowercase());
    Ok(children)
}

fn validate_input_tree(tree: &InputTree, rrip: Option<&RripOptions>) -> io::Result<()> {
    fn visit(
        entries: &[InputEntry],
        rrip: Option<&RripOptions>,
        depth: usize,
        path_len: usize,
    ) -> io::Result<()> {
        for entry in entries {
            match &entry.kind {
                InputEntryKind::Directory(children) => {
                    let child_path_len = if path_len == 0 {
                        entry.name.len()
                    } else {
                        path_len + 1 + entry.name.len()
                    };
                    if (depth >= 8 || child_path_len > 255)
                        && !rrip
                            .is_some_and(|options| options.enabled && options.relocate_deep_dirs)
                    {
                        return Err(io::Error::new(
                            io::ErrorKind::InvalidInput,
                            "directory depth or path length exceeds ISO 9660 limits and RRIP relocation is disabled",
                        ));
                    }
                    visit(children, rrip, depth + 1, child_path_len)?;
                }
                InputEntryKind::Symlink(_) => {
                    if !rrip.is_some_and(|options| options.enabled && options.preserve_symlinks) {
                        return Err(io::Error::new(
                            io::ErrorKind::InvalidInput,
                            "symbolic links require RRIP preserve_symlinks",
                        ));
                    }
                }
                InputEntryKind::CharacterDevice { .. } | InputEntryKind::BlockDevice { .. } => {
                    if !rrip.is_some_and(|options| options.enabled && options.preserve_devices) {
                        return Err(io::Error::new(
                            io::ErrorKind::InvalidInput,
                            "device entries require RRIP preserve_devices",
                        ));
                    }
                }
                InputEntryKind::File(contents) => {
                    if contents.len() as u64 > MAX_SINGLE_EXTENT_FILE_LEN {
                        return Err(io::Error::new(
                            io::ErrorKind::InvalidInput,
                            "file exceeds 4 GiB; the ISO writer stores each file in a single \
                             extent and cannot yet emit multi-extent records",
                        ));
                    }
                }
            }
        }
        Ok(())
    }
    visit(&tree.entries, rrip, 1, 0)
}

/// Largest file size a single ISO 9660 (ECMA-119 9.1) directory record can
/// address through its 32-bit `data_len` field. Larger files require
/// multi-extent records, which the writer does not yet emit — attempting to
/// write one is rejected up front rather than silently truncated to `u32`.
pub(crate) const MAX_SINGLE_EXTENT_FILE_LEN: u64 = u32::MAX as u64;

fn relocate_deep_directories(files: &mut WrittenFiles) {
    fn visit(
        dir: &mut WrittenDirectory,
        physical_depth: usize,
        physical_path_len: usize,
        moved: &mut Vec<WrittenDirectory>,
        internal_id: &mut usize,
    ) {
        let mut retained = Vec::with_capacity(dir.dirs.len());
        for mut child in core::mem::take(&mut dir.dirs) {
            let child_path_len = if physical_path_len == 0 {
                child.name.len()
            } else {
                physical_path_len + 1 + child.name.len()
            };
            if physical_depth + 1 > 8 || child_path_len > 255 {
                let target = child.id;
                let logical_parent = dir.id;
                let original_name = child.rrip_name.clone();
                child.name = Arc::new(alloc::format!("RRD{:06}", *internal_id));
                *internal_id += 1;
                child.relocation = DirectoryRelocation::Moved {
                    id: target,
                    logical_parent,
                };
                let relocated_path_len = "RR_MOVED".len() + 1 + child.name.len();
                visit(&mut child, 3, relocated_path_len, moved, internal_id);
                moved.push(child);

                let mut placeholder = WrittenDirectory::new(original_name);
                placeholder.relocation = DirectoryRelocation::Placeholder { target };
                retained.push(placeholder);
            } else {
                visit(
                    &mut child,
                    physical_depth + 1,
                    child_path_len,
                    moved,
                    internal_id,
                );
                retained.push(child);
            }
        }
        dir.dirs = retained;
    }

    let root = files.get_mut(&files.root_dir());
    let mut moved = Vec::new();
    let mut internal_id = 1;
    visit(root, 1, 0, &mut moved, &mut internal_id);
    if moved.is_empty() {
        return;
    }

    let occupied = root
        .dirs
        .iter()
        .map(|directory| directory.name.as_str())
        .collect::<std::collections::HashSet<_>>();
    let mut relocation_name = String::from("RR_MOVED");
    let mut suffix = 1;
    while occupied.contains(relocation_name.as_str()) {
        relocation_name = alloc::format!("RR_MOVED_{suffix}");
        suffix += 1;
    }
    let mut relocation_dir = WrittenDirectory::new(Arc::new(relocation_name));
    relocation_dir.id = usize::MAX;
    relocation_dir.dirs = moved;
    root.dirs.insert(0, relocation_dir);
}

#[derive(Debug, thiserror::Error)]
/// Identifies a IsoCreationError value.
pub enum IsoCreationError {
    #[error(transparent)]
    /// The `Io` variant.
    Io(#[from] io::Error),
}

/// Canonical error for ISO creation operations.
pub type Error = IsoCreationError;
/// Canonical result for ISO creation operations.
pub type Result<T> = core::result::Result<T, Error>;

/// Represents IsoImageWriter.
pub struct IsoImageWriter<DATA: Read + Write + Seek> {
    data: IsoCursor<DATA>,
    entry_types: Vec<EntryType>,
    ops: IsoFormatOptions,
    written_files: WrittenFiles,
    path_tables: BTreeMap<EntryType, PathTableRef>,
    inode_counter: u32,
    rrip_time: [u8; 7],
}

/// The kind of directory entry, used to select which RRIP entries to emit.
enum RripEntryKind<'a> {
    /// Root directory's "." entry — needs SP + ER + PX + NM(CURRENT)
    RootDot { metadata: InputMetadata, nlink: u32 },
    /// Root directory's ".." entry — needs PX + NM(PARENT)
    RootDotDot { metadata: InputMetadata, nlink: u32 },
    /// Non-root "." entry — needs PX + NM(CURRENT)
    Dot { metadata: InputMetadata, nlink: u32 },
    /// Non-root ".." entry — needs PX + NM(PARENT)
    DotDot { metadata: InputMetadata, nlink: u32 },
    /// A named directory entry
    Directory {
        original_name: &'a str,
        metadata: InputMetadata,
        nlink: u32,
    },
    /// A named file entry
    Entry {
        original_name: &'a str,
        metadata: InputMetadata,
        kind: &'a InputEntryKind,
    },
}

/// Compute the available system use space in a DirectoryRecord given
/// the ISO name length. The record is 256 bytes max; the fixed header
/// is 33 bytes, followed by the name (padded to even).
fn available_su_space(iso_name_len: usize) -> usize {
    let used = (33 + iso_name_len + 1) & !1; // pad to even boundary
    256usize.saturating_sub(used)
}

/// Build complete RRIP entries for a directory record.
///
/// Entries are ordered by priority (most important first, largest last),
/// so that `build_split` keeps the important ones inline and overflows
/// the rest via a CE pointer.
fn rrip_datetime(timestamp: Option<i64>, fallback: &[u8; 7]) -> [u8; 7] {
    use chrono::{Datelike, Timelike};
    let Some(timestamp) = timestamp.and_then(|value| chrono::DateTime::from_timestamp(value, 0))
    else {
        return *fallback;
    };
    [
        (timestamp.year() - 1900).clamp(0, 255) as u8,
        timestamp.month() as u8,
        timestamp.day() as u8,
        timestamp.hour() as u8,
        timestamp.minute() as u8,
        timestamp.second() as u8,
        0,
    ]
}

fn build_rrip_entries(
    kind: RripEntryKind<'_>,
    inode: u32,
    options: &RripOptions,
    fallback_time: &[u8; 7],
) -> RripBuilder {
    let mut builder = RripBuilder::new();
    let add_common = |builder: &mut RripBuilder,
                      metadata: InputMetadata,
                      type_mode: u32,
                      default_permissions: u32,
                      nlink: u32| {
        let permissions = if options.preserve_permissions {
            metadata.mode.unwrap_or(default_permissions)
        } else {
            default_permissions
        };
        let (uid, gid) = if options.preserve_ownership {
            (metadata.uid.unwrap_or(0), metadata.gid.unwrap_or(0))
        } else {
            (0, 0)
        };
        builder.add_px(type_mode | permissions, nlink, uid, gid, inode);
        if options.preserve_timestamps {
            let modified = rrip_datetime(metadata.modified, fallback_time);
            let accessed = rrip_datetime(metadata.accessed, fallback_time);
            // Emit the creation timestamp when the input carries one; in-memory
            // entries without a creation time keep the modify/access-only form.
            let created = metadata
                .created
                .map(|created| rrip_datetime(Some(created), fallback_time));
            builder.add_tf(created.as_ref(), &modified, &accessed);
        }
    };

    match &kind {
        RripEntryKind::RootDot { metadata, nlink } => {
            builder.add_sp(0);
            add_common(&mut builder, *metadata, 0o040000, 0o755, *nlink);
            builder.add_nm_current();
            builder.add_rrip_er(); // full ER, last (largest)
        }
        RripEntryKind::RootDotDot { metadata, nlink } => {
            add_common(&mut builder, *metadata, 0o040000, 0o755, *nlink);
            builder.add_nm_parent();
        }
        RripEntryKind::Dot { metadata, nlink } => {
            add_common(&mut builder, *metadata, 0o040000, 0o755, *nlink);
            builder.add_nm_current();
        }
        RripEntryKind::DotDot { metadata, nlink } => {
            add_common(&mut builder, *metadata, 0o040000, 0o755, *nlink);
            builder.add_nm_parent();
        }
        RripEntryKind::Directory {
            original_name,
            metadata,
            nlink,
        } => {
            add_common(&mut builder, *metadata, 0o040000, 0o755, *nlink);
            builder.add_nm(original_name.as_bytes());
        }
        RripEntryKind::Entry {
            original_name,
            metadata,
            kind,
        } => {
            let (type_mode, default_permissions) = match kind {
                InputEntryKind::File(_) => (0o100000, 0o644),
                InputEntryKind::Symlink(_) => (0o120000, 0o777),
                InputEntryKind::CharacterDevice { .. } => (0o020000, 0o600),
                InputEntryKind::BlockDevice { .. } => (0o060000, 0o600),
                InputEntryKind::Directory(_) => unreachable!(),
            };
            add_common(&mut builder, *metadata, type_mode, default_permissions, 1);
            builder.add_nm(original_name.as_bytes());
            match kind {
                InputEntryKind::Symlink(target) => {
                    builder.add_sl(target);
                }
                InputEntryKind::CharacterDevice { major, minor }
                | InputEntryKind::BlockDevice { major, minor } => {
                    builder.add_pn(*major, *minor);
                }
                _ => {}
            }
        }
    }

    builder
}

/// Apply a deduplication suffix to a name, producing e.g. `READM_1.TXT;1`.
///
/// The suffix `_N` is inserted before the extension (and before any `;1` version
/// suffix). The basename is truncated if needed to stay within format limits.
fn apply_dedup_suffix(name: &[u8], n: usize, ty: EntryType) -> Vec<u8> {
    let suffix = alloc::format!("_{n}");
    let suffix_bytes = suffix.as_bytes();

    match ty {
        EntryType::Joliet { .. } => {
            // Joliet: UTF-16 BE, find the dot (0x00 0x2E) or end
            let mut dot_pos = None;
            let mut i = 0;
            while i + 1 < name.len() {
                if name[i] == 0x00 && name[i + 1] == 0x2E {
                    dot_pos = Some(i);
                }
                i += 2;
            }
            let (basename, ext) = match dot_pos {
                Some(pos) => (&name[..pos], &name[pos..]),
                None => (name, &[][..]),
            };
            // Convert suffix to UTF-16 BE
            let suffix_u16: Vec<u8> = suffix
                .encode_utf16()
                .flat_map(|c| c.to_be_bytes())
                .collect();
            // Max 206 bytes (103 code units) for Joliet
            let max_basename = 206usize.saturating_sub(ext.len() + suffix_u16.len());
            let trunc_basename = &basename[..basename.len().min(max_basename) & !1];
            let mut result =
                Vec::with_capacity(trunc_basename.len() + suffix_u16.len() + ext.len());
            result.extend_from_slice(trunc_basename);
            result.extend_from_slice(&suffix_u16);
            result.extend_from_slice(ext);
            result
        }
        _ => {
            // ASCII-based names (L1, L2, L3)
            // Strip ";1" version suffix if present
            let (base_name, version) = if name.ends_with(b";1") {
                (&name[..name.len() - 2], &b";1"[..])
            } else {
                (name, &[][..])
            };
            // Find the dot separator
            let dot_pos = base_name.iter().rposition(|&b| b == b'.');
            let (basename, ext) = match dot_pos {
                Some(pos) => (&base_name[..pos], &base_name[pos..]),
                None => (base_name, &[][..]),
            };
            // Determine max basename length based on level
            let max_total = match ty {
                EntryType::Level1 { .. } => 8,
                EntryType::Level2 { .. } => 30usize.saturating_sub(ext.len()),
                _ => 207usize.saturating_sub(ext.len() + version.len()),
            };
            let max_basename = max_total.saturating_sub(suffix_bytes.len());
            let trunc_basename = &basename[..basename.len().min(max_basename)];
            let mut result = Vec::with_capacity(
                trunc_basename.len() + suffix_bytes.len() + ext.len() + version.len(),
            );
            result.extend_from_slice(trunc_basename);
            result.extend_from_slice(suffix_bytes);
            result.extend_from_slice(ext);
            result.extend_from_slice(version);
            result
        }
    }
}

/// A pending directory record, built in phase 1 and written in phases 2-3.
struct PendingRecord {
    name: Vec<u8>,
    split: SplitSu,
    dir_ref: DirectoryRef,
    flags: FileFlags,
}

io_transform! {
impl<DATA: Read + Write + Seek> IsoImageWriter<DATA> {
    /// Creates a complete ISO image and returns its output target.
    pub async fn create<T: Into<InputTree>>(
        data: DATA,
        files: T,
        ops: IsoFormatOptions,
    ) -> Result<DATA> {
        Self::create_with_allocation_floor(data, files, ops, None).await
    }

    /// Creates an ISO image while keeping file and directory allocations at or
    /// after an optional logical-sector floor.
    ///
    /// This is useful when composing ISO 9660 with another on-disc format whose
    /// metadata occupies sectors after the ISO volume descriptor sequence. A
    /// floor below the end of the descriptors has no effect. Volume descriptors
    /// and system-area structures retain their specification-defined locations.
    pub async fn create_with_allocation_floor<T: Into<InputTree>>(
        data: DATA,
        files: T,
        ops: IsoFormatOptions,
        allocation_floor: Option<u32>,
    ) -> Result<DATA> {
        let mut files = files.into();
        if ops.sector_size != 2048 {
            return Err(io::Error::new(
                io::ErrorKind::InvalidInput,
                "ISO creation currently requires 2048-byte logical sectors",
            )
            .into());
        }
        validate_input_tree(&files, ops.features.rock_ridge.as_ref())?;
        let mut writer = Self::new(data, ops);
        writer.write_volume_descriptors(&mut files).await?;
        if let Some(sector) = allocation_floor {
            let current = writer
                .data
                .stream_position()
                .await
                .map_err(io::Error::erase)?;
            let floor = u64::from(sector)
                .checked_mul(writer.ops.sector_size as u64)
                .ok_or_else(|| {
                    io::Error::new(io::ErrorKind::InvalidInput, "allocation floor overflow")
                })?;
            if floor > current {
                writer
                    .data
                    .seek(SeekFrom::Start(floor))
                    .await
                    .map_err(io::Error::erase)?;
            }
        }
        let root_dirs = writer.write_files(&files).await?;
        writer.write_path_tables().await?;
        writer.finalize_volume_descriptors(root_dirs).await?;
        Ok(writer.into_inner())
    }

    /// Returns the output target.
    pub fn into_inner(self) -> DATA {
        self.data.into_inner()
    }

    fn new(data: DATA, ops: IsoFormatOptions) -> Self {
        let now = super::super::directory::DirDateTime::now();
        let rrip_time = *<&[u8; 7]>::try_from(bytemuck::bytes_of(&now)).unwrap();
        let mut entry_types = Vec::new();
        // The base (PVD) entry type inherits supports_rrip from the filenames config
        entry_types.push(ops.features.filenames.into());
        if ops.features.long_filenames {
            entry_types.push(EntryType::Level3 {
                supports_lowercase: true,
                supports_rrip: false,
            });
        }
        if let Some(joliet) = ops.features.joliet {
            entry_types.push(joliet.into());
        }

        Self {
            data: IsoCursor::new(data, ops.sector_size),
            ops,
            entry_types,
            written_files: WrittenFiles::new(),
            path_tables: BTreeMap::new(),
            inode_counter: 1,
            rrip_time,
        }
    }

    const VOLUME_DESCRIPTOR_SET_START: LogicalSector = LogicalSector(16);

    fn parse_iso_str<C: Charset, const N: usize>(
        &self,
        s: &str,
        field_name: &'static str,
    ) -> io::Result<IsoStr<C, N>> {
        if self.ops.strict_charset {
            IsoStr::from_str_lossy(s)
        } else {
            IsoStr::from_str_unchecked(s)
        }
        .map_err(|_| io::Error::new(io::ErrorKind::InvalidInput, field_name))
    }

    async fn write_volume_descriptors(&mut self, files: &mut InputTree) -> io::Result<()> {
        self.data.seek_sector(Self::VOLUME_DESCRIPTOR_SET_START).await?;
        let mut volume_descriptors = VolumeDescriptorList::empty();
        for &entry in &self.entry_types {
            match entry {
                EntryType::Level1 { .. } | EntryType::Level2 { .. } => {
                    let mut pvd = PrimaryVolumeDescriptor::new(&self.ops.volume_name, 0);
                    pvd.volume_identifier = self.parse_iso_str(&self.ops.volume_name, "volume name")?;
                    pvd.dir_record.header.len = 34;
                    pvd.dir_record.header.flags = FileFlags::DIRECTORY.bits();
                    pvd.dir_record.header.file_identifier_len = 1;
                    pvd.dir_record.header.volume_sequence_number.write(1);
                    pvd.volume_sequence_number.write(1);
                    if let Some(s) = &self.ops.system_id {
                        pvd.system_identifier = self.parse_iso_str(s, "system identifier")?;
                    }
                    if let Some(s) = &self.ops.volume_set_id {
                        pvd.volume_set_identifier = self.parse_iso_str(s, "volume set identifier")?;
                    }
                    if let Some(s) = &self.ops.publisher_id {
                        pvd.publisher_identifier = self.parse_iso_str(s, "publisher identifier")?;
                    }
                    if let Some(s) = &self.ops.preparer_id {
                        pvd.preparer_identifier = self.parse_iso_str(s, "preparer identifier")?;
                    }
                    if let Some(s) = &self.ops.application_id {
                        pvd.application_identifier = self.parse_iso_str(s, "application identifier")?;
                    }
                    volume_descriptors.push(VolumeDescriptor::Primary(pvd));
                }
                EntryType::Level3 { .. } => {
                    // Version 2 for EVD
                    let mut evd = SupplementaryVolumeDescriptor::new_evd(&self.ops.volume_name, 0);
                    evd.volume_identifier = self.parse_iso_str(&self.ops.volume_name, "volume name")?;
                    evd.dir_record.header.len = 34;
                    evd.dir_record.header.flags = FileFlags::DIRECTORY.bits();
                    evd.dir_record.header.file_identifier_len = 1;
                    evd.dir_record.header.volume_sequence_number.write(1);
                    evd.volume_sequence_number.write(1);
                    volume_descriptors.push(VolumeDescriptor::Supplementary(evd));
                }
                EntryType::Joliet { level, .. } => {
                    let mut svd = SupplementaryVolumeDescriptor::new_svd(
                        &self.ops.volume_name,
                        0,
                        level.escape_sequence(),
                    );
                    svd.dir_record.header.len = 34;
                    svd.dir_record.header.flags = FileFlags::DIRECTORY.bits();
                    svd.dir_record.header.file_identifier_len = 1;
                    svd.dir_record.header.volume_sequence_number.write(1);
                    svd.volume_sequence_number.write(1);
                    if let Some(s) = &self.ops.system_id {
                        svd.system_identifier = SupplementaryVolumeDescriptor::utf16be_str(s);
                    }
                    if let Some(s) = &self.ops.volume_set_id {
                        svd.volume_set_identifier = SupplementaryVolumeDescriptor::utf16be_str(s);
                    }
                    if let Some(s) = &self.ops.publisher_id {
                        svd.publisher_identifier = SupplementaryVolumeDescriptor::utf16be_str(s);
                    }
                    if let Some(s) = &self.ops.preparer_id {
                        svd.preparer_identifier = SupplementaryVolumeDescriptor::utf16be_str(s);
                    }
                    if let Some(s) = &self.ops.application_id {
                        svd.application_identifier = SupplementaryVolumeDescriptor::utf16be_str(s);
                    }
                    volume_descriptors.push(VolumeDescriptor::Supplementary(svd));
                }
            }
        }

        if let Some(boot) = &self.ops.features.el_torito {
            let boot_record = ElToritoWriter::create_descriptor(boot, files);
            volume_descriptors.insert(1, VolumeDescriptor::BootRecord(boot_record));
        }

        volume_descriptors.write(&mut self.data).await?;
        Ok(())
    }

    async fn finalize_volume_descriptors(
        &mut self,
        root_dirs: BTreeMap<EntryType, DirectoryRef>,
    ) -> io::Result<()> {
        // Write boot catalog
        let catalog_ptr = if let Some(boot) = &self.ops.features.el_torito {
            let mut catalog = BootCatalog::default();
            let current_sector = self.data.pad_align_sector().await?;

            for (section, entry) in boot.sections() {
                let dir_ref = self
                    .written_files
                    .find_file(&entry.boot_image_path, self.ops.path_separator)
                    .ok_or_else(|| {
                        io::Error::new(
                            io::ErrorKind::NotFound,
                            "boot image file not found",
                        )
                    })?;
                let load_size = entry.load_size.map(core::num::NonZeroU16::get).unwrap_or_else(
                    || {
                        // Emulated media load a single virtual boot sector; the
                        // firmware then services the emulated disk. No-emulation
                        // entries load the whole image as 512-byte sectors.
                        if entry.emulation.is_emulated() {
                            1
                        } else {
                            dir_ref.size.div_ceil(512) as u16
                        }
                    },
                );
                let boot_image_lba = dir_ref.extent.0 as u32;
                let boot_entry =
                    BootSectionEntry::new(entry.emulation, 0, load_size, boot_image_lba);
                if let Some(section) = section {
                    catalog.add_section(section.platform, vec![boot_entry]);
                } else {
                    catalog.set_default_entry(boot_entry);
                }

                // Handle boot info table (standard El-Torito) or GRUB2 boot info
                // Both use similar format at offset 8 in the boot image
                if entry.boot_info_table || entry.grub2_boot_info {
                    // Boot info table requires at least 64 bytes in the boot image
                    // (header is at offset 8-56/64, checksum covers bytes 64+)
                    if dir_ref.size < 64 {
                        return Err(io::Error::new(
                            io::ErrorKind::InvalidInput,
                            "boot image too small for boot info table (minimum 64 bytes)",
                        ));
                    }

                    let mut checksum = 0u32;
                    let mut buffer = [0u8; 4];
                    let byte_offset = (boot_image_lba as u64) * self.ops.sector_size as u64;
                    self.data
                        .seek(SeekFrom::Start(byte_offset + 64))
                        .await
                        .map_err(io::Error::erase)?;
                    // Calculate checksum for all 4-byte chunks from offset 64 to end
                    let checksum_bytes = dir_ref.size - 64;
                    for _ in 0..(checksum_bytes / 4) {
                        self.data.read_exact(&mut buffer).await?;
                        checksum = checksum.wrapping_add(u32::from_le_bytes(buffer));
                    }

                    const TABLE_OFFSET: u64 = 8;
                    self.data
                        .seek(SeekFrom::Start(byte_offset + TABLE_OFFSET))
                        .await
                        .map_err(io::Error::erase)?;

                    if entry.grub2_boot_info {
                        // GRUB2/ISOLINUX uses extended 56-byte format with reserved bytes
                        let table = Grub2BootInfoTable {
                            pvd_lba: U32::new(16),
                            file_lba: U32::new(dir_ref.extent.0 as u32),
                            file_len: U32::new(dir_ref.size as u32),
                            checksum: U32::new(checksum),
                            reserved: [0u8; 40],
                        };
                        self.data.write_all(bytemuck::bytes_of(&table)).await?;
                    } else {
                        // Standard El-Torito 16-byte format
                        let table = BootInfoTable {
                            iso_start: U32::new(16),
                            file_lba: U32::new(dir_ref.extent.0 as u32),
                            file_len: U32::new(dir_ref.size as u32),
                            checksum: U32::new(checksum),
                        };
                        self.data.write_all(bytemuck::bytes_of(&table)).await?;
                    }
                }
            }

            if boot.write_boot_catalog {
                let dir_ref = self
                    .written_files
                    .find_file("boot.catalog", self.ops.path_separator)
                    .ok_or_else(|| {
                        io::Error::new(
                            io::ErrorKind::NotFound,
                            "boot.catalog file not found in written files",
                        )
                    })?;
                self.data.seek_sector(dir_ref.extent).await?;
                if dir_ref.size < catalog.size() {
                    return Err(io::Error::new(
                        io::ErrorKind::InvalidData,
                        "boot.catalog file too small",
                    ));
                }
                catalog.write(&mut self.data).await?;
                self.data.seek_sector(current_sector).await?;

                Some(dir_ref.extent.0 as u32)
            } else {
                self.data.seek_sector(current_sector).await?;
                catalog.write(&mut self.data).await?;
                self.data.pad_align_sector().await?;
                Some(current_sector.0 as u32)
            }
        } else {
            None
        };

        let end_position = self
            .data
            .stream_position()
            .await
            .map_err(io::Error::erase)?;
        let end_sector = self.data.pad_align_sector().await?;
        let volume_space = self.volume_space_sectors(end_sector);
        let image_len = end_sector.0 as u64 * self.ops.sector_size as u64;
        if alignment_requires_materialization(end_position, image_len) {
            self.data
                .seek(SeekFrom::Start(image_len - 1))
                .await
                .map_err(io::Error::erase)?;
            self.data.write_all(&[0]).await?;
        }
        self.data.seek_sector(Self::VOLUME_DESCRIPTOR_SET_START).await?;

        let mut buffer = vec![0u8; self.ops.sector_size];
        loop {
            self.data.read_exact(&mut buffer).await?;
            let header = VolumeDescriptorHeader::from_bytes(&buffer[0..7]);
            let ty = VolumeDescriptorType::from_u8(header.descriptor_type);
            if let VolumeDescriptorType::VolumeSetTerminator = ty {
                break;
            }
            if !header.is_valid() {
                return Err(io::Error::new(
                    io::ErrorKind::InvalidData,
                    "invalid volume descriptor header during finalization",
                ));
            }

            match ty {
                VolumeDescriptorType::PrimaryVolumeDescriptor => {
                    let base_type = self
                        .entry_types
                        .iter()
                        .find(|e| matches!(e, EntryType::Level1 { .. } | EntryType::Level2 { .. }))
                        .ok_or_else(|| {
                            io::Error::new(
                                io::ErrorKind::InvalidData,
                                "no base Level entry type found for PVD",
                            )
                        })?;
                    let root_dir = root_dirs.get(base_type).ok_or_else(|| {
                        io::Error::new(
                            io::ErrorKind::InvalidData,
                            "root directory not found for PVD entry type",
                        )
                    })?;
                    let pt = self.path_tables.get(base_type).ok_or_else(|| {
                        io::Error::new(
                            io::ErrorKind::InvalidData,
                            "path table not found for PVD entry type",
                        )
                    })?;
                    let pvd = bytemuck::from_bytes_mut::<PrimaryVolumeDescriptor>(&mut buffer);
                    pvd.dir_record.header.extent.write(root_dir.extent.0 as u32);
                    pvd.dir_record.header.data_len.write(root_dir.size as u32);
                    pvd.type_l_path_table.set(pt.lpt.0 as u32);
                    pvd.type_m_path_table.set(pt.mpt.0 as u32);
                    pvd.path_table_size.write(pt.size as u32);
                    pvd.volume_space_size.write(volume_space);
                }
                VolumeDescriptorType::SupplementaryVolumeDescriptor => {
                    let svd =
                        bytemuck::from_bytes_mut::<SupplementaryVolumeDescriptor>(&mut buffer);
                    match svd.header.version {
                        1 => {
                            for &level in JolietLevel::all() {
                                if svd.escape_sequences == level.escape_sequence() {
                                    let Some(joliet) = self
                                        .entry_types
                                        .iter()
                                        .find(
                                            |e| matches!(e, EntryType::Joliet{ level: jl, ..} if *jl == level),
                                        )
                                    else {
                                        continue;
                                    };
                                    let Some(root_dir) = root_dirs.get(joliet) else {
                                        continue;
                                    };
                                    let Some(pt) = self.path_tables.get(joliet) else {
                                        continue;
                                    };

                                    svd.dir_record.header.extent.write(root_dir.extent.0 as u32);
                                    svd.dir_record.header.data_len.write(root_dir.size as u32);
                                    svd.type_l_path_table.set(pt.lpt.0 as u32);
                                    svd.type_m_path_table.set(pt.mpt.0 as u32);
                                    svd.path_table_size.write(pt.size as u32);
                                    svd.volume_space_size.write(volume_space);
                                }
                            }
                        }
                        2 => {
                            if svd.escape_sequences != [b' '; 32] {
                                // We don't recognize this EVD
                                continue;
                            }

                            let Some(l3) = self
                                .entry_types
                                .iter()
                                .find(|e| matches!(e, EntryType::Level3 { .. }))
                            else {
                                continue;
                            };
                            let Some(root_dir) = root_dirs.get(l3) else {
                                continue;
                            };
                            let Some(pt) = self.path_tables.get(l3) else {
                                continue;
                            };
                            svd.dir_record.header.extent.write(root_dir.extent.0 as u32);
                            svd.dir_record.header.data_len.write(root_dir.size as u32);
                            svd.type_l_path_table.set(pt.lpt.0 as u32);
                            svd.type_m_path_table.set(pt.mpt.0 as u32);
                            svd.path_table_size.write(pt.size as u32);
                            svd.volume_space_size.write(volume_space);
                        }

                        // Unknown version
                        _ => {}
                    }
                }
                VolumeDescriptorType::BootRecord => {
                    let Some(catalog_ptr) = catalog_ptr else {
                        return Err(io::Error::new(
                            io::ErrorKind::InvalidData,
                            "boot record found but no boot catalog was written",
                        ));
                    };
                    let boot_record =
                        bytemuck::from_bytes_mut::<BootRecordVolumeDescriptor>(&mut buffer);
                    boot_record.catalog_ptr.set(catalog_ptr);
                }
                // We don't do anything
                _ => continue,
            }

            // Write the new data
            self.data
                .seek_relative(-(buffer.len() as i64))
                .await
                .map_err(io::Error::erase)?;
            self.data.write_all(&buffer).await?;
        }

        // Now we finalize the partition tables based on hybrid boot options
        self.write_partition_tables(end_sector).await?;

        Ok(())
    }

    async fn write_files(&mut self, files: &InputTree) -> io::Result<BTreeMap<EntryType, DirectoryRef>> {
        let mut next_directory_id = 1usize;
        {
            let walker = FileTreeWalker::new(files);
            let mut current_dir = self.written_files.root_dir();
            for file in walker {
                match file {
                    TreeWalkerItem::EnterDirectory(dir) => {
                        let name = dir.name();
                        let metadata = dir.metadata;
                        let written_dir = self.written_files.get_mut(&current_dir);
                        let index = written_dir.push_dir(name, metadata);
                        written_dir.dirs[index].id = next_directory_id;
                        next_directory_id += 1;
                        current_dir.push(index);
                    }
                    TreeWalkerItem::ExitDirectory(_dir) => {
                        current_dir.pop();
                    }
                    TreeWalkerItem::File(file) => {
                        // Extents are assigned in the planning pass below.
                        // Empty files keep extent 0 (per ISO 9660 they have no
                        // data to reference).
                        let dir = self.written_files.get_mut(&current_dir);
                        dir.files.push(WrittenFile {
                            name: file.name.clone(),
                            entry: DirectoryRef {
                                extent: LogicalSector(0),
                                size: 0,
                            },
                            kind: file.kind.clone(),
                            metadata: file.metadata,
                        });
                    }
                };
            }
        }

        if self
            .ops
            .features
            .rock_ridge
            .is_some_and(|options| options.enabled && options.relocate_deep_dirs)
        {
            relocate_deep_directories(&mut self.written_files);
        }

        // Pre-order: parents before children. libarchive (bsdtar) scans
        // directories as a stream and ignores a directory whose extent is
        // lower than its current position, so extents must ascend from
        // parents to children.
        fn collect_preorder(
            files: &WrittenFiles,
            id: &writer::DirectoryId,
            output: &mut Vec<writer::DirectoryId>,
        ) {
            output.push(id.clone());
            let dir = files.get(id);
            for (index, child) in dir.dirs.iter().enumerate() {
                if matches!(child.relocation, DirectoryRelocation::Placeholder { .. }) {
                    continue;
                }
                let mut child_id = id.clone();
                child_id.push(index);
                collect_preorder(files, &child_id, output);
            }
        }

        let root_id = self.written_files.root_dir();
        let mut order = Vec::new();
        collect_preorder(&self.written_files, &root_id, &mut order);

        let mut file_order = Vec::new();
        for directory_id in &order {
            let dir = self.written_files.get(directory_id);
            for (index, file) in dir.files.iter().enumerate() {
                if matches!(&file.kind, InputEntryKind::File(contents) if !contents.is_empty()) {
                    file_order.push((directory_id.clone(), index));
                }
            }
        }

        let sector_size = self.ops.sector_size as u64;
        let rrip_options = self.ops.features.rock_ridge;
        let rrip_time = self.rrip_time;
        let entry_types = self.entry_types.clone();
        let mut inode_counter = self.inode_counter;

        // ── Planning pass ──
        //
        // Build every directory's records once to measure its size, then
        // assign directory extents in pre-order and file data extents after
        // the whole directory region. Record sizes never depend on extent
        // *values*, so the write pass below reproduces this layout exactly.
        // libarchive requires continuation areas to precede the data extents
        // of regular files carrying CE entries, which file-data-last gives.
        let mut cursor = self
            .data
            .stream_position()
            .await
            .map_err(io::Error::erase)?;
        let mut relocation_refs: BTreeMap<(usize, EntryType), DirectoryRef> = BTreeMap::new();
        // Default refs tolerate forward references (unassigned child extents,
        // relocation targets) while sizing; the write pass rebuilds the
        // records with the real values.
        let mut default_refs: BTreeMap<(usize, EntryType), DirectoryRef> = BTreeMap::new();
        for directory_id in &order {
            let dir = self.written_files.get(directory_id);
            for ty in &entry_types {
                default_refs.insert((dir.id, *ty), DirectoryRef::default());
                if let DirectoryRelocation::Moved { id, .. } = dir.relocation {
                    default_refs.insert((id, *ty), DirectoryRef::default());
                }
            }
            let dir = self.written_files.get_mut(directory_id);
            for ty in &entry_types {
                dir.entries.entry(*ty).or_default();
            }
        }
        for directory_id in &order {
            let is_root = directory_id == &root_id;
            for ty in &entry_types {
                let dir = self.written_files.get(directory_id);
                let records = Self::build_directory_records(
                    *ty,
                    dir,
                    is_root,
                    &mut inode_counter,
                    rrip_options.as_ref(),
                    &rrip_time,
                    &default_refs,
                )?;
                let (extent, size_sectors) =
                    Self::layout_directory_records(cursor, sector_size, &records);
                let ca_len = records
                    .iter()
                    .filter(|r| r.split.has_overflow())
                    .map(|r| r.split.overflow.len() as u64)
                    .sum::<u64>();
                let reference = DirectoryRef {
                    extent: LogicalSector(extent as usize),
                    size: (size_sectors * sector_size) as usize,
                };
                let dir = self.written_files.get_mut(directory_id);
                dir.entries.insert(*ty, reference);
                relocation_refs.insert((dir.id, *ty), reference);
                if let DirectoryRelocation::Moved { id, .. } = dir.relocation {
                    relocation_refs.insert((id, *ty), reference);
                }
                cursor = (extent + size_sectors) * sector_size + ca_len;
            }
        }
        for (directory_id, index) in &file_order {
            let aligned = (cursor + sector_size - 1) & !(sector_size - 1);
            let dir = self.written_files.get_mut(directory_id);
            let file = &mut dir.files[*index];
            let len = match &file.kind {
                InputEntryKind::File(contents) => contents.len() as u64,
                _ => 0,
            };
            file.entry = DirectoryRef {
                extent: LogicalSector((aligned / sector_size) as usize),
                size: len as usize,
            };
            cursor = aligned + len;
        }

        // ── Write pass ──
        //
        // Rebuild the records now that every extent is known and write
        // directories in pre-order, each followed by its continuation area,
        // then all file contents.
        for directory_id in &order {
            let is_root = directory_id == &root_id;
            for ty in &entry_types {
                let dir = self.written_files.get(directory_id);
                let expected = dir.entries.get(ty).copied().unwrap_or_default();
                let mut records = Self::build_directory_records(
                    *ty,
                    dir,
                    is_root,
                    &mut inode_counter,
                    rrip_options.as_ref(),
                    &rrip_time,
                    &relocation_refs,
                )?;
                Self::write_directory_records(&mut self.data, sector_size, expected, &mut records)
                    .await?;
            }
        }
        self.inode_counter = inode_counter;

        for (directory_id, index) in &file_order {
            let expected = {
                let dir = self.written_files.get(directory_id);
                dir.files[*index].entry
            };
            let start = self.data.pad_align_sector().await?;
            if start != expected.extent {
                return Err(io::Error::new(
                    io::ErrorKind::InvalidData,
                    "file extent prediction did not match the written layout",
                ));
            }
            let dir = self.written_files.get(directory_id);
            if let InputEntryKind::File(contents) = &dir.files[*index].kind {
                self.data.write_all(contents).await?;
            }
        }

        fn collect_moved(
            directory: &WrittenDirectory,
            output: &mut Vec<(usize, usize, BTreeMap<EntryType, DirectoryRef>)>,
        ) {
            if let DirectoryRelocation::Moved { id, logical_parent } = directory.relocation {
                output.push((id, logical_parent, directory.entries.clone()));
            }
            for child in &directory.dirs {
                collect_moved(child, output);
            }
        }
        let mut moved = Vec::new();
        collect_moved(self.written_files.get(&root_id), &mut moved);
        let directory_end = self
            .data
            .stream_position()
            .await
            .map_err(io::Error::erase)?;
        for (_id, logical_parent, entries) in moved {
            for (ty, directory) in entries {
                if !ty.supports_rrip() {
                    continue;
                }
                let parent = relocation_refs
                    .get(&(logical_parent, ty))
                    .copied()
                    .ok_or_else(|| {
                        io::Error::new(
                            io::ErrorKind::InvalidData,
                            "logical parent extent was not written",
                        )
                    })?;
                self.patch_parent_link(directory, parent).await?;
            }
        }
        self.data
            .seek(SeekFrom::Start(directory_end))
            .await
            .map_err(io::Error::erase)?;
        let roots = self.written_files.root_refs().clone();

        let pos = self
            .data
            .stream_position()
            .await
            .map_err(io::Error::erase)?;
        for root in roots.values() {
            self.update_directory(*root, *root).await?;
        }
        // We need to seek back to this position
        self.data
            .seek(SeekFrom::Start(pos))
            .await
            .map_err(io::Error::erase)?;

        Ok(roots)
    }

    async fn write_path_tables(&mut self) -> io::Result<()> {
        for i in 0..self.entry_types.len() {
            let ty = self.entry_types[i];
            let l_ref = self.write_path_table(ty, EndianType::LittleEndian).await?;
            let m_ref = self.write_path_table(ty, EndianType::BigEndian).await?;
            assert_eq!(l_ref.size, m_ref.size);
            self.path_tables.insert(
                ty,
                PathTableRef {
                    lpt: l_ref.extent,
                    mpt: m_ref.extent,
                    size: l_ref.size as u64,
                },
            );
        }
        Ok(())
    }

    async fn write_path_table(&mut self, ty: EntryType, endian: EndianType) -> io::Result<DirectoryRef> {
        let start = self.data.pad_align_sector().await?;
        PathTableWriter {
            written_files: &self.written_files,
            ty,
            endian,
        }
        .write(&mut self.data).await?;
        let size = self
            .data
            .stream_position()
            .await
            .map_err(io::Error::erase)? as usize
            - (start.0 * self.data.sector_size);
        let _end = self.data.pad_align_sector().await?;
        Ok(DirectoryRef {
            extent: start,
            size,
        })
    }

    /// Writes the partition tables (MBR, GPT, or Hybrid) based on configuration.
    ///
    /// The GPT and Hybrid schemes append 33 sectors of 512 bytes (backup
    /// entry array plus backup header) after the ISO data, padded so that
    /// the image length stays a multiple of the logical sector size and the
    /// backup header occupies the last 512-byte sector. The appended region
    /// lies outside the ISO file-data area but is still counted in
    /// `volume_space_size`, so tools that copy `volume_space_size` logical
    /// sectors preserve the backup GPT, matching xorriso's appended-GPT
    /// practice.
    async fn write_partition_tables(&mut self, end_sector: LogicalSector) -> io::Result<()> {
        match self
            .ops
            .features
            .hybrid_boot
            .as_ref()
            .map(|h| h.partition_scheme)
        {
            None | Some(PartitionScheme::None) => {
                // No partition table requested - leave the system area empty.
                // Writing an MBR here would cause the kernel to detect a
                // partition table and prevent the ISO from being mounted.
            }
            Some(PartitionScheme::Mbr) => {
                self.write_mbr_boot(end_sector).await?;
            }
            Some(PartitionScheme::Gpt) => {
                self.write_gpt_boot(end_sector).await?;
            }
            Some(PartitionScheme::Hybrid) => {
                self.write_hybrid_boot(end_sector).await?;
            }
        }

        Ok(())
    }

    /// Writes an MBR partition table for BIOS USB boot (isohybrid-style).
    async fn write_mbr_boot(&mut self, end_sector: LogicalSector) -> io::Result<()> {
        let end_block = (end_sector.0 * (self.data.sector_size / 512)) as u32;

        let hybrid_opts = self.ops.features.hybrid_boot.as_ref();
        let bootable = hybrid_opts.map(|h| h.bootable).unwrap_or(true);

        let mut mbr = MasterBootRecord::default();
        mbr.with_partition_table(|pt| {
            // Create a partition covering the entire ISO
            // Type 0x17 is ISO9660/Hidden NTFS which is commonly used for hybrid ISOs
            pt[0] = MbrPartition {
                boot_indicator: if bootable { 0x80 } else { 0x00 },
                start_chs: Chs::new(0),
                part_type: MbrPartitionType::Iso9660.to_u8(),
                end_chs: Chs::new(end_block.saturating_sub(1)),
                start_lba: Le::<u32>::from_ne(0),
                sector_count: Le::<u32>::from_ne(end_block),
            };
        });

        // Inject bootstrap code if provided
        if let Some(ref hybrid_opts) = self.ops.features.hybrid_boot
            && let Some(ref bootstrap) = hybrid_opts.mbr_bootstrap
        {
            let len = bootstrap.len().min(446);
            mbr.bootstrap[..len].copy_from_slice(&bootstrap[..len]);
        }

        self.data
            .seek(SeekFrom::Start(0))
            .await
            .map_err(io::Error::erase)?;
        self.data.write_all(bytemuck::bytes_of(&mbr)).await?;

        Ok(())
    }

    /// Resolves the ISO path of the El Torito UEFI image to expose as a GPT
    /// EFI System Partition.
    ///
    /// Uses `HybridBootOptions::efi_boot_partition` when set; otherwise falls
    /// back to the boot image of the single `PlatformId::UEFI` El Torito
    /// section entry, if there is exactly one.
    fn efi_boot_partition_path(&self) -> Option<String> {
        let hybrid = self.ops.features.hybrid_boot.as_ref()?;
        if let Some(path) = &hybrid.efi_boot_partition {
            return Some(path.clone());
        }
        let boot = self.ops.features.el_torito.as_ref()?;
        let mut uefi_entries = boot
            .entries
            .iter()
            .filter(|(section, _)| section.platform == PlatformId::UEFI)
            .map(|(_, entry)| &entry.boot_image_path);
        let first = uefi_entries.next()?;
        if uefi_entries.next().is_some() {
            return None;
        }
        Some(first.clone())
    }

    /// Builds the GPT structures for the image.
    ///
    /// The disk spans the ISO data plus an appended backup-GPT region; the
    /// backup header sits in the last 512-byte sector of the padded image.
    /// The layout is non-overlapping (overlap is rejected by
    /// [`GptDisk::validate`]): a basic-data partition covers the ISO area
    /// before the EFI System Partition, the ESP covers the El Torito UEFI
    /// image exactly, and a second basic-data partition covers any remaining
    /// ISO data after it. Partitions start no earlier than 512-byte LBA 64,
    /// where the ISO volume descriptors begin: tools that convert ISOHYBRID
    /// GPT images to MBR (e.g. `limine bios-install`) embed boot code in
    /// sectors 1..63 and reject partitions starting below sector 63.
    ///
    /// Returns the disk together with the entry indices of the leading
    /// ISO9660 partition and the ESP, for hybrid MBR mirroring.
    /// Total image size in 512-byte sectors for GPT/Hybrid images: the ISO
    /// data plus the appended backup-GPT region, padded to a logical-sector
    /// boundary.
    fn gpt_total_512(&self, end_sector: LogicalSector) -> u64 {
        const BACKUP_GPT_SECTORS: u64 = 33;
        let blocks_per_sector = (self.ops.sector_size / 512) as u64;
        let iso_512 = end_sector.0 as u64 * blocks_per_sector;
        (iso_512 + BACKUP_GPT_SECTORS).div_ceil(blocks_per_sector) * blocks_per_sector
    }

    /// The `volume_space_size` to declare: for GPT/Hybrid images it covers the
    /// whole image including the appended backup-GPT region, so tools that
    /// copy `volume_space_size` logical sectors preserve the backup GPT.
    fn volume_space_sectors(&self, end_sector: LogicalSector) -> u32 {
        match self
            .ops
            .features
            .hybrid_boot
            .as_ref()
            .map(|h| h.partition_scheme)
        {
            Some(PartitionScheme::Gpt) | Some(PartitionScheme::Hybrid) => {
                let blocks_per_sector = (self.ops.sector_size / 512) as u64;
                (self.gpt_total_512(end_sector) / blocks_per_sector) as u32
            }
            _ => end_sector.0 as u32,
        }
    }

    fn build_gpt_disk(
        &self,
        end_sector: LogicalSector,
    ) -> io::Result<(GptDisk, Option<usize>, Option<usize>)> {
        let blocks_per_sector = (self.data.sector_size / 512) as u64;
        let iso_512 = end_sector.0 as u64 * blocks_per_sector;
        let total_512 = self.gpt_total_512(end_sector);

        let mut gpt = GptDisk::new(total_512, 512);
        let disk_guid =
            Self::generate_guid_from_string(&alloc::format!("disk-{}", self.ops.volume_name));
        gpt.primary_header.disk_guid = disk_guid;
        gpt.backup_header.disk_guid = disk_guid;

        const ISO_DATA_START_512: u64 = 64;

        let first_usable = gpt.primary_header.first_usable_lba.to_ne();
        let iso_part_start = first_usable.max(ISO_DATA_START_512);
        let iso_end = iso_512.saturating_sub(1);
        if iso_end <= iso_part_start {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                "image too small for a GPT partition table",
            ));
        }

        let map_part_err = |_| io::Error::new(io::ErrorKind::InvalidData, "invalid GPT layout");

        let esp = match self.efi_boot_partition_path() {
            Some(path) => {
                let dir_ref = self
                    .written_files
                    .find_file(&path, self.ops.path_separator)
                    .ok_or_else(|| {
                        io::Error::new(
                            io::ErrorKind::NotFound,
                            "EFI boot partition image not found in the ISO tree",
                        )
                    })?;
                let start = dir_ref.extent.0 as u64 * blocks_per_sector;
                let sectors = (dir_ref.size as u64).div_ceil(512).max(1);
                let end = start + sectors - 1;
                if start < iso_part_start || end > iso_end {
                    return Err(io::Error::new(
                        io::ErrorKind::InvalidData,
                        "EFI boot partition lies outside the ISO data area",
                    ));
                }
                Some((start, end))
            }
            None => None,
        };

        let mut iso_index = None;
        let mut esp_index = None;
        match esp {
            Some((esp_start, esp_end)) => {
                if esp_start > iso_part_start {
                    let mut data = GptPartitionEntry::new(
                        Guid::BASIC_DATA,
                        Self::generate_guid_from_string(&self.ops.volume_name),
                        iso_part_start,
                        esp_start - 1,
                    );
                    data.set_name_ascii(b"ISO9660");
                    iso_index = Some(gpt.add_partition(data).map_err(map_part_err)?);
                }
                let mut esp_entry = GptPartitionEntry::new(
                    Guid::EFI_SYSTEM,
                    Self::generate_guid_from_string(&alloc::format!(
                        "esp-{}",
                        self.ops.volume_name
                    )),
                    esp_start,
                    esp_end,
                );
                esp_entry.set_name_ascii(b"EFI System Partition");
                esp_index = Some(gpt.add_partition(esp_entry).map_err(map_part_err)?);
                if esp_end < iso_end {
                    let mut tail = GptPartitionEntry::new(
                        Guid::BASIC_DATA,
                        Self::generate_guid_from_string(&alloc::format!(
                            "data-{}",
                            self.ops.volume_name
                        )),
                        esp_end + 1,
                        iso_end,
                    );
                    tail.set_name_ascii(b"ISO9660");
                    gpt.add_partition(tail).map_err(map_part_err)?;
                }
            }
            None => {
                let mut data = GptPartitionEntry::new(
                    Guid::BASIC_DATA,
                    Self::generate_guid_from_string(&self.ops.volume_name),
                    iso_part_start,
                    iso_end,
                );
                data.set_name_ascii(b"ISO9660");
                iso_index = Some(gpt.add_partition(data).map_err(map_part_err)?);
            }
        }

        gpt.update_crcs();
        gpt.validate().map_err(map_part_err)?;
        Ok((gpt, iso_index, esp_index))
    }

    /// Writes a GPT partition table (protective MBR, primary and backup GPT)
    /// for UEFI boot. See [`Self::write_partition_tables`] for the appended
    /// backup region and [`Self::build_gpt_disk`] for the partition layout.
    async fn write_gpt_boot(&mut self, end_sector: LogicalSector) -> io::Result<()> {
        let (gpt, _, _) = self.build_gpt_disk(end_sector)?;
        gpt.write_to(&mut self.data).await.map_err(part_io_error)?;
        Ok(())
    }

    /// Writes a Hybrid MBR + GPT for dual BIOS/UEFI boot.
    ///
    /// The MBR carries a protective entry over the pre-partition gap, mirrors
    /// the leading ISO9660 basic-data partition as type 0x17, and mirrors the
    /// EFI System Partition as type 0xEF.
    async fn write_hybrid_boot(&mut self, end_sector: LogicalSector) -> io::Result<()> {
        let hybrid_opts = self.ops.features.hybrid_boot.as_ref();
        let bootable = hybrid_opts.map(|h| h.bootable).unwrap_or(true);

        let (gpt, iso_index, esp_index) = self.build_gpt_disk(end_sector)?;
        let total_512 = gpt.backup_header.my_lba.to_ne() + 1;

        let mut builder = HybridMbrBuilder::new(total_512).protective_slot(0);
        if let Some(iso_index) = iso_index {
            builder = builder.mirror_partition(iso_index as u32, MbrPartitionType::Iso9660, bootable);
        }
        if let Some(esp_index) = esp_index {
            builder = builder.mirror_partition(
                esp_index as u32,
                MbrPartitionType::EfiSystemPartition,
                false,
            );
        }
        let mut mbr = builder
            .build(&gpt.entries)
            .map_err(|_| io::Error::new(io::ErrorKind::InvalidInput, "invalid hybrid MBR"))?;

        if let Some(ref hybrid_opts) = self.ops.features.hybrid_boot
            && let Some(ref bootstrap) = hybrid_opts.mbr_bootstrap
        {
            let len = bootstrap.len().min(446);
            mbr.bootstrap[..len].copy_from_slice(&bootstrap[..len]);
        }

        gpt.write_to_with_mbr(&mut self.data, &mbr)
            .await
            .map_err(part_io_error)?;

        Ok(())
    }

    /// Generates a deterministic GUID from a string (simple hash-based).
    fn generate_guid_from_string(s: &str) -> Guid {
        // Simple FNV-1a hash to generate a deterministic GUID
        let mut hash1: u64 = 0xcbf29ce484222325;
        let mut hash2: u64 = 0x100000001b3;

        for byte in s.bytes() {
            hash1 ^= byte as u64;
            hash1 = hash1.wrapping_mul(0x100000001b3);
            hash2 ^= byte as u64;
            hash2 = hash2.wrapping_mul(0xcbf29ce484222325);
        }

        let mut bytes = [0u8; 16];
        bytes[0..8].copy_from_slice(&hash1.to_le_bytes());
        bytes[8..16].copy_from_slice(&hash2.to_le_bytes());

        // Set version 4 (random) and variant bits
        bytes[6] = (bytes[6] & 0x0f) | 0x40; // Version 4
        bytes[8] = (bytes[8] & 0x3f) | 0x80; // Variant 1

        Guid::from_bytes(bytes)
    }

    async fn update_directory(
        &mut self,
        parent: DirectoryRef,
        directory: DirectoryRef,
    ) -> io::Result<()> {
        let start = self.data.seek_sector(directory.extent).await?;
        let mut offset = 0;
        loop {
            if offset >= directory.size as u64 {
                break;
            }
            self.data
                .seek(SeekFrom::Start(start + offset))
                .await
                .map_err(io::Error::erase)?;
            let mut record = DirectoryRecord::parse(&mut self.data).await?;
            if record.header().len == 0 {
                break;
            }

            if record.name() == b"\x00" || record.name() == b"\x01" {
                let dir_ref = [directory, parent][record.name()[0] as usize];
                let header = record.header_mut();
                header.extent.write(dir_ref.extent.0 as u32);
                header.data_len.write(dir_ref.size as u32);
                self.data
                    .seek(SeekFrom::Start(start + offset))
                    .await
                    .map_err(io::Error::erase)?;
                record.write(&mut self.data).await?;
                offset += record.header().len as u64;
                continue;
            }
            offset += record.header().len as u64;

            if FileFlags::from_bits_truncate(record.header().flags).contains(FileFlags::DIRECTORY) {
                let record = DirectoryRef {
                    extent: LogicalSector(record.header().extent.read() as usize),
                    size: record.header().data_len.read() as usize,
                };
                self.update_directory(directory, record).await?;
            }
        }

        Ok(())
    }

    async fn patch_parent_link(
        &mut self,
        directory: DirectoryRef,
        parent: DirectoryRef,
    ) -> io::Result<()> {
        let start = self.data.seek_sector(directory.extent).await?;
        self.data
            .seek(SeekFrom::Start(start))
            .await
            .map_err(io::Error::erase)?;
        let dot = DirectoryRecord::parse(&mut self.data).await?;
        self.data
            .seek(SeekFrom::Start(start + dot.header().len as u64))
            .await
            .map_err(io::Error::erase)?;
        let mut dotdot = DirectoryRecord::parse(&mut self.data).await?;
        let system_use = dotdot.system_use_mut();
        let mut offset = 0;
        while offset + 4 <= system_use.len() {
            let length = system_use[offset + 2] as usize;
            if length < 4 || offset + length > system_use.len() {
                break;
            }
            if &system_use[offset..offset + 2] == b"PL" && length >= 12 {
                let value = crate::types::U32LsbMsb::new(parent.extent.0 as u32);
                system_use[offset + 4..offset + 12]
                    .copy_from_slice(bytemuck::bytes_of(&value));
                self.data
                    .seek(SeekFrom::Start(start + dot.header().len as u64))
                    .await
                    .map_err(io::Error::erase)?;
                dotdot.write(&mut self.data).await?;
                return Ok(());
            }
            offset += length;
        }
        Err(io::Error::new(
            io::ErrorKind::InvalidData,
            "relocated directory is missing its RRIP PL entry",
        ))
    }

    /// Write a directory using a three-phase approach:
    ///
    /// 1. Build all RRIP entries and split each against available inline space
    /// 2. If any have overflow: write a shared continuation area, patch CE entries
    /// 3. Write directory records with the inline SU bytes
    #[allow(clippy::too_many_arguments)]
    /// Build the pending records for one directory: dot/dotdot, child
    /// directories, and files, with RRIP system-use areas split against the
    /// inline budget, names deduplicated, and records ordered by File
    /// Identifier (ECMA-119 9.3). Sizes never depend on extent values, so
    /// the planning pass calls this with placeholder refs and the write pass
    /// rebuilds with the real ones.
    fn build_directory_records(
        ty: EntryType,
        dir: &WrittenDirectory,
        is_root: bool,
        inode_counter: &mut u32,
        rrip_options: Option<&RripOptions>,
        fallback_time: &[u8; 7],
        relocation_refs: &BTreeMap<(usize, EntryType), DirectoryRef>,
    ) -> io::Result<Vec<PendingRecord>> {
        let rrip_options = rrip_options.filter(|options| options.enabled);
        let has_rrip = ty.supports_rrip() && rrip_options.is_some();
        let options = rrip_options.copied().unwrap_or_else(RripOptions::disabled);
        let directory_nlink = 2 + dir.dirs.len() as u32;

        let mut records: Vec<PendingRecord> = Vec::new();

        // Dot entry (".")
        let dot_split = if has_rrip {
            let kind = if is_root {
                RripEntryKind::RootDot {
                    metadata: dir.metadata,
                    nlink: directory_nlink,
                }
            } else {
                RripEntryKind::Dot {
                    metadata: dir.metadata,
                    nlink: directory_nlink,
                }
            };
            let max = available_su_space(1); // name is b"\x00"
            build_rrip_entries(kind, 0, &options, fallback_time).build_split(max)
        } else {
            SplitSu::empty()
        };
        records.push(PendingRecord {
            name: vec![0x00],
            split: dot_split,
            dir_ref: DirectoryRef::default(),
            flags: FileFlags::DIRECTORY,
        });

        // Dotdot entry ("..")
        let dotdot_split = if has_rrip {
            let kind = if is_root {
                RripEntryKind::RootDotDot {
                    metadata: dir.metadata,
                    nlink: directory_nlink,
                }
            } else {
                RripEntryKind::DotDot {
                    metadata: dir.metadata,
                    nlink: directory_nlink,
                }
            };
            let max = available_su_space(1); // name is b"\x01"
            let mut builder = build_rrip_entries(kind, 0, &options, fallback_time);
            if let DirectoryRelocation::Moved { logical_parent, .. } = dir.relocation {
                let parent = relocation_refs
                    .get(&(logical_parent, ty))
                    .copied()
                    .unwrap_or_default();
                builder.add_pl(parent.extent.0 as u32);
            }
            builder.build_split(max)
        } else {
            SplitSu::empty()
        };
        records.push(PendingRecord {
            name: vec![0x01],
            split: dotdot_split,
            dir_ref: DirectoryRef::default(),
            flags: FileFlags::DIRECTORY,
        });

        // Directory entries
        for directory in &dir.dirs {
            let WrittenDirectory {
                name,
                rrip_name,
                entries,
                metadata,
                dirs,
                relocation,
                ..
            } = directory;
            let converted_name = ty.convert_directory_name(name);
            let split = if has_rrip {
                let inode = *inode_counter;
                *inode_counter += 1;
                let max = available_su_space(converted_name.as_bytes().len());
                let mut builder = build_rrip_entries(
                    RripEntryKind::Directory {
                        original_name: rrip_name,
                        metadata: *metadata,
                        nlink: 2 + dirs.len() as u32,
                    },
                    inode,
                    &options,
                    fallback_time,
                );
                match relocation {
                    DirectoryRelocation::Placeholder { target } => {
                        let target = relocation_refs.get(&(*target, ty)).ok_or_else(|| {
                            io::Error::new(
                                io::ErrorKind::InvalidData,
                                "relocated directory extent was not written",
                            )
                        })?;
                        builder.add_cl(target.extent.0 as u32);
                    }
                    DirectoryRelocation::Moved { .. } => {
                        builder.add_re();
                    }
                    DirectoryRelocation::None => {}
                }
                builder.build_split(max)
            } else {
                SplitSu::empty()
            };
            records.push(PendingRecord {
                name: converted_name.as_bytes().to_vec(),
                split,
                dir_ref: match relocation {
                    DirectoryRelocation::Placeholder { target } => relocation_refs
                        .get(&(*target, ty))
                        .copied()
                        .unwrap_or_default(),
                    _ => *entries.get(&ty).unwrap(),
                },
                flags: FileFlags::DIRECTORY,
            });
        }

        // File entries
        for file in &dir.files {
            let WrittenFile {
                name,
                entry,
                kind,
                metadata,
            } = file;
            let converted_name = ty.convert_name(name);
            let split = if has_rrip {
                let inode = *inode_counter;
                *inode_counter += 1;
                let max = available_su_space(converted_name.as_bytes().len());
                build_rrip_entries(
                    RripEntryKind::Entry {
                        original_name: name,
                        metadata: *metadata,
                        kind,
                    },
                    inode,
                    &options,
                    fallback_time,
                )
                .build_split(max)
            } else {
                SplitSu::empty()
            };
            records.push(PendingRecord {
                name: converted_name.as_bytes().to_vec(),
                split,
                dir_ref: *entry,
                flags: FileFlags::empty(),
            });
        }

        // ── Phase 1.5: Deduplicate names ──
        // Name mangling can map different original names to the same ISO name.
        // e.g., "readme.txt" and "README.txt" both become "README.TXT;1".
        // Resolve collisions with underscore-based suffixes.
        {
            use std::collections::HashSet;
            let mut seen: HashSet<Vec<u8>> = HashSet::new();
            for record in &mut records {
                // Skip dot/dotdot entries
                if record.name.len() == 1 && (record.name[0] == 0x00 || record.name[0] == 0x01) {
                    continue;
                }
                if seen.insert(record.name.clone()) {
                    continue;
                }
                let original = record.name.clone();
                let mut suffix = 1;
                loop {
                    let candidate = apply_dedup_suffix(&original, suffix, ty);
                    suffix += 1;
                    if seen.insert(candidate.clone()) {
                        record.name = candidate;
                        break;
                    }
                }
            }
        }

        // ── Phase 1.75: Order records by File Identifier (ECMA-119 9.3) ──
        // Directory records must be written in ascending File Identifier order.
        // "." and ".." must be the first two records in that order. A plain
        // byte-wise sort is insufficient for Joliet because every UTF-16BE ASCII
        // name begins with 0x00 and would therefore sort before the 0x01 ".."
        // identifier. Sort ordinary entries byte-wise only after ranking the two
        // special records explicitly.
        records.sort_by(|a, b| {
            let rank = |name: &[u8]| match name {
                [0x00] => 0,
                [0x01] => 1,
                _ => 2,
            };
            rank(&a.name)
                .cmp(&rank(&b.name))
                .then_with(|| a.name.cmp(&b.name))
        });

        Ok(records)
    }

    /// Compute the sector span `records` will occupy when written at byte
    /// position `pos`: returns (start sector, size in sectors). Mirrors the
    /// write logic in [`Self::write_directory_records`] exactly.
    fn layout_directory_records(
        pos: u64,
        sector_size: u64,
        records: &[PendingRecord],
    ) -> (u64, u64) {
        let align = |pos: u64| (pos + sector_size - 1) & !(sector_size - 1);
        let start = align(pos);
        let mut pos = start;
        for record in records {
            let record_size = DirectoryRecord::new(
                &record.name,
                &record.split.inline,
                record.dir_ref,
                record.flags,
            )
            .size() as u64;
            let remaining = sector_size - pos % sector_size;
            if record_size > remaining {
                pos += remaining;
            }
            pos += record_size;
        }
        let end = align(pos);
        (start / sector_size, (end - start) / sector_size)
    }

    /// Write records at the extent the planning pass assigned, followed by
    /// the continuation area their CE entries are patched to point at.
    /// Fails if the written layout does not match the plan.
    async fn write_directory_records(
        data: &mut IsoCursor<DATA>,
        sector_size: u64,
        expected: DirectoryRef,
        records: &mut [PendingRecord],
    ) -> io::Result<()> {
        let has_overflow = records.iter().any(|r| r.split.has_overflow());
        if has_overflow {
            let ca_sector = expected.extent.0 as u64 + expected.size as u64 / sector_size;
            let mut offset = 0u32;
            for record in records.iter_mut() {
                if record.split.has_overflow() {
                    record.split.patch_ce(ca_sector as u32, offset);
                    offset += record.split.overflow.len() as u32;
                }
            }
        }

        let start = data.pad_align_sector().await?;
        if start != expected.extent {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                "directory extent prediction did not match the written layout",
            ));
        }
        for record in records.iter() {
            let directory_record = DirectoryRecord::new(
                &record.name,
                &record.split.inline,
                record.dir_ref,
                record.flags,
            );
            let position = data.stream_position().await.map_err(io::Error::erase)? as usize;
            let sector_offset = position % data.sector_size;
            let remaining = data.sector_size - sector_offset;
            if directory_record.size() > remaining {
                let padding = vec![0_u8; remaining];
                data.write_all(&padding).await?;
            }
            directory_record.write(&mut *data).await?;
        }
        let end = data.pad_align_sector().await?;
        let size = (end.0 - start.0) * data.sector_size;
        if size != expected.size {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                "directory size prediction did not match the written layout",
            ));
        }

        if has_overflow {
            for record in records.iter() {
                if record.split.has_overflow() {
                    data.write_all(&record.split.overflow).await?;
                }
            }
        }
        Ok(())
    }
}
} // io_transform!

fn alignment_requires_materialization(current_position: u64, aligned_position: u64) -> bool {
    aligned_position > current_position
}

fn part_io_error(err: hadris_part::Error) -> io::Error {
    match err {
        hadris_part::Error::Io(err) => err,
        _ => io::Error::new(
            io::ErrorKind::InvalidData,
            "failed to write partition table",
        ),
    }
}

struct FileTreeWalker<'a> {
    stack: VecDeque<StackFrame<'a>>,
}

enum StackFrame<'a> {
    Node(&'a InputEntry),
    DirExit(&'a InputEntry),
}

#[derive(Debug, PartialEq, Eq)]
enum TreeWalkerItem<'a> {
    EnterDirectory(&'a InputEntry),
    File(&'a InputEntry),
    ExitDirectory(&'a InputEntry),
}

impl<'a> FileTreeWalker<'a> {
    pub fn new(input: &'a InputTree) -> Self {
        let mut stack = VecDeque::new();
        for file in input.entries.iter().rev() {
            stack.push_back(StackFrame::Node(file));
        }
        FileTreeWalker { stack }
    }
}

impl<'a> Iterator for FileTreeWalker<'a> {
    type Item = TreeWalkerItem<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        let frame = self.stack.pop_back()?;
        match frame {
            StackFrame::Node(file) => match &file.kind {
                InputEntryKind::Directory(children) => {
                    // Yield that we are entering this directory (pre-order event)
                    let current_dir = file;

                    // Push an Exit frame to signal leaving this directory later
                    self.stack.push_back(StackFrame::DirExit(current_dir));

                    // Push children in reverse order for DFS
                    for child in children.iter().rev() {
                        self.stack.push_back(StackFrame::Node(child));
                    }

                    Some(TreeWalkerItem::EnterDirectory(current_dir))
                }
                _ => Some(TreeWalkerItem::File(file)),
            },
            StackFrame::DirExit(dir) => Some(TreeWalkerItem::ExitDirectory(dir)),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*; // Import items from the outer module
    use alloc::vec;

    /// The single-extent ceiling is exactly the 32-bit `data_len` range, and
    /// ordinary files validate. The >4 GiB rejection path itself cannot be
    /// exercised in a unit test without allocating a >4 GiB buffer (files are
    /// held in memory as `Vec<u8>`); it is guarded by inspection and the
    /// constant below.
    #[test]
    fn single_extent_ceiling_and_normal_files_validate() {
        assert_eq!(MAX_SINGLE_EXTENT_FILE_LEN, u32::MAX as u64);

        let tree = InputTree::new(
            PathSeparator::ForwardSlash,
            vec![InputEntry::file("hello.txt", vec![0u8; 4096])],
        );
        assert!(validate_input_tree(&tree, None).is_ok());
    }

    #[test]
    fn alignment_only_materializes_new_padding() {
        assert!(!alignment_requires_materialization(2048, 2048));
        assert!(alignment_requires_materialization(2047, 2048));
    }

    #[test]
    fn test_depth_first_tree_walk_iterator() {
        // Define a test file hierarchy
        let file_a = InputEntry::file("root/dir1/fileA.txt", Vec::new());
        let file_b = InputEntry::file("root/dir1/fileB.txt", Vec::new());
        let file_c = InputEntry::file("root/fileC.txt", Vec::new());
        let file_d = InputEntry::file("root/dir2/fileD.txt", Vec::new());
        let file_e = InputEntry::file("root/dir2/subdir/fileE.txt", Vec::new());

        let subdir_node = InputEntry::directory("root/dir2/subdir", vec![file_e.clone()]);

        let dir1_node = InputEntry::directory("root/dir1", vec![file_a.clone(), file_b.clone()]);

        let dir2_node = InputEntry::directory(
            "root/dir2",
            vec![
                file_d.clone(),
                subdir_node.clone(), // Subdirectory
            ],
        );

        let root_level_files = vec![dir1_node.clone(), file_c.clone(), dir2_node.clone()];

        let input_tree = InputTree::new(PathSeparator::ForwardSlash, root_level_files);

        // Create the iterator
        let walker = FileTreeWalker::new(&input_tree);

        // Define the expected sequence of events (depth-first, pre-order for Enter, post-order for Exit)
        let expected_sequence = vec![
            TreeWalkerItem::EnterDirectory(&dir1_node),   // Enter dir1
            TreeWalkerItem::File(&file_a),                // Process fileA
            TreeWalkerItem::File(&file_b),                // Process fileB
            TreeWalkerItem::ExitDirectory(&dir1_node),    // Exit dir1
            TreeWalkerItem::File(&file_c),                // Process fileC
            TreeWalkerItem::EnterDirectory(&dir2_node),   // Enter dir2
            TreeWalkerItem::File(&file_d),                // Process fileD
            TreeWalkerItem::EnterDirectory(&subdir_node), // Enter subdir
            TreeWalkerItem::File(&file_e),                // Process fileE
            TreeWalkerItem::ExitDirectory(&subdir_node),  // Exit subdir
            TreeWalkerItem::ExitDirectory(&dir2_node),    // Exit dir2
        ];

        // Collect all items from the iterator
        let actual_sequence: Vec<TreeWalkerItem> = walker.collect();

        // Assert that the actual sequence matches the expected sequence
        assert_eq!(actual_sequence, expected_sequence);
    }

    #[test]
    fn test_dedup_suffix_l1_with_ext() {
        let ty = EntryType::Level1 {
            supports_lowercase: false,
            supports_rrip: false,
        };
        let result = apply_dedup_suffix(b"README.TXT;1", 1, ty);
        assert_eq!(result, b"README_1.TXT;1");
    }

    #[test]
    fn test_dedup_suffix_l1_no_ext() {
        let ty = EntryType::Level1 {
            supports_lowercase: false,
            supports_rrip: false,
        };
        let result = apply_dedup_suffix(b"FILENAME;1", 1, ty);
        assert_eq!(result, b"FILENA_1;1");
    }

    #[test]
    fn test_dedup_suffix_l2() {
        let ty = EntryType::Level2 {
            supports_lowercase: false,
            supports_rrip: false,
        };
        let result = apply_dedup_suffix(b"LONGFILENAME.EXT;1", 2, ty);
        assert_eq!(result, b"LONGFILENAME_2.EXT;1");
    }

    #[test]
    fn test_dedup_suffix_l3_no_version() {
        let ty = EntryType::Level3 {
            supports_lowercase: false,
            supports_rrip: false,
        };
        let result = apply_dedup_suffix(b"README.TXT", 1, ty);
        assert_eq!(result, b"README_1.TXT");
    }

    #[test]
    fn test_dedup_suffix_distinct() {
        let ty = EntryType::Level1 {
            supports_lowercase: false,
            supports_rrip: false,
        };
        let r1 = apply_dedup_suffix(b"README.TXT;1", 1, ty);
        let r2 = apply_dedup_suffix(b"README.TXT;1", 2, ty);
        let r3 = apply_dedup_suffix(b"README.TXT;1", 3, ty);
        assert_ne!(r1, r2);
        assert_ne!(r2, r3);
        assert_ne!(r1, r3);
    }
}