egui_charts/services/search/
expression.rs

1//! Arithmetic over symbols, for spread charts.
2
3use crate::model::Bar;
4use std::fmt;
5
6/// An arithmetic expression over symbols, such as `AAPL-MSFT` or `(BTCUSD+ETHUSD)/2`, charted as
7/// one synthetic series.
8///
9/// Symbols, decimal numbers, `+`, `-`, `*`, `/`, a leading minus and parentheses are accepted,
10/// with the usual precedence; spaces are ignored. A symbol is a run of letters, digits and
11/// `.`, `:`, `_` or `!`, such as `NASDAQ:AAPL`, `BRK.B` or `ES1!`, that is not a number. The
12/// text it formats to is the symbol of its [`Instrument`](crate::model::Instrument). At most
13/// 256 tokens are accepted to bound recursive parsing and evaluation of user input.
14///
15/// ```
16/// use chrono::{TimeZone, Utc};
17/// use egui_charts::model::Bar;
18/// use egui_charts::services::SymbolExpression;
19///
20/// let spread = SymbolExpression::parse("aapl - msft").unwrap();
21/// assert_eq!(spread.symbols(), ["aapl", "msft"]);
22/// assert_eq!(spread.to_string(), "aapl-msft");
23///
24/// let day = |d| Utc.with_ymd_and_hms(2024, 3, d, 0, 0, 0).unwrap();
25/// let aapl = [Bar::new(day(1), 170.0, 172.0, 169.0, 171.0, 0.0)];
26/// let msft = [Bar::new(day(1), 410.0, 415.0, 405.0, 412.0, 0.0)];
27/// let bars = spread
28///     .bars(|symbol| match symbol {
29///         "aapl" => Some(&aapl[..]),
30///         "msft" => Some(&msft[..]),
31///         _ => None,
32///     })
33///     .unwrap();
34/// assert_eq!((bars[0].open, bars[0].close), (-240.0, -241.0));
35/// ```
36#[derive(Clone, Debug, PartialEq)]
37pub struct SymbolExpression {
38    root: Node,
39}
40
41#[derive(Clone, Debug, PartialEq)]
42enum Node {
43    Number(f64),
44    Symbol(String),
45    Negate(Box<Node>),
46    Binary(Operator, Box<Node>, Box<Node>),
47}
48
49#[derive(Clone, Copy, Debug, PartialEq)]
50enum Operator {
51    Add,
52    Subtract,
53    Multiply,
54    Divide,
55}
56
57impl Operator {
58    fn precedence(self) -> u8 {
59        match self {
60            Self::Add | Self::Subtract => 1,
61            Self::Multiply | Self::Divide => 2,
62        }
63    }
64
65    fn sign(self) -> char {
66        match self {
67            Self::Add => '+',
68            Self::Subtract => '-',
69            Self::Multiply => '*',
70            Self::Divide => '/',
71        }
72    }
73}
74
75/// Why text is not a [`SymbolExpression`], or why one cannot be charted.
76#[derive(Clone, Debug, PartialEq)]
77#[non_exhaustive]
78pub enum ExpressionError {
79    /// A character that belongs to no symbol, number, operator or parenthesis.
80    UnexpectedCharacter(char),
81    /// An operator, a parenthesis or the end of the text where a symbol or number belongs.
82    MissingOperand,
83    /// A symbol, number or parenthesis that follows another without an operator.
84    MissingOperator(String),
85    /// A `(` without its `)`, or a `)` without its `(`.
86    UnbalancedParenthesis,
87    /// Numbers alone, with no symbol to chart.
88    NoSymbol,
89    /// A symbol the instrument catalog or the supplied history does not know.
90    UnknownSymbol(String),
91    /// More than 256 symbols, numbers, operators and parentheses.
92    TooComplex,
93}
94
95impl fmt::Display for ExpressionError {
96    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
97        match self {
98            Self::UnexpectedCharacter(found) => write!(f, "Unexpected character {found:?}"),
99            Self::MissingOperand => write!(f, "A symbol or number is missing"),
100            Self::MissingOperator(found) => write!(f, "An operator is missing before {found}"),
101            Self::UnbalancedParenthesis => write!(f, "Unbalanced parentheses"),
102            Self::NoSymbol => write!(f, "The expression has no symbol"),
103            Self::UnknownSymbol(symbol) => write!(f, "Unknown symbol {symbol}"),
104            Self::TooComplex => write!(f, "The expression exceeds 256 tokens"),
105        }
106    }
107}
108
109impl std::error::Error for ExpressionError {}
110
111#[derive(Clone, Debug, PartialEq)]
112enum Token {
113    Number(f64),
114    Symbol(String),
115    Operator(Operator),
116    Open,
117    Close,
118}
119
120fn tokens(text: &str) -> Result<Vec<Token>, ExpressionError> {
121    let symbol_char = |c: char| c.is_alphanumeric() || matches!(c, '.' | ':' | '_' | '!');
122    let mut tokens = Vec::new();
123    let mut chars = text.char_indices().peekable();
124    while let Some((start, c)) = chars.next() {
125        let token = match c {
126            _ if c.is_whitespace() => continue,
127            '+' => Token::Operator(Operator::Add),
128            '-' => Token::Operator(Operator::Subtract),
129            '*' => Token::Operator(Operator::Multiply),
130            '/' => Token::Operator(Operator::Divide),
131            '(' => Token::Open,
132            ')' => Token::Close,
133            _ if symbol_char(c) => {
134                let mut end = start + c.len_utf8();
135                while let Some(&(at, next)) = chars.peek()
136                    && symbol_char(next)
137                {
138                    end = at + next.len_utf8();
139                    chars.next();
140                }
141                let word = &text[start..end];
142                let numeric = word.chars().all(|c| c.is_ascii_digit() || c == '.');
143                match word.parse::<f64>() {
144                    Ok(number) if numeric && number.is_finite() => Token::Number(number),
145                    _ => Token::Symbol(word.to_owned()),
146                }
147            }
148            _ => return Err(ExpressionError::UnexpectedCharacter(c)),
149        };
150        if tokens.len() == 256 {
151            return Err(ExpressionError::TooComplex);
152        }
153        tokens.push(token);
154    }
155    Ok(tokens)
156}
157
158/// Recursive descent over the tokens: sums of products of signed factors.
159struct Parser {
160    tokens: Vec<Token>,
161    at: usize,
162}
163
164impl Parser {
165    fn peek(&self) -> Option<&Token> {
166        self.tokens.get(self.at)
167    }
168
169    fn sum(&mut self) -> Result<Node, ExpressionError> {
170        let mut node = self.product()?;
171        while let Some(&Token::Operator(op @ (Operator::Add | Operator::Subtract))) = self.peek() {
172            self.at += 1;
173            node = Node::Binary(op, Box::new(node), Box::new(self.product()?));
174        }
175        Ok(node)
176    }
177
178    fn product(&mut self) -> Result<Node, ExpressionError> {
179        let mut node = self.factor()?;
180        while let Some(&Token::Operator(op @ (Operator::Multiply | Operator::Divide))) = self.peek()
181        {
182            self.at += 1;
183            node = Node::Binary(op, Box::new(node), Box::new(self.factor()?));
184        }
185        Ok(node)
186    }
187
188    fn factor(&mut self) -> Result<Node, ExpressionError> {
189        let token = self.peek().cloned();
190        self.at += 1;
191        match token {
192            Some(Token::Number(number)) => Ok(Node::Number(number)),
193            Some(Token::Symbol(symbol)) => Ok(Node::Symbol(symbol)),
194            Some(Token::Operator(Operator::Subtract)) => Ok(Node::Negate(Box::new(self.factor()?))),
195            Some(Token::Open) => {
196                let node = self.sum()?;
197                if self.peek() != Some(&Token::Close) {
198                    return Err(match self.peek() {
199                        None => ExpressionError::UnbalancedParenthesis,
200                        Some(token) => ExpressionError::MissingOperator(describe(token)),
201                    });
202                }
203                self.at += 1;
204                Ok(node)
205            }
206            Some(Token::Close) if self.at == 1 => Err(ExpressionError::UnbalancedParenthesis),
207            _ => Err(ExpressionError::MissingOperand),
208        }
209    }
210}
211
212fn describe(token: &Token) -> String {
213    match token {
214        Token::Number(number) => number.to_string(),
215        Token::Symbol(symbol) => symbol.clone(),
216        Token::Operator(op) => op.sign().to_string(),
217        Token::Open => "(".into(),
218        Token::Close => ")".into(),
219    }
220}
221
222impl SymbolExpression {
223    /// Parses `text`, which may also be a lone symbol.
224    pub fn parse(text: &str) -> Result<Self, ExpressionError> {
225        let mut parser = Parser {
226            tokens: tokens(text)?,
227            at: 0,
228        };
229        let root = parser.sum()?;
230        if let Some(token) = parser.peek() {
231            return Err(if *token == Token::Close {
232                ExpressionError::UnbalancedParenthesis
233            } else {
234                ExpressionError::MissingOperator(describe(token))
235            });
236        }
237        let expression = Self { root };
238        if expression.symbols().is_empty() {
239            return Err(ExpressionError::NoSymbol);
240        }
241        Ok(expression)
242    }
243
244    /// Whether the expression is more than one symbol, which is what a spread chart needs.
245    #[cfg(feature = "widget")]
246    pub(crate) fn is_spread(&self) -> bool {
247        !matches!(self.root, Node::Symbol(_))
248    }
249
250    /// The symbols of the expression, each once, in order of appearance.
251    pub fn symbols(&self) -> Vec<&str> {
252        fn walk<'a>(node: &'a Node, found: &mut Vec<&'a str>) {
253            match node {
254                Node::Number(_) => {}
255                Node::Symbol(symbol) => {
256                    if !found.contains(&symbol.as_str()) {
257                        found.push(symbol);
258                    }
259                }
260                Node::Negate(inner) => walk(inner, found),
261                Node::Binary(_, left, right) => {
262                    walk(left, found);
263                    walk(right, found);
264                }
265            }
266        }
267        let mut found = Vec::new();
268        walk(&self.root, &mut found);
269        found
270    }
271
272    /// Replaces each symbol by `rename(symbol)`, such as the spelling of the instrument catalog.
273    #[cfg(feature = "ui")]
274    pub(crate) fn rename_symbols(&mut self, mut rename: impl FnMut(&str) -> String) {
275        fn walk(node: &mut Node, rename: &mut impl FnMut(&str) -> String) {
276            match node {
277                Node::Number(_) => {}
278                Node::Symbol(symbol) => *symbol = rename(symbol),
279                Node::Negate(inner) => walk(inner, rename),
280                Node::Binary(_, left, right) => {
281                    walk(left, rename);
282                    walk(right, rename);
283                }
284            }
285        }
286        walk(&mut self.root, &mut rename);
287    }
288
289    /// The value of the expression with each symbol replaced by `value(symbol)`, or `None` when
290    /// a symbol has no finite value or any intermediate result is not finite, as after a
291    /// division by zero.
292    pub fn evaluate(&self, value: impl Fn(&str) -> Option<f64>) -> Option<f64> {
293        fn walk(node: &Node, value: &impl Fn(&str) -> Option<f64>) -> Option<f64> {
294            Some(match node {
295                Node::Number(number) => *number,
296                Node::Symbol(symbol) => value(symbol)?,
297                Node::Negate(inner) => -walk(inner, value)?,
298                Node::Binary(op, left, right) => {
299                    let (left, right) = (walk(left, value)?, walk(right, value)?);
300                    match op {
301                        Operator::Add => left + right,
302                        Operator::Subtract => left - right,
303                        Operator::Multiply => left * right,
304                        Operator::Divide => left / right,
305                    }
306                }
307            })
308            .filter(|result| result.is_finite())
309        }
310        walk(&self.root, &value)
311    }
312
313    /// The synthetic series from the time-ordered bars `history` returns for each symbol.
314    ///
315    /// A bar is made for each time at which every symbol has a bar. Its open and close apply the
316    /// expression to the components' opens and closes, its high and low to their highs and lows,
317    /// and the high and low then widen to cover all four results, since a difference or a
318    /// quotient of highs need not be the highest value. Times whose result is not finite are left
319    /// out. Volume is zero because the components have no shared traded volume. A symbol without
320    /// history is an [`ExpressionError::UnknownSymbol`].
321    pub fn bars<'a>(
322        &self,
323        history: impl Fn(&str) -> Option<&'a [Bar]>,
324    ) -> Result<Vec<Bar>, ExpressionError> {
325        let components = self
326            .symbols()
327            .into_iter()
328            .map(|symbol| {
329                history(symbol)
330                    .map(|bars| (symbol, bars))
331                    .ok_or_else(|| ExpressionError::UnknownSymbol(symbol.to_owned()))
332            })
333            .collect::<Result<Vec<_>, _>>()?;
334        let timeline = components[0].1;
335        let mut bars = Vec::new();
336        for bar in timeline.iter() {
337            let Some(aligned) = components
338                .iter()
339                .map(|(symbol, bars)| {
340                    let at = bars.binary_search_by_key(&bar.time, |bar| bar.time).ok()?;
341                    Some((*symbol, &bars[at]))
342                })
343                .collect::<Option<Vec<_>>>()
344            else {
345                continue;
346            };
347            let field = |pick: fn(&Bar) -> f64| {
348                self.evaluate(|symbol| {
349                    aligned
350                        .iter()
351                        .find(|(name, _)| *name == symbol)
352                        .map(|(_, bar)| pick(bar))
353                })
354            };
355            let (Some(open), Some(high), Some(low), Some(close)) = (
356                field(|bar| bar.open),
357                field(|bar| bar.high),
358                field(|bar| bar.low),
359                field(|bar| bar.close),
360            ) else {
361                continue;
362            };
363            let values = [open, high, low, close];
364            bars.push(Bar::new(
365                bar.time,
366                open,
367                values.into_iter().fold(f64::MIN, f64::max),
368                values.into_iter().fold(f64::MAX, f64::min),
369                close,
370                0.0,
371            ));
372        }
373        Ok(bars)
374    }
375}
376
377impl fmt::Display for SymbolExpression {
378    /// The expression without spaces and with only the parentheses its order needs.
379    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
380        fn write(node: &Node, f: &mut fmt::Formatter<'_>) -> fmt::Result {
381            match node {
382                Node::Number(number) => write!(f, "{number}"),
383                Node::Symbol(symbol) => f.write_str(symbol),
384                Node::Negate(inner) => {
385                    f.write_str("-")?;
386                    operand(inner, 3, f)
387                }
388                Node::Binary(op, left, right) => {
389                    operand(left, op.precedence(), f)?;
390                    write!(f, "{}", op.sign())?;
391                    // A right operand of equal precedence keeps its parentheses: a-(b-c).
392                    operand(right, op.precedence() + 1, f)
393                }
394            }
395        }
396        fn operand(node: &Node, min: u8, f: &mut fmt::Formatter<'_>) -> fmt::Result {
397            let precedence = match node {
398                Node::Binary(op, ..) => op.precedence(),
399                _ => 3,
400            };
401            if precedence < min {
402                f.write_str("(")?;
403                write(node, f)?;
404                f.write_str(")")
405            } else {
406                write(node, f)
407            }
408        }
409        write(&self.root, f)
410    }
411}
412
413#[cfg(test)]
414mod tests {
415    use super::*;
416    use chrono::{TimeZone, Utc};
417
418    /// Precedence, signs and parentheses read and print as written, and each malformed text
419    /// names its fault.
420    #[test]
421    fn expressions_parse_print_and_report_faults() {
422        for (text, expected) in [
423            ("AAPL - MSFT", Ok("AAPL-MSFT")),
424            ("(BTCUSD+ETHUSD)/2", Ok("(BTCUSD+ETHUSD)/2")),
425            ("a-(b-c)", Ok("a-(b-c)")),
426            ("a-b-c", Ok("a-b-c")),
427            ("a*b+c", Ok("a*b+c")),
428            ("a*(b+c)", Ok("a*(b+c)")),
429            ("-a+2.5*NASDAQ:B", Ok("-a+2.5*NASDAQ:B")),
430            ("ES1!/BRK.B", Ok("ES1!/BRK.B")),
431            ("", Err(ExpressionError::MissingOperand)),
432            ("AAPL -", Err(ExpressionError::MissingOperand)),
433            (
434                "AAPL MSFT",
435                Err(ExpressionError::MissingOperator("MSFT".into())),
436            ),
437            ("(AAPL-MSFT", Err(ExpressionError::UnbalancedParenthesis)),
438            ("AAPL-MSFT)", Err(ExpressionError::UnbalancedParenthesis)),
439            ("AAPL%2", Err(ExpressionError::UnexpectedCharacter('%'))),
440            ("2*3", Err(ExpressionError::NoSymbol)),
441        ] {
442            let parsed = SymbolExpression::parse(text).map(|e| e.to_string());
443            assert_eq!(parsed, expected.map(str::to_owned), "{text:?}");
444        }
445        for text in [
446            format!("{}A{}", "(".repeat(300), ")".repeat(300)),
447            ["A"; 300].join("+"),
448            format!("{}A", "-".repeat(300)),
449        ] {
450            assert!(
451                SymbolExpression::parse(&text).is_err(),
452                "unbounded recursion"
453            );
454        }
455    }
456
457    /// The synthetic bars against hand-computed values: only times every symbol trades, the
458    /// expression applied to each price, the high and low widened over all four results, and a
459    /// zero divisor dropping its time.
460    #[test]
461    fn spread_bars_align_components_by_time() {
462        let day = |d| Utc.with_ymd_and_hms(2024, 3, d, 0, 0, 0).unwrap();
463        let a = [
464            Bar::new(day(1), 10.0, 14.0, 9.0, 12.0, 100.0),
465            Bar::new(day(2), 12.0, 13.0, 11.0, 11.5, 100.0),
466            Bar::new(day(3), 11.0, 15.0, 10.0, 14.0, 100.0),
467        ];
468        let b = [
469            Bar::new(day(1), 4.0, 8.0, 3.5, 5.0, 50.0),
470            Bar::new(day(3), 2.0, 0.0, 1.0, 7.0, 50.0),
471        ];
472        let history = |symbol: &str| match symbol {
473            "A" => Some(&a[..]),
474            "B" => Some(&b[..]),
475            _ => None,
476        };
477        let ohlc = |text: &str| {
478            SymbolExpression::parse(text)
479                .unwrap()
480                .bars(history)
481                .map(|bars| {
482                    assert!(bars.iter().all(crate::data::merge::valid));
483                    bars.iter()
484                        .map(|bar| (bar.time, bar.open, bar.high, bar.low, bar.close))
485                        .collect::<Vec<_>>()
486                })
487        };
488        // Day 1: opens 10-4, highs 14-8, lows 9-3.5, closes 12-5. Day 3: 11-2, 15-0, 10-1, 14-7.
489        assert_eq!(
490            ohlc("A-B"),
491            Ok(vec![
492                (day(1), 6.0, 7.0, 5.5, 7.0),
493                (day(3), 9.0, 15.0, 7.0, 7.0)
494            ])
495        );
496        // Day 1: 10/4, 14/8, 9/3.5, 12/5; day 3 divides a high by zero.
497        assert_eq!(
498            ohlc("A/B"),
499            Ok(vec![(day(1), 2.5, 2.5714285714285716, 1.75, 2.4)])
500        );
501        assert_eq!(ohlc("A-C"), Err(ExpressionError::UnknownSymbol("C".into())));
502        // A/0 is undefined; taking its reciprocal cannot turn it into a valid zero price.
503        assert_eq!(ohlc("1/(A/0)"), Ok(vec![]));
504    }
505}
egui_charts/services/search/expression.rs

egui_charts/services/search/
expression.rs
