src/htmlparser/generate_fsm.py

#!/usr/bin/env python
#
# Copyright (c) 2008, Google Inc.
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
#
#     * Redistributions of source code must retain the above copyright
# notice, this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above
# copyright notice, this list of conditions and the following disclaimer
# in the documentation and/or other materials provided with the
# distribution.
#     * Neither the name of Google Inc. nor the names of its
# contributors may be used to endorse or promote products derived from
# this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
# ---
#
# Generate a C include file from a finite state machine definition.
#
# Right now the form is the one expected by htmlparser.c so this file is pretty
# tightly coupled with htmlparser.c.
#

__author__ = 'falmeida@google.com (Filipe Almeida)'

import sys

from fsm_config import FSMConfig


class FSMGenerateAbstract(object):

  def __init__(self, config):
    self._config = config

  def Generate(self):
    """Returns the generated FSM description for the specified language.

    Raises a TypeError, because abstract methods can not be called.

    Raises:
      TypeError
    """
    raise TypeError('Abstract method %s.%s called' % (self._class.__name__,
                                                      self._function))


class FSMGenerateC(FSMGenerateAbstract):
  """Generate the C definition from a statemachien configuration object."""

  TABSTOP_ = 2

  def _Prefix(self):
    """Return a c declaration prefix."""

    return self._config.name.lower() + '_'

  def _StateInternalC(self, st):
    """Return the internal name of the state."""

    return '%sSTATE_INT_%s' % (self._Prefix().upper(), st.upper())

  def _StateExternalC(self, st):
    """Return the external name of the state."""

    return '%sSTATE_%s' % (self._Prefix().upper(), st.upper())

  def _MakeTuple(self, data):
    """Converts data to a string representation of a C tuple."""

    return '{ %s }' % ', '.join(data)

  def _CreateHeader(self):
    """Print the include file header."""

    out = []

    if self._config.comment:
      out.append('/* ' + self._config.comment)
    else:
      out.append('/* State machine definition for ' + self._config.name)
    out.append(' * Auto generated by generate_fsm.py. Please do not edit.')
    out.append(' */')

    return '\n'.join(out)

  def _ListToIndentedString(self, list):
    indented_list = ['  ' + e for e in list]
    return ',\n'.join(indented_list)

  def _CreateEnum(self, name, data):
    """Print a c enum definition."""

    return 'enum %s {\n%s\n};\n' % (name,
                                    self._ListToIndentedString(data))

  def _CreateStructList(self, name, type, data):
    """Print a c flat list.

    Generic function to print list in c in the form of a struct.

    Args:
      name: name of the structure.
      type: type of the struct.
      data: contents of the struct as a list of elements

    Returns:
      String with the generated list.
    """

    return "static const %s %s[] = {\n%s\n};\n" % (
        type,
        name,
        self._ListToIndentedString(data))

  def _CreateStatesEnum(self):
    """Print the internal states enum.

    Prints an enum containing all the valid states.

    Returns:
      String containing a C enumeration of the states.
    """
    list = []  # output list

    for state in self._config.states:
      list.append(self._StateInternalC(state))
    return self._CreateEnum(self._Prefix() + 'state_internal_enum', list)

  def _CreateStatesExternal(self):
    """Print a struct with a mapping from internal to external states."""
    list = []  # output list

    for state_name in self._config.states:
      list.append(self._StateExternalC(
                                self._config.states[state_name].external_name))

    return self._CreateStructList(self._Prefix() + 'states_external',
                                  'int',
                                  list)

  def _CreateStatesInternalNames(self):
    """Return a struct mapping internal states to a strings."""
    out = []  # output list

    for state_name in self._config.states:
      out.append('"' + state_name + '"')

    return self._CreateStructList(self._Prefix() + 'states_internal_names',
                                  'char *',
                                  out)

  def _CreateNumStates(self):
    """Print a Macro defining the number of states."""

    return "#define %s_NUM_STATES %s" % (self._config.name.upper(),
                                         str(len(self._config.states) + 1))

  def _ExpandBracketExpression(self, expression):
    """Expand ranges in a regexp bracket expression.

    Returns a string with the ranges in a bracket expression expanded.

    The bracket expression is similar to grep(1) or regular expression bracket
    expressions but it does not support the negation (^) modifier or named
    character classes like [:alpha:] or [:alnum:].

    The especial character class [:default:] will expand to all elements in the
    ascii range.

    For example, the expression 'a-c13A-D' will expand to 'abc13ABCD'.

    Args:
      expression: A regexp bracket expression. Ie: 'A-Z0-9'.

    Returns:
      A string with the ranges in the bracket expression expanded.
    """

    def ExpandRange(start, end):
      """Return a sequence of characters between start and end.

      Args:
        start: first character of the sequence.
        end: last character of the sequence.

      Returns:
        string containing the sequence of characters between start and end.
      """
      return [chr(c) for c in range(ord(start), ord(end) + 1)]

    def ListNext(input_list):
      """Pop the first element of a list.

      Args:
        input_list: python list object.

      Returns:
        First element of the list or None if the list is empty.
      """
      if input_list:
        return input_list.pop(0)
      else:
        return None

    out = []  # List containing the output

    # Special case for the character class [:default:]
    if expression == '[:default:]':
      out = [chr(c) for c in range(0, 255)]
      return ''.join(out)

    chars = [c for c in expression]  # list o characters in the expression.

    current = ListNext(chars)
    while current:
      next = ListNext(chars)
      if next == '-':
        next = ListNext(chars)
        if next:
          out.extend(ExpandRange(current, next))
        else:
          out.append(current)
          out.append('-')
        current = ListNext(chars)
      else:
        out.append(current)
        current = next

    return ''.join(out)

  def _CreateTransitionTable(self):
    """Print the state transition list.

    Returns a set of C structures that define the transition table for the state
    machine. This structure is a list of lists of ints (int **). The outer list
    indexes the source state and the inner list contains the destination state
    for each of the possible input characters:

    const int * const* transitions[source][input] == destination.

    The conditions are mapped from the conditions variable.

    Returns:
      String containing the generated transition table in a C struct.
    """
    out = []          # output list
    default_state = 'STATEMACHINE_ERROR'
    state_table = {}

    for state in self._config.states:
      state_table[state] = [default_state for col in xrange(255)]

    # We process the transition in reverse order while updating the table.
    for i_transition in range(len(self._config.transitions) - 1, -1, -1):
      transition = self._config.transitions[i_transition]
      (condition_name, src, dst) = (transition.condition,
                                    transition.source,
                                    transition.destination)
      condition = self._config.conditions[condition_name]
      char_list = self._ExpandBracketExpression(condition)

      for c in char_list:
        state_table[src][ord(c)] = self._StateInternalC(dst)

    # Create the inner lists which map input characters to destination states.
    for state in self._config.states:
      transition_row = []
      for c in xrange(0, 255):
        transition_row.append('    /* %06s */ %s' % (repr(chr(c)),
                                                     state_table[state][c]))

      out.append(self._CreateStructList('%stransition_row_%s' %
                                        (self._Prefix(),
                                         state),
                                        'int',
                                        transition_row))
      out.append('\n')

    # Create the outer list, which map source states to input characters.
    out.append('static const %s %s[] = {\n' % ('int *', self._Prefix() +
                                               'state_transitions'))

    row_list = ['  %stransition_row_%s' %
                (self._Prefix(), row) for row in self._config.states]
    out.append(',\n'.join(row_list))
    out.append('\n};\n')

    return ''.join(out)

  def Generate(self):
    """Returns the generated the C include statements for the statemachine."""

    print '\n'.join((self._CreateHeader(),
                     self._CreateNumStates(),
                     self._CreateStatesEnum(),
                     self._CreateStatesExternal(),
                     self._CreateStatesInternalNames(),
                     self._CreateTransitionTable()))


def main():
  if len(sys.argv) != 2:
    print "usage: generate_fsm.py config_file"
    sys.exit(1)

  config = FSMConfig()
  config.Load(sys.argv[1])

  gen = FSMGenerateC(config)
  gen.Generate()


if __name__ == "__main__":
  main()