Index: doc/papers/llheap/Paper.tex =================================================================== --- doc/papers/llheap/Paper.tex (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ doc/papers/llheap/Paper.tex (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -252,6 +252,6 @@ Dynamic code/data memory is managed by the dynamic loader for libraries loaded at runtime, which is complex especially in a multi-threaded program~\cite{Huang06}. However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control. -Stack memory is managed by the program call/return-mechanism using a simple LIFO technique, which works well for sequential programs. -For stackful coroutines and user threads, a new stack is commonly created in dynamic-allocation memory. +Stack memory is managed by the program call/return-mechanism using a LIFO technique, which works well for sequential programs. +For stackful coroutines and user threads, a new stack is commonly created in the dynamic-allocation memory. This work focuses solely on management of the dynamic-allocation memory. @@ -293,8 +293,8 @@ \begin{enumerate}[leftmargin=*,itemsep=0pt] \item -Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running on multiple kernel threads (M:N threading). - -\item -Extend the standard C heap functionality by preserving with each allocation: its request size plus the amount allocated, whether an allocation is zero fill, and allocation alignment. +Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC~\cite{uC++} and \CFA~\cite{Moss18,Delisle21} using user-level threads running on multiple kernel threads (M:N threading). + +\item +Extend the standard C heap functionality by preserving with each allocation: its request size plus the amount allocated, whether an allocation is zero fill and/or allocation alignment. \item @@ -365,5 +365,5 @@ The following discussion is a quick overview of the moving-pieces that affect the design of a memory allocator and its performance. -It is assumed that dynamic allocates and deallocates acquire storage for a program variable, referred to as an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC. +Dynamic acquires and releases obtain storage for a program variable, called an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC. Space for each allocated object comes from the dynamic-allocation zone. @@ -378,6 +378,5 @@ Figure~\ref{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}. -The \newterm{management data} is a data structure located at a known memory address and contains all information necessary to manage the storage data. -The management data starts with fixed-sized information in the static-data memory that references components in the dynamic-allocation memory. +The \newterm{management data} is a data structure located at a known memory address and contains fixed-sized information in the static-data memory that references components in the dynamic-allocation memory. For multi-threaded programs, additional management data may exist in \newterm{thread-local storage} (TLS) for each kernel thread executing the program. The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}. @@ -385,6 +384,6 @@ \ie only the program knows the location of allocated storage not the memory allocator. Freed objects (white) represent memory deallocated by the program, which are linked into one or more lists facilitating easy location of new allocations. -Reserved memory (dark grey) is one or more blocks of memory obtained from the operating system but not yet allocated to the program; -if there are multiple reserved blocks, they are also chained together, usually internally. +Reserved memory (dark grey) is one or more blocks of memory obtained from the \newterm{operating system} (OS) but not yet allocated to the program; +if there are multiple reserved blocks, they are also chained together. \begin{figure} @@ -395,5 +394,5 @@ \end{figure} -In most allocator designs, allocated objects have management data embedded within them. +In many allocator designs, allocated objects and reserved blocks have management data embedded within them (see also Section~\ref{s:ObjectContainers}). Figure~\ref{f:AllocatedObject} shows an allocated object with a header, trailer, and optional spacing around the object. The header contains information about the object, \eg size, type, etc. @@ -404,8 +403,8 @@ When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists. -A free object also contains management data, \eg size, pointers, etc. +A free object often contains management data, \eg size, pointers, etc. Often the free list is chained internally so it does not consume additional storage, \ie the link fields are placed at known locations in the unused memory blocks. For internal chaining, the amount of management data for a free node defines the minimum allocation size, \eg if 16 bytes are needed for a free-list node, allocation requests less than 16 bytes are rounded up. -The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new management information and/or program data. +The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new program data and/or management information. \begin{figure} @@ -428,5 +427,5 @@ \label{s:Fragmentation} -Fragmentation is memory requested from the operating system but not used by the program; +Fragmentation is memory requested from the OS but not used by the program; hence, allocated objects are not fragmentation. Figure~\ref{f:InternalExternalFragmentation} shows fragmentation is divided into two forms: internal or external. @@ -443,8 +442,8 @@ An allocator should strive to keep internal management information to a minimum. -\newterm{External fragmentation} is all memory space reserved from the operating system but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory. +\newterm{External fragmentation} is all memory space reserved from the OS but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory. This memory is problematic in two ways: heap blowup and highly fragmented memory. \newterm{Heap blowup} occurs when freed memory cannot be reused for future allocations leading to potentially unbounded external fragmentation growth~\cite{Berger00}. -Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects, resulting in a checkerboard of adjacent allocated and free areas, where the free blocks have become very small. +Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects, resulting in a checkerboard of adjacent allocated and free areas, where the free blocks have become to small to service requests. % Figure~\ref{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time. Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory (the allocated size cannot use a larger free block) and/or no coalescing of free storage. @@ -452,5 +451,5 @@ % Memory is highly fragmented when most free blocks are unusable because of their sizes. % For example, Figure~\ref{f:Contiguous} and Figure~\ref{f:HighlyFragmented} have the same quantity of external fragmentation, but Figure~\ref{f:HighlyFragmented} is highly fragmented. -% If there is a request to allocate a large object, Figure~\ref{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while Figure~\ref{f:HighlyFragmented} likely has to request more memory from the operating system. +% If there is a request to allocate a large object, Figure~\ref{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while Figure~\ref{f:HighlyFragmented} likely has to request more memory from the OS. % \begin{figure} @@ -475,5 +474,5 @@ The first approach is a \newterm{sequential-fit algorithm} with one list of free objects that is searched for a block large enough to fit a requested object size. Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size. -Any storage larger than the request can become spacing after the object or be split into a smaller free object. +Any storage larger than the request can become spacing after the object or split into a smaller free object. % The cost of the search depends on the shape and quality of the free list, \eg a linear versus a binary-tree free-list, a sorted versus unsorted free-list. @@ -489,9 +488,9 @@ The third approach is \newterm{splitting} and \newterm{coalescing algorithms}. -When an object is allocated, if there are no free objects of the requested size, a larger free object may be split into two smaller objects to satisfy the allocation request without obtaining more memory from the operating system. -For example, in the \newterm{buddy system}, a block of free memory is split into two equal chunks, one of those chunks is again split into two equal chunks, and so on until a block just large enough to fit the requested object is created. -When an object is deallocated it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger object. +When an object is allocated, if there are no free objects of the requested size, a larger free object is split into two smaller objects to satisfy the allocation request rather than obtaining more memory from the OS. +For example, in the \newterm{buddy system}, a block of free memory is split into equal chunks, one of those chunks is again split, and so on until a minimal block is created that fits the requested object. +When an object is deallocated, it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger block. Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled. -In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing. +In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays. While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup. % Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory. @@ -501,10 +500,10 @@ \label{s:Locality} -The principle of locality recognizes that programs tend to reference a small set of data, called a working set, for a certain period of time, where a working set is composed of temporal and spatial accesses~\cite{Denning05}. +The principle of locality recognizes that programs tend to reference a small set of data, called a \newterm{working set}, for a certain period of time, composed of temporal and spatial accesses~\cite{Denning05}. % Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period. % Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array. -Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy. +Hardware takes advantage of the working set through multiple levels of caching, \ie memory hierarchy. % When an object is accessed, the memory physically located around the object is also cached with the expectation that the current and nearby objects will be referenced within a short period of time. -For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory. +For example, entire cache lines are transferred between cache and memory, and entire virtual-memory pages are transferred between memory and disk. % A program exhibiting good locality has better performance due to fewer cache misses and page faults\footnote{With the advent of large RAM memory, paging is becoming less of an issue in modern programming.}. @@ -532,10 +531,10 @@ \label{s:MutualExclusion} -\newterm{Mutual exclusion} provides sequential access to the shared management data of the heap. +\newterm{Mutual exclusion} provides sequential access to the shared-management data of the heap. There are two performance issues for mutual exclusion. First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed. Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released. Contention can be reduced in a number of ways: -1) Using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks. +1) Using multiple fine-grained locks versus a single lock to spread the contention across a number of locks. 2) Using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff. 3) Using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}. @@ -551,6 +550,6 @@ a memory allocator can only affect the latter two. -Assume two objects, object$_1$ and object$_2$, share a cache line. -\newterm{Program-induced false-sharing} occurs when thread$_1$ passes a reference to object$_2$ to thread$_2$, and then threads$_1$ modifies object$_1$ while thread$_2$ modifies object$_2$. +Specifically, assume two objects, O$_1$ and O$_2$, share a cache line, with threads, T$_1$ and T$_2$. +\newterm{Program-induced false-sharing} occurs when T$_1$ passes a reference to O$_2$ to T$_2$, and then T$_1$ modifies O$_1$ while T$_2$ modifies O$_2$. % Figure~\ref{f:ProgramInducedFalseSharing} shows when Thread$_1$ passes Object$_2$ to Thread$_2$, a false-sharing situation forms when Thread$_1$ modifies Object$_1$ and Thread$_2$ modifies Object$_2$. % Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line. @@ -574,5 +573,5 @@ % \label{f:FalseSharing} % \end{figure} -\newterm{Allocator-induced active false-sharing}\label{s:AllocatorInducedActiveFalseSharing} occurs when object$_1$ and object$_2$ are heap allocated and their references are passed to thread$_1$ and thread$_2$, which modify the objects. +\newterm{Allocator-induced active false-sharing}\label{s:AllocatorInducedActiveFalseSharing} occurs when O$_1$ and O$_2$ are heap allocated and their references are passed to T$_1$ and T$_2$, which modify the objects. % For example, in Figure~\ref{f:AllocatorInducedActiveFalseSharing}, each thread allocates an object and loads a cache-line of memory into its associated cache. % Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line. @@ -580,5 +579,5 @@ % is another form of allocator-induced false-sharing caused by program-induced false-sharing. % When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing. -when thread$_1$ passes object$_2$ to thread$_2$, and thread$_2$ subsequently deallocates object$_2$, and then object$_2$ is reallocated to thread$_2$ while thread$_1$ is still using object$_1$. +when T$_1$ passes O$_2$ to T$_2$, and T$_2$ subsequently deallocates O$_2$, and then O$_2$ is reallocated to T$_2$ while T$_1$ is still using O$_1$. @@ -593,12 +592,5 @@ \label{s:MultiThreadedMemoryAllocatorFeatures} -The following features are used in the construction of multi-threaded memory-allocators: -\begin{enumerate}[itemsep=0pt] -\item multiple heaps: with or without a global heap, or with or without heap ownership. -\item object containers: with or without ownership, fixed or variable sized, global or local free-lists. -\item hybrid private/public heap -\item allocation buffer -\item lock-free operations -\end{enumerate} +The following features are used in the construction of multi-threaded memory-allocators: multiple heaps, user-level threading, ownership, object containers, allocation buffer, lock-free operations. The first feature, multiple heaps, pertains to different kinds of heaps. The second feature, object containers, pertains to the organization of objects within the storage area. @@ -606,10 +598,10 @@ -\subsection{Multiple Heaps} +\subsubsection{Multiple Heaps} \label{s:MultipleHeaps} A multi-threaded allocator has potentially multiple threads and heaps. The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity. -The spectrum ranges from multiple threads using a single heap, denoted as T:1 (see Figure~\ref{f:SingleHeap}), to multiple threads sharing multiple heaps, denoted as T:H (see Figure~\ref{f:SharedHeaps}), to one thread per heap, denoted as 1:1 (see Figure~\ref{f:PerThreadHeap}), which is almost back to a single-threaded allocator. +The spectrum ranges from multiple threads using a single heap, denoted as T:1, to multiple threads sharing multiple heaps, denoted as T:H, to one thread per heap, denoted as 1:1, which is almost back to a single-threaded allocator. \begin{figure} @@ -635,12 +627,12 @@ \end{figure} -\paragraph{T:1 model} where all threads allocate and deallocate objects from one heap. -Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS); -the heap may also return freed memory to the operating system. +\paragraph{T:1 model (see Figure~\ref{f:SingleHeap})} where all threads allocate and deallocate objects from one heap. +Memory is obtained from the freed objects, or reserved memory in the heap, or from the OS; +the heap may also return freed memory to the OS. The arrows indicate the direction memory conceptually moves for each kind of operation: allocation moves memory along the path from the heap/operating-system to the user application, while deallocation moves memory along the path from the application back to the heap/operating-system. To safely handle concurrency, a single lock may be used for all heap operations or fine-grained locking for different operations. Regardless, a single heap may be a significant source of contention for programs with a large amount of memory allocation. -\paragraph{T:H model} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps. +\paragraph{T:H model (see Figure~\ref{f:SharedHeaps})} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps. The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design. To determine which heap to access, each thread must point to its associated heap in some way. @@ -673,5 +665,5 @@ An alternative implementation is for all heaps to share one reserved memory, which requires a separate lock for the reserved storage to ensure mutual exclusion when acquiring new memory. Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur. -Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the operating system. +Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the OS. % \begin{figure} @@ -684,23 +676,21 @@ Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup. The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory. -Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive. -Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix. -In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused. +Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the OS (see Section~\ref{s:Ownership}). +Returning storage to the OS may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix. +% In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused. Adding a \newterm{global heap} (G) attempts to reduce the cost of obtaining/returning memory among heaps (sharing) by buffering storage within the application address-space. -Now, each heap obtains and returns storage to/from the global heap rather than the operating system. +Now, each heap obtains and returns storage to/from the global heap rather than the OS. Storage is obtained from the global heap only when a heap allocation cannot be fulfilled, and returned to the global heap when a heap's free memory exceeds some threshold. -Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary. +Similarly, the global heap buffers this memory, obtaining and returning storage to/from the OS as necessary. The global heap does not have its own thread and makes no internal allocation requests; instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations. Hence, the worst-case cost of a memory operation includes all these steps. -With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the operating system to achieve the same goal and is independent of the mechanism used by the operating system to present dynamic memory to an address space. - +With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the OS to achieve the same goal and is independent of the mechanism used by the OS to present dynamic memory to an address space. However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking. A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention. In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap. - -\paragraph{1:1 model (thread heaps)} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see ownership in Section~\ref{s:Ownership}). +\paragraph{1:1 model (see Figure~\ref{f:PerThreadHeap})} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see Section~\ref{s:Ownership}). An additional benefit of thread heaps is improved locality due to better memory layout. As each thread only allocates from its heap, all objects are consolidated in the storage area for that heap, better utilizing each CPUs cache and accessing fewer pages. @@ -708,5 +698,5 @@ Thread heaps can also eliminate allocator-induced active false-sharing, if memory is acquired so it does not overlap at crucial boundaries with memory for another thread's heap. For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them. -Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps. +% Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps. When a thread terminates, there are two options for handling its thread heap. @@ -720,5 +710,5 @@ It is possible to use any of the heap models with user-level (M:N) threading. -However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the operating system, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000). +However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the OS, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000). It is difficult to retain this goal, if the user-threading model is directly involved with the heap model. Figure~\ref{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model is provided by the language runtime. @@ -732,15 +722,15 @@ \end{figure} -Adopting this model results in a subtle problem with shared heaps. -With kernel threading, an operation that is started by a kernel thread is always completed by that thread. -For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption. +Adopting user threading results in a subtle problem with shared heaps. +With kernel threading, an operation started by a kernel thread is always completed by that thread. +For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap, even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption. However, this correctness property is not preserved for user-level threading. A user thread can start an allocation/deallocation on one kernel thread, be preempted (time slice), and continue running on a different kernel thread to complete the operation~\cite{Dice02}. When the user thread continues on the new kernel thread, it may have pointers into the previous kernel-thread's heap and hold locks associated with it. To get the same kernel-thread safety, time slicing must be disabled/\-enabled around these operations, so the user thread cannot jump to another kernel thread. -However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption does not happen that frequently. +However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption is infrequent (milliseconds). Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically. -Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation; -techniques like rollforward can be used to force an eventual preemption. +Occasional ignoring of a preemption should be benign, but a persistent lack of preemption can result in starvation; +techniques like rolling forward the preemption to the next context switch can be used. @@ -800,4 +790,38 @@ % For example, in Figure~\ref{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially. % If Thread$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur. + +For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps.% (see~Figure~\ref{f:HybridPrivatePublicHeap}). +The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup. +In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap. +Similarly, a thread first deallocates an object to its private heap, and second to the public heap. +Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps. +% Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap. +Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which does allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return. + +% \begin{figure} +% \centering +% \input{PrivatePublicHeaps.pstex_t} +% \caption{Hybrid Private/Public Heap for Per-thread Heaps} +% \label{f:HybridPrivatePublicHeap} +% \vspace{10pt} +% \input{RemoteFreeList.pstex_t} +% \caption{Remote Free-List} +% \label{f:RemoteFreeList} +% \end{figure} + +% As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified. +% For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}. +% To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage. +% Since the remote free-list is occasionally cleared during an allocation, this adds to that cost. +% Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object. + +% If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking. +% In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur. +% If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations. + +% The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator. +% Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used. +% In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps. +% For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach. @@ -817,5 +841,5 @@ -\subsection{Object Containers} +\subsubsection{Object Containers} \label{s:ObjectContainers} @@ -827,5 +851,5 @@ \eg an object is accessed by the program after it is allocated, while the header is accessed by the allocator after it is free. -The alternative factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks} in~\cite{Berger00}), as in Figure~\ref{f:ObjectContainer}. +An alternative approach factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks}~\cite{Berger00}), as in Figure~\ref{f:ObjectContainer}. The header for the container holds information necessary for all objects in the container; a trailer may also be used at the end of the container. @@ -862,5 +886,5 @@ -\subsubsection{Container Ownership} +\paragraph{Container Ownership} \label{s:ContainerOwnership} @@ -894,8 +918,8 @@ Additional restrictions may be applied to the movement of containers to prevent active false-sharing. -For example, if a container changes ownership through the global heap, then when a thread allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads. +For example, if a container changes ownership through the global heap, then a thread allocating from the newly acquired container is actively false-sharing even though no objects are passed among threads. Note, once the thread frees the object, no more false sharing can occur until the container changes ownership again. To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free. -One implementation approach that increases the freedom to return a free container to the operating system involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the operating system. +One implementation approach that increases the freedom to return a free container to the OS involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the OS. % \begin{figure} @@ -930,5 +954,5 @@ -\subsubsection{Container Size} +\paragraph{Container Size} \label{s:ContainerSize} @@ -941,5 +965,5 @@ However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation. With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container. -In general, large objects, \eg greater than 64\,KB, are allocated directly from the operating system and are returned immediately to the operating system to reduce long-term external fragmentation. +In general, large objects, \eg greater than 64\,KB, are allocated directly from the OS and are returned immediately to the OS to reduce long-term external fragmentation. If the container size is small, \eg 1\,KB, then a 1.5\,KB object is treated as a large object, which is likely to be inappropriate. Ideally, it is best to use smaller containers for smaller objects, and larger containers for medium objects, which leads to the issue of locating the container header. @@ -970,5 +994,5 @@ -\subsubsection{Container Free-Lists} +\paragraph{Container Free-Lists} \label{s:containersfreelists} @@ -1005,49 +1029,10 @@ -\subsubsection{Hybrid Private/Public Heap} -\label{s:HybridPrivatePublicHeap} - -Section~\ref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership). -For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps (see~Figure~\ref{f:HybridPrivatePublicHeap}). -The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup. -In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap. -Similarly, a thread first deallocates an object to its private heap, and second to the public heap. -Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps. -Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap. -Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return. - -\begin{figure} -\centering -\input{PrivatePublicHeaps.pstex_t} -\caption{Hybrid Private/Public Heap for Per-thread Heaps} -\label{f:HybridPrivatePublicHeap} -% \vspace{10pt} -% \input{RemoteFreeList.pstex_t} -% \caption{Remote Free-List} -% \label{f:RemoteFreeList} -\end{figure} - -As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified. -For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}. -To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage. -Since the remote free-list is occasionally cleared during an allocation, this adds to that cost. -Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object. - -If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking. -In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur. -If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations. - -The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator. -Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used. -In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps. -For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach. - - -\subsection{Allocation Buffer} +\subsubsection{Allocation Buffer} \label{s:AllocationBuffer} An allocation buffer is reserved memory (see Section~\ref{s:AllocatorComponents}) not yet allocated to the program, and is used for allocating objects when the free list is empty. That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later. -Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively. +Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or OS, respectively. The allocation buffer reduces contention and the number of global/operating-system calls. For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations. @@ -1062,5 +1047,5 @@ Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated. -A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system. +A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or OS. The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer. @@ -1068,8 +1053,8 @@ For example, when a container is created, rather than placing all objects within the container on the free list, the objects form an allocation buffer and are allocated from the buffer as allocation requests are made. This lazy method of constructing objects is beneficial in terms of paging and caching. -For example, although an entire container, possibly spanning several pages, is allocated from the operating system, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache. - - -\subsection{Lock-Free Operations} +For example, although an entire container, possibly spanning several pages, is allocated from the OS, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache. + + +\subsubsection{Lock-Free Operations} \label{s:LockFreeOperations} @@ -1194,7 +1179,7 @@ % A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable} % \end{quote} -% If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness. +% If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness. % Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable. -% Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the operating system is providing the second thread via the signal handler. +% Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler. % % Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted. @@ -1256,7 +1241,7 @@ A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable} \end{quote} -If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness. +If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness. Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable. -Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the operating system is providing the second thread via the signal handler. +Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler. Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted. @@ -1273,5 +1258,5 @@ For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath. However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs. -More operating system support is required to make this model viable, but there is still the serially-reusable problem with user-level threading. +More OS support is required to make this model viable, but there is still the serially-reusable problem with user-level threading. So the 1:1 model had no atomic actions along the fastpath and no special operating-system support requirements. The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in Section~\ref{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns. @@ -1308,5 +1293,5 @@ A primary goal of llheap is low latency, hence the name low-latency heap (llheap). Two forms of latency are internal and external. -Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the operating system. +Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the OS. Ideally latency is $O(1)$ with a small constant. @@ -1314,5 +1299,5 @@ The mitigating factor is that most programs have well behaved allocation patterns, where the majority of allocation operations can be $O(1)$, and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger). -To obtain $O(1)$ external latency means obtaining one large storage area from the operating system and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation. +To obtain $O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation. Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable. The mitigating factor is that operating-system calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}). @@ -1329,7 +1314,7 @@ headers per allocation versus containers, no coalescing to minimize latency, -global heap memory (pool) obtained from the operating system using @mmap@ to create and reuse heaps needed by threads, +global heap memory (pool) obtained from the OS using @mmap@ to create and reuse heaps needed by threads, local reserved memory (pool) per heap obtained from global pool, -global reserved memory (pool) obtained from the operating system using @sbrk@ call, +global reserved memory (pool) obtained from the OS using @sbrk@ call, optional fast-lookup table for converting allocation requests into bucket sizes, optional statistic-counters table for accumulating counts of allocation operations. @@ -1358,5 +1343,5 @@ Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M. All objects in a bucket are of the same size. -The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the operating system. +The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the OS. Each free bucket of a specific size has two lists. 1) A free stack used solely by the KT heap-owner, so push/pop operations do not require locking. @@ -1367,5 +1352,5 @@ Algorithm~\ref{alg:heapObjectAlloc} shows the allocation outline for an object of size $S$. First, the allocation is divided into small (@sbrk@) or large (@mmap@). -For large allocations, the storage is mapped directly from the operating system. +For large allocations, the storage is mapped directly from the OS. For small allocations, $S$ is quantized into a bucket size. Quantizing is performed using a binary search over the ordered bucket array. @@ -1378,5 +1363,5 @@ heap's local pool, global pool, -operating system (@sbrk@). +OS (@sbrk@). \begin{algorithm} @@ -1443,5 +1428,5 @@ Algorithm~\ref{alg:heapObjectFreeOwn} shows the de-allocation (free) outline for an object at address $A$ with ownership. First, the address is divided into small (@sbrk@) or large (@mmap@). -For large allocations, the storage is unmapped back to the operating system. +For large allocations, the storage is unmapped back to the OS. For small allocations, the bucket associated with the request size is retrieved. If the bucket is local to the thread, the allocation is pushed onto the thread's associated bucket. @@ -3044,5 +3029,5 @@ \textsf{pt3} is the only memory allocator where the total dynamic memory goes down in the second half of the program lifetime when the memory is freed by the benchmark program. -It makes pt3 the only memory allocator that gives memory back to the operating system as it is freed by the program. +It makes pt3 the only memory allocator that gives memory back to the OS as it is freed by the program. % FOR 1 THREAD Index: doc/papers/llheap/figures/AllocatorComponents.fig =================================================================== --- doc/papers/llheap/figures/AllocatorComponents.fig (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ doc/papers/llheap/figures/AllocatorComponents.fig (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -8,5 +8,4 @@ -2 1200 2 -6 1275 2025 2700 2625 6 2400 2025 2700 2625 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 @@ -14,6 +13,4 @@ 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 2700 2025 2700 2325 2400 2325 2400 2025 2700 2025 --6 -4 2 0 50 -1 2 11 0.0000 2 165 1005 2325 2400 Management\001 -6 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 @@ -61,7 +58,9 @@ 2 2 0 1 0 7 60 -1 13 0.000 0 0 -1 0 0 5 3300 2700 6300 2700 6300 3000 3300 3000 3300 2700 -4 0 0 50 -1 2 11 0.0000 2 165 585 3300 1725 Storage\001 +4 0 0 50 -1 2 11 0.0000 2 165 1005 3300 1725 Storage Data\001 4 2 0 50 -1 0 11 0.0000 2 165 810 3000 1875 free objects\001 4 2 0 50 -1 0 11 0.0000 2 135 1140 3000 2850 reserve memory\001 4 1 0 50 -1 0 11 0.0000 2 120 795 2325 1500 Static Zone\001 4 1 0 50 -1 0 11 0.0000 2 165 1845 4800 1500 Dynamic-Allocation Zone\001 +4 2 0 50 -1 2 11 0.0000 2 165 1005 2325 2325 Management\001 +4 2 0 50 -1 2 11 0.0000 2 135 375 2325 2525 Data\001 Index: c/papers/llheap/figures/AllocatorComponents.fig.bak =================================================================== --- doc/papers/llheap/figures/AllocatorComponents.fig.bak (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ (revision ) @@ -1,67 +1,0 @@ -#FIG 3.2 Produced by xfig version 3.2.7b -Landscape -Center -Inches -Letter -100.00 -Single --2 -1200 2 -6 1275 2025 2700 2625 -6 2400 2025 2700 2625 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 2700 2325 2700 2625 2400 2625 2400 2325 2700 2325 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 2700 2025 2700 2325 2400 2325 2400 2025 2700 2025 --6 -4 2 0 50 -1 2 11 0.0000 2 165 1005 2325 2400 Management\001 --6 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 4200 1800 4800 1800 4800 2100 4200 2100 4200 1800 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 4200 2100 5100 2100 5100 2400 4200 2400 4200 2100 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 5100 2100 6300 2100 6300 2400 5100 2400 5100 2100 -2 2 0 1 0 7 50 -1 17 0.000 0 0 -1 0 0 5 - 3300 1800 4200 1800 4200 2100 3300 2100 3300 1800 -2 2 0 1 0 7 50 -1 17 0.000 0 0 -1 0 0 5 - 5400 1800 6300 1800 6300 2100 5400 2100 5400 1800 -2 2 0 1 0 7 50 -1 17 0.000 0 0 -1 0 0 5 - 3300 2100 3600 2100 3600 2400 3300 2400 3300 2100 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 3300 2400 3900 2400 3900 2700 3300 2700 3300 2400 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 3900 2400 4800 2400 4800 2700 3900 2700 3900 2400 -2 2 0 1 0 7 50 -1 17 0.000 0 0 -1 0 0 5 - 4800 2400 5400 2400 5400 2700 4800 2700 4800 2400 -2 2 0 1 0 7 50 -1 17 0.000 0 0 -1 0 0 5 - 4800 1800 5400 1800 5400 2100 4800 2100 4800 1800 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 5400 2400 6300 2400 6300 2700 5400 2700 5400 2400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 45.00 90.00 - 3750 1950 4800 1800 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 45.00 90.00 - 5100 1950 3300 2100 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 45.00 90.00 - 3450 2250 4800 2400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 45.00 90.00 - 5100 2550 5400 2100 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 45.00 90.00 - 2550 2175 3300 1800 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 45.00 90.00 - 2550 2475 3300 2700 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3150 1275 3150 3000 -2 2 0 1 0 7 60 -1 13 0.000 0 0 -1 0 0 5 - 3300 2700 6300 2700 6300 3000 3300 3000 3300 2700 -4 1 0 50 -1 0 11 0.0000 2 120 795 2325 1425 Static Zone\001 -4 1 0 50 -1 0 11 0.0000 2 165 1845 4800 1425 Dynamic-Allocation Zone\001 -4 0 0 50 -1 2 11 0.0000 2 165 585 3300 1725 Storage\001 -4 2 0 50 -1 0 11 0.0000 2 165 810 3000 1875 free objects\001 -4 2 0 50 -1 0 11 0.0000 2 135 1140 3000 2850 reserve memory\001 Index: doc/user/figures/EHMHierarchy.fig =================================================================== --- doc/user/figures/EHMHierarchy.fig (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ doc/user/figures/EHMHierarchy.fig (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -29,10 +29,10 @@ 1 1 1.00 60.00 90.00 4950 1950 4950 1725 -4 1 0 50 -1 0 13 0.0000 2 135 225 1950 1650 IO\001 -4 1 0 50 -1 0 13 0.0000 2 135 915 4950 1650 Arithmetic\001 -4 1 0 50 -1 0 13 0.0000 2 150 330 1350 2100 File\001 -4 1 0 50 -1 0 13 0.0000 2 135 735 2550 2100 Network\001 -4 1 0 50 -1 0 13 0.0000 2 180 1215 3750 2100 DivideByZero\001 -4 1 0 50 -1 0 13 0.0000 2 150 810 4950 2100 Overflow\001 -4 1 0 50 -1 0 13 0.0000 2 150 915 6000 2100 Underflow\001 -4 1 0 50 -1 0 13 0.0000 2 180 855 3450 1200 Exception\001 +4 1 0 50 -1 0 12 0.0000 2 135 225 1950 1650 IO\001 +4 1 0 50 -1 0 12 0.0000 2 135 915 4950 1650 Arithmetic\001 +4 1 0 50 -1 0 12 0.0000 2 150 330 1350 2100 File\001 +4 1 0 50 -1 0 12 0.0000 2 135 735 2550 2100 Network\001 +4 1 0 50 -1 0 12 0.0000 2 180 1215 3750 2100 DivideByZero\001 +4 1 0 50 -1 0 12 0.0000 2 150 810 4950 2100 Overflow\001 +4 1 0 50 -1 0 12 0.0000 2 150 915 6000 2100 Underflow\001 +4 1 0 50 -1 0 12 0.0000 2 180 855 3450 1200 Exception\001 Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ doc/user/user.tex (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Mon Aug 22 23:43:30 2022 -%% Update Count : 5503 +%% Last Modified On : Mon Jun 5 21:18:29 2023 +%% Update Count : 5521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -108,6 +108,6 @@ \huge \CFA Team (past and present) \medskip \\ \Large Andrew Beach, Richard Bilson, Michael Brooks, Peter A. Buhr, Thierry Delisle, \smallskip \\ -\Large Glen Ditchfield, Rodolfo G. Esteves, Aaron Moss, Colby Parsons, Rob Schluntz, \smallskip \\ -\Large Fangren Yu, Mubeen Zulfiqar +\Large Glen Ditchfield, Rodolfo G. Esteves, Jiada Liang, Aaron Moss, Colby Parsons \smallskip \\ +\Large Rob Schluntz, Fangren Yu, Mubeen Zulfiqar }% author @@ -169,7 +169,7 @@ Like \Index*[C++]{\CC{}}, there may be both old and new ways to achieve the same effect. For example, the following programs compare the C, \CFA, and \CC I/O mechanisms, where the programs output the same result. -\begin{flushleft} -\begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}} -\multicolumn{1}{@{}c@{\hspace{1em}}}{\textbf{C}} & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}} \\ +\begin{center} +\begin{tabular}{@{}lll@{}} +\multicolumn{1}{@{}c}{\textbf{C}} & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}} \\ \begin{cfa}[tabsize=3] #include $\indexc{stdio.h}$ @@ -199,5 +199,5 @@ \end{cfa} \end{tabular} -\end{flushleft} +\end{center} While \CFA I/O \see{\VRef{s:StreamIOLibrary}} looks similar to \Index*[C++]{\CC{}}, there are important differences, such as automatic spacing between variables and an implicit newline at the end of the expression list, similar to \Index*{Python}~\cite{Python}. @@ -856,5 +856,5 @@ still works. Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments. -Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\Indexc{fallthru}, \eg: +Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\-\Indexc{fallthru}, \eg: \begin{cfa} ®choose® ( i ) { @@ -1167,5 +1167,5 @@ \end{cfa} \end{itemize} -\R{Warning}: specifying the down-to range maybe unexcepted because the loop control \emph{implicitly} switches the L and H values (and toggles the increment/decrement for I): +\R{Warning}: specifying the down-to range maybe unexpected because the loop control \emph{implicitly} switches the L and H values (and toggles the increment/decrement for I): \begin{cfa} for ( i; 1 ~ 10 ) ${\C[1.5in]{// up range}$ @@ -1173,5 +1173,5 @@ for ( i; ®10 -~ 1® ) ${\C{// \R{WRONG down range!}}\CRT}$ \end{cfa} -The reason for this sematics is that the range direction can be toggled by adding/removing the minus, ©'-'©, versus interchanging the L and H expressions, which has a greater chance of introducing errors. +The reason for this semantics is that the range direction can be toggled by adding/removing the minus, ©'-'©, versus interchanging the L and H expressions, which has a greater chance of introducing errors. @@ -2256,10 +2256,10 @@ Days days = Mon; // enumeration type declaration and initialization \end{cfa} -The set of enums are injected into the variable namespace at the definition scope. -Hence, enums may be overloaded with enum/variable/function names. -\begin{cfa} +The set of enums is injected into the variable namespace at the definition scope. +Hence, enums may be overloaded with variable, enum, and function names. +\begin{cfa} +int Foo; $\C{// type/variable separate namespaces}$ enum Foo { Bar }; enum Goo { Bar }; $\C[1.75in]{// overload Foo.Bar}$ -int Foo; $\C{// type/variable separate namespace}$ double Bar; $\C{// overload Foo.Bar, Goo.Bar}\CRT$ \end{cfa} @@ -2301,5 +2301,5 @@ Hence, the value of enum ©Mon© is 0, ©Tue© is 1, ...\,, ©Sun© is 6. If an enum value is specified, numbering continues by one from that value for subsequent unnumbered enums. -If an enum value is an expression, the compiler performs constant-folding to obtain a constant value. +If an enum value is a \emph{constant} expression, the compiler performs constant-folding to obtain a constant value. \CFA allows other integral types with associated values. @@ -2313,10 +2313,10 @@ \begin{cfa} // non-integral numeric -enum( ®double® ) Math { PI_2 = 1.570796, PI = 3.141597, E = 2.718282 } +enum( ®double® ) Math { PI_2 = 1.570796, PI = 3.141597, E = 2.718282 } // pointer -enum( ®char *® ) Name { Fred = "Fred", Mary = "Mary", Jane = "Jane" }; +enum( ®char *® ) Name { Fred = "Fred", Mary = "Mary", Jane = "Jane" }; int i, j, k; enum( ®int *® ) ptr { I = &i, J = &j, K = &k }; -enum( ®int &® ) ref { I = i, J = j, K = k }; +enum( ®int &® ) ref { I = i, J = j, K = k }; // tuple enum( ®[int, int]® ) { T = [ 1, 2 ] }; @@ -2361,5 +2361,5 @@ \begin{cfa} enum( char * ) Name2 { ®inline Name®, Jack = "Jack", Jill = "Jill" }; -enum ®/* inferred */® Name3 { ®inline Name2®, Sue = "Sue", Tom = "Tom" }; +enum ®/* inferred */® Name3 { ®inline Name2®, Sue = "Sue", Tom = "Tom" }; \end{cfa} Enumeration ©Name2© inherits all the enums and their values from enumeration ©Name© by containment, and a ©Name© enumeration is a subtype of enumeration ©Name2©. @@ -3818,7 +3818,7 @@ "[ output-file (default stdout) ] ]"; } // choose - } catch( ®Open_Failure® * ex; ex->istream == &in ) { + } catch( ®open_failure® * ex; ex->istream == &in ) { $\C{// input file errors}$ ®exit® | "Unable to open input file" | argv[1]; - } catch( ®Open_Failure® * ex; ex->ostream == &out ) { + } catch( ®open_failure® * ex; ex->ostream == &out ) { $\C{// output file errors}$ ®close®( in ); $\C{// optional}$ ®exit® | "Unable to open output file" | argv[2]; @@ -4038,5 +4038,5 @@ \item -\Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} toggle printing the separator. +\Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} globally toggle printing the separator. \begin{cfa}[belowskip=0pt] sout | sepDisable | 1 | 2 | 3; $\C{// turn off implicit separator}$ @@ -4053,5 +4053,5 @@ \item -\Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} toggle printing the separator with respect to the next printed item, and then return to the global separator setting. +\Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} locally toggle printing the separator with respect to the next printed item, and then return to the global separator setting. \begin{cfa}[belowskip=0pt] sout | 1 | sepOff | 2 | 3; $\C{// turn off implicit separator for the next item}$ @@ -4129,5 +4129,5 @@ 6 \end{cfa} -Note, a terminating ©nl© is merged (overrides) with the implicit newline at the end of the ©sout© expression, otherwise it is impossible to to print a single newline +Note, a terminating ©nl© is merged (overrides) with the implicit newline at the end of the ©sout© expression, otherwise it is impossible to print a single newline \item \Indexc{nlOn}\index{manipulator!nlOn@©nlOn©} implicitly prints a newline at the end of each output expression. Index: driver/cc1.cc =================================================================== --- driver/cc1.cc (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ driver/cc1.cc (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Fri Aug 26 14:23:51 2005 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 17 18:04:23 2022 -// Update Count : 422 +// Last Modified On : Fri Jun 9 11:36:44 2023 +// Update Count : 423 // @@ -385,5 +385,6 @@ // strip inappropriate flags with an argument - } else if ( arg == "-auxbase" || arg == "-auxbase-strip" || arg == "-dumpbase" || arg == "-dumpdir" ) { + } else if ( arg == "-auxbase" || arg == "-auxbase-strip" || + arg == "-dumpbase" || arg == "-dumpbase-ext" || arg == "-dumpdir" ) { i += 1; #ifdef __DEBUG_H__ Index: libcfa/src/concurrency/atomic.hfa =================================================================== --- libcfa/src/concurrency/atomic.hfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/concurrency/atomic.hfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,22 +10,42 @@ // Created On : Thu May 25 15:22:46 2023 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu May 25 15:24:45 2023 -// Update Count : 1 +// Last Modified On : Fri Jun 9 13:36:47 2023 +// Update Count : 46 // -#define LOAD( lock ) (__atomic_load_n( &(lock), __ATOMIC_SEQ_CST )) -#define LOADM( lock, memorder ) (__atomic_load_n( &(lock), memorder )) -#define STORE( lock, assn ) (__atomic_store_n( &(lock), assn, __ATOMIC_SEQ_CST )) -#define STOREM( lock, assn, memorder ) (__atomic_store_n( &(lock), assn, memorder )) -#define CLR( lock ) (__atomic_clear( &(lock), __ATOMIC_RELEASE )) -#define CLRM( lock, memorder ) (__atomic_clear( &(lock), memorder )) -#define TAS( lock ) (__atomic_test_and_set( &(lock), __ATOMIC_ACQUIRE )) -#define TASM( lock, memorder ) (__atomic_test_and_set( &(lock), memorder )) -#define CAS( change, comp, assn ) ({typeof(comp) __temp = (comp); __atomic_compare_exchange_n( &(change), &(__temp), (assn), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ); }) -#define CASM( change, comp, assn, memorder... ) ({typeof(comp) * __temp = &(comp); __atomic_compare_exchange_n( &(change), &(__temp), (assn), false, memorder, memorder ); }) -#define CASV( change, comp, assn ) (__atomic_compare_exchange_n( &(change), &(comp), (assn), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST )) -#define CASVM( change, comp, assn, memorder... ) (__atomic_compare_exchange_n( &(change), &(comp), (assn), false, memorder, memorder )) -#define FAS( change, assn ) (__atomic_exchange_n( &(change), (assn), __ATOMIC_SEQ_CST )) -#define FASM( change, assn, memorder ) (__atomic_exchange_n( &(change), (assn), memorder )) -#define FAI( change, Inc ) (__atomic_fetch_add( &(change), (Inc), __ATOMIC_SEQ_CST )) -#define FAIM( change, Inc, memorder ) (__atomic_fetch_add( &(change), (Inc), memorder )) +#define LOAD( val ) (LOADM( val, __ATOMIC_SEQ_CST)) +#define LOADM( val, memorder ) (__atomic_load_n( &(val), memorder)) + +#define STORE( val, assn ) (STOREM( val, assn, __ATOMIC_SEQ_CST)) +#define STOREM( val, assn, memorder ) (__atomic_store_n( &(val), assn, memorder)) + +#define TAS( lock ) (TASM( lock, __ATOMIC_ACQUIRE)) +#define TASM( lock, memorder ) (__atomic_test_and_set( &(lock), memorder)) + +#define TASCLR( lock ) (TASCLRM( lock, __ATOMIC_RELEASE)) +#define TASCLRM( lock, memorder ) (__atomic_clear( &(lock), memorder)) + +#define FAS( assn, replace ) (FASM(assn, replace, __ATOMIC_SEQ_CST)) +#define FASM( assn, replace, memorder ) (__atomic_exchange_n( &(assn), (replace), memorder)) + +#define FAI( assn, Inc ) (__atomic_fetch_add( &(assn), (Inc), __ATOMIC_SEQ_CST)) +#define FAIM( assn, Inc, memorder ) (__atomic_fetch_add( &(assn), (Inc), memorder)) + +// Use __sync because __atomic with 128-bit CAA can result in calls to pthread_mutex_lock. + +// #define CAS( assn, comp, replace ) (CASM( assn, comp, replace, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) +// #define CASM( assn, comp, replace, memorder... ) ({ \ +// typeof(comp) __temp = (comp); \ +// __atomic_compare_exchange_n( &(assn), &(__temp), (replace), false, memorder ); \ +// }) +#define CAS( assn, comp, replace ) (__sync_bool_compare_and_swap( &assn, comp, replace)) +#define CASM( assn, comp, replace, memorder... ) _Static_assert( false, "memory order unsupported for CAS macro" ); + +// #define CASV( assn, comp, replace ) (__atomic_compare_exchange_n( &(assn), &(comp), (replace), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST )) +// #define CASVM( assn, comp, replace, memorder... ) (__atomic_compare_exchange_n( &(assn), &(comp), (replace), false, memorder, memorder )) +#define CASV( assn, comp, replace ) ({ \ + typeof(comp) temp = comp; \ + typeof(comp) old = __sync_val_compare_and_swap( &(assn), (comp), (replace) ); \ + old == temp ? true : (comp = old, false); \ +}) +#define CASVM( assn, comp, replace, memorder... ) _Static_assert( false, "memory order unsupported for CASV macro" ); Index: libcfa/src/containers/lockfree.hfa =================================================================== --- libcfa/src/containers/lockfree.hfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/containers/lockfree.hfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -199,9 +199,12 @@ forall( T & ) +struct LinkData { + T * volatile top; // pointer to stack top + uintptr_t count; // count each push +}; + +forall( T & ) union Link { - struct { // 32/64-bit x 2 - T * volatile top; // pointer to stack top - uintptr_t count; // count each push - }; + LinkData(T) data; #if __SIZEOF_INT128__ == 16 __int128 // gcc, 128-bit integer @@ -220,10 +223,10 @@ void ?{}( StackLF(T) & this ) with(this) { stack.atom = 0; } - T * top( StackLF(T) & this ) with(this) { return stack.top; } + T * top( StackLF(T) & this ) with(this) { return stack.data.top; } void push( StackLF(T) & this, T & n ) with(this) { *( &n )`next = stack; // atomic assignment unnecessary, or use CAA for () { // busy wait - if ( __atomic_compare_exchange_n( &stack.atom, &( &n )`next->atom, (Link(T))@{ {&n, ( &n )`next->count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node + if ( __atomic_compare_exchange_n( &stack.atom, &( &n )`next->atom, (Link(T))@{ (LinkData(T))@{ &n, ( &n )`next->data.count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node } // for } // push @@ -232,6 +235,7 @@ Link(T) t @= stack; // atomic assignment unnecessary, or use CAA for () { // busy wait - if ( t.top == 0p ) return 0p; // empty stack ? - if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ {( t.top )`next->top, t.count} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.top; // attempt to update top node + if ( t.data.top == 0p ) return 0p; // empty stack ? + Link(T) * next = ( t.data.top )`next; + if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ (LinkData(T))@{ next->data.top, t.data.count } }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.data.top; // attempt to update top node } // for } // pop @@ -239,11 +243,13 @@ bool unsafe_remove( StackLF(T) & this, T * node ) with(this) { Link(T) * link = &stack; - for() { - T * next = link->top; - if( next == node ) { - link->top = ( node )`next->top; + for () { + // TODO: Avoiding some problems with double fields access. + LinkData(T) * data = &link->data; + T * next = (T *)&(*data).top; + if ( next == node ) { + data->top = ( node )`next->data.top; return true; } - if( next == 0p ) return false; + if ( next == 0p ) return false; link = ( next )`next; } Index: libcfa/src/fstream.cfa =================================================================== --- libcfa/src/fstream.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/fstream.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Apr 9 14:55:54 2022 -// Update Count : 515 +// Last Modified On : Mon Jun 5 22:00:23 2023 +// Update Count : 518 // @@ -117,5 +117,5 @@ } // for if ( file == 0p ) { - throw (Open_Failure){ os }; + throw (open_failure){ os }; // abort | IO_MSG "open output file \"" | name | "\"" | nl | strerror( errno ); } // if @@ -137,5 +137,5 @@ } // for if ( ret == EOF ) { - throw (Close_Failure){ os }; + throw (close_failure){ os }; // abort | IO_MSG "close output" | nl | strerror( errno ); } // if @@ -145,10 +145,10 @@ ofstream & write( ofstream & os, const char data[], size_t size ) { if ( fail( os ) ) { - throw (Write_Failure){ os }; + throw (write_failure){ os }; // abort | IO_MSG "attempt write I/O on failed stream"; } // if if ( fwrite( data, 1, size, (FILE *)(os.file$) ) != size ) { - throw (Write_Failure){ os }; + throw (write_failure){ os }; // abort | IO_MSG "write" | nl | strerror( errno ); } // if @@ -240,5 +240,5 @@ } // for if ( file == 0p ) { - throw (Open_Failure){ is }; + throw (open_failure){ is }; // abort | IO_MSG "open input file \"" | name | "\"" | nl | strerror( errno ); } // if @@ -260,5 +260,5 @@ } // for if ( ret == EOF ) { - throw (Close_Failure){ is }; + throw (close_failure){ is }; // abort | IO_MSG "close input" | nl | strerror( errno ); } // if @@ -268,10 +268,10 @@ ifstream & read( ifstream & is, char data[], size_t size ) { if ( fail( is ) ) { - throw (Read_Failure){ is }; + throw (read_failure){ is }; // abort | IO_MSG "attempt read I/O on failed stream"; } // if if ( fread( data, size, 1, (FILE *)(is.file$) ) == 0 ) { - throw (Read_Failure){ is }; + throw (read_failure){ is }; // abort | IO_MSG "read" | nl | strerror( errno ); } // if @@ -318,15 +318,15 @@ -static vtable(Open_Failure) Open_Failure_vt; +static vtable(open_failure) open_failure_vt; // exception I/O constructors -void ?{}( Open_Failure & ex, ofstream & ostream ) with(ex) { - virtual_table = &Open_Failure_vt; +void ?{}( open_failure & ex, ofstream & ostream ) with(ex) { + virtual_table = &open_failure_vt; ostream = &ostream; tag = 1; } // ?{} -void ?{}( Open_Failure & ex, ifstream & istream ) with(ex) { - virtual_table = &Open_Failure_vt; +void ?{}( open_failure & ex, ifstream & istream ) with(ex) { + virtual_table = &open_failure_vt; istream = &istream; tag = 0; @@ -334,15 +334,15 @@ -static vtable(Close_Failure) Close_Failure_vt; +static vtable(close_failure) close_failure_vt; // exception I/O constructors -void ?{}( Close_Failure & ex, ofstream & ostream ) with(ex) { - virtual_table = &Close_Failure_vt; +void ?{}( close_failure & ex, ofstream & ostream ) with(ex) { + virtual_table = &close_failure_vt; ostream = &ostream; tag = 1; } // ?{} -void ?{}( Close_Failure & ex, ifstream & istream ) with(ex) { - virtual_table = &Close_Failure_vt; +void ?{}( close_failure & ex, ifstream & istream ) with(ex) { + virtual_table = &close_failure_vt; istream = &istream; tag = 0; @@ -350,15 +350,15 @@ -static vtable(Write_Failure) Write_Failure_vt; +static vtable(write_failure) write_failure_vt; // exception I/O constructors -void ?{}( Write_Failure & ex, ofstream & ostream ) with(ex) { - virtual_table = &Write_Failure_vt; +void ?{}( write_failure & ex, ofstream & ostream ) with(ex) { + virtual_table = &write_failure_vt; ostream = &ostream; tag = 1; } // ?{} -void ?{}( Write_Failure & ex, ifstream & istream ) with(ex) { - virtual_table = &Write_Failure_vt; +void ?{}( write_failure & ex, ifstream & istream ) with(ex) { + virtual_table = &write_failure_vt; istream = &istream; tag = 0; @@ -366,25 +366,25 @@ -static vtable(Read_Failure) Read_Failure_vt; +static vtable(read_failure) read_failure_vt; // exception I/O constructors -void ?{}( Read_Failure & ex, ofstream & ostream ) with(ex) { - virtual_table = &Read_Failure_vt; +void ?{}( read_failure & ex, ofstream & ostream ) with(ex) { + virtual_table = &read_failure_vt; ostream = &ostream; tag = 1; } // ?{} -void ?{}( Read_Failure & ex, ifstream & istream ) with(ex) { - virtual_table = &Read_Failure_vt; +void ?{}( read_failure & ex, ifstream & istream ) with(ex) { + virtual_table = &read_failure_vt; istream = &istream; tag = 0; } // ?{} -// void throwOpen_Failure( ofstream & ostream ) { -// Open_Failure exc = { ostream }; +// void throwopen_failure( ofstream & ostream ) { +// open_failure exc = { ostream }; // } -// void throwOpen_Failure( ifstream & istream ) { -// Open_Failure exc = { istream }; +// void throwopen_failure( ifstream & istream ) { +// open_failure exc = { istream }; // } Index: libcfa/src/fstream.hfa =================================================================== --- libcfa/src/fstream.hfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/fstream.hfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Oct 10 09:37:32 2021 -// Update Count : 243 +// Last Modified On : Mon Jun 5 22:00:20 2023 +// Update Count : 246 // @@ -137,5 +137,5 @@ -exception Open_Failure { +exception open_failure { union { ofstream * ostream; @@ -146,8 +146,8 @@ }; -void ?{}( Open_Failure & this, ofstream & ); -void ?{}( Open_Failure & this, ifstream & ); +void ?{}( open_failure & this, ofstream & ); +void ?{}( open_failure & this, ifstream & ); -exception Close_Failure { +exception close_failure { union { ofstream * ostream; @@ -158,8 +158,8 @@ }; -void ?{}( Close_Failure & this, ofstream & ); -void ?{}( Close_Failure & this, ifstream & ); +void ?{}( close_failure & this, ofstream & ); +void ?{}( close_failure & this, ifstream & ); -exception Write_Failure { +exception write_failure { union { ofstream * ostream; @@ -170,8 +170,8 @@ }; -void ?{}( Write_Failure & this, ofstream & ); -void ?{}( Write_Failure & this, ifstream & ); +void ?{}( write_failure & this, ofstream & ); +void ?{}( write_failure & this, ifstream & ); -exception Read_Failure { +exception read_failure { union { ofstream * ostream; @@ -182,6 +182,6 @@ }; -void ?{}( Read_Failure & this, ofstream & ); -void ?{}( Read_Failure & this, ifstream & ); +void ?{}( read_failure & this, ofstream & ); +void ?{}( read_failure & this, ifstream & ); // Local Variables: // Index: libcfa/src/math.trait.hfa =================================================================== --- libcfa/src/math.trait.hfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/math.trait.hfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Fri Jul 16 15:40:52 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 2 11:36:56 2023 -// Update Count : 20 +// Last Modified On : Tue Jun 6 07:59:17 2023 +// Update Count : 24 // @@ -17,25 +17,25 @@ forall( U ) -trait Not { +trait not { void ?{}( U &, zero_t ); int !?( U ); -}; // Not +}; // not -forall( T | Not( T ) ) -trait Equality { +forall( T | not( T ) ) +trait equality { int ?==?( T, T ); int ?!=?( T, T ); -}; // Equality +}; // equality -forall( U | Equality( U ) ) -trait Relational { +forall( U | equality( U ) ) +trait relational { int ??( U, U ); int ?>=?( U, U ); -}; // Relational +}; // relational forall ( T ) -trait Signed { +trait Signed { // must be capitalized, conflict with keyword signed T +?( T ); T -?( T ); @@ -44,13 +44,13 @@ forall( U | Signed( U ) ) -trait Additive { +trait additive { U ?+?( U, U ); U ?-?( U, U ); U ?+=?( U &, U ); U ?-=?( U &, U ); -}; // Additive +}; // additive -forall( T | Additive( T ) ) -trait Incdec { +forall( T | additive( T ) ) +trait inc_dec { void ?{}( T &, one_t ); // T ?++( T & ); @@ -58,17 +58,17 @@ // T ?--( T & ); // T --?( T & ); -}; // Incdec +}; // inc_dec -forall( U | Incdec( U ) ) -trait Multiplicative { +forall( U | inc_dec( U ) ) +trait multiplicative { U ?*?( U, U ); U ?/?( U, U ); U ?%?( U, U ); U ?/=?( U &, U ); -}; // Multiplicative +}; // multiplicative -forall( T | Relational( T ) | Multiplicative( T ) ) -trait Arithmetic { -}; // Arithmetic +forall( T | relational( T ) | multiplicative( T ) ) +trait arithmetic { +}; // arithmetic // Local Variables: // Index: libcfa/src/parseconfig.cfa =================================================================== --- libcfa/src/parseconfig.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/parseconfig.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -144,5 +144,5 @@ in | nl; // ignore remainder of line } // for - } catch( Open_Failure * ex; ex->istream == &in ) { + } catch( open_failure * ex; ex->istream == &in ) { delete( kv_pairs ); throw *ex; @@ -203,5 +203,5 @@ -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_nonnegative( & T value ) { T zero_val = 0; @@ -209,5 +209,5 @@ } -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_positive( & T value ) { T zero_val = 0; @@ -215,5 +215,5 @@ } -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_nonpositive( & T value ) { T zero_val = 0; @@ -221,5 +221,5 @@ } -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_negative( & T value ) { T zero_val = 0; Index: libcfa/src/parseconfig.hfa =================================================================== --- libcfa/src/parseconfig.hfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/parseconfig.hfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -107,14 +107,14 @@ -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_nonnegative( & T ); -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_positive( & T ); -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_nonpositive( & T ); -forall(T | Relational( T )) +forall(T | relational( T )) [ bool ] is_negative( & T ); Index: libcfa/src/rational.cfa =================================================================== --- libcfa/src/rational.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/rational.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Wed Apr 6 17:54:28 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Aug 25 18:09:58 2022 -// Update Count : 194 +// Last Modified On : Mon Jun 5 22:49:06 2023 +// Update Count : 196 // @@ -20,5 +20,5 @@ #pragma GCC visibility push(default) -forall( T | Arithmetic( T ) ) { +forall( T | arithmetic( T ) ) { // helper routines @@ -39,28 +39,28 @@ abort | "Invalid rational number construction: denominator cannot be equal to 0."; } // exit - if ( d < (T){0} ) { d = -d; n = -n; } // move sign to numerator + if ( d < (T){0} ) { d = -d; n = -n; } // move sign to numerator return gcd( abs( n ), d ); // simplify - } // Rationalnumber::simplify + } // simplify // constructors - void ?{}( Rational(T) & r, zero_t ) { + void ?{}( rational(T) & r, zero_t ) { r{ (T){0}, (T){1} }; } // rational - void ?{}( Rational(T) & r, one_t ) { + void ?{}( rational(T) & r, one_t ) { r{ (T){1}, (T){1} }; } // rational - void ?{}( Rational(T) & r ) { + void ?{}( rational(T) & r ) { r{ (T){0}, (T){1} }; } // rational - void ?{}( Rational(T) & r, T n ) { + void ?{}( rational(T) & r, T n ) { r{ n, (T){1} }; } // rational - void ?{}( Rational(T) & r, T n, T d ) { - T t = simplify( n, d ); // simplify + void ?{}( rational(T) & r, T n, T d ) { + T t = simplify( n, d ); // simplify r.[numerator, denominator] = [n / t, d / t]; } // rational @@ -68,13 +68,13 @@ // getter for numerator/denominator - T numerator( Rational(T) r ) { + T numerator( rational(T) r ) { return r.numerator; } // numerator - T denominator( Rational(T) r ) { + T denominator( rational(T) r ) { return r.denominator; } // denominator - [ T, T ] ?=?( & [ T, T ] dest, Rational(T) src ) { + [ T, T ] ?=?( & [ T, T ] dest, rational(T) src ) { return dest = src.[ numerator, denominator ]; } // ?=? @@ -82,14 +82,14 @@ // setter for numerator/denominator - T numerator( Rational(T) r, T n ) { + T numerator( rational(T) r, T n ) { T prev = r.numerator; - T t = gcd( abs( n ), r.denominator ); // simplify + T t = gcd( abs( n ), r.denominator ); // simplify r.[numerator, denominator] = [n / t, r.denominator / t]; return prev; } // numerator - T denominator( Rational(T) r, T d ) { + T denominator( rational(T) r, T d ) { T prev = r.denominator; - T t = simplify( r.numerator, d ); // simplify + T t = simplify( r.numerator, d ); // simplify r.[numerator, denominator] = [r.numerator / t, d / t]; return prev; @@ -98,29 +98,29 @@ // comparison - int ?==?( Rational(T) l, Rational(T) r ) { + int ?==?( rational(T) l, rational(T) r ) { return l.numerator * r.denominator == l.denominator * r.numerator; } // ?==? - int ?!=?( Rational(T) l, Rational(T) r ) { + int ?!=?( rational(T) l, rational(T) r ) { return ! ( l == r ); } // ?!=? - int ?!=?( Rational(T) l, zero_t ) { - return ! ( l == (Rational(T)){ 0 } ); + int ?!=?( rational(T) l, zero_t ) { + return ! ( l == (rational(T)){ 0 } ); } // ?!=? - int ??( Rational(T) l, Rational(T) r ) { + int ?>?( rational(T) l, rational(T) r ) { return ! ( l <= r ); } // ?>? - int ?>=?( Rational(T) l, Rational(T) r ) { + int ?>=?( rational(T) l, rational(T) r ) { return ! ( l < r ); } // ?>=? @@ -128,64 +128,64 @@ // arithmetic - Rational(T) +?( Rational(T) r ) { - return (Rational(T)){ r.numerator, r.denominator }; + rational(T) +?( rational(T) r ) { + return (rational(T)){ r.numerator, r.denominator }; } // +? - Rational(T) -?( Rational(T) r ) { - return (Rational(T)){ -r.numerator, r.denominator }; + rational(T) -?( rational(T) r ) { + return (rational(T)){ -r.numerator, r.denominator }; } // -? - Rational(T) ?+?( Rational(T) l, Rational(T) r ) { + rational(T) ?+?( rational(T) l, rational(T) r ) { if ( l.denominator == r.denominator ) { // special case - return (Rational(T)){ l.numerator + r.numerator, l.denominator }; + return (rational(T)){ l.numerator + r.numerator, l.denominator }; } else { - return (Rational(T)){ l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator }; + return (rational(T)){ l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator }; } // if } // ?+? - Rational(T) ?+=?( Rational(T) & l, Rational(T) r ) { + rational(T) ?+=?( rational(T) & l, rational(T) r ) { l = l + r; return l; } // ?+? - Rational(T) ?+=?( Rational(T) & l, one_t ) { - l = l + (Rational(T)){ 1 }; + rational(T) ?+=?( rational(T) & l, one_t ) { + l = l + (rational(T)){ 1 }; return l; } // ?+? - Rational(T) ?-?( Rational(T) l, Rational(T) r ) { + rational(T) ?-?( rational(T) l, rational(T) r ) { if ( l.denominator == r.denominator ) { // special case - return (Rational(T)){ l.numerator - r.numerator, l.denominator }; + return (rational(T)){ l.numerator - r.numerator, l.denominator }; } else { - return (Rational(T)){ l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator }; + return (rational(T)){ l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator }; } // if } // ?-? - Rational(T) ?-=?( Rational(T) & l, Rational(T) r ) { + rational(T) ?-=?( rational(T) & l, rational(T) r ) { l = l - r; return l; } // ?-? - Rational(T) ?-=?( Rational(T) & l, one_t ) { - l = l - (Rational(T)){ 1 }; + rational(T) ?-=?( rational(T) & l, one_t ) { + l = l - (rational(T)){ 1 }; return l; } // ?-? - Rational(T) ?*?( Rational(T) l, Rational(T) r ) { - return (Rational(T)){ l.numerator * r.numerator, l.denominator * r.denominator }; + rational(T) ?*?( rational(T) l, rational(T) r ) { + return (rational(T)){ l.numerator * r.numerator, l.denominator * r.denominator }; } // ?*? - Rational(T) ?*=?( Rational(T) & l, Rational(T) r ) { + rational(T) ?*=?( rational(T) & l, rational(T) r ) { return l = l * r; } // ?*? - Rational(T) ?/?( Rational(T) l, Rational(T) r ) { + rational(T) ?/?( rational(T) l, rational(T) r ) { if ( r.numerator < (T){0} ) { r.[numerator, denominator] = [-r.numerator, -r.denominator]; } // if - return (Rational(T)){ l.numerator * r.denominator, l.denominator * r.numerator }; + return (rational(T)){ l.numerator * r.denominator, l.denominator * r.numerator }; } // ?/? - Rational(T) ?/=?( Rational(T) & l, Rational(T) r ) { + rational(T) ?/=?( rational(T) & l, rational(T) r ) { return l = l / r; } // ?/? @@ -194,5 +194,5 @@ forall( istype & | istream( istype ) | { istype & ?|?( istype &, T & ); } ) - istype & ?|?( istype & is, Rational(T) & r ) { + istype & ?|?( istype & is, rational(T) & r ) { is | r.numerator | r.denominator; T t = simplify( r.numerator, r.denominator ); @@ -203,9 +203,9 @@ forall( ostype & | ostream( ostype ) | { ostype & ?|?( ostype &, T ); } ) { - ostype & ?|?( ostype & os, Rational(T) r ) { + ostype & ?|?( ostype & os, rational(T) r ) { return os | r.numerator | '/' | r.denominator; } // ?|? - void ?|?( ostype & os, Rational(T) r ) { + void ?|?( ostype & os, rational(T) r ) { (ostype &)(os | r); ends( os ); } // ?|? @@ -213,14 +213,14 @@ } // distribution -forall( T | Arithmetic( T ) | { T ?\?( T, unsigned long ); } ) { - Rational(T) ?\?( Rational(T) x, long int y ) { +forall( T | arithmetic( T ) | { T ?\?( T, unsigned long ); } ) { + rational(T) ?\?( rational(T) x, long int y ) { if ( y < 0 ) { - return (Rational(T)){ x.denominator \ -y, x.numerator \ -y }; + return (rational(T)){ x.denominator \ -y, x.numerator \ -y }; } else { - return (Rational(T)){ x.numerator \ y, x.denominator \ y }; + return (rational(T)){ x.numerator \ y, x.denominator \ y }; } // if } // ?\? - Rational(T) ?\=?( Rational(T) & x, long int y ) { + rational(T) ?\=?( rational(T) & x, long int y ) { return x = x \ y; } // ?\? @@ -229,14 +229,14 @@ // conversion -forall( T | Arithmetic( T ) | { double convert( T ); } ) -double widen( Rational(T) r ) { +forall( T | arithmetic( T ) | { double convert( T ); } ) +double widen( rational(T) r ) { return convert( r.numerator ) / convert( r.denominator ); } // widen -forall( T | Arithmetic( T ) | { double convert( T ); T convert( double ); } ) -Rational(T) narrow( double f, T md ) { +forall( T | arithmetic( T ) | { double convert( T ); T convert( double ); } ) +rational(T) narrow( double f, T md ) { // http://www.ics.uci.edu/~eppstein/numth/frap.c - if ( md <= (T){1} ) { // maximum fractional digits too small? - return (Rational(T)){ convert( f ), (T){1}}; // truncate fraction + if ( md <= (T){1} ) { // maximum fractional digits too small? + return (rational(T)){ convert( f ), (T){1}}; // truncate fraction } // if @@ -260,5 +260,5 @@ if ( f > (double)0x7FFFFFFF ) break; // representation failure } // for - return (Rational(T)){ m00, m10 }; + return (rational(T)){ m00, m10 }; } // narrow Index: libcfa/src/rational.hfa =================================================================== --- libcfa/src/rational.hfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ libcfa/src/rational.hfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -12,6 +12,6 @@ // Created On : Wed Apr 6 17:56:25 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Jul 20 17:45:29 2021 -// Update Count : 118 +// Last Modified On : Mon Jun 5 22:49:05 2023 +// Update Count : 119 // @@ -19,77 +19,77 @@ #include "iostream.hfa" -#include "math.trait.hfa" // Arithmetic +#include "math.trait.hfa" // arithmetic // implementation -forall( T | Arithmetic( T ) ) { - struct Rational { +forall( T | arithmetic( T ) ) { + struct rational { T numerator, denominator; // invariant: denominator > 0 - }; // Rational + }; // rational // constructors - void ?{}( Rational(T) & r ); - void ?{}( Rational(T) & r, zero_t ); - void ?{}( Rational(T) & r, one_t ); - void ?{}( Rational(T) & r, T n ); - void ?{}( Rational(T) & r, T n, T d ); + void ?{}( rational(T) & r ); + void ?{}( rational(T) & r, zero_t ); + void ?{}( rational(T) & r, one_t ); + void ?{}( rational(T) & r, T n ); + void ?{}( rational(T) & r, T n, T d ); // numerator/denominator getter - T numerator( Rational(T) r ); - T denominator( Rational(T) r ); - [ T, T ] ?=?( & [ T, T ] dest, Rational(T) src ); + T numerator( rational(T) r ); + T denominator( rational(T) r ); + [ T, T ] ?=?( & [ T, T ] dest, rational(T) src ); // numerator/denominator setter - T numerator( Rational(T) r, T n ); - T denominator( Rational(T) r, T d ); + T numerator( rational(T) r, T n ); + T denominator( rational(T) r, T d ); // comparison - int ?==?( Rational(T) l, Rational(T) r ); - int ?!=?( Rational(T) l, Rational(T) r ); - int ?!=?( Rational(T) l, zero_t ); // => ! - int ??( Rational(T) l, Rational(T) r ); - int ?>=?( Rational(T) l, Rational(T) r ); + int ?==?( rational(T) l, rational(T) r ); + int ?!=?( rational(T) l, rational(T) r ); + int ?!=?( rational(T) l, zero_t ); // => ! + int ??( rational(T) l, rational(T) r ); + int ?>=?( rational(T) l, rational(T) r ); // arithmetic - Rational(T) +?( Rational(T) r ); - Rational(T) -?( Rational(T) r ); - Rational(T) ?+?( Rational(T) l, Rational(T) r ); - Rational(T) ?+=?( Rational(T) & l, Rational(T) r ); - Rational(T) ?+=?( Rational(T) & l, one_t ); // => ++?, ?++ - Rational(T) ?-?( Rational(T) l, Rational(T) r ); - Rational(T) ?-=?( Rational(T) & l, Rational(T) r ); - Rational(T) ?-=?( Rational(T) & l, one_t ); // => --?, ?-- - Rational(T) ?*?( Rational(T) l, Rational(T) r ); - Rational(T) ?*=?( Rational(T) & l, Rational(T) r ); - Rational(T) ?/?( Rational(T) l, Rational(T) r ); - Rational(T) ?/=?( Rational(T) & l, Rational(T) r ); + rational(T) +?( rational(T) r ); + rational(T) -?( rational(T) r ); + rational(T) ?+?( rational(T) l, rational(T) r ); + rational(T) ?+=?( rational(T) & l, rational(T) r ); + rational(T) ?+=?( rational(T) & l, one_t ); // => ++?, ?++ + rational(T) ?-?( rational(T) l, rational(T) r ); + rational(T) ?-=?( rational(T) & l, rational(T) r ); + rational(T) ?-=?( rational(T) & l, one_t ); // => --?, ?-- + rational(T) ?*?( rational(T) l, rational(T) r ); + rational(T) ?*=?( rational(T) & l, rational(T) r ); + rational(T) ?/?( rational(T) l, rational(T) r ); + rational(T) ?/=?( rational(T) & l, rational(T) r ); // I/O forall( istype & | istream( istype ) | { istype & ?|?( istype &, T & ); } ) - istype & ?|?( istype &, Rational(T) & ); + istype & ?|?( istype &, rational(T) & ); forall( ostype & | ostream( ostype ) | { ostype & ?|?( ostype &, T ); } ) { - ostype & ?|?( ostype &, Rational(T) ); - void ?|?( ostype &, Rational(T) ); + ostype & ?|?( ostype &, rational(T) ); + void ?|?( ostype &, rational(T) ); } // distribution } // distribution -forall( T | Arithmetic( T ) | { T ?\?( T, unsigned long ); } ) { - Rational(T) ?\?( Rational(T) x, long int y ); - Rational(T) ?\=?( Rational(T) & x, long int y ); +forall( T | arithmetic( T ) | { T ?\?( T, unsigned long ); } ) { + rational(T) ?\?( rational(T) x, long int y ); + rational(T) ?\=?( rational(T) & x, long int y ); } // distribution // conversion -forall( T | Arithmetic( T ) | { double convert( T ); } ) -double widen( Rational(T) r ); -forall( T | Arithmetic( T ) | { double convert( T ); T convert( double );} ) -Rational(T) narrow( double f, T md ); +forall( T | arithmetic( T ) | { double convert( T ); } ) +double widen( rational(T) r ); +forall( T | arithmetic( T ) | { double convert( T ); T convert( double );} ) +rational(T) narrow( double f, T md ); // Local Variables: // Index: src/AST/DeclReplacer.hpp =================================================================== --- src/AST/DeclReplacer.hpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/AST/DeclReplacer.hpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -18,21 +18,26 @@ #include -#include "Node.hpp" +namespace ast { + class DeclWithType; + class Expr; + class Node; + class TypeDecl; +} namespace ast { - class DeclWithType; - class TypeDecl; - class Expr; - namespace DeclReplacer { - using DeclMap = std::unordered_map< const DeclWithType *, const DeclWithType * >; - using TypeMap = std::unordered_map< const TypeDecl *, const TypeDecl * >; - using ExprMap = std::unordered_map< const DeclWithType *, const Expr * >; +namespace DeclReplacer { - const Node * replace( const Node * node, const DeclMap & declMap, bool debug = false ); - const Node * replace( const Node * node, const TypeMap & typeMap, bool debug = false ); - const Node * replace( const Node * node, const DeclMap & declMap, const TypeMap & typeMap, bool debug = false ); - const Node * replace( const Node * node, const ExprMap & exprMap); - } +using DeclMap = std::unordered_map< const DeclWithType *, const DeclWithType * >; +using TypeMap = std::unordered_map< const TypeDecl *, const TypeDecl * >; +using ExprMap = std::unordered_map< const DeclWithType *, const Expr * >; + +const Node * replace( const Node * node, const DeclMap & declMap, bool debug = false ); +const Node * replace( const Node * node, const TypeMap & typeMap, bool debug = false ); +const Node * replace( const Node * node, const DeclMap & declMap, const TypeMap & typeMap, bool debug = false ); +const Node * replace( const Node * node, const ExprMap & exprMap); + +} + } Index: src/AST/Pass.hpp =================================================================== --- src/AST/Pass.hpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/AST/Pass.hpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -414,7 +414,22 @@ }; -/// Use when the templated visitor should update the symbol table +/// Use when the templated visitor should update the symbol table, +/// that is, when your pass core needs to query the symbol table. +/// Expected setups: +/// - For master passes that kick off at the compilation unit +/// - before resolver: extend WithSymbolTableX +/// - after resolver: extend WithSymbolTable and use defaults +/// - (FYI, for completeness, the resolver's main pass uses ValidateOnAdd when it kicks off) +/// - For helper passes that kick off at arbitrary points in the AST: +/// - take an existing symbol table as a parameter, extend WithSymbolTable, +/// and construct with WithSymbolTable(const SymbolTable &) struct WithSymbolTable { - SymbolTable symtab; + WithSymbolTable(const ast::SymbolTable & from) : symtab(from) {} + WithSymbolTable(ast::SymbolTable::ErrorDetection errorMode = ast::SymbolTable::ErrorDetection::AssertClean) : symtab(errorMode) {} + ast::SymbolTable symtab; +}; +template +struct WithSymbolTableX : WithSymbolTable { + WithSymbolTableX() : WithSymbolTable(errorMode) {} }; Index: src/AST/Pass.impl.hpp =================================================================== --- src/AST/Pass.impl.hpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/AST/Pass.impl.hpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -72,5 +72,5 @@ template class container_t> static inline void take_all( it_t it, container_t> * decls, bool * mutated = nullptr ) { - if(empty(decls)) return; + if ( empty( decls ) ) return; std::transform(decls->begin(), decls->end(), it, [](const ast::Decl * decl) -> auto { @@ -78,14 +78,14 @@ }); decls->clear(); - if(mutated) *mutated = true; + if ( mutated ) *mutated = true; } template class container_t> static inline void take_all( it_t it, container_t> * stmts, bool * mutated = nullptr ) { - if(empty(stmts)) return; + if ( empty( stmts ) ) return; std::move(stmts->begin(), stmts->end(), it); stmts->clear(); - if(mutated) *mutated = true; + if ( mutated ) *mutated = true; } @@ -93,5 +93,5 @@ /// Check if should be skipped, different for pointers and containers template - bool skip( const ast::ptr & val) { + bool skip( const ast::ptr & val ) { return !val; } @@ -110,5 +110,5 @@ template - const node_t & get( const node_t & val, long) { + const node_t & get( const node_t & val, long ) { return val; } @@ -126,286 +126,282 @@ } } - - template< typename core_t > - template< typename node_t > - auto ast::Pass< core_t >::call_accept( const node_t * node ) - -> typename ast::Pass< core_t >::template generic_call_accept_result::type - { - __pedantic_pass_assert( __visit_children() ); - __pedantic_pass_assert( node ); - - static_assert( !std::is_base_of::value, "ERROR"); - static_assert( !std::is_base_of::value, "ERROR"); - - auto nval = node->accept( *this ); - __pass::result1< - typename std::remove_pointer< decltype( node->accept(*this) ) >::type - > res; - res.differs = nval != node; - res.value = nval; - return res; - } - - template< typename core_t > - __pass::template result1 ast::Pass< core_t >::call_accept( const ast::Expr * expr ) { - __pedantic_pass_assert( __visit_children() ); - __pedantic_pass_assert( expr ); - - auto nval = expr->accept( *this ); - return { nval != expr, nval }; - } - - template< typename core_t > - __pass::template result1 ast::Pass< core_t >::call_accept( const ast::Stmt * stmt ) { - __pedantic_pass_assert( __visit_children() ); - __pedantic_pass_assert( stmt ); - - const ast::Stmt * nval = stmt->accept( *this ); - return { nval != stmt, nval }; - } - - template< typename core_t > - __pass::template result1 ast::Pass< core_t >::call_accept_top( const ast::Expr * expr ) { - __pedantic_pass_assert( __visit_children() ); - __pedantic_pass_assert( expr ); - - const ast::TypeSubstitution ** typeSubs_ptr = __pass::typeSubs( core, 0 ); - if ( typeSubs_ptr && expr->env ) { - *typeSubs_ptr = expr->env; - } - - auto nval = expr->accept( *this ); - return { nval != expr, nval }; - } - - template< typename core_t > - __pass::template result1 ast::Pass< core_t >::call_accept_as_compound( const ast::Stmt * stmt ) { - __pedantic_pass_assert( __visit_children() ); - __pedantic_pass_assert( stmt ); - - // add a few useful symbols to the scope - using __pass::empty; - - // get the stmts/decls that will need to be spliced in - auto stmts_before = __pass::stmtsToAddBefore( core, 0 ); - auto stmts_after = __pass::stmtsToAddAfter ( core, 0 ); - auto decls_before = __pass::declsToAddBefore( core, 0 ); - auto decls_after = __pass::declsToAddAfter ( core, 0 ); - - // These may be modified by subnode but most be restored once we exit this statemnet. - ValueGuardPtr< const ast::TypeSubstitution * > __old_env ( __pass::typeSubs( core, 0 ) ); - ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before ); - ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after ); - ValueGuardPtr< typename std::remove_pointer< decltype(decls_before) >::type > __old_stmts_before( decls_before ); - ValueGuardPtr< typename std::remove_pointer< decltype(decls_after ) >::type > __old_stmts_after ( decls_after ); - - // Now is the time to actually visit the node - const ast::Stmt * nstmt = stmt->accept( *this ); - - // If the pass doesn't want to add anything then we are done - if( empty(stmts_before) && empty(stmts_after) && empty(decls_before) && empty(decls_after) ) { - return { nstmt != stmt, nstmt }; - } - - // Make sure that it is either adding statements or declartions but not both - // this is because otherwise the order would be awkward to predict - assert(( empty( stmts_before ) && empty( stmts_after )) - || ( empty( decls_before ) && empty( decls_after )) ); - - // Create a new Compound Statement to hold the new decls/stmts - ast::CompoundStmt * compound = new ast::CompoundStmt( stmt->location ); - - // Take all the declarations that go before - __pass::take_all( std::back_inserter( compound->kids ), decls_before ); - __pass::take_all( std::back_inserter( compound->kids ), stmts_before ); - - // Insert the original declaration - compound->kids.emplace_back( nstmt ); - - // Insert all the declarations that go before - __pass::take_all( std::back_inserter( compound->kids ), decls_after ); - __pass::take_all( std::back_inserter( compound->kids ), stmts_after ); - - return {true, compound}; - } - - template< typename core_t > - template< template class container_t > - __pass::template resultNstmt ast::Pass< core_t >::call_accept( const container_t< ptr > & statements ) { - __pedantic_pass_assert( __visit_children() ); - if( statements.empty() ) return {}; - - // We are going to aggregate errors for all these statements - SemanticErrorException errors; - - // add a few useful symbols to the scope - using __pass::empty; - - // get the stmts/decls that will need to be spliced in - auto stmts_before = __pass::stmtsToAddBefore( core, 0 ); - auto stmts_after = __pass::stmtsToAddAfter ( core, 0 ); - auto decls_before = __pass::declsToAddBefore( core, 0 ); - auto decls_after = __pass::declsToAddAfter ( core, 0 ); - - // These may be modified by subnode but most be restored once we exit this statemnet. - ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before ); - ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after ); - ValueGuardPtr< typename std::remove_pointer< decltype(decls_before) >::type > __old_stmts_before( decls_before ); - ValueGuardPtr< typename std::remove_pointer< decltype(decls_after ) >::type > __old_stmts_after ( decls_after ); - - // update pass statitistics - pass_visitor_stats.depth++; - pass_visitor_stats.max->push(pass_visitor_stats.depth); - pass_visitor_stats.avg->push(pass_visitor_stats.depth); - - __pass::resultNstmt new_kids; - for( auto value : enumerate( statements ) ) { - try { - size_t i = value.idx; - const Stmt * stmt = value.val; - __pedantic_pass_assert( stmt ); - const ast::Stmt * new_stmt = stmt->accept( *this ); - assert( new_stmt ); - if(new_stmt != stmt ) { new_kids.differs = true; } - - // Make sure that it is either adding statements or declartions but not both - // this is because otherwise the order would be awkward to predict - assert(( empty( stmts_before ) && empty( stmts_after )) - || ( empty( decls_before ) && empty( decls_after )) ); - - // Take all the statements which should have gone after, N/A for first iteration - new_kids.take_all( decls_before ); - new_kids.take_all( stmts_before ); - - // Now add the statement if there is one - if(new_stmt != stmt) { - new_kids.values.emplace_back( new_stmt, i, false ); - } else { - new_kids.values.emplace_back( nullptr, i, true ); - } - - // Take all the declarations that go before - new_kids.take_all( decls_after ); - new_kids.take_all( stmts_after ); +} + +template< typename core_t > +template< typename node_t > +auto ast::Pass< core_t >::call_accept( const node_t * node ) -> + typename ast::Pass< core_t >::template generic_call_accept_result::type +{ + __pedantic_pass_assert( __visit_children() ); + __pedantic_pass_assert( node ); + + static_assert( !std::is_base_of::value, "ERROR" ); + static_assert( !std::is_base_of::value, "ERROR" ); + + auto nval = node->accept( *this ); + __pass::result1< + typename std::remove_pointer< decltype( node->accept(*this) ) >::type + > res; + res.differs = nval != node; + res.value = nval; + return res; +} + +template< typename core_t > +ast::__pass::template result1 ast::Pass< core_t >::call_accept( const ast::Expr * expr ) { + __pedantic_pass_assert( __visit_children() ); + __pedantic_pass_assert( expr ); + + auto nval = expr->accept( *this ); + return { nval != expr, nval }; +} + +template< typename core_t > +ast::__pass::template result1 ast::Pass< core_t >::call_accept( const ast::Stmt * stmt ) { + __pedantic_pass_assert( __visit_children() ); + __pedantic_pass_assert( stmt ); + + const ast::Stmt * nval = stmt->accept( *this ); + return { nval != stmt, nval }; +} + +template< typename core_t > +ast::__pass::template result1 ast::Pass< core_t >::call_accept_top( const ast::Expr * expr ) { + __pedantic_pass_assert( __visit_children() ); + __pedantic_pass_assert( expr ); + + const ast::TypeSubstitution ** typeSubs_ptr = __pass::typeSubs( core, 0 ); + if ( typeSubs_ptr && expr->env ) { + *typeSubs_ptr = expr->env; + } + + auto nval = expr->accept( *this ); + return { nval != expr, nval }; +} + +template< typename core_t > +ast::__pass::template result1 ast::Pass< core_t >::call_accept_as_compound( const ast::Stmt * stmt ) { + __pedantic_pass_assert( __visit_children() ); + __pedantic_pass_assert( stmt ); + + // add a few useful symbols to the scope + using __pass::empty; + + // get the stmts/decls that will need to be spliced in + auto stmts_before = __pass::stmtsToAddBefore( core, 0 ); + auto stmts_after = __pass::stmtsToAddAfter ( core, 0 ); + auto decls_before = __pass::declsToAddBefore( core, 0 ); + auto decls_after = __pass::declsToAddAfter ( core, 0 ); + + // These may be modified by subnode but most be restored once we exit this statemnet. + ValueGuardPtr< const ast::TypeSubstitution * > __old_env ( __pass::typeSubs( core, 0 ) ); + ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before ); + ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after ); + ValueGuardPtr< typename std::remove_pointer< decltype(decls_before) >::type > __old_stmts_before( decls_before ); + ValueGuardPtr< typename std::remove_pointer< decltype(decls_after ) >::type > __old_stmts_after ( decls_after ); + + // Now is the time to actually visit the node + const ast::Stmt * nstmt = stmt->accept( *this ); + + // If the pass doesn't want to add anything then we are done + if ( empty(stmts_before) && empty(stmts_after) && empty(decls_before) && empty(decls_after) ) { + return { nstmt != stmt, nstmt }; + } + + // Make sure that it is either adding statements or declartions but not both + // this is because otherwise the order would be awkward to predict + assert(( empty( stmts_before ) && empty( stmts_after )) + || ( empty( decls_before ) && empty( decls_after )) ); + + // Create a new Compound Statement to hold the new decls/stmts + ast::CompoundStmt * compound = new ast::CompoundStmt( stmt->location ); + + // Take all the declarations that go before + __pass::take_all( std::back_inserter( compound->kids ), decls_before ); + __pass::take_all( std::back_inserter( compound->kids ), stmts_before ); + + // Insert the original declaration + compound->kids.emplace_back( nstmt ); + + // Insert all the declarations that go before + __pass::take_all( std::back_inserter( compound->kids ), decls_after ); + __pass::take_all( std::back_inserter( compound->kids ), stmts_after ); + + return { true, compound }; +} + +template< typename core_t > +template< template class container_t > +ast::__pass::template resultNstmt ast::Pass< core_t >::call_accept( const container_t< ptr > & statements ) { + __pedantic_pass_assert( __visit_children() ); + if ( statements.empty() ) return {}; + + // We are going to aggregate errors for all these statements + SemanticErrorException errors; + + // add a few useful symbols to the scope + using __pass::empty; + + // get the stmts/decls that will need to be spliced in + auto stmts_before = __pass::stmtsToAddBefore( core, 0 ); + auto stmts_after = __pass::stmtsToAddAfter ( core, 0 ); + auto decls_before = __pass::declsToAddBefore( core, 0 ); + auto decls_after = __pass::declsToAddAfter ( core, 0 ); + + // These may be modified by subnode but most be restored once we exit this statemnet. + ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before ); + ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after ); + ValueGuardPtr< typename std::remove_pointer< decltype(decls_before) >::type > __old_stmts_before( decls_before ); + ValueGuardPtr< typename std::remove_pointer< decltype(decls_after ) >::type > __old_stmts_after ( decls_after ); + + // update pass statitistics + pass_visitor_stats.depth++; + pass_visitor_stats.max->push(pass_visitor_stats.depth); + pass_visitor_stats.avg->push(pass_visitor_stats.depth); + + __pass::resultNstmt new_kids; + for ( auto value : enumerate( statements ) ) { + try { + size_t i = value.idx; + const Stmt * stmt = value.val; + __pedantic_pass_assert( stmt ); + const ast::Stmt * new_stmt = stmt->accept( *this ); + assert( new_stmt ); + if ( new_stmt != stmt ) { new_kids.differs = true; } + + // Make sure that it is either adding statements or declartions but not both + // this is because otherwise the order would be awkward to predict + assert(( empty( stmts_before ) && empty( stmts_after )) + || ( empty( decls_before ) && empty( decls_after )) ); + + // Take all the statements which should have gone after, N/A for first iteration + new_kids.take_all( decls_before ); + new_kids.take_all( stmts_before ); + + // Now add the statement if there is one + if ( new_stmt != stmt ) { + new_kids.values.emplace_back( new_stmt, i, false ); + } else { + new_kids.values.emplace_back( nullptr, i, true ); } - catch ( SemanticErrorException &e ) { - errors.append( e ); + + // Take all the declarations that go before + new_kids.take_all( decls_after ); + new_kids.take_all( stmts_after ); + } catch ( SemanticErrorException &e ) { + errors.append( e ); + } + } + pass_visitor_stats.depth--; + if ( !errors.isEmpty() ) { throw errors; } + + return new_kids; +} + +template< typename core_t > +template< template class container_t, typename node_t > +ast::__pass::template resultN ast::Pass< core_t >::call_accept( const container_t< ast::ptr > & container ) { + __pedantic_pass_assert( __visit_children() ); + if ( container.empty() ) return {}; + SemanticErrorException errors; + + pass_visitor_stats.depth++; + pass_visitor_stats.max->push(pass_visitor_stats.depth); + pass_visitor_stats.avg->push(pass_visitor_stats.depth); + + bool mutated = false; + container_t> new_kids; + for ( const node_t * node : container ) { + try { + __pedantic_pass_assert( node ); + const node_t * new_stmt = strict_dynamic_cast< const node_t * >( node->accept( *this ) ); + if ( new_stmt != node ) { + mutated = true; + new_kids.emplace_back( new_stmt ); + } else { + new_kids.emplace_back( nullptr ); } - } - pass_visitor_stats.depth--; - if ( !errors.isEmpty() ) { throw errors; } - - return new_kids; - } - - template< typename core_t > - template< template class container_t, typename node_t > - __pass::template resultN ast::Pass< core_t >::call_accept( const container_t< ast::ptr > & container ) { - __pedantic_pass_assert( __visit_children() ); - if( container.empty() ) return {}; - SemanticErrorException errors; - - pass_visitor_stats.depth++; - pass_visitor_stats.max->push(pass_visitor_stats.depth); - pass_visitor_stats.avg->push(pass_visitor_stats.depth); - - bool mutated = false; - container_t> new_kids; - for ( const node_t * node : container ) { - try { - __pedantic_pass_assert( node ); - const node_t * new_stmt = strict_dynamic_cast< const node_t * >( node->accept( *this ) ); - if(new_stmt != node ) { - mutated = true; - new_kids.emplace_back( new_stmt ); - } else { - new_kids.emplace_back( nullptr ); - } - - } - catch( SemanticErrorException &e ) { - errors.append( e ); - } - } - - __pedantic_pass_assert( new_kids.size() == container.size() ); - pass_visitor_stats.depth--; - if ( ! errors.isEmpty() ) { throw errors; } - - return ast::__pass::resultN{ mutated, new_kids }; - } - - template< typename core_t > - template - void ast::Pass< core_t >::maybe_accept( - const node_t * & parent, - field_t super_t::*field - ) { - static_assert( std::is_base_of::value, "Error deducing member object" ); - - if(__pass::skip(parent->*field)) return; - const auto & old_val = __pass::get(parent->*field, 0); - - static_assert( !std::is_same::value, "ERROR"); - - auto new_val = call_accept( old_val ); - - static_assert( !std::is_same::value /* || std::is_same::value */, "ERROR"); - - if( new_val.differs ) { - auto new_parent = __pass::mutate(parent); - new_val.apply(new_parent, field); - parent = new_parent; - } - } - - template< typename core_t > - template - void ast::Pass< core_t >::maybe_accept_top( - const node_t * & parent, - field_t super_t::*field - ) { - static_assert( std::is_base_of::value, "Error deducing member object" ); - - if(__pass::skip(parent->*field)) return; - const auto & old_val = __pass::get(parent->*field, 0); - - static_assert( !std::is_same::value, "ERROR"); - - auto new_val = call_accept_top( old_val ); - - static_assert( !std::is_same::value /* || std::is_same::value */, "ERROR"); - - if( new_val.differs ) { - auto new_parent = __pass::mutate(parent); - new_val.apply(new_parent, field); - parent = new_parent; - } - } - - template< typename core_t > - template - void ast::Pass< core_t >::maybe_accept_as_compound( - const node_t * & parent, - field_t super_t::*child - ) { - static_assert( std::is_base_of::value, "Error deducing member object" ); - - if(__pass::skip(parent->*child)) return; - const auto & old_val = __pass::get(parent->*child, 0); - - static_assert( !std::is_same::value, "ERROR"); - - auto new_val = call_accept_as_compound( old_val ); - - static_assert( !std::is_same::value || std::is_same::value, "ERROR"); - - if( new_val.differs ) { - auto new_parent = __pass::mutate(parent); - new_val.apply( new_parent, child ); - parent = new_parent; - } - } - + } catch ( SemanticErrorException &e ) { + errors.append( e ); + } + } + + __pedantic_pass_assert( new_kids.size() == container.size() ); + pass_visitor_stats.depth--; + if ( !errors.isEmpty() ) { throw errors; } + + return ast::__pass::resultN{ mutated, new_kids }; +} + +template< typename core_t > +template +void ast::Pass< core_t >::maybe_accept( + const node_t * & parent, + field_t super_t::*field +) { + static_assert( std::is_base_of::value, "Error deducing member object" ); + + if ( __pass::skip( parent->*field ) ) return; + const auto & old_val = __pass::get(parent->*field, 0); + + static_assert( !std::is_same::value, "ERROR" ); + + auto new_val = call_accept( old_val ); + + static_assert( !std::is_same::value /* || std::is_same::value */, "ERROR" ); + + if ( new_val.differs ) { + auto new_parent = __pass::mutate(parent); + new_val.apply(new_parent, field); + parent = new_parent; + } +} + +template< typename core_t > +template +void ast::Pass< core_t >::maybe_accept_top( + const node_t * & parent, + field_t super_t::*field +) { + static_assert( std::is_base_of::value, "Error deducing member object" ); + + if ( __pass::skip( parent->*field ) ) return; + const auto & old_val = __pass::get(parent->*field, 0); + + static_assert( !std::is_same::value, "ERROR" ); + + auto new_val = call_accept_top( old_val ); + + static_assert( !std::is_same::value /* || std::is_same::value */, "ERROR" ); + + if ( new_val.differs ) { + auto new_parent = __pass::mutate(parent); + new_val.apply(new_parent, field); + parent = new_parent; + } +} + +template< typename core_t > +template +void ast::Pass< core_t >::maybe_accept_as_compound( + const node_t * & parent, + field_t super_t::*child +) { + static_assert( std::is_base_of::value, "Error deducing member object" ); + + if ( __pass::skip( parent->*child ) ) return; + const auto & old_val = __pass::get(parent->*child, 0); + + static_assert( !std::is_same::value, "ERROR" ); + + auto new_val = call_accept_as_compound( old_val ); + + static_assert( !std::is_same::value || std::is_same::value, "ERROR" ); + + if ( new_val.differs ) { + auto new_parent = __pass::mutate(parent); + new_val.apply( new_parent, child ); + parent = new_parent; + } } @@ -761,18 +757,16 @@ if ( __visit_children() ) { - // Do not enter (or leave) a new scope if atFunctionTop. Remember to save the result. - auto guard1 = makeFuncGuard( [this, enterScope = !this->atFunctionTop]() { - if ( enterScope ) { - __pass::symtab::enter(core, 0); - } - }, [this, leaveScope = !this->atFunctionTop]() { - if ( leaveScope ) { - __pass::symtab::leave(core, 0); - } - }); - ValueGuard< bool > guard2( atFunctionTop ); - atFunctionTop = false; - guard_scope guard3 { *this }; - maybe_accept( node, &CompoundStmt::kids ); + // Do not enter (or leave) a new symbol table scope if atFunctionTop. + // But always enter (and leave) a new general scope. + if ( atFunctionTop ) { + ValueGuard< bool > guard1( atFunctionTop ); + atFunctionTop = false; + guard_scope guard2( *this ); + maybe_accept( node, &CompoundStmt::kids ); + } else { + guard_symtab guard1( *this ); + guard_scope guard2( *this ); + maybe_accept( node, &CompoundStmt::kids ); + } } Index: src/AST/SymbolTable.cpp =================================================================== --- src/AST/SymbolTable.cpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/AST/SymbolTable.cpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -88,9 +88,17 @@ } -SymbolTable::SymbolTable() +SymbolTable::SymbolTable( ErrorDetection errorMode ) : idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable(), - prevScope(), scope( 0 ), repScope( 0 ) { ++*stats().count; } + prevScope(), scope( 0 ), repScope( 0 ), errorMode(errorMode) { ++*stats().count; } SymbolTable::~SymbolTable() { stats().size->push( idTable ? idTable->size() : 0 ); } + +void SymbolTable::OnFindError( CodeLocation location, std::string error ) const { + assertf( errorMode != AssertClean, "Name collision/redefinition, found during a compilation phase where none should be possible. Detail: %s", error.c_str() ); + if (errorMode == ValidateOnAdd) { + SemanticError(location, error); + } + assertf( errorMode == IgnoreErrors, "Unrecognized symbol-table error mode %d", errorMode ); +} void SymbolTable::enterScope() { @@ -269,31 +277,29 @@ } -namespace { - /// true if redeclaration conflict between two types - bool addedTypeConflicts( const NamedTypeDecl * existing, const NamedTypeDecl * added ) { - if ( existing->base == nullptr ) { - return false; - } else if ( added->base == nullptr ) { - return true; - } else { - // typedef redeclarations are errors only if types are different - if ( ! ResolvExpr::typesCompatible( existing->base, added->base ) ) { - SemanticError( added->location, "redeclaration of " + added->name ); - } - } - // does not need to be added to the table if both existing and added have a base that are - // the same +bool SymbolTable::addedTypeConflicts( + const NamedTypeDecl * existing, const NamedTypeDecl * added ) const { + if ( existing->base == nullptr ) { + return false; + } else if ( added->base == nullptr ) { return true; - } - - /// true if redeclaration conflict between two aggregate declarations - bool addedDeclConflicts( const AggregateDecl * existing, const AggregateDecl * added ) { - if ( ! existing->body ) { - return false; - } else if ( added->body ) { - SemanticError( added, "redeclaration of " ); - } - return true; - } + } else { + // typedef redeclarations are errors only if types are different + if ( ! ResolvExpr::typesCompatible( existing->base, added->base ) ) { + OnFindError( added->location, "redeclaration of " + added->name ); + } + } + // does not need to be added to the table if both existing and added have a base that are + // the same + return true; +} + +bool SymbolTable::addedDeclConflicts( + const AggregateDecl * existing, const AggregateDecl * added ) const { + if ( ! existing->body ) { + return false; + } else if ( added->body ) { + OnFindError( added, "redeclaration of " ); + } + return true; } @@ -648,10 +654,10 @@ if ( deleter && ! existing.deleter ) { if ( handleConflicts.mode == OnConflict::Error ) { - SemanticError( added, "deletion of defined identifier " ); + OnFindError( added, "deletion of defined identifier " ); } return true; } else if ( ! deleter && existing.deleter ) { if ( handleConflicts.mode == OnConflict::Error ) { - SemanticError( added, "definition of deleted identifier " ); + OnFindError( added, "definition of deleted identifier " ); } return true; @@ -661,5 +667,5 @@ if ( isDefinition( added ) && isDefinition( existing.id ) ) { if ( handleConflicts.mode == OnConflict::Error ) { - SemanticError( added, + OnFindError( added, isFunction( added ) ? "duplicate function definition for " : @@ -670,5 +676,5 @@ } else { if ( handleConflicts.mode == OnConflict::Error ) { - SemanticError( added, "duplicate definition for " ); + OnFindError( added, "duplicate definition for " ); } return true; @@ -722,5 +728,5 @@ // Check that a Cforall declaration doesn't override any C declaration if ( hasCompatibleCDecl( name, mangleName ) ) { - SemanticError( decl, "Cforall declaration hides C function " ); + OnFindError( decl, "Cforall declaration hides C function " ); } } else { @@ -728,5 +734,5 @@ // type-compatibility, which it may not be. if ( hasIncompatibleCDecl( name, mangleName ) ) { - SemanticError( decl, "conflicting overload of C function " ); + OnFindError( decl, "conflicting overload of C function " ); } } Index: src/AST/SymbolTable.hpp =================================================================== --- src/AST/SymbolTable.hpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/AST/SymbolTable.hpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -93,6 +93,23 @@ public: - SymbolTable(); + + /// Mode to control when (during which pass) user-caused name-declaration errors get reported. + /// The default setting `AssertClean` supports, "I expect all user-caused errors to have been + /// reported by now," or, "I wouldn't know what to do with an error; are there even any here?" + enum ErrorDetection { + AssertClean, ///< invalid user decls => assert fails during addFoo (default) + ValidateOnAdd, ///< invalid user decls => calls SemanticError during addFoo + IgnoreErrors ///< acts as if unspecified decls were removed, forcing validity + }; + + explicit SymbolTable( + ErrorDetection ///< mode for the lifetime of the symbol table (whole pass) + ); + SymbolTable() : SymbolTable(AssertClean) {} ~SymbolTable(); + + ErrorDetection getErrorMode() const { + return errorMode; + } // when using an indexer manually (e.g., within a mutator traversal), it is necessary to @@ -158,4 +175,16 @@ private: + void OnFindError( CodeLocation location, std::string error ) const; + + template< typename T > + void OnFindError( const T * obj, const std::string & error ) const { + OnFindError( obj->location, toString( error, obj ) ); + } + + template< typename T > + void OnFindError( CodeLocation location, const T * obj, const std::string & error ) const { + OnFindError( location, toString( error, obj ) ); + } + /// Ensures that a proper backtracking scope exists before a mutation void lazyInitScope(); @@ -168,8 +197,17 @@ bool removeSpecialOverrides( IdData & decl, MangleTable::Ptr & mangleTable ); - /// Options for handling identifier conflicts + /// Error detection mode given at construction (pass-specific). + /// Logically const, except that the symbol table's push-pop is achieved by autogenerated + /// assignment onto self. The feield is left motuable to keep this code-gen simple. + /// Conceptual constness is preserved by all SymbolTable in a stack sharing the same mode. + ErrorDetection errorMode; + + /// Options for handling identifier conflicts. + /// Varies according to AST location during traversal: captures semantics of the construct + /// being visited as "would shadow" vs "must not collide." + /// At a given AST location, is the same for every pass. struct OnConflict { enum { - Error, ///< Throw a semantic error + Error, ///< Follow the current pass's ErrorDetection mode (may throw a semantic error) Delete ///< Delete the earlier version with the delete statement } mode; @@ -191,4 +229,10 @@ const Decl * deleter ); + /// true if redeclaration conflict between two types + bool addedTypeConflicts( const NamedTypeDecl * existing, const NamedTypeDecl * added ) const; + + /// true if redeclaration conflict between two aggregate declarations + bool addedDeclConflicts( const AggregateDecl * existing, const AggregateDecl * added ) const; + /// common code for addId, addDeletedId, etc. void addIdCommon( @@ -213,4 +257,5 @@ } + // Local Variables: // // tab-width: 4 // Index: src/AST/Util.cpp =================================================================== --- src/AST/Util.cpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/AST/Util.cpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -83,4 +83,23 @@ } +/// Check that the MemberExpr has an aggregate type and matching member. +void memberMatchesAggregate( const MemberExpr * expr ) { + const Type * aggrType = expr->aggregate->result->stripReferences(); + const AggregateDecl * decl = nullptr; + if ( auto inst = dynamic_cast( aggrType ) ) { + decl = inst->base; + } else if ( auto inst = dynamic_cast( aggrType ) ) { + decl = inst->base; + } + assertf( decl, "Aggregate of member not correct type." ); + + for ( auto aggrMember : decl->members ) { + if ( expr->member == aggrMember ) { + return; + } + } + assertf( false, "Member not found." ); +} + struct InvariantCore { // To save on the number of visits: this is a kind of composed core. @@ -108,4 +127,9 @@ } + void previsit( const MemberExpr * node ) { + previsit( (const ParseNode *)node ); + memberMatchesAggregate( node ); + } + void postvisit( const Node * node ) { no_strong_cycles.postvisit( node ); Index: src/Parser/lex.ll =================================================================== --- src/Parser/lex.ll (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/Parser/lex.ll (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ * Created On : Sat Sep 22 08:58:10 2001 * Last Modified By : Peter A. Buhr - * Last Modified On : Tue May 2 08:45:21 2023 - * Update Count : 769 + * Last Modified On : Fri Jun 9 10:04:00 2023 + * Update Count : 770 */ @@ -319,4 +319,5 @@ static { KEYWORD_RETURN(STATIC); } _Static_assert { KEYWORD_RETURN(STATICASSERT); } // C11 +_static_assert { KEYWORD_RETURN(STATICASSERT); } // C23 struct { KEYWORD_RETURN(STRUCT); } suspend { KEYWORD_RETURN(SUSPEND); } // CFA Index: src/Parser/parser.yy =================================================================== --- src/Parser/parser.yy (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/Parser/parser.yy (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Sat Sep 1 20:22:55 2001 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Apr 26 16:45:37 2023 -// Update Count : 6330 +// Last Modified On : Wed Jun 7 14:32:28 2023 +// Update Count : 6341 // @@ -108,9 +108,9 @@ assert( declList ); // printf( "distAttr1 typeSpec %p\n", typeSpec ); typeSpec->print( std::cout ); - DeclarationNode * cur = declList, * cl = (new DeclarationNode)->addType( typeSpec ); + DeclarationNode * cl = (new DeclarationNode)->addType( typeSpec ); // printf( "distAttr2 cl %p\n", cl ); cl->type->print( std::cout ); // cl->type->aggregate.name = cl->type->aggInst.aggregate->aggregate.name; - for ( cur = dynamic_cast( cur->get_next() ); cur != nullptr; cur = dynamic_cast( cur->get_next() ) ) { + for ( DeclarationNode * cur = dynamic_cast( declList->get_next() ); cur != nullptr; cur = dynamic_cast( cur->get_next() ) ) { cl->cloneBaseType( cur ); } // for @@ -206,7 +206,7 @@ #define NEW_ONE new ExpressionNode( build_constantInteger( yylloc, *new string( "1" ) ) ) #define UPDOWN( compop, left, right ) (compop == OperKinds::LThan || compop == OperKinds::LEThan ? left : right) -#define MISSING_ANON_FIELD "Missing loop fields with an anonymous loop index is meaningless as loop index is unavailable in loop body." -#define MISSING_LOW "Missing low value for up-to range so index is uninitialized." -#define MISSING_HIGH "Missing high value for down-to range so index is uninitialized." +#define MISSING_ANON_FIELD "syntax error, missing loop fields with an anonymous loop index is meaningless as loop index is unavailable in loop body." +#define MISSING_LOW "syntax error, missing low value for up-to range so index is uninitialized." +#define MISSING_HIGH "syntax error, missing high value for down-to range so index is uninitialized." static ForCtrl * makeForCtrl( @@ -232,8 +232,8 @@ ForCtrl * forCtrl( const CodeLocation & location, DeclarationNode * index, ExpressionNode * start, enum OperKinds compop, ExpressionNode * comp, ExpressionNode * inc ) { if ( index->initializer ) { - SemanticError( yylloc, "Direct initialization disallowed. Use instead: type var; initialization ~ comparison ~ increment." ); + SemanticError( yylloc, "syntax error, direct initialization disallowed. Use instead: type var; initialization ~ comparison ~ increment." ); } // if if ( index->next ) { - SemanticError( yylloc, "Multiple loop indexes disallowed in for-loop declaration." ); + SemanticError( yylloc, "syntax error, multiple loop indexes disallowed in for-loop declaration." ); } // if DeclarationNode * initDecl = index->addInitializer( new InitializerNode( start ) ); @@ -260,18 +260,18 @@ return forCtrl( location, type, new string( identifier->name ), start, compop, comp, inc ); } else { - SemanticError( yylloc, "Expression disallowed. Only loop-index name allowed." ); return nullptr; + SemanticError( yylloc, "syntax error, loop-index name missing. Expression disallowed." ); return nullptr; } // if } else { - SemanticError( yylloc, "Expression disallowed. Only loop-index name allowed." ); return nullptr; + SemanticError( yylloc, "syntax error, loop-index name missing. Expression disallowed. ." ); return nullptr; } // if } // forCtrl static void IdentifierBeforeIdentifier( string & identifier1, string & identifier2, const char * kind ) { - SemanticError( yylloc, ::toString( "Adjacent identifiers \"", identifier1, "\" and \"", identifier2, "\" are not meaningful in a", kind, ".\n" + SemanticError( yylloc, ::toString( "syntax error, adjacent identifiers \"", identifier1, "\" and \"", identifier2, "\" are not meaningful in a", kind, ".\n" "Possible cause is misspelled type name or missing generic parameter." ) ); } // IdentifierBeforeIdentifier static void IdentifierBeforeType( string & identifier, const char * kind ) { - SemanticError( yylloc, ::toString( "Identifier \"", identifier, "\" cannot appear before a ", kind, ".\n" + SemanticError( yylloc, ::toString( "syntax error, identifier \"", identifier, "\" cannot appear before a ", kind, ".\n" "Possible cause is misspelled storage/CV qualifier, misspelled typename, or missing generic parameter." ) ); } // IdentifierBeforeType @@ -689,15 +689,15 @@ // | RESUME '(' comma_expression ')' compound_statement // { SemanticError( yylloc, "Resume expression is currently unimplemented." ); $$ = nullptr; } - | IDENTIFIER IDENTIFIER // syntax error + | IDENTIFIER IDENTIFIER // invalid syntax rules { IdentifierBeforeIdentifier( *$1.str, *$2.str, "n expression" ); $$ = nullptr; } - | IDENTIFIER type_qualifier // syntax error + | IDENTIFIER type_qualifier // invalid syntax rules { IdentifierBeforeType( *$1.str, "type qualifier" ); $$ = nullptr; } - | IDENTIFIER storage_class // syntax error + | IDENTIFIER storage_class // invalid syntax rules { IdentifierBeforeType( *$1.str, "storage class" ); $$ = nullptr; } - | IDENTIFIER basic_type_name // syntax error + | IDENTIFIER basic_type_name // invalid syntax rules { IdentifierBeforeType( *$1.str, "type" ); $$ = nullptr; } - | IDENTIFIER TYPEDEFname // syntax error + | IDENTIFIER TYPEDEFname // invalid syntax rules { IdentifierBeforeType( *$1.str, "type" ); $$ = nullptr; } - | IDENTIFIER TYPEGENname // syntax error + | IDENTIFIER TYPEGENname // invalid syntax rules { IdentifierBeforeType( *$1.str, "type" ); $$ = nullptr; } ; @@ -1152,7 +1152,7 @@ identifier_or_type_name ':' attribute_list_opt statement { $$ = $4->add_label( yylloc, $1, $3 ); } - | identifier_or_type_name ':' attribute_list_opt error // syntax error - { - SemanticError( yylloc, ::toString( "Label \"", *$1.str, "\" must be associated with a statement, " + | identifier_or_type_name ':' attribute_list_opt error // invalid syntax rule + { + SemanticError( yylloc, ::toString( "syntx error, label \"", *$1.str, "\" must be associated with a statement, " "where a declaration, case, or default is not a statement. " "Move the label or terminate with a semi-colon." ) ); @@ -1193,6 +1193,6 @@ | statement_list_nodecl statement { assert( $1 ); $1->set_last( $2 ); $$ = $1; } - | statement_list_nodecl error // syntax error - { SemanticError( yylloc, "Declarations only allowed at the start of the switch body, i.e., after the '{'." ); $$ = nullptr; } + | statement_list_nodecl error // invalid syntax rule + { SemanticError( yylloc, "syntax error, declarations only allowed at the start of the switch body, i.e., after the '{'." ); $$ = nullptr; } ; @@ -1219,6 +1219,6 @@ $$ = $7 ? new StatementNode( build_compound( yylloc, (StatementNode *)((new StatementNode( $7 ))->set_last( sw )) ) ) : sw; } - | SWITCH '(' comma_expression ')' '{' error '}' // CFA, syntax error - { SemanticError( yylloc, "Only declarations can appear before the list of case clauses." ); $$ = nullptr; } + | SWITCH '(' comma_expression ')' '{' error '}' // CFA, invalid syntax rule error + { SemanticError( yylloc, "synatx error, declarations can only appear before the list of case clauses." ); $$ = nullptr; } | CHOOSE '(' comma_expression ')' case_clause // CFA { $$ = new StatementNode( build_switch( yylloc, false, $3, $5 ) ); } @@ -1228,6 +1228,6 @@ $$ = $7 ? new StatementNode( build_compound( yylloc, (StatementNode *)((new StatementNode( $7 ))->set_last( sw )) ) ) : sw; } - | CHOOSE '(' comma_expression ')' '{' error '}' // CFA, syntax error - { SemanticError( yylloc, "Only declarations can appear before the list of case clauses." ); $$ = nullptr; } + | CHOOSE '(' comma_expression ')' '{' error '}' // CFA, invalid syntax rule + { SemanticError( yylloc, "syntax error, declarations can only appear before the list of case clauses." ); $$ = nullptr; } ; @@ -1268,13 +1268,13 @@ case_label: // CFA - CASE error // syntax error - { SemanticError( yylloc, "Missing case list after case." ); $$ = nullptr; } + CASE error // invalid syntax rule + { SemanticError( yylloc, "syntax error, case list missing after case." ); $$ = nullptr; } | CASE case_value_list ':' { $$ = $2; } - | CASE case_value_list error // syntax error - { SemanticError( yylloc, "Missing colon after case list." ); $$ = nullptr; } + | CASE case_value_list error // invalid syntax rule + { SemanticError( yylloc, "syntax error, colon missing after case list." ); $$ = nullptr; } | DEFAULT ':' { $$ = new ClauseNode( build_default( yylloc ) ); } // A semantic check is required to ensure only one default clause per switch/choose statement. - | DEFAULT error // syntax error - { SemanticError( yylloc, "Missing colon after default." ); $$ = nullptr; } + | DEFAULT error // invalid syntax rules + { SemanticError( yylloc, "syntax error, colon missing after default." ); $$ = nullptr; } ; @@ -1405,13 +1405,13 @@ else { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } } - | comma_expression updowneq comma_expression '~' '@' // CFA, error + | comma_expression updowneq comma_expression '~' '@' // CFA, invalid syntax rules { SemanticError( yylloc, MISSING_ANON_FIELD ); $$ = nullptr; } - | '@' updowneq '@' // CFA, error + | '@' updowneq '@' // CFA, invalid syntax rules { SemanticError( yylloc, MISSING_ANON_FIELD ); $$ = nullptr; } - | '@' updowneq comma_expression '~' '@' // CFA, error + | '@' updowneq comma_expression '~' '@' // CFA, invalid syntax rules { SemanticError( yylloc, MISSING_ANON_FIELD ); $$ = nullptr; } - | comma_expression updowneq '@' '~' '@' // CFA, error + | comma_expression updowneq '@' '~' '@' // CFA, invalid syntax rules { SemanticError( yylloc, MISSING_ANON_FIELD ); $$ = nullptr; } - | '@' updowneq '@' '~' '@' // CFA, error + | '@' updowneq '@' '~' '@' // CFA, invalid syntax rules { SemanticError( yylloc, MISSING_ANON_FIELD ); $$ = nullptr; } @@ -1431,13 +1431,13 @@ { if ( $4 == OperKinds::GThan || $4 == OperKinds::GEThan ) { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } - else if ( $4 == OperKinds::LEThan ) { SemanticError( yylloc, "Equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } + else if ( $4 == OperKinds::LEThan ) { SemanticError( yylloc, "syntax error, equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } else $$ = forCtrl( yylloc, $3, $1, $3->clone(), $4, nullptr, NEW_ONE ); } - | comma_expression ';' '@' updowneq '@' // CFA, error - { SemanticError( yylloc, "Missing low/high value for up/down-to range so index is uninitialized." ); $$ = nullptr; } + | comma_expression ';' '@' updowneq '@' // CFA, invalid syntax rules + { SemanticError( yylloc, "syntax error, missing low/high value for up/down-to range so index is uninitialized." ); $$ = nullptr; } | comma_expression ';' comma_expression updowneq comma_expression '~' comma_expression // CFA { $$ = forCtrl( yylloc, $3, $1, UPDOWN( $4, $3->clone(), $5 ), $4, UPDOWN( $4, $5->clone(), $3->clone() ), $7 ); } - | comma_expression ';' '@' updowneq comma_expression '~' comma_expression // CFA, error + | comma_expression ';' '@' updowneq comma_expression '~' comma_expression // CFA, invalid syntax rules { if ( $4 == OperKinds::LThan || $4 == OperKinds::LEThan ) { SemanticError( yylloc, MISSING_LOW ); $$ = nullptr; } @@ -1447,10 +1447,10 @@ { if ( $4 == OperKinds::GThan || $4 == OperKinds::GEThan ) { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } - else if ( $4 == OperKinds::LEThan ) { SemanticError( yylloc, "Equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } + else if ( $4 == OperKinds::LEThan ) { SemanticError( yylloc, "syntax error, equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } else $$ = forCtrl( yylloc, $3, $1, $3->clone(), $4, nullptr, $7 ); } | comma_expression ';' comma_expression updowneq comma_expression '~' '@' // CFA { $$ = forCtrl( yylloc, $3, $1, UPDOWN( $4, $3->clone(), $5 ), $4, UPDOWN( $4, $5->clone(), $3->clone() ), nullptr ); } - | comma_expression ';' '@' updowneq comma_expression '~' '@' // CFA, error + | comma_expression ';' '@' updowneq comma_expression '~' '@' // CFA, invalid syntax rules { if ( $4 == OperKinds::LThan || $4 == OperKinds::LEThan ) { SemanticError( yylloc, MISSING_LOW ); $$ = nullptr; } @@ -1460,9 +1460,9 @@ { if ( $4 == OperKinds::GThan || $4 == OperKinds::GEThan ) { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } - else if ( $4 == OperKinds::LEThan ) { SemanticError( yylloc, "Equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } + else if ( $4 == OperKinds::LEThan ) { SemanticError( yylloc, "syntax error, equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } else $$ = forCtrl( yylloc, $3, $1, $3->clone(), $4, nullptr, nullptr ); } | comma_expression ';' '@' updowneq '@' '~' '@' // CFA - { SemanticError( yylloc, "Missing low/high value for up/down-to range so index is uninitialized." ); $$ = nullptr; } + { SemanticError( yylloc, "syntax error, missing low/high value for up/down-to range so index is uninitialized." ); $$ = nullptr; } | declaration comma_expression // CFA @@ -1481,5 +1481,5 @@ { if ( $3 == OperKinds::GThan || $3 == OperKinds::GEThan ) { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } - else if ( $3 == OperKinds::LEThan ) { SemanticError( yylloc, "Equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } + else if ( $3 == OperKinds::LEThan ) { SemanticError( yylloc, "syntax error, equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } else $$ = forCtrl( yylloc, $1, $2, $3, nullptr, NEW_ONE ); } @@ -1495,5 +1495,5 @@ { if ( $3 == OperKinds::GThan || $3 == OperKinds::GEThan ) { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } - else if ( $3 == OperKinds::LEThan ) { SemanticError( yylloc, "Equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } + else if ( $3 == OperKinds::LEThan ) { SemanticError( yylloc, "syntax error, equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } else $$ = forCtrl( yylloc, $1, $2, $3, nullptr, $6 ); } @@ -1508,9 +1508,9 @@ { if ( $3 == OperKinds::GThan || $3 == OperKinds::GEThan ) { SemanticError( yylloc, MISSING_HIGH ); $$ = nullptr; } - else if ( $3 == OperKinds::LEThan ) { SemanticError( yylloc, "Equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } + else if ( $3 == OperKinds::LEThan ) { SemanticError( yylloc, "syntax error, equality with missing high value is meaningless. Use \"~\"." ); $$ = nullptr; } else $$ = forCtrl( yylloc, $1, $2, $3, nullptr, nullptr ); } - | declaration '@' updowneq '@' '~' '@' // CFA, error - { SemanticError( yylloc, "Missing low/high value for up/down-to range so index is uninitialized." ); $$ = nullptr; } + | declaration '@' updowneq '@' '~' '@' // CFA, invalid syntax rules + { SemanticError( yylloc, "syntax error, missing low/high value for up/down-to range so index is uninitialized." ); $$ = nullptr; } | comma_expression ';' TYPEDEFname // CFA, array type @@ -1521,5 +1521,7 @@ | comma_expression ';' downupdowneq TYPEDEFname // CFA, array type { - if ( $3 == OperKinds::LEThan || $3 == OperKinds::GEThan ) { SemanticError( yylloc, "All enumation ranges are equal (all values). Remove \"=~\"." ); $$ = nullptr; } + if ( $3 == OperKinds::LEThan || $3 == OperKinds::GEThan ) { + SemanticError( yylloc, "syntax error, all enumeration ranges are equal (all values). Remove \"=~\"." ); $$ = nullptr; + } SemanticError( yylloc, "Type iterator is currently unimplemented." ); $$ = nullptr; } @@ -1616,5 +1618,5 @@ MUTEX '(' argument_expression_list_opt ')' statement { - if ( ! $3 ) { SemanticError( yylloc, "mutex argument list cannot be empty." ); $$ = nullptr; } + if ( ! $3 ) { SemanticError( yylloc, "syntax error, mutex argument list cannot be empty." ); $$ = nullptr; } $$ = new StatementNode( build_mutex( yylloc, $3, $5 ) ); } @@ -1664,6 +1666,6 @@ { $$ = build_waitfor_timeout( yylloc, $1, $3, $4, maybe_build_compound( yylloc, $5 ) ); } // "else" must be conditional after timeout or timeout is never triggered (i.e., it is meaningless) - | wor_waitfor_clause wor when_clause_opt timeout statement wor ELSE statement // syntax error - { SemanticError( yylloc, "else clause must be conditional after timeout or timeout never triggered." ); $$ = nullptr; } + | wor_waitfor_clause wor when_clause_opt timeout statement wor ELSE statement // invalid syntax rules + { SemanticError( yylloc, "syntax error, else clause must be conditional after timeout or timeout never triggered." ); $$ = nullptr; } | wor_waitfor_clause wor when_clause_opt timeout statement wor when_clause ELSE statement { $$ = build_waitfor_else( yylloc, build_waitfor_timeout( yylloc, $1, $3, $4, maybe_build_compound( yylloc, $5 ) ), $7, maybe_build_compound( yylloc, $9 ) ); } @@ -1709,6 +1711,6 @@ { $$ = new ast::WaitUntilStmt::ClauseNode( ast::WaitUntilStmt::ClauseNode::Op::LEFT_OR, $1, build_waituntil_timeout( yylloc, $3, $4, maybe_build_compound( yylloc, $5 ) ) ); } // "else" must be conditional after timeout or timeout is never triggered (i.e., it is meaningless) - | wor_waituntil_clause wor when_clause_opt timeout statement wor ELSE statement // syntax error - { SemanticError( yylloc, "else clause must be conditional after timeout or timeout never triggered." ); $$ = nullptr; } + | wor_waituntil_clause wor when_clause_opt timeout statement wor ELSE statement // invalid syntax rules + { SemanticError( yylloc, "syntax error, else clause must be conditional after timeout or timeout never triggered." ); $$ = nullptr; } | wor_waituntil_clause wor when_clause_opt timeout statement wor when_clause ELSE statement { $$ = new ast::WaitUntilStmt::ClauseNode( ast::WaitUntilStmt::ClauseNode::Op::LEFT_OR, $1, @@ -2065,9 +2067,9 @@ assert( $1->type ); if ( $1->type->qualifiers.any() ) { // CV qualifiers ? - SemanticError( yylloc, "Useless type qualifier(s) in empty declaration." ); $$ = nullptr; + SemanticError( yylloc, "syntax error, useless type qualifier(s) in empty declaration." ); $$ = nullptr; } // enums are never empty declarations because there must have at least one enumeration. if ( $1->type->kind == TypeData::AggregateInst && $1->storageClasses.any() ) { // storage class ? - SemanticError( yylloc, "Useless storage qualifier(s) in empty aggregate declaration." ); $$ = nullptr; + SemanticError( yylloc, "syntax error, useless storage qualifier(s) in empty aggregate declaration." ); $$ = nullptr; } } @@ -2100,9 +2102,9 @@ | type_declaration_specifier | sue_declaration_specifier - | sue_declaration_specifier invalid_types - { - SemanticError( yylloc, ::toString( "Missing ';' after end of ", + | sue_declaration_specifier invalid_types // invalid syntax rule + { + SemanticError( yylloc, ::toString( "syntax error, expecting ';' at end of ", $1->type->enumeration.name ? "enum" : ast::AggregateDecl::aggrString( $1->type->aggregate.kind ), - " declaration" ) ); + " declaration." ) ); $$ = nullptr; } @@ -2584,4 +2586,9 @@ // } // for } + | type_specifier field_declaring_list_opt '}' // invalid syntax rule + { + SemanticError( yylloc, ::toString( "syntax error, expecting ';' at end of previous declaration." ) ); + $$ = nullptr; + } | EXTENSION type_specifier field_declaring_list_opt ';' // GCC { $$ = fieldDecl( $2, $3 ); distExt( $$ ); } @@ -2682,7 +2689,7 @@ | ENUM '(' cfa_abstract_parameter_declaration ')' attribute_list_opt '{' enumerator_list comma_opt '}' { - if ( $3->storageClasses.val != 0 || $3->type->qualifiers.any() ) - { SemanticError( yylloc, "storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); } - + if ( $3->storageClasses.val != 0 || $3->type->qualifiers.any() ) { + SemanticError( yylloc, "syntax error, storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); + } $$ = DeclarationNode::newEnum( nullptr, $7, true, true, $3 )->addQualifiers( $5 ); } @@ -2693,5 +2700,7 @@ | ENUM '(' cfa_abstract_parameter_declaration ')' attribute_list_opt identifier attribute_list_opt { - if ( $3->storageClasses.any() || $3->type->qualifiers.val != 0 ) { SemanticError( yylloc, "storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); } + if ( $3->storageClasses.any() || $3->type->qualifiers.val != 0 ) { + SemanticError( yylloc, "syntax error, storage-class and CV qualifiers are not meaningful for enumeration constants, which are const." ); + } typedefTable.makeTypedef( *$6 ); } @@ -3166,13 +3175,13 @@ | IDENTIFIER IDENTIFIER { IdentifierBeforeIdentifier( *$1.str, *$2.str, " declaration" ); $$ = nullptr; } - | IDENTIFIER type_qualifier // syntax error + | IDENTIFIER type_qualifier // invalid syntax rules { IdentifierBeforeType( *$1.str, "type qualifier" ); $$ = nullptr; } - | IDENTIFIER storage_class // syntax error + | IDENTIFIER storage_class // invalid syntax rules { IdentifierBeforeType( *$1.str, "storage class" ); $$ = nullptr; } - | IDENTIFIER basic_type_name // syntax error + | IDENTIFIER basic_type_name // invalid syntax rules { IdentifierBeforeType( *$1.str, "type" ); $$ = nullptr; } - | IDENTIFIER TYPEDEFname // syntax error + | IDENTIFIER TYPEDEFname // invalid syntax rules { IdentifierBeforeType( *$1.str, "type" ); $$ = nullptr; } - | IDENTIFIER TYPEGENname // syntax error + | IDENTIFIER TYPEGENname // invalid syntax rules { IdentifierBeforeType( *$1.str, "type" ); $$ = nullptr; } | external_function_definition @@ -3209,5 +3218,7 @@ | type_qualifier_list { - if ( $1->type->qualifiers.any() ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( $1->type->qualifiers.any() ) { + SemanticError( yylloc, "syntax error, CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); + } if ( $1->type->forall ) forall = true; // remember generic type } @@ -3220,5 +3231,7 @@ | declaration_qualifier_list { - if ( $1->type && $1->type->qualifiers.any() ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( $1->type && $1->type->qualifiers.any() ) { + SemanticError( yylloc, "syntax error, CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); + } if ( $1->type && $1->type->forall ) forall = true; // remember generic type } @@ -3231,5 +3244,7 @@ | declaration_qualifier_list type_qualifier_list { - if ( ($1->type && $1->type->qualifiers.any()) || ($2->type && $2->type->qualifiers.any()) ) { SemanticError( yylloc, "CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); } + if ( ($1->type && $1->type->qualifiers.any()) || ($2->type && $2->type->qualifiers.any()) ) { + SemanticError( yylloc, "syntax error, CV qualifiers cannot be distributed; only storage-class and forall qualifiers." ); + } if ( ($1->type && $1->type->forall) || ($2->type && $2->type->forall) ) forall = true; // remember generic type } @@ -3262,5 +3277,5 @@ $$ = $3; forall = false; if ( $5 ) { - SemanticError( yylloc, "Attributes cannot be associated with function body. Move attribute(s) before \"with\" clause." ); + SemanticError( yylloc, "syntax error, attributes cannot be associated with function body. Move attribute(s) before \"with\" clause." ); $$ = nullptr; } // if Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/ResolvExpr/CommonType.cc (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -1017,7 +1017,7 @@ void postvisit( const ast::TraitInstType * ) {} - void postvisit( const ast::TypeInstType * inst ) {} - - void postvisit( const ast::TupleType * tuple) { + void postvisit( const ast::TypeInstType * ) {} + + void postvisit( const ast::TupleType * tuple ) { tryResolveWithTypedEnum( tuple ); } Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/ResolvExpr/Resolver.cc (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -1106,5 +1106,5 @@ /// Removes cast to type of argument (unlike StripCasts, also handles non-generated casts) - void removeExtraneousCast( ast::ptr & expr, const ast::SymbolTable & symtab ) { + void removeExtraneousCast( ast::ptr & expr ) { if ( const ast::CastExpr * castExpr = expr.as< ast::CastExpr >() ) { if ( typesCompatible( castExpr->arg->result, castExpr->result ) ) { @@ -1196,5 +1196,5 @@ ast::ptr< ast::Expr > castExpr = new ast::CastExpr{ untyped, type }; ast::ptr< ast::Expr > newExpr = findSingleExpression( castExpr, context ); - removeExtraneousCast( newExpr, context.symtab ); + removeExtraneousCast( newExpr ); return newExpr; } @@ -1261,4 +1261,5 @@ static size_t traceId; Resolver_new( const ast::TranslationGlobal & global ) : + ast::WithSymbolTable(ast::SymbolTable::ErrorDetection::ValidateOnAdd), context{ symtab, global } {} Resolver_new( const ResolveContext & context ) : @@ -2040,5 +2041,5 @@ const ast::Type * initContext = currentObject.getCurrentType(); - removeExtraneousCast( newExpr, symtab ); + removeExtraneousCast( newExpr ); // check if actual object's type is char[] Index: src/Validate/HoistStruct.cpp =================================================================== --- src/Validate/HoistStruct.cpp (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ src/Validate/HoistStruct.cpp (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -18,6 +18,8 @@ #include +#include "AST/DeclReplacer.hpp" #include "AST/Pass.hpp" #include "AST/TranslationUnit.hpp" +#include "AST/Vector.hpp" namespace Validate { @@ -51,4 +53,6 @@ template AggrDecl const * postAggregate( AggrDecl const * ); + template + InstType const * preCollectionInstType( InstType const * type ); ast::AggregateDecl const * parent = nullptr; @@ -66,4 +70,22 @@ qualifiedName( decl, ss ); return ss.str(); +} + +void extendParams( ast::vector & dstParams, + ast::vector const & srcParams ) { + if ( srcParams.empty() ) return; + + ast::DeclReplacer::TypeMap newToOld; + ast::vector params; + for ( ast::ptr const & srcParam : srcParams ) { + ast::TypeDecl * dstParam = ast::deepCopy( srcParam.get() ); + dstParam->init = nullptr; + newToOld.emplace( srcParam, dstParam ); + for ( auto assertion : dstParam->assertions ) { + assertion = ast::DeclReplacer::replace( assertion, newToOld ); + } + params.emplace_back( dstParam ); + } + spliceBegin( dstParams, params ); } @@ -74,9 +96,9 @@ mut->parent = parent; mut->name = qualifiedName( mut ); - return mut; - } else { - GuardValue( parent ) = decl; - return decl; - } + extendParams( mut->params, parent->params ); + decl = mut; + } + GuardValue( parent ) = decl; + return decl; } @@ -112,4 +134,36 @@ } +ast::AggregateDecl const * commonParent( + ast::AggregateDecl const * lhs, ast::AggregateDecl const * rhs ) { + for ( auto outer = lhs ; outer ; outer = outer->parent ) { + for ( auto inner = rhs ; inner ; inner = inner->parent ) { + if ( outer == inner ) { + return outer; + } + } + } + return nullptr; +} + +template +InstType const * HoistStructCore::preCollectionInstType( InstType const * type ) { + if ( !type->base->parent ) return type; + if ( type->base->params.empty() ) return type; + + InstType * mut = ast::mutate( type ); + ast::AggregateDecl const * parent = + commonParent( this->parent, mut->base->parent ); + assert( parent ); + + std::vector> args; + for ( const ast::ptr & param : parent->params ) { + args.emplace_back( new ast::TypeExpr( param->location, + new ast::TypeInstType( param ) + ) ); + } + spliceBegin( mut->params, args ); + return mut; +} + template InstType const * preInstType( InstType const * type ) { @@ -121,9 +175,9 @@ ast::StructInstType const * HoistStructCore::previsit( ast::StructInstType const * type ) { - return preInstType( type ); + return preInstType( preCollectionInstType( type ) ); } ast::UnionInstType const * HoistStructCore::previsit( ast::UnionInstType const * type ) { - return preInstType( type ); + return preInstType( preCollectionInstType( type ) ); } Index: tests/.expect/copyfile.txt =================================================================== --- tests/.expect/copyfile.txt (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/.expect/copyfile.txt (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Fri Jun 19 13:44:05 2020 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Jun 19 17:58:03 2020 -// Update Count : 4 +// Last Modified On : Mon Jun 5 21:20:07 2023 +// Update Count : 5 // @@ -30,7 +30,7 @@ exit | "Usage" | argv[0] | "[ input-file (default stdin) [ output-file (default stdout) ] ]"; } // choose - } catch( Open_Failure * ex ; ex->istream == &in ) { + } catch( open_failure * ex ; ex->istream == &in ) { exit | "Unable to open input file" | argv[1]; - } catch( Open_Failure * ex ; ex->ostream == &out ) { + } catch( open_failure * ex ; ex->ostream == &out ) { close( in ); // optional exit | "Unable to open output file" | argv[2]; Index: tests/.in/copyfile.txt =================================================================== --- tests/.in/copyfile.txt (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/.in/copyfile.txt (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Fri Jun 19 13:44:05 2020 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Jun 19 17:58:03 2020 -// Update Count : 4 +// Last Modified On : Mon Jun 5 21:20:07 2023 +// Update Count : 5 // @@ -30,7 +30,7 @@ exit | "Usage" | argv[0] | "[ input-file (default stdin) [ output-file (default stdout) ] ]"; } // choose - } catch( Open_Failure * ex ; ex->istream == &in ) { + } catch( open_failure * ex ; ex->istream == &in ) { exit | "Unable to open input file" | argv[1]; - } catch( Open_Failure * ex ; ex->ostream == &out ) { + } catch( open_failure * ex ; ex->ostream == &out ) { close( in ); // optional exit | "Unable to open output file" | argv[2]; Index: tests/concurrency/lockfree_stack.cfa =================================================================== --- tests/concurrency/lockfree_stack.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/concurrency/lockfree_stack.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Thu May 25 15:36:50 2023 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue May 30 19:02:32 2023 -// Update Count : 18 +// Last Modified On : Fri Jun 9 14:01:07 2023 +// Update Count : 68 // @@ -29,5 +29,5 @@ int64_t atom; #endif // __SIZEOF_INT128__ -} __attribute__(( aligned( 16 ) )); +}; struct Node { @@ -42,5 +42,6 @@ n.next = stack; // atomic assignment unnecessary for () { // busy wait - if ( CASV( stack.atom, n.next.atom, ((Link){ &n, n.next.count + 1 }.atom) ) ) break; // attempt to update top node + Link temp{ &n, n.next.count + 1 }; + if ( CASV( s.stack.atom, n.next.atom, temp.atom ) ) break; // attempt to update top node } } @@ -50,5 +51,6 @@ for () { // busy wait if ( t.top == NULL ) return NULL; // empty stack ? - if ( CASV( stack.atom, t.atom, ((Link){ t.top->next.top, t.count }.atom) ) ) return t.top; // attempt to update top node + Link temp{ t.top->next.top, t.count }; + if ( CASV( stack.atom, t.atom, temp.atom ) ) return t.top; // attempt to update top node } } @@ -57,11 +59,5 @@ Stack stack; // global stack -enum { Times = - #if defined( __ARM_ARCH ) // ARM CASV is very slow - 10_000 - #else - 1_000_000 - #endif // __arm_64__ -}; +enum { Times = 2_000_000 }; thread Worker {}; @@ -82,6 +78,5 @@ for ( i; N ) { // push N values on stack - // storage must be 16-bytes aligned for cmpxchg16b - push( stack, *(Node *)memalign( 16, sizeof( Node ) ) ); + push( stack, *(Node *)new() ); // must be 16-byte aligned } { Index: tests/configs/.expect/parseconfig.txt =================================================================== --- tests/configs/.expect/parseconfig.txt (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/configs/.expect/parseconfig.txt (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -12,5 +12,5 @@ Maximum student trips: 3 -Open_Failure thrown when config file does not exist +open_failure thrown when config file does not exist Failed to open the config file Index: tests/configs/parseconfig.cfa =================================================================== --- tests/configs/parseconfig.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/configs/parseconfig.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -66,8 +66,8 @@ - sout | "Open_Failure thrown when config file does not exist"; + sout | "open_failure thrown when config file does not exist"; try { parse_config( xstr(IN_DIR) "doesnt-exist.txt", entries, NUM_ENTRIES, parse_tabular_config_format ); - } catch( Open_Failure * ex ) { + } catch( open_failure * ex ) { sout | "Failed to open the config file"; } Index: tests/copyfile.cfa =================================================================== --- tests/copyfile.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/copyfile.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Fri Jun 19 13:44:05 2020 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Aug 15 15:00:48 2020 -// Update Count : 6 +// Last Modified On : Mon Jun 5 21:20:19 2023 +// Update Count : 7 // @@ -30,7 +30,7 @@ exit | "Usage" | argv[0] | "[ input-file (default stdin) [ output-file (default stdout) ] ]"; } // choose - } catch( Open_Failure * ex ; ex->istream == &in ) { + } catch( open_failure * ex ; ex->istream == &in ) { exit | "Unable to open input file" | argv[1]; - } catch( Open_Failure * ex ; ex->ostream == &out ) { + } catch( open_failure * ex ; ex->ostream == &out ) { close( in ); // optional exit | "Unable to open output file" | argv[2]; Index: tests/rational.cfa =================================================================== --- tests/rational.cfa (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ tests/rational.cfa (revision 38e266ca6862f1e0af193a04ede8b53f17361fee) @@ -10,6 +10,6 @@ // Created On : Mon Mar 28 08:43:12 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Jul 20 18:13:40 2021 -// Update Count : 107 +// Last Modified On : Mon Jun 5 22:58:09 2023 +// Update Count : 108 // @@ -19,5 +19,5 @@ #include -typedef Rational(int) RatInt; +typedef rational(int) rat_int; double convert( int i ) { return (double)i; } // used by narrow/widen int convert( double d ) { return (int)d; } @@ -25,24 +25,24 @@ int main() { sout | "constructor"; - RatInt a = { 3 }, b = { 4 }, c, d = 0, e = 1; + rat_int a = { 3 }, b = { 4 }, c, d = 0, e = 1; sout | "a : " | a | "b : " | b | "c : " | c | "d : " | d | "e : " | e; - a = (RatInt){ 4, 8 }; - b = (RatInt){ 5, 7 }; + a = (rat_int){ 4, 8 }; + b = (rat_int){ 5, 7 }; sout | "a : " | a | "b : " | b; - a = (RatInt){ -2, -3 }; - b = (RatInt){ 3, -2 }; + a = (rat_int){ -2, -3 }; + b = (rat_int){ 3, -2 }; sout | "a : " | a | "b : " | b; - a = (RatInt){ -2, 3 }; - b = (RatInt){ 3, 2 }; + a = (rat_int){ -2, 3 }; + b = (rat_int){ 3, 2 }; sout | "a : " | a | "b : " | b; sout | nl; sout | "comparison"; - a = (RatInt){ -2 }; - b = (RatInt){ -3, 2 }; + a = (rat_int){ -2 }; + b = (rat_int){ -3, 2 }; sout | "a : " | a | "b : " | b; - sout | "a == 0 : " | a == (Rational(int)){0}; // FIX ME - sout | "a == 1 : " | a == (Rational(int)){1}; // FIX ME + sout | "a == 0 : " | a == (rational(int)){0}; // FIX ME + sout | "a == 1 : " | a == (rational(int)){1}; // FIX ME sout | "a != 0 : " | a != 0; sout | "! a : " | ! a; @@ -73,9 +73,9 @@ sout | "conversion"; - a = (RatInt){ 3, 4 }; + a = (rat_int){ 3, 4 }; sout | widen( a ); - a = (RatInt){ 1, 7 }; + a = (rat_int){ 1, 7 }; sout | widen( a ); - a = (RatInt){ 355, 113 }; + a = (rat_int){ 355, 113 }; sout | widen( a ); sout | narrow( 0.75, 4 ); @@ -90,5 +90,5 @@ sout | "more tests"; - RatInt x = { 1, 2 }, y = { 2 }; + rat_int x = { 1, 2 }, y = { 2 }; sout | x - y; sout | x > y; @@ -96,12 +96,12 @@ sout | y | denominator( y, -2 ) | y; - RatInt z = { 0, 5 }; + rat_int z = { 0, 5 }; sout | z; sout | x | numerator( x, 0 ) | x; - x = (RatInt){ 1, MAX } + (RatInt){ 1, MAX }; + x = (rat_int){ 1, MAX } + (rat_int){ 1, MAX }; sout | x; - x = (RatInt){ 3, MAX } + (RatInt){ 2, MAX }; + x = (rat_int){ 3, MAX } + (rat_int){ 2, MAX }; sout | x; Index: sts/zombies/simplePoly.c =================================================================== --- tests/zombies/simplePoly.c (revision 1db6d707c9c3bb51aa52503723989ef9490a8c10) +++ (revision ) @@ -1,34 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// simplePoly.c -- -// -// Author : Richard C. Bilson -// Created On : Wed May 27 17:56:53 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue Mar 8 22:06:41 2016 -// Update Count : 3 -// - -forall( T, U | { T f( T, U ); } ) -T q( T t, U u ) { - return f( t, u ); -// return t; -} - -int f( int, double* ); - -void g( void ) { - int y; - double x; -// if ( y ) - q( 3, &x ); -} - -// Local Variables: // -// tab-width: 4 // -// compile-command: "cfa simplePoly.c" // -// End: //