Использование HashSet для канонизации объектов в Rust

В качестве учебного упражнения я смотрю на перенос cvs-fast-export в Rust.

Его основной режим работы - анализировать несколько основных файлов CVS в промежуточную форму, а затем анализировать промежуточную форму с целью преобразования ее в поток быстрого экспорта git.

Одна из вещей, которая выполняется при синтаксическом анализе, заключается в преобразовании общих частей промежуточной формы в каноническое представление. Мотивирующим примером являются авторы коммитов. Репозиторий CVS может содержать сотни тысяч отдельных файловых коммитов, но, вероятно, менее тысячи авторов. Таким образом, при разборе, когда вы вводите автора, когда вы анализируете его из файла, используется внутренняя таблица, и она даст вам указатель на каноническую версию, создающую новую, если она не видела ее раньше. (Я слышал, что это называется распыление или интернирование тоже). Этот указатель затем сохраняется на промежуточном объекте.

Моя первая попытка сделать что-то подобное в Rust пыталась использовать HashSet как интернирующий стол. Обратите внимание, что здесь используются номера версий CVS, а не авторы, это просто последовательность цифр, такая как 1.2.3.4, представленная в виде Vec,

use std::collections::HashSet;
use std::hash::Hash;

#[derive(PartialEq, Eq, Debug, Hash, Clone)]
struct CvsNumber(Vec<u16>);

fn intern<T:Eq + Hash + Clone>(set: &mut HashSet<T>, item: T) -> &T {
    let dupe = item.clone();
    if !set.contains(&item) {
        set.insert(item);
    }
    set.get(&dupe).unwrap()
}

fn main() {
    let mut set: HashSet<CvsNumber> = HashSet::new();
    let c1 = CvsNumber(vec![1, 2]);
    let c2 = intern(&mut set, c1);
    let c3 = CvsNumber(vec![1, 2]);
    let c4 = intern(&mut set, c3);
}

Это не с error[E0499]: cannot borrow 'set' as mutable more than once at a time, Это достаточно справедливо, HashSet не гарантирует, что ссылки на его ключи будут действительны, если вы добавите больше элементов после получения ссылки. Версия C старается гарантировать это. Чтобы получить эту гарантию, я думаю, HashSet должно быть закончено Box<T>, Однако я не могу объяснить время жизни для проверки заимствования.

Модель владения, которую я здесь использую, заключается в том, что интернациональная таблица владеет каноническими версиями данных и раздает ссылки. Ссылки должны быть действительными до тех пор, пока существует внутренняя таблица. Мы должны иметь возможность добавлять новые вещи во внутреннюю таблицу, не делая недействительными старые ссылки. Я думаю, что корень моей проблемы в том, что я запутался, как написать интерфейс для этого контракта в соответствии с моделью владения Rust.

Решения, которые я вижу с моим ограниченным знанием Rust:

  1. Сделать два прохода, построить HashSet на первом проходе, затем заморозьте его и используйте ссылки на втором проходе. Это означает дополнительное временное хранение (иногда существенное).
  2. небезопасный

У кого-нибудь есть идея получше?

Источник

2 ответа

Решение

Я несколько не согласен с @Shepmaster по использованию unsafe Вот.

Хотя сейчас это не вызывает проблем, если кто-то решит в будущем изменить использование HashSet включить некоторую обрезку (например, чтобы сохранить там только сотню авторов), затем unsafe сурово тебя укусит.

В отсутствие сильной причины производительности я бы просто использовал Rc<XXX>, Вы можете сделать это достаточно легко: type InternedXXX = Rc<XXX>;,

use std::collections::HashSet;
use std::hash::Hash;
use std::rc::Rc;

#[derive(PartialEq, Eq, Debug, Hash, Clone)]
struct CvsNumber(Rc<Vec<u16>>);

fn intern<T:Eq + Hash + Clone>(set: &mut HashSet<T>, item: T) -> T {
    if !set.contains(&item) {
        let dupe = item.clone();
        set.insert(dupe);
        item
    } else {
        set.get(&item).unwrap().clone()
    }
}

fn main() {
    let mut set: HashSet<CvsNumber> = HashSet::new();
    let c1 = CvsNumber(Rc::new(vec![1, 2]));
    let c2 = intern(&mut set, c1);
    let c3 = CvsNumber(Rc::new(vec![1, 2]));
    let c4 = intern(&mut set, c3);
}
Источник

Ваш анализ верен. Конечная проблема заключается в том, что при изменении HashSetкомпилятор не может гарантировать, что мутации не повлияют на существующие распределения. В самом деле, в общем случае они не будут, если вы не добавите еще один слой косвенности, как вы определили.

Это яркий пример места, которое unsafe Полезно. Вы, программист, можете утверждать, что код будет когда-либо использоваться только определенным образом, и этот конкретный способ позволит переменной быть стабильной при любых мутациях.

Обратите внимание, что String уже вводит кучу выделения. Пока вы не измените String как только он выделен, вам не нужно дополнительное Box,

Нечто подобное похоже на нормальное начало:

use std::collections::HashSet;
use std::cell::RefCell;

use std::mem;

struct EasyInterner(RefCell<HashSet<String>>);

impl EasyInterner {
    fn new() -> Self {
        EasyInterner(RefCell::new(HashSet::new()))
    }

    fn intern<'a>(&'a self, s: &str) -> &'a str {
        let mut set = self.0.borrow_mut();

        if !set.contains(s) {
            set.insert(s.into());
        }

        let interned = set.get(s).expect("Impossible missing string");

        // TODO: Document the pre- and post-conditions that the code must
        // uphold to make this unsafe code valid
        unsafe { mem::transmute(interned.as_str()) }
    }
}

fn main() {
    let i = EasyInterner::new();

    let a = i.intern("hello");
    let b = i.intern("world");
    let c = i.intern("hello");

    // Still strings
    assert_eq!(a, "hello");
    assert_eq!(a, c);
    assert_eq!(b, "world");

    // But with the same address
    assert_eq!(a.as_ptr(), c.as_ptr());
    assert!(a.as_ptr() != b.as_ptr());

    // This shouldn't compile; a cannot outlive the interner
    // {
    //    let i = EasyInterner::new();
    //    let a = i.intern("hello");
    //    a
    // };

    let the_pointer;
    let i = {
        let i = EasyInterner::new();
        {
            // Introduce a scope to contstrain the borrow of `i` for `s`
            let s = i.intern("inner");
            the_pointer = s.as_ptr();
        }
        i // moving i to a new location
        // All outstanding borrows are invalidated
    };

    // but the data is still allocated
    let s = i.intern("inner");
    assert_eq!(the_pointer, s.as_ptr());
}

Тем не менее, может оказаться более целесообразным использовать ящик, такой как string_cache, за которым стоит коллективный мозг проекта Servo.

Источник
Другие вопросы по тегам