// tg.beh -- Traversal graph calculation
// $Id: tg.beh,v 1.4 2000/09/19 21:08:39 dougo Exp $

// Step 0: import edu.neu.ccs.demeter.common.tg.*;

// Step 1: define classes implementing the interfaces NameI, which is
// empty (it's only used as keys in a hashtable), and StrategyGraphI:

/** A directed graph whose vertices are NameI objects and whose
    edges are uniquely labeled with consecutive ints starting from 0.
    Also associated with each edge is a constraint (i.e. a boolean
    predicate) on class graph edges.  Additionally, the graph has
    a set of source vertices and a set of target vertices. */
StrategyGraphI {
  /** An Enumeration of vertices (NameI objects) in the strategy graph. */
  public Enumeration getVertices();

  /** An Enumeration of source vertices (NameI objects),
      or null if the strategy is "from *". */
  public Enumeration getSources();

  /** An Enumeration of target vertices (NameI objects),
      or null if the strategy is "to *". */
  public Enumeration getTargets();

  /** The number of edges in the strategy graph. */
  public int numEdges();

  /** A Vector of Integers of the incoming edges to vertex c. */
  public Vector getIncomingIndices(NameI c);

  /** A Vector of Integers of the outgoing edges from vertex c. */
  public Vector getOutgoingIndices(NameI c);

  /** Does the edge meet the constraint on the ith strategy edge,
      given the name map?  The name map is a total map from NameI to
      NameI, both class names and part names. */
  public boolean meetsConstraint(int i, Edge edge, Dictionary nameMap);
}

// Step 2: construct a ClassGraph object and add an edge for each edge
// in the class graph using addConstructionEdge, addAlternationEdge,
// and addInheritanceEdge.  This object can be reused for multiple
// traversal graph computations (with different strategy graphs).

ClassGraph {
  /** Add a construction edge from source to dest named name. */
  public void addConstructionEdge(NameI source, NameI name, NameI dest) (@
    CEdge e = new CEdge();
    e.set_name(name);
    addEdge(e, source, dest);
  @)

  /** Add an alternation edge from source to dest. */
  public void addAlternationEdge(NameI source, NameI dest) (@
    addEdge(new AEdge(), source, dest);
  @)

  /** Add an inheritance edge from source to dest. */
  public void addInheritanceEdge(NameI source, NameI dest) (@
    addEdge(new IEdge(), source, dest);
  @)
}

// Step 3: supply a strategy graph and name map to produce a traversal graph.

ClassGraph {
  (@ // Global variables.  Bad.  None of this is reentrant.
     static int curTrav = 0;
     static int curSGsize = 0;
     static TraversalGraph curTG = null, curForwTG = null;
  @)

  /** Compute the traversal graph corresponding to the strategy graph
      sg with the given nameMap.  A null nameMap means the identity
      function. */
  public TraversalGraph computeTraversalGraph(StrategyGraphI sg,
					      Dictionary nameMap)
  (@
    curTrav++;
    curSGsize = sg.numEdges();
    curTG = new TraversalGraph();
    curForwTG = new TraversalGraph();
    final Dictionary fmap = nameMap;
    Dictionary map =	      // convert nameMap to a total function
      new Hashtable() {
	public Object get(Object sgName) {
	  Object cgName;
	  if (fmap == null || (cgName = fmap.get(sgName)) == null) {
	    return sgName;
	  }
	  return cgName;
	}
      };
    addIntercopyEdges(sg, map);
    unmarkAllForward();
    unmarkAllBackward();
    Enumeration sources = sg.getSources();
    Enumeration targets = sg.getTargets();
    if (sources == null && curSGsize == 1 && targets != null) {
      markAllForward();
    } else {
      if (sources == null) sources = vertices();
      while (sources.hasMoreElements())
	markReachableForwardFrom((NameI) sources.nextElement(), sg, map);
    }
    if (targets == null && curSGsize == 1) {
      markAllBackward();
      ClassGraph.curTG = ClassGraph.curForwTG;
    } else {
      if (targets == null) targets = vertices();
      while (targets.hasMoreElements())
	markReachableBackwardFrom((NameI) targets.nextElement(), sg, map);
    }
    return curTG;
  @)
}

// Step 4: query (or iterate over) the traversal graph to determine
// what nodes and edges in the class graph are in the traversal.

TraversalGraph {
  /** Is the named vertex in the traversal graph? */
  public boolean hasVertex(NameI name) (@
    return vertices.get(name) != null;
  @)

  /** An enumeration of the vertices (NameI objects) in the traversal graph. */
  public Enumeration vertices() (@
    return vertices.keys();
  @)

  /** Is the named construction edge in the traversal graph? */
  public boolean hasConstructionEdge(NameI source, NameI name, NameI dest) (@
    return edges.get(CEdge.toString(source, name, dest)) != null;
  @)

  /** Is the named alternation edge in the traversal graph? */
  public boolean hasAlternationEdge(NameI source, NameI dest) (@
    return edges.get(AEdge.toString(source, dest)) != null;
  @)

  /** Is the named inheritance edge in the traversal graph? */
  public boolean hasInheritanceEdge(NameI source, NameI dest) (@
    return edges.get(IEdge.toString(source, dest)) != null;
  @)

  /** An enumeration of the edges in the traversal graph. */
  public Enumeration edges() (@
    return edges.elements();
  @)
}

// Utility functions.
ClassGraph {
  /** Return the Vertex named c.  If it doesn't exist in the class
      graph, return null. */
  public Vertex findVertex(NameI c) (@ return (Vertex) vertexdict.get(c); @)

  /** Return the Vertex named c.  If it doesn't exist in the class
      graph, and add is true, then add it to the class graph;
      otherwise, return null. */
  public Vertex findVertex(NameI c, boolean add) (@
    Vertex v = findVertex(c);
    if (v == null && add) {
      v = new Vertex(c);
      addVertex(v);
    }
    return v;
  @)
}

// stuff that the core aspect generator needs...
TraversalGraph {
  /** Generate code for following intercopy edges. */
  public String intercopyEdgesCode(NameI name, String indent, String setname)(@
    Vertex v = (Vertex) vertices.get(name);
    return v.intercopyEdgesCode(indent, setname);
  @)

  /** Generate code for modifying the node set before following a
      construction edge. */
  public String cedgeMaskCode(NameI source, NameI name, NameI dest,
		    String indent, String oldsetname, String newsetname) (@
    CEdge cedge = (CEdge) edges.get(CEdge.toString(source, name, dest));
    return cedge.maskCode(indent, oldsetname, newsetname);
  @)

  /** Generate code for modifying the node set before following an
      inheritance edge. */
  public String iedgeMaskCode(NameI source, NameI dest, String indent,
			      String oldsetname, String newsetname) (@
    IEdge iedge = (IEdge) edges.get(IEdge.toString(source, dest));
    return iedge.maskCode(indent, oldsetname, newsetname);
  @)
}
    

// End of public interface.

ClassGraph {
  (@ Hashtable vertexdict; @)
  init (@
    vertexdict = new Hashtable();
    vertices = new Vertex_DList();
  @)

  void addVertex(Vertex v) (@
    vertices.addElement(v);
    vertexdict.put(v.get_name(), v);
  @)
  void addEdge(Edge e) (@
    e.get_source().addOutgoing(e);
    e.get_dest().addIncoming(e);
  @)
  void addEdge(Edge e, NameI source, NameI dest) (@
    e.set_source(findVertex(source, true));
    e.set_dest(findVertex(dest, true));
    addEdge(e);
  @)

  Enumeration vertices() (@
    return vertexdict.keys();
  @)
}

Vertex {
  init (@
    incoming = new Edge_List();
    outgoing = new Edge_List();
    mark = new Mark();
  @)    
  (@ public Vertex(NameI n) { this(); name = n; } @)  

  (@
    // Lazy initialization-- only init when needed.
    private int_int_Pair_List real_intercopyEdges = new int_int_Pair_List();;
    private int trav = 0;
  @)
  
  get intercopyEdges (@
    if (trav != ClassGraph.curTrav)
      set_intercopyEdges(new int_int_Pair_List());
    return real_intercopyEdges;
  @)

  set intercopyEdges (@
    real_intercopyEdges = dest;
    trav = ClassGraph.curTrav;
  @)
}

Vertex {
  void addIncoming(Edge e) (@ incoming.addElement(e); @)
  void addOutgoing(Edge e) (@ outgoing.addElement(e); @)
}

{ Edge, IEdge, CEdge, AEdge } { init (@ mark = new Mark(); @) }

ClassGraph {
  static void markAllForward()	  (@ Mark.all_forw = true; @)
  static void markAllBackward()    (@ Mark.all_back = true; @)
  static void unmarkAllForward()   (@ Mark.all_forw = false; @)
  static void unmarkAllBackward()  (@ Mark.all_back = false; @)
}

// These flags are set on "from *" or "to *" traversals,
// to save from marking everything.
Mark { (@ static boolean all_forw, all_back; @) }

Mark {
  (@
    // Lazy initialization-- only init when needed.
    private BitSet real_forw, real_back, real_both;
    private int forw_trav, back_trav, both_trav;
  @)

  get forw (@
    if (forw_trav != ClassGraph.curTrav)
      set_forw(new BitSet(ClassGraph.curSGsize));
    return real_forw;
  @)

  set forw (@
    real_forw = dest;
    forw_trav = ClassGraph.curTrav;
  @)

  get back (@
    if (back_trav != ClassGraph.curTrav) {
      set_back(new BitSet(ClassGraph.curSGsize));
    }
    return real_back;
  @)

  set back (@
    real_back = dest;
    back_trav = ClassGraph.curTrav;
  @)

  get both (@
    if (both_trav != ClassGraph.curTrav)
      set_both(null);
    return real_both;
  @)

  set both (@
    real_both = dest;
    both_trav = ClassGraph.curTrav;
  @)
}

{ Vertex, Edge } {
  BitSet get_mask() (@
    Mark mark = get_mark();
    if (mark.get_both() != null) return mark.get_both();
    BitSet ret;
    if (Mark.all_forw) {
      if (Mark.all_back) {
	ret = new BitSet();
	ret.set(0);
      } else {
	ret = mark.get_back();
      }
    } else if (Mark.all_back) {
      ret = mark.get_forw();
    } else {
      ret = (BitSet) mark.get_forw().clone();
      ret.and(mark.get_back());
    }
    mark.set_both(ret);
    return ret;
  @)
  boolean get_forw(int i) (@
    if (Mark.all_forw) return true;
    return mark.get_forw(i);
  @)
  boolean get_back(int i) (@
    if (Mark.all_back) return true;
    return mark.get_back(i);
  @)
  void set_forw(int i) (@
    mark.set_forw(i);
    ClassGraph.curForwTG.add(this);
    if (get_back(i)) ClassGraph.curTG.add(this);
  @)
  void set_back(int i) (@
    mark.set_back(i);
    if (get_forw(i)) ClassGraph.curTG.add(this);
  @)
}
Mark {
  (@ static final BitSet zero = new BitSet(0); @)
  boolean get_forw(int i) (@ return get_forw().get(i); @)
  boolean get_back(int i) (@ return get_back().get(i); @)
  void set_forw(int i) (@ get_forw().set(i); @)
  void set_back(int i) (@ get_back().set(i); @)
}

TraversalGraph {
  init (@ vertices = new Hashtable(); edges = new Hashtable(); @)
  void add(Vertex v) (@
    vertices.put(v.get_name(), v);
  @)
  void add(Edge e) (@
    edges.put(e.toString(), e);
  @)
}

int_int_Pair_List {
  // This should be generated automatically...
  public void append(int_int_Pair_List add) (@
    checktail();
    add.checktail();
    if (tail == null) {
      first = add.first;
    } else {
      tail.set_next(add.first);
    }
    tail = add.tail;
  @)
}

ClassGraph {
  /** Add pseudo-edges between copies of the class graph,
      according to nodes in the strategy graph. */
  public void addIntercopyEdges(StrategyGraphI sg, Dictionary nameMap)
  (@
    Enumeration sgVertices = sg.getVertices();
    while (sgVertices.hasMoreElements()) {
      NameI sgv = (NameI) sgVertices.nextElement();
      Vector incoming = sg.getIncomingIndices(sgv);
      Vector outgoing = sg.getOutgoingIndices(sgv);
      NameI cgv = (NameI) nameMap.get(sgv);
      Vertex tgv = findVertex(cgv);
      if (tgv == null) {
	System.err.println("Warning: class graph has no class \"" + cgv + "\".");
      } else {
	tgv.get_intercopyEdges().append(crossProduct(incoming, outgoing));
	// compute transitive closure?
      }
    }
  @)

  int_int_Pair_List crossProduct(Vector v1, Vector v2) (@
    int_int_Pair_List prod = new int_int_Pair_List();
    if (v1.isEmpty() || v2.isEmpty()) return prod;
    Enumeration e1 = v1.elements();
    while (e1.hasMoreElements()) {
      Integer x = (Integer) e1.nextElement();
      Enumeration e2 = v2.elements();
      while (e2.hasMoreElements()) {
	Integer y = (Integer) e2.nextElement();
	prod.addElement(new int_int_Pair(x.intValue(), y.intValue()));
      }
    }
    return prod;
  @)

  public void markReachableForwardFrom(NameI sgVertex, StrategyGraphI sg,
				       Dictionary nameMap)
  (@
    NameI cgVertex = (NameI) nameMap.get(sgVertex);
    Vertex v = findVertex(cgVertex, false);
    if (v == null) {
      // Should throw an exception, or at least take a PrintWriter as
      // parameter...
      System.err.println("Error: no such source class, \"" + cgVertex + "\"");
    } else {
      Vector indices = sg.getOutgoingIndices(sgVertex);
      Enumeration e = indices.elements();
      while (e.hasMoreElements()) {
	Integer i = (Integer) e.nextElement();
	v.markReachableForward(sg, i.intValue(), nameMap);
      }
    }
  @)
  public void markReachableBackwardFrom(NameI sgVertex, StrategyGraphI sg,
					Dictionary nameMap)
  (@
    NameI cgVertex = (NameI) nameMap.get(sgVertex);
    Vertex v = findVertex(cgVertex, false);
    if (v == null) {
      // Should throw an exception, or at least take a PrintWriter as
      // parameter...
      System.err.println("Error: no such target class, \"" + cgVertex + "\"");
    } else {
      Vector indices = sg.getIncomingIndices(sgVertex);
      Enumeration e = indices.elements();
      while (e.hasMoreElements()) {
	Integer i = (Integer) e.nextElement();
	v.markReachableBackward(sg, i.intValue(), nameMap);
      }
    }
  @)
}

Vertex {
  void markReachableForward(StrategyGraphI sg, int i, Dictionary nameMap)
    bypassing { -> *,incoming,*, -> *,source,* }
    to Vertex
  {
    around Vertex (@
      host.set_forw(i);
      subtraversal.apply();
      Enumeration e = host.get_intercopyEdges().elements();
      int old_i = i;
      while (e.hasMoreElements()) {
	int_int_Pair p = (int_int_Pair) e.nextElement();
	if (p.get_x() == old_i && p.get_y() != old_i) {
	  i = p.get_y();
	  host.set_forw(i);
	  // Check for intercopy edge cycles??
	  subtraversal.apply();
	}
      }
      i = old_i;
    @)
    (@ boolean last_was_inheritance; @)
    around CEdge (@
      if (!host.get_forw(i) && sg.meetsConstraint(i, host, nameMap)) {
	host.set_forw(i);
	boolean save = last_was_inheritance;
	last_was_inheritance = false;
	subtraversal.apply();
	last_was_inheritance = save;
      }
    @)
    around AEdge (@
      // alternation can't follow inheritance
      if (!host.get_forw(i) && sg.meetsConstraint(i, host, nameMap)
	  && !last_was_inheritance) {
	host.set_forw(i);
	subtraversal.apply();
      }
    @)
    around IEdge (@
      if (!host.get_forw(i) && sg.meetsConstraint(i, host, nameMap)) {
	host.set_forw(i);
	boolean save = last_was_inheritance;
	last_was_inheritance = true;
	subtraversal.apply();
	last_was_inheritance = save;
      }
    @)
  }
  void markReachableBackward(StrategyGraphI sg, int i, Dictionary nameMap)
    bypassing { -> *,outgoing,*, -> *,dest,* }
    to Vertex
  {
    around Vertex (@
      host.set_back(i);
      subtraversal.apply();
      Enumeration e = host.get_intercopyEdges().elements();
      int old_i = i;
      while (e.hasMoreElements()) {
	int_int_Pair p = (int_int_Pair) e.nextElement();
	if (p.get_y() == old_i && p.get_x() != old_i) {
	  i = p.get_x();
	  host.set_back(i);
	  // Check for intercopy edge cycles??
	  subtraversal.apply();
	}
      }
      i = old_i;
    @)
    (@ boolean last_was_alternation; @)
    around CEdge (@
      if (!host.get_back(i) && sg.meetsConstraint(i, host, nameMap)) {
	host.set_back(i);
	boolean save = last_was_alternation;
	last_was_alternation = false;
	subtraversal.apply();
	last_was_alternation = save;
      }
    @)
    around AEdge (@
      if (!host.get_back(i) && sg.meetsConstraint(i, host, nameMap)) {
	host.set_back(i);
	boolean save = last_was_alternation;
	last_was_alternation = true;
	subtraversal.apply();
	last_was_alternation = save;
      }
    @)
    around IEdge (@
      // inheritance can't follow alternation
      if (!host.get_back(i) && sg.meetsConstraint(i, host, nameMap)
	  && !last_was_alternation) {
	host.set_back(i);
	subtraversal.apply();
      }
    @)
  }
}

Vertex {
  /** Generate code for following intercopy edges. */
  String intercopyEdgesCode(String indent, String setname) (@
    String code = "";
    Enumeration e = get_intercopyEdges().elements();
    while (e.hasMoreElements()) {
      int_int_Pair p = (int_int_Pair) e.nextElement();
      code += indent + "if (" + setname + ".get(" + p.get_x() + "))"
		     + " " + setname + ".set(" + p.get_y() + ");\n";
    }
    return code;
  @)
}

Edge {
  /** Generate code for modifying the node set before following this edge. */
  String maskCode(String indent, String oldsetname, String newsetname)(@
    String code = "";
    BitSet mask = get_mask();
    for (int i = 0; i < mask.size(); i++) {
      if (mask.get(i)) code += indent + newsetname + ".set(" + i + ");\n";
    }
    code += indent + newsetname + ".and(" + oldsetname + ");\n";
    return code;
  @)
}

Edge {
  traversal toAll(EdgePartsVisitor) {
    bypassing { -> *,incoming,*, -> *,outgoing,* }
    to { NameI };
  }
}

EdgePartsVisitor {
  before { Edge, CEdge, AEdge, IEdge,
	   -> Edge,source,Vertex, -> Edge,dest,Vertex,
	   -> Vertex,name,NameI, -> CEdge,name,NameI } (@ @)
  after  { Edge, CEdge, AEdge, IEdge,
	   -> Edge,source,Vertex, -> Edge,dest,Vertex,
	   -> Vertex,name,NameI, -> CEdge,name,NameI } (@ @)
}

{ ClassGraph, int_int_Pair_List } {
  public String toString() (@
    StringWriter sw = new StringWriter();
    toAll(new PrintVisitor(new PrintWriter(sw, true)));
    return sw.toString();
  @)
  traversal toAll(UniversalVisitor) {
    bypassing { -> *,source,*, -> *,dest,* }
    to *;
  }
}

CEdge {
  public static String toString(NameI source, NameI name, NameI dest) (@
    return "-> " + source + "," + name + "," + dest;
  @)
  public String toString() (@
    return toString(source.get_name(), name, dest.get_name());
  @)
}

AEdge {
  public static String toString(NameI source, NameI dest) (@
    return "=> " + source + "," + dest;
  @)
  public String toString() (@
    return toString(source.get_name(), dest.get_name());
  @)
}

IEdge {
  static String toString(NameI source, NameI dest) (@
    return ":> " + source + "," + dest;
  @)
  public String toString() (@
    return toString(source.get_name(), dest.get_name());
  @)
}