Changeset ea3fa25


Ignore:
Timestamp:
Nov 2, 2020, 10:05:40 AM (3 years ago)
Author:
m3zulfiq <m3zulfiq@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
55acc3a, f7136f7
Parents:
45444c3 (diff), 6a036eb (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

Files:
3 added
21 edited

Legend:

Unmodified
Added
Removed

  • benchmark/readyQ/cycle.cfa

    r45444c3 rea3fa25  
    6262                }
    6363
    64                 printf("Took %'ld ms\n", (end - start)`ms);
     64                printf("Duration (ms)       : %'ld\n", (end - start)`ms);
     65                printf("Number of processors: %'d\n", nprocs);
     66                printf("Number of threads   : %'d\n", tthreads);
     67                printf("Cycle size (# thrds): %'d\n", ring_size);
    6568                printf("Yields per second   : %'18.2lf\n", ((double)global_counter) / (end - start)`s);
    6669                printf("ns per yields       : %'18.2lf\n", ((double)(end - start)`ns) / global_counter);

  • benchmark/readyQ/cycle.go

    r45444c3 rea3fa25  
    126126
    127127        p := message.NewPrinter(language.English)
    128         p.Printf("Took %f ms\n", delta.Seconds())
     128        p.Printf("Duration (ms)       : %f\n", delta.Seconds());
     129        p.Printf("Number of processors: %d\n", nprocs);
     130        p.Printf("Number of threads   : %d\n", tthreads);
     131        p.Printf("Cycle size (# thrds): %d\n", ring_size);
    129132        p.Printf("Yields per second   : %18.2f\n", float64(global_counter) / delta.Seconds())
    130133        p.Printf("ns per yields       : %18.2f\n", float64(delta.Nanoseconds()) / float64(global_counter))

  • doc/theses/thierry_delisle_PhD/comp_II/presentation.tex

    r45444c3 rea3fa25  
    3636        \miniframeson
    3737}
    38 \section{\CFA and Concurrency}
     38\section{Concurrency and \CFA}
     39\begin{frame}{Project}
     40        \begin{center}
     41                {\large Produce a scheduler for \CFA that is simple for programmers to understand and offers good general performance.}
     42        \end{center}
     43\end{frame}
     44%------------------------------
    3945\begin{frame}{\CFA}
     46        \CFA is a modern extension of C.
     47        It adds to C : overloading, constructors/destructors, polymorphism, and much more.
     48
     49        ~\newline
     50        For this project, the relevant aspects are:
     51        \begin{itemize}
     52                \item Fast and safe system language.
     53                \item Threading.
     54                \item Manual memory management.
     55        \end{itemize}
    4056
    4157\end{frame}
    … …  
    104120\begin{frame}{Priority Scheduling}
    105121        \begin{center}
    106         {\large
     122                {\large
    107123                        Runs all ready threads in group \textit{A} before any ready threads in group \textit{B}.
    108124                }
    … …  
    136152
    137153        Processors begin busy for long periods can mean starvation.
     154\end{frame}
     155%------------------------------
     156\begin{frame}{Scheduling in Practice: Summary}
     157        \begin{columns}
     158                \begin{column}{0.5\textwidth}
     159                        \textbf{Feedback Scheduling}
     160                        \newline
     161
     162                        \begin{itemize}
     163                                \item Inappropriate for short lived threads.
     164                                \item Overkill for cooperating threads.\newline
     165                        \end{itemize}
     166                \end{column}
     167                \begin{column}{0.5\textwidth}
     168                        \textbf{Priority Scheduling}
     169                        \newline
     170
     171                        \begin{itemize}
     172                                \item Allows lasting starvation.\newline
     173                                \item Hard to reason about.\newline~\newline
     174                        \end{itemize}
     175                \end{column}
     176        \end{columns}
     177
     178        ~\newline
     179        ~\newline
     180        \CFA would benefit from something different.
    138181\end{frame}
    139182%==============================
    … …  
    190233        \begin{itemize}
    191234                \item Acquire for reading for normal scheduling operations.
    192                 \item Acquire for right when resizing the array and creating/deleting internal queues.
     235                \item Acquire for writing when resizing the array and creating/deleting internal queues.
    193236        \end{itemize}
    194237\end{frame}
    … …  
    314357        Runtime system and scheduling are still open topics.
    315358        \newline
     359        \newline
    316360
    317361        This work offers a novel runtime and scheduling package.
     362        \newline
    318363        \newline
    319364
    … …  
    336381
    337382%------------------------------
    338 \begin{frame}{Timeline}
     383\begin{frame}{}
    339384        \begin{center}
    340385                {\large Questions?}

  • doc/theses/thierry_delisle_PhD/comp_II/presentationstyle.sty

    r45444c3 rea3fa25  
    2020\setbeamertemplate{blocks}[rounded][shadow=false]
    2121\newcommand\xrowht[2][0]{\addstackgap[.5\dimexpr#2\relax]{\vphantom{#1}}}
     22\setbeamertemplate{sections/subsections in toc}{\inserttocsectionnumber.~\inserttocsection}
    2223
    2324%==============================
    … …  
    3637\setbeamercolor{palette primary}{bg=colbg}
    3738\setbeamercolor{palette tertiary}{fg=red}
     39\setbeamercolor{section in toc}{fg=white}
     40\setbeamercolor{subsection in toc}{fg=gray}
    3841
    3942%==============================

  • doc/theses/thierry_delisle_PhD/thesis/Makefile

    r45444c3 rea3fa25  
    1515        front \
    1616        intro \
     17        existing \
    1718        runtime \
    1819        core \
    … …  
    2728        base \
    2829        empty \
     30        system \
    2931}
    3032
    … …  
    3739## Define the documents that need to be made.
    3840all: thesis.pdf
    39 thesis.pdf: ${TEXTS} ${FIGURES} ${PICTURES} glossary.tex
     41thesis.pdf: ${TEXTS} ${FIGURES} ${PICTURES} glossary.tex local.bib
    4042
    4143DOCUMENT = thesis.pdf

  • doc/theses/thierry_delisle_PhD/thesis/fig/system.fig

    r45444c3 rea3fa25  
    1 #FIG 3.2  Produced by xfig version 3.2.5c
     1#FIG 3.2  Produced by xfig version 3.2.7b
    22Landscape
    33Center
    … …  
    36361 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 3600 15 15 4500 3600 4515 3615
    3737-6
    38 6 3225 4125 4650 4425
    39 6 4350 4200 4650 4350
    40 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4425 4275 15 15 4425 4275 4440 4290
    41 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 4275 15 15 4500 4275 4515 4290
    42 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4575 4275 15 15 4575 4275 4590 4290
    43 -6
    44 1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3450 4275 225 150 3450 4275 3675 4425
    45 1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 4275 225 150 4050 4275 4275 4425
    46 -6
    47 6 6675 4125 7500 4425
    48 6 7200 4200 7500 4350
    49 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7275 4275 15 15 7275 4275 7290 4290
    50 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7350 4275 15 15 7350 4275 7365 4290
    51 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7425 4275 15 15 7425 4275 7440 4290
    52 -6
    53 1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 4275 225 150 6900 4275 7125 4425
    54 -6
    55386 6675 3525 8025 3975
    56392 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2
    … …  
    79621 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3975 2850 150 150 3975 2850 4125 2850
    80631 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 7200 2775 150 150 7200 2775 7350 2775
    81 1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4860
     641 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4830
    82651 3 0 1 0 0 0 0 0 0.000 1 0.0000 7200 2775 30 30 7200 2775 7230 2805
    83661 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3525 3600 150 150 3525 3600 3675 3600
    84 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3875 4800 100 100 3875 4800 3975 4800
    85 1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4650 4800 150 75 4650 4800 4800 4875
     671 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4625 4838 100 100 4625 4838 4725 4838
    86682 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5
    8769         2400 4200 2400 3750 1950 3750 1950 4200 2400 4200
    … …  
    153135        1 1 1.00 45.00 90.00
    154136         7875 3750 7875 2325 7200 2325 7200 2550
     1372 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5
     138         6975 4950 6750 4950 6750 4725 6975 4725 6975 4950
    1551392 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5
    156140         5850 4950 5850 4725 5625 4725 5625 4950 5850 4950
    157 2 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5
    158          6975 4950 6750 4950 6750 4725 6975 4725 6975 4950
    159 4 1 -1 0 0 0 10 0.0000 2 105 720 5550 4425 Processors\001
    160 4 1 -1 0 0 0 10 0.0000 2 120 1005 4200 3225 Blocked Tasks\001
    161 4 1 -1 0 0 0 10 0.0000 2 150 870 4200 3975 Ready Tasks\001
    162 4 1 -1 0 0 0 10 0.0000 2 135 1095 7350 1725 Other Cluster(s)\001
    163 4 1 -1 0 0 0 10 0.0000 2 105 840 4650 1725 User Cluster\001
    164 4 1 -1 0 0 0 10 0.0000 2 150 615 2175 3675 Manager\001
    165 4 1 -1 0 0 0 10 0.0000 2 105 990 2175 3525 Discrete-event\001
    166 4 1 -1 0 0 0 10 0.0000 2 135 795 2175 4350 preemption\001
    167 4 0 -1 0 0 0 10 0.0000 2 150 1290 2325 4875 generator/coroutine\001
    168 4 0 -1 0 0 0 10 0.0000 2 120 270 4050 4875 task\001
    169 4 0 -1 0 0 0 10 0.0000 2 105 450 7050 4875 cluster\001
    170 4 0 -1 0 0 0 10 0.0000 2 105 660 5925 4875 processor\001
    171 4 0 -1 0 0 0 10 0.0000 2 105 555 4875 4875 monitor\001
     1414 1 -1 0 0 0 10 0.0000 2 135 900 5550 4425 Processors\001
     1424 1 -1 0 0 0 10 0.0000 2 165 1170 4200 3975 Ready Threads\001
     1434 1 -1 0 0 0 10 0.0000 2 165 1440 7350 1725 Other Cluster(s)\001
     1444 1 -1 0 0 0 10 0.0000 2 135 1080 4650 1725 User Cluster\001
     1454 1 -1 0 0 0 10 0.0000 2 165 630 2175 3675 Manager\001
     1464 1 -1 0 0 0 10 0.0000 2 135 1260 2175 3525 Discrete-event\001
     1474 1 -1 0 0 0 10 0.0000 2 150 900 2175 4350 preemption\001
     1484 0 -1 0 0 0 10 0.0000 2 135 630 7050 4875 cluster\001
     1494 1 -1 0 0 0 10 0.0000 2 135 1350 4200 3225 Blocked Threads\001
     1504 0 -1 0 0 0 10 0.0000 2 135 540 4800 4875 thread\001
     1514 0 -1 0 0 0 10 0.0000 2 120 810 5925 4875 processor\001
     1524 0 -1 0 0 0 10 0.0000 2 165 1710 2325 4875 generator/coroutine\001

  • doc/theses/thierry_delisle_PhD/thesis/glossary.tex

    r45444c3 rea3fa25  
    11\makeglossaries
     2
     3% ----------------------------------
     4% Acronyms
     5\newacronym{api}{API}{Application Programming Interface}
     6\newacronym{fifo}{FIFO}{First-In, First-Out}
     7\newacronym{io}{I/O}{Input and Output}
     8\newacronym{numa}{NUMA}{Non-Uniform Memory Access}
     9\newacronym{raii}{RAII}{Resource Acquisition Is Initialization}
     10\newacronym{tls}{TLS}{Thread Local Storage}
     11
     12% ----------------------------------
     13% Definitions
     14
     15\longnewglossaryentry{thrd}
     16{name={thread}}
     17{
     18Threads created and managed inside user-space. Each thread has its own stack and its own thread of execution. User-level threads are invisible to the underlying operating system.
     19
     20\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
     21}
     22
     23\longnewglossaryentry{proc}
     24{name={processor}}
     25{
     26
     27}
     28
     29\longnewglossaryentry{rQ}
     30{name={ready-queue}}
     31{
     32
     33}
     34
     35\longnewglossaryentry{uthrding}
     36{name={user-level threading}}
     37{
     38
     39
     40\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
     41}
     42
     43% ----------------------------------
    244
    345\longnewglossaryentry{hthrd}
    446{name={hardware thread}}
    547{
    6 Threads representing the underlying hardware directly.
     48Threads representing the underlying hardware directly, \eg the CPU core, or hyper-thread if the hardware supports multiple threads of execution per core. The number of hardware threads is considered to be always fixed to a specific number determined by the hardware.
    749
    8 \textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
    9 }
    10 
    11 \longnewglossaryentry{thrd}
    12 {name={threads}}
    13 {
    14 Threads created and managed inside user-space. Each thread has its own stack and its own thread of execution. User-level threads are invisible to the underlying operating system.
    15 
    16 \textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
     50\textit{Synonyms : }
    1751}
    1852
    … …  
    5791}
    5892
    59 \longnewglossaryentry{proc}
    60 {name={virtual processor}}
    61 {
    6293
    63 }
    64 
    65 \longnewglossaryentry{Q}
    66 {name={work-queue}}
    67 {
    68 
    69 }
    7094
    7195\longnewglossaryentry{at}
    … …  
    131155}
    132156
    133 
    134 \newacronym{tls}{TLS}{Thread Local Storage}
    135 \newacronym{api}{API}{Application Program Interface}
    136 \newacronym{raii}{RAII}{Resource Acquisition Is Initialization}
    137 \newacronym{numa}{NUMA}{Non-Uniform Memory Access}

  • doc/theses/thierry_delisle_PhD/thesis/text/core.tex

    r45444c3 rea3fa25  
    11\chapter{Scheduling Core}\label{core}
    22
    3 This chapter addresses the need of scheduling on a somewhat ideal scenario
     3Before discussing scheduling in general, where it is important to address systems that are changing states, this document discusses scheduling in a somewhat ideal scenerio, where the system has reached a steady state. For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and but the system has the ressources necessary to accomplish the work. In short, the system is neither overloaded or underloaded.
    44
    5 \section{Existing Schedulers}
    6 \subsection{Feedback Scheduling}
     5I believe it is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected. As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to the new load and return to the steady state. Flaws in the scheduling in the steady state tend therefore to be pervasive in all states.
    76
    8 \subsection{Priority Scheduling}\label{priority}
     7\section{Design Goals}
     8As with most of the design decisions behind \CFA, the main goal is to match the expectation of the programmer, according to their probable mental model. To match these expectations, the design must offer the programmers sufficient guarantees so that, as long as the programmer respects the mental model, the system will also respect this model.
    99
    10 \subsection{Work Stealing}
     10For threading, a simple and common mental model is the ``Ideal multi-tasking CPU'' :
     11
     12\begin{displayquote}[Linux CFS\cit{https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt}]
     13        {[The]} ``Ideal multi-tasking CPU'' is a (non-existent  :-)) CPU that has 100\% physical power and which can run each task at precise equal speed, in parallel, each at [an equal fraction of the] speed.  For example: if there are 2 tasks running, then it runs each at 50\% physical power --- i.e., actually in parallel.
     14\end{displayquote}
     15
     16Applied to threads, this model states that every ready \gls{thrd} immediately runs in parallel with all other ready \glspl{thrd}. While a strict implementation of this model is not feasible, programmers still have expectations about scheduling that come from this model.
     17
     18In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with eachother but simply share the hardware. This makes it easier to reason about threading because ready \glspl{thrd} can be taken in isolation and the effect of the scheduler can be virtually ignored. This expectation of \gls{thrd} independence means the scheduler is expected to offer 2 guarantees:
     19\begin{enumerate}
     20        \item A fairness guarantee: a \gls{thrd} that is ready to run will not be prevented to do so by another thread.
     21        \item A performance guarantee: a \gls{thrd} that wants to start or stop running will not be slowed down by other threads wanting to do the same.
     22\end{enumerate}
     23
     24It is important to note that these guarantees are expected only up to a point. \Glspl{thrd} that are ready to run should not be prevented to do so, but they still need to share a limited amount of hardware. Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware, even if that share is very small.
     25
     26Similarly the performance guarantee, the lack of interferance between threads is only relevant op to a point. Ideally the cost of running and blocking would be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention. How much is an acceptable cost is obviously highly variable. For this document the performance experimentation will attempt to show that the cost of scheduling is not a major factor in application performance. This demonstration can be made by comparing application built in \CFA to applications built with other languages or other models. If the performance of an application built in \CFA is not meaningfully different than one built with a different runtime, then the scheduler has a negigeable impact on performance, \ie its impact can be ignored. Recall from a few paragraphs ago that the expectation of programmers is that the impact of the scheduler can be ignored. Therefore, if the cost of scheduling is not a significant portion of the runtime of several different application, I will consider the guarantee achieved.
     27
     28\todo{This paragraph should be moved later}
     29% The next step is then to decide what is considered a \emph{fair share}, \ie what metric is used to measure fairness. Since \CFA is intended to allow numerous short lived threads, I decided to avoid total CPU time as the measure of fairness. Total CPU time inherently favors new \glspl{thrd} over older ones which isn't necessarily a good thing. Instead, fairness is measured in terms of opportunities to run. This metric is more appropriate for a mix of short and long lived \glspl{thrd}.
    1130
    1231\section{Design}
    13 While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}.
     32While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}. A strictly \glsxtrshort{fifo} rea
    1433
    1534\subsection{Sharding}
    … …  
    1938                \input{base.pstex_t}
    2039        \end{center}
    21         \caption{Relaxed FIFO list at the base of the scheduler: an array of strictly FIFO lists.
    22         The timestamp is in all nodes and cell arrays.}
     40        \caption{Relaxed FIFO list}
    2341        \label{fig:base}
     42        List at the base of the scheduler: an array of strictly FIFO lists.
     43        The timestamp is in all nodes and cell arrays.
    2444\end{figure}
    2545
    … …  
    2848Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of these queues are empty.
    2949Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time.
    30 This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
    31 
    32 Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme.
    33 
    34 \paragraph{Dense Information}
    35 
    36 
    37 
    3850
    3951
    … …  
    4254                \input{empty.pstex_t}
    4355        \end{center}
    44         \caption{``More empty'' state of the queue: the array contains many empty cells.}
     56        \caption{``More empty'' Relaxed FIFO list}
    4557        \label{fig:empty}
     58        Emptier state of the queue: the array contains many empty cells, that is strictly FIFO lists containing no elements.
    4659\end{figure}
     60
     61This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
     62
     63Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme.
     64
     65\paragraph{Dense Information}

  • doc/theses/thierry_delisle_PhD/thesis/text/front.tex

    r45444c3 rea3fa25  
    184184\phantomsection         % allows hyperref to link to the correct page
    185185
     186% TODOs and missing citations
     187% -----------------------------
    186188\listofcits
    187189\listoftodos
     190\cleardoublepage
     191\phantomsection         % allows hyperref to link to the correct page
    188192
    189193

  • doc/theses/thierry_delisle_PhD/thesis/text/intro.tex

    r45444c3 rea3fa25  
    1 \chapter{Introduction}
     1\chapter*{Introduction}\label{intro}
     2\todo{A proper intro}
     3
     4The C programming language\cit{C}
     5
     6The \CFA programming language\cite{cfa:frontpage,cfa:typesystem} which extends the C programming language to add modern safety and productiviy features while maintaining backwards compatibility. Among it's productiviy features, \CFA introduces support for threading\cit{CFA Concurrency}, to allow programmers to write modern concurrent and parallel programming.
     7While previous work on the concurrent package of \CFA focused on features and interfaces, this thesis focuses on performance, introducing \glsxtrshort{api} changes only when required by performance considerations. More specifically, this thesis concentrates on scheduling and \glsxtrshort{io}. Prior to this work, the \CFA runtime used a strictly \glsxtrshort{fifo} \gls{rQ}.
     8
     9This work exclusively concentrates on Linux as it's operating system since the existing \CFA runtime and compiler does not already support other operating systems. Furthermore, as \CFA is yet to be released, supporting version of Linux older that the latest version is not a goal of this work.

  • doc/theses/thierry_delisle_PhD/thesis/text/io.tex

    r45444c3 rea3fa25  
    1 \chapter{I/O}
     1\chapter{User Level \glsxtrshort{io}}
     2As mentionned in Section~\ref{prev:io}, User-Level \glsxtrshort{io} requires multiplexing the \glsxtrshort{io} operations of many \glspl{thrd} onto fewer \glspl{proc} using asynchronous \glsxtrshort{io} operations. Various operating systems offer various forms of asynchronous operations and as mentioned in Chapter~\ref{intro}, this work is exclusively focuesd on Linux.
    23
    34\section{Existing options}
     5Since \glsxtrshort{io} operations are generally handled by the
    46
    57\subsection{\texttt{epoll}, \texttt{poll} and \texttt{select}}
    … …  
    79\subsection{Linux's AIO}
    810
     11
     12
     13\begin{displayquote}
     14        AIO is a horrible ad-hoc design, with the main excuse being "other,
     15        less gifted people, made that design, and we are implementing it for
     16        compatibility because database people - who seldom have any shred of
     17        taste - actually use it".
     18
     19        But AIO was always really really ugly.
     20
     21        \begin{flushright}
     22                -- Linus Torvalds\cit{https://lwn.net/Articles/671657/}
     23        \end{flushright}
     24\end{displayquote}
     25
     26Interestingly, in this e-mail answer, Linus goes on to describe
     27``a true \textit{asynchronous system call} interface''
     28that does
     29``[an] arbitrary system call X with arguments A, B, C, D asynchronously using a kernel thread''
     30in
     31``some kind of arbitrary \textit{queue up asynchronous system call} model''.
     32This description is actually quite close to the interface of the interface described in the next section.
     33
    934\subsection{\texttt{io\_uring}}
     35A very recent addition to Linux, \texttt{io\_uring}\cit{io\_uring} is a framework that aims to solve many of the problems listed with the above mentioned solutions.
    1036
    11 \subsection{Extra Kernel Threads}
     37\subsection{Extra Kernel Threads}\label{io:morethreads}
     38Finally, if the operating system does not offer any satisfying forms of asynchronous \glsxtrshort{io} operations, a solution is to fake it by creating a pool of \glspl{kthrd} and delegating operations to them in order to avoid blocking \glspl{proc}.
    1239
    1340\subsection{Discussion}

  • doc/theses/thierry_delisle_PhD/thesis/text/practice.tex

    r45444c3 rea3fa25  
    22The scheduling algorithm discribed in Chapter~\ref{core} addresses scheduling in a stable state.
    33However, it does not address problems that occur when the system changes state.
    4 Indeed the \CFA runtime, supports expanding and shrinking
    5 
    6 the number of KTHREAD\_place
    7 
    8 , both manually and, to some extent automatically.
     4Indeed the \CFA runtime, supports expanding and shrinking the number of KTHREAD\_place \todo{add kthrd to glossary}, both manually and, to some extent automatically.
    95This entails that the scheduling algorithm must support these transitions.
    106

  • doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex

    r45444c3 rea3fa25  
    11\chapter{\CFA Runtime}
     2This chapter offers an overview of the capabilities of the \CFA runtime prior to this work.
    23
    3 \section{M:N Threading}
     4Threading in \CFA offers is based on \Gls{uthrding}, where \glspl{thrd} are the representation of a unit of work. As such, \CFA programmers should expect these units to be fairly inexpensive, that is: programmers should be able to create a large number of \glspl{thrd} and switch between \glspl{thrd} liberally without many concerns for performance.
     5
     6\section{M:N Threading}\label{prev:model}
     7
     8C traditionnally uses a 1:1 threading model. This model uses \glspl{kthrd} to achive parallelism and concurrency. In this model, every thread of computation maps to an object in the kernel. The kernel then has the responsibility of managing these threads, \eg creating, scheduling, blocking. This also entails that the kernel has a perfect view of every thread executing in the system\footnote{This is not completly true due to primitives like \texttt{futex}es, which have a significant portion of their logic in user space.}.
     9
     10By contrast \CFA uses an M:N threading models, where concurrency is achieved using many user-level threads mapped onto fewer \glspl{kthrd}. The user-level threads have the same semantic meaning as a \glspl{kthrd} in the 1:1 model, they represent an independant thread of execution with it's on stack. The difference is that user-level threads do not have a corresponding object in the kernel, they are handled by the runtime in user space and scheduled onto \glspl{kthrd}, referred to as \glspl{proc} in this document. \Glspl{proc} run a \gls{thrd} until it context switches out, it then choses a different \gls{thrd} to run.
    411
    512\section{Clusters}
     13\begin{figure}
     14        \begin{center}
     15                \input{system.pstex_t}
     16        \end{center}
     17        \caption{Overview of the \CFA runtime}
     18        \label{fig:system}
     19        \Glspl{thrd} are scheduled inside a particular cluster, where it only runs on the \glspl{proc} which belong to the cluster. The discrete-event manager, which handles preemption and timeout, is a \gls{kthrd} which lives outside any cluster and does not run \glspl{thrd}.
     20\end{figure}
     21\CFA allows the option to group user-level threading, in the form of clusters. Both \glspl{thrd} and \glspl{proc} belong to a specific cluster. \Glspl{thrd} will only be scheduled onto \glspl{proc} in the same cluster and scheduling is done independantly of other clusters. Figure~\ref{fig:system} shows an overview if this system. This allows programmers to control more tightly parallelism. It also opens the door to handling effects like NUMA, by pining clusters to specific NUMA node\footnote{This is not currently implemented in \CFA, but the only hurdle left is creating a generic interface for cpu masks.}.
     22
     23\section{Scheduling}
     24The \CFA runtime was previously using a strictly \glsxtrshort{fifo} ready queue with a single lock. This setup offers perfect fairness in terms of opportunities to run/ However, it offers poor scalability, since the performance of the ready queue can never be improved by adding more \glspl{hthrd}, but the contention can cause significant performance degradation.
     25
     26\section{\glsxtrshort{io}}\label{prev:io}
     27Prior to this work, the \CFA runtime did not add any particular support for \glsxtrshort{io} operations. \CFA being built on C, this means that, while all the operations available in C are available in \CFA, \glsxtrshort{io} operations are designed for the POSIX threading model\cit{pthreads}. Using these operations in a M:N threading model, when they are built for 1:1 threading, means that operations block \glspl{proc} instead of \glspl{thrd}. While this can work in certain cases, it limits the number of concurrent operations to the number of \glspl{proc} rather than \glspl{thrd}. This also means that deadlocks can occur because all \glspl{proc} are blocked even if at least one \gls{thrd} is ready to run. A simple example of this type of deadlock would be as follows:
     28
     29Given a simple network program with 2 \glspl{thrd} and a single \gls{proc}, one \gls{thrd} sends network requests to a server and the other \gls{thrd} waits for response from the server. If the second \gls{thrd} races ahead, it may wait for responses to requests that have not been sent yet. In theory, this should not be a problem, even if the second \gls{thrd} waits, the first \gls{thrd} is still ready to run and should just be able to get CPU time and send the request. In practice with M:N threading, while the first \gls{thrd} is ready, the lone \gls{proc} in this example will \emph{not} try to run the first \gls{thrd} if it is blocked in the \glsxtrshort{io} operation of the second \gls{thrd}. If this happen, the system is effectively deadlocked\footnote{In this example, the deadlocked could be resolved if the server sends unprompted messages to the client. However, this solution is not general and may not be appropriate even in this simple case.}.
     30
     31One of the objective of this work, is to introduce \emph{User-Level \glsxtrshort{io}} which, as a parallel to \glslink{uthrding}{User-Level \emph{Threading}}, blocks \glspl{thrd} rather than \glspl{proc} when doing \glsxtrshort{io} operations. This entails multiplexing the \glsxtrshort{io} operations of many \glspl{thrd} onto fewer \glspl{proc}. This multiplexing requires that a single \gls{proc} be able to execute multiple operations in parallel. This cannot be done with operations that block \glspl{proc}, \ie \glspl{kthrd}, since the first operation would prevent starting new operations for its duration. Executing operations in parallel requires \emph{asynchronous} \glsxtrshort{io}, sometimes referred to as \emph{non-blocking}, since the \gls{kthrd} is not blocked.
    632
    733\section{Interoperating with \texttt{C}}
     34While \glsxtrshort{io} operations are the classical example of operations that block \glspl{kthrd}, the challenges mentioned in the previous section do not require \glsxtrshort{io} to be involved. These challenges are a product of blocking system calls rather than \glsxtrshort{io}. C offers no tools to identify whether or not a librairy function will lead to a blocking system call. This fact means interoperatability with C becomes a challenge in a M:N threading model.
     35
     36Languages like Go and Java, which have strict interoperatability with C\cit{JNI, GoLang with C}, can control operations in C by ``sandboxing'' them. They can, for example, delegate C operations to \glspl{kthrd} that are not \glspl{proc}. Sandboxing may help towards guaranteeing that the deadlocks mentioned in the previous section do not occur.
     37
     38As mentioned in Section~\cit{\CFA intro}, \CFA is binary compatible with C and, as such, trivially supports calls to and from C librairies. Furthermore, interoperatability can happen within a single library, through inline code or simply C and \CFA translation units archived together. The fine-grained interoperatability between C and \CFA has two consequences:
     39\begin{enumerate}
     40        \item Precisely identifying C calls that could block is difficult.
     41        \item Introducing code where interoperatability occurs could have a significant impact on general performance.
     42\end{enumerate}
     43
     44Because of these consequences, this work does not attempt to ``sandbox'' calls to C. It is possible that conflicting calls to C could lead to deadlocks on \CFA's M:N threading model where they would not in the traditionnal 1:1 threading model. However, I judge that solving this problem in general, in a way that is composable and flexible, is too complex in itself and would add too much work to this thesis. Therefore it is outside the scope of this thesis.

  • doc/theses/thierry_delisle_PhD/thesis/thesis.tex

    r45444c3 rea3fa25  
    121121% installation instructions there.
    122122
     123\usepackage{csquotes}
     124\usepackage{indentfirst} % as any self-respecting frenchman would
     125
    123126% Setting up the page margins...
    124127% uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the
    … …  
    218221% separate documents, they would each start with the \chapter command, i.e,
    219222% do not contain \documentclass or \begin{document} and \end{document} commands.
     223\part{Introduction}
    220224\input{text/intro.tex}
     225\input{text/existing.tex}
    221226\input{text/runtime.tex}
     227\part{Design}
    222228\input{text/core.tex}
    223229\input{text/practice.tex}
    224230\input{text/io.tex}
     231\part{Evaluation}
     232\chapter{Theoretical and Existance Proofs}
     233\chapter{Micro-Benchmarks}
     234\chapter{Larger-Scale applications}
     235\part{Conclusion \& Annexes}
    225236
    226237%----------------------------------------------------------------------
    … …  
    245256\addcontentsline{toc}{chapter}{\textbf{References}}
    246257
    247 \bibliography{uw-ethesis}
     258\bibliography{local}
    248259% Tip 5: You can create multiple .bib files to organize your references.
    249260% Just list them all in the \bibliogaphy command, separated by commas (no spaces).
    250261
    251 % The following statement causes the specified references to be added to the bibliography% even if they were not
    252 % cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional).
    253 \nocite{*}
     262% % The following statement causes the specified references to be added to the bibliography% even if they were not
     263% % cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional).
     264% \nocite{*}
    254265
    255266% The \appendix statement indicates the beginning of the appendices.

  • libcfa/src/concurrency/invoke.h

    r45444c3 rea3fa25  
    157157
    158158                // current execution status for coroutine
     159                // Possible values are:
     160                //    - TICKET_BLOCKED (-1) thread is blocked
     161                //    - TICKET_RUNNING ( 0) thread is running
     162                //    - TICKET_UNBLOCK ( 1) thread should ignore next block
    159163                volatile int ticket;
    160164                enum __Coroutine_State state:8;

  • libcfa/src/concurrency/io/setup.cfa

    r45444c3 rea3fa25  
    250250                                        // Fixup the thread state
    251251                                        thrd.state = Blocked;
    252                                         thrd.ticket = 0;
     252                                        thrd.ticket = TICKET_BLOCKED;
    253253                                        thrd.preempted = __NO_PREEMPTION;
    254254

  • libcfa/src/concurrency/kernel.cfa

    r45444c3 rea3fa25  
    299299                int old_ticket = __atomic_fetch_sub(&thrd_dst->ticket, 1, __ATOMIC_SEQ_CST);
    300300                switch(old_ticket) {
    301                         case 1:
     301                        case TICKET_RUNNING:
    302302                                // This is case 1, the regular case, nothing more is needed
    303303                                break RUNNING;
    304                         case 2:
     304                        case TICKET_UNBLOCK:
    305305                                // This is case 2, the racy case, someone tried to run this thread before it finished blocking
    306306                                // In this case, just run it again.
    … …  
    410410        int old_ticket = __atomic_fetch_add(&thrd->ticket, 1, __ATOMIC_SEQ_CST);
    411411        switch(old_ticket) {
    412                 case 1:
     412                case TICKET_RUNNING:
    413413                        // Wake won the race, the thread will reschedule/rerun itself
    414414                        break;
    415                 case 0:
     415                case TICKET_BLOCKED:
    416416                        /* paranoid */ verify( ! thrd->preempted != __NO_PREEMPTION );
    417417                        /* paranoid */ verify( thrd->state == Blocked );
    … …  
    422422                default:
    423423                        // This makes no sense, something is wrong abort
    424                         abort();
     424                        abort("Thread %p (%s) has mismatch park/unpark\n", thrd, thrd->self_cor.name);
    425425        }
    426426}

  • libcfa/src/concurrency/kernel/startup.cfa

    r45444c3 rea3fa25  
    441441
    442442static void ?{}( $thread & this, current_stack_info_t * info) with( this ) {
    443         ticket = 1;
     443        ticket = TICKET_RUNNING;
    444444        state = Start;
    445445        self_cor{ info };

  • libcfa/src/concurrency/kernel_private.hfa

    r45444c3 rea3fa25  
    6565// KERNEL ONLY unpark with out disabling interrupts
    6666void __unpark( struct __processor_id_t *, $thread * thrd );
     67
     68#define TICKET_BLOCKED (-1) // thread is blocked
     69#define TICKET_RUNNING ( 0) // thread is running
     70#define TICKET_UNBLOCK ( 1) // thread should ignore next block
    6771
    6872static inline bool __post(single_sem & this, struct __processor_id_t * id) {

  • libcfa/src/concurrency/thread.cfa

    r45444c3 rea3fa25  
    2929        context{ 0p, 0p };
    3030        self_cor{ name, storage, storageSize };
    31         ticket = 1;
     31        ticket = TICKET_RUNNING;
    3232        state = Start;
    3333        preempted = __NO_PREEMPTION;

  • src/InitTweak/FixInitNew.cpp

    r45444c3 rea3fa25  
    6161
    6262namespace InitTweak {
    63         namespace {
    64                 struct SelfAssignChecker {
    65                         void previsit( const ast::ApplicationExpr * appExpr );
    66                 };
    67 
    68                 struct StmtExprResult {
    69                         static void link( std::list<ast::ptr<ast::Decl> > & translationUnit );
    70 
    71                         const ast::StmtExpr * previsit( const ast::StmtExpr * stmtExpr );
    72                 };
    73 
    74                 struct InsertImplicitCalls : public ast::WithConstTypeSubstitution, public ast::WithShortCircuiting {
    75                         /// wrap function application expressions as ImplicitCopyCtorExpr nodes so that it is easy to identify which
    76                         /// function calls need their parameters to be copy constructed
    77                         static void insert( std::list<ast::ptr<ast::Decl> > & translationUnit );
    78 
    79                         const ast::Expr * postvisit( const ast::ApplicationExpr * appExpr );
    80 
    81                         // only handles each UniqueExpr once
    82                         // if order of visit does not change, this should be safe
    83                         void previsit (const ast::UniqueExpr *);
    84 
    85                         std::unordered_set<decltype(ast::UniqueExpr::id)> visitedIds;
    86                 };
    87 
    88                 struct ResolveCopyCtors final : public ast::WithGuards, public ast::WithStmtsToAdd<>, public ast::WithSymbolTable, public ast::WithShortCircuiting, public ast::WithVisitorRef<ResolveCopyCtors> {
    89                         /// generate temporary ObjectDecls for each argument and return value of each ImplicitCopyCtorExpr,
    90                         /// generate/resolve copy construction expressions for each, and generate/resolve destructors for both
    91                         /// arguments and return value temporaries
    92                         static void resolveImplicitCalls( std::list<ast::ptr<ast::Decl> > & translationUnit );
    93 
    94                         const ast::Expr * postvisit( const ast::ImplicitCopyCtorExpr * impCpCtorExpr );
    95                         const ast::StmtExpr * previsit( const ast::StmtExpr * stmtExpr );
    96                         const ast::UniqueExpr * previsit( const ast::UniqueExpr * unqExpr );
    97 
    98                         /// handles distant mutations of environment manually.
    99                         /// WithConstTypeSubstitution cannot remember where the environment is from
    100 
    101                         /// MUST be called at start of overload previsit
    102                         void previsit( const ast::Expr * expr);
    103                         /// MUST be called at return of overload postvisit
    104                         const ast::Expr * postvisit(const ast::Expr * expr);
    105 
    106                         /// create and resolve ctor/dtor expression: fname(var, [cpArg])
    107                         const ast::Expr * makeCtorDtor( const std::string & fname, const ast::ObjectDecl * var, const ast::Expr * cpArg = nullptr );
    108                         /// true if type does not need to be copy constructed to ensure correctness
    109                         bool skipCopyConstruct( const ast::Type * type );
    110                         ast::ptr< ast::Expr > copyConstructArg( const ast::Expr * arg, const ast::ImplicitCopyCtorExpr * impCpCtorExpr, const ast::Type * formal );
    111                         ast::Expr * destructRet( const ast::ObjectDecl * ret, const ast::Expr * arg );
    112                 private:
    113                         /// hack to implement WithTypeSubstitution while conforming to mutation safety.
    114                         ast::TypeSubstitution * env;
    115                         bool                    envModified;
    116                 };
    117 
    118                 /// collects constructed object decls - used as a base class
    119                 struct ObjDeclCollector : public ast::WithGuards, public ast::WithShortCircuiting {
    120                         // use ordered data structure to maintain ordering for set_difference and for consistent error messages
    121                         typedef std::list< const ast::ObjectDecl * > ObjectSet;
    122                         void previsit( const ast::CompoundStmt *compoundStmt );
    123                         void previsit( const ast::DeclStmt *stmt );
    124 
    125                         // don't go into other functions
    126                         void previsit( const ast::FunctionDecl * ) { visit_children = false; }
    127 
    128                   protected:
    129                         ObjectSet curVars;
    130                 };
    131 
    132                 // debug
    133                 template<typename ObjectSet>
    134                 struct PrintSet {
    135                         PrintSet( const ObjectSet & objs ) : objs( objs ) {}
    136                         const ObjectSet & objs;
    137                 };
    138                 template<typename ObjectSet>
    139                 PrintSet<ObjectSet> printSet( const ObjectSet & objs ) { return PrintSet<ObjectSet>( objs ); }
    140                 template<typename ObjectSet>
    141                 std::ostream & operator<<( std::ostream & out, const PrintSet<ObjectSet> & set) {
    142                         out << "{ ";
    143                         for ( auto & obj : set.objs ) {
    144                                 out << obj->name << ", " ;
    145                         } // for
    146                         out << " }";
    147                         return out;
    148                 }
    149 
    150                 struct LabelFinder final : public ObjDeclCollector {
    151                         typedef std::map< std::string, ObjectSet > LabelMap;
    152                         // map of Label -> live variables at that label
    153                         LabelMap vars;
    154 
    155                         typedef ObjDeclCollector Parent;
    156                         using Parent::previsit;
    157                         void previsit( const ast::Stmt * stmt );
    158 
    159                         void previsit( const ast::CompoundStmt *compoundStmt );
    160                         void previsit( const ast::DeclStmt *stmt );
    161                 };
    162 
    163                 struct InsertDtors final : public ObjDeclCollector, public ast::WithStmtsToAdd<> {
    164                         /// insert destructor calls at the appropriate places.  must happen before CtorInit nodes are removed
    165                         /// (currently by FixInit)
    166                         static void insert( std::list< ast::ptr<ast::Decl> > & translationUnit );
    167 
    168                         typedef std::list< ObjectDecl * > OrderedDecls;
    169                         typedef std::list< OrderedDecls > OrderedDeclsStack;
    170 
    171                         InsertDtors( ast::Pass<LabelFinder> & finder ) : finder( finder ), labelVars( finder.core.vars ) {}
    172 
    173                         typedef ObjDeclCollector Parent;
    174                         using Parent::previsit;
    175 
    176                         void previsit( const ast::FunctionDecl * funcDecl );
    177 
    178                         void previsit( const ast::BranchStmt * stmt );
    179                 private:
    180                         void handleGoto( const ast::BranchStmt * stmt );
    181 
    182                         ast::Pass<LabelFinder> & finder;
    183                         LabelFinder::LabelMap & labelVars;
    184                         OrderedDeclsStack reverseDeclOrder;
    185                 };
    186 
    187                 class FixInit : public ast::WithStmtsToAdd<> {
    188                   public:
    189                         /// expand each object declaration to use its constructor after it is declared.
    190                         static void fixInitializers( std::list< ast::ptr<ast::Decl> > &translationUnit );
    191 
    192                         const ast::DeclWithType * postvisit( const ast::ObjectDecl *objDecl );
    193 
    194                         std::list< ast::ptr< ast::Decl > > staticDtorDecls;
    195                 };
    196 
    197                 struct GenStructMemberCalls final : public ast::WithGuards, public ast::WithShortCircuiting, public ast::WithSymbolTable, public ast::WithVisitorRef<GenStructMemberCalls> {
    198                         /// generate default/copy ctor and dtor calls for user-defined struct ctor/dtors
    199                         /// for any member that is missing a corresponding ctor/dtor call.
    200                         /// error if a member is used before constructed
    201                         static void generate( std::list< ast::ptr<ast::Decl> > & translationUnit );
    202 
    203                         void previsit( const ast::FunctionDecl * funcDecl );
    204                         const ast::DeclWithType * postvisit( const ast::FunctionDecl * funcDecl );
    205 
    206                         void previsit( const ast::MemberExpr * memberExpr );
    207                         void previsit( const ast::ApplicationExpr * appExpr );
    208 
    209                         /// Note: this post mutate used to be in a separate visitor. If this pass breaks, one place to examine is whether it is
    210                         /// okay for this part of the recursion to occur alongside the rest.
    211                         const ast::Expr * postvisit( const ast::UntypedExpr * expr );
    212 
    213                         SemanticErrorException errors;
    214                   private:
    215                         template< typename... Params >
    216                         void emit( CodeLocation, const Params &... params );
    217 
    218                         ast::FunctionDecl * function = nullptr;
    219                         std::set< const ast::DeclWithType * > unhandled;
    220                         std::map< const ast::DeclWithType *, CodeLocation > usedUninit;
    221                         const ast::ObjectDecl * thisParam = nullptr;
    222                         bool isCtor = false; // true if current function is a constructor
    223                         const ast::StructDecl * structDecl = nullptr;
    224                 };
    225 
    226                 struct FixCtorExprs final : public ast::WithDeclsToAdd<>, public ast::WithSymbolTable, public ast::WithShortCircuiting {
    227                         /// expands ConstructorExpr nodes into comma expressions, using a temporary for the first argument
    228                         static void fix( std::list< ast::ptr<ast::Decl> > & translationUnit );
    229 
    230                         const ast::Expr * postvisit( const ast::ConstructorExpr * ctorExpr );
    231                 };
    232 
    233                 struct SplitExpressions : public ast::WithShortCircuiting {
    234                         /// add CompoundStmts around top-level expressions so that temporaries are destroyed in the correct places.
    235                         static void split( std::list<ast::ptr<ast::Decl> > & translationUnit );
    236 
    237                         ast::Stmt * postvisit( const ast::ExprStmt * stmt );
    238                         void previsit( const ast::TupleAssignExpr * expr );
    239                 };
    240         } // namespace
    241 
    242         void fix( std::list< ast::ptr<ast::Decl> > & translationUnit, bool inLibrary ) {
    243                 ast::Pass<SelfAssignChecker> checker;
    244                 accept_all( translationUnit, checker );
    245 
    246                 // fixes StmtExpr to properly link to their resulting expression
    247                 StmtExprResult::link( translationUnit );
    248 
    249                 // fixes ConstructorInit for global variables. should happen before fixInitializers.
    250                 InitTweak::fixGlobalInit( translationUnit, inLibrary );
    251 
    252                 // must happen before ResolveCopyCtors because temporaries have to be inserted into the correct scope
    253                 SplitExpressions::split( translationUnit );
    254 
    255                 InsertImplicitCalls::insert( translationUnit );
    256 
    257                 // Needs to happen before ResolveCopyCtors, because argument/return temporaries should not be considered in
    258                 // error checking branch statements
    259                 InsertDtors::insert( translationUnit );
    260 
    261                 ResolveCopyCtors::resolveImplicitCalls( translationUnit );
    262                 FixInit::fixInitializers( translationUnit );
    263                 GenStructMemberCalls::generate( translationUnit );
    264 
    265                 // Needs to happen after GenStructMemberCalls, since otherwise member constructors exprs
    266                 // don't have the correct form, and a member can be constructed more than once.
    267                 FixCtorExprs::fix( translationUnit );
    268         }
    269 
    270         namespace {
    271                 /// find and return the destructor used in `input`. If `input` is not a simple destructor call, generate a thunk
    272                 /// that wraps the destructor, insert it into `stmtsToAdd` and return the new function declaration
    273                 const ast::DeclWithType * getDtorFunc( const ast::ObjectDecl * objDecl, const ast::Stmt * input, std::list< ast::ptr<ast::Stmt> > & stmtsToAdd ) {
    274                         const CodeLocation loc = input->location;
    275                         // unwrap implicit statement wrapper
    276                         // Statement * dtor = input;
    277                         assert( input );
    278                         // std::list< const ast::Expr * > matches;
    279                         auto matches = collectCtorDtorCalls( input );
    280 
    281                         if ( dynamic_cast< const ast::ExprStmt * >( input ) ) {
    282                                 // only one destructor call in the expression
    283                                 if ( matches.size() == 1 ) {
    284                                         auto func = getFunction( matches.front() );
    285                                         assertf( func, "getFunction failed to find function in %s", toString( matches.front() ).c_str() );
    286 
    287                                         // cleanup argument must be a function, not an object (including function pointer)
    288                                         if ( auto dtorFunc = dynamic_cast< const ast::FunctionDecl * > ( func ) ) {
    289                                                 if ( dtorFunc->type->forall.empty() ) {
    290                                                         // simple case where the destructor is a monomorphic function call - can simply
    291                                                         // use that function as the cleanup function.
    292                                                         return func;
    293                                                 }
     63namespace {
     64        struct SelfAssignChecker {
     65                void previsit( const ast::ApplicationExpr * appExpr );
     66        };
     67
     68        struct StmtExprResult {
     69                const ast::StmtExpr * previsit( const ast::StmtExpr * stmtExpr );
     70        };
     71
     72        /// wrap function application expressions as ImplicitCopyCtorExpr nodes so that it is easy to identify which
     73        /// function calls need their parameters to be copy constructed
     74        struct InsertImplicitCalls : public ast::WithConstTypeSubstitution, public ast::WithShortCircuiting {
     75                const ast::Expr * postvisit( const ast::ApplicationExpr * appExpr );
     76
     77                // only handles each UniqueExpr once
     78                // if order of visit does not change, this should be safe
     79                void previsit (const ast::UniqueExpr *);
     80
     81                std::unordered_set<decltype(ast::UniqueExpr::id)> visitedIds;
     82        };
     83
     84        /// generate temporary ObjectDecls for each argument and return value of each ImplicitCopyCtorExpr,
     85        /// generate/resolve copy construction expressions for each, and generate/resolve destructors for both
     86        /// arguments and return value temporaries
     87        struct ResolveCopyCtors final : public ast::WithGuards, public ast::WithStmtsToAdd<>, public ast::WithSymbolTable, public ast::WithShortCircuiting, public ast::WithVisitorRef<ResolveCopyCtors> {
     88                const ast::Expr * postvisit( const ast::ImplicitCopyCtorExpr * impCpCtorExpr );
     89                const ast::StmtExpr * previsit( const ast::StmtExpr * stmtExpr );
     90                const ast::UniqueExpr * previsit( const ast::UniqueExpr * unqExpr );
     91
     92                /// handles distant mutations of environment manually.
     93                /// WithConstTypeSubstitution cannot remember where the environment is from
     94
     95                /// MUST be called at start of overload previsit
     96                void previsit( const ast::Expr * expr);
     97                /// MUST be called at return of overload postvisit
     98                const ast::Expr * postvisit(const ast::Expr * expr);
     99
     100                /// create and resolve ctor/dtor expression: fname(var, [cpArg])
     101                const ast::Expr * makeCtorDtor( const std::string & fname, const ast::ObjectDecl * var, const ast::Expr * cpArg = nullptr );
     102                /// true if type does not need to be copy constructed to ensure correctness
     103                bool skipCopyConstruct( const ast::Type * type );
     104                ast::ptr< ast::Expr > copyConstructArg( const ast::Expr * arg, const ast::ImplicitCopyCtorExpr * impCpCtorExpr, const ast::Type * formal );
     105                ast::Expr * destructRet( const ast::ObjectDecl * ret, const ast::Expr * arg );
     106        private:
     107                /// hack to implement WithTypeSubstitution while conforming to mutation safety.
     108                ast::TypeSubstitution * env;
     109                bool                    envModified;
     110        };
     111
     112        /// collects constructed object decls - used as a base class
     113        struct ObjDeclCollector : public ast::WithGuards, public ast::WithShortCircuiting {
     114                // use ordered data structure to maintain ordering for set_difference and for consistent error messages
     115                typedef std::list< const ast::ObjectDecl * > ObjectSet;
     116                void previsit( const ast::CompoundStmt *compoundStmt );
     117                void previsit( const ast::DeclStmt *stmt );
     118
     119                // don't go into other functions
     120                void previsit( const ast::FunctionDecl * ) { visit_children = false; }
     121
     122          protected:
     123                ObjectSet curVars;
     124        };
     125
     126        // debug
     127        template<typename ObjectSet>
     128        struct PrintSet {
     129                PrintSet( const ObjectSet & objs ) : objs( objs ) {}
     130                const ObjectSet & objs;
     131        };
     132        template<typename ObjectSet>
     133        PrintSet<ObjectSet> printSet( const ObjectSet & objs ) { return PrintSet<ObjectSet>( objs ); }
     134        template<typename ObjectSet>
     135        std::ostream & operator<<( std::ostream & out, const PrintSet<ObjectSet> & set) {
     136                out << "{ ";
     137                for ( auto & obj : set.objs ) {
     138                        out << obj->name << ", " ;
     139                } // for
     140                out << " }";
     141                return out;
     142        }
     143
     144        struct LabelFinder final : public ObjDeclCollector {
     145                typedef std::map< std::string, ObjectSet > LabelMap;
     146                // map of Label -> live variables at that label
     147                LabelMap vars;
     148
     149                typedef ObjDeclCollector Parent;
     150                using Parent::previsit;
     151                void previsit( const ast::Stmt * stmt );
     152
     153                void previsit( const ast::CompoundStmt *compoundStmt );
     154                void previsit( const ast::DeclStmt *stmt );
     155        };
     156
     157        /// insert destructor calls at the appropriate places.  must happen before CtorInit nodes are removed
     158        /// (currently by FixInit)
     159        struct InsertDtors final : public ObjDeclCollector, public ast::WithStmtsToAdd<> {
     160                typedef std::list< ObjectDecl * > OrderedDecls;
     161                typedef std::list< OrderedDecls > OrderedDeclsStack;
     162
     163                InsertDtors( ast::Pass<LabelFinder> & finder ) : finder( finder ), labelVars( finder.core.vars ) {}
     164
     165                typedef ObjDeclCollector Parent;
     166                using Parent::previsit;
     167
     168                void previsit( const ast::FunctionDecl * funcDecl );
     169
     170                void previsit( const ast::BranchStmt * stmt );
     171        private:
     172                void handleGoto( const ast::BranchStmt * stmt );
     173
     174                ast::Pass<LabelFinder> & finder;
     175                LabelFinder::LabelMap & labelVars;
     176                OrderedDeclsStack reverseDeclOrder;
     177        };
     178
     179        /// expand each object declaration to use its constructor after it is declared.
     180        struct FixInit : public ast::WithStmtsToAdd<> {
     181                static void fixInitializers( std::list< ast::ptr<ast::Decl> > &translationUnit );
     182
     183                const ast::DeclWithType * postvisit( const ast::ObjectDecl *objDecl );
     184
     185                std::list< ast::ptr< ast::Decl > > staticDtorDecls;
     186        };
     187
     188        /// generate default/copy ctor and dtor calls for user-defined struct ctor/dtors
     189        /// for any member that is missing a corresponding ctor/dtor call.
     190        /// error if a member is used before constructed
     191        struct GenStructMemberCalls final : public ast::WithGuards, public ast::WithShortCircuiting, public ast::WithSymbolTable, public ast::WithVisitorRef<GenStructMemberCalls> {
     192                void previsit( const ast::FunctionDecl * funcDecl );
     193                const ast::DeclWithType * postvisit( const ast::FunctionDecl * funcDecl );
     194
     195                void previsit( const ast::MemberExpr * memberExpr );
     196                void previsit( const ast::ApplicationExpr * appExpr );
     197
     198                /// Note: this post mutate used to be in a separate visitor. If this pass breaks, one place to examine is whether it is
     199                /// okay for this part of the recursion to occur alongside the rest.
     200                const ast::Expr * postvisit( const ast::UntypedExpr * expr );
     201
     202                SemanticErrorException errors;
     203          private:
     204                template< typename... Params >
     205                void emit( CodeLocation, const Params &... params );
     206
     207                ast::FunctionDecl * function = nullptr;
     208                std::set< const ast::DeclWithType * > unhandled;
     209                std::map< const ast::DeclWithType *, CodeLocation > usedUninit;
     210                const ast::ObjectDecl * thisParam = nullptr;
     211                bool isCtor = false; // true if current function is a constructor
     212                const ast::StructDecl * structDecl = nullptr;
     213        };
     214
     215        /// expands ConstructorExpr nodes into comma expressions, using a temporary for the first argument
     216        struct FixCtorExprs final : public ast::WithDeclsToAdd<>, public ast::WithSymbolTable, public ast::WithShortCircuiting {
     217                const ast::Expr * postvisit( const ast::ConstructorExpr * ctorExpr );
     218        };
     219
     220        /// add CompoundStmts around top-level expressions so that temporaries are destroyed in the correct places.
     221        struct SplitExpressions : public ast::WithShortCircuiting {
     222                ast::Stmt * postvisit( const ast::ExprStmt * stmt );
     223                void previsit( const ast::TupleAssignExpr * expr );
     224        };
     225} // namespace
     226
     227void fix( std::list< ast::ptr<ast::Decl> > & translationUnit, bool inLibrary ) {
     228        ast::Pass<SelfAssignChecker>::run( translationUnit );
     229
     230        // fixes StmtExpr to properly link to their resulting expression
     231        ast::Pass<StmtExprResult>::run( translationUnit );
     232
     233        // fixes ConstructorInit for global variables. should happen before fixInitializers.
     234        InitTweak::fixGlobalInit( translationUnit, inLibrary );
     235
     236        // must happen before ResolveCopyCtors because temporaries have to be inserted into the correct scope
     237        ast::Pass<SplitExpressions>::run( translationUnit );
     238
     239        ast::Pass<InsertImplicitCalls>::run( translationUnit );
     240
     241        // Needs to happen before ResolveCopyCtors, because argument/return temporaries should not be considered in
     242        // error checking branch statements
     243        {
     244                ast::Pass<LabelFinder> finder;
     245                ast::Pass<InsertDtors>::run( translationUnit, finder );
     246        }
     247
     248        ast::Pass<ResolveCopyCtors>::run( translationUnit );
     249        FixInit::fixInitializers( translationUnit );
     250        ast::Pass<GenStructMemberCalls>::run( translationUnit );
     251
     252        // Needs to happen after GenStructMemberCalls, since otherwise member constructors exprs
     253        // don't have the correct form, and a member can be constructed more than once.
     254        ast::Pass<FixCtorExprs>::run( translationUnit );
     255}
     256
     257namespace {
     258        /// find and return the destructor used in `input`. If `input` is not a simple destructor call, generate a thunk
     259        /// that wraps the destructor, insert it into `stmtsToAdd` and return the new function declaration
     260        const ast::DeclWithType * getDtorFunc( const ast::ObjectDecl * objDecl, const ast::Stmt * input, std::list< ast::ptr<ast::Stmt> > & stmtsToAdd ) {
     261                const CodeLocation loc = input->location;
     262                // unwrap implicit statement wrapper
     263                // Statement * dtor = input;
     264                assert( input );
     265                // std::list< const ast::Expr * > matches;
     266                auto matches = collectCtorDtorCalls( input );
     267
     268                if ( dynamic_cast< const ast::ExprStmt * >( input ) ) {
     269                        // only one destructor call in the expression
     270                        if ( matches.size() == 1 ) {
     271                                auto func = getFunction( matches.front() );
     272                                assertf( func, "getFunction failed to find function in %s", toString( matches.front() ).c_str() );
     273
     274                                // cleanup argument must be a function, not an object (including function pointer)
     275                                if ( auto dtorFunc = dynamic_cast< const ast::FunctionDecl * > ( func ) ) {
     276                                        if ( dtorFunc->type->forall.empty() ) {
     277                                                // simple case where the destructor is a monomorphic function call - can simply
     278                                                // use that function as the cleanup function.
     279                                                return func;
    294280                                        }
    295281                                }
    296282                        }
    297 
    298                         // otherwise the cleanup is more complicated - need to build a single argument cleanup function that
    299                         // wraps the more complicated code.
    300                         static UniqueName dtorNamer( "__cleanup_dtor" );
    301                         std::string name = dtorNamer.newName();
    302                         ast::FunctionDecl * dtorFunc = SymTab::genDefaultFunc( loc, name, objDecl->type->stripReferences(), false );
    303                         stmtsToAdd.push_back( new ast::DeclStmt(loc, dtorFunc ) );
    304 
    305                         // the original code contains uses of objDecl - replace them with the newly generated 'this' parameter.
    306                         const ast::ObjectDecl * thisParam = getParamThis( dtorFunc );
    307                         const ast::Expr * replacement = new ast::VariableExpr( loc, thisParam );
    308 
    309                         auto base = replacement->result->stripReferences();
    310                         if ( dynamic_cast< const ast::ArrayType * >( base ) || dynamic_cast< const ast::TupleType * > ( base ) ) {
    311                                 // need to cast away reference for array types, since the destructor is generated without the reference type,
    312                                 // and for tuple types since tuple indexing does not work directly on a reference
    313                                 replacement = new ast::CastExpr( replacement, base );
    314                         }
    315                         auto dtor = ast::DeclReplacer::replace( input, ast::DeclReplacer::ExprMap{ std::make_pair( objDecl, replacement ) } );
    316                         auto mutStmts = dtorFunc->stmts.get_and_mutate();
    317                         mutStmts->push_back(strict_dynamic_cast<const ast::Stmt *>( dtor ));
    318                         dtorFunc->stmts = mutStmts;
    319 
    320                         return dtorFunc;
    321                 }
    322 
    323                 void StmtExprResult::link( std::list<ast::ptr<ast::Decl> > & translationUnit ) {
    324                         ast::Pass<StmtExprResult> linker;
    325                         accept_all( translationUnit, linker );
    326                 }
    327 
    328                 void SplitExpressions::split( std::list<ast::ptr<ast::Decl> > & translationUnit ) {
    329                         ast::Pass<SplitExpressions> splitter;
    330                         accept_all( translationUnit, splitter );
    331                 }
    332 
    333                 void InsertImplicitCalls::insert( std::list<ast::ptr<ast::Decl> > & translationUnit ) {
    334                         ast::Pass<InsertImplicitCalls> inserter;
    335                         accept_all( translationUnit, inserter );
    336                 }
    337 
    338                 void ResolveCopyCtors::resolveImplicitCalls( std::list< ast::ptr<ast::Decl> > & translationUnit ) {
    339                         ast::Pass<ResolveCopyCtors> resolver;
    340                         accept_all( translationUnit, resolver );
    341                 }
    342 
    343                 void FixInit::fixInitializers( std::list< ast::ptr<ast::Decl> > & translationUnit ) {
    344                         ast::Pass<FixInit> fixer;
    345 
    346                         // can't use mutateAll, because need to insert declarations at top-level
    347                         // can't use DeclMutator, because sometimes need to insert IfStmt, etc.
    348                         SemanticErrorException errors;
    349                         for ( auto i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
    350                                 try {
    351                                         // maybeAccept( *i, fixer ); translationUnit should never contain null
    352                                         *i = (*i)->accept(fixer);
    353                                         translationUnit.splice( i, fixer.core.staticDtorDecls );
    354                                 } catch( SemanticErrorException &e ) {
    355                                         errors.append( e );
    356                                 } // try
    357                         } // for
    358                         if ( ! errors.isEmpty() ) {
    359                                 throw errors;
     283                }
     284
     285                // otherwise the cleanup is more complicated - need to build a single argument cleanup function that
     286                // wraps the more complicated code.
     287                static UniqueName dtorNamer( "__cleanup_dtor" );
     288                std::string name = dtorNamer.newName();
     289                ast::FunctionDecl * dtorFunc = SymTab::genDefaultFunc( loc, name, objDecl->type->stripReferences(), false );
     290                stmtsToAdd.push_back( new ast::DeclStmt(loc, dtorFunc ) );
     291
     292                // the original code contains uses of objDecl - replace them with the newly generated 'this' parameter.
     293                const ast::ObjectDecl * thisParam = getParamThis( dtorFunc );
     294                const ast::Expr * replacement = new ast::VariableExpr( loc, thisParam );
     295
     296                auto base = replacement->result->stripReferences();
     297                if ( dynamic_cast< const ast::ArrayType * >( base ) || dynamic_cast< const ast::TupleType * > ( base ) ) {
     298                        // need to cast away reference for array types, since the destructor is generated without the reference type,
     299                        // and for tuple types since tuple indexing does not work directly on a reference
     300                        replacement = new ast::CastExpr( replacement, base );
     301                }
     302                auto dtor = ast::DeclReplacer::replace( input, ast::DeclReplacer::ExprMap{ std::make_pair( objDecl, replacement ) } );
     303                auto mutStmts = dtorFunc->stmts.get_and_mutate();
     304                mutStmts->push_back(strict_dynamic_cast<const ast::Stmt *>( dtor ));
     305                dtorFunc->stmts = mutStmts;
     306
     307                return dtorFunc;
     308        }
     309
     310        void FixInit::fixInitializers( std::list< ast::ptr<ast::Decl> > & translationUnit ) {
     311                ast::Pass<FixInit> fixer;
     312
     313                // can't use mutateAll, because need to insert declarations at top-level
     314                // can't use DeclMutator, because sometimes need to insert IfStmt, etc.
     315                SemanticErrorException errors;
     316                for ( auto i = translationUnit.begin(); i != translationUnit.end(); ++i ) {
     317                        try {
     318                                // maybeAccept( *i, fixer ); translationUnit should never contain null
     319                                *i = (*i)->accept(fixer);
     320                                translationUnit.splice( i, fixer.core.staticDtorDecls );
     321                        } catch( SemanticErrorException &e ) {
     322                                errors.append( e );
     323                        } // try
     324                } // for
     325                if ( ! errors.isEmpty() ) {
     326                        throw errors;
     327                } // if
     328        }
     329
     330        const ast::StmtExpr * StmtExprResult::previsit( const ast::StmtExpr * stmtExpr ) {
     331                // we might loose the result expression here so add a pointer to trace back
     332                assert( stmtExpr->result );
     333                const ast::Type * result = stmtExpr->result;
     334                if ( ! result->isVoid() ) {
     335                        auto mutExpr = mutate(stmtExpr);
     336                        const ast::CompoundStmt * body = mutExpr->stmts;
     337                        assert( ! body->kids.empty() );
     338                        mutExpr->resultExpr = body->kids.back().strict_as<ast::ExprStmt>();
     339                        return mutExpr;
     340                }
     341                return stmtExpr;
     342        }
     343
     344        ast::Stmt * SplitExpressions::postvisit( const ast::ExprStmt * stmt ) {
     345                // wrap each top-level ExprStmt in a block so that destructors for argument and return temporaries are destroyed
     346                // in the correct places
     347                ast::CompoundStmt * ret = new ast::CompoundStmt( stmt->location, { stmt } );
     348                return ret;
     349        }
     350
     351        void SplitExpressions::previsit( const ast::TupleAssignExpr * ) {
     352                // don't do this within TupleAssignExpr, since it is already broken up into multiple expressions
     353                visit_children = false;
     354        }
     355
     356        // Relatively simple structural comparison for expressions, needed to determine
     357        // if two expressions are "the same" (used to determine if self assignment occurs)
     358        struct StructuralChecker {
     359                // Strip all casts and then dynamic_cast.
     360                template<typename T>
     361                static const T * cast( const ast::Expr * expr ) {
     362                        // this might be too permissive. It's possible that only particular casts are relevant.
     363                        while ( auto cast = dynamic_cast< const ast::CastExpr * >( expr ) ) {
     364                                expr = cast->arg;
     365                        }
     366                        return dynamic_cast< const T * >( expr );
     367                }
     368
     369                void previsit( const ast::Expr * ) {
     370                        // anything else does not qualify
     371                        result = false;
     372                }
     373
     374                // ignore casts
     375                void previsit( const ast::CastExpr * ) {}
     376
     377                void previsit( const ast::MemberExpr * memExpr ) {
     378                        if ( auto otherMember = cast< ast::MemberExpr >( other ) ) {
     379                                if ( otherMember->member == memExpr->member ) {
     380                                        other = otherMember->aggregate;
     381                                        return;
     382                                }
     383                        }
     384                        result = false;
     385                }
     386
     387                void previsit( const ast::VariableExpr * varExpr ) {
     388                        if ( auto otherVar = cast< ast::VariableExpr >( other ) ) {
     389                                if ( otherVar->var == varExpr->var ) {
     390                                        return;
     391                                }
     392                        }
     393                        result = false;
     394                }
     395
     396                void previsit( const ast::AddressExpr * ) {
     397                        if ( auto addrExpr = cast< ast::AddressExpr >( other ) ) {
     398                                other = addrExpr->arg;
     399                                return;
     400                        }
     401                        result = false;
     402                }
     403
     404                const ast::Expr * other;
     405                bool result = true;
     406                StructuralChecker( const ast::Expr * other ) : other(other) {}
     407        };
     408
     409        bool structurallySimilar( const ast::Expr * e1, const ast::Expr * e2 ) {
     410                return ast::Pass<StructuralChecker>::read( e1, e2 );
     411        }
     412
     413        void SelfAssignChecker::previsit( const ast::ApplicationExpr * appExpr ) {
     414                auto function = getFunction( appExpr );
     415                if ( function->name == "?=?" ) { // doesn't use isAssignment, because ?+=?, etc. should not count as self-assignment
     416                        if ( appExpr->args.size() == 2 ) {
     417                                // check for structural similarity (same variable use, ignore casts, etc. - but does not look too deeply, anything looking like a function is off limits)
     418                                if ( structurallySimilar( appExpr->args.front(), appExpr->args.back() ) ) {
     419                                        SemanticWarning( appExpr->location, Warning::SelfAssignment, toCString( appExpr->args.front() ) );
     420                                }
     421                        }
     422                }
     423        }
     424
     425        const ast::Expr * InsertImplicitCalls::postvisit( const ast::ApplicationExpr * appExpr ) {
     426                if ( auto function = appExpr->func.as<ast::VariableExpr>() ) {
     427                        if ( function->var->linkage.is_builtin ) {
     428                                // optimization: don't need to copy construct in order to call intrinsic functions
     429                                return appExpr;
     430                        } else if ( auto funcDecl = function->var.as<ast::DeclWithType>() ) {
     431                                auto ftype = dynamic_cast< const ast::FunctionType * >( GenPoly::getFunctionType( funcDecl->get_type() ) );
     432                                assertf( ftype, "Function call without function type: %s", toString( funcDecl ).c_str() );
     433                                if ( CodeGen::isConstructor( funcDecl->name ) && ftype->params.size() == 2 ) {
     434                                        auto t1 = getPointerBase( ftype->params.front() );
     435                                        auto t2 = ftype->params.back();
     436                                        assert( t1 );
     437
     438                                        if ( ResolvExpr::typesCompatible( t1, t2 ) ) {
     439                                                // optimization: don't need to copy construct in order to call a copy constructor
     440                                                return appExpr;
     441                                        } // if
     442                                } else if ( CodeGen::isDestructor( funcDecl->name ) ) {
     443                                        // correctness: never copy construct arguments to a destructor
     444                                        return appExpr;
     445                                } // if
    360446                        } // if
    361                 }
    362 
    363                 void InsertDtors::insert( std::list< ast::ptr<ast::Decl> > & translationUnit ) {
    364                         ast::Pass<LabelFinder> finder;
    365                         ast::Pass<InsertDtors> inserter( finder );
    366                         accept_all( translationUnit, inserter );
    367                 }
    368 
    369                 void GenStructMemberCalls::generate( std::list< ast::ptr<ast::Decl> > & translationUnit ) {
    370                         ast::Pass<GenStructMemberCalls> warner;
    371                         accept_all( translationUnit, warner );
    372                 }
    373 
    374                 void FixCtorExprs::fix( std::list< ast::ptr<ast::Decl> > & translationUnit ) {
    375                         ast::Pass<FixCtorExprs> fixer;
    376                         accept_all( translationUnit, fixer );
    377                 }
    378 
    379                 const ast::StmtExpr * StmtExprResult::previsit( const ast::StmtExpr * stmtExpr ) {
    380                         // we might loose the result expression here so add a pointer to trace back
    381                         assert( stmtExpr->result );
    382                         const ast::Type * result = stmtExpr->result;
    383                         if ( ! result->isVoid() ) {
    384                                 auto mutExpr = mutate(stmtExpr);
    385                                 const ast::CompoundStmt * body = mutExpr->stmts;
    386                                 assert( ! body->kids.empty() );
    387                                 mutExpr->resultExpr = body->kids.back().strict_as<ast::ExprStmt>();
     447                } // if
     448                CP_CTOR_PRINT( std::cerr << "InsertImplicitCalls: adding a wrapper " << appExpr << std::endl; )
     449
     450                // wrap each function call so that it is easy to identify nodes that have to be copy constructed
     451                ast::ptr<ast::TypeSubstitution> tmp = appExpr->env;
     452                auto mutExpr = mutate(appExpr);
     453                mutExpr->env = nullptr;
     454
     455                auto expr = new ast::ImplicitCopyCtorExpr( appExpr->location, mutExpr );
     456                // Move the type substitution to the new top-level, if it is attached to the appExpr.
     457                // Ensure it is not deleted with the ImplicitCopyCtorExpr by removing it before deletion.
     458                // The substitution is needed to obtain the type of temporary variables so that copy constructor
     459                // calls can be resolved.
     460                assert( typeSubs );
     461                // assert (mutExpr->env);
     462                expr->env = tmp;
     463                // mutExpr->env = nullptr;
     464                //std::swap( expr->env, appExpr->env );
     465                return expr;
     466        }
     467
     468        void ResolveCopyCtors::previsit(const ast::Expr * expr) {
     469                if (expr->env) {
     470                        GuardValue(env);
     471                        GuardValue(envModified);
     472                        env = expr->env->clone();
     473                        envModified = false;
     474                }
     475        }
     476
     477        const ast::Expr * ResolveCopyCtors::postvisit(const ast::Expr * expr) {
     478                if (expr->env) {
     479                        if (envModified) {
     480                                auto mutExpr = mutate(expr);
     481                                mutExpr->env = env;
    388482                                return mutExpr;
    389483                        }
    390                         return stmtExpr;
    391                 }
    392 
    393                 ast::Stmt * SplitExpressions::postvisit( const ast::ExprStmt * stmt ) {
    394                         // wrap each top-level ExprStmt in a block so that destructors for argument and return temporaries are destroyed
    395                         // in the correct places
    396                         ast::CompoundStmt * ret = new ast::CompoundStmt( stmt->location, { stmt } );
    397                         return ret;
    398                 }
    399 
    400                 void SplitExpressions::previsit( const ast::TupleAssignExpr * ) {
    401                         // don't do this within TupleAssignExpr, since it is already broken up into multiple expressions
    402                         visit_children = false;
    403                 }
    404 
    405                 // Relatively simple structural comparison for expressions, needed to determine
    406                 // if two expressions are "the same" (used to determine if self assignment occurs)
    407                 struct StructuralChecker {
    408                         const ast::Expr * stripCasts( const ast::Expr * expr ) {
    409                                 // this might be too permissive. It's possible that only particular casts are relevant.
    410                                 while ( auto cast = dynamic_cast< const ast::CastExpr * >( expr ) ) {
    411                                         expr = cast->arg;
     484                        else {
     485                                // env was not mutated, skip and delete the shallow copy
     486                                delete env;
     487                                return expr;
     488                        }
     489                }
     490                else {
     491                        return expr;
     492                }
     493        }
     494
     495        bool ResolveCopyCtors::skipCopyConstruct( const ast::Type * type ) { return ! isConstructable( type ); }
     496
     497        const ast::Expr * ResolveCopyCtors::makeCtorDtor( const std::string & fname, const ast::ObjectDecl * var, const ast::Expr * cpArg ) {
     498                assert( var );
     499                assert (var->isManaged());
     500                assert (!cpArg || cpArg->isManaged());
     501                // arrays are not copy constructed, so this should always be an ExprStmt
     502                ast::ptr< ast::Stmt > stmt = genCtorDtor(var->location, fname, var, cpArg );
     503                assertf( stmt, "ResolveCopyCtors: genCtorDtor returned nullptr: %s / %s / %s", fname.c_str(), toString( var ).c_str(), toString( cpArg ).c_str() );
     504                auto exprStmt = stmt.strict_as<ast::ImplicitCtorDtorStmt>()->callStmt.strict_as<ast::ExprStmt>();
     505                ast::ptr<ast::Expr> untyped = exprStmt->expr; // take ownership of expr
     506                // exprStmt->expr = nullptr;
     507
     508                // resolve copy constructor
     509                // should only be one alternative for copy ctor and dtor expressions, since all arguments are fixed
     510                // (VariableExpr and already resolved expression)
     511                CP_CTOR_PRINT( std::cerr << "ResolvingCtorDtor " << untyped << std::endl; )
     512                ast::ptr<ast::Expr> resolved = ResolvExpr::findVoidExpression(untyped, symtab);
     513                assert( resolved );
     514                if ( resolved->env ) {
     515                        // Extract useful information and discard new environments. Keeping them causes problems in PolyMutator passes.
     516                        env->add( *resolved->env );
     517                        envModified = true;
     518                        // delete resolved->env;
     519                        auto mut = mutate(resolved.get());
     520                        assertf(mut == resolved.get(), "newly resolved expression must be unique");
     521                        mut->env = nullptr;
     522                } // if
     523                // delete stmt;
     524                if ( auto assign = resolved.as<ast::TupleAssignExpr>() ) {
     525                        // fix newly generated StmtExpr
     526                        previsit( assign->stmtExpr );
     527                }
     528                return resolved.release();
     529        }
     530
     531        ast::ptr<ast::Expr> ResolveCopyCtors::copyConstructArg(
     532                const ast::Expr * arg, const ast::ImplicitCopyCtorExpr * impCpCtorExpr, const ast::Type * formal )
     533        {
     534                static UniqueName tempNamer("_tmp_cp");
     535                assert( env );
     536                const CodeLocation loc = impCpCtorExpr->location;
     537                // CP_CTOR_PRINT( std::cerr << "Type Substitution: " << *env << std::endl; )
     538                assert( arg->result );
     539                ast::ptr<ast::Type> result = arg->result;
     540                if ( skipCopyConstruct( result ) ) return arg; // skip certain non-copyable types
     541
     542                // type may involve type variables, so apply type substitution to get temporary variable's actual type,
     543                // since result type may not be substituted (e.g., if the type does not appear in the parameter list)
     544                // Use applyFree so that types bound in function pointers are not substituted, e.g. in forall(dtype T) void (*)(T).
     545
     546                // xxx - this originally mutates arg->result in place. is it correct?
     547                result = env->applyFree( result.get() ).node;
     548                auto mutResult = result.get_and_mutate();
     549                mutResult->set_const(false);
     550
     551                auto mutArg = mutate(arg);
     552                mutArg->result = mutResult;
     553
     554                ast::ptr<ast::Expr> guard = mutArg;
     555
     556                ast::ptr<ast::ObjectDecl> tmp = new ast::ObjectDecl({}, "__tmp", mutResult, nullptr );
     557
     558                // create and resolve copy constructor
     559                CP_CTOR_PRINT( std::cerr << "makeCtorDtor for an argument" << std::endl; )
     560                auto cpCtor = makeCtorDtor( "?{}", tmp, mutArg );
     561
     562                if ( auto appExpr = dynamic_cast< const ast::ApplicationExpr * >( cpCtor ) ) {
     563                        // if the chosen constructor is intrinsic, the copy is unnecessary, so
     564                        // don't create the temporary and don't call the copy constructor
     565                        auto function = appExpr->func.strict_as<ast::VariableExpr>();
     566                        if ( function->var->linkage == ast::Linkage::Intrinsic ) {
     567                                // arguments that need to be boxed need a temporary regardless of whether the copy constructor is intrinsic,
     568                                // so that the object isn't changed inside of the polymorphic function
     569                                if ( ! GenPoly::needsBoxing( formal, result, impCpCtorExpr->callExpr, env ) ) {
     570                                        // xxx - should arg->result be mutated? see comment above.
     571                                        return guard;
    412572                                }
    413                                 return expr;
    414                         }
    415 
    416                         void previsit( const ast::Expr * ) {
    417                                 // anything else does not qualify
    418                                 isSimilar = false;
    419                         }
    420 
    421                         template<typename T>
    422                         T * cast( const ast::Expr * node ) {
    423                                 // all expressions need to ignore casts, so this bit has been factored out
    424                                 return dynamic_cast< T * >( stripCasts( node ) );
    425                         }
    426 
    427                         // ignore casts
    428                         void previsit( const ast::CastExpr * ) {}
    429 
    430                         void previsit( const ast::MemberExpr * memExpr ) {
    431                                 if ( auto otherMember = cast< const ast::MemberExpr >( other ) ) {
    432                                         if ( otherMember->member == memExpr->member ) {
    433                                                 other = otherMember->aggregate;
    434                                                 return;
     573                        }
     574                }
     575
     576                // set a unique name for the temporary once it's certain the call is necessary
     577                auto mut = tmp.get_and_mutate();
     578                assertf (mut == tmp, "newly created ObjectDecl must be unique");
     579                mut->name = tempNamer.newName();
     580
     581                // replace argument to function call with temporary
     582                stmtsToAddBefore.push_back( new ast::DeclStmt(loc, tmp ) );
     583                arg = cpCtor;
     584                return destructRet( tmp, arg );
     585
     586                // impCpCtorExpr->dtors.push_front( makeCtorDtor( "^?{}", tmp ) );
     587        }
     588
     589        ast::Expr * ResolveCopyCtors::destructRet( const ast::ObjectDecl * ret, const ast::Expr * arg ) {
     590                // TODO: refactor code for generating cleanup attribute, since it's common and reused in ~3-4 places
     591                // check for existing cleanup attribute before adding another(?)
     592                // need to add __Destructor for _tmp_cp variables as well
     593
     594                assertf( ast::dtorStruct && ast::dtorStruct->members.size() == 2, "Destructor generation requires __Destructor definition." );
     595                assertf( ast::dtorStructDestroy, "Destructor generation requires __destroy_Destructor." );
     596
     597                const CodeLocation loc = ret->location;
     598
     599                // generate a __Destructor for ret that calls the destructor
     600                auto res = makeCtorDtor( "^?{}", ret );
     601                auto dtor = mutate(res);
     602
     603                // if the chosen destructor is intrinsic, elide the generated dtor handler
     604                if ( arg && isIntrinsicCallExpr( dtor ) ) {
     605                        return new ast::CommaExpr(loc, arg, new ast::VariableExpr(loc, ret ) );
     606                        // return;
     607                }
     608
     609                if ( ! dtor->env ) dtor->env = maybeClone( env );
     610                auto dtorFunc = getDtorFunc( ret, new ast::ExprStmt(loc, dtor ), stmtsToAddBefore );
     611
     612                auto dtorStructType = new ast::StructInstType(ast::dtorStruct);
     613
     614                // what does this do???
     615                dtorStructType->params.push_back( new ast::TypeExpr(loc, new ast::VoidType() ) );
     616
     617                // cast destructor pointer to void (*)(void *), to silence GCC incompatible pointer warnings
     618                auto dtorFtype = new ast::FunctionType();
     619                dtorFtype->params.push_back( new ast::PointerType(new ast::VoidType( ) ) );
     620                auto dtorType = new ast::PointerType( dtorFtype );
     621
     622                static UniqueName namer( "_ret_dtor" );
     623                auto retDtor = new ast::ObjectDecl(loc, namer.newName(), dtorStructType, new ast::ListInit(loc, { new ast::SingleInit(loc, ast::ConstantExpr::null(loc) ), new ast::SingleInit(loc, new ast::CastExpr( new ast::VariableExpr(loc, dtorFunc ), dtorType ) ) } ) );
     624                retDtor->attributes.push_back( new ast::Attribute( "cleanup", { new ast::VariableExpr(loc, ast::dtorStructDestroy ) } ) );
     625                stmtsToAddBefore.push_back( new ast::DeclStmt(loc, retDtor ) );
     626
     627                if ( arg ) {
     628                        auto member = new ast::MemberExpr(loc, ast::dtorStruct->members.front().strict_as<ast::DeclWithType>(), new ast::VariableExpr(loc, retDtor ) );
     629                        auto object = new ast::CastExpr( new ast::AddressExpr( new ast::VariableExpr(loc, ret ) ), new ast::PointerType(new ast::VoidType() ) );
     630                        ast::Expr * assign = createBitwiseAssignment( member, object );
     631                        return new ast::CommaExpr(loc, new ast::CommaExpr(loc, arg, assign ), new ast::VariableExpr(loc, ret ) );
     632                }
     633                return nullptr;
     634                // impCpCtorExpr->get_dtors().push_front( makeCtorDtor( "^?{}", ret ) );
     635        }
     636
     637        const ast::Expr * ResolveCopyCtors::postvisit( const ast::ImplicitCopyCtorExpr *impCpCtorExpr ) {
     638                CP_CTOR_PRINT( std::cerr << "ResolveCopyCtors: " << impCpCtorExpr << std::endl; )
     639
     640                ast::ApplicationExpr * appExpr = mutate(impCpCtorExpr->callExpr.get());
     641                const ast::ObjectDecl * returnDecl = nullptr;
     642                const CodeLocation loc = appExpr->location;
     643
     644                // take each argument and attempt to copy construct it.
     645                auto ftype = GenPoly::getFunctionType( appExpr->func->result );
     646                assert( ftype );
     647                auto & params = ftype->params;
     648                auto iter = params.begin();
     649                for ( auto & arg : appExpr->args ) {
     650                        const ast::Type * formal = nullptr;
     651                        if ( iter != params.end() ) { // does not copy construct C-style variadic arguments
     652                                // DeclarationWithType * param = *iter++;
     653                                formal = *iter++;
     654                        }
     655
     656                        arg = copyConstructArg( arg, impCpCtorExpr, formal );
     657                } // for
     658
     659                // each return value from the call needs to be connected with an ObjectDecl at the call site, which is
     660                // initialized with the return value and is destructed later
     661                // xxx - handle named return values?
     662                const ast::Type * result = appExpr->result;
     663                if ( ! result->isVoid() ) {
     664                        static UniqueName retNamer("_tmp_cp_ret");
     665                        // result = result->clone();
     666                        auto subResult = env->apply( result ).node;
     667                        auto ret = new ast::ObjectDecl(loc, retNamer.newName(), subResult, nullptr );
     668                        auto mutType = mutate(ret->type.get());
     669                        mutType->set_const( false );
     670                        ret->type = mutType;
     671                        returnDecl = ret;
     672                        stmtsToAddBefore.push_back( new ast::DeclStmt(loc, ret ) );
     673                        CP_CTOR_PRINT( std::cerr << "makeCtorDtor for a return" << std::endl; )
     674                } // for
     675                CP_CTOR_PRINT( std::cerr << "after Resolving: " << impCpCtorExpr << std::endl; )
     676                // ------------------------------------------------------
     677
     678                CP_CTOR_PRINT( std::cerr << "Coming out the back..." << impCpCtorExpr << std::endl; )
     679
     680                // detach fields from wrapper node so that it can be deleted without deleting too much
     681
     682                // xxx - actual env might be somewhere else, need to keep invariant
     683
     684                // deletion of wrapper should be handled by pass template now
     685
     686                // impCpCtorExpr->callExpr = nullptr;
     687                assert (appExpr->env == nullptr);
     688                appExpr->env = impCpCtorExpr->env;
     689                // std::swap( impCpCtorExpr->env, appExpr->env );
     690                // assert( impCpCtorExpr->env == nullptr );
     691                // delete impCpCtorExpr;
     692
     693                if ( returnDecl ) {
     694                        ast::Expr * assign = createBitwiseAssignment( new ast::VariableExpr(loc, returnDecl ), appExpr );
     695                        if ( ! dynamic_cast< const ast::ReferenceType * >( result ) ) {
     696                                // destructing reference returns is bad because it can cause multiple destructor calls to the same object - the returned object is not a temporary
     697                                assign = destructRet( returnDecl, assign );
     698                                assert(assign);
     699                        } else {
     700                                assign = new ast::CommaExpr(loc, assign, new ast::VariableExpr(loc, returnDecl ) );
     701                        }
     702                        // move env from appExpr to retExpr
     703                        // std::swap( assign->env, appExpr->env );
     704                        assign->env = appExpr->env;
     705                        // actual env is handled by common routine that replaces WithTypeSubstitution
     706                        return postvisit((const ast::Expr *)assign);
     707                } else {
     708                        return postvisit((const ast::Expr *)appExpr);
     709                } // if
     710        }
     711
     712        const ast::StmtExpr * ResolveCopyCtors::previsit( const ast::StmtExpr * _stmtExpr ) {
     713                // function call temporaries should be placed at statement-level, rather than nested inside of a new statement expression,
     714                // since temporaries can be shared across sub-expressions, e.g.
     715                //   [A, A] f();       // decl
     716                //   g([A] x, [A] y);  // decl
     717                //   g(f());           // call
     718                // f is executed once, so the return temporary is shared across the tuple constructors for x and y.
     719                // Explicitly mutating children instead of mutating the inner compound statement forces the temporaries to be added
     720                // to the outer context, rather than inside of the statement expression.
     721
     722                // call the common routine that replaces WithTypeSubstitution
     723                previsit((const ast::Expr *) _stmtExpr);
     724
     725                visit_children = false;
     726                const CodeLocation loc = _stmtExpr->location;
     727
     728                assert( env );
     729
     730                symtab.enterScope();
     731                // visit all statements
     732                auto stmtExpr = mutate(_stmtExpr);
     733                auto mutStmts = mutate(stmtExpr->stmts.get());
     734
     735                auto & stmts = mutStmts->kids;
     736                for ( auto & stmt : stmts ) {
     737                        stmt = stmt->accept( *visitor );
     738                } // for
     739                stmtExpr->stmts = mutStmts;
     740                symtab.leaveScope();
     741
     742                assert( stmtExpr->result );
     743                // const ast::Type * result = stmtExpr->result;
     744                if ( ! stmtExpr->result->isVoid() ) {
     745                        static UniqueName retNamer("_tmp_stmtexpr_ret");
     746
     747                        // result = result->clone();
     748                        auto result = env->apply( stmtExpr->result.get() ).node;
     749                        if ( ! InitTweak::isConstructable( result ) ) {
     750                                // delete result;
     751                                return stmtExpr;
     752                        }
     753                        auto mutResult = result.get_and_mutate();
     754                        mutResult->set_const(false);
     755
     756                        // create variable that will hold the result of the stmt expr
     757                        auto ret = new ast::ObjectDecl(loc, retNamer.newName(), mutResult, nullptr );
     758                        stmtsToAddBefore.push_back( new ast::DeclStmt(loc, ret ) );
     759
     760                        assertf(
     761                                stmtExpr->resultExpr,
     762                                "Statement-Expression should have a resulting expression at %s:%d",
     763                                stmtExpr->location.filename.c_str(),
     764                                stmtExpr->location.first_line
     765                        );
     766
     767                        const ast::ExprStmt * last = stmtExpr->resultExpr;
     768                        // xxx - if this is non-unique, need to copy while making resultExpr ref
     769                        assertf(last->unique(), "attempt to modify weakly shared statement");
     770                        auto mutLast = mutate(last);
     771                        // above assertion means in-place mutation is OK
     772                        try {
     773                                mutLast->expr = makeCtorDtor( "?{}", ret, mutLast->expr );
     774                        } catch(...) {
     775                                std::cerr << "*CFA internal error: ";
     776                                std::cerr << "can't resolve implicit constructor";
     777                                std::cerr << " at " << stmtExpr->location.filename;
     778                                std::cerr << ":" << stmtExpr->location.first_line << std::endl;
     779
     780                                abort();
     781                        }
     782
     783                        // add destructors after current statement
     784                        stmtsToAddAfter.push_back( new ast::ExprStmt(loc, makeCtorDtor( "^?{}", ret ) ) );
     785
     786                        // must have a non-empty body, otherwise it wouldn't have a result
     787                        assert( ! stmts.empty() );
     788
     789                        // if there is a return decl, add a use as the last statement; will not have return decl on non-constructable returns
     790                        stmts.push_back( new ast::ExprStmt(loc, new ast::VariableExpr(loc, ret ) ) );
     791                } // if
     792
     793                assert( stmtExpr->returnDecls.empty() );
     794                assert( stmtExpr->dtors.empty() );
     795
     796                return stmtExpr;
     797        }
     798
     799        // to prevent warnings ('_unq0' may be used uninitialized in this function),
     800        // insert an appropriate zero initializer for UniqueExpr temporaries.
     801        ast::Init * makeInit( const ast::Type * t ) {
     802                if ( auto inst = dynamic_cast< const ast::StructInstType * >( t ) ) {
     803                        // initizer for empty struct must be empty
     804                        if ( inst->base->members.empty() ) return new ast::ListInit({}, {});
     805                } else if ( auto inst = dynamic_cast< const ast::UnionInstType * >( t ) ) {
     806                        // initizer for empty union must be empty
     807                        if ( inst->base->members.empty() ) return new ast::ListInit({}, {});
     808                }
     809
     810                return new ast::ListInit( {}, { new ast::SingleInit( {}, ast::ConstantExpr::from_int({}, 0) ) } );
     811        }
     812
     813        const ast::UniqueExpr * ResolveCopyCtors::previsit( const ast::UniqueExpr * unqExpr ) {
     814                visit_children = false;
     815                // xxx - hack to prevent double-handling of unique exprs, otherwise too many temporary variables and destructors are generated
     816                static std::unordered_map< int, const ast::UniqueExpr * > unqMap;
     817                auto mutExpr = mutate(unqExpr);
     818                if ( ! unqMap.count( unqExpr->id ) ) {
     819                        // resolve expr and find its
     820
     821                        auto impCpCtorExpr = mutExpr->expr.as<ast::ImplicitCopyCtorExpr>();
     822                        // PassVisitor<ResolveCopyCtors> fixer;
     823
     824                        mutExpr->expr = mutExpr->expr->accept( *visitor );
     825                        // it should never be necessary to wrap a void-returning expression in a UniqueExpr - if this assumption changes, this needs to be rethought
     826                        assert( unqExpr->result );
     827                        if ( impCpCtorExpr ) {
     828                                auto comma = unqExpr->expr.strict_as<ast::CommaExpr>();
     829                                auto var = comma->arg2.strict_as<ast::VariableExpr>();
     830                                // note the variable used as the result from the call
     831                                mutExpr->var = var;
     832                        } else {
     833                                // expr isn't a call expr, so create a new temporary variable to use to hold the value of the unique expression
     834                                mutExpr->object = new ast::ObjectDecl( mutExpr->location, toString("_unq", mutExpr->id), mutExpr->result, makeInit( mutExpr->result ) );
     835                                mutExpr->var = new ast::VariableExpr( mutExpr->location, mutExpr->object );
     836                        }
     837
     838                        // stmtsToAddBefore.splice( stmtsToAddBefore.end(), fixer.pass.stmtsToAddBefore );
     839                        // stmtsToAddAfter.splice( stmtsToAddAfter.end(), fixer.pass.stmtsToAddAfter );
     840                        unqMap[mutExpr->id] = mutExpr;
     841                } else {
     842                        // take data from other UniqueExpr to ensure consistency
     843                        // delete unqExpr->get_expr();
     844                        mutExpr->expr = unqMap[mutExpr->id]->expr;
     845                        // delete unqExpr->result;
     846                        mutExpr->result = mutExpr->expr->result;
     847                }
     848                return mutExpr;
     849        }
     850
     851        const ast::DeclWithType * FixInit::postvisit( const ast::ObjectDecl *_objDecl ) {
     852                const CodeLocation loc = _objDecl->location;
     853
     854                // since this removes the init field from objDecl, it must occur after children are mutated (i.e. postvisit)
     855                if ( ast::ptr<ast::ConstructorInit> ctorInit = _objDecl->init.as<ast::ConstructorInit>() ) {
     856                        auto objDecl = mutate(_objDecl);
     857
     858                        // could this be non-unique?
     859                        if (objDecl != _objDecl) {
     860                                std::cerr << "FixInit: non-unique object decl " << objDecl->location << objDecl->name << std::endl;
     861                        }
     862                        // a decision should have been made by the resolver, so ctor and init are not both non-NULL
     863                        assert( ! ctorInit->ctor || ! ctorInit->init );
     864                        if ( const ast::Stmt * ctor = ctorInit->ctor ) {
     865                                if ( objDecl->storage.is_static ) {
     866                                        // originally wanted to take advantage of gcc nested functions, but
     867                                        // we get memory errors with this approach. To remedy this, the static
     868                                        // variable is hoisted when the destructor needs to be called.
     869                                        //
     870                                        // generate:
     871                                        // static T __objName_static_varN;
     872                                        // void __objName_dtor_atexitN() {
     873                                        //   __dtor__...;
     874                                        // }
     875                                        // int f(...) {
     876                                        //   ...
     877                                        //   static bool __objName_uninitialized = true;
     878                                        //   if (__objName_uninitialized) {
     879                                        //     __ctor(__objName);
     880                                        //     __objName_uninitialized = false;
     881                                        //     atexit(__objName_dtor_atexitN);
     882                                        //   }
     883                                        //   ...
     884                                        // }
     885
     886                                        static UniqueName dtorCallerNamer( "_dtor_atexit" );
     887
     888                                        // static bool __objName_uninitialized = true
     889                                        auto boolType = new ast::BasicType( ast::BasicType::Kind::Bool );
     890                                        auto boolInitExpr = new ast::SingleInit(loc, ast::ConstantExpr::from_int(loc, 1 ) );
     891                                        auto isUninitializedVar = new ast::ObjectDecl(loc, objDecl->mangleName + "_uninitialized", boolType, boolInitExpr, ast::Storage::Static, ast::Linkage::Cforall);
     892                                        isUninitializedVar->fixUniqueId();
     893
     894                                        // __objName_uninitialized = false;
     895                                        auto setTrue = new ast::UntypedExpr(loc, new ast::NameExpr(loc, "?=?" ) );
     896                                        setTrue->args.push_back( new ast::VariableExpr(loc, isUninitializedVar ) );
     897                                        setTrue->args.push_back( ast::ConstantExpr::from_int(loc, 0 ) );
     898
     899                                        // generate body of if
     900                                        auto initStmts = new ast::CompoundStmt(loc);
     901                                        auto & body = initStmts->kids;
     902                                        body.push_back( ctor );
     903                                        body.push_back( new ast::ExprStmt(loc, setTrue ) );
     904
     905                                        // put it all together
     906                                        auto ifStmt = new ast::IfStmt(loc, new ast::VariableExpr(loc, isUninitializedVar ), initStmts, 0 );
     907                                        stmtsToAddAfter.push_back( new ast::DeclStmt(loc, isUninitializedVar ) );
     908                                        stmtsToAddAfter.push_back( ifStmt );
     909
     910                                        const ast::Stmt * dtor = ctorInit->dtor;
     911
     912                                        // these should be automatically managed once reassigned
     913                                        // objDecl->set_init( nullptr );
     914                                        // ctorInit->set_ctor( nullptr );
     915                                        // ctorInit->set_dtor( nullptr );
     916                                        if ( dtor ) {
     917                                                // if the object has a non-trivial destructor, have to
     918                                                // hoist it and the object into the global space and
     919                                                // call the destructor function with atexit.
     920
     921                                                // Statement * dtorStmt = dtor->clone();
     922
     923                                                // void __objName_dtor_atexitN(...) {...}
     924                                                ast::FunctionDecl * dtorCaller = new ast::FunctionDecl(loc, objDecl->mangleName + dtorCallerNamer.newName(), {}, {}, {}, new ast::CompoundStmt(loc, {dtor}), ast::Storage::Static, ast::Linkage::C );
     925                                                dtorCaller->fixUniqueId();
     926                                                // dtorCaller->stmts->push_back( dtor );
     927
     928                                                // atexit(dtor_atexit);
     929                                                auto callAtexit = new ast::UntypedExpr(loc, new ast::NameExpr(loc, "atexit" ) );
     930                                                callAtexit->args.push_back( new ast::VariableExpr(loc, dtorCaller ) );
     931
     932                                                body.push_back( new ast::ExprStmt(loc, callAtexit ) );
     933
     934                                                // hoist variable and dtor caller decls to list of decls that will be added into global scope
     935                                                staticDtorDecls.push_back( objDecl );
     936                                                staticDtorDecls.push_back( dtorCaller );
     937
     938                                                // need to rename object uniquely since it now appears
     939                                                // at global scope and there could be multiple function-scoped
     940                                                // static variables with the same name in different functions.
     941                                                // Note: it isn't sufficient to modify only the mangleName, because
     942                                                // then subsequent Indexer passes can choke on seeing the object's name
     943                                                // if another object has the same name and type. An unfortunate side-effect
     944                                                // of renaming the object is that subsequent NameExprs may fail to resolve,
     945                                                // but there shouldn't be any remaining past this point.
     946                                                static UniqueName staticNamer( "_static_var" );
     947                                                objDecl->name = objDecl->name + staticNamer.newName();
     948                                                objDecl->mangleName = Mangle::mangle( objDecl );
     949
     950                                                // xxx - temporary hack: need to return a declaration, but want to hoist the current object out of this scope
     951                                                // create a new object which is never used
     952                                                static UniqueName dummyNamer( "_dummy" );
     953                                                auto dummy = new ast::ObjectDecl(loc, dummyNamer.newName(), new ast::PointerType(new ast::VoidType()), nullptr, ast::Storage::Static, ast::Linkage::Cforall, 0, { new ast::Attribute("unused") } );
     954                                                // delete ctorInit;
     955                                                return dummy;
     956                                        } else {
     957                                                objDecl->init = nullptr;
     958                                                return objDecl;
     959                                        }
     960                                } else {
     961                                        auto implicit = strict_dynamic_cast< const ast::ImplicitCtorDtorStmt * > ( ctor );
     962                                        auto ctorStmt = implicit->callStmt.as<ast::ExprStmt>();
     963                                        const ast::ApplicationExpr * ctorCall = nullptr;
     964                                        if ( ctorStmt && (ctorCall = isIntrinsicCallExpr( ctorStmt->expr )) && ctorCall->args.size() == 2 ) {
     965                                                // clean up intrinsic copy constructor calls by making them into SingleInits
     966                                                const ast::Expr * ctorArg = ctorCall->args.back();
     967                                                // ctorCall should be gone afterwards
     968                                                auto mutArg = mutate(ctorArg);
     969                                                mutArg->env = ctorCall->env;
     970                                                // std::swap( ctorArg->env, ctorCall->env );
     971                                                objDecl->init = new ast::SingleInit(loc, mutArg );
     972
     973                                                // ctorCall->args.pop_back();
     974                                        } else {
     975                                                stmtsToAddAfter.push_back( ctor );
     976                                                objDecl->init = nullptr;
     977                                                // ctorInit->ctor = nullptr;
     978                                        }
     979
     980                                        const ast::Stmt * dtor = ctorInit->dtor;
     981                                        if ( dtor ) {
     982                                                auto implicit = strict_dynamic_cast< const ast::ImplicitCtorDtorStmt * >( dtor );
     983                                                const ast::Stmt * dtorStmt = implicit->callStmt;
     984
     985                                                // don't need to call intrinsic dtor, because it does nothing, but
     986                                                // non-intrinsic dtors must be called
     987                                                if ( ! isIntrinsicSingleArgCallStmt( dtorStmt ) ) {
     988                                                        // set dtor location to the object's location for error messages
     989                                                        auto dtorFunc = getDtorFunc( objDecl, dtorStmt, stmtsToAddBefore );
     990                                                        objDecl->attributes.push_back( new ast::Attribute( "cleanup", { new ast::VariableExpr(loc, dtorFunc ) } ) );
     991                                                        // ctorInit->dtor = nullptr;
     992                                                } // if
     993                                        }
     994                                } // if
     995                        } else if ( const ast::Init * init = ctorInit->init ) {
     996                                objDecl->init = init;
     997                                // ctorInit->init = nullptr;
     998                        } else {
     999                                // no constructor and no initializer, which is okay
     1000                                objDecl->init = nullptr;
     1001                        } // if
     1002                        // delete ctorInit;
     1003                        return objDecl;
     1004                } // if
     1005                return _objDecl;
     1006        }
     1007
     1008        void ObjDeclCollector::previsit( const ast::CompoundStmt * ) {
     1009                GuardValue( curVars );
     1010        }
     1011
     1012        void ObjDeclCollector::previsit( const ast::DeclStmt * stmt ) {
     1013                // keep track of all variables currently in scope
     1014                if ( auto objDecl = stmt->decl.as<ast::ObjectDecl>() ) {
     1015                        curVars.push_back( objDecl );
     1016                } // if
     1017        }
     1018
     1019        void LabelFinder::previsit( const ast::Stmt * stmt ) {
     1020                // for each label, remember the variables in scope at that label.
     1021                for ( auto l : stmt->labels ) {
     1022                        vars[l] = curVars;
     1023                } // for
     1024        }
     1025
     1026        void LabelFinder::previsit( const ast::CompoundStmt * stmt ) {
     1027                previsit( (const ast::Stmt *) stmt );
     1028                Parent::previsit( stmt );
     1029        }
     1030
     1031        void LabelFinder::previsit( const ast::DeclStmt * stmt ) {
     1032                previsit( (const ast::Stmt *)stmt );
     1033                Parent::previsit( stmt );
     1034        }
     1035
     1036
     1037        void InsertDtors::previsit( const ast::FunctionDecl * funcDecl ) {
     1038                // each function needs to have its own set of labels
     1039                GuardValue( labelVars );
     1040                labelVars.clear();
     1041                // LabelFinder does not recurse into FunctionDecl, so need to visit
     1042                // its children manually.
     1043                if (funcDecl->type) funcDecl->type->accept(finder);
     1044                // maybeAccept( funcDecl->type, finder );
     1045                if (funcDecl->stmts) funcDecl->stmts->accept(finder) ;
     1046
     1047                // all labels for this function have been collected, insert destructors as appropriate via implicit recursion.
     1048        }
     1049
     1050        // Handle break/continue/goto in the same manner as C++.  Basic idea: any objects that are in scope at the
     1051        // BranchStmt but not at the labelled (target) statement must be destructed.  If there are any objects in scope
     1052        // at the target location but not at the BranchStmt then those objects would be uninitialized so notify the user
     1053        // of the error.  See C++ Reference 6.6 Jump Statements for details.
     1054        void InsertDtors::handleGoto( const ast::BranchStmt * stmt ) {
     1055                // can't do anything for computed goto
     1056                if ( stmt->computedTarget ) return;
     1057
     1058                assertf( stmt->target.name != "", "BranchStmt missing a label: %s", toString( stmt ).c_str() );
     1059                // S_L = lvars = set of objects in scope at label definition
     1060                // S_G = curVars = set of objects in scope at goto statement
     1061                ObjectSet & lvars = labelVars[ stmt->target ];
     1062
     1063                DTOR_PRINT(
     1064                        std::cerr << "at goto label: " << stmt->target.name << std::endl;
     1065                        std::cerr << "S_G = " << printSet( curVars ) << std::endl;
     1066                        std::cerr << "S_L = " << printSet( lvars ) << std::endl;
     1067                )
     1068
     1069
     1070                // std::set_difference requires that the inputs be sorted.
     1071                lvars.sort();
     1072                curVars.sort();
     1073
     1074                ObjectSet diff;
     1075                // S_L-S_G results in set of objects whose construction is skipped - it's an error if this set is non-empty
     1076                std::set_difference( lvars.begin(), lvars.end(), curVars.begin(), curVars.end(), std::inserter( diff, diff.begin() ) );
     1077                DTOR_PRINT(
     1078                        std::cerr << "S_L-S_G = " << printSet( diff ) << std::endl;
     1079                )
     1080                if ( ! diff.empty() ) {
     1081                        SemanticError( stmt, std::string("jump to label '") + stmt->target.name + "' crosses initialization of " + (*diff.begin())->name + " " );
     1082                } // if
     1083        }
     1084
     1085        void InsertDtors::previsit( const ast::BranchStmt * stmt ) {
     1086                switch( stmt->kind ) {
     1087                  case ast::BranchStmt::Continue:
     1088                  case ast::BranchStmt::Break:
     1089                        // could optimize the break/continue case, because the S_L-S_G check is unnecessary (this set should
     1090                        // always be empty), but it serves as a small sanity check.
     1091                  case ast::BranchStmt::Goto:
     1092                        handleGoto( stmt );
     1093                        break;
     1094                  default:
     1095                        assert( false );
     1096                } // switch
     1097        }
     1098
     1099        bool checkWarnings( const ast::FunctionDecl * funcDecl ) {
     1100                // only check for warnings if the current function is a user-defined
     1101                // constructor or destructor
     1102                if ( ! funcDecl ) return false;
     1103                if ( ! funcDecl->stmts ) return false;
     1104                return CodeGen::isCtorDtor( funcDecl->name ) && ! funcDecl->linkage.is_overrideable;
     1105        }
     1106
     1107        void GenStructMemberCalls::previsit( const ast::FunctionDecl * funcDecl ) {
     1108                GuardValue( function );
     1109                GuardValue( unhandled );
     1110                GuardValue( usedUninit );
     1111                GuardValue( thisParam );
     1112                GuardValue( isCtor );
     1113                GuardValue( structDecl );
     1114                errors = SemanticErrorException();  // clear previous errors
     1115
     1116                // need to start with fresh sets
     1117                unhandled.clear();
     1118                usedUninit.clear();
     1119
     1120                function = mutate(funcDecl);
     1121                // could this be non-unique?
     1122                if (function != funcDecl) {
     1123                        std::cerr << "GenStructMemberCalls: non-unique FunctionDecl " << funcDecl->location << funcDecl->name << std::endl;
     1124                }
     1125
     1126                isCtor = CodeGen::isConstructor( function->name );
     1127                if ( checkWarnings( function ) ) {
     1128                        // const ast::FunctionType * type = function->type;
     1129                        // assert( ! type->params.empty() );
     1130                        thisParam = function->params.front().strict_as<ast::ObjectDecl>();
     1131                        auto thisType = getPointerBase( thisParam->get_type() );
     1132                        auto structType = dynamic_cast< const ast::StructInstType * >( thisType );
     1133                        if ( structType ) {
     1134                                structDecl = structType->base;
     1135                                for ( auto & member : structDecl->members ) {
     1136                                        if ( auto field = member.as<ast::ObjectDecl>() ) {
     1137                                                // record all of the struct type's members that need to be constructed or
     1138                                                // destructed by the end of the function
     1139                                                unhandled.insert( field );
    4351140                                        }
    4361141                                }
    437                                 isSimilar = false;
    438                         }
    439 
    440                         void previsit( const ast::VariableExpr * varExpr ) {
    441                                 if ( auto otherVar = cast< const ast::VariableExpr >( other ) ) {
    442                                         if ( otherVar->var == varExpr->var ) {
    443                                                 return;
     1142                        }
     1143                }
     1144        }
     1145
     1146        const ast::DeclWithType * GenStructMemberCalls::postvisit( const ast::FunctionDecl * funcDecl ) {
     1147                // remove the unhandled objects from usedUninit, because a call is inserted
     1148                // to handle them - only objects that are later constructed are used uninitialized.
     1149                std::map< const ast::DeclWithType *, CodeLocation > diff;
     1150                // need the comparator since usedUninit and unhandled have different types
     1151                struct comp_t {
     1152                        typedef decltype(usedUninit)::value_type usedUninit_t;
     1153                        typedef decltype(unhandled)::value_type unhandled_t;
     1154                        bool operator()(usedUninit_t x, unhandled_t y) { return x.first < y; }
     1155                        bool operator()(unhandled_t x, usedUninit_t y) { return x < y.first; }
     1156                } comp;
     1157                std::set_difference( usedUninit.begin(), usedUninit.end(), unhandled.begin(), unhandled.end(), std::inserter( diff, diff.begin() ), comp );
     1158                for ( auto p : diff ) {
     1159                        auto member = p.first;
     1160                        auto loc = p.second;
     1161                        // xxx - make error message better by also tracking the location that the object is constructed at?
     1162                        emit( loc, "in ", function->name, ", field ", member->name, " used before being constructed" );
     1163                }
     1164
     1165                const CodeLocation loc = funcDecl->location;
     1166
     1167                if ( ! unhandled.empty() ) {
     1168                        auto mutStmts = function->stmts.get_and_mutate();
     1169                        // need to explicitly re-add function parameters to the indexer in order to resolve copy constructors
     1170                        auto guard = makeFuncGuard( [this]() { symtab.enterScope(); }, [this]() { symtab.leaveScope(); } );
     1171                        symtab.addFunction( function );
     1172
     1173                        // need to iterate through members in reverse in order for
     1174                        // ctor/dtor statements to come out in the right order
     1175                        for ( auto & member : reverseIterate( structDecl->members ) ) {
     1176                                auto field = member.as<ast::ObjectDecl>();
     1177                                // skip non-DWT members
     1178                                if ( ! field ) continue;
     1179                                // skip non-constructable members
     1180                                if ( ! tryConstruct( field ) ) continue;
     1181                                // skip handled members
     1182                                if ( ! unhandled.count( field ) ) continue;
     1183
     1184                                // insert and resolve default/copy constructor call for each field that's unhandled
     1185                                // std::list< const ast::Stmt * > stmt;
     1186                                ast::Expr * arg2 = nullptr;
     1187                                if ( function->name == "?{}" && isCopyFunction( function ) ) {
     1188                                        // if copy ctor, need to pass second-param-of-this-function.field
     1189                                        // std::list< DeclarationWithType * > & params = function->get_functionType()->get_parameters();
     1190                                        assert( function->params.size() == 2 );
     1191                                        arg2 = new ast::MemberExpr(funcDecl->location, field, new ast::VariableExpr(funcDecl->location, function->params.back() ) );
     1192                                }
     1193                                InitExpander_new srcParam( arg2 );
     1194                                // cast away reference type and construct field.
     1195                                ast::Expr * thisExpr = new ast::CastExpr(funcDecl->location, new ast::VariableExpr(funcDecl->location, thisParam ), thisParam->get_type()->stripReferences());
     1196                                ast::Expr * memberDest = new ast::MemberExpr(funcDecl->location, field, thisExpr );
     1197                                ast::ptr<ast::Stmt> callStmt = SymTab::genImplicitCall( srcParam, memberDest, loc, function->name, field, static_cast<SymTab::LoopDirection>(isCtor) );
     1198
     1199                                if ( callStmt ) {
     1200                                        // auto & callStmt = stmt.front();
     1201
     1202                                        try {
     1203                                                callStmt = callStmt->accept( *visitor );
     1204                                                if ( isCtor ) {
     1205                                                        mutStmts->push_front( callStmt );
     1206                                                } else { // TODO: don't generate destructor function/object for intrinsic calls
     1207                                                        // destructor statements should be added at the end
     1208                                                        // function->get_statements()->push_back( callStmt );
     1209
     1210                                                        // Optimization: do not need to call intrinsic destructors on members
     1211                                                        if ( isIntrinsicSingleArgCallStmt( callStmt ) ) continue;
     1212
     1213                                                        // __Destructor _dtor0 = { (void *)&b.a1, (void (*)(void *)_destroy_A };
     1214                                                        std::list< ast::ptr<ast::Stmt> > stmtsToAdd;
     1215
     1216                                                        static UniqueName memberDtorNamer = { "__memberDtor" };
     1217                                                        assertf( Validate::dtorStruct, "builtin __Destructor not found." );
     1218                                                        assertf( Validate::dtorStructDestroy, "builtin __destroy_Destructor not found." );
     1219
     1220                                                        ast::Expr * thisExpr = new ast::CastExpr( new ast::AddressExpr( new ast::VariableExpr(loc, thisParam ) ), new ast::PointerType( new ast::VoidType(), ast::CV::Qualifiers() ) );
     1221                                                        ast::Expr * dtorExpr = new ast::VariableExpr(loc, getDtorFunc( thisParam, callStmt, stmtsToAdd ) );
     1222
     1223                                                        // cast destructor pointer to void (*)(void *), to silence GCC incompatible pointer warnings
     1224                                                        auto dtorFtype = new ast::FunctionType();
     1225                                                        dtorFtype->params.emplace_back( new ast::PointerType( new ast::VoidType() ) );
     1226                                                        auto dtorType = new ast::PointerType( dtorFtype );
     1227
     1228                                                        auto destructor = new ast::ObjectDecl(loc, memberDtorNamer.newName(), new ast::StructInstType( ast::dtorStruct ), new ast::ListInit(loc, { new ast::SingleInit(loc, thisExpr ), new ast::SingleInit(loc, new ast::CastExpr( dtorExpr, dtorType ) ) } ) );
     1229                                                        destructor->attributes.push_back( new ast::Attribute( "cleanup", { new ast::VariableExpr({}, ast::dtorStructDestroy ) } ) );
     1230                                                        mutStmts->push_front( new ast::DeclStmt(loc, destructor ) );
     1231                                                        mutStmts->kids.splice( mutStmts->kids.begin(), stmtsToAdd );
     1232                                                }
     1233                                        } catch ( SemanticErrorException & error ) {
     1234                                                emit( funcDecl->location, "in ", function->name , ", field ", field->name, " not explicitly ", isCtor ? "constructed" : "destructed",  " and no ", isCtor ? "default constructor" : "destructor", " found" );
    4441235                                        }
    4451236                                }
    446                                 isSimilar = false;
    447                         }
    448 
    449                         void previsit( const ast::AddressExpr * ) {
    450                                 if ( auto addrExpr = cast< const ast::AddressExpr >( other ) ) {
    451                                         other = addrExpr->arg;
    452                                         return;
     1237                        }
     1238                        function->stmts = mutStmts;
     1239                }
     1240                if (! errors.isEmpty()) {
     1241                        throw errors;
     1242                }
     1243                // return funcDecl;
     1244                return function;
     1245        }
     1246
     1247        /// true if expr is effectively just the 'this' parameter
     1248        bool isThisExpression( const ast::Expr * expr, const ast::DeclWithType * thisParam ) {
     1249                // TODO: there are more complicated ways to pass 'this' to a constructor, e.g. &*, *&, etc.
     1250                if ( auto varExpr = dynamic_cast< const ast::VariableExpr * >( expr ) ) {
     1251                        return varExpr->var == thisParam;
     1252                } else if ( auto castExpr = dynamic_cast< const ast::CastExpr * > ( expr ) ) {
     1253                        return isThisExpression( castExpr->arg, thisParam );
     1254                }
     1255                return false;
     1256        }
     1257
     1258        /// returns a MemberExpr if expr is effectively just member access on the 'this' parameter, else nullptr
     1259        const ast::MemberExpr * isThisMemberExpr( const ast::Expr * expr, const ast::DeclWithType * thisParam ) {
     1260                if ( auto memberExpr = dynamic_cast< const ast::MemberExpr * >( expr ) ) {
     1261                        if ( isThisExpression( memberExpr->aggregate, thisParam ) ) {
     1262                                return memberExpr;
     1263                        }
     1264                } else if ( auto castExpr = dynamic_cast< const ast::CastExpr * >( expr ) ) {
     1265                        return isThisMemberExpr( castExpr->arg, thisParam );
     1266                }
     1267                return nullptr;
     1268        }
     1269
     1270        void GenStructMemberCalls::previsit( const ast::ApplicationExpr * appExpr ) {
     1271                if ( ! checkWarnings( function ) ) {
     1272                        visit_children = false;
     1273                        return;
     1274                }
     1275
     1276                std::string fname = getFunctionName( appExpr );
     1277                if ( fname == function->name ) {
     1278                        // call to same kind of function
     1279                        const ast::Expr * firstParam = appExpr->args.front();
     1280
     1281                        if ( isThisExpression( firstParam, thisParam ) ) {
     1282                                // if calling another constructor on thisParam, assume that function handles
     1283                                // all members - if it doesn't a warning will appear in that function.
     1284                                unhandled.clear();
     1285                        } else if ( auto memberExpr = isThisMemberExpr( firstParam, thisParam ) ) {
     1286                                // if first parameter is a member expression on the this parameter,
     1287                                // then remove the member from unhandled set.
     1288                                if ( isThisExpression( memberExpr->aggregate, thisParam ) ) {
     1289                                        unhandled.erase( memberExpr->member );
    4531290                                }
    454                                 isSimilar = false;
    455                         }
    456 
    457                         const ast::Expr * other = nullptr;
    458                         bool isSimilar = true;
    459                 };
    460 
    461                 bool structurallySimilar( const ast::Expr * e1, const ast::Expr * e2 ) {
    462                         ast::Pass<StructuralChecker> checker;
    463                         checker.core.other = e2;
    464                         e1->accept( checker );
    465                         return checker.core.isSimilar;
    466                 }
    467 
    468                 void SelfAssignChecker::previsit( const ast::ApplicationExpr * appExpr ) {
    469                         auto function = getFunction( appExpr );
    470                         if ( function->name == "?=?" ) { // doesn't use isAssignment, because ?+=?, etc. should not count as self-assignment
    471                                 if ( appExpr->args.size() == 2 ) {
    472                                         // check for structural similarity (same variable use, ignore casts, etc. - but does not look too deeply, anything looking like a function is off limits)
    473                                         if ( structurallySimilar( appExpr->args.front(), appExpr->args.back() ) ) {
    474                                                 SemanticWarning( appExpr->location, Warning::SelfAssignment, toCString( appExpr->args.front() ) );
    475                                         }
    476                                 }
    477                         }
    478                 }
    479 
    480                 const ast::Expr * InsertImplicitCalls::postvisit( const ast::ApplicationExpr * appExpr ) {
    481                         if ( auto function = appExpr->func.as<ast::VariableExpr>() ) {
    482                                 if ( function->var->linkage.is_builtin ) {
    483                                         // optimization: don't need to copy construct in order to call intrinsic functions
    484                                         return appExpr;
    485                                 } else if ( auto funcDecl = function->var.as<ast::DeclWithType>() ) {
    486                                         auto ftype = dynamic_cast< const ast::FunctionType * >( GenPoly::getFunctionType( funcDecl->get_type() ) );
    487                                         assertf( ftype, "Function call without function type: %s", toString( funcDecl ).c_str() );
    488                                         if ( CodeGen::isConstructor( funcDecl->name ) && ftype->params.size() == 2 ) {
    489                                                 auto t1 = getPointerBase( ftype->params.front() );
    490                                                 auto t2 = ftype->params.back();
    491                                                 assert( t1 );
    492 
    493                                                 if ( ResolvExpr::typesCompatible( t1, t2 ) ) {
    494                                                         // optimization: don't need to copy construct in order to call a copy constructor
    495                                                         return appExpr;
    496                                                 } // if
    497                                         } else if ( CodeGen::isDestructor( funcDecl->name ) ) {
    498                                                 // correctness: never copy construct arguments to a destructor
    499                                                 return appExpr;
    500                                         } // if
    501                                 } // if
    502                         } // if
    503                         CP_CTOR_PRINT( std::cerr << "InsertImplicitCalls: adding a wrapper " << appExpr << std::endl; )
    504 
    505                         // wrap each function call so that it is easy to identify nodes that have to be copy constructed
    506                         ast::ptr<ast::TypeSubstitution> tmp = appExpr->env;
    507                         auto mutExpr = mutate(appExpr);
    508                         mutExpr->env = nullptr;
    509 
    510                         auto expr = new ast::ImplicitCopyCtorExpr( appExpr->location, mutExpr );
    511                         // Move the type substitution to the new top-level, if it is attached to the appExpr.
    512                         // Ensure it is not deleted with the ImplicitCopyCtorExpr by removing it before deletion.
    513                         // The substitution is needed to obtain the type of temporary variables so that copy constructor
    514                         // calls can be resolved.
    515                         assert( typeSubs );
    516                         // assert (mutExpr->env);
    517                         expr->env = tmp;
    518                         // mutExpr->env = nullptr;
    519                         //std::swap( expr->env, appExpr->env );
    520                         return expr;
    521                 }
    522 
    523                 void ResolveCopyCtors::previsit(const ast::Expr * expr) {
    524                         if (expr->env) {
    525                                 GuardValue(env);
    526                                 GuardValue(envModified);
    527                                 env = expr->env->clone();
    528                                 envModified = false;
    529                         }
    530                 }
    531 
    532                 const ast::Expr * ResolveCopyCtors::postvisit(const ast::Expr * expr) {
    533                         if (expr->env) {
    534                                 if (envModified) {
    535                                         auto mutExpr = mutate(expr);
    536                                         mutExpr->env = env;
    537                                         return mutExpr;
    538                                 }
    539                                 else {
    540                                         // env was not mutated, skip and delete the shallow copy
    541                                         delete env;
    542                                         return expr;
    543                                 }
    544                         }
    545                         else {
    546                                 return expr;
    547                         }
    548                 }
    549 
    550                 bool ResolveCopyCtors::skipCopyConstruct( const ast::Type * type ) { return ! isConstructable( type ); }
    551 
    552                 const ast::Expr * ResolveCopyCtors::makeCtorDtor( const std::string & fname, const ast::ObjectDecl * var, const ast::Expr * cpArg ) {
    553                         assert( var );
    554                         assert (var->isManaged());
    555                         assert (!cpArg || cpArg->isManaged());
    556                         // arrays are not copy constructed, so this should always be an ExprStmt
    557                         ast::ptr< ast::Stmt > stmt = genCtorDtor(var->location, fname, var, cpArg );
    558                         assertf( stmt, "ResolveCopyCtors: genCtorDtor returned nullptr: %s / %s / %s", fname.c_str(), toString( var ).c_str(), toString( cpArg ).c_str() );
    559                         auto exprStmt = stmt.strict_as<ast::ImplicitCtorDtorStmt>()->callStmt.strict_as<ast::ExprStmt>();
    560                         ast::ptr<ast::Expr> untyped = exprStmt->expr; // take ownership of expr
    561                         // exprStmt->expr = nullptr;
    562 
    563                         // resolve copy constructor
    564                         // should only be one alternative for copy ctor and dtor expressions, since all arguments are fixed
    565                         // (VariableExpr and already resolved expression)
    566                         CP_CTOR_PRINT( std::cerr << "ResolvingCtorDtor " << untyped << std::endl; )
    567                         ast::ptr<ast::Expr> resolved = ResolvExpr::findVoidExpression(untyped, symtab);
    568                         assert( resolved );
    569                         if ( resolved->env ) {
    570                                 // Extract useful information and discard new environments. Keeping them causes problems in PolyMutator passes.
    571                                 env->add( *resolved->env );
    572                                 envModified = true;
    573                                 // delete resolved->env;
    574                                 auto mut = mutate(resolved.get());
    575                                 assertf(mut == resolved.get(), "newly resolved expression must be unique");
    576                                 mut->env = nullptr;
    577                         } // if
    578                         // delete stmt;
    579                         if ( auto assign = resolved.as<ast::TupleAssignExpr>() ) {
    580                                 // fix newly generated StmtExpr
    581                                 previsit( assign->stmtExpr );
    582                         }
    583                         return resolved.release();
    584                 }
    585 
    586                 ast::ptr<ast::Expr> ResolveCopyCtors::copyConstructArg(
    587                         const ast::Expr * arg, const ast::ImplicitCopyCtorExpr * impCpCtorExpr, const ast::Type * formal )
    588                 {
    589                         static UniqueName tempNamer("_tmp_cp");
    590                         assert( env );
    591                         const CodeLocation loc = impCpCtorExpr->location;
    592                         // CP_CTOR_PRINT( std::cerr << "Type Substitution: " << *env << std::endl; )
    593                         assert( arg->result );
    594                         ast::ptr<ast::Type> result = arg->result;
    595                         if ( skipCopyConstruct( result ) ) return arg; // skip certain non-copyable types
    596 
    597                         // type may involve type variables, so apply type substitution to get temporary variable's actual type,
    598                         // since result type may not be substituted (e.g., if the type does not appear in the parameter list)
    599                         // Use applyFree so that types bound in function pointers are not substituted, e.g. in forall(dtype T) void (*)(T).
    600                        
    601                         // xxx - this originally mutates arg->result in place. is it correct?
    602                         result = env->applyFree( result.get() ).node;
    603                         auto mutResult = result.get_and_mutate();
    604                         mutResult->set_const(false);
    605 
    606                         auto mutArg = mutate(arg);
    607                         mutArg->result = mutResult;
    608 
    609                         ast::ptr<ast::Expr> guard = mutArg;
    610 
    611                         ast::ptr<ast::ObjectDecl> tmp = new ast::ObjectDecl({}, "__tmp", mutResult, nullptr );
    612 
    613                         // create and resolve copy constructor
    614                         CP_CTOR_PRINT( std::cerr << "makeCtorDtor for an argument" << std::endl; )
    615                         auto cpCtor = makeCtorDtor( "?{}", tmp, mutArg );
    616 
    617                         if ( auto appExpr = dynamic_cast< const ast::ApplicationExpr * >( cpCtor ) ) {
    618                                 // if the chosen constructor is intrinsic, the copy is unnecessary, so
    619                                 // don't create the temporary and don't call the copy constructor
    620                                 auto function = appExpr->func.strict_as<ast::VariableExpr>();
    621                                 if ( function->var->linkage == ast::Linkage::Intrinsic ) {
    622                                         // arguments that need to be boxed need a temporary regardless of whether the copy constructor is intrinsic,
    623                                         // so that the object isn't changed inside of the polymorphic function
    624                                         if ( ! GenPoly::needsBoxing( formal, result, impCpCtorExpr->callExpr, env ) ) {
    625                                                 // xxx - should arg->result be mutated? see comment above.
    626                                                 return guard;
    627                                         }
    628                                 }
    629                         }
    630 
    631                         // set a unique name for the temporary once it's certain the call is necessary
    632                         auto mut = tmp.get_and_mutate();
    633                         assertf (mut == tmp, "newly created ObjectDecl must be unique");
    634                         mut->name = tempNamer.newName();
    635 
    636                         // replace argument to function call with temporary
    637                         stmtsToAddBefore.push_back( new ast::DeclStmt(loc, tmp ) );
    638                         arg = cpCtor;
    639                         return destructRet( tmp, arg );
    640 
    641                         // impCpCtorExpr->dtors.push_front( makeCtorDtor( "^?{}", tmp ) );
    642                 }
    643 
    644                 ast::Expr * ResolveCopyCtors::destructRet( const ast::ObjectDecl * ret, const ast::Expr * arg ) {
    645                         // TODO: refactor code for generating cleanup attribute, since it's common and reused in ~3-4 places
    646                         // check for existing cleanup attribute before adding another(?)
    647                         // need to add __Destructor for _tmp_cp variables as well
    648 
    649                         assertf( ast::dtorStruct && ast::dtorStruct->members.size() == 2, "Destructor generation requires __Destructor definition." );
    650                         assertf( ast::dtorStructDestroy, "Destructor generation requires __destroy_Destructor." );
    651 
    652                         const CodeLocation loc = ret->location;
    653 
    654                         // generate a __Destructor for ret that calls the destructor
    655                         auto res = makeCtorDtor( "^?{}", ret );
    656                         auto dtor = mutate(res);
    657 
    658                         // if the chosen destructor is intrinsic, elide the generated dtor handler
    659                         if ( arg && isIntrinsicCallExpr( dtor ) ) {
    660                                 return new ast::CommaExpr(loc, arg, new ast::VariableExpr(loc, ret ) );
    661                                 // return;
    662                         }
    663 
    664                         if ( ! dtor->env ) dtor->env = maybeClone( env );
    665                         auto dtorFunc = getDtorFunc( ret, new ast::ExprStmt(loc, dtor ), stmtsToAddBefore );
    666 
    667                         auto dtorStructType = new ast::StructInstType(ast::dtorStruct);
    668 
    669                         // what does this do???
    670                         dtorStructType->params.push_back( new ast::TypeExpr(loc, new ast::VoidType() ) );
    671 
    672                         // cast destructor pointer to void (*)(void *), to silence GCC incompatible pointer warnings
    673                         auto dtorFtype = new ast::FunctionType();
    674                         dtorFtype->params.push_back( new ast::PointerType(new ast::VoidType( ) ) );
    675                         auto dtorType = new ast::PointerType( dtorFtype );
    676 
    677                         static UniqueName namer( "_ret_dtor" );
    678                         auto retDtor = new ast::ObjectDecl(loc, namer.newName(), dtorStructType, new ast::ListInit(loc, { new ast::SingleInit(loc, ast::ConstantExpr::null(loc) ), new ast::SingleInit(loc, new ast::CastExpr( new ast::VariableExpr(loc, dtorFunc ), dtorType ) ) } ) );
    679                         retDtor->attributes.push_back( new ast::Attribute( "cleanup", { new ast::VariableExpr(loc, ast::dtorStructDestroy ) } ) );
    680                         stmtsToAddBefore.push_back( new ast::DeclStmt(loc, retDtor ) );
    681 
    682                         if ( arg ) {
    683                                 auto member = new ast::MemberExpr(loc, ast::dtorStruct->members.front().strict_as<ast::DeclWithType>(), new ast::VariableExpr(loc, retDtor ) );
    684                                 auto object = new ast::CastExpr( new ast::AddressExpr( new ast::VariableExpr(loc, ret ) ), new ast::PointerType(new ast::VoidType() ) );
    685                                 ast::Expr * assign = createBitwiseAssignment( member, object );
    686                                 return new ast::CommaExpr(loc, new ast::CommaExpr(loc, arg, assign ), new ast::VariableExpr(loc, ret ) );
    687                         }
    688                         return nullptr;
    689                         // impCpCtorExpr->get_dtors().push_front( makeCtorDtor( "^?{}", ret ) );
    690                 }
    691 
    692                 const ast::Expr * ResolveCopyCtors::postvisit( const ast::ImplicitCopyCtorExpr *impCpCtorExpr ) {
    693                         CP_CTOR_PRINT( std::cerr << "ResolveCopyCtors: " << impCpCtorExpr << std::endl; )
    694 
    695                         ast::ApplicationExpr * appExpr = mutate(impCpCtorExpr->callExpr.get());
    696                         const ast::ObjectDecl * returnDecl = nullptr;
    697                         const CodeLocation loc = appExpr->location;
    698 
    699                         // take each argument and attempt to copy construct it.
    700                         auto ftype = GenPoly::getFunctionType( appExpr->func->result );
    701                         assert( ftype );
    702                         auto & params = ftype->params;
    703                         auto iter = params.begin();
    704                         for ( auto & arg : appExpr->args ) {
    705                                 const ast::Type * formal = nullptr;
    706                                 if ( iter != params.end() ) { // does not copy construct C-style variadic arguments
    707                                         // DeclarationWithType * param = *iter++;
    708                                         formal = *iter++;
    709                                 }
    710 
    711                                 arg = copyConstructArg( arg, impCpCtorExpr, formal );
    712                         } // for
    713 
    714                         // each return value from the call needs to be connected with an ObjectDecl at the call site, which is
    715                         // initialized with the return value and is destructed later
    716                         // xxx - handle named return values?
    717                         const ast::Type * result = appExpr->result;
    718                         if ( ! result->isVoid() ) {
    719                                 static UniqueName retNamer("_tmp_cp_ret");
    720                                 // result = result->clone();
    721                                 auto subResult = env->apply( result ).node;
    722                                 auto ret = new ast::ObjectDecl(loc, retNamer.newName(), subResult, nullptr );
    723                                 auto mutType = mutate(ret->type.get());
    724                                 mutType->set_const( false );
    725                                 ret->type = mutType;
    726                                 returnDecl = ret;
    727                                 stmtsToAddBefore.push_back( new ast::DeclStmt(loc, ret ) );
    728                                 CP_CTOR_PRINT( std::cerr << "makeCtorDtor for a return" << std::endl; )
    729                         } // for
    730                         CP_CTOR_PRINT( std::cerr << "after Resolving: " << impCpCtorExpr << std::endl; )
    731                         // ------------------------------------------------------
    732 
    733                         CP_CTOR_PRINT( std::cerr << "Coming out the back..." << impCpCtorExpr << std::endl; )
    734 
    735                         // detach fields from wrapper node so that it can be deleted without deleting too much
    736 
    737                         // xxx - actual env might be somewhere else, need to keep invariant
    738 
    739                         // deletion of wrapper should be handled by pass template now
    740                        
    741                         // impCpCtorExpr->callExpr = nullptr;
    742                         assert (appExpr->env == nullptr);
    743                         appExpr->env = impCpCtorExpr->env;
    744                         // std::swap( impCpCtorExpr->env, appExpr->env );
    745                         // assert( impCpCtorExpr->env == nullptr );
    746                         // delete impCpCtorExpr;
    747 
    748                         if ( returnDecl ) {
    749                                 ast::Expr * assign = createBitwiseAssignment( new ast::VariableExpr(loc, returnDecl ), appExpr );
    750                                 if ( ! dynamic_cast< const ast::ReferenceType * >( result ) ) {
    751                                         // destructing reference returns is bad because it can cause multiple destructor calls to the same object - the returned object is not a temporary
    752                                         assign = destructRet( returnDecl, assign );
    753                                         assert(assign);
    754                                 } else {
    755                                         assign = new ast::CommaExpr(loc, assign, new ast::VariableExpr(loc, returnDecl ) );
    756                                 }
    757                                 // move env from appExpr to retExpr
    758                                 // std::swap( assign->env, appExpr->env );
    759                                 assign->env = appExpr->env;
    760                                 // actual env is handled by common routine that replaces WithTypeSubstitution
    761                                 return postvisit((const ast::Expr *)assign);
    762                         } else {
    763                                 return postvisit((const ast::Expr *)appExpr);
    764                         } // if
    765                 }
    766 
    767                 const ast::StmtExpr * ResolveCopyCtors::previsit( const ast::StmtExpr * _stmtExpr ) {
    768                         // function call temporaries should be placed at statement-level, rather than nested inside of a new statement expression,
    769                         // since temporaries can be shared across sub-expressions, e.g.
    770                         //   [A, A] f();       // decl
    771                         //   g([A] x, [A] y);  // decl
    772                         //   g(f());           // call
    773                         // f is executed once, so the return temporary is shared across the tuple constructors for x and y.
    774                         // Explicitly mutating children instead of mutating the inner compound statement forces the temporaries to be added
    775                         // to the outer context, rather than inside of the statement expression.
    776 
    777                         // call the common routine that replaces WithTypeSubstitution
    778                         previsit((const ast::Expr *) _stmtExpr);
    779 
     1291                        }
     1292                }
     1293        }
     1294
     1295        void GenStructMemberCalls::previsit( const ast::MemberExpr * memberExpr ) {
     1296                if ( ! checkWarnings( function ) || ! isCtor ) {
    7801297                        visit_children = false;
    781                         const CodeLocation loc = _stmtExpr->location;
    782 
    783                         assert( env );
    784 
    785                         symtab.enterScope();
    786                         // visit all statements
    787                         auto stmtExpr = mutate(_stmtExpr);
    788                         auto mutStmts = mutate(stmtExpr->stmts.get());
    789 
    790                         auto & stmts = mutStmts->kids;
    791                         for ( auto & stmt : stmts ) {
    792                                 stmt = stmt->accept( *visitor );
    793                         } // for
    794                         stmtExpr->stmts = mutStmts;
    795                         symtab.leaveScope();
    796 
    797                         assert( stmtExpr->result );
    798                         // const ast::Type * result = stmtExpr->result;
    799                         if ( ! stmtExpr->result->isVoid() ) {
    800                                 static UniqueName retNamer("_tmp_stmtexpr_ret");
    801 
    802                                 // result = result->clone();
    803                                 auto result = env->apply( stmtExpr->result.get() ).node;
    804                                 if ( ! InitTweak::isConstructable( result ) ) {
    805                                         // delete result;
    806                                         return stmtExpr;
    807                                 }
    808                                 auto mutResult = result.get_and_mutate();
    809                                 mutResult->set_const(false);
    810 
    811                                 // create variable that will hold the result of the stmt expr
    812                                 auto ret = new ast::ObjectDecl(loc, retNamer.newName(), mutResult, nullptr );
    813                                 stmtsToAddBefore.push_back( new ast::DeclStmt(loc, ret ) );
    814 
    815                                 assertf(
    816                                         stmtExpr->resultExpr,
    817                                         "Statement-Expression should have a resulting expression at %s:%d",
    818                                         stmtExpr->location.filename.c_str(),
    819                                         stmtExpr->location.first_line
    820                                 );
    821 
    822                                 const ast::ExprStmt * last = stmtExpr->resultExpr;
    823                                 // xxx - if this is non-unique, need to copy while making resultExpr ref
    824                                 assertf(last->unique(), "attempt to modify weakly shared statement");
    825                                 auto mutLast = mutate(last);
    826                                 // above assertion means in-place mutation is OK
    827                                 try {
    828                                         mutLast->expr = makeCtorDtor( "?{}", ret, mutLast->expr );
    829                                 } catch(...) {
    830                                         std::cerr << "*CFA internal error: ";
    831                                         std::cerr << "can't resolve implicit constructor";
    832                                         std::cerr << " at " << stmtExpr->location.filename;
    833                                         std::cerr << ":" << stmtExpr->location.first_line << std::endl;
    834 
    835                                         abort();
    836                                 }
    837 
    838                                 // add destructors after current statement
    839                                 stmtsToAddAfter.push_back( new ast::ExprStmt(loc, makeCtorDtor( "^?{}", ret ) ) );
    840 
    841                                 // must have a non-empty body, otherwise it wouldn't have a result
    842                                 assert( ! stmts.empty() );
    843 
    844                                 // if there is a return decl, add a use as the last statement; will not have return decl on non-constructable returns
    845                                 stmts.push_back( new ast::ExprStmt(loc, new ast::VariableExpr(loc, ret ) ) );
    846                         } // if
    847 
    848                         assert( stmtExpr->returnDecls.empty() );
    849                         assert( stmtExpr->dtors.empty() );
    850 
    851                         return stmtExpr;
    852                 }
    853 
    854                 // to prevent warnings ('_unq0' may be used uninitialized in this function),
    855                 // insert an appropriate zero initializer for UniqueExpr temporaries.
    856                 ast::Init * makeInit( const ast::Type * t ) {
    857                         if ( auto inst = dynamic_cast< const ast::StructInstType * >( t ) ) {
    858                                 // initizer for empty struct must be empty
    859                                 if ( inst->base->members.empty() ) return new ast::ListInit({}, {});
    860                         } else if ( auto inst = dynamic_cast< const ast::UnionInstType * >( t ) ) {
    861                                 // initizer for empty union must be empty
    862                                 if ( inst->base->members.empty() ) return new ast::ListInit({}, {});
    863                         }
    864 
    865                         return new ast::ListInit( {}, { new ast::SingleInit( {}, ast::ConstantExpr::from_int({}, 0) ) } );
    866                 }
    867 
    868                 const ast::UniqueExpr * ResolveCopyCtors::previsit( const ast::UniqueExpr * unqExpr ) {
    869                         visit_children = false;
    870                         // xxx - hack to prevent double-handling of unique exprs, otherwise too many temporary variables and destructors are generated
    871                         static std::unordered_map< int, const ast::UniqueExpr * > unqMap;
    872                         auto mutExpr = mutate(unqExpr);
    873                         if ( ! unqMap.count( unqExpr->id ) ) {
    874                                 // resolve expr and find its
    875 
    876                                 auto impCpCtorExpr = mutExpr->expr.as<ast::ImplicitCopyCtorExpr>();
    877                                 // PassVisitor<ResolveCopyCtors> fixer;
    878                                
    879                                 mutExpr->expr = mutExpr->expr->accept( *visitor );
    880                                 // it should never be necessary to wrap a void-returning expression in a UniqueExpr - if this assumption changes, this needs to be rethought
    881                                 assert( unqExpr->result );
    882                                 if ( impCpCtorExpr ) {
    883                                         auto comma = unqExpr->expr.strict_as<ast::CommaExpr>();
    884                                         auto var = comma->arg2.strict_as<ast::VariableExpr>();
    885                                         // note the variable used as the result from the call
    886                                         mutExpr->var = var;
    887                                 } else {
    888                                         // expr isn't a call expr, so create a new temporary variable to use to hold the value of the unique expression
    889                                         mutExpr->object = new ast::ObjectDecl( mutExpr->location, toString("_unq", mutExpr->id), mutExpr->result, makeInit( mutExpr->result ) );
    890                                         mutExpr->var = new ast::VariableExpr( mutExpr->location, mutExpr->object );
    891                                 }
    892 
    893                                 // stmtsToAddBefore.splice( stmtsToAddBefore.end(), fixer.pass.stmtsToAddBefore );
    894                                 // stmtsToAddAfter.splice( stmtsToAddAfter.end(), fixer.pass.stmtsToAddAfter );
    895                                 unqMap[mutExpr->id] = mutExpr;
    896                         } else {
    897                                 // take data from other UniqueExpr to ensure consistency
    898                                 // delete unqExpr->get_expr();
    899                                 mutExpr->expr = unqMap[mutExpr->id]->expr;
    900                                 // delete unqExpr->result;
    901                                 mutExpr->result = mutExpr->expr->result;
    902                         }
    903                         return mutExpr;
    904                 }
    905 
    906                 const ast::DeclWithType * FixInit::postvisit( const ast::ObjectDecl *_objDecl ) {
    907                         const CodeLocation loc = _objDecl->location;
    908 
    909                         // since this removes the init field from objDecl, it must occur after children are mutated (i.e. postvisit)
    910                         if ( ast::ptr<ast::ConstructorInit> ctorInit = _objDecl->init.as<ast::ConstructorInit>() ) {
    911                                 auto objDecl = mutate(_objDecl);
    912 
    913                                 // could this be non-unique?
    914                                 if (objDecl != _objDecl) {
    915                                         std::cerr << "FixInit: non-unique object decl " << objDecl->location << objDecl->name << std::endl;
    916                                 }
    917                                 // a decision should have been made by the resolver, so ctor and init are not both non-NULL
    918                                 assert( ! ctorInit->ctor || ! ctorInit->init );
    919                                 if ( const ast::Stmt * ctor = ctorInit->ctor ) {
    920                                         if ( objDecl->storage.is_static ) {
    921                                                 // originally wanted to take advantage of gcc nested functions, but
    922                                                 // we get memory errors with this approach. To remedy this, the static
    923                                                 // variable is hoisted when the destructor needs to be called.
    924                                                 //
    925                                                 // generate:
    926                                                 // static T __objName_static_varN;
    927                                                 // void __objName_dtor_atexitN() {
    928                                                 //   __dtor__...;
    929                                                 // }
    930                                                 // int f(...) {
    931                                                 //   ...
    932                                                 //   static bool __objName_uninitialized = true;
    933                                                 //   if (__objName_uninitialized) {
    934                                                 //     __ctor(__objName);
    935                                                 //     __objName_uninitialized = false;
    936                                                 //     atexit(__objName_dtor_atexitN);
    937                                                 //   }
    938                                                 //   ...
    939                                                 // }
    940 
    941                                                 static UniqueName dtorCallerNamer( "_dtor_atexit" );
    942 
    943                                                 // static bool __objName_uninitialized = true
    944                                                 auto boolType = new ast::BasicType( ast::BasicType::Kind::Bool );
    945                                                 auto boolInitExpr = new ast::SingleInit(loc, ast::ConstantExpr::from_int(loc, 1 ) );
    946                                                 auto isUninitializedVar = new ast::ObjectDecl(loc, objDecl->mangleName + "_uninitialized", boolType, boolInitExpr, ast::Storage::Static, ast::Linkage::Cforall);
    947                                                 isUninitializedVar->fixUniqueId();
    948 
    949                                                 // __objName_uninitialized = false;
    950                                                 auto setTrue = new ast::UntypedExpr(loc, new ast::NameExpr(loc, "?=?" ) );
    951                                                 setTrue->args.push_back( new ast::VariableExpr(loc, isUninitializedVar ) );
    952                                                 setTrue->args.push_back( ast::ConstantExpr::from_int(loc, 0 ) );
    953 
    954                                                 // generate body of if
    955                                                 auto initStmts = new ast::CompoundStmt(loc);
    956                                                 auto & body = initStmts->kids;
    957                                                 body.push_back( ctor );
    958                                                 body.push_back( new ast::ExprStmt(loc, setTrue ) );
    959 
    960                                                 // put it all together
    961                                                 auto ifStmt = new ast::IfStmt(loc, new ast::VariableExpr(loc, isUninitializedVar ), initStmts, 0 );
    962                                                 stmtsToAddAfter.push_back( new ast::DeclStmt(loc, isUninitializedVar ) );
    963                                                 stmtsToAddAfter.push_back( ifStmt );
    964 
    965                                                 const ast::Stmt * dtor = ctorInit->dtor;
    966 
    967                                                 // these should be automatically managed once reassigned
    968                                                 // objDecl->set_init( nullptr );
    969                                                 // ctorInit->set_ctor( nullptr );
    970                                                 // ctorInit->set_dtor( nullptr );
    971                                                 if ( dtor ) {
    972                                                         // if the object has a non-trivial destructor, have to
    973                                                         // hoist it and the object into the global space and
    974                                                         // call the destructor function with atexit.
    975 
    976                                                         // Statement * dtorStmt = dtor->clone();
    977 
    978                                                         // void __objName_dtor_atexitN(...) {...}
    979                                                         ast::FunctionDecl * dtorCaller = new ast::FunctionDecl(loc, objDecl->mangleName + dtorCallerNamer.newName(), {}, {}, {}, new ast::CompoundStmt(loc, {dtor}), ast::Storage::Static, ast::Linkage::C );
    980                                                         dtorCaller->fixUniqueId();
    981                                                         // dtorCaller->stmts->push_back( dtor );
    982 
    983                                                         // atexit(dtor_atexit);
    984                                                         auto callAtexit = new ast::UntypedExpr(loc, new ast::NameExpr(loc, "atexit" ) );
    985                                                         callAtexit->args.push_back( new ast::VariableExpr(loc, dtorCaller ) );
    986 
    987                                                         body.push_back( new ast::ExprStmt(loc, callAtexit ) );
    988 
    989                                                         // hoist variable and dtor caller decls to list of decls that will be added into global scope
    990                                                         staticDtorDecls.push_back( objDecl );
    991                                                         staticDtorDecls.push_back( dtorCaller );
    992 
    993                                                         // need to rename object uniquely since it now appears
    994                                                         // at global scope and there could be multiple function-scoped
    995                                                         // static variables with the same name in different functions.
    996                                                         // Note: it isn't sufficient to modify only the mangleName, because
    997                                                         // then subsequent Indexer passes can choke on seeing the object's name
    998                                                         // if another object has the same name and type. An unfortunate side-effect
    999                                                         // of renaming the object is that subsequent NameExprs may fail to resolve,
    1000                                                         // but there shouldn't be any remaining past this point.
    1001                                                         static UniqueName staticNamer( "_static_var" );
    1002                                                         objDecl->name = objDecl->name + staticNamer.newName();
    1003                                                         objDecl->mangleName = Mangle::mangle( objDecl );
    1004 
    1005                                                         // xxx - temporary hack: need to return a declaration, but want to hoist the current object out of this scope
    1006                                                         // create a new object which is never used
    1007                                                         static UniqueName dummyNamer( "_dummy" );
    1008                                                         auto dummy = new ast::ObjectDecl(loc, dummyNamer.newName(), new ast::PointerType(new ast::VoidType()), nullptr, ast::Storage::Static, ast::Linkage::Cforall, 0, { new ast::Attribute("unused") } );
    1009                                                         // delete ctorInit;
    1010                                                         return dummy;
    1011                                                 } else {
    1012                                                         objDecl->init = nullptr;
    1013                                                         return objDecl;
    1014                                                 }
    1015                                         } else {
    1016                                                 auto implicit = strict_dynamic_cast< const ast::ImplicitCtorDtorStmt * > ( ctor );
    1017                                                 auto ctorStmt = implicit->callStmt.as<ast::ExprStmt>();
    1018                                                 const ast::ApplicationExpr * ctorCall = nullptr;
    1019                                                 if ( ctorStmt && (ctorCall = isIntrinsicCallExpr( ctorStmt->expr )) && ctorCall->args.size() == 2 ) {
    1020                                                         // clean up intrinsic copy constructor calls by making them into SingleInits
    1021                                                         const ast::Expr * ctorArg = ctorCall->args.back();
    1022                                                         // ctorCall should be gone afterwards
    1023                                                         auto mutArg = mutate(ctorArg);
    1024                                                         mutArg->env = ctorCall->env;
    1025                                                         // std::swap( ctorArg->env, ctorCall->env );
    1026                                                         objDecl->init = new ast::SingleInit(loc, mutArg );
    1027 
    1028                                                         // ctorCall->args.pop_back();
    1029                                                 } else {
    1030                                                         stmtsToAddAfter.push_back( ctor );
    1031                                                         objDecl->init = nullptr;
    1032                                                         // ctorInit->ctor = nullptr;
    1033                                                 }
    1034 
    1035                                                 const ast::Stmt * dtor = ctorInit->dtor;
    1036                                                 if ( dtor ) {
    1037                                                         auto implicit = strict_dynamic_cast< const ast::ImplicitCtorDtorStmt * >( dtor );
    1038                                                         const ast::Stmt * dtorStmt = implicit->callStmt;
    1039 
    1040                                                         // don't need to call intrinsic dtor, because it does nothing, but
    1041                                                         // non-intrinsic dtors must be called
    1042                                                         if ( ! isIntrinsicSingleArgCallStmt( dtorStmt ) ) {
    1043                                                                 // set dtor location to the object's location for error messages
    1044                                                                 auto dtorFunc = getDtorFunc( objDecl, dtorStmt, stmtsToAddBefore );
    1045                                                                 objDecl->attributes.push_back( new ast::Attribute( "cleanup", { new ast::VariableExpr(loc, dtorFunc ) } ) );
    1046                                                                 // ctorInit->dtor = nullptr;
    1047                                                         } // if
    1048                                                 }
    1049                                         } // if
    1050                                 } else if ( const ast::Init * init = ctorInit->init ) {
    1051                                         objDecl->init = init;
    1052                                         // ctorInit->init = nullptr;
    1053                                 } else {
    1054                                         // no constructor and no initializer, which is okay
    1055                                         objDecl->init = nullptr;
    1056                                 } // if
    1057                                 // delete ctorInit;
    1058                                 return objDecl;
    1059                         } // if
    1060                         return _objDecl;
    1061                 }
    1062 
    1063                 void ObjDeclCollector::previsit( const ast::CompoundStmt * ) {
    1064                         GuardValue( curVars );
    1065                 }
    1066 
    1067                 void ObjDeclCollector::previsit( const ast::DeclStmt * stmt ) {
    1068                         // keep track of all variables currently in scope
    1069                         if ( auto objDecl = stmt->decl.as<ast::ObjectDecl>() ) {
    1070                                 curVars.push_back( objDecl );
    1071                         } // if
    1072                 }
    1073 
    1074                 void LabelFinder::previsit( const ast::Stmt * stmt ) {
    1075                         // for each label, remember the variables in scope at that label.
    1076                         for ( auto l : stmt->labels ) {
    1077                                 vars[l] = curVars;
    1078                         } // for
    1079                 }
    1080 
    1081                 void LabelFinder::previsit( const ast::CompoundStmt * stmt ) {
    1082                         previsit( (const ast::Stmt *) stmt );
    1083                         Parent::previsit( stmt );
    1084                 }
    1085 
    1086                 void LabelFinder::previsit( const ast::DeclStmt * stmt ) {
    1087                         previsit( (const ast::Stmt *)stmt );
    1088                         Parent::previsit( stmt );
    1089                 }
    1090 
    1091 
    1092                 void InsertDtors::previsit( const ast::FunctionDecl * funcDecl ) {
    1093                         // each function needs to have its own set of labels
    1094                         GuardValue( labelVars );
    1095                         labelVars.clear();
    1096                         // LabelFinder does not recurse into FunctionDecl, so need to visit
    1097                         // its children manually.
    1098                         if (funcDecl->type) funcDecl->type->accept(finder);
    1099                         // maybeAccept( funcDecl->type, finder );
    1100                         if (funcDecl->stmts) funcDecl->stmts->accept(finder) ;
    1101 
    1102                         // all labels for this function have been collected, insert destructors as appropriate via implicit recursion.
    1103                 }
    1104 
    1105                 // Handle break/continue/goto in the same manner as C++.  Basic idea: any objects that are in scope at the
    1106                 // BranchStmt but not at the labelled (target) statement must be destructed.  If there are any objects in scope
    1107                 // at the target location but not at the BranchStmt then those objects would be uninitialized so notify the user
    1108                 // of the error.  See C++ Reference 6.6 Jump Statements for details.
    1109                 void InsertDtors::handleGoto( const ast::BranchStmt * stmt ) {
    1110                         // can't do anything for computed goto
    1111                         if ( stmt->computedTarget ) return;
    1112 
    1113                         assertf( stmt->target.name != "", "BranchStmt missing a label: %s", toString( stmt ).c_str() );
    1114                         // S_L = lvars = set of objects in scope at label definition
    1115                         // S_G = curVars = set of objects in scope at goto statement
    1116                         ObjectSet & lvars = labelVars[ stmt->target ];
    1117 
    1118                         DTOR_PRINT(
    1119                                 std::cerr << "at goto label: " << stmt->target.name << std::endl;
    1120                                 std::cerr << "S_G = " << printSet( curVars ) << std::endl;
    1121                                 std::cerr << "S_L = " << printSet( lvars ) << std::endl;
    1122                         )
    1123 
    1124 
    1125                         // std::set_difference requires that the inputs be sorted.
    1126                         lvars.sort();
    1127                         curVars.sort();
    1128 
    1129                         ObjectSet diff;
    1130                         // S_L-S_G results in set of objects whose construction is skipped - it's an error if this set is non-empty
    1131                         std::set_difference( lvars.begin(), lvars.end(), curVars.begin(), curVars.end(), std::inserter( diff, diff.begin() ) );
    1132                         DTOR_PRINT(
    1133                                 std::cerr << "S_L-S_G = " << printSet( diff ) << std::endl;
    1134                         )
    1135                         if ( ! diff.empty() ) {
    1136                                 SemanticError( stmt, std::string("jump to label '") + stmt->target.name + "' crosses initialization of " + (*diff.begin())->name + " " );
    1137                         } // if
    1138                 }
    1139 
    1140                 void InsertDtors::previsit( const ast::BranchStmt * stmt ) {
    1141                         switch( stmt->kind ) {
    1142                           case ast::BranchStmt::Continue:
    1143                           case ast::BranchStmt::Break:
    1144                                 // could optimize the break/continue case, because the S_L-S_G check is unnecessary (this set should
    1145                                 // always be empty), but it serves as a small sanity check.
    1146                           case ast::BranchStmt::Goto:
    1147                                 handleGoto( stmt );
    1148                                 break;
    1149                           default:
    1150                                 assert( false );
    1151                         } // switch
    1152                 }
    1153 
    1154                 bool checkWarnings( const ast::FunctionDecl * funcDecl ) {
    1155                         // only check for warnings if the current function is a user-defined
    1156                         // constructor or destructor
    1157                         if ( ! funcDecl ) return false;
    1158                         if ( ! funcDecl->stmts ) return false;
    1159                         return CodeGen::isCtorDtor( funcDecl->name ) && ! funcDecl->linkage.is_overrideable;
    1160                 }
    1161 
    1162                 void GenStructMemberCalls::previsit( const ast::FunctionDecl * funcDecl ) {
    1163                         GuardValue( function );
    1164                         GuardValue( unhandled );
    1165                         GuardValue( usedUninit );
    1166                         GuardValue( thisParam );
    1167                         GuardValue( isCtor );
    1168                         GuardValue( structDecl );
    1169                         errors = SemanticErrorException();  // clear previous errors
    1170 
    1171                         // need to start with fresh sets
    1172                         unhandled.clear();
    1173                         usedUninit.clear();
    1174 
    1175                         function = mutate(funcDecl);
    1176                         // could this be non-unique?
    1177                         if (function != funcDecl) {
    1178                                 std::cerr << "GenStructMemberCalls: non-unique FunctionDecl " << funcDecl->location << funcDecl->name << std::endl;
    1179                         }
    1180 
    1181                         isCtor = CodeGen::isConstructor( function->name );
    1182                         if ( checkWarnings( function ) ) {
    1183                                 // const ast::FunctionType * type = function->type;
    1184                                 // assert( ! type->params.empty() );
    1185                                 thisParam = function->params.front().strict_as<ast::ObjectDecl>();
    1186                                 auto thisType = getPointerBase( thisParam->get_type() );
    1187                                 auto structType = dynamic_cast< const ast::StructInstType * >( thisType );
    1188                                 if ( structType ) {
    1189                                         structDecl = structType->base;
    1190                                         for ( auto & member : structDecl->members ) {
    1191                                                 if ( auto field = member.as<ast::ObjectDecl>() ) {
    1192                                                         // record all of the struct type's members that need to be constructed or
    1193                                                         // destructed by the end of the function
    1194                                                         unhandled.insert( field );
    1195                                                 }
    1196                                         }
    1197                                 }
    1198                         }
    1199                 }
    1200 
    1201                 const ast::DeclWithType * GenStructMemberCalls::postvisit( const ast::FunctionDecl * funcDecl ) {
    1202                         // remove the unhandled objects from usedUninit, because a call is inserted
    1203                         // to handle them - only objects that are later constructed are used uninitialized.
    1204                         std::map< const ast::DeclWithType *, CodeLocation > diff;
    1205                         // need the comparator since usedUninit and unhandled have different types
    1206                         struct comp_t {
    1207                                 typedef decltype(usedUninit)::value_type usedUninit_t;
    1208                                 typedef decltype(unhandled)::value_type unhandled_t;
    1209                                 bool operator()(usedUninit_t x, unhandled_t y) { return x.first < y; }
    1210                                 bool operator()(unhandled_t x, usedUninit_t y) { return x < y.first; }
    1211                         } comp;
    1212                         std::set_difference( usedUninit.begin(), usedUninit.end(), unhandled.begin(), unhandled.end(), std::inserter( diff, diff.begin() ), comp );
    1213                         for ( auto p : diff ) {
    1214                                 auto member = p.first;
    1215                                 auto loc = p.second;
    1216                                 // xxx - make error message better by also tracking the location that the object is constructed at?
    1217                                 emit( loc, "in ", function->name, ", field ", member->name, " used before being constructed" );
    1218                         }
    1219 
    1220                         const CodeLocation loc = funcDecl->location;
    1221 
    1222                         if ( ! unhandled.empty() ) {
    1223                                 auto mutStmts = function->stmts.get_and_mutate();
    1224                                 // need to explicitly re-add function parameters to the indexer in order to resolve copy constructors
    1225                                 auto guard = makeFuncGuard( [this]() { symtab.enterScope(); }, [this]() { symtab.leaveScope(); } );
    1226                                 symtab.addFunction( function );
    1227 
    1228                                 // need to iterate through members in reverse in order for
    1229                                 // ctor/dtor statements to come out in the right order
    1230                                 for ( auto & member : reverseIterate( structDecl->members ) ) {
    1231                                         auto field = member.as<ast::ObjectDecl>();
    1232                                         // skip non-DWT members
    1233                                         if ( ! field ) continue;
    1234                                         // skip non-constructable members
    1235                                         if ( ! tryConstruct( field ) ) continue;
    1236                                         // skip handled members
    1237                                         if ( ! unhandled.count( field ) ) continue;
    1238 
    1239                                         // insert and resolve default/copy constructor call for each field that's unhandled
    1240                                         // std::list< const ast::Stmt * > stmt;
    1241                                         ast::Expr * arg2 = nullptr;
    1242                                         if ( function->name == "?{}" && isCopyFunction( function ) ) {
    1243                                                 // if copy ctor, need to pass second-param-of-this-function.field
    1244                                                 // std::list< DeclarationWithType * > & params = function->get_functionType()->get_parameters();
    1245                                                 assert( function->params.size() == 2 );
    1246                                                 arg2 = new ast::MemberExpr(funcDecl->location, field, new ast::VariableExpr(funcDecl->location, function->params.back() ) );
    1247                                         }
    1248                                         InitExpander_new srcParam( arg2 );
    1249                                         // cast away reference type and construct field.
    1250                                         ast::Expr * thisExpr = new ast::CastExpr(funcDecl->location, new ast::VariableExpr(funcDecl->location, thisParam ), thisParam->get_type()->stripReferences());
    1251                                         ast::Expr * memberDest = new ast::MemberExpr(funcDecl->location, field, thisExpr );
    1252                                         ast::ptr<ast::Stmt> callStmt = SymTab::genImplicitCall( srcParam, memberDest, loc, function->name, field, static_cast<SymTab::LoopDirection>(isCtor) );
    1253 
    1254                                         if ( callStmt ) {
    1255                                                 // auto & callStmt = stmt.front();
    1256 
    1257                                                 try {
    1258                                                         callStmt = callStmt->accept( *visitor );
    1259                                                         if ( isCtor ) {
    1260                                                                 mutStmts->push_front( callStmt );
    1261                                                         } else { // TODO: don't generate destructor function/object for intrinsic calls
    1262                                                                 // destructor statements should be added at the end
    1263                                                                 // function->get_statements()->push_back( callStmt );
    1264 
    1265                                                                 // Optimization: do not need to call intrinsic destructors on members
    1266                                                                 if ( isIntrinsicSingleArgCallStmt( callStmt ) ) continue;
    1267 
    1268                                                                 // __Destructor _dtor0 = { (void *)&b.a1, (void (*)(void *)_destroy_A };
    1269                                                                 std::list< ast::ptr<ast::Stmt> > stmtsToAdd;
    1270 
    1271                                                                 static UniqueName memberDtorNamer = { "__memberDtor" };
    1272                                                                 assertf( Validate::dtorStruct, "builtin __Destructor not found." );
    1273                                                                 assertf( Validate::dtorStructDestroy, "builtin __destroy_Destructor not found." );
    1274 
    1275                                                                 ast::Expr * thisExpr = new ast::CastExpr( new ast::AddressExpr( new ast::VariableExpr(loc, thisParam ) ), new ast::PointerType( new ast::VoidType(), ast::CV::Qualifiers() ) );
    1276                                                                 ast::Expr * dtorExpr = new ast::VariableExpr(loc, getDtorFunc( thisParam, callStmt, stmtsToAdd ) );
    1277 
    1278                                                                 // cast destructor pointer to void (*)(void *), to silence GCC incompatible pointer warnings
    1279                                                                 auto dtorFtype = new ast::FunctionType();
    1280                                                                 dtorFtype->params.emplace_back( new ast::PointerType( new ast::VoidType() ) );
    1281                                                                 auto dtorType = new ast::PointerType( dtorFtype );
    1282 
    1283                                                                 auto destructor = new ast::ObjectDecl(loc, memberDtorNamer.newName(), new ast::StructInstType( ast::dtorStruct ), new ast::ListInit(loc, { new ast::SingleInit(loc, thisExpr ), new ast::SingleInit(loc, new ast::CastExpr( dtorExpr, dtorType ) ) } ) );
    1284                                                                 destructor->attributes.push_back( new ast::Attribute( "cleanup", { new ast::VariableExpr({}, ast::dtorStructDestroy ) } ) );
    1285                                                                 mutStmts->push_front( new ast::DeclStmt(loc, destructor ) );
    1286                                                                 mutStmts->kids.splice( mutStmts->kids.begin(), stmtsToAdd );
    1287                                                         }
    1288                                                 } catch ( SemanticErrorException & error ) {
    1289                                                         emit( funcDecl->location, "in ", function->name , ", field ", field->name, " not explicitly ", isCtor ? "constructed" : "destructed",  " and no ", isCtor ? "default constructor" : "destructor", " found" );
    1290                                                 }
    1291                                         }
    1292                                 }
    1293                                 function->stmts = mutStmts;
    1294                         }
    1295                         if (! errors.isEmpty()) {
    1296                                 throw errors;
    1297                         }
    1298                         // return funcDecl;
    1299                         return function;
    1300                 }
    1301 
    1302                 /// true if expr is effectively just the 'this' parameter
    1303                 bool isThisExpression( const ast::Expr * expr, const ast::DeclWithType * thisParam ) {
    1304                         // TODO: there are more complicated ways to pass 'this' to a constructor, e.g. &*, *&, etc.
    1305                         if ( auto varExpr = dynamic_cast< const ast::VariableExpr * >( expr ) ) {
    1306                                 return varExpr->var == thisParam;
    1307                         } else if ( auto castExpr = dynamic_cast< const ast::CastExpr * > ( expr ) ) {
    1308                                 return isThisExpression( castExpr->arg, thisParam );
    1309                         }
    1310                         return false;
    1311                 }
    1312 
    1313                 /// returns a MemberExpr if expr is effectively just member access on the 'this' parameter, else nullptr
    1314                 const ast::MemberExpr * isThisMemberExpr( const ast::Expr * expr, const ast::DeclWithType * thisParam ) {
    1315                         if ( auto memberExpr = dynamic_cast< const ast::MemberExpr * >( expr ) ) {
    1316                                 if ( isThisExpression( memberExpr->aggregate, thisParam ) ) {
    1317                                         return memberExpr;
    1318                                 }
    1319                         } else if ( auto castExpr = dynamic_cast< const ast::CastExpr * >( expr ) ) {
    1320                                 return isThisMemberExpr( castExpr->arg, thisParam );
    1321                         }
    1322                         return nullptr;
    1323                 }
    1324 
    1325                 void GenStructMemberCalls::previsit( const ast::ApplicationExpr * appExpr ) {
    1326                         if ( ! checkWarnings( function ) ) {
    1327                                 visit_children = false;
    1328                                 return;
    1329                         }
    1330 
    1331                         std::string fname = getFunctionName( appExpr );
    1332                         if ( fname == function->name ) {
    1333                                 // call to same kind of function
    1334                                 const ast::Expr * firstParam = appExpr->args.front();
    1335 
    1336                                 if ( isThisExpression( firstParam, thisParam ) ) {
    1337                                         // if calling another constructor on thisParam, assume that function handles
    1338                                         // all members - if it doesn't a warning will appear in that function.
    1339                                         unhandled.clear();
    1340                                 } else if ( auto memberExpr = isThisMemberExpr( firstParam, thisParam ) ) {
    1341                                         // if first parameter is a member expression on the this parameter,
    1342                                         // then remove the member from unhandled set.
    1343                                         if ( isThisExpression( memberExpr->aggregate, thisParam ) ) {
    1344                                                 unhandled.erase( memberExpr->member );
    1345                                         }
    1346                                 }
    1347                         }
    1348                 }
    1349 
    1350                 void GenStructMemberCalls::previsit( const ast::MemberExpr * memberExpr ) {
    1351                         if ( ! checkWarnings( function ) || ! isCtor ) {
    1352                                 visit_children = false;
    1353                                 return;
    1354                         }
    1355 
    1356                         if ( isThisExpression( memberExpr->aggregate, thisParam ) ) {
    1357                                 if ( unhandled.count( memberExpr->member ) ) {
    1358                                         // emit a warning because a member was used before it was constructed
    1359                                         usedUninit.insert( { memberExpr->member, memberExpr->location } );
    1360                                 }
    1361                         }
    1362                 }
    1363 
    1364                 template< typename Visitor, typename... Params >
    1365                 void error( Visitor & v, CodeLocation loc, const Params &... params ) {
    1366                         SemanticErrorException err( loc, toString( params... ) );
    1367                         v.errors.append( err );
    1368                 }
    1369 
    1370                 template< typename... Params >
    1371                 void GenStructMemberCalls::emit( CodeLocation loc, const Params &... params ) {
    1372                         // toggle warnings vs. errors here.
    1373                         // warn( params... );
    1374                         error( *this, loc, params... );
    1375                 }
    1376 
    1377                 const ast::Expr * GenStructMemberCalls::postvisit( const ast::UntypedExpr * untypedExpr ) {
    1378                         // Expression * newExpr = untypedExpr;
    1379                         // xxx - functions returning ast::ptr seems wrong...
    1380                         auto res = ResolvExpr::findVoidExpression( untypedExpr, symtab );
    1381                         return res.release();
    1382                         // return newExpr;
    1383                 }
    1384 
    1385                 void InsertImplicitCalls::previsit(const ast::UniqueExpr * unqExpr) {
    1386                         if (visitedIds.count(unqExpr->id)) visit_children = false;
    1387                         else visitedIds.insert(unqExpr->id);
    1388                 }
    1389 
    1390                 const ast::Expr * FixCtorExprs::postvisit( const ast::ConstructorExpr * ctorExpr ) {
    1391                         const CodeLocation loc = ctorExpr->location;
    1392                         static UniqueName tempNamer( "_tmp_ctor_expr" );
    1393                         // xxx - is the size check necessary?
    1394                         assert( ctorExpr->result && ctorExpr->result->size() == 1 );
    1395 
    1396                         // xxx - this can be TupleAssignExpr now. Need to properly handle this case.
    1397                         // take possession of expr and env
    1398                         ast::ptr<ast::ApplicationExpr> callExpr = ctorExpr->callExpr.strict_as<ast::ApplicationExpr>();
    1399                         ast::ptr<ast::TypeSubstitution> env = ctorExpr->env;
    1400                         // ctorExpr->set_callExpr( nullptr );
    1401                         // ctorExpr->set_env( nullptr );
    1402 
    1403                         // xxx - ideally we would reuse the temporary generated from the copy constructor passes from within firstArg if it exists and not generate a temporary if it's unnecessary.
    1404                         auto tmp = new ast::ObjectDecl(loc, tempNamer.newName(), callExpr->args.front()->result );
    1405                         declsToAddBefore.push_back( tmp );
    1406                         // delete ctorExpr;
    1407 
    1408                         // build assignment and replace constructor's first argument with new temporary
    1409                         auto mutCallExpr = callExpr.get_and_mutate();
    1410                         const ast::Expr * firstArg = callExpr->args.front();
    1411                         ast::Expr * assign = new ast::UntypedExpr(loc, new ast::NameExpr(loc, "?=?" ), { new ast::AddressExpr(loc, new ast::VariableExpr(loc, tmp ) ), new ast::AddressExpr( firstArg ) } );
    1412                         firstArg = new ast::VariableExpr(loc, tmp );
    1413                         mutCallExpr->args.front() = firstArg;
    1414 
    1415                         // resolve assignment and dispose of new env
    1416                         auto resolved = ResolvExpr::findVoidExpression( assign, symtab );
    1417                         auto mut = resolved.get_and_mutate();
    1418                         assertf(resolved.get() == mut, "newly resolved expression must be unique");
    1419                         mut->env = nullptr;
    1420 
    1421                         // for constructor expr:
    1422                         //   T x;
    1423                         //   x{};
    1424                         // results in:
    1425                         //   T x;
    1426                         //   T & tmp;
    1427                         //   &tmp = &x, ?{}(tmp), tmp
    1428                         ast::CommaExpr * commaExpr = new ast::CommaExpr(loc, resolved, new ast::CommaExpr(loc, mutCallExpr, new ast::VariableExpr(loc, tmp ) ) );
    1429                         commaExpr->env = env;
    1430                         return commaExpr;
    1431                 }
    1432         } // namespace
     1298                        return;
     1299                }
     1300
     1301                if ( isThisExpression( memberExpr->aggregate, thisParam ) ) {
     1302                        if ( unhandled.count( memberExpr->member ) ) {
     1303                                // emit a warning because a member was used before it was constructed
     1304                                usedUninit.insert( { memberExpr->member, memberExpr->location } );
     1305                        }
     1306                }
     1307        }
     1308
     1309        template< typename Visitor, typename... Params >
     1310        void error( Visitor & v, CodeLocation loc, const Params &... params ) {
     1311                SemanticErrorException err( loc, toString( params... ) );
     1312                v.errors.append( err );
     1313        }
     1314
     1315        template< typename... Params >
     1316        void GenStructMemberCalls::emit( CodeLocation loc, const Params &... params ) {
     1317                // toggle warnings vs. errors here.
     1318                // warn( params... );
     1319                error( *this, loc, params... );
     1320        }
     1321
     1322        const ast::Expr * GenStructMemberCalls::postvisit( const ast::UntypedExpr * untypedExpr ) {
     1323                // Expression * newExpr = untypedExpr;
     1324                // xxx - functions returning ast::ptr seems wrong...
     1325                auto res = ResolvExpr::findVoidExpression( untypedExpr, symtab );
     1326                return res.release();
     1327                // return newExpr;
     1328        }
     1329
     1330        void InsertImplicitCalls::previsit(const ast::UniqueExpr * unqExpr) {
     1331                if (visitedIds.count(unqExpr->id)) visit_children = false;
     1332                else visitedIds.insert(unqExpr->id);
     1333        }
     1334
     1335        const ast::Expr * FixCtorExprs::postvisit( const ast::ConstructorExpr * ctorExpr ) {
     1336                const CodeLocation loc = ctorExpr->location;
     1337                static UniqueName tempNamer( "_tmp_ctor_expr" );
     1338                // xxx - is the size check necessary?
     1339                assert( ctorExpr->result && ctorExpr->result->size() == 1 );
     1340
     1341                // xxx - this can be TupleAssignExpr now. Need to properly handle this case.
     1342                // take possession of expr and env
     1343                ast::ptr<ast::ApplicationExpr> callExpr = ctorExpr->callExpr.strict_as<ast::ApplicationExpr>();
     1344                ast::ptr<ast::TypeSubstitution> env = ctorExpr->env;
     1345                // ctorExpr->set_callExpr( nullptr );
     1346                // ctorExpr->set_env( nullptr );
     1347
     1348                // xxx - ideally we would reuse the temporary generated from the copy constructor passes from within firstArg if it exists and not generate a temporary if it's unnecessary.
     1349                auto tmp = new ast::ObjectDecl(loc, tempNamer.newName(), callExpr->args.front()->result );
     1350                declsToAddBefore.push_back( tmp );
     1351                // delete ctorExpr;
     1352
     1353                // build assignment and replace constructor's first argument with new temporary
     1354                auto mutCallExpr = callExpr.get_and_mutate();
     1355                const ast::Expr * firstArg = callExpr->args.front();
     1356                ast::Expr * assign = new ast::UntypedExpr(loc, new ast::NameExpr(loc, "?=?" ), { new ast::AddressExpr(loc, new ast::VariableExpr(loc, tmp ) ), new ast::AddressExpr( firstArg ) } );
     1357                firstArg = new ast::VariableExpr(loc, tmp );
     1358                mutCallExpr->args.front() = firstArg;
     1359
     1360                // resolve assignment and dispose of new env
     1361                auto resolved = ResolvExpr::findVoidExpression( assign, symtab );
     1362                auto mut = resolved.get_and_mutate();
     1363                assertf(resolved.get() == mut, "newly resolved expression must be unique");
     1364                mut->env = nullptr;
     1365
     1366                // for constructor expr:
     1367                //   T x;
     1368                //   x{};
     1369                // results in:
     1370                //   T x;
     1371                //   T & tmp;
     1372                //   &tmp = &x, ?{}(tmp), tmp
     1373                ast::CommaExpr * commaExpr = new ast::CommaExpr(loc, resolved, new ast::CommaExpr(loc, mutCallExpr, new ast::VariableExpr(loc, tmp ) ) );
     1374                commaExpr->env = env;
     1375                return commaExpr;
     1376        }
     1377} // namespace
    14331378} // namespace InitTweak
    14341379
Note: See TracChangeset for help on using the changeset viewer.