recur_func_parser/
lib.rs

1use pest::Parser;
2use pest_derive::Parser;
3use std::collections::HashMap;
4use thiserror::Error;
5
6
7#[derive(Parser)]
8#[grammar = "./grammar.pest"]
9/// The grammar parser for recusrive functions based on Pest grammar definition.
10pub struct RecurFunctionGrammar;
11
12#[derive(Debug, Error)]
13/// Errors which can apear when parsing.
14pub enum RecurFunctionParseError {
15    #[error("Invalid projection argument number: {0}")]
16    /// Error which signals that argument number in projection function is invalid.
17    InvalidProjectionArgumentNumber(String),
18    #[error("Invalid composition functions count: {0}")]
19    /// Error which signals about invalid number of functions in composition function.
20    InvalidCompositionFunctionsCount(String),
21    #[error("Invalid primitive base arguments count: {0}")]
22    /// Error which signals that base function in primitive function has invalid arguments count.
23    InvalidPrimitiveBaseArgumentsCount(String),
24    #[error("Invalid primitive step arguments count: {0}")]
25    /// Error which signals that step function in primitive function has invalid arguments count.
26    InvalidPrimitiveStepArgumentsCount(String),
27    #[error("Invalid arguments count: {0}")]
28    /// Error which signals that function has invalid arguments count.
29    InvalidArgumentsCount(String),
30    #[error("Expected function, but it wasn't there: {0}")]
31    /// Error which signals that function was expected, but not found.
32    FunctionExpected(String),
33    #[error("Expected integer, but it wasn't there: {0}")]
34    /// Error which signals that integer was expected, but not found.
35    IntegerExpected(String),
36    #[error("Expected identifier, but it wasn't there: {0}")]
37    /// Error which signals that identifier was expected, but not found.
38    IdentifierExpected(String),
39    #[error("Failed to parse int: {0}")]
40    /// Error which signals that string cannot be converted to u32.
41    ParseIntError(#[from] std::num::ParseIntError),
42    #[error("Undefined identifier while parsing: {0}")]
43    /// Error which signals that identifier is undefined.
44    UndefinedIdentifier(String),
45    #[error("Identifier already exists: {0}")]
46    /// Error which signals that identifier already exists.
47    IdentifierAlreadyExists(String),
48    #[error("Undefined rule while parsing: {0}")]
49    /// Error which signals that rule is undefined.
50    UndefinedRule(String),
51}
52
53#[derive(Debug, Clone, PartialEq)]
54/// Types of recursive functions.
55pub enum RecurFunctionType {
56    /// zero function.
57    Zero,
58    /// succesor function.
59    Successor,
60    /// projection function with arguments count and argument number.
61    Projection(u32, u32),
62    /// composition function with base function and functions to use.
63    Composition(Box<RecurFunction>, Vec<RecurFunction>),
64    /// primitive function with base function and step function.
65    Primitive(Box<RecurFunction>, Box<RecurFunction>),
66    /// minimization function with base function and max tries.
67    Minimization(Box<RecurFunction>, u32),
68}
69
70#[derive(Debug, Clone, PartialEq)]
71/// Struct which describes recursive function.
72pub struct RecurFunction {
73    /// function type.
74    function_type: RecurFunctionType,
75    /// function arguments count.
76    arguments_count: u32,
77    /// contains number if function is number otherwise None.
78    number: Option<u32>,
79}
80
81/// Struct which describes query.
82pub struct Query {
83    /// identifier of function to use for query.
84    identifier: String,
85    /// arguments for function.
86    arguments: Vec<u32>,
87}
88
89/// Parses recursive function pair into RecurFunction struct.
90///
91/// # Arguments
92///
93/// * `pair` - pest pair that is recursive function.
94/// * `identifier_functions` - parsed identifiers and their function, uses for checking existing functions.
95///
96/// # Returns
97///
98/// The parsed recursive function or RecurFunctionParseError wraped in Result.
99pub fn parse_recur_function(
100    pair: pest::iterators::Pair<Rule>,
101    identifier_functions: &HashMap<String, RecurFunction>,
102) -> Result<RecurFunction, RecurFunctionParseError> {
103    let pair_str = pair.as_str();
104    match pair.as_rule() {
105        Rule::zero => Ok(RecurFunction {
106            function_type: RecurFunctionType::Zero,
107            arguments_count: 1,
108            number: Some(0),
109        }),
110        Rule::successor => Ok(RecurFunction {
111            function_type: RecurFunctionType::Successor,
112            arguments_count: 1,
113            number: None,
114        }),
115        Rule::projection => {
116            let mut inner_pairs = pair.into_inner();
117            let arguments_count: u32 = inner_pairs
118                .next()
119                .ok_or(RecurFunctionParseError::IntegerExpected(
120                    pair_str.to_string(),
121                ))?
122                .as_str()
123                .parse::<u32>()?;
124            let argument_number: u32 = inner_pairs
125                .next()
126                .ok_or(RecurFunctionParseError::IntegerExpected(
127                    pair_str.to_string(),
128                ))?
129                .as_str()
130                .parse::<u32>()?;
131            if argument_number == 0 {
132                return Err(RecurFunctionParseError::InvalidProjectionArgumentNumber(
133                    pair_str.to_string(),
134                ));
135            }
136            if arguments_count < argument_number {
137                return Err(RecurFunctionParseError::InvalidArgumentsCount(
138                    pair_str.to_string(),
139                ));
140            }
141            Ok(RecurFunction {
142                function_type: RecurFunctionType::Projection(arguments_count, argument_number),
143                arguments_count,
144                number: None,
145            })
146        }
147        Rule::composition => {
148            let mut inner_pairs = pair.into_inner();
149            let base_function = parse_recur_function(
150                inner_pairs
151                    .next()
152                    .ok_or(RecurFunctionParseError::FunctionExpected(
153                        pair_str.to_string(),
154                    ))?,
155                identifier_functions,
156            )?;
157            let mut functions: Vec<RecurFunction> = Vec::new();
158            let mut arguments_count: u32 = 0;
159            for inner_pair in inner_pairs {
160                let function = parse_recur_function(inner_pair, identifier_functions)?;
161                if arguments_count == 0 {
162                    arguments_count = function.arguments_count;
163                } else if arguments_count != function.arguments_count {
164                    return Err(RecurFunctionParseError::InvalidArgumentsCount(
165                        pair_str.to_string(),
166                    ));
167                }
168                functions.push(function);
169            }
170            if functions.len() != base_function.arguments_count as usize {
171                return Err(RecurFunctionParseError::InvalidCompositionFunctionsCount(
172                    pair_str.to_string(),
173                ));
174            }
175            if arguments_count == 1
176                && functions.len() == 1
177                && functions[0].number.is_some()
178                && base_function.function_type == RecurFunctionType::Successor
179            {
180                let number = functions[0].number.unwrap() + 1;
181                return Ok(RecurFunction {
182                    function_type: RecurFunctionType::Composition(
183                        Box::new(base_function),
184                        functions,
185                    ),
186                    arguments_count,
187                    number: Some(number),
188                });
189            }
190            Ok(RecurFunction {
191                function_type: RecurFunctionType::Composition(Box::new(base_function), functions),
192                arguments_count,
193                number: None,
194            })
195        }
196        Rule::primitive => {
197            let mut inner_pairs = pair.into_inner();
198            let base_function = parse_recur_function(
199                inner_pairs
200                    .next()
201                    .ok_or(RecurFunctionParseError::FunctionExpected(
202                        pair_str.to_string(),
203                    ))?,
204                identifier_functions,
205            )?;
206            let step_function = parse_recur_function(
207                inner_pairs
208                    .next()
209                    .ok_or(RecurFunctionParseError::FunctionExpected(
210                        pair_str.to_string(),
211                    ))?,
212                identifier_functions,
213            )?;
214            if step_function.arguments_count < 2 {
215                return Err(RecurFunctionParseError::InvalidPrimitiveStepArgumentsCount(
216                    pair_str.to_string(),
217                ));
218            }
219            if step_function.arguments_count == 2
220                && (base_function.arguments_count != 1 || base_function.number.is_none())
221            {
222                return Err(RecurFunctionParseError::InvalidPrimitiveBaseArgumentsCount(
223                    pair_str.to_string(),
224                ));
225            }
226            if step_function.arguments_count > 2
227                && base_function.arguments_count != step_function.arguments_count - 2
228            {
229                return Err(RecurFunctionParseError::InvalidPrimitiveBaseArgumentsCount(
230                    pair_str.to_string(),
231                ));
232            }
233            let arguments_count = step_function.arguments_count - 1;
234            Ok(RecurFunction {
235                function_type: RecurFunctionType::Primitive(
236                    Box::new(base_function),
237                    Box::new(step_function),
238                ),
239                arguments_count,
240                number: None,
241            })
242        }
243        Rule::minimization => {
244            let mut inner_pairs = pair.into_inner();
245            let base_function = parse_recur_function(
246                inner_pairs
247                    .next()
248                    .ok_or(RecurFunctionParseError::FunctionExpected(
249                        pair_str.to_string(),
250                    ))?,
251                identifier_functions,
252            )?;
253            let max: u32 = inner_pairs
254                .next()
255                .ok_or(RecurFunctionParseError::IntegerExpected(
256                    pair_str.to_string(),
257                ))?
258                .as_str()
259                .parse::<u32>()?;
260            if base_function.arguments_count <= 1 {
261                return Err(RecurFunctionParseError::InvalidArgumentsCount(
262                    pair_str.to_string(),
263                ));
264            }
265            let arguments_count = base_function.arguments_count - 1;
266            Ok(RecurFunction {
267                function_type: RecurFunctionType::Minimization(Box::new(base_function), max),
268                arguments_count,
269                number: None,
270            })
271        }
272        Rule::identifier => {
273            let identifier: String = pair.as_str().to_string();
274            let function = identifier_functions
275                .get(&identifier)
276                .ok_or(RecurFunctionParseError::UndefinedIdentifier(
277                    pair.as_str().to_string(),
278                ))?
279                .clone();
280            Ok(function)
281        }
282        Rule::recursive_function => parse_recur_function(
283            pair.into_inner()
284                .next()
285                .ok_or(RecurFunctionParseError::FunctionExpected(
286                    pair_str.to_string(),
287                ))?,
288            identifier_functions,
289        ),
290        _ => Err(RecurFunctionParseError::UndefinedRule(
291            pair.as_str().to_string(),
292        )),
293    }
294}
295
296/// Parses recursive functions input into HashMap<String, RecurFunction> where key is identifier and value is its recursive function.
297///
298/// # Arguments
299///
300/// * `input` - string which includes recursive functions.
301///
302/// # Returns
303///
304/// HashMap<String, RecurFunction> where key is identifier and value is its recursive function or RecurFunctionParseError wraped into Result.
305pub fn parse_recur_functions(
306    input: &str,
307) -> Result<HashMap<String, RecurFunction>, RecurFunctionParseError> {
308    let got = RecurFunctionGrammar::parse(Rule::functions, input);
309    let mut inner_pairs = match got {
310        Ok(mut got) => got
311            .next()
312            .ok_or(RecurFunctionParseError::UndefinedRule(input.to_string()))?
313            .into_inner(),
314        Err(e) => return Err(RecurFunctionParseError::UndefinedRule(e.to_string())),
315    };
316    let mut identifier_functions = HashMap::<String, RecurFunction>::new();
317    while let Some(inner_pair) = inner_pairs.next() {
318        if inner_pair.as_rule() == Rule::EOI {
319            break;
320        }
321        let identifier: String = match inner_pair.as_rule() {
322            Rule::identifier => inner_pair.as_str().to_string(),
323            _ => {
324                return Err(RecurFunctionParseError::IdentifierExpected(
325                    inner_pair.as_str().to_string(),
326                ))
327            }
328        };
329        if identifier_functions.contains_key(&identifier) {
330            return Err(RecurFunctionParseError::IdentifierAlreadyExists(identifier));
331        }
332        let inner_pair = inner_pairs
333            .next()
334            .ok_or(RecurFunctionParseError::FunctionExpected(input.to_string()))?;
335        let recur_function: RecurFunction = match inner_pair.as_rule() {
336            Rule::recursive_function => parse_recur_function(inner_pair, &identifier_functions)?,
337            _ => {
338                return Err(RecurFunctionParseError::FunctionExpected(
339                    inner_pair.as_str().to_string(),
340                ))
341            }
342        };
343        identifier_functions.insert(identifier, recur_function);
344    }
345    Ok(identifier_functions)
346}
347
348/// Parses query input string into Query struct.
349///
350/// # Arguments
351///
352/// * `input` - string which includes query.
353/// * `identifier_functions` - parsed identifiers and their function, uses for checking existing functions.
354///
355/// # Returns
356///
357/// parsed query or RecurFunctionParseError wraped into Result.
358pub fn parse_query(
359    input: &str,
360    identifier_functions: &HashMap<String, RecurFunction>,
361) -> Result<Query, RecurFunctionParseError> {
362    let got = RecurFunctionGrammar::parse(Rule::query, input);
363    let mut inner_pairs = match got {
364        Ok(mut got) => got
365            .next()
366            .ok_or(RecurFunctionParseError::UndefinedRule(input.to_string()))?
367            .into_inner(),
368        Err(_) => return Err(RecurFunctionParseError::UndefinedRule(input.to_string())),
369    };
370    let inner_pair = inner_pairs
371        .next()
372        .ok_or(RecurFunctionParseError::IdentifierExpected(
373            input.to_string(),
374        ))?;
375    let identifier: String = match inner_pair.as_rule() {
376        Rule::identifier => inner_pair.as_str().to_string(),
377        _ => {
378            return Err(RecurFunctionParseError::IdentifierExpected(
379                inner_pair.as_str().to_string(),
380            ))
381        }
382    };
383    if !identifier_functions.contains_key(&identifier) {
384        return Err(RecurFunctionParseError::UndefinedIdentifier(
385            input.to_string(),
386        ));
387    }
388    let function = identifier_functions.get(&identifier).ok_or(
389        RecurFunctionParseError::UndefinedIdentifier(input.to_string()),
390    )?;
391    let mut arguments = Vec::<u32>::new();
392    for inner_pair in inner_pairs {
393        if inner_pair.as_rule() == Rule::EOI {
394            break;
395        }
396        let integer: u32 = match inner_pair.as_rule() {
397            Rule::integer => inner_pair.as_str().parse::<u32>()?,
398            _ => {
399                return Err(RecurFunctionParseError::IntegerExpected(
400                    inner_pair.as_str().to_string(),
401                ))
402            }
403        };
404        arguments.push(integer);
405    }
406    if function.number.is_some() && arguments.is_empty() {
407        return Ok(Query {
408            identifier,
409            arguments,
410        });
411    } else if function.arguments_count != arguments.len() as u32 {
412        return Err(RecurFunctionParseError::InvalidArgumentsCount(
413            input.to_string(),
414        ));
415    }
416    Ok(Query {
417        identifier,
418        arguments,
419    })
420}
421
422/// Parses given recursive functions on given arguments.
423///
424/// # Arguments
425///
426/// * `function` - function to execute.
427/// * `arguments` - arguments to use for calculations.
428///
429/// # Returns
430///
431/// Some(u32) if result is defined otherwise None.
432pub fn execute(function: &RecurFunction, arguments: &Vec<u32>) -> Option<u32> {
433    match &function.function_type {
434        RecurFunctionType::Zero => Some(0),
435        RecurFunctionType::Successor => Some(arguments.first()? + 1),
436        RecurFunctionType::Projection(_, argument_number) => {
437            let res = arguments.get(*argument_number as usize - 1)?;
438            Some(*res)
439        }
440        RecurFunctionType::Composition(base_function, functions) => {
441            let mut functions_results: Vec<u32> = Vec::<u32>::new();
442            for func in functions {
443                functions_results.push(execute(func, arguments)?);
444            }
445            execute(base_function, &functions_results)
446        }
447        RecurFunctionType::Primitive(base_function, step_function) => {
448            let mut res: u32;
449            let mut arguments = arguments.clone();
450            let max: u32 = arguments.pop()?;
451            if let Some(number) = base_function.number {
452                res = number;
453            } else {
454                res = execute(base_function, &arguments)?;
455            }
456            for i in 0..max {
457                let mut new_arguments = arguments.clone();
458                new_arguments.push(i);
459                new_arguments.push(res);
460                res = execute(step_function, &new_arguments)?;
461            }
462            Some(res)
463        }
464        RecurFunctionType::Minimization(base_function, max) => {
465            for i in 0..=*max {
466                let mut new_arguments = arguments.clone();
467                new_arguments.push(i);
468                if execute(base_function, &new_arguments)? == 0 {
469                    return Some(i);
470                }
471            }
472            None
473        }
474    }
475}
476
477/// Parses given query on given possible functions.
478///
479/// # Arguments
480///
481/// * `query` - function to execute.
482/// * `identifier_functions` - parsed identifiers and their function, uses for checking existing functions.
483///
484/// # Returns
485///
486/// Some(u32) if result is defined otherwise None.
487pub fn execute_query(
488    query: &Query,
489    identifier_functions: &HashMap<String, RecurFunction>,
490) -> Option<u32> {
491    let function: &RecurFunction = identifier_functions.get(&query.identifier)?;
492    if let Some(number) = function.number {
493        return Some(number);
494    }
495    execute(function, &query.arguments)
496}
recur_func_parser/lib.rs

recur_func_parser/
lib.rs
