How do you map AST nodes to symbols?

help
1

I've wrote some verifiers, or symbol solvers, for a language and used two different ways of attaching resolved symbols to AST nodes:

  • using fields prefixed by semantic, and
  • building a hash map from AST node to symbol

I could easily do the first way in Rust, but it seems unelegant as it mixes with syntactic fields. How would I do the second in Rust, given that Rc: Hash hashes the inner content instead of the Rc's address?

2

Two ways come to mind:

  1. Give each node a unique ID, and use that as the key into the map.

  2. Use a HashMap<PtrOf<Rc<Node>>, Symbol>, where PtrOf is a wrapper type that compares and hashes just the dereffed address of its parameter. (I've done something similar when I needed to use floats as keys into a map—but don't tell anyone, I'll get my credentials revoked!)

1 Like
3

Generating an unique ID would add some complexity, so I am giving your second idea a try:

use std::{rc::Rc, hash::Hash};

/// Allows hashing a `Rc<T>` value by its address and not its contents.
/// This struct additionally allows cloning and comparing equality
/// by pointer reference.
pub struct RcHashable<T>(pub Rc<T>);

impl<T> Hash for RcHashable<T> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        Rc::as_ptr(&self.0).hash(state)
    }
}

impl<T> Clone for RcHashable<T> {
    fn clone(&self) -> Self {
        Self(Rc::clone(&self.0))
    }
}

impl<T> Eq for RcHashable<T> {}

impl<T> PartialEq for RcHashable<T> {
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}
4

by_address — Rust library // Lib.rs provides this as a crate, if you prefer to go that route.

1 Like