Analysis: Add DollarInfo, VarPromotion, and move var clone at the right place when...
[scilab.git] / scilab / modules / ast / includes / analysis / tools.hxx
1 /*
2  *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3  *  Copyright (C) 2014 - 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 #ifndef __TOOLS_HXX__
14 #define __TOOLS_HXX__
15
16 #include <bitset>
17 #include <cmath>
18 #include <cstdint>
19 #include <iostream>
20 #include <limits>
21 #include <map>
22 #include <set>
23 #include <unordered_map>
24 #include <unordered_set>
25
26 #ifdef _MSC_VER
27 #include "stdint.h"
28 #include <intrin.h>
29 #endif
30
31 #include "core_math.h"
32 #include "symbol.hxx"
33
34 namespace analysis
35 {
36
37 namespace tools
38 {
39
40 #ifdef _MSC_VER
41 inline static double trunc(const double x)
42 {
43     return x > 0 ? floor(x) : ceil(x);
44 }
45
46 inline static uint32_t clz(const uint32_t x)
47 {
48     unsigned long r = 0;
49     _BitScanForward(&r, x);
50     return r;
51 }
52
53 inline static uint32_t clzll(const uint64_t x)
54 {
55 #ifdef _WIN64
56     unsigned long r = 0;
57     _BitScanForward64(&r, x);
58     return r;
59 #else
60     const uint32_t u32 = x >> 32;
61     if (u32)
62     {
63         return clz(u32);
64     }
65     return 32 + clz(x & 0xFFFFFFFFUL);
66 #endif
67 }
68 #else
69 inline static double trunc(const double x)
70 {
71 #ifdef __APPLE__
72     // Needed for compilation with GCC 4.8.2
73     return x > 0 ? floor(x) : ceil(x);
74 #else
75     return std::trunc(x);
76 #endif
77 }
78
79 inline static uint32_t clz(const uint32_t x)
80 {
81     return x ? __builtin_clz(x) : 32;
82 }
83
84 inline static uint32_t clzll(const uint64_t x)
85 {
86     return x ? __builtin_clzll(x) : 64;
87 }
88 #endif
89
90 inline static double NaN()
91 {
92     return std::numeric_limits<double>::quiet_NaN();
93 }
94
95 inline static bool isNaN(const double x)
96 {
97     return ISNAN(x) != 0;
98 }
99
100 inline static bool isFinite(const double x)
101 {
102     return finite(x) != 0;
103 }
104
105 inline static bool isInfinite(const double x)
106 {
107     return !isFinite(x);
108 }
109
110 enum IntType { NOTANINT, SIGNED, UNSIGNED };
111
112 inline static IntType getIntType(const double x)
113 {
114     if (x == trunc(x))
115     {
116         if (x >= 0)
117         {
118             if (x <= (double)std::numeric_limits<uint64_t>::max())
119             {
120                 return UNSIGNED;
121             }
122         }
123         else if (x >= (double)std::numeric_limits<int64_t>::min())
124         {
125             return SIGNED;
126         }
127     }
128
129     return NOTANINT;
130 }
131
132 template<typename T>
133 inline static bool asInteger(const double x, T & ival)
134 {
135     if (x == trunc(x))
136     {
137         if (x >= 0)
138         {
139             if (x <= (double)std::numeric_limits<T>::max())
140             {
141                 ival = (T)x;
142                 return true;
143             }
144         }
145         else if (x >= (double)std::numeric_limits<T>::min())
146         {
147             ival = (T)x;
148             return true;
149         }
150     }
151
152     return false;
153 }
154
155 inline static bool isAnInt(const double x)
156 {
157     return getIntType(x) != NOTANINT;
158 }
159
160 template<typename T>
161 inline static T cast(const double x)
162 {
163     if (x < static_cast<double>(std::numeric_limits<T>::max()))
164     {
165         if (x > static_cast<double>(std::numeric_limits<T>::min()))
166         {
167             return static_cast<T>(x);
168         }
169         else
170         {
171             return std::numeric_limits<T>::min();
172         }
173     }
174     else
175     {
176         return std::numeric_limits<T>::max();
177     }
178 }
179
180 template<typename T>
181 inline static T powui(T x, uint64_t n)
182 {
183     T p = x;
184     T y = (n & 1) ? x : 1;
185
186     while (n >>= 1)
187     {
188         p *= p;
189         if (n & 1)
190         {
191             y *= p;
192         }
193     }
194
195     return y;
196 }
197
198 inline std::wostream & operator<<(std::wostream & out, const IntType & it)
199 {
200     switch (it)
201     {
202         case IntType::NOTANINT :
203             out << L"NAI";
204             break;
205         case IntType::SIGNED :
206             out << L'S';
207             break;
208         case IntType::UNSIGNED :
209             out << L'U';
210             break;
211     }
212     return out;
213 }
214
215 template<typename T>
216 inline static unsigned char popcount(const T x)
217 {
218     return std::bitset<sizeof(T)>(x).count();
219 }
220
221 inline static unsigned char log2(const unsigned int x)
222 {
223     return (unsigned char)((sizeof(unsigned int) << 3) - clz(x) - 1);
224 }
225
226 inline static unsigned char log2(const unsigned long long x)
227 {
228     return (unsigned char)((sizeof(unsigned long long) << 3) - clzll(x) - 1);
229 }
230
231 template<typename T>
232 static void printSet(const T & set, std::wostream & out)
233 {
234     if (set.empty())
235     {
236         out << L"{}";
237     }
238     else
239     {
240         out << L'{';
241         for (typename T::const_iterator i = set.begin(); i != set.end(); ++i)
242         {
243             if (std::next(i) == set.end())
244             {
245                 out << *i << L'}';
246             }
247             else
248             {
249                 out << *i << L',';
250             }
251         }
252     }
253 }
254
255 template<typename T>
256 static void printMap(const T & map, std::wostream & out, const bool newLine = false )
257 {
258     if (map.empty())
259     {
260         out << L"{}";
261     }
262     else
263     {
264         out << L'{';
265         for (typename T::const_iterator i = map.begin(); i != map.end(); ++i)
266         {
267             out << i->first << L" -> " << i->second;
268             if (std::next(i) == map.end())
269             {
270                 out << L'}';
271             }
272             else
273             {
274                 out << L',';
275                 if (newLine)
276                 {
277                     out << L'\n';
278                 }
279             }
280         }
281     }
282 }
283
284 template<typename T>
285 static void printMapInfo(std::wostream & out, const T & map, const bool show_collisions = false)
286 {
287     double mean = 0;
288     double variance = 0;
289     const unsigned int count = map.bucket_count();
290     unsigned int empty_bucket_count = 0;
291     unsigned int collision_count = 0;
292
293     out << L"Map size: " << map.size() << std::endl;
294     out << L"Number of buckets: " << count << std::endl;
295
296     for (unsigned int i = 0; i < count; ++i)
297     {
298         if (const unsigned int s = map.bucket_size(i))
299         {
300             mean += (double)s;
301             if (s > 1)
302             {
303                 ++collision_count;
304             }
305         }
306         else
307         {
308             ++empty_bucket_count;
309         }
310     }
311     mean /= (double)count;
312
313     for (unsigned int i = 0; i < count; ++i)
314     {
315         const double ms = mean - (double)map.bucket_size(i);
316         variance += ms * ms;
317     }
318     variance /= (double)count;
319
320     out << L"Number of elements by buckets: mean=" << mean << L", sigma=" << std::sqrt(variance) << std::endl;
321     out << L"Number of empty buckets: " << empty_bucket_count << std::endl;
322     out << L"Number of collisions: " << collision_count << std::endl;
323
324     if (show_collisions)
325     {
326         std::multimap<unsigned int, typename T::key_type> collisions;
327         for (const auto & p : map)
328         {
329             collisions.emplace(map.bucket(p.first), p.first);
330         }
331
332         for (const auto & p : collisions)
333         {
334             out << L"Bucket " << p.first << L": " << p.second << L", hash=" << (typename T::hasher()(p.second)) << std::endl;
335         }
336     }
337 }
338
339 inline static std::size_t hash_combine(const std::size_t seed)
340 {
341     return seed;
342 }
343
344 template<typename... Args>
345 inline static std::size_t hash_combine(const std::size_t seed, Args... args)
346 {
347     // it is the way Boost has implemented hash_combine:
348     // http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html
349     return seed ^ (hash_combine(args...) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
350 }
351
352 struct HashSymbol
353 {
354     inline std::size_t operator()(const symbol::Symbol & sym) const
355     {
356         return std::hash<std::wstring>()(sym.getName());
357     }
358 };
359
360 struct EqSymbol
361 {
362     inline bool operator()(const symbol::Symbol & L, const symbol::Symbol & R) const
363     {
364         return L == R;
365     }
366 };
367
368 typedef std::set<symbol::Symbol> SymbolOrdSet;
369 typedef std::unordered_set<symbol::Symbol, HashSymbol> SymbolSet;
370 template<typename T>
371 using SymbolMap = std::unordered_map<symbol::Symbol, T, HashSymbol, EqSymbol>;
372
373 } // namespace tools
374
375 } // namespace analysis
376
377 #endif // __TOOLS_HXX__