cxxclass.cc

COPE the first practical network coding scheme which is developped on click

/*
 * cxxclass.{cc,hh} -- representation of C++ classes
 * Eddie Kohler
 *
 * Copyright (c) 2000 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */

#include <click/config.h>

#include "cxxclass.hh"
#include <click/straccum.hh>

bool CxxFunction::parsing_header_file;

CxxFunction::CxxFunction(const String &name, bool in_header,
			 const String &ret_type, const String &args,
			 const String &body, const String &clean_body)
  : _name(name), _in_header(in_header), _from_header_file(parsing_header_file),
    _alive(true), _ret_type(ret_type), _args(args),
    _body(body), _clean_body(clean_body)
{
  //fprintf(stderr, "%s::%s\n", _name.cc(), _body.cc());
}

String
compile_pattern(const String &pattern0)
{
  static const char *three_tokens[] = { ">>=", "<<=", "->*", "::*", 0 };
  static const char *two_tokens[] = { "++", "--", "+=", "-=", "*=", "/=", "->",
				      "%=", "^=", "&=", "~=", "==", "!=",
				      "&&", "||",
				      ">=", "<=", "::", "<<", ">>", ".*", 0 };
  
  StringAccum sa;
  const char *s = pattern0.data();
  const char *end_s = s + pattern0.length();

  while (s < end_s && isspace(*s)) // skip leading space
    s++;

  // XXX not all constraints on patterns are expressed here
  while (s < end_s) {
    if (isspace(*s)) {
      sa << ' ';
      while (s < end_s && isspace(*s))
	s++;
      
    } else if (isalnum(*s) || *s == '_') {
      while (s < end_s && (isalnum(*s) || *s == '_'))
	sa << *s++;
      sa << ' ';
      
    } else if (*s == '#') {
      assert(s < end_s - 1 && isdigit(s[1]));
      sa << s[0] << s[1];
      s += 2;
      
    } else {
      const char *token = 0;
      if (s < end_s - 2)
	for (int i = 0; !token && three_tokens[i]; i++)
	  if (strncmp(three_tokens[i], s, 3) == 0)
	    token = three_tokens[i];
      if (!token && s < end_s - 1)
	for (int i = 0; !token && two_tokens[i]; i++)
	  if (strncmp(two_tokens[i], s, 2) == 0)
	    token = two_tokens[i];
      if (!token)
	sa << *s++ << ' ';
      else {
	sa << token << ' ';
	s += strlen(token);
      }
    }
  }

  return sa.take_string();
}

bool
CxxFunction::find_expr(const String &pattern, int *pos1, int *pos2,
		       int match_pos[10], int match_len[10]) const
{
  const char *ps = pattern.data();
  int plen = pattern.length();

  const char *ts = _clean_body.data();
  int tpos = 0;
  int tlen = _clean_body.length();

  while (tpos < tlen) {

    // fast loop: look for occurrences of first character in pattern
    while (tpos < tlen && ts[tpos] != ps[0])
      tpos++;

    int tpos1 = tpos;
    tpos++;
    int ppos = 1;

    while (tpos < tlen && ppos < plen) {

      if (isspace(ps[ppos])) {
	if (ppos > 0 && (isalnum(ps[ppos-1]) || ps[ppos-1] == '_')
	    && (isalnum(ts[tpos]) || ts[tpos] == '_'))
	  break;
	while (tpos < tlen && isspace(ts[tpos]))
	  tpos++;
	ppos++;

      } else if (ps[ppos] == '#') {
	// save expr and skip over it
	int paren_level = 0;
	int question_level = 0;
	int which = ps[ppos+1] - '0';
	match_pos[which] = tpos;
	while (tpos < tlen) {
	  if (ts[tpos] == '(')
	    paren_level++;
	  else if (ts[tpos] == ')') {
	    if (paren_level == 0)
	      break;
	    paren_level--;
	  } else if (ts[tpos] == ',') {
	    if (paren_level == 0 && question_level == 0)
	      break;
	  } else if (ts[tpos] == '?')
	    question_level++;
	  else if (ts[tpos] == ':' && question_level)
	    question_level--;
	  tpos++;
	}
	match_len[which] = tpos - match_pos[which];
	ppos += 2;

      } else if (ps[ppos] == ts[tpos])
	ppos++, tpos++;

      else
	break;

    }

    if (ppos >= plen) {
      // check that this pattern match didn't occur after some evil qualifier,
      // namely '.', '::', or '->'
      int p = tpos1 - 1;
      while (p >= 0 && isspace(ts[p]))
	p--;
      if (p < 0
	  || (ts[p] != '.'
	      && (p == 0 || ts[p-1] != ':' || ts[p] != ':')
	      && (p == 0 || ts[p-1] != '-' || ts[p] != '>'))) {
	*pos1 = tpos1;
	*pos2 = tpos;
	return true;
      }
    }

    // look for next match
    tpos = tpos1 + 1;
  }

  return false;
}

bool
CxxFunction::find_expr(const String &pattern) const
{
  int pos1, pos2, match_pos[10], match_len[10];
  return find_expr(pattern, &pos1, &pos2, match_pos, match_len);
}

bool
CxxFunction::replace_expr(const String &pattern, const String &replacement)
{
  int pos1, pos2, match_pos[10], match_len[10];
  if (!find_expr(pattern, &pos1, &pos2, match_pos, match_len))
    return false;

  //fprintf(stderr, ":::::: %s\n", _body.cc());
  
  StringAccum sa, clean_sa;
  const char *s = replacement.data();
  const char *end_s = s + replacement.length();
  while (s < end_s) {
    if (*s == '#') {
      assert(s < end_s - 1 && isdigit(s[1]));
      int which = s[1] - '0';
      sa << _body.substring(match_pos[which], match_len[which]);
      clean_sa << _clean_body.substring(match_pos[which], match_len[which]);
      s += 2;
    } else {
      sa << *s;
      clean_sa << *s;
      s++;
    }
  }

  String new_body =
    _body.substring(0, pos1) + sa.take_string() + _body.substring(pos2);
  String new_clean_body =
    _clean_body.substring(0, pos1) + clean_sa.take_string()
    + _clean_body.substring(pos2);
  _body = new_body;
  _clean_body = new_clean_body;

  //fprintf(stderr, ">>>>>> %s\n", _body.cc());
  return true;
}


/*****
 * CxxClass
 **/

CxxClass::CxxClass(const String &name)
  : _name(name), _fn_map(-1)
{
  //fprintf(stderr, "!!!!!%s\n", _name.cc());
}

void
CxxClass::add_parent(CxxClass *cxx)
{
  _parents.push_back(cxx);
}

CxxFunction &
CxxClass::defun(const CxxFunction &fn)
{
  int which = _functions.size();
  _functions.push_back(fn);
  _fn_map.insert(fn.name(), which);
  _functions.back().unkill();
  return _functions.back();
}

bool
CxxClass::reach(int findex, Vector<int> &reached)
{
  if (findex < 0)
    return false;
  if (reached[findex])
    return _should_rewrite[findex];
  reached[findex] = true;
  
  // return true if reachable and rewritable
  const String &clean_body = _functions[findex].clean_body();
  const char *s = clean_body.data();
  int p = 0;
  int len = clean_body.length();
  bool should_rewrite = _has_push[findex] || _has_pull[findex];

  while (p < len) {
    
    // look for a function call
    while (p < len && s[p] != '(')
      p++;
    if (p >= len)
      break;

    int paren_p = p;
    for (p--; p >= 0 && isspace(s[p]); p--)
      /* nada */;
    if (p < 0 || (!isalnum(s[p]) && s[p] != '_')) {
      p = paren_p + 1;
      continue;
    }
    int end_word_p = p + 1;
    while (p >= 0 && (isalnum(s[p]) || s[p] == '_'))
      p--;
    int start_word_p = p + 1;
    while (p >= 0 && isspace(s[p]))
      p--;

    // have found word; check that it is a direct call
    if (p >= 0 && (s[p] == '.' || (p > 0 && s[p-1] == '-' && s[p] == '>')))
      /* do nothing; a call of some object */;
    else {
      // XXX class-qualified?
      String name = clean_body.substring(start_word_p, end_word_p - start_word_p);
      int findex2 = _fn_map[name];
      if (findex2 >= 0 && reach(findex2, reached))
	should_rewrite = true;
    }

    // skip past word
    p = paren_p + 1;
  }

  if (!should_rewrite && !_functions[findex].from_header_file()) {
    // might still be rewritable if it's inlined from the
    // .cc file, which we can't #include
    const String &ret_type = _functions[findex].ret_type();
    const char *s = ret_type.data();
    int len = ret_type.length();
    for (int p = 0; p < len - 6; p++)
      if (s[p+0] == 'i' && s[p+1] == 'n' && s[p+2] == 'l'
	  && s[p+3] == 'i' && s[p+4] == 'n' && s[p+5] == 'e'
	  && (p == 0 || isspace(s[p-1]))
	  && (p == len-6 || isspace(s[p+6]))) {
	should_rewrite = true;
	break;
      }
  }
  
  _should_rewrite[findex] = should_rewrite;
  return should_rewrite;
}

bool
CxxClass::find_should_rewrite()
{
  _has_push.assign(nfunctions(), 0);
  _has_pull.assign(nfunctions(), 0);
  _should_rewrite.assign(nfunctions(), 0);
  
  if (_fn_map["never_devirtualize"] >= 0)
    return false;

  static String::Initializer initializer;
  static String push_pattern = compile_pattern("output(#0).push(#1)");
  static String pull_pattern = compile_pattern("input(#0).pull()");
  static String checked_push_pattern = compile_pattern("checked_output_push(#0,#1)");
  for (int i = 0; i < nfunctions(); i++) {
    if (_functions[i].find_expr(push_pattern)
	|| _functions[i].find_expr(checked_push_pattern))
      _has_push[i] = 1;
    if (_functions[i].find_expr(pull_pattern))
      _has_pull[i] = 1;
  }

  Vector<int> reached(nfunctions(), 0);
  bool any = reach(_fn_map["push"], reached);
  any |= reach(_fn_map["pull"], reached);
  any |= reach(_fn_map["run_scheduled"], reached);
  any |= reach(_fn_map["run_task"], reached);
  any |= reach(_fn_map["run_timer"], reached);
  any |= reach(_fn_map["selected"], reached);
  int simple_action = _fn_map["simple_action"];
  if (simple_action >= 0) {
    reach(simple_action, reached);
    _should_rewrite[simple_action] = any = true;
  }
  if (_fn_map["devirtualize_all"] >= 0) {
    for (int i = 0; i < nfunctions(); i++) {
      const String &n = _functions[i].name();
      if (n != _name && n[0] != '~')
	_should_rewrite[i] = any = true;
    }
  }
  
  return any;
}

void
CxxClass::header_text(StringAccum &sa) const
{
  sa << "class " << _name;
  if (_parents.size()) {
    sa << " : ";
    for (int i = 0; i < _parents.size(); i++) {
      if (i) sa << ", ";
      sa << "public " << _parents[i]->name();
    }
  }
  sa << " {\n public:\n";
  for (int i = 0; i < _functions.size(); i++) {
    const CxxFunction &fn = _functions[i];
    if (fn.alive()) {
      sa << "  " << fn.ret_type() << " " << fn.name() << fn.args();
      if (fn.in_header())
	sa << " {" << fn.body() << "}\n";
      else
	sa << ";\n";
    }
  }
  sa << "};\n";
}

void
CxxClass::source_text(StringAccum &sa) const
{
  for (int i = 0; i < _functions.size(); i++) {
    const CxxFunction &fn = _functions[i];
    if (fn.alive() && !fn.in_header()) {
      sa << fn.ret_type() << "\n" << _name << "::" << fn.name() << fn.args();
      sa << "\n{" << fn.body() << "}\n";
    }
  }
}


/*****
 * CxxInfo
 **/

CxxInfo::CxxInfo()
  : _class_map(-1)
{
}