00001 """
00002 Classes dealing with sets of resources.
00003
00004 The basic mechanics of a resource set are the same for any of the
00005 resources we handle (ASNs, IPv4 addresses, or IPv6 addresses), so we
00006 can provide the same operations on any of them, even though the
00007 underlying details vary.
00008
00009 We also provide some basic set operations (union, intersection, etc).
00010
00011 $Id: resource_set.py 3449 2010-09-16 21:30:30Z sra $
00012
00013 Copyright (C) 2009--2010 Internet Systems Consortium ("ISC")
00014
00015 Permission to use, copy, modify, and distribute this software for any
00016 purpose with or without fee is hereby granted, provided that the above
00017 copyright notice and this permission notice appear in all copies.
00018
00019 THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
00020 REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
00021 AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
00022 INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
00023 LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
00024 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
00025 PERFORMANCE OF THIS SOFTWARE.
00026
00027 Portions copyright (C) 2007--2008 American Registry for Internet Numbers ("ARIN")
00028
00029 Permission to use, copy, modify, and distribute this software for any
00030 purpose with or without fee is hereby granted, provided that the above
00031 copyright notice and this permission notice appear in all copies.
00032
00033 THE SOFTWARE IS PROVIDED "AS IS" AND ARIN DISCLAIMS ALL WARRANTIES WITH
00034 REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
00035 AND FITNESS. IN NO EVENT SHALL ARIN BE LIABLE FOR ANY SPECIAL, DIRECT,
00036 INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
00037 LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
00038 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
00039 PERFORMANCE OF THIS SOFTWARE.
00040 """
00041
00042 import re, math
00043 import rpki.ipaddrs, rpki.oids, rpki.exceptions
00044
00045
00046
00047
00048 inherit_token = "<inherit>"
00049
00050 re_asn_range = re.compile("^([0-9]+)-([0-9]+)$")
00051 re_address_range = re.compile("^([0-9:.a-fA-F]+)-([0-9:.a-fA-F]+)$")
00052 re_prefix_with_maxlen = re.compile("^([0-9:.a-fA-F]+)/([0-9]+)-([0-9]+)$")
00053 re_prefix = re.compile("^([0-9:.a-fA-F]+)/([0-9]+)$")
00054
00055 class resource_range(object):
00056 """
00057 Generic resource range type. Assumes underlying type is some kind
00058 of integer.
00059
00060 This is a virtual class. You probably don't want to use this type
00061 directly.
00062 """
00063
00064 def __init__(self, min, max):
00065 """
00066 Initialize and sanity check a resource_range.
00067 """
00068 assert min.__class__ is max.__class__, "Type mismatch, %r doesn't match %r" % (min.__class__, max.__class__)
00069 assert min <= max, "Mis-ordered range: %s before %s" % (min, max)
00070 self.min = min
00071 self.max = max
00072
00073 def __cmp__(self, other):
00074 """
00075 Compare two resource_range objects.
00076 """
00077 assert self.__class__ is other.__class__, "Type mismatch, comparing %r with %r" % (self.__class__, other.__class__)
00078 return cmp(self.min, other.min) or cmp(self.max, other.max)
00079
00080 class resource_range_as(resource_range):
00081 """
00082 Range of Autonomous System Numbers.
00083
00084 Denotes a single ASN by a range whose min and max values are
00085 identical.
00086 """
00087
00088
00089
00090
00091 datum_type = long
00092
00093 def __str__(self):
00094 """
00095 Convert a resource_range_as to string format.
00096 """
00097 if self.min == self.max:
00098 return str(self.min)
00099 else:
00100 return str(self.min) + "-" + str(self.max)
00101
00102 def to_rfc3779_tuple(self):
00103 """
00104 Convert a resource_range_as to tuple format for RFC 3779 ASN.1 encoding.
00105 """
00106 if self.min == self.max:
00107 return ("id", self.min)
00108 else:
00109 return ("range", (self.min, self.max))
00110
00111 @classmethod
00112 def parse_str(cls, x):
00113 """
00114 Parse ASN resource range from text (eg, XML attributes).
00115 """
00116 r = re_asn_range.match(x)
00117 if r:
00118 return cls(long(r.group(1)), long(r.group(2)))
00119 else:
00120 return cls(long(x), long(x))
00121
00122 @classmethod
00123 def from_strings(cls, a, b = None):
00124 """
00125 Construct ASN range from strings.
00126 """
00127 if b is None:
00128 b = a
00129 return cls(long(a), long(b))
00130
00131 class resource_range_ip(resource_range):
00132 """
00133 Range of (generic) IP addresses.
00134
00135 Prefixes are converted to ranges on input, and ranges that can be
00136 represented as prefixes are written as prefixes on output.
00137
00138 This is a virtual class. You probably don't want to use it
00139 directly.
00140 """
00141
00142 def prefixlen(self):
00143 """
00144 Determine whether a resource_range_ip can be expressed as a
00145 prefix. Returns prefix length if it can, otherwise raises
00146 MustBePrefix exception.
00147 """
00148 mask = self.min ^ self.max
00149 if self.min & mask != 0:
00150 raise rpki.exceptions.MustBePrefix
00151 prefixlen = self.datum_type.bits
00152 while mask & 1:
00153 prefixlen -= 1
00154 mask >>= 1
00155 if mask:
00156 raise rpki.exceptions.MustBePrefix
00157 return prefixlen
00158
00159
00160 _prefixlen = prefixlen
00161
00162 def __str__(self):
00163 """
00164 Convert a resource_range_ip to string format.
00165 """
00166 try:
00167 return str(self.min) + "/" + str(self.prefixlen())
00168 except rpki.exceptions.MustBePrefix:
00169 return str(self.min) + "-" + str(self.max)
00170
00171 def to_rfc3779_tuple(self):
00172 """
00173 Convert a resource_range_ip to tuple format for RFC 3779 ASN.1
00174 encoding.
00175 """
00176 try:
00177 return ("addressPrefix", _long2bs(self.min, self.datum_type.bits,
00178 prefixlen = self.prefixlen()))
00179 except rpki.exceptions.MustBePrefix:
00180 return ("addressRange", (_long2bs(self.min, self.datum_type.bits, strip = 0),
00181 _long2bs(self.max, self.datum_type.bits, strip = 1)))
00182
00183 @classmethod
00184 def parse_str(cls, x):
00185 """
00186 Parse IP address range or prefix from text (eg, XML attributes).
00187 """
00188 r = re_address_range.match(x)
00189 if r:
00190 return cls(cls.datum_type(r.group(1)), cls.datum_type(r.group(2)))
00191 r = re_prefix.match(x)
00192 if r:
00193 return cls.make_prefix(cls.datum_type(r.group(1)), int(r.group(2)))
00194 raise rpki.exceptions.BadIPResource, 'Bad IP resource "%s"' % (x)
00195
00196 @classmethod
00197 def make_prefix(cls, prefix, prefixlen):
00198 """
00199 Construct a resource range corresponding to a prefix.
00200 """
00201 assert isinstance(prefix, cls.datum_type) and isinstance(prefixlen, (int, long))
00202 assert prefixlen >= 0 and prefixlen <= cls.datum_type.bits, "Nonsensical prefix length: %s" % prefixlen
00203 mask = (1 << (cls.datum_type.bits - prefixlen)) - 1
00204 assert (prefix & mask) == 0, "Resource not in canonical form: %s/%s" % (prefix, prefixlen)
00205 return cls(cls.datum_type(prefix), cls.datum_type(prefix | mask))
00206
00207 def chop_into_prefixes(self, result):
00208 """
00209 Chop up a resource_range_ip into ranges that can be represented as
00210 prefixes.
00211 """
00212 try:
00213 self.prefixlen()
00214 result.append(self)
00215 except rpki.exceptions.MustBePrefix:
00216 min = self.min
00217 max = self.max
00218 while max >= min:
00219 bits = int(math.log(max - min + 1, 2))
00220 while True:
00221 mask = ~(~0 << bits)
00222 assert min + mask <= max
00223 if min & mask == 0:
00224 break
00225 assert bits > 0
00226 bits -= 1
00227 result.append(self.make_prefix(min, self.datum_type.bits - bits))
00228 min = self.datum_type(min + mask + 1)
00229
00230 @classmethod
00231 def from_strings(cls, a, b = None):
00232 """
00233 Construct IP address range from strings.
00234 """
00235 if b is None:
00236 b = a
00237 a = rpki.ipaddrs.parse(a)
00238 b = rpki.ipaddrs.parse(b)
00239 if a.__class__ is not b.__class__:
00240 raise TypeError
00241 if cls is resource_range_ip:
00242 if isinstance(a, rpki.ipaddrs.v4addr):
00243 return resource_range_ipv4(a, b)
00244 if isinstance(a, rpki.ipaddrs.v6addr):
00245 return resource_range_ipv6(a, b)
00246 elif isinstance(a, cls.datum_type):
00247 return cls(a, b)
00248 raise TypeError
00249
00250 class resource_range_ipv4(resource_range_ip):
00251 """
00252 Range of IPv4 addresses.
00253 """
00254
00255
00256
00257
00258 datum_type = rpki.ipaddrs.v4addr
00259
00260 class resource_range_ipv6(resource_range_ip):
00261 """
00262 Range of IPv6 addresses.
00263 """
00264
00265
00266
00267
00268 datum_type = rpki.ipaddrs.v6addr
00269
00270 def _rsplit(rset, that):
00271 """
00272 Utility function to split a resource range into two resource ranges.
00273 """
00274 this = rset.pop(0)
00275 cell_type = type(this.min)
00276 assert type(this) is type(that) and type(this.max) is cell_type and \
00277 type(that.min) is cell_type and type(that.max) is cell_type
00278 if this.min < that.min:
00279 rset.insert(0, type(this)(this.min, cell_type(that.min - 1)))
00280 rset.insert(1, type(this)(that.min, this.max))
00281 else:
00282 assert this.max > that.max
00283 rset.insert(0, type(this)(this.min, that.max))
00284 rset.insert(1, type(this)(cell_type(that.max + 1), this.max))
00285
00286 class resource_set(list):
00287 """
00288 Generic resource set, a list subclass containing resource ranges.
00289
00290 This is a virtual class. You probably don't want to use it
00291 directly.
00292 """
00293
00294
00295
00296
00297 inherit = False
00298
00299
00300
00301
00302 canonical = False
00303
00304 def __init__(self, ini = None):
00305 """
00306 Initialize a resource_set.
00307 """
00308 list.__init__(self)
00309 if isinstance(ini, (int, long)):
00310 ini = str(ini)
00311 if ini is inherit_token:
00312 self.inherit = True
00313 elif isinstance(ini, str) and len(ini):
00314 self.extend(self.parse_str(s) for s in ini.split(","))
00315 elif isinstance(ini, tuple):
00316 self.parse_rfc3779_tuple(ini)
00317 elif isinstance(ini, list):
00318 self.extend(ini)
00319 else:
00320 assert ini is None or (isinstance(ini, str) and ini == ""), "Unexpected initializer: %s" % str(ini)
00321 self.canonize()
00322
00323 def canonize(self):
00324 """
00325 Whack this resource_set into canonical form.
00326 """
00327 assert not self.inherit or not self
00328 if not self.canonical:
00329 self.sort()
00330 for i in xrange(len(self) - 2, -1, -1):
00331 if self[i].max + 1 == self[i+1].min:
00332 self[i] = type(self[i])(self[i].min, self[i+1].max)
00333 self.pop(i + 1)
00334 if __debug__:
00335 for i in xrange(0, len(self) - 1):
00336 assert self[i].max < self[i+1].min, "Resource overlap: %s %s" % (self[i], self[i+1])
00337 self.canonical = True
00338
00339 def append(self, item):
00340 """
00341 Wrapper around list.append() (q.v.) to reset canonical flag.
00342 """
00343 list.append(self, item)
00344 self.canonical = False
00345
00346 def extend(self, item):
00347 """
00348 Wrapper around list.extend() (q.v.) to reset canonical flag.
00349 """
00350 list.extend(self, item)
00351 self.canonical = False
00352
00353 def __str__(self):
00354 """
00355 Convert a resource_set to string format.
00356 """
00357 if self.inherit:
00358 return inherit_token
00359 else:
00360 return ",".join(str(x) for x in self)
00361
00362 def _comm(self, other):
00363 """
00364 Like comm(1), sort of.
00365
00366 Returns a tuple of three resource sets: resources only in self,
00367 resources only in other, and resources in both. Used (not very
00368 efficiently) as the basis for most set operations on resource
00369 sets.
00370 """
00371
00372 assert not self.inherit
00373 assert type(self) is type(other), "Type mismatch %r %r" % (type(self), type(other))
00374 set1 = type(self)(self)
00375 set2 = type(other)(other)
00376 only1, only2, both = [], [], []
00377 while set1 or set2:
00378 if set1 and (not set2 or set1[0].max < set2[0].min):
00379 only1.append(set1.pop(0))
00380 elif set2 and (not set1 or set2[0].max < set1[0].min):
00381 only2.append(set2.pop(0))
00382 elif set1[0].min < set2[0].min:
00383 _rsplit(set1, set2[0])
00384 elif set2[0].min < set1[0].min:
00385 _rsplit(set2, set1[0])
00386 elif set1[0].max < set2[0].max:
00387 _rsplit(set2, set1[0])
00388 elif set2[0].max < set1[0].max:
00389 _rsplit(set1, set2[0])
00390 else:
00391 assert set1[0].min == set2[0].min and set1[0].max == set2[0].max
00392 both.append(set1.pop(0))
00393 set2.pop(0)
00394 return type(self)(only1), type(self)(only2), type(self)(both)
00395
00396 def union(self, other):
00397 """
00398 Set union for resource sets.
00399 """
00400
00401 assert not self.inherit
00402 assert type(self) is type(other), "Type mismatch: %r %r" % (type(self), type(other))
00403 set1 = type(self)(self)
00404 set2 = type(other)(other)
00405 result = []
00406 while set1 or set2:
00407 if set1 and (not set2 or set1[0].max < set2[0].min):
00408 result.append(set1.pop(0))
00409 elif set2 and (not set1 or set2[0].max < set1[0].min):
00410 result.append(set2.pop(0))
00411 else:
00412 this = set1.pop(0)
00413 that = set2.pop(0)
00414 assert type(this) is type(that)
00415 if this.min < that.min: min = this.min
00416 else: min = that.min
00417 if this.max > that.max: max = this.max
00418 else: max = that.max
00419 result.append(type(this)(min, max))
00420 while set1 and set1[0].max <= max:
00421 assert set1[0].min >= min
00422 del set1[0]
00423 while set2 and set2[0].max <= max:
00424 assert set2[0].min >= min
00425 del set2[0]
00426 return type(self)(result)
00427
00428 def intersection(self, other):
00429 """
00430 Set intersection for resource sets.
00431 """
00432 return self._comm(other)[2]
00433
00434 def difference(self, other):
00435 """
00436 Set difference for resource sets.
00437 """
00438 return self._comm(other)[0]
00439
00440 def symmetric_difference(self, other):
00441 """
00442 Set symmetric difference (XOR) for resource sets.
00443 """
00444 com = self._comm(other)
00445 return com[0].union(com[1])
00446
00447 def contains(self, item):
00448 """
00449 Set membership test for resource sets.
00450 """
00451 assert not self.inherit
00452 self.canonize()
00453 if not self:
00454 return False
00455 if type(item) is type(self[0]):
00456 min = item.min
00457 max = item.max
00458 else:
00459 min = item
00460 max = item
00461 lo = 0
00462 hi = len(self)
00463 while lo < hi:
00464 mid = (lo + hi) / 2
00465 if self[mid].max < max:
00466 lo = mid + 1
00467 else:
00468 hi = mid
00469 return lo < len(self) and self[lo].min <= min and self[lo].max >= max
00470
00471 def issubset(self, other):
00472 """
00473 Test whether self is a subset (possibly improper) of other.
00474 """
00475 for i in self:
00476 if not other.contains(i):
00477 return False
00478 return True
00479
00480 def issuperset(self, other):
00481 """
00482 Test whether self is a superset (possibly improper) of other.
00483 """
00484 return other.issubset(self)
00485
00486 @classmethod
00487 def from_sql(cls, sql, query, args = None):
00488 """
00489 Create resource set from an SQL query.
00490
00491 sql is an object that supports execute() and fetchall() methods
00492 like a DB API 2.0 cursor object.
00493
00494 query is an SQL query that returns a sequence of (min, max) pairs.
00495 """
00496
00497 sql.execute(query, args)
00498 return cls(ini = [cls.range_type(cls.range_type.datum_type(b),
00499 cls.range_type.datum_type(e))
00500 for (b, e) in sql.fetchall()])
00501
00502 @classmethod
00503 def parse_str(cls, s):
00504 """
00505 Parse resource set from text string (eg, XML attributes). This is
00506 a backwards compatability wrapper, real functionality is now part
00507 of the range classes.
00508 """
00509 return cls.range_type.parse_str(s)
00510
00511 class resource_set_as(resource_set):
00512 """
00513 Autonomous System Number resource set.
00514 """
00515
00516
00517
00518
00519 range_type = resource_range_as
00520
00521 def parse_rfc3779_tuple(self, x):
00522 """
00523 Parse ASN resource from tuple format generated by RFC 3779 ASN.1
00524 decoder.
00525 """
00526 if x[0] == "asIdsOrRanges":
00527 for aor in x[1]:
00528 if aor[0] == "range":
00529 min = aor[1][0]
00530 max = aor[1][1]
00531 else:
00532 min = aor[1]
00533 max = min
00534 self.append(resource_range_as(min, max))
00535 else:
00536 assert x[0] == "inherit"
00537 self.inherit = True
00538
00539 def to_rfc3779_tuple(self):
00540 """
00541 Convert ASN resource set into tuple format used for RFC 3779 ASN.1
00542 encoding.
00543 """
00544 self.canonize()
00545 if self:
00546 return ("asIdsOrRanges", tuple(a.to_rfc3779_tuple() for a in self))
00547 elif self.inherit:
00548 return ("inherit", "")
00549 else:
00550 return None
00551
00552 class resource_set_ip(resource_set):
00553 """
00554 (Generic) IP address resource set.
00555
00556 This is a virtual class. You probably don't want to use it
00557 directly.
00558 """
00559
00560 def parse_rfc3779_tuple(self, x):
00561 """
00562 Parse IP address resource sets from tuple format generated by RFC
00563 3779 ASN.1 decoder.
00564 """
00565 if x[0] == "addressesOrRanges":
00566 for aor in x[1]:
00567 if aor[0] == "addressRange":
00568 min = _bs2long(aor[1][0], self.range_type.datum_type.bits, 0)
00569 max = _bs2long(aor[1][1], self.range_type.datum_type.bits, 1)
00570 else:
00571 min = _bs2long(aor[1], self.range_type.datum_type.bits, 0)
00572 max = _bs2long(aor[1], self.range_type.datum_type.bits, 1)
00573 self.append(self.range_type(self.range_type.datum_type(min), self.range_type.datum_type(max)))
00574 else:
00575 assert x[0] == "inherit"
00576 self.inherit = True
00577
00578 def to_roa_prefix_set(self):
00579 """
00580 Convert from a resource set to a ROA prefix set.
00581 """
00582 prefix_ranges = []
00583 for r in self:
00584 r.chop_into_prefixes(prefix_ranges)
00585 return self.roa_prefix_set_type([
00586 self.roa_prefix_set_type.prefix_type(r.min, r.prefixlen())
00587 for r in prefix_ranges])
00588
00589 def to_rfc3779_tuple(self):
00590 """
00591 Convert IP resource set into tuple format used by RFC 3779 ASN.1
00592 encoder.
00593 """
00594 self.canonize()
00595 if self:
00596 return (self.afi, ("addressesOrRanges", tuple(a.to_rfc3779_tuple() for a in self)))
00597 elif self.inherit:
00598 return (self.afi, ("inherit", ""))
00599 else:
00600 return None
00601
00602 class resource_set_ipv4(resource_set_ip):
00603 """
00604 IPv4 address resource set.
00605 """
00606
00607
00608
00609
00610 range_type = resource_range_ipv4
00611
00612
00613
00614
00615 afi = "\x00\x01"
00616
00617 class resource_set_ipv6(resource_set_ip):
00618 """
00619 IPv6 address resource set.
00620 """
00621
00622
00623
00624
00625 range_type = resource_range_ipv6
00626
00627
00628
00629
00630 afi = "\x00\x02"
00631
00632 def _bs2long(bs, addrlen, fill):
00633 """
00634 Utility function to convert a bitstring (POW.pkix tuple
00635 representation) into a Python long.
00636 """
00637 x = 0L
00638 for y in bs:
00639 x = (x << 1) | y
00640 for y in xrange(addrlen - len(bs)):
00641 x = (x << 1) | fill
00642 return x
00643
00644 def _long2bs(number, addrlen, prefixlen = None, strip = None):
00645 """
00646 Utility function to convert a Python long into a POW.pkix tuple
00647 bitstring. This is a bit complicated because it supports the
00648 fiendishly compact encoding used in RFC 3779.
00649 """
00650 assert prefixlen is None or strip is None
00651 bs = []
00652 while number:
00653 bs.append(int(number & 1))
00654 number >>= 1
00655 if addrlen > len(bs):
00656 bs.extend((0 for i in xrange(addrlen - len(bs))))
00657 bs.reverse()
00658 if prefixlen is not None:
00659 return tuple(bs[0:prefixlen])
00660 if strip is not None:
00661 while bs and bs[-1] == strip:
00662 bs.pop()
00663 return tuple(bs)
00664
00665 class resource_bag(object):
00666 """
00667 Container to simplify passing around the usual triple of ASN, IPv4,
00668 and IPv6 resource sets.
00669 """
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683 def __init__(self, asn = None, v4 = None, v6 = None, valid_until = None):
00684 self.asn = asn or resource_set_as()
00685 self.v4 = v4 or resource_set_ipv4()
00686 self.v6 = v6 or resource_set_ipv6()
00687 self.valid_until = valid_until
00688
00689 def oversized(self, other):
00690 """
00691 True iff self is oversized with respect to other.
00692 """
00693 return not self.asn.issubset(other.asn) or \
00694 not self.v4.issubset(other.v4) or \
00695 not self.v6.issubset(other.v6)
00696
00697 def undersized(self, other):
00698 """
00699 True iff self is undersized with respect to other.
00700 """
00701 return not other.asn.issubset(self.asn) or \
00702 not other.v4.issubset(self.v4) or \
00703 not other.v6.issubset(self.v6)
00704
00705 @classmethod
00706 def from_rfc3779_tuples(cls, exts):
00707 """
00708 Build a resource_bag from intermediate form generated by RFC 3779
00709 ASN.1 decoder.
00710 """
00711 asn = None
00712 v4 = None
00713 v6 = None
00714 for x in exts:
00715 if x[0] == rpki.oids.name2oid["sbgp-autonomousSysNum"]:
00716 assert len(x[2]) == 1 or x[2][1] is None, "RDI not implemented: %s" % (str(x))
00717 assert asn is None
00718 asn = resource_set_as(x[2][0])
00719 if x[0] == rpki.oids.name2oid["sbgp-ipAddrBlock"]:
00720 for fam in x[2]:
00721 if fam[0] == resource_set_ipv4.afi:
00722 assert v4 is None
00723 v4 = resource_set_ipv4(fam[1])
00724 if fam[0] == resource_set_ipv6.afi:
00725 assert v6 is None
00726 v6 = resource_set_ipv6(fam[1])
00727 return cls(asn, v4, v6)
00728
00729 def empty(self):
00730 """
00731 True iff all resource sets in this bag are empty.
00732 """
00733 return not self.asn and not self.v4 and not self.v6
00734
00735 def __eq__(self, other):
00736 return self.asn == other.asn and \
00737 self.v4 == other.v4 and \
00738 self.v6 == other.v6 and \
00739 self.valid_until == other.valid_until
00740
00741 def __ne__(self, other):
00742 return not (self == other)
00743
00744 def intersection(self, other):
00745 """
00746 Compute intersection with another resource_bag. valid_until
00747 attribute (if any) inherits from self.
00748 """
00749 return self.__class__(self.asn.intersection(other.asn),
00750 self.v4.intersection(other.v4),
00751 self.v6.intersection(other.v6),
00752 self.valid_until)
00753
00754 def union(self, other):
00755 """
00756 Compute union with another resource_bag. valid_until attribute
00757 (if any) inherits from self.
00758 """
00759 return self.__class__(self.asn.union(other.asn),
00760 self.v4.union(other.v4),
00761 self.v6.union(other.v6),
00762 self.valid_until)
00763
00764 def __str__(self):
00765 s = ""
00766 if self.asn:
00767 s += "ASN: %s" % self.asn
00768 if self.v4:
00769 if s:
00770 s += ", "
00771 s += "V4: %s" % self.v4
00772 if self.v6:
00773 if s:
00774 s += ", "
00775 s += "V6: %s" % self.v6
00776 return s
00777
00778
00779
00780
00781
00782
00783
00784
00785
00786 class roa_prefix(object):
00787 """
00788 ROA prefix. This is similar to the resource_range_ip class, but
00789 differs in that it only represents prefixes, never ranges, and
00790 includes the maximum prefix length as an additional value.
00791
00792 This is a virtual class, you probably don't want to use it directly.
00793 """
00794
00795
00796
00797
00798
00799
00800
00801
00802
00803
00804
00805 def __init__(self, prefix, prefixlen, max_prefixlen = None):
00806 """
00807 Initialize a ROA prefix. max_prefixlen is optional and defaults
00808 to prefixlen. max_prefixlen must not be smaller than prefixlen.
00809 """
00810 if max_prefixlen is None:
00811 max_prefixlen = prefixlen
00812 assert max_prefixlen >= prefixlen, "Bad max_prefixlen: %d must not be shorter than %d" % (max_prefixlen, prefixlen)
00813 self.prefix = prefix
00814 self.prefixlen = prefixlen
00815 self.max_prefixlen = max_prefixlen
00816
00817 def __cmp__(self, other):
00818 """
00819 Compare two ROA prefix objects. Comparision is based on prefix,
00820 prefixlen, and max_prefixlen, in that order.
00821 """
00822 assert self.__class__ is other.__class__
00823 return (cmp(self.prefix, other.prefix) or
00824 cmp(self.prefixlen, other.prefixlen) or
00825 cmp(self.max_prefixlen, other.max_prefixlen))
00826
00827 def __str__(self):
00828 """
00829 Convert a ROA prefix to string format.
00830 """
00831 if self.prefixlen == self.max_prefixlen:
00832 return str(self.prefix) + "/" + str(self.prefixlen)
00833 else:
00834 return str(self.prefix) + "/" + str(self.prefixlen) + "-" + str(self.max_prefixlen)
00835
00836 def to_resource_range(self):
00837 """
00838 Convert this ROA prefix to the equivilent resource_range_ip
00839 object. This is an irreversable transformation because it loses
00840 the max_prefixlen attribute, nothing we can do about that.
00841 """
00842 return self.range_type.make_prefix(self.prefix, self.prefixlen)
00843
00844 def min(self):
00845 """
00846 Return lowest address covered by prefix.
00847 """
00848 return self.prefix
00849
00850 def max(self):
00851 """
00852 Return highest address covered by prefix.
00853 """
00854 t = self.range_type.datum_type
00855 return t(self.prefix | ((1 << (t.bits - self.prefixlen)) - 1))
00856
00857 def to_roa_tuple(self):
00858 """
00859 Convert a resource_range_ip to tuple format for ROA ASN.1
00860 encoding.
00861 """
00862 return (_long2bs(self.prefix, self.range_type.datum_type.bits, prefixlen = self.prefixlen),
00863 None if self.prefixlen == self.max_prefixlen else self.max_prefixlen)
00864
00865 @classmethod
00866 def parse_str(cls, x):
00867 """
00868 Parse ROA prefix from text (eg, an XML attribute).
00869 """
00870 r = re_prefix_with_maxlen.match(x)
00871 if r:
00872 return cls(cls.range_type.datum_type(r.group(1)), int(r.group(2)), int(r.group(3)))
00873 r = re_prefix.match(x)
00874 if r:
00875 return cls(cls.range_type.datum_type(r.group(1)), int(r.group(2)))
00876 raise rpki.exceptions.BadROAPrefix, 'Bad ROA prefix "%s"' % (x)
00877
00878 class roa_prefix_ipv4(roa_prefix):
00879 """
00880 IPv4 ROA prefix.
00881 """
00882
00883
00884
00885
00886 range_type = resource_range_ipv4
00887
00888 class roa_prefix_ipv6(roa_prefix):
00889 """
00890 IPv6 ROA prefix.
00891 """
00892
00893
00894
00895
00896 range_type = resource_range_ipv6
00897
00898 class roa_prefix_set(list):
00899 """
00900 Set of ROA prefixes, analogous to the resource_set_ip class.
00901 """
00902
00903 def __init__(self, ini = None):
00904 """
00905 Initialize a ROA prefix set.
00906 """
00907 list.__init__(self)
00908 if isinstance(ini, str) and len(ini):
00909 self.extend(self.parse_str(s) for s in ini.split(","))
00910 elif isinstance(ini, (list, tuple)):
00911 self.extend(ini)
00912 else:
00913 assert ini is None or ini == "", "Unexpected initializer: %s" % str(ini)
00914 self.sort()
00915
00916 def __str__(self):
00917 """
00918 Convert a ROA prefix set to string format.
00919 """
00920 return ",".join(str(x) for x in self)
00921
00922 @classmethod
00923 def parse_str(cls, s):
00924 """
00925 Parse ROA prefix from text (eg, an XML attribute).
00926 This method is a backwards compatability shim.
00927 """
00928 return cls.prefix_type.parse_str(s)
00929
00930 def to_resource_set(self):
00931 """
00932 Convert a ROA prefix set to a resource set. This is an
00933 irreversable transformation. We have to compute a union here
00934 because ROA prefix sets can include overlaps, while RFC 3779
00935 resource sets cannot. This is ugly, and there is almost certainly
00936 a more efficient way to do this, but start by getting the output
00937 right before worrying about making it fast or pretty.
00938 """
00939 r = self.resource_set_type()
00940 s = self.resource_set_type()
00941 s.append(None)
00942 for p in self:
00943 s[0] = p.to_resource_range()
00944 r = r.union(s)
00945 return r
00946
00947 @classmethod
00948 def from_sql(cls, sql, query, args = None):
00949 """
00950 Create ROA prefix set from an SQL query.
00951
00952 sql is an object that supports execute() and fetchall() methods
00953 like a DB API 2.0 cursor object.
00954
00955 query is an SQL query that returns a sequence of (prefix,
00956 prefixlen, max_prefixlen) triples.
00957 """
00958
00959 sql.execute(query, args)
00960 return cls([cls.prefix_type(cls.prefix_type.range_type.datum_type(x), int(y), int(z))
00961 for (x, y, z) in sql.fetchall()])
00962
00963 def to_roa_tuple(self):
00964 """
00965 Convert ROA prefix set into tuple format used by ROA ASN.1
00966 encoder. This is a variation on the format used in RFC 3779.
00967 """
00968 if self:
00969 return (self.resource_set_type.afi, tuple(a.to_roa_tuple() for a in self))
00970 else:
00971 return None
00972
00973 class roa_prefix_set_ipv4(roa_prefix_set):
00974 """
00975 Set of IPv4 ROA prefixes.
00976 """
00977
00978
00979
00980
00981 prefix_type = roa_prefix_ipv4
00982
00983
00984
00985
00986 resource_set_type = resource_set_ipv4
00987
00988
00989 resource_set_ipv4.roa_prefix_set_type = roa_prefix_set_ipv4
00990
00991 class roa_prefix_set_ipv6(roa_prefix_set):
00992 """
00993 Set of IPv6 ROA prefixes.
00994 """
00995
00996
00997
00998
00999 prefix_type = roa_prefix_ipv6
01000
01001
01002
01003
01004 resource_set_type = resource_set_ipv6
01005
01006
01007 resource_set_ipv6.roa_prefix_set_type = roa_prefix_set_ipv6
01008
01009
01010
01011 if __name__ == "__main__":
01012
01013 def testprefix(v):
01014 return " (%s)" % v.to_roa_prefix_set() if isinstance(v, resource_set_ip) else ""
01015
01016 def test1(t, s1, s2):
01017 if isinstance(s1, str) and isinstance(s2, str):
01018 print "x: ", s1
01019 print "y: ", s2
01020 r1 = t(s1)
01021 r2 = t(s2)
01022 print "x: ", r1, testprefix(r1)
01023 print "y: ", r2, testprefix(r2)
01024 v1 = r1._comm(r2)
01025 v2 = r2._comm(r1)
01026 assert v1[0] == v2[1] and v1[1] == v2[0] and v1[2] == v2[2]
01027 for i in r1: assert r1.contains(i) and r1.contains(i.min) and r1.contains(i.max)
01028 for i in r2: assert r2.contains(i) and r2.contains(i.min) and r2.contains(i.max)
01029 for i in v1[0]: assert r1.contains(i) and not r2.contains(i)
01030 for i in v1[1]: assert not r1.contains(i) and r2.contains(i)
01031 for i in v1[2]: assert r1.contains(i) and r2.contains(i)
01032 v1 = r1.union(r2)
01033 v2 = r2.union(r1)
01034 assert v1 == v2
01035 print "x|y:", v1, testprefix(v1)
01036 v1 = r1.difference(r2)
01037 v2 = r2.difference(r1)
01038 print "x-y:", v1, testprefix(v1)
01039 print "y-x:", v2, testprefix(v2)
01040 v1 = r1.symmetric_difference(r2)
01041 v2 = r2.symmetric_difference(r1)
01042 assert v1 == v2
01043 print "x^y:", v1, testprefix(v1)
01044 v1 = r1.intersection(r2)
01045 v2 = r2.intersection(r1)
01046 assert v1 == v2
01047 print "x&y:", v1, testprefix(v1)
01048
01049 def test2(t, s1, s2):
01050 print "x: ", s1
01051 print "y: ", s2
01052 r1 = t(s1)
01053 r2 = t(s2)
01054 print "x: ", r1
01055 print "y: ", r2
01056 print "x>y:", (r1 > r2)
01057 print "x<y:", (r1 < r2)
01058 test1(t.resource_set_type,
01059 r1.to_resource_set(),
01060 r2.to_resource_set())
01061
01062 def test3(t, s1, s2):
01063 test1(t, s1, s2)
01064 r1 = t(s1).to_roa_prefix_set()
01065 r2 = t(s2).to_roa_prefix_set()
01066 print "x: ", r1
01067 print "y: ", r2
01068 print "x>y:", (r1 > r2)
01069 print "x<y:", (r1 < r2)
01070 test1(t.roa_prefix_set_type.resource_set_type,
01071 r1.to_resource_set(),
01072 r2.to_resource_set())
01073
01074 print
01075 print "Testing set operations on resource sets"
01076 print
01077 test1(resource_set_as, "1,2,3,4,5,6,11,12,13,14,15", "1,2,3,4,5,6,111,121,131,141,151")
01078 print
01079 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32")
01080 print
01081 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.0.0.0/24")
01082 print
01083 test1(resource_set_ipv4, "10.0.0.0/24", "10.3.0.0/24,10.0.0.77/32")
01084 print
01085 test1(resource_set_ipv4, "10.0.0.0/24", "10.0.0.0/32,10.0.0.2/32,10.0.0.4/32")
01086 print
01087 print "Testing set operations on ROA prefixes"
01088 print
01089 test2(roa_prefix_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32")
01090 print
01091 test2(roa_prefix_set_ipv4, "10.0.0.0/24-32,10.6.0.0/24-32", "10.3.0.0/24,10.0.0.0/16-32")
01092 print
01093 test2(roa_prefix_set_ipv4, "10.3.0.0/24-24,10.0.0.0/16-32", "10.3.0.0/24,10.0.0.0/16-32")
01094 print
01095 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::2/128")
01096 print
01097 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::7/128")
01098 print
01099 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::/120")
01100 print
01101 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::/120-128")
01102 print
01103 test3(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32")
01104 print
01105 test3(resource_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::2/128")
01106 print
01107 test3(resource_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::/120")