Блог

В качестве учебного упражнения я рассматриваю возможность переноса 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: amp;mut HashSet<T>, item: T) -> amp;T {
    let dupe = item.clone();
    if !set.contains(amp;item) {
        set.insert(item);
    }
    set.get(amp;dupe).unwrap()
}

fn main() {
    let mut set: HashSet<CvsNumber> = HashSet::new();
    let c1 = CvsNumber(vec![1, 2]);
    let c2 = intern(amp;mut set, c1);
    let c3 = CvsNumber(vec![1, 2]);
    let c4 = intern(amp;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. Небезопасно

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

Я несколько не согласен с @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: amp;mut HashSet<T>, item: T) -> T {
    if !set.contains(amp;item) {
        let dupe = item.clone();
        set.insert(dupe);
        item
    } else {
        set.get(amp;item).unwrap().clone()
    }
}

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

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

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

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

Что-то вроде этого кажется подходящим началом:

 use std::{cell::RefCell, collections::HashSet, mem};

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

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

    fn intern<'a>(amp;'a self, s: amp;str) -> amp;'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 instead of copying this
        // from Stack Overflow without reading it
        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 x = {
    //     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.
• типизированный-arena
• generational-арена