c/
fts.rs

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

c/
fts.rs
