c/
fts.rs

1// Copyright (c) 2026 Meng Zhuo
2// SPDX-License-Identifier: BSD-3-Clause
3
4// A real fts(3) implementation. The tree is scanned depth-first on the first
5// fts_read() call into a preorder array; fts_read() then walks that array.
6
7pub const FTS_COMFOLLOW_V: c_int = 0x001;
8pub const FTS_LOGICAL_V: c_int = 0x002;
9pub const FTS_NOCHDIR_V: c_int = 0x004;
10pub const FTS_NOSTAT_V: c_int = 0x008;
11pub const FTS_PHYSICAL_V: c_int = 0x010;
12pub const FTS_SEEDOT_V: c_int = 0x020;
13pub const FTS_XDEV_V: c_int = 0x040;
14
15pub const FTS_D_V: u16 = 1;
16pub const FTS_DC_V: u16 = 2;
17pub const FTS_DEFAULT_V: u16 = 3;
18pub const FTS_DNR_V: u16 = 4;
19pub const FTS_DOT_V: u16 = 5;
20pub const FTS_DP_V: u16 = 6;
21pub const FTS_ERR_V: u16 = 7;
22pub const FTS_F_V: u16 = 8;
23pub const FTS_INIT_V: u16 = 9;
24pub const FTS_NS_V: u16 = 10;
25pub const FTS_NSOK_V: u16 = 11;
26pub const FTS_SL_V: u16 = 12;
27pub const FTS_SLNONE_V: u16 = 13;
28pub const FTS_W_V: u16 = 14;
29
30pub const FTS_SKIP_V: c_int = 1;
31pub const FTS_FOLLOW_V: c_int = 2;
32pub const FTS_NOINSTR_V: c_int = 3;
33
34const FTS_NAME_OFF: usize = 112;
35
36#[repr(C)]
37pub struct FtsEnt {
38    pub fts_cycle: *mut FtsEnt,
39    pub fts_parent: *mut FtsEnt,
40    pub fts_link: *mut FtsEnt,
41    pub fts_number: c_long,
42    pub fts_pointer: *mut c_void,
43    pub fts_accpath: *mut c_char,
44    pub fts_path: *mut c_char,
45    pub fts_errno: c_int,
46    pub fts_symfd: c_int,
47    pub fts_pathlen: u16,
48    pub fts_namelen: u16,
49    pub fts_ino: u64,
50    pub fts_dev: u64,
51    pub fts_nlink: u64,
52    pub fts_level: u16,
53    pub fts_info: u16,
54    pub fts_flags: u16,
55    pub fts_instr: u16,
56    pub fts_statp: *mut Stat,
57    pub fts_name: [c_char; 1],
58}
59
60const _: [(); 120] = [(); core::mem::size_of::<FtsEnt>()];
61
62pub struct Fts {
63    roots: *mut *mut c_char,
64    nroots: usize,
65    options: c_int,
66    compar: Option<unsafe extern "C" fn(*const *const FtsEnt, *const *const FtsEnt) -> c_int>,
67    ents: *mut *mut FtsEnt,
68    nents: usize,
69    ents_cap: usize,
70    idx: usize,
71    built: bool,
72}
73
74unsafe fn fts_name_ptr(ent: *mut FtsEnt) -> *mut c_char {
75    (ent as *mut u8).add(FTS_NAME_OFF) as *mut c_char
76}
77
78unsafe fn fts_ent_alloc(
79    path: *const c_char,
80    name: *const c_char,
81    level: u16,
82    parent: *mut FtsEnt,
83) -> *mut FtsEnt {
84    let plen = crate::strlen(path);
85    let nlen = crate::strlen(name);
86    let namelen = nlen + 1;
87    let stat_off = (core::mem::size_of::<FtsEnt>() + namelen + 7) & !7usize;
88    let total = stat_off + core::mem::size_of::<Stat>();
89    let raw = crate::calloc(1, total) as *mut u8;
90    if raw.is_null() { return core::ptr::null_mut(); }
91    let ent = raw as *mut FtsEnt;
92    (*ent).fts_parent = parent;
93    (*ent).fts_level = level;
94    (*ent).fts_pathlen = plen as u16;
95    (*ent).fts_namelen = nlen as u16;
96    let pathbuf = crate::malloc(plen + 1) as *mut c_char;
97    if pathbuf.is_null() { crate::free(raw as *mut c_void); return core::ptr::null_mut(); }
98    core::ptr::copy_nonoverlapping(path, pathbuf, plen + 1);
99    (*ent).fts_path = pathbuf;
100    (*ent).fts_accpath = pathbuf;
101    core::ptr::copy_nonoverlapping(name, fts_name_ptr(ent), namelen);
102    (*ent).fts_statp = raw.add(stat_off) as *mut Stat;
103    ent
104}
105
106unsafe fn fts_push(fts: *mut Fts, ent: *mut FtsEnt) {
107    if ent.is_null() { return; }
108    if (*fts).nents == (*fts).ents_cap {
109        let ncap = if (*fts).ents_cap == 0 { 64 } else { (*fts).ents_cap * 2 };
110        let na = crate::realloc(
111            (*fts).ents as *mut c_void,
112            ncap * core::mem::size_of::<*mut FtsEnt>(),
113        ) as *mut *mut FtsEnt;
114        if na.is_null() { return; }
115        (*fts).ents = na;
116        (*fts).ents_cap = ncap;
117    }
118    *(*fts).ents.add((*fts).nents) = ent;
119    (*fts).nents += 1;
120    (*ent).fts_link = core::ptr::null_mut();
121}
122
123unsafe fn fts_free_ent(ent: *mut FtsEnt) {
124    if ent.is_null() { return; }
125    if !(*ent).fts_path.is_null() { crate::free((*ent).fts_path as *mut c_void); }
126    crate::free(ent as *mut c_void);
127}
128
129unsafe fn fts_name_of(path: *const c_char) -> *const c_char {
130    let n = crate::strlen(path);
131    let mut i = n;
132    while i > 0 {
133        if *path.add(i - 1) == b'/' as c_char { break; }
134        i -= 1;
135    }
136    path.add(i)
137}
138
139unsafe fn fts_join(dir: *const c_char, name: *const c_char) -> *mut c_char {
140    let dl = crate::strlen(dir);
141    let nl = crate::strlen(name);
142    let need_sep = dl > 0 && *dir.add(dl - 1) != b'/' as c_char;
143    let total = dl + if need_sep { 1 } else { 0 } + nl + 1;
144    let p = crate::malloc(total) as *mut c_char;
145    if p.is_null() { return core::ptr::null_mut(); }
146    core::ptr::copy_nonoverlapping(dir, p, dl);
147    let mut o = dl;
148    if need_sep { *p.add(o) = b'/' as c_char; o += 1; }
149    core::ptr::copy_nonoverlapping(name, p.add(o), nl + 1);
150    p
151}
152
153unsafe fn fts_is_dir(mode: u32) -> bool { mode & 0o170000 == 0o040000 }
154unsafe fn fts_is_link(mode: u32) -> bool { mode & 0o170000 == 0o120000 }
155
156unsafe fn fts_stat_path(path: *const c_char, follow: bool, st: *mut Stat) -> c_int {
157    if follow { crate::stat(path, st) } else { crate::lstat(path, st as *mut c_void) }
158}
159
160unsafe fn fts_collect_names(path: *const c_char) -> (*mut *mut c_char, usize) {
161    let fd = crate::open(path, crate::O_DIRECTORY, 0); // O_RDONLY|O_DIRECTORY
162    if fd < 0 { return (core::ptr::null_mut(), 0); }
163    let mut cap = 16usize;
164    let mut count = 0usize;
165    let mut arr = crate::malloc(cap * core::mem::size_of::<*mut c_char>()) as *mut *mut c_char;
166    if arr.is_null() { crate::close(fd); return (core::ptr::null_mut(), 0); }
167    let mut buf = [0u8; 4096];
168    loop {
169        let n = <Arch as Syscalls>::syscall3(
170            SYS_GETDENTS64,
171            fd as i64,
172            buf.as_mut_ptr() as i64,
173            buf.len() as i64,
174        ) as isize;
175        if n <= 0 { break; }
176        let mut pos = 0usize;
177        while pos < n as usize {
178            let ent = buf.as_ptr().add(pos) as *const linux_dirent64;
179            let reclen = (*ent).d_reclen as usize;
180            if reclen == 0 { break; }
181            let namep = (ent as *const u8).add(core::mem::offset_of!(linux_dirent64, d_name)) as *const c_char;
182            let nl = crate::strlen(namep);
183            if count + 2 >= cap {
184                cap *= 2;
185                let na = crate::realloc(arr as *mut c_void, cap * core::mem::size_of::<*mut c_char>()) as *mut *mut c_char;
186                if na.is_null() { break; }
187                arr = na;
188            }
189            let copy = crate::malloc(nl + 1) as *mut c_char;
190            if copy.is_null() { break; }
191            core::ptr::copy_nonoverlapping(namep, copy, nl + 1);
192            *arr.add(count) = copy;
193            count += 1;
194            pos += reclen;
195        }
196    }
197    crate::close(fd);
198    (arr, count)
199}
200
201unsafe fn fts_free_names(arr: *mut *mut c_char, count: usize) {
202    if arr.is_null() { return; }
203    for i in 0..count {
204        if !(*arr.add(i)).is_null() { crate::free(*arr.add(i) as *mut c_void); }
205    }
206    crate::free(arr as *mut c_void);
207}
208
209unsafe fn fts_sort_entries(fts: *mut Fts, arr: *mut *mut FtsEnt, count: usize) {
210    let cmp = match (*fts).compar { Some(c) => c, None => return };
211    for i in 1..count {
212        let v = *arr.add(i);
213        let mut j = i;
214        while j > 0 {
215            let prev = *arr.add(j - 1);
216            let a = prev as *const FtsEnt;
217            let b = v as *const FtsEnt;
218            if cmp(&a, &b) <= 0 { break; }
219            *arr.add(j) = prev;
220            j -= 1;
221        }
222        *arr.add(j) = v;
223    }
224}
225
226unsafe fn fts_fill_info(ent: *mut FtsEnt, st: *mut Stat) -> u16 {
227    if (*ent).fts_errno != 0 { return FTS_NS_V; }
228    let mode = (*st).st_mode;
229    if fts_is_dir(mode) { FTS_D_V }
230    else if fts_is_link(mode) { FTS_SL_V }
231    else if mode & 0o170000 == 0o100000 { FTS_F_V }
232    else { FTS_DEFAULT_V }
233}
234
235unsafe fn fts_walk(fts: *mut Fts, ent: *mut FtsEnt) {
236    fts_push(fts, ent);
237    if (*ent).fts_level >= 64 || (*ent).fts_info != FTS_D_V { return; }
238    let mut p = (*ent).fts_parent;
239    while !p.is_null() {
240        if (*p).fts_info == FTS_D_V && (*p).fts_dev == (*ent).fts_dev && (*p).fts_ino == (*ent).fts_ino {
241            (*ent).fts_info = FTS_DC_V;
242            return;
243        }
244        p = (*p).fts_parent;
245    }
246
247    let (names, count) = fts_collect_names((*ent).fts_path);
248    if !names.is_null() {
249        let ptrsz = core::mem::size_of::<*mut c_char>();
250        let kids = crate::malloc((count + 1) * ptrsz) as *mut *mut FtsEnt;
251        if !kids.is_null() {
252            let mut nkids = 0usize;
253            for i in 0..count {
254                let name = *names.add(i);
255                if ((*fts).options & FTS_SEEDOT_V) == 0 {
256                    if crate::strcmp(name as *const u8, b".\0".as_ptr()) == 0 { continue; }
257                    if crate::strcmp(name as *const u8, b"..\0".as_ptr()) == 0 { continue; }
258                }
259                let full = fts_join((*ent).fts_path, name);
260                if full.is_null() { continue; }
261                let child = fts_ent_alloc(full, name, (*ent).fts_level + 1, ent);
262                crate::free(full as *mut c_void);
263                if child.is_null() { continue; }
264                let mut st: Stat = core::mem::zeroed();
265                let follow = (*fts).options & FTS_LOGICAL_V != 0;
266                let mut rc = fts_stat_path((*child).fts_path, follow, &mut st);
267                if rc != 0 && !follow {
268                    rc = fts_stat_path((*child).fts_path, true, &mut st);
269                }
270                if rc != 0 {
271                    (*child).fts_errno = ERRNO!();
272                    (*child).fts_info = FTS_NS_V;
273                } else {
274                    core::ptr::copy_nonoverlapping(&st as *const Stat as *const u8, (*child).fts_statp as *mut u8, core::mem::size_of::<Stat>());
275                    (*child).fts_ino = st.st_ino;
276                    (*child).fts_dev = st.st_dev;
277                    (*child).fts_nlink = st.st_nlink as u64;
278                    (*child).fts_info = fts_fill_info(child, &mut st);
279                }
280                *kids.add(nkids) = child;
281                nkids += 1;
282            }
283            fts_sort_entries(fts, kids, nkids);
284            for i in 0..nkids { fts_walk(fts, *kids.add(i)); }
285            crate::free(kids as *mut c_void);
286        }
287        fts_free_names(names, count);
288    }
289
290    let dp = fts_ent_alloc((*ent).fts_path, fts_name_ptr(ent), (*ent).fts_level, (*ent).fts_parent);
291    if !dp.is_null() {
292        (*dp).fts_info = FTS_DP_V;
293        (*dp).fts_dev = (*ent).fts_dev;
294        (*dp).fts_ino = (*ent).fts_ino;
295        fts_push(fts, dp);
296    }
297}
298
299unsafe fn fts_build(fts: *mut Fts) {
300    (*fts).built = true;
301    for i in 0..(*fts).nroots {
302        let root = *(*fts).roots.add(i);
303        if root.is_null() { continue; }
304        let mut st: Stat = core::mem::zeroed();
305        let follow = (*fts).options & (FTS_LOGICAL_V | FTS_COMFOLLOW_V) != 0;
306        let rc = fts_stat_path(root, follow, &mut st);
307        let ent = fts_ent_alloc(root, fts_name_of(root), 0, core::ptr::null_mut());
308        if ent.is_null() { continue; }
309        if rc != 0 {
310            (*ent).fts_errno = ERRNO!();
311            (*ent).fts_info = FTS_NS_V;
312            fts_push(fts, ent);
313            continue;
314        }
315        core::ptr::copy_nonoverlapping(&st as *const Stat as *const u8, (*ent).fts_statp as *mut u8, core::mem::size_of::<Stat>());
316        (*ent).fts_ino = st.st_ino;
317        (*ent).fts_dev = st.st_dev;
318        (*ent).fts_nlink = st.st_nlink as u64;
319        (*ent).fts_info = fts_fill_info(ent, &mut st);
320        fts_walk(fts, ent);
321    }
322}
323
324#[no_mangle]
325pub unsafe extern "C" fn fts_open(
326    path_argv: *mut *mut c_char,
327    options: c_int,
328    compar: Option<unsafe extern "C" fn(*const *const FtsEnt, *const *const FtsEnt) -> c_int>,
329) -> *mut Fts {
330    if path_argv.is_null() || (*path_argv).is_null() {
331        ERRNO!() = EINVAL;
332        return core::ptr::null_mut();
333    }
334    let fts = crate::calloc(1, core::mem::size_of::<Fts>()) as *mut Fts;
335    if fts.is_null() { ERRNO!() = ENOMEM; return core::ptr::null_mut(); }
336    let mut n = 0usize;
337    while !(*path_argv.add(n)).is_null() { n += 1; }
338    let roots = crate::malloc((n + 1) * core::mem::size_of::<*mut c_char>()) as *mut *mut c_char;
339    if roots.is_null() { crate::free(fts as *mut c_void); ERRNO!() = ENOMEM; return core::ptr::null_mut(); }
340    for i in 0..n {
341        let s = *path_argv.add(i);
342        let l = crate::strlen(s);
343        let copy = crate::malloc(l + 1) as *mut c_char;
344        if copy.is_null() { ERRNO!() = ENOMEM; crate::free(roots as *mut c_void); crate::free(fts as *mut c_void); return core::ptr::null_mut(); }
345        core::ptr::copy_nonoverlapping(s, copy, l + 1);
346        *roots.add(i) = copy;
347    }
348    *roots.add(n) = core::ptr::null_mut();
349    (*fts).roots = roots;
350    (*fts).nroots = n;
351    (*fts).options = options;
352    (*fts).compar = compar;
353    (*fts).ents = core::ptr::null_mut();
354    (*fts).nents = 0;
355    (*fts).ents_cap = 0;
356    (*fts).idx = 0;
357    (*fts).built = false;
358    fts
359}
360
361#[no_mangle]
362pub unsafe extern "C" fn fts_read(fts: *mut Fts) -> *mut FtsEnt {
363    if fts.is_null() { ERRNO!() = EINVAL; return core::ptr::null_mut(); }
364    if !(*fts).built { fts_build(fts); }
365    if (*fts).idx < (*fts).nents {
366        let e = *(*fts).ents.add((*fts).idx);
367        (*fts).idx += 1;
368        return e;
369    }
370    core::ptr::null_mut()
371}
372
373#[no_mangle]
374pub unsafe extern "C" fn fts_set(fts: *mut Fts, ent: *mut FtsEnt, instr: c_int) -> c_int {
375    if fts.is_null() || ent.is_null() { ERRNO!() = EINVAL; return -1; }
376    match instr {
377        FTS_SKIP_V => {
378            (*ent).fts_instr = FTS_SKIP_V as u16;
379            if (*ent).fts_info == FTS_D_V {
380                let lvl = (*ent).fts_level;
381                while (*fts).idx < (*fts).nents {
382                    let e = *(*fts).ents.add((*fts).idx);
383                    if (*e).fts_level < lvl { break; }
384                    (*fts).idx += 1;
385                    if (*e).fts_level == lvl && (*e).fts_info == FTS_DP_V { break; }
386                }
387                (*ent).fts_instr = FTS_SKIP_V as u16;
388            }
389        }
390        FTS_FOLLOW_V => {
391            (*ent).fts_instr = FTS_FOLLOW_V as u16;
392            if (*ent).fts_info == FTS_SL_V || (*ent).fts_info == FTS_SLNONE_V {
393                let mut st: Stat = core::mem::zeroed();
394                if crate::stat((*ent).fts_path, &mut st) == 0 {
395                    core::ptr::copy_nonoverlapping(&st as *const Stat as *const u8, (*ent).fts_statp as *mut u8, core::mem::size_of::<Stat>());
396                    (*ent).fts_ino = st.st_ino;
397                    (*ent).fts_dev = st.st_dev;
398                    (*ent).fts_nlink = st.st_nlink as u64;
399                    (*ent).fts_info = fts_fill_info(ent, &mut st);
400                }
401            }
402        }
403        FTS_NOINSTR_V => { (*ent).fts_instr = FTS_NOINSTR_V as u16; }
404        _ => { ERRNO!() = EINVAL; return -1; }
405    }
406    0
407}
408
409#[no_mangle]
410pub unsafe extern "C" fn fts_children(fts: *mut Fts, _instr: c_int) -> *mut FtsEnt {
411    if fts.is_null() { ERRNO!() = EINVAL; return core::ptr::null_mut(); }
412    if !(*fts).built { fts_build(fts); }
413    if (*fts).idx == 0 { return core::ptr::null_mut(); }
414    let parent = *(*fts).ents.add((*fts).idx - 1);
415    if (*parent).fts_info != FTS_D_V { return core::ptr::null_mut(); }
416    let level = (*parent).fts_level + 1;
417    let mut head: *mut FtsEnt = core::ptr::null_mut();
418    let mut tail: *mut FtsEnt = core::ptr::null_mut();
419    let mut i = (*fts).idx;
420    while i < (*fts).nents {
421        let q = *(*fts).ents.add(i);
422        if (*q).fts_level < level { break; }
423        if (*q).fts_level == level && (*q).fts_info != FTS_DP_V {
424            (*q).fts_link = core::ptr::null_mut();
425            if head.is_null() { head = q; } else { (*tail).fts_link = q; }
426            tail = q;
427        }
428        i += 1;
429    }
430    head
431}
432
433#[no_mangle]
434pub unsafe extern "C" fn fts_close(fts: *mut Fts) -> c_int {
435    if fts.is_null() { ERRNO!() = EINVAL; return -1; }
436    for i in 0..(*fts).nents {
437        fts_free_ent(*(*fts).ents.add(i));
438    }
439    if !(*fts).ents.is_null() { crate::free((*fts).ents as *mut c_void); }
440    for i in 0..(*fts).nroots {
441        if !(*(*fts).roots.add(i)).is_null() { crate::free(*(*fts).roots.add(i) as *mut c_void); }
442    }
443    crate::free((*fts).roots as *mut c_void);
444    crate::free(fts as *mut c_void);
445    0
446}
c/fts.rs

c/
fts.rs
