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 2457 2009-05-28 18:21:06Z 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, address, prefixlen):
00161 """
00162 Construct a resource range corresponding to a prefix.
00163 """
00164 assert isinstance(address, 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 (address & mask) == 0, "Resource not in canonical form: %s/%s" % (address, prefixlen)
00168 return cls(cls.datum_type(address), cls.datum_type(address | 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 def __init__(self, address, prefixlen, max_prefixlen = None):
00670 """
00671 Initialize a ROA prefix. max_prefixlen is optional and defaults
00672 to prefixlen. max_prefixlen must not be smaller than prefixlen.
00673 """
00674 if max_prefixlen is None:
00675 max_prefixlen = prefixlen
00676 assert max_prefixlen >= prefixlen, "Bad max_prefixlen: %d must not be shorter than %d" % (max_prefixlen, prefixlen)
00677 self.address = address
00678 self.prefixlen = prefixlen
00679 self.max_prefixlen = max_prefixlen
00680
00681 def __cmp__(self, other):
00682 """
00683 Compare two ROA prefix objects. Comparision is based on address,
00684 prefixlen, and max_prefixlen, in that order.
00685 """
00686 assert self.__class__ is other.__class__
00687 c = self.address - other.address
00688 if c == 0: c = self.prefixlen - other.prefixlen
00689 if c == 0: c = self.max_prefixlen - other.max_prefixlen
00690 if c < 0: c = -1
00691 if c > 0: c = 1
00692 return c
00693
00694 def __str__(self):
00695 """
00696 Convert a ROA prefix to string format.
00697 """
00698 if self.prefixlen == self.max_prefixlen:
00699 return str(self.address) + "/" + str(self.prefixlen)
00700 else:
00701 return str(self.address) + "/" + str(self.prefixlen) + "-" + str(self.max_prefixlen)
00702
00703 def to_resource_range(self):
00704 """
00705 Convert this ROA prefix to the equivilent resource_range_ip
00706 object. This is an irreversable transformation because it loses
00707 the max_prefixlen attribute, nothing we can do about that.
00708 """
00709 return self.range_type.make_prefix(self.address, self.prefixlen)
00710
00711 def min(self):
00712 """Return lowest address covered by prefix."""
00713 return self.address
00714
00715 def max(self):
00716 """
00717 Return highest address covered by prefix.
00718 """
00719 t = self.range_type.datum_type
00720 return t(self.address | ((1 << (t.bits - self.prefixlen)) - 1))
00721
00722 def to_roa_tuple(self):
00723 """
00724 Convert a resource_range_ip to tuple format for ROA ASN.1
00725 encoding.
00726 """
00727 return (_long2bs(self.address, self.range_type.datum_type.bits, prefixlen = self.prefixlen),
00728 None if self.prefixlen == self.max_prefixlen else self.max_prefixlen)
00729
00730 class roa_prefix_ipv4(roa_prefix):
00731 """
00732 IPv4 ROA prefix.
00733 """
00734
00735
00736
00737
00738 range_type = resource_range_ipv4
00739
00740 class roa_prefix_ipv6(roa_prefix):
00741 """
00742 IPv6 ROA prefix.
00743 """
00744
00745
00746
00747
00748 range_type = resource_range_ipv6
00749
00750 class roa_prefix_set(list):
00751 """
00752 Set of ROA prefixes, analogous to the resource_set_ip class.
00753 """
00754
00755 def __init__(self, ini = None):
00756 """
00757 Initialize a ROA prefix set.
00758 """
00759 list.__init__(self)
00760 if isinstance(ini, str) and len(ini):
00761 self.extend(self.parse_str(s) for s in ini.split(","))
00762 elif isinstance(ini, (list, tuple)):
00763 self.extend(ini)
00764 else:
00765 assert ini is None or ini == "", "Unexpected initializer: %s" % str(ini)
00766 self.sort()
00767
00768
00769
00770
00771 if False and __debug__:
00772 for i in xrange(0, len(self) - 1):
00773 assert self[i].max() < self[i+1].min(), "Prefix overlap: %s %s" % (self[i], self[i+1])
00774
00775 def __str__(self):
00776 """Convert a ROA prefix set to string format."""
00777 return ",".join(str(x) for x in self)
00778
00779 def parse_str(self, x):
00780 """
00781 Parse ROA prefix from text (eg, an XML attribute).
00782 """
00783 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)-([0-9]+)$", x)
00784 if r:
00785 return self.prefix_type(self.prefix_type.range_type.datum_type(r.group(1)), int(r.group(2)), int(r.group(3)))
00786 r = re.match("^([0-9:.a-fA-F]+)/([0-9]+)$", x)
00787 if r:
00788 return self.prefix_type(self.prefix_type.range_type.datum_type(r.group(1)), int(r.group(2)))
00789 raise RuntimeError, 'Bad ROA prefix "%s"' % (x)
00790
00791 def to_resource_set(self):
00792 """
00793 Convert a ROA prefix set to a resource set. This is an
00794 irreversable transformation. We have to compute a union here
00795 because ROA prefix sets can include overlaps, while RFC 3779
00796 resource sets cannot. This is ugly, and there is almost certainly
00797 a more efficient way to do this, but start by getting the output
00798 right before worrying about making it fast or pretty.
00799 """
00800 r = self.resource_set_type()
00801 s = self.resource_set_type()
00802 s.append(None)
00803 for p in self:
00804 s[0] = p.to_resource_range()
00805 r = r.union(s)
00806 return r
00807
00808 @classmethod
00809 def from_sql(cls, sql, query, args = None):
00810 """
00811 Create ROA prefix set from an SQL query.
00812
00813 sql is an object that supports execute() and fetchall() methods
00814 like a DB API 2.0 cursor object.
00815
00816 query is an SQL query that returns a sequence of (address,
00817 prefixlen, max_prefixlen) triples.
00818 """
00819
00820 sql.execute(query, args)
00821 return cls([cls.prefix_type(cls.prefix_type.range_type.datum_type(x), int(y), int(z))
00822 for (x, y, z) in sql.fetchall()])
00823
00824 def to_roa_tuple(self):
00825 """
00826 Convert ROA prefix set into tuple format used by ROA ASN.1
00827 encoder. This is a variation on the format used in RFC 3779.
00828 """
00829 if self:
00830 return (self.resource_set_type.afi, tuple(a.to_roa_tuple() for a in self))
00831 else:
00832 return None
00833
00834 class roa_prefix_set_ipv4(roa_prefix_set):
00835 """
00836 Set of IPv4 ROA prefixes.
00837 """
00838
00839
00840
00841
00842 prefix_type = roa_prefix_ipv4
00843
00844
00845
00846
00847 resource_set_type = resource_set_ipv4
00848
00849 class roa_prefix_set_ipv6(roa_prefix_set):
00850 """
00851 Set of IPv6 ROA prefixes.
00852 """
00853
00854
00855
00856
00857 prefix_type = roa_prefix_ipv6
00858
00859
00860
00861
00862 resource_set_type = resource_set_ipv6
00863
00864
00865
00866 if __name__ == "__main__":
00867
00868 def test1(t, s1, s2):
00869 if isinstance(s1, str) and isinstance(s2, str):
00870 print "x: ", s1
00871 print "y: ", s2
00872 r1 = t(s1)
00873 r2 = t(s2)
00874 print "x: ", r1
00875 print "y: ", r2
00876 v1 = r1._comm(r2)
00877 v2 = r2._comm(r1)
00878 assert v1[0] == v2[1] and v1[1] == v2[0] and v1[2] == v2[2]
00879 for i in r1: assert r1.contains(i) and r1.contains(i.min) and r1.contains(i.max)
00880 for i in r2: assert r2.contains(i) and r2.contains(i.min) and r2.contains(i.max)
00881 for i in v1[0]: assert r1.contains(i) and not r2.contains(i)
00882 for i in v1[1]: assert not r1.contains(i) and r2.contains(i)
00883 for i in v1[2]: assert r1.contains(i) and r2.contains(i)
00884 v1 = r1.union(r2)
00885 v2 = r2.union(r1)
00886 assert v1 == v2
00887 print "x|y:", v1
00888 v1 = r1.difference(r2)
00889 v2 = r2.difference(r1)
00890 print "x-y:", v1
00891 print "y-x:", v2
00892 v1 = r1.symmetric_difference(r2)
00893 v2 = r2.symmetric_difference(r1)
00894 assert v1 == v2
00895 print "x^y:", v1
00896 v1 = r1.intersection(r2)
00897 v2 = r2.intersection(r1)
00898 assert v1 == v2
00899 print "x&y:", v1
00900
00901 def test2(t, s1, s2):
00902 print "x: ", s1
00903 print "y: ", s2
00904 r1 = t(s1)
00905 r2 = t(s2)
00906 print "x: ", r1
00907 print "y: ", r2
00908 print "x>y:", (r1 > r2)
00909 print "x<y:", (r1 < r2)
00910 test1(t.resource_set_type, r1.to_resource_set(), r2.to_resource_set())
00911
00912 print
00913 print "Testing set operations on resource sets"
00914 print
00915 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")
00916 print
00917 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32")
00918 print
00919 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.0.0.0/24")
00920 print
00921 test1(resource_set_ipv4, "10.0.0.0/24", "10.3.0.0/24,10.0.0.77/32")
00922 print
00923 print "Testing set operations on ROA prefixes"
00924 print
00925 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")
00926 print
00927 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")
00928 print
00929 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")
00930 print