Changes in / [33218c6:ea91c42]


Ignore:
Files:
23 edited

Legend:

Unmodified
Added
Removed

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

    r33218c6 rea91c42  
    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 : 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:
     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 : \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:
    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.
    248 
    249 Note 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:
     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:
    250248\begin{cfacode}
    251249//Incorrect
    252250//T is not a monitor
    253251forall(dtype T)
    254 void foo(T * mutex t);
     252void foo(T * mutex t); 
    255253
    256254//Correct
    257 //this function only works on monitors
     255//this function only works on monitors 
    258256//(any monitor)
    259257forall(dtype T | is_monitor(T))
    260 void bar(T * mutex t));
     258void bar(T * mutex t)); 
    261259\end{cfacode}
    262260
    … …  
    269267In 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.
    270268
    271 First, here is a simple example of such a technique:
     269First, Here is a simple example of such a technique:
    272270
    273271\begin{cfacode}
    … …  
    291289\end{cfacode}
    292290
    293 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.
     291There 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. 
    294292
    295293An 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.
    … …  
    319317\end{pseudo}
    320318\end{multicols}
    321 The 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.
     319
     320The 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.
    322321
    323322A direct extension of the previous example is the \gls{group-acquire} version:
    … …  
    338337\end{pseudo}
    339338\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 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:
     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 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:
    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 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.
     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 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.
    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 (at line 10). 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. 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.
    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.
     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. 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.
    465465\\
    466466
    467 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.
    468 
    469467In 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.
    470468
    471469\subsubsection{Dependency graphs}
    472 In 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:
     470In 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:
    473471
    474472\begin{multicols}{2}
    … …  
    498496
    499497\subsubsection{Partial signalling}
    500 Finally, the solution that is chosen for \CFA is to use partial signalling. Consider the following case:
     498Finally, the solution that was chosen for \CFA is to use partial signalling. Consider the following case:
    501499
    502500\begin{multicols}{2}
    … …  
    520518\end{pseudo}
    521519\end{multicols}
    522 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 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.
     520
     521The 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.
    523522
    524523% ======================================================================
    … …  
    527526% ======================================================================
    528527% ======================================================================
    529 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, which is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
     528An 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}.
    530529
    531530For example here is an example highlighting the difference in behaviour:
    … …  
    626625        bool inUse;
    627626public:
    628         void P() {
    629                 if(inUse) wait(c);
     627        void P() { 
     628                if(inUse) wait(c); 
    630629                inUse = true;
    631630        }
    632         void V() {
    633                 inUse = false;
    634                 signal(c);
     631        void V() { 
     632                inUse = false;         
     633                signal(c); 
    635634        }
    636635}
    … …  
    640639        bool inUse;
    641640public:
    642         void P() {
    643                 if(inUse) _Accept(V);
     641        void P() { 
     642                if(inUse) _Accept(V); 
    644643                inUse = true;
    645644        }
    646         void g() {
     645        void g() { 
    647646                inUse = false;
    648647

  • doc/proposals/concurrency/version

    r33218c6 rea91c42  
    1 0.9.122
     10.9.119

  • src/CodeGen/CodeGenerator.cc

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

  • src/CodeGen/GenType.cc

    r33218c6 rea91c42  
    1313// Update Count     : 22
    1414//
    15 #include "GenType.h"
    1615
    1716#include <cassert>                // for assert, assertf
    … …  
    2019
    2120#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

    r33218c6 rea91c42  
    1313// Update Count     : 6
    1414//
    15 #include "Generate.h"
    1615
    1716#include <iostream>                  // for ostream, endl, operator<<
    … …  
    2120#include "CodeGenerator.h"           // for CodeGenerator, doSemicolon, oper...
    2221#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

    r33218c6 rea91c42  
    1616#include "TrackLoc.h"
    1717
    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
     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
    2324
    24 #include "Common/PassVisitor.h"      // for PassVisitor
    25 #include "Common/utility.h"          // for CodeLocation
    26 #include "SynTree/BaseSyntaxNode.h"  // for BaseSyntaxNode
     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
    2732
    2833class Declaration;
    … …  
    4146                std::stack< CodeLocation * > parents;
    4247        public:
    43                 LocationPrinter(size_t printLevel) :
     48                LocationPrinter(size_t printLevel) : 
    4449                        printLevel(printLevel), lastNode(nullptr)
    4550                {}
    … …  
    6065                                if ( !parents.empty() ) {
    6166                                        node->location = *parents.top();
    62                                 }
     67                                } 
    6368                                else if (nullptr != lastNode) {
    6469                                        node->location = *lastNode;
    65                                 }
     70                                } 
    6671                                else {
    6772                                        std::cerr << "Top level node has no CodeLocation " << name << std::endl;

  • src/Common/PassVisitor.impl.h

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

  • src/Common/PassVisitor.proto.h

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

  • src/SymTab/AddVisit.h

    r33218c6 rea91c42  
    1414//
    1515
    16 #include "SynTree/Statement.h"
    17 
    1816namespace SymTab {
    1917        void addDecls( std::list< Declaration* > &declsToAdd, std::list< Statement* > &statements, std::list< Statement* >::iterator i );
    … …  
    3028
    3129                        if ( stmt == stmts.end() ) break;
    32 
     30                       
    3331                        // run mutator on statement
    3432                        maybeAccept( *stmt, visitor );
    … …  
    6159
    6260                        if ( decl == translationUnit.end() ) break;
    63 
     61                       
    6462                        // run mutator on declaration
    6563                        maybeAccept( *decl, visitor );

  • src/SymTab/Autogen.cc

    r33218c6 rea91c42  
    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"
    1525#include "Autogen.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 
    35 class Attribute;
     26#include "GenPoly/ScopedSet.h"
     27#include "Common/ScopedMap.h"
     28#include "SymTab/Mangler.h"
     29#include "GenPoly/DeclMutator.h"
    3630
    3731namespace SymTab {
    … …  
    518512                // Make function polymorphic in same parameters as generic union, if applicable
    519513                const std::list< TypeDecl* > & typeParams = aggregateDecl->get_parameters(); // List of type variables to be placed on the generated functions
    520 
     514               
    521515                // default ctor/dtor need only first parameter
    522516                // void ?{}(T *); void ^?{}(T *);

  • src/SymTab/Autogen.h

    r33218c6 rea91c42  
    1616#pragma once
    1717
    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
     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"
    3324
    3425namespace SymTab {
    … …  
    163154                if ( isUnnamedBitfield( obj ) ) return;
    164155
    165                 bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && ! obj->get_bitfieldWidth() ) );
     156                bool addCast = (fname == "?{}" || fname == "^?{}") && ( !obj || ( obj && obj->get_bitfieldWidth() == NULL ) );
    166157                std::list< Statement * > stmts;
    167158                genCall( srcParam, dstParam, fname, back_inserter( stmts ), obj->get_type(), addCast, forward );

  • src/SymTab/FixFunction.cc

    r33218c6 rea91c42  
    1515
    1616#include "FixFunction.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...
     17#include "SynTree/Declaration.h"
     18#include "SynTree/Type.h"
     19#include "SynTree/Expression.h"
     20#include "Common/utility.h"
    2321
    2422namespace SymTab {

  • src/SymTab/FixFunction.h

    r33218c6 rea91c42  
    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"  // for Mutator
    19 #include "SynTree/SynTree.h"  // for Types
     18#include "SynTree/Mutator.h"
    2019
    2120namespace SymTab {
    … …  
    4443                virtual Type* mutate(ZeroType *zeroType);
    4544                virtual Type* mutate(OneType *oneType);
    46 
     45 
    4746                bool isVoid;
    4847        };

  • src/SymTab/ImplementationType.cc

    r33218c6 rea91c42  
    1515
    1616#include "ImplementationType.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
     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"
    2422
    2523

  • src/SymTab/ImplementationType.h

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

  • src/SymTab/Indexer.cc

    r33218c6 rea91c42  
    1616#include "Indexer.h"
    1717
    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
     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"
    3738
    3839#define debugPrint(x) if ( doDebug ) { std::cout << x; }

  • src/SymTab/Indexer.h

    r33218c6 rea91c42  
    1616#pragma once
    1717
    18 #include <iosfwd>             // for ostream
    19 #include <list>               // for list
    20 #include <string>             // for string
     18#include <list>
     19#include <string>
    2120
    22 #include "SynTree/Visitor.h"  // for Visitor
    23 #include "SynTree/SynTree.h"  // for AST nodes
     21#include "SynTree/Visitor.h"
    2422
    2523namespace SymTab {
    … …  
    127125
    128126                struct Impl;
    129 
    130127                Impl *tables;         ///< Copy-on-write instance of table data structure
    131128                unsigned long scope;  ///< Scope index of this pointer

  • src/SymTab/Mangler.cc

    r33218c6 rea91c42  
    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"
    1528#include "Mangler.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...
     29#include "CodeGen/OperatorTable.h"
    3030
    3131namespace SymTab {

  • src/SymTab/Mangler.h

    r33218c6 rea91c42  
    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 <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
     18#include <sstream>
     19#include "SynTree/SynTree.h"
     20#include "SynTree/Visitor.h"
    2521
    2622namespace SymTab {
    … …  
    5147                virtual void visit( ZeroType *zeroType );
    5248                virtual void visit( OneType *oneType );
    53 
     49 
    5450                std::string get_mangleName() { return mangleName.str(); }
    5551          private:
    … …  
    6157                bool mangleOverridable;         ///< Specially mangle overridable built-in methods
    6258                bool typeMode;                  ///< Produce a unique mangled name for a type
    63 
     59 
    6460                Mangler( bool mangleOverridable, bool typeMode );
    6561                Mangler( const Mangler & );
    66 
     62 
    6763                void mangleDecl( DeclarationWithType *declaration );
    6864                void mangleRef( ReferenceToType *refType, std::string prefix );
    6965                void mangleGenericRef( ReferenceToType *refType, std::string prefix );
    70 
     66 
    7167                void printQualifiers( Type *type );
    7268        }; // Mangler

  • src/SymTab/TypeEquality.cc

    r33218c6 rea91c42  
    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"
    1524#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
    2625
    2726namespace SymTab {
    2827        class TypeEquality : public Visitor {
    2928  public:
    30                 TypeEquality( Type * other, bool vlaErr ) : result( true ), other( other ),
     29                TypeEquality( Type * other, bool vlaErr ) : result( true ), other( other ), 
    3130                        vlaErr( vlaErr ) {}
    3231                bool result;
    … …  
    7271                handleQualifiers( basicType );
    7372                if ( BasicType * bt = dynamic_cast< BasicType * >( other ) ) {
    74                         result = result && basicType->get_kind() == bt->get_kind();
     73                        result = result && basicType->get_kind() == bt->get_kind(); 
    7574                } else {
    7675                        result = false;
    … …  
    9998
    10099                        if ( vlaErr ) {
    101                                 // useful for comparing typedef types - in this case, we
     100                                // useful for comparing typedef types - in this case, we 
    102101                                // want types to appear distinct if either is a VLA type
    103102                                if ( arrayType->get_isVarLen() || at->get_isVarLen() ) {
    … …  
    147146
    148147                        // parameter types must be equivalent
    149                         it1 = funcType->get_parameters().begin();
     148                        it1 = funcType->get_parameters().begin(); 
    150149                        it2 = ft->get_parameters().begin();
    151150                        for ( ; it1 != funcType->get_parameters().end(); ++it1, ++it2 ) {

  • src/SymTab/TypeEquality.h

    r33218c6 rea91c42  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // TypeEquality.h --
     7// TypeEquality.h -- 
    88//
    99// Author           : Rob Schluntz
    … …  
    1414//
    1515
    16 class Type;
    17 
    1816namespace SymTab {
    1917  // compare types t1 and t2 for equality
    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
     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 
    2220  bool typeEquals( Type * t1, Type * t2, bool vlaErr = false );
    2321} // namespace SymTab

  • src/SymTab/Validate.cc

    r33218c6 rea91c42  
    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"
    4064#include "Validate.h"
    4165
    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
     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"
    7775
    7876#define debugPrint( x ) if ( doDebug ) { std::cout << x; }
    … …  
    607605                // a return statement in a void-returning function in C. The expression is treated as if it
    608606                // were cast to void.
    609                 if ( ! returnStmt->get_expr() && returnVals.size() != 0 ) {
     607                if ( returnStmt->get_expr() == NULL && returnVals.size() != 0 ) {
    610608                        throw SemanticError( "Non-void function returns no values: " , returnStmt );
    611609                }
    … …  
    838836        void validateGeneric( Aggr * inst ) {
    839837                std::list< TypeDecl * > * params = inst->get_baseParameters();
    840                 if ( params ) {
     838                if ( params != NULL ) {
    841839                        std::list< Expression * > & args = inst->get_parameters();
    842840
    … …  
    939937        void ArrayLength::previsit( ObjectDecl * objDecl ) {
    940938                if ( ArrayType * at = dynamic_cast< ArrayType * >( objDecl->get_type() ) ) {
    941                         if ( at->get_dimension() ) return;
     939                        if ( at->get_dimension() != nullptr ) return;
    942940                        if ( ListInit * init = dynamic_cast< ListInit * >( objDecl->get_init() ) ) {
    943941                                at->set_dimension( new ConstantExpr( Constant::from_ulong( init->get_initializers().size() ) ) );

  • src/SymTab/Validate.h

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