Skip to content

fsm: build toRange on ascii.range instead of re-implementing it #1575

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
sergey-shandar merged 2 commits into from
Aug 15, 2026
Merged

fsm: build toRange on ascii.range instead of re-implementing it #1575

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
e4f744f
fsm: build toRange on ascii.range instead of re-implementing it
claude Aug 15, 2026
67d8af7
changelog: entry for the fsm toRange fix
claude Aug 15, 2026
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions changelog/unreleased/1575.md
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
- **BREAKING CHANGES:** `fsm`: `toRange` no longer throws on a one-character
argument — it is the singleton range, via `text/ascii`'s `range`. `toUnion`
is no longer exported; it was used only by the module's own proof
31 changes: 14 additions & 17 deletions fjs/fsm/module.f.mjs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,13 +12,13 @@
*/

import { equal, isEmpty, fold, map, toArray, foldScan, empty as emptyList } from '../types/list/module.f.mjs'
import { toRangeMap, union as byteSetUnion, one, empty, range } from '../types/byte_set/module.f.mjs'
import { toRangeMap, range } from '../types/byte_set/module.f.mjs'
import { intersect, union as sortedSetUnion } from '../types/sorted_set/module.f.mjs'
import { merge, get as rangeMapGet } from '../types/range_map/module.f.mjs'
import { strictEqual } from '../types/function/operator/module.f.mjs'
import { range as asciiRange } from '../text/ascii/module.f.mjs'
import { stringify } from '../media/json/module.f.mjs'
import { identity } from '../types/function/module.f.mjs'
import { stringToList } from '../text/utf16/module.f.mjs'
import { compose, identity } from '../types/function/module.f.mjs'
import { cmp } from '../types/string/module.f.mjs'

/** @typedef {readonly [string, ByteSet, string]} _Rule */
Expand All @@ -29,20 +29,17 @@ import { cmp } from '../types/string/module.f.mjs'

const stringifyIdentity = stringify(identity)

/** @type {(s: string) => ByteSet} */
export const toRange = s => {
const [b, e] = toArray(stringToList(s))
return range([b, e])
}

/** @type {Fold<number, ByteSet>} */
const toUnionOp = i => bs => byteSetUnion(bs)(one(i))

/** @type {(s: string) => ByteSet} */
export const toUnion = s => {
const codePoints = stringToList(s)
return fold(toUnionOp)(empty)(codePoints)
}
/**
* The byte set of an inclusive ASCII character range, written as the two
* endpoint characters: `toRange('az')`.
*
* `fjs/text/ascii` owns "two-character string to inclusive `Range`", including
* the one-character case where both endpoints are that character, so this is
* its composition with `byte_set.range` and nothing more.
*
* @type {(s: string) => ByteSet}
*/
export const toRange = compose(asciiRange)(range)

/** @type {Properties<SortedSet<string>>} */
const mergeOp = { union: sortedSetUnion(cmp), equal: equal(strictEqual), def: [] }
Expand Down
28 changes: 25 additions & 3 deletions fjs/fsm/proof.f.mjs
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,18 +1,30 @@
/**
* @import { Grammar } from './module.f.mjs'
* @import { ByteSet } from '../types/byte_set/types.ts'
*/

import { dfa, run, toRange, toUnion } from './module.f.mjs'
import { union } from '../types/byte_set/module.f.mjs'
import { dfa, run, toRange } from './module.f.mjs'
import { one, union, empty, range as byteSetRange } from '../types/byte_set/module.f.mjs'
import { sort, fromEntries } from '../types/object/module.f.mjs'
import { stringify } from '../media/json/module.f.mjs'
import { identity } from '../types/function/module.f.mjs'
import { toArray } from '../types/list/module.f.mjs'
import { fold, toArray } from '../types/list/module.f.mjs'
import { stringToList } from '../text/utf16/module.f.mjs'
import { assertEq } from '../asserts/module.f.mjs'

const stringifyIdentity = stringify(identity)

/**
* The byte set of a string's characters, used to spell a grammar's punctuation
* alphabets below. It lives here rather than in `fjs/fsm` or `types/byte_set`:
* `fjs/fsm` has no use for it, and a `types` leaf taking a *string* would have
* to depend on `fjs/text` to read one.
*
* @type {(s: string) => ByteSet}
*/
const toUnion = s =>
fold((/** @type {number} */i) => (/** @type {ByteSet} */bs) => union(bs)(one(i)))(empty)(stringToList(s))

const buildDfa = () => {
const lowercaseAlpha = toRange('az')
const uppercaseAlpha = toRange('AZ')
Expand All @@ -39,6 +51,16 @@ const buildDfa = () => {
}

export const proof = {
toRange: [
// Two characters name the inclusive range's endpoints.
() => assertEq(toRange('az'), byteSetRange([0x61, 0x7a])),
// One character is the singleton range. This threw `RangeError: The
// number NaN cannot be converted to a BigInt` while `toRange` read a
// second character that was not there.
() => assertEq(toRange('a'), byteSetRange([0x61, 0x61])),
() => assertEq(toRange('a'), one(0x61)),
() => assertEq(toRange('\0'), one(0)),
],
dfa: () => {
const dfa = buildDfa()
const entries = Object.entries(dfa)
Expand Down
42 changes: 0 additions & 42 deletions fjs/fsm/todo/torange-ascii-range.md
View file
Open in desktop

This file was deleted.

Loading