opendal/raw/oio/list/
flat_list.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use crate::raw::*;
19use crate::*;
20
21/// FlatLister will walk dir in bottom up way:
22///
23/// - List nested dir first
24/// - Go back into parent dirs one by one
25///
26/// Given the following file tree:
27///
28/// ```txt
29/// .
30/// ├── dir_x/
31/// │   ├── dir_y/
32/// │   │   ├── dir_z/
33/// │   │   └── file_c
34/// │   └── file_b
35/// └── file_a
36/// ```
37///
38/// ToFlatLister will output entries like:
39///
40/// ```txt
41/// dir_x/dir_y/dir_z/file_c
42/// dir_x/dir_y/dir_z/
43/// dir_x/dir_y/file_b
44/// dir_x/dir_y/
45/// dir_x/file_a
46/// dir_x/
47/// ```
48///
49/// # Note
50///
51/// There is no guarantee about the order between files and dirs at the same level.
52/// We only make sure the nested dirs will show up before parent dirs.
53///
54/// Especially, for storage services that can't return dirs first, ToFlatLister
55/// may output parent dirs' files before nested dirs, this is expected because files
56/// always output directly while listing.
57pub struct FlatLister<A: Access, L> {
58    acc: A,
59
60    next_dir: Option<oio::Entry>,
61    active_lister: Vec<(Option<oio::Entry>, L)>,
62}
63
64/// # Safety
65///
66/// wasm32 is a special target that we only have one event-loop for this FlatLister.
67unsafe impl<A: Access, L> Send for FlatLister<A, L> {}
68/// # Safety
69///
70/// We will only take `&mut Self` reference for FsLister.
71unsafe impl<A: Access, L> Sync for FlatLister<A, L> {}
72
73impl<A, L> FlatLister<A, L>
74where
75    A: Access,
76{
77    /// Create a new flat lister
78    pub fn new(acc: A, path: &str) -> FlatLister<A, L> {
79        FlatLister {
80            acc,
81            next_dir: Some(oio::Entry::new(path, Metadata::new(EntryMode::DIR))),
82            active_lister: vec![],
83        }
84    }
85}
86
87impl<A, L> oio::List for FlatLister<A, L>
88where
89    A: Access<Lister = L>,
90    L: oio::List,
91{
92    async fn next(&mut self) -> Result<Option<oio::Entry>> {
93        loop {
94            if let Some(de) = self.next_dir.take() {
95                let (_, mut l) = self.acc.list(de.path(), OpList::new()).await?;
96                if let Some(v) = l.next().await? {
97                    self.active_lister.push((Some(de.clone()), l));
98
99                    if v.mode().is_dir() {
100                        // should not loop itself again
101                        if v.path() != de.path() {
102                            self.next_dir = Some(v);
103                            continue;
104                        }
105                    } else {
106                        return Ok(Some(v));
107                    }
108                }
109            }
110
111            let (de, lister) = match self.active_lister.last_mut() {
112                Some((de, lister)) => (de, lister),
113                None => return Ok(None),
114            };
115
116            match lister.next().await? {
117                Some(v) if v.mode().is_dir() => {
118                    // should not loop itself again
119                    if v.path() != de.as_ref().expect("de should not be none here").path() {
120                        self.next_dir = Some(v);
121                        continue;
122                    }
123                }
124                Some(v) => return Ok(Some(v)),
125                None => match de.take() {
126                    Some(de) => {
127                        return Ok(Some(de));
128                    }
129                    None => {
130                        let _ = self.active_lister.pop();
131                        continue;
132                    }
133                },
134            }
135        }
136    }
137}
138
139impl<A, P> oio::BlockingList for FlatLister<A, P>
140where
141    A: Access<BlockingLister = P>,
142    P: oio::BlockingList,
143{
144    fn next(&mut self) -> Result<Option<oio::Entry>> {
145        loop {
146            if let Some(de) = self.next_dir.take() {
147                let (_, mut l) = self.acc.blocking_list(de.path(), OpList::new())?;
148                if let Some(v) = l.next()? {
149                    self.active_lister.push((Some(de.clone()), l));
150
151                    if v.mode().is_dir() {
152                        // should not loop itself again
153                        if v.path() != de.path() {
154                            self.next_dir = Some(v);
155                            continue;
156                        }
157                    } else {
158                        return Ok(Some(v));
159                    }
160                }
161            }
162
163            let (de, lister) = match self.active_lister.last_mut() {
164                Some((de, lister)) => (de, lister),
165                None => return Ok(None),
166            };
167
168            match lister.next()? {
169                Some(v) if v.mode().is_dir() => {
170                    if v.path() != de.as_ref().expect("de should not be none here").path() {
171                        self.next_dir = Some(v);
172                        continue;
173                    }
174                }
175                Some(v) => return Ok(Some(v)),
176                None => match de.take() {
177                    Some(de) => {
178                        return Ok(Some(de));
179                    }
180                    None => {
181                        let _ = self.active_lister.pop();
182                        continue;
183                    }
184                },
185            }
186        }
187    }
188}
189
190#[cfg(test)]
191mod tests {
192    use std::collections::HashMap;
193    use std::sync::Arc;
194    use std::vec;
195    use std::vec::IntoIter;
196
197    use log::debug;
198    use oio::BlockingList;
199
200    use super::*;
201
202    #[derive(Debug)]
203    struct MockService {
204        map: HashMap<&'static str, Vec<&'static str>>,
205    }
206
207    impl MockService {
208        fn new() -> Self {
209            let mut map = HashMap::default();
210            map.insert("x/", vec!["x/x/"]);
211            map.insert("x/x/", vec!["x/x/x/"]);
212            map.insert("x/x/x/", vec!["x/x/x/x"]);
213
214            Self { map }
215        }
216
217        fn get(&self, path: &str) -> MockLister {
218            let inner = self.map.get(path).expect("must have value").to_vec();
219
220            MockLister {
221                inner: inner.into_iter(),
222            }
223        }
224    }
225
226    impl Access for MockService {
227        type Reader = ();
228        type BlockingReader = ();
229        type Writer = ();
230        type BlockingWriter = ();
231        type Lister = ();
232        type BlockingLister = MockLister;
233        type Deleter = ();
234        type BlockingDeleter = ();
235
236        fn info(&self) -> Arc<AccessorInfo> {
237            let am = AccessorInfo::default();
238            am.update_full_capability(|mut cap| {
239                cap.list = true;
240                cap
241            });
242            am.into()
243        }
244
245        fn blocking_list(&self, path: &str, _: OpList) -> Result<(RpList, Self::BlockingLister)> {
246            debug!("visit path: {path}");
247            Ok((RpList::default(), self.get(path)))
248        }
249    }
250
251    struct MockLister {
252        inner: IntoIter<&'static str>,
253    }
254
255    impl BlockingList for MockLister {
256        fn next(&mut self) -> Result<Option<oio::Entry>> {
257            Ok(self.inner.next().map(|path| {
258                if path.ends_with('/') {
259                    oio::Entry::new(path, Metadata::new(EntryMode::DIR))
260                } else {
261                    oio::Entry::new(path, Metadata::new(EntryMode::FILE))
262                }
263            }))
264        }
265    }
266
267    #[test]
268    fn test_blocking_list() -> Result<()> {
269        let _ = tracing_subscriber::fmt().with_test_writer().try_init();
270
271        let acc = MockService::new();
272        let mut lister = FlatLister::new(acc, "x/");
273
274        let mut entries = Vec::default();
275
276        while let Some(e) = lister.next()? {
277            entries.push(e)
278        }
279
280        assert_eq!(
281            entries[0],
282            oio::Entry::new("x/x/x/x", Metadata::new(EntryMode::FILE))
283        );
284
285        Ok(())
286    }
287}
opendal/raw/oio/list/flat_list.rs

opendal/raw/oio/list/
flat_list.rs
