Wie würden Sie implementieren?: Viele Regeln über einen Baum in C#

Question

Ich habe eine Datenstruktur, die C#-Code wie folgt darstellt:

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;

... die ich mit einem einfachen Lexer/Parser-Kombination zu bauen. Ich muss den Baum durchlaufen und einen großen Satz von Regeln anwenden (mehr als 3000). Die Regeln werden ausgeführt, wenn sie auf verschiedene (und recht komplexe) Muster im Baum treffen. Zum Beispiel gibt es eine Regel, die ausgeführt wird, wenn eine Klasse nur Schnittstellen in derselben Assembly implementiert.

Meine ursprüngliche naive Implementierung iteriert über jede Regel, und dann durchläuft jede Regel den Baum auf der Suche nach ihrem spezifischen Muster. Das nimmt natürlich viel Zeit in Anspruch, selbst bei einer geringen Menge an Quellcode.

Man könnte dies mit der Funktionsweise von Antiviren-Software vergleichen, die komplexe Muster in einem großen Bestand an Binärcode erkennt.

Was würden Sie vorschlagen, wie man diese Art von Software implementiert?

EDT: Ich möchte nur hinzufügen: Nein, ich werde FxCop nicht neu implementieren.

Danke

Answer 1

Sie könnten versuchen, Ihre 3000 Regeln zusammenzufassen. Einige der 3000, so würde ich vermuten, gehen von einem anderen Mitglied der 3000 aus. Sagen wir, Regel 12 prüft 'eine Klasse implementiert eine Schnittstelle'. Regel 85 könnte lauten 'eine Klasse implementiert nur Schnittstellen in derselben Assembly'. Wenn Regel 12 fehlschlägt, muss Regel 85 überhaupt nicht ausgeführt werden.

Bei diesem Ansatz (Alpha-Beta Pruning) müssten Sie entweder Ihren Algorithmus umstrukturieren, um den Klassenbaum zu durchsuchen und dabei nach allen Regelmustern gleichzeitig zu suchen. Oder man müsste einen Datensatz speichern, der bei einem früheren Regeldurchlauf festgestellt hat, dass der aktuelle Regeldurchlauf irrelevant ist.

KOMMENTAR: Ich habe ein Konto der Stufe nub, kann also nicht direkt kommentieren. Können Sie ein Beispiel für vielleicht 2 weitere Regeln geben? Ich denke im Moment, dass Ihr Algorithmus 0(n*n) ist (folgendes kopiert von einem großen 0 Notation Beitrag)

O(n*log(n)): ein Algorithmus, der eine Art von "Teile und Herrsche"-Strategie anwendet. Schmerzt bei großem n. Typisches Beispiel: Merge Sort

O(n*n): eine verschachtelte Schleife irgendeiner Art. Schmerzt selbst bei kleinem n. Häufig bei naiven Matrixberechnungen. Sie sollten diese Art von Algorithmus möglichst vermeiden.

Answer 2

Ich würde in Erwägung ziehen, eine Art Repräsentation für Muster/Kontext zu erstellen und dann eine Hash-Map vom Muster zum Satz von Aktionen zu erstellen. Ohne mehr über Ihre Anforderungen zu wissen, ist es schwer, genauer zu sein, aber als Beispiel kann die Zeichenfolge "Namespace/Class" könnte ein Schlüssel zu einer Reihe von Aktionen sein, die von der Kenntnis des Namespaces und einer einzelnen Klasse, die er enthält, abhängen, "Class/Interface" könnte ein Schlüssel für die Menge der Aktionen sein, die sich auf eine einzelne Klasse und eine einzelne Schnittstelle beziehen, die sie implementiert, usw.

Der Algorithmus zur Durchquerung des Baums könnte seinen eigenen Kontext verfolgen (übergeordneter Knoten, aktueller Knoten usw.), einen Schlüssel auf der Grundlage seiner Position im Baum bilden, den Aktionssatz für diesen Schlüssel abrufen und dann alle diese Aktionen auslösen, wobei jeder eine Argumentstruktur gegeben wird, die die tatsächlichen Knoten entsprechend dem Schlüsselmuster bereitstellt.

Dies läuft darauf hinaus, eine spezielle Regelmaschine zu schaffen, die sich mit Regeln der Form "Wenn ich eine Klasse habe C und es implementiert eine Schnittstelle I , dann tun Sie ... mit C et I ".

Answer 3

@Jimmy McNulty

Das ist ein großartiger Ansatz. Alpha-Beta-Bereinigung nennen Sie das? Es geht darum, die Regeln so anzuordnen, dass, wenn eine versagt, andere ausgeschlossen werden. Habe ich Recht? Ich werde mir das mal ansehen.

Hier sind einige Beispiele für andere Regeln:

• Die Klasse ist endgültig und implementiert/erweitert keine Klasse außerhalb der Assembly.
• Die Methode ist virtuell, aber die Klasse ist privat oder intern.
• Klasse oder Methode hat ein bestimmtes Attribut.
• Die Methodenparameter sind zur Kompilierzeit bekannt.

Ich würde gerne etwas über andere Techniken erfahren, mit denen ich diese Art von Logik schneller/klüger ausführen kann.

Danke