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 2510 2009-06-09 20:25:16Z 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 == 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 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 %s %s" % (repr(type(self)), repr(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: %s %s" % (repr(type(self)), repr(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 return type(self)(result)
00312
00313 def intersection(self, other):
00314 """Set intersection for resource sets."""
00315 return self._comm(other)[2]
00316
00317 def difference(self, other):
00318 """Set difference for resource sets."""
00319 return self._comm(other)[0]
00320
00321 def symmetric_difference(self, other):
00322 """Set symmetric difference (XOR) for resource sets."""
00323 com = self._comm(other)
00324 return com[0].union(com[1])
00325
00326 def contains(self, item):
00327 """
00328 Set membership test for resource sets.
00329 """
00330 assert not self.inherit
00331 for i in self:
00332 if isinstance(item, type(i)) and i.min <= item.min and i.max >= item.max:
00333 return True
00334 elif isinstance(item, type(i.min)) and i.min <= item and i.max >= item:
00335 return True
00336 else:
00337 assert isinstance(item, (type(i), type(i.min)))
00338 return False
00339
00340 def issubset(self, other):
00341 """
00342 Test whether self is a subset (possibly improper) of other.
00343 """
00344 for i in self:
00345 if not other.contains(i):
00346 return False
00347 return True
00348
00349 def issuperset(self, other):
00350 """Test whether self is a superset (possibly improper) of other."""
00351 return other.issubset(self)
00352
00353 @classmethod
00354 def from_sql(cls, sql, query, args = None):
00355 """
00356 Create resource set from an SQL query.
00357
00358 sql is an object that supports execute() and fetchall() methods
00359 like a DB API 2.0 cursor object.
00360
00361 query is an SQL query that returns a sequence of (min, max) pairs.
00362 """
00363
00364 sql.execute(query, args)
00365 return cls(ini = [cls.range_type(cls.range_type.datum_type(b),
00366 cls.range_type.datum_type(e))
00367 for (b, e) in sql.fetchall()])
00368
00369 class resource_set_as(resource_set):
00370 """
00371 Autonomous System Number resource set.
00372 """
00373
00374
00375
00376
00377 range_type = resource_range_as
00378
00379 def parse_str(self, x):
00380 """
00381 Parse ASN resource sets from text (eg, XML attributes).
00382 """
00383 r = re.match("^([0-9]+)-([0-9]+)$", x)
00384 if r:
00385 return resource_range_as(long(r.group(1)), long(r.group(2)))
00386 else:
00387 return resource_range_as(long(x), long(x))
00388
00389 def parse_rfc3779_tuple(self, x):
00390 """
00391 Parse ASN resource from tuple format generated by RFC 3779 ASN.1
00392 decoder.
00393 """
00394 if x[0] == "asIdsOrRanges":
00395 for aor in x[1]:
00396 if aor[0] == "range":
00397 min = aor[1][0]
00398 max = aor[1][1]
00399 else:
00400 min = aor[1]
00401 max = min
00402 self.append(resource_range_as(min, max))
00403 else:
00404 assert x[0] == "inherit"
00405 self.inherit = True
00406
00407 def to_rfc3779_tuple(self):
00408 """
00409 Convert ASN resource set into tuple format used for RFC 3779 ASN.1
00410 encoding.
00411 """
00412 if self:
00413 return ("asIdsOrRanges", tuple(a.to_rfc3779_tuple() for a in self))
00414 elif self.inherit:
00415 return ("inherit", "")
00416 else:
00417 return None
00418
00419 class resource_set_ip(resource_set):
00420 """
00421 (Generic) IP address resource set.
00422
00423 This is a virtual class. You probably don't want to use it
00424 directly.
00425 """
00426
00427 def parse_str(self, x):
00428 """
00429 Parse IP address resource sets from text (eg, XML attributes).
00430 """
00431 r = re.match("^([0-9:.a-fA-F]+)-([0-9:.a-fA-F]+)$", x)
00432 if r:
00433 return self.range_type(self.range_type.datum_type(r.group(1)), self.range_type.datum_type(r.group(2)))
00434 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)$", x)
00435 if r:
00436 return self.range_type.make_prefix(self.range_type.datum_type(r.group(1)), int(r.group(2)))
00437 raise RuntimeError, 'Bad IP resource "%s"' % (x)
00438
00439 def parse_rfc3779_tuple(self, x):
00440 """
00441 Parse IP address resource sets from tuple format generated by RFC
00442 3779 ASN.1 decoder.
00443 """
00444 if x[0] == "addressesOrRanges":
00445 for aor in x[1]:
00446 if aor[0] == "addressRange":
00447 min = _bs2long(aor[1][0], self.range_type.datum_type.bits, 0)
00448 max = _bs2long(aor[1][1], self.range_type.datum_type.bits, 1)
00449 else:
00450 min = _bs2long(aor[1], self.range_type.datum_type.bits, 0)
00451 max = _bs2long(aor[1], self.range_type.datum_type.bits, 1)
00452 self.append(self.range_type(self.range_type.datum_type(min), self.range_type.datum_type(max)))
00453 else:
00454 assert x[0] == "inherit"
00455 self.inherit = True
00456
00457 def to_rfc3779_tuple(self):
00458 """
00459 Convert IP resource set into tuple format used by RFC 3779 ASN.1
00460 encoder.
00461 """
00462 if self:
00463 return (self.afi, ("addressesOrRanges", tuple(a.to_rfc3779_tuple() for a in self)))
00464 elif self.inherit:
00465 return (self.afi, ("inherit", ""))
00466 else:
00467 return None
00468
00469 class resource_set_ipv4(resource_set_ip):
00470 """
00471 IPv4 address resource set.
00472 """
00473
00474
00475
00476
00477 range_type = resource_range_ipv4
00478
00479
00480
00481
00482 afi = "\x00\x01"
00483
00484 class resource_set_ipv6(resource_set_ip):
00485 """
00486 IPv6 address resource set.
00487 """
00488
00489
00490
00491
00492 range_type = resource_range_ipv6
00493
00494
00495
00496
00497 afi = "\x00\x02"
00498
00499 def _bs2long(bs, addrlen, fill):
00500 """
00501 Utility function to convert a bitstring (POW.pkix tuple
00502 representation) into a Python long.
00503 """
00504 x = 0L
00505 for y in bs:
00506 x = (x << 1) | y
00507 for y in xrange(addrlen - len(bs)):
00508 x = (x << 1) | fill
00509 return x
00510
00511 def _long2bs(number, addrlen, prefixlen = None, strip = None):
00512 """
00513 Utility function to convert a Python long into a POW.pkix tuple
00514 bitstring. This is a bit complicated because it supports the
00515 fiendishly compact encoding used in RFC 3779.
00516 """
00517 assert prefixlen is None or strip is None
00518 bs = []
00519 while number:
00520 bs.append(int(number & 1))
00521 number >>= 1
00522 if addrlen > len(bs):
00523 bs.extend((0 for i in xrange(addrlen - len(bs))))
00524 bs.reverse()
00525 if prefixlen is not None:
00526 return tuple(bs[0:prefixlen])
00527 if strip is not None:
00528 while bs and bs[-1] == strip:
00529 bs.pop()
00530 return tuple(bs)
00531
00532 class resource_bag(object):
00533 """
00534 Container to simplify passing around the usual triple of ASN, IPv4,
00535 and IPv6 resource sets.
00536 """
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550 def __init__(self, asn = None, v4 = None, v6 = None, valid_until = None):
00551 self.asn = asn or resource_set_as()
00552 self.v4 = v4 or resource_set_ipv4()
00553 self.v6 = v6 or resource_set_ipv6()
00554 self.valid_until = valid_until
00555
00556 def oversized(self, other):
00557 """
00558 True iff self is oversized with respect to other.
00559 """
00560 return not self.asn.issubset(other.asn) or \
00561 not self.v4.issubset(other.v4) or \
00562 not self.v6.issubset(other.v6)
00563
00564 def undersized(self, other):
00565 """
00566 True iff self is undersized with respect to other.
00567 """
00568 return not other.asn.issubset(self.asn) or \
00569 not other.v4.issubset(self.v4) or \
00570 not other.v6.issubset(self.v6)
00571
00572 @classmethod
00573 def from_rfc3779_tuples(cls, exts):
00574 """
00575 Build a resource_bag from intermediate form generated by RFC 3779
00576 ASN.1 decoder.
00577 """
00578 asn = None
00579 v4 = None
00580 v6 = None
00581 for x in exts:
00582 if x[0] == rpki.oids.name2oid["sbgp-autonomousSysNum"]:
00583 assert len(x[2]) == 1 or x[2][1] is None, "RDI not implemented: %s" % (str(x))
00584 assert asn is None
00585 asn = resource_set_as(x[2][0])
00586 if x[0] == rpki.oids.name2oid["sbgp-ipAddrBlock"]:
00587 for fam in x[2]:
00588 if fam[0] == resource_set_ipv4.afi:
00589 assert v4 is None
00590 v4 = resource_set_ipv4(fam[1])
00591 if fam[0] == resource_set_ipv6.afi:
00592 assert v6 is None
00593 v6 = resource_set_ipv6(fam[1])
00594 return cls(asn, v4, v6)
00595
00596 def empty(self):
00597 """True iff all resource sets in this bag are empty."""
00598 return not self.asn and not self.v4 and not self.v6
00599
00600 def __eq__(self, other):
00601 return self.asn == other.asn and \
00602 self.v4 == other.v4 and \
00603 self.v6 == other.v6 and \
00604 self.valid_until == other.valid_until
00605
00606 def __ne__(self, other):
00607 return not (self == other)
00608
00609 def intersection(self, other):
00610 """
00611 Compute intersection with another resource_bag. valid_until
00612 attribute (if any) inherits from self.
00613 """
00614 return self.__class__(self.asn.intersection(other.asn),
00615 self.v4.intersection(other.v4),
00616 self.v6.intersection(other.v6),
00617 self.valid_until)
00618
00619 def union(self, other):
00620 """
00621 Compute union with another resource_bag. valid_until attribute
00622 (if any) inherits from self.
00623 """
00624 return self.__class__(self.asn.union(other.asn),
00625 self.v4.union(other.v4),
00626 self.v6.union(other.v6),
00627 self.valid_until)
00628
00629 def __str__(self):
00630 s = ""
00631 if self.asn:
00632 s += "ASN: %s" % self.asn
00633 if self.v4:
00634 if s:
00635 s += ", "
00636 s += "V4: %s" % self.v4
00637 if self.v6:
00638 if s:
00639 s += ", "
00640 s += "V6: %s" % self.v6
00641 return s
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651 class roa_prefix(object):
00652 """
00653 ROA prefix. This is similar to the resource_range_ip class, but
00654 differs in that it only represents prefixes, never ranges, and
00655 includes the maximum prefix length as an additional value.
00656
00657 This is a virtual class, you probably don't want to use it directly.
00658 """
00659
00660
00661
00662
00663
00664
00665
00666
00667
00668
00669
00670 def __init__(self, prefix, prefixlen, max_prefixlen = None):
00671 """
00672 Initialize a ROA prefix. max_prefixlen is optional and defaults
00673 to prefixlen. max_prefixlen must not be smaller than prefixlen.
00674 """
00675 if max_prefixlen is None:
00676 max_prefixlen = prefixlen
00677 assert max_prefixlen >= prefixlen, "Bad max_prefixlen: %d must not be shorter than %d" % (max_prefixlen, prefixlen)
00678 self.prefix = prefix
00679 self.prefixlen = prefixlen
00680 self.max_prefixlen = max_prefixlen
00681
00682 def __cmp__(self, other):
00683 """
00684 Compare two ROA prefix objects. Comparision is based on prefix,
00685 prefixlen, and max_prefixlen, in that order.
00686 """
00687 assert self.__class__ is other.__class__
00688 c = self.prefix - other.prefix
00689 if c == 0: c = self.prefixlen - other.prefixlen
00690 if c == 0: c = self.max_prefixlen - other.max_prefixlen
00691 if c < 0: c = -1
00692 if c > 0: c = 1
00693 return c
00694
00695 def __str__(self):
00696 """
00697 Convert a ROA prefix to string format.
00698 """
00699 if self.prefixlen == self.max_prefixlen:
00700 return str(self.prefix) + "/" + str(self.prefixlen)
00701 else:
00702 return str(self.prefix) + "/" + str(self.prefixlen) + "-" + str(self.max_prefixlen)
00703
00704 def to_resource_range(self):
00705 """
00706 Convert this ROA prefix to the equivilent resource_range_ip
00707 object. This is an irreversable transformation because it loses
00708 the max_prefixlen attribute, nothing we can do about that.
00709 """
00710 return self.range_type.make_prefix(self.prefix, self.prefixlen)
00711
00712 def min(self):
00713 """Return lowest address covered by prefix."""
00714 return self.prefix
00715
00716 def max(self):
00717 """
00718 Return highest address covered by prefix.
00719 """
00720 t = self.range_type.datum_type
00721 return t(self.prefix | ((1 << (t.bits - self.prefixlen)) - 1))
00722
00723 def to_roa_tuple(self):
00724 """
00725 Convert a resource_range_ip to tuple format for ROA ASN.1
00726 encoding.
00727 """
00728 return (_long2bs(self.prefix, self.range_type.datum_type.bits, prefixlen = self.prefixlen),
00729 None if self.prefixlen == self.max_prefixlen else self.max_prefixlen)
00730
00731 class roa_prefix_ipv4(roa_prefix):
00732 """
00733 IPv4 ROA prefix.
00734 """
00735
00736
00737
00738
00739 range_type = resource_range_ipv4
00740
00741 class roa_prefix_ipv6(roa_prefix):
00742 """
00743 IPv6 ROA prefix.
00744 """
00745
00746
00747
00748
00749 range_type = resource_range_ipv6
00750
00751 class roa_prefix_set(list):
00752 """
00753 Set of ROA prefixes, analogous to the resource_set_ip class.
00754 """
00755
00756 def __init__(self, ini = None):
00757 """
00758 Initialize a ROA prefix set.
00759 """
00760 list.__init__(self)
00761 if isinstance(ini, str) and len(ini):
00762 self.extend(self.parse_str(s) for s in ini.split(","))
00763 elif isinstance(ini, (list, tuple)):
00764 self.extend(ini)
00765 else:
00766 assert ini is None or ini == "", "Unexpected initializer: %s" % str(ini)
00767 self.sort()
00768
00769
00770
00771
00772 if False and __debug__:
00773 for i in xrange(0, len(self) - 1):
00774 assert self[i].max() < self[i+1].min(), "Prefix overlap: %s %s" % (self[i], self[i+1])
00775
00776 def __str__(self):
00777 """Convert a ROA prefix set to string format."""
00778 return ",".join(str(x) for x in self)
00779
00780 def parse_str(self, x):
00781 """
00782 Parse ROA prefix from text (eg, an XML attribute).
00783 """
00784 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)-([0-9]+)$", x)
00785 if r:
00786 return self.prefix_type(self.prefix_type.range_type.datum_type(r.group(1)), int(r.group(2)), int(r.group(3)))
00787 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)$", x)
00788 if r:
00789 return self.prefix_type(self.prefix_type.range_type.datum_type(r.group(1)), int(r.group(2)))
00790 raise RuntimeError, 'Bad ROA prefix "%s"' % (x)
00791
00792 def to_resource_set(self):
00793 """
00794 Convert a ROA prefix set to a resource set. This is an
00795 irreversable transformation. We have to compute a union here
00796 because ROA prefix sets can include overlaps, while RFC 3779
00797 resource sets cannot. This is ugly, and there is almost certainly
00798 a more efficient way to do this, but start by getting the output
00799 right before worrying about making it fast or pretty.
00800 """
00801 r = self.resource_set_type()
00802 s = self.resource_set_type()
00803 s.append(None)
00804 for p in self:
00805 s[0] = p.to_resource_range()
00806 r = r.union(s)
00807 return r
00808
00809 @classmethod
00810 def from_sql(cls, sql, query, args = None):
00811 """
00812 Create ROA prefix set from an SQL query.
00813
00814 sql is an object that supports execute() and fetchall() methods
00815 like a DB API 2.0 cursor object.
00816
00817 query is an SQL query that returns a sequence of (prefix,
00818 prefixlen, max_prefixlen) triples.
00819 """
00820
00821 sql.execute(query, args)
00822 return cls([cls.prefix_type(cls.prefix_type.range_type.datum_type(x), int(y), int(z))
00823 for (x, y, z) in sql.fetchall()])
00824
00825 def to_roa_tuple(self):
00826 """
00827 Convert ROA prefix set into tuple format used by ROA ASN.1
00828 encoder. This is a variation on the format used in RFC 3779.
00829 """
00830 if self:
00831 return (self.resource_set_type.afi, tuple(a.to_roa_tuple() for a in self))
00832 else:
00833 return None
00834
00835 class roa_prefix_set_ipv4(roa_prefix_set):
00836 """
00837 Set of IPv4 ROA prefixes.
00838 """
00839
00840
00841
00842
00843 prefix_type = roa_prefix_ipv4
00844
00845
00846
00847
00848 resource_set_type = resource_set_ipv4
00849
00850 class roa_prefix_set_ipv6(roa_prefix_set):
00851 """
00852 Set of IPv6 ROA prefixes.
00853 """
00854
00855
00856
00857
00858 prefix_type = roa_prefix_ipv6
00859
00860
00861
00862
00863 resource_set_type = resource_set_ipv6
00864
00865
00866
00867 if __name__ == "__main__":
00868
00869 def test1(t, s1, s2):
00870 if isinstance(s1, str) and isinstance(s2, str):
00871 print "x: ", s1
00872 print "y: ", s2
00873 r1 = t(s1)
00874 r2 = t(s2)
00875 print "x: ", r1
00876 print "y: ", r2
00877 v1 = r1._comm(r2)
00878 v2 = r2._comm(r1)
00879 assert v1[0] == v2[1] and v1[1] == v2[0] and v1[2] == v2[2]
00880 for i in r1: assert r1.contains(i) and r1.contains(i.min) and r1.contains(i.max)
00881 for i in r2: assert r2.contains(i) and r2.contains(i.min) and r2.contains(i.max)
00882 for i in v1[0]: assert r1.contains(i) and not r2.contains(i)
00883 for i in v1[1]: assert not r1.contains(i) and r2.contains(i)
00884 for i in v1[2]: assert r1.contains(i) and r2.contains(i)
00885 v1 = r1.union(r2)
00886 v2 = r2.union(r1)
00887 assert v1 == v2
00888 print "x|y:", v1
00889 v1 = r1.difference(r2)
00890 v2 = r2.difference(r1)
00891 print "x-y:", v1
00892 print "y-x:", v2
00893 v1 = r1.symmetric_difference(r2)
00894 v2 = r2.symmetric_difference(r1)
00895 assert v1 == v2
00896 print "x^y:", v1
00897 v1 = r1.intersection(r2)
00898 v2 = r2.intersection(r1)
00899 assert v1 == v2
00900 print "x&y:", v1
00901
00902 def test2(t, s1, s2):
00903 print "x: ", s1
00904 print "y: ", s2
00905 r1 = t(s1)
00906 r2 = t(s2)
00907 print "x: ", r1
00908 print "y: ", r2
00909 print "x>y:", (r1 > r2)
00910 print "x<y:", (r1 < r2)
00911 test1(t.resource_set_type, r1.to_resource_set(), r2.to_resource_set())
00912
00913 print
00914 print "Testing set operations on resource sets"
00915 print
00916 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")
00917 print
00918 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32")
00919 print
00920 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.0.0.0/24")
00921 print
00922 test1(resource_set_ipv4, "10.0.0.0/24", "10.3.0.0/24,10.0.0.77/32")
00923 print
00924 print "Testing set operations on ROA prefixes"
00925 print
00926 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")
00927 print
00928 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")
00929 print
00930 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")
00931 print