#!/usr/bin/python

"""This module is part of Swampy, a suite of programs available from

allendowney.com/swampy.

Copyright 2011 Allen B. Downey

Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.

"""

import optparse

import os

import copy

import random

import sys

import string

import time

# the following definitions can be accessed in the simulator

current_thread = None

def noop(*args):

"""A handy function taht does nothing."""

def balk():

"""Jumps to the top of the column."""

current_thread.balk()

class Semaphore:

"""Represents a semaphore in the simulator.

Maintains a random queue.

"""

def __init__(self, n=0):

self.n = n

self.queue = []

def __str__(self): return str(self.n)

def wait(self):

self.n -= 1

if self.n < 0:

self.block()

return self.n

def block(self):

thread = current_thread

thread.enqueue()

self.queue.append(thread)

def signal(self, n=1):

for i in range(n):

self.n += 1

if self.queue:

self.unblock()

def unblock(self):

"""Chooses a random thread and unblocks it."""

thread = random.choice(self.queue)

self.queue.remove(thread)

thread.dequeue()

thread.next_loop()

class FifoSemaphore(Semaphore):

"""Semaphore that implements a FIFO queue."""

def unblock(self):

"""Chooses the first thread and unblocks it."""

thread = self.queue.pop(0)

thread.dequeue()

thread.next_loop()

class Lightswitch:

"""Encapsulates the lightswitch pattern."""

def __init__(self):

self.counter = 0

self.mutex = Semaphore(1)

def lock(self, semaphore):

self.mutex.wait()

self.counter += 1

if self.counter == 1:

semaphore.wait()

self.mutex.signal()

def unlock(self, semaphore):

self.mutex.wait()

self.counter -= 1

if self.counter == 0:

semaphore.signal()

self.mutex.signal()

def pid():

"""Gets the ID of the current thread."""

return current_thread.name

def num_threads():

"""Gets the number of threads."""

sync = current_thread.column.p

return len(sync.threads)

# make globals and locals for the simulator

sim_globals = copy.copy(globals())

sim_locals = dict()

# anything defined after this point is not available inside the simulator

from Tkinter import N, S, E, W, TOP, BOTTOM, LEFT, RIGHT, END

from Gui import Gui, GuiCanvas

# get the version of Python

v = sys.version.split()[0].split('.')

major = int(v[0])

if major == 2:

all_thread_names = string.uppercase + string.lowercase

else:

all_thread_names = string.ascii_uppercase + string.ascii_lowercase

font = ("Courier", 12)

FSU = 9 # FSU, the fundamental Sync unit,

# determines the size of most things.

class Sync(Gui):

"""Represents the thread simulator."""

def __init__(self, args=['']):

Gui.__init__(self)

self.parse_args(args)

self.namer = Namer()

self.locals = sim_locals

self.globals = sim_globals

self.views = {}

self.w = self

self.threads = []

self.running = False

self.delay = 0.2

self.setup()

self.run_init()

for col in self.cols:

col.create_thread()

def parse_args(self, args):

parser = optparse.OptionParser()

parser.add_option('-w', '--write', dest='write',

action='store_true', default=False,

help='Write thread code in code subdirectory?')

parser.add_option('-s', '--side', dest='initside',

action='store_true', default=False,

help='Move the initialization code to the left side?')

(self.options, args) = parser.parse_args(args)

if args:

self.filename = args[0]

else:

self.filename = ''

def get_name(self, name=None):

return self.namer.next(name)

def get_threads(self):

return self.threads

def set_global(self, **kwds):

self.globals.update(kwds)

def get_global(self, attr):

return self.globals[attr]

def destroy(self):

"""Closes the top window."""

self.running = False

Gui.destroy(self)

def setup(self):

"""Makes the GUI."""

if self.filename:

self.read_file(self.filename)

self.make_columns()

if self.options.write:

self.write_files(self.filename)

return

self.topcol = Column(self, n=5)

self.colfr = self.fr()

self.cols = [Column(self, LEFT, n=5) for i in range(2)]

self.bu(side=RIGHT, text='Add\ncolumn', command=self.add_col)

self.endfr()

self.buttons()

def buttons(self):

"""Makes the buttons."""

self.row([1,1,1,1,1])

self.bu(text='Run', command=self.run)

self.bu(text='Random Run', command=self.random_run)

self.bu(text='Stop', command=self.stop)

self.bu(text='Step', command=self.step)

self.bu(text='Random Step', command=self.random_step)

self.endfr()

def register(self, thread):

"""Adds a new thread."""

self.threads.append(thread)

def unregister(self, thread):

"""Removes a thread."""

self.threads.remove(thread)

def run(self):

"""Runs the simulator with round-robin scheduling."""

self.run_helper(self.step)

def random_run(self):

"""Runs the simulator with random scheduling."""

self.run_helper(self.random_step)

def run_helper(self, step=None):

"""Runs the threads until someone clears self.running."""

self.running = True

while self.running:

step()

self.update()

time.sleep(self.delay)

def step(self):

"""Advances all the threads in order"""

for thread in self.threads:

thread.step_loop()

def random_step(self):

"""Advances one random thread."""

threads = [thread for thread in self.threads if not thread.queued]

if not threads:

print 'There are currently no threads that can run.'

return

thread = random.choice(threads)

thread.step_loop()

def stop(self):

"""Stops running."""

self.running = False

def read_file(self, filename):

"""Read a file that contains code for the simulator to execute.

Lines that start with ## do not appear

in the display.

A line that starts with "## thread" indicates the beginning of

a new column of code.

Returns a list of blocks where each block is a list of lines.

"""

def is_new_thread(line):

if line[0:2] != '##':

return False

words = line.strip('#').split()

word = words[0].lower()

return word == 'thread'

self.blocks = []

block = []

self.blocks.append(block)

fp = open(filename)

for line in fp:

line = line.rstrip()

if is_new_thread(line):

block = []

self.blocks.append(block)

else:

block.append(line)

fp.close()

def make_columns(self):

"""Adds the code in self.blocks to the GUI."""

if not self.blocks:

return

side = LEFT if self.options.initside else TOP

self.topcol = TopColumn(self, side=side)

self.topcol.add_rows(self.blocks[0])

self.colfr = self.fr()

self.cols = []

self.endfr()

for block in self.blocks[1:]:

col = self.add_col(0)

col.add_rows(block)

self.buttons()

def write_files(self, filename, dirname='book_code'):

"""Writes the code into separate files for the init and threads.

filename: name of the file we read

dirname: name of the destination subdirectory

Destination is a subdirectory of the directory the filename is in.

"""

path, filename = os.path.split(filename)

dest = os.path.join(path, dirname, filename)

block = self.blocks[0]

self.write_file(block, dest, 0)

for i, block in enumerate(self.blocks[1:]):

self.write_file(block, dest, i+1)

def write_file(self, block, filename, suffix=0):

trim_block(block)

name = '%s.%s' % (filename, str(suffix))

fp = open(name, 'w')

for line in block:

fp.write(line + '\n')

fp.close()

def add_col(self, n=5):

"""Adds a new column of code to the display."""

self.pushfr(self.colfr)

col = Column(self, LEFT, n)

self.cols.append(col)

self.popfr()

return col

def run_init(self):

"""Runs the initialization code in the top column."""

if not self.topcol.num_rows():

return

print 'running init'

self.clear_views()

self.views = {}

thread = Thread(self.topcol, name='0')

while True:

thread.step()

if thread.row == None: break

self.unregister(thread)

def update_views(self):

"""Loops through the views and updates them."""

for key, view in self.views.iteritems():

view.update(self.locals[key])

def clear_views(self):

"""Loops through the views and clears them."""

for key, view in self.views.iteritems():

view.clear()

def qu(self, **options):

"""Makes a queue."""

return self.widget(QueueCanvas, **options)

def subtract(d1, d2):

"""Subtracts two dictionaries.

Returns a new dictionary containing all the keys from

d1 that are not in d2.

"""

d = {}

for key in d1:

if key not in d2:

d[key] = d1[key]

return d

def diff_dict(d1, d2):

"""Diffs two dictionaries.

Returns two dictionaries: the first contains all the keys

from d1 that are not in d2; the second contains all the keys

that are in both dictionaries, but which have different values.

"""

d = {}

c = {}

for key in d1:

if key not in d2:

d[key] = d1[key]

elif d1[key] is not d2[key]:

c[key] = d1[key]

return d, c

def trim_block(block):

"""Removes comments from the beginning and empty lines from the end."""

if block and block[0].startswith('#'):

block.pop(0)

while block and not block[-1].strip():

block.pop(-1)

"""

The following classes define the composite objects that make

up the display: Row, TopRow, Column and TopColumn. They are

all subclasses of Widget.

"""

class Widget:

"""Superclass of all display objects.

Each Widget keeps a reference to its immediate parent Widget (p)

and to the top-most thing (w).

"""

def __init__(self, p, *args, **options):

self.p = p

self.w = p.w

self.setup(*args, **options)

class Row(Widget):

"""A row of code.

Each row contains two queues, runnable and queued,

and an entry that contains a line of code.

"""

def setup(self, text=''):

self.tag = None

self.fr = self.w.row([0,0,1])

self.queued = self.w.qu(side=LEFT, n=3)

self.runnable = self.w.qu(side=LEFT, n=3, label='Run')

self.en = self.w.en(side=LEFT, font=font)

self.en.bind('<Key>', self.keystroke)

self.w.endrow()

self.put(text)

def update(self, val):

if self.tag: self.clear()

text = str(val)

self.tag = self.runnable.display_text(text)

def clear(self):

self.runnable.delete(self.tag)

def keystroke(self, event=None):

"resize the entry whenever the user types a character"

self.entry_size()

def entry_size(self):

"resize the entry"

text = self.get()

width = self.en.cget('width')

l = len(text) + 2

if l > width:

self.en.configure(width=l)

def add_thread(self, thread):

self.runnable.add_thread(thread)

def remove_thread(self, thread):

self.runnable.remove_thread(thread)

def enqueue_thread(self, thread):

self.queued.add_thread(thread)

def dequeue_thread(self, thread):

self.queued.remove_thread(thread)

def put(self, text):

self.en.delete(0, END)

self.en.insert(0, text)

self.entry_size()

def get(self):

return self.en.get()

class TopRow(Row):

"""Rows in the initialization code at the top.

The top row is special because there is no queue for

queued threads, and the "runnable" queue is actually used

to display the value of variables.

"""

def setup(self, text=''):

Row.setup(self, text)

self.queued.destroy()

self.runnable.delete('all')

class Column(Widget):

"""A list of rows and a few buttons."""

def setup(self, side=TOP, n=0, Row=Row):

self.fr = self.w.fr(side=side, bd=3)

self.Row = Row

self.rows = [self.Row(self) for i in range(n)]

self.buttons = self.w.row([1,1], side=BOTTOM)

self.bu1 = self.w.bu(text='Create thread',

command=self.create_thread)

self.bu2 = self.w.bu(text='Add row',

command=self.add_row)

self.w.endrow()

self.w.endfr()

def num_rows(self):

return len(self.rows)

def add_rows(self, block, keep_blanks=False):

for line in block:

if line or keep_blanks:

self.add_row(line)

def add_row(self, text=''):

self.w.pushfr(self.fr)

row = self.Row(self, text)

self.w.popfr()

self.rows.append(row)

def create_thread(self):

new = Thread(self)

return new

def next_row(self, row):

if row is None:

return self.rows[0]

index = self.rows.index(row)

try:

return self.rows[index+1]

except IndexError:

return None

class TopColumn(Column):

"""The top column where the initialization code is.

The top column is different from the other columns in

two ways: it has different buttons, and it uses the TopRow

constructor to make new rows rather than the Row constructor.

"""

def setup(self, side=TOP, n=0, Row=TopRow):

Column.setup(self, side, n, Row)

self.bu1.configure(text='Run initialization',

command=self.p.run_init)

class QueueCanvas(GuiCanvas):

"""Displays the runnable and queued threads."""

def __init__(self, w, n=1, label='Queue'):

self.n = n

self.label = label

width = 2 * n * FSU

height = 3 * FSU

GuiCanvas.__init__(self, w, width=width, height=height,

transforms=[])

self.threads = []

self.setup()

def setup(self):

self.text([3, 15], self.label, font=font, anchor=W, fill='white')

def add_thread(self, thread):

self.undraw_queue()

self.threads.append(thread)

self.draw_queue()

def remove_thread(self, thread):

self.undraw_queue()

self.threads.remove(thread)

self.draw_queue()

def draw_queue(self):

x = FSU

y = FSU

r = 0.9 * FSU

for thread in self.threads:

self.draw_thread(thread, x, y, r)

x += 1.5*r

if x > self.get_width():

x = FSU

y += 1.5*r

def undraw_queue(self):

for thread in self.threads:

self.delete(thread.tag)

def draw_thread(self, thread, x=FSU, y=FSU, r=0.9*FSU):

thread.tag = 'Thread' + thread.name

self.circle([x, y], r, fill=thread.color, tags=thread.tag)

font=('Courier', int(r+3))

self.text([x, y], thread.name, font=font, tags=thread.tag)

self.tag_bind(thread.tag, '<Button-1>', thread.step_loop)

def undraw_thread(self, thread):

self.delete(thread.tag)

def display_text(self, text):

tag = self.text([15, 15], text, font=font)

return tag

class Namer(object):

def __init__(self):

self.names = all_thread_names

self.next_name = 0

self.colors = ['red', 'orange', 'yellow', 'greenyellow',

'green', 'mediumseagreen', 'skyblue',

'violet', 'magenta']

self.next_color = 0

def next(self, name=None):

if name == None:

name = self.names[self.next_name]

self.next_name += 1

self.next_name %= len(self.names)

color = self.colors[self.next_color]

self.next_color += 1

self.next_color %= len(self.colors)

return name, color

else:

return name, 'white'

class Namespace:

"""Used to store thread-local variables.

Inside the simulator, self refers to the thread's namespace.

"""

class Thread:

"""Represents simulated threads."""

def __init__(self, column, name=None):

self.column = column

self.sync = column.p

self.name, self.color = self.sync.get_name(name)

self.namespace = Namespace()

self.flag_map = {}

self.while_stack = []

self.sync.register(self)

self.start()

def __str__(self):

return '<' + self.name + '>'

def enqueue(self):

"""Puts this thread into queue."""

self.queued = True

self.row.remove_thread(self)

self.row.enqueue_thread(self)

def dequeue(self):

"""Removes this thread from queue."""

self.queued = False

self.row.dequeue_thread(self)

self.row.add_thread(self)

def jump_to(self, row):

"""Removes this thread from its current row and moves it to row."""

if self.row:

self.row.remove_thread(self)

self.row = row

if self.row:

self.row.add_thread(self)

def balk(self):

self.row.remove_thread(self)

self.row = None

def start(self):

"""Moves this thread to the top of the column."""

self.queued = False

self.row = None

self.next_loop()

def next_loop(self):

"""Moves to the next row, looping to the top if necessary."""

self.next_row()

if self.row == None:

self.start()

def next_row(self):

"""Moves this thread to the next row in the column."""

if self.queued:

return

row = self.column.next_row(self.row)

self.jump_to(row)

def skip_body(self):

"""Skips the body of a conditional."""

# get the current line

# get the next line

# compute the change in indent

# find the outdent

source = self.row.get()

head_indent = self.count_spaces(source)

self.next_row()

source = self.row.get()

body_indent = self.count_spaces(source)

indent = body_indent - head_indent

if indent <= 0:

raise SyntaxError('Body of compound statement must be indented.')

while True:

self.next_row()

if self.row == None:

break

source = self.row.get()

line_indent = self.count_spaces(source)

if line_indent <= head_indent:

break

def count_spaces(self, source):

"""Returns the number of leading spaces after expanding tabs."""

s = source.expandtabs(4)

t = s.lstrip(' ')

return len(s) - len(t)

def step(self, event=None):

"""Executes the current line of code, then moves to the next row.

The current limitation of this simulator is that each row

has to contain a complete Python statement. Also, each line

of code is executed atomically.

Args:

event: unused, provided so that this method can be used

as a binding callback

Returns:

line of code that executed or None

"""

if self.queued:

return None

if self.row == None:

return None

self.check_end_while()

source = self.row.get()

print self, source

before = copy.copy(self.sync.locals)

flag = self.exec_line(source, self.sync)

# see if any variables were defined or changed

after = self.sync.locals

defined, changed = diff_dict(after, before)

for key in defined:

self.sync.views[key] = self.row

if defined or changed:

self.sync.update_views()

# either skip to the next line or to the end of a false conditional

if flag:

self.next_row()

else:

self.skip_body()

return source

def exec_line(self, source, sync):

"""Runs a line of source code in the context of the given Sync.

Args:

source: source code from a Row

sync: Sync object

Returns:

if the line is an if statement, returns the result of

evaluating the condition

"""

global current_thread

current_thread = self

sync.globals['self'] = self.namespace

try:

s = source.strip()

code = compile(s, '<user-provided code>', 'exec')

exec code in sync.globals, sync.locals

return True

except SyntaxError as error:

# check whether it's a conditional statement

keyword = s.split()[0]

if keyword in ['if', 'else:', 'while']:

flag = self.handle_conditional(keyword, source, sync)

return flag

else:

raise error

def handle_conditional(self, keyword, source, sync):

"""Evaluates the condition part of an if statement.

Args:

keyword: if, else or while

source: source code from a Row

sync: Sync object

Returns:

if the line is an if statement, returns the result of

evaluating the condition; otherwise raises a SyntaxError

"""

s = source.strip()

if not s.endswith(':'):

raise SyntaxError('Header must end with :')

if keyword in ['if']:

# evaluate the condition

n = len(keyword)

condition = s[n:-1].strip()

flag = eval(condition, sync.globals, sync.locals)

# store the flag

indent = self.count_spaces(source)

self.flag_map[indent] = flag

return flag

elif keyword in ['while']:

# evaluate the condition

n = len(keyword)

condition = s[n:-1].strip()

flag = eval(condition, sync.globals, sync.locals)

if flag:

indent = self.count_spaces(source)

self.while_stack.append((indent, self.row))

return flag

else:

assert keyword == 'else:'

# see whether the condition was true

indent = self.count_spaces(source)

try:

flag = self.flag_map[indent]

return not flag

except KeyError:

raise SyntaxError('else does not match if')

def check_end_while(self):

"""Check if we are at the end of a while loop.

If so, jump to the top.

"""

if not self.while_stack:

return

indent, row = self.while_stack[-1]

source = self.row.get()

if self.count_spaces(source) <= indent:

self.while_stack.pop()

self.jump_to(row)

def step_loop(self, event=None):

self.step()

if self.row == None:

self.start()

def run(self):

while True:

self.step()

if self.row == None: break

def main():

sync = Sync(sys.argv[1:])

sync.mainloop()

if __name__ == '__main__':

main()