Wie funktioniert die Code-Vervollständigung?

84

Viele Editoren und IDEs haben Code-Vervollständigung. Einige von ihnen sind sehr "intelligent", andere nicht wirklich. Ich interessiere mich für den intelligenteren Typ. Ich habe zum Beispiel IDEs gesehen, die eine Funktion nur anbieten, wenn sie a) im aktuellen Bereich verfügbar ist, b) ihren Rückgabewert gültig ist. (Zum Beispiel bietet es nach "5 + foo [tab]" nur Funktionen, die etwas zurückgeben, das zu einer Ganzzahl oder zu Variablennamen des richtigen Typs hinzugefügt werden kann.) Ich habe auch gesehen, dass sie die am häufigsten verwendete oder längste Option vor sich haben der Liste.

Mir ist klar, dass Sie den Code analysieren müssen. Während der Bearbeitung des aktuellen Codes ist jedoch normalerweise eine Syntax fehlerhaft. Wie analysiert man etwas, wenn es unvollständig ist und Fehler enthält?

Es gibt auch eine zeitliche Beschränkung. Die Fertigstellung ist nutzlos, wenn es Sekunden dauert, eine Liste zu erstellen. Manchmal behandelt der Vervollständigungsalgorithmus Tausende von Klassen.

Was sind die guten Algorithmen und Datenstrukturen dafür?

Stribika
quelle
1
Eine gute Frage. Vielleicht möchten Sie sich den Code für einige der Open-Source-IDEs ansehen, die dies implementieren, z. B. Code :: Blocks unter codeblocks.org .
1
Hier ist der Artikel zum Erstellen der Code-Vervollständigung in C # Erstellen der Code-Vervollständigung in C #
Pritam Zope

Antworten:

64

Die IntelliSense-Engine in meinem UnrealScript-Sprachdienstprodukt ist kompliziert, aber ich werde hier so gut wie möglich einen Überblick geben. Der C # -Sprachendienst in VS2008 SP1 ist mein Leistungsziel (aus gutem Grund). Es ist noch nicht da, aber es ist schnell / genau genug, dass ich sicher Vorschläge machen kann, nachdem ein einzelnes Zeichen eingegeben wurde, ohne auf Strg + Leerzeichen zu warten oder der Benutzer einen .(Punkt) einzugeben . Je mehr Informationen Menschen [die an Sprachdiensten arbeiten] zu diesem Thema erhalten, desto besser ist die Erfahrung für Endbenutzer, sollte ich jemals ihre Produkte verwenden. Es gibt eine Reihe von Produkten, mit denen ich die unglückliche Erfahrung gemacht habe, dass ich nicht so genau auf Details geachtet habe. Infolgedessen habe ich mehr mit der IDE gekämpft als mit dem Codieren.

In meinem Sprachendienst ist es wie folgt aufgebaut:

  1. Holen Sie sich den Ausdruck am Cursor. Dies geht vom Anfang des Mitgliedszugriffsausdrucks bis zum Ende des Bezeichners, über dem sich der Cursor befindet. Der Mitgliedszugriffsausdruck liegt im Allgemeinen im Formular vor aa.bb.cc, kann jedoch auch Methodenaufrufe wie in enthalten aa.bb(3+2).cc.
  2. Holen Sie sich den Kontext um den Cursor. Dies ist sehr schwierig, da es nicht immer den gleichen Regeln wie der Compiler folgt (lange Geschichte), aber hier wird davon ausgegangen, dass dies der Fall ist. Im Allgemeinen bedeutet dies, dass die zwischengespeicherten Informationen zu der Methode / Klasse abgerufen werden, in der sich der Cursor befindet.
  3. Angenommen, das Kontextobjekt implementiert IDeclarationProvider, wo Sie aufrufen können GetDeclarations(), um eines IEnumerable<IDeclaration>der im Bereich sichtbaren Elemente anzuzeigen. In meinem Fall enthält diese Liste die lokalen / Parameter (wenn in einer Methode), Mitglieder (Felder und Methoden, nur statisch, außer in einer Instanzmethode, und keine privaten Mitglieder von Basistypen), Globale (Typen und Konstanten für die Sprache I. arbeite an) und Schlüsselwörtern. In dieser Liste befindet sich ein Element mit dem Namen aa. Als ersten Schritt bei der Bewertung des Ausdrucks in # 1 wählen wir das Element aus der Kontextaufzählung mit dem Namen aus aaund geben uns eine IDeclarationfür den nächsten Schritt.
  4. Als nächstes wende ich den Operator auf die IDeclarationDarstellung aaan, um eine andere zu erhalten, IEnumerable<IDeclaration>die die "Mitglieder" (in gewissem Sinne) von enthält aa. Da sich der .Operator vom ->Operator unterscheidet, rufe ich auf declaration.GetMembers(".")und erwarte, dass das IDeclarationObjekt den aufgelisteten Operator korrekt anwendet.
  5. Dies wird fortgesetzt, bis ich drücke cc, wo die Deklarationsliste ein Objekt mit dem Namen enthalten kann oder nichtcc . Wie Sie sicher wissen, sollten mehrere Elemente, die mit beginnen cc, ebenfalls angezeigt werden. Ich löse dieses Problem, indem ich die endgültige Aufzählung durch meinen dokumentierten Algorithmus leite , um dem Benutzer die hilfreichsten Informationen zu liefern.

Hier einige zusätzliche Hinweise für das IntelliSense-Backend:

  • Ich nutze die faulen Bewertungsmechanismen von LINQ bei der Implementierung in großem Umfang GetMembers. Jedes Objekt in meinem Cache kann einen Funktor bereitstellen, der für seine Mitglieder ausgewertet wird. Daher ist das Ausführen komplizierter Aktionen mit dem Baum nahezu trivial.
  • Anstatt dass jedes Objekt eines List<IDeclaration>seiner Mitglieder behält , behalte ich ein List<Name>, wobei Nameeine Struktur den Hash einer speziell formatierten Zeichenfolge enthält, die das Mitglied beschreibt. Es gibt einen riesigen Cache, der Objekten Namen zuordnet. Auf diese Weise kann ich beim erneuten Analysieren einer Datei alle in der Datei deklarierten Elemente aus dem Cache entfernen und mit den aktualisierten Mitgliedern neu füllen. Aufgrund der Konfiguration der Funktoren werden alle Ausdrücke sofort auf die neuen Elemente ausgewertet.

IntelliSense "Frontend"

Während der Benutzertyp ist die Datei häufiger syntaktisch falsch als korrekt. Daher möchte ich nicht willkürlich Teile des Caches entfernen, wenn der Benutzer tippt. Ich habe eine große Anzahl von Sonderfallregeln eingerichtet, um inkrementelle Aktualisierungen so schnell wie möglich durchzuführen. Der inkrementelle Cache wird nur lokal in einer geöffneten Datei gespeichert und stellt sicher, dass der Benutzer nicht merkt, dass der Backend-Cache durch seine Eingabe falsche Zeilen- / Spalteninformationen für Dinge wie die einzelnen Methoden in der Datei enthält.

  • Ein einlösender Faktor ist, dass mein Parser schnell ist . Es kann ein vollständiges Cache-Update einer 20000-Zeilen-Quelldatei in 150 ms verarbeiten, während es in einem Hintergrund-Thread mit niedriger Priorität in sich geschlossen arbeitet. Immer wenn dieser Parser eine geöffnete Datei erfolgreich (syntaktisch) durchläuft, wird der aktuelle Status der Datei in den globalen Cache verschoben.
  • Wenn die Datei syntaktisch nicht korrekt ist, verwende ich einen ANTLR-Filterparser (Entschuldigung für den Link - die meisten Informationen befinden sich auf der Mailingliste oder stammen aus dem Lesen der Quelle), um die gesuchte Datei zu analysieren:
    • Variablen- / Felddeklarationen.
    • Die Signatur für Klassen- / Strukturdefinitionen.
    • Die Signatur für Methodendefinitionen.
  • Im lokalen Cache beginnen Klassen- / Struktur- / Methodendefinitionen an der Signatur und enden, wenn die Verschachtelungsebene der Klammer wieder auf gerade zurückgesetzt wird. Methoden können auch enden, wenn eine andere Methodendeklaration erreicht wird (keine Verschachtelungsmethoden).
  • Im lokalen Cache werden Variablen / Felder mit dem unmittelbar vorhergehenden nicht geschlossenen Element verknüpft . Im folgenden kurzen Codeausschnitt finden Sie ein Beispiel dafür, warum dies wichtig ist.
  • Während der Benutzertypen führt ich außerdem eine Neuzuordnungstabelle, in der die hinzugefügten / entfernten Zeichenbereiche markiert sind. Dies wird verwendet für:
    • Stellen Sie sicher, dass ich den richtigen Kontext des Cursors identifizieren kann, da eine Methode in der Datei zwischen vollständigen Parsen verschoben werden kann / muss.
    • Stellen Sie sicher, dass Gehe zu Deklaration / Definition / Referenz Elemente in geöffneten Dateien korrekt findet.

Code-Snippet für den vorherigen Abschnitt:

class A
{
    int x; // linked to A

    void foo() // linked to A
    {
        int local; // linked to foo()

    // foo() ends here because bar() is starting
    void bar() // linked to A
    {
        int local2; // linked to bar()
    }

    int y; // linked again to A

Ich dachte, ich würde eine Liste der IntelliSense-Funktionen hinzufügen, die ich mit diesem Layout implementiert habe. Bilder von jedem finden Sie hier.

  • Automatische Vervollständigung
  • Tooltipps
  • Methodentipps
  • Klassenansicht
  • Code-Definitionsfenster
  • Browser aufrufen (VS 2010 fügt dies schließlich zu C # hinzu)
  • Semantisch korrekt Alle Referenzen suchen
Sam Harwell
quelle
Das ist großartig, danke. Ich habe beim Sortieren nie an die Groß- und Kleinschreibung gedacht. Mir gefällt besonders, dass Sie mit nicht übereinstimmenden Zahnspangen umgehen können.
Stribika
15

Ich kann nicht genau sagen, welche Algorithmen von einer bestimmten Implementierung verwendet werden, aber ich kann einige fundierte Vermutungen anstellen. Ein Trie ist eine sehr nützliche Datenstruktur für dieses Problem: Die IDE kann einen großen Trie im Speicher aller Symbole in Ihrem Projekt mit einigen zusätzlichen Metadaten an jedem Knoten verwalten.

Wenn Sie ein Zeichen eingeben, geht es einen Pfad in der Trie entlang. Alle Nachkommen eines bestimmten Trie-Knotens sind mögliche Vervollständigungen. Die IDE muss dann nur diejenigen herausfiltern, die im aktuellen Kontext sinnvoll sind, aber sie muss nur so viele berechnen, wie im Popup-Fenster zum Ausfüllen der Registerkarten angezeigt werden können.

Eine erweiterte Tab-Vervollständigung erfordert einen komplizierteren Versuch. Beispielsweise verfügt Visual Assist X über eine Funktion, mit der Sie nur die Großbuchstaben von CamelCase-Symbolen eingeben müssen. Wenn Sie beispielsweise SFN eingeben, wird das Symbol SomeFunctionNamein seinem Fenster zum Ausfüllen der Registerkarten angezeigt.

Für die Berechnung des Versuchs (oder anderer Datenstrukturen) muss der gesamte Code analysiert werden, um eine Liste aller Symbole in Ihrem Projekt zu erhalten. Visual Studio speichert dies in seiner IntelliSense-Datenbank, einer .ncbDatei, die neben Ihrem Projekt gespeichert ist, sodass nicht jedes Mal, wenn Sie Ihr Projekt schließen und erneut öffnen, alles neu analysiert werden muss. Wenn Sie zum ersten Mal ein großes Projekt öffnen (z. B. eines, das Sie gerade mit der Quellcodeverwaltung synchronisiert haben), nimmt sich VS die Zeit, um alles zu analysieren und die Datenbank zu generieren.

Ich weiß nicht, wie es mit inkrementellen Änderungen umgeht. Wie Sie sagten, wenn Sie Code schreiben, ist die Syntax in 90% der Fälle ungültig. Wenn Sie alles im Leerlauf reparieren, wird Ihre CPU mit einem sehr geringen Nutzen belastet, insbesondere wenn Sie eine von enthaltene Header-Datei ändern eine große Anzahl von Quelldateien.

Ich vermute, dass es entweder (a) nur dann repariert wird, wenn Sie Ihr Projekt tatsächlich erstellen (oder möglicherweise, wenn Sie es schließen / öffnen), oder (b) es eine Art lokales Parsen durchführt, bei dem der Code nur dort analysiert wird, wo Sie gerade sind in begrenzter Weise bearbeitet, nur um die Namen der relevanten Symbole zu erhalten. Da C ++ eine so außergewöhnlich komplizierte Grammatik hat, kann es sich in den dunklen Ecken merkwürdig verhalten, wenn Sie eine starke Metaprogrammierung für Vorlagen und dergleichen verwenden.

Adam Rosenfield
quelle
Der Versuch ist eine wirklich gute Idee. Bei den inkrementellen Änderungen kann es möglich sein, zuerst zu versuchen, die Datei erneut zu analysieren, wenn dies nicht funktioniert. Ignorieren Sie die aktuelle Zeile und wenn dies nicht funktioniert, ignorieren Sie den umschließenden {...} Block. Wenn alles andere fehlschlägt, verwenden Sie die letzte Datenbank.
Stribika