code.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <ctype.h>
   5
   6 #include "umpf.h"
   7
   8 struct list*
   9 new_var_hash(void)
  10 {
  11         struct list* res;
  12         int i;
  13
  14         res = xmalloc (HASHSIZE * sizeof(struct list));
  15         for (i = 0; i < HASHSIZE; i++)
  16                 list_init(res + i);
  17
  18         return res;
  19 }
  20
  21 int
  22 get_bucket_number(char* name)
  23 {
  24         unsigned int n = 0;
  25         unsigned char* p = name;
  26
  27         while (*p != '\0'){
  28                 n = n * MAGIC + toupper(*p++);
  29         }
  30         n %= HASHSIZE;
  31
  32         return n;
  33 }
  34
  35 /* return var struct or NULL if not found */
  36 struct variable*
  37 get_var_struct(char* name, enum var_type type, struct list* hash)
  38 {
  39         int n;
  40         struct variable *p;
  41
  42         n = get_bucket_number(name);
  43         LIST_FOREACH(p, hash + n)
  44                 if (!strcasecmp(p->name, name) && p->type == type)
  45                         return p;
  46
  47         return NULL;
  48 }
  49
  50 int
  51 find_var(char* name, enum var_type type, struct list* hash)
  52 {
  53         int n;
  54         struct variable *p;
  55
  56         n = get_bucket_number(name);
  57         LIST_FOREACH(p, hash + n)
  58                 if (!strcasecmp(p->name, name) && p->type == type)
  59                         return p->varcode;
  60
  61         p = xmalloc(sizeof(struct variable));
  62         p->name = xstrdup(name);
  63         p->varcode = current_varcode++;
  64         p->type = type;
  65         list_add_last(hash+n, &p->car);
  66
  67         return p->varcode;
  68 }
  69
  70 int
  71 store_const(char* c)
  72 {
  73         if (cur_const_n >= cur_const_s) {
  74                 cur_const_s *= 2;
  75                 const_tab = xrealloc(const_tab, cur_const_s);
  76         }
  77
  78         const_tab[cur_const_n] = c;
  79
  80         return -cur_const_n++;
  81 }
  82
  83 static void
  84 new_instr(struct code c, struct list* where)
  85 {
  86         struct code* p = xmalloc(sizeof(struct code));
  87         *p = c;
  88         if (where)
  89                 list_add_last(where, &p->car);
  90         else
  91                 list_add_last(&input_code, &p->car);
  92 }
  93
  94 static int
  95 new_3par_instr(int opcode, int left, int right, int pref_var,
  96                  struct list* where)
  97 {
  98         struct code ins;
  99
 100         ins.opcode = opcode;
 101         ins.u.tpop.l = left;
 102         ins.u.tpop.r = right;
 103         if (pref_var >= 0)
 104                 ins.u.tpop.res = pref_var;
 105         else
 106                 ins.u.tpop.res = current_varcode++;;
 107         new_instr(ins, where);
 108         return ins.u.tpop.res;
 109 }
 110
 111 /* return number of variable where lies result
 112  * pref_var < 0 => no preference
 113  */
 114 static int
 115 evaluate(struct tree* t, int pref_var, struct list* where)
 116 {
 117         if (t->st == ST_LEAF) {
 118                 return t->pt.leaf.n;
 119         }
 120         int left, right;
 121         left = evaluate(t->pt.op.left, -1, where);
 122         right = evaluate(t->pt.op.right, -1, where);
 123         switch (t->pt.op.op) {
 124                 case '.':
 125                         return new_3par_instr(OPC_CAT, left,
 126                                 right, pref_var, where);
 127                         break;
 128                 case '+':
 129                         return new_3par_instr(OPC_PLUS, left,
 130                                 right, pref_var, where);
 131                         break;
 132                 case '-':
 133                         return new_3par_instr(OPC_MINUS, left,
 134                                 right, pref_var, where);
 135                         break;
 136                 case '*':
 137                         return new_3par_instr(OPC_MUL, left,
 138                                 right, pref_var, where);
 139                         break;
 140                 case '/':
 141                         return new_3par_instr(OPC_DIV, left,
 142                                 right, pref_var, where);
 143                         break;
 144         }
 145         die("evaluate: Never can get here :)");
 146 }
 147
 148 static void
 149 do_ass(struct tree* t, struct list* where)
 150 {
 151         int var_l, var_r;
 152         struct code ins;
 153         var_l = t->pt.ass.left->pt.leaf.n;
 154         var_r = evaluate(t->pt.ass.right, -1, where);
 155
 156         ins.opcode = OPC_SET;
 157         ins.u.set.l = var_l;
 158         ins.u.set.r = var_r;
 159         new_instr(ins, where);
 160
 161 }
 162
 163 static int
 164 eval_cond(struct tree *t, int pref_var, struct list* where)
 165 {
 166         int left, right;
 167         if (t->pt.cond.type == JUST_BOOL) {
 168                 if (t->pt.cond.left->st == ST_LEAF)
 169                         return t->pt.cond.left->pt.leaf.n;
 170                 if (t->pt.cond.left->st == ST_OP)
 171                         return evaluate(t->pt.cond.left, -1, where);
 172                 else
 173                         die("eval_cond: %d cannot be JUST_BOOL\n",
 174                         t->pt.cond.left->st);
 175         }
 176         if (t->pt.cond.type == OP_REL) {
 177                 left = evaluate(t->pt.cond.left, -1, where);
 178                 right = evaluate(t->pt.cond.right, -1, where);
 179
 180                 switch (t->pt.cond.op) {
 181                         case '>':
 182                                 return new_3par_instr (OPC_GT, left,
 183                                         right, pref_var, where);
 184                                 break;
 185                         case '<':
 186                                 return new_3par_instr (OPC_LT, left,
 187                                         right, pref_var, where);
 188                                 break;
 189                         case CC('<','='):
 190                                 return new_3par_instr (OPC_LE, left,
 191                                         right, pref_var, where);
 192                                 break;
 193                         case CC('>','='):
 194                                 return new_3par_instr (OPC_GE, left,
 195                                         right, pref_var, where);
 196                                 break;
 197                         case CC('!','~'):
 198                                 return new_3par_instr (OPC_NRE, left,
 199                                         right, pref_var, where);
 200                                 break;
 201                         case CC('~','~'):
 202                                 return new_3par_instr (OPC_RE, left,
 203                                         right, pref_var, where);
 204                                 break;
 205                         case CC('=','='):
 206                                 return new_3par_instr (OPC_EQ, left,
 207                                         right, pref_var, where);
 208                                 break;
 209                         case CC('!','='):
 210                                 return new_3par_instr (OPC_NEQ, left,
 211                                         right, pref_var, where);
 212                                 break;
 213                         /* fixme: do more of them */
 214                         default:
 215                                 die("eval_cond: unknown relation op %c\n",
 216                                 t->pt.cond.op);
 217
 218                 }
 219         }
 220         if (t->pt.cond.type == OP_BOOL) {
 221                 struct code ins;
 222
 223                 left = eval_cond(t->pt.cond.left, -1, where);
 224                 if (t->pt.cond.op != '!') /* ! is unary */
 225                         right = eval_cond(t->pt.cond.right, -1, where);
 226                 switch (t->pt.cond.op) {
 227                         case '&':
 228                                 return new_3par_instr (OPC_AND, left,
 229                                         right, pref_var, where);
 230                                 break;
 231                         case '|':
 232                                 return new_3par_instr (OPC_OR, left,
 233                                         right, pref_var, where);
 234                                 break;
 235                         case '^':
 236                                 return new_3par_instr (OPC_XOR, left,
 237                                         right, pref_var, where);
 238                                 break;
 239                         case '!':
 240                                 ins.opcode = OPC_NOT;
 241                                 ins.u.dpop.par = left;
 242                                 if (pref_var >= 0)
 243                                         ins.u.dpop.res = pref_var;
 244                                 else
 245                                         ins.u.dpop.res = current_varcode++;;
 246                                 new_instr(ins, where);
 247                                 return ins.u.dpop.res;
 248                                 break;
 249                         default:
 250                                 die("eval_cond: unknown boolean op %c\n",
 251                                 t->pt.cond.op);
 252                 }
 253         }
 254
 255         die("eval_cond: unknown condition type");
 256 }
 257
 258 static void
 259 do_if(struct tree *t, struct list* where)
 260 {
 261         int c;
 262         struct code ins, nop, jmp;
 263         struct list* if_branch = xmalloc(sizeof(struct list));
 264         struct list* else_branch = xmalloc(sizeof(struct list));
 265
 266         list_init(if_branch);
 267         list_init(else_branch);
 268         nop.opcode  = OPC_NOP;
 269         jmp.opcode = OPC_JUMP;
 270
 271         c = eval_cond(t->pt.tif.c, -1, where);
 272
 273         compile(t->pt.tif.i, if_branch);
 274         compile(t->pt.tif.e, else_branch);
 275         new_instr(nop, else_branch);
 276         jmp.u.jump.target = list_last(else_branch);
 277         new_instr(jmp, if_branch);
 278         new_instr(nop, if_branch);
 279
 280         ins.opcode = OPC_JUMP_UNLESS;
 281         ins.u.jump_unless.cond = c;
 282         ins.u.jump_unless.target = list_last(if_branch);
 283         new_instr(ins, where);
 284         list_cat(where, if_branch);
 285         list_cat(where, else_branch);
 286
 287         free(if_branch);
 288         free(else_branch);
 289 }
 290
 291 static void
 292 do_arrow(struct tree* t, struct list* where)
 293 {
 294         int v;
 295         struct code ins;
 296
 297
 298         if (t->pt.arrow.left == K_COPY)
 299                 ins.u.arrow.copy = 1;
 300         else
 301                 ins.u.arrow.copy = 0;
 302         switch (t->pt.arrow.right) {
 303                 case K_EMPTY:
 304                         ins.opcode = OPC_DELIVER;
 305                         break;
 306                 case K_PIPE:
 307                         ins.opcode = OPC_PIPE;
 308                         break;
 309                 case K_MAIL:
 310                         ins.opcode = OPC_MAIL;
 311                         break;
 312                 case K_DISCARD:
 313                         ins.opcode = OPC_DISCARD;
 314                         break;
 315                 case K_FILTER:
 316                         ins.opcode = OPC_FILTER;
 317                         break;
 318                 default:
 319                         die("do_arrow: This cannot happen ;-)");
 320         }
 321
 322         if (t->pt.arrow.right != K_DISCARD) {
 323                 v = evaluate(t->pt.arrow.s, -1, where);
 324                 ins.u.arrow.what = v;
 325         }
 326
 327         new_instr(ins, where);
 328 }
 329
 330 static void
 331 reset_temp_var_count(void)
 332 {
 333         if (current_varcode > max_varcode)
 334                 max_varcode = current_varcode;
 335         current_varcode = temp_varcode_start;
 336 }
 337
 338 void
 339 compile(struct tree* t, struct list* where)
 340 {
 341         if (!t)
 342                 return;
 343         if (! where)
 344                 where = &input_code;
 345
 346         switch(t->st) {
 347                 case ST_BLOCK:
 348                         reset_temp_var_count();
 349                         compile(t->pt.block.head, where);
 350                         compile(t->pt.block.tail, where);
 351                         break;
 352                 case ST_EMPTY:
 353                         break;
 354                 case ST_LEAF: //warn?
 355                         break;
 356                 case ST_ASS:
 357                         do_ass(t, where);
 358                         break;
 359                 case ST_OP:
 360                         evaluate(t, -1, where); //emit warning?
 361                         break;
 362                 case ST_IF:
 363                         do_if(t, where);
 364                         break;
 365                 case ST_COND:
 366                         eval_cond(t, -1, where); // warn?
 367                 case ST_ARROW:
 368                         do_arrow(t, where);
 369                         break;
 370                 default:
 371                         die("compile: got to default, type: %d", t->st);
 372         }
 373 }
 374
 375 static char *
 376 lookup_var_name(int id)
 377 {
 378         int h;
 379
 380         for (h=0; h<HASHSIZE; h++) {
 381                 struct variable *p;
 382                 LIST_FOREACH(p, var_hash + h)
 383                         if (p->varcode == id)
 384                                 return p->name;
 385         }
 386         return "";
 387 }
 388
 389 void
 390 print_code(void)
 391 {
 392         struct code* p;
 393         int i;
 394
 395         printf("Known constants:\n");
 396         for (i=1; i<cur_const_n; i++)
 397                 printf("-%d\t\"%s\"\n", i, const_tab[i]);
 398         printf("\n");
 399
 400         printf("Known variables:\n");
 401         // This is grossly inefficient...
 402         for (i=0; i<temp_varcode_start; i++)
 403                 printf("%d\t%s\n", i, lookup_var_name(i));
 404         printf("\n");
 405
 406         LIST_FOREACH(p, &input_code) {
 407                 printf("%p: ", p);
 408                 switch (p->opcode) {
 409                         case OPC_SET:
 410                                 printf("SET %d %d\n", p->u.set.l, p->u.set.r);
 411                                 break;
 412                         case OPC_CAT:
 413                                 printf("CAT %d %d %d\n", p->u.tpop.l,
 414                                 p->u.tpop.r, p->u.tpop.res);
 415                                 break;
 416                         case OPC_JUMP:
 417                                 printf("JUMP %p\n", p->u.jump.target);
 418                                 break;
 419                         case OPC_JUMP_UNLESS:
 420                                 printf("JUMP_UNLESS %d %p\n", p->u.jump_unless.cond, p->u.jump_unless.target);
 421                                 break;
 422                         case OPC_GT:
 423                                 printf("GT %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 424                                 break;
 425                         case OPC_LT:
 426                                 printf("LT %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 427                                 break;
 428                         case OPC_LE:
 429                                 printf("LE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 430                                 break;
 431                         case OPC_GE:
 432                                 printf("GE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 433                                 break;
 434                         case OPC_RE:
 435                                 printf("RE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 436                                 break;
 437                         case OPC_NRE:
 438                                 printf("NRE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 439                                 break;
 440                         case OPC_NEQ:
 441                                 printf("NEQ %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 442                                 break;
 443                         case OPC_EQ:
 444                                 printf("EQ %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 445                                 break;
 446                         case OPC_AND:
 447                                 printf("AND %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 448                                 break;
 449                         case OPC_OR:
 450                                 printf("OR %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 451                                 break;
 452                         case OPC_XOR:
 453                                 printf("XOR %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 454                                 break;
 455                         case OPC_PLUS:
 456                                 printf("PLUS %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 457                                 break;
 458                         case OPC_MINUS:
 459                                 printf("MINUS %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 460                                 break;
 461                         case OPC_MUL:
 462                                 printf("MUL %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 463                                 break;
 464                         case OPC_DIV:
 465                                 printf("DIV %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 466                                 break;
 467                         case OPC_NOT:
 468                                 printf("NOT %d %d\n", p->u.dpop.par, p->u.dpop.res);
 469                                 break;
 470                         case OPC_NOP:
 471                                 printf("NOP\n");
 472                                 break;
 473                         case OPC_PIPE:
 474                                 printf("PIPE %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 475                                 break;
 476                         case OPC_FILTER:
 477                                 printf("FILTER %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 478                                 break;
 479                         case OPC_DELIVER:
 480                                 printf("DELIVER %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 481                                 break;
 482                         case OPC_MAIL:
 483                                 printf("MAIL %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 484                                 break;
 485                         case OPC_DISCARD:
 486                                 puts("DISCARD");
 487                                 break;
 488                         default:
 489                                 printf("not implemented, opcode: %d\n",
 490                                 p->opcode);
 491                 }
 492         }
 493 }