LCOV - code coverage report
Current view: top level - sql/server - rel_rel.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 1064 1223 87.0 %
Date: 2021-10-13 02:24:04 Functions: 75 80 93.8 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : #include "monetdb_config.h"
      10             : #include "rel_rel.h"
      11             : #include "rel_basetable.h"
      12             : #include "rel_exp.h"
      13             : #include "rel_prop.h"
      14             : #include "rel_unnest.h"
      15             : #include "sql_semantic.h"
      16             : #include "sql_mvc.h"
      17             : #include "rel_rewriter.h"
      18             : 
      19             : void
      20          44 : rel_set_exps(sql_rel *rel, list *exps)
      21             : {
      22          44 :         rel->exps = exps;
      23          44 :         rel->nrcols = list_length(exps);
      24          44 : }
      25             : 
      26             : /* some projections results are order dependend (row_number etc) */
      27             : int
      28     1761919 : project_unsafe(sql_rel *rel, int allow_identity)
      29             : {
      30     1761919 :         sql_rel *sub = rel->l;
      31             : 
      32     1761919 :         if (need_distinct(rel) || rel->r /* order by */)
      33             :                 return 1;
      34     1591093 :         if (list_empty(rel->exps))
      35             :                 return 0;
      36             :         /* projects without sub and projects around ddl's cannot be changed */
      37     1591093 :         if (!sub || sub->op == op_ddl)
      38             :                 return 1;
      39    11400209 :         for(node *n = rel->exps->h; n; n = n->next) {
      40    10261711 :                 sql_exp *e = n->data, *ne;
      41             : 
      42             :                 /* aggr func in project ! */
      43    10261711 :                 if (exp_unsafe(e, allow_identity))
      44             :                         return 1;
      45    10156470 :                 if ((ne = rel_find_exp(rel, e)) && ne != e)
      46             :                         return 1; /* no self referencing */
      47             :         }
      48             :         return 0;
      49             : }
      50             : 
      51             : /* we don't name relations directly, but sometimes we need the relation
      52             :    name. So we look it up in the first expression
      53             : 
      54             :    we should clean up (remove) this function.
      55             :  */
      56             : const char *
      57       91438 : rel_name( sql_rel *r )
      58             : {
      59       94927 :         if (is_basetable(r->op))
      60       91325 :                 return rel_base_name(r);
      61        3602 :         if (!is_project(r->op) && !is_base(r->op) && r->l)
      62             :                 return rel_name(r->l);
      63         113 :         if (r->exps && list_length(r->exps)) {
      64         113 :                 sql_exp *e = r->exps->h->data;
      65         113 :                 if (exp_relname(e))
      66         113 :                         return exp_relname(e);
      67           0 :                 if (e->type == e_column)
      68           0 :                         return e->l;
      69             :         }
      70             :         return NULL;
      71             : }
      72             : 
      73             : sql_rel *
      74        9949 : rel_distinct(sql_rel *l)
      75             : {
      76        9949 :         set_distinct(l);
      77        9949 :         return l;
      78             : }
      79             : 
      80             : sql_rel *
      81      499545 : rel_dup(sql_rel *r)
      82             : {
      83      499545 :         sql_ref_inc(&r->ref);
      84      499545 :         return r;
      85             : }
      86             : 
      87             : static void
      88      580916 : rel_destroy_(sql_rel *rel)
      89             : {
      90      580916 :         if (!rel)
      91             :                 return;
      92      580916 :         if (is_join(rel->op) ||
      93             :             is_semi(rel->op) ||
      94             :             is_select(rel->op) ||
      95      580916 :             is_set(rel->op) ||
      96      217927 :             is_topn(rel->op) ||
      97      217927 :                 is_sample(rel->op) ||
      98             :                 is_merge(rel->op)) {
      99      362989 :                 if (rel->l)
     100       84400 :                         rel_destroy(rel->l);
     101      362989 :                 if (rel->r)
     102       47476 :                         rel_destroy(rel->r);
     103      217927 :         } else if (is_simple_project(rel->op) || is_groupby(rel->op)) {
     104      211496 :                 if (rel->l)
     105       32070 :                         rel_destroy(rel->l);
     106        6431 :         } else if (is_insert(rel->op) || is_update(rel->op) || is_delete(rel->op) || is_truncate(rel->op)) {
     107         127 :                 if (rel->r)
     108         111 :                         rel_destroy(rel->r);
     109             :         }
     110             : }
     111             : 
     112             : void
     113     1014671 : rel_destroy(sql_rel *rel)
     114             : {
     115     1014671 :         if (!rel)
     116             :                 return;
     117     1014667 :         if (sql_ref_dec(&rel->ref) > 0)
     118             :                 return;
     119      542818 :         rel_destroy_(rel);
     120             : }
     121             : 
     122             : sql_rel*
     123     2666758 : rel_create(sql_allocator *sa)
     124             : {
     125     2666758 :         sql_rel *r = SA_NEW(sa, sql_rel);
     126     2666758 :         if(!r)
     127             :                 return NULL;
     128             : 
     129     2666758 :         *r = (sql_rel) {
     130             :                 .card = CARD_ATOM,
     131             :         };
     132     2666758 :         sql_ref_init(&r->ref);
     133     2666758 :         return r;
     134             : }
     135             : 
     136             : sql_rel *
     137          86 : rel_copy(mvc *sql, sql_rel *i, int deep)
     138             : {
     139             :         sql_rel *rel;
     140             : 
     141             :         if (mvc_highwater(sql))
     142           0 :                 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
     143             : 
     144          86 :         rel = rel_create(sql->sa);
     145          86 :         if (!rel)
     146             :                 return NULL;
     147             : 
     148          86 :         rel->op = i->op;
     149          86 :         switch(i->op) {
     150          29 :         case op_basetable:
     151          29 :                 rel_base_copy(sql, i, rel);
     152          29 :                 break;
     153           0 :         case op_table:
     154           0 :                 rel->l = i->l;
     155           0 :                 rel->r = i->r;
     156           0 :                 break;
     157          31 :         case op_project:
     158             :         case op_groupby:
     159          31 :                 if (i->l)
     160          29 :                         rel->l = rel_copy(sql, i->l, deep);
     161          31 :                 if (i->r) {
     162           0 :                         if (!deep) {
     163           0 :                                 rel->r = list_dup(i->r, (fdup) NULL);
     164             :                         } else {
     165           0 :                                 rel->r = exps_copy(sql, i->r);
     166             :                         }
     167             :                 }
     168             :                 break;
     169           0 :         case op_ddl:
     170           0 :                 if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
     171           0 :                         if (i->l)
     172           0 :                                 rel->l = rel_copy(sql, i->l, deep);
     173           0 :                 } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
     174           0 :                         if (i->l)
     175           0 :                                 rel->l = rel_copy(sql, i->l, deep);
     176           0 :                         if (i->r)
     177           0 :                                 rel->r = rel_copy(sql, i->r, deep);
     178             :                 }
     179             :                 break;
     180          22 :         case op_select:
     181             :         case op_topn:
     182             :         case op_sample:
     183             :         case op_truncate:
     184          22 :                 if (i->l)
     185          22 :                         rel->l = rel_copy(sql, i->l, deep);
     186             :                 break;
     187           4 :         case op_insert:
     188             :         case op_update:
     189             :         case op_delete:
     190             : 
     191             :         case op_join:
     192             :         case op_left:
     193             :         case op_right:
     194             :         case op_full:
     195             :         case op_semi:
     196             :         case op_anti:
     197             : 
     198             :         case op_union:
     199             :         case op_inter:
     200             :         case op_except:
     201             :         case op_merge:
     202           4 :                 if (i->l)
     203           4 :                         rel->l = rel_copy(sql, i->l, deep);
     204           4 :                 if (i->r)
     205           4 :                         rel->r = rel_copy(sql, i->r, deep);
     206             :                 break;
     207             :         }
     208             : 
     209          86 :         rel->card = i->card;
     210          86 :         rel->flag = i->flag;
     211          86 :         rel->nrcols = i->nrcols;
     212          86 :         rel->grouped = i->grouped;
     213          86 :         rel->used = i->used;
     214             : 
     215          86 :         if (is_processed(i))
     216          34 :                 set_processed(rel);
     217          86 :         if (is_dependent(i))
     218           0 :                 set_dependent(rel);
     219          86 :         if (is_outer(i))
     220           0 :                 set_outer(rel);
     221          86 :         if (is_single(i))
     222           0 :                 set_single(rel);
     223          86 :         if (need_distinct(i))
     224           2 :                 set_distinct(rel);
     225             : 
     226          86 :         rel->p = prop_copy(sql->sa, i->p);
     227          86 :         rel->exps = (!i->exps)?NULL:deep?exps_copy(sql, i->exps):list_dup(i->exps, (fdup)NULL);
     228          86 :         return rel;
     229             : }
     230             : 
     231             : sql_rel *
     232        5292 : rel_select_copy(sql_allocator *sa, sql_rel *l, list *exps)
     233             : {
     234        5292 :         sql_rel *rel = rel_create(sa);
     235        5292 :         if(!rel)
     236             :                 return NULL;
     237             : 
     238        5292 :         rel->l = l;
     239        5292 :         rel->r = NULL;
     240        5292 :         rel->op = op_select;
     241        5292 :         rel->exps = exps?list_dup(exps, (fdup)NULL):NULL;
     242        5292 :         rel->card = CARD_ATOM; /* no relation */
     243        5292 :         if (l) {
     244        5292 :                 rel->card = l->card;
     245        5292 :                 rel->nrcols = l->nrcols;
     246             :         }
     247             :         return rel;
     248             : }
     249             : 
     250             : sql_exp *
     251     7790160 : rel_bind_column( mvc *sql, sql_rel *rel, const char *cname, int f, int no_tname)
     252             : {
     253     7790160 :         int ambiguous = 0, multi = 0;
     254             : 
     255     7790160 :         if (!rel)
     256             :                 return NULL;
     257             :         if (mvc_highwater(sql))
     258           0 :                 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
     259             : 
     260     7790160 :         if ((is_project(rel->op) || is_base(rel->op))) {
     261             :                 sql_exp *e = NULL;
     262             : 
     263     4097113 :                 if (is_base(rel->op) && !rel->exps)
     264     3941299 :                         return rel_base_bind_column(sql, rel, cname, no_tname);
     265      155814 :                 if (!list_empty(rel->exps)) {
     266      155781 :                         e = exps_bind_column(rel->exps, cname, &ambiguous, &multi, no_tname);
     267      155781 :                         if (ambiguous || multi)
     268           6 :                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
     269      155775 :                         if (!e && is_groupby(rel->op) && rel->r) {
     270         169 :                                 e = exps_bind_alias(rel->r, NULL, cname);
     271         169 :                                 if (e) {
     272           0 :                                         e = exps_bind_column(rel->r, cname, &ambiguous, &multi, no_tname);
     273           0 :                                         if (ambiguous || multi)
     274           0 :                                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
     275             :                                         return e;
     276             :                                 }
     277             :                         }
     278             :                 }
     279      155808 :                 if (!e && (is_sql_sel(f) || is_sql_having(f) || !f) && is_groupby(rel->op) && rel->r) {
     280         171 :                         e = exps_bind_column(rel->r, cname, &ambiguous, &multi, no_tname);
     281         171 :                         if (ambiguous || multi)
     282           0 :                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
     283         171 :                         if (e) {
     284           2 :                                 e = exp_ref(sql, e);
     285           2 :                                 e->card = rel->card;
     286           2 :                                 return e;
     287             :                         }
     288             :                 }
     289      155806 :                 if (e)
     290      136766 :                         return exp_alias_or_copy(sql, exp_relname(e), cname, rel, e);
     291             :         }
     292     3712087 :         if ((is_simple_project(rel->op) || is_groupby(rel->op)) && rel->l) {
     293        5721 :                 if (!is_processed(rel))
     294          82 :                         return rel_bind_column(sql, rel->l, cname, f, no_tname);
     295     3706366 :         } else if (is_set(rel->op)) {
     296        2176 :                 assert(is_processed(rel));
     297             :                 return NULL;
     298     3704190 :         } else if (is_join(rel->op)) {
     299     3227647 :                 sql_exp *e1 = rel_bind_column(sql, rel->l, cname, f, no_tname), *e2 = NULL, *res;
     300             : 
     301     3227647 :                 if (e1 && (is_right(rel->op) || is_full(rel->op)))
     302           6 :                         set_has_nil(e1);
     303     3227647 :                 if (!e1 || !is_freevar(e1)) {
     304     3227647 :                         e2 = rel_bind_column(sql, rel->r, cname, f, no_tname);
     305     3227647 :                         if (e2 && (is_left(rel->op) || is_full(rel->op)))
     306          56 :                                 set_has_nil(e2);
     307     3227647 :                         if (e1 && e2 && !is_dependent(rel))
     308           3 :                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
     309             :                 }
     310     3227644 :                 res = e1 ? e1 : e2;
     311     3227644 :                 if (res)
     312     1699982 :                         set_not_unique(res);
     313     3227644 :                 return res;
     314      476543 :         } else if (is_semi(rel->op) ||
     315       11165 :                    is_select(rel->op) ||
     316       11143 :                    is_topn(rel->op) ||
     317             :                    is_sample(rel->op)) {
     318      465400 :                 if (rel->l)
     319      465400 :                         return rel_bind_column(sql, rel->l, cname, f, no_tname);
     320             :         }
     321             :         return NULL;
     322             : }
     323             : 
     324             : sql_exp *
     325     4318321 : rel_bind_column2( mvc *sql, sql_rel *rel, const char *tname, const char *cname, int f)
     326             : {
     327     4318321 :         int ambiguous = 0, multi = 0;
     328             : 
     329     4318321 :         if (!rel)
     330             :                 return NULL;
     331             :         if (mvc_highwater(sql))
     332           0 :                 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
     333             : 
     334     4317440 :         if ((is_project(rel->op) || is_base(rel->op))) {
     335             :                 sql_exp *e = NULL;
     336             : 
     337     1963837 :                 if (is_basetable(rel->op) && !rel->exps)
     338     1229739 :                         return rel_base_bind_column2(sql, rel, tname, cname);
     339             :                 /* in case of orderby we should also lookup the column in group by list (and use existing references) */
     340      734098 :                 if (!list_empty(rel->exps)) {
     341      734064 :                         e = exps_bind_column2(rel->exps, tname, cname, &multi);
     342      734064 :                         if (multi)
     343           1 :                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s.%s' ambiguous",
     344             :                                                                  tname, cname);
     345      734063 :                         if (!e && is_groupby(rel->op) && rel->r) {
     346         139 :                                 e = exps_bind_alias(rel->r, tname, cname);
     347         139 :                                 if (e) {
     348           6 :                                         const char *rname = exp_relname(e), *nname = exp_name(e);
     349           6 :                                         if (rname)
     350           0 :                                                 e = exps_bind_column2(rel->exps, rname, nname, &multi);
     351             :                                         else
     352           6 :                                                 e = exps_bind_column(rel->exps, nname, &ambiguous, &multi, 0);
     353           6 :                                         if (ambiguous || multi)
     354           0 :                                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s%s%s' ambiguous",
     355             :                                                                                  rname ? rname : "", rname ? "." : "", nname);
     356           6 :                                         if (e)
     357             :                                                 return e;
     358             :                                 }
     359             :                         }
     360             :                 }
     361      734091 :                 if (!e && (is_sql_sel(f) || is_sql_having(f) || !f) && is_groupby(rel->op) && rel->r) {
     362         143 :                         e = exps_bind_column2(rel->r, tname, cname, &multi);
     363         143 :                         if (multi)
     364           0 :                                 return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s.%s' ambiguous",
     365             :                                                                  tname, cname);
     366         143 :                         if (e) {
     367           0 :                                 e = exp_ref(sql, e);
     368           0 :                                 e->card = rel->card;
     369           0 :                                 return e;
     370             :                         }
     371             :                 }
     372      734091 :                 if (e)
     373      485659 :                         return exp_alias_or_copy(sql, tname, cname, rel, e);
     374             :         }
     375     2602035 :         if ((is_simple_project(rel->op) || is_groupby(rel->op)) && rel->l) {
     376      151911 :                 if (!is_processed(rel))
     377         100 :                         return rel_bind_column2(sql, rel->l, tname, cname, f);
     378     2450124 :         } else if (is_set(rel->op)) {
     379       60943 :                 assert(is_processed(rel));
     380             :                 return NULL;
     381     2389181 :         } else if (is_join(rel->op)) {
     382     1913906 :                 sql_exp *e = rel_bind_column2(sql, rel->l, tname, cname, f);
     383             : 
     384     1913906 :                 if (e && (is_right(rel->op) || is_full(rel->op)))
     385         256 :                         set_has_nil(e);
     386     1913906 :                 if (!e) {
     387      831966 :                         e = rel_bind_column2(sql, rel->r, tname, cname, f);
     388      831966 :                         if (e && (is_left(rel->op) || is_full(rel->op)))
     389       28647 :                                 set_has_nil(e);
     390             :                 }
     391     1913906 :                 if (e)
     392     1535947 :                         set_not_unique(e);
     393     1913906 :                 return e;
     394      475275 :         } else if (is_semi(rel->op) ||
     395       36097 :                    is_select(rel->op) ||
     396       35578 :                    is_topn(rel->op) ||
     397             :                    is_sample(rel->op)) {
     398      439697 :                 if (rel->l)
     399      439697 :                         return rel_bind_column2(sql, rel->l, tname, cname, f);
     400             :         }
     401             :         return NULL;
     402             : }
     403             : 
     404             : sql_exp *
     405           0 : rel_first_column(mvc *sql, sql_rel *r)
     406             : {
     407           0 :         if (is_simple_project(r->op))
     408           0 :                 return r->exps->h->data;
     409             : 
     410           0 :         list *exps = rel_projections(sql, r, NULL, 1, 1);
     411             : 
     412           0 :         if (!list_empty(exps))
     413           0 :                 return exps->h->data;
     414             : 
     415             :         return NULL;
     416             : }
     417             : 
     418             : sql_rel *
     419       37389 : rel_inplace_setop(mvc *sql, sql_rel *rel, sql_rel *l, sql_rel *r, operator_type setop, list *exps)
     420             : {
     421       37389 :         rel_destroy_(rel);
     422       37389 :         rel->l = l;
     423       37389 :         rel->r = r;
     424       37389 :         rel->op = setop;
     425       37389 :         rel->card = CARD_MULTI;
     426       37389 :         rel->flag = 0;
     427       37389 :         rel_setop_set_exps(sql, rel, exps, false);
     428       37389 :         set_processed(rel);
     429       37389 :         return rel;
     430             : }
     431             : 
     432             : sql_rel *
     433       43780 : rel_inplace_project(sql_allocator *sa, sql_rel *rel, sql_rel *l, list *e)
     434             : {
     435       43780 :         if (!l) {
     436       43780 :                 l = rel_create(sa);
     437       43780 :                 if(!l)
     438             :                         return NULL;
     439             : 
     440       43780 :                 *l = *rel;
     441       43780 :                 l->ref.refcnt = 1;
     442             :         } else {
     443           0 :                 rel_destroy_(rel);
     444             :         }
     445       43780 :         set_processed(rel);
     446             : 
     447       43780 :         rel->l = l;
     448       43780 :         rel->r = NULL;
     449       43780 :         rel->op = op_project;
     450       43780 :         rel->exps = e;
     451       43780 :         rel->card = CARD_MULTI;
     452       43780 :         rel->flag = 0;
     453       43780 :         if (l) {
     454       43780 :                 rel->nrcols = l->nrcols;
     455       43780 :                 assert (exps_card(rel->exps) <= rel->card);
     456             :         }
     457             :         return rel;
     458             : }
     459             : 
     460             : sql_rel *
     461         709 : rel_inplace_groupby(sql_rel *rel, sql_rel *l, list *groupbyexps, list *exps )
     462             : {
     463         709 :         rel_destroy_(rel);
     464         709 :         rel->card = CARD_ATOM;
     465         709 :         if (groupbyexps)
     466         580 :                 rel->card = CARD_AGGR;
     467         709 :         rel->l = l;
     468         709 :         rel->r = groupbyexps;
     469         709 :         rel->exps = exps;
     470         709 :         rel->nrcols = l->nrcols;
     471         709 :         rel->op = op_groupby;
     472         709 :         rel->flag = 0;
     473         709 :         set_processed(rel);
     474         709 :         return rel;
     475             : }
     476             : 
     477             : sql_rel *
     478       59725 : rel_setop(sql_allocator *sa, sql_rel *l, sql_rel *r, operator_type setop)
     479             : {
     480       59725 :         sql_rel *rel = rel_create(sa);
     481       59725 :         if(!rel)
     482             :                 return NULL;
     483       59725 :         rel->l = l;
     484       59725 :         rel->r = r;
     485       59725 :         rel->op = setop;
     486       59725 :         rel->exps = NULL;
     487       59725 :         rel->card = CARD_MULTI;
     488       59725 :         assert(l->nrcols == r->nrcols);
     489       59725 :         rel->nrcols = l->nrcols;
     490       59725 :         return rel;
     491             : }
     492             : 
     493             : sql_rel *
     494       54399 : rel_setop_check_types(mvc *sql, sql_rel *l, sql_rel *r, list *ls, list *rs, operator_type op)
     495             : {
     496       54399 :         list *nls = new_exp_list(sql->sa);
     497       54399 :         list *nrs = new_exp_list(sql->sa);
     498             :         node *n, *m;
     499             : 
     500       54399 :         if(!nls || !nrs)
     501             :                 return NULL;
     502             : 
     503      417400 :         for (n = ls->h, m = rs->h; n && m; n = n->next, m = m->next) {
     504      363006 :                 sql_exp *le = n->data;
     505      363006 :                 sql_exp *re = m->data;
     506             : 
     507      363006 :                 if ((rel_convert_types(sql, l, r, &le, &re, 1, type_set) < 0))
     508           5 :                         return NULL;
     509      363001 :                 append(nls, le);
     510      363001 :                 append(nrs, re);
     511             :         }
     512       54394 :         l = rel_project(sql->sa, l, nls);
     513       54394 :         r = rel_project(sql->sa, r, nrs);
     514       54394 :         set_processed(l);
     515       54394 :         set_processed(r);
     516       54394 :         return rel_setop(sql->sa, l, r, op);
     517             : }
     518             : 
     519             : void
     520       97049 : rel_setop_set_exps(mvc *sql, sql_rel *rel, list *exps, bool keep_props)
     521             : {
     522       97049 :         sql_rel *l = rel->l, *r = rel->r;
     523       97049 :         list *lexps = l->exps, *rexps = r->exps;
     524             : 
     525       97049 :         if (!is_project(l->op))
     526        8090 :                 lexps = rel_projections(sql, l, NULL, 0, 1);
     527       97049 :         if (!is_project(r->op))
     528        8124 :                 rexps = rel_projections(sql, r, NULL, 0, 1);
     529             : 
     530       97049 :         assert(is_set(rel->op) && list_length(lexps) == list_length(rexps) && list_length(exps) == list_length(lexps));
     531             : 
     532      753469 :         for (node *n = exps->h, *m = lexps->h, *o = rexps->h ; m && n && o ; n = n->next, m = m->next,o = o->next) {
     533      656420 :                 sql_exp *e = n->data, *f = m->data, *g = o->data;
     534             : 
     535      656420 :                 if (is_union(rel->op)) { /* propagate set_has_no_nil only if it's applicable to both sides of the union*/
     536      653469 :                         if (has_nil(f) || has_nil(g))
     537      589001 :                                 set_has_nil(e);
     538             :                         else
     539       64468 :                                 set_has_no_nil(e);
     540      653469 :                         if (!keep_props) {
     541      653131 :                                 e->p = NULL; /* remove all the properties on unions on the general case */
     542      653131 :                                 set_not_unique(e);
     543             :                         }
     544             :                 }
     545      656420 :                 e->card = CARD_MULTI; /* multi cardinality */
     546             :         }
     547       97049 :         rel->nrcols = l->nrcols;
     548       97049 :         rel->exps = exps;
     549       97049 : }
     550             : 
     551             : sql_rel *
     552      462499 : rel_crossproduct(sql_allocator *sa, sql_rel *l, sql_rel *r, operator_type join)
     553             : {
     554      462499 :         sql_rel *rel = rel_create(sa);
     555      462499 :         if(!rel)
     556             :                 return NULL;
     557             : 
     558      462499 :         rel->l = l;
     559      462499 :         rel->r = r;
     560      462499 :         rel->op = join;
     561      462499 :         rel->exps = NULL;
     562      462499 :         rel->card = CARD_MULTI;
     563      462499 :         rel->nrcols = l->nrcols + r->nrcols;
     564      462499 :         rel->single = is_single(r);
     565      462499 :         if (is_single(r))
     566          23 :                 reset_single(r);
     567             :         return rel;
     568             : }
     569             : 
     570             : sql_exp *
     571           0 : rel_is_constant(sql_rel **R, sql_exp *e)
     572             : {
     573           0 :         sql_rel *rel = *R;
     574             : 
     575           0 :         if (rel && rel->op == op_project && list_length(rel->exps) == 1 &&
     576           0 :             !rel->l && !rel->r && !rel_is_ref(rel) && e->type == e_column) {
     577           0 :                 sql_exp *ne = rel_find_exp(rel, e);
     578           0 :                 if (ne) {
     579           0 :                         rel_destroy(rel);
     580           0 :                         *R = NULL;
     581           0 :                         return ne;
     582             :                 }
     583             :         }
     584             :         return e;
     585             : }
     586             : 
     587             : sql_rel *
     588         859 : rel_topn(sql_allocator *sa, sql_rel *l, list *exps )
     589             : {
     590         859 :         sql_rel *rel = rel_create(sa);
     591         859 :         if(!rel)
     592             :                 return NULL;
     593             : 
     594         859 :         rel->l = l;
     595         859 :         rel->r = NULL;
     596         859 :         rel->op = op_topn;
     597         859 :         rel->exps = exps;
     598         859 :         rel->card = l->card;
     599         859 :         rel->nrcols = l->nrcols;
     600         859 :         return rel;
     601             : }
     602             : 
     603             : sql_rel *
     604          23 : rel_sample(sql_allocator *sa, sql_rel *l, list *exps )
     605             : {
     606          23 :         sql_rel *rel = rel_create(sa);
     607          23 :         if(!rel)
     608             :                 return NULL;
     609             : 
     610          23 :         rel->l = l;
     611          23 :         rel->r = NULL;
     612          23 :         rel->op = op_sample;
     613          23 :         rel->exps = exps;
     614          23 :         rel->card = l->card;
     615          23 :         rel->nrcols = l->nrcols;
     616          23 :         return rel;
     617             : }
     618             : 
     619             : sql_rel *
     620        8956 : rel_label( mvc *sql, sql_rel *r, int all)
     621             : {
     622        8956 :         int nr = ++sql->label;
     623             :         char tname[16], *tnme;
     624             :         char cname[16], *cnme = NULL;
     625             : 
     626        8956 :         tnme = number2name(tname, sizeof(tname), nr);
     627        8956 :         if (!is_project(r->op)) {
     628         559 :                 r = rel_project(sql->sa, r, rel_projections(sql, r, NULL, 1, 1));
     629         559 :                 set_processed(r);
     630             :         }
     631        8956 :         if (is_project(r->op) && r->exps) {
     632        8956 :                 node *ne = r->exps->h;
     633             : 
     634        8956 :                 list_hash_clear(r->exps);
     635       40550 :                 for (; ne; ne = ne->next) {
     636       31594 :                         sql_exp *e = ne->data;
     637             : 
     638       31594 :                         if (!is_freevar(e)) {
     639       31588 :                                 if (all) {
     640       31588 :                                         nr = ++sql->label;
     641       31588 :                                         cnme = number2name(cname, sizeof(cname), nr);
     642             :                                 }
     643       31588 :                                 exp_setname(sql->sa, e, tnme, cnme );
     644             :                         }
     645             :                 }
     646             :         }
     647             :         /* op_projects can have a order by list */
     648        8956 :         if (r->op == op_project && r->r) {
     649             :                 list *exps = r->r;
     650           0 :                 node *ne = exps->h;
     651             : 
     652           0 :                 list_hash_clear(exps);
     653           0 :                 for (; ne; ne = ne->next) {
     654           0 :                         if (all) {
     655           0 :                                 nr = ++sql->label;
     656           0 :                                 cnme = number2name(cname, sizeof(cname), nr);
     657             :                         }
     658           0 :                         exp_setname(sql->sa, ne->data, tnme, cnme );
     659             :                 }
     660             :         }
     661        8956 :         return r;
     662             : }
     663             : 
     664             : sql_exp *
     665       32067 : rel_project_add_exp( mvc *sql, sql_rel *rel, sql_exp *e)
     666             : {
     667       32067 :         assert(is_project(rel->op));
     668             : 
     669       32067 :         if (!exp_name(e))
     670          56 :                 exp_label(sql->sa, e, ++sql->label);
     671       32067 :         if (is_simple_project(rel->op)) {
     672       32046 :                 sql_rel *l = rel->l;
     673       32046 :                 if (!rel->exps)
     674          19 :                         rel->exps = new_exp_list(sql->sa);
     675       32046 :                 if (l && is_groupby(l->op) && exp_card(e) <= CARD_ATOM && list_empty(l->exps))
     676           0 :                         e = rel_project_add_exp(sql, l, e);
     677       32046 :                 if (e->card > rel->card)
     678          42 :                         rel->card = e->card;
     679       32046 :                 append(rel->exps, e);
     680       32046 :                 rel->nrcols++;
     681          21 :         } else if (is_groupby(rel->op)) {
     682          21 :                 return rel_groupby_add_aggr(sql, rel, e);
     683             :         }
     684       32046 :         e = exp_ref(sql, e);
     685       32046 :         return e;
     686             : }
     687             : 
     688             : sql_rel *
     689      295262 : rel_select_add_exp(sql_allocator *sa, sql_rel *l, sql_exp *e)
     690             : {
     691      295262 :         if ((l->op != op_select && !is_outerjoin(l->op)) || rel_is_ref(l))
     692        3924 :                 return rel_select(sa, l, e);
     693             : 
     694             : /*      allow during AST->relational for bool expresssions as well
     695             :         if (e->type != e_cmp && e->card > CARD_ATOM) {
     696             :                 sql_exp *t = exp_atom_bool(sa, 1);
     697             :                 e = exp_compare(sa, e, t, cmp_equal);
     698             :         }
     699             : */
     700      291338 :         if (!l->exps)
     701        5188 :                 l->exps = new_exp_list(sa);
     702      291338 :         append(l->exps, e);
     703      291338 :         return l;
     704             : }
     705             : 
     706             : void
     707      425452 : rel_join_add_exp( sql_allocator *sa, sql_rel *rel, sql_exp *e)
     708             : {
     709      425452 :         assert(is_join(rel->op) || is_semi(rel->op) || is_select(rel->op));
     710             : 
     711      425452 :         if (!rel->exps)
     712      382239 :                 rel->exps = new_exp_list(sa);
     713      425452 :         append(rel->exps, e);
     714      425452 :         if (e->card > rel->card)
     715           0 :                 rel->card = e->card;
     716      425452 : }
     717             : 
     718             : sql_exp *
     719       69461 : rel_groupby_add_aggr(mvc *sql, sql_rel *rel, sql_exp *e)
     720             : {
     721             :         sql_exp *m = NULL, *ne;
     722             : 
     723       69461 :         if (list_empty(rel->r))
     724       25262 :                 rel->card = e->card = CARD_ATOM;
     725             : 
     726       69461 :         if ((m=exps_any_match(rel->exps, e)) == NULL) {
     727       40910 :                 if (!exp_name(e))
     728       40841 :                         exp_label(sql->sa, e, ++sql->label);
     729       40910 :                 append(rel->exps, e);
     730       40910 :                 rel->nrcols++;
     731             :                 m = e;
     732             :         }
     733       69461 :         ne = exp_ref(sql, m);
     734       69461 :         return ne;
     735             : }
     736             : 
     737             : sql_rel *
     738      262126 : rel_select(sql_allocator *sa, sql_rel *l, sql_exp *e)
     739             : {
     740             :         sql_rel *rel;
     741             : 
     742      262126 :         if (l && is_outerjoin(l->op) && !is_processed(l)) {
     743         141 :                 if (e) {
     744         132 :                         if (!l->exps)
     745         126 :                                 l->exps = new_exp_list(sa);
     746         132 :                         append(l->exps, e);
     747             :                 }
     748         141 :                 return l;
     749             :         }
     750             : 
     751      261985 :         if (l && is_select(l->op) && !rel_is_ref(l)) { /* refine old select */
     752        7063 :                 if (e)
     753        7063 :                         rel_select_add_exp(sa, l, e);
     754        7063 :                 return l;
     755             :         }
     756      254922 :         rel = rel_create(sa);
     757      254922 :         if(!rel)
     758             :                 return NULL;
     759             : 
     760      254922 :         rel->l = l;
     761      254922 :         rel->r = NULL;
     762      254922 :         rel->op = op_select;
     763      254922 :         rel->exps = new_exp_list(sa);
     764      254922 :         if (e)
     765      176949 :                 rel_select_add_exp(sa, rel, e);
     766      254922 :         rel->card = CARD_ATOM; /* no relation */
     767      254922 :         if (l) {
     768      254922 :                 rel->card = l->card;
     769      254922 :                 rel->nrcols = l->nrcols;
     770      254922 :                 if (is_single(l))
     771        1029 :                         set_single(rel);
     772             :         }
     773             :         return rel;
     774             : }
     775             : 
     776             : sql_rel *
     777       34582 : rel_groupby(mvc *sql, sql_rel *l, list *groupbyexps )
     778             : {
     779       34582 :         sql_rel *rel = rel_create(sql->sa);
     780       34582 :         list *aggrs = new_exp_list(sql->sa);
     781             :         node *en;
     782       34582 :         if(!rel || !aggrs) {
     783           0 :                 rel_destroy(rel);
     784           0 :                 return NULL;
     785             :         }
     786             : 
     787       34582 :         rel->card = CARD_ATOM;
     788             :         /* reduce duplicates in groupbyexps */
     789       34582 :         if (groupbyexps && list_length(groupbyexps) > 1) {
     790        4767 :                 list *gexps = sa_list(sql->sa);
     791             : 
     792       22972 :                 for (en = groupbyexps->h; en; en = en->next) {
     793       18205 :                         sql_exp *e = en->data;
     794             : 
     795       18205 :                         if (!exps_any_match_same_or_no_alias(gexps, e))
     796       18112 :                                 append(gexps, e);
     797             :                 }
     798             :                 groupbyexps = gexps;
     799             :         }
     800             : 
     801       34582 :         if (groupbyexps) {
     802        8422 :                 rel->card = CARD_AGGR;
     803       30043 :                 for (en = groupbyexps->h; en; en = en->next) {
     804       21621 :                         sql_exp *e = en->data, *ne;
     805             : 
     806             :                         /* after the group by the cardinality reduces */
     807       21621 :                         e->card = MIN(e->card, rel->card); /* if the column is an atom, the cardinality should not change */
     808       21621 :                         ne = exp_ref(sql, e);
     809       21621 :                         ne = exp_propagate(sql->sa, ne, e);
     810       21621 :                         append(aggrs, ne);
     811             :                 }
     812             :         }
     813       34582 :         rel->l = l;
     814       34582 :         rel->r = groupbyexps;
     815       34582 :         rel->exps = aggrs;
     816       34582 :         rel->nrcols = aggrs?list_length(aggrs):0;
     817       34582 :         rel->op = op_groupby;
     818       34582 :         rel->grouped = 1;
     819       34582 :         return rel;
     820             : }
     821             : 
     822             : sql_rel *
     823      791186 : rel_project(sql_allocator *sa, sql_rel *l, list *e)
     824             : {
     825      791186 :         sql_rel *rel = rel_create(sa);
     826      791186 :         if(!rel)
     827             :                 return NULL;
     828             : 
     829      791186 :         rel->l = l;
     830      791186 :         rel->r = NULL;
     831      791186 :         rel->op = op_project;
     832      791186 :         rel->exps = e;
     833      791186 :         rel->card = exps_card(e);
     834      791186 :         if (l) {
     835      667590 :                 rel->card = l->card;
     836      667590 :                 if (e)
     837      612960 :                         rel->nrcols = list_length(e);
     838             :                 else
     839       54630 :                         rel->nrcols = l->nrcols;
     840      667590 :                 rel->single = is_single(l);
     841             :         }
     842      791186 :         if (e && !list_empty(e)) {
     843      736314 :                 set_processed(rel);
     844      736314 :                 rel->nrcols = list_length(e);
     845             :         }
     846             :         return rel;
     847             : }
     848             : 
     849             : sql_rel*
     850           7 : rel_project_exp(sql_allocator *sa, sql_exp *e)
     851             : {
     852           7 :         sql_rel *rel = rel_project(sa, NULL, append(new_exp_list(sa), e));
     853             : 
     854           7 :         return rel;
     855             : }
     856             : 
     857             : sql_rel *
     858         400 : rel_exception(sql_allocator *sa, sql_rel *l, sql_rel *r, list *exps)
     859             : {
     860         400 :         sql_rel *rel = rel_create(sa);
     861         400 :         if(!rel)
     862             :                 return NULL;
     863         400 :         rel->l = l;
     864         400 :         rel->r = r;
     865         400 :         rel->exps = exps;
     866         400 :         rel->op = op_ddl;
     867         400 :         rel->flag = ddl_exception;
     868         400 :         return rel;
     869             : }
     870             : 
     871             : sql_rel *
     872         186 : rel_relational_func(sql_allocator *sa, sql_rel *l, list *exps)
     873             : {
     874         186 :         sql_rel *rel = rel_create(sa);
     875         186 :         if(!rel)
     876             :                 return NULL;
     877             : 
     878         186 :         rel->flag = 1;
     879         186 :         rel->l = l;
     880         186 :         rel->op = op_table;
     881         186 :         rel->exps = exps;
     882         186 :         rel->card = CARD_MULTI;
     883         186 :         rel->nrcols = list_length(exps);
     884         186 :         return rel;
     885             : }
     886             : 
     887             : sql_rel *
     888       17734 : rel_table_func(sql_allocator *sa, sql_rel *l, sql_exp *f, list *exps, int kind)
     889             : {
     890       17734 :         sql_rel *rel = rel_create(sa);
     891       17734 :         if(!rel)
     892             :                 return NULL;
     893             : 
     894       17734 :         assert(kind > 0);
     895       17734 :         rel->flag = kind;
     896       17734 :         rel->l = l; /* relation before call */
     897       17734 :         rel->r = f; /* expression (table func call) */
     898       17734 :         rel->op = op_table;
     899       17734 :         rel->exps = exps;
     900       17734 :         rel->card = CARD_MULTI;
     901       17734 :         rel->nrcols = list_length(exps);
     902       17734 :         return rel;
     903             : }
     904             : 
     905             : static void
     906      365040 : exps_reset_props(list *exps, bool setnil)
     907             : {
     908      365040 :         if (!list_empty(exps)) {
     909     5310530 :                 for (node *m = exps->h; m; m = m->next) {
     910     4945496 :                         sql_exp *e = m->data;
     911             : 
     912     4945496 :                         if (setnil)
     913      433998 :                                 set_has_nil(e);
     914     4945496 :                         set_not_unique(e);
     915             :                 }
     916             :         }
     917      365040 : }
     918             : 
     919             : list *
     920     1440734 : _rel_projections(mvc *sql, sql_rel *rel, const char *tname, int settname, int intern, int basecol /* basecol only */ )
     921             : {
     922             :         list *lexps, *rexps, *exps;
     923             : 
     924             :         if (mvc_highwater(sql))
     925           0 :                 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
     926             : 
     927     1529880 :         if (!rel)
     928           0 :                 return new_exp_list(sql->sa);
     929             : 
     930     1529880 :         if (!tname && is_basetable(rel->op) && !is_processed(rel))
     931      344724 :                 rel_base_use_all( sql, rel);
     932             : 
     933     1529880 :         switch(rel->op) {
     934      182520 :         case op_join:
     935             :         case op_left:
     936             :         case op_right:
     937             :         case op_full:
     938      182520 :                 lexps = _rel_projections(sql, rel->l, tname, settname, intern, basecol);
     939      182520 :                 exps_reset_props(lexps, is_right(rel->op) || is_full(rel->op));
     940      182520 :                 rexps = _rel_projections(sql, rel->r, tname, settname, intern, basecol);
     941      182520 :                 exps_reset_props(rexps, is_left(rel->op) || is_full(rel->op));
     942      182520 :                 return list_merge(lexps, rexps, (fdup)NULL);
     943       11124 :         case op_groupby:
     944       11124 :                 if (list_empty(rel->exps) && rel->r) {
     945             :                         list *r = rel->r;
     946             :                         int label = 0;
     947             : 
     948           0 :                         if (!settname)
     949           0 :                                 label = ++sql->label;
     950           0 :                         exps = new_exp_list(sql->sa);
     951           0 :                         for (node *en = r->h; en; en = en->next) {
     952           0 :                                 sql_exp *e = en->data;
     953             : 
     954           0 :                                 if (basecol && !is_basecol(e))
     955           0 :                                         continue;
     956           0 :                                 if (intern || !is_intern(e)) {
     957           0 :                                         append(exps, e = exp_alias_or_copy(sql, tname, exp_name(e), rel, e));
     958           0 :                                         if (!settname) /* noname use alias */
     959           0 :                                                 exp_setrelname(sql->sa, e, label);
     960             : 
     961             :                                 }
     962             :                         }
     963             :                         return exps;
     964             :                 }
     965             :                 /* fall through */
     966             :         case op_project:
     967             :         case op_basetable:
     968             :         case op_table:
     969             : 
     970             :         case op_union:
     971             :         case op_except:
     972             :         case op_inter:
     973     1258214 :                 if (is_basetable(rel->op) && !rel->exps)
     974       90620 :                         return rel_base_projection(sql, rel, intern);
     975     1167594 :                 if (rel->exps) {
     976             :                         int label = 0;
     977             : 
     978     1113582 :                         if (!settname)
     979      232268 :                                 label = ++sql->label;
     980     1113582 :                         exps = new_exp_list(sql->sa);
     981     7000391 :                         for (node *en = rel->exps->h; en; en = en->next) {
     982     5886809 :                                 sql_exp *e = en->data;
     983             : 
     984     5886809 :                                 if (basecol && !is_basecol(e))
     985          39 :                                         continue;
     986     5886770 :                                 if (intern || !is_intern(e)) {
     987     5868524 :                                         append(exps, e = exp_alias_or_copy(sql, tname, exp_name(e), rel, e));
     988     5868524 :                                         if (!settname) /* noname use alias */
     989     1528682 :                                                 exp_setrelname(sql->sa, e, label);
     990             : 
     991             :                                 }
     992             :                         }
     993             :                         return exps;
     994             :                 }
     995             :                 /* I only expect set relations to hit here */
     996       54012 :                 assert(is_set(rel->op));
     997       54012 :                 lexps = _rel_projections(sql, rel->l, tname, settname, intern, basecol);
     998       54012 :                 rexps = _rel_projections(sql, rel->r, tname, settname, intern, basecol);
     999       54012 :                 if (lexps && rexps) {
    1000             :                         int label = 0;
    1001             : 
    1002       54012 :                         if (!settname)
    1003       54012 :                                 label = ++sql->label;
    1004       54012 :                         assert(list_length(lexps) == list_length(rexps));
    1005      414598 :                         for (node *en = lexps->h; en; en = en->next) {
    1006      360586 :                                 sql_exp *e = en->data;
    1007             : 
    1008      360586 :                                 e->card = rel->card;
    1009      360586 :                                 if (!settname) /* noname use alias */
    1010      360586 :                                         exp_setrelname(sql->sa, e, label);
    1011             :                         }
    1012             :                 }
    1013             :                 return lexps;
    1014       89146 :         case op_ddl:
    1015             :         case op_semi:
    1016             :         case op_anti:
    1017             : 
    1018             :         case op_select:
    1019             :         case op_topn:
    1020             :         case op_sample:
    1021       89146 :                 return _rel_projections(sql, rel->l, tname, settname, intern, basecol);
    1022             :         default:
    1023             :                 return NULL;
    1024             :         }
    1025             : }
    1026             : 
    1027             : list *
    1028      947337 : rel_projections(mvc *sql, sql_rel *rel, const char *tname, int settname, int intern)
    1029             : {
    1030      947337 :         assert(tname == NULL);
    1031      947337 :         return _rel_projections(sql, rel, tname, settname, intern, 0);
    1032             : }
    1033             : 
    1034             : /* find the path to the relation containing the base of the expression
    1035             :         (e_column), in most cases this means go down the join tree and
    1036             :         find the base column.
    1037             :  */
    1038             : static int
    1039     3957854 : rel_bind_path_(mvc *sql, sql_rel *rel, sql_exp *e, list *path )
    1040             : {
    1041             :         int found = 0;
    1042             : 
    1043             :         if (mvc_highwater(sql)) {
    1044           0 :                 sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    1045           0 :                 return 0;
    1046             :         }
    1047             : 
    1048     3957854 :         switch (rel->op) {
    1049     1845738 :         case op_join:
    1050             :         case op_left:
    1051             :         case op_right:
    1052             :         case op_full:
    1053             :                 /* first right (possible subquery) */
    1054     1845738 :                 found = rel_bind_path_(sql, rel->r, e, path);
    1055     1845738 :                 if (!found)
    1056     1561172 :                         found = rel_bind_path_(sql, rel->l, e, path);
    1057             :                 break;
    1058      104912 :         case op_semi:
    1059             :         case op_anti:
    1060             : 
    1061             :         case op_select:
    1062             :         case op_topn:
    1063             :         case op_sample:
    1064      104912 :                 found = rel_bind_path_(sql, rel->l, e, path);
    1065      104912 :                 break;
    1066             : 
    1067     1834765 :         case op_basetable:
    1068     1834765 :                 if (e->l)
    1069     1834765 :                         found = (rel_base_bind_column2_(rel, e->l, e->r) != NULL);
    1070             :                 else
    1071           0 :                         found = (rel_base_bind_column_(rel, e->r) != NULL);
    1072             :                 break;
    1073       45294 :         case op_union:
    1074             :         case op_inter:
    1075             :         case op_except:
    1076       45294 :                 if (!rel->exps) {
    1077           0 :                         found = rel_bind_path_(sql, rel->l, e, path);
    1078           0 :                         assert(0);
    1079             :                         break;
    1080             :                 }
    1081             :                 /* fall through */
    1082             :         case op_groupby:
    1083             :         case op_project:
    1084             :         case op_table:
    1085      172439 :                 if (!rel->exps)
    1086             :                         break;
    1087      172439 :                 if (!found && e->l && exps_bind_column2(rel->exps, e->l, e->r, NULL))
    1088             :                         found = 1;
    1089       86522 :                 if (!found && !e->l && exps_bind_column(rel->exps, e->r, NULL, NULL, 1))
    1090             :                         found = 1;
    1091             :                 break;
    1092             :         case op_insert:
    1093             :         case op_update:
    1094             :         case op_delete:
    1095             :         case op_truncate:
    1096             :         case op_merge:
    1097             :                 break;
    1098             :         case op_ddl:
    1099             :                 break;
    1100             :         }
    1101     3957854 :         if (found)
    1102     2356635 :                 list_prepend(path, rel);
    1103             :         return found;
    1104             : }
    1105             : 
    1106             : static list *
    1107      501156 : rel_bind_path(mvc *sql, sql_rel *rel, sql_exp *e, list *path)
    1108             : {
    1109      501156 :         if (!path)
    1110             :                 return NULL;
    1111             : 
    1112      501156 :         if (e->type == e_convert)
    1113       49187 :                 path = rel_bind_path(sql, rel, e->l, path);
    1114      451969 :         else if (e->type == e_column) {
    1115      446032 :                 if (rel) {
    1116      446032 :                         if (!rel_bind_path_(sql, rel, e, path)) {
    1117             :                                 /* something is wrong */
    1118             :                                 return NULL;
    1119             :                         }
    1120             :                 }
    1121      446032 :                 return path;
    1122             :         }
    1123             :         /* default the top relation */
    1124       55124 :         append(path, rel);
    1125       55124 :         return path;
    1126             : }
    1127             : 
    1128             : static sql_rel *
    1129       23426 : rel_select_push_exp_down(mvc *sql, sql_rel *rel, sql_exp *e)
    1130             : {
    1131       23426 :         sql_rel *r = rel->l, *jl = r->l, *jr = r->r;
    1132       23426 :         int left = r->op == op_join || r->op == op_left;
    1133       23426 :         int right = r->op == op_join || r->op == op_right;
    1134             :         int done = 0;
    1135             : 
    1136       23426 :         assert(is_select(rel->op));
    1137       23426 :         if (!is_full(r->op) && !is_single(r)) {
    1138       23426 :                 if (left && rel_rebind_exp(sql, jl, e)) {
    1139             :                         done = 1;
    1140           6 :                         r->l = jl = rel_select_add_exp(sql->sa, jl, e);
    1141       23420 :                 } else if (right && rel_rebind_exp(sql, jr, e)) {
    1142             :                         done = 1;
    1143           5 :                         r->r = jr = rel_select_add_exp(sql->sa, jr, e);
    1144             :                 }
    1145             :         }
    1146             :         if (!done)
    1147       23415 :                 rel_select_add_exp(sql->sa, rel, e);
    1148       23426 :         return rel;
    1149             : }
    1150             : 
    1151             : /* ls is the left expression of the select, e is the select expression.  */
    1152             : sql_rel *
    1153      104287 : rel_push_select(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *e, int f)
    1154             : {
    1155      104287 :         list *l = rel_bind_path(sql, rel, ls, sa_list(sql->sa));
    1156             :         node *n;
    1157             :         sql_rel *lrel = NULL, *p = NULL;
    1158             : 
    1159      104287 :         if (!l)
    1160             :                 return NULL;
    1161      104287 :         if (is_sql_or(f)) /* expression has no clear parent relation, so filter current with it */
    1162       18812 :                 return rel_select(sql->sa, rel, e);
    1163             : 
    1164      249654 :         for (n = l->h; n; n = n->next ) {
    1165      248458 :                 lrel = n->data;
    1166             : 
    1167      248458 :                 if (rel_is_ref(lrel))
    1168             :                         break;
    1169             : 
    1170             :                 /* push down as long as the operators allow this */
    1171      248381 :                 if (!is_select(lrel->op) &&
    1172      224405 :                     !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
    1173       84202 :                     lrel->op != op_join &&
    1174             :                     lrel->op != op_left)
    1175             :                         break;
    1176             :                 /* pushing through left head of a left join is allowed */
    1177      164183 :                 if (lrel->op == op_left && (!n->next || lrel->l != n->next->data))
    1178             :                         break;
    1179             :                 p = lrel;
    1180             :         }
    1181       85475 :         if (!lrel)
    1182             :                 return NULL;
    1183       85475 :         if (p && is_select(p->op) && !rel_is_ref(p)) { /* refine old select */
    1184       20627 :                 p = rel_select_push_exp_down(sql, p, e);
    1185             :         } else {
    1186       64848 :                 sql_rel *n = rel_select(sql->sa, lrel, e);
    1187             : 
    1188       64848 :                 if (p && p != lrel) {
    1189       62848 :                         assert(p->op == op_join || p->op == op_left || is_semi(p->op));
    1190       62848 :                         if (p->l == lrel) {
    1191       22354 :                                 p->l = n;
    1192             :                         } else {
    1193       40494 :                                 p->r = n;
    1194             :                         }
    1195             :                 } else {
    1196        2000 :                         if (rel != lrel)
    1197           0 :                                 assert(0);
    1198             :                         rel = n;
    1199             :                 }
    1200             :         }
    1201             :         return rel;
    1202             : }
    1203             : 
    1204             : /* ls and rs are the left and right expression of the join, e is the
    1205             :    join expression.
    1206             :  */
    1207             : sql_rel *
    1208      173579 : rel_push_join(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *rs, sql_exp *rs2, sql_exp *e, int f)
    1209             : {
    1210      173579 :         list *l = rel_bind_path(sql, rel, ls, sa_list(sql->sa));
    1211      173579 :         list *r = rel_bind_path(sql, rel, rs, sa_list(sql->sa));
    1212             :         list *r2 = NULL;
    1213             :         node *ln, *rn;
    1214             :         sql_rel *lrel = NULL, *rrel = NULL, *rrel2 = NULL, *p = NULL;
    1215             : 
    1216      173579 :         if (rs2)
    1217         524 :                 r2 = rel_bind_path(sql, rel, rs2, sa_list(sql->sa));
    1218      173579 :         if (!l || !r || (rs2 && !r2))
    1219             :                 return NULL;
    1220             : 
    1221      173579 :         if (is_sql_or(f))
    1222        2172 :                 return rel_push_select(sql, rel, ls, e, f);
    1223             : 
    1224             :         p = rel;
    1225      171407 :         if (r2) {
    1226             :                 node *rn2;
    1227             : 
    1228        1039 :                 for (ln = l->h, rn = r->h, rn2 = r2->h; ln && rn && rn2; ln = ln->next, rn = rn->next, rn2 = rn2->next ) {
    1229         545 :                         lrel = ln->data;
    1230         545 :                         rrel = rn->data;
    1231         545 :                         rrel2 = rn2->data;
    1232             : 
    1233         545 :                         if (rel_is_ref(lrel) || rel_is_ref(rrel) || rel_is_ref(rrel2) || is_processed(lrel) || is_processed(rrel))
    1234             :                                 break;
    1235             : 
    1236             :                         /* push down as long as the operators allow this
    1237             :                                 and the relation is equal.
    1238             :                         */
    1239         540 :                         if (lrel != rrel || lrel != rrel2 ||
    1240         523 :                                 (!is_select(lrel->op) &&
    1241          65 :                                  !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
    1242           0 :                                  lrel->op != op_join &&
    1243             :                                  lrel->op != op_left))
    1244             :                                 break;
    1245             :                         /* pushing through left head of a left join is allowed */
    1246         523 :                         if (lrel->op == op_left && (!ln->next || lrel->l != ln->next->data))
    1247             :                                 break;
    1248             :                         p = lrel;
    1249             :                 }
    1250             :         } else {
    1251      784957 :                 for (ln = l->h, rn = r->h; ln && rn; ln = ln->next, rn = rn->next ) {
    1252      782329 :                         lrel = ln->data;
    1253      782329 :                         rrel = rn->data;
    1254             : 
    1255      782329 :                         if (rel_is_ref(lrel) || rel_is_ref(rrel) || is_processed(lrel) || is_processed(rrel))
    1256             :                                 break;
    1257             : 
    1258             :                         /* push down as long as the operators allow this
    1259             :                                 and the relation is equal.
    1260             :                         */
    1261      750013 :                         if (lrel != rrel ||
    1262      615726 :                                 (!is_select(lrel->op) &&
    1263      611684 :                                  !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
    1264        1660 :                                  lrel->op != op_join &&
    1265             :                                  lrel->op != op_left))
    1266             :                                 break;
    1267             :                         /* pushing through left head of a left join is allowed */
    1268      614066 :                         if (lrel->op == op_left && (!ln->next || lrel->l != ln->next->data))
    1269             :                                 break;
    1270             :                         p = lrel;
    1271             :                 }
    1272             :         }
    1273      171407 :         if (!lrel || !rrel || (r2 && !rrel2))
    1274             :                 return NULL;
    1275             : 
    1276             :         /* filter on columns of this relation */
    1277      171407 :         if ((lrel == rrel && (!r2 || lrel == rrel2) && lrel->op != op_join) || rel_is_ref(p)) {
    1278        2814 :                 if (is_select(lrel->op) && !rel_is_ref(lrel)) {
    1279        1138 :                         lrel = rel_select_push_exp_down(sql, lrel, e);
    1280        1676 :                 } else if (p && is_select(p->op) && !rel_is_ref(p)) {
    1281        1661 :                         p = rel_select_push_exp_down(sql, p, e);
    1282             :                 } else {
    1283          15 :                         sql_rel *n = rel_select(sql->sa, lrel, e);
    1284             : 
    1285          15 :                         if (p && p != lrel) {
    1286          15 :                                 if (p->l == lrel)
    1287           5 :                                         p->l = n;
    1288             :                                 else
    1289          10 :                                         p->r = n;
    1290             :                         } else {
    1291             :                                 rel = n;
    1292             :                         }
    1293             :                 }
    1294        2814 :                 return rel;
    1295             :         }
    1296             : 
    1297      168593 :         rel_join_add_exp( sql->sa, p, e);
    1298      168593 :         return rel;
    1299             : }
    1300             : 
    1301             : sql_rel *
    1302       17641 : rel_or(mvc *sql, sql_rel *rel, sql_rel *l, sql_rel *r, list *oexps, list *lexps, list *rexps)
    1303             : {
    1304       17641 :         sql_rel *ll = l->l, *rl = r->l;
    1305             :         list *ls, *rs;
    1306             : 
    1307       17641 :         assert(!lexps || l == r);
    1308       17641 :         if (l == r && lexps) { /* merge both lists */
    1309          33 :                 sql_exp *e = exp_or(sql->sa, lexps, rexps, 0);
    1310          33 :                 list *nl = oexps?oexps:new_exp_list(sql->sa);
    1311             : 
    1312          33 :                 rel_destroy(r);
    1313          33 :                 append(nl, e);
    1314          33 :                 if (is_outerjoin(l->op) && is_processed(l))
    1315           0 :                         l = rel_select(sql->sa, l, NULL);
    1316          33 :                 l->exps = nl;
    1317          33 :                 return l;
    1318             :         }
    1319             : 
    1320             :         /* favor or expressions over union */
    1321       17608 :         if (l->op == r->op && is_select(l->op) &&
    1322       17608 :             ll == rl && ll == rel && !rel_is_ref(l) && !rel_is_ref(r)) {
    1323       17608 :                 sql_exp *e = exp_or(sql->sa, l->exps, r->exps, 0);
    1324       17608 :                 list *nl = new_exp_list(sql->sa);
    1325             : 
    1326       17608 :                 rel_destroy(r);
    1327       17608 :                 append(nl, e);
    1328       17608 :                 l->exps = nl;
    1329             : 
    1330             :                 /* merge and expressions */
    1331       17608 :                 ll = l->l;
    1332       19945 :                 while (ll && is_select(ll->op) && !rel_is_ref(ll)) {
    1333        2337 :                         list_merge(l->exps, ll->exps, (fdup)NULL);
    1334        2337 :                         l->l = ll->l;
    1335        2337 :                         ll->l = NULL;
    1336        2337 :                         rel_destroy(ll);
    1337        2337 :                         ll = l->l;
    1338             :                 }
    1339             :                 return l;
    1340             :         }
    1341             : 
    1342           0 :         if (rel) {
    1343           0 :                 ls = rel_projections(sql, rel, NULL, 1, 1);
    1344           0 :                 rs = rel_projections(sql, rel, NULL, 1, 1);
    1345             :         } else {
    1346           0 :                 ls = rel_projections(sql, l, NULL, 1, 1);
    1347           0 :                 rs = rel_projections(sql, r, NULL, 1, 1);
    1348             :         }
    1349           0 :         set_processed(l);
    1350           0 :         set_processed(r);
    1351           0 :         rel = rel_setop_check_types(sql, l, r, ls, rs, op_union);
    1352           0 :         if (!rel)
    1353             :                 return NULL;
    1354           0 :         rel_setop_set_exps(sql, rel, rel_projections(sql, rel, NULL, 1, 1), false);
    1355           0 :         set_processed(rel);
    1356           0 :         rel->nrcols = list_length(rel->exps);
    1357           0 :         rel = rel_distinct(rel);
    1358           0 :         if (!rel)
    1359             :                 return NULL;
    1360           0 :         if (exps_card(l->exps) <= CARD_AGGR &&
    1361           0 :             exps_card(r->exps) <= CARD_AGGR)
    1362             :         {
    1363           0 :                 rel->card = exps_card(l->exps);
    1364           0 :                 exps_fix_card( rel->exps, rel->card);
    1365             :         }
    1366             :         return rel;
    1367             : }
    1368             : 
    1369             : sql_table *
    1370        3685 : rel_ddl_table_get(sql_rel *r)
    1371             : {
    1372        3685 :         if (r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
    1373        3685 :                 sql_exp *e = r->exps->t->data;
    1374        3685 :                 atom *a = e->l;
    1375             : 
    1376        3685 :                 return a->data.val.pval;
    1377             :         }
    1378             :         return NULL;
    1379             : }
    1380             : 
    1381             : sql_rel *
    1382        2254 : rel_ddl_basetable_get(sql_rel *r)
    1383             : {
    1384        2254 :         if (r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
    1385        2254 :                 return r->l;
    1386             :         }
    1387             :         return NULL;
    1388             : }
    1389             : 
    1390             : static sql_exp *
    1391         427 : exps_find_identity(list *exps, sql_rel *p)
    1392             : {
    1393             :         node *n;
    1394             : 
    1395        2438 :         for (n=exps->h; n; n = n->next) {
    1396        2099 :                 sql_exp *e = n->data;
    1397             : 
    1398        2099 :                 if (is_identity(e, p))
    1399          88 :                         return e;
    1400             :         }
    1401             :         return NULL;
    1402             : }
    1403             : 
    1404             : static sql_rel *
    1405         706 : _rel_add_identity(mvc *sql, sql_rel *rel, sql_exp **exp)
    1406             : {
    1407         706 :         list *exps = rel_projections(sql, rel, NULL, 1, 1);
    1408             :         sql_exp *e;
    1409             : 
    1410         706 :         if (list_empty(exps)) {
    1411           0 :                 *exp = NULL;
    1412           0 :                 return rel;
    1413             :         }
    1414         706 :         if (!is_simple_project(rel->op) || !list_empty(rel->r) || rel_is_ref(rel))
    1415         536 :                 rel = rel_project(sql->sa, rel, exps);
    1416         706 :         e = rel->exps->h->data;
    1417         706 :         e = exp_column(sql->sa, exp_relname(e), exp_name(e), exp_subtype(e), rel->card, has_nil(e), is_unique(e), is_intern(e));
    1418         706 :         e = exp_unop(sql->sa, e, sql_bind_func(sql, "sys", "identity", exp_subtype(e), NULL, F_FUNC));
    1419         706 :         set_intern(e);
    1420         706 :         set_has_no_nil(e);
    1421         706 :         set_unique(e);
    1422         706 :         e->p = prop_create(sql->sa, PROP_HASHCOL, e->p);
    1423         706 :         *exp = exp_label(sql->sa, e, ++sql->label);
    1424         706 :         (void) rel_project_add_exp(sql, rel, e);
    1425         706 :         return rel;
    1426             : }
    1427             : 
    1428             : sql_rel *
    1429         596 : rel_add_identity(mvc *sql, sql_rel *rel, sql_exp **exp)
    1430             : {
    1431         596 :         if (rel && is_project(rel->op) && (*exp = exps_find_identity(rel->exps, rel->l)) != NULL)
    1432             :                 return rel;
    1433         508 :         return _rel_add_identity(sql, rel, exp);
    1434             : }
    1435             : 
    1436             : sql_rel *
    1437         198 : rel_add_identity2(mvc *sql, sql_rel *rel, sql_exp **exp)
    1438             : {
    1439             :         sql_rel *l = rel, *p = rel;
    1440             : 
    1441         198 :         if (rel && is_project(rel->op) && (*exp = exps_find_identity(rel->exps, rel->l)) != NULL)
    1442             :                 return rel;
    1443         424 :         while(l && !is_set(l->op) && rel_has_freevar(sql, l) && l->l) {
    1444             :                 p = l;
    1445             :                 l = l->l;
    1446             :         }
    1447         198 :         if (l != p) {
    1448             :                 sql_rel *o = rel;
    1449             :                 sql_exp *id;
    1450             : 
    1451          80 :                 p->l = _rel_add_identity(sql, l, exp);
    1452             :                 l = p->l;
    1453          80 :                 id = exp_ref(sql, *exp);
    1454         306 :                 while (o && o != l) {
    1455         226 :                         *exp = id;
    1456         226 :                         if (is_project(o->op))
    1457         190 :                                 rel_project_add_exp(sql, o, id);
    1458         226 :                         o = o->l;
    1459             :                 }
    1460             :                 return rel;
    1461             :         }
    1462         118 :         return _rel_add_identity(sql, rel, exp);
    1463             : }
    1464             : 
    1465             : sql_exp *
    1466        1536 : rel_find_column( sql_allocator *sa, sql_rel *rel, const char *tname, const char *cname )
    1467             : {
    1468        1820 :         if (!rel)
    1469             :                 return NULL;
    1470             : 
    1471        1820 :         if (rel->exps && (is_project(rel->op) || is_base(rel->op))) {
    1472        1536 :                 int ambiguous = 0, multi = 0;
    1473        1536 :                 sql_exp *e = exps_bind_column2(rel->exps, tname, cname, &multi);
    1474        1536 :                 if (!e && cname[0] == '%' && !tname)
    1475           0 :                         e = exps_bind_column(rel->exps, cname, &ambiguous, &multi, 0);
    1476        1536 :                 if (e && !ambiguous && !multi)
    1477        1536 :                         return exp_alias(sa, exp_relname(e), exp_name(e), exp_relname(e), cname, exp_subtype(e), e->card, has_nil(e), is_unique(e), is_intern(e));
    1478             :         }
    1479         284 :         if ((is_simple_project(rel->op) || is_groupby(rel->op)) && rel->l) {
    1480           0 :                 if (!is_processed(rel))
    1481             :                         return rel_find_column(sa, rel->l, tname, cname);
    1482         284 :         } else if (is_set(rel->op)) {
    1483           0 :                 assert(is_processed(rel));
    1484             :                 return NULL;
    1485         284 :         } else if (is_join(rel->op)) {
    1486           0 :                 sql_exp *e = rel_find_column(sa, rel->l, tname, cname);
    1487             : 
    1488           0 :                 if (e && (is_right(rel->op) || is_full(rel->op)))
    1489           0 :                         set_has_nil(e);
    1490           0 :                 if (!e) {
    1491           0 :                         e = rel_find_column(sa, rel->r, tname, cname);
    1492           0 :                         if (e && (is_left(rel->op) || is_full(rel->op)))
    1493           0 :                                 set_has_nil(e);
    1494             :                 }
    1495           0 :                 if (e)
    1496           0 :                         set_not_unique(e);
    1497           0 :                 return e;
    1498         284 :         } else if (is_semi(rel->op) ||
    1499           0 :                    is_select(rel->op) ||
    1500           0 :                    is_topn(rel->op) ||
    1501             :                    is_sample(rel->op)) {
    1502         284 :                 if (rel->l)
    1503             :                         return rel_find_column(sa, rel->l, tname, cname);
    1504             :         }
    1505             :         return NULL;
    1506             : }
    1507             : 
    1508             : int
    1509           0 : rel_in_rel(sql_rel *super, sql_rel *sub)
    1510             : {
    1511           0 :         if (!super)
    1512             :                 return 0;
    1513           0 :         if (super == sub)
    1514             :                 return 1;
    1515           0 :         if (is_join(super->op) || is_semi(super->op) || is_set(super->op) || is_modify(super->op) || is_ddl(super->op))
    1516           0 :                 return rel_in_rel(super->l, sub) || rel_in_rel(super->r, sub);
    1517           0 :         if (is_select(super->op) || is_simple_project(super->op) || is_groupby(super->op) || is_topn(super->op) || is_sample(super->op))
    1518           0 :                 return rel_in_rel(super->l, sub);
    1519             :         return 0;
    1520             : }
    1521             : 
    1522             : sql_rel*
    1523          16 : rel_parent(sql_rel *rel)
    1524             : {
    1525          16 :         if (rel->l && (is_project(rel->op) || is_topn(rel->op) || is_sample(rel->op))) {
    1526             :                 sql_rel *l = rel->l;
    1527          12 :                 if (is_project(l->op))
    1528          12 :                         return l;
    1529             :         }
    1530             :         return rel;
    1531             : }
    1532             : 
    1533             : sql_exp *
    1534       22943 : lastexp(sql_rel *rel)
    1535             : {
    1536       22943 :         if (!is_processed(rel) || is_topn(rel->op) || is_sample(rel->op))
    1537          16 :                 rel = rel_parent(rel);
    1538       22943 :         assert(list_length(rel->exps));
    1539       22943 :         assert(is_project(rel->op) || rel->op == op_table);
    1540       22943 :         return rel->exps->t->data;
    1541             : }
    1542             : 
    1543             : sql_rel *
    1544        4934 : rel_return_zero_or_one(mvc *sql, sql_rel *rel, exp_kind ek)
    1545             : {
    1546        4934 :         if (ek.card < card_set && rel->card > CARD_ATOM) {
    1547        3804 :                 list *exps = rel->exps;
    1548             : 
    1549        3804 :                 assert (is_simple_project(rel->op) || is_set(rel->op));
    1550        3804 :                 rel = rel_groupby(sql, rel, NULL);
    1551        7618 :                 for(node *n = exps->h; n; n=n->next) {
    1552        3814 :                         sql_exp *e = n->data;
    1553        3814 :                         if (!has_label(e))
    1554          49 :                                 exp_label(sql->sa, e, ++sql->label);
    1555        3814 :                         sql_subtype *t = exp_subtype(e); /* parameters don't have a type defined, for those use 'void' one */
    1556        3814 :                         sql_subfunc *zero_or_one = sql_bind_func(sql, "sys", "zero_or_one", t ? t : sql_bind_localtype("void"), NULL, F_AGGR);
    1557             : 
    1558        3814 :                         e = exp_ref(sql, e);
    1559        3814 :                         e = exp_aggr1(sql->sa, e, zero_or_one, 0, 0, CARD_ATOM, has_nil(e));
    1560        3814 :                         (void)rel_groupby_add_aggr(sql, rel, e);
    1561             :                 }
    1562             :         }
    1563        4934 :         return rel;
    1564             : }
    1565             : 
    1566             : sql_rel *
    1567       32982 : rel_zero_or_one(mvc *sql, sql_rel *rel, exp_kind ek)
    1568             : {
    1569       32982 :         if (is_topn(rel->op) || is_sample(rel->op))
    1570          17 :                 rel = rel_project(sql->sa, rel, rel_projections(sql, rel, NULL, 1, 0));
    1571       32982 :         if (ek.card < card_set && rel->card > CARD_ATOM) {
    1572       10224 :                 assert (is_simple_project(rel->op) || is_set(rel->op));
    1573             : 
    1574       10224 :                 list *exps = rel->exps;
    1575       20476 :                 for(node *n = exps->h; n; n=n->next) {
    1576       10252 :                         sql_exp *e = n->data;
    1577       10252 :                         if (!has_label(e))
    1578       10219 :                                 exp_label(sql->sa, e, ++sql->label);
    1579             :                 }
    1580       10224 :                 set_single(rel);
    1581             :         } else {
    1582       22758 :                 sql_exp *e = lastexp(rel);
    1583       22758 :                 if (!has_label(e))
    1584        9142 :                         exp_label(sql->sa, e, ++sql->label);
    1585             :         }
    1586       32982 :         return rel;
    1587             : }
    1588             : 
    1589             : static sql_rel *
    1590             : refs_find_rel(list *refs, sql_rel *rel)
    1591             : {
    1592             :         node *n;
    1593             : 
    1594       19035 :         for(n=refs->h; n; n = n->next->next) {
    1595       15849 :                 sql_rel *ref = n->data;
    1596       15849 :                 sql_rel *s = n->next->data;
    1597             : 
    1598       15849 :                 if (rel == ref)
    1599             :                         return s;
    1600             :         }
    1601             :         return NULL;
    1602             : }
    1603             : 
    1604             : static int exp_deps(mvc *sql, sql_exp *e, list *refs, list *l);
    1605             : 
    1606             : static int
    1607      495446 : exps_deps(mvc *sql, list *exps, list *refs, list *l)
    1608             : {
    1609             : 
    1610     1962607 :         for(node *n = exps->h; n; n = n->next)
    1611     1467161 :                 if (exp_deps(sql, n->data, refs, l) != 0)
    1612             :                         return -1;
    1613             :         return 0;
    1614             : }
    1615             : 
    1616             : static int
    1617     5736036 : id_cmp(sql_base *id1, sql_base *id2)
    1618             : {
    1619     5736036 :         if (id1->id == id2->id)
    1620       80704 :                 return 0;
    1621             :         return -1;
    1622             : }
    1623             : 
    1624             : static list *
    1625      518396 : cond_append(list *l, sql_base *b)
    1626             : {
    1627      518396 :         if (b->id >= FUNC_OIDS && !list_find(l, b, (fcmp) &id_cmp))
    1628      260385 :                 list_append(l, b);
    1629      518396 :         return l;
    1630             : }
    1631             : 
    1632             : static int rel_deps(mvc *sql, sql_rel *r, list *refs, list *l);
    1633             : 
    1634             : static int
    1635     1614831 : exp_deps(mvc *sql, sql_exp *e, list *refs, list *l)
    1636             : {
    1637             :         if (mvc_highwater(sql)) {
    1638           0 :                 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    1639           0 :                 return -1;
    1640             :         }
    1641             : 
    1642     1721097 :         switch(e->type) {
    1643       38515 :         case e_psm:
    1644       38515 :                 if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
    1645       16467 :                         return exp_deps(sql, e->l, refs, l);
    1646       22048 :                 } else if (e->flag & PSM_VAR) {
    1647             :                         return 0;
    1648       17994 :                 } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
    1649        5138 :                         if (exp_deps(sql, e->l, refs, l) != 0 || exps_deps(sql, e->r, refs, l) != 0)
    1650           0 :                                 return -1;
    1651        5138 :                         if (e->flag & PSM_IF && e->f)
    1652         627 :                                 return exps_deps(sql, e->f, refs, l);
    1653       12856 :                 } else if (e->flag & PSM_REL) {
    1654       12856 :                         sql_rel *rel = e->l;
    1655       12856 :                         return rel_deps(sql, rel, refs, l);
    1656             :                 }
    1657             :                 break;
    1658      574662 :         case e_atom:
    1659      574662 :                 if (e->f && exp_deps(sql, e->f, refs, l) != 0)
    1660           0 :                         return -1;
    1661             :                 break;
    1662             :         case e_column:
    1663             :                 break;
    1664       89772 :         case e_convert:
    1665       89772 :                 return exp_deps(sql, e->l, refs, l);
    1666      187491 :         case e_func: {
    1667      187491 :                 sql_subfunc *f = e->f;
    1668             : 
    1669      187491 :                 if (e->l && exps_deps(sql, e->l, refs, l) != 0)
    1670             :                         return -1;
    1671      187491 :                 cond_append(l, &f->func->base);
    1672      187491 :                 if (e->l && list_length(e->l) == 2 && strcmp(f->func->base.name, "next_value_for") == 0) {
    1673             :                         /* add dependency on seq nr */
    1674          83 :                         list *nl = e->l;
    1675          83 :                         sql_exp *schname = nl->h->data, *seqname = nl->t->data;
    1676          83 :                         char *sch_name = is_atom(schname->type) && schname->l ? ((atom*)schname->l)->data.val.sval : NULL;
    1677          83 :                         char *seq_name = is_atom(seqname->type) && seqname->l ? ((atom*)seqname->l)->data.val.sval : NULL;
    1678             : 
    1679          83 :                         if (sch_name && seq_name) {
    1680          83 :                                 sql_schema *sche = mvc_bind_schema(sql, sch_name);
    1681          83 :                                 if (sche) {
    1682          83 :                                         sql_sequence *seq = find_sql_sequence(sql->session->tr, sche, seq_name);
    1683          83 :                                         if (seq)
    1684          83 :                                                 cond_append(l, &seq->base);
    1685             :                                 }
    1686             :                         }
    1687             :                 }
    1688             :         } break;
    1689       15655 :         case e_aggr: {
    1690       15655 :                 sql_subfunc *a = e->f;
    1691             : 
    1692       15655 :                 if (e->l && exps_deps(sql, e->l, refs, l) != 0)
    1693             :                         return -1;
    1694       15655 :                 cond_append(l, &a->func->base);
    1695       15655 :         } break;
    1696       72384 :         case e_cmp: {
    1697       72384 :                 if (e->flag == cmp_or || e->flag == cmp_filter) {
    1698        1257 :                         if (e->flag == cmp_filter) {
    1699          12 :                                 sql_subfunc *f = e->f;
    1700          12 :                                 cond_append(l, &f->func->base);
    1701             :                         }
    1702        2514 :                         if (exps_deps(sql, e->l, refs, l) != 0 ||
    1703        1257 :                                 exps_deps(sql, e->r, refs, l) != 0)
    1704           0 :                                 return -1;
    1705       71127 :                 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
    1706        6144 :                         if (exp_deps(sql, e->l, refs, l) != 0 ||
    1707        3072 :                                 exps_deps(sql, e->r, refs, l) != 0)
    1708           0 :                                 return -1;
    1709             :                 } else {
    1710      136110 :                         if (exp_deps(sql, e->l, refs, l) != 0 ||
    1711       68055 :                                 exp_deps(sql, e->r, refs, l) != 0)
    1712           0 :                                 return -1;
    1713       68055 :                         if (e->f)
    1714             :                                 return exp_deps(sql, e->f, refs, l);
    1715             :                 }
    1716             :         }       break;
    1717             :         }
    1718             :         return 0;
    1719             : }
    1720             : 
    1721             : static int
    1722      380544 : rel_deps(mvc *sql, sql_rel *r, list *refs, list *l)
    1723             : {
    1724             :         if (mvc_highwater(sql)) {
    1725           0 :                 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    1726           0 :                 return -1;
    1727             :         }
    1728             : 
    1729      380544 :         if (!r)
    1730             :                 return 0;
    1731             : 
    1732      379828 :         if (rel_is_ref(r) && refs_find_rel(refs, r)) /* allready handled */
    1733             :                 return 0;
    1734      369846 :         switch (r->op) {
    1735       77273 :         case op_basetable: {
    1736       77273 :                 sql_table *t = r->l;
    1737             : 
    1738       77273 :                 cond_append(l, &t->base);
    1739             :                 /* find all used columns */
    1740      341076 :                 for (node *en = r->exps->h; en; en = en->next) {
    1741      263803 :                         sql_exp *exp = en->data;
    1742      263803 :                         const char *oname = exp->r;
    1743             : 
    1744      263803 :                         assert(!is_func(exp->type));
    1745      263803 :                         if (oname[0] == '%' && strcmp(oname, TID) == 0) {
    1746       29592 :                                 continue;
    1747      234211 :                         } else if (oname[0] == '%') {
    1748         211 :                                 sql_idx *i = find_sql_idx(t, oname+1);
    1749         211 :                                 cond_append(l, &i->base);
    1750             :                         } else {
    1751      234000 :                                 sql_column *c = find_sql_column(t, oname);
    1752      234000 :                                 cond_append(l, &c->base);
    1753             :                         }
    1754             :                 }
    1755             :         } break;
    1756        3671 :         case op_table: {
    1757        3671 :                 if ((IS_TABLE_PROD_FUNC(r->flag) || r->flag == TABLE_FROM_RELATION) && r->r) { /* table producing function, excluding rel_relational_func cases */
    1758             :                         sql_exp *op = r->r;
    1759        3671 :                         sql_subfunc *f = op->f;
    1760        3671 :                         cond_append(l, &f->func->base);
    1761             :                 }
    1762             :         } break;
    1763       60484 :         case op_join:
    1764             :         case op_left:
    1765             :         case op_right:
    1766             :         case op_full:
    1767             :         case op_semi:
    1768             :         case op_anti:
    1769             :         case op_union:
    1770             :         case op_except:
    1771             :         case op_inter:
    1772             : 
    1773             :         case op_insert:
    1774             :         case op_update:
    1775             :         case op_delete:
    1776             :         case op_merge:
    1777      120968 :                 if (rel_deps(sql, r->l, refs, l) != 0 ||
    1778       60484 :                         rel_deps(sql, r->r, refs, l) != 0)
    1779           0 :                         return -1;
    1780             :                 break;
    1781      136780 :         case op_project:
    1782             :         case op_select:
    1783             :         case op_groupby:
    1784             :         case op_topn:
    1785             :         case op_sample:
    1786             :         case op_truncate:
    1787      136780 :                 if (rel_deps(sql, r->l, refs, l) != 0)
    1788             :                         return -1;
    1789             :                 break;
    1790       91638 :         case op_ddl:
    1791       91638 :                 if (r->flag == ddl_output || r->flag == ddl_create_seq || r->flag == ddl_alter_seq || r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
    1792          21 :                         if (rel_deps(sql, r->l, refs, l) != 0)
    1793             :                                 return -1;
    1794       91617 :                 } else if (r->flag == ddl_list || r->flag == ddl_exception) {
    1795           0 :                         if (rel_deps(sql, r->l, refs, l) != 0 ||
    1796           0 :                                 rel_deps(sql, r->r, refs, l) != 0)
    1797           0 :                                 return -1;
    1798             :                 }
    1799             :                 break;
    1800             :         }
    1801      369846 :         if (!is_base(r->op) && r->exps) {
    1802      277101 :                 if (exps_deps(sql, r->exps, refs, l) != 0)
    1803             :                         return -1;
    1804             :         }
    1805      369846 :         if ((is_simple_project(r->op) || is_groupby(r->op)) && r->r) {
    1806       14060 :                 if (exps_deps(sql, r->r, refs, l) != 0)
    1807             :                         return -1;
    1808             :         }
    1809      369846 :         if (rel_is_ref(r)) {
    1810        3186 :                 list_append(refs, r);
    1811        3186 :                 list_append(refs, l);
    1812             :         }
    1813             :         return 0;
    1814             : }
    1815             : 
    1816             : list *
    1817      109919 : rel_dependencies(mvc *sql, sql_rel *r)
    1818             : {
    1819      109919 :         list *refs = sa_list(sql->sa);
    1820      109919 :         list *l = sa_list(sql->sa);
    1821             : 
    1822      109919 :         if (rel_deps(sql, r, refs, l) != 0)
    1823           0 :                 return NULL;
    1824             :         return l;
    1825             : }
    1826             : 
    1827             : static list *exps_exp_visitor(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown);
    1828             : 
    1829             : static inline list *
    1830       50249 : exps_exps_exp_visitor(visitor *v, sql_rel *rel, list *lists, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown)
    1831             : {
    1832             :         node *n;
    1833             : 
    1834       50249 :         if (list_empty(lists))
    1835             :                 return lists;
    1836      110155 :         for (n = lists->h; n; n = n->next) {
    1837       59906 :                 if (n->data && (n->data = exps_exp_visitor(v, rel, n->data, depth, exp_rewriter, topdown, relations_topdown)) == NULL)
    1838             :                         return NULL;
    1839             :         }
    1840             :         return lists;
    1841             : }
    1842             : 
    1843             : static sql_rel *rel_exp_visitor(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown);
    1844             : 
    1845             : static sql_exp *
    1846   135507618 : exp_visitor(visitor *v, sql_rel *rel, sql_exp *e, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown, bool *changed)
    1847             : {
    1848   135507618 :         if (mvc_highwater(v->sql))
    1849           0 :                 return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    1850             : 
    1851   135507980 :         assert(e);
    1852   135507980 :         if (topdown) {
    1853         772 :                 int changes = v->changes;
    1854         772 :                 if (!(e = exp_rewriter(v, rel, e, depth)))
    1855             :                         return NULL;
    1856         772 :                 *changed |= v->changes > changes;
    1857             :         }
    1858             : 
    1859   135507980 :         switch(e->type) {
    1860             :         case e_column:
    1861             :                 break;
    1862     3416205 :         case e_convert:
    1863     3416205 :                 if  ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1864             :                         return NULL;
    1865             :                 break;
    1866     6446152 :         case e_aggr:
    1867             :         case e_func:
    1868     6446152 :                 if (e->r) /* rewrite rank -r is list of lists */
    1869       50249 :                         if ((e->r = exps_exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1870             :                                 return NULL;
    1871     6446152 :                 if (e->l)
    1872     6318951 :                         if ((e->l = exps_exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1873             :                                 return NULL;
    1874             :                 break;
    1875     8148508 :         case e_cmp:
    1876     8148508 :                 if (e->flag == cmp_or || e->flag == cmp_filter) {
    1877      265634 :                         if ((e->l = exps_exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1878             :                                 return NULL;
    1879      265634 :                         if ((e->r = exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1880             :                                 return NULL;
    1881     7882874 :                 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
    1882      561910 :                         if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1883             :                                 return NULL;
    1884      561910 :                         if ((e->r = exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1885             :                                 return NULL;
    1886             :                 } else {
    1887     7320964 :                         if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1888             :                                 return NULL;
    1889     7320964 :                         if ((e->r = exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1890             :                                 return NULL;
    1891     7320964 :                         if (e->f && (e->f = exp_visitor(v, rel, e->f, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1892             :                                 return NULL;
    1893             :                 }
    1894             :                 break;
    1895      341813 :         case e_psm:
    1896      341813 :                 if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
    1897      104177 :                         if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1898             :                                 return NULL;
    1899      237636 :                 } else if (e->flag & PSM_VAR) {
    1900             :                         return e;
    1901      211591 :                 } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
    1902       29822 :                         if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, changed)) == NULL)
    1903             :                                 return NULL;
    1904       29822 :                         if ((e->r = exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1905             :                                 return NULL;
    1906       29822 :                         if (e->flag == PSM_IF && e->f && (e->f = exps_exp_visitor(v, rel, e->f, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1907             :                                 return NULL;
    1908      181769 :                 } else if (e->flag & PSM_REL) {
    1909      181769 :                         if ((e->l = rel_exp_visitor(v, e->l, exp_rewriter, topdown, relations_topdown)) == NULL)
    1910             :                                 return NULL;
    1911             :                 }
    1912             :                 break;
    1913    23798492 :         case e_atom:
    1914    23798492 :                 if (e->f)
    1915      140907 :                         if ((e->f = exps_exp_visitor(v, rel, e->f, depth+1, exp_rewriter, topdown, relations_topdown)) == NULL)
    1916             :                                 return NULL;
    1917             :                 break;
    1918             :         }
    1919   135481931 :         if (!topdown) {
    1920   135480784 :                 int changes = v->changes;
    1921   135480784 :                 if (!(e = exp_rewriter(v, rel, e, depth)))
    1922             :                         return NULL;
    1923   135480820 :                 *changed |= v->changes > changes;
    1924             :         }
    1925             :         return e;
    1926             : }
    1927             : 
    1928             : static list *
    1929    33394383 : exps_exp_visitor(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown)
    1930             : {
    1931    33394383 :         bool changed = false;
    1932    33394383 :         if (list_empty(exps))
    1933             :                 return exps;
    1934   150152761 :         for (node *n = exps->h; n; n = n->next)
    1935   116767488 :                 if (n->data && (n->data = exp_visitor(v, rel, n->data, depth, exp_rewriter, topdown, relations_topdown, &changed)) == NULL)
    1936             :                         return NULL;
    1937    33385273 :         if (changed && depth == 0) /* only level 0 exps use hash, so remove only on those */
    1938       35733 :                 list_hash_clear(exps);
    1939             :         return exps;
    1940             : }
    1941             : 
    1942             : static inline sql_rel *
    1943    26292594 : rel_exp_visitor(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown)
    1944             : {
    1945    26292594 :         if (mvc_highwater(v->sql))
    1946           0 :                 return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    1947             : 
    1948    26292595 :         if (!rel)
    1949             :                 return rel;
    1950             : 
    1951    26292576 :         if (relations_topdown) {
    1952     7152937 :                 if (rel->exps && (rel->exps = exps_exp_visitor(v, rel, rel->exps, 0, exp_rewriter, topdown, relations_topdown)) == NULL)
    1953             :                         return NULL;
    1954     7152932 :                 if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r && (rel->r = exps_exp_visitor(v, rel, rel->r, 0, exp_rewriter, topdown, relations_topdown)) == NULL)
    1955             :                         return NULL;
    1956             :         }
    1957             : 
    1958    26292571 :         switch(rel->op){
    1959             :         case op_basetable:
    1960             :                 break;
    1961      108399 :         case op_table:
    1962      108399 :                 if (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION) {
    1963      108302 :                         if (rel->l)
    1964        5626 :                                 if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
    1965             :                                         return NULL;
    1966             :                 }
    1967             :                 break;
    1968     1805130 :         case op_ddl:
    1969     1805130 :                 if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
    1970      179874 :                         if (rel->l)
    1971      177851 :                                 if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
    1972             :                                         return NULL;
    1973     1625256 :                 } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
    1974        3867 :                         if (rel->l)
    1975        3813 :                                 if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
    1976             :                                         return NULL;
    1977        3867 :                         if (rel->r)
    1978        3600 :                                 if ((rel->r = rel_exp_visitor(v, rel->r, exp_rewriter, topdown, relations_topdown)) == NULL)
    1979             :                                         return NULL;
    1980             :                 }
    1981             :                 break;
    1982     5763681 :         case op_insert:
    1983             :         case op_update:
    1984             :         case op_delete:
    1985             :         case op_merge:
    1986             : 
    1987             :         case op_join:
    1988             :         case op_left:
    1989             :         case op_right:
    1990             :         case op_full:
    1991             :         case op_semi:
    1992             :         case op_anti:
    1993             : 
    1994             :         case op_union:
    1995             :         case op_inter:
    1996             :         case op_except:
    1997     5763681 :                 if (rel->l)
    1998     5763681 :                         if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
    1999             :                                 return NULL;
    2000     5763681 :                 if (rel->r)
    2001     5761846 :                         if ((rel->r = rel_exp_visitor(v, rel->r, exp_rewriter, topdown, relations_topdown)) == NULL)
    2002             :                                 return NULL;
    2003             :                 break;
    2004    12099501 :         case op_select:
    2005             :         case op_topn:
    2006             :         case op_sample:
    2007             :         case op_project:
    2008             :         case op_groupby:
    2009             :         case op_truncate:
    2010    12099501 :                 if (rel->l)
    2011    11386747 :                         if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
    2012             :                                 return NULL;
    2013             :                 break;
    2014             :         }
    2015             : 
    2016    26292557 :         if (!relations_topdown) {
    2017    19139626 :                 if (rel->exps && (rel->exps = exps_exp_visitor(v, rel, rel->exps, 0, exp_rewriter, topdown, relations_topdown)) == NULL)
    2018             :                         return NULL;
    2019    19139624 :                 if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r && (rel->r = exps_exp_visitor(v, rel, rel->r, 0, exp_rewriter, topdown, relations_topdown)) == NULL)
    2020           0 :                         return NULL;
    2021             :         }
    2022             : 
    2023             :         return rel;
    2024             : }
    2025             : 
    2026             : sql_rel *
    2027           0 : rel_exp_visitor_topdown(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
    2028             : {
    2029           0 :         return rel_exp_visitor(v, rel, exp_rewriter, true, relations_topdown);
    2030             : }
    2031             : 
    2032             : sql_rel *
    2033     3007665 : rel_exp_visitor_bottomup(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
    2034             : {
    2035     3007665 :         return rel_exp_visitor(v, rel, exp_rewriter, false, relations_topdown);
    2036             : }
    2037             : 
    2038             : static list *exps_rel_visitor(visitor *v, list *exps, rel_rewrite_fptr rel_rewriter, bool topdown);
    2039             : 
    2040             : static sql_exp *
    2041   441381283 : exp_rel_visitor(visitor *v, sql_exp *e, rel_rewrite_fptr rel_rewriter, bool topdown)
    2042             : {
    2043   441381283 :         if (mvc_highwater(v->sql))
    2044           0 :                 return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    2045             : 
    2046   441382011 :         assert(e);
    2047   441382011 :         switch(e->type) {
    2048             :         case e_column:
    2049             :                 break;
    2050    13067694 :         case e_convert:
    2051    13067694 :                 if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2052           0 :                         return NULL;
    2053             :                 break;
    2054    22577122 :         case e_aggr:
    2055             :         case e_func:
    2056    22577122 :                 if (e->r) /* rewrite rank */
    2057       85052 :                         if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
    2058             :                                 return NULL;
    2059    22577122 :                 if (e->l)
    2060    21660127 :                         if ((e->l = exps_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2061           0 :                                 return NULL;
    2062             :                 break;
    2063    30389877 :         case e_cmp:
    2064    30389877 :                 if (e->flag == cmp_or || e->flag == cmp_filter) {
    2065      979585 :                         if ((e->l = exps_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2066             :                                 return NULL;
    2067      979585 :                         if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
    2068           0 :                                 return NULL;
    2069    29410292 :                 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
    2070     2139740 :                         if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2071             :                                 return NULL;
    2072     2139740 :                         if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
    2073           0 :                                 return NULL;
    2074             :                 } else {
    2075    27270552 :                         if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2076             :                                 return NULL;
    2077    27270551 :                         if ((e->r = exp_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
    2078             :                                 return NULL;
    2079    27270550 :                         if (e->f && (e->f = exp_rel_visitor(v, e->f, rel_rewriter, topdown)) == NULL)
    2080           0 :                                 return NULL;
    2081             :                 }
    2082             :                 break;
    2083     1676674 :         case e_psm:
    2084     1676674 :                 if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
    2085      540435 :                         if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2086           0 :                                 return NULL;
    2087     1136239 :                 } else if (e->flag & PSM_VAR) {
    2088             :                         return e;
    2089      988601 :                 } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
    2090      143010 :                         if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
    2091             :                                 return NULL;
    2092      143010 :                         if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
    2093             :                                 return NULL;
    2094      143010 :                         if (e->flag == PSM_IF && e->f && (e->f = exps_rel_visitor(v, e->f, rel_rewriter, topdown)) == NULL)
    2095           0 :                                 return NULL;
    2096      845591 :                 } else if (e->flag & PSM_REL) {
    2097      845591 :                         sql_rel *(*func)(visitor *, sql_rel *, rel_rewrite_fptr) = topdown ? rel_visitor_topdown : rel_visitor_bottomup;
    2098      845591 :                         if ((e->l = func(v, e->l, rel_rewriter)) == NULL)
    2099           2 :                                 return NULL;
    2100             :                 }
    2101             :                 break;
    2102    64928937 :         case e_atom:
    2103    64928937 :                 if (e->f)
    2104      339868 :                         if ((e->f = exps_rel_visitor(v, e->f, rel_rewriter, topdown)) == NULL)
    2105           0 :                                 return NULL;
    2106             :                 break;
    2107             :         }
    2108             :         return e;
    2109             : }
    2110             : 
    2111             : static list *
    2112   116365153 : exps_rel_visitor(visitor *v, list *exps, rel_rewrite_fptr rel_rewriter, bool topdown)
    2113             : {
    2114   116365153 :         if (list_empty(exps))
    2115             :                 return exps;
    2116   487227374 :         for (node *n = exps->h; n; n = n->next)
    2117   370926451 :                 if (n->data && (n->data = exp_rel_visitor(v, n->data, rel_rewriter, topdown)) == NULL)
    2118             :                         return NULL;
    2119             :         return exps;
    2120             : }
    2121             : 
    2122             : static inline sql_rel *
    2123    89634068 : do_rel_visitor(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter, bool topdown)
    2124             : {
    2125    89634068 :         if (rel->exps && (rel->exps = exps_rel_visitor(v, rel->exps, rel_rewriter, topdown)) == NULL)
    2126             :                 return NULL;
    2127    89633984 :         if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r && (rel->r = exps_rel_visitor(v, rel->r, rel_rewriter, topdown)) == NULL)
    2128             :                 return NULL;
    2129    89633984 :         int changes = v->changes;
    2130    89633984 :         rel = rel_rewriter(v, rel);
    2131    89634027 :         if (rel && rel->exps && v->changes > changes) {
    2132      300480 :                 list_hash_clear(rel->exps);
    2133      300480 :                 if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r)
    2134       13421 :                         list_hash_clear(rel->r);
    2135             :         }
    2136             :         return rel;
    2137             : }
    2138             : 
    2139             : static inline sql_rel *
    2140    89634128 : rel_visitor(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter, bool topdown)
    2141             : {
    2142    89634128 :         sql_rel *parent = v->parent;
    2143             : 
    2144    89634128 :         if (mvc_highwater(v->sql))
    2145           0 :                 return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    2146             : 
    2147    89634189 :         if (!rel)
    2148             :                 return NULL;
    2149             : 
    2150    89634159 :         if (topdown && !(rel = do_rel_visitor(v, rel, rel_rewriter, true)))
    2151             :                 return NULL;
    2152             : 
    2153    89634158 :         sql_rel *(*func)(visitor *, sql_rel *, rel_rewrite_fptr) = topdown ? rel_visitor_topdown : rel_visitor_bottomup;
    2154             : 
    2155    89634158 :         v->parent = rel;
    2156    89634158 :         switch(rel->op){
    2157             :         case op_basetable:
    2158             :                 break;
    2159      270958 :         case op_table:
    2160      270958 :                 if (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION) {
    2161      270617 :                         if (rel->l)
    2162       22965 :                                 if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
    2163             :                                         return NULL;
    2164             :                 }
    2165             :                 break;
    2166     3568672 :         case op_ddl:
    2167     3568672 :                 if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
    2168      382644 :                         if (rel->l)
    2169      378597 :                                 if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
    2170             :                                         return NULL;
    2171     3186028 :                 } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
    2172       14644 :                         if (rel->l)
    2173       14484 :                                 if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
    2174             :                                         return NULL;
    2175       14644 :                         if (rel->r)
    2176       13778 :                                 if ((rel->r = func(v, rel->r, rel_rewriter)) == NULL)
    2177             :                                         return NULL;
    2178     3171384 :                 } else if (rel->flag == ddl_psm) {
    2179      243652 :                         if ((rel->exps = exps_rel_visitor(v, rel->exps, rel_rewriter, topdown)) == NULL)
    2180             :                                 return NULL;
    2181             :                 }
    2182             :                 break;
    2183    21318399 :         case op_insert:
    2184             :         case op_update:
    2185             :         case op_delete:
    2186             :         case op_merge:
    2187             : 
    2188             :         case op_join:
    2189             :         case op_left:
    2190             :         case op_right:
    2191             :         case op_full:
    2192             :         case op_semi:
    2193             :         case op_anti:
    2194             : 
    2195             :         case op_union:
    2196             :         case op_inter:
    2197             :         case op_except:
    2198    21318399 :                 if (rel->l)
    2199    21318397 :                         if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
    2200             :                                 return NULL;
    2201    21318397 :                 if (rel->r)
    2202    21309714 :                         if ((rel->r = func(v, rel->r, rel_rewriter)) == NULL)
    2203             :                                 return NULL;
    2204             :                 break;
    2205    41099672 :         case op_select:
    2206             :         case op_topn:
    2207             :         case op_sample:
    2208             :         case op_project:
    2209             :         case op_groupby:
    2210             :         case op_truncate:
    2211    41099672 :                 if (rel->l)
    2212    39330731 :                         if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
    2213             :                                 return NULL;
    2214             :                 break;
    2215             :         }
    2216    89634145 :         v->parent = parent;
    2217             : 
    2218    89634145 :         if (!topdown)
    2219    66334327 :                 rel = do_rel_visitor(v, rel, rel_rewriter, false);
    2220             :         return rel;
    2221             : }
    2222             : 
    2223             : sql_rel *
    2224    23299794 : rel_visitor_topdown(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
    2225             : {
    2226    23299794 :         v->depth++;
    2227    23299794 :         rel = rel_visitor(v, rel, rel_rewriter, true);
    2228    23299814 :         v->depth--;
    2229    23299814 :         return rel;
    2230             : }
    2231             : 
    2232             : sql_rel *
    2233    66334364 : rel_visitor_bottomup(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
    2234             : {
    2235    66334364 :         v->depth++;
    2236    66334364 :         rel = rel_visitor(v, rel, rel_rewriter, false);
    2237    66334343 :         v->depth--;
    2238    66334343 :         return rel;
    2239             : }
    2240             : 
    2241             : list *
    2242         275 : exps_exp_visitor_topdown(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
    2243             : {
    2244         275 :         return exps_exp_visitor(v, rel, exps, depth, exp_rewriter, true, relations_topdown);
    2245             : }
    2246             : 
    2247             : list *
    2248           0 : exps_exp_visitor_bottomup(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
    2249             : {
    2250           0 :         return exps_exp_visitor(v, rel, exps, depth, exp_rewriter, false, relations_topdown);
    2251             : }
    2252             : 
    2253             : static bool
    2254      108953 : exps_rebind_exp(mvc *sql, sql_rel *rel, list *exps)
    2255             : {
    2256             :         bool ok = true;
    2257             : 
    2258             :         if (mvc_highwater(sql)) {
    2259           0 :                 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    2260           0 :                 return false;
    2261             :         }
    2262             : 
    2263      108953 :         if (list_empty(exps))
    2264             :                 return true;
    2265       96292 :         for (node *n = exps->h; n && ok; n = n->next)
    2266       60306 :                 ok &= rel_rebind_exp(sql, rel, n->data);
    2267             :         return ok;
    2268             : }
    2269             : 
    2270             : bool
    2271     7083964 : rel_rebind_exp(mvc *sql, sql_rel *rel, sql_exp *e)
    2272             : {
    2273             :         if (mvc_highwater(sql)) {
    2274           0 :                 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
    2275           0 :                 return false;
    2276             :         }
    2277             : 
    2278     7155001 :         switch (e->type) {
    2279       71037 :         case e_convert:
    2280       71037 :                 return rel_rebind_exp(sql, rel, e->l);
    2281       17233 :         case e_aggr:
    2282             :         case e_func:
    2283       17233 :                 return exps_rebind_exp(sql, rel, e->l);
    2284     3048143 :         case e_cmp:
    2285     3048143 :                 if (e->flag == cmp_in || e->flag == cmp_notin)
    2286        8591 :                         return rel_rebind_exp(sql, rel, e->l) && exps_rebind_exp(sql, rel, e->r);
    2287     3039552 :                 if (e->flag == cmp_or || e->flag == cmp_filter)
    2288        9088 :                         return exps_rebind_exp(sql, rel, e->l) && exps_rebind_exp(sql, rel, e->r);
    2289     3031033 :                 return rel_rebind_exp(sql, rel, e->l) && rel_rebind_exp(sql, rel, e->r) && (!e->f || rel_rebind_exp(sql, rel, e->f));
    2290     3945613 :         case e_column:
    2291     3945613 :                 return rel_find_exp(rel, e) != NULL;
    2292       72974 :         case e_atom:
    2293       72974 :                 return exps_rebind_exp(sql, rel, e->f);
    2294             :         case e_psm:
    2295             :                 return true;
    2296             :         }
    2297             :         return true;
    2298             : }
    2299             : 
    2300             : static sql_exp *
    2301         386 : _exp_freevar_offset(visitor *v, sql_rel *rel, sql_exp *e, int depth)
    2302             : {
    2303             :         (void)rel; (void)depth;
    2304             :         /* visitor will handle recursion, ie only need to check columns here */
    2305         386 :         int vf = is_freevar(e);
    2306         386 :         if (v->changes < vf)
    2307         293 :                 v->changes=vf;
    2308         386 :         return e;
    2309             : }
    2310             : 
    2311             : int
    2312         282 : exp_freevar_offset(mvc *sql, sql_exp *e)
    2313             : {
    2314         282 :         bool changed = false;
    2315         282 :         visitor v = { .sql = sql };
    2316             : 
    2317             :         (void) changed;
    2318         282 :         exp_visitor(&v, NULL, e, 0, &_exp_freevar_offset, true, true, &changed);
    2319             :         /* freevar offset is passed via changes */
    2320         282 :         return (v.changes);
    2321             : }

Generated by: LCOV version 1.14