src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

flow.go (1556B)

      1 // Copyright 2026 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 // Package flow implements a monotone flow analysis framework.
      6 package dense
      7 
      8 import (
      9 	"cmp"
     10 	"slices"
     11 
     12 	"honnef.co/go/tools/internal/xtools-internal/graph"
     13 )
     14 
     15 const debug = false
     16 
     17 // Analysis is the result of a monotone analysis. Fact is the type of elements
     18 // in the analysis semilattice, and represents the outcome of the analysis at
     19 // every node and edge.
     20 type Analysis[Fact any, NodeID comparable] struct {
     21 	nodeMap *graph.Index[NodeID]
     22 	ins     []Fact           // By NodeID
     23 	edges   []edgeFact[Fact] // Sorted by (from, to)
     24 }
     25 
     26 // In returns the analysis fact on entry to nid. This is the merge of the facts
     27 // on all incoming edges.
     28 func (a *Analysis[Fact, NodeID]) In(nid NodeID) Fact {
     29 	return a.ins[a.nodeMap.Index(nid)]
     30 }
     31 
     32 // Edge returns the analysis fact propagated on edge from ==> to.
     33 func (a *Analysis[Fact, NodeID]) Edge(from, to NodeID) Fact {
     34 	i, found := slices.BinarySearchFunc(a.edges, a.edge(from, to), edgeFact[Fact].compare)
     35 	if !found {
     36 		panic("no such edge")
     37 	}
     38 	return a.edges[i].fact
     39 }
     40 
     41 func (a *Analysis[Fact, NodeID]) edge(from, to NodeID) edge {
     42 	fromNum, toNum := a.nodeMap.Index(from), a.nodeMap.Index(to)
     43 	return edge{fromNum, toNum}
     44 }
     45 
     46 type edge struct {
     47 	from, to int
     48 }
     49 
     50 func (e edge) compare(f edge) int {
     51 	if v := cmp.Compare(e.from, f.from); v != 0 {
     52 		return v
     53 	}
     54 	return cmp.Compare(e.to, f.to)
     55 }
     56 
     57 type edgeFact[Fact any] struct {
     58 	edge
     59 	fact Fact
     60 }