Changeset 3c6e417

doc/papers/concurrency/Paper.tex

-                      r1e5dedc4
+                      r3c6e417
 Libraries like pthreads were developed for C, and the Solaris operating-system switched from user (JDK 1.1~\cite{JDK1.1}) to kernel threads.
 As a result, languages like Java, Scala, Objective-C~\cite{obj-c-book}, \CCeleven~\cite{C11}, and C\#~\cite{Csharp} adopt the 1:1 kernel-threading model, with a variety of presentation mechanisms.
 From 2000 onwards, languages like Go~\cite{Go}, Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, D~\cite{D}, and \uC~\cite{uC++,uC++book} have championed the M:N user-threading model, and many user-threading libraries have appeared~\cite{Qthreads,MPC,BoostThreads}, including putting green threads back into Java~\cite{Quasar}.
+From 2000 onwards, languages like Go~\cite{Go}, Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, D~\cite{D}, and \uC~\cite{uC++,uC++book} have championed the M:N user-threading model, and many user-threading libraries have appeared~\cite{Qthreads,MPC,Marcel}, including putting green threads back into Java~\cite{Quasar}.
 The main argument for user-level threading is that they are lighter weight than kernel threads (locking and context switching do not cross the kernel boundary), so there is less restriction on programming styles that encourage large numbers of threads performing medium work-units to facilitate load balancing by the runtime~\cite{Verch12}.
 As well, user-threading facilitates a simpler concurrency approach using thread objects that leverage sequential patterns versus events with call-backs~\cite{vonBehren03}.
 …
 Finally, it is important for a language to provide safety over performance \emph{as the default}, allowing careful reduction of safety for performance when necessary.
 Two concurrency violations of this philosophy are \emph{spurious wakeup} and \emph{barging}, i.e., random wakeup~\cite[\S~8]{Buhr05a} and signals-as-hints~\cite[\S~8]{Buhr05a}, where one is a consequence of the other, i.e., once there is spurious wakeup, signals-as-hints follows.
+Two concurrency violations of this philosophy are \emph{spurious wakeup} (random wakeup~\cite[\S~8]{Buhr05a}) and \emph{barging} (signals-as-hints~\cite[\S~8]{Buhr05a}), where one is a consequence of the other, i.e., once there is spurious wakeup, signals-as-hints follows.
 However, spurious wakeup is \emph{not} a foundational concurrency property~\cite[\S~8]{Buhr05a}, it is a performance design choice.
 Similarly, signals-as-hints is often a performance decision.
 We argue removing spurious wakeup and signals-as-hints makes concurrent programming significantly safer because it removes local non-determinism and matches with programmer expectation.
 (Authors experience teaching concurrency is that students are highly confused by these semantics.)
+(Author experience teaching concurrency is that students are highly confused by these semantics.)
 Clawing back performance, when local non-determinism is unimportant, should be an option not the default.
 …
 \section{Stateful Function}
+The generator/coroutine provides a stateful function, which is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}.
+A stateful function allows execution to be temporarily suspended and later resumed, e.g., plugin, device driver, finite-state machine.
+The stateful function is an old idea~\cite{Conway63,Marlin80} that is new again~\cite{C++20Coroutine19}, where execution is temporarily suspended and later resumed, e.g., plugin, device driver, finite-state machine.
 Hence, a stateful function may not end when it returns to its caller, allowing it to be restarted with the data and execution location present at the point of suspension.
 This capability is accomplished by retaining a data/execution \emph{closure} between invocations.
 …
 \end{figure}
 For generators, coroutines, and threads, many designs are based on function objects or pointers~\cite{Butenhof97, C++14, MS:VisualC++, BoostCoroutines15}.
+Stateful functions appear as generators, coroutines, and threads, where presentations are based on function objects or pointers~\cite{Butenhof97, C++14, MS:VisualC++, BoostCoroutines15}.
 For example, Python presents generators as a function object:
 \begin{python}
 …
 Figure~\ref{f:FibonacciAsymmetricGenerator} shows an unbounded asymmetric generator for an infinite sequence of Fibonacci numbers written in C and \CFA, with a simple C implementation for the \CFA version.
 This kind of generator is an \emph{output generator}, producing a new result on each resumption.
+This generator is an \emph{output generator}, producing a new result on each resumption.
 To compute Fibonacci, the previous two values in the sequence are retained to generate the next value, \ie @fn1@ and @fn@, plus the execution location where control restarts when the generator is resumed, \ie top or middle.
 An additional requirement is the ability to create an arbitrary number of generators (of any kind), \ie retaining state in global variables is insufficient;
+An additional requirement is the ability to create an arbitrary number of generators (of any kind), \ie retaining one state in global variables is insufficient;
 hence, state is retained in a closure between calls.
 Figure~\ref{f:CFibonacci} shows the C approach of manually creating the closure in structure @Fib@, and multiple instances of this closure provide multiple Fibonacci generators.
 The C version only has the middle execution state because the top execution state becomes declaration initialization.
+The C version only has the middle execution state because the top execution state is declaration initialization.
 Figure~\ref{f:CFAFibonacciGen} shows the \CFA approach, which also has a manual closure, but replaces the structure with a custom \CFA @generator@ type.
 This generator type is then connected to a function that \emph{must be named \lstinline|main|},\footnote{
 …
 As well, the data state is small, where variables @byte@ and @msg@ are communication variables for passing in message bytes and returning the message, and variables @lnth@, @crc@, and @sum@ are local variable that must be retained between calls and are manually hoisted into the generator type.
 % Manually, detecting and hoisting local-state variables is easy when the number is small.
 Finally, the execution state is large, with one @resume@ and seven @suspend@s.
+In contrast, the execution state is large, with one @resume@ and seven @suspend@s.
 Hence, the key benefits of the generator are correctness, safety, and maintenance because the execution states are transcribed directly into the programming language rather than using a table-driven approach.
 Because FSMs can be complex and occur frequently in important domains, direct support of the generator is crucial in a systems programming-language.
 …
 Figure~\ref{f:CFAPingPongGen} shows a symmetric generator, where the generator resumes another generator, forming a resume/resume cycle.
 (The trivial cycle is a generator resuming itself.)
 This control flow is similar to recursion for functions, but without stack growth.
+This control flow is similar to recursion for functions but without stack growth.
 The steps for symmetric control-flow are creating, executing, and terminating the cycle.
 Constructing the cycle must deal with definition-before-use to close the cycle, \ie, the first generator must know about the last generator, which is not within scope.
 …
 Terminating the cycle is accomplished by @suspend@ or @return@, both of which go back to the stack frame that started the cycle (program main in the example).
 The starting stack-frame is below the last active generator because the resume/resume cycle does not grow the stack.
 Also, since local variables are not retained in the generator function, it does not contain an objects with destructors that must be called, so the  cost is the same as a function return.
+Also, since local variables are not retained in the generator function, it does not contain any objects with destructors that must be called, so the  cost is the same as a function return.
 Destructor cost occurs when the generator instance is deallocated, which is easily controlled by the programmer.
 …
 Hence, the starter coroutine is remembered on the first resume and ending the coroutine resumes the starter.
 Figure~\ref{f:ProdConsRuntimeStacks} shows this semantic by the dashed lines from the end of the coroutine mains: @prod@ starts @cons@ so @cons@ resumes @prod@ at the end, and the program main starts @prod@ so @prod@ resumes the program main at the end.
 For other scenarios, it is always possible to devise a solution with additional programming effort.
+For other scenarios, it is always possible to devise a solution with additional programming effort, such as forcing the cycle forward (backward) to a safe point before starting termination.
 The producer/consumer example does not illustrate the full power of the starter semantics because @cons@ always ends first.
 …
 The function definitions ensures there is a statically-typed @main@ function that is the starting point (first stack frame) of a coroutine, and a mechanism to get (read) the currently executing coroutine handle.
 The @main@ function has no return value or additional parameters because the coroutine type allows an arbitrary number of interface functions with corresponding arbitrary typed input/output values versus fixed ones.
 The advantage of this approach is that users can easily create different types of coroutines, \eg changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ function, and possibly redefining @suspend@ and @resume@.
+The advantage of this approach is that users can easily create different types of coroutines, \eg changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ function, and possibly redefining \textsf{suspend} and @resume@.
 The \CFA custom-type @coroutine@ implicitly implements the getter and forward declarations for the coroutine main.
 …
 Once allocated, a VLS is fixed sized.}
 on the allocating stack, provided the allocating stack is large enough.
 For a VLS stack allocation, allocation/deallocation is an inexpensive adjustment of the stack point, modulo any stack constructor costs (\eg initial frame setup).
+For a VLS stack allocation/deallocation is an inexpensive adjustment of the stack pointer, modulo any stack constructor costs (\eg initial frame setup).
 For heap stack allocation, allocation/deallocation is an expensive heap allocation (where the heap can be a shared resource), modulo any stack constructor costs.
 With heap stack allocation, it is also possible to use a split (segmented) stack calling-convention, available with gcc and clang, so the stack is variable sized.
 …
 However, coroutines are a stepping stone towards concurrency.
 The transition to concurrency, even for a single thread with multiple stacks, occurs when coroutines context switch to a \newterm{scheduling coroutine}, introducing non-determinism from the coroutine perspective~\cite[\S~3,]{Buhr05a}\cite{Adya02}.
+The transition to concurrency, even for a single thread with multiple stacks, occurs when coroutines context switch to a \newterm{scheduling coroutine}, introducing non-determinism from the coroutine perspective~\cite[\S~3,]{Buhr05a}.
 Therefore, a minimal concurrency system requires coroutines \emph{in conjunction with a nondeterministic scheduler}.
 The resulting execution system now follows a cooperative threading-model, called \newterm{non-preemptive scheduling}.
+The resulting execution system now follows a cooperative threading-model~\cite{Adya02,libdill}, called \newterm{non-preemptive scheduling}.
 Adding \newterm{preemption} introduces non-cooperative scheduling, where context switching occurs randomly between any two instructions often based on a timer interrupt, called \newterm{preemptive scheduling}.
 While a scheduler introduces uncertain execution among explicit context switches, preemption introduces uncertainty by introducing implicit context switches.
 …
 This semantic ensures a thread is started and stopped exactly once, eliminating some programming error, and scales to multiple threads for basic (termination) synchronization.
 For block allocation to arbitrary depth, including recursion, threads are created/destroyed in a lattice structure (tree with top and bottom).
 Arbitrary topologies are possible using dynamic allocation, allowing threads to outlive their declaration scope, identical to normal dynamically allocating.
+Arbitrary topologies are possible using dynamic allocation, allowing threads to outlive their declaration scope, identical to normal dynamic allocation.
 \begin{cfa}
 MyTask * factory( int N ) { ... return `anew( N )`; } $\C{// allocate heap-based threads, implicit start after construction}$
 …
 \subsection{Mutual Exclusion}
 A group of instructions manipulating a specific instance of shared data that must be performed atomically is called an (individual) \newterm{critical-section}~\cite{Dijkstra65}.
 The generalization is called a \newterm{group critical-section}~\cite{Joung00}, where multiple tasks with the same session may use the resource simultaneously, but different sessions may not use the resource simultaneously.
+A group of instructions manipulating a specific instance of shared data that must be performed atomically is called a \newterm{critical section}~\cite{Dijkstra65}, which is enforced by \newterm{simple mutual-exclusion}.
+The generalization is called a \newterm{group critical-section}~\cite{Joung00}, where multiple tasks with the same session use the resource simultaneously and different sessions are segregated, which is enforced by \newterm{complex mutual-exclusion} providing the correct kind and number of threads using a group critical-section.
 The readers/writer problem~\cite{Courtois71} is an instance of a group critical-section, where readers share a session but writers have a unique session.
-\newterm{Mutual exclusion} enforces the correct kind and number of threads using a critical section.
 However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
 …
 Preventing or detecting barging is an involved challenge with low-level locks, which is made easier through higher-level constructs.
 This challenge is often split into two different approaches: barging avoidance and prevention.
 Algorithms that unconditionally releasing a lock for competing threads to acquire use barging avoidance during synchronization to force a barging thread to wait.
+Algorithms that unconditionally releasing a lock for competing threads to acquire use barging avoidance during synchronization to force a barging thread to wait;
 algorithms that conditionally hold locks during synchronization, \eg baton-passing~\cite{Andrews89}, prevent barging completely.
 …
 For this reason, \CFA requires programmers to identify the kind of parameter with the @mutex@ keyword and uses no keyword to mean \lstinline[morekeywords=nomutex]@nomutex@.
-\newpage
 The next semantic decision is establishing which parameter \emph{types} may be qualified with @mutex@.
 The following has monitor parameter types that are composed of multiple objects.
 …
 Users can still force the acquiring order by using @mutex@/\lstinline[morekeywords=nomutex]@nomutex@.
-\newpage
 \begin{cfa}
 void foo( M & mutex m1, M & mutex m2 ); $\C{// acquire m1 and m2}$
 …
 \end{cfa}
 The bulk-acquire semantics allow @bar@ or @baz@ to acquire a monitor lock and reacquire it in @foo@.
 In the calls to @bar@ and @baz@, the monitors are acquired in opposite order, possibly resulting in deadlock.
+The calls to @bar@ and @baz@ acquired the monitors in opposite order, possibly resulting in deadlock.
 However, this case is the simplest instance of the \emph{nested-monitor problem}~\cite{Lister77}, where monitors are acquired in sequence versus bulk.
 Detecting the nested-monitor problem requires dynamic tracking of monitor calls, and dealing with it requires rollback semantics~\cite{Dice10}.
 …
 % It is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signalling program without any danger that a third program will interpose a monitor entry and seize the resource instead.~\cite[p.~550]{Hoare74}
 % \end{cquote}
 Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implicit form of barging.
+Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implicit form of self barging.
 Hence, a \CFA @wait@ statement is not enclosed in a @while@ loop retesting a blocking predicate, which can cause thread starvation due to barging.
 Figure~\ref{f:MonitorScheduling} shows internal/external scheduling (for the bounded-buffer example in Figure~\ref{f:InternalExternalScheduling}).
+Figure~\ref{f:MonitorScheduling} shows general internal/external scheduling (for the bounded-buffer example in Figure~\ref{f:InternalExternalScheduling}).
 External calling threads block on the calling queue, if the monitor is occupied, otherwise they enter in FIFO order.
 Internal threads block on condition queues via @wait@ and they reenter from the condition in FIFO order.
+Internal threads block on condition queues via @wait@ and they reenter from the condition in FIFO order, or they block on urgent via @signal_block@ or @waitfor@ and reenter implicit when the monitor becomes empty, \ie, the thread in the monitor exits or waits.
 There are three signalling mechanisms to unblock waiting threads to enter the monitor.
 Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion so only can proceed.
+Note, signalling cannot have the signaller and signalled thread in the monitor simultaneously because of the mutual exclusion so only one can proceed.
 For internal scheduling, threads are unblocked from condition queues using @signal@, where the signallee is moved to urgent and the signaller continues (solid line).
 Multiple signals move multiple signallees to urgent, until the condition is empty.
 …
 Executing multiple @waitfor@s from different signalled functions causes the calling threads to move to urgent.
 External scheduling requires urgent to be a stack, because the signaller excepts to execute immediately after the specified monitor call has exited or waited.
+Internal scheduling behaves the same for an urgent stack or queue, except for signalling multiple threads, where the threads unblock from urgent in reverse order from signalling.
+If the restart order is important, multiple signalling by a signal thread can be transformed into shared signalling among threads, where each thread signals the next thread.
+Hence, \CFA uses an urgent stack.
+Internal scheduling behaves the same for an urgent stack or queue, except for multiple signalling, where the threads unblock from urgent in reverse order from signalling.
+If the restart order is important, multiple signalling by a signal thread can be transformed into daisy-chain signalling among threads, where each thread signals the next thread.
+We tried both a stack for @waitfor@ and queue for signalling, but that resulted in complex semantics about which thread enters next.
+Hence, \CFA uses a single urgent stack to correctly handle @waitfor@ and adequately support both forms of signalling.
 \begin{figure}
 …
 \end{figure}
 Figure~\ref{f:BBInt} shows a \CFA generic bounded-buffer with internal scheduling, where producers/consumers enter the monitor, see the buffer is full/empty, and block on an appropriate condition variable, @full@/@empty@.
+Figure~\ref{f:BBInt} shows a \CFA generic bounded-buffer with internal scheduling, where producers/consumers enter the monitor, detect the buffer is full/empty, and block on an appropriate condition variable, @full@/@empty@.
 The @wait@ function atomically blocks the calling thread and implicitly releases the monitor lock(s) for all monitors in the function's parameter list.
 The appropriate condition variable is signalled to unblock an opposite kind of thread after an element is inserted/removed from the buffer.
 …
 External scheduling is controlled by the @waitfor@ statement, which atomically blocks the calling thread, releases the monitor lock, and restricts the function calls that can next acquire mutual exclusion.
 If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
 Threads making calls to functions that are currently excluded block outside of (external to) the monitor on the calling queue, versus blocking on condition queues inside of (internal to) the monitor.
+Calls threads to functions that are currently excluded block outside of (external to) the monitor on the calling queue, versus blocking on condition queues inside of (internal to) the monitor.
 Figure~\ref{f:RWExt} shows a readers/writer lock written using external scheduling, where a waiting reader detects a writer using the resource and restricts further calls until the writer exits by calling @EndWrite@.
 The writer does a similar action for each reader or writer using the resource.
 Note, no new calls to @StarRead@/@StartWrite@ may occur when waiting for the call to @EndRead@/@EndWrite@.
 External scheduling allows waiting for events from other threads while restricting unrelated events.
+External scheduling allows waiting for events from other threads while restricting unrelated events, that would otherwise have to wait on conditions in the monitor.
 The mechnaism can be done in terms of control flow, \eg Ada @accept@ or \uC @_Accept@, or in terms of data, \eg Go @select@ on channels.
 While both mechanisms have strengths and weaknesses, this project uses the control-flow mechanism to be consistent with other language features.
 …
 Furthermore, barging corrupts the dating service during an exchange because a barger may also match and change the phone numbers, invalidating the previous exchange phone number.
 Putting loops around the @wait@s does not correct the problem;
 the solution must be restructured to account for barging.
+the simple solution must be restructured to account for barging.
 \begin{figure}
 …
 the signaller enters the monitor and changes state, detects a waiting threads that can use the state, performs a non-blocking signal on the condition queue for the waiting thread, and exits the monitor to run concurrently.
 The waiter unblocks next from the urgent queue, uses/takes the state, and exits the monitor.
 Blocking signalling is the reverse, where the waiter is providing the cooperation for the signalling thread;
+Blocking signal is the reverse, where the waiter is providing the cooperation for the signalling thread;
 the signaller enters the monitor, detects a waiting thread providing the necessary state, performs a blocking signal to place it on the urgent queue and unblock the waiter.
 The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to use/take the state.
 …
 While \CC supports bulk locking, @wait@ only accepts a single lock for a condition variable, so bulk locking with condition variables is asymmetric.
 Finally, a signaller,
-\newpage
 \begin{cfa}
 void baz( M & mutex m1, M & mutex m2 ) {
 …
+}
 \end{cfa}
 must have acquired at least the same locks as the waiting thread signalled from the condition queue.
+must have acquired at least the same locks as the waiting thread signalled from a condition queue to allow the locks to be passed, and hence, prevent barging.
 Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex parameters, \ie @waitfor( rtn, m1, m2 )@.
 …
 The \emph{conditional-expression} of a @when@ may call a function, but the function must not block or context switch.
 If there are multiple acceptable mutex calls, selection occurs top-to-bottom (prioritized) among the @waitfor@ clauses, whereas some programming languages with similar mechanisms accept nondeterministically for this case, \eg Go \lstinline[morekeywords=select]@select@.
 If some accept guards are true and there are no outstanding calls to these members, the acceptor is accept-blocked until a call to one of these members is made.
+If some accept guards are true and there are no outstanding calls to these members, the acceptor is blocked until a call to one of these members is made.
 If there is a @timeout@ clause, it provides an upper bound on waiting.
 If all the accept guards are false, the statement does nothing, unless there is a terminating @else@ clause with a true guard, which is executed instead.
 …
 However, the basic @waitfor@ semantics do not support this functionality, since using an object after its destructor is called is undefined.
 Therefore, to make this useful capability work, the semantics for accepting the destructor is the same as @signal@, \ie the call to the destructor is placed on the urgent queue and the acceptor continues execution, which throws an exception to the acceptor and then the caller is unblocked from the urgent queue to deallocate the object.
 Accepting the destructor is an idiomatic way to terminate a thread in \CFA.
+Accepting the destructor is the idiomatic way to terminate a thread in \CFA.
 …
 In the object-oriented scenario, the type and all its operators are always present at compilation (even separate compilation), so it is possible to number the operations in a bit mask and use an $O(1)$ compare with a similar bit mask created for the operations specified in a @waitfor@.
 In \CFA, monitor functions can be statically added/removed in translation units, so it is impossible to apply an $O(1)$ approach.
+However, in \CFA, monitor functions can be statically added/removed in translation units, making a fast subset check difficult.
 \begin{cfa}
         monitor M { ... }; // common type, included in .h file
 …
         void g( M & mutex m ) { waitfor( `f`, m ); }
 translation unit 2
         void `f`( M & mutex m );
+        void `f`( M & mutex m ); $\C{// replacing f and g for type M in this translation unit}$
         void `g`( M & mutex m );
         void h( M & mutex m ) { waitfor( `f`, m ) or waitfor( `g`, m ); }
+        void h( M & mutex m ) { waitfor( `f`, m ) or waitfor( `g`, m ); } $\C{// extending type M in this translation unit}$
 \end{cfa}
 The @waitfor@ statements in each translation unit cannot form a unique bit-mask because the monitor type does not carry that information.
 Hence, function pointers are used to identify the functions listed in the @waitfor@ statement, stored in a variable-sized array,
+Hence, function pointers are used to identify the functions listed in the @waitfor@ statement, stored in a variable-sized array.
 Then, the same implementation approach used for the urgent stack is used for the calling queue.
 Each caller has a list of monitors acquired, and the @waitfor@ statement performs a (usually short) linear search matching functions in the @waitfor@ list with called functions, and then verifying the associated mutex locks can be transfers.
 …
 External scheduling, like internal scheduling, becomes significantly more complex for multi-monitor semantics.
 Even in the simplest case, new semantics needs to be established.
+Even in the simplest case, new semantics need to be established.
 \begin{cfa}
 monitor M { ... };
 …
 For completeness and efficiency, \CFA provides a standard set of low-level locks: recursive mutex, condition, semaphore, barrier, \etc, and atomic instructions: @fetchAssign@, @fetchAdd@, @testSet@, @compareSet@, \etc.
 However, we strongly advocate using high-level concurrency mechanisms whenever possible.
+Some of these low-level mechanism are used in the \CFA runtime, but we strongly advocate using high-level mechanisms whenever possible.
 …
 \label{s:RuntimeStructureCluster}
 A \newterm{cluster} is a collection of threads and virtual processors (abstract kernel-thread) that execute the threads from its own ready queue (like an OS).
+A \newterm{cluster} is a collection of threads and virtual processors (abstract kernel-thread) that execute the (user) threads from its own ready queue (like an OS executing kernel threads).
 The purpose of a cluster is to control the amount of parallelism that is possible among threads, plus scheduling and other execution defaults.
 The default cluster-scheduler is single-queue multi-server, which provides automatic load-balancing of threads on processors.
 However, the scheduler is pluggable, supporting alternative schedulers, such as multi-queue multi-server, with work-stealing/sharing.
+However, the scheduler is pluggable, supporting alternative schedulers, such as multi-queue multi-server, with work-stealing/sharing across the virtual processors.
 If several clusters exist, both threads and virtual processors, can be explicitly migrated from one cluster to another.
 No automatic load balancing among clusters is performed by \CFA.
 …
 \label{s:RuntimeStructureProcessor}
 A virtual processor is implemented by a kernel thread (\eg UNIX process), which is subsequently scheduled for execution on a hardware processor by the underlying operating system.
+A virtual processor is implemented by a kernel thread (\eg UNIX process), which are scheduled for execution on a hardware processor by the underlying operating system.
 Programs may use more virtual processors than hardware processors.
 On a multiprocessor, kernel threads are distributed across the hardware processors resulting in virtual processors executing in parallel.
 (It is possible to use affinity to lock a virtual processor onto a particular hardware processor~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which is used when caching issues occur or for heterogeneous hardware processors.)
 The \CFA runtime attempts to block unused processors and unblock processors as the system load increases;
 balancing the workload with processors is difficult.
+balancing the workload with processors is difficult because it requires future knowledge, \ie what will the applicaton workload do next.
 Preemption occurs on virtual processors rather than user threads, via operating-system interrupts.
 Thus virtual processors execute user threads, where preemption frequency applies to a virtual processor, so preemption occurs randomly across the executed user threads.
 …
 \subsection{Preemption}
 Nondeterministic preemption provides fairness from long running threads, and forces concurrent programmers to write more robust programs, rather than relying on section of code between cooperative scheduling to be atomic,
+Nondeterministic preemption provides fairness from long running threads, and forces concurrent programmers to write more robust programs, rather than relying on section of code between cooperative scheduling to be atomic.
 A separate reason for not supporting preemption is that it significantly complicates the runtime system.
 Preemption is normally handled by setting a count-down timer on each virtual processor.
 …
 There are two versions of the \CFA runtime kernel: debug and non-debug.
 The debugging version has many runtime checks and internal assertions, \eg stack (non-writable) guard page, and checks for stack overflow whenever context switches occur among coroutines and threads, which catches most stack overflows.
 After a program is debugged, the non-debugging version can be used to decrease space and increase performance.
+After a program is debugged, the non-debugging version can be used to significantly decrease space and increase performance.
 …
 The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine to force stack creation, the creation cost is artificially low.
-\newpage
 \begin{multicols}{2}
 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
 …
 One solution is to offer various tuning options, allowing the scheduler to be adjusted to the requirements of the workload.
 However, to be truly flexible, a pluggable scheduler is necessary.
 Currently, the \CFA pluggable scheduler is too simple to handle complex scheduling, \eg quality of service and real-time, where the scheduler must interact with mutex objects to deal with issues like priority inversion.
+Currently, the \CFA pluggable scheduler is too simple to handle complex scheduling, \eg quality of service and real-time, where the scheduler must interact with mutex objects to deal with issues like priority inversion~\cite{Buhr00b}.
 \paragraph{Non-Blocking I/O}
 …
 \section{Acknowledgements}
 The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz and Andrew Beach on the features described in this paper.
+The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz, Andrew Beach and Michael Brooks on the features described in this paper.
 Funding for this project has been provided by Huawei Ltd.\ (\url{http://www.huawei.com}). %, and Peter Buhr is partially funded by the Natural Sciences and Engineering Research Council of Canada.

libcfa/src/clock.hfa

-                      r1e5dedc4
+                      r3c6e417
 // Created On       : Thu Apr 12 14:36:06 2018
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Mon Jul  2 21:40:01 2018
 // Update Count     : 7
+// Last Modified On : Thu Jun 13 21:21:13 2019
+// Update Count     : 8
 //
 …
                 clock_gettime( CLOCK_REALTIME, &curr );
                 return (Time){ curr };
         } // getTime
+        } // getTimeNsec
         Time getTime() {                                                                        // without nanoseconds

src/AST/Convert.cpp

-                      r1e5dedc4
+                      r3c6e417
         const ast::Expr * visit( const ast::UniqueExpr * node ) override final {
                 auto rslt = new UniqueExpr(
+                        get<Expression>().accept1(node->expr)
+                        get<Expression>().accept1(node->expr),
+                        node->id
                 );
 …
+        }
+        const ast::Type * visitType( const ast::Type * node, Type * type ) {
+                // Some types do this in their constructor so add a check.
+                if ( !node->attributes.empty() && type->attributes.empty() ) {
+                        type->attributes = get<Attribute>().acceptL( node->attributes );
+                }
+                this->node = type;
+                return nullptr;
+        }
         const ast::Type * visit( const ast::VoidType * node ) override final {
+                this->node = new VoidType{ cv( node ) };
+                return nullptr;
+                return visitType( node, new VoidType{ cv( node ) } );
+        }
 …
                         Validate::SizeType = type;
+                }
+                this->node = type;
+                return nullptr;
+                return visitType( node, type );
+        }
         const ast::Type * visit( const ast::PointerType * node ) override final {
                 this->node = new PointerType{
+                return visitType( node, new PointerType{
                         cv( node ),
                         get<Type>().accept1( node->base ),
 …
                         (bool)node->isVarLen,
                         (bool)node->isStatic
+                };
+                return nullptr;
+                } );
+        }
         const ast::Type * visit( const ast::ArrayType * node ) override final {
                 this->node = new ArrayType{
+                return visitType( node, new ArrayType{
                         cv( node ),
                         get<Type>().accept1( node->base ),
 …
                         (bool)node->isVarLen,
                         (bool)node->isStatic
+                };
+                return nullptr;
+                } );
+        }
         const ast::Type * visit( const ast::ReferenceType * node ) override final {
                 this->node = new ReferenceType{
+                return visitType( node, new ReferenceType{
                         cv( node ),
                         get<Type>().accept1( node->base )
+                };
+                return nullptr;
+                } );
+        }
         const ast::Type * visit( const ast::QualifiedType * node ) override final {
                 this->node = new QualifiedType{
+                return visitType( node, new QualifiedType{
                         cv( node ),
                         get<Type>().accept1( node->parent ),
                         get<Type>().accept1( node->child )
+                };
+                return nullptr;
+                } );
+        }
 …
                 ty->parameters = get<DeclarationWithType>().acceptL( node->params );
                 ty->forall = get<TypeDecl>().acceptL( node->forall );
+                this->node = ty;
+                return nullptr;
+        }
+        void postvisit( const ast::ReferenceToType * old, ReferenceToType * ty ) {
+                return visitType( node, ty );
+        }
+        const ast::Type * postvisit( const ast::ReferenceToType * old, ReferenceToType * ty ) {
                 ty->forall = get<TypeDecl>().acceptL( old->forall );
                 ty->parameters = get<Expression>().acceptL( old->params );
                 ty->hoistType = old->hoistType;
+                return visitType( old, ty );
+        }
 …
                         };
+                }
+                postvisit( node, ty );
+                this->node = ty;
+                return nullptr;
+                return postvisit( node, ty );
+        }
 …
                         };
+                }
+                postvisit( node, ty );
+                this->node = ty;
+                return nullptr;
+                return postvisit( node, ty );
+        }
 …
                         };
+                }
+                postvisit( node, ty );
+                this->node = ty;
+                return nullptr;
+                return postvisit( node, ty );
+        }
 …
                         };
+                }
+                postvisit( node, ty );
+                this->node = ty;
+                return nullptr;
+                return postvisit( node, ty );
+        }
 …
                         };
+                }
+                postvisit( node, ty );
+                this->node = ty;
+                return nullptr;
+                return postvisit( node, ty );
+        }
         const ast::Type * visit( const ast::TupleType * node ) override final {
                 this->node = new TupleType{
+                return visitType( node, new TupleType{
                         cv( node ),
                         get<Type>().acceptL( node->types )
                         // members generated by TupleType c'tor
+                };
+                return nullptr;
+                } );
+        }
         const ast::Type * visit( const ast::TypeofType * node ) override final {
                 this->node = new TypeofType{
+                return visitType( node, new TypeofType{
                         cv( node ),
                         get<Expression>().accept1( node->expr ),
                         (bool)node->kind
+                };
+                return nullptr;
+                } );
+        }
         const ast::Type * visit( const ast::VarArgsType * node ) override final {
+                this->node = new VarArgsType{ cv( node ) };
+                return nullptr;
+                return visitType( node, new VarArgsType{ cv( node ) } );
+        }
         const ast::Type * visit( const ast::ZeroType * node ) override final {
+                this->node = new ZeroType{ cv( node ) };
+                return nullptr;
+                return visitType( node, new ZeroType{ cv( node ) } );
+        }
         const ast::Type * visit( const ast::OneType * node ) override final {
+                this->node = new OneType{ cv( node ) };
+                return nullptr;
+        }
+        const ast::Type * visit( const ast::GlobalScopeType * ) override final {
+                this->node = new GlobalScopeType{};
+                return nullptr;
+                return visitType( node, new OneType{ cv( node ) } );
+        }
+        const ast::Type * visit( const ast::GlobalScopeType * node ) override final {
+                return visitType( node, new GlobalScopeType{} );
+        }
 …
                 auto rslt = new ast::UniqueExpr(
                         old->location,
+                        GET_ACCEPT_1(expr, Expr)
+                        GET_ACCEPT_1(expr, Expr),
+                        old->get_id()
                 );
                 rslt->object = GET_ACCEPT_1(object, ObjectDecl);
 …
+        }
+        void visitType( Type * old, ast::Type * type ) {
+                // Some types do this in their constructor so add a check.
+                if ( !old->attributes.empty() && type->attributes.empty() ) {
+                        type->attributes = GET_ACCEPT_V(attributes, Attribute);
+                }
+                this->node = type;
+        }
         virtual void visit( VoidType * old ) override final {
                 this->node = new ast::VoidType{ cv( old ) };
+                visitType( old, new ast::VoidType{ cv( old ) } );
+        }
 …
                         sizeType = type;
+                }
                 this->node = type;
+                visitType( old, type );
+        }
         virtual void visit( PointerType * old ) override final {
                 this->node = new ast::PointerType{
+                visitType( old, new ast::PointerType{
                         GET_ACCEPT_1( base, Type ),
                         GET_ACCEPT_1( dimension, Expr ),
 …
                         (ast::DimensionFlag)old->isStatic,
                         cv( old )
                 };
+                } );
+        }
         virtual void visit( ArrayType * old ) override final {
                 this->node = new ast::ArrayType{
+                visitType( old, new ast::ArrayType{
                         GET_ACCEPT_1( base, Type ),
                         GET_ACCEPT_1( dimension, Expr ),
 …
                         (ast::DimensionFlag)old->isStatic,
                         cv( old )
                 };
+                } );
+        }
         virtual void visit( ReferenceType * old ) override final {
                 this->node = new ast::ReferenceType{
+                visitType( old, new ast::ReferenceType{
                         GET_ACCEPT_1( base, Type ),
                         cv( old )
                 };
+                } );
+        }
         virtual void visit( QualifiedType * old ) override final {
                 this->node = new ast::QualifiedType{
+                visitType( old, new ast::QualifiedType{
                         GET_ACCEPT_1( parent, Type ),
                         GET_ACCEPT_1( child, Type ),
                         cv( old )
                 };
+                } );
+        }
 …
                 ty->params = GET_ACCEPT_V( parameters, DeclWithType );
                 ty->forall = GET_ACCEPT_V( forall, TypeDecl );
                 this->node = ty;
+                visitType( old, ty );
+        }
 …
                 ty->params = GET_ACCEPT_V( parameters, Expr );
                 ty->hoistType = old->hoistType;
+                visitType( old, ty );
+        }
 …
+                }
                 postvisit( old, ty );
-                this->node = ty;
+        }
 …
+                }
                 postvisit( old, ty );
-                this->node = ty;
+        }
 …
+                }
                 postvisit( old, ty );
-                this->node = ty;
+        }
 …
+                }
                 postvisit( old, ty );
-                this->node = ty;
+        }
 …
+                }
                 postvisit( old, ty );
-                this->node = ty;
+        }
         virtual void visit( TupleType * old ) override final {
                 this->node = new ast::TupleType{
+                visitType( old, new ast::TupleType{
                         GET_ACCEPT_V( types, Type ),
                         // members generated by TupleType c'tor
                         cv( old )
                 };
+                } );
+        }
         virtual void visit( TypeofType * old ) override final {
                 this->node = new ast::TypeofType{
+                visitType( old, new ast::TypeofType{
                         GET_ACCEPT_1( expr, Expr ),
                         (ast::TypeofType::Kind)old->is_basetypeof,
                         cv( old )
                 };
+                } );
+        }
 …
         virtual void visit( VarArgsType * old ) override final {
                 this->node = new ast::VarArgsType{ cv( old ) };
+                visitType( old, new ast::VarArgsType{ cv( old ) } );
+        }
         virtual void visit( ZeroType * old ) override final {
                 this->node = new ast::ZeroType{ cv( old ) };
+                visitType( old, new ast::ZeroType{ cv( old ) } );
+        }
         virtual void visit( OneType * old ) override final {
                 this->node = new ast::OneType{ cv( old ) };
+        }
         virtual void visit( GlobalScopeType * ) override final {
                 this->node = new ast::GlobalScopeType{};
+                visitType( old, new ast::OneType{ cv( old ) } );
+        }
+        virtual void visit( GlobalScopeType * old ) override final {
+                visitType( old, new ast::GlobalScopeType{} );
+        }

src/AST/Expr.hpp

-                      r1e5dedc4
+                      r3c6e417
         ParamEntry() : decl( 0 ), declptr( nullptr ), actualType( nullptr ), formalType( nullptr ), expr( nullptr ) {}
+        ParamEntry( UniqueId id, Decl * declptr, Type* actual, Type* formal, Expr* e )
+        ParamEntry(
+                UniqueId id, const Decl * declptr, const Type * actual, const Type * formal,
+                const Expr * e )
         : decl( id ), declptr( declptr ), actualType( actual ), formalType( formal ), expr( e ) {}
 };
 …
                         case Params: return data.inferParams;
+                        }
+                        assert(!"unreachable");
                         return *((InferredParams*)nullptr);
+                }
 …
                         assert(!"Mode was not already Params");
                         return *((InferredParams*)nullptr);
+                }
+                void set_inferParams( InferredParams && ps ) {
+                        switch(mode) {
+                        case Slots:
+                                data.resnSlots.~ResnSlots();
+                                // fallthrough
+                        case Empty:
+                                new(&data.inferParams) InferredParams{ std::move( ps ) };
+                                mode = Params;
+                                break;
+                        case Params:
+                                data.inferParams = std::move( ps );
+                                break;
+                        }
+                }

src/AST/Type.hpp

-                      r1e5dedc4
+                      r3c6e417
 public:
         CV::Qualifiers qualifiers;
+        Type( CV::Qualifiers q = {} ) : qualifiers(q) {}
+        std::vector<ptr<Attribute>> attributes;
+        Type( CV::Qualifiers q = {}, std::vector<ptr<Attribute>> && as = {} )
+        : qualifiers(q), attributes(std::move(as)) {}
         bool is_const() const { return qualifiers.is_const; }
 …
         ForallList forall;
+        ParameterizedType( ForallList&& fs = {}, CV::Qualifiers q = {} )
+        : Type(q), forall(std::move(fs)) {}
+        ParameterizedType( CV::Qualifiers q ) : Type(q), forall() {}
+        ParameterizedType( ForallList&& fs = {}, CV::Qualifiers q = {},
+                std::vector<ptr<Attribute>> && as = {} )
+        : Type(q, std::move(as)), forall(std::move(fs)) {}
+        ParameterizedType( CV::Qualifiers q, std::vector<ptr<Attribute>> && as = {} )
+        : Type(q, std::move(as)), forall() {}
 private:
 …
 public:
         std::vector<ptr<Expr>> params;
-        std::vector<ptr<Attribute>> attributes;
         std::string name;
         bool hoistType = false;
 …
         ReferenceToType( const std::string& n, CV::Qualifiers q = {},
                 std::vector<ptr<Attribute>> && as = {} )
         : ParameterizedType(q), params(), attributes(std::move(as)), name(n) {}
+        : ParameterizedType(q, std::move(as)), params(), name(n) {}
         /// Gets aggregate declaration this type refers to

src/AST/TypeEnvironment.hpp

r1e5dedc4	r3c6e417
215	215	std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
216	216
217		}
	217	} // namespace ast
218	218
219	219	// Local Variables: //

src/AST/porting.md

-                      r1e5dedc4
+                      r3c6e417
 * `ExplodedActual.h` => `ExplodedArg.hpp`
+`polyCost`
+* switched order of `env`, `symtab` parameters for better consistency
+`findMinCost`
+* pulled out conversion cost promotion into separate `promoteCvtCost` function
+`resolveAssertions` => `satisfyAssertions`
+* `ResolveAssertions.h` => `SatisfyAssertions.hpp`
+* `Resn*` => `Sat*`
 [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes

src/ResolvExpr/AlternativeFinder.cc

-                      r1e5dedc4
+                      r3c6e417
+        }
-        const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
-                if ( expr->result.as< ast::ReferenceType >() ) {
-                        // cast away reference from expr
-                        cost.incReference();
-                        return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() };
+                }
-                return expr;
+        }
         template< typename InputIterator, typename OutputIterator >
         void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
 …
+        }
         /// Unique identifier for matching expression resolutions to their requesting expression
         UniqueId globalResnSlot = 0;
+        /// Unique identifier for matching expression resolutions to their requesting expression (located in CandidateFinder.cpp)
+        extern UniqueId globalResnSlot;
         template< typename OutputIterator >

src/ResolvExpr/Candidate.hpp

-                      r1e5dedc4
+                      r3c6e417
         : expr( x ), cost( Cost::zero ), cvtCost( Cost::zero ), env( e ), open(), need() {}
         Candidate( const Candidate & o, const ast::Expr * x )
         : expr( x ), cost( o.cost ), cvtCost( Cost::zero ), env( o.env ), open( o.open ),
+        Candidate( const Candidate & o, const ast::Expr * x, const Cost & addedCost = Cost::zero )
+        : expr( x ), cost( o.cost + addedCost ), cvtCost( Cost::zero ), env( o.env ), open( o.open ),
           need( o.need ) {}
+        Candidate(
+                const ast::Expr * x, const ast::TypeEnvironment & e, const ast::OpenVarSet & o,
+                const ast::AssertionSet & n, const Cost & c, const Cost & cvt = Cost::zero )
+        : expr( x ), cost( c ), cvtCost( cvt ), env( e ), open( o ), need( n.begin(), n.end() ) {}
         Candidate(

src/ResolvExpr/CandidateFinder.cpp

-                      r1e5dedc4
+                      r3c6e417
 #include "Cost.h"
 #include "ExplodedArg.hpp"
+#include "RenameVars.h"           // for renameTyVars
 #include "Resolver.h"
+#include "ResolveTypeof.h"
 #include "SatisfyAssertions.hpp"
 #include "typeops.h"              // for adjustExprType
+#include "typeops.h"              // for adjustExprType, conversionCost, polyCost, specCost
 #include "Unify.h"
 #include "AST/Expr.hpp"
 …
 #include "AST/Type.hpp"
 #include "SymTab/Mangler.h"
+#include "SymTab/Validate.h"      // for validateType
 #include "Tuples/Tuples.h"        // for handleTupleAssignment
 …
 namespace ResolvExpr {
+using std::move;
+/// partner to move that copies any copyable type
+template<typename T>
+T copy( const T & x ) { return x; }
+const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
+        if ( expr->result.as< ast::ReferenceType >() ) {
+                // cast away reference from expr
+                cost.incReference();
+                return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() };
+        }
+        return expr;
+}
+/// Unique identifier for matching expression resolutions to their requesting expression
+UniqueId globalResnSlot = 0;
+Cost computeConversionCost(
+        const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab,
+        const ast::TypeEnvironment & env
+) {
+        PRINT(
+                std::cerr << std::endl << "converting ";
+                ast::print( std::cerr, argType, 2 );
+                std::cerr << std::endl << " to ";
+                ast::print( std::cerr, paramType, 2 );
+                std::cerr << std::endl << "environment is: ";
+                ast::print( std::cerr, env, 2 );
+                std::cerr << std::endl;
+        )
+        Cost convCost = conversionCost( argType, paramType, symtab, env );
+        PRINT(
+                std::cerr << std::endl << "cost is " << convCost << std::endl;
+        )
+        if ( convCost == Cost::infinity ) return convCost;
+        convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
+        PRINT(
+                std::cerr << "cost with polycost is " << convCost << std::endl;
+        )
+        return convCost;
+}
 namespace {
         /// First index is which argument, second is which alternative, third is which exploded element
         using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
 …
+        }
+        /// Computes conversion cost for a given expression to a given type
+        const ast::Expr * computeExpressionConversionCost(
+                const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
+        ) {
+                Cost convCost = computeConversionCost( arg->result, paramType, symtab, env );
+                outCost += convCost;
+                // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
+                // conversion. Ignore poly cost for now, since this requires resolution of the cast to
+                // infer parameters and this does not currently work for the reason stated below
+                Cost tmpCost = convCost;
+                tmpCost.incPoly( -tmpCost.get_polyCost() );
+                if ( tmpCost != Cost::zero ) {
+                        ast::ptr< ast::Type > newType = paramType;
+                        env.apply( newType );
+                        return new ast::CastExpr{ arg->location, arg, newType };
+                        // xxx - *should* be able to resolve this cast, but at the moment pointers are not
+                        // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
+                        // once this is fixed it should be possible to resolve the cast.
+                        // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
+                        // but it shouldn't be because this makes the conversion from DT* to DT* since
+                        // commontype(zero_t, DT*) is DT*, rather than nothing
+                        // CandidateFinder finder{ symtab, env };
+                        // finder.find( arg, ResolvMode::withAdjustment() );
+                        // assertf( finder.candidates.size() > 0,
+                        //      "Somehow castable expression failed to find alternatives." );
+                        // assertf( finder.candidates.size() == 1,
+                        //      "Somehow got multiple alternatives for known cast expression." );
+                        // return finder.candidates.front()->expr;
+                }
+                return arg;
+        }
         /// Computes conversion cost for a given candidate
         Cost computeApplicationConversionCost(
                 const CandidateRef & cand, const ast::SymbolTable & symtab
+                CandidateRef cand, const ast::SymbolTable & symtab
         ) {
+                #warning unimplemented
+                (void)cand; (void)symtab;
+                assert(false);
+                return Cost::infinity;
+                auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
+                auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
+                auto function = pointer->base.strict_as< ast::FunctionType >();
+                Cost convCost = Cost::zero;
+                const auto & params = function->params;
+                auto param = params.begin();
+                auto & args = appExpr->args;
+                for ( unsigned i = 0; i < args.size(); ++i ) {
+                        const ast::Type * argType = args[i]->result;
+                        PRINT(
+                                std::cerr << "arg expression:" << std::endl;
+                                ast::print( std::cerr, args[i], 2 );
+                                std::cerr << "--- results are" << std::endl;
+                                ast::print( std::cerr, argType, 2 );
+                        )
+                        if ( param == params.end() ) {
+                                if ( function->isVarArgs ) {
+                                        convCost.incUnsafe();
+                                        PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
+                                                << convCost << std::endl; ; )
+                                        // convert reference-typed expressions into value-typed expressions
+                                        cand->expr = ast::mutate_field_index(
+                                                appExpr, &ast::ApplicationExpr::args, i,
+                                                referenceToRvalueConversion( args[i], convCost ) );
+                                        continue;
+                                } else return Cost::infinity;
+                        }
+                        if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
+                                // Default arguments should be free - don't include conversion cost.
+                                // Unwrap them here because they are not relevant to the rest of the system
+                                cand->expr = ast::mutate_field_index(
+                                        appExpr, &ast::ApplicationExpr::args, i, def->expr );
+                                ++param;
+                                continue;
+                        }
+                        // mark conversion cost and also specialization cost of param type
+                        const ast::Type * paramType = (*param)->get_type();
+                        cand->expr = ast::mutate_field_index(
+                                appExpr, &ast::ApplicationExpr::args, i,
+                                computeExpressionConversionCost(
+                                        args[i], paramType, symtab, cand->env, convCost ) );
+                        convCost.decSpec( specCost( paramType ) );
+                        ++param;  // can't be in for-loop update because of the continue
+                }
+                if ( param != params.end() ) return Cost::infinity;
+                // specialization cost of return types can't be accounted for directly, it disables
+                // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
+                //
+                //   forall(otype OS) {
+                //     void ?|?(OS&, int);  // with newline
+                //     OS&  ?|?(OS&, int);  // no newline, always chosen due to more specialization
+                //   }
+                // mark type variable and specialization cost of forall clause
+                convCost.incVar( function->forall.size() );
+                for ( const ast::TypeDecl * td : function->forall ) {
+                        convCost.decSpec( td->assertions.size() );
+                }
+                return convCost;
+        }
+        void makeUnifiableVars(
+                const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars,
+                ast::AssertionSet & need
+        ) {
+                for ( const ast::TypeDecl * tyvar : type->forall ) {
+                        unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar };
+                        for ( const ast::DeclWithType * assn : tyvar->assertions ) {
+                                need[ assn ].isUsed = true;
+                        }
+                }
+        }
+        /// Gets a default value from an initializer, nullptr if not present
+        const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
+                if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
+                        if ( auto ce = si->value.as< ast::CastExpr >() ) {
+                                return ce->arg.as< ast::ConstantExpr >();
+                        } else {
+                                return si->value.as< ast::ConstantExpr >();
+                        }
+                }
+                return nullptr;
+        }
+        /// State to iteratively build a match of parameter expressions to arguments
+        struct ArgPack {
+                std::size_t parent;          ///< Index of parent pack
+                ast::ptr< ast::Expr > expr;  ///< The argument stored here
+                Cost cost;                   ///< The cost of this argument
+                ast::TypeEnvironment env;    ///< Environment for this pack
+                ast::AssertionSet need;      ///< Assertions outstanding for this pack
+                ast::AssertionSet have;      ///< Assertions found for this pack
+                ast::OpenVarSet open;        ///< Open variables for this pack
+                unsigned nextArg;            ///< Index of next argument in arguments list
+                unsigned tupleStart;         ///< Number of tuples that start at this index
+                unsigned nextExpl;           ///< Index of next exploded element
+                unsigned explAlt;            ///< Index of alternative for nextExpl > 0
+                ArgPack()
+                : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
+                  tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
+                ArgPack(
+                        const ast::TypeEnvironment & env, const ast::AssertionSet & need,
+                        const ast::AssertionSet & have, const ast::OpenVarSet & open )
+                : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
+                  open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
+                ArgPack(
+                        std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,
+                        ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,
+                        unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,
+                        unsigned nextExpl = 0, unsigned explAlt = 0 )
+                : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ),
+                  have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
+                  nextExpl( nextExpl ), explAlt( explAlt ) {}
+                ArgPack(
+                        const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
+                        ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
+                : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ),
+                  need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ),
+                  tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
+                /// true if this pack is in the middle of an exploded argument
+                bool hasExpl() const { return nextExpl > 0; }
+                /// Gets the list of exploded candidates for this pack
+                const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {
+                        return args[ nextArg-1 ][ explAlt ];
+                }
+                /// Ends a tuple expression, consolidating the appropriate args
+                void endTuple( const std::vector< ArgPack > & packs ) {
+                        // add all expressions in tuple to list, summing cost
+                        std::deque< const ast::Expr * > exprs;
+                        const ArgPack * pack = this;
+                        if ( expr ) { exprs.emplace_front( expr ); }
+                        while ( pack->tupleStart == 0 ) {
+                                pack = &packs[pack->parent];
+                                exprs.emplace_front( pack->expr );
+                                cost += pack->cost;
+                        }
+                        // reset pack to appropriate tuple
+                        std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
+                        expr = new ast::TupleExpr{ expr->location, move( exprv ) };
+                        tupleStart = pack->tupleStart - 1;
+                        parent = pack->parent;
+                }
+        };
+        /// Instantiates an argument to match a parameter, returns false if no matching results left
+        bool instantiateArgument(
+                const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,
+                std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,
+                unsigned nTuples = 0
+        ) {
+                if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
+                        // paramType is a TupleType -- group args into a TupleExpr
+                        ++nTuples;
+                        for ( const ast::Type * type : *tupleType ) {
+                                // xxx - dropping initializer changes behaviour from previous, but seems correct
+                                // ^^^ need to handle the case where a tuple has a default argument
+                                if ( ! instantiateArgument(
+                                        type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
+                                nTuples = 0;
+                        }
+                        // re-constitute tuples for final generation
+                        for ( auto i = genStart; i < results.size(); ++i ) {
+                                results[i].endTuple( results );
+                        }
+                        return true;
+                } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
+                        // paramType is a ttype, consumes all remaining arguments
+                        // completed tuples; will be spliced to end of results to finish
+                        std::vector< ArgPack > finalResults{};
+                        // iterate until all results completed
+                        std::size_t genEnd;
+                        ++nTuples;
+                        do {
+                                genEnd = results.size();
+                                // add another argument to results
+                                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                                        unsigned nextArg = results[i].nextArg;
+                                        // use next element of exploded tuple if present
+                                        if ( results[i].hasExpl() ) {
+                                                const ExplodedArg & expl = results[i].getExpl( args );
+                                                unsigned nextExpl = results[i].nextExpl + 1;
+                                                if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
+                                                results.emplace_back(
+                                                        i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
+                                                        copy( results[i].need ), copy( results[i].have ),
+                                                        copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
+                                                        results[i].explAlt );
+                                                continue;
+                                        }
+                                        // finish result when out of arguments
+                                        if ( nextArg >= args.size() ) {
+                                                ArgPack newResult{
+                                                        results[i].env, results[i].need, results[i].have, results[i].open };
+                                                newResult.nextArg = nextArg;
+                                                const ast::Type * argType = nullptr;
+                                                if ( nTuples > 0 || ! results[i].expr ) {
+                                                        // first iteration or no expression to clone,
+                                                        // push empty tuple expression
+                                                        newResult.parent = i;
+                                                        std::vector< ast::ptr< ast::Expr > > emptyList;
+                                                        newResult.expr =
+                                                                new ast::TupleExpr{ CodeLocation{}, move( emptyList ) };
+                                                        argType = newResult.expr->result;
+                                                } else {
+                                                        // clone result to collect tuple
+                                                        newResult.parent = results[i].parent;
+                                                        newResult.cost = results[i].cost;
+                                                        newResult.tupleStart = results[i].tupleStart;
+                                                        newResult.expr = results[i].expr;
+                                                        argType = newResult.expr->result;
+                                                        if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
+                                                                // the case where a ttype value is passed directly is special,
+                                                                // e.g. for argument forwarding purposes
+                                                                // xxx - what if passing multiple arguments, last of which is
+                                                                //       ttype?
+                                                                // xxx - what would happen if unify was changed so that unifying
+                                                                //       tuple
+                                                                // types flattened both before unifying lists? then pass in
+                                                                // TupleType (ttype) below.
+                                                                --newResult.tupleStart;
+                                                        } else {
+                                                                // collapse leftover arguments into tuple
+                                                                newResult.endTuple( results );
+                                                                argType = newResult.expr->result;
+                                                        }
+                                                }
+                                                // check unification for ttype before adding to final
+                                                if (
+                                                        unify(
+                                                                ttype, argType, newResult.env, newResult.need, newResult.have,
+                                                                newResult.open, symtab )
+                                                ) {
+                                                        finalResults.emplace_back( move( newResult ) );
+                                                }
+                                                continue;
+                                        }
+                                        // add each possible next argument
+                                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
+                                                const ExplodedArg & expl = args[nextArg][j];
+                                                // fresh copies of parent parameters for this iteration
+                                                ast::TypeEnvironment env = results[i].env;
+                                                ast::OpenVarSet open = results[i].open;
+                                                env.addActual( expl.env, open );
+                                                // skip empty tuple arguments by (nearly) cloning parent into next gen
+                                                if ( expl.exprs.empty() ) {
+                                                        results.emplace_back(
+                                                                results[i], move( env ), copy( results[i].need ),
+                                                                copy( results[i].have ), move( open ), nextArg + 1, expl.cost );
+                                                        continue;
+                                                }
+                                                // add new result
+                                                results.emplace_back(
+                                                        i, expl.exprs.front(), move( env ), copy( results[i].need ),
+                                                        copy( results[i].have ), move( open ), nextArg + 1, nTuples,
+                                                        expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
+                                        }
+                                }
+                                // reset for next round
+                                genStart = genEnd;
+                                nTuples = 0;
+                        } while ( genEnd != results.size() );
+                        // splice final results onto results
+                        for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
+                                results.emplace_back( move( finalResults[i] ) );
+                        }
+                        return ! finalResults.empty();
+                }
+                // iterate each current subresult
+                std::size_t genEnd = results.size();
+                for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                        unsigned nextArg = results[i].nextArg;
+                        // use remainder of exploded tuple if present
+                        if ( results[i].hasExpl() ) {
+                                const ExplodedArg & expl = results[i].getExpl( args );
+                                const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
+                                ast::TypeEnvironment env = results[i].env;
+                                ast::AssertionSet need = results[i].need, have = results[i].have;
+                                ast::OpenVarSet open = results[i].open;
+                                const ast::Type * argType = expr->result;
+                                PRINT(
+                                        std::cerr << "param type is ";
+                                        ast::print( std::cerr, paramType );
+                                        std::cerr << std::endl << "arg type is ";
+                                        ast::print( std::cerr, argType );
+                                        std::cerr << std::endl;
+                                )
+                                if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
+                                        unsigned nextExpl = results[i].nextExpl + 1;
+                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
+                                        results.emplace_back(
+                                                i, expr, move( env ), move( need ), move( have ), move( open ), nextArg,
+                                                nTuples, Cost::zero, nextExpl, results[i].explAlt );
+                                }
+                                continue;
+                        }
+                        // use default initializers if out of arguments
+                        if ( nextArg >= args.size() ) {
+                                if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
+                                        ast::TypeEnvironment env = results[i].env;
+                                        ast::AssertionSet need = results[i].need, have = results[i].have;
+                                        ast::OpenVarSet open = results[i].open;
+                                        if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) {
+                                                results.emplace_back(
+                                                        i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ),
+                                                        move( need ), move( have ), move( open ), nextArg, nTuples );
+                                        }
+                                }
+                                continue;
+                        }
+                        // Check each possible next argument
+                        for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
+                                const ExplodedArg & expl = args[nextArg][j];
+                                // fresh copies of parent parameters for this iteration
+                                ast::TypeEnvironment env = results[i].env;
+                                ast::AssertionSet need = results[i].need, have = results[i].have;
+                                ast::OpenVarSet open = results[i].open;
+                                env.addActual( expl.env, open );
+                                // skip empty tuple arguments by (nearly) cloning parent into next gen
+                                if ( expl.exprs.empty() ) {
+                                        results.emplace_back(
+                                                results[i], move( env ), move( need ), move( have ), move( open ),
+                                                nextArg + 1, expl.cost );
+                                        continue;
+                                }
+                                // consider only first exploded arg
+                                const ast::Expr * expr = expl.exprs.front();
+                                const ast::Type * argType = expr->result;
+                                PRINT(
+                                        std::cerr << "param type is ";
+                                        ast::print( std::cerr, paramType );
+                                        std::cerr << std::endl << "arg type is ";
+                                        ast::print( std::cerr, argType );
+                                        std::cerr << std::endl;
+                                )
+                                // attempt to unify types
+                                if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
+                                        // add new result
+                                        results.emplace_back(
+                                                i, expr, move( env ), move( need ), move( have ), move( open ),
+                                                nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
+                                }
+                        }
+                }
+                // reset for next parameter
+                genStart = genEnd;
+                return genEnd != results.size();
+        }
+        /// Generate a cast expression from `arg` to `toType`
+        const ast::Expr * restructureCast(
+                ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast
+        ) {
+                if (
+                        arg->result->size() > 1
+                        && ! toType->isVoid()
+                        && ! dynamic_cast< const ast::ReferenceType * >( toType )
+                ) {
+                        // Argument is a tuple and the target type is neither void nor a reference. Cast each
+                        // member of the tuple to its corresponding target type, producing the tuple of those
+                        // cast expressions. If there are more components of the tuple than components in the
+                        // target type, then excess components do not come out in the result expression (but
+                        // UniqueExpr ensures that the side effects will still be produced)
+                        if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
+                                // expressions which may contain side effects require a single unique instance of
+                                // the expression
+                                arg = new ast::UniqueExpr{ arg->location, arg };
+                        }
+                        std::vector< ast::ptr< ast::Expr > > components;
+                        for ( unsigned i = 0; i < toType->size(); ++i ) {
+                                // cast each component
+                                ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };
+                                components.emplace_back(
+                                        restructureCast( idx, toType->getComponent( i ), isGenerated ) );
+                        }
+                        return new ast::TupleExpr{ arg->location, move( components ) };
+                } else {
+                        // handle normally
+                        return new ast::CastExpr{ arg->location, arg, toType, isGenerated };
+                }
+        }
+        /// Gets the name from an untyped member expression (must be NameExpr)
+        const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {
+                if ( memberExpr->member.as< ast::ConstantExpr >() ) {
+                        SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
+                }
+                return memberExpr->member.strict_as< ast::NameExpr >()->name;
+        }
 …
+                }
+                /// Set up candidate assertions for inference
+                void inferParameters( CandidateRef & newCand, CandidateList & out ) {
+                        // Set need bindings for any unbound assertions
+                        UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
+                        for ( auto & assn : newCand->need ) {
+                                // skip already-matched assertions
+                                if ( assn.second.resnSlot != 0 ) continue;
+                                // assign slot for expression if needed
+                                if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
+                                // fix slot to assertion
+                                assn.second.resnSlot = crntResnSlot;
+                        }
+                        // pair slot to expression
+                        if ( crntResnSlot != 0 ) {
+                                newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
+                        }
+                        // add to output list; assertion satisfaction will occur later
+                        out.emplace_back( newCand );
+                }
+                /// Completes a function candidate with arguments located
+                void validateFunctionCandidate(
+                        const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
+                        CandidateList & out
+                ) {
+                        ast::ApplicationExpr * appExpr =
+                                new ast::ApplicationExpr{ func->expr->location, func->expr };
+                        // sum cost and accumulate arguments
+                        std::deque< const ast::Expr * > args;
+                        Cost cost = func->cost;
+                        const ArgPack * pack = &result;
+                        while ( pack->expr ) {
+                                args.emplace_front( pack->expr );
+                                cost += pack->cost;
+                                pack = &results[pack->parent];
+                        }
+                        std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
+                        appExpr->args = move( vargs );
+                        // build and validate new candidate
+                        auto newCand =
+                                std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
+                        PRINT(
+                                std::cerr << "instantiate function success: " << appExpr << std::endl;
+                                std::cerr << "need assertions:" << std::endl;
+                                ast::print( std::cerr, result.need, 2 );
+                        )
+                        inferParameters( newCand, out );
+                }
                 /// Builds a list of candidates for a function, storing them in out
                 void makeFunctionCandidates(
 …
                         const ExplodedArgs_new & args, CandidateList & out
                 ) {
+                        #warning unimplemented
+                        (void)func; (void)funcType; (void)args; (void)out;
+                        assert(false);
+                        ast::OpenVarSet funcOpen;
+                        ast::AssertionSet funcNeed, funcHave;
+                        ast::TypeEnvironment funcEnv{ func->env };
+                        makeUnifiableVars( funcType, funcOpen, funcNeed );
+                        // add all type variables as open variables now so that those not used in the parameter
+                        // list are still considered open
+                        funcEnv.add( funcType->forall );
+                        if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
+                                // attempt to narrow based on expected target type
+                                const ast::Type * returnType = funcType->returns.front()->get_type();
+                                if ( ! unify(
+                                        returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
+                                ) {
+                                        // unification failed, do not pursue this candidate
+                                        return;
+                                }
+                        }
+                        // iteratively build matches, one parameter at a time
+                        std::vector< ArgPack > results;
+                        results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
+                        std::size_t genStart = 0;
+                        for ( const ast::DeclWithType * param : funcType->params ) {
+                                auto obj = strict_dynamic_cast< const ast::ObjectDecl * >( param );
+                                // Try adding the arguments corresponding to the current parameter to the existing
+                                // matches
+                                if ( ! instantiateArgument(
+                                        obj->type, obj->init, args, results, genStart, symtab ) ) return;
+                        }
+                        if ( funcType->isVarArgs ) {
+                                // append any unused arguments to vararg pack
+                                std::size_t genEnd;
+                                do {
+                                        genEnd = results.size();
+                                        // iterate results
+                                        for ( std::size_t i = genStart; i < genEnd; ++i ) {
+                                                unsigned nextArg = results[i].nextArg;
+                                                // use remainder of exploded tuple if present
+                                                if ( results[i].hasExpl() ) {
+                                                        const ExplodedArg & expl = results[i].getExpl( args );
+                                                        unsigned nextExpl = results[i].nextExpl + 1;
+                                                        if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
+                                                        results.emplace_back(
+                                                                i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
+                                                                copy( results[i].need ), copy( results[i].have ),
+                                                                copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
+                                                                results[i].explAlt );
+                                                        continue;
+                                                }
+                                                // finish result when out of arguments
+                                                if ( nextArg >= args.size() ) {
+                                                        validateFunctionCandidate( func, results[i], results, out );
+                                                        continue;
+                                                }
+                                                // add each possible next argument
+                                                for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
+                                                        const ExplodedArg & expl = args[nextArg][j];
+                                                        // fresh copies of parent parameters for this iteration
+                                                        ast::TypeEnvironment env = results[i].env;
+                                                        ast::OpenVarSet open = results[i].open;
+                                                        env.addActual( expl.env, open );
+                                                        // skip empty tuple arguments by (nearly) cloning parent into next gen
+                                                        if ( expl.exprs.empty() ) {
+                                                                results.emplace_back(
+                                                                        results[i], move( env ), copy( results[i].need ),
+                                                                        copy( results[i].have ), move( open ), nextArg + 1,
+                                                                        expl.cost );
+                                                                continue;
+                                                        }
+                                                        // add new result
+                                                        results.emplace_back(
+                                                                i, expl.exprs.front(), move( env ), copy( results[i].need ),
+                                                                copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost,
+                                                                expl.exprs.size() == 1 ? 0 : 1, j );
+                                                }
+                                        }
+                                        genStart = genEnd;
+                                } while( genEnd != results.size() );
+                        } else {
+                                // filter out the results that don't use all the arguments
+                                for ( std::size_t i = genStart; i < results.size(); ++i ) {
+                                        ArgPack & result = results[i];
+                                        if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
+                                                validateFunctionCandidate( func, result, results, out );
+                                        }
+                                }
+                        }
+                }
                 /// Adds implicit struct-conversions to the alternative list
                 void addAnonConversions( const CandidateRef & cand ) {
+                        #warning unimplemented
+                        (void)cand;
+                        assert(false);
+                        // adds anonymous member interpretations whenever an aggregate value type is seen.
+                        // it's okay for the aggregate expression to have reference type -- cast it to the
+                        // base type to treat the aggregate as the referenced value
+                        ast::ptr< ast::Expr > aggrExpr( cand->expr );
+                        ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;
+                        cand->env.apply( aggrType );
+                        if ( aggrType.as< ast::ReferenceType >() ) {
+                                aggrExpr =
+                                        new ast::CastExpr{ aggrExpr->location, aggrExpr, aggrType->stripReferences() };
+                        }
+                        if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
+                                addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
+                        } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
+                                addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
+                        }
+                }
+                /// Adds aggregate member interpretations
+                void addAggMembers(
+                        const ast::ReferenceToType * aggrInst, const ast::Expr * expr,
+                        const Candidate & cand, const Cost & addedCost, const std::string & name
+                ) {
+                        for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
+                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
+                                CandidateRef newCand = std::make_shared<Candidate>(
+                                        cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
+                                // add anonymous member interpretations whenever an aggregate value type is seen
+                                // as a member expression
+                                addAnonConversions( newCand );
+                                candidates.emplace_back( move( newCand ) );
+                        }
+                }
+                /// Adds tuple member interpretations
+                void addTupleMembers(
+                        const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
+                        const Cost & addedCost, const ast::Expr * member
+                ) {
+                        if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
+                                // get the value of the constant expression as an int, must be between 0 and the
+                                // length of the tuple to have meaning
+                                long long val = constantExpr->intValue();
+                                if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
+                                        addCandidate(
+                                                cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },
+                                                addedCost );
+                                }
+                        }
+                }
 …
                                         funcE.emplace_back( *func, symtab );
+                                }
                                 argExpansions.emplace_front( std::move( funcE ) );
+                                argExpansions.emplace_front( move( funcE ) );
                                 for ( const CandidateRef & op : opFinder ) {
 …
                                 if ( cvtCost != Cost::infinity ) {
                                         withFunc->cvtCost = cvtCost;
                                         candidates.emplace_back( std::move( withFunc ) );
+                                }
+                        }
                         found = std::move( candidates );
+                                        candidates.emplace_back( move( withFunc ) );
+                                }
+                        }
+                        found = move( candidates );
                         // use a new list so that candidates are not examined by addAnonConversions twice
 …
                 void postvisit( const ast::CastExpr * castExpr ) {
+                        #warning unimplemented
+                        (void)castExpr;
+                        assert(false);
+                        ast::ptr< ast::Type > toType = castExpr->result;
+                        assert( toType );
+                        toType = resolveTypeof( toType, symtab );
+                        toType = SymTab::validateType( toType, symtab );
+                        toType = adjustExprType( toType, tenv, symtab );
+                        CandidateFinder finder{ symtab, tenv, toType };
+                        finder.find( castExpr->arg, ResolvMode::withAdjustment() );
+                        CandidateList matches;
+                        for ( CandidateRef & cand : finder.candidates ) {
+                                ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
+                                ast::OpenVarSet open( cand->open );
+                                cand->env.extractOpenVars( open );
+                                // It is possible that a cast can throw away some values in a multiply-valued
+                                // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the
+                                // subexpression results that are cast directly. The candidate is invalid if it
+                                // has fewer results than there are types to cast to.
+                                int discardedValues = cand->expr->result->size() - toType->size();
+                                if ( discardedValues < 0 ) continue;
+                                // unification run for side-effects
+                                unify( toType, cand->expr->result, cand->env, need, have, open, symtab );
+                                Cost thisCost = castCost( cand->expr->result, toType, symtab, cand->env );
+                                PRINT(
+                                        std::cerr << "working on cast with result: " << toType << std::endl;
+                                        std::cerr << "and expr type: " << cand->expr->result << std::endl;
+                                        std::cerr << "env: " << cand->env << std::endl;
+                                )
+                                if ( thisCost != Cost::infinity ) {
+                                        PRINT(
+                                                std::cerr << "has finite cost." << std::endl;
+                                        )
+                                        // count one safe conversion for each value that is thrown away
+                                        thisCost.incSafe( discardedValues );
+                                        CandidateRef newCand = std::make_shared<Candidate>(
+                                                restructureCast( cand->expr, toType, castExpr->isGenerated ),
+                                                copy( cand->env ), move( open ), move( need ), cand->cost,
+                                                cand->cost + thisCost );
+                                        inferParameters( newCand, matches );
+                                }
+                        }
+                        // select first on argument cost, then conversion cost
+                        CandidateList minArgCost = findMinCost( matches );
+                        promoteCvtCost( minArgCost );
+                        candidates = findMinCost( minArgCost );
+                }
 …
                         for ( CandidateRef & r : finder.candidates ) {
                                 addCandidate(
+                                        *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
+                                        *r,
+                                        new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
+                        }
+                }
                 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
+                        #warning unimplemented
+                        (void)memberExpr;
+                        assert(false);
+                        CandidateFinder aggFinder{ symtab, tenv };
+                        aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
+                        for ( CandidateRef & agg : aggFinder.candidates ) {
+                                // it's okay for the aggregate expression to have reference type -- cast it to the
+                                // base type to treat the aggregate as the referenced value
+                                Cost addedCost = Cost::zero;
+                                agg->expr = referenceToRvalueConversion( agg->expr, addedCost );
+                                // find member of the given type
+                                if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {
+                                        addAggMembers(
+                                                structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
+                                } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
+                                        addAggMembers(
+                                                unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
+                                } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {
+                                        addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );
+                                }
+                        }
+                }
 …
+                }
+                void postvisit( const ast::NameExpr * variableExpr ) {
+                        #warning unimplemented
+                        (void)variableExpr;
+                        assert(false);
+                void postvisit( const ast::NameExpr * nameExpr ) {
+                        std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name );
+                        PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
+                        for ( auto & data : declList ) {
+                                Cost cost = Cost::zero;
+                                ast::Expr * newExpr = data.combine( nameExpr->location, cost );
+                                CandidateRef newCand = std::make_shared<Candidate>(
+                                        newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
+                                        cost );
+                                PRINT(
+                                        std::cerr << "decl is ";
+                                        ast::print( std::cerr, data.id );
+                                        std::cerr << std::endl;
+                                        std::cerr << "newExpr is ";
+                                        ast::print( std::cerr, newExpr );
+                                        std::cerr << std::endl;
+                                )
+                                newCand->expr = ast::mutate_field(
+                                        newCand->expr.get(), &ast::Expr::result,
+                                        renameTyVars( newCand->expr->result ) );
+                                // add anonymous member interpretations whenever an aggregate value type is seen
+                                // as a name expression
+                                addAnonConversions( newCand );
+                                candidates.emplace_back( move( newCand ) );
+                        }
+                }
 …
                 void postvisit( const ast::SizeofExpr * sizeofExpr ) {
+                        #warning unimplemented
+                        (void)sizeofExpr;
+                        assert(false);
+                        if ( sizeofExpr->type ) {
+                                addCandidate(
+                                        new ast::SizeofExpr{
+                                                sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) },
+                                        tenv );
+                        } else {
+                                // find all candidates for the argument to sizeof
+                                CandidateFinder finder{ symtab, tenv };
+                                finder.find( sizeofExpr->expr );
+                                // find the lowest-cost candidate, otherwise ambiguous
+                                CandidateList winners = findMinCost( finder.candidates );
+                                if ( winners.size() != 1 ) {
+                                        SemanticError(
+                                                sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );
+                                }
+                                // return the lowest-cost candidate
+                                CandidateRef & choice = winners.front();
+                                choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
+                                choice->cost = Cost::zero;
+                                addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );
+                        }
+                }
                 void postvisit( const ast::AlignofExpr * alignofExpr ) {
+                        #warning unimplemented
+                        (void)alignofExpr;
+                        assert(false);
+                        if ( alignofExpr->type ) {
+                                addCandidate(
+                                        new ast::AlignofExpr{
+                                                alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) },
+                                        tenv );
+                        } else {
+                                // find all candidates for the argument to alignof
+                                CandidateFinder finder{ symtab, tenv };
+                                finder.find( alignofExpr->expr );
+                                // find the lowest-cost candidate, otherwise ambiguous
+                                CandidateList winners = findMinCost( finder.candidates );
+                                if ( winners.size() != 1 ) {
+                                        SemanticError(
+                                                alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );
+                                }
+                                // return the lowest-cost candidate
+                                CandidateRef & choice = winners.front();
+                                choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
+                                choice->cost = Cost::zero;
+                                addCandidate(
+                                        *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
+                        }
+                }
                 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
+                        #warning unimplemented
+                        (void)offsetofExpr;
+                        assert(false);
+                        const ast::ReferenceToType * aggInst;
+                        if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;
+                        else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;
+                        else return;
+                        for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {
+                                auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );
+                                addCandidate(
+                                        new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
+                        }
+                }
 …
                                                 new ast::LogicalExpr{
                                                         logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
+                                                std::move( env ), std::move( open ), std::move( need ),
+                                                r1->cost + r2->cost );
+                                                move( env ), move( open ), move( need ), r1->cost + r2->cost );
+                                }
+                        }
 …
                                                                 common )
                                                 ) {
+                                                        #warning unimplemented
+                                                        assert(false);
+                                                        // generate typed expression
+                                                        ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{
+                                                                conditionalExpr->location, r1->expr, r2->expr, r3->expr };
+                                                        newExpr->result = common ? common : r2->expr->result;
+                                                        // convert both options to result type
+                                                        Cost cost = r1->cost + r2->cost + r3->cost;
+                                                        newExpr->arg2 = computeExpressionConversionCost(
+                                                                newExpr->arg2, newExpr->result, symtab, env, cost );
+                                                        newExpr->arg3 = computeExpressionConversionCost(
+                                                                newExpr->arg3, newExpr->result, symtab, env, cost );
+                                                        // output candidate
+                                                        CandidateRef newCand = std::make_shared<Candidate>(
+                                                                newExpr, move( env ), move( open ), move( need ), cost );
+                                                        inferParameters( newCand, candidates );
+                                                }
+                                        }
 …
                                                         common )
                                         ) {
+                                                // generate new expression
                                                 ast::RangeExpr * newExpr =
                                                         new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
                                                 newExpr->result = common ? common : r1->expr->result;
+                                                #warning unimplemented
+                                                assert(false);
+                                                // add candidate
+                                                CandidateRef newCand = std::make_shared<Candidate>(
+                                                        newExpr, move( env ), move( open ), move( need ),
+                                                        r1->cost + r2->cost );
+                                                inferParameters( newCand, candidates );
+                                        }
+                                }
 …
                                 addCandidate(
                                         new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
                                         std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
+                                        new ast::TupleExpr{ tupleExpr->location, move( exprs ) },
+                                        move( env ), move( open ), move( need ), sumCost( subs ) );
+                        }
+                }
 …
                 void postvisit( const ast::StmtExpr * stmtExpr ) {
+                        #warning unimplemented
+                        (void)stmtExpr;
+                        assert(false);
+                        addCandidate( resolveStmtExpr( stmtExpr, symtab ), tenv );
+                }
                 void postvisit( const ast::UntypedInitExpr * initExpr ) {
+                        #warning unimplemented
+                        (void)initExpr;
+                        assert(false);
+                        // handle each option like a cast
+                        CandidateList matches;
+                        PRINT(
+                                std::cerr << "untyped init expr: " << initExpr << std::endl;
+                        )
+                        // O(n^2) checks of d-types with e-types
+                        for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) {
+                                // calculate target type
+                                const ast::Type * toType = resolveTypeof( initAlt.type, symtab );
+                                toType = SymTab::validateType( toType, symtab );
+                                toType = adjustExprType( toType, tenv, symtab );
+                                // The call to find must occur inside this loop, otherwise polymorphic return
+                                // types are not bound to the initialization type, since return type variables are
+                                // only open for the duration of resolving the UntypedExpr.
+                                CandidateFinder finder{ symtab, tenv, toType };
+                                finder.find( initExpr->expr, ResolvMode::withAdjustment() );
+                                for ( CandidateRef & cand : finder.candidates ) {
+                                        ast::TypeEnvironment env{ cand->env };
+                                        ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
+                                        ast::OpenVarSet open{ cand->open };
+                                        PRINT(
+                                                std::cerr << "  @ " << toType << " " << initAlt.designation << std::endl;
+                                        )
+                                        // It is possible that a cast can throw away some values in a multiply-valued
+                                        // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of
+                                        // the subexpression results that are cast directly. The candidate is invalid
+                                        // if it has fewer results than there are types to cast to.
+                                        int discardedValues = cand->expr->result->size() - toType->size();
+                                        if ( discardedValues < 0 ) continue;
+                                        // unification run for side-effects
+                                        unify( toType, cand->expr->result, env, need, have, open, symtab );
+                                        Cost thisCost = castCost( cand->expr->result, toType, symtab, env );
+                                        if ( thisCost != Cost::infinity ) {
+                                                // count one safe conversion for each value that is thrown away
+                                                thisCost.incSafe( discardedValues );
+                                                CandidateRef newCand = std::make_shared<Candidate>(
+                                                        new ast::InitExpr{
+                                                                initExpr->location, restructureCast( cand->expr, toType ),
+                                                                initAlt.designation },
+                                                        copy( cand->env ), move( open ), move( need ), cand->cost, thisCost );
+                                                inferParameters( newCand, matches );
+                                        }
+                                }
+                        }
+                        // select first on argument cost, then conversion cost
+                        CandidateList minArgCost = findMinCost( matches );
+                        promoteCvtCost( minArgCost );
+                        candidates = findMinCost( minArgCost );
+                }
 …
                         cand->env.applyFree( newResult );
                         cand->expr = ast::mutate_field(
                                 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
+                                cand->expr.get(), &ast::Expr::result, move( newResult ) );
                         out.emplace_back( cand );
 …
                 CandidateList satisfied;
                 std::vector< std::string > errors;
                 for ( auto & candidate : candidates ) {
                         satisfyAssertions( *candidate, symtab, satisfied, errors );
+                for ( CandidateRef & candidate : candidates ) {
+                        satisfyAssertions( candidate, symtab, satisfied, errors );
+                }
 …
                 // reset candidates
                 candidates = std::move( satisfied );
+                candidates = move( satisfied );
+        }
 …
                 auto oldsize = candidates.size();
                 candidates = std::move( pruned );
+                candidates = move( pruned );
                 PRINT(

src/ResolvExpr/CandidateFinder.hpp

-                      r1e5dedc4
+                      r3c6e417
 /// Data to perform expression resolution
 struct CandidateFinder {
         CandidateList candidates;                ///< List of candidate resolutions
         const ast::SymbolTable & symtab;         ///< Symbol table to lookup candidates
         const ast::TypeEnvironment & env;        ///< Substitutions performed in this resolution
         ast::ptr< ast::Type > targetType = nullptr;  ///< Target type for resolution
+        CandidateList candidates;          ///< List of candidate resolutions
+        const ast::SymbolTable & symtab;   ///< Symbol table to lookup candidates
+        const ast::TypeEnvironment & env;  ///< Substitutions performed in this resolution
+        ast::ptr< ast::Type > targetType;  ///< Target type for resolution
+        CandidateFinder( const ast::SymbolTable & symtab, const ast::TypeEnvironment & env )
+        : candidates(), symtab( symtab ), env( env ) {}
+        CandidateFinder(
+                const ast::SymbolTable & symtab, const ast::TypeEnvironment & env,
+                const ast::Type * tt = nullptr )
+        : candidates(), symtab( symtab ), env( env ), targetType( tt ) {}
         /// Fill candidates with feasible resolutions for `expr`
 …
 };
+/// Computes conversion cost between two types
+Cost computeConversionCost(
+        const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab,
+        const ast::TypeEnvironment & env );
 } // namespace ResolvExpr

src/ResolvExpr/CastCost.cc

-                      r1e5dedc4
+                      r3c6e417
                         });
                 } else {
+                        PassVisitor<CastCost> converter( dest, indexer, env, castCost );
+                        #warning cast on castCost artifact of having two functions, remove when port done
+                        PassVisitor<CastCost> converter(
+                                dest, indexer, env,
+                                (Cost (*)( Type *, Type *, const SymTab::Indexer &, const TypeEnvironment & ))
+                                        castCost );
                         src->accept( converter );
                         if ( converter.pass.get_cost() == Cost::infinity ) {
 …
+                }
+        }
+        Cost castCost(
+                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
+                const ast::TypeEnvironment & env
+        ) {
+                #warning unimplmented
+                (void)src; (void)dst; (void)symtab; (void)env;
+                assert(false);
+                return Cost::zero;
+        }
 } // namespace ResolvExpr

src/ResolvExpr/ConversionCost.cc

-                      r1e5dedc4
+                      r3c6e417
                         });
                 } else {
+                        PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
+                        PassVisitor<ConversionCost> converter(
+                                dest, indexer, env,
+                                (Cost (*)(Type*, Type*, const SymTab::Indexer&, const TypeEnvironment&))
+                                        conversionCost );
                         src->accept( converter );
                         if ( converter.pass.get_cost() == Cost::infinity ) {
 …
                         } else {
                                 PRINT( std::cerr << "reference to rvalue conversion" << std::endl; )
+                                PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
+                                PassVisitor<ConversionCost> converter(
+                                        dest, indexer, env,
+                                        (Cost (*)(Type*, Type*, const SymTab::Indexer&, const TypeEnvironment&))
+                                                conversionCost );
                                 src->accept( converter );
                                 return converter.pass.get_cost();
 …
                 } // if
+        }
+        Cost conversionCost(
+                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
+                const ast::TypeEnvironment & env
+        ) {
+                #warning unimplemented
+                (void)src; (void)dst; (void)symtab; (void)env;
+                assert(false);
+                return Cost::zero;
+        }
 } // namespace ResolvExpr

src/ResolvExpr/PolyCost.cc

-                      r1e5dedc4
+                      r3c6e417
 // Author           : Richard C. Bilson
 // Created On       : Sun May 17 09:50:12 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Sun May 17 09:52:02 2015
 // Update Count     : 3
+// Last Modified By : Andrew Beach
+// Last Modified On : Wed Jun 19 10:45:00 2019
+// Update Count     : 4
 //
+#include "AST/SymbolTable.hpp"
+#include "AST/Type.hpp"
+#include "AST/TypeEnvironment.hpp"
 #include "Common/PassVisitor.h"
 #include "SymTab/Indexer.h"   // for Indexer
 …
+        }
+// TODO: When the old PolyCost is torn out get rid of the _new suffix.
+struct PolyCost_new {
+        int result;
+        const ast::SymbolTable &symtab;
+        const ast::TypeEnvironment &env_;
+        PolyCost_new( const ast::SymbolTable & symtab, const ast::TypeEnvironment & env ) :
+                result( 0 ), symtab( symtab ), env_( env ) {}
+        void previsit( const ast::TypeInstType * type ) {
+                if ( const ast::EqvClass * eqv = env_.lookup( type->name ) ) /* && */ if ( eqv->bound ) {
+                        if ( const ast::TypeInstType * otherType = eqv->bound.as< ast::TypeInstType >() ) {
+                                if ( symtab.lookupType( otherType->name ) ) {
+                                        // Bound to opaque type.
+                                        result += 1;
+                                }
+                        } else {
+                                // Bound to concrete type.
+                                result += 1;
+                        }
+                }
+        }
+};
+int polyCost(
+        const ast::Type * type, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env
+) {
+        ast::Pass<PolyCost_new> costing( symtab, env );
+        type->accept( costing );
+        return costing.pass.result;
+}
 } // namespace ResolvExpr

src/ResolvExpr/RenameVars.cc

-                      r1e5dedc4
+                      r3c6e417
+                }
         } // namespace
+        const ast::Type * renameTyVars( const ast::Type * t ) {
+                #warning unimplemented; make sure resetTyVarRenaming() updated when implemented
+                (void)t;
+                assert(false);
+                return t;
+        }
 } // namespace ResolvExpr

src/ResolvExpr/RenameVars.h

-                      r1e5dedc4
+                      r3c6e417
 #include "SynTree/Visitor.h"  // for Visitor
+namespace ast {
+        class Type;
+}
 namespace ResolvExpr {
         /// Provides a consistent renaming of forall type names in a hierarchy by prefixing them with a unique "level" ID
         void renameTyVars( Type * );
+        const ast::Type * renameTyVars( const ast::Type * );
         /// resets internal state of renamer to avoid overflow

src/ResolvExpr/ResolveAssertions.cc

-                      r1e5dedc4
+                      r3c6e417
         using InferCache = std::unordered_map< UniqueId, InferredParams >;
+        /// Lexicographically-ordered vector of costs
+        using CostVec = std::vector< Cost >;
+        int compare( const CostVec & a, const CostVec & b ) {
+                unsigned i = 0;
+                do {
+                        // lex-compare where shorter one is less
+                        if ( i == a.size() ) {
+                                return i == b.size() ? 0 : -1;
+                        }
+                        if ( i == b.size() /* && i < a.size() */ ) return 1;
+                        int c = a[i].compare( b[i] );
+                        if ( c != 0 ) return c;
+                } while ( ++i );
+                assert(!"unreachable");
+        }
+        bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; }
         /// Flag for state iteration
         enum IterateFlag { IterateState };
 …
                 DeferList deferred;        ///< Deferred matches
                 InferCache inferred;       ///< Cache of already-inferred parameters
+                CostVec costs;             ///< Costs of recursive assertion satisfaction for disambiguation
                 SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
                 /// Initial resolution state for an alternative
                 ResnState( Alternative& a, SymTab::Indexer& indexer )
                 : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
+                : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, indexer(indexer) {
                         need.swap( a.need );
+                }
 …
                 ResnState( ResnState&& o, IterateFlag )
                 : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
+                  inferred(std::move(o.inferred)), indexer(o.indexer) {}
+                  inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) {
+                        costs.emplace_back( Cost::zero );
+                }
         };
 …
         };
+        void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
+                PassVisitor<InferMatcher> matcher{ inferred };
+                alt.expr = alt.expr->acceptMutator( matcher );
+                out.emplace_back( alt );
+        /// Map of alternative return types to recursive assertion satisfaction costs
+        using PruneMap = std::unordered_map<std::string, CostVec>;
+        /// Gets the pruning key for an alternative
+        std::string pruneKey( const Alternative & alt ) {
+                Type* resType = alt.expr->result->clone();
+                alt.env.apply( resType );
+                std::string resKey = SymTab::Mangler::mangleType( resType );
+                delete resType;
+                return std::move( resKey );
+        }
+        /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning
+        /// threshold.
+        void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) {
+                // prune if cheaper alternative for same key has already been generated
+                std::string resKey = pruneKey( resn.alt );
+                auto it = pruneThresholds.find( resKey );
+                if ( it != pruneThresholds.end() ) {
+                        if ( it->second < resn.costs ) return;
+                } else {
+                        pruneThresholds.emplace_hint( it, resKey, resn.costs );
+                }
+                // replace resolution slots with inferred params, add to output
+                PassVisitor<InferMatcher> matcher{ resn.inferred };
+                resn.alt.expr = resn.alt.expr->acceptMutator( matcher );
+                out.emplace_back( resn.alt );
+        }
 …
                 ResnList resns{ ResnState{ alt, root_indexer } };
                 ResnList new_resns{};
+                // Pruning thresholds by result type of the output alternatives.
+                // Alternatives *should* be generated in sorted order, so no need to retroactively prune
+                PruneMap thresholds;
                 // resolve assertions in breadth-first-order up to a limited number of levels deep
 …
                         // scan over all mutually-compatible resolutions
                         for ( auto& resn : resns ) {
+                                // stop this branch if already found a better option
+                                auto it = thresholds.find( pruneKey( resn.alt ) );
+                                if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn;
                                 // make initial pass at matching assertions
                                 for ( auto& assn : resn.need ) {
 …
                                         // either add successful match or push back next state
                                         if ( resn.newNeed.empty() ) {
                                                 finalizeAssertions( resn.alt, resn.inferred, out );
+                                                finalizeAssertions( resn, thresholds, out );
                                         } else {
                                                 new_resns.emplace_back( std::move(resn), IterateState );
 …
                                                 goto nextResn;
+                                        }
                                         // sort by cost
+                                        // sort by cost for overall pruning
                                         CandidateCost coster{ resn.indexer };
                                         std::sort( compatible.begin(), compatible.end(), coster );
-                                        // keep map of detected options
-                                        std::unordered_map<std::string, Cost> found;
                                         for ( auto& compat : compatible ) {
-                                                // filter by environment-adjusted result type, keep only cheapest option
-                                                Type* resType = alt.expr->result->clone();
-                                                compat.env.apply( resType );
-                                                // skip if cheaper alternative already processed with same result type
-                                                Cost resCost = coster.get( compat );
-                                                auto it = found.emplace( SymTab::Mangler::mangleType( resType ), resCost );
-                                                delete resType;
-                                                if ( it.second == false && it.first->second < resCost ) continue;
-                                                // proceed with resolution step
                                                 ResnState new_resn = resn;
 …
                                                 new_resn.alt.openVars = std::move(compat.openVars);
+                                                // mark cost of this path
+                                                new_resn.costs.back() += compat.cost;
                                                 // either add sucessful match or push back next state
                                                 if ( new_resn.newNeed.empty() ) {
                                                         finalizeAssertions( new_resn.alt, new_resn.inferred, out );
+                                                        finalizeAssertions( new_resn, thresholds, out );
                                                 } else {
                                                         new_resns.emplace_back( std::move(new_resn), IterateState );

src/ResolvExpr/ResolveTypeof.cc

-                      r1e5dedc4
+                      r3c6e417
                 return newType;
+        }
+        const ast::Type * resolveTypeof( const ast::Type * type , const ast::SymbolTable & symtab ) {
+                #warning unimplemented
+                (void)type; (void)symtab;
+                assert(false);
+                return nullptr;
+        }
 } // namespace ResolvExpr

src/ResolvExpr/ResolveTypeof.h

-                      r1e5dedc4
+                      r3c6e417
 class Indexer;
 }  // namespace SymTab
+namespace ast {
+        class Type;
+        class SymbolTable;
+}
 namespace ResolvExpr {
         Type *resolveTypeof( Type*, const SymTab::Indexer &indexer );
+        const ast::Type * resolveTypeof( const ast::Type *, const ast::SymbolTable & );
 } // namespace ResolvExpr

src/ResolvExpr/Resolver.cc

-                      r1e5dedc4
+                      r3c6e417
         void resolve( std::list< ast::ptr<ast::Decl> >& translationUnit ) {
                 ast::Pass<Resolver_new> resolver;
+                ast::Pass< Resolver_new > resolver;
                 accept_all( translationUnit, resolver );
+        }
+        ast::ptr< ast::Expr > resolveStmtExpr(
+                const ast::StmtExpr * stmtExpr, const ast::SymbolTable & symtab
+        ) {
+                assert( stmtExpr );
+                ast::Pass< Resolver_new > resolver{ symtab };
+                ast::ptr< ast::Expr > ret = stmtExpr;
+                ret = ret->accept( resolver );
+                strict_dynamic_cast< ast::StmtExpr * >( ret.get_and_mutate() )->computeResult();
+                return ret;
+        }

src/ResolvExpr/Resolver.h

-                      r1e5dedc4
+                      r3c6e417
         class Decl;
         class DeletedExpr;
+        class StmtExpr;
         class SymbolTable;
         class TypeEnvironment;
 …
         ast::ptr< ast::Expr > resolveInVoidContext(
                 const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env );
+        /// Resolves a statement expression
+        ast::ptr< ast::Expr > resolveStmtExpr(
+                const ast::StmtExpr * stmtExpr, const ast::SymbolTable & symtab );
 } // namespace ResolvExpr

src/ResolvExpr/SatisfyAssertions.cpp

-                      r1e5dedc4
+                      r3c6e417
 #include "SatisfyAssertions.hpp"
+#include <algorithm>
 #include <cassert>
+#include <sstream>
+#include <string>
+#include <unordered_map>
+#include <vector>
+#include "Candidate.hpp"
+#include "CandidateFinder.hpp"
+#include "Cost.h"
+#include "RenameVars.h"
+#include "typeops.h"
+#include "Unify.h"
+#include "AST/Decl.hpp"
+#include "AST/Expr.hpp"
+#include "AST/Node.hpp"
+#include "AST/Pass.hpp"
+#include "AST/Print.hpp"
+#include "AST/SymbolTable.hpp"
+#include "AST/TypeEnvironment.hpp"
+#include "Common/FilterCombos.h"
+#include "Common/Indenter.h"
+#include "GenPoly/GenPoly.h"
+#include "SymTab/Mangler.h"
 namespace ResolvExpr {
+// in CandidateFinder.cpp; unique ID for assertion satisfaction
+extern UniqueId globalResnSlot;
+namespace {
+        /// Post-unification assertion satisfaction candidate
+        struct AssnCandidate {
+                ast::SymbolTable::IdData cdata;  ///< Satisfying declaration
+                ast::ptr< ast::Type > adjType;   ///< Satisfying type
+                ast::TypeEnvironment env;        ///< Post-unification environment
+                ast::AssertionSet have;          ///< Post-unification have-set
+                ast::AssertionSet need;          ///< Post-unification need-set
+                ast::OpenVarSet open;            ///< Post-unification open-var-set
+                ast::UniqueId resnSlot;          ///< Slot for any recursive assertion IDs
+                AssnCandidate(
+                        const ast::SymbolTable::IdData c, const ast::Type * at, ast::TypeEnvironment && e,
+                        ast::AssertionSet && h, ast::AssertionSet && n, ast::OpenVarSet && o, ast::UniqueId rs )
+                : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ),
+                  need( std::move( n ) ), open( std::move( o ) ), resnSlot( rs ) {}
+        };
+        /// List of assertion satisfaction candidates
+        using AssnCandidateList = std::vector< AssnCandidate >;
+        /// Reference to a single deferred item
+        struct DeferRef {
+                const ast::DeclWithType * decl;
+                const ast::AssertionSetValue & info;
+                const AssnCandidate & match;
+        };
+        /// Wrapper for the deferred items from a single assertion satisfaction.
+        /// Acts like an indexed list of DeferRef
+        struct DeferItem {
+                const ast::DeclWithType * decl;
+                const ast::AssertionSetValue & info;
+                AssnCandidateList matches;
+                DeferItem(
+                        const ast::DeclWithType * d, const ast::AssertionSetValue & i, AssnCandidateList && ms )
+                : decl( d ), info( i ), matches( std::move( ms ) ) {}
+                bool empty() const { return matches.empty(); }
+                AssnCandidateList::size_type size() const { return matches.size(); }
+                DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; }
+        };
+        /// List of deferred satisfaction items
+        using DeferList = std::vector< DeferItem >;
+        /// Set of assertion satisfactions, grouped by resolution ID
+        using InferCache = std::unordered_map< ast::UniqueId, ast::InferredParams >;
+        /// Lexicographically-ordered vector of costs.
+        /// Lexicographic order comes from default operator< on std::vector.
+        using CostVec = std::vector< Cost >;
+        /// Flag for state iteration
+        enum IterateFlag { IterateState };
+        /// Intermediate state for satisfying a set of assertions
+        struct SatState {
+                CandidateRef cand;          ///< Candidate assertion is rooted on
+                ast::AssertionList need;    ///< Assertions to find
+                ast::AssertionSet newNeed;  ///< Recursive assertions from current satisfied assertions
+                DeferList deferred;         ///< Deferred matches
+                InferCache inferred;        ///< Cache of already-inferred assertions
+                CostVec costs;              ///< Disambiguating costs of recursive assertion satisfaction
+                ast::SymbolTable symtab;    ///< Name lookup (depends on previous assertions)
+                /// Initial satisfaction state for a candidate
+                SatState( CandidateRef & c, const ast::SymbolTable & syms )
+                : cand( c ), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero },
+                  symtab( syms ) { need.swap( c->need ); }
+                /// Update satisfaction state for next step after previous state
+                SatState( SatState && o, IterateFlag )
+                : cand( std::move( o.cand ) ), need( o.newNeed.begin(), o.newNeed.end() ), newNeed(),
+                  deferred(), inferred( std::move( o.inferred ) ), costs( std::move( o.costs ) ),
+                  symtab( o.symtab ) { costs.emplace_back( Cost::zero ); }
+                /// Field-wise next step constructor
+                SatState(
+                        CandidateRef && c, ast::AssertionSet && nn, InferCache && i, CostVec && cs,
+                        ast::SymbolTable && syms )
+                : cand( std::move( c ) ), need( nn.begin(), nn.end() ), newNeed(), deferred(),
+                  inferred( std::move( i ) ), costs( std::move( cs ) ), symtab( std::move( syms ) )
+                  { costs.emplace_back( Cost::zero ); }
+        };
+        /// Adds a captured assertion to the symbol table
+        void addToSymbolTable( const ast::AssertionSet & have, ast::SymbolTable & symtab ) {
+                for ( auto & i : have ) {
+                        if ( i.second.isUsed ) { symtab.addId( i.first ); }
+                }
+        }
+        /// Binds a single assertion, updating satisfaction state
+        void bindAssertion(
+                const ast::DeclWithType * decl, const ast::AssertionSetValue & info, CandidateRef & cand,
+                AssnCandidate & match, InferCache & inferred
+        ) {
+                const ast::DeclWithType * candidate = match.cdata.id;
+                assertf( candidate->uniqueId,
+                        "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
+                ast::Expr * varExpr = match.cdata.combine( cand->expr->location, cand->cvtCost );
+                varExpr->result = match.adjType;
+                if ( match.resnSlot ) { varExpr->inferred.resnSlots().emplace_back( match.resnSlot ); }
+                // place newly-inferred assertion in proper location in cache
+                inferred[ info.resnSlot ][ decl->uniqueId ] = ast::ParamEntry{
+                        candidate->uniqueId, candidate, match.adjType, decl->get_type(), varExpr };
+        }
+        /// Satisfy a single assertion
+        bool satisfyAssertion( ast::AssertionList::value_type & assn, SatState & sat ) {
+                // skip unused assertions
+                if ( ! assn.second.isUsed ) return true;
+                // find candidates that unify with the desired type
+                AssnCandidateList matches;
+                for ( const ast::SymbolTable::IdData & cdata : sat.symtab.lookupId( assn.first->name ) ) {
+                        const ast::DeclWithType * candidate = cdata.id;
+                        // build independent unification context for candidate
+                        ast::AssertionSet have, newNeed;
+                        ast::TypeEnvironment newEnv{ sat.cand->env };
+                        ast::OpenVarSet newOpen{ sat.cand->open };
+                        ast::ptr< ast::Type > toType = assn.first->get_type();
+                        ast::ptr< ast::Type > adjType =
+                                renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ) );
+                        // only keep candidates which unify
+                        if ( unify( toType, adjType, newEnv, newNeed, have, newOpen, sat.symtab ) ) {
+                                // set up binding slot for recursive assertions
+                                ast::UniqueId crntResnSlot = 0;
+                                if ( ! newNeed.empty() ) {
+                                        crntResnSlot = ++globalResnSlot;
+                                        for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; }
+                                }
+                                matches.emplace_back(
+                                        cdata, adjType, std::move( newEnv ), std::move( newNeed ), std::move( have ),
+                                        std::move( newOpen ), crntResnSlot );
+                        }
+                }
+                // break if no satisfying match
+                if ( matches.empty() ) return false;
+                // defer if too many satisfying matches
+                if ( matches.size() > 1 ) {
+                        sat.deferred.emplace_back( assn.first, assn.second, std::move( matches ) );
+                        return true;
+                }
+                // otherwise bind unique match in ongoing scope
+                AssnCandidate & match = matches.front();
+                addToSymbolTable( match.have, sat.symtab );
+                sat.newNeed.insert( match.need.begin(), match.need.end() );
+                sat.cand->env = std::move( match.env );
+                sat.cand->open = std::move( match.open );
+                bindAssertion( assn.first, assn.second, sat.cand, match, sat.inferred );
+                return true;
+        }
+        /// Map of candidate return types to recursive assertion satisfaction costs
+        using PruneMap = std::unordered_map< std::string, CostVec >;
+        /// Gets the pruning key for a candidate (derived from environment-adjusted return type)
+        std::string pruneKey( const Candidate & cand ) {
+                ast::ptr< ast::Type > resType = cand.expr->result;
+                cand.env.apply( resType );
+                return Mangle::mangle( resType, Mangle::typeMode() );
+        }
+        /// Associates inferred parameters with an expression
+        struct InferMatcher final {
+                InferCache & inferred;
+                InferMatcher( InferCache & inferred ) : inferred( inferred ) {}
+                const ast::Expr * postmutate( const ast::Expr * expr ) {
+                        // Skip if no slots to find
+                        if ( expr->inferred.mode != ast::Expr::InferUnion::Slots ) return expr;
+                        // find inferred parameters for resolution slots
+                        ast::InferredParams newInferred;
+                        for ( UniqueId slot : expr->inferred.resnSlots() ) {
+                                // fail if no matching assertions found
+                                auto it = inferred.find( slot );
+                                if ( it == inferred.end() ) {
+                                        assert(!"missing assertion");
+                                }
+                                // place inferred parameters into new map
+                                for ( auto & entry : it->second ) {
+                                        // recurse on inferParams of resolved expressions
+                                        entry.second.expr = postmutate( entry.second.expr );
+                                        auto res = newInferred.emplace( entry );
+                                        assert( res.second && "all assertions newly placed" );
+                                }
+                        }
+                        ast::Expr * ret = mutate( expr );
+                        ret->inferred.set_inferParams( std::move( newInferred ) );
+                        return ret;
+                }
+        };
+        /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning
+        /// threshold.
+        void finalizeAssertions(
+                CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs,
+                CandidateList & out
+        ) {
+                // prune if cheaper alternative for same key has already been generated
+                std::string key = pruneKey( *cand );
+                auto it = thresholds.find( key );
+                if ( it != thresholds.end() ) {
+                        if ( it->second < costs ) return;
+                } else {
+                        thresholds.emplace_hint( it, key, std::move( costs ) );
+                }
+                // replace resolution slots with inferred parameters, add to output
+                ast::Pass< InferMatcher > matcher{ inferred };
+                cand->expr = cand->expr->accept( matcher );
+                out.emplace_back( cand );
+        }
+        /// Combo iterator that combines candidates into an output list, merging their environments.
+        /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h`
+        /// for description of "combo iterator".
+        class CandidateEnvMerger {
+                /// Current list of merged candidates
+                std::vector< DeferRef > crnt;
+                /// Stack of environments to support backtracking
+                std::vector< ast::TypeEnvironment > envs;
+                /// Stack of open variables to support backtracking
+                std::vector< ast::OpenVarSet > opens;
+                /// Symbol table to use for merges
+                const ast::SymbolTable & symtab;
+        public:
+                /// The merged environment/open variables and the list of candidates
+                struct OutType {
+                        ast::TypeEnvironment env;
+                        ast::OpenVarSet open;
+                        std::vector< DeferRef > assns;
+                        Cost cost;
+                        OutType(
+                                const ast::TypeEnvironment & e, const ast::OpenVarSet & o,
+                                const std::vector< DeferRef > & as, const ast::SymbolTable & symtab )
+                        : env( e ), open( o ), assns( as ), cost( Cost::zero ) {
+                                // compute combined conversion cost
+                                for ( const DeferRef & assn : assns ) {
+                                        // compute conversion cost from satisfying decl to assertion
+                                        cost += computeConversionCost(
+                                                assn.match.adjType, assn.decl->get_type(), symtab, env );
+                                        // mark vars+specialization on function-type assertions
+                                        const ast::FunctionType * func =
+                                                GenPoly::getFunctionType( assn.match.cdata.id->get_type() );
+                                        if ( ! func ) continue;
+                                        for ( const ast::DeclWithType * param : func->params ) {
+                                                cost.decSpec( specCost( param->get_type() ) );
+                                        }
+                                        cost.incVar( func->forall.size() );
+                                        for ( const ast::TypeDecl * td : func->forall ) {
+                                                cost.decSpec( td->assertions.size() );
+                                        }
+                                }
+                        }
+                        bool operator< ( const OutType & o ) const { return cost < o.cost; }
+                };
+                CandidateEnvMerger(
+                        const ast::TypeEnvironment & env, const ast::OpenVarSet & open,
+                        const ast::SymbolTable & syms )
+                : crnt(), envs{ env }, opens{ open }, symtab( syms ) {}
+                bool append( DeferRef i ) {
+                        ast::TypeEnvironment env = envs.back();
+                        ast::OpenVarSet open = opens.back();
+                        mergeOpenVars( open, i.match.open );
+                        if ( ! env.combine( i.match.env, open, symtab ) ) return false;
+                        crnt.emplace_back( i );
+                        envs.emplace_back( std::move( env ) );
+                        opens.emplace_back( std::move( open ) );
+                        return true;
+                }
+                void backtrack() {
+                        crnt.pop_back();
+                        envs.pop_back();
+                        opens.pop_back();
+                }
+                OutType finalize() { return { envs.back(), opens.back(), crnt, symtab }; }
+        };
+        /// Limit to depth of recursion of assertion satisfaction
+        static const int recursionLimit = 4;
+        /// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of
+        static const int deferLimit = 10;
+} // anonymous namespace
 void satisfyAssertions(
         Candidate & alt, const ast::SymbolTable & symtab, CandidateList & out,
+        CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
         std::vector<std::string> & errors
 ) {
+        #warning unimplemented
+        (void)alt; (void)symtab; (void)out; (void)errors;
+        assert(false);
+        // finish early if no assertions to satisfy
+        if ( cand->need.empty() ) {
+                out.emplace_back( cand );
+                return;
+        }
+        // build list of possible combinations of satisfying declarations
+        std::vector< SatState > sats{ SatState{ cand, symtab } };
+        std::vector< SatState > nextSats{};
+        // pruning thresholds by result type of output candidates.
+        // Candidates *should* be generated in sorted order, so no need to retroactively prune
+        PruneMap thresholds;
+        // satisfy assertions in breadth-first order over the recursion tree of assertion satisfaction.
+        // Stop recursion at a limited number of levels deep to avoid infinite loops.
+        for ( unsigned level = 0; level < recursionLimit; ++level ) {
+                // for each current mutually-compatible set of assertions
+                for ( SatState & sat : sats ) {
+                        // stop this branch if a better option is already found
+                        auto it = thresholds.find( pruneKey( *sat.cand ) );
+                        if ( it != thresholds.end() && it->second < sat.costs ) goto nextSat;
+                        // make initial pass at matching assertions
+                        for ( auto & assn : sat.need ) {
+                                // fail early if any assertion is not satisfiable
+                                if ( ! satisfyAssertion( assn, sat ) ) {
+                                        Indenter tabs{ 3 };
+                                        std::ostringstream ss;
+                                        ss << tabs << "Unsatisfiable alternative:\n";
+                                        print( ss, *sat.cand, ++tabs );
+                                        ss << (tabs-1) << "Could not satisfy assertion:\n";
+                                        ast::print( ss, assn.first, tabs );
+                                        errors.emplace_back( ss.str() );
+                                        goto nextSat;
+                                }
+                        }
+                        if ( sat.deferred.empty() ) {
+                                // either add successful match or push back next state
+                                if ( sat.newNeed.empty() ) {
+                                        finalizeAssertions(
+                                                sat.cand, sat.inferred, thresholds, std::move( sat.costs ), out );
+                                } else {
+                                        nextSats.emplace_back( std::move( sat ), IterateState );
+                                }
+                        } else if ( sat.deferred.size() > deferLimit ) {
+                                // too many deferred assertions to attempt mutual compatibility
+                                Indenter tabs{ 3 };
+                                std::ostringstream ss;
+                                ss << tabs << "Unsatisfiable alternative:\n";
+                                print( ss, *sat.cand, ++tabs );
+                                ss << (tabs-1) << "Too many non-unique satisfying assignments for assertions:\n";
+                                for ( const auto & d : sat.deferred ) {
+                                        ast::print( ss, d.decl, tabs );
+                                }
+                                errors.emplace_back( ss.str() );
+                                goto nextSat;
+                        } else {
+                                // combine deferred assertions by mutual compatibility
+                                std::vector< CandidateEnvMerger::OutType > compatible = filterCombos(
+                                        sat.deferred, CandidateEnvMerger{ sat.cand->env, sat.cand->open, sat.symtab } );
+                                // fail early if no mutually-compatible assertion satisfaction
+                                if ( compatible.empty() ) {
+                                        Indenter tabs{ 3 };
+                                        std::ostringstream ss;
+                                        ss << tabs << "Unsatisfiable alternative:\n";
+                                        print( ss, *sat.cand, ++tabs );
+                                        ss << (tabs-1) << "No mutually-compatible satisfaction for assertions:\n";
+                                        for ( const auto& d : sat.deferred ) {
+                                                ast::print( ss, d.decl, tabs );
+                                        }
+                                        errors.emplace_back( ss.str() );
+                                        goto nextSat;
+                                }
+                                // sort by cost (for overall pruning order)
+                                std::sort( compatible.begin(), compatible.end() );
+                                // process mutually-compatible combinations
+                                for ( auto & compat : compatible ) {
+                                        // set up next satisfaction state
+                                        CandidateRef nextCand = std::make_shared<Candidate>(
+                                                sat.cand->expr, std::move( compat.env ), std::move( compat.open ),
+                                                ast::AssertionSet{} /* need moved into satisfaction state */,
+                                                sat.cand->cost, sat.cand->cvtCost );
+                                        ast::AssertionSet nextNewNeed{ sat.newNeed };
+                                        InferCache nextInferred{ sat.inferred };
+                                        CostVec nextCosts{ sat.costs };
+                                        nextCosts.back() += compat.cost;
+                                        ast::SymbolTable nextSymtab{ sat.symtab };
+                                        // add compatible assertions to new satisfaction state
+                                        for ( DeferRef r : compat.assns ) {
+                                                AssnCandidate match = r.match;
+                                                addToSymbolTable( match.have, nextSymtab );
+                                                nextNewNeed.insert( match.need.begin(), match.need.end() );
+                                                bindAssertion( r.decl, r.info, nextCand, match, nextInferred );
+                                        }
+                                        // either add successful match or push back next state
+                                        if ( nextNewNeed.empty() ) {
+                                                finalizeAssertions(
+                                                        nextCand, nextInferred, thresholds, std::move( nextCosts ), out );
+                                        } else {
+                                                nextSats.emplace_back(
+                                                        std::move( nextCand ), std::move( nextNewNeed ),
+                                                        std::move( nextInferred ), std::move( nextCosts ),
+                                                        std::move( nextSymtab ) );
+                                        }
+                                }
+                        }
+                nextSat:; }
+                // finish or reset for next round
+                if ( nextSats.empty() ) return;
+                sats.swap( nextSats );
+                nextSats.clear();
+        }
+        // exceeded recursion limit if reaches here
+        if ( out.empty() ) {
+                SemanticError( cand->expr->location, "Too many recursive assertions" );
+        }
+}

src/ResolvExpr/SatisfyAssertions.hpp

r1e5dedc4	r3c6e417
29	29	/// Recursively satisfies all assertions provided in a candidate; returns true if succeeds
30	30	void satisfyAssertions(
31		Candidate ~~& alt~~, const ast::SymbolTable & symtab, CandidateList & out,
	31	CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
32	32	std::vector<std::string> & errors );
33	33

src/ResolvExpr/SpecCost.cc

-                      r1e5dedc4
+                      r3c6e417
 // Author           : Aaron B. Moss
 // Created On       : Tue Oct 02 15:50:00 2018
 // Last Modified By : Aaron B. Moss
 // Last Modified On : Tue Oct 02 15:50:00 2018
 // Update Count     : 1
+// Last Modified By : Andrew Beach
+// Last Modified On : Wed Jun 19 10:43:00 2019
+// Update Count     : 2
 //
 #include <limits>
 #include <list>
+#include <type_traits>
+#include "AST/Pass.hpp"
+#include "AST/Type.hpp"
 #include "Common/PassVisitor.h"
 #include "SynTree/Declaration.h"
 …
                         visit_children = false;
+                }
         private:
                 // returns minimum non-negative count + 1 over type parameters (-1 if none such)
 …
                         visit_children = false;
+                }
                 // look for polymorphic parameters
                 void previsit(UnionInstType* uty) {
 …
                 return counter.pass.get_count();
+        }
+namespace {
+        /// The specialization counter inner class.
+        class SpecCounter : public ast::WithShortCircuiting, public ast::WithVisitorRef<SpecCounter> {
+                int count = -1;  ///< specialization count (-1 for none)
+                // Converts the max value to -1 (none), otherwise increments the value.
+                static int toNoneOrInc( int value ) {
+                        assert( 0 <= value );
+                        return value < std::numeric_limits<int>::max() ? value + 1 : -1;
+                }
+                template<typename T> using MapperT =
+                        typename std::add_pointer<ast::Type const *(typename T::value_type const &)>::type;
+                // Update the minimum to the new lowest non-none value.
+                template<typename T>
+                void updateMinimumPresent( int & minimum, const T & list, MapperT<T> mapper ) {
+                        for ( const auto & node : list ) {
+                                count = -1;
+                                mapper( node )->accept( *visitor );
+                                if ( count != -1 && count < minimum ) minimum = count;
+                        }
+                }
+                // Returns minimum non-negative count + 1 over type parameters (-1 if none such).
+                template<typename T>
+                int minimumPresent( const T & list, MapperT<T> mapper ) {
+                        int minCount = std::numeric_limits<int>::max();
+                        updateMinimumPresent( minCount, list, mapper );
+                        return toNoneOrInc( minCount );
+                }
+                // The three mappers:
+                static const ast::Type * decl_type( const ast::ptr< ast::DeclWithType > & decl ) {
+                        return decl->get_type();
+                }
+                static const ast::Type * expr_result( const ast::ptr< ast::Expr > & expr ) {
+                        return expr->result;
+                }
+                static const ast::Type * type_deref( const ast::ptr< ast::Type > & type ) {
+                        return type.get();
+                }
+        public:
+                int get_count() const { return 0 <= count ? count : 0; }
+                // Mark specialization of base type.
+                void postvisit( const ast::PointerType * ) { if ( count >= 0 ) ++count; }
+                void postvisit( const ast::ArrayType * ) { if ( count >= 0 ) ++count; }
+                void postvisit( const ast::ReferenceType * ) { if ( count >= 0 ) ++count; }
+                // Use the minimal specialization value over returns and params.
+                void previsit( const ast::FunctionType * fty ) {
+                        int minCount = std::numeric_limits<int>::max();
+                        updateMinimumPresent( minCount, fty->params, decl_type );
+                        updateMinimumPresent( minCount, fty->returns, decl_type );
+                        // Add another level to minCount if set.
+                        count = toNoneOrInc( minCount );
+                        // We have already visited children.
+                        visit_children = false;
+                }
+                // Look for polymorphic parameters.
+                void previsit( const ast::StructInstType * sty ) {
+                        count = minimumPresent( sty->params, expr_result );
+                        visit_children = false;
+                }
+                // Look for polymorphic parameters.
+                void previsit( const ast::UnionInstType * uty ) {
+                        count = minimumPresent( uty->params, expr_result );
+                        visit_children = false;
+                }
+                // Note polymorphic type (which may be specialized).
+                // xxx - maybe account for open/closed type variables
+                void postvisit( const ast::TypeInstType * ) { count = 0; }
+                // Use the minimal specialization over elements.
+                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
+                void previsit( const ast::TupleType * tty ) {
+                        count = minimumPresent( tty->types, type_deref );
+                        visit_children = false;
+                }
+        };
+} // namespace
+int specCost( const ast::Type * type ) {
+        if ( nullptr == type ) {
+                return 0;
+        }
+        ast::Pass<SpecCounter> counter;
+        type->accept( *counter.pass.visitor );
+        return counter.pass.get_count();
+}
 } // namespace ResolvExpr

src/ResolvExpr/typeops.h

-                      r1e5dedc4
+                      r3c6e417
         // in CastCost.cc
         Cost castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env );
+        Cost castCost(
+                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
+                const ast::TypeEnvironment & env );
         // in ConversionCost.cc
         Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env );
+        Cost conversionCost(
+                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
+                const ast::TypeEnvironment & env );
         // in AlternativeFinder.cc
 …
         // in PolyCost.cc
         int polyCost( Type *type, const TypeEnvironment &env, const SymTab::Indexer &indexer );
+        int polyCost(
+                const ast::Type * type, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env );
         // in SpecCost.cc
         int specCost( Type *type );
+        int specCost( const ast::Type * type );
         // in Occurs.cc
 …
         // in AlternativeFinder.cc
         void referenceToRvalueConversion( Expression *& expr, Cost & cost );
+        // in CandidateFinder.cpp
         const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost );

src/SymTab/Mangler.h

r1e5dedc4	r3c6e417
101	101	using Mode = bitfield<mangle_flags>;
102	102
	103	static inline Mode typeMode() { return NoOverrideable \| Type; }
	104
103	105	/// Mangle declaration name
104	106	std::string mangle( const ast::Node * decl, Mode mode = {} );

src/SymTab/Validate.cc

-                      r1e5dedc4
+                      r3c6e417
                 return addrExpr;
+        }
+        const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab ) {
+                #warning unimplemented
+                (void)type; (void)symtab;
+                assert(false);
+                return nullptr;
+        }
 } // namespace SymTab

src/SymTab/Validate.h

-                      r1e5dedc4
+                      r3c6e417
 class Type;
+namespace ast {
+        class Type;
+        class SymbolTable;
+}
 namespace SymTab {
         class Indexer;
 …
         void validate( std::list< Declaration * > &translationUnit, bool doDebug = false );
         void validateType( Type *type, const Indexer *indexer );
+        const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab );
 } // namespace SymTab

src/Tuples/Tuples.cc

-                      r1e5dedc4
+                      r3c6e417
 // Created On       : Mon Jun 17 14:41:00 2019
 // Last Modified By : Andrew Beach
 // Last Modified On : Wed Jun 12 15:43:00 2019
 // Update Count     : 0
+// Last Modified On : Tue Jun 18  9:31:00 2019
+// Update Count     : 1
 //
 …
         /// impure.
     struct ImpurityDetector : public ast::WithShortCircuiting {
-                ImpurityDetector( bool ignoreUnique ) : ignoreUnique( ignoreUnique ) {}
                 bool maybeImpure = false;
-                bool ignoreUnique;
                 void previsit( ast::ApplicationExpr const * appExpr ) {
-                        visit_children = false;
                         if ( ast::DeclWithType const * function = InitTweak::getFunction( appExpr ) ) {
                                 if ( function->linkage == ast::Linkage::Intrinsic
                                                 && ( function->name == "*?" || function->name == "?[?]" ) ) {
-                                        visit_children = true;
                                         return;
+                                }
+                        }
                         maybeImpure = true;
+                        maybeImpure = true; visit_children = false;
+                }
                 void previsit( ast::UntypedExpr const * ) {
                         maybeImpure = true; visit_children = false;
+                }
+        };
+        struct ImpurityDetectorIgnoreUnique : public ImpurityDetector {
                 void previsit( ast::UniqueExpr const * ) {
+                        if ( ignoreUnique ) {
+                                visit_children = false;
+                        }
+                        visit_children = false;
+                }
         };
+        bool detectImpurity( const ast::Expr * expr, bool ignoreUnique ) {
+                ast::Pass<ImpurityDetector> detector( ignoreUnique );
+        template<typename Detector>
+        bool detectImpurity( const ast::Expr * expr ) {
+                ast::Pass<Detector> detector;
                 expr->accept( detector );
                 return detector.pass.maybeImpure;
 …
 } // namespace
+bool maybeImpure( const ast::Expr * expr ) {
+        return detectImpurity<ImpurityDetector>( expr );
+}
 bool maybeImpureIgnoreUnique( const ast::Expr * expr ) {
         return detectImpurity( expr, true );
+        return detectImpurity<ImpurityDetectorIgnoreUnique>( expr );
+}

src/Tuples/Tuples.h

-                      r1e5dedc4
+                      r3c6e417
 // Created On       : Mon May 18 07:44:20 2015
 // Last Modified By : Andrew Beach
 // Last Modified On : Wed Jun 12 10:39:00 2017
 // Update Count     : 17
+// Last Modified On : Tue Jun 18 09:36:00 2019
+// Update Count     : 18
 //
 …
         /// returns true if the expression may contain side-effects.
         bool maybeImpure( Expression * expr );
+        bool maybeImpure( const ast::Expr * expr );
         /// Returns true if the expression may contain side-effect,

Context Navigation

Legend:

doc/papers/concurrency/Paper.tex

libcfa/src/clock.hfa

src/AST/Convert.cpp

src/AST/Expr.hpp

src/AST/Type.hpp

src/AST/TypeEnvironment.hpp

src/AST/porting.md

src/ResolvExpr/AlternativeFinder.cc

src/ResolvExpr/Candidate.hpp

src/ResolvExpr/CandidateFinder.cpp

src/ResolvExpr/CandidateFinder.hpp

src/ResolvExpr/CastCost.cc

src/ResolvExpr/ConversionCost.cc

src/ResolvExpr/PolyCost.cc

src/ResolvExpr/RenameVars.cc

src/ResolvExpr/RenameVars.h

src/ResolvExpr/ResolveAssertions.cc

src/ResolvExpr/ResolveTypeof.cc

src/ResolvExpr/ResolveTypeof.h

src/ResolvExpr/Resolver.cc

src/ResolvExpr/Resolver.h

src/ResolvExpr/SatisfyAssertions.cpp

src/ResolvExpr/SatisfyAssertions.hpp

src/ResolvExpr/SpecCost.cc

src/ResolvExpr/typeops.h

src/SymTab/Mangler.h

src/SymTab/Validate.cc

src/SymTab/Validate.h

src/Tuples/Tuples.cc

src/Tuples/Tuples.h

Download in other formats: