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 use std::{cmp, iter, str};
  13
  14 use itertools::Itertools;
  15 use multimap::MultiMap;
  16 use rustc_serialize::{self, json};
  17
  18 use codemap::LineRange;
  19
  20 /// A range that is inclusive of both ends.
  21 #[derive(Clone, Copy, Debug, Eq, PartialEq, RustcDecodable)]
  22 struct Range {
  23     pub lo: usize,
  24     pub hi: usize,
  25 }
  26
  27 impl<'a> From<&'a LineRange> for Range {
  28     fn from(range: &'a LineRange) -> Range {
  29         Range::new(range.lo, range.hi)
  30     }
  31 }
  32
  33 impl Range {
  34     fn new(lo: usize, hi: usize) -> Range {
  35         Range { lo: lo, hi: hi }
  36     }
  37
  38     fn is_empty(self) -> bool {
  39         self.lo > self.hi
  40     }
  41
  42     fn contains(self, other: Range) -> bool {
  43         if other.is_empty() {
  44             true
  45         } else {
  46             !self.is_empty() && self.lo <= other.lo && self.hi >= other.hi
  47         }
  48     }
  49
  50     fn intersects(self, other: Range) -> bool {
  51         if self.is_empty() || other.is_empty() {
  52             false
  53         } else {
  54             (self.lo <= other.hi && other.hi <= self.hi) ||
  55             (other.lo <= self.hi && self.hi <= other.hi)
  56         }
  57     }
  58
  59     fn adjacent_to(self, other: Range) -> bool {
  60         if self.is_empty() || other.is_empty() {
  61             false
  62         } else {
  63             self.hi + 1 == other.lo || other.hi + 1 == self.lo
  64         }
  65     }
  66
  67     /// Returns a new `Range` with lines from `self` and `other` if they were adjacent or
  68     /// intersect; returns `None` otherwise.
  69     fn merge(self, other: Range) -> Option<Range> {
  70         if self.adjacent_to(other) || self.intersects(other) {
  71             Some(Range::new(cmp::min(self.lo, other.lo), cmp::max(self.hi, other.hi)))
  72         } else {
  73             None
  74         }
  75     }
  76 }
  77
  78 /// A set of lines in files.
  79 ///
  80 /// It is represented as a multimap keyed on file names, with values a collection of
  81 /// non-overlapping ranges sorted by their start point. An inner `None` is interpreted to mean all
  82 /// lines in all files.
  83 #[derive(Clone, Debug, Default)]
  84 pub struct FileLines(Option<MultiMap<String, Range>>);
  85
  86 /// Normalizes the ranges so that the invariants for `FileLines` hold: ranges are non-overlapping,
  87 /// and ordered by their start point.
  88 fn normalize_ranges(map: &mut MultiMap<String, Range>) {
  89     for (_, ranges) in map.iter_all_mut() {
  90         ranges.sort_by_key(|x| x.lo);
  91         let merged = ranges.drain(..).coalesce(|x, y| x.merge(y).ok_or((x, y))).collect();
  92         *ranges = merged;
  93     }
  94 }
  95
  96 impl FileLines {
  97     /// Creates a `FileLines` that contains all lines in all files.
  98     pub fn all() -> FileLines {
  99         FileLines(None)
 100     }
 101
 102     /// Creates a `FileLines` from a `MultiMap`, ensuring that the invariants hold.
 103     fn from_multimap(map: MultiMap<String, Range>) -> FileLines {
 104         let mut map = map;
 105         normalize_ranges(&mut map);
 106         FileLines(Some(map))
 107     }
 108
 109     /// Returns an iterator over the files contained in `self`.
 110     pub fn files(&self) -> Files {
 111         Files(self.0.as_ref().map(MultiMap::keys))
 112     }
 113
 114     /// Returns true if `range` is fully contained in `self`.
 115     pub fn contains(&self, range: &LineRange) -> bool {
 116         let map = match self.0 {
 117             // `None` means "all lines in all files".
 118             None => return true,
 119             Some(ref map) => map,
 120         };
 121
 122         match map.get_vec(range.file_name()) {
 123             None => false,
 124             Some(ranges) => ranges.iter().any(|r| r.contains(Range::from(range))),
 125         }
 126     }
 127
 128     /// Returns true if any lines in `range` are in `self`.
 129     pub fn intersects(&self, range: &LineRange) -> bool {
 130         let map = match self.0 {
 131             // `None` means "all lines in all files".
 132             None => return true,
 133             Some(ref map) => map,
 134         };
 135
 136         match map.get_vec(range.file_name()) {
 137             None => false,
 138             Some(ranges) => ranges.iter().any(|r| r.intersects(Range::from(range))),
 139         }
 140     }
 141 }
 142
 143 /// FileLines files iterator.
 144 pub struct Files<'a>(Option<::std::collections::hash_map::Keys<'a, String, Vec<Range>>>);
 145
 146 impl<'a> iter::Iterator for Files<'a> {
 147     type Item = &'a String;
 148
 149     fn next(&mut self) -> Option<&'a String> {
 150         self.0.as_mut().and_then(Iterator::next)
 151     }
 152 }
 153
 154 // This impl is needed for `Config::override_value` to work for use in tests.
 155 impl str::FromStr for FileLines {
 156     type Err = String;
 157
 158     fn from_str(s: &str) -> Result<FileLines, String> {
 159         let v: Vec<JsonSpan> = try!(json::decode(s).map_err(|e| e.to_string()));
 160         let m = v.into_iter().map(JsonSpan::into_tuple).collect();
 161         Ok(FileLines::from_multimap(m))
 162     }
 163 }
 164
 165 // For JSON decoding.
 166 #[derive(Clone, Debug, RustcDecodable)]
 167 struct JsonSpan {
 168     file: String,
 169     range: (usize, usize),
 170 }
 171
 172 impl JsonSpan {
 173     // To allow `collect()`ing into a `MultiMap`.
 174     fn into_tuple(self) -> (String, Range) {
 175         let (lo, hi) = self.range;
 176         (self.file, Range::new(lo, hi))
 177     }
 178 }
 179
 180 // This impl is needed for inclusion in the `Config` struct. We don't have a toml representation
 181 // for `FileLines`, so it will just panic instead.
 182 impl rustc_serialize::Decodable for FileLines {
 183     fn decode<D: rustc_serialize::Decoder>(_: &mut D) -> Result<Self, D::Error> {
 184         panic!("FileLines cannot be deserialized from a project rustfmt.toml file: please \
 185                 specify it via the `--file-lines` option instead");
 186     }
 187 }
 188
 189 #[cfg(test)]
 190 mod test {
 191     use super::Range;
 192
 193     #[test]
 194     fn test_range_intersects() {
 195         assert!(Range::new(1, 2).intersects(Range::new(1, 1)));
 196         assert!(Range::new(1, 2).intersects(Range::new(2, 2)));
 197         assert!(!Range::new(1, 2).intersects(Range::new(0, 0)));
 198         assert!(!Range::new(1, 2).intersects(Range::new(3, 10)));
 199         assert!(!Range::new(1, 3).intersects(Range::new(5, 5)));
 200     }
 201
 202     #[test]
 203     fn test_range_adjacent_to() {
 204         assert!(!Range::new(1, 2).adjacent_to(Range::new(1, 1)));
 205         assert!(!Range::new(1, 2).adjacent_to(Range::new(2, 2)));
 206         assert!(Range::new(1, 2).adjacent_to(Range::new(0, 0)));
 207         assert!(Range::new(1, 2).adjacent_to(Range::new(3, 10)));
 208         assert!(!Range::new(1, 3).adjacent_to(Range::new(5, 5)));
 209     }
 210
 211     #[test]
 212     fn test_range_contains() {
 213         assert!(Range::new(1, 2).contains(Range::new(1, 1)));
 214         assert!(Range::new(1, 2).contains(Range::new(2, 2)));
 215         assert!(!Range::new(1, 2).contains(Range::new(0, 0)));
 216         assert!(!Range::new(1, 2).contains(Range::new(3, 10)));
 217     }
 218
 219     #[test]
 220     fn test_range_merge() {
 221         assert_eq!(None, Range::new(1, 3).merge(Range::new(5, 5)));
 222         assert_eq!(None, Range::new(4, 7).merge(Range::new(0, 1)));
 223         assert_eq!(Some(Range::new(3, 7)),
 224                    Range::new(3, 5).merge(Range::new(4, 7)));
 225         assert_eq!(Some(Range::new(3, 7)),
 226                    Range::new(3, 5).merge(Range::new(5, 7)));
 227         assert_eq!(Some(Range::new(3, 7)),
 228                    Range::new(3, 5).merge(Range::new(6, 7)));
 229         assert_eq!(Some(Range::new(3, 7)),
 230                    Range::new(3, 7).merge(Range::new(4, 5)));
 231     }
 232 }