fast_ntfs 1.0.1

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

use core::iter::FusedIterator;
use core::ops::Range;
use core::{fmt, mem};

use crate::io::{Read, Seek};
use bitflags::bitflags;
use derive_more::Display;
use nt_string::u16strle::U16StrLe;
use zerocopy::byteorder::LittleEndian;
use zerocopy::{FromBytes, Immutable, KnownLayout, U16, U32, U64, Unaligned};

use crate::attribute_value::{
    NtfsAttributeListNonResidentAttributeValue, NtfsAttributeValue, NtfsNonResidentAttributeValue,
    NtfsResidentAttributeValue,
};
use crate::error::{NtfsError, Result};
use crate::file::NtfsFile;
use crate::helpers::pod_from_prefix;
use crate::structured_values::{
    NtfsAttributeList, NtfsAttributeListEntries, NtfsStructuredValue,
    NtfsStructuredValueFromResidentAttributeValue,
};
use crate::types::{NtfsPosition, Vcn};

/// Size of all [`NtfsAttributeHeader`] fields.
const ATTRIBUTE_HEADER_SIZE: usize = mem::size_of::<NtfsAttributeHeader>();

/// On-disk structure of the generic header of an NTFS Attribute.
#[derive(Clone, Copy, Debug, FromBytes, Immutable, KnownLayout, Unaligned)]
#[repr(C, packed)]
struct NtfsAttributeHeader {
    /// Type of the attribute, known types are in [`NtfsAttributeType`].
    ty: U32<LittleEndian>,
    /// Length of the resident part of this attribute, in bytes.
    length: U32<LittleEndian>,
    /// 0 if this attribute has a resident value, 1 if this attribute has a non-resident value.
    is_non_resident: u8,
    /// Length of the name, in UTF-16 code points (every code point is 2 bytes).
    name_length: u8,
    /// Offset to the beginning of the name, in bytes from the beginning of this header.
    name_offset: U16<LittleEndian>,
    /// Flags of the attribute, known flags are in [`NtfsAttributeFlags`].
    flags: U16<LittleEndian>,
    /// Identifier of this attribute that is unique within the [`NtfsFile`].
    instance: U16<LittleEndian>,
}

bitflags! {
    /// Flags returned by [`NtfsAttribute::flags`].
    #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
    pub struct NtfsAttributeFlags: u16 {
        /// The attribute value is compressed.
        const COMPRESSED = 0x0001;
        /// The attribute value is encrypted.
        const ENCRYPTED = 0x4000;
        /// The attribute value is stored sparsely.
        const SPARSE = 0x8000;
    }
}

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

/// On-disk structure of the extra header of an NTFS Attribute that has a resident value.
#[derive(Clone, Copy, Debug, FromBytes, Immutable, KnownLayout, Unaligned)]
#[repr(C, packed)]
struct NtfsResidentAttributeHeader {
    attribute_header: NtfsAttributeHeader,
    /// Length of the value, in bytes.
    value_length: U32<LittleEndian>,
    /// Offset to the beginning of the value, in bytes from the beginning of the [`NtfsAttributeHeader`].
    value_offset: U16<LittleEndian>,
    /// 1 if this attribute (with resident value) is referenced in an index.
    indexed_flag: u8,
    reserved: u8,
}

/// On-disk structure of the extra header of an NTFS Attribute that has a non-resident value.
#[derive(Clone, Copy, Debug, FromBytes, Immutable, KnownLayout, Unaligned)]
#[repr(C, packed)]
struct NtfsNonResidentAttributeHeader {
    attribute_header: NtfsAttributeHeader,
    /// Lower boundary of Virtual Cluster Numbers (VCNs) referenced by this attribute.
    /// This becomes relevant when file data is split over multiple attributes.
    /// Otherwise, it's zero.
    lowest_vcn: Vcn,
    /// Upper boundary of Virtual Cluster Numbers (VCNs) referenced by this attribute.
    /// This becomes relevant when file data is split over multiple attributes.
    /// Otherwise, it's zero (or even -1 for zero-length files according to NTFS-3G).
    highest_vcn: Vcn,
    /// Offset to the beginning of the value data runs.
    data_runs_offset: U16<LittleEndian>,
    /// Binary exponent denoting the number of clusters in a compression unit.
    /// A typical value is 4, meaning that 2^4 = 16 clusters are part of a compression unit.
    /// A value of zero means no compression (but that should better be determined via
    /// [`NtfsAttributeFlags`]).
    compression_unit_exponent: u8,
    reserved: [u8; 5],
    /// Allocated space for the attribute value, in bytes. This is always a multiple of the cluster size.
    /// For compressed files, this is always a multiple of the compression unit size.
    allocated_size: U64<LittleEndian>,
    /// Size of the attribute value, in bytes.
    /// This can be larger than `allocated_size` if the value is compressed or stored sparsely.
    data_size: U64<LittleEndian>,
    /// Size of the initialized part of the attribute value, in bytes.
    /// This is usually the same as `data_size`.
    initialized_size: U64<LittleEndian>,
}

#[derive(Clone, Copy, Debug)]
enum NtfsAttributeHeaderKind {
    Resident(NtfsResidentAttributeHeader),
    NonResident(NtfsNonResidentAttributeHeader),
}

impl NtfsAttributeHeaderKind {
    fn common(&self) -> &NtfsAttributeHeader {
        match self {
            Self::Resident(header) => &header.attribute_header,
            Self::NonResident(header) => &header.attribute_header,
        }
    }
}

/// All known NTFS Attribute types.
///
/// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/attributes/index.html>
#[derive(Clone, Copy, Debug, Display, Eq, PartialEq)]
#[repr(u32)]
pub enum NtfsAttributeType {
    /// $STANDARD_INFORMATION, see [`NtfsStandardInformation`].
    ///
    /// [`NtfsStandardInformation`]: crate::structured_values::NtfsStandardInformation
    StandardInformation = 0x10,
    /// $ATTRIBUTE_LIST, see [`NtfsAttributeList`].
    ///
    /// [`NtfsAttributeList`]: crate::structured_values::NtfsAttributeList
    AttributeList = 0x20,
    /// $FILE_NAME, see [`NtfsFileName`].
    ///
    /// [`NtfsFileName`]: crate::structured_values::NtfsFileName
    FileName = 0x30,
    /// $OBJECT_ID, see [`NtfsObjectId`].
    ///
    /// [`NtfsObjectId`]: crate::structured_values::NtfsObjectId
    ObjectId = 0x40,
    /// $SECURITY_DESCRIPTOR
    SecurityDescriptor = 0x50,
    /// $VOLUME_NAME, see [`NtfsVolumeName`].
    ///
    /// [`NtfsVolumeName`]: crate::structured_values::NtfsVolumeName
    VolumeName = 0x60,
    /// $VOLUME_INFORMATION, see [`NtfsVolumeInformation`].
    ///
    /// [`NtfsVolumeInformation`]: crate::structured_values::NtfsVolumeInformation
    VolumeInformation = 0x70,
    /// $DATA, see [`NtfsFile::data`].
    Data = 0x80,
    /// $INDEX_ROOT, see [`NtfsIndexRoot`].
    ///
    /// [`NtfsIndexRoot`]: crate::structured_values::NtfsIndexRoot
    IndexRoot = 0x90,
    /// $INDEX_ALLOCATION, see [`NtfsIndexAllocation`].
    ///
    /// [`NtfsIndexAllocation`]: crate::structured_values::NtfsIndexAllocation
    IndexAllocation = 0xA0,
    /// $BITMAP
    Bitmap = 0xB0,
    /// $REPARSE_POINT
    ReparsePoint = 0xC0,
    /// $EA_INFORMATION
    EAInformation = 0xD0,
    /// $EA
    EA = 0xE0,
    /// $PROPERTY_SET
    PropertySet = 0xF0,
    /// $LOGGED_UTILITY_STREAM
    LoggedUtilityStream = 0x100,
    /// Marks the end of the valid attributes.
    End = 0xFFFF_FFFF,
}

impl TryFrom<u32> for NtfsAttributeType {
    type Error = ();

    fn try_from(value: u32) -> core::result::Result<Self, Self::Error> {
        match value {
            0x10 => Ok(Self::StandardInformation),
            0x20 => Ok(Self::AttributeList),
            0x30 => Ok(Self::FileName),
            0x40 => Ok(Self::ObjectId),
            0x50 => Ok(Self::SecurityDescriptor),
            0x60 => Ok(Self::VolumeName),
            0x70 => Ok(Self::VolumeInformation),
            0x80 => Ok(Self::Data),
            0x90 => Ok(Self::IndexRoot),
            0xA0 => Ok(Self::IndexAllocation),
            0xB0 => Ok(Self::Bitmap),
            0xC0 => Ok(Self::ReparsePoint),
            0xD0 => Ok(Self::EAInformation),
            0xE0 => Ok(Self::EA),
            0xF0 => Ok(Self::PropertySet),
            0x100 => Ok(Self::LoggedUtilityStream),
            0xFFFF_FFFF => Ok(Self::End),
            _ => Err(()),
        }
    }
}

/// A single NTFS Attribute of an [`NtfsFile`].
///
/// Not to be confused with [`NtfsFileAttributeFlags`].
///
/// This structure is returned by the [`NtfsAttributesRaw`] iterator as well as [`NtfsAttributeItem::to_attribute`].
///
/// Reference: <https://flatcap.github.io/linux-ntfs/ntfs/concepts/attribute_header.html>
///
/// [`NtfsFileAttributeFlags`]: crate::structured_values::NtfsFileAttributeFlags
#[derive(Clone, Debug)]
pub struct NtfsAttribute<'n, 'f> {
    file: &'f NtfsFile<'n>,
    header: NtfsAttributeHeaderKind,
    offset: usize,
    /// Has a value if this attribute's value may be split over multiple attributes.
    /// The connected attributes can be iterated using the encapsulated iterator.
    list_entries: Option<&'f NtfsAttributeListEntries<'n, 'f>>,
}

impl<'n, 'f> NtfsAttribute<'n, 'f> {
    pub(crate) fn new(
        file: &'f NtfsFile<'n>,
        offset: usize,
        end: usize,
        list_entries: Option<&'f NtfsAttributeListEntries<'n, 'f>>,
    ) -> Result<Self> {
        let position = file.position() + offset;
        let data = file.record_data().get(offset..end).unwrap_or_default();
        let common_header = pod_from_prefix::<NtfsAttributeHeader, ATTRIBUTE_HEADER_SIZE>(data)
            .ok_or(NtfsError::InvalidAttributeLength {
                position,
                expected: ATTRIBUTE_HEADER_SIZE,
                actual: data.len(),
            })?;
        let attribute_length = common_header.length.get() as usize;
        if attribute_length < ATTRIBUTE_HEADER_SIZE || attribute_length > data.len() {
            return Err(NtfsError::InvalidAttributeLength {
                position,
                expected: ATTRIBUTE_HEADER_SIZE.max(attribute_length),
                actual: data.len().min(attribute_length),
            });
        }

        let header = if common_header.is_non_resident == 0 {
            const SIZE: usize = mem::size_of::<NtfsResidentAttributeHeader>();
            let header =
                pod_from_prefix::<NtfsResidentAttributeHeader, SIZE>(&data[..attribute_length])
                    .ok_or(NtfsError::InvalidAttributeLength {
                        position,
                        expected: SIZE,
                        actual: attribute_length,
                    })?;
            NtfsAttributeHeaderKind::Resident(header)
        } else {
            const SIZE: usize = mem::size_of::<NtfsNonResidentAttributeHeader>();
            let header =
                pod_from_prefix::<NtfsNonResidentAttributeHeader, SIZE>(&data[..attribute_length])
                    .ok_or(NtfsError::InvalidAttributeLength {
                        position,
                        expected: SIZE,
                        actual: attribute_length,
                    })?;
            NtfsAttributeHeaderKind::NonResident(header)
        };

        Ok(Self {
            file,
            header,
            offset,
            list_entries,
        })
    }

    /// Returns the length of this NTFS Attribute, in bytes.
    ///
    /// This denotes the length of the attribute structure on disk.
    /// Apart from various headers, this structure also includes the name and,
    /// for resident attributes, the actual value.
    pub fn attribute_length(&self) -> u32 {
        self.header.common().length.get()
    }

    pub(crate) fn ensure_ty(&self, expected: NtfsAttributeType) -> Result<()> {
        let ty = self.ty()?;
        if ty != expected {
            return Err(NtfsError::AttributeOfDifferentType {
                position: self.position(),
                expected,
                actual: ty,
            });
        }

        Ok(())
    }

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

    /// Returns the identifier of this attribute that is unique within the [`NtfsFile`].
    pub fn instance(&self) -> u16 {
        self.header.common().instance.get()
    }

    /// Returns `true` if this is a resident attribute, i.e. one where its value
    /// is part of the attribute structure.
    pub fn is_resident(&self) -> bool {
        matches!(self.header, NtfsAttributeHeaderKind::Resident(_))
    }

    /// Gets the name of this NTFS Attribute (if any) and returns it wrapped in a [`U16StrLe`].
    ///
    /// Note that most NTFS attributes have no name and are distinguished by their types.
    /// Use [`NtfsAttribute::ty`] to get the attribute type.
    pub fn name(&self) -> Result<U16StrLe<'f>> {
        if self.name_offset() == 0 || self.name_length() == 0 {
            return Ok(U16StrLe(&[]));
        }

        self.validate_name_sizes()?;

        let start = self.offset + self.name_offset() as usize;
        let end = start + self.name_length();
        let string = U16StrLe(&self.file.record_data()[start..end]);

        Ok(string)
    }

    fn name_offset(&self) -> u16 {
        self.header.common().name_offset.get()
    }

    /// Returns the length of the name of this NTFS Attribute, in bytes.
    ///
    /// An attribute name has a maximum length of 255 UTF-16 code points (510 bytes).
    /// It is always part of the attribute itself and hence also of the length
    /// returned by [`NtfsAttribute::attribute_length`].
    pub fn name_length(&self) -> usize {
        let name_length_in_characters = self.header.common().name_length;
        name_length_in_characters as usize * mem::size_of::<u16>()
    }

    pub(crate) fn non_resident_value(&self) -> Result<NtfsNonResidentAttributeValue<'n, 'f>> {
        let (data, position) = self.non_resident_value_data_and_position()?;

        NtfsNonResidentAttributeValue::new(
            self.file.ntfs(),
            data,
            position,
            self.non_resident_value_data_size(),
        )
    }

    pub(crate) fn non_resident_value_data_and_position(&self) -> Result<(&'f [u8], NtfsPosition)> {
        debug_assert!(!self.is_resident());
        let start = self.offset + self.non_resident_value_data_runs_offset() as usize;
        let end = self.offset + self.attribute_length() as usize;
        let position = self.file.position() + start;
        let data = &self.file.record_data().get(start..end).ok_or(
            NtfsError::InvalidNonResidentValueDataRange {
                position,
                range: start..end,
                size: self.file.record_data().len(),
            },
        )?;
        Ok((data, position))
    }

    fn non_resident_value_data_size(&self) -> u64 {
        debug_assert!(!self.is_resident());
        match &self.header {
            NtfsAttributeHeaderKind::NonResident(header) => header.data_size.get(),
            NtfsAttributeHeaderKind::Resident(_) => unreachable!(),
        }
    }

    fn non_resident_value_data_runs_offset(&self) -> u16 {
        debug_assert!(!self.is_resident());
        match &self.header {
            NtfsAttributeHeaderKind::NonResident(header) => header.data_runs_offset.get(),
            NtfsAttributeHeaderKind::Resident(_) => unreachable!(),
        }
    }

    pub(crate) fn offset(&self) -> usize {
        self.offset
    }

    /// Returns the absolute position of this NTFS Attribute within the filesystem, in bytes.
    pub fn position(&self) -> NtfsPosition {
        self.file.position() + self.offset
    }

    /// Attempts to parse the value data as the given resident structured value type and returns that.
    ///
    /// This is a fast path for attributes that are always resident.
    /// It doesn't need a reference to the filesystem reader.
    ///
    /// This function first checks that the attribute is of the required type for that structured value
    /// and if it's a resident attribute.
    /// It returns with an error if that is not the case.
    /// It also returns an error for any parsing problem.
    pub fn resident_structured_value<S>(&self) -> Result<S>
    where
        S: NtfsStructuredValueFromResidentAttributeValue<'n, 'f>,
    {
        self.ensure_ty(S::TY)?;

        if !self.is_resident() {
            return Err(NtfsError::UnexpectedNonResidentAttribute {
                position: self.position(),
            });
        }

        let resident_value = self.resident_value()?;
        S::from_resident_attribute_value(resident_value)
    }

    pub(crate) fn resident_value(&self) -> Result<NtfsResidentAttributeValue<'f>> {
        debug_assert!(self.is_resident());
        self.validate_resident_value_sizes()?;

        let start = self.offset + self.resident_value_offset() as usize;
        let end = start + self.resident_value_length() as usize;
        let data = &self.file.record_data()[start..end];

        Ok(NtfsResidentAttributeValue::new(data, self.position()))
    }

    fn resident_value_length(&self) -> u32 {
        debug_assert!(self.is_resident());
        match &self.header {
            NtfsAttributeHeaderKind::Resident(header) => header.value_length.get(),
            NtfsAttributeHeaderKind::NonResident(_) => unreachable!(),
        }
    }

    fn resident_value_offset(&self) -> u16 {
        debug_assert!(self.is_resident());
        match &self.header {
            NtfsAttributeHeaderKind::Resident(header) => header.value_offset.get(),
            NtfsAttributeHeaderKind::NonResident(_) => unreachable!(),
        }
    }

    /// Attempts to parse the value data as the given structured value type and returns that.
    ///
    /// This function first checks that the attribute is of the required type for that structured value.
    /// It returns with an error if that is not the case.
    /// It also returns an error for any parsing problem.
    pub fn structured_value<T, S>(&self, fs: &mut T) -> Result<S>
    where
        T: Read + Seek,
        S: NtfsStructuredValue<'n, 'f>,
    {
        self.ensure_ty(S::TY)?;
        let value = self.value(fs)?;
        S::from_attribute_value(fs, value)
    }

    /// Returns the type of this NTFS Attribute, or [`NtfsError::UnsupportedAttributeType`]
    /// if it's an unknown type.
    pub fn ty(&self) -> Result<NtfsAttributeType> {
        let ty = self.header.common().ty.get();

        NtfsAttributeType::try_from(ty).map_err(|_| NtfsError::UnsupportedAttributeType {
            position: self.position(),
            actual: ty,
        })
    }

    fn validate_name_sizes(&self) -> Result<()> {
        let start = self.name_offset();
        if start as u32 >= self.attribute_length() {
            return Err(NtfsError::InvalidAttributeNameOffset {
                position: self.position(),
                expected: start,
                actual: self.attribute_length(),
            });
        }

        let end = start as usize + self.name_length();
        if end > self.attribute_length() as usize {
            return Err(NtfsError::InvalidAttributeNameLength {
                position: self.position(),
                expected: end,
                actual: self.attribute_length(),
            });
        }

        Ok(())
    }

    fn validate_resident_value_sizes(&self) -> Result<()> {
        debug_assert!(self.is_resident());

        let position = self.position();
        let attribute_length = self.attribute_length();

        let start = self.resident_value_offset();
        if start as u32 > attribute_length {
            return Err(NtfsError::InvalidResidentAttributeValueOffset {
                position,
                expected: start,
                actual: attribute_length,
            });
        }

        let length = self.resident_value_length();

        let end = u32::from(start).checked_add(length).ok_or(
            NtfsError::InvalidResidentAttributeValueLength {
                position,
                length,
                offset: start,
                actual: attribute_length,
            },
        )?;
        if end > attribute_length {
            return Err(NtfsError::InvalidResidentAttributeValueLength {
                position,
                length,
                offset: start,
                actual: attribute_length,
            });
        }

        Ok(())
    }

    /// Returns an [`NtfsAttributeValue`] structure to read the value of this NTFS Attribute.
    pub fn value<T>(&self, fs: &mut T) -> Result<NtfsAttributeValue<'n, 'f>>
    where
        T: Read + Seek,
    {
        if let Some(list_entries) = self.list_entries {
            // The first attribute reports the entire data size for all connected attributes
            // (remaining ones are set to zero).
            // Fortunately, we are the first attribute :)
            let data_size = self.non_resident_value_data_size();

            let value = NtfsAttributeListNonResidentAttributeValue::new(
                self.file.ntfs(),
                fs,
                list_entries.clone(),
                self.instance(),
                self.ty()?,
                data_size,
            )?;
            Ok(NtfsAttributeValue::AttributeListNonResident(value))
        } else if self.is_resident() {
            let value = self.resident_value()?;
            Ok(NtfsAttributeValue::Resident(value))
        } else {
            let value = self.non_resident_value()?;
            Ok(NtfsAttributeValue::NonResident(value))
        }
    }

    /// Returns the length of the value data of this NTFS Attribute, in bytes.
    pub fn value_length(&self) -> u64 {
        if self.is_resident() {
            self.resident_value_length() as u64
        } else {
            self.non_resident_value_data_size()
        }
    }
}

/// Iterator over
///   all attributes of an [`NtfsFile`],
///   returning an [`NtfsAttributeItem`] for each entry.
///
/// This iterator is returned from the [`NtfsFile::attributes`] function.
/// It 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).
///
/// Check [`NtfsAttributesRaw`] if you want to iterate over the plain attributes on the filesystem.
/// See [`NtfsAttributesAttached`] for an iterator that implements [`Iterator`] and [`FusedIterator`].
#[derive(Clone, Debug)]
pub struct NtfsAttributes<'n, 'f> {
    raw_iter: NtfsAttributesRaw<'n, 'f>,
    state: NtfsAttributesState<'n, 'f>,
}

#[derive(Clone, Debug)]
enum NtfsAttributesState<'n, 'f> {
    Raw,
    AttributeList {
        entries: NtfsAttributeListEntries<'n, 'f>,
        skip: Option<(u16, NtfsAttributeType)>,
    },
    Done,
}

impl<'n, 'f> NtfsAttributes<'n, 'f> {
    pub(crate) fn new(file: &'f NtfsFile<'n>) -> Self {
        Self {
            raw_iter: NtfsAttributesRaw::new(file),
            state: NtfsAttributesState::Raw,
        }
    }

    /// Returns a variant of this iterator that implements [`Iterator`] and [`FusedIterator`]
    /// by mutably borrowing the filesystem reader.
    pub fn attach<'a, T>(self, fs: &'a mut T) -> NtfsAttributesAttached<'n, 'f, 'a, T>
    where
        T: Read + Seek,
    {
        NtfsAttributesAttached::new(fs, self)
    }

    /// See [`Iterator::next`].
    pub fn next<T>(&mut self, fs: &mut T) -> Option<Result<NtfsAttributeItem<'n, 'f>>>
    where
        T: Read + Seek,
    {
        loop {
            match &mut self.state {
                NtfsAttributesState::AttributeList { entries, skip } => {
                    if let Some(item) =
                        Self::next_attribute_list_item(self.raw_iter.file, entries, skip, fs)
                    {
                        return Some(item);
                    }
                    self.state = NtfsAttributesState::Raw;
                }
                NtfsAttributesState::Raw => {
                    let attribute = match self.raw_iter.next() {
                        Some(attribute) => iter_try!(attribute),
                        None => {
                            self.state = NtfsAttributesState::Done;
                            return None;
                        }
                    };
                    if let Ok(NtfsAttributeType::AttributeList) = attribute.ty() {
                        let attribute_list =
                            iter_try!(attribute.structured_value::<T, NtfsAttributeList>(fs));
                        self.state = NtfsAttributesState::AttributeList {
                            entries: attribute_list.entries(),
                            skip: None,
                        };
                    } else {
                        let item = NtfsAttributeItem {
                            attribute_file: self.raw_iter.file,
                            attribute_value_file: None,
                            attribute_offset: attribute.offset(),
                            header: attribute.header,
                            list_entries: None,
                        };
                        return Some(Ok(item));
                    }
                }
                NtfsAttributesState::Done => return None,
            }
        }
    }

    fn next_attribute_list_item<T>(
        base_file: &'f NtfsFile<'n>,
        entries: &mut NtfsAttributeListEntries<'n, 'f>,
        skip: &mut Option<(u16, NtfsAttributeType)>,
        fs: &mut T,
    ) -> Option<Result<NtfsAttributeItem<'n, 'f>>>
    where
        T: Read + Seek,
    {
        loop {
            // A non-resident value may span adjacent Attribute List entries. Keep a checkpoint
            // from before reading the entry so its connected attributes can be revisited later.
            let entries_checkpoint = entries.clone();
            let entry = iter_try!(entries.next(fs)?);
            let entry_instance = entry.instance();
            let entry_record_number = entry.base_file_reference().file_record_number();
            let entry_ty = iter_try!(entry.ty());

            if entry_record_number == base_file.file_record_number() {
                continue;
            }

            if let Some((skip_instance, skip_ty)) = *skip
                && entry_instance == skip_instance
                && entry_ty == skip_ty
            {
                continue;
            }

            *skip = None;
            let entry_file = iter_try!(entry.to_file(base_file.ntfs(), fs));
            let entry_attribute = iter_try!(entry.to_attribute(&entry_file));
            let attribute_offset = entry_attribute.offset();
            let header = entry_attribute.header;

            let mut list_entries = None;
            if !entry_attribute.is_resident() {
                list_entries = Some(entries_checkpoint);
                *skip = Some((entry_instance, entry_ty));
            }

            return Some(Ok(NtfsAttributeItem {
                attribute_file: base_file,
                attribute_value_file: Some(entry_file),
                attribute_offset,
                header,
                list_entries,
            }));
        }
    }
}

/// Iterator over
///   all attributes of an [`NtfsFile`],
///   returning an [`NtfsAttributeItem`] for each entry,
///   implementing [`Iterator`] and [`FusedIterator`].
///
/// This iterator is returned from the [`NtfsAttributes::attach`] function.
/// Conceptually the same as [`NtfsAttributes`], but mutably borrows the filesystem
/// to implement aforementioned traits.
#[derive(Debug)]
pub struct NtfsAttributesAttached<'n, 'f, 'a, T: Read + Seek> {
    fs: &'a mut T,
    attributes: NtfsAttributes<'n, 'f>,
}

impl<'n, 'f, 'a, T> NtfsAttributesAttached<'n, 'f, 'a, T>
where
    T: Read + Seek,
{
    fn new(fs: &'a mut T, attributes: NtfsAttributes<'n, 'f>) -> Self {
        Self { fs, attributes }
    }

    /// Consumes this iterator and returns the inner [`NtfsAttributes`].
    pub fn detach(self) -> NtfsAttributes<'n, 'f> {
        self.attributes
    }
}

impl<'n, 'f, 'a, T> Iterator for NtfsAttributesAttached<'n, 'f, 'a, T>
where
    T: Read + Seek,
{
    type Item = Result<NtfsAttributeItem<'n, 'f>>;

    fn next(&mut self) -> Option<Self::Item> {
        self.attributes.next(self.fs)
    }
}

impl<'n, 'f, 'a, T> FusedIterator for NtfsAttributesAttached<'n, 'f, 'a, T> where T: Read + Seek {}

/// Item returned by the [`NtfsAttributes`] iterator.
///
/// [`NtfsAttributes`] provides a flattened view over the attributes by traversing Attribute Lists.
/// Attribute Lists may contain entries with references to other [`NtfsFile`]s.
/// Therefore, the attribute's information may either be stored in the original [`NtfsFile`] or in another
/// [`NtfsFile`] that has been read just for this attribute.
///
/// [`NtfsAttributeItem`] abstracts over both cases by providing a reference to the original [`NtfsFile`],
/// and optionally holding another [`NtfsFile`] if the attribute is actually stored there.
#[derive(Clone, Debug)]
pub struct NtfsAttributeItem<'n, 'f> {
    attribute_file: &'f NtfsFile<'n>,
    attribute_value_file: Option<NtfsFile<'n>>,
    attribute_offset: usize,
    header: NtfsAttributeHeaderKind,
    list_entries: Option<NtfsAttributeListEntries<'n, 'f>>,
}

impl<'n, 'f> NtfsAttributeItem<'n, 'f> {
    /// Returns the actual [`NtfsAttribute`] structure for this NTFS Attribute.
    pub fn to_attribute<'i>(&'i self) -> Result<NtfsAttribute<'n, 'i>> {
        let file = if let Some(file) = &self.attribute_value_file {
            file
        } else {
            self.attribute_file
        };

        Ok(NtfsAttribute {
            file,
            header: self.header,
            offset: self.attribute_offset,
            list_entries: self.list_entries.as_ref(),
        })
    }
}

/// Iterator over
///   all top-level attributes of an [`NtfsFile`],
///   returning an [`NtfsAttribute`] for each entry,
///   implementing [`Iterator`] and [`FusedIterator`].
///
/// This iterator is returned from the [`NtfsFile::attributes_raw`] function.
/// Contrary to [`NtfsAttributes`], it does not traverse $ATTRIBUTE_LIST attributes and returns them
/// as raw [`NtfsAttribute`]s.
/// Check that structure if you want an iterator providing a flattened "data-centric" view over
/// the attributes by traversing Attribute Lists automatically.
#[derive(Clone, Debug)]
pub struct NtfsAttributesRaw<'n, 'f> {
    file: &'f NtfsFile<'n>,
    items_range: Range<usize>,
}

impl<'n, 'f> NtfsAttributesRaw<'n, 'f> {
    pub(crate) fn new(file: &'f NtfsFile<'n>) -> Self {
        let start = file.first_attribute_offset() as usize;
        let end = file.data_size() as usize;
        let items_range = start..end;

        Self { file, items_range }
    }
}

impl<'n, 'f> Iterator for NtfsAttributesRaw<'n, 'f> {
    type Item = Result<NtfsAttribute<'n, 'f>>;

    fn next(&mut self) -> Option<Self::Item> {
        // This may be an entire attribute or just the 4-byte end marker.
        // Check if this marks the end of the attribute list.
        if self.items_range.len() < mem::size_of::<u32>() {
            return None;
        }

        let start = self.items_range.start;
        let end = start + mem::size_of::<u32>();
        let ty_slice = self.file.record_data().get(start..end)?;

        let ty = pod_from_prefix::<U32<LittleEndian>, { mem::size_of::<u32>() }>(ty_slice)
            .expect("the attribute type slice has a validated size")
            .get();
        if ty == NtfsAttributeType::End as u32 {
            return None;
        }

        // It's a real attribute.
        let attribute = iter_try!(NtfsAttribute::new(
            self.file,
            self.items_range.start,
            self.items_range.end,
            None,
        ));
        self.items_range.start += attribute.attribute_length() as usize;

        Some(Ok(attribute))
    }
}

impl<'n, 'f> FusedIterator for NtfsAttributesRaw<'n, 'f> {}