Struct NodeIndex 

pub struct NodeIndex(/* private fields */);

A unique index for a node within an AST.

Our encoding of 32-bit AST node indices is as follows:

• u32::MAX (1111…1) is reserved as a forbidden value (mapped to 0 for NonZero)
• u32::MAX - 1 (1111…0) is reserved for NodeIndex::NONE
• The top two bits encode the sub-AST level:
  • 00 is top-level AST
  • 01 is sub-AST (string annotation)
  • 10 is sub-sub-AST (string annotation in string annotation)
  • 11 is forbidden (well, it only appears in the above reserved values)
• The remaining 30 bits are the real (sub)-AST node index

To get the first sub-index of a node’s sub-AST we:

• increment the sub-AST level in the high-bits
• at level 1, multiply the real index by 256
• at level 2, multiply the real index by 8

The multiplication gives each node a reserved space of 256 nodes for its sub-AST to work with (“should be enough for anybody”), and 8 nodes for a sub-sub-AST (enough for an identifier and maybe some simple unions).

Here are some implications:

• We have 2^30 top-level AST nodes (1 billion)
• To have a string annotation, the parent node needs to be multiplied by 256 without overflowing 30 bits, so string annotations cannot be used after 2^22 nodes (4 million), which would be like, a million lines of code.
• To have a sub-string annotation, the top-level node needs to be multiplied by 256 * 8, so sub-string annotations cannot be used after 2^19 nodes (500 thousand), or about 100k lines of code.

This feels like a pretty reasonable compromise that will work well in practice, although it creates some very wonky boundary conditions that will be very unpleasant if someone runs into them.

That said, string annotations are in many regards “legacy” and so new code ideally doesn’t have to use them, and there’s never a real reason to use sub-annotation let-alone a sub-sub-annotation.

Implementations

impl NodeIndex

pub const NONE: NodeIndex

A placeholder NodeIndex.

pub fn as_u32(self) -> Option<u32>

Returns the index as a u32. or None for NodeIndex::NONE.

Trait Implementations

impl Clone for NodeIndex

fn clone(&self) -> NodeIndex

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for NodeIndex

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl From<u32> for NodeIndex

fn from(value: u32) -> NodeIndex

Converts to this type from the input type.

impl GetSize for NodeIndex

fn get_heap_size(&self) -> usize

Determines how many bytes this object occupies inside the heap.

fn get_heap_size_with_tracker<TRACKER>( &self, tracker: TRACKER, ) -> (usize, TRACKER)

where TRACKER: GetSizeTracker,

Determines how many bytes this object occupies inside the heap while using a tracker.

fn get_stack_size() -> usize

Determines how may bytes this object occupies inside the stack.

fn get_size(&self) -> usize

Determines the total size of the object.

fn get_size_with_tracker<T>(&self, tracker: T) -> (usize, T)

where T: GetSizeTracker,

Determines the total size of the object while using a tracker.

impl Hash for NodeIndex

fn hash<__H>(&self, state: &mut __H)

where __H: Hasher,

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Ord for NodeIndex

fn cmp(&self, other: &NodeIndex) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for NodeIndex

fn eq(&self, other: &NodeIndex) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for NodeIndex

fn partial_cmp(&self, other: &NodeIndex) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Copy for NodeIndex

impl Eq for NodeIndex

impl StructuralPartialEq for NodeIndex