backtracking_iterator/
concurrent.rs

1/*
2 * Copyright (c) 2019 Isaac van Bakel
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy of
5 * this software and associated documentation files (the "Software"), to deal in
6 * the Software without restriction, including without limitation the rights to
7 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 * the Software, and to permit persons to whom the Software is furnished to do so,
9 * subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in all
12 * copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20 */
21
22use super::{BacktrackingState, BacktrackingIterator};
23
24use std::sync::{Arc, RwLock, Mutex};
25
26static EXPECT_RW: &'static str = "The read-write lock on the history has been poisoned by a thread panic!";
27static EXPECT_MUTEX: &'static str = "The mutual exclusion lock on the iterator has been poisoned by a thread panic!"; 
28
29
30impl<'item, Iter> From<Iter> for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
31  /// Create a `ConcurrentReferencingBacktrackingIterator` from an existing iterator.
32  fn from(iterator: Iter) -> Self {
33    ConcurrentReferencingBacktrackingIterator {
34      item_marker: std::marker::PhantomData,
35      iterator: Arc::new(Mutex::new(iterator)),
36      backtracking_vec: Arc::new(RwLock::new(vec![])),
37      position: 0,
38    }
39  }
40}
41
42pub struct ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
43  item_marker: std::marker::PhantomData<&'item Iter::Item>,
44  iterator: Arc<Mutex<Iter>>,
45  backtracking_vec: Arc<RwLock<Vec<Iter::Item>>>,
46  position: usize,
47}
48
49impl<'item, Iter> Clone for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
50  fn clone(&self) -> Self {
51    ConcurrentReferencingBacktrackingIterator {
52      item_marker: std::marker::PhantomData,
53      iterator: self.iterator.clone(),
54      backtracking_vec: self.backtracking_vec.clone(),
55      position: self.position,
56    }
57  }
58}
59
60impl<'item, Iter> Iterator for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
61  type Item = &'item Iter::Item;
62
63  fn next(&mut self) -> Option<&'item Iter::Item> {
64    macro_rules! unsafe_backtracking_index {
65      ($index:expr) => {
66        unsafe {
67          &*(&self.backtracking_vec.read().expect(EXPECT_RW)[$index] as *const Iter::Item)
68        }
69      };
70    }
71
72    use crate::{Backtracking, Progressing};
73    if self.position >= self.backtracking_vec.read().expect(EXPECT_RW).len() {
74      if let Some(val) = self.iterator.lock().expect(EXPECT_MUTEX).next() {
75        self.backtracking_vec.write().expect(EXPECT_RW).push(val);
76        self.position = self.position + 1;
77        Some(unsafe_backtracking_index!(self.backtracking_vec.read().expect(EXPECT_RW).len() - 1))
78      } else {
79        None
80      }
81    } else {
82      let old_position = self.position;
83      self.position = self.position + 1;
84      Some(unsafe_backtracking_index!(old_position))
85    }
86  }
87}
88
89impl<'item, Iter> BacktrackingIterator for ConcurrentReferencingBacktrackingIterator<'item, Iter> where Iter: Iterator, Iter: 'item {
90  type RefPoint = usize;
91
92  fn get_ref_point(&self) -> usize {
93    self.position
94  }
95
96  fn get_oldest_point(&self) -> usize {
97    // Always the oldest position
98    0_usize
99  }
100
101  fn backtrack(&mut self, position: usize) {
102    self.position = position;
103  }
104}
105
106//// COPYING VERSION
107
108impl<Iter> From<Iter> for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
109  /// Create a `ConcurrentCopyingBacktrackingIterator` from an existing iterator.
110  fn from(iterator: Iter) -> Self {
111    ConcurrentCopyingBacktrackingIterator {
112      iterator: Arc::new(Mutex::new(iterator)),
113      backtracking_vec: Arc::new(RwLock::new(vec![])),
114      position: 0,
115    }
116  }
117}
118
119pub struct ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
120  iterator: Arc<Mutex<Iter>>,
121  backtracking_vec: Arc<RwLock<Vec<Iter::Item>>>,
122  position: usize,
123}
124
125impl<Iter> Clone for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
126  fn clone(&self) -> Self {
127    ConcurrentCopyingBacktrackingIterator {
128      iterator: self.iterator.clone(),
129      backtracking_vec: self.backtracking_vec.clone(),
130      position: self.position,
131    }
132  }
133}
134
135impl<Iter> Iterator for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
136  type Item = Iter::Item;
137
138  fn next(&mut self) -> Option<Iter::Item> {
139    
140    use crate::{Backtracking, Progressing};
141    if self.position >= self.backtracking_vec.read().expect(EXPECT_RW).len() {
142      if let Some(val) = self.iterator.lock().expect(EXPECT_MUTEX).next() {
143        self.backtracking_vec.write().expect(EXPECT_RW).push(val.clone());
144        self.position = self.position + 1;
145        Some(val)
146      } else {
147        None
148      }
149    } else {
150      let old_position = self.position;
151      self.position = self.position + 1;
152      Some(self.backtracking_vec.read().expect(EXPECT_RW)[old_position].clone())
153    }
154  }
155}
156
157impl<Iter> BacktrackingIterator for ConcurrentCopyingBacktrackingIterator<Iter> where Iter: Iterator, Iter::Item: Clone {
158  type RefPoint = usize;
159
160  fn get_ref_point(&self) -> usize {
161    self.position
162  }
163
164  fn get_oldest_point(&self) -> usize {
165    // Always the oldest position
166    0_usize
167  }
168
169  fn backtrack(&mut self, position: usize) {
170    self.position = position;
171  }
172}
173
174
175#[cfg(test)]
176mod tests {
177  #[test]
178  fn many_iter_test() {
179    use matches::{matches};
180
181    let bt_con_iter = crate::concurrent::ConcurrentReferencingBacktrackingIterator::from(1..1000);
182    
183    for _ in 1..3 {
184      let mut bt_iter = bt_con_iter.clone();
185      for expected in 1..1000 {
186        assert!(matches!(bt_iter.next(), Some(&i) if i == expected))
187      }
188    }
189  }
190  
191  #[test]
192  fn many_iter_clone_test() {
193    use matches::{matches};
194
195    let bt_con_iter = crate::concurrent::ConcurrentCopyingBacktrackingIterator::from(1..1000);
196    
197    for _ in 1..3 {
198      let mut bt_iter = bt_con_iter.clone();
199      for expected in 1..1000 {
200        assert!(matches!(bt_iter.next(), Some(i) if i == expected))
201      }
202    }
203  }
204  
205  #[test]
206  fn dont_need_clone_test() {
207    use matches::{matches};
208
209    struct Uncloneable {};
210    let uncloneables = vec![Uncloneable {}];
211    let mut bt_con_iter = crate::concurrent::ConcurrentReferencingBacktrackingIterator::from(uncloneables.into_iter());
212
213    assert!(matches!(bt_con_iter.next(), Some(&Uncloneable {})))
214  }
215}
216