1package vrp
2
3// TODO(dh): most of the constraints have implementations identical to
4// that of strings. Consider reusing them.
5
6import (
7	"fmt"
8	"go/types"
9
10	"honnef.co/go/tools/ssa"
11)
12
13type SliceInterval struct {
14	Length IntInterval
15}
16
17func (s SliceInterval) Union(other Range) Range {
18	i, ok := other.(SliceInterval)
19	if !ok {
20		i = SliceInterval{EmptyIntInterval}
21	}
22	if s.Length.Empty() || !s.Length.IsKnown() {
23		return i
24	}
25	if i.Length.Empty() || !i.Length.IsKnown() {
26		return s
27	}
28	return SliceInterval{
29		Length: s.Length.Union(i.Length).(IntInterval),
30	}
31}
32func (s SliceInterval) String() string { return s.Length.String() }
33func (s SliceInterval) IsKnown() bool  { return s.Length.IsKnown() }
34
35type SliceAppendConstraint struct {
36	aConstraint
37	A ssa.Value
38	B ssa.Value
39}
40
41type SliceSliceConstraint struct {
42	aConstraint
43	X     ssa.Value
44	Lower ssa.Value
45	Upper ssa.Value
46}
47
48type ArraySliceConstraint struct {
49	aConstraint
50	X     ssa.Value
51	Lower ssa.Value
52	Upper ssa.Value
53}
54
55type SliceIntersectionConstraint struct {
56	aConstraint
57	X ssa.Value
58	I IntInterval
59}
60
61type SliceLengthConstraint struct {
62	aConstraint
63	X ssa.Value
64}
65
66type MakeSliceConstraint struct {
67	aConstraint
68	Size ssa.Value
69}
70
71type SliceIntervalConstraint struct {
72	aConstraint
73	I IntInterval
74}
75
76func NewSliceAppendConstraint(a, b, y ssa.Value) Constraint {
77	return &SliceAppendConstraint{NewConstraint(y), a, b}
78}
79func NewSliceSliceConstraint(x, lower, upper, y ssa.Value) Constraint {
80	return &SliceSliceConstraint{NewConstraint(y), x, lower, upper}
81}
82func NewArraySliceConstraint(x, lower, upper, y ssa.Value) Constraint {
83	return &ArraySliceConstraint{NewConstraint(y), x, lower, upper}
84}
85func NewSliceIntersectionConstraint(x ssa.Value, i IntInterval, y ssa.Value) Constraint {
86	return &SliceIntersectionConstraint{NewConstraint(y), x, i}
87}
88func NewSliceLengthConstraint(x, y ssa.Value) Constraint {
89	return &SliceLengthConstraint{NewConstraint(y), x}
90}
91func NewMakeSliceConstraint(size, y ssa.Value) Constraint {
92	return &MakeSliceConstraint{NewConstraint(y), size}
93}
94func NewSliceIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
95	return &SliceIntervalConstraint{NewConstraint(y), i}
96}
97
98func (c *SliceAppendConstraint) Operands() []ssa.Value { return []ssa.Value{c.A, c.B} }
99func (c *SliceSliceConstraint) Operands() []ssa.Value {
100	ops := []ssa.Value{c.X}
101	if c.Lower != nil {
102		ops = append(ops, c.Lower)
103	}
104	if c.Upper != nil {
105		ops = append(ops, c.Upper)
106	}
107	return ops
108}
109func (c *ArraySliceConstraint) Operands() []ssa.Value {
110	ops := []ssa.Value{c.X}
111	if c.Lower != nil {
112		ops = append(ops, c.Lower)
113	}
114	if c.Upper != nil {
115		ops = append(ops, c.Upper)
116	}
117	return ops
118}
119func (c *SliceIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
120func (c *SliceLengthConstraint) Operands() []ssa.Value       { return []ssa.Value{c.X} }
121func (c *MakeSliceConstraint) Operands() []ssa.Value         { return []ssa.Value{c.Size} }
122func (s *SliceIntervalConstraint) Operands() []ssa.Value     { return nil }
123
124func (c *SliceAppendConstraint) String() string {
125	return fmt.Sprintf("%s = append(%s, %s)", c.Y().Name(), c.A.Name(), c.B.Name())
126}
127func (c *SliceSliceConstraint) String() string {
128	var lname, uname string
129	if c.Lower != nil {
130		lname = c.Lower.Name()
131	}
132	if c.Upper != nil {
133		uname = c.Upper.Name()
134	}
135	return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
136}
137func (c *ArraySliceConstraint) String() string {
138	var lname, uname string
139	if c.Lower != nil {
140		lname = c.Lower.Name()
141	}
142	if c.Upper != nil {
143		uname = c.Upper.Name()
144	}
145	return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
146}
147func (c *SliceIntersectionConstraint) String() string {
148	return fmt.Sprintf("%s = %s.%t ⊓ %s", c.Y().Name(), c.X.Name(), c.Y().(*ssa.Sigma).Branch, c.I)
149}
150func (c *SliceLengthConstraint) String() string {
151	return fmt.Sprintf("%s = len(%s)", c.Y().Name(), c.X.Name())
152}
153func (c *MakeSliceConstraint) String() string {
154	return fmt.Sprintf("%s = make(slice, %s)", c.Y().Name(), c.Size.Name())
155}
156func (c *SliceIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
157
158func (c *SliceAppendConstraint) Eval(g *Graph) Range {
159	l1 := g.Range(c.A).(SliceInterval).Length
160	var l2 IntInterval
161	switch r := g.Range(c.B).(type) {
162	case SliceInterval:
163		l2 = r.Length
164	case StringInterval:
165		l2 = r.Length
166	default:
167		return SliceInterval{}
168	}
169	if !l1.IsKnown() || !l2.IsKnown() {
170		return SliceInterval{}
171	}
172	return SliceInterval{
173		Length: l1.Add(l2),
174	}
175}
176func (c *SliceSliceConstraint) Eval(g *Graph) Range {
177	lr := NewIntInterval(NewZ(0), NewZ(0))
178	if c.Lower != nil {
179		lr = g.Range(c.Lower).(IntInterval)
180	}
181	ur := g.Range(c.X).(SliceInterval).Length
182	if c.Upper != nil {
183		ur = g.Range(c.Upper).(IntInterval)
184	}
185	if !lr.IsKnown() || !ur.IsKnown() {
186		return SliceInterval{}
187	}
188
189	ls := []Z{
190		ur.Lower.Sub(lr.Lower),
191		ur.Upper.Sub(lr.Lower),
192		ur.Lower.Sub(lr.Upper),
193		ur.Upper.Sub(lr.Upper),
194	}
195	// TODO(dh): if we don't truncate lengths to 0 we might be able to
196	// easily detect slices with high < low. we'd need to treat -∞
197	// specially, though.
198	for i, l := range ls {
199		if l.Sign() == -1 {
200			ls[i] = NewZ(0)
201		}
202	}
203
204	return SliceInterval{
205		Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
206	}
207}
208func (c *ArraySliceConstraint) Eval(g *Graph) Range {
209	lr := NewIntInterval(NewZ(0), NewZ(0))
210	if c.Lower != nil {
211		lr = g.Range(c.Lower).(IntInterval)
212	}
213	var l int64
214	switch typ := c.X.Type().(type) {
215	case *types.Array:
216		l = typ.Len()
217	case *types.Pointer:
218		l = typ.Elem().(*types.Array).Len()
219	}
220	ur := NewIntInterval(NewZ(l), NewZ(l))
221	if c.Upper != nil {
222		ur = g.Range(c.Upper).(IntInterval)
223	}
224	if !lr.IsKnown() || !ur.IsKnown() {
225		return SliceInterval{}
226	}
227
228	ls := []Z{
229		ur.Lower.Sub(lr.Lower),
230		ur.Upper.Sub(lr.Lower),
231		ur.Lower.Sub(lr.Upper),
232		ur.Upper.Sub(lr.Upper),
233	}
234	// TODO(dh): if we don't truncate lengths to 0 we might be able to
235	// easily detect slices with high < low. we'd need to treat -∞
236	// specially, though.
237	for i, l := range ls {
238		if l.Sign() == -1 {
239			ls[i] = NewZ(0)
240		}
241	}
242
243	return SliceInterval{
244		Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
245	}
246}
247func (c *SliceIntersectionConstraint) Eval(g *Graph) Range {
248	xi := g.Range(c.X).(SliceInterval)
249	if !xi.IsKnown() {
250		return c.I
251	}
252	return SliceInterval{
253		Length: xi.Length.Intersection(c.I),
254	}
255}
256func (c *SliceLengthConstraint) Eval(g *Graph) Range {
257	i := g.Range(c.X).(SliceInterval).Length
258	if !i.IsKnown() {
259		return NewIntInterval(NewZ(0), PInfinity)
260	}
261	return i
262}
263func (c *MakeSliceConstraint) Eval(g *Graph) Range {
264	i, ok := g.Range(c.Size).(IntInterval)
265	if !ok {
266		return SliceInterval{NewIntInterval(NewZ(0), PInfinity)}
267	}
268	if i.Lower.Sign() == -1 {
269		i.Lower = NewZ(0)
270	}
271	return SliceInterval{i}
272}
273func (c *SliceIntervalConstraint) Eval(*Graph) Range { return SliceInterval{c.I} }
274