Merge pull request #85 from google/depfix

Complete the new Build System

5 files changed, 2129 insertions, 0 deletions

diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/channel.go b/vendor/honnef.co/go/tools/staticcheck/vrp/channel.go
new file mode 100644
index 0000000..c8fbacb
--- /dev/null
+++ b/vendor/honnef.co/go/tools/staticcheck/vrp/channel.go
@@ -0,0 +1,73 @@
+package vrp
+
+import (
+	"fmt"
+
+	"honnef.co/go/tools/ssa"
+)
+
+type ChannelInterval struct {
+	Size IntInterval
+}
+
+func (c ChannelInterval) Union(other Range) Range {
+	i, ok := other.(ChannelInterval)
+	if !ok {
+		i = ChannelInterval{EmptyIntInterval}
+	}
+	if c.Size.Empty() || !c.Size.IsKnown() {
+		return i
+	}
+	if i.Size.Empty() || !i.Size.IsKnown() {
+		return c
+	}
+	return ChannelInterval{
+		Size: c.Size.Union(i.Size).(IntInterval),
+	}
+}
+
+func (c ChannelInterval) String() string {
+	return c.Size.String()
+}
+
+func (c ChannelInterval) IsKnown() bool {
+	return c.Size.IsKnown()
+}
+
+type MakeChannelConstraint struct {
+	aConstraint
+	Buffer ssa.Value
+}
+type ChannelChangeTypeConstraint struct {
+	aConstraint
+	X ssa.Value
+}
+
+func NewMakeChannelConstraint(buffer, y ssa.Value) Constraint {
+	return &MakeChannelConstraint{NewConstraint(y), buffer}
+}
+func NewChannelChangeTypeConstraint(x, y ssa.Value) Constraint {
+	return &ChannelChangeTypeConstraint{NewConstraint(y), x}
+}
+
+func (c *MakeChannelConstraint) Operands() []ssa.Value       { return []ssa.Value{c.Buffer} }
+func (c *ChannelChangeTypeConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
+
+func (c *MakeChannelConstraint) String() string {
+	return fmt.Sprintf("%s = make(chan, %s)", c.Y().Name, c.Buffer.Name())
+}
+func (c *ChannelChangeTypeConstraint) String() string {
+	return fmt.Sprintf("%s = changetype(%s)", c.Y().Name, c.X.Name())
+}
+
+func (c *MakeChannelConstraint) Eval(g *Graph) Range {
+	i, ok := g.Range(c.Buffer).(IntInterval)
+	if !ok {
+		return ChannelInterval{NewIntInterval(NewZ(0), PInfinity)}
+	}
+	if i.Lower.Sign() == -1 {
+		i.Lower = NewZ(0)
+	}
+	return ChannelInterval{i}
+}
+func (c *ChannelChangeTypeConstraint) Eval(g *Graph) Range { return g.Range(c.X) }
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/int.go b/vendor/honnef.co/go/tools/staticcheck/vrp/int.go
new file mode 100644
index 0000000..926bb7a
--- /dev/null
+++ b/vendor/honnef.co/go/tools/staticcheck/vrp/int.go
@@ -0,0 +1,476 @@
+package vrp
+
+import (
+	"fmt"
+	"go/token"
+	"go/types"
+	"math/big"
+
+	"honnef.co/go/tools/ssa"
+)
+
+type Zs []Z
+
+func (zs Zs) Len() int {
+	return len(zs)
+}
+
+func (zs Zs) Less(i int, j int) bool {
+	return zs[i].Cmp(zs[j]) == -1
+}
+
+func (zs Zs) Swap(i int, j int) {
+	zs[i], zs[j] = zs[j], zs[i]
+}
+
+type Z struct {
+	infinity int8
+	integer  *big.Int
+}
+
+func NewZ(n int64) Z {
+	return NewBigZ(big.NewInt(n))
+}
+
+func NewBigZ(n *big.Int) Z {
+	return Z{integer: n}
+}
+
+func (z1 Z) Infinite() bool {
+	return z1.infinity != 0
+}
+
+func (z1 Z) Add(z2 Z) Z {
+	if z2.Sign() == -1 {
+		return z1.Sub(z2.Negate())
+	}
+	if z1 == NInfinity {
+		return NInfinity
+	}
+	if z1 == PInfinity {
+		return PInfinity
+	}
+	if z2 == PInfinity {
+		return PInfinity
+	}
+
+	if !z1.Infinite() && !z2.Infinite() {
+		n := &big.Int{}
+		n.Add(z1.integer, z2.integer)
+		return NewBigZ(n)
+	}
+
+	panic(fmt.Sprintf("%s + %s is not defined", z1, z2))
+}
+
+func (z1 Z) Sub(z2 Z) Z {
+	if z2.Sign() == -1 {
+		return z1.Add(z2.Negate())
+	}
+	if !z1.Infinite() && !z2.Infinite() {
+		n := &big.Int{}
+		n.Sub(z1.integer, z2.integer)
+		return NewBigZ(n)
+	}
+
+	if z1 != PInfinity && z2 == PInfinity {
+		return NInfinity
+	}
+	if z1.Infinite() && !z2.Infinite() {
+		return Z{infinity: z1.infinity}
+	}
+	if z1 == PInfinity && z2 == PInfinity {
+		return PInfinity
+	}
+	panic(fmt.Sprintf("%s - %s is not defined", z1, z2))
+}
+
+func (z1 Z) Mul(z2 Z) Z {
+	if (z1.integer != nil && z1.integer.Sign() == 0) ||
+		(z2.integer != nil && z2.integer.Sign() == 0) {
+		return NewBigZ(&big.Int{})
+	}
+
+	if z1.infinity != 0 || z2.infinity != 0 {
+		return Z{infinity: int8(z1.Sign() * z2.Sign())}
+	}
+
+	n := &big.Int{}
+	n.Mul(z1.integer, z2.integer)
+	return NewBigZ(n)
+}
+
+func (z1 Z) Negate() Z {
+	if z1.infinity == 1 {
+		return NInfinity
+	}
+	if z1.infinity == -1 {
+		return PInfinity
+	}
+	n := &big.Int{}
+	n.Neg(z1.integer)
+	return NewBigZ(n)
+}
+
+func (z1 Z) Sign() int {
+	if z1.infinity != 0 {
+		return int(z1.infinity)
+	}
+	return z1.integer.Sign()
+}
+
+func (z1 Z) String() string {
+	if z1 == NInfinity {
+		return "-∞"
+	}
+	if z1 == PInfinity {
+		return "∞"
+	}
+	return fmt.Sprintf("%d", z1.integer)
+}
+
+func (z1 Z) Cmp(z2 Z) int {
+	if z1.infinity == z2.infinity && z1.infinity != 0 {
+		return 0
+	}
+	if z1 == PInfinity {
+		return 1
+	}
+	if z1 == NInfinity {
+		return -1
+	}
+	if z2 == NInfinity {
+		return 1
+	}
+	if z2 == PInfinity {
+		return -1
+	}
+	return z1.integer.Cmp(z2.integer)
+}
+
+func MaxZ(zs ...Z) Z {
+	if len(zs) == 0 {
+		panic("Max called with no arguments")
+	}
+	if len(zs) == 1 {
+		return zs[0]
+	}
+	ret := zs[0]
+	for _, z := range zs[1:] {
+		if z.Cmp(ret) == 1 {
+			ret = z
+		}
+	}
+	return ret
+}
+
+func MinZ(zs ...Z) Z {
+	if len(zs) == 0 {
+		panic("Min called with no arguments")
+	}
+	if len(zs) == 1 {
+		return zs[0]
+	}
+	ret := zs[0]
+	for _, z := range zs[1:] {
+		if z.Cmp(ret) == -1 {
+			ret = z
+		}
+	}
+	return ret
+}
+
+var NInfinity = Z{infinity: -1}
+var PInfinity = Z{infinity: 1}
+var EmptyIntInterval = IntInterval{true, PInfinity, NInfinity}
+
+func InfinityFor(v ssa.Value) IntInterval {
+	if b, ok := v.Type().Underlying().(*types.Basic); ok {
+		if (b.Info() & types.IsUnsigned) != 0 {
+			return NewIntInterval(NewZ(0), PInfinity)
+		}
+	}
+	return NewIntInterval(NInfinity, PInfinity)
+}
+
+type IntInterval struct {
+	known bool
+	Lower Z
+	Upper Z
+}
+
+func NewIntInterval(l, u Z) IntInterval {
+	if u.Cmp(l) == -1 {
+		return EmptyIntInterval
+	}
+	return IntInterval{known: true, Lower: l, Upper: u}
+}
+
+func (i IntInterval) IsKnown() bool {
+	return i.known
+}
+
+func (i IntInterval) Empty() bool {
+	return i.Lower == PInfinity && i.Upper == NInfinity
+}
+
+func (i IntInterval) IsMaxRange() bool {
+	return i.Lower == NInfinity && i.Upper == PInfinity
+}
+
+func (i1 IntInterval) Intersection(i2 IntInterval) IntInterval {
+	if !i1.IsKnown() {
+		return i2
+	}
+	if !i2.IsKnown() {
+		return i1
+	}
+	if i1.Empty() || i2.Empty() {
+		return EmptyIntInterval
+	}
+	i3 := NewIntInterval(MaxZ(i1.Lower, i2.Lower), MinZ(i1.Upper, i2.Upper))
+	if i3.Lower.Cmp(i3.Upper) == 1 {
+		return EmptyIntInterval
+	}
+	return i3
+}
+
+func (i1 IntInterval) Union(other Range) Range {
+	i2, ok := other.(IntInterval)
+	if !ok {
+		i2 = EmptyIntInterval
+	}
+	if i1.Empty() || !i1.IsKnown() {
+		return i2
+	}
+	if i2.Empty() || !i2.IsKnown() {
+		return i1
+	}
+	return NewIntInterval(MinZ(i1.Lower, i2.Lower), MaxZ(i1.Upper, i2.Upper))
+}
+
+func (i1 IntInterval) Add(i2 IntInterval) IntInterval {
+	if i1.Empty() || i2.Empty() {
+		return EmptyIntInterval
+	}
+	l1, u1, l2, u2 := i1.Lower, i1.Upper, i2.Lower, i2.Upper
+	return NewIntInterval(l1.Add(l2), u1.Add(u2))
+}
+
+func (i1 IntInterval) Sub(i2 IntInterval) IntInterval {
+	if i1.Empty() || i2.Empty() {
+		return EmptyIntInterval
+	}
+	l1, u1, l2, u2 := i1.Lower, i1.Upper, i2.Lower, i2.Upper
+	return NewIntInterval(l1.Sub(u2), u1.Sub(l2))
+}
+
+func (i1 IntInterval) Mul(i2 IntInterval) IntInterval {
+	if i1.Empty() || i2.Empty() {
+		return EmptyIntInterval
+	}
+	x1, x2 := i1.Lower, i1.Upper
+	y1, y2 := i2.Lower, i2.Upper
+	return NewIntInterval(
+		MinZ(x1.Mul(y1), x1.Mul(y2), x2.Mul(y1), x2.Mul(y2)),
+		MaxZ(x1.Mul(y1), x1.Mul(y2), x2.Mul(y1), x2.Mul(y2)),
+	)
+}
+
+func (i1 IntInterval) String() string {
+	if !i1.IsKnown() {
+		return "[⊥, ⊥]"
+	}
+	if i1.Empty() {
+		return "{}"
+	}
+	return fmt.Sprintf("[%s, %s]", i1.Lower, i1.Upper)
+}
+
+type IntArithmeticConstraint struct {
+	aConstraint
+	A  ssa.Value
+	B  ssa.Value
+	Op token.Token
+	Fn func(IntInterval, IntInterval) IntInterval
+}
+
+type IntAddConstraint struct{ *IntArithmeticConstraint }
+type IntSubConstraint struct{ *IntArithmeticConstraint }
+type IntMulConstraint struct{ *IntArithmeticConstraint }
+
+type IntConversionConstraint struct {
+	aConstraint
+	X ssa.Value
+}
+
+type IntIntersectionConstraint struct {
+	aConstraint
+	ranges   Ranges
+	A        ssa.Value
+	B        ssa.Value
+	Op       token.Token
+	I        IntInterval
+	resolved bool
+}
+
+type IntIntervalConstraint struct {
+	aConstraint
+	I IntInterval
+}
+
+func NewIntArithmeticConstraint(a, b, y ssa.Value, op token.Token, fn func(IntInterval, IntInterval) IntInterval) *IntArithmeticConstraint {
+	return &IntArithmeticConstraint{NewConstraint(y), a, b, op, fn}
+}
+func NewIntAddConstraint(a, b, y ssa.Value) Constraint {
+	return &IntAddConstraint{NewIntArithmeticConstraint(a, b, y, token.ADD, IntInterval.Add)}
+}
+func NewIntSubConstraint(a, b, y ssa.Value) Constraint {
+	return &IntSubConstraint{NewIntArithmeticConstraint(a, b, y, token.SUB, IntInterval.Sub)}
+}
+func NewIntMulConstraint(a, b, y ssa.Value) Constraint {
+	return &IntMulConstraint{NewIntArithmeticConstraint(a, b, y, token.MUL, IntInterval.Mul)}
+}
+func NewIntConversionConstraint(x, y ssa.Value) Constraint {
+	return &IntConversionConstraint{NewConstraint(y), x}
+}
+func NewIntIntersectionConstraint(a, b ssa.Value, op token.Token, ranges Ranges, y ssa.Value) Constraint {
+	return &IntIntersectionConstraint{
+		aConstraint: NewConstraint(y),
+		ranges:      ranges,
+		A:           a,
+		B:           b,
+		Op:          op,
+	}
+}
+func NewIntIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
+	return &IntIntervalConstraint{NewConstraint(y), i}
+}
+
+func (c *IntArithmeticConstraint) Operands() []ssa.Value   { return []ssa.Value{c.A, c.B} }
+func (c *IntConversionConstraint) Operands() []ssa.Value   { return []ssa.Value{c.X} }
+func (c *IntIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.A} }
+func (s *IntIntervalConstraint) Operands() []ssa.Value     { return nil }
+
+func (c *IntArithmeticConstraint) String() string {
+	return fmt.Sprintf("%s = %s %s %s", c.Y().Name(), c.A.Name(), c.Op, c.B.Name())
+}
+func (c *IntConversionConstraint) String() string {
+	return fmt.Sprintf("%s = %s(%s)", c.Y().Name(), c.Y().Type(), c.X.Name())
+}
+func (c *IntIntersectionConstraint) String() string {
+	return fmt.Sprintf("%s = %s %s %s (%t branch)", c.Y().Name(), c.A.Name(), c.Op, c.B.Name(), c.Y().(*ssa.Sigma).Branch)
+}
+func (c *IntIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
+
+func (c *IntArithmeticConstraint) Eval(g *Graph) Range {
+	i1, i2 := g.Range(c.A).(IntInterval), g.Range(c.B).(IntInterval)
+	if !i1.IsKnown() || !i2.IsKnown() {
+		return IntInterval{}
+	}
+	return c.Fn(i1, i2)
+}
+func (c *IntConversionConstraint) Eval(g *Graph) Range {
+	s := &types.StdSizes{
+		// XXX is it okay to assume the largest word size, or do we
+		// need to be platform specific?
+		WordSize: 8,
+		MaxAlign: 1,
+	}
+	fromI := g.Range(c.X).(IntInterval)
+	toI := g.Range(c.Y()).(IntInterval)
+	fromT := c.X.Type().Underlying().(*types.Basic)
+	toT := c.Y().Type().Underlying().(*types.Basic)
+	fromB := s.Sizeof(c.X.Type())
+	toB := s.Sizeof(c.Y().Type())
+
+	if !fromI.IsKnown() {
+		return toI
+	}
+	if !toI.IsKnown() {
+		return fromI
+	}
+
+	// uint<N> -> sint/uint<M>, M > N: [max(0, l1), min(2**N-1, u2)]
+	if (fromT.Info()&types.IsUnsigned != 0) &&
+		toB > fromB {
+
+		n := big.NewInt(1)
+		n.Lsh(n, uint(fromB*8))
+		n.Sub(n, big.NewInt(1))
+		return NewIntInterval(
+			MaxZ(NewZ(0), fromI.Lower),
+			MinZ(NewBigZ(n), toI.Upper),
+		)
+	}
+
+	// sint<N> -> sint<M>, M > N; [max(-∞, l1), min(2**N-1, u2)]
+	if (fromT.Info()&types.IsUnsigned == 0) &&
+		(toT.Info()&types.IsUnsigned == 0) &&
+		toB > fromB {
+
+		n := big.NewInt(1)
+		n.Lsh(n, uint(fromB*8))
+		n.Sub(n, big.NewInt(1))
+		return NewIntInterval(
+			MaxZ(NInfinity, fromI.Lower),
+			MinZ(NewBigZ(n), toI.Upper),
+		)
+	}
+
+	return fromI
+}
+func (c *IntIntersectionConstraint) Eval(g *Graph) Range {
+	xi := g.Range(c.A).(IntInterval)
+	if !xi.IsKnown() {
+		return c.I
+	}
+	return xi.Intersection(c.I)
+}
+func (c *IntIntervalConstraint) Eval(*Graph) Range { return c.I }
+
+func (c *IntIntersectionConstraint) Futures() []ssa.Value {
+	return []ssa.Value{c.B}
+}
+
+func (c *IntIntersectionConstraint) Resolve() {
+	r, ok := c.ranges[c.B].(IntInterval)
+	if !ok {
+		c.I = InfinityFor(c.Y())
+		return
+	}
+
+	switch c.Op {
+	case token.EQL:
+		c.I = r
+	case token.GTR:
+		c.I = NewIntInterval(r.Lower.Add(NewZ(1)), PInfinity)
+	case token.GEQ:
+		c.I = NewIntInterval(r.Lower, PInfinity)
+	case token.LSS:
+		// TODO(dh): do we need 0 instead of NInfinity for uints?
+		c.I = NewIntInterval(NInfinity, r.Upper.Sub(NewZ(1)))
+	case token.LEQ:
+		c.I = NewIntInterval(NInfinity, r.Upper)
+	case token.NEQ:
+		c.I = InfinityFor(c.Y())
+	default:
+		panic("unsupported op " + c.Op.String())
+	}
+}
+
+func (c *IntIntersectionConstraint) IsKnown() bool {
+	return c.I.IsKnown()
+}
+
+func (c *IntIntersectionConstraint) MarkUnresolved() {
+	c.resolved = false
+}
+
+func (c *IntIntersectionConstraint) MarkResolved() {
+	c.resolved = true
+}
+
+func (c *IntIntersectionConstraint) IsResolved() bool {
+	return c.resolved
+}
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/slice.go b/vendor/honnef.co/go/tools/staticcheck/vrp/slice.go
new file mode 100644
index 0000000..40658dd
--- /dev/null
+++ b/vendor/honnef.co/go/tools/staticcheck/vrp/slice.go
@@ -0,0 +1,273 @@
+package vrp
+
+// TODO(dh): most of the constraints have implementations identical to
+// that of strings. Consider reusing them.
+
+import (
+	"fmt"
+	"go/types"
+
+	"honnef.co/go/tools/ssa"
+)
+
+type SliceInterval struct {
+	Length IntInterval
+}
+
+func (s SliceInterval) Union(other Range) Range {
+	i, ok := other.(SliceInterval)
+	if !ok {
+		i = SliceInterval{EmptyIntInterval}
+	}
+	if s.Length.Empty() || !s.Length.IsKnown() {
+		return i
+	}
+	if i.Length.Empty() || !i.Length.IsKnown() {
+		return s
+	}
+	return SliceInterval{
+		Length: s.Length.Union(i.Length).(IntInterval),
+	}
+}
+func (s SliceInterval) String() string { return s.Length.String() }
+func (s SliceInterval) IsKnown() bool  { return s.Length.IsKnown() }
+
+type SliceAppendConstraint struct {
+	aConstraint
+	A ssa.Value
+	B ssa.Value
+}
+
+type SliceSliceConstraint struct {
+	aConstraint
+	X     ssa.Value
+	Lower ssa.Value
+	Upper ssa.Value
+}
+
+type ArraySliceConstraint struct {
+	aConstraint
+	X     ssa.Value
+	Lower ssa.Value
+	Upper ssa.Value
+}
+
+type SliceIntersectionConstraint struct {
+	aConstraint
+	X ssa.Value
+	I IntInterval
+}
+
+type SliceLengthConstraint struct {
+	aConstraint
+	X ssa.Value
+}
+
+type MakeSliceConstraint struct {
+	aConstraint
+	Size ssa.Value
+}
+
+type SliceIntervalConstraint struct {
+	aConstraint
+	I IntInterval
+}
+
+func NewSliceAppendConstraint(a, b, y ssa.Value) Constraint {
+	return &SliceAppendConstraint{NewConstraint(y), a, b}
+}
+func NewSliceSliceConstraint(x, lower, upper, y ssa.Value) Constraint {
+	return &SliceSliceConstraint{NewConstraint(y), x, lower, upper}
+}
+func NewArraySliceConstraint(x, lower, upper, y ssa.Value) Constraint {
+	return &ArraySliceConstraint{NewConstraint(y), x, lower, upper}
+}
+func NewSliceIntersectionConstraint(x ssa.Value, i IntInterval, y ssa.Value) Constraint {
+	return &SliceIntersectionConstraint{NewConstraint(y), x, i}
+}
+func NewSliceLengthConstraint(x, y ssa.Value) Constraint {
+	return &SliceLengthConstraint{NewConstraint(y), x}
+}
+func NewMakeSliceConstraint(size, y ssa.Value) Constraint {
+	return &MakeSliceConstraint{NewConstraint(y), size}
+}
+func NewSliceIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
+	return &SliceIntervalConstraint{NewConstraint(y), i}
+}
+
+func (c *SliceAppendConstraint) Operands() []ssa.Value { return []ssa.Value{c.A, c.B} }
+func (c *SliceSliceConstraint) Operands() []ssa.Value {
+	ops := []ssa.Value{c.X}
+	if c.Lower != nil {
+		ops = append(ops, c.Lower)
+	}
+	if c.Upper != nil {
+		ops = append(ops, c.Upper)
+	}
+	return ops
+}
+func (c *ArraySliceConstraint) Operands() []ssa.Value {
+	ops := []ssa.Value{c.X}
+	if c.Lower != nil {
+		ops = append(ops, c.Lower)
+	}
+	if c.Upper != nil {
+		ops = append(ops, c.Upper)
+	}
+	return ops
+}
+func (c *SliceIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
+func (c *SliceLengthConstraint) Operands() []ssa.Value       { return []ssa.Value{c.X} }
+func (c *MakeSliceConstraint) Operands() []ssa.Value         { return []ssa.Value{c.Size} }
+func (s *SliceIntervalConstraint) Operands() []ssa.Value     { return nil }
+
+func (c *SliceAppendConstraint) String() string {
+	return fmt.Sprintf("%s = append(%s, %s)", c.Y().Name(), c.A.Name(), c.B.Name())
+}
+func (c *SliceSliceConstraint) String() string {
+	var lname, uname string
+	if c.Lower != nil {
+		lname = c.Lower.Name()
+	}
+	if c.Upper != nil {
+		uname = c.Upper.Name()
+	}
+	return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
+}
+func (c *ArraySliceConstraint) String() string {
+	var lname, uname string
+	if c.Lower != nil {
+		lname = c.Lower.Name()
+	}
+	if c.Upper != nil {
+		uname = c.Upper.Name()
+	}
+	return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
+}
+func (c *SliceIntersectionConstraint) String() string {
+	return fmt.Sprintf("%s = %s.%t ⊓ %s", c.Y().Name(), c.X.Name(), c.Y().(*ssa.Sigma).Branch, c.I)
+}
+func (c *SliceLengthConstraint) String() string {
+	return fmt.Sprintf("%s = len(%s)", c.Y().Name(), c.X.Name())
+}
+func (c *MakeSliceConstraint) String() string {
+	return fmt.Sprintf("%s = make(slice, %s)", c.Y().Name(), c.Size.Name())
+}
+func (c *SliceIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
+
+func (c *SliceAppendConstraint) Eval(g *Graph) Range {
+	l1 := g.Range(c.A).(SliceInterval).Length
+	var l2 IntInterval
+	switch r := g.Range(c.B).(type) {
+	case SliceInterval:
+		l2 = r.Length
+	case StringInterval:
+		l2 = r.Length
+	default:
+		return SliceInterval{}
+	}
+	if !l1.IsKnown() || !l2.IsKnown() {
+		return SliceInterval{}
+	}
+	return SliceInterval{
+		Length: l1.Add(l2),
+	}
+}
+func (c *SliceSliceConstraint) Eval(g *Graph) Range {
+	lr := NewIntInterval(NewZ(0), NewZ(0))
+	if c.Lower != nil {
+		lr = g.Range(c.Lower).(IntInterval)
+	}
+	ur := g.Range(c.X).(SliceInterval).Length
+	if c.Upper != nil {
+		ur = g.Range(c.Upper).(IntInterval)
+	}
+	if !lr.IsKnown() || !ur.IsKnown() {
+		return SliceInterval{}
+	}
+
+	ls := []Z{
+		ur.Lower.Sub(lr.Lower),
+		ur.Upper.Sub(lr.Lower),
+		ur.Lower.Sub(lr.Upper),
+		ur.Upper.Sub(lr.Upper),
+	}
+	// TODO(dh): if we don't truncate lengths to 0 we might be able to
+	// easily detect slices with high < low. we'd need to treat -∞
+	// specially, though.
+	for i, l := range ls {
+		if l.Sign() == -1 {
+			ls[i] = NewZ(0)
+		}
+	}
+
+	return SliceInterval{
+		Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
+	}
+}
+func (c *ArraySliceConstraint) Eval(g *Graph) Range {
+	lr := NewIntInterval(NewZ(0), NewZ(0))
+	if c.Lower != nil {
+		lr = g.Range(c.Lower).(IntInterval)
+	}
+	var l int64
+	switch typ := c.X.Type().(type) {
+	case *types.Array:
+		l = typ.Len()
+	case *types.Pointer:
+		l = typ.Elem().(*types.Array).Len()
+	}
+	ur := NewIntInterval(NewZ(l), NewZ(l))
+	if c.Upper != nil {
+		ur = g.Range(c.Upper).(IntInterval)
+	}
+	if !lr.IsKnown() || !ur.IsKnown() {
+		return SliceInterval{}
+	}
+
+	ls := []Z{
+		ur.Lower.Sub(lr.Lower),
+		ur.Upper.Sub(lr.Lower),
+		ur.Lower.Sub(lr.Upper),
+		ur.Upper.Sub(lr.Upper),
+	}
+	// TODO(dh): if we don't truncate lengths to 0 we might be able to
+	// easily detect slices with high < low. we'd need to treat -∞
+	// specially, though.
+	for i, l := range ls {
+		if l.Sign() == -1 {
+			ls[i] = NewZ(0)
+		}
+	}
+
+	return SliceInterval{
+		Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
+	}
+}
+func (c *SliceIntersectionConstraint) Eval(g *Graph) Range {
+	xi := g.Range(c.X).(SliceInterval)
+	if !xi.IsKnown() {
+		return c.I
+	}
+	return SliceInterval{
+		Length: xi.Length.Intersection(c.I),
+	}
+}
+func (c *SliceLengthConstraint) Eval(g *Graph) Range {
+	i := g.Range(c.X).(SliceInterval).Length
+	if !i.IsKnown() {
+		return NewIntInterval(NewZ(0), PInfinity)
+	}
+	return i
+}
+func (c *MakeSliceConstraint) Eval(g *Graph) Range {
+	i, ok := g.Range(c.Size).(IntInterval)
+	if !ok {
+		return SliceInterval{NewIntInterval(NewZ(0), PInfinity)}
+	}
+	if i.Lower.Sign() == -1 {
+		i.Lower = NewZ(0)
+	}
+	return SliceInterval{i}
+}
+func (c *SliceIntervalConstraint) Eval(*Graph) Range { return SliceInterval{c.I} }
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/string.go b/vendor/honnef.co/go/tools/staticcheck/vrp/string.go
new file mode 100644
index 0000000..e05877f
--- /dev/null
+++ b/vendor/honnef.co/go/tools/staticcheck/vrp/string.go
@@ -0,0 +1,258 @@
+package vrp
+
+import (
+	"fmt"
+	"go/token"
+	"go/types"
+
+	"honnef.co/go/tools/ssa"
+)
+
+type StringInterval struct {
+	Length IntInterval
+}
+
+func (s StringInterval) Union(other Range) Range {
+	i, ok := other.(StringInterval)
+	if !ok {
+		i = StringInterval{EmptyIntInterval}
+	}
+	if s.Length.Empty() || !s.Length.IsKnown() {
+		return i
+	}
+	if i.Length.Empty() || !i.Length.IsKnown() {
+		return s
+	}
+	return StringInterval{
+		Length: s.Length.Union(i.Length).(IntInterval),
+	}
+}
+
+func (s StringInterval) String() string {
+	return s.Length.String()
+}
+
+func (s StringInterval) IsKnown() bool {
+	return s.Length.IsKnown()
+}
+
+type StringSliceConstraint struct {
+	aConstraint
+	X     ssa.Value
+	Lower ssa.Value
+	Upper ssa.Value
+}
+
+type StringIntersectionConstraint struct {
+	aConstraint
+	ranges   Ranges
+	A        ssa.Value
+	B        ssa.Value
+	Op       token.Token
+	I        IntInterval
+	resolved bool
+}
+
+type StringConcatConstraint struct {
+	aConstraint
+	A ssa.Value
+	B ssa.Value
+}
+
+type StringLengthConstraint struct {
+	aConstraint
+	X ssa.Value
+}
+
+type StringIntervalConstraint struct {
+	aConstraint
+	I IntInterval
+}
+
+func NewStringSliceConstraint(x, lower, upper, y ssa.Value) Constraint {
+	return &StringSliceConstraint{NewConstraint(y), x, lower, upper}
+}
+func NewStringIntersectionConstraint(a, b ssa.Value, op token.Token, ranges Ranges, y ssa.Value) Constraint {
+	return &StringIntersectionConstraint{
+		aConstraint: NewConstraint(y),
+		ranges:      ranges,
+		A:           a,
+		B:           b,
+		Op:          op,
+	}
+}
+func NewStringConcatConstraint(a, b, y ssa.Value) Constraint {
+	return &StringConcatConstraint{NewConstraint(y), a, b}
+}
+func NewStringLengthConstraint(x ssa.Value, y ssa.Value) Constraint {
+	return &StringLengthConstraint{NewConstraint(y), x}
+}
+func NewStringIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
+	return &StringIntervalConstraint{NewConstraint(y), i}
+}
+
+func (c *StringSliceConstraint) Operands() []ssa.Value {
+	vs := []ssa.Value{c.X}
+	if c.Lower != nil {
+		vs = append(vs, c.Lower)
+	}
+	if c.Upper != nil {
+		vs = append(vs, c.Upper)
+	}
+	return vs
+}
+func (c *StringIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.A} }
+func (c StringConcatConstraint) Operands() []ssa.Value        { return []ssa.Value{c.A, c.B} }
+func (c *StringLengthConstraint) Operands() []ssa.Value       { return []ssa.Value{c.X} }
+func (s *StringIntervalConstraint) Operands() []ssa.Value     { return nil }
+
+func (c *StringSliceConstraint) String() string {
+	var lname, uname string
+	if c.Lower != nil {
+		lname = c.Lower.Name()
+	}
+	if c.Upper != nil {
+		uname = c.Upper.Name()
+	}
+	return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
+}
+func (c *StringIntersectionConstraint) String() string {
+	return fmt.Sprintf("%s = %s %s %s (%t branch)", c.Y().Name(), c.A.Name(), c.Op, c.B.Name(), c.Y().(*ssa.Sigma).Branch)
+}
+func (c StringConcatConstraint) String() string {
+	return fmt.Sprintf("%s = %s + %s", c.Y().Name(), c.A.Name(), c.B.Name())
+}
+func (c *StringLengthConstraint) String() string {
+	return fmt.Sprintf("%s = len(%s)", c.Y().Name(), c.X.Name())
+}
+func (c *StringIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
+
+func (c *StringSliceConstraint) Eval(g *Graph) Range {
+	lr := NewIntInterval(NewZ(0), NewZ(0))
+	if c.Lower != nil {
+		lr = g.Range(c.Lower).(IntInterval)
+	}
+	ur := g.Range(c.X).(StringInterval).Length
+	if c.Upper != nil {
+		ur = g.Range(c.Upper).(IntInterval)
+	}
+	if !lr.IsKnown() || !ur.IsKnown() {
+		return StringInterval{}
+	}
+
+	ls := []Z{
+		ur.Lower.Sub(lr.Lower),
+		ur.Upper.Sub(lr.Lower),
+		ur.Lower.Sub(lr.Upper),
+		ur.Upper.Sub(lr.Upper),
+	}
+	// TODO(dh): if we don't truncate lengths to 0 we might be able to
+	// easily detect slices with high < low. we'd need to treat -∞
+	// specially, though.
+	for i, l := range ls {
+		if l.Sign() == -1 {
+			ls[i] = NewZ(0)
+		}
+	}
+
+	return StringInterval{
+		Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
+	}
+}
+func (c *StringIntersectionConstraint) Eval(g *Graph) Range {
+	var l IntInterval
+	switch r := g.Range(c.A).(type) {
+	case StringInterval:
+		l = r.Length
+	case IntInterval:
+		l = r
+	}
+
+	if !l.IsKnown() {
+		return StringInterval{c.I}
+	}
+	return StringInterval{
+		Length: l.Intersection(c.I),
+	}
+}
+func (c StringConcatConstraint) Eval(g *Graph) Range {
+	i1, i2 := g.Range(c.A).(StringInterval), g.Range(c.B).(StringInterval)
+	if !i1.Length.IsKnown() || !i2.Length.IsKnown() {
+		return StringInterval{}
+	}
+	return StringInterval{
+		Length: i1.Length.Add(i2.Length),
+	}
+}
+func (c *StringLengthConstraint) Eval(g *Graph) Range {
+	i := g.Range(c.X).(StringInterval).Length
+	if !i.IsKnown() {
+		return NewIntInterval(NewZ(0), PInfinity)
+	}
+	return i
+}
+func (c *StringIntervalConstraint) Eval(*Graph) Range { return StringInterval{c.I} }
+
+func (c *StringIntersectionConstraint) Futures() []ssa.Value {
+	return []ssa.Value{c.B}
+}
+
+func (c *StringIntersectionConstraint) Resolve() {
+	if (c.A.Type().Underlying().(*types.Basic).Info() & types.IsString) != 0 {
+		// comparing two strings
+		r, ok := c.ranges[c.B].(StringInterval)
+		if !ok {
+			c.I = NewIntInterval(NewZ(0), PInfinity)
+			return
+		}
+		switch c.Op {
+		case token.EQL:
+			c.I = r.Length
+		case token.GTR, token.GEQ:
+			c.I = NewIntInterval(r.Length.Lower, PInfinity)
+		case token.LSS, token.LEQ:
+			c.I = NewIntInterval(NewZ(0), r.Length.Upper)
+		case token.NEQ:
+		default:
+			panic("unsupported op " + c.Op.String())
+		}
+	} else {
+		r, ok := c.ranges[c.B].(IntInterval)
+		if !ok {
+			c.I = NewIntInterval(NewZ(0), PInfinity)
+			return
+		}
+		// comparing two lengths
+		switch c.Op {
+		case token.EQL:
+			c.I = r
+		case token.GTR:
+			c.I = NewIntInterval(r.Lower.Add(NewZ(1)), PInfinity)
+		case token.GEQ:
+			c.I = NewIntInterval(r.Lower, PInfinity)
+		case token.LSS:
+			c.I = NewIntInterval(NInfinity, r.Upper.Sub(NewZ(1)))
+		case token.LEQ:
+			c.I = NewIntInterval(NInfinity, r.Upper)
+		case token.NEQ:
+		default:
+			panic("unsupported op " + c.Op.String())
+		}
+	}
+}
+
+func (c *StringIntersectionConstraint) IsKnown() bool {
+	return c.I.IsKnown()
+}
+
+func (c *StringIntersectionConstraint) MarkUnresolved() {
+	c.resolved = false
+}
+
+func (c *StringIntersectionConstraint) MarkResolved() {
+	c.resolved = true
+}
+
+func (c *StringIntersectionConstraint) IsResolved() bool {
+	return c.resolved
+}
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go b/vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go
new file mode 100644
index 0000000..cb17f04
--- /dev/null
+++ b/vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go
@@ -0,0 +1,1049 @@
+package vrp
+
+// TODO(dh) widening and narrowing have a lot of code in common. Make
+// it reusable.
+
+import (
+	"fmt"
+	"go/constant"
+	"go/token"
+	"go/types"
+	"math/big"
+	"sort"
+	"strings"
+
+	"honnef.co/go/tools/ssa"
+)
+
+type Future interface {
+	Constraint
+	Futures() []ssa.Value
+	Resolve()
+	IsKnown() bool
+	MarkUnresolved()
+	MarkResolved()
+	IsResolved() bool
+}
+
+type Range interface {
+	Union(other Range) Range
+	IsKnown() bool
+}
+
+type Constraint interface {
+	Y() ssa.Value
+	isConstraint()
+	String() string
+	Eval(*Graph) Range
+	Operands() []ssa.Value
+}
+
+type aConstraint struct {
+	y ssa.Value
+}
+
+func NewConstraint(y ssa.Value) aConstraint {
+	return aConstraint{y}
+}
+
+func (aConstraint) isConstraint()  {}
+func (c aConstraint) Y() ssa.Value { return c.y }
+
+type PhiConstraint struct {
+	aConstraint
+	Vars []ssa.Value
+}
+
+func NewPhiConstraint(vars []ssa.Value, y ssa.Value) Constraint {
+	uniqm := map[ssa.Value]struct{}{}
+	for _, v := range vars {
+		uniqm[v] = struct{}{}
+	}
+	var uniq []ssa.Value
+	for v := range uniqm {
+		uniq = append(uniq, v)
+	}
+	return &PhiConstraint{
+		aConstraint: NewConstraint(y),
+		Vars:        uniq,
+	}
+}
+
+func (c *PhiConstraint) Operands() []ssa.Value {
+	return c.Vars
+}
+
+func (c *PhiConstraint) Eval(g *Graph) Range {
+	i := Range(nil)
+	for _, v := range c.Vars {
+		i = g.Range(v).Union(i)
+	}
+	return i
+}
+
+func (c *PhiConstraint) String() string {
+	names := make([]string, len(c.Vars))
+	for i, v := range c.Vars {
+		names[i] = v.Name()
+	}
+	return fmt.Sprintf("%s = φ(%s)", c.Y().Name(), strings.Join(names, ", "))
+}
+
+func isSupportedType(typ types.Type) bool {
+	switch typ := typ.Underlying().(type) {
+	case *types.Basic:
+		switch typ.Kind() {
+		case types.String, types.UntypedString:
+			return true
+		default:
+			if (typ.Info() & types.IsInteger) == 0 {
+				return false
+			}
+		}
+	case *types.Chan:
+		return true
+	case *types.Slice:
+		return true
+	default:
+		return false
+	}
+	return true
+}
+
+func ConstantToZ(c constant.Value) Z {
+	s := constant.ToInt(c).ExactString()
+	n := &big.Int{}
+	n.SetString(s, 10)
+	return NewBigZ(n)
+}
+
+func sigmaInteger(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
+	op := cond.Op
+	if !ins.Branch {
+		op = (invertToken(op))
+	}
+
+	switch op {
+	case token.EQL, token.GTR, token.GEQ, token.LSS, token.LEQ:
+	default:
+		return nil
+	}
+	var a, b ssa.Value
+	if (*ops[0]) == ins.X {
+		a = *ops[0]
+		b = *ops[1]
+	} else {
+		a = *ops[1]
+		b = *ops[0]
+		op = flipToken(op)
+	}
+	return NewIntIntersectionConstraint(a, b, op, g.ranges, ins)
+}
+
+func sigmaString(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
+	op := cond.Op
+	if !ins.Branch {
+		op = (invertToken(op))
+	}
+
+	switch op {
+	case token.EQL, token.GTR, token.GEQ, token.LSS, token.LEQ:
+	default:
+		return nil
+	}
+
+	if ((*ops[0]).Type().Underlying().(*types.Basic).Info() & types.IsString) == 0 {
+		var a, b ssa.Value
+		call, ok := (*ops[0]).(*ssa.Call)
+		if ok && call.Common().Args[0] == ins.X {
+			a = *ops[0]
+			b = *ops[1]
+		} else {
+			a = *ops[1]
+			b = *ops[0]
+			op = flipToken(op)
+		}
+		return NewStringIntersectionConstraint(a, b, op, g.ranges, ins)
+	}
+	var a, b ssa.Value
+	if (*ops[0]) == ins.X {
+		a = *ops[0]
+		b = *ops[1]
+	} else {
+		a = *ops[1]
+		b = *ops[0]
+		op = flipToken(op)
+	}
+	return NewStringIntersectionConstraint(a, b, op, g.ranges, ins)
+}
+
+func sigmaSlice(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
+	// TODO(dh) sigmaSlice and sigmaString are a lot alike. Can they
+	// be merged?
+	//
+	// XXX support futures
+
+	op := cond.Op
+	if !ins.Branch {
+		op = (invertToken(op))
+	}
+
+	k, ok := (*ops[1]).(*ssa.Const)
+	// XXX investigate in what cases this wouldn't be a Const
+	//
+	// XXX what if left and right are swapped?
+	if !ok {
+		return nil
+	}
+
+	call, ok := (*ops[0]).(*ssa.Call)
+	if !ok {
+		return nil
+	}
+	builtin, ok := call.Common().Value.(*ssa.Builtin)
+	if !ok {
+		return nil
+	}
+	if builtin.Name() != "len" {
+		return nil
+	}
+	callops := call.Operands(nil)
+
+	v := ConstantToZ(k.Value)
+	c := NewSliceIntersectionConstraint(*callops[1], IntInterval{}, ins).(*SliceIntersectionConstraint)
+	switch op {
+	case token.EQL:
+		c.I = NewIntInterval(v, v)
+	case token.GTR, token.GEQ:
+		off := int64(0)
+		if cond.Op == token.GTR {
+			off = 1
+		}
+		c.I = NewIntInterval(
+			v.Add(NewZ(off)),
+			PInfinity,
+		)
+	case token.LSS, token.LEQ:
+		off := int64(0)
+		if cond.Op == token.LSS {
+			off = -1
+		}
+		c.I = NewIntInterval(
+			NInfinity,
+			v.Add(NewZ(off)),
+		)
+	default:
+		return nil
+	}
+	return c
+}
+
+func BuildGraph(f *ssa.Function) *Graph {
+	g := &Graph{
+		Vertices: map[interface{}]*Vertex{},
+		ranges:   Ranges{},
+	}
+
+	var cs []Constraint
+
+	ops := make([]*ssa.Value, 16)
+	seen := map[ssa.Value]bool{}
+	for _, block := range f.Blocks {
+		for _, ins := range block.Instrs {
+			ops = ins.Operands(ops[:0])
+			for _, op := range ops {
+				if c, ok := (*op).(*ssa.Const); ok {
+					if seen[c] {
+						continue
+					}
+					seen[c] = true
+					if c.Value == nil {
+						switch c.Type().Underlying().(type) {
+						case *types.Slice:
+							cs = append(cs, NewSliceIntervalConstraint(NewIntInterval(NewZ(0), NewZ(0)), c))
+						}
+						continue
+					}
+					switch c.Value.Kind() {
+					case constant.Int:
+						v := ConstantToZ(c.Value)
+						cs = append(cs, NewIntIntervalConstraint(NewIntInterval(v, v), c))
+					case constant.String:
+						s := constant.StringVal(c.Value)
+						n := NewZ(int64(len(s)))
+						cs = append(cs, NewStringIntervalConstraint(NewIntInterval(n, n), c))
+					}
+				}
+			}
+		}
+	}
+	for _, block := range f.Blocks {
+		for _, ins := range block.Instrs {
+			switch ins := ins.(type) {
+			case *ssa.Convert:
+				switch v := ins.Type().Underlying().(type) {
+				case *types.Basic:
+					if (v.Info() & types.IsInteger) == 0 {
+						continue
+					}
+					cs = append(cs, NewIntConversionConstraint(ins.X, ins))
+				}
+			case *ssa.Call:
+				if static := ins.Common().StaticCallee(); static != nil {
+					if fn, ok := static.Object().(*types.Func); ok {
+						switch fn.FullName() {
+						case "bytes.Index", "bytes.IndexAny", "bytes.IndexByte",
+							"bytes.IndexFunc", "bytes.IndexRune", "bytes.LastIndex",
+							"bytes.LastIndexAny", "bytes.LastIndexByte", "bytes.LastIndexFunc",
+							"strings.Index", "strings.IndexAny", "strings.IndexByte",
+							"strings.IndexFunc", "strings.IndexRune", "strings.LastIndex",
+							"strings.LastIndexAny", "strings.LastIndexByte", "strings.LastIndexFunc":
+							// TODO(dh): instead of limiting by +∞,
+							// limit by the upper bound of the passed
+							// string
+							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(-1), PInfinity), ins))
+						case "bytes.Title", "bytes.ToLower", "bytes.ToTitle", "bytes.ToUpper",
+							"strings.Title", "strings.ToLower", "strings.ToTitle", "strings.ToUpper":
+							cs = append(cs, NewCopyConstraint(ins.Common().Args[0], ins))
+						case "bytes.ToLowerSpecial", "bytes.ToTitleSpecial", "bytes.ToUpperSpecial",
+							"strings.ToLowerSpecial", "strings.ToTitleSpecial", "strings.ToUpperSpecial":
+							cs = append(cs, NewCopyConstraint(ins.Common().Args[1], ins))
+						case "bytes.Compare", "strings.Compare":
+							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(-1), NewZ(1)), ins))
+						case "bytes.Count", "strings.Count":
+							// TODO(dh): instead of limiting by +∞,
+							// limit by the upper bound of the passed
+							// string.
+							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(0), PInfinity), ins))
+						case "bytes.Map", "bytes.TrimFunc", "bytes.TrimLeft", "bytes.TrimLeftFunc",
+							"bytes.TrimRight", "bytes.TrimRightFunc", "bytes.TrimSpace",
+							"strings.Map", "strings.TrimFunc", "strings.TrimLeft", "strings.TrimLeftFunc",
+							"strings.TrimRight", "strings.TrimRightFunc", "strings.TrimSpace":
+							// TODO(dh): lower = 0, upper = upper of passed string
+						case "bytes.TrimPrefix", "bytes.TrimSuffix",
+							"strings.TrimPrefix", "strings.TrimSuffix":
+							// TODO(dh) range between "unmodified" and len(cutset) removed
+						case "(*bytes.Buffer).Cap", "(*bytes.Buffer).Len", "(*bytes.Reader).Len", "(*bytes.Reader).Size":
+							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(0), PInfinity), ins))
+						}
+					}
+				}
+				builtin, ok := ins.Common().Value.(*ssa.Builtin)
+				ops := ins.Operands(nil)
+				if !ok {
+					continue
+				}
+				switch builtin.Name() {
+				case "len":
+					switch op1 := (*ops[1]).Type().Underlying().(type) {
+					case *types.Basic:
+						if op1.Kind() == types.String || op1.Kind() == types.UntypedString {
+							cs = append(cs, NewStringLengthConstraint(*ops[1], ins))
+						}
+					case *types.Slice:
+						cs = append(cs, NewSliceLengthConstraint(*ops[1], ins))
+					}
+
+				case "append":
+					cs = append(cs, NewSliceAppendConstraint(ins.Common().Args[0], ins.Common().Args[1], ins))
+				}
+			case *ssa.BinOp:
+				ops := ins.Operands(nil)
+				basic, ok := (*ops[0]).Type().Underlying().(*types.Basic)
+				if !ok {
+					continue
+				}
+				switch basic.Kind() {
+				case types.Int, types.Int8, types.Int16, types.Int32, types.Int64,
+					types.Uint, types.Uint8, types.Uint16, types.Uint32, types.Uint64, types.UntypedInt:
+					fns := map[token.Token]func(ssa.Value, ssa.Value, ssa.Value) Constraint{
+						token.ADD: NewIntAddConstraint,
+						token.SUB: NewIntSubConstraint,
+						token.MUL: NewIntMulConstraint,
+						// XXX support QUO, REM, SHL, SHR
+					}
+					fn, ok := fns[ins.Op]
+					if ok {
+						cs = append(cs, fn(*ops[0], *ops[1], ins))
+					}
+				case types.String, types.UntypedString:
+					if ins.Op == token.ADD {
+						cs = append(cs, NewStringConcatConstraint(*ops[0], *ops[1], ins))
+					}
+				}
+			case *ssa.Slice:
+				typ := ins.X.Type().Underlying()
+				switch typ := typ.(type) {
+				case *types.Basic:
+					cs = append(cs, NewStringSliceConstraint(ins.X, ins.Low, ins.High, ins))
+				case *types.Slice:
+					cs = append(cs, NewSliceSliceConstraint(ins.X, ins.Low, ins.High, ins))
+				case *types.Array:
+					cs = append(cs, NewArraySliceConstraint(ins.X, ins.Low, ins.High, ins))
+				case *types.Pointer:
+					if _, ok := typ.Elem().(*types.Array); !ok {
+						continue
+					}
+					cs = append(cs, NewArraySliceConstraint(ins.X, ins.Low, ins.High, ins))
+				}
+			case *ssa.Phi:
+				if !isSupportedType(ins.Type()) {
+					continue
+				}
+				ops := ins.Operands(nil)
+				dops := make([]ssa.Value, len(ops))
+				for i, op := range ops {
+					dops[i] = *op
+				}
+				cs = append(cs, NewPhiConstraint(dops, ins))
+			case *ssa.Sigma:
+				pred := ins.Block().Preds[0]
+				instrs := pred.Instrs
+				cond, ok := instrs[len(instrs)-1].(*ssa.If).Cond.(*ssa.BinOp)
+				ops := cond.Operands(nil)
+				if !ok {
+					continue
+				}
+				switch typ := ins.Type().Underlying().(type) {
+				case *types.Basic:
+					var c Constraint
+					switch typ.Kind() {
+					case types.Int, types.Int8, types.Int16, types.Int32, types.Int64,
+						types.Uint, types.Uint8, types.Uint16, types.Uint32, types.Uint64, types.UntypedInt:
+						c = sigmaInteger(g, ins, cond, ops)
+					case types.String, types.UntypedString:
+						c = sigmaString(g, ins, cond, ops)
+					}
+					if c != nil {
+						cs = append(cs, c)
+					}
+				case *types.Slice:
+					c := sigmaSlice(g, ins, cond, ops)
+					if c != nil {
+						cs = append(cs, c)
+					}
+				default:
+					//log.Printf("unsupported sigma type %T", typ) // XXX
+				}
+			case *ssa.MakeChan:
+				cs = append(cs, NewMakeChannelConstraint(ins.Size, ins))
+			case *ssa.MakeSlice:
+				cs = append(cs, NewMakeSliceConstraint(ins.Len, ins))
+			case *ssa.ChangeType:
+				switch ins.X.Type().Underlying().(type) {
+				case *types.Chan:
+					cs = append(cs, NewChannelChangeTypeConstraint(ins.X, ins))
+				}
+			}
+		}
+	}
+
+	for _, c := range cs {
+		if c == nil {
+			panic("nil constraint")
+		}
+		// If V is used in constraint C, then we create an edge V->C
+		for _, op := range c.Operands() {
+			g.AddEdge(op, c, false)
+		}
+		if c, ok := c.(Future); ok {
+			for _, op := range c.Futures() {
+				g.AddEdge(op, c, true)
+			}
+		}
+		// If constraint C defines variable V, then we create an edge
+		// C->V
+		g.AddEdge(c, c.Y(), false)
+	}
+
+	g.FindSCCs()
+	g.sccEdges = make([][]Edge, len(g.SCCs))
+	g.futures = make([][]Future, len(g.SCCs))
+	for _, e := range g.Edges {
+		g.sccEdges[e.From.SCC] = append(g.sccEdges[e.From.SCC], e)
+		if !e.control {
+			continue
+		}
+		if c, ok := e.To.Value.(Future); ok {
+			g.futures[e.From.SCC] = append(g.futures[e.From.SCC], c)
+		}
+	}
+	return g
+}
+
+func (g *Graph) Solve() Ranges {
+	var consts []Z
+	off := NewZ(1)
+	for _, n := range g.Vertices {
+		if c, ok := n.Value.(*ssa.Const); ok {
+			basic, ok := c.Type().Underlying().(*types.Basic)
+			if !ok {
+				continue
+			}
+			if (basic.Info() & types.IsInteger) != 0 {
+				z := ConstantToZ(c.Value)
+				consts = append(consts, z)
+				consts = append(consts, z.Add(off))
+				consts = append(consts, z.Sub(off))
+			}
+		}
+
+	}
+	sort.Sort(Zs(consts))
+
+	for scc, vertices := range g.SCCs {
+		n := 0
+		n = len(vertices)
+		if n == 1 {
+			g.resolveFutures(scc)
+			v := vertices[0]
+			if v, ok := v.Value.(ssa.Value); ok {
+				switch typ := v.Type().Underlying().(type) {
+				case *types.Basic:
+					switch typ.Kind() {
+					case types.String, types.UntypedString:
+						if !g.Range(v).(StringInterval).IsKnown() {
+							g.SetRange(v, StringInterval{NewIntInterval(NewZ(0), PInfinity)})
+						}
+					default:
+						if !g.Range(v).(IntInterval).IsKnown() {
+							g.SetRange(v, InfinityFor(v))
+						}
+					}
+				case *types.Chan:
+					if !g.Range(v).(ChannelInterval).IsKnown() {
+						g.SetRange(v, ChannelInterval{NewIntInterval(NewZ(0), PInfinity)})
+					}
+				case *types.Slice:
+					if !g.Range(v).(SliceInterval).IsKnown() {
+						g.SetRange(v, SliceInterval{NewIntInterval(NewZ(0), PInfinity)})
+					}
+				}
+			}
+			if c, ok := v.Value.(Constraint); ok {
+				g.SetRange(c.Y(), c.Eval(g))
+			}
+		} else {
+			uses := g.uses(scc)
+			entries := g.entries(scc)
+			for len(entries) > 0 {
+				v := entries[len(entries)-1]
+				entries = entries[:len(entries)-1]
+				for _, use := range uses[v] {
+					if g.widen(use, consts) {
+						entries = append(entries, use.Y())
+					}
+				}
+			}
+
+			g.resolveFutures(scc)
+
+			// XXX this seems to be necessary, but shouldn't be.
+			// removing it leads to nil pointer derefs; investigate
+			// where we're not setting values correctly.
+			for _, n := range vertices {
+				if v, ok := n.Value.(ssa.Value); ok {
+					i, ok := g.Range(v).(IntInterval)
+					if !ok {
+						continue
+					}
+					if !i.IsKnown() {
+						g.SetRange(v, InfinityFor(v))
+					}
+				}
+			}
+
+			actives := g.actives(scc)
+			for len(actives) > 0 {
+				v := actives[len(actives)-1]
+				actives = actives[:len(actives)-1]
+				for _, use := range uses[v] {
+					if g.narrow(use) {
+						actives = append(actives, use.Y())
+					}
+				}
+			}
+		}
+		// propagate scc
+		for _, edge := range g.sccEdges[scc] {
+			if edge.control {
+				continue
+			}
+			if edge.From.SCC == edge.To.SCC {
+				continue
+			}
+			if c, ok := edge.To.Value.(Constraint); ok {
+				g.SetRange(c.Y(), c.Eval(g))
+			}
+			if c, ok := edge.To.Value.(Future); ok {
+				if !c.IsKnown() {
+					c.MarkUnresolved()
+				}
+			}
+		}
+	}
+
+	for v, r := range g.ranges {
+		i, ok := r.(IntInterval)
+		if !ok {
+			continue
+		}
+		if (v.Type().Underlying().(*types.Basic).Info() & types.IsUnsigned) == 0 {
+			if i.Upper != PInfinity {
+				s := &types.StdSizes{
+					// XXX is it okay to assume the largest word size, or do we
+					// need to be platform specific?
+					WordSize: 8,
+					MaxAlign: 1,
+				}
+				bits := (s.Sizeof(v.Type()) * 8) - 1
+				n := big.NewInt(1)
+				n = n.Lsh(n, uint(bits))
+				upper, lower := &big.Int{}, &big.Int{}
+				upper.Sub(n, big.NewInt(1))
+				lower.Neg(n)
+
+				if i.Upper.Cmp(NewBigZ(upper)) == 1 {
+					i = NewIntInterval(NInfinity, PInfinity)
+				} else if i.Lower.Cmp(NewBigZ(lower)) == -1 {
+					i = NewIntInterval(NInfinity, PInfinity)
+				}
+			}
+		}
+
+		g.ranges[v] = i
+	}
+
+	return g.ranges
+}
+
+func VertexString(v *Vertex) string {
+	switch v := v.Value.(type) {
+	case Constraint:
+		return v.String()
+	case ssa.Value:
+		return v.Name()
+	case nil:
+		return "BUG: nil vertex value"
+	default:
+		panic(fmt.Sprintf("unexpected type %T", v))
+	}
+}
+
+type Vertex struct {
+	Value   interface{} // one of Constraint or ssa.Value
+	SCC     int
+	index   int
+	lowlink int
+	stack   bool
+
+	Succs []Edge
+}
+
+type Ranges map[ssa.Value]Range
+
+func (r Ranges) Get(x ssa.Value) Range {
+	if x == nil {
+		return nil
+	}
+	i, ok := r[x]
+	if !ok {
+		switch x := x.Type().Underlying().(type) {
+		case *types.Basic:
+			switch x.Kind() {
+			case types.String, types.UntypedString:
+				return StringInterval{}
+			default:
+				return IntInterval{}
+			}
+		case *types.Chan:
+			return ChannelInterval{}
+		case *types.Slice:
+			return SliceInterval{}
+		}
+	}
+	return i
+}
+
+type Graph struct {
+	Vertices map[interface{}]*Vertex
+	Edges    []Edge
+	SCCs     [][]*Vertex
+	ranges   Ranges
+
+	// map SCCs to futures
+	futures [][]Future
+	// map SCCs to edges
+	sccEdges [][]Edge
+}
+
+func (g Graph) Graphviz() string {
+	var lines []string
+	lines = append(lines, "digraph{")
+	ids := map[interface{}]int{}
+	i := 1
+	for _, v := range g.Vertices {
+		ids[v] = i
+		shape := "box"
+		if _, ok := v.Value.(ssa.Value); ok {
+			shape = "oval"
+		}
+		lines = append(lines, fmt.Sprintf(`n%d [shape="%s", label=%q, colorscheme=spectral11, style="filled", fillcolor="%d"]`,
+			i, shape, VertexString(v), (v.SCC%11)+1))
+		i++
+	}
+	for _, e := range g.Edges {
+		style := "solid"
+		if e.control {
+			style = "dashed"
+		}
+		lines = append(lines, fmt.Sprintf(`n%d -> n%d [style="%s"]`, ids[e.From], ids[e.To], style))
+	}
+	lines = append(lines, "}")
+	return strings.Join(lines, "\n")
+}
+
+func (g *Graph) SetRange(x ssa.Value, r Range) {
+	g.ranges[x] = r
+}
+
+func (g *Graph) Range(x ssa.Value) Range {
+	return g.ranges.Get(x)
+}
+
+func (g *Graph) widen(c Constraint, consts []Z) bool {
+	setRange := func(i Range) {
+		g.SetRange(c.Y(), i)
+	}
+	widenIntInterval := func(oi, ni IntInterval) (IntInterval, bool) {
+		if !ni.IsKnown() {
+			return oi, false
+		}
+		nlc := NInfinity
+		nuc := PInfinity
+		for _, co := range consts {
+			if co.Cmp(ni.Lower) <= 0 {
+				nlc = co
+				break
+			}
+		}
+		for _, co := range consts {
+			if co.Cmp(ni.Upper) >= 0 {
+				nuc = co
+				break
+			}
+		}
+
+		if !oi.IsKnown() {
+			return ni, true
+		}
+		if ni.Lower.Cmp(oi.Lower) == -1 && ni.Upper.Cmp(oi.Upper) == 1 {
+			return NewIntInterval(nlc, nuc), true
+		}
+		if ni.Lower.Cmp(oi.Lower) == -1 {
+			return NewIntInterval(nlc, oi.Upper), true
+		}
+		if ni.Upper.Cmp(oi.Upper) == 1 {
+			return NewIntInterval(oi.Lower, nuc), true
+		}
+		return oi, false
+	}
+	switch oi := g.Range(c.Y()).(type) {
+	case IntInterval:
+		ni := c.Eval(g).(IntInterval)
+		si, changed := widenIntInterval(oi, ni)
+		if changed {
+			setRange(si)
+			return true
+		}
+		return false
+	case StringInterval:
+		ni := c.Eval(g).(StringInterval)
+		si, changed := widenIntInterval(oi.Length, ni.Length)
+		if changed {
+			setRange(StringInterval{si})
+			return true
+		}
+		return false
+	case SliceInterval:
+		ni := c.Eval(g).(SliceInterval)
+		si, changed := widenIntInterval(oi.Length, ni.Length)
+		if changed {
+			setRange(SliceInterval{si})
+			return true
+		}
+		return false
+	default:
+		return false
+	}
+}
+
+func (g *Graph) narrow(c Constraint) bool {
+	narrowIntInterval := func(oi, ni IntInterval) (IntInterval, bool) {
+		oLower := oi.Lower
+		oUpper := oi.Upper
+		nLower := ni.Lower
+		nUpper := ni.Upper
+
+		if oLower == NInfinity && nLower != NInfinity {
+			return NewIntInterval(nLower, oUpper), true
+		}
+		if oUpper == PInfinity && nUpper != PInfinity {
+			return NewIntInterval(oLower, nUpper), true
+		}
+		if oLower.Cmp(nLower) == 1 {
+			return NewIntInterval(nLower, oUpper), true
+		}
+		if oUpper.Cmp(nUpper) == -1 {
+			return NewIntInterval(oLower, nUpper), true
+		}
+		return oi, false
+	}
+	switch oi := g.Range(c.Y()).(type) {
+	case IntInterval:
+		ni := c.Eval(g).(IntInterval)
+		si, changed := narrowIntInterval(oi, ni)
+		if changed {
+			g.SetRange(c.Y(), si)
+			return true
+		}
+		return false
+	case StringInterval:
+		ni := c.Eval(g).(StringInterval)
+		si, changed := narrowIntInterval(oi.Length, ni.Length)
+		if changed {
+			g.SetRange(c.Y(), StringInterval{si})
+			return true
+		}
+		return false
+	case SliceInterval:
+		ni := c.Eval(g).(SliceInterval)
+		si, changed := narrowIntInterval(oi.Length, ni.Length)
+		if changed {
+			g.SetRange(c.Y(), SliceInterval{si})
+			return true
+		}
+		return false
+	default:
+		return false
+	}
+}
+
+func (g *Graph) resolveFutures(scc int) {
+	for _, c := range g.futures[scc] {
+		c.Resolve()
+	}
+}
+
+func (g *Graph) entries(scc int) []ssa.Value {
+	var entries []ssa.Value
+	for _, n := range g.Vertices {
+		if n.SCC != scc {
+			continue
+		}
+		if v, ok := n.Value.(ssa.Value); ok {
+			// XXX avoid quadratic runtime
+			//
+			// XXX I cannot think of any code where the future and its
+			// variables aren't in the same SCC, in which case this
+			// code isn't very useful (the variables won't be resolved
+			// yet). Before we have a cross-SCC example, however, we
+			// can't really verify that this code is working
+			// correctly, or indeed doing anything useful.
+			for _, on := range g.Vertices {
+				if c, ok := on.Value.(Future); ok {
+					if c.Y() == v {
+						if !c.IsResolved() {
+							g.SetRange(c.Y(), c.Eval(g))
+							c.MarkResolved()
+						}
+						break
+					}
+				}
+			}
+			if g.Range(v).IsKnown() {
+				entries = append(entries, v)
+			}
+		}
+	}
+	return entries
+}
+
+func (g *Graph) uses(scc int) map[ssa.Value][]Constraint {
+	m := map[ssa.Value][]Constraint{}
+	for _, e := range g.sccEdges[scc] {
+		if e.control {
+			continue
+		}
+		if v, ok := e.From.Value.(ssa.Value); ok {
+			c := e.To.Value.(Constraint)
+			sink := c.Y()
+			if g.Vertices[sink].SCC == scc {
+				m[v] = append(m[v], c)
+			}
+		}
+	}
+	return m
+}
+
+func (g *Graph) actives(scc int) []ssa.Value {
+	var actives []ssa.Value
+	for _, n := range g.Vertices {
+		if n.SCC != scc {
+			continue
+		}
+		if v, ok := n.Value.(ssa.Value); ok {
+			if _, ok := v.(*ssa.Const); !ok {
+				actives = append(actives, v)
+			}
+		}
+	}
+	return actives
+}
+
+func (g *Graph) AddEdge(from, to interface{}, ctrl bool) {
+	vf, ok := g.Vertices[from]
+	if !ok {
+		vf = &Vertex{Value: from}
+		g.Vertices[from] = vf
+	}
+	vt, ok := g.Vertices[to]
+	if !ok {
+		vt = &Vertex{Value: to}
+		g.Vertices[to] = vt
+	}
+	e := Edge{From: vf, To: vt, control: ctrl}
+	g.Edges = append(g.Edges, e)
+	vf.Succs = append(vf.Succs, e)
+}
+
+type Edge struct {
+	From, To *Vertex
+	control  bool
+}
+
+func (e Edge) String() string {
+	return fmt.Sprintf("%s -> %s", VertexString(e.From), VertexString(e.To))
+}
+
+func (g *Graph) FindSCCs() {
+	// use Tarjan to find the SCCs
+
+	index := 1
+	var s []*Vertex
+
+	scc := 0
+	var strongconnect func(v *Vertex)
+	strongconnect = func(v *Vertex) {
+		// set the depth index for v to the smallest unused index
+		v.index = index
+		v.lowlink = index
+		index++
+		s = append(s, v)
+		v.stack = true
+
+		for _, e := range v.Succs {
+			w := e.To
+			if w.index == 0 {
+				// successor w has not yet been visited; recurse on it
+				strongconnect(w)
+				if w.lowlink < v.lowlink {
+					v.lowlink = w.lowlink
+				}
+			} else if w.stack {
+				// successor w is in stack s and hence in the current scc
+				if w.index < v.lowlink {
+					v.lowlink = w.index
+				}
+			}
+		}
+
+		if v.lowlink == v.index {
+			for {
+				w := s[len(s)-1]
+				s = s[:len(s)-1]
+				w.stack = false
+				w.SCC = scc
+				if w == v {
+					break
+				}
+			}
+			scc++
+		}
+	}
+	for _, v := range g.Vertices {
+		if v.index == 0 {
+			strongconnect(v)
+		}
+	}
+
+	g.SCCs = make([][]*Vertex, scc)
+	for _, n := range g.Vertices {
+		n.SCC = scc - n.SCC - 1
+		g.SCCs[n.SCC] = append(g.SCCs[n.SCC], n)
+	}
+}
+
+func invertToken(tok token.Token) token.Token {
+	switch tok {
+	case token.LSS:
+		return token.GEQ
+	case token.GTR:
+		return token.LEQ
+	case token.EQL:
+		return token.NEQ
+	case token.NEQ:
+		return token.EQL
+	case token.GEQ:
+		return token.LSS
+	case token.LEQ:
+		return token.GTR
+	default:
+		panic(fmt.Sprintf("unsupported token %s", tok))
+	}
+}
+
+func flipToken(tok token.Token) token.Token {
+	switch tok {
+	case token.LSS:
+		return token.GTR
+	case token.GTR:
+		return token.LSS
+	case token.EQL:
+		return token.EQL
+	case token.NEQ:
+		return token.NEQ
+	case token.GEQ:
+		return token.LEQ
+	case token.LEQ:
+		return token.GEQ
+	default:
+		panic(fmt.Sprintf("unsupported token %s", tok))
+	}
+}
+
+type CopyConstraint struct {
+	aConstraint
+	X ssa.Value
+}
+
+func (c *CopyConstraint) String() string {
+	return fmt.Sprintf("%s = copy(%s)", c.Y().Name(), c.X.Name())
+}
+
+func (c *CopyConstraint) Eval(g *Graph) Range {
+	return g.Range(c.X)
+}
+
+func (c *CopyConstraint) Operands() []ssa.Value {
+	return []ssa.Value{c.X}
+}
+
+func NewCopyConstraint(x, y ssa.Value) Constraint {
+	return &CopyConstraint{
+		aConstraint: aConstraint{
+			y: y,
+		},
+		X: x,
+	}
+}