// tg.beh -- Traversal graph calculation
// $Id: tg.beh,v 1.2 1998/04/29 13:27:32 dougo Exp $

StrategyGraphI {
  public Vector getIncomingIndices(ClassNameI c);
  public Vector getOutgoingIndices(ClassNameI c);
  public boolean meetsConstraint(int i, TGEdge edge);
}

// Constructors.
TraversalGraph {
  init (@
    vertexdict = new Hashtable();
    vertices = new TGVertex_DList();
  @)
}
TGVertex {
  init (@
    incoming = new TGEdge_List();
    outgoing = new TGEdge_List();
    intercopyEdges = new int_int_Pair_List();
    mark = new TGMark();
  @)    
  (@ public TGVertex(ClassNameI name) { this(); classname = name; } @)  
}
{ TGEdge, TGIEdge, TGCEdge, TGAEdge } { init (@ mark = new TGMark(); @) }

// Utility functions.
TraversalGraph {
  public TGVertex findVertex(ClassNameI c, boolean add) (@
    TGVertex v = (TGVertex) vertexdict.get(c);
    if (v == null && add) {
      // Terminal class; just add it.
      v = new TGVertex(c);
      addVertex(v);
    }
    return v;
  @)
  public void addVertex(TGVertex v) (@
    vertices.addElement(v);
    vertexdict.put(v.get_classname(), v);
  @)
  public void addEdge(TGEdge e) (@
    e.get_source().addOutgoing(e);
    e.get_dest().addIncoming(e);
  @)
}
TGVertex {
  void addIncoming(TGEdge e) (@ incoming.addElement(e); @)
  void addOutgoing(TGEdge e) (@ outgoing.addElement(e); @)
}

TraversalGraph {
  /** Mark every vertex & edge. */
  public static void markEverything() (@ markAllForward();markAllBackward(); @)
  public static void markAllForward()	  (@ TGMark.all_forw = true; @)
  public static void markAllBackward()    (@ TGMark.all_back = true; @)
  public static void unmarkAllForward()   (@ TGMark.all_forw = false; @)
  public static void unmarkAllBackward()  (@ TGMark.all_back = false; @)
}

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

TraversalGraph {
  /** Make n copies of the traversal graph.
      This is actually implemented by making n copies of the marks. */
  public void makeCopies(int copies)
    // Be careful to break cycles...
    bypassing -> TGEdge,*,TGVertex to TGMark
  {
    before TGMark (@
      host.set_forw(new BitSet(copies));
      host.set_back(new BitSet(copies));
      host.set_both(null);
    @)
  }
}

{ TGVertex, TGEdge } {
  public boolean is_in_trav() (@
    BitSet mask = get_mask();
    return mask != null && !mask.equals(TGMark.zero);
  @)
  BitSet get_mask() (@
    TGMark mark = get_mark();
    if (mark == null) return null;
    if (mark.get_both() != null) return mark.get_both();
    BitSet ret;
    if (TGMark.all_forw) {
      if (TGMark.all_back) {
	ret = new BitSet();
	ret.set(0);
      } else {
	ret = mark.get_back();
      }
    } else if (TGMark.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 (TGMark.all_forw) return true;
    TGMark mark = get_mark();
    return mark != null && mark.get_forw(i);
  @)
  boolean get_back(int i) (@
    if (TGMark.all_back) return true;
    TGMark mark = get_mark();
    return mark != null && mark.get_back(i);
  @)
  void set_forw(int i) (@
    TGMark mark = get_mark();
    if (mark != null) mark.set_forw(i);
  @)
  void set_back(int i) (@
    TGMark mark = get_mark();
    if (mark != null) mark.set_back(i);
  @)
}
TGMark {
  (@ static final BitSet zero = new BitSet(0); @)
  boolean get_forw(int i) (@ return forw.get(i); @)
  boolean get_back(int i) (@ return back.get(i); @)
  void set_forw(int i) (@ forw.set(i); @)
  void set_back(int i) (@ back.set(i); @)
}

TraversalGraph {
  /** Add pseudo-edges between copies of the traversal graph,
      according to nodes in the strategy graph. */
  public void addIntercopyEdges(StrategyGraphI sg)
    bypassing { -> *,incoming,* }
    to-stop TGVertex
  {
    before TGVertex (@
      ClassNameI dest = host.get_classname();
      Vector incoming = sg.getIncomingIndices(dest);
      Vector outgoing = sg.getOutgoingIndices(dest);
      host.set_intercopyEdges(crossProduct(incoming, outgoing));
      // compute transitive closure?
      // System.err.println("Intercopy edges for " + dest + ": " + host.get_intercopyEdges());
    @)
    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(ClassNameI c, StrategyGraphI sg) (@
    TGVertex v = findVertex(c, false);
    if (v == null) {
      // Should throw an exception, or at least take a PrintWriter as
      // parameter...
      System.err.println("Error: no such source class, \"" + c + "\"");
    } else {
      Vector indices = sg.getOutgoingIndices(c);
      Enumeration e = indices.elements();
      while (e.hasMoreElements()) {
	Integer i = (Integer) e.nextElement();
	v.markReachableForward(sg, i.intValue());
      }
    }
  @)
  public void markReachableBackwardFrom(ClassNameI c, StrategyGraphI sg) (@
    TGVertex v = findVertex(c, false);
    if (v == null) {
      // Should throw an exception, or at least take a PrintWriter as
      // parameter...
      System.err.println("Error: no such target class, \"" + c + "\"");
    } else {
      Vector indices = sg.getIncomingIndices(c);
      Enumeration e = indices.elements();
      while (e.hasMoreElements()) {
	Integer i = (Integer) e.nextElement();
	v.markReachableBackward(sg, i.intValue());
      }
    }
  @)
}

TGVertex {
  void markReachableForward(StrategyGraphI sg, int i)
    bypassing { -> *,incoming,*, -> *,source,* }
    to TGVertex
  {
    around TGVertex (@
      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 TGCEdge (@
      if (!host.get_forw(i) && sg.meetsConstraint(i, host)) {
	host.set_forw(i);
	boolean save = last_was_inheritance;
	last_was_inheritance = false;
	subtraversal.apply();
	last_was_inheritance = save;
      }
    @)
    around TGAEdge (@
      // alternation can't follow inheritance
      if (!host.get_forw(i) && sg.meetsConstraint(i, host)
	  && !last_was_inheritance) {
	host.set_forw(i);
	subtraversal.apply();
      }
    @)
    around TGIEdge (@
      if (!host.get_forw(i) && sg.meetsConstraint(i, host)) {
	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)
    bypassing { -> *,outgoing,*, -> *,dest,* }
    to TGVertex
  {
    around TGVertex (@
      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 TGCEdge (@
      if (!host.get_back(i) && sg.meetsConstraint(i, host)) {
	host.set_back(i);
	boolean save = last_was_alternation;
	last_was_alternation = false;
	subtraversal.apply();
	last_was_alternation = save;
      }
    @)
    around TGAEdge (@
      if (!host.get_back(i) && sg.meetsConstraint(i, host)) {
	host.set_back(i);
	boolean save = last_was_alternation;
	last_was_alternation = true;
	subtraversal.apply();
	last_was_alternation = save;
      }
    @)
    around TGIEdge (@
      // inheritance can't follow alternation
      if (!host.get_back(i) && sg.meetsConstraint(i, host)
	  && !last_was_alternation) {
	host.set_back(i);
	subtraversal.apply();
      }
    @)
  }
}

TGVertex {
  /** Generate code for following intercopy edges. */
  public String intercopyEdgesCode(String indent, String setname) (@
    String code = "";
    Enumeration e = 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;
  @)
}

TGEdge {
  /** Generate code for modifying the node set before following this edge. */
  public 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;
  @)
}

TGEdge {
  traversal toAll(TGEdgeVisitor) {
    bypassing { -> *,incoming,*, -> *,outgoing,* }
    to { ClassNameI, PartNameI };
  }
}

TGEdgeVisitor {
  before { TGEdge, TGCEdge, TGAEdge, TGIEdge,
	   -> TGEdge,source,TGVertex, -> TGEdge,dest,TGVertex,
	   -> TGVertex,classname,ClassNameI, -> TGCEdge,name,PartNameI } (@ @)
  after  { TGEdge, TGCEdge, TGAEdge, TGIEdge,
	   -> TGEdge,source,TGVertex, -> TGEdge,dest,TGVertex,
	   -> TGVertex,classname,ClassNameI, -> TGCEdge,name,PartNameI } (@ @)
}