--- /dev/null
+// 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
+
+// This file defines the constraint generation phase.
+
+// TODO(adonovan): move the constraint definitions and the store() etc
+// functions which add them (and are also used by the solver) into a
+// new file, constraints.go.
+
+import (
+ "fmt"
+ "go/token"
+ "go/types"
+
+ "golang.org/x/tools/go/callgraph"
+ "golang.org/x/tools/go/ssa"
+)
+
+var (
+ tEface = types.NewInterfaceType(nil, nil).Complete()
+ tInvalid = types.Typ[types.Invalid]
+ tUnsafePtr = types.Typ[types.UnsafePointer]
+)
+
+// ---------- Node creation ----------
+
+// nextNode returns the index of the next unused node.
+func (a *analysis) nextNode() nodeid {
+ return nodeid(len(a.nodes))
+}
+
+// addNodes creates nodes for all scalar elements in type typ, and
+// returns the id of the first one, or zero if the type was
+// analytically uninteresting.
+//
+// comment explains the origin of the nodes, as a debugging aid.
+//
+func (a *analysis) addNodes(typ types.Type, comment string) nodeid {
+ id := a.nextNode()
+ for _, fi := range a.flatten(typ) {
+ a.addOneNode(fi.typ, comment, fi)
+ }
+ if id == a.nextNode() {
+ return 0 // type contained no pointers
+ }
+ return id
+}
+
+// addOneNode creates a single node with type typ, and returns its id.
+//
+// typ should generally be scalar (except for tagged.T nodes
+// and struct/array identity nodes). Use addNodes for non-scalar types.
+//
+// comment explains the origin of the nodes, as a debugging aid.
+// subelement indicates the subelement, e.g. ".a.b[*].c".
+//
+func (a *analysis) addOneNode(typ types.Type, comment string, subelement *fieldInfo) nodeid {
+ id := a.nextNode()
+ a.nodes = append(a.nodes, &node{typ: typ, subelement: subelement, solve: new(solverState)})
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\tcreate n%d %s for %s%s\n",
+ id, typ, comment, subelement.path())
+ }
+ return id
+}
+
+// setValueNode associates node id with the value v.
+// cgn identifies the context iff v is a local variable.
+//
+func (a *analysis) setValueNode(v ssa.Value, id nodeid, cgn *cgnode) {
+ if cgn != nil {
+ a.localval[v] = id
+ } else {
+ a.globalval[v] = id
+ }
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\tval[%s] = n%d (%T)\n", v.Name(), id, v)
+ }
+
+ // Due to context-sensitivity, we may encounter the same Value
+ // in many contexts. We merge them to a canonical node, since
+ // that's what all clients want.
+
+ // Record the (v, id) relation if the client has queried pts(v).
+ if _, ok := a.config.Queries[v]; ok {
+ t := v.Type()
+ ptr, ok := a.result.Queries[v]
+ if !ok {
+ // First time? Create the canonical query node.
+ ptr = Pointer{a, a.addNodes(t, "query")}
+ a.result.Queries[v] = ptr
+ }
+ a.result.Queries[v] = ptr
+ a.copy(ptr.n, id, a.sizeof(t))
+ }
+
+ // Record the (*v, id) relation if the client has queried pts(*v).
+ if _, ok := a.config.IndirectQueries[v]; ok {
+ t := v.Type()
+ ptr, ok := a.result.IndirectQueries[v]
+ if !ok {
+ // First time? Create the canonical indirect query node.
+ ptr = Pointer{a, a.addNodes(v.Type(), "query.indirect")}
+ a.result.IndirectQueries[v] = ptr
+ }
+ a.genLoad(cgn, ptr.n, v, 0, a.sizeof(t))
+ }
+
+ for _, query := range a.config.extendedQueries[v] {
+ t, nid := a.evalExtendedQuery(v.Type().Underlying(), id, query.ops)
+
+ if query.ptr.a == nil {
+ query.ptr.a = a
+ query.ptr.n = a.addNodes(t, "query.extended")
+ }
+ a.copy(query.ptr.n, nid, a.sizeof(t))
+ }
+}
+
+// endObject marks the end of a sequence of calls to addNodes denoting
+// a single object allocation.
+//
+// obj is the start node of the object, from a prior call to nextNode.
+// Its size, flags and optional data will be updated.
+//
+func (a *analysis) endObject(obj nodeid, cgn *cgnode, data interface{}) *object {
+ // Ensure object is non-empty by padding;
+ // the pad will be the object node.
+ size := uint32(a.nextNode() - obj)
+ if size == 0 {
+ a.addOneNode(tInvalid, "padding", nil)
+ }
+ objNode := a.nodes[obj]
+ o := &object{
+ size: size, // excludes padding
+ cgn: cgn,
+ data: data,
+ }
+ objNode.obj = o
+
+ return o
+}
+
+// makeFunctionObject creates and returns a new function object
+// (contour) for fn, and returns the id of its first node. It also
+// enqueues fn for subsequent constraint generation.
+//
+// For a context-sensitive contour, callersite identifies the sole
+// callsite; for shared contours, caller is nil.
+//
+func (a *analysis) makeFunctionObject(fn *ssa.Function, callersite *callsite) nodeid {
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\t---- makeFunctionObject %s\n", fn)
+ }
+
+ // obj is the function object (identity, params, results).
+ obj := a.nextNode()
+ cgn := a.makeCGNode(fn, obj, callersite)
+ sig := fn.Signature
+ a.addOneNode(sig, "func.cgnode", nil) // (scalar with Signature type)
+ if recv := sig.Recv(); recv != nil {
+ a.addNodes(recv.Type(), "func.recv")
+ }
+ a.addNodes(sig.Params(), "func.params")
+ a.addNodes(sig.Results(), "func.results")
+ a.endObject(obj, cgn, fn).flags |= otFunction
+
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\t----\n")
+ }
+
+ // Queue it up for constraint processing.
+ a.genq = append(a.genq, cgn)
+
+ return obj
+}
+
+// makeTagged creates a tagged object of type typ.
+func (a *analysis) makeTagged(typ types.Type, cgn *cgnode, data interface{}) nodeid {
+ obj := a.addOneNode(typ, "tagged.T", nil) // NB: type may be non-scalar!
+ a.addNodes(typ, "tagged.v")
+ a.endObject(obj, cgn, data).flags |= otTagged
+ return obj
+}
+
+// makeRtype returns the canonical tagged object of type *rtype whose
+// payload points to the sole rtype object for T.
+//
+// TODO(adonovan): move to reflect.go; it's part of the solver really.
+//
+func (a *analysis) makeRtype(T types.Type) nodeid {
+ if v := a.rtypes.At(T); v != nil {
+ return v.(nodeid)
+ }
+
+ // Create the object for the reflect.rtype itself, which is
+ // ordinarily a large struct but here a single node will do.
+ obj := a.nextNode()
+ a.addOneNode(T, "reflect.rtype", nil)
+ a.endObject(obj, nil, T)
+
+ id := a.makeTagged(a.reflectRtypePtr, nil, T)
+ a.nodes[id+1].typ = T // trick (each *rtype tagged object is a singleton)
+ a.addressOf(a.reflectRtypePtr, id+1, obj)
+
+ a.rtypes.Set(T, id)
+ return id
+}
+
+// rtypeValue returns the type of the *reflect.rtype-tagged object obj.
+func (a *analysis) rtypeTaggedValue(obj nodeid) types.Type {
+ tDyn, t, _ := a.taggedValue(obj)
+ if tDyn != a.reflectRtypePtr {
+ panic(fmt.Sprintf("not a *reflect.rtype-tagged object: obj=n%d tag=%v payload=n%d", obj, tDyn, t))
+ }
+ return a.nodes[t].typ
+}
+
+// valueNode returns the id of the value node for v, creating it (and
+// the association) as needed. It may return zero for uninteresting
+// values containing no pointers.
+//
+func (a *analysis) valueNode(v ssa.Value) nodeid {
+ // Value nodes for locals are created en masse by genFunc.
+ if id, ok := a.localval[v]; ok {
+ return id
+ }
+
+ // Value nodes for globals are created on demand.
+ id, ok := a.globalval[v]
+ if !ok {
+ var comment string
+ if a.log != nil {
+ comment = v.String()
+ }
+ id = a.addNodes(v.Type(), comment)
+ if obj := a.objectNode(nil, v); obj != 0 {
+ a.addressOf(v.Type(), id, obj)
+ }
+ a.setValueNode(v, id, nil)
+ }
+ return id
+}
+
+// valueOffsetNode ascertains the node for tuple/struct value v,
+// then returns the node for its subfield #index.
+//
+func (a *analysis) valueOffsetNode(v ssa.Value, index int) nodeid {
+ id := a.valueNode(v)
+ if id == 0 {
+ panic(fmt.Sprintf("cannot offset within n0: %s = %s", v.Name(), v))
+ }
+ return id + nodeid(a.offsetOf(v.Type(), index))
+}
+
+// isTaggedObject reports whether object obj is a tagged object.
+func (a *analysis) isTaggedObject(obj nodeid) bool {
+ return a.nodes[obj].obj.flags&otTagged != 0
+}
+
+// taggedValue returns the dynamic type tag, the (first node of the)
+// payload, and the indirect flag of the tagged object starting at id.
+// Panic ensues if !isTaggedObject(id).
+//
+func (a *analysis) taggedValue(obj nodeid) (tDyn types.Type, v nodeid, indirect bool) {
+ n := a.nodes[obj]
+ flags := n.obj.flags
+ if flags&otTagged == 0 {
+ panic(fmt.Sprintf("not a tagged object: n%d", obj))
+ }
+ return n.typ, obj + 1, flags&otIndirect != 0
+}
+
+// funcParams returns the first node of the params (P) block of the
+// function whose object node (obj.flags&otFunction) is id.
+//
+func (a *analysis) funcParams(id nodeid) nodeid {
+ n := a.nodes[id]
+ if n.obj == nil || n.obj.flags&otFunction == 0 {
+ panic(fmt.Sprintf("funcParams(n%d): not a function object block", id))
+ }
+ return id + 1
+}
+
+// funcResults returns the first node of the results (R) block of the
+// function whose object node (obj.flags&otFunction) is id.
+//
+func (a *analysis) funcResults(id nodeid) nodeid {
+ n := a.nodes[id]
+ if n.obj == nil || n.obj.flags&otFunction == 0 {
+ panic(fmt.Sprintf("funcResults(n%d): not a function object block", id))
+ }
+ sig := n.typ.(*types.Signature)
+ id += 1 + nodeid(a.sizeof(sig.Params()))
+ if sig.Recv() != nil {
+ id += nodeid(a.sizeof(sig.Recv().Type()))
+ }
+ return id
+}
+
+// ---------- Constraint creation ----------
+
+// copy creates a constraint of the form dst = src.
+// sizeof is the width (in logical fields) of the copied type.
+//
+func (a *analysis) copy(dst, src nodeid, sizeof uint32) {
+ if src == dst || sizeof == 0 {
+ return // trivial
+ }
+ if src == 0 || dst == 0 {
+ panic(fmt.Sprintf("ill-typed copy dst=n%d src=n%d", dst, src))
+ }
+ for i := uint32(0); i < sizeof; i++ {
+ a.addConstraint(©Constraint{dst, src})
+ src++
+ dst++
+ }
+}
+
+// addressOf creates a constraint of the form id = &obj.
+// T is the type of the address.
+func (a *analysis) addressOf(T types.Type, id, obj nodeid) {
+ if id == 0 {
+ panic("addressOf: zero id")
+ }
+ if obj == 0 {
+ panic("addressOf: zero obj")
+ }
+ if a.shouldTrack(T) {
+ a.addConstraint(&addrConstraint{id, obj})
+ }
+}
+
+// load creates a load constraint of the form dst = src[offset].
+// offset is the pointer offset in logical fields.
+// sizeof is the width (in logical fields) of the loaded type.
+//
+func (a *analysis) load(dst, src nodeid, offset, sizeof uint32) {
+ if dst == 0 {
+ return // load of non-pointerlike value
+ }
+ if src == 0 && dst == 0 {
+ return // non-pointerlike operation
+ }
+ if src == 0 || dst == 0 {
+ panic(fmt.Sprintf("ill-typed load dst=n%d src=n%d", dst, src))
+ }
+ for i := uint32(0); i < sizeof; i++ {
+ a.addConstraint(&loadConstraint{offset, dst, src})
+ offset++
+ dst++
+ }
+}
+
+// store creates a store constraint of the form dst[offset] = src.
+// offset is the pointer offset in logical fields.
+// sizeof is the width (in logical fields) of the stored type.
+//
+func (a *analysis) store(dst, src nodeid, offset uint32, sizeof uint32) {
+ if src == 0 {
+ return // store of non-pointerlike value
+ }
+ if src == 0 && dst == 0 {
+ return // non-pointerlike operation
+ }
+ if src == 0 || dst == 0 {
+ panic(fmt.Sprintf("ill-typed store dst=n%d src=n%d", dst, src))
+ }
+ for i := uint32(0); i < sizeof; i++ {
+ a.addConstraint(&storeConstraint{offset, dst, src})
+ offset++
+ src++
+ }
+}
+
+// offsetAddr creates an offsetAddr constraint of the form dst = &src.#offset.
+// offset is the field offset in logical fields.
+// T is the type of the address.
+//
+func (a *analysis) offsetAddr(T types.Type, dst, src nodeid, offset uint32) {
+ if !a.shouldTrack(T) {
+ return
+ }
+ if offset == 0 {
+ // Simplify dst = &src->f0
+ // to dst = src
+ // (NB: this optimisation is defeated by the identity
+ // field prepended to struct and array objects.)
+ a.copy(dst, src, 1)
+ } else {
+ a.addConstraint(&offsetAddrConstraint{offset, dst, src})
+ }
+}
+
+// typeAssert creates a typeFilter or untag constraint of the form dst = src.(T):
+// typeFilter for an interface, untag for a concrete type.
+// The exact flag is specified as for untagConstraint.
+//
+func (a *analysis) typeAssert(T types.Type, dst, src nodeid, exact bool) {
+ if isInterface(T) {
+ a.addConstraint(&typeFilterConstraint{T, dst, src})
+ } else {
+ a.addConstraint(&untagConstraint{T, dst, src, exact})
+ }
+}
+
+// addConstraint adds c to the constraint set.
+func (a *analysis) addConstraint(c constraint) {
+ a.constraints = append(a.constraints, c)
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\t%s\n", c)
+ }
+}
+
+// copyElems generates load/store constraints for *dst = *src,
+// where src and dst are slices or *arrays.
+//
+func (a *analysis) copyElems(cgn *cgnode, typ types.Type, dst, src ssa.Value) {
+ tmp := a.addNodes(typ, "copy")
+ sz := a.sizeof(typ)
+ a.genLoad(cgn, tmp, src, 1, sz)
+ a.genStore(cgn, dst, tmp, 1, sz)
+}
+
+// ---------- Constraint generation ----------
+
+// genConv generates constraints for the conversion operation conv.
+func (a *analysis) genConv(conv *ssa.Convert, cgn *cgnode) {
+ res := a.valueNode(conv)
+ if res == 0 {
+ return // result is non-pointerlike
+ }
+
+ tSrc := conv.X.Type()
+ tDst := conv.Type()
+
+ switch utSrc := tSrc.Underlying().(type) {
+ case *types.Slice:
+ // []byte/[]rune -> string?
+ return
+
+ case *types.Pointer:
+ // *T -> unsafe.Pointer?
+ if tDst.Underlying() == tUnsafePtr {
+ return // we don't model unsafe aliasing (unsound)
+ }
+
+ case *types.Basic:
+ switch tDst.Underlying().(type) {
+ case *types.Pointer:
+ // Treat unsafe.Pointer->*T conversions like
+ // new(T) and create an unaliased object.
+ if utSrc == tUnsafePtr {
+ obj := a.addNodes(mustDeref(tDst), "unsafe.Pointer conversion")
+ a.endObject(obj, cgn, conv)
+ a.addressOf(tDst, res, obj)
+ return
+ }
+
+ case *types.Slice:
+ // string -> []byte/[]rune (or named aliases)?
+ if utSrc.Info()&types.IsString != 0 {
+ obj := a.addNodes(sliceToArray(tDst), "convert")
+ a.endObject(obj, cgn, conv)
+ a.addressOf(tDst, res, obj)
+ return
+ }
+
+ case *types.Basic:
+ // All basic-to-basic type conversions are no-ops.
+ // This includes uintptr<->unsafe.Pointer conversions,
+ // which we (unsoundly) ignore.
+ return
+ }
+ }
+
+ panic(fmt.Sprintf("illegal *ssa.Convert %s -> %s: %s", tSrc, tDst, conv.Parent()))
+}
+
+// genAppend generates constraints for a call to append.
+func (a *analysis) genAppend(instr *ssa.Call, cgn *cgnode) {
+ // Consider z = append(x, y). y is optional.
+ // This may allocate a new [1]T array; call its object w.
+ // We get the following constraints:
+ // z = x
+ // z = &w
+ // *z = *y
+
+ x := instr.Call.Args[0]
+
+ z := instr
+ a.copy(a.valueNode(z), a.valueNode(x), 1) // z = x
+
+ if len(instr.Call.Args) == 1 {
+ return // no allocation for z = append(x) or _ = append(x).
+ }
+
+ // TODO(adonovan): test append([]byte, ...string) []byte.
+
+ y := instr.Call.Args[1]
+ tArray := sliceToArray(instr.Call.Args[0].Type())
+
+ w := a.nextNode()
+ a.addNodes(tArray, "append")
+ a.endObject(w, cgn, instr)
+
+ a.copyElems(cgn, tArray.Elem(), z, y) // *z = *y
+ a.addressOf(instr.Type(), a.valueNode(z), w) // z = &w
+}
+
+// genBuiltinCall generates constraints for a call to a built-in.
+func (a *analysis) genBuiltinCall(instr ssa.CallInstruction, cgn *cgnode) {
+ call := instr.Common()
+ switch call.Value.(*ssa.Builtin).Name() {
+ case "append":
+ // Safe cast: append cannot appear in a go or defer statement.
+ a.genAppend(instr.(*ssa.Call), cgn)
+
+ case "copy":
+ tElem := call.Args[0].Type().Underlying().(*types.Slice).Elem()
+ a.copyElems(cgn, tElem, call.Args[0], call.Args[1])
+
+ case "panic":
+ a.copy(a.panicNode, a.valueNode(call.Args[0]), 1)
+
+ case "recover":
+ if v := instr.Value(); v != nil {
+ a.copy(a.valueNode(v), a.panicNode, 1)
+ }
+
+ case "print":
+ // In the tests, the probe might be the sole reference
+ // to its arg, so make sure we create nodes for it.
+ if len(call.Args) > 0 {
+ a.valueNode(call.Args[0])
+ }
+
+ case "ssa:wrapnilchk":
+ a.copy(a.valueNode(instr.Value()), a.valueNode(call.Args[0]), 1)
+
+ default:
+ // No-ops: close len cap real imag complex print println delete.
+ }
+}
+
+// shouldUseContext defines the context-sensitivity policy. It
+// returns true if we should analyse all static calls to fn anew.
+//
+// Obviously this interface rather limits how much freedom we have to
+// choose a policy. The current policy, rather arbitrarily, is true
+// for intrinsics and accessor methods (actually: short, single-block,
+// call-free functions). This is just a starting point.
+//
+func (a *analysis) shouldUseContext(fn *ssa.Function) bool {
+ if a.findIntrinsic(fn) != nil {
+ return true // treat intrinsics context-sensitively
+ }
+ if len(fn.Blocks) != 1 {
+ return false // too expensive
+ }
+ blk := fn.Blocks[0]
+ if len(blk.Instrs) > 10 {
+ return false // too expensive
+ }
+ if fn.Synthetic != "" && (fn.Pkg == nil || fn != fn.Pkg.Func("init")) {
+ return true // treat synthetic wrappers context-sensitively
+ }
+ for _, instr := range blk.Instrs {
+ switch instr := instr.(type) {
+ case ssa.CallInstruction:
+ // Disallow function calls (except to built-ins)
+ // because of the danger of unbounded recursion.
+ if _, ok := instr.Common().Value.(*ssa.Builtin); !ok {
+ return false
+ }
+ }
+ }
+ return true
+}
+
+// genStaticCall generates constraints for a statically dispatched function call.
+func (a *analysis) genStaticCall(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
+ fn := call.StaticCallee()
+
+ // Special cases for inlined intrinsics.
+ switch fn {
+ case a.runtimeSetFinalizer:
+ // Inline SetFinalizer so the call appears direct.
+ site.targets = a.addOneNode(tInvalid, "SetFinalizer.targets", nil)
+ a.addConstraint(&runtimeSetFinalizerConstraint{
+ targets: site.targets,
+ x: a.valueNode(call.Args[0]),
+ f: a.valueNode(call.Args[1]),
+ })
+ return
+
+ case a.reflectValueCall:
+ // Inline (reflect.Value).Call so the call appears direct.
+ dotdotdot := false
+ ret := reflectCallImpl(a, caller, site, a.valueNode(call.Args[0]), a.valueNode(call.Args[1]), dotdotdot)
+ if result != 0 {
+ a.addressOf(fn.Signature.Results().At(0).Type(), result, ret)
+ }
+ return
+ }
+
+ // Ascertain the context (contour/cgnode) for a particular call.
+ var obj nodeid
+ if a.shouldUseContext(fn) {
+ obj = a.makeFunctionObject(fn, site) // new contour
+ } else {
+ obj = a.objectNode(nil, fn) // shared contour
+ }
+ a.callEdge(caller, site, obj)
+
+ sig := call.Signature()
+
+ // Copy receiver, if any.
+ params := a.funcParams(obj)
+ args := call.Args
+ if sig.Recv() != nil {
+ sz := a.sizeof(sig.Recv().Type())
+ a.copy(params, a.valueNode(args[0]), sz)
+ params += nodeid(sz)
+ args = args[1:]
+ }
+
+ // Copy actual parameters into formal params block.
+ // Must loop, since the actuals aren't contiguous.
+ for i, arg := range args {
+ sz := a.sizeof(sig.Params().At(i).Type())
+ a.copy(params, a.valueNode(arg), sz)
+ params += nodeid(sz)
+ }
+
+ // Copy formal results block to actual result.
+ if result != 0 {
+ a.copy(result, a.funcResults(obj), a.sizeof(sig.Results()))
+ }
+}
+
+// genDynamicCall generates constraints for a dynamic function call.
+func (a *analysis) genDynamicCall(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
+ // pts(targets) will be the set of possible call targets.
+ site.targets = a.valueNode(call.Value)
+
+ // We add dynamic closure rules that store the arguments into
+ // the P-block and load the results from the R-block of each
+ // function discovered in pts(targets).
+
+ sig := call.Signature()
+ var offset uint32 = 1 // P/R block starts at offset 1
+ for i, arg := range call.Args {
+ sz := a.sizeof(sig.Params().At(i).Type())
+ a.genStore(caller, call.Value, a.valueNode(arg), offset, sz)
+ offset += sz
+ }
+ if result != 0 {
+ a.genLoad(caller, result, call.Value, offset, a.sizeof(sig.Results()))
+ }
+}
+
+// genInvoke generates constraints for a dynamic method invocation.
+func (a *analysis) genInvoke(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
+ if call.Value.Type() == a.reflectType {
+ a.genInvokeReflectType(caller, site, call, result)
+ return
+ }
+
+ sig := call.Signature()
+
+ // Allocate a contiguous targets/params/results block for this call.
+ block := a.nextNode()
+ // pts(targets) will be the set of possible call targets
+ site.targets = a.addOneNode(sig, "invoke.targets", nil)
+ p := a.addNodes(sig.Params(), "invoke.params")
+ r := a.addNodes(sig.Results(), "invoke.results")
+
+ // Copy the actual parameters into the call's params block.
+ for i, n := 0, sig.Params().Len(); i < n; i++ {
+ sz := a.sizeof(sig.Params().At(i).Type())
+ a.copy(p, a.valueNode(call.Args[i]), sz)
+ p += nodeid(sz)
+ }
+ // Copy the call's results block to the actual results.
+ if result != 0 {
+ a.copy(result, r, a.sizeof(sig.Results()))
+ }
+
+ // We add a dynamic invoke constraint that will connect the
+ // caller's and the callee's P/R blocks for each discovered
+ // call target.
+ a.addConstraint(&invokeConstraint{call.Method, a.valueNode(call.Value), block})
+}
+
+// genInvokeReflectType is a specialization of genInvoke where the
+// receiver type is a reflect.Type, under the assumption that there
+// can be at most one implementation of this interface, *reflect.rtype.
+//
+// (Though this may appear to be an instance of a pattern---method
+// calls on interfaces known to have exactly one implementation---in
+// practice it occurs rarely, so we special case for reflect.Type.)
+//
+// In effect we treat this:
+// var rt reflect.Type = ...
+// rt.F()
+// as this:
+// rt.(*reflect.rtype).F()
+//
+func (a *analysis) genInvokeReflectType(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
+ // Unpack receiver into rtype
+ rtype := a.addOneNode(a.reflectRtypePtr, "rtype.recv", nil)
+ recv := a.valueNode(call.Value)
+ a.typeAssert(a.reflectRtypePtr, rtype, recv, true)
+
+ // Look up the concrete method.
+ fn := a.prog.LookupMethod(a.reflectRtypePtr, call.Method.Pkg(), call.Method.Name())
+
+ obj := a.makeFunctionObject(fn, site) // new contour for this call
+ a.callEdge(caller, site, obj)
+
+ // From now on, it's essentially a static call, but little is
+ // gained by factoring together the code for both cases.
+
+ sig := fn.Signature // concrete method
+ targets := a.addOneNode(sig, "call.targets", nil)
+ a.addressOf(sig, targets, obj) // (a singleton)
+
+ // Copy receiver.
+ params := a.funcParams(obj)
+ a.copy(params, rtype, 1)
+ params++
+
+ // Copy actual parameters into formal P-block.
+ // Must loop, since the actuals aren't contiguous.
+ for i, arg := range call.Args {
+ sz := a.sizeof(sig.Params().At(i).Type())
+ a.copy(params, a.valueNode(arg), sz)
+ params += nodeid(sz)
+ }
+
+ // Copy formal R-block to actual R-block.
+ if result != 0 {
+ a.copy(result, a.funcResults(obj), a.sizeof(sig.Results()))
+ }
+}
+
+// genCall generates constraints for call instruction instr.
+func (a *analysis) genCall(caller *cgnode, instr ssa.CallInstruction) {
+ call := instr.Common()
+
+ // Intrinsic implementations of built-in functions.
+ if _, ok := call.Value.(*ssa.Builtin); ok {
+ a.genBuiltinCall(instr, caller)
+ return
+ }
+
+ var result nodeid
+ if v := instr.Value(); v != nil {
+ result = a.valueNode(v)
+ }
+
+ site := &callsite{instr: instr}
+ if call.StaticCallee() != nil {
+ a.genStaticCall(caller, site, call, result)
+ } else if call.IsInvoke() {
+ a.genInvoke(caller, site, call, result)
+ } else {
+ a.genDynamicCall(caller, site, call, result)
+ }
+
+ caller.sites = append(caller.sites, site)
+
+ if a.log != nil {
+ // TODO(adonovan): debug: improve log message.
+ fmt.Fprintf(a.log, "\t%s to targets %s from %s\n", site, site.targets, caller)
+ }
+}
+
+// objectNode returns the object to which v points, if known.
+// In other words, if the points-to set of v is a singleton, it
+// returns the sole label, zero otherwise.
+//
+// We exploit this information to make the generated constraints less
+// dynamic. For example, a complex load constraint can be replaced by
+// a simple copy constraint when the sole destination is known a priori.
+//
+// Some SSA instructions always have singletons points-to sets:
+// Alloc, Function, Global, MakeChan, MakeClosure, MakeInterface, MakeMap, MakeSlice.
+// Others may be singletons depending on their operands:
+// FreeVar, Const, Convert, FieldAddr, IndexAddr, Slice.
+//
+// Idempotent. Objects are created as needed, possibly via recursion
+// down the SSA value graph, e.g IndexAddr(FieldAddr(Alloc))).
+//
+func (a *analysis) objectNode(cgn *cgnode, v ssa.Value) nodeid {
+ switch v.(type) {
+ case *ssa.Global, *ssa.Function, *ssa.Const, *ssa.FreeVar:
+ // Global object.
+ obj, ok := a.globalobj[v]
+ if !ok {
+ switch v := v.(type) {
+ case *ssa.Global:
+ obj = a.nextNode()
+ a.addNodes(mustDeref(v.Type()), "global")
+ a.endObject(obj, nil, v)
+
+ case *ssa.Function:
+ obj = a.makeFunctionObject(v, nil)
+
+ case *ssa.Const:
+ // not addressable
+
+ case *ssa.FreeVar:
+ // not addressable
+ }
+
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\tglobalobj[%s] = n%d\n", v, obj)
+ }
+ a.globalobj[v] = obj
+ }
+ return obj
+ }
+
+ // Local object.
+ obj, ok := a.localobj[v]
+ if !ok {
+ switch v := v.(type) {
+ case *ssa.Alloc:
+ obj = a.nextNode()
+ a.addNodes(mustDeref(v.Type()), "alloc")
+ a.endObject(obj, cgn, v)
+
+ case *ssa.MakeSlice:
+ obj = a.nextNode()
+ a.addNodes(sliceToArray(v.Type()), "makeslice")
+ a.endObject(obj, cgn, v)
+
+ case *ssa.MakeChan:
+ obj = a.nextNode()
+ a.addNodes(v.Type().Underlying().(*types.Chan).Elem(), "makechan")
+ a.endObject(obj, cgn, v)
+
+ case *ssa.MakeMap:
+ obj = a.nextNode()
+ tmap := v.Type().Underlying().(*types.Map)
+ a.addNodes(tmap.Key(), "makemap.key")
+ elem := a.addNodes(tmap.Elem(), "makemap.value")
+
+ // To update the value field, MapUpdate
+ // generates store-with-offset constraints which
+ // the presolver can't model, so we must mark
+ // those nodes indirect.
+ for id, end := elem, elem+nodeid(a.sizeof(tmap.Elem())); id < end; id++ {
+ a.mapValues = append(a.mapValues, id)
+ }
+ a.endObject(obj, cgn, v)
+
+ case *ssa.MakeInterface:
+ tConc := v.X.Type()
+ obj = a.makeTagged(tConc, cgn, v)
+
+ // Copy the value into it, if nontrivial.
+ if x := a.valueNode(v.X); x != 0 {
+ a.copy(obj+1, x, a.sizeof(tConc))
+ }
+
+ case *ssa.FieldAddr:
+ if xobj := a.objectNode(cgn, v.X); xobj != 0 {
+ obj = xobj + nodeid(a.offsetOf(mustDeref(v.X.Type()), v.Field))
+ }
+
+ case *ssa.IndexAddr:
+ if xobj := a.objectNode(cgn, v.X); xobj != 0 {
+ obj = xobj + 1
+ }
+
+ case *ssa.Slice:
+ obj = a.objectNode(cgn, v.X)
+
+ case *ssa.Convert:
+ // TODO(adonovan): opt: handle these cases too:
+ // - unsafe.Pointer->*T conversion acts like Alloc
+ // - string->[]byte/[]rune conversion acts like MakeSlice
+ }
+
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\tlocalobj[%s] = n%d\n", v.Name(), obj)
+ }
+ a.localobj[v] = obj
+ }
+ return obj
+}
+
+// genLoad generates constraints for result = *(ptr + val).
+func (a *analysis) genLoad(cgn *cgnode, result nodeid, ptr ssa.Value, offset, sizeof uint32) {
+ if obj := a.objectNode(cgn, ptr); obj != 0 {
+ // Pre-apply loadConstraint.solve().
+ a.copy(result, obj+nodeid(offset), sizeof)
+ } else {
+ a.load(result, a.valueNode(ptr), offset, sizeof)
+ }
+}
+
+// genOffsetAddr generates constraints for a 'v=ptr.field' (FieldAddr)
+// or 'v=ptr[*]' (IndexAddr) instruction v.
+func (a *analysis) genOffsetAddr(cgn *cgnode, v ssa.Value, ptr nodeid, offset uint32) {
+ dst := a.valueNode(v)
+ if obj := a.objectNode(cgn, v); obj != 0 {
+ // Pre-apply offsetAddrConstraint.solve().
+ a.addressOf(v.Type(), dst, obj)
+ } else {
+ a.offsetAddr(v.Type(), dst, ptr, offset)
+ }
+}
+
+// genStore generates constraints for *(ptr + offset) = val.
+func (a *analysis) genStore(cgn *cgnode, ptr ssa.Value, val nodeid, offset, sizeof uint32) {
+ if obj := a.objectNode(cgn, ptr); obj != 0 {
+ // Pre-apply storeConstraint.solve().
+ a.copy(obj+nodeid(offset), val, sizeof)
+ } else {
+ a.store(a.valueNode(ptr), val, offset, sizeof)
+ }
+}
+
+// genInstr generates constraints for instruction instr in context cgn.
+func (a *analysis) genInstr(cgn *cgnode, instr ssa.Instruction) {
+ if a.log != nil {
+ var prefix string
+ if val, ok := instr.(ssa.Value); ok {
+ prefix = val.Name() + " = "
+ }
+ fmt.Fprintf(a.log, "; %s%s\n", prefix, instr)
+ }
+
+ switch instr := instr.(type) {
+ case *ssa.DebugRef:
+ // no-op.
+
+ case *ssa.UnOp:
+ switch instr.Op {
+ case token.ARROW: // <-x
+ // We can ignore instr.CommaOk because the node we're
+ // altering is always at zero offset relative to instr
+ tElem := instr.X.Type().Underlying().(*types.Chan).Elem()
+ a.genLoad(cgn, a.valueNode(instr), instr.X, 0, a.sizeof(tElem))
+
+ case token.MUL: // *x
+ a.genLoad(cgn, a.valueNode(instr), instr.X, 0, a.sizeof(instr.Type()))
+
+ default:
+ // NOT, SUB, XOR: no-op.
+ }
+
+ case *ssa.BinOp:
+ // All no-ops.
+
+ case ssa.CallInstruction: // *ssa.Call, *ssa.Go, *ssa.Defer
+ a.genCall(cgn, instr)
+
+ case *ssa.ChangeType:
+ a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
+
+ case *ssa.Convert:
+ a.genConv(instr, cgn)
+
+ case *ssa.Extract:
+ a.copy(a.valueNode(instr),
+ a.valueOffsetNode(instr.Tuple, instr.Index),
+ a.sizeof(instr.Type()))
+
+ case *ssa.FieldAddr:
+ a.genOffsetAddr(cgn, instr, a.valueNode(instr.X),
+ a.offsetOf(mustDeref(instr.X.Type()), instr.Field))
+
+ case *ssa.IndexAddr:
+ a.genOffsetAddr(cgn, instr, a.valueNode(instr.X), 1)
+
+ case *ssa.Field:
+ a.copy(a.valueNode(instr),
+ a.valueOffsetNode(instr.X, instr.Field),
+ a.sizeof(instr.Type()))
+
+ case *ssa.Index:
+ a.copy(a.valueNode(instr), 1+a.valueNode(instr.X), a.sizeof(instr.Type()))
+
+ case *ssa.Select:
+ recv := a.valueOffsetNode(instr, 2) // instr : (index, recvOk, recv0, ... recv_n-1)
+ for _, st := range instr.States {
+ elemSize := a.sizeof(st.Chan.Type().Underlying().(*types.Chan).Elem())
+ switch st.Dir {
+ case types.RecvOnly:
+ a.genLoad(cgn, recv, st.Chan, 0, elemSize)
+ recv += nodeid(elemSize)
+
+ case types.SendOnly:
+ a.genStore(cgn, st.Chan, a.valueNode(st.Send), 0, elemSize)
+ }
+ }
+
+ case *ssa.Return:
+ results := a.funcResults(cgn.obj)
+ for _, r := range instr.Results {
+ sz := a.sizeof(r.Type())
+ a.copy(results, a.valueNode(r), sz)
+ results += nodeid(sz)
+ }
+
+ case *ssa.Send:
+ a.genStore(cgn, instr.Chan, a.valueNode(instr.X), 0, a.sizeof(instr.X.Type()))
+
+ case *ssa.Store:
+ a.genStore(cgn, instr.Addr, a.valueNode(instr.Val), 0, a.sizeof(instr.Val.Type()))
+
+ case *ssa.Alloc, *ssa.MakeSlice, *ssa.MakeChan, *ssa.MakeMap, *ssa.MakeInterface:
+ v := instr.(ssa.Value)
+ a.addressOf(v.Type(), a.valueNode(v), a.objectNode(cgn, v))
+
+ case *ssa.ChangeInterface:
+ a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
+
+ case *ssa.TypeAssert:
+ a.typeAssert(instr.AssertedType, a.valueNode(instr), a.valueNode(instr.X), true)
+
+ case *ssa.Slice:
+ a.copy(a.valueNode(instr), a.valueNode(instr.X), 1)
+
+ case *ssa.If, *ssa.Jump:
+ // no-op.
+
+ case *ssa.Phi:
+ sz := a.sizeof(instr.Type())
+ for _, e := range instr.Edges {
+ a.copy(a.valueNode(instr), a.valueNode(e), sz)
+ }
+
+ case *ssa.MakeClosure:
+ fn := instr.Fn.(*ssa.Function)
+ a.copy(a.valueNode(instr), a.valueNode(fn), 1)
+ // Free variables are treated like global variables.
+ for i, b := range instr.Bindings {
+ a.copy(a.valueNode(fn.FreeVars[i]), a.valueNode(b), a.sizeof(b.Type()))
+ }
+
+ case *ssa.RunDefers:
+ // The analysis is flow insensitive, so we just "call"
+ // defers as we encounter them.
+
+ case *ssa.Range:
+ // Do nothing. Next{Iter: *ssa.Range} handles this case.
+
+ case *ssa.Next:
+ if !instr.IsString { // map
+ // Assumes that Next is always directly applied to a Range result.
+ theMap := instr.Iter.(*ssa.Range).X
+ tMap := theMap.Type().Underlying().(*types.Map)
+
+ ksize := a.sizeof(tMap.Key())
+ vsize := a.sizeof(tMap.Elem())
+
+ // The k/v components of the Next tuple may each be invalid.
+ tTuple := instr.Type().(*types.Tuple)
+
+ // Load from the map's (k,v) into the tuple's (ok, k, v).
+ osrc := uint32(0) // offset within map object
+ odst := uint32(1) // offset within tuple (initially just after 'ok bool')
+ sz := uint32(0) // amount to copy
+
+ // Is key valid?
+ if tTuple.At(1).Type() != tInvalid {
+ sz += ksize
+ } else {
+ odst += ksize
+ osrc += ksize
+ }
+
+ // Is value valid?
+ if tTuple.At(2).Type() != tInvalid {
+ sz += vsize
+ }
+
+ a.genLoad(cgn, a.valueNode(instr)+nodeid(odst), theMap, osrc, sz)
+ }
+
+ case *ssa.Lookup:
+ if tMap, ok := instr.X.Type().Underlying().(*types.Map); ok {
+ // CommaOk can be ignored: field 0 is a no-op.
+ ksize := a.sizeof(tMap.Key())
+ vsize := a.sizeof(tMap.Elem())
+ a.genLoad(cgn, a.valueNode(instr), instr.X, ksize, vsize)
+ }
+
+ case *ssa.MapUpdate:
+ tmap := instr.Map.Type().Underlying().(*types.Map)
+ ksize := a.sizeof(tmap.Key())
+ vsize := a.sizeof(tmap.Elem())
+ a.genStore(cgn, instr.Map, a.valueNode(instr.Key), 0, ksize)
+ a.genStore(cgn, instr.Map, a.valueNode(instr.Value), ksize, vsize)
+
+ case *ssa.Panic:
+ a.copy(a.panicNode, a.valueNode(instr.X), 1)
+
+ default:
+ panic(fmt.Sprintf("unimplemented: %T", instr))
+ }
+}
+
+func (a *analysis) makeCGNode(fn *ssa.Function, obj nodeid, callersite *callsite) *cgnode {
+ cgn := &cgnode{fn: fn, obj: obj, callersite: callersite}
+ a.cgnodes = append(a.cgnodes, cgn)
+ return cgn
+}
+
+// genRootCalls generates the synthetic root of the callgraph and the
+// initial calls from it to the analysis scope, such as main, a test
+// or a library.
+//
+func (a *analysis) genRootCalls() *cgnode {
+ r := a.prog.NewFunction("<root>", new(types.Signature), "root of callgraph")
+ root := a.makeCGNode(r, 0, nil)
+
+ // TODO(adonovan): make an ssa utility to construct an actual
+ // root function so we don't need to special-case site-less
+ // call edges.
+
+ // For each main package, call main.init(), main.main().
+ for _, mainPkg := range a.config.Mains {
+ main := mainPkg.Func("main")
+ if main == nil {
+ panic(fmt.Sprintf("%s has no main function", mainPkg))
+ }
+
+ targets := a.addOneNode(main.Signature, "root.targets", nil)
+ site := &callsite{targets: targets}
+ root.sites = append(root.sites, site)
+ for _, fn := range [2]*ssa.Function{mainPkg.Func("init"), main} {
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\troot call to %s:\n", fn)
+ }
+ a.copy(targets, a.valueNode(fn), 1)
+ }
+ }
+
+ return root
+}
+
+// genFunc generates constraints for function fn.
+func (a *analysis) genFunc(cgn *cgnode) {
+ fn := cgn.fn
+
+ impl := a.findIntrinsic(fn)
+
+ if a.log != nil {
+ fmt.Fprintf(a.log, "\n\n==== Generating constraints for %s, %s\n", cgn, cgn.contour())
+
+ // Hack: don't display body if intrinsic.
+ if impl != nil {
+ fn2 := *cgn.fn // copy
+ fn2.Locals = nil
+ fn2.Blocks = nil
+ fn2.WriteTo(a.log)
+ } else {
+ cgn.fn.WriteTo(a.log)
+ }
+ }
+
+ if impl != nil {
+ impl(a, cgn)
+ return
+ }
+
+ if fn.Blocks == nil {
+ // External function with no intrinsic treatment.
+ // We'll warn about calls to such functions at the end.
+ return
+ }
+
+ if a.log != nil {
+ fmt.Fprintln(a.log, "; Creating nodes for local values")
+ }
+
+ a.localval = make(map[ssa.Value]nodeid)
+ a.localobj = make(map[ssa.Value]nodeid)
+
+ // The value nodes for the params are in the func object block.
+ params := a.funcParams(cgn.obj)
+ for _, p := range fn.Params {
+ a.setValueNode(p, params, cgn)
+ params += nodeid(a.sizeof(p.Type()))
+ }
+
+ // Free variables have global cardinality:
+ // the outer function sets them with MakeClosure;
+ // the inner function accesses them with FreeVar.
+ //
+ // TODO(adonovan): treat free vars context-sensitively.
+
+ // Create value nodes for all value instructions
+ // since SSA may contain forward references.
+ var space [10]*ssa.Value
+ for _, b := range fn.Blocks {
+ for _, instr := range b.Instrs {
+ switch instr := instr.(type) {
+ case *ssa.Range:
+ // do nothing: it has a funky type,
+ // and *ssa.Next does all the work.
+
+ case ssa.Value:
+ var comment string
+ if a.log != nil {
+ comment = instr.Name()
+ }
+ id := a.addNodes(instr.Type(), comment)
+ a.setValueNode(instr, id, cgn)
+ }
+
+ // Record all address-taken functions (for presolver).
+ rands := instr.Operands(space[:0])
+ if call, ok := instr.(ssa.CallInstruction); ok && !call.Common().IsInvoke() {
+ // Skip CallCommon.Value in "call" mode.
+ // TODO(adonovan): fix: relies on unspecified ordering. Specify it.
+ rands = rands[1:]
+ }
+ for _, rand := range rands {
+ if atf, ok := (*rand).(*ssa.Function); ok {
+ a.atFuncs[atf] = true
+ }
+ }
+ }
+ }
+
+ // Generate constraints for instructions.
+ for _, b := range fn.Blocks {
+ for _, instr := range b.Instrs {
+ a.genInstr(cgn, instr)
+ }
+ }
+
+ a.localval = nil
+ a.localobj = nil
+}
+
+// genMethodsOf generates nodes and constraints for all methods of type T.
+func (a *analysis) genMethodsOf(T types.Type) {
+ itf := isInterface(T)
+
+ // TODO(adonovan): can we skip this entirely if itf is true?
+ // I think so, but the answer may depend on reflection.
+ mset := a.prog.MethodSets.MethodSet(T)
+ for i, n := 0, mset.Len(); i < n; i++ {
+ m := a.prog.MethodValue(mset.At(i))
+ a.valueNode(m)
+
+ if !itf {
+ // Methods of concrete types are address-taken functions.
+ a.atFuncs[m] = true
+ }
+ }
+}
+
+// generate generates offline constraints for the entire program.
+func (a *analysis) generate() {
+ start("Constraint generation")
+ if a.log != nil {
+ fmt.Fprintln(a.log, "==== Generating constraints")
+ }
+
+ // Create a dummy node since we use the nodeid 0 for
+ // non-pointerlike variables.
+ a.addNodes(tInvalid, "(zero)")
+
+ // Create the global node for panic values.
+ a.panicNode = a.addNodes(tEface, "panic")
+
+ // Create nodes and constraints for all methods of reflect.rtype.
+ // (Shared contours are used by dynamic calls to reflect.Type
+ // methods---typically just String().)
+ if rtype := a.reflectRtypePtr; rtype != nil {
+ a.genMethodsOf(rtype)
+ }
+
+ root := a.genRootCalls()
+
+ if a.config.BuildCallGraph {
+ a.result.CallGraph = callgraph.New(root.fn)
+ }
+
+ // Create nodes and constraints for all methods of all types
+ // that are dynamically accessible via reflection or interfaces.
+ for _, T := range a.prog.RuntimeTypes() {
+ a.genMethodsOf(T)
+ }
+
+ // Generate constraints for functions as they become reachable
+ // from the roots. (No constraints are generated for functions
+ // that are dead in this analysis scope.)
+ for len(a.genq) > 0 {
+ cgn := a.genq[0]
+ a.genq = a.genq[1:]
+ a.genFunc(cgn)
+ }
+
+ // The runtime magically allocates os.Args; so should we.
+ if os := a.prog.ImportedPackage("os"); os != nil {
+ // In effect: os.Args = new([1]string)[:]
+ T := types.NewSlice(types.Typ[types.String])
+ obj := a.addNodes(sliceToArray(T), "<command-line args>")
+ a.endObject(obj, nil, "<command-line args>")
+ a.addressOf(T, a.objectNode(nil, os.Var("Args")), obj)
+ }
+
+ // Discard generation state, to avoid confusion after node renumbering.
+ a.panicNode = 0
+ a.globalval = nil
+ a.localval = nil
+ a.localobj = nil
+
+ stop("Constraint generation")
+}
projects / dotfiles / .git / blobdiff