use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::path::{Path, PathBuf};
use std::time::SystemTime;
use serde::{Deserialize, Serialize};
use crate::config::schema::WikiLinkConfig;
use crate::doc::links::{self, LinkKind};
use crate::doc::outline::slugify;
pub const CACHE_VERSION: u32 = 1;
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct IndexedLink {
pub target: String,
pub wiki: bool,
pub line: usize,
pub context: String,
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct FileEntry {
pub mtime: u64,
pub size: u64,
pub links: Vec<IndexedLink>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Backlink {
pub source: PathBuf,
pub line: usize,
pub context: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WikiResolution {
Found {
path: PathBuf,
anchor: Option<String>,
},
Ambiguous {
candidates: Vec<PathBuf>,
anchor: Option<String>,
},
Missing {
page: String,
anchor: Option<String>,
},
}
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct IndexCache {
pub version: u32,
pub files: BTreeMap<PathBuf, FileEntry>,
}
#[derive(Debug, Default)]
pub struct Index {
files: BTreeMap<PathBuf, FileEntry>,
by_stem: HashMap<String, BTreeSet<PathBuf>>,
pub indexed: usize,
pub total: Option<usize>,
pub ready: bool,
}
impl Index {
pub fn new() -> Self {
Index::default()
}
pub fn from_cache(cache: IndexCache) -> Self {
if cache.version != CACHE_VERSION {
return Index::new();
}
let mut index = Index {
indexed: cache.files.len(),
files: cache.files,
..Index::new()
};
index.rebuild_stems();
index
}
pub fn to_cache(&self) -> IndexCache {
IndexCache {
version: CACHE_VERSION,
files: self.files.clone(),
}
}
pub fn len(&self) -> usize {
self.files.len()
}
pub fn is_empty(&self) -> bool {
self.files.is_empty()
}
pub fn is_current(&self, path: &Path, mtime: Option<SystemTime>, size: u64) -> bool {
let Some(entry) = self.files.get(path) else {
return false;
};
entry.size == size && entry.mtime == seconds(mtime)
}
pub fn insert(&mut self, path: PathBuf, entry: FileEntry) {
if let Some(stem) = stem_of(&path) {
self.by_stem.entry(stem).or_default().insert(path.clone());
}
self.files.insert(path, entry);
self.indexed = self.files.len();
}
pub fn remove(&mut self, path: &Path) {
self.files.remove(path);
if let Some(stem) = stem_of(path) {
if let Some(paths) = self.by_stem.get_mut(&stem) {
paths.remove(path);
if paths.is_empty() {
self.by_stem.remove(&stem);
}
}
}
self.indexed = self.files.len();
}
pub fn retain_paths(&mut self, live: &BTreeSet<PathBuf>) {
let gone: Vec<PathBuf> = self
.files
.keys()
.filter(|path| !live.contains(*path))
.cloned()
.collect();
for path in gone {
self.remove(&path);
}
}
pub fn backlinks(&self, target: &Path, config: &WikiLinkConfig) -> Vec<Backlink> {
let mut out = Vec::new();
for (source, entry) in &self.files {
for link in &entry.links {
let points_here = if link.wiki {
matches!(
self.resolve_wiki(&link.target, source, config),
WikiResolution::Found { ref path, .. } if path == target
)
} else {
self.resolve_relative(&link.target, source).as_deref() == Some(target)
};
if points_here {
out.push(Backlink {
source: source.clone(),
line: link.line,
context: link.context.clone(),
});
}
}
}
out
}
fn resolve_relative(&self, target: &str, source: &Path) -> Option<PathBuf> {
if target.is_empty() || links::is_external(target) {
return None;
}
let path = target.split('#').next().unwrap_or("");
if path.is_empty() {
return None;
}
let dir = source.parent().unwrap_or(Path::new(""));
let joined = links::normalise(&dir.join(path.replace('\\', "/")));
self.files.contains_key(&joined).then_some(joined)
}
pub fn resolve_wiki(
&self,
target: &str,
source: &Path,
config: &WikiLinkConfig,
) -> WikiResolution {
let (page, anchor) = match target.split_once('#') {
Some((page, heading)) => (page.trim(), Some(slugify(heading))),
None => (target.trim(), None),
};
let by_path = || self.by_relative_path(page, source, config);
let by_name = || self.by_filename(page, config);
let candidates =
if config.resolution == crate::config::schema::WikiResolutionOrder::PathFirst {
by_path().or_else(by_name)
} else {
by_name().or_else(by_path)
};
match candidates {
Some(mut candidates) if candidates.len() == 1 => WikiResolution::Found {
path: candidates.remove(0),
anchor,
},
Some(candidates) => WikiResolution::Ambiguous { candidates, anchor },
None => WikiResolution::Missing {
page: page.to_string(),
anchor,
},
}
}
fn by_relative_path(
&self,
page: &str,
source: &Path,
config: &WikiLinkConfig,
) -> Option<Vec<PathBuf>> {
let dir = source.parent().unwrap_or(Path::new(""));
for base in [Path::new(""), dir] {
for candidate in self.with_extensions(&base.join(page), config) {
if self.files.contains_key(&candidate) {
return Some(vec![candidate]);
}
}
}
None
}
fn by_filename(&self, page: &str, config: &WikiLinkConfig) -> Option<Vec<PathBuf>> {
let name = Path::new(page).file_name()?.to_str()?;
let paths = self.by_stem.get(&name.to_lowercase())?;
let exact: Vec<PathBuf> = paths
.iter()
.filter(|path| path.file_stem().and_then(|s| s.to_str()) == Some(name))
.filter(|path| self.has_wiki_extension(path, config))
.cloned()
.collect();
if !exact.is_empty() {
return Some(exact);
}
let folded: Vec<PathBuf> = paths
.iter()
.filter(|path| self.has_wiki_extension(path, config))
.cloned()
.collect();
(!folded.is_empty()).then_some(folded)
}
fn with_extensions(&self, base: &Path, config: &WikiLinkConfig) -> Vec<PathBuf> {
let mut out = Vec::with_capacity(config.extensions.len() + 1);
if base
.extension()
.and_then(|e| e.to_str())
.is_some_and(|e| config.extensions.iter().any(|k| k.eq_ignore_ascii_case(e)))
{
out.push(base.to_path_buf());
}
for extension in &config.extensions {
let mut with = base.as_os_str().to_os_string();
with.push(".");
with.push(extension);
out.push(PathBuf::from(with));
}
out
}
fn has_wiki_extension(&self, path: &Path, config: &WikiLinkConfig) -> bool {
path.extension()
.and_then(|e| e.to_str())
.is_some_and(|e| config.extensions.iter().any(|k| k.eq_ignore_ascii_case(e)))
}
fn rebuild_stems(&mut self) {
self.by_stem.clear();
for path in self.files.keys() {
if let Some(stem) = stem_of(path) {
self.by_stem.entry(stem).or_default().insert(path.clone());
}
}
}
}
pub fn entry_for(source: &str, mtime: Option<SystemTime>, size: u64) -> FileEntry {
let mut line_starts = vec![0usize];
line_starts.extend(source.match_indices('\n').map(|(at, _)| at + 1));
let links = links::extract(source)
.into_iter()
.map(|link| {
let line = match line_starts.binary_search(&link.range.start) {
Ok(at) => at,
Err(at) => at - 1,
};
let end = line_starts
.get(line + 1)
.map_or(source.len(), |next| next - 1);
IndexedLink {
target: link.target,
wiki: link.kind == LinkKind::Wiki,
line: line + 1,
context: source[line_starts[line]..end].trim().to_string(),
}
})
.collect();
FileEntry {
mtime: seconds(mtime),
size,
links,
}
}
fn seconds(mtime: Option<SystemTime>) -> u64 {
mtime
.and_then(|t| t.duration_since(SystemTime::UNIX_EPOCH).ok())
.map_or(0, |d| d.as_secs())
}
fn stem_of(path: &Path) -> Option<String> {
Some(path.file_stem()?.to_str()?.to_lowercase())
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum IndexEvent {
Indexed(Vec<(PathBuf, FileEntry)>),
Finished,
}
const INDEX_BATCH: usize = 64;
#[derive(Debug)]
pub struct IndexHandle {
cancelled: std::sync::Arc<std::sync::atomic::AtomicBool>,
}
impl IndexHandle {
pub fn cancel(&self) {
self.cancelled
.store(true, std::sync::atomic::Ordering::Relaxed);
}
}
impl Drop for IndexHandle {
fn drop(&mut self) {
self.cancel();
}
}
pub fn spawn(
root: PathBuf,
files: Vec<PathBuf>,
sink: impl Fn(IndexEvent) + Send + Sync + 'static,
) -> IndexHandle {
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
let cancelled = Arc::new(AtomicBool::new(false));
let flag = Arc::clone(&cancelled);
let sink = Arc::new(sink);
let thread_sink = Arc::clone(&sink);
let spawned = std::thread::Builder::new()
.name("perga-indexer".to_string())
.spawn(move || {
let mut batch = Vec::with_capacity(INDEX_BATCH);
for path in files {
if flag.load(Ordering::Relaxed) {
return;
}
if let Some(entry) = read_entry(&root.join(&path)) {
batch.push((path, entry));
}
if batch.len() >= INDEX_BATCH {
thread_sink(IndexEvent::Indexed(std::mem::take(&mut batch)));
batch.reserve(INDEX_BATCH);
}
}
if flag.load(Ordering::Relaxed) {
return;
}
if !batch.is_empty() {
thread_sink(IndexEvent::Indexed(batch));
}
thread_sink(IndexEvent::Finished);
});
if spawned.is_err() {
sink(IndexEvent::Finished);
}
IndexHandle { cancelled }
}
fn read_entry(path: &Path) -> Option<FileEntry> {
let bytes = std::fs::read(path).ok()?;
let metadata = std::fs::metadata(path).ok();
let source = String::from_utf8_lossy(&bytes);
Some(entry_for(
&source,
metadata.as_ref().and_then(|m| m.modified().ok()),
metadata.as_ref().map_or(0, |m| m.len()),
))
}
pub fn cache_path(root: &Path) -> Option<PathBuf> {
let dirs = directories::ProjectDirs::from("", "", "perga")?;
Some(
dirs.cache_dir()
.join(format!("{:016x}", hash_of_path(root)))
.join("index.bin"),
)
}
pub fn load_cache(root: &Path) -> Option<IndexCache> {
let bytes = std::fs::read(cache_path(root)?).ok()?;
postcard::from_bytes(&bytes).ok()
}
pub fn save_cache(root: &Path, cache: &IndexCache) -> std::io::Result<()> {
let Some(path) = cache_path(root) else {
return Ok(());
};
if let Some(parent) = path.parent() {
std::fs::create_dir_all(parent)?;
}
let bytes = postcard::to_allocvec(cache)
.map_err(|e| std::io::Error::new(std::io::ErrorKind::InvalidData, e))?;
let temp = path.with_extension("tmp");
std::fs::write(&temp, bytes)?;
std::fs::rename(&temp, &path)
}
fn hash_of_path(path: &Path) -> u64 {
use std::hash::{DefaultHasher, Hash, Hasher};
let mut hasher = DefaultHasher::new();
path.hash(&mut hasher);
hasher.finish()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::config::schema::WikiResolutionOrder;
fn config() -> WikiLinkConfig {
WikiLinkConfig::default()
}
fn index(files: &[(&str, &str)]) -> Index {
let mut index = Index::new();
for (path, source) in files {
index.insert(PathBuf::from(path), entry_for(source, None, 0));
}
index.ready = true;
index
}
#[test]
fn a_unique_filename_resolves_from_anywhere_in_the_vault() {
let index = index(&[("docs/api/auth.md", ""), ("README.md", "[[Auth]]")]);
assert_eq!(
index.resolve_wiki("Auth", Path::new("README.md"), &config()),
WikiResolution::Found {
path: PathBuf::from("docs/api/auth.md"),
anchor: None,
}
);
}
#[test]
fn a_folder_qualified_page_resolves_by_path() {
let index = index(&[
("docs/api/ambiguous.md", ""),
("docs/guides/ambiguous.md", ""),
]);
assert_eq!(
index.resolve_wiki("docs/guides/ambiguous", Path::new("README.md"), &config()),
WikiResolution::Found {
path: PathBuf::from("docs/guides/ambiguous.md"),
anchor: None,
}
);
}
#[test]
fn two_files_with_one_name_are_ambiguous_rather_than_guessed_at() {
let index = index(&[
("docs/api/ambiguous.md", ""),
("docs/guides/ambiguous.md", ""),
]);
let WikiResolution::Ambiguous { candidates, .. } =
index.resolve_wiki("Ambiguous", Path::new("README.md"), &config())
else {
panic!("a silent pick would send the reader to the wrong note");
};
assert_eq!(candidates.len(), 2);
}
#[test]
fn a_heading_fragment_is_slugified_with_the_anchor_slugger() {
let index = index(&[("kurulum.md", "")]);
assert_eq!(
index.resolve_wiki("kurulum#Kurulum Kılavuzu", Path::new("a.md"), &config()),
WikiResolution::Found {
path: PathBuf::from("kurulum.md"),
anchor: Some("kurulum-kılavuzu".to_string()),
}
);
}
#[test]
fn a_page_nobody_has_written_yet_is_missing_not_broken() {
let index = index(&[("README.md", "")]);
assert_eq!(
index.resolve_wiki("Not Yet Written", Path::new("README.md"), &config()),
WikiResolution::Missing {
page: "Not Yet Written".to_string(),
anchor: None,
}
);
}
#[test]
fn case_only_differences_prefer_the_exact_match() {
let index = index(&[("Setup.md", ""), ("notes/setup.md", "")]);
assert_eq!(
index.resolve_wiki("Setup", Path::new("a.md"), &config()),
WikiResolution::Found {
path: PathBuf::from("Setup.md"),
anchor: None,
}
);
}
#[test]
fn a_case_insensitive_match_is_the_last_resort() {
let index = index(&[("docs/Auth.md", "")]);
assert_eq!(
index.resolve_wiki("auth", Path::new("a.md"), &config()),
WikiResolution::Found {
path: PathBuf::from("docs/Auth.md"),
anchor: None,
}
);
}
#[test]
fn filename_first_prefers_the_name_over_the_path() {
let files = [("Page.md", ""), ("sub/Page.md", "")];
let source = Path::new("sub/here.md");
let path_first = index(&files).resolve_wiki("Page", source, &config());
assert_eq!(
path_first,
WikiResolution::Found {
path: PathBuf::from("Page.md"),
anchor: None,
}
);
let config = WikiLinkConfig {
resolution: WikiResolutionOrder::FilenameFirst,
..config()
};
let name_first = index(&files).resolve_wiki("Page", source, &config);
assert!(matches!(name_first, WikiResolution::Ambiguous { .. }));
}
#[test]
fn backlinks_find_both_wiki_and_relative_links() {
let index = index(&[
("docs/api/auth.md", "# Auth"),
("README.md", "See [the API](docs/api/auth.md).\n"),
("notes.md", "Rotate with [[Auth]] every year.\n"),
]);
let mut found = index.backlinks(Path::new("docs/api/auth.md"), &config());
found.sort_by(|a, b| a.source.cmp(&b.source));
assert_eq!(found.len(), 2);
assert_eq!(found[0].source, PathBuf::from("README.md"));
assert_eq!(found[0].line, 1);
assert_eq!(found[0].context, "See [the API](docs/api/auth.md).");
assert_eq!(found[1].source, PathBuf::from("notes.md"));
}
#[test]
fn a_link_on_the_third_line_reports_line_three() {
let entry = entry_for("one\ntwo\nsee [x](y.md) here\n", None, 0);
assert_eq!(entry.links[0].line, 3);
assert_eq!(entry.links[0].context, "see [x](y.md) here");
}
#[test]
fn removing_a_file_marks_inbound_links_broken() {
let mut index = index(&[("target.md", ""), ("source.md", "[[Target]]")]);
assert_eq!(index.backlinks(Path::new("target.md"), &config()).len(), 1);
index.remove(Path::new("target.md"));
assert!(index
.backlinks(Path::new("target.md"), &config())
.is_empty());
assert!(matches!(
index.resolve_wiki("Target", Path::new("source.md"), &config()),
WikiResolution::Missing { .. }
));
}
#[test]
fn a_cache_round_trips_through_postcard() {
let index = index(&[("a.md", "[[B]]"), ("b.md", "[[A]]")]);
let bytes = postcard::to_allocvec(&index.to_cache()).expect("the cache serialises");
let cache: IndexCache = postcard::from_bytes(&bytes).expect("the cache deserialises");
let restored = Index::from_cache(cache);
assert_eq!(restored.len(), 2);
assert_eq!(
restored.resolve_wiki("B", Path::new("a.md"), &config()),
WikiResolution::Found {
path: PathBuf::from("b.md"),
anchor: None,
}
);
}
#[test]
fn a_cache_from_another_version_is_discarded() {
let mut cache = index(&[("a.md", "")]).to_cache();
cache.version = CACHE_VERSION + 1;
assert!(Index::from_cache(cache).is_empty());
}
#[test]
fn a_cached_entry_is_only_current_when_both_mtime_and_size_match() {
let when = SystemTime::UNIX_EPOCH + std::time::Duration::from_secs(1_000);
let mut index = Index::new();
index.insert(PathBuf::from("a.md"), entry_for("x", Some(when), 1));
assert!(index.is_current(Path::new("a.md"), Some(when), 1));
assert!(!index.is_current(Path::new("a.md"), Some(when), 2));
assert!(!index.is_current(Path::new("a.md"), None, 1));
assert!(!index.is_current(Path::new("b.md"), Some(when), 1));
}
#[test]
fn files_the_walk_no_longer_reports_are_dropped() {
let mut index = index(&[("a.md", ""), ("b.md", "")]);
index.retain_paths(&BTreeSet::from([PathBuf::from("a.md")]));
assert_eq!(index.len(), 1);
assert!(matches!(
index.resolve_wiki("b", Path::new("a.md"), &config()),
WikiResolution::Missing { .. }
));
}
}