1use std::sync::Arc;
4
5use crate::base::addr::{letters_to_col, parse_a1_prefix};
6use crate::base::{CellError, MAX_ROWS};
7
8use crate::formula::ast::{Anchor, BinOp, Expr, RefKind, Reference, SheetSel, StructItem, StructRef, TrimMode, UnOp};
9use crate::formula::lexer::{Tok, Token, tokenize_locale};
10
11#[derive(Clone, Debug, PartialEq, thiserror::Error)]
12#[error("{msg}")]
13pub struct ParseError {
14 pub msg: String,
15 pub pos: usize,
16}
17
18pub(crate) const MAX_DEPTH: usize = 256;
19
20pub const MAX_FORMULA_LEN: usize = 8_192;
24
25pub fn parse(src: &str) -> Result<Expr, ParseError> {
28 parse_syntax(src, crate::formula::FormulaLocale::En)
29}
30
31pub fn parse_name(src: &str) -> Result<Expr, ParseError> {
34 parse_top(src, crate::formula::FormulaLocale::En, true)
35}
36
37const MAX_CLOSED_PARENS: usize = 8;
39
40pub fn parse_closing_parens<T>(src: &str, parse: impl Fn(&str) -> Result<T, ParseError>) -> Result<T, ParseError> {
44 let typed = match parse(src) {
45 Ok(parsed) => return Ok(parsed),
46 Err(e) => e,
47 };
48 let mut text = src.to_string();
49 for _ in 0..MAX_CLOSED_PARENS {
50 text.push(')');
51 if let Ok(parsed) = parse(&text) {
52 return Ok(parsed);
53 }
54 }
55 Err(typed)
56}
57
58pub(crate) fn parse_syntax(src: &str, locale: crate::formula::FormulaLocale) -> Result<Expr, ParseError> {
59 parse_top(src, locale, false)
60}
61
62fn parse_top(src: &str, locale: crate::formula::FormulaLocale, allow_union: bool) -> Result<Expr, ParseError> {
63 let body = src.strip_prefix('=').unwrap_or(src);
64 if body.len() > MAX_FORMULA_LEN && body.chars().count() > MAX_FORMULA_LEN {
65 return Err(ParseError { msg: format!("formula is longer than {MAX_FORMULA_LEN} characters"), pos: 0 });
66 }
67 let toks = tokenize_locale(body, locale).map_err(|e| ParseError { msg: e.msg, pos: e.pos })?;
68 let toks = significant_spaces(toks);
69 let mut p = Parser { toks, i: 0, depth: 0, input: locale == crate::formula::FormulaLocale::Es };
70 let e = p.expr(0, allow_union)?;
71 match p.peek() {
72 Tok::Eof => Ok(e),
73 t => Err(p.err(format!("unexpected {}", describe(t)))),
74 }
75}
76
77fn describe(t: &Tok) -> String {
78 match t {
79 Tok::RParen => "`)`".into(),
80 Tok::Comma => "`,`".into(),
81 Tok::Eof => "end of formula".into(),
82 other => format!("{other:?}"),
83 }
84}
85
86fn significant_spaces(toks: Vec<Token>) -> Vec<Token> {
89 let mut out: Vec<Token> = Vec::with_capacity(toks.len());
90 for (i, t) in toks.iter().enumerate() {
91 if t.tok == Tok::Space {
92 let prev_end = out.last().is_some_and(|p| matches!(p.tok, Tok::Word(_) | Tok::RParen | Tok::Struct(_) | Tok::Error(_)));
93 let next_start =
94 toks.get(i + 1).is_some_and(|n| matches!(n.tok, Tok::Word(_) | Tok::Sheet(..) | Tok::LParen | Tok::Func(_) | Tok::Error(_)));
95 if prev_end && next_start {
96 out.push(t.clone());
97 }
98 continue;
99 }
100 out.push(t.clone());
101 }
102 out
103}
104
105struct Parser {
106 toks: Vec<Token>,
107 i: usize,
108 depth: usize,
109 input: bool,
110}
111
112fn word_is_cols(w: &str) -> Option<(u32, bool)> {
113 let abs = w.starts_with('$');
114 letters_to_col(w.trim_start_matches('$')).map(|c| (c, abs))
115}
116
117fn word_is_row(w: &str) -> Option<(u32, bool)> {
118 let abs = w.starts_with('$');
119 let n: u32 = w.trim_start_matches('$').parse().ok()?;
120 if n == 0 || n > MAX_ROWS { None } else { Some((n - 1, abs)) }
121}
122
123fn word_is_cell(w: &str) -> Option<Anchor> {
124 let (col, row, col_abs, row_abs, rest) = parse_a1_prefix(w)?;
125 if !rest.is_empty() {
126 return None;
127 }
128 Some(Anchor { row, col, row_abs, col_abs })
129}
130
131pub fn normalize_function_name(name: &str) -> String {
134 let u = name.to_ascii_uppercase();
135 for p in ["_XLFN._XLWS.", "_XLFN.", "_XLWS."] {
136 if let Some(r) = u.strip_prefix(p) {
137 return r.to_string();
138 }
139 }
140 match u.strip_prefix("_XLUDF.") {
141 Some(r) => format!("_xludf.{r}"),
142 None => u,
143 }
144}
145
146impl Parser {
147 fn peek(&self) -> &Tok {
148 self.toks.get(self.i).map(|t| &t.tok).unwrap_or(&Tok::Eof)
149 }
150 fn peek_at(&self, k: usize) -> &Tok {
151 self.toks.get(self.i + k).map(|t| &t.tok).unwrap_or(&Tok::Eof)
152 }
153 fn pos(&self) -> usize {
154 self.toks.get(self.i).map(|t| t.start).unwrap_or(0)
155 }
156 fn next(&mut self) -> Tok {
157 let t = self.peek().clone();
158 if self.i < self.toks.len() {
159 self.i += 1;
160 }
161 t
162 }
163 fn err(&self, msg: impl Into<String>) -> ParseError {
164 ParseError { msg: msg.into(), pos: self.pos() }
165 }
166 fn expect(&mut self, t: Tok) -> Result<(), ParseError> {
167 if *self.peek() == t {
168 self.next();
169 Ok(())
170 } else {
171 Err(self.err(format!("expected {}, found {}", describe(&t), describe(self.peek()))))
172 }
173 }
174
175 fn binop(&self, allow_union: bool) -> Option<BinOp> {
176 Some(match self.peek() {
177 Tok::Op("+") => BinOp::Add,
178 Tok::Op("-") => BinOp::Sub,
179 Tok::Op("*") => BinOp::Mul,
180 Tok::Op("/") => BinOp::Div,
181 Tok::Op("^") => BinOp::Pow,
182 Tok::Op("&") => BinOp::Concat,
183 Tok::Op("=") => BinOp::Eq,
184 Tok::Op("<>") => BinOp::Ne,
185 Tok::Op("<") => BinOp::Lt,
186 Tok::Op(">") => BinOp::Gt,
187 Tok::Op("<=") => BinOp::Le,
188 Tok::Op(">=") => BinOp::Ge,
189 Tok::Colon => BinOp::Range,
190 Tok::Space => BinOp::Intersect,
191 Tok::Comma if allow_union => BinOp::Union,
192 _ => return None,
193 })
194 }
195
196 fn expr(&mut self, min_bp: u8, allow_union: bool) -> Result<Expr, ParseError> {
197 self.depth += 1;
198 if self.depth > MAX_DEPTH {
199 return Err(self.err("formula is nested too deeply"));
200 }
201 let mut lhs = self.prefix(allow_union)?;
202 let mut postfix = 0;
205 loop {
206 if *self.peek() == Tok::Op("%") {
207 if 70 < min_bp {
208 break;
209 }
210 postfix += 1;
211 if self.depth + postfix > MAX_DEPTH {
212 return Err(self.err("formula is nested too deeply"));
213 }
214 self.next();
215 lhs = Expr::Unary(UnOp::Percent, Box::new(lhs));
216 continue;
217 }
218 if *self.peek() == Tok::LParen && matches!(lhs, Expr::Call(..) | Expr::Invoke(..) | Expr::Paren(_) | Expr::Name(_)) {
219 if let Expr::Name(_) = lhs {
221 }
223 postfix += 1;
224 if self.depth + postfix > MAX_DEPTH {
225 return Err(self.err("formula is nested too deeply"));
226 }
227 self.next();
228 let args = self.args()?;
229 lhs = Expr::Invoke(Box::new(lhs), args);
230 continue;
231 }
232 if let Tok::Trim(mode) = *self.peek() {
233 let bp = BinOp::Range.precedence();
235 if bp < min_bp {
236 break;
237 }
238 self.next();
239 let rhs = self.expr(bp + 1, allow_union)?;
240 lhs = Expr::Unary(UnOp::Trim(mode), Box::new(combine(BinOp::Range, lhs, rhs)));
241 continue;
242 }
243 let Some(op) = self.binop(allow_union) else { break };
244 let bp = op.precedence();
245 if bp < min_bp {
246 break;
247 }
248 self.next();
249 let rhs = self.expr(bp + 1, allow_union)?;
250 lhs = combine(op, lhs, rhs);
251 }
252 self.depth -= 1;
253 Ok(lhs)
254 }
255
256 fn args(&mut self) -> Result<Vec<Expr>, ParseError> {
257 let mut args = Vec::new();
258 if *self.peek() == Tok::RParen {
259 self.next();
260 return Ok(args);
261 }
262 loop {
263 let a = match self.peek() {
264 Tok::Comma | Tok::RParen => Expr::Missing,
265 _ => self.expr(0, false)?,
266 };
267 args.push(a);
268 match self.next() {
269 Tok::Comma => continue,
270 Tok::RParen => break,
271 t => return Err(self.err(format!("expected `,` or `)`, found {}", describe(&t)))),
272 }
273 }
274 if args.len() > 255 {
275 return Err(self.err("too many arguments"));
276 }
277 Ok(args)
278 }
279
280 fn prefix(&mut self, allow_union: bool) -> Result<Expr, ParseError> {
281 match self.next() {
282 Tok::Number(n) => Ok(Expr::Number(n)),
283 Tok::Text(s) => Ok(Expr::Text(Arc::from(s))),
284 Tok::Bool(b) => Ok(Expr::Bool(b)),
285 Tok::Error(e) => Ok(Expr::Error(e)),
286 Tok::Op("-") => Ok(Expr::Unary(UnOp::Neg, Box::new(self.expr(60, allow_union)?))),
287 Tok::Op("+") => Ok(Expr::Unary(UnOp::Plus, Box::new(self.expr(60, allow_union)?))),
288 Tok::Op("@") => Ok(Expr::Unary(UnOp::At, Box::new(self.expr(95, allow_union)?))),
289 Tok::LParen => {
290 let e = self.expr(0, true)?;
291 self.expect(Tok::RParen)?;
292 Ok(Expr::Paren(Box::new(e)))
293 }
294 Tok::LBrace => self.array(),
295 Tok::Func(name) => {
296 let name = normalize_function_name(&name);
297 let mut args = self.args()?;
298 if name == "ANCHORARRAY"
300 && let [Expr::Ref(Reference { kind: RefKind::Cell(_), .. })] = args.as_slice()
301 && let Some(r) = args.pop()
302 {
303 return Ok(Expr::Unary(UnOp::Spill, Box::new(r)));
304 }
305 if name == "SINGLE"
307 && args.len() == 1
308 && let Some(x) = args.pop()
309 {
310 return Ok(Expr::Unary(UnOp::At, Box::new(x)));
311 }
312 let trim = match name.as_str() {
314 "_TRO_LEADING" => Some(TrimMode::Leading),
315 "_TRO_TRAILING" => Some(TrimMode::Trailing),
316 "_TRO_ALL" => Some(TrimMode::All),
317 _ => None,
318 };
319 if let Some(mode) = trim
320 && args.len() == 1
321 && let Some(x) = args.pop()
322 {
323 return Ok(Expr::Unary(UnOp::Trim(mode), Box::new(x)));
324 }
325 Ok(Expr::Call(name, args))
326 }
327 Tok::Sheet(a, b) => {
328 let sheet = match b {
329 Some(b) => SheetSel::Span(a, b),
330 None => SheetSel::Named(a),
331 };
332 match self.next() {
333 Tok::Word(w) => self.reference_from_word(sheet, &w),
334 Tok::Error(CellError::Ref) => Ok(Expr::Error(CellError::Ref)),
335 t => Err(self.err(format!("expected a reference after the sheet name, found {}", describe(&t)))),
336 }
337 }
338 Tok::Word(w) => {
339 if let Tok::Struct(_) = self.peek()
340 && word_is_cell(&w).is_none()
341 {
342 let pos = self.pos();
343 let Tok::Struct(body) = self.next() else { return Err(self.err("internal")) };
344 return parse_struct(&w, &body).map(Expr::Struct).map_err(|msg| ParseError { msg, pos });
345 }
346 self.reference_from_word(SheetSel::Current, &w)
347 }
348 Tok::Struct(body) => parse_struct("", &body).map(Expr::Struct).map_err(|msg| self.err(msg)),
349 t => Err(self.err(format!("unexpected {}", describe(&t)))),
350 }
351 }
352
353 fn reference_from_word(&mut self, sheet: SheetSel, w: &str) -> Result<Expr, ParseError> {
357 let trim = match self.peek() {
358 Tok::Colon => Some(None),
359 Tok::Trim(mode) => Some(Some(*mode)),
360 _ => None,
361 };
362 let wrap = |kind: RefKind, sheet: SheetSel| {
363 let r = Expr::Ref(Reference { sheet, kind });
364 match trim {
365 Some(Some(mode)) => Expr::Unary(UnOp::Trim(mode), Box::new(r)),
366 _ => r,
367 }
368 };
369 if let Some(a) = word_is_cell(w) {
370 if trim.is_some()
372 && let Tok::Word(w2) = self.peek_at(1)
373 && let Some(b) = word_is_cell(w2)
374 {
375 self.next();
376 self.next();
377 return Ok(wrap(RefKind::Range(a, b), sheet));
378 }
379 let cell = Expr::Ref(Reference { sheet, kind: RefKind::Cell(a) });
380 if *self.peek() == Tok::Op("#") {
381 self.next();
382 return Ok(Expr::Unary(UnOp::Spill, Box::new(cell)));
383 }
384 return Ok(cell);
385 }
386 let second = match self.peek_at(1) {
387 Tok::Word(w2) => Some(w2.clone()),
388 Tok::Number(n) if n.fract() == 0.0 && *n >= 1.0 => Some(format!("{n}")),
389 _ => None,
390 };
391 if trim.is_some()
392 && let Some(w2) = second
393 {
394 if let (Some((c0, a0)), Some((c1, a1))) = (word_is_cols(w), word_is_cols(&w2)) {
395 self.next();
396 self.next();
397 return Ok(wrap(RefKind::Cols(c0, a0, c1, a1), sheet));
398 }
399 if let (Some((r0, a0)), Some((r1, a1))) = (word_is_row(w), word_is_row(&w2)) {
400 self.next();
401 self.next();
402 return Ok(wrap(RefKind::Rows(r0, a0, r1, a1), sheet));
403 }
404 }
405 if sheet != SheetSel::Current {
406 if let SheetSel::Named(s) = sheet {
408 return Ok(Expr::Name(format!("{s}!{w}")));
409 }
410 return Err(self.err("invalid 3-D reference"));
411 }
412 if w.chars().next().is_some_and(|c| c.is_ascii_digit()) {
413 return Err(self.err(format!("unexpected `{w}`")));
414 }
415 if let Some(f) = w.get(..7).filter(|p| p.eq_ignore_ascii_case("_xleta.")).and_then(|_| w.get(7..)) {
417 return Ok(Expr::Name(f.to_ascii_uppercase()));
418 }
419 Ok(Expr::Name(w.to_string()))
420 }
421
422 fn array(&mut self) -> Result<Expr, ParseError> {
423 let mut rows = vec![Vec::new()];
424 loop {
425 let el = match self.next() {
426 Tok::Number(n) => Expr::Number(n),
427 Tok::Op("-") => match self.next() {
428 Tok::Number(n) => Expr::Number(-n),
429 t => return Err(self.err(format!("expected a number in array, found {}", describe(&t)))),
430 },
431 Tok::Op("+") => match self.next() {
432 Tok::Number(n) => Expr::Number(n),
433 t => return Err(self.err(format!("expected a number in array, found {}", describe(&t)))),
434 },
435 Tok::Text(s) => Expr::Text(Arc::from(s)),
436 Tok::Bool(b) => Expr::Bool(b),
437 Tok::Word(w) if self.input => crate::formula::input::boolean_alias(&w)
438 .map(Expr::Bool)
439 .ok_or_else(|| self.err(format!("array constants may only contain constants, found {}", describe(&Tok::Word(w)))))?,
440 Tok::Error(e) => Expr::Error(e),
441 t => return Err(self.err(format!("array constants may only contain constants, found {}", describe(&t)))),
442 };
443 if let Some(r) = rows.last_mut() {
444 r.push(el);
445 }
446 match self.next() {
447 Tok::Comma => {}
448 Tok::Semicolon => rows.push(Vec::new()),
449 Tok::RBrace => break,
450 t => return Err(self.err(format!("expected `,`, `;` or `}}`, found {}", describe(&t)))),
451 }
452 }
453 let w = rows.first().map_or(0, Vec::len);
454 if rows.iter().any(|r| r.len() != w) {
455 return Err(self.err("array rows must have the same length"));
456 }
457 Ok(Expr::Array(rows))
458 }
459}
460
461fn combine(op: BinOp, lhs: Expr, rhs: Expr) -> Expr {
463 if op == BinOp::Range
464 && let (Expr::Ref(a), Expr::Ref(b)) = (&lhs, &rhs)
465 && b.sheet == SheetSel::Current
466 && let (RefKind::Cell(x), RefKind::Cell(y)) = (&a.kind, &b.kind)
467 {
468 return Expr::Ref(Reference { sheet: a.sheet.clone(), kind: RefKind::Range(*x, *y) });
469 }
470 Expr::Binary(op, Box::new(lhs), Box::new(rhs))
471}
472
473pub fn parse_struct(table: &str, body: &str) -> Result<StructRef, String> {
477 let mut specifiers = Vec::new();
478 let mut cols: Vec<String> = Vec::new();
479 let raw = body;
482 let body = body.trim();
483 let unescape = |s: &str| {
484 let mut out = String::new();
485 let mut it = s.chars();
486 while let Some(c) = it.next() {
487 if c == '\'' {
488 if let Some(n) = it.next() {
489 out.push(n);
490 }
491 } else {
492 out.push(c);
493 }
494 }
495 out
496 };
497 let item = |s: &str| -> Option<StructItem> {
498 match s.trim().to_ascii_lowercase().as_str() {
499 "#all" => Some(StructItem::All),
500 "#data" => Some(StructItem::Data),
501 "#headers" => Some(StructItem::Headers),
502 "#totals" => Some(StructItem::Totals),
503 "#this row" => Some(StructItem::ThisRow),
504 _ => None,
505 }
506 };
507 let unexpected = |gap: &str| format!("unexpected `{gap}` in structured reference");
508 let column = |s: &str| -> Result<String, String> {
510 let mut esc = false;
511 for c in s.chars() {
512 match c {
513 _ if esc => esc = false,
514 '\'' => esc = true,
515 '[' | ']' => return Err(unexpected(s)),
516 _ => {}
517 }
518 }
519 Ok(unescape(s))
520 };
521 if !body.starts_with('[') {
522 if let Some(rest) = body.strip_prefix('@') {
524 specifiers.push(StructItem::ThisRow);
525 let rest = rest.trim();
526 let rest = rest.strip_prefix('[').and_then(|r| r.strip_suffix(']')).unwrap_or(rest);
527 if !rest.is_empty() {
528 cols.push(column(rest)?);
529 }
530 } else if let Some(i) = item(body) {
531 specifiers.push(i);
532 } else if !body.is_empty() {
533 cols.push(column(raw)?);
534 }
535 } else {
536 let mut parts = Vec::new();
538 let mut depth = 0;
539 let mut cur = String::new();
540 let mut gap = String::new();
542 let mut esc = false;
543 for c in body.chars() {
544 if esc {
545 cur.push(c);
546 esc = false;
547 continue;
548 }
549 match c {
550 '\'' if depth > 0 => {
551 cur.push(c);
552 esc = true;
553 }
554 '[' => {
555 if depth == 0 {
556 if !matches!(gap.trim(), "" | "," | ":") {
557 return Err(unexpected(gap.trim()));
558 }
559 gap.clear();
560 }
561 depth += 1;
562 if depth > 1 {
563 cur.push(c);
564 }
565 }
566 ']' => {
567 if depth == 0 {
568 return Err(unexpected("]"));
569 }
570 depth -= 1;
571 if depth > 0 {
572 cur.push(c);
573 } else {
574 parts.push(std::mem::take(&mut cur));
575 }
576 }
577 _ if depth > 0 => cur.push(c),
578 _ => gap.push(c),
579 }
580 }
581 if depth > 0 {
582 return Err("unclosed `[` in structured reference".to_string());
583 }
584 for p in parts {
585 if let Some(i) = item(&p) {
586 specifiers.push(i);
587 } else {
588 cols.push(column(&p)?);
589 }
590 }
591 let tail = gap.trim();
592 if !tail.is_empty() {
593 let bare = tail.strip_prefix(',').map(str::trim).unwrap_or("");
594 let simple = !bare.is_empty() && !bare.chars().any(|c| matches!(c, '[' | ']' | '#' | '\'' | ',' | ':'));
595 if !(simple && specifiers == [StructItem::ThisRow] && cols.is_empty()) {
596 return Err(unexpected(tail));
597 }
598 cols.push(bare.to_string());
599 }
600 }
601 if cols.len() > 2 {
602 return Err("a structured reference names at most two columns".to_string());
603 }
604 let mut it = cols.into_iter();
605 let col_start = it.next();
606 let col_end = it.next();
607 Ok(StructRef { table: table.to_string(), specifiers, col_start, col_end })
608}