#! /usr/bin/python2.7
#
# Compute our KCC topology
#
# Copyright (C) Dave Craft 2011
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

import os
import sys
import random

# ensure we get messages out immediately, so they get in the samba logs,
# and don't get swallowed by a timeout
os.environ['PYTHONUNBUFFERED'] = '1'

# forcing GMT avoids a problem in some timezones with kerberos. Both MIT
# heimdal can get mutual authentication errors due to the 24 second difference
# between UTC and GMT when using some zone files (eg. the PDT zone from
# the US)
os.environ["TZ"] = "GMT"

# Find right directory when running from source tree


import optparse
import logging

from samba import (
    getopt as options,
    Ldb,
    ldb,
    dsdb,
    read_and_sub_file)
from samba.auth import system_session
from samba.samdb import SamDB
from samba.dcerpc import drsuapi
from samba.kcc_utils import *

class KCC(object):
    """The Knowledge Consistency Checker class.

    A container for objects and methods allowing a run of the KCC.  Produces a
    set of connections in the samdb for which the Distributed Replication
    Service can then utilize to replicate naming contexts
    """
    def __init__(self):
        """Initializes the partitions class which can hold
        our local DCs partitions or all the partitions in
        the forest
        """
        self.part_table = {}    # partition objects
        self.site_table = {}
        self.transport_table = {}
        self.sitelink_table = {}

        # Used in inter-site topology computation.  A list
        # of connections (by NTDSConnection object) that are
        # to be kept when pruning un-needed NTDS Connections
        self.keep_connection_list = []

        self.my_dsa_dnstr = None  # My dsa DN
        self.my_dsa = None  # My dsa object

        self.my_site_dnstr = None
        self.my_site = None

        self.samdb = None

    def load_all_transports(self):
        """Loads the inter-site transport objects for Sites

        ::returns: Raises an Exception on error
        """
        try:
            res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
                                    self.samdb.get_config_basedn(),
                                    scope=ldb.SCOPE_SUBTREE,
                                    expression="(objectClass=interSiteTransport)")
        except ldb.LdbError, (enum, estr):
            raise Exception("Unable to find inter-site transports - (%s)" %
                    estr)

        for msg in res:
            dnstr = str(msg.dn)

            # already loaded
            if dnstr in self.transport_table.keys():
                continue

            transport = Transport(dnstr)

            transport.load_transport(self.samdb)

            # Assign this transport to table
            # and index by dn
            self.transport_table[dnstr] = transport

    def load_all_sitelinks(self):
        """Loads the inter-site siteLink objects

        ::returns: Raises an Exception on error
        """
        try:
            res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
                                    self.samdb.get_config_basedn(),
                                    scope=ldb.SCOPE_SUBTREE,
                                    expression="(objectClass=siteLink)")
        except ldb.LdbError, (enum, estr):
            raise Exception("Unable to find inter-site siteLinks - (%s)" % estr)

        for msg in res:
            dnstr = str(msg.dn)

            # already loaded
            if dnstr in self.sitelink_table.keys():
                continue

            sitelink = SiteLink(dnstr)

            sitelink.load_sitelink(self.samdb)

            # Assign this siteLink to table
            # and index by dn
            self.sitelink_table[dnstr] = sitelink

    def get_sitelink(self, site1_dnstr, site2_dnstr):
        """Return the siteLink (if it exists) that connects the
        two input site DNs
        """
        for sitelink in self.sitelink_table.values():
            if sitelink.is_sitelink(site1_dnstr, site2_dnstr):
                return sitelink
        return None

    def load_my_site(self):
        """Loads the Site class for the local DSA

        ::returns: Raises an Exception on error
        """
        self.my_site_dnstr = "CN=%s,CN=Sites,%s" % (
                              self.samdb.server_site_name(),
                              self.samdb.get_config_basedn())
        site = Site(self.my_site_dnstr)
        site.load_site(self.samdb)

        self.site_table[self.my_site_dnstr] = site
        self.my_site = site

    def load_all_sites(self):
        """Discover all sites and instantiate and load each
        NTDS Site settings.

        ::returns: Raises an Exception on error
        """
        try:
            res = self.samdb.search("CN=Sites,%s" %
                                    self.samdb.get_config_basedn(),
                                    scope=ldb.SCOPE_SUBTREE,
                                    expression="(objectClass=site)")
        except ldb.LdbError, (enum, estr):
            raise Exception("Unable to find sites - (%s)" % estr)

        for msg in res:
            sitestr = str(msg.dn)

            # already loaded
            if sitestr in self.site_table.keys():
                continue

            site = Site(sitestr)
            site.load_site(self.samdb)

            self.site_table[sitestr] = site

    def load_my_dsa(self):
        """Discover my nTDSDSA dn thru the rootDSE entry

        ::returns: Raises an Exception on error.
        """
        dn = ldb.Dn(self.samdb, "")
        try:
            res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
                                    attrs=["dsServiceName"])
        except ldb.LdbError, (enum, estr):
            raise Exception("Unable to find my nTDSDSA - (%s)" % estr)

        self.my_dsa_dnstr = res[0]["dsServiceName"][0]
        self.my_dsa = self.my_site.get_dsa(self.my_dsa_dnstr)

    def load_all_partitions(self):
        """Discover all NCs thru the Partitions dn and
        instantiate and load the NCs.

        Each NC is inserted into the part_table by partition
        dn string (not the nCName dn string)

        ::returns: Raises an Exception on error
        """
        try:
            res = self.samdb.search("CN=Partitions,%s" %
                                    self.samdb.get_config_basedn(),
                                    scope=ldb.SCOPE_SUBTREE,
                                    expression="(objectClass=crossRef)")
        except ldb.LdbError, (enum, estr):
            raise Exception("Unable to find partitions - (%s)" % estr)

        for msg in res:
            partstr = str(msg.dn)

            # already loaded
            if partstr in self.part_table.keys():
                continue

            part = Partition(partstr)

            part.load_partition(self.samdb)
            self.part_table[partstr] = part

    def should_be_present_test(self):
        """Enumerate all loaded partitions and DSAs in local
        site and test if NC should be present as replica
        """
        for partdn, part in self.part_table.items():
            for dsadn, dsa in self.my_site.dsa_table.items():
               needed, ro, partial = part.should_be_present(dsa)
               logger.info("dsadn:%s\nncdn:%s\nneeded=%s:ro=%s:partial=%s\n" %
                           (dsadn, part.nc_dnstr, needed, ro, partial))

    def refresh_failed_links_connections(self):
        # XXX - not implemented yet
        pass

    def is_stale_link_connection(self, target_dsa):
        """Returns False if no tuple z exists in the kCCFailedLinks or
        kCCFailedConnections variables such that z.UUIDDsa is the
        objectGUID of the target dsa, z.FailureCount > 0, and
        the current time - z.TimeFirstFailure > 2 hours.
        """
        # XXX - not implemented yet
        return False

    def remove_unneeded_failed_links_connections(self):
        # XXX - not implemented yet
        pass

    def remove_unneeded_ntdsconn(self, all_connected):
        """Removes unneeded NTDS Connections after computation
        of KCC intra and inter-site topology has finished.
        """
        mydsa = self.my_dsa

        # Loop thru connections
        for cn_dnstr, cn_conn in mydsa.connect_table.items():

            s_dnstr = cn_conn.get_from_dnstr()
            if s_dnstr is None:
                cn_conn.to_be_deleted = True
                continue

            # Get the source DSA no matter what site
            s_dsa = self.get_dsa(s_dnstr)

            # Check if the DSA is in our site
            if self.my_site.same_site(s_dsa):
                same_site = True
            else:
                same_site = False

            # Given an nTDSConnection object cn, if the DC with the
            # nTDSDSA object dc that is the parent object of cn and
            # the DC with the nTDSDA object referenced by cn!fromServer
            # are in the same site, the KCC on dc deletes cn if all of
            # the following are true:
            #
            # Bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options.
            #
            # No site settings object s exists for the local DC's site, or
            # bit NTDSSETTINGS_OPT_IS_TOPL_CLEANUP_DISABLED is clear in
            # s!options.
            #
            # Another nTDSConnection object cn2 exists such that cn and
            # cn2 have the same parent object, cn!fromServer = cn2!fromServer,
            # and either
            #
            #     cn!whenCreated < cn2!whenCreated
            #
            #     cn!whenCreated = cn2!whenCreated and
            #     cn!objectGUID < cn2!objectGUID
            #
            # Bit NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options
            if same_site:
                if not cn_conn.is_generated():
                    continue

                if self.my_site.is_cleanup_ntdsconn_disabled():
                    continue

                # Loop thru connections looking for a duplicate that
                # fulfills the previous criteria
                lesser = False

                for cn2_dnstr, cn2_conn in mydsa.connect_table.items():
                    if cn2_conn is cn_conn:
                        continue

                    s2_dnstr = cn2_conn.get_from_dnstr()
                    if s2_dnstr is None:
                        continue

                    # If the NTDS Connections has a different
                    # fromServer field then no match
                    if s2_dnstr != s_dnstr:
                        continue

                    lesser = (cn_conn.whenCreated < cn2_conn.whenCreated or
                              (cn_conn.whenCreated == cn2_conn.whenCreated and
                               cmp(cn_conn.guid, cn2_conn.guid) < 0))

                    if lesser:
                        break

                if lesser and not cn_conn.is_rodc_topology():
                    cn_conn.to_be_deleted = True

            # Given an nTDSConnection object cn, if the DC with the nTDSDSA
            # object dc that is the parent object of cn and the DC with
            # the nTDSDSA object referenced by cn!fromServer are in
            # different sites, a KCC acting as an ISTG in dc's site
            # deletes cn if all of the following are true:
            #
            #     Bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options.
            #
            #     cn!fromServer references an nTDSDSA object for a DC
            #     in a site other than the local DC's site.
            #
            #     The keepConnections sequence returned by
            #     CreateIntersiteConnections() does not contain
            #     cn!objectGUID, or cn is "superseded by" (see below)
            #     another nTDSConnection cn2 and keepConnections
            #     contains cn2!objectGUID.
            #
            #     The return value of CreateIntersiteConnections()
            #     was true.
            #
            #     Bit NTDSCONN_OPT_RODC_TOPOLOGY is clear in
            #     cn!options
            #
            else: # different site

                if not mydsa.is_istg():
                    continue

                if not cn_conn.is_generated():
                    continue

                if self.keep_connection(cn_conn):
                    continue

                # XXX - To be implemented

                if not all_connected:
                    continue

                if not cn_conn.is_rodc_topology():
                    cn_conn.to_be_deleted = True


        if opts.readonly:
            for dnstr, connect in mydsa.connect_table.items():
                if connect.to_be_deleted:
                    logger.info("TO BE DELETED:\n%s" % connect)
                if connect.to_be_added:
                    logger.info("TO BE ADDED:\n%s" % connect)

            # Peform deletion from our tables but perform
            # no database modification
            mydsa.commit_connections(self.samdb, ro=True)
        else:
            # Commit any modified connections
            mydsa.commit_connections(self.samdb)

    def get_dsa_by_guidstr(self, guidstr):
        """Given a DSA guid string, consule all sites looking
        for the corresponding DSA and return it.
        """
        for site in self.site_table.values():
            dsa = site.get_dsa_by_guidstr(guidstr)
            if dsa is not None:
                return dsa
        return None

    def get_dsa(self, dnstr):
        """Given a DSA dn string, consule all sites looking
        for the corresponding DSA and return it.
        """
        for site in self.site_table.values():
            dsa = site.get_dsa(dnstr)
            if dsa is not None:
                return dsa
        return None

    def modify_repsFrom(self, n_rep, t_repsFrom, s_rep, s_dsa, cn_conn):
        """Update t_repsFrom if necessary to satisfy requirements. Such
        updates are typically required when the IDL_DRSGetNCChanges
        server has moved from one site to another--for example, to
        enable compression when the server is moved from the
        client's site to another site.

        :param n_rep: NC replica we need
        :param t_repsFrom: repsFrom tuple to modify
        :param s_rep: NC replica at source DSA
        :param s_dsa: source DSA
        :param cn_conn: Local DSA NTDSConnection child

        ::returns: (update) bit field containing which portion of the
           repsFrom was modified.  This bit field is suitable as input
           to IDL_DRSReplicaModify ulModifyFields element, as it consists
           of these bits:
               drsuapi.DRSUAPI_DRS_UPDATE_SCHEDULE
               drsuapi.DRSUAPI_DRS_UPDATE_FLAGS
               drsuapi.DRSUAPI_DRS_UPDATE_ADDRESS
        """
        s_dnstr = s_dsa.dsa_dnstr
        update = 0x0

        if self.my_site.same_site(s_dsa):
            same_site = True
        else:
            same_site = False

        times = cn_conn.convert_schedule_to_repltimes()

        # if schedule doesn't match then update and modify
        if times != t_repsFrom.schedule:
            t_repsFrom.schedule = times

        # Bit DRS_PER_SYNC is set in replicaFlags if and only
        # if nTDSConnection schedule has a value v that specifies
        # scheduled replication is to be performed at least once
        # per week.
        if cn_conn.is_schedule_minimum_once_per_week():

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_PER_SYNC) == 0x0:
                t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_PER_SYNC

        # Bit DRS_INIT_SYNC is set in t.replicaFlags if and only
        # if the source DSA and the local DC's nTDSDSA object are
        # in the same site or source dsa is the FSMO role owner
        # of one or more FSMO roles in the NC replica.
        if same_site or n_rep.is_fsmo_role_owner(s_dnstr):

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_INIT_SYNC) == 0x0:
                t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_INIT_SYNC

        # If bit NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT is set in
        # cn!options, bit DRS_NEVER_NOTIFY is set in t.replicaFlags
        # if and only if bit NTDSCONN_OPT_USE_NOTIFY is clear in
        # cn!options. Otherwise, bit DRS_NEVER_NOTIFY is set in
        # t.replicaFlags if and only if s and the local DC's
        # nTDSDSA object are in different sites.
        if (cn_conn.options & dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) != 0x0:

            if (cn_conn.option & dsdb.NTDSCONN_OPT_USE_NOTIFY) == 0x0:

                if (t_repsFrom.replica_flags &
                    drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0:
                    t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_NEVER_NOTIFY

        elif not same_site:

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0:
                t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_NEVER_NOTIFY

        # Bit DRS_USE_COMPRESSION is set in t.replicaFlags if
        # and only if s and the local DC's nTDSDSA object are
        # not in the same site and the
        # NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION bit is
        # clear in cn!options
        if (not same_site and
           (cn_conn.options &
            dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) == 0x0):

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_USE_COMPRESSION) == 0x0:
                t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_USE_COMPRESSION

        # Bit DRS_TWOWAY_SYNC is set in t.replicaFlags if and only
        # if bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options.
        if (cn_conn.options & dsdb.NTDSCONN_OPT_TWOWAY_SYNC) != 0x0:

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_TWOWAY_SYNC) == 0x0:
                t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_TWOWAY_SYNC

        # Bits DRS_DISABLE_AUTO_SYNC and DRS_DISABLE_PERIODIC_SYNC are
        # set in t.replicaFlags if and only if cn!enabledConnection = false.
        if not cn_conn.is_enabled():

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC) == 0x0:
                t_repsFrom.replica_flags |= \
                    drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC) == 0x0:
                t_repsFrom.replica_flags |= \
                    drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC

        # If s and the local DC's nTDSDSA object are in the same site,
        # cn!transportType has no value, or the RDN of cn!transportType
        # is CN=IP:
        #
        #     Bit DRS_MAIL_REP in t.replicaFlags is clear.
        #
        #     t.uuidTransport = NULL GUID.
        #
        #     t.uuidDsa = The GUID-based DNS name of s.
        #
        # Otherwise:
        #
        #     Bit DRS_MAIL_REP in t.replicaFlags is set.
        #
        #     If x is the object with dsname cn!transportType,
        #     t.uuidTransport = x!objectGUID.
        #
        #     Let a be the attribute identified by
        #     x!transportAddressAttribute. If a is
        #     the dNSHostName attribute, t.uuidDsa = the GUID-based
        #      DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
        #
        # It appears that the first statement i.e.
        #
        #     "If s and the local DC's nTDSDSA object are in the same
        #      site, cn!transportType has no value, or the RDN of
        #      cn!transportType is CN=IP:"
        #
        # could be a slightly tighter statement if it had an "or"
        # between each condition.  I believe this should
        # be interpreted as:
        #
        #     IF (same-site) OR (no-value) OR (type-ip)
        #
        # because IP should be the primary transport mechanism
        # (even in inter-site) and the absense of the transportType
        # attribute should always imply IP no matter if its multi-site
        #
        # NOTE MS-TECH INCORRECT:
        #
        #     All indications point to these statements above being
        #     incorrectly stated:
        #
        #         t.uuidDsa = The GUID-based DNS name of s.
        #
        #         Let a be the attribute identified by
        #         x!transportAddressAttribute. If a is
        #         the dNSHostName attribute, t.uuidDsa = the GUID-based
        #         DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
        #
        #     because the uuidDSA is a GUID and not a GUID-base DNS
        #     name.  Nor can uuidDsa hold (s!parent)!a if not
        #     dNSHostName.  What should have been said is:
        #
        #         t.naDsa = The GUID-based DNS name of s
        #
        #     That would also be correct if transportAddressAttribute
        #     were "mailAddress" because (naDsa) can also correctly
        #     hold the SMTP ISM service address.
        #
        nastr = "%s._msdcs.%s" % (s_dsa.dsa_guid, self.samdb.forest_dns_name())

        # We're not currently supporting SMTP replication
        # so is_smtp_replication_available() is currently
        # always returning False
        if (same_site or
            cn_conn.transport_dnstr is None or
            cn_conn.transport_dnstr.find("CN=IP") == 0 or
            not is_smtp_replication_available()):

            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_MAIL_REP) != 0x0:
                t_repsFrom.replica_flags &= ~drsuapi.DRSUAPI_DRS_MAIL_REP

            null_guid = misc.GUID()
            if (t_repsFrom.transport_guid is None or
                t_repsFrom.transport_guid != null_guid):
                t_repsFrom.transport_guid = null_guid

            # See (NOTE MS-TECH INCORRECT) above
            if t_repsFrom.version == 0x1:
                if t_repsFrom.dns_name1 is None or \
                   t_repsFrom.dns_name1 != nastr:
                    t_repsFrom.dns_name1 = nastr
            else:
                if t_repsFrom.dns_name1 is None or \
                   t_repsFrom.dns_name2 is None or \
                   t_repsFrom.dns_name1 != nastr or \
                   t_repsFrom.dns_name2 != nastr:
                    t_repsFrom.dns_name1 = nastr
                    t_repsFrom.dns_name2 = nastr

        else:
            if (t_repsFrom.replica_flags &
                drsuapi.DRSUAPI_DRS_MAIL_REP) == 0x0:
                t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_MAIL_REP

            # We have a transport type but its not an
            # object in the database
            if cn_conn.transport_dnstr not in self.transport_table.keys():
                raise Exception("Missing inter-site transport - (%s)" %
                                cn_conn.transport_dnstr)

            x_transport = self.transport_table[cn_conn.transport_dnstr]

            if t_repsFrom.transport_guid != x_transport.guid:
                t_repsFrom.transport_guid = x_transport.guid

            # See (NOTE MS-TECH INCORRECT) above
            if x_transport.address_attr == "dNSHostName":

                if t_repsFrom.version == 0x1:
                    if t_repsFrom.dns_name1 is None or \
                       t_repsFrom.dns_name1 != nastr:
                        t_repsFrom.dns_name1 = nastr
                else:
                    if t_repsFrom.dns_name1 is None or \
                       t_repsFrom.dns_name2 is None or \
                       t_repsFrom.dns_name1 != nastr or \
                       t_repsFrom.dns_name2 != nastr:
                        t_repsFrom.dns_name1 = nastr
                        t_repsFrom.dns_name2 = nastr

            else:
                # MS tech specification says we retrieve the named
                # attribute in "transportAddressAttribute" from the parent of
                # the DSA object
                try:
                    pdnstr = s_dsa.get_parent_dnstr()
                    attrs = [ x_transport.address_attr ]

                    res = self.samdb.search(base=pdnstr, scope=ldb.SCOPE_BASE,
                                            attrs=attrs)
                except ldb.ldbError, (enum, estr):
                    raise Exception \
                        ("Unable to find attr (%s) for (%s) - (%s)" %
                         (x_transport.address_attr, pdnstr, estr))

                msg = res[0]
                nastr = str(msg[x_transport.address_attr][0])

                # See (NOTE MS-TECH INCORRECT) above
                if t_repsFrom.version == 0x1:
                    if t_repsFrom.dns_name1 is None or \
                       t_repsFrom.dns_name1 != nastr:
                        t_repsFrom.dns_name1 = nastr
                else:
                    if t_repsFrom.dns_name1 is None or \
                       t_repsFrom.dns_name2 is None or \
                       t_repsFrom.dns_name1 != nastr or \
                       t_repsFrom.dns_name2 != nastr:

                        t_repsFrom.dns_name1 = nastr
                        t_repsFrom.dns_name2 = nastr

        if t_repsFrom.is_modified():
            logger.debug("modify_repsFrom(): %s" % t_repsFrom)

    def is_repsFrom_implied(self, n_rep, cn_conn):
        """Given a NC replica and NTDS Connection, determine if the connection
        implies a repsFrom tuple should be present from the source DSA listed
        in the connection to the naming context

        :param n_rep: NC replica
        :param conn: NTDS Connection
        ::returns (True || False), source DSA:
        """
        # NTDS Connection must satisfy all the following criteria
        # to imply a repsFrom tuple is needed:
        #
        #    cn!enabledConnection = true.
        #    cn!options does not contain NTDSCONN_OPT_RODC_TOPOLOGY.
        #    cn!fromServer references an nTDSDSA object.
        s_dsa = None

        if cn_conn.is_enabled() and not cn_conn.is_rodc_topology():

            s_dnstr = cn_conn.get_from_dnstr()
            if s_dnstr is not None:
                s_dsa = self.get_dsa(s_dnstr)

            # No DSA matching this source DN string?
            if s_dsa is None:
                return False, None

        # To imply a repsFrom tuple is needed, each of these
        # must be True:
        #
        #     An NC replica of the NC "is present" on the DC to
        #     which the nTDSDSA object referenced by cn!fromServer
        #     corresponds.
        #
        #     An NC replica of the NC "should be present" on
        #     the local DC
        s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)

        if s_rep is None or not s_rep.is_present():
            return False, None

        # To imply a repsFrom tuple is needed, each of these
        # must be True:
        #
        #     The NC replica on the DC referenced by cn!fromServer is
        #     a writable replica or the NC replica that "should be
        #     present" on the local DC is a partial replica.
        #
        #     The NC is not a domain NC, the NC replica that
        #     "should be present" on the local DC is a partial
        #     replica, cn!transportType has no value, or
        #     cn!transportType has an RDN of CN=IP.
        #
        implied = (not s_rep.is_ro() or n_rep.is_partial()) and \
                  (not n_rep.is_domain() or
                   n_rep.is_partial() or
                   cn_conn.transport_dnstr is None or
                   cn_conn.transport_dnstr.find("CN=IP") == 0)

        if implied:
            return True, s_dsa
        else:
            return False, None

    def translate_ntdsconn(self):
        """This function adjusts values of repsFrom abstract attributes of NC
        replicas on the local DC to match those implied by
        nTDSConnection objects.
        """
        logger.debug("translate_ntdsconn(): enter")

        if self.my_dsa.is_translate_ntdsconn_disabled():
            return

        current_rep_table, needed_rep_table = self.my_dsa.get_rep_tables()

        # Filled in with replicas we currently have that need deleting
        delete_rep_table = {}

        # We're using the MS notation names here to allow
        # correlation back to the published algorithm.
        #
        # n_rep      - NC replica (n)
        # t_repsFrom - tuple (t) in n!repsFrom
        # s_dsa      - Source DSA of the replica. Defined as nTDSDSA
        #              object (s) such that (s!objectGUID = t.uuidDsa)
        #              In our IDL representation of repsFrom the (uuidDsa)
        #              attribute is called (source_dsa_obj_guid)
        # cn_conn    - (cn) is nTDSConnection object and child of the local DC's
        #              nTDSDSA object and (cn!fromServer = s)
        # s_rep      - source DSA replica of n
        #
        # If we have the replica and its not needed
        # then we add it to the "to be deleted" list.
        for dnstr, n_rep in current_rep_table.items():
            if dnstr not in needed_rep_table.keys():
                delete_rep_table[dnstr] = n_rep

        # Now perform the scan of replicas we'll need
        # and compare any current repsFrom against the
        # connections
        for dnstr, n_rep in needed_rep_table.items():

            # load any repsFrom and fsmo roles as we'll
            # need them during connection translation
            n_rep.load_repsFrom(self.samdb)
            n_rep.load_fsmo_roles(self.samdb)

            # Loop thru the existing repsFrom tupples (if any)
            for i, t_repsFrom in enumerate(n_rep.rep_repsFrom):

                # for each tuple t in n!repsFrom, let s be the nTDSDSA
                # object such that s!objectGUID = t.uuidDsa
                guidstr = str(t_repsFrom.source_dsa_obj_guid)
                s_dsa = self.get_dsa_by_guidstr(guidstr)

                # Source dsa is gone from config (strange)
                # so cleanup stale repsFrom for unlisted DSA
                if s_dsa is None:
                    logger.debug("repsFrom source DSA guid (%s) not found" %
                                 guidstr)
                    t_repsFrom.to_be_deleted = True
                    continue

                s_dnstr = s_dsa.dsa_dnstr

                # Retrieve my DSAs connection object (if it exists)
                # that specifies the fromServer equivalent to
                # the DSA that is specified in the repsFrom source
                cn_conn = self.my_dsa.get_connection_by_from_dnstr(s_dnstr)

                # Let (cn) be the nTDSConnection object such that (cn)
                # is a child of the local DC's nTDSDSA object and
                # (cn!fromServer = s) and (cn!options) does not contain
                # NTDSCONN_OPT_RODC_TOPOLOGY or NULL if no such (cn) exists.
                if cn_conn and cn_conn.is_rodc_topology():
                    cn_conn = None

                # KCC removes this repsFrom tuple if any of the following
                # is true:
                #     cn = NULL.
                #
                #     No NC replica of the NC "is present" on DSA that
                #     would be source of replica
                #
                #     A writable replica of the NC "should be present" on
                #     the local DC, but a partial replica "is present" on
                #     the source DSA
                s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)

                if cn_conn is None or \
                   s_rep is None or not s_rep.is_present() or \
                   (not n_rep.is_ro() and s_rep.is_partial()):

                    t_repsFrom.to_be_deleted = True
                    continue

                # If the KCC did not remove t from n!repsFrom, it updates t
                self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)

            # Loop thru connections and add implied repsFrom tuples
            # for each NTDSConnection under our local DSA if the
            # repsFrom is not already present
            for cn_dnstr, cn_conn in self.my_dsa.connect_table.items():

                implied, s_dsa = self.is_repsFrom_implied(n_rep, cn_conn)
                if not implied:
                    continue

                # Loop thru the existing repsFrom tupples (if any) and
                # if we already have a tuple for this connection then
                # no need to proceed to add.  It will have been changed
                # to have the correct attributes above
                for i, t_repsFrom in enumerate(n_rep.rep_repsFrom):

                     guidstr = str(t_repsFrom.source_dsa_obj_guid)
                     if s_dsa is self.get_dsa_by_guidstr(guidstr):
                         s_dsa = None
                         break

                if s_dsa is None:
                    continue

                # Create a new RepsFromTo and proceed to modify
                # it according to specification
                t_repsFrom = RepsFromTo(n_rep.nc_dnstr)

                t_repsFrom.source_dsa_obj_guid = s_dsa.dsa_guid

                self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)

                # Add to our NC repsFrom as this is newly computed
                if t_repsFrom.is_modified():
                    n_rep.rep_repsFrom.append(t_repsFrom)

            if opts.readonly:
                # Display any to be deleted or modified repsFrom
                text = n_rep.dumpstr_to_be_deleted()
                if text:
                    logger.info("TO BE DELETED:\n%s" % text)
                text = n_rep.dumpstr_to_be_modified()
                if text:
                    logger.info("TO BE MODIFIED:\n%s" % text)

                # Peform deletion from our tables but perform
                # no database modification
                n_rep.commit_repsFrom(self.samdb, ro=True)
            else:
                # Commit any modified repsFrom to the NC replica
                n_rep.commit_repsFrom(self.samdb)

    def keep_connection(self, cn_conn):
        """Determines if the connection is meant to be kept during the
        pruning of unneeded connections operation.

        Consults the keep_connection_list[] which was built during
        intersite NC replica graph computation.

        ::returns (True or False): if (True) connection should not be pruned
        """
        if cn_conn in self.keep_connection_list:
            return True
        return False

    def merge_failed_links(self):
        """Merge of kCCFailedLinks and kCCFailedLinks from bridgeheads.
        The KCC on a writable DC attempts to merge the link and connection
        failure information from bridgehead DCs in its own site to help it
        identify failed bridgehead DCs.
        """
        # MS-TECH Ref 6.2.2.3.2 Merge of kCCFailedLinks and kCCFailedLinks
        #     from Bridgeheads

        # XXX - not implemented yet

    def setup_graph(self):
        """Set up a GRAPH, populated with a VERTEX for each site
        object, a MULTIEDGE for each siteLink object, and a
        MUTLIEDGESET for each siteLinkBridge object (or implied
        siteLinkBridge).

        ::returns: a new graph
        """
        # XXX - not implemented yet
        return None

    def get_bridgehead(self, site, part, transport, partial_ok, detect_failed):
        """Get a bridghead DC.

        :param site: site object representing for which a bridgehead
            DC is desired.
        :param part: crossRef for NC to replicate.
        :param transport: interSiteTransport object for replication
            traffic.
        :param partial_ok: True if a DC containing a partial
            replica or a full replica will suffice, False if only
            a full replica will suffice.
        :param detect_failed: True to detect failed DCs and route
            replication traffic around them, False to assume no DC
            has failed.
        ::returns: dsa object for the bridgehead DC or None
        """

        bhs = self.get_all_bridgeheads(site, part, transport,
                                       partial_ok, detect_failed)
        if len(bhs) == 0:
            logger.debug("get_bridgehead: exit\n\tsitedn=%s\n\tbhdn=None" %
                         site.site_dnstr)
            return None
        else:
            logger.debug("get_bridgehead: exit\n\tsitedn=%s\n\tbhdn=%s" %
                         (site.site_dnstr, bhs[0].dsa_dnstr))
            return bhs[0]

    def get_all_bridgeheads(self, site, part, transport,
                            partial_ok, detect_failed):
        """Get all bridghead DCs satisfying the given criteria

        :param site: site object representing the site for which
            bridgehead DCs are desired.
        :param part: partition for NC to replicate.
        :param transport: interSiteTransport object for
            replication traffic.
        :param partial_ok: True if a DC containing a partial
            replica or a full replica will suffice, False if
            only a full replica will suffice.
        :param detect_ok: True to detect failed DCs and route
            replication traffic around them, FALSE to assume
            no DC has failed.
        ::returns: list of dsa object for available bridgehead
            DCs or None
        """

        bhs = []

        logger.debug("get_all_bridgeheads: %s" % transport)

        for key, dsa in site.dsa_table.items():

            pdnstr = dsa.get_parent_dnstr()

            # IF t!bridgeheadServerListBL has one or more values and
            # t!bridgeheadServerListBL does not contain a reference
            # to the parent object of dc then skip dc
            if (len(transport.bridgehead_list) != 0 and
                pdnstr not in transport.bridgehead_list):
                continue

            # IF dc is in the same site as the local DC
            #    IF a replica of cr!nCName is not in the set of NC replicas
            #    that "should be present" on dc or a partial replica of the
            #    NC "should be present" but partialReplicasOkay = FALSE
            #        Skip dc
            if self.my_site.same_site(dsa):
                needed, ro, partial = part.should_be_present(dsa)
                if not needed or (partial and not partial_ok):
                    continue

            # ELSE
            #     IF an NC replica of cr!nCName is not in the set of NC
            #     replicas that "are present" on dc or a partial replica of
            #     the NC "is present" but partialReplicasOkay = FALSE
            #          Skip dc
            else:
                rep = dsa.get_current_replica(part.nc_dnstr)
                if rep is None or (rep.is_partial() and not partial_ok):
                    continue

            # IF AmIRODC() and cr!nCName corresponds to default NC then
            #     Let dsaobj be the nTDSDSA object of the dc
            #     IF  dsaobj.msDS-Behavior-Version < DS_BEHAVIOR_WIN2008
            #         Skip dc
            if self.my_dsa.is_ro() and part.is_default():
                if not dsa.is_minimum_behavior(DS_BEHAVIOR_WIN2008):
                    continue

            # IF t!name != "IP" and the parent object of dc has no value for
            # the attribute specified by t!transportAddressAttribute
            #     Skip dc
            if transport.name != "IP":
                # MS tech specification says we retrieve the named
                # attribute in "transportAddressAttribute" from the parent
                # of the DSA object
                try:
                    attrs = [ transport.address_attr ]

                    res = self.samdb.search(base=pdnstr, scope=ldb.SCOPE_BASE,
                                            attrs=attrs)
                except ldb.ldbError, (enum, estr):
                    continue

                msg = res[0]
                nastr = str(msg[transport.address_attr][0])

            # IF BridgeheadDCFailed(dc!objectGUID, detectFailedDCs) = TRUE
            #     Skip dc
            if self.is_bridgehead_failed(dsa, detect_failed):
                continue

            logger.debug("get_all_bridgeheads: dsadn=%s" % dsa.dsa_dnstr)
            bhs.append(dsa)

        # IF bit NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED is set in
        # s!options
        #    SORT bhs such that all GC servers precede DCs that are not GC
        #    servers, and otherwise by ascending objectGUID
        # ELSE
        #    SORT bhs in a random order
        if site.is_random_bridgehead_disabled():
            bhs.sort(sort_dsa_by_gc_and_guid)
        else:
            random.shuffle(bhs)

        return bhs


    def is_bridgehead_failed(self, dsa, detect_failed):
        """Determine whether a given DC is known to be in a failed state
        ::returns: True if and only if the DC should be considered failed
        """
        # XXX - not implemented yet
        return False

    def create_connection(self, part, rbh, rsite, transport,
                          lbh, lsite, link_opt, link_sched,
                          partial_ok, detect_failed):
        """Create an nTDSConnection object with the given parameters
        if one does not already exist.

        :param part: crossRef object for the NC to replicate.
        :param rbh: nTDSDSA object for DC to act as the
            IDL_DRSGetNCChanges server (which is in a site other
            than the local DC's site).
        :param rsite: site of the rbh
        :param transport: interSiteTransport object for the transport
            to use for replication traffic.
        :param lbh: nTDSDSA object for DC to act as the
            IDL_DRSGetNCChanges client (which is in the local DC's site).
        :param lsite: site of the lbh
        :param link_opt: Replication parameters (aggregated siteLink options, etc.)
        :param link_sched: Schedule specifying the times at which
            to begin replicating.
        :partial_ok: True if bridgehead DCs containing partial
            replicas of the NC are acceptable.
        :param detect_failed: True to detect failed DCs and route
            replication traffic around them, FALSE to assume no DC
            has failed.
        """
        rbhs_all = self.get_all_bridgeheads(rsite, part, transport,
                                            partial_ok, False)

        # MS-TECH says to compute rbhs_avail but then doesn't use it
        # rbhs_avail = self.get_all_bridgeheads(rsite, part, transport,
        #                                        partial_ok, detect_failed)

        lbhs_all = self.get_all_bridgeheads(lsite, part, transport,
                                            partial_ok, False)

        # MS-TECH says to compute lbhs_avail but then doesn't use it
        # lbhs_avail = self.get_all_bridgeheads(lsite, part, transport,
        #                                       partial_ok, detect_failed)

        # FOR each nTDSConnection object cn such that the parent of cn is
        # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
        for ldsa in lbhs_all:
            for cn in ldsa.connect_table.values():

                rdsa = None
                for rdsa in rbhs_all:
                    if cn.from_dnstr == rdsa.dsa_dnstr:
                        break

                if rdsa is None:
                    continue

                # IF bit NTDSCONN_OPT_IS_GENERATED is set in cn!options and
                # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options and
                # cn!transportType references t
                if (cn.is_generated() and not cn.is_rodc_topology() and
                    cn.transport_dnstr == transport.dnstr):

                    # IF bit NTDSCONN_OPT_USER_OWNED_SCHEDULE is clear in
                    # cn!options and cn!schedule != sch
                    #     Perform an originating update to set cn!schedule to
                    #     sched
                    if (not cn.is_user_owned_schedule() and
                        not cn.is_equivalent_schedule(link_sched)):
                        cn.schedule = link_sched
                        cn.set_modified(True)

                    # IF bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
                    # NTDSCONN_OPT_USE_NOTIFY are set in cn
                    if cn.is_override_notify_default() and \
                       cn.is_use_notify():

                        # IF bit NTDSSITELINK_OPT_USE_NOTIFY is clear in
                        # ri.Options
                        #    Perform an originating update to clear bits
                        #    NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
                        #    NTDSCONN_OPT_USE_NOTIFY in cn!options
                        if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) == 0:
                            cn.options &= \
                                ~(dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
                                  dsdb.NTDSCONN_OPT_USE_NOTIFY)
                            cn.set_modified(True)

                    # ELSE
                    else:

                        # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in
                        # ri.Options
                        #     Perform an originating update to set bits
                        #     NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
                        #     NTDSCONN_OPT_USE_NOTIFY in cn!options
                        if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
                            cn.options |= \
                                (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
                                 dsdb.NTDSCONN_OPT_USE_NOTIFY)
                            cn.set_modified(True)


                    # IF bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options
                    if cn.is_twoway_sync():

                        # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is clear in
                        # ri.Options
                        #     Perform an originating update to clear bit
                        #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
                        if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) == 0:
                            cn.options &= ~dsdb.NTDSCONN_OPT_TWOWAY_SYNC
                            cn.set_modified(True)

                    # ELSE
                    else:

                        # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in
                        # ri.Options
                        #     Perform an originating update to set bit
                        #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
                        if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
                            cn.options |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
                            cn.set_modified(True)


                    # IF bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION is set
                    # in cn!options
                    if cn.is_intersite_compression_disabled():

                        # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is clear
                        # in ri.Options
                        #     Perform an originating update to clear bit
                        #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
                        #     cn!options
                        if (link_opt &
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            