Ignore:
Timestamp:
May 21, 2021, 4:48:10 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum, stuck-waitfor-destruct
Children:
f1bce515
Parents:
5407cdc (diff), 7404cdc (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

Location:
doc/theses/andrew_beach_MMath
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/Makefile

    r5407cdc r8d66610  
    3434        ${LATEX} ${BASE}
    3535        ${BIBTEX} ${BUILD}/${BASE}
    36         ${LATEX} ${BASE}
    3736        ${GLOSSARY} ${BUILD}/${BASE}
    3837        ${LATEX} ${BASE}

  • doc/theses/andrew_beach_MMath/cfalab.sty

    r5407cdc r8d66610  
    11% Package for CFA Research Lab.
     2% (Now more a personal collection and testing grounds for common.sty.)
    23%
    3 % Made by combining and updating various macro files people had made.
     4% This is a collection of commands everyone working on CFA related documents
     5% should find useful. So mostly programming language related tools.
    46%
    57% Internal commands are prefixed with "\cfalab@".
    … …  
    1012
    1113% Other packages required.
     14%
     15% Access to new basic LaTeX tools and other low level commands.
    1216\RequirePackage{etoolbox}
     17% Code formatting tools and environments.
    1318\RequirePackage{listings}
     19% Automatically adds spaces.
    1420\RequirePackage{xspace}
    1521
    16 % Symbols: All symbols are zero argument robust commands with special rules
    17 % about the space following the c.s. token. Normally the space might be
    18 % re-added according to the rules of the xspace package. They may be followed
    19 % by a star (which the command will consume) to disable this behaviour.
     22% Tip for commands that end with \xspace: if the default is not correct then
     23% follow the command with {} to disable \xspace, use '{} ' to force add a
     24% space and '{}<whatever-follows>' to force remove one.
     25%
     26% \CFA
     27% Cforall with the forall symbol.
     28\newrobustcmd\CFA{\textsf{C\raisebox{\depth}{\rotatebox{180}{A}}}\xspace}
     29% \Cpp[<std>]
     30% C++ symbol name. You may optionally provide <std> to specify a standard.
     31\newrobustcmd\Cpp[1][\xspace]{C++#1}
    2032
    21 % \newsymbolcmd{<command>}{<replacement text>}
    22 %     Defines <command> to be a symbol that has the given <replacement text>.
    23 \newrobustcmd*\newsymbolcmd[2]{\newrobustcmd{#1}{\cfalab@symbol{#2}}}
    24 \def\cfalab@symbol#1{\@ifnextchar*{#1\cfalab@eatstar}{#1\xspace}}
    25 \def\cfalab@eatstar*{}
    26 
    27 % Cforall with the forall symbol.
    28 \newsymbolcmd\CFA{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}}
    29 % C++ with kerning. (No standard number support.)
    30 \newsymbolcmd\CPP{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}}
    31 
    32 % This is executed very early in the \begin{document} code.
     33% This is executed very early in the \begin{document} code, before the
     34% document's contents but after packages are loaded.
    3335\AtEndPreamble{
    3436  \@ifpackageloaded{hyperref}{
    … …  
    3638    \pdfstringdefDisableCommands{
    3739      \def\CFA{CFA}
    38       \def\CPP{C++}
     40      \def\Cpp{C++}
     41      \def\lstinline{}
     42      \def\code#1#2{#2}
    3943    }
    4044  }{}
    4145}
     46
     47% \colour{<colour>}{<text>}
     48% Just \color but using the LaTeX style instead of TeX style command.
     49\newcommand*\colour[2]{{\color{#1}#2}}
     50
     51% \code{<language>}{<code>}
     52% Use the listings package to format the snipit of <code> in <language>.
     53\newrobustcmd*\code[2]{\lstinline[language=#1]{#2}}
     54
     55% \begin{cfa}[<options>]
     56% \end{cfa}
     57% Use the listings package to format a block of CFA code.
     58% Extra listings options can be passed in as an optional argument.
     59\lstnewenvironment{cfa}[1][]{\lstset{language=CFA}\lstset{#1}}{}
     60
     61% \settextunderscore{(new|old)}
     62% Redefines the underscore either as a new repersentation or the old one.
     63% Not that some other packages (ex. hyperref) can override this. Set it up
     64% after loading them.
     65\let\cfalab@textunderscore@old=\textunderscore
     66\newcommand\cfalab@textunderscore@new{%
     67    \leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
     68\newcommand\settextunderscore[1]{%
     69    \renewcommand\textunderscore{\csuse{cfalab@textunderscore@#1}}}
    4270
    4371% The CFA listings language. Based off of ANCI C and including GCC extensions.
    … …  
    6189\lstset{defaultdialect={[UW]CFA}}
    6290
    63 % The cfalab style defines some common settings useful in different languages.
    64 \lstdefinestyle{cfalab}{%
    65     columns=fullflexible,
    66     basicstyle=\linespread{0.9}\tt,
    67     stringstyle=\tt,
     91% Create an internal paragraph indent amount. This is used internally to
     92% mimic the standard indent even when it has been overriden in the document.
     93\newlength\cfalab@parindent
     94\deflength\cfalab@parindent{\parindent}
     95
     96% The cfacommon style has many useful defaults for CFA and other types of
     97% code. Use the listings option "style=cfacommon" to load them.
     98\lstdefinestyle{cfacommon}{
     99  columns=fullflexible,
     100  basicstyle=\linespread{0.9}\sf,
     101  stringstyle=\tt,
     102  tabsize=5,
     103  % Indent code to paragraph indentation.
     104  xleftmargin=\cfalab@parindent,
     105  % Allow ASCII characters in the range 128-255.
     106  extendedchars=true,
     107  % This allows you to use "math mode" to insert LaTeX into the code.
     108  % Use \( and \) if you need to insert math mode inside that code.
     109  escapechar=\$,
     110  % Disable LaTeX math escape in CFA code $...$
     111  mathescape=false,
     112  keepspaces=true,
     113  % Do not show spaces with cup.
     114  showstringspaces=false,
     115  % Show blank lines at end of code.
     116  showlines=true,
     117  % Spacing above/below code block.
     118  aboveskip=4pt,belowskip=0pt,
     119  numberstyle=\footnotesize\sf,
     120  % Replace/adjust listing characters that look bad in sanserif.
     121  literate={-}{\makebox[1ex][c]{\raisebox{0.7ex}{\rule{0.75ex}{0.1ex}}}}1
     122    {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
     123    {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     124    {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2
     125    {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2,
    68126}
    69127
    70 % \code*[<escape character>]{<code>}
    71 %     Use the listings package to format a snipit of <code>.
    72 %     The <escape character> must be a character that does not appear in
    73 %     <code> and defaults to a backtick.
    74 \newcommand*\codeC[2][\`]{\lstinline[language=C]#1#2#1}
    75 \newcommand*\codeCFA[2][\`]{\lstinline[language=CFA]#1#2#1}
     128% common.tex Compatablity ===================================================
     129% Below this line is for compatability with the old common.tex file.
    76130
    77 % \settextunderscore{(new|old)}
    78 %     Redefines the underscore either as a new repersentation or the old one.
    79 %     Not that some other packages (ex. hyperref) can override this. Set it
    80 %     up after loading them.
    81 \let\cfalab@textunderscore@old=\textunderscore
    82 \newcommand\cfalab@textunderscore@new{%
    83     \leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    84 \newcommand\settextunderscore[1]{%
    85     \renewcommand\textunderscore{\csuse{cfalab@textunderscore@#1}}}
     131% Backwards compatable way to activate the cfacommon style.
     132\newcommand{\CFAStyle}{\lstset{style=cfacommon}}
     133
     134% A couple of abbreviations are provided. Just ones someone liked.
     135%
     136% Abbreviation formatting commands (renew to customize):
     137\newcommand{\abbrevFont}{\textit}
     138%
     139% Abbreviations that, if not followed by a comma or colon, add a comma.
     140\newrobustcmd*\cfalab@abbrev@comma{%
     141  \@ifnextchar{,}{}{\@ifnextchar{:}{}{,\xspace}}}
     142\providerobustcmd*\eg{\abbrevFont{e}.\abbrevFont{g}.\cfalab@abbrev@comma}
     143\providerobustcmd*\ie{\abbrevFont{i}.\abbrevFont{e}.\cfalab@abbrev@comma}
     144%
     145% Abbreviations that, if not followed by a period, add a period.
     146\newrobustcmd*\cfalab@abbrev@period{\@ifnextchar{.}{}{.\xspace}}
     147\providerobustcmd*\etc{\abbrevFont{etc}\cfalab@abbrev@period}
     148\providerobustcmd*\etal{\abbrevFont{et}~\abbrevFont{al}\cfalab@abbrev@period}
     149\providerobustcmd*\viz{\abbrevFont{viz}\cfalab@abbrev@period}
    86150
    87151\endinput

  • doc/theses/andrew_beach_MMath/existing.tex

    r5407cdc r8d66610  
    1616to be defined~\cite{Moss18}.
    1717\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$
     18char i; int i; double i;
     19int f(); double f();
     20void g( int ); void g( double );
    2121\end{cfa}
    2222This feature requires name mangling so the assembly symbols are unique for
    … …  
    2626mangling is:
    2727\begin{cfa}
    28 // name mangling
     28// name mangling on by default
    2929int i; // _X1ii_1
    30 @extern "C"@ {  // no name mangling
     30extern "C" {  // disables name mangling
    3131        int j; // j
    32         @extern "Cforall"@ {  // name mangling
     32        extern "Cforall" {  // enables name mangling
    3333                int k; // _X1ki_1
    3434        }
    35         // no name mangling
    36 }
    37 // name mangling
     35        // revert to no name mangling
     36}
     37// revert to name mangling
    3838\end{cfa}
    3939Both forms of @extern@ affect all the declarations within their nested lexical
    … …  
    5050\begin{cfa}
    5151int i, j;
    52 int @&@ ri = i, @&&@ rri = ri;
     52int & ri = i, && rri = ri;
    5353rri = 3;  // auto-dereference assign to i
    54 @&@ri = @&@j; // rebindable
     54&ri = &j; // rebindable
    5555ri = 5;   // assign to j
    5656\end{cfa}
    … …  
    6464
    6565In general, operator names in \CFA are constructed by bracketing an operator
    66 token with @?@, which indicates the position of 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 (@?++@).
     66token with @?@, which indicates the position of the arguments. For example,
     67infixed multiplication is @?*?@ while prefix dereference is @*?@.
     68This syntax make it easy to tell the difference between prefix operations
     69(such as @++?@) and post-fix operations (@?++@).
    7070
    7171The 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.
     72initialization syntax in C. That initialation syntax is also the operator
     73form. \CFA will generate a constructor call each time a variable is declared,
     74passing the initialization arguments to the constructort.
     75\begin{cfa}
     76struct Example { ... };
     77void ?{}(Example & this) { ... }
     78{
     79        Example a;
     80        Example b = {};
     81}
     82void ?{}(Example & this, char first, int num) { ... }
     83{
     84        Example c = {'a', 2};
     85}
     86\end{cfa}
     87Both @a@ and @b@ will be initalized with the first constructor (there is no
     88general way to skip initialation) while @c@ will be initalized with the
     89second.
     90
    7491% 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
     92Similarly destructors use the special name @^?{}@ (the @^@ has no special
     93meaning). They can be called explicatly as well but normally they are
     94implicitly called on a variable when it goes out of scope.
     95\begin{cfa}
     96void ^?{}(Example & this) { ... }
    7997{
    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 \Cpp). It is possible to define constructors/destructors for
    91 basic and existing types (unlike \Cpp).
     98    Example d;
     99} // <- implicit destructor call
     100\end{cfa}
     101No operator name is restricted in what function signatures they may be bound
     102to although most of the forms cannot be called in operator form. Some
     103``near-misses" will generate warnings.
     104
     105Whenever a type is defined, \CFA will create a default zero-argument
     106constructor, a copy constructor, a series of argument-per-field constructors
     107and a destructor. All user constructors are defined after this.
     108Because operators are never part of the type definition they may be added
     109at any time, including on built-in types.
    92110
    93111\section{Polymorphism}
    … …  
    105123works on any type @T@:
    106124\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}
     125forall( T ) T identity( T val ) { return val; }
     126int forty_two = identity( 42 );
     127char capital_a = identity( 'A' );
     128\end{cfa}
     129Each use of a polymorphic declaration will resolve its polymorphic parameters
     130(in this case, just @T@) to concrete types (@int@ in the first use and @char@
     131in the second).
    110132
    111133To allow a polymorphic function to be separately compiled, the type @T@ must be
    … …  
    115137types used in a function, \eg:
    116138\begin{cfa}
    117 forall( T @| { void do_once(T); }@) // assertion
     139forall( T | { void do_once(T); })
    118140void do_twice(T value) {
    119141        do_once(value);
    120142        do_once(value);
    121143}
    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.
     144\end{cfa}
    128145
    129146A polymorphic function can be used in the same way as a normal function.  The
    … …  
    132149all the variables replaced with the concrete types from the arguments) is
    133150defined at a call site.
     151\begin{cfa}
     152void do_once(int i) { ... }
     153int i;
     154do_twice(i);
     155\end{cfa}
     156Any object with a type fulfilling the assertion may be passed as an argument to
     157a @do_twice@ call.
    134158
    135159Note, a function named @do_once@ is not required in the scope of @do_twice@ to
    … …  
    138162call.
    139163\begin{cfa}
    140 void do_once(double y) { ... } // global
     164void do_once(double y) { ... }
    141165int quadruple(int x) {
    142         void do_once(int y) { y = y * 2; } // local
    143         do_twice(x); // using local "do_once"
     166        void do_once(int y) { y = y * 2; }
     167        do_twice(x);
    144168        return x;
    145169}
    … …  
    150174function. The matched assertion function is then passed as a function pointer
    151175to @do_twice@ and called within it.
     176The global definition of @do_once@ is ignored.
    152177
    153178To avoid typing long lists of assertions, constraints can be collect into
    … …  
    161186and the @forall@ list in the previous example is replaced with the trait.
    162187\begin{cfa}
    163 forall(dtype T | @done_once(T)@)
     188forall(dtype T | done_once(T))
    164189\end{cfa}
    165190In general, a trait can contain an arbitrary number of assertions, both
    … …  
    172197declarations instead of parameters, returns, and local variable declarations.
    173198\begin{cfa}
    174 forall(dtype @T@)
     199forall(dtype T)
    175200struct node {
    176         node(@T@) * next;  // generic linked node
    177         @T@ * data;
    178 }
    179 node(@int@) inode;
    180 \end{cfa}
    181 The generic type @node(T)@ is an example of a polymorphic-type usage.  Like \Cpp
    182 template usage, a polymorphic-type usage must specify a type parameter.
     201        node(T) * next;  // generic linked node
     202        T * data;
     203}
     204node(int) inode;
     205\end{cfa}
     206The generic type @node(T)@ is an example of a polymorphic type usage.  Like \Cpp
     207template usage, a polymorphic type usage must specify a type parameter.
    183208
    184209There are many other polymorphism features in \CFA but these are the ones used
    … …  
    219244Each coroutine has a @main@ function, which takes a reference to a coroutine
    220245object and returns @void@.
    221 \begin{cfa}[numbers=left]
    222 void main(@CountUp & this@) { // argument matches trait is_coroutine
    223         unsigned int up = 0;  // retained between calls
    224         while (true) {
    225                 next = up; // make "up" available outside function
    226                 @suspend;@$\label{suspend}$
    227                 up += 1;
     246\begin{cfa}
     247void main(CountUp & this) {
     248    for (unsigned int next = 0 ; true ; ++next) {
     249                next = up;
     250                suspend;$\label{suspend}$
    228251        }
    229252}
    … …  
    254277@mutex@.
    255278\begin{cfa}
    256 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
     279void example(MonitorA & mutex argA, MonitorB & mutex argB);
    257280\end{cfa}
    258281When the function is called, it implicitly acquires the monitor lock for all of

  • doc/theses/andrew_beach_MMath/features.tex

    r5407cdc r8d66610  
    2020\subparagraph{Raise}
    2121The raise is the starting point for exception handling. It marks the beginning
    22 of exception handling by \newterm{raising} an excepion, which passes it to
     22of exception handling by raising an excepion, which passes it to
    2323the EHM.
    2424
    2525Some well known examples include the @throw@ statements of \Cpp and Java and
    26 the \codePy{raise} statement from Python. In real systems a raise may preform
    27 some other work (such as memory management) but for the purposes of this
    28 overview that can be ignored.
     26the \code{Python}{raise} statement from Python. In real systems a raise may
     27preform some other work (such as memory management) but for the
     28purposes of this overview that can be ignored.
    2929
    3030\subparagraph{Handle}
    … …  
    9393A handler labelled with any given exception can handle exceptions of that
    9494type or any child type of that exception. The root of the exception hierarchy
    95 (here \codeC{exception}) acts as a catch-all, leaf types catch single types
     95(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
    9696and the exceptions in the middle can be used to catch different groups of
    9797related exceptions.
    … …  
    101101between different sub-hierarchies.
    102102This design is used in \CFA even though it is not a object-orientated
    103 language using different tools to create the hierarchy.
     103language; so different tools are used to create the hierarchy.
    104104
    105105% Could I cite the rational for the Python IO exception rework?
    … …  
    123123\section{Virtuals}
    124124Virtual types and casts are not part of \CFA's EHM nor are they required for
    125 any EHM. But \CFA uses a hierarchial system of exceptions and this feature
    126 is leveraged to create that.
    127 
    128 % Maybe talk about why the virtual system is so minimal.
    129 % Created for but not a part of the exception system.
     125any EHM.
     126However the \CFA uses a hierarchy built with the virtual system as the basis
     127for exceptions and exception matching.
     128
     129The virtual system would have ideally been part of \CFA before the work
     130on exception handling began, but unfortunately it was not.
     131Because of this only the features and framework needed for the EHM were
     132designed and implemented. Other features were considered to ensure that
     133the structure could accomidate other desirable features but they were not
     134implemented.
     135The rest of this section will only discuss the finalized portion of the
     136virtual system.
    130137
    131138The virtual system supports multiple ``trees" of types. Each tree is
    … …  
    143150It is important to note that these are virtual members, not virtual methods
    144151of object-orientated programming, and can be of any type.
    145 However, since \CFA has function pointers and they are allowed, virtual
    146 members can be used to mimic virtual methods.
     152\CFA still supports virtual methods as a special case of virtual members.
     153Function pointers that take a pointer to the virtual type will be modified
     154with each level of inheritance so that refers to the new type.
     155This means an object can always be passed to a function in its virtual table
     156as if it were a method.
    147157
    148158Each virtual type has a unique id.
    … …  
    175185While much of the virtual infrastructure is created, it is currently only used
    176186internally for exception handling. The only user-level feature is the virtual
    177 cast, which is the same as the \Cpp \lstinline[language=C++]|dynamic_cast|.
     187cast, which is the same as the \Cpp \code{C++}{dynamic_cast}.
    178188\label{p:VirtualCast}
    179189\begin{cfa}
    … …  
    197207\begin{cfa}
    198208trait is_exception(exceptT &, virtualT &) {
    199         virtualT const & get_exception_vtable(exceptT *);
     209        // Numerous imaginary assertions.
    200210};
    201211\end{cfa}
    202212The trait is defined over two types, the exception type and the virtual table
    203 type. This should be one-to-one: each exception type has only one virtual
    204 table type and vice versa. The only assertion in the trait is
    205 @get_exception_vtable@, which takes a pointer of the exception type and
    206 returns a reference to the virtual table type instance.
    207 
    208 % TODO: This section, and all references to get_exception_vtable, are
    209 % out-of-data. Perhaps wait until the update is finished before rewriting it.
    210 The function @get_exception_vtable@ is actually a constant function.
    211 Regardless of the value passed in (including the null pointer) it should
    212 return a reference to the virtual table instance for that type.
    213 The reason it is a function instead of a constant is that it make type
    214 annotations easier to write as you can use the exception type instead of the
    215 virtual table type; which usually has a mangled name.
    216 % Also \CFA's trait system handles functions better than constants and doing
    217 % it this way reduce the amount of boiler plate we need.
     213type. Each exception type should have but a single virtual table type.
     214Now there are no actual assertions in this trait because the trait system
     215actually can't express them (adding such assertions would be part of
     216completing the virtual system). The imaginary assertions would probably come
     217from a trait defined by the virtual system, and state that the exception type
     218is a virtual type, is a decendent of @exception_t@ (the base exception type)
     219and note its virtual table type.
    218220
    219221% I did have a note about how it is the programmer's responsibility to make
    … …  
    235237Both traits ensure a pair of types are an exception type and its virtual table
    236238and defines one of the two default handlers. The default handlers are used
    237 as fallbacks and are discussed in detail in \VRef{s:ExceptionHandling}.
     239as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
    238240
    239241However, all three of these traits can be tricky to use directly.
    … …  
    351353for particular exception type.
    352354The global default termination handler performs a cancellation
    353 \see{\VRef{s:Cancellation}} on the current stack with the copied exception.
     355(see \vref{s:Cancellation}) on the current stack with the copied exception.
    354356
    355357\subsection{Resumption}
    … …  
    426428
    427429\subsubsection{Resumption Marking}
     430\label{s:ResumptionMarking}
    428431A key difference between resumption and termination is that resumption does
    429432not unwind the stack. A side effect that is that when a handler is matched
    … …  
    472475The symmetry between resumption termination is why this pattern was picked.
    473476Other patterns, such as marking just the handlers that caught, also work but
    474 lack the symmetry means there are less rules to remember.
     477lack the symmetry means there are more rules to remember.
    475478
    476479\section{Conditional Catch}
    … …  
    557560\end{cfa}
    558561If there are further handlers after this handler only the first version will
    559 check them. If multiple handlers on a single try block could handle the same
    560 exception the translations get more complex but they are equivilantly
     562check them. If multiple handlers on a single try block that could handle the
     563same exception the translations get more complex but they are equivilantly
    561564powerful.
    562565
    … …  
    633636and the current stack is
    634637unwound. After that it depends one which stack is being cancelled.
    635 \begin{description}
    636 \item[Main Stack:]
     638
     639\paragraph{Main Stack}
    637640The main stack is the one used by the program main at the start of execution,
    638641and is the only stack in a sequential program.
    … …  
    645648to, so it would have be explicitly managed.
    646649
    647 \item[Thread Stack:]
     650\paragraph{Thread Stack}
    648651A thread stack is created for a \CFA @thread@ object or object that satisfies
    649652the @is_thread@ trait.
    … …  
    671674Also you can always add an explicit join if that is the desired behaviour.
    672675
    673 \item[Coroutine Stack:]
     676\paragraph{Coroutine Stack}
    674677A coroutine stack is created for a @coroutine@ object or object that
    675678satisfies the @is_coroutine@ trait.
    … …  
    685688(in terms of coroutine state) called resume on this coroutine, so the message
    686689is passed to the latter.
    687 \end{description}

  • doc/theses/andrew_beach_MMath/future.tex

    r5407cdc r8d66610  
    110110\section{Zero-Cost Try}
    111111\CFA does not have zero-cost try-statements because the compiler generates C
    112 code rather than assembler code \see{\VPageref{p:zero-cost}}. When the compiler
     112code rather than assembler code (see \vpageref{p:zero-cost}). When the compiler
    113113does create its own assembly (or LLVM byte-code), then zero-cost try-statements
    114114are possible. The downside of zero-cost try-statements is the LSDA complexity,

  • doc/theses/andrew_beach_MMath/implement.tex

    r5407cdc r8d66610  
    99% Virtual table rules. Virtual tables, the pointer to them and the cast.
    1010While 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.
     11cast (see the virtual cast feature \vpageref{p:VirtualCast}),
     12substantial structure is required to support it,
     13and provide features for exception handling and the standard library.
    1414
    1515\subsection{Virtual Type}
    16 Virtual types only have one change to their structure, the addition of a
    17 pointer to the virtual table. This is always the first field so that
    18 if it is cast to a supertype the field's location is still known.
    19 
    20 This field is set as part of all new generated constructors.
    21 \todo{They only come as part exceptions and don't work.}
    22 After the object is created the field is constant.
    23 
    24 However it can be read from, internally it is just a regular field called
    25 @virtual_table@. Dereferencing it gives the virtual table and access to the
    26 type's virtual members.
     16Virtual types only have one change to their structure: the addition of a
     17pointer to the virtual table, which is called the \emph{virtual-table pointer}.
     18Internally, the field is called @virtual_table@.
     19The field is fixed after construction. It is always the first field in the
     20structure so that its location is always known.
     21\todo{Talk about constructors for virtual types (after they are working).}
     22
     23This is what binds an instance of a virtual type to a virtual table. This
     24pointer can be used as an identity check. It can also be used to access the
     25virtual table and the virtual members there.
     26
     27\subsection{Type Id}
     28Every virtual type has a unique id.
     29Type ids can be compared for equality (the types reperented are the same)
     30or used to access the type's type information.
     31The type information currently is only the parent's type id or, if the
     32type has no parent, zero.
     33
     34The id's are implemented as pointers to the type's type information instance.
     35Derefencing the pointer gets the type information.
     36By going back-and-forth between the type id and
     37the type info one can find every ancestor of a virtual type.
     38It also pushes the issue of creating a unique value (for
     39the type id) to the problem of creating a unique instance (for type
     40information) which the linker can solve.
     41
     42Advanced linker support is required because there is no place that appears
     43only once to attach the type information to. There should be one structure
     44definition but it is included in multiple translation units. Each virtual
     45table definition should be unique but there are an arbitrary number of thoses.
     46So the special section prefix \texttt{.gnu.linkonce} is used.
     47With a unique suffix (making the entire section name unique) the linker will
     48remove multiple definition making sure only one version exists after linking.
     49Then it is just a matter of making sure there is a unique name for each type.
     50
     51This is done in three phases.
     52The first phase is to generate a new structure definition to store the type
     53information. The layout is the same in each case, just the parent's type id,
     54but the types are changed.
     55The structure's name is change, it is based off the virtual type's name, and
     56the type of the parent's type id.
     57If the virtual type is polymorphic then the type information structure is
     58polymorphic as well, with the same polymorphic arguments.
     59
     60The second phase is to generate an instance of the type information with a
     61almost unique name, generated by mangling the virtual type name.
     62
     63The third phase is implicit with \CFA's overloading scheme. \CFA mangles
     64names with type information so that all of the symbols exported to the linker
     65are unique even if in \CFA code they are the same. Having two declarations
     66with the same name and same type is forbidden because it is impossible for
     67overload resolution to pick between them. This is why a unique type is
     68generated for each virtual type.
     69Polymorphic information is included in this mangling so polymorphic
     70types will have seperate instances for each set of polymorphic arguments.
     71
     72\begin{cfa}
     73struct TYPE_ID_TYPE {
     74        PARENT_ID_TYPE const * parent;
     75};
     76
     77__attribute__((cfa_linkonce))
     78TYPE_ID_TYPE const TYPE_ID_NAME = {
     79        &PARENT_ID_NAME,
     80};
     81\end{cfa}
     82
     83\subsubsection{cfa\_linkonce Attribute}
     84Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
     85This attribute can be put on an object or function definition
     86(any global declaration with a name and a type).
     87This allows you to define that object or function multiple times.
     88All definitions should have the link-once attribute on them and all should
     89be identical.
     90
     91The simplist way to use it is to put a definition in a header where the
     92forward declaration would usually go.
     93This is how it is used for type-id instances. There was is no unique location
     94associated with a type except for the type definition which is in a header.
     95This allows the unique type-id object to be generated there.
     96
     97Internally @cfa_linkonce@ removes all @section@ attributes
     98from the declaration (as well as itself) and replaces them with
     99@section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the
     100mangled name of the object.
     101The prefix \texttt{.gnu.linkonce} in section names is recognized by the
     102linker. If two of these sections with the same name, including everything
     103that comes after the special prefix, then only one will be used and the other
     104will be discarded.
    27105
    28106\subsection{Virtual Table}
    29 Every time a virtual type is defined the new virtual table type must also be
    30 defined.
    31 
    32 The unique instance is important because the address of the virtual table
    33 instance is used as the identifier for the virtual type. So a pointer to the
    34 virtual table and the ID for the virtual type are interchangable.
    35 \todo{Unique instances might be going so we will have to talk about the new
    36 system instead.}
    37 
    38 The first step in putting it all together is to create the virtual table type.
    39 The virtual table type is just a structure and can be described in terms of
    40 its fields. The first field is always the parent type ID (or a pointer to
    41 the parent virtual table) or 0 (the null pointer).
    42 Next are other fields on the parent virtual table are repeated.
    43 Finally are the fields used to store any new virtual members of the new
    44 The virtual type
    45 
    46 The virtual system is accessed through a private constant field inserted at the
    47 beginning of every virtual type, called the virtual-table pointer. This field
    48 points at a type's virtual table and is assigned during the object's
    49 construction. The address of a virtual table acts as the unique identifier for
    50 the virtual type, and the first field of a virtual table is a pointer to the
    51 parent virtual-table or @0p@. The remaining fields are duplicated from the
    52 parent tables in this type's inheritance chain, followed by any fields this type
    53 introduces. Parent fields are duplicated so they can be changed (all virtual
    54 members are overridable), so that references to the dispatched type
    55 are replaced with the current virtual type.
    56 % These are always taken by pointer or reference.
    57 
    58 % Simple ascii diragram:
    59 \begin{verbatim}
    60 parent_pointer  \
    61 parent_field0   |
    62 ...             | Same layout as parent.
    63 parent_fieldN   /
     107Each virtual type has a virtual table type that stores its type id and
     108virtual members.
     109Each virtual type instance is bound to a table instance that is filled with
     110the values of virtual members.
     111Both the layout of the fields and their value are decided by the rules given
     112below.
     113
     114The layout always comes in three parts.
     115The first section is just the type id at the head of the table. It is always
     116there to ensure that
     117The second section are all the virtual members of the parent, in the same
     118order as they appear in the parent's virtual table. Note that the type may
     119change slightly as references to the ``this" will change. This is limited to
     120inside pointers/references and via function pointers so that the size (and
     121hence the offsets) are the same.
     122The third section is similar to the second except that it is the new virtual
     123members introduced at this level in the hierarchy.
     124
     125\begin{figure}
     126\begin{cfa}
     127type_id
     128parent_field0
     129...
     130parent_fieldN
    64131child_field0
    65132...
    66133child_fieldN
    67 \end{verbatim}
    68 \todo{Refine the diagram}
    69 
    70 % For each virtual type, a virtual table is constructed. This is both a new type
    71 % and an instance of that type. Other instances of the type could be created
    72 % but the system doesn't use them. So this section will go over the creation of
    73 % the type and the instance.
    74 
    75 A virtual table is created when the virtual type is created. The name of the
    76 type is created by mangling the name of the base type. The name of the instance
    77 is also generated by name mangling. The fields are initialized automatically.
    78 The parent field is initialized by getting the type of the parent field and
    79 using that to calculate the mangled name of the parent's virtual table type.
    80 There are two special fields that are included like normal fields but have
    81 special initialization rules: the @size@ field is the type's size and is
    82 initialized with a @sizeof@ expression, the @align@ field is the type's
    83 alignment and uses an @alignof@ expression. The remaining fields are resolved
    84 to a name matching the field's name and type using the normal visibility and
    85 overload resolution rules of the type system.
    86 
    87 These operations are split up into several groups depending on where they take
    88 place which varies for monomorphic and polymorphic types. The first devision is
    89 between the declarations and the definitions. Declarations, such as a function
    90 signature or a aggregate's name, must always be visible but may be repeated in
    91 the form of forward declarations in headers. Definitions, such as function
    92 bodies and a aggregate's layout, can be separately compiled but must occur
    93 exactly once in a source file.
    94 
    95 \begin{sloppypar}
    96 The declarations include the virtual type definition and forward declarations
    97 of the virtual table instance, constructor, message function and
    98 @get_exception_vtable@. The definition includes the storage and initialization
    99 of the virtual table instance and the bodies of the three functions.
    100 \end{sloppypar}
    101 
    102 Monomorphic instances put all of these two groups in one place each.
    103 Polymorphic instances also split out the core declarations and definitions from
    104 the per-instance information. The virtual table type and most of the functions
    105 are polymorphic so they are all part of the core. The virtual table instance
    106 and the @get_exception_vtable@ function.
    107 
    108 \begin{sloppypar}
     134\end{cfa}
     135\caption{Virtual Table Layout}
     136\label{f:VirtualTableLayout}
     137\todo*{Improve the Virtual Table Layout diagram.}
     138\end{figure}
     139
     140The first and second sections together mean that every virtual table has a
     141prefix that has the same layout and types as its parent virtual table.
     142This, combined with the fixed offset to the virtual table pointer, means that
     143for any virtual type it doesn't matter if we have it or any of its
     144descendants, it is still always safe to access the virtual table through
     145the virtual table pointer.
     146From there it is safe to check the type id to identify the exact type of the
     147underlying object, access any of the virtual members and pass the object to
     148any of the method-like virtual members.
     149
     150When a virtual table is declared the user decides where to declare it and its
     151name. The initialization of the virtual table is entirely automatic based on
     152the context of the declaration.
     153
     154The type id is always fixed, each virtual table type will always have one
     155exactly one possible type id.
     156The virtual members are usually filled in by resolution. The best match for
     157a given name and type at the declaration site is filled in.
     158There are two exceptions to that rule: the @size@ field is the type's size
     159and is set to the result of a @sizeof@ expression, the @align@ field is the
     160type's alignment and similarly uses an @alignof@ expression.
     161
     162\subsubsection{Concurrency Integration}
    109163Coroutines and threads need instances of @CoroutineCancelled@ and
    110164@ThreadCancelled@ respectively to use all of their functionality. When a new
    … …  
    112166the instance is created as well. The definition of the virtual table is created
    113167at the definition of the main function.
    114 \end{sloppypar}
     168
     169\begin{figure}
     170\begin{cfa}
     171coroutine Example {
     172        // fields
     173}
     174\end{cfa}
     175
     176\begin{cfa}
     177__attribute__((cfa_linkonce))
     178struct __cfatid_struct_CoroutineCancelled(Example)
     179                __cfatid_CoroutineCancelled = {
     180        &EXCEPTION_TYPE_ID,
     181};
     182extern CoroutineCancelled_vtable _default_vtable_object_declaration;
     183extern CoroutineCancelled_vtable & _default_vtable;
     184\end{cfa}
     185
     186\begin{cfa}
     187void main(Example & this) {
     188        // body
     189}
     190\end{cfa}
     191
     192\begin{cfa}
     193CoroutineCancelled_vtable _default_vtable_object_declaration = {
     194        __cfatid_CoroutineCancelled,
     195        // Virtual member initialization.
     196};
     197
     198CoroutineCancelled_vtable & _default_vtable =
     199        &_default_vtable_object_declaration;
     200\end{cfa}
     201\caption{Concurrency Transformations}
     202\label{f:ConcurrencyTransformations}
     203\end{figure}
     204\todo{Improve Concurrency Transformations figure.}
    115205
    116206\subsection{Virtual Cast}
    … …  
    119209% The C-cast is just to make sure the generated code is correct so the rest of
    120210% the section is about that function.
    121 The function is
     211The function is implemented in the standard library and has the following
     212signature:
    122213\begin{cfa}
    123214void * __cfa__virtual_cast(
    124         struct __cfa__parent_vtable const * parent,
    125         struct __cfa__parent_vtable const * const * child );
    126 \end{cfa}
    127 and it is implemented in the standard library. The structure reperents the
    128 head of a vtable which is the pointer to the parent virtual table. The
    129 @parent@ points directly at the parent type virtual table while the @child@
    130 points at the object of the (possibe) child type.
    131 
    132 In terms of the virtual cast expression, @parent@ comes from looking up the
    133 type being cast to and @child@ is the result of the expression being cast.
    134 Because the complier outputs C code, some type C type casts are also used.
    135 The last bit of glue is an map that saves every virtual type the compiler
    136 sees. This is used to check the type used in a virtual cast is a virtual
    137 type and to get its virtual table.
    138 (It also checks for conflicting definitions.)
    139 
    140 Inside the function it is a simple conditional. If the type repersented by
    141 @parent@ is or is an ancestor of the type repersented by @*child@ (it
    142 requires one more level of derefence to pass through the object) then @child@
    143 is returned, otherwise the null pointer is returned.
    144 
    145 The check itself is preformed is a simple linear search. If the child
    146 virtual table or any of its ancestors (which are retreved through the first
    147 field of every virtual table) are the same as the parent virtual table then
    148 the cast succeeds.
     215        struct __cfavir_type_td parent,
     216        struct __cfavir_type_id const * child );
     217\end{cfa}
     218The type id of target type of the virtual cast is passed in as @parent@ and
     219the cast target is passed in as @child@.
     220
     221For C generation both arguments and the result are wrapped with type casts.
     222There is also an internal store inside the compiler to make sure that the
     223target type is a virtual type.
     224% It also checks for conflicting definitions.
     225
     226The virtual cast either returns the original pointer as a new type or null.
     227So the function just does the parent check and returns the approprate value.
     228The parent check is a simple linear search of child's ancestors using the
     229type information.
    149230
    150231\section{Exceptions}
    … …  
    161242
    162243Stack unwinding is the process of removing stack frames (activations) from the
    163 stack. On function entry and return, unwinding is handled directly by the code
    164 embedded in the function. Usually, the stack-frame size is known statically
    165 based on parameter and local variable declarations. For dynamically-sized
    166 local variables, a runtime computation is necessary to know the frame
    167 size. Finally, a function's frame-size may change during execution as local
    168 variables (static or dynamic sized) go in and out of scope.
     244stack. On function entry and return, unwinding is handled directly by the
     245call/return code embedded in the function.
     246In many cases the position of the instruction pointer (relative to parameter
     247and local declarations) is enough to know the current size of the stack
     248frame.
     249
     250Usually, the stack-frame size is known statically based on parameter and
     251local variable declarations. Even with dynamic stack-size the information
     252to determain how much of the stack has to be removed is still contained
     253within the function.
    169254Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
    170255bumping the hardware stack-pointer up or down as needed.
    171 
    172 Unwinding across multiple stack frames is more complex because individual stack
    173 management code associated with each frame is bypassed. That is, the location
    174 of a function's frame-management code is largely unknown and dispersed
    175 throughout the function, hence the current frame size managed by that code is
    176 also unknown. Hence, code unwinding across frames does not have direct
    177 knowledge about what is on the stack, and hence, how much of the stack needs to
    178 be removed.
    179 
    180 % At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
    181 % move the top of the stack, discarding everything on the stack above a certain
    182 % point. However this ignores all the cleanup code that should be run when
    183 % certain sections of the stack are removed (for \CFA these are from destructors
    184 % and finally clauses) and also requires that the point to which the stack is
    185 % being unwound is known ahead of time. libunwind is used to address both of
    186 % these problems.
     256Constructing/destructing values on the stack takes longer put in terms of
     257figuring out what needs to be done is of similar complexity.
     258
     259Unwinding across multiple stack frames is more complex because that
     260information is no longer contained within the current function.
     261With seperate compilation a function has no way of knowing what its callers
     262are so it can't know how large those frames are.
     263Without altering the main code path it is also hard to pass that work off
     264to the caller.
    187265
    188266The traditional unwinding mechanism for C is implemented by saving a snap-shot
    … …  
    191269reseting to a snap-shot of an arbitrary but existing function frame on the
    192270stack. It is up to the programmer to ensure the snap-shot is valid when it is
    193 reset, making this unwinding approach fragile with potential errors that are
    194 difficult to debug because the stack becomes corrupted.
    195 
    196 However, many languages define cleanup actions that must be taken when objects
    197 are deallocated from the stack or blocks end, such as running a variable's
    198 destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
    199 requires walking the stack and checking each stack frame for these potential
    200 actions.
    201 
    202 For exceptions, it must be possible to walk the stack frames in search of @try@
    203 statements to match and execute a handler. For termination exceptions, it must
    204 also be possible to unwind all stack frames from the throw to the matching
    205 catch, and each of these frames must be checked for cleanup actions. Stack
    206 walking is where most of the complexity and expense of exception handling
    207 appears.
     271reset and that all required clean-up from the unwound stacks is preformed.
     272This approach is fragile and forces a work onto the surounding code.
     273
     274With respect to that work forced onto the surounding code,
     275many languages define clean-up actions that must be taken when certain
     276sections of the stack are removed. Such as when the storage for a variable
     277is removed from the stack or when a try statement with a finally clause is
     278(conceptually) popped from the stack.
     279None of these should be handled by the user, that would contradict the
     280intention of these features, so they need to be handled automatically.
     281
     282To safely remove sections of the stack the language must be able to find and
     283run these clean-up actions even when removing multiple functions unknown at
     284the beginning of the unwinding.
    208285
    209286One of the most popular tools for stack management is libunwind, a low-level
    … …  
    215292\subsection{libunwind Usage}
    216293Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
    217 provides \CC-style stack-unwinding. Its operation is divided into two phases:
     294provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
    218295search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
    219296stack and decide where unwinding should stop (but no unwinding occurs). The
    … …  
    226303LSDA can contain any information but conventionally it is a table with entries
    227304representing regions of the function and what has to be done there during
    228 unwinding. These regions are bracketed by the instruction pointer. If the
     305unwinding. These regions are bracketed by instruction addresses. If the
    229306instruction pointer is within a region's start/end, then execution is currently
    230307executing in that region. Regions are used to mark out the scopes of objects
    … …  
    238315
    239316The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
    240 attaches its personality function. However, this
     317attaches a personality function to each function.
     318In plain C (which \CFA currently compiles down to) this
    241319flag only handles the cleanup attribute:
    242 \todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive
    243 and that's all I know.}
    244320\begin{cfa}
    245321void clean_up( int * var ) { ... }
    246322int avar __attribute__(( cleanup(clean_up) ));
    247323\end{cfa}
    248 which is used on a variable and specifies a function, in this case @clean_up@,
    249 run when the variable goes out of scope.
    250 The function is passed a pointer to the object being removed from the stack
    251 so it can be used to mimic destructors.
    252 However, this feature cannot be used to mimic @try@ statements as it cannot
    253 control the unwinding.
     324The attribue is used on a variable and specifies a function,
     325in this case @clean_up@, run when the variable goes out of scope.
     326This is enough to mimic destructors, but not try statements which can effect
     327the unwinding.
     328
     329To get full unwinding support all of this has to be done directly with
     330assembly and assembler directives. Partiularly the cfi directives
     331\texttt{.cfi\_lsda} and \texttt{.cfi\_personality}.
    254332
    255333\subsection{Personality Functions}
    … …  
    268346\end{lstlisting}
    269347The @action@ argument is a bitmask of possible actions:
    270 \begin{enumerate}
     348\begin{enumerate}[topsep=5pt]
    271349\item
    272350@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
    … …  
    291369@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
    292370the cleanup phase and uses a different means to decide when to stop
    293 \see{\VRef{s:ForcedUnwind}}.
     371(see \vref{s:ForcedUnwind}).
    294372\end{enumerate}
    295373
    296374The @exception_class@ argument is a copy of the
    297 \lstinline[language=C]|exception|'s @exception_class@ field.
    298 
    299 The \lstinline[language=C]|exception| argument is a pointer to the user
    300 provided storage object. It has two public fields, the exception class, which
    301 is actually just a number, identifying the exception handling mechanism that
    302 created it, and the cleanup function. The cleanup function is called if
    303 required by the exception.
     375\code{C}{exception}'s @exception_class@ field.
     376This a number that identifies the exception handling mechanism that created
     377the
     378
     379The \code{C}{exception} argument is a pointer to the user
     380provided storage object. It has two public fields: the @exception_class@,
     381which is described above, and the @exception_cleanup@ function.
     382The clean-up function is used by the EHM to clean-up the exception if it
     383should need to be freed at an unusual time, it takes an argument that says
     384why it had to be cleaned up.
    304385
    305386The @context@ argument is a pointer to an opaque type passed to helper
    … …  
    309390that can be passed several places in libunwind. It includes a number of
    310391messages for special cases (some of which should never be used by the
    311 personality function) and error codes but unless otherwise noted the
     392personality function) and error codes. However, unless otherwise noted, the
    312393personality function should always return @_URC_CONTINUE_UNWIND@.
    313394
    … …  
    324405@_URC_END_OF_STACK@.
    325406
    326 Second, when a handler is matched, raise exception continues onto the cleanup
    327 phase.
     407Second, when a handler is matched, raise exception moves to the clean-up
     408phase and walks the stack a second time.
    328409Once again, it calls the personality functions of each stack frame from newest
    329410to oldest. This pass stops at the stack frame containing the matching handler.
    … …  
    338419Forced Unwind is the other central function in libunwind.
    339420\begin{cfa}
    340 _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
     421_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
    341422        _Unwind_Stop_Fn, void *);
    342423\end{cfa}
    … …  
    380461Each stack must have its own exception context. In a sequential \CFA program,
    381462there is only one stack with a single global exception-context. However, when
    382 the library @libcfathread@ is linked, there are multiple stacks where each
     463the library @libcfathread@ is linked, there are multiple stacks and each
    383464needs its own exception context.
    384465
    385 General access to the exception context is provided by function
     466The exception context should be retrieved by calling the function
    386467@this_exception_context@. For sequential execution, this function is defined as
    387468a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
    … …  
    390471
    391472The sequential @this_exception_context@ returns a hard-coded pointer to the
    392 global execption context.
     473global exception context.
    393474The concurrent version adds the exception context to the data stored at the
    394 base of each stack. When @this_exception_context@ is called it retrieves the
     475base of each stack. When @this_exception_context@ is called, it retrieves the
    395476active stack and returns the address of the context saved there.
    396477
    … …  
    399480% catches. Talk about GCC nested functions.
    400481
    401 Termination exceptions use libunwind heavily because it matches the intended
    402 use from \CC exceptions closely. The main complication for \CFA is that the
     482\CFA termination exceptions use libunwind heavily because they match \Cpp
     483\Cpp exceptions closely. The main complication for \CFA is that the
    403484compiler generates C code, making it very difficult to generate the assembly to
    404485form the LSDA for try blocks or destructors.
    … …  
    411492per-exception storage.
    412493
    413 [Quick ASCII diagram to get started.]
     494\begin{figure}
    414495\begin{verbatim}
    415496Fixed Header  | _Unwind_Exception   <- pointer target
    … …  
    420501              V ...
    421502\end{verbatim}
    422 
    423 Exceptions are stored in variable-sized blocks.
    424 The first component is a fixed sized data structure that contains the
     503\caption{Exception Layout}
     504\label{f:ExceptionLayout}
     505\end{figure}
     506\todo*{Convert the exception layout to an actual diagram.}
     507
     508Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
     509The first component is a fixed-sized data structure that contains the
    425510information for libunwind and the exception system. The second component is an
    426511area of memory big enough to store the exception. Macros with pointer arthritic
    … …  
    428513@_Unwind_Exception@ to the entire node.
    429514
    430 All of these nodes are linked together in a list, one list per stack, with the
     515Multipe exceptions can exist at the same time because exceptions can be
     516raised inside handlers, destructors and finally blocks.
     517Figure~\vref{f:MultipleExceptions} shows a program that has multiple
     518exceptions active at one time.
     519Each time an exception is thrown and caught the stack unwinds and the finally
     520clause runs. This will throw another exception (until @num_exceptions@ gets
     521high enough) which must be allocated. The previous exceptions may not be
     522freed because the handler/catch clause has not been run.
     523So the EHM must keep them alive while it allocates exceptions for new throws.
     524
     525\begin{figure}
     526\centering
     527% Andrew: Figure out what these do and give them better names.
     528\newsavebox{\myboxA}
     529\newsavebox{\myboxB}
     530\begin{lrbox}{\myboxA}
     531\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     532unsigned num_exceptions = 0;
     533void throws() {
     534    try {
     535        try {
     536            ++num_exceptions;
     537            throw (Example){table};
     538        } finally {
     539            if (num_exceptions < 3) {
     540                throws();
     541            }
     542        }
     543    } catch (exception_t *) {
     544        --num_exceptions;
     545    }
     546}
     547int main() {
     548    throws();
     549}
     550\end{lstlisting}
     551\end{lrbox}
     552
     553\begin{lrbox}{\myboxB}
     554\begin{lstlisting}
     555\end{lstlisting}
     556\end{lrbox}
     557
     558{\usebox\myboxA}
     559\hspace{25pt}
     560{\usebox\myboxB}
     561
     562\caption{Multiple Exceptions}
     563\label{f:MultipleExceptions}
     564\end{figure}
     565\todo*{Work on multiple exceptions code sample.}
     566
     567All exceptions are stored in nodes which are then linked together in lists,
     568one list per stack, with the
    431569list head stored in the exception context. Within each linked list, the most
    432570recently thrown exception is at the head followed by older thrown
    … …  
    439577exception, the copy function, and the free function, so they are specific to an
    440578exception type. The size and copy function are used immediately to copy an
    441 exception into managed memory. After the exception is handled the free function
    442 is used to clean up the exception and then the entire node is passed to free
    443 so the memory can be given back to the heap.
     579exception into managed memory. After the exception is handled, the free
     580function is used to clean up the exception and then the entire node is
     581passed to free so the memory can be given back to the heap.
    444582
    445583\subsection{Try Statements and Catch Clauses}
    … …  
    454592calls them.
    455593Because this function is known and fixed (and not an arbitrary function that
    456 happens to contain a try statement) this means the LSDA can be generated ahead
     594happens to contain a try statement), the LSDA can be generated ahead
    457595of time.
    458596
    459597Both the LSDA and the personality function are set ahead of time using
    460 embedded assembly. This is handcrafted using C @asm@ statements and contains
     598embedded assembly. This assembly code is handcrafted using C @asm@ statements
     599and contains
    461600enough information for the single try statement the function repersents.
    462601
    … …  
    487626nested functions and all other functions besides @__cfaehm_try_terminate@ in
    488627\CFA use the GCC personality function and the @-fexceptions@ flag to generate
    489 the LSDA. This allows destructors to be implemented with the cleanup attribute.
     628the LSDA.
     629Using this pattern, \CFA implements destructors with the cleanup attribute.
     630
     631\begin{figure}
     632\begin{cfa}
     633try {
     634        // TRY BLOCK
     635} catch (Exception1 * name1 ; check(name1)) {
     636        // CATCH BLOCK 1
     637} catch (Exception2 * name2) {
     638        // CATCH BLOCK 2
     639}
     640\end{cfa}
     641
     642\begin{cfa}
     643void try(void) {
     644        // TRY BLOCK
     645}
     646int match(exception_t * __exception_inst) {
     647        {
     648                Exception1 * name1;
     649                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
     650                        return 1;
     651                }
     652        }
     653        {
     654                Exception2 * name2;
     655                if (name2 = (virtual Exception2 *)__exception_inst) {
     656                        return 2;
     657                }
     658        }
     659        return 0;
     660}
     661void catch(exception_t * __exception_inst, int __handler_index) {
     662        switch (__handler_index) {
     663        case 1:
     664        {
     665                Exception1 * name1 = (virtual Exception1 *)__exception_inst;
     666                // CATCH BLOCK 1
     667        }
     668        return;
     669        case 2:
     670        {
     671                Exception2 * name2 = (virtual Exception2 *)__exception_inst;
     672                // CATCH BLOCK 2
     673        }
     674        return;
     675        }
     676}
     677{
     678        __cfaehm_try_terminate(try, catch, match);
     679}
     680\end{cfa}
     681
     682\caption{Termination Transformation}
     683\label{f:TerminationTransformation}
     684\todo*{Improve (compress?) Termination Transformations.}
     685\end{figure}
    490686
    491687\section{Resumption}
    492688% The stack-local data, the linked list of nodes.
    493689
    494 Resumption simple to implement because there is no stack unwinding. The
    495 resumption raise uses a list of nodes for its stack traversal. The head of the
    496 list is stored in the exception context. The nodes in the list have a pointer
    497 to the next node and a pointer to the handler function.
    498 
    499 A resumption raise traverses this list. At each node the handler function is
    500 called, passing the exception by pointer. It returns true if the exception is
    501 handled and false otherwise.
    502 
    503 The handler function does both the matching and handling. It computes the
    504 condition of each @catchResume@ in top-to-bottom order, until it finds a
    505 handler that matches. If no handler matches then the function returns
    506 false. Otherwise the matching handler is run; if it completes successfully, the
    507 function returns true. Rethrowing, through the @throwResume;@ statement,
    508 causes the function to return true.
     690Resumption simpler to implement than termination
     691because there is no stack unwinding.
     692Instead of storing the data in a special area using assembly,
     693there is just a linked list of possible handlers for each stack,
     694with each node on the list reperenting a try statement on the stack.
     695
     696The head of the list is stored in the exception context.
     697The nodes are stored in order, with the more recent try statements closer
     698to the head of the list.
     699Instead of traversing the stack resumption handling traverses the list.
     700At each node the EHM checks to see if the try statement the node repersents
     701can handle the exception. If it can, then the exception is handled and
     702the operation finishes, otherwise the search continues to the next node.
     703If the search reaches the end of the list without finding a try statement
     704that can handle the exception the default handler is executed and the
     705operation finishes.
     706
     707In each node is a handler function which does most of the work there.
     708The handler function is passed the raised the exception and returns true
     709if the exception is handled and false if it cannot be handled here.
     710
     711For each @catchResume@ clause the handler function will:
     712check to see if the raised exception is a descendant type of the declared
     713exception type, if it is and there is a conditional expression then it will
     714run the test, if both checks pass the handling code for the clause is run
     715and the function returns true, otherwise it moves onto the next clause.
     716If this is the last @catchResume@ clause then instead of moving onto
     717the next clause the function returns false as no handler could be found.
     718
     719\begin{figure}
     720\begin{cfa}
     721try {
     722        // TRY BLOCK
     723} catchResume (Exception1 * name1 ; check(name1)) {
     724        // CATCH BLOCK 1
     725} catchResume (Exception2 * name2) {
     726        // CATCH BLOCK 2
     727}
     728\end{cfa}
     729
     730\begin{cfa}
     731bool handle(exception_t * __exception_inst) {
     732        {
     733                Exception1 * name1;
     734                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
     735                        // CATCH BLOCK 1
     736                        return 1;
     737                }
     738        }
     739        {
     740                Exception2 * name2;
     741                if (name2 = (virtual Exception2 *)__exception_inst) {
     742                        // CATCH BLOCK 2
     743                        return 2;
     744                }
     745        }
     746        return false;
     747}
     748struct __try_resume_node __resume_node
     749        __attribute__((cleanup( __cfaehm_try_resume_cleanup )));
     750__cfaehm_try_resume_setup( &__resume_node, handler );
     751\end{cfa}
     752
     753\caption{Resumption Transformation}
     754\label{f:ResumptionTransformation}
     755\todo*{Improve (compress?) Resumption Transformations.}
     756\end{figure}
    509757
    510758% Recursive Resumption Stuff:
    511 Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
     759Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
     760the stack
    512761already examined, is accomplished by updating the front of the list as the
    513 search continues. Before the handler at a node is called the head of the list
     762search continues. Before the handler at a node is called, the head of the list
    514763is updated to the next node of the current node. After the search is complete,
    515764successful or not, the head of the list is reset.
    … …  
    524773stack -- the first one points over all the checked handlers -- and the ordering
    525774is maintained.
     775
     776\begin{figure}
     777\begin{minipage}[l][][b]{0,2\textwidth}
     778\begin{verbatim}
     779
     780
     781  X <-
     782  |
     783  V
     784  X
     785  |
     786  V
     787  X
     788\end{verbatim}
     789Initial State
     790\end{minipage}
     791\begin{minipage}[l][][b]{0,2\textwidth}
     792\begin{verbatim}
     793
     794
     795  X
     796  |
     797  V
     798  X <-
     799  |
     800  V
     801  X
     802\end{verbatim}
     803Handler Found
     804\end{minipage}
     805\begin{minipage}[l][][b]{0,2\textwidth}
     806\begin{verbatim}
     807  X <-
     808 /
     809/ X
     810| |
     811\ V
     812  X
     813  |
     814  V
     815  X
     816\end{verbatim}
     817Try Block Added
     818\end{minipage}
     819\begin{minipage}[l][][b]{0,2\textwidth}
     820\begin{verbatim}
     821
     822
     823  X <-
     824  |
     825  V
     826  X
     827  |
     828  V
     829  X
     830\end{verbatim}
     831Handler Done
     832\end{minipage}
     833\caption{Resumption Marking}
     834\label{f:ResumptionMarking}
     835\todo*{Convert Resumption Marking into a line figure.}
     836\end{figure}
    526837
    527838\label{p:zero-cost}
    … …  
    540851\section{Finally}
    541852% Uses destructors and GCC nested functions.
    542 Finally clauses is placed into a GCC nested-function with a unique name, and no
    543 arguments or return values. This nested function is then set as the cleanup
     853A finally clause is placed into a GCC nested-function with a unique name,
     854and no arguments or return values.
     855This nested function is then set as the cleanup
    544856function of an empty object that is declared at the beginning of a block placed
    545857around the context of the associated @try@ statement.
    546858
    547 The rest is handled by GCC. The try block and all handlers are inside the
     859The rest is handled by GCC. The try block and all handlers are inside this
    548860block. At completion, control exits the block and the empty object is cleaned
    549861up, which runs the function that contains the finally code.
    … …  
    553865
    554866Cancellation also uses libunwind to do its stack traversal and unwinding,
    555 however it uses a different primary function @_Unwind_ForcedUnwind@. Details
    556 of its interface can be found in the \VRef{s:ForcedUnwind}.
     867however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
     868of its interface can be found in the Section~\vref{s:ForcedUnwind}.
    557869
    558870The first step of cancellation is to find the cancelled stack and its type:
    … …  
    560872pointer and the current thread pointer, and every thread stores a pointer to
    561873its main coroutine and the coroutine it is currently executing.
    562 
    563 So if the active thread's main and current coroutine are the same. If they
    564 are then the current stack is a thread stack, otherwise it is a coroutine
    565 stack. If it is a thread stack then an equality check with the stored main
    566 thread pointer and current thread pointer is enough to tell if the current
    567 thread is the main thread or not.
     874\todo*{Consider adding a description of how threads are coroutines.}
     875
     876If a the current thread's main and current coroutines are the same then the
     877current stack is a thread stack. Furthermore it is easy to compare the
     878current thread to the main thread to see if they are the same. And if this
     879is not a thread stack then it must be a coroutine stack.
    568880
    569881However, if the threading library is not linked, the sequential execution is on
    … …  
    574886Regardless of how the stack is chosen, the stop function and parameter are
    575887passed to the forced-unwind function. The general pattern of all three stop
    576 functions is the same: they continue unwinding until the end of stack when they
    577 do there primary work.
     888functions is the same: they continue unwinding until the end of stack and
     889then preform their transfer.
    578890
    579891For main stack cancellation, the transfer is just a program abort.

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

    r5407cdc r8d66610  
    6666% Tip: Photographs should be cropped and compressed so as not to be too large.
    6767
    68 % To create a PDF output that is optimized for double-sided printing:
    69 % 1) comment-out the \documentclass statement in the preamble below, and
    70 %    un-comment the second \documentclass line.
    71 % 2) change the value assigned below to the boolean variable "PrintVersion"
    72 %    from "false" to "true".
    73 
    7468% ======================================================================
    7569%   D O C U M E N T   P R E A M B L E
    … …  
    8781}
    8882
    89 % Some LaTeX commands I define for my own nomenclature.
    90 % If you have to, it's easier to make changes to nomenclature once here than
    91 % in a million places throughout your thesis!
    92 \newcommand{\package}[1]{\textbf{#1}} % package names in bold text
    93 \newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font
    94 \newcommand{\href}[1]{#1} % does nothing, but defines the command so the
    95 % print-optimized version will ignore \href tags (redefined by hyperref pkg).
    96 % Anything defined here may be redefined by packages added below...
     83% Does nothing, ignores \href tags (redefined by hyperref package).
     84\newcommand{\href}[1]{#1}
    9785
    9886% For a nomenclature (optional; available from ctan.org)
    … …  
    10593% Removes large sections of the document.
    10694\usepackage{comment}
    107 % Adds todos (Must be included after comment.)
    108 \usepackage{todonotes}
     95% Adds todo commands.
     96\usepackage{todo}
     97% cfa macros used in the document
     98\usepackage{cfalab}
     99% allow global and individual modification of spacing
     100\usepackage{enumitem}
     101% Improved reference tools.
     102\usepackage[nospace]{varioref}
    109103
    110104% Hyperlinks make it very easy to navigate an electronic document.
    … …  
    151145
    152146% Exception to the rule of hyperref being the last add-on package
    153 \usepackage[automake,toc,abbreviations]{glossaries-extra}
     147\usepackage[toc,abbreviations]{glossaries-extra}
    154148% If glossaries-extra is not in your LaTeX distribution, get it from CTAN
    155149% (http://ctan.org/pkg/glossaries-extra), although it's supposed to be in
    … …  
    208202\makeglossaries
    209203
    210 % cfa macros used in the document
    211 %\usepackage{cfalab}
    212 % I'm going to bring back eventually.
    213 \makeatletter
    214 % Combines all \CC* commands:
    215 \newrobustcmd*\Cpp[1][\xspace]{\cfalab@Cpp#1}
    216 \newcommand\cfalab@Cpp{C\kern-.1em\hbox{+\kern-.25em+}}
    217 % Optional arguments do not work with pdf string. (Some fix-up required.)
    218 \pdfstringdefDisableCommands{\def\Cpp{C++}}
    219 
    220 % Wrappers for inline code snippits.
    221 \newrobustcmd*\codeCFA[1]{\lstinline[language=CFA]{#1}}
    222 \newrobustcmd*\codeC[1]{\lstinline[language=C]{#1}}
    223 \newrobustcmd*\codeCpp[1]{\lstinline[language=C++]{#1}}
    224 \newrobustcmd*\codePy[1]{\lstinline[language=Python]{#1}}
    225 
    226 % Colour text, formatted in LaTeX style instead of TeX style.
    227 \newcommand*\colour[2]{{\color{#1}#2}}
    228 \makeatother
    229 
    230 \input{common}
    231 % CFA code-style for all languages
    232 \CFAStyle
    233 % CFA default lnaguage
    234 \lstset{language=CFA,basicstyle=\linespread{0.9}\tt}
     204% listings package configuation:
     205\lstMakeShortInline@
     206\lstset{language=CFA,style=cfacommon,basicstyle=\linespread{0.9}\tt}
     207\lstset{moredelim=**[is][\protect\color{red}]{@}{@}}
    235208% Annotations from Peter:
    236209\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
    … …  
    262235% Tip: Putting each sentence on a new line is a way to simplify later editing.
    263236%----------------------------------------------------------------------
     237\input{intro}
    264238\input{existing}
    265239\input{features}
    266240\input{implement}
    267 %\input{unwinding}
    268241\input{future}
    269242
    … …  
    325298\phantomsection         % allows hyperref to link to the correct page
    326299
     300\todos
     301
    327302%----------------------------------------------------------------------
    328303\end{document} % end of logical document
Note: See TracChangeset for help on using the changeset viewer.