Wie werden Generika implementiert?

16

Dies ist die Frage aus Sicht der Compiler-Interna.

Ich interessiere mich für Generika, nicht für Vorlagen (C ++), daher habe ich die Frage mit C # markiert. Nicht Java, da AFAIK die Generika in beiden Sprachen in Implementierungen unterscheiden.

Wenn ich mir Sprachen ohne Generika anschaue, ist das ziemlich einfach. Sie können die Klassendefinition validieren, der Hierarchie hinzufügen und fertig.

Aber was tun mit generischer Klasse und was noch wichtiger ist, wie mit Verweisen darauf umzugehen ist? So stellen Sie sicher, dass statische Felder pro Instanziierung singulär sind (dh jedes Mal, wenn generische Parameter aufgelöst werden).

Nehmen wir an, ich sehe einen Anruf:

var x = new Foo<Bar>();

Füge ich Foo_Barder Hierarchie eine neue Klasse hinzu?


Update: Bisher habe ich nur 2 relevante Beiträge gefunden, aber auch sie gehen nicht auf viele Details im Sinne von "Wie mache ich das selbst?" Ein:

Greenoldman
quelle
Eine Aufwertung, weil ich eine vollständige Antwort für interessant halte. Ich habe einige Ideen, wie es funktioniert, aber nicht genug, um genau zu antworten. Ich glaube nicht, dass Generika in C # für jeden generischen Typ zu speziellen Klassen kompiliert werden. Sie scheinen zur Laufzeit behoben zu sein (die Verwendung von Generika kann zu einem spürbaren Geschwindigkeitsverlust führen). Vielleicht können wir Eric Lippert dazu bringen, sich einzuschalten?
KChaloux
2
@ KChaloux: Auf der MSIL-Ebene gibt es eine Beschreibung des Generikums. Wenn die JIT ausgeführt wird, wird für jeden Werttyp, der als generischer Parameter verwendet wird, ein separater Maschinencode sowie ein weiterer Satz von Maschinencode erstellt, der alle Referenztypen abdeckt. Das Beibehalten der generischen Beschreibung in MSIL ist sehr hilfreich, da Sie damit zur Laufzeit neue Instanzen erstellen können.
Ben Voigt
@ Ben Deshalb habe ich nicht versucht, die Frage tatsächlich zu beantworten: p
KChaloux
Ich bin mir nicht sicher , ob Sie noch da sind, aber was Sprache kompilieren Sie zu . Das wird einen großen Einfluss darauf haben, wie Sie Generika implementieren. Ich kann Informationen darüber bereitstellen, wie ich es normalerweise am vorderen Ende angegangen bin, aber das hintere Ende kann sehr unterschiedlich sein.
Telastyn
@Telastyn, für diese Themen bin ich mir sicher :-) Ich suche etwas sehr nahes an C #, in meinem Fall kompiliere ich zu PHP (kein Scherz). Ich bin Ihnen dankbar, wenn Sie Ihr Wissen teilen.
Greenoldman

Antworten:

4

So stellen Sie sicher, dass statische Felder pro Instanziierung singulär sind (dh jedes Mal, wenn generische Parameter aufgelöst werden).

Jede generische Instanziierung verfügt über eine eigene Kopie der (verwirrend benannten) MethodTable, in der statische Felder gespeichert werden.

Nehmen wir an, ich sehe einen Anruf:

var x = new Foo<Bar>();

Füge ich Foo_Barder Hierarchie eine neue Klasse hinzu?

Ich bin mir nicht sicher, ob es sinnvoll ist, sich die Klassenhierarchie als eine Struktur vorzustellen, die tatsächlich zur Laufzeit existiert. Es ist eher ein logisches Konstrukt.

Wenn Sie jedoch MethodTables berücksichtigen, von denen jede einen indirekten Zeiger auf ihre Basisklasse enthält, um diese Hierarchie zu bilden, wird der Hierarchie eine neue Klasse hinzugefügt.

svick
quelle
Danke, das ist ein interessantes Stück. Die statischen Felder werden also ähnlich wie bei der virtuellen Tabelle gelöst, oder? Gibt es einen Verweis auf "globales" Wörterbuch, das Einträge für jeden Typ enthält? Ich könnte also 2 Assemblys haben, die sich nicht gegenseitig kennen und von denen Foo<string>nicht zwei Instanzen eines statischen Felds erzeugt werden Foo.
Greenoldman
1
@ Greenoldman Nun, nicht ähnlich wie virtuelle Tabelle, genau das gleiche. Die MethodTable enthält sowohl statische Felder als auch Verweise auf Methoden des Typs, die beim virtuellen Versand verwendet werden (daher heißt sie MethodTable). Und ja, die CLR muss eine Tabelle haben, mit der sie auf alle Methodentabellen zugreifen kann.
Svick
2

Ich sehe dort zwei konkrete Fragen. Sie möchten wahrscheinlich zusätzliche verwandte Fragen stellen (als separate Frage mit einem Link zurück zu dieser), um ein umfassendes Verständnis zu erhalten.

Wie werden statische Felder mit separaten Instanzen pro generischer Instanz versehen?

Nun, für statische Elemente, die sich nicht auf die generischen Typparameter beziehen, ist dies ziemlich einfach (verwenden Sie ein Wörterbuch, das von den generischen Parametern auf den Wert abgebildet wird).

Elemente (statisch oder nicht), die sich auf die Typparameter beziehen, können über das Löschen von Typen behandelt werden. Verwenden Sie einfach (oft System.Object) die stärkste Einschränkung . Da die Typinformationen nach Compiler-Typprüfungen gelöscht werden, sind Laufzeit-Typprüfungen nicht erforderlich (obwohl zur Laufzeit möglicherweise noch Schnittstellenumwandlungen vorhanden sind).

Erscheint jede generische Instanz separat in der Typhierarchie?

Nicht in .NET-Generika. Es wurde entschieden, die Vererbung von den Typparametern auszuschließen, sodass sich herausstellt, dass alle Instanzen eines Generikums an derselben Stelle in der Typhierarchie befinden.

Dies war wahrscheinlich eine gute Entscheidung, da es unglaublich überraschend wäre, keine Namen aus einer Basisklasse nachzuschlagen.

Ben Voigt
quelle
Mein Problem ist, dass ich mich nicht vom Denken in Bezug auf die Vorlage lösen kann. Zum Beispiel - anders als Vorlage generische Klasse ist vollständig zusammengestellt. Dies bedeutet, dass in anderen Assemblys, die diese Klasse verwenden, was passiert? Die bereits kompilierte Methode wird beim internen Casting aufgerufen? Ich bezweifle, dass sich die Generika auf Einschränkungen stützen können - ansonsten eher auf Argumente Foo<int>und Foo<string>dieselben Daten ohne FooEinschränkungen.
Greenoldman
1
@greenoldman: Können wir Werttypen für eine Minute vermeiden, weil sie tatsächlich speziell behandelt werden? Wenn Sie List<string>und haben List<Form>, da List<T>intern ein Element vom Typ vorhanden ist T[]und es keine Einschränkungen gibt T, erhalten Sie tatsächlich Maschinencode, der ein Element manipuliert object[]. Da jedoch nur TInstanzen in das Array eingefügt werden, kann alles, was herauskommt, Tohne zusätzliche Typprüfung als zurückgegeben werden. Wenn Sie dies ControlCollection<T> where T : Controlgetan T[]hätten, wäre das interne Array geworden Control[].
Ben Voigt
Verstehe ich richtig, dass die Einschränkung als interner Typname verwendet wird, aber wenn die Klasse tatsächlich verwendet wird, wird das Casting verwendet? OK, ich verstehe dieses Modell, aber ich hatte den Eindruck, dass Java es verwendet, nicht C #.
Greenoldman
3
@greenoldman: Java führt die Typlöschung im Übersetzungsschritt source-> bytecode durch. Das macht es dem Prüfer unmöglich, generischen Code zu prüfen. C # erledigt dies im Schritt Bytecode-> Maschinencode.
Ben Voigt
@BenVoigt In Java bleiben einige Informationen zu den generischen Typen erhalten, da Sie andernfalls keine generisch verwendende Klasse ohne deren Quelle kompilieren könnten. Es ist nur nicht in der Bytecode-Sequenz selbst AIUI gehalten, sondern in Klassenmetadaten.
Donal Fellows
1

Aber was tun mit generischer Klasse und was noch wichtiger ist, wie mit Verweisen darauf umzugehen ist?

Der allgemeine Weg im Frontend des Compilers besteht darin, zwei Arten von Typinstanzen zu haben, den generischen Typ ( List<T>) und einen gebundenen generischen Typ ( List<Foo>). Der generische Typ definiert, welche Funktionen vorhanden sind, welche Felder und hat generische Typreferenzen, wo Timmer verwendet wird. Der gebundene generische Typ enthält einen Verweis auf den generischen Typ und eine Reihe von Typargumenten. Damit haben Sie genügend Informationen, um dann einen konkreten Typ zu generieren und die generischen Typreferenzen durch Foooder unabhängig von den Typargumenten zu ersetzen . Diese Art der Unterscheidung ist wichtig, wenn Sie Typinferenz machen und List<T>versus ableiten müssen List<Foo>.

Anstatt an Generika wie Vorlagen zu denken (die verschiedene Implementierungen direkt aufbauen), kann es hilfreich sein, sie als Konstruktoren für funktionale Sprachtypen zu betrachten (wobei die generischen Argumente wie Argumente in einer Funktion sind, die Ihnen einen Typ gibt).

Was das Backend angeht, weiß ich es nicht wirklich. Alle meine Arbeiten mit Generika zielten auf CIL als Backend ab, sodass ich sie dort zu den unterstützten Generika kompilieren konnte.

Telastyn
quelle
Vielen Dank (schade, dass ich keine Mehrfachantworten akzeptieren kann). Es ist großartig zu hören, dass ich diesen Schritt so ziemlich richtig gemacht habe - in meinem Fall List<T>gilt der echte Typ (seine Definition), während List<Foo>(danke auch für das Terminologiestück) mit meinem Ansatz die Erklärungen von List<T>(natürlich jetzt gebunden an) enthalten Foostatt T).
Greenoldman