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                         break;
 368                 case ST_ARROW:
 369                         do_arrow(t, where);
 370                         break;
 371                 default:
 372                         die("compile: got to default, type: %d", t->st);
 373         }
 374 }
 375
 376 static char *
 377 lookup_var_name(int id)
 378 {
 379         int h;
 380
 381         for (h=0; h<HASHSIZE; h++) {
 382                 struct variable *p;
 383                 LIST_FOREACH(p, var_hash + h)
 384                         if (p->varcode == id)
 385                                 return p->name;
 386         }
 387         return "";
 388 }
 389
 390 void
 391 print_code(void)
 392 {
 393         struct code* p;
 394         int i;
 395
 396         printf("Known constants:\n");
 397         for (i=1; i<cur_const_n; i++)
 398                 printf("-%d\t\"%s\"\n", i, const_tab[i]);
 399         printf("\n");
 400
 401         printf("Known variables:\n");
 402         // This is grossly inefficient...
 403         for (i=0; i<temp_varcode_start; i++)
 404                 printf("%d\t%s\n", i, lookup_var_name(i));
 405         printf("\n");
 406
 407         LIST_FOREACH(p, &input_code) {
 408                 printf("%p: ", p);
 409                 switch (p->opcode) {
 410                         case OPC_SET:
 411                                 printf("SET %d %d\n", p->u.set.l, p->u.set.r);
 412                                 break;
 413                         case OPC_CAT:
 414                                 printf("CAT %d %d %d\n", p->u.tpop.l,
 415                                 p->u.tpop.r, p->u.tpop.res);
 416                                 break;
 417                         case OPC_JUMP:
 418                                 printf("JUMP %p\n", p->u.jump.target);
 419                                 break;
 420                         case OPC_JUMP_UNLESS:
 421                                 printf("JUMP_UNLESS %d %p\n", p->u.jump_unless.cond, p->u.jump_unless.target);
 422                                 break;
 423                         case OPC_GT:
 424                                 printf("GT %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 425                                 break;
 426                         case OPC_LT:
 427                                 printf("LT %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 428                                 break;
 429                         case OPC_LE:
 430                                 printf("LE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 431                                 break;
 432                         case OPC_GE:
 433                                 printf("GE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 434                                 break;
 435                         case OPC_RE:
 436                                 printf("RE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 437                                 break;
 438                         case OPC_NRE:
 439                                 printf("NRE %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 440                                 break;
 441                         case OPC_NEQ:
 442                                 printf("NEQ %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 443                                 break;
 444                         case OPC_EQ:
 445                                 printf("EQ %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 446                                 break;
 447                         case OPC_AND:
 448                                 printf("AND %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 449                                 break;
 450                         case OPC_OR:
 451                                 printf("OR %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 452                                 break;
 453                         case OPC_XOR:
 454                                 printf("XOR %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 455                                 break;
 456                         case OPC_PLUS:
 457                                 printf("PLUS %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 458                                 break;
 459                         case OPC_MINUS:
 460                                 printf("MINUS %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 461                                 break;
 462                         case OPC_MUL:
 463                                 printf("MUL %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 464                                 break;
 465                         case OPC_DIV:
 466                                 printf("DIV %d %d %d\n", p->u.tpop.l, p->u.tpop.r, p->u.tpop.res);
 467                                 break;
 468                         case OPC_NOT:
 469                                 printf("NOT %d %d\n", p->u.dpop.par, p->u.dpop.res);
 470                                 break;
 471                         case OPC_NOP:
 472                                 printf("NOP\n");
 473                                 break;
 474                         case OPC_PIPE:
 475                                 printf("PIPE %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 476                                 break;
 477                         case OPC_FILTER:
 478                                 printf("FILTER %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 479                                 break;
 480                         case OPC_DELIVER:
 481                                 printf("DELIVER %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 482                                 break;
 483                         case OPC_MAIL:
 484                                 printf("MAIL %d %d\n", p->u.arrow.what, p->u.arrow.copy);
 485                                 break;
 486                         case OPC_DISCARD:
 487                                 puts("DISCARD");
 488                                 break;
 489                         default:
 490                                 printf("not implemented, opcode: %d\n",
 491                                 p->opcode);
 492                 }
 493         }
 494 }