Как бы вы реализовали ?: Много правил над деревом в C #

Question

У меня есть структура данных, которая представляет код C #, например:

class Namespace:
    string Name;
    List<Class> Classes;

class Class:
    string Name;
    List<Property> Properties;
    List<Method> Methods;
    List<Method> Constructors;
    List<Field> Fields;
    List<Class> InnerClasses;
    Class Parent;
    List<Interface> Implements;

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

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

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

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

EDT: Просто хотел бы добавить: нет, я не перевоплощаю FxCop.

Спасибо

Answer 1

Вы можете попытаться объединить ваши 3000 правил. Некоторые из 3000 я бы предположил, предположим, что другой член 3000. Скажем, правило 12 проверяет «класс реализует интерфейс». Правило 85 может быть «класс реализует интерфейсы только в одной сборке». Если правило 12 не выполняется, нет необходимости запускать правило 85 вообще.

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

КОММЕНТАРИЙ: У меня есть учетная запись уровня nub, поэтому я не могу комментировать напрямую. Можете ли вы привести пример еще 2 правил? В настоящее время я думаю, что ваш алгоритм равен 0 (n * n) (следующий скопирован из большого сообщения с нотацией 0)

O (n * log (n)): алгоритм, который выполняет стратегию «разделяй и властвуй». Больно за большой н. Типичный пример: сортировка слиянием

O (n * n): некоторый вложенный цикл. Больно даже при маленьком п. Общее с наивными матричными вычислениями. Вы хотите избежать такого алгоритма, если можете.

Answer 2

@ Джимми МакНалти

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

Вот несколько примеров других правил:

• Класс является окончательным и не реализует / расширяет класс вне сборки.
• Метод является виртуальным, но класс является частным или внутренним.
• У класса или метода есть определенный атрибут.
• Параметр метода известен во время компиляции.

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

Спасибо

Answer 3

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

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

Это равносильно созданию механизма правил специального назначения, который работает с правилами вида "Если у меня есть класс C, и он реализует интерфейс I, тогда делайте ... с C и I».