Skip to content

web search done right

5.0 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

pub trait SplitWithRange {
    fn split_with_range<P>(&self, pred: P) -> impl Iterator<Item = (&str, std::ops::Range<usize>)>
    where
        P: Fn(char) -> bool;
}

pub trait SplitWhitespaceWithRange {
    fn split_whitespace_with_range(&self) -> impl Iterator<Item = (&str, std::ops::Range<usize>)>;
}

pub struct SplitWithRangeIter<'a, P> {
    s: &'a str,
    pred: P,
    start: usize,
}

impl<'a, P> SplitWithRangeIter<'a, P> {
    fn new(s: &'a str, pred: P) -> Self {
        Self { s, pred, start: 0 }
    }
}

impl<'a, P> Iterator for SplitWithRangeIter<'a, P>
where
    P: Fn(char) -> bool,
{
    type Item = (&'a str, std::ops::Range<usize>);

    fn next(&mut self) -> Option<Self::Item> {
        for c in self.s[self.start..].chars() {
            if !(self.pred)(c) {
                break;
            }
            self.start += c.len_utf8();
        }

        if self.start >= self.s.len() {
            return None;
        }

        let start = self.s[self.start..].find(|c: char| !(self.pred)(c))?;
        let start = self.start + start;
        let end = self.s[start..]
            .find(|c| (self.pred)(c))
            .map(|end| start + end)
            .unwrap_or(self.s.len());
        let range = start..end;
        self.start = end;
        Some((&self.s[range.clone()], range))
    }
}

impl SplitWhitespaceWithRange for str {
    fn split_whitespace_with_range(&self) -> impl Iterator<Item = (&str, std::ops::Range<usize>)> {
        self.split_with_range(char::is_whitespace)
    }
}

impl SplitWhitespaceWithRange for String {
    fn split_whitespace_with_range(&self) -> impl Iterator<Item = (&str, std::ops::Range<usize>)> {
        self.split_with_range(char::is_whitespace)
    }
}

impl SplitWithRange for str {
    fn split_with_range<P>(&self, pred: P) -> impl Iterator<Item = (&str, std::ops::Range<usize>)>
    where
        P: Fn(char) -> bool,
    {
        SplitWithRangeIter::new(self, pred)
    }
}

impl SplitWithRange for String {
    fn split_with_range<P>(&self, pred: P) -> impl Iterator<Item = (&str, std::ops::Range<usize>)>
    where
        P: Fn(char) -> bool,
    {
        SplitWithRangeIter::new(self, pred)
    }
}

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

    #[test]
    fn test_split_whitespace_with_range() {
        let txt = "Hello, world! 123";
        let tokens: Vec<_> = txt.split_whitespace_with_range().collect();
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], ("Hello,", 0..6));
        assert_eq!(tokens[1], ("world!", 7..13));
        assert_eq!(tokens[2], ("123", 14..17));
    }

    #[test]
    fn test_split_whitespace_with_range_empty() {
        let txt = "";
        let tokens: Vec<_> = txt.split_whitespace_with_range().collect();
        assert_eq!(tokens.len(), 0);
    }

    #[test]
    fn test_multi_whitespace() {
        let txt = "Hello,   world! 123";
        let tokens: Vec<_> = txt.split_whitespace_with_range().collect();
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], ("Hello,", 0..6));
        assert_eq!(tokens[1], ("world!", 9..15));
        assert_eq!(tokens[2], ("123", 16..19));
    }

    #[test]
    fn unicode() {
        let txt = "best café";
        let tokens: Vec<_> = txt.split_whitespace_with_range().collect();
        assert_eq!(tokens.len(), 2);
        assert_eq!(tokens[0], ("best", 0..4));
        assert_eq!(tokens[1], ("café", 5..10));

        let txt = "Hello, 世界! 123";
        let tokens: Vec<_> = txt.split_whitespace_with_range().collect();
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], ("Hello,", 0..6));
        assert_eq!(tokens[1], ("世界!", 7..14));
        assert_eq!(tokens[2], ("123", 15..18));
    }

    proptest! {
        #[test]
        fn prop_split_whitespace_with_range(s: String) {
            let tokens: Vec<_> = s.split_whitespace_with_range().collect();
            for (txt, range) in tokens {
                assert_eq!(&s[range.clone()], txt);
            }
        }

        #[test]
        fn consistent_with_std(s: String) {
            let tokens: Vec<_> = s.split_whitespace().collect();
            let tokens_with_range: Vec<_> = s.split_whitespace_with_range().collect();
            let tokens_with_range: Vec<_> = tokens_with_range.into_iter().map(|(txt, _)| txt).collect();
            assert_eq!(tokens, tokens_with_range);
        }
    }
}