Finish separation of testing from sel_ldr validation. Also, automate

src/trusted/validator_arm/dgen_output.py

 #!/usr/bin/python
 #
-# Copyright 2012 The Native Client Authors.  All rights reserved.
-# Use of this source code is governed by a BSD-style license that can
-# be found in the LICENSE file.
+# Copyright (c) 2012 The Native Client Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
 #
 
 """
 Responsible for generating the decoder based on parsed table representations.
 """
 
 import dgen_opt
 
 def generate_decoder_h(tables, decoder_name, filename, named_decoders, out):
     """Entry point to the decoder for .h file.
 
     Args:
         tables: list of Table objects to process.
         decoder_name: The name of the decoder state to build.
         filename: The (localized) name for the .h file.
         named_decoders: If true, generate a decoder state with named instances.
         out: a COutput object to write to.
     """
     if len(tables) == 0: raise Exception('No tables provided.')
 
     ifdef_name = _generate_ifdef_name(filename)
-    named_prefix = ''
-    if named_decoders:
-      named_prefix = 'Named'
 
     _generate_header(out)
-    out.line()
+    if named_decoders:

[robertm, 2012/04/11 01:28:43]

this is getting really hard to understand, maybe it is time
to switch to a template based approach, i.e. "%"
you probably need two templates, depending on tcb on/off.
Using the "%(name)s" placeholders will help making this readable.

[Karl, 2012/04/16 23:18:10]

Done.

+      _generate_not_tcb(out)
     out.line("#ifndef %s" % ifdef_name)
     out.line("#define %s" % ifdef_name)
     out.line()
     out.line('#include "native_client/src/trusted/validator_arm/decode.h"')
-    out.line()
-    out.line('namespace nacl_arm_dec {')
+    if named_decoders:
+      out.line('#include "native_client/src/trusted/validator_arm/'
+               'named_class_decoder.h"')
     out.line()
     if named_decoders:
-      _generate_named_decoder_classes(tables, named_prefix, out)
-    _generate_decoder_state_type(tables, decoder_name, named_prefix, out)
+      _generate_rule_classes(tables, out)
+    out.line('namespace nacl_arm_%s {' % ('test' if named_decoders else 'dec'))
+    out.line()
+    if named_decoders:
+      _generate_named_decoder_classes(tables, out)
+    _generate_decoder_state_type(tables, decoder_name, named_decoders, out)
     out.line('}  // namespace')
     out.line("#endif  // %s" % ifdef_name)
 
 
 def generate_decoder_cc(tables, decoder_name, filename, named_decoders, out):
     """Entry point to the decoder for .cc file
 
     Args:
         tables: list of Table objects to process.
         decoder_name: The name of the decoder state to build.
         filename: The (localized) name for the .h file.
         named_decoders: If true, generate a decoder state with named instances.
         out: a COutput object to write to.
     """
     if len(tables) == 0: raise Exception('No tables provided.')
 
-    named_prefix = ''
+    _generate_header(out)
     if named_decoders:
-      named_prefix = 'Named'
-
-    _generate_header(out)
-    out.line()
+      _generate_not_tcb(out)
     out.line('#include "%s"' % (filename[:-2] + 'h'))
     out.line();
     out.line('#include <stdio.h>')
     out.line()
-    out.line('namespace nacl_arm_dec {')
+    if named_decoders:
+      out.line('using nacl_arm_dec::ClassDecoder;')
+      out.line('using nacl_arm_dec::Instruction;')
+      out.line()
+    out.line('namespace nacl_arm_%s {' % ('test' if named_decoders else 'dec'))
     out.line()
     if named_decoders:
-      _generate_named_decoder_classes_impls(tables, named_prefix, out)
-    _generate_prototypes(tables, decoder_name, named_prefix, out)
-    _generate_implementations(tables, decoder_name, named_prefix, out)
-    _generate_constructors(tables, decoder_name, named_prefix, out)
-    _generate_entry_point(decoder_name, named_prefix, tables[0].name, out)
+      _generate_named_decoder_classes_impls(tables, out)
+    _generate_implementations(tables, decoder_name, named_decoders, out)
+    _generate_constructors(tables, decoder_name, named_decoders, out)
+    _generate_entry_point(decoder_name, named_decoders, tables[0].name, out)
     out.line('}  // namespace')
 
 
+def generate_tests_cc(tables, out):
+  if len(tables) == 0: raise Exception('No tables provided.')
+
+  _generate_header(out)
+  _generate_not_tcb(out)
+  out.line('#include "gtest/gtest.h"')
+  out.line('#include "native_client/src/trusted/validator_arm/'
+           'inst_classes_testers.h"')
+  out.line()
+  out.line('namespace nacl_arm_test {')
+  out.line()
+  _generate_rule_testers(tables, out)
+  _generate_tester(out)
+  _generate_test_patterns(tables, out)
+  out.line('}  // namespace')
+  out.line()
+  _generate_test_main(out)
+
+def _named(name, named_decoders):
+  """ Adds 'Named' prefix to name if named_decoders """
+  return 'Named' + name if named_decoders else name
+
 def _generate_ifdef_name(filename):
+  """ Generates the ifdef name to use for the given filename"""
   return filename.replace("/", "_").replace(".", "_").upper() + "_"
 
+def _internalize_component(components):
+  """ Removes an element from components, internalizes the value, and
+      returns the internalized value"
+  """
+  if components:
+    c = components[0]
+    components.remove(c)
+    return None if c == "None" else c
+
+def _terminal_components(terminal):
+  """ Returns the components of a terminal. That is, a four tuple
+      of the form:
+         (class, rule_name, pattern, constraints)
+      where
+         class - The decoder class to return.
+         rule_name - The arm rule that applies
+         pattern - The bit pattern associated with the arm rule
+         constrainst - Name defining constraints to apply.
+  """
+  components = terminal.split()
+  cls = _internalize_component(components)
+  rule = _internalize_component(components)
+  pattern = _internalize_component(components)
+  constraints = _internalize_component(components)
+  return (cls, rule, pattern, constraints)
+
+def _terminal_name(terminal, named_decoders = False):
+  """ Returns the terminal name from the terminal action components,
+      unless named_decoders is true and there is a rule name in the
+      action components. In the latter case, the rule name is returned.
+  """
+  components = _terminal_components(terminal)
+  return components[1] if named_decoders and components[1] else components[0]
+
+def _table_terminals(tables):
+    """ Returns the set of terminals (i.e. actions) defined in the given
+        tables.
+    """
+    terminals = set()
+    for t in tables:
+        for r in t.rows:
+            if r.action.startswith('='):
+                terminals.add(r.action[1:])
+    return terminals
+
+def _named_terminals(tables, named_decoders):
+    """ Returns the set of (named) class names in the given tables. """
+    terminals = set()
+    for t in _table_terminals(tables):
+      terminals.add(_terminal_name(t, named_decoders))
+    return terminals
+
 def _generate_header(out):
     out.block_comment(
         'Copyright 2012 The Native Client Authors.  All rights reserved.',
         'Use of this source code is governed by a BSD-style license that can',
         'be found in the LICENSE file.',
         )
     out.line()
     out.block_comment('DO NOT EDIT: GENERATED CODE')
+    out.line()
 
-def _table_terminals(tables):
-    terminals = set()
-    for t in tables:
-        for r in t.rows:
-            if r.action.startswith('='):
-                terminals.add(r.action[1:])
-    return terminals
+def _generate_not_tcb(out):
+    out.line('#ifndef NACL_TRUSTED_BUT_NOT_TCB')
+    out.line('#error("This file is not meant for use in the TCB")')
+    out.line('#endif')
+    out.line()
 
-def _generate_named_decoder_classes(tables, named_prefix, out):
-  for t in _table_terminals(tables):
-    out.enter_block('struct %s%s : public %s' % (named_prefix, t, t))
-    out.line('virtual ~%s%s() {}' % (named_prefix, t))
-    out.line('virtual const char* name() const;')
+def _generate_rule_class(term, out):
+  """ Generates an instance class for the rule name of the terminal,
+      if the terminal has one. This ensures that it will have a different
+      name than the terminal class, making it easier to identify rules
+      that overlap.
+  """
+  components = _terminal_components(term)
+  if components[1]:
+    out.enter_block('class %s : public %s' % (components[1], components[0]))
+    out.visibility('public')
+    out.line('virtual ~%s() {}' % components[1])
     out.exit_block(';')
     out.line()
 
-def _generate_named_decoder_classes_impls(tables, named_prefix, out):
+def _generate_rule_classes(tables, out):
+  """ Generates an instance class for each rule name defined in the tables.
+      This ensures that each rule name will define a decoder class with the
+      same name as the rule, making test errors easier to understand.
+  """
+  out.block_comment('Define rule decoder classes')
+  out.line('namespace nacl_arm_dec {');
+  out.line()
   for t in _table_terminals(tables):
-    out.enter_block('const char* %s%s::name() const' % (named_prefix, t));
-    out.line('return "%s";' % t)
+    _generate_rule_class(t, out)
+  out.line('}  // namespace nacl_arm_dec')
+  out.line()
+
+def _generate_named_decoder_classes(tables, out):
+  """ Generates a named decoder class for each type of generated
+      decoder class in the decoder state.
+  """
+  out.block_comment('Define name class decoders for each class decoder')
+  out.line()
+  for t in _named_terminals(tables, True):
+    out.enter_block('class %s : public NamedClassDecoder' %

[robertm, 2012/04/11 01:28:43]

this would also benefit from a template

[Karl, 2012/04/16 23:18:10]

Done.

+                    _named(t, True))
+    out.visibility('public');
+    out.line('%s();' % _named(t, True))
+    out.line('virtual ~%s() {}' % _named(t, True))
+    out.visibility('private')
+    out.line('nacl_arm_dec::%s named_decoder_;' % t)
+    out.exit_block(';')
+    out.line()
+
+def _generate_named_decoder_classes_impls(tables, out):
+  """ Generates method implementations for each generated
+      named decoder class
+  """
+  for t in _named_terminals(tables, True):
+    out.enter_constructor_header('%s::%s()' %
+                                 (_named(t, True),
+                                  _named(t, True)))
+    out.line('NamedClassDecoder(named_decoder_, "%s")' % t)
+    out.exit_constructor_header()
+    out.enter_block()
     out.exit_block()
     out.line()
 
-def _generate_decoder_state_type(tables, decoder_name, named_prefix, out):
-    cls_name = '%s%s' % (named_prefix, decoder_name)
+def _generate_decoder_state_type(tables, decoder_name, named_decoders, out):
+    """ Generates the deocder state that dispatches the correct class
+        decoder for any instruction.
+    """
     out.block_comment(
         'Defines a stateless decoder class selector for instructions'
     )
-    out.block_comment('Define the class decoders used by this decoder state.')
-    out.enter_block('class %s : DecoderState' % cls_name)
+    out.enter_block('class %s : nacl_arm_dec::DecoderState' %
+                    _named(decoder_name, named_decoders))
     out.visibility('public')
-    out.comment('Generates an instance of a decoder state.')
-    out.line('explicit %s();' % cls_name)
-    out.line('virtual ~%s();' % cls_name)
+    out.block_comment('Generates an instance of a decoder state.')
+    out.line('explicit %s();' % _named(decoder_name, named_decoders))
+    out.line('virtual ~%s();' % _named(decoder_name, named_decoders))
     out.line()
-    out.comment('Parses the given instruction, returning the decoder to use.')
-    out.line('virtual const class ClassDecoder '
-             '&decode(const Instruction) const;')
-    out.line()
-    out.comment('Define the decoders to use in this decoder state')
-    for t in _table_terminals(tables):
-        out.line('%s%s %s_instance_;' % (named_prefix, t, t))
-    out.line()
-    out.visibility('private')
-    out.comment("Don't allow the following!")
-    out.line('explicit %s(const %s&);' % (cls_name, cls_name))
-    out.line('void operator=(const %s&);' % cls_name)
+    out.block_comment(
+        'Parses the given instruction, returning the decoder to use.')
+    if named_decoders:
+      out.line('const NamedClassDecoder &decode_named('
+               '     const nacl_arm_dec::Instruction) const;')
+    out.line('virtual const class nacl_arm_dec::ClassDecoder')
+    out.line('      &decode(const nacl_arm_dec::Instruction) const;')
+    if not named_decoders:
+      out.line()
+      out.visibility('private')
+    _generate_fields(tables, named_decoders, out)
+    if named_decoders:
+      out.line()
+      out.visibility('private')
+    _generate_prototypes(tables, named_decoders, out)
     out.exit_block(';')
     out.line()
 
-def _generate_prototypes(tables, decoder_name, named_prefix, out):
+def _generate_fields(tables, named_decoders, out):
+    """ Generates an instance field for each class decoder used by
+        the decoder state, so that only one instance exists.
+    """
+    out.block_comment('Define the class decoders used by this decoder state.')
+    for t in _named_terminals(tables, named_decoders):
+        out.line('const %s %s_instance_;' % (_named(t, named_decoders), t))
+    out.line()
+
+def _generate_prototypes(tables, named_decoders, out):
+    """ Generate parsing method prototypes for the decoder state. """
     out.block_comment('Prototypes for static table-matching functions.')
     for t in tables:
-
-        out.line('static inline const ClassDecoder &decode_%s(' % t.name)
-        out.line('    const Instruction insn, const %s%s *state);' %
-                 (named_prefix, decoder_name))
+        out.line('inline const %s &decode_%s('
+                 '     const nacl_arm_dec::Instruction insn) const;'
+                 % (_named('ClassDecoder', named_decoders), t.name))
         out.line()
 
-def _generate_implementations(tables, decoder_name, named_prefix, out):
+def _generate_implementations(tables, decoder_name, named_decoders, out):
+    """ Generate bodies for each parsing method defined for the
+        decoder state.
+    """
     out.block_comment('Table-matching function implementations.')
     for t in tables:
         out.line()
-        _generate_table(t, decoder_name, named_prefix, out)
-    out.line()
+        _generate_table(t, decoder_name, named_decoders, out)
 
-def _generate_constructors(tables, decoder_name, named_prefix, out):
-    out.enter_constructor_header('%s%s::%s%s()' % (named_prefix, decoder_name,
-                                                   named_prefix, decoder_name))
+def _generate_constructors(tables, decoder_name, named_decoders, out):
+    """ Generate the constructor/destructor for the decoder state."""
+    out.enter_constructor_header('%s::%s()' %
+                                 (_named(decoder_name, named_decoders),
+                                  _named(decoder_name, named_decoders)))
     out.line('DecoderState()')
-    for t in _table_terminals(tables):
+    for t in _named_terminals(tables, named_decoders):
       out.line(', %s_instance_()' % t)
     out.exit_constructor_header()
     out.enter_block()
     out.exit_block()
     out.line()
-    out.enter_block('%s%s::~%s%s()' % (named_prefix, decoder_name,
-                                       named_prefix, decoder_name))
+    out.enter_block('%s::~%s()' % (_named(decoder_name, named_decoders),
+                                   _named(decoder_name, named_decoders)))
     out.exit_block()
     out.line()
 
-def _generate_entry_point(decoder_name, named_prefix, initial_table_name, out):
+def _generate_entry_point(decoder_name, named_decoders,
+                          initial_table_name, out):
+    """ Generate method bodies for the top-level parsing method(s) of
+        the decoder state.
+    """
     out.enter_block(
-        'const ClassDecoder &%s%s::decode(const Instruction insn) const' %
-        (named_prefix, decoder_name))
-    out.line('return decode_%s(insn, this);'
-        % initial_table_name)
+        'const ClassDecoder &%s::decode(const Instruction insn) const' %
+        _named(decoder_name, named_decoders))
+    if named_decoders:
+      out.line('return decode_named(insn).named_decoder();')
+    else:
+      out.line('return decode_%s(insn);' % initial_table_name)
     out.exit_block()
     out.line()
+    if named_decoders:
+      out.line('const NamedClassDecoder &%s::decode_named(' %
+                _named(decoder_name, True))
+      out.enter_block('     const Instruction insn) const')
+      out.line('return decode_%s(insn);' % initial_table_name)
+      out.exit_block()
+      out.line()
 
-
-def _generate_table(table, decoder_name, named_prefix, out):
-    """Generates the implementation of a single table."""
+def _generate_table(table, decoder_name, named_decoders, out):
+    """Generates the implementation of a single parsing table."""
     out.block_comment(
         'Implementation of table %s.' % table.name,
         'Specified by: %s.' % table.citation
     )
-    out.line('static inline const ClassDecoder &decode_%s(' %table.name)
-    out.enter_block('    const Instruction insn, const %s%s *state)' %
-                    (named_prefix, decoder_name))
+    out.enter_block('const %s &%s::decode_%s(const Instruction insn) const' %
+                    (_named('ClassDecoder', named_decoders),
+                     _named(decoder_name, named_decoders),
+                     table.name))
 
-    optimized = dgen_opt.optimize_rows(table.rows)
+    # If not named decoder classes, optimize as much as possible. That
+    # is, only consider the decoder class name when merging. If generating
+    # named decoder classes, separate base on rule name as well.
+    num_action_cols = 2 if named_decoders else 1
+    optimized = dgen_opt.optimize_rows(table.rows_filtered(num_action_cols))
     print ("Table %s: %d rows minimized to %d"
         % (table.name, len(table.rows), len(optimized)))
     for row in sorted(optimized):
         exprs = ["(%s)" % p.to_c_expr('insn') for p in row.patterns]
         out.enter_block('if (%s)' % ' && '.join(exprs))
 
         if row.action.startswith('='):
-            _generate_terminal(row.action[1:], out)
+            _generate_terminal(_terminal_name(row.action[1:],
+                                              named_decoders),
+                               out)
         elif row.action.startswith('->'):
             _generate_table_change(row.action[2:], out)
         else:
             raise Exception('Bad table action: %s' % row.action)
 
         out.exit_block()
         out.line()
 
     _generate_safety_net(table, out)
     out.exit_block()
+    out.line()
 
 def _generate_terminal(name, out):
-    out.line('return state->%s_instance_;' % name)
+    out.line('return %s_instance_;' % name)
 
 def _generate_table_change(name, out):
-    out.line('return decode_%s(insn, state);' % name)
+    out.line('return decode_%s(insn);' % name)
 
 def _generate_safety_net(table, out):
     out.line('// Catch any attempt to fall through...')
     out.line('fprintf(stderr, "TABLE IS INCOMPLETE: %s could not parse %%08X",'
         'insn.bits(31,0));' % table.name)
     _generate_terminal('Forbidden', out)
 
+def _rule_tester(rule):
+  return '%s_Tester' % rule
+
+def _rule_base_tester(cls, constraints):
+  return '%sTester%s' % (cls, (constraints if constraints else ''))
+
+def _generate_rule_tester(term, out):
+  components = _terminal_components(term)
+  cls = components[0]
+  rule = components[1]
+  pattern = components[2]
+  constraints = components[3]
+  if cls and rule and pattern:
+    rule_tester = _rule_tester(rule)
+    rule_base_tester = _rule_base_tester(cls, constraints)
+    out.line('class %s ' %  rule_tester)
+    out.enter_block('  : public %s' % rule_base_tester)
+    out.visibility('public')
+    out.line('%s()' % rule_tester)
+    out.line(' : %s(' % rule_base_tester)
+    out.line('       state_.%s_instance_)' % _terminal_name(term, True))
+    out.enter_block()
+    out.exit_block()
+    out.exit_block(';')
+    out.line()
+
+def _generate_rule_testers(tables, out):
+  out.block_comment('Tester classes for decoder rules')
+  out.line()
+  for t in _table_terminals(tables):
+    _generate_rule_tester(t, out)
+
+def _generate_tester(out):
+  out.block_comment('Defines a gtest testing harness for testing',
+                    'Arm32 instructions.')
+  out.enter_block('class Arm32InstructionTests : public ::testing::Test')
+  out.visibility('protected')
+  out.line('Arm32InstructionTests() {}')
+  out.exit_block(';')
+  out.line()
+
+def _generate_test_pattern(term, out):
+  components = _terminal_components(term)
+  cls = components[0]
+  rule = components[1]
+  pattern = components[2]
+  if cls and rule and pattern:
+    rule_tester = _rule_tester(rule)
+    out.enter_block('TEST_F(Arm32InstructionTests, %s_Test)' % rule_tester)
+    out.line('%s tester;' % rule_tester)
+    out.line('tester.Test("%s");' % pattern)
+    out.exit_block()
+    out.line()
+
+def _generate_test_patterns(tables, out):
+  out.block_comment('Test coverage of rule patterns')
+  out.line()
+  for t in _table_terminals(tables):
+    _generate_test_pattern(t, out)
+
+def _generate_test_main(out):
+  out.block_comment('Test driver function.')
+  out.enter_block('int main(int argc, char *argv[])')
+  out.line('testing::InitGoogleTest(&argc, argv);')
+  out.line('return RUN_ALL_TESTS();')
+  out.exit_block()
+
 
 class COutput(object):
     """Provides nicely-formatted C++ output."""
 
     def __init__(self, out):
         self._out = out
         self._indent = 0
 
     def line(self, str = ''):
         self._out.write(self._tabs())
@@ skipping 30 matching lines @@
 
     def _tabs(self):
         return '  ' * self._indent
 
 
 def each_index_pair(sequence):
     """Utility method: Generates each unique index pair in sequence."""
     for i in range(0, len(sequence)):
         for j in range(i + 1, len(sequence)):
             yield (i, j)