root/cly/trunk/cly/builder.py

# -*- coding: utf-8 -*-
#
# Copyright (C) 2006-2007 Alec Thomas <alec@swapoff.org>
#
# This software is licensed as described in the file COPYING, which
# you should have received as part of this distribution.
#


"""Classes for constructing CLY grammars."""


import datetime
import os
import posixpath
import re
import warnings
from itertools import chain
from xml.dom import minidom
from inspect import isclass, getargspec
from cly.exceptions import *
from cly.parser import Context

try:
    import pytz
except ImportError:
    pytz = None


__all__ = [
    'Node', 'Masquerade', 'Defaults', 'Alias', 'Group', 'If', 'Apply', 'Action',
    'Variable', 'Grammar', 'XMLGrammar', 'Help', 'LazyHelp', 'Word', 'Keyword',
    'String', 'URI', 'LDAPDN', 'Integer', 'Float', 'IP', 'Hostname', 'Host',
    'EMail', 'File', 'Boolean', 'KeyValue', 'AbsoluteTime', 'RelativeTime',
    'Timezone', 'cull_candidates',
    ]
__docformat__ = 'restructuredtext en'


class Node(object):
    """The base class for all grammar nodes.

    Any :class:`Node` instances passed to the constructor will become children of
    this node in the grammar hierarchy. :class:`Node`\ s as keyword arguments
    will be named after their keyword, while positional arguments will be
    provided auto-generated names. This is generally only useful for "control"
    nodes, such as :class:`Alias`.

    Supported keyword arguments:

        :help:
            string or callable returning a list of (key, help) tuples A help
            string or a callable returning an iterable of (key, help) pairs.
            There is a useful class called Help which can be used for this
            purpose.

        :name:
            The name of the node. If ommitted the keyword argument name used in
            the parent Node is used. The node name also defines the node path
            and the default pattern to match against if not explicitly provided:

            >>> Node(name='something')
            <Node:/something>

    The following constructor arguments are also class variables, and as
    such can be overridden at the class level by subclasses of Node. Useful If
    you find yourself using a particular pattern repeatedly.

        :pattern:
            The regular expression used to match user input. If not provided,
            the node name is used:

            >>> a = Node(name='something')
            >>> a.pattern == a.name
            True

        :separator:
            A regular expression used to match the text separating this node
            and the next.

        :group:
            Nodes with the same group value will be collated visually.
            Generally a number, but can also be a string or any other
            comparable object.

        :order:
            Within a group, nodes are normally ordered alphabetically. This can
            be overridden by setting this to a value other than 0.

        :match_candidates:
            Modifies the behaviour of the parser when matching completion
            candidates.

            The :meth:`candidates` method returns a list of words that match at the
            current token, which are then used for completion.  If
            ``match_candidates=True`` the allowed input will be explicitly
            constrainted to just these candidates.

            ``match_candidates`` will be set automatically if
            :meth:`candidates` is provided.

            Useful for situations where you have a general regex pattern (eg. a
            pattern matching files) but a known set of matches at this point
            (eg.  files in the current directory).

        :cull_candidates:
            If ``True`` (the default) :meth:`candidates` may return a static
            list of candidates that is automatically culled based on the text
            being matched. This avoids a lot of boiler plate code.

            >>> a = Node(candidates=['one', 'two'])
            >>> print list(a.candidates(None, ''))
            ['one ', 'two ']
            >>> print list(a.candidates(None, 'o'))
            ['one ']

        :traversals:
            The number of times this node can match in any parse context.
            :class:`Alias` nodes allow for multiple traversal.

            If ``traversals=0`` the node will match an infinite number of times.

        :label:
            Specify the global label for this node. This can be used by the
            :class:`Alias` to refer to nodes by label rather than path.
    """
    pattern = None
    separator = r'\s+|\s*$'
    order = 0
    match_candidates = False
    cull_candidates = True
    traversals = 1
    label = None

    def __init__(self, *anonymous, **kwargs):
        self._children = {}
        self._group = None
        help = kwargs.pop('help', '')
        if isinstance(help, basestring):
            self._help = help
        elif callable(help):
            self.help = help
        else:
            raise InvalidHelp('help must be a callable or a string')
        if 'pattern' in kwargs:
            self.pattern = kwargs.pop('pattern')
        if 'separator' in kwargs:
            self.separator = kwargs.pop('separator')
        if 'candidates' in kwargs:
            candidates = kwargs.pop('candidates')
            if callable(candidates):
                self.candidates = candidates
            else:
                self.candidates = lambda c, t: candidates
            self.match_candidates = True
        self.cull_candidates = kwargs.pop('cull_candidates', self.cull_candidates)
        if self.cull_candidates:
            def cull(context, text):
                return cull_candidates(cull.candidates(context, text), text)
            cull.candidates = self.candidates
            self.candidates = cull
        if self.pattern is not None:
            self._pattern = re.compile(self.pattern)
        self._separator = re.compile(self.separator)
        if self.pattern is not None and self.separator is not None:
            self._full_match = re.compile('(?:%s)(?:%s)' %
                                          (self.pattern, self.separator))
        self.name = kwargs.pop('name', None)
        self.parent = None
        self.__anonymous_children = 0
        self(*anonymous, **kwargs)

    def _get_group(self):
        if self._group is None and self.parent:
            return self.parent.group
        return self._group or 0

    def _set_group(self, group):
        self._group = group

    group = property(lambda self: self._get_group(),
                     lambda self, value: self._set_group(value))

    def _set_name(self, name):
        """Set the name of this node.

        If the Node does not have an existing matching pattern associated with
        it, a pattern will be created using the name.
        """
        self._name = name
        if isinstance(name, basestring) and self.pattern is None:
            self.pattern = name
            self._pattern = re.compile(name)
        if self.pattern is not None and self.separator is not None:
            self._full_match = re.compile('(?:%s)(?:%s)' %
                                          (self.pattern, self.separator))
    name = property(lambda self: self._name,
                    lambda self, name: self._set_name(name))

    def help(self, context):
        """Return help for node.

        :returns: A sequence of tuples in the form (lhs, help).
        """
        if self.name == self.pattern:
            yield (self.name, self._help)
        else:
            yield ('<%s>' % self.name, self._help)

    def __call__(self, *anonymous, **options):
        """Update or add options and child nodes.

        Positional arguments are treated as anonymous child nodes, while
        keyword arguments can either be named child nodes or attribute updates
        for this node. See __init__ for more information on attributes.

        >>> top = Node(name='top')
        >>> top(subnode=Node())
        <Node:/top>
        >>> top.find('/subnode')
        <Node:/top/subnode>
        """
        for node in anonymous:
            if not isinstance(node, Node):
                raise InvalidAnonymousNode('"%r" must be a Node object' % node)
            # TODO Convert help to name instead of __anonymous_<n>
            node.name = '__anonymous_%i' % self.__anonymous_children
            node.parent = self
            self._children[node.name] = node
            self.__anonymous_children += 1

        for k, v in options.iteritems():
            if isinstance(v, Node):
                k = k.rstrip('_')
                v.name = k
                v.parent = self
                self._children[k] = v
            else:
                try:
                    setattr(self, k, v)
                except AttributeError:
                    raise AttributeError('Can\'t set attribute "%s"' % k)
        return self

    def __iter__(self):
        """Iterate over child nodes, ignoring context.

        >>> tree = Node()(two=Node(), three=Node())
        >>> list(tree)
        [<Node:/three>, <Node:/two>]
        """
        def nat_tokenise(key, splitter=re.compile(r'(\d+)')):
            def convert(k):
              if k.isdigit():
                return int(k)
              return k
            return [convert(el) for el in splitter.split(key)]

        children = sorted(self._children.values(),
                          key=lambda i: (i.group, i.order, nat_tokenise(i.name)))
        for child in children:
            yield child

    def __setitem__(self, key, child):
        """Emulate dictionary set.

        >>> node = Node()
        >>> node['two'] = Node()
        >>> list(node.walk())
        [<Node:/>, <Node:/two>]
        """
        self(**{key: child})

    def __getitem__(self, key):
        """Emulate dictionary get.

        >>> node = Node()(two=Node())
        >>> node['two']
        <Node:/two>
        """
        return self._children[key]

    def __delitem__(self, key):
        """Emulate dictionary delete.

        >>> node = Node(two=Node(), three=Node())
        >>> list(node.walk())
        [<Node:/>, <Node:/three>, <Node:/two>]
        >>> del node['two']
        >>> list(node.walk())
        [<Node:/>, <Node:/three>]
        """
        child = self._children.pop(key)
        child.parent = None

    def __contains__(self, key):
        """Emulate dictionary key existence test.

        >>> node = Node(two=Node(), three=Node())
        >>> 'two' in node
        True
        """
        return key in self._children

    def walk(self, predicate=None):
        """Perform a recursive walk of the grammar tree.

        >>> tree = Node(two=Node(three=Node(), four=Node()))
        >>> list(tree.walk())
        [<Node:/>, <Node:/two>, <Node:/two/four>, <Node:/two/three>]
        """
        if predicate is None:
            predicate = lambda node: True

        def _walk(root):
            if not predicate(root):
                return
            yield root
            for node in root._children.itervalues():
                for subnode in _walk(node):
                    yield subnode

        for node in _walk(self):
            yield node

    def children(self, context, follow=False):
        """Iterate over child nodes, optionally follow()ing branches.

        >>> from cly import *
        >>> grammar = Grammar(two=Node(three=Node(),
        ...                            four=Node()),
        ...                            five=Alias(target='../two/*'))
        >>> parser = Parser(grammar)
        >>> context = Context(parser, None)
        >>> list(grammar.children(context))
        [<Alias:/five for /two/*>, <Node:/two>]
        >>> list(grammar.children(context, follow=True))
        [<Node:/two/four>, <Node:/two/three>, <Node:/two>]
        """
        for child in self:
            if child.valid(context):
                if follow:
                    for branch in child.follow(context):
                        if branch.valid(context):
                            yield branch
                else:
                    yield child

    def follow(self, context):
        """Return alternative Nodes to traverse.

        The children() method calls this method when follow=True to expand
        aliased nodes, although it could be used for other purposes."""
        yield self

    def selected(self, context, match):
        """This node was selected by the parser.

        By default, informs the context that the node has been traversed."""
        context.selected(self)

    def next(self, context):
        """Return an iterable over the set of next candidate nodes."""
        for child in self.children(context, follow=True):
            yield child

    def match(self, context):
        """Does this node match the current token?

        Must return a regex match object or None for no match. If
        ``match_candidates`` is true the token must also match one of the values
        returned by ``candidates()``.

        Must include separator in determining whether a match was
        successful."""
        if not self.valid(context):
            return None
        match = self._pattern.match(context.command, context.cursor)
        if match:
            # Check that separator matches as well
            if not self._separator.match(context.command, context.cursor +
                                         len(match.group())):
                return None
            if self.match_candidates and match.group() + ' ' not in \
                    self.candidates(context, match.group()):
                return None
            return match

    def advance(self, context):
        """Advance context cursor based on this nodes match."""
        match = self._full_match.match(context.command, context.cursor)
        context.advance(len(match.group()))

    def visible(self, context):
        """Should this node be visible?"""
        return True

    def terminal(self, context):
        """This node was selected as a terminal."""
        raise UnexpectedEOL(context)

    def depth(self):
        """The depth of this node in the grammar.

        >>> grammar = Grammar(one=Node(), two=Node())
        >>> grammar.depth()
        0
        >>> grammar.find('/two').depth()
        1
        """
        return self.parent and self.parent.depth() + 1 or 0

    def path(self):
        """The full grammar path to this node. Path components are separated
        by a forward slash.

        >>> grammar = Grammar(one=Node(), two=Node())
        >>> grammar.find('/two').path()
        '/two'
        """
        names = []
        node = self
        while node is not None:
            if node.name is not None:
                names.insert(0, node.name)
            node = node.parent
        return '/' + '/'.join(names)

    def candidates(self, context, text):
        """Return an iterable of completion candidates for the given text. The
        default is to use the content of self.help().

        :param text: Text entered so far.

        >>> grammar = Grammar(one=Node(), two=Node())
        >>> list(grammar.find('/one').candidates(None, 'o'))
        ['one ']
        >>> list(grammar.find('/one').candidates(None, 't'))
        []
        """
        for key, help in self.help(context):
            if key[0] != '<':
                yield key

    def find(self, path):
        """Find a Node by path rooted at this node.

        :param path: "Path" to the node, or a label.
        :returns: Found node.

        >>> top = Node(name='top', one=Node(),
        ...            two=Node(three=Node()))
        >>> top.find('/two/three')
        <Node:/top/two/three>
        >>> top.find('/one/bar')
        Traceback (most recent call last):
        ...
        InvalidNodePath: /top/one/bar
        """
        if self.label == path:
            return self
        components = filter(None, path.split('/'))
        if not components:
            return self
        for child in self:
            if not path.startswith('/'):
                return child.find(path)
            elif child.name == components[0]:
                return child.find('/' + '/'.join(components[1:]))
        if path.startswith('/'):
            raise InvalidNodePath(posixpath.join(self.path(), path.strip('/')))
        else:
            raise InvalidNodePath(path)

    def valid(self, context):
        """Is this node valid in the given context?"""
        # Node is invalid if traversed more than self.traversals times
        return not self.traversals or \
            context.traversed(self) < self.traversals

    def _get_anonymous(self):
        """Is this node anonymous?"""
        return self.name.startswith('__anonymous_')

    anonymous = property(_get_anonymous, doc=_get_anonymous.__doc__)

    def update(self, node):
        """Merge another node into this one.

        If a merging node collides with an existing one, the existing node
        will be preserved and the merging nodes children merged.

        :param node: Node to merge into this.
        """
        self.__anonymous_children += node.__anonymous_children
        for key, child in node._children.iteritems():
            if key not in self:
                self[key] = child
            else:
                self[key].update(child)

    def __repr__(self):
        return '<%s:%s>' % (self.__class__.__name__, self.path() or '<root>')

    @classmethod
    def cast_attribute(cls, namespace, name, value):
        """Define functions for casting attributes to their correct Python type.

        Upcalling is necessary.

        :param namespace: The XML namespace of the attribute. Compare against
                    XMLGrammar.EVAL_NS to determine if forced evaluation
                    can/should occur.
        :param name: Attribute name.
        :param value: Value to cast.

        :returns: Tuple of (value, options) where options is a dictionary of
                  extra Node constructor arguments.
        """
        casts = {
            'traversals': int, 'group': group_cast,
            'order': int, 'match_candidates': boolean_cast,
            'with_context': boolean_cast,
            }
        if name in casts:
            return casts[name](value), {}

        # Attributes that can be strings but by default have a method.
        if name == 'help' and namespace != XMLGrammar.EVAL_NS:
            return value, {}

        # Is the destination Node attribute callable? Do a lazy eval.
        function = getattr(cls, name, None)
        if callable(function):
            args, _, _, _ = getargspec(function)
            if args and args[0] == 'self':
                args.pop(0)
            value = lazy_attr_evaluator(value, args)
        return value, {}

    @classmethod
    def attribute_aliases(cls):
        """Define attribute aliases for this node.

        Parent classes are automatically merged, so upcalling is unnecessary.

        :returns: Mapping of old to new keys.
        """
        return {'if': 'valid'}


class Masquerade(Node):
    """A node that masquerades as other nodes.

    Masquerade is a general-purpose tool for dynamically inserting nodes into
    the grammar at the current location. Implementations should override the
    ``masqueraded()`` method.

    Use cases:

      - Conditionally present nodes.
      - Dynamically generated nodes.
      - Aliases for other parts of the grammar.

    >>> from cly.parser import Parser
    >>> class Privileged(Masquerade):
    ...     authenticated = False
    ...     def masqueraded(self, context):
    ...         if not self.authenticated:
    ...             return []
    ...         shutdown = Node(Action(self.shutdown), name='shutdown')
    ...         return [shutdown]
    ...     def shutdown(self):
    ...         print 'shutdown()'
    >>> privileged = Privileged()
    >>> parser = Parser(Grammar(privileged, one=Node()))
    >>> parser.execute('shutdown')
    Traceback (most recent call last):
    ...
    InvalidToken: invalid token 'shutdown'
    >>> privileged.authenticated = True
    >>> parser.execute('shutdown')
    shutdown()
    """

    def masqueraded(self, context):
        """Return a sequence of all masqueraded nodes.

        Masquerades as child nodes by default.
        """
        return super(Masquerade, self).children(context, follow=True)

    def selected(self, context, match):
        raise SystemError('Masqueraded nodes should never be selected')

    def follow(self, context):
        return list(self.masqueraded(context))

    def visible(self, context):
        for node in self.masqueraded(context):
            if node.visible(context):
                return True
        return False

    def valid(self, context):
        for node in self.masqueraded(context):
            if node.valid(context):
                return True
        return False


class Defaults(Masquerade):
    """Set variables in a branch.

    This is primarily useful in XML grammars.

    >>> from cly import *
    >>> parser = Parser(Grammar(Defaults(foo=10, bar=20)(baz=Node())))
    >>> parser.parse('baz').vars
    {'foo': 10, 'bar': 20}

    In an XML grammar, all attributes are evaluated. This means that strings
    must be double quoted.
    """
    vars = ''
    unset = ''

    def __init__(self, **kwargs):
        super(Defaults, self).__init__()
        self.vars = kwargs

    def follow(self, context):
        context.vars.update(self.vars)
        return super(Defaults, self).follow(context)

    @classmethod
    def cast_attribute(cls, namespace, name, value):
        return eval(value), {}


class