# Neotoma

A flexible, cached parser combinator framework for Rust with built-in memoization and backtracking capabilities.

## Features

- **Parser Combinators**: Compose complex parsers from simple building blocks
- **Built-in Caching**: Automatic memoization prevents redundant parsing work
- **Backtracking Support**: Efficient backtracking with automatic position management
- **UTF-8 Aware**: Dual-level design supporting both byte-level and character-level parsing
- **Generic Input Sources**: Works with any `Read + Seek` implementation
- **Thread Safe**: Uses `parking_lot` for efficient synchronization primitives
- **Grammar Support**: Self-parsing grammar system for complex syntax definitions

## Quick Start

Add Neotoma to your `Cargo.toml`:

```toml
[dependencies]
neotoma = "0.1"
```

### Basic Example

```rust
use neotoma::prelude::*;
use neotoma::{seq, oneof};
use std::io::Cursor;

// Parse "hello world" with optional whitespace
let parser = seq![
    Literal::from_str("hello"),
    Optional::new(Utf8Class::whitespace()),
    Literal::from_str("world")
];

let input = Cursor::new(b"hello world");
let mut source = Source::new(input);

match parse(parser, &mut source) {
    Ok(result) => println!("Parsed: {:?}", result),
    Err(e) => println!("Parse error: {:?}", e),
}
```

### Character Classes

```rust
use neotoma::prelude::*;

// Parse one or more digits
let numbers = Utf8Class::with_min("0123456789", 1);

// Parse alphabetic characters
let letters = Utf8Class::alpha();

// Parse alphanumeric with bounds
let identifier = Utf8Class::alphanumeric().with_bounds(1, 20);
```

### Composition with Macros

```rust
use neotoma::{seq, oneof};
use neotoma::prelude::*;

// Sequential composition
let sequence = seq![
    Literal::from_str("if"),
    Utf8Class::whitespace(),
    Literal::from_str("true")
];

// Alternative composition  
let choice = oneof![
    Literal::from_str("true"),
    Literal::from_str("false"),
    Utf8Class::digits()
];
```

### Repetition and Lists

```rust
use neotoma::prelude::*;

// Zero or more digits
let numbers = Repeat::new(Utf8Class::digits());

// Comma-separated list
let csv = Repeat::new(Utf8Class::alpha())
    .with_joint(Literal::from_str(","));

// Bounded repetition
let bounded = Repeat::new(Utf8Class::alpha())
    .with_bounds(2, 5);
```

## Grammar System

Neotoma includes a self-parsing grammar system that allows you to
define complex parsers using a declarative syntax. The `GrammarParser`
can parse grammar definitions and produce executable parsers.

### Basic Usage

```rust
use neotoma::grammar::GrammarParser;
use neotoma::prelude::*;
use std::io::Cursor;

let grammar_text = r#"
    @start expression
    expression = (number "+" number)
    number = digits
"#;

let grammar_parser = GrammarParser::new();
let mut input = Cursor::new(grammar_text.as_bytes());
let mut source = Source::new(&mut input);

let grammar = parse(grammar_parser, &mut source).unwrap();

// Use the grammar to parse expressions
let mut expr_input = Cursor::new(b"42+24");
let mut expr_source = Source::new(&mut expr_input);
let result = parse(grammar, &mut expr_source).unwrap();
```

### Grammar Syntax

#### Terminals and Literals
- `"text"` - matches literal string (use `\"` for escaped quotes)
- `eof` - matches end of file (ensures complete input consumption)

#### Character Classes
- `digits` - matches one or more decimal digits (0-9)
- `alpha` - matches one or more alphabetic characters (ASCII)
- `alphanumeric` - matches one or more alphanumeric characters (ASCII) 
- `whitespace` - matches one or more whitespace characters (ASCII)
- `hexdigits` - matches one or more hexadecimal digits (0-9, a-f, A-F)
- `udigits`, `ualpha`, `ualphanumeric`, `uwhitespace` - UTF-8 equivalents
- `[abc]` - matches any character in the set (custom UTF-8 character class)
- `[^abc]` - matches any character NOT in the set (negated UTF-8 character class)

#### Composition
- `(A B C)` - matches A followed by B followed by C (sequence)
- `(| A B C)` - matches either A or B or C (alternatives)

#### Repetition
- `(* A)` - matches zero or more instances of A
- `(+ A)` - matches one or more instances of A  
- `(? A)` - matches zero or one instances of A
- `(* A / B)` - matches zero or more A's separated by B
- `(+ A / B)` - matches one or more A's separated by B

#### Rules and References
- `name = rule` - defines a named parsing rule
- `name` - references a named rule (enables recursion)
- `@start name` - sets the starting rule (defaults to last rule if not specified)

### Complex Grammar Example

```rust
let arithmetic_grammar = r#"
    @start complete_expression
    
    complete_expression = (expression eof)
    expression = additive_expr
    
    additive_expr = (| addition subtraction multiplicative_expr)
    addition = (multiplicative_expr (? whitespace) "+" (? whitespace) additive_expr)
    subtraction = (multiplicative_expr (? whitespace) "-" (? whitespace) additive_expr)
    
    multiplicative_expr = (| multiplication division primary_expr)
    multiplication = (primary_expr (? whitespace) "*" (? whitespace) multiplicative_expr)
    division = (primary_expr (? whitespace) "/" (? whitespace) multiplicative_expr)
    
    primary_expr = (| number variable parenthesized_expr)
    number = digits
    variable = alpha
    parenthesized_expr = ("(" (? whitespace) expression (? whitespace) ")")
"#;
```

This grammar handles:
- Proper operator precedence (multiplication/division before addition/subtraction)
- Recursive expressions with parentheses
- Variables and numbers
- Optional whitespace handling
- Left-associative operations

## Architecture

Neotoma uses a **Template Method Pattern** for its core `Parser` trait:

- **`read()`**: Implement your parsing logic here
- **`parse()`**: Public API that automatically handles caching and backtracking
- **`id()`**: Override for parameterized parsers to avoid cache conflicts

### Key Design Principles

- **Composability**: Orthogonal combinators work together seamlessly
- **Performance**: Memoization prevents redundant parsing
- **Type Safety**: Generic composition prevents common mistakes
- **Memory Efficiency**: Smart pointer integration and optimized data structures

## Documentation

- [API Documentation](https://docs.rs/neotoma)

## Examples

The `tests/` directory contains comprehensive examples:

- **Arithmetic Parser**: Mathematical expression parsing
- **Lisp Expressions**: Recursive data structure parsing
- **Grammar Definitions**: Self-parsing grammar systems

## Python Bindings

Python bindings are available in the `neotoma-py/` directory. See the [Python README](./neotoma-py/README.md) for details.

## License

Licensed under either of:

- Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
- MIT License ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

## Contributing

Contributions are welcome! Please feel free to submit a patch.