Analysis: fix bugs
[scilab.git] / scilab / modules / ast / src / cpp / analysis / InferenceConstraints.cpp
1 /*
2  *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3  *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
4  *
5  *  This file must be used under the terms of the CeCILL.
6  *  This source file is licensed as described in the file COPYING, which
7  *  you should have received as part of this distribution.  The terms
8  *  are also available at
9  *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
10  *
11  */
12
13 #include "gvn/InferenceConstraint.hxx"
14
15 namespace analysis
16 {
17 InferenceConstraint::Result SameDimsConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
18 {
19     const GVN::Value & R1 = *values[0];
20     const GVN::Value & C1 = *values[1];
21     const GVN::Value & R2 = *values[2];
22     const GVN::Value & C2 = *values[3];
23
24     if (R1.value == R2.value)
25     {
26         if (C1.value == C2.value)
27         {
28             return Result::RESULT_TRUE;
29         }
30
31         MultivariatePolynomial mp = *C1.poly - *C2.poly;
32         if (mp.constant != 0 && mp.isCoeffPositive(false))
33         {
34             return Result::RESULT_FALSE;
35         }
36     }
37     else
38     {
39         MultivariatePolynomial mp = *R1.poly - *R2.poly;
40         if (mp.constant > 0 && mp.isCoeffPositive(false))
41         {
42             return Result::RESULT_FALSE;
43         }
44     }
45     return Result::RESULT_DUNNO;
46 }
47
48 MPolyConstraintSet SameDimsConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
49 {
50     MPolyConstraintSet set(2);
51     const GVN::Value & R1 = *values[0];
52     const GVN::Value & C1 = *values[1];
53     const GVN::Value & R2 = *values[2];
54     const GVN::Value & C2 = *values[3];
55
56     set.add(*R1.poly - *R2.poly, MPolyConstraint::Kind::EQ0);
57     set.add(*C1.poly - *C2.poly, MPolyConstraint::Kind::EQ0);
58
59     return set;
60 }
61
62 void SameDimsConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const
63 {
64     GVN::Value & R1 = *values[0];
65     GVN::Value & C1 = *values[1];
66     GVN::Value & R2 = *values[2];
67     GVN::Value & C2 = *values[3];
68
69     applyEquality(R1, R2);
70     applyEquality(C1, C2);
71 }
72
73 InferenceConstraint::Result EqualConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
74 {
75     const GVN::Value & x = *values[0];
76     const GVN::Value & y = *values[1];
77
78     if (x.value == y.value)
79     {
80         return Result::RESULT_TRUE;
81     }
82     else
83     {
84         MultivariatePolynomial mp = *x.poly - *y.poly;
85         if (mp.constant > 0 && mp.isCoeffPositive(false))
86         {
87             return Result::RESULT_FALSE;
88         }
89     }
90     return Result::RESULT_DUNNO;
91 }
92
93 void EqualConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const
94 {
95     GVN::Value & x = *values[0];
96     GVN::Value & y = *values[1];
97
98     applyEquality(x, y);
99 }
100
101 MPolyConstraintSet EqualConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
102 {
103     MPolyConstraintSet set(1);
104     const GVN::Value & x = *values[0];
105     const GVN::Value & y = *values[1];
106
107     set.add(*x.poly - *y.poly, MPolyConstraint::Kind::EQ0);
108
109     return set;
110 }
111
112 InferenceConstraint::Result MPolyConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
113 {
114     const std::vector<const MultivariatePolynomial *> & args = InferenceConstraint::getArgs(values);
115     MultivariatePolynomial mp;
116
117     if (poly.containsVarsGEq(args.size()))
118     {
119         mp = poly.translateVariables(gvn.getCurrentValue() + 1, args.size()).eval(args);
120     }
121     else
122     {
123         mp = poly.eval(args);
124     }
125
126     switch (kind)
127     {
128         case EQ0:
129         {
130             if (mp.isConstant(0))
131             {
132                 // for all X, P(X) == 0
133                 return Result::RESULT_TRUE;
134             }
135             else if (mp.constant != 0 && mp.isCoeffPositive(false))
136             {
137                 // P(X) = Q(X) + K where K != 0 and Q with positive coeffs
138                 return Result::RESULT_FALSE;
139             }
140             else
141             {
142                 return Result::RESULT_DUNNO;
143             }
144         }
145         case NEQ0:
146             if (mp.constant != 0 && mp.isCoeffPositive(false))
147             {
148                 return Result::RESULT_TRUE;
149             }
150             else if (mp.isConstant(0))
151             {
152                 return Result::RESULT_FALSE;
153             }
154             else
155             {
156                 return Result::RESULT_DUNNO;
157             }
158         case GT0:
159             if (mp.isCoeffStrictPositive())
160             {
161                 return Result::RESULT_TRUE;
162             }
163             else if (mp.constant < 0 && mp.isCoeffNegative(false))
164             {
165                 return Result::RESULT_FALSE;
166             }
167             else
168             {
169                 return Result::RESULT_DUNNO;
170             }
171         case GEQ0:
172         {
173             if (mp.isCoeffPositive())
174             {
175                 return Result::RESULT_TRUE;
176             }
177             else if (mp.isConstant() && mp.constant < 0)
178             {
179                 return Result::RESULT_FALSE;
180             }
181             else
182             {
183                 return Result::RESULT_DUNNO;
184             }
185         }
186     }
187 }
188
189 MPolyConstraintSet MPolyConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
190 {
191     MPolyConstraintSet set(1);
192     set.add(poly.eval(InferenceConstraint::getArgs(values)), kind);
193
194     return set;
195 }
196
197 void MPolyConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const
198 {
199     if (kind == EQ0)
200     {
201         if (poly.constant == 0 && poly.polynomial.size() == 2)
202         {
203             const MultivariateMonomial & m1 = *poly.polynomial.begin();
204             const MultivariateMonomial & m2 = *std::next(poly.polynomial.begin());
205
206             if (((m1.coeff == 1 && m2.coeff == -1) || (m1.coeff == -1 && m2.coeff == 1)) && (m1.monomial.size() == 1 && m2.monomial.size() == 1))
207             {
208                 // We have a polynomial P such as P(X,Y)=X-Y
209                 GVN::Value & x = *values[m1.monomial.begin()->var];
210                 GVN::Value & y = *values[m2.monomial.begin()->var];
211
212                 applyEquality(x, y);
213             }
214         }
215     }
216 }
217
218 InferenceConstraint::Result MPolyConstraintSet::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
219 {
220     for (const auto & constraint : constraints)
221     {
222         Result res = constraint.check(gvn, values);
223         if (res != Result::RESULT_TRUE)
224         {
225             return res;
226         }
227     }
228     return Result::RESULT_TRUE;
229 }
230
231 MPolyConstraintSet MPolyConstraintSet::getMPConstraints(const std::vector<GVN::Value *> & values) const
232 {
233     MPolyConstraintSet set(constraints.size());
234     const std::vector<const MultivariatePolynomial *> args = InferenceConstraint::getArgs(values);
235     for (const auto & constraint : constraints)
236     {
237         set.add(constraint.poly.eval(args), constraint.kind);
238     }
239     return set;
240 }
241
242 void MPolyConstraintSet::applyConstraints(const std::vector<GVN::Value *> & values) const
243 {
244     for (const auto & mpc : constraints)
245     {
246         mpc.applyConstraints(values);
247     }
248 }
249
250 InferenceConstraint::Result PositiveConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
251 {
252     const GVN::Value & x = *values[0];
253
254     if (x.poly->isCoeffPositive())
255     {
256         return Result::RESULT_TRUE;
257     }
258     else if (x.poly->isConstant() && x.poly->constant < 0)
259     {
260         return Result::RESULT_FALSE;
261     }
262
263     return Result::RESULT_DUNNO;
264 }
265
266 void PositiveConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const { }
267
268 MPolyConstraintSet PositiveConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
269 {
270     MPolyConstraintSet set(1);
271     const GVN::Value & x = *values[0];
272
273     set.add(*x.poly, MPolyConstraint::Kind::GEQ0);
274
275     return set;
276 }
277
278 InferenceConstraint::Result StrictPositiveConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
279 {
280     const GVN::Value & x = *values[0];
281
282     if (x.poly->isCoeffStrictPositive())
283     {
284         return Result::RESULT_TRUE;
285     }
286     else if (x.poly->isConstant() && x.poly->constant <= 0)
287     {
288         return Result::RESULT_FALSE;
289     }
290
291     return Result::RESULT_DUNNO;
292 }
293
294 void StrictPositiveConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const { }
295
296 MPolyConstraintSet StrictPositiveConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
297 {
298     MPolyConstraintSet set(1);
299     const GVN::Value & x = *values[0];
300
301     set.add(*x.poly, MPolyConstraint::Kind::GT0);
302
303     return set;
304 }
305
306 InferenceConstraint::Result StrictGreaterConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
307 {
308     const GVN::Value & x = *values[0];
309     const GVN::Value & y = *values[1];
310
311     if (x.value == y.value)
312     {
313         return Result::RESULT_FALSE;
314     }
315
316     MultivariatePolynomial mp = *x.poly - *y.poly;
317     if (mp.constant > 0 && mp.isCoeffPositive(false))
318     {
319         return Result::RESULT_TRUE;
320     }
321     else if (mp.constant < 0 && mp.isCoeffNegative(false))
322     {
323         return Result::RESULT_FALSE;
324     }
325
326     return Result::RESULT_DUNNO;
327 }
328
329 void StrictGreaterConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const { }
330
331 MPolyConstraintSet StrictGreaterConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
332 {
333     MPolyConstraintSet set(1);
334     const GVN::Value & x = *values[0];
335     const GVN::Value & y = *values[1];
336
337     set.add(*x.poly - *y.poly, MPolyConstraint::Kind::GT0);
338
339     return set;
340 }
341
342 InferenceConstraint::Result GreaterConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
343 {
344     const GVN::Value & x = *values[0];
345     const GVN::Value & y = *values[1];
346
347     if (x.value == y.value)
348     {
349         return Result::RESULT_TRUE;
350     }
351
352     MultivariatePolynomial mp = *x.poly - *y.poly;
353     if (mp.isCoeffPositive(true))
354     {
355         return Result::RESULT_TRUE;
356     }
357     else if (mp.constant < 0 && mp.isCoeffNegative(false))
358     {
359         return Result::RESULT_FALSE;
360     }
361
362     return Result::RESULT_DUNNO;
363 }
364
365 void GreaterConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const { }
366
367 MPolyConstraintSet GreaterConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
368 {
369     MPolyConstraintSet set(1);
370     const GVN::Value & x = *values[0];
371     const GVN::Value & y = *values[1];
372
373     set.add(*x.poly - *y.poly, MPolyConstraint::Kind::GEQ0);
374
375     return set;
376 }
377
378 InferenceConstraint::Result ValidIndexConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
379 {
380     const GVN::Value & index = *values[0];
381     const GVN::Value & max = *values[1];
382     if (index.poly->constant > 0 && index.poly->isCoeffPositive(false))
383     {
384         // the index is geq than 1
385         MultivariatePolynomial mp = *max.poly - *index.poly;
386         if (mp.isCoeffPositive())
387         {
388             // max - index >= 0
389             return Result::RESULT_TRUE;
390         }
391         else if (mp.isConstant() && mp.constant < 0)
392         {
393             return Result::RESULT_FALSE;
394         }
395     }
396     else if (index.poly->isConstant() && index.poly->constant < 1)
397     {
398         return Result::RESULT_FALSE;
399     }
400
401     return Result::RESULT_DUNNO;
402 }
403
404 void ValidIndexConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const { }
405
406 MPolyConstraintSet ValidIndexConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
407 {
408     MPolyConstraintSet set(2);
409     const GVN::Value & index = *values[0];
410     const GVN::Value & max = *values[1];
411
412     set.add(*max.poly - *index.poly, MPolyConstraint::Kind::GEQ0);
413     set.add(*index.poly - 1, MPolyConstraint::Kind::GEQ0);
414
415     return set;
416 }
417
418 InferenceConstraint::Result ValidRangeConstraint::check(GVN & gvn, const std::vector<GVN::Value *> & values) const
419 {
420     const GVN::Value & index_min = *values[0];
421     const GVN::Value & index_max = *values[1];
422     const GVN::Value & min = *values[2];
423     const GVN::Value & max = *values[3];
424
425     MultivariatePolynomial mp_min = *index_min.poly - *min.poly;
426     if (mp_min.isCoeffPositive())
427     {
428         MultivariatePolynomial mp_max = *max.poly - *index_max.poly;
429         if (mp_max.isCoeffPositive())
430         {
431             return Result::RESULT_TRUE;
432         }
433         else if (mp_max.isConstant() && mp_max.constant < 0)
434         {
435             return Result::RESULT_FALSE;
436         }
437     }
438     else if (mp_min.isConstant() && mp_min.constant < 0)
439     {
440         return Result::RESULT_FALSE;
441     }
442
443     return Result::RESULT_DUNNO;
444 }
445
446 void ValidRangeConstraint::applyConstraints(const std::vector<GVN::Value *> & values) const { }
447
448 MPolyConstraintSet ValidRangeConstraint::getMPConstraints(const std::vector<GVN::Value *> & values) const
449 {
450     MPolyConstraintSet set(4);
451     const GVN::Value & index_min = *values[0];
452     const GVN::Value & index_max = *values[1];
453     const GVN::Value & min = *values[2];
454     const GVN::Value & max = *values[3];
455
456     set.add(*index_min.poly - *min.poly, MPolyConstraint::Kind::GEQ0);
457     set.add(*max.poly - *index_max.poly, MPolyConstraint::Kind::GEQ0);
458
459     return set;
460 }
461 }