Changeset 3e2f5e3


Ignore:
Timestamp:
Jun 24, 2019, 4:11:41 PM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
2856438, 6c55a3d
Parents:
3623f9d (diff), 1335e6f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

Files:
9 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r3623f9d r3e2f5e3  
    280280The runtime also ensures multiple monitors can be safely acquired \emph{simultaneously} (deadlock free), and this feature is fully integrated with all monitor synchronization mechanisms.
    281281All control-flow features integrate with the \CFA polymorphic type-system and exception handling, while respecting the expectations and style of C programmers.
    282 Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages.
     282Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming languages.
    283283}%
    284284
     
    301301In many ways, \CFA is to C as Scala~\cite{Scala} is to Java, providing a \emph{research vehicle} for new typing and control-flow capabilities on top of a highly popular programming language allowing immediate dissemination.
    302302Within the \CFA framework, new control-flow features are created from scratch because ISO \Celeven defines only a subset of the \CFA extensions, where the overlapping features are concurrency~\cite[\S~7.26]{C11}.
    303 However, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}, and \Celeven and pthreads concurrency is simple, based on thread fork/join in a function and a few locks, which is low-level and error prone;
     303However, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}, and \Celeven and pthreads concurrency is simple, based on thread fork/join in a function and a few locks, which is low-level and error-prone;
    304304no high-level language concurrency features are defined.
    305305Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-9 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C11 concurrency approach.
     
    312312As a result, languages like Java, Scala, Objective-C~\cite{obj-c-book}, \CCeleven~\cite{C11}, and C\#~\cite{Csharp} adopt the 1:1 kernel-threading model, with a variety of presentation mechanisms.
    313313From 2000 onwards, languages like Go~\cite{Go}, Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, D~\cite{D}, and \uC~\cite{uC++,uC++book} have championed the M:N user-threading model, and many user-threading libraries have appeared~\cite{Qthreads,MPC,Marcel}, including putting green threads back into Java~\cite{Quasar}.
    314 The main argument for user-level threading is that they are lighter weight than kernel threads (locking and context switching do not cross the kernel boundary), so there is less restriction on programming styles that encourage large numbers of threads performing medium work-units to facilitate load balancing by the runtime~\cite{Verch12}.
     314The main argument for user-level threading is that they are lighter weight than kernel threads (locking and context switching do not cross the kernel boundary), so there is less restriction on programming styles that encourage large numbers of threads performing medium work units to facilitate load balancing by the runtime~\cite{Verch12}.
    315315As well, user-threading facilitates a simpler concurrency approach using thread objects that leverage sequential patterns versus events with call-backs~\cite{Adya02,vonBehren03}.
    316316Finally, performant user-threading implementations (both time and space) meet or exceed direct kernel-threading implementations, while achieving the programming advantages of high concurrency levels and safety.
    317317
    318 A further effort over the past two decades is the development of language memory-models to deal with the conflict between language features and compiler/hardware optimizations, i.e., some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}.
     318A further effort over the past two decades is the development of language memory models to deal with the conflict between language features and compiler/hardware optimizations, \ie, some language features are unsafe in the presence of aggressive sequential optimizations~\cite{Buhr95a,Boehm05}.
    319319The consequence is that a language must provide sufficient tools to program around safety issues, as inline and library code is all sequential to the compiler.
    320 One solution is low-level qualifiers and functions (e.g., @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs.
     320One solution is low-level qualifiers and functions (\eg, @volatile@ and atomics) allowing \emph{programmers} to explicitly write safe (race-free~\cite{Boehm12}) programs.
    321321A safer solution is high-level language constructs so the \emph{compiler} knows the optimization boundaries, and hence, provides implicit safety.
    322 This problem is best know with respect to concurrency, but applies to other complex control-flow, like exceptions\footnote{
     322This problem is best known with respect to concurrency, but applies to other complex control-flow, like exceptions\footnote{
    323323\CFA exception handling will be presented in a separate paper.
    324 The key feature that dovetails with this paper is non-local exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++}
     324The key feature that dovetails with this paper is nonlocal exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++}
    325325} and coroutines.
    326 Finally, language solutions allow matching constructs with language paradigm, i.e., imperative and functional languages often have different presentations of the same concept to fit their programming model.
     326Finally, language solutions allow matching constructs with language paradigm, \ie, imperative and functional languages often have different presentations of the same concept to fit their programming model.
    327327
    328328Finally, it is important for a language to provide safety over performance \emph{as the default}, allowing careful reduction of safety for performance when necessary.
    329 Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, i.e., once there is spurious wakeup, signals-as-hints follows.
     329Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, \ie, once there is spurious wakeup, signals-as-hints follow.
    330330However, spurious wakeup is \emph{not} a foundational concurrency property~\cite[\S~8]{Buhr05a}, it is a performance design choice.
    331 Similarly, signals-as-hints is often a performance decision.
    332 We argue removing spurious wakeup and signals-as-hints makes concurrent programming significantly safer because it removes local non-determinism and matches with programmer expectation.
     331Similarly, signals-as-hints are often a performance decision.
     332We argue removing spurious wakeup and signals-as-hints make concurrent programming significantly safer because it removes local non-determinism and matches with programmer expectation.
    333333(Author experience teaching concurrency is that students are highly confused by these semantics.)
    334334Clawing back performance, when local non-determinism is unimportant, should be an option not the default.
     
    337337Most augmented traditional (Fortran 18~\cite{Fortran18}, Cobol 14~\cite{Cobol14}, Ada 12~\cite{Ada12}, Java 11~\cite{Java11}) and new languages (Go~\cite{Go}, Rust~\cite{Rust}, and D~\cite{D}), except \CC, diverge from C with different syntax and semantics, only interoperate indirectly with C, and are not systems languages, for those with managed memory.
    338338As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten.
    339 While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (e.g., objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
     339While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (\eg, objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
    340340Hence, rewriting and retraining costs for these languages, even \CC, are prohibitive for companies with a large C software-base.
    341341\CFA with its orthogonal feature-set, its high-performance runtime, and direct access to all existing C libraries circumvents these problems.
     
    343343
    344344\CFA embraces user-level threading, language extensions for advanced control-flow, and safety as the default.
    345 We present comparative examples so the reader can judge if the \CFA control-flow extensions are better and safer than those in other concurrent, imperative programming-languages, and perform experiments to show the \CFA runtime is competitive with other similar mechanisms.
     345We present comparative examples so the reader can judge if the \CFA control-flow extensions are better and safer than those in other concurrent, imperative programming languages, and perform experiments to show the \CFA runtime is competitive with other similar mechanisms.
    346346The main contributions of this work are:
    347347\begin{itemize}
     
    349349language-level generators, coroutines and user-level threading, which respect the expectations of C programmers.
    350350\item
    351 monitor synchronization without barging, and the ability to safely acquiring multiple monitors \emph{simultaneously} (deadlock free), while seamlessly integrating these capability with all monitor synchronization mechanisms.
     351monitor synchronization without barging, and the ability to safely acquiring multiple monitors \emph{simultaneously} (deadlock free), while seamlessly integrating these capabilities with all monitor synchronization mechanisms.
    352352\item
    353353providing statically type-safe interfaces that integrate with the \CFA polymorphic type-system and other language features.
     
    367367\section{Stateful Function}
    368368
    369 The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, e.g., plugin, device driver, finite-state machine.
     369The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, \eg, plugin, device driver, finite-state machine.
    370370Hence, a stateful function may not end when it returns to its caller, allowing it to be restarted with the data and execution location present at the point of suspension.
    371371This capability is accomplished by retaining a data/execution \emph{closure} between invocations.
    372 If the closure is fixed size, we call it a \emph{generator} (or \emph{stackless}), and its control flow is restricted, e.g., suspending outside the generator is prohibited.
    373 If the closure is variable sized, we call it a \emph{coroutine} (or \emph{stackful}), and as the names implies, often implemented with a separate stack with no programming restrictions.
     372If the closure is fixed size, we call it a \emph{generator} (or \emph{stackless}), and its control flow is restricted, \eg, suspending outside the generator is prohibited.
     373If the closure is variably sized, we call it a \emph{coroutine} (or \emph{stackful}), and as the names implies, often implemented with a separate stack with no programming restrictions.
    374374Hence, refactoring a stackless coroutine may require changing it to stackful.
    375 A foundational property of all \emph{stateful functions} is that resume/suspend \emph{do not} cause incremental stack growth, i.e., resume/suspend operations are remembered through the closure not the stack.
     375A foundational property of all \emph{stateful functions} is that resume/suspend \emph{do not} cause incremental stack growth, \ie, resume/suspend operations are remembered through the closure not the stack.
    376376As well, activating a stateful function is \emph{asymmetric} or \emph{symmetric}, identified by resume/suspend (no cycles) and resume/resume (cycles).
    377377A fixed closure activated by modified call/return is faster than a variable closure activated by context switching.
    378 Additionally, any storage management for the closure (especially in unmanaged languages, i.e., no garbage collection) must also be factored into design and performance.
     378Additionally, any storage management for the closure (especially in unmanaged languages, \ie, no garbage collection) must also be factored into design and performance.
    379379Therefore, selecting between stackless and stackful semantics is a tradeoff between programming requirements and performance, where stackless is faster and stackful is more general.
    380380Note, creation cost is amortized across usage, so activation cost is usually the dominant factor.
     
    603603the top initialization state appears at the start and the middle execution state is denoted by statement @suspend@.
    604604Any local variables in @main@ \emph{are not retained} between calls;
    605 hence local variable are only for temporary computations \emph{between} suspends.
     605hence local variables are only for temporary computations \emph{between} suspends.
    606606All retained state \emph{must} appear in the generator's type.
    607607As well, generator code containing a @suspend@ cannot be refactored into a helper function called by the generator, because @suspend@ is implemented via @return@, so a return from the helper function goes back to the current generator not the resumer.
     
    618618sout | (int)f1() | (double)f1() | f2( 2 ); // alternative interface, cast selects call based on return type, step 2 values
    619619\end{cfa}
    620 Now, the generator can be a separately-compiled opaque-type only accessed through its interface functions.
     620Now, the generator can be a separately compiled opaque-type only accessed through its interface functions.
    621621For contrast, Figure~\ref{f:PythonFibonacci} shows the equivalent Python Fibonacci generator, which does not use a generator type, and hence only has a single interface, but an implicit closure.
    622622
     
    624624(This restriction is removed by the coroutine in Section~\ref{s:Coroutine}.)
    625625This requirement follows from the generality of variable-size local-state, \eg local state with a variable-length array requires dynamic allocation because the array size is unknown at compile time.
    626 However, dynamic allocation significantly increases the cost of generator creation/destruction and is a show-stopper for embedded real-time programming.
     626However, dynamic allocation significantly increases the cost of generator creation/destruction and is a showstopper for embedded real-time programming.
    627627But more importantly, the size of the generator type is tied to the local state in the generator main, which precludes separate compilation of the generator main, \ie a generator must be inlined or local state must be dynamically allocated.
    628628With respect to safety, we believe static analysis can discriminate local state from temporary variables in a generator, \ie variable usage spanning @suspend@, and generate a compile-time error.
     
    648648\end{center}
    649649The example takes advantage of resuming a generator in the constructor to prime the loops so the first character sent for formatting appears inside the nested loops.
    650 The destructor provides a newline, if formatted text ends with a full line.
     650The destructor provides a newline if formatted text ends with a full line.
    651651Figure~\ref{f:CFormatSim} shows the C implementation of the \CFA input generator with one additional field and the computed @goto@.
    652652For contrast, Figure~\ref{f:PythonFormatter} shows the equivalent Python format generator with the same properties as the Fibonacci generator.
     
    669669In contrast, the execution state is large, with one @resume@ and seven @suspend@s.
    670670Hence, the key benefits of the generator are correctness, safety, and maintenance because the execution states are transcribed directly into the programming language rather than using a table-driven approach.
    671 Because FSMs can be complex and occur frequently in important domains, direct support of the generator is crucial in a systems programming-language.
     671Because FSMs can be complex and frequently occur in important domains, direct support of the generator is crucial in a system programming language.
    672672
    673673\begin{figure}
     
    782782The steps for symmetric control-flow are creating, executing, and terminating the cycle.
    783783Constructing the cycle must deal with definition-before-use to close the cycle, \ie, the first generator must know about the last generator, which is not within scope.
    784 (This issues occurs for any cyclic data-structure.)
     784(This issue occurs for any cyclic data structure.)
    785785% The example creates all the generators and then assigns the partners that form the cycle.
    786786% Alternatively, the constructor can assign the partners as they are declared, except the first, and the first-generator partner is set after the last generator declaration to close the cycle.
     
    792792
    793793Figure~\ref{f:CPingPongSim} shows the implementation of the symmetric generator, where the complexity is the @resume@, which needs an extension to the calling convention to perform a forward rather than backward jump.
    794 This jump starts at the top of the next generator main to re-execute the normal calling convention to make space on the stack for its local variables.
     794This jump-starts at the top of the next generator main to re-execute the normal calling convention to make space on the stack for its local variables.
    795795However, before the jump, the caller must reset its stack (and any registers) equivalent to a @return@, but subsequently jump forward.
    796796This semantics is basically a tail-call optimization, which compilers already perform.
     
    862862
    863863Finally, part of this generator work was inspired by the recent \CCtwenty generator proposal~\cite{C++20Coroutine19} (which they call coroutines).
    864 Our work provides the same high-performance asymmetric-generators as \CCtwenty, and extends their work with symmetric generators.
    865 An additional \CCtwenty generator feature allows @suspend@ and @resume@ to be followed by a restricted compound-statement that is executed after the current generator has reset its stack but before calling the next generator, specified with \CFA syntax:
     864Our work provides the same high-performance asymmetric generators as \CCtwenty, and extends their work with symmetric generators.
     865An additional \CCtwenty generator feature allows @suspend@ and @resume@ to be followed by a restricted compound statement that is executed after the current generator has reset its stack but before calling the next generator, specified with \CFA syntax:
    866866\begin{cfa}
    867867... suspend`{ ... }`;
     
    879879A coroutine is specified by replacing @generator@ with @coroutine@ for the type.
    880880Coroutine generality results in higher cost for creation, due to dynamic stack allocation, execution, due to context switching among stacks, and terminating, due to possible stack unwinding and dynamic stack deallocation.
    881 A series of different kinds of coroutines and their implementation demonstrate how coroutines extend generators.
     881A series of different kinds of coroutines and their implementations demonstrate how coroutines extend generators.
    882882
    883883First, the previous generator examples are converted to their coroutine counterparts, allowing local-state variables to be moved from the generator type into the coroutine main.
     
    11641164\end{cfa}
    11651165\end{tabular}
    1166 \caption{Producer / consumer: resume-resume cycle, bi-directional communication}
     1166\caption{Producer / consumer: resume-resume cycle, bidirectional communication}
    11671167\label{f:ProdCons}
    11681168\end{figure}
     
    12081208Furthermore, each deallocated coroutine must guarantee all destructors are run for object allocated in the coroutine type \emph{and} allocated on the coroutine's stack at the point of suspension, which can be arbitrarily deep.
    12091209When a coroutine's main ends, its stack is already unwound so any stack allocated objects with destructors have been finalized.
    1210 The na\"{i}ve semantics for coroutine-cycle termination is context switch to the last resumer, like executing a @suspend@/@return@ in a generator.
     1210The na\"{i}ve semantics for coroutine-cycle termination is to context switch to the last resumer, like executing a @suspend@/@return@ in a generator.
    12111211However, for coroutines, the last resumer is \emph{not} implicitly below the current stack frame, as for generators, because each coroutine's stack is independent.
    12121212Unfortunately, it is impossible to determine statically if a coroutine is in a cycle and unrealistic to check dynamically (graph-cycle problem).
     
    12141214
    12151215Our solution is to context switch back to the first resumer (starter) once the coroutine ends.
    1216 This semantics works well for the most common asymmetric and symmetric coroutine usage-patterns.
     1216This semantics works well for the most common asymmetric and symmetric coroutine usage patterns.
    12171217For asymmetric coroutines, it is common for the first resumer (starter) coroutine to be the only resumer.
    12181218All previous generators converted to coroutines have this property.
    1219 For symmetric coroutines, it is common for the cycle creator to persist for the life-time of the cycle.
     1219For symmetric coroutines, it is common for the cycle creator to persist for the lifetime of the cycle.
    12201220Hence, the starter coroutine is remembered on the first resume and ending the coroutine resumes the starter.
    12211221Figure~\ref{f:ProdConsRuntimeStacks} shows this semantic by the dashed lines from the end of the coroutine mains: @prod@ starts @cons@ so @cons@ resumes @prod@ at the end, and the program main starts @prod@ so @prod@ resumes the program main at the end.
     
    12851285\end{cfa}
    12861286Note, copying generators/coroutines/threads is not meaningful.
    1287 For example, both the resumer and suspender descriptors can have bi-directional pointers;
     1287For example, both the resumer and suspender descriptors can have bidirectional pointers;
    12881288copying these coroutines does not update the internal pointers so behaviour of both copies would be difficult to understand.
    12891289Furthermore, two coroutines cannot logically execute on the same stack.
    12901290A deep coroutine copy, which copies the stack, is also meaningless in an unmanaged language (no garbage collection), like C, because the stack may contain pointers to object within it that require updating for the copy.
    12911291The \CFA @dtype@ property provides no \emph{implicit} copying operations and the @is_coroutine@ trait provides no \emph{explicit} copying operations, so all coroutines must be passed by reference (pointer).
    1292 The function definitions ensures there is a statically-typed @main@ function that is the starting point (first stack frame) of a coroutine, and a mechanism to get (read) the coroutine descriptor from its handle.
     1292The function definitions ensure there is a statically typed @main@ function that is the starting point (first stack frame) of a coroutine, and a mechanism to get (read) the coroutine descriptor from its handle.
    12931293The @main@ function has no return value or additional parameters because the coroutine type allows an arbitrary number of interface functions with corresponding arbitrary typed input/output values versus fixed ones.
    12941294The advantage of this approach is that users can easily create different types of coroutines, \eg changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ function, and possibly redefining \textsf{suspend} and @resume@.
     
    13421342For a VLS stack allocation/deallocation is an inexpensive adjustment of the stack pointer, modulo any stack constructor costs (\eg initial frame setup).
    13431343For heap stack allocation, allocation/deallocation is an expensive heap allocation (where the heap can be a shared resource), modulo any stack constructor costs.
    1344 With heap stack allocation, it is also possible to use a split (segmented) stack calling-convention, available with gcc and clang, so the stack is variable sized.
     1344With heap stack allocation, it is also possible to use a split (segmented) stack calling convention, available with gcc and clang, so the stack is variable sized.
    13451345Currently, \CFA supports stack/heap allocated descriptors but only fixed-sized heap allocated stacks.
    13461346In \CFA debug-mode, the fixed-sized stack is terminated with a write-only page, which catches most stack overflows.
     
    13591359\label{s:Concurrency}
    13601360
    1361 Concurrency is nondeterministic scheduling of independent sequential execution-paths (threads), where each thread has its own stack.
     1361Concurrency is nondeterministic scheduling of independent sequential execution paths (threads), where each thread has its own stack.
    13621362A single thread with multiple call stacks, \newterm{coroutining}~\cite{Conway63,Marlin80}, does \emph{not} imply concurrency~\cite[\S~2]{Buhr05a}.
    13631363In coroutining, coroutines self-schedule the thread across stacks so execution is deterministic.
     
    13671367The transition to concurrency, even for a single thread with multiple stacks, occurs when coroutines context switch to a \newterm{scheduling coroutine}, introducing non-determinism from the coroutine perspective~\cite[\S~3,]{Buhr05a}.
    13681368Therefore, a minimal concurrency system requires coroutines \emph{in conjunction with a nondeterministic scheduler}.
    1369 The resulting execution system now follows a cooperative threading-model~\cite{Adya02,libdill}, called \newterm{non-preemptive scheduling}.
     1369The resulting execution system now follows a cooperative threading model~\cite{Adya02,libdill}, called \newterm{non-preemptive scheduling}.
    13701370Adding \newterm{preemption} introduces non-cooperative scheduling, where context switching occurs randomly between any two instructions often based on a timer interrupt, called \newterm{preemptive scheduling}.
    13711371While a scheduler introduces uncertain execution among explicit context switches, preemption introduces uncertainty by introducing implicit context switches.
     
    14971497\end{cquote}
    14981498Like coroutines, the @dtype@ property prevents \emph{implicit} copy operations and the @is_thread@ trait provides no \emph{explicit} copy operations, so threads must be passed by reference (pointer).
    1499 Similarly, the function definitions ensures there is a statically-typed @main@ function that is the thread starting point (first stack frame), a mechanism to get (read) the thread descriptor from its handle, and a special destructor to prevent deallocation while the thread is executing.
     1499Similarly, the function definitions ensure there is a statically typed @main@ function that is the thread starting point (first stack frame), a mechanism to get (read) the thread descriptor from its handle, and a special destructor to prevent deallocation while the thread is executing.
    15001500(The qualifier @mutex@ for the destructor parameter is discussed in Section~\ref{s:Monitor}.)
    15011501The difference between the coroutine and thread is that a coroutine borrows a thread from its caller, so the first thread resuming a coroutine creates the coroutine's stack and starts running the coroutine main on the stack;
     
    15121512Hence, a programmer must learn and manipulate two sets of design/programming patterns.
    15131513While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account.
    1514 In contrast, approaches based on stateful models more closely resemble the standard call/return programming-model, resulting in a single programming paradigm.
     1514In contrast, approaches based on stateful models more closely resemble the standard call/return programming model, resulting in a single programming paradigm.
    15151515
    15161516At the lowest level, concurrent control is implemented by atomic operations, upon which different kinds of locking mechanisms are constructed, \eg semaphores~\cite{Dijkstra68b}, barriers, and path expressions~\cite{Campbell74}.
     
    15201520
    15211521One of the most natural, elegant, and efficient mechanisms for mutual exclusion and synchronization for shared-memory systems is the \emph{monitor}.
    1522 First proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}, many concurrent programming-languages provide monitors as an explicit language construct: \eg 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}.
     1522First proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}, many concurrent programming languages provide monitors as an explicit language construct: \eg 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}.
    15231523In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as mutex locks or semaphores to simulate monitors.
    1524 For these reasons, \CFA selected monitors as the core high-level concurrency-construct, upon which higher-level approaches can be easily constructed.
     1524For these reasons, \CFA selected monitors as the core high-level concurrency construct, upon which higher-level approaches can be easily constructed.
    15251525
    15261526
     
    15711571% (While a constructor may publish its address into a global variable, doing so generates a race-condition.)
    15721572The prefix increment operation, @++?@, is normally @mutex@, indicating mutual exclusion is necessary during function execution, to protect the incrementing from race conditions, unless there is an atomic increment instruction for the implementation type.
    1573 The assignment operators provide bi-directional conversion between an atomic and normal integer without accessing field @cnt@;
     1573The assignment operators provide bidirectional conversion between an atomic and normal integer without accessing field @cnt@;
    15741574these operations only need @mutex@, if reading/writing the implementation type is not atomic.
    15751575The atomic counter is used without any explicit mutual-exclusion and provides thread-safe semantics, which is similar to the \CC template @std::atomic@.
     
    15931593Similar safety is offered by \emph{explicit} mechanisms like \CC RAII;
    15941594monitor \emph{implicit} safety ensures no programmer usage errors.
    1595 Furthermore, RAII mechansims cannot handle complex synchronization within a monitor, where the monitor lock may not be released on function exit because it is passed to an unblocking thread;
     1595Furthermore, RAII mechanisms cannot handle complex synchronization within a monitor, where the monitor lock may not be released on function exit because it is passed to an unblocking thread;
    15961596RAII is purely a mutual-exclusion mechanism (see Section~\ref{s:Scheduling}).
    15971597
     
    16321632
    16331633The benefit of mandatory monitor qualifiers is self-documentation, but requiring both @mutex@ and \lstinline[morekeywords=nomutex]@nomutex@ for all monitor parameters is redundant.
    1634 Instead, the semantics have one qualifier as the default and the other required.
     1634Instead, the semantics has one qualifier as the default and the other required.
    16351635For example, make the safe @mutex@ qualifier the default because assuming \lstinline[morekeywords=nomutex]@nomutex@ may cause subtle errors.
    16361636Alternatively, make the unsafe \lstinline[morekeywords=nomutex]@nomutex@ qualifier the default because it is the \emph{normal} parameter semantics while @mutex@ parameters are rare.
     
    18091809Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion, so either the signaller or signallee can proceed.
    18101810For internal scheduling, threads are unblocked from condition queues using @signal@, where the signallee is moved to urgent and the signaller continues (solid line).
    1811 Multiple signals move multiple signallees to urgent, until the condition is empty.
     1811Multiple signals move multiple signallees to urgent until the condition is empty.
    18121812When the signaller exits or waits, a thread blocked on urgent is processed before calling threads to prevent barging.
    18131813(Java conceptually moves the signalled thread to the calling queue, and hence, allows barging.)
     
    18191819The @waitfor@ has the same semantics as @signal_block@, where the signalled thread executes before the signallee, which waits on urgent.
    18201820Executing multiple @waitfor@s from different signalled functions causes the calling threads to move to urgent.
    1821 External scheduling requires urgent to be a stack, because the signaller excepts to execute immediately after the specified monitor call has exited or waited.
     1821External scheduling requires urgent to be a stack, because the signaller expects to execute immediately after the specified monitor call has exited or waited.
    18221822Internal scheduling behaves the same for an urgent stack or queue, except for multiple signalling, where the threads unblock from urgent in reverse order from signalling.
    18231823If the restart order is important, multiple signalling by a signal thread can be transformed into daisy-chain signalling among threads, where each thread signals the next thread.
     
    21432143\end{figure}
    21442144
    2145 Note, a group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, e.g.:
     2145Note, a group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, \eg:
    21462146\begin{cfa}
    21472147if ( C1 ) waitfor( mem1 );                       when ( C1 ) waitfor( mem1 );
     
    22562256\label{s:LooseObjectDefinitions}
    22572257
    2258 In an object-oriented programming-language, a class includes an exhaustive list of operations.
     2258In an object-oriented programming language, a class includes an exhaustive list of operations.
    22592259A new class can add members via static inheritance but the subclass still has an exhaustive list of operations.
    22602260(Dynamic member adding, \eg JavaScript~\cite{JavaScript}, is not considered.)
     
    26712671\subsection{Preemption}
    26722672
    2673 Nondeterministic preemption provides fairness from long running threads, and forces concurrent programmers to write more robust programs, rather than relying on code between cooperative scheduling to be atomic.
     2673Nondeterministic preemption provides fairness from long-running threads, and forces concurrent programmers to write more robust programs, rather than relying on code between cooperative scheduling to be atomic.
    26742674This atomic reliance can fail on multi-core machines, because execution across cores is nondeterministic.
    26752675A different reason for not supporting preemption is that it significantly complicates the runtime system, \eg Microsoft runtime does not support interrupts and on Linux systems, interrupts are complex (see below).
    2676 Preemption is normally handled by setting a count-down timer on each virtual processor.
    2677 When the timer expires, an interrupt is delivered, and the interrupt handler resets the count-down timer, and if the virtual processor is executing in user code, the signal handler performs a user-level context-switch, or if executing in the language runtime-kernel, the preemption is ignored or rolled forward to the point where the runtime kernel context switches back to user code.
     2676Preemption is normally handled by setting a countdown timer on each virtual processor.
     2677When the timer expires, an interrupt is delivered, and the interrupt handler resets the countdown timer, and if the virtual processor is executing in user code, the signal handler performs a user-level context-switch, or if executing in the language runtime kernel, the preemption is ignored or rolled forward to the point where the runtime kernel context switches back to user code.
    26782678Multiple signal handlers may be pending.
    26792679When control eventually switches back to the signal handler, it returns normally, and execution continues in the interrupted user thread, even though the return from the signal handler may be on a different kernel thread than the one where the signal is delivered.
     
    26852685\begin{cquote}
    26862686A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked.
    2687 If more than one of the threads has the signal unblocked, then the kernel chooses an arbitrary thread to which to deliver the signal.
     2687If more than one of the threads has the signal unblocked, then the kernel chooses an arbitrary thread to which it will deliver the signal.
    26882688SIGNAL(7) - Linux Programmer's Manual
    26892689\end{cquote}
     
    26912691To ensure each virtual processor receives a preemption signal, a discrete-event simulation is run on a special virtual processor, and only it sets and receives timer events.
    26922692Virtual processors register an expiration time with the discrete-event simulator, which is inserted in sorted order.
    2693 The simulation sets the count-down timer to the value at the head of the event list, and when the timer expires, all events less than or equal to the current time are processed.
     2693The simulation sets the countdown timer to the value at the head of the event list, and when the timer expires, all events less than or equal to the current time are processed.
    26942694Processing a preemption event sends an \emph{internal} @SIGUSR1@ signal to the registered virtual processor, which is always delivered to that processor.
    26952695
     
    29132913\paragraph{Mutual-Exclusion}
    29142914
    2915 Uncontented mutual exclusion, which occurs frequently, is measured by entering/leaving a critical section.
     2915Uncontented mutual exclusion, which frequently occurs, is measured by entering/leaving a critical section.
    29162916For monitors, entering and leaving a monitor function is measured.
    29172917To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured.
  • src/AST/Type.hpp

    r3623f9d r3e2f5e3  
    164164        static const char *typeNames[];
    165165
    166         BasicType( Kind k, CV::Qualifiers q = {} ) : Type(q), kind(k) {}
     166        BasicType( Kind k, CV::Qualifiers q = {}, std::vector<ptr<Attribute>> && as = {} )
     167        : Type(q, std::move(as)), kind(k) {}
    167168
    168169        /// Check if this type represents an integer type
  • src/ResolvExpr/CastCost.cc

    r3623f9d r3e2f5e3  
    1616#include <cassert>                       // for assert
    1717
     18#include "AST/Print.hpp"
     19#include "AST/SymbolTable.hpp"
     20#include "AST/Type.hpp"
     21#include "AST/TypeEnvironment.hpp"
    1822#include "ConversionCost.h"              // for ConversionCost
    1923#include "Cost.h"                        // for Cost, Cost::infinity
     
    3135
    3236namespace ResolvExpr {
    33         struct CastCost : public ConversionCost {
     37        struct CastCost_old : public ConversionCost {
    3438          public:
    35                 CastCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc );
     39                CastCost_old( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc );
    3640
    3741                using ConversionCost::previsit;
     
    7882                        });
    7983                } else {
    80                         #warning cast on castCost artifact of having two functions, remove when port done
    81                         PassVisitor<CastCost> converter(
     84                        PassVisitor<CastCost_old> converter(
    8285                                dest, indexer, env,
    8386                                (Cost (*)( Type *, Type *, const SymTab::Indexer &, const TypeEnvironment & ))
     
    9396        }
    9497
    95         CastCost::CastCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc )
     98        CastCost_old::CastCost_old( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc )
    9699                : ConversionCost( dest, indexer, env, costFunc ) {
    97100        }
    98101
    99         void CastCost::postvisit( BasicType *basicType ) {
     102        void CastCost_old::postvisit( BasicType *basicType ) {
    100103                PointerType *destAsPointer = dynamic_cast< PointerType* >( dest );
    101104                if ( destAsPointer && basicType->isInteger() ) {
     
    107110        }
    108111
    109         void CastCost::postvisit( PointerType *pointerType ) {
     112        void CastCost_old::postvisit( PointerType *pointerType ) {
    110113                if ( PointerType *destAsPtr = dynamic_cast< PointerType* >( dest ) ) {
    111114                        if ( pointerType->get_qualifiers() <= destAsPtr->get_qualifiers() && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) {
     
    130133        }
    131134
    132         Cost castCost(
    133                 const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
    134                 const ast::TypeEnvironment & env
    135         ) {
    136                 #warning unimplmented
    137                 (void)src; (void)dst; (void)symtab; (void)env;
    138                 assert(false);
     135namespace {
     136        struct CastCost_new : public ConversionCost_new {
     137                using ConversionCost_new::previsit;
     138                using ConversionCost_new::postvisit;
     139
     140                CastCost_new(
     141                        const ast::Type * dst, const ast::SymbolTable & symtab,
     142                        const ast::TypeEnvironment & env, CostCalculation costFunc )
     143                : ConversionCost_new( dst, symtab, env, costFunc ) {}
     144
     145                void postvisit( const ast::BasicType * basicType ) {
     146                        auto ptr = dynamic_cast< const ast::PointerType * >( dst );
     147                        if ( ptr && basicType->isInteger() ) {
     148                                // needed for, e.g. unsigned long => void *
     149                                cost = Cost::unsafe;
     150                        } else {
     151                                cost = conversionCost( basicType, dst, symtab, env );
     152                        }
     153                }
     154
     155                void postvisit( const ast::PointerType * pointerType ) {
     156                        if ( auto ptr = dynamic_cast< const ast::PointerType * >( dst ) ) {
     157                                if (
     158                                        pointerType->qualifiers <= ptr->qualifiers
     159                                        && typesCompatibleIgnoreQualifiers( pointerType->base, ptr->base, symtab, env )
     160                                ) {
     161                                        cost = Cost::safe;
     162                                } else {
     163                                        ast::TypeEnvironment newEnv{ env };
     164                                        if ( auto wParams = pointerType->base.as< ast::ParameterizedType >() ) {
     165                                                newEnv.add( wParams->forall );
     166                                        }
     167                                        int castResult = ptrsCastable( pointerType->base, ptr->base, symtab, newEnv );
     168                                        if ( castResult > 0 ) {
     169                                                cost = Cost::safe;
     170                                        } else if ( castResult < 0 ) {
     171                                                cost = Cost::infinity;
     172                                        }
     173                                }
     174                        } else if ( auto basic = dynamic_cast< const ast::BasicType * >( dst ) ) {
     175                                if ( basic->isInteger() ) {
     176                                        // necessary for, e.g. void * => unsigned long
     177                                        cost = Cost::unsafe;
     178                                }
     179                        }
     180                }
     181        };
     182} // anonymous namespace
     183
     184Cost castCost(
     185        const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     186        const ast::TypeEnvironment & env
     187) {
     188        if ( auto typeInst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
     189                if ( const ast::EqvClass * eqvClass = env.lookup( typeInst->name ) ) {
     190                        // check cast cost against bound type, if present
     191                        if ( eqvClass->bound ) {
     192                                return castCost( src, eqvClass->bound, symtab, env );
     193                        } else {
     194                                return Cost::infinity;
     195                        }
     196                } else if ( const ast::NamedTypeDecl * named = symtab.lookupType( typeInst->name ) ) {
     197                        // all typedefs should be gone by now
     198                        auto type = strict_dynamic_cast< const ast::TypeDecl * >( named );
     199                        if ( type->base ) {
     200                                return castCost( src, type->base, symtab, env ) + Cost::safe;
     201                        }
     202                }
     203        }
     204
     205        PRINT(
     206                std::cerr << "castCost ::: src is ";
     207                ast::print( std::cerr, src );
     208                std::cerr << std::endl << "dest is ";
     209                ast::print( std::cerr, dst );
     210                std::cerr << std::endl << "env is" << std::endl;
     211                ast::print( std::cerr, env, 2 );
     212        )
     213
     214        if ( typesCompatibleIgnoreQualifiers( src, dst, symtab, env ) ) {
     215                PRINT( std::cerr << "compatible!" << std::endl; )
    139216                return Cost::zero;
    140         }
     217        } else if ( dynamic_cast< const ast::VoidType * >( dst ) ) {
     218                return Cost::safe;
     219        } else if ( auto refType = dynamic_cast< const ast::ReferenceType * >( dst ) ) {
     220                PRINT( std::cerr << "conversionCost: dest is reference" << std::endl; )
     221                #warning cast on ptrsCastable artifact of having two functions, remove when port done
     222                return convertToReferenceCost(
     223                        src, refType, symtab, env,
     224                        ( int (*)(
     225                                const ast::Type *, const ast::Type *, const ast::SymbolTable &,
     226                                const ast::TypeEnvironment & )
     227                        ) ptrsCastable );
     228        } else {
     229                #warning cast on castCost artifact of having two functions, remove when port done
     230                ast::Pass< CastCost_new > converter{
     231                        dst, symtab, env,
     232                        ( Cost (*)(
     233                                const ast::Type *, const ast::Type *, const ast::SymbolTable &,
     234                                const ast::TypeEnvironment & )
     235                        ) castCost };
     236                src->accept( converter );
     237                return converter.pass.cost;
     238        }
     239}
     240
    141241} // namespace ResolvExpr
    142242
  • src/ResolvExpr/ConversionCost.h

    r3623f9d r3e2f5e3  
    7474        const ast::SymbolTable &, const ast::TypeEnvironment &)>;
    7575
    76 // TODO: When the old ConversionCost is removed, get ride of the _new suffix.
     76#warning when the old ConversionCost is removed, get ride of the _new suffix.
    7777class ConversionCost_new : public ast::WithShortCircuiting {
     78protected:
    7879        const ast::Type * dst;
    7980        const ast::SymbolTable & symtab;
  • src/ResolvExpr/PtrsAssignable.cc

    r3623f9d r3e2f5e3  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 11:44:11 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Mar  2 17:36:05 2016
    13 // Update Count     : 8
    14 //
    15 
    16 #include "AST/Fwd.hpp"
     11// Last Modified By : Andrew
     12// Last Modified On : Mon Jun 24 15:29:00 2019
     13// Update Count     : 9
     14//
     15
     16#include "typeops.h"
     17
     18#include "AST/Pass.hpp"
     19#include "AST/Type.hpp"
     20#include "AST/TypeEnvironment.hpp"
    1721#include "Common/PassVisitor.h"
    1822#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     
    108112        void PtrsAssignable::postvisit(  __attribute__((unused)) OneType *oneType ) {}
    109113
     114// TODO: Get rid of the `_new` suffix when the old version is removed.
     115struct PtrsAssignable_new : public ast::WithShortCircuiting {
     116        const ast::Type * dst;
     117        const ast::TypeEnvironment & typeEnv;
     118        int result;
     119
     120        PtrsAssignable_new( const ast::Type * dst, const ast::TypeEnvironment & env ) :
     121                dst( dst ), typeEnv( env ), result( 0 ) {}
     122
     123        void previsit( Type * ) { visit_children = false; }
     124
     125        void postvisit( const ast::EnumInstType * ) {
     126                if ( dynamic_cast< const ast::BasicType * >( dst ) ) {
     127                        // int * = E *, etc. is safe. This isn't technically correct, as each
     128                        // enum has one basic type that it is compatible with, an that type can
     129                        // differ from enum to enum. Without replicating GCC's internal logic,
     130                        // there is no way to know which type this particular enum is compatible
     131                        // with, so punt on this for now.
     132                        result = 1;
     133                }
     134        }
     135        void postvisit( const ast::TypeInstType * inst ) {
     136                if ( const ast::EqvClass * eqv = typeEnv.lookup( inst->name ) ) {
     137                        if ( eqv->bound ) {
     138                                // T * = S * for any S depends on the type bound to T
     139                                result = ptrsAssignable( eqv->bound, dst, typeEnv );
     140                        }
     141                }
     142        }
     143};
     144
    110145int ptrsAssignable( const ast::Type * src, const ast::Type * dst,
    111146                const ast::TypeEnvironment & env ) {
    112         #warning unimplemented
    113         (void)src;
    114         (void)dst;
    115         (void)env;
    116         assert(0);
     147        if ( const ast::TypeInstType * dstAsInst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
     148                if ( const ast::EqvClass * eqv = env.lookup( dstAsInst->name ) ) {
     149                        return ptrsAssignable( src, eqv->bound, env );
     150                }
     151        }
     152        if ( dynamic_cast< const ast::VoidType * >( dst ) ) {
     153                return -1;
     154        } else {
     155                ast::Pass<PtrsAssignable_new> visitor( dst, env );
     156                src->accept( visitor );
     157                return visitor.pass.result;
     158        }
     159
     160// see ticket #136 (this should be able to replace the visitor).
     161#if 0
     162        if ( const ast::TypeInstType * dstAsTypeInst =
     163                        dynamic_cast< const ast::TypeInstType* >( dst ) ) {
     164                if ( const ast::EqvClass * eqv = env.lookup( dstAsTypeInst->get_name() ) ) {
     165                        return ptrsAssignable( src, eqv->type, env );
     166                } // if
     167        } // if
     168        if ( dynamic_cast< VoidType* >( dst ) ) {
     169                // void * = T * for any T is unsafe
     170                // xxx - this should be safe, but that currently breaks the build
     171                return -1;
     172        } else if ( dynamic_cast< EnumInstType * >( src ) ) {
     173                if ( dynamic_cast< BasicType * >( dst ) ) {
     174                        // int * = E *, etc. is safe. This isn't technically correct, as each
     175                        // enum has one basic type that it is compatible with, an that type can
     176                        // differ from enum to enum. Without replicating GCC's internal logic,
     177                        // there is no way to know which type this particular enum is compatible
     178                        // with, so punt on this for now.
     179                        return 1;
     180                }
     181        } else if ( const ast::TypeInstType * typeInstType =
     182                        dynamic_cast< const ast::TypeInstType * >( src ) ) {
     183                if ( const ast::EqvClass * eqv = env.lookup( typeInstType->name ) ) {
     184                        if ( eqv->bound ) {
     185                                // T * = S * for any S depends on the type bound to T
     186                                return ptrsAssignable( eqv->bound, dst, env );
     187                        }
     188                }
     189        }
    117190        return 0;
     191#endif
    118192}
    119193
  • src/ResolvExpr/PtrsCastable.cc

    r3623f9d r3e2f5e3  
    1414//
    1515
     16#include "AST/Decl.hpp"
     17#include "AST/Pass.hpp"
     18#include "AST/Type.hpp"
     19#include "AST/TypeEnvironment.hpp"
    1620#include "Common/PassVisitor.h"
    1721#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     
    2327
    2428namespace ResolvExpr {
    25         struct PtrsCastable : public WithShortCircuiting  {
     29        struct PtrsCastable_old : public WithShortCircuiting  {
    2630          public:
    27                 PtrsCastable( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer );
     31                PtrsCastable_old( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer );
    2832
    2933                int get_result() const { return result; }
     
    8690                        return objectCast( src, env, indexer );
    8791                } else {
    88                         PassVisitor<PtrsCastable> ptrs( dest, env, indexer );
     92                        PassVisitor<PtrsCastable_old> ptrs( dest, env, indexer );
    8993                        src->accept( ptrs );
    9094                        return ptrs.pass.get_result();
     
    9296        }
    9397
    94         PtrsCastable::PtrsCastable( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer )
     98        PtrsCastable_old::PtrsCastable_old( Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer )
    9599                : dest( dest ), result( 0 ), env( env ), indexer( indexer )     {
    96100        }
    97101
    98         void PtrsCastable::postvisit( VoidType * ) {
    99                 result = objectCast( dest, env, indexer );
    100         }
    101 
    102         void PtrsCastable::postvisit( BasicType * ) {
    103                 result = objectCast( dest, env, indexer );
    104         }
    105 
    106         void PtrsCastable::postvisit( PointerType * ) {
    107                 result = objectCast( dest, env, indexer );
    108         }
    109 
    110         void PtrsCastable::postvisit( ArrayType * ) {
    111                 result = objectCast( dest, env, indexer );
    112         }
    113 
    114         void PtrsCastable::postvisit( FunctionType * ) {
     102        void PtrsCastable_old::postvisit( VoidType * ) {
     103                result = objectCast( dest, env, indexer );
     104        }
     105
     106        void PtrsCastable_old::postvisit( BasicType * ) {
     107                result = objectCast( dest, env, indexer );
     108        }
     109
     110        void PtrsCastable_old::postvisit( PointerType * ) {
     111                result = objectCast( dest, env, indexer );
     112        }
     113
     114        void PtrsCastable_old::postvisit( ArrayType * ) {
     115                result = objectCast( dest, env, indexer );
     116        }
     117
     118        void PtrsCastable_old::postvisit( FunctionType * ) {
    115119                // result = -1;
    116120                result = functionCast( dest, env, indexer );
    117121        }
    118122
    119         void PtrsCastable::postvisit( StructInstType * ) {
    120                 result = objectCast( dest, env, indexer );
    121         }
    122 
    123         void PtrsCastable::postvisit( UnionInstType * ) {
    124                 result = objectCast( dest, env, indexer );
    125         }
    126 
    127         void PtrsCastable::postvisit( EnumInstType * ) {
     123        void PtrsCastable_old::postvisit( StructInstType * ) {
     124                result = objectCast( dest, env, indexer );
     125        }
     126
     127        void PtrsCastable_old::postvisit( UnionInstType * ) {
     128                result = objectCast( dest, env, indexer );
     129        }
     130
     131        void PtrsCastable_old::postvisit( EnumInstType * ) {
    128132                if ( dynamic_cast< EnumInstType* >( dest ) ) {
    129133                        result = 1;
     
    139143        }
    140144
    141         void PtrsCastable::postvisit( TraitInstType * ) {}
    142 
    143         void PtrsCastable::postvisit(TypeInstType *inst) {
     145        void PtrsCastable_old::postvisit( TraitInstType * ) {}
     146
     147        void PtrsCastable_old::postvisit(TypeInstType *inst ) {
    144148                //result = objectCast( inst, env, indexer ) > 0 && objectCast( dest, env, indexer ) > 0 ? 1 : -1;
    145149                result = objectCast( inst, env, indexer ) == objectCast( dest, env, indexer ) ? 1 : -1;
    146150        }
    147151
    148         void PtrsCastable::postvisit( TupleType * ) {
    149                 result = objectCast( dest, env, indexer );
    150         }
    151 
    152         void PtrsCastable::postvisit( VarArgsType * ) {
    153                 result = objectCast( dest, env, indexer );
    154         }
    155 
    156         void PtrsCastable::postvisit( ZeroType * ) {
    157                 result = objectCast( dest, env, indexer );
    158         }
    159 
    160         void PtrsCastable::postvisit( OneType * ) {
    161                 result = objectCast( dest, env, indexer );
    162         }
     152        void PtrsCastable_old::postvisit( TupleType * ) {
     153                result = objectCast( dest, env, indexer );
     154        }
     155
     156        void PtrsCastable_old::postvisit( VarArgsType * ) {
     157                result = objectCast( dest, env, indexer );
     158        }
     159
     160        void PtrsCastable_old::postvisit( ZeroType * ) {
     161                result = objectCast( dest, env, indexer );
     162        }
     163
     164        void PtrsCastable_old::postvisit( OneType * ) {
     165                result = objectCast( dest, env, indexer );
     166        }
     167
     168namespace {
     169        // can this type be cast to an object (1 for yes, -1 for no)
     170        int objectCast(
     171                const ast::Type * src, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab
     172        ) {
     173                if ( dynamic_cast< const ast::FunctionType * >( src ) ) {
     174                        return -1;
     175                } else if ( auto inst = dynamic_cast< const ast::TypeInstType * >( src ) ) {
     176                        if ( const ast::NamedTypeDecl * named = symtab.lookupType( inst->name ) ) {
     177                                if ( auto tyDecl = dynamic_cast< const ast::TypeDecl * >( named ) ) {
     178                                        if ( tyDecl->kind == ast::TypeVar::Ftype ) {
     179                                                return -1;
     180                                        }
     181                                }
     182                        } else if ( const ast::EqvClass * eqvClass = env.lookup( inst->name ) ) {
     183                                if ( eqvClass->data.kind == ast::TypeVar::Ftype ) {
     184                                        return -1;
     185                                }
     186                        }
     187                }
     188
     189                return 1;
     190        }
     191
     192        // can this type be cast to a function (inverse of objectCast)
     193        int functionCast(
     194                const ast::Type * src, const ast::TypeEnvironment & env, const ast::SymbolTable & symtab
     195        ) {
     196                return -1 * objectCast( src, env, symtab );
     197        }
     198
     199        class PtrsCastable_new : public ast::WithShortCircuiting {
     200                const ast::Type * dst;
     201                const ast::TypeEnvironment & env;
     202                const ast::SymbolTable & symtab;
     203        public:
     204                int result;
     205
     206                PtrsCastable_new(
     207                        const ast::Type * d, const ast::TypeEnvironment & e, const ast::SymbolTable & syms )
     208                : dst( d ), env( e ), symtab( syms ), result( 0 ) {}
     209
     210                void previsit( const ast::Type * ) { visit_children = false; }
     211
     212                void postvisit( const ast::VoidType * ) {
     213                        result = objectCast( dst, env, symtab );
     214                }
     215
     216                void postvisit( const ast::BasicType * ) {
     217                        result = objectCast( dst, env, symtab );
     218                }
     219
     220                void postvisit( const ast::PointerType * ) {
     221                        result = objectCast( dst, env, symtab );
     222                }
     223
     224                void postvisit( const ast::ArrayType * ) {
     225                        result = objectCast( dst, env, symtab );
     226                }
     227
     228                void postvisit( const ast::FunctionType * ) {
     229                        result = functionCast( dst, env, symtab );
     230                }
     231
     232                void postvisit( const ast::StructInstType * ) {
     233                        result = objectCast( dst, env, symtab );
     234                }
     235
     236                void postvisit( const ast::UnionInstType * ) {
     237                        result = objectCast( dst, env, symtab );
     238                }
     239
     240                void postvisit( const ast::EnumInstType * ) {
     241                        if ( dynamic_cast< const ast::EnumInstType * >( dst ) ) {
     242                                result = 1;
     243                        } else if ( auto bt = dynamic_cast< const ast::BasicType * >( dst ) ) {
     244                                if ( bt->kind == ast::BasicType::SignedInt ) {
     245                                        result = 0;
     246                                } else {
     247                                        result = 1;
     248                                }
     249                        } else {
     250                                result = objectCast( dst, env, symtab );
     251                        }
     252                }
     253
     254                void postvisit( const ast::TraitInstType * ) {}
     255
     256                void postvisit( const ast::TypeInstType * inst ) {
     257                        // check trait and destination type are both object or both function
     258                        result = objectCast( inst, env, symtab ) == objectCast( dst, env, symtab ) ? 1 : -1;
     259                }
     260
     261                void postvisit( const ast::TupleType * ) {
     262                        result = objectCast( dst, env, symtab );
     263                }
     264
     265                void postvisit( const ast::VarArgsType * ) {
     266                        result = objectCast( dst, env, symtab );
     267                }
     268
     269                void postvisit( const ast::ZeroType * ) {
     270                        result = objectCast( dst, env, symtab );
     271                }
     272
     273                void postvisit( const ast::OneType * ) {
     274                        result = objectCast( dst, env, symtab );
     275                }
     276
     277        };
     278} // anonymous namespace
     279
     280int ptrsCastable(
     281        const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     282        const ast::TypeEnvironment & env
     283) {
     284        if ( auto inst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
     285                if ( const ast::EqvClass * eqvClass = env.lookup( inst->name ) ) {
     286                        return ptrsAssignable( src, eqvClass->bound, env );
     287                }
     288        }
     289
     290        if ( dynamic_cast< const ast::VoidType * >( dst ) ) {
     291                return objectCast( src, env, symtab );
     292        } else {
     293                ast::Pass< PtrsCastable_new > ptrs{ dst, env, symtab };
     294                src->accept( ptrs );
     295                return ptrs.pass.result;
     296        }
     297}
     298
    163299} // namespace ResolvExpr
    164300
  • src/ResolvExpr/ResolveTypeof.cc

    r3623f9d r3e2f5e3  
    1818#include <cassert>               // for assert
    1919
     20#include "AST/CVQualifiers.hpp"
     21#include "AST/Node.hpp"
     22#include "AST/Pass.hpp"
     23#include "AST/Type.hpp"
     24#include "AST/TypeEnvironment.hpp"
    2025#include "Common/PassVisitor.h"  // for PassVisitor
     26#include "Common/utility.h"      // for copy
    2127#include "Resolver.h"            // for resolveInVoidContext
    2228#include "SynTree/Expression.h"  // for Expression
     
    4248        }
    4349
    44         class ResolveTypeof : public WithShortCircuiting {
     50        class ResolveTypeof_old : public WithShortCircuiting {
    4551          public:
    46                 ResolveTypeof( const SymTab::Indexer &indexer ) : indexer( indexer ) {}
     52                ResolveTypeof_old( const SymTab::Indexer &indexer ) : indexer( indexer ) {}
    4753                void premutate( TypeofType *typeofType );
    4854                Type * postmutate( TypeofType *typeofType );
     
    5359
    5460        Type * resolveTypeof( Type *type, const SymTab::Indexer &indexer ) {
    55                 PassVisitor<ResolveTypeof> mutator( indexer );
     61                PassVisitor<ResolveTypeof_old> mutator( indexer );
    5662                return type->acceptMutator( mutator );
    5763        }
    5864
    59         void ResolveTypeof::premutate( TypeofType * ) {
     65        void ResolveTypeof_old::premutate( TypeofType * ) {
    6066                visit_children = false;
    6167        }
    6268
    63         Type * ResolveTypeof::postmutate( TypeofType *typeofType ) {
     69        Type * ResolveTypeof_old::postmutate( TypeofType *typeofType ) {
    6470#if 0
    6571                std::cerr << "resolving typeof: ";
     
    108114        }
    109115
    110         const ast::Type * resolveTypeof( const ast::Type * type , const ast::SymbolTable & symtab ) {
    111                 #warning unimplemented
    112                 (void)type; (void)symtab;
    113                 assert(false);
    114                 return nullptr;
    115         }
     116namespace {
     117        struct ResolveTypeof_new : public ast::WithShortCircuiting {
     118                const ast::SymbolTable & localSymtab;
     119
     120                ResolveTypeof_new( const ast::SymbolTable & syms ) : localSymtab( syms ) {}
     121
     122                void premutate( const ast::TypeofType * ) { visit_children = false; }
     123
     124                const ast::Type * postmutate( const ast::TypeofType * typeofType ) {
     125                        // pass on null expression
     126                        if ( ! typeofType->expr ) return typeofType;
     127
     128                        ast::ptr< ast::Type > newType;
     129                        if ( auto tyExpr = typeofType->expr.as< ast::TypeExpr >() ) {
     130                                // typeof wrapping type
     131                                newType = tyExpr->type;
     132                        } else {
     133                                // typeof wrapping expression
     134                                ast::TypeEnvironment dummy;
     135                                ast::ptr< ast::Expr > newExpr =
     136                                        resolveInVoidContext( typeofType->expr, localSymtab, dummy );
     137                                assert( newExpr->result && ! newExpr->result->isVoid() );
     138                                newType = newExpr->result;
     139                        }
     140
     141                        // clear qualifiers for base, combine with typeoftype quals regardless
     142                        if ( typeofType->kind == ast::TypeofType::Basetypeof ) {
     143                                // replace basetypeof(<enum>) by int
     144                                if ( newType.as< ast::EnumInstType >() ) {
     145                                        newType = new ast::BasicType{
     146                                                ast::BasicType::SignedInt, newType->qualifiers, copy(newType->attributes) };
     147                                }
     148                                reset_qualifiers(
     149                                        newType,
     150                                        ( newType->qualifiers & ~ast::CV::EquivQualifiers ) | typeofType->qualifiers );
     151                        } else {
     152                                add_qualifiers( newType, typeofType->qualifiers );
     153                        }
     154
     155                        return newType;
     156                }
     157        };
     158} // anonymous namespace
     159
     160const ast::Type * resolveTypeof( const ast::Type * type , const ast::SymbolTable & symtab ) {
     161        ast::Pass< ResolveTypeof_new > mutator{ symtab };
     162        return type->accept( mutator );
     163}
     164
    116165} // namespace ResolvExpr
    117166
  • src/ResolvExpr/Resolver.cc

    r3623f9d r3e2f5e3  
    12261226                const ast::StaticAssertDecl * previsit( const ast::StaticAssertDecl * );
    12271227
    1228                 void previsit( const ast::ArrayType * );
    1229                 void previsit( const ast::PointerType * );
     1228                const ast::ArrayType * previsit( const ast::ArrayType * );
     1229                const ast::PointerType * previsit( const ast::PointerType * );
    12301230
    12311231                const ast::ExprStmt *        previsit( const ast::ExprStmt * );
     
    13341334
    13351335        template< typename PtrType >
    1336         void handlePtrType( const PtrType * type, const ast::SymbolTable & symtab ) {
    1337                 #warning unimplemented; needs support for new Validate::SizeType global
    1338                 (void)type; (void)symtab;
    1339                 assert( false );
    1340         }
    1341 
    1342         void Resolver_new::previsit( const ast::ArrayType * at ) {
    1343                 handlePtrType( at, symtab );
    1344         }
    1345 
    1346         void Resolver_new::previsit( const ast::PointerType * pt ) {
    1347                 handlePtrType( pt, symtab );
     1336        const PtrType * handlePtrType( const PtrType * type, const ast::SymbolTable & symtab ) {
     1337                if ( type->dimension ) {
     1338                        #warning should use new equivalent to Validate::SizeType rather than sizeType here
     1339                        ast::ptr< ast::Type > sizeType = new ast::BasicType{ ast::BasicType::LongUnsignedInt };
     1340                        ast::mutate_field(
     1341                                type, &PtrType::dimension,
     1342                                findSingleExpression( type->dimension, sizeType, symtab ) );
     1343                }
     1344                return type;
     1345        }
     1346
     1347        const ast::ArrayType * Resolver_new::previsit( const ast::ArrayType * at ) {
     1348                return handlePtrType( at, symtab );
     1349        }
     1350
     1351        const ast::PointerType * Resolver_new::previsit( const ast::PointerType * pt ) {
     1352                return handlePtrType( pt, symtab );
    13481353        }
    13491354
  • src/ResolvExpr/typeops.h

    r3623f9d r3e2f5e3  
    9999        // in PtrsCastable.cc
    100100        int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer );
     101        int ptrsCastable(
     102                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
     103                const ast::TypeEnvironment & env );
    101104
    102105        // in Unify.cc
Note: See TracChangeset for help on using the changeset viewer.