User:Pseudosphere/mwcollapse.py
From The Wiki Camp 2
Jump to navigationJump to search
A python module for converting finite-state machines into mw-collapsible spaghetti. Works best with tree-like systems; is very inefficient for highly "symmetric" FSMs, since the output size is proportional to the number of state transitions.
class StateNode:
__slots__ = "state", "transitions"
def __init__(self, state, transitions=None):
self.state = tuple(state)
self.transitions = {} if transitions == None else transitions
def __call__(self, var):
return self.state[var]
def __len__(self):
return len(self.transitions)
def __length_hint__(self):
return len(self.transitions)
def __getitem__(self, key):
return self.transitions[key]
def __setitem__(self, key, value):
self.transitions[key] = value
def __delitem__(self, key):
del self.transitions[key]
def __iter__(self):
return iter(self.transitions)
def __reversed__(self):
return reversed(self.transitions)
def __contains__(self, item):
return item in self.transitions
class StateMachine:
__slots__ = "states"
def __init__(self, *states):
self.states = states
def __repr__(self):
return f"<StateMachine object of {len(self.states)} states>"
def __bool__(self):
return bool(self.states)
def __len__(self):
return len(self.states)
def __length_hint__(self):
return len(self.states)
def __getitem__(self, key):
return self.states[key]
def __iter__(self):
return iter(self.states)
def __reversed__(self):
return reversed(self.states)
def __contains__(self, item):
return item in self.states
def index(self, value):
return self.states.index(value)
class ElementContainer:
"""An Element-like sequence of Element-like objects."""
__slots__ = "_children", "_parent"
def __init__(self, *children):
self._children = children
self._parent = None
for c in children:
if isinstance(c, ElementContainer):
c._parent = self
def __str__(self):
return "".join(str(c) for c in self._children)
def compile(self, identifier, statemachine):
for child in self._children:
if isinstance(child, ElementContainer):
child.compile(identifier, statemachine)
def visible(self, state):
return self._parent == None or self._parent.visible(state)
class Element(ElementContainer):
"""An HTML element"""
__slots__ = "_attributes", "_children", "name", "_parent"
@staticmethod
def _gentag(l, name, attributes, children):
l.append("<")
l.append(name)
for k in attributes:
l.append(" ")
l.append(k)
l.append("=\"")
l.append(attributes[k].replace("&", "&").replace('"', """))
l.append("\"")
l.append(">")
l.extend(str(c) for c in children)
l.append("</")
l.append(name)
l.append(">")
def __init__(self, name, *children, attributes=None):
super().__init__(*children)
self._attributes = {} if attributes == None else attributes.copy()
self.name = name
def __str__(self):
l = []
self._gentag(l, self.name, self._attributes, self._children)
return "".join(l)
class Toggleable(Element):
"""An mw-collapsible HTML element; might still be visible when collapsed.
var = index into a boolean tuple of collapsible states;
should not be shared with other elements."""
__slots__ = "var"
def __init__(self, name, var, *children, attributes=None):
super().__init__(name, *children, attributes=attributes)
self.var = var
def compile(self, identifier, statemachine):
self._attributes["id"] = f"mw-customcollapsible-{identifier}-{self.var}"
self._attributes["class"] = self._attributes["class"] + (" mw-collapsible" if statemachine[0](self.var) else " mw-collapsible mw-collapsed") if "class" in self._attributes else ("mw-collapsible" if statemachine[0](self.var) else "mw-collapsible mw-collapsed")
super().compile(identifier, statemachine)
class Collapsible(Toggleable):
"""An mw-collapsible HTML element; should always be hidden while collapsed.
var = index into a boolean tuple of collapsible states;
should not be shared with other elements."""
def visible(self, state):
return state(self._var) and super().visible(state)
class Trigger(Element):
"""A sequence of mw-customtoggle HTML elements."""
__slots__ = "event", "_identifier", "_toggles"
def __init__(self, name, event, content="", attributes=None):
super().__init__(name, content, attributes=attributes)
self.event = event
def __str__(self):
hasclass = "class" in self._attributes
l = []
for i, toggle in enumerate(self._toggles):
if toggle != None:
attributes = self._attributes.copy()
attributes["id"] = f"mw-customcollapsible-{self._identifier}-t{i}-{self.event}"
attributes["class"] = " ".join((attributes["class"], *toggle) if hasclass else toggle)
self._gentag(l, self.name, attributes, self._children)
return "".join(l)
def compile(self, identifier, statemachine):
self._identifier = identifier
self._toggles = tuple(self._gentoggle(statemachine, state, i) for i, state in enumerate(statemachine))
def _gentoggle(self, states, state, index):
if self.event in state and self.visible(state):
s = {"mw-collapsible"}
if index != 0:
s.add("mw-collapsed")
tstate = state[self.event]
if state != tstate:
s.update(f"mw-customtoggle-{self._identifier}-{n}" for n in range(len(state.state)) if state(n) != tstate(n))
s.update(f"mw-customtoggle-{self._identifier}-t{index}-{event}" for event in state)
s.update(f"mw-customtoggle-{self._identifier}-t{states.index(tstate)}-{event}" for event in tstate)
else:
s.add("mw-redundanttoggle")
return s
return None
def _genNode(transitions, d, l, transition, stategen, s):
if s not in d:
node = StateNode(stategen(s))
d[s] = node
l.append(node)
for t in transitions:
newstate = transition(s, t)
if None != newstate:
node[t] = _genNode(transitions, d, l, transition, stategen, newstate)
return node
return d[s]
def genStateMachine(transitions, transition, stategen, initial):
"""Generates a state machine from a transition function.
transitions is an iterable of transition names (the inputs to the state machine).
transition is a function accepting a state (which can be any hashable object) and a transition name;
it returns a new state deterministically and without side effects, or None if the transition name is not applicable for this state.
stategen converts a state to an iterable of boolean values representing the states of collapsibles.
initial is the initial state of the machine."""
l = []
_genNode(transitions, {}, l, transition, stategen, initial)
return StateMachine(*l)
def collapseTrigger(name, event, var, content="", attributes=None):
"""Convenience function to generate a Trigger and Collapsible which can substitute each other."""
return ElementContainer(Trigger(name, event, content, attributes=attributes), Collapsible(name, var, content, attributes=attributes))
def example():
"""An example function generating a simple counter."""
# <!--HTML pseudocode for this example-->
#
# <initial>
# let $COUNTER = 0;
# </initial>
#
# <transition id="increment">
# if $COUNTER != 99 then increment $COUNTER;
# </transition>
# <transition id="decrement">
# if $COUNTER != 0 then decrement $COUNTER;
# </transition>
#
# <stategen>
# display collapsibles with id == ((tens digit of $COUNTER) + 10) or id == (ones digit of $COUNTER);
# </stategen>
#
# <span collapsible-id="10"></span><span collapsible-id="11">1</span><!--...--><span collapsible-id="19">9</span><span collapsible-id="0">0</span><!--...--><span collapsible-id="9">9</span><br/>
# <span trigger-id="increment" style="background-color:#000;border:1px solid;color:#0F0;">+</span><br/>
# <span trigger-id="decrement" style="background-color:#000;border:1px solid;color:red;">-</span>
def transition(state, transition):
if transition == "increment":
return None if state == 99 else state + 1
return None if state == 0 else state - 1
def stategen(state):
l = [n == state % 10 for n in range(10)]
l.extend(n == state // 10 for n in range(10))
return tuple(l)
stateMachine = genStateMachine(("increment", "decrement"), transition, stategen, 0)
elements = [Collapsible("span", 10, "")]
elements.extend(Collapsible("span", n + 10, str(n)) for n in range(1, 10))
elements.extend(Collapsible("span", n, str(n)) for n in range(10))
elements.append("<br/>\n")
elements.append(Trigger("span", "increment", "+", attributes={"style": "background-color:#000;border:1px solid;color:#0F0;"}))
elements.append("<br/>\n")
elements.append(Trigger("span", "decrement", "-", attributes={"style": "background-color:#000;border:1px solid;color:red;"}))
elementContainer = ElementContainer(*elements)
elementContainer.compile("counter", stateMachine)
print(elementContainer)
Output Complexity
"Complexity" is the number of elements with mw-customtoggle.
| FSM | Complexity | |
|---|---|---|
| mwcollapse.py | Optimal | |
| System n bits of information in size (worst case) | ||
| Binary decision tree of depth n | ||
| 15-puzzle style sliding puzzle with n tiles | ||
| System with n states (worst case) | ||
| Counter from 1 to n | ||
| Single-pile Nim of size n | ||
| System n bits of information in size (best case) | ||
| n independent toggle switches | ||
