dymokomi/luce-std
Source of release 0.7.1
0.7.1 / src / files / walk.lucb
#==============================================================================================
#
# walk - Recursive directory traversal
#
# DESCRIPTION:
# Walk a directory tree, handing each entry to a visitor, guarding against symlink
# cycles and a maximum depth; or collect every path below a root.
#
#==============================================================================================
## A symlink cycle was found during the walk.
pub let directory_cycle: ErrorCode = ErrorCode.package(33)
## The walk exceeded its maximum depth.
pub let depth_limit: ErrorCode = ErrorCode.package(34)
## A borrowed traversal callback. For directories, true requests descent and
## false prunes that subtree; the return value is ignored for other entry kinds.
## Path is a NUL-terminated borrowed label, valid only during this callback. Copy
## it to retain it. Error-message storage must outlive the walk, as for other
## borrowed Base errors. Callbacks run serially in depth-first enumeration order.
pub interface WalkVisitor:
func visit(path: str, info: Metadata, depth: usize) -> bool!
## Visit root at depth zero, then its descendants, without following directory
## symlinks below root. Root uses ordinary OS path resolution. Labels are built
## from the supplied root; directory renames do not redirect handle-based traversal
## and may leave those labels unusable as OS paths. This is not a filesystem snapshot.
## A child deeper than max_depth reports depth_limit instead of silently skipping
## entries. Repeated ancestor identities report directory_cycle. OS/callback errors
## stop traversal; earlier callback effects remain. All owned resources are cleaned
## up on failure. Storage is proportional to depth plus the longest path label;
## cycle detection compares each descended directory with its open ancestors.
pub func walk_with(root: c.str, visitor: WalkVisitor, max_depth: usize = 64) -> !:
let owner = memory.allocator
let root_info = try metadata(root)
let descend = try visitor.visit((str)root, root_info, 0)
if root_info.kind != FileKind.directory or not descend:
return
var state = try WalkState.start(root, root_info, owner)
defer state.destroy()
while state.count > 0:
let index = state.count - 1
let next_name = try state.frames[index].directory.next()
if next_name == none:
try state.pop()
continue
let name = next_name else continue
let depth = state.count
if depth > max_depth:
error(depth_limit, "directory traversal exceeded its depth limit")
let info = try state.frames[index].directory.entry_metadata((c.str)name, false)
let parent_length = state.path.length()
if parent_length > 0 and state.path.view()[parent_length - 1] != '/':
try state.path.put_byte('/')
try state.path.put_text(name)
# NUL-terminated, so a visitor may hand the path to C as it is
let visit_children = try visitor.visit((str)try state.path.terminated(), info, depth)
if info.kind != FileKind.directory or not visit_children:
state.path.truncate(parent_length)
continue
if state.contains(info.device, info.inode):
error(directory_cycle, "directory traversal encountered an ancestor again")
var child = try state.frames[index].directory.open_directory((c.str)name, false)
errdefer child.destroy()
let opened = try child.metadata()
if opened.device != info.device or opened.inode != info.inode:
error(failed, "a directory changed before traversal could enter it")
try state.push(child, opened)
## Every entry below `root`, as paths relative to it joined by `/`, sorted by bytes:
## directories are listed and entered, symlinks listed but not followed. The result owns
## its texts, as `list`'s does. Limits and failures are walk_with's.
pub func walk(root: c.str, max_depth: usize = 64) -> interop.Owned[const str[]]!:
let label = (str)root
let skipped = label.length if label.length > 0 and label.bytes[label.length - 1] == '/' else label.length + 1
var collected = Collected(skipped = skipped)
errdefer collected.names.release()
try walk_with(root, &collected, max_depth)
sort.sort(collected.names.view())
return try collected.names.finish()
## The paths walk collects, relative to the root.
struct Collected: WalkVisitor:
var names: owned.Gathered
var skipped: usize
func visit(path: str, info: Metadata, depth: usize) -> bool!:
if depth > 0:
try self.names.add((str)path.bytes[self.skipped..])
return true
struct WalkFrame:
var directory: Directory
var device: u64
var inode: u64
var path_length: usize
## Frames own open directories; one builder owns the current path. No borrowed
## frame pointer survives growth, and the allocator is independent of callback
## changes to memory.allocator.
struct WalkState:
var frames: WalkFrame[]
var count: usize
var path: collections.Buffer
var owner: memory.Allocator
static func start(root: c.str, expected: Metadata, owner: memory.Allocator) -> WalkState!:
var directory = try Directory.open(root)
errdefer directory.destroy()
let info = try directory.metadata()
if info.device != expected.device or info.inode != expected.inode:
error(failed, "the traversal root changed before it could be opened")
with owner:
var path: collections.Buffer
errdefer path.destroy()
try path.put_text((str)root)
let frames = try new WalkFrame[8] ---
frames[0] = WalkFrame(directory = directory, device = info.device, inode = info.inode,
path_length = path.length())
return WalkState(frames = frames, count = 1, path = path, owner = owner)
func contains(device: u64, inode: u64) -> bool:
for frame in self.frames[..<self.count]:
if frame.device == device and frame.inode == inode:
return true
return false
## Ownership transfers only after growth succeeds. The caller closes child
## on failure; after success this frame is its sole owner.
func push(child: Directory, info: Metadata) -> !:
if self.count == self.frames.length:
let capacity = self.frames.length *? 2 else error(memory.exhausted, "the traversal stack is too large")
with self.owner:
let grown = try new WalkFrame[capacity] ---
memory.copy(grown, self.frames, self.count)
free(self.frames)
self.frames = grown
self.frames[self.count] = WalkFrame(directory = child, device = info.device, inode = info.inode,
path_length = self.path.length())
self.count += 1
func pop() -> !:
let index = self.count - 1
self.frames[index].directory.close() catch failure:
self.count -= 1
error(failure.code, failure.message)
self.count -= 1
if self.count > 0:
self.path.truncate(self.frames[self.count - 1].path_length)
func destroy():
while self.count > 0:
self.count -= 1
self.frames[self.count].directory.destroy()
self.path.destroy()
if self.frames.length > 0:
free(self.frames) in self.owner
var empty: WalkFrame[]
self.frames = empty