1package vrp
2
3// TODO(dh) widening and narrowing have a lot of code in common. Make
4// it reusable.
5
6import (
7	"fmt"
8	"go/constant"
9	"go/token"
10	"go/types"
11	"math/big"
12	"sort"
13	"strings"
14
15	"honnef.co/go/tools/lint"
16	"honnef.co/go/tools/ssa"
17)
18
19type Future interface {
20	Constraint
21	Futures() []ssa.Value
22	Resolve()
23	IsKnown() bool
24	MarkUnresolved()
25	MarkResolved()
26	IsResolved() bool
27}
28
29type Range interface {
30	Union(other Range) Range
31	IsKnown() bool
32}
33
34type Constraint interface {
35	Y() ssa.Value
36	isConstraint()
37	String() string
38	Eval(*Graph) Range
39	Operands() []ssa.Value
40}
41
42type aConstraint struct {
43	y ssa.Value
44}
45
46func NewConstraint(y ssa.Value) aConstraint {
47	return aConstraint{y}
48}
49
50func (aConstraint) isConstraint()  {}
51func (c aConstraint) Y() ssa.Value { return c.y }
52
53type PhiConstraint struct {
54	aConstraint
55	Vars []ssa.Value
56}
57
58func NewPhiConstraint(vars []ssa.Value, y ssa.Value) Constraint {
59	uniqm := map[ssa.Value]struct{}{}
60	for _, v := range vars {
61		uniqm[v] = struct{}{}
62	}
63	var uniq []ssa.Value
64	for v := range uniqm {
65		uniq = append(uniq, v)
66	}
67	return &PhiConstraint{
68		aConstraint: NewConstraint(y),
69		Vars:        uniq,
70	}
71}
72
73func (c *PhiConstraint) Operands() []ssa.Value {
74	return c.Vars
75}
76
77func (c *PhiConstraint) Eval(g *Graph) Range {
78	i := Range(nil)
79	for _, v := range c.Vars {
80		i = g.Range(v).Union(i)
81	}
82	return i
83}
84
85func (c *PhiConstraint) String() string {
86	names := make([]string, len(c.Vars))
87	for i, v := range c.Vars {
88		names[i] = v.Name()
89	}
90	return fmt.Sprintf("%s = φ(%s)", c.Y().Name(), strings.Join(names, ", "))
91}
92
93func isSupportedType(typ types.Type) bool {
94	switch typ := typ.Underlying().(type) {
95	case *types.Basic:
96		switch typ.Kind() {
97		case types.String, types.UntypedString:
98			return true
99		default:
100			if (typ.Info() & types.IsInteger) == 0 {
101				return false
102			}
103		}
104	case *types.Chan:
105		return true
106	case *types.Slice:
107		return true
108	default:
109		return false
110	}
111	return true
112}
113
114func ConstantToZ(c constant.Value) Z {
115	s := constant.ToInt(c).ExactString()
116	n := &big.Int{}
117	n.SetString(s, 10)
118	return NewBigZ(n)
119}
120
121func sigmaInteger(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
122	op := cond.Op
123	if !ins.Branch {
124		op = (invertToken(op))
125	}
126
127	switch op {
128	case token.EQL, token.GTR, token.GEQ, token.LSS, token.LEQ:
129	default:
130		return nil
131	}
132	var a, b ssa.Value
133	if (*ops[0]) == ins.X {
134		a = *ops[0]
135		b = *ops[1]
136	} else {
137		a = *ops[1]
138		b = *ops[0]
139		op = flipToken(op)
140	}
141	return NewIntIntersectionConstraint(a, b, op, g.ranges, ins)
142}
143
144func sigmaString(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
145	op := cond.Op
146	if !ins.Branch {
147		op = (invertToken(op))
148	}
149
150	switch op {
151	case token.EQL, token.GTR, token.GEQ, token.LSS, token.LEQ:
152	default:
153		return nil
154	}
155
156	if ((*ops[0]).Type().Underlying().(*types.Basic).Info() & types.IsString) == 0 {
157		var a, b ssa.Value
158		call, ok := (*ops[0]).(*ssa.Call)
159		if ok && call.Common().Args[0] == ins.X {
160			a = *ops[0]
161			b = *ops[1]
162		} else {
163			a = *ops[1]
164			b = *ops[0]
165			op = flipToken(op)
166		}
167		return NewStringIntersectionConstraint(a, b, op, g.ranges, ins)
168	}
169	var a, b ssa.Value
170	if (*ops[0]) == ins.X {
171		a = *ops[0]
172		b = *ops[1]
173	} else {
174		a = *ops[1]
175		b = *ops[0]
176		op = flipToken(op)
177	}
178	return NewStringIntersectionConstraint(a, b, op, g.ranges, ins)
179}
180
181func sigmaSlice(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
182	// TODO(dh) sigmaSlice and sigmaString are a lot alike. Can they
183	// be merged?
184	//
185	// XXX support futures
186
187	op := cond.Op
188	if !ins.Branch {
189		op = (invertToken(op))
190	}
191
192	k, ok := (*ops[1]).(*ssa.Const)
193	// XXX investigate in what cases this wouldn't be a Const
194	//
195	// XXX what if left and right are swapped?
196	if !ok {
197		return nil
198	}
199
200	call, ok := (*ops[0]).(*ssa.Call)
201	if !ok {
202		return nil
203	}
204	builtin, ok := call.Common().Value.(*ssa.Builtin)
205	if !ok {
206		return nil
207	}
208	if builtin.Name() != "len" {
209		return nil
210	}
211	callops := call.Operands(nil)
212
213	v := ConstantToZ(k.Value)
214	c := NewSliceIntersectionConstraint(*callops[1], IntInterval{}, ins).(*SliceIntersectionConstraint)
215	switch op {
216	case token.EQL:
217		c.I = NewIntInterval(v, v)
218	case token.GTR, token.GEQ:
219		off := int64(0)
220		if cond.Op == token.GTR {
221			off = 1
222		}
223		c.I = NewIntInterval(
224			v.Add(NewZ(off)),
225			PInfinity,
226		)
227	case token.LSS, token.LEQ:
228		off := int64(0)
229		if cond.Op == token.LSS {
230			off = -1
231		}
232		c.I = NewIntInterval(
233			NInfinity,
234			v.Add(NewZ(off)),
235		)
236	default:
237		return nil
238	}
239	return c
240}
241
242func BuildGraph(f *ssa.Function) *Graph {
243	g := &Graph{
244		Vertices: map[interface{}]*Vertex{},
245		ranges:   Ranges{},
246	}
247
248	var cs []Constraint
249
250	ops := make([]*ssa.Value, 16)
251	seen := map[ssa.Value]bool{}
252	for _, block := range f.Blocks {
253		for _, ins := range block.Instrs {
254			ops = ins.Operands(ops[:0])
255			for _, op := range ops {
256				if c, ok := (*op).(*ssa.Const); ok {
257					if seen[c] {
258						continue
259					}
260					seen[c] = true
261					if c.Value == nil {
262						switch c.Type().Underlying().(type) {
263						case *types.Slice:
264							cs = append(cs, NewSliceIntervalConstraint(NewIntInterval(NewZ(0), NewZ(0)), c))
265						}
266						continue
267					}
268					switch c.Value.Kind() {
269					case constant.Int:
270						v := ConstantToZ(c.Value)
271						cs = append(cs, NewIntIntervalConstraint(NewIntInterval(v, v), c))
272					case constant.String:
273						s := constant.StringVal(c.Value)
274						n := NewZ(int64(len(s)))
275						cs = append(cs, NewStringIntervalConstraint(NewIntInterval(n, n), c))
276					}
277				}
278			}
279		}
280	}
281	for _, block := range f.Blocks {
282		for _, ins := range block.Instrs {
283			switch ins := ins.(type) {
284			case *ssa.Convert:
285				switch v := ins.Type().Underlying().(type) {
286				case *types.Basic:
287					if (v.Info() & types.IsInteger) == 0 {
288						continue
289					}
290					cs = append(cs, NewIntConversionConstraint(ins.X, ins))
291				}
292			case *ssa.Call:
293				if static := ins.Common().StaticCallee(); static != nil {
294					if fn, ok := static.Object().(*types.Func); ok {
295						switch lint.FuncName(fn) {
296						case "bytes.Index", "bytes.IndexAny", "bytes.IndexByte",
297							"bytes.IndexFunc", "bytes.IndexRune", "bytes.LastIndex",
298							"bytes.LastIndexAny", "bytes.LastIndexByte", "bytes.LastIndexFunc",
299							"strings.Index", "strings.IndexAny", "strings.IndexByte",
300							"strings.IndexFunc", "strings.IndexRune", "strings.LastIndex",
301							"strings.LastIndexAny", "strings.LastIndexByte", "strings.LastIndexFunc":
302							// TODO(dh): instead of limiting by +∞,
303							// limit by the upper bound of the passed
304							// string
305							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(-1), PInfinity), ins))
306						case "bytes.Title", "bytes.ToLower", "bytes.ToTitle", "bytes.ToUpper",
307							"strings.Title", "strings.ToLower", "strings.ToTitle", "strings.ToUpper":
308							cs = append(cs, NewCopyConstraint(ins.Common().Args[0], ins))
309						case "bytes.ToLowerSpecial", "bytes.ToTitleSpecial", "bytes.ToUpperSpecial",
310							"strings.ToLowerSpecial", "strings.ToTitleSpecial", "strings.ToUpperSpecial":
311							cs = append(cs, NewCopyConstraint(ins.Common().Args[1], ins))
312						case "bytes.Compare", "strings.Compare":
313							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(-1), NewZ(1)), ins))
314						case "bytes.Count", "strings.Count":
315							// TODO(dh): instead of limiting by +∞,
316							// limit by the upper bound of the passed
317							// string.
318							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(0), PInfinity), ins))
319						case "bytes.Map", "bytes.TrimFunc", "bytes.TrimLeft", "bytes.TrimLeftFunc",
320							"bytes.TrimRight", "bytes.TrimRightFunc", "bytes.TrimSpace",
321							"strings.Map", "strings.TrimFunc", "strings.TrimLeft", "strings.TrimLeftFunc",
322							"strings.TrimRight", "strings.TrimRightFunc", "strings.TrimSpace":
323							// TODO(dh): lower = 0, upper = upper of passed string
324						case "bytes.TrimPrefix", "bytes.TrimSuffix",
325							"strings.TrimPrefix", "strings.TrimSuffix":
326							// TODO(dh) range between "unmodified" and len(cutset) removed
327						case "(*bytes.Buffer).Cap", "(*bytes.Buffer).Len", "(*bytes.Reader).Len", "(*bytes.Reader).Size":
328							cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(0), PInfinity), ins))
329						}
330					}
331				}
332				builtin, ok := ins.Common().Value.(*ssa.Builtin)
333				ops := ins.Operands(nil)
334				if !ok {
335					continue
336				}
337				switch builtin.Name() {
338				case "len":
339					switch op1 := (*ops[1]).Type().Underlying().(type) {
340					case *types.Basic:
341						if op1.Kind() == types.String || op1.Kind() == types.UntypedString {
342							cs = append(cs, NewStringLengthConstraint(*ops[1], ins))
343						}
344					case *types.Slice:
345						cs = append(cs, NewSliceLengthConstraint(*ops[1], ins))
346					}
347
348				case "append":
349					cs = append(cs, NewSliceAppendConstraint(ins.Common().Args[0], ins.Common().Args[1], ins))
350				}
351			case *ssa.BinOp:
352				ops := ins.Operands(nil)
353				basic, ok := (*ops[0]).Type().Underlying().(*types.Basic)
354				if !ok {
355					continue
356				}
357				switch basic.Kind() {
358				case types.Int, types.Int8, types.Int16, types.Int32, types.Int64,
359					types.Uint, types.Uint8, types.Uint16, types.Uint32, types.Uint64, types.UntypedInt:
360					fns := map[token.Token]func(ssa.Value, ssa.Value, ssa.Value) Constraint{
361						token.ADD: NewIntAddConstraint,
362						token.SUB: NewIntSubConstraint,
363						token.MUL: NewIntMulConstraint,
364						// XXX support QUO, REM, SHL, SHR
365					}
366					fn, ok := fns[ins.Op]
367					if ok {
368						cs = append(cs, fn(*ops[0], *ops[1], ins))
369					}
370				case types.String, types.UntypedString:
371					if ins.Op == token.ADD {
372						cs = append(cs, NewStringConcatConstraint(*ops[0], *ops[1], ins))
373					}
374				}
375			case *ssa.Slice:
376				typ := ins.X.Type().Underlying()
377				switch typ := typ.(type) {
378				case *types.Basic:
379					cs = append(cs, NewStringSliceConstraint(ins.X, ins.Low, ins.High, ins))
380				case *types.Slice:
381					cs = append(cs, NewSliceSliceConstraint(ins.X, ins.Low, ins.High, ins))
382				case *types.Array:
383					cs = append(cs, NewArraySliceConstraint(ins.X, ins.Low, ins.High, ins))
384				case *types.Pointer:
385					if _, ok := typ.Elem().(*types.Array); !ok {
386						continue
387					}
388					cs = append(cs, NewArraySliceConstraint(ins.X, ins.Low, ins.High, ins))
389				}
390			case *ssa.Phi:
391				if !isSupportedType(ins.Type()) {
392					continue
393				}
394				ops := ins.Operands(nil)
395				dops := make([]ssa.Value, len(ops))
396				for i, op := range ops {
397					dops[i] = *op
398				}
399				cs = append(cs, NewPhiConstraint(dops, ins))
400			case *ssa.Sigma:
401				pred := ins.Block().Preds[0]
402				instrs := pred.Instrs
403				cond, ok := instrs[len(instrs)-1].(*ssa.If).Cond.(*ssa.BinOp)
404				ops := cond.Operands(nil)
405				if !ok {
406					continue
407				}
408				switch typ := ins.Type().Underlying().(type) {
409				case *types.Basic:
410					var c Constraint
411					switch typ.Kind() {
412					case types.Int, types.Int8, types.Int16, types.Int32, types.Int64,
413						types.Uint, types.Uint8, types.Uint16, types.Uint32, types.Uint64, types.UntypedInt:
414						c = sigmaInteger(g, ins, cond, ops)
415					case types.String, types.UntypedString:
416						c = sigmaString(g, ins, cond, ops)
417					}
418					if c != nil {
419						cs = append(cs, c)
420					}
421				case *types.Slice:
422					c := sigmaSlice(g, ins, cond, ops)
423					if c != nil {
424						cs = append(cs, c)
425					}
426				default:
427					//log.Printf("unsupported sigma type %T", typ) // XXX
428				}
429			case *ssa.MakeChan:
430				cs = append(cs, NewMakeChannelConstraint(ins.Size, ins))
431			case *ssa.MakeSlice:
432				cs = append(cs, NewMakeSliceConstraint(ins.Len, ins))
433			case *ssa.ChangeType:
434				switch ins.X.Type().Underlying().(type) {
435				case *types.Chan:
436					cs = append(cs, NewChannelChangeTypeConstraint(ins.X, ins))
437				}
438			}
439		}
440	}
441
442	for _, c := range cs {
443		if c == nil {
444			panic("nil constraint")
445		}
446		// If V is used in constraint C, then we create an edge V->C
447		for _, op := range c.Operands() {
448			g.AddEdge(op, c, false)
449		}
450		if c, ok := c.(Future); ok {
451			for _, op := range c.Futures() {
452				g.AddEdge(op, c, true)
453			}
454		}
455		// If constraint C defines variable V, then we create an edge
456		// C->V
457		g.AddEdge(c, c.Y(), false)
458	}
459
460	g.FindSCCs()
461	g.sccEdges = make([][]Edge, len(g.SCCs))
462	g.futures = make([][]Future, len(g.SCCs))
463	for _, e := range g.Edges {
464		g.sccEdges[e.From.SCC] = append(g.sccEdges[e.From.SCC], e)
465		if !e.control {
466			continue
467		}
468		if c, ok := e.To.Value.(Future); ok {
469			g.futures[e.From.SCC] = append(g.futures[e.From.SCC], c)
470		}
471	}
472	return g
473}
474
475func (g *Graph) Solve() Ranges {
476	var consts []Z
477	off := NewZ(1)
478	for _, n := range g.Vertices {
479		if c, ok := n.Value.(*ssa.Const); ok {
480			basic, ok := c.Type().Underlying().(*types.Basic)
481			if !ok {
482				continue
483			}
484			if (basic.Info() & types.IsInteger) != 0 {
485				z := ConstantToZ(c.Value)
486				consts = append(consts, z)
487				consts = append(consts, z.Add(off))
488				consts = append(consts, z.Sub(off))
489			}
490		}
491
492	}
493	sort.Sort(Zs(consts))
494
495	for scc, vertices := range g.SCCs {
496		n := 0
497		n = len(vertices)
498		if n == 1 {
499			g.resolveFutures(scc)
500			v := vertices[0]
501			if v, ok := v.Value.(ssa.Value); ok {
502				switch typ := v.Type().Underlying().(type) {
503				case *types.Basic:
504					switch typ.Kind() {
505					case types.String, types.UntypedString:
506						if !g.Range(v).(StringInterval).IsKnown() {
507							g.SetRange(v, StringInterval{NewIntInterval(NewZ(0), PInfinity)})
508						}
509					default:
510						if !g.Range(v).(IntInterval).IsKnown() {
511							g.SetRange(v, InfinityFor(v))
512						}
513					}
514				case *types.Chan:
515					if !g.Range(v).(ChannelInterval).IsKnown() {
516						g.SetRange(v, ChannelInterval{NewIntInterval(NewZ(0), PInfinity)})
517					}
518				case *types.Slice:
519					if !g.Range(v).(SliceInterval).IsKnown() {
520						g.SetRange(v, SliceInterval{NewIntInterval(NewZ(0), PInfinity)})
521					}
522				}
523			}
524			if c, ok := v.Value.(Constraint); ok {
525				g.SetRange(c.Y(), c.Eval(g))
526			}
527		} else {
528			uses := g.uses(scc)
529			entries := g.entries(scc)
530			for len(entries) > 0 {
531				v := entries[len(entries)-1]
532				entries = entries[:len(entries)-1]
533				for _, use := range uses[v] {
534					if g.widen(use, consts) {
535						entries = append(entries, use.Y())
536					}
537				}
538			}
539
540			g.resolveFutures(scc)
541
542			// XXX this seems to be necessary, but shouldn't be.
543			// removing it leads to nil pointer derefs; investigate
544			// where we're not setting values correctly.
545			for _, n := range vertices {
546				if v, ok := n.Value.(ssa.Value); ok {
547					i, ok := g.Range(v).(IntInterval)
548					if !ok {
549						continue
550					}
551					if !i.IsKnown() {
552						g.SetRange(v, InfinityFor(v))
553					}
554				}
555			}
556
557			actives := g.actives(scc)
558			for len(actives) > 0 {
559				v := actives[len(actives)-1]
560				actives = actives[:len(actives)-1]
561				for _, use := range uses[v] {
562					if g.narrow(use) {
563						actives = append(actives, use.Y())
564					}
565				}
566			}
567		}
568		// propagate scc
569		for _, edge := range g.sccEdges[scc] {
570			if edge.control {
571				continue
572			}
573			if edge.From.SCC == edge.To.SCC {
574				continue
575			}
576			if c, ok := edge.To.Value.(Constraint); ok {
577				g.SetRange(c.Y(), c.Eval(g))
578			}
579			if c, ok := edge.To.Value.(Future); ok {
580				if !c.IsKnown() {
581					c.MarkUnresolved()
582				}
583			}
584		}
585	}
586
587	for v, r := range g.ranges {
588		i, ok := r.(IntInterval)
589		if !ok {
590			continue
591		}
592		if (v.Type().Underlying().(*types.Basic).Info() & types.IsUnsigned) == 0 {
593			if i.Upper != PInfinity {
594				s := &types.StdSizes{
595					// XXX is it okay to assume the largest word size, or do we
596					// need to be platform specific?
597					WordSize: 8,
598					MaxAlign: 1,
599				}
600				bits := (s.Sizeof(v.Type()) * 8) - 1
601				n := big.NewInt(1)
602				n = n.Lsh(n, uint(bits))
603				upper, lower := &big.Int{}, &big.Int{}
604				upper.Sub(n, big.NewInt(1))
605				lower.Neg(n)
606
607				if i.Upper.Cmp(NewBigZ(upper)) == 1 {
608					i = NewIntInterval(NInfinity, PInfinity)
609				} else if i.Lower.Cmp(NewBigZ(lower)) == -1 {
610					i = NewIntInterval(NInfinity, PInfinity)
611				}
612			}
613		}
614
615		g.ranges[v] = i
616	}
617
618	return g.ranges
619}
620
621func VertexString(v *Vertex) string {
622	switch v := v.Value.(type) {
623	case Constraint:
624		return v.String()
625	case ssa.Value:
626		return v.Name()
627	case nil:
628		return "BUG: nil vertex value"
629	default:
630		panic(fmt.Sprintf("unexpected type %T", v))
631	}
632}
633
634type Vertex struct {
635	Value   interface{} // one of Constraint or ssa.Value
636	SCC     int
637	index   int
638	lowlink int
639	stack   bool
640
641	Succs []Edge
642}
643
644type Ranges map[ssa.Value]Range
645
646func (r Ranges) Get(x ssa.Value) Range {
647	if x == nil {
648		return nil
649	}
650	i, ok := r[x]
651	if !ok {
652		switch x := x.Type().Underlying().(type) {
653		case *types.Basic:
654			switch x.Kind() {
655			case types.String, types.UntypedString:
656				return StringInterval{}
657			default:
658				return IntInterval{}
659			}
660		case *types.Chan:
661			return ChannelInterval{}
662		case *types.Slice:
663			return SliceInterval{}
664		}
665	}
666	return i
667}
668
669type Graph struct {
670	Vertices map[interface{}]*Vertex
671	Edges    []Edge
672	SCCs     [][]*Vertex
673	ranges   Ranges
674
675	// map SCCs to futures
676	futures [][]Future
677	// map SCCs to edges
678	sccEdges [][]Edge
679}
680
681func (g Graph) Graphviz() string {
682	var lines []string
683	lines = append(lines, "digraph{")
684	ids := map[interface{}]int{}
685	i := 1
686	for _, v := range g.Vertices {
687		ids[v] = i
688		shape := "box"
689		if _, ok := v.Value.(ssa.Value); ok {
690			shape = "oval"
691		}
692		lines = append(lines, fmt.Sprintf(`n%d [shape="%s", label=%q, colorscheme=spectral11, style="filled", fillcolor="%d"]`,
693			i, shape, VertexString(v), (v.SCC%11)+1))
694		i++
695	}
696	for _, e := range g.Edges {
697		style := "solid"
698		if e.control {
699			style = "dashed"
700		}
701		lines = append(lines, fmt.Sprintf(`n%d -> n%d [style="%s"]`, ids[e.From], ids[e.To], style))
702	}
703	lines = append(lines, "}")
704	return strings.Join(lines, "\n")
705}
706
707func (g *Graph) SetRange(x ssa.Value, r Range) {
708	g.ranges[x] = r
709}
710
711func (g *Graph) Range(x ssa.Value) Range {
712	return g.ranges.Get(x)
713}
714
715func (g *Graph) widen(c Constraint, consts []Z) bool {
716	setRange := func(i Range) {
717		g.SetRange(c.Y(), i)
718	}
719	widenIntInterval := func(oi, ni IntInterval) (IntInterval, bool) {
720		if !ni.IsKnown() {
721			return oi, false
722		}
723		nlc := NInfinity
724		nuc := PInfinity
725
726		// Don't get stuck widening for an absurd amount of time due
727		// to an excess number of constants, as may be present in
728		// table-based scanners.
729		if len(consts) < 1000 {
730			for _, co := range consts {
731				if co.Cmp(ni.Lower) <= 0 {
732					nlc = co
733					break
734				}
735			}
736			for _, co := range consts {
737				if co.Cmp(ni.Upper) >= 0 {
738					nuc = co
739					break
740				}
741			}
742		}
743
744		if !oi.IsKnown() {
745			return ni, true
746		}
747		if ni.Lower.Cmp(oi.Lower) == -1 && ni.Upper.Cmp(oi.Upper) == 1 {
748			return NewIntInterval(nlc, nuc), true
749		}
750		if ni.Lower.Cmp(oi.Lower) == -1 {
751			return NewIntInterval(nlc, oi.Upper), true
752		}
753		if ni.Upper.Cmp(oi.Upper) == 1 {
754			return NewIntInterval(oi.Lower, nuc), true
755		}
756		return oi, false
757	}
758	switch oi := g.Range(c.Y()).(type) {
759	case IntInterval:
760		ni := c.Eval(g).(IntInterval)
761		si, changed := widenIntInterval(oi, ni)
762		if changed {
763			setRange(si)
764			return true
765		}
766		return false
767	case StringInterval:
768		ni := c.Eval(g).(StringInterval)
769		si, changed := widenIntInterval(oi.Length, ni.Length)
770		if changed {
771			setRange(StringInterval{si})
772			return true
773		}
774		return false
775	case SliceInterval:
776		ni := c.Eval(g).(SliceInterval)
777		si, changed := widenIntInterval(oi.Length, ni.Length)
778		if changed {
779			setRange(SliceInterval{si})
780			return true
781		}
782		return false
783	default:
784		return false
785	}
786}
787
788func (g *Graph) narrow(c Constraint) bool {
789	narrowIntInterval := func(oi, ni IntInterval) (IntInterval, bool) {
790		oLower := oi.Lower
791		oUpper := oi.Upper
792		nLower := ni.Lower
793		nUpper := ni.Upper
794
795		if oLower == NInfinity && nLower != NInfinity {
796			return NewIntInterval(nLower, oUpper), true
797		}
798		if oUpper == PInfinity && nUpper != PInfinity {
799			return NewIntInterval(oLower, nUpper), true
800		}
801		if oLower.Cmp(nLower) == 1 {
802			return NewIntInterval(nLower, oUpper), true
803		}
804		if oUpper.Cmp(nUpper) == -1 {
805			return NewIntInterval(oLower, nUpper), true
806		}
807		return oi, false
808	}
809	switch oi := g.Range(c.Y()).(type) {
810	case IntInterval:
811		ni := c.Eval(g).(IntInterval)
812		si, changed := narrowIntInterval(oi, ni)
813		if changed {
814			g.SetRange(c.Y(), si)
815			return true
816		}
817		return false
818	case StringInterval:
819		ni := c.Eval(g).(StringInterval)
820		si, changed := narrowIntInterval(oi.Length, ni.Length)
821		if changed {
822			g.SetRange(c.Y(), StringInterval{si})
823			return true
824		}
825		return false
826	case SliceInterval:
827		ni := c.Eval(g).(SliceInterval)
828		si, changed := narrowIntInterval(oi.Length, ni.Length)
829		if changed {
830			g.SetRange(c.Y(), SliceInterval{si})
831			return true
832		}
833		return false
834	default:
835		return false
836	}
837}
838
839func (g *Graph) resolveFutures(scc int) {
840	for _, c := range g.futures[scc] {
841		c.Resolve()
842	}
843}
844
845func (g *Graph) entries(scc int) []ssa.Value {
846	var entries []ssa.Value
847	for _, n := range g.Vertices {
848		if n.SCC != scc {
849			continue
850		}
851		if v, ok := n.Value.(ssa.Value); ok {
852			// XXX avoid quadratic runtime
853			//
854			// XXX I cannot think of any code where the future and its
855			// variables aren't in the same SCC, in which case this
856			// code isn't very useful (the variables won't be resolved
857			// yet). Before we have a cross-SCC example, however, we
858			// can't really verify that this code is working
859			// correctly, or indeed doing anything useful.
860			for _, on := range g.Vertices {
861				if c, ok := on.Value.(Future); ok {
862					if c.Y() == v {
863						if !c.IsResolved() {
864							g.SetRange(c.Y(), c.Eval(g))
865							c.MarkResolved()
866						}
867						break
868					}
869				}
870			}
871			if g.Range(v).IsKnown() {
872				entries = append(entries, v)
873			}
874		}
875	}
876	return entries
877}
878
879func (g *Graph) uses(scc int) map[ssa.Value][]Constraint {
880	m := map[ssa.Value][]Constraint{}
881	for _, e := range g.sccEdges[scc] {
882		if e.control {
883			continue
884		}
885		if v, ok := e.From.Value.(ssa.Value); ok {
886			c := e.To.Value.(Constraint)
887			sink := c.Y()
888			if g.Vertices[sink].SCC == scc {
889				m[v] = append(m[v], c)
890			}
891		}
892	}
893	return m
894}
895
896func (g *Graph) actives(scc int) []ssa.Value {
897	var actives []ssa.Value
898	for _, n := range g.Vertices {
899		if n.SCC != scc {
900			continue
901		}
902		if v, ok := n.Value.(ssa.Value); ok {
903			if _, ok := v.(*ssa.Const); !ok {
904				actives = append(actives, v)
905			}
906		}
907	}
908	return actives
909}
910
911func (g *Graph) AddEdge(from, to interface{}, ctrl bool) {
912	vf, ok := g.Vertices[from]
913	if !ok {
914		vf = &Vertex{Value: from}
915		g.Vertices[from] = vf
916	}
917	vt, ok := g.Vertices[to]
918	if !ok {
919		vt = &Vertex{Value: to}
920		g.Vertices[to] = vt
921	}
922	e := Edge{From: vf, To: vt, control: ctrl}
923	g.Edges = append(g.Edges, e)
924	vf.Succs = append(vf.Succs, e)
925}
926
927type Edge struct {
928	From, To *Vertex
929	control  bool
930}
931
932func (e Edge) String() string {
933	return fmt.Sprintf("%s -> %s", VertexString(e.From), VertexString(e.To))
934}
935
936func (g *Graph) FindSCCs() {
937	// use Tarjan to find the SCCs
938
939	index := 1
940	var s []*Vertex
941
942	scc := 0
943	var strongconnect func(v *Vertex)
944	strongconnect = func(v *Vertex) {
945		// set the depth index for v to the smallest unused index
946		v.index = index
947		v.lowlink = index
948		index++
949		s = append(s, v)
950		v.stack = true
951
952		for _, e := range v.Succs {
953			w := e.To
954			if w.index == 0 {
955				// successor w has not yet been visited; recurse on it
956				strongconnect(w)
957				if w.lowlink < v.lowlink {
958					v.lowlink = w.lowlink
959				}
960			} else if w.stack {
961				// successor w is in stack s and hence in the current scc
962				if w.index < v.lowlink {
963					v.lowlink = w.index
964				}
965			}
966		}
967
968		if v.lowlink == v.index {
969			for {
970				w := s[len(s)-1]
971				s = s[:len(s)-1]
972				w.stack = false
973				w.SCC = scc
974				if w == v {
975					break
976				}
977			}
978			scc++
979		}
980	}
981	for _, v := range g.Vertices {
982		if v.index == 0 {
983			strongconnect(v)
984		}
985	}
986
987	g.SCCs = make([][]*Vertex, scc)
988	for _, n := range g.Vertices {
989		n.SCC = scc - n.SCC - 1
990		g.SCCs[n.SCC] = append(g.SCCs[n.SCC], n)
991	}
992}
993
994func invertToken(tok token.Token) token.Token {
995	switch tok {
996	case token.LSS:
997		return token.GEQ
998	case token.GTR:
999		return token.LEQ
1000	case token.EQL:
1001		return token.NEQ
1002	case token.NEQ:
1003		return token.EQL
1004	case token.GEQ:
1005		return token.LSS
1006	case token.LEQ:
1007		return token.GTR
1008	default:
1009		panic(fmt.Sprintf("unsupported token %s", tok))
1010	}
1011}
1012
1013func flipToken(tok token.Token) token.Token {
1014	switch tok {
1015	case token.LSS:
1016		return token.GTR
1017	case token.GTR:
1018		return token.LSS
1019	case token.EQL:
1020		return token.EQL
1021	case token.NEQ:
1022		return token.NEQ
1023	case token.GEQ:
1024		return token.LEQ
1025	case token.LEQ:
1026		return token.GEQ
1027	default:
1028		panic(fmt.Sprintf("unsupported token %s", tok))
1029	}
1030}
1031
1032type CopyConstraint struct {
1033	aConstraint
1034	X ssa.Value
1035}
1036
1037func (c *CopyConstraint) String() string {
1038	return fmt.Sprintf("%s = copy(%s)", c.Y().Name(), c.X.Name())
1039}
1040
1041func (c *CopyConstraint) Eval(g *Graph) Range {
1042	return g.Range(c.X)
1043}
1044
1045func (c *CopyConstraint) Operands() []ssa.Value {
1046	return []ssa.Value{c.X}
1047}
1048
1049func NewCopyConstraint(x, y ssa.Value) Constraint {
1050	return &CopyConstraint{
1051		aConstraint: aConstraint{
1052			y: y,
1053		},
1054		X: x,
1055	}
1056}
1057