netipx.go

Documentation: go4.org/netipx

     1  // Copyright 2020 The Inet.Af AUTHORS. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package netipx contains code and types that were left behind when
     6  // the old inet.af/netaddr package moved to the standard library in Go
     7  // 1.18 as net/netip.
     8  package netipx // import "go4.org/netipx"
     9  
    10  import (
    11  	"errors"
    12  	"fmt"
    13  	"math"
    14  	"net"
    15  	"net/netip"
    16  	"sort"
    17  	"strings"
    18  )
    19  
    20  // FromStdIP returns an IP from the standard library's IP type.
    21  //
    22  // If std is invalid, ok is false.
    23  //
    24  // FromStdIP implicitly unmaps IPv6-mapped IPv4 addresses. That is, if
    25  // len(std) == 16 and contains an IPv4 address, only the IPv4 part is
    26  // returned, without the IPv6 wrapper. This is the common form returned by
    27  // the standard library's ParseIP: https://play.golang.org/p/qdjylUkKWxl.
    28  // To convert a standard library IP without the implicit unmapping, use
    29  // netip.AddrFromSlice.
    30  func FromStdIP(std net.IP) (ip netip.Addr, ok bool) {
    31  	ret, ok := netip.AddrFromSlice(std)
    32  	return ret.Unmap(), ok
    33  }
    34  
    35  // MustFromStdIP is like FromStdIP, but it panics if std is invalid.
    36  func MustFromStdIP(std net.IP) netip.Addr {
    37  	ret, ok := netip.AddrFromSlice(std)
    38  	if !ok {
    39  		panic("not a valid IP address")
    40  	}
    41  	return ret.Unmap()
    42  }
    43  
    44  // FromStdIPRaw returns an IP from the standard library's IP type.
    45  // If std is invalid, ok is false.
    46  // Unlike FromStdIP, FromStdIPRaw does not do an implicit Unmap if
    47  // len(std) == 16 and contains an IPv6-mapped IPv4 address.
    48  //
    49  // Deprecated: use netip.AddrFromSlice instead.
    50  func FromStdIPRaw(std net.IP) (ip netip.Addr, ok bool) {
    51  	return netip.AddrFromSlice(std)
    52  }
    53  
    54  // AddrNext returns the IP following ip.
    55  // If there is none, it returns the IP zero value.
    56  //
    57  // Deprecated: use netip.Addr.Next instead.
    58  func AddrNext(ip netip.Addr) netip.Addr {
    59  	addr := u128From16(ip.As16()).addOne()
    60  	if ip.Is4() {
    61  		if uint32(addr.lo) == 0 {
    62  			// Overflowed.
    63  			return netip.Addr{}
    64  		}
    65  		return addr.IP4()
    66  	} else {
    67  		if addr.isZero() {
    68  			// Overflowed
    69  			return netip.Addr{}
    70  		}
    71  		return addr.IP6().WithZone(ip.Zone())
    72  	}
    73  }
    74  
    75  // AddrPrior returns the IP before ip.
    76  // If there is none, it returns the IP zero value.
    77  //
    78  // Deprecated: use netip.Addr.Prev instead.
    79  func AddrPrior(ip netip.Addr) netip.Addr {
    80  	addr := u128From16(ip.As16())
    81  	if ip.Is4() {
    82  		if uint32(addr.lo) == 0 {
    83  			return netip.Addr{}
    84  		}
    85  		return addr.subOne().IP4()
    86  	} else {
    87  		if addr.isZero() {
    88  			return netip.Addr{}
    89  		}
    90  		return addr.subOne().IP6().WithZone(ip.Zone())
    91  	}
    92  }
    93  
    94  // FromStdAddr maps the components of a standard library TCPAddr or
    95  // UDPAddr into an IPPort.
    96  func FromStdAddr(stdIP net.IP, port int, zone string) (_ netip.AddrPort, ok bool) {
    97  	ip, ok := FromStdIP(stdIP)
    98  	if !ok || port < 0 || port > math.MaxUint16 {
    99  		return netip.AddrPort{}, false
   100  	}
   101  	ip = ip.Unmap()
   102  	if zone != "" {
   103  		if ip.Is4() {
   104  			ok = false
   105  			return
   106  		}
   107  		ip = ip.WithZone(zone)
   108  	}
   109  	return netip.AddrPortFrom(ip, uint16(port)), true
   110  }
   111  
   112  // FromStdIPNet returns an netip.Prefix from the standard library's IPNet type.
   113  // If std is invalid, ok is false.
   114  func FromStdIPNet(std *net.IPNet) (prefix netip.Prefix, ok bool) {
   115  	ip, ok := FromStdIP(std.IP)
   116  	if !ok {
   117  		return netip.Prefix{}, false
   118  	}
   119  
   120  	if l := len(std.Mask); l != net.IPv4len && l != net.IPv6len {
   121  		// Invalid mask.
   122  		return netip.Prefix{}, false
   123  	}
   124  
   125  	ones, bits := std.Mask.Size()
   126  	if ones == 0 && bits == 0 {
   127  		// IPPrefix does not support non-contiguous masks.
   128  		return netip.Prefix{}, false
   129  	}
   130  
   131  	return netip.PrefixFrom(ip, ones), true
   132  }
   133  
   134  // RangeOfPrefix returns the inclusive range of IPs that p covers.
   135  //
   136  // If p is zero or otherwise invalid, Range returns the zero value.
   137  func RangeOfPrefix(p netip.Prefix) IPRange {
   138  	p = p.Masked()
   139  	if !p.IsValid() {
   140  		return IPRange{}
   141  	}
   142  	return IPRangeFrom(p.Addr(), PrefixLastIP(p))
   143  }
   144  
   145  // PrefixIPNet returns the net.IPNet representation of an netip.Prefix.
   146  // The returned value is always non-nil.
   147  // Any zone identifier is dropped in the conversion.
   148  func PrefixIPNet(p netip.Prefix) *net.IPNet {
   149  	if !p.IsValid() {
   150  		return &net.IPNet{}
   151  	}
   152  	return &net.IPNet{
   153  		IP:   p.Addr().AsSlice(),
   154  		Mask: net.CIDRMask(p.Bits(), p.Addr().BitLen()),
   155  	}
   156  }
   157  
   158  // AddrIPNet returns the net.IPNet representation of an netip.Addr
   159  // with a mask corresponding to the addresses's bit length.
   160  // The returned value is always non-nil.
   161  // Any zone identifier is dropped in the conversion.
   162  func AddrIPNet(addr netip.Addr) *net.IPNet {
   163  	if !addr.IsValid() {
   164  		return &net.IPNet{}
   165  	}
   166  	return &net.IPNet{
   167  		IP:   addr.AsSlice(),
   168  		Mask: net.CIDRMask(addr.BitLen(), addr.BitLen()),
   169  	}
   170  }
   171  
   172  // PrefixLastIP returns the last IP in the prefix.
   173  func PrefixLastIP(p netip.Prefix) netip.Addr {
   174  	if !p.IsValid() {
   175  		return netip.Addr{}
   176  	}
   177  	a16 := p.Addr().As16()
   178  	var off uint8
   179  	var bits uint8 = 128
   180  	if p.Addr().Is4() {
   181  		off = 12
   182  		bits = 32
   183  	}
   184  	for b := uint8(p.Bits()); b < bits; b++ {
   185  		byteNum, bitInByte := b/8, 7-(b%8)
   186  		a16[off+byteNum] |= 1 << uint(bitInByte)
   187  	}
   188  	if p.Addr().Is4() {
   189  		return netip.AddrFrom16(a16).Unmap()
   190  	} else {
   191  		return netip.AddrFrom16(a16) // doesn't unmap
   192  	}
   193  }
   194  
   195  // IPRange represents an inclusive range of IP addresses
   196  // from the same address family.
   197  //
   198  // The From and To IPs are inclusive bounds, with both included in the
   199  // range.
   200  //
   201  // To be valid, the From and To values must be non-zero, have matching
   202  // address families (IPv4 vs IPv6), and From must be less than or equal to To.
   203  // IPv6 zones are stripped out and ignored.
   204  // An invalid range may be ignored.
   205  type IPRange struct {
   206  	// from is the initial IP address in the range.
   207  	from netip.Addr
   208  
   209  	// to is the final IP address in the range.
   210  	to netip.Addr
   211  }
   212  
   213  // IPRangeFrom returns an IPRange from from to to.
   214  // It does not allocate.
   215  func IPRangeFrom(from, to netip.Addr) IPRange {
   216  	return IPRange{
   217  		from: from.WithZone(""),
   218  		to:   to.WithZone(""),
   219  	}
   220  }
   221  
   222  // From returns the lower bound of r.
   223  func (r IPRange) From() netip.Addr { return r.from }
   224  
   225  // To returns the upper bound of r.
   226  func (r IPRange) To() netip.Addr { return r.to }
   227  
   228  // ParseIPRange parses a range out of two IPs separated by a hyphen.
   229  //
   230  // It returns an error if the range is not valid.
   231  func ParseIPRange(s string) (IPRange, error) {
   232  	var r IPRange
   233  	h := strings.IndexByte(s, '-')
   234  	if h == -1 {
   235  		return r, fmt.Errorf("no hyphen in range %q", s)
   236  	}
   237  	from, to := s[:h], s[h+1:]
   238  	var err error
   239  	r.from, err = netip.ParseAddr(from)
   240  	if err != nil {
   241  		return r, fmt.Errorf("invalid From IP %q in range %q", from, s)
   242  	}
   243  	r.from = r.from.WithZone("")
   244  	r.to, err = netip.ParseAddr(to)
   245  	if err != nil {
   246  		return r, fmt.Errorf("invalid To IP %q in range %q", to, s)
   247  	}
   248  	r.to = r.to.WithZone("")
   249  	if !r.IsValid() {
   250  		return r, fmt.Errorf("range %v to %v not valid", r.from, r.to)
   251  	}
   252  	return r, nil
   253  }
   254  
   255  // MustParseIPRange calls ParseIPRange(s) and panics on error.
   256  // It is intended for use in tests with hard-coded strings.
   257  func MustParseIPRange(s string) IPRange {
   258  	r, err := ParseIPRange(s)
   259  	if err != nil {
   260  		panic(err)
   261  	}
   262  	return r
   263  }
   264  
   265  // String returns a string representation of the range.
   266  //
   267  // For a valid range, the form is "From-To" with a single hyphen
   268  // separating the IPs, the same format recognized by
   269  // ParseIPRange.
   270  func (r IPRange) String() string {
   271  	if r.IsValid() {
   272  		return fmt.Sprintf("%s-%s", r.from, r.to)
   273  	}
   274  	if !r.from.IsValid() || !r.to.IsValid() {
   275  		return "zero IPRange"
   276  	}
   277  	return "invalid IPRange"
   278  }
   279  
   280  // AppendTo appends a text encoding of r,
   281  // as generated by MarshalText,
   282  // to b and returns the extended buffer.
   283  func (r IPRange) AppendTo(b []byte) []byte {
   284  	if r.IsZero() {
   285  		return b
   286  	}
   287  	b = r.from.AppendTo(b)
   288  	b = append(b, '-')
   289  	b = r.to.AppendTo(b)
   290  	return b
   291  }
   292  
   293  // MarshalText implements the encoding.TextMarshaler interface,
   294  // The encoding is the same as returned by String, with one exception:
   295  // If ip is the zero value, the encoding is the empty string.
   296  func (r IPRange) MarshalText() ([]byte, error) {
   297  	if r.IsZero() {
   298  		return []byte(""), nil
   299  	}
   300  	var max int
   301  	if r.from.Is4() {
   302  		max = len("255.255.255.255-255.255.255.255")
   303  	} else {
   304  		max = len("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff")
   305  	}
   306  	b := make([]byte, 0, max)
   307  	return r.AppendTo(b), nil
   308  }
   309  
   310  // UnmarshalText implements the encoding.TextUnmarshaler interface.
   311  // The IP range is expected in a form accepted by ParseIPRange.
   312  // It returns an error if *r is not the IPRange zero value.
   313  func (r *IPRange) UnmarshalText(text []byte) error {
   314  	if *r != (IPRange{}) {
   315  		return errors.New("refusing to Unmarshal into non-zero IPRange")
   316  	}
   317  	if len(text) == 0 {
   318  		return nil
   319  	}
   320  	var err error
   321  	*r, err = ParseIPRange(string(text))
   322  	return err
   323  }
   324  
   325  // IsZero reports whether r is the zero value of the IPRange type.
   326  func (r IPRange) IsZero() bool {
   327  	return r == IPRange{}
   328  }
   329  
   330  // IsValid reports whether r.From() and r.To() are both non-zero and
   331  // obey the documented requirements: address families match, and From
   332  // is less than or equal to To.
   333  func (r IPRange) IsValid() bool {
   334  	return r.from.IsValid() &&
   335  		r.from.BitLen() == r.to.BitLen() &&
   336  		r.from.Zone() == r.to.Zone() &&
   337  		!r.to.Less(r.from)
   338  }
   339  
   340  // Valid reports whether r.From() and r.To() are both non-zero and
   341  // obey the documented requirements: address families match, and From
   342  // is less than or equal to To.
   343  //
   344  // Deprecated: use the correctly named and identical IsValid method instead.
   345  func (r IPRange) Valid() bool { return r.IsValid() }
   346  
   347  // Contains reports whether the range r includes addr.
   348  //
   349  // An invalid range always reports false.
   350  //
   351  // If ip has an IPv6 zone, Contains returns false,
   352  // because IPPrefixes strip zones.
   353  func (r IPRange) Contains(addr netip.Addr) bool {
   354  	return r.IsValid() && addr.Zone() == "" && r.contains(addr)
   355  }
   356  
   357  // contains is like Contains, but without the validity check.
   358  // addr must not have a zone.
   359  func (r IPRange) contains(addr netip.Addr) bool {
   360  	return r.from.Compare(addr) <= 0 && r.to.Compare(addr) >= 0
   361  }
   362  
   363  // less reports whether r is "before" other. It is before if r.From()
   364  // is before other.From(). If they're equal, then the larger range
   365  // (higher To()) comes first.
   366  func (r IPRange) less(other IPRange) bool {
   367  	if cmp := r.from.Compare(other.from); cmp != 0 {
   368  		return cmp < 0
   369  	}
   370  	return other.to.Less(r.to)
   371  }
   372  
   373  // entirelyBefore returns whether r lies entirely before other in IP
   374  // space.
   375  func (r IPRange) entirelyBefore(other IPRange) bool {
   376  	return r.to.Less(other.from)
   377  }
   378  
   379  func lessOrEq(ip, ip2 netip.Addr) bool { return ip.Compare(ip2) <= 0 }
   380  
   381  // entirelyWithin returns whether r is entirely contained within
   382  // other.
   383  func (r IPRange) coveredBy(other IPRange) bool {
   384  	return lessOrEq(other.from, r.from) && lessOrEq(r.to, other.to)
   385  }
   386  
   387  // inMiddleOf returns whether r is inside other, but not touching the
   388  // edges of other.
   389  func (r IPRange) inMiddleOf(other IPRange) bool {
   390  	return other.from.Less(r.from) && r.to.Less(other.to)
   391  }
   392  
   393  // overlapsStartOf returns whether r entirely overlaps the start of
   394  // other, but not all of other.
   395  func (r IPRange) overlapsStartOf(other IPRange) bool {
   396  	return lessOrEq(r.from, other.from) && r.to.Less(other.to)
   397  }
   398  
   399  // overlapsEndOf returns whether r entirely overlaps the end of
   400  // other, but not all of other.
   401  func (r IPRange) overlapsEndOf(other IPRange) bool {
   402  	return other.from.Less(r.from) && lessOrEq(other.to, r.to)
   403  }
   404  
   405  // mergeIPRanges returns the minimum and sorted set of IP ranges that
   406  // cover r.
   407  func mergeIPRanges(rr []IPRange) (out []IPRange, valid bool) {
   408  	// Always return a copy of r, to avoid aliasing slice memory in
   409  	// the caller.
   410  	switch len(rr) {
   411  	case 0:
   412  		return nil, true
   413  	case 1:
   414  		return []IPRange{rr[0]}, true
   415  	}
   416  
   417  	sort.Slice(rr, func(i, j int) bool { return rr[i].less(rr[j]) })
   418  	out = make([]IPRange, 1, len(rr))
   419  	out[0] = rr[0]
   420  	for _, r := range rr[1:] {
   421  		prev := &out[len(out)-1]
   422  		switch {
   423  		case !r.IsValid():
   424  			// Invalid ranges make no sense to merge, refuse to
   425  			// perform.
   426  			return nil, false
   427  		case prev.to.Next() == r.from:
   428  			// prev and r touch, merge them.
   429  			//
   430  			//   prev     r
   431  			// f------tf-----t
   432  			prev.to = r.to
   433  		case prev.to.Less(r.from):
   434  			// No overlap and not adjacent (per previous case), no
   435  			// merging possible.
   436  			//
   437  			//   prev       r
   438  			// f------t  f-----t
   439  			out = append(out, r)
   440  		case prev.to.Less(r.to):
   441  			// Partial overlap, update prev
   442  			//
   443  			//   prev
   444  			// f------t
   445  			//     f-----t
   446  			//        r
   447  			prev.to = r.to
   448  		default:
   449  			// r entirely contained in prev, nothing to do.
   450  			//
   451  			//    prev
   452  			// f--------t
   453  			//  f-----t
   454  			//     r
   455  		}
   456  	}
   457  	return out, true
   458  }
   459  
   460  // Overlaps reports whether p and o overlap at all.
   461  //
   462  // If p and o are of different address families or either are invalid,
   463  // it reports false.
   464  func (r IPRange) Overlaps(o IPRange) bool {
   465  	return r.IsValid() &&
   466  		o.IsValid() &&
   467  		r.from.Compare(o.to) <= 0 &&
   468  		o.from.Compare(r.to) <= 0
   469  }
   470  
   471  // prefixMaker returns a address-family-corrected IPPrefix from a and bits,
   472  // where the input bits is always in the IPv6-mapped form for IPv4 addresses.
   473  type prefixMaker func(a uint128, bits uint8) netip.Prefix
   474  
   475  // Prefixes returns the set of IPPrefix entries that covers r.
   476  //
   477  // If either of r's bounds are invalid, in the wrong order, or if
   478  // they're of different address families, then Prefixes returns nil.
   479  //
   480  // Prefixes necessarily allocates. See AppendPrefixes for a version that uses
   481  // memory you provide.
   482  func (r IPRange) Prefixes() []netip.Prefix {
   483  	return r.AppendPrefixes(nil)
   484  }
   485  
   486  // AppendPrefixes is an append version of IPRange.Prefixes. It appends
   487  // the netip.Prefix entries that cover r to dst.
   488  func (r IPRange) AppendPrefixes(dst []netip.Prefix) []netip.Prefix {
   489  	if !r.IsValid() {
   490  		return nil
   491  	}
   492  	return appendRangePrefixes(dst, r.prefixFrom128AndBits, u128From16(r.from.As16()), u128From16(r.to.As16()))
   493  }
   494  
   495  func (r IPRange) prefixFrom128AndBits(a uint128, bits uint8) netip.Prefix {
   496  	var ip netip.Addr
   497  	if r.from.Is4() {
   498  		bits -= 12 * 8
   499  		ip = a.IP4()
   500  	} else {
   501  		ip = a.IP6()
   502  	}
   503  	return netip.PrefixFrom(ip, int(bits))
   504  }
   505  
   506  // aZeroBSet is whether, after the common bits, a is all zero bits and
   507  // b is all set (one) bits.
   508  func comparePrefixes(a, b uint128) (common uint8, aZeroBSet bool) {
   509  	common = a.commonPrefixLen(b)
   510  
   511  	// See whether a and b, after their common shared bits, end
   512  	// in all zero bits or all one bits, respectively.
   513  	if common == 128 {
   514  		return common, true
   515  	}
   516  
   517  	m := mask6[common]
   518  	return common, (a.xor(a.and(m)).isZero() &&
   519  		b.or(m) == uint128{^uint64(0), ^uint64(0)})
   520  }
   521  
   522  // Prefix returns r as an IPPrefix, if it can be presented exactly as such.
   523  // If r is not valid or is not exactly equal to one prefix, ok is false.
   524  func (r IPRange) Prefix() (p netip.Prefix, ok bool) {
   525  	if !r.IsValid() {
   526  		return
   527  	}
   528  	from128 := u128From16(r.from.As16())
   529  	to128 := u128From16(r.to.As16())
   530  	if common, ok := comparePrefixes(from128, to128); ok {
   531  		return r.prefixFrom128AndBits(from128, common), true
   532  	}
   533  	return
   534  }
   535  
   536  func appendRangePrefixes(dst []netip.Prefix, makePrefix prefixMaker, a, b uint128) []netip.Prefix {
   537  	common, ok := comparePrefixes(a, b)
   538  	if ok {
   539  		// a to b represents a whole range, like 10.50.0.0/16.
   540  		// (a being 10.50.0.0 and b being 10.50.255.255)
   541  		return append(dst, makePrefix(a, common))
   542  	}
   543  	// Otherwise recursively do both halves.
   544  	dst = appendRangePrefixes(dst, makePrefix, a, a.bitsSetFrom(common+1))
   545  	dst = appendRangePrefixes(dst, makePrefix, b.bitsClearedFrom(common+1), b)
   546  	return dst
   547  }
   548
View as plain text