simple caching of synthesis unit contexts

UnitTestBot · AbdullinAM · Jun 20, 2022 · Jun 20, 2022 · Jun 22, 2022 · Jun 28, 2022
commit d1b09c8e7935518c89105a45f8200d27c4812b14
diff --git a/utbot-framework/src/main/kotlin/org/utbot/framework/plugin/api/TestCaseGenerator.kt b/utbot-framework/src/main/kotlin/org/utbot/framework/plugin/api/TestCaseGenerator.kt
@@ -233,7 +233,7 @@ open class TestCaseGenerator(
         return methods.map { method ->
             UtMethodTestSet(
                 method,
-                minimizeExecutions(method2executions.getValue(method).toAssemble()),
+                minimizeExecutions(method2executions.getValue(method).toAssemble(method)),
                 jimpleBody(method),
                 method2errors.getValue(method)
             )
@@ -384,19 +384,14 @@ open class TestCaseGenerator(
         return minimizedExecutions
     }
 
-    private fun List<UtExecution>.toAssemble(): List<UtExecution> =
+    private fun List<UtExecution>.toAssemble(method: UtMethod<*>): List<UtExecution> =
         map { execution ->
             val symbolicExecution = (execution as? UtSymbolicExecution) ?: return@map execution
             val oldStateBefore = execution.stateBefore
 
             val constrainedExecution = symbolicExecution.constrainedExecution ?: return@map execution
-            val aa = Synthesizer(this@TestCaseGenerator, constrainedExecution.modelsAfter)
-            val synthesizedModels = try {
-                aa.synthesize()
-            } catch (e: Throwable) {
-                logger.debug(e) { "Failure during constraint synthesis" }
-                return@map execution
-            }
+            val aa = Synthesizer(this@TestCaseGenerator, method, constrainedExecution.modelsAfter)
+            val synthesizedModels = aa.synthesize()
 
             val (synthesizedThis, synthesizedParameters) = oldStateBefore.thisInstance?.let {
                 synthesizedModels.first() to synthesizedModels.drop(1)

diff --git a/utbot-framework/src/main/kotlin/org/utbot/framework/synthesis/SynthesisUnitChecker.kt b/utbot-framework/src/main/kotlin/org/utbot/framework/synthesis/SynthesisUnitChecker.kt
@@ -1,5 +1,6 @@
 package org.utbot.framework.synthesis
 
+import com.jetbrains.rd.util.AtomicInteger
 import mu.KotlinLogging
 import org.utbot.framework.PathSelectorType
 import org.utbot.framework.UtSettings
@@ -14,14 +15,17 @@ class SynthesisUnitChecker(
     val testCaseGenerator: TestCaseGenerator,
     val declaringClass: SootClass,
 ) {
+    companion object {
+        private val initializerMethodId = AtomicInteger()
+    }
+
     private val logger = KotlinLogging.logger("ConstrainedSynthesisUnitChecker")
-    private var id = 0
 
     fun tryGenerate(synthesisUnitContext: SynthesisUnitContext, parameters: List<UtModel>): List<UtModel>? {
         if (!synthesisUnitContext.isFullyDefined) return null
 
         val synthesisMethodContext = SynthesisMethodContext(synthesisUnitContext)
-        val method = synthesisMethodContext.method("\$initializer_${id++}", declaringClass)
+        val method = synthesisMethodContext.method("\$initializer_${initializerMethodId.getAndIncrement()}", declaringClass)
 
         val execution = run {
             val executions = testCaseGenerator.generateWithPostCondition(

diff --git a/utbot-framework/src/main/kotlin/org/utbot/framework/synthesis/Synthesizer.kt b/utbot-framework/src/main/kotlin/org/utbot/framework/synthesis/Synthesizer.kt
@@ -11,8 +11,21 @@ import org.utbot.framework.plugin.api.util.objectClassId
 
 internal fun Collection<ClassId>.expandable() = filter { !it.isArray && !it.isPrimitive }.toSet()
 
+private object SynthesisCache {
+    private val successfulInitializers =
+        mutableMapOf<UtMethod<*>, MutableMap<List<Int>, MutableList<SynthesisUnitContext>>>()
+
+    operator fun get(utMethod: UtMethod<*>, parameters: List<Int>): List<SynthesisUnitContext> =
+        successfulInitializers.getOrPut(utMethod, ::mutableMapOf).getOrPut(parameters, ::mutableListOf)
+
+    operator fun set(utMethod: UtMethod<*>, parameters: List<Int>, synthesisUnitContext: SynthesisUnitContext) =
+        successfulInitializers.getOrPut(utMethod, ::mutableMapOf).getOrPut(parameters, ::mutableListOf)
+            .add(synthesisUnitContext)
+}
+
 class Synthesizer(
     val testCaseGenerator: TestCaseGenerator,
+    val method: UtMethod<*>,
     val parameters: List<UtModel>,
     val depth: Int = synthesisMaxDepth
 ) {
@@ -49,9 +62,8 @@ class Synthesizer(
 
     private val unitChecker = SynthesisUnitChecker(testCaseGenerator, objectClassId.toSoot())
 
-    private fun splitModels(): Set<Set<UtModel>> {
-        val modelComparator = compareBy<UtModel> { parametersMap[it]!! }
-        val result = parameters.map { sortedSetOf(modelComparator, it) }.toMutableSet()
+    private fun splitModels(): Set<List<UtModel>> {
+        val result = parameters.map { mutableSetOf(it) }.toMutableSet()
         while (true) {
             var changed = false
             loopExit@ for (current in result) {
@@ -72,41 +84,68 @@ class Synthesizer(
             }
             if (!changed) break
         }
-        return result.map { it.sortedBy { parametersMap[it] }.toSet() }.toSet()
+        return result.map { models -> models.sortedBy { parametersMap[it] } }.toSet()
     }
 
     fun synthesize(timeLimit: Long = synthesisTimeoutInMillis): List<UtModel?> {
         val modelSubsets = splitModels()
-        val currentTime = { System.currentTimeMillis() }
-        val startTime = currentTime()
+        val startTime = System.currentTimeMillis()
+        val timeLimitExceeded = { System.currentTimeMillis() - startTime > timeLimit }
 
         val result = MutableList<UtModel?>(parameters.size) { null }
         for (models in modelSubsets) {
-            val modelsList = models.toList()
-            val queueIterator = SynthesisUnitContextQueue(modelsList, statementStorage, depth)
+            val modelIndices = models.map { parametersMap[it]!! }
             var found = false
 
+            for (cachedUnits in SynthesisCache[method, modelIndices]) {
+                if (timeLimitExceeded()) break
+
+                val assembleModel = try {
+                    val mappedUnits = cachedUnits.copyWithNewModelsOrNull(models) ?: continue
+                    unitChecker.tryGenerate(mappedUnits, models)
+                } catch (e: Throwable) {
+                    logger.warn { "Error during assemble model generation from cached unit context" }
+                    null
+                }
+                if (assembleModel != null) {
+                    logger.debug { "Found $assembleModel" }
+                    found = true
+                    break
+                }
+            }
+
+            val queueIterator = SynthesisUnitContextQueue(models, statementStorage, depth)
             while (
                 queueIterator.hasNext() &&
-                (currentTime() - startTime) < timeLimit &&
+                !timeLimitExceeded() &&
                 !found
             ) {
                 val units = queueIterator.next()
                 if (!units.isFullyDefined) continue
 
-                val assembleModel = unitChecker.tryGenerate(units, modelsList)
+                val assembleModel = try {
+                    unitChecker.tryGenerate(units, models)
+                } catch (e: Throwable) {
+                    logger.error { "Error during assemble model generation" }
+                    logger.error(e.message)
+                    logger.error(e.stackTraceToString())
+                    null
+                }
+
                 if (assembleModel != null) {
                     logger.debug { "Found $assembleModel" }
-                    success()
-                    for ((model, assemble) in modelsList.zip(assembleModel)) {
-                        result[parametersMap[model]!!] = assemble
+                    for ((index, assemble) in modelIndices.zip(assembleModel)) {
+                        result[index] = assemble
                     }
+                    SynthesisCache[method, modelIndices] = units
                     found = true
                 }
             }
 
-            if (found) success()
-            else failure()
+            when {
+                found -> success()
+                else -> failure()
+            }
         }
         return result
     }
@@ -178,6 +217,16 @@ class SynthesisUnitContext(
 
         is MethodUnit -> params.all { it.isFullyDefined() }
     }
+
+    fun copyWithNewModelsOrNull(newModels: List<UtModel>): SynthesisUnitContext? {
+        // if current context contains some internal models -- we cannot copy it
+        if (mapping.size != models.size) return null
+
+        val modelMapping = models.zip(newModels).toMap()
+        return SynthesisUnitContext(newModels, mapping.mapKeys {
+            modelMapping[it.key] ?: return null
+        })
+    }
 }
 
 class SynthesisUnitContextQueue(
@@ -276,15 +325,15 @@ class SynthesisUnitContextQueue(
     private fun produce(state: SynthesisUnit): List<SynthesisUnit> =
         when (state) {
             is MethodUnit -> state.params.run {
-                    flatMapIndexed { idx, leaf ->
-                        val newLeafs = produce(leaf)
-                        newLeafs.map { newLeaf ->
-                            val newParams = toMutableList()
-                            newParams[idx] = newLeaf
-                            state.copy(params = newParams)
-                        }
+                flatMapIndexed { idx, leaf ->
+                    val newLeafs = produce(leaf)
+                    newLeafs.map { newLeaf ->
+                        val newParams = toMutableList()
+                        newParams[idx] = newLeaf
+                        state.copy(params = newParams)
                     }
                 }
+            }
 
             is ObjectUnit -> {
                 val leafs = leafExpander.expand(state)