The PEAK Developers' Center   TrellisSTM UserPreferences
HelpContents Search Diffs Info Edit Subscribe XML Print View
The following 695 words could not be found in the dictionary of 50 words (including 50 LocalSpellingWords) and are highlighted below:
Abort   Above   Abstract   Active   Also   An   And   As   Assertion   But   Callbacks   Can   Cell   Cells   Circularity   Cleanup   Commit   Constant   Contents   Controller   Controllers   Creating   Custom   Demo   During   Error   Event   Explicitly   False   For   Framework   Haha   History   However   If   In   It   Last   Like   Link   Links   Listener   Listeners   Local   Logged   Loop   Manager   Max   Memory   Mixin   Nested   None   Normally   Note   Nothing   Notices   Object   Observer   Observers   Of   Otherwise   Pattern   Perform   Points   Put   Python   Record   Register   Remove   Rollback   Runtime   Save   Setattr   Since   Singleton   Software   Some   Subject   Subjects   Table   Task   Testing   That   The   These   They   This   Thus   To   Traceback   Transactional   Trellis   True   Type   Types   Undo   Unless   Unlike   What   When   While   You   Your   abort   aborting   aborts   access   acquired   action   actions   activated   active   activity   actual   actually   addition   additional   adjusted   affecting   after   all   allowed   allowing   allows   already   also   always   an   and   any   applicable   application   are   args   arguments   as   assume   at   atomic   atomically   attr   attribute   attributes   automatic   automatically   available   back   bar   bare   base   basically   baz   be   because   been   before   behave   being   below   best   between   beyond   break   built   but   by   caching   calculating   calculation   call   called   calling   calls   can   cancel   cannot   case   caught   cause   cell   cells   chains   chance   change   changed   changes   circumstances   class   classes   cleanup   code   comes   comitting   commit   commits   committing   completed   complex   conserve   constant   contents   context   control   controlled   controller   convenience   copy   correctly   could   course   create   created   ctrl   current   currently   custom   data   def   default   defer   del   depend   dependencies   dependency   depends   derive   detailing   determining   dictate   didn   differently   dirty   do   document   does   done   during   each   eagerly   early   easier   effect   effectively   else   enough   ensure   enter   entering   entry   equal   equalling   equivalent   error   errors   etc   even   event   events   exactly   example   exc   except   exception   exceptions   executable   execute   executing   execution   existence   exit   exiting   explicitly   exports   external   extremes   f1   f2   f3   failing   fails   fairly   false   far   first   flag   flagging   following   for   forms   found   framework   from   func   function   functions   generally   get   gets   given   goes   greater   grow   guaranteed   happen   happened   has   have   held   hello   here   higher   hist   history   hood   how   however   if   ignored   immediately   implement   implementation   import   in   including   increased   increases   indicates   init   initialize   initialized   initially   install   instance   instances   instead   interact   invocation   invoke   invoked   invokes   involved   is   it   iter   its   job   just   keep   kept   know   l1   l2   last   later   layer   least   life   like   link   link11   link12   link21   link22   links   list   listen   listener   listeners   local   lock   locking   locks   log   loop   lot   main   making   manage   managed   manager   managers   manages   manner   manually   many   means   memory   method   methods   mgr   might   modified   modifies   modify   modifying   module   modules   more   most   msg   much   multi   multiple   multithreaded   must   namespace   necessary   need   needed   needs   nested   network   never   next   no   non   normal   normally   not   note   nothing   notices   notification   notified   num   number   object   objects   observer   observers   occurrence   occurs   of   old   on   once   one   ones   only   op   operation   operations   opposite   optional   or   order   other   out   output   over   overall   own   pass   passed   pattern   peak   per   performing   phase   place   plan   point   position   positional   possible   practical   prefix   pretends   pretty   previous   previously   print   process   program   programs   progresses   prohibited   provided   purposes   raise   raised   re   reached   read   readable   readonly   reads   ready   recalculate   recalculated   recalculation   receive   recent   recently   record   recorded   recording   records   refer   referenceable   referencing   reflect   register   registered   registrations   related   relationship   relationships   released   relevant   remember   repeatedly   replace   replacement   replaces   represents   requires   reraised   resources   responsible   restore   result   return   returns   reverse   rollback   rolled   rule   rules   run   running   runs   s1   s2   safe   same   savepoint   savepoints   saves   schedule   scheduled   schedules   section   see   self   service   set   setattr   sets   setups   shortcut   shortcuts   shorthand   should   shown   simple   simply   single   singleton   slot   slots   so   some   something   sophisticated   source   sp   special   specialized   specific   specified   specifies   standard   starts   state   still   stm   store   strong   structures   subclass   subclassed   subject   subjects   subsequent   success   successfully   such   super   supports   sys   system   taken   takes   task   tb   tedious   terms   test   testing   tests   than   that   the   their   them   then   there   therefore   these   they   things   this   those   though   thread   threading   three   thus   time   times   to   traceback   track   tracks   trellis   true   try   trying   two   typ   type   types   unchanged   under   undo   undoing   undone   unit   unless   unlike   unlink   unlinked   until   up   usable   use   used   useful   uses   using   usually   util   val   value   valued   values   ve   version   very   want   wanted   was   way   weak   weakref   were   what   whatever   when   whenever   where   whether   which   while   whose   why   will   wish   with   within   without   won   words   work   working   works   would   writable   write   writes   yet   you   your   zero  

Clear message

Software Transactional Memory (STM) And Observers

The Trellis is built on a simple Python STM (Software Transactional Memory) and "Observer Pattern" implementation. This document specifies how that implementation works, and tests it.

You should read this document if you plan to implement your own Trellis cell types or other custom data structures, or if you just want to know how things work "under the hood".

Table of Contents

STM History

An STM's job is to manage "atomic" changes to objects: i.e., multiple changes that must happen as a unit, or else be rolled back.

To do this, the STM must have a history: a record of the actions taken within a given "atomic" change set. The PEAK implementation of an STM history is found in the module:

>>> from import STMHistory

>>> hist = STMHistory()

A history object's atomically() method invokes a function as an atomic operation, and its active attribute indicates whether it is currently performing an atomic operation:

>>> def is_active():
...     print "Active?",

>>> is_active()
Active? False

>>> hist.atomically(is_active)
Active? True

>>> is_active()
Active? False

Nested calls to atomically() simply execute the function, without affecting the history:

>>> def nested_operation():
...     hist.atomically(is_active)
...     is_active()

>>> hist.atomically(nested_operation)
Active? True
Active? True

Commit/Abort Notices

In order to get notification of commits or aborts, you can register Python "context managers" with the history, using the manage() method. The manage() method takes a context manager and calls its __enter__() method immediately, then calls its __exit__() method when the current atomic operation is completed. This allows things like locks or other resources to be acquired as the operation progresses, and then get automatically released when the operation is completed:

>>> class DemoManager(object):
...     def __init__(self, num):
...         self.num = num
...     def __enter__(self):
...         print "Manager", self.num, "entering"
...     def __exit__(self, typ, val, tb):
...         print "Manager", self.num, "exiting", typ, val, tb

>>> hist.manage(DemoManager(1))
Traceback (most recent call last):
AssertionError: Can't manage without active history

>>> hist.atomically(hist.manage, DemoManager(2))
Manager 2 entering
Manager 2 exiting None None None

The same context manager can be passed to manage repeatedly, but its enter/exit methods will only be called once:

>>> def multi_manage():
...     mgr = DemoManager(3)
...     hist.manage(mgr)
...     hist.manage(mgr)

>>> hist.atomically(multi_manage)
Manager 3 entering
Manager 3 exiting None None None

And if multiple context managers are registered, their __exit__ methods are called in the opposite order from their __enter__ methods:

>>> def multi_manage():
...     hist.manage(DemoManager(4))
...     hist.manage(DemoManager(5))

>>> hist.atomically(multi_manage)
Manager 4 entering
Manager 5 entering
Manager 5 exiting None None None
Manager 4 exiting None None None

The __exit__() method is normally called with three None values, unless an exception occurs during the operation. In that case, the sys.exc_info() of the exception is passed in to the manager(s), before the exception is re-raised:

>>> def do_error():
...     hist.manage(DemoManager(6))
...     raise TypeError("Testing!")

>>> try:
...     hist.atomically(do_error)
... except TypeError:
...     print "caught exception"
Manager 6 entering
Manager 6 exiting ...TypeError... Testing! <traceback object...>
caught exception

The __exit__() method should not raise an error. Also note that, unlike normal Python context managers, the return value of __exit__() is ignored. (In other words, STM context managers cannot cause an exception to be ignored.)

If an __exit__() method does raise an error, however, subsequent context managers will be passed the type, value, and traceback of the failing manager, and the exception will be reraised:

>>> class ErrorManager(DemoManager):
...     def __exit__(self, typ, val, tb):
...         super(ErrorManager, self).__exit__(typ, val, tb)
...         raise RuntimeError("Haha!")

>>> def manage_with_error():
...     hist.manage(DemoManager(7))
...     hist.manage(ErrorManager("error"))
...     hist.manage(DemoManager(8))

>>> try:
...     hist.atomically(manage_with_error)
... except RuntimeError:
...     print "caught exception"
Manager 7 entering
Manager error entering
Manager 8 entering
Manager 8 exiting None None None
Manager error exiting None None None
Manager 7 exiting ...RuntimeError... Haha! <traceback object...>
caught exception

In other words, all context managers are guaranteed to have their __exit__ methods called, even if one fails. The exception that comes out of the atomically() call will be the most recently-raised exception.

Last, but not least, history objects have a in_cleanup attribute that indicates whether they are currently in the process of comitting or aborting an operation. This can be useful if context managers might call code that needs to behave differently during a commit/abort than during an atomic operation:

>>> hist.in_cleanup

>>> class CleanupManager:
...     def __enter__(self):
...         print "on entry:", hist.in_cleanup
...     def __exit__(self, typ, val, tb):
...         print "on exit:", hist.in_cleanup

>>> hist.atomically(hist.manage, CleanupManager())
on entry: False
on exit: True

Undo, Rollback and Save Points

While you can use context managers to implement some forms of commit/rollback, it's easier for most things to use a history object's "undo" log. The log records "undo actions": functions (and optional positional arguments) that can be used to undo whatever operations have been done so far. For example:

>>> def undoing(msg):
...     print "undoing", msg

>>> def with_undo():
...     hist.on_undo(undoing, "op 1")
...     hist.on_undo(undoing, "op 2")

>>> hist.atomically(with_undo)  # success, nothing gets undone

Nothing happened here, because the operation completed successfully. But if an error occurs, the undo functions are called in reverse order:

>>> def with_undo():
...     hist.on_undo(undoing, "op 1")
...     hist.on_undo(undoing, "op 2")
...     raise TypeError("foo")

>>> try:
...     hist.atomically(with_undo)
... except TypeError:
...     print "caught exception"
undoing op 2
undoing op 1
caught exception

But this does NOT happen if the error occurs in a manager's __exit__() method:

>>> def with_undo():
...     hist.manage(ErrorManager("error"))
...     hist.on_undo(undoing, "op 1")
...     hist.on_undo(undoing, "op 2")

>>> try:
...     hist.atomically(with_undo)
... except RuntimeError:
...     print "caught exception"
Manager error entering
Manager error exiting None None None
caught exception

(That's because managers may be used to control locking or other context setups that need to still be in place for the undo's to be safe.)

Note, by the way, that undo functions must NEVER raise errors, under any circumstances. If they do, any undo functions that have not been called yet, will never be called.

In addition to the automatic rollback on error, you can also record savepoints within an atomic operation, and then rollback to that savepoint at any time later:

>>> def with_savepoint():
...     hist.on_undo(undoing, "op 1")
...     sp = hist.savepoint()
...     hist.on_undo(undoing, "op 2")
...     hist.on_undo(undoing, "op 3")
...     hist.rollback_to(sp)

>>> hist.atomically(with_savepoint)
undoing op 3
undoing op 2

Commit Callbacks

If you want to defer an action until the overall operation is ready to commit, you can use the on_commit(func, *args) method:

>>> def do_something(msg):
...     print "committing", msg

>>> def do_with_commit():
...     hist.on_commit(do_something, "hello!")
...     print "registered commit operation"

>>> hist.atomically(do_with_commit)
registered commit operation
committing hello!

Commit actions are called in the order they are registered (before any managers) and their registrations are subject to undo:

>>> def do_with_commit_and_undo():
...     hist.manage(DemoManager('test'))
...     hist.on_commit(do_something, 1)
...     sp = hist.savepoint()
...     hist.on_commit(do_something, 2)
...     hist.rollback_to(sp)
...     hist.on_commit(do_something, 3)

>>> hist.atomically(do_with_commit_and_undo)
Manager test entering
committing 1
committing 3
Manager test exiting None None None

Commit actions are also allowed to record undo actions, in case there is an error later in the commit process:

>>> def do_with_commit_and_undo():
...     def f1():
...         print "f1 running"
...         hist.on_undo(f3)
...     def f2():
...         print "f2 running"
...         raise AssertionError
...     def f3():
...         print "f3 running"
...     hist.on_commit(f1)
...     hist.on_commit(f2)

>>> try:
...     hist.atomically(do_with_commit_and_undo)
... except AssertionError:
...     print "caught exception"
f1 running
f2 running
f3 running
caught exception

And of course, commit actions are not run if an error occurs before they have a chance to run:

>>> def do_no_commit():
...     hist.on_commit(do_something, "should not happen")
...     raise AssertionError
>>> try:
...     hist.atomically(do_no_commit)
... except AssertionError:
...     print "caught exception"
caught exception

Logged Setattr

As a convenience, you can use the change_attr() method of history objects to automatically log an undo function to restore the old value of the attribute being set:

>>> class SomeObject:
...     pass

>>> s1 = SomeObject()
>>> = 'bar'

>>> def setattr_normally():
...     hist.change_attr(s1, 'foo', "baz")

>>> hist.atomically(setattr_normally)

>>> def setattr_rollback():
...     hist.change_attr(s1, 'foo', "spam")
...     raise TypeError

>>> hist.atomically(setattr_rollback)
Traceback (most recent call last):

>>>      # result is unchanged after rollback

As you can see, this saves you the work of recording the undo operation manually.

The Observer Framework

Above and beyond the bare STM system, the Trellis also needs a strong "observer" system that manages subjects, listeners, and the links between them:

>>> from import stm

In addition, the observer framework supports calculating and caching the "safe recalculation order" of a network of subjects and listeners, so that listeners that modify other subjects are (generally) run before the listeners that depend on those subjects. In the event that a listener modifies a subject that has already been read during a given recalculation, the recalculation order is adjusted, and the atomic operation's history is undone to the point where the modified subject was first read. And, if two listeners interact in such a way that each is modifying something the other has read, then a stm.CircularityError is raised, detailing what listeners were involved in the loop.


A Controller is a more sophisticated version of an STMHistory, that also schedules and tracks the execution of listeners (rules) and what subjects they've read or changed. The Trellis uses a per-thread Controller instance to implement cell recalculation. Controller objects have the following additional methods and attributes, many of which must be invoked by subjects or listeners in order to record their activity effectively:

Register the .manager of the subject to receive commit/abort notices -- basically equivalent to .manage(subject.manager) if subject.manager is not None. When you write methods that modify subjects, you should generally call this method first, in case its manager is (for example) a lock that should be held while modifying the subject.
Record that the subject was "used" (i.e., read) by the current listener, if any. (This method automatically calls lock(subject) to ensure that the subject's context manager, if any, is activated first.)
Record that the subject was "changed" by the current listener or by external code. (This method calls lock(subject) to ensure that the subject's context manager, if any, is activated first, but you should still call lock(subject) before actually making a change.)
schedule(listener, source_layer=None)
Put listener on the recalculation schedule, to be recalculated when its layer is reached. If source_layer is specified, and it's greater or equal than listener.layer, listener.layer will be increased, and if necessary, its position in the recalculation schedule will be adjusted.
Remove listener from the recalculation schedule, if it's currently scheduled.
The listener that is currently being run(), or None if no listener is currently executing.
True if the controller is currently in the read-only commit phase where observers are run and changes are prohibited. False at all other times.

Explicitly invoke a in a controlled manner. This is normally used only when a listener must be run for the first time, and its output must be immediately available. (Otherwise, it would be enough to schedule() it for later.) Cells use this method when their value is read and they have not been initialized.

During the run, the Controller pretends that the listener was run in a previous recalculation, for purposes of determining which rules were run (and therefore may need undoing in the event of an order change) in the current calculation. The how's and why's of this are fairly tedious: just remember that if you are trying to have your listener run for the first time so its dependencies can be initialized, you should use this method to do it. (Since simply calling won't set the current_listener or track dependencies correctly.)

Note that most of these methods and attributes are only usable while an atomic action is in effect. (That is, when the .active attribute is true.) The only exceptions are schedule() and cancel().

The Singleton Controller

During normal Trellis operation, there is only one Controller instance, which is available as trellis.ctrl. It is actually an instance of a LocalController subclass, which is a threading.local. That is, even though it is a single object, it has thread-specific state, allowing it to be used as a singleton even by multithreaded programs.

As a shortcut, the trellis module exports the following methods to its main namespace, so that you can use them without the ctrl. prefix:

  • on_commit()
  • on_undo()
  • atomically()
  • manage()
  • savepoint()
  • rollback_to()
  • change_attr()
  • schedule()
  • cancel()
  • lock()
  • used()
  • changed()
  • initialize()

Thus, trellis.on_commit() is a convenience shorthand for trellis.ctrl.on_commit(). (You must still refer to the ctrl object for access to attributes such as ctrl.current_listener.)

If you wish to replace the standard LocalController (e.g. for testing or a specialized application), you must use the trellis.install_controller() function, which replaces the shortcuts with the methods of the provided object, and sets trellis.ctrl to the replacement object.

(Of course, this will only be useful if you do it before any modules import their own copy of trellis.ctrl or any of the shortcuts, or if they always prefix their uses with trellis.. It's thus best if you install your custom controller very early in the life of your program, if possible.)

Creating Custom Cell Types (TBD)

TODO: write up AbstractCell, ConstantMixin, value/get_value/set_value, etc.

EditText of this page (last modified 2008-05-23 12:49:27)
FindPage by browsing, title search , text search or an index
Or try one of these actions: AttachFile, DeletePage, LikePages, LocalSiteMap, SpellCheck