use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::rc::Rc;
use crate::bib::{Aux, Bib, Entry};
use crate::bst::{Command, Style, Token};
#[derive(Debug, Clone)]
enum Val {
Int(i64),
Str(String),
Fun(Rc<Vec<Token>>),
Missing,
}
impl Val {
fn as_int(&self) -> Option<i64> {
match self {
Val::Int(i) => Some(*i),
_ => None,
}
}
fn as_str(&self) -> String {
match self {
Val::Str(s) => s.clone(),
Val::Int(i) => i.to_string(),
_ => String::new(),
}
}
}
#[derive(Debug, Default, Clone)]
struct EntryState {
key: String,
kind: String,
fields: BTreeMap<String, String>,
ints: BTreeMap<String, i64>,
strs: BTreeMap<String, String>,
}
#[derive(Default)]
struct Out {
line: String,
text: String,
}
const MAX_PRINT_LINE: usize = 79;
const MIN_PRINT_LINE: usize = 3;
impl Out {
fn write(&mut self, s: &str) {
self.line.push_str(s);
}
fn newline(&mut self) {
let mut rest: String = self.line.trim_end().to_string();
self.line.clear();
let mut indent = "";
loop {
let full: Vec<char> = format!("{indent}{rest}").chars().collect();
if full.len() <= MAX_PRINT_LINE {
self.text.extend(full);
self.text.push('\n');
return;
}
let mut at = MAX_PRINT_LINE;
while at > MIN_PRINT_LINE && full[at] != ' ' {
at -= 1;
}
if at == MIN_PRINT_LINE {
self.text.extend(full.iter());
self.text.push('\n');
return;
}
self.text.extend(full[..at].iter());
self.text.push('\n');
rest = full[at + 1..].iter().collect();
indent = " ";
}
}
}
pub struct Vm<'a> {
style: &'a Style,
functions: BTreeMap<String, Rc<Vec<Token>>>,
fields: BTreeSet<String>,
entry_ints: BTreeSet<String>,
entry_strs: BTreeSet<String>,
global_ints: BTreeMap<String, i64>,
global_strs: BTreeMap<String, String>,
entries: Vec<EntryState>,
order: Vec<usize>,
current: Option<usize>,
preamble: String,
stack: Vec<Val>,
out: Out,
pub warnings: Vec<String>,
trace: Option<Trace>,
}
const PARALLEL_ENTRIES: usize = 256;
const MIN_CHUNK: usize = 64;
#[derive(Default)]
struct Trace {
read_first: BTreeSet<String>,
written: BTreeSet<String>,
}
struct Shared {
fields: BTreeSet<String>,
entry_ints: BTreeSet<String>,
entry_strs: BTreeSet<String>,
global_ints: BTreeMap<String, i64>,
global_strs: BTreeMap<String, String>,
preamble: String,
}
struct Ran {
original: Vec<EntryState>,
entries: Vec<EntryState>,
global_ints: BTreeMap<String, i64>,
global_strs: BTreeMap<String, String>,
trace: Trace,
text: String,
line: String,
stack_empty: bool,
warnings: Vec<String>,
}
fn run_chunk(style: &Style, shared: &Shared, body: &[Token], entries: Vec<EntryState>) -> Ran {
let original = entries.clone();
let mut vm = Vm {
style,
functions: functions_of(style),
fields: shared.fields.clone(),
entry_ints: shared.entry_ints.clone(),
entry_strs: shared.entry_strs.clone(),
global_ints: shared.global_ints.clone(),
global_strs: shared.global_strs.clone(),
entries,
order: Vec::new(),
current: None,
preamble: shared.preamble.clone(),
stack: Vec::new(),
out: Out::default(),
warnings: Vec::new(),
trace: Some(Trace::default()),
};
let body = Rc::new(body.to_vec());
for at in 0..vm.entries.len() {
vm.current = Some(at);
vm.execute(body.clone());
}
Ran {
original,
entries: vm.entries,
global_ints: vm.global_ints,
global_strs: vm.global_strs,
trace: vm.trace.unwrap_or_default(),
text: vm.out.text,
line: vm.out.line,
stack_empty: vm.stack.is_empty(),
warnings: vm.warnings,
}
}
fn functions_of(style: &Style) -> BTreeMap<String, Rc<Vec<Token>>> {
let mut functions = BTreeMap::new();
for command in &style.commands {
if let Command::Function { name, body } = command {
functions.insert(name.clone(), Rc::new(body.clone()));
}
}
functions
}
impl<'a> Vm<'a> {
pub fn new(style: &'a Style, db: &Bib, aux: &Aux) -> Vm<'a> {
let mut vm = Vm {
style,
functions: functions_of(style),
fields: BTreeSet::new(),
entry_ints: BTreeSet::new(),
entry_strs: BTreeSet::new(),
global_ints: BTreeMap::new(),
global_strs: BTreeMap::new(),
entries: Vec::new(),
order: Vec::new(),
current: None,
preamble: db.preamble.clone(),
stack: Vec::new(),
out: Out::default(),
warnings: Vec::new(),
trace: None,
};
for command in &style.commands {
match command {
Command::Entry {
fields,
integers,
strings,
} => {
vm.fields
.extend(fields.iter().map(|f| f.to_ascii_lowercase()));
vm.entry_ints.extend(integers.iter().cloned());
vm.entry_strs.extend(strings.iter().cloned());
}
Command::Integers(names) => {
for name in names {
vm.global_ints.insert(name.clone(), 0);
}
}
Command::Strings(names) => {
for name in names {
vm.global_strs.insert(name.clone(), String::new());
}
}
_ => {}
}
}
vm.entry_strs.insert("sort.key$".into());
vm.fields.insert("crossref".into());
let selection = db.select(aux);
let mut cited: HashMap<&str, &Entry> = HashMap::new();
for entry in &selection.cited {
cited.entry(entry.key.as_str()).or_insert(entry);
}
let mut loaded: HashSet<String> = HashSet::new();
for key in &aux.citations {
let Some(entry) = cited.get(key.as_str()) else {
continue;
};
if loaded.insert(entry.key.clone()) {
vm.entries.push(vm.state_of(entry));
}
}
if aux.all {
for entry in &db.entries {
if loaded.insert(entry.key.clone()) {
vm.entries.push(vm.state_of(entry));
}
}
}
for key in &selection.missing {
vm.warnings
.push(format!("I didn't find a database entry for \"{key}\""));
}
vm.resolve_crossrefs(db);
vm.order = (0..vm.entries.len()).collect();
vm
}
fn resolve_crossrefs(&mut self, db: &Bib) {
const MIN_CROSSREFS: usize = 2;
let mut counts: BTreeMap<String, usize> = BTreeMap::new();
for entry in &self.entries {
if let Some(target) = entry.fields.get("crossref") {
*counts.entry(target.trim().to_string()).or_default() += 1;
}
}
let mut by_lower: HashMap<String, &Entry> = HashMap::new();
for entry in &db.entries {
by_lower
.entry(entry.key.to_ascii_lowercase())
.or_insert(entry);
}
let mut listed: HashSet<String> = self
.entries
.iter()
.map(|e| e.key.to_ascii_lowercase())
.collect();
for at in 0..self.entries.len() {
let Some(target) = self.entries[at].fields.get("crossref") else {
continue;
};
let target = target.trim().to_string();
if counts.get(&target).copied().unwrap_or(0) < MIN_CROSSREFS {
continue;
}
let lower = target.to_ascii_lowercase();
if listed.contains(&lower) {
continue;
}
if let Some(found) = by_lower.get(&lower) {
let state = self.state_of(found);
self.entries.push(state);
listed.insert(lower);
}
}
for at in 0..self.entries.len() {
let Some(target) = self.entries[at].fields.get("crossref").cloned() else {
continue;
};
let target = target.trim().to_string();
let lower = target.to_ascii_lowercase();
let parent = by_lower.get(&lower).map(|e| self.state_of(e));
match parent {
Some(parent) => {
for (name, value) in parent.fields {
if name != "crossref" {
self.entries[at].fields.entry(name).or_insert(value);
}
}
}
None => self.warnings.push(format!(
"A bad cross reference---entry \"{}\" refers to entry \"{target}\", which doesn't exist",
self.entries[at].key
)),
}
if !listed.contains(&lower) {
self.entries[at].fields.remove("crossref");
}
}
}
fn state_of(&self, entry: &Entry) -> EntryState {
let mut state = EntryState {
key: entry.key.clone(),
kind: entry.kind.to_ascii_lowercase(),
..EntryState::default()
};
for (name, value) in &entry.fields {
let name = name.to_ascii_lowercase();
if self.fields.contains(&name) {
state.fields.insert(name, value.clone());
}
}
for name in &self.entry_ints {
state.ints.insert(name.clone(), 0);
}
for name in &self.entry_strs {
state.strs.insert(name.clone(), String::new());
}
state
}
pub fn run(&mut self) -> String {
for command in &self.style.commands {
match command {
Command::Execute(body) => {
self.current = None;
self.execute(Rc::new(body.clone()));
}
Command::Iterate(body) => self.iterate(body, false),
Command::Reverse(body) => self.iterate(body, true),
Command::Sort => {
let keys: Vec<String> = self
.entries
.iter()
.map(|e| e.strs["sort.key$"].clone())
.collect();
self.order.sort_by(|&a, &b| keys[a].cmp(&keys[b]));
}
_ => {}
}
}
std::mem::take(&mut self.out.text)
}
fn iterate(&mut self, body: &[Token], reverse: bool) {
let mut order = self.order.clone();
if reverse {
order.reverse();
}
let body = Rc::new(body.to_vec());
let threads = crate::parallel::default_threads().min(order.len() / MIN_CHUNK);
let done = match threads > 1 && order.len() >= PARALLEL_ENTRIES {
true => self.iterate_parallel(&body, &order, threads),
false => 0,
};
for &at in &order[done..] {
self.current = Some(at);
self.execute(body.clone());
}
self.current = None;
}
fn iterate_parallel(
&mut self,
body: &Rc<Vec<Token>>,
order: &[usize],
threads: usize,
) -> usize {
let shared = Shared {
fields: self.fields.clone(),
entry_ints: self.entry_ints.clone(),
entry_strs: self.entry_strs.clone(),
global_ints: self.global_ints.clone(),
global_strs: self.global_strs.clone(),
preamble: self.preamble.clone(),
};
self.trace = Some(Trace::default());
self.current = Some(order[0]);
self.execute(body.clone());
let carried = match &self.trace {
Some(trace) => !trace.read_first.is_disjoint(&trace.written),
None => false,
};
if carried {
self.trace = None;
return 1;
}
let bounds: Vec<usize> = (0..=threads).map(|k| k * order.len() / threads).collect();
let chunks: Vec<Vec<EntryState>> = (1..threads)
.map(|k| {
order[bounds[k]..bounds[k + 1]]
.iter()
.map(|&at| std::mem::take(&mut self.entries[at]))
.collect()
})
.collect();
let style = self.style;
let tokens: &[Token] = body;
let results: Vec<Ran> = std::thread::scope(|scope| {
let workers: Vec<_> = chunks
.into_iter()
.map(|entries| {
let shared = &shared;
scope.spawn(move || run_chunk(style, shared, tokens, entries))
})
.collect();
for &at in &order[1..bounds[1]] {
self.current = Some(at);
self.execute(body.clone());
}
workers
.into_iter()
.map(|worker| worker.join().expect("a bibliography worker panicked"))
.collect()
});
let mut written = self.trace.take().map(|t| t.written).unwrap_or_default();
let mut clean = self.stack.is_empty() && self.out.line.is_empty();
let mut done = bounds[1];
for (k, ran) in results.into_iter().enumerate() {
let positions = &order[bounds[k + 1]..bounds[k + 2]];
let keep = clean && ran.stack_empty && ran.trace.read_first.is_disjoint(&written);
if !keep {
clean = false;
for (&at, entry) in positions.iter().zip(ran.original) {
self.entries[at] = entry;
}
continue;
}
for (&at, entry) in positions.iter().zip(ran.entries) {
self.entries[at] = entry;
}
for name in &ran.trace.written {
if let Some(value) = ran.global_ints.get(name) {
self.global_ints.insert(name.clone(), *value);
} else if let Some(value) = ran.global_strs.get(name) {
self.global_strs.insert(name.clone(), value.clone());
}
}
written.extend(ran.trace.written);
self.out.text.push_str(&ran.text);
self.out.line = ran.line;
self.warnings.extend(ran.warnings);
clean = self.out.line.is_empty();
done = bounds[k + 2];
}
done
}
fn execute(&mut self, body: Rc<Vec<Token>>) {
for token in body.iter() {
match token {
Token::Integer(i) => self.stack.push(Val::Int(*i)),
Token::String(s) => self.stack.push(Val::Str(s.clone())),
Token::Block(body) => self.stack.push(Val::Fun(Rc::new(body.clone()))),
Token::Quoted(name) => match self.functions.get(name) {
Some(body) => self.stack.push(Val::Fun(body.clone())),
None => self
.stack
.push(Val::Fun(Rc::new(vec![Token::Name(name.clone())]))),
},
Token::Name(name) => self.call(name),
}
}
}
fn call(&mut self, name: &str) {
if self.builtin(name) {
return;
}
if let Some(body) = self.functions.get(name).cloned() {
self.execute(body);
return;
}
if let Some(value) = self.global_ints.get(name) {
self.stack.push(Val::Int(*value));
self.note_read(name);
return;
}
if let Some(value) = self.global_strs.get(name) {
self.stack.push(Val::Str(value.clone()));
self.note_read(name);
return;
}
if let Some(at) = self.current {
let entry = &self.entries[at];
if self.fields.contains(name) {
self.stack.push(match entry.fields.get(name) {
Some(value) => Val::Str(value.clone()),
None => Val::Missing,
});
return;
}
if let Some(value) = entry.ints.get(name) {
self.stack.push(Val::Int(*value));
return;
}
if let Some(value) = entry.strs.get(name) {
self.stack.push(Val::Str(value.clone()));
return;
}
}
self.warnings.push(format!("I couldn't execute {name}"));
}
fn note_read(&mut self, name: &str) {
if let Some(trace) = &mut self.trace {
if !trace.written.contains(name) && !trace.read_first.contains(name) {
trace.read_first.insert(name.to_string());
}
}
}
fn note_write(&mut self, name: String) {
if let Some(trace) = &mut self.trace {
trace.written.insert(name);
}
}
fn pop(&mut self) -> Val {
self.stack.pop().unwrap_or(Val::Missing)
}
fn pop_str(&mut self) -> String {
self.pop().as_str()
}
fn pop_int(&mut self) -> i64 {
self.pop().as_int().unwrap_or(0)
}
fn pop_fun(&mut self) -> Rc<Vec<Token>> {
match self.pop() {
Val::Fun(body) => body,
_ => Rc::new(Vec::new()),
}
}
fn assign(&mut self, target: &Rc<Vec<Token>>, value: Val) {
let Some(Token::Name(name)) = target.first() else {
return;
};
let name = name.clone();
if let Some(slot) = self.global_ints.get_mut(&name) {
*slot = value.as_int().unwrap_or(0);
self.note_write(name);
return;
}
if let Some(slot) = self.global_strs.get_mut(&name) {
*slot = value.as_str();
self.note_write(name);
return;
}
if let Some(at) = self.current {
if let Some(slot) = self.entries[at].ints.get_mut(&name) {
*slot = value.as_int().unwrap_or(0);
return;
}
if let Some(slot) = self.entries[at].strs.get_mut(&name) {
*slot = value.as_str();
return;
}
}
self.warnings.push(format!("{name} is not a variable"));
}
fn builtin(&mut self, name: &str) -> bool {
match name {
">" | "<" => {
let b = self.pop_int();
let a = self.pop_int();
let yes = match name {
">" => a > b,
_ => a < b,
};
self.stack.push(Val::Int(yes as i64));
}
"=" => {
let b = self.pop();
let a = self.pop();
let same = match (&a, &b) {
(Val::Int(a), Val::Int(b)) => a == b,
_ => a.as_str() == b.as_str(),
};
self.stack.push(Val::Int(same as i64));
}
"+" | "-" => {
let b = self.pop_int();
let a = self.pop_int();
self.stack.push(Val::Int(match name {
"+" => a + b,
_ => a - b,
}));
}
"*" => {
let b = self.pop_str();
let a = self.pop_str();
self.stack.push(Val::Str(a + &b));
}
":=" => {
let target = self.pop_fun();
let value = self.pop();
self.assign(&target, value);
}
"add.period$" => {
let s = self.pop_str();
self.stack.push(Val::Str(add_period(&s)));
}
"call.type$" => {
let kind = match self.current {
Some(at) => self.entries[at].kind.clone(),
None => String::new(),
};
let which = match self.functions.contains_key(&kind) {
true => kind,
false => "default.type".to_string(),
};
if let Some(body) = self.functions.get(&which).cloned() {
self.execute(body);
}
}
"change.case$" => {
let how = self.pop_str();
let s = self.pop_str();
self.stack.push(Val::Str(change_case(&s, &how)));
}
"chr.to.int$" => {
let s = self.pop_str();
let mut chars = s.chars();
match (chars.next(), chars.next()) {
(Some(c), None) => self.stack.push(Val::Int(c as i64)),
_ => {
self.warnings
.push(format!("\"{s}\" isn't a single character"));
self.stack.push(Val::Int(0));
}
}
}
"entry.max$" => self.stack.push(Val::Int(500)),
"global.max$" => self.stack.push(Val::Int(200_000)),
"cite$" => {
let key = match self.current {
Some(at) => self.entries[at].key.clone(),
None => String::new(),
};
self.stack.push(Val::Str(key));
}
"duplicate$" => {
let top = self.pop();
self.stack.push(top.clone());
self.stack.push(top);
}
"empty$" => {
let top = self.pop();
let empty = match &top {
Val::Missing => true,
other => other.as_str().trim().is_empty(),
};
self.stack.push(Val::Int(empty as i64));
}
"format.name$" => {
let format = self.pop_str();
let which = self.pop_int();
let names = self.pop_str();
self.stack
.push(Val::Str(format_name(&names, which, &format)));
}
"if$" => {
let no = self.pop_fun();
let yes = self.pop_fun();
let test = self.pop_int();
self.execute(match test > 0 {
true => yes,
false => no,
});
}
"int.to.chr$" => {
let i = self.pop_int();
let c = u32::try_from(i)
.ok()
.and_then(char::from_u32)
.unwrap_or('\0');
self.stack.push(Val::Str(c.to_string()));
}
"int.to.str$" => {
let i = self.pop_int();
self.stack.push(Val::Str(i.to_string()));
}
"missing$" => {
let top = self.pop();
self.stack
.push(Val::Int(matches!(top, Val::Missing) as i64));
}
"newline$" => self.out.newline(),
"num.names$" => {
let s = self.pop_str();
self.stack.push(Val::Int(split_names(&s).len() as i64));
}
"pop$" => {
self.pop();
}
"preamble$" => {
let preamble = self.preamble.clone();
self.stack.push(Val::Str(preamble));
}
"purify$" => {
let s = self.pop_str();
self.stack.push(Val::Str(purify(&s)));
}
"quote$" => self.stack.push(Val::Str("\"".into())),
"skip$" => {}
"stack$" => {
let stack = std::mem::take(&mut self.stack);
for value in stack.iter().rev() {
self.warnings.push(format!("{value:?}"));
}
}
"substring$" => {
let len = self.pop_int();
let start = self.pop_int();
let s = self.pop_str();
self.stack.push(Val::Str(substring(&s, start, len)));
}
"swap$" => {
let b = self.pop();
let a = self.pop();
self.stack.push(b);
self.stack.push(a);
}
"text.length$" => {
let s = self.pop_str();
self.stack.push(Val::Int(text_length(&s) as i64));
}
"text.prefix$" => {
let len = self.pop_int();
let s = self.pop_str();
self.stack.push(Val::Str(text_prefix(&s, len)));
}
"top$" => {
let top = self.pop();
self.warnings.push(format!("{top:?}"));
}
"type$" => {
let kind = match self.current {
Some(at) => self.entries[at].kind.clone(),
None => String::new(),
};
self.stack
.push(Val::Str(match self.functions.contains_key(&kind) {
true => kind,
false => String::new(),
}));
}
"warning$" => {
let s = self.pop_str();
self.warnings.push(s);
}
"while$" => {
let body = self.pop_fun();
let test = self.pop_fun();
for _ in 0..1_000_000 {
self.execute(test.clone());
if self.pop_int() <= 0 {
return true;
}
self.execute(body.clone());
}
self.warnings.push("a while$ loop did not finish".into());
}
"width$" => {
let s = self.pop_str();
self.stack.push(Val::Int(width(&s)));
}
"write$" => {
let s = self.pop_str();
self.out.write(&s);
}
_ => return false,
}
true
}
}
pub fn run(aux: &Aux, style: &Style, db: &Bib) -> (String, Vec<String>) {
let mut vm = Vm::new(style, db, aux);
let bbl = vm.run();
(bbl, std::mem::take(&mut vm.warnings))
}
fn is_special(chars: &[char], at: usize) -> bool {
chars.get(at) == Some(&'{') && chars.get(at + 1) == Some(&'\\')
}
fn cs_end(chars: &[char], at: usize) -> usize {
let mut i = at + 1;
match chars.get(i) {
Some(c) if c.is_ascii_alphabetic() => {
while chars.get(i).is_some_and(|c| c.is_ascii_alphabetic()) {
i += 1;
}
}
Some(_) => i += 1,
None => {}
}
i
}
fn group_end(chars: &[char], at: usize) -> usize {
let mut depth = 0usize;
let mut i = at;
while i < chars.len() {
match chars[i] {
'{' => depth += 1,
'}' => {
depth -= 1;
if depth == 0 {
return i;
}
}
_ => {}
}
i += 1;
}
chars.len()
}
fn add_period(s: &str) -> String {
for c in s.chars().rev() {
match c {
'}' => continue,
'.' | '!' | '?' => return s.to_string(),
_ => break,
}
}
format!("{s}.")
}
fn text_length(s: &str) -> usize {
let chars: Vec<char> = s.chars().collect();
let mut n = 0usize;
let mut i = 0usize;
while i < chars.len() {
if is_special(&chars, i) {
i = group_end(&chars, i) + 1;
n += 1;
continue;
}
if chars[i] != '{' && chars[i] != '}' {
n += 1;
}
i += 1;
}
n
}
fn text_prefix(s: &str, len: i64) -> String {
if len <= 0 {
return String::new();
}
let chars: Vec<char> = s.chars().collect();
let mut out = String::new();
let mut n = 0i64;
let mut depth = 0usize;
let mut i = 0usize;
while i < chars.len() && n < len {
if is_special(&chars, i) {
let end = group_end(&chars, i);
out.extend(&chars[i..=end.min(chars.len() - 1)]);
i = end + 1;
n += 1;
continue;
}
match chars[i] {
'{' => depth += 1,
'}' => depth = depth.saturating_sub(1),
_ => n += 1,
}
out.push(chars[i]);
i += 1;
}
for _ in 0..depth {
out.push('}');
}
out
}
fn substring(s: &str, start: i64, len: i64) -> String {
let chars: Vec<char> = s.chars().collect();
let n = chars.len() as i64;
if len <= 0 || start == 0 {
return String::new();
}
let (from, to) = match start > 0 {
true => (start - 1, start - 1 + len),
false => {
let end = n + start + 1;
(end - len, end)
}
};
let from = from.clamp(0, n) as usize;
let to = to.clamp(0, n) as usize;
chars[from..to.max(from)].iter().collect()
}
fn purify(s: &str) -> String {
let chars: Vec<char> = s.chars().collect();
let mut out = String::new();
let mut i = 0usize;
while i < chars.len() {
if is_special(&chars, i) {
let end = group_end(&chars, i);
let mut j = i + 1;
while j < end {
if chars[j] == '\\' {
j = cs_end(&chars, j).min(end);
continue;
}
if chars[j].is_alphanumeric() {
out.push(chars[j]);
}
j += 1;
}
i = end + 1;
continue;
}
match chars[i] {
c if c.is_alphanumeric() => out.push(c),
' ' | '-' | '~' => out.push(' '),
_ => {}
}
i += 1;
}
out
}
fn change_case(s: &str, how: &str) -> String {
let how = how.chars().next().unwrap_or('t').to_ascii_lowercase();
let chars: Vec<char> = s.chars().collect();
let mut out = String::new();
let mut depth = 0usize;
let mut i = 0usize;
let mut at_start = true;
while i < chars.len() {
if is_special(&chars, i) && depth == 0 {
let end = group_end(&chars, i);
out.push('{');
let mut j = i + 1;
while j < end {
if chars[j] == '\\' {
let stop = cs_end(&chars, j).min(end);
out.extend(&chars[j..stop]);
j = stop;
continue;
}
out.push(convert(chars[j], how, at_start));
j += 1;
}
out.push('}');
i = end + 1;
at_start = false;
continue;
}
match chars[i] {
'{' => {
depth += 1;
out.push('{');
}
'}' => {
depth = depth.saturating_sub(1);
out.push('}');
}
c if depth > 0 => out.push(c),
c => {
out.push(convert(c, how, at_start));
if !c.is_whitespace() {
at_start = c == ':';
}
}
}
if i == 0 {
at_start = false;
}
i += 1;
}
out
}
fn convert(c: char, how: char, protected: bool) -> char {
match how {
'u' => c.to_ascii_uppercase(),
'l' => c.to_ascii_lowercase(),
_ if protected => c,
_ => c.to_ascii_lowercase(),
}
}
fn split_names(s: &str) -> Vec<String> {
let chars: Vec<char> = s.chars().collect();
let mut out = Vec::new();
let mut current = String::new();
let mut depth = 0usize;
let mut i = 0usize;
while i < chars.len() {
match chars[i] {
'{' => depth += 1,
'}' => depth = depth.saturating_sub(1),
_ => {}
}
if depth == 0
&& chars[i].is_whitespace()
&& chars
.get(i + 1..i + 4)
.map(|w| w.iter().collect::<String>().eq_ignore_ascii_case("and"))
== Some(true)
&& chars.get(i + 4).is_some_and(|c| c.is_whitespace())
{
out.push(current.trim().to_string());
current.clear();
i += 5;
continue;
}
current.push(chars[i]);
i += 1;
}
if !current.trim().is_empty() {
out.push(current.trim().to_string());
}
out
}
#[derive(Debug, Default, PartialEq)]
struct Name {
first: Vec<String>,
von: Vec<String>,
last: Vec<String>,
jr: Vec<String>,
}
fn first_letter(token: &str) -> Option<char> {
let chars: Vec<char> = token.chars().collect();
let mut i = 0usize;
let mut depth = 0usize;
while i < chars.len() {
match chars[i] {
'{' => {
if chars.get(i + 1) == Some(&'\\') {
let end = group_end(&chars, i);
let mut j = i + 1;
while j < end {
if chars[j] == '\\' {
j = cs_end(&chars, j).min(end);
continue;
}
if chars[j].is_alphabetic() {
return Some(chars[j]);
}
j += 1;
}
i = end + 1;
continue;
}
depth += 1;
}
'}' => depth = depth.saturating_sub(1),
c if depth == 0 && c.is_alphabetic() => return Some(c),
_ => {}
}
i += 1;
}
None
}
fn is_von(token: &str) -> bool {
first_letter(token).is_some_and(|c| c.is_lowercase())
}
fn parse_name(name: &str) -> Name {
let chars: Vec<char> = name.chars().collect();
let mut parts: Vec<String> = vec![String::new()];
let mut depth = 0usize;
for &c in &chars {
match c {
'{' => depth += 1,
'}' => depth = depth.saturating_sub(1),
',' if depth == 0 => {
parts.push(String::new());
continue;
}
_ => {}
}
parts.last_mut().expect("a part").push(c);
}
let tokens = |s: &str| -> Vec<String> {
let mut out: Vec<String> = Vec::new();
let mut current = String::new();
let mut depth = 0usize;
for c in s.chars() {
match c {
'{' => depth += 1,
'}' => depth = depth.saturating_sub(1),
c if c.is_whitespace() && depth == 0 => {
if !current.is_empty() {
out.push(std::mem::take(&mut current));
}
continue;
}
_ => {}
}
current.push(c);
}
if !current.is_empty() {
out.push(current);
}
out
};
let mut out = Name::default();
match parts.len() {
1 => {
let all = tokens(&parts[0]);
let (mut von_start, mut von_end) = (all.len(), all.len());
for (i, token) in all.iter().enumerate() {
if i + 1 < all.len() && is_von(token) {
if von_start == all.len() {
von_start = i;
}
von_end = i + 1;
}
}
match von_start < all.len() {
true => {
out.first = all[..von_start].to_vec();
out.von = all[von_start..von_end].to_vec();
out.last = all[von_end..].to_vec();
}
false => {
let split = all.len().saturating_sub(1);
out.first = all[..split].to_vec();
out.last = all[split..].to_vec();
}
}
}
_ => {
let head = tokens(&parts[0]);
let mut von_end = 0usize;
for (i, token) in head.iter().enumerate() {
if i + 1 < head.len() && is_von(token) {
von_end = i + 1;
}
}
out.von = head[..von_end].to_vec();
out.last = head[von_end..].to_vec();
match parts.len() {
2 => out.first = tokens(&parts[1]),
_ => {
out.jr = tokens(&parts[1]);
out.first = tokens(&parts[2]);
}
}
}
}
out
}
fn abbreviate(token: &str, after: &str) -> String {
token
.split('-')
.filter_map(|piece| {
let chars: Vec<char> = piece.chars().collect();
if is_special(&chars, 0) {
let end = group_end(&chars, 0);
let head: String = chars[..=end.min(chars.len() - 1)].iter().collect();
return Some(format!("{head}{after}"));
}
first_letter(piece).map(|c| format!("{c}{after}"))
})
.collect::<Vec<_>>()
.join("-")
}
fn join_tokens(pieces: &[String]) -> String {
let mut out = String::new();
for (i, piece) in pieces.iter().enumerate() {
if i > 0 {
let last = i + 1 == pieces.len();
let after_short_first = i == 1 && text_length(&pieces[0]) < 3;
out.push(match last || after_short_first {
true => '~',
false => ' ',
});
}
out.push_str(piece);
}
out
}
fn format_name(names: &str, which: i64, format: &str) -> String {
let all = split_names(names);
let Some(name) = all.get((which.max(1) - 1) as usize) else {
return String::new();
};
let name = parse_name(name);
let chars: Vec<char> = format.chars().collect();
let mut out = String::new();
let mut i = 0usize;
while i < chars.len() {
if chars[i] != '{' {
out.push(chars[i]);
i += 1;
continue;
}
let end = group_end(&chars, i);
let group: String = chars[i + 1..end.min(chars.len())].iter().collect();
out.push_str(&render_group(&group, &name));
i = end + 1;
}
out
}
fn render_group(group: &str, name: &Name) -> String {
let chars: Vec<char> = group.chars().collect();
let Some(at) = chars.iter().position(|c| "fvljFVLJ".contains(*c)) else {
return group.to_string();
};
let letter = chars[at].to_ascii_lowercase();
let long = chars.get(at + 1).map(|c| c.to_ascii_lowercase()) == Some(letter);
let mut after = at + 1 + long as usize;
let pre: String = chars[..at].iter().collect();
let mut separator: Option<String> = None;
if chars.get(after) == Some(&'{') {
let end = group_end(&chars, after);
separator = Some(chars[after + 1..end.min(chars.len())].iter().collect());
after = end + 1;
}
let post: String = chars[after.min(chars.len())..].iter().collect();
let tokens = match letter {
'f' => &name.first,
'v' => &name.von,
'l' => &name.last,
_ => &name.jr,
};
if tokens.is_empty() {
return String::new();
}
let mut post = post;
let mut ending: Option<char> = None;
if post.ends_with("~~") {
post.pop();
} else if post.ends_with('~') {
post.pop();
ending = Some('~');
}
let pieces: Vec<String> = match long {
true => tokens.iter().map(|t| format!("{t}{post}")).collect(),
false => tokens.iter().map(|t| abbreviate(t, &post)).collect(),
};
let joined = match &separator {
Some(sep) => pieces.join(sep),
None => join_tokens(&pieces),
};
let mut body = format!("{pre}{joined}");
if ending == Some('~') {
body.push(match text_length(&body) < 3 {
true => '~',
false => ' ',
});
}
body
}
fn width(s: &str) -> i64 {
let chars: Vec<char> = s.chars().collect();
let mut total = 0i64;
let mut i = 0usize;
while i < chars.len() {
if is_special(&chars, i) {
let end = group_end(&chars, i);
let mut j = i + 1;
while j < end {
if chars[j] == '\\' {
let start = j + 1;
j = cs_end(&chars, j).min(end);
let cs: String = chars[start..j].iter().collect();
total += symbol_width(&cs);
if cs.chars().all(|c| c.is_ascii_alphabetic()) {
while j < end && chars[j].is_whitespace() {
j += 1;
}
}
continue;
}
if chars[j] != '{' && chars[j] != '}' {
total += char_width(chars[j]);
}
j += 1;
}
i = end + 1;
continue;
}
total += char_width(chars[i]);
i += 1;
}
total
}
fn symbol_width(cs: &str) -> i64 {
match cs {
"aa" => 500,
"AA" => 750,
"ae" => 722,
"AE" => 903,
"o" => 500,
"O" => 778,
"oe" => 778,
"OE" => 1014,
"ss" => 500,
"l" => 278,
"L" => 625,
"i" => 278,
"j" => 306,
_ => 0,
}
}
fn char_width(c: char) -> i64 {
const WIDTHS: [i64; 96] = [
278, 278, 500, 833, 500, 833, 778, 278, 389, 389, 500, 778, 278, 333, 278, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 278, 278, 278, 778, 472, 472, 778, 750, 708, 722, 764, 681, 653, 785, 750, 361, 514, 778, 625, 917, 750, 778, 681, 778, 736, 556, 722, 750, 750, 1028, 750, 750, 611, 278, 500, 278, 500, 278, 278, 500, 556, 444, 556, 444, 306, 500, 556, 278, 306, 528, 278, 833, 556, 500, 556, 528, 392, 394, 389, 556, 528, 722, 528, 528, 444, 500, 1000, 500, 500, 0, ];
match c as usize {
code @ 32..=127 => WIDTHS[code - 32],
_ => 0,
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_string_builtins_do_what_bibtex_does() {
assert_eq!(text_length("{\\ss}"), 1);
assert_eq!(text_length("{\\'a}bc"), 3);
assert_eq!(text_length("{ab}c"), 3);
assert_eq!(text_prefix("{\\'a}bcd", 3), "{\\'a}bc");
assert_eq!(text_prefix("{ab}cd", 3), "{ab}c");
assert_eq!(text_prefix("{ab}cd", 1), "{a}");
assert_eq!(text_prefix("a{bc}d", 2), "a{b}");
assert_eq!(text_prefix("ab{cd", 3), "ab{c}");
assert_eq!(text_prefix("{\\'a}bcd", 2), "{\\'a}b");
assert_eq!(change_case("aBc {\\'e} DEF", "t"), "abc {\\'e} def");
assert_eq!(change_case("aBc {\\'e} DEF", "u"), "ABC {\\'E} DEF");
assert_eq!(change_case("The {TeX}book", "l"), "the {TeX}book");
assert_eq!(purify("a{\\'e}B{XY}c"), "aeBXYc");
assert_eq!(purify("Knuth, Donald E."), "Knuth Donald E");
assert_eq!(substring("abcdef", 2, 3), "bcd");
assert_eq!(substring("abcdef", -2, 3), "cde");
assert_eq!(substring("abcdef", 1, 100), "abcdef");
assert_eq!(substring("abcdef", 0, 3), "");
assert_eq!(add_period("A title"), "A title.");
assert_eq!(add_period("Who?"), "Who?");
assert_eq!(add_period("{Who?}"), "{Who?}");
assert_eq!(add_period("A title!"), "A title!");
}
#[test]
fn width_measures_what_bibtex_measures() {
assert_eq!(width("A"), 750);
assert_eq!(width("AV"), 1500, "no kerning: BibTeX adds widths");
assert_eq!(width("ff"), 612, "and no ligature either");
assert_eq!(width(" "), 278);
assert_eq!(width("{ab}"), 2056, "a brace is 500 wide");
assert_eq!(width("{\\ss}"), 500);
assert_eq!(width("{\\ss}x"), 1028);
assert_eq!(width("{\\ae}"), 722);
assert_eq!(
width("{\\'a}"),
500,
"an accent is worth nothing, the a 500"
);
assert_eq!(width("{\\relax x}"), 528, "an unknown control sequence too");
assert_eq!(width("{\\ }"), 0);
}
#[test]
fn a_name_is_split_the_way_bibtex_splits_it() {
let name = parse_name("Donald E. Knuth");
assert_eq!(name.first, ["Donald", "E."]);
assert_eq!(name.last, ["Knuth"]);
let name = parse_name("Ludwig van Beethoven");
assert_eq!(name.first, ["Ludwig"]);
assert_eq!(name.von, ["van"]);
assert_eq!(name.last, ["Beethoven"]);
let name = parse_name("de la Vega, Maria");
assert_eq!(name.von, ["de", "la"]);
assert_eq!(name.last, ["Vega"]);
assert_eq!(name.first, ["Maria"]);
let name = parse_name("King, Jr., Martin Luther");
assert_eq!(name.last, ["King"]);
assert_eq!(name.jr, ["Jr."]);
assert_eq!(name.first, ["Martin", "Luther"]);
let name = parse_name("Erd{\\H o}s, P.");
assert_eq!(name.last, ["Erd{\\H o}s"]);
assert_eq!(name.first, ["P."]);
assert_eq!(split_names("{Barnes and Noble, Inc.}").len(), 1);
assert_eq!(split_names("A. One and B. Two and C. Three").len(), 3);
}
#[test]
fn format_name_writes_what_bibtex_writes() {
for (names, format, want) in [
("Donald E. Knuth", "{ff~}{vv~}{ll}{, jj}", "Donald~E. Knuth"),
("Donald E. Knuth", "{f.~}{vv~}{ll}{, jj}", "D.~E. Knuth"),
(
"Ludwig van Beethoven",
"{vv~}{ll}{, jj}{, ff}",
"van Beethoven, Ludwig",
),
(
"de la Vega, Maria",
"{ff~}{vv~}{ll}{, jj}",
"Maria de~la Vega",
),
(
"King, Jr., Martin Luther",
"{ff~}{vv~}{ll}{, jj}",
"Martin~Luther King, Jr.",
),
(
"King, Jr., Martin Luther",
"{vv~}{ll}{, jj}{, f.}",
"King, Jr., M.~L.",
),
("Al Bo", "{ff~}{vv~}{ll}{, jj}", "Al~Bo"),
("Erd{\\H o}s, P.", "{ff~}{vv~}{ll}{, jj}", "P.~Erd{\\H o}s"),
("Jean-Paul Sartre", "{f.~}{vv~}{ll}{, jj}", "J.-P. Sartre"),
(
"Jean Baptiste Pierre Lamarck",
"{ff~}{vv~}{ll}{, jj}",
"Jean Baptiste~Pierre Lamarck",
),
(
"Jean Baptiste Pierre Marie Lamarck",
"{f.~}{ll}",
"J.~B. P.~M. Lamarck",
),
(
"van de la Vega Lopez, Maria",
"{vv~}{ll}",
"van de~la Vega~Lopez",
),
("Aho, Alfred V.", "{v{}}{l{}}", "A"),
("de la Vega, Maria", "{v{}}{l{}}", "dlV"),
(
"{Barnes and Noble, Inc.}",
"{ff~}{vv~}{ll}{, jj}",
"{Barnes and Noble, Inc.}",
),
] {
assert_eq!(
format_name(names, 1, format),
want,
"{names:?} through {format:?}"
);
}
assert_eq!(format_name("A. One and B. Two", 2, "{ll}"), "Two");
assert_eq!(format_name("A. One", 7, "{ll}"), "");
}
#[test]
fn a_long_line_is_broken_where_bibtex_breaks_it() {
let mut out = Out::default();
let words: Vec<String> = (1..30).map(|i| format!("word{i:02}")).collect();
out.write(&words.join(" "));
out.newline();
let lines: Vec<&str> = out.text.lines().collect();
assert_eq!(lines[0].chars().count(), 76);
assert!(lines[1].starts_with(" word12"), "{:?}", lines[1]);
assert!(lines.iter().all(|l| l.chars().count() <= 79));
let mut out = Out::default();
out.write(&"x".repeat(200));
out.newline();
assert_eq!(out.text.trim_end().chars().count(), 200);
let mut out = Out::default();
out.write(" trailing ");
out.newline();
assert_eq!(out.text, " trailing\n");
}
}