BookSpec.scala

package adcal1222_3

import cats.{Applicative, Order}
import cats.data.NonEmptyList
import cats.data.NonEmptyList.one
import cats.instances.list._
import cats.instances.string._
import cats.syntax.either._
import cats.syntax.traverse._
import org.scalacheck.cats.implicits._
import org.scalacheck.{Gen, Prop}
import Book._

sealed trait Target { val value: String }
sealed trait Name  extends Target
case class Addr(value:  String) extends Target
case class Alias(value: String) extends Name
case class Group(value: String) extends Name

case class Book(assoc: BookAssoc) {
  def names:                 Set[Name]           = assoc.keySet
  def addresses(name: Name): Option[SomeTargets] = assoc.get(name)

  def add(n: Name, t: Target): ErrorOrBook = {
    val targets = n match {
      case _: Alias => one(t)
      case _: Group => assoc.get(n).fold(one(t))(ts => (t :: ts).distinct)
    }
    val updated = assoc.updated(n, targets)
    Either.cond(isValidMap(updated), Book(updated), "circular reference")
  }
  def del(n: Name, t: Target): Book = Book {
    n match {
      case _: Alias => assoc - n
      case _: Group => assoc.get(n).fold(assoc) {
        _ filter (_ != t) match {
          case Nil => assoc - n
          case th :: tt => assoc.updated(n, NonEmptyList(th, tt))
        }
      }
    }
  }
  def lookup(n: Name): Set[Addr] = assoc.get(n).fold(Set.empty[Addr]) {
    _.map {
      case addr: Addr => Set(addr)
      case name: Name => lookup(name)
    }.toList.toSet.flatten
  }
}
object Book {
  type SomeTargets = NonEmptyList[Target]
  type BookAssoc   = Map[Name, SomeTargets]
  type ErrorOrBook = Either[String, Book]
  implicit val targetOrder: Order[Target] = (t1, t2) => Order.compare(t1.value, t2.value)

  val empty: Book = apply(Map.empty[Name, SomeTargets])

  def isValid(b: Book):             Boolean = isValidMap(b.assoc)
  def isValidMap(assoc: BookAssoc): Boolean = checkCirculation(assoc)
  def checkCirculation(assoc: BookAssoc): Boolean = {
    def loop(n: Name, ns: Set[Name] = Set.empty[Name]): Boolean =
      !(ns contains n) && assoc.get(n).forall {
        _.forall {
          case _: Addr => true
          case n: Name => loop(n, ns + n)
        }
      }
    assoc.keySet.forall(loop(_))
  }
}

object BookSpec extends org.scalacheck.Properties("Book Spec") {
  import Prop.forAll

  implicit val applicativeGen: Applicative[Gen] = new Applicative[Gen] {
    def pure[A](x: A): Gen[A] = Gen.const(x)
    def ap[A, B](ff: Gen[A => B])(fa: Gen[A]): Gen[B] = ff flatMap fa.map
  }
  val genAddr:  Gen[Addr]  = Gen.oneOf("A1", "A2", "A3") map Addr
  val genAlias: Gen[Alias] = Gen.oneOf("N1", "N2", "N3") map Alias
  val genGroup: Gen[Group] = Gen.oneOf("G1", "G2", "G3") map Group

  val genName:   Gen[Name]   = Gen.oneOf(genAlias, genGroup)
  val genTarget: Gen[Target] = Gen.oneOf(genAddr, genAlias, genGroup)

  def genSomeTargets(max: Int): Gen[SomeTargets] = for {
    m <- Gen.chooseNum(1, max)
    h <- genTarget
    t <- Gen.listOfN(m - 1, genTarget)
  } yield NonEmptyList(h, t)

  val genBook: Gen[Book] = {
    val genAssoc = for {
      len    <- Gen.chooseNum(0, 3)
      names  <- Gen.listOfN(len, genName)
      tuples <- names.map {
        case a: Alias => genSomeTargets(1).map((a, _))
        case g: Group => genSomeTargets(3).map((g, _))
      }.sequence[Gen, (Name, SomeTargets)]
    } yield tuples.toMap
    genAssoc retryUntil Book.isValidMap map Book.apply
  }
  case class Operation(f: Book => ErrorOrBook, display: String) {
    def apply(b: Book): ErrorOrBook = f(b)
    override def toString: String   = display
  }
  val genOperationList: Gen[List[Operation]] = {
    val genOperation = for {
      n <- genName
      t <- genTarget
      o <- Gen.oneOf(
        Operation(b => b.add(n, t),        s"add($n, $t)"),
        Operation(b => Right(b.del(n, t)), s"del($n, $t)"))
    } yield o
    Gen.chooseNum(0, 5) flatMap(Gen.listOfN(_, genOperation))
  }

  property("del undoes add") =
    forAll(genBook, genName, genTarget) { (b, n, t) =>
      b.addresses(n).nonEmpty || b.add(n, t).map(_.del(n, t)).forall(b == _)
    }
  property("add idempotent") =
    forAll(genBook, genName, genTarget) { (b0, n, t) =>
      (for {
        b1 <- b0.add(n, t)
        b2 <- b1.add(n, t)
      } yield b1 == b2).forall(identity)
    }
  property("lookup yields") =
    forAll(genBook) { b =>
      b.names.forall(b.addresses(_).nonEmpty)
    }
  property("add succeeds on empty book") =
    forAll(genName, genTarget) { (n, t) =>
      n == t || Book.empty.add(n, t).isRight
    }
  property("invariants keep") =
    forAll(genBook, genOperationList) { (b, os) =>
      os.foldLeft(b.asRight[String])(_ flatMap _.apply).forall(Book.isValid)
    }
}