Changeset 63238a4


Ignore:
Timestamp:
Jun 26, 2018, 5:16:23 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, with_gc
Children:
28f3a19, 6d6cf5a
Parents:
d286cf68 (diff), 3d56d15b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

Files:
19 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/OOPSLA17/Makefile

    rd286cf68 r63238a4  
    3333
    3434DOCUMENT = generic_types.pdf
     35BASE = ${basename ${DOCUMENT}}
    3536
    3637# Directives #
     
    4142
    4243clean :
    43         @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
     44        @rm -frv ${DOCUMENT} ${BASE}.ps ${Build}
    4445
    4546# File Dependencies #
    4647
    47 ${DOCUMENT} : ${basename ${DOCUMENT}}.ps
     48${DOCUMENT} : ${BASE}.ps
    4849        ps2pdf $<
    4950
    50 ${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
     51${BASE}.ps : ${BASE}.dvi
    5152        dvips ${Build}/$< -o $@
    5253
    53 ${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ../../bibliography/pl.bib
     54${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     55                ../../bibliography/pl.bib | ${Build}
    5456        # Must have *.aux file containing citations for bibtex
    5557        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
     
    6365## Define the default recipes.
    6466
    65 ${Build}:
     67${Build} :
    6668        mkdir -p ${Build}
    6769
     
    6971        gnuplot -e Build="'${Build}/'" evaluation/timing.gp
    7072
    71 %.tex : %.fig
     73%.tex : %.fig | ${Build}
    7274        fig2dev -L eepic $< > ${Build}/$@
    7375
    74 %.ps : %.fig
     76%.ps : %.fig | ${Build}
    7577        fig2dev -L ps $< > ${Build}/$@
    7678
    77 %.pstex : %.fig
     79%.pstex : %.fig | ${Build}
    7880        fig2dev -L pstex $< > ${Build}/$@
    7981        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • doc/papers/concurrency/Makefile

    rd286cf68 r63238a4  
    2020
    2121FIGURES = ${addsuffix .tex, \
    22 monitor \
    23 ext_monitor \
    2422int_monitor \
    2523dependency \
     
    2725
    2826PICTURES = ${addsuffix .pstex, \
     27monitor \
     28ext_monitor \
    2929system \
    3030monitor_structs \
     
    5959        dvips ${Build}/$< -o $@
    6060
    61 ${BASE}.dvi : Makefile ${Build} ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    62                 annex/local.bib ../../bibliography/pl.bib
     61${BASE}.dvi : Makefile ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     62                annex/local.bib ../../bibliography/pl.bib | ${Build}
    6363        # Must have *.aux file containing citations for bibtex
    6464        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    65         ${BibTeX} ${Build}/${basename $@}
     65        -${BibTeX} ${Build}/${basename $@}
    6666        # Some citations reference others so run again to resolve these citations
    6767        ${LaTeX} ${basename $@}.tex
    68         ${BibTeX} ${Build}/${basename $@}
     68        -${BibTeX} ${Build}/${basename $@}
    6969        # Run again to finish citations
    7070        ${LaTeX} ${basename $@}.tex
     
    7272## Define the default recipes.
    7373
    74 ${Build}:
     74${Build} :
    7575        mkdir -p ${Build}
    7676
    77 ${BASE}.out.ps: ${Build}
     77${BASE}.out.ps : | ${Build}
    7878        ln -fs ${Build}/Paper.out.ps .
    7979
    80 WileyNJD-AMA.bst:
     80WileyNJD-AMA.bst :
    8181        ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst .
    8282
    83 %.tex : %.fig ${Build}
     83%.tex : %.fig | ${Build}
    8484        fig2dev -L eepic $< > ${Build}/$@
    8585
    86 %.ps : %.fig ${Build}
     86%.ps : %.fig | ${Build}
    8787        fig2dev -L ps $< > ${Build}/$@
    8888
    89 %.pstex : %.fig ${Build}
     89%.pstex : %.fig | ${Build}
    9090        fig2dev -L pstex $< > ${Build}/$@
    9191        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • doc/papers/concurrency/Paper.tex

    rd286cf68 r63238a4  
    271271Hence, there are two problems to be solved: concurrency and parallelism.
    272272While these two concepts are often combined, they are distinct, requiring different tools~\cite[\S~2]{Buhr05a}.
    273 Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization.
     273Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost, and resource utilization.
    274274
    275275The proposed concurrency API is implemented in a dialect of C, called \CFA.
     
    282282Extended versions and explanation of the following code examples are available at the \CFA website~\cite{Cforall} or in Moss~\etal~\cite{Moss18}.
    283283
    284 \CFA is an extension of ISO-C, and hence, supports all C paradigms.
     284\CFA is a non-object-oriented extension of ISO-C, and hence, supports all C paradigms.
    285285%It is a non-object-oriented system-language, meaning most of the major abstractions have either no runtime overhead or can be opted out easily.
    286 Like C, the basics of \CFA revolve around structures and routines.
     286Like C, the building blocks of \CFA are structures and routines.
    287287Virtually all of the code generated by the \CFA translator respects C memory layouts and calling conventions.
    288288While \CFA is not an object-oriented language, lacking the concept of a receiver (\eg @this@) and nominal inheritance-relationships, C does have a notion of objects: ``region of data storage in the execution environment, the contents of which can represent values''~\cite[3.15]{C11}.
     
    296296int x = 1, y = 2, z = 3;
    297297int * p1 = &x, ** p2 = &p1,  *** p3 = &p2,      $\C{// pointers to x}$
    298         `&` r1 = x,  `&&` r2 = r1,  `&&&` r3 = r2;      $\C{// references to x}$
     298    `&` r1 = x,   `&&` r2 = r1,   `&&&` r3 = r2;        $\C{// references to x}$
    299299int * p4 = &z, `&` r4 = z;
    300300
     
    411411\end{cquote}
    412412Overloading is important for \CFA concurrency since the runtime system relies on creating different types to represent concurrency objects.
    413 Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions to prevent name clashes.
     413Therefore, overloading eliminates long prefixes and other naming conventions to prevent name clashes.
    414414As seen in Section~\ref{basics}, routine @main@ is heavily overloaded.
    415 
    416 Variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name:
     415For example, variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name:
    417416\begin{cfa}
    418417struct S { int `i`; int j; double m; } s;
     
    428427}
    429428\end{cfa}
    430 For parallel semantics, both @s.i@ and @t.i@ are visible the same type, so only @i@ is ambiguous without qualification.
     429For parallel semantics, both @s.i@ and @t.i@ are visible with the same type, so only @i@ is ambiguous without qualification.
    431430
    432431
     
    468467\end{cquote}
    469468While concurrency does not use operator overloading directly, it provides an introduction for the syntax of constructors.
    470 
    471 
    472 \subsection{Parametric Polymorphism}
    473 \label{s:ParametricPolymorphism}
    474 
    475 The signature feature of \CFA is parametric-polymorphic routines~\cite{} with routines generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types.
    476 For example, the following sum routine works for any type that supports construction from 0 and addition:
    477 \begin{cfa}
    478 forall( otype T | { void `?{}`( T *, zero_t ); T `?+?`( T, T ); } ) // constraint type, 0 and +
    479 T sum( T a[$\,$], size_t size ) {
    480         `T` total = { `0` };                                    $\C{// initialize by 0 constructor}$
    481         for ( size_t i = 0; i < size; i += 1 )
    482                 total = total `+` a[i];                         $\C{// select appropriate +}$
    483         return total;
    484 }
    485 S sa[5];
    486 int i = sum( sa, 5 );                                           $\C{// use S's 0 construction and +}$
    487 \end{cfa}
    488 
    489 \CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each routine declaration:
    490 \begin{cfa}
    491 trait `sumable`( otype T ) {
    492         void `?{}`( T &, zero_t );                              $\C{// 0 literal constructor}$
    493         T `?+?`( T, T );                                                $\C{// assortment of additions}$
    494         T ?+=?( T &, T );
    495         T ++?( T & );
    496         T ?++( T & );
    497 };
    498 forall( otype T `| sumable( T )` )                      $\C{// use trait}$
    499 T sum( T a[$\,$], size_t size );
    500 \end{cfa}
    501 
    502 Assertions can be @otype@ or @dtype@.
    503 @otype@ refers to a ``complete'' object, \ie an object has a size, default constructor, copy constructor, destructor and an assignment operator.
    504 @dtype@ only guarantees an object has a size and alignment.
    505 
    506 Using the return type for discrimination, it is possible to write a type-safe @alloc@ based on the C @malloc@:
    507 \begin{cfa}
    508 forall( dtype T | sized(T) ) T * alloc( void ) { return (T *)malloc( sizeof(T) ); }
    509 int * ip = alloc();                                                     $\C{// select type and size from left-hand side}$
    510 double * dp = alloc();
    511 struct S {...} * sp = alloc();
    512 \end{cfa}
    513 where the return type supplies the type/size of the allocation, which is impossible in most type systems.
    514469
    515470
     
    540495\CFA also provides @new@ and @delete@, which behave like @malloc@ and @free@, in addition to constructing and destructing objects:
    541496\begin{cfa}
    542 {       struct S s = {10};                                              $\C{// allocation, call constructor}$
    543         ...
     497{
     498        ... struct S s = {10}; ...                              $\C{// allocation, call constructor}$
    544499}                                                                                       $\C{// deallocation, call destructor}$
    545500struct S * s = new();                                           $\C{// allocation, call constructor}$
     
    547502delete( s );                                                            $\C{// deallocation, call destructor}$
    548503\end{cfa}
    549 \CFA concurrency uses object lifetime as a means of synchronization and/or mutual exclusion.
     504\CFA concurrency uses object lifetime as a means of mutual exclusion and/or synchronization.
     505
     506
     507\subsection{Parametric Polymorphism}
     508\label{s:ParametricPolymorphism}
     509
     510The signature feature of \CFA is parametric-polymorphic routines~\cite{} with routines generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types.
     511For example, the following sum routine works for any type that supports construction from 0 and addition:
     512\begin{cfa}
     513forall( otype T | { void `?{}`( T *, zero_t ); T `?+?`( T, T ); } ) // constraint type, 0 and +
     514T sum( T a[$\,$], size_t size ) {
     515        `T` total = { `0` };                                    $\C{// initialize by 0 constructor}$
     516        for ( size_t i = 0; i < size; i += 1 )
     517                total = total `+` a[i];                         $\C{// select appropriate +}$
     518        return total;
     519}
     520S sa[5];
     521int i = sum( sa, 5 );                                           $\C{// use S's 0 construction and +}$
     522\end{cfa}
     523The builtin type @zero_t@ (and @one_t@) overload constant 0 (and 1) for a new types, where both 0 and 1 have special meaning in C.
     524
     525\CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each routine declaration:
     526\begin{cfa}
     527trait `sumable`( otype T ) {
     528        void `?{}`( T &, zero_t );                              $\C{// 0 literal constructor}$
     529        T `?+?`( T, T );                                                $\C{// assortment of additions}$
     530        T ?+=?( T &, T );
     531        T ++?( T & );
     532        T ?++( T & );
     533};
     534forall( otype T `| sumable( T )` )                      $\C{// use trait}$
     535T sum( T a[$\,$], size_t size );
     536\end{cfa}
     537
     538Assertions can be @otype@ or @dtype@.
     539@otype@ refers to a ``complete'' object, \ie an object has a size, default constructor, copy constructor, destructor and an assignment operator.
     540@dtype@ only guarantees an object has a size and alignment.
     541
     542Using the return type for discrimination, it is possible to write a type-safe @alloc@ based on the C @malloc@:
     543\begin{cfa}
     544forall( dtype T | sized(T) ) T * alloc( void ) { return (T *)malloc( sizeof(T) ); }
     545int * ip = alloc();                                                     $\C{// select type and size from left-hand side}$
     546double * dp = alloc();
     547struct S {...} * sp = alloc();
     548\end{cfa}
     549where the return type supplies the type/size of the allocation, which is impossible in most type systems.
    550550
    551551
     
    727727
    728728Using a coroutine, it is possible to express the Fibonacci formula directly without any of the C problems.
    729 Figure~\ref{f:Coroutine3States} creates a @coroutine@ type:
    730 \begin{cfa}
    731 `coroutine` Fib { int fn; };
    732 \end{cfa}
    733 which provides communication, @fn@, for the \newterm{coroutine main}, @main@, which runs on the coroutine stack, and possibly multiple interface routines @next@.
     729Figure~\ref{f:Coroutine3States} creates a @coroutine@ type, @`coroutine` Fib { int fn; }@, which provides communication, @fn@, for the \newterm{coroutine main}, @main@, which runs on the coroutine stack, and possibly multiple interface routines, \eg @next@.
    734730Like the structure in Figure~\ref{f:ExternalState}, the coroutine type allows multiple instances, where instances of this type are passed to the (overloaded) coroutine main.
    735 The coroutine main's stack holds the state for the next generation, @f1@ and @f2@, and the code has the three suspend points, representing the three states in the Fibonacci formula, to context switch back to the caller's resume.
     731The coroutine main's stack holds the state for the next generation, @f1@ and @f2@, and the code has the three suspend points, representing the three states in the Fibonacci formula, to context switch back to the caller's @resume@.
    736732The interface routine @next@, takes a Fibonacci instance and context switches to it using @resume@;
    737733on restart, the Fibonacci field, @fn@, contains the next value in the sequence, which is returned.
     
    843839\end{figure}
    844840
    845 The previous examples are \newterm{asymmetric (semi) coroutine}s because one coroutine always calls a resuming routine for another coroutine, and the resumed coroutine always suspends back to its last resumer, similar to call/return for normal routines
    846 However, there is no stack growth because @resume@/@suspend@ context switch to existing stack-frames rather than create new ones.
     841The previous examples are \newterm{asymmetric (semi) coroutine}s because one coroutine always calls a resuming routine for another coroutine, and the resumed coroutine always suspends back to its last resumer, similar to call/return for normal routines.
     842However,@resume@/@suspend@ context switch to existing stack-frames rather than create new ones so there is no stack growth.
    847843\newterm{Symmetric (full) coroutine}s have a coroutine call a resuming routine for another coroutine, which eventually forms a resuming-call cycle.
    848844(The trivial cycle is a coroutine resuming itself.)
     
    933929The producer call to @delivery@ transfers values into the consumer's communication variables, resumes the consumer, and returns the consumer status.
    934930For the first resume, @cons@'s stack is initialized, creating local variables retained between subsequent activations of the coroutine.
    935 The consumer iterates until the @done@ flag is set, prints, increments status, and calls back to the producer via @payment@, and on return from @payment@, prints the receipt from the producer and increments @money@ (inflation).
     931The consumer iterates until the @done@ flag is set, prints the values delivered by the producer, increments status, and calls back to the producer via @payment@, and on return from @payment@, prints the receipt from the producer and increments @money@ (inflation).
    936932The call from the consumer to the @payment@ introduces the cycle between producer and consumer.
    937933When @payment@ is called, the consumer copies values into the producer's communication variable and a resume is executed.
     
    963959\end{cfa}
    964960and the programming language (and possibly its tool set, \eg debugger) may need to understand @baseCoroutine@ because of the stack.
    965 Furthermore, the execution of constructs/destructors is in the wrong order for certain operations, \eg for threads;
    966 \eg, if the thread is implicitly started, it must start \emph{after} all constructors, because the thread relies on a completely initialized object, but the inherited constructor runs \emph{before} the derived.
     961Furthermore, the execution of constructs/destructors is in the wrong order for certain operations.
     962For example, for threads if the thread is implicitly started, it must start \emph{after} all constructors, because the thread relies on a completely initialized object, but the inherited constructor runs \emph{before} the derived.
    967963
    968964An alternatively is composition:
     
    984980symmetric_coroutine<>::yield_type
    985981\end{cfa}
    986 Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthread@~\cite{pthreads}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}.
     982Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthreads@~\cite{pthreads}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}.
    987983However, the generic thread-handle (identifier) is limited (few operations), unless it is wrapped in a custom type.
    988984\begin{cfa}
     
    1001997Note, the type @coroutine_t@ must be an abstract handle to the coroutine, because the coroutine descriptor and its stack are non-copyable.
    1002998Copying the coroutine descriptor results in copies being out of date with the current state of the stack.
    1003 Correspondingly, copying the stack results is copies being out of date with coroutine descriptor, and pointers in the stack being out of date to data on the stack.
     999Correspondingly, copying the stack results is copies being out of date with the coroutine descriptor, and pointers in the stack being out of date to data on the stack.
    10041000(There is no mechanism in C to find all stack-specific pointers and update them as part of a copy.)
    10051001
     
    10151011Furthermore, implementing coroutines without language supports also displays the power of a programming language.
    10161012While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed without using the language support.
    1017 The reserved keyword eases use for the common cases.
     1013The reserved keyword simply eases use for the common cases.
    10181014
    10191015Part of the mechanism to generalize coroutines is using a \CFA trait, which defines a coroutine as anything satisfying the trait @is_coroutine@, and this trait is used to restrict coroutine-manipulation routines:
     
    10301026The @main@ routine has no return value or additional parameters because the coroutine type allows an arbitrary number of interface routines with corresponding arbitrary typed input/output values versus fixed ones.
    10311027The generic routines @suspend@ and @resume@ can be redefined, but any object passed to them is a coroutine since it must satisfy the @is_coroutine@ trait to compile.
    1032 The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ routine, and possibly redefining @suspend@ and @resume@.
     1028The advantage of this approach is that users can easily create different types of coroutines, \eg changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ routine, and possibly redefining @suspend@ and @resume@.
    10331029The \CFA keyword @coroutine@ implicitly implements the getter and forward declarations required for implementing the coroutine main:
    10341030\begin{cquote}
     
    10981094The difference is that a coroutine borrows a thread from its caller, so the first thread resuming a coroutine creates an instance of @main@;
    10991095whereas, a user thread receives its own thread from the runtime system, which starts in @main@ as some point after the thread constructor is run.\footnote{
    1100 The \lstinline@main@ routine is already a special routine in C (where the program begins), so it is a natural extension of the semantics to use overloading to declare mains for different coroutines/threads (the normal main being the main of the initial thread).}
     1096The \lstinline@main@ routine is already a special routine in C, \ie where the program's initial thread begins, so it is a natural extension of this semantics to use overloading to declare \lstinline@main@s for user coroutines and threads.}
    11011097No return value or additional parameters are necessary for this routine because the task type allows an arbitrary number of interface routines with corresponding arbitrary typed input/output values.
    11021098
     
    11891185void main( Adder & adder ) with( adder ) {
    11901186    subtotal = 0;
    1191     for ( int c = 0; c < cols; c += 1 ) {
    1192                 subtotal += row[c];
    1193     }
     1187    for ( int c = 0; c < cols; c += 1 ) { subtotal += row[c]; }
    11941188}
    11951189int main() {
     
    12161210
    12171211Uncontrolled non-deterministic execution is meaningless.
    1218 To reestablish meaningful execution requires mechanisms to reintroduce determinism (\ie restrict non-determinism), called mutual exclusion and synchronization, where mutual exclusion is an access-control mechanism on data shared by threads, and synchronization is a timing relationship among threads~\cite[\S~4]{Buhr05a}.
     1212To reestablish meaningful execution requires mechanisms to reintroduce determinism, \ie restrict non-determinism, called mutual exclusion and synchronization, where mutual exclusion is an access-control mechanism on data shared by threads, and synchronization is a timing relationship among threads~\cite[\S~4]{Buhr05a}.
    12191213Since many deterministic challenges appear with the use of mutable shared state, some languages/libraries disallow it, \eg Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka~\cite{Akka} (Scala).
    1220 In these paradigms, interaction among concurrent objects is performed by stateless message-passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts (\eg channels~\cite{CSP,Go}).
    1221 However, in call/return-based languages, these approaches force a clear distinction (\ie introduce a new programming paradigm) between regular and concurrent computation (\ie routine call versus message passing).
     1214In these paradigms, interaction among concurrent objects is performed by stateless message-passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts, \eg channels~\cite{CSP,Go}.
     1215However, in call/return-based languages, these approaches force a clear distinction, \ie introduce a new programming paradigm, between regular and concurrent computation, \eg routine call versus message passing.
    12221216Hence, a programmer must learn and manipulate two sets of design patterns.
    12231217While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account.
     
    12441238However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
    12451239Methods range from low-level locks, which are fast and flexible but require significant attention for correctness, to higher-level concurrency techniques, which sacrifice some performance to improve ease of use.
    1246 Ease of use comes by either guaranteeing some problems cannot occur (\eg deadlock free), or by offering a more explicit coupling between shared data and critical section.
    1247 For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing) for numerical types.
     1240Ease of use comes by either guaranteeing some problems cannot occur, \eg deadlock free, or by offering a more explicit coupling between shared data and critical section.
     1241For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations, \eg reading/writing, for numerical types.
    12481242However, a significant challenge with locks is composability because it takes careful organization for multiple locks to be used while preventing deadlock.
    12491243Easing composability is another feature higher-level mutual-exclusion mechanisms can offer.
     
    12541248Synchronization enforces relative ordering of execution, and synchronization tools provide numerous mechanisms to establish these timing relationships.
    12551249Low-level synchronization primitives offer good performance and flexibility at the cost of ease of use;
    1256 higher-level mechanisms often simplify usage by adding better coupling between synchronization and data (\eg message passing), or offering a simpler solution to otherwise involved challenges, \eg barrier lock.
     1250higher-level mechanisms often simplify usage by adding better coupling between synchronization and data, \eg message passing, or offering a simpler solution to otherwise involved challenges, \eg barrier lock.
    12571251Often synchronization is used to order access to a critical section, \eg ensuring a reader thread is the next kind of thread to enter a critical section.
    12581252If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, that reader has \newterm{barged}.
     
    12721266The strong association with the call/return paradigm eases programmability, readability and maintainability, at a slight cost in flexibility and efficiency.
    12731267
    1274 Note, like coroutines/threads, both locks and monitors require an abstract handle to reference them, because at their core, both mechanisms are manipulating non-copyable shared state.
     1268Note, like coroutines/threads, both locks and monitors require an abstract handle to reference them, because at their core, both mechanisms are manipulating non-copyable shared-state.
    12751269Copying a lock is insecure because it is possible to copy an open lock and then use the open copy when the original lock is closed to simultaneously access the shared data.
    12761270Copying a monitor is secure because both the lock and shared data are copies, but copying the shared data is meaningless because it no longer represents a unique entity.
     
    13751369\end{cfa}
    13761370(While object-oriented monitors can be extended with a mutex qualifier for multiple-monitor members, no prior example of this feature could be found.)
    1377 In practice, writing multi-locking routines that do not deadlocks is tricky.
     1371In practice, writing multi-locking routines that do not deadlock is tricky.
    13781372Having language support for such a feature is therefore a significant asset for \CFA.
    13791373
    13801374The capability to acquire multiple locks before entering a critical section is called \newterm{bulk acquire}.
    1381 In previous example, \CFA guarantees the order of acquisition is consistent across calls to different routines using the same monitors as arguments.
     1375In the previous example, \CFA guarantees the order of acquisition is consistent across calls to different routines using the same monitors as arguments.
    13821376This consistent ordering means acquiring multiple monitors is safe from deadlock.
    13831377However, users can force the acquiring order.
     
    13951389In the calls to @bar@ and @baz@, the monitors are acquired in opposite order.
    13961390
    1397 However, such use leads to lock acquiring order problems resulting in deadlock~\cite{Lister77}, where detecting it requires dynamically tracking of monitor calls, and dealing with it requires implement rollback semantics~\cite{Dice10}.
     1391However, such use leads to lock acquiring order problems resulting in deadlock~\cite{Lister77}, where detecting it requires dynamically tracking of monitor calls, and dealing with it requires rollback semantics~\cite{Dice10}.
    13981392In \CFA, safety is guaranteed by using bulk acquire of all monitors to shared objects, whereas other monitor systems provide no aid.
    13991393While \CFA provides only a partial solution, the \CFA partial solution handles many useful cases.
     
    14401434
    14411435
    1442 \section{Internal Scheduling}
    1443 \label{s:InternalScheduling}
     1436\section{Scheduling}
     1437\label{s:Scheduling}
    14441438
    14451439While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed.
     
    14541448The appropriate condition lock is signalled to unblock an opposite kind of thread after an element is inserted/removed from the buffer.
    14551449Signalling is unconditional, because signalling an empty condition lock does nothing.
     1450
    14561451Signalling semantics cannot have the signaller and signalled thread in the monitor simultaneously, which means:
    14571452\begin{enumerate}
     
    14631458The signalling thread blocks but is marked for urgrent unblocking at the next scheduling point and the signalled thread continues.
    14641459\end{enumerate}
    1465 The first approach is too restrictive, as it precludes solving a reasonable class of problems (\eg dating service).
     1460The first approach is too restrictive, as it precludes solving a reasonable class of problems, \eg dating service.
    14661461\CFA supports the next two semantics as both are useful.
    14671462Finally, while it is common to store a @condition@ as a field of the monitor, in \CFA, a @condition@ variable can be created/stored independently.
     
    15391534If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
    15401535Threads making calls to routines that are currently excluded block outside (external) of the monitor on a calling queue, versus blocking on condition queues inside (internal) of the monitor.
     1536% External scheduling is more constrained and explicit, which helps programmers reduce the non-deterministic nature of concurrency.
     1537External scheduling allows users to wait for events from other threads without concern of unrelated events occurring.
     1538The mechnaism can be done in terms of control flow, \eg Ada @accept@ or \uC @_Accept@, or in terms of data, \eg Go channels.
     1539While both mechanisms have strengths and weaknesses, this project uses a control-flow mechanism to stay consistent with other language semantics.
     1540Two challenges specific to \CFA for external scheduling are loose object-definitions (see Section~\ref{s:LooseObjectDefinitions}) and multiple-monitor routines (see Section~\ref{s:Multi-MonitorScheduling}).
    15411541
    15421542For internal scheduling, non-blocking signalling (as in the producer/consumer example) is used when the signaller is providing the cooperation for a waiting thread;
    15431543the signaller enters the monitor and changes state, detects a waiting threads that can use the state, performs a non-blocking signal on the condition queue for the waiting thread, and exits the monitor to run concurrently.
    1544 The waiter unblocks next, takes the state, and exits the monitor.
     1544The waiter unblocks next, uses/takes the state, and exits the monitor.
    15451545Blocking signalling is the reverse, where the waiter is providing the cooperation for the signalling thread;
    15461546the signaller enters the monitor, detects a waiting thread providing the necessary state, performs a blocking signal to place it on the urgent queue and unblock the waiter.
    1547 The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to take the state.
     1547The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to use/take the state.
    15481548
    15491549Figure~\ref{f:DatingService} shows a dating service demonstrating the two forms of signalling: non-blocking and blocking.
    15501550The dating service matches girl and boy threads with matching compatibility codes so they can exchange phone numbers.
    15511551A thread blocks until an appropriate partner arrives.
    1552 The complexity is exchanging phone number in the monitor,
    1553 While the non-barging monitor prevents a caller from stealing a phone number, the monitor mutual-exclusion property
    1554 
    1555 The dating service is an example of a monitor that cannot be written using external scheduling because:
    1556 
    1557 The example in table \ref{tbl:datingservice} highlights the difference in behaviour.
    1558 As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
    1559 To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example.
    1560 This feature removes the need for a second condition variables and simplifies programming.
    1561 Like every other monitor semantic, @signal_block@ uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to @signal_block@, meaning no other thread can acquire the monitor either before or after the call.
     1552The complexity is exchanging phone number in the monitor because the monitor mutual-exclusion property prevents exchanging numbers.
     1553For internal scheduling, the @exchange@ condition is necessary to block the thread finding the match, while the matcher unblocks to take the oppose number, post its phone number, and unblock the partner.
     1554For external scheduling, the implicit urgent-condition replaces the explict @exchange@-condition and @signal_block@ puts the finding thread on the urgent condition and unblocks the matcher..
     1555
     1556The dating service is an example of a monitor that cannot be written using external scheduling because it requires knowledge of calling parameters to make scheduling decisions, and parameters of waiting threads are unavailable;
     1557as well, an arriving thread may not find a partner and must wait, which requires a condition variable, and condition variables imply internal scheduling.
    15621558
    15631559\begin{figure}
     
    16551651}
    16561652\end{cfa}
    1657 must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the front of the condition queue.
    1658 In general, the signaller does not know the order of waiting threads, so in general, it must acquire the maximum number of mutex locks for the worst-case waiting thread.
     1653must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the condition queue.
    16591654
    16601655Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
     
    16671662void foo( M & mutex m1, M & mutex m2 ) {
    16681663        ... wait( `e, m1` ); ...                                $\C{// release m1, keeping m2 acquired )}$
    1669 void baz( M & mutex m1, M & mutex m2 ) {        $\C{// must acquire m1 and m2 )}$
     1664void bar( M & mutex m1, M & mutex m2 ) {        $\C{// must acquire m1 and m2 )}$
    16701665        ... signal( `e` ); ...
    16711666\end{cfa}
    1672 The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to  enter @baz@ to get to the @signal@.
     1667The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to  enter @bar@ to get to the @signal@.
    16731668While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable.
    16741669
     
    17551750However, Figure~\ref{f:OtherWaitingThread} shows this solution is complex depending on other waiters, resulting is choices when the signaller finishes the inner mutex-statement.
    17561751The singaller can retain @m2@ until completion of the outer mutex statement and pass the locks to waiter W1, or it can pass @m2@ to waiter W2 after completing the inner mutex-statement, while continuing to hold @m1@.
    1757 In the latter case, waiter W2 must eventually pass @m2@ to waiter W1, which is complex because W2 may have waited before W1 so it is unaware of W1.
     1752In the latter case, waiter W2 must eventually pass @m2@ to waiter W1, which is complex because W1 may have waited before W2, so W2 is unaware of it.
    17581753Furthermore, there is an execution sequence where the signaller always finds waiter W2, and hence, waiter W1 starves.
    17591754
     
    18561851The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
    18571852Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
    1858 
    1859 \subsubsection{Partial Signalling} \label{partial-sig}
    18601853\end{comment}
    18611854
    18621855
     1856\begin{comment}
    18631857\section{External scheduling} \label{extsched}
    18641858
    1865 An alternative to internal scheduling is external scheduling (see Table~\ref{tbl:sched}).
    1866 
    1867 \begin{comment}
    18681859\begin{table}
    18691860\begin{tabular}{|c|c|c|}
     
    19291920\label{tbl:sched}
    19301921\end{table}
    1931 \end{comment}
    1932 
    1933 This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    1934 Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
    1935 External scheduling can generally be done either in terms of control flow (\eg Ada with @accept@, \uC with @_Accept@) or in terms of data (\eg Go with channels).
    1936 Of course, both of these paradigms have their own strengths and weaknesses, but for this project, control-flow semantics was chosen to stay consistent with the rest of the languages semantics.
    1937 Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines.
    1938 The previous example shows a simple use @_Accept@ versus @wait@/@signal@ and its advantages.
    1939 Note that while other languages often use @accept@/@select@ as the core external scheduling keyword, \CFA uses @waitfor@ to prevent name collisions with existing socket \textbf{api}s.
    19401922
    19411923For the @P@ member above using internal scheduling, the call to @wait@ only guarantees that @V@ is the last routine to access the monitor, allowing a third routine, say @isInUse()@, acquire mutual exclusion several times while routine @P@ is waiting.
    19421924On the other hand, external scheduling guarantees that while routine @P@ is waiting, no other routine than @V@ can acquire the monitor.
    1943 
    1944 % ======================================================================
    1945 % ======================================================================
     1925\end{comment}
     1926
     1927
    19461928\subsection{Loose Object Definitions}
    1947 % ======================================================================
    1948 % ======================================================================
    1949 In \uC, a monitor class declaration includes an exhaustive list of monitor operations.
    1950 Since \CFA is not object oriented, monitors become both more difficult to implement and less clear for a user:
    1951 
    1952 \begin{cfa}
    1953 monitor A {};
    1954 
    1955 void f(A & mutex a);
    1956 void g(A & mutex a) {
    1957         waitfor(f); // Obvious which f() to wait for
    1958 }
    1959 
    1960 void f(A & mutex a, int); // New different F added in scope
    1961 void h(A & mutex a) {
    1962         waitfor(f); // Less obvious which f() to wait for
    1963 }
    1964 \end{cfa}
    1965 
    1966 Furthermore, external scheduling is an example where implementation constraints become visible from the interface.
    1967 Here is the cfa-code for the entering phase of a monitor:
    1968 \begin{center}
    1969 \begin{tabular}{l}
    1970 \begin{cfa}
    1971         if monitor is free
    1972                 enter
    1973         elif already own the monitor
    1974                 continue
    1975         elif monitor accepts me
    1976                 enter
    1977         else
    1978                 block
    1979 \end{cfa}
    1980 \end{tabular}
    1981 \end{center}
     1929\label{s:LooseObjectDefinitions}
     1930
     1931In an object-oriented programming-language, a class includes an exhaustive list of operations.
     1932However, new members can be added via static inheritance or dynaic members, \eg JavaScript~\cite{JavaScript}.
     1933Similarly, monitor routines can be added at any time in \CFA, making it less clear for programmers and more difficult to implement.
     1934\begin{cfa}
     1935monitor M {};
     1936void `f`( M & mutex m );
     1937void g( M & mutex m ) { waitfor( `f` ); }       $\C{// clear which f}$
     1938void `f`( M & mutex m, int );                           $\C{// different f}$
     1939void h( M & mutex m ) { waitfor( `f` ); }       $\C{// unclear which f}$
     1940\end{cfa}
     1941Hence, the cfa-code for the entering a monitor looks like:
     1942\begin{cfa}
     1943if ( $\textrm{\textit{monitor is free}}$ ) $\LstCommentStyle{// \color{red}enter}$
     1944else if ( $\textrm{\textit{already own monitor}}$ ) $\LstCommentStyle{// \color{red}continue}$
     1945else if ( $\textrm{\textit{monitor accepts me}}$ ) $\LstCommentStyle{// \color{red}enter}$
     1946else $\LstCommentStyle{// \color{red}block}$
     1947\end{cfa}
    19821948For the first two conditions, it is easy to implement a check that can evaluate the condition in a few instructions.
    1983 However, a fast check for @monitor accepts me@ is much harder to implement depending on the constraints put on the monitors.
    1984 Indeed, monitors are often expressed as an entry queue and some acceptor queue as in Figure~\ref{fig:ClassicalMonitor}.
     1949However, a fast check for \emph{monitor accepts me} is much harder to implement depending on the constraints put on the monitors.
     1950Figure~\ref{fig:ClassicalMonitor} shows monitors are often expressed as an entry (calling) queue, some acceptor queues, and an urgent stack/queue.
    19851951
    19861952\begin{figure}
    19871953\centering
    1988 \subfloat[Classical Monitor] {
     1954\subfloat[Classical monitor] {
    19891955\label{fig:ClassicalMonitor}
    1990 {\resizebox{0.45\textwidth}{!}{\input{monitor}}}
     1956{\resizebox{0.45\textwidth}{!}{\input{monitor.pstex_t}}}
    19911957}% subfloat
    1992 \qquad
    1993 \subfloat[bulk acquire Monitor] {
     1958\quad
     1959\subfloat[Bulk acquire monitor] {
    19941960\label{fig:BulkMonitor}
    1995 {\resizebox{0.45\textwidth}{!}{\input{ext_monitor}}}
     1961{\resizebox{0.45\textwidth}{!}{\input{ext_monitor.pstex_t}}}
    19961962}% subfloat
    1997 \caption{External Scheduling Monitor}
     1963\caption{Monitor Implementation}
     1964\label{f:MonitorImplementation}
    19981965\end{figure}
    19991966
    2000 There are other alternatives to these pictures, but in the case of the left picture, implementing a fast accept check is relatively easy.
    2001 Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (\eg 128) of mutex members.
    2002 This approach requires a unique dense ordering of routines with an upper-bound and that ordering must be consistent across translation units.
    2003 For OO languages these constraints are common, since objects only offer adding member routines consistently across translation units via inheritance.
    2004 However, in \CFA users can extend objects with mutex routines that are only visible in certain translation unit.
    2005 This means that establishing a program-wide dense-ordering among mutex routines can only be done in the program linking phase, and still could have issues when using dynamically shared objects.
    2006 
    2007 The alternative is to alter the implementation as in Figure~\ref{fig:BulkMonitor}.
    2008 Here, the mutex routine called is associated with a thread on the entry queue while a list of acceptable routines is kept separate.
    2009 Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions.
    2010 Storing an array of accepted routine pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search.
    2011 Furthermore, supporting nested external scheduling (\eg listing \ref{f:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
    2012 
     1967For a fixed (small) number of mutex routines (\eg 128), the accept check reduces to a bitmask of allowed callers, which can be checked with a single instruction.
     1968This approach requires a unique dense ordering of routines with a small upper-bound and the ordering must be consistent across translation units.
     1969For object-oriented languages these constraints are common, but \CFA mutex routines can be added in any scope and are only visible in certain translation unit, precluding program-wide dense-ordering among mutex routines.
     1970
     1971Figure~\ref{fig:BulkMonitor} shows the \CFA monitor implementation.
     1972The mutex routine called is associated with each thread on the entry queue, while a list of acceptable routines is kept separately.
     1973The accepted list is a variable-sized array of accepted routine pointers, so the single instruction bitmask comparison is replaced by dereferencing a pointer followed by a linear search.
     1974
     1975\begin{comment}
    20131976\begin{figure}
    20141977\begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]
     
    20341997In the end, the most flexible approach has been chosen since it allows users to write programs that would otherwise be  hard to write.
    20351998This decision is based on the assumption that writing fast but inflexible locks is closer to a solved problem than writing locks that are as flexible as external scheduling in \CFA.
    2036 
    2037 % ======================================================================
    2038 % ======================================================================
     1999\end{comment}
     2000
     2001
    20392002\subsection{Multi-Monitor Scheduling}
    2040 % ======================================================================
    2041 % ======================================================================
     2003\label{s:Multi-MonitorScheduling}
    20422004
    20432005External scheduling, like internal scheduling, becomes significantly more complex when introducing multi-monitor syntax.
    2044 Even in the simplest possible case, some new semantics needs to be established:
     2006Even in the simplest possible case, new semantics needs to be established:
    20452007\begin{cfa}
    20462008monitor M {};
    2047 
    2048 void f(M & mutex a);
    2049 
    2050 void g(M & mutex b, M & mutex c) {
    2051         waitfor(f); // two monitors M => unknown which to pass to f(M & mutex)
    2052 }
    2053 \end{cfa}
    2054 The obvious solution is to specify the correct monitor as follows:
    2055 
     2009void f( M & mutex m1 );
     2010void g( M & mutex m1, M & mutex m2 ) {
     2011        waitfor( f );                                                   $\C{// pass m1 or m2 to f?}$
     2012}
     2013\end{cfa}
     2014The solution is for the programmer to disambiguate:
     2015\begin{cfa}
     2016        waitfor( f, m2 );                                               $\C{// wait for call to f with argument m2}$
     2017\end{cfa}
     2018Routine @g@ has acquired both locks, so when routine @f@ is called, the lock for monitor @m2@ is passed from @g@ to @f@ (while @g@ still holds lock @m1@).
     2019This behaviour can be extended to the multi-monitor @waitfor@ statement.
    20562020\begin{cfa}
    20572021monitor M {};
    2058 
    2059 void f(M & mutex a);
    2060 
    2061 void g(M & mutex a, M & mutex b) {
    2062         // wait for call to f with argument b
    2063         waitfor(f, b);
    2064 }
    2065 \end{cfa}
    2066 This syntax is unambiguous.
    2067 Both locks are acquired and kept by @g@.
    2068 When routine @f@ is called, the lock for monitor @b@ is temporarily transferred from @g@ to @f@ (while @g@ still holds lock @a@).
    2069 This behaviour can be extended to the multi-monitor @waitfor@ statement as follows.
    2070 
    2071 \begin{cfa}
    2072 monitor M {};
    2073 
    2074 void f(M & mutex a, M & mutex b);
    2075 
    2076 void g(M & mutex a, M & mutex b) {
    2077         // wait for call to f with arguments a and b
    2078         waitfor(f, a, b);
    2079 }
    2080 \end{cfa}
    2081 
    2082 Note that the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired in the routine. @waitfor@ used in any other context is undefined behaviour.
     2022void f( M & mutex m1, M & mutex m2 );
     2023void g( M & mutex m1, M & mutex m2 ) {
     2024        waitfor( f, m1, m2 );                                   $\C{// wait for call to f with arguments m1 and m2}$
     2025}
     2026\end{cfa}
     2027Again, the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired by accepting routine.
    20832028
    20842029An important behaviour to note is when a set of monitors only match partially:
    2085 
    20862030\begin{cfa}
    20872031mutex struct A {};
    2088 
    20892032mutex struct B {};
    2090 
    2091 void g(A & mutex a, B & mutex b) {
    2092         waitfor(f, a, b);
    2093 }
    2094 
     2033void g( A & mutex m1, B & mutex m2 ) {
     2034        waitfor( f, m1, m2 );
     2035}
    20952036A a1, a2;
    20962037B b;
    2097 
    20982038void foo() {
    2099         g(a1, b); // block on accept
    2100 }
    2101 
     2039        g( a1, b ); // block on accept
     2040}
    21022041void bar() {
    2103         f(a2, b); // fulfill cooperation
     2042        f( a2, b ); // fulfill cooperation
    21042043}
    21052044\end{cfa}
     
    21082047It is also important to note that in the case of external scheduling the order of parameters is irrelevant; @waitfor(f,a,b)@ and @waitfor(f,b,a)@ are indistinguishable waiting condition.
    21092048
    2110 % ======================================================================
    2111 % ======================================================================
     2049
    21122050\subsection{\protect\lstinline|waitfor| Semantics}
    2113 % ======================================================================
    2114 % ======================================================================
    21152051
    21162052Syntactically, the @waitfor@ statement takes a routine identifier and a set of monitors.
     
    22112147\end{figure}
    22122148
    2213 % ======================================================================
    2214 % ======================================================================
     2149
    22152150\subsection{Waiting For The Destructor}
    2216 % ======================================================================
    2217 % ======================================================================
     2151
    22182152An interesting use for the @waitfor@ statement is destructor semantics.
    22192153Indeed, the @waitfor@ statement can accept any @mutex@ routine, which includes the destructor (see section \ref{data}).
     
    22422176
    22432177
    2244 % ######     #    ######     #    #       #       ####### #       ###  #####  #     #
    2245 % #     #   # #   #     #   # #   #       #       #       #        #  #     # ##   ##
    2246 % #     #  #   #  #     #  #   #  #       #       #       #        #  #       # # # #
    2247 % ######  #     # ######  #     # #       #       #####   #        #   #####  #  #  #
    2248 % #       ####### #   #   ####### #       #       #       #        #        # #     #
    2249 % #       #     # #    #  #     # #       #       #       #        #  #     # #     #
    2250 % #       #     # #     # #     # ####### ####### ####### ####### ###  #####  #     #
    22512178\section{Parallelism}
     2179
    22522180Historically, computer performance was about processor speeds and instruction counts.
    22532181However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}.
     
    22592187While there are many variations of the presented paradigms, most of these variations do not actually change the guarantees or the semantics, they simply move costs in order to achieve better performance for certain workloads.
    22602188
     2189
    22612190\section{Paradigms}
     2191
     2192
    22622193\subsection{User-Level Threads}
     2194
    22632195A direct improvement on the \textbf{kthread} approach is to use \textbf{uthread}.
    22642196These threads offer most of the same features that the operating system already provides but can be used on a much larger scale.
     
    22692201Examples of languages that support \textbf{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
    22702202
     2203
    22712204\subsection{Fibers : User-Level Threads Without Preemption} \label{fibers}
     2205
    22722206A popular variant of \textbf{uthread} is what is often referred to as \textbf{fiber}.
    22732207However, \textbf{fiber} do not present meaningful semantic differences with \textbf{uthread}.
     
    22782212An example of a language that uses fibers is Go~\cite{Go}
    22792213
     2214
    22802215\subsection{Jobs and Thread Pools}
     2216
    22812217An approach on the opposite end of the spectrum is to base parallelism on \textbf{pool}.
    22822218Indeed, \textbf{pool} offer limited flexibility but at the benefit of a simpler user interface.
     
    22892225The gold standard of this implementation is Intel's TBB library~\cite{TBB}.
    22902226
     2227
    22912228\subsection{Paradigm Performance}
     2229
    22922230While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level.
    22932231Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload.
     
    22972235Finally, if the units of uninterrupted work are large, enough the paradigm choice is largely amortized by the actual work done.
    22982236
     2237
    22992238\section{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel}
     2239
    23002240A \textbf{cfacluster} is a group of \textbf{kthread} executed in isolation. \textbf{uthread} are scheduled on the \textbf{kthread} of a given \textbf{cfacluster}, allowing organization between \textbf{uthread} and \textbf{kthread}.
    23012241It is important that \textbf{kthread} belonging to a same \textbf{cfacluster} have homogeneous settings, otherwise migrating a \textbf{uthread} from one \textbf{kthread} to the other can cause issues.
     
    23052245Currently \CFA only supports one \textbf{cfacluster}, the initial one.
    23062246
     2247
    23072248\subsection{Future Work: Machine Setup}\label{machine}
     2249
    23082250While this was not done in the context of this paper, another important aspect of clusters is affinity.
    23092251While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups.
     
    23112253OS support for CPU affinity is now common~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
    23122254
     2255
    23132256\subsection{Paradigms}\label{cfaparadigms}
     2257
    23142258Given these building blocks, it is possible to reproduce all three of the popular paradigms.
    23152259Indeed, \textbf{uthread} is the default paradigm in \CFA.
     
    23192263
    23202264
    2321 
    23222265\section{Behind the Scenes}
     2266
    23232267There are several challenges specific to \CFA when implementing concurrency.
    23242268These challenges are a direct result of bulk acquire and loose object definitions.
     
    23372281Note that since the major contributions of this paper are extending monitor semantics to bulk acquire and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed.
    23382282
    2339 % ======================================================================
    2340 % ======================================================================
     2283
    23412284\section{Mutex Routines}
    2342 % ======================================================================
    2343 % ======================================================================
    23442285
    23452286The first step towards the monitor implementation is simple @mutex@ routines.
     
    23762317\end{figure}
    23772318
     2319
    23782320\subsection{Details: Interaction with polymorphism}
     2321
    23792322Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be more complex to support.
    23802323However, it is shown that entry-point locking solves most of the issues.
     
    24562399Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites.
    24572400
    2458 % ======================================================================
    2459 % ======================================================================
     2401
    24602402\section{Threading} \label{impl:thread}
    2461 % ======================================================================
    2462 % ======================================================================
    24632403
    24642404Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency.
     
    24732413\end{figure}
    24742414
     2415
    24752416\subsection{Processors}
     2417
    24762418Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically @pthread@s in the current implementation of \CFA.
    24772419Indeed, any parallelism must go through operating-system libraries.
     
    24812423Processors internally use coroutines to take advantage of the existing context-switching semantics.
    24822424
     2425
    24832426\subsection{Stack Management}
     2427
    24842428One of the challenges of this system is to reduce the footprint as much as possible.
    24852429Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
     
    24882432In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large.
    24892433
     2434
    24902435\subsection{Context Switching}
     2436
    24912437As mentioned in section \ref{coroutine}, coroutines are a stepping stone for implementing threading, because they share the same mechanism for context-switching between different stacks.
    24922438To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific routine call.
     
    25022448This option is not currently present in \CFA, but the changes required to add it are strictly additive.
    25032449
     2450
    25042451\subsection{Preemption} \label{preemption}
     2452
    25052453Finally, an important aspect for any complete threading system is preemption.
    25062454As mentioned in section \ref{basics}, preemption introduces an extra degree of uncertainty, which enables users to have multiple threads interleave transparently, rather than having to cooperate among threads for proper scheduling and CPU distribution.
     
    25362484Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
    25372485
     2486
    25382487\subsection{Scheduler}
    25392488Finally, an aspect that was not mentioned yet is the scheduling algorithm.
     
    25412490Further discussion on scheduling is present in section \ref{futur:sched}.
    25422491
    2543 % ======================================================================
    2544 % ======================================================================
     2492
    25452493\section{Internal Scheduling} \label{impl:intsched}
    2546 % ======================================================================
    2547 % ======================================================================
     2494
    25482495The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:ClassicalMonitor} for convenience):
    25492496
    25502497\begin{figure}
    25512498\begin{center}
    2552 {\resizebox{0.4\textwidth}{!}{\input{monitor}}}
     2499{\resizebox{0.4\textwidth}{!}{\input{monitor.pstex_t}}}
    25532500\end{center}
    25542501\caption{Traditional illustration of a monitor}
  • doc/papers/concurrency/figures/ext_monitor.fig

    rd286cf68 r63238a4  
    88-2
    991200 2
    10 5 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 3150.000 3450.000 3150 3150 2850 3450 3150 3750
    11 5 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 3150.000 4350.000 3150 4050 2850 4350 3150 4650
    12 6 5850 1950 6150 2250
    13 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2100 105 105 6000 2100 6105 2205
    14 4 1 -1 0 0 0 10 0.0000 2 105 90 6000 2160 d\001
     105 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 1575.000 3450.000 1575 3150 1275 3450 1575 3750
     115 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 1575.000 4350.000 1575 4050 1275 4350 1575 4650
     126 4275 1950 4575 2250
     131 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2100 105 105 4425 2100 4530 2205
     144 1 -1 0 0 0 10 0.0000 2 105 90 4425 2160 d\001
    1515-6
    16 6 5100 2100 5400 2400
    17 1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 5250 2250 105 105 5250 2250 5355 2250
    18 4 1 -1 0 0 0 10 0.0000 2 105 120 5250 2295 X\001
     166 4275 1650 4575 1950
     171 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 1800 105 105 4425 1800 4530 1905
     184 1 -1 0 0 0 10 0.0000 2 105 90 4425 1860 b\001
    1919-6
    20 6 5100 1800 5400 2100
    21 1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 5250 1950 105 105 5250 1950 5355 1950
    22 4 1 -1 0 0 0 10 0.0000 2 105 120 5250 2010 Y\001
     206 1495 5445 5700 5655
     211 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 1575 5550 80 80 1575 5550 1655 5630
     221 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 2925 5550 105 105 2925 5550 3030 5655
     231 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 4425 5550 105 105 4425 5550 4530 5655
     244 0 -1 0 0 0 12 0.0000 2 135 1035 3150 5625 blocked task\001
     254 0 -1 0 0 0 12 0.0000 2 135 870 1725 5625 active task\001
     264 0 -1 0 0 0 12 0.0000 2 135 1050 4650 5625 routine mask\001
    2327-6
    24 6 5850 1650 6150 1950
    25 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 1800 105 105 6000 1800 6105 1905
    26 4 1 -1 0 0 0 10 0.0000 2 105 90 6000 1860 b\001
     286 3525 1800 3825 2400
     291 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 3675 1950 105 105 3675 1950 3780 1950
     302 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
     31         3525 1800 3825 1800 3825 2400 3525 2400 3525 1800
     324 1 4 0 0 0 10 0.0000 2 105 120 3675 2010 Y\001
    2733-6
    28 6 3070 5445 7275 5655
    29 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3150 5550 80 80 3150 5550 3230 5630
    30 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4500 5550 105 105 4500 5550 4605 5655
    31 1 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 6000 5550 105 105 6000 5550 6105 5655
    32 4 0 -1 0 0 0 12 0.0000 2 135 1035 4725 5625 blocked task\001
    33 4 0 -1 0 0 0 12 0.0000 2 135 870 3300 5625 active task\001
    34 4 0 -1 0 0 0 12 0.0000 2 135 1050 6225 5625 routine mask\001
     346 3525 2100 3825 2400
     351 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 3675 2250 105 105 3675 2250 3780 2250
     364 1 4 0 0 0 10 0.0000 2 105 120 3675 2295 X\001
    3537-6
    36 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3300 3600 105 105 3300 3600 3405 3705
    37 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3600 3600 105 105 3600 3600 3705 3705
    38 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6600 3900 105 105 6600 3900 6705 4005
    39 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 3900 105 105 6900 3900 7005 4005
    40 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2700 105 105 6000 2700 6105 2805
    41 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2400 105 105 6000 2400 6105 2505
    42 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 5100 4575 80 80 5100 4575 5180 4655
     381 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 1725 3600 105 105 1725 3600 1830 3705
     391 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 2025 3600 105 105 2025 3600 2130 3705
     401 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5025 3900 105 105 5025 3900 5130 4005
     411 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5325 3900 105 105 5325 3900 5430 4005
     421 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2700 105 105 4425 2700 4530 2805
     431 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2400 105 105 4425 2400 4530 2505
     441 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3525 4575 80 80 3525 4575 3605 4655
    43452 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    44          4050 2925 5475 2925 5475 3225 4050 3225 4050 2925
     46         2475 2925 3900 2925 3900 3225 2475 3225 2475 2925
    45472 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    46          3150 3750 3750 3750 3750 4050 3150 4050
     48         1575 3750 2175 3750 2175 4050 1575 4050
    47492 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 3
    48          3150 3450 3750 3450 3900 3675
     50         1575 3450 2175 3450 2325 3675
    49512 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    50          3750 3150 3600 3375
     52         2175 3150 2025 3375
    51532 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 3
    52          3150 4350 3750 4350 3900 4575
     54         1575 4350 2175 4350 2325 4575
    53552 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    54          3750 4050 3600 4275
     56         2175 4050 2025 4275
    55572 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    56          3150 4650 3750 4650 3750 4950 4950 4950
     58         1575 4650 2175 4650 2175 4950 3375 4950
    57592 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    58          6450 3750 6300 3975
     60         4875 3750 4725 3975
    59612 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2
    60          4950 4950 5175 5100
     62         3375 4950 3600 5100
    61632 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 9
    62          5250 4950 6450 4950 6450 4050 7050 4050 7050 3750 6450 3750
    63          6450 2850 6150 2850 6150 1650
     64         3675 4950 4875 4950 4875 4050 5475 4050 5475 3750 4875 3750
     65         4875 2850 4575 2850 4575 1650
    64662 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5
    65          5850 4200 5850 3300 4350 3300 4350 4200 5850 4200
    66 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
     67         4275 4200 4275 3300 2775 3300 2775 4200 4275 4200
     682 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6769        1 1 1.00 60.00 120.00
    68         7 1 1.00 60.00 120.00
    69          5250 3150 5250 2400
     70         3675 3075 3675 2400
     712 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
     72         4125 2850 4575 3000
    70732 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    71          3150 3150 3750 3150 3750 2850 5700 2850 5700 1650
    72 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    73          5700 2850 6150 3000
    74 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    75          5100 1800 5400 1800 5400 2400 5100 2400 5100 1800
    76 4 1 -1 0 0 0 10 0.0000 2 75 75 6000 2745 a\001
    77 4 1 -1 0 0 0 10 0.0000 2 75 75 6000 2445 c\001
    78 4 1 -1 0 0 0 12 0.0000 2 135 315 5100 5325 exit\001
    79 4 1 -1 0 0 0 12 0.0000 2 135 135 3300 3075 A\001
    80 4 1 -1 0 0 0 12 0.0000 2 135 795 3300 4875 condition\001
    81 4 1 -1 0 0 0 12 0.0000 2 135 135 3300 5100 B\001
    82 4 0 -1 0 0 0 12 0.0000 2 135 420 6600 3675 stack\001
    83 4 0 -1 0 0 0 12 0.0000 2 180 750 6600 3225 acceptor/\001
    84 4 0 -1 0 0 0 12 0.0000 2 180 750 6600 3450 signalled\001
    85 4 1 -1 0 0 0 12 0.0000 2 135 795 3300 2850 condition\001
    86 4 1 -1 0 0 0 12 0.0000 2 165 420 6000 1350 entry\001
    87 4 1 -1 0 0 0 12 0.0000 2 135 495 6000 1575 queue\001
    88 4 0 -1 0 0 0 12 0.0000 2 135 525 6300 2400 arrival\001
    89 4 0 -1 0 0 0 12 0.0000 2 135 630 6300 2175 order of\001
    90 4 1 -1 0 0 0 12 0.0000 2 135 525 5100 3675 shared\001
    91 4 1 -1 0 0 0 12 0.0000 2 135 735 5100 3975 variables\001
    92 4 0 0 50 -1 0 11 0.0000 2 165 855 4275 3150 Acceptables\001
    93 4 0 0 50 -1 0 11 0.0000 2 120 165 5775 2700 W\001
    94 4 0 0 50 -1 0 11 0.0000 2 120 135 5775 2400 X\001
    95 4 0 0 50 -1 0 11 0.0000 2 120 105 5775 2100 Z\001
    96 4 0 0 50 -1 0 11 0.0000 2 120 135 5775 1800 Y\001
     74         1575 3150 2175 3150 2175 2850 4125 2850 4125 1650
     754 1 -1 0 0 0 10 0.0000 2 75 75 4425 2745 a\001
     764 1 -1 0 0 0 10 0.0000 2 75 75 4425 2445 c\001
     774 1 -1 0 0 0 12 0.0000 2 135 315 3525 5325 exit\001
     784 1 -1 0 0 0 12 0.0000 2 135 135 1725 3075 A\001
     794 1 -1 0 0 0 12 0.0000 2 135 795 1725 4875 condition\001
     804 1 -1 0 0 0 12 0.0000 2 135 135 1725 5100 B\001
     814 0 -1 0 0 0 12 0.0000 2 135 420 5025 3675 stack\001
     824 0 -1 0 0 0 12 0.0000 2 180 750 5025 3225 acceptor/\001
     834 0 -1 0 0 0 12 0.0000 2 180 750 5025 3450 signalled\001
     844 1 -1 0 0 0 12 0.0000 2 135 795 1725 2850 condition\001
     854 1 -1 0 0 0 12 0.0000 2 165 420 4425 1350 entry\001
     864 1 -1 0 0 0 12 0.0000 2 135 495 4425 1575 queue\001
     874 0 -1 0 0 0 12 0.0000 2 135 525 4725 2400 arrival\001
     884 0 -1 0 0 0 12 0.0000 2 135 630 4725 2175 order of\001
     894 1 -1 0 0 0 12 0.0000 2 135 525 3525 3675 shared\001
     904 1 -1 0 0 0 12 0.0000 2 135 735 3525 3975 variables\001
     914 0 4 50 -1 0 11 0.0000 2 120 135 4150 1875 Y\001
     924 0 4 50 -1 0 11 0.0000 2 120 105 4150 2175 Z\001
     934 0 4 50 -1 0 11 0.0000 2 120 135 4150 2475 X\001
     944 0 4 50 -1 0 11 0.0000 2 120 165 4150 2775 W\001
     954 0 -1 0 0 3 12 0.0000 2 150 540 5025 4275 urgent\001
     964 1 0 50 -1 0 11 0.0000 2 165 600 3150 3150 accepted\001
  • doc/papers/concurrency/figures/monitor.fig

    rd286cf68 r63238a4  
    72722 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    7373         3600 1500 3600 2100 4200 2100 4200 900
    74 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
    75          2700 1500 2700 2100 3300 2100 3300 1500
    76742 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 9
    7775         3600 4200 4800 4200 4800 3300 5400 3300 5400 3000 4800 3000
     
    79772 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5
    8078         4200 3450 4200 2550 2700 2550 2700 3450 4200 3450
     792 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4
     80         2700 1500 2700 2100 3300 2100 3300 1500
    81814 1 -1 0 0 0 10 0.0000 2 75 75 4350 1995 a\001
    82824 1 -1 0 0 0 10 0.0000 2 75 75 4350 1695 c\001
     
    89894 0 -1 0 0 0 12 0.0000 2 180 750 4950 2700 signalled\001
    90904 1 -1 0 0 0 12 0.0000 2 135 795 1650 2100 condition\001
    91 4 1 -1 0 0 0 12 0.0000 2 135 135 2550 1425 X\001
    92 4 1 -1 0 0 0 12 0.0000 2 135 135 3450 1425 Y\001
     914 1 4 0 0 0 12 0.0000 2 135 135 2550 1425 X\001
     924 1 4 0 0 0 12 0.0000 2 135 135 3450 1425 Y\001
    93934 1 -1 0 0 0 12 0.0000 2 165 420 4350 600 entry\001
    94944 1 -1 0 0 0 12 0.0000 2 135 495 4350 825 queue\001
     
    1001004 1 -1 0 0 0 10 0.0000 2 75 75 3450 1995 c\001
    1011014 1 -1 0 0 0 12 0.0000 2 135 570 3000 1200 queues\001
     1024 0 -1 0 0 3 12 0.0000 2 150 540 4950 3525 urgent\001
  • doc/papers/general/Makefile

    rd286cf68 r63238a4  
    5959        dvips ${Build}/$< -o $@
    6060
    61 ${BASE}.dvi : Makefile ${Build} ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    62                 ../../bibliography/pl.bib
     61${BASE}.dvi : Makefile ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     62                ../../bibliography/pl.bib | ${Build}
    6363        # Must have *.aux file containing citations for bibtex
    6464        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
     
    7575        mkdir -p ${Build}
    7676
    77 ${BASE}.out.ps : ${Build}
     77${BASE}.out.ps : | ${Build}
    7878        ln -fs ${Build}/Paper.out.ps .
    7979
     
    8484        gnuplot -e Build="'${Build}/'" evaluation/timing.gp
    8585
    86 %.tex : %.fig ${Build}
     86%.tex : %.fig | ${Build}
    8787        fig2dev -L eepic $< > ${Build}/$@
    8888
    89 %.ps : %.fig ${Build}
     89%.ps : %.fig | ${Build}
    9090        fig2dev -L ps $< > ${Build}/$@
    9191
    92 %.pstex : %.fig ${Build}
     92%.pstex : %.fig | ${Build}
    9393        fig2dev -L pstex $< > ${Build}/$@
    9494        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • doc/proposals/ctordtor/Makefile

    rd286cf68 r63238a4  
    1 ## Define the appropriate configuration variables.
     1## Define the configuration variables.
    22
    3 MACROS = ../../LaTeXmacros
    4 BIB = ../../bibliography
     3Build = build
     4Figures = figures
     5Macros = ../../LaTeXmacros
     6Bib = ../../bibliography
    57
    6 TeXLIB = .:$(MACROS):$(MACROS)/listings:$(MACROS)/enumitem:$(BIB)/:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error
     8TeXLIB = .:${Macros}:${MACROS}/listings:${MACROS}/enumitem:${Bib}/:
     9LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    810BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
     11
     12MAKEFLAGS = --no-print-directory # --silent
     13VPATH = ${Build} ${Figures}
    914
    1015## Define the text source files.
     
    2934
    3035DOCUMENT = ctor.pdf
     36BASE = ${basename ${DOCUMENT}}
    3137
    3238# Directives #
     39
     40.PHONY : all clean                                      # not file names
    3341
    3442all : ${DOCUMENT}
    3543
    3644clean :
    37         rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \
    38                 ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT}
     45        @rm -frv ${DOCUMENT} ${BASE}.ps ${Build}
    3946
    4047# File Dependencies #
    4148
    42 ${DOCUMENT} : ${basename ${DOCUMENT}}.ps
     49${DOCUMENT} : ${BASE}.ps
    4350        ps2pdf $<
    4451
    45 ${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    46         dvips $< -o $@
     52${BASE}.ps : ${BASE}.dvi
     53        dvips ${Build}/$< -o $@
    4754
    48 ${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    49                 $(MACROS)/common.tex $(MACROS)/indexstyle $(BIB)/cfa.bib
     55${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     56                ${Macros}/common.tex ${Macros}/indexstyle ${Bib}/pl.bib | ${Build}
    5057        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    51         if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi
     58        #if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
    5259        # Must have *.aux file containing citations for bibtex
    5360        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    54         -${BibTeX} ${basename $@}
    55         # Some citations reference others so run steps again to resolve these citations
     61        -${BibTeX} ${Build}/${basename $@}
     62        # Some citations reference others so run again to resolve these citations
    5663        ${LaTeX} ${basename $@}.tex
    57         -${BibTeX} ${basename $@}
     64        -${BibTeX} ${Build}/${basename $@}
    5865        # Make index from *.aux entries and input index at end of document
    59         makeindex -s $(MACROS)/indexstyle ${basename $@}.idx
     66        #makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx
     67        # Run again to finish citations
    6068        ${LaTeX} ${basename $@}.tex
    6169        # Run again to get index title into table of contents
     
    6775## Define the default recipes.
    6876
    69 %.tex : %.fig
    70         fig2dev -L eepic $< > $@
     77${Build}:
     78        mkdir -p ${Build}
    7179
    72 %.ps : %.fig
    73         fig2dev -L ps $< > $@
     80%.tex : %.fig | ${Build}
     81        fig2dev -L eepic $< > ${Build}/$@
    7482
    75 %.pstex : %.fig
    76         fig2dev -L pstex $< > $@
    77         fig2dev -L pstex_t -p $@ $< > $@_t
     83%.ps : %.fig | ${Build}
     84        fig2dev -L ps $< > ${Build}/$@
     85
     86%.pstex : %.fig | ${Build}
     87        fig2dev -L pstex $< > ${Build}/$@
     88        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    7889
    7990# Local Variables: #
  • doc/proposals/ctordtor/ctor.tex

    rd286cf68 r63238a4  
    1 % inline code ©...© (copyright symbol) emacs: C-q M-)
    2 % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
    3 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
    4 % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
    5 % LaTex escape §...§ (section symbol) emacs: C-q M-'
    6 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
    7 % math escape $...$ (dollar symbol)
    8 
    91\documentclass[twoside,11pt]{article}
    102
     
    157\usepackage{textcomp}
    168\usepackage[latin1]{inputenc}
     9
    1710\usepackage{fullpage,times,comment}
    1811\usepackage{epic,eepic}
    19 \usepackage{upquote}                                                                    % switch curled `'" to straight
     12\usepackage{upquote}                                    % switch curled `'" to straight
    2013\usepackage{calc}
    2114\usepackage{xspace}
    2215\usepackage{graphicx}
    23 \usepackage{varioref}                                                                   % extended references
    24 \usepackage{listings}                                                                   % format program code
    25 \usepackage[flushmargin]{footmisc}                                              % support label/reference in footnote
     16\usepackage{varioref}                                   % extended references
     17\usepackage{listings}                                   % format program code
     18\usepackage[flushmargin]{footmisc}                      % support label/reference in footnote
    2619\usepackage{latexsym}                                   % \Box glyph
    2720\usepackage{mathptmx}                                   % better math font with "times"
     
    3427\renewcommand{\UrlFont}{\small\sf}
    3528
    36 \setlength{\topmargin}{-0.45in}                                                 % move running title into header
     29\setlength{\topmargin}{-0.45in}                         % move running title into header
    3730\setlength{\headsep}{0.25in}
    3831
     
    4336
    4437\interfootnotelinepenalty=10000
     38
     39\CFAStyle                                               % use default CFA format-style
     40% inline code ©...© (copyright symbol) emacs: C-q M-)
     41% red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
     42% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
     43% green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
     44% LaTex escape §...§ (section symbol) emacs: C-q M-'
     45% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
     46% math escape $...$ (dollar symbol)
     47
    4548
    4649\title{
     
    8386\thispagestyle{plain}
    8487\pagenumbering{arabic}
    85 
    8688
    8789
  • doc/proposals/tuples/Makefile

    rd286cf68 r63238a4  
    1 ## Define the appropriate configuration variables.
     1## Define the configuration variables.
    22
    3 MACROS = ../../LaTeXmacros
    4 BIB = ../../bibliography
     3Build = build
     4Figures = figures
     5Macros = ../../LaTeXmacros
     6Bib = ../../bibliography
    57
    6 TeXLIB = .:$(MACROS):$(MACROS)/listings:$(MACROS)/enumitem:$(BIB)/:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error
     8TeXLIB = .:${Macros}:${MACROS}/listings:${MACROS}/enumitem:${Bib}/:
     9LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    810BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
     11
     12MAKEFLAGS = --no-print-directory --silent #
     13VPATH = ${Build} ${Figures}
    914
    1015## Define the text source files.
     
    2934
    3035DOCUMENT = tuples.pdf
     36BASE = ${basename ${DOCUMENT}}
    3137
    3238# Directives #
     39
     40.PHONY : all clean                                      # not file names
    3341
    3442all : ${DOCUMENT}
    3543
    3644clean :
    37         rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \
    38                 ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT}
     45        @rm -frv ${DOCUMENT} ${BASE}.ps ${Build}
    3946
    4047# File Dependencies #
    4148
    42 ${DOCUMENT} : ${basename ${DOCUMENT}}.ps
     49${DOCUMENT} : ${BASE}.ps
    4350        ps2pdf $<
    4451
    45 ${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    46         dvips $< -o $@
     52${BASE}.ps : ${BASE}.dvi
     53        dvips ${Build}/$< -o $@
    4754
    48 ${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    49                 $(MACROS)/common.tex $(MACROS)/indexstyle $(BIB)/cfa.bib
     55${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     56                ${Macros}/common.tex ${Macros}/indexstyle ${Bib}/pl.bib | ${Build}
    5057        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    51         if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi
     58        #if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
    5259        # Must have *.aux file containing citations for bibtex
    5360        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    54         -${BibTeX} ${basename $@}
    55         # Some citations reference others so run steps again to resolve these citations
     61        -${BibTeX} ${Build}/${basename $@}
     62        # Some citations reference others so run again to resolve these citations
    5663        ${LaTeX} ${basename $@}.tex
    57         -${BibTeX} ${basename $@}
     64        -${BibTeX} ${Build}/${basename $@}
    5865        # Make index from *.aux entries and input index at end of document
    59         makeindex -s $(MACROS)/indexstyle ${basename $@}.idx
     66        #makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx
     67        # Run again to finish citations
    6068        ${LaTeX} ${basename $@}.tex
    6169        # Run again to get index title into table of contents
     
    6775## Define the default recipes.
    6876
    69 %.tex : %.fig
    70         fig2dev -L eepic $< > $@
     77${Build}:
     78        mkdir -p ${Build}
    7179
    72 %.ps : %.fig
    73         fig2dev -L ps $< > $@
     80%.tex : %.fig | ${Build}
     81        fig2dev -L eepic $< > ${Build}/$@
    7482
    75 %.pstex : %.fig
    76         fig2dev -L pstex $< > $@
    77         fig2dev -L pstex_t -p $@ $< > $@_t
     83%.ps : %.fig | ${Build}
     84        fig2dev -L ps $< > ${Build}/$@
     85
     86%.pstex : %.fig | ${Build}
     87        fig2dev -L pstex $< > ${Build}/$@
     88        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    7889
    7990# Local Variables: #
  • doc/proposals/tuples/tuples.tex

    rd286cf68 r63238a4  
    1 % inline code ©...© (copyright symbol) emacs: C-q M-)
    2 % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
    3 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
    4 % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
    5 % LaTex escape §...§ (section symbol) emacs: C-q M-'
    6 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
    7 % math escape $...$ (dollar symbol)
    8 
    91\documentclass[twoside,11pt]{article}
    102
     
    157\usepackage{textcomp}
    168\usepackage[latin1]{inputenc}
     9
    1710\usepackage{fullpage,times,comment}
    1811\usepackage{epic,eepic}
    19 \usepackage{upquote}                                                                    % switch curled `'" to straight
     12\usepackage{upquote}                                    % switch curled `'" to straight
    2013\usepackage{calc}
    2114\usepackage{xspace}
    2215\usepackage{graphicx}
    23 \usepackage{varioref}                                                                   % extended references
    24 \usepackage{listings}                                                                   % format program code
    25 \usepackage[flushmargin]{footmisc}                                              % support label/reference in footnote
     16\usepackage{varioref}                                   % extended references
     17\usepackage{listings}                                   % format program code
     18\usepackage[flushmargin]{footmisc}                      % support label/reference in footnote
    2619\usepackage{latexsym}                                   % \Box glyph
    2720\usepackage{mathptmx}                                   % better math font with "times"
     
    3427\renewcommand{\UrlFont}{\small\sf}
    3528
    36 \setlength{\topmargin}{-0.45in}                                                 % move running title into header
     29\setlength{\topmargin}{-0.45in}                         % move running title into header
    3730\setlength{\headsep}{0.25in}
    3831
     
    4235
    4336\interfootnotelinepenalty=10000
     37
     38\CFAStyle                                               % use default CFA format-style
     39% inline code ©...© (copyright symbol) emacs: C-q M-)
     40% red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
     41% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
     42% green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
     43% LaTex escape §...§ (section symbol) emacs: C-q M-'
     44% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
     45% math escape $...$ (dollar symbol)
     46
    4447
    4548\title{
  • doc/refrat/Makefile

    rd286cf68 r63238a4  
    5353        dvips ${Build}/$< -o $@
    5454
    55 ${BASE}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    56                 ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib
     55${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     56                ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib | ${Build}
    5757        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    5858        if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
     
    7878        mkdir -p ${Build}
    7979
    80 %.tex : %.fig ${Build}
     80%.tex : %.fig | ${Build}
    8181        fig2dev -L eepic $< > ${Build}/$@
    8282
    83 %.ps : %.fig ${Build}
     83%.ps : %.fig | ${Build}
    8484        fig2dev -L ps $< > ${Build}/$@
    8585
    86 %.pstex : %.fig ${Build}
     86%.pstex : %.fig | ${Build}
    8787        fig2dev -L pstex $< > ${Build}/$@
    8888        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • doc/theses/aaron_moss/comp_II/Makefile

    rd286cf68 r63238a4  
    3232
    3333DOCUMENT = comp_II.pdf
     34BASE = ${basename ${DOCUMENT}}
    3435
    3536# Directives #
     
    4041
    4142clean :
    42         @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
     43        @rm -frv ${DOCUMENT} ${BASE}.ps ${Build}
    4344
    4445# File Dependencies #
    4546
    46 ${DOCUMENT} : ${basename ${DOCUMENT}}.ps
     47${DOCUMENT} : ${BASE}.ps
    4748        ps2pdf $<
    4849
    49 ${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
     50${BASE}.ps : ${BASE}.dvi
    5051        dvips ${Build}/$< -o $@
    5152
    52 ${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    53                 ${Macros}/common.tex ${Macros}/indexstyle ../../../bibliography/pl.bib
     53${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     54                ${Macros}/common.tex ${Macros}/indexstyle ../../../bibliography/pl.bib | ${Build}
    5455        # Must have *.aux file containing citations for bibtex
    5556        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
     
    6667        mkdir -p ${Build}
    6768
    68 %.tex : %.fig
     69%.tex : %.fig ${Build}
    6970        fig2dev -L eepic $< > ${Build}/$@
    7071
    71 %.ps : %.fig
     72%.ps : %.fig | ${Build}
    7273        fig2dev -L ps $< > ${Build}/$@
    7374
    74 %.pstex : %.fig
     75%.pstex : %.fig | ${Build}
    7576        fig2dev -L pstex $< > ${Build}/$@
    7677        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • doc/theses/thierry_delisle/Makefile

    rd286cf68 r63238a4  
    5151
    5252DOCUMENT = thesis.pdf
     53BASE = ${basename ${DOCUMENT}}
    5354
    5455# Directives #
     
    5960
    6061clean :
    61         @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
     62        @rm -frv ${DOCUMENT} ${BASE}.ps ${Build}
    6263
    6364# File Dependencies #
    6465
    65 ${DOCUMENT} : ${basename ${DOCUMENT}}.ps
     66${DOCUMENT} : ${BASE}.ps
    6667        ps2pdf $<
    6768
    68 ${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
     69${BASE}.ps : ${BASE}.dvi
    6970        dvips ${Build}/$< -o $@
    7071
    71 ${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    72                 ${Macros}/common.tex ${Macros}/indexstyle annex/local.bib ../../bibliography/pl.bib
     72${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     73                ${Macros}/common.tex ${Macros}/indexstyle annex/local.bib ../../bibliography/pl.bib | ${Build}
    7374        # Must have *.aux file containing citations for bibtex
    7475        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
     
    9192        fig2dev -L eepic $< > ${Build}/$@
    9293
    93 %.ps : %.fig ${Build}
     94%.ps : %.fig | ${Build}
    9495        fig2dev -L ps $< > ${Build}/$@
    9596
    96 %.pstex : %.fig ${Build}
     97%.pstex : %.fig | ${Build}
    9798        fig2dev -L pstex $< > ${Build}/$@
    9899        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • doc/user/Makefile

    rd286cf68 r63238a4  
    5757        dvips ${Build}/$< -o $@
    5858
    59 ${BASE}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
    60                 ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib
     59${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
     60                ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib | ${Build}
    6161        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    6262        if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
     
    7979        mkdir -p ${Build}
    8080
    81 %.tex : %.fig ${Build}
     81%.tex : %.fig | ${Build}
    8282        fig2dev -L eepic $< > ${Build}/$@
    8383
    84 %.ps : %.fig ${Build}
     84%.ps : %.fig | ${Build}
    8585        fig2dev -L ps $< > ${Build}/$@
    8686
    87 %.pstex : %.fig ${Build}
     87%.pstex : %.fig | ${Build}
    8888        fig2dev -L pstex $< > ${Build}/$@
    8989        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
  • src/Parser/TypedefTable.cc

    rd286cf68 r63238a4  
    1010// Created On       : Sat May 16 15:20:13 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 13:17:56 2018
    13 // Update Count     : 192
     12// Last Modified On : Fri Jun 22 06:14:39 2018
     13// Update Count     : 206
    1414//
    1515
     
    7878        debugPrint( cerr << "Adding current at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl );
    7979        auto ret = kindTable.insertAt( scope, identifier, kind );
    80         if ( ! ret.second ) ret.first->second = kind;           // exists => update
     80        //if ( ! ret.second ) ret.first->second = kind;         // exists => update
     81        assert( ret.first->second == kind );                            // exists
    8182} // TypedefTable::addToScope
    8283
    8384void TypedefTable::addToEnclosingScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) {
    84         assert( kindTable.currentScope() >= 1 );
    85         auto scope = kindTable.currentScope() - 1;
    86         debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl );
     85        assert( kindTable.currentScope() >= 1 + level );
     86        auto scope = kindTable.currentScope() - 1 - level;
     87        debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << " level " << level << endl );
    8788        auto ret = kindTable.insertAt( scope, identifier, kind );
    8889        if ( ! ret.second ) ret.first->second = kind;           // exists => update
     
    9192void TypedefTable::enterScope() {
    9293        kindTable.beginScope();
    93         debugPrint( cerr << "Entering scope " << kindTable.currentScope() << endl );
    94         debugPrint( print() );
     94        debugPrint( cerr << "Entering scope " << kindTable.currentScope() << endl; print() );
    9595} // TypedefTable::enterScope
    9696
    9797void TypedefTable::leaveScope() {
    98         debugPrint( cerr << "Leaving scope " << kindTable.currentScope() << endl );
    99         debugPrint( print() );
     98        debugPrint( cerr << "Leaving scope " << kindTable.currentScope() << endl; print() );
    10099        kindTable.endScope();
    101100} // TypedefTable::leaveScope
     
    114113                --scope;
    115114                debugPrint( cerr << endl << "[" << scope << "]" );
    116         }
     115        } // while
    117116        debugPrint( cerr << endl );
    118 }
     117} // TypedefTable::print
    119118
    120119// Local Variables: //
  • src/Parser/TypedefTable.h

    rd286cf68 r63238a4  
    1010// Created On       : Sat May 16 15:24:36 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 12:10:17 2018
    13 // Update Count     : 85
     12// Last Modified On : Fri Jun 22 05:29:58 2018
     13// Update Count     : 86
    1414//
    1515
     
    2525        typedef ScopedMap< std::string, int > KindTable;
    2626        KindTable kindTable;   
     27        unsigned int level = 0;
    2728  public:
    2829        ~TypedefTable();
     
    3738        void leaveScope();
    3839
     40        void up() { level += 1; }
     41        void down() { level -= 1; }
     42
    3943        void print( void ) const;
    4044}; // TypedefTable
  • src/Parser/lex.ll

    rd286cf68 r63238a4  
    1010 * Created On       : Sat Sep 22 08:58:10 2001
    1111 * Last Modified By : Peter A. Buhr
    12  * Last Modified On : Thu Jun  7 08:27:40 2018
    13  * Update Count     : 679
     12 * Last Modified On : Wed Jun 20 09:08:28 2018
     13 * Update Count     : 682
    1414 */
    1515
     
    2525//**************************** Includes and Defines ****************************
    2626
     27// trigger before each matching rule's action
     28#define YY_USER_ACTION \
     29        yylloc.first_line = yylineno; \
     30        yylloc.first_column = column; \
     31        column += yyleng; \
     32        yylloc.last_column = column; \
     33        yylloc.last_line = yylineno; \
     34        yylloc.filename = yyfilename ? yyfilename : "";
    2735unsigned int column = 0;                                                                // position of the end of the last token parsed
    28 #define YY_USER_ACTION yylloc.first_line = yylineno; yylloc.first_column = column; column += yyleng; yylloc.last_column = column; yylloc.last_line = yylineno; yylloc.filename = yyfilename ? yyfilename : "";                          // trigger before each matching rule's action
    2936
    3037#include <string>
     
    4956#define NUMERIC_RETURN(x)       rm_underscore(); RETURN_VAL( x ) // numeric constant
    5057#define KEYWORD_RETURN(x)       RETURN_CHAR( x )                        // keyword
    51 #define QKEYWORD_RETURN(x)      typedefTable.isKind( yytext ); RETURN_VAL(x); // quasi-keyword
     58#define QKEYWORD_RETURN(x)      RETURN_VAL(x);                          // quasi-keyword
    5259#define IDENTIFIER_RETURN()     RETURN_VAL( typedefTable.isKind( yytext ) )
    5360#define ATTRIBUTE_RETURN()      RETURN_VAL( ATTR_IDENTIFIER )
  • src/Parser/parser.yy

    rd286cf68 r63238a4  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 10:07:12 2018
    13 // Update Count     : 3527
     12// Last Modified On : Fri Jun 22 13:59:11 2018
     13// Update Count     : 3586
    1414//
    1515
     
    136136} // build_postfix_name
    137137
    138 bool forall = false, xxx = false;                                               // aggregate have one or more forall qualifiers ?
     138bool forall = false, xxx = false, yyy = false;                  // aggregate have one or more forall qualifiers ?
    139139
    140140// https://www.gnu.org/software/bison/manual/bison.html#Location-Type
     
    304304%type<en> enumerator_value_opt
    305305
    306 %type<decl> exception_declaration external_definition external_definition_list external_definition_list_no_pop_push external_definition_list_opt
     306%type<decl> external_definition external_definition_list external_definition_list_opt
     307
     308%type<decl> exception_declaration
    307309
    308310%type<decl> field_declaration field_declaration_list_opt field_declarator_opt field_declaring_list
     
    18211823        ;
    18221824
     1825fred:
     1826        // empty
     1827                { yyy = false; }
     1828        ;
     1829
    18231830aggregate_type:                                                                                 // struct, union
    18241831        aggregate_key attribute_list_opt '{' field_declaration_list_opt '}'
    18251832                { $$ = DeclarationNode::newAggregate( $1, new string( DeclarationNode::anonymous.newName() ), nullptr, $4, true )->addQualifiers( $2 ); }
    1826         | aggregate_key attribute_list_opt no_attr_identifier
     1833        | aggregate_key attribute_list_opt no_attr_identifier fred
    18271834                {
    18281835                        typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); // create typedef
     
    18311838                }
    18321839          '{' field_declaration_list_opt '}'
    1833                 { $$ = DeclarationNode::newAggregate( $1, $3, nullptr, $6, true )->addQualifiers( $2 ); }
    1834         | aggregate_key attribute_list_opt type_name
     1840                { $$ = DeclarationNode::newAggregate( $1, $3, nullptr, $7, true )->addQualifiers( $2 ); }
     1841        | aggregate_key attribute_list_opt type_name fred
    18351842                {
    18361843                        typedefTable.makeTypedef( *$3->type->symbolic.name, forall ? TYPEGENname : TYPEDEFname ); // create typedef
     
    18391846                }
    18401847          '{' field_declaration_list_opt '}'
    1841                 { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, nullptr, $6, true )->addQualifiers( $2 ); }
     1848                { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, nullptr, $7, true )->addQualifiers( $2 ); }
    18421849        | aggregate_key attribute_list_opt '(' type_list ')' '{' field_declaration_list_opt '}' // CFA
    18431850                { $$ = DeclarationNode::newAggregate( $1, new string( DeclarationNode::anonymous.newName() ), $4, $7, false )->addQualifiers( $2 ); }
     
    18461853
    18471854aggregate_type_nobody:                                                                  // struct, union - {...}
    1848         aggregate_key attribute_list_opt no_attr_identifier
     1855        aggregate_key attribute_list_opt no_attr_identifier fred
    18491856                {
    18501857                        typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname );
     
    18531860                        $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 );
    18541861                }
    1855         | aggregate_key attribute_list_opt type_name
     1862        | aggregate_key attribute_list_opt type_name fred
    18561863                {
    18571864                        // Create new generic declaration with same name as previous forward declaration, where the IDENTIFIER is
     
    18671874aggregate_key:
    18681875        STRUCT
    1869                 { $$ = DeclarationNode::Struct; }
     1876                { yyy = true; $$ = DeclarationNode::Struct; }
    18701877        | UNION
    1871                 { $$ = DeclarationNode::Union; }
     1878                { yyy = true; $$ = DeclarationNode::Union; }
    18721879        | EXCEPTION
    1873                 { $$ = DeclarationNode::Exception; }
     1880                { yyy = true; $$ = DeclarationNode::Exception; }
    18741881        | COROUTINE
    1875                 { $$ = DeclarationNode::Coroutine; }
     1882                { yyy = true; $$ = DeclarationNode::Coroutine; }
    18761883        | MONITOR
    1877                 { $$ = DeclarationNode::Monitor; }
     1884                { yyy = true; $$ = DeclarationNode::Monitor; }
    18781885        | THREAD
    1879                 { $$ = DeclarationNode::Thread; }
     1886                { yyy = true; $$ = DeclarationNode::Thread; }
    18801887        ;
    18811888
     
    23222329
    23232330translation_unit:
    2324         // empty
    2325                 {}                                                                                              // empty input file
     2331        // empty, input file
    23262332        | external_definition_list
    23272333                { parseTree = parseTree ? parseTree->appendList( $1 ) : $1;     }
     
    23372343        ;
    23382344
    2339         // SKULLDUGGERY: Declarations in extern "X" and distribution need to be added to the current lexical scope.
    2340         // However, external_definition_list creates a new scope around each external_definition, but the pop loses all the
    2341         // types in the extern "X" and distribution at the end of the block. This version of external_definition_list does
    2342 
    2343         // not do push/pop for declarations at the level of the extern "X" and distribution block. Any recursive uses of
    2344         // external_definition_list within the extern "X" and distribution block correctly pushes/pops for that scope level.
    2345 external_definition_list_no_pop_push:
    2346         external_definition
    2347         | external_definition_list_no_pop_push
    2348                 { forall = xxx; }
    2349           external_definition
    2350                 { $$ = $1 ? $1->appendList( $3 ) : $3; }
    2351         ;
    2352 
    23532345external_definition_list_opt:
    23542346        // empty
    23552347                { $$ = nullptr; }
    2356         | external_definition_list_no_pop_push
     2348        | external_definition_list
     2349        ;
     2350
     2351up:
     2352                { typedefTable.up(); }
     2353        ;
     2354
     2355down:
     2356                { typedefTable.down(); }
    23572357        ;
    23582358
     
    23742374                        linkage = LinkageSpec::linkageUpdate( yylloc, linkage, $2 );
    23752375                }
    2376           '{' external_definition_list_opt '}'
     2376          '{' up external_definition_list_opt down '}'
    23772377                {
    23782378                        linkage = linkageStack.top();
    23792379                        linkageStack.pop();
    2380                         $$ = $5;
     2380                        $$ = $6;
    23812381                }
    23822382        | type_qualifier_list
    2383                 { if ( $1->type->forall ) xxx = forall = true; } // remember generic type
    2384           '{' external_definition_list_opt '}'                          // CFA, namespace
    2385                 {
    2386                         for ( DeclarationNode * iter = $4; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) {
     2383                {
     2384                        if ( $1->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); }
     2385                        if ( $1->type->forall ) xxx = forall = true; // remember generic type
     2386                }
     2387          '{' up external_definition_list_opt down '}'          // CFA, namespace
     2388                {
     2389                        for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) {
    23872390                                if ( isMangled( iter->linkage ) ) {             // ignore extern "C"
    23882391                                        iter->addQualifiers( $1->clone() );
     
    23912394                        xxx = false;
    23922395                        delete $1;
    2393                         $$ = $4;
     2396                        $$ = $5;
    23942397                }
    23952398        | declaration_qualifier_list
    2396                 { if ( $1->type->forall ) xxx = forall = true; } // remember generic type
    2397           '{' external_definition_list_opt '}'                          // CFA, namespace
    2398                 {
    2399                         for ( DeclarationNode * iter = $4; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) {
     2399                {
     2400                        if ( $1->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); }
     2401                        if ( $1->type->forall ) xxx = forall = true; // remember generic type
     2402                }
     2403          '{' up external_definition_list_opt down '}'          // CFA, namespace
     2404                {
     2405                        for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) {
    24002406                                if ( isMangled( iter->linkage ) ) {             // ignore extern "C"
    24012407                                        iter->addQualifiers( $1->clone() );
     
    24042410                        xxx = false;
    24052411                        delete $1;
    2406                         $$ = $4;
     2412                        $$ = $5;
    24072413                }
    24082414        | declaration_qualifier_list type_qualifier_list
    24092415                {
    2410                         // forall must be in the type_qualifier_list
    2411                         if ( $2->type->forall ) xxx = forall = true; // remember generic type
    2412                 }
    2413           '{' external_definition_list_opt '}'                          // CFA, namespace
    2414                 {
    2415                         for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) {
     2416                        if ( ($1->type && $1->type->qualifiers.val) || $2->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); }
     2417                        if ( ($1->type && $1->type->forall) || $2->type->forall ) xxx = forall = true; // remember generic type
     2418                }
     2419          '{' up external_definition_list_opt down '}'          // CFA, namespace
     2420                {
     2421                        for ( DeclarationNode * iter = $6; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) {
    24162422                                if ( isMangled( iter->linkage ) && isMangled( $2->linkage ) ) { // ignore extern "C"
    24172423                                        iter->addQualifiers( $1->clone() );
     
    24222428                        delete $1;
    24232429                        delete $2;
    2424                         $$ = $5;
     2430                        $$ = $6;
    24252431                }
    24262432        ;
  • src/SynTree/Type.cc

    rd286cf68 r63238a4  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Sep 25 15:16:32 2017
    13 // Update Count     : 38
     12// Last Modified On : Fri Jun 22 10:17:19 2018
     13// Update Count     : 39
    1414//
    1515#include "Type.h"
     
    6969
    7070// These must remain in the same order as the corresponding bit fields.
    71 const char * Type::FuncSpecifiersNames[] = { "inline", "fortran", "_Noreturn" };
     71const char * Type::FuncSpecifiersNames[] = { "inline", "_Noreturn", "fortran" };
    7272const char * Type::StorageClassesNames[] = { "extern", "static", "auto", "register", "_Thread_local" };
    7373const char * Type::QualifiersNames[] = { "const", "restrict", "volatile", "lvalue", "mutex", "_Atomic" };
Note: See TracChangeset for help on using the changeset viewer.