Skip to content

Make UtEnumConstModel and UtClassRefModel reference models #414 #611

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
dtim merged 3 commits into from
Aug 4, 2022
Merged

Make UtEnumConstModel and UtClassRefModel reference models #414 #611

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
fb11fdb
Make UtEnumConstModel and UtClassRefModel reference models #414
dtim Jun 27, 2022
0b7cbc1
Fuzzer refactoring: id generator interface and caching id generator
dtim Aug 3, 2022
b11b184
A unit test to check that enum ids in recursive models are consistent
dtim Aug 4, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Fuzzer refactoring: id generator interface and caching id generator 
A custom id generator interface hierarchy is used instead of `IntSupplier`:
  * `IdGenerator` that allows to create fresh identifiers,
  * `IdentityPreservingIdGenerator`: `IdGenerator` that can return
    the same id for the same object.

A default implementation of `IdentityPreservingIdGenerator` is used in
fuzzer. It uses reference equality for object comparison, that allows
to create distinct models of equal object (in `equals` sense), and
to always assign the same id to the same enum value.
  • Loading branch information
@dtim
dtim committed Aug 4, 2022
commit 0b7cbc195a2b1c941ff4a8047970ab2ff35858b4
8 changes: 8 additions & 0 deletions utbot-framework-api/src/main/kotlin/org/utbot/framework/plugin/api/util/IdUtil.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -117,6 +117,9 @@ val ClassId.isFloatType: Boolean
val ClassId.isDoubleType: Boolean
get() = this == doubleClassId || this == doubleWrapperClassId

val ClassId.isClassType: Boolean
get() = this == classClassId

val voidClassId = ClassId("void")
val booleanClassId = ClassId("boolean")
val byteClassId = ClassId("byte")
Expand All @@ -138,6 +141,8 @@ val longWrapperClassId = java.lang.Long::class.id
val floatWrapperClassId = java.lang.Float::class.id
val doubleWrapperClassId = java.lang.Double::class.id

val classClassId = java.lang.Class::class.id

// We consider void wrapper as primitive wrapper
// because voidClassId is considered primitive here
val primitiveWrappers = setOf(
Expand Down Expand Up @@ -285,6 +290,9 @@ val ClassId.isMap: Boolean
val ClassId.isIterableOrMap: Boolean
get() = isIterable || isMap

val ClassId.isEnum: Boolean
get() = jClass.isEnum

fun ClassId.findFieldByIdOrNull(fieldId: FieldId): Field? {
if (isNotSubtypeOf(fieldId.declaringClass)) {
return null
Expand Down
12 changes: 6 additions & 6 deletions utbot-framework/src/main/kotlin/org/utbot/engine/UtBotSymbolicEngine.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -82,6 +82,7 @@ import org.utbot.framework.plugin.api.util.utContext
import org.utbot.framework.plugin.api.util.description
import org.utbot.framework.util.jimpleBody
import org.utbot.framework.plugin.api.util.voidClassId
import org.utbot.fuzzer.ReferencePreservingIntIdGenerator
import org.utbot.fuzzer.FallbackModelProvider
import org.utbot.fuzzer.FuzzedMethodDescription
import org.utbot.fuzzer.FuzzedValue
Expand Down Expand Up @@ -114,8 +115,7 @@ class EngineController {
//for debugging purpose only
private var stateSelectedCount = 0

//all id values of synthetic default models must be greater that for real ones
private var nextDefaultModelId = 1500_000_000
private val defaultIdGenerator = ReferencePreservingIntIdGenerator()

private fun pathSelector(graph: InterProceduralUnitGraph, typeRegistry: TypeRegistry) =
when (pathSelectorType) {
Expand Down Expand Up @@ -391,7 +391,7 @@ class UtBotSymbolicEngine(
return@flow
}

val fallbackModelProvider = FallbackModelProvider { nextDefaultModelId++ }
val fallbackModelProvider = FallbackModelProvider(defaultIdGenerator)
val constantValues = collectConstantsForFuzzer(graph)

val thisInstance = when {
Expand All @@ -405,7 +405,7 @@ class UtBotSymbolicEngine(
null
}
else -> {
ObjectModelProvider { nextDefaultModelId++ }.withFallback(fallbackModelProvider).generate(
ObjectModelProvider(ReferencePreservingIntIdGenerator()).withFallback(fallbackModelProvider).generate(
FuzzedMethodDescription("thisInstance", voidClassId, listOf(methodUnderTest.clazz.id), constantValues)
).take(10).shuffled(Random(0)).map { it.value.model }.first().apply {
if (this is UtNullModel) { // it will definitely fail because of NPE,
Expand All @@ -427,14 +427,14 @@ class UtBotSymbolicEngine(
var attempts = UtSettings.fuzzingMaxAttempts
val hasMethodUnderTestParametersToFuzz = executableId.parameters.isNotEmpty()
val fuzzedValues = if (hasMethodUnderTestParametersToFuzz) {
fuzz(methodUnderTestDescription, modelProvider(defaultModelProviders { nextDefaultModelId++ }))
fuzz(methodUnderTestDescription, modelProvider(defaultModelProviders(defaultIdGenerator)))
} else {
// in case a method with no parameters is passed fuzzing tries to fuzz this instance with different constructors, setters and field mutators
val thisMethodDescription = FuzzedMethodDescription("thisInstance", voidClassId, listOf(methodUnderTest.clazz.id), constantValues).apply {
className = executableId.classId.simpleName
packageName = executableId.classId.packageName
}
fuzz(thisMethodDescription, ObjectModelProvider { nextDefaultModelId++ }.apply {
fuzz(thisMethodDescription, ObjectModelProvider(defaultIdGenerator).apply {
limitValuesCreatedByFieldAccessors = 500
})
}
Expand Down
58 changes: 35 additions & 23 deletions utbot-framework/src/main/kotlin/org/utbot/fuzzer/FallbackModelProvider.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -14,6 +14,8 @@ import org.utbot.framework.plugin.api.util.defaultValueModel
import org.utbot.framework.plugin.api.util.executableId
import org.utbot.framework.plugin.api.util.id
import org.utbot.framework.plugin.api.util.isArray
import org.utbot.framework.plugin.api.util.isClassType
import org.utbot.framework.plugin.api.util.isEnum
import org.utbot.framework.plugin.api.util.isIterable
import org.utbot.framework.plugin.api.util.isPrimitive
import org.utbot.framework.plugin.api.util.jClass
Expand All @@ -31,7 +33,7 @@ import kotlin.reflect.KClass
* Used as a fallback implementation until other providers cover every type.
*/
open class FallbackModelProvider(
private val idGenerator: IntSupplier
private val idGenerator: IdGenerator<Int>
): AbstractModelProvider() {

override fun toModel(classId: ClassId): UtModel {
Expand All @@ -46,11 +48,11 @@ open class FallbackModelProvider(
it.parameters.isEmpty() && it.isPublic
}
return when {
classId.isPrimitive ->
classId.isPrimitive || classId.isEnum || classId.isClassType ->
classId.defaultValueModel()
classId.isArray ->
UtArrayModel(
id = idGenerator.asInt,
id = idGenerator.createId(),
classId,
length = 0,
classId.elementClassId!!.defaultValueModel(),
Expand Down Expand Up @@ -81,26 +83,36 @@ open class FallbackModelProvider(
val defaultConstructor = kclass.java.constructors.firstOrNull {
it.parameters.isEmpty() && it.isPublic // check constructor is public
}
return if (kclass.isAbstract) { // sealed class is abstract by itself
UtNullModel(kclass.java.id)
} else if (defaultConstructor != null) {
val chain = mutableListOf<UtStatementModel>()
val model = UtAssembleModel(
id = idGenerator.asInt,
kclass.id,
kclass.id.toString(),
chain
)
chain.add(
UtExecutableCallModel(model, defaultConstructor.executableId, listOf(), model)
)
model
} else {
UtCompositeModel(
id = idGenerator.asInt,
kclass.id,
isMock = false
)
return when {
kclass.isAbstract -> {
// sealed class is abstract by itself
UtNullModel(kclass.java.id)

}
kclass.java.isEnum || kclass == java.lang.Class::class -> {
// No sensible fallback solution for these classes except returning default `null` value
UtNullModel(kclass.java.id)
}
defaultConstructor != null -> {
val chain = mutableListOf<UtStatementModel>()
val model = UtAssembleModel(
id = idGenerator.createId(),
kclass.id,
kclass.id.toString(),
chain
)
chain.add(
UtExecutableCallModel(model, defaultConstructor.executableId, listOf(), model)
)
model
}
else -> {
UtCompositeModel(
id = idGenerator.createId(),
kclass.id,
isMock = false
)
}
}
}
}
88 changes: 80 additions & 8 deletions utbot-fuzzers/src/main/kotlin/org/utbot/fuzzer/Fuzzer.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,12 +12,89 @@ import org.utbot.fuzzer.providers.PrimitiveDefaultsModelProvider
import org.utbot.fuzzer.providers.EnumModelProvider
import org.utbot.fuzzer.providers.PrimitiveWrapperModelProvider
import java.lang.IllegalArgumentException
import java.util.IdentityHashMap
import java.util.concurrent.atomic.AtomicInteger
import java.util.function.IntSupplier
import kotlin.random.Random

private val logger by lazy { KotlinLogging.logger {} }

/**
* Identifier generator interface for fuzzer model providers.
*
* Provides fresh identifiers for generated models.
*
* Warning: specific generators are not guaranteed to be thread-safe.
*
* @param Id the identifier type (e.g., [Int] for [UtReferenceModel] providers)
*/
interface IdGenerator<Id> {
/**
* Create a fresh identifier. Each subsequent call should return a different value.
*
* The method is not guaranteed to be thread-safe, unless an implementation makes such a guarantee.
*/
fun createId(): Id
}

/**
* Identity preserving identifier generator interface.
*
* It allows to optionally save identifiers assigned to specific objects and later get the same identifiers
* for these objects instead of fresh identifiers. This feature is necessary, for example, to implement reference
* equality for enum models.
*
* Warning: specific generators are not guaranteed to be thread-safe.
*
* @param Id the identifier type (e.g., [Int] for [UtReferenceModel] providers)
*/
interface IdentityPreservingIdGenerator<Id> : IdGenerator<Id> {
/**
* Return an identifier for a specified non-null object. If an identifier has already been assigned
* to an object, subsequent calls should return the same identifier for this object.
*
* Note: the interface does not specify whether reference equality or regular `equals`/`compareTo` equality
* will be used to compare objects. Each implementation may provide these guarantees by itself.
*
* The method is not guaranteed to be thread-safe, unless an implementation makes such a guarantee.
*/
fun getOrCreateIdForValue(value: Any): Id
}

/**
* An identity preserving id generator for fuzzer value providers that returns identifiers of type [Int].
*
* When identity-preserving identifier is requested, objects are compared by reference.
* The generator is not thread-safe.
*
* @param lowerBound an integer value so that any generated identifier is strictly greater than it.
*
* Warning: when generating [UtReferenceModel] identifiers, no identifier should be equal to zero,
* as this value is reserved for [UtNullModel]. To guarantee it, [lowerBound] should never be negative.
* Avoid using custom lower bounds (maybe except fuzzer unit tests), use the predefined default value instead.
*/
class ReferencePreservingIntIdGenerator(lowerBound: Int = DEFAULT_LOWER_BOUND) : IdentityPreservingIdGenerator<Int> {
private val lastId: AtomicInteger = AtomicInteger(lowerBound)
private val cache: IdentityHashMap<Any?, Int> = IdentityHashMap()

override fun getOrCreateIdForValue(value: Any): Int {
return cache.getOrPut(value) { createId() }
}

override fun createId(): Int {
return lastId.incrementAndGet()
}

companion object {
/**
* The default lower bound (all generated integer identifiers will be greater than it).
*
* It is defined as a large value because all synthetic [UtModel] instances
* must have greater identifiers than the real models.
*/
const val DEFAULT_LOWER_BOUND: Int = 1500_000_000
}
}

fun fuzz(description: FuzzedMethodDescription, vararg modelProviders: ModelProvider): Sequence<List<FuzzedValue>> {
if (modelProviders.isEmpty()) {
throw IllegalArgumentException("At least one model provider is required")
Expand All @@ -42,7 +119,7 @@ fun fuzz(description: FuzzedMethodDescription, vararg modelProviders: ModelProvi
/**
* Creates a model provider from a list of default providers.
*/
fun defaultModelProviders(idGenerator: IntSupplier = SimpleIdGenerator()): ModelProvider {
fun defaultModelProviders(idGenerator: IdentityPreservingIdGenerator<Int>): ModelProvider {
return ModelProvider.of(
ObjectModelProvider(idGenerator),
CollectionModelProvider(idGenerator),
Expand All @@ -59,7 +136,7 @@ fun defaultModelProviders(idGenerator: IntSupplier = SimpleIdGenerator()): Model
/**
* Creates a model provider for [ObjectModelProvider] that generates values for object constructor.
*/
fun objectModelProviders(idGenerator: IntSupplier = SimpleIdGenerator()): ModelProvider {
fun objectModelProviders(idGenerator: IdentityPreservingIdGenerator<Int>): ModelProvider {
return ModelProvider.of(
CollectionModelProvider(idGenerator),
ArrayModelProvider(idGenerator),
Expand All @@ -71,8 +148,3 @@ fun objectModelProviders(idGenerator: IntSupplier = SimpleIdGenerator()): ModelP
PrimitiveWrapperModelProvider,
)
}

class SimpleIdGenerator : IntSupplier {
private val id = AtomicInteger()
override fun getAsInt() = id.incrementAndGet()
}
5 changes: 3 additions & 2 deletions utbot-fuzzers/src/main/kotlin/org/utbot/fuzzer/providers/ArrayModelProvider.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,12 +5,13 @@ import org.utbot.framework.plugin.api.util.defaultValueModel
import org.utbot.framework.plugin.api.util.isArray
import org.utbot.fuzzer.FuzzedMethodDescription
import org.utbot.fuzzer.FuzzedParameter
import org.utbot.fuzzer.IdGenerator
import org.utbot.fuzzer.ModelProvider
import org.utbot.fuzzer.ModelProvider.Companion.yieldAllValues
import java.util.function.IntSupplier

class ArrayModelProvider(
private val idGenerator: IntSupplier
private val idGenerator: IdGenerator<Int>
) : ModelProvider {
override fun generate(description: FuzzedMethodDescription): Sequence<FuzzedParameter> = sequence {
description.parametersMap
Expand All @@ -19,7 +20,7 @@ class ArrayModelProvider(
.forEach { (arrayClassId, indices) ->
yieldAllValues(indices, listOf(0, 10).map { arraySize ->
UtArrayModel(
id = idGenerator.asInt,
id = idGenerator.createId(),
arrayClassId,
length = arraySize,
arrayClassId.elementClassId!!.defaultValueModel(),
Expand Down
5 changes: 3 additions & 2 deletions utbot-fuzzers/src/main/kotlin/org/utbot/fuzzer/providers/CollectionModelProvider.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -11,6 +11,7 @@ import org.utbot.framework.plugin.api.util.id
import org.utbot.framework.plugin.api.util.jClass
import org.utbot.fuzzer.FuzzedMethodDescription
import org.utbot.fuzzer.FuzzedParameter
import org.utbot.fuzzer.IdGenerator
import org.utbot.fuzzer.ModelProvider
import org.utbot.fuzzer.ModelProvider.Companion.yieldAllValues
import java.util.function.IntSupplier
Expand All @@ -23,7 +24,7 @@ import java.util.function.IntSupplier
* a non-modifiable collection and tries to add values.
*/
class CollectionModelProvider(
private val idGenerator: IntSupplier
private val idGenerator: IdGenerator<Int>
) : ModelProvider {

private val generators = mapOf(
Expand Down Expand Up @@ -92,7 +93,7 @@ class CollectionModelProvider(

private fun Class<*>.createdBy(init: ExecutableId, params: List<UtModel> = emptyList()): UtAssembleModel {
val instantiationChain = mutableListOf<UtStatementModel>()
val genId = idGenerator.asInt
val genId = idGenerator.createId()
return UtAssembleModel(
genId,
id,
Expand Down
19 changes: 3 additions & 16 deletions utbot-fuzzers/src/main/kotlin/org/utbot/fuzzer/providers/EnumModelProvider.kt
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,34 +1,21 @@
package org.utbot.fuzzer.providers

import org.utbot.framework.plugin.api.UtEnumConstantModel
import org.utbot.framework.plugin.api.util.id
import org.utbot.framework.plugin.api.util.isSubtypeOf
import org.utbot.framework.plugin.api.util.jClass
import org.utbot.fuzzer.IdentityPreservingIdGenerator
import org.utbot.fuzzer.FuzzedMethodDescription
import org.utbot.fuzzer.FuzzedParameter
import org.utbot.fuzzer.ModelProvider
import org.utbot.fuzzer.ModelProvider.Companion.yieldAllValues
import java.util.function.IntSupplier

class EnumModelProvider : ModelProvider {
private val idGenerator: IntSupplier
private val limit: Int
private val idCache: MutableMap<Enum<*>, Int> = mutableMapOf()

constructor(idGenerator: IntSupplier) : this(idGenerator, Int.MAX_VALUE)

constructor(idGenerator: IntSupplier, limit: Int) {
this.idGenerator = idGenerator
this.limit = limit
}

class EnumModelProvider(private val idGenerator: IdentityPreservingIdGenerator<Int>) : ModelProvider {
override fun generate(description: FuzzedMethodDescription): Sequence<FuzzedParameter> = sequence {
description.parametersMap
.asSequence()
.filter { (classId, _) -> classId.jClass.isEnum }
.forEach { (classId, indices) ->
yieldAllValues(indices, classId.jClass.enumConstants.filterIsInstance<Enum<*>>().map {
val id = idCache[it] ?: idGenerator.asInt
val id = idGenerator.getOrCreateIdForValue(it)
UtEnumConstantModel(id, classId, it).fuzzed { summary = "%var% = ${it.name}" }
})
}
Expand Down
Loading