source: doc/theses/fangren_yu_COOP_S20/Report.tex @ 1526e86

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 1526e86 was 1526e86, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

small updates and some more questions

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