1package vrp
2
3import (
4	"fmt"
5	"go/token"
6	"go/types"
7
8	"honnef.co/go/tools/ssa"
9)
10
11type StringInterval struct {
12	Length IntInterval
13}
14
15func (s StringInterval) Union(other Range) Range {
16	i, ok := other.(StringInterval)
17	if !ok {
18		i = StringInterval{EmptyIntInterval}
19	}
20	if s.Length.Empty() || !s.Length.IsKnown() {
21		return i
22	}
23	if i.Length.Empty() || !i.Length.IsKnown() {
24		return s
25	}
26	return StringInterval{
27		Length: s.Length.Union(i.Length).(IntInterval),
28	}
29}
30
31func (s StringInterval) String() string {
32	return s.Length.String()
33}
34
35func (s StringInterval) IsKnown() bool {
36	return s.Length.IsKnown()
37}
38
39type StringSliceConstraint struct {
40	aConstraint
41	X     ssa.Value
42	Lower ssa.Value
43	Upper ssa.Value
44}
45
46type StringIntersectionConstraint struct {
47	aConstraint
48	ranges   Ranges
49	A        ssa.Value
50	B        ssa.Value
51	Op       token.Token
52	I        IntInterval
53	resolved bool
54}
55
56type StringConcatConstraint struct {
57	aConstraint
58	A ssa.Value
59	B ssa.Value
60}
61
62type StringLengthConstraint struct {
63	aConstraint
64	X ssa.Value
65}
66
67type StringIntervalConstraint struct {
68	aConstraint
69	I IntInterval
70}
71
72func NewStringSliceConstraint(x, lower, upper, y ssa.Value) Constraint {
73	return &StringSliceConstraint{NewConstraint(y), x, lower, upper}
74}
75func NewStringIntersectionConstraint(a, b ssa.Value, op token.Token, ranges Ranges, y ssa.Value) Constraint {
76	return &StringIntersectionConstraint{
77		aConstraint: NewConstraint(y),
78		ranges:      ranges,
79		A:           a,
80		B:           b,
81		Op:          op,
82	}
83}
84func NewStringConcatConstraint(a, b, y ssa.Value) Constraint {
85	return &StringConcatConstraint{NewConstraint(y), a, b}
86}
87func NewStringLengthConstraint(x ssa.Value, y ssa.Value) Constraint {
88	return &StringLengthConstraint{NewConstraint(y), x}
89}
90func NewStringIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
91	return &StringIntervalConstraint{NewConstraint(y), i}
92}
93
94func (c *StringSliceConstraint) Operands() []ssa.Value {
95	vs := []ssa.Value{c.X}
96	if c.Lower != nil {
97		vs = append(vs, c.Lower)
98	}
99	if c.Upper != nil {
100		vs = append(vs, c.Upper)
101	}
102	return vs
103}
104func (c *StringIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.A} }
105func (c StringConcatConstraint) Operands() []ssa.Value        { return []ssa.Value{c.A, c.B} }
106func (c *StringLengthConstraint) Operands() []ssa.Value       { return []ssa.Value{c.X} }
107func (s *StringIntervalConstraint) Operands() []ssa.Value     { return nil }
108
109func (c *StringSliceConstraint) String() string {
110	var lname, uname string
111	if c.Lower != nil {
112		lname = c.Lower.Name()
113	}
114	if c.Upper != nil {
115		uname = c.Upper.Name()
116	}
117	return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
118}
119func (c *StringIntersectionConstraint) String() string {
120	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)
121}
122func (c StringConcatConstraint) String() string {
123	return fmt.Sprintf("%s = %s + %s", c.Y().Name(), c.A.Name(), c.B.Name())
124}
125func (c *StringLengthConstraint) String() string {
126	return fmt.Sprintf("%s = len(%s)", c.Y().Name(), c.X.Name())
127}
128func (c *StringIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
129
130func (c *StringSliceConstraint) Eval(g *Graph) Range {
131	lr := NewIntInterval(NewZ(0), NewZ(0))
132	if c.Lower != nil {
133		lr = g.Range(c.Lower).(IntInterval)
134	}
135	ur := g.Range(c.X).(StringInterval).Length
136	if c.Upper != nil {
137		ur = g.Range(c.Upper).(IntInterval)
138	}
139	if !lr.IsKnown() || !ur.IsKnown() {
140		return StringInterval{}
141	}
142
143	ls := []Z{
144		ur.Lower.Sub(lr.Lower),
145		ur.Upper.Sub(lr.Lower),
146		ur.Lower.Sub(lr.Upper),
147		ur.Upper.Sub(lr.Upper),
148	}
149	// TODO(dh): if we don't truncate lengths to 0 we might be able to
150	// easily detect slices with high < low. we'd need to treat -∞
151	// specially, though.
152	for i, l := range ls {
153		if l.Sign() == -1 {
154			ls[i] = NewZ(0)
155		}
156	}
157
158	return StringInterval{
159		Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
160	}
161}
162func (c *StringIntersectionConstraint) Eval(g *Graph) Range {
163	var l IntInterval
164	switch r := g.Range(c.A).(type) {
165	case StringInterval:
166		l = r.Length
167	case IntInterval:
168		l = r
169	}
170
171	if !l.IsKnown() {
172		return StringInterval{c.I}
173	}
174	return StringInterval{
175		Length: l.Intersection(c.I),
176	}
177}
178func (c StringConcatConstraint) Eval(g *Graph) Range {
179	i1, i2 := g.Range(c.A).(StringInterval), g.Range(c.B).(StringInterval)
180	if !i1.Length.IsKnown() || !i2.Length.IsKnown() {
181		return StringInterval{}
182	}
183	return StringInterval{
184		Length: i1.Length.Add(i2.Length),
185	}
186}
187func (c *StringLengthConstraint) Eval(g *Graph) Range {
188	i := g.Range(c.X).(StringInterval).Length
189	if !i.IsKnown() {
190		return NewIntInterval(NewZ(0), PInfinity)
191	}
192	return i
193}
194func (c *StringIntervalConstraint) Eval(*Graph) Range { return StringInterval{c.I} }
195
196func (c *StringIntersectionConstraint) Futures() []ssa.Value {
197	return []ssa.Value{c.B}
198}
199
200func (c *StringIntersectionConstraint) Resolve() {
201	if (c.A.Type().Underlying().(*types.Basic).Info() & types.IsString) != 0 {
202		// comparing two strings
203		r, ok := c.ranges[c.B].(StringInterval)
204		if !ok {
205			c.I = NewIntInterval(NewZ(0), PInfinity)
206			return
207		}
208		switch c.Op {
209		case token.EQL:
210			c.I = r.Length
211		case token.GTR, token.GEQ:
212			c.I = NewIntInterval(r.Length.Lower, PInfinity)
213		case token.LSS, token.LEQ:
214			c.I = NewIntInterval(NewZ(0), r.Length.Upper)
215		case token.NEQ:
216		default:
217			panic("unsupported op " + c.Op.String())
218		}
219	} else {
220		r, ok := c.ranges[c.B].(IntInterval)
221		if !ok {
222			c.I = NewIntInterval(NewZ(0), PInfinity)
223			return
224		}
225		// comparing two lengths
226		switch c.Op {
227		case token.EQL:
228			c.I = r
229		case token.GTR:
230			c.I = NewIntInterval(r.Lower.Add(NewZ(1)), PInfinity)
231		case token.GEQ:
232			c.I = NewIntInterval(r.Lower, PInfinity)
233		case token.LSS:
234			c.I = NewIntInterval(NInfinity, r.Upper.Sub(NewZ(1)))
235		case token.LEQ:
236			c.I = NewIntInterval(NInfinity, r.Upper)
237		case token.NEQ:
238		default:
239			panic("unsupported op " + c.Op.String())
240		}
241	}
242}
243
244func (c *StringIntersectionConstraint) IsKnown() bool {
245	return c.I.IsKnown()
246}
247
248func (c *StringIntersectionConstraint) MarkUnresolved() {
249	c.resolved = false
250}
251
252func (c *StringIntersectionConstraint) MarkResolved() {
253	c.resolved = true
254}
255
256func (c *StringIntersectionConstraint) IsResolved() bool {
257	return c.resolved
258}
259