algebra/
steenrod_parser.rs

1//! This module includes code for parsing an expression in the Steenrod algebra into an abstract
2//! syntax tree.
3
4use std::str::FromStr;
5
6use anyhow::{Context, anyhow};
7use nom::{
8    IResult as IResultBase, Parser,
9    branch::alt,
10    bytes::complete::tag,
11    character::complete::{alpha1, alphanumeric0, char, digit1 as digit, space0},
12    combinator::{map, map_res, opt, peek},
13    error::{ErrorKind, ParseError, context},
14    multi::{many0, separated_list1},
15    sequence::{delimited, pair, preceded},
16};
17
18use crate::{adem_algebra::AdemBasisElement, algebra::milnor_algebra::PPart};
19
20type IResult<I, O> = IResultBase<I, O, nom::error::Error<I>>;
21
22#[derive(Debug, Clone)]
23pub enum AlgebraBasisElt {
24    AList(Vec<BocksteinOrSq>), // Admissible list.
25    PList(PPart),
26    P(u32),
27    Q(u32),
28}
29
30#[derive(Debug, Clone)]
31pub enum AlgebraNode {
32    Product(Box<Self>, Box<Self>),
33    Sum(Box<Self>, Box<Self>),
34    BasisElt(AlgebraBasisElt),
35    Scalar(i32),
36}
37
38pub type ModuleNode = Vec<(AlgebraNode, String)>;
39
40/// Pad both ends with whitespace
41pub(crate) fn space<'a, O, E: ParseError<&'a str>, F: Parser<&'a str, Output = O, Error = E>>(
42    f: F,
43) -> impl Parser<&'a str, Output = O, Error = E> {
44    delimited(space0, f, space0)
45}
46
47/// Surround with brackets
48pub(crate) fn brackets<'a, O, E: ParseError<&'a str>, F: Parser<&'a str, Output = O, Error = E>>(
49    f: F,
50) -> impl Parser<&'a str, Output = O, Error = E> {
51    delimited(char('('), f, char(')'))
52}
53
54pub(crate) fn digits<T: FromStr + Copy>(i: &str) -> IResult<&str, T> {
55    map_res(space(digit), FromStr::from_str).parse(i)
56}
57
58pub(crate) fn p_or_sq(i: &str) -> IResult<&str, &str> {
59    alt((tag("P"), tag("Sq"))).parse(i)
60}
61
62fn fold_separated<I: Clone, OS, O, E>(
63    mut sep: impl Parser<I, Output = OS, Error = E>,
64    mut f: impl Parser<I, Output = O, Error = E>,
65    mut acc: impl FnMut(O, O) -> O,
66) -> impl FnMut(I) -> IResultBase<I, O, E> {
67    move |i: I| {
68        let (mut i, mut res) = f.parse(i)?;
69        loop {
70            match sep.parse(i.clone()) {
71                Err(nom::Err::Error(_)) => return Ok((i, res)),
72                Err(e) => return Err(e),
73                Ok((i1, _)) => match f.parse(i1.clone()) {
74                    Err(nom::Err::Error(_)) => return Ok((i, res)),
75                    Err(e) => return Err(e),
76                    Ok((i2, o)) => {
77                        i = i2;
78                        res = acc(res, o);
79                    }
80                },
81            }
82        }
83    }
84}
85
86#[derive(Clone, Debug, Copy)]
87pub enum BocksteinOrSq {
88    Bockstein,
89    Sq(u32),
90}
91
92impl BocksteinOrSq {
93    pub(crate) fn to_adem_basis_elt(self, q: i32) -> AdemBasisElement {
94        match self {
95            Self::Bockstein => {
96                if q == 1 {
97                    AdemBasisElement {
98                        degree: 1,
99                        bocksteins: 0,
100                        ps: vec![1],
101                        p_or_sq: false,
102                    }
103                } else {
104                    AdemBasisElement {
105                        degree: 1,
106                        bocksteins: 1,
107                        ps: vec![],
108                        p_or_sq: true,
109                    }
110                }
111            }
112            Self::Sq(x) => AdemBasisElement {
113                degree: x as i32 * q,
114                bocksteins: 0,
115                ps: vec![x],
116                p_or_sq: q != 1,
117            },
118        }
119    }
120}
121
122fn algebra_generator(i: &str) -> IResult<&str, AlgebraBasisElt> {
123    alt((
124        map(char('b'), |_| AlgebraBasisElt::Q(0)),
125        map(preceded(char('Q'), digits), AlgebraBasisElt::Q),
126        map(preceded(p_or_sq, digits), AlgebraBasisElt::P),
127        map(
128            alt((
129                preceded(p_or_sq, brackets(separated_list1(char(','), digits))),
130                preceded(char('M'), brackets(many0(digits))),
131            )),
132            AlgebraBasisElt::PList,
133        ),
134        map(
135            preceded(
136                char('A'),
137                brackets(many0(alt((
138                    map(char('b'), |_| BocksteinOrSq::Bockstein),
139                    map(digits, BocksteinOrSq::Sq),
140                )))),
141            ),
142            AlgebraBasisElt::AList,
143        ),
144    ))
145    .parse(i)
146}
147
148fn scalar(i: &str) -> IResult<&str, i32> {
149    alt((
150        digits,
151        preceded(char('+'), digits),
152        map(preceded(char('-'), digits), |x: i32| -x),
153    ))
154    .parse(i)
155}
156
157fn algebra_factor(i: &str) -> IResult<&str, AlgebraNode> {
158    space(alt((
159        map(algebra_generator, AlgebraNode::BasisElt),
160        map(scalar, AlgebraNode::Scalar),
161        brackets(algebra_expr),
162    )))
163    .parse(i)
164}
165
166fn algebra_term(i: &str) -> IResult<&str, AlgebraNode> {
167    let (i, sign) = opt(alt((char('+'), char('-')))).parse(i)?;
168
169    let (i, mut res) = fold_separated(char('*'), algebra_factor, |acc, val| {
170        AlgebraNode::Product(Box::new(acc), Box::new(val))
171    })(i)?;
172
173    if let Some('-') = sign {
174        res = AlgebraNode::Product(Box::new(AlgebraNode::Scalar(-1)), Box::new(res));
175    }
176    Ok((i, res))
177}
178
179fn algebra_expr(i: &str) -> IResult<&str, AlgebraNode> {
180    fold_separated(
181        peek(alt((char('+'), char('-')))),
182        space(algebra_term),
183        |acc, val| AlgebraNode::Sum(Box::new(acc), Box::new(val)),
184    )(i)
185}
186
187fn module_generator(i: &str) -> IResult<&str, String> {
188    let (rest, (a, more_str)) = pair(alpha1, alphanumeric0).parse(i)?;
189    if a.starts_with("Sq") || a.starts_with('P') || a.starts_with('Q') {
190        return Err(nom::Err::Failure(nom::error::Error::new(
191            &i[0..a.len()],
192            ErrorKind::Verify,
193        )));
194    }
195    Ok((rest, a.to_string() + more_str))
196}
197
198fn module_term(i: &str) -> IResult<&str, ModuleNode> {
199    use AlgebraNode::*;
200
201    let (i, prefix) = opt(alt((
202        map(pair(space(algebra_term), char('*')), |(a, _)| a),
203        map(char('-'), |_| Scalar(-1)),
204        map(char('+'), |_| Scalar(1)),
205    )))
206    .parse(i)?;
207
208    match space(module_generator).parse(i) {
209        Ok((i, g)) => return Ok((i, vec![(prefix.unwrap_or(Scalar(1)), g)])),
210        Err(nom::Err::Error(_)) => (),
211        Err(e) => return Err(e),
212    }
213
214    let (i, expr) =
215        context("Parsing bracketed expression", space(brackets(module_expr))).parse(i)?;
216    Ok((
217        i,
218        match prefix {
219            Some(a) => expr
220                .into_iter()
221                .map(|(b, v)| (Product(Box::new(a.clone()), Box::new(b)), v))
222                .collect(),
223            None => expr,
224        },
225    ))
226}
227
228fn module_expr(i: &str) -> IResult<&str, ModuleNode> {
229    fold_separated(
230        peek(alt((char('+'), char('-')))),
231        module_term,
232        |mut a, b| {
233            a.extend_from_slice(&b);
234            a
235        },
236    )(i)
237}
238
239fn convert_error(i: &str) -> impl FnOnce(nom::Err<nom::error::Error<&str>>) -> anyhow::Error + '_ {
240    move |err| {
241        anyhow!(match err {
242            nom::Err::Error(e) | nom::Err::Failure(e) => format!(
243                "Parse error at position {}: {:?}",
244                i.len() - e.input.len(),
245                e.code
246            ),
247            _ => format!("{err:#}"),
248        })
249    }
250}
251
252pub fn parse_algebra(i: &str) -> anyhow::Result<AlgebraNode> {
253    let (rest, parse_tree) = algebra_expr(i)
254        .map_err(convert_error(i))
255        .with_context(|| format!("Error when parsing algebra string {i}"))?;
256    if rest.is_empty() {
257        Ok(parse_tree)
258    } else {
259        Err(anyhow!(
260            "Failed to consume all of input. Remaining: '{rest}'"
261        ))
262    }
263}
264
265pub fn parse_module(i: &str) -> anyhow::Result<ModuleNode> {
266    let (rest, parse_tree) = module_expr(i)
267        .map_err(convert_error(i))
268        .with_context(|| format!("Error when parsing module string {i}"))?;
269    if rest.is_empty() {
270        Ok(parse_tree)
271    } else {
272        Err(anyhow!(
273            "Failed to consume all of input. Remaining: '{rest}'"
274        ))
275    }
276}
277
278#[cfg(test)]
279mod tests {
280    use expect_test::{Expect, expect};
281
282    use super::*;
283
284    #[test]
285    fn test_parse_algebra() {
286        let check = |input, output: Expect| {
287            output.assert_eq(&format!("{:?}", parse_algebra(input).unwrap()));
288        };
289
290        check(
291            "b * Q3 * (Sq1 * A(2 b 5) + M(0 0 2) * P(0, 1) * Sq(1, 0))",
292            expect![[
293                r#"Product(Product(BasisElt(Q(0)), BasisElt(Q(3))), Sum(Product(BasisElt(P(1)), BasisElt(AList([Sq(2), Bockstein, Sq(5)]))), Product(Product(BasisElt(PList([0, 0, 2])), BasisElt(PList([0, 1]))), BasisElt(PList([1, 0])))))"#
294            ]],
295        );
296    }
297
298    #[test]
299    fn test_parse_module() {
300        let check = |input, output: Expect| {
301            output.assert_eq(&format!("{:?}", parse_module(input).unwrap()));
302        };
303
304        check("x0", expect![[r#"[(Scalar(1), "x0")]"#]]);
305
306        check("Sq2 * x0", expect![[r#"[(BasisElt(P(2)), "x0")]"#]]);
307
308        check(
309            "Sq1 * x0 + x1",
310            expect![[r#"[(BasisElt(P(1)), "x0"), (Scalar(1), "x1")]"#]],
311        );
312
313        check(
314            "(Sq3 + Sq2 * Sq1) * x0",
315            expect![[r#"[(Sum(BasisElt(P(3)), Product(BasisElt(P(2)), BasisElt(P(1)))), "x0")]"#]],
316        );
317
318        check(
319            "Sq3 * x0 + Sq2 * x1",
320            expect![[r#"[(BasisElt(P(3)), "x0"), (BasisElt(P(2)), "x1")]"#]],
321        );
322
323        check(
324            "(Sq3 - Sq2 * Sq1) * (Sq1 * x0 + x1)",
325            expect![[
326                r#"[(Product(Sum(BasisElt(P(3)), Product(Scalar(-1), Product(BasisElt(P(2)), BasisElt(P(1))))), BasisElt(P(1))), "x0"), (Product(Sum(BasisElt(P(3)), Product(Scalar(-1), Product(BasisElt(P(2)), BasisElt(P(1))))), Scalar(1)), "x1")]"#
327            ]],
328        );
329
330        check(
331            "x3 - (Sq3 * x0 + Sq1 * x2)",
332            expect![[
333                r#"[(Scalar(1), "x3"), (Product(Scalar(-1), BasisElt(P(3))), "x0"), (Product(Scalar(-1), BasisElt(P(1))), "x2")]"#
334            ]],
335        );
336    }
337
338    #[test]
339    fn test_parse_module_errors() {
340        // Checking the error output breaks because it depends on whether backtraces are available.
341        let check = |input| {
342            assert!(parse_module(input).is_err());
343        };
344
345        check("x0 + ");
346        check("2 * (x1 + Sq1 * x0");
347        check("Sqx");
348    }
349}
algebra/steenrod_parser.rs

algebra/
steenrod_parser.rs
