// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// +build aix darwin dragonfly freebsd linux netbsd openbsd solaris

// Minimal RFC 6724 address selection.

package net

import 

func sortByRFC6724( []IPAddr) {
	if len() < 2 {
		return
	}
	sortByRFC6724withSrcs(, srcAddrs())
}

func sortByRFC6724withSrcs( []IPAddr,  []IP) {
	if len() != len() {
		panic("internal error")
	}
	 := make([]ipAttr, len())
	 := make([]ipAttr, len())
	for ,  := range  {
		[] = ipAttrOf(.IP)
		[] = ipAttrOf([])
	}
	sort.Stable(&byRFC6724{
		addrs:    ,
		addrAttr: ,
		srcs:     ,
		srcAttr:  ,
	})
}

// srcsAddrs tries to UDP-connect to each address to see if it has a
// route. (This doesn't send any packets). The destination port
// number is irrelevant.
func srcAddrs( []IPAddr) []IP {
	 := make([]IP, len())
	 := UDPAddr{Port: 9}
	for  := range  {
		.IP = [].IP
		.Zone = [].Zone
		,  := DialUDP("udp", nil, &)
		if  == nil {
			if ,  := .LocalAddr().(*UDPAddr);  {
				[] = .IP
			}
			.Close()
		}
	}
	return 
}

type ipAttr struct {
	Scope      scope
	Precedence uint8
	Label      uint8
}

func ipAttrOf( IP) ipAttr {
	if  == nil {
		return ipAttr{}
	}
	 := rfc6724policyTable.Classify()
	return ipAttr{
		Scope:      classifyScope(),
		Precedence: .Precedence,
		Label:      .Label,
	}
}

type byRFC6724 struct {
	addrs    []IPAddr // addrs to sort
	addrAttr []ipAttr
	srcs     []IP // or nil if unreachable
	srcAttr  []ipAttr
}

func ( *byRFC6724) () int { return len(.addrs) }

func ( *byRFC6724) (,  int) {
	.addrs[], .addrs[] = .addrs[], .addrs[]
	.srcs[], .srcs[] = .srcs[], .srcs[]
	.addrAttr[], .addrAttr[] = .addrAttr[], .addrAttr[]
	.srcAttr[], .srcAttr[] = .srcAttr[], .srcAttr[]
}

// Less reports whether i is a better destination address for this
// host than j.
//
// The algorithm and variable names comes from RFC 6724 section 6.
func ( *byRFC6724) (,  int) bool {
	 := .addrs[].IP
	 := .addrs[].IP
	 := .srcs[]
	 := .srcs[]
	 := &.addrAttr[]
	 := &.addrAttr[]
	 := &.srcAttr[]
	 := &.srcAttr[]

	const  = true
	const  = false

	// Rule 1: Avoid unusable destinations.
	// If DB is known to be unreachable or if Source(DB) is undefined, then
	// prefer DA.  Similarly, if DA is known to be unreachable or if
	// Source(DA) is undefined, then prefer DB.
	if  == nil &&  == nil {
		return false // "equal"
	}
	if  == nil {
		return 
	}
	if  == nil {
		return 
	}

	// Rule 2: Prefer matching scope.
	// If Scope(DA) = Scope(Source(DA)) and Scope(DB) <> Scope(Source(DB)),
	// then prefer DA.  Similarly, if Scope(DA) <> Scope(Source(DA)) and
	// Scope(DB) = Scope(Source(DB)), then prefer DB.
	if .Scope == .Scope && .Scope != .Scope {
		return 
	}
	if .Scope != .Scope && .Scope == .Scope {
		return 
	}

	// Rule 3: Avoid deprecated addresses.
	// If Source(DA) is deprecated and Source(DB) is not, then prefer DB.
	// Similarly, if Source(DA) is not deprecated and Source(DB) is
	// deprecated, then prefer DA.

	// TODO(bradfitz): implement? low priority for now.

	// Rule 4: Prefer home addresses.
	// If Source(DA) is simultaneously a home address and care-of address
	// and Source(DB) is not, then prefer DA.  Similarly, if Source(DB) is
	// simultaneously a home address and care-of address and Source(DA) is
	// not, then prefer DB.

	// TODO(bradfitz): implement? low priority for now.

	// Rule 5: Prefer matching label.
	// If Label(Source(DA)) = Label(DA) and Label(Source(DB)) <> Label(DB),
	// then prefer DA.  Similarly, if Label(Source(DA)) <> Label(DA) and
	// Label(Source(DB)) = Label(DB), then prefer DB.
	if .Label == .Label &&
		.Label != .Label {
		return 
	}
	if .Label != .Label &&
		.Label == .Label {
		return 
	}

	// Rule 6: Prefer higher precedence.
	// If Precedence(DA) > Precedence(DB), then prefer DA.  Similarly, if
	// Precedence(DA) < Precedence(DB), then prefer DB.
	if .Precedence > .Precedence {
		return 
	}
	if .Precedence < .Precedence {
		return 
	}

	// Rule 7: Prefer native transport.
	// If DA is reached via an encapsulating transition mechanism (e.g.,
	// IPv6 in IPv4) and DB is not, then prefer DB.  Similarly, if DB is
	// reached via encapsulation and DA is not, then prefer DA.

	// TODO(bradfitz): implement? low priority for now.

	// Rule 8: Prefer smaller scope.
	// If Scope(DA) < Scope(DB), then prefer DA.  Similarly, if Scope(DA) >
	// Scope(DB), then prefer DB.
	if .Scope < .Scope {
		return 
	}
	if .Scope > .Scope {
		return 
	}

	// Rule 9: Use longest matching prefix.
	// When DA and DB belong to the same address family (both are IPv6 or
	// both are IPv4 [but see below]): If CommonPrefixLen(Source(DA), DA) >
	// CommonPrefixLen(Source(DB), DB), then prefer DA.  Similarly, if
	// CommonPrefixLen(Source(DA), DA) < CommonPrefixLen(Source(DB), DB),
	// then prefer DB.
	//
	// However, applying this rule to IPv4 addresses causes
	// problems (see issues 13283 and 18518), so limit to IPv6.
	if .To4() == nil && .To4() == nil {
		 := commonPrefixLen(, )
		 := commonPrefixLen(, )

		if  >  {
			return 
		}
		if  <  {
			return 
		}
	}

	// Rule 10: Otherwise, leave the order unchanged.
	// If DA preceded DB in the original list, prefer DA.
	// Otherwise, prefer DB.
	return false // "equal"
}

type policyTableEntry struct {
	Prefix     *IPNet
	Precedence uint8
	Label      uint8
}

type policyTable []policyTableEntry

// RFC 6724 section 2.1.
var rfc6724policyTable = policyTable{
	{
		Prefix:     mustCIDR("::1/128"),
		Precedence: 50,
		Label:      0,
	},
	{
		Prefix:     mustCIDR("::/0"),
		Precedence: 40,
		Label:      1,
	},
	{
		// IPv4-compatible, etc.
		Prefix:     mustCIDR("::ffff:0:0/96"),
		Precedence: 35,
		Label:      4,
	},
	{
		// 6to4
		Prefix:     mustCIDR("2002::/16"),
		Precedence: 30,
		Label:      2,
	},
	{
		// Teredo
		Prefix:     mustCIDR("2001::/32"),
		Precedence: 5,
		Label:      5,
	},
	{
		Prefix:     mustCIDR("fc00::/7"),
		Precedence: 3,
		Label:      13,
	},
	{
		Prefix:     mustCIDR("::/96"),
		Precedence: 1,
		Label:      3,
	},
	{
		Prefix:     mustCIDR("fec0::/10"),
		Precedence: 1,
		Label:      11,
	},
	{
		Prefix:     mustCIDR("3ffe::/16"),
		Precedence: 1,
		Label:      12,
	},
}

func init() {
	sort.Sort(sort.Reverse(byMaskLength(rfc6724policyTable)))
}

// byMaskLength sorts policyTableEntry by the size of their Prefix.Mask.Size,
// from smallest mask, to largest.
type byMaskLength []policyTableEntry

func ( byMaskLength) () int      { return len() }
func ( byMaskLength) (,  int) { [], [] = [], [] }
func ( byMaskLength) (,  int) bool {
	,  := [].Prefix.Mask.Size()
	,  := [].Prefix.Mask.Size()
	return  < 
}

// mustCIDR calls ParseCIDR and panics on any error, or if the network
// is not IPv6.
func mustCIDR( string) *IPNet {
	, ,  := ParseCIDR()
	if  != nil {
		panic(.Error())
	}
	if len() != IPv6len {
		panic("unexpected IP length")
	}
	return 
}

// Classify returns the policyTableEntry of the entry with the longest
// matching prefix that contains ip.
// The table t must be sorted from largest mask size to smallest.
func ( policyTable) ( IP) policyTableEntry {
	for ,  := range  {
		if .Prefix.Contains() {
			return 
		}
	}
	return policyTableEntry{}
}

// RFC 6724 section 3.1.
type scope uint8

const (
	scopeInterfaceLocal scope = 0x1
	scopeLinkLocal      scope = 0x2
	scopeAdminLocal     scope = 0x4
	scopeSiteLocal      scope = 0x5
	scopeOrgLocal       scope = 0x8
	scopeGlobal         scope = 0xe
)

func classifyScope( IP) scope {
	if .IsLoopback() || .IsLinkLocalUnicast() {
		return scopeLinkLocal
	}
	 := len() == IPv6len && .To4() == nil
	if  && .IsMulticast() {
		return scope([1] & 0xf)
	}
	// Site-local addresses are defined in RFC 3513 section 2.5.6
	// (and deprecated in RFC 3879).
	if  && [0] == 0xfe && [1]&0xc0 == 0xc0 {
		return scopeSiteLocal
	}
	return scopeGlobal
}

// commonPrefixLen reports the length of the longest prefix (looking
// at the most significant, or leftmost, bits) that the
// two addresses have in common, up to the length of a's prefix (i.e.,
// the portion of the address not including the interface ID).
//
// If a or b is an IPv4 address as an IPv6 address, the IPv4 addresses
// are compared (with max common prefix length of 32).
// If a and b are different IP versions, 0 is returned.
//
// See https://tools.ietf.org/html/rfc6724#section-2.2
func commonPrefixLen(,  IP) ( int) {
	if  := .To4();  != nil {
		 = 
	}
	if  := .To4();  != nil {
		 = 
	}
	if len() != len() {
		return 0
	}
	// If IPv6, only up to the prefix (first 64 bits)
	if len() > 8 {
		 = [:8]
		 = [:8]
	}
	for len() > 0 {
		if [0] == [0] {
			 += 8
			 = [1:]
			 = [1:]
			continue
		}
		 := 8
		,  := [0], [0]
		for {
			 >>= 1
			 >>= 1
			--
			if  ==  {
				 += 
				return
			}
		}
	}
	return
}