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 2776 2009-09-19 03:26:51Z sra $
00012
00013 Copyright (C) 2009 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
00043 import rpki.ipaddrs, rpki.oids, rpki.exceptions
00044
00045
00046
00047
00048 inherit_token = "<inherit>"
00049
00050 class resource_range(object):
00051 """
00052 Generic resource range type. Assumes underlying type is some kind
00053 of integer.
00054
00055 This is a virtual class. You probably don't want to use this type
00056 directly.
00057 """
00058
00059 def __init__(self, min, max):
00060 """
00061 Initialize and sanity check a resource_range.
00062 """
00063 assert min <= max, "Mis-ordered range: %s before %s" % (str(min), str(max))
00064 self.min = min
00065 self.max = max
00066
00067 def __cmp__(self, other):
00068 """
00069 Compare two resource_range objects.
00070 """
00071 assert self.__class__ is other.__class__, "Type mismatch, comparing %r with %r" % (self.__class__, other.__class__)
00072 c = self.min - other.min
00073 if c == 0: c = self.max - other.max
00074 if c < 0: c = -1
00075 if c > 0: c = 1
00076 return c
00077
00078 class resource_range_as(resource_range):
00079 """
00080 Range of Autonomous System Numbers.
00081
00082 Denotes a single ASN by a range whose min and max values are
00083 identical.
00084 """
00085
00086
00087
00088
00089 datum_type = long
00090
00091 def __str__(self):
00092 """
00093 Convert a resource_range_as to string format.
00094 """
00095 if self.min == self.max:
00096 return str(self.min)
00097 else:
00098 return str(self.min) + "-" + str(self.max)
00099
00100 def to_rfc3779_tuple(self):
00101 """
00102 Convert a resource_range_as to tuple format for RFC 3779 ASN.1 encoding.
00103 """
00104 if self.min == self.max:
00105 return ("id", self.min)
00106 else:
00107 return ("range", (self.min, self.max))
00108
00109 class resource_range_ip(resource_range):
00110 """
00111 Range of (generic) IP addresses.
00112
00113 Prefixes are converted to ranges on input, and ranges that can be
00114 represented as prefixes are written as prefixes on output.
00115
00116 This is a virtual class. You probably don't want to use it
00117 directly.
00118 """
00119
00120 def _prefixlen(self):
00121 """
00122 Determine whether a resource_range_ip can be expressed as a
00123 prefix.
00124 """
00125 mask = self.min ^ self.max
00126 if self.min & mask != 0:
00127 return -1
00128 prefixlen = self.datum_type.bits
00129 while mask & 1:
00130 prefixlen -= 1
00131 mask >>= 1
00132 if mask:
00133 return -1
00134 else:
00135 return prefixlen
00136
00137 def __str__(self):
00138 """
00139 Convert a resource_range_ip to string format.
00140 """
00141 prefixlen = self._prefixlen()
00142 if prefixlen < 0:
00143 return str(self.min) + "-" + str(self.max)
00144 else:
00145 return str(self.min) + "/" + str(prefixlen)
00146
00147 def to_rfc3779_tuple(self):
00148 """
00149 Convert a resource_range_ip to tuple format for RFC 3779 ASN.1
00150 encoding.
00151 """
00152 prefixlen = self._prefixlen()
00153 if prefixlen < 0:
00154 return ("addressRange", (_long2bs(self.min, self.datum_type.bits, strip = 0),
00155 _long2bs(self.max, self.datum_type.bits, strip = 1)))
00156 else:
00157 return ("addressPrefix", _long2bs(self.min, self.datum_type.bits, prefixlen = prefixlen))
00158
00159 @classmethod
00160 def make_prefix(cls, prefix, prefixlen):
00161 """
00162 Construct a resource range corresponding to a prefix.
00163 """
00164 assert isinstance(prefix, cls.datum_type) and isinstance(prefixlen, (int, long))
00165 assert prefixlen >= 0 and prefixlen <= cls.datum_type.bits, "Nonsensical prefix length: %s" % prefixlen
00166 mask = (1 << (cls.datum_type.bits - prefixlen)) - 1
00167 assert (prefix & mask) == 0, "Resource not in canonical form: %s/%s" % (prefix, prefixlen)
00168 return cls(cls.datum_type(prefix), cls.datum_type(prefix | mask))
00169
00170 class resource_range_ipv4(resource_range_ip):
00171 """
00172 Range of IPv4 addresses.
00173 """
00174
00175
00176
00177
00178 datum_type = rpki.ipaddrs.v4addr
00179
00180 class resource_range_ipv6(resource_range_ip):
00181 """
00182 Range of IPv6 addresses.
00183 """
00184
00185
00186
00187
00188 datum_type = rpki.ipaddrs.v6addr
00189
00190 def _rsplit(rset, that):
00191 """
00192 Utility function to split a resource range into two resource ranges.
00193 """
00194 this = rset.pop(0)
00195 cell_type = type(this.min)
00196 assert type(this) is type(that) and type(this.max) is cell_type and \
00197 type(that.min) is cell_type and type(that.max) is cell_type
00198 if this.min < that.min:
00199 rset.insert(0, type(this)(this.min, cell_type(that.min - 1)))
00200 rset.insert(1, type(this)(that.min, this.max))
00201 else:
00202 assert this.max > that.max
00203 rset.insert(0, type(this)(this.min, that.max))
00204 rset.insert(1, type(this)(cell_type(that.max + 1), this.max))
00205
00206 class resource_set(list):
00207 """
00208 Generic resource set, a list subclass containing resource ranges.
00209
00210 This is a virtual class. You probably don't want to use it
00211 directly.
00212 """
00213
00214
00215
00216
00217 inherit = False
00218
00219 def __init__(self, ini = None):
00220 """
00221 Initialize a resource_set.
00222 """
00223 list.__init__(self)
00224 if isinstance(ini, (int, long)):
00225 ini = str(ini)
00226 if ini is inherit_token:
00227 self.inherit = True
00228 elif isinstance(ini, str) and len(ini):
00229 self.extend(self.parse_str(s) for s in ini.split(","))
00230 elif isinstance(ini, tuple):
00231 self.parse_rfc3779_tuple(ini)
00232 elif isinstance(ini, list):
00233 self.extend(ini)
00234 else:
00235 assert ini is None or (isinstance(ini, str) and ini == ""), "Unexpected initializer: %s" % str(ini)
00236 assert not self.inherit or not self
00237 self.sort()
00238 for i in xrange(len(self) - 2, -1, -1):
00239 if self[i].max + 1 == self[i+1].min:
00240 self[i] = type(self[i])(self[i].min, self[i+1].max)
00241 self.pop(i + 1)
00242 if __debug__:
00243 for i in xrange(0, len(self) - 1):
00244 assert self[i].max < self[i+1].min, "Resource overlap: %s %s" % (self[i], self[i+1])
00245
00246 def __str__(self):
00247 """
00248 Convert a resource_set to string format.
00249 """
00250 if self.inherit:
00251 return inherit_token
00252 else:
00253 return ",".join(str(x) for x in self)
00254
00255 def _comm(self, other):
00256 """
00257 Like comm(1), sort of.
00258
00259 Returns a tuple of three resource sets: resources only in self,
00260 resources only in other, and resources in both. Used (not very
00261 efficiently) as the basis for most set operations on resource
00262 sets.
00263 """
00264 assert not self.inherit
00265 assert type(self) is type(other), "Type mismatch %r %r" % (type(self), type(other))
00266 set1 = self[:]
00267 set2 = other[:]
00268 only1, only2, both = [], [], []
00269 while set1 or set2:
00270 if set1 and (not set2 or set1[0].max < set2[0].min):
00271 only1.append(set1.pop(0))
00272 elif set2 and (not set1 or set2[0].max < set1[0].min):
00273 only2.append(set2.pop(0))
00274 elif set1[0].min < set2[0].min:
00275 _rsplit(set1, set2[0])
00276 elif set2[0].min < set1[0].min:
00277 _rsplit(set2, set1[0])
00278 elif set1[0].max < set2[0].max:
00279 _rsplit(set2, set1[0])
00280 elif set2[0].max < set1[0].max:
00281 _rsplit(set1, set2[0])
00282 else:
00283 assert set1[0].min == set2[0].min and set1[0].max == set2[0].max
00284 both.append(set1.pop(0))
00285 set2.pop(0)
00286 return type(self)(only1), type(self)(only2), type(self)(both)
00287
00288 def union(self, other):
00289 """
00290 Set union for resource sets.
00291 """
00292 assert not self.inherit
00293 assert type(self) is type(other), "Type mismatch: %r %r" % (type(self), type(other))
00294 set1 = self[:]
00295 set2 = other[:]
00296 result = []
00297 while set1 or set2:
00298 if set1 and (not set2 or set1[0].max < set2[0].min):
00299 result.append(set1.pop(0))
00300 elif set2 and (not set1 or set2[0].max < set1[0].min):
00301 result.append(set2.pop(0))
00302 else:
00303 this = set1.pop(0)
00304 that = set2.pop(0)
00305 assert type(this) is type(that)
00306 if this.min < that.min: min = this.min
00307 else: min = that.min
00308 if this.max > that.max: max = this.max
00309 else: max = that.max
00310 result.append(type(this)(min, max))
00311 while set1 and set1[0].max <= max:
00312 assert set1[0].min >= min
00313 del set1[0]
00314 while set2 and set2[0].max <= max:
00315 assert set2[0].min >= min
00316 del set2[0]
00317 return type(self)(result)
00318
00319 def intersection(self, other):
00320 """Set intersection for resource sets."""
00321 return self._comm(other)[2]
00322
00323 def difference(self, other):
00324 """Set difference for resource sets."""
00325 return self._comm(other)[0]
00326
00327 def symmetric_difference(self, other):
00328 """Set symmetric difference (XOR) for resource sets."""
00329 com = self._comm(other)
00330 return com[0].union(com[1])
00331
00332 def contains(self, item):
00333 """
00334 Set membership test for resource sets.
00335 """
00336 assert not self.inherit
00337 if not self:
00338 return False
00339 if type(item) is type(self[0]):
00340 min = item.min
00341 max = item.max
00342 else:
00343 min = item
00344 max = item
00345 lo = 0
00346 hi = len(self)
00347 while lo < hi:
00348 mid = (lo + hi) / 2
00349 if self[mid].max < max:
00350 lo = mid + 1
00351 else:
00352 hi = mid
00353 return lo < len(self) and self[lo].min <= min and self[lo].max >= max
00354
00355 def issubset(self, other):
00356 """
00357 Test whether self is a subset (possibly improper) of other.
00358 """
00359 for i in self:
00360 if not other.contains(i):
00361 return False
00362 return True
00363
00364 def issuperset(self, other):
00365 """Test whether self is a superset (possibly improper) of other."""
00366 return other.issubset(self)
00367
00368 @classmethod
00369 def from_sql(cls, sql, query, args = None):
00370 """
00371 Create resource set from an SQL query.
00372
00373 sql is an object that supports execute() and fetchall() methods
00374 like a DB API 2.0 cursor object.
00375
00376 query is an SQL query that returns a sequence of (min, max) pairs.
00377 """
00378
00379 sql.execute(query, args)
00380 return cls(ini = [cls.range_type(cls.range_type.datum_type(b),
00381 cls.range_type.datum_type(e))
00382 for (b, e) in sql.fetchall()])
00383
00384 class resource_set_as(resource_set):
00385 """
00386 Autonomous System Number resource set.
00387 """
00388
00389
00390
00391
00392 range_type = resource_range_as
00393
00394 def parse_str(self, x):
00395 """
00396 Parse ASN resource sets from text (eg, XML attributes).
00397 """
00398 r = re.match("^([0-9]+)-([0-9]+)$", x)
00399 if r:
00400 return resource_range_as(long(r.group(1)), long(r.group(2)))
00401 else:
00402 return resource_range_as(long(x), long(x))
00403
00404 def parse_rfc3779_tuple(self, x):
00405 """
00406 Parse ASN resource from tuple format generated by RFC 3779 ASN.1
00407 decoder.
00408 """
00409 if x[0] == "asIdsOrRanges":
00410 for aor in x[1]:
00411 if aor[0] == "range":
00412 min = aor[1][0]
00413 max = aor[1][1]
00414 else:
00415 min = aor[1]
00416 max = min
00417 self.append(resource_range_as(min, max))
00418 else:
00419 assert x[0] == "inherit"
00420 self.inherit = True
00421
00422 def to_rfc3779_tuple(self):
00423 """
00424 Convert ASN resource set into tuple format used for RFC 3779 ASN.1
00425 encoding.
00426 """
00427 if self:
00428 return ("asIdsOrRanges", tuple(a.to_rfc3779_tuple() for a in self))
00429 elif self.inherit:
00430 return ("inherit", "")
00431 else:
00432 return None
00433
00434 class resource_set_ip(resource_set):
00435 """
00436 (Generic) IP address resource set.
00437
00438 This is a virtual class. You probably don't want to use it
00439 directly.
00440 """
00441
00442 def parse_str(self, x):
00443 """
00444 Parse IP address resource sets from text (eg, XML attributes).
00445 """
00446 r = re.match("^([0-9:.a-fA-F]+)-([0-9:.a-fA-F]+)$", x)
00447 if r:
00448 return self.range_type(self.range_type.datum_type(r.group(1)), self.range_type.datum_type(r.group(2)))
00449 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)$", x)
00450 if r:
00451 return self.range_type.make_prefix(self.range_type.datum_type(r.group(1)), int(r.group(2)))
00452 raise RuntimeError, 'Bad IP resource "%s"' % (x)
00453
00454 def parse_rfc3779_tuple(self, x):
00455 """
00456 Parse IP address resource sets from tuple format generated by RFC
00457 3779 ASN.1 decoder.
00458 """
00459 if x[0] == "addressesOrRanges":
00460 for aor in x[1]:
00461 if aor[0] == "addressRange":
00462 min = _bs2long(aor[1][0], self.range_type.datum_type.bits, 0)
00463 max = _bs2long(aor[1][1], self.range_type.datum_type.bits, 1)
00464 else:
00465 min = _bs2long(aor[1], self.range_type.datum_type.bits, 0)
00466 max = _bs2long(aor[1], self.range_type.datum_type.bits, 1)
00467 self.append(self.range_type(self.range_type.datum_type(min), self.range_type.datum_type(max)))
00468 else:
00469 assert x[0] == "inherit"
00470 self.inherit = True
00471
00472 def to_rfc3779_tuple(self):
00473 """
00474 Convert IP resource set into tuple format used by RFC 3779 ASN.1
00475 encoder.
00476 """
00477 if self:
00478 return (self.afi, ("addressesOrRanges", tuple(a.to_rfc3779_tuple() for a in self)))
00479 elif self.inherit:
00480 return (self.afi, ("inherit", ""))
00481 else:
00482 return None
00483
00484 class resource_set_ipv4(resource_set_ip):
00485 """
00486 IPv4 address resource set.
00487 """
00488
00489
00490
00491
00492 range_type = resource_range_ipv4
00493
00494
00495
00496
00497 afi = "\x00\x01"
00498
00499 class resource_set_ipv6(resource_set_ip):
00500 """
00501 IPv6 address resource set.
00502 """
00503
00504
00505
00506
00507 range_type = resource_range_ipv6
00508
00509
00510
00511
00512 afi = "\x00\x02"
00513
00514 def _bs2long(bs, addrlen, fill):
00515 """
00516 Utility function to convert a bitstring (POW.pkix tuple
00517 representation) into a Python long.
00518 """
00519 x = 0L
00520 for y in bs:
00521 x = (x << 1) | y
00522 for y in xrange(addrlen - len(bs)):
00523 x = (x << 1) | fill
00524 return x
00525
00526 def _long2bs(number, addrlen, prefixlen = None, strip = None):
00527 """
00528 Utility function to convert a Python long into a POW.pkix tuple
00529 bitstring. This is a bit complicated because it supports the
00530 fiendishly compact encoding used in RFC 3779.
00531 """
00532 assert prefixlen is None or strip is None
00533 bs = []
00534 while number:
00535 bs.append(int(number & 1))
00536 number >>= 1
00537 if addrlen > len(bs):
00538 bs.extend((0 for i in xrange(addrlen - len(bs))))
00539 bs.reverse()
00540 if prefixlen is not None:
00541 return tuple(bs[0:prefixlen])
00542 if strip is not None:
00543 while bs and bs[-1] == strip:
00544 bs.pop()
00545 return tuple(bs)
00546
00547 class resource_bag(object):
00548 """
00549 Container to simplify passing around the usual triple of ASN, IPv4,
00550 and IPv6 resource sets.
00551 """
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565 def __init__(self, asn = None, v4 = None, v6 = None, valid_until = None):
00566 self.asn = asn or resource_set_as()
00567 self.v4 = v4 or resource_set_ipv4()
00568 self.v6 = v6 or resource_set_ipv6()
00569 self.valid_until = valid_until
00570
00571 def oversized(self, other):
00572 """
00573 True iff self is oversized with respect to other.
00574 """
00575 return not self.asn.issubset(other.asn) or \
00576 not self.v4.issubset(other.v4) or \
00577 not self.v6.issubset(other.v6)
00578
00579 def undersized(self, other):
00580 """
00581 True iff self is undersized with respect to other.
00582 """
00583 return not other.asn.issubset(self.asn) or \
00584 not other.v4.issubset(self.v4) or \
00585 not other.v6.issubset(self.v6)
00586
00587 @classmethod
00588 def from_rfc3779_tuples(cls, exts):
00589 """
00590 Build a resource_bag from intermediate form generated by RFC 3779
00591 ASN.1 decoder.
00592 """
00593 asn = None
00594 v4 = None
00595 v6 = None
00596 for x in exts:
00597 if x[0] == rpki.oids.name2oid["sbgp-autonomousSysNum"]:
00598 assert len(x[2]) == 1 or x[2][1] is None, "RDI not implemented: %s" % (str(x))
00599 assert asn is None
00600 asn = resource_set_as(x[2][0])
00601 if x[0] == rpki.oids.name2oid["sbgp-ipAddrBlock"]:
00602 for fam in x[2]:
00603 if fam[0] == resource_set_ipv4.afi:
00604 assert v4 is None
00605 v4 = resource_set_ipv4(fam[1])
00606 if fam[0] == resource_set_ipv6.afi:
00607 assert v6 is None
00608 v6 = resource_set_ipv6(fam[1])
00609 return cls(asn, v4, v6)
00610
00611 def empty(self):
00612 """True iff all resource sets in this bag are empty."""
00613 return not self.asn and not self.v4 and not self.v6
00614
00615 def __eq__(self, other):
00616 return self.asn == other.asn and \
00617 self.v4 == other.v4 and \
00618 self.v6 == other.v6 and \
00619 self.valid_until == other.valid_until
00620
00621 def __ne__(self, other):
00622 return not (self == other)
00623
00624 def intersection(self, other):
00625 """
00626 Compute intersection with another resource_bag. valid_until
00627 attribute (if any) inherits from self.
00628 """
00629 return self.__class__(self.asn.intersection(other.asn),
00630 self.v4.intersection(other.v4),
00631 self.v6.intersection(other.v6),
00632 self.valid_until)
00633
00634 def union(self, other):
00635 """
00636 Compute union with another resource_bag. valid_until attribute
00637 (if any) inherits from self.
00638 """
00639 return self.__class__(self.asn.union(other.asn),
00640 self.v4.union(other.v4),
00641 self.v6.union(other.v6),
00642 self.valid_until)
00643
00644 def __str__(self):
00645 s = ""
00646 if self.asn:
00647 s += "ASN: %s" % self.asn
00648 if self.v4:
00649 if s:
00650 s += ", "
00651 s += "V4: %s" % self.v4
00652 if self.v6:
00653 if s:
00654 s += ", "
00655 s += "V6: %s" % self.v6
00656 return s
00657
00658
00659
00660
00661
00662
00663
00664
00665
00666 class roa_prefix(object):
00667 """
00668 ROA prefix. This is similar to the resource_range_ip class, but
00669 differs in that it only represents prefixes, never ranges, and
00670 includes the maximum prefix length as an additional value.
00671
00672 This is a virtual class, you probably don't want to use it directly.
00673 """
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685 def __init__(self, prefix, prefixlen, max_prefixlen = None):
00686 """
00687 Initialize a ROA prefix. max_prefixlen is optional and defaults
00688 to prefixlen. max_prefixlen must not be smaller than prefixlen.
00689 """
00690 if max_prefixlen is None:
00691 max_prefixlen = prefixlen
00692 assert max_prefixlen >= prefixlen, "Bad max_prefixlen: %d must not be shorter than %d" % (max_prefixlen, prefixlen)
00693 self.prefix = prefix
00694 self.prefixlen = prefixlen
00695 self.max_prefixlen = max_prefixlen
00696
00697 def __cmp__(self, other):
00698 """
00699 Compare two ROA prefix objects. Comparision is based on prefix,
00700 prefixlen, and max_prefixlen, in that order.
00701 """
00702 assert self.__class__ is other.__class__
00703 c = self.prefix - other.prefix
00704 if c == 0: c = self.prefixlen - other.prefixlen
00705 if c == 0: c = self.max_prefixlen - other.max_prefixlen
00706 if c < 0: c = -1
00707 if c > 0: c = 1
00708 return c
00709
00710 def __str__(self):
00711 """
00712 Convert a ROA prefix to string format.
00713 """
00714 if self.prefixlen == self.max_prefixlen:
00715 return str(self.prefix) + "/" + str(self.prefixlen)
00716 else:
00717 return str(self.prefix) + "/" + str(self.prefixlen) + "-" + str(self.max_prefixlen)
00718
00719 def to_resource_range(self):
00720 """
00721 Convert this ROA prefix to the equivilent resource_range_ip
00722 object. This is an irreversable transformation because it loses
00723 the max_prefixlen attribute, nothing we can do about that.
00724 """
00725 return self.range_type.make_prefix(self.prefix, self.prefixlen)
00726
00727 def min(self):
00728 """Return lowest address covered by prefix."""
00729 return self.prefix
00730
00731 def max(self):
00732 """
00733 Return highest address covered by prefix.
00734 """
00735 t = self.range_type.datum_type
00736 return t(self.prefix | ((1 << (t.bits - self.prefixlen)) - 1))
00737
00738 def to_roa_tuple(self):
00739 """
00740 Convert a resource_range_ip to tuple format for ROA ASN.1
00741 encoding.
00742 """
00743 return (_long2bs(self.prefix, self.range_type.datum_type.bits, prefixlen = self.prefixlen),
00744 None if self.prefixlen == self.max_prefixlen else self.max_prefixlen)
00745
00746 class roa_prefix_ipv4(roa_prefix):
00747 """
00748 IPv4 ROA prefix.
00749 """
00750
00751
00752
00753
00754 range_type = resource_range_ipv4
00755
00756 class roa_prefix_ipv6(roa_prefix):
00757 """
00758 IPv6 ROA prefix.
00759 """
00760
00761
00762
00763
00764 range_type = resource_range_ipv6
00765
00766 class roa_prefix_set(list):
00767 """
00768 Set of ROA prefixes, analogous to the resource_set_ip class.
00769 """
00770
00771 def __init__(self, ini = None):
00772 """
00773 Initialize a ROA prefix set.
00774 """
00775 list.__init__(self)
00776 if isinstance(ini, str) and len(ini):
00777 self.extend(self.parse_str(s) for s in ini.split(","))
00778 elif isinstance(ini, (list, tuple)):
00779 self.extend(ini)
00780 else:
00781 assert ini is None or ini == "", "Unexpected initializer: %s" % str(ini)
00782 self.sort()
00783
00784
00785
00786
00787 if False and __debug__:
00788 for i in xrange(0, len(self) - 1):
00789 assert self[i].max() < self[i+1].min(), "Prefix overlap: %s %s" % (self[i], self[i+1])
00790
00791 def __str__(self):
00792 """Convert a ROA prefix set to string format."""
00793 return ",".join(str(x) for x in self)
00794
00795 def parse_str(self, x):
00796 """
00797 Parse ROA prefix from text (eg, an XML attribute).
00798 """
00799 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)-([0-9]+)$", x)
00800 if r:
00801 return self.prefix_type(self.prefix_type.range_type.datum_type(r.group(1)), int(r.group(2)), int(r.group(3)))
00802 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)$", x)
00803 if r:
00804 return self.prefix_type(self.prefix_type.range_type.datum_type(r.group(1)), int(r.group(2)))
00805 raise RuntimeError, 'Bad ROA prefix "%s"' % (x)
00806
00807 def to_resource_set(self):
00808 """
00809 Convert a ROA prefix set to a resource set. This is an
00810 irreversable transformation. We have to compute a union here
00811 because ROA prefix sets can include overlaps, while RFC 3779
00812 resource sets cannot. This is ugly, and there is almost certainly
00813 a more efficient way to do this, but start by getting the output
00814 right before worrying about making it fast or pretty.
00815 """
00816 r = self.resource_set_type()
00817 s = self.resource_set_type()
00818 s.append(None)
00819 for p in self:
00820 s[0] = p.to_resource_range()
00821 r = r.union(s)
00822 return r
00823
00824 @classmethod
00825 def from_sql(cls, sql, query, args = None):
00826 """
00827 Create ROA prefix set from an SQL query.
00828
00829 sql is an object that supports execute() and fetchall() methods
00830 like a DB API 2.0 cursor object.
00831
00832 query is an SQL query that returns a sequence of (prefix,
00833 prefixlen, max_prefixlen) triples.
00834 """
00835
00836 sql.execute(query, args)
00837 return cls([cls.prefix_type(cls.prefix_type.range_type.datum_type(x), int(y), int(z))
00838 for (x, y, z) in sql.fetchall()])
00839
00840 def to_roa_tuple(self):
00841 """
00842 Convert ROA prefix set into tuple format used by ROA ASN.1
00843 encoder. This is a variation on the format used in RFC 3779.
00844 """
00845 if self:
00846 return (self.resource_set_type.afi, tuple(a.to_roa_tuple() for a in self))
00847 else:
00848 return None
00849
00850 class roa_prefix_set_ipv4(roa_prefix_set):
00851 """
00852 Set of IPv4 ROA prefixes.
00853 """
00854
00855
00856
00857
00858 prefix_type = roa_prefix_ipv4
00859
00860
00861
00862
00863 resource_set_type = resource_set_ipv4
00864
00865 class roa_prefix_set_ipv6(roa_prefix_set):
00866 """
00867 Set of IPv6 ROA prefixes.
00868 """
00869
00870
00871
00872
00873 prefix_type = roa_prefix_ipv6
00874
00875
00876
00877
00878 resource_set_type = resource_set_ipv6
00879
00880
00881
00882 if __name__ == "__main__":
00883
00884 def test1(t, s1, s2):
00885 if isinstance(s1, str) and isinstance(s2, str):
00886 print "x: ", s1
00887 print "y: ", s2
00888 r1 = t(s1)
00889 r2 = t(s2)
00890 print "x: ", r1
00891 print "y: ", r2
00892 v1 = r1._comm(r2)
00893 v2 = r2._comm(r1)
00894 assert v1[0] == v2[1] and v1[1] == v2[0] and v1[2] == v2[2]
00895 for i in r1: assert r1.contains(i) and r1.contains(i.min) and r1.contains(i.max)
00896 for i in r2: assert r2.contains(i) and r2.contains(i.min) and r2.contains(i.max)
00897 for i in v1[0]: assert r1.contains(i) and not r2.contains(i)
00898 for i in v1[1]: assert not r1.contains(i) and r2.contains(i)
00899 for i in v1[2]: assert r1.contains(i) and r2.contains(i)
00900 v1 = r1.union(r2)
00901 v2 = r2.union(r1)
00902 assert v1 == v2
00903 print "x|y:", v1
00904 v1 = r1.difference(r2)
00905 v2 = r2.difference(r1)
00906 print "x-y:", v1
00907 print "y-x:", v2
00908 v1 = r1.symmetric_difference(r2)
00909 v2 = r2.symmetric_difference(r1)
00910 assert v1 == v2
00911 print "x^y:", v1
00912 v1 = r1.intersection(r2)
00913 v2 = r2.intersection(r1)
00914 assert v1 == v2
00915 print "x&y:", v1
00916
00917 def test2(t, s1, s2):
00918 print "x: ", s1
00919 print "y: ", s2
00920 r1 = t(s1)
00921 r2 = t(s2)
00922 print "x: ", r1
00923 print "y: ", r2
00924 print "x>y:", (r1 > r2)
00925 print "x<y:", (r1 < r2)
00926 test1(t.resource_set_type, r1.to_resource_set(), r2.to_resource_set())
00927
00928 print
00929 print "Testing set operations on resource sets"
00930 print
00931 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")
00932 print
00933 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32")
00934 print
00935 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.0.0.0/24")
00936 print
00937 test1(resource_set_ipv4, "10.0.0.0/24", "10.3.0.0/24,10.0.0.77/32")
00938 print
00939 test1(resource_set_ipv4, "10.0.0.0/24", "10.0.0.0/32,10.0.0.2/32,10.0.0.4/32")
00940 print
00941 print "Testing set operations on ROA prefixes"
00942 print
00943 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")
00944 print
00945 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")
00946 print
00947 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")
00948 print