Twig.cpp

/*
 * Twig
 * Universal Accelerator Parser
 * Copyright (C) 2007 David Sagan
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at
 * your option) any later version. 
 * 
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
 * for more details. 
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation, Inc., 
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 * 
 * Direct questions, comments, etc to:
 *   David Sagan (dcs16@cornell.edu)
 */

#include "AML/AMLUtilities.hpp"

using namespace std;
using namespace BasicUtilities;

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

AttributeID::AttributeID() : name(), value() {};
AttributeID::AttributeID(string _name, string _value) : name(_name), value(_value) {};

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

void NodeID::addAttribute (string name, string value) {

  attribute.push_back(AttributeID(name, value));

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

bool NodeID::operator== (const NodeID& n) const {

  if (name != n.name) return false;

  if (attribute.size() != n.attribute.size()) return false;

  AttributeIDVecCIter in = n.attribute.begin();
  for (AttributeIDVecCIter ax = attribute.begin(); ax != attribute.end(); ax++) {
    if (ax->name != in->name || ax->value !=  in->value) return false;
    in++;
  }

  return true;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

bool NodeID::operator== (UAPNode* u) {

  if (name != "" && name != u->getName()) return false;

  for (AttributeIDVecCIter ax = attribute.begin(); ax != attribute.end(); ax++) {
    if (!u->getAttribute(ax->name)) return false;
    if (ax->value != "" && u->getAttributeString(ax->name) != ax->value) return false;
  }

  return true;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

UAPNode* NodeID::getChild(UAPNode* parent, bool create) {

  // Look for a UAPNode child that matches the present NodeID.

  UAPNode* child = NULL;
  NodeVec children = parent->getChildrenByName(name);
  for (NodeVecCIter in = children.begin(); in != children.end(); in++) {
    child = *in;
    for (AttributeIDVecCIter ai = attribute.begin(); ai != attribute.end(); ai++) {
      if (child->getAttributeString(ai->name) != ai->value) {
        child = NULL;
        break;
      }
    }
    if (child) break;
  }

  // If does not exist then create it if wanted.                                                    

  if (create && !child) {
    child = parent->addChild(name);
    for (AttributeIDVecCIter ai = attribute.begin(); ai != attribute.end(); ai++)
      child->addAttribute(ai->name, ai->value);
  }

  return child;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

bool operator== (const NodeIDVec& x, const NodeIDVec& y) {

  if (x.size() != y.size()) return false;

  NodeIDVecCIter iy = y.begin();
  for (NodeIDVecCIter ix = x.begin(); ix != x.end(); ix++) {
    if (!(*ix == *iy)) return false;
    iy++;
  }

  return true;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

Twig::Twig(string twig_str, bool has_ele_name) {
  fromString(twig_str, has_ele_name);
}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

Twig::Twig() : name(), target_attribute(), nodeid_vec(), has_brackets(false) { 
  prefix.clear(); 
}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

bool Twig::fromString (string twig_str, bool has_ele_name) {

  nodeid_vec.clear();
  name = "";
  prefix.clear();
  target_attribute = "";
  has_brackets = false;

  bool ok;
  StrList words = break_line_into_words (twig_str, ok);
  if (!ok) return false;
  if (words.size() == 0) return true;

  // Twig could look something like: 
  //    "q1[quadrupole:k(n=1)@err]" or
  //    "length" or
  //    "bend:g(design=b[len])"
  // ix_b1 and ix_b2 point to  a "[...]" that denote a node list. 
  // But this construct must come before any "(" or "="

  StrListIter ix_b1 = words.end(), ix_b2 = words.end();
  for (StrListIter is = words.begin(); is != words.end(); is++) {
    if (*is == "(") break;
    if (*is == "=") break;
    if (*is == "[") {
      if (ix_b1 != words.end()) return false;
      ix_b1 = is;
    }
    if (*is == "]") {
      if (ix_b1 == words.end()) return false;
      ix_b2 = is;
      break;
    }
  }

  if (ix_b2 != words.end() && ix_b2 != --words.end()) return false;

  // Decompose:
  //   With brackets:                                  words -> ele[attrib]
  //   W/O brackets and starts with "A." or ".A":      words -> ele
  //   None of the above:                              words -> attrib

  StrList ele_words, attrib_words;
  if (ix_b1 != words.end()) {
    has_brackets = true;
    ele_words = list_copy (words.begin(), ix_b1);
    attrib_words = list_copy(ix_b1, ix_b2);
    attrib_words.pop_front();
  } else if (element_val(words, 1) == "." || element_val(words, 2) == ".") {
    ele_words = words;
  } else {
    attrib_words = words;
  }

  // Pull off prefixes.
  // ele_words should be something like "A.B.C" or "A...B" or ".B"
  
  if (!ele_words.empty() && ele_words.front() == ".") { // Take care of initial "."
    prefix.push_back("");
    str_pop (ele_words);
  }
    
  while (true) {
    if (ele_words.empty()) break;
    if (ele_words.size() == 1) {
      name = ele_words.front();
      break;
    }
    prefix.push_back(str_pop(ele_words));
    if (str_pop (ele_words) != ".") return false;
  }

  // Pull off the target if there is one.

  StrListIter i_at = rfind (attrib_words, "@");
  StrListIter i_p = rfind (attrib_words, ")");

  // Ambiguous case. Example: "q".

  if (has_ele_name && ix_b1 == words.end() && i_at == attrib_words.end() && 
                              i_p == attrib_words.end() && prefix.empty()) {
    while (attrib_words.size() != 0) name += str_pop(attrib_words);
    return true;
  }

  // Pull off target if it exists

  if (i_at != attrib_words.end()) {
    for (StrListIter ix = i_at; ix != attrib_words.end(); ix++) {
      if (ix == i_at) continue;
      target_attribute += *ix;
      if (*ix == ")") {
        cout << "error: Twig";
        throw;
      }
    }
    attrib_words.erase(i_at, attrib_words.end());
  }
  
  // Loop over all nodes.
  // A single node looks like "name(attrib1 = val1, ...)"
  // Loop over all nodes that make up the attribute

  while (true) {

    // Get node name.

    if (attrib_words.empty()) return true;
    string word = str_pop(attrib_words);

    // get attributes if they are present

    NodeID node1;
    if (word != "(") {
      node1.name = word;
      if (attrib_words.empty()) {
        nodeid_vec_push_back(node1, twig_str);
        return true;
      }
      word = str_pop (attrib_words);
    }

    if (word != ":" && word != "(") return false;

    if (word == "(") {
      while (true) {
        string attrib_name, value;
        word = str_pop (attrib_words);
        if (!isdigit(word[0]) && !isalpha(word[0]) && word != ")") return false;
        if (word == ")") break;
        attrib_name = word;
        word = str_pop (attrib_words);
        if (word == "=") {
          word = str_pop (attrib_words);
          value = word;
          word = str_pop (attrib_words);
        }
        node1.addAttribute(attrib_name, value);
        if (word == ")") {
          if (attrib_words.empty()) {
            nodeid_vec_push_back(node1, twig_str);
            return true;
          }
          word = str_pop (attrib_words);
          break;
        }
        if (word != ",") return false;
      }
    }

    nodeid_vec_push_back(node1, twig_str);

    if (word != ":") return false;

  }

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

void Twig::nodeid_vec_push_back (NodeID& node, const string& twig_str) {

  // Split the name

  bool prefix_found;
  splitXMLName(node.name, node.xml_uri, node.xml_prefix, node.xml_local_name, prefix_found);

  // Look for a previous component of the nodeid_vec to grab the uri or prefix

  if (node.xml_uri == "") {  // Must be local or qualified
    for (NodeIDVecRIter in = nodeid_vec.rbegin(); in != nodeid_vec.rend(); in++) {
      if (in->xml_prefix == node.xml_prefix) {
        node.xml_uri = in->xml_uri;
        nodeid_vec.push_back(node);
        return;
      }
    }
    if (!prefix_found) { 
      nodeid_vec.push_back(node);
      return;
    }
    cout << "Twig::nodeid_vec_push_back: No elder found with matching XML prefix for: " 
             << twig_str << endl;
    throw;
  }

  // With a universal-name the xml_prefix is obtained from the nearest elder
  // with the same xml_uri.

  if (node.xml_uri != "" && !prefix_found) {
    for (NodeIDVecRIter in = nodeid_vec.rbegin(); in != nodeid_vec.rend(); in++) {
      if (in->xml_uri == node.xml_uri) {
        node.xml_prefix = in->xml_prefix;
        nodeid_vec.push_back(node);
        return;
      }
    }

    node.xml_prefix = "NOT DEFINED!";
    return;
  }

  // Must be a full-name. Nothing to be done here.

  nodeid_vec.push_back(node);
  return;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

StrList Twig::break_line_into_words(string line, bool& ok) {

  // This routine gets the next word chunk...
  // If there are only blank characters in line then return word = "".
  // Else strip off leading blanks.

  ok = false;
  StrList words;
  int ix_parens = 0, ix_square = 0;

  // Loop over all words

  while (true) {

    size_t ix_not = line.find_first_not_of(' ');
    if (ix_not == string::npos) {
      if (ix_parens == 0 && ix_square == 0) ok = true;
      return words;
    }
    line.erase(0, ix_not);

    size_t ix_d = line.find_first_of("[]@=,:()\'\" ");

    // If first character is a delimitor

    if (ix_d == 0) {
      string ch0 = line.substr(0, 1);
      line.erase(0, 1);
      if (ch0 == "(") ix_parens++;
      if (ch0 == ")") ix_parens--;
      if (ch0 == "[") ix_square++;
      if (ch0 == "]") ix_square--;

      // Quoted text. Find matching quote mark
      if (ch0 == "\'" || ch0 == "\"") {
        size_t ix_d2 = line.find_first_of(ch0);
        if (ix_d2 == string::npos) return words;  // Unbalanced quote
        words.push_back(line.substr(0, ix_d2));
        line.erase(0, ix_d2+1);
        continue;
      }
      // Here if not a quote mark
      words.push_back(ch0);

    // Else first character is not a delimitor.
    // Return all characters before delimitor.

    } else {
      words.push_back(line.substr(0, ix_d));
      line.erase(0, ix_d);
    }

  }

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

string NodeID::toString () const {

  string attrib_str;
  for (AttributeIDVecCIter ai = attribute.begin(); ai != attribute.end(); ai++) {
    string value = ai->value;
    if (value.find_first_of(" ,():=") != string::npos) value = "\'" + value + "\'";

    string name = ai->name;
    if (name.find_first_of(" ,():=") != string::npos) name = "\'" + name + "\'";

    if (ai != attribute.begin()) attrib_str += ", ";

    if (value == "")
      attrib_str += name;
    else
      attrib_str += name + "=" + value;
  }

  string node_str = name;
  if (node_str.find_first_of(" ,():=") != string::npos) node_str = "\'" + node_str + "\'";

  if (attrib_str != "") node_str = node_str + "(" + attrib_str + ")";

  return node_str;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

string Twig::toNodeString (bool include_target_attrib) {

  string twig_str = "";

  for (NodeIDVecCIter ni = nodeid_vec.begin(); ni != nodeid_vec.end(); ni++) {
    twig_str = twig_str + ":" + ni->toString();
  }

  twig_str.erase(0,1);  // Erase leading ":"

  if (include_target_attrib) twig_str += "@" + target_attribute;

  return twig_str;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

string Twig::toString () {

  string twig_str = toNodeString();

  // Eg: attrib_root = "q1", attrib = "length", target = "err"
  //        -> full_attrib = "q1[length@err]"

  if (target_attribute != "") twig_str = twig_str + "@" + target_attribute;

  if (name != "" || !prefix.empty()) {

    twig_str = "[" + twig_str + "]";

    if (name == "" && prefix.empty())
      twig_str = "*" + twig_str;
    else if (name == "" && !prefix.empty())
      twig_str = "%" + twig_str;
    else
      twig_str = name + twig_str;
       
    for (StrListCIter is = prefix.begin(); is != prefix.end(); is++) {
      twig_str = *is + "." + twig_str;
    }

  }

  return twig_str;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

UAPNode* Twig::getLocalSubNode (UAPNode* root, bool create) {

  UAPNode* this_node = root;

  for (NodeIDVecIter ni = nodeid_vec.begin(); ni != nodeid_vec.end(); ni++) {
    this_node = ni->getChild(this_node, create);
    if (!this_node) return NULL;
  }

  return this_node;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

UAPNode* Twig::getLocalSubNode (UAPNode* root, string twig_str, bool create) {

  Twig twig;
  if (!twig.fromString(twig_str)) return NULL;
  return twig.getLocalSubNode(root, create);

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

NodeVec Twig::getSubNodes (UAPNode* root, string twig_str) {

  Twig twig;
  NodeVec n_node;
  if (!twig.fromString(twig_str)) return n_node;
  return twig.getSubNodes(root); 

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

NodeVec Twig::getSubNodes (UAPNode* root) {

  // Extract from (name, nodeid_vec) the head node and put that into node0.
  // Everything else goes into id_vec.

  NodeIDVec id_vec = nodeid_vec;
  
  NodeID node0;

  if (name == "") {
    node0 = id_vec.front();
    id_vec.erase(id_vec.begin());
  } else {
    node0.addAttribute("name", name);
  }

  // Now that node0 and id_vec have been setup, let get_sub_nodes do all the work.

  NodeVec node_vec;
  get_sub_nodes (root, node0, id_vec, node_vec);
  return node_vec;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

void Twig::get_sub_nodes (UAPNode* root, 
                            NodeID node0, NodeIDVec id_vec, NodeVec& node_vec) {

  if (node0 == root) {
    Twig twig;
    twig.nodeid_vec = id_vec;
    twig.get_local_sub_nodes(root, id_vec, node_vec);
  }

  NodeVec children = root->getChildren();
  for (NodeVecCIter in = children.begin(); in != children.end(); in++) {
    get_sub_nodes (*in, node0, id_vec, node_vec);
  }

  return;

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

void Twig::get_local_sub_nodes (UAPNode* root, 
                              NodeIDVec id_vec, NodeVec& node_vec) {

  if (id_vec.empty()) {
    node_vec.push_back(root);
    return;
  }

  NodeID node0 = id_vec.front();
  id_vec.erase(id_vec.begin());

  NodeVec children = root->getChildren();
  for (NodeVecIter ni = children.begin(); ni != children.end(); ni++) {
    UAPNode* child = *ni;
    if (!(node0 == child)) continue;
    if (id_vec.empty())
      node_vec.push_back(child);
    else
      get_local_sub_nodes (child, id_vec, node_vec);
  }

  return;  

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

UAPNode* Twig::getSubNode (UAPNode* root) {

  // Extract head

  NodeIDVec id_vec = nodeid_vec;
  
  NodeID node0;

  if (name == "") {
    node0 = id_vec.front();
    id_vec.erase(id_vec.begin());
  } else {
    node0.addAttribute("name", name);
  }

  // Look for head

  return get_sub_node (root, node0, id_vec);

}

// --------------------------------------------------------------------------------
// --------------------------------------------------------------------------------

UAPNode* Twig::get_sub_node (UAPNode* root, NodeID node0, NodeIDVec id_vec) {

  if (node0 == root) {
    Twig twig;
    twig.nodeid_vec = id_vec;
    UAPNode* node = twig.getLocalSubNode(root);
    if (node) return node;
  }

  NodeVec children = root->getChildren();
  for (NodeVecCIter in = children.begin(); in != children.end(); in++) {
    UAPNode* child = *in;
    UAPNode* node = get_sub_node (child, node0, id_vec);
    if (node) return node;
  }

  return NULL;

}

//--------------------------------------------------------------------
//--------------------------------------------------------------------

bool Twig::matchNameAndPrefix (UAPNode* named_node) {

  // Check if the names match

  string node_name = named_node->getAttributeString("name");
  if (node_name == "") return false;
  if (name == "") return false;

  if (!matchName (name, node_name)) return false;

  // If the Twig does not have a prefix then the prefix is always matched.

  if (prefix.empty()) return true;

  // Break the node_prefix into its components.

  string node_prefix_str = named_node->getAttributeString("prefix");
  StrList node_prefix;

  for (size_t ix = node_prefix_str.find('.'); ix != string::npos; 
                                        ix = node_prefix_str.find('.')) {
    node_prefix.push_back(node_prefix_str.substr(0, ix));
    node_prefix_str = node_prefix_str.substr(ix+1);
  }
  node_prefix.push_back(node_prefix_str);

  // And match to the Twig prefix.

  return matchPrefix (prefix, prefix.begin(), node_prefix, node_prefix.begin());

}

//--------------------------------------------------------------------
//--------------------------------------------------------------------

bool Twig::matchName (string twig_name, string node_name) {

  if (twig_name.empty() && node_name.empty()) return true;

  // "*" matches to any number of characters.

  if (twig_name[0] == '*') {
    if (twig_name.size() == 1) return true;
    if (matchName (twig_name.substr(1), node_name)) return true;
    if (node_name.size() < 2) return false;
    return matchName(twig_name, node_name.substr(1));
  }

  if (twig_name.empty() || node_name.empty()) return false;

  // "?" matches to any one character.

  if (twig_name[0] != '?' && twig_name[0] != node_name[0]) return false;
  if (twig_name.size() == 1) {
    if (node_name.size() == 1) return true;
    else return false;
  }

  // If twig_name.size > 1 && node_name.size == 1 then
  // match only if twig_name contains only "*" characters after the first character.

  if (node_name.size() == 1) 
    return (twig_name.find_first_not_of('*', 1) == string::npos);  
  else
    return matchName(twig_name.substr(1), node_name.substr(1));

}

//--------------------------------------------------------------------
//--------------------------------------------------------------------

bool Twig::matchPrefix (StrList& twig_prefix, StrListCIter twig_iter,
                        StrList& node_prefix, StrListCIter node_iter) {

  // It is assumed that twig_prefix and node_prefix are both non-empty.

  string node0 = *node_iter;
  string twig0 = *twig_iter;

  StrListCIter node1_iter = node_iter;
  node1_iter++;
  bool node0_is_last = (node1_iter == node_prefix.end());

  StrListCIter twig1_iter = twig_iter;
  twig1_iter++;
  bool twig0_is_last = (twig1_iter == twig_prefix.end());


  // "." matches to any number of components

  if (twig0 == ".") {
    if (twig0_is_last) return true;
    if (matchPrefix (twig_prefix, twig1_iter, node_prefix, node_iter));
    if (node0_is_last) return false;
    return (matchPrefix (twig_prefix, twig_iter, node_prefix, node1_iter));
  }

  // 

  if (!matchName (twig0, node0)) return false;

  if (twig0_is_last) {
    if (node0_is_last) return true;
    else return false;
  }

  if (node0_is_last) {
    for (twig1_iter++; twig1_iter != twig_prefix.end(); twig1_iter++) {
      if (*twig1_iter != ".") return false;
    }
    return true;
  } else
    return matchPrefix (twig_prefix, twig1_iter, node_prefix, node1_iter);

}

//--------------------------------------------------------------------
//--------------------------------------------------------------------

bool Twig::operator== (Twig t) {

  if (!(nodeid_vec == t.nodeid_vec)) return false;
  if (!(name == t.name)) return false;
  if (prefix.size() != t.prefix.size()) return false;

  StrListCIter it = t.prefix.begin();
  for (StrListCIter is = prefix.begin(); is != prefix.end(); is++) {
    if (is != it) return false;
    it++;
  }

  return (target_attribute == t.target_attribute);

}

---