class Attrs(tuple):
    """Immutable sequence type that stores the attributes of an element.
    
    Ordering of the attributes is preserved, while access by name is also
    supported.
    
    >>> attrs = Attrs([('href', '#'), ('title', 'Foo')])
    >>> attrs
    Attrs([('href', '#'), ('title', 'Foo')])
    
    >>> 'href' in attrs
    True
    >>> 'tabindex' in attrs
    False
    >>> attrs.get('title')
    'Foo'
    
    Instances may not be manipulated directly. Instead, the operators ``|`` and
    ``-`` can be used to produce new instances that have specific attributes
    added, replaced or removed.
    
    To remove an attribute, use the ``-`` operator. The right hand side can be
    either a string or a set/sequence of strings, identifying the name(s) of
    the attribute(s) to remove:
    
    >>> attrs - 'title'
    Attrs([('href', '#')])
    >>> attrs - ('title', 'href')
    Attrs()
    
    The original instance is not modified, but the operator can of course be
    used with an assignment:

    >>> attrs
    Attrs([('href', '#'), ('title', 'Foo')])
    >>> attrs -= 'title'
    >>> attrs
    Attrs([('href', '#')])
    
    To add a new attribute, use the ``|`` operator, where the right hand value
    is a sequence of ``(name, value)`` tuples (which includes `Attrs`
    instances):
    
    >>> attrs | [('title', 'Bar')]
    Attrs([('href', '#'), ('title', 'Bar')])
    
    If the attributes already contain an attribute with a given name, the value
    of that attribute is replaced:
    
    >>> attrs | [('href', 'http://example.org/')]
    Attrs([('href', 'http://example.org/')])
    """
    __slots__ = []

    def __contains__(self, name):
        """Return whether the list includes an attribute with the specified
        name.
        
        :return: `True` if the list includes the attribute
        :rtype: `bool`
        """
        for attr, _ in self:
            if attr == name:
                return True

    def __getitem__(self, i):
        """Return an item or slice of the attributes list.
        
        >>> attrs = Attrs([('href', '#'), ('title', 'Foo')])
        >>> attrs[1]
        ('title', 'Foo')
        >>> attrs[1:]
        Attrs([('title', 'Foo')])
        """
        items = tuple.__getitem__(self, i)
        if type(i) is slice:
            return Attrs(items)
        return items

    def __getslice__(self, i, j):
        """Return a slice of the attributes list.
        
        >>> attrs = Attrs([('href', '#'), ('title', 'Foo')])
        >>> attrs[1:]
        Attrs([('title', 'Foo')])
        """
        return Attrs(tuple.__getslice__(self, i, j))

    def __or__(self, attrs):
        """Return a new instance that contains the attributes in `attrs` in
        addition to any already existing attributes. Any attributes in the new
        set that have a value of `None` are removed.
        
        :return: a new instance with the merged attributes
        :rtype: `Attrs`
        """
        remove = set([an for an, av in attrs if av is None])
        replace = dict([(an, av) for an, av in attrs
                        if an in self and av is not None])
        return Attrs([(sn, replace.get(sn, sv)) for sn, sv in self
                      if sn not in remove] +
                     [(an, av) for an, av in attrs
                      if an not in self and an not in remove])

    def __repr__(self):
        if not self:
            return 'Attrs()'
        return 'Attrs([%s])' % ', '.join([repr(item) for item in self])

    def __sub__(self, names):
        """Return a new instance with all attributes with a name in `names` are
        removed.
        
        :param names: the names of the attributes to remove
        :return: a new instance with the attribute removed
        :rtype: `Attrs`
        """
        if isinstance(names, basestring):
            names = (names,)
        return Attrs([(name, val) for name, val in self if name not in names])

    def get(self, name, default=None):
        """Return the value of the attribute with the specified name, or the
        value of the `default` parameter if no such attribute is found.
        
        :param name: the name of the attribute
        :param default: the value to return when the attribute does not exist
        :return: the attribute value, or the `default` value if that attribute
                 does not exist
        :rtype: `object`
        """
        for attr, value in self:
            if attr == name:
                return value
        return default

    def totuple(self):
        """Return the attributes as a markup event.
        
        The returned event is a `TEXT` event, the data is the value of all
        attributes joined together.
        
        >>> Attrs([('href', '#'), ('title', 'Foo')]).totuple()
        ('TEXT', '#Foo', (None, -1, -1))
        
        :return: a `TEXT` event
        :rtype: `tuple`
        """
        return TEXT, ''.join([x[1] for x in self]), (None, -1, -1) class Markup(unicode):
    """Marks a string as being safe for inclusion in HTML/XML output without
    needing to be escaped.
    """
    __slots__ = []

    def __add__(self, other):
        return Markup(unicode.__add__(self, escape(other)))

    def __radd__(self, other):
        return Markup(unicode.__add__(escape(other), self))

    def __mod__(self, args):
        if isinstance(args, dict):
            args = dict(zip(args.keys(), map(escape, args.values())))
        elif isinstance(args, (list, tuple)):
            args = tuple(map(escape, args))
        else:
            args = escape(args)
        return Markup(unicode.__mod__(self, args))

    def __mul__(self, num):
        return Markup(unicode.__mul__(self, num))
    __rmul__ = __mul__

    def __repr__(self):
        return "<%s %s>" % (type(self).__name__, unicode.__repr__(self))

    def join(self, seq, escape_quotes=True):
        """Return a `Markup` object which is the concatenation of the strings
        in the given sequence, where this `Markup` object is the separator
        between the joined elements.
        
        Any element in the sequence that is not a `Markup` instance is
        automatically escaped.
        
        :param seq: the sequence of strings to join
        :param escape_quotes: whether double quote characters in the elements
                              should be escaped
        :return: the joined `Markup` object
        :rtype: `Markup`
        :see: `escape`
        """
        return Markup(unicode.join(self, [escape(item, quotes=escape_quotes)
                                          for item in seq]))

    @classmethod
    def escape(cls, text, quotes=True):
        """Create a Markup instance from a string and escape special characters
        it may contain (<, >, & and \").
        
        >>> escape('"1 < 2"')
        <Markup u'&#34;1 &lt; 2&#34;'>
        
        If the `quotes` parameter is set to `False`, the \" character is left
        as is. Escaping quotes is generally only required for strings that are
        to be used in attribute values.
        
        >>> escape('"1 < 2"', quotes=False)
        <Markup u'"1 &lt; 2"'>
        
        :param text: the text to escape
        :param quotes: if ``True``, double quote characters are escaped in
                       addition to the other special characters
        :return: the escaped `Markup` string
        :rtype: `Markup`
        """
        if not text:
            return cls()
        if type(text) is cls:
            return text
        if hasattr(text, '__html__'):
            return cls(text.__html__())

        text = text.replace('&', '&amp;') \
                   .replace('<', '&lt;') \
                   .replace('>', '&gt;')
        if quotes:
            text = text.replace('"', '&#34;')
        return cls(text)

    def unescape(self):
        """Reverse-escapes &, <, >, and \" and returns a `unicode` object.
        
        >>> Markup('1 &lt; 2').unescape()
        u'1 < 2'
        
        :return: the unescaped string
        :rtype: `unicode`
        :see: `genshi.core.unescape`
        """
        if not self:
            return ''
        return unicode(self).replace('&#34;', '"') \
                            .replace('&gt;', '>') \
                            .replace('&lt;', '<') \
                            .replace('&amp;', '&')

    def stripentities(self, keepxmlentities=False):
        """Return a copy of the text with any character or numeric entities
        replaced by the equivalent UTF-8 characters.
        
        If the `keepxmlentities` parameter is provided and evaluates to `True`,
        the core XML entities (``&amp;``, ``&apos;``, ``&gt;``, ``&lt;`` and
        ``&quot;``) are not stripped.
        
        :return: a `Markup` instance with entities removed
        :rtype: `Markup`
        :see: `genshi.util.stripentities`
        """
        return Markup(stripentities(self, keepxmlentities=keepxmlentities))

    def striptags(self):
        """Return a copy of the text with all XML/HTML tags removed.
        
        :return: a `Markup` instance with all tags removed
        :rtype: `Markup`
        :see: `genshi.util.striptags`
        """
        return Markup(striptags(self)) class Namespace(object):
    """Utility class creating and testing elements with a namespace.
    
    Internally, namespace URIs are encoded in the `QName` of any element or
    attribute, the namespace URI being enclosed in curly braces. This class
    helps create and test these strings.
    
    A `Namespace` object is instantiated with the namespace URI.
    
    >>> html = Namespace('http://www.w3.org/1999/xhtml')
    >>> html
    Namespace('http://www.w3.org/1999/xhtml')
    >>> html.uri
    u'http://www.w3.org/1999/xhtml'
    
    The `Namespace` object can than be used to generate `QName` objects with
    that namespace:
    
    >>> html.body
    QName('http://www.w3.org/1999/xhtml}body')
    >>> html.body.localname
    u'body'
    >>> html.body.namespace
    u'http://www.w3.org/1999/xhtml'
    
    The same works using item access notation, which is useful for element or
    attribute names that are not valid Python identifiers:
    
    >>> html['body']
    QName('http://www.w3.org/1999/xhtml}body')
    
    A `Namespace` object can also be used to test whether a specific `QName`
    belongs to that namespace using the ``in`` operator:
    
    >>> qname = html.body
    >>> qname in html
    True
    >>> qname in Namespace('http://www.w3.org/2002/06/xhtml2')
    False
    """
    def __new__(cls, uri):
        if type(uri) is cls:
            return uri
        return object.__new__(cls)

    def __getnewargs__(self):
        return (self.uri,)

    def __getstate__(self):
        return self.uri

    def __setstate__(self, uri):
        self.uri = uri

    def __init__(self, uri):
        self.uri = unicode(uri)

    def __contains__(self, qname):
        return qname.namespace == self.uri

    def __ne__(self, other):
        return not self == other

    def __eq__(self, other):
        if isinstance(other, Namespace):
            return self.uri == other.uri
        return self.uri == other

    def __getitem__(self, name):
        return QName(self.uri + '}' + name)
    __getattr__ = __getitem__

    def __hash__(self):
        return hash(self.uri)

    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, stringrepr(self.uri))

    def __str__(self):
        return self.uri.encode('utf-8')

    def __unicode__(self):
        return self.uri class Stream(object):
    """Represents a stream of markup events.
    
    This class is basically an iterator over the events.
    
    Stream events are tuples of the form::
    
      (kind, data, position)
    
    where ``kind`` is the event kind (such as `START`, `END`, `TEXT`, etc),
    ``data`` depends on the kind of event, and ``position`` is a
    ``(filename, line, offset)`` tuple that contains the location of the
    original element or text in the input. If the original location is unknown,
    ``position`` is ``(None, -1, -1)``.
    
    Also provided are ways to serialize the stream to text. The `serialize()`
    method will return an iterator over generated strings, while `render()`
    returns the complete generated text at once. Both accept various parameters
    that impact the way the stream is serialized.
    """
    __slots__ = ['events', 'serializer']

    START = StreamEventKind('START') #: a start tag
    END = StreamEventKind('END') #: an end tag
    TEXT = StreamEventKind('TEXT') #: literal text
    XML_DECL = StreamEventKind('XML_DECL') #: XML declaration
    DOCTYPE = StreamEventKind('DOCTYPE') #: doctype declaration
    START_NS = StreamEventKind('START_NS') #: start namespace mapping
    END_NS = StreamEventKind('END_NS') #: end namespace mapping
    START_CDATA = StreamEventKind('START_CDATA') #: start CDATA section
    END_CDATA = StreamEventKind('END_CDATA') #: end CDATA section
    PI = StreamEventKind('PI') #: processing instruction
    COMMENT = StreamEventKind('COMMENT') #: comment

    def __init__(self, events, serializer=None):
        """Initialize the stream with a sequence of markup events.
        
        :param events: a sequence or iterable providing the events
        :param serializer: the default serialization method to use for this
                           stream

        :note: Changed in 0.5: added the `serializer` argument
        """
        self.events = events #: The underlying iterable producing the events
        self.serializer = serializer #: The default serializion method

    def __iter__(self):
        return iter(self.events)

    def __or__(self, function):
        """Override the "bitwise or" operator to apply filters or serializers
        to the stream, providing a syntax similar to pipes on Unix shells.
        
        Assume the following stream produced by the `HTML` function:
        
        >>> from genshi.input import HTML
        >>> html = HTML('''<p onclick="alert('Whoa')">Hello, world!</p>''')
        >>> print(html)
        <p onclick="alert('Whoa')">Hello, world!</p>
        
        A filter such as the HTML sanitizer can be applied to that stream using
        the pipe notation as follows:
        
        >>> from genshi.filters import HTMLSanitizer
        >>> sanitizer = HTMLSanitizer()
        >>> print(html | sanitizer)
        <p>Hello, world!</p>
        
        Filters can be any function that accepts and produces a stream (where
        a stream is anything that iterates over events):
        
        >>> def uppercase(stream):
        ...     for kind, data, pos in stream:
        ...         if kind is TEXT:
        ...             data = data.upper()
        ...         yield kind, data, pos
        >>> print(html | sanitizer | uppercase)
        <p>HELLO, WORLD!</p>
        
        Serializers can also be used with this notation:
        
        >>> from genshi.output import TextSerializer
        >>> output = TextSerializer()
        >>> print(html | sanitizer | uppercase | output)
        HELLO, WORLD!
        
        Commonly, serializers should be used at the end of the "pipeline";
        using them somewhere in the middle may produce unexpected results.
        
        :param function: the callable object that should be applied as a filter
        :return: the filtered stream
        :rtype: `Stream`
        """
        return Stream(_ensure(function(self)), serializer=self.serializer)

    def filter(self, *filters):
        """Apply filters to the stream.
        
        This method returns a new stream with the given filters applied. The
        filters must be callables that accept the stream object as parameter,
        and return the filtered stream.
        
        The call::
        
            stream.filter(filter1, filter2)
        
        is equivalent to::
        
            stream | filter1 | filter2
        
        :param filters: one or more callable objects that should be applied as
                        filters
        :return: the filtered stream
        :rtype: `Stream`
        """
        return reduce(operator.or_, (self,) + filters)

    def render(self, method=None, encoding='utf-8', out=None, **kwargs):
        """Return a string representation of the stream.
        
        Any additional keyword arguments are passed to the serializer, and thus
        depend on the `method` parameter value.
        
        :param method: determines how the stream is serialized; can be either
                       "xml", "xhtml", "html", "text", or a custom serializer
                       class; if `None`, the default serialization method of
                       the stream is used
        :param encoding: how the output string should be encoded; if set to
                         `None`, this method returns a `unicode` object
        :param out: a file-like object that the output should be written to
                    instead of being returned as one big string; note that if
                    this is a file or socket (or similar), the `encoding` must
                    not be `None` (that is, the output must be encoded)
        :return: a `str` or `unicode` object (depending on the `encoding`
                 parameter), or `None` if the `out` parameter is provided
        :rtype: `basestring`
        
        :see: XMLSerializer, XHTMLSerializer, HTMLSerializer, TextSerializer
        :note: Changed in 0.5: added the `out` parameter
        """
        from genshi.output import encode
        if method is None:
            method = self.serializer or 'xml'
        generator = self.serialize(method=method, **kwargs)
        return encode(generator, method=method, encoding=encoding, out=out)

    def select(self, path, namespaces=None, variables=None):
        """Return a new stream that contains the events matching the given
        XPath expression.
        
        >>> from genshi import HTML
        >>> stream = HTML('<doc><elem>foo</elem><elem>bar</elem></doc>')
        >>> print(stream.select('elem'))
        <elem>foo</elem><elem>bar</elem>
        >>> print(stream.select('elem/text()'))
        foobar
        
        Note that the outermost element of the stream becomes the *context
        node* for the XPath test. That means that the expression "doc" would
        not match anything in the example above, because it only tests against
        child elements of the outermost element:
        
        >>> print(stream.select('doc'))
        <BLANKLINE>
        
        You can use the "." expression to match the context node itself
        (although that usually makes little sense):
        
        >>> print(stream.select('.'))
        <doc><elem>foo</elem><elem>bar</elem></doc>
        
        :param path: a string containing the XPath expression
        :param namespaces: mapping of namespace prefixes used in the path
        :param variables: mapping of variable names to values
        :return: the selected substream
        :rtype: `Stream`
        :raises PathSyntaxError: if the given path expression is invalid or not
                                 supported
        """
        from genshi.path import Path
        return Path(path).select(self, namespaces, variables)

    def serialize(self, method='xml', **kwargs):
        """Generate strings corresponding to a specific serialization of the
        stream.
        
        Unlike the `render()` method, this method is a generator that returns
        the serialized output incrementally, as opposed to returning a single
        string.
        
        Any additional keyword arguments are passed to the serializer, and thus
        depend on the `method` parameter value.
        
        :param method: determines how the stream is serialized; can be either
                       "xml", "xhtml", "html", "text", or a custom serializer
                       class; if `None`, the default serialization method of
                       the stream is used
        :return: an iterator over the serialization results (`Markup` or
                 `unicode` objects, depending on the serialization method)
        :rtype: ``iterator``
        :see: XMLSerializer, XHTMLSerializer, HTMLSerializer, TextSerializer
        """
        from genshi.output import get_serializer
        if method is None:
            method = self.serializer or 'xml'
        return get_serializer(method, **kwargs)(_ensure(self))

    def __str__(self):
        return self.render()

    def __unicode__(self):
        return self.render(encoding=None)

    def __html__(self):
        return self class StreamEventKind(str):
    """A kind of event on a markup stream."""
    __slots__ = []
    _instances = {}

    def __new__(cls, val):
        return cls._instances.setdefault(val, str.__new__(cls, val)) START = StreamEventKind('START') #: a start tag END = StreamEventKind('END') #: an end tag START_NS = StreamEventKind('START_NS') #: start namespace mapping END_NS = StreamEventKind('END_NS') #: end namespace mapping TEXT = StreamEventKind('TEXT') #: literal text PI = StreamEventKind('PI') #: processing instruction COMMENT = StreamEventKind('COMMENT') #: comment class XMLParser(object):
    """Generator-based XML parser based on roughly equivalent code in
    Kid/ElementTree.
    
    The parsing is initiated by iterating over the parser object:
    
    >>> parser = XMLParser(StringIO('<root id="2"><child>Foo</child></root>'))
    >>> for kind, data, pos in parser:
    ...     print('%s %s' % (kind, data))
    START (QName('root'), Attrs([(QName('id'), u'2')]))
    START (QName('child'), Attrs())
    TEXT Foo
    END child
    END root
    """

    _entitydefs = ['<!ENTITY %s "&#%d;">' % (name, value) for name, value in
                   entities.name2codepoint.items()]
    _external_dtd = '\n'.join(_entitydefs)

    def __init__(self, source, filename=None, encoding=None):
        """Initialize the parser for the given XML input.
        
        :param source: the XML text as a file-like object
        :param filename: the name of the file, if appropriate
        :param encoding: the encoding of the file; if not specified, the
                         encoding is assumed to be ASCII, UTF-8, or UTF-16, or
                         whatever the encoding specified in the XML declaration
                         (if any)
        """
        self.source = source
        self.filename = filename

        # Setup the Expat parser
        parser = expat.ParserCreate(encoding, '}')
        parser.buffer_text = True
        parser.returns_unicode = True
        parser.ordered_attributes = True

        parser.StartElementHandler = self._handle_start
        parser.EndElementHandler = self._handle_end
        parser.CharacterDataHandler = self._handle_data
        parser.StartDoctypeDeclHandler = self._handle_doctype
        parser.StartNamespaceDeclHandler = self._handle_start_ns
        parser.EndNamespaceDeclHandler = self._handle_end_ns
        parser.StartCdataSectionHandler = self._handle_start_cdata
        parser.EndCdataSectionHandler = self._handle_end_cdata
        parser.ProcessingInstructionHandler = self._handle_pi
        parser.XmlDeclHandler = self._handle_xml_decl
        parser.CommentHandler = self._handle_comment

        # Tell Expat that we'll handle non-XML entities ourselves
        # (in _handle_other)
        parser.DefaultHandler = self._handle_other
        parser.SetParamEntityParsing(expat.XML_PARAM_ENTITY_PARSING_ALWAYS)
        parser.UseForeignDTD()
        parser.ExternalEntityRefHandler = self._build_foreign

        self.expat = parser
        self._queue = []

    def parse(self):
        """Generator that parses the XML source, yielding markup events.
        
        :return: a markup event stream
        :raises ParseError: if the XML text is not well formed
        """
        def _generate():
            try:
                bufsize = 4 * 1024 # 4K
                done = False
                while 1:
                    while not done and len(self._queue) == 0:
                        data = self.source.read(bufsize)
                        if data == '': # end of data
                            if hasattr(self, 'expat'):
                                self.expat.Parse('', True)
                                del self.expat # get rid of circular references
                            done = True
                        else:
                            if isinstance(data, unicode):
                                data = data.encode('utf-8')
                            self.expat.Parse(data, False)
                    for event in self._queue:
                        yield event
                    self._queue = []
                    if done:
                        break
            except expat.ExpatError, e:
                msg = str(e)
                raise ParseError(msg, self.filename, e.lineno, e.offset)
        return Stream(_generate()).filter(_coalesce)

    def __iter__(self):
        return iter(self.parse())

    def _build_foreign(self, context, base, sysid, pubid):
        parser = self.expat.ExternalEntityParserCreate(context)
        parser.ParseFile(StringIO(self._external_dtd))
        return 1

    def _enqueue(self, kind, data=None, pos=None):
        if pos is None:
            pos = self._getpos()
        if kind is TEXT:
            # Expat reports the *end* of the text event as current position. We
            # try to fix that up here as much as possible. Unfortunately, the
            # offset is only valid for single-line text. For multi-line text,
            # it is apparently not possible to determine at what offset it
            # started
            if '\n' in data:
                lines = data.splitlines()
                lineno = pos[1] - len(lines) + 1
                offset = -1
            else:
                lineno = pos[1]
                offset = pos[2] - len(data)
            pos = (pos[0], lineno, offset)
        self._queue.append((kind, data, pos))

    def _getpos_unknown(self):
        return (self.filename, -1, -1)

    def _getpos(self):
        return (self.filename, self.expat.CurrentLineNumber,
                self.expat.CurrentColumnNumber)

    def _handle_start(self, tag, attrib):
        attrs = Attrs([(QName(name), value) for name, value in
                       zip(*[iter(attrib)] * 2)])
        self._enqueue(START, (QName(tag), attrs))

    def _handle_end(self, tag):
        self._enqueue(END, QName(tag))

    def _handle_data(self, text):
        self._enqueue(TEXT, text)

    def _handle_xml_decl(self, version, encoding, standalone):
        self._enqueue(XML_DECL, (version, encoding, standalone))

    def _handle_doctype(self, name, sysid, pubid, has_internal_subset):
        self._enqueue(DOCTYPE, (name, pubid, sysid))

    def _handle_start_ns(self, prefix, uri):
        self._enqueue(START_NS, (prefix or '', uri))

    def _handle_end_ns(self, prefix):
        self._enqueue(END_NS, prefix or '')

    def _handle_start_cdata(self):
        self._enqueue(START_CDATA)

    def _handle_end_cdata(self):
        self._enqueue(END_CDATA)

    def _handle_pi(self, target, data):
        self._enqueue(PI, (target, data))

    def _handle_comment(self, text):
        self._enqueue(COMMENT, text)

    def _handle_other(self, text):
        if text.startswith('&'):
            # deal with undefined entities
            try:
                text = unichr(entities.name2codepoint[text[1:-1]])
                self._enqueue(TEXT, text)
            except KeyError:
                filename, lineno, offset = self._getpos()
                error = expat.error('undefined entity "%s": line %d, column %d'
                                    % (text, lineno, offset))
                error.code = expat.errors.XML_ERROR_UNDEFINED_ENTITY
                error.lineno = lineno
                error.offset = offset
                raise error class BadDirectiveError(TemplateSyntaxError):
    """Exception raised when an unknown directive is encountered when parsing
    a template.
    
    An unknown directive is any attribute using the namespace for directives,
    with a local name that doesn't match any registered directive.
    """

    def __init__(self, name, filename=None, lineno=-1):
        """Create the exception
        
        :param name: the name of the directive
        :param filename: the filename of the template
        :param lineno: the number of line in the template at which the error
                       occurred
        """
        TemplateSyntaxError.__init__(self, 'bad directive "%s"' % name,
                                     filename, lineno) class Template(DirectiveFactory):
    """Abstract template base class.
    
    This class implements most of the template processing model, but does not
    specify the syntax of templates.
    """

    EXEC = StreamEventKind('EXEC')
    """Stream event kind representing a Python code suite to execute."""

    EXPR = StreamEventKind('EXPR')
    """Stream event kind representing a Python expression."""

    INCLUDE = StreamEventKind('INCLUDE')
    """Stream event kind representing the inclusion of another template."""

    SUB = StreamEventKind('SUB')
    """Stream event kind representing a nested stream to which one or more
    directives should be applied.
    """

    serializer = None
    _number_conv = unicode # function used to convert numbers to event data

    def __init__(self, source, filepath=None, filename=None, loader=None,
                 encoding=None, lookup='strict', allow_exec=True):
        """Initialize a template from either a string, a file-like object, or
        an already parsed markup stream.
        
        :param source: a string, file-like object, or markup stream to read the
                       template from
        :param filepath: the absolute path to the template file
        :param filename: the path to the template file relative to the search
                         path
        :param loader: the `TemplateLoader` to use for loading included
                       templates
        :param encoding: the encoding of the `source`
        :param lookup: the variable lookup mechanism; either "strict" (the
                       default), "lenient", or a custom lookup class
        :param allow_exec: whether Python code blocks in templates should be
                           allowed
        
        :note: Changed in 0.5: Added the `allow_exec` argument
        """
        self.filepath = filepath or filename
        self.filename = filename
        self.loader = loader
        self.lookup = lookup
        self.allow_exec = allow_exec
        self._init_filters()
        self._init_loader()
        self._prepared = False

        if isinstance(source, basestring):
            source = StringIO(source)
        else:
            source = source
        try:
            self._stream = self._parse(source, encoding)
        except ParseError, e:
            raise TemplateSyntaxError(e.msg, self.filepath, e.lineno, e.offset)

    def __getstate__(self):
        state = self.__dict__.copy()
        state['filters'] = []
        return state

    def __setstate__(self, state):
        self.__dict__ = state
        self._init_filters()

    def __repr__(self):
        return '<%s "%s">' % (type(self).__name__, self.filename)

    def _init_filters(self):
        self.filters = [self._flatten, self._include]

    def _init_loader(self):
        if self.loader is None:
            from genshi.template.loader import TemplateLoader
            if self.filename:
                if self.filepath != self.filename:
                    basedir = os.path.normpath(self.filepath)[:-len(
                        os.path.normpath(self.filename))
                    ]
                else:
                    basedir = os.path.dirname(self.filename)
            else:
                basedir = '.'
            self.loader = TemplateLoader([os.path.abspath(basedir)])

    @property
    def stream(self):
        if not self._prepared:
            self._stream = list(self._prepare(self._stream))
            self._prepared = True
        return self._stream

    def _parse(self, source, encoding):
        """Parse the template.
        
        The parsing stage parses the template and constructs a list of
        directives that will be executed in the render stage. The input is
        split up into literal output (text that does not depend on the context
        data) and directives or expressions.
        
        :param source: a file-like object containing the XML source of the
                       template, or an XML event stream
        :param encoding: the encoding of the `source`
        """
        raise NotImplementedError

    def _prepare(self, stream):
        """Call the `attach` method of every directive found in the template.
        
        :param stream: the event stream of the template
        """
        from genshi.template.loader import TemplateNotFound

        for kind, data, pos in stream:
            if kind is SUB:
                directives = []
                substream = data[1]
                for _, cls, value, namespaces, pos in sorted(data[0]):
                    directive, substream = cls.attach(self, substream, value,
                                                      namespaces, pos)
                    if directive:
                        directives.append(directive)
                substream = self._prepare(substream)
                if directives:
                    yield kind, (directives, list(substream)), pos
                else:
                    for event in substream:
                        yield event
            else:
                if kind is INCLUDE:
                    href, cls, fallback = data
                    if isinstance(href, basestring) and \
                            not getattr(self.loader, 'auto_reload', True):
                        # If the path to the included template is static, and
                        # auto-reloading is disabled on the template loader,
                        # the template is inlined into the stream
                        try:
                            tmpl = self.loader.load(href, relative_to=pos[0],
                                                    cls=cls or self.__class__)
                            for event in tmpl.stream:
                                yield event
                        except TemplateNotFound:
                            if fallback is None:
                                raise
                            for event in self._prepare(fallback):
                                yield event
                        continue
                    elif fallback:
                        # Otherwise the include is performed at run time
                        data = href, cls, list(self._prepare(fallback))

                yield kind, data, pos

    def generate(self, *args, **kwargs):
        """Apply the template to the given context data.
        
        Any keyword arguments are made available to the template as context
        data.
        
        Only one positional argument is accepted: if it is provided, it must be
        an instance of the `Context` class, and keyword arguments are ignored.
        This calling style is used for internal processing.
        
        :return: a markup event stream representing the result of applying
                 the template to the context data.
        """
        vars = {}
        if args:
            assert len(args) == 1
            ctxt = args[0]
            if ctxt is None:
                ctxt = Context(**kwargs)
            else:
                vars = kwargs
            assert isinstance(ctxt, Context)
        else:
            ctxt = Context(**kwargs)

        stream = self.stream
        for filter_ in self.filters:
            stream = filter_(iter(stream), ctxt, **vars)
        return Stream(stream, self.serializer)

    def _flatten(self, stream, ctxt, **vars):
        number_conv = self._number_conv
        stack = []
        push = stack.append
        pop = stack.pop
        stream = iter(stream)

        while 1:
            for kind, data, pos in stream:

                if kind is START and data[1]:
                    # Attributes may still contain expressions in start tags at
                    # this point, so do some evaluation
                    tag, attrs = data
                    new_attrs = []
                    for name, value in attrs:
                        if type(value) is list: # this is an interpolated string
                            values = [event[1]
                                for event in self._flatten(value, ctxt, **vars)
                                if event[0] is TEXT and event[1] is not None
                            ]
                            if not values:
                                continue
                            value = ''.join(values)
                        new_attrs.append((name, value))
                    yield kind, (tag, Attrs(new_attrs)), pos

                elif kind is EXPR:
                    result = _eval_expr(data, ctxt, vars)
                    if result is not None:
                        # First check for a string, otherwise the iterable test
                        # below succeeds, and the string will be chopped up into
                        # individual characters
                        if isinstance(result, basestring):
                            yield TEXT, result, pos
                        elif isinstance(result, (int, float, long)):
                            yield TEXT, number_conv(result), pos
                        elif hasattr(result, '__iter__'):
                            push(stream)
                            stream = _ensure(result)
                            break
                        else:
                            yield TEXT, unicode(result), pos

                elif kind is SUB:
                    # This event is a list of directives and a list of nested
                    # events to which those directives should be applied
                    push(stream)
                    stream = _apply_directives(data[1], data[0], ctxt, vars)
                    break

                elif kind is EXEC:
                    _exec_suite(data, ctxt, vars)

                else:
                    yield kind, data, pos

            else:
                if not stack:
                    break
                stream = pop()

    def _include(self, stream, ctxt, **vars):
        """Internal stream filter that performs inclusion of external
        template files.
        """
        from genshi.template.loader import TemplateNotFound

        for event in stream:
            if event[0] is INCLUDE:
                href, cls, fallback = event[1]
                if not isinstance(href, basestring):
                    parts = []
                    for subkind, subdata, subpos in self._flatten(href, ctxt,
                                                                  **vars):
                        if subkind is TEXT:
                            parts.append(subdata)
                    href = ''.join([x for x in parts if x is not None])
                try:
                    tmpl = self.loader.load(href, relative_to=event[2][0],
                                            cls=cls or self.__class__)
                    for event in tmpl.generate(ctxt, **vars):
                        yield event
                except TemplateNotFound:
                    if fallback is None:
                        raise
                    for filter_ in self.filters:
                        fallback = filter_(iter(fallback), ctxt, **vars)
                    for event in fallback:
                        yield event
            else:
                yield event class TemplateSyntaxError(TemplateError):
    """Exception raised when an expression in a template causes a Python syntax
    error, or the template is not well-formed.
    """

    def __init__(self, message, filename=None, lineno=-1, offset=-1):
        """Create the exception
        
        :param message: the error message
        :param filename: the filename of the template
        :param lineno: the number of line in the template at which the error
                       occurred
        :param offset: the column number at which the error occurred
        """
        if isinstance(message, SyntaxError) and message.lineno is not None:
            message = str(message).replace(' (line %d)' % message.lineno, '')
        TemplateError.__init__(self, message, filename, lineno) def _apply_directives(stream, directives, ctxt, vars):
    """Apply the given directives to the stream.
    
    :param stream: the stream the directives should be applied to
    :param directives: the list of directives to apply
    :param ctxt: the `Context`
    :param vars: additional variables that should be available when Python
                 code is executed
    :return: the stream with the given directives applied
    """
    if directives:
        stream = directives[0](iter(stream), directives[1:], ctxt, **vars)
    return stream EXEC = StreamEventKind('EXEC') INCLUDE = StreamEventKind('INCLUDE') SUB = StreamEventKind('SUB') class Suite(Code):
    """Executes Python statements used in templates.

    >>> data = dict(test='Foo', items=[1, 2, 3], dict={'some': 'thing'})
    >>> Suite("foo = dict['some']").execute(data)
    >>> data['foo']
    'thing'
    """
    __slots__ = []
    mode = 'exec'

    def execute(self, data):
        """Execute the suite in the given data dictionary.
        
        :param data: a mapping containing the data to execute in
        """
        __traceback_hide__ = 'before_and_this'
        _globals = self._globals(data)
        exec self.code in _globals, data class NewTextTemplate(Template):
    r"""Implementation of a simple text-based template engine. This class will
    replace `OldTextTemplate` in a future release.
    
    It uses a more explicit delimiting style for directives: instead of the old
    style which required putting directives on separate lines that were prefixed
    with a ``#`` sign, directives and commenbtsr are enclosed in delimiter pairs
    (by default ``{% ... %}`` and ``{# ... #}``, respectively).
    
    Variable substitution uses the same interpolation syntax as for markup
    languages: simple references are prefixed with a dollar sign, more complex
    expression enclosed in curly braces.
    
    >>> tmpl = NewTextTemplate('''Dear $name,
    ... 
    ... {# This is a comment #}
    ... We have the following items for you:
    ... {% for item in items %}
    ...  * ${'Item %d' % item}
    ... {% end %}
    ... ''')
    >>> print(tmpl.generate(name='Joe', items=[1, 2, 3]).render(encoding=None))
    Dear Joe,
    <BLANKLINE>
    <BLANKLINE>
    We have the following items for you:
    <BLANKLINE>
     * Item 1
    <BLANKLINE>
     * Item 2
    <BLANKLINE>
     * Item 3
    <BLANKLINE>
    <BLANKLINE>
    
    By default, no spaces or line breaks are removed. If a line break should
    not be included in the output, prefix it with a backslash:
    
    >>> tmpl = NewTextTemplate('''Dear $name,
    ... 
    ... {# This is a comment #}\
    ... We have the following items for you:
    ... {% for item in items %}\
    ...  * $item
    ... {% end %}\
    ... ''')
    >>> print(tmpl.generate(name='Joe', items=[1, 2, 3]).render(encoding=None))
    Dear Joe,
    <BLANKLINE>
    We have the following items for you:
     * 1
     * 2
     * 3
    <BLANKLINE>
    
    Backslashes are also used to escape the start delimiter of directives and
    comments:

    >>> tmpl = NewTextTemplate('''Dear $name,
    ... 
    ... \{# This is a comment #}
    ... We have the following items for you:
    ... {% for item in items %}\
    ...  * $item
    ... {% end %}\
    ... ''')
    >>> print(tmpl.generate(name='Joe', items=[1, 2, 3]).render(encoding=None))
    Dear Joe,
    <BLANKLINE>
    {# This is a comment #}
    We have the following items for you:
     * 1
     * 2
     * 3
    <BLANKLINE>
    
    :since: version 0.5
    """
    directives = [('def', DefDirective),
                  ('when', WhenDirective),
                  ('otherwise', OtherwiseDirective),
                  ('for', ForDirective),
                  ('if', IfDirective),
                  ('choose', ChooseDirective),
                  ('with', WithDirective)]
    serializer = 'text'

    _DIRECTIVE_RE = r'((?<!\\)%s\s*(\w+)\s*(.*?)\s*%s|(?<!\\)%s.*?%s)'
    _ESCAPE_RE = r'\\\n|\\(\\)|\\(%s)|\\(%s)'

    def __init__(self, source, filepath=None, filename=None, loader=None,
                 encoding=None, lookup='strict', allow_exec=False,
                 delims=('{%', '%}', '{#', '#}')):
        self.delimiters = delims
        Template.__init__(self, source, filepath=filepath, filename=filename,
                          loader=loader, encoding=encoding, lookup=lookup)

    def _get_delims(self):
        return self._delims
    def _set_delims(self, delims):
        if len(delims) != 4:
            raise ValueError('delimiers tuple must have exactly four elements')
        self._delims = delims
        self._directive_re = re.compile(self._DIRECTIVE_RE % tuple(
            [re.escape(d) for d in delims]
        ), re.DOTALL)
        self._escape_re = re.compile(self._ESCAPE_RE % tuple(
            [re.escape(d) for d in delims[::2]]
        ))
    delimiters = property(_get_delims, _set_delims, """\
    The delimiters for directives and comments. This should be a four item tuple
    of the form ``(directive_start, directive_end, comment_start,
    comment_end)``, where each item is a string.
    """)

    def _parse(self, source, encoding):
        """Parse the template from text input."""
        stream = [] # list of events of the "compiled" template
        dirmap = {} # temporary mapping of directives to elements
        depth = 0

        source = source.read()
        if isinstance(source, str):
            source = source.decode(encoding or 'utf-8', 'replace')
        offset = 0
        lineno = 1

        _escape_sub = self._escape_re.sub
        def _escape_repl(mo):
            groups = [g for g in mo.groups() if g]
            if not groups:
                return ''
            return groups[0]

        for idx, mo in enumerate(self._directive_re.finditer(source)):
            start, end = mo.span(1)
            if start > offset:
                text = _escape_sub(_escape_repl, source[offset:start])
                for kind, data, pos in interpolate(text, self.filepath, lineno,
                                                   lookup=self.lookup):
                    stream.append((kind, data, pos))
                lineno += len(text.splitlines())

            lineno += len(source[start:end].splitlines())
            command, value = mo.group(2, 3)

            if command == 'include':
                pos = (self.filename, lineno, 0)
                value = list(interpolate(value, self.filepath, lineno, 0,
                                         lookup=self.lookup))
                if len(value) == 1 and value[0][0] is TEXT:
                    value = value[0][1]
                stream.append((INCLUDE, (value, None, []), pos))

            elif command == 'python':
                if not self.allow_exec:
                    raise TemplateSyntaxError('Python code blocks not allowed',
                                              self.filepath, lineno)
                try:
                    suite = Suite(value, self.filepath, lineno,
                                  lookup=self.lookup)
                except SyntaxError, err:
                    raise TemplateSyntaxError(err, self.filepath,
                                              lineno + (err.lineno or 1) - 1)
                pos = (self.filename, lineno, 0)
                stream.append((EXEC, suite, pos))

            elif command == 'end':
                depth -= 1
                if depth in dirmap:
                    directive, start_offset = dirmap.pop(depth)
                    substream = stream[start_offset:]
                    stream[start_offset:] = [(SUB, ([directive], substream),
                                              (self.filepath, lineno, 0))]

            elif command:
                cls = self.get_directive(command)
                if cls is None:
                    raise BadDirectiveError(command)
                directive = 0, cls, value, None, (self.filepath, lineno, 0)
                dirmap[depth] = (directive, len(stream))
                depth += 1

            offset = end

        if offset < len(source):
            text = _escape_sub(_escape_repl, source[offset:])
            for kind, data, pos in interpolate(text, self.filepath, lineno,
                                               lookup=self.lookup):
                stream.append((kind, data, pos))

        return stream
from itertools import chain
from genshi.core import Attrs, Markup, Namespace, Stream, StreamEventKind
from genshi.core import START, END, START_NS, END_NS, TEXT, PI, COMMENT
from genshi.input import XMLParser
from genshi.template.base import BadDirectiveError, Template, \
                                 TemplateSyntaxError, _apply_directives, \
                                 EXEC, INCLUDE, SUB
from genshi.template.eval import Suite
from genshi.template.interpolation import interpolate
from genshi.template.directives import *
from genshi.template.text import NewTextTemplate
                depth -= 1
                new_stream.append((kind, data, pos))

                # If there have have directive attributes with the
                # corresponding start tag, move the events inbetween into
                # a "subprogram"
                if (depth, data) in dirmap:
                    directives, offset, strip = dirmap.pop((depth, data))
                    substream = new_stream[offset:]
                    if strip:
                        substream = substream[1:-1]
                    new_stream[offset:] = [
                        (SUB, (directives, substream), pos)
                    ]

            elif kind is SUB:
                directives, substream = data
                substream = self._extract_directives(substream, namespace,
                                                     factory)

                if len(substream) == 1 and substream[0][0] is SUB:
                    added_directives, substream = substream[0][1]
                    directives += added_directives

                new_stream.append((kind, (directives, substream), pos))

            elif kind is START_NS:
                # Strip out the namespace declaration for template
                # directives
                prefix, uri = data
                ns_prefix[prefix] = uri
                if uri != namespace:
                    new_stream.append((kind, data, pos))

            elif kind is END_NS:
                uri = ns_prefix.pop(data, None)
                if uri and uri != namespace:
                    new_stream.append((kind, data, pos))

            else:
                new_stream.append((kind, data, pos))

        return new_stream

    def _extract_includes(self, stream):
        streams = [[]] # stacked lists of events of the "compiled" template
        prefixes = {}
        fallbacks = []
        includes = []
        xinclude_ns = Namespace(self.XINCLUDE_NAMESPACE)

        for kind, data, pos in stream:
            stream = streams[-1]

            if kind is START:
                # Record any directive attributes in start tags
                tag, attrs = data
                if tag in xinclude_ns:
                    if tag.localname == 'include':
                        include_href = attrs.get('href')
                        if not include_href:
                            raise TemplateSyntaxError('Include misses required '
                                                      'attribute "href"',
                                                      self.filepath, *pos[1:])
                        includes.append((include_href, attrs.get('parse')))
                        streams.append([])
                    elif tag.localname == 'fallback':
                        streams.append([])
                        fallbacks.append(streams[-1])
                else:
                    stream.append((kind, (tag, attrs), pos))

            elif kind is END:
                if fallbacks and data == xinclude_ns['fallback']:
                    assert streams.pop() is fallbacks[-1]
                elif data == xinclude_ns['include']:
                    fallback = None
                    if len(fallbacks) == len(includes):
                        fallback = fallbacks.pop()
                    streams.pop() # discard anything between the include tags
                                  # and the fallback element
                    stream = streams[-1]
                    href, parse = includes.pop()
                    try:
                        cls = {
                            'xml': MarkupTemplate,
                            'text': NewTextTemplate
                        }.get(parse) or self.__class__
                    except KeyError:
                        raise TemplateSyntaxError('Invalid value for "parse" '
                                                  'attribute of include',
                                                  self.filepath, *pos[1:])
                    stream.append((INCLUDE, (href, cls, fallback), pos))
                else:
                    stream.append((kind, data, pos))

            elif kind is START_NS and data[1] == xinclude_ns:
                # Strip out the XInclude namespace
                prefixes[data[0]] = data[1]

            elif kind is END_NS and data in prefixes:
                prefixes.pop(data)

            else:
                stream.append((kind, data, pos))

        assert len(streams) == 1
        return streams[0]

    def _interpolate_attrs(self, stream):
        for kind, data, pos in stream:

            if kind is START:
                # Record any directive attributes in start tags
                tag, attrs = data
                new_attrs = []
                for name, value in attrs:
                    if value:
                        value = list(interpolate(value, self.filepath, pos[1],
                                                 pos[2], lookup=self.lookup))

                        if len(value) == 1 and value[0][0] is TEXT: