vstorage 0.7.0

//! Produce normalise hash of items.

use std::borrow::Cow;

use sha2::{Digest as _, Sha256};
use vparser::{ParamIter, Parser};

// TODO: See (in vdirsyncer) IGNORE_PROPS for more props that might make sense to ignore.
pub const ICS_FIELDS_TO_IGNORE: &[&str] = &[
    // Servers often mutate this; resulting in noise when comparing.
    "PRODID",
    // When the information was last revised.
    // I don't think that servers SHOULD modify this, but they often do.
    // See: https://www.rfc-editor.org/rfc/rfc5545#section-3.8.7.2
    "DTSTAMP",
    // Ditto
    // See: https://www.rfc-editor.org/rfc/rfc5545#section-3.8.7.3
    "LAST-MODIFIED",
];

/// Parsed line that we need to keep around.
#[derive(Debug)]
struct ParsedLine<'a> {
    name: Cow<'a, str>,
    value: Cow<'a, str>,
    /// Parameters string for parsing later
    params_str: Cow<'a, str>,
}

/// Property with normalised hashing.
#[derive(Debug)]
struct NormalizedProperty<'a> {
    /// The property name
    name: &'a str,
    /// Sorted, uppercase parameter key-value pairs
    params: Vec<(Cow<'a, str>, &'a str)>,
    /// The property value
    value: &'a str,
}

impl NormalizedProperty<'_> {
    /// Hash this property into the hasher.
    fn hash_into(&self, hasher: &mut Sha256) {
        hasher.update(self.name.as_bytes());
        for (key, value) in &self.params {
            hasher.update(b";");
            hasher.update(key.as_bytes());
            hasher.update(b"=");
            hasher.update(value.as_bytes());
        }
        hasher.update(b":");
        hasher.update(self.value.as_bytes());
        hasher.update(b"\r\n");
    }

    /// Sort by name, params and value.
    fn sort_key(&self) -> impl Ord + '_ {
        (self.name, &self.params, self.value)
    }
}

/// Component in the tree hierarchy (e.g., VCALENDAR, VEVENT, VTIMEZONE).
#[derive(Debug)]
struct Component<'a> {
    name: &'a str,
    properties: Vec<NormalizedProperty<'a>>,
    sub_components: Vec<Component<'a>>,
}

impl<'a> Component<'a> {
    fn new(name: &'a str) -> Self {
        Component {
            name,
            properties: Vec::new(),
            sub_components: Vec::new(),
        }
    }

    /// Normalize and hash this component in a single pass.
    ///
    /// Returns the hash of this component for use in sorting by parent.
    fn normalize_and_hash(mut self) -> [u8; 32] {
        // Sort properties by their sort key.
        self.properties
            .sort_by(|a, b| a.sort_key().cmp(&b.sort_key()));

        // Recursively normalize subcomponents and collect their hashes.
        let mut subcomponent_hashes: Vec<[u8; 32]> = self
            .sub_components
            .into_iter()
            .map(Component::normalize_and_hash)
            .collect();
        subcomponent_hashes.sort_unstable();

        // Compute hash of this component.
        let mut hasher = Sha256::new();
        hasher.update(b"BEGIN:");
        hasher.update(self.name.as_bytes());
        hasher.update(b"\r\n");

        for prop in &self.properties {
            prop.hash_into(&mut hasher);
        }

        for hash in &subcomponent_hashes {
            hasher.update(b"\0");
            hasher.update(hash.as_slice());
        }

        hasher.update(b"END:");
        hasher.update(self.name.as_bytes());
        hasher.update(b"\r\n");

        hasher.finalize().into()
    }
}

/// Parse and hash normalized iCalendar/vCard data.
pub fn hash_normalized(raw: &str, hasher: &mut Sha256) {
    // First pass: collect all parsed lines.
    let parser = Parser::new(raw);
    let mut parsed_lines = Vec::new();

    for line in parser {
        if ICS_FIELDS_TO_IGNORE.contains(&line.name().as_ref()) {
            continue;
        }

        let raw_line = line.raw();
        if raw_line.is_empty() {
            continue;
        }

        parsed_lines.push(ParsedLine {
            name: line.name(),
            value: line.value(),
            params_str: line.params(),
        });
    }

    // Second pass: build component tree from parsed lines.
    let mut component_stack: Vec<Component> = Vec::new();
    let mut root_properties = Vec::new();

    for parsed in &parsed_lines {
        if parsed.name == "BEGIN" {
            component_stack.push(Component::new(parsed.value.as_ref()));
        } else if parsed.name == "END" {
            if let Some(completed_component) = component_stack.pop() {
                if component_stack.is_empty() {
                    // Root component.
                    let hash = completed_component.normalize_and_hash();
                    hasher.update(hash);
                    return;
                }
                // Add to parent component
                if let Some(parent) = component_stack.last_mut() {
                    parent.sub_components.push(completed_component);
                }
            }
        } else {
            // Regular property.
            let name = parsed.name.as_ref();
            let value = parsed.value.as_ref();

            let mut params: Vec<(Cow<str>, &str)> = Vec::new();
            for param in ParamIter::new(&parsed.params_str) {
                let param_name = param.name();
                let param_value = param.value();

                // Normalize parameter name to uppercase
                let normalized_key = if param_name.bytes().any(|b| b.is_ascii_lowercase()) {
                    Cow::Owned(param_name.to_string().to_ascii_uppercase())
                } else {
                    Cow::Borrowed(param_name)
                };

                params.push((normalized_key, param_value));
            }

            // Sort parameters by key, then by value.
            params.sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.cmp(b.1)));

            let prop = NormalizedProperty {
                name,
                params,
                value,
            };

            if let Some(current_component) = component_stack.last_mut() {
                current_component.properties.push(prop);
            } else {
                root_properties.push(prop);
            }
        }
    }

    // Only extremely malformed entries will match this branch,
    // well-formed icalendar files will have drained this queue already.
    if !root_properties.is_empty() {
        root_properties.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()));
        for prop in root_properties {
            prop.hash_into(hasher);
        }
    }
}

#[cfg(test)]
mod test {
    use crate::base::Item;

    #[test]
    fn compare_hashing_with_and_without_prodid() {
        let without_prodid: Item = [
            "BEGIN:VCALENDAR",
            "BEGIN:VEVENT",
            "DTSTART:19970714T170000Z",
            "DTEND:19970715T035959Z",
            "SUMMARY:Bastille Day Party",
            "UID:11bb6bed-c29b-4999-a627-12dee35f8395",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();
        let with_prodid: Item = [
            "PRODID:test-client",
            "BEGIN:VCALENDAR",
            "BEGIN:VEVENT",
            "DTSTART:19970714T170000Z",
            "DTEND:19970715T035959Z",
            "SUMMARY:Bastille Day Party",
            "UID:11bb6bed-c29b-4999-a627-12dee35f8395",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        assert_eq!(without_prodid.hash(), with_prodid.hash());
        assert_eq!(
            without_prodid.hash().to_string(),
            "D6C9565AD90A7C9736EE1DBF3B8002C018ADB5EB953E3A3F5292B816A28D1ACD"
        );
    }

    #[test]
    fn compare_hashing_with_different_folding() {
        let first: Item = [
            "DESCRIPTION:Voor meer informatie zie https://nluug.nl/evenementen/nluug/na",
            " jaarsconferentie-2023/",
        ]
        .join("\r\n")
        .into();
        let second: Item = [
            "DESCRIPTION:Voor meer informatie zie https:",
            " //nluug.nl/evenementen/nluug/najaarsconferentie-2023/",
        ]
        .join("\r\n")
        .into();

        assert_eq!(first.hash(), second.hash());
        assert_eq!(
            first.hash().to_string(),
            "9FCE34302FB7B6677542987089C91FDDF79F18F1D42862B03B1DEDF8E72F0CE2"
        );
    }

    #[test]
    fn hash_with_reordered_timezone() {
        let timezone_first:Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "CALSCALE:GREGORIAN",
            "BEGIN:VTIMEZONE",
            "TZID:Europe/Amsterdam",
            "X-LIC-LOCATION:Europe/Amsterdam",
            "BEGIN:DAYLIGHT",
            "TZOFFSETFROM:+0100",
            "TZOFFSETTO:+0200",
            "TZNAME:CEST",
            "DTSTART:19700329T020000",
            "RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU",
            "END:DAYLIGHT",
            "BEGIN:STANDARD",
            "TZOFFSETFROM:+0200",
            "TZOFFSETTO:+0100",
            "TZNAME:CET",
            "DTSTART:19701025T030000",
            "RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU",
            "END:STANDARD",
            "END:VTIMEZONE",
            "BEGIN:VEVENT",
            "UID:DF1E090791D8A93F3B530CFDA9CBFC0573CE3AB61C63A02AA33051B903F68A82",
            "SUMMARY:NLUUG najaarsconferentie 2023",
            "DESCRIPTION:Voor meer informatie zie https://nluug.nl/evenementen/nluug/najaarsconferentie-2023/",
            "DTSTART;TZID=Europe/Amsterdam:20231128T083000",
            "DTEND;TZID=Europe/Amsterdam:20231128T180000",
            "LOCATION:Winthontlaan 4-6, Utrecht, The Netherlands",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n").into();
        let timezone_last :Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "CALSCALE:GREGORIAN",
            "BEGIN:VEVENT",
            "UID:DF1E090791D8A93F3B530CFDA9CBFC0573CE3AB61C63A02AA33051B903F68A82",
            "SUMMARY:NLUUG najaarsconferentie 2023",
            "DESCRIPTION:Voor meer informatie zie https://nluug.nl/evenementen/nluug/najaarsconferentie-2023/",
            "DTSTART;TZID=Europe/Amsterdam:20231128T083000",
            "DTEND;TZID=Europe/Amsterdam:20231128T180000",
            "LOCATION:Winthontlaan 4-6, Utrecht, The Netherlands",
            "END:VEVENT",
            "BEGIN:VTIMEZONE",
            "TZID:Europe/Amsterdam",
            "X-LIC-LOCATION:Europe/Amsterdam",
            "BEGIN:DAYLIGHT",
            "TZOFFSETFROM:+0100",
            "TZOFFSETTO:+0200",
            "TZNAME:CEST",
            "DTSTART:19700329T020000",
            "RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU",
            "END:DAYLIGHT",
            "BEGIN:STANDARD",
            "TZOFFSETFROM:+0200",
            "TZOFFSETTO:+0100",
            "TZNAME:CET",
            "DTSTART:19701025T030000",
            "RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU",
            "END:STANDARD",
            "END:VTIMEZONE",
            "END:VCALENDAR",
        ]
        .join("\r\n").into();

        assert_eq!(timezone_first.hash(), timezone_last.hash());
    }

    #[test]
    fn test_hash_with_reordered_fields() {
        // Fields in different order should produce the same hash
        let item1: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VEVENT",
            "UID:test-123",
            "SUMMARY:Test Event",
            "DTSTART:20231128T100000Z",
            "DTEND:20231128T110000Z",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VEVENT",
            "DTEND:20231128T110000Z",
            "DTSTART:20231128T100000Z",
            "SUMMARY:Test Event",
            "UID:test-123",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }

    #[test]
    fn test_hash_with_reordered_components() {
        // Components in different order should produce the same hash
        let item1: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VEVENT",
            "UID:event-1",
            "SUMMARY:First Event",
            "END:VEVENT",
            "BEGIN:VEVENT",
            "UID:event-2",
            "SUMMARY:Second Event",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VEVENT",
            "UID:event-2",
            "SUMMARY:Second Event",
            "END:VEVENT",
            "BEGIN:VEVENT",
            "UID:event-1",
            "SUMMARY:First Event",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }

    #[test]
    fn test_hash_with_parameter_name_case() {
        // Parameter names with different cases should produce the same hash
        let item1: Item = [
            "BEGIN:VCALENDAR",
            "BEGIN:VEVENT",
            "UID:test-123",
            "DTSTART;TZID=Europe/Amsterdam:20231128T100000",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCALENDAR",
            "BEGIN:VEVENT",
            "UID:test-123",
            "DTSTART;tzid=Europe/Amsterdam:20231128T100000",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }

    #[test]
    fn test_hash_with_parameter_order() {
        // Parameters in different order should produce the same hash
        let item1: Item = [
            "BEGIN:VCARD",
            "VERSION:3.0",
            "TEL;TYPE=CELL;TYPE=VOICE;TYPE=pref:+31612345678",
            "END:VCARD",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCARD",
            "VERSION:3.0",
            "TEL;TYPE=pref;TYPE=VOICE;TYPE=CELL:+31612345678",
            "END:VCARD",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }

    #[test]
    fn test_hash_with_mixed_parameter_case() {
        // Mixed parameter name cases should normalize consistently
        let item1: Item = [
            "BEGIN:VCARD",
            "VERSION:3.0",
            "TEL;TYPE=CELL;TYPE=VOICE;TYPE=PREF:+31612345678",
            "END:VCARD",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCARD",
            "VERSION:3.0",
            "TEL;type=CELL;Type=VOICE;TyPe=PREF:+31612345678",
            "END:VCARD",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }

    #[test]
    fn test_hash_complex_normalization() {
        // Combine field reordering, component reordering, and parameter normalization
        let item1: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VTIMEZONE",
            "TZID:Europe/Amsterdam",
            "BEGIN:STANDARD",
            "DTSTART:19701025T030000",
            "TZOFFSETFROM:+0200",
            "TZOFFSETTO:+0100",
            "END:STANDARD",
            "END:VTIMEZONE",
            "BEGIN:VEVENT",
            "UID:event-1",
            "SUMMARY:Meeting",
            "DTSTART;TZID=Europe/Amsterdam:20231128T100000",
            "DTEND;TZID=Europe/Amsterdam:20231128T110000",
            "END:VEVENT",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VEVENT",
            "DTEND;tzid=Europe/Amsterdam:20231128T110000",
            "DTSTART;tzid=Europe/Amsterdam:20231128T100000",
            "SUMMARY:Meeting",
            "UID:event-1",
            "END:VEVENT",
            "BEGIN:VTIMEZONE",
            "TZID:Europe/Amsterdam",
            "BEGIN:STANDARD",
            "TZOFFSETTO:+0100",
            "TZOFFSETFROM:+0200",
            "DTSTART:19701025T030000",
            "END:STANDARD",
            "END:VTIMEZONE",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }

    #[test]
    fn test_hash_nested_components() {
        // Nested components with different field orders
        let item1: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VTIMEZONE",
            "TZID:Europe/Amsterdam",
            "BEGIN:STANDARD",
            "DTSTART:19701025T030000",
            "TZOFFSETFROM:+0200",
            "TZOFFSETTO:+0100",
            "END:STANDARD",
            "BEGIN:DAYLIGHT",
            "DTSTART:19700329T020000",
            "TZOFFSETFROM:+0100",
            "TZOFFSETTO:+0200",
            "END:DAYLIGHT",
            "END:VTIMEZONE",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        let item2: Item = [
            "BEGIN:VCALENDAR",
            "VERSION:2.0",
            "BEGIN:VTIMEZONE",
            "TZID:Europe/Amsterdam",
            "BEGIN:DAYLIGHT",
            "TZOFFSETTO:+0200",
            "TZOFFSETFROM:+0100",
            "DTSTART:19700329T020000",
            "END:DAYLIGHT",
            "BEGIN:STANDARD",
            "TZOFFSETTO:+0100",
            "TZOFFSETFROM:+0200",
            "DTSTART:19701025T030000",
            "END:STANDARD",
            "END:VTIMEZONE",
            "END:VCALENDAR",
        ]
        .join("\r\n")
        .into();

        assert_eq!(item1.hash(), item2.hash());
    }
}