Changes in / [ea91c42:33218c6]


Ignore:
Files:
23 edited

Legend:

Unmodified
Added
Removed

  • doc/proposals/concurrency/text/concurrency.tex

    rea91c42 r33218c6  
    44% ======================================================================
    55% ======================================================================
    6 Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. 
    7 
    8 Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. 
    9 
    10 An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA. 
     6Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account.
     7
     8Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}.
     9
     10An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA.
    1111
    1212One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct.
    … …  
    101101        }
    102102\end{cfacode}
    103 The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order. 
     103The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order.
    104104
    105105However, such use leads the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlock and is therefore undefined behavior. As shown on several occasion\cit, solving this problem requires:
    … …  
    169169\end{tabular}
    170170\end{center}
    171 Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting. 
     171Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting.
    172172
    173173% ======================================================================
    … …  
    178178Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be complex to support. However, it is shown that entry-point locking solves most of the issues.
    179179
    180 First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. 
    181 
    182 Before looking into complex control flow, it is important to present the difference between the two acquiring options : \gls{callsite-locking} and \gls{entry-point-locking}, i.e. acquiring the monitors before making a mutex routine call or as the first instruction of the mutex routine call. For example:
     180First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines.
     181
     182Before looking into complex control-flow, it is important to present the difference between the two acquiring options : callsite and entry-point locking, i.e. acquiring the monitors before making a mutex routine call or as the first operation of the mutex routine-call. For example:
    183183\begin{center}
    184184\setlength\tabcolsep{1.5pt}
    … …  
    245245\end{center}
    246246
    247 \Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else. Note that the \code{mutex} keyword relies on the resolver rather than another form of language, which mean that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example:
     247\Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else.
     248
     249Note the \code{mutex} keyword relies on the resolver, which means that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example:
    248250\begin{cfacode}
    249251//Incorrect
    250252//T is not a monitor
    251253forall(dtype T)
    252 void foo(T * mutex t); 
     254void foo(T * mutex t);
    253255
    254256//Correct
    255 //this function only works on monitors 
     257//this function only works on monitors
    256258//(any monitor)
    257259forall(dtype T | is_monitor(T))
    258 void bar(T * mutex t)); 
     260void bar(T * mutex t));
    259261\end{cfacode}
    260262
    … …  
    267269In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronisation. With monitors, this is generally achieved with internal or external scheduling as in\cit. Since internal scheduling of single monitors is mostly a solved problem, this proposal concentraits on extending internal scheduling to multiple monitors at once. Indeed, like the \gls{group-acquire} semantics, internal scheduling extends to multiple monitors at once in a way that is natural to the user but requires additional complexity on the implementation side.
    268270
    269 First, Here is a simple example of such a technique:
     271First, here is a simple example of such a technique:
    270272
    271273\begin{cfacode}
    … …  
    289291\end{cfacode}
    290292
    291 There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering. 
     293There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering.
    292294
    293295An important aspect to take into account here is that \CFA does not allow barging, which means that once function \code{bar} releases the monitor, foo is guaranteed to resume immediately after (unless some other thread waited on the same condition). This guarantees offers the benefit of not having to loop arount waits in order to guarantee that a condition is still met. The main reason \CFA offers this guarantee is that users can easily introduce barging if it becomes a necessity but adding barging prevention or barging avoidance is more involved without language support. Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design of \CFA concurrency.
    … …  
    317319\end{pseudo}
    318320\end{multicols}
    319 
    320 The previous example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention.
     321The example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention.
    321322
    322323A direct extension of the previous example is the \gls{group-acquire} version:
    … …  
    337338\end{pseudo}
    338339\end{multicols}
    339 
    340340This version uses \gls{group-acquire} (denoted using the \& symbol), but the presence of multiple monitors does not add a particularly new meaning. Synchronization happens between the two threads in exactly the same way and order. The only difference is that mutual exclusion covers more monitors. On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
    341341
    … …  
    397397\end{center}
    398398
    399 It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 17), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. We are therefore left with three options:
     399It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 16), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. There are three options:
    400400
    401401\subsubsection{Delaying signals}
    402 The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed is what fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single groupd of object. Effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.
     402The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed because this semantics fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single group of object, effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.
    403403\begin{multicols}{2}
    404404Waiter
    … …  
    424424\end{pseudo}
    425425\end{multicols}
    426 However, this solution can become much more complicated depending on what is executed while secretly holding B. Indeed, nothing prevents a user from signalling monitor A on a different condition variable:
     426However, this solution can become much more complicated depending on what is executed while secretly holding B (at line 10). Indeed, nothing prevents a user from signalling monitor A on a different condition variable:
    427427\newpage
    428428\begin{multicols}{2}
    … …  
    459459\end{multicols}
    460460
    461 The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen. Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.
    462 
    463 \paragraph{Case 1: thread 1 will go first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it.
    464 \paragraph{Case 2: thread 2 will go first.} In this case, the problem is that monitor B needs to be passed to thread 1. This can be done directly or using thread 2 as an intermediate.
     461The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen.
     462
     463\paragraph{Case 1: thread 1 goes first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it.
     464\paragraph{Case 2: thread 2 goes first.} In this case, the problem is that monitor B needs to be passed to thread 1, which can be done directly or using thread 2 as an intermediate.
    465465\\
    466466
     467Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.
     468
    467469In both cases however, the threads need to be able to distinguish on a per monitor basis which ones need to be released and which ones need to be transferred. Which means monitors cannot be handled as a single homogenous group.
    468470
    469471\subsubsection{Dependency graphs}
    470 In the Listing 1 pseudo-code, there is a solution which would statisfy both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example the following code which is just a direct extension to three monitors requires at least three ownership transfer and has multiple solutions:
     472In the Listing 1 pseudo-code, there is a solution which statisfies both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example, the following code, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions:
    471473
    472474\begin{multicols}{2}
    … …  
    496498
    497499\subsubsection{Partial signalling}
    498 Finally, the solution that was chosen for \CFA is to use partial signalling. Consider the following case:
     500Finally, the solution that is chosen for \CFA is to use partial signalling. Consider the following case:
    499501
    500502\begin{multicols}{2}
    … …  
    518520\end{pseudo}
    519521\end{multicols}
    520 
    521 The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated in to only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation.
     522The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated into only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation.
    522523
    523524% ======================================================================
    … …  
    526527% ======================================================================
    527528% ======================================================================
    528 An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation. This is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
     529An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
    529530
    530531For example here is an example highlighting the difference in behaviour:
    … …  
    625626        bool inUse;
    626627public:
    627         void P() { 
    628                 if(inUse) wait(c); 
     628        void P() {
     629                if(inUse) wait(c);
    629630                inUse = true;
    630631        }
    631         void V() { 
    632                 inUse = false;         
    633                 signal(c); 
     632        void V() {
     633                inUse = false;
     634                signal(c);
    634635        }
    635636}
    … …  
    639640        bool inUse;
    640641public:
    641         void P() { 
    642                 if(inUse) _Accept(V); 
     642        void P() {
     643                if(inUse) _Accept(V);
    643644                inUse = true;
    644645        }
    645         void g() { 
     646        void g() {
    646647                inUse = false;
    647648

  • doc/proposals/concurrency/version

    rea91c42 r33218c6  
    1 0.9.119
     10.9.122

  • src/CodeGen/CodeGenerator.cc

    rea91c42 r33218c6  
    1313// Update Count     : 485
    1414//
     15#include "CodeGenerator.h"
    1516
    1617#include <cassert>                   // for assert, assertf
    1718#include <list>                      // for _List_iterator, list, list<>::it...
    1819
    19 #include "CodeGenerator.h"
    2020#include "Common/SemanticError.h"    // for SemanticError
    2121#include "Common/UniqueName.h"       // for UniqueName

  • src/CodeGen/GenType.cc

    rea91c42 r33218c6  
    1313// Update Count     : 22
    1414//
     15#include "GenType.h"
    1516
    1617#include <cassert>                // for assert, assertf
    … …  
    1920
    2021#include "CodeGenerator.h"        // for CodeGenerator
    21 #include "GenType.h"
    2222#include "SynTree/Declaration.h"  // for DeclarationWithType
    2323#include "SynTree/Expression.h"   // for Expression

  • src/CodeGen/Generate.cc

    rea91c42 r33218c6  
    1313// Update Count     : 6
    1414//
     15#include "Generate.h"
    1516
    1617#include <iostream>                  // for ostream, endl, operator<<
    … …  
    2021#include "CodeGenerator.h"           // for CodeGenerator, doSemicolon, oper...
    2122#include "GenType.h"                 // for genPrettyType
    22 #include "Generate.h"
    2323#include "Parser/LinkageSpec.h"      // for isBuiltin, isGeneratable
    2424#include "SynTree/BaseSyntaxNode.h"  // for BaseSyntaxNode

  • src/CodeTools/TrackLoc.cc

    rea91c42 r33218c6  
    1616#include "TrackLoc.h"
    1717
    18 #include <cstdlib>                    // for size_t, exit, EXIT_FAILURE
    19 #include <iostream>                   // for operator<<, ostream, basic_ostream
    20 #include <iterator>                   // for back_inserter, inserter
    21 #include <stack>                      // for stack
    22 #include <string>                     // for operator<<, string
    23 #include <typeindex>                  // for type_index
     18#include <cstdlib>                   // for exit, EXIT_FAILURE
     19#include <iostream>                  // for operator<<, ostream, basic_ostream
     20#include <stack>                     // for stack
     21#include <string>                    // for operator<<, string
     22#include <typeindex>                 // for type_index
    2423
    25 #include "Common/PassVisitor.h"       // for PassVisitor
    26 #include "Common/PassVisitor.impl.h"  // for acceptAll
    27 #include "Common/SemanticError.h"     // for SemanticError
    28 #include "Common/utility.h"           // for CodeLocation
    29 #include "SynTree/BaseSyntaxNode.h"   // for BaseSyntaxNode
    30 #include "SynTree/Mutator.h"          // for mutateAll
    31 #include "SynTree/Visitor.h"          // for acceptAll
     24#include "Common/PassVisitor.h"      // for PassVisitor
     25#include "Common/utility.h"          // for CodeLocation
     26#include "SynTree/BaseSyntaxNode.h"  // for BaseSyntaxNode
    3227
    3328class Declaration;
    … …  
    4641                std::stack< CodeLocation * > parents;
    4742        public:
    48                 LocationPrinter(size_t printLevel) : 
     43                LocationPrinter(size_t printLevel) :
    4944                        printLevel(printLevel), lastNode(nullptr)
    5045                {}
    … …  
    6560                                if ( !parents.empty() ) {
    6661                                        node->location = *parents.top();
    67                                 } 
     62                                }
    6863                                else if (nullptr != lastNode) {
    6964                                        node->location = *lastNode;
    70                                 } 
     65                                }
    7166                                else {
    7267                                        std::cerr << "Top level node has no CodeLocation " << name << std::endl;

  • src/Common/PassVisitor.impl.h

    rea91c42 r33218c6  
    11#pragma once
     2// IWYU pragma: private, include "PassVisitor.h"
    23
    34#define VISIT_START( node )                     \

  • src/Common/PassVisitor.proto.h

    rea91c42 r33218c6  
    11#pragma once
     2// IWYU pragma: private, include "PassVisitor.h"
    23
    34template<typename pass_type>

  • src/SymTab/AddVisit.h

    rea91c42 r33218c6  
    1414//
    1515
     16#include "SynTree/Statement.h"
     17
    1618namespace SymTab {
    1719        void addDecls( std::list< Declaration* > &declsToAdd, std::list< Statement* > &statements, std::list< Statement* >::iterator i );
    … …  
    2830
    2931                        if ( stmt == stmts.end() ) break;
    30                        
     32
    3133                        // run mutator on statement
    3234                        maybeAccept( *stmt, visitor );
    … …  
    5961
    6062                        if ( decl == translationUnit.end() ) break;
    61                        
     63
    6264                        // run mutator on declaration
    6365                        maybeAccept( *decl, visitor );

  • src/SymTab/Autogen.cc

    rea91c42 r33218c6  
    1313// Update Count     : 62
    1414//
    15 
    16 #include <list>
    17 #include <iterator>
    18 #include "SynTree/Visitor.h"
    19 #include "SynTree/Type.h"
    20 #include "SynTree/Statement.h"
    21 #include "SynTree/TypeSubstitution.h"
    22 #include "Common/utility.h"
    23 #include "AddVisit.h"
    24 #include "MakeLibCfa.h"
    2515#include "Autogen.h"
    26 #include "GenPoly/ScopedSet.h"
    27 #include "Common/ScopedMap.h"
    28 #include "SymTab/Mangler.h"
    29 #include "GenPoly/DeclMutator.h"
     16
     17#include <algorithm>               // for count_if
     18#include <cassert>                 // for safe_dynamic_cast, assert, assertf
     19#include <iterator>                // for back_insert_iterator, back_inserter
     20#include <list>                    // for list, _List_iterator, list<>::iter...
     21#include <set>                     // for set, _Rb_tree_const_iterator
     22#include <vector>                  // for vector
     23
     24#include "AddVisit.h"              // for addVisit
     25#include "Common/ScopedMap.h"      // for ScopedMap<>::const_iterator, Scope...
     26#include "Common/utility.h"        // for cloneAll, operator+
     27#include "GenPoly/DeclMutator.h"   // for DeclMutator
     28#include "GenPoly/ScopedSet.h"     // for ScopedSet, ScopedSet<>::iterator
     29#include "SymTab/Mangler.h"        // for Mangler
     30#include "SynTree/Mutator.h"       // for maybeMutate
     31#include "SynTree/Statement.h"     // for CompoundStmt, ReturnStmt, ExprStmt
     32#include "SynTree/Type.h"          // for FunctionType, Type, TypeInstType
     33#include "SynTree/Visitor.h"       // for maybeAccept, Visitor, acceptAll
     34
     35class Attribute;
    3036
    3137namespace SymTab {
    … …  
    512518                // Make function polymorphic in same parameters as generic union, if applicable
    513519                const std::list< TypeDecl* > & typeParams = aggregateDecl->get_parameters(); // List of type variables to be placed on the generated functions
    514                
     520
    515521                // default ctor/dtor need only first parameter
    516522                // void ?{}(T *); void ^?{}(T *);

  • src/SymTab/Autogen.h

    rea91c42 r33218c6  
    1616#pragma once
    1717
    18 #include <string>
    19 #include "SynTree/Statement.h"
    20 #include "SynTree/Expression.h"
    21 #include "SynTree/Declaration.h"
    22 #include "SynTree/Initializer.h"
    23 #include "InitTweak/InitTweak.h"
     18#include <cassert>                // for assert
     19#include <iterator>               // for back_insert_iterator, back_inserter
     20#include <list>                   // for list
     21#include <string>                 // for string, operator==
     22
     23#include "Common/UniqueName.h"    // for UniqueName
     24#include "InitTweak/InitTweak.h"  // for InitExpander
     25#include "Parser/LinkageSpec.h"   // for C
     26#include "SynTree/Constant.h"     // for Constant
     27#include "SynTree/Declaration.h"  // for ObjectDecl, Declaration (ptr only)
     28#include "SynTree/Expression.h"   // for UntypedExpr, NameExpr, VariableExpr
     29#include "SynTree/Initializer.h"  // for SingleInit
     30#include "SynTree/Label.h"        // for Label, noLabels
     31#include "SynTree/Statement.h"    // for Statement (ptr only), CompoundStmt
     32#include "SynTree/Type.h"         // for Type, ArrayType, Type::Qualifiers
    2433
    2534namespace SymTab {
    … …  
    154163                if ( isUnnamedBitfield( obj ) ) return;
    155164
    156                 bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && obj->get_bitfieldWidth() == NULL ) );
     165                bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && ! obj->get_bitfieldWidth() ) );
    157166                std::list< Statement * > stmts;
    158167                genCall( srcParam, dstParam, fname, back_inserter( stmts ), obj->get_type(), addCast, forward );

  • src/SymTab/FixFunction.cc

    rea91c42 r33218c6  
    1515
    1616#include "FixFunction.h"
    17 #include "SynTree/Declaration.h"
    18 #include "SynTree/Type.h"
    19 #include "SynTree/Expression.h"
    20 #include "Common/utility.h"
     17
     18#include <list>                   // for list
     19
     20#include "Common/utility.h"       // for maybeClone
     21#include "SynTree/Declaration.h"  // for FunctionDecl, ObjectDecl, Declarati...
     22#include "SynTree/Type.h"         // for ArrayType, PointerType, Type, Basic...
    2123
    2224namespace SymTab {

  • src/SymTab/FixFunction.h

    rea91c42 r33218c6  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // FixFunction.h -- 
     7// FixFunction.h --
    88//
    99// Author           : Richard C. Bilson
    … …  
    1616#pragma once
    1717
    18 #include "SynTree/Mutator.h"
     18#include "SynTree/Mutator.h"  // for Mutator
     19#include "SynTree/SynTree.h"  // for Types
    1920
    2021namespace SymTab {
    … …  
    4344                virtual Type* mutate(ZeroType *zeroType);
    4445                virtual Type* mutate(OneType *oneType);
    45  
     46
    4647                bool isVoid;
    4748        };

  • src/SymTab/ImplementationType.cc

    rea91c42 r33218c6  
    1515
    1616#include "ImplementationType.h"
    17 #include "SynTree/Type.h"
    18 #include "SynTree/Declaration.h"
    19 #include "SynTree/Visitor.h"
    20 #include "SymTab/Indexer.h"
    21 #include "Common/utility.h"
     17
     18#include <list>                   // for list, _List_iterator, list<>::iterator
     19
     20#include "SymTab/Indexer.h"       // for Indexer
     21#include "SynTree/Declaration.h"  // for NamedTypeDecl
     22#include "SynTree/Type.h"         // for TupleType, Type, ArrayType, Pointer...
     23#include "SynTree/Visitor.h"      // for Visitor
    2224
    2325

  • src/SymTab/ImplementationType.h

    rea91c42 r33218c6  
    1616#pragma once
    1717
    18 #include "SynTree/SynTree.h"
    19 #include "SymTab/Indexer.h"
     18class Type;
    2019
    2120namespace SymTab {
     21class Indexer;
     22
    2223        Type *implementationType( Type *, const SymTab::Indexer &indexer );
    2324

  • src/SymTab/Indexer.cc

    rea91c42 r33218c6  
    1616#include "Indexer.h"
    1717
    18 #include <string>
    19 #include <typeinfo>
    20 #include <unordered_map>
    21 #include <unordered_set>
    22 #include <utility>
    23 #include <algorithm>
    24 
    25 #include "Mangler.h"
    26 
    27 #include "Common/utility.h"
    28 
    29 #include "ResolvExpr/typeops.h"
    30 
    31 #include "SynTree/Declaration.h"
    32 #include "SynTree/Type.h"
    33 #include "SynTree/Expression.h"
    34 #include "SynTree/Initializer.h"
    35 #include "SynTree/Statement.h"
    36 
    37 #include "InitTweak/InitTweak.h"
     18#include <cassert>                 // for assert, safe_dynamic_cast
     19#include <iostream>                // for operator<<, basic_ostream, ostream
     20#include <string>                  // for string, operator<<, operator!=
     21#include <unordered_map>           // for operator!=, unordered_map<>::const...
     22#include <unordered_set>           // for unordered_set
     23#include <utility>                 // for pair, make_pair, move
     24
     25#include "Common/SemanticError.h"  // for SemanticError
     26#include "Common/utility.h"        // for cloneAll
     27#include "InitTweak/InitTweak.h"   // for isConstructor, isCopyFunction, isC...
     28#include "Mangler.h"               // for Mangler
     29#include "Parser/LinkageSpec.h"    // for isMangled, isOverridable, Spec
     30#include "ResolvExpr/typeops.h"    // for typesCompatible
     31#include "SynTree/Constant.h"      // for Constant
     32#include "SynTree/Declaration.h"   // for DeclarationWithType, FunctionDecl
     33#include "SynTree/Expression.h"    // for Expression, ImplicitCopyCtorExpr
     34#include "SynTree/Initializer.h"   // for Initializer
     35#include "SynTree/Statement.h"     // for CompoundStmt, Statement, ForStmt (...
     36#include "SynTree/Type.h"          // for Type, StructInstType, UnionInstType
    3837
    3938#define debugPrint(x) if ( doDebug ) { std::cout << x; }

  • src/SymTab/Indexer.h

    rea91c42 r33218c6  
    1616#pragma once
    1717
    18 #include <list>
    19 #include <string>
     18#include <iosfwd>             // for ostream
     19#include <list>               // for list
     20#include <string>             // for string
    2021
    21 #include "SynTree/Visitor.h"
     22#include "SynTree/Visitor.h"  // for Visitor
     23#include "SynTree/SynTree.h"  // for AST nodes
    2224
    2325namespace SymTab {
    … …  
    125127
    126128                struct Impl;
     129
    127130                Impl *tables;         ///< Copy-on-write instance of table data structure
    128131                unsigned long scope;  ///< Scope index of this pointer

  • src/SymTab/Mangler.cc

    rea91c42 r33218c6  
    1313// Update Count     : 21
    1414//
    15 
    16 #include <cassert>
    17 #include <string>
    18 #include <algorithm>
    19 #include <iterator>
    20 #include <functional>
    21 #include <set>
    22 
    23 #include "SynTree/Declaration.h"
    24 #include "SynTree/Type.h"
    25 #include "SynTree/Expression.h"
    26 #include "SynTree/Initializer.h"
    27 #include "SynTree/Statement.h"
    2815#include "Mangler.h"
    29 #include "CodeGen/OperatorTable.h"
     16
     17#include <algorithm>                // for copy, transform
     18#include <cassert>                  // for assert, assertf
     19#include <functional>               // for const_mem_fun_t, mem_fun
     20#include <iterator>                 // for ostream_iterator, back_insert_ite...
     21#include <list>                     // for _List_iterator, list, _List_const...
     22#include <string>                   // for string, operator<<, basic_string
     23
     24#include "CodeGen/OperatorTable.h"  // for OperatorInfo, operatorLookup
     25#include "Common/utility.h"         // for toString
     26#include "Parser/LinkageSpec.h"     // for Spec, isOverridable, AutoGen, Int...
     27#include "SynTree/Declaration.h"    // for TypeDecl, DeclarationWithType
     28#include "SynTree/Expression.h"     // for TypeExpr, Expression, operator<<
     29#include "SynTree/Type.h"           // for Type, ReferenceToType, Type::Fora...
    3030
    3131namespace SymTab {

  • src/SymTab/Mangler.h

    rea91c42 r33218c6  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // Mangler.h -- 
     7// Mangler.h --
    88//
    99// Author           : Richard C. Bilson
    … …  
    1616#pragma once
    1717
    18 #include <sstream>
    19 #include "SynTree/SynTree.h"
    20 #include "SynTree/Visitor.h"
     18#include <map>                // for map, map<>::value_compare
     19#include <sstream>            // for ostringstream
     20#include <string>             // for string
     21#include <utility>            // for pair
     22
     23#include "SynTree/SynTree.h"  // for Types
     24#include "SynTree/Visitor.h"  // for Visitor, maybeAccept
    2125
    2226namespace SymTab {
    … …  
    4751                virtual void visit( ZeroType *zeroType );
    4852                virtual void visit( OneType *oneType );
    49  
     53
    5054                std::string get_mangleName() { return mangleName.str(); }
    5155          private:
    … …  
    5761                bool mangleOverridable;         ///< Specially mangle overridable built-in methods
    5862                bool typeMode;                  ///< Produce a unique mangled name for a type
    59  
     63
    6064                Mangler( bool mangleOverridable, bool typeMode );
    6165                Mangler( const Mangler & );
    62  
     66
    6367                void mangleDecl( DeclarationWithType *declaration );
    6468                void mangleRef( ReferenceToType *refType, std::string prefix );
    6569                void mangleGenericRef( ReferenceToType *refType, std::string prefix );
    66  
     70
    6771                void printQualifiers( Type *type );
    6872        }; // Mangler

  • src/SymTab/TypeEquality.cc

    rea91c42 r33218c6  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // TypeEquality.cc -- 
     7// TypeEquality.cc --
    88//
    99// Author           : Rob Schluntz
    … …  
    1313// Update Count     : 37
    1414//
    15 
    16 #include <list>
    17 #include <iterator>
    18 #include "Validate.h"
    19 #include "SynTree/Visitor.h"
    20 #include "SynTree/Type.h"
    21 #include "SynTree/Statement.h"
    22 #include "SynTree/TypeSubstitution.h"
    23 #include "Indexer.h"
    2415#include "TypeEquality.h"
     16
     17#include <cassert>                // for assert
     18#include <list>                   // for list, list<>::iterator, _List_iterator
     19#include <string>                 // for operator==, string, basic_string
     20
     21#include "SynTree/Constant.h"     // for Constant
     22#include "SynTree/Declaration.h"  // for DeclarationWithType
     23#include "SynTree/Expression.h"   // for ConstantExpr, Expression
     24#include "SynTree/Type.h"         // for Type, ArrayType, FunctionType, Enum...
     25#include "SynTree/Visitor.h"      // for Visitor
    2526
    2627namespace SymTab {
    2728        class TypeEquality : public Visitor {
    2829  public:
    29                 TypeEquality( Type * other, bool vlaErr ) : result( true ), other( other ), 
     30                TypeEquality( Type * other, bool vlaErr ) : result( true ), other( other ),
    3031                        vlaErr( vlaErr ) {}
    3132                bool result;
    … …  
    7172                handleQualifiers( basicType );
    7273                if ( BasicType * bt = dynamic_cast< BasicType * >( other ) ) {
    73                         result = result && basicType->get_kind() == bt->get_kind(); 
     74                        result = result && basicType->get_kind() == bt->get_kind();
    7475                } else {
    7576                        result = false;
    … …  
    9899
    99100                        if ( vlaErr ) {
    100                                 // useful for comparing typedef types - in this case, we 
     101                                // useful for comparing typedef types - in this case, we
    101102                                // want types to appear distinct if either is a VLA type
    102103                                if ( arrayType->get_isVarLen() || at->get_isVarLen() ) {
    … …  
    146147
    147148                        // parameter types must be equivalent
    148                         it1 = funcType->get_parameters().begin(); 
     149                        it1 = funcType->get_parameters().begin();
    149150                        it2 = ft->get_parameters().begin();
    150151                        for ( ; it1 != funcType->get_parameters().end(); ++it1, ++it2 ) {

  • src/SymTab/TypeEquality.h

    rea91c42 r33218c6  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // TypeEquality.h -- 
     7// TypeEquality.h --
    88//
    99// Author           : Rob Schluntz
    … …  
    1414//
    1515
     16class Type;
     17
    1618namespace SymTab {
    1719  // compare types t1 and t2 for equality
    18   // if vlaErr is true, then if at least one of the types is a 
    19   // variable-length array type, then the result will be false 
     20  // if vlaErr is true, then if at least one of the types is a
     21  // variable-length array type, then the result will be false
    2022  bool typeEquals( Type * t1, Type * t2, bool vlaErr = false );
    2123} // namespace SymTab

  • src/SymTab/Validate.cc

    rea91c42 r33218c6  
    3838//   definition occurs later in the input.
    3939
    40 #include <algorithm>
    41 #include <iterator>
    42 #include <list>
    43 
    44 #include "CodeGen/CodeGenerator.h"
    45 
    46 #include "Common/PassVisitor.h"
    47 #include "Common/ScopedMap.h"
    48 #include "Common/UniqueName.h"
    49 #include "Common/utility.h"
    50 
    51 #include "Concurrency/Keywords.h"
    52 
    53 #include "GenPoly/DeclMutator.h"
    54 
    55 #include "InitTweak/InitTweak.h"
    56 
    57 #include "AddVisit.h"
    58 #include "Autogen.h"
    59 #include "FixFunction.h"
    60 // #include "ImplementationType.h"
    61 #include "Indexer.h"
    62 #include "MakeLibCfa.h"
    63 #include "TypeEquality.h"
    6440#include "Validate.h"
    6541
    66 #include "ResolvExpr/typeops.h"
    67 
    68 #include "SynTree/Attribute.h"
    69 #include "SynTree/Expression.h"
    70 #include "SynTree/Mutator.h"
    71 #include "SynTree/Statement.h"
    72 #include "SynTree/Type.h"
    73 #include "SynTree/TypeSubstitution.h"
    74 #include "SynTree/Visitor.h"
     42#include <cstddef>                     // for size_t
     43#include <algorithm>                   // for move, transform
     44#include <cassert>                     // for safe_dynamic_cast, assertf
     45#include <iterator>                    // for back_inserter, inserter, back_...
     46#include <list>                        // for list, _List_iterator, list<>::...
     47#include <map>                         // for _Rb_tree_iterator, map, map<>:...
     48#include <memory>                      // for unique_ptr, allocator
     49#include <string>                      // for string, operator+, operator==
     50#include <tuple>                       // for get
     51#include <utility>                     // for pair, make_pair
     52
     53#include "AddVisit.h"                  // for addVisit
     54#include "Autogen.h"                   // for SizeType, autogenerateRoutines
     55#include "CodeGen/CodeGenerator.h"     // for genName
     56#include "Common/PassVisitor.h"        // for PassVisitor, WithDeclsToAdd
     57#include "Common/ScopedMap.h"          // for ScopedMap<>::const_iterator
     58#include "Common/SemanticError.h"      // for SemanticError
     59#include "Common/UniqueName.h"         // for UniqueName
     60#include "Common/utility.h"            // for operator+, cloneAll, deleteAll
     61#include "Concurrency/Keywords.h"      // for applyKeywords, implementMutexF...
     62#include "FixFunction.h"               // for FixFunction
     63#include "Indexer.h"                   // for Indexer
     64#include "InitTweak/InitTweak.h"       // for isCtorDtor, isCtorDtorAssign
     65#include "Parser/LinkageSpec.h"        // for C, Cforall
     66#include "ResolvExpr/typeops.h"        // for extractResultType, typesCompat...
     67#include "SynTree/Attribute.h"         // for Attribute
     68#include "SynTree/Constant.h"          // for Constant
     69#include "SynTree/Declaration.h"       // for EnumDecl, StructDecl, UnionDecl
     70#include "SynTree/Expression.h"        // for TypeExpr, CompoundLiteralExpr
     71#include "SynTree/Initializer.h"       // for ListInit, Initializer, noDesig...
     72#include "SynTree/Mutator.h"           // for mutateAll, Mutator
     73#include "SynTree/Statement.h"         // for CompoundStmt, DeclStmt, Return...
     74#include "SynTree/Type.h"              // for Type, TypeInstType, TraitInstType
     75#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution, applySubstit...
     76#include "SynTree/Visitor.h"           // for acceptAll, Visitor
    7577
    7678#define debugPrint( x ) if ( doDebug ) { std::cout << x; }
    … …  
    605607                // a return statement in a void-returning function in C. The expression is treated as if it
    606608                // were cast to void.
    607                 if ( returnStmt->get_expr() == NULL && returnVals.size() != 0 ) {
     609                if ( ! returnStmt->get_expr() && returnVals.size() != 0 ) {
    608610                        throw SemanticError( "Non-void function returns no values: " , returnStmt );
    609611                }
    … …  
    836838        void validateGeneric( Aggr * inst ) {
    837839                std::list< TypeDecl * > * params = inst->get_baseParameters();
    838                 if ( params != NULL ) {
     840                if ( params ) {
    839841                        std::list< Expression * > & args = inst->get_parameters();
    840842
    … …  
    937939        void ArrayLength::previsit( ObjectDecl * objDecl ) {
    938940                if ( ArrayType * at = dynamic_cast< ArrayType * >( objDecl->get_type() ) ) {
    939                         if ( at->get_dimension() != nullptr ) return;
     941                        if ( at->get_dimension() ) return;
    940942                        if ( ListInit * init = dynamic_cast< ListInit * >( objDecl->get_init() ) ) {
    941943                                at->set_dimension( new ConstantExpr( Constant::from_ulong( init->get_initializers().size() ) ) );

  • src/SymTab/Validate.h

    rea91c42 r33218c6  
    1717#pragma once
    1818
    19 #include "SynTree/SynTree.h"
     19#include <list>  // for list
     20
     21class Declaration;
     22class Type;
    2023
    2124namespace SymTab {
Note: See TracChangeset for help on using the changeset viewer.