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