Improvements to aggregation code and fucntion library
[com/gs-lite.git] / src / ftacmp / parse_partn.cc
1 /* ------------------------------------------------
2 Copyright 2014 AT&T Intellectual Property
3    Licensed under the Apache License, Version 2.0 (the "License");
4    you may not use this file except in compliance with the License.
5    You may obtain a copy of the License at
6
7      http://www.apache.org/licenses/LICENSE-2.0
8
9    Unless required by applicable law or agreed to in writing, software
10    distributed under the License is distributed on an "AS IS" BASIS,
11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12    See the License for the specific language governing permissions and
13    limitations under the License.
14  ------------------------------------------- */
15 #include"parse_partn.h"
16 #include "parse_schema.h"
17 #include"analyze_fta.h"
18
19
20 using namespace std;
21
22
23 int find_field(scalarexp_t *se, string &fld){
24         vector<scalarexp_t *> operands;
25         int o,ret=0;
26
27         switch(se->get_operator_type()){
28         case SE_LITERAL:
29                 return 0;
30         case SE_PARAM:
31         case SE_IFACE_PARAM:
32                 return 100;             // force failure, but no error message.
33         case SE_UNARY_OP:
34                 return find_field(se->get_left_se(), fld);
35         case SE_BINARY_OP:
36                 return find_field(se->get_left_se(), fld)+find_field(se->get_right_se(), fld);
37         case SE_COLREF:
38                 fld = se->get_colref()->get_field();
39                 return 1;
40         case SE_AGGR_STAR:
41         case SE_AGGR_SE:
42 //                      Should be no aggregates
43                 return 0;
44         case SE_FUNC:
45                 return 100;             // force failure, but no error message.
46         default:
47                 fprintf(stderr,"INTERNAL ERROR in find_field, unknown operator type %d\n", se->get_operator_type());
48                 return(-100);
49         }
50         return(-100);
51 }
52
53
54 int partn_def_t::verify(table_list *schema, string &err_msg){
55         if(schema->find_tbl(protocol) < 0){
56                 err_msg += "ERROR, partition definition "+name+" uses source "+protocol+", but its not in the schema.\n";
57                 return 1;
58         }
59         if(schema->get_schema_type(schema->find_tbl(protocol)) != PROTOCOL_SCHEMA){
60                 err_msg += "ERROR, partition definition "+name+" uses source "+protocol+", but its not a PROTOCOL.\n";
61                 return 1;
62         }
63
64         tablevar_t *fme = new tablevar_t(protocol.c_str());
65         tablevar_list_t fm(fme);
66
67 //              Validate the SE and assign data types.
68         int i;
69         int retval = 0;
70         for(i=0;i<se_list.size();++i){
71                 int ret = verify_colref(se_list[i],&fm,schema,NULL);
72                 if(ret){
73                         err_msg += "ERROR validating entry "+int_to_string(i)+" of partition definition "+name+".\n";
74                         retval=1;
75                 }
76         }
77         if(retval)
78                 return 1;
79
80 //              Ensure that the data type is an integer type.
81         for(i=0;i<se_list.size();++i){
82                 data_type *dt = se_list[i]->get_data_type();
83                 string type_s = dt->get_type_str();
84                 if(! ( type_s=="UINT" || type_s=="INT" || type_s=="ULLONG" || type_s=="LLONG") ){
85                         err_msg += "ERROR, entry "+int_to_string(i)+" of partition definition "+name+" has type "+type_s+", but it must be one of UINT, INT, ULLONG, LLONG.\n";
86                         retval=1;
87                 }
88         }
89         if(retval)
90                 return 1;
91
92 //              Ensure that each SE ref's a field only once.
93         for(i=0;i<se_list.size();++i){
94                 string fld;
95                 int ret = find_field(se_list[i],fld);
96                 if(ret<0){
97                         err_msg += "ERROR validating entry "+int_to_string(i)+" of partition definition "+name+".\n";
98                         retval=1;
99                 }
100                 if(ret!=1){
101                         err_msg += "ERROR validating entry "+int_to_string(i)+" of partition definition "+name+": the expression references a field "+int_to_string(ret)+" times, but it should reference a field exactly once.\n";
102                         retval=1;
103                         field_list.push_back("");
104                 }else{
105                         field_list.push_back(fld);
106                 }
107         }
108         if(retval)
109                 return 1;
110
111         return 0;
112
113 }
114
115 void find_colref_path(scalarexp_t *se, vector<scalarexp_t *> &se_stack){
116         vector<scalarexp_t *> operands;
117         int o,ret=0;
118
119         switch(se->get_operator_type()){
120         case SE_LITERAL:
121         case SE_PARAM:
122         case SE_IFACE_PARAM:
123                 return ;
124         case SE_UNARY_OP:
125                 find_colref_path(se->get_left_se(), se_stack);
126                 if(se_stack.size()>0)
127                         se_stack.push_back(se);
128                 return;
129         case SE_BINARY_OP:
130                 find_colref_path(se->get_left_se(), se_stack);
131                 if(se_stack.size()>0){
132                         se_stack.push_back(se);
133                         return;
134                 }
135                 find_colref_path(se->get_right_se(), se_stack);
136                 if(se_stack.size()>0)
137                         se_stack.push_back(se);
138                 return;
139         case SE_COLREF:
140                 se_stack.push_back(se);
141                 return;
142         case SE_AGGR_STAR:
143         case SE_AGGR_SE:
144 //                      Should be no aggregates
145                 return;
146         case SE_FUNC:
147                 operands = se->get_operands();
148                 for(o=0;o<operands.size();o++){
149                         find_colref_path(operands[o], se_stack);
150                         if(se_stack.size()>0){
151                                 se_stack.push_back(se);
152                                 return;
153                         }
154                 }
155                 return;
156         default:
157                 fprintf(stderr,"INTERNAL ERROR in find_colref_path, unknown operator type %d\n", se->get_operator_type());
158                 return;
159         }
160         return;
161 }
162
163 struct param_int{
164         union{
165                 long int li;
166                 unsigned long int uli;
167                 long long int lli;
168                 unsigned long long int ulli;
169         } v;
170     dtype d;
171
172         void convert_to_final() {};
173
174         void load_val(dtype dt, const char *val){
175                 d=dt;
176                 switch(dt){
177                 case u_int_t:
178                         sscanf(val,"%llu",&(v.ulli));
179                         break;
180                 case int_t:
181                         sscanf(val,"%lld",&(v.lli));
182                         break;
183                 case u_llong_t:
184                         sscanf(val,"%llu",&(v.ulli));
185                         break;
186                 case llong_t:
187                         sscanf(val,"%lld",&(v.lli));
188                         break;
189                 default:
190                         fprintf(stderr,"INTERNAL ERROR, data type %d passed to param_int::load_val.\n",dt);
191                         exit(1);
192                 }
193         }
194
195         void add(dtype dt, param_int &l, param_int &r){
196                 d=dt;
197                 if(dt==int_t || dt==llong_t)
198                         if(l.d==int_t || l.d==llong_t)
199                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli+r.v.lli; else v.lli = l.v.lli+r.v.ulli;
200                         else
201                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli+r.v.lli; else v.lli = l.v.ulli+r.v.ulli;
202                 else
203                         if(l.d==int_t || l.d==llong_t)
204                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli+r.v.lli; else v.ulli = l.v.lli+r.v.ulli;
205                         else
206                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli+r.v.lli; else v.ulli = l.v.ulli+r.v.ulli;
207         }
208         void subtract(dtype dt, param_int &l, param_int &r){
209                 d=dt;
210                 if(dt==int_t || dt==llong_t)
211                         if(l.d==int_t || l.d==llong_t)
212                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli-r.v.lli; else v.lli = l.v.lli-r.v.ulli;
213                         else
214                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli-r.v.lli; else v.lli = l.v.ulli-r.v.ulli;
215                 else
216                         if(l.d==int_t || l.d==llong_t)
217                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli-r.v.lli; else v.ulli = l.v.lli-r.v.ulli;
218                         else
219                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli-r.v.lli; else v.ulli = l.v.ulli-r.v.ulli;
220         }
221         void mult(dtype dt, param_int &l, param_int &r){
222                 d=dt;
223                 if(dt==int_t || dt==llong_t)
224                         if(l.d==int_t || l.d==llong_t)
225                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli*r.v.lli; else v.lli = l.v.lli*r.v.ulli;
226                         else
227                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli*r.v.lli; else v.lli = l.v.ulli*r.v.ulli;
228                 else
229                         if(l.d==int_t || l.d==llong_t)
230                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli*r.v.lli; else v.ulli = l.v.lli*r.v.ulli;
231                         else
232                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli*r.v.lli; else v.ulli = l.v.ulli*r.v.ulli;
233         }
234         void div(dtype dt, param_int &l, param_int &r){
235                 d=dt;
236                 if(dt==int_t || dt==llong_t)
237                         if(l.d==int_t || l.d==llong_t)
238                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli/r.v.lli; else v.lli = l.v.lli/r.v.ulli;
239                         else
240                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli/r.v.lli; else v.lli = l.v.ulli/r.v.ulli;
241                 else
242                         if(l.d==int_t || l.d==llong_t)
243                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli/r.v.lli; else v.ulli = l.v.lli/r.v.ulli;
244                         else
245                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli/r.v.lli; else v.ulli = l.v.ulli/r.v.ulli;
246         }
247         void bit_and(dtype dt, param_int &l, param_int &r){
248                 d=dt;
249                 if(dt==int_t || dt==llong_t)
250                         if(l.d==int_t || l.d==llong_t)
251                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli&r.v.lli; else v.lli = l.v.lli&r.v.ulli;
252                         else
253                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli&r.v.lli; else v.lli = l.v.ulli&r.v.ulli;
254                 else
255                         if(l.d==int_t || l.d==llong_t)
256                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli&r.v.lli; else v.ulli = l.v.lli&r.v.ulli;
257                         else
258                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli&r.v.lli; else v.ulli = l.v.ulli&r.v.ulli;
259         }
260         void bit_or(dtype dt, param_int &l, param_int &r){
261                 d=dt;
262                 if(dt==int_t || dt==llong_t)
263                         if(l.d==int_t || l.d==llong_t)
264                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli|r.v.lli; else v.lli = l.v.lli|r.v.ulli;
265                         else
266                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli|r.v.lli; else v.lli = l.v.ulli|r.v.ulli;
267                 else
268                         if(l.d==int_t || l.d==llong_t)
269                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli|r.v.lli; else v.ulli = l.v.lli|r.v.ulli;
270                         else
271                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli|r.v.lli; else v.ulli = l.v.ulli|r.v.ulli;
272         }
273         void modulo(dtype dt, param_int &l, param_int &r){
274                 d=dt;
275                 if(dt==int_t || dt==llong_t)
276                         if(l.d==int_t || l.d==llong_t)
277                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli%r.v.lli; else v.lli = l.v.lli%r.v.ulli;
278                         else
279                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli%r.v.lli; else v.lli = l.v.ulli%r.v.ulli;
280                 else
281                         if(l.d==int_t || l.d==llong_t)
282                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli%r.v.lli; else v.ulli = l.v.lli%r.v.ulli;
283                         else
284                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli%r.v.lli; else v.ulli = l.v.ulli%r.v.ulli;
285         }
286         void shift_left(dtype dt, param_int &l, param_int &r){
287                 d=dt;
288                 if(dt==int_t || dt==llong_t)
289                         if(l.d==int_t || l.d==llong_t)
290                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli<<r.v.lli; else v.lli = l.v.lli<<r.v.ulli;
291                         else
292                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli<<r.v.lli; else v.lli = l.v.ulli<<r.v.ulli;
293                 else
294                         if(l.d==int_t || l.d==llong_t)
295                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli<<r.v.lli; else v.ulli = l.v.lli<<r.v.ulli;
296                         else
297                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli<<r.v.lli; else v.ulli = l.v.ulli<<r.v.ulli;
298         }
299         void shift_right(dtype dt, param_int &l, param_int &r){
300                 d=dt;
301                 if(dt==int_t || dt==llong_t)
302                         if(l.d==int_t || l.d==llong_t)
303                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.lli>>r.v.lli; else v.lli = l.v.lli>>r.v.ulli;
304                         else
305                                 if(r.d==int_t || r.d==llong_t) v.lli = l.v.ulli>>r.v.lli; else v.lli = l.v.ulli>>r.v.ulli;
306                 else
307                         if(l.d==int_t || l.d==llong_t)
308                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.lli>>r.v.lli; else v.ulli = l.v.lli>>r.v.ulli;
309                         else
310                                 if(r.d==int_t || r.d==llong_t) v.ulli = l.v.ulli>>r.v.lli; else v.ulli = l.v.ulli>>r.v.ulli;
311         }
312
313         void plus(dtype dt, param_int &l){
314                 d=dt;
315                 if(dt==int_t || dt==llong_t)
316                         if(l.d==int_t || l.d==llong_t)
317                                 v.lli = l.v.ulli;
318                         else
319                                 v.lli = l.v.lli;
320                 else
321                         if(l.d==int_t || l.d==llong_t)
322                                 v.ulli = l.v.ulli;
323                         else
324                                 v.ulli = l.v.lli;
325         }
326         void minus(dtype dt, param_int &l){
327                 d=dt;
328                 if(dt==int_t || dt==llong_t)
329                         if(l.d==int_t || l.d==llong_t)
330                                 v.lli = -l.v.ulli;
331                         else
332                                 v.lli = -l.v.lli;
333                 else
334                         if(l.d==int_t || l.d==llong_t)
335                                 v.ulli = -l.v.ulli;
336                         else
337                                 v.ulli = -l.v.lli;
338         }
339         void abs_not(dtype dt, param_int &l){
340                 d=dt;
341                 if(dt==int_t || dt==llong_t)
342                         if(l.d==int_t || l.d==llong_t)
343                                 v.lli = !l.v.ulli;
344                         else
345                                 v.lli = !l.v.lli;
346                 else
347                         if(l.d==int_t || l.d==llong_t)
348                                 v.ulli = !l.v.ulli;
349                         else
350                                 v.ulli = !l.v.lli;
351         }
352         void bit_not(dtype dt, param_int &l){
353                 d=dt;
354                 if(dt==int_t || dt==llong_t)
355                         if(l.d==int_t || l.d==llong_t)
356                                 v.lli = ~l.v.ulli;
357                         else
358                                 v.lli = ~l.v.lli;
359                 else
360                         if(l.d==int_t || l.d==llong_t)
361                                 v.ulli = ~l.v.ulli;
362                         else
363                                 v.ulli = ~l.v.lli;
364         }
365 };
366
367
368 bool int_operand_divides(param_int &lp, param_int &rp){
369         if( (lp.d==int_t || lp.d==llong_t)){
370                 if(lp.v.lli < 0)
371                         lp.v.ulli = -lp.v.lli;
372                 else
373                         lp.v.ulli = lp.v.lli;
374         }
375         if( (rp.d==int_t || rp.d==llong_t)){
376                 if(rp.v.lli < 0)
377                         rp.v.ulli = -rp.v.lli;
378                 else
379                         rp.v.ulli = rp.v.lli;
380         }
381     unsigned long long int d = rp.v.ulli / lp.v.ulli;
382     unsigned long long int r = rp.v.ulli - d * lp.v.ulli;
383         return d==0;
384 }
385
386 bool int_operand_implies(param_int &lp, param_int &rp){
387         unsigned long long int d = (lp.v.ulli & rp.v.ulli) | (!lp.v.ulli);
388         return (~d)==0;
389 }
390
391
392
393
394 void extract_param_int(scalarexp_t *se, param_int &p_int) {
395 param_int lp, rp;
396 string op_str;
397 dtype dt = se->get_data_type()->get_type();
398         switch(se->get_operator_type()){
399         case SE_LITERAL:
400                 p_int.load_val(se->get_data_type()->get_type(),se->to_string().c_str());
401                 return;
402         case SE_UNARY_OP:
403                 extract_param_int(se->get_left_se(), lp);
404                 op_str = se->get_op();
405                 if(op_str=="+") p_int.plus(dt,lp);
406                 if(op_str=="-") p_int.minus(dt,lp);
407                 if(op_str=="!") p_int.abs_not(dt,lp);
408                 if(op_str=="~") p_int.bit_not(dt,lp);
409                 return;
410         case SE_BINARY_OP:
411                 extract_param_int(se->get_left_se(), lp);
412                 extract_param_int(se->get_right_se(), rp);
413                 op_str = se->get_op();
414                 if(op_str=="+") p_int.add(dt,lp,rp);
415                 if(op_str=="-") p_int.subtract(dt,lp,rp);
416                 if(op_str=="*") p_int.mult(dt,lp,rp);
417                 if(op_str=="/") p_int.div(dt,lp,rp);
418                 if(op_str=="&") p_int.bit_and(dt,lp,rp);
419                 if(op_str=="|") p_int.bit_or(dt,lp,rp);
420                 if(op_str=="%") p_int.modulo(dt,lp,rp);
421                 if(op_str=="<<") p_int.shift_left(dt,lp,rp);
422                 if(op_str==">>") p_int.shift_right(dt,lp,rp);
423                 return;
424         default:
425                 fprintf(stderr,"INTERNAL ERROR in find_field, invalid operator type %d\n", se->get_operator_type());
426                 exit(1);
427         }
428         return;
429
430 }
431
432
433 void get_int_operand(scalarexp_t *parent, scalarexp_t *child, param_int &p_int){
434         if(parent->get_operator_type() != SE_BINARY_OP){
435                 fprintf(stderr,"INTERNAL ERROR, operator type %d in get_int_operand.\n",
436 parent->get_operator_type());
437                 exit(1);
438         }
439         if(parent->get_right_se() == child){
440                 extract_param_int(parent->get_left_se(), p_int);
441                 p_int.convert_to_final();
442         }else{
443                 extract_param_int(parent->get_right_se(), p_int);
444                 p_int.convert_to_final();
445         }
446 }
447
448
449 bool partition_compatible(scalarexp_t *pse, scalarexp_t *gse){
450         vector<scalarexp_t *> pstack, gstack;
451
452         find_colref_path(pse, pstack);
453         find_colref_path(gse, gstack);
454
455         int ppos=0, gpos=0;
456         string p_op, g_op;
457         param_int p_int, g_int;
458
459         while(ppos<pstack.size()-1 && gpos<gstack.size()-1){
460
461 //              first, try to raise both stack pointers.
462                 if(ppos<pstack.size()-1 && gpos<gstack.size()-1){
463                         p_op = pstack[ppos+1]->get_op();
464                         g_op = gstack[gpos+1]->get_op();
465                         if(p_op==g_op){
466                                 if(p_op=="/"){
467                                         get_int_operand(pstack[ppos+1],pstack[ppos],p_int);
468                                         get_int_operand(gstack[gpos+1],gstack[gpos],g_int);
469                                         if(int_operand_divides(g_int, p_int)){
470                                                 ppos++;
471                                                 gpos++;
472                                                 continue;
473                                         }else{
474                                                 return false;
475                                         }
476                                 }
477                                 if(p_op=="&"){
478                                         get_int_operand(pstack[ppos+1],pstack[ppos],p_int);
479                                         get_int_operand(gstack[gpos+1],gstack[gpos],g_int);
480                                         if(int_operand_implies(p_int, g_int)){
481                                                 ppos++;
482                                                 gpos++;
483                                                 continue;
484                                         }else{
485                                                 return false;
486                                         }
487                                 }
488                                 if(p_op=="|"){
489                                         get_int_operand(pstack[ppos+1],pstack[ppos],p_int);
490                                         get_int_operand(gstack[gpos+1],gstack[gpos],g_int);
491                                         if(int_operand_implies(g_int, p_int)){
492                                                 ppos++;
493                                                 gpos++;
494                                                 continue;
495                                         }else{
496                                                 return false;
497                                         }
498                                 }
499                         }
500                 }
501                 if(ppos<pstack.size()-1){
502                         p_op = pstack[ppos+1]->get_op();
503                         if(p_op=="+" || p_op=="-" || p_op=="*" || p_op=="/" || p_op=="&" || p_op=="|"){
504                                 ppos++;
505                                 continue;
506                         }
507                 }
508                 if(gpos<gstack.size()-1){
509                         g_op = gstack[gpos+1]->get_op();
510                         if(g_op=="+" || g_op=="-" || g_op=="*" || g_op=="/" || g_op=="&" || g_op=="|"){
511                                 gpos++;
512                                 continue;
513                         }
514                 }
515
516                 return false;   // no reduction rule applies
517         }
518
519         return true;            // reduced both stacks.
520 }
521
522
523 bool partn_def_t::is_compatible(gb_table *gb_tbl){
524         vector<string> gb_flds;
525         int i,p,g;
526
527         for(i=0;i<gb_tbl->size();++i){
528                 string gfld;
529                 if(find_field(gb_tbl->get_def(i),gfld)==1){
530                         gb_flds.push_back(gfld);
531                 }else{
532                         gb_flds.push_back("");
533                 }
534         }
535
536         for(p=p;p<se_list.size();++p){
537                 for(g=0;g<gb_tbl->size();++g){
538                         if(partition_compatible(se_list[p], gb_tbl->get_def(g)))
539                                 break;
540                 }
541                 if(g==gb_tbl->size()){
542                         return false;
543                 }
544         }
545         return true;
546 }