Christopher Prohm

This post continues my journey of compile-time string processing in Rust. While working on the validation of identifiers I decided to implement compile-time validation of well-known identifiers. My initial assumption was that this task would be pretty straightforward. As it turns out, it is not. This post first looks into Rust's definition of identifiers and then combines it with the iteration scheme of the last post.

Rust defines identifiers in terms of Unicode Standard Annex #31. An identifier is a sequence of characters with specific Unicode properties. Those properties are specified in tables that list the ranges of characters with that property. This post uses the Unicode 17.0.0 data published in DerivedCoreProperties.txt.¹

Rust defines an identifier as follows. The initial character must have the Unicode property XID_Start or be an underscore (_). Subsequent characters must have Unicode property XID_Continue. Join characters (U+200C and U+200D) are not supported.

The derived core properties file contains sections for different properties that list the ranges of characters with that property. For example, the section for the XID_Start property starts with:

0041..005A    ; XID_Start # L&  [26] LATIN CAPITAL LETTER A..LATIN CAPITAL LETTER Z
0061..007A    ; XID_Start # L&  [26] LATIN SMALL LETTER A..LATIN SMALL LETTER Z

A Python script reads these ranges, filters them to the relevant properties, and then merges overlapping ranges of different properties. It writes the ranges as a const-compatible table with properties of a range encoded as a bit mask. The ranges are half-open, with an inclusive start and exclusive end. The full entry can be expressed as eight bytes. Scalar values are in the range 0x0 to 0x10ffff, that can be encoded in three bytes. One start and end, leaves space for a u16 property mask.

use std::range::Range;

const fn to_range(start: u32, end: u32) -> Range<[u8; 3]> {
    let start = start.to_le_bytes();
    let end = end.to_le_bytes();
    Range {
        start: [start[0], start[1], start[2]],
        end: [end[0], end[1], end[2]],
    }
}

pub const XID_CONTINUE: u16 = 1 << 0;
pub const XID_START: u16 = 1 << 1;
pub const PROPERTIES: &[(Range<[u8; 3]>, u16)] = &[
    (to_range(0x0, 0x30), 0),
    (to_range(0x30, 0x3a), XID_CONTINUE),
    (to_range(0x3a, 0x41), 0),
    (to_range(0x41, 0x5b), XID_CONTINUE | XID_START),
    // ...
];

The table fragment above encodes that

• "A" (0x41) through "Z" (0x5a) can be used to start or continue an identifier.
• "0" (0x30) through "9" (0x39) can be used to continue an identifier.
• \0 (0x00) through "/" (0x2f) and ":" (0x3a) through "@" (0x40) cannot appear in an identifier.

The lookup of a character uses bisection search to find the range containing the character. The generated table includes the gaps between properties with an empty mask, so it covers the complete Unicode scalar range. That invariant means the search always finds a range for every valid Rust char.

const fn get_char_properties(c: char) -> u16 {
    let needle = c as u32;

    let mut haystack_lower = 0_usize;
    let mut haystack_upper = PROPERTIES.len();

    loop {
        assert!(haystack_lower < haystack_upper);
        let idx = haystack_lower.midpoint(haystack_upper);
        let (Range { start, end }, properties) = PROPERTIES[idx];
        let start = u32::from_le_bytes([start[0], start[1], start[2], 0]);
        let end = u32::from_le_bytes([end[0], end[1], end[2], 0]);

        if needle < start {
            haystack_upper = idx;
        } else if needle >= end {
            haystack_lower = idx + 1;
        } else {
            break properties;
        }
    }
}

With the property mask, it is possible to check for the XID_Start and XID_Continue properties.

pub const fn is_xid_start(c: char) -> bool {
    (get_char_properties(c) & XID_START) != 0
}

pub const fn is_xid_continue(c: char) -> bool {
    (get_char_properties(c) & XID_CONTINUE) != 0
}

The Rust identifier start and continue character rules are then defined as

pub const fn is_rust_ident_start(c: char) -> bool {
    c == '_' || is_xid_start(c)
}

pub const fn is_rust_ident_continue(c: char) -> bool {
    c != '\u{200c}' && c != '\u{200d}' && is_xid_continue(c)
}

Finally, this check can be combined with the character iterator from the last post to define a function that checks whether a string is a valid rust identifier.

pub const fn is_rust_ident(s: &str) -> bool {
    let mut current = s;
    let mut pos = 0;

    while let Some((char, next)) = next_char(current) {
        let is_valid = match pos {
            0 => is_rust_ident_start(char),
            _ => is_rust_ident_continue(char),
        };
        if !is_valid {
            return false;
        }

        current = next;
        pos += 1;
    }

    // need at least one character
    pos != 0
}

As I was just as interested in learning as in solving my problem, I decided to write a fully custom implementation. The result is quite compact, simple, and usable from const-compatible code. However, there are existing Rust crates for this problem, even if not usable in const contexts. unicode-ident is the practical choice if all I need is XID_Start and XID_Continue. It is maintained for this exact use case and is optimized carefully. unicode-xid is another widely used crate for identifier classification. ucd-generate supports generating lookup tables, similar to those described above.