From 3ad6a49a28d6768a6bbbd38c3fea80bc4ea59b16 Mon Sep 17 00:00:00 2001
From: yeom <yeom>
Date: Thu, 3 Mar 2011 19:33:42 +0000
Subject: [PATCH] add grammar for the definition of location hierarchy.
 location hierarchy is stored in the lattice data structure. class descriptor
 has a lattice object since each class maintains its own location hierarchy,

---
 Robust/src/IR/ClassDescriptor.java |  14 ++++
 Robust/src/IR/Tree/BuildIR.java    |  17 ++++-
 Robust/src/Lex/Keyword.java        |   2 +
 Robust/src/Lex/Lexer.java          |   2 +-
 Robust/src/Parse/java14.cup        |  38 +++++++++--
 Robust/src/Util/Lattice.java       | 103 +++++++++++++++++++++++++++++
 6 files changed, 170 insertions(+), 6 deletions(-)
 create mode 100644 Robust/src/Util/Lattice.java

diff --git a/Robust/src/IR/ClassDescriptor.java b/Robust/src/IR/ClassDescriptor.java
index 26e57df0..d1fa7b49 100644
--- a/Robust/src/IR/ClassDescriptor.java
+++ b/Robust/src/IR/ClassDescriptor.java
@@ -1,6 +1,7 @@
 package IR;
 import java.util.*;
 import IR.Tree.*;
+import Util.Lattice;
 
 public class ClassDescriptor extends Descriptor {
   private static int UIDCount=1; // start from 1 instead of 0 for multicore gc
@@ -38,6 +39,9 @@ public class ClassDescriptor extends Descriptor {
   SymbolTable enumdescs;
   HashMap<String, Integer> enumConstantTbl;
   int enumconstantid = 0;
+  
+  // for SSJava
+  Lattice<String> locOrder;
 
   public ClassDescriptor(String classname, boolean isInterface) {
     this("", classname, isInterface);
@@ -57,6 +61,7 @@ public class ClassDescriptor extends Descriptor {
     superIFdesc = new SymbolTable();
     this.innerdescs = new SymbolTable();
     this.enumdescs = new SymbolTable();
+    this.locOrder=new Lattice<String>();
   }
 
   public int getId() {
@@ -370,4 +375,13 @@ public class ClassDescriptor extends Descriptor {
   public Modifiers getModifier() {
     return this.modifiers;
   }
+  
+  public Lattice<String> getLocOrder(){
+    return this.locOrder;
+  }
+  
+  public void setLocOrder(Lattice<String> locOrder){
+    this.locOrder=locOrder;
+  }
+  
 }
diff --git a/Robust/src/IR/Tree/BuildIR.java b/Robust/src/IR/Tree/BuildIR.java
index fd12e968..4b505b0a 100644
--- a/Robust/src/IR/Tree/BuildIR.java
+++ b/Robust/src/IR/Tree/BuildIR.java
@@ -1,5 +1,6 @@
 package IR.Tree;
 import IR.*;
+import Util.Lattice;
 
 import java.util.*;
 
@@ -473,11 +474,25 @@ public class BuildIR {
 	} else if (isNode(decl, "static_block")) {
 	  parseStaticBlockDecl(cn, decl.getChild("static_block_declaration"));
 	} else if (isNode(decl,"block")) {
-	} else throw new Error();
+	} else if (isNode(decl,"location_order_declaration")) {
+	  parseLocationOrder(cn,decl.getChild("location_order_list"));
+  } else throw new Error();
       }
     }
   }
   
+  private void parseLocationOrder(ClassDescriptor cn, ParseNode pn){
+    ParseNodeVector pnv=pn.getChildren();
+    Lattice<String> locOrder=new Lattice<String>();
+    for(int i=0; i<pnv.size(); i++) {
+      ParseNode loc=pnv.elementAt(i);
+      String lowerLoc=loc.getChildren().elementAt(0).getLabel();
+      String higherLoc=loc.getChildren().elementAt(1).getLabel();
+      locOrder.put(higherLoc, lowerLoc);      
+    }
+    cn.setLocOrder(locOrder);
+  }
+  
   private void parseClassMember(ClassDescriptor cn, ParseNode pn) {
     ParseNode fieldnode=pn.getChild("field");
     if (fieldnode!=null) {
diff --git a/Robust/src/Lex/Keyword.java b/Robust/src/Lex/Keyword.java
index b10d949c..b773a7fe 100644
--- a/Robust/src/Lex/Keyword.java
+++ b/Robust/src/Lex/Keyword.java
@@ -91,5 +91,7 @@ class Keyword extends Token {
     // Keywords for interface of mgc
     key_table.put("interface", new Integer(Sym.INTERFACE));
     key_table.put("implements", new Integer(Sym.IMPLEMENTS));
+    // Keywords for Self-Stabilizing Java
+    key_table.put("locdef", new Integer(Sym.LOCDEF));
   }
 }
diff --git a/Robust/src/Lex/Lexer.java b/Robust/src/Lex/Lexer.java
index ba081e86..744c5aca 100644
--- a/Robust/src/Lex/Lexer.java
+++ b/Robust/src/Lex/Lexer.java
@@ -267,7 +267,7 @@ public class Lexer {
     "import", "instanceof", "int",
     "interface",
     "isavailable",
-    "long",
+    "locdef", "long", 
     "native", "new", "optional", "package", "private", "protected", "public", 
     "rblock", "return",
     "scratch", "sese", "short", "static", "strictfp", "super", "switch", "synchronized",
diff --git a/Robust/src/Parse/java14.cup b/Robust/src/Parse/java14.cup
index 448e3b62..d25c325b 100644
--- a/Robust/src/Parse/java14.cup
+++ b/Robust/src/Parse/java14.cup
@@ -86,6 +86,7 @@ terminal MULTEQ, DIVEQ, MODEQ, PLUSEQ, MINUSEQ; // assignment_operator
 terminal LSHIFTEQ, RSHIFTEQ, URSHIFTEQ; // assignment_operator
 terminal ANDEQ, XOREQ, OREQ; // assignment_operator
 terminal AT;           // support annotations
+terminal LOCDEF;          // declaration of location hierarchy
 
 terminal java.lang.Number INTEGER_LITERAL;
 terminal java.lang.Number FLOATING_POINT_LITERAL;
@@ -158,6 +159,8 @@ non terminal ParseNode static_initializer;
 non terminal ParseNode constructor_declaration, constructor_declarator;
 non terminal ParseNode constructor_body;
 non terminal ParseNode explicit_constructor_invocation;
+// 19.8.6) Location Hierarchy Declarations
+non terminal ParseNode location_order_declaration, location_order_list, location_order;
 // 19.9.1) Interface Declarations
 non terminal ParseNode interface_declaration;
 non terminal normal_interface_declaration, annotation_type_declaration;
@@ -950,14 +953,17 @@ class_body_declaration ::=
 	:}
 	|	block:block {:
 		RESULT=(new ParseNode("block")).addChild(block).getRoot();
-:}
+        :}
+        |       location_order_declaration:lod {:
+                RESULT=(new ParseNode("location_order_declaration")).addChild(lod).getRoot();
+        :}
 	;
 class_member_declaration ::=
 	//failure aware computation
 	flag_declaration:flag {: 
 	RESULT=(new ParseNode("flag")).addChild(flag).getRoot(); 
-	:}
-	|
+	:}	
+        |
 	field_declaration:field {: 
 	RESULT=(new ParseNode("field")).addChild(field).getRoot(); 
 	:}
@@ -1034,7 +1040,6 @@ enum_constant ::=
 //	|	SEMICOLON class_body_declarations_opt:cbdo
 //	;
 
-
 //Failure aware computation
 flag_declaration ::= 
 		FLAG IDENTIFIER:id SEMICOLON {: 
@@ -1281,6 +1286,31 @@ SUPER LPAREN argument_list_opt:alo RPAREN SEMICOLON {:
 //	|	primary DOT SUPER LPAREN argument_list_opt RPAREN SEMICOLON
 	;
 
+// 19.8.6) Location Hierarchy Declarations
+location_order_declaration ::= LOCDEF LBRACE location_order_list:lol RBRACE {:
+                RESULT=lol;			   
+        :}
+        ;
+location_order_list ::= 
+                location_order:lo {:
+                ParseNode pn=new ParseNode("location_order_list");
+		pn.addChild(lo);
+		RESULT=pn;
+        :}
+        |       location_order_list:lol COMMA location_order:lo {:
+                lol.addChild(lo);
+		RESULT=lol;
+        :}
+        ;
+location_order ::= 
+                IDENTIFIER:loc1 LT IDENTIFIER:loc2{:
+         	ParseNode pn=new ParseNode("location_order");
+		pn.addChild(loc1);
+		pn.addChild(loc2);
+		RESULT=pn;         
+        :}
+        ;
+
 // 19.9) Interfaces
 
 // 19.9.1) Interface Declarations
diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java
new file mode 100644
index 00000000..6ddc9a34
--- /dev/null
+++ b/Robust/src/Util/Lattice.java
@@ -0,0 +1,103 @@
+package Util;
+
+import java.util.HashSet;
+import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.Set;
+
+public class Lattice<T> {
+  private Hashtable<T, Set<T>> table;
+  int size;
+
+  public Lattice() {
+    table = new Hashtable<T, Set<T>>();
+  }
+
+  public boolean put(T key, T value) {
+    Set<T> s;
+    if (table.containsKey(key)) {
+      s = table.get(key);
+    } else {
+      s = new HashSet<T>();
+      table.put(key, s);
+    }
+    if (!s.contains(value)) {
+      size++;
+      s.add(value);
+      return true;
+    } else
+      return false;
+  }
+
+  public Set<T> get(T key) {
+    return table.get(key);
+  }
+  
+  public boolean containsKey(T o) {
+    return table.containsKey(o);
+  }
+
+  public boolean isGreaterThan(T a, T b) {
+
+    Set<T> neighborSet = get(a);
+    System.out.println("neightborSet of " + a + "=" + neighborSet);
+
+    if (neighborSet == null) {
+      return false;
+    } else if (neighborSet.contains(b)) {
+      return true;
+    } else {
+      boolean reachable = false;
+      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
+        T neighbor = iterator.next();
+        reachable = reachable || isGreaterThan(neighbor, b);
+      }
+      return reachable;
+    }
+  }
+
+  public T getGLB(Set<T> inputSet) {
+
+    Set<T> lowerSet = new HashSet<T>();
+
+    // get lower set of input locations
+    for (Iterator<T> iterator = inputSet.iterator(); iterator.hasNext();) {
+      T element = iterator.next();
+      lowerSet.addAll(getLowerSet(element, new HashSet<T>()));
+    }
+
+    // calculate the greatest element of lower set
+    // find an element A, where every lower bound B of lowerSet, B<A
+    for (Iterator<T> iterator = lowerSet.iterator(); iterator.hasNext();) {
+      T lowerElement = iterator.next();
+      boolean isGreaterThanAll = true;
+      for (Iterator<T> iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
+        T e = iterator2.next();
+        if (!lowerElement.equals(e)) {
+          if (!isGreaterThan(lowerElement, e)) {
+            isGreaterThanAll = false;
+            break;
+          }
+        }
+      }
+      if (isGreaterThanAll) {
+        return lowerElement;
+      }
+    }
+    return null;
+  }
+
+  public Set<T> getLowerSet(T element, Set<T> lowerSet) {
+
+    Set<T> neighborSet = get(element);
+    if (neighborSet != null) {
+      lowerSet.addAll(neighborSet);
+      for (Iterator<T> iterator = neighborSet.iterator(); iterator.hasNext();) {
+        T neighbor = iterator.next();
+        lowerSet = getLowerSet(neighbor, lowerSet);
+      }
+    }
+    return lowerSet;
+  }
+
+}
-- 
2.34.1