Changeset f99f5ba


Ignore:
Timestamp:
Feb 1, 2021, 2:42:22 PM (9 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
8be729f, c235179
Parents:
cd70477 (diff), 5669d0b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
4 added
26 edited

Legend:

Unmodified
Added
Removed
  • .gitignore

    rcd70477 rf99f5ba  
    7979# generated by npm
    8080package-lock.json
     81
     82# generated by benchmark
     83benchmark/Cargo.toml
  • doc/LaTeXmacros/common.tex

    rcd70477 rf99f5ba  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Mon Oct  5 09:34:46 2020
    14 %% Update Count     : 464
     13%% Last Modified On : Thu Jan 28 19:01:57 2021
     14%% Update Count     : 494
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
     
    3232\setlist[enumerate]{listparindent=\parindent}% global
    3333\setlist[enumerate,2]{leftmargin=\parindent,labelsep=*,align=parleft,label=\alph*.}% local
    34 \setlist[description]{itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex}
     34\setlist[description]{topsep=0.5ex,itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex}
    3535
    3636% Names used in the document.
     
    8989\newcommand{\italic}[1]{\emph{\hyperpage{#1}}}
    9090\newcommand{\Definition}[1]{\textbf{\hyperpage{#1}}}
    91 \newcommand{\see}[1]{\emph{see}~#1}
     91\newcommand{\see}[1]{(see #1)}
    9292
    9393% Define some commands that produce formatted index entries suitable for cross-references.
     
    229229\usepackage{listings}                                                                   % format program code
    230230\usepackage{lstlang}
     231\usepackage{calc}                                                                               % latex arithmetic
     232
    231233\makeatletter
    232 
    233234\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{#1}}}
    234235\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
     
    265266showlines=true,                                                 % show blank lines at end of code
    266267aboveskip=4pt,                                                  % spacing above/below code block
    267 belowskip=3pt,
     268belowskip=-2pt,
     269numberstyle=\footnotesize\sf,                   % numbering style
    268270% replace/adjust listing characters that look bad in sanserif
    269271literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.75ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
     
    293295language=CFA,
    294296escapechar=\$,                                                  % LaTeX escape in CFA code
     297mathescape=false,                                               % LaTeX math escape in CFA code $...$
    295298moredelim=**[is][\color{red}]{@}{@},    % red highlighting @...@
    296299}% lstset
  • doc/bibliography/pl.bib

    rcd70477 rf99f5ba  
    17971797}
    17981798
    1799 @article{Delisle19,
     1799@article{Delisle20,
    18001800    keywords    = {concurrency, Cforall},
    18011801    contributer = {pabuhr@plg},
    18021802    author      = {Thierry Delisle and Peter A. Buhr},
    18031803    title       = {Advanced Control-flow and Concurrency in \textsf{C}$\mathbf{\forall}$},
    1804     year        = 2019,
     1804    year        = 2020,
    18051805    journal     = spe,
    1806     pages       = {1-33},
    1807     note        = {submitted},
     1806    pages       = {1-38},
     1807    note        = {\href{https://doi-org.proxy.lib.uwaterloo.ca/10.1002/spe.2925}{https://\-doi-org.proxy.lib.uwaterloo.ca/\-10.1002/\-spe.2925}},
     1808    note        = {},
    18081809}
    18091810
  • doc/theses/andrew_beach_MMath/.gitignore

    rcd70477 rf99f5ba  
    33
    44# Final Files:
    5 thesis.pdf
     5*.pdf
    66
    77# The Makefile here is not generated.
  • doc/theses/andrew_beach_MMath/existing.tex

    rcd70477 rf99f5ba  
    1 \chapter{\CFA Existing Features}
    2 
    3 \CFA (C-for-all)~\cite{Cforall} is an open-source project extending ISO C with modern safety and productivity features, while still ensuring backwards compatibility with C and its programmers.
    4 \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm (non-object-oriented) and these features can be added incrementally to an existing C code-base allowing programmers to learn \CFA on an as-needed basis.
    5 
    6 \section{Overloading and extern}
    7 Cforall has overloading, allowing multiple definitions of the same name to
    8 be defined.~\cite{Moss18}
    9 
    10 This also adds name mangling so that the assembly symbols are unique for
    11 different overloads. For compatability with names in C there is also a
    12 syntax to diable the name mangling. These unmangled names cannot be overloaded
    13 but act as the interface between C and \CFA code.
    14 
    15 The syntax for disabling mangling is:
    16 \begin{cfa}
    17 extern "C" {
    18     ...
    19 }
    20 \end{cfa}
    21 
    22 To re-enable mangling once it is disabled the syntax is:
    23 \begin{cfa}
    24 extern "Cforall" {
    25     ...
    26 }
    27 \end{cfa}
    28 
    29 Both should occur at the declaration level and effect all the declarations
    30 in @...@. Neither care about the state of mangling when they begin
    31 and will return to that state after the group is finished. So re-enabling
    32 is only used to nest areas of mangled and unmangled declarations.
    33 
    34 \section{References}
    35 \CFA adds references to C. These are auto-dereferencing pointers and use the
    36 same syntax as pointers except they use ampersand (@&@) instead of
    37 the asterisk (@*@). They can also be constaint or mutable, if they
    38 are mutable they may be assigned to by using the address-of operator
    39 (@&@) which converts them into a pointer.
     1\chapter{\texorpdfstring{\CFA Existing Features}{Cforall Existing Features}}
     2
     3\CFA (C-for-all)~\cite{Cforall} is an open-source project extending ISO C with
     4modern safety and productivity features, while still ensuring backwards
     5compatibility with C and its programmers.  \CFA is designed to have an
     6orthogonal feature-set based closely on the C programming paradigm
     7(non-object-oriented) and these features can be added incrementally to an
     8existing C code-base allowing programmers to learn \CFA on an as-needed basis.
     9
     10Only those \CFA features pertinent to this thesis are discussed.  Many of the
     11\CFA syntactic and semantic features used in the thesis should be fairly
     12obvious to the reader.
     13
     14\section{\texorpdfstring{Overloading and \lstinline|extern|}{Overloading and extern}}
     15\CFA has extensive overloading, allowing multiple definitions of the same name
     16to be defined.~\cite{Moss18}
     17\begin{cfa}
     18char i; int i; double i;                        $\C[3.75in]{// variable overload}$
     19int f(); double f();                            $\C{// return overload}$
     20void g( int ); void g( double );        $\C{// parameter overload}\CRT$
     21\end{cfa}
     22This feature requires name mangling so the assembly symbols are unique for
     23different overloads. For compatibility with names in C, there is also a syntax
     24to disable name mangling. These unmangled names cannot be overloaded but act as
     25the interface between C and \CFA code.  The syntax for disabling/enabling
     26mangling is:
     27\begin{cfa}
     28// name mangling
     29int i; // _X1ii_1
     30@extern "C"@ {  // no name mangling
     31        int j; // j
     32        @extern "Cforall"@ {  // name mangling
     33                int k; // _X1ki_1
     34        }
     35        // no name mangling
     36}
     37// name mangling
     38\end{cfa}
     39Both forms of @extern@ affect all the declarations within their nested lexical
     40scope and transition back to the previous mangling state when the lexical scope
     41ends.
     42
     43\section{Reference Type}
     44\CFA adds a rebindable reference type to C, but more expressive than the \CC
     45reference.  Multi-level references are allowed and act like auto-dereferenced
     46pointers using the ampersand (@&@) instead of the pointer asterisk (@*@). \CFA
     47references may also be mutable or non-mutable. If mutable, a reference variable
     48may be assigned to using the address-of operator (@&@), which converts the
     49reference to a pointer.
     50\begin{cfa}
     51int i, j;
     52int @&@ ri = i, @&&@ rri = ri;
     53rri = 3;  // auto-dereference assign to i
     54@&@ri = @&@j; // rebindable
     55ri = 5;   // assign to j
     56\end{cfa}
    4057
    4158\section{Constructors and Destructors}
    4259
    4360Both constructors and destructors are operators, which means they are just
    44 functions with special names. The special names are used to define them and
    45 may be used to call the functions expicately. The \CFA special names are
    46 constructed by taking the tokens in the operators and putting @?@ where
    47 the arguments would go. So multiplication is @?*?@ while dereference
    48 is @*?@. This also make it easy to tell the difference between
    49 pre-fix operations (such as @++?@) and post-fix operations
    50 (@?++@).
    51 
    52 The special name for contructors is @?{}@, which comes from the
    53 initialization syntax in C. The special name for destructors is
    54 @^{}@. % I don't like the \^{} symbol but $^\wedge$ isn't better.
    55 
    56 Any time a type T goes out of scope the destructor matching
    57 @void ^?{}(T &);@ is called. In theory this is also true of
    58 primitive types such as @int@, but in practice those are no-ops and
    59 are usually omitted for optimization.
     61functions with special operator names rather than type names in \CC. The
     62special operator names may be used to call the functions explicitly (not
     63allowed in \CC for constructors).
     64
     65In general, operator names in \CFA are constructed by bracketing an operator
     66token with @?@, which indicates where the arguments. For example, infixed
     67multiplication is @?*?@ while prefix dereference is @*?@. This syntax make it
     68easy to tell the difference between prefix operations (such as @++?@) and
     69post-fix operations (@?++@).
     70
     71The special name for a constructor is @?{}@, which comes from the
     72initialization syntax in C. The special name for a destructor is @^{}@, where
     73the @^@ has no special meaning.
     74% I don't like the \^{} symbol but $^\wedge$ isn't better.
     75\begin{cfa}
     76struct T { ... };
     77void ?@{}@(@T &@ this, ...) { ... }  // constructor
     78void ?@^{}@(@T &@ this, ...) { ... } // destructor
     79{
     80        T s = @{@ ... @}@;  // same constructor/initialization braces
     81} // destructor call automatically generated
     82\end{cfa}
     83The first parameter is a reference parameter to the type for the
     84constructor/destructor. Destructors may have multiple parameters.  The compiler
     85implicitly matches an overloaded constructor @void ^?{}(T &, ...);@ to an
     86object declaration with associated initialization, and generates a construction
     87call after the object is allocated. When an object goes out of scope, the
     88matching overloaded destructor @void ^?{}(T &);@ is called.  Without explicit
     89definition, \CFA creates a default and copy constructor, destructor and
     90assignment (like \CC). It is possible to define constructors/destructors for
     91basic and existing types.
    6092
    6193\section{Polymorphism}
    62 \CFA uses polymorphism to create functions and types that are defined over
    63 different types. \CFA polymorphic declarations serve the same role as \CC
    64 templates or Java generics.
    65 
    66 Polymorphic declaractions start with a forall clause that goes before the
    67 standard (monomorphic) declaration. These declarations have the same syntax
    68 except that you may use the names introduced by the forall clause in them.
    69 
    70 Forall clauses are written @forall( ... )@ where @...@ becomes
    71 the list of polymorphic variables (local type names) and assertions, which
    72 repersent required operations on those types.
    73 
    74 \begin{cfa}
    75 forall(dtype T | { void do_once(T &); })
    76 void do_twice(T & value) {
    77     do_once(value);
    78     do_once(value);
    79 }
    80 \end{cfa}
    81 
    82 A polymorphic function can be used in the same way normal functions are.
    83 The polymorphics variables are filled in with concrete types and the
    84 assertions are checked. An assertion checked by seeing if that name of that
    85 type (with all the variables replaced with the concrete types) is defined at
    86 the the call site.
    87 
    88 As an example, even if no function named @do_once@ is not defined
    89 near the definition of @do_twice@ the following code will work.
    90 \begin{cfa}
     94\CFA uses parametric polymorphism to create functions and types that are
     95defined over multiple types. \CFA polymorphic declarations serve the same role
     96as \CC templates or Java generics. The ``parametric'' means the polymorphism is
     97accomplished by passing argument operations to associate \emph{parameters} at
     98the call site, and these parameters are used in the function to differentiate
     99among the types the function operates on.
     100
     101Polymorphic declarations start with a universal @forall@ clause that goes
     102before the standard (monomorphic) declaration. These declarations have the same
     103syntax except they may use the universal type names introduced by the @forall@
     104clause.  For example, the following is a polymorphic identity function that
     105works on any type @T@:
     106\begin{cfa}
     107@forall( T )@ @T@ identity( @T@ val ) { return val; }
     108int forty_two = identity( 42 ); // T bound to int, forty_two == 42
     109\end{cfa}
     110
     111To allow a polymorphic function to be separately compiled, the type @T@ must be
     112constrained by the operations used on @T@ in the function body. The @forall@
     113clauses is augmented with a list of polymorphic variables (local type names)
     114and assertions (constraints), which represent the required operations on those
     115types used in a function, \eg:
     116\begin{cfa}
     117forall( T @| { void do_once(T); }@) // assertion
     118void do_twice(T value) {
     119        do_once(value);
     120        do_once(value);
     121}
     122void do_once(int i) { ... }  // provide assertion
     123int i;
     124do_twice(i); // implicitly pass assertion do_once to do_twice
     125\end{cfa}
     126Any object with a type fulfilling the assertion may be passed as an argument to
     127a @do_twice@ call.
     128
     129A polymorphic function can be used in the same way as a normal function.  The
     130polymorphic variables are filled in with concrete types and the assertions are
     131checked. An assertion is checked by verifying each assertion operation (with
     132all the variables replaced with the concrete types from the arguments) is
     133defined at a call site.
     134
     135Note, a function named @do_once@ is not required in the scope of @do_twice@ to
     136compile it, unlike \CC template expansion. Furthermore, call-site inferencing
     137allows local replacement of the most specific parametric functions needs for a
     138call.
     139\begin{cfa}
     140void do_once(double y) { ... } // global
    91141int quadruple(int x) {
    92     void do_once(int & y) {
    93         y = y * 2;
    94     }
    95     do_twice(x);
    96     return x;
    97 }
    98 \end{cfa}
    99 This is not the recommended way to implement a quadruple function but it
    100 does work. The complier will deduce that @do_twice@'s T is an
    101 integer from the argument. It will then look for a definition matching the
    102 assertion which is the @do_once@ defined within the function. That
    103 function will be passed in as a function pointer to @do_twice@ and
    104 called within it.
    105 
    106 To avoid typing out long lists of assertions again and again there are also
    107 traits which collect assertions into convenent packages that can then be used
    108 in assertion lists instead of all of their components.
    109 \begin{cfa}
    110 trait done_once(dtype T) {
    111     void do_once(T &);
    112 }
    113 \end{cfa}
    114 
    115 After this the forall list in the previous example could instead be written
    116 with the trait instead of the assertion itself.
    117 \begin{cfa}
    118 forall(dtype T | done_once(T))
    119 \end{cfa}
    120 
    121 Traits can have arbitrary number of assertions in them and are usually used to
    122 create short hands for, and give descriptive names to, commond groupings of
    123 assertions.
    124 
    125 Polymorphic structures and unions may also be defined by putting a forall
    126 clause before the declaration. The type variables work the same way except
    127 are now used in field declaractions instead of parameters and local variables.
    128 
     142        void do_once(int y) { y = y * 2; } // local
     143        do_twice(x); // using local "do_once"
     144        return x;
     145}
     146\end{cfa}
     147Specifically, the complier deduces that @do_twice@'s T is an integer from the
     148argument @x@. It then looks for the most specific definition matching the
     149assertion, which is the nested integral @do_once@ defined within the
     150function. The matched assertion function is then passed as a function pointer
     151to @do_twice@ and called within it.
     152
     153To avoid typing long lists of assertions, constraints can be collect into
     154convenient packages called a @trait@, which can then be used in an assertion
     155instead of the individual constraints.
     156\begin{cfa}
     157trait done_once(T) {
     158        void do_once(T);
     159}
     160\end{cfa}
     161and the @forall@ list in the previous example is replaced with the trait.
     162\begin{cfa}
     163forall(dtype T | @done_once(T)@)
     164\end{cfa}
     165In general, a trait can contain an arbitrary number of assertions, both
     166functions and variables, and are usually used to create a shorthand for, and
     167give descriptive names to, common groupings of assertions describing a certain
     168functionality, like @sumable@, @listable@, \etc.
     169
     170Polymorphic structures and unions are defined by qualifying the aggregate type
     171with @forall@. The type variables work the same except they are used in field
     172declarations instead of parameters, returns, and local variable declarations.
    129173\begin{cfa}
    130174forall(dtype T)
    131175struct node {
    132     node(T) * next;
    133     T * data;
    134 }
    135 \end{cfa}
    136 
    137 The @node(T)@ is a use of a polymorphic structure. Polymorphic types
    138 must be provided their polymorphic parameters.
    139 
    140 There are many other features of polymorphism that have not given here but
    141 these are the ones used by the exception system.
     176        node(T) * next;  // generic linked node
     177        T * data;
     178}
     179\end{cfa}
     180The generic type @node(T)@ is an example of a polymorphic-type usage.  Like \CC
     181templates usage, a polymorphic-type usage must specify a type parameter.
     182
     183There are many other polymorphism features in \CFA but these are the ones used
     184by the exception system.
    142185
    143186\section{Concurrency}
    144 
    145 \CFA has a number of concurrency features, @thread@s,
    146 @monitor@s and @mutex@ parameters, @coroutine@s and
    147 @generator@s. The two features that interact with the exception system
    148 are @thread@s and @coroutine@s; they and their supporting
    149 constructs will be described here.
    150 
    151 \subsection{Coroutines}
    152 Coroutines are routines that do not have to finish execution to hand control
    153 back to their caller, instead they may suspend their execution at any time
    154 and resume it later.
    155 Coroutines are not true concurrency but share some similarities and many of
    156 the same underpinnings and so are included as part of the \CFA threading
    157 library.
    158 
    159 In \CFA coroutines are created using the @coroutine@ keyword which
    160 works just like @struct@ except that the created structure will be
    161 modified by the compiler to satify the @is_coroutine@ trait.
    162 
    163 These structures act as the interface between callers and the coroutine,
    164 the fields are used to pass information in and out. Here is a simple example
    165 where the single field is used to pass the next number in a sequence out.
     187\CFA has a number of concurrency features: @thread@, @monitor@, @mutex@
     188parameters, @coroutine@ and @generator@. The two features that interact with
     189the exception system are @thread@ and @coroutine@; they and their supporting
     190constructs are described here.
     191
     192\subsection{Coroutine}
     193A coroutine is a type with associated functions, where the functions are not
     194required to finish execution when control is handed back to the caller. Instead
     195they may suspend execution at any time and be resumed later at the point of
     196last suspension. (Generators are stackless and coroutines are stackful.) These
     197types are not concurrent but share some similarities along with common
     198underpinnings, so they are combined with the \CFA threading library. Further
     199discussion in this section only refers to the coroutine because generators are
     200similar.
     201
     202In \CFA, a coroutine is created using the @coroutine@ keyword, which is an
     203aggregate type like @struct,@ except the structure is implicitly modified by
     204the compiler to satisfy the @is_coroutine@ trait; hence, a coroutine is
     205restricted by the type system to types that provide this special trait.  The
     206coroutine structure acts as the interface between callers and the coroutine,
     207and its fields are used to pass information in and out of coroutine interface
     208functions.
     209
     210Here is a simple example where a single field is used to pass (communicate) the
     211next number in a sequence.
    166212\begin{cfa}
    167213coroutine CountUp {
    168     unsigned int next;
    169 }
    170 \end{cfa}
    171 
    172 The routine part of the coroutine is a main function for the coroutine. It
    173 takes a reference to a coroutine object and returns nothing. In this function,
    174 and any functions called by this function, the suspend statement may be used
    175 to return execution to the coroutine's caller. When control returns to the
    176 function it continue from that same suspend statement instead of at the top
    177 of the function.
    178 \begin{cfa}
    179 void main(CountUp & this) {
    180     unsigned int next = 0;
    181     while (true) {
    182         this.next = next;
    183         suspend;
    184         next = next + 1;
    185     }
    186 }
    187 \end{cfa}
    188 
    189 Control is passed to the coroutine with the resume function. This includes the
    190 first time when the coroutine is starting up. The resume function takes a
    191 reference to the coroutine structure and returns the same reference. The
    192 return value is for easy access to communication variables. For example the
    193 next value from a count-up can be generated and collected in a single
    194 expression: @resume(count).next@.
     214        unsigned int next; // communication variable
     215}
     216CountUp countup;
     217\end{cfa}
     218Each coroutine has @main@ function, which takes a reference to a coroutine
     219object and returns @void@.
     220\begin{cfa}[numbers=left]
     221void main(@CountUp & this@) { // argument matches trait is_coroutine
     222        unsigned int up = 0;  // retained between calls
     223        while (true) {
     224                next = up; // make "up" available outside function
     225                @suspend;@$\label{suspend}$
     226                up += 1;
     227        }
     228}
     229\end{cfa}
     230In this function, or functions called by this function (helper functions), the
     231@suspend@ statement is used to return execution to the coroutine's caller
     232without terminating the coroutine.
     233
     234A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
     235The first resume calls the @main@ function at the top. Thereafter, resume calls
     236continue a coroutine in the last suspended function after the @suspend@
     237statement, in this case @main@ line~\ref{suspend}.  The @resume@ function takes
     238a reference to the coroutine structure and returns the same reference. The
     239return value allows easy access to communication variables defined in the
     240coroutine object. For example, the @next@ value for coroutine object @countup@
     241is both generated and collected in the single expression:
     242@resume(countup).next@.
    195243
    196244\subsection{Monitors and Mutex}
    197 
    198 True concurrency does not garrenty ordering. To get some of that ordering back
    199 \CFA uses monitors and mutex (mutual exclution) parameters. A monitor is
    200 another special declaration that contains a lock and is compatable with mutex
    201 parameters.
    202 
    203 Function parameters can have the @mutex@ qualifiers on reference
    204 arguments, for example @void example(a_monitor & mutex arg);@. When the
    205 function is called it will acquire the lock on all of the mutex parameters.
    206 
    207 This means that all functions that mutex on a type are part of a critical
    208 section and only one will ever run at a time.
     245Concurrency does not guarantee ordering; without ordering results are
     246non-deterministic. To claw back ordering, \CFA uses monitors and @mutex@
     247(mutual exclusion) parameters. A monitor is another kind of aggregate, where
     248the compiler implicitly inserts a lock and instances are compatible with
     249@mutex@ parameters.
     250
     251A function that requires deterministic (ordered) execution, acquires mutual
     252exclusion on a monitor object by qualifying an object reference parameter with
     253@mutex@.
     254\begin{cfa}
     255void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
     256\end{cfa}
     257When the function is called, it implicitly acquires the monitor lock for all of
     258the mutex parameters without deadlock.  This semantics means all functions with
     259the same mutex type(s) are part of a critical section for objects of that type
     260and only one runs at a time.
    209261
    210262\subsection{Threads}
    211 While coroutines allow new things to be done with a single execution path
    212 threads actually introduce new paths of execution that continue independently.
    213 Now for threads to work together their must be some communication between them
    214 and that means the timing of certain operations does have to be known. There
    215 or various means of syncronization and mutual exclution provided by \CFA but
    216 for exceptions only the basic two -- fork and join -- are needed.
    217 
    218 Threads are created like coroutines except the keyword is changed:
     263Functions, generators, and coroutines are sequential so there is only a single
     264(but potentially sophisticated) execution path in a program. Threads introduce
     265multiple execution paths that continue independently.
     266
     267For threads to work safely with objects requires mutual exclusion using
     268monitors and mutex parameters. For threads to work safely with other threads,
     269also requires mutual exclusion in the form of a communication rendezvous, which
     270also supports internal synchronization as for mutex objects. For exceptions
     271only the basic two basic operations are important: thread fork and join.
     272
     273Threads are created like coroutines with an associated @main@ function:
    219274\begin{cfa}
    220275thread StringWorker {
    221     const char * input;
    222     int result;
     276        const char * input;
     277        int result;
    223278};
    224 
    225279void main(StringWorker & this) {
    226     const char * localCopy = this.input;
    227     // ... do some work, perhaps hashing the string ...
    228     this.result = result;
    229 }
    230 \end{cfa}
    231 The main function will start executing after the fork operation and continue
    232 executing until it is finished. If another thread joins with this one it will
    233 wait until main has completed execution. In other words everything the thread
    234 does is between fork and join.
    235 
    236 From the outside this is the creation and destruction of the thread object.
    237 Fork happens after the constructor is run and join happens before the
    238 destructor runs. Join also happens during the @join@ function which
    239 can be used to join a thread earlier. If it is used the destructor does not
    240 join as that has already been completed.
     280        const char * localCopy = this.input;
     281        // ... do some work, perhaps hashing the string ...
     282        this.result = result;
     283}
     284{
     285        StringWorker stringworker; // fork thread running in "main"
     286} // implicitly join with thread $\(\Rightarrow\)$ wait for completion
     287\end{cfa}
     288The thread main is where a new thread starts execution after a fork operation
     289and then the thread continues executing until it is finished. If another thread
     290joins with an executing thread, it waits until the executing main completes
     291execution. In other words, everything a thread does is between a fork and join.
     292
     293From the outside, this behaviour is accomplished through creation and
     294destruction of a thread object.  Implicitly, fork happens after a thread
     295object's constructor is run and join happens before the destructor runs. Join
     296can also be specified explicitly using the @join@ function to wait for a
     297thread's completion independently from its deallocation (\ie destructor
     298call). If @join@ is called explicitly, the destructor does not implicitly join.
  • doc/theses/andrew_beach_MMath/features.tex

    rcd70477 rf99f5ba  
    1 \chapter{Features}
    2 
    3 This chapter covers the design and user interface of the \CFA exception
    4 handling mechanism.
    5 
    6 \section{Virtual Casts}
    7 
    8 Virtual casts and virtual types are not truly part of the exception system but
    9 they did not exist in \CFA and are useful in exceptions. So a minimal version
    10 of they virtual system was designed and implemented.
    11 
    12 Virtual types are organized in simple hierarchies. Each virtual type may have
    13 a parent and can have any number of children. A type's descendants are its
    14 children and its children's descendants. A type may not be its own descendant.
    15 
    16 Each virtual type has an associated virtual table type. A virtual table is a
    17 structure that has fields for all the virtual members of a type. A virtual
    18 type has all the virtual members of its parent and can add more. It may also
    19 update the values of the virtual members and should in many cases.
    20 
    21 Except for virtual casts, this is only used internally in the exception
    22 system. There is no general purpose interface for the other features. A
    23 a virtual cast has the following syntax:
    24 
    25 \begin{lstlisting}
     1\chapter{Exception Features}
     2
     3This chapter covers the design and user interface of the \CFA
     4exception-handling mechanism.
     5
     6\section{Virtuals}
     7Virtual types and casts are not required for a basic exception-system but are
     8useful for advanced exception features. However, \CFA is not object-oriented so
     9there is no obvious concept of virtuals.  Hence, to create advanced exception
     10features for this work, I needed to designed and implemented a virtual-like
     11system for \CFA.
     12
     13Object-oriented languages often organized exceptions into a simple hierarchy,
     14\eg Java.
     15\begin{center}
     16\setlength{\unitlength}{4000sp}%
     17\begin{picture}(1605,612)(2011,-1951)
     18\put(2100,-1411){\vector(1, 0){225}}
     19\put(3450,-1411){\vector(1, 0){225}}
     20\put(3550,-1411){\line(0,-1){225}}
     21\put(3550,-1636){\vector(1, 0){150}}
     22\put(3550,-1636){\line(0,-1){225}}
     23\put(3550,-1861){\vector(1, 0){150}}
     24\put(2025,-1490){\makebox(0,0)[rb]{\LstBasicStyle{exception}}}
     25\put(2400,-1460){\makebox(0,0)[lb]{\LstBasicStyle{arithmetic}}}
     26\put(3750,-1460){\makebox(0,0)[lb]{\LstBasicStyle{underflow}}}
     27\put(3750,-1690){\makebox(0,0)[lb]{\LstBasicStyle{overflow}}}
     28\put(3750,-1920){\makebox(0,0)[lb]{\LstBasicStyle{zerodivide}}}
     29\end{picture}%
     30\end{center}
     31The hierarchy provides the ability to handle an exception at different degrees
     32of specificity (left to right).  Hence, it is possible to catch a more general
     33exception-type in higher-level code where the implementation details are
     34unknown, which reduces tight coupling to the lower-level implementation.
     35Otherwise, low-level code changes require higher-level code changes, \eg,
     36changing from raising @underflow@ to @overflow@ at the low level means changing
     37the matching catch at the high level versus catching the general @arithmetic@
     38exception. In detail, each virtual type may have a parent and can have any
     39number of children. A type's descendants are its children and its children's
     40descendants. A type may not be its own descendant.
     41
     42The exception hierarchy allows a handler (@catch@ clause) to match multiple
     43exceptions, \eg a base-type handler catches both base and derived
     44exception-types.
     45\begin{cfa}
     46try {
     47        ...
     48} catch(arithmetic &) {
     49        ... // handle arithmetic, underflow, overflow, zerodivide
     50}
     51\end{cfa}
     52Most exception mechanisms perform a linear search of the handlers and select
     53the first matching handler, so the order of handers is now important because
     54matching is many to one.
     55
     56Each virtual type needs an associated virtual table. A virtual table is a
     57structure with fields for all the virtual members of a type. A virtual type has
     58all the virtual members of its parent and can add more. It may also update the
     59values of the virtual members and often does.
     60
     61While much of the virtual infrastructure is created, it is currently only used
     62internally for exception handling. The only user-level feature is the virtual
     63cast, which is the same as the \CC \lstinline[language=C++]|dynamic_cast|.
     64\label{p:VirtualCast}
     65\begin{cfa}
    2666(virtual TYPE)EXPRESSION
    27 \end{lstlisting}
    28 
    29 This has the same precedence as a traditional C-cast and can be used in the
    30 same places. This will convert the result of EXPRESSION to the type TYPE. Both
    31 the type of EXPRESSION and TYPE must be pointers to virtual types.
    32 
    33 The cast is checked and will either return the original value or null, based
    34 on the result of the check. The check is does the object pointed at have a
    35 type that is a descendant of the target type. If it is the result is the
    36 pointer, otherwise the result is null.
    37 
    38 \section{Exceptions}
     67\end{cfa}
     68Note, the syntax and semantics matches a C-cast, rather than the unusual \CC
     69syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be a
     70pointer to a virtual type. The cast dynamically checks if the @EXPRESSION@ type
     71is the same or a subtype of @TYPE@, and if true, returns a pointer to the
     72@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
     73
     74\section{Exception}
    3975% Leaving until later, hopefully it can talk about actual syntax instead
    4076% of my many strange macros. Syntax aside I will also have to talk about the
    4177% features all exceptions support.
    4278
    43 \subsection{Exception Traits}
    44 Exceptions are defined by the trait system; there are a series of traits and
    45 if a type satisfies them then they can be used as exceptions.
    46 
    47 \begin{lstlisting}
    48 trait is_exception(dtype exceptT, dtype virtualT) {
    49     virtualT const & get_exception_vtable(exceptT *);
     79Exceptions are defined by the trait system; there are a series of traits, and
     80if a type satisfies them, then it can be used as an exception.  The following
     81is the base trait all exceptions need to match.
     82\begin{cfa}
     83trait is_exception(exceptT &, virtualT &) {
     84        virtualT const & @get_exception_vtable@(exceptT *);
    5085};
    51 \end{lstlisting}
    52 This is the base trait that all exceptions need to match.
    53 The single function takes any pointer (including the null pointer) and
    54 returns a reference to the virtual table instance. Defining this function
    55 also establishes the virtual type and virtual table pair to the resolver
    56 and promises that @exceptT@ is a virtual type and a child of the
    57 base exception type.
    58 
    59 One odd thing about @get_exception_vtable@ is that it should always
    60 be a constant function, returning the same value regardless of its argument.
    61 A pointer or reference to the virtual table instance could be used instead,
    62 however using a function has some ease of implementation advantages and
    63 allows for easier disambiguation because the virtual type name (or the
    64 address of an instance that is in scope) can be used instead of the mangled
    65 virtual table name.
    66 
    67 Also note the use of the word ``promise" in the trait description. \CFA
    68 cannot currently check to see if either @exceptT@ or
    69 @virtualT@ match the layout requirements. Currently this is
    70 considered part of @get_exception_vtable@'s correct implementation.
    71 
    72 \begin{lstlisting}
     86\end{cfa}
     87The function takes any pointer, including the null pointer, and returns a
     88reference to the virtual-table object. Defining this function also establishes
     89the virtual type and a virtual-table pair to the \CFA type-resolver and
     90promises @exceptT@ is a virtual type and a child of the base exception-type.
     91
     92\PAB{I do not understand this paragraph.}
     93One odd thing about @get_exception_vtable@ is that it should always be a
     94constant function, returning the same value regardless of its argument.  A
     95pointer or reference to the virtual table instance could be used instead,
     96however using a function has some ease of implementation advantages and allows
     97for easier disambiguation because the virtual type name (or the address of an
     98instance that is in scope) can be used instead of the mangled virtual table
     99name.  Also note the use of the word ``promise'' in the trait
     100description. Currently, \CFA cannot check to see if either @exceptT@ or
     101@virtualT@ match the layout requirements. This is considered part of
     102@get_exception_vtable@'s correct implementation.
     103
     104\section{Raise}
     105\CFA provides two kinds of exception raise: termination
     106\see{\VRef{s:Termination}} and resumption \see{\VRef{s:Resumption}}, which are
     107specified with the following traits.
     108\begin{cfa}
    73109trait is_termination_exception(
    74         dtype exceptT, dtype virtualT | is_exception(exceptT, virtualT)) {
    75     void defaultTerminationHandler(exceptT &);
     110                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
     111        void @defaultTerminationHandler@(exceptT &);
    76112};
    77 \end{lstlisting}
    78 The only additional function required to make the exception usable with
    79 termination is a default handler. This function is called whenever a
    80 termination throw on an exception of this type is preformed and no handler
    81 is found.
    82 
    83 \begin{lstlisting}
     113\end{cfa}
     114The function is required to allow a termination raise, but is only called if a
     115termination raise does not find an appropriate handler.
     116
     117Allowing a resumption raise is similar.
     118\begin{cfa}
    84119trait is_resumption_exception(
    85         dtype exceptT, dtype virtualT | is_exception(exceptT, virtualT)) {
    86     void defaultResumptionHandler(exceptT &);
     120                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
     121        void @defaultResumptionHandler@(exceptT &);
    87122};
    88 \end{lstlisting}
    89 Creating a resumption exception is exactly the same except for resumption.
    90 The name change reflects that and the function is called when a resumption
    91 throw on an exception of this type is preformed and no handler is found.
    92 
    93 Finally there are three additional macros that can be used to refer to the
    94 these traits. They are @IS_EXCEPTION@,
    95 @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    96 Each takes the virtual type's name and, for polymorphic types only, the
    97 parenthesized list of polymorphic arguments. These do the name mangling to
    98 get the virtual table name and provide the arguments to both sides.
    99 
    100 \section{Termination}
    101 
    102 Termination exception throws are likely the most familiar kind, as they are
    103 used in several popular programming languages. A termination will throw an
    104 exception, search the stack for a handler, unwind the stack to where the
    105 handler is defined, execute the handler and then continue execution after
    106 the handler. They are used when execution cannot continue here.
    107 
    108 Termination has two pieces of syntax it uses. The first is the throw:
    109 \begin{lstlisting}
     123\end{cfa}
     124The function is required to allow a resumption raise, but is only called if a
     125resumption raise does not find an appropriate handler.
     126
     127Finally there are three convenience macros for referring to the these traits:
     128@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.  Each
     129takes the virtual type's name, and for polymorphic types only, the
     130parenthesized list of polymorphic arguments. These macros do the name mangling
     131to get the virtual-table name and provide the arguments to both sides
     132\PAB{What's a ``side''?}
     133
     134\subsection{Termination}
     135\label{s:Termination}
     136
     137Termination raise, called ``throw'', is familiar and used in most programming
     138languages with exception handling. The semantics of termination is: search the
     139stack for a matching handler, unwind the stack frames to the matching handler,
     140execute the handler, and continue execution after the handler. Termination is
     141used when execution \emph{cannot} return to the throw. To continue execution,
     142the program must \emph{recover} in the handler from the failed (unwound)
     143execution at the raise to safely proceed after the handler.
     144
     145A termination raise is started with the @throw@ statement:
     146\begin{cfa}
    110147throw EXPRESSION;
    111 \end{lstlisting}
    112 
    113 The expression must evaluate to a reference to a termination exception. A
    114 termination exception is any exception with a
    115 @void defaultTerminationHandler(T &);@ (the default handler) defined
    116 on it. The handler is taken from the call sight with \CFA's trait system and
    117 passed into the exception system along with the exception itself.
    118 
    119 The exception passed into the system is then copied into managed memory.
    120 This is to ensure it remains in scope during unwinding. It is the user's
    121 responsibility to make sure the original exception is freed when it goes out
    122 of scope. Being allocated on the stack is sufficient for this.
    123 
    124 Then the exception system will search the stack starting from the throw and
    125 proceeding towards the base of the stack, from callee to caller. As it goes
    126 it will check any termination handlers it finds:
    127 
    128 \begin{lstlisting}
    129 try {
    130     TRY_BLOCK
    131 } catch (EXCEPTION_TYPE * NAME) {
    132     HANDLER
    133 }
    134 \end{lstlisting}
    135 
    136 This shows a try statement with a single termination handler. The statements
    137 in TRY\_BLOCK will be executed when control reaches this statement. While
    138 those statements are being executed if a termination exception is thrown and
    139 it is not handled by a try statement further up the stack the EHM will check
    140 all of the terminations handlers attached to the try block, top to bottom.
    141 
    142 At each handler the EHM will check to see if the thrown exception is a
    143 descendant of EXCEPTION\_TYPE. If it is the pointer to the exception is
    144 bound to NAME and the statements in HANDLER are executed. If control reaches
    145 the end of the handler then it exits the block, the exception is freed and
    146 control continues after the try statement.
    147 
    148 The default handler is only used if no handler for the exception is found
    149 after the entire stack is searched. When that happens the default handler
    150 is called with a reference to the exception as its only argument. If the
    151 handler returns control continues from after the throw statement.
    152 
    153 \paragraph{Conditional Catches}
    154 
    155 Catch clauses may also be written as:
    156 \begin{lstlisting}
    157 catch (EXCEPTION_TYPE * NAME ; CONDITION)
    158 \end{lstlisting}
    159 This has the same behaviour as a regular catch clause except that if the
    160 exception matches the given type the condition is also run. If the result is
    161 true only then is this considered a matching handler. If the result is false
    162 then the handler does not match and the search continues with the next clause
    163 in the try block.
    164 
    165 The condition considers all names in scope at the beginning of the try block
    166 to be in scope along with the name introduce in the catch clause itself.
    167 
    168 \paragraph{Re-Throwing}
    169 
    170 You can also re-throw the most recent termination exception with
    171 @throw;@. % This is terrible and you should never do it.
    172 This can be done in a handler or any function that could be called from a
    173 handler.
    174 
    175 This will start another termination throw reusing the exception, meaning it
    176 does not copy the exception or allocated any more memory for it. However the
    177 default handler is still at the original through and could refer to data that
    178 was on the unwound section of the stack. So instead a new default handler that
    179 does a program level abort is used.
    180 
    181 \section{Resumption}
    182 
    183 Resumption exceptions are less popular then termination but in many
    184 regards are simpler and easier to understand. A resumption throws an exception,
    185 searches for a handler on the stack, executes that handler on top of the stack
    186 and then continues execution from the throw. These are used when a problem
    187 needs to be fixed before execution continues.
    188 
    189 A resumption is thrown with a throw resume statement:
    190 \begin{lstlisting}
     148\end{cfa}
     149The expression must return a termination-exception reference, where the
     150termination exception has a type with a @void defaultTerminationHandler(T &)@
     151(default handler) defined. The handler is found at the call site using \CFA's
     152trait system and passed into the exception system along with the exception
     153itself.
     154
     155At runtime, a representation of the exception type and an instance of the
     156exception type is copied into managed memory (heap) to ensure it remains in
     157scope during unwinding. It is the user's responsibility to ensure the original
     158exception object at the throw is freed when it goes out of scope. Being
     159allocated on the stack is sufficient for this.
     160
     161Then the exception system searches the stack starting from the throw and
     162proceeding towards the base of the stack, from callee to caller. At each stack
     163frame, a check is made for termination handlers defined by the @catch@ clauses
     164of a @try@ statement.
     165\begin{cfa}
     166try {
     167        GUARDED_BLOCK
     168} @catch (EXCEPTION_TYPE$\(_1\)$ * NAME)@ { // termination handler 1
     169        HANDLER_BLOCK$\(_1\)$
     170} @catch (EXCEPTION_TYPE$\(_2\)$ * NAME)@ { // termination handler 2
     171        HANDLER_BLOCK$\(_2\)$
     172}
     173\end{cfa}
     174The statements in the @GUARDED_BLOCK@ are executed. If those statements, or any
     175functions invoked from those statements, throws an exception, and the exception
     176is not handled by a try statement further up the stack, the termination
     177handlers are searched for a matching exception type from top to bottom.
     178
     179Exception matching checks the representation of the thrown exception-type is
     180the same or a descendant type of the exception types in the handler clauses. If
     181there is a match, a pointer to the exception object created at the throw is
     182bound to @NAME@ and the statements in the associated @HANDLER_BLOCK@ are
     183executed. If control reaches the end of the handler, the exception is freed,
     184and control continues after the try statement.
     185
     186The default handler visible at the throw statement is used if no matching
     187termination handler is found after the entire stack is searched. At that point,
     188the default handler is called with a reference to the exception object
     189generated at the throw. If the default handler returns, the system default
     190action is executed, which often terminates the program. This feature allows
     191each exception type to define its own action, such as printing an informative
     192error message, when an exception is not handled in the program.
     193
     194\subsection{Resumption}
     195\label{s:Resumption}
     196
     197Resumption raise, called ``resume'', is as old as termination
     198raise~\cite{Goodenough75} but is less popular. In many ways, resumption is
     199simpler and easier to understand, as it is simply a dynamic call (as in
     200Lisp). The semantics of resumption is: search the stack for a matching handler,
     201execute the handler, and continue execution after the resume. Notice, the stack
     202cannot be unwound because execution returns to the raise point. Resumption is
     203used used when execution \emph{can} return to the resume. To continue
     204execution, the program must \emph{correct} in the handler for the failed
     205execution at the raise so execution can safely continue after the resume.
     206
     207A resumption raise is started with the @throwResume@ statement:
     208\begin{cfa}
    191209throwResume EXPRESSION;
    192 \end{lstlisting}
    193 The result of EXPRESSION must be a resumption exception type. A resumption
    194 exception type is any type that satisfies the assertion
    195 @void defaultResumptionHandler(T &);@ (the default handler). When the
    196 statement is executed the expression is evaluated and the result is thrown.
    197 
    198 Handlers are declared using clauses in try statements:
    199 \begin{lstlisting}
    200 try {
    201     TRY_BLOCK
    202 } catchResume (EXCEPTION_TYPE * NAME) {
    203     HANDLER
    204 }
    205 \end{lstlisting}
    206 This is a simple example with the try block and a single resumption handler.
    207 Multiple resumption handlers can be put in a try statement and they can be
    208 mixed with termination handlers.
    209 
    210 When a resumption begins it will start searching the stack starting from
    211 the throw statement and working its way to the callers. In each try statement
    212 handlers will be tried top to bottom. Each handler is checked by seeing if
    213 the thrown exception is a descendant of EXCEPTION\_TYPE. If not the search
    214 continues. Otherwise NAME is bound to a pointer to the exception and the
    215 HANDLER statements are executed. After they are finished executing control
    216 continues from the throw statement.
    217 
    218 If no appropriate handler is found then the default handler is called. The
    219 throw statement acts as a regular function call passing the exception to
    220 the default handler and after the handler finishes executing control continues
    221 from the throw statement.
    222 
    223 The exception system also tracks the position of a search on the stack. If
    224 another resumption exception is thrown while a resumption handler is running
    225 it will first check handlers pushed to the stack by the handler and any
    226 functions it called, then it will continue from the try statement that the
    227 handler is a part of; except for the default handler where it continues from
    228 the throw the default handler was passed to.
    229 
    230 This makes the search pattern for resumption reflect the one for termination,
    231 which is what most users expect.
     210\end{cfa}
     211The semantics of the @throwResume@ statement are like the @throw@, but the
     212expression has a type with a @void defaultResumptionHandler(T &)@ (default
     213handler) defined, where the handler is found at the call site by the type
     214system.  At runtime, a representation of the exception type and an instance of
     215the exception type is \emph{not} copied because the stack is maintained during
     216the handler search.
     217
     218Then the exception system searches the stack starting from the resume and
     219proceeding towards the base of the stack, from callee to caller. At each stack
     220frame, a check is made for resumption handlers defined by the @catchResume@
     221clauses of a @try@ statement.
     222\begin{cfa}
     223try {
     224        GUARDED_BLOCK
     225} @catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME)@ { // resumption handler 1
     226        HANDLER_BLOCK$\(_1\)$
     227} @catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME)@ { // resumption handler 2
     228        HANDLER_BLOCK$\(_2\)$
     229}
     230\end{cfa}
     231The statements in the @GUARDED_BLOCK@ are executed. If those statements, or any
     232functions invoked from those statements, resumes an exception, and the
     233exception is not handled by a try statement further up the stack, the
     234resumption handlers are searched for a matching exception type from top to
     235bottom. (Note, termination and resumption handlers may be intermixed in a @try@
     236statement but the kind of raise (throw/resume) only matches with the
     237corresponding kind of handler clause.)
     238
     239The exception search and matching for resumption is the same as for
     240termination, including exception inheritance. The difference is when control
     241reaches the end of the handler: the resumption handler returns after the resume
     242rather than after the try statement. The resume point assumes the handler has
     243corrected the problem so execution can safely continue.
     244
     245Like termination, if no resumption handler is found, the default handler
     246visible at the resume statement is called, and the system default action is
     247executed.
     248
     249For resumption, the exception system uses stack marking to partition the
     250resumption search. If another resumption exception is raised in a resumption
     251handler, the second exception search does not start at the point of the
     252original raise. (Remember the stack is not unwound and the current handler is
     253at the top of the stack.) The search for the second resumption starts at the
     254current point on the stack because new try statements may have been pushed by
     255the handler or functions called from the handler. If there is no match back to
     256the point of the current handler, the search skips\label{p:searchskip} the stack frames already
     257searched by the first resume and continues after the try statement. The default
     258handler always continues from default handler associated with the point where
     259the exception is created.
    232260
    233261% This might need a diagram. But it is an important part of the justification
    234262% of the design of the traversal order.
    235 It also avoids the recursive resumption problem. If the entire stack is
    236 searched loops of resumption can form. Consider a handler that handles an
    237 exception of type A by resuming an exception of type B and on the same stack,
    238 later in the search path, is a second handler that handles B by resuming A.
    239 
    240 Assuming no other handlers on the stack handle A or B then in either traversal
    241 system an A resumed from the top of the stack will be handled by the first
    242 handler. A B resumed from the top or from the first handler it will be handled
    243 by the second handler. The only difference is when A is thrown from the second
    244 handler. The entire stack search will call the first handler again, creating a
    245 loop. Starting from the position in the stack though will break this loop.
    246 
    247 \paragraph{Conditional Catches}
    248 
    249 Resumption supports conditional catch clauses like termination does. They
    250 use the same syntax except the keyword is changed:
    251 \begin{lstlisting}
    252 catchResume (EXCEPTION_TYPE * NAME ; CONDITION) 
    253 \end{lstlisting}
    254 
    255 It also has the same behaviour, after the exception type has been matched
    256 with the EXCEPTION\_TYPE the CONDITION is evaluated with NAME in scope. If
    257 the result is true then the handler is run, otherwise the search continues
    258 just as if there had been a type mismatch.
    259 
    260 \paragraph{Re-Throwing}
    261 
    262 You may also re-throw resumptions with a @throwResume;@ statement.
    263 This can only be done from inside of a @catchResume@ block.
    264 
    265 Outside of any side effects of any code already run in the handler this will
    266 have the same effect as if the exception had not been caught in the first
    267 place.
     263\begin{verbatim}
     264       throwResume2 ----------.
     265            |                 |
     266 generated from handler       |
     267            |                 |
     268         handler              |
     269            |                 |
     270        throwResume1 -----.   :
     271            |             |   :
     272           try            |   : search skip
     273            |             |   :
     274        catchResume  <----'   :
     275            |                 |
     276\end{verbatim}
     277
     278This resumption search-pattern reflect the one for termination, which matches
     279with programmer expectations. However, it avoids the \emph{recursive
     280resumption} problem. If parts of the stack are searched multiple times, loops
     281can easily form resulting in infinite recursion.
     282
     283Consider the trivial case:
     284\begin{cfa}
     285try {
     286        throwResume$\(_1\)$ (E &){};
     287} catch( E * ) {
     288        throwResume;
     289}
     290\end{cfa}
     291Based on termination semantics, programmer expectation is for the re-resume to
     292continue searching the stack frames after the try statement. However, the
     293current try statement is still on the stack below the handler issuing the
     294reresume \see{\VRef{s:Reraise}}. Hence, the try statement catches the re-raise
     295again and does another re-raise \emph{ad infinitum}, which is confusing and
     296difficult to debug. The \CFA resumption search-pattern skips the try statement
     297so the reresume search continues after the try, mathcing programmer
     298expectation.
     299
     300\section{Conditional Catch}
     301Both termination and resumption handler-clauses may perform conditional matching:
     302\begin{cfa}
     303catch (EXCEPTION_TYPE * NAME ; @CONDITION@)
     304\end{cfa}
     305First, the same semantics is used to match the exception type. Second, if the
     306exception matches, @CONDITION@ is executed. The condition expression may
     307reference all names in scope at the beginning of the try block and @NAME@
     308introduced in the handler clause.  If the condition is true, then the handler
     309matches. Otherwise, the exception search continues at the next appropriate kind
     310of handler clause in the try block.
     311\begin{cfa}
     312try {
     313        f1 = open( ... );
     314        f2 = open( ... );
     315        ...
     316} catch( IOFailure * f ; fd( f ) == f1 ) {
     317        // only handle IO failure for f1
     318}
     319\end{cfa}
     320Note, catching @IOFailure@, checking for @f1@ in the handler, and reraising the
     321exception if not @f1@ is different because the reraise does not examine any of
     322remaining handlers in the current try statement.
     323
     324\section{Reraise}
     325\label{s:Reraise}
     326Within the handler block or functions called from the handler block, it is
     327possible to reraise the most recently caught exception with @throw@ or
     328@throwResume@, respective.
     329\begin{cfa}
     330catch( ... ) {
     331        ... throw; // rethrow
     332} catchResume( ... ) {
     333        ... throwResume; // reresume
     334}
     335\end{cfa}
     336The only difference between a raise and a reraise is that reraise does not
     337create a new exception; instead it continues using the current exception, \ie
     338no allocation and copy. However the default handler is still set to the one
     339visible at the raise point, and hence, for termination could refer to data that
     340is part of an unwound stack frame. To prevent this problem, a new default
     341handler is generated that does a program-level abort.
     342
    268343
    269344\section{Finally Clauses}
    270 
    271 A @finally@ clause may be placed at the end of a try statement after
    272 all the handler clauses. In the simply case, with no handlers, it looks like
    273 this:
    274 
    275 \begin{lstlisting}
    276 try {
    277     TRY_BLOCK
     345A @finally@ clause may be placed at the end of a @try@ statement.
     346\begin{cfa}
     347try {
     348        GUARDED_BLOCK
     349} ...   // any number or kind of handler clauses
    278350} finally {
    279     FINAL_STATEMENTS
    280 }
    281 \end{lstlisting}
    282 
    283 Any number of termination handlers and resumption handlers may proceed the
    284 finally clause.
    285 
    286 The FINAL\_STATEMENTS, the finally block, are executed whenever the try
    287 statement is removed from the stack. This includes: the TRY\_BLOCK finishes
    288 executing, a termination exception finishes executing and the stack unwinds.
    289 
    290 Execution of the finally block should finish by letting control run off
    291 the end of the block. This is because after the finally block is complete
    292 control will continue to where ever it would if the finally clause was not
    293 present.
    294 
    295 Because of this local control flow out of the finally block is forbidden.
    296 The compiler rejects uses of @break@, @continue@,
    297 @fallthru@ and @return@ that would cause control to leave
    298 the finally block. Other ways to leave the finally block - such as a long
    299 jump or termination - are much harder to check, at best requiring additional
    300 run-time overhead, and so are merely discouraged.
     351        FINALLY_BLOCK
     352}
     353\end{cfa}
     354The @FINALLY_BLOCK@ is executed when the try statement is unwound from the
     355stack, \ie when the @GUARDED_BLOCK@ or any handler clause finishes. Hence, the
     356finally block is always executed.
     357
     358Execution of the finally block should always finish, meaning control runs off
     359the end of the block. This requirement ensures always continues as if the
     360finally clause is not present, \ie finally is for cleanup not changing control
     361flow.  Because of this requirement, local control flow out of the finally block
     362is forbidden.  The compiler precludes any @break@, @continue@, @fallthru@ or
     363@return@ that causes control to leave the finally block. Other ways to leave
     364the finally block, such as a long jump or termination are much harder to check,
     365and at best requiring additional run-time overhead, and so are discouraged.
    301366
    302367\section{Cancellation}
    303 
    304 Cancellation can be thought of as a stack-level abort or as an uncatchable
    305 termination. It unwinds the entirety of the current exception and if possible
    306 passes an exception to a different stack as a message.
    307 
    308 There is no special statement for starting a cancellation, instead you call
    309 the standard library function @cancel\_stack@ which takes an exception.
    310 Unlike in a throw this exception is not used in control flow but is just there
    311 to pass information about why the cancellation happened.
    312 
    313 The handler is decided entirely by which stack is being canceled. There are
    314 three handlers that apply to three different groups of stacks:
    315 \begin{itemize}
    316 \item Main Stack:
    317 The main stack is the one on which the program main is called at the beginning
    318 of your program. It is also the only stack you have without the libcfathreads.
    319 
    320 Because of this there is no other stack ``above" (or possibly at all) for main
    321 to notify when a cancellation occurs. So after the stack is unwound we do a
    322 program level abort.
    323 
    324 \item Thread Stack:
    325 Thread stacks are those created @thread@ or otherwise satisfy the
    326 @is\_thread@ trait.
    327 
    328 Threads only have two structural points of communication that must happen,
    329 start and join. As the thread must be running to preform a cancellation it
    330 will be after start and before join, so join is one cancellation uses.
    331 
    332 After the stack is unwound the thread will halt as if had completed normally
    333 and wait for another thread to join with it. The other thread, when it joins,
    334 checks for a cancellation. If so it will throw the resumption exception
    335 @ThreadCancelled@.
    336 
    337 There is a difference here in how explicate joins (with the @join@
    338 function) and implicate joins (from a destructor call). Explicate joins will
    339 take the default handler (@defaultResumptionHandler@) from the context
    340 and use like a regular through does if the exception is not caught. The
    341 implicate join does a program abort instead.
    342 
    343 This is for safety. One of the big problems in exceptions is you cannot handle
    344 two terminations or cancellations on the same stack as either can destroy the
    345 context required for the other. This can happen with join but as the
    346 destructors will always be run when the stack is being unwound and one
     368Cancellation is a stack-level abort, which can be thought of as as an
     369uncatchable termination. It unwinds the entirety of the current stack, and if
     370possible forwards the cancellation exception to a different stack.
     371
     372There is no special statement for starting a cancellation; instead the standard
     373library function @cancel_stack@ is called passing an exception.  Unlike a
     374raise, this exception is not used in matching only to pass information about
     375the cause of the cancellation.
     376
     377Handling of a cancellation depends on which stack is being cancelled.
     378\begin{description}
     379\item[Main Stack:]
     380The main stack is the one used by the program main at the start of execution,
     381and is the only stack in a sequential program.  Hence, when cancellation is
     382forwarded to the main stack, there is no other forwarding stack, so after the
     383stack is unwound, there is a program-level abort.
     384
     385\item[Thread Stack:]
     386A thread stack is created for a @thread@ object or object that satisfies the
     387@is_thread@ trait.  A thread only has two points of communication that must
     388happen: start and join. As the thread must be running to perform a
     389cancellation, it must occur after start and before join, so join is a
     390cancellation point.  After the stack is unwound, the thread halts and waits for
     391another thread to join with it. The joining thread, checks for a cancellation,
     392and if present, resumes exception @ThreadCancelled@.
     393
     394There is a subtle difference between the explicit join (@join@ function) and
     395implicit join (from a destructor call). The explicit join takes the default
     396handler (@defaultResumptionHandler@) from its calling context, which is used if
     397the exception is not caught. The implicit join does a program abort instead.
     398
     399This semantics is for safety. One difficult problem for any exception system is
     400defining semantics when an exception is raised during an exception search:
     401which exception has priority, the original or new exception? No matter which
     402exception is selected, it is possible for the selected one to disrupt or
     403destroy the context required for the other. \PAB{I do not understand the
     404following sentences.} This loss of information can happen with join but as the
     405thread destructor is always run when the stack is being unwound and one
    347406termination/cancellation is already active. Also since they are implicit they
    348407are easier to forget about.
    349408
    350 \item Coroutine Stack:
    351 Coroutine stacks are those created with @coroutine@ or otherwise
    352 satisfy the @is\_coroutine@ trait.
    353 
    354 A coroutine knows of two other coroutines, its starter and its last resumer.
    355 The last resumer is ``closer" so that is the one notified.
    356 
    357 After the stack is unwound control goes to the last resumer.
    358 Resume will resume throw a @CoroutineCancelled@ exception, which is
    359 polymorphic over the coroutine type and has a pointer to the coroutine being
    360 canceled and the canceling exception. The resume function also has an
    361 assertion that the @defaultResumptionHandler@ for the exception. So it
    362 will use the default handler like a regular throw.
    363 
    364 \end{itemize}
     409\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
     410or object that satisfies the @is_coroutine@ trait.  A coroutine only knows of
     411two other coroutines, its starter and its last resumer.  The last resumer has
     412the tightest coupling to the coroutine it activated.  Hence, cancellation of
     413the active coroutine is forwarded to the last resumer after the stack is
     414unwound, as the last resumer has the most precise knowledge about the current
     415execution. When the resumer restarts, it resumes exception
     416@CoroutineCancelled@, which is polymorphic over the coroutine type and has a
     417pointer to the cancelled coroutine.
     418
     419The resume function also has an assertion that the @defaultResumptionHandler@
     420for the exception. So it will use the default handler like a regular throw.
     421\end{description}
  • doc/theses/andrew_beach_MMath/future.tex

    rcd70477 rf99f5ba  
    11\chapter{Future Work}
    22
     3\section{Language Improvements}
     4\CFA is a developing programming language. As such, there are partially or
     5unimplemented features of the language (including several broken components)
     6that I had to workaround while building an exception handling system largely in
     7the \CFA language (some C components).  The following are a few of these
     8issues, and once implemented/fixed, how this would affect the exception system.
     9\begin{itemize}
     10\item
     11The implementation of termination is not portable because it includes
     12hand-crafted assembly statements. These sections must be generalized to support
     13more hardware architectures, \eg ARM processor.
     14\item
     15Due to a type-system problem, the catch clause cannot bind the exception to a
     16reference instead of a pointer. Since \CFA has a very general reference
     17capability, programmers will want to use it. Once fixed, this capability should
     18result in little or no change in the exception system.
     19\item
     20Termination handlers cannot use local control-flow transfers, \eg by @break@,
     21@return@, \etc. The reason is that current code generation hoists a handler
     22into a nested function for convenience (versus assemble-code generation at the
     23@try@ statement). Hence, when the handler runs, its code is not in the lexical
     24scope of the @try@ statement, where the local control-flow transfers are
     25meaningful.
     26\end{itemize}
     27
    328\section{Complete Virtual System}
    4 The virtual system should be completed. It was never supposed to be part of
    5 this project and so minimal work was done on it. A draft of what the complete
    6 system might look like was created but it was never finalized or implemented.
    7 A future project in \CFA would be to complete that work and to update the
    8 parts of the exception system that use the current version.
     29The virtual system should be completed. It was not supposed to be part of this
     30project, but was thrust upon it to do exception inheritance; hence, only
     31minimal work was done. A draft for a complete virtual system is available but
     32it is not finalized.  A future \CFA project is to complete that work and then
     33update the exception system that uses the current version.
    934
    10 There are several improvements to the virtual system that would improve
    11 the exception traits. The biggest one is an assertion that checks that one
    12 virtual type is a child of another virtual type. This would capture many of
    13 the requirements much more precisely.
     35There are several improvements to the virtual system that would improve the
     36exception traits. The most important one is an assertion to check one virtual
     37type is a child of another. This check precisely captures many of the
     38correctness requirements.
    1439
    1540The full virtual system might also include other improvement like associated
    16 types. This is a proposed feature that would allow traits to refer to types
    17 not listed in their header. This would allow the exception traits to not
    18 refer to the virtual table type explicatly which would remove the need for
    19 the interface macros.
     41types to allow traits to refer to types not listed in their header. This
     42feature allows exception traits to not refer to the virtual-table type
     43explicitly, removing the need for the current interface macros.
    2044
    21 \section{Additional Throws}
    22 Several other kinds of throws, beyond the termination throw (@throw@),
    23 the resumption throw (@throwResume@) and the re-throws, were considered.
    24 None were as useful as the core throws but they would likely be worth
    25 revising.
     45\section{Additional Raises}
     46Several other kinds of exception raises were considered beyond termination
     47(@throw@), resumption (@throwResume@), and reraise.
    2648
    27 The first ones are throws for asynchronous exceptions, throwing exceptions
    28 from one stack to another. These act like signals allowing for communication
    29 between the stacks. This is usually used with resumption as it allows the
    30 target stack to continue execution normally after the exception has been
    31 handled.
     49The first is a non-local/concurrent raise providing asynchronous exceptions,
     50\ie raising an exception on another stack. This semantics acts like signals
     51allowing for out-of-band communication among coroutines and threads. This kind
     52of raise is often restricted to resumption to allow the target stack to
     53continue execution normally after the exception has been handled. That is,
     54allowing one coroutine/thread to unwind the stack of another via termination is
     55bad software engineering.
    3256
    33 This would much more coordination between the concurrency system and the
    34 exception system to handle. Most of the interesting design decisions around
    35 applying asynchronous exceptions appear to be around masking (controlling
    36 which exceptions may be thrown at a stack). It would likely require more of
    37 the virtual system and would also effect how default handlers are set.
     57Non-local/concurrent requires more coordination between the concurrency system
     58and the exception system. Many of the interesting design decisions centre
     59around masking (controlling which exceptions may be thrown at a stack). It
     60would likely require more of the virtual system and would also effect how
     61default handlers are set.
    3862
    39 The other throws were designed to mimic bidirectional algebraic effects.
    40 Algebraic effects are used in some functional languages and allow a function
     63Other raises were considered to mimic bidirectional algebraic effects.
     64Algebraic effects are used in some functional languages allowing one function
    4165to have another function on the stack resolve an effect (which is defined with
    42 a function-like interface).
    43 These can be mimiced with resumptions and the the new throws were designed
    44 to try and mimic bidirectional algebraic effects, where control can go back
    45 and forth between the function effect caller and handler while the effect
    46 is underway.
     66a functional-like interface).  This semantics can be mimicked with resumptions
     67and new raises were discussed to mimic bidirectional algebraic-effects, where
     68control can go back and forth between the function-effect caller and handler
     69while the effect is underway.
    4770% resume-top & resume-reply
     71These raises would be like the resumption raise except using different search
     72patterns to find the handler.
    4873
    49 These throws would likely be just like the resumption throw except they would
    50 use different search patterns to find the handler to reply to.
     74\section{Zero-Cost Try}
     75\CFA does not have zero-cost try-statements because the compiler generates C
     76code rather than assembler code \see{\VPageref{p:zero-cost}}. When the compiler
     77does create its own assembly (or LLVM byte-code), then zero-cost try-statements
     78are possible. The downside of zero-cost try-statements is the LSDA complexity,
     79its size (program bloat), and the high cost of raising an exception.
    5180
    52 \section{Zero-Cost Exceptions}
    53 \CFA does not have zero-cost exceptions because it does not generate assembly
    54 but instead generates C code. See the implementation section. When the
    55 compiler does start to create its own assembly (or LLVM byte code) then
    56 zero-cost exceptions could be implemented.
     81Alternatively, some research could be done into the simpler alternative method
     82with a non-zero-cost try-statement but much lower cost exception raise. For
     83example, programs are starting to use exception in the normal control path, so
     84more exceptions are thrown. In these cases, the cost balance switches towards
     85low-cost raise. Unfortunately, while exceptions remain exceptional, the
     86libunwind model will probably remain the most effective option.
    5787
    58 Now in zero-cost exceptions the only part that is zero-cost are the try
    59 blocks. Some research could be done into the alternative methods for systems
    60 that expect a lot more exceptions to be thrown, allowing some overhead in
    61 entering and leaving try blocks to make throws faster. But while exceptions
    62 remain exceptional the libunwind model will probably remain the most effective
    63 option.
     88Zero-cost resumptions is still an open problem. First, because libunwind does
     89not support a successful-exiting stack-search without doing an unwind.
     90Workarounds are possible but awkward. Ideally an extension to libunwind could
     91be made, but that would either require separate maintenance or gain enough
     92support to have it folded into the standard.
    6493
    65 Zero-cost resumptions have more problems to solve. First because libunwind
    66 does not support a successful exiting stack search without doing an unwind.
    67 There are several ways to hack that functionality in. Ideally an extension to
    68 libunwind could be made, but that would either require seperate maintenance
    69 or gain enough support to have it folded into the standard.
    70 
    71 Also new techniques to skip previously searched parts of the stack will have
    72 to be developed. The recursive resume problem still remains and ideally the
    73 same pattern of ignoring sections of the stack.
     94Also new techniques to skip previously searched parts of the stack need to be
     95developed to handle the recursive resume problem and support advanced algebraic
     96effects.
    7497
    7598\section{Signal Exceptions}
    76 Exception Handling: Issues and a Proposed Notation suggests there are three
    77 types of exceptions: escape, notify and signal.
    78 Escape exceptions are our termination exceptions, notify exceptions are
    79 resumption exceptions and that leaves signal exception unimplemented.
     99Goodenough~\cite{Goodenough75} suggests three types of exceptions: escape,
     100notify and signal.  Escape are termination exceptions, notify are resumption
     101exceptions, leaving signal unimplemented.
    80102
    81 Signal exceptions allow either behaviour, that is after the exception is
    82 handled control can either return to the throw or from where the handler is
    83 defined.
     103A signal exception allows either behaviour, \ie after an exception is handled,
     104the handler has the option of returning to the raise or after the @try@
     105statement. Currently, \CFA fixes the semantics of the handler return
     106syntactically by the @catch@ or @catchResume@ clause.
    84107
    85 The design should be rexamined and be updated for \CFA. A very direct
    86 translation would perhaps have a new throw and catch pair and a statement
    87 (or statements) could be used to decide if the handler returns to the throw
    88 or continues where it is, but there are other options.
     108Signal exception should be reexamined and possibly be supported in \CFA. A very
     109direct translation is to have a new raise and catch pair, and a new statement
     110(or statements) would indicate if the handler returns to the raise or continues
     111where it is; but there may be other options.
    89112
    90 For instance resumption could be extended to cover this use by allowing
    91 local control flow out of it. This would require an unwind as part of the
    92 transition as there are stack frames that have to be removed.
    93 This would mean there is no notify like throw but because \CFA does not have
    94 exception signatures a termination can be thrown from any resumption handler
    95 already so there are already ways one could try to do this in existing \CFA.
     113For instance, resumption could be extended to cover this use by allowing local
     114control flow out of it. This approach would require an unwind as part of the
     115transition as there are stack frames that have to be removed.  This approach
     116means there is no notify raise, but because \CFA does not have exception
     117signatures, a termination can be thrown from within any resumption handler so
     118there is already a way to do mimic this in existing \CFA.
    96119
    97120% Maybe talk about the escape; and escape CONTROL_STMT; statements or how
    98121% if we could choose if _Unwind_Resume proceeded to the clean-up stage this
    99122% would be much easier to implement.
    100 
    101 \section{Language Improvements}
    102 There is also a lot of work that are not follow ups to this work in terms of
    103 research, some have no interesting research to be done at all, but would
    104 improve \CFA as a programming language. The full list of these would
    105 naturally be quite extensive but here are a few examples that involve
    106 exceptions:
    107 
    108 \begin{itemize}
    109 \item The implementation of termination is not portable because it includes
    110 some assembly statements. These sections will have to be re-written to so
    111 \CFA has full support on more machines.
    112 \item Allowing exception handler to bind the exception to a reference instead
    113 of a pointer. This should actually result in no change in behaviour so there
    114 is no reason not to allow it. It is however a small improvement; giving a bit
    115 of flexibility to the user in what style they want to use.
    116 \item Enabling local control flow (by @break@, @return@ and
    117 similar statements) out of a termination handler. The current set-up makes
    118 this very difficult but the catch function that runs the handler after it has
    119 been matched could be inlined into the function's body, which would make this
    120 much easier. (To do the same for try blocks would probably wait for zero-cost
    121 exceptions, which would allow the try block to be inlined as well.)
    122 \end{itemize}
  • doc/theses/andrew_beach_MMath/implement.tex

    rcd70477 rf99f5ba  
    22% Goes over how all the features are implemented.
    33
     4The implementation work for this thesis covers two components: the virtual
     5system and exceptions. Each component is discussed in detail.
     6
    47\section{Virtual System}
     8\label{s:VirtualSystem}
    59% Virtual table rules. Virtual tables, the pointer to them and the cast.
    6 The \CFA virtual system only has one public facing feature: virtual casts.
    7 However there is a lot of structure to support that and provide some other
    8 features for the standard library.
    9 
    10 All of this is accessed through a field inserted at the beginning of every
    11 virtual type. Currently it is called @virtual_table@ but it is not
    12 ment to be accessed by the user. This field is a pointer to the type's
    13 virtual table instance. It is assigned once during the object's construction
    14 and left alone after that.
    15 
    16 \subsection{Virtual Table Construction}
    17 For each virtual type a virtual table is constructed. This is both a new type
    18 and an instance of that type. Other instances of the type could be created
    19 but the system doesn't use them. So this section will go over the creation of
    20 the type and the instance.
    21 
    22 Creating the single instance is actually very important. The address of the
    23 table acts as the unique identifier for the virtual type. Similarly the first
    24 field in every virtual table is the parent's id; a pointer to the parent
    25 virtual table instance.
    26 
    27 The remaining fields contain the type's virtual members. First come the ones
    28 present on the parent type, in the same order as they were the parent, and
    29 then any that this type introduces. The types of the ones inherited from the
    30 parent may have a slightly modified type, in that references to the
    31 dispatched type are replaced with the current virtual type. These are always
    32 taken by pointer or reference.
    33 
    34 The structure itself is created where the virtual type is created. The name
    35 of the type is created by mangling the name of the base type. The name of the
    36 instance is also generated by name mangling.
    37 
    38 The fields are initialized automatically.
     10While the \CFA virtual system currently has only one public feature, virtual
     11cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to
     12support it, and provide features for exception handling and the standard
     13library.
     14
     15\subsection{Virtual Table}
     16The virtual system is accessed through a private constant field inserted at the
     17beginning of every virtual type, called the virtual-table pointer. This field
     18points at a type's virtual table and is assigned during the object's
     19construction.  The address of a virtual table acts as the unique identifier for
     20the virtual type, and the first field of a virtual table is a pointer to the
     21parent virtual-table or @0p@.  The remaining fields are duplicated from the
     22parent tables in this type's inheritance chain, followed by any fields this type
     23introduces. Parent fields are duplicated so they can be changed (\CC
     24\lstinline[language=c++]|override|), so that references to the dispatched type
     25are replaced with the current virtual type.
     26\PAB{Can you create a simple diagram of the layout?}
     27% These are always taken by pointer or reference.
     28
     29% For each virtual type, a virtual table is constructed. This is both a new type
     30% and an instance of that type. Other instances of the type could be created
     31% but the system doesn't use them. So this section will go over the creation of
     32% the type and the instance.
     33
     34A virtual table is created when the virtual type is created. The name of the
     35type is created by mangling the name of the base type. The name of the instance
     36is also generated by name mangling.  The fields are initialized automatically.
    3937The parent field is initialized by getting the type of the parent field and
    4038using that to calculate the mangled name of the parent's virtual table type.
    4139There are two special fields that are included like normal fields but have
    4240special initialization rules: the @size@ field is the type's size and is
    43 initialized with a sizeof expression, the @align@ field is the type's
    44 alignment and uses an alignof expression. The remaining fields are resolved
    45 to a name matching the field's name and type using the normal visibility
    46 and overload resolution rules of the type system.
    47 
    48 These operations are split up into several groups depending on where they
    49 take place which can vary for monomorphic and polymorphic types. The first
    50 devision is between the declarations and the definitions. Declarations, such
    51 as a function signature or a structure's name, must always be visible but may
    52 be repeated so they go in headers. Definitions, such as function bodies and a
    53 structure's layout, don't have to be visible on use but must occur exactly
    54 once and go into source files.
    55 
     41initialized with a @sizeof@ expression, the @align@ field is the type's
     42alignment and uses an @alignof@ expression. The remaining fields are resolved
     43to a name matching the field's name and type using the normal visibility and
     44overload resolution rules of the type system.
     45
     46These operations are split up into several groups depending on where they take
     47place which varies for monomorphic and polymorphic types. The first devision is
     48between the declarations and the definitions. Declarations, such as a function
     49signature or a aggregate's name, must always be visible but may be repeated in
     50the form of forward declarations in headers. Definitions, such as function
     51bodies and a aggregate's layout, can be separately compiled but must occur
     52exactly once in a source file.
     53
     54\begin{sloppypar}
    5655The declarations include the virtual type definition and forward declarations
    5756of the virtual table instance, constructor, message function and
    58 @get_exception_vtable@. The definition includes the storage and
    59 initialization of the virtual table instance and the bodies of the three
    60 functions.
     57@get_exception_vtable@. The definition includes the storage and initialization
     58of the virtual table instance and the bodies of the three functions.
     59\end{sloppypar}
    6160
    6261Monomorphic instances put all of these two groups in one place each.
    63 
    64 Polymorphic instances also split out the core declarations and definitions
    65 from the per-instance information. The virtual table type and most of the
    66 functions are polymorphic so they are all part of the core. The virtual table
    67 instance and the @get_exception_vtable@ function.
    68 
     62Polymorphic instances also split out the core declarations and definitions from
     63the per-instance information. The virtual table type and most of the functions
     64are polymorphic so they are all part of the core. The virtual table instance
     65and the @get_exception_vtable@ function.
     66
     67\begin{sloppypar}
    6968Coroutines and threads need instances of @CoroutineCancelled@ and
    70 @ThreadCancelled@ respectively to use all of their functionality.
    71 When a new data type is declared with @coroutine@ or @thread@
    72 the forward declaration for the instance is created as well. The definition
    73 of the virtual table is created at the definition of the main function.
     69@ThreadCancelled@ respectively to use all of their functionality.  When a new
     70data type is declared with @coroutine@ or @thread@ the forward declaration for
     71the instance is created as well. The definition of the virtual table is created
     72at the definition of the main function.
     73\end{sloppypar}
    7474
    7575\subsection{Virtual Cast}
    76 Virtual casts are implemented as a function call that does the check and a
    77 old C-style cast to do the type conversion. The C-cast is just to make sure
    78 the generated code is correct so the rest of the section is about that
    79 function.
    80 
    81 The function is @__cfa__virtual_cast@ and it is implemented in the
    82 standard library. It takes a pointer to the target type's virtual table and
    83 the object pointer being cast. The function is very simple, getting the
    84 object's virtual table pointer and then checking to see if it or any of
    85 its ancestors, by using the parent pointers, are the same as the target type
    86 virtual table pointer. It does this in a simple loop.
    87 
    88 For the generated code a forward decaration of the virtual works as follows.
    89 There is a forward declaration of @__cfa__virtual_cast@ in every cfa
    90 file so it can just be used. The object argument is the expression being cast
    91 so that is just placed in the argument list.
    92 
    93 To build the target type parameter the compiler will create a mapping from
    94 concrete type-name -- so for polymorphic types the parameters are filled in
    95 -- to virtual table address. Every virtual table declaraction is added to the
    96 this table; repeats are ignored unless they have conflicting definitions.
    97 This does mean the declaractions have to be in scope, but they should usually
    98 be introduced as part of the type definition.
     76Virtual casts are implemented as a function call that does the subtype check
     77and a C coercion-cast to do the type conversion.
     78% The C-cast is just to make sure the generated code is correct so the rest of
     79% the section is about that function.
     80The function is
     81\begin{cfa}
     82void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
     83        struct __cfa__parent_vtable const * const * child );
     84}
     85\end{cfa}
     86and it is implemented in the standard library. It takes a pointer to the target
     87type's virtual table and the object pointer being cast. The function performs a
     88linear search starting at the object's virtual-table and walking through the
     89the parent pointers, checking to if it or any of its ancestors are the same as
     90the target-type virtual table-pointer.
     91
     92For the generated code, a forward declaration of the virtual works as follows.
     93There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so
     94it can just be used. The object argument is the expression being cast so that
     95is just placed in the argument list.
     96
     97To build the target type parameter, the compiler creates a mapping from
     98concrete type-name -- so for polymorphic types the parameters are filled in --
     99to virtual table address. Every virtual table declaration is added to the this
     100table; repeats are ignored unless they have conflicting definitions.  Note,
     101these declarations do not have to be in scope, but they should usually be
     102introduced as part of the type definition.
     103
     104\PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to
     105write more to make it clear.}
     106
    99107
    100108\section{Exceptions}
     
    106114% resumption doesn't as well.
    107115
    108 Many modern languages work with an interal stack that function push and pop
    109 their local data to. Stack unwinding removes large sections of the stack,
    110 often across functions.
    111 
    112 At a very basic level this can be done with @setjmp@ \& @longjmp@
    113 which simply move the top of the stack, discarding everything on the stack
    114 above a certain point. However this ignores all the clean-up code that should
    115 be run when certain sections of the stack are removed (for \CFA these are from
    116 destructors and finally clauses) and also requires that the point to which the
    117 stack is being unwound is known ahead of time. libunwind is used to address
    118 both of these problems.
    119 
    120 Libunwind, provided in @unwind.h@ on most platorms, is a C library
    121 that provides \CPP style stack unwinding. Its operation is divided into two
    122 phases. The search phase -- phase 1 -- is used to scan the stack and decide
    123 where the unwinding will stop, this allows for a dynamic target. The clean-up
    124 phase -- phase 2 -- does the actual unwinding and also runs any clean-up code
    125 as it goes.
    126 
    127 To use the libunwind each function must have a personality function and an
    128 LSDA (Language Specific Data Area). Libunwind actually does very little, it
    129 simply moves down the stack from function to function. Most of the actions are
    130 implemented by the personality function which libunwind calls on every
    131 function. Since this is shared across many functions or even every function in
    132 a language it will need a bit more information. This is provided by the LSDA
    133 which has the unique information for each function.
    134 
    135 Theoretically the LSDA can contain anything but conventionally it is a table
    136 with entries reperenting areas of the function and what has to be done there
    137 during unwinding. These areas are described in terms of where the instruction
    138 pointer is. If the current value of the instruction pointer is between two
    139 values reperenting the beginning and end of a region then execution is
    140 currently being executed. These are used to mark out try blocks and the
    141 scopes of objects with destructors to run.
    142 
    143 GCC will generate an LSDA and attach its personality function with the
    144 @-fexceptions@ flag. However this only handles the cleanup attribute.
    145 This attribute is used on a variable and specifies a function that should be
    146 run when the variable goes out of scope. The function is passed a pointer to
    147 the object as well so it can be used to mimic destructors. It however cannot
    148 be used to mimic try statements.
    149 
    150 \subsection{Implementing Personality Functions}
    151 Personality functions have a complex interface specified by libunwind.
    152 This section will cover some of the important parts of that interface.
    153 
    154 \begin{lstlisting}
    155 typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn)(
    156     int version,
    157     _Unwind_Action action,
    158     _Unwind_Exception_Class exception_class,
    159     _Unwind_Exception * exception,
    160     struct _Unwind_Context * context);
     116% Many modern languages work with an interal stack that function push and pop
     117% their local data to. Stack unwinding removes large sections of the stack,
     118% often across functions.
     119
     120Stack unwinding is the process of removing stack frames (activations) from the
     121stack. On function entry and return, unwinding is handled directly by the code
     122embedded in the function. Usually, the stack-frame size is known statically
     123based on parameter and local variable declarations.  For dynamically-sized
     124local variables, a runtime computation is necessary to know the frame
     125size. Finally, a function's frame-size may change during execution as local
     126variables (static or dynamic sized) go in and out of scope.
     127Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
     128bumping the hardware stack-pointer up or down as needed.
     129
     130Unwinding across multiple stack frames is more complex because individual stack
     131management code associated with each frame is bypassed. That is, the location
     132of a function's frame-management code is largely unknown and dispersed
     133throughout the function, hence the current frame size managed by that code is
     134also unknown. Hence, code unwinding across frames does not have direct
     135knowledge about what is on the stack, and hence, how much of the stack needs to
     136be removed.
     137
     138% At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
     139% move the top of the stack, discarding everything on the stack above a certain
     140% point. However this ignores all the cleanup code that should be run when
     141% certain sections of the stack are removed (for \CFA these are from destructors
     142% and finally clauses) and also requires that the point to which the stack is
     143% being unwound is known ahead of time. libunwind is used to address both of
     144% these problems.
     145
     146The traditional unwinding mechanism for C is implemented by saving a snap-shot
     147of a function's state with @setjmp@ and restoring that snap-shot with
     148@longjmp@. This approach bypasses the need to know stack details by simply
     149reseting to a snap-shot of an arbitrary but existing function frame on the
     150stack. It is up to the programmer to ensure the snap-shot is valid when it is
     151reset, making this unwinding approach fragile with potential errors that are
     152difficult to debug because the stack becomes corrupted.
     153
     154However, many languages define cleanup actions that must be taken when objects
     155are deallocated from the stack or blocks end, such as running a variable's
     156destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
     157requires walking the stack and checking each stack frame for these potential
     158actions.
     159
     160For exceptions, it must be possible to walk the stack frames in search of @try@
     161statements to match and execute a handler. For termination exceptions, it must
     162also be possible to unwind all stack frames from the throw to the matching
     163catch, and each of these frames must be checked for cleanup actions. Stack
     164walking is where most of the complexity and expense of exception handling
     165appears.
     166
     167One of the most popular tools for stack management is libunwind, a low-level
     168library that provides tools for stack walking, handler execution, and
     169unwinding. What follows is an overview of all the relevant features of
     170libunwind needed for this work, and how \CFA uses them to implement exception
     171handling.
     172
     173\subsection{libunwind Usage}
     174Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
     175provides \CC-style stack-unwinding. Its operation is divided into two phases:
     176search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
     177stack and decide where unwinding should stop (but no unwinding occurs). The
     178cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
     179
     180To use libunwind, each function must have a personality function and a Language
     181Specific Data Area (LSDA).  The LSDA has the unique information for each
     182function to tell the personality function where a function is executing, its
     183current stack frame, and what handlers should be checked.  Theoretically, the
     184LSDA can contain any information but conventionally it is a table with entries
     185representing regions of the function and what has to be done there during
     186unwinding. These regions are bracketed by the instruction pointer. If the
     187instruction pointer is within a region's start/end, then execution is currently
     188executing in that region. Regions are used to mark out the scopes of objects
     189with destructors and try blocks.
     190
     191% Libunwind actually does very little, it simply moves down the stack from
     192% function to function. Most of the actions are implemented by the personality
     193% function which libunwind calls on every function. Since this is shared across
     194% many functions or even every function in a language it will need a bit more
     195% information.
     196
     197The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
     198attaches its personality function. \PAB{to what is it attached?}  However, this
     199flag only handles the cleanup attribute
     200\begin{cfa}
     201void clean_up( int * var ) { ... }
     202int avar __attribute__(( __cleanup(clean_up) ));
     203\end{cfa}
     204which is used on a variable and specifies a function, \eg @clean_up@, run when
     205the variable goes out of scope. The function is passed a pointer to the object
     206so it can be used to mimic destructors. However, this feature cannot be used to
     207mimic @try@ statements.
     208
     209\subsection{Personality Functions}
     210Personality functions have a complex interface specified by libunwind.  This
     211section covers some of the important parts of the interface.
     212
     213A personality function performs four tasks, although not all have to be
     214present.
     215\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
     216typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
     217        _Unwind_Action @action@,
     218        _Unwind_Exception_Class @exception_class@,
     219        _Unwind_Exception * @exception@,
     220        struct _Unwind_Context * @context@
     221);
    161222\end{lstlisting}
    162 
    163 The return value, the reason code, is an enumeration of possible messages
     223The @action@ argument is a bitmask of possible actions:
     224\begin{enumerate}
     225\item
     226@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
     227to check for handlers.  If there is a handler in a stack frame, as defined by
     228the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
     229it return @_URC_CONTINUE_UNWIND@.
     230
     231\item
     232@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
     233unwound and all cleanup code is run. The personality function does whatever
     234cleanup the language defines (such as running destructors/finalizers) and then
     235generally returns @_URC_CONTINUE_UNWIND@.
     236
     237\item
     238\begin{sloppypar}
     239@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
     240handler. The personality function must prepare to return to normal code
     241execution and return @_URC_INSTALL_CONTEXT@.
     242\end{sloppypar}
     243
     244\item
     245@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
     246the cleanup phase and uses a different means to decide when to stop
     247\see{\VRef{s:ForcedUnwind}}.
     248\end{enumerate}
     249
     250The @exception_class@ argument is a copy of the
     251\lstinline[language=C]|exception|'s @exception_class@ field.
     252
     253The \lstinline[language=C]|exception| argument is a pointer to the user
     254provided storage object. It has two public fields, the exception class, which
     255is actually just a number, identifying the exception handling mechanism that
     256created it, and the cleanup function. The cleanup function is called if
     257required by the exception.
     258
     259The @context@ argument is a pointer to an opaque type passed to helper
     260functions called inside the personality function.
     261
     262The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
    164263that can be passed several places in libunwind. It includes a number of
    165264messages for special cases (some of which should never be used by the
     
    167266personality function should always return @_URC_CONTINUE_UNWIND@.
    168267
    169 The @version@ argument is the verson of the implementation that is
    170 calling the personality function. At this point it appears to always be 1 and
    171 it will likely stay that way until a new version of the API is updated.
    172 
    173 The @action@ argument is set of flags that tell the personality
    174 function when it is being called and what it must do on this invocation.
    175 The flags are as follows:
    176 \begin{itemize}
    177 \item@_UA_SEARCH_PHASE@: This flag is set whenever the personality
    178 function is called during the search phase. The personality function should
    179 decide if unwinding will stop in this function or not. If it does then the
    180 personality function should return @_URC_HANDLER_FOUND@.
    181 \item@_UA_CLEANUP_PHASE@: This flag is set whenever the personality
    182 function is called during the cleanup phase. If no other flags are set this
    183 means the entire frame will be unwound and all cleanup code should be run.
    184 \item@_UA_HANDLER_FRAME@: This flag is set during the cleanup phase
    185 on the function frame that found the handler. The personality function must
    186 prepare to return to normal code execution and return
    187 @_URC_INSTALL_CONTEXT@.
    188 \item@_UA_FORCE_UNWIND@: This flag is set if the personality function
    189 is called through a forced unwind call. Forced unwind only performs the
    190 cleanup phase and uses a different means to decide when to stop. See its
    191 section below.
    192 \end{itemize}
    193 
    194 The @exception_class@ argument is a copy of the @exception@'s
    195 @exception_class@ field.
    196 
    197 The @exception@ argument is a pointer to the user provided storage
    198 object. It has two public fields, the exception class which is actually just
    199 a number that identifies the exception handling mechanism that created it and
    200 the other is the clean-up function. The clean-up function is called if the
    201 exception needs to
    202 
    203 The @context@ argument is a pointer to an opaque type. This is passed
    204 to the many helper functions that can be called inside the personality
    205 function.
    206 
    207268\subsection{Raise Exception}
    208 This could be considered the central function of libunwind. It preforms the
    209 two staged unwinding the library is built around and most of the rest of the
    210 interface of libunwind is here to support it. It's signature is as follows:
    211 
    212 \begin{lstlisting}
     269Raising an exception is the central function of libunwind and it performs a
     270two-staged unwinding.
     271\begin{cfa}
    213272_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
     273\end{cfa}
     274First, the function begins the search phase, calling the personality function
     275of the most recent stack frame. It continues to call personality functions
     276traversing the stack from newest to oldest until a function finds a handler or
     277the end of the stack is reached. In the latter case, raise exception returns
     278@_URC_END_OF_STACK@.
     279
     280Second, when a handler is matched, raise exception continues onto the cleanup phase.
     281Once again, it calls the personality functions of each stack frame from newest
     282to oldest. This pass stops at the stack frame containing the matching handler.
     283If that personality function has not install a handler, it is an error.
     284
     285If an error is encountered, raise exception returns either
     286@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
     287error occurred.
     288
     289\subsection{Forced Unwind}
     290\label{s:ForcedUnwind}
     291Forced Unwind is the other central function in libunwind.
     292\begin{cfa}
     293_Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
     294        _Unwind_Stop_Fn, void *);
     295\end{cfa}
     296It also unwinds the stack but it does not use the search phase. Instead another
     297function, the stop function, is used to stop searching.  The exception is the
     298same as the one passed to raise exception. The extra arguments are the stop
     299function and the stop parameter. The stop function has a similar interface as a
     300personality function, except it is also passed the stop parameter.
     301\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
     302typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
     303        _Unwind_Action @action@,
     304        _Unwind_Exception_Class @exception_class@,
     305        _Unwind_Exception * @exception@,
     306        struct _Unwind_Context * @context@,
     307        void * @stop_parameter@);
    214308\end{lstlisting}
    215309
    216 When called the function begins the search phase, calling the personality
    217 function of the most recent stack frame. It will continue to call personality
    218 functions traversing the stack new-to-old until a function finds a handler or
    219 the end of the stack is reached. In the latter case raise exception will
    220 return with @_URC_END_OF_STACK@.
    221 
    222 Once a handler has been found raise exception continues onto the the cleanup
    223 phase. Once again it will call the personality functins of each stack frame
    224 from newest to oldest. This pass will stop at the stack frame that found the
    225 handler last time, if that personality function does not install the handler
    226 it is an error.
    227 
    228 If an error is encountered raise exception will return either
    229 @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending
    230 on when the error occured.
    231 
    232 \subsection{Forced Unwind}
    233 This is the second big function in libunwind. It also unwinds a stack but it
    234 does not use the search phase. Instead another function, the stop function,
    235 is used to decide when to stop.
    236 
    237 \begin{lstlisting}
    238 _Unwind_Reason_Code _Unwind_ForcedUnwind(
    239     _Unwind_Exception *, _Unwind_Stop_Fn, void *);
    240 \end{lstlisting}
    241 
    242 The exception is the same as the one passed to raise exception. The extra
    243 arguments are the stop function and the stop parameter. The stop function has
    244 a similar interface as a personality function, except it is also passed the
    245 stop parameter.
    246 
    247 \begin{lstlisting}
    248 typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(
    249     int version,
    250     _Unwind_Action action,
    251     _Unwind_Exception_Class exception_class,
    252     _Unwind_Exception * exception,
    253     struct _Unwind_Context * context,
    254     void * stop_parameter);
    255 \end{lstlisting}
    256 
    257310The stop function is called at every stack frame before the personality
    258 function is called and then once more once after all frames of the stack have
    259 been unwound.
    260 
    261 Each time it is called the stop function should return @_URC_NO_REASON@
    262 or transfer control directly to other code outside of libunwind. The
    263 framework does not provide any assistance here.
    264 
    265 Its arguments are the same as the paired personality function.
    266 The actions @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always
    267 set when it is called. By the official standard that is all but both GCC and
    268 Clang add an extra action on the last call at the end of the stack:
    269 @_UA_END_OF_STACK@.
     311function is called and then once more after all frames of the stack are
     312unwound.
     313
     314Each time it is called, the stop function should return @_URC_NO_REASON@ or
     315transfer control directly to other code outside of libunwind. The framework
     316does not provide any assistance here.
     317
     318\begin{sloppypar}
     319Its arguments are the same as the paired personality function.  The actions
     320@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
     321called. Beyond the libunwind standard, both GCC and Clang add an extra action
     322on the last call at the end of the stack: @_UA_END_OF_STACK@.
     323\end{sloppypar}
    270324
    271325\section{Exception Context}
    272326% Should I have another independent section?
    273327% There are only two things in it, top_resume and current_exception. How it is
    274 % stored changes depending on wheither or not the thread-library is linked.
    275 
    276 The exception context is a piece of global storage used to maintain data
    277 across different exception operations and to communicate between different
    278 components.
    279 
    280 Each stack has its own exception context. In a purely sequental program, using
    281 only core Cforall, there is only one stack and the context is global. However
    282 if the library @libcfathread@ is linked then there can be multiple
    283 stacks so they will each need their own.
    284 
    285 To handle this code always gets the exception context from the function
    286 @this_exception_context@. The main exception handling code is in
    287 @libcfa@ and that library also defines the function as a weak symbol
    288 so it acts as a default. Meanwhile in @libcfathread@ the function is
    289 defined as a strong symbol that replaces it when the libraries are linked
    290 together.
    291 
    292 The version of the function defined in @libcfa@ is very simple. It
    293 returns a pointer to a global static variable. With only one stack this
    294 global instance is associated with the only stack.
    295 
    296 The version of the function defined in @libcfathread@ has to handle
    297 more as there are multiple stacks. The exception context is included as
    298 part of the per-stack data stored as part of coroutines. In the cold data
    299 section, stored at the base of each stack, is the exception context for that
    300 stack. The @this_exception_context@ uses the concurrency library to get
    301 the current coroutine and through it the cold data section and the exception
    302 context.
     328% stored changes depending on whether or not the thread-library is linked.
     329
     330The exception context is global storage used to maintain data across different
     331exception operations and to communicate among different components.
     332
     333Each stack must have its own exception context. In a sequential \CFA program,
     334there is only one stack with a single global exception-context. However, when
     335the library @libcfathread@ is linked, there are multiple stacks where each
     336needs its own exception context.
     337
     338General access to the exception context is provided by function
     339@this_exception_context@. For sequential execution, this function is defined as
     340a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
     341concurrent, it links with @libcfathread@, where this function is defined with a
     342strong symbol replacing the sequential version.
     343
     344% The version of the function defined in @libcfa@ is very simple. It returns a
     345% pointer to a global static variable. With only one stack this global instance
     346% is associated with the only stack.
     347
     348For coroutines, @this_exception_context@ accesses the exception context stored
     349at the base of the stack. For threads, @this_exception_context@ uses the
     350concurrency library to access the current stack of the thread or coroutine
     351being executed by the thread, and then accesses the exception context stored at
     352the base of this stack.
    303353
    304354\section{Termination}
     
    306356% catches. Talk about GCC nested functions.
    307357
    308 Termination exceptions use libunwind quite heavily because it matches the
    309 intended use from \CPP exceptions very closely. The main complication is that
    310 since the \CFA compiler works by translating to C code it cannot generate the
    311 assembly to form the LSDA for try blocks or destructors.
     358Termination exceptions use libunwind heavily because it matches the intended
     359use from \CC exceptions closely. The main complication for \CFA is that the
     360compiler generates C code, making it very difficult to generate the assembly to
     361form the LSDA for try blocks or destructors.
    312362
    313363\subsection{Memory Management}
    314 The first step of termination is to copy the exception into memory managed by
    315 the exception system. Currently the system just uses malloc, without reserved
    316 memory or and ``small allocation" optimizations. The exception handling
    317 mechanism manages memory for the exception as well as memory for libunwind
    318 and the system's own per-exception storage.
    319 
    320 Exceptions are stored in variable sized block. The first component is a fixed
    321 sized data structure that contains the information for libunwind and the
    322 exception system. The second component is a blob of memory that is big enough
    323 to store the exception. Macros with pointer arthritic and type cast are
    324 used to move between the components or go from the embedded
     364The first step of a termination raise is to copy the exception into memory
     365managed by the exception system. Currently, the system uses @malloc@, rather
     366than reserved memory or the stack top. The exception handling mechanism manages
     367memory for the exception as well as memory for libunwind and the system's own
     368per-exception storage.
     369
     370Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout
     371figure.} The first component is a fixed sized data structure that contains the
     372information for libunwind and the exception system. The second component is an
     373area of memory big enough to store the exception. Macros with pointer arthritic
     374and type cast are used to move between the components or go from the embedded
    325375@_Unwind_Exception@ to the entire node.
    326376
    327 All of these nodes are strung together in a linked list. One linked list per
    328 stack, with the head stored in the exception context. Within each linked list
    329 the most recently thrown exception is at the head and the older exceptions
    330 are further down the list. This list format allows exceptions to be thrown
    331 while a different exception is being handled. Only the exception at the head
    332 of the list is currently being handled, the other will wait for the
    333 exceptions before them to be removed.
    334 
    335 The virtual members in the exception's virtual table. The size of the
    336 exception, the copy function and the free function are all in the virtual
    337 table so they are decided per-exception type. The size and copy function are
    338 used right away when the exception is copied in to managed memory. After the
    339 exception is handled the free function is used to clean up the exception and
    340 then the entire node is passed to free.
    341 
    342 \subsection{Try Statements \& Catch Clauses}
    343 The try statements with termination handlers have a pretty complex conversion
    344 to compensate for the lack of assembly generation. Libunwind requires an LSDA
    345 (Language Specific Data Area) and personality function for a function to
    346 unwind across it. The LSDA in particular is hard to generate at the level of
    347 C which is what the \CFA compiler outputs so a work-around is used.
    348 
    349 This work around is a function called @__cfaehm_try_terminate@ in the
    350 standard library. The contents of a try block and the termination handlers
    351 are converted into functions. These are then passed to the try terminate
    352 function and it calls them. This puts the try statements in their own
    353 functions so that no function has to deal with both termination handlers and
    354 destructors.
    355 
    356 This function has some custom embedded assembly that defines its personality
    357 function and LSDA. This is hand coded in C which is why there is only one
    358 version of it, the compiler has no capability to generate it. The personality
    359 function is structured so that it may be expanded, but really it only handles
    360 this one function. Notably it does not handle any destructors so the function
    361 is constructed so that it does need to run it.
     377All of these nodes are linked together in a list, one list per stack, with the
     378list head stored in the exception context. Within each linked list, the most
     379recently thrown exception is at the head followed by older thrown
     380exceptions. This format allows exceptions to be thrown, while a different
     381exception is being handled. The exception at the head of the list is currently
     382being handled, while other exceptions wait for the exceptions before them to be
     383removed.
     384
     385The virtual members in the exception's virtual table provide the size of the
     386exception, the copy function, and the free function, so they are specific to an
     387exception type. The size and copy function are used immediately to copy an
     388exception into managed memory. After the exception is handled the free function
     389is used to clean up the exception and then the entire node is passed to free.
     390
     391\subsection{Try Statements and Catch Clauses}
     392The try statement with termination handlers is complex because it must
     393compensate for the lack of assembly-code generated from \CFA. Libunwind
     394requires an LSDA and personality function for control to unwind across a
     395function. The LSDA in particular is hard to mimic in generated C code.
     396
     397The workaround is a function called @__cfaehm_try_terminate@ in the standard
     398library. The contents of a try block and the termination handlers are converted
     399into functions. These are then passed to the try terminate function and it
     400calls them. This approach puts a try statement in its own functions so that no
     401function has to deal with both termination handlers and destructors. \PAB{I do
     402not understand the previous sentence.}
     403
     404This function has some custom embedded assembly that defines \emph{its}
     405personality function and LSDA. The assembly is created with handcrafted C @asm@
     406statements, which is why there is only one version of it. The personality
     407function is structured so that it can be expanded, but currently it only
     408handles this one function.  Notably, it does not handle any destructors so the
     409function is constructed so that it does need to run it. \PAB{I do not
     410understand the previous sentence.}
    362411
    363412The three functions passed to try terminate are:
    364 \begin{itemize}
    365 \item The try function: This function is the try block, all the code inside
    366 the try block is placed inside the try function. It takes no parameters and
    367 has no return value. This function is called during regular execution to run
    368 the try block.
    369 \item The match function: This function decides if this try statement should
    370 handle any given termination exception. It takes a pointer to the exception
    371 and returns 0 if the exception is not handled here. Otherwise the return value
    372 is the id of the handler that should handle the exception. It is called
    373 during the search phase.
    374 It is constructed from the conditional part of each handler. It runs each
    375 check in turn, first checking to see if the object
    376 \item The catch function: This function handles the exception. It takes a
    377 pointer to the exception and the handler's id and returns nothing. It is
    378 called after the clean-up phase.
    379 It is constructed by stitching together the bodies of each handler
    380 \end{itemize}
    381 All three are created with GCC nested functions. GCC nested functions can be
    382 used to create closures, functions that can refer to the state of other
    383 functions on the stack. This allows the functions to refer to the main
    384 function and all the variables in scope.
    385 
    386 These nested functions and all other functions besides
    387 @__cfaehm_try_terminate@ in \CFA use the GCC personality function and
    388 the @-fexceptions@ flag to generate the LSDA. This allows destructors
    389 to be implemented with the cleanup attribute.
     413\begin{description}
     414\item[try function:] This function is the try block, all the code inside the
     415try block is placed inside the try function. It takes no parameters and has no
     416return value. This function is called during regular execution to run the try
     417block.
     418
     419\item[match function:] This function is called during the search phase and
     420decides if a catch clause matches the termination exception.  It is constructed
     421from the conditional part of each handler and runs each check, top to bottom,
     422in turn, first checking to see if the exception type matches and then if the
     423condition is true. It takes a pointer to the exception and returns 0 if the
     424exception is not handled here. Otherwise the return value is the id of the
     425handler that matches the exception.
     426
     427\item[handler function:] This function handles the exception. It takes a
     428pointer to the exception and the handler's id and returns nothing. It is called
     429after the cleanup phase.  It is constructed by stitching together the bodies of
     430each handler and dispatches to the selected handler.
     431\end{description}
     432All three functions are created with GCC nested functions. GCC nested functions
     433can be used to create closures, functions that can refer to the state of other
     434functions on the stack. This approach allows the functions to refer to all the
     435variables in scope for the function containing the @try@ statement.  These
     436nested functions and all other functions besides @__cfaehm_try_terminate@ in
     437\CFA use the GCC personality function and the @-fexceptions@ flag to generate
     438the LSDA. This allows destructors to be implemented with the cleanup attribute.
    390439
    391440\section{Resumption}
    392441% The stack-local data, the linked list of nodes.
    393442
    394 Resumption uses a list of nodes for its stack traversal. The head of the list
    395 is stored in the exception context. The nodes in the list just have a pointer
     443Resumption simple to implement because there is no stack unwinding. The
     444resumption raise uses a list of nodes for its stack traversal. The head of the
     445list is stored in the exception context. The nodes in the list have a pointer
    396446to the next node and a pointer to the handler function.
    397447
    398 The on a resumption throw the this list is traversed. At each node the
    399 handler function is called and is passed the exception by pointer. It returns
    400 true if the exception was handled and false otherwise.
    401 
    402 The handler function does both the matching and catching. It tries each
    403 the condition of @catchResume@ in order, top-to-bottom and until it
    404 finds a handler that matches. If no handler matches then the function returns
    405 false. Otherwise the matching handler is run, if it completes successfully
    406 the function returns true. Rethrows, through the @throwResume;@
    407 statement, cause the function to return true.
     448A resumption raise traverses this list. At each node the handler function is
     449called, passing the exception by pointer. It returns true if the exception is
     450handled and false otherwise.
     451
     452The handler function does both the matching and handling. It computes the
     453condition of each @catchResume@ in top-to-bottom order, until it finds a
     454handler that matches. If no handler matches then the function returns
     455false. Otherwise the matching handler is run; if it completes successfully, the
     456function returns true. Reresume, through the @throwResume;@ statement, cause
     457the function to return true.
    408458
    409459% Recursive Resumption Stuff:
    410 Blocking out part of the stack is accomplished by updating the front of the
    411 list as the search continues. Before the handler at a node is called the head
    412 of the list is updated to the next node of the current node. After the search
    413 is complete, successful or not, the head of the list is reset.
    414 
    415 This means the current handler and every handler that has already been
    416 checked are not on the list while a handler is run. If a resumption is thrown
    417 during the handling of another resumption the active handlers and all the
    418 other handler checked up to this point will not be checked again.
     460Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
     461already examined, is accomplished by updating the front of the list as the
     462search continues. Before the handler at a node is called the head of the list
     463is updated to the next node of the current node. After the search is complete,
     464successful or not, the head of the list is reset.
     465
     466This mechanism means the current handler and every handler that has already
     467been checked are not on the list while a handler is run. If a resumption is
     468thrown during the handling of another resumption the active handlers and all
     469the other handler checked up to this point are not checked again.
    419470
    420471This structure also supports new handler added while the resumption is being
    421472handled. These are added to the front of the list, pointing back along the
    422 stack -- the first one will point over all the checked handlers -- and the
    423 ordering is maintained.
    424 
    425 \subsection{Libunwind Compatibility}
    426 Resumption does not use libunwind for two simple reasons. The first is that
    427 it does not have to unwind anything so would never need to use the clean-up
    428 phase. Still the search phase could be used to make it free to enter or exit
    429 a try statement with resumption handlers in the same way termination handlers
    430 are for the same trade off in the cost of the throw. This is where the second
    431 reason comes in, there is no way to return from a search without installing
    432 a handler or raising an error.
    433 
    434 Although work arounds could be created none seemed to be worth it for the
    435 prototype. This implementation has no difference in behaviour and is much
    436 simpler.
     473stack -- the first one points over all the checked handlers -- and the ordering
     474is maintained.
     475
     476\label{p:zero-cost}
     477Note, the resumption implementation has a cost for entering/exiting a @try@
     478statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
     479clauses has zero-cost entry/exit. While resumption does not need the stack
     480unwinding and cleanup provided by libunwind, it could use the search phase to
     481providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
     482to return from a libunwind search without installing a handler or raising an
     483error.  Although workarounds might be possible, they are beyond the scope of
     484this thesis. The current resumption implementation has simplicity in its
     485favour.
    437486% Seriously, just compare the size of the two chapters and then consider
    438487% that unwind is required knowledge for that chapter.
     
    440489\section{Finally}
    441490% Uses destructors and GCC nested functions.
    442 Finally clauses are a simple decomposition to some of the existing features.
    443 The code in the block is placed into a GCC nested function with a unique name,
    444 no arguments or return values. This nested function is then set as the
    445 clean-up function of an empty object that is declared at the beginning of a
    446 block placed around the contexts of the try statement.
     491Finally clauses is placed into a GCC nested-function with a unique name, and no
     492arguments or return values. This nested function is then set as the cleanup
     493function of an empty object that is declared at the beginning of a block placed
     494around the context of the associated @try@ statement.
    447495
    448496The rest is handled by GCC. The try block and all handlers are inside the
    449 block. When they are complete control exits the block and the empty object
    450 is cleaned up, which runs the function that contains the finally code.
     497block. At completion, control exits the block and the empty object is cleaned
     498up, which runs the function that contains the finally code.
    451499
    452500\section{Cancellation}
     
    454502
    455503Cancellation also uses libunwind to do its stack traversal and unwinding,
    456 however it uses a different primary function @_Unwind_ForcedUnwind@.
    457 Details of its interface can be found in the unwind section.
    458 
    459 The first step of cancellation is to find the stack was cancelled and which
    460 type of stack it is. Luckily the threads library stores the main thread
    461 pointer and the current thread pointer and every thread stores a pointer to
     504however it uses a different primary function @_Unwind_ForcedUnwind@.  Details
     505of its interface can be found in the \VRef{s:ForcedUnwind}.
     506
     507The first step of cancellation is to find the cancelled stack and its type:
     508coroutine or thread. Fortunately, the thread library stores the main thread
     509pointer and the current thread pointer, and every thread stores a pointer to
    462510its main coroutine and the coroutine it is currently executing.
    463511
    464 So if the the current thread's main and current coroutine do not match, it is
    465 a coroutine cancellation. Otherwise if the main and current thread do not
    466 match, it is a thread cancellation. Otherwise it is a main thread
    467 cancellation.
    468 
    469 However if the threading library is not linked then execution must be on the
    470 main stack as that is the only one that exists. So the entire check is skipped
    471 using the linker and weak symbols. Instead the main thread cancellation is
    472 unconditionally preformed.
    473 
    474 Regardless of how they are choosen afterwords the stop function and the stop
    475 parameter are passed to the forced unwind functon. The general pattern of all
    476 three stop functions is the same, they continue unwinding until the end of
    477 stack when they do there primary work.
    478 
    479 Main stack cancellation it is very simple. The ``transfer" is just an abort,
    480 the program stops executing.
    481 
    482 The coroutine cancellation stores the exception on the coroutine and then
    483 does a coroutine context switch. The rest is handled inside resume. Every time
    484 control returns from a resumed thread there is a check to see if it is
    485 cancelled. If it is the exception is retrieved and the CoroutineCancelled
    486 exception is constructed and loaded. It is then thrown as a regular exception
    487 with the default handler coming from the context of the resumption call.
    488 
    489 The thread cancellation stores the exception on the thread's main stack and
    490 then returns to the scheduler. The rest is handled by the joiner. The wait
    491 for the joined thread to finish works the same but after that it checks
    492 to see if there was a cancellation. If there was the exception is retrieved
    493 and the ThreadCancelled exception is constructed. The default handler is
    494 passed in as a function pointer. If it is null (as it is for the
    495 auto-generated joins on destructor call) it a default is used that simply
    496 calls abort; which gives the required handling on implicate join.
     512The first check is if the current thread's main and current coroutine do not
     513match, implying a coroutine cancellation; otherwise, it is a thread
     514cancellation. Otherwise it is a main thread cancellation. \PAB{Previous
     515sentence does not make sense.}
     516
     517However, if the threading library is not linked, the sequential execution is on
     518the main stack. Hence, the entire check is skipped because the weak-symbol
     519function is loaded. Therefore, a main thread cancellation is unconditionally
     520performed.
     521
     522Regardless of how the stack is chosen, the stop function and parameter are
     523passed to the forced-unwind function. The general pattern of all three stop
     524functions is the same: they continue unwinding until the end of stack when they
     525do there primary work.
     526
     527For main stack cancellation, the transfer is just a program abort.
     528
     529For coroutine cancellation, the exception is stored on the coroutine's stack,
     530and the coroutine context switches to its last resumer. The rest is handled on
     531the backside of the resume, which check if the resumed coroutine is
     532cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
     533and a @CoroutineCancelled@ exception is constructed and loaded with the
     534cancelled exception. It is then resumed as a regular exception with the default
     535handler coming from the context of the resumption call.
     536
     537For thread cancellation, the exception is stored on the thread's main stack and
     538then context switched to the scheduler. The rest is handled by the thread
     539joiner. When the join is complete, the joiner checks if the joined thread is
     540cancelled. If cancelled, the exception is retrieved and the joined thread, and
     541a @ThreadCancelled@ exception is constructed and loaded with the cancelled
     542exception. The default handler is passed in as a function pointer. If it is
     543null (as it is for the auto-generated joins on destructor call), the default is
     544used, which is a program abort.
     545%; which gives the required handling on implicate join.
  • doc/theses/andrew_beach_MMath/unwinding.tex

    rcd70477 rf99f5ba  
    1 \chapter{Unwinding in \CFA}
     1\chapter{\texorpdfstring{Unwinding in \CFA}{Unwinding in Cforall}}
    22
    3 Stack unwinding is the process of removing things from the stack. Within
    4 functions and on function return this is handled directly by the code in the
    5 function itself as it knows exactly what is on the stack just from the
    6 current location in the function. Unwinding across stack frames means that it
    7 is no longer knows exactly what is on the stack or even how much of the stack
    8 needs to be removed.
     3Stack unwinding is the process of removing stack frames (activations) from the
     4stack. On function entry and return, unwinding is handled directly by the code
     5embedded in the function. Usually, the stack-frame size is known statically
     6based on parameters and local variable declarations.  For dynamically-sized
     7local variables, a runtime computation is necessary to know the frame
     8size. Finally, a function's frame-size may change during execution as local
     9variables (static or dynamic sized) go in and out of scope.
     10Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
     11bumping the hardware stack-pointer up or down as needed.
    912
    10 Even this is fairly simple if nothing needs to happen when the stack unwinds.
    11 Traditional C can unwind the stack by saving and restoring state (with
    12 @setjmp@ \& @longjmp@). However many languages define actions that
    13 have to be taken when something is removed from the stack, such as running
    14 a variable's destructor or a @try@ statement's @finally@
    15 clause. Handling this requires walking the stack going through each stack
    16 frame.
     13Unwinding across multiple stack frames is more complex because individual stack
     14management code associated with each frame is bypassed. That is, the location
     15of a function's frame code is largely unknown and dispersed throughout the
     16function, hence the current stack-frame size managed by that code is also
     17unknown. Hence, code unwinding across frames does not have direct knowledge
     18about what is on the stack, and hence, how much of the stack needs to be
     19removed.
    1720
    18 For exceptions, this means everything from the point the exception is raised
    19 to the point it is caught, while checking each frame for handlers during the
    20 stack walk to find out where it should be caught. This is where the most of
    21 the expense and complexity of exception handling comes from.
     21The traditional unwinding mechanism for C is implemented by saving a snap-shot
     22of a function's state with @setjmp@ and restoring that snap-shot with
     23@longjmp@. This approach bypasses the need to know stack details by simply
     24reseting to a snap-shot of an arbitrary but existing function frame on the
     25stack. It is up to the programmer to ensure the snap-shot is valid when it is
     26reset, making the code fragile with potential errors that are difficult to
     27debug because the stack becomes corrupted.
    2228
    23 To do all of this we use libunwind, a low level library that provides tools
    24 for stack walking and stack unwinding. What follows is an overview of all the
    25 relivant features of libunwind and then how \CFA uses them to implement its
    26 exception handling.
     29However, many languages define cleanup actions that have to be taken when
     30something is deallocated from the stack or blocks end, such as running a
     31variable's destructor or a @try@ statement's @finally@ clause. Handling these
     32mechanisms requires walking the stack and checking each stack frame for these
     33potential actions.
     34
     35For exceptions, it must be possible to walk the stack frames in search of try
     36statements with handlers to perform exception matching. For termination
     37exceptions, it must be possible to unwind all stack frames from the throw to
     38the matching catch, and each of these frames must be checked for cleanup
     39actions. Stack walking is where the most of the complexity and expense of
     40exception handling comes from.
     41
     42One of the most popular tools for stack management is libunwind, a low level
     43library that provides tools for stack walking and unwinding. What follows is an
     44overview of all the relevant features of libunwind and how \CFA uses them to
     45implement its exception handling.
    2746
    2847\section{libunwind Usage}
    29 
    30 \CFA uses two primary functions in libunwind to create most of its
    31 exceptional control-flow: @_Unwind_RaiseException@ and
    32 @_Unwind_ForcedUnwind@.
    33 Their operation is divided into two phases: search and clean-up. The search
    34 phase -- phase 1 -- is used to scan the stack but not unwinding it. The
    35 clean-up phase -- phase 2 -- is used for unwinding.
     48\CFA uses two primary functions in libunwind to create most of its exceptional
     49control-flow: @_Unwind_RaiseException@ and @_Unwind_ForcedUnwind@.  Their
     50operation is divided into two phases: search and clean-up. The search phase --
     51phase 1 -- is used to scan the stack but not unwinding it. The clean-up phase
     52-- phase 2 -- is used for unwinding.
    3653
    3754The raise-exception function uses both phases. It starts by searching for a
     
    4461A personality function performs three tasks, although not all have to be
    4562present. The tasks performed are decided by the actions provided.
    46 @_Unwind_Action@ is a bitmask of possible actions and an argument of
    47 this type is passed into the personality function.
     63@_Unwind_Action@ is a bitmask of possible actions and an argument of this type
     64is passed into the personality function.
    4865\begin{itemize}
    49 \item@_UA_SEARCH_PHASE@ is passed in search phase and tells the
    50 personality function to check for handlers. If there is a handler in this
    51 stack frame, as defined by the language, the personality function should
    52 return @_URC_HANDLER_FOUND@. Otherwise it should return
    53 @_URC_CONTINUE_UNWIND@.
    54 \item@_UA_CLEANUP_PHASE@ is passed in during the clean-up phase and
    55 means part or all of the stack frame is removed. The personality function
    56 should do whatever clean-up the language defines
    57 (such as running destructors/finalizers) and then generally returns
    58 @_URC_CONTINUE_UNWIND@.
    59 \item@_UA_HANDLER_FRAME@ means the personality function must install
    60 a handler. It is also passed in during the clean-up phase and is in addition
    61 to the clean-up action. libunwind provides several helpers for the personality
    62 function here. Once it is done, the personality function must return
    63 @_URC_INSTALL_CONTEXT@.
     66\item
     67\begin{sloppypar}
     68@_UA_SEARCH_PHASE@ is passed in for the search phase and tells the personality
     69function to check for handlers. If there is a handler in a stack frame, as
     70defined by the language, the personality function returns @_URC_HANDLER_FOUND@;
     71otherwise it return @_URC_CONTINUE_UNWIND@.
     72\end{sloppypar}
     73\item
     74@_UA_CLEANUP_PHASE@ is passed in during the clean-up phase and means part or
     75all of the stack frame is removed. The personality function does whatever
     76clean-up the language defines (such as running destructors/finalizers) and then
     77generally returns @_URC_CONTINUE_UNWIND@.
     78\item
     79@_UA_HANDLER_FRAME@ means the personality function must install a handler. It
     80is also passed in during the clean-up phase and is in addition to the clean-up
     81action. libunwind provides several helpers for the personality function. Once
     82it is done, the personality function returns @_URC_INSTALL_CONTEXT@.
    6483\end{itemize}
    65 The personality function is given a number of other arguments. Some are for
    66 compatability and there is the @struct _Unwind_Context@ pointer which
    67 passed to many helpers to get information about the current stack frame.
     84The personality function is given a number of other arguments. Some arguments
     85are for compatibility, and there is the @struct _Unwind_Context@ pointer which
     86is passed to many helpers to get information about the current stack frame.
    6887
    69 Forced-unwind only performs the clean-up phase. It takes three arguments:
    70 a pointer to the exception, a pointer to the stop function and a pointer to
    71 the stop parameter. It does most of the same things as phase two of
    72 raise-exception but with some extras.
    73 The first it passes in an extra action to the personality function on each
    74 stack frame, @_UA_FORCE_UNWIND@, which means a handler cannot be
     88For cancellation, forced-unwind only performs the clean-up phase. It takes
     89three arguments: a pointer to the exception, a pointer to the stop function and
     90a pointer to the stop parameter. It does most of the same actions as phase two
     91of raise-exception but passes in an extra action to the personality function on
     92each stack frame, @_UA_FORCE_UNWIND@, which means a handler cannot be
    7593installed.
    7694
    77 The big change is that forced-unwind calls the stop function. Each time it
    78 steps into a frame, before calling the personality function, it calls the
    79 stop function. The stop function receives all the same arguments as the
    80 personality function will and the stop parameter supplied to forced-unwind.
     95As well, forced-unwind calls the stop function each time it steps into a frame,
     96before calling the personality function. The stop function receives all the
     97same arguments as the personality function and the stop parameter supplied to
     98forced-unwind.
    8199
    82100The stop function is called one more time at the end of the stack after all
    83 stack frames have been removed. By the standard API this is marked by setting
     101stack frames have been removed. The standard API marks this frame by setting
    84102the stack pointer inside the context passed to the stop function. However both
    85103GCC and Clang add an extra action for this case @_UA_END_OF_STACK@.
    86104
    87 Each time function the stop function is called it can do one or two things.
    88 When it is not the end of the stack it can return @_URC_NO_REASON@ to
    89 continue unwinding.
     105Each time the stop function is called, it can do one or two things.  When it is
     106not the end of the stack it can return @_URC_NO_REASON@ to continue unwinding.
    90107% Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND?
    91 Its only other option is to use its own means to transfer control elsewhere
    92 and never return to its caller. It may always do this and no additional tools
    93 are provided to do it.
     108The other option is to use some other means to transfer control elsewhere and
     109never return to its caller. libunwind provides no additional tools for
     110alternate transfers of control.
    94111
    95 \section{\CFA Implementation}
     112\section{\texorpdfstring{\CFA Implementation}{Cforall Implementation}}
    96113
    97 To use libunwind, \CFA provides several wrappers, its own storage,
    98 personality functions, and a stop function.
     114To use libunwind, \CFA provides several wrappers, its own storage, personality
     115functions, and a stop function.
    99116
    100117The wrappers perform three tasks: set-up, clean-up and controlling the
     
    108125The core control code is called every time a throw -- after set-up -- or
    109126re-throw is run. It uses raise-exception to search for a handler and to run it
    110 if one is found. If no handler is found and raise-exception returns then
     127if one is found. If no handler is found and raise-exception returns, then
    111128forced-unwind is called to run all destructors on the stack before terminating
    112129the process.
    113130
    114 The stop function is very simple. It checks the end of stack flag to see if
    115 it is finished unwinding. If so, it calls @exit@ to end the process,
    116 otherwise it returns with no-reason to continue unwinding.
     131The stop function is simple. It checks for the end of stack flag to see if
     132unwinding is finished. If so, it calls @exit@ to end the process, otherwise it
     133returns with no-reason to continue unwinding.
    117134% Yeah, this is going to have to change.
    118135
    119136The personality routine is more complex because it has to obtain information
    120 about the function by scanning the LSDA (Language Specific Data Area). This
     137about the function by scanning the Language Specific Data Area (LSDA). This
    121138step allows a single personality function to be used for multiple functions and
    122 let that personaliity function figure out exactly where in the function
    123 execution was, what is currently in the stack frame and what handlers should
    124 be checked.
     139lets that personality function figure out exactly where in the function
     140execution is, what is currently in the stack frame, and what handlers should be
     141checked.
    125142% Not that we do that yet.
    126143
    127 However, generating the LSDA is difficult. It requires knowledge about the
    128 location of the instruction pointer and stack layout, which varies with
    129 compiler and optimization levels. So for frames where there are only
    130 destructors, GCC's attribute cleanup with the @-fexception@ flag is
    131 sufficient to handle unwinding.
     144It is also necessary to generate the LSDA, which is difficult. It requires
     145knowledge about the location of the instruction pointer and stack layout, which
     146varies with compiler and optimization levels. Fortunately, for frames where
     147there are only destructors, GCC's attribute cleanup with the @-fexception@ flag
     148is sufficient to handle unwinding.
    132149
    133 The only functions that require more than that are those that contain
    134 @try@ statements. A @try@ statement has a @try@
    135 clause, some number of @catch@ clauses and @catchResume@
    136 clauses and may have a @finally@ clause. Of these only @try@
    137 statements with @catch@ clauses need to be transformed and only they
    138 and the @try@ clause are involved.
     150The only functions that require more information are those containing @try@
     151statements. Specifically, only @try@ statements with @catch@ clauses need to be
     152transformed.  The @try@ statement is converted into a series of closures that
     153can access other parts of the function according to scoping rules but can be
     154passed around. The @catch@ clauses are converted into two functions: the match
     155function and the handler function.
    139156
    140 The @try@ statement is converted into a series of closures which can
    141 access other parts of the function according to scoping rules but can be
    142 passed around. The @try@ clause is converted into the try functions,
    143 almost entirely unchanged. The @catch@ clauses are converted into two
    144 functions; the match function and the catch function.
     157Together the match function and the catch function form the code that runs when
     158an exception passes out of the guarded block for a try statement. The match
     159function is used during the search phase: it is passed an exception and checks
     160each handler to see if the raised exception matches the handler exception. It
     161returns an index that represents which handler matched or there is no
     162match. The catch function is used during the clean-up phase, it is passed an
     163exception and the index of a handler. It casts the exception to the exception
     164type declared in that handler and then runs the handler's body.
    145165
    146 Together the match function and the catch function form the code that runs
    147 when an exception passes out of a try block. The match function is used during
    148 the search phase, it is passed an exception and checks each handler to see if
    149 it will handle the exception. It returns an index that repersents which
    150 handler matched or that none of them did. The catch function is used during
    151 the clean-up phase, it is passed an exception and the index of a handler. It
    152 casts the exception to the exception type declared in that handler and then
    153 runs the handler's body.
    154 
    155 These three functions are passed to @try_terminate@. This is an
     166These three functions are passed to @try_terminate@, which is an
    156167% Maybe I shouldn't quote that, it isn't its actual name.
    157 internal hand-written function that has its own personality function and
    158 custom assembly LSD does the exception handling in \CFA. During normal
    159 execution all this function does is call the try function and then return.
    160 It is only when exceptions are thrown that anything interesting happens.
     168internal hand-written function that has its own personality function and custom
     169assembly LSDA for doing the exception handling in \CFA. During normal
     170execution, this function calls the try function and then return.  It is only
     171when exceptions are thrown that anything interesting happens.
    161172
    162173During the search phase the personality function gets the pointer to the match
    163 function and calls it. If the match function returns a handler index the
     174function and calls it. If the match function returns a handler index, the
    164175personality function saves it and reports that the handler has been found,
    165 otherwise unwinding continues.
    166 During the clean-up phase the personality function only does anything if the
    167 handler was found in this frame. If it was then the personality function
    168 installs the handler, which is setting the instruction pointer in
    169 @try_terminate@ to an otherwise unused section that calls the catch
    170 function, passing it the current exception and handler index.
    171 @try_terminate@ returns as soon as the catch function returns.
     176otherwise unwinding continues.  During the clean-up phase, the personality
     177function only performs an action, when a handler is found in a frame. For each
     178found frame, the personality function installs the handler, which sets the
     179instruction pointer in @try_terminate@ to an otherwise unused section that
     180calls the catch function, passing it the current exception and handler index.
     181@try_terminate@ returns as soon as the catch function returns.  At this point
     182control has returned to normal control flow.
    172183
    173 At this point control has returned to normal control flow.
     184\PAB{Maybe a diagram would be helpful?}
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rcd70477 rf99f5ba  
    9191\hypersetup{
    9292    plainpages=false,       % needed if Roman numbers in frontpages
    93     unicode=false,          % non-Latin characters in Acrobats bookmarks
    94     pdftoolbar=true,        % show Acrobats toolbar?
    95     pdfmenubar=true,        % show Acrobats menu?
     93    unicode=false,          % non-Latin characters in Acrobat's bookmarks
     94    pdftoolbar=true,        % show Acrobat's toolbar?
     95    pdfmenubar=true,        % show Acrobat's menu?
    9696    pdffitwindow=false,     % window fit to page when opened
    9797    pdfstartview={FitH},    % fits the width of the page to the window
     
    163163\input{common}
    164164\CFAStyle                                               % CFA code-style for all languages
    165 \lstset{basicstyle=\linespread{0.9}\tt}
     165\lstset{language=CFA,basicstyle=\linespread{0.9}\tt}    % CFA default lnaguage
     166\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
    166167
    167168%======================================================================
     
    188189\input{existing}
    189190\input{features}
    190 \input{unwinding}
     191\input{implement}
     192%\input{unwinding}
    191193\input{future}
    192194
  • libcfa/src/Makefile.am

    rcd70477 rf99f5ba  
    7676        stdlib.hfa \
    7777        time.hfa \
     78        bits/weakso_locks.hfa \
    7879        containers/maybe.hfa \
    7980        containers/pair.hfa \
  • libcfa/src/bits/collection.hfa

    rcd70477 rf99f5ba  
     1//
     2// Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo
     3//
     4// The contents of this file are covered under the licence agreement in the
     5// file "LICENCE" distributed with Cforall.
     6//
     7// bits/collection.hfa -- PUBLIC
     8// Intrusive singly-linked list
     9//
     10// Author           : Colby Alexander Parsons & Peter A. Buhr
     11// Created On       : Thu Jan 21 19:46:50 2021
     12// Last Modified By :
     13// Last Modified On :
     14// Update Count     :
     15//
     16
    117#pragma once
    2 #include <stdio.h> // REMOVE THIS AFTER DEBUGGING
    3 
    418
    519struct Colable {
    6         struct Colable * next;                                                                          // next node in the list
     20        // next node in the list
    721        // invariant: (next != 0) <=> listed()
     22        struct Colable * next;
    823};
    924#ifdef __cforall
     
    5368        Collection & ?=?( const Collection & ) = void;          // no assignment
    5469
    55         void ?{}( Collection & collection ) with( collection ) {       
     70        void ?{}( Collection & collection ) with( collection ) {
    5671                root = 0p;
    5772        } // post: empty()
  • libcfa/src/bits/sequence.hfa

    rcd70477 rf99f5ba  
     1//
     2// Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo
     3//
     4// The contents of this file are covered under the licence agreement in the
     5// file "LICENCE" distributed with Cforall.
     6//
     7// bits/sequence.hfa -- PUBLIC
     8// Intrusive doubly-linked list
     9//
     10// Author           : Colby Alexander Parsons & Peter A. Buhr
     11// Created On       : Thu Jan 21 19:46:50 2021
     12// Last Modified By :
     13// Last Modified On :
     14// Update Count     :
     15//
     16
    117#pragma once
    218
     
    622struct Seqable {
    723        __cfa_anonymous_object(Colable);
    8         struct Seqable * back;                                                                          // pointer to previous node in the list
     24        // pointer to previous node in the list
     25        struct Seqable * back;
    926};
    1027
     
    2744                return sq->back;
    2845        }
    29 
    30         // // wrappers to make Collection have T
    31         // forall( T & ) {
    32         //      T *& Back( T * n ) {
    33         //              return (T *)Back( (Seqable *)n );
    34         //      }
    35         // } // distribution
    3646} // distribution
    3747
     
    4353// and the back field of the last node points at the first node (circular).
    4454
    45 forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) {
     55forall( T & ) {
    4656        struct Sequence {
    47                 inline Collection;                                                              // Plan 9 inheritance
     57                // Plan 9 inheritance
     58                inline Collection;
    4859        };
    4960
    5061        static inline {
     62                void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
     63                Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
     64
     65                void ?{}( Sequence(T) & s ) with( s ) {
     66                        ((Collection &)s){};
     67                }       // post: isEmpty()
     68        }
     69
     70        static inline forall(| { T *& Back ( T * ); T *& Next ( T * ); }) {
    5171                // wrappers to make Collection have T
    5272                T & head( Sequence(T) & s ) with( s ) {
    5373                        return *(T *)head( (Collection &)s );
    5474                } // post: empty() & head() == 0 | !empty() & head() in *s
    55 
    56                 void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
    57                 Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
    58 
    59                 void ?{}( Sequence(T) & s ) with( s ) {
    60                         ((Collection &)s){};
    61                 }       // post: isEmpty()
    6275
    6376                // Return a pointer to the last sequence element, without removing it.
     
    145158                        return n;
    146159                } // post: n->listed() & *n in *s & succ(n) == bef
    147                
     160
    148161                // pre: n->listed() & *n in *s
    149162                T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
     
    285298
    286299        static inline {
    287                 void ?{}( SeqIterRev(T) & si ) with( si ) {     
     300                void ?{}( SeqIterRev(T) & si ) with( si ) {
    288301                        ((ColIter &)si){};
    289302                        seq = 0p;
     
    291304
    292305                // Create a iterator active in sequence s.
    293                 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {   
     306                void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
    294307                        ((ColIter &)si){};
    295308                        seq = &s;
     
    297310                } // post: elts = null
    298311
    299                 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { 
     312                void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) {
    300313                        ((ColIter &)si){};
    301314                        seq = &s;
  • libcfa/src/concurrency/locks.cfa

    rcd70477 rf99f5ba  
     1//
     2// Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo
     3//
     4// The contents of this file are covered under the licence agreement in the
     5// file "LICENCE" distributed with Cforall.
     6//
     7// locks.hfa -- LIBCFATHREAD
     8// Runtime locks that used with the runtime thread system.
     9//
     10// Author           : Colby Alexander Parsons
     11// Created On       : Thu Jan 21 19:46:50 2021
     12// Last Modified By :
     13// Last Modified On :
     14// Update Count     :
     15//
     16
     17#define __cforall_thread__
     18
    119#include "locks.hfa"
    220#include "kernel_private.hfa"
     
    5674
    5775void ^?{}( blocking_lock & this ) {}
    58 void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
    59 void ^?{}( single_acquisition_lock & this ) {}
    60 void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
    61 void ^?{}( owner_lock & this ) {}
    62 void  ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };}
    63 void ^?{}( multiple_acquisition_lock & this ) {}
     76
    6477
    6578void lock( blocking_lock & this ) with( this ) {
     
    168181        unlock( lock );
    169182}
    170 
    171 //-----------------------------------------------------------------------------
    172 // Overloaded routines for traits
    173 // These routines are temporary until an inheritance bug is fixed
    174 void   lock      ( single_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
    175 void   unlock    ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
    176 void   on_wait   ( single_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
    177 void   on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
    178 void   set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
    179 size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
    180 
    181 void   lock     ( owner_lock & this ) { lock   ( (blocking_lock &)this ); }
    182 void   unlock   ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
    183 void   on_wait  ( owner_lock & this ) { on_wait( (blocking_lock &)this ); }
    184 void   on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
    185 void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
    186 size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
    187 
    188 void   lock     ( multiple_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
    189 void   unlock   ( multiple_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
    190 void   on_wait  ( multiple_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
    191 void   on_notify( multiple_acquisition_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); }
    192 void   set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
    193 size_t get_recursion_count( multiple_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
    194183
    195184//-----------------------------------------------------------------------------
  • libcfa/src/concurrency/locks.hfa

    rcd70477 rf99f5ba  
     1//
     2// Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo
     3//
     4// The contents of this file are covered under the licence agreement in the
     5// file "LICENCE" distributed with Cforall.
     6//
     7// locks.hfa -- PUBLIC
     8// Runtime locks that used with the runtime thread system.
     9//
     10// Author           : Colby Alexander Parsons
     11// Created On       : Thu Jan 21 19:46:50 2021
     12// Last Modified By :
     13// Last Modified On :
     14// Update Count     :
     15//
     16
    117#pragma once
    218
    319#include <stdbool.h>
    420
    5 #include "bits/locks.hfa"
    6 #include "bits/sequence.hfa"
    7 
    8 #include "invoke.h"
     21#include "bits/weakso_locks.hfa"
    922
    1023#include "time_t.hfa"
    1124#include "time.hfa"
     25
     26//----------
     27struct single_acquisition_lock {
     28        inline blocking_lock;
     29};
     30
     31static inline void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
     32static inline void ^?{}( single_acquisition_lock & this ) {}
     33static inline void   lock      ( single_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
     34static inline void   unlock    ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
     35static inline void   on_wait   ( single_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
     36static inline void   on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
     37static inline void   set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
     38static inline size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
     39
     40//----------
     41struct owner_lock {
     42        inline blocking_lock;
     43};
     44
     45static inline void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
     46static inline void ^?{}( owner_lock & this ) {}
     47static inline void   lock     ( owner_lock & this ) { lock   ( (blocking_lock &)this ); }
     48static inline void   unlock   ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
     49static inline void   on_wait  ( owner_lock & this ) { on_wait( (blocking_lock &)this ); }
     50static inline void   on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
     51static inline void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
     52static inline size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
    1253
    1354//-----------------------------------------------------------------------------
     
    3879        info_thread(L) *& Next( info_thread(L) * this );
    3980}
    40 
    41 //-----------------------------------------------------------------------------
    42 // Blocking Locks
    43 struct blocking_lock {
    44         // Spin lock used for mutual exclusion
    45         __spinlock_t lock;
    46 
    47         // List of blocked threads
    48         Sequence( $thread ) blocked_threads;
    49 
    50         // Count of current blocked threads
    51         size_t wait_count;
    52 
    53         // Flag if the lock allows multiple acquisition
    54         bool multi_acquisition;
    55 
    56         // Flag if lock can be released by non owner
    57         bool strict_owner;
    58 
    59         // Current thread owning the lock
    60         struct $thread * owner;
    61 
    62         // Number of recursion level
    63         size_t recursion_count;
    64 };
    65 
    66 struct single_acquisition_lock {
    67         inline blocking_lock;
    68 };
    69 
    70 struct owner_lock {
    71         inline blocking_lock;
    72 };
    73 
    74 struct multiple_acquisition_lock {
    75         inline blocking_lock;
    76 };
    77 
    78 void  ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner );
    79 void ^?{}( blocking_lock & this );
    80 
    81 void  ?{}( single_acquisition_lock & this );
    82 void ^?{}( single_acquisition_lock & this );
    83 
    84 void  ?{}( owner_lock & this );
    85 void ^?{}( owner_lock & this );
    86 
    87 void  ?{}( multiple_acquisition_lock & this );
    88 void ^?{}( multiple_acquisition_lock & this );
    89 
    90 void lock( blocking_lock & this );
    91 bool try_lock( blocking_lock & this );
    92 void unlock( blocking_lock & this );
    93 void on_notify( blocking_lock & this, struct $thread * t );
    94 void on_wait( blocking_lock & this );
    95 size_t wait_count( blocking_lock & this );
    96 void set_recursion_count( blocking_lock & this, size_t recursion );
    97 size_t get_recursion_count( blocking_lock & this );
    98 
    99 void lock( single_acquisition_lock & this );
    100 void unlock( single_acquisition_lock & this );
    101 void on_notify( single_acquisition_lock & this, struct $thread * t );
    102 void on_wait( single_acquisition_lock & this );
    103 void set_recursion_count( single_acquisition_lock & this, size_t recursion );
    104 size_t get_recursion_count( single_acquisition_lock & this );
    105 
    106 void lock( owner_lock & this );
    107 void unlock( owner_lock & this );
    108 void on_notify( owner_lock & this, struct $thread * t );
    109 void on_wait( owner_lock & this );
    110 void set_recursion_count( owner_lock & this, size_t recursion );
    111 size_t get_recursion_count( owner_lock & this );
    112 
    113 void lock( multiple_acquisition_lock & this );
    114 void unlock( multiple_acquisition_lock & this );
    115 void on_notify( multiple_acquisition_lock & this, struct $thread * t );
    116 void on_wait( multiple_acquisition_lock & this );
    117 void set_recursion_count( multiple_acquisition_lock & this, size_t recursion );
    118 size_t get_recursion_count( multiple_acquisition_lock & this );
    11981
    12082//-----------------------------------------------------------------------------
  • libcfa/src/stdlib.hfa

    rcd70477 rf99f5ba  
    1010// Created On       : Thu Jan 28 17:12:35 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Jan 18 21:51:13 2021
    13 // Update Count     : 569
     12// Last Modified On : Thu Jan 21 22:02:13 2021
     13// Update Count     : 574
    1414//
    1515
     
    195195                                #pragma GCC diagnostic push
    196196                                #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
    197                                 memcpy( (char *)ptr + i, &Fill.t, sizeof(Fill.t) );
     197                                assert( size <= sizeof(Fill.t) );
     198                                memcpy( (char *)ptr + i, &Fill.t, size );
    198199                                #pragma GCC diagnostic pop
    199200                        }
  • src/Parser/parser.yy

    rcd70477 rf99f5ba  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Jan 11 21:32:10 2021
    13 // Update Count     : 4633
     12// Last Modified On : Wed Jan 27 08:58:56 2021
     13// Update Count     : 4680
    1414//
    1515
     
    4141
    4242%{
    43 #define YYDEBUG_LEXER_TEXT (yylval)                                             // lexer loads this up each time
     43#define YYDEBUG_LEXER_TEXT( yylval )                                    // lexer loads this up each time
    4444#define YYDEBUG 1                                                                               // get the pretty debugging code to compile
    4545#define YYERROR_VERBOSE                                                                 // more information in syntax errors
     
    6363extern TypedefTable typedefTable;
    6464
    65 stack< LinkageSpec::Spec > linkageStack;
     65stack<LinkageSpec::Spec> linkageStack;
    6666
    6767bool appendStr( string & to, string & from ) {
     
    187187        ConstantExpr * constant = dynamic_cast<ConstantExpr *>(type->expr.get());
    188188        if ( constant && (constant->get_constant()->get_value() == "0" || constant->get_constant()->get_value() == "1") ) {
    189         type = new ExpressionNode( new CastExpr( maybeMoveBuild< Expression >(type), new BasicType( Type::Qualifiers(), BasicType::SignedInt ) ) );
     189                type = new ExpressionNode( new CastExpr( maybeMoveBuild<Expression>(type), new BasicType( Type::Qualifiers(), BasicType::SignedInt ) ) );
    190190        } // if
    191191        return new ForCtrl(
     
    440440
    441441%type<decl> type_qualifier type_qualifier_name forall type_qualifier_list_opt type_qualifier_list
    442 %type<decl> type_specifier type_specifier_nobody
     442%type<decl> type_specifier type_specifier_nobody enum_specifier_nobody
    443443
    444444%type<decl> variable_declarator variable_ptr variable_array variable_function
    445445%type<decl> variable_abstract_declarator variable_abstract_ptr variable_abstract_array variable_abstract_function
    446446
    447 %type<decl> attribute_list_opt attribute_list attribute_name_list attribute attribute_name
     447%type<decl> attribute_list_opt attribute_list attribute_opt attribute attribute_name_list attribute_name
    448448
    449449// initializers
     
    578578                { $$ = $2; }
    579579        | '(' compound_statement ')'                                            // GCC, lambda expression
    580                 { $$ = new ExpressionNode( new StmtExpr( dynamic_cast< CompoundStmt * >(maybeMoveBuild< Statement >($2) ) ) ); }
     580                { $$ = new ExpressionNode( new StmtExpr( dynamic_cast<CompoundStmt *>(maybeMoveBuild<Statement>($2) ) ) ); }
    581581        | type_name '.' identifier                                                      // CFA, nested type
    582582                { SemanticError( yylloc, "Qualified name is currently unimplemented." ); $$ = nullptr; }
     
    610610                {
    611611                        // create a GenericExpr wrapper with one association pair
    612                         $$ = new GenericExpr( nullptr, { { maybeMoveBuildType($1), maybeMoveBuild<Expression>($3) } } );
     612                        $$ = new GenericExpr( nullptr, { { maybeMoveBuildType($1), maybeMoveBuild<Expression>( $3 ) } } );
    613613                }
    614614        | DEFAULT ':' assignment_expression
    615                 { $$ = new GenericExpr( nullptr, { { maybeMoveBuild<Expression>($3) } } ); }
     615                { $$ = new GenericExpr( nullptr, { { maybeMoveBuild<Expression>( $3 ) } } ); }
    616616        ;
    617617
     
    743743                        switch ( $1 ) {
    744744                          case OperKinds::AddressOf:
    745                                 $$ = new ExpressionNode( new AddressExpr( maybeMoveBuild< Expression >( $2 ) ) );
     745                                $$ = new ExpressionNode( new AddressExpr( maybeMoveBuild<Expression>( $2 ) ) );
    746746                                break;
    747747                          case OperKinds::PointTo:
     
    749749                                break;
    750750                          case OperKinds::And:
    751                                 $$ = new ExpressionNode( new AddressExpr( new AddressExpr( maybeMoveBuild< Expression >( $2 ) ) ) );
     751                                $$ = new ExpressionNode( new AddressExpr( new AddressExpr( maybeMoveBuild<Expression>( $2 ) ) ) );
    752752                                break;
    753753                          default:
     
    762762                { $$ = new ExpressionNode( build_unary_ptr( OperKinds::Decr, $2 ) ); }
    763763        | SIZEOF unary_expression
    764                 { $$ = new ExpressionNode( new SizeofExpr( maybeMoveBuild< Expression >( $2 ) ) ); }
     764                { $$ = new ExpressionNode( new SizeofExpr( maybeMoveBuild<Expression>( $2 ) ) ); }
    765765        | SIZEOF '(' type_no_function ')'
    766766                { $$ = new ExpressionNode( new SizeofExpr( maybeMoveBuildType( $3 ) ) ); }
    767767        | ALIGNOF unary_expression                                                      // GCC, variable alignment
    768                 { $$ = new ExpressionNode( new AlignofExpr( maybeMoveBuild< Expression >( $2 ) ) ); }
     768                { $$ = new ExpressionNode( new AlignofExpr( maybeMoveBuild<Expression>( $2 ) ) ); }
    769769        | ALIGNOF '(' type_no_function ')'                                      // GCC, type alignment
    770770                { $$ = new ExpressionNode( new AlignofExpr( maybeMoveBuildType( $3 ) ) ); }
     
    794794                { $$ = new ExpressionNode( build_keyword_cast( $2, $5 ) ); }
    795795        | '(' VIRTUAL ')' cast_expression                                       // CFA
    796                 { $$ = new ExpressionNode( new VirtualCastExpr( maybeMoveBuild< Expression >( $4 ), maybeMoveBuildType( nullptr ) ) ); }
     796                { $$ = new ExpressionNode( new VirtualCastExpr( maybeMoveBuild<Expression>( $4 ), maybeMoveBuildType( nullptr ) ) ); }
    797797        | '(' VIRTUAL type_no_function ')' cast_expression      // CFA
    798                 { $$ = new ExpressionNode( new VirtualCastExpr( maybeMoveBuild< Expression >( $5 ), maybeMoveBuildType( $3 ) ) ); }
     798                { $$ = new ExpressionNode( new VirtualCastExpr( maybeMoveBuild<Expression>( $5 ), maybeMoveBuildType( $3 ) ) ); }
    799799        | '(' RETURN type_no_function ')' cast_expression       // CFA
    800800                { SemanticError( yylloc, "Return cast is currently unimplemented." ); $$ = nullptr; }
     
    977977        assignment_expression
    978978        | comma_expression ',' assignment_expression
    979                 { $$ = new ExpressionNode( new CommaExpr( maybeMoveBuild< Expression >( $1 ), maybeMoveBuild< Expression >( $3 ) ) ); }
     979                { $$ = new ExpressionNode( new CommaExpr( maybeMoveBuild<Expression>( $1 ), maybeMoveBuild<Expression>( $3 ) ) ); }
    980980        ;
    981981
     
    11021102        constant_expression                                                     { $$ = $1; }
    11031103        | constant_expression ELLIPSIS constant_expression      // GCC, subrange
    1104                 { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild< Expression >( $1 ), maybeMoveBuild< Expression >( $3 ) ) ); }
     1104                { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild<Expression>( $1 ), maybeMoveBuild<Expression>( $3 ) ) ); }
    11051105        | subrange                                                                                      // CFA, subrange
    11061106        ;
     
    12471247                { $$ = new StatementNode( build_computedgoto( $3 ) ); }
    12481248                // A semantic check is required to ensure fallthru appears only in the body of a choose statement.
    1249     | fall_through_name ';'                                                             // CFA
     1249        | fall_through_name ';'                                                         // CFA
    12501250                { $$ = new StatementNode( build_branch( BranchStmt::FallThrough ) ); }
    1251     | fall_through_name identifier_or_type_name ';'             // CFA
     1251        | fall_through_name identifier_or_type_name ';'         // CFA
    12521252                { $$ = new StatementNode( build_branch( $2, BranchStmt::FallThrough ) ); }
    12531253        | fall_through_name DEFAULT ';'                                         // CFA
     
    14481448asm_operand:                                                                                    // GCC
    14491449        string_literal '(' constant_expression ')'
    1450                 { $$ = new ExpressionNode( new AsmExpr( nullptr, $1, maybeMoveBuild< Expression >( $3 ) ) ); }
     1450                { $$ = new ExpressionNode( new AsmExpr( nullptr, $1, maybeMoveBuild<Expression>( $3 ) ) ); }
    14511451        | '[' IDENTIFIER ']' string_literal '(' constant_expression ')'
    1452                 { $$ = new ExpressionNode( new AsmExpr( $2, $4, maybeMoveBuild< Expression >( $6 ) ) ); }
     1452                { $$ = new ExpressionNode( new AsmExpr( $2, $4, maybeMoveBuild<Expression>( $6 ) ) ); }
    14531453        ;
    14541454
     
    17361736        | sue_type_specifier_nobody
    17371737        | type_type_specifier
     1738        ;
     1739
     1740enum_specifier_nobody:                                                                  // type specifier - {...}
     1741                // Preclude SUE declarations in restricted scopes (see type_specifier_nobody)
     1742        basic_type_specifier
     1743        | sue_type_specifier_nobody
    17381744        ;
    17391745
     
    20042010        ;
    20052011
    2006 fred:
    2007         // empty
    2008                 { yyy = false; }
    2009         ;
    2010 
    20112012aggregate_type:                                                                                 // struct, union
    20122013        aggregate_key attribute_list_opt
     
    20142015          '{' field_declaration_list_opt '}' type_parameters_opt
    20152016                { $$ = DeclarationNode::newAggregate( $1, nullptr, $7, $5, true )->addQualifiers( $2 ); }
    2016         | aggregate_key attribute_list_opt identifier fred
     2017        | aggregate_key attribute_list_opt identifier
    20172018                {
    20182019                        typedefTable.makeTypedef( *$3, forall || typedefTable.getEnclForall() ? TYPEGENname : TYPEDEFname ); // create typedef
     
    20202021                }
    20212022          '{' field_declaration_list_opt '}' type_parameters_opt
    2022                 { $$ = DeclarationNode::newAggregate( $1, $3, $9, $7, true )->addQualifiers( $2 ); }
    2023         | aggregate_key attribute_list_opt type_name fred
     2023                { $$ = DeclarationNode::newAggregate( $1, $3, $8, $6, true )->addQualifiers( $2 ); }
     2024        | aggregate_key attribute_list_opt type_name
    20242025                {
    20252026                        // for type_name can be a qualified type name S.T, in which case only the last name in the chain needs a typedef (other names in the chain should already have one)
     
    20282029                }
    20292030          '{' field_declaration_list_opt '}' type_parameters_opt
    2030                 { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $9, $7, true )->addQualifiers( $2 ); }
     2031                { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $8, $6, true )->addQualifiers( $2 ); }
    20312032        | aggregate_type_nobody
    20322033        ;
     
    20402041
    20412042aggregate_type_nobody:                                                                  // struct, union - {...}
    2042         aggregate_key attribute_list_opt identifier fred
     2043        aggregate_key attribute_list_opt identifier
    20432044                {
    20442045                        typedefTable.makeTypedef( *$3, forall || typedefTable.getEnclForall() ? TYPEGENname : TYPEDEFname );
     
    20462047                        $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 );
    20472048                }
    2048         | aggregate_key attribute_list_opt type_name fred
     2049        | aggregate_key attribute_list_opt type_name
    20492050                {
    20502051                        forall = false;                                                         // reset
     
    21842185        ;
    21852186
     2187// Cannot use attribute_list_opt because of ambiguity with enum_specifier_nobody, which already parses attribute.
     2188// Hence, only a single attribute is allowed after the "ENUM".
    21862189enum_type:                                                                                              // enum
    2187         ENUM attribute_list_opt '{' enumerator_list comma_opt '}'
     2190        ENUM attribute_opt '{' enumerator_list comma_opt '}'
    21882191                { $$ = DeclarationNode::newEnum( nullptr, $4, true )->addQualifiers( $2 ); }
    2189         | ENUM attribute_list_opt identifier
     2192        | ENUM attribute_opt identifier
    21902193                { typedefTable.makeTypedef( *$3 ); }
    21912194          '{' enumerator_list comma_opt '}'
    21922195                { $$ = DeclarationNode::newEnum( $3, $6, true )->addQualifiers( $2 ); }
    2193         | ENUM attribute_list_opt type_name
     2196        | ENUM attribute_opt typedef                                            // enum cannot be generic
    21942197          '{' enumerator_list comma_opt '}'
    2195                 { $$ = DeclarationNode::newEnum( $3->type->symbolic.name, $5, true )->addQualifiers( $2 ); }
     2198                { $$ = DeclarationNode::newEnum( $3->name, $5, true )->addQualifiers( $2 ); }
     2199        | ENUM enum_specifier_nobody '{' enumerator_list comma_opt '}'
     2200                // { $$ = DeclarationNode::newEnum( nullptr, $4, true ); }
     2201                { SemanticError( yylloc, "Typed enumeration is currently unimplemented." ); $$ = nullptr; }
     2202        | ENUM enum_specifier_nobody declarator '{' enumerator_list comma_opt '}'
     2203                // {
     2204                //      typedefTable.makeTypedef( *$3->name );
     2205                //      $$ = DeclarationNode::newEnum( nullptr, $5, true );
     2206                // }
     2207                { SemanticError( yylloc, "Typed enumeration is currently unimplemented." ); $$ = nullptr; }
    21962208        | enum_type_nobody
    21972209        ;
    21982210
    21992211enum_type_nobody:                                                                               // enum - {...}
    2200         ENUM attribute_list_opt identifier
     2212        ENUM attribute_opt identifier
    22012213                {
    22022214                        typedefTable.makeTypedef( *$3 );
    22032215                        $$ = DeclarationNode::newEnum( $3, 0, false )->addQualifiers( $2 );
    22042216                }
    2205         | ENUM attribute_list_opt type_name
     2217        | ENUM attribute_opt type_name                                          // enum cannot be generic
    22062218                {
    22072219                        typedefTable.makeTypedef( *$3->type->symbolic.name );
     
    22202232        // empty
    22212233                { $$ = nullptr; }
    2222         | '=' constant_expression
    2223                 { $$ = $2; }
     2234        // | '=' constant_expression
     2235        //      { $$ = $2; }
     2236        | '=' initializer
     2237                { $$ = $2->get_expression(); }                                  // FIX ME: enum only deals with constant_expression
    22242238        ;
    22252239
     
    24032417                { $$ = $3; }
    24042418        | '[' push constant_expression ELLIPSIS constant_expression pop ']' // GCC, multiple array elements
    2405                 { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild< Expression >( $3 ), maybeMoveBuild< Expression >( $5 ) ) ); }
     2419                { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild<Expression>( $3 ), maybeMoveBuild<Expression>( $5 ) ) ); }
    24062420        | '.' '[' push field_name_list pop ']'                          // CFA, tuple field selector
    24072421                { $$ = $4; }
     
    24412455type_parameter:                                                                                 // CFA
    24422456        type_class identifier_or_type_name
    2443                 {   typedefTable.addToScope( *$2, TYPEDEFname, "9" );
    2444                         if ( $1 == TypeDecl::Otype ) { SemanticError( yylloc, "otype keyword is deprecated" ); }
    2445                         if ( $1 == TypeDecl::Dtype ) { SemanticError( yylloc, "dtype keyword is deprecated" ); }
    2446                         if ( $1 == TypeDecl::Ttype ) { SemanticError( yylloc, "ttype keyword is deprecated" ); }
     2457                {
     2458                        typedefTable.addToScope( *$2, TYPEDEFname, "9" );
     2459                        if ( $1 == TypeDecl::Otype ) { SemanticError( yylloc, "otype keyword is deprecated, use T " ); }
     2460                        if ( $1 == TypeDecl::Dtype ) { SemanticError( yylloc, "dtype keyword is deprecated, use T &" ); }
     2461                        if ( $1 == TypeDecl::Ttype ) { SemanticError( yylloc, "ttype keyword is deprecated, use T ..." ); }
    24472462                }
    24482463          type_initializer_opt assertion_list_opt
     
    27382753subrange:
    27392754        constant_expression '~' constant_expression                     // CFA, integer subrange
    2740                 { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild< Expression >( $1 ), maybeMoveBuild< Expression >( $3 ) ) ); }
     2755                { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild<Expression>( $1 ), maybeMoveBuild<Expression>( $3 ) ) ); }
    27412756        ;
    27422757
     
    27622777        | attribute_list attribute
    27632778                { $$ = $2->addQualifiers( $1 ); }
     2779        ;
     2780
     2781attribute_opt:
     2782        // empty
     2783                { $$ = nullptr; }
     2784        | attribute
    27642785        ;
    27652786
  • tests/.expect/attributes.nast.x64.txt

    rcd70477 rf99f5ba  
    66
    77}
    8 struct __attribute__ ((unused)) __anonymous0 {
     8struct __anonymous0 {
    99};
    1010static inline void _X12_constructorFv_S12__anonymous0_autogen___1(struct __anonymous0 *_X4_dstS12__anonymous0_1);
     
    2626    return _X4_retS12__anonymous0_1;
    2727}
     28__attribute__ ((unused)) struct __anonymous0 _X5DummyS12__anonymous0_1;
    2829struct __attribute__ ((unused)) Agn1;
    2930struct __attribute__ ((unused)) Agn2 {
  • tests/.expect/attributes.nast.x86.txt

    rcd70477 rf99f5ba  
    66
    77}
    8 struct __attribute__ ((unused)) __anonymous0 {
     8struct __anonymous0 {
    99};
    1010static inline void _X12_constructorFv_S12__anonymous0_autogen___1(struct __anonymous0 *_X4_dstS12__anonymous0_1);
     
    2626    return _X4_retS12__anonymous0_1;
    2727}
     28__attribute__ ((unused)) struct __anonymous0 _X5DummyS12__anonymous0_1;
    2829struct __attribute__ ((unused)) Agn1;
    2930struct __attribute__ ((unused)) Agn2 {
  • tests/.expect/attributes.oast.x64.txt

    rcd70477 rf99f5ba  
    66
    77}
    8 struct __attribute__ ((unused)) __anonymous0 {
     8struct __anonymous0 {
    99};
    1010static inline void _X12_constructorFv_S12__anonymous0_autogen___1(struct __anonymous0 *_X4_dstS12__anonymous0_1);
     
    2626    return _X4_retS12__anonymous0_1;
    2727}
     28__attribute__ ((unused)) struct __anonymous0 _X5DummyS12__anonymous0_1;
    2829struct __attribute__ ((unused)) Agn1;
    2930struct __attribute__ ((unused)) Agn2 {
  • tests/.expect/attributes.oast.x86.txt

    rcd70477 rf99f5ba  
    66
    77}
    8 struct __attribute__ ((unused)) __anonymous0 {
     8struct __anonymous0 {
    99};
    1010static inline void _X12_constructorFv_S12__anonymous0_autogen___1(struct __anonymous0 *_X4_dstS12__anonymous0_1);
     
    2626    return _X4_retS12__anonymous0_1;
    2727}
     28__attribute__ ((unused)) struct __anonymous0 _X5DummyS12__anonymous0_1;
    2829struct __attribute__ ((unused)) Agn1;
    2930struct __attribute__ ((unused)) Agn2 {
  • tests/alloc2.cfa

    rcd70477 rf99f5ba  
    1616        bool passed = (malloc_size(ip) == size) && (malloc_usable_size(ip) >= size) && (malloc_alignment(ip) == align) && ((uintptr_t)ip % align  == 0);
    1717        if (!passed) {
    18                 printf("failed test %3d: %4lu %4lu but got %4lu ( %3lu ) %4lu\n", tests_total, size, align, malloc_size(ip), malloc_usable_size(ip), malloc_alignment(ip));
     18                printf("failed test %3d: %4zu %4zu but got %4zu ( %3zu ) %4zu\n", tests_total, size, align, malloc_size(ip), malloc_usable_size(ip), malloc_alignment(ip));
    1919                tests_failed += 1;
    2020        }
  • tests/attributes.cfa

    rcd70477 rf99f5ba  
    1010// Created On       : Mon Feb  6 16:07:02 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Tue Nov  6 17:51:12 2018
    13 // Update Count     : 17
     12// Last Modified On : Mon Jan 25 21:26:41 2021
     13// Update Count     : 20
    1414//
    1515
     
    2222
    2323// aggregate_name
    24 struct __attribute__(( unused )) {};
     24struct __attribute__(( unused )) {} Dummy;
    2525struct __attribute__(( unused )) Agn1;
    2626struct __attribute__(( unused )) Agn2 {};
  • tools/prettyprinter/Makefile.am

    rcd70477 rf99f5ba  
    1111## Created On       : Wed Jun 28 12:07:10 2017
    1212## Last Modified By : Peter A. Buhr
    13 ## Last Modified On : Mon Apr 16 09:43:23 2018
    14 ## Update Count     : 20
     13## Last Modified On : Thu Jan 28 08:48:22 2021
     14## Update Count     : 23
    1515###############################################################################
    1616
     
    2020BUILT_SOURCES = parser.hh
    2121
    22 AM_YFLAGS = -d -t -v
     22AM_YFLAGS = -d -t -v -Wno-yacc
    2323
    2424SRC = lex.ll \
     
    3434pretty_CXXFLAGS = -Wno-deprecated -Wall -DYY_NO_INPUT -O2 -g -std=c++14
    3535
    36 MAINTAINERCLEANFILES = parser.output
     36MOSTLYCLEANFILES = parser.output
  • tools/prettyprinter/ParserTypes.h

    rcd70477 rf99f5ba  
    1313// Created On       : Sun Dec 16 15:00:49 2001
    1414// Last Modified By : Peter A. Buhr
    15 // Last Modified On : Sat Jul 22 10:13:09 2017
    16 // Update Count     : 175
     15// Last Modified On : Tue Jan 26 23:05:34 2021
     16// Update Count     : 176
    1717//
    1818
    1919#pragma once
    2020
    21 int yylex();
     21extern "C" int yylex();
    2222
    2323#include <string>
  • tools/prettyprinter/parser.yy

    rcd70477 rf99f5ba  
    1010// Created On       : Sat Dec 15 13:44:21 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sun Apr 15 21:40:30 2018
    13 // Update Count     : 1052
     12// Last Modified On : Tue Jan 26 22:50:03 2021
     13// Update Count     : 1053
    1414//
    1515
     
    1717#define YYDEBUG_LEXER_TEXT( yylval )                                    // lexer loads this up each time
    1818#define YYDEBUG 1                                                                               // get the pretty debugging code to compile
     19#define YYERROR_VERBOSE                                                                 // more information in syntax errors
    1920
    2021#include <iostream>
Note: See TracChangeset for help on using the changeset viewer.