# $Id: states.py 4824 2006-12-09 00:59:23Z goodger $

# Author: David Goodger <goodger@python.org>

# Copyright: This module has been placed in the public domain.

"""

This is the ``docutils.parsers.restructuredtext.states`` module, the core of

the reStructuredText parser.  It defines the following:

:Classes:

    - `RSTStateMachine`: reStructuredText parser's entry point.

    - `NestedStateMachine`: recursive StateMachine.

    - `RSTState`: reStructuredText State superclass.

    - `Inliner`: For parsing inline markup.

    - `Body`: Generic classifier of the first line of a block.

    - `SpecializedBody`: Superclass for compound element members.

    - `BulletList`: Second and subsequent bullet_list list_items

    - `DefinitionList`: Second+ definition_list_items.

    - `EnumeratedList`: Second+ enumerated_list list_items.

    - `FieldList`: Second+ fields.

    - `OptionList`: Second+ option_list_items.

    - `RFC2822List`: Second+ RFC2822-style fields.

    - `ExtensionOptions`: Parses directive option fields.

    - `Explicit`: Second+ explicit markup constructs.

    - `SubstitutionDef`: For embedded directives in substitution definitions.

    - `Text`: Classifier of second line of a text block.

    - `SpecializedText`: Superclass for continuation lines of Text-variants.

    - `Definition`: Second line of potential definition_list_item.

    - `Line`: Second line of overlined section title or transition marker.

    - `Struct`: An auxiliary collection class.

:Exception classes:

    - `MarkupError`

    - `ParserError`

    - `MarkupMismatch`

:Functions:

    - `escape2null()`: Return a string, escape-backslashes converted to nulls.

    - `unescape()`: Return a string, nulls removed or restored to backslashes.

:Attributes:

    - `state_classes`: set of State classes used with `RSTStateMachine`.

Parser Overview

===============

The reStructuredText parser is implemented as a recursive state machine,

examining its input one line at a time.  To understand how the parser works,

please first become familiar with the `docutils.statemachine` module.  In the

description below, references are made to classes defined in this module;

please see the individual classes for details.

Parsing proceeds as follows:

1. The state machine examines each line of input, checking each of the

   transition patterns of the state `Body`, in order, looking for a match.

   The implicit transitions (blank lines and indentation) are checked before

   any others.  The 'text' transition is a catch-all (matches anything).

2. The method associated with the matched transition pattern is called.

   A. Some transition methods are self-contained, appending elements to the

      document tree (`Body.doctest` parses a doctest block).  The parser's

      current line index is advanced to the end of the element, and parsing

      continues with step 1.

   B. Other transition methods trigger the creation of a nested state machine,

      whose job is to parse a compound construct ('indent' does a block quote,

      'bullet' does a bullet list, 'overline' does a section [first checking

      for a valid section header], etc.).

      - In the case of lists and explicit markup, a one-off state machine is

        created and run to parse contents of the first item.

      - A new state machine is created and its initial state is set to the

        appropriate specialized state (`BulletList` in the case of the

        'bullet' transition; see `SpecializedBody` for more detail).  This

        state machine is run to parse the compound element (or series of

        explicit markup elements), and returns as soon as a non-member element

        is encountered.  For example, the `BulletList` state machine ends as

        soon as it encounters an element which is not a list item of that

        bullet list.  The optional omission of inter-element blank lines is

        enabled by this nested state machine.

      - The current line index is advanced to the end of the elements parsed,

        and parsing continues with step 1.

   C. The result of the 'text' transition depends on the next line of text.

      The current state is changed to `Text`, under which the second line is

      examined.  If the second line is:

      - Indented: The element is a definition list item, and parsing proceeds

        similarly to step 2.B, using the `DefinitionList` state.

      - A line of uniform punctuation characters: The element is a section

        header; again, parsing proceeds as in step 2.B, and `Body` is still

        used.

      - Anything else: The element is a paragraph, which is examined for

        inline markup and appended to the parent element.  Processing

        continues with step 1.

"""

__docformat__ = 'reStructuredText'

import sys

import re

import roman

from types import TupleType, FunctionType, MethodType

from docutils import nodes, statemachine, utils, urischemes

from docutils import ApplicationError, DataError

from docutils.statemachine import StateMachineWS, StateWS

from docutils.nodes import fully_normalize_name as normalize_name

from docutils.nodes import whitespace_normalize_name

from docutils.utils import escape2null, unescape, column_width

import docutils.parsers.rst

from docutils.parsers.rst import directives, languages, tableparser, roles

from docutils.parsers.rst.languages import en as _fallback_language_module

class MarkupError(DataError): pass

class UnknownInterpretedRoleError(DataError): pass

class InterpretedRoleNotImplementedError(DataError): pass

class ParserError(ApplicationError): pass

class MarkupMismatch(Exception): pass

class Struct:

    """Stores data attributes for dotted-attribute access."""

    def __init__(self, **keywordargs):

        self.__dict__.update(keywordargs)

class RSTStateMachine(StateMachineWS):

    """

    reStructuredText's master StateMachine.

    The entry point to reStructuredText parsing is the `run()` method.

    """

    def run(self, input_lines, document, input_offset=0, match_titles=1,

            inliner=None):

        """

        Parse `input_lines` and modify the `document` node in place.

        Extend `StateMachineWS.run()`: set up parse-global data and

        run the StateMachine.

        """

        self.language = languages.get_language(

            document.settings.language_code)

        self.match_titles = match_titles

        if inliner is None:

            inliner = Inliner()

        inliner.init_customizations(document.settings)

        self.memo = Struct(document=document,

                           reporter=document.reporter,

                           language=self.language,

                           title_styles=[],

                           section_level=0,

                           section_bubble_up_kludge=0,

                           inliner=inliner)

        self.document = document

        self.attach_observer(document.note_source)

        self.reporter = self.memo.reporter

        self.node = document

        results = StateMachineWS.run(self, input_lines, input_offset,

                                     input_source=document['source'])

        assert results == [], 'RSTStateMachine.run() results should be empty!'

        self.node = self.memo = None    # remove unneeded references

class NestedStateMachine(StateMachineWS):

    """

    StateMachine run from within other StateMachine runs, to parse nested

    document structures.

    """

    def run(self, input_lines, input_offset, memo, node, match_titles=1):

        """

        Parse `input_lines` and populate a `docutils.nodes.document` instance.

        Extend `StateMachineWS.run()`: set up document-wide data.

        """

        self.match_titles = match_titles

        self.memo = memo

        self.document = memo.document

        self.attach_observer(self.document.note_source)

        self.reporter = memo.reporter

        self.language = memo.language

        self.node = node

        results = StateMachineWS.run(self, input_lines, input_offset)

        assert results == [], ('NestedStateMachine.run() results should be '

                               'empty!')

        return results

class RSTState(StateWS):

    """

    reStructuredText State superclass.

    Contains methods used by all State subclasses.

    """

    nested_sm = NestedStateMachine

    def __init__(self, state_machine, debug=0):

        self.nested_sm_kwargs = {'state_classes': state_classes,

                                 'initial_state': 'Body'}

        StateWS.__init__(self, state_machine, debug)

    def runtime_init(self):

        StateWS.runtime_init(self)

        memo = self.state_machine.memo

        self.memo = memo

        self.reporter = memo.reporter

        self.inliner = memo.inliner

        self.document = memo.document

        self.parent = self.state_machine.node

    def goto_line(self, abs_line_offset):

        """

        Jump to input line `abs_line_offset`, ignoring jumps past the end.

        """

        try:

            self.state_machine.goto_line(abs_line_offset)

        except EOFError:

            pass

    def no_match(self, context, transitions):

        """

        Override `StateWS.no_match` to generate a system message.

        This code should never be run.

        """

        self.reporter.severe(

            'Internal error: no transition pattern match.  State: "%s"; '

            'transitions: %s; context: %s; current line: %r.'

            % (self.__class__.__name__, transitions, context,

               self.state_machine.line),

            line=self.state_machine.abs_line_number())

        return context, None, []

    def bof(self, context):

        """Called at beginning of file."""

        return [], []

    def nested_parse(self, block, input_offset, node, match_titles=0,

                     state_machine_class=None, state_machine_kwargs=None):

        """

        Create a new StateMachine rooted at `node` and run it over the input

        `block`.

        """

        if state_machine_class is None:

            state_machine_class = self.nested_sm

        if state_machine_kwargs is None:

            state_machine_kwargs = self.nested_sm_kwargs

        block_length = len(block)

        state_machine = state_machine_class(debug=self.debug,

                                            **state_machine_kwargs)

        state_machine.run(block, input_offset, memo=self.memo,

                          node=node, match_titles=match_titles)

        state_machine.unlink()

        new_offset = state_machine.abs_line_offset()

        # No `block.parent` implies disconnected -- lines aren't in sync:

        if block.parent and (len(block) - block_length) != 0:

            # Adjustment for block if modified in nested parse:

            self.state_machine.next_line(len(block) - block_length)

        return new_offset

    def nested_list_parse(self, block, input_offset, node, initial_state,

                          blank_finish,

                          blank_finish_state=None,

                          extra_settings={},

                          match_titles=0,

                          state_machine_class=None,

                          state_machine_kwargs=None):

        """

        Create a new StateMachine rooted at `node` and run it over the input

        `block`. Also keep track of optional intermediate blank lines and the

        required final one.

        """

        if state_machine_class is None:

            state_machine_class = self.nested_sm

        if state_machine_kwargs is None:

            state_machine_kwargs = self.nested_sm_kwargs.copy()

        state_machine_kwargs['initial_state'] = initial_state

        state_machine = state_machine_class(debug=self.debug,

                                            **state_machine_kwargs)

        if blank_finish_state is None:

            blank_finish_state = initial_state

        state_machine.states[blank_finish_state].blank_finish = blank_finish

        for key, value in extra_settings.items():

            setattr(state_machine.states[initial_state], key, value)

        state_machine.run(block, input_offset, memo=self.memo,

                          node=node, match_titles=match_titles)

        blank_finish = state_machine.states[blank_finish_state].blank_finish

        state_machine.unlink()

        return state_machine.abs_line_offset(), blank_finish

    def section(self, title, source, style, lineno, messages):

        """Check for a valid subsection and create one if it checks out."""

        if self.check_subsection(source, style, lineno):

            self.new_subsection(title, lineno, messages)

    def check_subsection(self, source, style, lineno):

        """

        Check for a valid subsection header.  Return 1 (true) or None (false).

        When a new section is reached that isn't a subsection of the current

        section, back up the line count (use ``previous_line(-x)``), then

        ``raise EOFError``.  The current StateMachine will finish, then the

        calling StateMachine can re-examine the title.  This will work its way

        back up the calling chain until the correct section level isreached.

        @@@ Alternative: Evaluate the title, store the title info & level, and

        back up the chain until that level is reached.  Store in memo? Or

        return in results?

        :Exception: `EOFError` when a sibling or supersection encountered.

        """

        memo = self.memo

        title_styles = memo.title_styles

        mylevel = memo.section_level

        try:                            # check for existing title style

            level = title_styles.index(style) + 1

        except ValueError:              # new title style

            if len(title_styles) == memo.section_level: # new subsection

                title_styles.append(style)

                return 1

            else:                       # not at lowest level

                self.parent += self.title_inconsistent(source, lineno)

                return None

        if level <= mylevel:            # sibling or supersection

            memo.section_level = level   # bubble up to parent section

            if len(style) == 2:

                memo.section_bubble_up_kludge = 1

            # back up 2 lines for underline title, 3 for overline title

            self.state_machine.previous_line(len(style) + 1)

            raise EOFError              # let parent section re-evaluate

        if level == mylevel + 1:        # immediate subsection

            return 1

        else:                           # invalid subsection

            self.parent += self.title_inconsistent(source, lineno)

            return None

    def title_inconsistent(self, sourcetext, lineno):

        error = self.reporter.severe(

            'Title level inconsistent:', nodes.literal_block('', sourcetext),

            line=lineno)

        return error

    def new_subsection(self, title, lineno, messages):

        """Append new subsection to document tree. On return, check level."""

        memo = self.memo

        mylevel = memo.section_level

        memo.section_level += 1

        section_node = nodes.section()

        self.parent += section_node

        textnodes, title_messages = self.inline_text(title, lineno)

        titlenode = nodes.title(title, '', *textnodes)

        name = normalize_name(titlenode.astext())

        section_node['names'].append(name)

        section_node += titlenode

        section_node += messages

        section_node += title_messages

        self.document.note_implicit_target(section_node, section_node)

        offset = self.state_machine.line_offset + 1

        absoffset = self.state_machine.abs_line_offset() + 1

        newabsoffset = self.nested_parse(

              self.state_machine.input_lines[offset:], input_offset=absoffset,

              node=section_node, match_titles=1)

        self.goto_line(newabsoffset)

        if memo.section_level <= mylevel: # can't handle next section?

            raise EOFError              # bubble up to supersection

        # reset section_level; next pass will detect it properly

        memo.section_level = mylevel

    def paragraph(self, lines, lineno):

        """

        Return a list (paragraph & messages) & a boolean: literal_block next?

        """

        data = '\n'.join(lines).rstrip()

        if re.search(r'(?<!\\)(\\\\)*::$', data):

            if len(data) == 2:

                return [], 1

            elif data[-3] in ' \n':

                text = data[:-3].rstrip()

            else:

                text = data[:-1]

            literalnext = 1

        else:

            text = data

            literalnext = 0

        textnodes, messages = self.inline_text(text, lineno)

        p = nodes.paragraph(data, '', *textnodes)

        p.line = lineno

        return [p] + messages, literalnext

    def inline_text(self, text, lineno):

        """

        Return 2 lists: nodes (text and inline elements), and system_messages.

        """

        return self.inliner.parse(text, lineno, self.memo, self.parent)

    def unindent_warning(self, node_name):

        return self.reporter.warning(

            '%s ends without a blank line; unexpected unindent.' % node_name,

            line=(self.state_machine.abs_line_number() + 1))

def build_regexp(definition, compile=1):

    """

    Build, compile and return a regular expression based on `definition`.

    :Parameter: `definition`: a 4-tuple (group name, prefix, suffix, parts),

        where "parts" is a list of regular expressions and/or regular

        expression definitions to be joined into an or-group.

    """

    name, prefix, suffix, parts = definition

    part_strings = []

    for part in parts:

        if type(part) is TupleType:

            part_strings.append(build_regexp(part, None))

        else:

            part_strings.append(part)

    or_group = '|'.join(part_strings)

    regexp = '%(prefix)s(?P<%(name)s>%(or_group)s)%(suffix)s' % locals()

    if compile:

        return re.compile(regexp, re.UNICODE)

    else:

        return regexp

class Inliner:

    """

    Parse inline markup; call the `parse()` method.

    """

    def __init__(self):

        self.implicit_dispatch = [(self.patterns.uri, self.standalone_uri),]

        """List of (pattern, bound method) tuples, used by

        `self.implicit_inline`."""

    def init_customizations(self, settings):

        """Setting-based customizations; run when parsing begins."""

        if settings.pep_references:

            self.implicit_dispatch.append((self.patterns.pep,

                                           self.pep_reference))

        if settings.rfc_references:

            self.implicit_dispatch.append((self.patterns.rfc,

                                           self.rfc_reference))

    def parse(self, text, lineno, memo, parent):

        # Needs to be refactored for nested inline markup.

        # Add nested_parse() method?

        """

        Return 2 lists: nodes (text and inline elements), and system_messages.

        Using `self.patterns.initial`, a pattern which matches start-strings

        (emphasis, strong, interpreted, phrase reference, literal,

        substitution reference, and inline target) and complete constructs

        (simple reference, footnote reference), search for a candidate.  When

        one is found, check for validity (e.g., not a quoted '*' character).

        If valid, search for the corresponding end string if applicable, and

        check it for validity.  If not found or invalid, generate a warning

        and ignore the start-string.  Implicit inline markup (e.g. standalone

        URIs) is found last.

        """

        self.reporter = memo.reporter

        self.document = memo.document

        self.language = memo.language

        self.parent = parent

        pattern_search = self.patterns.initial.search

        dispatch = self.dispatch

        remaining = escape2null(text)

        processed = []

        unprocessed = []

        messages = []

        while remaining:

            match = pattern_search(remaining)

            if match:

                groups = match.groupdict()

                method = dispatch[groups['start'] or groups['backquote']

                                  or groups['refend'] or groups['fnend']]

                before, inlines, remaining, sysmessages = method(self, match,

                                                                 lineno)

                unprocessed.append(before)

                messages += sysmessages

                if inlines:

                    processed += self.implicit_inline(''.join(unprocessed),

                                                      lineno)

                    processed += inlines

                    unprocessed = []

            else:

                break

        remaining = ''.join(unprocessed) + remaining

        if remaining:

            processed += self.implicit_inline(remaining, lineno)

        return processed, messages

    openers = '\'"([{<'

    closers = '\'")]}>'

    start_string_prefix = (r'((?<=^)|(?<=[-/: \n%s]))' % re.escape(openers))

    end_string_suffix = (r'((?=$)|(?=[-/:.,;!? \n\x00%s]))'

                         % re.escape(closers))

    non_whitespace_before = r'(?<![ \n])'

    non_whitespace_escape_before = r'(?<![ \n\x00])'

    non_whitespace_after = r'(?![ \n])'

    # Alphanumerics with isolated internal [-._] chars (i.e. not 2 together):

    simplename = r'(?:(?!_)\w)+(?:[-._](?:(?!_)\w)+)*'

    # Valid URI characters (see RFC 2396 & RFC 2732);

    # final \x00 allows backslash escapes in URIs:

    uric = r"""[-_.!~*'()[\];/:@&=+$,%a-zA-Z0-9\x00]"""

    # Delimiter indicating the end of a URI (not part of the URI):

    uri_end_delim = r"""[>]"""

    # Last URI character; same as uric but no punctuation:

    urilast = r"""[_~*/=+a-zA-Z0-9]"""

    # End of a URI (either 'urilast' or 'uric followed by a

    # uri_end_delim'):

    uri_end = r"""(?:%(urilast)s|%(uric)s(?=%(uri_end_delim)s))""" % locals()

    emailc = r"""[-_!~*'{|}/#?^`&=+$%a-zA-Z0-9\x00]"""

    email_pattern = r"""

          %(emailc)s+(?:\.%(emailc)s+)*   # name