Skip to content
← Journal
11 min readAta Mohammadi

The Senior Frontend Engineering Blueprint, Part 7: Building a Linear-Time Query Language Parser

Every product with a power-user search box eventually needs a real query language, and reaching for new RegExp(userInput) is how you end up hand-rolling a vulnerability. Here is a filter-query DSL built from a sticky-regex tokenizer, a recursive-descent parser, and a recursive Zod schema — with a ReDoS stress test to prove the O(N) claim.

Every product with a power-user search box eventually grows a filter language. GitHub has one, Jira has one, Datadog has one — status:active AND (views >= 1000 OR tag in [react, typescript]) AND author:"Alex M." is the shape they all converge on, because it's the smallest grammar that covers field comparisons, set membership, quoted literals and boolean composition. The moment your product needs this, there are two ways to build it: reach for new RegExp(userInput) or a hand-rolled recursive merge and hope, or actually build a parser. Part 6 of this series covered why the first option is how you end up shipping a ReDoS vulnerability by accident — nested quantifiers, catastrophic backtracking, an attacker paying a few bytes to cost your event loop seconds. This article is the sequel that piece was building toward: what actually building something ReDoS-safe, end to end, looks like. It won't re-explain backtracking; it assumes you've read that part or already know why /^(a+)+$/ is a problem.

What we're building

The target is a small pipeline that turns an untrusted query string into a validated, typed Abstract Syntax Tree:

Input:
status:active AND (views >= 1000 OR tag in [react, typescript]) AND author:"Alex M."

Output (validated AST):
{
  "type": "logical",
  "operator": "AND",
  "left": { "type": "comparison", "field": "status", "operator": "eq", "value": "active" },
  "right": {
    "type": "logical",
    "operator": "AND",
    "left": {
      "type": "logical",
      "operator": "OR",
      "left": { "type": "comparison", "field": "views", "operator": "gte", "value": 1000 },
      "right": { "type": "in_list", "field": "tag", "operator": "in", "values": ["react", "typescript"] }
    },
    "right": { "type": "comparison", "field": "author", "operator": "eq", "value": "Alex M." }
  }
}

Three requirements shape every decision below:

  • Linear time, provably. The tokenizer must process the input in one pass, with no construct that can trigger backtracking, so a pathological input costs the same as a normal one of the same length.
  • A small, unambiguous grammar. Comparison operators (:, =, !=, >, <, >=, <=), an in [...] set-membership form, and AND/OR composition with parentheses for grouping — nothing more.
  • Validated output, not just parsed output. The parser's raw tree gets checked against a schema before anything downstream trusts it.

Step 1: a tokenizer that cannot backtrack

The trick is the sticky flag, /y. A sticky regex matches only at lastIndex — if the pattern doesn't match exactly where the cursor sits, it fails immediately, in O(1), rather than scanning forward. This is not a style preference. It's what makes the O(N) claim actually true. The global flag, /g, will happily continue searching past a non-match at the current position; used inside a hand-rolled scan loop, that reintroduces exactly the kind of unbounded rescan cost you built a linear tokenizer to avoid. Sticky regex fails fast and moves on; global regex goes looking.

export type TokenType =
  | "LPAREN"
  | "RPAREN"
  | "LBRACKET"
  | "RBRACKET"
  | "COMMA"
  | "LOGICAL_AND"
  | "LOGICAL_OR"
  | "OP_IN"
  | "OP_COMPARE"
  | "IDENTIFIER"
  | "NUMBER"
  | "STRING";

export interface Token {
  type: TokenType;
  value: string;
  position: number;
}

// Every rule is anchored to `lastIndex` — none of these can scan forward on a miss.
const RULES: Array<{ type: TokenType; regex: RegExp }> = [
  { type: "LPAREN", regex: /\(/y },
  { type: "RPAREN", regex: /\)/y },
  { type: "LBRACKET", regex: /\[/y },
  { type: "RBRACKET", regex: /\]/y },
  { type: "COMMA", regex: /,/y },
  { type: "LOGICAL_AND", regex: /AND\b/y },
  { type: "LOGICAL_OR", regex: /OR\b/y },
  { type: "OP_IN", regex: /in\b/y },
  { type: "OP_COMPARE", regex: /(:|<=|>=|!=|<|>|=)/y },
  { type: "NUMBER", regex: /-?\d+(\.\d+)?\b/y },
  // No nested quantifier: an escaped char or a non-quote-non-backslash char, repeated once.
  { type: "STRING", regex: /"([^"\\]|\\.)*"/y },
  { type: "IDENTIFIER", regex: /[a-zA-Z_][a-zA-Z0-9_.-]*/y },
];

const WHITESPACE_REGEX = /\s+/y;

export function tokenize(input: string): Token[] {
  const tokens: Token[] = [];
  let cursor = 0;
  const length = input.length;

  while (cursor < length) {
    WHITESPACE_REGEX.lastIndex = cursor;
    const wsMatch = WHITESPACE_REGEX.exec(input);
    if (wsMatch) {
      cursor = WHITESPACE_REGEX.lastIndex;
      if (cursor >= length) break;
    }

    let matched = false;

    for (const rule of RULES) {
      rule.regex.lastIndex = cursor;
      const match = rule.regex.exec(input);

      if (match) {
        let rawValue = match[0];
        if (rule.type === "STRING") {
          rawValue = rawValue.slice(1, -1).replace(/\\"/g, '"');
        }

        tokens.push({ type: rule.type, value: rawValue, position: cursor });
        cursor = rule.regex.lastIndex;
        matched = true;
        break;
      }
    }

    if (!matched) {
      throw new Error(`Syntax Error: unrecognised token '${input[cursor]}' at position ${cursor}`);
    }
  }

  return tokens;
}

Notice the STRING rule: /"([^"\\]|\\.)*"/y. It's a repeated alternation, which is exactly the shape that causes catastrophic backtracking when the two alternatives can both match the same character — but here they can't. [^"\\] excludes backslash, \\. requires one. Every character in the input belongs to exactly one branch, never both, so there's nothing for the engine to backtrack between. That mutual exclusivity, not the sticky flag alone, is the other half of what keeps this linear.

Step 2: a recursive-descent parser that encodes precedence for free

Operator precedence in a hand-rolled parser doesn't need a table or a post-processing pass. It falls straight out of which function calls which: parseOrExpression calls parseAndExpression calls parseComparisonOrGroup, so OR binds loosest, AND binds tighter, and comparisons/parenthesised groups sit at the bottom. Nothing outside that call graph has to know the precedence rules exist.

import { Token, TokenType } from "./tokenizer";

export type RawASTNode =
  | { type: "comparison"; field: string; operator: string; value: string | number }
  | { type: "in_list"; field: string; operator: "in"; values: Array<string | number> }
  | { type: "logical"; operator: "AND" | "OR"; left: RawASTNode; right: RawASTNode };

export class QueryParser {
  private tokens: Token[];
  private current = 0;

  constructor(tokens: Token[]) {
    this.tokens = tokens;
  }

  public parse(): RawASTNode {
    if (this.tokens.length === 0) {
      throw new Error("Cannot parse an empty query");
    }
    const ast = this.parseOrExpression();
    if (!this.isAtEnd()) {
      const remaining = this.peek();
      throw new Error(`Unexpected token '${remaining.value}' at position ${remaining.position}`);
    }
    return ast;
  }

  // Lowest precedence
  private parseOrExpression(): RawASTNode {
    let expr = this.parseAndExpression();
    while (this.match("LOGICAL_OR")) {
      const right = this.parseAndExpression();
      expr = { type: "logical", operator: "OR", left: expr, right };
    }
    return expr;
  }

  private parseAndExpression(): RawASTNode {
    let expr = this.parseComparisonOrGroup();
    while (this.match("LOGICAL_AND")) {
      const right = this.parseComparisonOrGroup();
      expr = { type: "logical", operator: "AND", left: expr, right };
    }
    return expr;
  }

  // Comparisons, `in [...]` lists, and parenthesised grouping
  private parseComparisonOrGroup(): RawASTNode {
    if (this.match("LPAREN")) {
      const expr = this.parseOrExpression();
      this.consume("RPAREN", "Expected ')' after grouping expression");
      return expr;
    }

    const fieldToken = this.consume("IDENTIFIER", "Expected field name in comparison");
    const field = fieldToken.value;

    if (this.match("OP_IN")) {
      this.consume("LBRACKET", "Expected '[' following 'in' operator");
      const values: Array<string | number> = [];

      if (!this.check("RBRACKET")) {
        do {
          const valToken = this.consumeValueToken();
          values.push(valToken.type === "NUMBER" ? Number(valToken.value) : valToken.value);
        } while (this.match("COMMA"));
      }

      this.consume("RBRACKET", "Expected ']' at end of value list");
      return { type: "in_list", field, operator: "in", values };
    }

    const opToken = this.consume("OP_COMPARE", `Expected comparison operator after field '${field}'`);
    const valToken = this.consumeValueToken();

    return {
      type: "comparison",
      field,
      operator: opToken.value,
      value: valToken.type === "NUMBER" ? Number(valToken.value) : valToken.value,
    };
  }

  private consumeValueToken(): Token {
    if (this.check("STRING") || this.check("NUMBER") || this.check("IDENTIFIER")) {
      return this.advance();
    }
    const next = this.peek();
    throw new Error(`Expected value literal at position ${next?.position ?? "EOF"}`);
  }

  private match(...types: TokenType[]): boolean {
    for (const type of types) {
      if (this.check(type)) {
        this.advance();
        return true;
      }
    }
    return false;
  }

  private check(type: TokenType): boolean {
    if (this.isAtEnd()) return false;
    return this.peek().type === type;
  }

  private advance(): Token {
    if (!this.isAtEnd()) this.current++;
    return this.previous();
  }

  private isAtEnd(): boolean {
    return this.current >= this.tokens.length;
  }

  private peek(): Token {
    return this.tokens[this.current]!;
  }

  private previous(): Token {
    return this.tokens[this.current - 1]!;
  }

  private consume(type: TokenType, message: string): Token {
    if (this.check(type)) return this.advance();
    const token = this.peek();
    throw new Error(`${message} at position ${token?.position ?? "EOF"}`);
  }
}

Step 3: validating the tree, not just producing one

A parser that only checks syntax will happily hand you a structurally valid tree with a field name your schema doesn't recognise, or an operator your business logic never expects. The parser's job ends at "this is a well-formed query." Whether it's a query you actually allow is a separate, explicit check — a recursive Zod schema over the AST shape, with z.lazy breaking the type/schema circularity a self-referential node needs:

import { z } from "zod";

export const OperatorSchema = z.enum([":", "=", "==", "!=", ">", "<", ">=", "<="]).transform((op) => {
  switch (op) {
    case ":":
    case "=":
    case "==":
      return "eq" as const;
    case "!=":
      return "neq" as const;
    case ">":
      return "gt" as const;
    case "<":
      return "lt" as const;
    case ">=":
      return "gte" as const;
    case "<=":
      return "lte" as const;
  }
});

export const ComparisonFilterNodeSchema = z.object({
  type: z.literal("comparison"),
  field: z.string().min(1).regex(/^[a-zA-Z_][a-zA-Z0-9_.]*$/, "Invalid field name"),
  operator: OperatorSchema,
  value: z.union([z.string(), z.number()]),
});

export type ComparisonFilterNode = z.infer<typeof ComparisonFilterNodeSchema>;

export const InListFilterNodeSchema = z.object({
  type: z.literal("in_list"),
  field: z.string().min(1),
  operator: z.literal("in"),
  values: z.array(z.union([z.string(), z.number()])).min(1, "List cannot be empty"),
});

export type InListFilterNode = z.infer<typeof InListFilterNodeSchema>;

export type FilterASTNode =
  | ComparisonFilterNode
  | InListFilterNode
  | { type: "logical"; operator: "AND" | "OR"; left: FilterASTNode; right: FilterASTNode };

// z.lazy defers evaluation until the schema is actually used, which is what lets
// FilterASTSchema reference itself inside its own definition.
export const FilterASTSchema: z.ZodType<FilterASTNode> = z.lazy(() =>
  z.discriminatedUnion("type", [
    ComparisonFilterNodeSchema,
    InListFilterNodeSchema,
    z.object({
      type: z.literal("logical"),
      operator: z.enum(["AND", "OR"]),
      left: FilterASTSchema,
      right: FilterASTSchema,
    }),
  ]),
);

Step 4: one function, three stages, structured failure

import { tokenize } from "./tokenizer";
import { QueryParser } from "./parser";
import { FilterASTSchema, FilterASTNode } from "./schema";

export type ParseResult =
  | { success: true; ast: FilterASTNode }
  | { success: false; stage: "LEXER" | "PARSER" | "VALIDATION"; error: string };

export function parseFilterQuery(query: string): ParseResult {
  try {
    const tokens = tokenize(query);
    const parser = new QueryParser(tokens);
    const rawAst = parser.parse();

    const validationResult = FilterASTSchema.safeParse(rawAst);
    if (!validationResult.success) {
      return { success: false, stage: "VALIDATION", error: validationResult.error.message };
    }

    return { success: true, ast: validationResult.data };
  } catch (err) {
    const message = err instanceof Error ? err.message : "Unknown error";
    const stage = message.startsWith("Syntax Error") ? "LEXER" : "PARSER";
    return { success: false, stage, error: message };
  }
}

Three stages, three failure shapes. A caller building a search UI can tell "you have a typo" (LEXER), "your parentheses don't balance" (PARSER), and "that's a query I understand but won't allow" (VALIDATION) apart, and show a different message for each.

Step 5: proving the O(N) claim, not asserting it

A verification suite for a parser is normal. A verification suite for a ReDoS-safe parser has to include an actual attack payload and a timing assertion, or the safety claim is just marketing:

import { parseFilterQuery } from "../src/dsl";

function runTests() {
  console.log("--- DSL parser verification ---");

  const complexQuery = 'status:active AND (views >= 1000 OR tag in [react, "web dev"]) AND author:"Sarah B."';
  const res1 = parseFilterQuery(complexQuery);
  console.assert(res1.success === true, "Test 1 failed: expected valid parse");
  if (res1.success) {
    console.assert(res1.ast.type === "logical", "Test 1 failed: root must be logical");
    console.log("Complex query parsed and validated.");
  }

  const malformedQuery = "status:active AND (views > 100";
  const res2 = parseFilterQuery(malformedQuery);
  console.assert(res2.success === false, "Test 2 failed: should detect unclosed paren");
  if (!res2.success) {
    console.assert(res2.stage === "PARSER", "Test 2 failed: stage must be PARSER");
  }
  console.log("Unclosed grouping correctly rejected.");

  const invalidOpQuery = "status ?? active";
  const res3 = parseFilterQuery(invalidOpQuery);
  console.assert(res3.success === false, "Test 3 failed: should detect invalid operator");
  if (!res3.success) {
    console.assert(res3.stage === "LEXER", "Test 3 failed: stage must be LEXER");
  }
  console.log("Invalid characters correctly rejected at the lexer.");

  // A non-linear engine testing tens of thousands of unclosed spaces/quotes would hang.
  const attackPayload =
    "field:value AND (" + " ".repeat(50000) + 'tag in ["unterminated string' + "a".repeat(50000);

  const startTime = performance.now();
  const res4 = parseFilterQuery(attackPayload);
  const duration = performance.now() - startTime;

  console.assert(res4.success === false, "Test 4 failed: attack payload must fail");
  console.assert(duration < 100, `Test 4 failed: took ${duration.toFixed(2)}ms — that's a ReDoS`);
  console.log(`ReDoS payload rejected in ${duration.toFixed(2)}ms.`);
}

runTests();

100,000 characters of adversarial input, parsed and rejected in low single-digit milliseconds on ordinary hardware — because nothing in this pipeline ever revisits a character it's already consumed.

What this is actually testing for

If this shows up as a live-coding exercise, here's what the interviewer is checking, underneath the working code:

Design choice What it demonstrates
Sticky (/y) over global (/g) regex in the tokenizer Understanding that /g's forward-scanning behaviour on a miss reintroduces the exact cost class a linear tokenizer exists to remove
Precedence via the call graph (parseOrExpression → parseAndExpression → parseComparisonOrGroup), not a table Recursive descent doesn't need precedence climbing or a post-pass — the grammar hierarchy is the precedence
z.discriminatedUnion("type", [...]) plus z.lazy() Discriminated unions let TypeScript narrow on node.type inside a switch for free; z.lazy is the only way to let a schema reference itself before it finishes being defined
A separate VALIDATION stage after a successful parse Syntactic validity and semantic validity are different questions — a parser answering "yes" to both conflates them and usually gets the second one wrong silently

The compressed version

  • Sticky regex, not global, is what makes an O(N) tokenizer claim true — /g will scan past a non-match, /y fails at the cursor in O(1).
  • Precedence lives in which parser method calls which, not in a separate table: OR → AND → comparisons/groups, bottom to top.
  • A recursive discriminated union needs z.lazy() to break the self-reference — the schema can't be fully defined before it's used inside itself.
  • Parsing and validating are different steps with different failure modes; keep LEXER/PARSER/VALIDATION distinguishable so callers can say something useful to the user.
  • Don't take a ReDoS-safety claim on faith — the only convincing proof is an actual adversarial payload and a timing assertion in the test suite.

Keep reading

Next step

Tell us what is broken or what should exist.

Send the shape of the problem and any constraints you already know — budget, deadline, the stack you are stuck with. You will get a written reply from the engineer who would do the work, not a sales sequence.

Start a project→[email protected]