Changes in / [f99f5ba:cd70477]


Ignore:
Files:
4 deleted
26 edited

Legend:

Unmodified
Added
Removed

  • .gitignore

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

  • doc/LaTeXmacros/common.tex

    rf99f5ba rcd70477  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Thu Jan 28 19:01:57 2021
    14 %% Update Count     : 494
     13%% Last Modified On : Mon Oct  5 09:34:46 2020
     14%% Update Count     : 464
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    3232\setlist[enumerate]{listparindent=\parindent}% global
    3333\setlist[enumerate,2]{leftmargin=\parindent,labelsep=*,align=parleft,label=\alph*.}% local
    34 \setlist[description]{topsep=0.5ex,itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex}
     34\setlist[description]{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]{(see #1)}
     91\newcommand{\see}[1]{\emph{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 
    233231\makeatletter
     232
    234233\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{#1}}}
    235234\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
    … …  
    266265showlines=true,                                                 % show blank lines at end of code
    267266aboveskip=4pt,                                                  % spacing above/below code block
    268 belowskip=-2pt,
    269 numberstyle=\footnotesize\sf,                   % numbering style
     267belowskip=3pt,
    270268% replace/adjust listing characters that look bad in sanserif
    271269literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.75ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    … …  
    295293language=CFA,
    296294escapechar=\$,                                                  % LaTeX escape in CFA code
    297 mathescape=false,                                               % LaTeX math escape in CFA code $...$
    298295moredelim=**[is][\color{red}]{@}{@},    % red highlighting @...@
    299296}% lstset

  • doc/bibliography/pl.bib

    rf99f5ba rcd70477  
    17971797}
    17981798
    1799 @article{Delisle20,
     1799@article{Delisle19,
    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        = 2020,
     1804    year        = 2019,
    18051805    journal     = spe,
    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        = {},
     1806    pages       = {1-33},
     1807    note        = {submitted},
    18091808}
    18101809

  • doc/theses/andrew_beach_MMath/.gitignore

    rf99f5ba rcd70477  
    33
    44# Final Files:
    5 *.pdf
     5thesis.pdf
    66
    77# The Makefile here is not generated.

  • doc/theses/andrew_beach_MMath/existing.tex

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

  • doc/theses/andrew_beach_MMath/features.tex

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

  • doc/theses/andrew_beach_MMath/future.tex

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

  • doc/theses/andrew_beach_MMath/implement.tex

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

  • doc/theses/andrew_beach_MMath/unwinding.tex

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

  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rf99f5ba rcd70477  
    9191\hypersetup{
    9292    plainpages=false,       % needed if Roman numbers in frontpages
    93     unicode=false,          % non-Latin characters in Acrobat's bookmarks
    94     pdftoolbar=true,        % show Acrobat's toolbar?
    95     pdfmenubar=true,        % show Acrobat's 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{language=CFA,basicstyle=\linespread{0.9}\tt}    % CFA default lnaguage
    166 \newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
     165\lstset{basicstyle=\linespread{0.9}\tt}
    167166
    168167%======================================================================
    … …  
    189188\input{existing}
    190189\input{features}
    191 \input{implement}
    192 %\input{unwinding}
     190\input{unwinding}
    193191\input{future}
    194192

  • libcfa/src/Makefile.am

    rf99f5ba rcd70477  
    7676        stdlib.hfa \
    7777        time.hfa \
    78         bits/weakso_locks.hfa \
    7978        containers/maybe.hfa \
    8079        containers/pair.hfa \

  • libcfa/src/bits/collection.hfa

    rf99f5ba rcd70477  
    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 //
     1#pragma once
     2#include <stdio.h> // REMOVE THIS AFTER DEBUGGING
    163
    17 #pragma once
    184
    195struct Colable {
    20         // next node in the list
     6        struct Colable * next;                                                                          // next node in the list
    217        // invariant: (next != 0) <=> listed()
    22         struct Colable * next;
    238};
    249#ifdef __cforall
    … …  
    6853        Collection & ?=?( const Collection & ) = void;          // no assignment
    6954
    70         void ?{}( Collection & collection ) with( collection ) {
     55        void ?{}( Collection & collection ) with( collection ) {       
    7156                root = 0p;
    7257        } // post: empty()

  • libcfa/src/bits/sequence.hfa

    rf99f5ba rcd70477  
    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 
    171#pragma once
    182
    … …  
    226struct Seqable {
    237        __cfa_anonymous_object(Colable);
    24         // pointer to previous node in the list
    25         struct Seqable * back;
     8        struct Seqable * back;                                                                          // pointer to previous node in the list
    269};
    2710
    … …  
    4427                return sq->back;
    4528        }
     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
    4636} // distribution
    4737
    … …  
    5343// and the back field of the last node points at the first node (circular).
    5444
    55 forall( T & ) {
     45forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) {
    5646        struct Sequence {
    57                 // Plan 9 inheritance
    58                 inline Collection;
     47                inline Collection;                                                              // Plan 9 inheritance
    5948        };
    6049
    6150        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 * ); }) {
    7151                // wrappers to make Collection have T
    7252                T & head( Sequence(T) & s ) with( s ) {
    7353                        return *(T *)head( (Collection &)s );
    7454                } // 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()
    7562
    7663                // Return a pointer to the last sequence element, without removing it.
    … …  
    158145                        return n;
    159146                } // post: n->listed() & *n in *s & succ(n) == bef
    160 
     147               
    161148                // pre: n->listed() & *n in *s
    162149                T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
    … …  
    298285
    299286        static inline {
    300                 void ?{}( SeqIterRev(T) & si ) with( si ) {
     287                void ?{}( SeqIterRev(T) & si ) with( si ) {     
    301288                        ((ColIter &)si){};
    302289                        seq = 0p;
    … …  
    304291
    305292                // Create a iterator active in sequence s.
    306                 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
     293                void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {   
    307294                        ((ColIter &)si){};
    308295                        seq = &s;
    … …  
    310297                } // post: elts = null
    311298
    312                 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) {
     299                void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { 
    313300                        ((ColIter &)si){};
    314301                        seq = &s;

  • libcfa/src/concurrency/locks.cfa

    rf99f5ba rcd70477  
    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 
    191#include "locks.hfa"
    202#include "kernel_private.hfa"
    … …  
    7456
    7557void ^?{}( blocking_lock & this ) {}
    76 
     58void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
     59void ^?{}( single_acquisition_lock & this ) {}
     60void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
     61void ^?{}( owner_lock & this ) {}
     62void  ?{}( multiple_acquisition_lock & this ) {((blocking_lock &)this){ true, false };}
     63void ^?{}( multiple_acquisition_lock & this ) {}
    7764
    7865void lock( blocking_lock & this ) with( this ) {
    … …  
    181168        unlock( lock );
    182169}
     170
     171//-----------------------------------------------------------------------------
     172// Overloaded routines for traits
     173// These routines are temporary until an inheritance bug is fixed
     174void   lock      ( single_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
     175void   unlock    ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
     176void   on_wait   ( single_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
     177void   on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
     178void   set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
     179size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
     180
     181void   lock     ( owner_lock & this ) { lock   ( (blocking_lock &)this ); }
     182void   unlock   ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
     183void   on_wait  ( owner_lock & this ) { on_wait( (blocking_lock &)this ); }
     184void   on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
     185void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
     186size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
     187
     188void   lock     ( multiple_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
     189void   unlock   ( multiple_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
     190void   on_wait  ( multiple_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
     191void   on_notify( multiple_acquisition_lock & this, struct $thread * t ){ on_notify( (blocking_lock &)this, t ); }
     192void   set_recursion_count( multiple_acquisition_lock & this, size_t recursion ){ set_recursion_count( (blocking_lock &)this, recursion ); }
     193size_t get_recursion_count( multiple_acquisition_lock & this ){ return get_recursion_count( (blocking_lock &)this ); }
    183194
    184195//-----------------------------------------------------------------------------

  • libcfa/src/concurrency/locks.hfa

    rf99f5ba rcd70477  
    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 
    171#pragma once
    182
    193#include <stdbool.h>
    204
    21 #include "bits/weakso_locks.hfa"
     5#include "bits/locks.hfa"
     6#include "bits/sequence.hfa"
     7
     8#include "invoke.h"
    229
    2310#include "time_t.hfa"
    2411#include "time.hfa"
    25 
    26 //----------
    27 struct single_acquisition_lock {
    28         inline blocking_lock;
    29 };
    30 
    31 static inline void  ?{}( single_acquisition_lock & this ) {((blocking_lock &)this){ false, false };}
    32 static inline void ^?{}( single_acquisition_lock & this ) {}
    33 static inline void   lock      ( single_acquisition_lock & this ) { lock   ( (blocking_lock &)this ); }
    34 static inline void   unlock    ( single_acquisition_lock & this ) { unlock ( (blocking_lock &)this ); }
    35 static inline void   on_wait   ( single_acquisition_lock & this ) { on_wait( (blocking_lock &)this ); }
    36 static inline void   on_notify ( single_acquisition_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
    37 static inline void   set_recursion_count( single_acquisition_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
    38 static inline size_t get_recursion_count( single_acquisition_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
    39 
    40 //----------
    41 struct owner_lock {
    42         inline blocking_lock;
    43 };
    44 
    45 static inline void  ?{}( owner_lock & this ) {((blocking_lock &)this){ true, true };}
    46 static inline void ^?{}( owner_lock & this ) {}
    47 static inline void   lock     ( owner_lock & this ) { lock   ( (blocking_lock &)this ); }
    48 static inline void   unlock   ( owner_lock & this ) { unlock ( (blocking_lock &)this ); }
    49 static inline void   on_wait  ( owner_lock & this ) { on_wait( (blocking_lock &)this ); }
    50 static inline void   on_notify( owner_lock & this, struct $thread * t ) { on_notify( (blocking_lock &)this, t ); }
    51 static inline void   set_recursion_count( owner_lock & this, size_t recursion ) { set_recursion_count( (blocking_lock &)this, recursion ); }
    52 static inline size_t get_recursion_count( owner_lock & this ) { return get_recursion_count( (blocking_lock &)this ); }
    5312
    5413//-----------------------------------------------------------------------------
    … …  
    7938        info_thread(L) *& Next( info_thread(L) * this );
    8039}
     40
     41//-----------------------------------------------------------------------------
     42// Blocking Locks
     43struct 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
     66struct single_acquisition_lock {
     67        inline blocking_lock;
     68};
     69
     70struct owner_lock {
     71        inline blocking_lock;
     72};
     73
     74struct multiple_acquisition_lock {
     75        inline blocking_lock;
     76};
     77
     78void  ?{}( blocking_lock & this, bool multi_acquisition, bool strict_owner );
     79void ^?{}( blocking_lock & this );
     80
     81void  ?{}( single_acquisition_lock & this );
     82void ^?{}( single_acquisition_lock & this );
     83
     84void  ?{}( owner_lock & this );
     85void ^?{}( owner_lock & this );
     86
     87void  ?{}( multiple_acquisition_lock & this );
     88void ^?{}( multiple_acquisition_lock & this );
     89
     90void lock( blocking_lock & this );
     91bool try_lock( blocking_lock & this );
     92void unlock( blocking_lock & this );
     93void on_notify( blocking_lock & this, struct $thread * t );
     94void on_wait( blocking_lock & this );
     95size_t wait_count( blocking_lock & this );
     96void set_recursion_count( blocking_lock & this, size_t recursion );
     97size_t get_recursion_count( blocking_lock & this );
     98
     99void lock( single_acquisition_lock & this );
     100void unlock( single_acquisition_lock & this );
     101void on_notify( single_acquisition_lock & this, struct $thread * t );
     102void on_wait( single_acquisition_lock & this );
     103void set_recursion_count( single_acquisition_lock & this, size_t recursion );
     104size_t get_recursion_count( single_acquisition_lock & this );
     105
     106void lock( owner_lock & this );
     107void unlock( owner_lock & this );
     108void on_notify( owner_lock & this, struct $thread * t );
     109void on_wait( owner_lock & this );
     110void set_recursion_count( owner_lock & this, size_t recursion );
     111size_t get_recursion_count( owner_lock & this );
     112
     113void lock( multiple_acquisition_lock & this );
     114void unlock( multiple_acquisition_lock & this );
     115void on_notify( multiple_acquisition_lock & this, struct $thread * t );
     116void on_wait( multiple_acquisition_lock & this );
     117void set_recursion_count( multiple_acquisition_lock & this, size_t recursion );
     118size_t get_recursion_count( multiple_acquisition_lock & this );
    81119
    82120//-----------------------------------------------------------------------------

  • libcfa/src/stdlib.hfa

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

  • src/Parser/parser.yy

    rf99f5ba rcd70477  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Jan 27 08:58:56 2021
    13 // Update Count     : 4680
     12// Last Modified On : Mon Jan 11 21:32:10 2021
     13// Update Count     : 4633
    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 enum_specifier_nobody
     442%type<decl> type_specifier type_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_opt attribute attribute_name_list attribute_name
     447%type<decl> attribute_list_opt attribute_list attribute_name_list attribute 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 
    1740 enum_specifier_nobody:                                                                  // type specifier - {...}
    1741                 // Preclude SUE declarations in restricted scopes (see type_specifier_nobody)
    1742         basic_type_specifier
    1743         | sue_type_specifier_nobody
    17441738        ;
    17451739
    … …  
    20102004        ;
    20112005
     2006fred:
     2007        // empty
     2008                { yyy = false; }
     2009        ;
     2010
    20122011aggregate_type:                                                                                 // struct, union
    20132012        aggregate_key attribute_list_opt
    … …  
    20152014          '{' field_declaration_list_opt '}' type_parameters_opt
    20162015                { $$ = DeclarationNode::newAggregate( $1, nullptr, $7, $5, true )->addQualifiers( $2 ); }
    2017         | aggregate_key attribute_list_opt identifier
     2016        | aggregate_key attribute_list_opt identifier fred
    20182017                {
    20192018                        typedefTable.makeTypedef( *$3, forall || typedefTable.getEnclForall() ? TYPEGENname : TYPEDEFname ); // create typedef
    … …  
    20212020                }
    20222021          '{' field_declaration_list_opt '}' type_parameters_opt
    2023                 { $$ = DeclarationNode::newAggregate( $1, $3, $8, $6, true )->addQualifiers( $2 ); }
    2024         | aggregate_key attribute_list_opt type_name
     2022                { $$ = DeclarationNode::newAggregate( $1, $3, $9, $7, true )->addQualifiers( $2 ); }
     2023        | aggregate_key attribute_list_opt type_name fred
    20252024                {
    20262025                        // 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)
    … …  
    20292028                }
    20302029          '{' field_declaration_list_opt '}' type_parameters_opt
    2031                 { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $8, $6, true )->addQualifiers( $2 ); }
     2030                { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, $9, $7, true )->addQualifiers( $2 ); }
    20322031        | aggregate_type_nobody
    20332032        ;
    … …  
    20412040
    20422041aggregate_type_nobody:                                                                  // struct, union - {...}
    2043         aggregate_key attribute_list_opt identifier
     2042        aggregate_key attribute_list_opt identifier fred
    20442043                {
    20452044                        typedefTable.makeTypedef( *$3, forall || typedefTable.getEnclForall() ? TYPEGENname : TYPEDEFname );
    … …  
    20472046                        $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 );
    20482047                }
    2049         | aggregate_key attribute_list_opt type_name
     2048        | aggregate_key attribute_list_opt type_name fred
    20502049                {
    20512050                        forall = false;                                                         // reset
    … …  
    21852184        ;
    21862185
    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".
    21892186enum_type:                                                                                              // enum
    2190         ENUM attribute_opt '{' enumerator_list comma_opt '}'
     2187        ENUM attribute_list_opt '{' enumerator_list comma_opt '}'
    21912188                { $$ = DeclarationNode::newEnum( nullptr, $4, true )->addQualifiers( $2 ); }
    2192         | ENUM attribute_opt identifier
     2189        | ENUM attribute_list_opt identifier
    21932190                { typedefTable.makeTypedef( *$3 ); }
    21942191          '{' enumerator_list comma_opt '}'
    21952192                { $$ = DeclarationNode::newEnum( $3, $6, true )->addQualifiers( $2 ); }
    2196         | ENUM attribute_opt typedef                                            // enum cannot be generic
     2193        | ENUM attribute_list_opt type_name
    21972194          '{' enumerator_list comma_opt '}'
    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; }
     2195                { $$ = DeclarationNode::newEnum( $3->type->symbolic.name, $5, true )->addQualifiers( $2 ); }
    22082196        | enum_type_nobody
    22092197        ;
    22102198
    22112199enum_type_nobody:                                                                               // enum - {...}
    2212         ENUM attribute_opt identifier
     2200        ENUM attribute_list_opt identifier
    22132201                {
    22142202                        typedefTable.makeTypedef( *$3 );
    22152203                        $$ = DeclarationNode::newEnum( $3, 0, false )->addQualifiers( $2 );
    22162204                }
    2217         | ENUM attribute_opt type_name                                          // enum cannot be generic
     2205        | ENUM attribute_list_opt type_name
    22182206                {
    22192207                        typedefTable.makeTypedef( *$3->type->symbolic.name );
    … …  
    22322220        // empty
    22332221                { $$ = nullptr; }
    2234         // | '=' constant_expression
    2235         //      { $$ = $2; }
    2236         | '=' initializer
    2237                 { $$ = $2->get_expression(); }                                  // FIX ME: enum only deals with constant_expression
     2222        | '=' constant_expression
     2223                { $$ = $2; }
    22382224        ;
    22392225
    … …  
    24172403                { $$ = $3; }
    24182404        | '[' push constant_expression ELLIPSIS constant_expression pop ']' // GCC, multiple array elements
    2419                 { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild<Expression>( $3 ), maybeMoveBuild<Expression>( $5 ) ) ); }
     2405                { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild< Expression >( $3 ), maybeMoveBuild< Expression >( $5 ) ) ); }
    24202406        | '.' '[' push field_name_list pop ']'                          // CFA, tuple field selector
    24212407                { $$ = $4; }
    … …  
    24552441type_parameter:                                                                                 // CFA
    24562442        type_class identifier_or_type_name
    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 ..." ); }
     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" ); }
    24622447                }
    24632448          type_initializer_opt assertion_list_opt
    … …  
    27532738subrange:
    27542739        constant_expression '~' constant_expression                     // CFA, integer subrange
    2755                 { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild<Expression>( $1 ), maybeMoveBuild<Expression>( $3 ) ) ); }
     2740                { $$ = new ExpressionNode( new RangeExpr( maybeMoveBuild< Expression >( $1 ), maybeMoveBuild< Expression >( $3 ) ) ); }
    27562741        ;
    27572742
    … …  
    27772762        | attribute_list attribute
    27782763                { $$ = $2->addQualifiers( $1 ); }
    2779         ;
    2780 
    2781 attribute_opt:
    2782         // empty
    2783                 { $$ = nullptr; }
    2784         | attribute
    27852764        ;
    27862765

  • tests/.expect/attributes.nast.x64.txt

    rf99f5ba rcd70477  
    66
    77}
    8 struct __anonymous0 {
     8struct __attribute__ ((unused)) __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;
    2928struct __attribute__ ((unused)) Agn1;
    3029struct __attribute__ ((unused)) Agn2 {

  • tests/.expect/attributes.nast.x86.txt

    rf99f5ba rcd70477  
    66
    77}
    8 struct __anonymous0 {
     8struct __attribute__ ((unused)) __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;
    2928struct __attribute__ ((unused)) Agn1;
    3029struct __attribute__ ((unused)) Agn2 {

  • tests/.expect/attributes.oast.x64.txt

    rf99f5ba rcd70477  
    66
    77}
    8 struct __anonymous0 {
     8struct __attribute__ ((unused)) __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;
    2928struct __attribute__ ((unused)) Agn1;
    3029struct __attribute__ ((unused)) Agn2 {

  • tests/.expect/attributes.oast.x86.txt

    rf99f5ba rcd70477  
    66
    77}
    8 struct __anonymous0 {
     8struct __attribute__ ((unused)) __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;
    2928struct __attribute__ ((unused)) Agn1;
    3029struct __attribute__ ((unused)) Agn2 {

  • tests/alloc2.cfa

    rf99f5ba rcd70477  
    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: %4zu %4zu but got %4zu ( %3zu ) %4zu\n", tests_total, size, align, malloc_size(ip), malloc_usable_size(ip), malloc_alignment(ip));
     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));
    1919                tests_failed += 1;
    2020        }

  • tests/attributes.cfa

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

  • tools/prettyprinter/Makefile.am

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

  • tools/prettyprinter/ParserTypes.h

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

  • tools/prettyprinter/parser.yy

    rf99f5ba rcd70477  
    1010// Created On       : Sat Dec 15 13:44:21 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Tue Jan 26 22:50:03 2021
    13 // Update Count     : 1053
     12// Last Modified On : Sun Apr 15 21:40:30 2018
     13// Update Count     : 1052
    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
    2019
    2120#include <iostream>
Note: See TracChangeset for help on using the changeset viewer.