#!/usr/bin/python
# Inspired by Mark S. Miller's whenUpdated and reactToUpdate protocol
# described in
# http://www.erights.org/javadoc/org/erights/e/elib/slot/EverReporter.html
# and
# http://www.erights.org/javadoc/org/erights/e/elib/slot/EverReactor.html
# with the following differences: no generation numbers; three methods
# instead of two; and a differing number of messages, in either the
# fast-changing extreme or the slow-changing extreme, three messages
# per communicated change instead of two.
# This protocol shares with Miller's protocol and with MESI the virtue
# that either many writes and no reads, or many reads and no writes,
# result in no communication; it shares with Miller's protocol the
# virtue that it degrades to polling in the case where updates happen
# very frequently (it won't send change notifications more often than
# the sink can receive them) and to asynchronous notification in the
# case where updates happen very rarely.
# A ValueSource accepts just one message: get_value(self, sink), where
# sink is a ValueSink. When the ValueSource has a value --- possibly
# immediately --- it calls sink.send_value(newval). At some later
# time, it calls sink.retract_value(), and then discards the sink.
# A Formula implements the ValueSource interface, but it also has a
# list of ValueSources it draws inputs from. The Formula has a state,
# either unknown, working, or known. The Formula can only be
# "unknown" if no sinks currently care about its answer; the first
# time someone calls get_value on it, it changes to "working".
# A "working" Formula tries to get values from each of its
# ValueSources; on transition into this state, it passes them each a
# FormulaInputSink that will deposit the value in the relevant place
# inside it the Formula. If any of the ValueSources calls
# retract_value() during this time, it must immediately be polled
# again with the same FormulaInputSink.
# Eventually, we hope, all the inputs of the Formula are known. At
# this point, the Formula changes from "working" to "known" state, and
# at this point calls send_value() on any sinks that cared about its
# output. In "known" state, if any input calls retract_value(), the
# Formula becomes "unknown" and calls retract_value() on all the sinks
# attached to its output.
# To accommodate ref-counting nicely, the Formula extends ValueSource
# (rather than having a ValueSource), since "working" must flow from
# the ValueSource interface to the FormulaInputSinks, while "known"
# flows the other way; while the Formula has a list of its input
# ValueSources, the FormulaInputSinks are ephemeral objects with
# references to the Formula. This will impede the garbage-collection
# of "working" formulas. Perhaps the ValueSources should reference
# their sinks weakly.
from __future__ import nested_scopes
import operator
def immediate_evaluator(thunk): thunk()
class QueuedEvaluator(object):
def __init__(self): self.queue = []
def __call__(self, thunk): self.queue.append(thunk)
def run(self):
while self.queue: self.queue.pop(0)()
class ValueSource(object):
def __init__(self, evaluator=immediate_evaluator):
self.value = None
self.sinks = []
self.evaluator = [evaluator]
def delay(self, thunk):
self.evaluator[0](thunk)
def get_value(self, sink):
self.sinks.append(sink)
if self.value:
value = self.value[0]
self.delay(lambda: sink.send_value(value))
def send_value(self, new_value):
assert not self.value
self.value = [new_value]
for sink in self.sinks:
def value_sender(sink_contour):
return lambda: sink_contour.send_value(new_value)
self.delay(value_sender(sink))
def retract_value(self):
assert self.value
self.value = None
sinks = self.sinks
self.sinks = []
for sink in sinks:
def value_retractor(sink_contour):
return lambda: sink_contour.retract_value()
self.delay(value_retractor(sink))
def all(some_boolean_list):
for x in some_boolean_list:
if not x:
return False
return True
class unknown(object): pass
class working(object): pass
class known(object): pass
class FormulaInputSink(object):
def __init__(self, formula, arg_index):
(self.formula, self.arg_index) = (formula, arg_index)
def send_value(self, new_value):
self.formula.send_input(self.arg_index, new_value)
def retract_value(self):
self.formula.retract_input(self.arg_index)
class Formula(ValueSource):
def __init__(self, formula, args, evaluator=immediate_evaluator):
ValueSource.__init__(self, evaluator=evaluator)
(self.formula, self.args) = ([formula], args)
self.state = unknown
self.input_values = [None for arg in self.args]
def get_value(self, sink):
if self.state is unknown:
self.start_working()
return ValueSource.get_value(self, sink)
def start_working(self):
assert self.state is unknown
for ii in range(len(self.input_values)):
if not self.input_values[ii]:
self.request_input(ii)
self.state = working
self.try_to_finish_working()
def finish_working(self):
assert self.state is working
value = apply(self.formula[0], [x for (x,) in self.input_values])
self.send_value(value)
self.state = known
def send_input(self, index, new_value):
assert not self.input_values[index]
assert not self.value # XXX is this wrong?
self.input_values[index] = [new_value]
self.try_to_finish_working()
def try_to_finish_working(self):
if self.state is working and all(self.input_values):
self.finish_working()
def retract_input(self, index):
if self.value:
self.retract_value()
self.input_values[index] = None
if self.state is working:
self.request_input(index)
else:
self.state = unknown
def request_input(self, index):
assert not self.input_values[index]
self.args[index].get_value(FormulaInputSink(self, index))
def ok(a, b): assert a == b, (a, b)
def test():
three = Formula(lambda: 3, [])
ok(three.value, None)
out = ValueSource()
three.get_value(out)
ok(three.value, [3])
ok(out.value, [3])
four = Formula(lambda: 4, [])
ok(four.value, None)
seven = Formula(operator.add, [three, four])
ok(four.value, None)
ok(seven.value, None)
seven.get_value(ValueSource())
ok(seven.value, [7])
in1 = ValueSource()
in2 = ValueSource()
adder = Formula(operator.add, [in1, in2])
ok(adder.state, unknown)
adder.get_value(ValueSource())
ok(adder.value, None)
ok(adder.state, working)
in1.send_value(5)
ok(adder.value, None)
ok(adder.state, working)
in2.send_value(8)
ok(adder.value, [13])
ok(adder.state, known)
in1.retract_value()
ok(adder.value, None)
ok(adder.state, unknown)
in1.send_value(13)
ok(adder.value, None)
ok(adder.state, unknown)
adder.get_value(ValueSource())
ok(adder.value, [21])
ok(adder.state, known)
in1.retract_value()
in2.retract_value()
in1.send_value(3)
ok(adder.value, None)
ok(adder.state, unknown)
in1.retract_value()
in1.send_value(4)
ok(adder.value, None)
ok(adder.state, unknown)
adder.get_value(ValueSource())
ok(adder.value, None)
ok(adder.state, working)
in1.retract_value()
ok(adder.state, working)
in1.send_value(5)
ok(adder.state, working)
in2.send_value(6)
ok(adder.state, known)
ok(adder.value, [11])
test()
