./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 551b0097 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash d7b9ddf837d983b2f2db252b1327ae049806ab568e5bf2d0a60ffd182bd7d0fe --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 17:20:27,908 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 17:20:27,970 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2025-01-09 17:20:27,976 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 17:20:27,979 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 17:20:28,002 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 17:20:28,003 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 17:20:28,004 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 17:20:28,004 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 17:20:28,004 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 17:20:28,005 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 17:20:28,005 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 17:20:28,005 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 17:20:28,005 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 17:20:28,006 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 17:20:28,006 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 17:20:28,007 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 17:20:28,007 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 17:20:28,007 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 17:20:28,007 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 17:20:28,007 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 17:20:28,007 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 17:20:28,007 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 17:20:28,007 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 17:20:28,008 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 17:20:28,008 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 17:20:28,009 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 17:20:28,009 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> d7b9ddf837d983b2f2db252b1327ae049806ab568e5bf2d0a60ffd182bd7d0fe [2025-01-09 17:20:28,225 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 17:20:28,232 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 17:20:28,234 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 17:20:28,235 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 17:20:28,235 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 17:20:28,236 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i [2025-01-09 17:20:29,424 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/72875c831/e536c8550bab4b149210a01db65258be/FLAGb5a7011b2 [2025-01-09 17:20:29,811 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 17:20:29,812 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i [2025-01-09 17:20:29,835 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/72875c831/e536c8550bab4b149210a01db65258be/FLAGb5a7011b2 [2025-01-09 17:20:29,995 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/72875c831/e536c8550bab4b149210a01db65258be [2025-01-09 17:20:29,999 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 17:20:30,000 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 17:20:30,005 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 17:20:30,005 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 17:20:30,009 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 17:20:30,010 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 05:20:29" (1/1) ... [2025-01-09 17:20:30,010 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5db5173 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:30, skipping insertion in model container [2025-01-09 17:20:30,010 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 05:20:29" (1/1) ... [2025-01-09 17:20:30,057 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 17:20:30,265 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i[4493,4506] [2025-01-09 17:20:30,271 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i[4553,4566] [2025-01-09 17:20:30,698 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,704 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,704 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,705 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,705 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,713 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,714 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,715 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,715 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,718 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,720 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,720 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:30,720 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,092 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i[150674,150687] [2025-01-09 17:20:31,093 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 17:20:31,109 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 17:20:31,122 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i[4493,4506] [2025-01-09 17:20:31,123 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i[4553,4566] [2025-01-09 17:20:31,159 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,159 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,159 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,160 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,160 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,166 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,166 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,167 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,167 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,168 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,168 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,169 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,169 WARN L1731 CHandler]: Possible shadowing of function index [2025-01-09 17:20:31,220 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_end_harness_negated.i[150674,150687] [2025-01-09 17:20:31,220 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 17:20:31,345 INFO L204 MainTranslator]: Completed translation [2025-01-09 17:20:31,346 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31 WrapperNode [2025-01-09 17:20:31,346 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 17:20:31,347 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 17:20:31,347 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 17:20:31,347 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 17:20:31,351 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,382 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,404 INFO L138 Inliner]: procedures = 668, calls = 1038, calls flagged for inlining = 53, calls inlined = 6, statements flattened = 131 [2025-01-09 17:20:31,405 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 17:20:31,405 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 17:20:31,405 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 17:20:31,405 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 17:20:31,411 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,412 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,414 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,432 INFO L175 MemorySlicer]: Split 21 memory accesses to 3 slices as follows [2, 5, 14]. 67 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 6 writes are split as follows [0, 0, 6]. [2025-01-09 17:20:31,433 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,433 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,446 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,447 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,453 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,455 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,456 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,459 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 17:20:31,459 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 17:20:31,459 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 17:20:31,460 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 17:20:31,460 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (1/1) ... [2025-01-09 17:20:31,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 17:20:31,475 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:20:31,492 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-01-09 17:20:31,494 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-01-09 17:20:31,510 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-01-09 17:20:31,510 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 17:20:31,510 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2025-01-09 17:20:31,513 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2025-01-09 17:20:31,513 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 17:20:31,513 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 17:20:31,513 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-01-09 17:20:31,514 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2025-01-09 17:20:31,514 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-09 17:20:31,514 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-01-09 17:20:31,712 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 17:20:31,714 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 17:20:31,918 INFO L? ?]: Removed 53 outVars from TransFormulas that were not future-live. [2025-01-09 17:20:31,918 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 17:20:31,927 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 17:20:31,927 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-09 17:20:31,928 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:20:31 BoogieIcfgContainer [2025-01-09 17:20:31,928 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 17:20:31,929 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 17:20:31,929 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 17:20:31,932 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 17:20:31,932 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 05:20:29" (1/3) ... [2025-01-09 17:20:31,932 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@244c9625 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 05:20:31, skipping insertion in model container [2025-01-09 17:20:31,932 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:20:31" (2/3) ... [2025-01-09 17:20:31,932 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@244c9625 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 05:20:31, skipping insertion in model container [2025-01-09 17:20:31,932 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:20:31" (3/3) ... [2025-01-09 17:20:31,933 INFO L128 eAbstractionObserver]: Analyzing ICFG aws_linked_list_end_harness_negated.i [2025-01-09 17:20:31,941 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 17:20:31,942 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG aws_linked_list_end_harness_negated.i that has 6 procedures, 66 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-01-09 17:20:31,974 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 17:20:31,980 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;@76eed4a1, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 17:20:31,980 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 17:20:31,982 INFO L276 IsEmpty]: Start isEmpty. Operand has 66 states, 46 states have (on average 1.326086956521739) internal successors, (61), 47 states have internal predecessors, (61), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-01-09 17:20:31,987 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2025-01-09 17:20:31,987 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:31,988 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:31,988 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:31,990 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:31,991 INFO L85 PathProgramCache]: Analyzing trace with hash -437087491, now seen corresponding path program 1 times [2025-01-09 17:20:31,995 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:31,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2016647725] [2025-01-09 17:20:31,995 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:31,996 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:32,116 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-01-09 17:20:32,143 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-01-09 17:20:32,143 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:32,143 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:32,253 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-01-09 17:20:32,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:32,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2016647725] [2025-01-09 17:20:32,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2016647725] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:20:32,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2037445171] [2025-01-09 17:20:32,254 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:32,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:20:32,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:20:32,256 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:20:32,258 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-01-09 17:20:32,359 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-01-09 17:20:32,413 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-01-09 17:20:32,413 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:32,413 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:32,416 INFO L256 TraceCheckSpWp]: Trace formula consists of 330 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-01-09 17:20:32,422 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:20:32,434 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-01-09 17:20:32,436 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:20:32,437 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2037445171] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:32,437 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:20:32,437 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-01-09 17:20:32,438 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [56749474] [2025-01-09 17:20:32,439 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:32,441 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-01-09 17:20:32,441 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:32,457 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-01-09 17:20:32,457 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 17:20:32,459 INFO L87 Difference]: Start difference. First operand has 66 states, 46 states have (on average 1.326086956521739) internal successors, (61), 47 states have internal predecessors, (61), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 14.0) internal successors, (28), 2 states have internal predecessors, (28), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:32,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:32,478 INFO L93 Difference]: Finished difference Result 124 states and 172 transitions. [2025-01-09 17:20:32,479 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-01-09 17:20:32,480 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 14.0) internal successors, (28), 2 states have internal predecessors, (28), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 67 [2025-01-09 17:20:32,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:32,485 INFO L225 Difference]: With dead ends: 124 [2025-01-09 17:20:32,485 INFO L226 Difference]: Without dead ends: 61 [2025-01-09 17:20:32,487 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 17:20:32,491 INFO L435 NwaCegarLoop]: 85 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, 85 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 [2025-01-09 17:20:32,493 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 17:20:32,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2025-01-09 17:20:32,516 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2025-01-09 17:20:32,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 42 states have (on average 1.3095238095238095) internal successors, (55), 43 states have internal predecessors, (55), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-01-09 17:20:32,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 80 transitions. [2025-01-09 17:20:32,526 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 80 transitions. Word has length 67 [2025-01-09 17:20:32,526 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:32,526 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 80 transitions. [2025-01-09 17:20:32,527 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 14.0) internal successors, (28), 2 states have internal predecessors, (28), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:32,527 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 80 transitions. [2025-01-09 17:20:32,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2025-01-09 17:20:32,529 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:32,529 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:32,537 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-01-09 17:20:32,730 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-01-09 17:20:32,730 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:32,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:32,730 INFO L85 PathProgramCache]: Analyzing trace with hash -1850366153, now seen corresponding path program 1 times [2025-01-09 17:20:32,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:32,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1399017085] [2025-01-09 17:20:32,731 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:32,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:32,770 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-01-09 17:20:32,810 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-01-09 17:20:32,810 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:32,810 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:33,255 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-01-09 17:20:33,255 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:33,255 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1399017085] [2025-01-09 17:20:33,255 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1399017085] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:33,255 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 17:20:33,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-01-09 17:20:33,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [910414559] [2025-01-09 17:20:33,255 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:33,256 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-01-09 17:20:33,256 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:33,256 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-01-09 17:20:33,256 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-01-09 17:20:33,257 INFO L87 Difference]: Start difference. First operand 61 states and 80 transitions. Second operand has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 1 states have call successors, (7) [2025-01-09 17:20:33,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:33,294 INFO L93 Difference]: Finished difference Result 71 states and 93 transitions. [2025-01-09 17:20:33,294 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-01-09 17:20:33,295 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 1 states have call successors, (7) Word has length 67 [2025-01-09 17:20:33,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:33,297 INFO L225 Difference]: With dead ends: 71 [2025-01-09 17:20:33,297 INFO L226 Difference]: Without dead ends: 69 [2025-01-09 17:20:33,297 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-01-09 17:20:33,297 INFO L435 NwaCegarLoop]: 77 mSDtfsCounter, 3 mSDsluCounter, 300 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 377 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 17:20:33,298 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 377 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 17:20:33,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2025-01-09 17:20:33,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 68. [2025-01-09 17:20:33,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 46 states have (on average 1.2826086956521738) internal successors, (59), 48 states have internal predecessors, (59), 14 states have call successors, (14), 6 states have call predecessors, (14), 7 states have return successors, (17), 13 states have call predecessors, (17), 13 states have call successors, (17) [2025-01-09 17:20:33,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 90 transitions. [2025-01-09 17:20:33,304 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 90 transitions. Word has length 67 [2025-01-09 17:20:33,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:33,305 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 90 transitions. [2025-01-09 17:20:33,305 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 1 states have call successors, (7) [2025-01-09 17:20:33,305 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 90 transitions. [2025-01-09 17:20:33,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-01-09 17:20:33,306 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:33,306 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:33,306 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-09 17:20:33,306 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:33,306 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:33,306 INFO L85 PathProgramCache]: Analyzing trace with hash -815851661, now seen corresponding path program 1 times [2025-01-09 17:20:33,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:33,307 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515939012] [2025-01-09 17:20:33,307 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:33,307 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:33,332 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 69 statements into 1 equivalence classes. [2025-01-09 17:20:33,347 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 69 of 69 statements. [2025-01-09 17:20:33,347 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:33,347 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:33,525 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-01-09 17:20:33,526 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:33,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515939012] [2025-01-09 17:20:33,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1515939012] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:33,526 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 17:20:33,526 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-01-09 17:20:33,526 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650736582] [2025-01-09 17:20:33,526 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:33,527 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-01-09 17:20:33,527 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:33,528 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-01-09 17:20:33,528 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-01-09 17:20:33,528 INFO L87 Difference]: Start difference. First operand 68 states and 90 transitions. Second operand has 7 states, 7 states have (on average 5.428571428571429) internal successors, (38), 7 states have internal predecessors, (38), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:33,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:33,651 INFO L93 Difference]: Finished difference Result 129 states and 172 transitions. [2025-01-09 17:20:33,651 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-09 17:20:33,652 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.428571428571429) internal successors, (38), 7 states have internal predecessors, (38), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 69 [2025-01-09 17:20:33,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:33,653 INFO L225 Difference]: With dead ends: 129 [2025-01-09 17:20:33,653 INFO L226 Difference]: Without dead ends: 70 [2025-01-09 17:20:33,654 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-01-09 17:20:33,655 INFO L435 NwaCegarLoop]: 67 mSDtfsCounter, 21 mSDsluCounter, 278 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 17:20:33,655 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 345 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 17:20:33,656 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2025-01-09 17:20:33,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2025-01-09 17:20:33,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 46 states have (on average 1.2608695652173914) internal successors, (58), 48 states have internal predecessors, (58), 14 states have call successors, (14), 6 states have call predecessors, (14), 7 states have return successors, (17), 13 states have call predecessors, (17), 13 states have call successors, (17) [2025-01-09 17:20:33,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 89 transitions. [2025-01-09 17:20:33,668 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 89 transitions. Word has length 69 [2025-01-09 17:20:33,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:33,668 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 89 transitions. [2025-01-09 17:20:33,668 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.428571428571429) internal successors, (38), 7 states have internal predecessors, (38), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:33,668 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 89 transitions. [2025-01-09 17:20:33,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2025-01-09 17:20:33,669 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:33,670 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:33,670 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-01-09 17:20:33,670 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:33,670 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:33,670 INFO L85 PathProgramCache]: Analyzing trace with hash 144634447, now seen corresponding path program 1 times [2025-01-09 17:20:33,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:33,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1133099238] [2025-01-09 17:20:33,670 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:33,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:33,698 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 71 statements into 1 equivalence classes. [2025-01-09 17:20:33,710 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 71 of 71 statements. [2025-01-09 17:20:33,712 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:33,712 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:33,905 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-01-09 17:20:33,906 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:33,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1133099238] [2025-01-09 17:20:33,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1133099238] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:33,906 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 17:20:33,907 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-01-09 17:20:33,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [277786483] [2025-01-09 17:20:33,907 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:33,907 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 17:20:33,907 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:33,908 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 17:20:33,908 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-01-09 17:20:33,908 INFO L87 Difference]: Start difference. First operand 68 states and 89 transitions. Second operand has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:34,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:34,038 INFO L93 Difference]: Finished difference Result 135 states and 180 transitions. [2025-01-09 17:20:34,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 17:20:34,039 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 71 [2025-01-09 17:20:34,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:34,040 INFO L225 Difference]: With dead ends: 135 [2025-01-09 17:20:34,040 INFO L226 Difference]: Without dead ends: 75 [2025-01-09 17:20:34,040 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2025-01-09 17:20:34,041 INFO L435 NwaCegarLoop]: 64 mSDtfsCounter, 30 mSDsluCounter, 325 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 389 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 17:20:34,041 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 389 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 17:20:34,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2025-01-09 17:20:34,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 69. [2025-01-09 17:20:34,051 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 47 states have (on average 1.2553191489361701) internal successors, (59), 49 states have internal predecessors, (59), 14 states have call successors, (14), 6 states have call predecessors, (14), 7 states have return successors, (17), 13 states have call predecessors, (17), 13 states have call successors, (17) [2025-01-09 17:20:34,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 90 transitions. [2025-01-09 17:20:34,053 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 90 transitions. Word has length 71 [2025-01-09 17:20:34,053 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:34,053 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 90 transitions. [2025-01-09 17:20:34,053 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:34,056 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 90 transitions. [2025-01-09 17:20:34,056 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-01-09 17:20:34,057 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:34,057 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:34,057 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-01-09 17:20:34,057 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:34,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:34,057 INFO L85 PathProgramCache]: Analyzing trace with hash -370795422, now seen corresponding path program 1 times [2025-01-09 17:20:34,057 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:34,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [378654226] [2025-01-09 17:20:34,057 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:34,057 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:34,084 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:20:34,102 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:20:34,105 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:34,105 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:34,320 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-01-09 17:20:34,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:34,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [378654226] [2025-01-09 17:20:34,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [378654226] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:20:34,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [121599214] [2025-01-09 17:20:34,321 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:34,321 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:20:34,321 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:20:34,324 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:20:34,327 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-01-09 17:20:34,426 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:20:34,465 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:20:34,465 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:34,465 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:34,467 INFO L256 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-01-09 17:20:34,471 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:20:34,532 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 18 treesize of output 7 [2025-01-09 17:20:34,541 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 [2025-01-09 17:20:34,608 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:20:34,609 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:20:34,610 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:20:34,615 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 45 treesize of output 21 [2025-01-09 17:20:34,623 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:20:34,624 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:20:34,625 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 29 [2025-01-09 17:20:35,073 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2025-01-09 17:20:35,073 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:20:35,073 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [121599214] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:35,073 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:20:35,073 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [6] total 13 [2025-01-09 17:20:35,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1172987350] [2025-01-09 17:20:35,074 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:35,074 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-01-09 17:20:35,074 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:35,074 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-01-09 17:20:35,074 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2025-01-09 17:20:35,075 INFO L87 Difference]: Start difference. First operand 69 states and 90 transitions. Second operand has 9 states, 9 states have (on average 4.666666666666667) internal successors, (42), 8 states have internal predecessors, (42), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2025-01-09 17:20:35,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:35,448 INFO L93 Difference]: Finished difference Result 189 states and 251 transitions. [2025-01-09 17:20:35,448 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 17:20:35,448 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.666666666666667) internal successors, (42), 8 states have internal predecessors, (42), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 73 [2025-01-09 17:20:35,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:35,450 INFO L225 Difference]: With dead ends: 189 [2025-01-09 17:20:35,450 INFO L226 Difference]: Without dead ends: 132 [2025-01-09 17:20:35,454 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2025-01-09 17:20:35,454 INFO L435 NwaCegarLoop]: 60 mSDtfsCounter, 46 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 17:20:35,454 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 400 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 17:20:35,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2025-01-09 17:20:35,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 130. [2025-01-09 17:20:35,472 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 89 states have (on average 1.2808988764044944) internal successors, (114), 94 states have internal predecessors, (114), 26 states have call successors, (26), 11 states have call predecessors, (26), 14 states have return successors, (34), 24 states have call predecessors, (34), 24 states have call successors, (34) [2025-01-09 17:20:35,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 174 transitions. [2025-01-09 17:20:35,475 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 174 transitions. Word has length 73 [2025-01-09 17:20:35,475 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:35,475 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 174 transitions. [2025-01-09 17:20:35,475 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.666666666666667) internal successors, (42), 8 states have internal predecessors, (42), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2025-01-09 17:20:35,475 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 174 transitions. [2025-01-09 17:20:35,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-01-09 17:20:35,477 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:35,478 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:35,486 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-01-09 17:20:35,678 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:20:35,679 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:35,679 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:35,679 INFO L85 PathProgramCache]: Analyzing trace with hash -851875680, now seen corresponding path program 1 times [2025-01-09 17:20:35,679 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:35,679 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [299856526] [2025-01-09 17:20:35,679 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:35,679 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:35,700 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:20:35,710 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:20:35,710 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:35,710 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:35,924 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-01-09 17:20:35,925 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:35,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [299856526] [2025-01-09 17:20:35,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [299856526] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:20:35,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [995564701] [2025-01-09 17:20:35,925 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:35,925 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:20:35,925 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:20:35,927 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:20:35,932 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-01-09 17:20:36,022 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:20:36,063 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:20:36,063 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:36,063 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:36,065 INFO L256 TraceCheckSpWp]: Trace formula consists of 335 conjuncts, 52 conjuncts are in the unsatisfiable core [2025-01-09 17:20:36,071 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:20:36,117 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 [2025-01-09 17:20:36,128 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 18 treesize of output 7 [2025-01-09 17:20:36,159 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 25 [2025-01-09 17:20:36,171 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 33 treesize of output 28 [2025-01-09 17:20:36,952 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 44 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-01-09 17:20:36,953 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:20:36,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [995564701] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:36,953 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:20:36,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [6] total 14 [2025-01-09 17:20:36,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1773263935] [2025-01-09 17:20:36,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:36,954 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 17:20:36,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:36,955 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 17:20:36,955 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2025-01-09 17:20:36,955 INFO L87 Difference]: Start difference. First operand 130 states and 174 transitions. Second operand has 10 states, 9 states have (on average 6.111111111111111) internal successors, (55), 10 states have internal predecessors, (55), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:20:37,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:37,423 INFO L93 Difference]: Finished difference Result 189 states and 247 transitions. [2025-01-09 17:20:37,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 17:20:37,424 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 6.111111111111111) internal successors, (55), 10 states have internal predecessors, (55), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 73 [2025-01-09 17:20:37,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:37,428 INFO L225 Difference]: With dead ends: 189 [2025-01-09 17:20:37,428 INFO L226 Difference]: Without dead ends: 130 [2025-01-09 17:20:37,429 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 62 SyntacticMatches, 4 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2025-01-09 17:20:37,429 INFO L435 NwaCegarLoop]: 59 mSDtfsCounter, 45 mSDsluCounter, 410 mSDsCounter, 0 mSdLazyCounter, 260 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 469 SdHoareTripleChecker+Invalid, 282 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 260 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 17:20:37,429 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 469 Invalid, 282 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 260 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 17:20:37,430 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2025-01-09 17:20:37,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 128. [2025-01-09 17:20:37,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 88 states have (on average 1.2727272727272727) internal successors, (112), 92 states have internal predecessors, (112), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2025-01-09 17:20:37,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 170 transitions. [2025-01-09 17:20:37,454 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 170 transitions. Word has length 73 [2025-01-09 17:20:37,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:37,454 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 170 transitions. [2025-01-09 17:20:37,454 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 6.111111111111111) internal successors, (55), 10 states have internal predecessors, (55), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:20:37,455 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 170 transitions. [2025-01-09 17:20:37,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2025-01-09 17:20:37,455 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:37,456 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:37,466 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-01-09 17:20:37,656 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:20:37,657 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:37,657 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:37,657 INFO L85 PathProgramCache]: Analyzing trace with hash -2015815503, now seen corresponding path program 1 times [2025-01-09 17:20:37,658 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:37,658 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1017314244] [2025-01-09 17:20:37,658 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:37,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:37,671 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 72 statements into 1 equivalence classes. [2025-01-09 17:20:37,679 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 72 of 72 statements. [2025-01-09 17:20:37,679 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:37,679 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:37,860 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-01-09 17:20:37,861 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:37,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1017314244] [2025-01-09 17:20:37,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1017314244] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:37,861 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 17:20:37,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-01-09 17:20:37,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1469209282] [2025-01-09 17:20:37,861 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:37,862 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 17:20:37,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:37,862 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 17:20:37,863 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-01-09 17:20:37,863 INFO L87 Difference]: Start difference. First operand 128 states and 170 transitions. Second operand has 8 states, 8 states have (on average 5.125) internal successors, (41), 8 states have internal predecessors, (41), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:37,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:20:37,979 INFO L93 Difference]: Finished difference Result 261 states and 350 transitions. [2025-01-09 17:20:37,979 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-09 17:20:37,979 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.125) internal successors, (41), 8 states have internal predecessors, (41), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 72 [2025-01-09 17:20:37,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:20:37,981 INFO L225 Difference]: With dead ends: 261 [2025-01-09 17:20:37,982 INFO L226 Difference]: Without dead ends: 140 [2025-01-09 17:20:37,983 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2025-01-09 17:20:37,983 INFO L435 NwaCegarLoop]: 66 mSDtfsCounter, 27 mSDsluCounter, 330 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 396 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 17:20:37,983 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 396 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 17:20:37,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2025-01-09 17:20:37,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 130. [2025-01-09 17:20:37,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 90 states have (on average 1.2666666666666666) internal successors, (114), 94 states have internal predecessors, (114), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2025-01-09 17:20:37,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 172 transitions. [2025-01-09 17:20:37,998 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 172 transitions. Word has length 72 [2025-01-09 17:20:37,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:20:37,999 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 172 transitions. [2025-01-09 17:20:37,999 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.125) internal successors, (41), 8 states have internal predecessors, (41), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 17:20:37,999 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 172 transitions. [2025-01-09 17:20:38,000 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-01-09 17:20:38,001 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:20:38,001 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:20:38,001 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-01-09 17:20:38,002 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:20:38,002 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:20:38,002 INFO L85 PathProgramCache]: Analyzing trace with hash -1588233316, now seen corresponding path program 1 times [2025-01-09 17:20:38,002 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:20:38,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1348061282] [2025-01-09 17:20:38,002 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:38,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:20:38,015 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:20:38,024 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:20:38,026 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:38,027 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:38,241 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-01-09 17:20:38,242 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:20:38,242 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1348061282] [2025-01-09 17:20:38,242 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1348061282] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:20:38,242 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [443613762] [2025-01-09 17:20:38,242 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:20:38,242 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:20:38,242 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:20:38,247 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:20:38,252 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-01-09 17:20:38,346 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:20:38,381 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:20:38,381 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:20:38,381 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:20:38,383 INFO L256 TraceCheckSpWp]: Trace formula consists of 325 conjuncts, 33 conjuncts are in the unsatisfiable core [2025-01-09 17:20:38,386 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:20:38,473 INFO L349 Elim1Store]: treesize reduction 66, result has 39.4 percent of original size [2025-01-09 17:20:38,474 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 76 treesize of output 128 [2025-01-09 17:20:38,479 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 16 treesize of output 15 [2025-01-09 17:20:38,496 INFO L173 IndexEqualityManager]: detected equality via solver [2025-01-09 17:20:38,496 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 16 treesize of output 1 [2025-01-09 17:20:38,520 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 69 treesize of output 26 [2025-01-09 17:20:39,102 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2025-01-09 17:20:39,102 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:20:39,102 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [443613762] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:20:39,102 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:20:39,102 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [6] total 16 [2025-01-09 17:20:39,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1568937143] [2025-01-09 17:20:39,102 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:20:39,103 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-01-09 17:20:39,103 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:20:39,103 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-01-09 17:20:39,103 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=202, Unknown=0, NotChecked=0, Total=240 [2025-01-09 17:20:39,103 INFO L87 Difference]: Start difference. First operand 130 states and 172 transitions. Second operand has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:20:43,107 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:20:47,139 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:20:51,168 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:20:55,225 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:20:59,235 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:03,532 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:03,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:21:03,721 INFO L93 Difference]: Finished difference Result 207 states and 277 transitions. [2025-01-09 17:21:03,722 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-01-09 17:21:03,722 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 73 [2025-01-09 17:21:03,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:21:03,723 INFO L225 Difference]: With dead ends: 207 [2025-01-09 17:21:03,723 INFO L226 Difference]: Without dead ends: 134 [2025-01-09 17:21:03,724 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 57 SyntacticMatches, 8 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=109, Invalid=541, Unknown=0, NotChecked=0, Total=650 [2025-01-09 17:21:03,724 INFO L435 NwaCegarLoop]: 64 mSDtfsCounter, 188 mSDsluCounter, 417 mSDsCounter, 0 mSdLazyCounter, 316 mSolverCounterSat, 54 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 24.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 481 SdHoareTripleChecker+Invalid, 376 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 316 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 24.4s IncrementalHoareTripleChecker+Time [2025-01-09 17:21:03,725 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [188 Valid, 481 Invalid, 376 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 316 Invalid, 6 Unknown, 0 Unchecked, 24.4s Time] [2025-01-09 17:21:03,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2025-01-09 17:21:03,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 132. [2025-01-09 17:21:03,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 92 states have (on average 1.2608695652173914) internal successors, (116), 96 states have internal predecessors, (116), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2025-01-09 17:21:03,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 174 transitions. [2025-01-09 17:21:03,736 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 174 transitions. Word has length 73 [2025-01-09 17:21:03,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:21:03,736 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 174 transitions. [2025-01-09 17:21:03,736 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:21:03,736 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 174 transitions. [2025-01-09 17:21:03,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-01-09 17:21:03,737 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:21:03,737 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:21:03,746 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-01-09 17:21:03,941 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2025-01-09 17:21:03,941 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:21:03,942 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:21:03,942 INFO L85 PathProgramCache]: Analyzing trace with hash 980022358, now seen corresponding path program 1 times [2025-01-09 17:21:03,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:21:03,942 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2062416406] [2025-01-09 17:21:03,942 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:03,942 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:21:03,957 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:21:03,969 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:21:03,969 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:03,970 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:04,105 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2025-01-09 17:21:04,105 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:21:04,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2062416406] [2025-01-09 17:21:04,106 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2062416406] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:21:04,106 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [899367225] [2025-01-09 17:21:04,107 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:04,107 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:04,107 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:21:04,110 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:21:04,111 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-01-09 17:21:04,203 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:21:04,232 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:21:04,232 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:04,232 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:04,234 INFO L256 TraceCheckSpWp]: Trace formula consists of 310 conjuncts, 46 conjuncts are in the unsatisfiable core [2025-01-09 17:21:04,238 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:21:04,263 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 18 treesize of output 19 [2025-01-09 17:21:04,274 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 24 treesize of output 9 [2025-01-09 17:21:04,310 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:04,312 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:04,313 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:04,318 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 57 treesize of output 25 [2025-01-09 17:21:04,325 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:04,326 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:04,327 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 35 [2025-01-09 17:21:05,132 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 44 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-01-09 17:21:05,132 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:21:05,132 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [899367225] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:21:05,132 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:21:05,132 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [6] total 15 [2025-01-09 17:21:05,132 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [790307354] [2025-01-09 17:21:05,132 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:21:05,132 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 17:21:05,132 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:21:05,133 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 17:21:05,133 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-01-09 17:21:05,133 INFO L87 Difference]: Start difference. First operand 132 states and 174 transitions. Second operand has 11 states, 10 states have (on average 5.5) internal successors, (55), 11 states have internal predecessors, (55), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:21:05,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:21:05,753 INFO L93 Difference]: Finished difference Result 214 states and 285 transitions. [2025-01-09 17:21:05,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-01-09 17:21:05,754 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 5.5) internal successors, (55), 11 states have internal predecessors, (55), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 73 [2025-01-09 17:21:05,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:21:05,755 INFO L225 Difference]: With dead ends: 214 [2025-01-09 17:21:05,756 INFO L226 Difference]: Without dead ends: 136 [2025-01-09 17:21:05,757 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 61 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2025-01-09 17:21:05,757 INFO L435 NwaCegarLoop]: 61 mSDtfsCounter, 87 mSDsluCounter, 324 mSDsCounter, 0 mSdLazyCounter, 274 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 385 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 274 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-01-09 17:21:05,758 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 385 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 274 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-01-09 17:21:05,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2025-01-09 17:21:05,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 134. [2025-01-09 17:21:05,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 94 states have (on average 1.2553191489361701) internal successors, (118), 98 states have internal predecessors, (118), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2025-01-09 17:21:05,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 176 transitions. [2025-01-09 17:21:05,776 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 176 transitions. Word has length 73 [2025-01-09 17:21:05,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:21:05,777 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 176 transitions. [2025-01-09 17:21:05,777 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 5.5) internal successors, (55), 11 states have internal predecessors, (55), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:21:05,777 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 176 transitions. [2025-01-09 17:21:05,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-01-09 17:21:05,778 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:21:05,778 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:21:05,784 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-01-09 17:21:05,978 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:05,978 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:21:05,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:21:05,979 INFO L85 PathProgramCache]: Analyzing trace with hash -532470128, now seen corresponding path program 1 times [2025-01-09 17:21:05,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:21:05,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [748248813] [2025-01-09 17:21:05,979 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:05,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:21:06,019 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:21:06,023 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:21:06,024 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:06,024 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:06,356 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-01-09 17:21:06,356 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:21:06,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [748248813] [2025-01-09 17:21:06,357 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [748248813] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:21:06,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1882002344] [2025-01-09 17:21:06,357 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:06,357 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:06,357 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:21:06,361 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:21:06,362 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-01-09 17:21:06,453 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:21:06,500 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:21:06,501 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:06,501 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:06,502 INFO L256 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 39 conjuncts are in the unsatisfiable core [2025-01-09 17:21:06,504 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:21:06,588 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 [2025-01-09 17:21:07,307 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2025-01-09 17:21:07,307 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:21:07,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1882002344] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:21:07,307 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:21:07,307 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [9] total 19 [2025-01-09 17:21:07,307 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1762037379] [2025-01-09 17:21:07,307 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:21:07,308 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-01-09 17:21:07,308 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:21:07,308 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-01-09 17:21:07,308 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2025-01-09 17:21:07,308 INFO L87 Difference]: Start difference. First operand 134 states and 176 transitions. Second operand has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:21:11,316 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:15,367 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:19,379 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:23,403 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:27,463 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:31,472 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Real, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:31,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:21:31,975 INFO L93 Difference]: Finished difference Result 222 states and 294 transitions. [2025-01-09 17:21:31,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-01-09 17:21:31,976 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 73 [2025-01-09 17:21:31,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:21:31,977 INFO L225 Difference]: With dead ends: 222 [2025-01-09 17:21:31,978 INFO L226 Difference]: Without dead ends: 138 [2025-01-09 17:21:31,978 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 57 SyntacticMatches, 8 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=131, Invalid=681, Unknown=0, NotChecked=0, Total=812 [2025-01-09 17:21:31,979 INFO L435 NwaCegarLoop]: 66 mSDtfsCounter, 211 mSDsluCounter, 375 mSDsCounter, 0 mSdLazyCounter, 285 mSolverCounterSat, 60 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 24.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 211 SdHoareTripleChecker+Valid, 441 SdHoareTripleChecker+Invalid, 351 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 285 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 24.4s IncrementalHoareTripleChecker+Time [2025-01-09 17:21:31,979 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [211 Valid, 441 Invalid, 351 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 285 Invalid, 6 Unknown, 0 Unchecked, 24.4s Time] [2025-01-09 17:21:31,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2025-01-09 17:21:32,003 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 136. [2025-01-09 17:21:32,003 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 96 states have (on average 1.25) internal successors, (120), 100 states have internal predecessors, (120), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2025-01-09 17:21:32,004 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 178 transitions. [2025-01-09 17:21:32,006 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 178 transitions. Word has length 73 [2025-01-09 17:21:32,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:21:32,006 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 178 transitions. [2025-01-09 17:21:32,006 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 17:21:32,006 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 178 transitions. [2025-01-09 17:21:32,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-01-09 17:21:32,007 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:21:32,007 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:21:32,017 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-01-09 17:21:32,207 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-01-09 17:21:32,208 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:21:32,209 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:21:32,209 INFO L85 PathProgramCache]: Analyzing trace with hash 1956164170, now seen corresponding path program 1 times [2025-01-09 17:21:32,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:21:32,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1966530418] [2025-01-09 17:21:32,209 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:32,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:21:32,223 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:21:32,226 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:21:32,227 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:32,227 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:32,297 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-01-09 17:21:32,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:21:32,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1966530418] [2025-01-09 17:21:32,297 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1966530418] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:21:32,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [979661472] [2025-01-09 17:21:32,297 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:32,297 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:32,297 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:21:32,300 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:21:32,307 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-01-09 17:21:32,403 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-01-09 17:21:32,426 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-01-09 17:21:32,426 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:32,426 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:32,427 INFO L256 TraceCheckSpWp]: Trace formula consists of 280 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-01-09 17:21:32,428 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:21:32,495 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2025-01-09 17:21:32,495 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:21:32,495 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [979661472] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:21:32,495 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:21:32,496 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [5] total 9 [2025-01-09 17:21:32,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1367907363] [2025-01-09 17:21:32,496 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:21:32,496 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-01-09 17:21:32,496 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:21:32,496 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-01-09 17:21:32,496 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-01-09 17:21:32,496 INFO L87 Difference]: Start difference. First operand 136 states and 178 transitions. Second operand has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 2 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-01-09 17:21:32,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:21:32,589 INFO L93 Difference]: Finished difference Result 293 states and 391 transitions. [2025-01-09 17:21:32,590 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-01-09 17:21:32,590 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 2 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 73 [2025-01-09 17:21:32,590 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:21:32,591 INFO L225 Difference]: With dead ends: 293 [2025-01-09 17:21:32,591 INFO L226 Difference]: Without dead ends: 172 [2025-01-09 17:21:32,591 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 70 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2025-01-09 17:21:32,592 INFO L435 NwaCegarLoop]: 80 mSDtfsCounter, 103 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 17:21:32,592 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [103 Valid, 208 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 17:21:32,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2025-01-09 17:21:32,609 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 172. [2025-01-09 17:21:32,609 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 127 states have (on average 1.2677165354330708) internal successors, (161), 134 states have internal predecessors, (161), 28 states have call successors, (28), 11 states have call predecessors, (28), 16 states have return successors, (38), 26 states have call predecessors, (38), 26 states have call successors, (38) [2025-01-09 17:21:32,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 227 transitions. [2025-01-09 17:21:32,611 INFO L78 Accepts]: Start accepts. Automaton has 172 states and 227 transitions. Word has length 73 [2025-01-09 17:21:32,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:21:32,612 INFO L471 AbstractCegarLoop]: Abstraction has 172 states and 227 transitions. [2025-01-09 17:21:32,612 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 2 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-01-09 17:21:32,612 INFO L276 IsEmpty]: Start isEmpty. Operand 172 states and 227 transitions. [2025-01-09 17:21:32,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-01-09 17:21:32,616 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:21:32,616 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:21:32,631 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-01-09 17:21:32,816 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:32,817 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:21:32,817 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:21:32,817 INFO L85 PathProgramCache]: Analyzing trace with hash 425263750, now seen corresponding path program 1 times [2025-01-09 17:21:32,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:21:32,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [531908863] [2025-01-09 17:21:32,818 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:32,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:21:32,836 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-01-09 17:21:32,845 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-01-09 17:21:32,846 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:32,846 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:32,975 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-01-09 17:21:32,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:21:32,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [531908863] [2025-01-09 17:21:32,976 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [531908863] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:21:32,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1919461138] [2025-01-09 17:21:32,976 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:32,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:32,976 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:21:32,979 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:21:32,981 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-01-09 17:21:33,087 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-01-09 17:21:33,122 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-01-09 17:21:33,122 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:33,122 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:33,124 INFO L256 TraceCheckSpWp]: Trace formula consists of 385 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-01-09 17:21:33,128 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:21:33,166 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 18 treesize of output 19 [2025-01-09 17:21:33,177 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 24 treesize of output 9 [2025-01-09 17:21:33,211 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,212 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 28 [2025-01-09 17:21:33,216 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,217 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,218 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 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 40 [2025-01-09 17:21:33,222 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,223 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 20 [2025-01-09 17:21:33,229 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,230 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 13 [2025-01-09 17:21:33,255 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,257 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,258 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 47 treesize of output 42 [2025-01-09 17:21:33,261 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 0 case distinctions, treesize of input 31 treesize of output 25 [2025-01-09 17:21:33,266 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,268 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:33,269 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 35 [2025-01-09 17:21:33,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 13 [2025-01-09 17:21:33,804 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 44 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-01-09 17:21:33,804 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 17:21:34,110 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse1 (+ |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.offset| 24)) (.cse2 (+ |c_ULTIMATE.start_aws_linked_list_end_harness_~#list~0#1.offset| 16))) (and (forall ((|v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15| Int)) (or (< |c_#StackHeapBarrier| (+ |v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15| 1)) (forall ((v_ArrVal_718 (Array Int Int)) (v_ArrVal_714 Int)) (= (select (select (let ((.cse0 (store (store |c_#memory_$Pointer$#2.base| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base| (store (select |c_#memory_$Pointer$#2.base| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base|) |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.offset| v_ArrVal_714)) |v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15| v_ArrVal_718))) (store .cse0 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base| (store (select .cse0 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base|) .cse1 |v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15|))) |c_ULTIMATE.start_aws_linked_list_end_harness_~#list~0#1.base|) .cse2) 0)))) (forall ((|v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15| Int)) (or (< |c_#StackHeapBarrier| (+ |v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15| 1)) (forall ((v_ArrVal_712 Int) (v_subst_1 Int) (v_ArrVal_720 (Array Int Int))) (= (select (select (let ((.cse3 (store (store |c_#memory_$Pointer$#2.offset| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base| (store (select |c_#memory_$Pointer$#2.offset| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base|) |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.offset| v_ArrVal_712)) |v_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base_15| v_ArrVal_720))) (store .cse3 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base| (store (select .cse3 |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base|) .cse1 v_subst_1))) |c_ULTIMATE.start_aws_linked_list_end_harness_~#list~0#1.base|) .cse2) 0)))))) is different from false [2025-01-09 17:21:34,122 INFO L173 IndexEqualityManager]: detected equality via solver [2025-01-09 17:21:34,122 INFO L173 IndexEqualityManager]: detected equality via solver [2025-01-09 17:21:34,179 INFO L349 Elim1Store]: treesize reduction 86, result has 45.2 percent of original size [2025-01-09 17:21:34,180 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 171 treesize of output 200 [2025-01-09 17:21:34,188 INFO L173 IndexEqualityManager]: detected equality via solver [2025-01-09 17:21:34,189 INFO L173 IndexEqualityManager]: detected equality via solver [2025-01-09 17:21:34,246 INFO L349 Elim1Store]: treesize reduction 86, result has 45.2 percent of original size [2025-01-09 17:21:34,247 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 327 treesize of output 314 [2025-01-09 17:21:34,262 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:34,263 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 260 treesize of output 258 [2025-01-09 17:21:34,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 217 treesize of output 205 [2025-01-09 17:21:34,285 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:34,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 296 treesize of output 296 [2025-01-09 17:21:34,296 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 263 treesize of output 251 [2025-01-09 17:21:34,351 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 8 treesize of output 4 [2025-01-09 17:21:34,785 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:34,786 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 103 treesize of output 105 [2025-01-09 17:21:34,831 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:34,832 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 32 [2025-01-09 17:21:34,876 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 1 not checked. [2025-01-09 17:21:34,876 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1919461138] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 17:21:34,876 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 17:21:34,876 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 11, 10] total 23 [2025-01-09 17:21:34,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [598048734] [2025-01-09 17:21:34,876 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 17:21:34,877 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-01-09 17:21:34,877 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:21:34,877 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-01-09 17:21:34,877 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=388, Unknown=15, NotChecked=40, Total=506 [2025-01-09 17:21:34,878 INFO L87 Difference]: Start difference. First operand 172 states and 227 transitions. Second operand has 23 states, 20 states have (on average 4.9) internal successors, (98), 22 states have internal predecessors, (98), 9 states have call successors, (22), 3 states have call predecessors, (22), 7 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2025-01-09 17:21:36,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:21:36,050 INFO L93 Difference]: Finished difference Result 263 states and 350 transitions. [2025-01-09 17:21:36,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-01-09 17:21:36,051 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 20 states have (on average 4.9) internal successors, (98), 22 states have internal predecessors, (98), 9 states have call successors, (22), 3 states have call predecessors, (22), 7 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 74 [2025-01-09 17:21:36,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:21:36,052 INFO L225 Difference]: With dead ends: 263 [2025-01-09 17:21:36,052 INFO L226 Difference]: Without dead ends: 180 [2025-01-09 17:21:36,052 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 127 SyntacticMatches, 5 SemanticMatches, 32 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=133, Invalid=908, Unknown=19, NotChecked=62, Total=1122 [2025-01-09 17:21:36,053 INFO L435 NwaCegarLoop]: 105 mSDtfsCounter, 64 mSDsluCounter, 1211 mSDsCounter, 0 mSdLazyCounter, 789 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 1316 SdHoareTripleChecker+Invalid, 963 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 789 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 134 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-01-09 17:21:36,053 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 1316 Invalid, 963 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 789 Invalid, 0 Unknown, 134 Unchecked, 0.8s Time] [2025-01-09 17:21:36,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2025-01-09 17:21:36,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 178. [2025-01-09 17:21:36,086 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 132 states have (on average 1.2575757575757576) internal successors, (166), 139 states have internal predecessors, (166), 28 states have call successors, (28), 12 states have call predecessors, (28), 17 states have return successors, (37), 26 states have call predecessors, (37), 26 states have call successors, (37) [2025-01-09 17:21:36,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 231 transitions. [2025-01-09 17:21:36,087 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 231 transitions. Word has length 74 [2025-01-09 17:21:36,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:21:36,087 INFO L471 AbstractCegarLoop]: Abstraction has 178 states and 231 transitions. [2025-01-09 17:21:36,087 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 20 states have (on average 4.9) internal successors, (98), 22 states have internal predecessors, (98), 9 states have call successors, (22), 3 states have call predecessors, (22), 7 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2025-01-09 17:21:36,087 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 231 transitions. [2025-01-09 17:21:36,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2025-01-09 17:21:36,088 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:21:36,088 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:21:36,106 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-01-09 17:21:36,289 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:36,289 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:21:36,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:21:36,290 INFO L85 PathProgramCache]: Analyzing trace with hash -1004376704, now seen corresponding path program 1 times [2025-01-09 17:21:36,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:21:36,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [136690191] [2025-01-09 17:21:36,290 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:36,290 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:21:36,308 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 86 statements into 1 equivalence classes. [2025-01-09 17:21:36,315 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 86 of 86 statements. [2025-01-09 17:21:36,316 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:36,316 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:36,382 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-01-09 17:21:36,382 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:21:36,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [136690191] [2025-01-09 17:21:36,382 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [136690191] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:21:36,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1087118346] [2025-01-09 17:21:36,382 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:36,382 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:36,382 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:21:36,385 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:21:36,388 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-01-09 17:21:36,489 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 86 statements into 1 equivalence classes. [2025-01-09 17:21:36,519 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 86 of 86 statements. [2025-01-09 17:21:36,519 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:36,519 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:36,520 INFO L256 TraceCheckSpWp]: Trace formula consists of 354 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-09 17:21:36,521 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:21:36,580 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 40 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-09 17:21:36,580 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 17:21:36,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1087118346] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 17:21:36,580 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 17:21:36,580 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [6] total 11 [2025-01-09 17:21:36,580 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535827978] [2025-01-09 17:21:36,580 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 17:21:36,580 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-01-09 17:21:36,581 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:21:36,581 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-01-09 17:21:36,581 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-01-09 17:21:36,581 INFO L87 Difference]: Start difference. First operand 178 states and 231 transitions. Second operand has 7 states, 6 states have (on average 10.5) internal successors, (63), 7 states have internal predecessors, (63), 4 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 4 states have call successors, (9) [2025-01-09 17:21:36,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 17:21:36,675 INFO L93 Difference]: Finished difference Result 326 states and 419 transitions. [2025-01-09 17:21:36,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-09 17:21:36,675 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 10.5) internal successors, (63), 7 states have internal predecessors, (63), 4 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 4 states have call successors, (9) Word has length 86 [2025-01-09 17:21:36,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 17:21:36,676 INFO L225 Difference]: With dead ends: 326 [2025-01-09 17:21:36,676 INFO L226 Difference]: Without dead ends: 127 [2025-01-09 17:21:36,677 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2025-01-09 17:21:36,677 INFO L435 NwaCegarLoop]: 79 mSDtfsCounter, 106 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 17:21:36,678 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 282 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 17:21:36,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2025-01-09 17:21:36,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2025-01-09 17:21:36,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 89 states have (on average 1.202247191011236) internal successors, (107), 92 states have internal predecessors, (107), 25 states have call successors, (25), 11 states have call predecessors, (25), 12 states have return successors, (26), 23 states have call predecessors, (26), 23 states have call successors, (26) [2025-01-09 17:21:36,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 158 transitions. [2025-01-09 17:21:36,689 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 158 transitions. Word has length 86 [2025-01-09 17:21:36,689 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 17:21:36,689 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 158 transitions. [2025-01-09 17:21:36,689 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 10.5) internal successors, (63), 7 states have internal predecessors, (63), 4 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 4 states have call successors, (9) [2025-01-09 17:21:36,690 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 158 transitions. [2025-01-09 17:21:36,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-01-09 17:21:36,690 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 17:21:36,690 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2025-01-09 17:21:36,697 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-01-09 17:21:36,891 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:36,891 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 17:21:36,891 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 17:21:36,891 INFO L85 PathProgramCache]: Analyzing trace with hash -2091433240, now seen corresponding path program 1 times [2025-01-09 17:21:36,891 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 17:21:36,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1461263402] [2025-01-09 17:21:36,892 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:36,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 17:21:36,908 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-01-09 17:21:36,918 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-01-09 17:21:36,918 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:36,918 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:37,061 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-01-09 17:21:37,061 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 17:21:37,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1461263402] [2025-01-09 17:21:37,061 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1461263402] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 17:21:37,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1086555941] [2025-01-09 17:21:37,061 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 17:21:37,062 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 17:21:37,062 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 17:21:37,063 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 17:21:37,066 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-01-09 17:21:37,178 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 87 statements into 1 equivalence classes. [2025-01-09 17:21:37,221 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 87 of 87 statements. [2025-01-09 17:21:37,222 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 17:21:37,222 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 17:21:37,225 INFO L256 TraceCheckSpWp]: Trace formula consists of 429 conjuncts, 100 conjuncts are in the unsatisfiable core [2025-01-09 17:21:37,229 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 17:21:37,291 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 16 treesize of output 16 [2025-01-09 17:21:37,294 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:37,294 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 11 [2025-01-09 17:21:37,299 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 16 treesize of output 16 [2025-01-09 17:21:37,303 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:37,303 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 11 [2025-01-09 17:21:37,343 INFO L349 Elim1Store]: treesize reduction 38, result has 22.4 percent of original size [2025-01-09 17:21:37,343 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 95 treesize of output 101 [2025-01-09 17:21:37,346 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:37,349 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:37,350 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 21 [2025-01-09 17:21:37,351 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 18 [2025-01-09 17:21:37,358 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 72 treesize of output 58 [2025-01-09 17:21:42,198 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 31 proven. 15 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-01-09 17:21:42,199 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 17:21:43,533 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:43,533 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 1 case distinctions, treesize of input 165 treesize of output 126 [2025-01-09 17:21:43,544 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:43,544 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 1 case distinctions, treesize of input 161 treesize of output 154 [2025-01-09 17:21:43,583 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:43,584 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 1073 treesize of output 927 [2025-01-09 17:21:43,614 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 561 treesize of output 545 [2025-01-09 17:21:43,657 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:43,657 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 848 treesize of output 854 [2025-01-09 17:21:43,673 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 683 treesize of output 675 [2025-01-09 17:21:43,690 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:43,690 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 703 treesize of output 679 [2025-01-09 17:21:43,946 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 6 treesize of output 4 [2025-01-09 17:21:44,091 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 5 treesize of output 3 [2025-01-09 17:21:44,111 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:44,112 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 199 treesize of output 201 [2025-01-09 17:21:44,377 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:44,377 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 168 treesize of output 170 [2025-01-09 17:21:44,565 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 8 treesize of output 4 [2025-01-09 17:21:44,641 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 [2025-01-09 17:21:44,658 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-09 17:21:44,669 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 52 [2025-01-09 17:21:44,774 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 17:21:44,774 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 218 treesize of output 196 [2025-01-09 17:21:45,261 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 12 proven. 21 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-01-09 17:21:45,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1086555941] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 17:21:45,262 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 17:21:45,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 29, 20] total 51 [2025-01-09 17:21:45,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [360109231] [2025-01-09 17:21:45,262 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 17:21:45,262 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2025-01-09 17:21:45,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 17:21:45,263 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2025-01-09 17:21:45,264 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=202, Invalid=2262, Unknown=86, NotChecked=0, Total=2550 [2025-01-09 17:21:45,264 INFO L87 Difference]: Start difference. First operand 127 states and 158 transitions. Second operand has 51 states, 47 states have (on average 3.0851063829787235) internal successors, (145), 44 states have internal predecessors, (145), 15 states have call successors, (27), 7 states have call predecessors, (27), 13 states have return successors, (26), 13 states have call predecessors, (26), 15 states have call successors, (26) [2025-01-09 17:21:54,247 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:21:58,341 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 17:22:05,548 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0]