<main.cc>=

#include <sstream>
#include "read-code-blocks.h"
#include "samecode-utils.h"
#include "storage.h"
#include "interpret.h"


// Deja vu c++ style.

   static const std::string & find_difference(const str_utils::str_vec &, const str_utils::str_vec &);
   static str_utils::str_vec no_registers(const str_utils::str_vec &);


static std::string
compare_code(const code_block & cb1, const code_block & cb2) {

  // Compare the given code blocks for identical computations; return a message
  // describing the results.  If the message is empty, the computations were
  // identical; otherwise the message describes a difference found between the
  // two computations.

  const storage 
    s1 = interpret(cb1),
    s2 = interpret(cb2);
  
  const str_utils::str_vec
    vars1 = no_registers(s1.get_variables()),
    vars2 = no_registers(s2.get_variables());

  for (unsigned i = 0; i < vars1.size(); i++) {

    const std::string & var = vars1[i];
    const value & v1 = s1.get_value(var);

    if (s2.is_defined(var)) {
      const value & v2 = s2.get_value(var);

      if (v1 != v2) {
        std::ostringstream oss;
        oss << "Block 1 defines " << var << " as " << v1 << ".\n"
            << "Block 2 defines " << var << " as " << v2 << ".\n";
        return oss.str();
        }
      }
    else {
      std::ostringstream oss;
      oss << "Block 1 defines " << var << " as " << v1 << ".\n"
          << "Block 2 does not define " << var << ".\n";
      return oss.str();
      }
    }
  
  if (vars2.size() > vars1.size()) {
    const std::string & var = find_difference(vars2, vars1);
    std::ostringstream oss;
    oss << "Block 1 does not define " << var << ".\n"
        << "Block 2 defines " << var << " as " << s2.get_value(var) << ".\n";
    return oss.str();
    }

  return std::string();
  }


static const std::string &
find_difference(
  const str_utils::str_vec & sv1, const str_utils::str_vec & sv2) {

  // Return an element in sv1 that's not in sv2; Die with an error if no such
  // element exists.

  assert(sv1.size() > sv2.size());

  for (str_utils::strvec_index i = sv1.size(); i > 0; i--) { 

    const std::string & s = sv1[i - 1];
    str_utils::strvec_index j = sv2.size();

    while (j > 0) 
      if (s == sv2[j - 1])
        break;
      else
        j--;

    if (j == 0)
      return s;
    }

  assert(!"can't happen in find_reference()");

  return sv1[0];
  }


int 
main() {

  const code_blocks blks = read_code_blocks(std::cin);

  if (blks.empty()) 
    return EXIT_SUCCESS;
  if (blks.size() != 2) {
    std::cerr << "Expected two code blocks, read " << blks.size() << ".\n";
    return EXIT_FAILURE;
    }

  const std::string & str = compare_code(blks[0], blks[1]);

  if (str.empty())
    return EXIT_SUCCESS;
  else {
    std::cerr << str;
    return EXIT_FAILURE;
    }
  }


static str_utils::str_vec 
no_registers(const str_utils::str_vec & vars) {

  // Return a vector of identifers, none of which are registers.

  str_utils::str_vec nvars;

  for (str_utils::strvec_index i = 0; i < vars.size(); i++) {
    const std::string & v = vars[i];
    if (!samecode_utils::is_register(v))
      nvars.push_back(v);
    }

  return nvars;
  }

Defines main.cc (links are to index).

<storage.h>=

#ifndef _storage_h_defined_
#define _storage_h_defined_

#include "str-utils.h"
#include "value.h"

class storage {

  public:

    // Return true iff the given variable is defined.

       bool is_defined(const std::string &) const;

    // Return the value associated with the given variable.

       value get_value(const std::string &) const;

    // Return the names of all the variables defined.

       str_utils::str_vec get_variables(void) const {
         return vars;
         }

    // Set the given variable to the given value.

       void set_value(const std::string &, const value &);

  private:

    std::vector<std::string> vars;
    std::vector<value> vals;

    int find(const std::string &) const;
  };

#endif

Defines storage.h (links are to index).

<storage.cc>=

#include "storage.h"
#include "samecode-utils.h"


bool storage::
is_defined(const std::string & var) const {
  return find(var) > -1;
  }


int storage::
find(const std::string & var) const {

  // Return the index of the given variable, or -1 if the given variable 
  // isn't defined.

  for (unsigned i = 0; i < vars.size(); i++)
    if (vars[i] == var)
      return static_cast<int>(i);

  return -1;
  }


value storage::
get_value(const std::string & var) const {

  const int i = find(var);

  return (i > -1) ? vals[i] : value(var);
  }


void storage::
set_value(const std::string & var, const value & v) {

  assert(!str_utils::is_int(var));

  const int i = find(var);

  debugp << "set var " << var << " to value " << v << "\n";

  if (i > -1)
    vals[i] = v;
  else {
    vars.push_back(var);
    vals.push_back(v);
    }
  }

Defines storage.cc (links are to index).

<interpret.h>=

#ifndef _interpret_h_defined_
#define _interpret_h_defined_

#include "storage.h"
#include "code-block.h"

// Evaluate the given code block and return the final storage configuration.

   extern storage interpret(const code_block &);

#endif

Defines interpret.h (links are to index).

<interpret.cc>=

#include "interpret.h"
#include "samecode-utils.h"
#include "operation.h"


// Deja vu, c++ style.

   static value get_value(const storage &, const std::string &);


static void
interpret(storage & s, const instruction & ins) {

  // Interpret the given instruction relative to the given storage.

  const value 
    dval = get_value(s, ins.dst),
    sval = get_value(s, ins.src);

  if (ins.opr == "move")
    s.set_value(ins.dst, sval);
  else {
    assert(operation::is_oper(ins.opr));
    s.set_value(ins.dst, value(dval, ins.opr, sval));
    }
  }


storage 
interpret(const code_block & cb) {

  storage s;

  for (unsigned i = 0; i < cb.size(); i++)
    interpret(s, cb[i]);

  return s;
  }


static value
get_value(const storage & s, const std::string & str) {

  // Return the value associated with the given string relative to the given
  // storage.

  return str_utils::is_int(str) ? value(str) : s.get_value(str);
  }

Defines interpret.cc (links are to index).

<instruction.h>=

#ifndef _instruction_h_defined_
#define _instruction_h_defined_

#include <string>

struct instruction {

  std::string opr, dst, src;

  // Return the instruction created from the given instruction string; die with
  // an error message if the string doesn't describe a legal instruction.

     instruction(std::string &);
  };

#endif

Defines instruction.h (links are to index).

<instruction.cc>=

#include "instruction.h"
#include "samecode-utils.h"
#include "operation.h"


static std::string
check_dst(const std::string & opr, const std::string & dst) {

  // Return dst if it's a legal destination for the given operation; die with
  // an error message otherwise.

  if (!samecode_utils::is_register(dst) and 
      ((opr != "move") or !samecode_utils::is_variable(dst))) {
    std::cerr << "Invalid instruction:  invalid destination \"" << dst 
              << "\".\n";
    exit(EXIT_FAILURE);
    }

  return dst;
  }


static std::string
check_opr(const std::string & opr) {

  // Return opr if it's a valid operator; die with an error message otherwise.

  if (!operation::is_oper(opr)) {
    std::cerr << "Invalid instruction:  unrecognized operator \"" << opr 
              << "\".\n";
    exit(EXIT_FAILURE);
    }

  return opr;
  }


static std::string
check_src(const std::string & opr, const std::string & src) {

  // Return src if it's a legal source for the given operation; die with
  // an error message otherwise.

  if (!samecode_utils::is_register(src) and !str_utils::is_int(src) and 
      ((opr != "move") or !samecode_utils::is_variable(src))) {
    std::cerr << "Invalid instruction:  illegal source \"" << src << "\".\n";
    exit(EXIT_FAILURE);
    }

  return src;
  }


instruction::
instruction(std::string & str) {

  str_utils::str_vec pieces = str_utils::split(str);

  if (pieces.size() != 3) {
    std::cerr << "Invalid instruction:  expected 3 fields, got " 
              << pieces.size() << ".\n";
    exit(EXIT_FAILURE);
    }

  opr = check_opr(pieces[0]);
  dst = check_dst(opr, pieces[1]);
  src = check_src(opr, pieces[2]);
  }

Defines instruction.cc (links are to index).

<code-block.h>=

#ifndef _code_block_h_defined_
#define _code_block_h_defined_

#include <vector>
#include <string>
#include "code-block.h"
#include "instruction.h"

typedef std::vector<instruction> code_block;
typedef code_block::size_type    cblk_indx;

#endif

Defines code-block.h (links are to index).

<operation.h>=

#ifndef _operator_h_defined_
#define _operator_h_defined_

#include <string>

namespace operation {

  // Return the value of the given operation.

     std::string do_op(const std::string &, const std::string &, const std::string &);

  // Return true iff the given string is a recognized operator.

     extern bool is_oper(const std::string &);

  // Return true iff the given string is a associative operator.

     extern bool is_associative(const std::string &);

  // Return true iff the given string is a commutative operator.

     extern bool is_commutative(const std::string &);

  };

#endif

Defines operation.h (links are to index).

<operation.cc>=

#include <sstream>
#include <iostream>
#include "operation.h"


const struct oper_info {
  std::string oper;
  bool commutative;
  bool associative;
  } operators[] = {
    { "+",    true,  true },
    { "-",    false, false },
    { "*",    true,  true },
    { "/",    false, false },
    { "%",    false, false },
    { "^",    true,  true },
    { "&",    true,  true },
    { "|",    true,  true },
    { "<<",   false, false },
    { ">>",   false, false },
    { "move", false, false },
  };

const unsigned oper_cnt = sizeof(operators)/sizeof(oper_info);


static int 
find(const std::string oper) {
  
  // Return the index of the given operation, or -1 if there's no such 
  // operation.

  for (unsigned i = 0; i < oper_cnt; i++)
    if (operators[i].oper == oper)
      return i;

  return -1;
  }


namespace operation {


  std::string do_op(
    const std::string & l, const std::string & o, const std::string & r) {

    std::istringstream iss(l + " " + r);
    int lv, rv;
    if (!(iss >> lv >> rv))
      assert(!"bad values in operation::do_op"); 

         if (o == "+") lv += rv;
    else if (o == "-") lv -= rv;
    else if (o == "*") lv *= rv;
    else if (o == "/") lv /= rv ? rv : 1;
    else if (o == "%") lv %= rv ? rv : 1;
    else if (o == "^") lv ^= rv ? rv : 1;
    else if (o == "|") lv |= rv ? rv : 1;
    else if (o == "&") lv &= rv ? rv : 1;
    else if (o == "<<") lv <<= rv;
    else if (o == ">>") lv >>= rv;
    else {
      std::cerr << "Unrecognized operation in operation::do_op.\n";
      std::abort();
      }

    std::ostringstream oss;
    oss << lv;

    return oss.str();
    }


  bool 
  is_oper(const std::string & opr) {
    return find(opr) != -1;
    }


  bool 
  is_associative(const std::string & opr) {
    const int i = find(opr);
    assert(i > -1);
    return operators[i].associative;
    }


  bool 
  is_commutative(const std::string & opr) {
    const int i = find(opr);
    assert(i > -1);
    return operators[i].commutative;
    }
  }

Defines operation.cc (links are to index).

<read-code-blocks.h>=

#ifndef _read_code_blocks_h_defined_
#define _read_code_blocks_h_defined_

#include <istream>
#include <vector>
#include "code-block.h"

typedef std::vector<code_block> code_blocks;

// Read and return all the code blocks in the given input stream.

   extern code_blocks read_code_blocks(std::istream &);

#endif

Defines read-code-blocks.h (links are to index).

<read-code-blocks.cc>=

#include "read-code-blocks.h"
#include "samecode-utils.h"


static bool
read_code_block(std::istream & is, code_block & cb) {

  // Read into code block cb the next code block from the input stream is.
  // Return true if a code block was read; false otherwise.

  std::string ln;

  if (!str_utils::read_next_nonblank_line(is, ln))
    return false;

  cb.clear();

  do cb.push_back(instruction(ln));
  while (std::getline(is, ln) and !str_utils::is_blank_line(ln));
  
  return true;
  }


code_blocks 
read_code_blocks(std::istream & is) {

  code_blocks blks;
  code_block cb;

  while (read_code_block(is, cb)) 
    blks.push_back(cb);

  return blks;
  }

Defines read-code-blocks.cc (links are to index).

Unordered Values

<value.h>=

#ifndef _value_h_defined_
#define _value_h_defined_

#include <ostream>
#include <string>
#include <vector>

class value {
 
  public:
 
     // Make a new value having the given value.

        value(const std::string &);

     // Make a new value equal to the given value.

        value(const value &);

     // Make a new value equal to the given binary operator applied to the
     // given values.

        value(const value &, const std::string &, const value &);

     // Write this value to the given output stream.

        friend std::ostream & operator << (std::ostream &, const value &);

     // Return true iff this value is the same as the given value.

        bool operator == (const value & v) const;

     // Return true iff this value is not the same as the given value.

        bool operator != (const value & v) const {
          return !(*this == v);
          }

  private:

    std::string type;
    value * left, * right;

    value * copy(const value *) const;
    value(const value *, const std::string &, const value *);

    friend class canonical_value;
  };

#endif

<value.cc>=

#include <iterator>
#include "value.h"
#include "operation.h"
#include "samecode-utils.h"
#include "canonical-value.h"


value * value::
copy(const value * vp) const {

  if (!vp)
    return 0;

  return new value(vp->left, vp->type, vp->right);
  }


std::ostream & 
operator << (std::ostream & os, const value & v) {

  if (v.left and v.right)
    return os << "(" << *(v.left) << " " << v.type 
              << " " << *(v.right) << ")";
  else {
    assert(!v.left and !v.right);
    return os << v.type;
    }
  }


bool value::
operator == (const value & v) const {
  return canonical_value(this) == canonical_value(&v);
  }


value::
value(const value & v) 
  : type(v.type), left(copy(v.left)), right(copy(v.right)) {
  }


value::
value(const std::string & v) 
  : type(v), left(0), right(0) {
  }


value::
value(const value & lv, const std::string & opr, const value & rv) 
  : type(opr), left(copy(&lv)), right(copy(&rv)) {
  }


value::
value(const value * lvp, const std::string & opr, const value * rvp) 
  : type(opr), left(copy(lvp)), right(copy(rvp)) {
  }

<canonical-value.h>=

#ifndef _canonical_value_h_defined_
#define _canonical_value_h_defined_

#include <ostream>
#include <string>
#include <vector>
#include "value.h"

class canonical_value {
 
  public:
 
     // Make a new canonical value derived from the given value.

        canonical_value(const value * const);

     // Return true iff this canonical value is the same as the given canonical
     // value.

        bool operator == (const canonical_value &) const;

  private:

    typedef std::vector<canonical_value> Children;

    std::string type;
    Children children;

    void associative_canonify();
    void commutative_canonify();
    void constant_canonify();
    std::string flatten() const;
    void splice(unsigned);
  };

#endif

Defines canonical-value.h (links are to index).

<canonical-value.cc>=

#include <iterator>
#include "canonical-value.h"
#include "operation.h"
#include "samecode-utils.h"
#include "value.h"

void canonical_value::
associative_canonify() {

  // Put this value in associative-canonical form:  if the operator is 
  // associative, put all the descendent operands under this value. 

  unsigned i;

  for (i = 0; i < children.size(); i++)
    children[i].associative_canonify();

  if (operation::is_oper(type) and operation::is_associative(type))
    for (i = children.size(); i > 0; i--)
      if (children[i - 1].type == type)
        splice(i - 1);
  }


void canonical_value::
commutative_canonify() {

  // Put this value in commutative-canonical form:  if the operator is 
  // commutative, put the arguments in ascending order by the contents 
  // of the type field.

  unsigned i;

  for (i = 0; i < children.size(); i++)
    children[i].commutative_canonify();

  if (operation::is_oper(type) and operation::is_commutative(type))
    for (i = 0; i < children.size(); i++) {
      unsigned min = i;
      for (unsigned j = i + 1; j < children.size(); j++)
        if (children[min].type > children[j].type)
          min = j;
      if (min != i)
        std::swap(children[min], children[i]);
      }
  }


canonical_value::
canonical_value(const value * const vp) 
  : type(vp->type) {

  if (vp->left and vp->right) {
    children.push_back(canonical_value(vp->left));
    children.push_back(canonical_value(vp->right));
    }
  else
    assert(!vp->left and !vp->right);

  associative_canonify();
  commutative_canonify();
  constant_canonify();
  }


void canonical_value::
constant_canonify() {

  // Put this value in constant-canonical form:  if the operator has
  // constant operands, do the operation at compile time.

  for (unsigned i = 0; i < children.size(); i++)
    children[i].constant_canonify();

  while ((children.size() > 1) and 
         (str_utils::is_int(children[0].type)) and
         (str_utils::is_int(children[1].type))) {
    children[0].type = 
      operation::do_op(children[0].type, type, children[1].type);
    children.erase(children.begin() + 1);
    }

  if (children.size() == 1) {
    type = children[0].type;
    children.clear();
    }
  }


std::string canonical_value::
flatten() const {

  std::string s(type);

  for (unsigned i = 0; i < children.size(); i++)
    s += " " + children[i].flatten();

  return s;
  }


bool canonical_value::
operator == (const canonical_value & v) const {

  const std::string 
    v1 = flatten(),
    v2 = v.flatten();

  const bool rv = v1 == v2;

  debugp << "v1 = '" << v1 << ", v2 = '" << v2 << "'.\n";

  return rv;
  }


void canonical_value::
splice(unsigned cno) {

  // Replace the given child with its grandchildren.

  assert(cno < children.size());

  canonical_value child = children[cno];

  Children::iterator i = children.begin();
  std::advance(i, cno);
  children.erase(i);

  i = children.begin();
  std::advance(i, cno);
  children.insert(i, child.children.begin(), child.children.end());
  }

Defines canonical-value.cc (links are to index).

Samecode Utilties

<samecode-utils.h>=

#ifndef _samecode_utils_h_defined_
#define _samecode_utils_h_defined_

#ifndef DEBUGP
#  define DEBUGP 0
#endif

#define debugp if (DEBUGP) std::cerr

#include <cassert>
#include <cstdlib>
#include <iostream>
#include <string>
#include "str-utils.h"

namespace samecode_utils {

  // Return true iff the given identifer is a register.

     extern bool is_register(const std::string &);

  // Return true iff the given identifer is a variable.

     extern bool is_variable(const std::string &);
  };

#endif

<samecode-utils.cc>=

#include "samecode-utils.h"

namespace samecode_utils {

  bool
  is_register(const std::string & str) {

    // Return true iff the string str is a valid register name.

    return (str.size() == 2) and ('r' == str[0]) and 
           (str.find_first_of("01234567", 1) == 1);
    }


  bool
  is_variable(const std::string & str) {

    // Return true iff the string str is a valid variable name.

    const std::string a = 
      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";

    return (str.find_first_of(a) == 0) and
           (str.find_first_not_of(a + "0123456789") == std::string::npos) and
           !samecode_utils::is_register(str);
    }
  };

String Utilities

<str-utils.h>=

#ifndef _str_utils_h_defined_
#define _str_utils_h_defined_

#include <string>
#include <istream>
#include <vector>

namespace str_utils {

  typedef std::vector<std::string> str_vec;
  typedef str_vec::iterator        strvec_iter;
  typedef str_vec::const_iterator  strvec_citer;
  typedef str_vec::size_type       strvec_index;

  typedef std::string::size_type   str_index;

  extern bool is_blank_line(const std::string &);
  extern bool read_next_nonblank_line(std::istream &, std::string &);
  extern str_vec split(const std::string &);
  extern bool is_int(const std::string &);
  }

#endif

<str-utils.cc>=

#include "str-utils.h"

static const char * const space_chars = "\t\n ";

namespace str_utils {


  bool 
  is_blank_line(const std::string & str) {
    return str.find_first_not_of(space_chars) == std::string::npos;
    }


  bool
  is_int(const std::string & str) {

    if (str.empty())
      return false;

    const str_index i = (((str[0] == '-') or (str[0] == '+')) ? 1 : 0);

    return str.find_first_not_of("0123456789", i) == std::string::npos;
    }


  bool 
  read_next_nonblank_line(std::istream & is, std::string & str) {
    while (true) {
      if (!std::getline(is, str)) return false;
      if (!is_blank_line(str)) return true;
      }
    }


  str_vec 
  split(const std::string & str) {
    
    str_vec svec;
    strvec_index end = 0;

    while (true) {
      const str_index start = str.find_first_not_of(space_chars, end);
      if (start == std::string::npos) break;
      end = str.find_first_of(space_chars, start + 1);
      if (end == std::string::npos)
        end = str.length();
      svec.push_back(str.substr(start, end - start));
      }

    return svec;
    }
  }


#ifdef STRUTILSTEST

// g++ -o STRUTILS-TEST -g -ansi -pedantic -Wall -DSTRUTILSTEST str-utils.cc && ./STRUTILS-TEST

#include <cassert>

int main() {
  str_utils::str_vec svec = str_utils::split("one two three");
  assert(svec.size() == 3);
  assert(svec[0] == "one");
  assert(svec[1] == "two");
  assert(svec[2] == "three");

  svec = str_utils::split("");
  assert(svec.empty());

  assert(str_utils::is_int("+1"));
  assert(str_utils::is_int("11"));
  assert(str_utils::is_int("-1"));
  assert(!(str_utils::is_int("a")));
  }

#endif