#! /usr/bin/env python3 from __future__ import print_function import random import re import string import os from optparse import OptionParser # # to make Python2 and Python3 act the same -- how dumb # def random_seed(seed): try: random.seed(seed, version=1) except: random.seed(seed) return def random_randint(low, hi): return int(low + random.random() * (hi - low + 1)) def random_choice(L): return L[random_randint(0, len(L)-1)] # # boilerplate code for .c files used by both readable/runnable code versions # class Boilerplate: def __init__(self, fd): self.fd = fd return def init(self): self.fd.write('#include \n') self.fd.write('#include \n') self.fd.write('#include \n') self.fd.write('#include \n') self.fd.write('#include \n') self.fd.write('#include \n') self.fd.write('#include \n') self.fd.write('\n') self.fd.write('void wait_or_die() {\n') self.fd.write(' int rc = wait(NULL);\n') self.fd.write(' assert(rc > 0);\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('int fork_or_die() {\n') self.fd.write(' int rc = fork();\n') self.fd.write(' assert(rc >= 0);\n') self.fd.write(' return rc;\n') self.fd.write('}\n') self.fd.write('\n') return def init_runnable(self): self.init() self.fd.write('#define Time_GetSeconds() ({ struct timeval t; int rc = gettimeofday(&t, NULL); assert(rc == 0); (double) t.tv_sec + (double) t.tv_usec/1e6; })\n') self.fd.write('\n') self.fd.write('double t_start;\n') self.fd.write('\n') self.fd.write('struct pid_map {\n') self.fd.write(' int pid;\n') self.fd.write(' char name[10];\n') self.fd.write(' struct pid_map *next;\n') self.fd.write('};\n') self.fd.write('\n') self.fd.write('struct pid_map *head = NULL;\n') self.fd.write('\n') self.fd.write('void Space(char c) {\n') self.fd.write(' int i;\n') self.fd.write(' for (i = 0; i < 5 * (c - \'a\'); i++) {\n') self.fd.write(' printf(\" \"); \n') self.fd.write(' }\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('char *Lookup(int pid) {\n') self.fd.write(' struct pid_map *curr = head;\n') self.fd.write(' while (curr) {\n') self.fd.write(' if (curr->pid == pid) \n') self.fd.write(' return(curr->name);\n') self.fd.write(' curr = curr->next;\n') self.fd.write(' }\n') self.fd.write(' return NULL;\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('void Record(int pid, char *m) {\n') self.fd.write(' struct pid_map *n = malloc(sizeof(struct pid_map));\n') self.fd.write(' assert(n);\n') self.fd.write(' n->pid = pid;\n') self.fd.write(' strcpy(n->name, m);\n') self.fd.write(' n->next = head;\n') self.fd.write(' head = n;\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('void Wait(char *m) {\n') self.fd.write(' int rc = wait(NULL);\n') self.fd.write(' assert(rc > 0);\n') self.fd.write(' double t = Time_GetSeconds() - t_start;\n') self.fd.write(' printf(\"%3d \", (int)t);\n') self.fd.write(' Space(m[0]);\n') self.fd.write(' char *n = Lookup(rc);\n') self.fd.write(' assert(n != NULL);\n') self.fd.write(' printf(\"%s<-%s\\n\", m, n);\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('void Sleep(int s, char *m) {\n') self.fd.write(' sleep(s);\n') self.fd.write(' double t = Time_GetSeconds() - t_start;\n') self.fd.write(' printf(\"%3d %s\\n\", (int)t, m);\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('void Fork(char *p, char *c) {\n') self.fd.write(' double t = Time_GetSeconds() - t_start;\n') self.fd.write(' printf(\"%3d \", (int)t);\n') self.fd.write(' Space(p[0]);\n') self.fd.write(' printf(\"%s->%s\\n\", p, c);\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('void __Begin(char *m) {\n') self.fd.write(' double t = Time_GetSeconds() - t_start;\n') self.fd.write(' printf(\"%3d \", (int)t);\n') self.fd.write(' Space(m[0]);\n') self.fd.write(' printf(\"%s+\\n\", m);\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('void __End(char *m) {\n') self.fd.write(' double t = Time_GetSeconds() - t_start;\n') self.fd.write(' printf(\"%3d \", (int)t);\n') self.fd.write(' Space(m[0]);\n') self.fd.write(' printf(\"%s-\\n\", m);\n') self.fd.write('}\n') self.fd.write('\n') self.fd.write('#define Begin(m) { __Begin(m); }\n') self.fd.write('#define End(m) { __End(m); exit(0); }\n') self.fd.write('\n') return def fini(self): self.fd.write(' return 0;\n') self.fd.write('}\n\n') return def main(self): self.fd.write('int main(int argc, char *argv[]) {\n') return def main_runnable(self): self.main() self.fd.write(' int rc;\n') self.fd.write(' t_start = Time_GetSeconds();\n') return def __fini__(self): close(self.fd) return class CodeGeneratorReadable: def __init__(self, out_file_base, actions): self.out_file = out_file_base + '.c' self.actions = actions self.tab_level = 1 self.fd = open(self.out_file, 'w') self.boiler = Boilerplate(self.fd) return def __fini__(self): self.fd.close() return def tab(self): for i in range(self.tab_level): self.fd.write(' ') return def add_thread(self, thread_id): self.tab() self.fd.write('// process %s\n' % thread_id) return def add_fork(self): self.tab() self.fd.write('if (fork_or_die() == 0) {\n') self.tab_level += 1 return def add_sleep(self, sleep_time): self.tab() self.fd.write('sleep(%s);\n' % sleep_time) return def add_exit(self): self.tab() self.fd.write('exit(0);\n') self.tab_level -= 1 self.tab() self.fd.write('}\n') return def add_wait(self): self.tab() self.fd.write('wait_or_die();\n') return def generate(self): self.boiler.init() self.boiler.main() self.add_thread('a') for a in actions: tmp = a.split(' ') if tmp[0] == 'fork': # fork thread_id sleep_time assert(len(tmp) == 3) self.add_fork() self.add_sleep(tmp[2]) self.add_thread(tmp[1]) elif tmp[0] == 'exit': assert(len(tmp) == 1) self.add_exit() elif tmp[0] == 'wait': assert(len(tmp) == 1) self.add_wait() else: print('bad command') exit(1) return self.boiler.fini() self.__fini__() return class CodeGeneratorRunnable: def __init__(self, out_file_base, actions): self.out_file = out_file_base + '.c' self.actions = actions self.tab_level = 1 self.fd = open(self.out_file, 'w') self.boiler = Boilerplate(self.fd) self.parent_list = [] self.waiting_for = {} self.used_times = {} return def __fini__(self): self.fd.close() return def tab(self): for i in range(self.tab_level): self.fd.write(' ') return def add_thread(self, thread_id): self.tab() self.waiting_for[thread_id] = [] self.fd.write('Begin(\"%s\");\n' % thread_id) self.curr_thread = thread_id return def add_fork(self, child_thread, sleep_time): self.parent_list.append(self.curr_thread) self.waiting_for[self.curr_thread].append(child_thread) # print('add fork for %s' % self.curr_thread, self.waiting_for[self.curr_thread]) self.tab() self.fd.write('Fork(\"%s\", \"%s\");\n' % (self.curr_thread, child_thread)) self.tab() self.fd.write('if ((rc = fork_or_die()) == 0) {\n') self.tab_level += 1 return def add_sleep(self, sleep_time): self.tab() self.fd.write('sleep(%s);\n' % sleep_time) return def add_exit(self): # MUST HAVE DONE ALL WAITS(!) if len(self.waiting_for[self.curr_thread]) > 0: print('error: thread cannot exit without performing all needed waits') print(' thread %s has outstanding children:' % self.curr_thread, self.waiting_for[self.curr_thread]) exit(1) self.tab() self.fd.write('End(\"%s\");\n' % self.curr_thread) self.tab_level -= 1 self.tab() self.fd.write('}\n') self.tab() self.fd.write('Record(rc, \"%s\");\n' % self.curr_thread) self.curr_thread = self.parent_list.pop() return def add_wait(self): self.tab() # how to know who to wait for? waiting_for = self.waiting_for[self.curr_thread].pop(0) # print('%s waited for %s' % (self.curr_thread, waiting_for[1])) self.fd.write('Wait(\"%s\");\n' % self.curr_thread); return def generate(self): self.boiler.init_runnable() self.boiler.main_runnable() self.add_thread('a') for a in actions: tmp = a.split(' ') if tmp[0] == 'fork': # fork thread_id sleep_time assert(len(tmp) == 3) self.add_fork(tmp[1], tmp[2]) self.add_sleep(tmp[2]) self.add_thread(tmp[1]) elif tmp[0] == 'exit': assert(len(tmp) == 1) self.add_exit() elif tmp[0] == 'wait': assert(len(tmp) == 1) self.add_wait() else: print('bad command') exit(1) return self.boiler.fini() self.__fini__() return # # Generates input for C code generators # class ProgramGenerator: def __init__(self, num_actions, max_sleep_time): self.num_actions = num_actions self.max_sleep_time = max_sleep_time self.names = string.ascii_lowercase + string.ascii_uppercase self.name_index = 1 self.used_times = {} self.used_times[0] = True return def get_next_name(self): if self.name_index == len(self.names): print('program generator: out of names (too many processes)') exit(1) n = self.names[self.name_index] self.name_index += 1 return n def get_sleep_time(self): return random_randint(1, self.max_sleep_time) def add_fork_begin(self): name = self.get_next_name() sleep_time = self.get_sleep_time() self.actions.append('fork %s %d' % (name, sleep_time)) self.need_wait[self.fork_level] += 1 self.fork_level += 1 self.need_wait[self.fork_level] = 0 return def add_fork_end(self): self.actions.append('exit') self.fork_level -= 1 return def add_wait(self): self.actions.append('wait') self.need_wait[self.fork_level] -= 1 return def clean_up(self): n = self.need_wait[self.fork_level] for i in range(n): self.actions.append('wait') if self.fork_level > 0: self.actions.append('exit') return n + 1 def generate(self, fork_chance, wait_chance, exit_chance): self.actions = [] self.fork_level = 0 self.need_wait = {} self.need_wait[self.fork_level] = 0 total_chance = fork_chance + wait_chance + exit_chance if total_chance != 100: print('fork/wait/exit chance must sum to 100, but sums to', total_chance) exit(1) self.fork_chance = float(fork_chance) / 100.0 self.wait_chance = float(fork_chance + wait_chance) / 100.0 # the rest is 'exit_chance' n = 0 while n < self.num_actions: r = random.random() if r < self.fork_chance: # print('fork') self.add_fork_begin() n += 1 elif r < self.wait_chance: # print('wait?') if self.need_wait[self.fork_level] > 0: # print('wait') self.add_wait() n += 1 else: # print('exit') if self.fork_level > 0: # must do all needed waits now # self.add_fork_end() n += self.clean_up() self.fork_level -= 1 # diagnostics # print('level', self.fork_level, 'actions', self.actions, 'nw', self.need_wait[self.fork_level]) # clean up: while self.fork_level >= 0: self.clean_up() self.fork_level -= 1 return self.actions # # Parses user input into program understood by C code generators # class Parser: def __init__(self, program): self.program = program self.orig_program = program def abort_if(self, condition, message): if condition: print('bad program: [%s]' % self.orig_program) print(message) exit(1) return def parse(self): # remove spaces around commas program = self.program p = re.compile('\s*,\s*') m = p.search(program) while m: program = program.replace(m.group(), ',', 1) m = p.search(program, m.end()) # add spaces around braces program = program.replace('{', ' { ') program = program.replace('}', ' } ') # now go through and find the commands # easy to parse by just splitting on spaces tokens = program.split() action_list = [] # add actions understood by generators here curr = 0 # where we are in list of tokens brace_count = 0 # ensures matching number of braces wait_count = {} # tracks, per fork-nesting level, that enough waits are added fork_level = 0 # tracks level of forks wait_count[fork_level] = 0 while curr < len(tokens): if tokens[curr] == '': curr += 1 continue elif tokens[curr] == 'fork': wait_count[fork_level] += 1 fork_level += 1 wait_count[fork_level] = 0 self.abort_if(len(tokens) < curr + 2, 'malformed program: fork needs process name,sleep length plus {description} of what the forked process should do') args = tokens[curr + 1] args_split = args.split(',') self.abort_if(len(args_split) != 2, 'not enough args to fork (process name, sleep time)') lbrace = tokens[curr + 2] self.abort_if(lbrace != '{', 'must have {} following fork') action_list.append('fork %s %s' % (args_split[0], args_split[1])) # skip over the argument and the left brace curr += 2 brace_count += 1 elif tokens[curr] == '}': self.abort_if(fork_level == 0, 'extra close brace') action_list.append("exit") self.abort_if(wait_count[fork_level] != 0, '#waits does not match #forks') brace_count -= 1 fork_level -= 1 elif tokens[curr] == 'wait': wait_count[fork_level] -= 1 action_list.append("wait") else: self.abort_if(True, 'unrecognized token %s' % tokens[curr]) # loop until all done with tokens curr += 1 # some final checks self.abort_if(wait_count[0] != 0, '#waits does not match #forks') self.abort_if(brace_count != 0, 'unbalanced braces') return action_list # # MAIN PROGRAM # parser = OptionParser() parser.add_option('-s', '--seed', default=-1, help='random seed', action='store', type='int', dest='seed') parser.add_option('-r', '--readable', default='read', help='file to read (e.g., "read", to produce read.c)', action='store', type='string', dest='readable') parser.add_option('-R', '--runnable', default='run', help='file to run (e.g., "run", to produce run.c)', action='store', type='string', dest='runnable') parser.add_option('-n', '--num_actions', default=10, help='num actions', action='store', type='int', dest='num_actions') parser.add_option('-f', '--fork_chance', default=30, help='chances that a program will fork', action='store', type='int', dest='fork_chance') parser.add_option('-w', '--wait_chance', default=40, help='chances that a program will wait', action='store', type='int', dest='wait_chance') parser.add_option('-e', '--exit_chance', default=30, help='chances that a program will exit', action='store', type='int', dest='exit_chance') parser.add_option('-S', '--sleep_time', default=10, help='max sleep time for a process', action='store', type='int', dest='max_sleep_time') parser.add_option('-A', '--action_list', default='none', help='action list, instead of randomly generated ones (simple example: "fork b,10 {} wait" is a program that runs a process (called a) which then forks process b which runs for 10 seconds, and then a waits for b to complete; see README for details', action='store', type='string', dest='action_list') parser.add_option('-c', '--compute', help='compute answers for me', action='store_true', default=False, dest='solve') (options, args) = parser.parse_args() if options.seed != -1: random_seed(options.seed) if options.max_sleep_time < 1: print('max sleep time must be >= 1') exit(1) if options.fork_chance < 1 or options.fork_chance > 99: print('fork chance must be between 1 and 99') exit(1) if options.wait_chance < 1 or options.wait_chance > 99: print('wait chance must be between 1 and 99') exit(1) if options.exit_chance < 1 or options.exit_chance > 99: print('exit chance must be between 1 and 99') exit(1) if options.action_list == 'none': pg = ProgramGenerator(options.num_actions, options.max_sleep_time) actions = pg.generate(options.fork_chance, options.wait_chance, options.exit_chance) else: action_list = options.action_list p = Parser(action_list) actions = p.parse() # print(actions) cg_read = CodeGeneratorReadable(options.readable, actions) cg_read.generate() cg_run = CodeGeneratorRunnable(options.runnable, actions) cg_run.generate() # now either list the code, or run it if options.solve: os.system('gcc -o %s %s.c -Wall' % (options.runnable, options.runnable)) os.system('./%s' % options.runnable) else: # print('cat %s.c' % options.readable) stream = os.popen('cat %s.c' % options.readable) output = stream.read() print(output) # rc = os.system('cat %s.c' % options.readable) # print(rc)