summaryrefslogtreecommitdiffhomepage
path: root/vendor/golang.org/x/tools/go/ssa/task.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/golang.org/x/tools/go/ssa/task.go')
-rw-r--r--vendor/golang.org/x/tools/go/ssa/task.go103
1 files changed, 0 insertions, 103 deletions
diff --git a/vendor/golang.org/x/tools/go/ssa/task.go b/vendor/golang.org/x/tools/go/ssa/task.go
deleted file mode 100644
index 5024985..0000000
--- a/vendor/golang.org/x/tools/go/ssa/task.go
+++ /dev/null
@@ -1,103 +0,0 @@
-// Copyright 2024 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package ssa
-
-import (
- "sync/atomic"
-)
-
-// Each task has two states: it is initially "active",
-// and transitions to "done".
-//
-// tasks form a directed graph. An edge from x to y (with y in x.edges)
-// indicates that the task x waits on the task y to be done.
-// Cycles are permitted.
-//
-// Calling x.wait() blocks the calling goroutine until task x,
-// and all the tasks transitively reachable from x are done.
-//
-// The nil *task is always considered done.
-type task struct {
- done chan unit // close when the task is done.
- edges map[*task]unit // set of predecessors of this task.
- transitive atomic.Bool // true once it is known all predecessors are done.
-}
-
-func (x *task) isTransitivelyDone() bool { return x == nil || x.transitive.Load() }
-
-// addEdge creates an edge from x to y, indicating that
-// x.wait() will not return before y is done.
-// All calls to x.addEdge(...) should happen before x.markDone().
-func (x *task) addEdge(y *task) {
- if x == y || y.isTransitivelyDone() {
- return // no work remaining
- }
-
- // heuristic done check
- select {
- case <-x.done:
- panic("cannot add an edge to a done task")
- default:
- }
-
- if x.edges == nil {
- x.edges = make(map[*task]unit)
- }
- x.edges[y] = unit{}
-}
-
-// markDone changes the task's state to markDone.
-func (x *task) markDone() {
- if x != nil {
- close(x.done)
- }
-}
-
-// wait blocks until x and all the tasks it can reach through edges are done.
-func (x *task) wait() {
- if x.isTransitivelyDone() {
- return // already known to be done. Skip allocations.
- }
-
- // Use BFS to wait on u.done to be closed, for all u transitively
- // reachable from x via edges.
- //
- // This work can be repeated by multiple workers doing wait().
- //
- // Note: Tarjan's SCC algorithm is able to mark SCCs as transitively done
- // as soon as the SCC has been visited. This is theoretically faster, but is
- // a more complex algorithm. Until we have evidence, we need the more complex
- // algorithm, the simpler algorithm BFS is implemented.
- //
- // In Go 1.23, ssa/TestStdlib reaches <=3 *tasks per wait() in most schedules
- // On some schedules, there is a cycle building net/http and internal/trace/testtrace
- // due to slices functions.
- work := []*task{x}
- enqueued := map[*task]unit{x: {}}
- for i := 0; i < len(work); i++ {
- u := work[i]
- if u.isTransitivelyDone() { // already transitively done
- work[i] = nil
- continue
- }
- <-u.done // wait for u to be marked done.
-
- for v := range u.edges {
- if _, ok := enqueued[v]; !ok {
- enqueued[v] = unit{}
- work = append(work, v)
- }
- }
- }
-
- // work is transitively closed over dependencies.
- // u in work is done (or transitively done and skipped).
- // u is transitively done.
- for _, u := range work {
- if u != nil {
- x.transitive.Store(true)
- }
- }
-}