fstmd 1.0.0

Finite-State Markdown Engine - O(N) single-pass Markdown to HTML converter using pure FST

FSTMD - Finite-State Markdown Engine

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

pip install fstmd

Or install from source:

git clone https://github.com/fstmd/fstmd.git
cd fstmd
pip install -e .

Quick Start

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

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

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:

• < → <
• > → >
• & → &
• " → "
• ' → '

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:

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.

Development

Setup

# 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

# Install build tools
pip install build twine

# Build distribution
python -m build

# Check the build
twine check dist/*

Publish to PyPI

# 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 file.

Acknowledgments

Inspired by:

• markdown-it - Architecture insights
• peg-markdown - PEG-based parsing ideas
• Automata theory and FST research

---

Made with ❤️ for fast, secure Markdown parsing.