keyparser: moved classes from test/ to ranger/

5 files changed, 458 insertions, 280 deletions

diff --git a/ranger/container/__init__.py b/ranger/container/__init__.py
index 51122291..b3fe9aff 100644
--- a/ranger/container/__init__.py
+++ b/ranger/container/__init__.py
@@ -18,5 +18,5 @@ used to manage stored data
 """
 from ranger.container.history import History
 from ranger.container.keybuffer import KeyBuffer
-from .commandlist import CommandList
+from .keymap import KeyMap
 from .bookmarks import Bookmarks
diff --git a/ranger/container/commandlist.py b/ranger/container/commandlist.py
deleted file mode 100644
index f50603f2..00000000
--- a/ranger/container/commandlist.py
+++ /dev/null
@@ -1,208 +0,0 @@
-# Copyright (C) 2009, 2010  Roman Zimbelmann <romanz@lavabit.com>
-#
-# This program is free software: you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation, either version 3 of the License, or
-# (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program.  If not, see <http://www.gnu.org/licenses/>.
-
-from ranger.ext.openstruct import OpenStruct
-
-class CommandArgument(object):
-	def __init__(self, fm, displayable, keybuffer):
-		self.fm = fm
-		self.wdg = displayable
-		self.keybuffer = keybuffer
-		self.n = keybuffer.number
-		self.keys = str(keybuffer)
-
-def cmdarg(displayable):
-	return CommandArgument(displayable.fm, \
-			displayable, displayable.env.keybuffer)
-
-class CommandList(object):
-	"""
-	CommandLists are dictionary-like objects which give you a command
-	for a given key combination.  CommandLists must be filled before use.
-	"""
-
-	dummy_object = None
-	dummies_in_paths = False
-	paths = {}
-	commandlist = []
-
-	def __init__(self):
-		self.commandlist = []
-		self.paths = {}
-
-	def __getitem__(self, key):
-		"""Returns the command with the given key combination"""
-		if isinstance(key, str):
-			key = self._str_to_tuple(key)
-		return self.paths[key]
-
-	def rebuild_paths(self):
-		"""
-		Fill the path dictionary with dummie objects.
-		We need to know when to clear the keybuffer (when a wrong key is pressed)
-		and when to wait for the rest of the key combination.  For "gg" we
-		will assign "g" to a dummy which tells the program to do the latter
-		and wait.
-		"""
-		if self.dummies_in_paths:
-			self.remove_dummies()
-
-		for cmd in self.commandlist:
-			for key in cmd.keys:
-				for path in self._keypath(key):
-					if path not in self.paths:
-						self.paths[path] = self.dummy_object
-
-		self.dummies_in_paths = True
-
-	def _keypath(self, tup):
-		"""split a tuple like (a,b,c,d) into [(a,), (a,b), (a,b,c)]"""
-		length = len(tup)
-
-		if length == 0:
-			return ()
-		if length == 1:
-			return (tup, )
-
-		current = []
-		all = []
-
-		for i in range(len(tup) - 1):
-			current.append(tup[i])
-			all.append(tuple(current))
-
-		return all
-
-	def remove_dummies(self):
-		"""
-		Remove dummie objects in case you have to rebuild a path dictionary
-		which already contains dummie objects.
-		"""
-		for k in tuple(self.paths.keys()):
-			if self.paths[k] == self.dummy_object: del self.paths[k]
-		self.dummies_in_paths = False
-
-
-	def _str_to_tuple(self, obj):
-		"""splits a string into a tuple of integers"""
-		if isinstance(obj, tuple):
-			return obj
-		elif isinstance(obj, str):
-			return tuple(map(ord, obj))
-		elif isinstance(obj, int):
-			return (obj, )
-		else:
-			raise TypeError('need a str, int or tuple for str_to_tuple')
-
-	def bind(self, fnc, *keys):
-		"""create a Command object and assign it to the given key combinations."""
-		if len(keys) == 0: return
-
-		keys = tuple(map(self._str_to_tuple, keys))
-
-		cmd = Command(fnc, keys)
-
-		self.commandlist.append(cmd)
-		for key in cmd.keys:
-			self.paths[key] = cmd
-
-	def show(self, *keys, **keywords):
-		"""create a Show object and assign it to the given key combinations."""
-		if len(keys) == 0: return
-
-		keys = tuple(map(self._str_to_tuple, keys))
-
-		obj = Show(keywords, keys)
-
-		self.commandlist.append(obj)
-		for key in obj.keys:
-			self.paths[key] = obj
-
-	def alias(self, existing, *new):
-		"""bind the <new> keys to the command of the <existing> key"""
-		existing = self._str_to_tuple(existing)
-		new = tuple(map(self._str_to_tuple, new))
-
-		obj = AliasedCommand(_make_getter(self.paths, existing), new)
-
-		self.commandlist.append(obj)
-		for key in new:
-			self.paths[key] = obj
-
-	def unbind(self, *keys):
-		i = len(self.commandlist)
-		keys = set(map(self._str_to_tuple, keys))
-
-		while i > 0:
-			i -= 1
-			cmd = self.commandlist[i]
-			cmd.keys -= keys
-			if not cmd.keys:
-				del self.commandlist[i]
-
-		for k in keys:
-			del self.paths[k]
-
-	def clear(self):
-		"""remove all bindings"""
-		self.paths.clear()
-		del self.commandlist[:]
-
-
-class Command(object):
-	"""Command objects store information about a command"""
-
-	keys = []
-
-	def __init__(self, fnc, keys):
-		self.keys = set(keys)
-		self.execute = fnc
-
-	def execute(self, *args):
-		"""Execute the command"""
-
-	def execute_wrap(self, displayable):
-		self.execute(cmdarg(displayable))
-
-
-class AliasedCommand(Command):
-	def __init__(self, getter, keys):
-		self.getter = getter
-		self.keys = set(keys)
-
-	def get_execute(self):
-		return self.getter()
-
-	execute = property(get_execute)
-
-
-class Show(object):
-	"""Show objects do things without clearing the keybuffer"""
-
-	keys = []
-	text = ''
-
-	def __init__(self, dictionary, keys):
-		self.keys = set(keys)
-		self.show_obj = OpenStruct(dictionary)
-
-
-def _make_getter(paths, key):
-	def getter():
-		try:
-			return paths[key].execute
-		except:
-			return lambda: None
-	return getter
diff --git a/ranger/container/keybuffer.py b/ranger/container/keybuffer.py
deleted file mode 100644
index 2992aea2..00000000
--- a/ranger/container/keybuffer.py
+++ /dev/null
@@ -1,71 +0,0 @@
-# Copyright (C) 2009, 2010  Roman Zimbelmann <romanz@lavabit.com>
-#
-# This program is free software: you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation, either version 3 of the License, or
-# (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program.  If not, see <http://www.gnu.org/licenses/>.
-
-def to_string(i):
-	try:
-		return chr(i)
-	except ValueError:
-		return '?'
-
-from collections import deque
-from curses.ascii import ascii
-
-ZERO = ord('0')
-NINE = ord('9')
-
-class KeyBuffer(object):
-	def __init__(self):
-		self.number = None
-		self.queue = deque()
-		self.queue_with_numbers = deque()
-
-	def clear(self):
-		"""Clear the keybuffer and restore the initial state"""
-		self.number = None
-		self.queue.clear()
-		self.queue_with_numbers.clear()
-
-	def append(self, key):
-		"""
-		Append a key to the keybuffer, or initial numbers to
-		the number attribute.
-		"""
-		self.queue_with_numbers.append(key)
-
-		if not self.queue and key >= ZERO and key <= NINE:
-			if self.number is None:
-				self.number = 0
-			try:
-				self.number = self.number * 10 + int(chr(key))
-			except ValueError:
-				return
-		else:
-			self.queue.append(key)
-
-	def tuple_with_numbers(self):
-		"""Get a tuple of ascii codes."""
-		return tuple(self.queue_with_numbers)
-
-	def tuple_without_numbers(self):
-		"""
-		Get a tuple of ascii codes.
-		If the keybuffer starts with numbers, those will
-		be left out. To access them, use keybuffer.number
-		"""
-		return tuple(self.queue)
-
-	def __str__(self):
-		"""returns a concatenation of all characters"""
-		return "".join( map( to_string, self.queue_with_numbers ) )
diff --git a/ranger/container/keymap.py b/ranger/container/keymap.py
new file mode 100644
index 00000000..c2aa344f
--- /dev/null
+++ b/ranger/container/keymap.py
@@ -0,0 +1,323 @@
+# Copyright (c) 2009, 2010 hut <hut@lavabit.com>
+#
+# Permission to use, copy, modify, and/or distribute this software for any
+# purpose with or without fee is hereby granted, provided that the above
+# copyright notice and this permission notice appear in all copies.
+#
+# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+from string import ascii_lowercase
+from inspect import isfunction, getargspec
+from ranger.ext.tree import Tree
+
+MAX_ALIAS_RECURSION = 20
+DIRKEY = 9001
+ANYKEY = 9002
+FUNC = 'func'
+DIRECTION = 'direction'
+DIRARG = 'dir'
+ALIASARG = 'alias'
+
+class Direction(object):
+	"""An object with a down and right method"""
+	def __init__(self, down=0, right=0):
+		self.down = down
+		self.right = right
+
+	def copy(self):
+		new = type(self)()
+		new.__dict__.update(self.__dict__)
+		return new
+
+	def __mul__(self, other):
+		copy = self.copy()
+		if other is not None:
+			copy.down *= other
+			copy.right *= other
+		return copy
+	__rmul__ = __mul__
+
+def to_string(i):
+	"""convert a ord'd integer to a string"""
+	try:
+		return chr(i)
+	except ValueError:
+		return '?'
+
+def is_ascii_digit(n):
+	return n >= 48 and n <= 57
+
+class CommandArgs(object):
+	"""The arguments which are passed to a keybinding function"""
+	def __init__(self, fm, widget, keybuffer):
+		self.fm = fm
+		self.wdg = widget
+		self.keybuffer = keybuffer
+		self.n = keybuffer.quant
+		self.direction = keybuffer.directions and keybuffer.directions[0] or None
+		self.directions = keybuffer.directions
+		self.keys = str(keybuffer)
+		self.matches = keybuffer.matches
+		self.binding = keybuffer.command
+
+	@staticmethod
+	def from_widget(self, widget):
+		return CommandArgs(displayable.fm, \
+				displayable, displayable.env.keybuffer)
+
+class KeyMap(Tree):
+	"""Contains a tree with all the keybindings"""
+	def add(self, *args, **keywords):
+		if keywords:
+			return self.add_binding(*args, **keywords)
+		firstarg = args[0]
+		if isfunction(firstarg):
+			keywords[FUNC] = firstarg
+			return self.add_binding(*args[1:], **keywords)
+		def decorator_function(func):
+			keywords = {FUNC:func}
+			self.add(*args, **keywords)
+			return func
+		return decorator_function
+
+	def add_binding(self, *keys, **actions):
+		assert keys
+		bind = Binding(keys, actions)
+		for key in keys:
+			self.set(translate_keys(key), bind)
+
+	def __getitem__(self, key):
+		return self.traverse(translate_keys(key))
+
+class Binding(object):
+	"""The keybinding object"""
+	def __init__(self, keys, actions):
+		assert hasattr(keys, '__iter__')
+		assert isinstance(actions, dict)
+		self.actions = actions
+		try:
+			self.function = self.actions[FUNC]
+		except KeyError:
+			self.function = None
+			self.has_direction = False
+		else:
+			argnames = getargspec(self.function)[0]
+			try:
+				self.has_direction = actions['with_direction']
+			except KeyError:
+				self.has_direction = DIRECTION in argnames
+		try:
+			self.direction = self.actions[DIRARG]
+		except KeyError:
+			self.direction = None
+		try:
+			alias = self.actions[ALIASARG]
+		except KeyError:
+			self.alias = None
+		else:
+			self.alias = translate_keys(alias)
+
+class KeyBuffer(object):
+	"""The evaluator and storage for pressed keys"""
+	def __init__(self, keymap, direction_keys):
+		self.keymap = keymap
+		self.direction_keys = direction_keys
+		self.clear()
+
+	def add(self, key):
+		if self.failure:
+			return None
+		assert isinstance(key, int)
+		assert key >= 0
+
+		# evaluate quantifiers
+		if self.eval_quantifier and self._do_eval_quantifier(key):
+			return
+
+		# evaluate the command
+		if self.eval_command and self._do_eval_command(key):
+			return
+
+		# evaluate (the first number of) the direction-quantifier
+		if self.eval_quantifier and self._do_eval_quantifier(key):
+			return
+
+		# evaluate direction keys {j,k,gg,pagedown,...}
+		if not self.eval_command:
+			self._do_eval_direction(key)
+
+	def _do_eval_direction(self, key):
+		# swap quant and direction_quant in bindings like '<dir>'
+		if self.quant is not None and self.command is None \
+		and self.direction_quant is None:
+			self.direction_quant = self.quant
+			self.quant = None
+
+		try:
+			assert isinstance(self.dir_tree_pointer, dict)
+			self.dir_tree_pointer = self.dir_tree_pointer[key]
+		except KeyError:
+			self.failure = True
+		else:
+			self._direction_try_to_finish()
+
+	def _direction_try_to_finish(self, rec=MAX_ALIAS_RECURSION):
+		if rec <= 0:
+			self.failure = True
+			return None
+		if not isinstance(self.dir_tree_pointer, dict):
+			match = self.dir_tree_pointer
+			assert isinstance(match, Binding)
+			if 'alias' in match.actions:
+				self.dir_tree_pointer = self.direction_keys.traverse(
+					match.alias)
+				self._direction_try_to_finish(rec - 1)
+			else:
+				direction = match.actions['dir'] * self.direction_quant
+				self.directions.append(direction)
+				self.direction_quant = None
+				self.eval_command = True
+				self._try_to_finish()
+
+	def _do_eval_quantifier(self, key):
+		if self.eval_command:
+			tree = self.tree_pointer
+		else:
+			tree = self.dir_tree_pointer
+		if is_ascii_digit(key) and ANYKEY not in tree:
+			attr = self.eval_command and 'quant' or 'direction_quant'
+			if getattr(self, attr) is None:
+				setattr(self, attr, 0)
+			setattr(self, attr, getattr(self, attr) * 10 + key - 48)
+		else:
+			self.eval_quantifier = False
+			return None
+		return True
+
+	def _do_eval_command(self, key):
+		try:
+			assert isinstance(self.tree_pointer, dict)
+			self.tree_pointer = self.tree_pointer[key]
+		except TypeError:
+			print(self.tree_pointer)
+			self.failure = True
+			return None
+		except KeyError:
+			if DIRKEY in self.tree_pointer:
+				self.eval_command = False
+				self.eval_quantifier = True
+				self.tree_pointer = self.tree_pointer[DIRKEY]
+				assert isinstance(self.tree_pointer, (Binding, dict))
+				self.dir_tree_pointer = self.direction_keys._tree
+			elif ANYKEY in self.tree_pointer:
+				self.matches.append(key)
+				self.tree_pointer = self.tree_pointer[ANYKEY]
+				assert isinstance(self.tree_pointer, (Binding, dict))
+				self._try_to_finish()
+			else:
+				self.failure = True
+				return None
+		else:
+			self._try_to_finish()
+
+	def _try_to_finish(self, rec=MAX_ALIAS_RECURSION):
+		if rec <= 0:
+			self.failure = True
+			return None
+		assert isinstance(self.tree_pointer, (Binding, dict, KeyMap))
+		if isinstance(self.tree_pointer, KeyMap):
+			self.tree_pointer = self.tree_pointer._tree
+		if isinstance(self.tree_pointer, Binding):
+			if 'alias' in self.tree_pointer.actions:
+				self.tree_pointer = self.keymap.traverse(
+					translate_keys(self.tree_pointer.actions['alias']))
+				self._try_to_finish(rec - 1)
+			else:
+				self.command = self.tree_pointer
+				self.done = True
+
+	def clear(self):
+		self.failure = False
+		self.done = False
+		self.quant = None
+		self.matches = []
+		self.command = None
+		self.direction_quant = None
+		self.directions = []
+		self.all_keys = []
+		self.tree_pointer = self.keymap._tree
+		self.dir_tree_pointer = self.direction_keys._tree
+
+		self.eval_quantifier = True
+		self.eval_command = True
+
+	def __str__(self):
+		"""returns a concatenation of all characters"""
+		return "".join(to_string(c) for c in self.all_keys)
+
+	def simulate_press(self, string):
+		for char in translate_keys(string):
+			self.add(char)
+			if self.done:
+				return self.command
+			if self.failure:
+				break
+
+key_map = {
+	'dir': DIRKEY,
+	'any': ANYKEY,
+	'cr': ord("\n"),
+	'enter': ord("\n"),
+	'space': ord(" "),
+	'space': ord(" "),
+	'tab': ord('\t'),
+}
+for char in ascii_lowercase:
+	key_map['c-' + char] = ord(char) - 96
+
+def translate_keys(obj):
+	"""
+	Translate a keybinding to a sequence of integers
+
+	Example:
+	lol<CR>   =>   (108, 111, 108, 10)
+	"""
+	assert isinstance(obj, (tuple, int, str))
+	if isinstance(obj, tuple):
+		for char in obj:
+			yield char
+	elif isinstance(obj, int):
+		yield obj
+	elif isinstance(obj, str):
+		in_brackets = False
+		bracket_content = None
+		for char in obj:
+			if in_brackets:
+				if char == '>':
+					in_brackets = False
+					string = ''.join(bracket_content).lower()
+					try:
+						yield key_map[string]
+					except KeyError:
+						yield ord('<')
+						for c in bracket_content:
+							yield ord(c)
+						yield ord('>')
+				else:
+					bracket_content.append(char)
+			else:
+				if char == '<':
+					in_brackets = True
+					bracket_content = []
+				else:
+					yield ord(char)
+		if in_brackets:
+			yield ord('<')
+			for c in bracket_content:
+				yield ord(c)
diff --git a/ranger/ext/tree.py b/ranger/ext/tree.py
new file mode 100644
index 00000000..d7b08cd7
--- /dev/null
+++ b/ranger/ext/tree.py
@@ -0,0 +1,134 @@
+# Copyright (c) 2009, 2010 hut <hut@lavabit.com>
+#
+# Permission to use, copy, modify, and/or distribute this software for any
+# purpose with or without fee is hereby granted, provided that the above
+# copyright notice and this permission notice appear in all copies.
+#
+# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+class Tree(object):
+	def __init__(self, dictionary=None, parent=None, key=None):
+		if dictionary is None:
+			self._tree = dict()
+		else:
+			self._tree = dictionary
+		self.key = key
+		self.parent = parent
+
+	def copy(self):
+		"""Create a deep copy"""
+		def deep_copy_dict(dct):
+			dct = dct.copy()
+			for key, val in dct.items():
+				if isinstance(val, dict):
+					dct[key] = deep_copy_dict(val)
+			return dct
+		newtree = Tree()
+		if isinstance(self._tree, dict):
+			newtree._tree = deep_copy_dict(self._tree)
+		else:
+			newtree._tree = self._tree
+		return newtree
+
+	def merge(self, other, copy=True):
+		"""Merge another Tree into a copy of self"""
+		def deep_merge(branch, otherbranch):
+			assert isinstance(otherbranch, dict)
+			if not isinstance(branch, dict):
+				branch = dict()
+			elif copy:
+				branch = branch.copy()
+			for key, val in otherbranch.items():
+				if isinstance(val, dict):
+					if key not in branch:
+						branch[key] = None
+					branch[key] = deep_merge(branch[key], val)
+				else:
+					branch[key] = val
+			return branch
+
+		if isinstance(self._tree, dict) and isinstance(other._tree, dict):
+			content = deep_merge(self._tree, other._tree)
+		elif copy and hasattr(other._tree, 'copy'):
+			content = other._tree.copy()
+		else:
+			content = other._tree
+		return type(self)(content)
+
+	def set(self, keys, value, force=True):
+		"""Sets the element at the end of the path to <value>."""
+		if not isinstance(keys, (list, tuple)):
+			keys = tuple(keys)
+		if len(keys) == 0:
+			self.replace(value)
+		else:
+			fnc = force and self.plow or self.traverse
+			subtree = fnc(keys)
+			subtree.replace(value)
+
+	def unset(self, iterable):
+		chars = list(iterable)
+		first = True
+
+		while chars:
+			if first or isinstance(subtree, Tree) and subtree.empty():
+				top = chars.pop()
+				subtree = self.traverse(chars)
+				del subtree._tree[top]
+			else:
+				break
+			first = False
+
+	def empty(self):
+		return len(self._tree) == 0
+
+	def replace(self, value):
+		if self.parent:
+			self.parent[self.key] = value
+		self._tree = value
+
+	def plow(self, iterable):
+		"""Move along a path, creating nonexistant subtrees"""
+		tree = self._tree
+		last_tree = None
+		char = None
+		for char in iterable:
+			try:
+				newtree = tree[char]
+				if not isinstance(newtree, dict):
+					raise KeyError()
+			except KeyError:
+				newtree = dict()
+				tree[char] = newtree
+			last_tree = tree
+			tree = newtree
+		if isinstance(tree, dict):
+			return type(self)(tree, parent=last_tree, key=char)
+		else:
+			return tree
+
+	def traverse(self, iterable):
+		"""Move along a path, raising exceptions when failed"""
+		tree = self._tree
+		last_tree = tree
+		char = None
+		for char in iterable:
+			last_tree = tree
+			try:
+				tree = tree[char]
+			except TypeError:
+				raise KeyError("trying to enter leaf")
+			except KeyError:
+				raise KeyError(str(char) + " not in tree " + str(tree))
+		if isinstance(tree, dict):
+			return type(self)(tree, parent=last_tree, key=char)
+		else:
+			return tree
+
+	__getitem__ = traverse