A Flow Extension to Coroutine Types for Deadlock Detection in Go Thanks: This study is supported by the Science and Technology Development Fund, Macau SAR, with File No. 0015/2023/RIA1. Qiqi Jason Gu Lixue Liu Wei Ke Abstract Coroutines, as an abstract programming construct, are a generalization of functions that can suspend execution part-way for later resumption. Coroutine Types are behavioral types to model interactions of coroutines with a single receiving operation followed by a single yielding operation. Coroutine Types have been applied to model-driven engineering, smart contracts, and test case generation. We contribute a Flow extension to Coroutine Types, so that coroutines with more than one receiving and yielding operation can be modeled. We accordingly revise the reduction rules of Coroutine Types. To show the usefulness of the Flow extension, we contribute a type system that maps expressions of the Go programming language to Coroutine Types. If the reduction result is 𝟎 \mathbf{0} , the two channel operations are paired properly and the program has no deadlocks. We choose Go because it is a popular programming language for distributed systems, but a frequent kind of bugs in Go is deadlocks due to the wrong use of concurrency features. We concentrate on the most commonly used semantics in Go: unbuffered channels with the keywords go and defer . Our Flow extension and the type system recognize 17 patterns of channels and goroutine interactions, including mismatched receivers and senders, nested goroutines, etc. We also integrate the Z3 SMT solver to take account of conditional execution and type inheritance. Other static or dynamic deadlock detectors crashed or gave wrong predictions in some patterns. Therefore, our type-based deadlock analyzer not only fills the gap in the landscape of value-based detection, but also complements existing detectors. I Introduction Coroutines, as an abstract programming construct, are a generalization of functions that can suspend execution part-way for later resumption. To study the collective behavior of a set of coroutines in the field of process calculi, Gu and Ke proposed Coroutine Types [ 15 ] which are behavioral type expressions for coroutines. Their Coroutine Types have been applied to model-driven engineering [ 16 ] , smart contracts, and test case generation [ 26 ] . Coroutine Types require a coroutine to fully receive data before yielding anything. This however becomes a restriction when we apply Coroutine Types to many real-world programming languages that support concurrency. This paper thus puts forward a Flow extension to Coroutine Types to overcome this restriction. Our Flow extension allows yielding and receiving operations to happen in any order for an unlimited number of times. The extension also includes constraint types \tau/\rho , akin to the Boolean conditional \textit{if }\rho\textit{ then }\tau in Communicating Sequential Processes [ 39 ] . Our constraint types enhance the expressiveness of Coroutine Types so that we are able to take account of type inheritance in data of channels, and any other conditional activation of coroutines. The reduction rules are adjusted for the new semantics. To check the applicability and solve real-world problems, we have created a Flow type system to map expressions in the Go language (abbreviated as Golang) onto Coroutine Types with Flow. Thus we are able to check, from the viewpoint of behavioral types, the deadlock freedom of a Go program. We choose Go because it is a popular choice in building scalable web applications, blockchains, and other distributed systems. In Go, coroutines are branded as goroutines. Golang has a wide range of concurrency features [ 30 ] , but our type system only types some of them. Listing 1 shows Golang features that can be mapped onto Coroutine Types with Flow, including the keyword go and defer , and unbuffered channels. The keyword go takes a function call or a call to an anonymous subroutine, and starts a goroutine. A statement prefixed by the keyword defer defers the execution of a function until the surrounding function returns. Channels in Go are statically typed conduits, meaning the conduit sends and receives a single type of data. Meanwhile, one goroutine has access to more than one channel for the input and output purpose. Channels are created by the syntax make(chan t , n ) , where t is a type, and n specifies the buffer capacity of the channel. If n is 0 or omitted, the channel becomes unbuffered, meaning a send operation will be awaiting until a receive operation is performed on this channel, and vice versa. The send and the receive operation on a channel use the same operator <- . On one hand, when it’s used as a binary operator as in x <- y , x is a channel and y is a value to send. On the other hand, when it’s used as a unary operator as in <- y , y becomes a channel and the whole expression evaluates to the received value. In Listing 1 , Line 4 creates a channel of int; Line 6 starts a deferred goroutine that reads the channel; Line 9 sends a datum to the channel. Listing 1: A piece of Go code containing the channel creation, sending, receiving, and the keywords go and defer ⬇ 1 import ”fmt” 2 3 func main () { 4 channel := make ( chan int ) 5 6 defer func () { fmt . Print (<- channel ) }() 7 go func () { 8 if true { 9 channel <- 20 10 } 11 }() 12 } Coroutine Types with Flow are designed to analyze 17 kinds of deadlock situations with respect to channel and goroutine interactions in Golang. We used our algorithm to analyze 4 real-world program files and got correct deadlock situations. Additionally we ran two state-of-the-art static deadlock analyzers and one dynamic analyzer, and they could not correctly predict deadlock situations in some of the 21 cases. In summary, the main contributions of this paper are: 1. We propose a Flow extension to the previously published Coroutine Types in order to model flexible receiving and yielding behaviors of coroutines. 2. We propose a set of typing rules that map critical concurrency features in the Go language onto type expressions in the Flow extension. 3. Our Flow extension complements traditional deadlock analyzers which failed to analyze 11 deadlock patterns and 3 real-world cases. The rest of the paper is organized as follows. First, we review related work in Section II . Then building on previous research, Section III proposes a Flow extension to Coroutine Types and revises the reduction rules. Next Section IV presents a Flow type system that maps Golang expressions to Coroutine Types for detecting deadlocks. We also compare our algorithm with other tools in this section. Section V briefs about the limitations of Coroutine Types with Flow and the corresponding deadlock detection algorithm. Lastly we conclude in Section VI . II Related Work Predicting a deadlock is essentially solving a halting problem, which is proven undecidable [ 34 ] . Yet, we can very well reason limited forms of deadlocks [ 32 ] . Concurrency bugs have symptoms of either blocking or non-blocking execution [ 46 ] . Blocking refers to no progress of all processes, known as a deadlock. If only a few processes do not make progress, it is a partial lock [ 37 ] . In this section we first talk about abstract interpretation, which is a method to extract certain properties from a program and analyze the properties in an abstract way. The property in interest can be deadlock-freedom, termination, whether a neural network is robust with respect to perturbations [ 40 ] , so on and so forth. If we are interested in the type information, abstract interpretation is specialized to a type system, where a type is not necessarily a standard type, such as integers, booleans, etc., but also behavioral types or session types [ 19 ] which model of an abstract behavior of a program. A type system is used in the static time or dynamic time depending on whether the programming language is static or dynamic. Besides type systems, static or dynamic analysis have other ways to determine concurrency properties of a program. II-A Abstract Interpretation Abstract interpretation provides a general framework to approximate program behaviors and derive finite models amenable to automated reasoning. It reduces the possible states of a program [ 34 , p21] . One simple example is the analysis of the sign of integer arithmetic, whether the result is positive ( + ), negative ( - ), or unknown ( \pm ). Veileborg et al. [ 43 ] abstract the channels in a Go program into status, and use the point-to relation to make a graph of how channels are used. [ 21 ] translates C ++ programs into the modeling language Promela and then finds concurrency issues. Communicating sequential processes (CSP) [ 31 ] and Calculus of Communicating Systems (CCS) [ 39 ] are members of process calculi. CSP supports conditions, and uses an exclamation mark ( ! ) for sending data, and an question mark ( ? ) for receiving data. Given Golang source code, Almeida and Antonio [ 2 ] generate an intermediate representation dubbed MiGo [ 22 ] . MiGo then is translated into a representation in CCS. They ignored Go’s select statements. Next, their deadlock detection and resolution algorithms are performed. Coelho [ 8 ] modeled select statements as external choices in CCS and developed a Go module, named GoDDaR. II-B Type Systems If types are abstracted from a program, a type system is being studied. Hosoya et al. [ 18 ] created Regular Expression Types to check the validness of an XML file to a grammar. Typed Lua [ 29 ] endeavors to introduce optional typing to the Lua language including its coroutines. While its type system allows for type narrowing, it does not assign a specific type to the coroutine construct as a whole. Furthermore, the return types of coroutines cannot depend on input types within the Typed Lua system. CorDuroy [ 3 ] is a statically-typed language for coroutines based on the simply-typed lambda calculus. Godel [ 23 ] uses behavioral types to model the SSA form of a Go program, and studies the liveness and channel safety properties. The evaluation was done on a small set of 22 programs. Godel’s method has one limitation in that it does not support programs that spawn new threads in for-loops. Barclay et al. [ 4 ] invented a coroutine-based dynamically-typed language for prototyping code. This language has no functions but coroutines, and all coroutines are callable objects. II-C Static Analysis Static tools analyze source code without the need of a compiler or execution of the code. Static analysis tends to be conservative, in order to avoid the state-explosion problem [ 24 ] . GCatch [ 28 ] instructs Microsoft Z3 [ 9 ] , a SMT solver to solve an equation that equals to a deadlock state. If a solution is found, the solution is the conditions that lead to the deadlock. Staticcheck [ 17 ] and Vet [ 13 ] analyze Go source code statically. With a limited number of check rules, they spot concurrency bugs in rare cases. Zhang et al. invented a closed-source tool GoDetector [ 45 ] , which can detect not only channel-related bugs but also WaitGroup-related bugs. JaDA is a deadlock analyzer for the Java bytecode [ 12 ] . It was evaluated on 247 Java files in 25 benchmarks. II-D Dynamic Analysis Dynamic approaches collect information during execution of a program. This approach is effective in analyzing one execution of an object program, but cannot study behaviors which the program has not exhibited. Dynamic analysis minimizes false positives and negatives, but this method incurs execution overhead. Memory leaks are often detected at the execution time [ 14 ] . Liang et al. [ 25 ] intercepts API calls from a program to classify whether the program is malicious. Golang provides the package runtime/trace [ 36 ] . Developers place trace.Start(traceFile) and trace.Stop() around the code they want to diagnose. A traceFile is written to disk, and the command line go tool trace traceFile [ 35 ] visualizes the file. This toolchain is not insightful enough to locate concurrency bugs, so GoAT [ 41 ] , a GOPATH-based project, patches the toolchain so as to record more events, and also devises another static component to visualize and inspect the trace output. Akin to GoAT, BinGo [ 46 ] is a hybrid solution involving runtime and static analysis. Rather than modifying the go execution binary, its runtime component performs code inject into the address space. Unfortunately its source code is not available. Similarly, Concuerror [ 7 ] combines dynamic analysis with static analysis to find bugs in Erlang. The most naive deadlock detection resides in the Go runtime itself. If all goroutines are paused, its built-in deadlock detector will print the stack trace, then kill the program [ 33 ] . GoLeak by Uber [ 42 ] declares deadlocks if the main function, which is the root goroutine, fails to finish within a pre-defined time period. III A Flow Extension to Coroutine Types The syntax of our behavioral types is defined in Fig. 1 . Italic names—sequence types, product types, and concrete types—are from the base Coroutine Types [ 16 ] , not part of the Flow extension. Concrete types are simple types with no internal structure, such as Int or StringBuilder. A sequence \Theta is flat and associative, that is {\left\langle{\left\langle\tau_{1},\tau_{2}\right\rangle},\tau_{3}\right\rangle}={\left\langle\tau_{1},{\left\langle\tau_{2},\tau_{3}\right\rangle}\right\rangle} , where both sides can be simplified to {\left\langle\tau_{1},\tau_{2},\tau_{3}\right\rangle} . A sequence of a particular type \tau is written as \Theta_{\tau} . To give the length n of a sequence, \Theta_{\tau} is written as \tau^{n} . \displaystyle\omega::= \displaystyle\mbox{Flow item} \displaystyle\Omega \displaystyle\mid \displaystyle{\displaystyle!}\tau \displaystyle\mbox{yielded item} \displaystyle\mid \displaystyle{\displaystyle?}\tau \displaystyle\mbox{received item} \displaystyle\tau::= \displaystyle\mbox{types} \displaystyle T \displaystyle\mid \displaystyle\tau/\penalty\rho \displaystyle\mbox{constrained types} \displaystyle\Xi \displaystyle\mid \displaystyle(\tau\mid\tau) \displaystyle\mbox{union types} \displaystyle\Sigma \displaystyle\mid \displaystyle\llbracket\omega;\omega;\cdots\rrbracket \displaystyle\mbox{coroutine def types} \displaystyle D \displaystyle\mid \displaystyle\left[\omega;\omega;\cdots\right] \displaystyle\mbox{coroutine ins types} \displaystyle I \displaystyle\mid \displaystyle{\displaystyle\left\langle\tau,\tau\right\rangle} \displaystyle\mbox{{sequence types}} \displaystyle\Theta \displaystyle\mid \displaystyle{\displaystyle\left(\tau,\tau\right)} \displaystyle\mbox{{product types}} \displaystyle P \displaystyle\mid \displaystyle\textrm{Int}\mid\textrm{String}\mid\cdots \displaystyle\mbox{{concrete types}} \displaystyle K Fig. 1: Abstract syntax for our coroutine types with Flow The principal types in the Flow extension are coroutine definition types D and coroutine instance types I . A coroutine definition is akin to a function definition. A coroutine instance is one execution of a function. Depending on the arguments, coroutine instances may exhibit diverse input and output behaviors. \operatorname{Start}:D\to I is a type-level function that starts a coroutine definition and turns it into a coroutine instance. Both definition and instance are made of Flow items \Theta_{\Omega} , telling how the coroutine yields and receives data. Yielding and receiving actions are a protocol to control when to execute a coroutine. Self-canceling is permitted, for example \left[{!}A;{?}A\right] . Disjoint union types may exist in a coroutine definition but not in a coroutine instance because at runtime we always know the exact chosen type. A type can take an optional Boolean predicate \rho . The instructions in \rho are specific to applications. It could model type inheritance, generic functions, and conditional executions. For instance, l:\llbracket{?}{\left\langle x,\textrm{Book}\right\rangle};{!}{\left\langle x,\textrm{Book},\textrm{Reserve}\right\rangle}\rrbracket/\penalty x\mathop{<:}\textrm{User} reads: “ l is a coroutine definition which receives x and Book, and yields x , Book, and Reserve, where x is a subclass of User.” The kinds of predicates depend on the application and is not part of the Flow extension. Equation ( 1 ) is reduction rules of constrained types. The construct \mathbf{0} denotes no behavior. \displaystyle\tau/\penalty\textrm{false} \displaystyle\Rightarrow\mathbf{0} (1) \displaystyle\tau/\penalty\textrm{true} \displaystyle\Rightarrow\tau \displaystyle\tau/\penalty\rho_{1}/\penalty\rho_{2} \displaystyle\Rightarrow\tau/\penalty\rho_{1}\wedge\rho_{2} \displaystyle\tau/\penalty\rho\wedge(x\mapsto v) \displaystyle\Rightarrow\tau[x\mapsto v]/\penalty\rho If the type in a Flow item is a sequence, the Flow direction indicator \psi (yielding ! or receiving ? ) should be distributed to each sequence item, i.e., {\psi}{{\left\langle\tau_{1},\tau_{2},\cdots\right\rangle}}\Rightarrow{\left\langle{\psi}{\tau_{1}},{\psi}{\tau_{2}},\cdots\right\rangle} . Variables can take place of concrete types, integers, or arguments of a function. Free variables are considered constants. Gu and Ke’s Coroutine Types [ 15 ] defines minimal elements for coroutine reduction, containing solely concrete types, sequences, coroutines with fixed receiving and yielding order. Coroutine definitions and coroutine instances are not distinguished there. They later added product types to control the precedence of reduction [ 16 ] , but here we switch to leverage \operatorname{Start} to activate coroutines, which is to some extent a precedence. We still keep product types as tuples because they can group elements. III-A Reduction Rules The reduce function is defined as \bm{\circ}{}:\Theta_{I}\to I . The arguments of \bm{\circ}{} have to be a sequence of coroutine instances or Start functions that return instances. The return type is a coroutine instance I and we do not further reduce it to K . In this way we know the data are computed rather than from a static field. The reduce function \bm{\circ} consists of rules running in a demand-driven strategy [ 38 ] . During the evaluation of \bm{\circ} , a Flow item with empty type is regarded as useless, and should be removed from a coroutine. \psi being the channel operation ! or ? , reduction Rule CR1 lists the reduction regarding removing these identity elements. e_{1}\Rightarrow e_{2} means an expression e_{1} evaluates or reduces to another expression or value e_{2} . \begin{split}\bm{\circ}{\left\langle S_{1},\left[\omega_{1};\psi(\mathbf{0});\omega_{2}\right],S_{2}\right\rangle}&\Rightarrow\bm{\circ}{\left\langle S_{1},\left[\omega_{1};\omega_{2}\right],S_{2}\right\rangle}\\ \bm{\circ}{\left\langle S_{1},\left[\psi(\mathbf{0})\right],S_{2}\right\rangle}&\Rightarrow\bm{\circ}{\left\langle S_{1},S_{2}\right\rangle}\\ \bm{\circ}{\left\langle S_{1},\operatorname{Start}(\llbracket\omega_{1};\psi(\mathbf{0});\omega_{2}\rrbracket),S_{2}\right\rangle}&\Rightarrow\bm{\circ}{\left\langle S_{1},\operatorname{Start}(\llbracket\omega_{1};\omega_{2}\rrbracket),S_{2}\right\rangle}\\ \bm{\circ}{\left\langle S_{1},\operatorname{Start}(\llbracket\psi(\mathbf{0})\rrbracket),S_{2}\right\rangle}&\Rightarrow\bm{\circ}{\left\langle S_{1},S_{2}\right\rangle}\\ \end{split} (CR1) \operatorname{Start}(d) takes a coroutine definition d and turns it into a coroutine instance i . Recall a coroutine definition may contain disjoint union types. In Listing 2 , if we ignore the defer statement, we have s:\llbracket{!}(\textrm{Int}/v<10\mid\textrm{Bool}/\neg(v<10))\rrbracket for the definition. For instantiation, go s(20) translates \operatorname{Start}(s) to \left[{!}\textrm{Bool}\right] because the branch \textrm{Bool}/\neg(v<10) is chosen, while go s(2) translates \operatorname{Start}(s) to \left[{!}\textrm{Int}\right] . Section IV will discuss the mapping from the if statement to (\textrm{Int}/v<10\mid\textrm{Bool}/\neg(v<10)) , as well as the processing of Go’s defer statements. Listing 2: Function s yields disparate types based on a condition, which can be solved by the Z3 solver ⬇ var ch1 chan int = make ( chan int ) var ch2 chan bool = make ( chan bool ) func s ( v int ) { defer func (){ ch2 <- true }() if v < 10 { ch1 <- v } else { ch2 <- true } } func main () { go s (2) fmt . Println (<- ch1 , <- ch2 ) } Other reduction rules need to access or manipulate auxiliary data. Thus the symbol \vdash is employed. Left to \vdash is the context comprised of Pending Type \tau:T and External Yields E:\Theta_{K\mid P} . Pending type is what a coroutine yielded and not yet received by a coroutine. External Yields is a sequence of pending types that are not receivable by any coroutine. Right to \vdash is an expression which can be a type or a call to the reduce function. Same as the previous work [ 16 ] , we use a wildcard (\cdot) to indicate an unreferenced item in rules. For example (\cdot,E) means at this point the pending type, which may or may not be \mathbf{0} , is not used in other parts of the rule. The “main body” of coroutine instance and coroutine definition is a sequence of Flow items. We use the head function and the tail function, defined in the base Coroutine Types [ 16 ] to get the first element and rest elements of an instance, shown in Fig. 2 . We never take head or tail out of a definition. \displaystyle{\mathbf{h}}(\left[\omega_{1};\omega_{2};\cdots\right]) \displaystyle=\omega_{1} \displaystyle{\mathbf{t}}(\left[\omega_{1};\omega_{2};\cdots\right]) \displaystyle=\left[\omega_{2};\cdots\right] Fig. 2: Definition of head {\mathbf{h}} and tail {\mathbf{t}} of a coroutine instance The following reduction rules ( CR2 ) to ( CR7 ) are very similar to the ones in the base Coroutine Types, but we have to revise them to recognize the new Flow items \Omega . III-A 1 Yielding Listing 3: the function \mathbf{first} and \mathbf{none} in Haskell ⬇ first :: [ a ] -> ( a -> Bool ) -> ( Maybe a , [ a ], [ a ]) first s p = case break p s of ( before , []) -> ( Nothing , before , []) ( before , x : after ) -> ( Just x , before , after ) none :: [ a ] -> ( a -> Bool ) -> Bool none s p = case first s p of ( Nothing , s , []) -> True _ -> False We use the function \mathbf{first} defined in the base Coroutine Types to find the first coroutine instance i in a list S that matches a condition p , written as (i,S_{1},S_{2})=\mathbf{first}(S,\lambda i.p(i)) , where along with the coroutine, \mathbf{first} also returns S_{1} all elements before i and S_{2} all elements after i . Listing 3 is its formal definition in Haskell. If \mathbf{first} can’t make out a matching element, then i=S_{2}=\mathbf{0} . This special case is abbreviated as \mathbf{none} . ( CR2 ) is triggered when there is no pending type and the function \mathbf{first} is able to find the a coroutine whose head direction is yielding. Then, we transfer the yielded type into the context. In case a coroutine has exhausted its action statements, {\mathbf{t}}(s) would be \mathbf{0} and it’s subject to deletion by ( CR1 ). \begin{split}(\mathbf{0},\cdot)\vdash\bm{\circ}(S)\Rightarrow(\tau,\cdot)\vdash\bm{\circ}({\left\langle S_{1},{{\mathbf{t}}(i)},S_{2}\right\rangle})\\ \textrm{provided}\;\\ (i,S_{1},S_{2})=\mathbf{first}(S,\lambda i\ldotp{\mathbf{h}}(i)={!}\tau)\end{split} (CR2) If the yielded type is a coroutine instance or an invocation to the type-level function \operatorname{Start} , ( CR3 ) evaluates \operatorname{Start} and inserts the yielded instance at the end of the list. This mimics the breadth-first search and mitigates infinite loops if a coroutine continuously starts itself. \begin{split}(\mathbf{0},\cdot)\vdash\bm{\circ}(S)\Rightarrow(\mathbf{0},\cdot)\vdash\bm{\circ}({\left\langle S_{1},{{\mathbf{t}}(i)},S_{2},\left[u;v\right]\right\rangle})\\ \textrm{provided}\quad\\ (i,S_{1},S_{2})=\mathbf{first}(S,\lambda i\ldotp{\mathbf{h}}(s)={!}\left[u;v\right])\end{split} (CR3) ( CR4 ) describes a deadlocked state when no coroutine has a yielding head and the pending type is \mathbf{0} , suggesting nothing to receive. In such case, the reduction terminates with result E followed by all the remaining coroutines from the list. The distributive law applies in this rule, and coroutines as a first-class citizen are allowed within a coroutine. \begin{split}(\mathbf{0},E)\vdash\bm{\circ}(S)\Rightarrow(\mathbf{0},\mathbf{0})\vdash\left[{!}E;{!}S\right]\\ \textrm{provided}\;\mathbf{none}(S,\lambda i\ldotp{\mathbf{h}}(i)={!}\tau)\end{split} (CR4) III-A 2 Resuming When the pending type \tau is not \mathbf{0} , the resume operation is triggered. ( CR5 ) picks up the first coroutine i that can receive \tau , and resumes it. \mathbf{match}:T\times T\to\Theta is defined in the base Coroutine Types, a commutative function to match two types (potentially carrying constraints) and returns a set of conditions B under which the two types are equal. As we know, a coroutine type can contain variables and therefore the conditions returned by \mathbf{match} could bind the variables. For example, \mathbf{match}(\textrm{Int}^{5},\textrm{Int}^{n})=\{n\mapsto 5\} . If in no way can two types match, \bot is returned, and \bot\wedge B=\bot . Our improvement to the \mathbf{match} function is to back it up by a SMT solver, Microsoft Z3. The details about constraint handling are given in Section III-B . \begin{split}(\tau,\cdot)\vdash\bm{\circ}(S)\Rightarrow(\mathbf{0},\cdot)\vdash\bm{\circ}{\left\langle S_{1},{\mathbf{t}}(i)/\penalty B,S_{2}\right\rangle}\quad\textrm{provided}\;\\ (i,S_{1},S_{2})=\mathbf{first}(S,\lambda i\ldotp{\mathbf{h}}(i)={?}s\wedge\mathbf{match}(\tau,s)=B)\end{split} (CR5) \begin{split}(\tau,E)\vdash\bm{\circ}(S)\Rightarrow(\mathbf{0},{\left\langle E,\tau\right\rangle})\vdash\bm{\circ}(S)\quad\textrm{provided}\;\\ \mathbf{none}(S,\lambda i\ldotp{\mathbf{h}}(i)={?}u\wedge\mathbf{match}(\tau,u)\neq\bot)\end{split} (CR6) \begin{split}(\mathbf{0},\cdot)\vdash\bm{\circ}(S)\Rightarrow(\mathbf{0},\cdot)\vdash\bm{\circ}({\left\langle S_{1},{{\mathbf{t}}(i)}/\penalty B,S_{2}\right\rangle}\smallsetminus i^{\prime})\quad\textrm{provided}\;\\ (i,S_{1},S_{2})=\mathbf{first}(S,\lambda i\ldotp{\mathbf{h}}(i)={?}t\wedge t\in I)\\ \textrm{and}\;(i^{\prime},\cdot,\cdot)=\mathbf{first}(S\smallsetminus i,\lambda i^{\prime}\ldotp\mathbf{match}(i^{\prime},t)=B)\end{split} (CR7) ( CR6 ) stipulates that if none of the coroutines in S can process the pending type \tau , then \tau gets appended to the external yields E . This reduction rule often paves the way for ( CR4 ) for termination because ( CR4 ) expects an empty pending type. Coroutine cancelation is not a key part for Golang because goroutine must be written with a semaphore or alike to allow early termination. Nevertheless, ( CR7 ) outlines how a coroutine receives other coroutines for the complete first-class support of coroutine in the base Coroutine Types. Line 2 in ( CR7 ) finds the first coroutine whose head {\mathbf{h}}(s) is a receiving pattern of a coroutine instance, then Line 3 matches this pattern with another coroutine i^{\prime} , returning conditions B . At the end, we apply the condition to {\mathbf{t}}(i) , and also remove the received coroutine from the result by using the set minus sign. Overall this rule shows the powerfulness of the first-class coroutine support: a component of a coroutine can remove another coroutine as a whole. The base Coroutine Types [ 16 ] has a rule that loops the external yields. This rule is detrimental to channel-based deadlock detection. Consequently our Flow extension disables this rule. Consider Listing 4 , where main() first yields String, then yields Int, but work() requires Int followed by String. The order mismatch makes for infinite blocking. If we enable the rule “loop external” in [ 16 ] , the analyzer will report termination, which is incorrect. Listing 4 was enlisted into the supported deadlock patterns in Section IV-A . Listing 4: Out-of-order.go in our dataset will run into a deadlock ⬇ func work ( cInt chan int , cStr chan string ) { fmt . Println (<- cInt ) fmt . Println (<- cStr ) } func main () { cInt := make ( chan int ) cStr := make ( chan string ) go work ( cInt , cStr ) cStr <- ”hello” cInt <- 1 ... } Overall, the whole reduction algorithm is deterministic because it checks rules in order and there is no random choice. The step to collect coroutine definitions surely terminates because there is a limited number of functions in a program. Nevertheless, the subsequent reduction process may not terminate if a Go function recursively calls itself. This is one form of labeled infinite coroutines that always restore itself after execution. ( CR3 ) adopts the breath-first manner and mitigates infinite loops. Moreover, the whole reduction process aborts once the main coroutine is used up. As the last measure, our implementation caps the reduction steps at 500. Our previous paper [ 15 ] hasdetailed analysis of these properties, including determinism and termination. III-B Constrained Type Handling Whenever \mathbf{match} is called, it is possible that a constrained type needs to be checked. This kind of checking is done by Microsoft Z3 [ 9 ] in the Flow extension. Z3 recognizes many logical operations, such as negation, conjunction and disjunction. Equality checks on symbols and comparisons (less-than and greater-than) on numbers are also fundamental. Of these binary relations, on one side is typically a variable, and on the other side is a constant or another variable. In our case, symbols are our concrete types in Fig. 1 . \displaystyle c(\left[\omega_{1};\omega_{2};\cdots;\omega_{n}\right]) \displaystyle=\textstyle\bigcup c(\omega_{i}) \displaystyle c(\llbracket\omega_{1};\omega_{2};\cdots;\omega_{n}\rrbracket) \displaystyle=\textstyle\bigcup c(\omega_{i}) \displaystyle c(\psi\tau) \displaystyle=c(\tau) \displaystyle c(\tau/\penalty\rho) \displaystyle=c(\tau)\cup c(\rho) \displaystyle c(\tau_{1}\mid\tau_{2}) \displaystyle=c(\tau_{1})\cup c(\tau_{2}) \displaystyle c({\left\langle\tau_{1},\tau_{2},\cdots,\tau_{n}\right\rangle}) \displaystyle=\textstyle\bigcup c(\tau_{i}) \displaystyle c({\left(\tau_{1},\tau_{2},\cdots,\tau_{n}\right)}) \displaystyle=\textstyle\bigcup c(\tau_{i}) \displaystyle c(K) \displaystyle=\left\{K\right\} Fig. 3: Function c finds all concrete types from a type As mentioned, variables in our coroutine types are allowed to present any concrete type. The set containing all concrete types in the universe is named the Concrete sort in Z3. We denote the Concrete sort as \mathbf{K} . Let c:T\to\Theta_{K} be a function that collects all concrete types from a type. Fig. 3 shows the definition of c . The collect function runs before reduction rules introduced earlier because we need to collect all kinds of types in the program. The assembled Concrete sort \mathbf{K} is fed into the \mathbf{match} function highlighted by the shaded background on the right of Fig. 4 . Fig. 4: Collect Concrete Types runs only once. The shaded box on the right is the flowchart of the \mathbf{match} function \mathbf{match} (and \mathbf{none} ) involves in building a boolean expression, solving the expression, and returning the condition under which the expression is true. In the Flow extension, the types of variables are inferred. If the opposite side of a variable is an integer, the variable is of type Int. If opposite a variable is a concrete type, the variable is of type Concrete and given the set of collected concrete types as its domain. If both sides are variables, the two should have the same type. A variable equal to a complex type or \mathbf{0} is not permitted, resulting to \bot . \mathbf{match} processes not only equality checks, but also arithmetic comparisons or custom functions that may appear in \rho in constrained types. Examples include the less-than symbol in \textrm{Int}/\penalty v<10 , and the subtype constraint in \big[{{?}{\left\langle x,\textrm{Book}\right\rangle}};\linebreak{{!}{\left\langle x,\textrm{Book},\textrm{Reserve}\right\rangle}}\big]/\penalty x\mathop{<:}\textrm{User} Although Z3 comes with assorted Boolean and numerical expressions, users of the Flow extension, such as the Flow type system introduced in Section IV , can inject custom functions, such as a subtype relation, for application-specific purposes. Custom functions shall return a Boolean value. They are usually second-order logic with universal qualifiers and a material conditional. In a Go program, type inheritance is usually achieved by anonymous fields. We define a function head inherit and a function body in SMT-LIB syntax [ 5 ] . Listing 5 establishes a function body, accepting x of Concrete and y of Concrete . r is the inverse of known subtyping relations, such as Faculty is a subclass of User, and Student is a subclass of User. Then => is an implication (material conditional) that if x and y are not in known subtyping relationships, (inherit x y) is false. We could have kept a persistent Z3 context and run Load Custom Functions once as we do for Collect Concrete Types, but Z3 may have some memory leaking issue so we have to free up the Z3 context regularly. Listing 5: Function body of the inherit custom function ⬇ ( forall (( x Concrete ) ( y Concrete )) ( let (( r ( not ( or ( and (= x Faculty ) (= y User )) ( and (= x Student ) (= y User )))))) (=> r (= ( inherit x y ) false )))) When \mathbf{match} is called with a pending type \tau_{1}/\rho_{1} and a receiving coroutine \left[{?}\tau_{2};\cdots\right]/\penalty\rho_{2} , we build an Boolean expression (\tau_{1}=\tau_{2})\wedge\rho_{1}\wedge\rho_{2} , and ask Z3 to solve it. Equation ( 1 ) is used as well. If Z3 answers “sat” on the Boolean expression, we extract condition B from the interpretation (the step Extract Condition) and use it in ( CR5 ) or ( CR7 ). Z3 is a satisfiability solver and only finds one instance of variables that make the expression true. Suppose during ( CR5 ), the pending type is {\left(x^{1},y^{j}\right)}/\penalty j<5 , and \mathbf{match} is going to process the head of \left[{?}{\left(x^{i},y^{j}\right)};{?}{\left(y^{j},x^{i}\right)}\right]/\penalty j>0 , and i,j are variables; then we build an expression {\left(x^{1},y^{j}\right)}={\left(x^{i},y^{j}\right)}\wedge j<5\wedge j>0 . Z3 will return B=\left\{i\mapsto 1,j\mapsto 1\right\} . While j=1 satisfies the expression, we shouldn’t replace j by this exact number because the value of j is not uniquely determined yet. Instead, we should update the coroutine to \left[{-}{{\left(y^{j},x^{1}\right)}}\right]/\penalty 0