/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml --traceabstraction.trace.refinement.strategy FIXED_PREFERENCES --cacsl2boogietranslator.allow.undefined.functions true --traceabstraction.smt.solver External_ModelsAndUnsatCoreMode --traceabstraction.command.for.external.solver 'cvc5 --incremental --print-success --lang smt' -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-05 02:29:20,294 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-05 02:29:20,366 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf [2024-11-05 02:29:20,371 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-05 02:29:20,371 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-05 02:29:20,400 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-05 02:29:20,401 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-05 02:29:20,401 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-05 02:29:20,402 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-05 02:29:20,403 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-05 02:29:20,404 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-05 02:29:20,404 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-05 02:29:20,406 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-05 02:29:20,407 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-05 02:29:20,407 INFO L153 SettingsManager]: * Use SBE=true [2024-11-05 02:29:20,407 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-05 02:29:20,407 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-05 02:29:20,408 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-05 02:29:20,408 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-05 02:29:20,408 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-05 02:29:20,408 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-05 02:29:20,410 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-05 02:29:20,410 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-05 02:29:20,411 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-05 02:29:20,411 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-05 02:29:20,411 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-05 02:29:20,411 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-05 02:29:20,411 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-05 02:29:20,412 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-05 02:29:20,412 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-05 02:29:20,412 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-05 02:29:20,412 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-05 02:29:20,412 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-05 02:29:20,413 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-05 02:29:20,413 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-05 02:29:20,413 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-05 02:29:20,413 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-05 02:29:20,413 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-05 02:29:20,414 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-05 02:29:20,414 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-05 02:29:20,414 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-05 02:29:20,416 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FIXED_PREFERENCES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMT solver -> External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Command for external solver -> cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:20,624 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-05 02:29:20,650 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-05 02:29:20,654 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-05 02:29:20,655 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-05 02:29:20,656 INFO L274 PluginConnector]: CDTParser initialized [2024-11-05 02:29:20,657 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i [2024-11-05 02:29:22,051 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-05 02:29:22,432 INFO L384 CDTParser]: Found 1 translation units. [2024-11-05 02:29:22,433 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i [2024-11-05 02:29:22,469 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b347cc89e/647ade86805843fe82288ac68545302a/FLAG45e2b9296 [2024-11-05 02:29:22,486 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b347cc89e/647ade86805843fe82288ac68545302a [2024-11-05 02:29:22,488 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-05 02:29:22,491 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-05 02:29:22,493 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-05 02:29:22,493 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-05 02:29:22,499 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-05 02:29:22,500 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.11 02:29:22" (1/1) ... [2024-11-05 02:29:22,501 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5e45fab1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:22, skipping insertion in model container [2024-11-05 02:29:22,501 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.11 02:29:22" (1/1) ... [2024-11-05 02:29:22,595 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-05 02:29:22,882 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i[4500,4513] [2024-11-05 02:29:22,891 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i[4560,4573] [2024-11-05 02:29:23,399 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,492 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,493 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,494 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,503 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,505 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,505 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,506 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,506 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,507 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,508 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,512 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,512 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,514 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,515 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,526 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,526 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,527 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,527 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,528 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,529 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,529 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,529 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,531 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,532 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,532 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,532 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,533 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,533 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:23,831 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,831 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,832 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:23,833 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,006 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,037 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:29:24,061 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-05 02:29:24,125 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-05 02:29:24,144 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i[4500,4513] [2024-11-05 02:29:24,145 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i[4560,4573] [2024-11-05 02:29:24,180 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,199 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,199 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,200 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,204 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,205 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,205 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,206 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,208 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,208 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,208 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,210 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,210 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,213 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,213 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,218 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,219 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,219 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,219 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,220 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,221 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,221 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,221 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,222 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,222 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,223 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,223 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,223 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,223 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,271 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,275 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,276 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,276 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,307 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:29:24,316 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:29:24,324 INFO L200 MainTranslator]: Completed pre-run [2024-11-05 02:29:24,338 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i[4500,4513] [2024-11-05 02:29:24,338 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_push_front_harness.i[4560,4573] [2024-11-05 02:29:24,396 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,397 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,397 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,397 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,398 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,403 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,404 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,405 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,406 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,406 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,407 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,407 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,408 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:29:24,473 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:29:24,653 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-05 02:29:24,665 INFO L204 MainTranslator]: Completed translation [2024-11-05 02:29:24,666 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24 WrapperNode [2024-11-05 02:29:24,666 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-05 02:29:24,667 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-05 02:29:24,667 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-05 02:29:24,667 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-05 02:29:24,676 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,741 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,782 INFO L138 Inliner]: procedures = 687, calls = 1046, calls flagged for inlining = 52, calls inlined = 6, statements flattened = 154 [2024-11-05 02:29:24,783 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-05 02:29:24,784 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-05 02:29:24,784 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-05 02:29:24,784 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-05 02:29:24,795 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,796 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,802 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,830 INFO L175 MemorySlicer]: Split 36 memory accesses to 3 slices as follows [2, 29, 5]. 81 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 0, 5]. The 10 writes are split as follows [0, 10, 0]. [2024-11-05 02:29:24,832 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,832 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,853 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,856 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,865 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,868 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,880 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-05 02:29:24,881 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-05 02:29:24,882 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-05 02:29:24,882 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-05 02:29:24,882 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (1/1) ... [2024-11-05 02:29:24,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-05 02:29:24,898 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-05 02:29:24,912 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-05 02:29:24,915 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-05 02:29:24,942 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-05 02:29:24,942 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-05 02:29:24,942 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-05 02:29:24,942 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-05 02:29:24,943 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-05 02:29:24,943 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-05 02:29:24,943 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-05 02:29:24,943 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-05 02:29:24,943 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-05 02:29:24,944 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-05 02:29:24,944 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-05 02:29:24,944 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-05 02:29:24,944 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-05 02:29:24,945 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-05 02:29:24,945 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-05 02:29:24,945 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_insert_before [2024-11-05 02:29:24,946 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_insert_before [2024-11-05 02:29:24,946 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-05 02:29:24,946 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-05 02:29:24,946 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-05 02:29:24,946 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-05 02:29:24,946 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-05 02:29:24,946 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-05 02:29:24,946 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-05 02:29:24,947 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-05 02:29:24,947 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-05 02:29:24,947 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-05 02:29:24,947 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-05 02:29:24,947 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-05 02:29:24,947 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-05 02:29:24,947 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2024-11-05 02:29:24,947 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2024-11-05 02:29:25,246 INFO L238 CfgBuilder]: Building ICFG [2024-11-05 02:29:25,248 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-05 02:29:25,717 INFO L? ?]: Removed 67 outVars from TransFormulas that were not future-live. [2024-11-05 02:29:25,717 INFO L287 CfgBuilder]: Performing block encoding [2024-11-05 02:29:25,732 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-05 02:29:25,733 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-05 02:29:25,733 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.11 02:29:25 BoogieIcfgContainer [2024-11-05 02:29:25,733 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-05 02:29:25,737 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-05 02:29:25,737 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-05 02:29:25,740 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-05 02:29:25,740 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.11 02:29:22" (1/3) ... [2024-11-05 02:29:25,740 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bf5cf5a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.11 02:29:25, skipping insertion in model container [2024-11-05 02:29:25,741 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:29:24" (2/3) ... [2024-11-05 02:29:25,741 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bf5cf5a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.11 02:29:25, skipping insertion in model container [2024-11-05 02:29:25,741 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.11 02:29:25" (3/3) ... [2024-11-05 02:29:25,742 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_push_front_harness.i [2024-11-05 02:29:25,757 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-05 02:29:25,757 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-05 02:29:25,815 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-05 02:29:25,821 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@6402982f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-05 02:29:25,821 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-05 02:29:25,827 INFO L276 IsEmpty]: Start isEmpty. Operand has 104 states, 67 states have (on average 1.2835820895522387) internal successors, (86), 68 states have internal predecessors, (86), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2024-11-05 02:29:25,835 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-05 02:29:25,836 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:29:25,836 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:29:25,837 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:29:25,841 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:29:25,841 INFO L85 PathProgramCache]: Analyzing trace with hash 2111829670, now seen corresponding path program 1 times [2024-11-05 02:29:25,848 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:29:25,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1476290198] [2024-11-05 02:29:25,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:29:25,852 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:25,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:29:25,856 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:29:25,858 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (2)] Waiting until timeout for monitored process [2024-11-05 02:29:26,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:29:26,132 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-05 02:29:26,138 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:29:26,172 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-05 02:29:26,172 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:29:26,255 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-05 02:29:26,256 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:29:26,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1476290198] [2024-11-05 02:29:26,256 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1476290198] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:29:26,256 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:29:26,256 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-05 02:29:26,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [230780736] [2024-11-05 02:29:26,263 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:29:26,269 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-05 02:29:26,269 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:29:26,287 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-05 02:29:26,288 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-05 02:29:26,290 INFO L87 Difference]: Start difference. First operand has 104 states, 67 states have (on average 1.2835820895522387) internal successors, (86), 68 states have internal predecessors, (86), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) Second operand has 2 states, 2 states have (on average 19.0) internal successors, (38), 2 states have internal predecessors, (38), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-05 02:29:26,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:29:26,319 INFO L93 Difference]: Finished difference Result 200 states and 295 transitions. [2024-11-05 02:29:26,322 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-05 02:29:26,323 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 19.0) internal successors, (38), 2 states have internal predecessors, (38), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 74 [2024-11-05 02:29:26,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:29:26,332 INFO L225 Difference]: With dead ends: 200 [2024-11-05 02:29:26,333 INFO L226 Difference]: Without dead ends: 99 [2024-11-05 02:29:26,341 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 146 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-05 02:29:26,345 INFO L432 NwaCegarLoop]: 138 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-05 02:29:26,348 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 138 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-05 02:29:26,366 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2024-11-05 02:29:26,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2024-11-05 02:29:26,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 63 states have (on average 1.2380952380952381) internal successors, (78), 64 states have internal predecessors, (78), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2024-11-05 02:29:26,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 133 transitions. [2024-11-05 02:29:26,406 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 133 transitions. Word has length 74 [2024-11-05 02:29:26,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:29:26,407 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 133 transitions. [2024-11-05 02:29:26,407 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 19.0) internal successors, (38), 2 states have internal predecessors, (38), 2 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-05 02:29:26,407 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 133 transitions. [2024-11-05 02:29:26,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-05 02:29:26,413 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:29:26,413 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:29:26,416 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (2)] Ended with exit code 0 [2024-11-05 02:29:26,614 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:26,615 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:29:26,615 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:29:26,615 INFO L85 PathProgramCache]: Analyzing trace with hash 839656352, now seen corresponding path program 1 times [2024-11-05 02:29:26,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:29:26,616 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1321810516] [2024-11-05 02:29:26,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:29:26,616 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:26,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:29:26,617 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:29:26,618 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (3)] Waiting until timeout for monitored process [2024-11-05 02:29:26,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:29:26,826 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-05 02:29:26,829 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:29:26,883 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-11-05 02:29:26,883 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:29:26,946 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2024-11-05 02:29:26,947 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:29:26,947 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1321810516] [2024-11-05 02:29:26,947 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1321810516] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:29:26,947 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:29:26,947 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 4 [2024-11-05 02:29:26,947 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [813538997] [2024-11-05 02:29:26,947 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:29:26,948 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-05 02:29:26,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:29:26,951 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-05 02:29:26,951 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-05 02:29:26,952 INFO L87 Difference]: Start difference. First operand 99 states and 133 transitions. Second operand has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-05 02:29:27,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:29:27,000 INFO L93 Difference]: Finished difference Result 187 states and 257 transitions. [2024-11-05 02:29:27,003 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-05 02:29:27,004 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 74 [2024-11-05 02:29:27,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:29:27,005 INFO L225 Difference]: With dead ends: 187 [2024-11-05 02:29:27,006 INFO L226 Difference]: Without dead ends: 102 [2024-11-05 02:29:27,006 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 144 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-05 02:29:27,009 INFO L432 NwaCegarLoop]: 130 mSDtfsCounter, 1 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-05 02:29:27,009 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 384 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-05 02:29:27,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-05 02:29:27,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2024-11-05 02:29:27,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 67 states have internal predecessors, (81), 28 states have call successors, (28), 7 states have call predecessors, (28), 7 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2024-11-05 02:29:27,028 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 136 transitions. [2024-11-05 02:29:27,028 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 136 transitions. Word has length 74 [2024-11-05 02:29:27,030 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:29:27,030 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 136 transitions. [2024-11-05 02:29:27,030 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-05 02:29:27,030 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 136 transitions. [2024-11-05 02:29:27,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-05 02:29:27,033 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:29:27,033 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:29:27,038 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (3)] Ended with exit code 0 [2024-11-05 02:29:27,233 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:27,234 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:29:27,234 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:29:27,235 INFO L85 PathProgramCache]: Analyzing trace with hash 358576094, now seen corresponding path program 1 times [2024-11-05 02:29:27,235 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:29:27,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [350486143] [2024-11-05 02:29:27,235 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:29:27,235 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:27,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:29:27,236 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:29:27,237 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (4)] Waiting until timeout for monitored process [2024-11-05 02:29:27,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:29:27,449 WARN L253 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 159 conjuncts are in the unsatisfiable core [2024-11-05 02:29:27,465 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:29:27,506 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:29:27,575 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-05 02:29:27,731 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:29:27,789 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:29:28,020 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:29:28,020 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:29:28,047 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:29:28,073 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:29:29,937 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-05 02:29:29,937 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:29:30,438 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-05 02:29:30,438 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:29:30,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [350486143] [2024-11-05 02:29:30,438 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [350486143] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:29:30,438 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:29:30,438 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [6] total 18 [2024-11-05 02:29:30,439 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [396976476] [2024-11-05 02:29:30,439 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:29:30,439 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-05 02:29:30,439 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:29:30,440 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-05 02:29:30,440 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:29:30,440 INFO L87 Difference]: Start difference. First operand 102 states and 136 transitions. Second operand has 14 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (11), 3 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-05 02:29:33,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:29:33,058 INFO L93 Difference]: Finished difference Result 246 states and 329 transitions. [2024-11-05 02:29:33,058 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-05 02:29:33,058 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (11), 3 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 74 [2024-11-05 02:29:33,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:29:33,062 INFO L225 Difference]: With dead ends: 246 [2024-11-05 02:29:33,062 INFO L226 Difference]: Without dead ends: 153 [2024-11-05 02:29:33,064 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 121 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=82, Invalid=424, Unknown=0, NotChecked=0, Total=506 [2024-11-05 02:29:33,065 INFO L432 NwaCegarLoop]: 113 mSDtfsCounter, 66 mSDsluCounter, 610 mSDsCounter, 0 mSdLazyCounter, 274 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 723 SdHoareTripleChecker+Invalid, 284 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 274 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-05 02:29:33,065 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 723 Invalid, 284 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 274 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-05 02:29:33,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2024-11-05 02:29:33,087 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 152. [2024-11-05 02:29:33,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 104 states have (on average 1.25) internal successors, (130), 106 states have internal predecessors, (130), 36 states have call successors, (36), 12 states have call predecessors, (36), 11 states have return successors, (35), 33 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-05 02:29:33,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 201 transitions. [2024-11-05 02:29:33,091 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 201 transitions. Word has length 74 [2024-11-05 02:29:33,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:29:33,091 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 201 transitions. [2024-11-05 02:29:33,092 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (11), 3 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-05 02:29:33,092 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 201 transitions. [2024-11-05 02:29:33,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-05 02:29:33,093 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:29:33,093 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:29:33,100 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (4)] Ended with exit code 0 [2024-11-05 02:29:33,299 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:33,300 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:29:33,300 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:29:33,300 INFO L85 PathProgramCache]: Analyzing trace with hash 87330846, now seen corresponding path program 1 times [2024-11-05 02:29:33,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:29:33,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [108510098] [2024-11-05 02:29:33,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:29:33,301 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:33,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:29:33,304 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:29:33,306 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (5)] Waiting until timeout for monitored process [2024-11-05 02:29:33,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:29:33,488 WARN L253 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 168 conjuncts are in the unsatisfiable core [2024-11-05 02:29:33,502 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:29:33,514 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:29:33,557 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-05 02:29:33,678 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:29:33,703 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:29:33,732 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:29:33,931 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:29:33,931 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:29:33,956 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:29:35,790 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-05 02:29:35,790 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:29:36,299 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-05 02:29:36,299 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:29:36,299 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [108510098] [2024-11-05 02:29:36,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [108510098] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:29:36,299 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:29:36,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [7] total 20 [2024-11-05 02:29:36,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [953108798] [2024-11-05 02:29:36,300 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:29:36,300 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-05 02:29:36,300 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:29:36,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-05 02:29:36,301 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=323, Unknown=0, NotChecked=0, Total=380 [2024-11-05 02:29:36,301 INFO L87 Difference]: Start difference. First operand 152 states and 201 transitions. Second operand has 15 states, 13 states have (on average 3.3846153846153846) internal successors, (44), 13 states have internal predecessors, (44), 4 states have call successors, (11), 3 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-05 02:29:39,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:29:39,902 INFO L93 Difference]: Finished difference Result 251 states and 332 transitions. [2024-11-05 02:29:39,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-05 02:29:39,902 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 3.3846153846153846) internal successors, (44), 13 states have internal predecessors, (44), 4 states have call successors, (11), 3 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 76 [2024-11-05 02:29:39,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:29:39,905 INFO L225 Difference]: With dead ends: 251 [2024-11-05 02:29:39,905 INFO L226 Difference]: Without dead ends: 153 [2024-11-05 02:29:39,906 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 131 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=82, Invalid=470, Unknown=0, NotChecked=0, Total=552 [2024-11-05 02:29:39,906 INFO L432 NwaCegarLoop]: 136 mSDtfsCounter, 52 mSDsluCounter, 812 mSDsCounter, 0 mSdLazyCounter, 378 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 948 SdHoareTripleChecker+Invalid, 391 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 378 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.1s IncrementalHoareTripleChecker+Time [2024-11-05 02:29:39,907 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 948 Invalid, 391 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 378 Invalid, 0 Unknown, 0 Unchecked, 3.1s Time] [2024-11-05 02:29:39,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2024-11-05 02:29:39,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 152. [2024-11-05 02:29:39,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 104 states have (on average 1.2307692307692308) internal successors, (128), 106 states have internal predecessors, (128), 36 states have call successors, (36), 12 states have call predecessors, (36), 11 states have return successors, (35), 33 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-05 02:29:39,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 199 transitions. [2024-11-05 02:29:39,928 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 199 transitions. Word has length 76 [2024-11-05 02:29:39,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:29:39,928 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 199 transitions. [2024-11-05 02:29:39,928 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 3.3846153846153846) internal successors, (44), 13 states have internal predecessors, (44), 4 states have call successors, (11), 3 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-05 02:29:39,928 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 199 transitions. [2024-11-05 02:29:39,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-05 02:29:39,930 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:29:39,930 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:29:39,934 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (5)] Ended with exit code 0 [2024-11-05 02:29:40,130 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:40,131 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:29:40,131 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:29:40,131 INFO L85 PathProgramCache]: Analyzing trace with hash -1987244964, now seen corresponding path program 1 times [2024-11-05 02:29:40,131 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:29:40,131 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1420555643] [2024-11-05 02:29:40,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:29:40,132 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:40,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:29:40,133 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:29:40,134 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (6)] Waiting until timeout for monitored process [2024-11-05 02:29:40,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:29:40,350 WARN L253 TraceCheckSpWp]: Trace formula consists of 280 conjuncts, 177 conjuncts are in the unsatisfiable core [2024-11-05 02:29:40,364 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:29:40,370 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:29:40,402 INFO L349 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2024-11-05 02:29:40,402 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 9 treesize of output 15 [2024-11-05 02:29:40,425 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 1 [2024-11-05 02:29:40,430 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:29:40,683 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:29:40,706 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:29:40,862 INFO L349 Elim1Store]: treesize reduction 8, result has 68.0 percent of original size [2024-11-05 02:29:40,863 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 20 treesize of output 30 [2024-11-05 02:29:40,915 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:29:40,916 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 35 [2024-11-05 02:29:40,957 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:29:40,957 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 39 [2024-11-05 02:29:41,370 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:29:41,371 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 159 treesize of output 109 [2024-11-05 02:29:41,396 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2024-11-05 02:29:41,400 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:29:41,434 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:29:41,435 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 76 treesize of output 71 [2024-11-05 02:29:44,654 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 24 proven. 5 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-05 02:29:44,655 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:29:45,121 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-05 02:29:45,121 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:29:45,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1420555643] [2024-11-05 02:29:45,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1420555643] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:29:45,121 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:29:45,121 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 6] total 20 [2024-11-05 02:29:45,122 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [621264220] [2024-11-05 02:29:45,122 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:29:45,122 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-05 02:29:45,122 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:29:45,123 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-05 02:29:45,123 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=323, Unknown=0, NotChecked=0, Total=380 [2024-11-05 02:29:45,124 INFO L87 Difference]: Start difference. First operand 152 states and 199 transitions. Second operand has 20 states, 17 states have (on average 4.470588235294118) internal successors, (76), 17 states have internal predecessors, (76), 6 states have call successors, (20), 4 states have call predecessors, (20), 7 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-05 02:29:56,668 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-05 02:29:59,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:29:59,503 INFO L93 Difference]: Finished difference Result 300 states and 399 transitions. [2024-11-05 02:29:59,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-05 02:29:59,503 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 4.470588235294118) internal successors, (76), 17 states have internal predecessors, (76), 6 states have call successors, (20), 4 states have call predecessors, (20), 7 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) Word has length 76 [2024-11-05 02:29:59,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:29:59,506 INFO L225 Difference]: With dead ends: 300 [2024-11-05 02:29:59,506 INFO L226 Difference]: Without dead ends: 206 [2024-11-05 02:29:59,507 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 168 GetRequests, 132 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 266 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=155, Invalid=1035, Unknown=0, NotChecked=0, Total=1190 [2024-11-05 02:29:59,508 INFO L432 NwaCegarLoop]: 160 mSDtfsCounter, 181 mSDsluCounter, 1117 mSDsCounter, 0 mSdLazyCounter, 580 mSolverCounterSat, 26 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 1277 SdHoareTripleChecker+Invalid, 607 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 580 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.3s IncrementalHoareTripleChecker+Time [2024-11-05 02:29:59,508 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [188 Valid, 1277 Invalid, 607 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 580 Invalid, 1 Unknown, 0 Unchecked, 12.3s Time] [2024-11-05 02:29:59,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2024-11-05 02:29:59,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 184. [2024-11-05 02:29:59,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 131 states have (on average 1.251908396946565) internal successors, (164), 135 states have internal predecessors, (164), 38 states have call successors, (38), 14 states have call predecessors, (38), 14 states have return successors, (39), 34 states have call predecessors, (39), 37 states have call successors, (39) [2024-11-05 02:29:59,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 241 transitions. [2024-11-05 02:29:59,543 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 241 transitions. Word has length 76 [2024-11-05 02:29:59,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:29:59,543 INFO L471 AbstractCegarLoop]: Abstraction has 184 states and 241 transitions. [2024-11-05 02:29:59,543 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 4.470588235294118) internal successors, (76), 17 states have internal predecessors, (76), 6 states have call successors, (20), 4 states have call predecessors, (20), 7 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-05 02:29:59,543 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 241 transitions. [2024-11-05 02:29:59,544 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-05 02:29:59,545 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:29:59,545 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:29:59,548 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (6)] Ended with exit code 0 [2024-11-05 02:29:59,745 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:59,746 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:29:59,746 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:29:59,746 INFO L85 PathProgramCache]: Analyzing trace with hash 958884107, now seen corresponding path program 1 times [2024-11-05 02:29:59,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:29:59,746 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1581336189] [2024-11-05 02:29:59,746 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:29:59,746 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:29:59,747 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:29:59,748 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:29:59,749 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (7)] Waiting until timeout for monitored process [2024-11-05 02:29:59,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:29:59,951 WARN L253 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 171 conjuncts are in the unsatisfiable core [2024-11-05 02:29:59,962 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:29:59,967 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:29:59,997 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-05 02:30:00,132 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:30:00,150 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:30:00,245 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 7 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:00,259 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 7 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:00,277 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:01,548 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-11-05 02:30:01,548 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:30:02,255 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2024-11-05 02:30:02,256 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:30:02,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1581336189] [2024-11-05 02:30:02,256 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1581336189] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:30:02,256 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:30:02,256 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13, 10] imperfect sequences [] total 21 [2024-11-05 02:30:02,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1304768082] [2024-11-05 02:30:02,256 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:30:02,257 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-05 02:30:02,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:30:02,257 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-05 02:30:02,258 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2024-11-05 02:30:02,258 INFO L87 Difference]: Start difference. First operand 184 states and 241 transitions. Second operand has 21 states, 19 states have (on average 3.6315789473684212) internal successors, (69), 19 states have internal predecessors, (69), 5 states have call successors, (20), 3 states have call predecessors, (20), 4 states have return successors, (18), 4 states have call predecessors, (18), 5 states have call successors, (18) [2024-11-05 02:30:04,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:30:04,246 INFO L93 Difference]: Finished difference Result 305 states and 402 transitions. [2024-11-05 02:30:04,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-05 02:30:04,247 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 3.6315789473684212) internal successors, (69), 19 states have internal predecessors, (69), 5 states have call successors, (20), 3 states have call predecessors, (20), 4 states have return successors, (18), 4 states have call predecessors, (18), 5 states have call successors, (18) Word has length 78 [2024-11-05 02:30:04,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:30:04,248 INFO L225 Difference]: With dead ends: 305 [2024-11-05 02:30:04,248 INFO L226 Difference]: Without dead ends: 139 [2024-11-05 02:30:04,249 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 135 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=138, Invalid=564, Unknown=0, NotChecked=0, Total=702 [2024-11-05 02:30:04,250 INFO L432 NwaCegarLoop]: 109 mSDtfsCounter, 92 mSDsluCounter, 937 mSDsCounter, 0 mSdLazyCounter, 292 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 1046 SdHoareTripleChecker+Invalid, 314 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 292 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-05 02:30:04,250 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [103 Valid, 1046 Invalid, 314 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 292 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-05 02:30:04,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-11-05 02:30:04,282 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2024-11-05 02:30:04,282 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 93 states have (on average 1.1720430107526882) internal successors, (109), 96 states have internal predecessors, (109), 34 states have call successors, (34), 11 states have call predecessors, (34), 11 states have return successors, (35), 31 states have call predecessors, (35), 33 states have call successors, (35) [2024-11-05 02:30:04,283 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 178 transitions. [2024-11-05 02:30:04,284 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 178 transitions. Word has length 78 [2024-11-05 02:30:04,284 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:30:04,284 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 178 transitions. [2024-11-05 02:30:04,284 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 3.6315789473684212) internal successors, (69), 19 states have internal predecessors, (69), 5 states have call successors, (20), 3 states have call predecessors, (20), 4 states have return successors, (18), 4 states have call predecessors, (18), 5 states have call successors, (18) [2024-11-05 02:30:04,284 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 178 transitions. [2024-11-05 02:30:04,285 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-05 02:30:04,285 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:30:04,285 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:30:04,288 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (7)] Ended with exit code 0 [2024-11-05 02:30:04,486 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:04,487 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:30:04,487 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:30:04,487 INFO L85 PathProgramCache]: Analyzing trace with hash 1465660058, now seen corresponding path program 1 times [2024-11-05 02:30:04,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:30:04,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1557172320] [2024-11-05 02:30:04,487 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:30:04,487 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:04,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:30:04,488 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:30:04,489 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (8)] Waiting until timeout for monitored process [2024-11-05 02:30:04,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:30:04,693 WARN L253 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 206 conjuncts are in the unsatisfiable core [2024-11-05 02:30:04,704 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:30:04,710 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:30:04,729 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 1 [2024-11-05 02:30:04,735 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:04,752 INFO L349 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2024-11-05 02:30:04,752 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 9 treesize of output 15 [2024-11-05 02:30:04,990 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:04,997 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:30:05,023 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2024-11-05 02:30:05,188 INFO L349 Elim1Store]: treesize reduction 46, result has 43.9 percent of original size [2024-11-05 02:30:05,189 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 26 treesize of output 54 [2024-11-05 02:30:05,304 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:30:05,305 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 35 [2024-11-05 02:30:05,372 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:30:05,372 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 39 [2024-11-05 02:30:05,431 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:05,448 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:06,394 INFO L349 Elim1Store]: treesize reduction 36, result has 53.8 percent of original size [2024-11-05 02:30:06,394 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 177 treesize of output 147 [2024-11-05 02:30:06,597 INFO L349 Elim1Store]: treesize reduction 20, result has 79.4 percent of original size [2024-11-05 02:30:06,598 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 48 treesize of output 110 [2024-11-05 02:30:07,045 INFO L349 Elim1Store]: treesize reduction 80, result has 24.5 percent of original size [2024-11-05 02:30:07,045 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 76 treesize of output 63 [2024-11-05 02:30:07,856 INFO L349 Elim1Store]: treesize reduction 64, result has 37.9 percent of original size [2024-11-05 02:30:07,857 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 6 disjoint index pairs (out of 15 index pairs), introduced 7 new quantified variables, introduced 14 case distinctions, treesize of input 188 treesize of output 141 [2024-11-05 02:30:07,949 INFO L349 Elim1Store]: treesize reduction 112, result has 29.6 percent of original size [2024-11-05 02:30:07,949 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 6 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 13 case distinctions, treesize of input 106 treesize of output 123 [2024-11-05 02:30:08,035 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1