1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
//! What the mouth produces: TeX has exactly two kinds of token.
use crate::catcode::Cat;
use once_cell::sync::Lazy;
use rustc_hash::FxHashMap;
use std::sync::RwLock;
/// A control sequence name, interned to a 32-bit id.
///
/// `tex.web` §256 does the same thing and for the same reason: the name is
/// looked up ONCE, in the hash table, and everything after that carries the
/// resulting `eqtb` pointer. A token then costs no allocation, comparing two is
/// an integer compare, and the meaning table is an array index rather than a
/// string hash.
///
/// It matters here because expansion copies token lists constantly -- every
/// macro use clones its body -- and a `String` per control sequence made each
/// copy a run of heap allocations. The names themselves are few (a document has
/// hundreds of distinct control sequences and expands them millions of times),
/// so interning trades a bounded table for an unbounded number of allocations.
#[derive(Clone, Copy)]
pub struct CsId(&'static str);
// Interning makes one canonical `&'static str` per distinct name, so two ids
// for the same name are the same pointer. Comparing and hashing THAT rather
// than the characters is what keeps a meaning lookup cheap: the table hashes a
// pointer, not a string, and `\ifx` compares two words.
impl PartialEq for CsId {
fn eq(&self, other: &Self) -> bool {
std::ptr::eq(self.0.as_ptr(), other.0.as_ptr()) && self.0.len() == other.0.len()
}
}
impl Eq for CsId {}
impl std::hash::Hash for CsId {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
(self.0.as_ptr() as usize).hash(state);
}
}
impl std::fmt::Debug for CsId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "Cs({})", self.0)
}
}
/// The name table. Written once per NEW name and read on every resolve, which
/// is what an `RwLock` is for; the write side is cold after warm-up.
///
/// Names are leaked to `&'static str` deliberately. A control sequence name,
/// once seen, is live for the rest of the run -- the meaning table, every token
/// carrying its id, and every diagnostic can refer to it -- so there is nothing
/// to free and no lifetime to thread through the engine. The set is bounded by
/// the document's DISTINCT control sequences (hundreds), not by how often they
/// are expanded (millions), which is exactly the trade interning exists to make.
struct Names {
to_id: FxHashMap<&'static str, &'static str>,
count: usize,
}
static NAMES: Lazy<RwLock<Names>> = Lazy::new(|| {
RwLock::new(Names {
to_id: FxHashMap::default(),
count: 0,
})
});
/// What the name of a `\noexpand`ed control sequence starts with. The NUL keeps
/// it out of reach of any document.
pub const NOEXPAND_PREFIX: &str = "\u{0}noexpand:";
impl CsId {
/// The id for a name, interning it if this is the first sighting.
///
/// The lock is taken HERE and nowhere else on a hot path: interning happens
/// once per control sequence the mouth reads, while resolving one happens
/// once per expansion -- millions of times. An earlier revision stored an
/// index and resolved it through the table, which put a lock acquire in
/// front of every primitive dispatch and measured 25% SLOWER than the
/// `String` it replaced. Carrying the canonical pointer means resolving is
/// free.
pub fn intern(name: &str) -> CsId {
// A per-thread cache in front of the shared table. The mouth interns
// every control sequence it reads, and a document says `\the` or a
// macro's own name thousands of times, so the overwhelmingly common
// case is a name this thread has already seen. Answering that without
// touching the shared lock is what keeps interning from costing more
// than the `String` it replaced.
thread_local! {
static SEEN: std::cell::RefCell<FxHashMap<Box<str>, &'static str>> =
std::cell::RefCell::new(FxHashMap::default());
}
if let Some(hit) = SEEN.with(|c| c.borrow().get(name).copied()) {
return CsId(hit);
}
let canonical = Self::intern_shared(name);
SEEN.with(|c| c.borrow_mut().insert(name.into(), canonical.0));
canonical
}
/// The shared table, taken only when this thread has not seen the name.
fn intern_shared(name: &str) -> CsId {
if let Some(s) = NAMES.read().expect("names").to_id.get(name) {
return CsId(s);
}
let mut n = NAMES.write().expect("names");
// Re-check: another thread may have interned it between the two locks.
if let Some(s) = n.to_id.get(name) {
return CsId(s);
}
let leaked: &'static str = Box::leak(name.to_string().into_boxed_str());
n.to_id.insert(leaked, leaked);
n.count += 1;
CsId(leaked)
}
/// The name behind an id.
///
/// The id IS the canonical name, so this is a field read -- no lock, no
/// table, no allocation. The primitive dispatch stays a `match` on string
/// literals while tokens stay 16 bytes of `Copy`.
pub fn name(self) -> &'static str {
self.0
}
/// §358's `dont_expand`: the same control sequence as an id that the
/// expander does not see as what it is. A token `\noexpand` passed over is
/// `\relax`-like for whoever reads it next and is itself again when it is
/// stored (`\edef`, an argument, a token list).
pub fn noexpanded(self) -> CsId {
CsId::intern(&format!("{NOEXPAND_PREFIX}{}", self.0))
}
/// The control sequence a [`CsId::noexpanded`] id stands for.
pub fn noexpand_origin(self) -> Option<CsId> {
self.0.strip_prefix(NOEXPAND_PREFIX).map(CsId::intern)
}
/// How many distinct control sequences have been seen. For tests and
/// `--cache-stats`; a document's count is small and bounded.
pub fn interned_count() -> usize {
NAMES.read().expect("names").count
}
}
/// A token, as `tex.web` §289 defines one.
///
/// A character token carries the catcode it had WHEN IT WAS READ, not the
/// current one — that is why `\catcode`\{=1` after a macro was defined does not
/// retroactively change that macro's body. Keeping the pair together is what
/// makes the distinction representable at all.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Token {
Char(char, Cat),
/// A control sequence, stored WITHOUT its escape character, as an interned
/// id rather than a name.
Cs(CsId),
}
impl Token {
/// A control sequence token from a name, interning it.
pub fn cs(name: &str) -> Token {
Token::Cs(CsId::intern(name))
}
/// The name of a control-sequence token, or `None` for a character.
pub fn cs_name(&self) -> Option<&'static str> {
match self {
Token::Cs(id) => Some(id.name()),
Token::Char(..) => None,
}
}
/// Whether this is the named control sequence, without materialising the
/// name: the comparison is against an interned id.
pub fn is_cs(&self, name: &str) -> bool {
matches!(self, Token::Cs(id) if *id == CsId::intern(name))
}
/// The text `\string` and `\message` produce for this token.
///
/// A multi-letter control sequence prints with a trailing space and a
/// single-character one does not (`tex.web` §294's `print_cs`) — the rule
/// that makes `\message{\foo}` read `\foo ` and `\message{\!}` read `\!`.
pub fn to_text(&self, escape: Esc) -> String {
match self {
Token::Char(c, _) => c.to_string(),
Token::Cs(id) => {
let name = id.noexpand_origin().map_or(id.name(), CsId::name);
let single = name.chars().count() == 1;
match single {
true => format!("{escape}{name}"),
false => format!("{escape}{name} "),
}
}
}
}
pub fn is_space(&self) -> bool {
matches!(self, Token::Char(_, Cat::Space))
}
}
/// The character `\escapechar` puts in front of a control sequence's name when
/// it is printed, or none (`tex.web` §63's `print_esc` prints nothing for a
/// value outside 0..255 -- `\escapechar=-1` is how a document asks for a bare
/// name).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Esc(pub Option<char>);
impl Esc {
/// The escape character an `\escapechar` value selects.
pub fn from_code(code: i64) -> Self {
match u8::try_from(code) {
Ok(b) => Esc(Some(char::from(b))),
Err(_) => Esc(None),
}
}
}
impl std::fmt::Display for Esc {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.0 {
Some(c) => write!(f, "{c}"),
None => Ok(()),
}
}
}