1 /// Slot is a single saved capture location. Note that there are two slots for 2 /// every capture in a regular expression (one slot each for the start and end 3 /// of the capture). 4 pub type Slot = Option<usize>; 5 6 /// Locations represents the offsets of each capturing group in a regex for 7 /// a single match. 8 /// 9 /// Unlike `Captures`, a `Locations` value only stores offsets. 10 #[doc(hidden)] 11 #[derive(Clone, Debug)] 12 pub struct Locations(Vec<Slot>); 13 14 impl Locations { 15 /// Returns the start and end positions of the Nth capture group. Returns 16 /// `None` if `i` is not a valid capture group or if the capture group did 17 /// not match anything. The positions returned are *always* byte indices 18 /// with respect to the original string matched. pos(&self, i: usize) -> Option<(usize, usize)>19 pub fn pos(&self, i: usize) -> Option<(usize, usize)> { 20 let (s, e) = (i * 2, i * 2 + 1); 21 match (self.0.get(s), self.0.get(e)) { 22 (Some(&Some(s)), Some(&Some(e))) => Some((s, e)), 23 _ => None, 24 } 25 } 26 27 /// Creates an iterator of all the capture group positions in order of 28 /// appearance in the regular expression. Positions are byte indices 29 /// in terms of the original string matched. iter(&self) -> SubCapturesPosIter30 pub fn iter(&self) -> SubCapturesPosIter { 31 SubCapturesPosIter { idx: 0, locs: self } 32 } 33 34 /// Returns the total number of capturing groups. 35 /// 36 /// This is always at least `1` since every regex has at least `1` 37 /// capturing group that corresponds to the entire match. len(&self) -> usize38 pub fn len(&self) -> usize { 39 self.0.len() / 2 40 } 41 42 /// Return the individual slots as a slice. as_slots(&mut self) -> &mut [Slot]43 pub(crate) fn as_slots(&mut self) -> &mut [Slot] { 44 &mut self.0 45 } 46 } 47 48 /// An iterator over capture group positions for a particular match of a 49 /// regular expression. 50 /// 51 /// Positions are byte indices in terms of the original string matched. 52 /// 53 /// `'c` is the lifetime of the captures. 54 pub struct SubCapturesPosIter<'c> { 55 idx: usize, 56 locs: &'c Locations, 57 } 58 59 impl<'c> Iterator for SubCapturesPosIter<'c> { 60 type Item = Option<(usize, usize)>; 61 next(&mut self) -> Option<Option<(usize, usize)>>62 fn next(&mut self) -> Option<Option<(usize, usize)>> { 63 if self.idx >= self.locs.len() { 64 return None; 65 } 66 let x = match self.locs.pos(self.idx) { 67 None => Some(None), 68 Some((s, e)) => Some(Some((s, e))), 69 }; 70 self.idx += 1; 71 x 72 } 73 } 74 75 /// `RegularExpression` describes types that can implement regex searching. 76 /// 77 /// This trait is my attempt at reducing code duplication and to standardize 78 /// the internal API. Specific duplication that is avoided are the `find` 79 /// and `capture` iterators, which are slightly tricky. 80 /// 81 /// It's not clear whether this trait is worth it, and it also isn't 82 /// clear whether it's useful as a public trait or not. Methods like 83 /// `next_after_empty` reak of bad design, but the rest of the methods seem 84 /// somewhat reasonable. One particular thing this trait would expose would be 85 /// the ability to start the search of a regex anywhere in a haystack, which 86 /// isn't possible in the current public API. 87 pub trait RegularExpression: Sized { 88 /// The type of the haystack. 89 type Text: ?Sized; 90 91 /// The number of capture slots in the compiled regular expression. This is 92 /// always two times the number of capture groups (two slots per group). slots_len(&self) -> usize93 fn slots_len(&self) -> usize; 94 95 /// Allocates fresh space for all capturing groups in this regex. locations(&self) -> Locations96 fn locations(&self) -> Locations { 97 Locations(vec![None; self.slots_len()]) 98 } 99 100 /// Returns the position of the next character after `i`. 101 /// 102 /// For example, a haystack with type `&[u8]` probably returns `i+1`, 103 /// whereas a haystack with type `&str` probably returns `i` plus the 104 /// length of the next UTF-8 sequence. next_after_empty(&self, text: &Self::Text, i: usize) -> usize105 fn next_after_empty(&self, text: &Self::Text, i: usize) -> usize; 106 107 /// Returns the location of the shortest match. shortest_match_at( &self, text: &Self::Text, start: usize, ) -> Option<usize>108 fn shortest_match_at( 109 &self, 110 text: &Self::Text, 111 start: usize, 112 ) -> Option<usize>; 113 114 /// Returns whether the regex matches the text given. is_match_at(&self, text: &Self::Text, start: usize) -> bool115 fn is_match_at(&self, text: &Self::Text, start: usize) -> bool; 116 117 /// Returns the leftmost-first match location if one exists. find_at( &self, text: &Self::Text, start: usize, ) -> Option<(usize, usize)>118 fn find_at( 119 &self, 120 text: &Self::Text, 121 start: usize, 122 ) -> Option<(usize, usize)>; 123 124 /// Returns the leftmost-first match location if one exists, and also 125 /// fills in any matching capture slot locations. captures_read_at( &self, locs: &mut Locations, text: &Self::Text, start: usize, ) -> Option<(usize, usize)>126 fn captures_read_at( 127 &self, 128 locs: &mut Locations, 129 text: &Self::Text, 130 start: usize, 131 ) -> Option<(usize, usize)>; 132 133 /// Returns an iterator over all non-overlapping successive leftmost-first 134 /// matches. find_iter(self, text: &Self::Text) -> Matches<Self>135 fn find_iter(self, text: &Self::Text) -> Matches<Self> { 136 Matches { re: self, text: text, last_end: 0, last_match: None } 137 } 138 139 /// Returns an iterator over all non-overlapping successive leftmost-first 140 /// matches with captures. captures_iter(self, text: &Self::Text) -> CaptureMatches<Self>141 fn captures_iter(self, text: &Self::Text) -> CaptureMatches<Self> { 142 CaptureMatches(self.find_iter(text)) 143 } 144 } 145 146 /// An iterator over all non-overlapping successive leftmost-first matches. 147 pub struct Matches<'t, R> 148 where 149 R: RegularExpression, 150 R::Text: 't, 151 { 152 re: R, 153 text: &'t R::Text, 154 last_end: usize, 155 last_match: Option<usize>, 156 } 157 158 impl<'t, R> Matches<'t, R> 159 where 160 R: RegularExpression, 161 R::Text: 't, 162 { 163 /// Return the text being searched. text(&self) -> &'t R::Text164 pub fn text(&self) -> &'t R::Text { 165 self.text 166 } 167 168 /// Return the underlying regex. regex(&self) -> &R169 pub fn regex(&self) -> &R { 170 &self.re 171 } 172 } 173 174 impl<'t, R> Iterator for Matches<'t, R> 175 where 176 R: RegularExpression, 177 R::Text: 't + AsRef<[u8]>, 178 { 179 type Item = (usize, usize); 180 next(&mut self) -> Option<(usize, usize)>181 fn next(&mut self) -> Option<(usize, usize)> { 182 if self.last_end > self.text.as_ref().len() { 183 return None; 184 } 185 let (s, e) = match self.re.find_at(self.text, self.last_end) { 186 None => return None, 187 Some((s, e)) => (s, e), 188 }; 189 if s == e { 190 // This is an empty match. To ensure we make progress, start 191 // the next search at the smallest possible starting position 192 // of the next match following this one. 193 self.last_end = self.re.next_after_empty(self.text, e); 194 // Don't accept empty matches immediately following a match. 195 // Just move on to the next match. 196 if Some(e) == self.last_match { 197 return self.next(); 198 } 199 } else { 200 self.last_end = e; 201 } 202 self.last_match = Some(e); 203 Some((s, e)) 204 } 205 } 206 207 /// An iterator over all non-overlapping successive leftmost-first matches with 208 /// captures. 209 pub struct CaptureMatches<'t, R>(Matches<'t, R>) 210 where 211 R: RegularExpression, 212 R::Text: 't; 213 214 impl<'t, R> CaptureMatches<'t, R> 215 where 216 R: RegularExpression, 217 R::Text: 't, 218 { 219 /// Return the text being searched. text(&self) -> &'t R::Text220 pub fn text(&self) -> &'t R::Text { 221 self.0.text() 222 } 223 224 /// Return the underlying regex. regex(&self) -> &R225 pub fn regex(&self) -> &R { 226 self.0.regex() 227 } 228 } 229 230 impl<'t, R> Iterator for CaptureMatches<'t, R> 231 where 232 R: RegularExpression, 233 R::Text: 't + AsRef<[u8]>, 234 { 235 type Item = Locations; 236 next(&mut self) -> Option<Locations>237 fn next(&mut self) -> Option<Locations> { 238 if self.0.last_end > self.0.text.as_ref().len() { 239 return None; 240 } 241 let mut locs = self.0.re.locations(); 242 let (s, e) = match self.0.re.captures_read_at( 243 &mut locs, 244 self.0.text, 245 self.0.last_end, 246 ) { 247 None => return None, 248 Some((s, e)) => (s, e), 249 }; 250 if s == e { 251 self.0.last_end = self.0.re.next_after_empty(self.0.text, e); 252 if Some(e) == self.0.last_match { 253 return self.next(); 254 } 255 } else { 256 self.0.last_end = e; 257 } 258 self.0.last_match = Some(e); 259 Some(locs) 260 } 261 } 262