# source:doc/theses/fangren_yu_COOP_S20/Report.tex@4f3a4d75

Last change on this file since 4f3a4d75 was 79e261b7, checked in by Peter A. Buhr <pabuhr@…>, 21 months ago

remove repeated pagebackref=true option

• Property mode set to 100644
File size: 35.1 KB
Line
1\documentclass[twoside,11pt]{article}
2
3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4
5% Latex packages used in the document.
6\usepackage{fullpage,times,comment}
7\usepackage{epic,eepic}
8\usepackage{upquote}                                                                    % switch curled '" to straight
9\usepackage{calc}
10\usepackage{varioref}                                                                   % extended references
11\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
12\renewcommand{\thesubfigure}{\alph{subfigure})}
13\usepackage[flushmargin]{footmisc}                                              % support label/reference in footnote
14\usepackage{latexsym}                                   % \Box glyph
15\usepackage{mathptmx}                                   % better math font with "times"
16\usepackage[toc]{appendix}                                                              % article does not have appendix
17\usepackage[usenames]{color}
18\input{common}                                          % common CFA document macros
20\usepackage{breakurl}
21\urlstyle{sf}
22
23% reduce spacing
24\setlist[itemize]{topsep=5pt,parsep=0pt}% global
25\setlist[enumerate]{topsep=5pt,parsep=0pt}% global
26
27\usepackage[pagewise]{lineno}
28\renewcommand{\linenumberfont}{\scriptsize\sffamily}
29
30% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
31% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
32% AFTER HYPERREF.
33\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
34\newcommand{\NOTE}{\textbf{NOTE}}
35\newcommand{\TODO}[1]{{\color{Purple}#1}}
36
37\setlength{\topmargin}{-0.45in}                                                 % move running title into header
39
40%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
41
42\CFAStyle                                                                                               % CFA code-style for all languages
43\lstset{
44language=C++,moredelim=**[is][\color{red}]{@}{@}                % make C++ the default language
45}% lstset
46\lstnewenvironment{C++}[1][]                            % use C++ style
47{\lstset{language=C++,moredelim=**[is][\color{red}]{@}{@}}\lstset{#1}}{}
48
49%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
50
51\setcounter{secnumdepth}{3}                             % number subsubsections
53\makeindex
54
55%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
56
57\title{\Huge
58\lstinline|cfa-cc| Developer's Reference
59}% title
60
61\author{\LARGE
62Fangren Yu
63}% author
64
65\date{
66\today
67}% date
68
69%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70
71\begin{document}
73% changed after setting pagestyle
76\pagenumbering{roman}
77\linenumbers                                            % comment out to turn off line numbering
78
79\maketitle
80\pdfbookmark[1]{Contents}{section}
81\tableofcontents
82
83\clearpage
84\thispagestyle{plain}
85\pagenumbering{arabic}
86
87
88\section{Overview}
89
90@cfa-cc@ is the reference compiler for the \CFA programming language, which is a non-object-oriented extension to C.
91\CFA attempts to introduce productive modern programming language features to C while maintaining as much backward-compatibility as possible, so that most existing C programs can seamlessly work with \CFA.
92
93Since the \CFA project dates back to the early 2000s, and only restarted in the past few years, there is a significant amount of legacy code in the current compiler codebase with little documentation.
94The lack of documentation makes it difficult to develop new features from the current implementation and diagnose problems.
95
96Currently, the \CFA team is also facing poor compiler performance.
97For the development of a new programming language, writing standard libraries is an important component.
98The slow compiler causes building of the library files to take tens of minutes, making iterative development and testing almost impossible.
99There is an ongoing effort to rewrite the core data-structure of the compiler to overcome the performance issue, but many bugs have appeared during this work, and lack of documentation is hampering debugging.
100
101This developer's reference manual begins the documentation and should be continuously im\-proved until it eventually covers the entire compiler codebase.
102For now, the focus is mainly on the parts being rewritten, and also the primary performance bottleneck, namely the resolution algorithm.
103Its aimed is to provide new project developers with guidance in understanding the codebase, and clarify the purpose and behaviour of certain functions that are not mentioned in the previous \CFA research papers~\cite{Bilson03,Ditchfield92,Moss19}.
104
105
106\section{Compiler Framework}
107
108\CFA source code is first transformed into an abstract syntax tree (AST) by the parser before analyzed by the compiler.
109
110
111\subsection{AST Representation}
112
113
114There are 4 major categories of AST nodes used by the compiler, along with some derived structures.
115
116\subsubsection{Declaration Nodes}
117
118A declaration node represents either of:
119\begin{itemize}
120\item
121type declaration: @struct@, @union@, @typedef@ or type parameter (see \VRef[Appendix]{s:KindsTypeParameters})
122\item
123variable declaration
124\item
125function declaration
126\end{itemize}
127Declarations are introduced by standard C declarations, with the usual scoping rules.
128In addition, declarations can also be qualified by the \lstinline[language=CFA]@forall@ clause (which is the origin of \CFA's name):
129\begin{cfa}
130forall ( <$\emph{TypeParameterList}$> | <$\emph{AssertionList}$> )
131        $\emph{declaration}$
132\end{cfa}
133Type parameters in \CFA are similar to \CC template type parameters.
134The \CFA declaration
135\begin{cfa}
136forall (dtype T) ...
137\end{cfa}
138behaves similarly to the \CC template declaration
139\begin{C++}
140template <typename T> ...
141\end{C++}
142
143Assertions are a distinctive feature of \CFA, similar to \emph{interfaces} in D and Go, and \emph{traits} in Rust.
144Contrary to the \CC template where arbitrary functions and operators can be used in a template definition, in a \CFA parametric function, operations on parameterized types must be declared in assertions.
145Consider the following \CC template:
146\begin{C++}
147@template@ forall<typename T> T foo( T t ) {
148        return t + t * t;
149}
150\end{C++}
151where there are no explicit requirements on the type @T@.
152Therefore, the \CC compiler must deduce what operators are required during textual (macro) expansion of the template at each usage.
153As a result, templates cannot be compiled.
154\CFA assertions specify restrictions on type parameters:
155\begin{cfa}
156forall( dtype T | @{ T ?+?( T, T ); T ?*?( T, T ) }@ ) int foo ( T t ) {
157        return t + t * t;
158}
159\end{cfa}
160Assertions are written using the usual \CFA function declaration syntax.
161Only types with operators @+@'' and @*@'' work with this function, and the function prototype is sufficient to allow separate compilation.
162
163Type parameters and assertions are used in the following compiler data-structures.
164
165
166\subsubsection{Type Nodes}
167
168Type nodes represent the type of an object or expression.
169Named types reference the corresponding type declarations.
170The type of a function is its function pointer type (same as standard C).
171With the addition of type parameters, named types may contain a list of parameter values (actual parameter types).
172
173
174\subsubsection{Statement Nodes}
175
176Statement nodes represent the executable statements in the program, including basic expression statements, control flows and blocks.
177Local declarations (within a block statement) are represented as declaration statements.
178
179
180\subsubsection{Expression Nodes}
181
182Some expressions are represented differently before and after the resolution stage:
183\begin{itemize}
184\item
185Name expressions: @NameExpr@ pre-resolution, @VariableExpr@ post-resolution
186\item
187Member expressions: @UntypedMemberExpr@ pre-resolution, @MemberExpr@ post-resolution
188\item
189\begin{sloppypar}
190Function call expressions (including overloadable operators): @UntypedExpr@ pre-resolution, @ApplicationExpr@ post-resolution
191\end{sloppypar}
192\end{itemize}
193The pre-resolution representation contains only the symbols.
194Post-resolution links them to the actual variable and function declarations.
195
196
197\subsection{Compilation Passes}
198
199Compilation steps are implemented as passes, which follows a general structural recursion pattern on the syntax tree.
200
201The basic workflow of compilation passes follows preorder and postorder traversal on the AST data-structure, implemented with visitor pattern, and can be loosely described with the following pseudocode:
202\begin{C++}
203Pass::visit( node_t node ) {
204        previsit( node );
205        if ( visit_children )
206                for each child of node:
207                        child.accept( this );
208        postvisit( node );
209}
210\end{C++}
211Operations in @previsit@ happen in preorder (top to bottom) and operations in @postvisit@ happen in postorder (bottom to top).
212The precise order of recursive operations on child nodes can be found in @Common/PassVisitor.impl.h@ (old) and @AST/Pass.impl.hpp@ (new).
213
214Implementations of compilation passes follow certain conventions:
215\begin{itemize}
216\item
217Passes \textbf{should not} directly override the visit method (Non-virtual Interface principle);
218if a pass desires different recursion behaviour, it should set @visit_children@ to false and perform recursive calls manually within previsit or postvisit procedures.
219To enable this option, inherit from the @WithShortCircuiting@ mixin.
220\item
221previsit may mutate the node but \textbf{must not} change the node type or return @nullptr@.
222\item
223postvisit may mutate the node, reconstruct it to a different node type, or delete it by returning @nullptr@.
224\item
225If the previsit or postvisit method is not defined for a node type, the step is skipped.
226If the return type is declared as @void@, the original node is returned by default.
227These behaviours are controlled by template specialization rules;
228see @Common/PassVisitor.proto.h@ (old) and @AST/@ @Pass.proto.hpp@ (new) for details.
229\end{itemize}
230Other useful mixin classes for compilation passes include:
231\begin{itemize}
232\item
233@WithGuards@ allows saving and restoring variable values automatically upon entering/exiting the current node.
234\item
235@WithVisitorRef@ creates a wrapped entity for the current pass (the actual argument passed to recursive calls internally) for explicit recursion, usually used together with @WithShortCircuiting@.
236\item
237@WithSymbolTable@ gives a managed symbol table with built-in scoping-rule handling (\eg on entering and exiting a block statement)
238\end{itemize}
239\NOTE: If a pass extends the functionality of another existing pass, due to \CC overloading resolution rules, it \textbf{must} explicitly introduce the inherited previsit and postvisit procedures to its own scope, or otherwise they are not picked up by template resolution:
240\begin{C++}
241class Pass2: public Pass1 {
242        @using Pass1::previsit;@
243        @using Pass1::postvisit;@
244        // new procedures
245}
246\end{C++}
247
248
249\subsection{Data Structure Change (new-ast)}
250
251It has been observed that excessive copying of syntax tree structures accounts for a majority of computation cost and significantly slows down the compiler.
252In the previous implementation of the syntax tree, every internal node has a unique parent;
253therefore all copies are required to duplicate the entire subtree.
254A new, experimental re-implementation of the syntax tree (source under directory @AST/@ hereby referred to as new-ast'') attempts to overcome this issue with a functional approach that allows sharing of common sub-structures and only makes copies when necessary.
255
256The core of new-ast is a customized implementation of smart pointers, similar to @std::shared_ptr@ and @std::weak_ptr@ in the \CC standard library.
257Reference counting is used to detect sharing and allowing certain optimizations.
258For a purely functional (immutable) data-structure, all mutations are modelled by shallow copies along the path of mutation.
259With reference counting optimization, unique nodes are allowed to be mutated in place.
260This however, may potentially introduce some complications and bugs;
261a few issues are discussed near the end of this section.
262
263
264\subsubsection{Source: \lstinline{AST/Node.hpp}}
265
266Class @ast::Node@ is the base class of all new-ast node classes, which implements reference counting mechanism.
267Two different counters are recorded: strong'' reference count for number of nodes semantically owning it;
268`weak'' reference count for number of nodes holding a mere reference and only need to observe changes.
269Class @ast::ptr_base@ is the smart pointer implementation and also takes care of resource management.
270
271Direct access through the smart pointer is read-only.
272A mutable access should be obtained by calling @shallowCopy@ or mutate as below.
273
274Currently, the weak pointers are only used to reference declaration nodes from a named type, or a variable expression.
275Since declaration nodes are intended to denote unique entities in the program, weak pointers always point to unique (unshared) nodes.
276This property may change in the future, and weak references to shared nodes may introduce some problems;
277see mutate function below.
278
279All node classes should always use smart pointers in structure definitions versus raw pointers.
280Function
281\begin{C++}
282void ast::Node::increment(ref_type ref)
283\end{C++}
284increments this node's strong or weak reference count.
285Function
286\begin{C++}
287void ast::Node::decrement(ref_type ref, bool do_delete = true)
288\end{C++}
289decrements this node's strong or weak reference count.
290If strong reference count reaches zero, the node is deleted.
291\NOTE: Setting @do_delete@ to false may result in a detached node.
292Subsequent code should manually delete the node or assign it to a strong pointer to prevent memory leak.
293
294Reference counting functions are internally called by @ast::ptr_base@.
295Function
296\begin{C++}
297template<typename node_t>
298node_t * shallowCopy(const node_t * node)
299\end{C++}
300returns a mutable, shallow copy of node: all child pointers are pointing to the same child nodes.
301Function
302\begin{C++}
303template<typename node_t>
304node_t * mutate(const node_t * node)
305\end{C++}
306returns a mutable pointer to the same node, if the node is unique (strong reference count is 1);
307otherwise, it returns @shallowCopy(node)@.
308It is an error to mutate a shared node that is weak-referenced.
309Currently this does not happen.
310A problem may appear once weak pointers to shared nodes (\eg expression nodes) are used;
311special care is needed.
312
313\NOTE: This naive uniqueness check may not be sufficient in some cases.
314A discussion of the issue is presented at the end of this section.
315Functions
316\begin{C++}
317template<typename node_t, typename parent_t, typename field_t, typename assn_t>
318const node_t * mutate_field(const node_t * node, field_t parent_t::* field, assn_t && val)
319\end{C++}
320\begin{C++}
321template<typename node_t, typename parent_t, typename coll_t, typename ind_t,
322                typename field_t>
323const node_t * mutate_field_index(const node_t * node, coll_t parent_t::* field, ind_t i,
324                field_t && val)
325\end{C++}
326are helpers for mutating a field on a node using pointer to a member function (creates shallow copy when necessary).
327
328
329\subsubsection{Issue: Undetected Sharing}
330
331The @mutate@ behaviour described above has a problem: deeper shared nodes may be
332mistakenly considered as unique. \VRef[Figure]{f:DeepNodeSharing} shows how the problem could arise:
333\begin{figure}
334\centering
335\input{DeepNodeSharing}
336\caption{Deep sharing of nodes}
337\label{f:DeepNodeSharing}
338\end{figure}
339Given the tree rooted at P1, which is logically the chain P1-A-B, and P2 is irrelevant, assume @mutate(B)@ is called.
340The algorithm considers B as unique since it is only directly owned by A.
341However, the other tree P2-A-B indirectly shares the node B and is therefore wrongly mutated.
342
343To partly address this problem, if the mutation is called higher up the tree, a chain mutation helper can be used.
344
345\subsubsection{Source: \lstinline{AST/Chain.hpp}}
346
347Function
348\begin{C++}
349template<typename node_t, Node::ref_type ref_t>
350auto chain_mutate(ptr_base<node_t, ref_t> & base)
351\end{C++}
352returns a chain mutator handle that takes pointer-to-member to go down the tree, while creating shallow copies as necessary;
353see @struct _chain_mutator@ in the source code for details.
354
355For example, in the above diagram, if mutation of B is wanted while at P1, the call using @chain_mutate@ looks like the following:
356\begin{C++}
357chain_mutate(P1.a)(&A.b) = new_value_of_b;
358\end{C++}
359\NOTE: if some node in chain mutate is shared (therefore shallow copied), it implies that every node further down is also copied, thus correctly executing the functional mutation algorithm.
360This example code creates copies of both A and B and performs mutation on the new nodes, so that the other tree P2-A-B is untouched.
361However, if a pass traverses down to node B and performs mutation, for example, in @postvisit(B)@, information on sharing higher up is lost.
362Since the new-ast structure is only in experimental use with the resolver algorithm, which mostly rebuilds the tree bottom-up, this issue does not actually happen.
363It should be addressed in the future when other compilation passes are migrated to new-ast and many of them contain procedural mutations, where it might cause accidental mutations to other logically independent trees (\eg common sub-expression) and become a bug.
364
365
366\section{Compiler Algorithm Documentation}
367
368This compiler algorithm documentation covers most of the resolver, data structures used in variable and expression resolution, and a few directly related passes.
369Later passes involving code generation are not included yet;
370documentation for those will be done latter.
371
372
373\subsection{Symbol Table}
374
375\NOTE: For historical reasons, the symbol-table data-structure is called @indexer@ in the old implementation.
376Hereby, the name is changed to @SymbolTable@.
377The symbol table stores a mapping from names to declarations, implements a similar name-space separation rule, and provides the same scoping rules as standard C.\footnote{ISO/IEC 9899:1999, Sections 6.2.1 and 6.2.3.}
378The difference in name-space rule is that @typedef@ aliases are no longer considered ordinary identifiers.
379In addition to C tag-types (@struct@, @union@, @enum@), \CFA introduces another tag type, @trait@, which is a named collection of assertions.
380
381
382\subsubsection{Source: \lstinline{AST/SymbolTable.hpp}}
383
384Function
385\begin{C++}
386SymbolTable::addId(const DeclWithType * decl)
387\end{C++}
388provides name mangling of identifiers, since \CFA allows overloading of variables and functions.
389The mangling scheme is closely based on the Itanium \CC ABI,\footnote{\url{https://itanium-cxx-abi.github.io/cxx-abi/abi.html}, Section 5.1} while making adaptations to \CFA specific features, mainly assertions and overloaded variables by type.
390
391Naming conflicts are handled by mangled names;
392lookup by name returns a list of declarations with the same identifier name.
393Functions
394\begin{C++}
395SymbolTable::addStruct(const StructDecl * decl)
396SymbolTable::addUnion(const UnionDecl * decl)
397SymbolTable::addEnum(const EnumDecl * decl)
398SymbolTable::addTrait(const TraitDecl * decl)
399\end{C++}
400add a tag-type declaration to the symbol table.
401Function
402\begin{C++}
403SymbolTable::addType(const NamedTypeDecl * decl)
404\end{C++}
405adds a @typedef@ alias to the symbol table.
406
407\textbf{C Incompatibility Note}: Since \CFA allows using @struct@, @union@ and @enum@ type-names without a prefix keyword, as in \CC, @typedef@ names and tag-type names cannot be disambiguated by syntax rules.
408Currently the compiler puts them together and disallows collision.
409The following program is valid C but invalid \CFA (and \CC):
410\begin{C++}
411struct A {};
412typedef int A; // gcc: ok, cfa: Cannot redefine typedef A
413struct A sa; // C disambiguates via struct prefix
414A ia;
415\end{C++}
416In practices, such usage is extremely rare, and hence, this change (as in \CC) has minimal impact on existing C programs.
417The declaration
418\begin{C++}
419struct A {};
420typedef struct A A; // A is an alias for struct A
421A a;
422struct A b;
423\end{C++}
424is not an error because the alias name is identical to the original.
425Finally, the following program is allowed in \CFA:
426\begin{C++}
427typedef int A;
428void A(); // name mangled
429// gcc: A redeclared as different kind of symbol, cfa: ok
430\end{C++}
431because the function name is mangled.
432
433
434\subsection{Type Environment and Unification}
435
436The following core ideas underlie the parametric type-resolution algorithm.
437A type environment organizes type parameters into \textbf{equivalent classes} and maps them to actual types.
438Unification is the algorithm that takes two (possibly parametric) types and parameter mappings, and attempts to produce a common type by matching information in the type environments.
439
440The unification algorithm is recursive in nature and runs in two different modes internally:
441\begin{itemize}
442\item
443Exact unification mode requires equivalent parameters to match perfectly.
444\item
445Inexact unification mode allows equivalent parameters to be converted to a common type.
446\end{itemize}
447For a pair of matching parameters (actually, their equivalent classes), if either side is open (not bound to a concrete type yet), they are combined.
448
449Within the inexact mode, types are allowed to differ on their cv-qualifiers (\eg @const@, @volatile@, \etc);
450additionally, if a type never appear either in a parameter list or as the base type of a pointer, it may also be widened (\ie safely converted).
451As \CFA currently does not implement subclassing as in object-oriented languages, widening conversions are only on the primitive types, \eg conversion from @int@ to @long int@.
452
453The need for two unification modes comes from the fact that parametric types are considered compatible only if all parameters are exactly the same (not just compatible).
454Pointer types also behaves similarly;
455in fact, they may be viewed as a primitive kind of parametric types.
456@int *@ and @long *@ are different types, just like @vector(int)@ and @vector(long)@ are, for the parametric type @*(T)@ / @vector(T)@, respectively.
457
458The resolver uses the following @public@ functions:\footnote{
459Actual code also tracks assertions on type parameters; those extra arguments are omitted here for conciseness.}
460
461
462\subsubsection{Source: \lstinline{ResolvExpr/Unify.cc}}
463
464Function
465\begin{C++}
466bool unify(const Type * type1, const Type * type2, TypeEnvironment & env,
467        OpenVarSet & openVars, const SymbolTable & symtab, Type *& commonType)
468\end{C++}
469returns a boolean indicating if the unification succeeds or fails after attempting to unify @type1@ and @type2@ within current type environment.
470If the unify succeeds, @env@ is modified by combining the equivalence classes of matching parameters in @type1@ and @type2@, and their common type is written to @commonType@.
471If the unify fails, nothing changes.
472Functions
473\begin{C++}
474bool typesCompatible(const Type * type1, const Type * type2, const SymbolTable & symtab,
475        const TypeEnvironment & env)
476bool typesCompatibleIgnoreQualifiers(const Type * type1, const Type * type2,
477        const SymbolTable & symtab, const TypeEnvironment & env)
478\end{C++}
479return a boolean indicating if types @type1@ and @type2@ can possibly be the same type.
480The second version ignores the outermost cv-qualifiers if present.\footnote{
481In \lstinline@const int * const@, only the second \lstinline@const@ is ignored.}
482These function have no side effects.
483
484\NOTE: No attempt is made to widen the types (exact unification is used), although the function names may suggest otherwise, \eg @typesCompatible(int, long)@ returns false.
485
486
487\subsection{Expression Resolution}
488
489The design of the current version of expression resolver is outlined in the Ph.D.\ thesis by Aaron Moss~\cite{Moss19}.
490A summary of the resolver algorithm for each expression type is presented below.
491
492All overloadable operators are modelled as function calls.
493For a function call, interpretations of the function and arguments are found recursively.
494Then the following steps produce a filtered list of valid interpretations:
495\begin{enumerate}
496\item
497From all possible combinations of interpretations of the function and arguments, those where argument types may be converted to function parameter types are considered valid.
498\item
499Valid interpretations with the minimum sum of argument costs are kept.
500\item
501\label{p:argcost}
502Argument costs are then discarded; the actual cost for the function call expression is the sum of conversion costs from the argument types to parameter types.
503\item
504\label{p:returntype}
505For each return type, the interpretations with satisfiable assertions are then sorted by actual cost computed in step~\ref{p:argcost}.
506If for a given type, the minimum cost interpretations are not unique, that return type is ambiguous.
507If the minimum cost interpretation is unique but contains an ambiguous argument, it is also ambiguous.
508\end{enumerate}
509Therefore, for each return type, the resolver produces:
510\begin{itemize}
511\item
512no alternatives
513\item
514a single valid alternative
515\item
516an ambiguous alternative
517\end{itemize}
518\NOTE: an ambiguous alternative may be discarded at the parent expressions because a different return type matches better for the parent expressions.
519
520The \emph{non}-overloadable expressions in \CFA are: cast expressions, address-of (unary @&@) expressions, short-circuiting logical expressions (@&&@, @||@) and ternary conditional expression (@?:@).
521
522For a cast expression, the convertible argument types are kept.
523Then the result is selected by lowest argument cost, and further by lowest conversion cost to target type.
524If the lowest cost is still not unique or an ambiguous argument interpretation is selected, the cast expression is ambiguous.
525In an expression statement, the top level expression is implicitly cast to @void@.
526
527For an address-of expression, only lvalue results are kept and the minimum cost is selected.
528
529For logical expressions @&&@ and @||@, arguments are implicitly cast to @bool@, and follow the rules fr cast expression above.
530
531For the ternary conditional expression, the condition is implicitly cast to @bool@, and the branch expressions must have compatible types.
532Each pair of compatible branch expression types produce a possible interpretation, and the cost is defined as the sum of the expression costs plus the sum of conversion costs to the common type.
533
534
535\subsection{Conversion and Application Cost}
536
537There were some unclear parts in the previous documentation in the cost system, as described in the Moss thesis~\cite{Moss19}, section 4.1.2.
538Some clarification are presented in this section.
539
540\begin{enumerate}
541\item
542Conversion to a type denoted by parameter may incur additional cost if the match is not exact.
543For example, if a function is declared to accept @(T, T)@ and receives @(int, long)@, @T@ is deducted @long@ and an additional widening conversion cost is added for @int@ to @T@.
544
545\item
546The specialization level of a function is the sum of the least depth of an appearance of a type parameter (counting pointers, references and parameterized types), plus the number of assertions.
547A higher specialization level is favoured if argument conversion costs are equal.
548
549\item
550Coercion of pointer types is only allowed in explicit cast expressions;
551the only allowed implicit pointer casts are adding qualifiers to the base type and cast to @void*@, and these counts as safe conversions.
552Note that implicit cast from @void *@ to other pointer types is no longer valid, as opposed to standard C.
553\end{enumerate}
554
555
556\subsection{Assertion Satisfaction}
557
558The resolver tries to satisfy assertions on expressions only when it is needed: either while selecting from multiple alternatives of a same result type for a function call (step \ref{p:returntype} of resolving function calls) or upon reaching the top level of an expression statement.
559
560Unsatisfiable alternatives are discarded.
561Satisfiable alternatives receive \textbf{implicit parameters}: in \CFA, parametric functions may be separately compiled, as opposed to \CC templates which are only compiled at instantiation.
562Given the parametric function-definition:
563\begin{C++}
564forall (otype T | {void foo(T);})
565void bar (T t) { foo(t); }
566\end{C++}
567the function @bar@ does not know which @foo@ to call when compiled without knowing the call site, so it requests a function pointer to be passed as an extra argument.
568At the call site, implicit parameters are automatically inserted by the compiler.
569
570Implementation of implicit parameters is discussed in \VRef[Appendix]{s:ImplementationParametricFunctions}.
571
572\section{Tests}
573
574\subsection{Test Suites}
575
576Automatic test suites are located under the @tests/@ directory.
577A test case consists of an input CFA source file (suffix @.cfa@), and an expected output file located in the @tests/.expect/@ directory, with the same file name ending with suffix @.txt@.
578For example, the test named @tests/tuple/tupleCast.cfa@ has the following files, for example:
579\begin{C++}
580tests/
581        tuple/
582                .expect/
583                        tupleCast.txt
584                tupleCast.cfa
585\end{C++}
586If compilation fails, the error output is compared to the expect file.
587If the compilation succeeds but does not generate an executable, the compilation output is compared to the expect file.
588If the compilation succeeds and generates an executable, the executable is run and its output is compared to the expect file.
589To run the tests, execute the test script @test.py@ under the @tests/@ directory, with a list of test names to be run, or @--all@ (or @make all-tests@) to run all tests.
590The test script reports test cases fail/success, compilation time and program run time.
591To see all the options available for @test.py@ using the @--help@ option.
592
593
594\subsection{Performance Reports}
595
596To turn on performance reports, pass the @-XCFA -S@ flag to the compiler.
597Three kinds of performance reports are available:
598\begin{enumerate}
599\item
600Time, reports time spent in each compilation step
601\item
602Heap, reports number of dynamic memory allocations, total bytes allocated, and
603maximum heap memory usage
604\item
605Counters, for certain predefined statistics; counters can be registered anywhere in
606the compiler as a static object, and the interface can be found at
607@Common/Stats/Counter.h@.
608\end{enumerate}
609It is suggested to run performance tests with optimization (@g++@ flag @-O3@).
610
611
612\appendix
613\section{Appendix}
614
615\subsection{Kinds of Type Parameters}
616\label{s:KindsTypeParameters}
617
618A type parameter in a @forall@ clause has 3 kinds:
619\begin{enumerate}[listparindent=0pt]
620\item
621@dtype@: any data type (built-in or user defined) that is not a concrete type.
622
623A non-concrete type is an incomplete type such as an opaque type or pointer/reference with an implicit (pointer) size and implicitly generated reference and dereference operations.
624\item
625@otype@: any data type (built-in or user defined) that is concrete type.
626
627A concrete type is a complete type, \ie types that can be used to create a variable, which also implicitly asserts the existence of default and copy constructors, assignment, and destructor\footnote{\CFA implements the same automatic resource management (RAII) semantics as \CC.}.
628% \item
629% @ftype@: any function type.
630%
631% @ftype@ provides two purposes:
632% \begin{itemize}
633% \item
634% Differentiate function pointer from data pointer because (in theory) some systems have different sizes for these pointers.
635% \item
636% Disallow a function pointer to match an overloaded data pointer, since variables and functions can have the same names.
637% \end{itemize}
638
639\item
640@ttype@: tuple (variadic) type.
641
642Restricted to the type for the last parameter in a function, it provides a type-safe way to implement variadic functions.
643Note however, that it has certain restrictions, as described in the implementation section below.
644\end{enumerate}
645
646
647\subsection{GNU C Nested Functions}
648
649\CFA is designed to be mostly compatible with GNU C, an extension to ISO C99 and C11 standards. The \CFA compiler also implements some language features by GCC extensions, most notably nested functions.
650
651In ISO C, function definitions are not allowed to be nested. GCC allows nested functions with full lexical scoping. The following example is taken from GCC documentation\footnote{\url{https://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html}}:
652\begin{C++}
653void bar( int * array, int offset, int size ) {
654        int access( int * array, int index ) { return array[index + offset]; }
655        int i;
656        /* ... */
657        for ( i = 0; i < size; i++ )
658                /* ... */ access (array, i) /* ... */
659}
660\end{C++}
661GCC nested functions behave identically to \CC lambda functions with default by-reference capture (stack-allocated, lifetime ends upon exiting the declared block), while also possible to be passed as arguments with standard function pointer types.
662
663
664\subsection{Implementation of Parametric Functions}
665\label{s:ImplementationParametricFunctions}
666
667\CFA implements parametric functions using the implicit parameter approach: required assertions are passed to the callee by function pointers;
668size of a parametric type must also be known if referenced directly (\ie not as a pointer).
669
670The implementation is similar to the one from Scala\footnote{\url{https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html}}, with some notable differences in resolution:
671\begin{enumerate}
672\item
673All types, variables, and functions are candidates of implicit parameters
674\item
675The parameter (assertion) name must match the actual declarations.
676\end{enumerate}
677
678For example, the \CFA function declaration
679\begin{cfa}
680forall( otype T | { int foo( T, int ); } )
681int bar(T);
682\end{cfa}
683after implicit parameter expansion, has the actual signature\footnote{\textbf{otype} also requires the type to have constructor and destructor, which are the first two function pointers preceding the one for \textbf{foo}.}
684\begin{C++}
685int bar( T, size_t, void (*)(T&), void (*)(T&), int (*)(T, int) );
686\end{C++}
687The implicit parameter approach has an apparent issue: when the satisfying declaration is also parametric, it may require its own implicit parameters too.
688That also causes the supplied implicit parameter to have a different \textbf{actual} type than the \textbf{nominal} type, so it cannot be passed directly.
689Therefore, a wrapper with matching actual type must be created, and it is here where GCC nested functions are used internally by the compiler.
690
691Consider the following program:
692\begin{cfa}
693int assertion(int);
694
695forall( otype T | { int assertion(T); } )
696void foo(T);
697
698forall(otype T | { void foo(T); } )
699void bar(T t) {
700        foo(t);
701}
702\end{cfa}
703The \CFA compiler translates the program to non-parametric form\footnote{In the final code output, \lstinline@T@ needs to be replaced by an opaque type, and arguments must be accessed by a frame pointer offset table, due to the unknown sizes. The presented code here is simplified for better understanding.}
704\begin{C++}
705// ctor, dtor and size arguments are omitted
706void foo(T, int (*)(T));
707
708void bar(T t, void (*foo)(T)) {
709        foo(t);
710}
711\end{C++}
712However, when @bar(1)@ is called, @foo@ cannot be directly provided as an argument:
713\begin{C++}
714bar(1, foo); // WRONG: foo has different actual type
715\end{C++}
716and an additional step is required:
717\begin{C++}
718{
719        void _foo_wrapper(int t) {
720                foo( t, assertion );
721        }
722        bar( 1, _foo_wrapper );
723}
724\end{C++}
725Nested assertions and implicit parameter creation may continue indefinitely.
726This issue is a limitation of implicit parameter implementation.
727In particular, polymorphic variadic recursion must be structural (\ie the number of arguments decreases in any possible recursive calls), otherwise code generation gets into an infinite loop.
728The \CFA compiler sets a limit on assertion depth and reports an error if assertion resolution does not terminate within the limit (as for \lstinline[language=C++]@templates@ in \CC).
729