def test_empty_tree(self):
     """
     Test trie ctor, and that is doesn't match on "any" prefix.
     """
     t = StringTrie()
     for key in [u'', u'f', u'foo', u'foobar']:
         with self.assertRaises(KeyError):
             t.longest_prefix_value(key)

 def test_longest_prefix_1(self):
     """
     Test that keys are detected as prefix of themselfes.
     """
     t = StringTrie()
     test_keys = [u'f', u'foo', u'foobar', u'baz']
     for key in test_keys:
         t[key] = key
     for key in test_keys:
         self.assertEqual(t.longest_prefix_value(key), key)

    def test_longest_prefix_3(self):
        """
        Test non-matching prefix lookups.
        """
        t = StringTrie()

        for key in [u'x', u'fop', u'foobar']:
            t[key] = key

        for key in [u'y', u'yfoo', u'fox', u'fooba']:
            with self.assertRaises(KeyError):
                t.longest_prefix_value(key)

    def __init__(self, router, uri, permissions=None, default_permissions=None):
        """

        :param router: The router this role is defined on.
        :type router: obj
        :param uri: The URI of the role.
        :type uri: unicode
        :param permissions: A permissions configuration, e.g. a list
           of permission dicts like `{'uri': 'com.example.*', 'call': True}`
        :type permissions: list of dict
        :param default_permissions: The default permissions to apply when no other
            configured permission matches. The default permissions when not explicitly
            set is to deny all actions on all URIs!
        :type default_permissions: dict
        """
        RouterRole.__init__(self, router, uri)
        assert(permissions is None or isinstance(permissions, list))
        if permissions:
            for p in permissions:
                assert(isinstance(p, dict))
        assert(default_permissions is None or isinstance(default_permissions, dict))

        # default permissions (used when nothing else is matching)
        # note: default permissions have their matching URI and match policy set to None!
        if default_permissions:
            self._default = RouterPermissions.from_dict(default_permissions)
        else:
            self._default = RouterPermissions(None, None,
                                              call=False,
                                              register=False,
                                              publish=False,
                                              subscribe=False,
                                              disclose_caller=False,
                                              disclose_publisher=False,
                                              cache=True)

        # Trie of explicitly configured permissions
        self._permissions = StringTrie()
        self._wild_permissions = StringTrie()

        # for "wildcard" URIs, there will be a ".." in them somewhere,
        # and so we want to match on the biggest prefix
        # (i.e. everything to the left of the first "..")
        for obj in permissions or []:
            perms = RouterPermissions.from_dict(obj)
            if '..' in perms.uri:
                trunc = perms.uri[:perms.uri.index('..')]
                self._wild_permissions[trunc] = perms
            else:
                self._permissions[perms.uri] = perms

    def test_longest_prefix_4(self):
        """
        Test that a trie with an empty string as a key contained
        matches a non-empty prefix matching lookup.
        """
        self.skip = True
        # stored_key = u'x'  # this works (and of course it should!)
        stored_key = u''  # this blows up! (and it _should_ work)
        test_key = u'xyz'

        t = StringTrie()
        t[stored_key] = stored_key
        self.assertTrue(stored_key in t)
        self.assertTrue(test_key.startswith(stored_key))
        self.assertEqual(t.longest_prefix_value(test_key), stored_key)

    def __init__(self, router, uri, permissions=None, default_permissions=None):
        """
        Ctor.

        :param uri: The URI of the role.
        :type uri: str
        :param permissions: A permissions configuration, e.g. a list
           of permission dicts like `{'uri': 'com.example.*', 'call': True}`
        :type permissions: list
        """
        RouterRole.__init__(self, router, uri)
        self.permissions = permissions or []

        self._urimap = StringTrie()
        self._default = default_permissions or RouterPermissions('', True, False, False, False, False)

        for p in self.permissions:
            uri = p['uri']

            if len(uri) > 0 and uri[-1] == '*':
                match_by_prefix = True
                uri = uri[:-1]
            else:
                match_by_prefix = False

            perms = RouterPermissions(uri, match_by_prefix,
                                      call=p.get('call', False),
                                      register=p.get('register', False),
                                      publish=p.get('publish', False),
                                      subscribe=p.get('subscribe', False))

            if len(uri) > 0:
                self._urimap[uri] = perms
            else:
                self._default = perms

class FIB:
    def __init__(self):
        self.fib = StringTrie()
        self.fib["/mbandeira"] = "int1"
        self.fib["/cdrummond"] = "int2"

    def getIface(self, contentName):
        return self.fib.longest_prefix_value(contentName)

 def __init__(self, router_session_factory, config, reactor):
     self._router_session_factory = router_session_factory
     self._router_factory = router_session_factory._routerFactory
     self._options = config.get(u'options', {})
     self._realm = self._options.get(u'realm', None)
     self._reactor = reactor
     self._payload_mapping = StringTrie()
     for topic, pmap in self._options.get(u'payload_mapping', {}).items():
         self._set_payload_format(topic, pmap)

def filter_argv(argv, option_strings, *blacklist):
    ptree = StringTrie({v: i for i, v in enumerate(blacklist)})
    filtered = []
    boolean_args = set(option_strings)
    i = -1
    while i + 1 < len(argv):
        i += 1
        arg = argv[i]
        has_value = arg.startswith("-") and \
            not any(arg.startswith(b) for b in boolean_args) \
            and '=' not in arg and arg != "-"
        if ptree.longest_prefix(arg, None) is None:
            filtered.append(arg)
            if has_value:
                i += 1
                filtered.append(argv[i])
        elif has_value:
            i += 1
    return filtered

        def __init__(self, default_key=None):
            """

            Create a new key ring to hold public and private keys mapped from an URI space.
            """
            assert(default_key is None or isinstance(default_key, Key) or type(default_key == six.text_type))
            self._uri_to_key = StringTrie()
            if type(default_key) == six.text_type:
                default_key = Key(originator_priv=default_key, responder_priv=default_key)
            self._default_key = default_key

    def test_longest_prefix_2(self):
        """
        Test matching prefix lookups.
        """
        t = StringTrie()
        test_keys = [u'f', u'foo', u'foobar']
        for key in test_keys:
            t[key] = key

        test_keys = {
            u'foobarbaz': u'foobar',
            u'foobaz': u'foo',
            u'fool': u'foo',
            u'foo': u'foo',
            u'fob': u'f',
            u'fo': u'f',
            u'fx': u'f',
            u'f': u'f',
        }
        for key in test_keys:
            self.assertEqual(t.longest_prefix_value(key), test_keys[key])

class Suggester(object):
    def __init__(self):
        self.trie = None

    def update_trie(self, word_list):
        self.trie = StringTrie()
        for word in word_list:
            word = word.lower()
            self.trie[word] = word

    def search_prefix(self, prefix):
        return self.trie.values(prefix=prefix)

    def __init__(self, ordered=False):
        # flag indicating whether observers should be maintained in a SortedSet
        # or a regular set (unordered)
        self._ordered = ordered

        # map: URI => ExactUriObservation
        self._observations_exact = {}

        # map: URI => PrefixUriObservation
        self._observations_prefix = StringTrie()

        # map: URI => WildcardUriObservation
        self._observations_wildcard = WildcardTrieMatcher()

        # map: observation ID => UriObservation
        self._observation_id_to_observation = {}

    def __init__(self, router, uri, permissions=None, default_permissions=None):
        """

        :param router: The router this role is defined on.
        :type router: obj
        :param uri: The URI of the role.
        :type uri: unicode
        :param permissions: A permissions configuration, e.g. a list
           of permission dicts like `{'uri': 'com.example.*', 'call': True}`
        :type permissions: list of dict
        :param default_permissions: The default permissions to apply when no other
            configured permission matches. The default permissions when not explicitly
            set is to deny all actions on all URIs!
        :type default_permissions: dict
        """
        RouterRole.__init__(self, router, uri)
        assert(permissions is None or type(permissions) == list)
        if permissions:
            for p in permissions:
                assert(type(p) == dict)
        assert(default_permissions is None or type(default_permissions) == dict)

        # default permissions (used when nothing else is matching)
        # note: default permissions have their matching URI and match policy set to None!
        if default_permissions:
            self._default = RouterPermissions.from_dict(default_permissions)
        else:
            self._default = RouterPermissions(None, None,
                                              call=False,
                                              register=False,
                                              publish=False,
                                              subscribe=False,
                                              disclose_caller=False,
                                              disclose_publisher=False,
                                              cache=True)

        # Trie of explicitly configured permissions
        self._permissions = StringTrie()

        for obj in permissions or []:
            perms = RouterPermissions.from_dict(obj)
            self._permissions[perms.uri] = perms

    def __init__(self, ordered=False):
        # flag indicating whether observers should be maintained in a SortedSet
        # or a regular set (unordered)
        self._ordered = ordered

        # map: URI => ExactUriObservation
        self._observations_exact = {}

        # map: URI => PrefixUriObservation
        self._observations_prefix = StringTrie()

        # map: URI => WildcardUriObservation
        if True:
            # use a Trie-based implementation (supposed to be faster, but
            # otherwise compatible to the naive implementation below)
            self._observations_wildcard = WildcardTrieMatcher()
        else:
            self._observations_wildcard = WildcardMatcher()

        # map: observation ID => UriObservation
        self._observation_id_to_observation = {}

class RouterRoleStaticAuth(RouterRole):
    """
    A role on a router realm that is authorized using a static configuration.
    """

    def __init__(self, router, uri, permissions=None, default_permissions=None):
        """

        :param router: The router this role is defined on.
        :type router: obj
        :param uri: The URI of the role.
        :type uri: unicode
        :param permissions: A permissions configuration, e.g. a list
           of permission dicts like `{'uri': 'com.example.*', 'call': True}`
        :type permissions: list of dict
        :param default_permissions: The default permissions to apply when no other
            configured permission matches. The default permissions when not explicitly
            set is to deny all actions on all URIs!
        :type default_permissions: dict
        """
        RouterRole.__init__(self, router, uri)
        assert(permissions is None or type(permissions) == list)
        if permissions:
            for p in permissions:
                assert(type(p) == dict)
        assert(default_permissions is None or type(default_permissions) == dict)

        # default permissions (used when nothing else is matching)
        # note: default permissions have their matching URI and match policy set to None!
        if default_permissions:
            self._default = RouterPermissions.from_dict(default_permissions)
        else:
            self._default = RouterPermissions(None, None,
                                              call=False,
                                              register=False,
                                              publish=False,
                                              subscribe=False,
                                              disclose_caller=False,
                                              disclose_publisher=False,
                                              cache=True)

        # Trie of explicitly configured permissions
        self._permissions = StringTrie()

        for obj in permissions or []:
            perms = RouterPermissions.from_dict(obj)
            self._permissions[perms.uri] = perms

    def authorize(self, session, uri, action):
        """
        Authorize a session connected under this role to perform the given
        action on the given URI.

        :param session: The WAMP session that requests the action.
        :type session: Instance of :class:`autobahn.wamp.protocol.ApplicationSession`
        :param uri: The URI on which to perform the action.
        :type uri: str
        :param action: The action to be performed.
        :type action: str

        :return: bool -- Flag indicating whether session is authorized or not.
        """
        self.log.debug(
            "CrossbarRouterRoleStaticAuth.authorize {myuri} {uri} {action}",
            myuri=self.uri, uri=uri, action=action)

        try:
            # longest prefix match of the URI to be authorized against our Trie
            # of configured URIs for permissions
            permissions = self._permissions.longest_prefix_value(uri)

            # if there is a _prefix_ matching URI, check that this is actually the
            # match policy on the permission (otherwise, apply default permissions)!
            if permissions.match != u'prefix' and uri != permissions.uri:
                permissions = self._default

        except KeyError:
            # workaround because of https://bitbucket.org/gsakkis/pytrie/issues/4/string-keys-of-zero-length-are-not
            if u'' in self._permissions:
                permissions = self._permissions[u'']
            else:
                permissions = self._default

        if action == u'publish':
            return {
                u'allow': permissions.publish,
                u'disclose': permissions.disclose_publisher,
                u'cache': permissions.cache
            }

        elif action == u'subscribe':
            return {
                u'allow': permissions.subscribe,
                u'cache': permissions.cache
            }

        elif action == u'call':
            return {
                u'allow': permissions.call,
                u'disclose': permissions.disclose_caller,
#.........这里部分代码省略.........

class UriObservationMap(object):

    """
    Represents the current set of observations maintained by a broker/dealer.

    To test: trial crossbar.router.test.test_subscription
    """

    __slots__ = (
        "_ordered",
        "_observations_exact",
        "_observations_prefix",
        "_observations_wildcard",
        "_observation_id_to_observation",
    )

    def __init__(self, ordered=False):
        # flag indicating whether observers should be maintained in a SortedSet
        # or a regular set (unordered)
        self._ordered = ordered

        # map: URI => ExactUriObservation
        self._observations_exact = {}

        # map: URI => PrefixUriObservation
        self._observations_prefix = StringTrie()

        # map: URI => WildcardUriObservation
        if True:
            # use a Trie-based implementation (supposed to be faster, but
            # otherwise compatible to the naive implementation below)
            self._observations_wildcard = WildcardTrieMatcher()
        else:
            self._observations_wildcard = WildcardMatcher()

        # map: observation ID => UriObservation
        self._observation_id_to_observation = {}

    def __repr__(self):
        return "{}(_ordered={}, _observations_exact={}, _observations_wildcard={})".format(
            self.__class__.__name__,
            self._ordered,
            self._observations_exact,
            self._observations_prefix,
            self._observations_wildcard,
            self._observation_id_to_observation,
        )

    def add_observer(self, observer, uri, match=u"exact", extra=None):
        """
        Adds a observer to the observation set and returns the respective observation.

        :param observer: The observer to add (this can be any opaque object).
        :type observer: obj
        :param uri: The URI (or URI pattern) to add the observer to add to.
        :type uri: unicode
        :param match: The matching policy for observing, one of ``u"exact"``, ``u"prefix"`` or ``u"wildcard"``.
        :type match: unicode

        :returns: A tuple ``(observation, was_already_observed, was_first_observer)``. Here,
            ``observation`` is an instance of one of ``ExactUriObservation``, ``PrefixUriObservation`` or ``WildcardUriObservation``.
        :rtype: tuple
        """
        if not isinstance(uri, six.text_type):
            raise Exception("'uri' should be unicode, not {}".format(type(uri).__name__))

        if match == u"exact":

            # if the exact-matching URI isn't in our map, create a new observation
            #
            if uri not in self._observations_exact:
                self._observations_exact[uri] = ExactUriObservation(uri, ordered=self._ordered, extra=extra)
                is_first_observer = True
            else:
                is_first_observer = False

            # get the observation
            #
            observation = self._observations_exact[uri]

        elif match == u"prefix":

            # if the prefix-matching URI isn't in our map, create a new observation
            #
            if uri not in self._observations_prefix:
                self._observations_prefix[uri] = PrefixUriObservation(uri, ordered=self._ordered, extra=extra)
                is_first_observer = True
            else:
                is_first_observer = False

            # get the observation
            #
            observation = self._observations_prefix[uri]

        elif match == u"wildcard":

            # if the wildcard-matching URI isn't in our map, create a new observation
            #
            if uri not in self._observations_wildcard:
                self._observations_wildcard[uri] = WildcardUriObservation(uri, ordered=self._ordered, extra=extra)
#.........这里部分代码省略.........

    class KeyRing(object):
        """
        A keyring holds (cryptobox) public-private key pairs for use with WAMP-cryptobox payload
        encryption. The keyring can be set on a WAMP session and then transparently will get used
        for encrypting and decrypting WAMP message payloads.
        """

        @public
        def __init__(self, default_key=None):
            """

            Create a new key ring to hold public and private keys mapped from an URI space.
            """
            assert(default_key is None or isinstance(default_key, Key) or type(default_key == six.text_type))
            self._uri_to_key = StringTrie()
            if type(default_key) == six.text_type:
                default_key = Key(originator_priv=default_key, responder_priv=default_key)
            self._default_key = default_key

        @public
        def generate_key(self):
            """
            Generate a new private key and return a pair with the base64 encodings
            of (priv_key, pub_key).
            """
            key = PrivateKey.generate()
            priv_key = key.encode(encoder=Base64Encoder)
            pub_key = key.public_key.encode(encoder=Base64Encoder)
            return (u'{}'.format(priv_key), u'{}'.format(pub_key))

        @public
        def set_key(self, uri, key):
            """
            Add a key set for a given URI.
            """
            assert(type(uri) == six.text_type)
            assert(key is None or isinstance(key, Key) or type(key) == six.text_type)
            if type(key) == six.text_type:
                key = Key(originator_priv=key, responder_priv=key)
            if uri == u'':
                self._default_key = key
            else:
                if key is None:
                    if uri in self._uri_to_key:
                        del self._uri_to_key[uri]
                else:
                    self._uri_to_key[uri] = key

        @public
        def rotate_key(self, uri):
            assert(type(uri) == six.text_type)
            if uri in self._uri_to_key:
                self._uri_to_key[uri].rotate()
            else:
                self._uri_to_key[uri].rotate()

        def _get_box(self, is_originating, uri, match_exact=False):
            try:
                if match_exact:
                    key = self._uri_to_key[uri]
                else:
                    key = self._uri_to_key.longest_prefix_value(uri)
            except KeyError:
                if self._default_key:
                    key = self._default_key
                else:
                    return None

            if is_originating:
                return key.originator_box
            else:
                return key.responder_box

        @public
        def encode(self, is_originating, uri, args=None, kwargs=None):
            """
            Encrypt the given WAMP URI, args and kwargs into an EncodedPayload instance, or None
            if the URI should not be encrypted.
            """
            assert(type(is_originating) == bool)
            assert(type(uri) == six.text_type)
            assert(args is None or type(args) in (list, tuple))
            assert(kwargs is None or type(kwargs) == dict)

            box = self._get_box(is_originating, uri)

            if not box:
                # if we didn't find a crypto box, then return None, which
                # signals that the payload travel unencrypted (normal)
                return None

            payload = {
                u'uri': uri,
                u'args': args,
                u'kwargs': kwargs
            }
            nonce = random(Box.NONCE_SIZE)
            payload_ser = _json_dumps(payload).encode('utf8')

            payload_encr = box.encrypt(payload_ser, nonce, encoder=RawEncoder)
#.........这里部分代码省略.........

from pytrie import StringTrie as trie
from bitstring import BitArray

words = open('words.txt')
t = trie.fromkeys(words.read().splitlines())

def evaluate(target):
	good = BitArray(len(target)) # all characters that are part of a meaningful word
	bestLength = 0 # length of the longest word
	bestPattern = BitArray(len(target)) # characters that form the longest word

	for i in range(len(target)):
		match = t.longest_prefix(key=target[i:], default="")
		if len(match)>0:
			temp = BitArray(len(target))
			temp.set(1, range(i, i+len(match))) # set mathcing character positions to 1
			good.set(1, range(i, i+len(match))) # set mathcing character positions to 1
			if len(match)>bestLength:
				bestLength = len(match)
				bestPattern = temp
	return bestPattern, good

class WampMQTTServerFactory(Factory):

    log = make_logger()

    protocol = WampMQTTServerProtocol

    serializers = {
        u'json': JsonObjectSerializer(),
        u'msgpack': MsgPackObjectSerializer(),
        u'cbor': CBORObjectSerializer(),
        u'ubjson': UBJSONObjectSerializer(),
    }

    def __init__(self, router_session_factory, config, reactor):
        self._router_session_factory = router_session_factory
        self._router_factory = router_session_factory._routerFactory
        self._options = config.get(u'options', {})
        self._realm = self._options.get(u'realm', None)
        self._reactor = reactor
        self._payload_mapping = StringTrie()
        for topic, pmap in self._options.get(u'payload_mapping', {}).items():
            self._set_payload_format(topic, pmap)

    def buildProtocol(self, addr):
        protocol = self.protocol(self._reactor)
        protocol.factory = self
        return protocol

    def _get_payload_format(self, topic):
        """
        Map a WAMP topic URI to MQTT payload format.
        :param topic: WAMP URI.
        :type topic: str

        :returns: Payload format metadata.
        :rtype: dict
        """
        try:
            pmap = self._payload_mapping.longest_prefix_value(topic)
        except KeyError:
            return None
        else:
            return pmap

    def _set_payload_format(self, topic, pmap=None):
        if pmap is None:
            if topic in self._payload_mapping:
                del self._payload_mapping[topic]
        else:
            self._payload_mapping[topic] = pmap

    @inlineCallbacks
    def transform_wamp(self, topic, msg):
        # check for cached transformed payload
        cache_key = u'_{}_{}'.format(self.__class__.__name__, id(self))
        cached = msg._serialized.get(cache_key, None)

        if cached:
            payload_format, mapped_topic, payload = cached
            self.log.debug('using cached payload for {cache_key} in message {msg_id}!', msg_id=id(msg), cache_key=cache_key)
        else:
            # convert WAMP URI to MQTT topic
            mapped_topic = _wamp_topic_to_mqtt(topic)

            # for WAMP->MQTT, the payload mapping is determined from the
            # WAMP URI (not the transformed MQTT topic)
            payload_format = self._get_payload_format(topic)
            payload_format_type = payload_format[u'type']

            if payload_format_type == u'passthrough':
                payload = msg.payload

            elif payload_format_type == u'native':
                serializer = payload_format.get(u'serializer', None)
                payload = self._transform_wamp_native(serializer, msg)

            elif payload_format_type == u'dynamic':
                    encoder = payload_format.get(u'encoder', None)
                    codec_realm = payload_format.get(u'realm', self._realm)
                    payload = yield self._transform_wamp_dynamic(encoder, codec_realm, mapped_topic, topic, msg)
            else:
                raise Exception('payload format {} not implemented'.format(payload_format))

            msg._serialized[cache_key] = (payload_format, mapped_topic, payload)

        self.log.debug('transform_wamp({topic}, {msg}) -> payload_format={payload_format}, mapped_topic={mapped_topic}, payload={payload}', topic=topic, msg=msg, payload_format=payload_format, mapped_topic=mapped_topic, payload=payload)
        returnValue((payload_format, mapped_topic, payload))

    @inlineCallbacks
    def _transform_wamp_dynamic(self, encoder, codec_realm, mapped_topic, topic, msg):
        codec_session = self._router_factory.get(codec_realm)._realm.session
        payload = yield codec_session.call(encoder, mapped_topic, topic, msg.args, msg.kwargs)
        returnValue(payload)

    def _transform_wamp_native(self, serializer, msg):
        obj = {}
        for opt in [u'args',
                    u'kwargs',
                    u'exclude',
                    u'exclude_authid',
#.........这里部分代码省略.........