Lonestar, es müssen mehrere Probleme gelöst werden: Du musst den Kontext der angeforderten Vervollständigung im Editor und Programm erkennen und du musst einen kompletten Überblick über alle Möglichkeiten haben und daraus die Vervollständigungsliste bilden. Für den Überblick brauchst du ein Repository, das ständig aktuell gehalten werden muss. Des weiteren willst du mögliche Vervollständigungen "intelligent" priorisieren. Der Editor muss dabei das wenigste Tun. Die Verwaltung des Repositories und das Verständnis der Programme scheint mir das größere Problem.
Wäre die Programmiersprache vollständig deklarativ und auch noch statisch typisiert, wäre es vergleichsweise einfach, ein solches Repository zu erstellen und aktuell zu halten. Leider ist Python weder das eine noch das andere. Auch den Kontext in einem nun statischen Stück Code zu finden wäre vergleichsweise einfach.
Betrachten wir daher zuerst eine idealisierte Programmiersprache:
Code: Alles auswählen
module b
import * from builtins
export C
class C
var x: list[int] = []
def m(x: int): int
self.x << x
return len(x)
module a
import C from b
export main
def main(args: list[str])
c = C()
for a in args
print(c.m(int(a)))
Meine Sprache kennt Module, in deren Namensraum man Namen aus anderen Modulen importieren kann und die selbst wieder Namen exportieren. Ein Modul ist eine Folge von Klassen- oder Funktionsdefinitionen, niemals einfach nur Anweisungen. In einer Klasse kann ich Variablen und Methoden definieren. Alles hat einen Typ:
Code: Alles auswählen
b >> module
C >> class[C]
C.x >> list[int]
C.m >> fun[[C, int], int]
a >> module
a.C >> class[C]
a.main >> fun[list[str], none]
Damit haben auch alle Teilausdrücke einen Typ - das Typsystem muss (siehe Scala) einfach mächtig genug sein, um hier möglichst ohne "cast" auszukommen.
Ich kann nun mit ModuleInfo, ClassInfo, VarInfo, MethodInfo und FunInfo sowie TypInfo Objekten eine Repräsentation des Quelltexts aufbauen, ohne ihn ausführen zu müssen, da die die Wirkung der Deklarationen kenne. Heraus kommt dann ein Repository, welches weiß, dass es drei Module (a, b und builtins) gibt, das a z.B. in der Datei "a.sma" und b in der Datei "b.sma" abgelegt ist, das b eine Klasse C definiert, diese wiederum eine Variable und eine Methode und wie deren Typen aussehen.
Jedes Mal, wenn sich der Quelltext ändert (bei Eclipse und Java ist das AFAIK nach 700ms Inaktivität des Benutzers nach einer Änderung oder so), rennt das System nun los und passt das Repository an. Eclipse unterstützt das System dadurch, dass Deltas vom Editor berechnet werden, anhand derer man - aufwendiger aber letztlich effizienter - nur so viel wie nötig jedes Mal verarbeiten muss.
Kommen wir zum Editor.
Angenommen, ich fordere in einer komplett leeren Datei die Komplettierung an. Der Kontext ist damit offenbar die Datei (a.k.a. compilation unit) und weil meine Sprache so aufgebaut ist, dass es immer mit `module` losgeht, ist das die einzige an dieser Stelle sinnvolle Vervollständigung.
Gleiches gilt, wenn ich nach `mod` um Hilfe bitte. Das ist an dieser Stelle ein Syntaxfehler, der Kontext ist also immer noch die Datei, die einzige mögliche Komplettierung `module`.
Alternativ könnte das System auch vermuten, dass ich wohl ein Schlüsselwort tippen wollte, weil ich (exklusive der drei Buchstaben) am Zeilenanfang stehe, und mir da alle möglichen Schlüsselworte anbieten und die Liste gleich auf alle, die mit `mod` beginnen einschränken. Schlüsselworte sind ein ärmlicher Default, aber besser als gar nix.
Wäre der Kontext der einer Funktion oder Methode, wäre auch ein Name denkbar. Dazu muss man nun die Liste der lokalen Variablen in der Funktion, die üblichen Pseudovariablen wie `self`, `true`, `false` oder `none`, sowie modullokalen und schließlich importierte Namen kennen; und dieser Reihenfolge anzeigen, falls sie überhaupt auf `mod` passen.
In einer Klasse als Kontext sind wieder `var` und `def` möglich. Meine Sprache ist absichtlich recht simpel.
In einem Kommentar könnte es sinnvoll sein, einfach beliebige Worte zu komplettieren, damit man Dampfdruckausstoßdüse nicht jedes Mal neu tippen muss. Diese Form der Komplettierung kann allgemein immer hilfreich sein, gerade wenn die Sprache nicht statisch komplett typisiert ist.
Spannender ist nun die Komplettierung hinter `self.` in einer Methode. Ich befinde mich in einer "Attributzugriffsposition". Das kann ich noch syntaktisch erkennen. Nun muss ich aber als nächstes den (statischen) Typ von `self` bestimmen. Für diesen Spezialfall ist es einfach, weiß ich doch, dass diese Pseudovariable für das Empfängerobjekt steht und ich somit, da ich auch weiß, zu welcher Klasse die Methode gehört, in meinem Repository nachschlagen, welche Variablen und Funktionen meine Klasse und alle Oberklassen so anbieten. Entdeckt man etwas wie `return expr.`, so kann man eine Nummer schlauer sein (Standard bei Java-IDEs) und spicken, welchen Rückgabetyp die Methode oder Funktion des Kontext hat und die Ergebnismenge passend priorisieren (filtern geht nicht, weil der Anwender die Kaskade noch weiterführen könnte).
Um den Typ eines Teilausdrucks zu berechnen, muss ich diesen komplett bis auf bekannte primitive Operationen herunter brechen und dann dann eine Typanalyse (in meinem Beispiel mit lokaler Typinferenz) durchführen. So sähe der Rumpf von `main` vielleicht so aus:
Code: Alles auswählen
Block(
Assignment(
Local("c"),
Call(Name("C"))),
For(Local("a"), Local("args"), Block(
Call(Name("print"),
Call(GetAttr(Local("c"), "m"),
Call(Name("int"), Local("a")))))))
Von innen nach außen: Der Typ von `a` in dem letzten `Local("a")` muss in dem Block bekannt sein, da die Variable durch das `for` gebunden wird. Diese weiß, dass sie auf den Typ von `args` die Funktion `iter()` anwenden muss, die ich nicht klug genug bin, korrekt zu typisieren, daher sage ich lieber, es wird `__iter__()` aufgerufen, welches im Falle einer `list[T]` als `fun[list[T], T]` definiert ist. Der Typ von `args` muss bekannt sein, er wird in den äußeren Block reingereicht. Nun kann ich aus `list[int]` und `fun[list[T], T]` ein T=int ableiten und somit ist `a` vom Typ `int`.
So mache ich weiter, bis ich alle Typen aller Teilausdrücke kenne. Der Typ von `c` ist beispielsweise der - oder ein generellerer - von `a`. Die Zuweisung überträgt auch den Typ. Spannend ist, dass ohne explizite Deklaration von Variablen, mögliche Typen auch später noch generischer werden können. Gerade als Bedingung in einem `if` macht das viel Spaß.
Am besten baut man aus dem Quelltext einen abstrakten Syntaxbaum (AST), den man mit Typinformationen annotiert und der weiterhin noch weiß, an welcher Stelle im Quelltext seine Bestandteile standen. In der Regel müsste hier ein Intervall reichen. Damit kann man dann für eine Vervollständigung einfach die Cursorposition nehmen und den Knoten des AST suchen, der gerade noch den Cursor enthält und somit zusammen mit allen seinen Vätern den Kontext vorgibt.
Man braucht dafür allerdings einen Parser, der sehr verzeihend ist und nicht nach dem ersten Fehler im Programm aufgibt, sondern so bald wie möglich wieder aufsetzt, um nicht fälschlich alles, was hinter einer unvollständigen Zeile steht, als Fehler zu verwerfen und so korrekte Definitionen (wenigstens zeitweise) aus dem Repository zu entfernen.
Auch muss man das System so tunen, dass ein öffnender Kommentar (falls es das gibt) oder mehrzeiliger String nicht den selben Effekt hat. Hier sollte sich das Repository so lange noch an den alten Stand erinnern, bis der Kommentar oder String wieder geschlossen wird.
Also: Eigentlich ist das alles gar nicht so schwer :) Mal abgesehen, von dem Typsystem, welches man benötigt, um das Programm "zu verstehen". EcmaScript 4 könnte interessant sein, da es versucht, auf eine eigentlich dynamische Sprache, ein statisches Typsystem aufzusetzen. Oder Fortress, welches typisierte Module hat. Deren Strukturtypen könnte man sich beispielsweise abschauen, da man glaube ich entsprechendes braucht. Alternativ helfen Traits als Sprachkonzept. Polymorphe Typen und Vereinigungstypen sind meines Wissens ebenfalls notwendig. Will man Tupel typisieren, was notwendig wird, sobald man mehrere Werte in einer Funktion zurückgeben kann, braucht man dafür ebenfalls Typausdrücke.
Was jetzt möglich wird, sind Refactorings. Eclipse und Java beispielsweise kennen in ihrem AST nicht nur die ursprünglichen Quelltextpositionen, sondern er ist ein derartiges Modell, dass wenn man den AST ändert, Eclipse automatisch den Quelltext im Editor anpasst. Dies macht etwa das gleichzeitige Ändern aller Vorkommen einer Variable leicht möglich; oder das Umschreiben von `import`-Anweisungen.
Angenommen, ich hätte in meiner Sprache eine Variante, dass ich
schreiben könnte. Habe ich nur dies:
und will ich `foo` in `bar` umbenennen, muss das System schlau genug sein, und gleichzeitig, das `import` mit einem `as bar` ergänzen und außerdem warnen, falls es `bar` schon geben sollte.
Übungsaufgabe: Welchen Typ hat eigentlich der Teilausdruck `[]`?
Stefan