\section{Client Lists}

\begin{code}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE StrictData     #-}
module Network.Tox.DHT.ClientList where

import           Control.Monad                 (join)
import           Data.List                     (sort)
import           Data.Map                      (Map)
import qualified Data.Map                      as Map
import           Test.QuickCheck.Arbitrary     (Arbitrary, arbitrary,
                                                arbitrarySizedNatural)
import qualified Test.QuickCheck.Gen           as Gen
import           Test.QuickCheck.Gen           (Gen)

import           Network.Tox.Crypto.Key        (PublicKey)
import           Network.Tox.DHT.ClientNode    (ClientNode)
import qualified Network.Tox.DHT.ClientNode    as ClientNode
import           Network.Tox.DHT.Distance      (Distance)
import qualified Network.Tox.DHT.Distance      as Distance
import           Network.Tox.NodeInfo.NodeInfo (NodeInfo)
import qualified Network.Tox.NodeInfo.NodeInfo as NodeInfo
import           Network.Tox.Time              (Timestamp)


{-------------------------------------------------------------------------------
 -
 - :: Implementation.
 -
 ------------------------------------------------------------------------------}

\end{code}

A Client List of \textit{maximum size} \texttt{k} with a given public key as
\textit{base key} is an ordered set of at most \texttt{k} nodes close to the
base key.  The elements are sorted by \href{#distance}{distance} from the base
key.  Thus, the first (smallest) element of the set is the closest one to the
base key in that set, the last (greatest) element is the furthest away.  The
maximum size and base key are constant throughout the lifetime of a Client
List.


\begin{code}

data ClientList = ClientList
  { ClientList -> PublicKey
baseKey :: PublicKey
  , ClientList -> Int
maxSize :: Int
  , ClientList -> ClientNodes
nodes   :: ClientNodes
  }
  deriving (ClientList -> ClientList -> Bool
(ClientList -> ClientList -> Bool)
-> (ClientList -> ClientList -> Bool) -> Eq ClientList
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ClientList -> ClientList -> Bool
$c/= :: ClientList -> ClientList -> Bool
== :: ClientList -> ClientList -> Bool
$c== :: ClientList -> ClientList -> Bool
Eq, ReadPrec [ClientList]
ReadPrec ClientList
Int -> ReadS ClientList
ReadS [ClientList]
(Int -> ReadS ClientList)
-> ReadS [ClientList]
-> ReadPrec ClientList
-> ReadPrec [ClientList]
-> Read ClientList
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [ClientList]
$creadListPrec :: ReadPrec [ClientList]
readPrec :: ReadPrec ClientList
$creadPrec :: ReadPrec ClientList
readList :: ReadS [ClientList]
$creadList :: ReadS [ClientList]
readsPrec :: Int -> ReadS ClientList
$creadsPrec :: Int -> ReadS ClientList
Read, Int -> ClientList -> ShowS
[ClientList] -> ShowS
ClientList -> String
(Int -> ClientList -> ShowS)
-> (ClientList -> String)
-> ([ClientList] -> ShowS)
-> Show ClientList
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ClientList] -> ShowS
$cshowList :: [ClientList] -> ShowS
show :: ClientList -> String
$cshow :: ClientList -> String
showsPrec :: Int -> ClientList -> ShowS
$cshowsPrec :: Int -> ClientList -> ShowS
Show)

type ClientNodes = Map Distance ClientNode

nodeInfos :: ClientList -> [NodeInfo]
nodeInfos :: ClientList -> [NodeInfo]
nodeInfos = (ClientNode -> NodeInfo) -> [ClientNode] -> [NodeInfo]
forall a b. (a -> b) -> [a] -> [b]
map ClientNode -> NodeInfo
ClientNode.nodeInfo ([ClientNode] -> [NodeInfo])
-> (ClientList -> [ClientNode]) -> ClientList -> [NodeInfo]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ClientNodes -> [ClientNode]
forall k a. Map k a -> [a]
Map.elems (ClientNodes -> [ClientNode])
-> (ClientList -> ClientNodes) -> ClientList -> [ClientNode]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ClientList -> ClientNodes
nodes

empty :: PublicKey -> Int -> ClientList
empty :: PublicKey -> Int -> ClientList
empty PublicKey
publicKey Int
size = ClientList :: PublicKey -> Int -> ClientNodes -> ClientList
ClientList
  { baseKey :: PublicKey
baseKey = PublicKey
publicKey
  , maxSize :: Int
maxSize = Int
size
  , nodes :: ClientNodes
nodes   = ClientNodes
forall k a. Map k a
Map.empty
  }

isEmpty :: ClientList -> Bool
isEmpty :: ClientList -> Bool
isEmpty = ClientNodes -> Bool
forall k a. Map k a -> Bool
Map.null (ClientNodes -> Bool)
-> (ClientList -> ClientNodes) -> ClientList -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ClientList -> ClientNodes
nodes

updateClientNodes :: (ClientNodes -> ClientNodes) -> ClientList -> ClientList
updateClientNodes :: (ClientNodes -> ClientNodes) -> ClientList -> ClientList
updateClientNodes ClientNodes -> ClientNodes
f clientList :: ClientList
clientList@ClientList{ ClientNodes
nodes :: ClientNodes
nodes :: ClientList -> ClientNodes
nodes } =
  ClientList
clientList{nodes :: ClientNodes
nodes = ClientNodes -> ClientNodes
f ClientNodes
nodes}

lookup :: PublicKey -> ClientList -> Maybe NodeInfo
lookup :: PublicKey -> ClientList -> Maybe NodeInfo
lookup PublicKey
publicKey _cl :: ClientList
_cl@ClientList{ PublicKey
baseKey :: PublicKey
baseKey :: ClientList -> PublicKey
baseKey, ClientNodes
nodes :: ClientNodes
nodes :: ClientList -> ClientNodes
nodes } =
  ClientNode -> NodeInfo
ClientNode.nodeInfo (ClientNode -> NodeInfo) -> Maybe ClientNode -> Maybe NodeInfo
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PublicKey -> PublicKey -> Distance
Distance.xorDistance PublicKey
publicKey PublicKey
baseKey Distance -> ClientNodes -> Maybe ClientNode
forall k a. Ord k => k -> Map k a -> Maybe a
`Map.lookup` ClientNodes
nodes

\end{code}


A Client List is \textit{full} when the number of nodes it contains is the
maximum size of the list.

A node is \textit{viable} for entry if the Client List is not \textit{full} or the
node's public key has a lower distance from the base key than the current entry
with the greatest distance.

If a node is \textit{viable} and the Client List is \textit{full}, the entry
with the greatest distance from the base key is removed to keep the size below
the maximum configured size.

Adding a node whose key already exists will result in an update of the Node
Info in the Client List.  Removing a node for which no Node Info exists in the
Client List has no effect.  Thus, removing a node twice is permitted and has the
same effect as removing it once.

\begin{code}

full :: ClientList -> Bool
full :: ClientList -> Bool
full ClientList{ ClientNodes
nodes :: ClientNodes
nodes :: ClientList -> ClientNodes
nodes, Int
maxSize :: Int
maxSize :: ClientList -> Int
maxSize } =
  ClientNodes -> Int
forall k a. Map k a -> Int
Map.size ClientNodes
nodes Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
maxSize

addNode :: Timestamp -> NodeInfo -> ClientList -> ClientList
addNode :: Timestamp -> NodeInfo -> ClientList -> ClientList
addNode Timestamp
time NodeInfo
nodeInfo clientList :: ClientList
clientList@ClientList{ PublicKey
baseKey :: PublicKey
baseKey :: ClientList -> PublicKey
baseKey, Int
maxSize :: Int
maxSize :: ClientList -> Int
maxSize } =
  ((ClientNodes -> ClientNodes) -> ClientList -> ClientList
`updateClientNodes` ClientList
clientList) ((ClientNodes -> ClientNodes) -> ClientList)
-> (ClientNodes -> ClientNodes) -> ClientList
forall a b. (a -> b) -> a -> b
$
    Int -> ClientNodes -> ClientNodes
forall k a. Int -> Map k a -> Map k a
mapTake Int
maxSize
    (ClientNodes -> ClientNodes)
-> (ClientNodes -> ClientNodes) -> ClientNodes -> ClientNodes
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Distance -> ClientNode -> ClientNodes -> ClientNodes
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert
      (PublicKey -> PublicKey -> Distance
Distance.xorDistance (NodeInfo -> PublicKey
NodeInfo.publicKey NodeInfo
nodeInfo) PublicKey
baseKey)
      (Timestamp -> NodeInfo -> ClientNode
ClientNode.newNode Timestamp
time NodeInfo
nodeInfo)
  where
    -- | 'mapTake' is 'Data.Map.take' in >=containers-0.5.8, but we define it
    -- for compatibility with older versions.
    mapTake :: Int -> Map k a -> Map k a
    mapTake :: Int -> Map k a -> Map k a
mapTake Int
n = [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
Map.fromDistinctAscList ([(k, a)] -> Map k a)
-> (Map k a -> [(k, a)]) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [(k, a)] -> [(k, a)]
forall a. Int -> [a] -> [a]
take Int
n ([(k, a)] -> [(k, a)])
-> (Map k a -> [(k, a)]) -> Map k a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
Map.toAscList


removeNode :: PublicKey -> ClientList -> ClientList
removeNode :: PublicKey -> ClientList -> ClientList
removeNode PublicKey
publicKey ClientList
clientList =
  ((ClientNodes -> ClientNodes) -> ClientList -> ClientList
`updateClientNodes` ClientList
clientList) ((ClientNodes -> ClientNodes) -> ClientList)
-> (PublicKey -> ClientNodes -> ClientNodes)
-> PublicKey
-> ClientList
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
    Distance -> ClientNodes -> ClientNodes
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete (Distance -> ClientNodes -> ClientNodes)
-> (PublicKey -> Distance)
-> PublicKey
-> ClientNodes
-> ClientNodes
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PublicKey -> PublicKey -> Distance
Distance.xorDistance PublicKey
publicKey (PublicKey -> ClientList) -> PublicKey -> ClientList
forall a b. (a -> b) -> a -> b
$ ClientList -> PublicKey
baseKey ClientList
clientList

viable :: NodeInfo -> ClientList -> Bool
viable :: NodeInfo -> ClientList -> Bool
viable NodeInfo
nodeInfo ClientList{ PublicKey
baseKey :: PublicKey
baseKey :: ClientList -> PublicKey
baseKey, Int
maxSize :: Int
maxSize :: ClientList -> Int
maxSize, ClientNodes
nodes :: ClientNodes
nodes :: ClientList -> ClientNodes
nodes } =
  let key :: Distance
key = PublicKey -> PublicKey -> Distance
Distance.xorDistance (NodeInfo -> PublicKey
NodeInfo.publicKey NodeInfo
nodeInfo) PublicKey
baseKey
  in (Distance
key Distance -> [Distance] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem`) ([Distance] -> Bool)
-> ([Distance] -> [Distance]) -> [Distance] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [Distance] -> [Distance]
forall a. Int -> [a] -> [a]
take Int
maxSize ([Distance] -> [Distance])
-> ([Distance] -> [Distance]) -> [Distance] -> [Distance]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Distance] -> [Distance]
forall a. Ord a => [a] -> [a]
sort ([Distance] -> Bool) -> [Distance] -> Bool
forall a b. (a -> b) -> a -> b
$ Distance
key Distance -> [Distance] -> [Distance]
forall a. a -> [a] -> [a]
: ClientNodes -> [Distance]
forall k a. Map k a -> [k]
Map.keys ClientNodes
nodes

\end{code}

The iteration order of a Client List is in order of distance from the base
key.  I.e. the first node seen in iteration is the closest, and the last node
is the furthest away in terms of the distance metric.

\begin{code}

foldNodes :: (a -> NodeInfo -> a) -> a -> ClientList -> a
foldNodes :: (a -> NodeInfo -> a) -> a -> ClientList -> a
foldNodes a -> NodeInfo -> a
f a
x = (a -> NodeInfo -> a) -> a -> [NodeInfo] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl a -> NodeInfo -> a
f a
x ([NodeInfo] -> a) -> (ClientList -> [NodeInfo]) -> ClientList -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ClientList -> [NodeInfo]
nodeInfos

closeNodes :: PublicKey -> ClientList -> [ (Distance, NodeInfo) ]
closeNodes :: PublicKey -> ClientList -> [(Distance, NodeInfo)]
closeNodes PublicKey
publicKey ClientList{ PublicKey
baseKey :: PublicKey
baseKey :: ClientList -> PublicKey
baseKey, ClientNodes
nodes :: ClientNodes
nodes :: ClientList -> ClientNodes
nodes } =
  Map Distance NodeInfo -> [(Distance, NodeInfo)]
forall k a. Map k a -> [(k, a)]
Map.toAscList (Map Distance NodeInfo -> [(Distance, NodeInfo)])
-> (ClientNodes -> Map Distance NodeInfo)
-> ClientNodes
-> [(Distance, NodeInfo)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ClientNode -> NodeInfo) -> ClientNodes -> Map Distance NodeInfo
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ClientNode -> NodeInfo
ClientNode.nodeInfo (ClientNodes -> [(Distance, NodeInfo)])
-> ClientNodes -> [(Distance, NodeInfo)]
forall a b. (a -> b) -> a -> b
$
    (Distance -> Distance) -> ClientNodes -> ClientNodes
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys (PublicKey -> PublicKey -> Distance -> Distance
Distance.rebaseDistance PublicKey
baseKey PublicKey
publicKey) ClientNodes
nodes

{-------------------------------------------------------------------------------
 -
 - :: Tests.
 -
 ------------------------------------------------------------------------------}


genClientList :: PublicKey -> Int -> Gen ClientList
genClientList :: PublicKey -> Int -> Gen ClientList
genClientList PublicKey
publicKey Int
size =
  (ClientList -> (Timestamp, NodeInfo) -> ClientList)
-> ClientList -> [(Timestamp, NodeInfo)] -> ClientList
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (((Timestamp, NodeInfo) -> ClientList -> ClientList)
-> ClientList -> (Timestamp, NodeInfo) -> ClientList
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((Timestamp, NodeInfo) -> ClientList -> ClientList)
 -> ClientList -> (Timestamp, NodeInfo) -> ClientList)
-> ((Timestamp, NodeInfo) -> ClientList -> ClientList)
-> ClientList
-> (Timestamp, NodeInfo)
-> ClientList
forall a b. (a -> b) -> a -> b
$ (Timestamp -> NodeInfo -> ClientList -> ClientList)
-> (Timestamp, NodeInfo) -> ClientList -> ClientList
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Timestamp -> NodeInfo -> ClientList -> ClientList
addNode) (PublicKey -> Int -> ClientList
empty PublicKey
publicKey Int
size) ([(Timestamp, NodeInfo)] -> ClientList)
-> Gen [(Timestamp, NodeInfo)] -> Gen ClientList
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen (Timestamp, NodeInfo) -> Gen [(Timestamp, NodeInfo)]
forall a. Gen a -> Gen [a]
Gen.listOf Gen (Timestamp, NodeInfo)
forall a. Arbitrary a => Gen a
arbitrary


instance Arbitrary ClientList where
  arbitrary :: Gen ClientList
arbitrary = Gen (Gen ClientList) -> Gen ClientList
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join (Gen (Gen ClientList) -> Gen ClientList)
-> Gen (Gen ClientList) -> Gen ClientList
forall a b. (a -> b) -> a -> b
$ PublicKey -> Int -> Gen ClientList
genClientList (PublicKey -> Int -> Gen ClientList)
-> Gen PublicKey -> Gen (Int -> Gen ClientList)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen PublicKey
forall a. Arbitrary a => Gen a
arbitrary Gen (Int -> Gen ClientList) -> Gen Int -> Gen (Gen ClientList)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Gen Int
forall a. Integral a => Gen a
arbitrarySizedNatural
\end{code}