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 rustc_serialize::{self, json};
  18
  19 use codemap::LineRange;
  20
  21 /// A range that is inclusive of both ends.
  22 #[derive(Clone, Copy, Debug, Eq, PartialEq, RustcDecodable)]
  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.drain(..).coalesce(|x, y| x.merge(y).ok_or((x, y))).collect();
  93         *ranges = merged;
  94     }
  95 }
  96
  97 impl FileLines {
  98     /// Creates a `FileLines` that contains all lines in all files.
  99     pub fn all() -> FileLines {
 100         FileLines(None)
 101     }
 102
 103     /// Creates a `FileLines` from a `MultiMap`, ensuring that the invariants hold.
 104     fn from_multimap(map: MultiMap<String, Range>) -> FileLines {
 105         let mut map = map;
 106         normalize_ranges(&mut map);
 107         FileLines(Some(map))
 108     }
 109
 110     /// Returns an iterator over the files contained in `self`.
 111     pub fn files(&self) -> Files {
 112         Files(self.0.as_ref().map(MultiMap::keys))
 113     }
 114
 115     /// Returns true if `range` is fully contained in `self`.
 116     pub fn contains(&self, range: &LineRange) -> bool {
 117         let map = match self.0 {
 118             // `None` means "all lines in all files".
 119             None => return true,
 120             Some(ref map) => map,
 121         };
 122
 123         match canonicalize_path_string(range.file_name()).and_then(|canonical| {
 124                                                                        map.get_vec(&canonical)
 125                                                                            .ok_or(())
 126                                                                    }) {
 127             Ok(ranges) => ranges.iter().any(|r| r.contains(Range::from(range))),
 128             Err(_) => false,
 129         }
 130     }
 131
 132     /// Returns true if any lines in `range` are in `self`.
 133     pub fn intersects(&self, range: &LineRange) -> bool {
 134         let map = match self.0 {
 135             // `None` means "all lines in all files".
 136             None => return true,
 137             Some(ref map) => map,
 138         };
 139
 140         match map.get_vec(range.file_name()) {
 141             None => false,
 142             Some(ranges) => ranges.iter().any(|r| r.intersects(Range::from(range))),
 143         }
 144     }
 145 }
 146
 147 /// FileLines files iterator.
 148 pub struct Files<'a>(Option<::std::collections::hash_map::Keys<'a, String, Vec<Range>>>);
 149
 150 impl<'a> iter::Iterator for Files<'a> {
 151     type Item = &'a String;
 152
 153     fn next(&mut self) -> Option<&'a String> {
 154         self.0.as_mut().and_then(Iterator::next)
 155     }
 156 }
 157
 158 fn canonicalize_path_string(s: &str) -> Result<String, ()> {
 159     match path::PathBuf::from(s).canonicalize() {
 160         Ok(canonicalized) => canonicalized.to_str().map(|s| s.to_string()).ok_or(()),
 161         _ => Err(()),
 162     }
 163 }
 164
 165 // This impl is needed for `Config::override_value` to work for use in tests.
 166 impl str::FromStr for FileLines {
 167     type Err = String;
 168
 169     fn from_str(s: &str) -> Result<FileLines, String> {
 170         let v: Vec<JsonSpan> = try!(json::decode(s).map_err(|e| e.to_string()));
 171         let m = try!(v.into_iter().map(JsonSpan::into_tuple).collect());
 172         Ok(FileLines::from_multimap(m))
 173     }
 174 }
 175
 176 // For JSON decoding.
 177 #[derive(Clone, Debug, RustcDecodable)]
 178 struct JsonSpan {
 179     file: String,
 180     range: (usize, usize),
 181 }
 182
 183 impl JsonSpan {
 184     // To allow `collect()`ing into a `MultiMap`.
 185     fn into_tuple(self) -> Result<(String, Range), String> {
 186         let (lo, hi) = self.range;
 187         let canonical = try!(canonicalize_path_string(&self.file).map_err(|_| {
 188             format!("Can't canonicalize {}", &self.file)
 189         }));
 190         Ok((canonical, Range::new(lo, hi)))
 191     }
 192 }
 193
 194 // This impl is needed for inclusion in the `Config` struct. We don't have a toml representation
 195 // for `FileLines`, so it will just panic instead.
 196 impl rustc_serialize::Decodable for FileLines {
 197     fn decode<D: rustc_serialize::Decoder>(_: &mut D) -> Result<Self, D::Error> {
 198         panic!("FileLines cannot be deserialized from a project rustfmt.toml file: please \
 199                 specify it via the `--file-lines` option instead");
 200     }
 201 }
 202
 203 #[cfg(test)]
 204 mod test {
 205     use super::Range;
 206
 207     #[test]
 208     fn test_range_intersects() {
 209         assert!(Range::new(1, 2).intersects(Range::new(1, 1)));
 210         assert!(Range::new(1, 2).intersects(Range::new(2, 2)));
 211         assert!(!Range::new(1, 2).intersects(Range::new(0, 0)));
 212         assert!(!Range::new(1, 2).intersects(Range::new(3, 10)));
 213         assert!(!Range::new(1, 3).intersects(Range::new(5, 5)));
 214     }
 215
 216     #[test]
 217     fn test_range_adjacent_to() {
 218         assert!(!Range::new(1, 2).adjacent_to(Range::new(1, 1)));
 219         assert!(!Range::new(1, 2).adjacent_to(Range::new(2, 2)));
 220         assert!(Range::new(1, 2).adjacent_to(Range::new(0, 0)));
 221         assert!(Range::new(1, 2).adjacent_to(Range::new(3, 10)));
 222         assert!(!Range::new(1, 3).adjacent_to(Range::new(5, 5)));
 223     }
 224
 225     #[test]
 226     fn test_range_contains() {
 227         assert!(Range::new(1, 2).contains(Range::new(1, 1)));
 228         assert!(Range::new(1, 2).contains(Range::new(2, 2)));
 229         assert!(!Range::new(1, 2).contains(Range::new(0, 0)));
 230         assert!(!Range::new(1, 2).contains(Range::new(3, 10)));
 231     }
 232
 233     #[test]
 234     fn test_range_merge() {
 235         assert_eq!(None, Range::new(1, 3).merge(Range::new(5, 5)));
 236         assert_eq!(None, Range::new(4, 7).merge(Range::new(0, 1)));
 237         assert_eq!(Some(Range::new(3, 7)),
 238                    Range::new(3, 5).merge(Range::new(4, 7)));
 239         assert_eq!(Some(Range::new(3, 7)),
 240                    Range::new(3, 5).merge(Range::new(5, 7)));
 241         assert_eq!(Some(Range::new(3, 7)),
 242                    Range::new(3, 5).merge(Range::new(6, 7)));
 243         assert_eq!(Some(Range::new(3, 7)),
 244                    Range::new(3, 7).merge(Range::new(4, 5)));
 245     }
 246 }