vendor/rustfix-0.5.1/src/replace.rs

   1 //! A small module giving you a simple container that allows easy and cheap
   2 //! replacement of parts of its content, with the ability to prevent changing
   3 //! the same parts multiple times.
   4
   5 use anyhow::{anyhow, ensure, Error};
   6 use std::rc::Rc;
   7
   8 #[derive(Debug, Clone, PartialEq, Eq)]
   9 enum State {
  10     Initial,
  11     Replaced(Rc<[u8]>),
  12     Inserted(Rc<[u8]>),
  13 }
  14
  15 impl State {
  16     fn is_inserted(&self) -> bool {
  17         if let State::Inserted(..) = *self {
  18             true
  19         } else {
  20             false
  21         }
  22     }
  23 }
  24
  25 #[derive(Debug, Clone, PartialEq, Eq)]
  26 struct Span {
  27     /// Start of this span in parent data
  28     start: usize,
  29     /// up to end including
  30     end: usize,
  31     data: State,
  32 }
  33
  34 /// A container that allows easily replacing chunks of its data
  35 #[derive(Debug, Clone, Default)]
  36 pub struct Data {
  37     original: Vec<u8>,
  38     parts: Vec<Span>,
  39 }
  40
  41 impl Data {
  42     /// Create a new data container from a slice of bytes
  43     pub fn new(data: &[u8]) -> Self {
  44         Data {
  45             original: data.into(),
  46             parts: vec![Span {
  47                 data: State::Initial,
  48                 start: 0,
  49                 end: data.len().saturating_sub(1),
  50             }],
  51         }
  52     }
  53
  54     /// Render this data as a vector of bytes
  55     pub fn to_vec(&self) -> Vec<u8> {
  56         if self.original.is_empty() {
  57             return Vec::new();
  58         }
  59
  60         self.parts.iter().fold(Vec::new(), |mut acc, d| {
  61             match d.data {
  62                 State::Initial => acc.extend_from_slice(&self.original[d.start..=d.end]),
  63                 State::Replaced(ref d) | State::Inserted(ref d) => acc.extend_from_slice(&d),
  64             };
  65             acc
  66         })
  67     }
  68
  69     /// Replace a chunk of data with the given slice, erroring when this part
  70     /// was already changed previously.
  71     pub fn replace_range(
  72         &mut self,
  73         from: usize,
  74         up_to_and_including: usize,
  75         data: &[u8],
  76     ) -> Result<(), Error> {
  77         let exclusive_end = up_to_and_including + 1;
  78
  79         ensure!(
  80             from <= exclusive_end,
  81             "Invalid range {}...{}, start is larger than end",
  82             from,
  83             up_to_and_including
  84         );
  85
  86         ensure!(
  87             up_to_and_including <= self.original.len(),
  88             "Invalid range {}...{} given, original data is only {} byte long",
  89             from,
  90             up_to_and_including,
  91             self.original.len()
  92         );
  93
  94         let insert_only = from == exclusive_end;
  95
  96         // Since we error out when replacing an already replaced chunk of data,
  97         // we can take some shortcuts here. For example, there can be no
  98         // overlapping replacements -- we _always_ split a chunk of 'initial'
  99         // data into three[^empty] parts, and there can't ever be two 'initial'
 100         // parts touching.
 101         //
 102         // [^empty]: Leading and trailing ones might be empty if we replace
 103         // the whole chunk. As an optimization and without loss of generality we
 104         // don't add empty parts.
 105         let new_parts = {
 106             let index_of_part_to_split = self
 107                 .parts
 108                 .iter()
 109                 .position(|p| {
 110                     !p.data.is_inserted() && p.start <= from && p.end >= up_to_and_including
 111                 })
 112                 .ok_or_else(|| {
 113                     use log::Level::Debug;
 114                     if log_enabled!(Debug) {
 115                         let slices = self
 116                             .parts
 117                             .iter()
 118                             .map(|p| {
 119                                 (
 120                                     p.start,
 121                                     p.end,
 122                                     match p.data {
 123                                         State::Initial => "initial",
 124                                         State::Replaced(..) => "replaced",
 125                                         State::Inserted(..) => "inserted",
 126                                     },
 127                                 )
 128                             })
 129                             .collect::<Vec<_>>();
 130                         debug!(
 131                             "no single slice covering {}...{}, current slices: {:?}",
 132                             from, up_to_and_including, slices,
 133                         );
 134                     }
 135
 136                     anyhow!(
 137                         "Could not replace range {}...{} in file \
 138                          -- maybe parts of it were already replaced?",
 139                         from,
 140                         up_to_and_including
 141                     )
 142                 })?;
 143
 144             let part_to_split = &self.parts[index_of_part_to_split];
 145
 146             // If this replacement matches exactly the part that we would
 147             // otherwise split then we ignore this for now. This means that you
 148             // can replace the exact same range with the exact same content
 149             // multiple times and we'll process and allow it.
 150             //
 151             // This is currently done to alleviate issues like
 152             // rust-lang/rust#51211 although this clause likely wants to be
 153             // removed if that's fixed deeper in the compiler.
 154             if part_to_split.start == from && part_to_split.end == up_to_and_including {
 155                 if let State::Replaced(ref replacement) = part_to_split.data {
 156                     if &**replacement == data {
 157                         return Ok(());
 158                     }
 159                 }
 160             }
 161
 162             ensure!(
 163                 part_to_split.data == State::Initial,
 164                 "Cannot replace slice of data that was already replaced"
 165             );
 166
 167             let mut new_parts = Vec::with_capacity(self.parts.len() + 2);
 168
 169             // Previous parts
 170             if let Some(ps) = self.parts.get(..index_of_part_to_split) {
 171                 new_parts.extend_from_slice(&ps);
 172             }
 173
 174             // Keep initial data on left side of part
 175             if from > part_to_split.start {
 176                 new_parts.push(Span {
 177                     start: part_to_split.start,
 178                     end: from.saturating_sub(1),
 179                     data: State::Initial,
 180                 });
 181             }
 182
 183             // New part
 184             new_parts.push(Span {
 185                 start: from,
 186                 end: up_to_and_including,
 187                 data: if insert_only {
 188                     State::Inserted(data.into())
 189                 } else {
 190                     State::Replaced(data.into())
 191                 },
 192             });
 193
 194             // Keep initial data on right side of part
 195             if up_to_and_including < part_to_split.end {
 196                 new_parts.push(Span {
 197                     start: up_to_and_including + 1,
 198                     end: part_to_split.end,
 199                     data: State::Initial,
 200                 });
 201             }
 202
 203             // Following parts
 204             if let Some(ps) = self.parts.get(index_of_part_to_split + 1..) {
 205                 new_parts.extend_from_slice(&ps);
 206             }
 207
 208             new_parts
 209         };
 210
 211         self.parts = new_parts;
 212
 213         Ok(())
 214     }
 215 }
 216
 217 #[cfg(test)]
 218 mod tests {
 219     use super::*;
 220     use proptest::prelude::*;
 221
 222     fn str(i: &[u8]) -> &str {
 223         ::std::str::from_utf8(i).unwrap()
 224     }
 225
 226     #[test]
 227     fn replace_some_stuff() {
 228         let mut d = Data::new(b"foo bar baz");
 229         d.replace_range(4, 6, b"lol").unwrap();
 230         assert_eq!("foo lol baz", str(&d.to_vec()));
 231     }
 232
 233     #[test]
 234     fn replace_a_single_char() {
 235         let mut d = Data::new(b"let y = true;");
 236         d.replace_range(4, 4, b"mut y").unwrap();
 237         assert_eq!("let mut y = true;", str(&d.to_vec()));
 238     }
 239
 240     #[test]
 241     fn replace_multiple_lines() {
 242         let mut d = Data::new(b"lorem\nipsum\ndolor");
 243
 244         d.replace_range(6, 10, b"lol").unwrap();
 245         assert_eq!("lorem\nlol\ndolor", str(&d.to_vec()));
 246
 247         d.replace_range(12, 16, b"lol").unwrap();
 248         assert_eq!("lorem\nlol\nlol", str(&d.to_vec()));
 249     }
 250
 251     #[test]
 252     fn replace_multiple_lines_with_insert_only() {
 253         let mut d = Data::new(b"foo!");
 254
 255         d.replace_range(3, 2, b"bar").unwrap();
 256         assert_eq!("foobar!", str(&d.to_vec()));
 257
 258         d.replace_range(0, 2, b"baz").unwrap();
 259         assert_eq!("bazbar!", str(&d.to_vec()));
 260
 261         d.replace_range(3, 3, b"?").unwrap();
 262         assert_eq!("bazbar?", str(&d.to_vec()));
 263     }
 264
 265     #[test]
 266     fn replace_invalid_range() {
 267         let mut d = Data::new(b"foo!");
 268
 269         assert!(d.replace_range(2, 0, b"bar").is_err());
 270         assert!(d.replace_range(0, 2, b"bar").is_ok());
 271     }
 272
 273     #[test]
 274     fn empty_to_vec_roundtrip() {
 275         let s = "";
 276         assert_eq!(s.as_bytes(), Data::new(s.as_bytes()).to_vec().as_slice());
 277     }
 278
 279     #[test]
 280     #[should_panic(expected = "Cannot replace slice of data that was already replaced")]
 281     fn replace_overlapping_stuff_errs() {
 282         let mut d = Data::new(b"foo bar baz");
 283
 284         d.replace_range(4, 6, b"lol").unwrap();
 285         assert_eq!("foo lol baz", str(&d.to_vec()));
 286
 287         d.replace_range(4, 6, b"lol2").unwrap();
 288     }
 289
 290     #[test]
 291     #[should_panic(expected = "original data is only 3 byte long")]
 292     fn broken_replacements() {
 293         let mut d = Data::new(b"foo");
 294         d.replace_range(4, 7, b"lol").unwrap();
 295     }
 296
 297     #[test]
 298     fn replace_same_twice() {
 299         let mut d = Data::new(b"foo");
 300         d.replace_range(0, 0, b"b").unwrap();
 301         d.replace_range(0, 0, b"b").unwrap();
 302         assert_eq!("boo", str(&d.to_vec()));
 303     }
 304
 305     proptest! {
 306         #[test]
 307         #[ignore]
 308         fn new_to_vec_roundtrip(ref s in "\\PC*") {
 309             assert_eq!(s.as_bytes(), Data::new(s.as_bytes()).to_vec().as_slice());
 310         }
 311
 312         #[test]
 313         #[ignore]
 314         fn replace_random_chunks(
 315             ref data in "\\PC*",
 316             ref replacements in prop::collection::vec(
 317                 (any::<::std::ops::Range<usize>>(), any::<Vec<u8>>()),
 318                 1..1337,
 319             )
 320         ) {
 321             let mut d = Data::new(data.as_bytes());
 322             for &(ref range, ref bytes) in replacements {
 323                 let _ = d.replace_range(range.start, range.end, bytes);
 324             }
 325         }
 326     }
 327 }