bob/
macros.rs

1use std::collections::HashMap;
2use std::sync::Arc;
3use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
4
5use crate::Element;
6
7/// An ordered set of macro definitions. Later definitions win.
8///
9/// A set layered over another (see [`Macros::with`]) shares it rather than
10/// copying it, so each widget of a large display costs only its own macros.
11#[derive(Clone, Debug, Default, PartialEq)]
12pub struct Macros(Arc<Layer>);
13
14#[derive(Debug, Default, PartialEq)]
15struct Layer {
16    parent: Option<Macros>,
17    /// Consulted after `parent` and everything below it.
18    base: Option<Macros>,
19    own: Vec<(String, String)>,
20    /// Position in `own` of the last definition of each name.
21    index: HashMap<String, usize>,
22    /// Layers below this one.
23    depth: u32,
24}
25
26/// The most expanded text that [`Macros::with`] holds in one layer.
27const MAX_LAYER_BYTES: usize = 1 << 20;
28
29/// The most expanded macro text, counting what was expanded as well as what
30/// it came to, that a whole load should do, for [`Macros::with_budget`] to be
31/// given. Each expansion takes the size of its text and result, so this also
32/// bounds the lookups, and so the time, of a load.
33pub const MAX_LOAD_BYTES: usize = 4 << 20;
34
35/// The most definitions in a layer, and the most layers; more are ignored.
36const MAX_LAYER_MACROS: usize = 512;
37const MAX_LAYERS: u32 = 32;
38
39impl Macros {
40    pub fn from_element(el: &Element) -> Self {
41        Self::from_pairs(el.children.iter().map(|c| (c.name.clone(), c.text.clone())))
42    }
43
44    pub fn from_pairs<K: Into<String>, V: Into<String>>(
45        pairs: impl IntoIterator<Item = (K, V)>,
46    ) -> Self {
47        let own: Vec<(String, String)> = pairs
48            .into_iter()
49            .map(|(k, v)| (k.into(), v.into()))
50            .collect();
51        Self::layer(None, None, own)
52    }
53
54    fn layer(parent: Option<Macros>, base: Option<Macros>, own: Vec<(String, String)>) -> Self {
55        let index = own
56            .iter()
57            .enumerate()
58            .map(|(i, (k, _))| (k.clone(), i))
59            .collect();
60        let depth = parent.as_ref().map_or(0, |p| p.0.depth + 1);
61        Self(Arc::new(Layer {
62            parent,
63            base,
64            own,
65            index,
66            depth,
67        }))
68    }
69
70    pub fn get(&self, name: &str) -> Option<&str> {
71        let own = self.0.index.get(name).map(|&i| self.0.own[i].1.as_str());
72        own.or_else(|| self.0.parent.as_ref()?.get(name))
73            .or_else(|| self.0.base.as_ref()?.get(name))
74    }
75
76    pub fn is_empty(&self) -> bool {
77        self.0.own.is_empty()
78            && self.0.parent.as_ref().is_none_or(|p| p.is_empty())
79            && self.0.base.as_ref().is_none_or(|b| b.is_empty())
80    }
81
82    /// Every definition, in the order [`Macros::get`] lets later ones win:
83    /// a layer's `base` first, then its `parent` (and all below it), then
84    /// its own.
85    pub fn iter(&self) -> impl Iterator<Item = (&str, &str)> {
86        let mut out = Vec::new();
87        self.collect_into(&mut out);
88        out.into_iter()
89    }
90
91    fn collect_into<'a>(&'a self, out: &mut Vec<(&'a str, &'a str)>) {
92        if let Some(b) = &self.0.base {
93            b.collect_into(out);
94        }
95        if let Some(p) = &self.0.parent {
96            p.collect_into(out);
97        }
98        out.extend(self.0.own.iter().map(|(k, v)| (k.as_str(), v.as_str())));
99    }
100
101    /// These macros with `inner` layered on top. Values in `inner` are first
102    /// expanded against `self`, so `<P>$(P):SUB</P>` works. Only `inner`'s
103    /// own definitions are used, not the layers under it: for a whole chain,
104    /// such as a link's, use [`Macros::over`].
105    pub fn with(&self, inner: &Macros) -> Macros {
106        self.with_budget(inner, &AtomicUsize::new(MAX_LAYER_BYTES))
107    }
108
109    /// [`Macros::with`], where expanding the values takes the size of their
110    /// text and result from `left`, which several layers may share. Once it
111    /// is spent, values are kept as written, not expanded, so nested
112    /// definitions that each double the last, in many widgets, can't use
113    /// memory or time without bound. Only the definitions made in `inner`
114    /// itself are used, at most [`MAX_LAYER_MACROS`] of them, and no more
115    /// than [`MAX_LAYERS`] deep.
116    pub fn with_budget(&self, inner: &Macros, left: &AtomicUsize) -> Macros {
117        if inner.0.own.is_empty() {
118            return self.clone();
119        }
120        if self.0.depth >= MAX_LAYERS {
121            log::warn!("macros nested over {MAX_LAYERS} deep are ignored");
122            return self.clone();
123        }
124        if inner.0.own.len() > MAX_LAYER_MACROS {
125            log::warn!("over {MAX_LAYER_MACROS} macros in a widget; the rest are ignored");
126        }
127        let own = inner
128            .0
129            .own
130            .iter()
131            .take(MAX_LAYER_MACROS)
132            .map(|(k, v)| {
133                let v = if left.load(Ordering::Relaxed) > 0 {
134                    let out = expand(v, &|name| self.get(name).map(str::to_string));
135                    spend(left, v.len() + out.len());
136                    out
137                } else {
138                    warn_spent();
139                    v.clone()
140                };
141                (k.clone(), v)
142            })
143            .collect();
144        Self::layer(Some(self.clone()), None, own)
145    }
146
147    /// `defaults` with `over` on top of them, sharing both: `over` is the
148    /// macros an embedding passes to the display it embeds, and is a whole
149    /// chain of the embedder's layers, which are not copied.
150    pub fn over(defaults: &Macros, over: &Macros, left: &AtomicUsize) -> Macros {
151        if over.0.parent.is_none() && over.0.base.is_none() {
152            return defaults.with_budget(over, left);
153        }
154        // A value naming its own key, as `P=$(P):SUB` does, means the next
155        // layer down, which here is the display's default.
156        let own = over
157            .iter()
158            .filter_map(|(k, v)| {
159                let default = defaults.get(k)?;
160                let fixed = v
161                    .replace(&format!("$({k})"), default)
162                    .replace(&format!("${{{k}}}"), default);
163                (fixed != v && over.get(k) == Some(v)).then(|| (k.to_string(), fixed))
164            })
165            .collect();
166        Self::layer(Some(over.clone()), Some(defaults.clone()), own)
167    }
168
169    /// The bytes of the definitions in this layer alone.
170    pub fn own_bytes(&self) -> usize {
171        self.0.own.iter().map(|(k, v)| k.len() + v.len()).sum()
172    }
173}
174
175/// Take `n` from `left`, down to nothing.
176pub fn spend(left: &AtomicUsize, n: usize) {
177    let mut l = left.load(Ordering::Relaxed);
178    while let Err(now) =
179        left.compare_exchange(l, l.saturating_sub(n), Ordering::Relaxed, Ordering::Relaxed)
180    {
181        l = now;
182    }
183}
184
185/// Warn, once until [`rearm_warning`], that an expansion was left as written.
186static WARNED: AtomicBool = AtomicBool::new(false);
187
188/// Let the next expansion that gives up warn again, as at the start of a load.
189pub fn rearm_warning() {
190    WARNED.store(false, Ordering::Relaxed);
191    SPENT_WARNED.store(false, Ordering::Relaxed);
192}
193
194static SPENT_WARNED: AtomicBool = AtomicBool::new(false);
195
196/// Warn, once per load, that the macro budget is spent and text is left as written.
197pub fn warn_spent() {
198    if !SPENT_WARNED.swap(true, Ordering::Relaxed) {
199        log::warn!("macro expansion budget spent; the rest of the load is left as written");
200    }
201}
202
203/// Replace `$(NAME)` and `${NAME}` using `lookup`. `$(NAME=default)` falls back
204/// to the default; unknown names are left as written, like Phoebus does.
205/// Text whose expansion would take more than [`MAX_WORK`] (16 KiB) of output,
206/// such as nested `$(M)` that each name `$(M)` several times, is returned
207/// unexpanded, as written, rather than truncated.
208pub fn expand(text: &str, lookup: &dyn Fn(&str) -> Option<String>) -> String {
209    let mut work = 0;
210    expand_depth(text, lookup, 0, &mut work).unwrap_or_else(|| {
211        if !WARNED.swap(true, Ordering::Relaxed) {
212            log::warn!("macro expansion over {MAX_WORK} bytes left as written: {text:.80}");
213        }
214        text.to_string()
215    })
216}
217
218/// The most output, counted over every nested expansion, that [`expand`] builds.
219/// Kept at 16 KiB rather than more because an expansion that fails costs all
220/// of it each time, and widgets expand text as they draw.
221const MAX_WORK: usize = 16 << 10;
222
223/// [`expand`] one level down, adding the size of what it builds to `work`;
224/// `None` once that passes [`MAX_WORK`].
225fn expand_depth(
226    text: &str,
227    lookup: &dyn Fn(&str) -> Option<String>,
228    depth: u32,
229    work: &mut usize,
230) -> Option<String> {
231    *work += text.len();
232    if *work > MAX_WORK {
233        return None;
234    }
235    if depth > 10 || !text.contains('$') {
236        return Some(text.to_string());
237    }
238    let mut out = String::with_capacity(text.len());
239    let mut rest = text;
240    while let Some(pos) = rest.find('$') {
241        out.push_str(&rest[..pos]);
242        let after = &rest[pos + 1..];
243        let close = match after.chars().next() {
244            Some('(') => ')',
245            Some('{') => '}',
246            _ => {
247                out.push('$');
248                rest = after;
249                continue;
250            }
251        };
252        let Some(end) = matching(after, close) else {
253            out.push_str(&rest[pos..]);
254            return Some(out);
255        };
256        let body = expand_depth(&after[1..end], lookup, depth + 1, work)?;
257        let (name, default) = match body.split_once('=') {
258            Some((n, d)) => (n, Some(d)),
259            None => (body.as_str(), None),
260        };
261        match lookup(name).or(default.map(str::to_string)) {
262            Some(value) => out.push_str(&expand_depth(&value, lookup, depth + 1, work)?),
263            None => out.push_str(&rest[pos..pos + end + 2]),
264        }
265        rest = &after[end + 1..];
266    }
267    out.push_str(rest);
268    Some(out)
269}
270
271/// Index of the bracket closing the one at the start of `s`, allowing nesting.
272fn matching(s: &str, close: char) -> Option<usize> {
273    let open = s.chars().next()?;
274    let mut level = 0;
275    for (i, c) in s.char_indices() {
276        if c == open {
277            level += 1;
278        } else if c == close {
279            level -= 1;
280            if level == 0 {
281                return Some(i);
282            }
283        }
284    }
285    None
286}
287
288#[cfg(test)]
289mod tests {
290    use super::*;
291
292    fn m() -> Macros {
293        Macros::from_pairs([("P", "BL01T"), ("R", ":DET:"), ("N", "$(P)")])
294    }
295
296    fn ex(s: &str) -> String {
297        let m = m();
298        expand(s, &|n| m.get(n).map(str::to_string))
299    }
300
301    #[test]
302    fn expands_both_bracket_styles() {
303        assert_eq!(ex("$(P)$(R)Acquire"), "BL01T:DET:Acquire");
304        assert_eq!(ex("${P}:X"), "BL01T:X");
305    }
306
307    #[test]
308    fn keeps_unknown_and_uses_defaults() {
309        assert_eq!(ex("$(Q):X"), "$(Q):X");
310        assert_eq!(ex("$(Q=dflt)"), "dflt");
311        assert_eq!(ex("cost $5"), "cost $5");
312        assert_eq!(ex("$(P"), "$(P");
313    }
314
315    #[test]
316    fn nested_expansion_is_bounded() {
317        // Each level names the next six times: 6^10 bytes if expanded in full.
318        let mut pairs = vec![("M0".to_string(), "x".to_string())];
319        for i in 1..=10 {
320            pairs.push((format!("M{i}"), format!("$(M{})", i - 1).repeat(6)));
321        }
322        let m = Macros::from_pairs(pairs);
323        let start = std::time::Instant::now();
324        let text = "$(M10)";
325        let out = expand(text, &|n| m.get(n).map(str::to_string));
326        assert_eq!(out, text);
327        assert!(start.elapsed().as_secs() < 2);
328        // Ordinary long values still expand.
329        let m = Macros::from_pairs([("L", "y".repeat(10_000))]);
330        assert_eq!(
331            expand("$(L)", &|n| m.get(n).map(str::to_string)).len(),
332            10_000
333        );
334    }
335
336    #[test]
337    fn layers_share_a_budget() {
338        let root = Macros::from_pairs([("V", "x".repeat(1000))]);
339        let left = AtomicUsize::new(5000);
340        let inner = Macros::from_pairs((0..100).map(|i| (format!("N{i}"), "$(V)")));
341        let set = root.with_budget(&inner, &left);
342        // Expanded until spent, then kept as written.
343        assert_eq!(set.get("N0").map(str::len), Some(1000));
344        assert_eq!(set.get("N99"), Some("$(V)"));
345        assert!(set.own_bytes() < 10_000);
346        let more = set.with_budget(&inner, &left);
347        assert_eq!(more.get("N0"), Some("$(V)"));
348    }
349
350    #[test]
351    fn iter_lists_every_layer_as_get_sees_them() {
352        // An embedded display's defaults (the base) under its caller's
353        // chain: iterating, later definitions win as `get` has them.
354        let defaults = Macros::from_pairs([("D", "dflt"), ("P", "D")]);
355        let caller = Macros::from_pairs([("P", "CALL")]).with(&Macros::from_pairs([("id", "01")]));
356        let m = Macros::over(&defaults, &caller, &AtomicUsize::new(1 << 20));
357        let last: std::collections::BTreeMap<_, _> = m.iter().collect();
358        for (k, v) in &last {
359            assert_eq!(m.get(k), Some(*v), "{k}");
360        }
361        assert_eq!(
362            last.into_iter().collect::<Vec<_>>(),
363            [("D", "dflt"), ("P", "CALL"), ("id", "01")]
364        );
365    }
366
367    #[test]
368    fn caller_self_references_use_the_displays_defaults() {
369        let ex = |m: &Macros, t: &str| expand(t, &|n| m.get(n).map(str::to_string));
370        let defaults = Macros::from_pairs([("P", "D")]);
371        let own = Macros::from_pairs([("P", "$(P):SUB")]);
372        let none = Macros::from_pairs([("X", "1")]);
373        let caller = none.with(&own);
374        let m = Macros::over(&defaults, &caller, &AtomicUsize::new(1 << 20));
375        assert_eq!(ex(&m, "$(P)"), "D:SUB");
376        let caller = Macros::from_pairs([("P", "CALL")]).with(&own);
377        let m = Macros::over(&defaults, &caller, &AtomicUsize::new(1 << 20));
378        assert_eq!(ex(&m, "$(P)"), "CALL:SUB");
379    }
380
381    #[test]
382    fn expands_recursively_and_layers() {
383        assert_eq!(ex("$(N)"), "BL01T");
384        let inner = Macros::from_pairs([("P", "$(P):SUB")]);
385        assert_eq!(m().with(&inner).get("P"), Some("BL01T:SUB"));
386    }
387}
bob/macros.rs

bob/
macros.rs
