#
rustfix/
replace.rs

    1//! A small module giving you a simple container that allows
    2//! easy and cheap replacement of parts of its content,
    3//! with the ability to commit or rollback pending changes.
    4//!
    5//! Create a new [`Data`] struct with some initial set of code,
    6//! then record changes with [`Data::replace_range`],
    7//! which will validate that the changes do not conflict with one another.
    8//! At any time, you can "checkpoint" the current changes with [`Data::commit`]
    9//! or roll them back (perhaps due to a conflict) with [`Data::restore`].
    10//! When you're done, use [`Data::to_vec`]
    11//! to merge the original data with the changes.
    12//!
    13//! # Notes
    14//!
    15//! The [`Data::to_vec`] method includes uncommitted changes, if present.
    16//! The reason for including uncommitted changes is that typically, once you're calling those,
    17//! you're done with edits and will be dropping the [`Data`] struct in a moment.
    18//! In this case, requiring an extra call to `commit` would be unnecessary work.
    19//! Of course, there's no harm in calling `commit`---it's just not strictly necessary.
    20//!
    21//! Put another way, the main point of `commit` is to checkpoint a set of known-good changes
    22//! before applying additional sets of as-of-yet unvalidated changes.
    23//! If no future changes are expected, you aren't _required_ to pay the cost of `commit`.
    24//! If you want to discard uncommitted changes, simply call [`Data::restore`] first.
    25
    26use std::ops::Range;
    27use std::rc::Rc;
    28
    29use crate::error::Error;
    30
    31/// Data that should replace a particular range of the original.
    32#[derive(Clone)]
    33struct Span {
    34    /// Span of the parent data to be replaced, inclusive of the start, exclusive of the end.
    35    range: Range<usize>,
    36    /// New data to insert at the `start` position of the `original` data.
    37    data: Rc<[u8]>,
    38    /// Whether this data is committed or provisional.
    39    committed: bool,
    40}
    41
    42impl std::fmt::Debug for Span {
    43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    44        let state = if self.is_insert() {
    45            "inserted"
    46        } else {
    47            "replaced"
    48        };
    49
    50        let committed = if self.committed {
    51            "committed"
    52        } else {
    53            "uncommitted"
    54        };
    55
    56        write!(
    57            f,
    58            "({}, {}: {state}, {committed})",
    59            self.range.start, self.range.end
    60        )
    61    }
    62}
    63
    64impl Span {
    65    fn new(range: Range<usize>, data: &[u8]) -> Self {
    66        Self {
    67            range,
    68            data: data.into(),
    69            committed: false,
    70        }
    71    }
    72
    73    /// Returns `true` if and only if this is a "pure" insertion,
    74    /// i.e. does not remove any existing data.
    75    ///
    76    /// The insertion point is the `start` position of the range.
    77    fn is_insert(&self) -> bool {
    78        self.range.start == self.range.end
    79    }
    80}
    81
    82impl PartialEq for Span {
    83    /// Returns `true` if and only if this `Span` and `other` have the same range and data,
    84    /// regardless of `committed` status.
    85    fn eq(&self, other: &Self) -> bool {
    86        self.range == other.range && self.data == other.data
    87    }
    88}
    89
    90/// A container that allows easily replacing chunks of its data.
    91#[derive(Debug, Clone, Default)]
    92pub struct Data {
    93    /// Original data.
    94    original: Vec<u8>,
    95    /// [`Span`]s covering the full range of the original data.
    96    /// Important: it's expected that the underlying implementation maintains this in order,
    97    /// sorted ascending by start position.
    98    parts: Vec<Span>,
    99}
    100
    101impl Data {
    102    /// Create a new data container from a slice of bytes
    103    pub fn new(data: &[u8]) -> Self {
    104        Data {
    105            original: data.into(),
    106            parts: vec![],
    107        }
    108    }
    109
    110    /// Commit the current changes.
    111    pub fn commit(&mut self) {
    112        self.parts.iter_mut().for_each(|span| span.committed = true);
    113    }
    114
    115    /// Discard uncommitted changes.
    116    pub fn restore(&mut self) {
    117        self.parts.retain(|parts| parts.committed);
    118    }
    119
    120    /// Merge the original data with changes, **including** uncommitted changes.
    121    ///
    122    /// See the module-level documentation for more information on why uncommitted changes are included.
    123    pub fn to_vec(&self) -> Vec<u8> {
    124        let mut prev_end = 0;
    125        let mut s = self.parts.iter().fold(Vec::new(), |mut acc, span| {
    126            // Hedge against potential implementation errors.
    127            debug_assert!(
    128                prev_end <= span.range.start,
    129                "expected parts in sorted order"
    130            );
    131
    132            acc.extend_from_slice(&self.original[prev_end..span.range.start]);
    133            acc.extend_from_slice(&span.data);
    134            prev_end = span.range.end;
    135            acc
    136        });
    137
    138        // Append remaining data, if any.
    139        s.extend_from_slice(&self.original[prev_end..]);
    140        s
    141    }
    142
    143    /// Record a provisional change.
    144    ///
    145    /// If committed, the original data in the given `range` will be replaced by the given data.
    146    /// If there already exist changes for data in the given range (committed or not),
    147    /// this method will return an error.
    148    /// It will also return an error if the beginning of the range comes before its end,
    149    /// or if the range is outside that of the original data.
    150    pub fn replace_range(&mut self, range: Range<usize>, data: &[u8]) -> Result<(), Error> {
    151        if range.start > range.end {
    152            return Err(Error::InvalidRange(range));
    153        }
    154
    155        if range.end > self.original.len() {
    156            return Err(Error::DataLengthExceeded(range, self.original.len()));
    157        }
    158
    159        // Keep sorted by start position, or by end position if the start position is the same,
    160        // which has the effect of keeping a pure insertion ahead of a replacement.
    161        // That limits the kinds of conflicts that can happen, simplifying the checks below.
    162        let ins_point = self.parts.partition_point(|span| {
    163            span.range.start < range.start
    164                || (span.range.start == range.start && span.range.end < range.end)
    165        });
    166
    167        let incoming = Span::new(range, data.as_ref());
    168
    169        // Reject if the change starts before the previous one ends.
    170        if let Some(before) = ins_point.checked_sub(1).and_then(|i| self.parts.get(i)) {
    171            if incoming.range.start < before.range.end {
    172                return Err(Error::AlreadyReplaced {
    173                    is_identical: incoming == *before,
    174                    range: incoming.range,
    175                });
    176            }
    177        }
    178
    179        // Reject if the change ends after the next one starts,
    180        // or if this is an insert and there's already an insert there.
    181        if let Some(after) = self.parts.get(ins_point) {
    182            if incoming.range.end > after.range.start || incoming.range == after.range {
    183                return Err(Error::AlreadyReplaced {
    184                    is_identical: incoming == *after,
    185                    range: incoming.range,
    186                });
    187            }
    188        }
    189
    190        self.parts.insert(ins_point, incoming);
    191        Ok(())
    192    }
    193}
    194
    195#[cfg(test)]
    196mod tests {
    197    use super::*;
    198    use proptest::prelude::*;
    199
    200    fn str(i: &[u8]) -> &str {
    201        ::std::str::from_utf8(i).unwrap()
    202    }
    203
    204    #[test]
    205    fn insert_at_beginning() {
    206        let mut d = Data::new(b"foo bar baz");
    207        d.replace_range(0..0, b"oh no ").unwrap();
    208        assert_eq!("oh no foo bar baz", str(&d.to_vec()));
    209    }
    210
    211    #[test]
    212    fn insert_at_end() {
    213        let mut d = Data::new(b"foo bar baz");
    214        d.replace_range(11..11, b" oh no").unwrap();
    215        assert_eq!("foo bar baz oh no", str(&d.to_vec()));
    216    }
    217
    218    #[test]
    219    fn replace_some_stuff() {
    220        let mut d = Data::new(b"foo bar baz");
    221        d.replace_range(4..7, b"lol").unwrap();
    222        assert_eq!("foo lol baz", str(&d.to_vec()));
    223    }
    224
    225    #[test]
    226    fn replace_a_single_char() {
    227        let mut d = Data::new(b"let y = true;");
    228        d.replace_range(4..5, b"mut y").unwrap();
    229        assert_eq!("let mut y = true;", str(&d.to_vec()));
    230    }
    231
    232    #[test]
    233    fn replace_multiple_lines() {
    234        let mut d = Data::new(b"lorem\nipsum\ndolor");
    235
    236        d.replace_range(6..11, b"lol").unwrap();
    237        assert_eq!("lorem\nlol\ndolor", str(&d.to_vec()));
    238
    239        d.replace_range(12..17, b"lol").unwrap();
    240        assert_eq!("lorem\nlol\nlol", str(&d.to_vec()));
    241    }
    242
    243    #[test]
    244    fn replace_multiple_lines_with_insert_only() {
    245        let mut d = Data::new(b"foo!");
    246
    247        d.replace_range(3..3, b"bar").unwrap();
    248        assert_eq!("foobar!", str(&d.to_vec()));
    249
    250        d.replace_range(0..3, b"baz").unwrap();
    251        assert_eq!("bazbar!", str(&d.to_vec()));
    252
    253        d.replace_range(3..4, b"?").unwrap();
    254        assert_eq!("bazbar?", str(&d.to_vec()));
    255    }
    256
    257    #[test]
    258    #[allow(clippy::reversed_empty_ranges)]
    259    fn replace_invalid_range() {
    260        let mut d = Data::new(b"foo!");
    261
    262        assert!(d.replace_range(2..1, b"bar").is_err());
    263        assert!(d.replace_range(0..3, b"bar").is_ok());
    264    }
    265
    266    #[test]
    267    fn empty_to_vec_roundtrip() {
    268        let s = "";
    269        assert_eq!(s.as_bytes(), Data::new(s.as_bytes()).to_vec().as_slice());
    270    }
    271
    272    #[test]
    273    fn replace_same_range_diff_data() {
    274        let mut d = Data::new(b"foo bar baz");
    275
    276        d.replace_range(4..7, b"lol").unwrap();
    277        assert_eq!("foo lol baz", str(&d.to_vec()));
    278
    279        assert!(matches!(
    280            d.replace_range(4..7, b"lol2").unwrap_err(),
    281            Error::AlreadyReplaced {
    282                is_identical: false,
    283                ..
    284            },
    285        ));
    286    }
    287
    288    #[test]
    289    fn replace_same_range_same_data() {
    290        let mut d = Data::new(b"foo bar baz");
    291
    292        d.replace_range(4..7, b"lol").unwrap();
    293        assert_eq!("foo lol baz", str(&d.to_vec()));
    294
    295        assert!(matches!(
    296            d.replace_range(4..7, b"lol").unwrap_err(),
    297            Error::AlreadyReplaced {
    298                is_identical: true,
    299                ..
    300            },
    301        ));
    302    }
    303
    304    #[test]
    305    fn broken_replacements() {
    306        let mut d = Data::new(b"foo");
    307        assert!(matches!(
    308            d.replace_range(4..8, b"lol").unwrap_err(),
    309            Error::DataLengthExceeded(std::ops::Range { start: 4, end: 8 }, 3),
    310        ));
    311    }
    312
    313    #[test]
    314    fn insert_same_twice() {
    315        let mut d = Data::new(b"foo");
    316        d.replace_range(1..1, b"b").unwrap();
    317        assert_eq!("fboo", str(&d.to_vec()));
    318        assert!(matches!(
    319            d.replace_range(1..1, b"b").unwrap_err(),
    320            Error::AlreadyReplaced {
    321                is_identical: true,
    322                ..
    323            },
    324        ));
    325        assert_eq!("fboo", str(&d.to_vec()));
    326    }
    327
    328    #[test]
    329    fn commit_restore() {
    330        let mut d = Data::new(b", ");
    331        assert_eq!(", ", str(&d.to_vec()));
    332
    333        d.replace_range(2..2, b"world").unwrap();
    334        d.replace_range(0..0, b"hello").unwrap();
    335        assert_eq!("hello, world", str(&d.to_vec()));
    336
    337        d.restore();
    338        assert_eq!(", ", str(&d.to_vec()));
    339
    340        d.commit();
    341        assert_eq!(", ", str(&d.to_vec()));
    342
    343        d.replace_range(2..2, b"world").unwrap();
    344        assert_eq!(", world", str(&d.to_vec()));
    345        d.commit();
    346        assert_eq!(", world", str(&d.to_vec()));
    347        d.restore();
    348        assert_eq!(", world", str(&d.to_vec()));
    349
    350        d.replace_range(0..0, b"hello").unwrap();
    351        assert_eq!("hello, world", str(&d.to_vec()));
    352        d.commit();
    353        assert_eq!("hello, world", str(&d.to_vec()));
    354        d.restore();
    355        assert_eq!("hello, world", str(&d.to_vec()));
    356    }
    357
    358    proptest! {
    359        #[test]
    360        fn new_to_vec_roundtrip(ref s in "\\PC*") {
    361            assert_eq!(s.as_bytes(), Data::new(s.as_bytes()).to_vec().as_slice());
    362        }
    363
    364        #[test]
    365        fn replace_random_chunks(
    366            ref data in "\\PC*",
    367            ref replacements in prop::collection::vec(
    368                (any::<::std::ops::Range<usize>>(), any::<Vec<u8>>()),
    369                1..100,
    370            )
    371        ) {
    372            let mut d = Data::new(data.as_bytes());
    373            for &(ref range, ref bytes) in replacements {
    374                let _ = d.replace_range(range.clone(), bytes);
    375            }
    376        }
    377    }
    378}