Русский
Русский
English
Статистика
Реклама

Linq

LINQ на JavaScript для самых маленьких

15.08.2020 16:07:21 | Автор: admin

Шел очередной день самоизоляции, и я делал один из тех проектов для себя, которые мы забрасываем через пару дней после того как начали. Ну вы знаете, тот проект, который сделает вас знаменитым, позволит вам выучить новый ЯП, новый фреймворк и все такое. В общем, это был самый обычный день, самой обычной пандемии. Ничего не предвещало беды, пока одна библиотека, которой я пользовался для работы с массивами не выпала со stack overflow И вот тут-то все и запузырилось.


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


Почему LINQ?


Вкратце для тех, кто не в курсе:


LINQ (Language-Integrated Query) представляет простой и удобный язык запросов к источнику данных. В качестве источника данных может выступать объект, реализующий интерфейс IEnumerable (например, стандартные коллекции, массивы), набор данных DataSet, документ XML.

И LINQ позволяет делать вот так:


string[] teams = { "Бавария", "Боруссия", "Реал Мадрид", "Манчестер Сити", "ПСЖ", "Барселона" };var selectedTeams = teams.Where(t=>t.ToUpper().StartsWith("Б")).OrderBy(t => t);

Из особых преимуществ хотелось бы отметить:


  • Lazy-computation
  • Оптимизацию запросов
  • Удобная система методов расширения

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


Приступая к работе


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


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


  • Код должен быть легко-расширяемым
  • Код должен быть быстрым

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


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


В этой статье я расскажу как сделать несколько методов, потому что, если я буду описывать весь код, то эту портянку никто не будет читать.

Разберем мы:


  • Where
  • Sort
  • Min

Эти методы я, в общем-то, взял не с потолка:


  • Where мы рассмотрим как метод, который легко поддается оптимизации и его можно использовать для ленивых вычислений.
  • Sort как метод, который требует чтобы выражение до него было вычислено.
  • Min как пример агрегатной операции.

Приступим



Начнем с некоторых умозаключений:


  1. Мы хотим иметь методы расширения
  2. Методы расширения будут возвращать нам новые данные


На мой взгляд это очень похоже на паттерн Декоратор.


Если кратко, то схема классов должна быть такой:



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


export class Collection<T> implements ICollection<T> {    protected inner: Collection<T>;    private _computed: T[] | null = null; // Здесь мы с вами будем хранить уже посчитанный результат выражения, после того как коллекция "материализовалась"    public where(condition: FilterCondition<T>): ICollection<T> {        return new FilteringCollection<T>(this, condition);    }    public sort(condition?: CompareCondition<T> | undefined): ICollection<T> {        return new SortingCollection<T>(this, {            compare: condition        })    }    public min(predicate?: CompareCondition<T> | undefined): T {        return new MinAggregator(this, predicate).aggregate();    }    public toArray(): T[] {        return this.computed;    }    public [Symbol.iterator](): IterableIterator<T> {        return this.getIterator();    }    public getIterator(): IterableIterator<T> {        return this.computed[Symbol.iterator](); // По задумке, коллекция материализуется еще и в цикле for - of    }    private get computed(): T[] { // Ленивые вычисления: материализуем коллекцию только при вызове геттера        if (this._computed == null) {            const result = this.materialize();            Object.freeze(result);            this._computed = result;        }        return this._computed    }    protected materialize(): T[] { // Метод материализации коллекции        return this.inner.toArray();    }}

"В чем здесь декоратор?" спросите вы, а я вам отвечу: "Учите матчасть".


Допустим есть выражение:


const collection = new Collection([6, 5, 4, 3, 2, 1]);const result = collection.where(item => item % 2).sort(); // [1, 3, 5]

Разберем его по шагам, пусть:


        const collection = new Collection([6, 5, 4, 3, 2, 1]);/* 1) */const filtered = collection.where(item => item % 2);/* 2) */const sorted = filtered.sort();

1) Мы вызываем метод where у класса Collection, мы передаем ему ссылку на текущую коллекцию и записываем ее в поле inner.
2) Мы вызываем метод sort у класса FilteringCollection, мы передаем ему ссылку на текущую коллекцию и записываем ее в поле inner.


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


1) Вызовется materialize у FilteringCollection и вернется массив [5, 3, 1].
2) Вызовется materialize у SortingCollection и вернется массив [1, 3, 5].


Where


Реализация фильтрующего декоратора


export class FilteringCollection<T> extends Collection<T> {    public constructor(iterable: Collection<T> | T[], private condition: FilterCondition<T>) {        super(iterable);    }    public where(condition: FilterCondition<T>): ICollection<T> { // Перегрузка метода where        const that = this;        const result = new FilteringCollection<T>(this.inner, item => condition(item) && that.condition(item));        return result;    }    protected materialize(): T[] { // перегрузка метода материализации        return this.inner.toArray().filter(this.condition);    }}

Пояснение


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


Отдельно хотелось бы отметить, что данная реализация оптимизирует проход по цепочке из where:


То есть


_(cats).where(cat => cat.age < 3).where(cat => cat.age > 1).toArray()

будет преобразовано в


_(cats).where(cat => cat.age < 3 && (function(item){    return item.age > 1;}(cat))).toArray()

происходит эта оптимизация вот тут:


public where(condition: FilterCondition<T>): ICollection<T> { // Перегрузка метода where        const result = new FilteringCollection<T>(this.inner, item => condition(item) && this.condition(item)); // <-- тут        return result;    }

Мы просто отдаем в новый декоратор исходную коллекцию и подменяем выражение "сращенным".


В методе materialize у нас просто используется метод массива filter. Я выбрал его как самый простой и эффективный вариант для фильтрации. Все другое, что я пробовал проигрывало в производительности.


Поговорим о производительности
----------------------------------------------------Filter for 1000000:Where x 104 ops/sec 14.73% (61 runs sampled)Lodash filter x 609 ops/sec 0.67% (88 runs sampled)Native filter x 537 ops/sec 1.69% (85 runs sampled)Double where x 102 ops/sec 11.51% (64 runs sampled)Double lodash filter x 368 ops/sec 1.00% (88 runs sampled)Double native filter x 336 ops/sec 1.08% (84 runs sampled)10 where x 66.60 ops/sec 9.15% (59 runs sampled)10 lodash filter x 99.44 ops/sec 1.20% (73 runs sampled)10 native filter x 81.80 ops/sec 1.33% (70 runs sampled)----------------------------------------------------Filter for 1000:Where x 24,296 ops/sec 0.90% (88 runs sampled)Lodash filter x 60,927 ops/sec 0.90% (89 runs sampled)Native filter x 204,522 ops/sec 6.76% (87 runs sampled)Double where x 20,281 ops/sec 0.86% (90 runs sampled)Double lodash filter x 37,553 ops/sec 0.97% (90 runs sampled)Double native filter x 115,652 ops/sec 6.12% (91 runs sampled)10 where x 9,559 ops/sec 1.09% (87 runs sampled)10 lodash filter x 8,850 ops/sec 0.80% (87 runs sampled)10 native filter x 22,507 ops/sec 9.22% (84 runs sampled)----------------------------------------------------Filter for 10:Where x 1,788,009 ops/sec 0.81% (87 runs sampled)Lodash filter x 720,558 ops/sec 0.80% (84 runs sampled)Native filter x 14,917,151 ops/sec 0.61% (85 runs sampled)Double where x 1,257,163 ops/sec 0.52% (95 runs sampled)Double lodash filter x 456,365 ops/sec 0.74% (76 runs sampled)Double native filter x 8,262,940 ops/sec 0.64% (90 runs sampled)10 where x 489,733 ops/sec 0.67% (94 runs sampled)10 lodash filter x 135,275 ops/sec 0.61% (94 runs sampled)10 native filter x 1,350,316 ops/sec 0.94% (90 runs sampled)----------------------------------------------------

Коротко для ленивых: Наши побеждают, но только на коротких дистанциях.
Кстати такой расклад еще и с select (его реализацию вы можете увидеть в исходниках).


Sort


Реализация сортирующего декоратора


export class SortingCollection<T, V = T> extends Collection<T> implements ISortingCollection<T> {    private sortSettings: SortSettings<T, V>[];    public constructor(iterable: Collection<T>, ...sortSettings: SortSettings<T, V>[]) {        super(iterable);        this.sortSettings = _(sortSettings)        .where(item => !!item.compare || !!item.mapping) // Получаем правила маппинга полей и сортировку по ним        .toArray();    }    protected materialize(): T[] {        const comparer = new Comparer(this.sortSettings, this.defaultCompare);        return  Array.from(this.inner.toArray()).sort(this.sortSettings.length ? (first, second) => comparer.compare(first, second) : undefined);    }    private defaultCompare(first: V, second: V): number {        if(first < second) {            return -1        } else if (second < first) {            return 1        } else {            return 0;        }    }}

Пояснение


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


Отдельно бы хотелось отметить тот факт что Lodash, так же как и js изменяет исходный массив при сортировке.



Поговорим о производительности
----------------------------------------------------Sort for 1000000:Sort x 0.80 ops/sec 3.59% (6 runs sampled)Lodash sort x 0.97 ops/sec 27.98% (7 runs sampled)Native sort x 1.05 ops/sec 14.71% (7 runs sampled)SortBy x 0.19 ops/sec 10.31% (5 runs sampled)Lodash SortBy x 0.37 ops/sec 7.21% (5 runs sampled)Sort after map x 0.47 ops/sec 8.67% (6 runs sampled)----------------------------------------------------Sort for 1000:Sort x 1,121 ops/sec 0.77% (85 runs sampled)Lodash sort x 1,267 ops/sec 0.77% (89 runs sampled)Native sort x 1,274 ops/sec 0.88% (86 runs sampled)SortBy x 488 ops/sec 1.45% (80 runs sampled)Lodash SortBy x 549 ops/sec 9.60% (70 runs sampled)Sort after map x 954 ops/sec 1.50% (83 runs sampled)----------------------------------------------------Sort for 10:Sort x 171,700 ops/sec 1.38% (85 runs sampled)Lodash sort x 196,364 ops/sec 2.01% (80 runs sampled)Native sort x 250,820 ops/sec 0.96% (85 runs sampled)SortBy x 114,064 ops/sec 0.90% (86 runs sampled)Lodash SortBy x 86,370 ops/sec 17.93% (67 runs sampled)Sort after map x 221,034 ops/sec 1.31% (87 runs sampled)----------------------------------------------------

Все так же для ленивых:
одинаково.


Min


Реализация агрератора поиска минимального элемента


export class MinAggregator<T> extends ReduceAggregator<T> {    public constructor(collection: ICollection<T>, condition?: CompareCondition<T>) {        super(collection, condition ? (first, second) => this.compare(first, second, condition) : (a, b) => a < b ? a : b)    }    private compare(first: T, second: T, func: CompareCondition<T>): T {        return func(first, second) < 0 ? first : second;    }}export class ReduceAggregator<T> extends Aggregator<T> {    public constructor(private collection: ICollection<T>, protected predicate: ReduceCondition<T>){        super();    }    public aggregate(): T {        return this.collection.toArray().reduce((first, second) => this.predicate(first, second))    }}

Не ожидали? А декоратора не будет.


Вместо него у нас будет агрегатор.


Пояснение


Не уверен что оно вообще нужно, мы просто делаем свертку.


Поговорим о производительности
----------------------------------------------------Aggregate for 1000000:Min x 43.69 ops/sec 28.48% (65 runs sampled)Lodash Min x 117 ops/sec 0.58% (73 runs sampled)----------------------------------------------------Aggregate for 1000:Min x 61,220 ops/sec 5.10% (87 runs sampled)Lodash Min x 111,452 ops/sec 0.72% (90 runs sampled)----------------------------------------------------Aggregate for 10:Min x 3,502,264 ops/sec 1.36% (86 runs sampled)Lodash Min x 4,181,189 ops/sec 1.48% (86 runs sampled)----------------------------------------------------Aggregate By for 1000000 disp 50:Min By x 23.81 ops/sec 2.02% (42 runs sampled)Lodash Min By x 42.66 ops/sec 2.46% (55 runs sampled)----------------------------------------------------Aggregate By for 1000 disp 50:Min By x 43,064 ops/sec 0.71% (86 runs sampled)Lodash Min By x 60,212 ops/sec 0.89% (87 runs sampled)----------------------------------------------------Aggregate By for 100 disp 50:Min By x 351,098 ops/sec 1.03% (81 runs sampled)Lodash Min By x 382,302 ops/sec 1.39% (76 runs sampled)----------------------------------------------------

Lodash победил.


Итоги


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


Если кто знает как понизить стоимость итерации при фильтрации и маппинге, а именно вот тут:
this.inner.toArray().filter(this.condition);


то буду раз узнать ответ!

Открыт к критике, хочу сделать код лучше.


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


Репозиторий
Npm-пакет

Подробнее..
Категории: Javascript , Typescript , Js , Linq

Cоздание переиспользуемых Linq фильтров (построителей предикатов для Where), которые можно применять для разных типов

15.04.2021 22:17:49 | Автор: admin

Способ создания переиспользуемых Linq фильтров (построителей предикатов для условия Where), которые можно применять для разных типов объектов. Поля объектов для фильтрации указываются с помощью MemberExpression.

Способ подходит для Entity Framework, включая Async операции.

Основная идея. Что такое переиспользуемый фильтр?

Например есть приказы:

class Order { public DateTime Start { get; set; }public DateTime? End { get; set; }}

Пусть нужно найти все приказы которые будут действовать в ближайшие 7 дней.

С помощью переиспользуемого построителя фильтра (если бы он был реализован) найти приказы можно так:

var ordersFiltred = orders.WhereOverlap(// с помощью MemberExpressions// указываем по каким полям производить поискfromField: oo => oo.Start,toField: oo => oo.End,// указываем период поискаfrom: DateTime.Now,to: DateTime.Now.AddDays(7)).ToList();

Этот же WhereOverlap можно переиспользовать и применить к другому типу. Например, для поиска командировок:

class Trip { public DateTime? From { get; set; }public DateTime? To { get; set; }}
var tripsFiltred = trips.WhereOverlap(// с помощью MemberExpressions// указываем по каким полям производить поискfromField: oo => oo.From,toField: oo => oo.To,from: DateTime.Now,to: DateTime.Now.AddDays(7)).ToList();

Приказы и командировки - это разные типы объектов, у них нет общего интерфейса, поля для поиска называются по-разному. И все таки для обоих типов (и приказов и командировок) применяется один переиспользуемый фильтр WhereOverlap.

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

Как сделать переиспользуемый фильтр

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

Пусть есть выплаты и премии:

class Payout { public decimal Total { get; set; }public bool UnderControl { get; set; }}class Premium {public decimal Sum { get; set; }public bool RequiresConfirmation { get; set; }}

Сделаем переиспользуемый фильтр для поиска платежей больше определенной суммы:

class UnderControlPayFilter {readonly decimal Limit;public UnderControlPayFilter(decimal limit) {Limit = limit;}public Expression<Func<TEnt, bool>> Create<TEnt>(Expression<Func<TEnt, decimal>> sumField) {// GreaterOrEqual - нужно реализовать// GreaterOrEqual - это extension, который принимает//  - указание на поле (Expression sumField)//  - и значение с которым нужно сравнивать (Limit)return sumField.GreaterOrEqual(Limit);}}

Пример использования UnderControlPayFilter фильтра:

// фильтр поиска платежей требующих дополнительного контроля//// конкретный предел (здесь 1000) можно вынести в настройки,// а UnderControlPayFilter зарегистрировать в IoC-контейнере.// Тогда можно централизовано (через найстройки приложения)// управлять максимальным пределомvar underControlPayFilter = new UnderControlPayFilter(1000);//// Применение переиспользуемого фильтра для выплатvar payoutPredicate =underControlPayFilter.Create<Payout>(pp => pp.Total);// здесь, для упрощения, payouts - это массив,// в реальном приложении это может быть Entity Framework DbSet var payouts = new[] {new Payout{ Total = 100 },new Payout{ Total = 50, UnderControl = true },new Payout{ Total = 25.5m },new Payout{ Total = 1050.67m }}.AsQueryable().Where(payoutPredicate).ToList();//// Применение переиспользуемого фильтра для премийvar premiumPredicate =underControlPayFilter.Create<Premium>(pp => pp.Sum);// здесь, для упрощения, premiums - это массив,// в реальном приложении это может быть Entity Framework DbSet var premiums = new[] {new Premium{ Sum = 2000 },new Premium{ Sum = 50.08m },new Premium{ Sum = 25.5m, RequiresConfirmation = true },new Premium{ Sum = 1070.07m }}.AsQueryable().Where(premiumPredicate).ToList();

Все готово, осталось только реализовать GreaterOrEqual extension:

public static class MemberExpressionExtensions {    public static Expression<Func<TEnt, bool>> GreaterOrEqual<TEnt, TProp>(        this Expression<Func<TEnt, TProp>> field, TProp val)            => Expression.Lambda<Func<TEnt, bool>>(                Expression.GreaterThanOrEqual(field.Body, Expression.Constant(val, typeof(TProp))),                 field.Parameters);}

По аналогии можно реализовать extension-ы LessOrEqual, Equal, HasNoVal и другие.

Более сложные переиспользуемые фильтры с операторами И и ИЛИ

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

Дополним UnderControlPayFilter:

class UnderControlPayFilter {readonly decimal Limit;public UnderControlPayFilter(decimal limit) {Limit = limit;}public Expression<Func<TEnt, bool>> Create<TEnt>(Expression<Func<TEnt, decimal>> sumField,Expression<Func<TEnt, bool>> controlMarkField) {// PredicateBuilder нужно реализовать (см. ниже)return PredicateBuilder.Or(sumField.GreaterOrEqual(Limit),controlMarkField.Equal(true));}}

Пример использования:

// для выплатvar payoutPredicate =underControlPayFilter.Create<Payout>(sumField: pp => pp.Total,controlMarkField: pp => pp.UnderControl);// для премийvar premiumPredicate = underControlPayFilter.Create<Premium>(sumField: pp => pp.Sum,controlMarkField: pp => pp.RequiresConfirmation);

PredicateBuilder это A universal PredicateBuilder сделанный Pete Montgomery.

Заключение

Чтобы делать свои переиспользуемые фильтры, нужен только PredicateBuilder и MemberExpressionExtensions. Просто скопируйте их в свой проект. Переиспользуемые фильтры можно оформить как extension (как WhereOverlap), как статический хелпер или класс (как UnderControlPayFilter).

Я сделал парочку переиспользуемых фильтров - GitHub, NuGet (включает PredicateBuilder и MemberExpressionExtensions).

Подробнее..

Перевод Дерево синтаксиса и альтернатива LINQ при взаимодействии с базами данных SQL

24.10.2020 12:06:33 | Автор: admin


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


История из жизни разработчика


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


Раньше у них было что-то вроде этого:


А хотели они что-то такое:



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


CREATE PROCEDURE dbo.SomeContextUserFind    (@ContextId int, @Filter nvarchar(max)) ASBEGINDECLARE @sql nvarchar(max) =     N'SELECT U.UserId, U.FirstName, U.LastName    FROM [User] U    INNER JOIN [SomeContext] [C]      ON ....    WHERE [C].ContextId = @p1 AND ' + @Filter;EXEC sp_executesql     @sql,    N'@p1 int',    @p1=@ContextIdEND

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


string BuildFilter(IEnumerable<FilterItem> items){    var builder = new StringBuilder();    foreach (var item in items)    {        builder.Append(item.Field);        bool isLike = false;        switch (item.Operation)        {            case Operation.Equals:                builder.Append(" = ");                break;            case Operation.Like:                isLike = true;                builder.Append(" LIKE ");                break;            //...        }        builder.Append('\'');        if (isLike)            builder.Append('%');        builder.Append(Escape(item.Value));        if (isLike)            builder.Append('%');        builder.Append('\'');    }    return builder.ToString();}

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


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


В этот момент я вспомнил про абстрактное синтаксическое дерево, которое, очевидно, является лучшим выбором в данном случае, и далее я объясню, что это такое и как оно помогает.


Абстрактное синтаксическое дерево


Во-первых, давайте проанализируем строки фильтра, которые мы собираемся генерить, например вот эту:


[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Doe')

И здесь мы можем заметить некоторую структуру:



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


abstract class Expr{ }class ExprColumn : Expr{    public string Name;}class ExprStr : Expr{    public string Value;}abstract class ExprBoolean : Expr{ }class ExprEqPredicate : ExprBoolean{    public ExprColumn Column;    public ExprStr Value;}class ExprAnd : ExprBoolean{    public ExprBoolean Left;    public ExprBoolean Right;}class ExprOr : ExprBoolean{    public ExprBoolean Left;    public ExprBoolean Right;}

Используя классы, мы можем создать объект, который будет представлять исходный фильтр:


var filterExpression = new ExprAnd{    Left = new ExprEqPredicate    {        Column = new ExprColumn        {            Name = "FirstName"        },        Value = new ExprStr        {            Value = "John"        }    },    Right = new ExprOr    {        Left = new ExprEqPredicate        {            Column = new ExprColumn            {                Name = "LastName"            },            Value = new ExprStr            {                Value = "Smith"            }        },        Right = new ExprEqPredicate        {            Column = new ExprColumn            {                Name = "LastName"            },            Value = new ExprStr            {                Value = "Doe"            }        }    }};

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


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


<eqPredicate> ::= <column> = <str><or> ::= <eqPredicate>|or|<and> OR <eqPredicate>|or|<and><and> ::= <eqPredicate>|(<or>)|<and> AND <eqPredicate>|(<or>)|<and>

Примечание: Абстрактное означает, что синтаксис не описывает все детали языка, например, группирующие скобки, лишние пробелы и т. д.


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


Генерация SQL кода


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


Первый способ использовать сопоставление с образцом (Pattern Matching), что довольно просто:


var filterExpression = ...;StringBuilder stringBuilder = new StringBuilder();Match(filterExpression);void Match(Expr expr){    switch (expr)    {        case ExprColumn col:            stringBuilder.Append('[' + Escape(col.Name, ']') + ']');            break;        case ExprStr str:            stringBuilder.Append('\'' + Escape(str.Value, '\'') + '\'');            break;        case ExprEqPredicate predicate:            Match(predicate.Column);            stringBuilder.Append('=');            Match(predicate.Value);            break;        case ExprOr or:            Match(or.Left);            stringBuilder.Append(" OR ");            Match(or.Right);            break;        case ExprAnd and:            ParenthesisForOr(and.Left);            stringBuilder.Append(" AND ");            ParenthesisForOr(and.Right);            break;    }}void ParenthesisForOr(ExprBoolean expr){    if (expr is ExprOr)    {        stringBuilder.Append('(');        Match(expr);        stringBuilder.Append(')');    }    else    {        Match(expr);    }}

В результате в билдере будет следующая строка:


[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Joe')

Вроде это то, что нам нужно!


"Посетитель"


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


interface IExprVisitor{    void VisitColumn(ExprColumn column);    void VisitStr(ExprStr str);    void VisitEqPredicate(ExprEqPredicate eqPredicate);    void VisitOr(ExprOr or);    void VisitAnd(ExprAnd and);}

И любой объект (нашей структуры) может сделать выбор:


abstract class Expr{    public abstract void Accept(IExprVisitor visitor);}class ExprColumn : Expr{    public string Name;    public override void Accept(IExprVisitor visitor)        => visitor.VisitColumn(this);}class ExprStr : Expr{    public string Value;    public override void Accept(IExprVisitor visitor)        => visitor.VisitStr(this);}...

Теперь мы можем выделить генерацию sql кода в отдельный класс:


class SqlBuilder : IExprVisitor{    private readonly StringBuilder _stringBuilder         = new StringBuilder();    public string GetResult()        => this._stringBuilder.ToString();    public void VisitColumn(ExprColumn column)    {        this._stringBuilder            .Append('[' + Escape(column.Name, ']') + ']');    }    public void VisitStr(ExprStr str)    {        this._stringBuilder            .Append('\'' + Escape(str.Value, '\'') + '\'');    }    public void VisitEqPredicate(ExprEqPredicate eqPredicate)    {        eqPredicate.Column.Accept(this);        this._stringBuilder.Append('=');        eqPredicate.Value.Accept(this);    }    public void VisitAnd(ExprAnd and)    {        and.Left.Accept(this);        this._stringBuilder.Append(" AND ");        and.Right.Accept(this);    }    public void VisitOr(ExprOr or)    {        ParenthesisForOr(or.Left);        this._stringBuilder.Append(" OR ");        ParenthesisForOr(or.Right);    }    void ParenthesisForOr(ExprBoolean expr)    {        if (expr is ExprOr)        {            this._stringBuilder.Append('(');            expr.Accept(this);            this._stringBuilder.Append(')');        }        else        {            expr.Accept(this);        }    }    private static string Escape(string str, char ch)    {        ...    }}

И использовать его следующим образом:


var filterExpression = BuildFilter();var sqlBuilder = new SqlBuilder();filterExpression.Accept(sqlBuilder);string sql = sqlBuilder.GetResult();

В результате мы получаем желаемую строку:


[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Joe')

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


Обход дерева и круглые скобки


В этом алгоритме есть несколько аспектов, на которые следует обратить внимание.


Во-первых, как это вообще работает?


Фактически, здесь мы выполняем обход синтаксического дерева в глубину, и код sql является следом этого обхода:



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


Во-вторых, что происходит со скобками?


Дело в том, что логические выражения имеют определенный порядок вычисления. Операция И вычисляется первой, а операция ИЛИ второй. Скобки необходимы для изменения этой последовательности, поскольку любое выражение в скобках имеет более высокий приоритет при вычислении. Но в синтаксическом дереве последовательность оценки задается самой структурой (от ветвей до корня), поэтому отдельный тип для круглых скобок не требуется.


Расширение синтаксиса


В реальности нам конечно понадобятся и другие предикаты, например, NotEqual, и чтобы иметь возможность его (предикат) использовать, нам просто нужно добавить новый класс:


class ExprNotEqPredicate : ExprBoolean{    public ExprColumn Column;    public ExprStr Value;    public override void Accept(IExprVisitor visitor)        => visitor.VisitNotEqPredicate(this);}

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


public void VisitNotEqPredicate(ExprNotEqPredicate exprNotEqPredicate){    exprNotEqPredicate.Column.Accept(this);    this._stringBuilder.Append("!=");    exprNotEqPredicate.Value.Accept(this);}

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


Кстати, в документации по SQL Server есть все правила синтаксиса SQL, которые весьма полезны для подобного расширения:


Перегрузка операторов


Очевидно, что создание синтаксических деревьев путем вызова конструкторов классов это не самый удобный способ. Однако нам может помочь перегрузка оператора C#. Давайте сделаем следующее:


class ExprColumn : Expr{    ...    public static ExprBoolean operator==(ExprColumn column, string value)        => new ExprEqPredicate         {            Column = column, Value = new ExprStr {Value = value}        };    public static ExprBoolean operator !=(ExprColumn column, string value)        => new ExprNotEqPredicate        {            Column = column, Value = new ExprStr {Value = value}        };}abstract class ExprBoolean : Expr{    public static ExprBoolean operator &(ExprBoolean left, ExprBoolean right)        => new ExprAnd{Left = left, Right = right};    public static ExprBoolean operator |(ExprBoolean left, ExprBoolean right)        => new ExprOr { Left = left, Right = right };}

Теперь мы можем создать дерево синтаксиса очень простым и понятным способом:


ExprColumn firstName = new ExprColumn{Name = "FirstName"};ExprColumn lastName = new ExprColumn{Name = "LastName"};var expr = firstName == "John" & (lastName == "Smith" | lastName == "Doe");var builder = new SqlBuilder();expr.Accept(builder);var sql = builder.GetResult();

И результатом будет:


[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Doe')

Примечание: C# не допускает перегрузки операторов && и ||, и в этом есть смысл, поскольку эти операторы прекращают дальнейшую дальнейшее вычисление, если результат уже заранее известен (Например true || ....), но нам нужно вычислить все части для построения синтаксического дерева (результат будет выполняться базой данных SQL).


Что дальше


Кажется, мы решили проблему с фильтрацией, но как насчет сортировки и пейджинга? Также иногда необходимо добавить к оригинальному запросу какой-нибудь под-запрос (View или Derived Table) для фильтрации (или сортировки) по вычисляемым полям.


Не проблема! Давайте просто реализуем весь синтаксис SQL SELECT:


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


Альтернатива LINQ


То, что мы сделали с перегрузкой операторов, до некоторой степени напоминает выражения LINQ, и на самом деле тут есть некоторые сходства. Компилятор C# генерирует синтаксические деревья, а затем библиотеки, такие как Entity Framework или LINQ to SQL, преобразуют эти деревья в реальный код SQL.


Основная проблема этого подхода заключается в том, что компилятор генерирует синтаксическое дерево языка C#, а нам то нужен SQL! Отражение императивного C# в декларативный SQL это не простая задача, а результаты часто непредсказуемы.


Я предпочитаю другой подход вместо использования синтаксиса C# в качестве основы можно использовать настоящий синтаксис SQL. И вместо компилятора он может использовать перегрузку операторов, методы расширения и различные вспомогательные классы.


При таком подходе, с одной стороны, мы получаем почти такую же гибкость, как если бы мы использовали хранимые процедуры. С другой стороны, у нас строгая типизация, intellisense и бизнес-логика не перемещается в базу данных. И не нужно каждый раз гуглить, как выполнить LEFT JOIN в LINQ)


Еще одно преимущество заключается в том, что операторы обновления данных (INSERT, UPDATE, DELETE и даже MERGE) также могут быть реализованы таким же образом, и нет необходимости загружать тысячи записей из базы данных для обновления только одного столбца.


Просто пример того, что можно сделать, используя в качестве основы реальный синтаксис SQL (взято отсюда):


await InsertInto(tCustomer, tCustomer.UserId)    .From(        Select(tUser.UserId)            .From(tUser)            .Where(!Exists(                SelectOne()                    .From(tSubCustomer)                    .Where(tSubCustomer.UserId == tUser.UserId))))    .Exec(database);

Заключение


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


Link to SqExpress проект, который частично включает код из этой статьи.

Подробнее..
Категории: C , Sql , Net , Abstract syntax tree , Query builder , Linq , Linq to sql

Оживляем деревья выражений кодогенерацией

02.01.2021 00:07:07 | Автор: admin

Деревья выражений System.Linq.Expressions дают возможность выразить намерения не только самим кодом, но и его структурой, синтаксисом.

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

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

(бенчмарк)

Действие

Время, нс

Cached Compile Invoke

0.5895 0.0132 ns

Compile and Invoke

83,292.3139 922.4315 ns

Это особенно обидно, когда выражение простое, например содержит только доступ к свойству (в библиотеках для маппинга, сериализации, дата-байндинга), вызову конструктора или метода (для IoC/DI решений).

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

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

  • Встроенную интерпретацию.
    Необходимость использования интерпретатора вместо компилятора указывается соответствующим флагом:

    Expression.Compile(preferInterpretation: true)
    

    Происходит через рефлексию, но с накладными расходами на формирование стека инструкций.

    Для платформ Xamarin.iOS, Xamarin.watchOS, Xamarin.tvOS, Mono.PS4 и Mono.XBox стандартная компиляция через генерацию IL (System.Reflection.Emit) долгое время была недоступна и на данный момент под капотом всегда откатывается к этому варианту.

  • FastExpressionCompile от @dadhi.
    Ускоряет компиляцию за счет оптимизиpованной генерации IL и с меньшим количеством проверок совместимости.

    На платформах без поддержки JIT компиляции может использоваться только с включенным Mono Interpreter.

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

    Интерпретируя вручную, уже можно воспользоваться способами ускорения рефлексии. Самые эффективные из них, например Fasterflect, используют System.Reflection.Emit и на некоторых платформах так же могут требовать включения Mono Interpreter.

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

Компилировать выражения или какие-то их части во время написания кода (design-time) или сборки (compile-time).

Для compile-time компиляции делегатов к фрагментам деревьев выражений требуется сгенерировать соответствующий код.

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

От самого API требуется только давать нужный делегат по ключу, как в словаре. У интересующих нас фрагментов кода: методов, конструкторов и свойств на стыке run-time и compile-time естественный идентификатор это сигнатура. По ней генерируемый код будет класть делегаты в словарь, а клиенты забирать.

Например, для класса со свойством

namespace Namespace{  public class TestClass  {    public int Property { get; set; }  }}

используемым внутри System.Linq.Expressions.Expression<T> лямбды

Expression<Func<TestClass, int>> expression = o => o.Property;

делегатами чтения и записи в общем виде являются

Func<object, object> _ = obj => ((Namespace.TestClass)obj).Property;Action<object, object> _ => (t, m) => ((Namespace.TestClass)t).Property  = (System.Int32)m;

и генерируемый код для их регистрации будет примерно таким:

namespace ExpressionDelegates.AccessorRegistration{  public static class ModuleInitializer  {    public static void Initialize()    {      ExpressionDelegates.Accessors.Add("Namespace.TestClass.Property",        getter: obj => ((Namespace.TestClass)obj).Property,        setter: (t, m) => ((Namespace.TestClass)t).Property = (System.Int32)m);    }  }}

Генерация

Наиболее известные решения для кодогенерации, на мой взгляд, это:

Отдельная область применения есть у каждого решения, и только Roslyn Source Generators умеет анализировать исходный C# код даже в процессе его набора.

Кроме того, именно Roslyn Source Generators видятся более или менее стандартом для кодогенерации, т. к. были представлены как фича основного компилятора языка и используют Roslyn API, используемый в анализаторах и code-fix.

Принцип работы Roslyn Source Generators описан в дизайн-документе (местами не актуален!) и гайде.

Вкратце: для создания генератора требуется создать реализацию интерфейса

namespace Microsoft.CodeAnalysis{  public interface ISourceGenerator  {    void Initialize(GeneratorInitializationContext context);    void Execute(GeneratorExecutionContext context);  }}

и подключить ее к проекту как анализатор.

Метод Initialize пригодится для выполнения какой-либо единоразовой логики. GeneratorInitializationContext на данный момент может быть полезен только для подключения посетителя узлов синтаксиса кода.

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

Для каждого файла исходного кода Roslyn предоставляет синтаксическое дерево в виде объекта SyntaxTree:

GeneratorExecutionContext.Compilation.SyntaxTrees

а так же семантическую модель:

semanticModel =  GeneratorExecutionContext.Compilation.GetSemanticModel(SyntaxTree)

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

Среди всех узлов синтаксических деревьев сборки нам нужно найти только интересующие нас лямбда-выражения типа System.Linq.Expressions.Expression<T> и отобрать из их узлов-потомков выражения, описывающие доступ к членам классов, создание объектов и вызов методов:

По семантике узла, так называемому символу (Symbol), можно определять:

  • типы, используемые выражением;

  • область видимости;

  • IsStatic, IsConst, IsReadOnly и другие характеристики.

На основе такой информации и будем генерировать подходящий код.

В Roslyn API (Microsoft.CodeAnalysis) построить сигнатуру намного проще, чем c API рефлексии (System.Reflection). Достаточно сконвертировать символ в строку при помощи методаISymbol.ToDisplayString(SymbolDisplayFormat) c подходящим форматом:

Зная сигнатуры свойства/поля, его типа и обладателя формируем строки для добавления делегатов:

Оформляем код добавления делегатов в класс и отдаем компилятору:

var sourceBuilder = new StringBuilder(@"namespace ExpressionDelegates.AccessorRegistration{  public static class ModuleInitializer  {    public static void Initialize()    {");      foreach (var line in registrationLines)      {        sourceBuilder.AppendLine();        sourceBuilder.Append(' ', 6).Append(line);      }      sourceBuilder.Append(@"    }  }}");GeneratorExecutionContext.AddSource(  "AccessorRegistration",  SourceText.From(sourceBuilder.ToString(), Encoding.UTF8));

Этот код обязательно будет добавлен в сборку ...если генератор сможет отработать :)

Дело в том, что хоть Source Generators технически и не фича языка, поддерживаются они только в проектах с C# 9+. Позволить такую роскошь без костылей и ограничений на данный момент могут только проекты на .NET 5.

Совместимость

Поддержку Roslyn Source Generators API для .NET Standard, платформ .NET Core, .NET Framework и даже Xamarin поможет организовать Uno.SourceGeneration.

Uno.SourceGeneration предоставляет собственные копии интерфейса ISourceGenerator и атрибута [Generator], которые при миграции на С# 9 меняются на оригинальные из пространства имен Microsoft.CodeAnalysis простым удалением импортов Uno:

using Uno.SourceGeneration;using GeneratorAttribute = Uno.SourceGeneration.GeneratorAttribute;using ISourceGenerator = Uno.SourceGeneration.ISourceGenerator;
Для подключения достаточно добавить несколько строк в файл проекта.

В проект, где генератор будет использоваться:

<ItemGroup>  <SourceGenerator Include="PATH\TO\GENERATOR.dll" /></ItemGroup>

Например, распространяя генератор через nuget, подключение можно осуществлять вложением MSBuild props файла со следующим путём:

Инициализация

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

Для этих целей отлично подходит Module Initializer. Это конструктор сборки (а точнее ее модуля), который запускается сразу после ее загрузки и до вызовов к остальному коду. Он давно есть в CLR, но к сожалению, в C# его поддержка c атрибутом [ModuleInitializer] добавлена только в 9 версии.

Решение по добавлению конструктора в сборку с более широкой поддержкой платформ есть у Fody плагин Fody.ModuleInit. После компиляции добавляет классы с именами ModuleInitializer в конструктор сборки. В такой класс и будем оборачивать инициализацию сгенерированных делегатов.

Подключение Fody.ModuleInit через MSBuild свойства вместо FodyWeavers.xml исключит конфликты с другими Weaver-ами Fody в проекте клиента.

Использование

Таким образом, при сборке проекта:

  1. Source Generator добавит в сборку код, регистрирующий делегаты для деревьев выражений, в обертке класса ModuleInitializer.

  2. Fody.ModuleInit добавит ModuleInitializer в конструктор сборки.

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

Проверяем:

Expression<Func<string, int>> expression = s => s.Length;MemberInfo accessorInfo = ((MemberExpression)expression.Body).Member;Accessor lengthAccessor = ExpressionDelegates.Accessors.Find(accessorInfo);var length = lengthAccessor.Get("17 letters string");// length == 17

При декомпиляции сборки видно, что сгенерированный код и инициализатор модуля на месте:

Бенчмарки

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

Действие

Время, нс

Вызов простого делегата конструктора

4.6937 0.0443

Вызов сгенерированного делегата конструктора

5.8940 0.0459

Поиск и вызов сгенерированного делегата конструктора

191.1785 2.0766

Компиляция выражения и вызов конструктора

88,701.7674 962.4325

Вызов простого делегата доступа к свойству

1.7740 0.0291

Вызов сгенерированного делегата доступа к свойству

5.8792 0.1525

Поиск и вызов сгенерированного делегата доступа к свойству

163.2990 1.4388

Компиляция выражения и вызов геттера

88,103.7519 235.3721

Вызов простого делегата метода

1.1767 0.0289

Вызов сгенерированного делегата метода

4.1000 0.0185

Поиск и вызов сгенерированного делегата метода

186.4856 2.5224

Компиляция выражения и вызов метода

83,292.3139 922.4315

Полный вариант таблицы, с бенчмарками интерпретации.

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

Flame-график бенчмарка поиска и вызова сгенерированного делегата доступа к свойствуFlame-график бенчмарка поиска и вызова сгенерированного делегата доступа к свойству

Идеи насчёт оптимизации построения сигнатур по System.Reflection.MemberInfo приветствуются. Реализация на момент написания.

Заключение

По итогу получилось современное решение для кодогенерации с актуальной совместимостью и автоматической инициализацией.

Полный код можно посмотреть на: github/ExpressionDelegates, а подключить через nuget.

Для тех, кто будет пробовать Source Generators хотелось бы отметить несколько полезностей:

  • Source Generator Playground (github).
    Позволяет экспериментировать с Roslyn Source Generators в браузере, онлайн.

  • Окно визуализации синтаксиса для Visual Studio.
    Удобный инструмент для знакомства с Roslyn Syntax API на собственном коде.

  • Отлаживается Source Generator вызовом отладчика из его кода. Пример.
    Для этого нужен компонент Visual Studio Just-In-Time debugger и включенная настройка Tools -> Options -> Debugging -> Just-In-Time Debugging -> Managed.

  • В сгенерированных *.cs файлах срабатывают брейкпоинты, проверено в Visual Studio16.8.
    При генерации через Uno.SourceGeneration файлы размещаются по пути: \obj\{configuration}\{platform}\g\.
    С Roslyn Source Generators их появление включается через MSBuild свойство EmitCompilerGeneratedFiles.
    Стандартный путь: \obj\{configuration}\{platform}\generated\, переопределяется в свойстве CompilerGeneratedFilesOutputPath.

  • Source Generators можно конфигурировать свойствами MSBuild.
    При использовании Uno.SourceGeneration значение получают вызовом

    GeneratorExecutionContext.GetMSBuildPropertyValue(string)
    

    Для Roslyn Source Generators требуемые свойства необходимо сперва отдельно обозначить в MSBuild группе CompilerVisibleProperty и только после вызывать:

    GeneratorExecutionContext.AnalyzerConfigOptions.GlobalOptions  .TryGetValue("build_property.<PROPERTY_NAME>", out var propertyValue)
    
  • Из генератора можно кидать предупреждения и ошибки сборки.

    //Roslyn Source GeneratorsGeneratorExecutionContext.ReportDiagnostic(Diagnostic)//Uno.SourceGeneration:GeneratorExecutionContext.GetLogger().Warn/Error().
    
Подробнее..

Когда программисту нечего делать или оптимизируем код при помощи Linq.Expression

16.01.2021 22:14:09 | Автор: admin

Так сложилось, что активно кодировать мне не удается уже лет пять. Так что каждый шанс залезть в код и напакостить там товарищам воспринимается с радостью, как возможность тряхнуть стариной и убедиться что есть еще ягоды в ягодицах (ака шило в жопе).Да, и сразу оговорюсь, что статья скорее туториал, не из серии "смотрите ух как круто я могу", а из серии "о, какой удачный вариант показать на простом примере применение технологии, которая у некоторых коллег вызывает затруднения". Моё глубокое убеждение что подобные решения должны входить в арсенал любого разработчика на C#.

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

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

Линейный поиск в таблице - 0.6ms
Линейный поиск цепочкой if-return - 0.1ms
Поиск делением пополам - 0.08ms
Поиск словарем - 0.018ms

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

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

И тут как раз возник тот самый момент чешутся ручки, и совпало два фактора - во-первых, я большой поклонник data-driven архитектур, уже лет 20 как. А во-вторых .NET предоставляет совершенно уникальные средства для построения кода на лету. Так почему бы не попробовать построить цепочку операторов if для двоичного поиска из таблицы, и сделать это в виде Linq выражения? А ничего не препятствует, на самом деле. А главное, что та же логика потом хорошо подойдет для того, чтобы просто сгенерить код табличной функции для более примитивной архитектуры микроконтроллера.

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

Начнем с оператора if, который проверяет попадание значения в диапазон и возвращает коэффициент, если мы попали. Код очень простой - функция получает параметры range (диапазон), коэффициент, который надо вернуть (value), ссылку на исходное значение (v) и ссылку на точку возврата.Функция строит, соответственно, три Linq элемента - оператор возврата, условие для if и сам if. Получается аналог конструкции
If (v >= from && v < to) return value;

public Expression CreateSimpleIf(double from, double to,                       double value,                       Expression v, LabelTarget returnTarget){    var returnStmt = Expression.Return(      returnTarget,       Expression.Constant(value));    var ifCondition = Expression.AndAlso(        Expression.GreaterThanOrEqual(v, Expression.Constant(from)),         Expression.LessThan(v, Expression.Constant(to)));    return Expression.IfThen(ifCondition, returnStmt);}

Теперь построим цепочку операторов для массива диапазонов. Я отдельно обрабатываю ситуации в 1 и 2 элемента, это необязательно, но у меня чисто рефлекс чуть-чуть, но ускорить код там, где можно.

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

Получается аналог конструкции

If (v >= mid.from && v < mid.to) return mid.value
If (v < mid.from)
return search in (0...mid-1)
else
return search in (mid + 1...length - 1);

Span используется что бы избежать пересоздания массивов/списков в которых хранятся коэффициенты и/или чтобы не таскать за собой два дополнительных параметра начало диапазона в таблице для поиска и конец диапазона в таблице для поиска.

public Expression CreateSpanExpression(Span<Coefficient> span,           Expression v,           LabelTarget returnTarget){    if (span.Length == 1)        return CreateSimpleIf(span[0].RangeFrom,                    span[0].RangeTo,                    span[0].Value,                    v, returnTarget);    else if (span.Length == 2)    {        Expression[] ifs = new Expression[2];        ifs[0] = CreateSimpleIf(span[0].RangeFrom,                    span[0].RangeTo,                    span[0].Value,                    v, returnTarget);        ifs[1] = CreateSimpleIf(span[1].RangeFrom,                    span[1].RangeTo,                    span[1].Value,                    v, returnTarget);        return Expression.Block(ifs);    }    else    {        int mid = span.Length / 2;        Expression[] blocks = new Expression[2];        blocks[0] = CreateSimpleIf(span[mid].RangeFrom,                        span[mid].RangeTo,                        span[mid].Value,                        v, returnTarget);        var leftSide =           CreateSpanExpression(span.Slice(0, mid),                                v, returnTarget);        var rightSide =           CreateSpanExpression(span.Slice(mid + 1,                                span.Length - mid - 1),                                v, returnTarget);        Expression condition =           Expression.LessThan(v,                               Expression.Constant(span[mid].RangeFrom));        blocks[1] = Expression.IfThenElse(condition, leftSide, rightSide);        return Expression.Block(blocks);     }} 

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

public Func<double, double> CreateBTReeExpression(){    var value = Expression.Parameter(typeof(double), "value");    var returnTarget = Expression.Label(typeof(double));    var ifs = CreateSpanExpression(mCoefficients.ToArray(),                                    value, returnTarget);    var body = Expression.Block(typeof(double),                  new Expression[]                  {                    ifs,                    Expression.Label(returnTarget,                      Expression.Constant(0.0))                 });    var expression = Expression.Lambda(typeof(Func<double, double>),                        body,                        new ParameterExpression[] { value });    var functionDelegate = expression.Compile();    return (Func<double, double>) functionDelegate;        }

Ок, проверяем, а стоило ли оно хлопот? По замерам у меня получилось 0.012ms, или в 1.5 раза быстрее использования Dictionary. Ну и плюс появившаяся возможность легко адаптировать код для генерация исходного кода функции для микроконтроллера.

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

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

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

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

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

Подробнее..
Категории: C , Net , Linq , Compilation

Перевод IQueryable порождает сильную связанность

23.02.2021 20:21:55 | Автор: admin

Время от времени я встречаю людей, пытающихся выразить API в терминах IQueryable<T>. Почти всегда это плохая идея. В этой статье я объясню почему. В кратце, IQueryable<T> это один из лучших примеров заголовочного интерфейса (Header Interface), предлагаемых платформой .NET. Его почти невозможно реализовать полностью.


Эта статья о проблемах реализации API на основе интерфейса IQueryable<T>. Это не претензия к интерфейсу как таковому. Кроме этого, это не претензия к замечательным методам LINQ, доступным для интерфейса IEnumerable<T>.

Можно сказать, что IQueryable<T> это одно сплошное нарушение принципа подстановки Лисков. Я буду использовать закон Постела, чтобы объяснить почему это так.


Принцип устойчивости, также известен как закон Постела в честь Джона Постела: Будь либерален к тому, что принимаешь, и консервативен к тому, что отсылаешь (Be liberal in what you accept, and conservative in what you send).

Использование IQueryable<T>


Первая часть закона Постела применительно к проектированию API гласит о том, что API должен быть либеральным по отношению к тому, что принимает. Иными словами, мы говорим о входных параметрах. Таким образом, API, принимающий IQueryable<T> может выглядеть следующим образом:


IFoo SomeMethod(IQueryable<Bar> q);

Достаточно ли либеральные требования этого API? Определенно, нет. Такой интерфейс требует от вызывающего кода передать реализацию IQueryable<Bar>. Согласно принципу подстановки Лисков программа должна оставаться корректной для всех реализаций интерфейса. Это относится как к реализации IQueryable<Bar>, так и к реализации SomeMethod.


Важно понимать основное назначение IQueryable<T>: интерфейс спроектирован для использования в связке с поставщиками запросов (Query Provider). Иными словами, это не просто последовательность экземпляров класса Bar, которую можно отфильтровать или преобразовать к последовательности другого типа. Нет, это выражение, предназначенное для трансляции в запрос к какому-то источнику данных, чаще всего, к SQL. Это довольно серьезное требование для вызывающего кода.


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


Такие требования могли бы быть представлены гораздо проще, без того, чтобы предъявлять значительные требования к клиенту. В обоих случаях, мы могли бы использовать специализированные Query Objects или, даже проще, просто создать набор специализированных методов.


Для фильтрации


IFoo FindById(int fooId);

IFoo FindByCorrelationId(int correlationId);

Для постраничного вывода


IEnumerable<IFoo> GetFoos(int page);

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


IQueryable<T> в качестве результата


Вторая часть закона Постела гласит о том, что API должен быть консервативен в том, что он отправляет. Другими словами, метод должен гарантировать, что возвращаемые им данные строго соответствуют контракту между вызывающей стороной и реализацией. Метод, возвращающий IQueryable<T> может выглядеть следующим образом:


IQueryable<Bar> GetBars();

При разработке API большая часть контракта определяется интерфейсом (или базовым классом). Таким образом, тип возвращаемого значения метода определяет консервативную гарантию в плане возвращаемых данных. Таким образом, в случае возврата IQueryable <Bar> метод гарантирует, что он вернет полную реализацию IQueryable <Bar>.


Это консервативно? Вызывая LSP, потребитель должен иметь возможность делать все, что разрешено IQueryable<Bar>, не влияя на корректность программы. Это весьма серьезное обещание. Кто сможет его выполнить?


Существующие реализации


Реализация IQueryable<T> огромная задача. Если вы мне не верите, просто взгляните на серию публикаций Создание поставщика IQueryable на сайте Microsoft. Интерфейс настолько гибкий и выразительный, что, за одним исключением, всегда можно написать запрос, который данный провайдер не может перевести.


Вы когда-нибудь работали с Entity Framework или другим ORM и получали NotSupportedException? Многие люди получали. Фактически, за одним исключением, я твердо убежден, что все существующие реализации нарушают LSP. Я даже готов отправить бесплатную копию своей книги первому читателю, который укажет мне на реальную, общедоступную реализацию IQueryable<T>, которая может принять любое выражение, которое я ей скормлю.

Кроме того, набор функций, поддерживаемых каждой реализацией, варьируется от поставщика запросов к поставщику запросов. Выражение, которое может быть переведено Entity Framework, может не работать с поставщиком запросов Microsoft OData. Единственная реализация, которая полностью реализует IQueryable<T>, это реализация в памяти (и ссылка на нее не принесет вам бесплатной книги). По иронии судьбы эту реализацию можно рассматривать как реализацию Null Object, и она идет вразрез с предназначением интерфейса IQueryable<T>, именно потому, что он не переводит выражение на другой язык.


Почему это важно


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


Такой интерфейс дает ложные гарантии:


public interface IRepository{    IQueryable<T> Query<T>();}

Согласно LSP и закону Постела, это, казалось бы, гарантирует, что вы можете написать любое выражение запроса (независимо от его сложности) для возвращаемого экземпляра, и оно всегда будет работать. На практике этого никогда не происходит. Программисты, определяющие такие интерфейсы, неизменно имеют в виду конкретную ORM, и они неявно стремятся оставаться в пределах, которые, как они знают, безопасны для этой конкретной ORM. Это дырявая абстракция.
Если вы имеете в виду конкретный ORM, скажите об этом прямо. Не прячьте его за интерфейс. Это создает иллюзию того, что вы можете заменить одну реализацию другой. На практике это невозможно. Представьте, что вы пытаетесь заменить источник данных с SQL на Event Store.


Торт это ложь.



Подробнее..
Категории: C , Net , Linq , Tight coupling , Iqueryable , Query provider

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru