Index: fedd/compose.py
===================================================================
--- fedd/compose.py	(revision 22c88c956759b6a2d630e1d746edb67650649ae1)
+++ fedd/compose.py	(revision b0581ac699bd4c012eb507f877f47964e7fef136)
@@ -10,61 +10,148 @@
 
 class constraint:
-    def __init__(self, required=False, accepts=None, provides=None):
+    def __init__(self, name=None, required=False, accepts=None, provides=None,
+	    match=None):
+	self.name = name
 	self.required = required
 	self.accepts = accepts or []
 	self.provides = provides or []
+	self.match = match
 
     def __str__(self):
-	return "%s:%s:%s" % (self.required, ",".join(self.provides), 
-		",".join(self.accepts))
-
-
-def add_to_map(exp, mark):
-    valid_marks = ('stub', 'transit')
-
+	return "%s:%s:%s:%s" % (self.name, self.required,
+		",".join(self.provides), ",".join(self.accepts))
+
+
+def add_to_map(exp, mark, provides, accepts):
+    """
+    Create a constraint from a string of the form
+	name:required:provides:accepts
+    where name is the name of the node in the current topology, if the second
+    field is "required" this is a required constraint, a list of attributes
+    that this connection point provides and a list that it accepts.  The
+    provides and accepts lists are comma-separated.  Note that the string
+    passed in as exp should have whitespace removed. The constraint is added to
+    the mark dict under the name key and entries in the provides and accepts
+    are made to teh constraing for each attribute that it provides or accepts.
+    """
     nn, r, p, a = exp.split(":")
     p = p.split(",")
     a = a.split(",")
-    mark[nn] = constraint(r == 'required', p, a)
-
-def annotate_topo(top, mark):
-    def make_new_name(names):
-	i = 0
-	n = "mark%d" % i
-	while n in names:
-	    i += 1
-	    n = "mark%d" % i
-	names.add(n)
-	return n
-
-    snames = set([ s.name for s in top.substrates ])
-
+    c = constraint(name=nn, required=(r == 'required'), provides=p, accepts=a)
+    mark[nn] = c
+
+    for attr, dict in ((p, provides), (a, accepts)):
+	for a in attr:
+	    if a not in dict: dict[a] = [c]
+	    else: dict[a].append(c)
+
+def make_new_name(names, prefix="name"):
+    """
+    Generate an identifier not present in names by appending an integer to
+    prefix.  The new name is inserted into names and returned.
+    """
+    i = 0
+    n = "%s%d" % (prefix,i)
+    while n in names:
+	i += 1
+	n = "%s%d" % (prefix,i)
+    names.add(n)
+    return n
+
+def add_interfaces(top, mark):
+    """
+    Add unconnected interfaces to the nodes whose names are keys in the mark
+    dict.  As the interface is added change the name field of the contstraint
+    in mark into a tuple containing the node name, interface name, and topology
+    in which they reside.
+    """
     for e in top.elements:
-	for n in e.name:
-	    if n in mark:
-		if all([ not i.get_attribute('export') for i in e.interface]):
-		    con = mark[n]
-		    inames = set([x.name for x in e.interface])
-		    sn = make_new_name(snames)
-		    ii = make_new_name(inames)
-		    s = topdl.Substrate(name=sn)
-		    i = topdl.Interface(substrate=sn, name=ii, element=e,
-			    attribute=[
-				topdl.Attribute(attribute='composition_point',
-				    value='True'),
-				topdl.Attribute(attribute='required', 
-				    value = "%s" % con.required),
-				topdl.Attribute(attribute='provides', 
-				    value=",".join(con.provides)),
-				topdl.Attribute(attribute='accepts', 
-				    value=",".join(con.accepts)),
-				]
-			    )
-		    e.interface.append(i)
-		    top.substrates.append(s)
-
-    top.incorporate_elements()
+	if e.name in mark:
+	    con = mark[e.name]
+	    ii = make_new_name(set([x.name for x in e.interface]), "inf")
+	    e.interface.append(
+		    topdl.Interface(substrate=[], name=ii, element=e))
+	    con.name = (e.name, ii, top)
+
+def localize_names(top, names, marks):
+    """
+    Take a topology and rename any substrates or elements that share a name
+    with an existing computer or substrate.  Keep the original name as a
+    localized_name attribute.  In addition, remap any constraints or interfaces
+    that point to the old name over to the new one.  Constraints are found in
+    the marks dict, indexed by node name.  Those constraints name attributes
+    have already been converted to triples (node name, interface name,
+    topology) so only the node name needs to be changed.
+    """
+    sub_map = { }
+    for s in top.substrates:
+	s.set_attribute('localized_name', s.name)
+	if s.name in names:
+	    sub_map[s.name] = n = make_new_name(names, "substrate")
+	    s.name = n
+	else:
+	    names.add(s.name)
+
+    for e in [ e for e in top.elements if isinstance(e, topdl.Computer)]:
+	e.set_attribute('localized_name', e.name)
+	if e.name in names:
+	    nn= make_new_name(names, "computer")
+	    if e.name in marks:
+		n, i, t = marks[e.name].name
+		marks[e.name].name = (nn, i, t)
+	    e.name = nn
+	else:
+	    names.add(e.name)
+
+	# Interface mapping.  The list comprehension creates a list of
+	# substrate names where each element in the list is replaced by the
+	# entry in sub_map indexed by it if present and left alone otherwise.
+	for i in e.interface:
+	    i.substrate = [ sub_map.get(ii, ii) for ii in i.substrate ]
+
+def meet_constraints(candidates, provides, accepts):
+    """
+    Try to meet all the constraints in candidates using the information in the
+    provides and accepts dicts (which index constraints that provide or accept
+    the given attribute). A constraint is met if it can be matched with another
+    constraint that provides an attribute that the first constraint accepts.
+    Only one match per pair is allowed, and we always prefer matching a
+    required constraint to an unreqired one.  If all the candidates can be
+    matches, return True and return False otherwise.
+    """
+    got_all = True
+    for c in candidates:
+	if not c.match:
+	    match = None
+	    for a in c.accepts:
+		for can in provides.get(a,[]):
+		    # A constraint cannot satisfy itself, nor do we allow loops
+		    # within the same topology.  This also excludes matched
+		    # constraints.
+		    if can.name != c.name and can.name[2] != c.name[2] and \
+			    not can.match:
+			match = can
+			# Within providers, prefer matches against required
+			# composition points
+			if can.required:
+			    break
+		# Within acceptance categories, prefer matches against required
+		# composition points
+		if match and match.required:
+		    break
+
+	    # Done checking all possible matches.
+	    if match:
+		match.match = c
+		c.match = match
+	    else:
+		got_all = False
+    return got_all
 
 def remote_ns2topdl(uri, desc, cert):
+    """
+    Call a remote service to convert the ns2 to topdl (and in fact all the way
+    to a topdl.Topology.
+    """
 
     req = { 'description' : { 'ns2description': desc }, }
@@ -85,4 +172,53 @@
 	return None
 
+def connect_composition_points(top, contraints):
+    """
+    top is a topology containing copies of all the topologies represented in
+    the contsraints, flattened into one name space.  This routine inserts the
+    additional substrates required to interconnect the topology as described by
+    the constraints.  After the links are made, unused connection points are
+    purged.
+    """
+    done = set()
+    for c in constraints:
+	if c not in done and c.match:
+	    # c is an unprocessed matched constraint.  Create a substrate
+	    # and attach it to the interfaces named by c and c.match.
+	    sn = make_new_name(names, "sub")
+	    s = topdl.Substrate(name=sn)
+	    connected = 0
+	    # Walk through all the computers in the topology
+	    for e in [ e for e in top.elements \
+		    if isinstance(e, topdl.Computer)]:
+		# if the computer matches the computer and interface name in
+		# either c or c.match, connect it.  Once both computers have
+		# been found and connected, exit the loop walking through all
+		# computers.
+		for comp, inf in (c.name[0:2], c.match.name[0:2]):
+		    if e.name == comp:
+			for i in e.interface:
+			    if i.name == inf:
+				i.substrate.append(sn)
+				connected += 1
+				break
+			break
+		# Connected both, so add the substrate to the topology
+		if connected == 2: 
+		    top.substrates.append(s)
+		    break
+	    # c and c.match have been processed, so add them to the done set
+	    done.add(c)
+	    done.add(c.match)
+
+    # All interfaces with matched constraints have been connected.  Cull any
+    # interfaces unassigned to a substrate
+    for e in [ e for e in top.elements if isinstance(e, topdl.Computer)]:
+	if any([ not i.substrate for i in e.interface]):
+	    e.interface = [ i for i in e.interface if i.substrate ]
+
+    top.incorporate_elements()
+
+
+
 const_re = re.compile("\s*#\s*COMPOSITION:\s*([^:]+:[^:]+:.*)")
 
@@ -94,4 +230,5 @@
 
 opts, args = parser.parse_args()
+
 
 if opts.cert:
@@ -102,4 +239,9 @@
     cert = None
 
+comps = [ ]
+names = set()
+constraints = [ ]
+provides = { }
+accepts = { }
 for fn in args:
     marks = { }
@@ -111,15 +253,34 @@
 	    m = const_re.search(l)
 	    if m:
-		add_to_map(re.sub('\s', '', m.group(1)), marks)
+		add_to_map(re.sub('\s', '', m.group(1)), marks, provides, 
+			accepts)
     except EnvironmentError, e:
-	print >>sys.stderr, "Error on %S: %s" % (fn, e)
-
-    print marks
+	print >>sys.stderr, "Error on %s: %s" % (fn, e)
+	continue
 
     top = remote_ns2topdl(opts.url, contents, cert)
-
-    if top: 
-	annotate_topo(top, marks)
-	print topdl.topology_to_xml(top)
-    else:
-	sys.exit("Topology conversion failed on %s" % fn)
+    add_interfaces(top, marks)
+    localize_names(top, names, marks)
+    top.incorporate_elements()
+    constraints.extend(marks.values())
+    comps.append(top)
+
+# Now the various components live in the same namespace and are marked with
+# their composition requirements. 
+
+if not meet_constraints([c for c in constraints if c.required], 
+	provides, accepts):
+    sys.exit("Could not meet all required constraints")
+meet_constraints([ c for c in constraints if not c.match ], provides, accepts)
+
+# Make a topology containing all elements and substrates from components that
+# had matches.
+comp = topdl.Topology()
+for t in set([ c.name[2] for c in constraints if c.match]):
+    comp.elements.extend([e.clone() for e in t.elements])
+    comp.substrates.extend([s.clone() for s in t.substrates])
+
+# Add substrates and connections corresponding to composition points
+connect_composition_points(comp, constraints)
+
+print topdl.topology_to_xml(comp, top='experiment')
