src/file_lines.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! This module contains types and functions to support formatting specific line ranges.
  12
  13 use std::{cmp, iter, path, str};
  14
  15 use itertools::Itertools;
  16 use multimap::MultiMap;
  17 use serde_json as json;
  18
  19 use codemap::LineRange;
  20
  21 /// A range that is inclusive of both ends.
  22 #[derive(Clone, Copy, Debug, Eq, PartialEq, Deserialize)]
  23 struct Range {
  24     pub lo: usize,
  25     pub hi: usize,
  26 }
  27
  28 impl<'a> From<&'a LineRange> for Range {
  29     fn from(range: &'a LineRange) -> Range {
  30         Range::new(range.lo, range.hi)
  31     }
  32 }
  33
  34 impl Range {
  35     fn new(lo: usize, hi: usize) -> Range {
  36         Range { lo: lo, hi: hi }
  37     }
  38
  39     fn is_empty(self) -> bool {
  40         self.lo > self.hi
  41     }
  42
  43     fn contains(self, other: Range) -> bool {
  44         if other.is_empty() {
  45             true
  46         } else {
  47             !self.is_empty() && self.lo <= other.lo && self.hi >= other.hi
  48         }
  49     }
  50
  51     fn intersects(self, other: Range) -> bool {
  52         if self.is_empty() || other.is_empty() {
  53             false
  54         } else {
  55             (self.lo <= other.hi && other.hi <= self.hi) ||
  56             (other.lo <= self.hi && self.hi <= other.hi)
  57         }
  58     }
  59
  60     fn adjacent_to(self, other: Range) -> bool {
  61         if self.is_empty() || other.is_empty() {
  62             false
  63         } else {
  64             self.hi + 1 == other.lo || other.hi + 1 == self.lo
  65         }
  66     }
  67
  68     /// Returns a new `Range` with lines from `self` and `other` if they were adjacent or
  69     /// intersect; returns `None` otherwise.
  70     fn merge(self, other: Range) -> Option<Range> {
  71         if self.adjacent_to(other) || self.intersects(other) {
  72             Some(Range::new(cmp::min(self.lo, other.lo), cmp::max(self.hi, other.hi)))
  73         } else {
  74             None
  75         }
  76     }
  77 }
  78
  79 /// A set of lines in files.
  80 ///
  81 /// It is represented as a multimap keyed on file names, with values a collection of
  82 /// non-overlapping ranges sorted by their start point. An inner `None` is interpreted to mean all
  83 /// lines in all files.
  84 #[derive(Clone, Debug, Default)]
  85 pub struct FileLines(Option<MultiMap<String, Range>>);
  86
  87 /// Normalizes the ranges so that the invariants for `FileLines` hold: ranges are non-overlapping,
  88 /// and ordered by their start point.
  89 fn normalize_ranges(map: &mut MultiMap<String, Range>) {
  90     for (_, ranges) in map.iter_all_mut() {
  91         ranges.sort_by_key(|x| x.lo);
  92         let merged = ranges
  93             .drain(..)
  94             .coalesce(|x, y| x.merge(y).ok_or((x, y)))
  95             .collect();
  96         *ranges = merged;
  97     }
  98 }
  99
 100 impl FileLines {
 101     /// Creates a `FileLines` that contains all lines in all files.
 102     pub fn all() -> FileLines {
 103         FileLines(None)
 104     }
 105
 106     /// Creates a `FileLines` from a `MultiMap`, ensuring that the invariants hold.
 107     fn from_multimap(map: MultiMap<String, Range>) -> FileLines {
 108         let mut map = map;
 109         normalize_ranges(&mut map);
 110         FileLines(Some(map))
 111     }
 112
 113     /// Returns an iterator over the files contained in `self`.
 114     pub fn files(&self) -> Files {
 115         Files(self.0.as_ref().map(MultiMap::keys))
 116     }
 117
 118     /// Returns true if `self` includes all lines in all files. Otherwise runs `f` on all ranges in
 119     /// the designated file (if any) and returns true if `f` ever does.
 120     fn file_range_matches<F>(&self, file_name: &str, f: F) -> bool
 121         where F: FnMut(&Range) -> bool
 122     {
 123         let map = match self.0 {
 124             // `None` means "all lines in all files".
 125             None => return true,
 126             Some(ref map) => map,
 127         };
 128
 129         match canonicalize_path_string(file_name).and_then(|file| map.get_vec(&file).ok_or(())) {
 130             Ok(ranges) => ranges.iter().any(f),
 131             Err(_) => false,
 132         }
 133     }
 134
 135     /// Returns true if `range` is fully contained in `self`.
 136     pub fn contains(&self, range: &LineRange) -> bool {
 137         self.file_range_matches(range.file_name(), |r| r.contains(Range::from(range)))
 138     }
 139
 140     /// Returns true if any lines in `range` are in `self`.
 141     pub fn intersects(&self, range: &LineRange) -> bool {
 142         self.file_range_matches(range.file_name(), |r| r.intersects(Range::from(range)))
 143     }
 144
 145     /// Returns true if `line` from `file_name` is in `self`.
 146     pub fn contains_line(&self, file_name: &str, line: usize) -> bool {
 147         self.file_range_matches(file_name, |r| r.lo <= line && r.hi >= line)
 148     }
 149
 150     /// Returns true if any of the lines between `lo` and `hi` from `file_name` are in `self`.
 151     pub fn intersects_range(&self, file_name: &str, lo: usize, hi: usize) -> bool {
 152         self.file_range_matches(file_name, |r| r.intersects(Range::new(lo, hi)))
 153     }
 154 }
 155
 156 /// FileLines files iterator.
 157 pub struct Files<'a>(Option<::std::collections::hash_map::Keys<'a, String, Vec<Range>>>);
 158
 159 impl<'a> iter::Iterator for Files<'a> {
 160     type Item = &'a String;
 161
 162     fn next(&mut self) -> Option<&'a String> {
 163         self.0.as_mut().and_then(Iterator::next)
 164     }
 165 }
 166
 167 fn canonicalize_path_string(s: &str) -> Result<String, ()> {
 168     if s == "stdin" {
 169         return Ok(s.to_string());
 170     }
 171
 172     match path::PathBuf::from(s).canonicalize() {
 173         Ok(canonicalized) => canonicalized.to_str().map(|s| s.to_string()).ok_or(()),
 174         _ => Err(()),
 175     }
 176 }
 177
 178 // This impl is needed for `Config::override_value` to work for use in tests.
 179 impl str::FromStr for FileLines {
 180     type Err = String;
 181
 182     fn from_str(s: &str) -> Result<FileLines, String> {
 183         let v: Vec<JsonSpan> = json::from_str(s).map_err(|e| e.to_string())?;
 184         let m = v.into_iter()
 185             .map(JsonSpan::into_tuple)
 186             .collect::<Result<_, _>>()?;
 187         Ok(FileLines::from_multimap(m))
 188     }
 189 }
 190
 191 // For JSON decoding.
 192 #[derive(Clone, Debug, Deserialize)]
 193 struct JsonSpan {
 194     file: String,
 195     range: (usize, usize),
 196 }
 197
 198 impl JsonSpan {
 199     // To allow `collect()`ing into a `MultiMap`.
 200     fn into_tuple(self) -> Result<(String, Range), String> {
 201         let (lo, hi) = self.range;
 202         let canonical = canonicalize_path_string(&self.file)
 203             .map_err(|_| format!("Can't canonicalize {}", &self.file))?;
 204         Ok((canonical, Range::new(lo, hi)))
 205     }
 206 }
 207
 208 // This impl is needed for inclusion in the `Config` struct. We don't have a toml representation
 209 // for `FileLines`, so it will just panic instead.
 210 impl<'de> ::serde::de::Deserialize<'de> for FileLines {
 211     fn deserialize<D>(_: D) -> Result<Self, D::Error>
 212         where D: ::serde::de::Deserializer<'de>
 213     {
 214         panic!("FileLines cannot be deserialized from a project rustfmt.toml file: please \
 215                 specify it via the `--file-lines` option instead");
 216     }
 217 }
 218
 219 #[cfg(test)]
 220 mod test {
 221     use super::Range;
 222
 223     #[test]
 224     fn test_range_intersects() {
 225         assert!(Range::new(1, 2).intersects(Range::new(1, 1)));
 226         assert!(Range::new(1, 2).intersects(Range::new(2, 2)));
 227         assert!(!Range::new(1, 2).intersects(Range::new(0, 0)));
 228         assert!(!Range::new(1, 2).intersects(Range::new(3, 10)));
 229         assert!(!Range::new(1, 3).intersects(Range::new(5, 5)));
 230     }
 231
 232     #[test]
 233     fn test_range_adjacent_to() {
 234         assert!(!Range::new(1, 2).adjacent_to(Range::new(1, 1)));
 235         assert!(!Range::new(1, 2).adjacent_to(Range::new(2, 2)));
 236         assert!(Range::new(1, 2).adjacent_to(Range::new(0, 0)));
 237         assert!(Range::new(1, 2).adjacent_to(Range::new(3, 10)));
 238         assert!(!Range::new(1, 3).adjacent_to(Range::new(5, 5)));
 239     }
 240
 241     #[test]
 242     fn test_range_contains() {
 243         assert!(Range::new(1, 2).contains(Range::new(1, 1)));
 244         assert!(Range::new(1, 2).contains(Range::new(2, 2)));
 245         assert!(!Range::new(1, 2).contains(Range::new(0, 0)));
 246         assert!(!Range::new(1, 2).contains(Range::new(3, 10)));
 247     }
 248
 249     #[test]
 250     fn test_range_merge() {
 251         assert_eq!(None, Range::new(1, 3).merge(Range::new(5, 5)));
 252         assert_eq!(None, Range::new(4, 7).merge(Range::new(0, 1)));
 253         assert_eq!(Some(Range::new(3, 7)),
 254                    Range::new(3, 5).merge(Range::new(4, 7)));
 255         assert_eq!(Some(Range::new(3, 7)),
 256                    Range::new(3, 5).merge(Range::new(5, 7)));
 257         assert_eq!(Some(Range::new(3, 7)),
 258                    Range::new(3, 5).merge(Range::new(6, 7)));
 259         assert_eq!(Some(Range::new(3, 7)),
 260                    Range::new(3, 7).merge(Range::new(4, 5)));
 261     }
 262 }