source: fedd/compose.py @ ec9962b

#!/usr/local/bin/python

import sys
import re
import os
import random

from optparse import OptionParser, OptionValueError
from federation.remote_service import service_caller
from federation import topdl

class constraint:
    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:%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(",")
    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:
        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 randomize_constraint_order(indexes):
    """
    Randomly reorder the lists of constraints that provides and accepts hold.
    """
    if not isinstance(indexes, tuple):
        indexes = (indexes,)

    for idx in indexes:
        for k in idx.keys():
            random.shuffle(idx[k])

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 }, }

    try:
        r = service_caller('Ns2Topdl')(uri, req, cert)
    except:
        return None

    if r.has_key('Ns2TopdlResponseBody'):
        r = r['Ns2TopdlResponseBody']
        ed = r.get('experimentdescription', None)
        if 'topdldescription' in ed:
            return topdl.Topology(**ed['topdldescription'])
        else:
            return None
    else:
        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()

def import_tcl_constraints(marks, provides, accepts, contents):
    """
    Contents is a list containing the lines of an annotated ns2 file.  This
    routine extracts the constraint comment lines and convertes them into
    constraints in the namespace of the tcl experiment, as well as inserting
    them in the accepts and provides indices.
    """
    for l in contents:
        m = const_re.search(l)
        if m:
            add_to_map(re.sub('\s', '', m.group(1)), marks, provides, 
                    accepts)


def multi_callback(option, opt_str, value, parser):
    """
    Parse a --multifile command line option.  The parameter is of the form
    filename,count.  This splits the argument at the rightmost comma and
    inserts the filename, count tuple into the "files" option.  It handles a
    couple error cases, too.  This is an optparse.OptionParser callback.
    """
    idx = value.rfind(',')
    if idx != -1:
        try:
            parser.values.files.append((value[0:idx], int(value[idx+1:])))
        except ValueError, e:
            raise OptionValueError("Can't convert %s to int in multifile (%s)" \
                    % (value[idx+1:], value))
    else:
        raise OptionValueError("Bad format (need a comma) for multifile: %s" \
                % value)



# Main line begins

const_re = re.compile("\s*#\s*COMPOSITION:\s*([^:]+:[^:]+:.*)")

parser = OptionParser()
parser.add_option('--url', dest='url', default="http://localhost:13235",
        help='url of ns2 to topdl service')
parser.add_option('--certfile', dest='cert', default=None,
        help='Certificate to use as identity')
parser.add_option('--seed', dest='seed', type='int', default=None,
        help='Random number seed')
parser.add_option('--multifile', dest='files', default=[], type='string', 
        action='callback', callback=multi_callback, 
        help="Include file multiple times")

opts, args = parser.parse_args()

if opts.cert:
    cert = opts.cert
elif os.access(os.path.expanduser("~/.ssl/emulab.pem"), os.R_OK):
    cert = os.path.expanduser("~/.ssl/emulab.pem")
else:
    cert = None

random.seed(opts.seed)

files = opts.files
files.extend([ (a, 1) for a in args])

comps = [ ]
names = set()
constraints = [ ]
provides = { }
accepts = { }
for fn, cnt in files:
    marks = { }
    try:
        f = open(fn, "r")
        contents = [ l for l in f ]
    except EnvironmentError, e:
        print >>sys.stderr, "Error on %s: %s" % (fn, e)
        continue

    top = remote_ns2topdl(opts.url, "".join(contents), cert)
    if not top:
        sys.exit("Cannot create topology from: %s" % fn)

    for i in range(0, cnt):
        t = top.clone()
        import_tcl_constraints(marks, provides, accepts, contents)
        add_interfaces(t, marks)
        localize_names(t, names, marks)
        t.incorporate_elements()
        constraints.extend(marks.values())
        comps.append(t)

# Let the user know if they messed up on specifying constraints.
if any([ not isinstance(c.name, tuple) for c in constraints]):
    print >>sys.stderr, "nodes not found for constraints on %s" % \
            ",".join([ c.name for c in constraints \
            if isinstance(c.name, basestring)])
    constraints = [ c for c in constraints if isinstance(c.name, tuple )]

# Mix up the constraint indexes 
randomize_constraint_order((provides, accepts))

# 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')