use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::path::Path;
pub const ROOT_FOLDER: u32 = 0xffff_ffff;
const ROOT_ID: u32 = 1;
#[derive(Clone, Copy, Debug)]
pub struct WalkLimits {
pub max_files: usize,
pub max_depth: usize,
}
impl Default for WalkLimits {
fn default() -> Self {
Self {
max_files: 20_000,
max_depth: 16,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Folder {
pub id: u32,
pub name: String,
pub parent: u32,
pub folders: Vec<u32>,
pub files: Vec<u32>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct File {
pub id: u32,
pub folder: u32,
pub name: String,
pub relative: String,
pub size: u64,
pub container: u8,
}
#[derive(Clone, Debug, Default)]
pub struct FolderTree {
folders: BTreeMap<u32, Folder>,
files: BTreeMap<u32, File>,
by_path: BTreeMap<String, u32>,
truncated: bool,
}
impl FolderTree {
pub fn walk(root: &Path, limits: WalkLimits) -> std::io::Result<Self> {
let mut budget = limits.max_files;
let mut truncated = false;
std::fs::read_dir(root)?;
let scanned = scan(root, "", 0, limits, &mut budget, &mut truncated);
let mut tree = Self {
truncated,
..Self::default()
};
let mut next = ROOT_ID;
tree.number(scanned, String::new(), ROOT_ID, &mut next);
Ok(tree)
}
fn number(&mut self, scanned: Scanned, name: String, parent: u32, next: &mut u32) -> u32 {
let id = *next;
*next = next.saturating_add(1);
let mut folder = Folder {
id,
name,
parent: if id == ROOT_ID { ROOT_ID } else { parent },
folders: Vec::new(),
files: Vec::new(),
};
for found in scanned.files {
let file_id = *next;
*next = next.saturating_add(1);
folder.files.push(file_id);
self.by_path.insert(found.relative.clone(), file_id);
self.files.insert(
file_id,
File {
id: file_id,
folder: id,
name: found.name,
relative: found.relative,
size: found.size,
container: found.container,
},
);
}
for (child_name, child) in scanned.folders {
let child_id = self.number(child, child_name, id, next);
folder.folders.push(child_id);
}
self.folders.insert(id, folder);
id
}
pub fn folder(&self, id: u32) -> Option<&Folder> {
self.folders
.get(&if id == ROOT_FOLDER { ROOT_ID } else { id })
}
pub fn file(&self, id: u32) -> Option<&File> {
self.files.get(&id)
}
pub fn file_by_path(&self, relative: &str) -> Option<&File> {
self.files
.get(self.by_path.get(relative.trim_start_matches('/'))?)
}
pub fn files(&self) -> impl Iterator<Item = &File> {
self.files.values()
}
pub fn file_count(&self) -> usize {
self.files.len()
}
pub fn folder_count(&self) -> usize {
self.folders.len().saturating_sub(1)
}
pub fn is_empty(&self) -> bool {
self.files.is_empty()
}
pub fn is_truncated(&self) -> bool {
self.truncated
}
pub fn index_in_folder(&self, file: u32) -> Option<u32> {
let folder = self.folders.get(&self.files.get(&file)?.folder)?;
let index = folder.files.iter().position(|&id| id == file)?;
u32::try_from(index).ok()
}
pub fn file_by_lookup(&self, name: &[u8]) -> Option<&File> {
let (folder, entry) = parse_lookup_name(name)?;
self.files.get(&entry).filter(|file| file.folder == folder)
}
pub fn lookup_numbers(&self, file: u32) -> Option<(u32, u32)> {
let found = self.files.get(&file)?;
Some((found.folder, found.id))
}
}
pub fn lookup_name(folder: u32, entry: u32) -> Vec<u8> {
let mut name = vec![0x3f, 0x00];
name.extend_from_slice(format!("D {folder:X} {entry:X}").as_bytes());
name
}
pub fn parse_lookup_name(name: &[u8]) -> Option<(u32, u32)> {
let text = std::str::from_utf8(name.strip_prefix(&[0x3f, 0x00])?).ok()?;
let mut words = text.strip_prefix("D ")?.split(' ');
let folder = u32::from_str_radix(words.next()?, 16).ok()?;
let entry = u32::from_str_radix(words.next()?, 16).ok()?;
words.next().is_none().then_some((folder, entry))
}
pub fn container_for(name: &str) -> Option<u8> {
let (_, extension) = name.rsplit_once('.')?;
match extension.to_ascii_lowercase().as_str() {
"mp3" => Some(1),
"m4a" => Some(4),
"wav" => Some(11),
"aif" | "aiff" => Some(12),
_ => None,
}
}
fn is_skipped_directory(name: &str) -> bool {
name.starts_with('.')
|| [
"System Volume Information",
"$RECYCLE.BIN",
"RECYCLER",
"LOST.DIR",
"PIONEER",
"Engine Library",
"_Serato_",
]
.iter()
.any(|skipped| name.eq_ignore_ascii_case(skipped))
}
pub fn collate(left: &str, right: &str) -> Ordering {
let key = |character: char| -> (u8, u32) {
if character.is_ascii_alphabetic() {
(0, u32::from(character.to_ascii_lowercase()))
} else if character.is_ascii_digit() {
(1, u32::from(character))
} else if character.is_ascii() {
(2, u32::from(character))
} else {
(3, u32::from(character))
}
};
left.chars()
.map(key)
.cmp(right.chars().map(key))
.then_with(|| left.cmp(right))
}
#[derive(Debug, Default)]
struct Scanned {
files: Vec<ScannedFile>,
folders: Vec<(String, Scanned)>,
}
#[derive(Debug)]
struct ScannedFile {
name: String,
relative: String,
size: u64,
container: u8,
}
fn scan(
directory: &Path,
relative: &str,
depth: usize,
limits: WalkLimits,
budget: &mut usize,
truncated: &mut bool,
) -> Scanned {
let mut scanned = Scanned::default();
let Ok(listing) = std::fs::read_dir(directory) else {
return scanned;
};
let mut files = Vec::new();
let mut folders = Vec::new();
for entry in listing.flatten() {
let Ok(name) = entry.file_name().into_string() else {
continue;
};
let Ok(kind) = entry.file_type() else {
continue;
};
if kind.is_dir() {
if !is_skipped_directory(&name) {
folders.push(name);
}
} else if kind.is_file()
&& !name.starts_with('.')
&& let Some(container) = container_for(&name)
&& let Ok(metadata) = entry.metadata()
&& metadata.len() > 0
{
files.push(ScannedFile {
relative: join(relative, &name),
name,
size: metadata.len(),
container,
});
}
}
files.sort_by(|left, right| collate(&left.name, &right.name));
folders.sort_by(|left, right| collate(left, right));
for file in files {
if *budget == 0 {
*truncated = true;
break;
}
*budget -= 1;
scanned.files.push(file);
}
if depth < limits.max_depth {
for name in folders {
let below = scan(
&directory.join(&name),
&join(relative, &name),
depth + 1,
limits,
budget,
truncated,
);
if !below.files.is_empty() || !below.folders.is_empty() {
scanned.folders.push((name, below));
}
}
} else if !folders.is_empty() {
*truncated = true;
}
scanned
}
fn join(parent: &str, name: &str) -> String {
if parent.is_empty() {
name.to_owned()
} else {
format!("{parent}/{name}")
}
}
#[cfg(test)]
mod tests {
use super::*;
struct Stick(std::path::PathBuf);
impl Stick {
fn new(name: &str, files: &[(&str, usize)]) -> Self {
let root =
std::env::temp_dir().join(format!("prolink-folder-{name}-{}", std::process::id()));
let _ = std::fs::remove_dir_all(&root);
std::fs::create_dir_all(&root).expect("a scratch directory");
for (path, size) in files {
let full = root.join(path);
if path.ends_with('/') {
std::fs::create_dir_all(&full).expect("a folder");
continue;
}
std::fs::create_dir_all(full.parent().expect("a parent")).expect("its folder");
std::fs::write(&full, vec![0x55u8; *size]).expect("a file");
}
Self(root)
}
}
impl Drop for Stick {
fn drop(&mut self) {
let _ = std::fs::remove_dir_all(&self.0);
}
}
fn names(tree: &FolderTree, folder: u32) -> Vec<String> {
let found = tree.folder(folder).expect("the folder");
found
.folders
.iter()
.map(|id| format!("{}/", tree.folder(*id).expect("a folder").name))
.chain(
found
.files
.iter()
.map(|id| tree.file(*id).expect("a file").name.clone()),
)
.collect()
}
#[test]
fn a_folder_lists_its_folders_then_its_files_in_the_players_order() {
let mut names = vec![
"Zed", "abc", "ABD", "aardvark", "2 two", "1 one", "10 ten", "_under", "!bang",
"(paren", "Éclair", "Äpfel", "日本", "Ωmega",
];
names.sort_by(|left, right| collate(left, right));
assert_eq!(
names,
[
"aardvark", "abc", "ABD", "Zed", "10 ten", "1 one", "2 two", "!bang", "(paren",
"_under", "Äpfel", "Éclair", "Ωmega", "日本",
]
);
}
#[test]
fn the_root_reads_as_on_plainmp3() {
let stick = Stick::new(
"root",
&[
("01 Full v23.mp3", 10),
("SHORT.MP3", 10),
("Filename Artist - Filename Title.mp3", 10),
("Order/a.mp3", 10),
("Deep/L01/b.mp3", 10),
],
);
let tree = FolderTree::walk(&stick.0, WalkLimits::default()).expect("it walks");
assert_eq!(
names(&tree, ROOT_FOLDER),
[
"Deep/",
"Order/",
"Filename Artist - Filename Title.mp3",
"SHORT.MP3",
"01 Full v23.mp3",
]
);
}
#[test]
fn only_what_a_player_can_play_is_listed() {
let stick = Stick::new(
"playable",
&[
("a.mp3", 10),
("b.M4A", 10),
("c.wav", 10),
("d.aif", 10),
("e.AIFF", 10),
("f.flac", 10),
("._a.mp3", 10),
(".hidden.mp3", 10),
("empty.mp3", 0),
("cover.jpg", 10),
("Empty/", 0),
("Only Docs/readme.txt", 10),
("PIONEER/MYSETTING.DAT", 10),
("PIONEER/x.mp3", 10),
("System Volume Information/y.mp3", 10),
(".Trashes/z.mp3", 10),
("Nested/Empty/", 0),
("Nested/Deeper/n.mp3", 10),
],
);
let tree = FolderTree::walk(&stick.0, WalkLimits::default()).expect("it walks");
assert_eq!(
names(&tree, ROOT_FOLDER),
["Nested/", "a.mp3", "b.M4A", "c.wav", "d.aif", "e.AIFF"]
);
let nested = tree.folder(ROOT_FOLDER).expect("root").folders[0];
assert_eq!(
names(&tree, nested),
["Deeper/"],
"its empty folder is left out"
);
assert_eq!(tree.file_count(), 6);
assert_eq!(tree.folder_count(), 2);
}
#[test]
fn ids_are_one_space_counted_depth_first() {
let stick = Stick::new(
"ids",
&[
("x.mp3", 10),
("y.mp3", 10),
("A/p.mp3", 10),
("B/q.mp3", 10),
],
);
let tree = FolderTree::walk(&stick.0, WalkLimits::default()).expect("it walks");
let root = tree.folder(ROOT_FOLDER).expect("root");
assert_eq!(root.id, 1);
assert_eq!(root.files, [2, 3], "the root's files first");
assert_eq!(root.folders, [4, 6], "then each folder, its files after it");
assert_eq!(tree.file(5).expect("A's file").relative, "A/p.mp3");
assert_eq!(tree.file_by_path("/A/p.mp3").map(|file| file.id), Some(5));
assert_eq!(tree.file_by_path("A/p.mp3").map(|file| file.id), Some(5));
assert_eq!(tree.file_by_path("A/q.mp3"), None);
assert_eq!(tree.file(7).expect("B's file").folder, 6);
assert_eq!(tree.index_in_folder(3), Some(1));
let again = FolderTree::walk(&stick.0, WalkLimits::default()).expect("it walks");
assert_eq!(again.file(5), tree.file(5));
}
#[test]
fn a_player_opens_a_file_by_its_two_numbers() {
assert_eq!(
lookup_name(2, 5),
[0x3f, 0x00, 0x44, 0x20, 0x32, 0x20, 0x35]
);
assert_eq!(&lookup_name(0x578, 2)[2..], b"D 578 2");
assert_eq!(&lookup_name(0x4fc, 0x11)[2..], b"D 4FC 11");
assert_eq!(
parse_lookup_name(&lookup_name(0x4fc, 0x11)),
Some((0x4fc, 0x11))
);
assert_eq!(parse_lookup_name(b"Contents"), None);
assert_eq!(parse_lookup_name(&[0x3f, 0x00, b'D', b' ', b'2']), None);
let stick = Stick::new("lookup", &[("A/p.mp3", 10)]);
let tree = FolderTree::walk(&stick.0, WalkLimits::default()).expect("it walks");
let (folder, entry) = tree.lookup_numbers(3).expect("the file");
assert_eq!((folder, entry), (2, 3));
assert_eq!(
tree.file_by_lookup(&lookup_name(folder, entry))
.map(|file| file.relative.as_str()),
Some("A/p.mp3")
);
assert_eq!(
tree.file_by_lookup(&lookup_name(1, entry)),
None,
"another folder's"
);
}
#[test]
fn a_walk_stops_at_its_limits_and_says_so() {
let stick = Stick::new(
"limits",
&[
("a.mp3", 10),
("b.mp3", 10),
("c.mp3", 10),
("D1/D2/d.mp3", 10),
],
);
let tree = FolderTree::walk(
&stick.0,
WalkLimits {
max_files: 2,
max_depth: 16,
},
)
.expect("it walks");
assert_eq!(tree.file_count(), 2);
assert!(tree.is_truncated());
let shallow = FolderTree::walk(
&stick.0,
WalkLimits {
max_files: 100,
max_depth: 1,
},
)
.expect("it walks");
assert_eq!(shallow.file_count(), 3, "D2 is past the depth");
assert!(shallow.is_truncated());
}
}