+++ /dev/null
-import java.util.*;\r
-\r
-public class Auto\r
-{\r
- public static void main(String args[]) \r
- {\r
- }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class Component extends Module\r
-{\r
- Component()\r
- {\r
- }\r
- Component(String n)\r
- {\r
- name=n;\r
- }\r
- String name;\r
-\r
- // These are the libs we want to build with.\r
- public Set<LibInst> buildLibs;\r
-\r
- public String name() { return name; }\r
-\r
- public boolean autoBuild()\r
- {\r
- // buildLibs must contain a list of libInstances. We need to check that\r
- // These libs meet certain criterea.\r
- if(!duplicateLibClasses(buildLibs).isEmpty())\r
- {\r
- // Error: The lib instance implement the same lib twice.\r
- return false;\r
- }\r
- if(! libClassesProduced(buildLibs).containsAll(consumesLibClasses))\r
- {\r
- // We can not cover the libclasses consumed with these instances.\r
- return false;\r
- }\r
- getConstructorOrder(buildLibs);\r
- getDestructorOrder(buildLibs);\r
-\r
- // Get PPI, Protocol, GUID, PCDs from the lib instances. These are all simple unions of\r
- // the corresponding sets in the modules. There is no ordering needed.\r
- // TODO\r
-\r
- return true;\r
- }\r
-\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-// A directed Acyclic Graph class. The main purpose is to provide a set of nodes\r
-// and the dependency relations between them. Then ask for a topological sort of\r
-// the nodes.\r
-\r
-public class DAG<Node>\r
-{\r
- // Constructor.\r
- DAG()\r
- {\r
- children = new HashMap<Node,Set<Node>>();\r
- }\r
-\r
- public Set<Node> nodes() { return children.keySet(); }\r
- public Set<Node> children(Node parent) { return children.get(parent); }\r
-\r
- // Add the relations from a compatible DAG to this one.\r
- public void add(DAG<Node> newDag)\r
- {\r
- for(Node parent : newDag.children.keySet())\r
- {\r
- children.put(parent, newDag.children(parent));\r
- }\r
- }\r
-\r
- // The central data structure is a one-to-many map. Each node is \r
- // treated as a parent. It is mapped to a list of its children. Leaf\r
- // nodes are also treated as parents and map to an empty list of\r
- // children.\r
- Map<Node,Set<Node>> children;\r
-\r
- public void remove(Collection<Node> nodes)\r
- {\r
- // Remove it as a parent\r
- for(Node node : nodes)\r
- {\r
- children.remove(node);\r
- }\r
-\r
- for(Set<Node> childlist : children.values())\r
- {\r
- // Remove it as a child\r
- childlist.removeAll(nodes);\r
- }\r
- }\r
-\r
- // Remove every occurrence of node from the DAG.\r
- public void remove(Node node)\r
- {\r
- // Remove it as a parent\r
- children.remove(node);\r
-\r
- for(Set<Node> childlist : children.values())\r
- {\r
- // Remove it as a child\r
- childlist.remove(node);\r
- }\r
- }\r
-\r
- // Return true iff parent is a direct parent of child.\r
- public boolean directDepends(Node parent, Node child)\r
- {\r
- return children.containsKey(parent) ? \r
- children(parent).contains(child) :\r
- false;\r
- }\r
-\r
- // Return true iff parent is a direct or indirect parent of child.\r
- // This is the transitive closure of the dependency relation.\r
- public boolean depends(Node parent, Node child)\r
- {\r
- if(!children.containsKey(parent))\r
- {\r
- return false;\r
- }\r
- if( directDepends(parent, child) )\r
- {\r
- return true;\r
- }\r
- else\r
- {\r
- for(Node descendent : children(parent) )\r
- {\r
- // Recursively call depends() to compute the transitive closure of\r
- // the relation.\r
- if(depends(descendent, child))\r
- {\r
- return true;\r
- }\r
- }\r
- return false;\r
- } \r
- }\r
-\r
- // Add a parent child relation to the dag. Fail if there is already\r
- // a dependency from the child to the parent. This implies a cycle.\r
- // Our invariant is that the DAG must never contain a cycle. That\r
- // way it lives up to its name.\r
- public void add(Node parent, Node child)\r
- {\r
- if(depends(child, parent))\r
- {\r
- System.out.format("Error: There is a cycle from %s to %s.\n", parent, child);\r
- return;\r
- }\r
- if(children.containsKey(parent))\r
- {\r
- children(parent).add(child);\r
- }\r
- else\r
- {\r
- Set<Node> cs = new HashSet<Node>();\r
- cs.add(child);\r
- children.put(parent, cs);\r
- }\r
- if(!children.containsKey(child))\r
- {\r
- children.put(child,new HashSet<Node>());\r
- }\r
- }\r
-\r
- // Perform a topological sort on the DAG.\r
- public List<Node> sort()\r
- {\r
- // Make an ordered list to hold the topo sort.\r
- List<Node> sorted = new LinkedList<Node>();\r
-\r
- // We add the leaves to the beginning of the list until\r
- // the sorted list contains all the nodes in the DAG.\r
- while(!sorted.containsAll(nodes()))\r
- {\r
- // Ignoring the ones we have found, what are the leaves of this\r
- // DAG?\r
- Set<Node> leaves = leaves(sorted);\r
- // Put the new leaves at the beginning of the list.\r
- sorted.addAll(0, leaves);\r
- }\r
- return sorted;\r
- }\r
-\r
- // Return the set of nodes that have no children. Pretend\r
- // the nodes in the exclude list are not present.\r
- public Set<Node> leaves(Collection<Node> exclude)\r
- {\r
- Set<Node> leaves=new HashSet<Node>();\r
- for(Node parent : children.keySet())\r
- {\r
- if(exclude.contains(parent))\r
- {\r
- continue;\r
- }\r
- // If the children of parent are a subset of the exclude set,\r
- // then parent is a leaf.\r
- if(exclude.containsAll(children(parent)))\r
- {\r
- leaves.add(parent);\r
- }\r
- }\r
- return leaves;\r
- }\r
-\r
- // Return the set of nodes that have no children.\r
- public Set<Node> leaves()\r
- {\r
- Set<Node> leaves=new HashSet<Node>();\r
- for(Node parent : children.keySet())\r
- {\r
- if( children(parent).isEmpty())\r
- {\r
- leaves.add(parent);\r
- }\r
- }\r
- return leaves;\r
- }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class Database\r
-{\r
- Database()\r
- {\r
- }\r
- Database(String n)\r
- {\r
- name=n;\r
- }\r
- public String name;\r
- Map<String,Set<Package>> packages;\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class GuidDecl\r
-{\r
- GuidDecl()\r
- {\r
- }\r
- GuidDecl(String n)\r
- {\r
- name=n;\r
- }\r
- public String name;\r
- public String cName;\r
- public String guid;\r
- public String name() { return name; }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class LibClass\r
-{\r
- LibClass()\r
- {\r
- }\r
- LibClass(String n)\r
- {\r
- name=n;\r
- }\r
- String name;\r
- public String name() { return name; }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class LibInst extends Module\r
-{\r
- LibInst()\r
- {\r
- }\r
- LibInst(String n)\r
- {\r
- name=n;\r
- }\r
-\r
- public Set<LibClass> producesLibClasses;\r
-\r
- public String constructorName, destructorName;\r
-\r
- public boolean autoBuild()\r
- {\r
- // A simple compile, without link.\r
- return true;\r
- }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class Module\r
-{\r
- Module()\r
- {\r
- }\r
- Module(String n)\r
- {\r
- name=n;\r
- }\r
- String name;\r
-\r
- public String name() { return name; }\r
-\r
- public Set<LibClass> consumesLibClasses;\r
-\r
- // The set of packages that this module depends upon.\r
- Set<Package> packageDepends;\r
- public Set<Package> packageDeps() { return packageDepends; }\r
-\r
- public boolean autoBuild()\r
- {\r
- // This should be implemented in the derived class.\r
- return true;\r
- }\r
-\r
- // Make sure that each class in this set of libclasses is declared in one\r
- // of the packages that this module depends on.\r
- public boolean validateLibClasses(Set<LibClass> classes)\r
- {\r
- for(LibClass lc : classes)\r
- {\r
- // Assume we will not find it.\r
- boolean found = false;\r
-\r
- for(Package p : packageDepends)\r
- {\r
- if(p.libClassDecls.contains(lc))\r
- {\r
- found=true;\r
- break;\r
- }\r
- }\r
- if(found == false)\r
- {\r
- // Error: This LibClass is not found in any of our Packages.\r
- return false;\r
- }\r
- }\r
- // Well, we never came up empty handed, so it looks good.\r
- return true;\r
- }\r
-\r
- public Set<LibClass> libClassesProduced(Collection<LibInst> instances)\r
- {\r
- // given a set of lib instances, what is the set of lib classes produced?\r
-\r
- Set<LibClass> classes = new HashSet<LibClass>();\r
-\r
- for(LibInst li : instances)\r
- {\r
- classes.addAll(li.producesLibClasses);\r
- }\r
- return classes;\r
- }\r
-\r
- // Search the given set of lib instance to see if, among them, they\r
- // produce the same LibClass more than once.\r
- public Set<LibClass> duplicateLibClasses(Set<LibInst> libs)\r
- {\r
- // Return true iff each class produced is produced only once.\r
-\r
- List<LibClass> classes = new LinkedList<LibClass>();\r
- Set<LibClass> dups = new HashSet<LibClass>();\r
-\r
- for(LibInst li : libs)\r
- {\r
- classes.addAll(li.producesLibClasses);\r
- }\r
-\r
- for(LibClass c : classes)\r
- {\r
- for(LibClass inner : classes)\r
- {\r
- if(c.equals(inner))\r
- {\r
- dups.add(c);\r
- }\r
- }\r
- }\r
- return dups;\r
- }\r
-\r
- public Set<LibInst> getProducers(LibClass lc, Set<LibInst> libs)\r
- {\r
- // Return the subset of the given libs that produce this LibClass.\r
-\r
- Set<LibInst> producers = new HashSet<LibInst>();\r
-\r
- for(LibInst li : libs)\r
- {\r
- if(li.producesLibClasses.contains(lc))\r
- {\r
- producers.add(li);\r
- }\r
- }\r
- return producers;\r
- }\r
- \r
- // \r
- // The central dependency relationship between library instances is as follows.\r
- // A LibInst "A" depends upon LibInst "B" if, and only if, there exists a LibClass\r
- // "C" such that A consumes C and B produces C. This is the partial order over which \r
- // we construct a Directed Acyclic Graph (DAG). The DAG can be used to detect\r
- // cycles in the depends relation (which are illegal) and it can be used to implement a\r
- // topological sort which is a total ordering over LibInstances. This total order on \r
- // lib instances is what is needed in order to call the constructors and destructors\r
- // in the proper sequence.\r
- //\r
- public DAG<LibInst> makeDAG(Set<LibInst> libs)\r
- {\r
- DAG<LibInst> dag = new DAG<LibInst>();\r
-\r
- if(duplicateLibClasses(libs).size()>0)\r
- {\r
- System.out.format("Error: The library instances implement at least one "\r
- + "library class more than once.\n");\r
- }\r
-\r
- for(LibInst consumer : libs)\r
- {\r
- // Find all the producers for each LC that li consumes. \r
- for(LibClass lc : consumer.consumesLibClasses )\r
- {\r
- Set<LibInst> producers = getProducers(lc, libs);\r
- if(producers.isEmpty())\r
- {\r
- System.out.format("Error: Unmet dependency libclass:%s .", lc.name() );\r
- return null;\r
- }\r
-\r
- // There is exactly one lib inst that produces this class.\r
- LibInst producer = producers.iterator().next();\r
-\r
- // Now we are ready to add the dependency to the dag. It will flag \r
- // circular dependencies for us.\r
- dag.add(consumer, producer);\r
- }\r
- }\r
- return dag;\r
- }\r
-\r
- // As you evaluate each node in the graph (starting with the module node), you\r
- // must call the constructors for all the child nodes before you call the\r
- // constructor for the current node. \r
- public List<LibInst> getConstructorOrder(Set<LibInst> libs)\r
- {\r
- List<LibInst> rev = new LinkedList<LibInst>();\r
-\r
- for(LibInst li : getDestructorOrder(libs))\r
- rev.add(0, li); \r
-\r
- return rev;\r
- }\r
-\r
- // The destructor order is exactly the reverese of the constructor order.\r
- // As you evaluate each node in the graph (starting with the module node), you\r
- // must call the destructor for the all the parent nodes before calling the\r
- // destructors for the current node, and then call the destructors for all the\r
- // child nodes. \r
- public List<LibInst> getDestructorOrder(Set<LibInst> libs)\r
- {\r
- DAG<LibInst> dag = makeDAG(libs);\r
-\r
- return dag.sort();\r
- }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class Package\r
-{\r
- Package()\r
- {\r
- }\r
- Package(String n)\r
- {\r
- name=n;\r
- }\r
- public String name;\r
-\r
- public Set<LibClass> libClassDecls;\r
- public Set<GuidDecl> guidDecls;\r
- public Set<PpiDecl> ppiDecls;\r
- public Set<ProtocolDecl> protocolDecls;\r
- public Set<Module> modules;\r
- public Set<Package> depends;\r
-\r
- public void genBuild()\r
- {\r
- for(Module m : modules)\r
- {\r
- m.autoBuild();\r
- }\r
- }\r
-\r
- // Figure out what this package depends on based on what the modules \r
- // depend on.\r
- public void calculateDependencies()\r
- {\r
- depends = new HashSet<Package>();\r
- for(Module m : modules)\r
- {\r
- depends.addAll(m.packageDeps());\r
- }\r
- }\r
-\r
- public void makeJar(String name) {};\r
-\r
- public void addModule(Module m) {};\r
- public void removeModule(Module m) {};\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class PpiDecl\r
-{\r
- PpiDecl()\r
- {\r
- }\r
- PpiDecl(String n)\r
- {\r
- name=n;\r
- }\r
- public String name;\r
- public String cName;\r
- public String guid;\r
- public String name() { return name; }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class ProtocolDecl\r
-{\r
- ProtocolDecl()\r
- {\r
- }\r
- ProtocolDecl(String n)\r
- {\r
- name=n;\r
- }\r
- public String name;\r
- public String cName;\r
- public String guid;\r
- public String name() { return name; }\r
-}\r
+++ /dev/null
-import java.util.*;\r
-\r
-public class TSort\r
-{\r
- public static void main(String args[]) \r
- {\r
- DAG<String> dag = new DAG<String>();\r
- int i;\r
-\r
- if(args.length % 2==1)\r
- {\r
- System.out.println("Error: Odd number of elements");\r
- return;\r
- }\r
- for(i=0; i< args.length/2; i++)\r
- {\r
- dag.add(args[i*2], args[i*2+1]);\r
- // System.out.println(pair.left);\r
- // System.out.println(pair.right);\r
- }\r
- System.out.println(dag.sort().toString());\r
- System.out.println(dag.sort().toString());\r
- }\r
-}\r
+++ /dev/null
-<?xml version="1.0"?>\r
-<!--\r
-Copyright (c) 2006, Intel Corporation\r
-All rights reserved. This program and the accompanying materials\r
-are licensed and made available under the terms and conditions of the BSD License\r
-which accompanies this distribution. The full text of the license may be found at\r
-http://opensource.org/licenses/bsd-license.php\r
-\r
-THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
-WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
--->\r
-<project name="proto" default="all">\r
- <taskdef resource="net/sf/antcontrib/antlib.xml"/>\r
- <target name="all">\r
- <javac srcdir=".">\r
- <compilerarg value="-Xlint"/>\r
- </javac>\r
- <jar destfile="Prototype.jar"\r
- basedir="."\r
- includes="*.class"\r
- excludes="**/Not this one.class"\r
- />\r
- </target>\r
-\r
- <target name="clean"/>\r
- <target name="cleanall"/>\r
-</project>\r