Index: doc/bibliography/pl.bib =================================================================== --- doc/bibliography/pl.bib (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ doc/bibliography/pl.bib (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -188,9 +188,9 @@ Unstructured {\it sends\/} and {\it accepts\/} are forbidden. To this the mechanisms of {\it delegation\/} and {\it delay queues\/} - are added to enable switching and triggering of activities. - Concurrent subactivities and atomic actions are provided for + are added to enable switching and triggering of activities. + Concurrent subactivities and atomic actions are provided for compactness and simplicity. We show how solutions to many important concurrent problems [sic], such as pipelining, constraint management - and ``administration'' can be compactly expressed using these + and ``administration'' can be compactly expressed using these mechanisms. }, @@ -529,5 +529,5 @@ like ``c is a collection with element type e'', but how such things are used isn't explained. - + For each descriptive class used in a parameter list, an implicit parameter is created that is passed a vector of procedures. @@ -1172,5 +1172,5 @@ @techreport{Prokopec11, keywords = {ctrie, concurrent map}, - contributer = {a3moss@uwaterloo.ca}, + contributer = {a3moss@uwaterloo.ca}, title = {Cache-aware lock-free concurrent hash tries}, author = {Prokopec, Aleksandar and Bagwell, Phil and Odersky, Martin}, @@ -1500,5 +1500,5 @@ year = 2001, url = {http://citeseer.ist.psu.edu/berger01composing.html} -} +} @article{Andrews83, @@ -1545,5 +1545,5 @@ We give a rationale for our decisions and compare Concurrent C extensions with the concurrent programming facilities in Ada. - Concurrent C has been implemented on the UNIX system running on a + Concurrent C has been implemented on the UNIX system running on a single processor. A distributed version of Concurrent C is being implemented. @@ -1814,5 +1814,5 @@ keywords = {objects, concurrency}, contributer = {gjditchfield@plg}, - author = {P. A. Buhr and G. J. Ditchfield and B. M. Younger and C. R. Zarnke}, + author = {P. A. Buhr and G. J. Ditchfield and B. M. Younger and C. R. Zarnke}, title = {Concurrency in {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}}}, institution = {Department of Computer Science, University of Waterloo}, @@ -2044,5 +2044,5 @@ series = {Lecture Notes in Computer Science, Ed. by G. Goos and J. Hartmanis} } - + @article{Wang71, keywords = {coroutines}, @@ -2056,5 +2056,5 @@ pages = {425-449}, } - + @article{Castagna95, keywords = {type-systems, covariance, contravariance}, @@ -2390,5 +2390,5 @@ year = 1996, } - + @article{Richardson93, keywords = {C++, persistence, database}, @@ -2473,5 +2473,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} @article{design, @@ -2700,5 +2700,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} @book{Eiffel, @@ -3357,5 +3357,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} @manual{Fortran95, @@ -3740,5 +3740,5 @@ keywords = {processes, distributed computing}, contributer = {pabuhr@plg}, - author = {Robert E. Strom and David F. Bacon and Arthur P. Goldberg and Andy Lowry and Daniel M. Yellin and Shaula Alexander Yemini}, + author = {Robert E. Strom and David F. Bacon and Arthur P. Goldberg and Andy Lowry and Daniel M. Yellin and Shaula Alexander Yemini}, title = {Hermes: A Language for Distributed Computing}, institution = {IBM T. J. Watson Research Center}, @@ -3751,5 +3751,5 @@ keywords = {processes, distributed computing}, contributer = {pabuhr@plg}, - author = {Robert E. Strom and David F. Bacon and Arthur P. Goldberg and Andy Lowry and Daniel M. Yellin and Shaula Alexander Yemini}, + author = {Robert E. Strom and David F. Bacon and Arthur P. Goldberg and Andy Lowry and Daniel M. Yellin and Shaula Alexander Yemini}, title = {Hermes: A Language for Distributed Computing}, publisher = {Prentice-Hall}, @@ -4302,5 +4302,5 @@ pages = {85-103} } - + @article{Murer96, keywords = {interators, generators, cursors}, @@ -4330,5 +4330,5 @@ % J - + @book{Java, keywords = {Java}, @@ -4627,5 +4627,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} @article{Dice15, @@ -4978,5 +4978,5 @@ number = 31 } - + @article{Dueck90, keywords = {attribute grammars}, @@ -5107,5 +5107,5 @@ keywords = {multiple inheritance}, contributer = {pabuhr@plg}, - author = {Harry Bretthauer and Thomas Christaller and J\"{u}rgen Kopp}, + author = {Harry Bretthauer and Thomas Christaller and J\"{u}rgen Kopp}, title = {Multiple vs. Single Inheritance in Object-oriented Programming Languages. What do we really want?}, institution = {Gesellschaft F\"{u}r Mathematik und Datenverarbeitung mbH}, @@ -5650,5 +5650,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} @book{Deitel04, @@ -5827,5 +5827,5 @@ year = 1980, month = nov, volume = 15, number = 11, pages = {47-56}, - note = {Proceedings of the ACM-SIGPLAN Symposium on the {Ada} Programming Language}, + note = {Proceedings of the ACM-SIGPLAN Symposium on the {Ada} Programming Language}, comment = { The two-pass (bottom-up, then top-down) algorithm, with a proof @@ -5957,5 +5957,5 @@ Given a base typed lambda calculus with function types, type abstractions, and a recursive expression \(\mbox{fix } x:t.e\), - then type inference for the partially typed language + then type inference for the partially typed language \begin{eqnarray} \lambda x:\tau.e &\Rightarrow& \lambda x.e \\ @@ -6603,5 +6603,5 @@ manner. The paper also discusses efficient composition of sequences of asynchronous calls to different locations in a - network. + network. } } @@ -6616,5 +6616,5 @@ volume = 32, number = 4, pages = {305-311}, abstract = { - + } } @@ -6934,5 +6934,5 @@ partitioning switch statements into dense tables. It also implements target-independent function tracing and expression-level - profiling. + profiling. } } @@ -7150,5 +7150,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} @inproceedings{Leissa14, @@ -7268,5 +7268,5 @@ keywords = {Smalltalk, abstract class, protocol}, contributer = {gjditchfield@plg}, - author = {A. Goldberg and D. Robson}, + author = {A. Goldberg and D. Robson}, title = {Smalltalk-80: The Language and its Implementation}, publisher = {Addison-Wesley}, @@ -7845,5 +7845,5 @@ title = {Thread (computing)}, author = {{Threading Model}}, - howpublished= {\href{https://en.wikipedia.org/wiki/Thread_(computing)}{https://\-en.wikipedia.org/\-wiki/\-Thread\_(computing)}}, + howpublished= {\href{https://en.wikipedia.org/wiki/Thread_(computing)}{https://\-en.wikipedia.org/\-wiki/\-Thread\_\-(computing)}}, } @@ -7889,5 +7889,5 @@ note = {Lecture Notes in Computer Science, v. 19}, abstract = { - + } } @@ -8008,5 +8008,5 @@ publisher = {USENIX Association}, address = {Berkeley, CA, USA}, -} +} @article{Leroy00, @@ -8354,5 +8354,5 @@ author = {Bjarne Stroustrup}, title = {What is ``Object-Oriented Programming''?}, - booktitle = {Proceedings of the First European Conference on Object Oriented Programming}, + booktitle = {Proceedings of the First European Conference on Object Oriented Programming}, month = jun, year = 1987 @@ -8396,5 +8396,5 @@ publisher = {ACM}, address = {New York, NY, USA}, -} +} % X Index: doc/theses/thierry_delisle_PhD/thesis/local.bib =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/local.bib (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ doc/theses/thierry_delisle_PhD/thesis/local.bib (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -583,5 +583,5 @@ title={Per-entity load tracking}, author={Corbet, Jonathan}, - journal={LWN article, available at: https://lwn.net/Articles/531853}, + journal={LWN article, available at: {\href{https://lwn.net/Articles/531853}{https://\-lwn.net/\-Articles/\-531853}}}, year={2013} } @@ -717,5 +717,5 @@ title = {Scheduling Benchmarks}, author = {Thierry Delisle}, - howpublished = {\href{https://github.com/cforall/SchedulingBenchmarks_PhD22}{https://\-github.com/\-cforall/\-SchedulingBenchmarks\_\-PhD22}}, + howpublished = {\href{https://github.com/cforall/SchedulingBenchmarks_PhD22}{https://\-github.com/\-cforall/\-Scheduling\-Benchmarks\_\-PhD22}}, } @@ -832,5 +832,5 @@ title = "eventfd(2) Linux User's Manual", year = "2019", - month = "MArch", + month = "March", } @@ -1060,5 +1060,5 @@ year = "2020", month = "June", - howpublished = "\href{https://xkcd.com/2318/}", + howpublished = "\href{https://xkcd.com/2318/}{https://\-xkcd.com/\-2318/}", note = "[Online; accessed 10-June-2020]" } @@ -1069,5 +1069,5 @@ year = "2011", month = "June", - howpublished = "\href{https://xkcd.com/908/}", + howpublished = "\href{https://xkcd.com/908/}{https://\-xkcd.com/\-908/}", note = "[Online; accessed 25-August-2022]" } Index: doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -187,5 +187,5 @@ Looking at the left column on AMD, Figures~\ref{fig:cycle:nasus:ops} and \ref{fig:cycle:nasus:ns} all 4 runtimes achieve very similar throughput and scalability. However, as the number of \procs grows higher, the results on AMD show notably more variability than on Intel. -The different performance improvements and plateaus are due to cache topology and appear at the expected: \proc counts of 64, 128 and 192, for the same reasons as on Intel. +The different performance improvements and plateaus are due to cache topology and appear at the expected \proc counts of 64, 128 and 192, for the same reasons as on Intel. Looking next at the right column on AMD, Figures~\ref{fig:cycle:nasus:low:ops} and \ref{fig:cycle:nasus:low:ns}, Tokio and Go have the same throughput performance, while \CFA is slightly slower. This result is different than on Intel, where Tokio behaved like \CFA rather than behaving like Go. @@ -491,6 +491,6 @@ \section{Locality} -As mentioned in the churn benchmark, when \glslink{atsched}{unparking} a \at, it is possible to either \unpark to the local or remote ready-queue.\footnote{ -It is also possible to \unpark to a third unrelated ready-queue, but without additional knowledge about the situation, it is likely to degrade performance.} +As mentioned in the churn benchmark, when \glslink{atsched}{unparking} a \at, it is possible to either \unpark to the local or remote sub-queue.\footnote{ +It is also possible to \unpark to a third unrelated sub-queue, but without additional knowledge about the situation, it is likely to degrade performance.} The locality experiment includes two variations of the churn benchmark, where a data array is added. In both variations, before @V@ing the semaphore, each \at calls a @work@ function which increments random cells inside the data array. @@ -720,6 +720,6 @@ In both variations, the experiment effectively measures how long it takes for all \ats to run once after a given synchronization point. -In an ideal scenario where the scheduler is strictly FIFO, every thread would run once after the synchronization and therefore the delay between leaders would be given by, $(CSL + SL) / (NP - 1)$, -where $CSL$ is the context-switch latency, $SL$ is the cost for enqueueing and dequeuing a \at, and $NP$ is the number of \procs. +In an ideal scenario where the scheduler is strictly FIFO, every thread would run once after the synchronization and therefore the delay between leaders would be given by, $NT(CSL + SL) / (NP - 1)$, +where $CSL$ is the context-switch latency, $SL$ is the cost for enqueueing and dequeuing a \at, $NT$ is the number of \ats, and $NP$ is the number of \procs. However, if the scheduler allows \ats to run many times before other \ats can run once, this delay increases. The semaphore version is an approximation of strictly FIFO scheduling, where none of the \ats \emph{attempt} to run more than once. @@ -734,7 +734,4 @@ \begin{table} -\caption[Transfer Benchmark on Intel and AMD]{Transfer Benchmark on Intel and AMD\smallskip\newline Average measurement of how long it takes for all \ats to acknowledge the leader \at. -DNC stands for ``did not complete'', meaning that after 5 seconds of a new leader being decided, some \ats still had not acknowledged the new leader.} -\label{fig:transfer:res} \setlength{\extrarowheight}{2pt} \setlength{\tabcolsep}{5pt} @@ -753,4 +750,7 @@ \end{tabular} \end{centering} +\caption[Transfer Benchmark on Intel and AMD]{Transfer Benchmark on Intel and AMD\smallskip\newline Average measurement of how long it takes for all \ats to acknowledge the leader \at. +DNC stands for ``did not complete'', meaning that after 5 seconds of a new leader being decided, some \ats still had not acknowledged the new leader.} +\label{fig:transfer:res} \end{table} @@ -768,9 +768,8 @@ Looking at the next two columns, the results for the yield variation on Intel, the story is very different. -\CFA achieves better latencies, presumably due to no synchronization with the yield. +\CFA achieves better latencies, presumably due to the lack of synchronization with the yield. Go does complete the experiment, but with drastically higher latency: latency at 2 \procs is $350\times$ higher than \CFA and $70\times$ higher at 192 \procs. -This difference is because Go has a classic work-stealing scheduler, but it adds coarse-grain preemption -, which interrupts the spinning leader after a period. +This difference is because Go has a classic work-stealing scheduler, but it adds coarse-grain preemption, which interrupts the spinning leader after a period. Neither Libfibre nor Tokio complete the experiment. Both runtimes also use classical work-stealing scheduling without preemption, and therefore, none of the work queues are ever emptied so no load balancing occurs. Index: doc/theses/thierry_delisle_PhD/thesis/text/io.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/io.tex (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ doc/theses/thierry_delisle_PhD/thesis/text/io.tex (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -25,5 +25,5 @@ \paragraph{\lstinline{select}} is the oldest of these options, and takes as input a contiguous array of bits, where each bit represents a file descriptor of interest. Hence, the array length must be as long as the largest FD currently of interest. -On return, it outputs the set in place to identify which of the file descriptors changed state. +On return, it outputs the set motified in place to identify which of the file descriptors changed state. This destructive change means selecting in a loop requires re-initializing the array for each iteration. Another limit of @select@ is that calls from different \glspl{kthrd} sharing FDs are independent. @@ -35,5 +35,5 @@ \paragraph{\lstinline{poll}} is the next oldest option, and takes as input an array of structures containing the FD numbers rather than their position in an array of bits, allowing a more compact input for interest sets that contain widely spaced FDs. For small interest sets with densely packed FDs, the @select@ bit mask can take less storage, and hence, copy less information into the kernel. -Furthermore, @poll@ is non-destructive, so the array of structures does not have to be re-initialized on every call. +However, @poll@ is non-destructive, so the array of structures does not have to be re-initialized on every call. Like @select@, @poll@ suffers from the limitation that the interest set cannot be changed by other \glspl{kthrd}, while a manager thread is blocked in @poll@. @@ -314,5 +314,5 @@ A simple approach to polling is to allocate a \at per @io_uring@ instance and simply let the poller \ats poll their respective instances when scheduled. -With the pool of SEQ instances approach, the big advantage is that it is fairly flexible. +With the pool of SQE instances approach, the big advantage is that it is fairly flexible. It does not impose restrictions on what \ats submitting \io operations can and cannot do between allocations and submissions. It also can gracefully handle running out of resources, SQEs or the kernel returning @EBUSY@. @@ -320,5 +320,5 @@ The routing and allocation algorithm needs to keep track of which ring instances have available SQEs, block incoming requests if no instance is available, prevent barging if \ats are already queued up waiting for SQEs and handle SQEs being freed. The submission side needs to safely append SQEs to the ring buffer, correctly handle chains, make sure no SQE is dropped or left pending forever, notify the allocation side when SQEs can be reused, and handle the kernel returning @EBUSY@. -Compared to the private-instance approach, all this synchronization has a significant cost this synchronization is entirely overhead. +Compared to the private-instance approach, all this synchronization has a significant cost and this synchronization is entirely overhead. \subsubsection{Instance borrowing} Index: doc/theses/thierry_delisle_PhD/thesis/text/practice.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/practice.tex (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ doc/theses/thierry_delisle_PhD/thesis/text/practice.tex (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -101,5 +101,5 @@ This leaves too many \procs when there are not enough \ats for all the \procs to be useful. These idle \procs cannot be removed because their lifetime is controlled by the application, and only the application knows when the number of \ats may increase or decrease. -While idle \procs can spin until work appears, this approach wastes energy, unnecessarily produces heat and prevents other applications from using the processor. +While idle \procs can spin until work appears, this approach wastes energy, unnecessarily produces heat and prevents other applications from using the \gls{hthrd}. Therefore, idle \procs are put into an idle state, called \newterm{Idle-Sleep}, where the \gls{kthrd} is blocked until the scheduler deems it is needed. @@ -107,5 +107,5 @@ First, a data structure needs to keep track of all \procs that are in idle sleep. Because idle sleep is spurious, this data structure has strict performance requirements, in addition to strict correctness requirements. -Next, some mechanism is needed to block \glspl{kthrd}, \eg @pthread_cond_wait@ on a pthread semaphore. +Next, some mechanism is needed to block \glspl{kthrd}, \eg @pthread_cond_wait@ or a pthread semaphore. The complexity here is to support \at \glslink{atblock}{parking} and \glslink{atsched}{unparking}, user-level locking, timers, \io operations, and all other \CFA features with minimal complexity. Finally, the scheduler needs a heuristic to determine when to block and unblock an appropriate number of \procs. Index: libcfa/src/bits/locks.hfa =================================================================== --- libcfa/src/bits/locks.hfa (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ libcfa/src/bits/locks.hfa (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -13,6 +13,6 @@ // Created On : Tue Oct 31 15:14:38 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Aug 12 14:18:07 2020 -// Update Count : 13 +// Last Modified On : Mon Sep 19 18:51:53 2022 +// Update Count : 17 // @@ -60,9 +60,9 @@ disable_interrupts(); - for ( unsigned int i = 1;; i += 1 ) { + for ( i; 1 ~ @ ) { if ( (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0) ) break; #ifndef NOEXPBACK // exponential spin - for ( volatile unsigned int s = 0; s < spin; s += 1 ) Pause(); + for ( volatile unsigned int s; 0 ~ spin ) Pause(); // slowly increase by powers of 2 Index: libcfa/src/concurrency/kernel/cluster.hfa =================================================================== --- libcfa/src/concurrency/kernel/cluster.hfa (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ libcfa/src/concurrency/kernel/cluster.hfa (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -63,5 +63,5 @@ } } - return (max + 2 * max) / 2; + return 8 * max; } Index: libcfa/src/concurrency/kernel/fwd.hfa =================================================================== --- libcfa/src/concurrency/kernel/fwd.hfa (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ libcfa/src/concurrency/kernel/fwd.hfa (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -179,8 +179,9 @@ // Similar to a binary semaphore with a 'one shot' semantic // is expected to be discarded after each party call their side + enum(struct thread$ *) { oneshot_ARMED = 0p, oneshot_FULFILLED = 1p }; struct oneshot { // Internal state : - // 0p : is initial state (wait will block) - // 1p : fulfilled (wait won't block) + // armed : initial state, wait will block + // fulfilled : wait won't block // any thread : a thread is currently waiting struct thread$ * volatile ptr; @@ -189,5 +190,5 @@ static inline { void ?{}(oneshot & this) { - this.ptr = 0p; + this.ptr = oneshot_ARMED; } @@ -199,8 +200,8 @@ for() { struct thread$ * expected = this.ptr; - if(expected == 1p) return false; + if(expected == oneshot_FULFILLED) return false; if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { park(); - /* paranoid */ verify( this.ptr == 1p ); + /* paranoid */ verify( this.ptr == oneshot_FULFILLED ); return true; } @@ -211,6 +212,6 @@ // return true if a thread was unparked thread$ * post(oneshot & this, bool do_unpark = true) { - struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST); - if( got == 0p || got == 1p ) return 0p; + struct thread$ * got = __atomic_exchange_n( &this.ptr, oneshot_FULFILLED, __ATOMIC_SEQ_CST); + if( got == oneshot_ARMED || got == oneshot_FULFILLED ) return 0p; if(do_unpark) unpark( got ); return got; @@ -223,10 +224,11 @@ // thread on "any of" [a given set of] futures. // does not support multiple threads waiting on the same future + enum(struct oneshot *) { future_ARMED = 0p, future_FULFILLED = 1p, future_PROGRESS = 2p, future_ABANDONED = 3p }; struct future_t { // Internal state : - // 0p : is initial state (wait will block) - // 1p : fulfilled (wait won't block) - // 2p : in progress () - // 3p : abandoned, server should delete + // armed : initial state, wait will block + // fulfilled : result is ready, wait won't block + // progress : someone else is in the process of fulfilling this + // abandoned : client no longer cares, server should delete // any oneshot : a context has been setup to wait, a thread could wait on it struct oneshot * volatile ptr; @@ -235,5 +237,5 @@ static inline { void ?{}(future_t & this) { - this.ptr = 0p; + this.ptr = future_ARMED; } @@ -242,11 +244,11 @@ void reset(future_t & this) { // needs to be in 0p or 1p - __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST); + __atomic_exchange_n( &this.ptr, future_ARMED, __ATOMIC_SEQ_CST); } // check if the future is available bool available( future_t & this ) { - while( this.ptr == 2p ) Pause(); - return this.ptr == 1p; + while( this.ptr == future_PROGRESS ) Pause(); + return this.ptr == future_FULFILLED; } @@ -254,10 +256,10 @@ // intented to be use by wait, wait_any, waitfor, etc. rather than used directly bool setup( future_t & this, oneshot & wait_ctx ) { - /* paranoid */ verify( wait_ctx.ptr == 0p || wait_ctx.ptr == 1p ); + /* paranoid */ verify( wait_ctx.ptr == oneshot_ARMED || wait_ctx.ptr == oneshot_FULFILLED ); // The future needs to set the wait context for() { struct oneshot * expected = this.ptr; // Is the future already fulfilled? - if(expected == 1p) return false; // Yes, just return false (didn't block) + if(expected == future_FULFILLED) return false; // Yes, just return false (didn't block) // The future is not fulfilled, try to setup the wait context @@ -277,22 +279,22 @@ // attempt to remove the context so it doesn't get consumed. - if(__atomic_compare_exchange_n( &this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { + if(__atomic_compare_exchange_n( &this.ptr, &expected, future_ARMED, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { // we still have the original context, then no one else saw it return false; } - // expected == 0p: future was never actually setup, just return - if( expected == 0p ) return false; - - // expected == 1p: the future is ready and the context was fully consumed + // expected == ARMED: future was never actually setup, just return + if( expected == future_ARMED ) return false; + + // expected == FULFILLED: the future is ready and the context was fully consumed // the server won't use the pointer again // It is safe to delete (which could happen after the return) - if( expected == 1p ) return true; - - // expected == 2p: the future is ready but the context hasn't fully been consumed + if( expected == future_FULFILLED ) return true; + + // expected == PROGRESS: the future is ready but the context hasn't fully been consumed // spin until it is safe to move on - if( expected == 2p ) { - while( this.ptr != 1p ) Pause(); - /* paranoid */ verify( this.ptr == 1p ); + if( expected == future_PROGRESS ) { + while( this.ptr != future_FULFILLED ) Pause(); + /* paranoid */ verify( this.ptr == future_FULFILLED ); return true; } @@ -305,21 +307,21 @@ // Mark the future as abandoned, meaning it will be deleted by the server bool abandon( future_t & this ) { - /* paranoid */ verify( this.ptr != 3p ); + /* paranoid */ verify( this.ptr != future_ABANDONED ); // Mark the future as abandonned - struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST); + struct oneshot * got = __atomic_exchange_n( &this.ptr, future_ABANDONED, __ATOMIC_SEQ_CST); // If the future isn't already fulfilled, let the server delete it - if( got == 0p ) return false; - - // got == 2p: the future is ready but the context hasn't fully been consumed + if( got == future_ARMED ) return false; + + // got == PROGRESS: the future is ready but the context hasn't fully been consumed // spin until it is safe to move on - if( got == 2p ) { - while( this.ptr != 1p ) Pause(); - got = 1p; + if( got == future_PROGRESS ) { + while( this.ptr != future_FULFILLED ) Pause(); + got = future_FULFILLED; } // The future is completed delete it now - /* paranoid */ verify( this.ptr != 1p ); + /* paranoid */ verify( this.ptr != future_FULFILLED ); free( &this ); return true; @@ -336,19 +338,19 @@ #pragma GCC diagnostic ignored "-Wfree-nonheap-object" #endif - if( expected == 3p ) { free( &this ); return 0p; } + if( expected == future_ABANDONED ) { free( &this ); return 0p; } #if defined(__GNUC__) && __GNUC__ >= 7 #pragma GCC diagnostic pop #endif - /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen - /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case. + /* paranoid */ verify( expected != future_FULFILLED ); // Future is already fulfilled, should not happen + /* paranoid */ verify( expected != future_PROGRESS ); // Future is bein fulfilled by someone else, this is even less supported then the previous case. // If there is a wait context, we need to consume it and mark it as consumed after // If there is no context then we can skip the in progress phase - struct oneshot * want = expected == 0p ? 1p : 2p; + struct oneshot * want = expected == future_ARMED ? future_FULFILLED : future_PROGRESS; if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { - if( expected == 0p ) { return 0p; } + if( expected == future_ARMED ) { return 0p; } thread$ * ret = post( *expected, do_unpark ); - __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST); + __atomic_store_n( &this.ptr, future_FULFILLED, __ATOMIC_SEQ_CST); return ret; } @@ -366,5 +368,5 @@ // Wait for the future to tru - while( this.ptr == 2p ) Pause(); + while( this.ptr == future_PROGRESS ) Pause(); // Make sure the state makes sense // Should be fulfilled, could be in progress but it's out of date if so @@ -372,5 +374,5 @@ // and the oneshot should not be needed any more __attribute__((unused)) struct oneshot * was = this.ptr; - /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was ); + /* paranoid */ verifyf( was == future_FULFILLED, "Expected this.ptr to be 1p, was %p\n", was ); // Mark the future as fulfilled, to be consistent Index: libcfa/src/concurrency/monitor.hfa =================================================================== --- libcfa/src/concurrency/monitor.hfa (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ libcfa/src/concurrency/monitor.hfa (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -60,4 +60,5 @@ void ^?{}( monitor_dtor_guard_t & this ); +/* static inline forall( T & | sized(T) | { void ^?{}( T & mutex ); } ) void delete( T * th ) { @@ -65,4 +66,5 @@ free( th ); } +*/ static inline forall( T & | sized(T) | { void ^?{}( T & mutex ); } ) Index: libcfa/src/iostream.cfa =================================================================== --- libcfa/src/iostream.cfa (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ libcfa/src/iostream.cfa (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Aug 25 18:05:49 2022 -// Update Count : 1354 +// Last Modified On : Sat Aug 27 15:04:15 2022 +// Update Count : 1358 // @@ -765,5 +765,5 @@ fmtuc.flags.pc = f.flags.pc; fmtuc.flags.nobsdp = f.flags.nobsdp; - for ( unsigned int i = 0; f.val[i] != '\0'; i += 1 ) { + for ( i; 0 ~ @ : @; f.val[i] != '\0' ) { fmtuc.val = f.val[i]; // os | fmtuc | nonl; @@ -931,5 +931,5 @@ if ( fmt( is, "%39[0-9]%*[0-9]", s ) == 1 ) { // take first 39 characters, ignore remaining ullli = 0; - for ( unsigned int i = 0; s[i] != '\0'; i += 1 ) { + for ( i; 0 ~ @ : @; s[i] != '\0' ) { ullli = ullli * 10 + s[i] - '0'; } // for Index: src/AST/Create.cpp =================================================================== --- src/AST/Create.cpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) +++ src/AST/Create.cpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -0,0 +1,63 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Create.cpp -- Helpers to create pieces of the AST. +// +// Author : Andrew Beach +// Created On : Tue Sep 20 13:28:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Tue Sep 20 14:55:00 2022 +// Update Count : 0 +// + +#include "AST/Create.hpp" + +#include "AST/Attribute.hpp" +#include "AST/Copy.hpp" +#include "AST/Decl.hpp" + +namespace ast { + +namespace { + + template + std::vector> vectorCopy( + std::vector> const & nodes ) { + return map_range>>( nodes, + []( ptr const & node ){ + return deepCopy( node ); + } + ); + } + +} // namespace + +StructDecl * asForward( StructDecl const * decl ) { + if ( !decl->body ) { + return nullptr; + } + StructDecl * fwd = new StructDecl( decl->location, + decl->name, + decl->kind, + vectorCopy( decl->attributes ), + decl->linkage ); + fwd->params = vectorCopy( decl->params ); + return fwd; +} + +UnionDecl * asForward( UnionDecl const * decl ) { + if ( !decl->body ) { + return nullptr; + } + UnionDecl * fwd = new UnionDecl( decl->location, + decl->name, + vectorCopy( decl->attributes ), + decl->linkage ); + fwd->params = vectorCopy( decl->params ); + return fwd; +} + +} Index: src/AST/Create.hpp =================================================================== --- src/AST/Create.hpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) +++ src/AST/Create.hpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -0,0 +1,26 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Create.hpp -- Helpers to create pieces of the AST. +// +// Author : Andrew Beach +// Created On : Tue Sep 20 13:25:00 2022 +// Last Modified By : Andrew Beach +// Last Modified On : Tue Sep 20 14:38:00 2022 +// Update Count : 0 +// + +#include "AST/Fwd.hpp" + +namespace ast { + +/// Create a forward declaration of the existing declaration. +/// If the argument is already a forward declaration, return nullptr instead. +/// More efficient than the deepCopy and clear pattern. +StructDecl * asForward( StructDecl const * ); +UnionDecl * asForward( UnionDecl const * ); + +} Index: src/AST/Print.cpp =================================================================== --- src/AST/Print.cpp (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/AST/Print.cpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -90,5 +90,5 @@ static constexpr auto Qualifiers = make_array( - "const", "restrict", "volatile", "lvalue", "mutex", "_Atomic" + "const", "restrict", "volatile", "mutex", "_Atomic" ); }; @@ -1635,4 +1635,4 @@ constexpr array Printer::Names::FuncSpecifiers; constexpr array Printer::Names::StorageClasses; -constexpr array Printer::Names::Qualifiers; +constexpr array Printer::Names::Qualifiers; } Index: src/AST/Type.hpp =================================================================== --- src/AST/Type.hpp (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/AST/Type.hpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -412,5 +412,4 @@ std::string typeString() const { return std::string("_") + std::to_string(formal_usage) + "_" + std::to_string(expr_id) + "_" + base->name; } bool operator==(const TypeEnvKey & other) const { return base == other.base && formal_usage == other.formal_usage && expr_id == other.expr_id; } - }; Index: src/AST/TypeEnvironment.hpp =================================================================== --- src/AST/TypeEnvironment.hpp (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/AST/TypeEnvironment.hpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -56,4 +56,10 @@ struct AssertCompare { bool operator()( const VariableExpr * d1, const VariableExpr * d2 ) const { + auto kind1 = ast::SymbolTable::getSpecialFunctionKind(d1->var->name); + auto kind2 = ast::SymbolTable::getSpecialFunctionKind(d2->var->name); + // heuristics optimization: force special functions to go last + if (kind1 > kind2) return true; + else if (kind1 < kind2) return false; + int cmp = d1->var->name.compare( d2->var->name ); return cmp < 0 || ( cmp == 0 && d1->result < d2->result ); Index: src/AST/module.mk =================================================================== --- src/AST/module.mk (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/AST/module.mk (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -24,4 +24,6 @@ AST/Copy.cpp \ AST/Copy.hpp \ + AST/Create.cpp \ + AST/Create.hpp \ AST/CVQualifiers.hpp \ AST/Decl.cpp \ Index: src/CodeGen/CodeGenerator.cc =================================================================== --- src/CodeGen/CodeGenerator.cc (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/CodeGen/CodeGenerator.cc (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -494,4 +494,10 @@ assert( false ); } // switch + } else if( varExpr->get_var()->get_linkage() == LinkageSpec::BuiltinCFA && varExpr->get_var()->get_name() == "intptr" ) { + // THIS is a hack to make it a constant until a proper constexpr solution is created + output << "((void*)"; + std::list< Expression* >::iterator arg = applicationExpr->get_args().begin(); + (*arg++)->accept( *visitor ); + output << ")"; } else { varExpr->accept( *visitor ); Index: src/Concurrency/Waitfor.cc =================================================================== --- src/Concurrency/Waitfor.cc (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/Concurrency/Waitfor.cc (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -402,5 +402,5 @@ clause.target.function = nullptr; - clause.target.arguments.empty(); + clause.target.arguments.clear(); clause.condition = nullptr; } Index: src/GenPoly/InstantiateGenericNew.cpp =================================================================== --- src/GenPoly/InstantiateGenericNew.cpp (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/GenPoly/InstantiateGenericNew.cpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -22,4 +22,5 @@ #include "AST/Copy.hpp" // for deepCopy +#include "AST/Create.hpp" // for asForward #include "AST/Pass.hpp" // for Pass, WithGuard, WithShortCi... #include "AST/TranslationUnit.hpp" // for TranslationUnit @@ -255,16 +256,4 @@ void stripInstParams( ast::BaseInstType * inst ) { inst->params.clear(); -} - -// TODO: I think this should become a generic helper. -template -Aggr * asForward( Aggr const * decl ) { - if ( !decl->body ) { - return nullptr; - } - Aggr * mut = ast::deepCopy( decl ); - mut->body = false; - mut->members.clear(); - return mut; } @@ -553,5 +542,5 @@ // Forward declare before recursion. (TODO: Only when needed, #199.) insert( inst, typeSubs, newDecl ); - if ( AggrDecl const * forwardDecl = asForward( newDecl ) ) { + if ( AggrDecl const * forwardDecl = ast::asForward( newDecl ) ) { declsToAddBefore.push_back( forwardDecl ); } Index: src/GenPoly/Lvalue2.cc =================================================================== --- src/GenPoly/Lvalue2.cc (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/GenPoly/Lvalue2.cc (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -23,4 +23,3 @@ } - } Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/ResolvExpr/CommonType.cc (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -28,4 +28,5 @@ #include "Unify.h" // for unifyExact, WidenMode #include "typeops.h" // for isFtype +#include "Tuples/Tuples.h" // #define DEBUG @@ -675,4 +676,6 @@ ast::TypeEnvironment & tenv; const ast::OpenVarSet & open; + ast::AssertionSet & need; + ast::AssertionSet & have; public: static size_t traceId; @@ -681,6 +684,7 @@ CommonType_new( const ast::Type * t2, WidenMode w, const ast::SymbolTable & st, - ast::TypeEnvironment & env, const ast::OpenVarSet & o ) - : type2( t2 ), widen( w ), symtab( st ), tenv( env ), open( o ), result() {} + ast::TypeEnvironment & env, const ast::OpenVarSet & o, + ast::AssertionSet & need, ast::AssertionSet & have ) + : type2( t2 ), widen( w ), symtab( st ), tenv( env ), open( o ), need (need), have (have) ,result() {} void previsit( const ast::Node * ) { visit_children = false; } @@ -753,5 +757,4 @@ bool tryResolveWithTypedEnum( const ast::Type * type1 ) { if (auto enumInst = dynamic_cast (type2) ) { - ast::AssertionSet have, need; // unused ast::OpenVarSet newOpen{ open }; if (enumInst->base->base @@ -792,5 +795,4 @@ reset_qualifiers( t2 ); - ast::AssertionSet have, need; ast::OpenVarSet newOpen{ open }; if ( unifyExact( t1, t2, tenv, have, need, newOpen, noWiden(), symtab ) ) { @@ -803,4 +805,139 @@ } } + else if ( isFtype (t1) && isFtype (t2) ) { + auto f1 = t1.as(); + if (!f1) return; + auto f2 = t2.strict_as(); + + assertf(f1->returns.size() <= 1, "Function return should not be a list"); + assertf(f2->returns.size() <= 1, "Function return should not be a list"); + + if ( + ( f1->params.size() != f2->params.size() || f1->returns.size() != f2->returns.size() ) + && ! f1->isTtype() + && ! f2->isTtype() + ) return; + + auto params1 = flattenList( f1->params, tenv ); + auto params2 = flattenList( f2->params, tenv ); + + auto crnt1 = params1.begin(); + auto crnt2 = params2.begin(); + auto end1 = params1.end(); + auto end2 = params2.end(); + + while (crnt1 != end1 && crnt2 != end2 ) { + const ast::Type * arg1 = *crnt1; + const ast::Type * arg2 = *crnt2; + + bool isTuple1 = Tuples::isTtype( t1 ); + bool isTuple2 = Tuples::isTtype( t2 ); + + // assumes here that ttype *must* be last parameter + if ( isTuple1 && ! isTuple2 ) { + // combine remainder of list2, then unify + if (unifyExact( + arg1, tupleFromTypes( crnt2, end2 ), tenv, need, have, open, + noWiden(), symtab )) { + break; + + } + else return; + } else if ( ! isTuple1 && isTuple2 ) { + // combine remainder of list1, then unify + if (unifyExact( + tupleFromTypes( crnt1, end1 ), arg2, tenv, need, have, open, + noWiden(), symtab )) { + break; + + } + else return; + } + + // allow qualifiers of pointer and reference base to become more specific + if (auto ref1 = dynamic_cast (arg1)) { + if (auto ref2 = dynamic_cast (arg2)) { + ast::ptr base1 = ref1->base; + ast::ptr base2 = ref2->base; + + // xxx - assume LHS is always the target type + + if ( ! ((widen.second && ref2->qualifiers.is_mutex) + || (ref1->qualifiers.is_mutex == ref2->qualifiers.is_mutex ))) return; + + if ( (widen.second && base1->qualifiers <= base2->qualifiers ) || (base2->qualifiers == base1->qualifiers) ) { + + reset_qualifiers(base1); + reset_qualifiers(base2); + + if ( ! unifyExact( + base1, base2, tenv, need, have, open, noWiden(), symtab ) + ) return; + } + } + else return; + } + else if (auto ptr1 = dynamic_cast (arg1)) { + if (auto ptr2 = dynamic_cast (arg2)) { + ast::ptr base1 = ptr1->base; + ast::ptr base2 = ptr2->base; + + // xxx - assume LHS is always the target type + // a function accepting const can always be called by non-const arg + + if ( (widen.second && base1->qualifiers <= base2->qualifiers ) || (base2->qualifiers == base1->qualifiers) ) { + + reset_qualifiers(base1); + reset_qualifiers(base2); + + if ( ! unifyExact( + base1, base2, tenv, need, have, open, noWiden(), symtab ) + ) return; + } + } + else return; + + } + else if (! unifyExact( + arg1, arg2, tenv, need, have, open, noWiden(), symtab )) return; + + ++crnt1; ++crnt2; + } + if ( crnt1 != end1 ) { + // try unifying empty tuple with ttype + const ast::Type * t1 = *crnt1; + if (! Tuples::isTtype( t1 ) ) return; + if (! unifyExact( + t1, tupleFromTypes( crnt2, end2 ), tenv, need, have, open, + noWiden(), symtab )) return; + } else if ( crnt2 != end2 ) { + // try unifying empty tuple with ttype + const ast::Type * t2 = *crnt2; + if (! Tuples::isTtype( t2 ) ) return; + if (! unifyExact( + tupleFromTypes( crnt1, end1 ), t2, tenv, need, have, open, + noWiden(), symtab )) return; + } + if ((f1->returns.size() == 0 && f2->returns.size() == 0) + || (f1->returns.size() == 1 && f2->returns.size() == 1 && unifyExact(f1->returns[0], f2->returns[0], tenv, need, have, open, noWiden(), symtab))) { + result = pointer; + + for (auto & assn : f1->assertions) { + auto i = need.find(assn); + if (i != need.end()) i->second.isUsed = true; + auto j = have.find(assn); + if (j != have.end()) j->second.isUsed = true; + } + + for (auto & assn : f2->assertions) { + auto i = need.find(assn); + if (i != need.end()) i->second.isUsed = true; + auto j = have.find(assn); + if (j != have.end()) j->second.isUsed = true; + } + + } + } // if ftype + } } else if ( widen.second && dynamic_cast< const ast::ZeroType * >( type2 ) ) { @@ -839,5 +976,4 @@ reset_qualifiers( t2 ); - ast::AssertionSet have, need; ast::OpenVarSet newOpen{ open }; if ( unifyExact( t1, t2, tenv, have, need, newOpen, noWiden(), symtab ) ) { @@ -857,5 +993,5 @@ // xxx - does unifying a ref with typed enumInst makes sense? if (!dynamic_cast(type2)) - result = commonType( type2, ref, widen, symtab, tenv, open ); + result = commonType( type2, ref, tenv, need, have, open, widen, symtab ); } } @@ -877,5 +1013,5 @@ // xxx - is this already handled by unify? if (!dynamic_cast(type2)) - result = commonType( type2, enumInst, widen, symtab, tenv, open ); + result = commonType( type2, enumInst, tenv, need, have, open, widen, symtab); } @@ -895,5 +1031,4 @@ reset_qualifiers( t2 ); - ast::AssertionSet have, need; ast::OpenVarSet newOpen{ open }; if ( unifyExact( t1, t2, tenv, have, need, newOpen, noWiden(), symtab ) ) { @@ -999,6 +1134,6 @@ ast::ptr< ast::Type > commonType( const ast::ptr< ast::Type > & type1, const ast::ptr< ast::Type > & type2, - WidenMode widen, const ast::SymbolTable & symtab, ast::TypeEnvironment & env, - const ast::OpenVarSet & open + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab ) { unsigned depth1 = type1->referenceDepth(); @@ -1036,5 +1171,5 @@ } // otherwise both are reference types of the same depth and this is handled by the visitor - ast::Pass visitor{ type2, widen, symtab, env, open }; + ast::Pass visitor{ type2, widen, symtab, env, open, need, have }; type1->accept( visitor ); ast::ptr< ast::Type > result = visitor.core.result; @@ -1047,5 +1182,4 @@ if ( type->base ) { ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; - ast::AssertionSet have, need; ast::OpenVarSet newOpen{ open }; Index: src/ResolvExpr/ConversionCost.cc =================================================================== --- src/ResolvExpr/ConversionCost.cc (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/ResolvExpr/ConversionCost.cc (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -22,8 +22,10 @@ #include "ResolvExpr/Cost.h" // for Cost #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment +#include "ResolvExpr/Unify.h" #include "SymTab/Indexer.h" // for Indexer #include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl #include "SynTree/Type.h" // for Type, BasicType, TypeInstType #include "typeops.h" // for typesCompatibleIgnoreQualifiers + namespace ResolvExpr { @@ -657,5 +659,25 @@ cost = Cost::safe; } - } else { + } + /* + else if ( const ast::FunctionType * dstFunc = dstAsPtr->base.as()) { + if (const ast::FunctionType * srcFunc = pointerType->base.as()) { + if (dstFunc->params.empty() && dstFunc->isVarArgs ) { + cost = Cost::unsafe; // assign any function to variadic fptr + } + } + else { + ast::AssertionSet need, have; // unused + ast::OpenVarSet open; + env.extractOpenVars(open); + ast::TypeEnvironment tenv = env; + if ( unify(dstAsPtr->base, pointerType->base, tenv, need, have, open, symtab) ) { + cost = Cost::safe; + } + } + // else infinity + } + */ + else { int assignResult = ptrsAssignable( pointerType->base, dstAsPtr->base, env ); if ( 0 < assignResult && tq1 <= tq2 ) { Index: src/ResolvExpr/SatisfyAssertions.cpp =================================================================== --- src/ResolvExpr/SatisfyAssertions.cpp (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/ResolvExpr/SatisfyAssertions.cpp (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -36,4 +36,5 @@ #include "AST/SymbolTable.hpp" #include "AST/TypeEnvironment.hpp" +#include "FindOpenVars.h" #include "Common/FilterCombos.h" #include "Common/Indenter.h" @@ -161,5 +162,5 @@ /// Satisfy a single assertion - bool satisfyAssertion( ast::AssertionList::value_type & assn, SatState & sat ) { + bool satisfyAssertion( ast::AssertionList::value_type & assn, SatState & sat, bool allowConversion = false, bool skipUnbound = false) { // skip unused assertions if ( ! assn.second.isUsed ) return true; @@ -180,4 +181,5 @@ if (thisArgType.as()) otypeKey = Mangle::Encoding::pointer; else if (!isUnboundType(thisArgType)) otypeKey = Mangle::mangle(thisArgType, Mangle::Type | Mangle::NoGenericParams); + else if (skipUnbound) return false; candidates = sat.symtab.specialLookupId(kind, otypeKey); @@ -205,15 +207,35 @@ // only keep candidates which unify - if ( unify( toType, adjType, newEnv, newNeed, have, newOpen, sat.symtab ) ) { - // set up binding slot for recursive assertions - ast::UniqueId crntResnSlot = 0; - if ( ! newNeed.empty() ) { - crntResnSlot = ++globalResnSlot; - for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; } - } - - matches.emplace_back( - cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ), - std::move( newOpen ), crntResnSlot ); + + ast::OpenVarSet closed; + findOpenVars( toType, newOpen, closed, newNeed, have, FirstClosed ); + findOpenVars( adjType, newOpen, closed, newNeed, have, FirstOpen ); + if ( allowConversion ) { + if ( auto c = commonType( toType, adjType, newEnv, newNeed, have, newOpen, WidenMode {true, true}, sat.symtab ) ) { + // set up binding slot for recursive assertions + ast::UniqueId crntResnSlot = 0; + if ( ! newNeed.empty() ) { + crntResnSlot = ++globalResnSlot; + for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; } + } + + matches.emplace_back( + cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ), + std::move( newOpen ), crntResnSlot ); + } + } + else { + if ( unifyExact( toType, adjType, newEnv, newNeed, have, newOpen, WidenMode {true, true}, sat.symtab ) ) { + // set up binding slot for recursive assertions + ast::UniqueId crntResnSlot = 0; + if ( ! newNeed.empty() ) { + crntResnSlot = ++globalResnSlot; + for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; } + } + + matches.emplace_back( + cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ), + std::move( newOpen ), crntResnSlot ); + } } } @@ -413,4 +435,5 @@ // for each current mutually-compatible set of assertions for ( SatState & sat : sats ) { + bool allowConversion = false; // stop this branch if a better option is already found auto it = thresholds.find( pruneKey( *sat.cand ) ); @@ -418,4 +441,5 @@ // should a limit be imposed? worst case here is O(n^2) but very unlikely to happen. + for (unsigned resetCount = 0; ; ++resetCount) { ast::AssertionList next; @@ -424,5 +448,5 @@ for ( auto & assn : sat.need ) { // fail early if any assertion is not satisfiable - if ( ! satisfyAssertion( assn, sat ) ) { + if ( ! satisfyAssertion( assn, sat, allowConversion, !next.empty() ) ) { next.emplace_back(assn); // goto nextSat; @@ -433,14 +457,22 @@ // fail if nothing resolves else if (next.size() == sat.need.size()) { - Indenter tabs{ 3 }; - std::ostringstream ss; - ss << tabs << "Unsatisfiable alternative:\n"; - print( ss, *sat.cand, ++tabs ); - ss << (tabs-1) << "Could not satisfy assertion:\n"; - ast::print( ss, next[0].first, tabs ); - - errors.emplace_back( ss.str() ); - goto nextSat; - } + if (allowConversion) { + Indenter tabs{ 3 }; + std::ostringstream ss; + ss << tabs << "Unsatisfiable alternative:\n"; + print( ss, *sat.cand, ++tabs ); + ss << (tabs-1) << "Could not satisfy assertion:\n"; + ast::print( ss, next[0].first, tabs ); + + errors.emplace_back( ss.str() ); + goto nextSat; + } + + else { + allowConversion = true; + continue; + } + } + allowConversion = false; sat.need = std::move(next); } Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/ResolvExpr/Unify.cc (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -707,4 +707,50 @@ } + namespace { + /// Replaces ttype variables with their bound types. + /// If this isn't done when satifying ttype assertions, then argument lists can have + /// different size and structure when they should be compatible. + struct TtypeExpander_new : public ast::WithShortCircuiting, public ast::PureVisitor { + ast::TypeEnvironment & tenv; + + TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {} + + const ast::Type * postvisit( const ast::TypeInstType * typeInst ) { + if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) { + // expand ttype parameter into its actual type + if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) { + return clz->bound; + } + } + return typeInst; + } + }; + } + + std::vector< ast::ptr< ast::Type > > flattenList( + const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env + ) { + std::vector< ast::ptr< ast::Type > > dst; + dst.reserve( src.size() ); + for ( const auto & d : src ) { + ast::Pass expander{ env }; + // TtypeExpander pass is impure (may mutate nodes in place) + // need to make nodes shared to prevent accidental mutation + ast::ptr dc = d->accept(expander); + auto types = flatten( dc ); + for ( ast::ptr< ast::Type > & t : types ) { + // outermost const, volatile, _Atomic qualifiers in parameters should not play + // a role in the unification of function types, since they do not determine + // whether a function is callable. + // NOTE: **must** consider at least mutex qualifier, since functions can be + // overloaded on outermost mutex and a mutex function has different + // requirements than a non-mutex function + remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); + dst.emplace_back( t ); + } + } + return dst; + } + class Unify_new final : public ast::WithShortCircuiting { const ast::Type * type2; @@ -778,63 +824,4 @@ private: - /// Replaces ttype variables with their bound types. - /// If this isn't done when satifying ttype assertions, then argument lists can have - /// different size and structure when they should be compatible. - struct TtypeExpander_new : public ast::WithShortCircuiting, public ast::PureVisitor { - ast::TypeEnvironment & tenv; - - TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {} - - const ast::Type * postvisit( const ast::TypeInstType * typeInst ) { - if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) { - // expand ttype parameter into its actual type - if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) { - return clz->bound; - } - } - return typeInst; - } - }; - - /// returns flattened version of `src` - static std::vector< ast::ptr< ast::Type > > flattenList( - const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env - ) { - std::vector< ast::ptr< ast::Type > > dst; - dst.reserve( src.size() ); - for ( const auto & d : src ) { - ast::Pass expander{ env }; - // TtypeExpander pass is impure (may mutate nodes in place) - // need to make nodes shared to prevent accidental mutation - ast::ptr dc = d->accept(expander); - auto types = flatten( dc ); - for ( ast::ptr< ast::Type > & t : types ) { - // outermost const, volatile, _Atomic qualifiers in parameters should not play - // a role in the unification of function types, since they do not determine - // whether a function is callable. - // NOTE: **must** consider at least mutex qualifier, since functions can be - // overloaded on outermost mutex and a mutex function has different - // requirements than a non-mutex function - remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); - dst.emplace_back( t ); - } - } - return dst; - } - - /// Creates a tuple type based on a list of DeclWithType - template< typename Iter > - static const ast::Type * tupleFromTypes( Iter crnt, Iter end ) { - std::vector< ast::ptr< ast::Type > > types; - while ( crnt != end ) { - // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure - // that this results in a flat tuple - flatten( *crnt, types ); - - ++crnt; - } - - return new ast::TupleType{ std::move(types) }; - } template< typename Iter > @@ -1048,16 +1035,5 @@ private: /// Creates a tuple type based on a list of Type - static const ast::Type * tupleFromTypes( - const std::vector< ast::ptr< ast::Type > > & tys - ) { - std::vector< ast::ptr< ast::Type > > out; - for ( const ast::Type * ty : tys ) { - // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure - // that this results in a flat tuple - flatten( ty, out ); - } - - return new ast::TupleType{ std::move(out) }; - } + static bool unifyList( @@ -1231,5 +1207,5 @@ } - } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) { + } else if ( common = commonType( t1, t2, env, need, have, open, widen, symtab )) { // no exact unification, but common type auto c = shallowCopy(common.get()); Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ src/ResolvExpr/typeops.h (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -138,6 +138,12 @@ Type * commonType( Type * type1, Type * type2, bool widenFirst, bool widenSecond, const SymTab::Indexer & indexer, TypeEnvironment & env, const OpenVarSet & openVars ); ast::ptr< ast::Type > commonType( - const ast::ptr< ast::Type > & type1, const ast::ptr< ast::Type > & type2, WidenMode widen, - const ast::SymbolTable & symtab, ast::TypeEnvironment & env, const ast::OpenVarSet & open ); + const ast::ptr< ast::Type > & type1, const ast::ptr< ast::Type > & type2, + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab + ); + // in Unify.cc + std::vector< ast::ptr< ast::Type > > flattenList( + const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env + ); // in PolyCost.cc @@ -181,5 +187,5 @@ /// flatten tuple type into existing list of types - static inline void flatten( + inline void flatten( const ast::Type * type, std::vector< ast::ptr< ast::Type > > & out ) { @@ -194,5 +200,5 @@ /// flatten tuple type into list of types - static inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) { + inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) { std::vector< ast::ptr< ast::Type > > out; out.reserve( type->size() ); @@ -200,4 +206,27 @@ return out; } + + template< typename Iter > + const ast::Type * tupleFromTypes( Iter crnt, Iter end ) { + std::vector< ast::ptr< ast::Type > > types; + while ( crnt != end ) { + // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure + // that this results in a flat tuple + flatten( *crnt, types ); + + ++crnt; + } + + + return new ast::TupleType{ std::move(types) }; + } + + inline const ast::Type * tupleFromTypes( + const std::vector< ast::ptr< ast::Type > > & tys + ) { + return tupleFromTypes( tys.begin(), tys.end() ); + } + + // in TypeEnvironment.cc Index: tests/concurrent/.expect/ctor-check.txt =================================================================== --- tests/concurrent/.expect/ctor-check.txt (revision 4520b77e192c372763501afd950a0f1452141b3b) +++ tests/concurrent/.expect/ctor-check.txt (revision a065f1ffe843ea0a3ceecdf36a1210abe07a2441) @@ -2,5 +2,5 @@ ?{}: function ... with parameters - this: lvalue reference to instance of struct Empty with body + this: mutex reference to instance of struct Empty with body ... returning nothing with body