TraceHash.scala

package tracehash

final case class Cover(suffixLength: Int, fragmentLength: Int, coverSize: Int)

object `package` {
  def stackTraceHash(ex: Throwable): String = {
    val stackTrace = principalStackTrace(
      Slice.of(ex.getStackTrace),
      ex.isInstanceOf[StackOverflowError])

    val stackTraceStr = stackTrace.toList
      .map { el =>
        val className  = Option(el.getClassName).getOrElse("{null}")
        val methodName = Option(el.getMethodName).getOrElse("{null}")
        className + "/" + methodName
      }
      .mkString("|")

    val prefix  = ex.getClass.getName.filter(_.isUpper).mkString("")
    val descStr = ex.getClass.getCanonicalName + " : " + stackTraceStr

    prefix + "-" + sha1(descStr)
  }

  def sha1(str: String): String = {
    val md = java.security.MessageDigest.getInstance("SHA-1")
    md.update(str.getBytes("UTF-8"))
    md.digest()
      .map(x => Integer.toString((x & 0xff) + 0x100, 16).drop(1))
      .mkString("")
  }
  
  private[this] val SOE_MAX_FRAGMENT_SIZE = 255
  private[this] val NON_SOE_PRINCIPAL_SIZE = 5
  
  def principalStackTrace(
    stack: Slice[StackTraceElement],
    stackOverflow: Boolean
  ): Slice[StackTraceElement] =
    if (stackOverflow) {
      principalSOStackTrace(stack.reverse) match {
        case None    => stack.slice(0, NON_SOE_PRINCIPAL_SIZE).reverse
        case Some(x) => x
      }
    } else stack.slice(0, NON_SOE_PRINCIPAL_SIZE).reverse
  
  def principalSOStackTrace(stack: Slice[StackTraceElement]): Option[Slice[StackTraceElement]] = {
    val cover = bestCover(stack)

    if (cover.coverSize >= cover.fragmentLength * 2) {
      var index = cover.suffixLength
      var minIndex = index
      var minSlice = stack.slice(index, cover.fragmentLength)

      while (index < cover.fragmentLength) {
        val currentSlice = stack.slice(index, cover.fragmentLength)

        if (currentSlice < minSlice) {
          minIndex = index
          minSlice = currentSlice
        }

        index += 1
      }

      Some(minSlice)
    } else None
  }
  
  def bestCover(stack: Slice[StackTraceElement]): Cover = {
    val result = Array.ofDim[Cover](SOE_MAX_FRAGMENT_SIZE)

    var suffixLen = 1
    while (suffixLen <= SOE_MAX_FRAGMENT_SIZE) {
      val suffix = stack.slice(0, suffixLen)

      var maxCoverage = 0
      var maxFragLen = 0

      var fragLen = suffixLen
      while (fragLen + suffixLen < stack.length &&
             fragLen <= SOE_MAX_FRAGMENT_SIZE)
      {
        if (fragLen >= suffixLen) {
          val fragSuffix = stack.slice(fragLen, suffixLen)

          if (fragSuffix === suffix) {
            val fragment = stack.slice(suffixLen, fragLen)

            val coverage = cover(stack, fragment, suffixLen)
            if (coverage > maxCoverage) {
              maxCoverage = coverage
              maxFragLen = fragLen
            }
          }
        }

        fragLen += 1
      }

      result(suffixLen - 1) = Cover(suffixLen, maxFragLen, maxCoverage)

      suffixLen += 1
    }

    result.sortBy { case Cover(sl, fl, mv) => (-mv, fl, sl) }
    result(0)
  }

  def cover[A](array: Slice[A], fragment: Slice[A], start: Int)(implicit A: Ord[Slice[A]]): Int = {
    var index = start
    var done = false
    while (!done && index + fragment.length < array.length) {
      val other = array.slice(index, fragment.length)
      if (other === fragment) index += fragment.length
      else done = true
    }
    index - start
  }
  
  implicit class OrdOps[A](val a: A) extends AnyVal {
    def < (b: A)(implicit A: Ord[A]): Boolean =
      A.compare(a, b) == Comparison.LT
    def ===(b: A)(implicit A: Ord[A]): Boolean =
      A.compare(a, b) == Comparison.EQ
    def >< (b: A)(implicit A: Ord[A]): Comparison =
      A.compare(a, b)
  }
}

final class Slice[A](
  array: Array[A],
  start: Int,
  val length: Int,
  val reversed: Boolean
) {
  private[this] def index(i: Int): Int = {
    require(0 <= i && i < length)
    if (!reversed) start + i
    else start + length - 1 - i
  }

  def apply(i: Int): A = array(index(i))

  def slice(newStart: Int, newLength: Int): Slice[A] = {
    require(0 <= newStart && newStart <= length)
    require(0 <= newLength && newStart + newLength < length)
    val from = index(newStart)
    val to = index(newStart + newLength - 1)
    new Slice(array, math.min(from, to), newLength, reversed)
  }

  def reverse: Slice[A] =
    new Slice(array, start, length, !reversed)

  def toList: List[A] = {
    val builder = List.newBuilder[A]
    var i: Int = 0
    while (i < length) {
      builder += apply(i)
      i += 1
    }
    builder.result()
  }
}
object Slice {
  def of[A](array: Array[A]): Slice[A] =
    new Slice(array, 0, array.length, false)
}

sealed abstract class Comparison {
  import Comparison._

  def |+| (that: Comparison): Comparison = (this, that) match {
    case (LT, _) => LT
    case (EQ, x) => x
    case (GT, _) => GT
  }
}
object Comparison {
  final case object GT extends Comparison
  final case object EQ extends Comparison
  final case object LT extends Comparison
}

trait Ord[A] {
  def compare(a: A, b: A): Comparison
}
object Ord {
  def apply[A](implicit A: Ord[A]): Ord[A] = A

  implicit val intOrd: Ord[Int] = new Ord[Int] {
    def compare(a: Int, b: Int): Comparison =
      if      (a < b) Comparison.LT
      else if (a > b) Comparison.GT
      else            Comparison.EQ
  }
  implicit val stringOrd: Ord[String] = new Ord[String] {
    def compare(a: String, b: String): Comparison = {
      val c = a.compareTo(b)
      if      (c == -1) Comparison.LT
      else if (c == 1)  Comparison.GT
      else              Comparison.EQ
    }
  }

  def sliceOrd[A](implicit A: Ord[A]): Ord[Slice[A]] = new Ord[Slice[A]] {
    def compare(a: Slice[A], b: Slice[A]): Comparison = {
      if (a.length != b.length) intOrd.compare(a.length, b.length)
      else {
        val length = a.length
        def go(i: Int): Comparison =
          if (i < length) {
            val cmp = A.compare(a(i), b(i))
            if (cmp == Comparison.EQ) go(i + 1) else cmp
          } else Comparison.EQ
        go(0)
      }
    }
  }

  implicit val stackElementOrd: Ord[StackTraceElement] = new Ord[StackTraceElement] {
    def compare(a: StackTraceElement, b: StackTraceElement): Comparison =
      intOrd.compare(a.getLineNumber, b.getLineNumber) |+|
      stringOrd.compare(a.getClassName, b.getClassName) |+|
      stringOrd.compare(a.getMethodName, b.getMethodName)
  }

  implicit val stackElementSlice: Ord[Slice[StackTraceElement]] =
    sliceOrd(stackElementOrd)
}