pointer/api.go

// Copyright 2013 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 pointer

import (
	"fmt"
	"go/token"
	"io"

	"code.google.com/p/go.tools/go/types/typemap"
	"code.google.com/p/go.tools/ssa"
)

type Config struct {
	// -------- Scope of the analysis --------

	// Clients must provide the analysis with at least one package defining a main() function.
	Mains []*ssa.Package // set of 'main' packages to analyze
	root  *ssa.Function  // synthetic analysis root

	// -------- Optional callbacks invoked by the analysis --------

	// Call is invoked for each discovered call-graph edge.  The
	// call-graph is a multigraph over CallGraphNodes with edges
	// labelled by the CallSite that gives rise to the edge.
	// (The caller node is available as site.Caller())
	//
	// Clients that wish to construct a call graph may provide
	// CallGraph.AddEdge here.
	//
	// The callgraph may be context-sensitive, i.e. it may
	// distinguish separate calls to the same function depending
	// on the context.
	//
	Call func(site CallSite, callee CallGraphNode)

	// CallSite is invoked for each call-site encountered in the
	// program.
	//
	// The callgraph may be context-sensitive, i.e. it may
	// distinguish separate calls to the same function depending
	// on the context.
	//
	CallSite func(site CallSite)

	// Warn is invoked for each warning encountered by the analysis,
	// e.g. unknown external function, unsound use of unsafe.Pointer.
	// pos may be zero if the position is not known.
	Warn func(pos token.Pos, format string, args ...interface{})

	// Print is invoked during the analysis for each discovered
	// call to the built-in print(x).
	//
	// Pointer p may be saved until the analysis is complete, at
	// which point its methods provide access to the analysis
	// (The result of callings its methods within the Print
	// callback is undefined.)  p is nil if x is non-pointerlike.
	//
	// TODO(adonovan): this was a stop-gap measure for identifing
	// arbitrary expressions of interest in the tests.  Now that
	// ssa.ValueForExpr exists, we should use that instead.
	//
	Print func(site *ssa.CallCommon, p Pointer)

	// The client populates QueryValues[v] for each ssa.Value v
	// of interest.
	//
	// The boolean (Indirect) indicates whether to compute the
	// points-to set for v (false) or *v (true): the latter is
	// typically wanted for Values corresponding to source-level
	// lvalues, e.g. an *ssa.Global.
	//
	// The pointer analysis will populate the corresponding
	// QueryResults value when it creates the pointer variable
	// for v or *v.  Upon completion the client can inspect the
	// map for the results.
	//
	// If a Value belongs to a function that the analysis treats
	// context-sensitively, the corresponding QueryResults slice
	// may have multiple Pointers, one per distinct context.  Use
	// PointsToCombined to merge them.
	//
	// TODO(adonovan): refactor the API: separate all results of
	// Analyze() into a dedicated Result struct.
	//
	QueryValues  map[ssa.Value]Indirect
	QueryResults map[ssa.Value][]Pointer

	// -------- Other configuration options --------

	// If Log is non-nil, a log messages are written to it.
	// Logging is extremely verbose.
	Log io.Writer
}

type Indirect bool // map[ssa.Value]Indirect is not a set

func (c *Config) prog() *ssa.Program {
	for _, main := range c.Mains {
		return main.Prog
	}
	panic("empty scope")
}

// A Pointer is an equivalence class of pointerlike values.
//
// TODO(adonovan): add a method
//    Context() CallGraphNode
// for pointers corresponding to local variables,
//
type Pointer interface {
	// PointsTo returns the points-to set of this pointer.
	PointsTo() PointsToSet

	// MayAlias reports whether the receiver pointer may alias
	// the argument pointer.
	MayAlias(Pointer) bool

	String() string
}

// A PointsToSet is a set of labels (locations or allocations).
//
type PointsToSet interface {
	// PointsTo returns the set of labels that this points-to set
	// contains.
	Labels() []*Label

	// Intersects reports whether this points-to set and the
	// argument points-to set contain common members.
	Intersects(PointsToSet) bool

	// If this PointsToSet came from a Pointer of interface kind,
	// ConcreteTypes returns the set of concrete types the
	// interface may contain.
	//
	// The result is a mapping whose keys are the concrete types
	// to which this interface may point.  For each pointer-like
	// key type, the corresponding map value is a set of pointer
	// abstractions of that concrete type, represented as a
	// []Pointer slice.  Use PointsToCombined to merge them.
	ConcreteTypes() *typemap.M
}

// Union returns the set containing all the elements of each set in sets.
func Union(sets ...PointsToSet) PointsToSet {
	var union ptset
	for _, set := range sets {
		set := set.(ptset)
		union.a = set.a
		union.pts.addAll(set.pts)
	}
	return union
}

// PointsToCombined returns the combined points-to set of all the
// specified pointers.
func PointsToCombined(ptrs []Pointer) PointsToSet {
	var ptsets []PointsToSet
	for _, ptr := range ptrs {
		ptsets = append(ptsets, ptr.PointsTo())
	}
	return Union(ptsets...)
}

// ---- PointsToSet public interface

type ptset struct {
	a   *analysis // may be nil if pts is nil
	pts nodeset
}

func (s ptset) Labels() []*Label {
	var labels []*Label
	for l := range s.pts {
		// Scan back to the previous object start.
		for i := l; i >= 0; i-- {
			n := s.a.nodes[i]
			if n.flags&ntObject != 0 {
				// TODO(adonovan): do bounds-check against n.size.
				var v ssa.Value
				if n.flags&ntFunction != 0 {
					v = n.data.(*cgnode).fn
				} else {
					v = n.data.(ssa.Value)
					// TODO(adonovan): what if v is nil?
				}
				labels = append(labels, &Label{
					Value:      v,
					subelement: s.a.nodes[l].subelement,
				})
				break
			}
		}
	}
	return labels
}

func (s ptset) ConcreteTypes() *typemap.M {
	var tmap typemap.M // default hasher // TODO(adonovan): opt: memoize per analysis
	for ifaceObjId := range s.pts {
		if s.a.nodes[ifaceObjId].flags&ntInterface == 0 {
			// ConcreteTypes called on non-interface PT set.
			continue // shouldn't happen
		}
		v, tconc := s.a.interfaceValue(ifaceObjId)
		prev, _ := tmap.At(tconc).([]Pointer)
		tmap.Set(tconc, append(prev, ptr{s.a, v}))
	}
	return &tmap
}

func (x ptset) Intersects(y_ PointsToSet) bool {
	y := y_.(ptset)
	for l := range x.pts {
		if _, ok := y.pts[l]; ok {
			return true
		}
	}
	return false
}

// ---- Pointer public interface

// ptr adapts a node to the Pointer interface.
type ptr struct {
	a *analysis
	n nodeid // non-zero
}

func (p ptr) String() string {
	return fmt.Sprintf("n%d", p.n)
}

func (p ptr) PointsTo() PointsToSet {
	return ptset{p.a, p.a.nodes[p.n].pts}
}

func (p ptr) MayAlias(q Pointer) bool {
	return p.PointsTo().Intersects(q.PointsTo())
}

func (p ptr) ConcreteTypes() *typemap.M {
	return p.PointsTo().ConcreteTypes()
}