/*  DFL interpreter skeleton
    (c) 1996, Howard E. Motteler

USAGE: 

   dfl program [datafile]

DISCUSSION:

This program implements a DFL dataflow interpreter.  The
interpreter has two main sections: the first section reads
a DFL program and creates a record for each DFL statement.
For the statement "c = a + b", this record would have two
input buffers, for "a" and "b", and a pointer to an output
buffer for "c".  After the records are created, another
pass is made, in which pointers for variables on the LHS of
each statement are set to point to buffers corresponding to
the same variables on the RHS.  (Thus the restriction that
a variable can appear at most once on the RHS of a program.)
Special statement records are initialized to contain the 
variables "in", "out" and "halt".

The method used here to build the dataflow graph is not very
efficient--it is O(L^2), where L is the number of lines--but
has the virtue of simplicity; it would have saved quite a
bit of space to have used an array of token buffers, seperate
from the statement records.

The parser as it now exists is a grungy hack; in retrospect
it would have been far simpler to use "lex" or similar tools
to read and parse the DFL program file.

The second section of the interpreter executes the dataflow
graph created in the first section; here statement records
(or nodes) that are ready are executed, until either (1) no
statements are ready, or (2) an explicit "halt" is issued.
Ready statements can be executed concurrently by a set of
threads; however unless care is taken the scheduler can be a
bottleneck.

PROGRAM INPUT/OUTPUT:

If the variable "in" is referenced on the RHS of a statement,
the interpreter reads a sequence of one or more integers from
stdin, or from the specified file.  If the variable "out" is
assigned to (on the LHS of a statement), all values copied to
the buffer are printed to stdout.

LIMITATIONS:

  - NUMSTMT is max number of program statements
  - VBUFSIZE is max values per input buffer
  - SLEN is maximum variabld or constant length 
  - some assorted buffers have hard-coded sizes

WARNING:

This program has been tried out on a few relatively simple
DFL programs, but it has not been extensively tested, and
almost certainly contains as yet undiscovered bugs.

*/

#include <stdio.h>
#include <ulocks.h>
#include <task.h>


/*  dataflow input buffers
 *  ----------------------
 */
#define VBUFSIZE 20

struct vbuf {
   int buf[VBUFSIZE];
   int  out, count; 
   };

void write_vbuf(struct vbuf *p, int v) {

   if (p->count == VBUFSIZE) {
      fprintf(stderr, "write_vbuf: buffer full\n");
      exit(1);
      }
   (p->buf)[ (p->out + p->count) % VBUFSIZE ] = v;
   p->count = p->count + 1;
   }

int read_vbuf(struct vbuf *p) {
   int v;
   if (p->count == 0) {
      fprintf(stderr, "read_vbuf: buffer empty\n");
      exit(1);
      }
   v = (p->buf)[ p->out ] ;
   p->out = (p->out + 1) % VBUFSIZE ;
   p->count = p->count - 1 ;
   return v;
   }

int full_vbuf(struct vbuf *p) { return p->count == VBUFSIZE; }

int empty_vbuf(struct vbuf *p) { return p->count == 0; }

void init_vbuf(struct vbuf *p) { p->out=0; p->count=0; }

void print_vbuf(struct vbuf *p) { 
   int i;
   for (i=p->out; i != p->count; i = (i+1) % VBUFSIZE)
      printf("%d ", p->buf[i]);
   printf("\n");
   }


/*  statement record definitions
 *  ----------------------------
 */
#define NUMSTMT 100	     /* max number of statements */
#define SLEN    24	     /* longest constant or variable name */
#define NOSYM  "(no symbol)"

/* statment state */
#define READY  'R'
#define WAIT   'W'

/* opcodes  */
#define NO_OP    'N'
#define IN_OP    'I'
#define OUT_OP   'O'
#define HALT_OP  'H'
#define ASST_OP  'A'

struct {
   char state;
   char opcode;
   char in1sym[SLEN], in2sym[SLEN];
   struct vbuf in1, in2;
   char out1sym[SLEN], out2sym[SLEN];
   struct vbuf *out1, *out2;
   } stmt_rec[NUMSTMT];

void print_stmt_rec(int i) {

   printf("---- statement record %d ----\n", i+1);
   printf("state  = %c\n", stmt_rec[i].state);
   printf("opcode = %c\n", stmt_rec[i].opcode);
   printf("in1sym = %s  in2sym = %s\n", 
	  stmt_rec[i].in1sym, stmt_rec[i].in2sym);
   if (!empty_vbuf(&stmt_rec[i].in1)) {
      printf("input buffer 1: ");
      print_vbuf(&stmt_rec[i].in1);
      }
   if (!empty_vbuf(&stmt_rec[i].in2)) {
      printf("input buffer 2: ");
      print_vbuf(&stmt_rec[i].in2);
      }
   printf("out1sym = %s  out2sym = %s\n", 
	  stmt_rec[i].out1sym, stmt_rec[i].out2sym);
   if (stmt_rec[i].out1 !=  0)
      printf("output buffer 1 at %x\n", stmt_rec[i].out1);
   if (stmt_rec[i].out2 !=  0)
      printf("output buffer 2 at %x\n", stmt_rec[i].out2);
   }

void init_stmt_rec(int i) {
      stmt_rec[i].state     = WAIT;
      stmt_rec[i].opcode    = NO_OP;
      strncpy(stmt_rec[i].in1sym, NOSYM, SLEN);
      strncpy(stmt_rec[i].in1sym, NOSYM, SLEN);
      strncpy(stmt_rec[i].in2sym, NOSYM, SLEN);
      strncpy(stmt_rec[i].in2sym, NOSYM, SLEN);
      strncpy(stmt_rec[i].out1sym, NOSYM, SLEN);
      strncpy(stmt_rec[i].out2sym, NOSYM, SLEN);
      init_vbuf(&stmt_rec[i].in1);
      init_vbuf(&stmt_rec[i].in2);
      stmt_rec[i].out1 = 0;
      stmt_rec[i].out2 = 0;
      }


/*  MAIN
 * -----
 */
main (int argc, char *argv[]) {

   int i, j, k, c;
   char *p, *q;

   FILE *pchan;			/* program channel 	     	*/
   FILE *inchan;		/* data channel			*/
   static char linebuf[100];	/* program line buffer 	     	*/
   static char databuf[100];	/* int string input buffer	*/
   char *word[10];		/* statement word pointers   	*/
   int wordcnt = 0; 		/* total words on a line     	*/
   int stmtcnt = 0;		/* statement counter		*/
   int ready = 0;		/* flag that some stmt is ready */
   int in_eof = 0;		/* flag we've hit EOF on data   */

   int in_stmt=0, out_stmt, halt_stmt;
   struct vbuf in_buf, out_buf, halt_buf;

   init_vbuf(&in_buf);
   init_vbuf(&out_buf);
   init_vbuf(&halt_buf);

   /*  open the program file
    */
   if ((pchan=fopen(argv[1], "r")) == NULL) {
      printf("dfl: can't open program file %s\n", argv[1]);
      exit(1);
      }

   /*  open the data file, if requested
    *  default is to read from stdin
    */
   inchan = stdin; 
   if (argc==3 && (inchan=fopen(argv[2], "r")) == NULL) {
      printf("dfl: can't open data file %s\n", argv[2]);
      exit(1);
      }

   /*   Parse DFL lines and set up statement records
    *   --------------------------------------------
    */  
   for (;; stmtcnt++) {

      /*  read a line into linebuf 
       */
      for (p=linebuf; (c=getc(pchan)) != '\n' && c != EOF; *p++ = c);  
      if (c == EOF) break;
      *p = 0;

      /*  split buf into an array of words 
       */
      p = linebuf;
      k = 0;
      do {
	 while (*p && isspace(*p)) p++;
	 q = p;
	 while (*q && !isspace(*q)) q++;
	 if (q != p) word[k++] = p;
	 if (*q != 0) *q++ = 0;
	 p = q;
	 }  while (*p);

      wordcnt = k;

      /*  do some basic syntax checks
       */      
      if (!(wordcnt == 3 || wordcnt == 5) || (*word[1] != '=') ) {
	 printf("dfl: illegal statement: %s\n", linebuf);
	 exit(1);
	 }

      /*  set up the statement record
       */
      init_stmt_rec(stmtcnt);

      if (wordcnt == 3) {

	 /* <var> = <var> 
	  */	
	 stmt_rec[stmtcnt].opcode  = ASST_OP;
	 strncpy(stmt_rec[stmtcnt].in1sym, word[2], SLEN);
	 if (isdigit(*word[2])) 
	    write_vbuf(&stmt_rec[stmtcnt].in1, atoi(word[2]));
	 strncpy(stmt_rec[stmtcnt].out1sym, word[0], SLEN);
	 }
      else if (*word[3] != '=') {

	 /* <var> = <var> <op> <var> 
	  */
	 stmt_rec[stmtcnt].opcode  = *word[3];
	 strncpy(stmt_rec[stmtcnt].in1sym, word[2], SLEN);
	 if (isdigit(*word[2])) 
	    write_vbuf(&stmt_rec[stmtcnt].in1, atoi(word[2]));
	 strncpy(stmt_rec[stmtcnt].in2sym, word[4], SLEN);
	 if (isdigit(*word[4])) 
	    write_vbuf(&stmt_rec[stmtcnt].in2, atoi(word[4]));
	 strncpy(stmt_rec[stmtcnt].out1sym, word[0], SLEN);
	 }
      else {

	 /* <var> = <var> = <var> 
	  */
	 stmt_rec[stmtcnt].opcode  = *word[3];
	 strncpy(stmt_rec[stmtcnt].in1sym, word[4], SLEN);
	 if (isdigit(*word[4]))
	    write_vbuf(&stmt_rec[stmtcnt].in1, atoi(word[4]));
	 strncpy(stmt_rec[stmtcnt].out1sym, word[2], SLEN);
	 strncpy(stmt_rec[stmtcnt].out2sym, word[0], SLEN);
	 }

      /*  set flag if "in" variable was referenced
       */
      if (strcmp(word[2], "in") == 0
	  || (wordcnt == 5 && strcmp(word[4], "in") == 0))
	  in_stmt = 1; 

      } /* end of stament read loop */


   /*  build statment records for "in", "out", and "halt" 
    */
   if (in_stmt) {
      init_stmt_rec(stmtcnt);
      stmt_rec[stmtcnt].opcode  = IN_OP;
      strncpy(stmt_rec[stmtcnt].out1sym, "in", SLEN);
      in_stmt = stmtcnt++;
      }

   init_stmt_rec(stmtcnt);
   stmt_rec[stmtcnt].opcode  = OUT_OP;
   strncpy(stmt_rec[stmtcnt].in1sym, "out", SLEN);
   out_stmt = stmtcnt++;

   init_stmt_rec(stmtcnt);
   stmt_rec[stmtcnt].opcode  = HALT_OP;
   strncpy(stmt_rec[stmtcnt].in1sym, "halt", SLEN);
   halt_stmt = stmtcnt++;


   /*  for each statement's output assignment, search 
    *  for an input buffer with the same name
    */
   for (i=0; i<stmtcnt; i++) {

      if (strcmp(stmt_rec[i].out1sym, NOSYM) != 0)

	 for (j=0; j<stmtcnt; j++) {

	    if (strcmp(stmt_rec[i].out1sym, stmt_rec[j].in1sym) == 0)
	       stmt_rec[i].out1 = &(stmt_rec[j].in1);

	    if (strcmp(stmt_rec[i].out1sym, stmt_rec[j].in2sym) == 0)
	       stmt_rec[i].out1 = &(stmt_rec[j].in2);
	    }

      if (strcmp(stmt_rec[i].out2sym, NOSYM) != 0)

	 for (j=0; j<stmtcnt; j++) {

	    if (strcmp(stmt_rec[i].out2sym, stmt_rec[j].in1sym) == 0)
	       stmt_rec[i].out2 = &(stmt_rec[j].in1);

	    if (strcmp(stmt_rec[i].out2sym, stmt_rec[j].in2sym) == 0)
	       stmt_rec[i].out2 = &(stmt_rec[j].in2);
	    }
      }


   /*  partial validity check--make sure each statement's output
    *  assignment has a matching input buffer somewhere
    */
   for (i=0; i<stmtcnt; i++) {
     
      if (strcmp(stmt_rec[i].out1sym, NOSYM) != 0
	  && stmt_rec[i].out1 == (struct vbuf *) 0) {
	 printf("dfl: unmatched output symbol \"%s\", line %d\n", 
		stmt_rec[i].out1sym, i+1);	    
	 /* print_stmt_rec(i); */
	 exit(1);
	 }

      if (strcmp(stmt_rec[i].out2sym, NOSYM) != 0
	   && stmt_rec[i].out1 == (struct vbuf *) 0) {
	 printf("dfl: unmatched output symbol \"%s\", line %d\n", 
		stmt_rec[i].out2sym, i+1);	    
	 /* print_stmt_rec(i); */
	 exit(1);
	 }
      }

   
   /*   TEMPORARY -- dump statement records and quit
    */
   for (i=0; i<stmtcnt; i++) print_stmt_rec(i);
   exit(0);


   /*  Statement execution loop
    *  ------------------------
    */
   for (;;) {

      /*   check for input 
       */	
      while (in_stmt && !in_eof && !full_vbuf(stmt_rec[in_stmt].out1)) {

	 /*  read next int from stdin
	  */
	 c=getc(inchan); 
	 if (c != EOF) {
	    while (isspace(c) && c != EOF) c = getc(inchan);
	    p = databuf;
	    while (!isspace(c) && c != EOF) { *p++ = c; c = getc(inchan); }
	    *p = 0;
	    if (c != EOF)
	       write_vbuf(stmt_rec[in_stmt].out1, atoi(databuf));
	    }
	 in_eof = c == EOF;
	 }


      /*  execute ready statements
       *  -------------------------
       *
       * You have to fill in this part; a statement is ready
       * if its input buffer(s) are non-empty and its output
       * buffer(s) are not full.  You may want to add a test
       * to terminate if no statements are ready.
       *
       */


      /*  output
       */
      while (!empty_vbuf(&stmt_rec[out_stmt].in1)) {
	 printf ("dfl: output = %d\n", 
		 read_vbuf(&stmt_rec[out_stmt].in1));
	 }

      /*  check for halt
       */
      if (!empty_vbuf(&stmt_rec[halt_stmt].in1)) {
	 printf ("dfl: received halt; terminating\n");
	 exit(0);
	 }

      } /* end of statement execution loop */
	    
   } /* end of main */