Нашёл

#prog #rust #моё

Если вы хоть когда-то писали на Rust код, который имеет дело с окрестностями на квадратной сетке, то вы знали, как с этим неудобно работать. Индексы в Rust беззнаковые — просто прибавить 1 и -1 нельзя (впрочем, можно на nightly), проверить на отрицательный индекс после вычитания нельзя, так что логика по обработке нижних и верхних границ разная. Вдобавок, нужный код для соседних мест приходится писать по четыре раза, смешивая сугубо техническую логику обхода соседей и бизнес-логику.

Разве не было бы удобно, если бы мы просто могли получить список валидных индексов для соседей и уже итерироваться по нему? Конечно, можно. Вот только возникает вопрос, в чём именно возвращать индексы. В зависимости от размеров сетки, количество валидных соседей (неймановских) может быть любое от нуля до четырёх включительно. Казалось бы, напрашивается использовать вектор, но выделять память в куче для 8 usize — это как-то перебор, особенно с учётом того, что код для получения соседей наверняка будет в горячем цикле, где память выделять нежелательно. Можно, конечно, завести какой-нибудь small vec, который при малых размерах хранит на стеке вместо кучи, но... Оно нам точно надо? Можно ещё сделать мини-вектор на четыре элемента максимум из enum, но это такая куча бойлерплейта...

Несколько малоизвестно, что похожий вопрос дизайна API решён в std. У char есть метод encode_utf8, который принимает мутабельную ссылку на слайс байт, использует этот буфер, чтобы перевести char в закодированную в UTF-8 строку, и возвращает ссылку на строковой слайс. Да, переинтепретированные байтики из аргумента:

fn encode_utf8(self, dst: &mut [u8]) -> &mut str

Мы можем использовать похожий подход: принимать на вход ссылку слайс из пар индексов, заполнять нужную часть и возвращать ссылку на заполненную часть. На самом деле лучше даже принимать ссылку не на слайс, а на массив из четырёх элементов — нам точно этого хватит.

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

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

#[derive(Clone, Copy)]
struct Bounds {
rows: usize,
cols: usize,
}

Ну и начнём писать сам метод:

type Pos = (usize, usize);

impl Bounds {
fn around(
self,
buf: &mut [Pos; 4],
(row, col): Pos
) -> &[Pos] {
let mut i = 0;
...
}
}

Немного остановимся и подумаем, как будет выглядеть операция добавления индексов. Кажется, как-то так:

buf[i] = (new_row, new_col);
i += 1;

И так — для каждого из четырёх соседей... Нельзя ли покороче? Можно. Запишем замыкание:

let mut put = |r, c| {
buf[i] = (r, c);
i += 1;
}

Здесь принципиально то, что: а) замыкание не move, ибо нам buf и i ещё понадобятся, чтобы вернуть результат; б) замыкание должно быть мутабельным, чтобы позволить менять захваченные переменные. Что ж, приведу готовый метод целиком:

impl Bounds {
fn around(
self,
buf: &mut [Pos; 4],
(row, col): Pos
) -> &[Pos] {
let mut i = 0;
let mut put = |r, c| {
buf[i] = (r, c);
i += 1;
};
if let Some(row) = row.checked_sub(1) {
put(row, col);
}
if let Some(col) = col.checked_sub(1) {
put(row, col);
}
if col + 1 < self.cols {
put(row, col + 1);
}
if row + 1 < self.rows {
put(row + 1, col);
}
&buf[..i]
}
}

Аналогичный метод можно написать для окрестности Мура. И, кстати, такой код без non-lexical lifetimes не скомпилировался бы.

Вызывающий код будет выглядеть примерно так:

const BUF: [Pos; 4] = [(0, 0); 4];

// ⬇️ без этого компилятор будет выдавать предупреждение,
// поскольку берётся ссылка на временное значение,
// заданное константой, а не саму константу
#[allow(const_item_mutation)]
for i in 0..rows {
    for j in 0..cols {
        for &(row, col) in bounds.around(&mut BUF, (i, j)) {
            ...
        }
    }
}

У читателя может возникнуть резонный вопрос: а действительно ли сгенерированный код эффективный, нет ли там лишних паник? Проверка показывает, что при уровне оптимизации -O2 никаких паник в методе не остаётся. Оно и не удивительно: i не может стать больше четырёх, а у наc массив на четыре элемента как раз. Сила dataflow-анализа!

Как всегда, весь код в гисте.

Меня нарисовали. Приятно

#music

heavenpierceher.bandcamp.com/track/the-cyber-grind

(youtube.com/watch?v=e9EqU9y69vU)

Музыка, под которую хочется убивать.

(в чатике уже обсудили)

Допустим, вы запускаете в Linux процесс под рутом, которому нужно что-то прочитать или подключиться/забиндиться на сокет, а потом дропнуть привилегии до условного <nobody>/<nogroup>.

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

Итак, для смены пользователя текущего процесса мы вызываем libc::setuid(%uid_nobody%) (os.setuid в этом вашем питоне, nix::unistd::setuid в этом вашем расте и т.д.). Вызываем, понятно после смены группы, потому что если мы станем не рутом, то уже группу себе не сменим.

Так что сначала мы меняем группу. Как? Ну очевидно же что libc::setgid, как в миллионе каких-то примеров из гугла.

А вот и нихера.

libc::setgid не устанавливает процессу единую группу, а переключает её. В случае работы под рутом, вы можете выбрать любую группу, и она будет _добавлена_ в список групп процесса и выставлена по-умолчанию. Тоесть, если процесс был запущен как root:root, а вы вызвали libc::setgid(%gid_nogroup%), то процесс будет иметь обе группы - и nogroup (по-умолчанию) и root, а значит иметь право читать/писать всё в системе, куда имеет доступ группа root.

Как правильно?

Перед libc::setgid нужно обязательно вызвать libc::setgroups([%gid_nobody%]). Этот вызов выбрасывает у процесса все группы, кроме %gid_nobody% (добавляет её, если нет), но при этом процесс всё еще работает с gid=root(0). Далее, делаем libc::setgid. Потом libc::setuid. И всё работает как надо.

Тест для примера (пускать под рутом)

так права на группу остаются

echo "hello" > test.txt;chmod 640 test.txt
echo "import os; os.setgid(65534); os.setuid(65534);print(open('test.txt').read())"|python3

а так всё в порядке, доступа нет

echo "hello" > test.txt;chmod 640 test.txt
echo "import os;os.setgroups([65534]);os.setgid(65534);os.setuid(65534);print(open('test.txt').read())"|python3

PermissionError: [Errno 13]

А помните, был такой Клаб хауз?

Пост годичной давности:

Master — барская ветвь.
Slave — холопская ветвь.
Issue — донос.
Pull — арест / захват.
Push — продавить.
Stars — звезды на погонах.
Maintainer — гражданин начальник.
Contributor — кодо-обязанный
Release — амнистия.
Milestone — пятилетка.

via @shatrov_g

А теперь вот: tass.ru/obschestvo/14489179

(thanks @rusdacent)

My programming proverbs:

Short code is nice but not required.
Ensure preconditions are met.
No hungarian notation.
Delegate allocations to caller.

Narrow interfaces are preferable.
Universal solution is not always the most efficient.
Development is not only coding but communication.
Early exits are better.
Security can't be added retroactively.

#prog #rust #моё

Как скомпилировать задницу

В ASCII-символах можно составить стилизованное изображение ягодиц:

()()

(Или, если вы предпочитаете пошире, ( )( ))

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

Во-первых, можно, очевидно, считать это частью синтаксиса вызова функции. Тогда можно сделать возвращающую функцию функцию, вызвать её и вызвать результат:

fn func() -> fn() { || {} }

fn f() {
func()()
}

Во-вторых, можно сделать макрос, который проглотит вообще любой синтаксис, лишь бы он разбивался на токены Rust:

macro_rules! butt { ($a:tt $b:tt ) => {}; }

butt! {
()()
}

Но это всё уловки. Если же разбирать это, как отдельное выражение, то это unit, который вызван, как функция без аргументов. В принципе, этот синтаксис можно сделать валидным, если реализовать FnOnce() для (), но у нас нет такой возможности из-за orphan rule: трейт FnOnce определён в core (платформо-независимая часть стандартной библиотеки Rust), а () вообще является примитивным типом. Так что без шансов.

ИЛИ ВСЁ-ТАКИ МОЖНО? Нам мешается core — значит, избавимся от неё! Для этого нам понадобится фича no_core — странная, толком недокументированная и, скорее всего, навечно нестабильная. Её существование может показаться странной, но в ней есть смысл: в конце-концов, core не может зависеть от себя же.

Что ж, выпишем первые строчки:

#![feature(no_core)]
#![no_std] // std нам тоже не нужно
#![no_core]

Так как FnOnce определён в core, которую мы только что собственноручно отключили, нам придётся определить этот трейт самостоятельно. Разумеется, он не является обычным трейтом. Во-первых, его реализация включает столь нужный нам синтаксис вызова — неудивительно, что он является lang item. Просто так определить lang item мы не можем, нам понадобится ещё одна фича: собственно, lang_items. Во-вторых, единственный метод call_once определён со специальным ABI "rust-call". Само его использование требует дополнительной фичи unboxed_closures (название историческое, с тех времён, когда из-за отсутствия impl Trait не было возможности вернуть замыкание иначе, как кроме боксинга). Что ж, допишем код дальше:

#![feature(lang_items, unboxed_closures)]

#[lang = "fn_once"]
trait FnOnce<Args> {
#[lang = "fn_once_output"]
type Output;
extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

НО! У нас тут есть обобщённые аргументы, а значит, есть и неявное ограничение Sized. Значит, этот трейт нам тоже потребуется определить:

#[lang = "sized"]
pub trait Sized {}

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

impl FnOnce<()> for () {
type Output = ();
extern "rust-call" fn call_once(self, _: ()) -> () {}
}

Осталось только реализовать сидалище:

pub fn bottom() {
( )( )
}

О да, вот теперь оно компилируется. Код целиком:

#![feature(lang_items, no_core, unboxed_closures)]

#![no_std]
#![no_core]

#[lang = "sized"]
trait Sized {}

#[lang = "fn_once"]
trait FnOnce<Args: ?Sized> {
#[lang = "fn_once_output"]
type Output;
extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

impl FnOnce<()> for () {
type Output = ();
extern "rust-call" fn call_once(self, _: ()) -> () {}
}

pub fn bottom() {
( )( )
}

Извините, в этот раз без гиста.

В СМЫСЛЕ УЖЕ МАЙ

#article

Imposter Syndrome (в блоге inside Rust)

This is the most fundamental philosophy of both the Rust language and the Rust project: we don't think it's sufficient to build robust systems by only including people who don't make mistakes; we think it's better to provide tooling and process to catch and prevent mistakes.

#prog #itsec #article

Seriously, stop using RSA

https://elicit.org/

Крутой инструмент на базе ИИ: ищет релевантные статьи по запросу и выделяет в них ответы на заданный вопрос. Пока что бесплатно

#prog #rust #abnormalprogramming

Rust9x: Compile Rust code for Windows 95, NT and above

#prog #parsing #article

Faster general parsing through context-free memoization (pdf, thanks @zukaboo)

(thanks @grammarware, @GabrielFallen)

We present a novel parsing algorithm for all context-free languages. The algorithm features a clean mathematical formulation: parsing is expressed as a series of standard operations on regular languages and relations. Parsing complexity w.r.t. input length matches the state of the art: it is worst-case cubic, quadratic for unambiguous grammars, and linear for LR-regular grammars. What distinguishes our approach is that parsing can be implemented using only immutable, acyclic data structures. We also propose a parsing optimization technique called context-free memoization. It allows handling an overwhelming majority of input symbols using a simple stack and a lookup table, similarly to the operation of a deterministic LR(1) parser. This allows our proof-of-concept implementation to outperform the best current implementations of common generalized parsing algorithms (Earley, GLR, and GLL). Tested on a large Java source corpus, parsing is 3–5 times faster, while recognition—35 times faster.

Честно скажу, я прочитал по диагонали, но фактически алгоритм выглядит, как parsing with derivatives, но сделанный правильно.

Настроение: написать статью вместе с несколькими людьми под псевдонимом Norman Problem, чтобы на статью ссылались, как "N. Problem et al"