The normative reference for rgxr’s data formats and behavior: the
Fa wire format, derived-state naming, auth, saved
documents, trace semantics, regex syntax, engine limits, render engines,
environment variables and the error envelope. The machine-readable API
contract is openapi.yaml at
the repo root; producers and consumers derive from these two
documents.
The shapes documented here are frozen now that users exist: saved
documents and API consumers depend on them, so changes are additive and
land together with an update to this page and openapi.yaml,
never as a silent wire change. The TM wire schema was extended to
multi-tape and nondeterministic machines (a tapes field
plus action lists per read-tuple); old single-action payloads are still
accepted on input.
Fa typeCanonical wire format (camelCase, arrays sorted):
{
"alphabet": ["a", "b"],
"states": ["q0", "q1", "q2"],
"initial": "q0",
"accepting": ["q2"],
"transitions": {
"q0": { "a": ["q0", "q1"], "b": ["q0"] },
"q1": { "b": ["q2"] },
"q2": { "a": ["q2"], "b": ["q2"] }
}
}Rules:
(state, symbol)
transition = no transition. A DFA is an Fa
whose transitions define exactly one target for every state × every
alphabet symbol. Fa::determinism_violation() reports the
first violation.state → symbol → set of states. States have
names; lookup by name is O(1), and structure edits never re-index the
world.BTreeMap/ BTreeSet everywhere. Serialization
is deterministic → stable graphviz output, stable golden tests, no flaky
CI.run
consumes the input string one char at a time. A multi-char
alphabet symbol is structurally legal but unreachable by
run (matches nothing)."" as the transition symbol
("q0": { "": ["q1"] }). "" is never a member
of alphabet: Fa::validate() accepts it as a
transition key and rejects it inside alphabet. Any
ε-transition makes the Fa nondeterministic, so DFAs produced by
constructions never contain "". The regex→NFA Thompson
construction emits "" for its ε-transitions, and rendering
displays "" as ε.initial, accepting, or as a transition
source/target must be in states. Isolated states (no
transitions) are legal; that’s why states exists.
Fa::validate() enforces all of this.deny_unknown_fields): the frontend must send exactly the
documented fields. This is deliberate: wire drift fails loudly instead
of silently dropping data.accepting =
accepts nothing. An epsilon-only NFA may have an empty
alphabet. states and accepting
always serialize, even when empty.Constructions (subset construction, product, minimization, state elimination) generate new state names deterministically:
",").#k with the smallest k ≥ 2 that is free.No randomness, no format!("q{}", counter) across
runs.
Candidates per construction:
| Construction | Candidate name |
|---|---|
to_dfa |
member states sorted, joined with ,; the empty subset
is ∅ |
union / intersection /
difference |
(s1,…,sn), one component per operand |
| sink added to complete an operand | ∅ |
concatenation |
original state name, first operand first |
minimize |
smallest member of the equivalence class |
regex_to_nfa |
q0…qn by BFS rank from the initial state |
regex_to_nfa states carry no semantic content beyond
their position, so BFS rank over the deterministic Thompson graph is the
name: it depends only on the regex.
rgxr never stores passwords. Signing in is optional and goes through any OpenID Connect provider:
OIDC_CLIENT_ID,
default rgxr, redirect URI
<origin>/auth/callback). The top-right user menu
offers SIGN IN and SIGN UP; sign-up sends prompt=create,
which opens the provider’s registration page. A sign-in started in one
tab can finish in another, as when the link in a verification email
opens a new tab; if its pending state is gone, the callback restarts the
sign-in once. Tokens live in the browser’s localStorage and are
refreshed before they expire. SIGN OUT ends the provider session
too.Authorization: Bearer, verifies its signature against the
issuer’s JWKS (fetched on first use, refetched when a token names an
unknown key) and checks iss, aud
(RGXR_OIDC_AUDIENCE) and exp. Data is scoped
to the token’s sub, which survives username changes. The
provider must put the client id in the access token’s aud
(Keycloak: an audience mapper)./me reports the anonymous user when
RGXR_ANONYMOUS_FALLBACK=true (or in dev mode), and is 401
otherwise. Saved documents always need a token: the anonymous user owns
nothing on the server, and the web app keeps a signed-out visitor’s
documents in that browser’s localStorage (rgxr.docs),
shared with nobody. An invalid token is always 401, and an unreachable
provider is 503, so an outage never signs anyone out. Without
OIDC_ISSUER the UI offers no sign-in at all.RGXR_DEV_MODE=true → additionally allows the Vite dev
server origin (http://localhost:5173) as a CORS
origin.POST/PUT /automata bodies are
{ name, data } where
{ "fa": { ...Fa... }, "layout": { "q0": { "x": 250, "y": 80 } } }layout is frontend-owned (xyflow
positions). The backend treats it as opaque JSONB passthrough and must
never parse or validate it.
Grammars, PDAs and TMs are saved as their editor source:
{ "kind": "cfg", "text": "S -> a S b | ε" }kind ∈ fa | cfg | pda | tm, default
fa (rows written before kinds existed). fa
documents carry fa and no text; the others
carry text (≤ 64 KiB) and no fa. List
summaries include kind.
run returns a trace of snapshots: the
epsilon-closed set of active states after consuming
each symbol, serialized sorted. Step 0 has symbol: null
(the initial closure) and symbol is always present in the
JSON, null included.
accepted = last step's states ∩ accepting ≠ ∅. For DFAs
each snapshot is a singleton: same shape, simpler view.
| union · juxtaposition concat · * star ·
+ plus · ? option · ( ) grouping
· \x escape for literal metacharacters · empty expression
or ε = the empty string (\ε is a literal ε).
Unicode literals allowed. Parse errors → invalid_regex with
a human-readable message naming the 1-based position.
* + ? > concatenation >
|.a** ≡ a*,
a*+? is valid.a|, |,
().\x makes any x literal; metacharacters are
| * + ? ( ) \.regex_to_nfa output is the set of
literals used.fa_to_regex output always re-parses with this syntax.
The empty language has no expression in it and returns
invalid_fa. Conversion is size-bounded: an automaton whose
equivalent regex would be too large to build returns
invalid_fa instead of exhausting memory.
Every engine request finishes in bounded time and memory. Exceeding a
limit is a 400 with a message naming the limit
(invalid_regex for regex limits, invalid_fa
otherwise), except the body limit.
| Limit | Value | Applies to |
|---|---|---|
| Request body | 2 MiB | every endpoint; over it → 413 with code
invalid_request |
| States per input automaton | 10 000 | every engine operation and render |
| Alphabet symbols per input automaton | 256 | every engine operation and render |
| State name or symbol length | 256 bytes | every engine operation and render |
| Transition targets per input automaton | 200 000 | every engine operation and render |
| Transitions derived by ε-removal or completion | 1 000 000 | union, intersection, difference, fa_to_regex |
| States built by a construction | 10 000 | to_dfa, union, intersection, difference |
| Transitions built by a product | 200 000 | union, intersection, difference |
| Automata per n-ary operation | 16 | union, intersection, concatenation |
run input |
10 000 symbols | run |
run trace size |
1 000 000 active-state entries and 16 MiB of state names in total | run |
| Regex length | 10 000 characters | regex_to_nfa |
| Group nesting | 200 levels | regex_to_nfa |
| States eliminated | 1 000 | fa_to_regex |
| Saved automata listed | 500 newest | GET /automata |
| Expression size | 4 096 nodes per edge, 2 000 000 nodes built in total | fa_to_regex |
| Grammar size | 200 nonterminals, 2 000 right-hand-side symbols | every grammar endpoint |
| Parsed word | 32 symbols; 10 000 000 chart/table steps (over → 400
asking for a shorter word or simpler grammar) |
grammar/parse, grammar/cyk |
| CNF rules built | 20 000 | grammar/cnf, grammar/cyk |
| PDA size / input | 500 states, 5 000 transitions / 200 symbols | pda/* |
| PDA → CFG size | normalised transitions × states² ≤ 200 000 | pda/to-grammar |
| PDA search | 50 000 configurations, stack depth 400 (limit hit →
truncated) |
pda/run |
| TM size / input / steps | 500 states / 500 symbols / 100 000 steps; 1–4 tapes; nondeterministic search up to 50 000 configurations (trace keeps 2 000) | tm/run |
| Grading sweep | 4 000 words up to length 12; 200 000 work units shared across words
(a PDA or nondeterministic-TM configuration = 1, a deterministic TM step
= 1/16, a parse step = 1/128; over → budgetExhausted) |
grade |
| Table-filling | 100 reachable states | ops/minimize/table |
Stacked postfix operators fold while parsing (a*** ≡
a*), so they count toward the length limit only.
fast: FA → DOT (rgxr-render::to_dot) →
dot -Tsvg. Must be available in every deployment.latex: DOT → dot2tex →
pdflatex → dvisvgm → SVG. Optional; disabled
via RGXR_LATEX_ENABLED=false (default false until the image
ships texlive) → 503 render_unavailable.Every render subprocess runs under a hard timeout (5 s for the
fast engine’s dot; the latex stages allow
longer).
Latex render responses additionally carry tikz: the TikZ
source the image was produced from, for pasting into LaTeX documents
(which cannot embed SVG natively). It includes the stroke-width override
the rendered image used and a comment naming the required preamble
packages. fast responses have no tikz
field.
| Var | Default | Meaning |
|---|---|---|
DATABASE_URL |
none | Postgres URL (sqlx) |
RGXR_PORT |
8080 |
Listen port |
RGXR_DEV_MODE |
false |
Dev conveniences: Vite-origin CORS; requests without a token run as
anonymous |
RGXR_ANONYMOUS_FALLBACK |
false |
Requests without a token run as anonymous instead of
401 |
RGXR_OIDC_ISSUER |
none | OIDC issuer whose access tokens the API accepts; unset → every token is 401 |
RGXR_OIDC_AUDIENCE |
rgxr |
Required aud entry of accepted access tokens |
RGXR_LATEX_ENABLED |
false |
Enable the latex render engine |
RUST_LOG |
info |
tracing filter |
rgxr-web adds:
| Var | Default | Meaning |
|---|---|---|
OIDC_ISSUER |
none | OIDC issuer for the optional sign-in; unset → no sign-in UI, everyone stays anonymous |
OIDC_CLIENT_ID |
rgxr |
Public client id registered at the issuer |
API_UPSTREAM |
none | Forward api paths to this base URL (compose); unset → the ingress routes them |
Locally the variables come from the shell or a .env
file. In our production deployment (see Operations) they are injected via OpenBao →
ESO → K8s Secret; other deployments pass them however their platform
injects environment variables.
{ "error": { "code": "invalid_fa", "message": "initial state `q9` is not in `states`" } }Codes: invalid_request, invalid_fa,
invalid_regex, not_found,
unauthorized, conflict,
render_unavailable, internal. Input validation
is always 400; missing resources 404.