Skip to content

Solution for long term memory for agent coding CLIs and to facilitate handoff between different agent vendors

Rust
16.6 KB
Raw Blame
use std::collections::{HashMap, HashSet};
use std::ops::Range;

use schemars::JsonSchema;
use serde::{Deserialize, Serialize};
use sha2::{Digest, Sha256};

pub(crate) const MAX_EDITS: usize = 32;
pub(crate) const MAX_EDIT_CHARS: usize = 64 * 1024;
pub(crate) const MAX_CHANGED_CHARS: usize = 256 * 1024;
pub(crate) const MAX_SECTION_HASHES: usize = 100;

#[derive(Debug, Clone, Serialize, JsonSchema)]
pub(crate) struct SectionHash {
    pub anchor: String,
    pub level: u8,
    pub sha256: String,
}

#[derive(Debug, Clone, Copy, Deserialize, JsonSchema)]
#[serde(rename_all = "snake_case")]
pub(crate) enum AppendTarget {
    Section,
    EndOfPage,
}

#[derive(Debug, Clone, Deserialize, JsonSchema)]
#[serde(tag = "op", rename_all = "snake_case")]
pub(crate) enum PagePatchEdit {
    Append {
        target: AppendTarget,
        #[serde(default)]
        anchor: Option<String>,
        content: String,
    },
    AddSection {
        anchor: String,
        content: String,
    },
    ReplaceSection {
        anchor: String,
        section_sha256: String,
        content: String,
    },
}

#[derive(Debug, thiserror::Error, PartialEq, Eq)]
pub(crate) enum PatchError {
    #[error("at least one edit is required")]
    Empty,
    #[error("too many edits (maximum {MAX_EDITS})")]
    TooMany,
    #[error("edit content is too large")]
    ContentTooLarge,
    #[error("combined edit content is too large")]
    BatchTooLarge,
    #[error("append target section requires an anchor")]
    MissingAnchor,
    #[error("append target end_of_page cannot have an anchor")]
    UnexpectedAnchor,
    #[error("anchor not found: {0}")]
    AnchorNotFound(String),
    #[error("anchor is ambiguous: {0}")]
    AmbiguousAnchor(String),
    #[error("more than one edit targets anchor: {0}")]
    DuplicateTarget(String),
    #[error("add_section anchor must be one ATX level 2-6 heading")]
    InvalidNewHeading,
    #[error("heading already exists: {0}")]
    HeadingExists(String),
    #[error("section precondition failed: {0}")]
    SectionPreconditionFailed(String),
    #[error("edits overlap")]
    Overlapping,
}

#[derive(Debug, Clone)]
struct Section {
    anchor: String,
    normalized: String,
    level: u8,
    whole: Range<usize>,
    content: Range<usize>,
}

#[derive(Debug)]
struct Change {
    range: Range<usize>,
    replacement: String,
}

pub(crate) fn section_hashes(body: &str) -> (Vec<SectionHash>, bool) {
    let sections = parse_sections(body);
    let truncated = sections.len() > MAX_SECTION_HASHES;
    let hashes = sections
        .into_iter()
        .take(MAX_SECTION_HASHES)
        .map(|section| SectionHash {
            anchor: section.anchor,
            level: section.level,
            sha256: hash(&body.as_bytes()[section.whole]),
        })
        .collect();
    (hashes, truncated)
}

pub(crate) fn apply(body: &str, edits: &[PagePatchEdit]) -> Result<String, PatchError> {
    validate_bounds(edits)?;
    let sections = parse_sections(body);
    let mut by_anchor: HashMap<&str, Vec<&Section>> = HashMap::new();
    for section in &sections {
        by_anchor
            .entry(section.normalized.as_str())
            .or_default()
            .push(section);
    }

    let mut targets = HashSet::new();
    let mut added = HashSet::new();
    let mut changes = Vec::with_capacity(edits.len());
    for edit in edits {
        let change = match edit {
            PagePatchEdit::Append {
                target: AppendTarget::EndOfPage,
                anchor,
                content,
            } => {
                if anchor
                    .as_deref()
                    .is_some_and(|value| !value.trim().is_empty())
                {
                    return Err(PatchError::UnexpectedAnchor);
                }
                if !targets.insert("\0eof".to_string()) {
                    return Err(PatchError::DuplicateTarget("end_of_page".into()));
                }
                Change {
                    range: body.len()..body.len(),
                    replacement: appended(body, content),
                }
            }
            PagePatchEdit::Append {
                target: AppendTarget::Section,
                anchor,
                content,
            } => {
                let raw = anchor.as_deref().ok_or(PatchError::MissingAnchor)?;
                let section = find_section(&by_anchor, raw)?;
                if !targets.insert(section.normalized.clone()) {
                    return Err(PatchError::DuplicateTarget(section.anchor.clone()));
                }
                Change {
                    range: section.whole.end..section.whole.end,
                    replacement: appended(&body[section.whole.clone()], content),
                }
            }
            PagePatchEdit::AddSection { anchor, content } => {
                let (level, title) = parse_single_heading(anchor)?;
                let normalized = normalize_anchor(&title);
                if by_anchor.contains_key(normalized.as_str()) || !added.insert(normalized.clone())
                {
                    return Err(PatchError::HeadingExists(title));
                }
                targets.insert(format!("\0add:{normalized}"));
                let heading = format!("{} {}", "#".repeat(level as usize), title);
                Change {
                    range: body.len()..body.len(),
                    replacement: appended(body, &format!("{heading}\n{content}")),
                }
            }
            PagePatchEdit::ReplaceSection {
                anchor,
                section_sha256,
                content,
            } => {
                let section = find_section(&by_anchor, anchor)?;
                if !targets.insert(section.normalized.clone()) {
                    return Err(PatchError::DuplicateTarget(section.anchor.clone()));
                }
                if !constant_time_eq(
                    section_sha256.trim(),
                    &hash(&body.as_bytes()[section.whole.clone()]),
                ) {
                    return Err(PatchError::SectionPreconditionFailed(
                        section.anchor.clone(),
                    ));
                }
                Change {
                    range: section.content.clone(),
                    replacement: section_content(content),
                }
            }
        };
        changes.push(change);
    }

    changes.sort_by_key(|change| (change.range.start, change.range.end));
    let mut merged: Vec<Change> = Vec::with_capacity(changes.len());
    for change in changes {
        if let Some(previous) = merged.last_mut()
            && previous.range.is_empty()
            && change.range == previous.range
        {
            previous.replacement.push_str(&change.replacement);
            continue;
        }
        if merged
            .last()
            .is_some_and(|previous| previous.range.end > change.range.start)
        {
            return Err(PatchError::Overlapping);
        }
        merged.push(change);
    }
    let mut result = body.to_owned();
    for change in merged.into_iter().rev() {
        result.replace_range(change.range, &change.replacement);
    }
    Ok(result)
}

fn validate_bounds(edits: &[PagePatchEdit]) -> Result<(), PatchError> {
    if edits.is_empty() {
        return Err(PatchError::Empty);
    }
    if edits.len() > MAX_EDITS {
        return Err(PatchError::TooMany);
    }
    let sizes = edits.iter().map(|edit| match edit {
        PagePatchEdit::Append { content, .. }
        | PagePatchEdit::AddSection { content, .. }
        | PagePatchEdit::ReplaceSection { content, .. } => content.chars().count(),
    });
    let mut total = 0usize;
    for size in sizes {
        if size > MAX_EDIT_CHARS {
            return Err(PatchError::ContentTooLarge);
        }
        total = total.saturating_add(size);
    }
    if total > MAX_CHANGED_CHARS {
        return Err(PatchError::BatchTooLarge);
    }
    Ok(())
}

fn find_section<'a>(
    sections: &'a HashMap<&str, Vec<&Section>>,
    anchor: &str,
) -> Result<&'a Section, PatchError> {
    let normalized = normalize_anchor(anchor);
    match sections.get(normalized.as_str()).map(Vec::as_slice) {
        None | Some([]) => Err(PatchError::AnchorNotFound(anchor.to_owned())),
        Some([section]) => Ok(section),
        Some(_) => Err(PatchError::AmbiguousAnchor(anchor.to_owned())),
    }
}

fn parse_sections(body: &str) -> Vec<Section> {
    let mut headings = Vec::new();
    let mut offset = 0usize;
    let mut fence: Option<(char, usize)> = None;
    for line_with_newline in body.split_inclusive('\n') {
        let line = line_with_newline
            .strip_suffix('\n')
            .unwrap_or(line_with_newline);
        if let Some((marker, width)) = fence {
            if closes_fence(line, marker, width) {
                fence = None;
            }
        } else if let Some(marker) = fence_marker(line) {
            fence = Some(marker);
        } else if let Some((level, anchor)) = heading(line) {
            headings.push((offset, offset + line_with_newline.len(), level, anchor));
        }
        offset += line_with_newline.len();
    }
    headings
        .iter()
        .enumerate()
        .map(|(index, (start, content_start, level, anchor))| {
            let end = headings[index + 1..]
                .iter()
                .find(|(_, _, next_level, _)| next_level <= level)
                .map(|(next_start, _, _, _)| *next_start)
                .unwrap_or(body.len());
            Section {
                anchor: anchor.clone(),
                normalized: normalize_anchor(anchor),
                level: *level,
                whole: *start..end,
                content: *content_start..end,
            }
        })
        .collect()
}

fn heading(line: &str) -> Option<(u8, String)> {
    let trimmed = line
        .strip_prefix("   ")
        .unwrap_or(line.trim_start_matches(' '));
    if line.len() - trimmed.len() > 3 {
        return None;
    }
    let hashes = trimmed.bytes().take_while(|byte| *byte == b'#').count();
    if !(1..=6).contains(&hashes)
        || !trimmed
            .as_bytes()
            .get(hashes)
            .is_none_or(u8::is_ascii_whitespace)
    {
        return None;
    }
    let mut title = trimmed[hashes..].trim().to_owned();
    // A trailing `#` run closes the heading only after a space or tab
    // (CommonMark), so `## C#` keeps its `#`.
    let without_closing = title.trim_end_matches('#');
    if without_closing.is_empty() || without_closing.ends_with([' ', '\t']) {
        title = without_closing.trim_end().to_owned();
    }
    (!title.is_empty()).then_some((hashes as u8, title))
}

fn fence_marker(line: &str) -> Option<(char, usize)> {
    let trimmed = line.trim_start_matches(' ');
    if line.len() - trimmed.len() > 3 {
        return None;
    }
    let marker = trimmed.chars().next()?;
    if marker != '`' && marker != '~' {
        return None;
    }
    let width = trimmed.chars().take_while(|c| *c == marker).count();
    (width >= 3).then_some((marker, width))
}

fn closes_fence(line: &str, marker: char, width: usize) -> bool {
    let trimmed = line.trim_start_matches(' ');
    if line.len() - trimmed.len() > 3 {
        return false;
    }
    let count = trimmed
        .chars()
        .take_while(|candidate| *candidate == marker)
        .count();
    count >= width && trimmed[count..].trim().is_empty()
}

fn parse_single_heading(raw: &str) -> Result<(u8, String), PatchError> {
    if raw.contains('\n') {
        return Err(PatchError::InvalidNewHeading);
    }
    let (level, title) = heading(raw).ok_or(PatchError::InvalidNewHeading)?;
    if level == 1 {
        return Err(PatchError::InvalidNewHeading);
    }
    Ok((level, title))
}

fn normalize_anchor(raw: &str) -> String {
    let title = heading(raw)
        .map(|(_, title)| title)
        .unwrap_or_else(|| raw.to_owned());
    title
        .split_whitespace()
        .collect::<Vec<_>>()
        .join(" ")
        .to_lowercase()
}

fn appended(existing: &str, content: &str) -> String {
    let prefix = if existing.is_empty() || existing.ends_with('\n') {
        ""
    } else {
        "\n"
    };
    let suffix = if content.ends_with('\n') { "" } else { "\n" };
    format!("{prefix}{content}{suffix}")
}

fn section_content(content: &str) -> String {
    let suffix = if content.is_empty() || content.ends_with('\n') {
        ""
    } else {
        "\n"
    };
    format!("{content}{suffix}")
}

fn hash(bytes: &[u8]) -> String {
    format!("{:x}", Sha256::digest(bytes))
}

fn constant_time_eq(left: &str, right: &str) -> bool {
    left.len() == right.len()
        && left
            .bytes()
            .zip(right.bytes())
            .fold(0u8, |different, (a, b)| different | (a ^ b))
            == 0
}

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

    #[test]
    fn hashes_ignore_headings_inside_fences_and_flag_duplicates() {
        let body = "# T\n## Same\na\n```md\n## Hidden\n```\n## Same\nb\n";
        let (sections, truncated) = section_hashes(body);
        assert!(!truncated);
        assert_eq!(sections.iter().filter(|s| s.anchor == "Same").count(), 2);
        assert!(!sections.iter().any(|s| s.anchor == "Hidden"));
        assert_eq!(
            apply(
                body,
                &[PagePatchEdit::Append {
                    target: AppendTarget::Section,
                    anchor: Some("same".into()),
                    content: "x".into(),
                }]
            ),
            Err(PatchError::AmbiguousAnchor("same".into()))
        );
    }

    #[test]
    fn replaces_one_section_only_with_its_hash() {
        let body = "# T\n## One\nold\n### Child\nkept in section\n## Two\nother\n";
        let hash = section_hashes(body)
            .0
            .into_iter()
            .find(|section| section.anchor == "One")
            .unwrap()
            .sha256;
        let patched = apply(
            body,
            &[PagePatchEdit::ReplaceSection {
                anchor: "## One".into(),
                section_sha256: hash,
                content: "new".into(),
            }],
        )
        .unwrap();
        assert_eq!(patched, "# T\n## One\nnew\n## Two\nother\n");
    }

    #[test]
    fn stale_hash_and_conflicting_targets_fail_without_output() {
        let body = "# T\n## One\nold\n";
        assert!(matches!(
            apply(
                body,
                &[PagePatchEdit::ReplaceSection {
                    anchor: "One".into(),
                    section_sha256: "0".repeat(64),
                    content: "new".into(),
                }]
            ),
            Err(PatchError::SectionPreconditionFailed(_))
        ));
        let edits = [
            PagePatchEdit::Append {
                target: AppendTarget::Section,
                anchor: Some("One".into()),
                content: "a".into(),
            },
            PagePatchEdit::Append {
                target: AppendTarget::Section,
                anchor: Some("one".into()),
                content: "b".into(),
            },
        ];
        assert!(matches!(
            apply(body, &edits),
            Err(PatchError::DuplicateTarget(_))
        ));
    }

    #[test]
    fn appends_to_section_or_page_and_adds_a_unique_section() {
        let body = "# T\n## Log\none\n## Tail\ntwo";
        let patched = apply(
            body,
            &[
                PagePatchEdit::Append {
                    target: AppendTarget::Section,
                    anchor: Some("Log".into()),
                    content: "next".into(),
                },
                PagePatchEdit::AddSection {
                    anchor: "## Fresh".into(),
                    content: "new".into(),
                },
            ],
        )
        .unwrap();
        assert_eq!(
            patched,
            "# T\n## Log\none\nnext\n## Tail\ntwo\n## Fresh\nnew\n"
        );
    }

    #[test]
    fn a_trailing_hash_closes_a_heading_only_after_a_space() {
        let body = "# T\n## Notes on C#\nold\n## Tail ##\nend\n";
        let anchors: Vec<_> = section_hashes(body)
            .0
            .into_iter()
            .map(|section| section.anchor)
            .collect();
        assert_eq!(anchors, ["T", "Notes on C#", "Tail"]);
        let patched = apply(
            body,
            &[
                PagePatchEdit::Append {
                    target: AppendTarget::Section,
                    anchor: Some("Notes on C#".into()),
                    content: "more".into(),
                },
                PagePatchEdit::AddSection {
                    anchor: "## F#".into(),
                    content: "new".into(),
                },
            ],
        )
        .unwrap();
        assert_eq!(
            patched,
            "# T\n## Notes on C#\nold\nmore\n## Tail ##\nend\n## F#\nnew\n"
        );
    }
}