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