Skip to content

stdlib.misc

Miscellaneous Pure Algorithm Utilities

Generated from v0.65.7. 6 source files, 83 documented symbols.

glob.xi

fn glob_match(pattern: Str, s: Str) -> Bool

Match s against a glob pattern supporting '?' (any single character) and '*' (zero or more characters). O(pattern.len() * s.len()) worst, with the classic star-backtracking algorithm. Pattern matching is case-sensitive.

  • Postcondition: ((pattern.len() == 0) => (result == (s.len() == 0))) && ((pattern == "*") => (result == true))
fn glob_match_case_insensitive(pattern: Str, s: Str) -> Bool

Case-insensitive glob match: same semantics as glob_match but compares characters with case folding. O(pattern.len() * s.len()) worst.

  • Postcondition: ((pattern.len() == 0) => (result == (s.len() == 0))) && ((pattern == "*") => (result == true))
fn glob_escape(s: Str) -> Str

Escape glob metacharacters ('*', '?', '[') in s with a backslash so the result matches literally. O(len).

  • Postcondition: ((glob_has_magic(s) == false) => (result == s)) && ((s.len() == 0) => (result.len() == 0))
fn glob_unescape(s: Str) -> Str

Undo glob escaping: remove one backslash before each metacharacter. O(len).

  • Postcondition: (s.len() == 0) => (result == s)
fn glob_has_magic(s: Str) -> Bool

Whether s contains any glob metacharacter ('*', '?', '['). O(len).

  • Postcondition: ((s.len() == 0) => (result == false)) && ((result == true) => (s.len() > 0))
fn glob_quote(s: Str) -> Str

Quote s so it matches literally: the same as glob_escape. O(len).

  • Postcondition: ((glob_has_magic(s) == false) => (result == s)) && ((s.len() == 0) => (result.len() == 0))
fn glob_translate(pattern: Str) -> Str

Convert a glob pattern to a regex pattern string: '' becomes '.', '?' becomes '.', and other regex metacharacters are escaped. O(len).

  • Postcondition: (pattern.len() == 0) => (result.len() == 0)
fn glob_compile(pattern: Str) -> Result[Int, Str]

Compile a glob pattern for repeated matching. This implementation keeps a single compiled-pattern slot: each call replaces the previous pattern, and the returned handle is always 1 (any other value is invalid). Matches use the same semantics as glob_match ('*' and '?' metacharacters, case-sensitive). Errors: Err on an empty pattern.

  • Postcondition: ((pattern.len() == 0) => (result.is_err == true)) && ((pattern.len() > 0) => (result.is_ok == true))
fn glob_compile_match(compiled: Int, s: Str) -> Bool

Match s against the pattern most recently compiled by glob_compile. Returns false when compiled is not the current handle (or the slot is still empty). O(p * s) worst.

  • Postcondition: (compiled != 1) => (result == false)
fn glob_match_ext(pattern: Str, s: Str) -> Bool

Match s against the extended glob syntax, CASE-SENSITIVE: '' zero or more characters (a second '' is not special here) '?' exactly one character '[...]' one character class: leading '!' or '^' negates, '-' spans ranges ('a-z'), ']' first is a literal member, '\' escapes inside the class '\x' literal x (a backslash escapes the next pattern character) An unterminated '[' is a literal '['. O(|pattern| * |s|) worst case.

  • Postcondition: (pattern.len() == 0) => (result == (s.len() == 0))
fn glob_match_path(pattern: Str, path: Str, sep: Char) -> Bool

Path-aware glob match, CASE-SENSITIVE, over separator sep ('/', '\', or any byte): '?' matches one non-separator character, '' zero or more non-separator characters, '[...]' one non-separator character, and a pattern segment of two or more '' only is a GLOBSTAR matching zero or more WHOLE path segments (leading, middle and trailing positions all work; "src/**" therefore also matches "src" itself). There is NO escape character in this dialect -- a backslash is an ordinary character, so Windows-style patterns need no quoting. A trailing separator in the pattern demands a trailing (empty) segment. O(|pattern| * |path|) worst.

  • Postcondition: (pattern.len() == 0) => (result == (path.len() == 0))
fn glob_match_path_any(pattern: Str, path: Str) -> Bool

Like glob_match_path with BOTH '/' and '\' treated as separators, for mixed POSIX/Windows path trees. CASE-SENSITIVE. Because a backslash is always a separator here, this dialect has no escape character either (use glob_match_ext for escape semantics). O(|pattern| * |path|) worst case.

  • Postcondition: (pattern.len() == 0) => (result == (path.len() == 0))

levenshtein.xi

fn levenshtein_distance(a: Str, b: Str) -> Int

The minimum edit distance between a and b (insert/delete/substitute). O(m*n) time, O(min(m,n)) space via a rolling row.

  • Postcondition: ((a.len() == 0) => (result == b.len())) && ((b.len() == 0) => (result == a.len())) && ((a == b) => (result == 0))
fn levenshtein_distance_limited(a: Str, b: Str, max: Int) -> Int

Edit distance capped at max. Returns the true distance when it is <= max, otherwise returns max + 1 (indicating the distance exceeds the cap). O(m*n) worst but only evaluates the diagonal band that can stay within the limit, so long divergent strings exit early.

  • Postcondition: ((a.len() == 0 && b.len() <= max && max >= 0) => (result == b.len())) && ((a.len() > b.len() + max && max >= 0) => (result == max + 1))
fn levenshtein_similarity(a: Str, b: Str) -> Float64

Normalized similarity in [0, 1]: 1 - dist / max(len_a, len_b). Equal strings score 1.0; completely different strings approach 0.0.

  • Postcondition: ((a == b && a.len() > 0) => (result == 1)) && ((a.len() == 0 && b.len() == 0) => (result == 1))
fn levenshtein_matrix(a: Str, b: Str) -> Vec[Vec[Int]]

Compute the full (m+1) x (n+1) dynamic-programming matrix for a and b. matrix[i][j] is the edit distance between a[0..i) and b[0..j). O(m*n). NOTE: nested Vec[Vec[Int]] element access is unreliable in the current compiler - treat the result as opaque.

  • Postcondition: (a.len() == 0) => (result.len() == 1)
fn levenshtein_align(a: Str, b: Str) -> (Str, Str)

Optimal alignment of a and b as (aligned_a, aligned_b) with '-' marking gaps. O(mn) time, O(mn) space.

  • Postcondition: result._0.len() == result._1.len()
  • Postcondition: result._0.len() >= a.len() && result._0.len() >= b.len()
  • Postcondition: result._0.len() <= a.len() + b.len()
fn levenshtein_edit_script(a: Str, b: Str) -> Vec[Str]

The sequence of edit operations transforming a into b. Operations are "keep:c", "del:c", "ins:c" and "sub:x>y". O(m*n).

  • Postcondition: ((a.len() == 0 && b.len() == 0) => (result.len() == 0)) && ((a.len() == 0 && b.len() > 0) => (result.len() == b.len()))
fn damerau_levenshtein(a: Str, b: Str) -> Int

Damerau-Levenshtein distance with unrestricted adjacent transpositions. O(mn) time, O(mn) space. Uses the classic last-occurrence algorithm.

  • Postcondition: ((a.len() == 0) => (result == b.len())) && ((b.len() == 0) => (result == a.len()))
fn osa_distance(a: Str, b: Str) -> Int

Optimal string alignment (restricted transposition) distance. O(mn) time, O(mn) space. Only allows adjacent transpositions that are not themselves part of further transpositions.

  • Postcondition: ((a.len() == 0) => (result == b.len())) && ((b.len() == 0) => (result == a.len()))
fn wagner_fischer(a: Str, b: Str) -> Int

Classic Wagner-Fischer edit distance (full-matrix variant of the standard Levenshtein distance). O(mn) time, O(mn) space.

  • Postcondition: ((a.len() == 0) => (result == b.len())) && ((b.len() == 0) => (result == a.len()))

misc.xi

fn semver_compare(a: Str, b: Str) -> Int

Compare two semantic version strings (major.minor.patch). Returns -1 if a < b, 0 if equal, 1 if a > b.

  • Precondition: a.len() > 0
  • Precondition: b.len() > 0

fn levenshtein_distance(a: Str, b: Str) -> Int

Compute the Levenshtein (edit) distance between two strings. Uses dynamic programming with O(m*n) time and O(min(m,n)) space.

  • Postcondition: result >= 0

fn glob_match(pattern: Str, text: Str) -> Bool

Match a string against a glob pattern supporting: '?' matches any single character '*' matches zero or more characters

  • Postcondition: (pattern.len() == 0 && text.len() != 0) => (result == false)
  • Postcondition: (pattern == "*") => (result == true)

fn natural_compare(a: Str, b: Str) -> Int

Compare two strings using natural sort order (e.g., "file2" < "file10"). Returns -1 if a < b, 0 if equal, 1 if a > b.

  • Postcondition: (a.len() == 0 && b.len() == 0) => (result == 0)
  • Postcondition: (a.len() == 0 && b.len() != 0) => (result == -1)

fn slugify(s: Str) -> Str

Convert a string to a URL-friendly slug (lowercased, non-alnum -> '-').

  • Postcondition: result.len() <= s.len()

fn soundex(code: Str) -> Str

Compute the classic American Soundex code for a string (4 chars). Delegates to the canonical xiom.misc.soundex shim (pre-1.0 alignment: the empty string encodes as "", not the legacy "0000"). Kept as a unique delegation so bare soundex(...) calls stop binding the stale copy that returned "0000" (duplicate-leaf class; see the compiler-lane relay).

  • Postcondition: (code.len() == 0) => (result.len() == 0)

fn is_palindrome(s: Str) -> Bool

Check if a string reads the same forward and backward.

  • Postcondition: (s.len() == 0) => (result == true)

fn reverse_str(s: Str) -> Str

Return the reversed copy of a string.

  • Postcondition: result.len() == s.len()

fn count_occurrences(haystack: Str, needle: Str) -> Int

Count non-overlapping occurrences of needle in haystack.

  • Precondition: needle.len() > 0
  • Postcondition: result >= 0

fn truncate(s: Str, max_len: Int) -> Str

Truncate a string to at most max_len bytes.

  • Precondition: max_len >= 0
  • Postcondition: result.len() <= s.len()

fn damerau_levenshtein_distance(a: Str, b: Str) -> Int

Damerau-Levenshtein distance (insert/delete/substitute/transpose), O(n*m).

  • Postcondition: (a.len() == 0) => (result == b.len())
  • Postcondition: (b.len() == 0) => (result == a.len())

fn jaro_similarity(a: Str, b: Str) -> Float64

Jaro similarity in [0, 1] (ASCII-aware matching window).

  • Postcondition: (a.len() == 0 && b.len() == 0) => (result == 1)
  • Postcondition: (a.len() == 0 && b.len() != 0) => (result == 0)
  • Postcondition: (a.len() != 0 && b.len() == 0) => (result == 0)

fn jaro_winkler_similarity(a: Str, b: Str) -> Float64

Jaro-Winkler similarity (prefix bonus up to 4 chars, scale 0.1).

  • Postcondition: (a.len() == 0 && b.len() == 0) => (result == 1)

fn hamming_distance(a: Str, b: Str) -> Int

Hamming distance; -1 if lengths differ.

  • Postcondition: (a.len() != b.len()) => (result == -1)

fn longest_common_subsequence(a: Str, b: Str) -> Str

Longest common subsequence (not substring), O(n*m).

  • Postcondition: (a.len() == 0 || b.len() == 0) => (result.len() == 0)

fn to_roman(n: Int) -> Str

Roman numerals for 1..3999; "" outside the range.

  • Precondition: n >= 1
  • Precondition: n <= 3999

fn from_roman(s: Str) -> Int

Parse a Roman numeral; 0 if invalid.

  • Postcondition: (s.len() == 0) => (result == 0)

fn to_camel_case(s: Str) -> Str

Convert to camelCase.

  • Postcondition: (s.len() == 0) => (result.len() == 0)

fn to_pascal_case(s: Str) -> Str

Convert to PascalCase.

  • Postcondition: (s.len() == 0) => (result.len() == 0)

fn to_snake_case(s: Str) -> Str

Convert to snake_case.

  • Postcondition: (s.len() == 0) => (result.len() == 0)

fn to_kebab_case(s: Str) -> Str

Convert to kebab-case.

  • Postcondition: (s.len() == 0) => (result.len() == 0)

fn ordinal(n: Int) -> Str

Ordinal suffix: 1st, 2nd, 3rd, 11th, 21st, ...

  • Postcondition: (n == 1) => (result == "1st")
  • Postcondition: (n == 11) => (result == "11th")

fn pluralize(s: Str, count: Int) -> Str

Naive pluralize: count == 1 keeps the singular; otherwise +s / +es / +ies.

  • Postcondition: (count == 1) => (result == s)
  • Postcondition: (s.len() == 0) => (result == s)

fn is_anagram(a: Str, b: Str) -> Bool

Anagrams (ASCII case-insensitive letter counts).

  • Postcondition: (a.len() == 0 && b.len() == 0) => (result == true)

fn celsius_to_fahrenheit(c: Float64) -> Float64

---- Units ----

  • Postcondition: (c == 0) => (result == 32)

fn fahrenheit_to_celsius(f: Float64) -> Float64

Fahrenheit to Celsius.

  • Postcondition: (f == 32) => (result == 0)

fn celsius_to_kelvin(c: Float64) -> Float64

Celsius to Kelvin.

  • Postcondition: (c == 0) => (result == 273.15)

fn kelvin_to_celsius(k: Float64) -> Float64

Kelvin to Celsius.

  • Postcondition: (k == 273.15) => (result == 0)

fn fahrenheit_to_kelvin(f: Float64) -> Float64

Fahrenheit to Kelvin.

  • Postcondition: (f == -459.67) => (result == 0)

fn kelvin_to_fahrenheit(k: Float64) -> Float64

Kelvin to Fahrenheit.

  • Postcondition: (k == 0) => (result == -459.67)

fn miles_to_km(m: Float64) -> Float64

Miles to kilometres.

  • Postcondition: (m == 1) => (result == 1.609344)

fn km_to_miles(km: Float64) -> Float64

Kilometres to miles.

  • Postcondition: (km == 1.609344) => (result == 1)

fn human_size(bytes: Int) -> Str

Human-readable byte size: "512 B", "1.5 KB", "3.2 MB", ... Integer math only (the runtime lacks decimal float formatting).

  • Postcondition: (bytes <= 0) => (result == "0 B")

natural.xi

fn natural_compare(a: Str, b: Str) -> Int

Compare a and b in natural order: -1, 0, or 1. Embedded digit runs are compared numerically (so "file2" < "file10"); other characters compare by code point. O(min(len_a, len_b)).

  • Postcondition: result >= -1 && result <= 1
fn natural_compare_ignore_case(a: Str, b: Str) -> Int

Natural comparison ignoring case: digit runs compare numerically, letters compare by lowercase code point. O(min(len_a, len_b)).

  • Postcondition: result >= -1 && result <= 1
fn natural_sort(strings: &Vec[Str]) -> Vec[Str]

A copy of strings sorted naturally (ascending). O(k^2 * n) with insertion sort; stable.

  • Postcondition: result.len() == strings.len()
fn natural_sort_by(items: &Vec[Str], key: fn(&Str) -> Str) -> Vec[Str]

Sort items by an extracted natural key, returning a new vector. O(k^2 * n). The key function must be named and return a Str. NOTE: implemented as a concrete Vec[Str] specialization of the frozen generic API (compiler fn-ptr codegen bug - docs/STDLIB_GENERICS.md).

  • Postcondition: result.len() == items.len()
fn natural_key(s: Str) -> Vec[(Int, Str)]

The comparison segments of s; each tuple is (digit_value, chunk). Digit runs yield (parsed_value, digit_string); text runs yield (0, text_chunk). O(n).

  • Postcondition: ((s.len() == 0) => (result.len() == 0)) && ((s.len() > 0) => (result.len() >= 1))
fn natural_chunk(s: Str) -> Vec[Str]

Split s into alternating digit and text chunks. O(n).

  • Postcondition: ((s.len() == 0) => (result.len() == 0)) && ((s.len() > 0) => (result.len() >= 1))
fn natural_is_digit_run(s: Str, i: Int) -> Bool

Whether s contains a digit run starting at index i. O(1). Returns false when i is out of bounds.

  • Postcondition: ((i < 0 || i >= s.len()) => (result == false)) && ((result == true) => (i >= 0 && i < s.len()))
fn natural_compare_numeric(a: Str, b: Str) -> Int

Compare two pure numeric strings by value (leading zeros are ignored). O(n). Returns -1, 0, or 1. Non-digit content compares lexicographically.

  • Postcondition: result >= -1 && result <= 1
fn natural_sort_desc(strings: &Vec[Str]) -> Vec[Str]

A copy of strings sorted naturally in descending order. O(k^2 * n).

  • Postcondition: result.len() == strings.len()

semver.xi

type SemVer

A semantic version: major, minor, patch, prerelease and build metadata. prerelease and build are the raw dot-separated identifier strings (without the '-' / '+' prefix); empty when absent.

Field Type
major Int
minor Int
patch Int
prerelease Str
build Str
fn semver_parse(s: Str) -> Option[SemVer]

Parse a semantic version string such as "1.2.3", "1.2.3-alpha.1" or "1.2.3+build.5". An optional leading 'v'/'V' is accepted. Returns None for malformed input (missing parts, non-numeric core, invalid identifiers).

  • Postcondition: (s.len() == 0) => (result.is_none == true)
  • Postcondition: (s.len() == 1) => (result.is_none == true)
  • Postcondition: (s == "1.2.3") => (result.is_some == true)
fn semver_compare(a: SemVer, b: SemVer) -> Int

Compare two SemVer values by precedence: -1, 0, or 1. Build metadata is ignored; a version without prerelease outranks one with a prerelease.

  • Postcondition: (a.major < b.major) => (result == -1)
  • Postcondition: (a.major == b.major && a.minor == b.minor && a.patch == b.patch && a.prerelease.len() == 0 && b.prerelease.len() == 0) => (result == 0)
fn semver_valid(s: Str) -> Bool

Whether s is a valid semantic version string. O(n).

  • Postcondition: (s.len() == 0) => (result == false)
fn semver_matches(version: Str, constraint: Str) -> Bool

Whether a version string satisfies a constraint string. Supports operator prefixes (>=, <=, >, <, =), caret (^), tilde (~), bare versions, partial versions ("1.2", "1", "1.2.x") and space-separated AND groups.

  • Postcondition: (version.len() == 0) => (result == false)
fn semver_satisfies(version: Str, range: Str) -> Bool

Whether a version falls inside a hyphen ("a - b") or comma-separated range. Comma-separated parts are alternatives (OR); a hyphen range is inclusive on both ends. A bare range delegates to semver_matches.

  • Postcondition: (version.len() == 0) => (result == false)
fn semver_inc(s: Str, part: Str) -> Option[Str]

Bump a version part ("major", "minor", "patch", "prerelease", "build"). Returns the new version string, or None if s is not a valid version. prerelease bumps the trailing numeric identifier (appending ".0" when the prerelease is not numeric); build does the same for build metadata.

  • Postcondition: (s.len() == 0) => (result.is_none == true)
fn semver_to_string(v: SemVer) -> Str

Serialize a SemVer back to text. O(n).

  • Postcondition: (v.major == 1 && v.minor == 2 && v.patch == 3 && v.prerelease.len() == 0 && v.build.len() == 0) => (result == "1.2.3")
fn semver_prerelease(v: SemVer) -> Option[Str]

The prerelease identifier, if any.

  • Postcondition: (v.prerelease.len() == 0) => (result.is_none == true)
fn semver_build(v: SemVer) -> Option[Str]

The build metadata, if any.

  • Postcondition: (v.build.len() == 0) => (result.is_none == true)
fn semver_caret(a: SemVer, b: SemVer) -> Bool

Caret compatibility: whether b falls in the caret range anchored at a.

  • Postcondition: (a.major > 0 && b.major != a.major) => (result == false)
fn semver_tilde(a: SemVer, b: SemVer) -> Bool

Tilde compatibility: whether b falls in the tilde range anchored at a.

  • Postcondition: (b.major != a.major) => (result == false)
fn semver_gt(a: SemVer, b: SemVer) -> Bool

Strict greater-than comparison of two SemVer values.

  • Postcondition: result == (semver_compare(a, b) > 0)
fn semver_lt(a: SemVer, b: SemVer) -> Bool

Strict less-than comparison of two SemVer values.

  • Postcondition: result == (semver_compare(a, b) < 0)

soundex.xi

fn soundex(s: Str) -> Str

Four-character American Soundex code of s (canonical: returns "" for empty input). Params: s the word to encode. Returns: the code. Complexity: O(|s|).

  • Postcondition: (s.len() == 0) => (result.len() == 0)
fn soundex_compare(a: Str, b: Str) -> Bool

Whether two strings share a Soundex code. O(|a| + |b|).

  • Postcondition: (a == b) => (result == true)
fn soundex_encode(s: Str) -> Str

Alias for soundex (kept for API compatibility). O(|s|).

  • Postcondition: (s.len() == 0) => (result.len() == 0)
fn soundex_key(s: Str) -> Str

Canonical comparison key for s: the standard Soundex code. O(|s|).

  • Postcondition: (s.len() == 0) => (result.len() == 0)
fn soundex_similarity(a: Str, b: Str) -> Float64

Similarity in [0, 1] from the number of matching Soundex digits. O(1). Canonical-aligned edge cases: two empty inputs score 1.0; exactly one empty input scores 0.0 (the old duplicate compared "0000" codes instead).

  • Postcondition: ((a.len() == 0 && b.len() == 0) => (result == 1)) && ((a.len() == 0 && b.len() > 0) => (result == 0))
fn soundex_variants(s: Str) -> Vec[Str]

Deterministic alternate Soundex codes for s. Returns a vector with the standard code plus a code that encodes the first letter's own digit (a common variant). O(|s|). The first element is always the canonical code.

  • Postcondition: result.len() == 2