PyDev AST

Aus Eclipse
Wechseln zu: Navigation, Suche

PyDev enthält einen Editor für Python-Quelltexte, der beispielsweise Syntax-Hervorhebung und Code-Vervollständigung anbietet. Außerdem wird, ähnlich wie für Java, eine Outline des Python-Quelltextes in Bearbeitung angeboten. Nicht zuletzt enthält PyDev auch einige Refactoring-Tools.

Um diese Funktionalitäten anzubieten, muss PyDev Python-Quelltexte analysieren können. Dazu wird ein Parser für Python-Quelltext verwendet, der aus dem Quelltext einen Syntaxbaum (AST) extrahiert, der für die weitere Verarbeitung genutzt werden kann. In einem solchen Syntaxbaum wird der Quelltext als Baum repräsentiert, dessen Knoten im wesentlichen Elemente der Python-Grammatik repräsentieren und einige weitere Informationen enthalten, beispielsweise die jeweilige Position im Quelltext.

Um den PyDev-AST zu einem Python-Quelltext in Eclipse anzuzeigen, wurde im Rahmen dieser Seminararbeit ein AST Viewer entwickelt, der in einem gesonderten Artikel beschrieben wird.

Parser

Der Python-Parser in PyDev basiert auf dem Parser der Python-Implementierung Jython[1]. Für PyDev ist er im Plugin org.python.pydev.parser implementiert. Darin gibt es für die verschiedenen Versionen von python jeweils einen eigenen Parser im Paket org.python.pydev.parser.grammarXX mit XX gleich 24 für python 2.4 und so weiter für python 2.5, 2.6 und 3.0. Die python-Syntax wird mithilfe von javacc gelesen. Dazu hat jedes der Pakete org.python.pydev.parser.grammarXX eine Datei python.jjt_template. Diese wird mit dem Skript make_replace.py in org.python.pydev.parser.grammarcommon in die Eingabedatei python.jjt für javacc transformiert.

AST-Knoten

Die Knotentypen des AST werden größtenteils im Paket org.python.pydev.parser.jython.ast definiert. Die Klassen in diesem Paket werden größtenteils automatisch vom Skript asdl_java.py erzeugt, das auf einem entsprechenden Skript in Jython basiert.

Die Klassen des AST sind abgeleitet von org.python.pydev.parser.jython.SimpleNode[2].

Die Knotentypen sind auf einer separaten Seite ausgeführt. Jeder Knoten enthält die seinem Typ entsprechenden Informationen. Da die Klassen der Knotentypen alle von SimpleNode abgeleitet sind, sind die dort definierten Attribute in allen Knoten verfügbar. Es handelt sich dabei um

int beginLine
Zeile, in dem der Knotentext im Python-Quelltext gefunden wurde.
int beginColumn
Spalte in beginLine, in der der Knotentext im Python-Quelltext gefunden wurde.
SimpleNode parent
Elternknoten, siehe unten.
List<Object> specialsBefore und List<Object> specialsAfter
Hier werden Annotationen und Kommentare gespeichert. Der Zugriff ist offenbar nur über instanceof und Casts möglich.

Zeichenpositionen

Die Bedeutung der Zeichenpositionen ist vom Knotentyp abhängig und nicht immer einfach zu erraten, siehe folgendes Beispiel:

for i in range(3):         # For: Start beim 'f' von for
    print      "i=%d" % d  # Print: Start beim '"' des Musters; BinOp %: Start beim letzten 'd'

Die Länge oder das Ende des Quelltextes zu den Knoten wird nicht aufgezeichnet. Um daher beispielsweise die Auswahlmarkierung so zu erweitern, dass alle Kind-Elemente um die aktuell selektierte Quelltext-Stelle herum ebenfalls markiert werden, kann daher der AST mit einem org.python.pydev.refactoring.ast.visitors.selection.SelectionExtenderVisitor durchlaufen werden.

Achtung: PyDev verwendet andere Konventionen für Zeilen- und Spalten-Nummern (Start jeweils bei 1) als in Eclipse üblich (Start bei 0).

Elternknoten

Die Klasse SimpleNode enthält ein Attribut parent. Es ist nicht klar, wann dieses Attribut gefüllt wird und mit welchem Wert. Es gibt nämlich einen ParentVisitor, der dieses Attribut überschreibt. Das scheint nicht besonders sinnvoll, wenn das Attribut nicht vor Verwendung des ParentVisitor leer wäre. Außerdem sieht der ParentVisitor, wie jeder Visitor, nur einen Teil der Knoten des Baums, sodass die von ihm gefundene Eltern-Kind-Beziehung nicht der des Baums entspricht. Beispielsweise hat ein Import-Knoten eine Liste von aliasType-Kindern, die ein Visitor nicht sieht (siehe #Visitor). Ein Visitor sieht nur die Kinder der aliasType-Knoten, diese sind vom Typ NameTok. Die tatsächlichen Eltern der NameTok-Knoten sind also die aliasType-Knoten, während der ParentVisitor den Import-Knoten als Elternknoten bestimmt.

Bestimmung der Knotentypen

Um zu einem gegebenen Knoten den Typ zu bestimmen, kann der instanceof-Operator-verwendet werden.

Eine alternative, wenn auch deutlich umständlichere Möglichkeit besteht für die Knotentypen, die von einem Visitor (siehe #Visitor) besucht werden. Hierzu könnte ein Visitor entwickelt werden, der ausgehen vom Elternknoten oder der Wurzel des AST den Knoten sucht, dessen Typ bestimmt werden soll. Werden alle Methoden visitXYZ überschrieben, kann auch so der Knotentyp ermittelt werden. Insgesamt erscheint dies deutlich aufwendiger als die Verwendung von instanceof.

Wurzelknoten

Es gibt keine Funktion, um zu einem AST-Knoten die Wurzel des AST zu bestimmen. Auf den Wurzelknoten des AST zu einem Python-Quelltext in einem Python-Editor kann über die Methode PyEdit.getAST() zugegriffen werden. Dieser Wurzelknoten ist immer vom Typ Module, da jeder Python-Quelltext ein Modul definiert.

Adapter

Für die Verwendung des AST ist es oft nützlich, die einzelnen Knoten eines Syntaxbaum mit Zusatzinformationen zu versehen. Das könnten beispielsweise Daten sein, die sich aus dem AST nur teuer berechnen lassen und die deshalb zwischengespeichert werden sollen, oder eine Markierung, ob der Knoten bei einem Durchlauf des Baums besucht wurde. Die Knoten-Klassen des AST in PyDev lassen sich nicht direkt mit solchen Informationen versehen. Stattdessen werden hier sogenannte Adapter verwendet[3]. Beispiele für Adapter sind:

AbstractNodeAdapter<T extends SimpleNode>

Der AbstractNodeAdapter ist ein allgemeiner/abstrakter Adapter, der zu einem AST-Knoten den Adapter des Eltern-Knotens und weitere Informationen zusammenfasst.

AbstractScopeNode<T extends SimpleNode>

Der AbstractScopeNode ist ein allgemeiner/astrakter Adapter für solche AST-Knoten, die einen Scope definieren. Beispiele sind ModuleAdapter, ClassDefAdapter, oder FunctionDefAdapter.

ModuleAdapter

Der ModuleAdapter ist abgeleitet von AbstractScopeNode<Module>. Er erweitert den Knotentyp Module. Üblicherweise werden Instanzen dieser Klasse mithilfe der VisitorFactory erzeugt und dabei der Aufbau des AST gestartet. Dies geschieht über die Methode VisitorFactory.createModuleAdapter(...), die wiederum nötigenfalls VisitorFactory.getRootNode(IDocument) aufruft. So wird auch ein ModuleAdapter erzeugt, wenn eine Instanz der Klasse RefactoringInfo erzeugt wird.

Es ist leider nicht möglich, den org.python.pydev.refactoring.ast.adapters.ModuleAdapter außerhalb von PyDev zu verwenden, denn das Paket org.python.pydev.refactoring.ast.adapters wird nicht exportiert.

ClassDefAdapter

Der ClassDefAdapter adaptiert einen ClassDef-Knoten und ermöglicht den einfachen Zugriff auf Methoden, Konstruktoren, Superklassen.

Visitor

Um den AST zu durchlaufen, wird das Visitor-Pattern[4] verwendet.

Zu den meisten (siehe unten) AST-Knotentypen, beispielsweise Tuple gibt es im Interface VisitorIF eine Methode:
Object visitTuple(Tuple node);
Der Knotentyp Tuple hat wiederrum zwei Methoden, um den Baum zu durchlaufen
Object accept(VisitorIF visitor) throws Exception {
    return visitor.visitTuple(this);
}
void traverse(VisitorIF visitor) throws Exception {
    ... // alle Kinder besuchen
}
Es gibt eine (ebenfalls automatisch erzeugte) Klasse VisitorBase, die (als einzige Klasse) VisitorIF implementiert und zwei neue abstrakte Methoden definiert:
   abstract protected Object unhandled_node(SimpleNode node) throws Exception;
   abstract public void traverse(SimpleNode node) throws Exception;
Alle anderen abstrakten Methoden aus VisitorIF rufen diese Methoden folgendermaßen auf:
public Object visitTuple(Tuple node) throws Exception {
    Object ret = unhandled_node(node);
    traverse(node);
    return ret;
}

Wenn also von VisitorBase abgeleitet wird, brauchen daher nur die Methoden für interessanten AST-Elemente überschrieben werden. Die in PyDev vorhandenen Visitors sind alle von VisitorBase abgeleitet.

Wie oben geschrieben, gibt es für die meisten Knotentypen eine Methode visitXYZ in VisitorIF. Beispielsweise ist hier der Knotentyp argumentsType ausgenommen, in dem die Parameter einer Funktion zusammengefasst werden, beispielsweise über keyword arguments und Default-Parameter. Es sieht so aus, als würde ein Visitor nur rein syntaktische Elemente zu sehen bekommen, während diejenigen Knoten, die schon ansatzweise semantische Informationen enthalten, nur über den jeweiligen Elternknoten erreicht werden können.

Vorhandene Visitors

Es sind in PyDev zahlreiche Klassen vorhanden, die von VisitorBase ableiten. Diese sind einfach aufzufinden, indem das PyDev-Projekt in Eclipse importiert wird und die Typhierarchie für VisitorBase aufgerufen wird.

Rewriter

Um Python-Quelltext aus dem AST zu erzeugen, kann der Visitor org.python.pydev.refactoring.ast.visitors.rewriter.Rewriter aus dem Plugin org.python.pydev.refactoring verwendet werden. Dessen Methoden String createSourceFromAST(...) erzeugen einen String mit Python-Quelltext zum dem übergebenen AST-Knoten.

Leider lässt sich nur innerhalb des Plugins org.python.pydev.refactoring auf Rewriter zugreifen, da das Paket org.python.pydev.refactoring.ast.visitors.rewriter nicht exportiert wird.

SelectionExtenderVisitor

Für Refactorings ist es oft notwendig, die Auswahl des Benutzers zu erweitern bis sie einen vollständigen AST-Knoten darstellt. Dazu kann der Visitor org.python.pydev.refactoring.ast.visitors.selection.SelectionExtenderVisitor aus dem Plugin org.python.pydev.refactoring benutzt werden. Die Methode ITextSelection org.python.pydev.refactoring.core.base.RefactoringInfo.getExtendedSelection() verwendet diesen Visitor, um die Selektion zu erweitern.

LocalVariablesVisitor

Um beispielsweise eine Liste der lokalen Variablen zu erhalten, kann der org.python.pydev.refactoring.ast.visitors.LocalVariablesVisitor verwendet werden.

Ein Beispiel für dessen Verwendung findet sich in org.python.pydev.refactoring.coderefactoring.inlinelocal.InlineLocalRefactoring.checkInitialConditions(...). Dort wird zunächst anhand der Textselektion des Benutzers der Scope bestimmt, in dem nach Variablen gesucht werden soll. Danach wird der LocalVariablesVisitor aufgerufen, den AST ab dem Wurzelknoten des Scope zu durchlaufen. Dabei werden in visitName(...) alle Variablennamen mitgeschrieben. Diese sind nach Ende des Baumdurchlaufs mit LocalVariablesVisitor.getVariables() als Liste von Name-Objekten abrufbar.

Der Zugriff auf diesen Visitor ist nur innerhalb von PyDev möglich. Der in PyDev_Refactoring_Beispiel gezeigte InsertNoneNameFinderVisitor ist sehr ähnlich zum LocalVariablesVisitor

Zugriff auf den AST

Der Zugriff auf den AST zu einem Quelltext in einem Python-Editor soll hier anhand der Funktion Go to definition dargestellt werden. Diese Funktion lässt sich über die Benutzerschnittstelle von Eclipse aufrufen, um an die Quelltext-Stelle zu navigieren, an der eine Funktion oder Variable definiert wird. Ein weiteres — und deutlich einfacheres — Beispiel für den Zugriff auf den AST wird im Artikel PyDev_Refactoring_Beispiel dargestellt, in dem ein im Rahmen dieser Seminararbeit erstelltes Beispiel für ein Refactoring-Tool vorgestellt wird.

Der Startpunkt für Go to definition ist die Klasse PyGoToDefinition. Es handelt sich hier um eine Action, die auf eine Benutzeraktion hin gestartet wird. Diese Action ist zwar von PyRefactorAction abgeleitet, aber es handelt sich hierbei natürlich nicht um ein Refactoring-Tool sondern um eine Navigationshilfe. Anders als in [5] beschrieben wird hier kein getrennter IActionDelegate verwendet, sondern die Oberklasse PyAction von PyRefactorAction implementiert das interface IEditorActionDelegate. Über dessen Methode setActiveEditor(...) teilt Eclipse vor dem Aufruf von run(...) dem IEditorActionDelegate den aktuellen Editor mit. Ist dieser eine Instanz von PyEdit, kann mit PyEdit.getAST() auf den AST zugegriffen werden. Die Python-Editoren starten regelmäßig eine Analyse des Quelltextes. Mit PyEdit.getAST() wird jeweils der letzte so generierte Syntaxbaum erreicht. Beim Aufruf von PyGoToDefinition.run(...) wird zunächst anhand eines Zeitstempels geprüft, ob die AST der offenen Python-Editoren (Instanzen von PyEdit) noch aktuell sind. Wenn nicht, werden diese aktualisiert. In jedem Fall wird mit aktuellen AST PyGoToDefinition.findDefinitionsAndOpen(...) aufgerufen. Von findDefinitionsAndOpen(...) aus wird ein mit PyRefactorAction.getRefactoringRequest() ein RefactoringRequest erzeugt. Diese Klasse bietet über die Methode getModule() Zugriff auf das Python-Modul, das im Editor bearbeitet wird. Schließlich wird in findDefinition(...) die Suche nach der Definition an eine Implementierung von IPyRefactoring weitergereicht. Die einzige konkrete Implementierung von IPyRefactoring ist Refactorer. Diese Implementierung kann durch Anknüpfen an den Extension Point org.python.pydev.pydev_refactoring theoretisch ersetzt (aber soweit erkennbar nicht erweitert) werden. Refactorer.findDefinition(...) reicht die Aufgabe an RefactorerFindDefinition weiter und dies wiederum an PyRefactoringFindDefinition.findActualDefinition(...). Von dort geht es in ein paar Zwischenschritten weiter zu IModule.findDefinition(...), wobei das IModule mit RefactoringRequest.getModule() erreicht wird. Aufgrund der Sprachmöglichkeiten von Python gibt es mehrere verschiedene Modul-Typen, die alle unterscheidlich durchsucht werden müssen:

  • Java Klassen, denn Jython erlaubt den Import von Java-Klassen als Python-Module
    • als Quelltext, .class-Datei oder in einem JAR
  • Compilierte Python-Module
  • Python-Module im Quelltext, implementiert in SourceModule

Auf die weitere Suche nach der Definition soll nur für SourceModule kurz eingangen werden. Zunächst wird in SourceModule.findDefinition(...) mithilfe eines FindScopeVisitor der Scope zur zu suchenden Definition bestimmt. Dazu läuft der Visitor den AST ab und merkt sich auf einem Stack diejenigen AST-Elemente, die einen neuen Scope eröffnen. Schließlich wird das Element zurückgeliefert, das die übergebene Zeile im Quelltext enthält. Schließlich wird ein FindDefinitionModelVisitor benutzt, um mögliche Definitionen zu finden. Dieser Visitor interpretiert den AST anhand der Semantik von Python und sammelt entweder die exakte oder eine Liste möglicher Kandidaten für die gesuchte Definition in der Instanzvariablen definitions.

Quellen

  1. http://www.pydev.org/developers_grammar.html
  2. Im plugin org.python.pydev.core ist ein leeres Interface org.python.pydev.parser.ISimpleNode definiert, das von SimpleNode "implementiert" wird. Das Interface ISimpleNode wird in den Interfaces IParserObserver und IParserObserver2 in der Signatur der Methode void parserChanged(...) verwendet, da dort aus irgendwelchen Gründen nicht SimpleNode verwendet werden kann. Der Parameter vom Typ ISimpleNode wird allerdings nur in PyEdit verwendet und dort als erstes auf SimpleNode gecastet.
  3. http://sifsstud2.hsr.ch/doc/PythonRefactoring.pdf, Kap. 3.1.2
  4. http://en.wikipedia.org/wiki/Visitor_pattern
  5. Clayberg/Rubel