fstmd 1.0.0
Finite-State Markdown Engine - O(N) single-pass Markdown to HTML converter using pure FST
License: MIT
Requires Python: >=3.13
Keywords: markdown, html, parser, finite-state-transducer, fst, mealy-machine, performance, zero-dependencies

# FSTMD - Finite-State Markdown Engine

[![Python 3.13+](https://img.shields.io/badge/python-3.13+-blue.svg)](https://www.python.org/downloads/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![Type Checked](https://img.shields.io/badge/type--checked-mypy-blue.svg)](http://mypy-lang.org/)

A **pure Finite State Transducer (FST)** Markdown to HTML converter for Python 3.13+.

## Features

- ⚡ **O(N) Single-Pass Processing** - No backtracking, no regex, no AST
- 🔒 **Security First** - XSS prevention with proper HTML escaping
- 🎯 **Zero Dependencies** - Pure Python, no external packages required
- 📐 **Type Safe** - Full type annotations, mypy strict compatible
- 🚀 **Python 3.13+ Optimized** - Uses latest Python features

## Installation

```bash
pip install fstmd
```

Or install from source:

```bash
git clone https://github.com/fstmd/fstmd.git
cd fstmd
pip install -e .
```

## Quick Start

```python
from fstmd import Markdown

# Create a parser (safe mode by default)
md = Markdown(mode="safe")

# Render Markdown to HTML
html = md.render("**Hello** *world*")
print(html)
# Output: <p><strong>Hello</strong> <em>world</em></p>
```

## Supported Markdown Features

| Feature | Syntax | Output |
|---------|--------|--------|
| Bold | `**text**` | `<strong>text</strong>` |
| Italic | `*text*` | `<em>text</em>` |
| Bold+Italic | `***text***` | `<strong><em>text</em></strong>` |
| Headings | `# H1` to `###### H6` | `<h1>` to `<h6>` |
| Unordered Lists | `- item` | `<ul><li>item</li></ul>` |
| Paragraphs | Blank line separated | `<p>...</p>` |

## API Reference

### Markdown Class

```python
from fstmd import Markdown

# Safe mode (default) - escapes all HTML
md = Markdown(mode="safe")

# Raw mode - passes through HTML (use with trusted input only!)
md = Markdown(mode="raw")

# Strict mode - raises exceptions on security issues
md = Markdown(mode="safe", strict=True)

# Render markdown
html = md.render("# Hello **World**")

# Always render safely, regardless of instance mode
safe_html = md.render_safe("<script>alert(1)</script>")
```

### Convenience Functions

```python
from fstmd.parser import render, render_unsafe

# Quick render with caching
html = render("**bold**")

# Render without escaping (dangerous!)
html = render_unsafe("<b>raw html</b>")
```

## Security

FSTMD is designed with security as a primary concern:

### Safe Mode (Default)

All HTML special characters are escaped:
- `<` → `&lt;`
- `>` → `&gt;`
- `&` → `&amp;`
- `"` → `&quot;`
- `'` → `&#x27;`

```python
md = Markdown(mode="safe")
result = md.render("<script>alert('xss')</script>")
# Output: <p>&lt;script&gt;alert(&#x27;xss&#x27;)&lt;/script&gt;</p>
```

### Dangerous Pattern Detection

The library detects and can reject:
- `<script>` tags
- `javascript:` URLs
- `vbscript:` URLs
- `data:` URLs (except safe image types)

## Architecture

### Finite State Transducer Design

FSTMD uses a **Mealy Machine** (FST) where output is generated during state transitions.

```
┌─────────────────────────────────────────────────────────────────┐
│                        INLINE FST STATES                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│   ┌───────┐    '*'     ┌──────────┐    '*'    ┌──────────┐     │
│   │ TEXT  │───────────►│ STAR_ONE │──────────►│ STAR_TWO │     │
│   └───┬───┘            └────┬─────┘           └────┬─────┘     │
│       │                     │                      │            │
│       │ other               │ other                │ other      │
│       ▼                     ▼                      ▼            │
│   output char           start italic           start bold      │
│                                                                 │
│   ┌───────────┐        ┌────────────┐                          │
│   │ IN_ITALIC │◄───────│ STAR_ONE   │ (from TEXT with '*')     │
│   └─────┬─────┘        └────────────┘                          │
│         │ '*'                                                   │
│         ▼                                                       │
│   ┌──────────────┐                                             │
│   │ close italic │────► output </em>, goto TEXT                │
│   └──────────────┘                                             │
│                                                                 │
│   ┌──────────┐         ┌───────────────┐                       │
│   │ IN_BOLD  │◄────────│ STAR_TWO      │ (from STAR_ONE)       │
│   └────┬─────┘         └───────────────┘                       │
│        │ '**'                                                   │
│        ▼                                                        │
│   ┌─────────────┐                                              │
│   │ close bold  │────────► output </strong>                    │
│   └─────────────┘                                              │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘
```

### Block-Level FST

```
┌─────────────────────────────────────────────────────────────────┐
│                        BLOCK FST STATES                         │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│   ┌──────────┐                                                  │
│   │  START   │ ─────────────────────────────────────────────┐   │
│   └────┬─────┘                                               │   │
│        │                                                      │   │
│    ┌───┴───┐   '#'     ┌──────────┐                          │   │
│    │ LINE  │──────────►│ HEADING  │──► count #'s, emit <hN>  │   │
│    │ START │           └──────────┘                          │   │
│    └───┬───┘                                                  │   │
│        │                                                      │   │
│        │   '-'    ┌───────────────┐                          │   │
│        ├─────────►│ LIST_ITEM     │──► emit <li>             │   │
│        │          └───────────────┘                          │   │
│        │                                                      │   │
│        │   '\n'   ┌───────────────┐                          │   │
│        ├─────────►│ BLANK_LINE    │──► close paragraph       │   │
│        │          └───────────────┘                          │   │
│        │                                                      │   │
│        │  other   ┌───────────────┐                          │   │
│        └─────────►│ PARAGRAPH     │──► emit <p>              │   │
│                   └───────────────┘                          │   │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘
```

### Key Design Decisions

1. **Two-Character Lookahead Maximum** - Disambiguates `*` vs `**` vs `***`
2. **No Backtracking** - All decisions are final
3. **Output During Transitions** - Mealy machine produces output as it processes
4. **Immutable State Definitions** - States are enums, transitions are cached

## Performance

### Complexity Guarantees

| Operation | Time Complexity | Space Complexity |
|-----------|-----------------|------------------|
| Parse     | O(N)            | O(N)             |
| Per character | O(1)        | O(1)             |

### Benchmarks

Tested on Python 3.13 with a medium-sized document (~500 chars):

| Library | Avg Time (ms) | Throughput | Relative |
|---------|---------------|------------|----------|
| FSTMD | 0.05 | 10M chars/sec | 1.0x |
| markdown-it-py | 0.15 | 3.3M chars/sec | 0.33x |
| Python-Markdown | 0.30 | 1.7M chars/sec | 0.17x |
| CommonMark-Py | 0.35 | 1.4M chars/sec | 0.14x |

*Note: Benchmarks vary by hardware and document structure.*

Run benchmarks yourself:

```python
from fstmd.benchmarks import run_benchmarks, print_benchmark_results

results = run_benchmarks()
print_benchmark_results(results)
```

## Limitations

FSTMD focuses on speed and simplicity. It does **not** support:

- Code blocks (fenced or indented)
- Block quotes
- Ordered lists
- Links and images
- Tables
- Footnotes
- HTML pass-through in safe mode

For full CommonMark compliance, use [markdown-it-py](https://github.com/executablebooks/markdown-it-py).

## Development

### Setup

```bash
# Clone the repository
git clone https://github.com/fstmd/fstmd.git
cd fstmd

# Install with dev dependencies
pip install -e ".[dev]"

# Run tests
pytest

# Type checking
mypy fstmd

# Linting
ruff check fstmd
```

### Project Structure

```
fstmd/
├── __init__.py          # Package exports
├── __main__.py          # CLI entry point
├── parser.py            # High-level Markdown class
├── exceptions.py        # Custom exceptions
├── core/
│   ├── __init__.py
│   ├── fsm.py          # Main FST engine
│   ├── states.py       # State definitions
│   ├── transitions.py  # Transition table
│   └── safe_html.py    # HTML escaping
├── benchmarks/
│   ├── __init__.py
│   └── runner.py       # Benchmark utilities
└── tests/
    ├── conftest.py
    ├── test_inline.py
    ├── test_blocks.py
    ├── test_security.py
    ├── test_fsm.py
    └── test_integration.py
```

## Building and Publishing

### Build

```bash
# Install build tools
pip install build twine

# Build distribution
python -m build

# Check the build
twine check dist/*
```

### Publish to PyPI

```bash
# Upload to TestPyPI first
twine upload --repository testpypi dist/*

# Upload to PyPI
twine upload dist/*
```

## Contributing

Contributions are welcome! Please:

1. Fork the repository
2. Create a feature branch
3. Add tests for new functionality
4. Ensure all tests pass (`pytest`)
5. Ensure type checking passes (`mypy fstmd`)
6. Ensure linting passes (`ruff check fstmd`)
7. Submit a pull request

## License

MIT License - see [LICENSE](LICENSE) file.

## Acknowledgments

Inspired by:
- [markdown-it](https://github.com/markdown-it/markdown-it) - Architecture insights
- [peg-markdown](https://github.com/jgm/peg-markdown) - PEG-based parsing ideas
- Automata theory and FST research

---

Made with ❤️ for fast, secure Markdown parsing.