-
Notifications
You must be signed in to change notification settings - Fork 10.5k
/
Copy pathgenerics.tex
12285 lines (10479 loc) · 861 KB
/
generics.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[a4paper,headsepline,bibliography=totoc,toc=flat,fleqn,twoside=semi]{scrbook}
\usepackage{imakeidx}
\usepackage[pdfborder={0 0 0},linkcolor=blue,citecolor=blue,linktocpage=true,colorlinks=true]{hyperref}
\usepackage{upgreek}
\usepackage{bm}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{textgreek}
\usepackage{tikz-cd}
\usepackage{mathtools}
\usepackage{fancyvrb}
\usepackage{array}
\usepackage{xcolor}
\usepackage{mdframed}
%\overfullrule=10pt
\usetikzlibrary{positioning,shapes,shadows,arrows,trees,calc}
\tikzstyle{class}=[rounded corners,draw=black,thick,anchor=west]
\theoremstyle{definition}
\newtheorem{definition}{Definition}[chapter]
\theoremstyle{definition}
\newtheorem{example}{Example}[chapter]
\theoremstyle{definition}
\newtheorem{algorithm}{Algorithm}[chapter]
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}{Lemma}[chapter]
\RecustomVerbatimEnvironment{Verbatim}{Verbatim}{frame=single,numbers=left}
\DeclareNewTOC[
type = listing,
counterwithin=chapter,
float
]{listing}
\newcommand{\mathboxed}[1]{\boxed{\mbox{\vphantom{pI\texttt{pI}}#1}}}
\newcommand{\ttbox}[1]{\boxed{\mbox{\vphantom{pI\texttt{pI}}\texttt{#1}}}}
\newcommand{\ttgp}[2]{\texttt{$\uptau$\_#1\_#2}}
\newcommand{\SubMap}[1]{\begin{tabular}{|lll|}
\hline
\multicolumn{3}{|l|}{\textbf{Types}}\\
\hline
#1\\
\hline
\end{tabular}}
\newcommand{\SubMapC}[2]{\begin{tabular}{|lll|}
\hline
\multicolumn{3}{|l|}{\textbf{Types}}\\
\hline
#1\\
\hline
\hline
\multicolumn{3}{|l|}{\textbf{Conformances}}\\
\hline
#2\\
\hline
\end{tabular}}
\newcommand{\SubType}[2]{\texttt{#1}&$:=$&\texttt{#2}}
\newcommand{\SubConf}[1]{\multicolumn{3}{|l|}{\texttt{#1}}}
\newcommand{\archetype}[1]{$[\![\texttt{#1}]\!]$}
\newcommand{\namesym}[1]{\mathsf{#1}}
\newcommand{\genericparam}[1]{\bm{\mathsf{#1}}}
\newcommand{\proto}[1]{\bm{\mathsf{#1}}}
\newcommand{\protosym}[1]{[\proto{#1}]}
\newcommand{\gensig}[2]{\langle #1\;\textit{where}\;#2\rangle}
\newcommand{\genericsym}[2]{\bm{\uptau}_{#1,#2}}
\newcommand{\assocsym}[2]{[\proto{#1}\colon\namesym{#2}]}
\newcommand{\layoutsym}[1]{[\mathsf{layout\;#1}]}
\newcommand{\supersym}[1]{[\mathsf{superclass}\;#1]}
\newcommand{\concretesym}[1]{[\mathsf{concrete}\;#1]}
\DeclareMathOperator{\gpdepth}{depth}
\DeclareMathOperator{\gpindex}{index}
\DeclareMathOperator{\domain}{domain}
\newcommand{\SourceFile}[1]{\href{https://github.com/apple/swift/tree/main/#1}{\texttt{#1}}}
% Note: \apiref{foo}{bar} must be followed by a newline, because of a quirk with \noindent
\def\apiref#1#2
{\bigskip\hrule\smallskip\noindent\texttt{#1}\hfill\textsl{#2}\smallskip\hrule\smallskip\noindent}
% Comment this out and uncomment the next line to see the work-in-progress sections
\newcommand{\ifWIP}{\iffalse}
%\newcommand{\ifWIP}{\iftrue}
\makeindex[intoc]
\title{\begin{center}
$\left<
\begin{array}{cc}
:&=
\\
\uptau&\rightarrow
\end{array}
\right>$
\end{center}
\bigskip
Compiling Swift Generics}
\author{Slava Pestov}
\pagestyle{headings}
\begin{document}
\maketitle
\chapter*{Preface}
This is a book about the implementation of generic programming in Swift. While it is primarily meant to be a reference for Swift compiler contributors, it should also be of interest to other language designers, type system researchers, and even just curious Swift programmers. Some familiarity with general compiler design and the Swift language is assumed. A basic understanding of abstract algebra is also helpful.
This work began as a paper about the Requirement Machine, a new implementation of the core algorithms in Swift generics which shipped with Swift~5.6. After making some progress on writing the paper, I realized that a reference guide for the entire generics implementation would be more broadly useful to the community. I worked backwards, adding more preliminary material and revising subsequent sections until reaching a fixed point, hopefully converging on something approximating a coherent and self-contained treatment of this cross-section of the compiler.
Part~\ref{part fundamentals} of this book outlines the basic building blocks. Each chapter in the first part depends on the previous chapters; a determined (or stubborn) reader should be able to work through them sequentially, however you might find it easier to skim some sections and refer back later.
Part~\ref{part odds and ends} details how various language features are built up from the core concepts of generics. In the second part, each chapter is mostly independent of the others.
Part~\ref{part rqm} dives into the Requirement Machine, which implements generic signature queries and requirement minimization. This is the most technical part of the book.
Occasional historical asides explain when major features were introduced, citing the relevant Swift evolution proposals. The bibliography lists all cited proposals. There is also an automatically-generated index at the end; you might find it useful for looking up unfamiliar terminology.
The Swift compiler is implemented in C++. To help separate essential from incidental complexity, concepts are described without immediately referencing the source code. Every chapter ends with a ``Source Code Reference'' section, structured somewhat like an API reference, which translates what was previously explained into code. You can skip this material if you're not interested in the practicalities of the compiler implementation itself. No knowledge of C++ is required outside of these sections.
This book was typeset with \TeX. You can find the latest version in our git repository:
\begin{quote}
\url{https://github.com/apple/swift/tree/main/docs/Generics}
\end{quote}
\tableofcontents
\part{Nuts and Bolts}\label{part fundamentals}
\chapter{Introduction}\label{roadmap}
Swift generics were designed with four primary goals in mind:
\begin{enumerate}
\item Generic definitions should be independently type checked, without knowledge of all possible concrete type substitutions that they are invoked with.
\item Shared libraries that export generic definitions should be able to evolve resiliently without requiring recompilation of clients.
\item Layouts of generic types should be determined by their concrete substitutions, with fields of generic parameter type stored inline.
\item Abstraction over concrete types with generic parameters should only impose a cost across module boundaries, or in other situations where type information is not available at compile time.
\end{enumerate}
The Swift compiler achieves these goals as follows:
\begin{enumerate}
\item The interface between a generic definition and its uses is mediated by \textbf{generic requirements}. The generic requirements describe the behavior of the generic parameter types inside the function body, and the generic arguments at the call site are checked against the declaration's generic requirements at compile time.
\item Generic functions receive \textbf{runtime type metadata} for each generic argument from the caller. Type metadata defines operations to abstractly manipulate values of their type without knowledge of their concrete layout.
\item Runtime type metadata is constructed for each type in the language. The \textbf{runtime type layout} of a generic type is computed recursively from the type metadata of the generic arguments. Generic types always store their contents without boxing or indirection.
\item The optimizer can generate a \textbf{specialization} of a generic function in the case where the definition is visible at the call site. This eliminates the overhead of runtime type metadata and abstract value manipulation.
\end{enumerate}
An important part of compiler implementation is the design of domain objects to model concepts in the language being compiled. One way to think of a compiler is that it is \emph{a library for implementing the target language}. A well-designed set of domain objects facilitates the introduction of new language features that compose existing functionality in new ways.
The generics implementation deals with four fundamental domain objects: \emph{generic signatures}, \emph{substitution maps}, \emph{requirement signatures}, and \emph{conformances}. As you will see, they are defined as much by their inherent structure, as their relationship with each other. Subsequent chapters will dive into all the details, but first, we're going to look at a series of worked examples to help you understand the big picture.
\section{Generic Functions}
Consider these two rather contrived function declarations:
\begin{Verbatim}
func identity(_ x: Int) -> Int { return x }
func identity(_ x: String) -> String { return x }
\end{Verbatim}
Apart from the parameter and return type, both have the same exact definition, and indeed you can write the same function for any concrete type. Your aesthetic sense might lead you to replace both with a single generic function:
\begin{Verbatim}
func identity<T>(_ x: T) -> T { return x }
\end{Verbatim}
While this function declaration is trivial, it illustrates some important concepts and allows us to introduce terminology. You'll see a full description of the compilation pipeline in the next chapter, but for now, let's consider a simplified view where we begin with parsing, then type checking, and finally code generation.
\begin{figure}\captionabove{The abstract syntax tree for \texttt{identity(\_:)}}\label{identity ast}
\begin{center}
\begin{tikzpicture}[%
grow via three points={one child at (0.5,-0.7) and
two children at (0.5,-0.7) and (0.5,-1.4)},
edge from parent path={[->] (\tikzparentnode.south) |- (\tikzchildnode.west)}]
\node [class] {\vphantom{p}function declaration: \texttt{identity}}
child { node [class] {\vphantom{p}generic parameter list: \texttt{<T>}}
child { node [class] {\vphantom{p}generic parameter declaration: \texttt{T}}}}
child [missing] {}
child { node [class] {\vphantom{p}parameter declaration: \texttt{\_ x:\ T}}
child { node [class] {\vphantom{p}type representation: \texttt{T}}}}
child [missing] {}
child { node [class] {\vphantom{p}type representation: \texttt{T}}}
child { node [class] {\vphantom{p}body}
child { node [class] {\vphantom{p}statement: \texttt{return x}}
child { node [class] {\vphantom{p}expression: \texttt{x}}}}
child [missing] {}}
child [missing] {}
child [missing] {};
\end{tikzpicture}
\end{center}
\end{figure}
\index{function declaration}
\index{generic parameter list}
\index{generic parameter declaration}
\index{type representation}
\index{identifier}
\index{name lookup}
\paragraph{Parsing} Figure~\ref{identity ast} shows the abstract syntax tree produced by the parser before type checking. The key elements:
\begin{enumerate}
\item The \emph{generic parameter list} \texttt{<T>} introduces a single \emph{generic parameter declaration} named \texttt{T}. As its name suggests, this declares the generic parameter type \texttt{T}, scoped to the entire source range of this function.
\item The \emph{type representation} \texttt{T} appears twice, first in the the parameter declaration \verb|_ x: T| and then as return type of \verb|identity(_:)|. A type representation is the purely syntactic form of a type. The parser does not perform name lookup, so the type representation stores the identifier \texttt{T} and does not refer to the generic parameter declaration of \texttt{T} in any way.
\item The function body contains an expression referencing \texttt{x}. Again, the parser does not perform name lookup, so this is just the identifier \texttt{x} and is not associated with the parameter declaration \verb|_ x: T|.
\end{enumerate}
\index{generic parameter type}
\index{generic signature}
\index{type resolution}
\index{type}
\index{interface type}
\index{generic function type}
\paragraph{Type checking} Some additional structure is formed during type checking:
\begin{enumerate}
\item The generic parameter declaration \texttt{T} declares the generic parameter type \texttt{T}. Types are distinct from type declarations in Swift; some types denote a \emph{reference} a type declaration, and some are \emph{structural} (such as function types or tuple types).
\item The type checker constructs a \emph{generic signature} for our function declaration. The generic signature has the printed representation \texttt{<T>} and contains the single generic parameter type \texttt{T}. This is the simplest possible generic signature, apart from the empty generic signature of a non-generic declaration.
\item The type checker performs \emph{type resolution} to transform the type representation \texttt{T} appearing in our parameter declaration and return type into a semantic \emph{type}. Type resolution queries name lookup for the identifier \texttt{T} at the source location of each type representation, which finds the generic parameter declaration \texttt{T} in both cases. This type declaration declares the generic parameter type \texttt{T}, which becomes the resolved type.
\item There is now enough information to form the function's \emph{interface type}, which is the type of a reference to this function from expression context. The interface type of a generic function declaration is a \emph{generic function type}, composed from the function's generic signature, parameter types, and return type:
\begin{quote}
\begin{verbatim}
<T> (T) -> T
\end{verbatim}
\end{quote}
\end{enumerate}
The final step is the type checking of the function's body. The expression type checker queries name lookup for the identifier \texttt{x}, which finds the parameter declaration \verb|_ x: T|.
\index{archetype type}
\index{primary archetype type}
While the type of our function parameter is the generic parameter type \texttt{T}, inside the body of a generic function it becomes a different kind of type, called a \emph{primary archetype}. The distinction isn't terribly important right now, and it will be covered in Chapter~\ref{genericenv}. It suffices to say that we'll use the notation \archetype{T} for the primary archetype corresponding to the generic parameter type \texttt{T}.
With that out of the way, the expression type checker assigns the type \archetype{T} to the expression \texttt{x} appearing in the return statement. As expected, this matches the declared return type of the function.
\paragraph{Code generation}
We've now successfully type checked our function declaration. How might we generate code for it? Recall the two concrete implementations that we folded into our single generic function:
\begin{Verbatim}
func identity(_ x: Int) -> Int { return x }
func identity(_ x: String) -> String { return x }
\end{Verbatim}
The calling conventions of these functions differ significantly:
\begin{enumerate}
\item The first function receives and returns the \texttt{Int} value in a machine register. The \texttt{Int} type is \emph{trivial},\footnote{Or POD, for you C++ folks.} meaning it can be copied and moved at will.
\item The second function is trickier. A \texttt{String} is stored as a 16-byte value in memory, and contains a pointer to a reference-counted buffer. When manipulating values of a non-trivial type like \texttt{String}, memory ownership comes into play.
The standard ownership semantics for a Swift function call are defined such that the caller retains ownership over the parameter values passed into the callee, while the callee transfers ownership of the return value to the caller. This means that the \verb|identity(_:)| function cannot just return the value \texttt{x}; instead, it must first create a logical copy of \texttt{x} that it owns, and then return this owned copy. This is achieved by incrementing the string value's buffer reference count via a call to a runtime function.
\end{enumerate}
More generally, every Swift type has a size and alignment, and defines three fundamental operations that can be performed on all values of that type: moving the value, copying the value, and destroying the value. A move is semantically equivalent to, but more efficient than, copying a value followed by destroying the old copy.\footnote{Of course if move-only types are ever introduced into the language, this will no longer be so; a new kind of value will exist which cannot be copied.}
With a trivial type, moving or copying a value simply copies the value's bytes from one memory location to another, and destroying a value does nothing. With a reference type, these operations update the reference count. Copying a reference increments the reference count on its heap-allocated backing storage, and destroying a reference decrements the reference count, deallocating the backing storage when the reference count reaches zero. Even more complex behaviors are also possible; a struct might contain a mix of trivial types and references, for example. Weak references and existential types also have non-trivial value operations.
As the joke goes, every problem in computer science can be solved with an extra level of indirection. The calling convention for a generic function takes \emph{runtime type metadata} for every generic parameter in the function's generic signature. Every type in the language has a reified representation as runtime type metadata, storing the type's size and alignment together with function pointers implementing the move, copy and destroy operations. The generated code for a generic function abstractly manipulates values of generic parameter type using the runtime type metadata provided by the caller. An important property of runtime type metadata is \emph{identity}; two pointers to runtime type metadata are equal if and only if they represent the same type in the language.
\newenvironment{MoreDetails}{\medskip\begin{mdframed}[rightline=true,frametitlerule=true,frametitlerulecolor=gray,frametitlebackgroundcolor=light-gray,frametitlerulewidth=2pt,backgroundcolor=light-gray,linecolor=gray,frametitle={More details}]
\begin{itemize}}{\end{itemize}
\end{mdframed}}
\definecolor{light-gray}{gray}{0.90}
\begin{MoreDetails}
\item Types: Chapter~\ref{types}
\item Function declarations: Section~\ref{func decls}
\item Generic parameter lists: Chapter~\ref{generic declarations}
\item Type resolution: Chapter~\ref{typeresolution}
\end{MoreDetails}
\paragraph{Substitution maps} Let us now turn our attention to the callers of generic functions. A \emph{call expression} references a \emph{callee} together with a list of arguments. The callee is some other expression with a function type. Some possible callees include references to named function declarations, type expressions (which invokes a constructor), function parameters and local variables of function type, and results of other calls which return functions. In our example, we might call the \verb|identity(_:)| function as follows:
\begin{Verbatim}
identity(3)
identity("Hello, Swift")
\end{Verbatim}
The callee here is a direct reference to the declaration of \verb|identity(_:)|. In Swift, calls to generic functions never specify their generic arguments explicitly; instead, the type checker infers them from the types of call argument expressions. A reference to a named generic function stores a \emph{substitution map} mapping each generic parameter type of the callee's generic signature to the inferred generic argument, also called the \emph{replacement type}.
The generic signature of \verb|identity(_:)| has a single generic parameter type. The two references to \verb|identity(_:)| have different substitution maps; the first substitution map has the replacement type \texttt{Int}, and the second \texttt{String}. We will use the following notation for these substitution maps:
\[
\SubMap{\SubType{T}{Int}}
\qquad
\SubMap{\SubType{T}{String}}
\]
We can apply a substitution map to the interface type of our function declaration to get the \emph{substituted type} of the callee:
\[\ttbox{<T> (T) -> T} \times \SubMap{\SubType{T}{Int}} = \ttbox{(Int) -> Int}\]
Substitution maps also play a role in code generation. When generating a call to a generic function, the compiler emits code to realize the runtime type metadata for each replacement type in the substitution map. The types \texttt{Int} and \texttt{String} are \emph{nominal types} defined in the standard library. These types are non-generic and have a fixed layout, so their runtime type metadata can be recovered by taking the address of a constant symbol exported by the standard library.
\index{structural type}
\index{metadata access function}
Structural types are slightly more complicated. Suppose we were instead compiling a call to \verb|identity(_:)| where the replacement type for \texttt{T} was some function type, say \verb|(Int, String) -> Float|. Function types can have arbitrary parameter and return types. Therefore, structural type metadata is \emph{instantiated} by calling one of several \emph{metadata access functions}, declared in the runtime. These runtime entry points take metadata for the parameter types and return type, construct metadata representing the function type, and cache the result for future accesses.
\begin{MoreDetails}
\item Substitution maps: Chapter~\ref{substmaps}
\end{MoreDetails}
\index{inlinable function}
\paragraph{Specialization} The passing of runtime type metadata and the resulting indirect manipulation of values incurs a performance penalty. As an alternative, if the definition of a generic function is visible at the call site, the optimizer can generate a \emph{specialization} of the generic function by cloning the definition and applying the substitution map to all types appearing in the function's body. Definitions of generic functions are always visible to the specializer within their defining module. Shared library developers can also opt-in to exporting the body of a function across module boundaries with the \texttt{@inlinable} attribute.
\begin{MoreDetails}
\item \texttt{@inlinable} attribute: Section~\ref{module system}
\end{MoreDetails}
\section{Generic Types}
\index{struct declaration}
\index{stored property declaration}
For our next example, consider this simple generic struct storing two values of the same type:
\begin{Verbatim}
struct Pair<T> {
let first: T
let second: T
init(first: T, second: T) {
self.first = first
self.second = second
}
}
\end{Verbatim}
This struct declaration contains three members: two stored property declarations, and a constructor declaration. Recall that declarations have an \emph{interface type}, which is the type of a reference to the declaration from expression context. The interface type of \texttt{first} and \texttt{second} is the generic parameter type \texttt{T}.
\index{metatype type}
When a type declaration is referenced from expression context the result is a value representing the type, and the type of this value is a metatype type, so the interface type of \texttt{Pair} is the metatype type \texttt{Pair<T>.Type}.
\index{declared interface type}
\index{generic nominal type}
Type declarations also have a more primitive notion of a \emph{declared interface type}, which is the type assigned to a reference to the declaration from type context. The declared interface type of \texttt{Pair} is the \emph{generic nominal type} \texttt{Pair<T>}. The interface type of a type declaration is the metatype of its declared interface type.
\index{context substitution map}
Instances of \texttt{Pair} store their fields inline without boxing, and the layout of \texttt{Pair} depends on the generic parameter \texttt{T}. If you declare a local variable whose type is the generic nominal type \texttt{Pair<Int>}, the compiler can directly compute the type's layout to determine the size of the stack allocation:
\begin{Verbatim}
let twoIntegers: Pair<Int> = ...
\end{Verbatim}
To compute the layout, the compiler first factors the type \texttt{Pair<Int>} into the application of a substitution map to the declared interface type:
\[\ttbox{Pair<Int>} = \ttbox{Pair<T>} \times \SubMap{\SubType{T}{Int}}\]
The compiler then computes the substituted type of each stored property by applying this substitution map to each stored property's interface type:
\[\ttbox{T} \times \SubMap{\SubType{T}{Int}} = \ttbox{Int}\]
Therefore both fields of \texttt{Pair<Int>} have a substituted type of \texttt{Int}. The \texttt{Int} type has a size of 8 bytes and an alignment of 8 bytes, from which we derive that \texttt{Pair<Int>} has a size of 16 bytes and alignment of 8 bytes.
\index{metadata access function}
However, the layout is not always known at compile time, in which case we need the runtime type metadata for \texttt{Pair<T>}. When compiling the declaration of \texttt{Pair}, the compiler emits a \emph{metadata access function} which takes the type metadata for \texttt{T} as an argument. The metadata access function calculates the layout of \texttt{Pair<T>} for this \texttt{T} with the same algorithm as the compiler, but at runtime, and caches the result.
Note that the runtime type metadata for \texttt{Pair<Int>} has two parts:
\begin{enumerate}
\item A common prefix present in all runtime type metadata, which includes the total size and alignment of a value.
\item A private area specific to the declaration of \texttt{Pair<T>}, such as the \emph{field offset vector} storing the starting offset of each field within a value.
\end{enumerate}
The first part comes into play if we call our \verb|identity(_:)| function with a value of type \texttt{Pair<Int>}. The generated code for the call invokes a metadata access function for \texttt{Pair<T>} with the metadata for \texttt{Int} as an argument, and passes the resulting metadata for \texttt{Pair<Int>} to \verb|identity(_:)|. The implementation of \verb|identity(_:)| doesn't know that it is dealing with a \texttt{Pair<Int>}, but it uses the provided metadata to abstractly manipulate the value.
The second part is used by the constructor implementation. The constructor does not have a generic parameter list of its own, but it is nested inside of a generic type, so it inherits the generic signature of the type, which is \texttt{<T>}. The interface type of this constructor is the generic function type:
\begin{quote}
\begin{verbatim}
<T> (T, T) -> Pair<T>
\end{verbatim}
\end{quote}
Recall our declaration of the \texttt{twoIntegers} variable. Let's complete the declaration by writing down an initial value expression which calls the constructor:
\begin{Verbatim}
let twoIntegers: Pair<Int> = Pair(first: 1, second: 2)
\end{Verbatim}
At the call site, we have full knowledge of the layout of \texttt{twoIntegers}. However, the implementation of \texttt{Pair.init} only knows that it is working with a \texttt{Pair<T>}, and not a \texttt{Pair<Int>}. The generated code for the constructor calls the metadata access function for \texttt{Pair<T>} with the provided metadata for \texttt{T}. Since it knows it is working with a \texttt{Pair<T>}, it can look inside the private area to get the field offset of \texttt{first} and \texttt{second}, and assign the two parameters into the \texttt{first} and \texttt{second} stored properties of \texttt{self}.
\begin{MoreDetails}
\item Type declarations: Section~\ref{type declarations}
\item Context substitution map: Section~\ref{contextsubstmap}
\end{MoreDetails}
\section{Protocols}
Our \verb|identity(_:)| function and the \texttt{Pair} type did not state any generic requirements, so they couldn't do much with their generic values except pass them around, which the compiler expresses in terms of the fundamental value operations---move, copy and destroy.
\index{generic requirement}
\index{conformance requirement}
\index{opaque parameter}
\index{where clause}
We can do more interesting things with our generic parameter types by writing down generic requirements. The most important kind is the \emph{protocol conformance requirement}, which states that the replacement type for a generic requirement must conform to the given protocol.
\begin{Verbatim}
protocol Shape {
func draw()
}
func drawShapes<S: Shape>(_ shapes: [S]) {
for shape in shapes {
shape.draw()
}
}
\end{Verbatim}
The \verb|drawShapes(_:)| function takes an array of values whose type conforms to \texttt{Shape}. You can also write the declaration of \verb|drawShapes(_:)| using a trailing \texttt{where} clause, or avoid the explicit generic parameter list altogether and declare an \emph{opaque parameter type} instead:
\begin{Verbatim}
func drawShapes<S>(_ shapes: [S]) where S: Shape
func drawShapes(_ shapes: [some Shape])
\end{Verbatim}
\index{generic signature}
The generic signatures we've seen previously were rather trivial, only storing a single generic parameter type. More generally, a generic signature actually consists of a list of generic parameter types together with a list of requirements. Irrespective of the surface syntax, the generic signature of \verb|drawShape(_:)| will have a single requirement. We will use the following notation for generic signatures with requirements:
\begin{quote}
\begin{verbatim}
<S where S: Shape>
\end{verbatim}
\end{quote}
The interface type of \verb|drawShapes(_:)| is a generic function type incorporating this generic signature:
\begin{quote}
\begin{verbatim}
<S where S: Shape> (S) -> ()
\end{verbatim}
\end{quote}
\index{qualified lookup}
Inside the body of \verb|drawShapes(_:)|, the \texttt{shape} local variable bound by the \texttt{for}~loop is a value of type \archetype{S} (remember, generic parameter types become archetype types inside the function body; but as before, the distinction doesn't matter right now). Since \texttt{S} is subject to the conformance requirement \verb|S: Shape|, we can call the \texttt{draw()} method of the \texttt{Shape} protocol on \texttt{shape}. More precisely, a \emph{qualified lookup} of the identifier \texttt{draw} with a base type of \archetype{S} will find the \texttt{draw()} method of \texttt{Shape} as a consequence of the conformance requirement.
\index{witness table}
How does the compiler generate code for the call \verb|shape.draw()|? Once again, we need to introduce some indirection. For each conformance requirement in the generic signature of a generic function, the generic function receives a \emph{witness table} from the caller. The layout of a witness table is determined by the protocol's requirements; a method becomes an entry storing a function pointer. To call our protocol method, the compiler loads the function pointer from the witness table, and invokes it with the argument value of \texttt{shape}.
Note that \verb|drawShapes(_:)| operates on a homogeneous array of shapes. While the array contains an arbitrary number of elements, \verb|drawShapes(_:)| only receives a single runtime type metadata for \texttt{S}, and one witness table for the conformance requirement \verb|S: Shape|, which together describe all elements of the array.
\begin{MoreDetails}
\item Protocols: Section~\ref{protocols}
\item Constraint types: Section~\ref{constraints}
\item Trailing \texttt{where} clauses: Section~\ref{trailing where clauses}
\item Opaque parameters: Section~\ref{opaque parameters}
\item Name lookup: Section~\ref{name lookup}
\end{MoreDetails}
\index{conformance}
\index{normal conformance}
\paragraph{Conformances} We can write a struct declaration conforming to \texttt{Shape}:
\begin{Verbatim}
struct Circle: Shape {
let radius: Double
func draw() {...}
}
\end{Verbatim}
The declaration of \texttt{Circle} states a \emph{conformance} to the \texttt{Shape} protocol in its inheritance clause. The type checker constructs an object called a \emph{normal conformance}, which records the mapping from the protocol's requirements to the members of the conforming type which \emph{witness} those requirements.
When the compiler generates the code for the declaration of \texttt{Circle}, it emits a witness table for each normal conformance defined on the type declaration. In our case, there is just a single requirement \texttt{Shape.draw()}, witnessed by the method \texttt{Circle.draw()}. The witness table for this conformance references the witness (indirectly, because the witness is always wrapped in a \emph{thunk}, which is a small function which shuffles some registers around and then calls the actual witness. This must be the case because protocol requirements use a slightly different calling convention than ordinary generic functions).
Now, let's look at a call to \verb|drawShape(_:)| with an array of circles:
\begin{Verbatim}
drawShapes([Circle(radius: 1), Circle(radius: 2)])
\end{Verbatim}
Recall that a reference to a generic function declaration comes with a substitution map. Substitution maps store a replacement type for each generic parameter of a generic signature, so our substitution map maps \texttt{S} to the replacement type \texttt{Circle}. When the generic signature has conformance requirements, the substitution map also stores a conformance for each conformance requirement. This is the ``proof'' that the concrete replacement type actually conforms to the protocol.
\index{global conformance lookup}
The type checker finds conformances by \emph{global conformance lookup}. The call to \verb|drawShape(_:)| will only type check if the replacement type conforms to \texttt{Shape}; the type checker rejects a call that provides an array of integers for example, because there is no conformance of \texttt{Int} to \texttt{Shape}.\footnote{Of course, you could define this conformance with an extension.}
We will use the following notation for substitution maps storing a conformance:
\[\SubMapC{\SubType{S}{Circle}}{\SubConf{Circle:\ Shape}}\]
When emitting code to call to a generic function, the compiler looks at the substitution map and emits a reference to runtime type metadata for each replacement type, and a reference to the witness table for each conformance. In our case, \verb|drawShapes(_:)| takes a single runtime type metadata and a single witness table for the conformance. (The contents of the witness table were emitted when compiling the declaration of \texttt{Circle}; compiling the substitution map references this existing witness table.)
\begin{MoreDetails}
\item Conformances: Chapter~\ref{conformances}
\item Conformance lookup: Section~\ref{conformance lookup}
\end{MoreDetails}
\index{declaration reference type representation}
\index{associated type}
\paragraph{Associated types} Perhaps the simplest example of a protocol with an associated type is the \texttt{Iterator} protocol in the standard library. This protocol abstracts over an iterator which produces elements of a type that depends on the conformance:
\begin{Verbatim}
protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}
\end{Verbatim}
Consider a generic function which returns the first element produced by an iterator:
\begin{Verbatim}
func firstElement<I: IteratorProtocol>(_ iter: inout I) -> I.Element {
return iter.next()!
}
\end{Verbatim}
The return type of our function is the \emph{declaration reference type representation} \texttt{I.Element} with two components, ``\texttt{I}'' and ``\texttt{Element}''. Type resolution resolves this type representation to a type by performing a qualified lookup of \texttt{Element} on the base type \texttt{I}. The generic parameter type \texttt{I} is subject to a conformance requirement, and qualified lookup finds the associated type declaration \texttt{Element}.
\index{dependent member type}
The resolved type is a \emph{dependent member type} composed from the generic parameter type \texttt{I} and associated type declaration \texttt{Element}. We will denote this dependent member type as \verb|I.[IteratorProtocol]Element| to make explicit the fact that a name lookup has resolved the identifier \texttt{Element} to an associated type.
The interface type of \verb|firstElement(_:)| is therefore this generic function type:
\begin{quote}
\begin{verbatim}
<I where I: IteratorProtocol>
(inout I) -> I.[IteratorProtocol]Element
\end{verbatim}
\end{quote}
\begin{MoreDetails}
\item Declaration reference type representations: Section \ref{declreftyperepr}
\end{MoreDetails}
\index{type parameter}
\paragraph{Type parameters}
A \emph{type parameter} in some fixed generic signature is either a generic parameter type, or a dependent member type whose base type conforms to the protocol of this associated type. The generic signature of \verb|firstElement(_:)| has two valid type parameters:
\begin{quote}
\begin{verbatim}
I
I.[IteratorProtocol]Element
\end{verbatim}
\end{quote}
As with generic parameter types, dependent member types become primary archetypes in the body of a generic function; we can reveal a little more about the structure of primary archetypes now, and say that a primary archetype packages a type parameter together with a generic signature.
Inside the body of \verb|firstElement(_:)|, the result of the call expression \verb|iter.next()!| is the optional type \texttt{\archetype{I.Element}?}, which is force-unwrapped to yield the archetype type \archetype{I.Element}. To manipulate a value of the element type abstractly, the compiler must be able to recover its runtime type metadata.
While metadata for generic parameters is passed in directly, for dependent member types the metadata is recovered from one or more witness tables provided by the caller. A witness table for a conformance to \texttt{IteratorProtocol} stores two entries, one for each of the protocol's requirements:
\begin{itemize}
\item A metadata access function to witness the \texttt{Element} associated type.
\item A function pointer to witness the \texttt{next()} protocol requirement.
\end{itemize}
\index{type witness}
\paragraph{Type witnesses} When a concrete type conforms to a protocol, the normal conformance stores a \emph{type witness} for each of the protocol's associated types; this information is populated by the type checker during conformance checking.
\begin{listing}\captionabove{Iterator producing the natural numbers}\label{natural numbers listing}
\begin{Verbatim}
struct NaturalNumbers: IteratorProtocol {
typealias Element = Int
var x = 0
mutating func next() -> Int? {
defer { x += 1 }
return x
}
}
\end{Verbatim}
\end{listing}
Listing~\ref{natural numbers listing} shows a type that conforms to \texttt{IteratorProtocol} by producing an infinite stream of incrementing integers.
Here, the associated type \texttt{Element} is witnessed by a type alias declaration with an underlying type of \texttt{Int}. This matches the return type of \texttt{NaturalNumbers.next()}. Indeed, we can omit the type alias entirely in this case, and instead rely on \emph{associated type inference} to derive it from the interface type of the witness.
Suppose we call \verb|firstElement(_:)| with a value of type \texttt{NaturalNumbers}:
\begin{Verbatim}
var iter = NaturalNumbers()
print(firstElement(&iter))
\end{Verbatim}
The substitution map for the call stores the replacement type \texttt{NaturalNumbers} and the conformance of \texttt{NaturalNumbers} to \texttt{IteratorProtocol}:
\begin{quote}
\SubMapC{\SubType{I}{NaturalNumbers}}{\SubConf{NaturalNumbers:\ IteratorProtocol}}
\end{quote}
To compute the substituted type of the call, we apply our substitution map to the interface type of \verb|firstElement(_:)|. Substitution transforms the parameter type \texttt{I} to the replacement type \texttt{NaturalNumbers}.
To compute the substituted return type for \verb|I.[IteratorProtocol]Element|, we can look up the type witness in the conformance stored in the substitution map. This is entirely analogous to how the generated code for our function is able to recover the runtime type metadata for this dependent member type from a witness table at run time.
The normal conformance of \verb|NaturalNumbers: IteratorProtocol| can be found in the substitution map, and it stores the type witness for \verb|Element|, which is \verb|Int|. The substituted return type is \verb|Int|, and the substituted function type for the call is therefore:
\begin{quote}
\begin{verbatim}
(inout NaturalNumbers) -> Int
\end{verbatim}
\end{quote}
\begin{MoreDetails}
\item Type witnesses: Section~\ref{type witnesses}
\item Dependent member type substitution: Section~\ref{abstract conformances}
\end{MoreDetails}
\index{associated conformance}
\index{requirement signature}
\paragraph{Associated conformances} Protocols can also impose requirements on their associated types. The \texttt{Sequence} protocol in the standard library is one such example:
\begin{Verbatim}
protocol Sequence {
associatedtype Element
associatedtype Iterator: IteratorProtocol
where Element == Iterator.Element
func makeIterator() -> Iterator
}
\end{Verbatim}
There are two requirements here:
\begin{enumerate}
\item The conformance requirement \verb|Iterator: IteratorProtocol|, which is written as a constraint type in the inheritance clause of the \texttt{Iterator} associated type.
\item The same-type requirement \verb|Element == Iterator.Element|, written in a trailing \texttt{where} clause.
\end{enumerate}
Requirements on the generic parameters of a generic function or generic type are collected in the declaration's generic signature. A protocol analogously has a \emph{requirement signature} which collects the requirements imposed on its associated types. A protocol always declares a single generic parameter named \texttt{Self}, and our notation for a requirement signature looks like a generic signature over the protocol \texttt{Self} type:
\begin{quote}
\begin{verbatim}
<Self where Self.[Sequence]Element ==
Self.[Sequence]Iterator.[IteratorProtocol]Element,
Self.[Sequence]Iterator: IteratorProtocol>
\end{verbatim}
\end{quote}
The conformance requirement \verb|Self.[Sequence]Iterator: IteratorProtocol| is an \emph{associated conformance requirement}, and associated conformance requirements appear in protocol witness tables. Therefore a witness table for a conformance to \texttt{Sequence} has \emph{four} entries:
\begin{enumerate}
\item A metadata access function to witness the \texttt{Element} associated type.
\item A metadata access function to witness the \texttt{Iterator} associated type.
\item A witness table access function to witness the associated conformance requirement \verb|Iterator: IteratorProtocol|.
\item A function pointer to the witness the \texttt{makeIterator()} protocol requirement.
\end{enumerate}
\index{abstract conformance}
\paragraph{Abstract conformances}
Let's define a \verb|firstElementSeq(_:)| function which operates on a sequence.\footnote{We could give both functions the same name and take advantage of function overloading, but for clarity we're not going to do that.} We can call the \verb|makeIterator()| protocol requirement to create an iterator for our sequence, and then hand off this iterator to the \verb|firstElement(_:)| function we defined previously:
\begin{Verbatim}
func firstElementSeq<S: Sequence>(_ sequence: S) -> S.Element {
var iter = sequence.makeIterator()
return firstElement(&iter)
}
\end{Verbatim}
The substitution map for the call to \verb|firstElement(_:)| is interesting. The argument \texttt{iter} has the type \archetype{S.Element}, which becomes the replacement type for the generic parameter \texttt{I} of \verb|firstElement(_:)|. Recall that this substitution map also needs to store a conformance. Since the conforming type is an archetype and not a concrete type, global conformance lookup returns an \emph{abstract conformance}. So our substitution map looks like this:
\[\SubMapC{\SubType{I}{\archetype{S.Iterator}}}{\SubConf{\archetype{S.Iterator}:\ IteratorProtocol}}\]
When generating code for the call, we need to emit runtime type metadata for \texttt{I} as well as a witness table for \verb|I: IteratorProtocol|. Both of these are recovered from the witness table for the conformance \verb|S: Sequence| that was passed by the caller of \verb|firstElementSeq(_:)|:
\begin{enumerate}
\item The replacement type for \texttt{I} is \archetype{S.Iterator}. Runtime type metadata for this type is recovered by calling the metadata access function for the \texttt{Iterator} associated type stored in the \verb|S: Sequence| witness table.
\item The conformance for \verb|I: Iterator| is an abstract conformance. We know the type \archetype{S.Iterator} conforms to \verb|IteratorProtocol| because the \texttt{Sequence} protocol says that it does. Therefore, the witness table for this conformance is recovered by calling the witness table access function for the \verb|Iterator: IteratorProtocol| associated conformance in our \verb|S: Sequence| witness table.
\end{enumerate}
Recall that the shape of the substitution map is determined by the generic signature of the callee. In our earlier examples, the replacement types and conformances were fully concrete, which allowed us to emit runtime type metadata and witness tables for a call by referencing global symbols.
More generally, the replacement types and conformances are defined in terms of the type parameters of the caller's generic signature. This makes sense, because we start with the runtime type metadata and witness tables received by the caller, from which we recover the runtime metadata and witness tables required by the callee. Here, the caller is \verb|firstElementSeq(_:)| and the callee is \verb|firstElement(_:)|.
\section{Language Comparison}
\index{C++}
\index{Java}
\index{Rust}
Swift generics occupy a unique point in the design space, which avoids some of the tradeoffs inherent in the design of other popular languages:
\begin{itemize}
\item C++ templates do not allow for separate compilation and type checking. When a template declaration is compiled, only minimal semantic checks are performed and no code is actually generated. The body of a template declaration must be visible at each expansion point, and full semantic checks are performed after template expansion. There is no formal notion of requirements on template parameters; at a given expansion point, template expansion either succeeds or fails depending on how the substituted template parameters are used in the body of the template.
\item Rust generics are separately type checked with the use of generic requirements. Unlike C++, specialization is not part of the semantic model of the language, but it is mandated by the implementation because Rust does not define a calling convention for unspecialized generic code. After type checking, the compiler completely specializes all usages of generic definitions for every set of provided generic arguments.
\item Java generics are separately type checked and compiled. Only reference types can be used as generic arguments; primitive value types must be boxed on the heap. The implementation strategy uses a uniform runtime layout for all generic types, and generic argument types are not reified at runtime. This avoids the complexity of generic type layout at the virtual machine level, but it comes at the cost of runtime type checks and heap allocation.
\end{itemize}
We can summarize this with a table.
\begin{quote}
\begin{tabular}{|l|>{\centering}p{1.3cm}|>{\centering}p{1.3cm}|>{\centering}p{1.3cm}|>{\centering\arraybackslash}p{1.3cm}|}
\hline
&C++&Rust&Java&Swift\\
\hline
Separate compilation&$\times$&$\times$&\checkmark&\checkmark\\
Specialization&\checkmark&$\checkmark$&$\times$&\checkmark\\
Generic requirements&$\times$&$\checkmark$&$\checkmark$&\checkmark\\
Unboxed values&\checkmark&\checkmark&$\times$&\checkmark\\
\hline
\end{tabular}
\end{quote}
\chapter{Compilation Model}\label{compilation model}
\index{Xcode}
\index{Swift package manager}
\index{Swift driver}
\index{shared library}
\index{framework}
Most developers interact with the Swift compiler through Xcode and the Swift package manager, but for simplicity let's just consider direct invocation of \texttt{swiftc} from the command line. You can invoke \texttt{swiftc}, passing a list of all source files in your module as command line arguments:
\begin{Verbatim}
$ swiftc m.swift v.swift c.swift
\end{Verbatim}
The \texttt{swiftc} command runs the \emph{Swift driver}. By default, the driver emits an executable. When building frameworks (or libraries, if you're not versed in Apple jargon), the driver is invoked with the \texttt{-emit-library} and \texttt{-emit-module} flags, which generate a shared library and binary module file instead. Binary modules are consumed by the compiler when importing the framework, and are discussed in Section~\ref{module system}.
\index{main function}
\index{main source file}
\index{top-level code declaration}
Executables must define a \emph{main function}, which is the entry point invoked when the executable is run. There are three mechanisms for doing so:
\begin{enumerate}
\item If the module consists of a single source file, or if there are multiple source files and one of them is named \texttt{main.swift}, then this file becomes the \emph{main source file} of the module. The main source file can contain statements at the top level, outside of a function body; consecutive top-level statements are collected into \emph{top-level code declarations}. The main function executes the statements of each top-level code declaration in order. Source files other than the main source file cannot contain top-level code declarations.
\item If a struct, enum or class declaration is annotated with the \texttt{@main} attribute, the declaration must contain a static method named \texttt{main()}; this method becomes the main entry point. This attribute was introduced in Swift 5.3~\cite{se0281}.
\item The \texttt{@NSApplicationMain} and \texttt{@UIApplicationMain} attributes are an older way to specify the main entry point on Apple platforms. When applied to a class adopting the \texttt{NSApplicationMain} or \texttt{UIApplicationMain} protocol, a main entry point is generated which calls the \texttt{NSApplicationMain()} or \texttt{UIApplicationMain()} system framework function.
\end{enumerate}
\index{frontend job}
\index{Swift frontend}
\index{batch mode}
\index{whole module optimization}
\index{single file mode}
The Swift driver schedules \emph{frontend jobs} to perform the actual compilation work. Each frontend job runs the \emph{Swift frontend} process, which is what compiler developers think of as ``the compiler.'' Multiple frontend jobs can run in parallel, leveraging multi-core concurrency. By default, the number of concurrent frontend jobs is determined by the number of CPU cores; this can be overridden with the \texttt{-j} driver flag. If there are more frontend jobs than can be run simultaneously, the driver queues them and kicks them off as other frontend jobs complete.
Source files are divided among frontend jobs according to the \emph{compilation mode}:
\begin{enumerate}
\item In \emph{batch mode}, source files are partitioned into fixed-size batches, up to the maximum batch size. Each frontend job compiles the source files of a single batch. This is the default.
\item In \emph{single file mode}, there is frontend job per source file, which is effectively the same as batch mode with a maximum batch size of one. Single file mode is only used for debugging and performance testing the compiler itself. The \texttt{-disable-batch-mode} command line flag instructs the driver to run in single file mode.
\item In \emph{whole module optimization mode}, there is no parallelism; a single frontend job is scheduled to build all source files. This trades build time for quality of generated code, because the compiler is able to perform more aggressive optimization across source file boundaries. The \texttt{-wmo} driver flag enables whole module optimization.
\end{enumerate}
The Swift frontend itself is single-threaded, therefore a source file is the minimum unit of parallelism.
\index{incremental build}
In batch mode and single file mode, the driver can also perform an \emph{incremental build} by re-using the result of previous compilations, providing an additional compile-time speedup. Incremental builds are described in Section~\ref{request evaluator}.
\index{primary file}
\index{secondary file}
The driver invokes the frontend with a list of \emph{primary files} and \emph{secondary files}. The primary files are those that this specific frontend job is tasked with building, and the secondary files are the remaining source files in the module. Each source file is a primary file of exactly one frontend job, and each frontend job's primary files and secondary files together form the full list of source files in the module.
The \verb|-###| driver flag performs a ``dry run'' which prints all commands to run without actually doing anything.
\begin{Verbatim}
$ swiftc m.swift v.swift c.swift -###
swift-frontend -frontend -c -primary-file m.swift v.swift c.swift ...
swift-frontend -frontend -c m.swift -primary-file v.swift c.swift ...
swift-frontend -frontend -c m.swift v.swift -primary-file c.swift ...
ld m.o v.o c.o -o main
\end{Verbatim}
In the above, we're performing a batch mode build, but the module only has three source files, so for maximum parallelism each batch consists of a single source file. Therefore, each frontend job has a single primary file, with the other two source files becoming the secondary files for the job. The final command is the linker invocation, which combines the output of each frontend job into our binary executable.
\begin{figure}\captionabove{The compilation pipeline}\label{compilerpipeline}
\begin{center}
\begin{tikzpicture}[node distance=1.5cm]
\tikzstyle{stage} = [rectangle, draw=black, text centered]
\tikzstyle{arrow} = [->,>=stealth]
\node (Parse) [stage] {Parse};
\node (Sema) [stage, below of=Parse] {Sema};
\node (SILGen) [stage, below of=Sema] {SILGen};
\node (SILOptimizer) [stage, below of=SILGen] {SILOptimizer};
\node (IRGen) [stage, below of=SILOptimizer] {IRGen};
\node (LLVM) [stage, below of=IRGen] {LLVM};
\draw [arrow] (Parse) -- (Sema);
\draw [arrow] (Sema) -- (SILGen);
\draw [arrow] (SILGen) -- (SILOptimizer);
\draw [arrow] (SILOptimizer) -- (IRGen);
\draw [arrow] (IRGen) -- (LLVM);
\end{tikzpicture}
\end{center}
\end{figure}
\medskip
\index{parser}
\index{Sema}
\index{SILGen}
\index{SIL optimizer}
\index{IRGen}
\index{LLVM}
\index{SIL mandatory pass}
\index{SIL performance pass}
\index{raw SIL}
\index{canonical SIL}
The frontend implements a classic multi-stage compiler pipeline, shown in Figure~\ref{compilerpipeline}:
\begin{itemize}
\item \textbf{Parse:} First, all source files are parsed into an abstract syntax tree.
\item \textbf{Sema:} Semantic analysis type-checks and validates the abstract syntax tree.
\item \textbf{SILGen:} The type-checked syntax tree is lowered to \emph{raw} SIL.
\item \textbf{SILOptimizer:} The raw SIL is transformed into \emph{canonical} SIL by a series of \emph{mandatory passes}, which analyze the control flow graph and emit diagnostics; for example, \emph{definite initialization} ensures that all storage locations are initialized.
When the \texttt{-O} command line flag is specified, the canonical SIL is further optimized by a series of \emph{performance passes} with the goal of improving run-time performance and reducing code size.
\item \textbf{IRGen:} The optimized SIL is then transformed into LLVM IR.
\item \textbf{LLVM:} Finally, the LLVM IR is handed off to LLVM, which performs various lower level optimizations before generating machine code.
\end{itemize}
Each pipeline phase can emit warnings and errors. The parser attempts to recover from errors; the presence of parse errors does not prevent Sema from running. On the other hand, if Sema emits errors, compilation stops; SILGen does not attempt to lower an invalid abstract syntax tree to SIL.
\index{TBD}
\index{textual interface}
The pipeline will be slightly different depending on what the driver and frontend were asked to produce. When the frontend is instructed to emit a binary module file only, and not an object file, compilation stops after the SIL optimizer. When generating a textual interface file or TBD file, compilation stops after Sema. (Textual interfaces are discussed in Section~\ref{module system}. A TBD file is a list of symbols in a shared library, which can be consumed by the linker and is faster to generate than the shared library itself; we're not going to talk about them here.)
\index{synthesized declaration}
\index{s-expression}
\index{Lisp}
\index{assembly language}
Various command-line flags print the output of each phase to the terminal (or some other file in conjunction with the \texttt{-o} flag), useful for debugging the compiler:
\begin{itemize}
\item \texttt{-dump-parse} prints the parsed syntax tree as an s-expression.\footnote{The term comes from Lisp. An s-expression represents a tree structure as nested parenthesized lists; e.g.\ \texttt{(a (b c) d)} is a node with three children \texttt{a}, \texttt{(b c)} and \texttt{d}, and \texttt{(b c)} has two children \texttt{b} and \texttt{c}.}
\item \texttt{-dump-ast} prints the type-checked syntax tree as an s-expression.
\item \texttt{-print-ast} prints the type-checked syntax tree in a form that approximates what was written in source code. This is useful for getting a sense of what declarations the compiler synthesized, for example for derived conformances to protocols like \texttt{Equatable}.
\item \texttt{-emit-silgen} prints the raw SIL output by SILGen.
\item \texttt{-emit-sil} prints the canonical SIL output by the SIL optimizer. To see the output of the performance pipeline, also pass \texttt{-O}.
\item \texttt{-emit-ir} prints the LLVM IR output by IRGen.
\item \texttt{-S} prints the assembly output by LLVM.
\end{itemize}
\index{frontend flag}
Some command-line flags, such as those listed above, are understood by both the driver and the frontend. Certain other flags used for compiler development and debugging and only known to the frontend.
If the driver is invoked with the \texttt{-frontend} flag as the first command line flag, then instead of scheduling frontend jobs, the driver spawns a single frontend job, passing it the rest of the command line without further processing:
\begin{Verbatim}
$ swiftc -frontend -typecheck -primary-file a.swift b.swift
\end{Verbatim}
Another mechanism for passing flags to the frontend is the \texttt{-Xfrontend} flag. When this flag appears in a command-line invocation of the driver, the command line argument that comes immediately after is passed to the frontend:
\begin{Verbatim}
$ swiftc a.swift b.swift -Xfrontend -dump-requirement-machine
\end{Verbatim}
The SIL intermediate form is described in \cite{sil}.
\section{Name Lookup}\label{name lookup}
\index{qualified lookup}
\index{unqualified lookup}
Name lookup is the process of resolving identifiers to declarations. The Swift compiler does not have a distinct ``name binding'' phase; instead, name lookup is queried from various points in the compilation process. Broadly speaking, there are two kinds of name lookup: \emph{unqualified lookup} and \emph{qualified lookup}. An unqualified lookup resolves a single identifier \texttt{foo}, while qualified lookup resolves an identifier \texttt{bar} relative to a base, such as \texttt{foo.bar}. There are also three important variations which are described immediately after the two fundamental kinds.
\paragraph{Unqualified lookup}
An unqualified lookup is always performed relative to the source location where the identifier actually appears. The source location may be inside of a primary file or secondary file.
The first time an unqualified lookup is performed inside a source file, a \emph{scope tree} is constructed by walking the source file's abstract syntax tree. The root scope is the source file itself. Each scope has an associated source range, and zero or more child scopes; each child scope's source range must be a subrange of the source range of its parent, and the source ranges of sibling scopes are disjoint. Each scope introduces zero or more \emph{variable bindings}.
\index{top-level lookup}
\index{scope tree}
\index{source range}
\index{source location}
Unqualified lookup first finds the innermost scope containing the source location, and proceeds to walk the scope tree up to the root, searching each parent node for bindings named by the given identifier. If the lookup reaches the root node, a \emph{top-level lookup} is performed next. This will look for top-level declarations named by the given identifier, first in all source files of the current module, followed by all imported modules.
\index{direct lookup}
\paragraph{Qualified lookup}
A qualified lookup looks inside a list of type declarations for members with a given name. Starting from an initial list of type declarations, qualified lookup also visits the superclass of a class declaration, and conformed protocols.
The more primitive operation performed at each step is called a \emph{direct lookup}, which searches inside a single type declaration and its extensions only, by consulting the type declaration's \emph{lookup table}.
\index{module lookup}
\paragraph{Module lookup} A qualified lookup where the base is a module declaration searches for a top-level declaration in the given module and any other modules that it re-exports via \texttt{@\_exported import}.
\index{dynamic lookup}
\index{AnyObject lookup}
\index{Objective-C}
\paragraph{Dynamic lookup} A qualified lookup where the base is the \texttt{AnyObject} type implements the legacy Objective-C behavior of a message send to \texttt{id}, which can invoke any method defined in any Objective-C class or protocol. In Swift, a dynamic lookup searches a global lookup table constructed from all \texttt{@objc} members of all classes and protocols. Any class can contain \texttt{@objc} members; the attribute can either be explicitly stated, or inferred if the method overrides an \texttt{@objc} method from the superclass. Protocol members are \texttt{@objc} only if the protocol itself is \texttt{@objc}.
\index{partial order}
\paragraph{Operator lookup}
Operator symbols are declared at the top level of a module. Operator symbols have a fixity (prefix, infix, or postfix), and infix operators also have a \emph{precedence group}. Precedence groups are partially ordered with respect to other precedence groups. Standard operators like \texttt{+} and \texttt{*} and their precedence groups are thus defined in the standard library, rather than being built-in to the language itself.
\index{sequence expression}
\index{operator symbol}
\index{precedence group}
\index{operator lookup}
An arithmetic expression like \texttt{2 + 3 * 6} is parsed as a \emph{sequence expression}, which is a flat list of nodes and operator symbols. The parser does not know the precedence, fixity or associativity of the \texttt{+} and \texttt{*} operators. Indeed, it does not know that they exist at all. The \emph{pre-check} phase of the expression type checker looks up operator symbols and transforms sequence expressions into the more familiar nested tree form.
Operator symbols do not themselves have an implementation; they are just names. An operator symbol can be used as the name of a function implementing the operator on a specific type (for prefix and postfix operators) or a specific pair of types (for infix operators). Operator functions can be declared either at the top level, or as a member of a type. As far as a name lookup is concerned, the interesting thing about operator functions is that they are visible globally, even when declared inside of a type. Operator functions are found by consulting the operator lookup table, which contains top-level operator functions as well as member operator functions of all declared types.
When the compiler type checks the expression \texttt{2 + 3 * 6}, it must pick two specific operator functions for \texttt{+} and \texttt{*} among all the possibilities in order to make this expression type check. In this case, the overloads for \texttt{Int} are chosen, because \texttt{Int} is the default literal type for the literals \texttt{2}, \texttt{3} and \texttt{6}.
\begin{listing}\captionabove{Operator lookup in action}\label{customops}
\begin{Verbatim}
prefix operator <&>
infix operator ++: MyPrecedence
infix operator **: MyPrecedence
precedencegroup MyPrecedence {
associativity: right
higherThan: AdditionPrecedence
}
// Member operator examples
struct Chicken {
static prefix func <&>(x: Chicken) {}
static func ++(lhs: Chicken, rhs: Chicken) -> Int {}
}
struct Sausage {
static func ++(lhs: Sausage, rhs: Sausage) -> Bool {}
}
// Top-level operator example
func **(lhs: Sausage, rhs: Sausage) -> Sausage {}
// Global operator lookup finds Sausage.++
// `fn' has type (Sausage, Sausage) -> Bool
let fn = { ($0 ++ $1) as Bool }
\end{Verbatim}
\end{listing}
Listing~\ref{customops} shows the definition of some custom operators and precedence groups. Note that the overload of \texttt{++} inside struct \texttt{Chicken} returns \texttt{Int}, and the overload of \texttt{++} inside struct \texttt{Sausage} returns \texttt{Bool}. The closure value stored in \texttt{fn} applies \texttt{++} to two anonymous closure parameters, \verb|$0| and \verb|$1|. While they do not have declared types, by simply coercing the \emph{return type} to \texttt{Bool}, we are able to unambiguously pick the overload of \texttt{++} declared in \texttt{Sausage}. (Whether this is good style is an exercise for the reader.)
Initially, infix operators defined their precedence as an integer value; Swift 3 introduced named precedence groups \cite{se0077}. The global lookup for operator functions dates back to when all operator functions were declared at the top level. Swift~3 also introduced the ability to declare operator functions as members of types, but the global lookup behavior was retained \cite{se0091}.
\section{Delayed Parsing}
\index{primary file}
\index{secondary file}
The above ``compilation pipeline'' model is a simplification of the actual state of affairs. Recall that in the case where the driver schedules multiple frontend jobs, the list of source files is partitioned into disjoint subsets, where each subset becomes the primary files of some frontend job. Ultimately, each frontend job only needs to generate machine code from the declarations in its primary files, so all stages from SILGen onward operate on the frontend job's primary files only.
However, the situation with parsing and type checking is more subtle. At a minimum, each frontend job must parse and type check its primary files. Furthermore, the partition of source files into frontend jobs is artificial and not visible to the user, and certainly a declaration in a primary file can reference declarations in secondary files. Therefore, in the general case, the abstract syntax tree for all secondary files must be available to a frontend job as well. On the other hand, it would be inefficient if every frontend job was required to fully parse all secondary files, because the time spent in the parser would be proportional to the number of frontend jobs multiplied by the number of source files, negating the benefits of parallelism.
The \emph{delayed parsing} optimization solves this dilemma. When parsing a secondary file for the first time, syntax tree nodes for the bodies of top-level types, extensions and functions are not actually built. Instead, the parser operates in a high-speed mode where comments are skipped and pairs of braces are matched, but very little other work is performed. This constructs a ``skeleton'' representation of each secondary file. If the body of a type or extension in a secondary file is needed later---for example, because the type checking of a declaration in a primary file needs to perform a name lookup into this type---the source range of the declaration is parsed again, this time building the full syntax tree.
\index{operator lookup}
Operator lookup is incompatible with delayed parsing, because operator functions defined inside types are globally visible, as explained in the previous section. To deal with this, the parser looks for the keyword ``\texttt{func}'' followed by an operator symbol when skipping a type or extension body in a secondary file. The presence of this token sequence effectively disables delayed parsing for this declaration, because the first time an operator lookup is performed in the expression pre-checking pass, the bodies of all types containing operator functions are parsed again. Most types and extensions do not define operator functions, so this occurs rarely in practice.
\index{AnyObject lookup}
\index{dynamic lookup}
\index{Objective-C}
The situation with \texttt{AnyObject} lookup is similar, since a method call on a value of type \texttt{AnyObject} must consult a global lookup table constructed from \texttt{@objc} members of classes, and the (implicitly \texttt{@objc}) members of \texttt{@objc} protocols. Unlike operator functions, classes and \texttt{@objc} protocols are quite common in Swift programs, so it would be unfortunate to penalize compile-time performance when \texttt{AnyObject} is a rarely-used feature. Instead, the solution is to eagerly parse classes and \texttt{@objc} protocols the first time a frontend job encounters a dynamic \texttt{AnyObject} method call.
There's actually one more complication here. Classes can be nested inside of other types, whose bodies are skipped if they appear in a secondary file. This is resolved with the same trick as operator lookup. When skipping the body of a type, the parser looks for occurrences of the ``\texttt{class}'' keyword. If the body contains this keyword, this type is parsed and its members visited recursively when building the \texttt{AnyObject} global lookup table.
Most Swift programs, even those making heavy use of Objective-C interoperability, do not contain a dynamic \texttt{AnyObject} method call in every source file, so delayed parsing remains effective.
\begin{example}\label{anyobjectdelayedparseex}
Listing~\ref{anyobjectdelayedparse} shows an example of this behavior. This program consists of three files. Suppose that the driver kicks off three frontend jobs, with a single primary file for each frontend job:
\begin{itemize}
\item The frontend job with the primary file \texttt{a.swift} will parse \texttt{b.swift} and \texttt{c.swift} as secondary files. The body of \texttt{g()} in \texttt{b.swift} is skipped, and the body of \texttt{Outer} in \texttt{c.swift} is skipped. The parser makes a note that \texttt{Outer} contains the \texttt{class} keyword. The function \texttt{f()} in \texttt{a.swift} contains a dynamic \texttt{AnyObject} method call, so this frontend job will construct the global lookup table, triggering parsing of \texttt{Outer} and \texttt{Inner} in \texttt{c.swift}.
\item The frontend job with the primary file \texttt{b.swift} will parse \texttt{a.swift} and \texttt{c.swift} as secondary files. This primary file does not reference anything from \texttt{c.swift} at all, so \texttt{Outer} remains unparsed in this frontend job. Type checking the call to \texttt{f()} from \texttt{g()} also does not require parsing the \emph{body} of \texttt{f()}.
\item The frontend job with the primary file \texttt{c.swift} will parse \texttt{a.swift} and \texttt{b.swift} as secondary files, skipping parsing the bodies of \texttt{f()} and \texttt{g()}.
\end{itemize}
\end{example}
\begin{listing}\captionabove{Delayed parsing with \texttt{AnyObject} lookup}\label{anyobjectdelayedparse}
\begin{Verbatim}
// a.swift
func f(x: AnyObject) {
x.foo()!
}
\end{Verbatim}
\begin{Verbatim}
// b.swift
func g() {
f()
}
\end{Verbatim}
\begin{Verbatim}
// c.swift
struct Outer {
class Inner {
@objc func foo() {}
}
}
\end{Verbatim}
\end{listing}
\begin{example}
It is possible to construct a program where type checking of each primary file triggers complete parsing of all type and extension bodies in every secondary file, either because of pathological dependencies between source files, or extreme reliance on operator lookup and \texttt{AnyObject} lookup. Listing~\ref{defeatdelayparse} shows an example of the first kind. Again, if you assume the driver kicks off three frontend jobs with a single primary file for each frontend job, then each frontend job will eventually parse all type bodies in the other two secondary files.
\end{example}
\begin{listing}\captionabove{Defeating delayed parsing}\label{defeatdelayparse}
\begin{Verbatim}
// x.swift
struct A {
typealias T = B.T
typealias U = C.T
}
\end{Verbatim}
\begin{Verbatim}
// y.swift
struct B {
typealias T = C.T
typealias U = A.T
}
\end{Verbatim}
\begin{Verbatim}
// z.swift
struct C {
typealias T = Int
typealias U = B.T
}
\end{Verbatim}
\end{listing}
\section{Request Evaluator}\label{request evaluator}
\index{request}
\index{request evaluator}
\index{evaluation function}
The \emph{request evaluator} is central to the architecture of the Swift compiler. Essentially, the request evaluator is a framework for performing queries against the abstract syntax tree. A \emph{request} packages a list of input parameters together with an \emph{evaluation function}. With the exception of emitting diagnostics, the evaluation function should be referentially transparent. Only the request evaluator should directly invoke the evaluation function; the request evaluator caches the result of the evaluation function for subsequent requests. As well as caching results, the request evaluator implements automatic cycle detection, and dependency tracking for incremental builds.
The request evaluator is used to implement a form of lazy type checking. We saw from the previous section that in any given frontend job, declarations in primary files can reference declarations in secondary files without restriction. Swift programmers also know that declarations in a source file can also appear in any order; there is no need to forward declare names, and certain kinds of circular references are also permitted.
\index{type-check source file request}
\index{AST lowering request}
\index{interface type request}
\index{generic signature request}
\index{qualified lookup request}
\index{unqualified lookup request}
For this reason the classic compiler design of a single type-checking pass that walks declarations in source order is not well-suited for Swift. Indeed, while the Swift type checker does walk over the declarations in each primary file over source order, instead of directly performing type checking work, it kicks off a series of requests which perform queries against declarations that may appear further down in the primary file, or in other secondary files. The compiler defines over two hundred kinds of requests. Important request kinds include:
\begin{itemize}
\item The \textbf{type-check source file request} is the key entry point into the type checker, explained below.
\item The \textbf{AST lowering request} is the entry point into SILGen, generating SIL from the abstract syntax tree for a source file.
\item The \textbf{unqualified lookup request} and \textbf{qualified lookup request} perform the two kinds of name lookup described in the previous section.
\item The \textbf{interface type request} is explained in Chapter~\ref{decls}.
\item The \textbf{generic signature request} is explained in Chapter~\ref{building generic signatures}.
\end{itemize}
\begin{listing}\captionabove{Forward reference example}\label{forwardref}
\begin{Verbatim}
let food = cook()
func cook() -> Food {}
struct Food {}
\end{Verbatim}
\end{listing}
The \textbf{type-check source file request}'s evaluation function visits each declaration in a primary source file. It is responsible for kicking off enough requests to ensure that SILGen can proceed if all requests succeeded without emitting diagnostics. Consider what happens when type checking the program in Listing~\ref{forwardref}:
\begin{enumerate}
\item The \textbf{type-check source file request} begins by visiting the declaration of \texttt{food} and performing various semantic checks.
\item One of these checks evaluates the \textbf{interface type request} with the declaration of \texttt{food}. This is a variable declaration, so the evaluation function type checks the initial value expression and returns the type of the result.
\begin{enumerate}
\item In order to type check the expression \texttt{cook()}, the \textbf{interface type request} is evaluated again, this time with the declaration of \texttt{cook} as its input parameter.
\item The interface type of \texttt{cook()} has not been computed yet, so the request evaluator calls the evaluation function for this request.
\end{enumerate}
\item After computing the interface type of \texttt{food} and performing other semantic checks, the \textbf{type-check source file request} moves on to the declaration of \texttt{cook}:
\begin{enumerate}
\item The \textbf{interface type request} is evaluated once again, with the input parameter being the declaration of \texttt{cook}.
\item The result was already cached, so the request evaluator immediately returns the cached result without computing it again.
\end{enumerate}
\end{enumerate}
The \textbf{type-check source file request} is special, because it does not return a value; it is evaluated for the side effect of emitting diagnostics, whereas most other requests return a value. The implementation of the \textbf{type-check source file request} guarantees that if no diagnostics were emitted, then SILGen can generate valid SIL for all declarations in a primary file. However, SILGen can still evaluate other requests which result in diagnostics being emitted in secondary files.
\begin{listing}\captionabove{Diagnostic emitted during SILGen}\label{silgendiag}
\begin{Verbatim}
// a.swift
struct Box {
let contents: DoesNotExist
}
\end{Verbatim}
\begin{Verbatim}
// b.swift
func open(_: Box) {}
\end{Verbatim}
\end{listing}
\begin{example}
Listing~\ref{silgendiag} shows a program with two files. The first file declares a struct with a stored property naming a non-existent type. The second file declares a function whose input parameter type is the struct type declared by this struct declaration.
A frontend job with the primary file \texttt{b.swift} and the secondary file \texttt{a.swift} does not emit any diagnostics in the type checking pass, because the stored property \texttt{contents} of \texttt{Box} is not actually referenced.
However when SILGen runs, it needs to determine whether the parameter of type \texttt{Box} to the \texttt{open()} function needs to be passed directly in registers, or via an address by computing the \emph{type lowering} for the \texttt{Box} type. Type lowering recursively visits the stored properties of \texttt{Box} and computes their type lowering; this evaluates the \textbf{interface type request} for the \texttt{contents} property of \texttt{Box}, which emits a diagnostic because the identifier ``\texttt{DoesNotExist}'' does not resolve to a valid type.
\end{example}
The request evaluator framework was first introduced in Swift~4.2 \cite{reqeval}. In subsequent releases, various ad-hoc mechanisms were gradually converted into request evaluator requests, with resulting gains to compiler performance, stability, and implementation maintainability.