Rustのthread local gensym/internパターン

Rust

概要: Rustでgensymおよびinternを行う方法を説明する。

gensymとinternとは何か

  • gensymパターンは、「まだ使われていない整数」を返す fresh() 関数を実装するというパターンである。型推論などで一時変数を作成するなどの用途で用いられる。
  • internパターンは、文字列などの複雑なデータに対し、データの同値性に基づいて整数を振ることで簡単に比較等できるようにするというパターンである。

Rustによるthread local gensym

gensymは以下のように実現される。

  • スレッドローカル変数に、今まで払出した整数の最大値を記録する。
  • 必要に応じてこの変数をインクリメントする。

このとき生成されたIDは他スレッドと共有できないため、 !Send をつける。

use std::cell::Cell;

// u32を包む
#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
pub struct Symbol(u32);
impl !Send for Symbol {}

impl Symbol {
    pub fn fresh() -> Self {
        thread_local! {
            static NEXT_SYMBOL_ID : Cell<u32> = Cell::new(0);
        }
        NEXT_SYMBOL_ID.with(|next_symbol_id| {
            let symbol_id = next_symbol_id.get();
            next_symbol_id.set(symbol_id + 1);
            Symbol(symbol_id)
        })
    }
}

Rustによるthread local intern

internは以下のように実現される。

  • スレッドローカル変数に、今まで割り当て済みの文字列の一覧を、正引きと逆引きの組で保持する。
  • 必要に応じてエントリを追加する。

このとき生成されたIDは他スレッドと共有できないため、 !Send をつける。

use std::borrow::Borrow;
use std::cell::RefCell;
use std::collections::HashMap;
use std::hash::Hash;

#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
pub struct Symbol(u32);
impl !Send for Symbol {}

struct SymbolTable {
    strings: Vec<String>,
    symbols: HashMap<String, Symbol>,
}

thread_local! {
    static SYMBOL_TABLE : RefCell<SymbolTable> = RefCell::new(SymbolTable {
        strings: Vec::new(),
        symbols: HashMap::new(),
    });
}

impl Symbol {
    pub fn intern<Q:?Sized + Hash + Eq + ToOwned<Owned=String>>(s: &Q) -> Self where String: Borrow<Q> {
        SYMBOL_TABLE.with(|symbol_table_cell| {
            let SymbolTable {
                ref mut strings,
                ref mut symbols,
            } = *symbol_table_cell.borrow_mut();
            if let Some(&symbol) = symbols.get(s) {
                symbol
            } else {
                let symbol = Symbol(strings.len() as u32);
                strings.push(s.to_owned());
                symbols.insert(s.to_owned(), symbol);
                symbol
            }
        })
    }
    pub fn to_str(self) -> String {
        SYMBOL_TABLE.with(|symbol_table_cell| {
            let symbol_table = symbol_table_cell.borrow();
            symbol_table.strings[self.0 as usize].clone()
        })
    }
}

Rustコンパイラ内でのthread local gensym/internパターンの使用例

まとめ

gensymとinternは文脈依存のIDを生成するデザインパターンである。Rustではこれをスレッドローカル変数を用いて実装する場合がある。