Import dynamic pattern stuff

3 files changed, 2068 insertions, 0 deletions

diff --git a/dynamic/__init__.py b/dynamic/__init__.py
new file mode 100644
index 0000000..54ae03c
--- /dev/null
+++ b/dynamic/__init__.py
@@ -0,0 +1,100 @@
+""" This file contains functions for extraction dynamical patterns from
+Python code. """
+
+import collections
+from collections import defaultdict
+import json
+
+from .pg_logger import exec_script_str_local
+
+def extract_vars(state):
+    """ Extract active variables from a state. """
+    if 'globals' not in state:
+        return {}
+    variables = state['globals'].copy()
+    for stack in state['stack_to_render']:
+        for name, value in stack['encoded_locals'].items():
+            variables["{}({})".format(name, stack['func_name'])] = value
+    return variables
+
+def finalizer(input_code, output_trace):
+    """ Creates time series from extracted traces. """
+    active_vars = {}
+    var_counter = defaultdict(int)
+    var_vals = defaultdict(list)
+
+    for state_i, state in enumerate(output_trace):
+        line = state.get('line', -1)
+        trace_vars = extract_vars(state)
+
+        # remove inactive vars
+        active_vars = {k:v for k, v in active_vars.items() if k in trace_vars}
+
+        # add new vars to active vars
+        for var in (trace_vars.keys() - active_vars.keys()):
+            var_counter[var] += 1
+            active_vars[var] = "{}_{}".format(var, var_counter[var])
+
+        # add new values to value lists
+        for cur_name, global_name in active_vars.items():
+            # get value (from heap if reference is given)
+            value = trace_vars[cur_name]
+            if value and isinstance(value, list) and value[0] == "REF":
+                value = state["heap"][value[1]]
+            # add to list if new value
+            if global_name not in var_vals or var_vals[global_name][-1][2] != value:
+                var_vals[global_name].append((state_i, line, value))
+
+    # remove variables that had only one value
+    for key in set(var_vals.keys()):
+        if len(var_vals[key]) <= 1:
+            del var_vals[key]
+    return dict(code=input_code, trace=output_trace, series=var_vals)
+
+def following_pairs_patterns(trace_data):
+    series = trace_data['series']
+    for se, val in series.items():
+        for v1, v2 in zip(val, val[1:]):
+            yield "[{}]:[{}]".format(v1[2], v2[2])
+
+def get_trace_data(code, call=None, inputs=None):
+    if call:
+        code += '\n\n' + call
+    if inputs:
+        inputs = json.dumps(inputs)
+    return exec_script_str_local(code, inputs, False, False, finalizer)
+
+def get_attributes(programs, call, inputs):
+    patterns = collections.defaultdict(list)
+    for program in programs:
+        print(program)
+        trace = get_trace_data(program, call, inputs)
+        for pat in following_pairs_patterns(trace):
+            patterns[pat] += [program]
+
+    attrs = collections.OrderedDict()
+    for pat, progs in sorted(patterns.items(), key=lambda x: len(x[1]), reverse=True):
+        if len(progs) < 5:
+            break
+        attrs['dynamic-{}'.format(len(attrs))] = {'desc': pat, 'programs': progs}
+
+    return attrs
+
+if __name__ == '__main__':
+    script = """
+def add(a, b):
+    m = a * b
+    m += a / b
+    m -= a % b
+    return m
+
+s = 0
+for i in range(1, 10):
+    for j in range(1, 10):
+        s += add(i, j)
+print(s)
+"""
+    trace_data = get_trace_data(script)
+    for p in following_pairs_patterns(trace_data):
+        print(p)
+
diff --git a/dynamic/pg_encoder.py b/dynamic/pg_encoder.py
new file mode 100644
index 0000000..7cf0c8e
--- /dev/null
+++ b/dynamic/pg_encoder.py
@@ -0,0 +1,377 @@
+# Online Python Tutor
+# https://github.com/pgbovine/OnlinePythonTutor/
+#
+# Copyright (C) Philip J. Guo (philip@pgbovine.net)
+#
+# Permission is hereby granted, free of charge, to any person obtaining a
+# copy of this software and associated documentation files (the
+# "Software"), to deal in the Software without restriction, including
+# without limitation the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so, subject to
+# the following conditions:
+#
+# The above copyright notice and this permission notice shall be included
+# in all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+# Thanks to John DeNero for making the encoder work on both Python 2 and 3
+
+
+# Given an arbitrary piece of Python data, encode it in such a manner
+# that it can be later encoded into JSON.
+#   http://json.org/
+#
+# We use this function to encode run-time traces of data structures
+# to send to the front-end.
+#
+# Format:
+#   Primitives:
+#   * None, int, long, float, str, bool - unchanged
+#     (json.dumps encodes these fine verbatim, except for inf, -inf, and nan)
+#
+#   exceptions: float('inf')  -> ['SPECIAL_FLOAT', 'Infinity']
+#               float('-inf') -> ['SPECIAL_FLOAT', '-Infinity']
+#               float('nan')  -> ['SPECIAL_FLOAT', 'NaN']
+#               x == int(x)   -> ['SPECIAL_FLOAT', '%.1f' % x]
+#               (this way, 3.0 prints as '3.0' and not as 3, which looks like an int)
+#
+#   If render_heap_primitives is True, then primitive values are rendered
+#   on the heap as ['HEAP_PRIMITIVE', <type name>, <value>]
+#
+#   (for SPECIAL_FLOAT values, <value> is a list like ['SPECIAL_FLOAT', 'Infinity'])
+#
+#   Compound objects:
+#   * list     - ['LIST', elt1, elt2, elt3, ..., eltN]
+#   * tuple    - ['TUPLE', elt1, elt2, elt3, ..., eltN]
+#   * set      - ['SET', elt1, elt2, elt3, ..., eltN]
+#   * dict     - ['DICT', [key1, value1], [key2, value2], ..., [keyN, valueN]]
+#   * instance - ['INSTANCE', class name, [attr1, value1], [attr2, value2], ..., [attrN, valueN]]
+#   * instance with __str__ defined - ['INSTANCE_PPRINT', class name, <__str__ value>]
+#   * class    - ['CLASS', class name, [list of superclass names], [attr1, value1], [attr2, value2], ..., [attrN, valueN]]
+#   * function - ['FUNCTION', function name, parent frame ID (for nested functions)]
+#   * module   - ['module', module name]
+#   * other    - [<type name>, string representation of object]
+#   * compound object reference - ['REF', target object's unique_id]
+#
+# the unique_id is derived from id(), which allows us to capture aliasing
+
+
+# number of significant digits for floats
+FLOAT_PRECISION = 4
+
+
+from collections import defaultdict
+import re, types
+import sys
+import math
+typeRE = re.compile("<type '(.*)'>")
+classRE = re.compile("<class '(.*)'>")
+
+import inspect
+
+# TODO: maybe use the 'six' library to smooth over Py2 and Py3 incompatibilities?
+is_python3 = (sys.version_info[0] == 3)
+if is_python3:
+  # avoid name errors (GROSS!)
+  long = int
+  unicode = str
+
+
+def is_class(dat):
+  """Return whether dat is a class."""
+  if is_python3:
+    return isinstance(dat, type)
+  else:
+    return type(dat) in (types.ClassType, types.TypeType)
+
+
+def is_instance(dat):
+  """Return whether dat is an instance of a class."""
+  if is_python3:
+    return type(dat) not in PRIMITIVE_TYPES and \
+           isinstance(type(dat), type) and \
+           not isinstance(dat, type)
+  else:
+    # ugh, classRE match is a bit of a hack :(
+    return type(dat) == types.InstanceType or classRE.match(str(type(dat)))
+
+
+def get_name(obj):
+  """Return the name of an object."""
+  return obj.__name__ if hasattr(obj, '__name__') else get_name(type(obj))
+
+
+PRIMITIVE_TYPES = (int, long, float, str, unicode, bool, type(None))
+
+def encode_primitive(dat):
+  t = type(dat)
+  if t is float:
+    if math.isinf(dat):
+      if dat > 0:
+        return ['SPECIAL_FLOAT', 'Infinity']
+      else:
+        return ['SPECIAL_FLOAT', '-Infinity']
+    elif math.isnan(dat):
+      return ['SPECIAL_FLOAT', 'NaN']
+    else:
+      # render floats like 3.0 as '3.0' and not as 3
+      if dat == int(dat):
+        return ['SPECIAL_FLOAT', '%.1f' % dat]
+      else:
+        return round(dat, FLOAT_PRECISION)
+  elif t is str and (not is_python3):
+    # hack only for Python 2 strings ... always turn into unicode
+    # and display '?' when it's not valid unicode
+    return dat.decode('utf-8', 'replace')
+  else:
+    # return all other primitives verbatim
+    return dat
+
+
+# grab a line number like ' <line 2>' or ' <line 2b>'
+def create_lambda_line_number(codeobj, line_to_lambda_code):
+  try:
+    lambda_lineno = codeobj.co_firstlineno
+    lst = line_to_lambda_code[lambda_lineno]
+    ind = lst.index(codeobj)
+    # add a suffix for all subsequent lambdas on a line beyond the first
+    # (nix this for now because order isn't guaranteed when you have
+    #  multiple lambdas on the same line)
+    '''
+    if ind > 0:
+      lineno_str = str(lambda_lineno) + chr(ord('a') + ind)
+    else:
+      lineno_str = str(lambda_lineno)
+    '''
+    lineno_str = str(lambda_lineno)
+    return ' <line ' + lineno_str + '>'
+  except:
+    return ''
+
+
+# Note that this might BLOAT MEMORY CONSUMPTION since we're holding on
+# to every reference ever created by the program without ever releasing
+# anything!
+class ObjectEncoder:
+  def __init__(self, render_heap_primitives):
+    # Key: canonicalized small ID
+    # Value: encoded (compound) heap object
+    self.encoded_heap_objects = {}
+
+    self.render_heap_primitives = render_heap_primitives
+
+    self.id_to_small_IDs = {}
+    self.cur_small_ID = 1
+
+    # wow, creating unique identifiers for lambdas is quite annoying,
+    # especially if we want to properly differentiate:
+    # 1.) multiple lambdas defined on the same line, and
+    # 2.) the same lambda code defined multiple times on different lines
+    #
+    # However, it gets confused when there are multiple identical
+    # lambdas on the same line, like:
+    # f(lambda x:x*x, lambda y:y*y, lambda x:x*x)
+
+    # (assumes everything is in one file)
+    # Key:   line number
+    # Value: list of the code objects of lambdas defined
+    #        on that line in the order they were defined
+    self.line_to_lambda_code = defaultdict(list)
+
+
+  def get_heap(self):
+    return self.encoded_heap_objects
+
+
+  def reset_heap(self):
+    # VERY IMPORTANT to reassign to an empty dict rather than just
+    # clearing the existing dict, since get_heap() could have been
+    # called earlier to return a reference to a previous heap state
+    self.encoded_heap_objects = {}
+
+  def set_function_parent_frame_ID(self, ref_obj, enclosing_frame_id):
+    assert ref_obj[0] == 'REF'
+    func_obj = self.encoded_heap_objects[ref_obj[1]]
+    assert func_obj[0] == 'FUNCTION'
+    func_obj[-1] = enclosing_frame_id
+
+
+  # return either a primitive object or an object reference;
+  # and as a side effect, update encoded_heap_objects
+  def encode(self, dat, get_parent):
+    """Encode a data value DAT using the GET_PARENT function for parent ids."""
+    # primitive type
+    if not self.render_heap_primitives and type(dat) in PRIMITIVE_TYPES:
+      return encode_primitive(dat)
+    # compound type - return an object reference and update encoded_heap_objects
+    else:
+      my_id = id(dat)
+
+      try:
+        my_small_id = self.id_to_small_IDs[my_id]
+      except KeyError:
+        my_small_id = self.cur_small_ID
+        self.id_to_small_IDs[my_id] = self.cur_small_ID
+        self.cur_small_ID += 1
+
+      del my_id # to prevent bugs later in this function
+
+      ret = ['REF', my_small_id]
+
+      # punt early if you've already encoded this object
+      if my_small_id in self.encoded_heap_objects:
+        return ret
+
+
+      # major side-effect!
+      new_obj = []
+      self.encoded_heap_objects[my_small_id] = new_obj
+
+      typ = type(dat)
+
+      if typ == list:
+        new_obj.append('LIST')
+        for e in dat:
+          new_obj.append(self.encode(e, get_parent))
+      elif typ == tuple:
+        new_obj.append('TUPLE')
+        for e in dat:
+          new_obj.append(self.encode(e, get_parent))
+      elif typ == set:
+        new_obj.append('SET')
+        for e in dat:
+          new_obj.append(self.encode(e, get_parent))
+      elif typ == dict:
+        new_obj.append('DICT')
+        for (k, v) in dat.items():
+          # don't display some built-in locals ...
+          if k not in ('__module__', '__return__', '__locals__'):
+            new_obj.append([self.encode(k, get_parent), self.encode(v, get_parent)])
+      elif typ in (types.FunctionType, types.MethodType):
+        if is_python3:
+          argspec = inspect.getfullargspec(dat)
+        else:
+          argspec = inspect.getargspec(dat)
+
+        printed_args = [e for e in argspec.args]
+        if argspec.varargs:
+          printed_args.append('*' + argspec.varargs)
+
+        if is_python3:
+          if argspec.varkw:
+            printed_args.append('**' + argspec.varkw)
+          if argspec.kwonlyargs:
+            printed_args.extend(argspec.kwonlyargs)
+        else:
+          if argspec.keywords:
+            printed_args.append('**' + argspec.keywords)
+
+        func_name = get_name(dat)
+
+        pretty_name = func_name
+
+        # sometimes might fail for, say, <genexpr>, so just ignore
+        # failures for now ...
+        try:
+          pretty_name += '(' + ', '.join(printed_args) + ')'
+        except TypeError:
+          pass
+
+        # put a line number suffix on lambdas to more uniquely identify
+        # them, since they don't have names
+        if func_name == '<lambda>':
+            cod = (dat.__code__ if is_python3 else dat.func_code) # ugh!
+            lst = self.line_to_lambda_code[cod.co_firstlineno]
+            if cod not in lst:
+                lst.append(cod)
+            pretty_name += create_lambda_line_number(cod,
+                                                     self.line_to_lambda_code)
+
+        encoded_val = ['FUNCTION', pretty_name, None]
+        if get_parent:
+          enclosing_frame_id = get_parent(dat)
+          encoded_val[2] = enclosing_frame_id
+        new_obj.extend(encoded_val)
+      elif typ is types.BuiltinFunctionType:
+        pretty_name = get_name(dat) + '(...)'
+        new_obj.extend(['FUNCTION', pretty_name, None])
+      elif is_class(dat) or is_instance(dat):
+        self.encode_class_or_instance(dat, new_obj)
+      elif typ is types.ModuleType:
+        new_obj.extend(['module', dat.__name__])
+      elif typ in PRIMITIVE_TYPES:
+        assert self.render_heap_primitives
+        new_obj.extend(['HEAP_PRIMITIVE', type(dat).__name__, encode_primitive(dat)])
+      else:
+        typeStr = str(typ)
+        m = typeRE.match(typeStr)
+
+        if not m:
+          m = classRE.match(typeStr)
+
+        assert m, typ
+
+        if is_python3:
+          encoded_dat = str(dat)
+        else:
+          # ugh, for bytearray() in Python 2, str() returns
+          # non-JSON-serializable characters, so need to decode:
+          encoded_dat = str(dat).decode('utf-8', 'replace')
+        new_obj.extend([m.group(1), encoded_dat])
+
+      return ret
+
+
+  def encode_class_or_instance(self, dat, new_obj):
+    """Encode dat as a class or instance."""
+    if is_instance(dat):
+      if hasattr(dat, '__class__'):
+        # common case ...
+        class_name = get_name(dat.__class__)
+      else:
+        # super special case for something like
+        # "from datetime import datetime_CAPI" in Python 3.2,
+        # which is some weird 'PyCapsule' type ...
+        # http://docs.python.org/release/3.1.5/c-api/capsule.html
+        class_name = get_name(type(dat))
+
+      if hasattr(dat, '__str__') and \
+         (not dat.__class__.__str__ is object.__str__): # make sure it's not the lame default __str__
+        # N.B.: when objects are being constructed, this call
+        # might fail since not all fields have yet been populated
+        try:
+          pprint_str = str(dat)
+        except:
+          pprint_str = '<incomplete object>'
+
+        new_obj.extend(['INSTANCE_PPRINT', class_name, pprint_str])
+        return # bail early
+      else:
+        new_obj.extend(['INSTANCE', class_name])
+        # don't traverse inside modules, or else risk EXPLODING the visualization
+        if class_name == 'module':
+          return
+    else:
+      superclass_names = [e.__name__ for e in dat.__bases__ if e is not object]
+      new_obj.extend(['CLASS', get_name(dat), superclass_names])
+
+    # traverse inside of its __dict__ to grab attributes
+    # (filter out useless-seeming ones, based on anecdotal observation):
+    hidden = ('__doc__', '__module__', '__return__', '__dict__',
+        '__locals__', '__weakref__', '__qualname__')
+    if hasattr(dat, '__dict__'):
+      user_attrs = sorted([e for e in dat.__dict__ if e not in hidden])
+    else:
+      user_attrs = []
+
+    for attr in user_attrs:
+      new_obj.append([self.encode(attr, None), self.encode(dat.__dict__[attr], None)])
+
diff --git a/dynamic/pg_logger.py b/dynamic/pg_logger.py
new file mode 100644
index 0000000..07289e3
--- /dev/null
+++ b/dynamic/pg_logger.py
@@ -0,0 +1,1591 @@
+# Online Python Tutor
+# https://github.com/pgbovine/OnlinePythonTutor/
+#
+# Copyright (C) Philip J. Guo (philip@pgbovine.net)
+#
+# Permission is hereby granted, free of charge, to any person obtaining a
+# copy of this software and associated documentation files (the
+# "Software"), to deal in the Software without restriction, including
+# without limitation the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so, subject to
+# the following conditions:
+#
+# The above copyright notice and this permission notice shall be included
+# in all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+
+# This is the meat of the Online Python Tutor back-end.  It implements a
+# full logger for Python program execution (based on pdb, the standard
+# Python debugger imported via the bdb module), printing out the values
+# of all in-scope data structures after each executed instruction.
+
+
+import imp
+import sys
+import bdb # the KEY import here!
+import re
+import traceback
+import types
+
+# TODO: use the 'six' package to smooth out Py2 and Py3 differences
+is_python3 = (sys.version_info[0] == 3)
+
+# NB: don't use cStringIO since it doesn't support unicode!!!
+if is_python3:
+  import io as StringIO
+  import io # expose regular io for Python3 users too
+else:
+  import StringIO
+from . import pg_encoder
+
+
+# TODO: not threadsafe:
+
+# upper-bound on the number of executed lines, in order to guard against
+# infinite loops
+#MAX_EXECUTED_LINES = 300
+MAX_EXECUTED_LINES = 10000 # on 2016-05-01, I increased the limit from 300 to 1000 for Python due to popular user demand! and I also improved the warning message
+
+#DEBUG = False
+DEBUG = True
+
+BREAKPOINT_STR = '#break'
+
+CLASS_RE = re.compile('class\s+')
+
+
+# simple sandboxing scheme:
+#
+# - use resource.setrlimit to deprive this process of ANY file descriptors
+#   (which will cause file read/write and subprocess shell launches to fail)
+# - restrict user builtins and module imports
+#   (beware that this is NOT foolproof at all ... there are known flaws!)
+#
+# ALWAYS use defense-in-depth and don't just rely on these simple mechanisms
+try:
+  import resource
+  resource_module_loaded = True
+except ImportError:
+  # Google App Engine doesn't seem to have the 'resource' module
+  resource_module_loaded = False
+
+
+# From http://coreygoldberg.blogspot.com/2009/05/python-redirect-or-turn-off-stdout-and.html
+class NullDevice():
+    def write(self, s):
+        pass
+
+
+# These could lead to XSS or other code injection attacks, so be careful:
+# these are now deprecated as of 2016-06-28
+__html__ = None
+def setHTML(htmlStr):
+  global __html__
+  __html__ = htmlStr
+
+__css__ = None
+def setCSS(cssStr):
+  global __css__
+  __css__ = cssStr
+
+__js__ = None
+def setJS(jsStr):
+  global __js__
+  __js__ = jsStr
+
+
+# ugh, I can't figure out why in Python 2, __builtins__ seems to
+# be a dict, but in Python 3, __builtins__ seems to be a module,
+# so just handle both cases ... UGLY!
+if type(__builtins__) is dict:
+  BUILTIN_IMPORT = __builtins__['__import__']
+else:
+  assert type(__builtins__) is types.ModuleType
+  BUILTIN_IMPORT = __builtins__.__import__
+
+
+# whitelist of module imports
+ALLOWED_STDLIB_MODULE_IMPORTS = ('math', 'random', 'time', 'datetime',
+                          'functools', 'itertools', 'operator', 'string',
+                          'collections', 're', 'json',
+                          'heapq', 'bisect', 'copy', 'hashlib')
+
+# allow users to import but don't explicitly import it since it's
+# already been done above
+OTHER_STDLIB_WHITELIST = ('StringIO', 'io')
+
+# TODO: 2017-01-14: this CUSTOM_MODULE_IMPORTS thing is now DEPRECATED ...
+# whitelist of custom modules to import into OPT
+# (TODO: support modules in a subdirectory, but there are various
+# logistical problems with doing so that I can't overcome at the moment,
+# especially getting setHTML, setCSS, and setJS to work in the imported
+# modules.)
+CUSTOM_MODULE_IMPORTS = () # ignore these for now
+#                        ('callback_module',
+#                         'ttt_module',
+#                         'html_module',
+#                         'htmlexample_module',
+# ignore these troublesome imports for now
+#                         'watch_module',   # 'import sys' might be troublesome
+#                         'bintree_module',
+#                         'GChartWrapper',
+#                         'matrix',
+#                         'htmlFrame')
+
+
+# PREEMPTIVELY import all of these modules, so that when the user's
+# script imports them, it won't try to do a file read (since they've
+# already been imported and cached in memory). Remember that when
+# the user's code runs, resource.setrlimit(resource.RLIMIT_NOFILE, (0, 0))
+# will already be in effect, so no more files can be opened.
+#
+# NB: All modules in CUSTOM_MODULE_IMPORTS will be imported, warts and
+# all, so they better work on Python 2 and 3!
+for m in ALLOWED_STDLIB_MODULE_IMPORTS + CUSTOM_MODULE_IMPORTS:
+  __import__(m)
+
+
+# Restrict imports to a whitelist
+def __restricted_import__(*args):
+  # filter args to ONLY take in real strings so that someone can't
+  # subclass str and bypass the 'in' test on the next line
+  args = [e for e in args if type(e) is str]
+
+  if args[0] in ALLOWED_STDLIB_MODULE_IMPORTS + CUSTOM_MODULE_IMPORTS + OTHER_STDLIB_WHITELIST:
+    imported_mod = BUILTIN_IMPORT(*args)
+
+    if args[0] in CUSTOM_MODULE_IMPORTS:
+      # add special magical functions to custom imported modules
+      setattr(imported_mod, 'setHTML', setHTML)
+      setattr(imported_mod, 'setCSS', setCSS)
+      setattr(imported_mod, 'setJS', setJS)
+
+    # somewhat weak protection against imported modules that contain one
+    # of these troublesome builtins. again, NOTHING is foolproof ...
+    # just more defense in depth :)
+    for mod in ('os', 'sys', 'posix', 'gc'):
+      if hasattr(imported_mod, mod):
+        delattr(imported_mod, mod)
+
+    return imported_mod
+  else:
+    raise ImportError('{0} not supported'.format(args[0]))
+
+
+# Support interactive user input by:
+#
+# 1. running the entire program up to a call to raw_input (or input in py3),
+# 2. bailing and returning a trace ending in a special 'raw_input' event,
+# 3. letting the web frontend issue a prompt to the user to grab a string,
+# 4. RE-RUNNING the whole program with that string added to input_string_queue,
+# 5. which should bring execution to the next raw_input call (if
+#    available), or to termination.
+# Repeat until no more raw_input calls are encountered.
+# Note that this is mad inefficient, but is simple to implement!
+
+# VERY IMPORTANT -- set random seed to 0 to ensure deterministic execution:
+import random
+random.seed(0)
+
+# queue of input strings passed from either raw_input or mouse_input
+input_string_queue = []
+
+
+def open_wrapper(*args):
+  if is_python3:
+      raise Exception('''open() is not supported by Python Tutor.
+Instead use io.StringIO() to simulate a file.
+Here is an example: http://goo.gl/uNvBGl''')
+  else:
+      raise Exception('''open() is not supported by Python Tutor.
+Instead use StringIO.StringIO() to simulate a file.
+Here is an example: http://goo.gl/Q9xQ4p''')
+
+# create a more sensible error message for unsupported features
+def create_banned_builtins_wrapper(fn_name):
+  def err_func(*args):
+    raise Exception("'" + fn_name + "' is not supported by Python Tutor.")
+  return err_func
+
+
+class RawInputException(Exception):
+  pass
+
+def raw_input_wrapper(prompt=''):
+  if input_string_queue:
+    input_str = input_string_queue.pop(0)
+
+    # write the prompt and user input to stdout, to emulate what happens
+    # at the terminal
+    sys.stdout.write(str(prompt)) # always convert prompt into a string
+    sys.stdout.write(input_str + "\n") # newline to simulate the user hitting Enter
+    return input_str
+  raise RawInputException(str(prompt)) # always convert prompt into a string
+
+
+# Python 2 input() does eval(raw_input())
+def python2_input_wrapper(prompt=''):
+  if input_string_queue:
+    input_str = input_string_queue.pop(0)
+
+    # write the prompt and user input to stdout, to emulate what happens
+    # at the terminal
+    sys.stdout.write(str(prompt)) # always convert prompt into a string
+    sys.stdout.write(input_str + "\n") # newline to simulate the user hitting Enter
+    return eval(input_str) # remember to eval!
+  raise RawInputException(str(prompt)) # always convert prompt into a string
+
+class MouseInputException(Exception):
+  pass
+
+def mouse_input_wrapper(prompt=''):
+  if input_string_queue:
+    return input_string_queue.pop(0)
+  raise MouseInputException(prompt)
+
+
+
+# blacklist of builtins
+BANNED_BUILTINS = ['reload', 'open', 'compile',
+                   'file', 'eval', 'exec', 'execfile',
+                   'exit', 'quit', 'help',
+                   'dir', 'globals', 'locals', 'vars']
+# Peter says 'apply' isn't dangerous, so don't ban it
+
+IGNORE_VARS = set(('__builtins__', '__name__', '__exception__', '__doc__', '__package__'))
+
+
+'''
+2013-12-26
+
+Okay, what's with this f_valuestack business?
+
+If you compile your own CPython and patch Objects/frameobject.c to add a
+Python accessor for f_valuestack, then you can actually access the value
+stack, which is useful for, say, grabbbing the objects within
+list/set/dict comprehensions as they're being built. e.g., try:
+
+    z = [x*y for x in range(5) for y in range(5)]
+
+Note that on pythontutor.com, I am currently running custom-compiled
+versions of Python-2.7.6 and Python-3.3.3 with this f_valuestack hack.
+Unless you run your own custom CPython, you won't get these benefits.
+
+
+Patch:
+
+ static PyObject *
+ frame_getlineno(PyFrameObject *f, void *closure)
+ {
+     return PyLong_FromLong(PyFrame_GetLineNumber(f));
+ }
+
++// copied from Py2crazy, which was for Python 2, but let's hope this still works!
++static PyObject *
++frame_getvaluestack(PyFrameObject* f) {
++    // pgbovine - TODO: will this memory leak? hopefully not,
++    // since all other accessors seem to follow the same idiom
++    PyObject* lst = PyList_New(0);
++    if (f->f_stacktop != NULL) {
++        PyObject** p = NULL;
++        for (p = f->f_valuestack; p < f->f_stacktop; p++) {
++            PyList_Append(lst, *p);
++        }
++    }
++
++    return lst;
++}
++
+ /* Setter for f_lineno - you can set f_lineno from within a trace function in
+  * order to jump to a given line of code, subject to some restrictions.  Most
+  * lines are OK to jump to because they don't make any assumptions about the
+@@ -368,6 +384,11 @@
+
+ static PyGetSetDef frame_getsetlist[] = {
+     {"f_locals",        (getter)frame_getlocals, NULL, NULL},
+     {"f_lineno",        (getter)frame_getlineno,
+                     (setter)frame_setlineno, NULL},
+     {"f_trace",         (getter)frame_gettrace, (setter)frame_settrace, NULL},
++
++    // pgbovine
++    {"f_valuestack",(getter)frame_getvaluestack,
++                    (setter)NULL /* don't let it be set */, NULL},
++
+     {0}
+ };
+'''
+
+# at_global_scope should be true only if 'frame' represents the global scope
+def get_user_globals(frame, at_global_scope=False):
+  d = filter_var_dict(frame.f_globals)
+
+  # don't blurt out all of f_valuestack for now ...
+  '''
+  if at_global_scope and hasattr(frame, 'f_valuestack'):
+    for (i, e) in enumerate(frame.f_valuestack):
+      d['_tmp' + str(i+1)] = e
+  '''
+
+  # print out list objects being built up in Python 2.x list comprehensions
+  # (which don't have its own special <listcomp> frame, sadly)
+  if not is_python3 and hasattr(frame, 'f_valuestack'):
+    for (i, e) in enumerate([e for e in frame.f_valuestack if type(e) is list]):
+      d['_tmp' + str(i+1)] = e
+
+  # also filter out __return__ for globals only, but NOT for locals
+  if '__return__' in d:
+    del d['__return__']
+  return d
+
+def get_user_locals(frame):
+  ret = filter_var_dict(frame.f_locals)
+  # don't blurt out all of f_valuestack for now ...
+  '''
+  if hasattr(frame, 'f_valuestack'):
+    for (i, e) in enumerate(frame.f_valuestack):
+      ret['_tmp' + str(i+1)] = e
+  '''
+
+  # special printing of list/set/dict comprehension objects as they are
+  # being built up incrementally ...
+  f_name = frame.f_code.co_name
+  if hasattr(frame, 'f_valuestack'):
+    # print out list objects being built up in Python 2.x list comprehensions
+    # (which don't have its own special <listcomp> frame, sadly)
+    if not is_python3:
+      for (i, e) in enumerate([e for e in frame.f_valuestack
+                               if type(e) is list]):
+        ret['_tmp' + str(i+1)] = e
+
+    # for dict and set comprehensions, which have their own frames:
+    if f_name.endswith('comp>'):
+      for (i, e) in enumerate([e for e in frame.f_valuestack
+                               if type(e) in (list, set, dict)]):
+        ret['_tmp' + str(i+1)] = e
+
+  return ret
+
+def filter_var_dict(d):
+  ret = {}
+  for (k,v) in d.items():
+    if k not in IGNORE_VARS:
+      ret[k] = v
+  return ret
+
+
+# yield all function objects locally-reachable from frame,
+# making sure to traverse inside all compound objects ...
+def visit_all_locally_reachable_function_objs(frame):
+  for (k, v) in get_user_locals(frame).items():
+    for e in visit_function_obj(v, set()):
+      if e: # only non-null if it's a function object
+        assert type(e) in (types.FunctionType, types.MethodType)
+        yield e
+
+
+# TODO: this might be slow if we're traversing inside lots of objects:
+def visit_function_obj(v, ids_seen_set):
+  v_id = id(v)
+
+  # to prevent infinite loop
+  if v_id in ids_seen_set:
+    yield None
+  else:
+    ids_seen_set.add(v_id)
+
+    typ = type(v)
+    
+    # simple base case
+    if typ in (types.FunctionType, types.MethodType):
+      yield v
+
+    # recursive cases
+    elif typ in (list, tuple, set):
+      for child in v:
+        for child_res in visit_function_obj(child, ids_seen_set):
+          yield child_res
+
+    elif typ == dict or pg_encoder.is_class(v) or pg_encoder.is_instance(v):
+      contents_dict = None
+
+      if typ == dict:
+        contents_dict = v
+      # warning: some classes or instances don't have __dict__ attributes
+      elif hasattr(v, '__dict__'):
+        contents_dict = v.__dict__
+
+      if contents_dict:
+        for (key_child, val_child) in contents_dict.items():
+          for key_child_res in visit_function_obj(key_child, ids_seen_set):
+            yield key_child_res
+          for val_child_res in visit_function_obj(val_child, ids_seen_set):
+            yield val_child_res
+
+    # degenerate base case
+    yield None
+
+
+class PGLogger(bdb.Bdb):
+    # if custom_modules is non-empty, it should be a dict mapping module
+    # names to the python source code of each module. when _runscript is
+    # called, it will do "from <module> import *" for all modules in
+    # custom_modules before running the user's script and then trace all
+    # code within custom_modules
+    #
+    # if separate_stdout_by_module, then have a separate stdout stream
+    # for each module rather than all stdout going to a single stream
+    def __init__(self, cumulative_mode, heap_primitives, show_only_outputs, finalizer_func,
+                 disable_security_checks=False, crazy_mode=False,
+                 custom_modules=None, separate_stdout_by_module=False, probe_exprs=None):
+        bdb.Bdb.__init__(self)
+        self.mainpyfile = ''
+        self._wait_for_mainpyfile = 0
+
+        if probe_exprs:
+            self.probe_exprs = probe_exprs
+        else:
+            self.probe_exprs = None
+
+        self.separate_stdout_by_module = separate_stdout_by_module
+        self.stdout_by_module = {} # Key: module name, Value: StringIO faux-stdout
+
+        self.modules_to_trace = set(['__main__']) # always trace __main__!
+
+        # Key: module name
+        # Value: module's python code as a string
+        self.custom_modules = custom_modules
+        if self.custom_modules:
+            for module_name in self.custom_modules:
+                self.modules_to_trace.add(module_name)
+
+        self.disable_security_checks = disable_security_checks
+
+        # if True, then displays ALL stack frames that have ever existed
+        # rather than only those currently on the stack (and their
+        # lexical parents)
+        self.cumulative_mode = cumulative_mode
+
+        # if True, then render certain primitive objects as heap objects
+        self.render_heap_primitives = heap_primitives
+
+        # if True, then don't render any data structures in the trace,
+        # and show only outputs
+        self.show_only_outputs = show_only_outputs
+
+        # Run using the custom Py2crazy Python interpreter
+        self.crazy_mode = crazy_mode
+
+        # a function that takes the output trace as a parameter and
+        # processes it
+        self.finalizer_func = finalizer_func
+
+        # each entry contains a dict with the information for a single
+        # executed line
+        self.trace = []
+
+        # if this is true, don't put any more stuff into self.trace
+        self.done = False
+
+        # if this is non-null, don't do any more tracing until a
+        # 'return' instruction with a stack gotten from
+        # get_stack_code_IDs() that matches wait_for_return_stack
+        self.wait_for_return_stack = None
+
+        #http://stackoverflow.com/questions/2112396/in-python-in-google-app-engine-how-do-you-capture-output-produced-by-the-print
+        self.GAE_STDOUT = sys.stdout
+
+        # Key:   function object
+        # Value: parent frame
+        self.closures = {}
+
+        # Key:   code object for a lambda
+        # Value: parent frame
+        self.lambda_closures = {}
+
+        # set of function objects that were defined in the global scope
+        self.globally_defined_funcs = set()
+
+        # Key: frame object
+        # Value: monotonically increasing small ID, based on call order
+        self.frame_ordered_ids = {}
+        self.cur_frame_id = 1
+
+        # List of frames to KEEP AROUND after the function exits.
+        # If cumulative_mode is True, then keep ALL frames in
+        # zombie_frames; otherwise keep only frames where
+        # nested functions were defined within them.
+        self.zombie_frames = []
+
+        # set of elements within zombie_frames that are also
+        # LEXICAL PARENTS of other frames
+        self.parent_frames_set = set()
+
+        # all globals that ever appeared in the program, in the order in
+        # which they appeared. note that this might be a superset of all
+        # the globals that exist at any particular execution point,
+        # since globals might have been deleted (using, say, 'del')
+        self.all_globals_in_order = []
+
+        # very important for this single object to persist throughout
+        # execution, or else canonical small IDs won't be consistent.
+        self.encoder = pg_encoder.ObjectEncoder(self.render_heap_primitives)
+
+        self.executed_script = None # Python script to be executed!
+
+        # if there is at least one line that ends with BREAKPOINT_STR,
+        # then activate "breakpoint mode", where execution should stop
+        # ONLY at breakpoint lines.
+        self.breakpoints = []
+
+        self.prev_lineno = -1 # keep track of previous line just executed
+
+
+    def get_user_stdout(self):
+        def encode_stringio(sio):
+            # This is SUPER KRAZY! In Python 2, the buflist inside of a StringIO
+            # instance can be made up of both str and unicode, so we need to convert
+            # the str to unicode and replace invalid characters with the Unicode '?'
+            # But leave unicode elements alone. This way, EVERYTHING inside buflist
+            # will be unicode. (Note that in Python 3, everything is already unicode,
+            # so we're fine.)
+            if not is_python3:
+                sio.buflist = [(e.decode('utf-8', 'replace')
+                                           if type(e) is str
+                                           else e)
+                                          for e in sio.buflist]
+            return sio.getvalue()
+
+        if self.separate_stdout_by_module:
+            ret = {}
+            for module_name in self.stdout_by_module:
+                ret[module_name] = encode_stringio(self.stdout_by_module[module_name])
+            return ret
+        else:
+            # common case - single stdout stream
+            return encode_stringio(self.user_stdout)
+
+
+    def get_frame_id(self, cur_frame):
+      return self.frame_ordered_ids[cur_frame]
+
+    # Returns the (lexical) parent of a function value.
+    def get_parent_of_function(self, val):
+      if val in self.closures:
+          return self.get_frame_id(self.closures[val])
+      elif val in self.lambda_closures:
+          return self.get_frame_id(self.lambda_closures[val])
+      else:
+        return None
+
+
+    # Returns the (lexical) parent frame of the function that was called
+    # to create the stack frame 'frame'.
+    #
+    # OKAY, this is a SUPER hack, but I don't see a way around it
+    # since it's impossible to tell exactly which function
+    # ('closure') object was called to create 'frame'.
+    #
+    # The Python interpreter doesn't maintain this information,
+    # so unless we hack the interpreter, we will simply have
+    # to make an educated guess based on the contents of local
+    # variables inherited from possible parent frame candidates.
+    def get_parent_frame(self, frame):
+      #print >> sys.stderr, 'get_parent_frame: frame.f_code', frame.f_code
+      for (func_obj, parent_frame) in self.closures.items():
+        # ok, there's a possible match, but let's compare the
+        # local variables in parent_frame to those of frame
+        # to make sure. this is a hack that happens to work because in
+        # Python, each stack frame inherits ('inlines') a copy of the
+        # variables from its (lexical) parent frame.
+        if func_obj.__code__ == frame.f_code:
+          all_matched = True
+          for k in frame.f_locals:
+            # Do not try to match local names
+            if k in frame.f_code.co_varnames:
+              continue
+            if k != '__return__' and k in parent_frame.f_locals:
+              if parent_frame.f_locals[k] != frame.f_locals[k]:
+                all_matched = False
+                break
+
+          if all_matched:
+            return parent_frame
+
+      for (lambda_code_obj, parent_frame) in self.lambda_closures.items():
+        if lambda_code_obj == frame.f_code:
+          # TODO: should we do more verification like above?!?
+          return parent_frame
+
+      return None
+
+
+    def lookup_zombie_frame_by_id(self, frame_id):
+      # TODO: kinda inefficient
+      for e in self.zombie_frames:
+        if self.get_frame_id(e) == frame_id:
+          return e
+      assert False # should never get here
+
+
+    # unused ...
+    #def reset(self):
+    #    bdb.Bdb.reset(self)
+    #    self.forget()
+
+
+    def forget(self):
+        self.lineno = None
+        self.stack = []
+        self.curindex = 0
+        self.curframe = None
+
+    def setup(self, f, t):
+        self.forget()
+        self.stack, self.curindex = self.get_stack(f, t)
+        self.curframe = self.stack[self.curindex][0]
+
+    # should be a reasonably unique ID to match calls and returns:
+    def get_stack_code_IDs(self):
+        return [id(e[0].f_code) for e in self.stack]
+
+
+    # Override Bdb methods
+
+    def user_call(self, frame, argument_list):
+        """This method is called when there is the remote possibility
+        that we ever need to stop in this function."""
+        # TODO: figure out a way to move this down to 'def interaction'
+        # or right before self.trace.append ...
+        if self.done: return
+
+        if self._wait_for_mainpyfile:
+            return
+        if self.stop_here(frame):
+            # delete __return__ so that on subsequent calls to
+            # a generator function, the OLD yielded (returned)
+            # value gets deleted from the frame ...
+            try:
+              del frame.f_locals['__return__']
+            except KeyError:
+              pass
+
+            self.interaction(frame, None, 'call')
+
+    def user_line(self, frame):
+        """This function is called when we stop or break at this line."""
+        if self.done: return
+
+        if self._wait_for_mainpyfile:
+            if ((frame.f_globals['__name__'] not in self.modules_to_trace) or
+                frame.f_lineno <= 0):
+            # older code:
+            #if (self.canonic(frame.f_code.co_filename) != "<string>" or
+            #    frame.f_lineno <= 0):
+                return
+            self._wait_for_mainpyfile = 0
+        self.interaction(frame, None, 'step_line')
+
+    def user_return(self, frame, return_value):
+        """This function is called when a return trap is set here."""
+        if self.done: return
+
+        frame.f_locals['__return__'] = return_value
+        self.interaction(frame, None, 'return')
+
+    def user_exception(self, frame, exc_info):
+        """This function is called if an exception occurs,
+        but only if we are to stop at or just below this level."""
+        if self.done: return
+
+        exc_type, exc_value, exc_traceback = exc_info
+        frame.f_locals['__exception__'] = exc_type, exc_value
+        if type(exc_type) == type(''):
+            exc_type_name = exc_type
+        else: exc_type_name = exc_type.__name__
+
+        if exc_type_name == 'RawInputException':
+          raw_input_arg = str(exc_value.args[0]) # make sure it's a string so it's JSON serializable!
+          self.trace.append(dict(event='raw_input', prompt=raw_input_arg))
+          self.done = True
+        elif exc_type_name == 'MouseInputException':
+          mouse_input_arg = str(exc_value.args[0]) # make sure it's a string so it's JSON serializable!
+          self.trace.append(dict(event='mouse_input', prompt=mouse_input_arg))
+          self.done = True
+        else:
+          self.interaction(frame, exc_traceback, 'exception')
+
+    def get_script_line(self, n):
+        return self.executed_script_lines[n-1]
+
+    # General interaction function
+
+    def interaction(self, frame, traceback, event_type):
+        self.setup(frame, traceback)
+        tos = self.stack[self.curindex]
+        top_frame = tos[0]
+        lineno = tos[1]
+
+        topframe_module = top_frame.f_globals['__name__']
+
+        # debug ...
+        '''
+        print >> sys.stderr
+        print >> sys.stderr, '=== STACK ===', 'curindex:', self.curindex
+        for (e,ln) in self.stack:
+          print >> sys.stderr, e.f_code.co_name + ' ' + e.f_code.co_filename + ' ' + str(ln)
+        print >> sys.stderr, "top_frame", top_frame.f_code.co_name, top_frame.f_code
+        '''
+
+
+        # don't trace inside of ANY functions that aren't user-written code
+        # (e.g., those from imported modules -- e.g., random, re -- or the
+        # __restricted_import__ function in this file)
+        #
+        # empirically, it seems like the FIRST entry in self.stack is
+        # the 'run' function from bdb.py, but everything else on the
+        # stack is the user program's "real stack"
+
+        # Look only at the "topmost" frame on the stack ...
+
+        # if we're not in a module that we are explicitly tracing, skip:
+        # (this comes up in tests/backend-tests/namedtuple.txt)
+        if topframe_module not in self.modules_to_trace:
+          return
+        # also don't trace inside of the magic "constructor" code
+        if top_frame.f_code.co_name == '__new__':
+          return
+        # or __repr__, which is often called when running print statements
+        if top_frame.f_code.co_name == '__repr__':
+          return
+
+        # don't trace if wait_for_return_stack is non-null ...
+        if self.wait_for_return_stack:
+          if event_type == 'return' and \
+             (self.wait_for_return_stack == self.get_stack_code_IDs()):
+            self.wait_for_return_stack = None # reset!
+          return # always bail!
+        else:
+          # Skip all "calls" that are actually class definitions, since
+          # those faux calls produce lots of ugly cruft in the trace.
+          #
+          # NB: Only trigger on calls to functions defined in
+          # user-written code (i.e., co_filename == '<string>'), but that
+          # should already be ensured by the above check for whether we're
+          # in user-written code.
+          if event_type == 'call':
+            first_lineno = top_frame.f_code.co_firstlineno
+            if topframe_module == "__main__":
+                func_line = self.get_script_line(first_lineno)
+            elif topframe_module in self.custom_modules:
+                module_code = self.custom_modules[topframe_module]
+                module_code_lines = module_code.splitlines() # TODO: maybe pre-split lines?
+                func_line = module_code_lines[first_lineno-1]
+            else:
+                # you're hosed
+                func_line = ''
+            #print >> sys.stderr, func_line
+
+            if CLASS_RE.match(func_line.lstrip()): # ignore leading spaces
+              self.wait_for_return_stack = self.get_stack_code_IDs()
+              return
+
+
+        self.encoder.reset_heap() # VERY VERY VERY IMPORTANT,
+                                  # or else we won't properly capture heap object mutations in the trace!
+
+        if event_type == 'call':
+          # Don't be so strict about this assertion because it FAILS
+          # when you're calling a generator (not for the first time),
+          # since that frame has already previously been on the stack ...
+          #assert top_frame not in self.frame_ordered_ids
+
+          self.frame_ordered_ids[top_frame] = self.cur_frame_id
+          self.cur_frame_id += 1
+
+          if self.cumulative_mode:
+            self.zombie_frames.append(top_frame)
+
+        # kinda tricky to get the timing right -- basically, as soon as you
+        # make a call, set sys.stdout to the stream for the appropriate
+        # module, and as soon as you return, set sys.stdout to the
+        # stream for your caller's module. we need to do this on the
+        # return call since we want to immediately start picking up
+        # prints to stdout *right after* this function returns
+        if self.separate_stdout_by_module:
+          if event_type == 'call':
+            if topframe_module in self.stdout_by_module:
+              sys.stdout = self.stdout_by_module[topframe_module]
+            else:
+              sys.stdout = self.stdout_by_module["<other>"]
+          elif event_type == 'return' and self.curindex > 0:
+            prev_tos = self.stack[self.curindex - 1]
+            prev_topframe = prev_tos[0]
+            prev_topframe_module = prev_topframe.f_globals['__name__']
+            if prev_topframe_module in self.stdout_by_module:
+              sys.stdout = self.stdout_by_module[prev_topframe_module]
+            else:
+              sys.stdout = self.stdout_by_module["<other>"]
+
+
+        # only render zombie frames that are NO LONGER on the stack
+        #
+        # subtle: self.stack[:self.curindex+1] is the real stack, since
+        # everything after self.curindex+1 is beyond the top of the
+        # stack. this seems to be relevant only when there's an exception,
+        # since the ENTIRE stack is preserved but self.curindex
+        # starts decrementing as the exception bubbles up the stack.
+        cur_stack_frames = [e[0] for e in self.stack[:self.curindex+1]]
+        zombie_frames_to_render = [e for e in self.zombie_frames if e not in cur_stack_frames]
+
+
+        # each element is a pair of (function name, ENCODED locals dict)
+        encoded_stack_locals = []
+
+
+        # returns a dict with keys: function name, frame id, id of parent frame, encoded_locals dict
+        def create_encoded_stack_entry(cur_frame):
+          #print >> sys.stderr, '- create_encoded_stack_entry', cur_frame, self.closures, self.lambda_closures
+          ret = {}
+
+
+          parent_frame_id_list = []
+
+          f = cur_frame
+          while True:
+            p = self.get_parent_frame(f)
+            if p:
+              pid = self.get_frame_id(p)
+              assert pid
+              parent_frame_id_list.append(pid)
+              f = p
+            else:
+              break
+
+
+          cur_name = cur_frame.f_code.co_name
+
+          if cur_name == '':
+            cur_name = 'unnamed function'
+
+          # augment lambdas with line number
+          if cur_name == '<lambda>':
+            cur_name += pg_encoder.create_lambda_line_number(cur_frame.f_code,
+                                                             self.encoder.line_to_lambda_code)
+
+          # encode in a JSON-friendly format now, in order to prevent ill
+          # effects of aliasing later down the line ...
+          encoded_locals = {}
+
+          for (k, v) in get_user_locals(cur_frame).items():
+            is_in_parent_frame = False
+
+            # don't display locals that appear in your parents' stack frames,
+            # since that's redundant
+            for pid in parent_frame_id_list:
+              parent_frame = self.lookup_zombie_frame_by_id(pid)
+              if k in parent_frame.f_locals:
+                # ignore __return__, which is never copied
+                if k != '__return__':
+                  # these values SHOULD BE ALIASES
+                  # (don't do an 'is' check since it might not fire for primitives)
+                  if parent_frame.f_locals[k] == v:
+                      is_in_parent_frame = True
+
+            if is_in_parent_frame and k not in cur_frame.f_code.co_varnames:
+              continue
+
+            # don't display some built-in locals ...
+            if k == '__module__':
+              continue
+
+            encoded_val = self.encoder.encode(v, self.get_parent_of_function)
+            encoded_locals[k] = encoded_val
+
+
+          # order the variable names in a sensible way:
+
+          # Let's start with co_varnames, since it (often) contains all
+          # variables in this frame, some of which might not exist yet.
+          ordered_varnames = []
+          for e in cur_frame.f_code.co_varnames:
+            if e in encoded_locals:
+              ordered_varnames.append(e)
+
+          # sometimes co_varnames doesn't contain all of the true local
+          # variables: e.g., when executing a 'class' definition.  in that
+          # case, iterate over encoded_locals and push them onto the end
+          # of ordered_varnames in alphabetical order
+          for e in sorted(encoded_locals.keys()):
+            if e != '__return__' and e not in ordered_varnames:
+              ordered_varnames.append(e)
+
+          # finally, put __return__ at the very end
+          if '__return__' in encoded_locals:
+            ordered_varnames.append('__return__')
+
+          # doctor Python 3 initializer to look like a normal function (denero)
+          if '__locals__' in encoded_locals:
+            ordered_varnames.remove('__locals__')
+            local = encoded_locals.pop('__locals__')
+            if encoded_locals.get('__return__', True) is None:
+              encoded_locals['__return__'] = local
+
+          # crucial sanity checks!
+          assert len(ordered_varnames) == len(encoded_locals)
+          for e in ordered_varnames:
+            assert e in encoded_locals
+
+          return dict(func_name=cur_name,
+                      is_parent=(cur_frame in self.parent_frames_set),
+                      frame_id=self.get_frame_id(cur_frame),
+                      parent_frame_id_list=parent_frame_id_list,
+                      encoded_locals=encoded_locals,
+                      ordered_varnames=ordered_varnames)
+
+
+        i = self.curindex
+
+        # look for whether a nested function has been defined during
+        # this particular call:
+        if i > 1: # i == 1 implies that there's only a global scope visible
+          for v in visit_all_locally_reachable_function_objs(top_frame):
+            if (v not in self.closures and \
+                v not in self.globally_defined_funcs):
+
+              # Look for the presence of the code object (v.func_code
+              # for Python 2 or v.__code__ for Python 3) in the
+              # constant pool (f_code.co_consts) of an enclosing
+              # stack frame, and set that frame as your parent.
+              #
+              # This technique properly handles lambdas passed as
+              # function parameters. e.g., this example:
+              #
+              # def foo(x):
+              #   bar(lambda y: x + y)
+              # def bar(a):
+              #   print a(20)
+              # foo(10)
+              chosen_parent_frame = None
+              # SUPER hacky but seems to work -- use reversed(self.stack)
+              # because we want to traverse starting from the TOP of the stack
+              # (most recent frame) and find the first frame containing
+              # a constant code object that matches v.__code__ or v.func_code
+              #
+              # required for this example from Berkeley CS61a:
+              #
+              # def f(p, k):
+              #     def g():
+              #         print(k)
+              #     if k == 0:
+              #         f(g, 1)
+              # f(None, 0)
+              #
+              # there are two calls to f, each of which defines a
+              # closure g that should point to the respective frame.
+              #
+              # note that for the second call to f, the parent of the
+              # g defined in there should be that frame, which is at
+              # the TOP of the stack. this reversed() hack does the
+              # right thing. note that if you don't traverse the stack
+              # backwards, then you will mistakenly get the parent as
+              # the FIRST f frame (bottom of the stack).
+              for (my_frame, my_lineno) in reversed(self.stack):
+                if chosen_parent_frame:
+                  break
+
+                for frame_const in my_frame.f_code.co_consts:
+                  if frame_const is (v.__code__ if is_python3 else v.func_code):
+                    chosen_parent_frame = my_frame
+                    break
+
+              # 2013-12-01 commented out this line so tests/backend-tests/papajohn-monster.txt
+              # works without an assertion failure ...
+              #assert chosen_parent_frame # I hope this always passes :0
+
+              # this condition should be False for functions declared in global scope ...
+              if chosen_parent_frame in self.frame_ordered_ids:
+                self.closures[v] = chosen_parent_frame
+                self.parent_frames_set.add(chosen_parent_frame) # unequivocally add to this set!!!
+                if not chosen_parent_frame in self.zombie_frames:
+                  self.zombie_frames.append(chosen_parent_frame)
+          else:
+            # look for code objects of lambdas defined within this
+            # function, which comes up in cases like line 2 of:
+            # def x(y):
+            #   (lambda z: lambda w: z+y)(y)
+            #
+            # x(42)
+            if top_frame.f_code.co_consts:
+              for e in top_frame.f_code.co_consts:
+                if type(e) == types.CodeType and e.co_name == '<lambda>':
+                  # TODO: what if it's already in lambda_closures?
+                  self.lambda_closures[e] = top_frame
+                  self.parent_frames_set.add(top_frame) # copy-paste from above
+                  if not top_frame in self.zombie_frames:
+                    self.zombie_frames.append(top_frame)
+        else:
+          # if there is only a global scope visible ...
+          for (k, v) in get_user_globals(top_frame).items():
+            if (type(v) in (types.FunctionType, types.MethodType) and \
+                v not in self.closures):
+              self.globally_defined_funcs.add(v)
+
+
+        # climb up until you find '<module>', which is (hopefully) the global scope
+        top_frame = None
+        while True:
+          cur_frame = self.stack[i][0]
+          cur_name = cur_frame.f_code.co_name
+          if cur_name == '<module>':
+            break
+
+          # do this check because in some cases, certain frames on the
+          # stack might NOT be tracked, so don't push a stack entry for
+          # those frames. this happens when you have a callback function
+          # in an imported module. e.g., your code:
+          #     def foo():
+          #         bar(baz)
+          #
+          #     def baz(): pass
+          #
+          # imported module code:
+          #     def bar(callback_func):
+          #         callback_func()
+          #
+          # when baz is executing, the real stack is [foo, bar, baz] but
+          # bar is in imported module code, so pg_logger doesn't trace
+          # it, and it doesn't show up in frame_ordered_ids. thus, the
+          # stack to render should only be [foo, baz].
+          if cur_frame in self.frame_ordered_ids:
+            encoded_stack_locals.append(create_encoded_stack_entry(cur_frame))
+            if not top_frame:
+                top_frame = cur_frame
+          i -= 1
+
+        zombie_encoded_stack_locals = [create_encoded_stack_entry(e) for e in zombie_frames_to_render]
+
+
+        # encode in a JSON-friendly format now, in order to prevent ill
+        # effects of aliasing later down the line ...
+        encoded_globals = {}
+        cur_globals_dict = get_user_globals(tos[0], at_global_scope=(self.curindex <= 1))
+        for (k, v) in cur_globals_dict.items():
+          encoded_val = self.encoder.encode(v, self.get_parent_of_function)
+          encoded_globals[k] = encoded_val
+
+          if k not in self.all_globals_in_order:
+            self.all_globals_in_order.append(k)
+
+        # filter out globals that don't exist at this execution point
+        # (because they've been, say, deleted with 'del')
+        ordered_globals = [e for e in self.all_globals_in_order if e in encoded_globals]
+        assert len(ordered_globals) == len(encoded_globals)
+
+
+        # merge zombie_encoded_stack_locals and encoded_stack_locals
+        # into one master ordered list using some simple rules for
+        # making it look aesthetically pretty
+        stack_to_render = [];
+
+        # first push all regular stack entries
+        if encoded_stack_locals:
+          for e in encoded_stack_locals:
+            e['is_zombie'] = False
+            e['is_highlighted'] = False
+            stack_to_render.append(e)
+
+          # highlight the top-most active stack entry
+          stack_to_render[0]['is_highlighted'] = True
+
+
+        # now push all zombie stack entries
+        for e in zombie_encoded_stack_locals:
+          # don't display return value for zombie frames
+          # TODO: reconsider ...
+          '''
+          try:
+            e['ordered_varnames'].remove('__return__')
+          except ValueError:
+            pass
+          '''
+
+          e['is_zombie'] = True
+          e['is_highlighted'] = False # never highlight zombie entries
+
+          stack_to_render.append(e)
+
+        # now sort by frame_id since that sorts frames in "chronological
+        # order" based on the order they were invoked
+        stack_to_render.sort(key=lambda e: e['frame_id'])
+
+
+
+        # create a unique hash for this stack entry, so that the
+        # frontend can uniquely identify it when doing incremental
+        # rendering. the strategy is to use a frankenstein-like mix of the
+        # relevant fields to properly disambiguate closures and recursive
+        # calls to the same function
+        for e in stack_to_render:
+          hash_str = e['func_name']
+          # frame_id is UNIQUE, so it can disambiguate recursive calls
+          hash_str += '_f' + str(e['frame_id'])
+
+          # needed to refresh GUI display ...
+          if e['is_parent']:
+            hash_str += '_p'
+
+          # TODO: this is no longer needed, right? (since frame_id is unique)
+          #if e['parent_frame_id_list']:
+          #  hash_str += '_p' + '_'.join([str(i) for i in e['parent_frame_id_list']])
+          if e['is_zombie']:
+            hash_str += '_z'
+
+          e['unique_hash'] = hash_str
+
+
+        # handle probe_exprs *before* encoding the heap with self.encoder.get_heap
+        encoded_probe_vals = {}
+        if self.probe_exprs:
+            if top_frame: # are we in a function call?
+                top_frame_locals = get_user_locals(top_frame)
+            else:
+                top_frame_locals = {}
+            for e in self.probe_exprs:
+                try:
+                    # evaluate it with globals + locals of the top frame ...
+                    probe_val = eval(e, cur_globals_dict, top_frame_locals)
+                    encoded_probe_vals[e] = self.encoder.encode(probe_val, self.get_parent_of_function)
+                except:
+                    pass # don't encode the value if there's been an error
+
+        if self.show_only_outputs:
+          trace_entry = dict(line=lineno,
+                             event=event_type,
+                             func_name=tos[0].f_code.co_name,
+                             globals={},
+                             ordered_globals=[],
+                             stack_to_render=[],
+                             heap={},
+                             stdout=self.get_user_stdout())
+        else:
+          trace_entry = dict(line=lineno,
+                             event=event_type,
+                             func_name=tos[0].f_code.co_name,
+                             globals=encoded_globals,
+                             ordered_globals=ordered_globals,
+                             stack_to_render=stack_to_render,
+                             heap=self.encoder.get_heap(),
+                             stdout=self.get_user_stdout())
+          if encoded_probe_vals:
+            trace_entry['probe_exprs'] = encoded_probe_vals
+
+        # optional column numbers for greater precision
+        # (only relevant in Py2crazy, a hacked CPython that supports column numbers)
+        if self.crazy_mode:
+          # at the very least, grab the column number
+          trace_entry['column'] = frame.f_colno
+
+          # now try to find start_col and extent
+          # (-1 is an invalid instruction index)
+          if frame.f_lasti >= 0:
+            key = (frame.f_code.co_code, frame.f_lineno, frame.f_colno,frame.f_lasti)
+            if key in self.bytecode_map:
+              v = self.bytecode_map[key]
+              trace_entry['expr_start_col'] = v.start_col
+              trace_entry['expr_width'] = v.extent
+              trace_entry['opcode'] = v.opcode
+
+        # set a 'custom_module_name' field if we're executing in a module
+        # that's not the __main__ script:
+        if topframe_module != "__main__":
+          trace_entry['custom_module_name'] = topframe_module
+
+        # TODO: refactor into a non-global
+        # these are now deprecated as of 2016-06-28
+        global __html__, __css__, __js__
+        if __html__:
+          trace_entry['html_output'] = __html__
+        if __css__:
+          trace_entry['css_output'] = __css__
+        if __js__:
+          trace_entry['js_output'] = __js__
+
+        # if there's an exception, then record its info:
+        if event_type == 'exception':
+          # always check in f_locals
+          exc = frame.f_locals['__exception__']
+          trace_entry['exception_msg'] = exc[0].__name__ + ': ' + str(exc[1])
+
+
+        # append to the trace only the breakpoint line and the next
+        # executed line, so that if you set only ONE breakpoint, OPT shows
+        # the state before and after that line gets executed.
+        append_to_trace = True
+        if self.breakpoints:
+          if not ((lineno in self.breakpoints) or (self.prev_lineno in self.breakpoints)):
+            append_to_trace = False
+
+          # TRICKY -- however, if there's an exception, then ALWAYS
+          # append it to the trace, so that the error can be displayed
+          if event_type == 'exception':
+            append_to_trace = True
+
+        self.prev_lineno = lineno
+
+        if append_to_trace:
+          self.trace.append(trace_entry)
+
+
+        # sanity check to make sure the state of the world at a 'call' instruction
+        # is identical to that at the instruction immediately following it ...
+        '''
+        if len(self.trace) > 1:
+          cur = self.trace[-1]
+          prev = self.trace[-2]
+          if prev['event'] == 'call':
+            assert cur['globals'] == prev['globals']
+            for (s1, s2) in zip(cur['stack_to_render'], prev['stack_to_render']):
+              assert s1 == s2
+            assert cur['heap'] == prev['heap']
+            assert cur['stdout'] == prev['stdout']
+        '''
+
+
+        if len(self.trace) >= MAX_EXECUTED_LINES:
+          self.trace.append(dict(event='instruction_limit_reached', exception_msg='Stopped after running ' + str(MAX_EXECUTED_LINES) + ' steps. Please shorten your code,\nsince Python Tutor is not designed to handle long-running code.'))
+          self.force_terminate()
+
+        self.forget()
+
+
+    def _runscript(self, script_str):
+        self.executed_script = script_str
+        self.executed_script_lines = self.executed_script.splitlines()
+
+        for (i, line) in enumerate(self.executed_script_lines):
+          line_no = i + 1
+          if line.endswith(BREAKPOINT_STR):
+            self.breakpoints.append(line_no)
+
+
+        # populate an extent map to get more accurate ranges from code
+        if self.crazy_mode:
+            # in Py2crazy standard library as Python-2.7.5/Lib/super_dis.py
+            import super_dis
+            try:
+                self.bytecode_map = super_dis.get_bytecode_map(self.executed_script)
+            except:
+                # failure oblivious
+                self.bytecode_map = {}
+
+
+        # When bdb sets tracing, a number of call and line events happens
+        # BEFORE debugger even reaches user's code (and the exact sequence of
+        # events depends on python version). So we take special measures to
+        # avoid stopping before we reach the main script (see user_line and
+        # user_call for details).
+        self._wait_for_mainpyfile = 1
+
+
+        # ok, let's try to sorta 'sandbox' the user script by not
+        # allowing certain potentially dangerous operations.
+        user_builtins = {}
+
+        # ugh, I can't figure out why in Python 2, __builtins__ seems to
+        # be a dict, but in Python 3, __builtins__ seems to be a module,
+        # so just handle both cases ... UGLY!
+        if type(__builtins__) is dict:
+          builtin_items = __builtins__.items()
+        else:
+          assert type(__builtins__) is types.ModuleType
+          builtin_items = []
+          for k in dir(__builtins__):
+            builtin_items.append((k, getattr(__builtins__, k)))
+
+        for (k, v) in builtin_items:
+          if k == 'open': # put this before BANNED_BUILTINS
+            user_builtins[k] = open_wrapper
+          elif k in BANNED_BUILTINS:
+            user_builtins[k] = create_banned_builtins_wrapper(k)
+          elif k == '__import__':
+            user_builtins[k] = __restricted_import__
+          else:
+            if k == 'raw_input':
+              user_builtins[k] = raw_input_wrapper
+            elif k == 'input':
+              if is_python3:
+                # Python 3 input() is Python 2 raw_input()
+                user_builtins[k] = raw_input_wrapper
+              else:
+                user_builtins[k] = python2_input_wrapper
+            else:
+              user_builtins[k] = v
+
+        user_builtins['mouse_input'] = mouse_input_wrapper
+
+        # TODO: we can disable these imports here, but a crafty user can
+        # always get a hold of them by importing one of the external
+        # modules, so there's no point in trying security by obscurity
+        user_builtins['setHTML'] = setHTML
+        user_builtins['setCSS'] = setCSS
+        user_builtins['setJS'] = setJS
+
+        if self.separate_stdout_by_module:
+          self.stdout_by_module["__main__"] = StringIO.StringIO()
+          if self.custom_modules:
+            for module_name in self.custom_modules:
+              self.stdout_by_module[module_name] = StringIO.StringIO()
+          self.stdout_by_module["<other>"] = StringIO.StringIO() # catch-all for all other modules we're NOT tracing
+          sys.stdout = self.stdout_by_module["<other>"] # start with <other>
+        else:
+          # default -- a single unified stdout stream
+          self.user_stdout = StringIO.StringIO()
+          sys.stdout = self.user_stdout
+
+        self.ORIGINAL_STDERR = sys.stderr
+
+        # don't do this, or else certain kinds of errors, such as syntax
+        # errors, will be silently ignored. WEIRD!
+        #sys.stderr = NullDevice # silence errors
+
+        user_globals = {}
+
+        # if there are custom_modules, 'import' them into user_globals,
+        # which emulates "from <module> import *"
+        if self.custom_modules:
+            for mn in self.custom_modules:
+                # http://code.activestate.com/recipes/82234-importing-a-dynamically-generated-module/
+                new_m = imp.new_module(mn)
+                exec(self.custom_modules[mn], new_m.__dict__) # exec in custom globals
+                user_globals.update(new_m.__dict__)
+
+        # important: do this LAST to get precedence over values in custom_modules
+        user_globals.update({"__name__"    : "__main__",
+                             "__builtins__" : user_builtins})
+
+        try:
+          # enforce resource limits RIGHT BEFORE running script_str
+
+          # set ~200MB virtual memory limit AND a 5-second CPU time
+          # limit (tuned for Webfaction shared hosting) to protect against
+          # memory bombs such as:
+          #   x = 2
+          #   while True: x = x*x
+          if resource_module_loaded and (not self.disable_security_checks):
+            resource.setrlimit(resource.RLIMIT_AS, (200000000, 200000000))
+            resource.setrlimit(resource.RLIMIT_CPU, (5, 5))
+
+            # protect against unauthorized filesystem accesses ...
+            resource.setrlimit(resource.RLIMIT_NOFILE, (0, 0)) # no opened files allowed
+
+            # VERY WEIRD. If you activate this resource limitation, it
+            # ends up generating an EMPTY trace for the following program:
+            #   "x = 0\nfor i in range(10):\n  x += 1\n   print x\n  x += 1\n"
+            # (at least on my Webfaction hosting with Python 2.7)
+            #resource.setrlimit(resource.RLIMIT_FSIZE, (0, 0))  # (redundancy for paranoia)
+
+            # The posix module is a built-in and has a ton of OS access
+            # facilities ... if you delete those functions from
+            # sys.modules['posix'], it seems like they're gone EVEN IF
+            # someone else imports posix in a roundabout way. Of course,
+            # I don't know how foolproof this scheme is, though.
+            # (It's not sufficient to just "del sys.modules['posix']";
+            #  it can just be reimported without accessing an external
+            #  file and tripping RLIMIT_NOFILE, since the posix module
+            #  is baked into the python executable, ergh. Actually DON'T
+            #  "del sys.modules['posix']", since re-importing it will
+            #  refresh all of the attributes. ergh^2)
+            for a in dir(sys.modules['posix']):
+              delattr(sys.modules['posix'], a)
+            # do the same with os
+            for a in dir(sys.modules['os']):
+              # 'path' is needed for __restricted_import__ to work
+              # and 'stat' is needed for some errors to be reported properly
+              if a not in ('path', 'stat'):
+                delattr(sys.modules['os'], a)
+            # ppl can dig up trashed objects with gc.get_objects()
+            import gc
+            for a in dir(sys.modules['gc']):
+              delattr(sys.modules['gc'], a)
+            del sys.modules['gc']
+
+            # sys.modules contains an in-memory cache of already-loaded
+            # modules, so if you delete modules from here, they will
+            # need to be re-loaded from the filesystem.
+            #
+            # Thus, as an extra precaution, remove these modules so that
+            # they can't be re-imported without opening a new file,
+            # which is disallowed by resource.RLIMIT_NOFILE
+            #
+            # Of course, this isn't a foolproof solution by any means,
+            # and it might lead to UNEXPECTED FAILURES later in execution.
+            del sys.modules['os']
+            del sys.modules['os.path']
+            del sys.modules['sys']
+
+          self.run(script_str, user_globals, user_globals)
+        # sys.exit ...
+        except SystemExit:
+          #sys.exit(0)
+          raise bdb.BdbQuit
+        except:
+          if DEBUG:
+            traceback.print_exc()
+
+          trace_entry = dict(event='uncaught_exception')
+
+          (exc_type, exc_val, exc_tb) = sys.exc_info()
+          if hasattr(exc_val, 'lineno'):
+            trace_entry['line'] = exc_val.lineno
+          if hasattr(exc_val, 'offset'):
+            trace_entry['offset'] = exc_val.offset
+
+          trace_entry['exception_msg'] = type(exc_val).__name__ + ": " +  str(exc_val)
+
+          # SUPER SUBTLE! if ANY exception has already been recorded by
+          # the program, then DON'T record it again as an uncaught_exception.
+          # This looks kinda weird since the exact exception message doesn't
+          # need to match up, but in practice, there should be at most only
+          # ONE exception per trace.
+          already_caught = False
+          for e in self.trace:
+            if e['event'] == 'exception':
+              already_caught = True
+              break
+
+          if not already_caught:
+            if not self.done:
+              self.trace.append(trace_entry)
+
+          raise bdb.BdbQuit # need to forceably STOP execution
+
+
+    def force_terminate(self):
+      #self.finalize()
+      raise bdb.BdbQuit # need to forceably STOP execution
+
+
+    def finalize(self):
+      sys.stdout = self.GAE_STDOUT # very important!
+      sys.stderr = self.ORIGINAL_STDERR
+
+      assert len(self.trace) <= (MAX_EXECUTED_LINES + 1)
+
+      # don't do this anymore ...
+      '''
+      # filter all entries after 'return' from '<module>', since they
+      # seem extraneous:
+      res = []
+      for e in self.trace:
+        res.append(e)
+        if e['event'] == 'return' and e['func_name'] == '<module>':
+          break
+      '''
+
+      res = self.trace
+
+      # if the SECOND to last entry is an 'exception'
+      # and the last entry is return from <module>, then axe the last
+      # entry, for aesthetic reasons :)
+      if len(res) >= 2 and \
+         res[-2]['event'] == 'exception' and \
+         res[-1]['event'] == 'return' and res[-1]['func_name'] == '<module>':
+        res.pop()
+
+      self.trace = res
+
+      if self.custom_modules:
+        # when there's custom_modules, call with a dict as the first parameter
+        return self.finalizer_func(dict(main_code=self.executed_script,
+                                        custom_modules=self.custom_modules),
+                                   self.trace)
+      else:
+        # common case
+        return self.finalizer_func(self.executed_script, self.trace)
+
+
+import json
+
+# the MAIN meaty function!!!
+def exec_script_str(script_str, raw_input_lst_json, options_json, finalizer_func):
+  if options_json:
+    options = json.loads(options_json)
+  else:
+    # defaults
+    options = {'cumulative_mode': False,
+               'heap_primitives': False, 'show_only_outputs': False}
+
+  py_crazy_mode = ('py_crazy_mode' in options and options['py_crazy_mode'])
+
+  logger = PGLogger(options['cumulative_mode'], options['heap_primitives'], options['show_only_outputs'], finalizer_func,
+                    crazy_mode=py_crazy_mode)
+
+  # TODO: refactor these NOT to be globals
+  global input_string_queue
+  input_string_queue = []
+  if raw_input_lst_json:
+    # TODO: if we want to support unicode, remove str() cast
+    input_string_queue = [str(e) for e in json.loads(raw_input_lst_json)]
+
+  global __html__, __css__, __js__
+  __html__, __css__, __js__ = None, None, None
+
+  try:
+    logger._runscript(script_str)
+  except bdb.BdbQuit:
+    pass
+  finally:
+    logger.finalize()
+
+
+# disables security check and returns the result of finalizer_func
+# WARNING: ONLY RUN THIS LOCALLY and never over the web, since
+# security checks are disabled
+#
+# [optional] probe_exprs is a list of strings representing
+# expressions whose values to probe at each step (advanced)
+def exec_script_str_local(script_str, raw_input_lst_json, cumulative_mode, heap_primitives, finalizer_func, probe_exprs=None):
+  # TODO: add py_crazy_mode option here too ...
+  logger = PGLogger(cumulative_mode, heap_primitives, False, finalizer_func, disable_security_checks=True, probe_exprs=probe_exprs)
+
+  # TODO: refactor these NOT to be globals
+  global input_string_queue
+  input_string_queue = []
+  if raw_input_lst_json:
+    # TODO: if we want to support unicode, remove str() cast
+    input_string_queue = [str(e) for e in json.loads(raw_input_lst_json)]
+
+  global __html__, __css__, __js__
+  __html__, __css__, __js__ = None, None, None
+
+  try:
+    logger._runscript(script_str)
+  except bdb.BdbQuit:
+    pass
+  finally:
+    return logger.finalize()
+
+
+# deprecated?!?
+def exec_str_with_user_ns(script_str, user_ns, finalizer_func):
+  logger = PGLogger(False, False, False, finalizer_func, disable_security_checks=True)
+
+  global __html__, __css__, __js__
+  __html__, __css__, __js__ = None, None, None
+
+  try:
+    logger._runscript(script_str, user_ns)
+  except bdb.BdbQuit:
+    pass
+  finally:
+    return logger.finalize()
+