<commit_before>package scorex.crypto.authds.merkle

import scorex.crypto.authds.storage.{BlobStorage, StorageType, VersionedStorage}
import scorex.crypto.hash.{Blake2b256, CryptographicHash}
import scorex.utils.ScryptoLogging

import scala.annotation.tailrec
import scala.util.{Failure, Try}


trait MerkleTree[HashFn <: CryptographicHash, ST <: StorageType] extends ScryptoLogging {

  import MerkleTree._

  protected type Level <: BlobStorage[ST]
  protected type LevelId = Int

  protected type LPos = (LevelId, Position)
  type Digest = HashFn#Digest

  val hashFunction: HashFn
  protected lazy val emptyHash = hashFunction(Array[Byte]()).dropRight(1)

  protected def createLevel(level: LevelId, version: VersionedStorage[ST]#VersionTag): Try[Level]

  protected def getLevel(level: LevelId): Option[Level]

  def size: Long

  def height: Int = calculateRequiredLevel(size)

  def rootHash: Digest = getHash((height, 0)).get

  /**
    * Return AuthData at position $index
    */
  def proofByIndex(index: Position): Option[MerklePath[HashFn]] = {
    val nonEmptyBlocks = size

    if (index < nonEmptyBlocks && index >= 0) {
      @tailrec
      def calculateTreePath(n: Position, currentLevel: Int, acc: Seq[Digest] = Seq()): Seq[Digest] = {
        if (currentLevel < height) {
          val hashOpt = if (n % 2 == 0) getHash((currentLevel, n + 1)) else getHash((currentLevel, n - 1))
          hashOpt match {
            case Some(h) =>
              calculateTreePath(n / 2, currentLevel + 1, h +: acc)
            case None if currentLevel == 0 && index == nonEmptyBlocks - 1 =>
              calculateTreePath(n / 2, currentLevel + 1, emptyHash +: acc)
            case None =>
              log.error(s"Unable to get hash for lev=$currentLevel, position=$n")
              acc.reverse
          }
        } else {
          acc.reverse
        }
      }
      Some(MerklePath(index, calculateTreePath(index, 0)))
    } else {
      None
    }
  }

  def getHash(key: LPos): Option[Digest] = {
    getLevel(key._1).get.get(key._2) match {
      //todo: exception
      case None =>
        if (key._1 > 0) {
          val h1 = getHash((key._1 - 1, key._2 * 2))
          val h2 = getHash((key._1 - 1, key._2 * 2 + 1))
          val calculatedHash = (h1, h2) match {
            case (Some(hash1), Some(hash2)) => hashFunction(hash1 ++ hash2)
            case (Some(h), _) => hashFunction(h ++ emptyHash)
            case (_, Some(h)) => hashFunction(emptyHash ++ h)
            case _ => emptyHash
          }
          setTreeElement(key, calculatedHash)
          Some(calculatedHash)
        } else {
          None
        }
      case digest =>
        digest
    }
  }

  protected def setTreeElement(key: LPos, value: Digest): Unit = Try {
    getLevel(key._1).get.set(key._2, value)
  }.recoverWith { case t: Throwable =>
    log.warn("Failed to set key:" + key, t)
    Failure(t)
  }
}

object MerkleTree {
  type Position = Long
  val DefaultHashFunction = Blake2b256

  def calculateRequiredLevel(numberOfDataBlocks: Position): Int = {
    def log2(x: Double): Double = math.log(x) / math.log(2)
    math.ceil(log2(numberOfDataBlocks)).toInt
  }
}<commit_msg>getHash refactoring<commit_after>package scorex.crypto.authds.merkle

import scorex.crypto.authds.storage.{BlobStorage, StorageType, VersionedStorage}
import scorex.crypto.hash.{Blake2b256, CryptographicHash}
import scorex.utils.ScryptoLogging

import scala.annotation.tailrec
import scala.util.{Failure, Try}


trait MerkleTree[HashFn <: CryptographicHash, ST <: StorageType] extends ScryptoLogging {

  import MerkleTree._

  protected type Level <: BlobStorage[ST]
  protected type LevelId = Int

  protected type LPos = (LevelId, Position)
  type Digest = HashFn#Digest

  val hashFunction: HashFn
  protected lazy val emptyHash = hashFunction(Array[Byte]()).dropRight(1)

  protected def createLevel(level: LevelId, version: VersionedStorage[ST]#VersionTag): Try[Level]

  protected def getLevel(level: LevelId): Option[Level]

  def size: Long

  def height: Int = calculateRequiredLevel(size)

  def rootHash: Digest = getHash((height, 0)).get

  /**
    * Return AuthData at position $index
    */
  def proofByIndex(index: Position): Option[MerklePath[HashFn]] = {
    val nonEmptyBlocks = size

    if (index < nonEmptyBlocks && index >= 0) {
      @tailrec
      def calculateTreePath(n: Position, currentLevel: Int, acc: Seq[Digest] = Seq()): Seq[Digest] = {
        if (currentLevel < height) {
          val hashOpt = if (n % 2 == 0) getHash((currentLevel, n + 1)) else getHash((currentLevel, n - 1))
          hashOpt match {
            case Some(h) =>
              calculateTreePath(n / 2, currentLevel + 1, h +: acc)
            case None if currentLevel == 0 && index == nonEmptyBlocks - 1 =>
              calculateTreePath(n / 2, currentLevel + 1, emptyHash +: acc)
            case None =>
              log.error(s"Unable to get hash for lev=$currentLevel, position=$n")
              acc.reverse
          }
        } else {
          acc.reverse
        }
      }
      Some(MerklePath(index, calculateTreePath(index, 0)))
    } else {
      None
    }
  }

  def getHash(key: LPos): Option[Digest] = {
    def setTreeElement(key: LPos, value: Digest): Unit = Try {
      getLevel(key._1).get.set(key._2, value)
    }.recoverWith { case t: Throwable =>
      log.warn("Failed to set key:" + key, t)
      Failure(t)
    }

    getLevel(key._1).get.get(key._2) match {
      //todo: exception
      case None =>
        if (key._1 > 0) {
          val h1 = getHash((key._1 - 1, key._2 * 2))
          val h2 = getHash((key._1 - 1, key._2 * 2 + 1))
          val calculatedHash = (h1, h2) match {
            case (Some(hash1), Some(hash2)) => hashFunction(hash1 ++ hash2)
            case (Some(h), None) => hashFunction(h ++ emptyHash)
            case (None, Some(h)) => hashFunction(emptyHash ++ h)
            case (None, None) => emptyHash
          }
          setTreeElement(key, calculatedHash)
          Some(calculatedHash)
        } else {
          None
        }
      case digest =>
        digest
    }
  }
}

object MerkleTree {
  type Position = Long
  val DefaultHashFunction = Blake2b256

  def calculateRequiredLevel(numberOfDataBlocks: Position): Int = {
    def log2(x: Double): Double = math.log(x) / math.log(2)
    math.ceil(log2(numberOfDataBlocks)).toInt
  }
}
{'fraction_non_alphanumeric': 0.12048757618377871, 'fraction_numerical': 0.015002344116268168, 'mean_word_length': 2.62400906002265, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '935076', 'n_tokens_mistral': 2079, 'n_tokens_neox': 2009, 'n_words': 506}