once_list2/
lib.rs

1// Copyright 2021 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![doc = include_str!("../README.md")]
16#![cfg_attr(feature = "nightly", feature(allocator_api))]
17#![cfg_attr(feature = "nightly", feature(box_into_inner))]
18#![cfg_attr(feature = "nightly", feature(coerce_unsized))]
19#![cfg_attr(feature = "nightly", feature(doc_cfg))]
20#![cfg_attr(feature = "nightly", feature(once_cell_try_insert))]
21#![cfg_attr(feature = "nightly", feature(ptr_metadata))]
22#![cfg_attr(feature = "nightly", feature(unsize))]
23
24#[cfg(not(feature = "sync"))]
25pub(crate) use ::std::cell::OnceCell;
26#[cfg(feature = "sync")]
27pub(crate) use ::std::sync::OnceLock as OnceCell;
28
29mod any;
30mod cache_mode;
31mod cons;
32mod iter;
33mod once_list;
34mod oncecell_ext;
35
36pub use crate::cache_mode::{CacheMode, NoCache, WithLen, WithTail, WithTailLen};
37pub use crate::iter::{IntoIter, Iter, IterMut};
38pub use crate::once_list::OnceList;
39pub use crate::once_list::OnceListCore;
40pub use crate::once_list::OnceListWithLen;
41pub use crate::once_list::OnceListWithTail;
42pub use crate::once_list::OnceListWithTailLen;
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47    use ::std::hash::Hash;
48
49    use ::allocator_api2::alloc::Global;
50
51    use crate::cache_mode::{CacheMode, NoCache, WithLen, WithTail, WithTailLen};
52    use crate::once_list::OnceListCore;
53
54    /// Cache-modes (not list types) we can construct for tests.
55    ///
56    /// This keeps the list type as `OnceListCore<i32, Global, M>` and still gives you the mode
57    /// (and therefore variant) in backtraces: `run::<WithTailLen<i32, Global>>()` etc.
58    trait I32Mode: CacheMode<i32, Global> + Clone {
59        fn new_list() -> OnceListCore<i32, Global, Self>;
60    }
61
62    impl I32Mode for NoCache {
63        fn new_list() -> OnceListCore<i32, Global, Self> {
64            OnceListCore::<i32, Global, NoCache>::new()
65        }
66    }
67    impl I32Mode for WithLen<i32, Global> {
68        fn new_list() -> OnceListCore<i32, Global, Self> {
69            OnceListCore::<i32, Global, WithLen<i32, Global>>::new()
70        }
71    }
72    impl I32Mode for WithTail<i32, Global> {
73        fn new_list() -> OnceListCore<i32, Global, Self> {
74            OnceListCore::<i32, Global, WithTail<i32, Global>>::new()
75        }
76    }
77    impl I32Mode for WithTailLen<i32, Global> {
78        fn new_list() -> OnceListCore<i32, Global, Self> {
79            OnceListCore::<i32, Global, WithTailLen<i32, Global>>::new()
80        }
81    }
82
83    // Defines a `#[test] fn ...()` and, inside it, a monomorphized helper `run::<L>()`.
84    // This keeps per-variant type information in backtraces without extra panic plumbing.
85    macro_rules! test_all_i32_variants {
86        (fn $test_name:ident($list:ident) $body:block) => {
87            #[test]
88            fn $test_name() {
89                fn run<M: I32Mode>() {
90                    let $list: OnceListCore<i32, Global, M> = M::new_list();
91                    $body
92                }
93
94                run::<NoCache>();
95                run::<WithLen<i32, Global>>();
96                run::<WithTail<i32, Global>>();
97                run::<WithTailLen<i32, Global>>();
98            }
99        };
100    }
101
102    test_all_i32_variants!(fn test_new(list) {
103        assert!(list.is_empty());
104        assert_eq!(list.len(), 0);
105        assert_eq!(list.iter().next(), None);
106    });
107
108    #[test]
109    fn test_default() {
110        // `Default` is defined only for the default mode (`OnceList`).
111        let list = OnceList::<i32>::default();
112        assert!(list.is_empty());
113        assert_eq!(list.len(), 0);
114        assert_eq!(list.iter().next(), None);
115    }
116
117    #[test]
118    fn test_from_iter() {
119        // `FromIterator` is implemented only for the default mode (`OnceList`).
120        let list = [1, 2, 3].into_iter().collect::<OnceList<_>>();
121        assert_eq!(list.len(), 3);
122        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
123
124        // For other modes, build via `extend` and assert the same semantics.
125        fn run<M: I32Mode>() {
126            let list: OnceListCore<i32, Global, M> = M::new_list();
127            list.extend([1, 2, 3]);
128            assert_eq!(list.len(), 3);
129            assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
130        }
131        run::<NoCache>();
132        run::<WithLen<i32, Global>>();
133        run::<WithTail<i32, Global>>();
134        run::<WithTailLen<i32, Global>>();
135    }
136
137    test_all_i32_variants!(fn test_push(list) {
138        let val = list.push_back(42);
139        assert_eq!(val, &42);
140        assert_eq!(list.len(), 1);
141        assert_eq!(list.clone().into_iter().collect::<Vec<_>>(), vec![42]);
142
143        list.push_back(100);
144        list.push_back(3);
145        assert_eq!(list.len(), 3);
146        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![42, 100, 3]);
147    });
148
149    test_all_i32_variants!(fn test_extend(list) {
150        list.extend([1, 2, 3]);
151        list.extend([4, 5, 6]);
152        assert_eq!(list.len(), 6);
153        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]);
154    });
155
156    test_all_i32_variants!(fn test_clear(list) {
157        let mut list = list;
158        list.extend([1, 2, 3]);
159        list.clear();
160        assert!(list.is_empty());
161        assert_eq!(list.len(), 0);
162        assert_eq!(list.iter().next(), None);
163    });
164
165    test_all_i32_variants!(fn test_front_back(list) {
166        assert_eq!(list.front(), None);
167        assert_eq!(list.back(), None);
168
169        list.push_back(42);
170        assert_eq!(list.front(), Some(&42));
171        assert_eq!(list.back(), Some(&42));
172
173        list.extend([1, 2, 3]);
174        assert_eq!(list.front(), Some(&42));
175        assert_eq!(list.back(), Some(&3));
176
177        // Compatibility aliases.
178        assert_eq!(list.first(), list.front());
179        assert_eq!(list.last(), list.back());
180    });
181
182    test_all_i32_variants!(fn test_pop_front(list) {
183        let mut list = list;
184        assert_eq!(list.pop_front(), None);
185
186        list.extend([1, 2, 3]);
187        assert_eq!(list.pop_front(), Some(1));
188        assert_eq!(list.front(), Some(&2));
189        assert_eq!(list.back(), Some(&3));
190        assert_eq!(list.len(), 2);
191
192        assert_eq!(list.pop_front(), Some(2));
193        assert_eq!(list.pop_front(), Some(3));
194        assert_eq!(list.pop_front(), None);
195        assert!(list.is_empty());
196        assert_eq!(list.len(), 0);
197    });
198
199    test_all_i32_variants!(fn test_contains(list) {
200        list.extend([1, 2, 3]);
201        assert!(list.contains(&1));
202        assert!(list.contains(&2));
203        assert!(list.contains(&3));
204        assert!(!list.contains(&0));
205        assert!(!list.contains(&4));
206    });
207
208    test_all_i32_variants!(fn test_remove(list) {
209        let mut list = list;
210        list.extend([1, 2, 3]);
211        assert_eq!(list.remove(|&v| v == 2), Some(2));
212        assert_eq!(list.iter().collect::<Vec<_>>(), vec![&1, &3]);
213
214        assert_eq!(list.remove(|&v| v == 0), None);
215        assert_eq!(list.iter().collect::<Vec<_>>(), vec![&1, &3]);
216
217        assert_eq!(list.remove(|&v| v == 1), Some(1));
218        assert_eq!(list.iter().collect::<Vec<_>>(), vec![&3]);
219
220        assert_eq!(list.remove(|&v| v == 3), Some(3));
221        assert!(list.is_empty());
222    });
223
224    test_all_i32_variants!(fn test_iter_sees_push_after_exhausted(list) {
225        list.push_back(1);
226
227        let mut it = list.iter();
228        assert_eq!(it.next(), Some(&1));
229        assert_eq!(it.next(), None);
230
231        // After the iterator reached the end, pushing a new element should make it visible
232        // from the same iterator.
233        list.push_back(2);
234        assert_eq!(it.next(), Some(&2));
235        assert_eq!(it.next(), None);
236    });
237
238    test_all_i32_variants!(fn test_iter_sees_extend_after_exhausted(list) {
239        list.push_back(1);
240
241        let mut it = list.iter();
242        assert_eq!(it.next(), Some(&1));
243        assert_eq!(it.next(), None);
244
245        // Same property should hold for `extend()` as well.
246        list.extend([2, 3]);
247        assert_eq!(it.next(), Some(&2));
248        assert_eq!(it.next(), Some(&3));
249        assert_eq!(it.next(), None);
250    });
251
252    test_all_i32_variants!(fn test_iter_mut_allows_in_place_update(list) {
253        let mut list = list;
254        list.extend([1, 2, 3]);
255        for v in list.iter_mut() {
256            *v += 10;
257        }
258        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![11, 12, 13]);
259    });
260
261    test_all_i32_variants!(fn test_into_iter_for_ref(list) {
262        list.extend([1, 2, 3]);
263
264        // `IntoIterator for &OnceListCore` should yield `&T`.
265        let collected = (&list).into_iter().copied().collect::<Vec<_>>();
266        assert_eq!(collected, vec![1, 2, 3]);
267
268        // Also ensure `for x in &list` works (uses the same `IntoIterator` impl).
269        let mut sum = 0;
270        for &v in &list {
271            sum += v;
272        }
273        assert_eq!(sum, 6);
274    });
275
276    test_all_i32_variants!(fn test_into_iter_for_mut_ref_allows_in_place_update(list) {
277        let mut list = list;
278        list.extend([1, 2, 3]);
279
280        // `IntoIterator for &mut OnceListCore` should yield `&mut T`.
281        for v in &mut list {
282            *v += 10;
283        }
284        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![11, 12, 13]);
285    });
286
287    test_all_i32_variants!(fn test_iter_mut_empty_and_singleton(list) {
288        // Empty list
289        {
290            let mut empty = list;
291            let mut it = empty.iter_mut();
292            assert!(it.next().is_none());
293
294            // Singleton list (reuse the same list type/instance)
295            empty.push_back(1);
296            let mut it = empty.iter_mut();
297            let v = it.next().unwrap();
298            *v = 2;
299            assert!(it.next().is_none());
300            assert_eq!(empty.into_iter().collect::<Vec<_>>(), vec![2]);
301        }
302    });
303
304    test_all_i32_variants!(fn test_eq(list1) {
305        list1.extend([1, 2, 3]);
306
307        let list2 = {
308            let l = OnceList::<i32>::new();
309            l.extend([1, 2, 3]);
310            l
311        };
312        assert_eq!(
313            list1.iter().collect::<Vec<_>>(),
314            list2.iter().collect::<Vec<_>>()
315        );
316
317        let list3 = {
318            let l = OnceList::<i32>::new();
319            l.extend([1, 2, 4]);
320            l
321        };
322        assert_ne!(
323            list1.iter().collect::<Vec<_>>(),
324            list3.iter().collect::<Vec<_>>()
325        );
326    });
327
328    test_all_i32_variants!(fn test_hash(list1) {
329        use ::std::hash::{DefaultHasher, Hasher};
330        list1.extend([1, 2, 3]);
331
332        let list2 = {
333            let l = OnceList::<i32>::new();
334            l.extend([1, 2, 3]);
335            l
336        };
337
338        let mut hasher1 = DefaultHasher::new();
339        let mut hasher2 = DefaultHasher::new();
340        list1.hash(&mut hasher1);
341        list2.hash(&mut hasher2);
342        assert_eq!(hasher1.finish(), hasher2.finish());
343    });
344
345    #[test]
346    #[cfg(feature = "nightly")]
347    fn test_unsized_slice_push() {
348        let list: OnceList<[i32]> = OnceList::new();
349        let first = list.push_unsized([1]);
350        let second = list.push_unsized([2, 3]);
351        assert_eq!(first, &[1]);
352        assert_eq!(second, &[2, 3]);
353
354        assert_eq!(list.iter().nth(0), Some(&[1] as &[i32]));
355        assert_eq!(list.iter().nth(1), Some(&[2, 3] as &[i32]));
356    }
357
358    #[test]
359    #[cfg(feature = "nightly")]
360    fn test_unsized_dyn_push() {
361        let list: OnceList<dyn ToString> = OnceList::new();
362        let first = list.push_unsized(1);
363        let second = list.push_unsized("hello");
364        assert_eq!(first.to_string(), "1");
365        assert_eq!(second.to_string(), "hello");
366
367        assert_eq!(
368            list.iter().nth(0).map(<dyn ToString>::to_string),
369            Some("1".to_string())
370        );
371        assert_eq!(
372            list.iter().nth(1).map(<dyn ToString>::to_string),
373            Some("hello".to_string())
374        );
375    }
376
377    #[test]
378    #[cfg(feature = "nightly")]
379    fn test_unsized_slice_remove_into_box() {
380        let list = OnceList::<[i32]>::new();
381        list.push_unsized([1]);
382        list.push_unsized([2, 3]);
383        list.push_unsized([4, 5, 6]);
384
385        let mut list = list;
386        let removed = list.remove_into_box(|s| s.len() == 2);
387        assert_eq!(removed, Some(Box::new([2, 3]) as Box<[i32]>));
388        assert_eq!(list.len(), 2);
389        assert_eq!(list.iter().nth(0), Some(&[1] as &[i32]));
390        assert_eq!(list.iter().nth(1), Some(&[4, 5, 6] as &[i32]));
391    }
392
393    #[test]
394    #[cfg(feature = "nightly")]
395    fn test_unsized_dyn_remove_into_box() {
396        let list = OnceList::<dyn ToString>::new();
397        list.push_unsized(1);
398        list.push_unsized("hello");
399        list.push_unsized(42);
400
401        let mut list = list;
402        let removed = list.remove_into_box(|s| s.to_string() == "hello");
403        assert_eq!(removed.map(|s| s.to_string()), Some("hello".to_string()));
404        assert_eq!(list.len(), 2);
405        assert_eq!(
406            list.iter().nth(0).map(|s| s.to_string()),
407            Some("1".to_string())
408        );
409        assert_eq!(
410            list.iter().nth(1).map(|s| s.to_string()),
411            Some("42".to_string())
412        );
413    }
414
415    #[test]
416    #[cfg(feature = "nightly")]
417    fn test_unsized_slice_remove_as() {
418        let list = OnceList::<[i32]>::new();
419        list.push_unsized([1]);
420        list.push_unsized([2, 3]);
421        list.push_unsized([4, 5, 6]);
422
423        let mut list = list;
424        let removed: Option<[i32; 2]> = unsafe { list.remove_unsized_as(|s| s.try_into().ok()) };
425        assert_eq!(removed, Some([2, 3]));
426        assert_eq!(list.len(), 2);
427        assert_eq!(list.iter().nth(0), Some(&[1] as &[i32]));
428        assert_eq!(list.iter().nth(1), Some(&[4, 5, 6] as &[i32]));
429    }
430
431    // (No special "variant labeling" test needed; the per-variant generic `run::<L>()`
432    // monomorphization will show `L` in backtraces when `RUST_BACKTRACE=1` is enabled.)
433}
once_list2/lib.rs

once_list2/
lib.rs
