Index: doc/papers/OOPSLA17/Makefile =================================================================== --- doc/papers/OOPSLA17/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/papers/OOPSLA17/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -33,4 +33,5 @@ DOCUMENT = generic_types.pdf +BASE = ${basename ${DOCUMENT}} # Directives # @@ -41,15 +42,16 @@ clean : - @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi +${BASE}.ps : ${BASE}.dvi dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ../../bibliography/pl.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ../../bibliography/pl.bib | ${Build} # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi @@ -63,5 +65,5 @@ ## Define the default recipes. -${Build}: +${Build} : mkdir -p ${Build} @@ -69,11 +71,11 @@ gnuplot -e Build="'${Build}/'" evaluation/timing.gp -%.tex : %.fig +%.tex : %.fig | ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/papers/concurrency/Makefile =================================================================== --- doc/papers/concurrency/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/papers/concurrency/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -20,6 +20,4 @@ FIGURES = ${addsuffix .tex, \ -monitor \ -ext_monitor \ int_monitor \ dependency \ @@ -27,4 +25,6 @@ PICTURES = ${addsuffix .pstex, \ +monitor \ +ext_monitor \ system \ monitor_structs \ @@ -59,12 +59,12 @@ dvips ${Build}/$< -o $@ -${BASE}.dvi : Makefile ${Build} ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ - annex/local.bib ../../bibliography/pl.bib +${BASE}.dvi : Makefile ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + annex/local.bib ../../bibliography/pl.bib | ${Build} # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi - ${BibTeX} ${Build}/${basename $@} + -${BibTeX} ${Build}/${basename $@} # Some citations reference others so run again to resolve these citations ${LaTeX} ${basename $@}.tex - ${BibTeX} ${Build}/${basename $@} + -${BibTeX} ${Build}/${basename $@} # Run again to finish citations ${LaTeX} ${basename $@}.tex @@ -72,20 +72,20 @@ ## Define the default recipes. -${Build}: +${Build} : mkdir -p ${Build} -${BASE}.out.ps: ${Build} +${BASE}.out.ps : | ${Build} ln -fs ${Build}/Paper.out.ps . -WileyNJD-AMA.bst: +WileyNJD-AMA.bst : ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst . -%.tex : %.fig ${Build} +%.tex : %.fig | ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig ${Build} +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig ${Build} +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/papers/concurrency/Paper.tex =================================================================== --- doc/papers/concurrency/Paper.tex (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/papers/concurrency/Paper.tex (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -271,5 +271,5 @@ Hence, there are two problems to be solved: concurrency and parallelism. While these two concepts are often combined, they are distinct, requiring different tools~\cite[\S~2]{Buhr05a}. -Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization. +Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost, and resource utilization. The proposed concurrency API is implemented in a dialect of C, called \CFA. @@ -282,7 +282,7 @@ Extended versions and explanation of the following code examples are available at the \CFA website~\cite{Cforall} or in Moss~\etal~\cite{Moss18}. -\CFA is an extension of ISO-C, and hence, supports all C paradigms. +\CFA is a non-object-oriented extension of ISO-C, and hence, supports all C paradigms. %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. -Like C, the basics of \CFA revolve around structures and routines. +Like C, the building blocks of \CFA are structures and routines. Virtually all of the code generated by the \CFA translator respects C memory layouts and calling conventions. While \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}. @@ -296,5 +296,5 @@ int x = 1, y = 2, z = 3; int * p1 = &x, ** p2 = &p1, *** p3 = &p2, $\C{// pointers to x}$ - `&` r1 = x, `&&` r2 = r1, `&&&` r3 = r2; $\C{// references to x}$ + `&` r1 = x, `&&` r2 = r1, `&&&` r3 = r2; $\C{// references to x}$ int * p4 = &z, `&` r4 = z; @@ -411,8 +411,7 @@ \end{cquote} Overloading is important for \CFA concurrency since the runtime system relies on creating different types to represent concurrency objects. -Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions to prevent name clashes. +Therefore, overloading eliminates long prefixes and other naming conventions to prevent name clashes. As seen in Section~\ref{basics}, routine @main@ is heavily overloaded. - -Variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name: +For example, variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name: \begin{cfa} struct S { int `i`; int j; double m; } s; @@ -428,5 +427,5 @@ } \end{cfa} -For parallel semantics, both @s.i@ and @t.i@ are visible the same type, so only @i@ is ambiguous without qualification. +For parallel semantics, both @s.i@ and @t.i@ are visible with the same type, so only @i@ is ambiguous without qualification. @@ -468,48 +467,4 @@ \end{cquote} While concurrency does not use operator overloading directly, it provides an introduction for the syntax of constructors. - - -\subsection{Parametric Polymorphism} -\label{s:ParametricPolymorphism} - -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. -For example, the following sum routine works for any type that supports construction from 0 and addition: -\begin{cfa} -forall( otype T | { void `?{}`( T *, zero_t ); T `?+?`( T, T ); } ) // constraint type, 0 and + -T sum( T a[$\,$], size_t size ) { - `T` total = { `0` }; $\C{// initialize by 0 constructor}$ - for ( size_t i = 0; i < size; i += 1 ) - total = total `+` a[i]; $\C{// select appropriate +}$ - return total; -} -S sa[5]; -int i = sum( sa, 5 ); $\C{// use S's 0 construction and +}$ -\end{cfa} - -\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: -\begin{cfa} -trait `sumable`( otype T ) { - void `?{}`( T &, zero_t ); $\C{// 0 literal constructor}$ - T `?+?`( T, T ); $\C{// assortment of additions}$ - T ?+=?( T &, T ); - T ++?( T & ); - T ?++( T & ); -}; -forall( otype T `| sumable( T )` ) $\C{// use trait}$ -T sum( T a[$\,$], size_t size ); -\end{cfa} - -Assertions can be @otype@ or @dtype@. -@otype@ refers to a ``complete'' object, \ie an object has a size, default constructor, copy constructor, destructor and an assignment operator. -@dtype@ only guarantees an object has a size and alignment. - -Using the return type for discrimination, it is possible to write a type-safe @alloc@ based on the C @malloc@: -\begin{cfa} -forall( dtype T | sized(T) ) T * alloc( void ) { return (T *)malloc( sizeof(T) ); } -int * ip = alloc(); $\C{// select type and size from left-hand side}$ -double * dp = alloc(); -struct S {...} * sp = alloc(); -\end{cfa} -where the return type supplies the type/size of the allocation, which is impossible in most type systems. @@ -540,6 +495,6 @@ \CFA also provides @new@ and @delete@, which behave like @malloc@ and @free@, in addition to constructing and destructing objects: \begin{cfa} -{ struct S s = {10}; $\C{// allocation, call constructor}$ - ... +{ + ... struct S s = {10}; ... $\C{// allocation, call constructor}$ } $\C{// deallocation, call destructor}$ struct S * s = new(); $\C{// allocation, call constructor}$ @@ -547,5 +502,50 @@ delete( s ); $\C{// deallocation, call destructor}$ \end{cfa} -\CFA concurrency uses object lifetime as a means of synchronization and/or mutual exclusion. +\CFA concurrency uses object lifetime as a means of mutual exclusion and/or synchronization. + + +\subsection{Parametric Polymorphism} +\label{s:ParametricPolymorphism} + +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. +For example, the following sum routine works for any type that supports construction from 0 and addition: +\begin{cfa} +forall( otype T | { void `?{}`( T *, zero_t ); T `?+?`( T, T ); } ) // constraint type, 0 and + +T sum( T a[$\,$], size_t size ) { + `T` total = { `0` }; $\C{// initialize by 0 constructor}$ + for ( size_t i = 0; i < size; i += 1 ) + total = total `+` a[i]; $\C{// select appropriate +}$ + return total; +} +S sa[5]; +int i = sum( sa, 5 ); $\C{// use S's 0 construction and +}$ +\end{cfa} +The 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. + +\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: +\begin{cfa} +trait `sumable`( otype T ) { + void `?{}`( T &, zero_t ); $\C{// 0 literal constructor}$ + T `?+?`( T, T ); $\C{// assortment of additions}$ + T ?+=?( T &, T ); + T ++?( T & ); + T ?++( T & ); +}; +forall( otype T `| sumable( T )` ) $\C{// use trait}$ +T sum( T a[$\,$], size_t size ); +\end{cfa} + +Assertions can be @otype@ or @dtype@. +@otype@ refers to a ``complete'' object, \ie an object has a size, default constructor, copy constructor, destructor and an assignment operator. +@dtype@ only guarantees an object has a size and alignment. + +Using the return type for discrimination, it is possible to write a type-safe @alloc@ based on the C @malloc@: +\begin{cfa} +forall( dtype T | sized(T) ) T * alloc( void ) { return (T *)malloc( sizeof(T) ); } +int * ip = alloc(); $\C{// select type and size from left-hand side}$ +double * dp = alloc(); +struct S {...} * sp = alloc(); +\end{cfa} +where the return type supplies the type/size of the allocation, which is impossible in most type systems. @@ -727,11 +727,7 @@ Using a coroutine, it is possible to express the Fibonacci formula directly without any of the C problems. -Figure~\ref{f:Coroutine3States} creates a @coroutine@ type: -\begin{cfa} -`coroutine` Fib { int fn; }; -\end{cfa} -which provides communication, @fn@, for the \newterm{coroutine main}, @main@, which runs on the coroutine stack, and possibly multiple interface routines @next@. +Figure~\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@. Like 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. -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. +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@. The interface routine @next@, takes a Fibonacci instance and context switches to it using @resume@; on restart, the Fibonacci field, @fn@, contains the next value in the sequence, which is returned. @@ -843,6 +839,6 @@ \end{figure} -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 -However, there is no stack growth because @resume@/@suspend@ context switch to existing stack-frames rather than create new ones. +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. +However,@resume@/@suspend@ context switch to existing stack-frames rather than create new ones so there is no stack growth. \newterm{Symmetric (full) coroutine}s have a coroutine call a resuming routine for another coroutine, which eventually forms a resuming-call cycle. (The trivial cycle is a coroutine resuming itself.) @@ -933,5 +929,5 @@ The producer call to @delivery@ transfers values into the consumer's communication variables, resumes the consumer, and returns the consumer status. For the first resume, @cons@'s stack is initialized, creating local variables retained between subsequent activations of the coroutine. -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). +The 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). The call from the consumer to the @payment@ introduces the cycle between producer and consumer. When @payment@ is called, the consumer copies values into the producer's communication variable and a resume is executed. @@ -963,6 +959,6 @@ \end{cfa} and the programming language (and possibly its tool set, \eg debugger) may need to understand @baseCoroutine@ because of the stack. -Furthermore, the execution of constructs/destructors is in the wrong order for certain operations, \eg for threads; -\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. +Furthermore, the execution of constructs/destructors is in the wrong order for certain operations. +For 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. An alternatively is composition: @@ -984,5 +980,5 @@ symmetric_coroutine<>::yield_type \end{cfa} -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}. +Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthreads@~\cite{pthreads}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}. However, the generic thread-handle (identifier) is limited (few operations), unless it is wrapped in a custom type. \begin{cfa} @@ -1001,5 +997,5 @@ Note, the type @coroutine_t@ must be an abstract handle to the coroutine, because the coroutine descriptor and its stack are non-copyable. Copying the coroutine descriptor results in copies being out of date with the current state of the stack. -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. +Correspondingly, 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. (There is no mechanism in C to find all stack-specific pointers and update them as part of a copy.) @@ -1015,5 +1011,5 @@ Furthermore, implementing coroutines without language supports also displays the power of a programming language. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed without using the language support. -The reserved keyword eases use for the common cases. +The reserved keyword simply eases use for the common cases. Part 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: @@ -1030,5 +1026,5 @@ The @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. The 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. -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@. +The 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@. The \CFA keyword @coroutine@ implicitly implements the getter and forward declarations required for implementing the coroutine main: \begin{cquote} @@ -1098,5 +1094,5 @@ The difference is that a coroutine borrows a thread from its caller, so the first thread resuming a coroutine creates an instance of @main@; whereas, 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{ -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).} +The \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.} No 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. @@ -1189,7 +1185,5 @@ void main( Adder & adder ) with( adder ) { subtotal = 0; - for ( int c = 0; c < cols; c += 1 ) { - subtotal += row[c]; - } + for ( int c = 0; c < cols; c += 1 ) { subtotal += row[c]; } } int main() { @@ -1216,8 +1210,8 @@ Uncontrolled non-deterministic execution is meaningless. -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}. +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}. Since 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). -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}). -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). +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}. +However, 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. Hence, a programmer must learn and manipulate two sets of design patterns. While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account. @@ -1244,6 +1238,6 @@ However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use. Methods 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. -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. -For example, the \CC @std::atomic@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing) for numerical types. +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. +For example, the \CC @std::atomic@ offers an easy way to express mutual-exclusion on a restricted set of operations, \eg reading/writing, for numerical types. However, a significant challenge with locks is composability because it takes careful organization for multiple locks to be used while preventing deadlock. Easing composability is another feature higher-level mutual-exclusion mechanisms can offer. @@ -1254,5 +1248,5 @@ Synchronization enforces relative ordering of execution, and synchronization tools provide numerous mechanisms to establish these timing relationships. Low-level synchronization primitives offer good performance and flexibility at the cost of ease of use; -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. +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. Often 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. If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, that reader has \newterm{barged}. @@ -1272,5 +1266,5 @@ The strong association with the call/return paradigm eases programmability, readability and maintainability, at a slight cost in flexibility and efficiency. -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. +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. Copying 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. Copying 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. @@ -1375,9 +1369,9 @@ \end{cfa} (While object-oriented monitors can be extended with a mutex qualifier for multiple-monitor members, no prior example of this feature could be found.) -In practice, writing multi-locking routines that do not deadlocks is tricky. +In practice, writing multi-locking routines that do not deadlock is tricky. Having language support for such a feature is therefore a significant asset for \CFA. The capability to acquire multiple locks before entering a critical section is called \newterm{bulk acquire}. -In previous example, \CFA guarantees the order of acquisition is consistent across calls to different routines using the same monitors as arguments. +In the previous example, \CFA guarantees the order of acquisition is consistent across calls to different routines using the same monitors as arguments. This consistent ordering means acquiring multiple monitors is safe from deadlock. However, users can force the acquiring order. @@ -1395,5 +1389,5 @@ In the calls to @bar@ and @baz@, the monitors are acquired in opposite order. -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}. +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 rollback semantics~\cite{Dice10}. In \CFA, safety is guaranteed by using bulk acquire of all monitors to shared objects, whereas other monitor systems provide no aid. While \CFA provides only a partial solution, the \CFA partial solution handles many useful cases. @@ -1440,6 +1434,6 @@ -\section{Internal Scheduling} -\label{s:InternalScheduling} +\section{Scheduling} +\label{s:Scheduling} While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed. @@ -1454,4 +1448,5 @@ The appropriate condition lock is signalled to unblock an opposite kind of thread after an element is inserted/removed from the buffer. Signalling is unconditional, because signalling an empty condition lock does nothing. + Signalling semantics cannot have the signaller and signalled thread in the monitor simultaneously, which means: \begin{enumerate} @@ -1463,5 +1458,5 @@ The signalling thread blocks but is marked for urgrent unblocking at the next scheduling point and the signalled thread continues. \end{enumerate} -The first approach is too restrictive, as it precludes solving a reasonable class of problems (\eg dating service). +The first approach is too restrictive, as it precludes solving a reasonable class of problems, \eg dating service. \CFA supports the next two semantics as both are useful. Finally, while it is common to store a @condition@ as a field of the monitor, in \CFA, a @condition@ variable can be created/stored independently. @@ -1539,25 +1534,26 @@ If 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. Threads 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. +% External scheduling is more constrained and explicit, which helps programmers reduce the non-deterministic nature of concurrency. +External scheduling allows users to wait for events from other threads without concern of unrelated events occurring. +The mechnaism can be done in terms of control flow, \eg Ada @accept@ or \uC @_Accept@, or in terms of data, \eg Go channels. +While both mechanisms have strengths and weaknesses, this project uses a control-flow mechanism to stay consistent with other language semantics. +Two 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}). For internal scheduling, non-blocking signalling (as in the producer/consumer example) is used when the signaller is providing the cooperation for a waiting thread; the 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. -The waiter unblocks next, takes the state, and exits the monitor. +The waiter unblocks next, uses/takes the state, and exits the monitor. Blocking signalling is the reverse, where the waiter is providing the cooperation for the signalling thread; the 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. -The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to take the state. +The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to use/take the state. Figure~\ref{f:DatingService} shows a dating service demonstrating the two forms of signalling: non-blocking and blocking. The dating service matches girl and boy threads with matching compatibility codes so they can exchange phone numbers. A thread blocks until an appropriate partner arrives. -The complexity is exchanging phone number in the monitor, -While the non-barging monitor prevents a caller from stealing a phone number, the monitor mutual-exclusion property - -The dating service is an example of a monitor that cannot be written using external scheduling because: - -The example in table \ref{tbl:datingservice} highlights the difference in behaviour. -As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed. -To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example. -This feature removes the need for a second condition variables and simplifies programming. -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. +The complexity is exchanging phone number in the monitor because the monitor mutual-exclusion property prevents exchanging numbers. +For 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. +For 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.. + +The 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; +as well, an arriving thread may not find a partner and must wait, which requires a condition variable, and condition variables imply internal scheduling. \begin{figure} @@ -1655,6 +1651,5 @@ } \end{cfa} -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. -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. +must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the condition queue. Similarly, 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 )@. @@ -1667,8 +1662,8 @@ void foo( M & mutex m1, M & mutex m2 ) { ... wait( `e, m1` ); ... $\C{// release m1, keeping m2 acquired )}$ -void baz( M & mutex m1, M & mutex m2 ) { $\C{// must acquire m1 and m2 )}$ +void bar( M & mutex m1, M & mutex m2 ) { $\C{// must acquire m1 and m2 )}$ ... signal( `e` ); ... \end{cfa} -The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to enter @baz@ to get to the @signal@. +The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to enter @bar@ to get to the @signal@. While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable. @@ -1755,5 +1750,5 @@ However, Figure~\ref{f:OtherWaitingThread} shows this solution is complex depending on other waiters, resulting is choices when the signaller finishes the inner mutex-statement. The 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@. -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. +In 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. Furthermore, there is an execution sequence where the signaller always finds waiter W2, and hence, waiter W1 starves. @@ -1856,14 +1851,10 @@ The 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. Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one. - -\subsubsection{Partial Signalling} \label{partial-sig} \end{comment} +\begin{comment} \section{External scheduling} \label{extsched} -An alternative to internal scheduling is external scheduling (see Table~\ref{tbl:sched}). - -\begin{comment} \begin{table} \begin{tabular}{|c|c|c|} @@ -1929,86 +1920,58 @@ \label{tbl:sched} \end{table} -\end{comment} - -This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency. -Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring. -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). -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. -Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines. -The previous example shows a simple use @_Accept@ versus @wait@/@signal@ and its advantages. -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. For 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. On the other hand, external scheduling guarantees that while routine @P@ is waiting, no other routine than @V@ can acquire the monitor. - -% ====================================================================== -% ====================================================================== +\end{comment} + + \subsection{Loose Object Definitions} -% ====================================================================== -% ====================================================================== -In \uC, a monitor class declaration includes an exhaustive list of monitor operations. -Since \CFA is not object oriented, monitors become both more difficult to implement and less clear for a user: - -\begin{cfa} -monitor A {}; - -void f(A & mutex a); -void g(A & mutex a) { - waitfor(f); // Obvious which f() to wait for -} - -void f(A & mutex a, int); // New different F added in scope -void h(A & mutex a) { - waitfor(f); // Less obvious which f() to wait for -} -\end{cfa} - -Furthermore, external scheduling is an example where implementation constraints become visible from the interface. -Here is the cfa-code for the entering phase of a monitor: -\begin{center} -\begin{tabular}{l} -\begin{cfa} - if monitor is free - enter - elif already own the monitor - continue - elif monitor accepts me - enter - else - block -\end{cfa} -\end{tabular} -\end{center} +\label{s:LooseObjectDefinitions} + +In an object-oriented programming-language, a class includes an exhaustive list of operations. +However, new members can be added via static inheritance or dynaic members, \eg JavaScript~\cite{JavaScript}. +Similarly, monitor routines can be added at any time in \CFA, making it less clear for programmers and more difficult to implement. +\begin{cfa} +monitor M {}; +void `f`( M & mutex m ); +void g( M & mutex m ) { waitfor( `f` ); } $\C{// clear which f}$ +void `f`( M & mutex m, int ); $\C{// different f}$ +void h( M & mutex m ) { waitfor( `f` ); } $\C{// unclear which f}$ +\end{cfa} +Hence, the cfa-code for the entering a monitor looks like: +\begin{cfa} +if ( $\textrm{\textit{monitor is free}}$ ) $\LstCommentStyle{// \color{red}enter}$ +else if ( $\textrm{\textit{already own monitor}}$ ) $\LstCommentStyle{// \color{red}continue}$ +else if ( $\textrm{\textit{monitor accepts me}}$ ) $\LstCommentStyle{// \color{red}enter}$ +else $\LstCommentStyle{// \color{red}block}$ +\end{cfa} For the first two conditions, it is easy to implement a check that can evaluate the condition in a few instructions. -However, a fast check for @monitor accepts me@ is much harder to implement depending on the constraints put on the monitors. -Indeed, monitors are often expressed as an entry queue and some acceptor queue as in Figure~\ref{fig:ClassicalMonitor}. +However, a fast check for \emph{monitor accepts me} is much harder to implement depending on the constraints put on the monitors. +Figure~\ref{fig:ClassicalMonitor} shows monitors are often expressed as an entry (calling) queue, some acceptor queues, and an urgent stack/queue. \begin{figure} \centering -\subfloat[Classical Monitor] { +\subfloat[Classical monitor] { \label{fig:ClassicalMonitor} -{\resizebox{0.45\textwidth}{!}{\input{monitor}}} +{\resizebox{0.45\textwidth}{!}{\input{monitor.pstex_t}}} }% subfloat -\qquad -\subfloat[bulk acquire Monitor] { +\quad +\subfloat[Bulk acquire monitor] { \label{fig:BulkMonitor} -{\resizebox{0.45\textwidth}{!}{\input{ext_monitor}}} +{\resizebox{0.45\textwidth}{!}{\input{ext_monitor.pstex_t}}} }% subfloat -\caption{External Scheduling Monitor} +\caption{Monitor Implementation} +\label{f:MonitorImplementation} \end{figure} -There are other alternatives to these pictures, but in the case of the left picture, implementing a fast accept check is relatively easy. -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. -This approach requires a unique dense ordering of routines with an upper-bound and that ordering must be consistent across translation units. -For OO languages these constraints are common, since objects only offer adding member routines consistently across translation units via inheritance. -However, in \CFA users can extend objects with mutex routines that are only visible in certain translation unit. -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. - -The alternative is to alter the implementation as in Figure~\ref{fig:BulkMonitor}. -Here, the mutex routine called is associated with a thread on the entry queue while a list of acceptable routines is kept separate. -Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions. -Storing an array of accepted routine pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search. -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. - +For 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. +This approach requires a unique dense ordering of routines with a small upper-bound and the ordering must be consistent across translation units. +For 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. + +Figure~\ref{fig:BulkMonitor} shows the \CFA monitor implementation. +The mutex routine called is associated with each thread on the entry queue, while a list of acceptable routines is kept separately. +The 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. + +\begin{comment} \begin{figure} \begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}] @@ -2034,72 +1997,48 @@ In the end, the most flexible approach has been chosen since it allows users to write programs that would otherwise be hard to write. This 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. - -% ====================================================================== -% ====================================================================== +\end{comment} + + \subsection{Multi-Monitor Scheduling} -% ====================================================================== -% ====================================================================== +\label{s:Multi-MonitorScheduling} External scheduling, like internal scheduling, becomes significantly more complex when introducing multi-monitor syntax. -Even in the simplest possible case, some new semantics needs to be established: +Even in the simplest possible case, new semantics needs to be established: \begin{cfa} monitor M {}; - -void f(M & mutex a); - -void g(M & mutex b, M & mutex c) { - waitfor(f); // two monitors M => unknown which to pass to f(M & mutex) -} -\end{cfa} -The obvious solution is to specify the correct monitor as follows: - +void f( M & mutex m1 ); +void g( M & mutex m1, M & mutex m2 ) { + waitfor( f ); $\C{// pass m1 or m2 to f?}$ +} +\end{cfa} +The solution is for the programmer to disambiguate: +\begin{cfa} + waitfor( f, m2 ); $\C{// wait for call to f with argument m2}$ +\end{cfa} +Routine @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@). +This behaviour can be extended to the multi-monitor @waitfor@ statement. \begin{cfa} monitor M {}; - -void f(M & mutex a); - -void g(M & mutex a, M & mutex b) { - // wait for call to f with argument b - waitfor(f, b); -} -\end{cfa} -This syntax is unambiguous. -Both locks are acquired and kept by @g@. -When routine @f@ is called, the lock for monitor @b@ is temporarily transferred from @g@ to @f@ (while @g@ still holds lock @a@). -This behaviour can be extended to the multi-monitor @waitfor@ statement as follows. - -\begin{cfa} -monitor M {}; - -void f(M & mutex a, M & mutex b); - -void g(M & mutex a, M & mutex b) { - // wait for call to f with arguments a and b - waitfor(f, a, b); -} -\end{cfa} - -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. +void f( M & mutex m1, M & mutex m2 ); +void g( M & mutex m1, M & mutex m2 ) { + waitfor( f, m1, m2 ); $\C{// wait for call to f with arguments m1 and m2}$ +} +\end{cfa} +Again, the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired by accepting routine. An important behaviour to note is when a set of monitors only match partially: - \begin{cfa} mutex struct A {}; - mutex struct B {}; - -void g(A & mutex a, B & mutex b) { - waitfor(f, a, b); -} - +void g( A & mutex m1, B & mutex m2 ) { + waitfor( f, m1, m2 ); +} A a1, a2; B b; - void foo() { - g(a1, b); // block on accept -} - + g( a1, b ); // block on accept +} void bar() { - f(a2, b); // fulfill cooperation + f( a2, b ); // fulfill cooperation } \end{cfa} @@ -2108,9 +2047,6 @@ It 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. -% ====================================================================== -% ====================================================================== + \subsection{\protect\lstinline|waitfor| Semantics} -% ====================================================================== -% ====================================================================== Syntactically, the @waitfor@ statement takes a routine identifier and a set of monitors. @@ -2211,9 +2147,7 @@ \end{figure} -% ====================================================================== -% ====================================================================== + \subsection{Waiting For The Destructor} -% ====================================================================== -% ====================================================================== + An interesting use for the @waitfor@ statement is destructor semantics. Indeed, the @waitfor@ statement can accept any @mutex@ routine, which includes the destructor (see section \ref{data}). @@ -2242,12 +2176,6 @@ -% ###### # ###### # # # ####### # ### ##### # # -% # # # # # # # # # # # # # # # ## ## -% # # # # # # # # # # # # # # # # # # -% ###### # # ###### # # # # ##### # # ##### # # # -% # ####### # # ####### # # # # # # # # -% # # # # # # # # # # # # # # # # -% # # # # # # # ####### ####### ####### ####### ### ##### # # \section{Parallelism} + Historically, computer performance was about processor speeds and instruction counts. However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}. @@ -2259,6 +2187,10 @@ While 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. + \section{Paradigms} + + \subsection{User-Level Threads} + A direct improvement on the \textbf{kthread} approach is to use \textbf{uthread}. These threads offer most of the same features that the operating system already provides but can be used on a much larger scale. @@ -2269,5 +2201,7 @@ Examples of languages that support \textbf{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}. + \subsection{Fibers : User-Level Threads Without Preemption} \label{fibers} + A popular variant of \textbf{uthread} is what is often referred to as \textbf{fiber}. However, \textbf{fiber} do not present meaningful semantic differences with \textbf{uthread}. @@ -2278,5 +2212,7 @@ An example of a language that uses fibers is Go~\cite{Go} + \subsection{Jobs and Thread Pools} + An approach on the opposite end of the spectrum is to base parallelism on \textbf{pool}. Indeed, \textbf{pool} offer limited flexibility but at the benefit of a simpler user interface. @@ -2289,5 +2225,7 @@ The gold standard of this implementation is Intel's TBB library~\cite{TBB}. + \subsection{Paradigm Performance} + While 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. Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload. @@ -2297,5 +2235,7 @@ Finally, if the units of uninterrupted work are large, enough the paradigm choice is largely amortized by the actual work done. + \section{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel} + A \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}. It 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. @@ -2305,5 +2245,7 @@ Currently \CFA only supports one \textbf{cfacluster}, the initial one. + \subsection{Future Work: Machine Setup}\label{machine} + While this was not done in the context of this paper, another important aspect of clusters is affinity. While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups. @@ -2311,5 +2253,7 @@ OS 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. + \subsection{Paradigms}\label{cfaparadigms} + Given these building blocks, it is possible to reproduce all three of the popular paradigms. Indeed, \textbf{uthread} is the default paradigm in \CFA. @@ -2319,6 +2263,6 @@ - \section{Behind the Scenes} + There are several challenges specific to \CFA when implementing concurrency. These challenges are a direct result of bulk acquire and loose object definitions. @@ -2337,9 +2281,6 @@ Note 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. -% ====================================================================== -% ====================================================================== + \section{Mutex Routines} -% ====================================================================== -% ====================================================================== The first step towards the monitor implementation is simple @mutex@ routines. @@ -2376,5 +2317,7 @@ \end{figure} + \subsection{Details: Interaction with polymorphism} + Depending 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. However, it is shown that entry-point locking solves most of the issues. @@ -2456,9 +2399,6 @@ Furthermore, 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. -% ====================================================================== -% ====================================================================== + \section{Threading} \label{impl:thread} -% ====================================================================== -% ====================================================================== Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency. @@ -2473,5 +2413,7 @@ \end{figure} + \subsection{Processors} + Parallelism 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. Indeed, any parallelism must go through operating-system libraries. @@ -2481,5 +2423,7 @@ Processors internally use coroutines to take advantage of the existing context-switching semantics. + \subsection{Stack Management} + One of the challenges of this system is to reduce the footprint as much as possible. Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible. @@ -2488,5 +2432,7 @@ In 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. + \subsection{Context Switching} + As 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. To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific routine call. @@ -2502,5 +2448,7 @@ This option is not currently present in \CFA, but the changes required to add it are strictly additive. + \subsection{Preemption} \label{preemption} + Finally, an important aspect for any complete threading system is preemption. As 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. @@ -2536,4 +2484,5 @@ Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel. + \subsection{Scheduler} Finally, an aspect that was not mentioned yet is the scheduling algorithm. @@ -2541,14 +2490,12 @@ Further discussion on scheduling is present in section \ref{futur:sched}. -% ====================================================================== -% ====================================================================== + \section{Internal Scheduling} \label{impl:intsched} -% ====================================================================== -% ====================================================================== + The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:ClassicalMonitor} for convenience): \begin{figure} \begin{center} -{\resizebox{0.4\textwidth}{!}{\input{monitor}}} +{\resizebox{0.4\textwidth}{!}{\input{monitor.pstex_t}}} \end{center} \caption{Traditional illustration of a monitor} Index: doc/papers/concurrency/figures/ext_monitor.fig =================================================================== --- doc/papers/concurrency/figures/ext_monitor.fig (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/papers/concurrency/figures/ext_monitor.fig (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -8,89 +8,89 @@ -2 1200 2 -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 -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 -6 5850 1950 6150 2250 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2100 105 105 6000 2100 6105 2205 -4 1 -1 0 0 0 10 0.0000 2 105 90 6000 2160 d\001 +5 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 1575.000 3450.000 1575 3150 1275 3450 1575 3750 +5 1 0 1 -1 -1 0 0 -1 0.000 0 1 0 0 1575.000 4350.000 1575 4050 1275 4350 1575 4650 +6 4275 1950 4575 2250 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2100 105 105 4425 2100 4530 2205 +4 1 -1 0 0 0 10 0.0000 2 105 90 4425 2160 d\001 -6 -6 5100 2100 5400 2400 -1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 5250 2250 105 105 5250 2250 5355 2250 -4 1 -1 0 0 0 10 0.0000 2 105 120 5250 2295 X\001 +6 4275 1650 4575 1950 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 1800 105 105 4425 1800 4530 1905 +4 1 -1 0 0 0 10 0.0000 2 105 90 4425 1860 b\001 -6 -6 5100 1800 5400 2100 -1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 5250 1950 105 105 5250 1950 5355 1950 -4 1 -1 0 0 0 10 0.0000 2 105 120 5250 2010 Y\001 +6 1495 5445 5700 5655 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 1575 5550 80 80 1575 5550 1655 5630 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 2925 5550 105 105 2925 5550 3030 5655 +1 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 4425 5550 105 105 4425 5550 4530 5655 +4 0 -1 0 0 0 12 0.0000 2 135 1035 3150 5625 blocked task\001 +4 0 -1 0 0 0 12 0.0000 2 135 870 1725 5625 active task\001 +4 0 -1 0 0 0 12 0.0000 2 135 1050 4650 5625 routine mask\001 -6 -6 5850 1650 6150 1950 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 1800 105 105 6000 1800 6105 1905 -4 1 -1 0 0 0 10 0.0000 2 105 90 6000 1860 b\001 +6 3525 1800 3825 2400 +1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 3675 1950 105 105 3675 1950 3780 1950 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 3525 1800 3825 1800 3825 2400 3525 2400 3525 1800 +4 1 4 0 0 0 10 0.0000 2 105 120 3675 2010 Y\001 -6 -6 3070 5445 7275 5655 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3150 5550 80 80 3150 5550 3230 5630 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4500 5550 105 105 4500 5550 4605 5655 -1 3 0 1 -1 -1 0 0 4 0.000 1 0.0000 6000 5550 105 105 6000 5550 6105 5655 -4 0 -1 0 0 0 12 0.0000 2 135 1035 4725 5625 blocked task\001 -4 0 -1 0 0 0 12 0.0000 2 135 870 3300 5625 active task\001 -4 0 -1 0 0 0 12 0.0000 2 135 1050 6225 5625 routine mask\001 +6 3525 2100 3825 2400 +1 3 0 1 -1 -1 1 0 4 0.000 1 0.0000 3675 2250 105 105 3675 2250 3780 2250 +4 1 4 0 0 0 10 0.0000 2 105 120 3675 2295 X\001 -6 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3300 3600 105 105 3300 3600 3405 3705 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3600 3600 105 105 3600 3600 3705 3705 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6600 3900 105 105 6600 3900 6705 4005 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 3900 105 105 6900 3900 7005 4005 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2700 105 105 6000 2700 6105 2805 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6000 2400 105 105 6000 2400 6105 2505 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 5100 4575 80 80 5100 4575 5180 4655 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 1725 3600 105 105 1725 3600 1830 3705 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 2025 3600 105 105 2025 3600 2130 3705 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5025 3900 105 105 5025 3900 5130 4005 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 5325 3900 105 105 5325 3900 5430 4005 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2700 105 105 4425 2700 4530 2805 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4425 2400 105 105 4425 2400 4530 2505 +1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 3525 4575 80 80 3525 4575 3605 4655 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 4050 2925 5475 2925 5475 3225 4050 3225 4050 2925 + 2475 2925 3900 2925 3900 3225 2475 3225 2475 2925 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4 - 3150 3750 3750 3750 3750 4050 3150 4050 + 1575 3750 2175 3750 2175 4050 1575 4050 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 3 - 3150 3450 3750 3450 3900 3675 + 1575 3450 2175 3450 2325 3675 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 - 3750 3150 3600 3375 + 2175 3150 2025 3375 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 3 - 3150 4350 3750 4350 3900 4575 + 1575 4350 2175 4350 2325 4575 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 - 3750 4050 3600 4275 + 2175 4050 2025 4275 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4 - 3150 4650 3750 4650 3750 4950 4950 4950 + 1575 4650 2175 4650 2175 4950 3375 4950 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 - 6450 3750 6300 3975 + 4875 3750 4725 3975 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 2 - 4950 4950 5175 5100 + 3375 4950 3600 5100 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 9 - 5250 4950 6450 4950 6450 4050 7050 4050 7050 3750 6450 3750 - 6450 2850 6150 2850 6150 1650 + 3675 4950 4875 4950 4875 4050 5475 4050 5475 3750 4875 3750 + 4875 2850 4575 2850 4575 1650 2 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5 - 5850 4200 5850 3300 4350 3300 4350 4200 5850 4200 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 + 4275 4200 4275 3300 2775 3300 2775 4200 4275 4200 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 3150 5250 2400 + 3675 3075 3675 2400 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4125 2850 4575 3000 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 3150 3150 3750 3150 3750 2850 5700 2850 5700 1650 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 5700 2850 6150 3000 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 5100 1800 5400 1800 5400 2400 5100 2400 5100 1800 -4 1 -1 0 0 0 10 0.0000 2 75 75 6000 2745 a\001 -4 1 -1 0 0 0 10 0.0000 2 75 75 6000 2445 c\001 -4 1 -1 0 0 0 12 0.0000 2 135 315 5100 5325 exit\001 -4 1 -1 0 0 0 12 0.0000 2 135 135 3300 3075 A\001 -4 1 -1 0 0 0 12 0.0000 2 135 795 3300 4875 condition\001 -4 1 -1 0 0 0 12 0.0000 2 135 135 3300 5100 B\001 -4 0 -1 0 0 0 12 0.0000 2 135 420 6600 3675 stack\001 -4 0 -1 0 0 0 12 0.0000 2 180 750 6600 3225 acceptor/\001 -4 0 -1 0 0 0 12 0.0000 2 180 750 6600 3450 signalled\001 -4 1 -1 0 0 0 12 0.0000 2 135 795 3300 2850 condition\001 -4 1 -1 0 0 0 12 0.0000 2 165 420 6000 1350 entry\001 -4 1 -1 0 0 0 12 0.0000 2 135 495 6000 1575 queue\001 -4 0 -1 0 0 0 12 0.0000 2 135 525 6300 2400 arrival\001 -4 0 -1 0 0 0 12 0.0000 2 135 630 6300 2175 order of\001 -4 1 -1 0 0 0 12 0.0000 2 135 525 5100 3675 shared\001 -4 1 -1 0 0 0 12 0.0000 2 135 735 5100 3975 variables\001 -4 0 0 50 -1 0 11 0.0000 2 165 855 4275 3150 Acceptables\001 -4 0 0 50 -1 0 11 0.0000 2 120 165 5775 2700 W\001 -4 0 0 50 -1 0 11 0.0000 2 120 135 5775 2400 X\001 -4 0 0 50 -1 0 11 0.0000 2 120 105 5775 2100 Z\001 -4 0 0 50 -1 0 11 0.0000 2 120 135 5775 1800 Y\001 + 1575 3150 2175 3150 2175 2850 4125 2850 4125 1650 +4 1 -1 0 0 0 10 0.0000 2 75 75 4425 2745 a\001 +4 1 -1 0 0 0 10 0.0000 2 75 75 4425 2445 c\001 +4 1 -1 0 0 0 12 0.0000 2 135 315 3525 5325 exit\001 +4 1 -1 0 0 0 12 0.0000 2 135 135 1725 3075 A\001 +4 1 -1 0 0 0 12 0.0000 2 135 795 1725 4875 condition\001 +4 1 -1 0 0 0 12 0.0000 2 135 135 1725 5100 B\001 +4 0 -1 0 0 0 12 0.0000 2 135 420 5025 3675 stack\001 +4 0 -1 0 0 0 12 0.0000 2 180 750 5025 3225 acceptor/\001 +4 0 -1 0 0 0 12 0.0000 2 180 750 5025 3450 signalled\001 +4 1 -1 0 0 0 12 0.0000 2 135 795 1725 2850 condition\001 +4 1 -1 0 0 0 12 0.0000 2 165 420 4425 1350 entry\001 +4 1 -1 0 0 0 12 0.0000 2 135 495 4425 1575 queue\001 +4 0 -1 0 0 0 12 0.0000 2 135 525 4725 2400 arrival\001 +4 0 -1 0 0 0 12 0.0000 2 135 630 4725 2175 order of\001 +4 1 -1 0 0 0 12 0.0000 2 135 525 3525 3675 shared\001 +4 1 -1 0 0 0 12 0.0000 2 135 735 3525 3975 variables\001 +4 0 4 50 -1 0 11 0.0000 2 120 135 4150 1875 Y\001 +4 0 4 50 -1 0 11 0.0000 2 120 105 4150 2175 Z\001 +4 0 4 50 -1 0 11 0.0000 2 120 135 4150 2475 X\001 +4 0 4 50 -1 0 11 0.0000 2 120 165 4150 2775 W\001 +4 0 -1 0 0 3 12 0.0000 2 150 540 5025 4275 urgent\001 +4 1 0 50 -1 0 11 0.0000 2 165 600 3150 3150 accepted\001 Index: doc/papers/concurrency/figures/monitor.fig =================================================================== --- doc/papers/concurrency/figures/monitor.fig (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/papers/concurrency/figures/monitor.fig (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -72,6 +72,4 @@ 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4 3600 1500 3600 2100 4200 2100 4200 900 -2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4 - 2700 1500 2700 2100 3300 2100 3300 1500 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 9 3600 4200 4800 4200 4800 3300 5400 3300 5400 3000 4800 3000 @@ -79,4 +77,6 @@ 2 2 1 1 -1 -1 0 0 -1 4.000 0 0 0 0 0 5 4200 3450 4200 2550 2700 2550 2700 3450 4200 3450 +2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 0 0 4 + 2700 1500 2700 2100 3300 2100 3300 1500 4 1 -1 0 0 0 10 0.0000 2 75 75 4350 1995 a\001 4 1 -1 0 0 0 10 0.0000 2 75 75 4350 1695 c\001 @@ -89,6 +89,6 @@ 4 0 -1 0 0 0 12 0.0000 2 180 750 4950 2700 signalled\001 4 1 -1 0 0 0 12 0.0000 2 135 795 1650 2100 condition\001 -4 1 -1 0 0 0 12 0.0000 2 135 135 2550 1425 X\001 -4 1 -1 0 0 0 12 0.0000 2 135 135 3450 1425 Y\001 +4 1 4 0 0 0 12 0.0000 2 135 135 2550 1425 X\001 +4 1 4 0 0 0 12 0.0000 2 135 135 3450 1425 Y\001 4 1 -1 0 0 0 12 0.0000 2 165 420 4350 600 entry\001 4 1 -1 0 0 0 12 0.0000 2 135 495 4350 825 queue\001 @@ -100,2 +100,3 @@ 4 1 -1 0 0 0 10 0.0000 2 75 75 3450 1995 c\001 4 1 -1 0 0 0 12 0.0000 2 135 570 3000 1200 queues\001 +4 0 -1 0 0 3 12 0.0000 2 150 540 4950 3525 urgent\001 Index: doc/papers/general/Makefile =================================================================== --- doc/papers/general/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/papers/general/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -59,6 +59,6 @@ dvips ${Build}/$< -o $@ -${BASE}.dvi : Makefile ${Build} ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ - ../../bibliography/pl.bib +${BASE}.dvi : Makefile ${BASE}.out.ps WileyNJD-AMA.bst ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ../../bibliography/pl.bib | ${Build} # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi @@ -75,5 +75,5 @@ mkdir -p ${Build} -${BASE}.out.ps : ${Build} +${BASE}.out.ps : | ${Build} ln -fs ${Build}/Paper.out.ps . @@ -84,11 +84,11 @@ gnuplot -e Build="'${Build}/'" evaluation/timing.gp -%.tex : %.fig ${Build} +%.tex : %.fig | ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig ${Build} +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig ${Build} +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/proposals/ctordtor/Makefile =================================================================== --- doc/proposals/ctordtor/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/proposals/ctordtor/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -1,10 +1,15 @@ -## Define the appropriate configuration variables. +## Define the configuration variables. -MACROS = ../../LaTeXmacros -BIB = ../../bibliography +Build = build +Figures = figures +Macros = ../../LaTeXmacros +Bib = ../../bibliography -TeXLIB = .:$(MACROS):$(MACROS)/listings:$(MACROS)/enumitem:$(BIB)/: -LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error +TeXLIB = .:${Macros}:${MACROS}/listings:${MACROS}/enumitem:${Bib}/: +LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex + +MAKEFLAGS = --no-print-directory # --silent +VPATH = ${Build} ${Figures} ## Define the text source files. @@ -29,33 +34,36 @@ DOCUMENT = ctor.pdf +BASE = ${basename ${DOCUMENT}} # Directives # + +.PHONY : all clean # not file names all : ${DOCUMENT} clean : - rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \ - ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi - dvips $< -o $@ +${BASE}.ps : ${BASE}.dvi + dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \ - $(MACROS)/common.tex $(MACROS)/indexstyle $(BIB)/cfa.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ${Macros}/common.tex ${Macros}/indexstyle ${Bib}/pl.bib | ${Build} # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. - if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi + #if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi - -${BibTeX} ${basename $@} - # Some citations reference others so run steps again to resolve these citations + -${BibTeX} ${Build}/${basename $@} + # Some citations reference others so run again to resolve these citations ${LaTeX} ${basename $@}.tex - -${BibTeX} ${basename $@} + -${BibTeX} ${Build}/${basename $@} # Make index from *.aux entries and input index at end of document - makeindex -s $(MACROS)/indexstyle ${basename $@}.idx + #makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx + # Run again to finish citations ${LaTeX} ${basename $@}.tex # Run again to get index title into table of contents @@ -67,13 +75,16 @@ ## Define the default recipes. -%.tex : %.fig - fig2dev -L eepic $< > $@ +${Build}: + mkdir -p ${Build} -%.ps : %.fig - fig2dev -L ps $< > $@ +%.tex : %.fig | ${Build} + fig2dev -L eepic $< > ${Build}/$@ -%.pstex : %.fig - fig2dev -L pstex $< > $@ - fig2dev -L pstex_t -p $@ $< > $@_t +%.ps : %.fig | ${Build} + fig2dev -L ps $< > ${Build}/$@ + +%.pstex : %.fig | ${Build} + fig2dev -L pstex $< > ${Build}/$@ + fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t # Local Variables: # Index: doc/proposals/ctordtor/ctor.tex =================================================================== --- doc/proposals/ctordtor/ctor.tex (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/proposals/ctordtor/ctor.tex (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -1,10 +1,2 @@ -% inline code ©...© (copyright symbol) emacs: C-q M-) -% red highlighting ®...® (registered trademark symbol) emacs: C-q M-. -% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ -% green highlighting ¢...¢ (cent symbol) emacs: C-q M-" -% LaTex escape §...§ (section symbol) emacs: C-q M-' -% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^ -% math escape $...$ (dollar symbol) - \documentclass[twoside,11pt]{article} @@ -15,13 +7,14 @@ \usepackage{textcomp} \usepackage[latin1]{inputenc} + \usepackage{fullpage,times,comment} \usepackage{epic,eepic} -\usepackage{upquote} % switch curled `'" to straight +\usepackage{upquote} % switch curled `'" to straight \usepackage{calc} \usepackage{xspace} \usepackage{graphicx} -\usepackage{varioref} % extended references -\usepackage{listings} % format program code -\usepackage[flushmargin]{footmisc} % support label/reference in footnote +\usepackage{varioref} % extended references +\usepackage{listings} % format program code +\usepackage[flushmargin]{footmisc} % support label/reference in footnote \usepackage{latexsym} % \Box glyph \usepackage{mathptmx} % better math font with "times" @@ -34,5 +27,5 @@ \renewcommand{\UrlFont}{\small\sf} -\setlength{\topmargin}{-0.45in} % move running title into header +\setlength{\topmargin}{-0.45in} % move running title into header \setlength{\headsep}{0.25in} @@ -43,4 +36,14 @@ \interfootnotelinepenalty=10000 + +\CFAStyle % use default CFA format-style +% inline code ©...© (copyright symbol) emacs: C-q M-) +% red highlighting ®...® (registered trademark symbol) emacs: C-q M-. +% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ +% green highlighting ¢...¢ (cent symbol) emacs: C-q M-" +% LaTex escape §...§ (section symbol) emacs: C-q M-' +% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^ +% math escape $...$ (dollar symbol) + \title{ @@ -83,5 +86,4 @@ \thispagestyle{plain} \pagenumbering{arabic} - Index: doc/proposals/tuples/Makefile =================================================================== --- doc/proposals/tuples/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/proposals/tuples/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -1,10 +1,15 @@ -## Define the appropriate configuration variables. +## Define the configuration variables. -MACROS = ../../LaTeXmacros -BIB = ../../bibliography +Build = build +Figures = figures +Macros = ../../LaTeXmacros +Bib = ../../bibliography -TeXLIB = .:$(MACROS):$(MACROS)/listings:$(MACROS)/enumitem:$(BIB)/: -LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error +TeXLIB = .:${Macros}:${MACROS}/listings:${MACROS}/enumitem:${Bib}/: +LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex + +MAKEFLAGS = --no-print-directory --silent # +VPATH = ${Build} ${Figures} ## Define the text source files. @@ -29,33 +34,36 @@ DOCUMENT = tuples.pdf +BASE = ${basename ${DOCUMENT}} # Directives # + +.PHONY : all clean # not file names all : ${DOCUMENT} clean : - rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \ - ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi - dvips $< -o $@ +${BASE}.ps : ${BASE}.dvi + dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \ - $(MACROS)/common.tex $(MACROS)/indexstyle $(BIB)/cfa.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ${Macros}/common.tex ${Macros}/indexstyle ${Bib}/pl.bib | ${Build} # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. - if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi + #if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi - -${BibTeX} ${basename $@} - # Some citations reference others so run steps again to resolve these citations + -${BibTeX} ${Build}/${basename $@} + # Some citations reference others so run again to resolve these citations ${LaTeX} ${basename $@}.tex - -${BibTeX} ${basename $@} + -${BibTeX} ${Build}/${basename $@} # Make index from *.aux entries and input index at end of document - makeindex -s $(MACROS)/indexstyle ${basename $@}.idx + #makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx + # Run again to finish citations ${LaTeX} ${basename $@}.tex # Run again to get index title into table of contents @@ -67,13 +75,16 @@ ## Define the default recipes. -%.tex : %.fig - fig2dev -L eepic $< > $@ +${Build}: + mkdir -p ${Build} -%.ps : %.fig - fig2dev -L ps $< > $@ +%.tex : %.fig | ${Build} + fig2dev -L eepic $< > ${Build}/$@ -%.pstex : %.fig - fig2dev -L pstex $< > $@ - fig2dev -L pstex_t -p $@ $< > $@_t +%.ps : %.fig | ${Build} + fig2dev -L ps $< > ${Build}/$@ + +%.pstex : %.fig | ${Build} + fig2dev -L pstex $< > ${Build}/$@ + fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t # Local Variables: # Index: doc/proposals/tuples/tuples.tex =================================================================== --- doc/proposals/tuples/tuples.tex (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/proposals/tuples/tuples.tex (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -1,10 +1,2 @@ -% inline code ©...© (copyright symbol) emacs: C-q M-) -% red highlighting ®...® (registered trademark symbol) emacs: C-q M-. -% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ -% green highlighting ¢...¢ (cent symbol) emacs: C-q M-" -% LaTex escape §...§ (section symbol) emacs: C-q M-' -% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^ -% math escape $...$ (dollar symbol) - \documentclass[twoside,11pt]{article} @@ -15,13 +7,14 @@ \usepackage{textcomp} \usepackage[latin1]{inputenc} + \usepackage{fullpage,times,comment} \usepackage{epic,eepic} -\usepackage{upquote} % switch curled `'" to straight +\usepackage{upquote} % switch curled `'" to straight \usepackage{calc} \usepackage{xspace} \usepackage{graphicx} -\usepackage{varioref} % extended references -\usepackage{listings} % format program code -\usepackage[flushmargin]{footmisc} % support label/reference in footnote +\usepackage{varioref} % extended references +\usepackage{listings} % format program code +\usepackage[flushmargin]{footmisc} % support label/reference in footnote \usepackage{latexsym} % \Box glyph \usepackage{mathptmx} % better math font with "times" @@ -34,5 +27,5 @@ \renewcommand{\UrlFont}{\small\sf} -\setlength{\topmargin}{-0.45in} % move running title into header +\setlength{\topmargin}{-0.45in} % move running title into header \setlength{\headsep}{0.25in} @@ -42,4 +35,14 @@ \interfootnotelinepenalty=10000 + +\CFAStyle % use default CFA format-style +% inline code ©...© (copyright symbol) emacs: C-q M-) +% red highlighting ®...® (registered trademark symbol) emacs: C-q M-. +% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ +% green highlighting ¢...¢ (cent symbol) emacs: C-q M-" +% LaTex escape §...§ (section symbol) emacs: C-q M-' +% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^ +% math escape $...$ (dollar symbol) + \title{ Index: doc/refrat/Makefile =================================================================== --- doc/refrat/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/refrat/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -53,6 +53,6 @@ dvips ${Build}/$< -o $@ -${BASE}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ - ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib | ${Build} # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi @@ -78,11 +78,11 @@ mkdir -p ${Build} -%.tex : %.fig ${Build} +%.tex : %.fig | ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig ${Build} +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig ${Build} +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/theses/aaron_moss/comp_II/Makefile =================================================================== --- doc/theses/aaron_moss/comp_II/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/theses/aaron_moss/comp_II/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -32,4 +32,5 @@ DOCUMENT = comp_II.pdf +BASE = ${basename ${DOCUMENT}} # Directives # @@ -40,16 +41,16 @@ clean : - @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi +${BASE}.ps : ${BASE}.dvi dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ - ${Macros}/common.tex ${Macros}/indexstyle ../../../bibliography/pl.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ${Macros}/common.tex ${Macros}/indexstyle ../../../bibliography/pl.bib | ${Build} # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi @@ -66,11 +67,11 @@ mkdir -p ${Build} -%.tex : %.fig +%.tex : %.fig ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/theses/thierry_delisle/Makefile =================================================================== --- doc/theses/thierry_delisle/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/theses/thierry_delisle/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -51,4 +51,5 @@ DOCUMENT = thesis.pdf +BASE = ${basename ${DOCUMENT}} # Directives # @@ -59,16 +60,16 @@ clean : - @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build} + @rm -frv ${DOCUMENT} ${BASE}.ps ${Build} # File Dependencies # -${DOCUMENT} : ${basename ${DOCUMENT}}.ps +${DOCUMENT} : ${BASE}.ps ps2pdf $< -${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi +${BASE}.ps : ${BASE}.dvi dvips ${Build}/$< -o $@ -${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ - ${Macros}/common.tex ${Macros}/indexstyle annex/local.bib ../../bibliography/pl.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ${Macros}/common.tex ${Macros}/indexstyle annex/local.bib ../../bibliography/pl.bib | ${Build} # Must have *.aux file containing citations for bibtex if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi @@ -91,8 +92,8 @@ fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig ${Build} +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig ${Build} +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: doc/user/Makefile =================================================================== --- doc/user/Makefile (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ doc/user/Makefile (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -57,6 +57,6 @@ dvips ${Build}/$< -o $@ -${BASE}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ - ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib +${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \ + ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib | ${Build} # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run. if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi @@ -79,11 +79,11 @@ mkdir -p ${Build} -%.tex : %.fig ${Build} +%.tex : %.fig | ${Build} fig2dev -L eepic $< > ${Build}/$@ -%.ps : %.fig ${Build} +%.ps : %.fig | ${Build} fig2dev -L ps $< > ${Build}/$@ -%.pstex : %.fig ${Build} +%.pstex : %.fig | ${Build} fig2dev -L pstex $< > ${Build}/$@ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t Index: src/Parser/TypedefTable.cc =================================================================== --- src/Parser/TypedefTable.cc (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ src/Parser/TypedefTable.cc (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -10,6 +10,6 @@ // Created On : Sat May 16 15:20:13 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jun 7 13:17:56 2018 -// Update Count : 192 +// Last Modified On : Fri Jun 22 06:14:39 2018 +// Update Count : 206 // @@ -78,11 +78,12 @@ debugPrint( cerr << "Adding current at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl ); auto ret = kindTable.insertAt( scope, identifier, kind ); - if ( ! ret.second ) ret.first->second = kind; // exists => update + //if ( ! ret.second ) ret.first->second = kind; // exists => update + assert( ret.first->second == kind ); // exists } // TypedefTable::addToScope void TypedefTable::addToEnclosingScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) { - assert( kindTable.currentScope() >= 1 ); - auto scope = kindTable.currentScope() - 1; - debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl ); + assert( kindTable.currentScope() >= 1 + level ); + auto scope = kindTable.currentScope() - 1 - level; + debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << " level " << level << endl ); auto ret = kindTable.insertAt( scope, identifier, kind ); if ( ! ret.second ) ret.first->second = kind; // exists => update @@ -91,11 +92,9 @@ void TypedefTable::enterScope() { kindTable.beginScope(); - debugPrint( cerr << "Entering scope " << kindTable.currentScope() << endl ); - debugPrint( print() ); + debugPrint( cerr << "Entering scope " << kindTable.currentScope() << endl; print() ); } // TypedefTable::enterScope void TypedefTable::leaveScope() { - debugPrint( cerr << "Leaving scope " << kindTable.currentScope() << endl ); - debugPrint( print() ); + debugPrint( cerr << "Leaving scope " << kindTable.currentScope() << endl; print() ); kindTable.endScope(); } // TypedefTable::leaveScope @@ -114,7 +113,7 @@ --scope; debugPrint( cerr << endl << "[" << scope << "]" ); - } + } // while debugPrint( cerr << endl ); -} +} // TypedefTable::print // Local Variables: // Index: src/Parser/TypedefTable.h =================================================================== --- src/Parser/TypedefTable.h (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ src/Parser/TypedefTable.h (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -10,6 +10,6 @@ // Created On : Sat May 16 15:24:36 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jun 7 12:10:17 2018 -// Update Count : 85 +// Last Modified On : Fri Jun 22 05:29:58 2018 +// Update Count : 86 // @@ -25,4 +25,5 @@ typedef ScopedMap< std::string, int > KindTable; KindTable kindTable; + unsigned int level = 0; public: ~TypedefTable(); @@ -37,4 +38,7 @@ void leaveScope(); + void up() { level += 1; } + void down() { level -= 1; } + void print( void ) const; }; // TypedefTable Index: src/Parser/lex.ll =================================================================== --- src/Parser/lex.ll (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ src/Parser/lex.ll (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -10,6 +10,6 @@ * Created On : Sat Sep 22 08:58:10 2001 * Last Modified By : Peter A. Buhr - * Last Modified On : Thu Jun 7 08:27:40 2018 - * Update Count : 679 + * Last Modified On : Wed Jun 20 09:08:28 2018 + * Update Count : 682 */ @@ -25,6 +25,13 @@ //**************************** Includes and Defines **************************** +// trigger before each matching rule's action +#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 : ""; unsigned int column = 0; // position of the end of the last token parsed -#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 #include @@ -49,5 +56,5 @@ #define NUMERIC_RETURN(x) rm_underscore(); RETURN_VAL( x ) // numeric constant #define KEYWORD_RETURN(x) RETURN_CHAR( x ) // keyword -#define QKEYWORD_RETURN(x) typedefTable.isKind( yytext ); RETURN_VAL(x); // quasi-keyword +#define QKEYWORD_RETURN(x) RETURN_VAL(x); // quasi-keyword #define IDENTIFIER_RETURN() RETURN_VAL( typedefTable.isKind( yytext ) ) #define ATTRIBUTE_RETURN() RETURN_VAL( ATTR_IDENTIFIER ) Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ src/Parser/parser.yy (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Jun 7 10:07:12 2018 -// Update Count : 3527 +// Last Modified On : Fri Jun 22 13:59:11 2018 +// Update Count : 3586 // @@ -136,5 +136,5 @@ } // build_postfix_name -bool forall = false, xxx = false; // aggregate have one or more forall qualifiers ? +bool forall = false, xxx = false, yyy = false; // aggregate have one or more forall qualifiers ? // https://www.gnu.org/software/bison/manual/bison.html#Location-Type @@ -304,5 +304,7 @@ %type enumerator_value_opt -%type exception_declaration external_definition external_definition_list external_definition_list_no_pop_push external_definition_list_opt +%type external_definition external_definition_list external_definition_list_opt + +%type exception_declaration %type field_declaration field_declaration_list_opt field_declarator_opt field_declaring_list @@ -1821,8 +1823,13 @@ ; +fred: + // empty + { yyy = false; } + ; + aggregate_type: // struct, union aggregate_key attribute_list_opt '{' field_declaration_list_opt '}' { $$ = DeclarationNode::newAggregate( $1, new string( DeclarationNode::anonymous.newName() ), nullptr, $4, true )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt no_attr_identifier + | aggregate_key attribute_list_opt no_attr_identifier fred { typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); // create typedef @@ -1831,6 +1838,6 @@ } '{' field_declaration_list_opt '}' - { $$ = DeclarationNode::newAggregate( $1, $3, nullptr, $6, true )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt type_name + { $$ = DeclarationNode::newAggregate( $1, $3, nullptr, $7, true )->addQualifiers( $2 ); } + | aggregate_key attribute_list_opt type_name fred { typedefTable.makeTypedef( *$3->type->symbolic.name, forall ? TYPEGENname : TYPEDEFname ); // create typedef @@ -1839,5 +1846,5 @@ } '{' field_declaration_list_opt '}' - { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, nullptr, $6, true )->addQualifiers( $2 ); } + { $$ = DeclarationNode::newAggregate( $1, $3->type->symbolic.name, nullptr, $7, true )->addQualifiers( $2 ); } | aggregate_key attribute_list_opt '(' type_list ')' '{' field_declaration_list_opt '}' // CFA { $$ = DeclarationNode::newAggregate( $1, new string( DeclarationNode::anonymous.newName() ), $4, $7, false )->addQualifiers( $2 ); } @@ -1846,5 +1853,5 @@ aggregate_type_nobody: // struct, union - {...} - aggregate_key attribute_list_opt no_attr_identifier + aggregate_key attribute_list_opt no_attr_identifier fred { typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); @@ -1853,5 +1860,5 @@ $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 ); } - | aggregate_key attribute_list_opt type_name + | aggregate_key attribute_list_opt type_name fred { // Create new generic declaration with same name as previous forward declaration, where the IDENTIFIER is @@ -1867,15 +1874,15 @@ aggregate_key: STRUCT - { $$ = DeclarationNode::Struct; } + { yyy = true; $$ = DeclarationNode::Struct; } | UNION - { $$ = DeclarationNode::Union; } + { yyy = true; $$ = DeclarationNode::Union; } | EXCEPTION - { $$ = DeclarationNode::Exception; } + { yyy = true; $$ = DeclarationNode::Exception; } | COROUTINE - { $$ = DeclarationNode::Coroutine; } + { yyy = true; $$ = DeclarationNode::Coroutine; } | MONITOR - { $$ = DeclarationNode::Monitor; } + { yyy = true; $$ = DeclarationNode::Monitor; } | THREAD - { $$ = DeclarationNode::Thread; } + { yyy = true; $$ = DeclarationNode::Thread; } ; @@ -2322,6 +2329,5 @@ translation_unit: - // empty - {} // empty input file + // empty, input file | external_definition_list { parseTree = parseTree ? parseTree->appendList( $1 ) : $1; } @@ -2337,22 +2343,16 @@ ; - // SKULLDUGGERY: Declarations in extern "X" and distribution need to be added to the current lexical scope. - // However, external_definition_list creates a new scope around each external_definition, but the pop loses all the - // types in the extern "X" and distribution at the end of the block. This version of external_definition_list does - - // not do push/pop for declarations at the level of the extern "X" and distribution block. Any recursive uses of - // external_definition_list within the extern "X" and distribution block correctly pushes/pops for that scope level. -external_definition_list_no_pop_push: - external_definition - | external_definition_list_no_pop_push - { forall = xxx; } - external_definition - { $$ = $1 ? $1->appendList( $3 ) : $3; } - ; - external_definition_list_opt: // empty { $$ = nullptr; } - | external_definition_list_no_pop_push + | external_definition_list + ; + +up: + { typedefTable.up(); } + ; + +down: + { typedefTable.down(); } ; @@ -2374,15 +2374,18 @@ linkage = LinkageSpec::linkageUpdate( yylloc, linkage, $2 ); } - '{' external_definition_list_opt '}' + '{' up external_definition_list_opt down '}' { linkage = linkageStack.top(); linkageStack.pop(); - $$ = $5; + $$ = $6; } | type_qualifier_list - { if ( $1->type->forall ) xxx = forall = true; } // remember generic type - '{' external_definition_list_opt '}' // CFA, namespace - { - for ( DeclarationNode * iter = $4; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + { + if ( $1->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( $1->type->forall ) xxx = forall = true; // remember generic type + } + '{' up external_definition_list_opt down '}' // CFA, namespace + { + for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { if ( isMangled( iter->linkage ) ) { // ignore extern "C" iter->addQualifiers( $1->clone() ); @@ -2391,11 +2394,14 @@ xxx = false; delete $1; - $$ = $4; + $$ = $5; } | declaration_qualifier_list - { if ( $1->type->forall ) xxx = forall = true; } // remember generic type - '{' external_definition_list_opt '}' // CFA, namespace - { - for ( DeclarationNode * iter = $4; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + { + if ( $1->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( $1->type->forall ) xxx = forall = true; // remember generic type + } + '{' up external_definition_list_opt down '}' // CFA, namespace + { + for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { if ( isMangled( iter->linkage ) ) { // ignore extern "C" iter->addQualifiers( $1->clone() ); @@ -2404,14 +2410,14 @@ xxx = false; delete $1; - $$ = $4; + $$ = $5; } | declaration_qualifier_list type_qualifier_list { - // forall must be in the type_qualifier_list - if ( $2->type->forall ) xxx = forall = true; // remember generic type - } - '{' external_definition_list_opt '}' // CFA, namespace - { - for ( DeclarationNode * iter = $5; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { + if ( ($1->type && $1->type->qualifiers.val) || $2->type->qualifiers.val ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( ($1->type && $1->type->forall) || $2->type->forall ) xxx = forall = true; // remember generic type + } + '{' up external_definition_list_opt down '}' // CFA, namespace + { + for ( DeclarationNode * iter = $6; iter != nullptr; iter = (DeclarationNode *)iter->get_next() ) { if ( isMangled( iter->linkage ) && isMangled( $2->linkage ) ) { // ignore extern "C" iter->addQualifiers( $1->clone() ); @@ -2422,5 +2428,5 @@ delete $1; delete $2; - $$ = $5; + $$ = $6; } ; Index: src/SynTree/Type.cc =================================================================== --- src/SynTree/Type.cc (revision d286cf68892dfb231fb65f0127f47f3d593ac9f1) +++ src/SynTree/Type.cc (revision 63238a406594e568d241c92a9157cb2afefce4b1) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Sep 25 15:16:32 2017 -// Update Count : 38 +// Last Modified On : Fri Jun 22 10:17:19 2018 +// Update Count : 39 // #include "Type.h" @@ -69,5 +69,5 @@ // These must remain in the same order as the corresponding bit fields. -const char * Type::FuncSpecifiersNames[] = { "inline", "fortran", "_Noreturn" }; +const char * Type::FuncSpecifiersNames[] = { "inline", "_Noreturn", "fortran" }; const char * Type::StorageClassesNames[] = { "extern", "static", "auto", "register", "_Thread_local" }; const char * Type::QualifiersNames[] = { "const", "restrict", "volatile", "lvalue", "mutex", "_Atomic" };