Дмитpий Hecтepук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Posts Tagged ‘reflection

Проект CallSharp: I/O Call Instrumentation на платформе .NET

4 комментария

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

callsharp_0_1_1

Сначала простой пример: у вас есть "abc", нужно получить "cba". Ниже я представил это схематично, и далее в статье я буду продолжать использовать такие заголовки.

ff0

Этот пример идеально иллюстрирует проблему, т.к. в .NET у строки нету метода Reverse(), и решений этой задачи – несколько. Например, можно написать вот так:

new string(input.Reverse().ToArray())

Следовательно, хотелось бы получить программу, которая сама выводила бы эти цепочки вызовов на основе входных и выходных данных, гуляя по .NET BCL API, делая все возмножные вызовы и проверяя их на соответствие. Звучит немного фантастично, да?

Давайте возьмем для начала простой пример:

ff1

В нашем случае abc – это точно строка, и ничто иное. Теперь нам предстоит понять что на abc можно вызвать чтобы получить ABC.

Нам повезло что строки в .NET немутабельны, и нам не нужно проверять изменения оригинальной строки после вызовов на ней – только выходного значения. А следовательно, мы можем взять и поискать все методы (а также свойства, которые в .NET тоже методы с приставкой get_), которые

  • Являются нестатическими методами класса string (System.String, если быть педантичными)

  • Могут не принимать ни одного аргумента

  • Возвращают строку

Примечательно, что «могут не принимать ни одного аргумента» – это три раздельных случая, а именно

  • Функция не имеет параметров вообще, т.е. Foo()

  • Функция может и имеет параметры, но у всех них есть дефолтные значения, т.е. Foo(int n = 0)

  • Функция берет упакованый список, т.е. Foo(params char[] letters)

Если руководствоваться этими критериями, мы получим список фунций string, которых было бы неплохо вызвать на строке "abc":

Normalize 
ToLower 
ToLowerInvariant 
ToUpper 
ToUpperInvariant 
ToString 
Trim
TrimStart
TrimEnd

Берем каждую из этих функций, вызываем на "abc", смотрим на результат. Подходят только две функции:

input.ToUpper()
input.ToUpperInvariant()

Ура, первая миссия выполнена!

ff2

Как понять, что за тип у числа 3 справа? Я предлагаю вот такой алгоритм:

  • Через reflection, берем все типы у которых есть метод TryParse().

  • Вызываем на всех данных. Если возвращает true – делаем боксинг распаршенного (неологизм?) объекта, возвращая его как object.

  • Не забываем, что любой ввод это как минимум string. А если ввод имеет длину 1, то это еще и char.

Согласно этому алгоритму, тройка (3) справа может быть и string и char (а также float или даже TimeSpan!), но в текущем примере, мы допустим что это все же Int32 или просто int.

Используя все тот же линейный поиск по нестатическим методам, мы моментально находим

input.Length

Естественно, что на самом деле это вызов функции get_Length(), но CallSharp заранее удаляет все ненужные декорации для удобства пользователя.

ff3

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

  • Не обязательно являются членами класса (в нашем случае – строки), но тем не менее попадают в список одобренных типов. Причина: я не хочу произвольно вызывать File.Delete(), например

  • Возвращают нужный нам тип (в данном случае – bool)

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

string.IsNullOrEmpty(input)
string.IsNullOrWhiteSpace(input)

Прекрасно! Давайте что-нибудь посложнее уже!

ff4

Ухх, тут ситуация посложнее – "abc ", то есть два пробела на конце: это одной функцией уже не получить. Надо делать цепочку вызовов. В данном случае цепочка не должна быть stringstringstring, она может быть stringчто угодноstring, т.к. промежуточные данные нам не важны.

Именно на этом этапе происходит комбинаторный взрыв. Ну, а что вы хотели? Зато мы на наших входных данных получаем очень много вариантов:

string.Concat(input.Split()).ToUpper()
string.Concat(input.Split()).ToUpperInvariant()
input.ToUpper().Trim()
input.ToUpper().TrimEnd()
input.ToUpperInvariant().Trim()
input.ToUpperInvariant().TrimEnd()
input.Trim().ToUpper()
input.Trim().ToUpperInvariant()
input.TrimEnd().ToUpperInvariant()
input.TrimEnd().ToUpper() // + lots more solutions

Я не стал выкладывать все решения, их достаточно много. Как видите, все варианты являются более-менее правильными, но не учтена коммутативность вызовов: ведь по сути не важно, вызывать нам .Trim().ToUpper() или .ToUpper().Trim(), но программа этого не знает.

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

ff5

Мы пока что обсуждали только «няшные» функции которые можно вызывать без аргументов. Всё – такое дело больше не прокатит. Чтобы удалить bbb на конце нужно вызвать что-то, что жестко выпиливает или b или bbb или удаляет 3 последние буквы в тексте.

Естественно, что все аргументы вызова должны как-то коррелировать с объектом, на котором идет вызов. Для этого сделан страшный и ужасный FragmentationEngine – класс-дробитель, который умеет дробить другие типы на составные части. (Тут должна быть картинка Дробителя из Hearthstone.)

Давайте возьмем строку aaabbb. Ее можно раздробить так:

  • Все возмоджные буквы (в данном случае – 'a' и 'b')

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

  • Все возможные числа в пределах длины самой строки. Это нужно для вызовов всяких Substring().

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

  • Вызовы с 2+ аргументами делают нехилый комбинаторный взрыв. Простой пример – это Substring().

  • Вызовы функций которые берут params[] теоретически создают ничем не ограниченный комбинаторный взрыв, поэтому их нужно или лимитировать или не вызывать вообще.

CallSharp, конечно, справляется с нашим синтетическим примером и выдает нам

input.Trim('b')
input.TrimEnd('b')

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

ff6

Хмм, казалось бы, нужно всего лишь удалить er ну или e и r по отдельности. Если запустить CallSharp на этом примере, мы получим

input.Trim('e','r')
input.Trim('r','e')
input.Trim('a','e','r')
input.Trim('a','r','e')
input.Trim('e','a','r')
input.Trim('e','r','a')
input.Trim('r','a','e')
input.Trim('r','e','a')
input.TrimEnd('e','r')
input.TrimEnd('r','e') 
// 30+ more options

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

ff7

Тут вариантов меньше, вот они:

input.Replace("aabb", "aa")
input.Replace("bb", "")
input.Replace("bbcc", "cc")

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

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

ff8

Тут можно просто удалить пробел, но CallSharp дает много вариантов, например

input.Replace(" ", string.Empty)
input.Replace(" b ", "b")
input.Replace("a b ", "ab")
input.Replace(" b c", "bc")
input.Replace("a b c", "abc")
// at greater depth,
string.Concat(input.Split())

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

Резюмируя

Сейчас CallSharp работает, скажем так, небыстро. Проблема в основном в использовании reflection (в частности, MethodInfo.Invoke()) а также в комбинаторных взрывах связанных с глубиной вызовов и количеством аргументов и их вариаций.

Текущие проблемы с перформансом отчасти решатся при переезде от динамического до статического reflection (предполагается сделать всё на T4). Оптимизаций можно делать очень много – я бы например хотел сделать аннотации для разметки «коммутативности» как наборов функций, так и аргументов в функциях (например, порядок букв в Trim() не важен).

CallSharp – open source проект, лежит на GitHub. Там же есть его релизы – по ссылке click here установится ClickOnce дистрибутив, которые самообновляется по мере выхода новых версий.

Для тех, кому хочется чуть более живого повествования, ниже представлен мой доклад на Петербургской .NET User Group:

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

Written by Dmitri

17 декабря 2016 at 14:34

Опубликовано в .NET

Tagged with ,