Короткий обзор очередных обновлений смотрелки логов chipmunk. Много исправлений, много корректировок и немного фишек, в том числе запрашиваемых сообществом.

Последний релиз 2.16.2 вышел пару дней назад и содержит довольно много исправлений, кроме того оптимизирована работа ряда функций. Нет смысла останавливаться на полном перечне изменений, но стоит упомянуть о том, что могло бы быть полезно вам.

В деталях

Появилось новое приложение для боковой панели Shell. Фактически это простая запускалка консольных команд. Работает крайне просто вбиваем команду смотрим вывод. Таким образом вы можете проанализировать в chipmunk вывод от любой интересующей вас команды, будь то adb logcat, journalctl или tail.

Кстати о последнем, мы получали от сообщества вопросы о поддержке обновления открытого файла и это будет реализовано в версии 3.0 вместе с миграцией всего ядра на rust. Однако, уже сейчас вы можете просто запустить команду tail -f name_of_live_logfile и получать живой вывод. Естественно, если при этом у вас будет активный поиск, то и результаты его будут обновляться автоматически.

Кроме того, Shell позволяет редактировать переменные окружения. Вы можете изменить или добавить переменные, сохранить всё в ваш профайл и после просто его выбрать. Может быть весьма удобно, если какая-то из ваших консольных программ берёт данные из окружения.

Блиц

• DLT коннектор теперь понимает и UDP, и TCP, и IPv4 и IPv6. Последние не требуют каких-либо галочек и переключателей, тип адреса будет определён автоматически. Также можно подключиться к нескольким multicast точкам.

• Исправили рендер графиков. Теперь все отрисовывается корректно и при изменении размеров окна, и при переключении между сессиями.

• От встроенного терминала решили отказаться. Он не несёт в себе никакого функционала, который можно было бы с пользой интегрировать с chipmunk, но добавляет головной боли с точки зрения зависимостей и стабильности работы программы.

• Научили chipmunk обновляться через прокси (соответствующие настройки можно найти в меню Settings/General/Network

• Добавили поддержку копирования и экспорта результатов поиска.

Пожалуй это самое важное. Я не рискну сейчас анонсировать точные сроки по версии 3.0 с ядром на rust, скажу лишь то, что мы рассчитываем на этот год. И это будет легче достигнуть с Вашей поддержкой ведь каждая новая звёздочка на github это не только ценная обратная связь, но и наша ответственность перед Вами!

Спасибо. Тепла, добра и света!

Я долго откладывал этот день, но вечно откладывать было нельзя. Что ж, время пришло. Пора наконец разобраться с макросами в Rust. Ну или хотя бы начать.

Давайте сразу определимся, зачем вы хотите их использовать. Макросы - это про метапрограммирование и, можно даже сказать отчасти про reflective программирование. Я, конечно, не разработчик паттернов и стандартов, но использовать макрос (объявленный macro_rules!) как замену функции, как по мне, плохая идея. Во-первых, потому, что функция принимает переменные конкретного типа, а макрос, который принимает переменную, банально не знает её типа, соответственно, понять смысл операций можно только по названию и по самой сигнатуре макроса. А синтаксис макросов не то чтобы очень очевиден

Но, надеюсь, благодаря этой статье он станет более понятен для вас.

Что за зверь такой, macro_rules!?

Давайте начнём с самого простого. macro_rules! - наш путь к написанию макросов, встроенный прямо в стандартную библиотеку. Давайте начнём с простого примера - макрос, который делает то же, что и unwrap. Это, конечно, невероятно глупая и плохая идея, но для примера подойдёт.

Обратите внимание, что макрос объявлен до вызова.

Проверить:

macro_rules! uncover{

($var:ident) => {

match $var{

Some(t) => t,

None => panic!("None value")

}

}

}

fn main(){

let x = Some(2i32);

let unwrapped = uncover!(x);

println!("{}", unwrapped);

}

Ну-с давайте разбираться. Что же мы сделали? Перво-наперво, мы объявили макрос uncover:

macro_rules! uncover

Который принимает переменную $var типа ident. Вообще говоря, ident это не только переменная, но и название функции. Полный список типов, которые можно передать как аргумент в макрос можно поглядеть тут.

В каком-то смысле, вы передаёте в макрос не переменную, а код. Все, что знает макрос про $var - это название того, что мы передали в uncover (в нашем случае, х).

Далее идёт код, который вполне себе похож на нативный Rust код, однако есть момент, который бросается в глаза: мы используем переменную со знаком доллара. Итак, что же сделает этот макрос при вызове? Он вставит всю сигнатуру на то место, где вы его вызываете. То есть по сути в рантайме код будет выглядеть не так:

let unwrapped = uncover!(x);

А так:

let unwrapped = match x{

Some(t) => t,

None => panic!(None value)

};

Использовать макросы как обычные функции - плохая идея. Они делают не то же самое, что функции (хотя чем-то похоже на inline-фуннции). И хоть код

let x = 2i32;

let unwrapped = uncover!(x);

не скомпилируется, лучше использовать старые-добрые функции. Всё-таки, они более явные и отлично выполняют цель, с которой были созданы.

Summary

Итак, зачем же тебе, простой Иван город Тверь, писать макросы? Да не знаю, сам подумай. Может, есть повторяющееся место в коде, под которое идеально подойдёт макрос? Или ты написал нереальную реализацию списка со скоростью работы O(1) и хочешь инициализировать его вот так: list![1,2,3] ? Ну или тебе просто нравится заниматься метапрограммированием? Правда, последнее трудно вяжется с macro_rules! Всё-таки, в языке есть более мощное метапрограммирование, тёмная магия proc_macro, syn, qoute и TokenTree, но о ней как-нибудь в другой раз.

Вот, собственно, и всё. Писать макросы с помощью macro_rules не так-то сложно, главное разобраться в базовых правилах. Может, это сбережёт ваши нервы и/или деньги. Конечно, я не затрагивал в этой статье самое интересное, это наиболее простое из того, что есть. Цель статьи - показать, что макросы - это несложно.

Пишите, если хотите статью про proc_macro и syn, там действительно есть на что посмотреть.

Корректность кода на платформе Android является наиважнейшим аспектом в контексте безопасности, стабильности и качества каждого релиза Android. По-прежнему сложнее всего вытравливаются ошибки, связанные с безопасностью памяти и попадающиеся в коде на С и C++. Google вкладывает огромные усилия и ресурсы в обнаружение, устранение багов такого рода, а также в уменьшение вреда от них, старается, чтобы багов в релизы Android проникало как можно меньше. Тем не менее, несмотря на все эти меры, ошибки, связанные с безопасностью памяти, остаются основным источником проблем со стабильностью. На их долю неизменно приходится ~70% наиболее серьезных уязвимостей Android.

Наряду с текущимиипланируемымимероприятиями по улучшению выявления багов, связанных с памятью, Google также наращивает усилия по их предотвращению. Языки, обеспечивающие безопасность памяти наиболее эффективные и выгодные средства для решения этой задачи. Теперь в рамках проекта Android Open Source Project (AOSP) наряду с языками Java и Kotlin, отличающимися безопасностью памяти, поддерживается и язык Rust, предназначенный для разработки операционной системы как таковой.

Системное программирование

Управляемые языки, в частности, Java и Kotlin, лучше всего подходят для разработки приложений под Android. Эти языки проектировались в расчете на удобство использования, портируемость и безопасность. Среда исполнения Android (ART)управляет памятью так, как указал разработчик. В операционной системе Android широко используется Java, что фактически защищает большие участки платформы Android от багов, связанных с памятью. К сожалению, на низких уровнях ОС Android Java и Kotlin бессильны.

На низких уровнях ОС нужны языки для системного программирования, такие как C, C++ и Rust. При проектировании этих языков приоритет отдавался контролируемости и предсказуемости. Они обеспечивают доступ к низкоуровневым ресурсам системы и железу. Они обходятся минимальными ресурсами, прогнозировать их производительность также сравнительно просто.

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

Rust предоставляет гарантии по поводу безопасности памяти, так как использует сочетание проверок во время компиляции, чтобы обеспечить соблюдение времени жизни объектов и владение ими, а также проверки во время исполнения и таким образом гарантировать валидность обращений к памяти. Такая безопасность действительно обеспечивается, а производительность остается не меньшей, чем при работе с C и C++.

Пределы работы в песочнице

Языки C и C++ не дают таких же гарантий безопасности, как Rust, и требуют надежной изоляции. Все процессы Android укладываются в песочницу, и мы придерживаемся правила двух, принимая решение, требуется ли для конкретной функциональности дополнительная изоляция и снижение привилегий. Правило двух формулируется просто: при наличии следующих трех вариантов действий, разработчики вправе выбрать лишь два из них.

В Android это означает, что, если код написан на C/C++ и разбирает потенциально небезопасный ввод, то он должен содержаться в жестко ограниченной песочнице без привилегий. Тогда как следование правилу двух хорошо помогает снижать тяжесть и повышать доступность уязвимостей, связанных с безопасностью, оно сопряжено с некоторыми ограничениями. Работа в песочнице дорогое удовольствие; для ее обеспечения требуются новые процессы, которыесопряжены с дополнительными накладными расходами и провоцируют задержки, связанные с межпроцессной коммуникацией и дополнительным расходом памяти. Работа в песочнице не позволяет полностью исключить уязвимости в коде, а эффективность такой работы снижается при высокой плотности багов, позволяющей злоумышленникам сцеплять вместе множество уязвимостей сразу.

Язык, обеспечивающий безопасность памяти, такой, как Rust, помогает преодолеть эти ограничения двумя способами:

1. Снижает плотность багов в нашем коде, тем самым повышая эффективность применяемой песочницы.

2. Снижает потребность в использовании песочницы, поскольку предоставляет новые возможности, которые более безопасны в работе и одновременно менее требовательны к ресурсам.

Что же насчет всего имеющегося C++?

Разумеется, если мы введем новый язык программирования, это никак не поможет нам с исправлением уже имеющихся багов в имеющемся коде на C/C++.

Вышеприведенный анализ возраста багов, связанных с безопасностью памяти (отсчитывается с момента их появления) позволяет судить, почему команда Android делает акцент на новых разработках, а не на переписывании зрелого кода на C/C++. Большинство багов возникает в новом или недавно измененном коде, причем, возраст около 50% багов составляет менее года.

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

Ограничения находимости багов

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

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

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

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

Предотвращение прежде всего

В Rust модернизируется ряд языковых аспектов, что позволяет улучшить корректность кода:

• Безопасность памяти обеспечивается благодаря сочетанию проверок во время компиляции и во время выполнения.

• Конкурентность данных предотвращает гонку данных. Учитывая, насколько легко при этом становится писать эффективный потокобезопасный код, Rust обрел слоганБезбоязненная Конкурентность.

• Более выразительная система типов помогает предотвратить логические ошибки при программировании (напр., обертки нового типа, варианты перечислений с содержимым).

• Ссылки и переменные по умолчанию являются неизменяемыми что помогает разработчику следовать безопасному принципу наименьших привилегий. Программист помечает ссылку или переменную как изменяемые, только если в самом деле намерен сделать их таковыми. Притом, что в C++ есть const, эта возможность обычно используется нечасто и несогласованно. Напротив, компилятор Rust помогает избегать случайных аннотаций об изменяемости, так как выдает предупреждения об изменяемых значениях, которые никогда не меняются.

• Улучшенная обработка ошибок в стандартных библиотеках потенциально провальные вызовы обертываются в Result, и поэтому компилятор требует от пользователя проверять возможность провала даже для функций, не возвращающих необходимого значения. Это позволяет защититься от таких багов как уязвимостьRage Against the Cage, возникающая из-за необработанной ошибки. Обеспечивая легкое просачивание ошибок при помощи оператора ? и оптимизируя Result с расчетом на низкие издержки, Rust стимулирует пользователей писать все потенциально провальные функции в одном и том же стиле, благодаря чему все они получают ту же защиту.

• Инициализация требует, чтобы все переменные инициализировались перед началом использования. Исторически сложилось, что неинициализированные уязвимости памяти были в Android причиной 3-5% уязвимостей, связанных с безопасностью. В Android 11, чтобы сгладить эту проблему, стала применятьсяавтоматическая инициализация памяти на C/C++. Однако, инициализация в ноль не всегда безопасна, особенно для таких штук, как возвращаемые значения, и в этой области может стать новым источником неправильной обработки ошибок. Rust требует, чтобы любая переменная перед использованием инициализировалась в полноценный член своего типа. Тем самым избегается проблема непреднамеренной инициализации небезопасного значения. Подобно Clang в C/C++, компилятор Rust знает о требовании инициализации и позволяет избежать потенциальных проблем производительности, связанных с двойной инициализацией.

• Более безопасная обработка целых чисел Очистка во избежание включена в отладочных сборках Rust по умолчанию, что стимулирует программистов указывать wrapping_add, если действительно предполагается допустить переполнение при расчетах, или saturating_add если не предполагается. Очистка при переполнении в дальнейшем должна быть включена для всех сборок Android. Кроме того, при всех преобразованиях целочисленных типов применяются явные приведения: разработчик не может сделать случайного приведения в процессе вызова функции при присваивании значения переменной или при попытке выполнять арифметические операции с другими типами.

Что дальше

Введение нового языка на платформу Android серьезное предприятие. Существуют такие связки инструментов и зависимости, которые необходимо поддерживать, тестовая инфраструктура и оснащение, которые потребуется обновить. Также придется дополнительно обучить разработчиков. Это проект не на один год. Следите за обновлениями в блоге Google.

Первое правило хорошего тона в программировании (или одно из первых) гласит: "Не копируй код". Используй функции и наследование.

Если с функциями все понятно, то с наследованием посложнее. Вы, наверное, знаете, что в Rust нет прямого наследования, но есть способы добиться чего-то на него похожего. О них я и расскажу.

impl dyn Trait

Если вы посмотрите на реализацию итератора, то увидите, что у него есть один required метод (то есть тот, который нужно реализовать нам) и provided методы (те, которые реализованы за нас). Что нам это даёт? А то, что если мы напишем свою реализацию какой-либо коллекции, то чтобы реализовать для нее итератор нам нужно всего-навсего имплементировать next(). Все остальные фп-шные штуки вроде map(), filter(), fold() и т.д. будут реализованы автоматически.

Представим, что вы пишите иерархию классов для игры в жанре RPG. Так вот, вместо того, чтобы в каждом новом классе писать один и тот же код, например, получения урона, можно сделать единый интерфейс, который подставит нужный код там, где вы этого попросите:

enum Damage{    Physical(f32),    Magic(f32)}trait Character{  fn get_magic_resistance(&self) -> f32;  fn get_physical_resistance(&self) -> f32;  fn set_hp(&mut self, new_value: f32);  fn get_hp(&self) -> f32;  fn get_type(&self) -> CharacterType;  fn get_dmg(&self) -> Damage;}impl dyn Character {  fn make_hurt(&mut self, dmg: Damage) {    match dmg{      Damage::Physical(dmg) => self.set_hp(self.get_hp() - dmg / self.get_physical_resistance().exp()),      Damage::Magic(dmg) => self.set_hp(self.get_hp() - dmg / self.get_magic_resistance().exp())    }  }}#[derive(Debug, Clone, Copy)]enum CharacterType {    Mage,    Warrior,    Rogue}impl Default for CharacterType {    fn default() -> Self{        CharacterType::Warrior    }}#[derive(Default)]struct Player{    ty: CharacterType,    phys_resist: f32,    mag_resist: f32,    hp: f32,    dmg: f32}impl Player {    pub fn new(ty: CharacterType, hp: f32, dmg: f32) -> Self {        Self{ ty, hp, dmg, .. Default::default() }    }}impl Character for Player{    #[inline]    fn get_magic_resistance(&self) -> f32 {        self.mag_resist    }        #[inline]    fn get_physical_resistance(&self) -> f32{        self.phys_resist    }        #[inline]    fn set_hp(&mut self, new_value: f32){        self.hp = new_value;    }        #[inline]    fn get_hp(&self) -> f32 {        self.hp    }        #[inline]    fn get_type(&self) -> CharacterType {        self.ty    }        fn get_dmg(&self) -> Damage{        match self.ty {            CharacterType::Mage => Damage::Magic(self.dmg),            _ => Damage::Physical(self.dmg)        }    }}struct EnemyWarrior{    ty: CharacterType,    phys_resist: f32,    mag_resist: f32,    hp: f32,    dmg: f32}impl Default for EnemyWarrior {    fn default() -> Self {        Self{            ty: CharacterType::Warrior,            phys_resist: 0.,            mag_resist: 0.,            hp: 10.,            dmg: 1.        }    }}impl Character for EnemyWarrior{    #[inline]    fn get_magic_resistance(&self) -> f32 {        self.mag_resist    }        #[inline]    fn get_physical_resistance(&self) -> f32{        self.phys_resist    }        #[inline]    fn set_hp(&mut self, new_value: f32){        self.hp = new_value;    }        #[inline]    fn get_hp(&self) -> f32 {        self.hp    }        fn get_type(&self) -> CharacterType {        CharacterType::Warrior    }        fn get_dmg(&self) -> Damage{        match self.ty {            CharacterType::Mage => Damage::Magic(self.dmg),            _ => Damage::Physical(self.dmg)        }    }}fn main(){    let mut player = Player::new(CharacterType::Warrior, 10., 1.);    let mut enemy = EnemyWarrior::default();        <dyn Character>::make_hurt(&mut enemy, player.get_dmg());    println!("{}", enemy.get_hp());}

TL;DR сделали 2 структуры и реализовали для них трейт Character, в котором 6 required методов и 1 provided метод.

Но внимательный читатель совершенно справедливо спросит: "Так мы ведь всё равно скопировали код?" Верно, из-за того, что в трейтах нельзя объявлять поля, нам пришлось городить required методы для получения нужных данных. Сейчас-то, конечно, их всего 6, но потом у нас могут добавиться передвижения, анимации, левел-апы и проч. Конечно, целый один метод у нас один на все имплементации, но код-то мы все равно копируем?

Deref<Target=_>

Тут нам на помощь приходит трейт Deref. Честно говоря, не знаю, насколько это хорошая практика использовать его с такой целью, но, например, в image есть такое: ImageBuffer реализует Deref для [P::Subpixel] и, соответственно, имеет все методы массива, которые есть в стандартной библиотеке. Давайте перепишем наш пример под Deref и посмотрим, сколько места нам удалось сэкономить.

use std::ops::Deref;use std::ops::DerefMut;enum Damage{    Physical(f32),    Magic(f32)}#[derive(Default)]struct Character{    ty: CharacterType,    phys_resist: f32,    mag_resist: f32,    hp: f32,    dmg: f32}impl Character {    #[inline]    fn get_magic_resistance(&self) -> f32 {        self.mag_resist    }        #[inline]    fn get_physical_resistance(&self) -> f32{        self.phys_resist    }        #[inline]    fn set_hp(&mut self, new_value: f32){        self.hp = new_value;    }        #[inline]    fn get_hp(&self) -> f32 {        self.hp    }        #[inline]    fn get_type(&self) -> CharacterType {        self.ty    }        fn get_dmg(&self) -> Damage{        match self.ty {            CharacterType::Mage => Damage::Magic(self.dmg),            _ => Damage::Physical(self.dmg)        }    }  fn make_hurt(&mut self, dmg: Damage) {    match dmg{      Damage::Physical(dmg) => self.set_hp(self.get_hp() - dmg / self.get_physical_resistance().exp()),      Damage::Magic(dmg) => self.set_hp(self.get_hp() - dmg / self.get_magic_resistance().exp())    }  }}#[derive(Debug, Clone, Copy)]enum CharacterType {    Mage,    Warrior,    Rogue}impl Default for CharacterType {    fn default() -> Self{        CharacterType::Warrior    }}#[derive(Default)]struct Player(Character);impl Player {    pub fn new(ty: CharacterType, hp: f32, dmg: f32) -> Self {        Self(Character{ ty, hp, dmg, .. Default::default() })    }}impl Deref for Player {    type Target = Character;        #[inline]    fn deref(&self) -> &Self::Target{        &self.0    }}impl DerefMut for Player {    #[inline]    fn deref_mut(&mut self) -> &mut Self::Target{        &mut self.0    }}struct EnemyWarrior(Character);impl Default for EnemyWarrior {    fn default() -> Self {        Self(Character {            ty: CharacterType::Warrior,            phys_resist: 0.,            mag_resist: 0.,            hp: 10.,            dmg: 1.        })    }}impl Deref for EnemyWarrior {    type Target = Character;        #[inline]    fn deref(&self) -> &Self::Target{        &self.0    }}impl DerefMut for EnemyWarrior {    #[inline]    fn deref_mut(&mut self) -> &mut Self::Target{        &mut self.0    }}fn main(){    let mut player = Player::new(CharacterType::Warrior, 10., 1.);    let mut enemy = EnemyWarrior::default();        enemy.make_hurt(player.get_dmg());    println!("{}", enemy.get_hp());}

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

Но у такого подхода тоже есть минус. Если нам нужны другие данные, помимо "родительских", тогда нам придётся создавать дополнительные структуры, чтобы хранить уже свои, независимые от "родительских", данные. Тогда нам придется писать код вроде:

struct Child (Parent, ChildInner);impl Child {  pub fn get_some_field_from_inner(&self) -> &ChildInner::Field {    &self.1.field  }}

И, согласитесь, сигнатура этого метода не очень удобочитаемая. А если у нас будет несколько внутренних структур, то остаётся только пожелать здоровья людям, которые будут это ревьюить и/или поддерживать.

Заключение

В заключение хочу сказать, что в расте не помешало бы явное наследование структур. Всё-таки, как ни крути, в других языках оно позволяет писать с одной стороны хорошо читаемый, с другой стороны лаконичный код (если, конечно, это не множественное наследование). Подходы в Rust, конечно, позволяют экономить какое-то количество места, но хотелось бы чего-то более явного. Да и интерфейсы Deref, DerefMut вообще не предназначены для того, для чего мы их использовали в данной статье. Они, как следует из названия, нужны чтобы разыменовывать умные указатели. А если вы объединяете несколько структур данных, то вам придется использовать синтаксис self.1, который далеко не очевидный. В общем, как и всегда, есть и плюсы и минусы.

Вот, собственно, и все, что я хотел сказать на эту тему. Может, я что-то упустил? Напишите в комментариях, если вас тоже волнует эта тема, хочется знать, что не мне одному не хватает наследования в Rust.

Начало

Порой, простое и красивое решение лучше правильного и выдержанного. Возможно, именно так бы и было, если в жизни всё происходило как в учебниках. На практике же, нужно пройти долгий путь, чтобы создать задуманное.

Отступая от лирики, в данной статье я хочу рассказать заинтересованному читателю про шифрование по ГОСТ, а именно алгоритм Кузнечик, и про то, что стоит обратить внимание на новые и перспективные средства язык Rust.

Хватит отступлений, предлагаю начать!

Что будет в данной статье

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

Для тех, кто уже устал читать, даю ссылочку на код, возможно кому-то пригодится.

Rust или не Rust?

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

Я считаю, для данной задачи Rust удовлетворяет требованиям производительности и использования памяти, а также что, он более перспективный и удобный в использовании, чем тот же C++. Это лишь моё субъективное мнение и никого не прошу придерживаться его. К тому же, язык программирования это всего лишь инструмент со своими особенностями, преимуществами и недостатками. Если вы считаете, что это не так рад буду услышать вашу позицию по данному вопросу.

Реализация

Перед тем, как вдаваться в подробности кода было бы не плохо продемонстрировать HelloWorld. Для начала подключим библиотеку kuznechik:

Cargo.toml:

[dependencies]kuznechik = "0.2.0"

Теперь зашифруем и расшифруем строку "Hello World!":

main.rs:

fn hello_world() {    // Инициализация    let gamma = vec![0x12, 0x34, 0x56, 0x78, 0x90, 0xab, 0xce, 0xf0, 0xa1, 0xb2, 0xc3, 0xd4, 0xe5, 0xf0, 0x01, 0x12,                     0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89, 0x90, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19];    let kuz = Kuznechik::new("Кузнечик на Rust").unwrap();    let mut alg = AlgOfb::new(&kuz);    alg.gamma = gamma.clone();        let data = String::from("Hello World!").into_bytes();    // Шифрование    let enc_data = alg.encrypt(data.clone());    println!("Encrypted data:\n{:?}", &enc_data);    // Расшифрование    alg.gamma = gamma;    let dec_data = alg.decrypt(enc_data);    println!(        "Decrypted data:\n{}",        String::from_utf8(dec_data.clone()).unwrap()    );    assert_eq!(dec_data, data);}

В коде, представленном выше для создания объекта Kuznechik используется пароль в виде строки. Функция Kuznechik::new() принимает строку и хеширует её по алгоритму Sha3-256 для получения мастер ключа. Также вы можете напрямую задать мастер ключ, для этого можно воспользоваться функцией Kuznechik::new_with_master_key(). Данная функция принимает массив длиной 256 бит (тип [u8; 32]).

Функции alg.encrypt() и alg.decrypt() принимают на вход и возвращают вектор байтов Vec<u8>. Данные функции принимают во владение входные вектора. В некоторых режимах длина выходного вектора больше входного, связано это с процедурой дополнения.

Обзор библиотеки

Архитектура

Архитектура библиотеки устроена так, что неизменяемые данные ключи, хранятся в структуре Kuznechik, а изменяемые и присущи конкретному режиму шифрования данные в структурах, начинающихся с префикса Alg- (в данном примере - AlgOfb). Это касается и функционального кода. Всё это позволяет создать один экземпляр Kuznechik (единожды развернуть ключи) и использовать разные режимы.

Режимы шифрования

Алгоритм Кузнечик может работать в шести режимах (типы AlgEcb, AlgCtr, AlgOfb, AlgCbc, AlgCfb, AlgMac). В приведённом выше примере представлен режим гаммирования с обратной связью по выходу (OFB). В данном режиме для работы алгоритма требуется гамма, значение которой задаётся через переменную alg.gamma. Необходимо учесть, что данная переменная изменяется в процессе шифрования и для успешного расшифрования требуется установить начальное значение гаммы.

Базовый алгоритм

В этом разделе я покажу, как может выглядеть реализация на Rust. Более подробно вы можете посмотреть в исходниках на GitHub.

Базовый алгоритм шифрования выглядит намного проще чем его описание в стандарте:

pub fn encrypt_block(data: &mut Block128, keys: &[Block128; 10]) {    for i in 0..9 {        tfm_lsx(data, &keys[i]);    }    tfm_x(data, &keys[9]);}

Здесь производится девять итераций LSX-преобразования и затем ещё одну итерацию X-преобразования. Напомню длина блока 128 бит или 16 байт. Тип Block128 именно такого размера, элементы которого имеют тип u8.

Далее LSX-преобразование. Оно состоит из поочерёдного вызова X, S, и L преобразований.

fn tfm_lsx(data: &mut Block128, key: &Block128) {    tfm_x(data, key);    tfm_s(data);    tfm_l(data);}

В свою очередь X-преобразование делает сложение по модулю 2 (проще говоря - XOR) блока данных с ключом:

fn tfm_x(data: &mut Block128, key: &Block128) {    for i in 0..16 {        data[i] ^= key[i];    }}

В S-преобразовании в данные вносится нелинейность для чего к данным применяется подстановка (пи).

fn tfm_s(data: &mut Block128) {    for i in 0..16 {        data[i] = K_PI[data[i] as usize];    }}

L-преобразование производит 16 раз R-преобразование на данными.

fn tfm_l(data: &mut Block128) {    for _ in 0..16 {        tfm_r(data);    }}

И наконец R-преобразование:

fn tfm_r(data: &mut Block128) {    let temp = trf_linear(data);    data.rotate_right(1);    data[0] = temp;}

Данное преобразование лучше всего показать на рисунке. F линейное преобразование, которое соотносит 16 байтам однобайтовый результат, согласно выражению ниже.

Линейное преобразование:

Чтобы не вычислять значение линейного преобразования на каждой итерации L-преобразования, можно вычислить, своего рода, таблицу умножения. Таблица содержит 7 строк и 256 столбцов, что соответствует произведениям в поле Галуа коэффициентов на значения входных данных (произведения входных данных на коэффициент равный 1 нет смысла держать в таблице, т.к. результат равен входным данным).

Вычисление линейного преобразования по такой таблице умножения занимает O(1) времени и требует O(1) памяти, а точнее 7 * 256 = 1792 байта, что не так много для современного компьютера.

Собственно реализация:

fn trf_linear(data: &Block128) -> u8 {  // indexes:  0,  1,   2,   3,   4,   5,   6    // values:  16, 32, 133, 148, 192, 194, 251    let mut res = 0u8;    res ^= MULT_TABLE[3][data[0] as usize];    res ^= MULT_TABLE[1][data[1] as usize];    res ^= MULT_TABLE[2][data[2] as usize];    res ^= MULT_TABLE[0][data[3] as usize];    res ^= MULT_TABLE[5][data[4] as usize];    res ^= MULT_TABLE[4][data[5] as usize];    res ^= data[6];    res ^= MULT_TABLE[6][data[7] as usize];    res ^= data[8];    res ^= MULT_TABLE[4][data[9] as usize];    res ^= MULT_TABLE[5][data[10] as usize];    res ^= MULT_TABLE[0][data[11] as usize];    res ^= MULT_TABLE[2][data[12] as usize];    res ^= MULT_TABLE[1][data[13] as usize];    res ^= MULT_TABLE[3][data[14] as usize];    res ^= data[15];    res}

Что касается сложения в линейном преобразовании, то это всего лишь XOR. Таблицу умножения вы можете посмотреть в исходниках.

На этом всё, показывать обратные преобразования и режимы работы здесь будет уже лишним, и так уже кода получилось многовато, если что вы знаете где искать. Да, благодарю вас если вы дочитали до этого момента, всё же статья уже затянулась.

Про велосипед

Многие, наверно спросят, зачем писать то, что уже написано. Можно же использовать готовое от дяди Васи. В ответ я перечислю основные причины, которые подтолкнули меня на создание такого проекта.

• Лицензирование ПО.

• Качество ПО (безопасность, производительность, требования к памяти и тд.).

• Интерфейс взаимодействия.

• Зависимости.

• Ну и конечно же опыт, который получаешь в процессе разработки.

Продолжение следует

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

На этом пока всё. Надеюсь, что данная статья поможет кому-нибудь в понимании алгоритма Кузнечик и языка Rust. Спасибо за внимание.

Отдельное спасибо Chris F за фотографии кузнечика.

Недавно я создала небольшой инструмент под названием dnspeep, который позволяет понять, какие DNS-запросы отправляет ваш компьютер и какие ответы он получает. Всего мой код занял 250 строк на Rust. В этой статье я расскажу о коде, объясню, для чего он нужен, почему в нём возникла необходимость, а также расскажу о некоторых проблемах, с которыми я столкнулась при его написании. И, конечно, вы сами сможете попробовать код в действии.

Что нужно для начала работы с кодом

Чтобы было удобнее работать с кодом, я подготовила несколько бинарных файлов.

Команды для Linux (x86):

wget https://github.com/jvns/dnspeep/releases/download/v0.1.0/dnspeep-linux.tar.gztar -xf dnspeep-linux.tar.gzsudo ./dnspeep

Команды для Mac:

wget https://github.com/jvns/dnspeep/releases/download/v0.1.0/dnspeep-macos.tar.gztar -xf dnspeep-macos.tar.gzsudo ./dnspeep

Коду необходим доступ ко всем отправляемым компьютером пакетам DNS, поэтому его необходимо запускать от имени root. По этой же причине утилиту tcpdump также нужно запускать от имени root: код использует libpcap ту же библиотеку, что и tcpdump. Если вам по какой-либо причине не захочется загружать бинарные файлы и запускать их от имени root, вы можете воспользоваться моим исходным кодом и создать на его основе собственный.

Что получается в результате

Каждая строка представляет собой DNS-запрос и соответствующий запросу ответ.

$ sudo dnspeepquery   name                 server IP      responseA       firefox.com          192.168.1.1    A: 44.235.246.155, A: 44.236.72.93, A: 44.236.48.31AAAA    firefox.com          192.168.1.1    NOERRORA       bolt.dropbox.com     192.168.1.1    CNAME: bolt.v.dropbox.com, A: 162.125.19.131

Эти запросы отражают мои визиты на сайт neopets.com в браузере, а запрос bolt.dropbox.com возник потому, что у меня запущен агент Dropbox, и, как я полагаю, время от времени он заходит на свой сайт для синхронизации.

Зачем создавать ещё один инструмент DNS?

Я считаю, что в таком инструменте есть смысл, так как с его помощью можно лучше представить, как работает DNS без этого инструмента довольно сложно понять, как ведёт себя DNS на компьютере.

Ваш браузер (и другие компьютерные программы) постоянно отправляет DNS-запросы. Если знать, какие запросы отправляет компьютер и какие ответы он получает, можно получить более реальную картину "жизни" компьютера.

Написанный мною код я также использую как инструмент отладки. На вопросы типа: "А не связана ли моя проблема с DNS?" ответить иногда бывает довольно сложно. Пользователи, не зная всей информации, зачастую, чтобы найти проблему, используют метод проб и ошибок или просто строят догадки, хотя, казалось бы, стоит просто проанализировать ответы на получаемые компьютером DNS-запросы, и проблема будет решена.

Можно увидеть, какое программное обеспечение "тайно" выходит в Интернет

Мне нравится в этом инструменте, что он даёт представление о том, какие программы моего компьютера пользуются Интернетом! Например, я обнаружила, что какая-то утилита на моём компьютере время от времени по непонятной причине отправляет запросы на ping.manjaro.org, вероятно, чтобы проверить, подключён ли мой компьютер к Интернету.

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

Если вы раньше не работали с tcpdump, поначалу может быть непонятно, что делает эта утилита

Рассказывая людям об отправляемых с компьютера DNS-запросах, я почти всегда хочу добавить: "Всю информацию можно получить через tcpdump!" Что делает утилита tcpdump? Она осуществляет разбор пакетов DNS! Например, вот как выглядит DNS-запрос incoming.telemetry.mozilla.org.:

11:36:38.973512 wlp3s0 Out IP 192.168.1.181.42281 > 192.168.1.1.53: 56271+ A? incoming.telemetry.mozilla.org. (48)11:36:38.996060 wlp3s0 In  IP 192.168.1.1.53 > 192.168.1.181.42281: 56271 3/0/0 CNAME telemetry-incoming.r53-2.services.mozilla.com., CNAME prod.data-ingestion.prod.dataops.mozgcp.net., A 35.244.247.133 (180)

Сначала эта информация может показаться "тёмным лесом", но её при некоторых навыках можно научиться читать. Давайте для примера разберём такой запрос:

192.168.1.181.42281 > 192.168.1.1.53: 56271+ A? incoming.telemetry.mozilla.org. (48)

• A? означает DNS-запрос типа A;

• incoming.telemetry.mozilla.org. это имя объекта, к которому осуществляется запрос;

• 56271 это идентификатор DNS-запроса;

• 192.168.1.181.42281 исходный IP/порт;

• 192.168.1.1.53 IP/порт назначения;

• (48) длина DNS-пакета.

Ответ выглядит следующим образом:

56271 3/0/0 CNAME telemetry-incoming.r53-2.services.mozilla.com., CNAME prod.data-ingestion.prod.dataops.mozgcp.net., A 35.244.247.133 (180)

• 3/0/0 количество записей в ответе: 3 ответа, 0 полномочий, 0 дополнительно. Исходя из моего опыта, tcpdump выводит только количество ответов на запрос.

• CNAME telemetry-incoming.r53-2.services.mozilla.com, CNAME prod.data-ingestion.prod.dataops.mozgcp.net. и A 35.244.247.133 это те самые три ответа

• 56271 идентификатор ответов, соответствующий идентификатору запроса. По этому идентификатору можно понять, что это ответ на запрос из предыдущей строки.

С таким форматом, конечно, работать довольно сложно, ведь человеку нужно просто посмотреть на трафик DNS, к чему все эти нагромождения? И вот ему приходится вручную сопоставлять запросы и ответы, к тому же не всегда находящиеся на соседних строках. Здесь в дело вступают компьютерные возможности!

Я решила написать небольшую программку dnspeep, которая будет сама выполнять такое сопоставление, а также удалять определённую (на мой взгляд, лишнюю) информацию.

Проблемы, с которыми я столкнулась при написании кода

При написании кода я столкнулась с рядом проблем.

• Мне пришлось несколько изменить библиотеку pcap, чтобы заставить её правильно работать с Tokio на Mac OS вот эти изменения. Это была одна из тех ошибок, на поиск которой ушло много часов, а всё исправление уложилось в одну строку.

• Разные дистрибутивы Linux, по всей видимости, используют разные версии libpcap.so, поэтому мне не удалось воспользоваться непосредственно бинарным файлом, динамически компонующим libpcap (у других пользователей возникала такая же проблема, например здесь). Поэтому компилировать библиотеки libpcap в инструмент на Linux мне пришлось статически. Я до сих пор не понимаю, как такое правильно организовать на Rust, но я добилась, чего хотела, и всё заработало я скопировала файл libpcap.a в каталог target/release/deps, а затем просто запустила cargo build.

• Используемая мною библиотека dns_parser поддерживает не все типы DNS-запросов, а только некоторые самые распространённые. Возможно, для разбора DNS-пакетов можно было использовать другую библиотеку, но я не нашла подходящей.

• Поскольку интерфейс библиотеки pcap выдает набор "голых" байтов (в том числе для данных Ethernet-фреймов), мне пришлось написать код, который определял, сколько байтов нужно отсечь от начала строки, чтобы получить IP-заголовок пакета. Но я уверена, что в моей задаче ещё остались "подводные камни".

Кстати, вы даже не представляете, каких сложностей мне стоило подобрать название для своей утилиты ведь инструментов для работы с DNS великое множество, и у каждого своё название (dnsspy! dnssnoop! dnssniff! dnswatch!) Сначала я хотела включить в название слово spy (шпион) или его синонимы, а затем остановилась на показавшемся мне забавным названии, которое о чудо! ещё никто не занял для собственного DNS-инструмента.

У моей утилиты есть один недостаток: она не сообщает, какой именно процесс отправил DNS-запрос, но выход есть используйте инструмент dnssnoop. Этот инструмент работает с данными eBPF. Судя по описанию, он должен работать нормально, но я его ещё не пробовала.

В моём коде наверняка ещё много ошибок

Мне удалось его протестировать только на Linux и Mac, и я уже знаю как минимум об одной ошибке (из-за того, что поддерживаются не все DNS-запросы). Если найдёте ошибку, пожалуйста, сообщите мне!

Сами по себе ошибки не опасны интерфейс libpcap доступен только для чтения, самое худшее, что может случиться, он получит какие-то непонятные данные и выдаст ошибку или аварийно завершит работу.

Мне нравится составлять небольшие учебные материалы

В последнее время я получаю огромное удовольствие от написания небольших учебных материалов по DNS. Вот ссылки на мои предыдущие статьи:

• Простой способ составления DNS-запросов;

• Рассказывается, что происходит внутри компьютера при отправке DNS-запроса;

• Ссылка на dnspeep.

Ранее в своих постах я просто объясняла, как работают существующие инструменты (например dig или tcpdump), а если и писала собственные инструменты, то довольно редко. Но сейчас для меня очевидно, что выходные данные этих инструментов довольно туманны, их сложно понять, поэтому мне захотелось создать более дружественные варианты просмотра такой информации, чтобы не только гуру tcpdump, но любые другие пользователи могли понять, какие DNS-запросы отправляет их компьютер.

А если вы хотите не только понимать, что происходит с запросами и ответами DNS на вашем компьютере, но и писать собственные протоколы для своих приложений, обратите внимание на профессии C++ разработчик или Java-разработчик, позволяющие с нуля освоить эти языки или прокачать своё владение ими. Приходите опытные менторы и эксперты своего дела с удовольствием поделяться с вами своими знаниями.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Как всё началось

Сидел я на третьем курсе колледжа и ничего не делал, получая пятерки. Материал я усваивал быстро (спасибо форумам и хабру), но чего-то мне не хватало и тогда я взялся за изучение операционных систем, надеясь что-то сделать к диплому. Время шло, практика и кончился третий курс.

Переходя в следующий курс я начал активно изучать всё что касалось ОСи, но толком никуда не продвинулся. Тогда и родилась у меня идея создать свой ЯП.

Времени было мало, а делать было что-то нужно и я в свободное от удалёнки (с серой ЗП) что-то писал.

Язык я решил назвать The Gorge.

Часть первая. Как работает язык и где его найти

Было принято решение разместить язык на платформе гитхаб и создать новый профиль.
На тот момент я имел в распоряжении старый подаренный мне акк, но в последствии всё-таки создал свой и сейчас его можно найти так: (просто допишите сайт)/pcPowerJG/natural-network.

В папке src в файле lib.rs мы можем увидеть чудо, язык написан почти полностью на раст (почему почти? к сожалению в далёкие времена 2019 года раст не давал открыть файл на моей любимой манжаре и пришлось открывать его через Си).

Ну так вот, первое что мне было необходимо сделать - создать словарь используемых ключевых слов.

words.push("object".to_string());//1 // используется для создания объекта, который хранит значения в памятиwords.push("if".to_string());//2// оператор условия, нужен для сравнения ДВУХ параметровwords.push("exit_()".to_string());//3//выход из приложенияwords.push("func".to_string());     //4//инициализация функции words.push("print".to_string());//5 // вывод на консольwords.push("remove".to_string());//6 //удалениеwords.push("array".to_string());//7 // создание массиваwords.push("struct".to_string()); //8 // создание структурыwords.push("end".to_string());//9//end operationwords.push("end_func".to_string()); // 10 // конец функцииwords.push("return".to_string()); //  11words.push("!eq".to_string());//  12words.push(">".to_string());  //  13words.push("<".to_string());  //  14words.push("loop".to_string());// 15words.push("end_loop".to_string());// 16words.push("_".to_string()); // 17 // просто в качестве НЕ ключевого словаwords.push("break".to_string()); // 18words.push("true".to_string()); // 19words.push("false".to_string()); // 20

Как мы видим у слов есть определённая нумерация (и не с нуля. это важно).

Следующая главная функция это функция старт.

pub fn start_(&mut self, text: String) -> u8

В ней происходит вся магия обработки текста и перевод его в действие. Сразу оговорюсь, мы пишем интерпретатор.

Так как мы пишем интерпретатор, нам необходимо как-то это обрабатывать, для этого необходимо создавать карту действий, но мы ограничимся простым массивом.

Так же создадим переменные для временного хранения информации (тело цикла к примеру или математическое выражение, имя функции и т.д.).

Привожу код.

let mut temp_values: String = String::new();//ВРЕМЕННЕ ПЕРЕМЕННЕlet mut temp_name: String = String::new();        //...let mut temp_buffer: String = String::new();//...let mut func_text: String = String::new();let mut last_op: [usize; 3] = [0; 3]; // храним три последних действия// ----------------------------------------------let mut if_count: usize = 0;let mut if_result: bool = true; // ответ на условиеlet mut struct_flag: bool = false; // это структура или условиеlet mut function_inactive_flag: bool = false; // если функция не активнаlet mut loop_flag: bool = false; // попали на циклlet mut index_loop: usize = 0; // количество циклов (для цикла в цикле)

Так же смотря код можно заметить много флагов, они нужны как-раз таки для нормального функционирования.

Всего наш код делиться на три блока

if ch == ' ' || ch == '\t' {  //...................} else if ch == '\n' {  //...................} else if ch == '=' {  //...................}} else {  temp_values.push(ch);}

В первом мы выполняем действия при разделении кода (то есть сразу смотрим что за ключевое слово или переменная и записываем в карту действий). Второй выполняем после символа окончания строки, тут мы выполняем действия. И третий выполняется при присваивании.
Блок else нужен только для записи переменной.

Дальше ныряем по коду, предлагаю посмотреть каждый блок отдельно.

if function_inactive_flag {  // ...}if loop_flag {  // ...}match temp_values.trim() {  // ...}

Мы видим в блоке ещё три блока. Первый блок связан с функциями, в нём происходит запись их в переменную (мы храним имя функции как переменную).

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

Всё остальное же идёт согласно законам логики построения программы.

К примеру: a = b + c
Преобразуется в: last_op[0] = 1 last_op[1] = 17
И выполниться: в функции math_work .

Математика

Функция преобразования переменных в значения:

fn math_work(&self, text: String) -> String {  let text: String = Words::trim(text.clone());  let mut result_string: String = String::new();  let mut temp_string: String = String::new();  for ch in text.chars() {    match ch {      '+' | '-' | '/' | '*' | '(' | ')' | '&' | '|' | '!' | '=' | '<' | '>' => {        if Words::is_digit(temp_string.clone()) {          result_string += temp_string.clone().as_str();        } else {          result_string += self.search_var(temp_string).0.clone().as_str();        }        result_string.push(ch.clone());        temp_string = String::new();      },      _ => {        temp_string.push(ch.clone());      },    }  }   let (value, type_, _temp) = self.search_var(temp_string.clone());  if _temp {    result_string += value.as_str();  } else {    result_string += temp_string.clone().as_str();  } result_string}

Всё достаточно просто, если символ не является буквой (или другим символом используемым в именах переменных) - сразу пишем его, если является ищем конец переменной (обычно между переменными есть два других спецсимвола, либо символ конца строки) и заменяем её имя значением.

Передаём всё в следующую функцию:

fn eval(str_: Vec<char>) -> f32 {  let mut i: usize = 0;  Words::expr(str_, &mut i)}

fn eval(str_: Vec<char>) -> f32 {  let mut i: usize = 0;  Words::expr(str_, &mut i)}fn plus_one(u: &mut usize) {  *u += 1;}fn number(ch_: Vec<char>, idx: &mut usize) -> f32 {  let mut result: f32 = 0.0;  //float result = 0.0;  let mut div: f32 = 10.0;  let mut sign: f32 = 1.0;  if ch_[*idx] == '-'{    sign = -1.0;    *idx += 1;  }  while *idx < ch_.len() &&  match ch_[*idx] {    '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => { true },    _ => { false }  }  {    result = result * 10.0 + (f32::from_str(&ch_[*idx].to_string()).expect("не удалось форматировать строку"));    *idx += 1;  }  if *idx < ch_.len() && (ch_[*idx] == '.'){    *idx += 1;            while *idx < ch_.len() &&    match ch_[*idx] {      '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => { true },      _ => { false }    }     {      result = result + (f32::from_str(&ch_[*idx].to_string()).expect("не удалось форматировать строку")) / div;      div *= 10.0;      *idx += 1;    }  }  sign * result}fn expr(ch_: Vec<char>, idx: &mut usize) -> f32 {  let mut result: f32 = Words::term(ch_.clone(), idx);      while *idx < ch_.len() && (ch_[*idx] == '+' || ch_[*idx] == '-') {    match ch_[*idx] {      '+' => {        *idx += 1;        result += Words::term(ch_.clone(), idx);      },      '-' => {        *idx += 1;            result -= Words::term(ch_.clone(), idx);      },      _ => {},    }   } result}fn term(ch_: Vec<char>, idx: &mut usize) -> f32 {  let mut result: f32 = Words::factor(ch_.clone(), idx);  let mut div: f32 = 0.0;  while *idx < ch_.len() && (ch_[*idx] == '*' || ch_[*idx] == '/') {    match ch_[*idx] {      '*' => {        *idx += 1;        result *= Words::factor(ch_.clone(), idx);      },      '/' => {        *idx += 1;            div = Words::factor(ch_.clone(), idx);            if (div != 0.0) {          result /= div;        } else {          panic!("Division by zero!\n");                            }      },      _ => {},    }  } result}fn factor(ch_: Vec<char>, idx: &mut usize) -> f32 {  let mut result: f32 = 0.0;  let mut sign: f32 = 1.0;  if (ch_[*idx] == '-') {    sign = -1.0;    *idx += 1;  }  if (ch_[*idx] == '(') {    *idx += 1;    result = Words::expr(ch_.clone(), idx);    if (ch_[*idx] != ')') {      panic!("Brackets unbalanced!\n");    }    *idx += 1;  } else { result = Words::number(ch_, idx); }  sign * result}

Переменные

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

Все переменные занимают место сразу в двух массивах, массив имён и типов:

object_buffer: Vec<(String, usize)>

Массив значений:

value_buffer: Vec<String>

Для добавления новой переменной используется функция add_vars:

fn add_vars(&mut self, vars_name: String, mut vars_value: String, vars_type: usize) {  //object_buffer: Vec<(String, usize)>  //value_buffer: Vec<String>  if vars_value.clone().split('\"').collect::<Vec<&str>>().len() > 1 {    vars_value = vars_value.split('\"').collect::<Vec<&str>>()[1].to_string();  } else {    vars_value = vars_value.clone().trim().to_string();  }  self.object_buffer.push((vars_name, vars_type));  self.value_buffer.push(vars_value);}

В ней всего одна проверка, есть ли кавычки (что в кавычках мы считаем текстом и не отрезаем пробелы).

Для удаления переменной:

fn remove_vars(&mut self, vars_name: String) {  for i in 0..self.object_buffer.len() {    if self.object_buffer[i].0.clone() == vars_name {      self.object_buffer.remove(i);      self.value_buffer.remove(i);      return;    }  }}

Запись значения и поиск:

fn set_value(&mut self, vars_name: String, mut vars_value: String) {  for i in 0..self.object_buffer.len() {    if self.object_buffer[i].0 == vars_name {      if vars_value.clone().split('\"').collect::<Vec<&str>>().len() > 1 {        vars_value = vars_value.split('\"').collect::<Vec<&str>>()[1].to_string();      } else {        vars_value = vars_value.clone().trim().to_string();      }      self.value_buffer[i] = vars_value.clone();      return;    }  }}pub fn search_var(&self, vars_name: String) -> (String, usize, bool) {  for i in 0..self.object_buffer.len() {    if self.object_buffer[i].0 == vars_name {      let value: String = self.value_buffer[i].clone();      let type_: usize = self.object_buffer[i].1.clone();      return (value, type_, true);     }  }  (String::new(), 0, false)}

Так же планируется импортировать из старой версии языка поддержку внешних библиотек.

import("/lib.so")extern_func("lib.so", func_name)  extern_func("lib.so", func_name, arg1, arg2)close_import("lib.so")

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

Что нужно исправить и добавить?

1. Исправить функцию обработки условий (не заходите туда, я серьезно);

2. Зачем нам всё хранить в тексте? Исправить на байты;

3. Импортировать поддержу сишных библиотек из старой версии языка

Спасибо за внимание.

В предыдущей статье я описал векторные языки и их ключевые отличия от обычных языков. На коротких примерах я постарался показать, как эти особенности позволяют реализовывать алгоритмы необычным образом, кратко и с высоким уровнем абстракции. В силу своей векторной природы такие языки идеально присоблены для обработки больших данных, и в качестве доказательства в этой статье я полностью реализую на векторном языке простой SQL интерпретатор. А чтобы продемонстрировать, что векторный подход можно использовать на любом языке, я реализую тот же самый интерпретатор на Rust. Преимущества векторного подхода столь велики, что даже интерпретатор в интерпретаторе сможет обработать select с группировкой из таблицы в 100 миллионов строк за 20 с небольшим секунд.

Общий план.

Конечная цель - реализовать интепретатор, способный выполнять выражения типа:

select * from (select sym,size,count(*),avg(price) into r  from bt where price>10.0 and sym='fb'  group by sym,size)  as t1 join ref on t1.sym=ref.sym, t1.size = ref.size

Т.е. он должен поддерживать основные функции типа сложения и сравнения, позволять where и group by выражения, а также - inner join по нескольким колонкам.

В качестве векторного языка я возьму Q, так как его специализация - базы данных.

Интерпретатор будет состоять из лексера, парсера и собственно интерпретатора. Для экономии места я буду приводить только ключевые места, а весь код можно найти здесь. Так же для краткости я реализую лишь часть функциональности, но так, чтобы все важное было на месте: join, where, group by, 3 типа данных, агрегирующие функции и т.п.

На примере лексера вы сможете познакомиться, пожалуй, с одним из самых красивых приемов программирования, который встречается в векторных языках, - использование данных как функций.

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

Наконец, сам интерпретатор. На Q он имеет весьма скромные размеры - строк 25. На Rust, конечно, гораздо больше, но написать его проще, чем может показаться. Нужно просто по шагам повторять все операции Q, адаптируя их к специфике Rust.

Это моя первая программа на Rust и сразу хочу сказать, что слухи о его сложности сильно преувеличены. Если писать в функциональном стиле (read only), то проблем нет никаких. После того, как Rust несколько раз забраковал мои идеи, я понял, чего он хочет и уже не сталкивался с необходимостью все переделывать из-за контроллера ссылок, а явные времена жизни понадобились только один раз и по делу. Зато взамен мы получаем программу, которую можно распараллелить по щелчку пальцев. Что мы и сделаем, чтобы добиться просто феноменальной производительности для столь примитивной программы.

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

Лексер

Векторные языки идеальны для написания лексеров. Пусть у нас есть функция fsa, которая принимает на вход текущее состояние лексера и входной символ и возвращает новое состояние:

fsa[state;char] -> state

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

Т.е. есть следующие этапы:

• Кодирование. Входные символы отображаются в группы (my.var -> aa.aaa, 12.01 -> 00.00, "str 1" -> "sss 1" и т.д.).

• Трансформация. Закодированные символы пропускаются через fsa (aa.aaa -> aAAAAA, 00.00 -> 0IFFF, "sss 1" -> "SSSSSR).

• Разбиваем начальную строку на части по начальным состояниям (a, 0, " и т.д.). Для удобства все не начальные состояния обозначены большими буквами.

Все три этапа - это векторные операции, поэтому на Q эта идея реализуется одной строкой (все состояния закодированы так, что начальные меньше limit):

(where fsa\[start;input]<limit)cut input

Это в сущности весь лексер. Правда еще необходимо определить fsa. В подавляющем большинстве случаев в качестве fsa можно взять матрицу - таблицу переходов конечного автомата. Простой автомат можно задать и руками, но можно реализовать небольшой DSL. Отображение в группы можно организовать через небольшой массив (ограничимся ASCII символами для простоты):

cgrp: ("\t \r\n";"0..9";"a..zA..Z"),"\\\"=<>.'";c2grp: 128#0; // массив [0;128]// Q позволяет присваивать значения по индексу любой формы.// В данном случае массиву массивов. В Rust необходимы два явных цикла:// cgrp.iter().enumerate().for_each(|(i,&s)| s.iter()//   .for_each(|&s| c2grp[s as usize] = i + 1));c2grp[`int$cgrp]: 1+til count cgrp;

Для краткости я не привожу все цифры и буквы. Нас интересуют пробельные символы, цифры, буквы, а также несколько специальных символов. Мы закодируем эти группы числами 1, 2 и т.д., все остальные символы поместим в группу 0. Чтобы закодировать входную строку, достаточно взять индекс в массиве c2grp:

c2grp `int$string

Автомат задается правилами (текущее состояние(я);группа(ы) символов) -> новое состояние. Для обозначения групп и начальных состояний токенов удобно использовать первые символы соответствующих групп (для группы 0..9 - 0, например). Для обозначения промежуточных состояний - большие буквы. Например, правило для имен можно записать так:

aA А a0.

т.е. если автомат находится в состояниях "a" (начало имени) или "A" (внутри имени), и на вход поступают символы из групп [a,0,.], то автомат остается в состоянии "A". В начальное состояние "a" автомат попадет автоматически, когда встретит букву (это правило действует по умолчанию). После этого, если дальше он встретит букву, цифру или точку, то перейдет во внутреннее состояние "A" и будет там оставаться до тех пор, пока не встретит какой-то другой символ. Я запишу все правила без лишних комментариев (Rust):

let rules: [&[u8];21] =  [b"aA A a0.",                         // имена   b"0I I 0",b"0I F .",b"F F 0",        // int/float   b"= E =",b"> E =",b"< E =",b"< E >", // <>, >= и т.п.   b"\" S *",b"S S *",b"\"S R \"",      // "str"   b"' U *",b"U U *",b"'U V '",         // 'str'   b"\tW W \t"];                        // пробельные символы

Числа и строки заданы в упрощенном формате. "*" в качестве входного символа имеет специальное значение - все возможные символы. Большие буквы - это состояния внутри токенов. Такая договоренность дает нам возможность легко определить начало токена - это все состояния, которые не большие буквы.

Матрица fsa из этих правил генерируется элементарно. Схематично это выглядит так:

fsa[*;y] = y (по умолчанию для всех состояний)"aA A a0." -> "aA","A","a0."; fsa[enc["aA"];enc["a0."]] = enc["A"]...

Необходимо закодировать символы с помощью вектора states:

states: distinct " ",(first each cgrp),raze fsa[;1];limit: 2+count cgrp;enc:states?; // в Q encode - это поиск индекса элемента в векторе

Вперед поместим все начальные состояния (пробел для учета группы 0), чтобы можно было легко определить limit.

Код генерации fsa я опускаю - он следует схеме выше.

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

let s2n = move |v| ["ID","NUM","STR","STR","WS","OTHER"][find1(&stn,&v)];move |s| {    if s.len()==0 {return Vec::<Token>::new()};    let mut sti = 0usize;    let st: Vec<usize> = s.as_bytes().iter().map(|b| { // st:fsa\[0;c2grp x]        sti = fsa[sti][c2grp[std::cmp::min(*b as usize,127)]];        sti}).collect();    let mut ix: Vec<usize> = st.iter().enumerate() // ix:where st<sta        .filter_map(|(i,v)| if *v<sta {Some(i)} else {None}).collect();    ix.push(st.len());    (0..ix.len()-1).into_iter()        .filter_map(|i|            match s2n(st[ix[i]]) {                 "WS" => None,                  kind => Some(Token{ str:&s[ix[i]..ix[i+1]], kind})             }).collect()

На Q получится значительно более кратко:

s2n:(states?"a0\"'\t")!("ID";"NUM";"STR";"STR";"WS");lex:{  i:where (st:fsa\[0;c2grp x])<limit;  {x[;where not "WS"~/: x 0]} (s2n st i;i cut x)};

Если мы запустим лексер, то получим:

lex "10 + a0" -> (("NUM";"";"ID");("10";"+";"a0"))

Интерпретатор

Интерпретатор можно разделить на две части - выполнение выражений и выполнение select. Первая часть тривиальна на Q, но требует большого количества кода на Rust. Я приведу основные структуры данных, чтобы было понятно, как в целом работает интерпретатор. В основе лежит enum Val:

type RVal=Arc<Val>;enum Val {       I(i64),    D(f64),    II(Vec<i64>),    DD(Vec<f64>),    S(Arc<String>),    SS(Vec<Arc<String>>),    TBL(Dict<RVal>),    ERR(String),}

Есть три типа данных - строки, целые и нецелые, две формы их представления - атомарная и вектор. Также есть таблицы и ошибки. Dict - это пара Vec<String> и Vec<T> одинаковой длины. В случае таблицы T = Vec<RVal>, где каждый Val - это II, DD или SS. Rust позволяет в легкую распаралелливать программу, но нужно, чтобы типы данных позволяли передавать свои значения между потоками. Для этого я обернул все разделяемые значения в асинхронный счетчик ссылок Arc. Считается, что атомарные операции более медленные, однако в программе, которая работает с большими данными, это не имеет большого значения.

Интерпретатор работает с выражениями:

enum Expr {    Empty,    F1(fn (RVal) -> RRVal, Box<Expr>), // f(x)    F2(fn (RVal,RVal) -> RRVal, Box<Expr>, Box<Expr>), // f(x,y)    ELst(Vec<Expr>),    ID(String),  // variable/column    Val(Val),    // simple value - 10, "str"    Set(String,Box<Expr>), // 'set var expr' - assignment    Sel(Sel), // select    Tbl(Vec<String>,Vec<Expr>), // [c1 expr1, c2 expr2] - create table }

ELst и Empty используются только парсером. Expr (ссылки на себя) необходимо хранить в куче (Box). Выполняются выражения функцией eval в некотором контексте, где заданы переменные (Set), а также могут быть определены колонки таблицы:

struct ECtx {    ctx: HashMap<String,Arc<Val>>,   // variables}struct SCtx {    tbl: Arc<Table>,                // within select    idx: Option<Vec<usize>>,        // idx into tbl    grp: Arc<Vec<String>>,          // group by cols}

eval сравнительно проста (self = ECtx):

type RRVal=Result<Arc<Val>,String>;fn top_eval(&mut self, e: Expr) -> RRVal {    match e {        Expr::Set(id,e) => {            let v = self.eval(*e, None)?;            self.ctx.insert(id,v.clone()); Ok(v)},        Expr::Sel(s) => self.do_sel(s),        _ => self.eval(e, None)    }}fn eval(&self, e: Expr, sctx:Option<&SCtx>) -> RRVal {    match e {        Expr::ID(id) => self.resolve_name(sctx,&id),        Expr::Val(v) => Ok(v.into()),        Expr::F1(f,e) => Ok(f(self.eval(*e,sctx)?)?),        Expr::F2(f,e1,e2) => Ok(f(self.eval(*e1,sctx)?,self.eval(*e2,sctx)?)?),        Expr::Tbl(n,e) => { self.eval_table(None,n,e) }        e => Err(format!("unexpected expr {:?}",e))    }}

Set и Sel нужен модифицируемый контекст, а его нельзя будет передать просто так в другой поток. Поэтому eval разбит на две части. Задача resolve_name - найти переменную или колонку и при необходимости применить where индекс. eval_table - собрать таблицу из частей и проверить, что с ней все в порядке (колонки одной длины и т.п.). Функции F1 (max, count ...) и F2 (+, >=, ...) сводятся к огромным match блокам, где для каждого типа прописывается нужная операция. Макросы позволяют уменьшить количество кода. Например, для арифметических операций часть match выглядит так:

(Val::D(i1),Val::I(i2)) => Ok(Val::D($op(*i1,*i2 as f64)).into()),(Val::D(i1),Val::D(i2)) => Ok(Val::D($op(*i1,*i2)).into()),(Val::I(i1),Val::II(i2)) => Ok(Val::II(i2.par_iter()    .map(|v| $op(*i1,*v)).collect()).into()),

Это может показаться неоптимальным, но когда вы обрабатываете таблицу на 100 миллионов строк, это не имеет ни малейшего значения. Видите слово par_iter выше? Это все, что нужно сделать в Rust, чтобы операция стала параллельной.

Выполнение select гораздо интереснее и сложнее. Разберем его на Q, потому что код на Rust многословно повторяет код на Q, который и сам по себе непростой.

Select состоит из подвыражений (join, where, group, select, distinct, into), каждое из которых выполняется отдельно. Самое сложное из них - join. В его основе лежит функция rename, задача которой присвоить колонкам уникальные имена, чтобы не возникло конфликта при join:

// если x это name -> найти, select -> выполнитьsget:{[x] $[10=type x;get x;sel1 x]};// в грамматике таблица определяется как '(ID|sel) ("as" ID)?'// так что x это список из 2 элементов: (ID из as или имя таблицы;ID/select)// y - уникальный префиксrename:{[x;y]  t:sget x 1; // получить таблицу: names!vals  k:(k!v),(n,/:k)!v:(y,n:x[0],"."),/:k:key t; // k - оригинальные имена,        // v - уникальные, n - с префиксом (table.name)  (k;v!value t)};

Все эти манипуляции сводятся к построению двух словарей - отображения из настоящих имен колонок и расширенных (table.name) в уникальные и из уникальных имен в сами колонки таблицы. Уникальные имена позволяют иметь в одной join таблице колонки с одинаковыми именами из разных таблиц и обращаться к ним в выражениях через нотацию с точкой.

В основе join следующая функция:

// x - текущая таблица в формате rename// y - следующая таблица в этом формате// z - join выражение, список (колонка в x;и в y)// условие join: x[z[i;0]]==y[z[i;1]] для всех ijoin_core:{[x;y;z]  // m - отображение имен в уникальные для новой таблицы x+y  // имена из x имеют приоритет  // c - переименовываем join колонки в уникальные имена  c:(m:y[0],x 0)z;  // после join z[;0] и z[;1] колонки будут одинаковыми  // поэтому колонки из y перенаправим на x  m[z[;1]]:c[;0];  // x[1]c[;0] - просто join колонки из таблицы x (подтаблица)  // y[1]c[;1] - симметрично из y  // sij[xval;yval] -> (idx1;idx2) найти индексы join в обеих таблицах  // sidx[(i1;i2);x;y без join колонок] -  //  собрать новую таблицу из x и y и индексов  (m;sidx[sij[x[1]c[;0];y[1]c[;1]];x 1;c[;1]_ y 1])}// sidx просто применяет индексы ко всем колонкам и объединяет y и z// y z - это словари, но поскольку традиционно векторные функции имеют// максимально широкую область определения, не нужно обращаться явно к value sidx:{(y@\:x 0),z@\:x 1};

Вся работа выполняется в функции sij, все остальное - это манипуляции именами, колонками и индексами. Если бы мы захотели добавить другой тип индекса, достаточно было бы написать еще одну sij. Конечно, функция выглядит непросто, но учитывая, что она покрывает 80% select, ей можно это простить.

Функция sij сводится к поиску строк таблицы x в таблице y. В Rust для этих целей можно использовать HashMap с быстрой hash функцией FNV - поместить в Map одну таблицу и потом искать в ней строки второй. В Q, судя по времени выполнения, скорее всего используется что-то подобное. В целом в Q у нас есть два варианта - использовать векторные примитивы или воспользоваться встроенными возможностями связанными с таблицами. В первом варианте все по-честному:

// x и y - списки колонокsij:{j:where count[y 0]>i:$[1=count x;y[0]?x 0;flip[y]?flip x]; (j;i j)};// или на псевдокоде// i=find_idx[tblY;tblX]; j=i where not null i; return (j,i[j])

используем функцию поиска значения в векторе (?) и транспозиции матрицы (flip). Этот вариант не такой медленный как может показаться - всего в 2.5 раза медленнее, чем оптимизированный поиск сразу по таблице (который выглядит ровно также - x?y, только x и y - таблицы, а не списки векторов). Это показывает в очередной раз силу векторных примитивов.

Наконец сам join - это просто цикл свертки по всем таблицам (fold):

// "/" это fold, rename' это map(rename)sjoin:{[v] join_core/[rename[v 0;"@"];rename'[v 1;string til count v 1];v 2]};

Остальные части select гораздо проще. where:

swhere:{[t;w] i:til count value[t 1]0;  // все строки по умолчанию  $[count w;where 0<>seval[t;i;();w];i]}; // выбрать те, которые не 0// seval такой же как eval в Rust, т.е. его сигнатура:// seval[table,index;group by cols;expr], ECtx - это сам Q

Основная функция select:

sel2:{[p] // p ~ словарь с элементами select (`j, `s, `g  и т.п.)  i:swhere[tbl:sjoin p`j;p`w]; // сходу делаем join и where  if[0=count p`s; // в случае select * надо найти подходящие имена колонкам    rmap:v[vi]!key[tbl 0] vi:v?distinct v:value tbl 0;    p[`s]:{nfix[x]!x} rmap key tbl 1];  if[count p`g; // group by    // из group колонок нужен только первый элемент, нужно знать их имена    gn:nfix {$[10=type x;x;""]} each p`g;    // sgrp вернет список индексов (idx1;idx2;..) для каждой группы    // затем нужно выполнить seval[tbl;idxN;gn;exprM] для всех idx+expr    // т.е. двойной цикл, который в Q скрыт за двумя "each"    g:sgrp[tbl;i;p`g]];    :key[p`s]!flip {x[z] each y}[seval[tbl;;gn];value p`s] each g;  // если group нет, то все элементарно - просто seval для всех select выражений  (),/:seval[tbl;i;()] each p`s };

Функция sgrp в основе group by - это просто векторный примитив group, возвращающий словарь, где ключи - уникальные значения, а значения - их индексы во входном значении:

sgrp:{[t;i;g] i value group flip seval[t;i;()] each g};

Я опускаю distinct и into части, поскольку они малоинтересны. В целом - это весь select на Q. В краткой записи он занимает всего 25 строк. Можно ли ждать хоть какой-то производительности от столь скромной программы? Да, потому что она написана на векторном языке!

Производительность

Напомню, что этот игрушечный интерпретатор может выполнять выражения типа

select * from (select sym,size,count(*),avg(price) into r  from bt where price>10.0 and sym='fb'  group by sym,size)  as t1 join ref on t1.sym=ref.sym, t1.size = ref.size

и при этом справляться с таблицами в сотни миллионов строк. В частности таблица bt в выражении выше сгенерирована выражением:

// в интерпретаторе на Rust// s = ("apple";"msft";"ibm";"bp";"gazp";"google";"fb";"abc")// i/f - i64/f64 интервалы [0-100)set bt [sym rand('s',100000000), size rand('i', 100000000),    price rand('f', 100000000)]

Т.е. содержит 100 миллионов строк. Поначалу базовый select с group by (получается 800 групп по ~125000 элементов)

select sym,size,count(*),avg(price) into r from bt group by sym,size

работал 44 секунды в программе на Rust, что совсем неплохо и само по себе. Однако после некоторых оптимизаций, а главное распаралелливания ключевых операций, мне удалось добиться скорости порядка 6 секунд. На мой взгляд весьма хороший результат для подобной таблицы.

Самое главное, программа на Rust, несмотря на свой внушительный вид, - это почти 1 в 1 программа на Q. Поэтому больших интеллектуальных усилий и даже отладки она не потребовала. Также благодаря векторности изначального языка ее ускорение путем распараллеливания не потребовало почти никаких усилий - если все операции изначально над массивами, то все что нужно - это вставить там и тут par_iter вместо iter.

Интерпретатор на Q не столь быстр, но вышеуказанный select всего на 50% медленнее аналогичного запроса на самом Q. Это значит, что по сути Q работает на больших данных почти также быстро, как и программа на компилируемом языке.

Хочу также отметить то, насколько великолепным языком проявил себя Rust. За все время разработки и отладки я не получил ни одного segfault и даже panic увидел всего несколько раз, и почти все это были простые ошибки выхода за пределы массива. Также поражает, насколько легко и безопасно в нем можно распараллелить задачу.

Парсер

Я отложил парсер на конец, поскольку он довольно объемен и не имеет прямого отношения к теме статьи. Тем не менее, может вам будет интересно ознакомиться с тем, как легко можно написать весьма серьезный парсер в функциональном стиле на Rust.

Это рекурсивный нисходящий парсер без заглядывания вперед. Из-за этого он не может предсказать следующий шаг и вынужден обходить все варианты. Такой парсер, конечно, медленный и не годится для серьезных задач, но для SQL выражений больше и не надо. Какая разница, парсится выражение 1 микросекунду или 10, если сам запрос займет минимум сотни микросекунд.

Такие парсеры часто пишут руками, и выглядят они примерно так:

parse_expr1(..) {   if(success(parse_expr2(..)) {    if (success(parse_str("+") || success(parse_str("-")) {      if(success(parse_expr1(..)) {         return <expr operation expr>      }      return Fail    }    return <expr>  }  return Fail;}

Главная идея предлагаемого парсера в том, что нет смысла писать это все руками, можно написать генератор подобных парсеров из BNF-подобной формы. Для всех сущностей BNF пишем по функции, затем генерируем из описания грамматики в виде строк набор парсящих функций, и все готово. В Rust, как строго типизированном языке, есть нюансы. В первую очередь определим типы для парсящих и post process функций:

type ParseFn = Box<dyn Fn(&PCtx,&[Token],usize) -> Option<(Expr,usize)>>;type PPFn = fn(Vec<Expr>) -> Expr;

ParseFn будет захватывать правила грамматики, поэтому она должна быть замыканием (closure) и лежать в куче. PCtx содержит другие ParseFn для рекурсивных вызовов и PPFn для постобработки дерева. Если парсинг не удался, она возвращает None, иначе Some с выражением и новым индексом в массив токенов. PPFn обрабатывает узел дерева, поэтому принимает безликий список выражений и превращает его в нужное выражение.

Для понимания процесса приведу часть грамматики, касающуюся выражений:

("expr", "expr1 ('or' expr {lst})? {f2}"),("expr1","'not' expr1 {f1} | expr2 ('and' expr1 {lst})? {f2}"),("expr2","expr3 (('='|'<>'|'<='|'>='|'>'|'<') expr2 {lst})? {f2}"),("expr3","expr4 (('+'|'-') expr3 {lst})? {f2}"),("expr4","vexpr (('*'|'/') expr4 {lst})? {f2}"),("vexpr","'(' expr ')' {2} | '-' expr {f1} | call | ID | STR | NUM |  '[' (telst (',' telst)* {conc}) ']' {tblv}"),("call", "('sum'|'avg'|'count'|'min'|'max') '(' expr ')' {call} |  'count' '(' '*' ')' {cnt} | 'rand' '(' STR ',' NUM ')' {rand}"),

Тут видны ключевые части - имя правила, само правило и PP функции в фигурных скобках. Каждая продукция правила должна заканчиваться на PP функцию, поскольку правило возвращает Expr, а не Vec<Expr>. PP функция по умолчанию возвращает последний элемент вектора, поэтому кое-где PP функций нет. ID, NUM и т.п. должны обрабатываться ParseFn функцией с соответствующим именем.

Генерируется наш парсер с помощью следующей функции:

let parse = |str| {    let t = l(str);  // add ({}) depth map    let mut lvl = 0;    pp_or(&t.into_iter().map(|v| {      match v.str.as_bytes()[0] {        b'(' | b'{' => lvl+=1,        b')' | b'}' => lvl-=1,        _ => ()};      (v,std::cmp::max(0,lvl))}).collect::<Vec<(Token,i32)>>()    , 0)};

l - это лексер, я переиспользую для этого лексер SQL. Нужно добавить карту глубины вложенности скобок, чтобы было удобно выделять BNF подвыражения. Поскольку это парсер для внутренних потребностей, то нет необходимости проверять правильность скобок, беспокоиться о глубине рекурсии и т.п.

Далее наше правило поступает в парсер BNF. Нужно реализовать следующие компоненты:

• or правило - A | B

• and правило - A B C

• const правило - "(", "select".

• token правило - NUM, STR.

• subrule правило - expr1, call.

• optional правило - A?

• 0+ правило - A*

• 1+ правило - A+

• PP правило - {ppfn}

Это работа, требующая тщательности, но проделать ее нужно один раз. Например, or правило:

fn pp_or(t: &[(Token,i32)], lvl:i32) -> ParseFn {    if t.len() == 0 {return Box::new(|_,_,i| Some((Expr::Empty,i)))};    let mut r: Vec<ParseFn> = t      .split(|(v,i)| *i == lvl && v.str.as_bytes()[0] == b'|' )      .map(|v| pp_and(v,lvl)).collect();    if 1 == r.len() {        r.pop().unwrap()    } else {        Box::new(move |ctx,toks,idx|          r.iter().find_map(|f| f(ctx,toks,idx)))    }}

Функция должна вернуть ParseFn замыкание. В общем случае, когда pp_and вернула несколько ParseFn, нужно организовать цикл и выполнять подфункции, пока одна из них не вернет Some.

pp_and работает аналогично, только все ее подфункции должны вернуть Some. Также в случае успеха она должна вызвать нужную PPFn для обработки результата.

fn pp_and(t: &[(Token,i32)], lvl:i32) -> ParseFn {    if t.len() == 0 {return Box::new(|_,_,i| Some((Expr::Empty,i)))};    let (rules,usr) = pp_val(Vec::<ParseFn>::new(),t,lvl);    Box::new(move |ctx,toks,i| {        let mut j = i;        let mut v = Vec::<Expr>::with_capacity(rules.len());        for r0 in &rules {        if let Some((v0,j0)) = r0(ctx,toks,j) {            j = j0; v.push(v0)            } else {return None} };        Some((ctx.ppfns[&usr](v),j))    })}

pp_val рекурсивно обрабатывает круглые скобки и все базовые выражения. Вот некоторые примеры из нее:

// Token - if ok call rules[Token]move |ctx,tok,i| if i<tok.len() && tok[i].kind == s   {ctx.rules[&s](ctx,tok,i)} else {None}// Subrulemove |ctx,tok,i| ctx.rules[&s](ctx,tok,i))}// rule?move |ctx,tok,i| Some(rule(ctx,tok,i).unwrap_or((Expr::Empty,i)))// rule+move |ctx,tok,i| {    let (e,i) = plst(&rule,ctx,tok,i);    if 0<e.len() {Some((Expr::ELst(e),i))} else {None}}// где plstlet mut j = i; let mut v:Vec<Expr> = Vec::new();while let Some((e,i)) = rule(ctx,tok,j) {j=i; v.push(e)};(v,j)

Это весь код, необходимый для создания парсера. Чтобы его сгенерировать, нужно вызвать parse и положить правило в map:

let mut map = HashMap::new();map.insert("expr".to_string(), parse("expr1 ('or' expr {lst})? {f2}"));...  

Также необходимо определить PP функции. В большинстве случаев они сравнительно просты:

let mut pfn: HashMap<String,PPFn> = HashMap::new();// default rulepfn.insert("default".to_string(),|mut e| e.pop().unwrap());// set name expr выражениеpfn.insert("set".to_string(),|mut e| Expr::Set(e.swap_remove(1).as_id(),  e.pop().unwrap().into()) );

В Rust нельзя просто взять элемент из массива, поэтому необходимы функции типа swap_remove, которые делают это безопасно.

Наконец, положим правила в специальную структуру и определим для нее функцию parse:

PCtx { rules:map, ppfns:pfn}...impl PCtx {    fn parse(&self, t:&[Token]) -> Expr {        if let Some((e,i)) = self.rules["top"](&self,t,0) {            if i == t.len() {e}              else {Val::ERR("parse error".into()).into()}        } else {Val::ERR("parse error".into()).into()}    }}

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

Современные сети, основанные на маршрутизации IP-пакетов, а точнее сервисы, которые они предоставляют, по факту управляются протоколом BGP. Этот протокол был спроектирован в конце 80-хх на трех салфетках. Да, с тех пор в этот протокол добавили массу возможностей, в том числе обмен маршрутной информацией VPN, правилами фильтрации трафика и всяким прочим полезным, но основа там осталась все той же, описанной на трех салфетках. И в этом есть свой плюс, потому что этот протокол в своей сути очень прост.

Но я хотел поговорить не о его простоте, а о "махании кулаками после драки", с которой частенько приходится сталкивать любой службе эксплуатации сети, или NOC - network operation centre (а может быть и center).

Поступает жалоба "а у меня вот сайт не открывается", или "вот час тому назад плохо работал сайт такой-то, а 5 минут тому назад он починился". Инженер идет на маршрутизатор и смотрит что маршрут к адресу рекомого сайта изменился 5 минут тому назад. И что с этим можно сделать? Чаще всего мало чего. Маршрутизатор знает, что вот такой маршрут "прилетел" 5 минут тому назад, а вот что было раньше? Может быть ничего существенного и не произошло, у маршрута обновились какие-нибудь информационные параметры, а пакеты как летели, так и летят в том же направлении. А может быть наоборот - маршрут изменился существенно и пакеты летят совсем в другом направлении. И узнать историю без дополнительного инструментария (или машины времени) нет возможности. И опять же - хорошо бы узнать, что же именно менялось. Да, есть глобальный инструмент bgplay. Но он рассчитан на использование в Интернете и запоминает изменения при перестроении маршрута между разными провайдерами. А вот изменения внутри сети одного провайдера он не ловит, да и не должен, так как не все то что происходит внутри автономной системы, должно быть видно снаружи.

И вот захотелось мне заиметь такой инструмент. Поиски готового ни к чему не привели (ни на что тут не претендую, может плохо искал). Соответственно, если нет готового решения - почему бы и не попробовать сделать самому? Все вроде понятно, собираем маршрутную информацию и храним историю изменений.

А вот дальше я подзавис. Самая лучшая библиотека, даже я бы сказал целый фреймворк, для обработки BGP - это пакет exabgp. Всем хорош и удобен. Один, на мой взгляд, существенный минус - он на python. Не то чтобы я был питононенавистником, отнюдь. Но каждый инструмент хорош, когда применяется по назначению. А python имеет всем известные особенности (интерпретатор, GIL), которые препятствуют эффективной обработке данных, если алгоритмы реализовывать именно на нем. И в данном случае мне хотелось бы иметь реализацию инструмента на компилируемом (как минимум) языке, с управляемыми политиками блокировок. А также иметь возможность выделить обработку протокола BGP в виде библиотеки и желательно чтобы применяемый язык мог позволить библиотеке жить без своего неотделимого и неотъемлемого рантайма (привет, golang!). Для чего? Ну, например, для того чтобы в перспективе применять эту библиотеку для других bgp-шных приложений. Ну и для скорости. Далеко не для всех видов запросов для поиска маршрутной информации возможно построить эффективный индекс.

Решил я попробовать в качестве основного языка по этой теме Rust и в общем все что хотел получилось. Работу с протоколом BGP выделил в библиотеку. В отличие от exabgp реализовывать логику работы BGP FSM в библиотеке я не стал, по той простой причине что в Rust для сети используется не одно API, std там строго синхронное, а в реальных задачах лучше иметь возможность применять по желанию и потребности асинхронные библиотеки. Библиотеку разумеется назвал zettabgp, а приложение bgpexplorer.

Принцип работы прост. Bgpexplorer может как выступать в роли bgp-спикера, то есть роутер (лучше всего route reflector) устанавливает с сервером bgp-соседство, и отдает в сторону сервера всю маршрутную информацию. Приложение накапливает в своей RIB (Routing Information Database) как актуальную маршрутную информацию, так и историческую. Для просмотра и поисковых запросов доступен веб-интерфейс. Сейчас все хранится в оперативной памяти и ее нужно достаточно много - в зависимости разумеется от того, какого объема таблицу маршрутизации нужно отслеживать.

Если интересно попробовать - то это просто. Нужна сеть, которую нужно мониторить и комп (сервер) с достаточно большим объемом ОЗУ чтобы маршрутная информация туда поместилась.

На сервере нужно взять исходники с гитхаба, предполагается что уже есть git и rust.

$ git clone https://github.com/wladwm/bgpexplorer...$ cd bgpexplorer$ cargo build...

Приложение собрано. Теперь на роутере настроим соседство с сервером.

Если это Cisco, то:

! Номер автономки тут 65535 разумеется для примера, как и адресаrouter bgp 65535 ! указываем адрес сервера с той же автономкой, чтобы сессия была IBGP neighbor 10.1.1.1 remote-as 65535 ! указываем с какого адреса соединяться neighbor 10.1.1.1 update-source Loopback0 ! будем ждать попыток соединения с сервера neighbor 10.1.1.1 transport connection-mode passive address-family ipv4 ! для паблик инета активируем  neighbor 10.1.1.1 activate ! отправляем на сервер вообще все что есть  neighbor 10.1.1.1 route-reflector-client ! Активируем если нужно ipv4 labeled-unicast  neighbor 10.1.1.1 send-label address-family vpnv4 ! включаем VPNv4  neighbor 10.1.1.1 activate  neighbor 10.1.1.1 send-community extended

Возвращаемся на сервер и подготовим конфигурационный файл для приложения

$ cat > bgpexplorer.ini <<EOF[main]httplisten=0.0.0.0:8080httproot=contribsession=s0whoisjsonconfig=whois.json[s0]mode=bmpactivebgppeer=10.0.0.1peeras=65535EOF

В секции main указываем:

• httplisten на каком адресе и порту будет работать протокол http

• httproot где лежит корень файлового сервиса. Там лежит index.html и все такое прочее.

• Whoisjsonconfig указывает на файл конфигурации сервиса whois

• Session это имя секции, описывающей режим работы bgp, в данном примере s0

В секции сессии (s0 в данном примере) указано:

• bgppeer адрес роутера BGP для активного режима

• Peeras номер автономной системы

• protolisten адрес:порт, где ожидать входящего соединения по протоколу BGP или BMP

• Mode варианты работы протокола

В mode можно указать:

• bgppassive ждать входящего подключения от роутера

• bgpactive инициировать подключение к роутеру

• bmpactive инициировать подключение к роутеру по протоколу BMP

• bmppassive ждать входящего подключения от роутера по протоколу BMP

После написания ini-файла можно запустить bgpexplorer, например, командой

cargo run

После чего можно открыть браузер и направить его на адрес сервера с указанием порта.

На самом верху будет выбор RIB для просмотра - IPv4, IPv6, VPN разные всякие и т.п.

Далее строка для фильтра, а уже после нее - пейджинг и собственно маршрутная информация.

Неактивные маршруты будут отображены серым курсивом. У маршрутов, у которых есть история изменений будет кнопка разворачивания истории.

В фильтре можно задавать кроме собственно подсетей фильтрацию по community, aspath, nexthop, route-target, route-distinguisher.

При наведении курсора на ASn, адреса роутеров будет выполняться запрос к whois или DNS, и полученная информация будет отображаться в попапе. Иногда это долго, но бывает полезно.

Буду рад, если этот инструмент пригодится еще кому-нибудь. Найденные проблемы, пожелания, идеи, конструктивная критика приветствуется.

Не так давно в качестве хобби я решил погрузиться в изучение embedded разработки на Rust и через какое-то время мне захотелось сделать себе логгер, который бы просто писал логи через UART, но при этом не знал какая конкретно реализация используется. Вот тут я быстро осознал, именно в этом конкретном случае я не могу полагаться на статический полиморфизм и мономорфизацию, ведь компилятор не знает сколько нужно памяти выделять под конкретную реализацию. Фактически это означает, что нам нужно как-то уметь сохранять в памяти типы, размер которых неизвестен на этапе компиляции. Такой способностью обладает типBox, но он использует для этого динамическое выделение памяти из кучи. В итоге возникла идея написать свой аналог данного типа, но хранящий объект в предоставленном пользователем буфере, а не в глобальной куче.

А почему бы просто не взять какой-нибудьlinked_list_allocatorот Фила, дать ему пару килобайт памяти и воспользоваться обычнымBoxтипом, или даже взять какой-нибудь простейший bump аллокатор, ведь мы хотим использовать его лишь для того, чтобы создать несколько глобальных объектов, но есть множество сценариев, когда куча не используется принципиально? Это и дополнительная зависимость от целогоallocкрейта и дополнительные риски, что использование кучи выйдет за рамки строго детерминированных сценариев, что будет приводить к трудноуловимым ошибкам.

С другой стороны, мы можем просто принимать&'static dyn Traitи таким образом переложить заботу о том, как получить такую ссылку, на конечного пользователя, но чтобы обеспечить потом доступ к этой ссылке, нам необходимо использовать примитивы синхронизации или же воспользоваться unsafe кодом, с другой стороны, конечный пользователь тоже должен воспользоваться ими, чтобы создать такую ссылку. В конечном итоге у нас получается или двойная работа или unsafe в публичном API, что довольно плохо. Да и в целом, Box обладает гораздо более широкой областью применения, например, его можно использовать для организации очереди задач в очередном futures executor.

Что же такое безразмерные типы?

Хочу немного напомнить о том, что такое типы динамического размера (DST) и чем они отличаются от обычных. Большинство типов имеют фиксированный размер, известный на этапе компиляции, такие типы компилятор помечает трейтомSized, но есть типы, размер которых в памяти неизвестен на этапе компиляции, поэтому компилятор не может размещать их в статической памяти или на стэке по значению, такие типы еще называют безразмерными.

Тут очень важно понимать, что для каждого конкретного типа компиляторточнознает внутреннее устройство его безразмерного аналога, проблема в том, что один и тот же безразмерныйdyn Displayможет быть получен из самых разнообразных конкретных типов, чем и обеспечивается динамический полиморфизм. И именно поэтому можно приводить к безразмерным типам лишь ссылки и указатели, уж размер указателя компилятору всегда известен.

Ссылки и указатели в Rust это не всегда просто адреса в памяти, в случае с DST типами, помимо адреса хранится еще и объект с метаданными указателя, но гораздо проще это все осознать, если просто взглянуть на код стандартной библиотеки.

#[repr(C)]pub(crate) union PtrRepr<T: ?Sized> {    pub(crate) const_ptr: *const T,    pub(crate) mut_ptr: *mut T,    pub(crate) components: PtrComponents<T>,}#[repr(C)]pub(crate) struct PtrComponents<T: ?Sized> {    pub(crate) data_address: *const (),    pub(crate) metadata: <T as Pointee>::Metadata,}

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

pub struct DynMetadata<Dyn: ?Sized> {    vtable_ptr: &'static VTable,    phantom: crate::marker::PhantomData<Dyn>,}/// The common prefix of all vtables. It is followed by function pointers for trait methods.////// Private implementation detail of DynMetadata::size_of etc.#[repr(C)]struct VTable {    drop_in_place: fn(*mut ()),    size_of: usize,    align_of: usize,}

Таким образом, в текущей реализации, размер&dyn Displayна x86_64 составляет 16 байт, а когда мы пишем такой вот код:

let a: u64 = 42;let dyn_a: &dyn Display = &a;

Компилятор генерирует объектVTableи сохраняет его где-то в статической памяти, а обычную ссылку заменяет на широкую, содержащую кроме адреса еще и указатель на таблицу виртуальных функций. Ссылка на таблицу виртуальных функций статическая и не зависит от места расположения значения, таким образом, для того, чтобы создать желаемыйBox<dyn Display>из искомого значенияa, нам необходимо извлечь метаданные из ссылки наdyn_aи все это вместе скопировать в заранее приготовленный для этого буфер. Чтобы все это сделать, нам необходимо использовать nightly features:unsizeиptr_metadata.

Для получения&dyn Tиз&Valueиспользуется специальный маркерный трейтUnsize, который выражает отношение междуSizedтипом и его безразмерным альтер-эго. То есть,TэтоUnsize<dyn Trait>в том случае, еслиTреализуетTrait.

А чтобы работать с метаданными указателя используется функцияcore::ptr::metadataи типажPointee, который связывает тип указателя и тип его метаданных, в случае с безразмерными типами метаданные имеют типDynMetadata<T>, гдеTэто искомый безразмерный тип.

#[inline]fn meta_offset_layout<T, Value>(value: &Value) -> (DynMetadata<T>, Layout, usize)where    T: ?Sized + Pointee<Metadata = DynMetadata<T>>,    Value: Unsize<T> + ?Sized,{    // Get dynamic metadata for the given value.    let meta = ptr::metadata(value as &T);    // Compute memory layout to store the value + its metadata.    let meta_layout = Layout::for_value(&meta);    let value_layout = Layout::for_value(value);    let (layout, offset) = meta_layout.extend(value_layout).unwrap();    (meta, layout, offset)}

Помимо извлечения метаданных, данная функция еще и вычисляет размещение в памяти для метаданных и смещение по которому следует сохранять значение, но об этом мы подробнее еще поговорим.

Обратите внимание, что мы беремLayoutот ссылки на метаданные, а неDynMetadata<Dyn>::layout, последний описывает размещениеVTable, но нас интересует размещение самогоDynMetadata, будьте внимательны!

Пишем свой Box

Вот, теперь у нас есть все необходимое, чтобы написать нашBox, его код довольно простой:

Конструктор, который копирует данные и метаданные в предоставленный буфер, используя довольно удобное API указателя.

impl<T, M> Box<T, M>where    T: ?Sized + Pointee<Metadata = DynMetadata<T>>,    M: AsRef<[u8]> + AsMut<[u8]>,{    pub fn new_in_buf<Value>(mut mem: M, value: Value) -> Self    where        Value: Unsize<T>,    {        let (meta, layout, offset) = meta_offset_layout(&value);        // Check that the provided buffer has sufficient capacity to store the given value.        assert!(layout.size() > 0);        assert!(layout.size() <= mem.as_ref().len());        unsafe {            let ptr = NonNull::new(mem.as_mut().as_mut_ptr()).unwrap();            // Store dynamic metadata at the beginning of the given memory buffer.            ptr.cast::<DynMetadata<T>>().as_ptr().write(meta);            // Store the value in the remainder of the memory buffer.            ptr.cast::<u8>()                .as_ptr()                .add(offset)                .cast::<Value>()                .write(value);            Self {                mem,                phantom: PhantomData,            }        }    }}

А вот и код, который собирает байты назад в&dyn Trait:

    #[inline]    fn meta(&self) -> DynMetadata<T> {        unsafe { *self.mem.as_ref().as_ptr().cast() }    }    #[inline]    fn layout_meta(&self) -> (Layout, usize, DynMetadata<T>) {        let meta = self.meta();        let (layout, offset) = Layout::for_value(&meta).extend(meta.layout()).unwrap();        (layout, offset, meta)    }    #[inline]    fn value_ptr(&self) -> *const T {        let (_, offset, meta) = self.layout_meta();        unsafe {            let ptr = self.mem.as_ref().as_ptr().add(offset).cast::<()>();            ptr::from_raw_parts(ptr, meta)        }    }    #[inline]    fn value_mut_ptr(&mut self) -> *mut T {        let (_, offset, meta) = self.layout_meta();        unsafe {            let ptr = self.mem.as_mut().as_mut_ptr().add(offset).cast::<()>();            ptr::from_raw_parts_mut(ptr, meta)        }    }

Дальше смело можно добавить реализациюDerefиDerefMut, в конце концов, в данном случае это как раз тот самый случай, для которых эти самые типы и были созданы.

impl<T, M> Deref for Box<T, M>where    T: ?Sized + Pointee<Metadata = DynMetadata<T>>,    M: AsRef<[u8]> + AsMut<[u8]>,{    type Target = T;    #[inline]    fn deref(&self) -> &T {        self.as_ref()    }}impl<T, M> DerefMut for Box<T, M>where    T: ?Sized + Pointee<Metadata = DynMetadata<T>>,    M: AsRef<[u8]> + AsMut<[u8]>,{    #[inline]    fn deref_mut(&mut self) -> &mut T {        self.as_mut()    }}

running 8 teststest tests::test_box_dyn_fn ... oktest tests::test_box_nested_dyn_fn ... oktest tests::test_box_in_provided_memory ... oktest tests::test_box_trait_object ... oktest tests::test_box_move ... oktest tests::test_drop ... oktest tests::test_layout_of_dyn ... oktest tests::test_box_insufficient_memory ... ok

Miri

Казалось бы, все замечательно, можно использовать библиотеку в боевом коде... Но, постойте, мы же написали unsafe код, как мы вообще можем быть уверены в том, что нигде не нарушили никакие инварианты? К счастью, существует такой проект, как Miri, который интерпретирует промежуточное представление MIR, генерируемое компилятором rustc, используя специальную виртуальную машину. Таким образом, можно находить очень многие ошибки в unsafe коде, подробнее об этом можно почитать в этойстатье. Давайте попробуем запустить наши тесты используя Miri.

cargo miri test   Compiling static-box v0.0.1 (/home/aleksey/Projects/opensource/static-box)    Finished test [unoptimized + debuginfo] target(s) in 0.40s     Running unittests (target/x86_64-unknown-linux-gnu/debug/deps/static_box-e2c02215f3157959)running 8 teststest tests::test_box_dyn_fn ... error: Undefined Behavior: accessing memory with alignment 1, but alignment 8 is required   --> /home/aleksey/.rustup/toolchains/nightly-2021-04-25-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:886:9    |886 |         copy_nonoverlapping(&src as *const T, dst, 1);    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ accessing memory with alignment 1, but alignment 8 is required    |    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

Ага! Вот и нашлась довольно серьезная проблема, которую мы упустили, и которую нам наша x86 архитектура просто взяла и простила - невыровненный доступ к памяти. Напомню, что процессоры при работе с памятью используют машинные слова, размер которых обычно равен размеру указателя, поэтому компиляторы вставляют в типы, которые не кратны размеру машинного слова, дополнительные байты для выравнивания, тоже самое касается и полей структур. В нашем случае, мы просто подряд пишем байты метаданных и значения в буфер, начиная с какого-то адреса, никак ничего не проверяя, поэтому может возникать ситуация, когда адреса полей становятся не кратными машинному слову.

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

        // Construct a box to move the specified memory into the necessary location.        // SAFETY: This code relies on the fact that this method will be inlined.        let mut new_box = Self {            align_offset: 0,            mem,            phantom: PhantomData,        };        let raw_ptr = new_box.mem.as_mut().as_mut_ptr();        // Compute the offset that needs to be applied to the pointer in order to make        // it aligned correctly.        new_box.align_offset = raw_ptr.align_offset(layout.align());

Вот собственно и все, после этого Miri больше не показывает ошибок выравнивания.

cargo miri test   Compiling static-box v0.1.0 (/home/aleksey/Projects/opensource/static-box)    Finished test [unoptimized + debuginfo] target(s) in 0.30s     Running unittests (target/x86_64-unknown-linux-gnu/debug/deps/static_box-ce23f69c165cf930)running 11 teststest tests::test_box_dyn_fn ... oktest tests::test_box_in_provided_memory ... oktest tests::test_box_in_static_mem ... oktest tests::test_box_in_unaligned_memory ... oktest tests::test_box_insufficient_memory ... oktest tests::test_box_move ... oktest tests::test_box_nested_dyn_fn ... oktest tests::test_box_trait_object ... oktest tests::test_drop ... oktest tests::test_layout_of_dyn_split_at_mut ... oktest tests::test_layout_of_dyn_vec ... oktest result: ok. 11 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out   Doc-tests static-boxrunning 2 teststest src/lib.rs - (line 24) ... oktest src/lib.rs - (line 48) ... oktest result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.15s

Хочу еще сказать несколько слов относительно типаLayout, в нем содержится два поляsize, которое содержит размер памяти в байтах, необходимый для размещения объекта, иalign- это число (причем всегда степень двойки), которому должен быть кратен указатель на объект данного типа. И таким образом, чтобы починить выравнивание, мы просто вычисляем сколько нам нужно прибавить к адресу начала буфера, чтобы получить адрес кратныйalign. Дополнительно довольно доступно написано про выравнивание уу Фила.

Заключение

Ура, теперь мы можем писать вот такой вот код!

use static_box::Box;struct Uart1Rx {    // Implementation details...}impl SerialWrite for Uart1Rx {    fn write(&mut self, _byte: u8) {        // Implementation details    }}let rx = Uart1Rx { /* ... */ };SOME_GLOBAL_WRITER.init_once(move || Box::<dyn SerialWrite, [u8; 32]>::new(rx));// A bit of code later.SOME_GLOBAL_WRITER.lock().unwrap().write_str("Hello world!");

Итак, мы при помощи unsafe и некоторого количества nightly фич смогли написать тип, позволяющий размещать полиморфные объекты на стеке или в статической памяти без использования кучи, что может быть полезным во многих случаях. Хотя, конечно, каждый раз при получении ссылки на объект приходится дополнительно вычислять адрес метаданных и значения, но мы не можем просто так взять и сохранить эти адреса как поля структуры, в этом случае она станет самоссылающиеся, что довольно неприятно в Rust контексте, это не работает с семантикой перемещения. В целом, если воспользоваться pin API, и сделать нашBox неперемещаемым, то можно будет позволить себе эту оптимизацию, а заодно и обеспечить возможность работать с любыми Future типами.

Хочу еще сказать напоследок, что не стоит бояться писать низкоуровневый unsafe код, но стоит 10 раз подумать над его корректностью и обязательно использовать Miri вCIтестах, он отлавливает довольно много ошибок, а разработка низкоуровневого кода требует очень большой внимательности к деталям всевозможным граничным случаям. В конечном счете, именно знания того, как в реальности реализована та или иная языковая абстракция, позволяет перестать воспринимать её как черную магию. Часто все намного проще и очевиднее, чем кажется, стоит просто копнуть чуть поглубже.

А еще важно иногда выходить за рамки stable Rust, чтобы быть в курсе, куда же язык дальше развивается и тем самым расширять свой кругозор.

Ссылка на крейт

Зачем нужен Rust в R?

Первый вопрос, который должен возникнуть у читателя -- а зачем вообще использовать Rust вместе с R? Ответ довольно прост: Rust -- новый системный язык программирования, спроектированный специально для написания безопасного и легко распараллеливаемого кода. Rust довольно сложен в освоении (в сравнении с другими языками), но при этом предоставляет отличные инструменты для разработки. Rust имеет довольно неплохую ООП систему и очень много заимствует из функциональных языков программирования. Несмотря на дополнительную сложность из-за функциональных/ООП компонентов, Rust позиционируется как zero-cost abstraction язык, так же как и C++.

Из-за своей популярности Rust привлекает разработчиков, которые портируют старые библиотеки и разрабатывают новые крейты. Большинство из этих крейтов можно напрямую использовать в пакетах для R, упрощая жизнь разработчикам на R.

Таким образом, можно привести два основных аргумента в пользу использования Rust: более безопасный и удобочитаемый код и доступ к целому репозиторию Rust-крейтов.

Что нужно, чтобы R код мог вызвать Rust-библиотеку?

На самом деле -- не так уж много. R-пакеты могут содержать директорию src/, в которой находится исходный код на одном из компилируемых языков. С помощью src/Makevars или src/Makevars.win файлов (вариация make) можно контролировать процесс сборки, например, вызвав на одном из шагов cargo (см. пример здесь):

cargo build --release --manifest-path=rustlib/Cargo.toml

При этом Rust -библиотека должна собираться как crate-type = ["staticlib"]. Кроме непосредственной компиляции Rust-кода, нужно предоставить C-обертки к экспортируемым функциям, а так же добавить несколько магических вызовов специальных R-функций, которые объясняют R, какие именно функции и какого типа экспортируются из данной библиотеки (например, вот так).

Основная проблема -- C-обертки и преобразование типов из R SEXP (фактически, специальный указатель) во что-то, совместимое с Rust, учитывая при этом специфику управления памятью в R (все эти ваши PROTECT, UNPORTECT, и т. д.). Как результат -- легко создать примитивный прототип без функционала, практически невозможно написать достаточно большой проект.

Интегрируем R и Rust: три простых шага

Шаг первый: баиндинги для заголовочных файлов R

Взаимодействие с R происходит через специализированный API, доступный обычно ввиде C/ C++ заголовочных файлов (см. $R_HOME\include\). Разумеется, вызывать эти методы можно практически из любого языка, но это неудобно -- загловочные файлы невозможно подключить напрямую к Rust. К счастью, у этой проблемы уже давно есть решение: rust-bindgen (rust-lang/rust-bindgen). bindgen позволяет автоматически генерировать Rust-обертки из заголовочных файлов, и делает это довольно эффективно.

Так появился крейт libR-sys, который предоставляет баиндинги ко всем необходимым внутренним R функциям. Генерация баиндингов -- вещь нетривиальная, bindgen зависит от clangи сложен в конфигурировании, поэтому мы предоставляем pre-computed (заранее сгененрированные) баиндинги для большинства платформ, поддерживающих R. Список включает в себя linux-x64 (созданный с помощью Ubuntu-20.04), win-x86/x64 (с помощью msys2, x86 может иметь проблемы в каких-то пограничных случаях), macOS включая 11 версию (по возможности), x64 и экспериментально arm64 (честно я не знаю, есть ли arm64 сборка R под macOS). Для каждой из упомянутых платформ/архитектур мы стараемся предоставить три версии баиндингов: oldrel, release, и devel, что соответствует "прошлой", "текущей" (сейчас это 4.1.0) и "находящейся в разработке" версиям R.

В качестве альтернативы баиндинги можно сгенерировать непосредственно в системе где компилируется R пакет, при условии что все необходимые зависимости присутствуют (особенная головная боль на Windows). Гипотетически, можно собрать R для неподдерживаемой платформы и прямо на месте сгененрирвоать баиндинги (если Rust поддерживает такую платформу).

Исхоный код проекта досутпен здесь. Крейт находится в стадии поддержки, т. к. основная разработка завершена. Сейчас решается вопрос об автоматизации деплоймента новых баиндингов когда происходит релиз новой версии R.

Шаг второй: автоматизируем преобразование типов и экспорт функций

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

Прежде чем продолжить, я хочу сделать небольшое отступление. Вся идея проекта extendr и, в особенности, имплементация большей части Rust-крейтов, принадлежит Энди Томасону (@andy-thomason). Без его вклада, на мой субъективный взгляд, extendr в том виде, в котором он существует сейчас, был бы невозможен.

Вернемся обратно к коду. Как избавиться от боилерплейта? Легко, надо всего лишь распарсить исходный код Rust. Например, используя syn и подобные крейты. Моей экспертизы недостаточно, чтобы детально описать процесс парсинга и кодогенерации, но для конечного пользователя экспорт Rust функции становится невероятно простым. Во-первых, нужно пометить функции с помощью аттрибута #[extendr]:

#[extendr]fn add_i32(x : i32, y : i32) -> i32 { x + y }#[extendr]fn add_vec(x : &[i32], y : &[i32]) -> Vec<i32> {     x.iter().zip(y.iter()).map(|v| v.0 + v.1).collect()}

Во-вторых, нужно явно объявить экспортируемые функции:

extendr_module! {  mod extendrtest;  fn add_i32;  fn add_vec;}

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

К сожалению, остается одно небольшое ограничение при интеграции Rust-кода в проект. Дело в том, что если в папке src/ отсутствуют файлы-исходники, то стандартная процедура компиляции R попросут игнорирует все остальное и библиотека не компилируется. Чтобы обойти это, в src/ добавляется единственный файл entrypoint.c, примерно следующего содержания:

void R_init_extendrtest_extendr(void *dll);void R_init_extendrtest(void *dll) {  R_init_extendrtest_extendr(dll);}

Здесь R_init_extendrtest_extendr генерируется автоматически с помощью Rust-крейта, а R_init_extendrtest -- непосредственно вызывается из R. Мы пока что не нашли способа избавиться от этого ограничения.

Некоторых изменений требуют и Makevars-файлы. Вот пример из одного из тестовых проектов:

LIBDIR = ./rust/target/releaseSTATLIB = $(LIBDIR)/libextendrtest.aPKG_LIBS = -L$(LIBDIR) -lextendrtestall: C_clean$(SHLIB): $(STATLIB)$(STATLIB):cargo build --lib --release --manifest-path=./rust/Cargo.tomlC_clean:rm -Rf $(SHLIB) $(STATLIB) $(OBJECTS)clean:rm -Rf $(SHLIB) $(STATLIB) $(OBJECTS) rust/target

Фактически, мы отдельно компилируем Rust-крейт, а потом создаем совместимую с R библиотеку используя Rust-библиотеку и результат компиляции entrypoint.c.

Аналогично выглядит и версия для Windows, с той лишь разницей что на Windows мы поддерживаем иx86, и x64, из-за чего приходится динамически выбирать правильный путь к STATLIB.

extendr выполняет не только кодогенерацию на стороне Rust, он еще генерирует обертки на стороне R. Если предположить, что приведенный выше Rust код является частью пакета {extendrtest}, то становятся досутпны следующие функции:

extendrtest::add_i32(4L, 11L)# [1] 15extendrtest::add_vec(1:10, 10:1)#  [1] 11 11 11 11 11 11 11 11 11 11

Да, насктолько просто.

Шаг третий: user-friendliness

В своей работе мы вдохновлялись такими проектами как {cpp11} - header-only пакет для интеграции C++11 кода. Так появился на свет {rextendr}, R - пакет без Rust-зависимости, который решает три основные задачи:

• Создание шаблона пакета, использующего extendr, наподобие {usethis};

• Компиляция и исполнение Rust - кода на лету, прямо в R-сессии. Именно это демонстрирует Анимация Для Привлечения Внимания;

• Предоставление специальных knitr-модулей (engines), а именно {extendr} и {extendrsrc}, которые позволяют включать фрагменты Rust-кода (и результаты его выполнения) в ваш Rmarkdown прямо рядом с R-кодом, обеспечивая их взаимодействие.

Сейчас {rextendr} отправился на проверку в CRAN, и мы ждем результатов. Я думаю, самое время продемонстроровать несколько примеров именно с использованием {rextendr}. Сразу оговорюсь, для упрощения и воспроизводимости, я буду использовать{reprex}.

Самый простой пример это, конечно же,

rextendr::rust_function("fn hello_r() -> &'static str { \"Hello R!\" }")#> i build directory: 'C:\Users\...\AppData\Local\Temp\Rtmp259cVM\file10186cb44264'#> v Writing 'C:/Users/.../AppData/Local/Temp/Rtmp259cVM/file10186cb44264/target/extendr_wrappers.R'.hello_r()#> [1] "Hello R!"

Пример со сложением я уже показывал, но что будет, если явно передать NA?

rextendr::rust_function("fn add_i32(x : i32, y : i32) -> i32 { x + y }")#> i build directory: 'C:\Users\...\AppData\Local\Temp\Rtmp2P2cnQ\file2f7c65e8269a'#> v Writing 'C:/Users/.../AppData/Local/Temp/Rtmp2P2cnQ/file2f7c65e8269a/target/extendr_wrappers.R'.add_i32(42L, NA)#> Error in add_i32(42L, NA): unable to convert R object to primitive

Сообщения об ошибках еще не очень информативны, мы работаем над этим, но тем не менее мы получаем базовую валидацию просто за счет системы типов -- NA не совместим с i32. Однако, можно написать вот так

rextendr::rust_function("fn add_i32_opt(x : Option<i32>, y : Option<i32>) -> Option<i32> {    match (x, y) {        (Some(a), Some(b)) => Some(a + b),        _ => None    }}")#> i build directory: 'C:\Users\...\AppData\Local\Temp\Rtmpyg3uPw\file6587a897d2a'#> v Writing 'C:/Users/.../AppData/Local/Temp/Rtmpyg3uPw/file6587a897d2a/target/extendr_wrappers.R'.add_i32_opt(NA, 42L)#> [1] NAadd_i32_opt(42L, 100L)#> [1] 142

Хотите еще больше магии? Макрос R! выполняет внутри R-код, возвращая результат если операция была успешной. Как насчет

x <- 42L y <- 100Lrextendr::rust_eval("R!(x)? * 2 + R!(y)? * 3")#> i build directory: 'C:\Users\...\AppData\Local\Temp\RtmpKeC23J\file32ec53677fc9'#> v Writing 'C:/Users/.../AppData/Local/Temp/RtmpKeC23J/file32ec53677fc9/target/extendr_wrappers.R'.#> [1] 384

Можно попробовать смешать переменные из R и Rust.

library(tibble)x <- 10:1 # Эта переменная на стороне Rrextendr::rust_eval("call!(\"tibble\", x = R!(x), y = 1..=10)")#> i build directory: 'C:\Users\...\AppData\Local\Temp\RtmpcDWhlk\file45802f52dc5'#> v Writing 'C:/Users/.../AppData/Local/Temp/RtmpcDWhlk/file45802f52dc5/target/extendr_wrappers.R'.#> # A tibble: 10 x 2#>        x     y#>    <int> <int>#>  1    10     1#>  2     9     2#>  3     8     3#>  4     7     4#>  5     6     5#>  6     5     6#>  7     4     7#>  8     3     8#>  9     2     9#> 10     1    10

Эти макросы полезны, но до сих пор нестабильны. Они лишь демонстрируют потенциальные возможности для взаимодействия R и Rust.

Для безопасной печати в Rout существует отдельный макрос : rprintln!.

x <- 42Lrextendr::rust_eval("rprintln!(\"Hello from Rust! x = {}\", R!(x)?.as_integer().unwrap());")#> i build directory: 'C:\Users\...\AppData\Local\Temp\RtmpWQh3w0\file48e024f161ce'#> v Writing 'C:/Users/.../AppData/Local/Temp/RtmpWQh3w0/file48e024f161ce/target/extendr_wrappers.R'.#> Hello from Rust! x = 42

Пишем свой extendr-пакет

В этом разделе я просто приведу пример генерации пакета с использование {rextendr} и других стандартных инструментов:

pkg <- file.path(tempfile(), "myextendr")dir.create(pkg, recursive = TRUE)usethis::create_package(pkg)usethis::proj_activate(pkg)rextendr::use_extendr()rextendr::document()rextendr::document()hello_world()

pkg <- file.path(tempfile(), "myextendr")dir.create(pkg, recursive = TRUE)usethis::create_package(pkg)#> v Setting active project to 'C:/Users/.../AppData/Local/Temp/RtmpAVW4HZ/file122c180d1953/myextendr'#> v Creating 'R/'#> v Writing 'DESCRIPTION'#> Package: myextendr#> Title: What the Package Does (One Line, Title Case)#> Version: 0.0.0.9000#> Authors@R (parsed):#>     * First Last <first.last@example.com> [aut, cre] (YOUR-ORCID-ID)#> Description: What the package does (one paragraph).#> License: `use_mit_license()`, `use_gpl3_license()` or friends to pick a#>     license#> Encoding: UTF-8#> LazyData: true#> Roxygen: list(markdown = TRUE)#> RoxygenNote: 7.1.1#> v Writing 'NAMESPACE'#> v Setting active project to '<no active project>'usethis::proj_activate(pkg)#> v Setting active project to 'C:/Users/.../AppData/Local/Temp/RtmpAVW4HZ/file122c180d1953/myextendr'#> v Changing working directory to 'C:/Users/.../AppData/Local/Temp/RtmpAVW4HZ/file122c180d1953/myextendr/'rextendr::use_extendr()#> v Creating 'src/rust/src'.#> v Writing 'src/entrypoint.c'#> v Writing 'src/Makevars'#> v Writing 'src/Makevars.win'#> v Writing 'src/.gitignore'#> v Writing 'src/rust/Cargo.toml'.#> v Writing 'src/rust/src/lib.rs'#> v Writing 'R/extendr-wrappers.R'#> v Finished configuring extendr for package myextendr.#> * Please update the system requirement in 'DESCRIPTION' file.#> * Please run `rextendr::document()` for changes to take effect.rextendr::document()#> i Generating extendr wrapper functions for package: myextendr.#> ! No library found at 'src/myextendr.dll', recompilation is required.#> Re-compiling myextendr#>   -  installing *source* package 'myextendr' ...#>      ** using staged installation#>      ** libs#>      rm -Rf myextendr.dll ./rust/target/x86_64-pc-windows-gnu/release/libmyextendr.a entrypoint.o#>      "C:/rtools40/mingw64/bin/"gcc  -I"C:/PROGRA~1/R/R-41~1.0/include" -DNDEBUG          -O2 -Wall  -std=gnu99 -mfpmath=sse -msse2 -mstackrealign  -UNDEBUG -Wall -pedantic -g -O0 -c entrypoint.c -o entrypoint.o#>      cargo build --target=x86_64-pc-windows-gnu --lib --release --manifest-path=./rust/Cargo.toml#>              Updating crates.io index#>             Compiling winapi-build v0.1.1#>       Compiling winapi v0.3.9#>       Compiling winapi v0.2.8#>       Compiling proc-macro2 v1.0.27#>       Compiling unicode-xid v0.2.2#>       Compiling syn v1.0.73#>       Compiling extendr-engine v0.2.0#>       Compiling lazy_static v1.4.0#>             Compiling kernel32-sys v0.2.2#>             Compiling quote v1.0.9#>             Compiling extendr-macros v0.2.0#>             Compiling libR-sys v0.2.1#>             Compiling extendr-api v0.2.0#>             Compiling myextendr v0.1.0 (C:\Users\...\AppData\Local\Temp\RtmpAVW4HZ\file122c180d1953\myextendr\src\rust)#>              Finished release [optimized] target(s) in 33.09s#>      C:/rtools40/mingw64/bin/gcc -shared -s -static-libgcc -o myextendr.dll tmp.def entrypoint.o -L./rust/target/x86_64-pc-windows-gnu/release -lmyextendr -lws2_32 -ladvapi32 -luserenv -LC:/PROGRA~1/R/R-41~1.0/bin/x64 -lR#>      installing to C:/Users/.../AppData/Local/Temp/RtmpAVW4HZ/devtools_install_122c37bd1965/00LOCK-myextendr/00new/myextendr/libs/x64#>   -  DONE (myextendr)#> v Writing 'R/extendr-wrappers.R'.#> i Updating myextendr documentation#> i Loading myextendr#> Writing NAMESPACE#> Writing NAMESPACE#> Writing hello_world.Rdrextendr::document()#> i Generating extendr wrapper functions for package: myextendr.#> i 'R/extendr-wrappers.R' is up-to-date. Skip generating wrapper functions.#> i Updating myextendr documentation#> i Loading myextendr#> Writing NAMESPACE#> Writing NAMESPACEhello_world()#> [1] "Hello world!"

hello_world() написана на Rust и автоматически экспортируется в R. Обратите внимание, что hello_world.Rd был создан при вызове rextendr::document() (аналог devtools::document()). Дело в том, что rextendr-парсер воспринимает /// комментарии как R комментарии. Rust функция выглядит вот так

/// Return string `"Hello world!"` to R./// @export#[extendr]fn hello_world() -> &'static str {    "Hello world!"}

Что автоматически генерирует R обертку

#' Return string `"Hello world!"` to R.#' @exporthello_world <- function() .Call(wrap__hello_world)

и, как результат, обновляет документацию и NAMESPACE с помощью {roxygen2}.

Если этого мало

Здесь я хотел бы коротко описать последнюю важную фичу extendr. Крейт позволяет экспортировать не просто функции, а целые типы. Легким движением руки можно пробросить кастомный тип из Rust в R , а инстансы этого типа -- передавать в обе стороны как ссылки. Это позволяет заполучить ООП в R в традиционном (object-first) стиле, модицифируя in-place объекты, созданные и доступные из Rust:

rextendr::rust_source(code = "struct Counter {    n: i32,}#[extendr]impl Counter {    fn new() -> Self {        Self { n: 0 }    }        fn increment(&mut self) {        self.n += 1;    }        fn get_n(&self) -> i32 {        self.n    }}")#> i build directory: 'C:\Users\...\AppData\Local\Temp\RtmpWOu1pt\file5318783e2176'#> v Writing 'C:/Users/.../AppData/Local/Temp/RtmpWOu1pt/file5318783e2176/target/extendr_wrappers.R'.cntr <- Counter$new()cntr$get_n()#> [1] 0cntr$increment()cntr$increment()cntr$get_n()#> [1] 2

Вместо заключения

Статья получилась гораздо длиннее и сумбурней, чем я ожидал. Тем не менее, я не успел описать все возможности extendr. Этот проект амбициозный и еще далек от завершения, но я считаю, что давно пришло время добавить поддержку Rust в R, а главное сделать взаимодействие этих языков удобным. Мы осторожно надеемся, что в конечном итоге сможем добавить официальную поддержку Rust, на равне с C / C++. К сожалению, сейчас ее отсутствие накладывает на нас некоторые ограничения.

Отдельным вызовом было заставить эту систему работать на Windows. Мы столкнулись со множеством проблем, но на данный момент нам удалось справиться практически со всеми трудностями. Для запуска на Windows extendr требует стандартный Rust - тулчейн, stable-x86_64-pc-windows-msvc, с дополнительными целями (targets) x86_64-pc-windows-gnu и i686-pc-windows-gnu, а также Rtools40v2 (последняя версия на момент написания, отличается от Rtools40).

Скудную документацию можно найти здесь и в репозиториях проекта extendr.

Спасибо что дочитали до конца!