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
//! Per-`Console` style interner. **Dormant in v0.11.0-alpha.1.**
//!
//! Foundation for the L2 perf work documented in `.review/V0_11_DESIGN.md`:
//! deduplicate `Style` instances inside a `Console` so `Segment::style`
//! can shrink from `Option<Style>` (~136 B) to a 4-byte `StyleId`. This
//! file lands the *types* — interner, ID, dedup map, NULL sentinel — but
//! no callers wire through it yet. PR1b will swap `Segment.style` over.
//!
//! # Design notes
//!
//! - `StyleId(u32)` is `Copy`. `StyleId::NULL == StyleId(0)` is reserved
//! for `Style::null()` and is pre-seeded by [`StyleInterner::new`].
//! - Dedup is content-based: `HashMap<Arc<Style>, StyleId>` works because
//! `Arc<T>: Hash + Eq` delegates to `T`'s impls (and `Style` has manual
//! `Hash + Eq`). Two distinct `Arc` instances with equal `Style` content
//! hash to the same bucket and compare equal.
//! - `Arc<Style>` (not raw `Style`) so `get` can return a cheap clone
//! without copying the underlying style data.
//! - **No cap yet.** Per the design doc, an LRU eviction at 64K ids will
//! land in PR3 alongside interner activation. Until then, an unbounded
//! `Vec` is fine because nothing actually interns.
use std::collections::HashMap;
use std::sync::Arc;
use crate::style::Style;
/// Stable identifier for an interned [`Style`] within a single
/// [`StyleInterner`]. Cross-interner IDs are not interchangeable.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct StyleId(u32);
impl StyleId {
/// Reserved id for `Style::null()`. Always present immediately after
/// [`StyleInterner::new`] returns.
pub const NULL: StyleId = StyleId(0);
/// Numeric value of the id. Useful for serialization and
/// stable-equality assertions in tests.
pub const fn as_u32(self) -> u32 {
self.0
}
}
impl Default for StyleId {
fn default() -> Self {
Self::NULL
}
}
/// Content-deduplicating interner for [`Style`] values. One interner per
/// [`crate::console::Console`] (renderables on different consoles must
/// not share ids).
#[derive(Debug)]
pub struct StyleInterner {
forward: Vec<Arc<Style>>,
reverse: HashMap<Arc<Style>, StyleId>,
}
impl StyleInterner {
/// Create an interner pre-seeded with `Style::null()` at
/// [`StyleId::NULL`].
pub fn new() -> Self {
let null_style = Arc::new(Style::null());
let mut interner = Self {
forward: Vec::new(),
reverse: HashMap::new(),
};
interner.forward.push(Arc::clone(&null_style));
interner.reverse.insert(null_style, StyleId::NULL);
interner
}
/// Intern a style and return its id. If an equal style is already
/// interned, the existing id is returned.
pub fn intern(&mut self, style: Style) -> StyleId {
let arc = Arc::new(style);
if let Some(&id) = self.reverse.get(&arc) {
return id;
}
let id = StyleId(self.forward.len() as u32);
self.forward.push(Arc::clone(&arc));
self.reverse.insert(arc, id);
id
}
/// Look up an interned style by id. Returns `None` for ids from
/// other interners or invalid ids.
pub fn get(&self, id: StyleId) -> Option<&Arc<Style>> {
self.forward.get(id.0 as usize)
}
/// Number of distinct styles interned (including the pre-seeded
/// null). Always >= 1.
pub fn len(&self) -> usize {
self.forward.len()
}
/// Whether the interner holds nothing beyond the pre-seeded null.
pub fn is_empty(&self) -> bool {
self.forward.len() <= 1
}
}
impl Default for StyleInterner {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn null_is_pre_seeded() {
let interner = StyleInterner::new();
assert_eq!(interner.len(), 1);
assert!(interner.is_empty()); // empty = "nothing beyond null"
let arc = interner.get(StyleId::NULL).expect("null present");
assert!(arc.is_null());
}
#[test]
fn dedup_returns_same_id() {
let mut interner = StyleInterner::new();
let s = Style::parse("bold red");
let id1 = interner.intern(s.clone());
let id2 = interner.intern(s);
assert_eq!(id1, id2);
assert_eq!(interner.len(), 2); // null + bold red
}
#[test]
fn distinct_styles_get_distinct_ids() {
let mut interner = StyleInterner::new();
let bold = Style::parse("bold");
let italic = Style::parse("italic");
let id1 = interner.intern(bold);
let id2 = interner.intern(italic);
assert_ne!(id1, id2);
assert_eq!(interner.len(), 3);
}
#[test]
fn null_intern_returns_null_id() {
let mut interner = StyleInterner::new();
let id = interner.intern(Style::null());
assert_eq!(id, StyleId::NULL);
assert_eq!(interner.len(), 1); // no growth
}
#[test]
fn get_unknown_id_returns_none() {
let interner = StyleInterner::new();
assert!(interner.get(StyleId(999)).is_none());
}
#[test]
fn ids_are_stable() {
let mut interner = StyleInterner::new();
let s = Style::parse("bold");
let id = interner.intern(s.clone());
// Intern many other styles; original id must not move.
for i in 0..10 {
interner.intern(Style::parse(&format!("color({i})")));
}
assert_eq!(interner.intern(s), id);
}
}