<ul dir="auto">
<li>What version of Go are you using (go version)?</li>
</ul>
<p dir="auto">The same problem exists on</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="go version go1.4.2 linux/amd64
go version devel +5ee5528 Thu May 28 12:04:35 2015 +0000 linux/amd64"><pre class="notranslate"><code class="notranslate">go version go1.4.2 linux/amd64
go version devel +5ee5528 Thu May 28 12:04:35 2015 +0000 linux/amd64
</code></pre></div>
<ul dir="auto">
<li>What operating system and processor architecture are you using?</li>
</ul>
<p dir="auto">Linux amd64, ubuntu 14.04</p>
<ul dir="auto">
<li>What did you do?</li>
</ul>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="git clone https://gist.github.com/883d01d0274dda5e32d1.git bug
cd bug
go build"><pre class="notranslate"><code class="notranslate">git clone https://gist.github.com/883d01d0274dda5e32d1.git bug
cd bug
go build
</code></pre></div>
<ul dir="auto">
<li>What did you expect to see?</li>
</ul>
<p dir="auto">No error</p>
<ul dir="auto">
<li>What did you see instead?</li>
</ul>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="./e.go:4: TypeType.New undefined (type *Type has no field or method New)"><pre class="notranslate"><code class="notranslate">./e.go:4: TypeType.New undefined (type *Type has no field or method New)
</code></pre></div>
<p dir="auto">If you look in <a href="https://gist.github.com/ncw/883d01d0274dda5e32d1#file-t-go">t.go</a> you can see that method is defined.</p>
<p dir="auto">If you concatenate <a href="https://gist.github.com/ncw/883d01d0274dda5e32d1#file-e-go">e.go</a> and <code class="notranslate">t.go</code> and compile (remove duplicate package line) then it compiles fine.</p>
<p dir="auto"><a href="https://gist.github.com/ncw/883d01d0274dda5e32d1">Here is the Gist</a></p>
<h2 dir="auto">e.go</h2>
<div class="highlight highlight-source-go notranslate position-relative overflow-auto" dir="auto" data-snippet-clipboard-copy-content="package foo

var (
    Base = TypeType.New()
    // To trigger the problem
    //  * Need Base as argument - it is fine if you substitute with nil
    //  * Need the x, _ = form of call
    Something, _ = NewSomething(Base)
)

func NewSomething(t *Type) (*Type, error) {
    return nil, nil
}"><pre class="notranslate"><span class="pl-k">package</span> foo

<span class="pl-k">var</span> (
    <span class="pl-s1">Base</span> <span class="pl-c1">=</span> <span class="pl-s1">TypeType</span>.<span class="pl-en">New</span>()
    <span class="pl-c">// To trigger the problem</span>
    <span class="pl-c">//  * Need Base as argument - it is fine if you substitute with nil</span>
    <span class="pl-c">//  * Need the x, _ = form of call</span>
    <span class="pl-s1">Something</span>, <span class="pl-s1">_</span> <span class="pl-c1">=</span> <span class="pl-en">NewSomething</span>(<span class="pl-s1">Base</span>)
)

<span class="pl-k">func</span> <span class="pl-en">NewSomething</span>(<span class="pl-s1">t</span> <span class="pl-c1">*</span><span class="pl-smi">Type</span>) (<span class="pl-c1">*</span><span class="pl-smi">Type</span>, <span class="pl-smi">error</span>) {
    <span class="pl-k">return</span> <span class="pl-c1">nil</span>, <span class="pl-c1">nil</span>
}</pre></div>
<h2 dir="auto">t.go</h2>
<div class="highlight highlight-source-go notranslate position-relative overflow-auto" dir="auto" data-snippet-clipboard-copy-content="package foo

type Type struct{}

var TypeType *Type = &amp;Type{}

func (t *Type) New() *Type {
    return &amp;Type{}
}"><pre class="notranslate"><span class="pl-k">package</span> foo

<span class="pl-k">type</span> <span class="pl-smi">Type</span> <span class="pl-k">struct</span>{}

<span class="pl-k">var</span> <span class="pl-s1">TypeType</span> <span class="pl-c1">*</span><span class="pl-smi">Type</span> <span class="pl-c1">=</span> <span class="pl-c1">&amp;</span><span class="pl-smi">Type</span>{}

<span class="pl-k">func</span> (<span class="pl-s1">t</span> <span class="pl-c1">*</span><span class="pl-smi">Type</span>) <span class="pl-en">New</span>() <span class="pl-c1">*</span><span class="pl-smi">Type</span> {
    <span class="pl-k">return</span> <span class="pl-c1">&amp;</span><span class="pl-smi">Type</span>{}
}</pre></div>
<h1 dir="auto">The Proposal</h1>
<p dir="auto">Deadlock's make programs fail. Partial deadlocks (where a subset of the goroutines in a system are deadlocked) are difficult to find and debug. While predicting the occurrences of these deadlocks is not computable, detecting them when they occur is. Adding in a partial deadlock detector would be a powerful tool in debugging our concurrent programs.</p>
<p dir="auto">Like the race detector, a flag-able deadlock detector would use environment variables to log, or exit on detected deadlocks. The deadlock detector would <em>not</em> detect all deadlocks, or potential deadlocks, only a subset of those that are occurring.</p>
<p dir="auto">The goal of this proposal is to see if such a feature is desirable, and present a plausible implementation. If it is desirable a detailed design doc will follow.</p>
<h2 dir="auto">Is this the Halting Problem?</h2>
<p dir="auto">No. If the <a href="https://en.wikipedia.org/wiki/Deadlock#Necessary_conditions" rel="nofollow">necessary conditions are met</a> the program will not continue.</p>
<h1 dir="auto">Proposed Implementation</h1>
<h2 dir="auto">High Level</h2>
<p dir="auto">In short the proposed implementation is to "hook" into the garbage collector, and use it's mark phase to build a <a href="https://en.wikipedia.org/wiki/Wait-for_graph" rel="nofollow">wait-for graph</a>. Then use <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" rel="nofollow">Tarjan's algorithm</a> to find deadlock cycles. That is the strongly connect components with no edges to non deadlocked components.</p>
<h2 dir="auto">More Detailed</h2>
<p dir="auto">As go uses a <em>mark-sweep</em> garbage collector most of the computationally expensive work necessary for dead lock detection is <em>already being done</em>. Here is how the proposed detector would work (in very high level terms):</p>
<ol dir="auto">
<li>At the beginning of the mark phase all goroutines in a wait state are examined, along with the object they are waiting on.</li>
<li>As objects are marked (colored black or gray) from the various roots, if the object is one one of the "waited on" resources, it can be added as an edge in our wait for graph.</li>
<li>Any resource which is not referenced from another root will be added as an edge to a "nothing" node.</li>
<li>At the end of the mark phase (e.g. post stop the world) run Tarjan's (or similar) to determine the strongly connected components.</li>
<li>If we have a strongly connected component with no edges to a non deadlocked component, the involved goroutines are deadlocked.</li>
</ol>
<h2 dir="auto">Notes</h2>
<p dir="auto">I have intentionally glossed over:</p>
<ul dir="auto">
<li>Dealing with timers (interruptible waits) and globally referenced resources</li>
<li>That an object referenced by multiple roots may contain a reference to a waited on object in another root (paths to the waited on object would have to be stored and examined when previously colored nodes are addressed)</li>
<li>Send and receive mechanics on channels<br>
for simplicity's sake.</li>
</ul>