1from __future__ import absolute_import
2from __future__ import division
3from __future__ import print_function
4
5import logging
6
7import os
8from unicodedata import category
9
10from six import string_types
11from six import text_type
12
13from six.moves.urllib.request import pathname2url
14from six.moves.urllib.parse import urldefrag
15from six.moves.urllib.parse import urljoin
16
17from rdflib.term import URIRef, Variable, _XSD_PFX, _is_valid_uri
18
19__doc__ = """
20===================
21Namespace Utilities
22===================
23
24RDFLib provides mechanisms for managing Namespaces.
25
26In particular, there is a :class:`~rdflib.namespace.Namespace` class
27that takes as its argument the base URI of the namespace.
28
29.. code-block:: pycon
30
31    >>> from rdflib.namespace import Namespace
32    >>> owl = Namespace('http://www.w3.org/2002/07/owl#')
33
34Fully qualified URIs in the namespace can be constructed either by attribute
35or by dictionary access on Namespace instances:
36
37.. code-block:: pycon
38
39    >>> owl.seeAlso
40    rdflib.term.URIRef(u'http://www.w3.org/2002/07/owl#seeAlso')
41    >>> owl['seeAlso']
42    rdflib.term.URIRef(u'http://www.w3.org/2002/07/owl#seeAlso')
43
44
45Automatic handling of unknown predicates
46-----------------------------------------
47
48As a programming convenience, a namespace binding is automatically
49created when :class:`rdflib.term.URIRef` predicates are added to the graph.
50
51Importable namespaces
52-----------------------
53
54The following namespaces are available by directly importing from rdflib:
55
56* RDF
57* RDFS
58* OWL
59* XSD
60* FOAF
61* SKOS
62* DOAP
63* DC
64* DCTERMS
65* VOID
66
67.. code-block:: pycon
68
69    >>> from rdflib import OWL
70    >>> OWL.seeAlso
71    rdflib.term.URIRef(u'http://www.w3.org/2002/07/owl#seeAlso')
72
73"""
74
75__all__ = [
76    'is_ncname', 'split_uri', 'Namespace',
77    'ClosedNamespace', 'NamespaceManager',
78    'XMLNS', 'RDF', 'RDFS', 'XSD', 'OWL',
79    'SKOS', 'DOAP', 'FOAF', 'DC', 'DCTERMS', 'VOID']
80
81logger = logging.getLogger(__name__)
82
83
84class Namespace(text_type):
85
86    __doc__ = """
87    Utility class for quickly generating URIRefs with a common prefix
88
89    >>> from rdflib import Namespace
90    >>> n = Namespace("http://example.org/")
91    >>> n.Person # as attribute
92    rdflib.term.URIRef(u'http://example.org/Person')
93    >>> n['first-name'] # as item - for things that are not valid python identifiers
94    rdflib.term.URIRef(u'http://example.org/first-name')
95
96    """
97
98    def __new__(cls, value):
99        try:
100            rt = text_type.__new__(cls, value)
101        except UnicodeDecodeError:
102            rt = text_type.__new__(cls, value, 'utf-8')
103        return rt
104
105    @property
106    def title(self):
107        return URIRef(self + 'title')
108
109    def term(self, name):
110        # need to handle slices explicitly because of __getitem__ override
111        return URIRef(self + (name if isinstance(name, string_types) else ''))
112
113    def __getitem__(self, key, default=None):
114        return self.term(key)
115
116    def __getattr__(self, name):
117        if name.startswith("__"):  # ignore any special Python names!
118            raise AttributeError
119        else:
120            return self.term(name)
121
122    def __repr__(self):
123        return "Namespace(%r)" % text_type(self)
124
125
126class URIPattern(text_type):
127
128    __doc__ = """
129    Utility class for creating URIs according to some pattern
130    This supports either new style formatting with .format
131    or old-style with % operator
132
133    >>> u=URIPattern("http://example.org/%s/%d/resource")
134    >>> u%('books', 12345)
135    rdflib.term.URIRef(u'http://example.org/books/12345/resource')
136
137    """
138
139    def __new__(cls, value):
140        try:
141            rt = text_type.__new__(cls, value)
142        except UnicodeDecodeError:
143            rt = text_type.__new__(cls, value, 'utf-8')
144        return rt
145
146    def __mod__(self, *args, **kwargs):
147        return URIRef(text_type(self).__mod__(*args, **kwargs))
148
149    def format(self, *args, **kwargs):
150        return URIRef(text_type.format(self, *args, **kwargs))
151
152    def __repr__(self):
153        return "URIPattern(%r)" % text_type(self)
154
155
156class ClosedNamespace(object):
157    """
158    A namespace with a closed list of members
159
160    Trying to create terms not listen is an error
161    """
162
163    def __init__(self, uri, terms):
164        self.uri = uri
165        self.__uris = {}
166        for t in terms:
167            self.__uris[t] = URIRef(self.uri + t)
168
169    def term(self, name):
170        uri = self.__uris.get(name)
171        if uri is None:
172            raise KeyError(
173                "term '{}' not in namespace '{}'".format(name, self.uri)
174            )
175        else:
176            return uri
177
178    def __getitem__(self, key, default=None):
179        return self.term(key)
180
181    def __getattr__(self, name):
182        if name.startswith("__"):  # ignore any special Python names!
183            raise AttributeError
184        else:
185            try:
186                return self.term(name)
187            except KeyError as e:
188                raise AttributeError(e)
189
190    def __str__(self):
191        return text_type(self.uri)
192
193    def __repr__(self):
194        return "rdf.namespace.ClosedNamespace(%r)" % text_type(self.uri)
195
196
197class _RDFNamespace(ClosedNamespace):
198    """
199    Closed namespace for RDF terms
200    """
201
202    def __init__(self):
203        super(_RDFNamespace, self).__init__(
204            URIRef("http://www.w3.org/1999/02/22-rdf-syntax-ns#"),
205            terms=[
206                # Syntax Names
207                "RDF", "Description", "ID", "about", "parseType",
208                "resource", "li", "nodeID", "datatype",
209
210                # RDF Classes
211                "Seq", "Bag", "Alt", "Statement", "Property",
212                "List", "PlainLiteral",
213
214                # RDF Properties
215                "subject", "predicate", "object", "type",
216                "value", "first", "rest",
217                # and _n where n is a non-negative integer
218
219                # RDF Resources
220                "nil",
221
222                # Added in RDF 1.1
223                "XMLLiteral", "HTML", "langString",
224
225                # Added in JSON-LD 1.1
226                "JSON", "CompoundLiteral", "language", "direction"]
227        )
228
229    def term(self, name):
230        # Container membership properties
231        if name.startswith('_'):
232            try:
233                i = int(name[1:])
234            except ValueError:
235                pass
236            else:
237                if i > 0:
238                    return URIRef("%s_%s" % (self.uri, i))
239
240        return super(_RDFNamespace, self).term(name)
241
242
243RDF = _RDFNamespace()
244
245
246RDFS = ClosedNamespace(
247    uri=URIRef("http://www.w3.org/2000/01/rdf-schema#"),
248    terms=[
249        "Resource", "Class", "subClassOf", "subPropertyOf", "comment", "label",
250        "domain", "range", "seeAlso", "isDefinedBy", "Literal", "Container",
251        "ContainerMembershipProperty", "member", "Datatype"]
252)
253
254OWL = Namespace('http://www.w3.org/2002/07/owl#')
255
256XSD = Namespace(_XSD_PFX)
257
258CSVW = Namespace('http://www.w3.org/ns/csvw#')
259DC = Namespace('http://purl.org/dc/elements/1.1/')
260DCAT = Namespace('http://www.w3.org/ns/dcat#')
261DCTERMS = Namespace('http://purl.org/dc/terms/')
262DOAP = Namespace('http://usefulinc.com/ns/doap#')
263FOAF = ClosedNamespace(
264    uri=URIRef('http://xmlns.com/foaf/0.1/'),
265    terms=[
266        # all taken from http://xmlns.com/foaf/spec/
267        'Agent', 'Person', 'name', 'title', 'img',
268        'depiction', 'depicts', 'familyName',
269        'givenName', 'knows', 'based_near', 'age', 'made',
270        'maker', 'primaryTopic', 'primaryTopicOf', 'Project', 'Organization',
271        'Group', 'member', 'Document', 'Image', 'nick',
272        'mbox', 'homepage', 'weblog', 'openid', 'jabberID',
273        'mbox_sha1sum', 'interest', 'topic_interest', 'topic', 'page',
274        'workplaceHomepage', 'workInfoHomepage', 'schoolHomepage', 'publications', 'currentProject',
275        'pastProject', 'account', 'OnlineAccount', 'accountName', 'accountServiceHomepage',
276        'PersonalProfileDocument', 'tipjar', 'sha1', 'thumbnail', 'logo'
277    ]
278)
279ODRL2 = Namespace('http://www.w3.org/ns/odrl/2/')
280ORG = Namespace('http://www.w3.org/ns/org#')
281PROV = ClosedNamespace(
282    uri=URIRef('http://www.w3.org/ns/prov#'),
283    terms=[
284        'Entity', 'Activity', 'Agent', 'wasGeneratedBy', 'wasDerivedFrom',
285        'wasAttributedTo', 'startedAtTime', 'used', 'wasInformedBy', 'endedAtTime',
286        'wasAssociatedWith', 'actedOnBehalfOf', 'Collection', 'EmptyCollection', 'Bundle',
287        'Person', 'SoftwareAgent', 'Organization', 'Location', 'alternateOf',
288        'specializationOf', 'generatedAtTime', 'hadPrimarySource', 'value', 'wasQuotedFrom',
289        'wasRevisionOf', 'invalidatedAtTime', 'wasInvalidatedBy', 'hadMember', 'wasStartedBy',
290        'wasEndedBy', 'invalidated', 'influenced', 'atLocation', 'generated',
291        'Influence', 'EntityInfluence', 'Usage', 'Start', 'End',
292        'Derivation', 'PrimarySource', 'Quotation', 'Revision', 'ActivityInfluence',
293        'Generation', 'Communication', 'Invalidation', 'AgentInfluence',
294        'Attribution', 'Association', 'Plan', 'Delegation', 'InstantaneousEvent',
295        'Role', 'wasInfluencedBy', 'qualifiedInfluence', 'qualifiedGeneration', 'qualifiedDerivation',
296        'qualifiedPrimarySource', 'qualifiedQuotation', 'qualifiedRevision', 'qualifiedAttribution',
297        'qualifiedInvalidation', 'qualifiedStart', 'qualifiedUsage', 'qualifiedCommunication', 'qualifiedAssociation',
298        'qualifiedEnd', 'qualifiedDelegation', 'influencer', 'entity', 'hadUsage', 'hadGeneration',
299        'activity', 'agent', 'hadPlan', 'hadActivity', 'atTime', 'hadRole'
300    ]
301)
302PROF = Namespace('http://www.w3.org/ns/dx/prof/')
303SDO = Namespace('https://schema.org/')
304SH = Namespace('http://www.w3.org/ns/shacl#')
305SKOS = ClosedNamespace(
306    uri=URIRef('http://www.w3.org/2004/02/skos/core#'),
307    terms=[
308        # all taken from https://www.w3.org/TR/skos-reference/#L1302
309        'Concept', 'ConceptScheme', 'inScheme', 'hasTopConcept', 'topConceptOf',
310        'altLabel', 'hiddenLabel', 'prefLabel', 'notation', 'changeNote',
311        'definition', 'editorialNote', 'example', 'historyNote', 'note',
312        'scopeNote', 'broader', 'broaderTransitive', 'narrower', 'narrowerTransitive',
313        'related', 'semanticRelation', 'Collection', 'OrderedCollection', 'member',
314        'memberList', 'broadMatch', 'closeMatch', 'exactMatch', 'mappingRelation',
315        'narrowMatch', 'relatedMatch'
316    ]
317)
318SOSA = Namespace('http://www.w3.org/ns/ssn/')
319SSN = Namespace('http://www.w3.org/ns/sosa/')
320TIME = Namespace('http://www.w3.org/2006/time#')
321VOID = Namespace('http://rdfs.org/ns/void#')
322
323
324class NamespaceManager(object):
325    """
326
327    Class for managing prefix => namespace mappings
328
329    Sample usage from FuXi ...
330
331    .. code-block:: python
332
333        ruleStore = N3RuleStore(additionalBuiltins=additionalBuiltins)
334        nsMgr = NamespaceManager(Graph(ruleStore))
335        ruleGraph = Graph(ruleStore,namespace_manager=nsMgr)
336
337
338    and ...
339
340    .. code-block:: pycon
341
342        >>> import rdflib
343        >>> from rdflib import Graph
344        >>> from rdflib.namespace import Namespace, NamespaceManager
345        >>> exNs = Namespace('http://example.com/')
346        >>> namespace_manager = NamespaceManager(Graph())
347        >>> namespace_manager.bind('ex', exNs, override=False)
348        >>> g = Graph()
349        >>> g.namespace_manager = namespace_manager
350        >>> all_ns = [n for n in g.namespace_manager.namespaces()]
351        >>> assert ('ex', rdflib.term.URIRef('http://example.com/')) in all_ns
352        >>>
353
354    """
355
356    def __init__(self, graph):
357        self.graph = graph
358        self.__cache = {}
359        self.__cache_strict = {}
360        self.__log = None
361        self.__strie = {}
362        self.__trie = {}
363        for p, n in self.namespaces():  # self.bind is not always called
364            insert_trie(self.__trie, str(n))
365        self.bind("xml", "http://www.w3.org/XML/1998/namespace")
366        self.bind("rdf", RDF)
367        self.bind("rdfs", RDFS)
368        self.bind("xsd", XSD)
369
370    def reset(self):
371        self.__cache = {}
372        self.__strie = {}
373        self.__trie = {}
374        for p, n in self.namespaces():  # repopulate the trie
375            insert_trie(self.__trie, str(n))
376
377    def __get_store(self):
378        return self.graph.store
379    store = property(__get_store)
380
381    def qname(self, uri):
382        prefix, namespace, name = self.compute_qname(uri)
383        if prefix == "":
384            return name
385        else:
386            return ":".join((prefix, name))
387
388    def qname_strict(self, uri):
389        prefix, namespace, name = self.compute_qname_strict(uri)
390        if prefix == '':
391            return name
392        else:
393            return ':'.join((prefix, name))
394
395    def normalizeUri(self, rdfTerm):
396        """
397        Takes an RDF Term and 'normalizes' it into a QName (using the
398        registered prefix) or (unlike compute_qname) the Notation 3
399        form for URIs: <...URI...>
400        """
401        try:
402            namespace, name = split_uri(rdfTerm)
403            if namespace not in self.__strie:
404                insert_strie(self.__strie, self.__trie, str(namespace))
405            namespace = URIRef(text_type(namespace))
406        except:
407            if isinstance(rdfTerm, Variable):
408                return "?%s" % rdfTerm
409            else:
410                return "<%s>" % rdfTerm
411        prefix = self.store.prefix(namespace)
412        if prefix is None and isinstance(rdfTerm, Variable):
413            return "?%s" % rdfTerm
414        elif prefix is None:
415            return "<%s>" % rdfTerm
416        else:
417            qNameParts = self.compute_qname(rdfTerm)
418            return ':'.join([qNameParts[0], qNameParts[-1]])
419
420    def compute_qname(self, uri, generate=True):
421
422        if not _is_valid_uri(uri):
423            raise ValueError(
424                '"{}" does not look like a valid URI, cannot serialize this. Did you want to urlencode it?'.format(uri)
425            )
426
427        if uri not in self.__cache:
428            try:
429                namespace, name = split_uri(uri)
430            except ValueError as e:
431                namespace = URIRef(uri)
432                prefix = self.store.prefix(namespace)
433                if not prefix:
434                    raise e
435            if namespace not in self.__strie:
436                insert_strie(self.__strie, self.__trie, namespace)
437
438            if self.__strie[namespace]:
439                pl_namespace = get_longest_namespace(self.__strie[namespace], uri)
440                if pl_namespace is not None:
441                    namespace = pl_namespace
442                    name = uri[len(namespace):]
443
444            namespace = URIRef(namespace)
445            prefix = self.store.prefix(namespace)  # warning multiple prefixes problem
446
447            if prefix is None:
448                if not generate:
449                    raise KeyError(
450                        "No known prefix for {} and generate=False".format(namespace)
451                    )
452                num = 1
453                while 1:
454                    prefix = "ns%s" % num
455                    if not self.store.namespace(prefix):
456                        break
457                    num += 1
458                self.bind(prefix, namespace)
459            self.__cache[uri] = (prefix, namespace, name)
460        return self.__cache[uri]
461
462    def compute_qname_strict(self, uri, generate=True):
463        # code repeated to avoid branching on strict every time
464        # if output needs to be strict (e.g. for xml) then
465        # only the strict output should bear the overhead
466        prefix, namespace, name = self.compute_qname(uri)
467        if is_ncname(text_type(name)):
468            return prefix, namespace, name
469        else:
470            if uri not in self.__cache_strict:
471                try:
472                    namespace, name = split_uri(uri, NAME_START_CATEGORIES)
473                except ValueError as e:
474                    message = ('This graph cannot be serialized to a strict format '
475                               'because there is no valid way to shorten {}'.format(uri))
476                    raise ValueError(message)
477                    # omitted for strict since NCNames cannot be empty
478                    #namespace = URIRef(uri)
479                    #prefix = self.store.prefix(namespace)
480                    #if not prefix:
481                        #raise e
482
483                if namespace not in self.__strie:
484                    insert_strie(self.__strie, self.__trie, namespace)
485
486                # omitted for strict
487                #if self.__strie[namespace]:
488                    #pl_namespace = get_longest_namespace(self.__strie[namespace], uri)
489                    #if pl_namespace is not None:
490                        #namespace = pl_namespace
491                        #name = uri[len(namespace):]
492
493                namespace = URIRef(namespace)
494                prefix = self.store.prefix(namespace)  # warning multiple prefixes problem
495
496                if prefix is None:
497                    if not generate:
498                        raise KeyError(
499                            "No known prefix for {} and generate=False".format(namespace)
500                        )
501                    num = 1
502                    while 1:
503                        prefix = "ns%s" % num
504                        if not self.store.namespace(prefix):
505                            break
506                        num += 1
507                    self.bind(prefix, namespace)
508                self.__cache_strict[uri] = (prefix, namespace, name)
509
510            return self.__cache_strict[uri]
511
512    def bind(self, prefix, namespace, override=True, replace=False):
513        """bind a given namespace to the prefix
514
515        if override, rebind, even if the given namespace is already
516        bound to another prefix.
517
518        if replace, replace any existing prefix with the new namespace
519
520        """
521
522        namespace = URIRef(text_type(namespace))
523        # When documenting explain that override only applies in what cases
524        if prefix is None:
525            prefix = ''
526        bound_namespace = self.store.namespace(prefix)
527        # Check if the bound_namespace contains a URI
528        # and if so convert it into a URIRef for comparison
529        # This is to prevent duplicate namespaces with the
530        # same URI
531        if bound_namespace:
532            bound_namespace = URIRef(bound_namespace)
533        if bound_namespace and bound_namespace != namespace:
534
535            if replace:
536                self.store.bind(prefix, namespace)
537                insert_trie(self.__trie, str(namespace))
538                return
539
540            # prefix already in use for different namespace
541            #
542            # append number to end of prefix until we find one
543            # that's not in use.
544            if not prefix:
545                prefix = "default"
546            num = 1
547            while 1:
548                new_prefix = "%s%s" % (prefix, num)
549                tnamespace = self.store.namespace(new_prefix)
550                if tnamespace and namespace == URIRef(tnamespace):
551                    # the prefix is already bound to the correct
552                    # namespace
553                    return
554                if not self.store.namespace(new_prefix):
555                    break
556                num += 1
557            self.store.bind(new_prefix, namespace)
558        else:
559            bound_prefix = self.store.prefix(namespace)
560            if bound_prefix is None:
561                self.store.bind(prefix, namespace)
562            elif bound_prefix == prefix:
563                pass  # already bound
564            else:
565                if override or bound_prefix.startswith("_"):  # or a generated prefix
566                    self.store.bind(prefix, namespace)
567        insert_trie(self.__trie, str(namespace))
568
569    def namespaces(self):
570        for prefix, namespace in self.store.namespaces():
571            namespace = URIRef(namespace)
572            yield prefix, namespace
573
574    def absolutize(self, uri, defrag=1):
575        base = urljoin("file:", pathname2url(os.getcwd()))
576        result = urljoin("%s/" % base, uri, allow_fragments=not defrag)
577        if defrag:
578            result = urldefrag(result)[0]
579        if not defrag:
580            if uri and uri[-1] == "#" and result[-1] != "#":
581                result = "%s#" % result
582        return URIRef(result)
583
584# From: http://www.w3.org/TR/REC-xml#NT-CombiningChar
585#
586# * Name start characters must have one of the categories Ll, Lu, Lo,
587#   Lt, Nl.
588#
589# * Name characters other than Name-start characters must have one of
590#   the categories Mc, Me, Mn, Lm, or Nd.
591#
592# * Characters in the compatibility area (i.e. with character code
593#   greater than #xF900 and less than #xFFFE) are not allowed in XML
594#   names.
595#
596# * Characters which have a font or compatibility decomposition
597#   (i.e. those with a "compatibility formatting tag" in field 5 of the
598#   database -- marked by field 5 beginning with a "<") are not allowed.
599#
600# * The following characters are treated as name-start characters rather
601#   than name characters, because the property file classifies them as
602#   Alphabetic: [#x02BB-#x02C1], #x0559, #x06E5, #x06E6.
603#
604# * Characters #x20DD-#x20E0 are excluded (in accordance with Unicode
605#   2.0, section 5.14).
606#
607# * Character #x00B7 is classified as an extender, because the property
608#   list so identifies it.
609#
610# * Character #x0387 is added as a name character, because #x00B7 is its
611#   canonical equivalent.
612#
613# * Characters ':' and '_' are allowed as name-start characters.
614#
615# * Characters '-' and '.' are allowed as name characters.
616
617
618NAME_START_CATEGORIES = ["Ll", "Lu", "Lo", "Lt", "Nl"]
619SPLIT_START_CATEGORIES = NAME_START_CATEGORIES + ['Nd']
620NAME_CATEGORIES = NAME_START_CATEGORIES + ["Mc", "Me", "Mn", "Lm", "Nd"]
621ALLOWED_NAME_CHARS = [u"\u00B7", u"\u0387", u"-", u".", u"_", u":"]
622
623
624# http://www.w3.org/TR/REC-xml-names/#NT-NCName
625#  [4] NCName ::= (Letter | '_') (NCNameChar)* /* An XML Name, minus
626#      the ":" */
627#  [5] NCNameChar ::= Letter | Digit | '.' | '-' | '_' | CombiningChar
628#      | Extender
629
630
631def is_ncname(name):
632    if name:
633        first = name[0]
634        if first == "_" or category(first) in NAME_START_CATEGORIES:
635            for i in range(1, len(name)):
636                c = name[i]
637                if not category(c) in NAME_CATEGORIES:
638                    if c != ':' and c in ALLOWED_NAME_CHARS:
639                        continue
640                    return 0
641                # if in compatibility area
642                # if decomposition(c)!='':
643                #    return 0
644
645            return 1
646
647    return 0
648
649
650XMLNS = "http://www.w3.org/XML/1998/namespace"
651
652
653def split_uri(uri, split_start=SPLIT_START_CATEGORIES):
654    if uri.startswith(XMLNS):
655        return (XMLNS, uri.split(XMLNS)[1])
656    length = len(uri)
657    for i in range(0, length):
658        c = uri[-i - 1]
659        if not category(c) in NAME_CATEGORIES:
660            if c in ALLOWED_NAME_CHARS:
661                continue
662            for j in range(-1 - i, length):
663                if category(uri[j]) in split_start or uri[j] == "_":
664                    # _ prevents early split, roundtrip not generate
665                    ns = uri[:j]
666                    if not ns:
667                        break
668                    ln = uri[j:]
669                    return (ns, ln)
670            break
671    raise ValueError("Can't split '{}'".format(uri))
672
673def insert_trie(trie, value):  # aka get_subtrie_or_insert
674    """ Insert a value into the trie if it is not already contained in the trie.
675        Return the subtree for the value regardless of whether it is a new value
676        or not. """
677    if value in trie:
678        return trie[value]
679    multi_check = False
680    for key in tuple(trie.keys()):
681        if len(value) > len(key) and value.startswith(key):
682            return insert_trie(trie[key], value)
683        elif key.startswith(value):  # we know the value is not in the trie
684            if not multi_check:
685                trie[value] = {}
686                multi_check = True  # there can be multiple longer existing prefixes
687            dict_ = trie.pop(key)  # does not break strie since key<->dict_ remains unchanged
688            trie[value][key] = dict_
689    if value not in trie:
690        trie[value] = {}
691    return trie[value]
692
693def insert_strie(strie, trie, value):
694    if value not in strie:
695        strie[value] = insert_trie(trie, value)
696
697def get_longest_namespace(trie, value):
698    for key in trie:
699        if value.startswith(key):
700            out = get_longest_namespace(trie[key], value)
701            if out is None:
702                return key
703            else:
704                return out
705    return None
706