uqa-analysis 0.3.0

//
// Unified Query Algebra
//
// Copyright (c) 2023-2026 Cognica, Inc.
//

//! Ordered character edits write directly into reserved text and source-map buffers.

use uqa_core::memory::MemoryBudget;

use super::replacement::Replacement;
use crate::cooperative_regex::CooperativeRegex;
use crate::source::EditBuilder;
use crate::{AnalysisResult, FilteredText};

pub(super) fn replace_html(
    text: &mut FilteredText<'_>,
    budget: &MemoryBudget,
    poll: &mut dyn FnMut() -> AnalysisResult<()>,
) -> AnalysisResult<()> {
    poll()?;
    let edited = {
        let input = text.as_str();
        let mut builder = EditBuilder::new(input, budget, poll);
        let mut index = 0;
        while index < input.len() {
            builder.check()?;
            let character = input[index..].chars().next().expect("valid UTF-8 boundary");
            if character != '<' {
                index += character.len_utf8();
                continue;
            }
            let mut cursor = index + character.len_utf8();
            let mut has_content = false;
            let mut end = None;
            let mut closed = false;
            while cursor < input.len() {
                builder.check()?;
                let character = input[cursor..]
                    .chars()
                    .next()
                    .expect("valid UTF-8 boundary");
                if character == '>' {
                    closed = true;
                    if has_content {
                        end = cursor.checked_add(character.len_utf8());
                    }
                    break;
                }
                has_content = true;
                cursor += character.len_utf8();
            }
            if let Some(end) = end {
                builder.edit(index..end, std::iter::once(" "))?;
                index = end;
            } else if !closed {
                break;
            } else {
                index += character.len_utf8();
            }
        }
        builder.finish()?
    };
    text.apply_edited(edited, budget, poll)
}

pub(super) fn replace_literal(
    text: &mut FilteredText<'_>,
    old: &str,
    new: &str,
    budget: &MemoryBudget,
    poll: &mut dyn FnMut() -> AnalysisResult<()>,
) -> AnalysisResult<()> {
    poll()?;
    let edited = {
        let input = text.as_str();
        let mut builder = EditBuilder::new(input, budget, poll);
        if old.is_empty() {
            for (index, _) in input.char_indices() {
                builder.check()?;
                builder.edit(index..index, std::iter::once(new))?;
            }
            builder.edit(input.len()..input.len(), std::iter::once(new))?;
        } else {
            let input_bytes = input.as_bytes();
            let old_bytes = old.as_bytes();
            if let Some(last_start) = input_bytes.len().checked_sub(old_bytes.len()) {
                let mut start = 0;
                let mut scanned = 0;
                while start <= last_start {
                    if scanned % 1024 == 0 {
                        builder.check()?;
                    }
                    if input.is_char_boundary(start)
                        && bytes_equal(input_bytes, old_bytes, start, &mut builder)?
                    {
                        let end = start + old_bytes.len();
                        builder.edit(start..end, std::iter::once(new))?;
                        start = end;
                    } else {
                        start += 1;
                    }
                    scanned += 1;
                }
            }
        }
        builder.finish()?
    };
    text.apply_edited(edited, budget, poll)
}

fn bytes_equal(
    input: &[u8],
    pattern: &[u8],
    start: usize,
    builder: &mut EditBuilder<'_, '_>,
) -> AnalysisResult<bool> {
    for (left, right) in input[start..start + pattern.len()]
        .chunks(1024)
        .zip(pattern.chunks(1024))
    {
        builder.check()?;
        if left != right {
            return Ok(false);
        }
    }
    Ok(true)
}

pub(super) fn replace_pattern(
    text: &mut FilteredText<'_>,
    pattern: &CooperativeRegex,
    replacement: &Replacement<'_>,
    budget: &MemoryBudget,
    poll: &mut dyn FnMut() -> AnalysisResult<()>,
) -> AnalysisResult<()> {
    poll()?;
    let mut search = pattern.searcher(budget, replacement.uses_captures(), poll)?;
    let edited = {
        let input = text.as_str();
        let mut builder = EditBuilder::new(input, budget, poll);
        let mut start = 0;
        let mut last_end = None;
        loop {
            builder.check()?;
            let Some(matched) = search.find_at(input, start, &mut || builder.check())? else {
                break;
            };
            if matched.is_empty() && Some(matched.end) == last_end {
                if start == input.len() {
                    break;
                }
                start += 1;
                continue;
            }
            builder.edit(
                matched.clone(),
                replacement.fragments(search.captures(), input),
            )?;
            start = matched.end;
            last_end = Some(start);
        }
        builder.finish()?
    };
    drop(search);
    text.apply_edited(edited, budget, poll)
}

#[cfg(test)]
mod tests {
    use super::{replace_html, replace_literal, replace_pattern};
    use crate::{AnalysisError, FilteredText};
    use regex::Regex;
    use uqa_core::memory::MemoryBudget;

    use super::super::replacement::Replacement;
    use crate::cooperative_regex::CooperativeRegex;

    #[test]
    fn literal_search_polls_inside_a_long_unmatched_input() {
        let input = "x".repeat(128 * 1024);
        let mut text = FilteredText::new(&input);
        let budget = MemoryBudget::new(0);
        let mut polls = 0;
        replace_literal(&mut text, "needle", "replacement", &budget, &mut || {
            polls += 1;
            Ok(())
        })
        .unwrap();
        assert!(polls > input.len() / 2048);
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn literal_search_cancellation_releases_an_unpublished_edit() {
        let input = "x".repeat(128 * 1024);
        let mut text = FilteredText::new(&input);
        let budget = MemoryBudget::new(1 << 20);
        let mut polls = 0;
        let result = replace_literal(&mut text, "needle", "replacement", &budget, &mut || {
            polls += 1;
            if polls == 8 {
                Err(AnalysisError::Cancelled)
            } else {
                Ok(())
            }
        });
        assert!(matches!(result, Err(AnalysisError::Cancelled)));
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn configured_pattern_scan_polls_through_a_long_unmatched_input() {
        let input = "x".repeat(128 * 1024);
        let mut text = FilteredText::new(&input);
        let replacement = Replacement::literal("#");
        let cooperative = CooperativeRegex::compile("needle").unwrap();
        let budget = MemoryBudget::new(0);
        let mut polls = 0;
        replace_pattern(&mut text, &cooperative, &replacement, &budget, &mut || {
            polls += 1;
            Ok(())
        })
        .unwrap();
        assert!(polls > input.len() / 2048);
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn configured_pattern_scan_cancellation_releases_unpublished_edit() {
        let input = "x".repeat(128 * 1024);
        let mut text = FilteredText::new(&input);
        let replacement = Replacement::literal("#");
        let cooperative = CooperativeRegex::compile("needle").unwrap();
        let budget = MemoryBudget::new(1 << 20);
        let mut polls = 0;
        let result = replace_pattern(&mut text, &cooperative, &replacement, &budget, &mut || {
            polls += 1;
            if polls == 8 {
                Err(AnalysisError::Cancelled)
            } else {
                Ok(())
            }
        });
        assert!(matches!(result, Err(AnalysisError::Cancelled)));
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn capture_pattern_scan_polls_before_resolving_replacement_captures() {
        let prefix = "x".repeat(128 * 1024);
        let input = format!("{prefix}needle");
        let mut text = FilteredText::new(&input);
        let pattern = Regex::new("(needle)").unwrap();
        let replacement = Replacement::prepare("<$1>", &pattern);
        let cooperative = CooperativeRegex::compile("(needle)").unwrap();
        let budget = MemoryBudget::new(1 << 20);
        let mut polls = 0;
        replace_pattern(&mut text, &cooperative, &replacement, &budget, &mut || {
            polls += 1;
            Ok(())
        })
        .unwrap();
        assert!(polls > input.len() / 2048);
        assert_eq!(text.as_str(), format!("{prefix}<needle>"));
    }

    #[test]
    fn capture_pattern_scan_cancellation_releases_unpublished_edit() {
        let input = "x".repeat(128 * 1024);
        let mut text = FilteredText::new(&input);
        let pattern = Regex::new("(needle)").unwrap();
        let replacement = Replacement::prepare("<$1>", &pattern);
        let cooperative = CooperativeRegex::compile("(needle)").unwrap();
        let budget = MemoryBudget::new(1 << 20);
        let mut polls = 0;
        let result = replace_pattern(&mut text, &cooperative, &replacement, &budget, &mut || {
            polls += 1;
            if polls == 8 {
                Err(AnalysisError::Cancelled)
            } else {
                Ok(())
            }
        });
        assert!(matches!(result, Err(AnalysisError::Cancelled)));
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn capture_pattern_replacement_resolves_captures_after_range_search() {
        let input = "prefix foobar suffix";
        let mut text = FilteredText::new(input);
        let pattern = Regex::new("(foo)(bar)").unwrap();
        let replacement = Replacement::prepare("<$2-$1>", &pattern);
        let cooperative = CooperativeRegex::compile("(foo)(bar)").unwrap();
        replace_pattern(
            &mut text,
            &cooperative,
            &replacement,
            &MemoryBudget::new(1 << 20),
            &mut || Ok(()),
        )
        .unwrap();
        assert_eq!(text.as_str(), "prefix <bar-foo> suffix");
    }

    #[test]
    fn capture_pattern_preserves_anchors_after_a_nonzero_restart() {
        let input = "xab";
        let mut text = FilteredText::new(input);
        let pattern = Regex::new(r"(^ab|b|x)").unwrap();
        let replacement = Replacement::prepare("<$1>", &pattern);
        let cooperative = CooperativeRegex::compile(r"(^ab|b|x)").unwrap();
        replace_pattern(
            &mut text,
            &cooperative,
            &replacement,
            &MemoryBudget::new(1 << 20),
            &mut || Ok(()),
        )
        .unwrap();
        assert_eq!(text.as_str(), "<x>a<b>");
    }

    #[test]
    fn capture_pattern_reserves_all_capture_slots_before_search() {
        let input = "x".repeat(128 * 1024);
        let mut text = FilteredText::new(&input);
        let pattern = Regex::new("(needle)").unwrap();
        let replacement = Replacement::prepare("<$1>", &pattern);
        let cooperative = CooperativeRegex::compile("(needle)").unwrap();
        let budget = MemoryBudget::new(0);
        let result = replace_pattern(&mut text, &cooperative, &replacement, &budget, &mut || {
            Ok(())
        });
        assert!(matches!(
            result,
            Err(crate::AnalysisError::Memory(
                uqa_core::memory::MemoryError::Limit { .. }
            ))
        ));
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn html_scan_matches_the_pinned_regex_on_small_inputs() {
        let regex = Regex::new(r"<[^>]+>").unwrap();
        let mut input = String::new();
        visit_html_inputs(&mut input, &regex, 5);
    }

    fn visit_html_inputs(input: &mut String, regex: &Regex, remaining: usize) {
        if remaining == 0 {
            let expected = regex.replace_all(input, " ");
            let mut text = FilteredText::new(input);
            replace_html(&mut text, &MemoryBudget::new(1 << 20), &mut || Ok(())).unwrap();
            assert_eq!(text.as_str(), expected.as_ref());
            return;
        }
        for character in ['<', '>', 'a', '🙂'] {
            input.push(character);
            visit_html_inputs(input, regex, remaining - 1);
            input.pop();
        }
    }

    #[test]
    fn html_scan_polls_through_a_long_unmatched_input() {
        let input = format!("{}x", "<".repeat(128 * 1024));
        let mut text = FilteredText::new(&input);
        let budget = MemoryBudget::new(0);
        let mut polls = 0;
        replace_html(&mut text, &budget, &mut || {
            polls += 1;
            Ok(())
        })
        .unwrap();
        assert!(polls > input.len() / 2048);
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }

    #[test]
    fn html_scan_cancellation_releases_an_unpublished_edit() {
        let input = format!("{}x", "<".repeat(128 * 1024));
        let mut text = FilteredText::new(&input);
        let budget = MemoryBudget::new(1 << 20);
        let mut polls = 0;
        let result = replace_html(&mut text, &budget, &mut || {
            polls += 1;
            if polls == 8 {
                Err(AnalysisError::Cancelled)
            } else {
                Ok(())
            }
        });
        assert!(matches!(result, Err(AnalysisError::Cancelled)));
        assert_eq!(text.as_str(), input);
        assert_eq!(budget.used(), 0);
    }
}