fast_ntfs 1.0.2

// Copyright 2021-2026 Colin Finck <colin@reactos.org>
// SPDX-License-Identifier: MIT OR Apache-2.0

use core::cmp::Ordering;
use core::fmt;
use core::mem;
use core::num::NonZeroU64;

use alloc::string::String;
use alloc::vec::Vec;
use bitflags::bitflags;
use nt_string::u16strle::U16StrLe;
use zerocopy::byteorder::LittleEndian;
use zerocopy::{FromBytes, Immutable, KnownLayout, U16, U32, Unaligned};

use crate::attribute::{
    NtfsAttribute, NtfsAttributeItem, NtfsAttributeRef, NtfsAttributeType, NtfsAttributes,
    NtfsAttributesRaw, NtfsAttributesRawRef,
};
use crate::attribute_value::NtfsAttributeValue;
use crate::error::{NtfsError, Result};
use crate::file_reference::NtfsFileReference;
use crate::helpers::pod_from_prefix;
use crate::index::NtfsIndex;
use crate::indexes::NtfsFileNameIndex;
use crate::io::{Read, Seek, SeekFrom};
use crate::ntfs::Ntfs;
use crate::record::{Record, RecordHeader, RecordRef};
use crate::structured_values::{
    NtfsAttributeList, NtfsFileName, NtfsFileNameRef, NtfsFileNamespace, NtfsIndexRoot,
    NtfsStandardInformation, NtfsStructuredValueFromResidentAttributeValue,
};
use crate::types::NtfsPosition;
use crate::upcase_table::UpcaseOrd;

/// A list of standardized NTFS File Record Numbers.
///
/// Most of these files store internal NTFS housekeeping information.
///
/// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/index.html>
#[repr(u64)]
pub enum KnownNtfsFileRecordNumber {
    /// A back-reference to the Master File Table (MFT).
    ///
    /// Leads to the same File Record as [`Ntfs::mft_position`].
    MFT = 0,
    /// A mirror copy of the Master File Table (MFT).
    MFTMirr = 1,
    /// The journaling logfile.
    ///
    /// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/logfile.html>
    LogFile = 2,
    /// File containing basic filesystem information and the user-defined volume name.
    ///
    /// You can easily access that information via [`Ntfs::volume_info`] and [`Ntfs::volume_name`].
    Volume = 3,
    /// File defining all attributes supported by this NTFS filesystem.
    ///
    /// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/attrdef.html>
    AttrDef = 4,
    /// The root directory of the filesystem.
    ///
    /// You can easily access it via [`Ntfs::root_directory`].
    RootDirectory = 5,
    /// Map of used clusters.
    ///
    /// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/bitmap.html>
    Bitmap = 6,
    /// A back-reference to the boot sector of the filesystem.
    Boot = 7,
    /// A file consisting of Data Runs to bad cluster ranges.
    ///
    /// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/badclus.html>
    BadClus = 8,
    /// A list of all Security Descriptors used by this filesystem.
    ///
    /// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/secure.html>
    Secure = 9,
    /// The $UpCase file that contains a table of all uppercase characters for the
    /// 65536 characters of the Unicode Basic Multilingual Plane.
    ///
    /// NTFS uses this table to perform case-insensitive comparisons.
    UpCase = 10,
    /// A directory of further files containing housekeeping information.
    ///
    /// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/files/extend.html>
    Extend = 11,
}

#[derive(Clone, Copy, Debug, FromBytes, Immutable, KnownLayout, Unaligned)]
#[repr(C, packed)]
struct FileRecordHeader {
    record_header: RecordHeader,
    sequence_number: U16<LittleEndian>,
    hard_link_count: U16<LittleEndian>,
    first_attribute_offset: U16<LittleEndian>,
    flags: U16<LittleEndian>,
    data_size: U32<LittleEndian>,
    allocated_size: U32<LittleEndian>,
    base_file_record: NtfsFileReference,
    next_attribute_instance: U16<LittleEndian>,
}

bitflags! {
    /// Flags returned by [`NtfsFile::flags`].
    #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
    pub struct NtfsFileFlags: u16 {
        /// Record is in use.
        const IN_USE = 0x0001;
        /// Record is a directory.
        const IS_DIRECTORY = 0x0002;
    }
}

/// Selects which values [`NtfsFile::scan_metadata`] extracts.
#[derive(Clone, Copy, Debug)]
pub struct NtfsFileMetadataOptions<'a> {
    /// Preferred `$FILE_NAME` namespaces, from highest to lowest priority.
    pub namespace_order: &'a [NtfsFileNamespace],
    /// Optional parent File Record Number used to select a particular hard link.
    pub match_parent_record_number: Option<u64>,
    /// Whether to parse `$STANDARD_INFORMATION`.
    pub include_standard_information: bool,
    /// Whether to inspect the unnamed `$DATA` stream.
    pub include_unnamed_data: bool,
    /// Whether to collect named `$DATA` streams.
    pub include_named_data: bool,
}

/// Size metadata for one named `$DATA` stream.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct NtfsFileDataStream {
    pub name: String,
    pub size: u64,
    pub allocated_size: u64,
}

#[derive(Debug)]
struct ScannedDataStream {
    metadata: NtfsFileDataStream,
    name_code_units: Vec<u16>,
}

/// Metadata extracted by one raw File Record attribute scan plus targeted list fallbacks.
#[derive(Clone, Debug)]
pub struct NtfsFileMetadata {
    pub preferred_name: Option<NtfsFileName>,
    pub standard_information: Option<NtfsStandardInformation>,
    pub unnamed_data_size: u64,
    pub unnamed_allocated_size: u64,
    pub named_data_streams: Vec<NtfsFileDataStream>,
}

/// Metadata borrowed from a caller-owned in-place FILE record.
#[derive(Clone, Debug)]
pub struct NtfsFileMetadataRef<'r> {
    pub preferred_name: Option<NtfsFileNameRef<'r>>,
    pub standard_information: Option<NtfsStandardInformation>,
    pub unnamed_data_size: u64,
    pub unnamed_allocated_size: u64,
    pub named_data_streams: Vec<NtfsFileDataStream>,
}

impl fmt::Display for NtfsFileFlags {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(&self.0, f)
    }
}

/// A single NTFS File Record.
///
/// These records are denoted via a `FILE` signature on the filesystem.
///
/// NTFS uses File Records to manage all user-facing files and directories, as well as some internal files for housekeeping.
/// Every File Record consists of [`NtfsAttribute`]s, which may reference additional File Records.
/// Even the Master File Table (MFT) itself is organized as a File Record.
///
/// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/concepts/file_record.html>
///
/// [`NtfsAttribute`]: crate::attribute::NtfsAttribute
#[derive(Clone, Debug)]
pub struct NtfsFile<'n> {
    ntfs: &'n Ntfs,
    record: Record,
    header: FileRecordHeader,
    file_record_number: u64,
}

/// Allocation-free FILE record view borrowed from caller-owned, mutable raw bytes.
///
/// Dropping this view restores update-sequence trailers, so the original bytes can be cached or
/// parsed again. [`scan_metadata`][Self::scan_metadata] returns `None` for records containing
/// `$ATTRIBUTE_LIST` unless every requested value is known to be complete in the base record.
#[derive(Debug)]
pub struct NtfsFileRef<'n, 'r> {
    ntfs: &'n Ntfs,
    record: RecordRef<'r>,
    header: FileRecordHeader,
    file_record_number: u64,
}

impl<'n, 'r> NtfsFileRef<'n, 'r> {
    pub(crate) fn new(
        ntfs: &'n Ntfs,
        position: NonZeroU64,
        file_record_number: u64,
        data: &'r mut [u8],
    ) -> Result<Self> {
        let mut record = RecordRef::new(data, position.into())?;
        let signature = record.signature();
        if signature != *b"FILE" {
            return Err(NtfsError::InvalidFileSignature {
                position: record.position(),
                expected: b"FILE",
                actual: signature,
            });
        }
        record.fixup()?;
        let header = pod_from_prefix::<FileRecordHeader, { mem::size_of::<FileRecordHeader>() }>(
            record.data(),
        )
        .ok_or(NtfsError::BufferTooSmall {
            expected: mem::size_of::<FileRecordHeader>(),
            actual: record.data().len(),
        })?;
        if header.allocated_size.get() > record.len() {
            return Err(NtfsError::InvalidFileAllocatedSize {
                position: record.position(),
                expected: header.allocated_size.get(),
                actual: record.len(),
            });
        }
        if header.data_size.get() > header.allocated_size.get() {
            return Err(NtfsError::InvalidFileUsedSize {
                position: record.position(),
                expected: header.data_size.get(),
                actual: header.allocated_size.get(),
            });
        }
        Ok(Self {
            ntfs,
            record,
            header,
            file_record_number,
        })
    }

    pub fn file_record_number(&self) -> u64 {
        self.file_record_number
    }

    pub fn flags(&self) -> NtfsFileFlags {
        NtfsFileFlags::from_bits_truncate(self.header.flags.get())
    }

    pub fn is_directory(&self) -> bool {
        self.flags().contains(NtfsFileFlags::IS_DIRECTORY)
    }

    /// Scans metadata without allocation or File Record copies.
    ///
    /// Returns `Ok(None)` when a requested structured value is non-resident, or when an
    /// `$ATTRIBUTE_LIST` may contain a better name or requested `$DATA` outside the base record.
    /// The caller should then retry through the owning API to preserve connected attribute
    /// semantics.
    pub fn scan_metadata(
        &self,
        options: NtfsFileMetadataOptions<'_>,
    ) -> Result<Option<NtfsFileMetadataRef<'_>>> {
        let include_data = options.include_unnamed_data || options.include_named_data;
        let mut preferred_name = None;
        let mut standard_information = None;
        let mut unnamed_data_size = 0;
        let mut unnamed_allocated_size = 0;
        let mut unnamed_data_found = false;
        let mut unnamed_data_complete = false;
        let mut named_data_streams = Vec::new();
        let mut has_attribute_list = false;

        for attribute in NtfsAttributesRawRef::new(
            self.record.data(),
            self.record.position(),
            self.header.first_attribute_offset.get(),
            self.header.data_size.get(),
        ) {
            let attribute = attribute?;
            match attribute.ty()? {
                NtfsAttributeType::AttributeList => has_attribute_list = true,
                NtfsAttributeType::FileName if !options.namespace_order.is_empty() => {
                    if !attribute.is_resident() {
                        return Ok(None);
                    }
                    let (value, position) = attribute.resident_value()?;
                    let file_name = NtfsFileNameRef::new(value, position)?;
                    if let Some(rank) = Self::file_name_rank(
                        &file_name,
                        options.namespace_order,
                        options.match_parent_record_number,
                    ) && preferred_name.as_ref().is_none_or(
                        |(best_rank, _): &(usize, NtfsFileNameRef<'_>)| rank < *best_rank,
                    ) {
                        preferred_name = Some((rank, file_name));
                    }
                }
                NtfsAttributeType::StandardInformation
                    if options.include_standard_information && standard_information.is_none() =>
                {
                    if !attribute.is_resident() {
                        return Ok(None);
                    }
                    let (value, position) = attribute.resident_value()?;
                    standard_information =
                        Some(NtfsStandardInformation::from_slice(value, position)?);
                }
                NtfsAttributeType::Data if include_data => {
                    let (stream, is_complete) = self.file_data_stream(&attribute)?;
                    if stream.name.is_empty() {
                        if options.include_unnamed_data && !unnamed_data_found {
                            unnamed_data_found = true;
                            unnamed_data_complete = is_complete;
                            unnamed_data_size = stream.size;
                            unnamed_allocated_size = stream.allocated_size;
                        }
                    } else if options.include_named_data {
                        named_data_streams.push(stream);
                    }
                }
                _ => {}
            }
        }

        if has_attribute_list {
            let preferred_name_complete = options.namespace_order.is_empty()
                || preferred_name.as_ref().is_some_and(|(rank, _)| *rank == 0);
            let requested_data_complete = !options.include_named_data
                && (!options.include_unnamed_data || (unnamed_data_found && unnamed_data_complete));
            if !preferred_name_complete || !requested_data_complete {
                return Ok(None);
            }
        }

        Ok(Some(NtfsFileMetadataRef {
            preferred_name: preferred_name.map(|(_, file_name)| file_name),
            standard_information,
            unnamed_data_size,
            unnamed_allocated_size,
            named_data_streams,
        }))
    }

    fn file_data_stream(
        &self,
        attribute: &NtfsAttributeRef<'_>,
    ) -> Result<(NtfsFileDataStream, bool)> {
        let name = attribute.name()?.to_string_lossy();
        let size = attribute.value_length();
        let (allocated_size, is_complete) = if attribute.is_resident() {
            (0, true)
        } else {
            let mut allocated_size = 0u64;
            let mut represented_size = 0u64;
            let mut runs_are_valid = true;
            for run in attribute.non_resident_value(self.ntfs)?.data_runs() {
                let Ok(run) = run else {
                    runs_are_valid = false;
                    break;
                };
                represented_size = represented_size.saturating_add(run.allocated_size());
                if run.data_position().value().is_some() {
                    allocated_size = allocated_size.saturating_add(run.allocated_size());
                }
            }
            let starts_at_zero = attribute
                .lowest_vcn()
                .is_some_and(|lowest_vcn| lowest_vcn.value() == 0);
            (
                allocated_size,
                starts_at_zero && runs_are_valid && represented_size >= size,
            )
        };
        Ok((
            NtfsFileDataStream {
                name,
                size,
                allocated_size,
            },
            is_complete,
        ))
    }

    fn file_name_rank(
        file_name: &NtfsFileNameRef<'_>,
        namespace_order: &[NtfsFileNamespace],
        match_parent_record_number: Option<u64>,
    ) -> Option<usize> {
        if match_parent_record_number.is_some_and(|parent_record_number| {
            file_name.parent_directory_reference().file_record_number() != parent_record_number
        }) {
            return None;
        }
        namespace_order
            .iter()
            .position(|namespace| *namespace == file_name.namespace())
    }
}

impl<'n> NtfsFile<'n> {
    pub(crate) fn new<T>(
        ntfs: &'n Ntfs,
        fs: &mut T,
        position: NonZeroU64,
        file_record_number: u64,
    ) -> Result<Self>
    where
        T: Read + Seek,
    {
        Self::new_with_buffer(ntfs, fs, position, file_record_number, Vec::new())
    }

    pub(crate) fn new_with_buffer<T>(
        ntfs: &'n Ntfs,
        fs: &mut T,
        position: NonZeroU64,
        file_record_number: u64,
        mut data: Vec<u8>,
    ) -> Result<Self>
    where
        T: Read + Seek,
    {
        data.resize(ntfs.file_record_size() as usize, 0);
        fs.seek(SeekFrom::Start(position.get()))?;
        fs.read_exact(&mut data)?;

        Self::from_data(ntfs, position, file_record_number, data)
    }

    pub(crate) fn from_data(
        ntfs: &'n Ntfs,
        position: NonZeroU64,
        file_record_number: u64,
        data: Vec<u8>,
    ) -> Result<Self> {
        let mut record = Record::new(data, position.into())?;
        Self::validate_signature(&record)?;
        record.fixup()?;
        let header = pod_from_prefix::<FileRecordHeader, { mem::size_of::<FileRecordHeader>() }>(
            record.data(),
        )
        .ok_or(NtfsError::BufferTooSmall {
            expected: mem::size_of::<FileRecordHeader>(),
            actual: record.data().len(),
        })?;

        let file = Self {
            ntfs,
            record,
            header,
            file_record_number,
        };
        file.validate_sizes()?;

        Ok(file)
    }

    /// Returns the allocated size of this NTFS File Record, in bytes.
    pub fn allocated_size(&self) -> u32 {
        self.header.allocated_size.get()
    }

    /// Returns an iterator over all attributes of this file.
    ///
    /// This provides a flattened "data-centric" view of the attributes and abstracts away the filesystem details
    /// to deal with many or large attributes (Attribute Lists and connected attributes).
    /// Use [`NtfsFile::attributes_raw`] to iterate over the plain attributes on the filesystem.
    ///
    /// Due to the abstraction, the iterator returns an [`NtfsAttributeItem`] for each entry.
    ///
    /// [`NtfsAttributeItem`]: crate::NtfsAttributeItem
    pub fn attributes<'f>(&'f self) -> NtfsAttributes<'n, 'f> {
        NtfsAttributes::<'n, 'f>::new(self)
    }

    /// Returns an iterator over all top-level attributes of this file.
    ///
    /// Contrary to [`NtfsFile::attributes`], it does not traverse $ATTRIBUTE_LIST attributes, but returns
    /// them as raw attributes.
    /// Check that function if you want an iterator providing a flattened "data-centric" view over
    /// the attributes by traversing Attribute Lists automatically.
    ///
    /// The iterator returns an [`NtfsAttribute`] for each entry.
    ///
    /// [`NtfsAttribute`]: crate::NtfsAttribute
    pub fn attributes_raw<'f>(&'f self) -> NtfsAttributesRaw<'n, 'f> {
        NtfsAttributesRaw::new(self)
    }

    /// Convenience function to get a $DATA attribute of this file.
    ///
    /// As NTFS supports multiple data streams per file, you can specify the name of the $DATA attribute
    /// to look up.
    /// Passing an empty string here looks up the default unnamed $DATA attribute (commonly known as the "file data").
    /// The name is looked up case-insensitively.
    ///
    /// If you need more control over which $DATA attribute is available and picked up,
    /// you can use [`NtfsFile::attributes`] to iterate over all attributes of this file.
    ///
    /// # Panics
    ///
    /// Panics if `data_stream_name` is non-empty and [`read_upcase_table`][Ntfs::read_upcase_table] had not been
    /// called on the passed [`Ntfs`] object.
    pub fn data<'f, T>(
        &'f self,
        fs: &mut T,
        data_stream_name: &str,
    ) -> Option<Result<NtfsAttributeItem<'n, 'f>>>
    where
        T: Read + Seek,
    {
        self.find_attribute(fs, NtfsAttributeType::Data, data_stream_name)
    }

    /// Finds an attribute by type and name without flattening unrelated `$ATTRIBUTE_LIST` entries.
    ///
    /// Resident attributes in the base File Record are returned immediately. A local non-resident
    /// attribute is also returned directly when no `$ATTRIBUTE_LIST` exists. Otherwise this method
    /// filters list entries by type, name, and `lowest_vcn` before loading the referenced extension
    /// File Record. Connected non-resident attributes retain the list iterator needed to combine
    /// all of their data runs.
    ///
    /// Empty names are compared directly. Non-empty names are compared case-insensitively and
    /// require the `$UpCase` table to have been loaded, just like [`NtfsFile::data`].
    pub fn find_attribute<'f, T>(
        &'f self,
        fs: &mut T,
        ty: NtfsAttributeType,
        name: &str,
    ) -> Option<Result<NtfsAttributeItem<'n, 'f>>>
    where
        T: Read + Seek,
    {
        let mut local_match = None;
        let mut attribute_lists = Vec::new();

        for attribute in self.attributes_raw() {
            let attribute = iter_try!(attribute);
            let attribute_ty = iter_try!(attribute.ty());
            if attribute_ty == ty
                && Self::attribute_name_matches(self.ntfs, iter_try!(attribute.name()), name)
            {
                if attribute.is_resident() || ty == NtfsAttributeType::AttributeList {
                    return Some(Ok(NtfsAttributeItem::from_attribute(attribute, None)));
                }
                local_match = Some(attribute.clone());
            }
            if attribute_ty == NtfsAttributeType::AttributeList {
                attribute_lists.push(attribute);
            }
        }

        if attribute_lists.is_empty() {
            return local_match
                .map(|attribute| Ok(NtfsAttributeItem::from_attribute(attribute, None)));
        }

        for attribute in attribute_lists {
            let attribute_list = iter_try!(attribute.structured_value::<T, NtfsAttributeList>(fs));
            let mut entries = attribute_list.entries();
            loop {
                let entries_checkpoint = entries.clone();
                let Some(entry) = entries.next(fs) else {
                    break;
                };
                let entry = iter_try!(entry);
                if iter_try!(entry.ty()) != ty
                    || entry.lowest_vcn().value() != 0
                    || !Self::attribute_name_matches(self.ntfs, entry.name(), name)
                {
                    continue;
                }

                let entry_record_number = entry.base_file_reference().file_record_number();
                if entry_record_number == self.file_record_number() {
                    let entry_attribute = iter_try!(entry.to_attribute(self));
                    return Some(Ok(NtfsAttributeItem::from_attribute(
                        entry_attribute,
                        Some(entries_checkpoint),
                    )));
                }

                let entry_file = iter_try!(entry.to_file(self.ntfs(), fs));
                return Some(NtfsAttributeItem::from_attribute_list_entry(
                    self,
                    entry_file,
                    &entry,
                    entries_checkpoint,
                ));
            }
        }

        local_match.map(|attribute| Ok(NtfsAttributeItem::from_attribute(attribute, None)))
    }

    fn attribute_name_matches(ntfs: &Ntfs, actual: U16StrLe<'_>, expected: &str) -> bool {
        if expected.is_empty() {
            actual.is_empty()
        } else {
            actual.upcase_cmp(ntfs, &expected) == Ordering::Equal
        }
    }

    /// Returns the size actually used by data of this NTFS File Record, in bytes.
    ///
    /// This is less or equal than [`NtfsFile::allocated_size`].
    pub fn data_size(&self) -> u32 {
        self.header.data_size.get()
    }

    /// Convenience function to return an [`NtfsIndex`] if this file is a directory.
    /// This structure can be used to iterate over all files of this directory or a find a specific one.
    ///
    /// Apart from any propagated error, this function may return [`NtfsError::NotADirectory`]
    /// if this [`NtfsFile`] is not a directory.
    ///
    /// If you need more control over the picked up $INDEX_ROOT and $INDEX_ALLOCATION attributes
    /// you can use [`NtfsFile::attributes`] to iterate over all attributes of this file.
    pub fn directory_index<'f, T>(
        &'f self,
        fs: &mut T,
    ) -> Result<NtfsIndex<'n, 'f, NtfsFileNameIndex>>
    where
        T: Read + Seek,
    {
        if !self.is_directory() {
            return Err(NtfsError::NotADirectory {
                position: self.position(),
            });
        }

        // A File Record may contain multiple indexes, so we have to match the name of the directory index.
        let directory_index_name = "$I30";

        let mut attributes = self.attributes();
        let mut index_root_item = None;
        let mut index_allocation_item = None;
        while let Some(item) = attributes.next(fs) {
            let item = item?;
            let attribute = item.to_attribute()?;
            let ty = attribute.ty()?;
            if !matches!(
                ty,
                NtfsAttributeType::IndexRoot | NtfsAttributeType::IndexAllocation
            ) || attribute.name()? != directory_index_name
            {
                continue;
            }

            match ty {
                NtfsAttributeType::IndexRoot => index_root_item = Some(item),
                NtfsAttributeType::IndexAllocation => index_allocation_item = Some(item),
                _ => unreachable!(),
            }

            if index_root_item.is_some() && index_allocation_item.is_some() {
                break;
            }
        }

        let index_root_item = index_root_item.ok_or(NtfsError::AttributeNotFound {
            position: self.position(),
            ty: NtfsAttributeType::IndexRoot,
        })?;
        let index_root_attribute = index_root_item.to_attribute()?;
        let index_root = index_root_attribute.resident_structured_value::<NtfsIndexRoot>()?;
        if index_root.is_large_index() && index_allocation_item.is_none() {
            return Err(NtfsError::AttributeNotFound {
                position: self.position(),
                ty: NtfsAttributeType::IndexAllocation,
            });
        }

        NtfsIndex::<NtfsFileNameIndex>::new_with_fs_from_index_root(
            index_root,
            index_allocation_item,
            fs,
        )
    }

    /// Returns the NTFS File Record Number of this file.
    ///
    /// This number uniquely identifies this file and can be used to recreate this [`NtfsFile`]
    /// object via [`Ntfs::file`].
    pub fn file_record_number(&self) -> u64 {
        self.file_record_number
    }

    /// Finds a resident attribute of a specific type, optionally with a specific name and/or a specific
    /// instance identifier, and returns it.
    /// Returns [`NtfsError::AttributeNotFound`] if no such resident attribute could be found.
    ///
    /// The attribute type is given through the passed structured value type parameter.
    ///
    /// Note that this function DOES NOT traverse Attribute Lists!
    pub(crate) fn find_resident_attribute<'f>(
        &'f self,
        ty: NtfsAttributeType,
        match_name: Option<&str>,
        match_instance: Option<u16>,
    ) -> Result<NtfsAttribute<'n, 'f>> {
        // Resident attributes are always stored on the top-level (we don't have to dig into Attribute Lists).
        for attribute in self.attributes_raw() {
            let attribute = attribute?;

            if attribute.ty()? != ty {
                continue;
            }

            if let Some(instance) = match_instance
                && attribute.instance() != instance
            {
                continue;
            }

            if let Some(name) = match_name
                && attribute.name()? != name
            {
                continue;
            }

            return Ok(attribute);
        }

        Err(NtfsError::AttributeNotFound {
            position: self.position(),
            ty,
        })
    }

    /// Finds a resident attribute of a specific type, optionally with a specific name, and returns its structured value.
    /// Returns [`NtfsError::AttributeNotFound`] if no such resident attribute could be found.
    ///
    /// The attribute type is given through the passed structured value type parameter.
    ///
    /// Note that this function DOES NOT traverse Attribute Lists!
    pub(crate) fn find_resident_attribute_structured_value<'f, S>(
        &'f self,
        match_name: Option<&str>,
    ) -> Result<S>
    where
        S: NtfsStructuredValueFromResidentAttributeValue<'n, 'f>,
    {
        let attribute = self.find_resident_attribute(S::TY, match_name, None)?;
        attribute.resident_structured_value::<S>()
    }

    pub(crate) fn first_attribute_offset(&self) -> u16 {
        self.header.first_attribute_offset.get()
    }

    /// Returns flags set for this file as specified by [`NtfsFileFlags`].
    pub fn flags(&self) -> NtfsFileFlags {
        NtfsFileFlags::from_bits_truncate(self.header.flags.get())
    }

    /// Returns the number of hard links to this NTFS File Record.
    pub fn hard_link_count(&self) -> u16 {
        self.header.hard_link_count.get()
    }

    /// Convenience function to get the $STANDARD_INFORMATION attribute of this file
    /// (see [`NtfsStandardInformation`]).
    ///
    /// This internally calls [`NtfsFile::attributes_raw`] to iterate through the file's
    /// attributes and pick up the first $STANDARD_INFORMATION attribute.
    pub fn info(&self) -> Result<NtfsStandardInformation> {
        self.find_resident_attribute_structured_value::<NtfsStandardInformation>(None)
    }

    /// Returns whether this NTFS File Record represents a directory.
    pub fn is_directory(&self) -> bool {
        self.flags().contains(NtfsFileFlags::IS_DIRECTORY)
    }

    /// Consumes this file and returns its record buffer for reuse with [`Ntfs::file_with_buffer`].
    pub fn into_buffer(self) -> Vec<u8> {
        self.record.into_data()
    }

    /// Convenience function to get a $FILE_NAME attribute of this file (see [`NtfsFileName`]).
    ///
    /// A file may have multiple $FILE_NAME attributes for each [`NtfsFileNamespace`].
    /// Files with hard links have further $FILE_NAME attributes for each directory they are in.
    /// You may optionally filter for a namespace and parent directory via the parameters.
    ///
    /// This internally calls [`NtfsFile::attributes`] to iterate through the file's
    /// attributes and pick up the first matching $FILE_NAME attribute.
    pub fn name<T>(
        &self,
        fs: &mut T,
        match_namespace: Option<NtfsFileNamespace>,
        match_parent_record_number: Option<u64>,
    ) -> Option<Result<NtfsFileName>>
    where
        T: Read + Seek,
    {
        let mut iter = self.attributes();

        while let Some(item) = iter.next(fs) {
            let item = iter_try!(item);
            let attribute = iter_try!(item.to_attribute());

            let ty = iter_try!(attribute.ty());
            if ty != NtfsAttributeType::FileName {
                continue;
            }

            let file_name = iter_try!(attribute.structured_value::<_, NtfsFileName>(fs));

            if let Some(namespace) = match_namespace
                && file_name.namespace() != namespace
            {
                continue;
            }

            if let Some(parent_record_number) = match_parent_record_number
                && file_name.parent_directory_reference().file_record_number()
                    != parent_record_number
            {
                continue;
            }

            return Some(Ok(file_name));
        }

        None
    }

    /// Returns the best `$FILE_NAME` according to `namespace_order` and an optional parent.
    ///
    /// The base File Record is scanned first without following `$ATTRIBUTE_LIST`. If a local name
    /// satisfies the highest namespace priority, it is returned immediately. Only when a better
    /// candidate may live in an extension record does this method inspect `$ATTRIBUTE_LIST`, and
    /// then it loads only entries whose type is `$FILE_NAME`.
    ///
    /// An empty `namespace_order` accepts no names and returns `None`.
    pub fn preferred_name<T>(
        &self,
        fs: &mut T,
        namespace_order: &[NtfsFileNamespace],
        match_parent_record_number: Option<u64>,
    ) -> Option<Result<NtfsFileName>>
    where
        T: Read + Seek,
    {
        if namespace_order.is_empty() {
            return None;
        }

        let mut best = None;
        for attribute in self.attributes_raw() {
            let attribute = iter_try!(attribute);
            if iter_try!(attribute.ty()) != NtfsAttributeType::FileName {
                continue;
            }

            let file_name = iter_try!(attribute.structured_value::<T, NtfsFileName>(fs));
            let Some(rank) =
                Self::file_name_rank(&file_name, namespace_order, match_parent_record_number)
            else {
                continue;
            };
            if rank == 0 {
                return Some(Ok(file_name));
            }
            if best
                .as_ref()
                .is_none_or(|(best_rank, _): &(usize, NtfsFileName)| rank < *best_rank)
            {
                best = Some((rank, file_name));
            }
        }

        for attribute in self.attributes_raw() {
            let attribute = iter_try!(attribute);
            if iter_try!(attribute.ty()) != NtfsAttributeType::AttributeList {
                continue;
            }

            let attribute_list = iter_try!(attribute.structured_value::<T, NtfsAttributeList>(fs));
            let mut entries = attribute_list.entries();
            while let Some(entry) = entries.next(fs) {
                let entry = iter_try!(entry);
                if iter_try!(entry.ty()) != NtfsAttributeType::FileName
                    || entry.base_file_reference().file_record_number() == self.file_record_number()
                {
                    continue;
                }

                let entry_file = iter_try!(entry.to_file(self.ntfs(), fs));
                let entry_attribute = iter_try!(entry.to_attribute(&entry_file));
                let file_name = iter_try!(entry_attribute.structured_value::<T, NtfsFileName>(fs));
                let Some(rank) =
                    Self::file_name_rank(&file_name, namespace_order, match_parent_record_number)
                else {
                    continue;
                };
                if rank == 0 {
                    return Some(Ok(file_name));
                }
                if best
                    .as_ref()
                    .is_none_or(|(best_rank, _): &(usize, NtfsFileName)| rank < *best_rank)
                {
                    best = Some((rank, file_name));
                }
            }
        }

        best.map(|(_, file_name)| Ok(file_name))
    }

    fn file_name_rank(
        file_name: &NtfsFileName,
        namespace_order: &[NtfsFileNamespace],
        match_parent_record_number: Option<u64>,
    ) -> Option<usize> {
        if match_parent_record_number.is_some_and(|parent_record_number| {
            file_name.parent_directory_reference().file_record_number() != parent_record_number
        }) {
            return None;
        }

        namespace_order
            .iter()
            .position(|namespace| *namespace == file_name.namespace())
    }

    /// Extracts the scan-oriented metadata of this file in one raw attribute traversal.
    ///
    /// `$ATTRIBUTE_LIST` entries are then visited once, and only extension records needed for a
    /// better file name or requested `$DATA` streams are loaded. Connected non-resident data keeps
    /// its entry checkpoint, so logical and allocated sizes cover every continuation extent.
    pub fn scan_metadata<T>(
        &self,
        fs: &mut T,
        options: NtfsFileMetadataOptions<'_>,
    ) -> Result<NtfsFileMetadata>
    where
        T: Read + Seek,
    {
        let include_data = options.include_unnamed_data || options.include_named_data;
        let mut preferred_name = None;
        let mut standard_information = None;
        let mut local_data_attributes = Vec::new();
        let mut attribute_lists = Vec::new();

        for attribute in self.attributes_raw() {
            let attribute = attribute?;
            match attribute.ty()? {
                NtfsAttributeType::FileName if !options.namespace_order.is_empty() => {
                    let file_name = attribute.structured_value::<T, NtfsFileName>(fs)?;
                    if let Some(rank) = Self::file_name_rank(
                        &file_name,
                        options.namespace_order,
                        options.match_parent_record_number,
                    ) && preferred_name
                        .as_ref()
                        .is_none_or(|(best_rank, _): &(usize, NtfsFileName)| rank < *best_rank)
                    {
                        preferred_name = Some((rank, file_name));
                    }
                }
                NtfsAttributeType::StandardInformation
                    if options.include_standard_information && standard_information.is_none() =>
                {
                    standard_information =
                        Some(attribute.resident_structured_value::<NtfsStandardInformation>()?);
                }
                NtfsAttributeType::Data if include_data => {
                    local_data_attributes.push(attribute);
                }
                NtfsAttributeType::AttributeList => attribute_lists.push(attribute),
                _ => {}
            }
        }

        let mut unnamed_data_size = 0;
        let mut unnamed_allocated_size = 0;
        let mut unnamed_data_found = false;
        let mut named_data_streams = Vec::new();
        let mut named_data_stream_names = Vec::new();

        for attribute in &attribute_lists {
            let attribute_list = attribute.structured_value::<T, NtfsAttributeList>(fs)?;
            let mut entries = attribute_list.entries();
            loop {
                let entries_checkpoint = entries.clone();
                let Some(entry) = entries.next(fs) else {
                    break;
                };
                let entry = entry?;
                match entry.ty()? {
                    NtfsAttributeType::FileName
                        if !options.namespace_order.is_empty()
                            && preferred_name.as_ref().is_none_or(|(rank, _)| *rank != 0) =>
                    {
                        if entry.base_file_reference().file_record_number()
                            == self.file_record_number()
                        {
                            continue;
                        }
                        let entry_file = entry.to_file(self.ntfs(), fs)?;
                        let entry_attribute = entry.to_attribute(&entry_file)?;
                        let file_name = entry_attribute.structured_value::<T, NtfsFileName>(fs)?;
                        if let Some(rank) = Self::file_name_rank(
                            &file_name,
                            options.namespace_order,
                            options.match_parent_record_number,
                        ) && preferred_name
                            .as_ref()
                            .is_none_or(|(best_rank, _): &(usize, NtfsFileName)| rank < *best_rank)
                        {
                            preferred_name = Some((rank, file_name));
                        }
                    }
                    NtfsAttributeType::Data if include_data && entry.lowest_vcn().value() == 0 => {
                        let entry_name = entry.name();
                        if (!entry_name.is_empty() && !options.include_named_data)
                            || (entry_name.is_empty()
                                && (!options.include_unnamed_data || unnamed_data_found))
                        {
                            continue;
                        }

                        let item = self.attribute_list_item(&entry, entries_checkpoint, fs)?;
                        let stream = Self::file_data_stream(&item, fs)?;
                        Self::record_data_stream(
                            stream,
                            options,
                            &mut unnamed_data_found,
                            &mut unnamed_data_size,
                            &mut unnamed_allocated_size,
                            &mut named_data_streams,
                            &mut named_data_stream_names,
                        );
                    }
                    _ => {}
                }
            }
        }

        // A consistent Attribute List contains every attribute. Retain local fallbacks for damaged
        // or partially reconstructed records, while de-duplicating streams already found above.
        for attribute in local_data_attributes {
            let name = attribute.name()?;
            if (name.is_empty() && (!options.include_unnamed_data || unnamed_data_found))
                || (!name.is_empty()
                    && (!options.include_named_data
                        || named_data_stream_names.iter().any(|existing_name| {
                            name.u16_iter().eq(existing_name.iter().copied())
                        })))
            {
                continue;
            }
            let item = NtfsAttributeItem::from_attribute(attribute, None);
            let stream = Self::file_data_stream(&item, fs)?;
            Self::record_data_stream(
                stream,
                options,
                &mut unnamed_data_found,
                &mut unnamed_data_size,
                &mut unnamed_allocated_size,
                &mut named_data_streams,
                &mut named_data_stream_names,
            );
        }

        Ok(NtfsFileMetadata {
            preferred_name: preferred_name.map(|(_, file_name)| file_name),
            standard_information,
            unnamed_data_size,
            unnamed_allocated_size,
            named_data_streams,
        })
    }

    fn attribute_list_item<'f, T>(
        &'f self,
        entry: &crate::structured_values::NtfsAttributeListEntry,
        entries_checkpoint: crate::structured_values::NtfsAttributeListEntries<'n, 'f>,
        fs: &mut T,
    ) -> Result<NtfsAttributeItem<'n, 'f>>
    where
        T: Read + Seek,
    {
        if entry.base_file_reference().file_record_number() == self.file_record_number() {
            let entry_attribute = entry.to_attribute(self)?;
            return Ok(NtfsAttributeItem::from_attribute(
                entry_attribute,
                Some(entries_checkpoint),
            ));
        }

        let entry_file = entry.to_file(self.ntfs(), fs)?;
        NtfsAttributeItem::from_attribute_list_entry(self, entry_file, entry, entries_checkpoint)
    }

    fn file_data_stream<T>(
        item: &NtfsAttributeItem<'n, '_>,
        fs: &mut T,
    ) -> Result<ScannedDataStream>
    where
        T: Read + Seek,
    {
        let attribute = item.to_attribute()?;
        let name = attribute.name()?;
        let name_code_units = name.u16_iter().collect();
        let name = name.to_string_lossy();
        let size = attribute.value_length();
        let allocated_size = match attribute.value(fs)? {
            NtfsAttributeValue::Resident(_) => 0,
            NtfsAttributeValue::NonResident(value) => value
                .data_runs()
                .filter_map(|run| run.ok())
                .filter(|run| run.data_position().value().is_some())
                .fold(0u64, |total, run| {
                    total.saturating_add(run.allocated_size())
                }),
            NtfsAttributeValue::AttributeListNonResident(value) => {
                let mut total = 0u64;
                value.for_each_data_run(fs, |run| {
                    if run.data_position().value().is_some() {
                        total = total.saturating_add(run.allocated_size());
                    }
                    Ok(())
                })?;
                total
            }
        };

        Ok(ScannedDataStream {
            metadata: NtfsFileDataStream {
                name,
                size,
                allocated_size,
            },
            name_code_units,
        })
    }

    fn record_data_stream(
        stream: ScannedDataStream,
        options: NtfsFileMetadataOptions<'_>,
        unnamed_data_found: &mut bool,
        unnamed_data_size: &mut u64,
        unnamed_allocated_size: &mut u64,
        named_data_streams: &mut Vec<NtfsFileDataStream>,
        named_data_stream_names: &mut Vec<Vec<u16>>,
    ) {
        if stream.name_code_units.is_empty() {
            if options.include_unnamed_data && !*unnamed_data_found {
                *unnamed_data_found = true;
                *unnamed_data_size = stream.metadata.size;
                *unnamed_allocated_size = stream.metadata.allocated_size;
            }
        } else if options.include_named_data
            && !named_data_stream_names
                .iter()
                .any(|existing| existing == &stream.name_code_units)
        {
            named_data_stream_names.push(stream.name_code_units);
            named_data_streams.push(stream.metadata);
        }
    }

    /// Returns the [`Ntfs`] object reference associated to this file.
    pub fn ntfs(&self) -> &'n Ntfs {
        self.ntfs
    }

    /// Returns the absolute byte position of this File Record in the NTFS filesystem.
    pub fn position(&self) -> NtfsPosition {
        self.record.position()
    }

    pub(crate) fn record_data(&self) -> &[u8] {
        self.record.data()
    }

    /// Returns the sequence number of this file.
    ///
    /// NTFS reuses records of deleted files when new files are created.
    /// This number is incremented every time a file is deleted.
    /// Hence, it gives a count how many time this File Record has been reused.
    pub fn sequence_number(&self) -> u16 {
        self.header.sequence_number.get()
    }

    fn validate_signature(record: &Record) -> Result<()> {
        let signature = &record.signature();
        let expected = b"FILE";

        if signature == expected {
            Ok(())
        } else {
            Err(NtfsError::InvalidFileSignature {
                position: record.position(),
                expected,
                actual: *signature,
            })
        }
    }

    fn validate_sizes(&self) -> Result<()> {
        if self.allocated_size() > self.record.len() {
            return Err(NtfsError::InvalidFileAllocatedSize {
                position: self.record.position(),
                expected: self.allocated_size(),
                actual: self.record.len(),
            });
        }

        if self.data_size() > self.allocated_size() {
            return Err(NtfsError::InvalidFileUsedSize {
                position: self.record.position(),
                expected: self.data_size(),
                actual: self.allocated_size(),
            });
        }

        Ok(())
    }
}

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

    fn scanned_stream(name_code_units: &[u16], size: u64) -> ScannedDataStream {
        ScannedDataStream {
            metadata: NtfsFileDataStream {
                name: String::from_utf16_lossy(name_code_units),
                size,
                allocated_size: 0,
            },
            name_code_units: name_code_units.to_vec(),
        }
    }

    #[test]
    fn data_stream_deduplication_uses_original_utf16_code_units() {
        let options = NtfsFileMetadataOptions {
            namespace_order: &[],
            match_parent_record_number: None,
            include_standard_information: false,
            include_unnamed_data: false,
            include_named_data: true,
        };
        let mut unnamed_data_found = false;
        let mut unnamed_data_size = 0;
        let mut unnamed_allocated_size = 0;
        let mut named_data_streams = Vec::new();
        let mut named_data_stream_names = Vec::new();

        for stream in [
            scanned_stream(&[0xd800], 1),
            scanned_stream(&[0xd801], 2),
            scanned_stream(&[0xd800], 3),
        ] {
            NtfsFile::<'static>::record_data_stream(
                stream,
                options,
                &mut unnamed_data_found,
                &mut unnamed_data_size,
                &mut unnamed_allocated_size,
                &mut named_data_streams,
                &mut named_data_stream_names,
            );
        }

        assert_eq!(named_data_streams.len(), 2);
        assert_eq!(named_data_streams[0].name, named_data_streams[1].name);
        assert_eq!(named_data_streams[0].size, 1);
        assert_eq!(named_data_streams[1].size, 2);
        assert_eq!(named_data_stream_names, vec![vec![0xd800], vec![0xd801]]);
    }
}