./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c --full-output --architecture 32bit -------------------------------------------------------------------------------- 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/recursified_nla-digbench/recursified_dijkstra-u.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-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 32bit --witnessprinter.graph.data.programhash 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 04:10:55,721 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 04:10:55,792 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-01-09 04:10:55,799 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 04:10:55,802 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 04:10:55,826 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 04:10:55,827 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 04:10:55,828 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 04:10:55,828 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 04:10:55,828 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 04:10:55,829 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 04:10:55,829 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 04:10:55,829 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 04:10:55,829 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 04:10:55,830 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:10:55,830 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:10:55,832 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:10:55,832 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 04:10:55,832 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:10:55,832 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:10:55,832 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:10:55,833 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:10:55,833 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 04:10:55,833 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 04:10:55,833 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 04:10:55,833 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 04:10:55,833 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 04:10:55,833 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 04:10:55,834 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 04:10:55,834 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 04:10:55,834 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 04:10:55,834 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 04:10:55,834 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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 [2025-01-09 04:10:56,125 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 04:10:56,133 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 04:10:56,136 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 04:10:56,137 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 04:10:56,137 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 04:10:56,139 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2025-01-09 04:10:57,402 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/514cd87c2/02bc9fccdd434db588f1a08aa1f524af/FLAGbe898194e [2025-01-09 04:10:57,657 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 04:10:57,658 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2025-01-09 04:10:57,668 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/514cd87c2/02bc9fccdd434db588f1a08aa1f524af/FLAGbe898194e [2025-01-09 04:10:57,968 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/514cd87c2/02bc9fccdd434db588f1a08aa1f524af [2025-01-09 04:10:57,970 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 04:10:57,971 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 04:10:57,972 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 04:10:57,972 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 04:10:57,975 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 04:10:57,976 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:10:57" (1/1) ... [2025-01-09 04:10:57,977 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@124f9b14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:57, skipping insertion in model container [2025-01-09 04:10:57,977 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:10:57" (1/1) ... [2025-01-09 04:10:57,993 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 04:10:58,104 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/recursified_nla-digbench/recursified_dijkstra-u.c[1076,1089] [2025-01-09 04:10:58,132 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:10:58,145 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 04:10:58,153 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/recursified_nla-digbench/recursified_dijkstra-u.c[1076,1089] [2025-01-09 04:10:58,191 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:10:58,206 INFO L204 MainTranslator]: Completed translation [2025-01-09 04:10:58,207 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58 WrapperNode [2025-01-09 04:10:58,207 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 04:10:58,208 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 04:10:58,208 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 04:10:58,208 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 04:10:58,213 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,223 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,251 INFO L138 Inliner]: procedures = 17, calls = 173, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 114 [2025-01-09 04:10:58,252 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 04:10:58,252 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 04:10:58,252 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 04:10:58,252 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 04:10:58,262 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,263 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,270 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,300 INFO L175 MemorySlicer]: Split 139 memory accesses to 6 slices as follows [2, 35, 22, 21, 29, 30]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 3, 2, 1, 3, 2]. [2025-01-09 04:10:58,301 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,301 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,314 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,319 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,325 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,327 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,332 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,335 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 04:10:58,336 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 04:10:58,336 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 04:10:58,336 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 04:10:58,337 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (1/1) ... [2025-01-09 04:10:58,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:10:58,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:10:58,370 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 04:10:58,377 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 04:10:58,399 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 04:10:58,399 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_33_0 [2025-01-09 04:10:58,399 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_33_0 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-01-09 04:10:58,400 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-01-09 04:10:58,401 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_53_0 [2025-01-09 04:10:58,401 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_53_0 [2025-01-09 04:10:58,402 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 04:10:58,402 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 04:10:58,402 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-01-09 04:10:58,402 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-01-09 04:10:58,403 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-01-09 04:10:58,403 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-01-09 04:10:58,403 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-01-09 04:10:58,403 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-01-09 04:10:58,403 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 04:10:58,403 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 04:10:58,403 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-01-09 04:10:58,537 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 04:10:58,538 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 04:10:58,797 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-01-09 04:10:58,797 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 04:10:58,806 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 04:10:58,807 INFO L312 CfgBuilder]: Removed 2 assume(true) statements. [2025-01-09 04:10:58,807 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:10:58 BoogieIcfgContainer [2025-01-09 04:10:58,807 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 04:10:58,810 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 04:10:58,810 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 04:10:58,813 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 04:10:58,814 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 04:10:57" (1/3) ... [2025-01-09 04:10:58,814 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63454c01 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:10:58, skipping insertion in model container [2025-01-09 04:10:58,814 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:10:58" (2/3) ... [2025-01-09 04:10:58,814 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63454c01 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:10:58, skipping insertion in model container [2025-01-09 04:10:58,816 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:10:58" (3/3) ... [2025-01-09 04:10:58,818 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra-u.c [2025-01-09 04:10:58,830 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 04:10:58,832 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_dijkstra-u.c that has 4 procedures, 47 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-01-09 04:10:58,871 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 04:10:58,879 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;@401ff16d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 04:10:58,879 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 04:10:58,883 INFO L276 IsEmpty]: Start isEmpty. Operand has 47 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 32 states have internal predecessors, (37), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-01-09 04:10:58,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2025-01-09 04:10:58,888 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:10:58,888 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:10:58,889 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:10:58,892 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:10:58,893 INFO L85 PathProgramCache]: Analyzing trace with hash 2024161958, now seen corresponding path program 1 times [2025-01-09 04:10:58,899 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:10:58,900 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1600067484] [2025-01-09 04:10:58,900 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:10:58,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:10:58,975 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-01-09 04:10:59,002 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-01-09 04:10:59,004 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:10:59,005 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:10:59,088 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:10:59,088 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:10:59,088 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1600067484] [2025-01-09 04:10:59,089 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1600067484] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:10:59,089 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:10:59,089 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-01-09 04:10:59,091 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1495877935] [2025-01-09 04:10:59,091 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:10:59,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-01-09 04:10:59,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:10:59,104 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-01-09 04:10:59,105 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 04:10:59,106 INFO L87 Difference]: Start difference. First operand has 47 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 32 states have internal predecessors, (37), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 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 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-01-09 04:10:59,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:10:59,122 INFO L93 Difference]: Finished difference Result 91 states and 135 transitions. [2025-01-09 04:10:59,123 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-01-09 04:10:59,124 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2025-01-09 04:10:59,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:10:59,129 INFO L225 Difference]: With dead ends: 91 [2025-01-09 04:10:59,129 INFO L226 Difference]: Without dead ends: 43 [2025-01-09 04:10:59,132 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 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 04:10:59,137 INFO L435 NwaCegarLoop]: 59 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, 59 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 04:10:59,138 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 04:10:59,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-01-09 04:10:59,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2025-01-09 04:10:59,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 29 states have internal predecessors, (30), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-01-09 04:10:59,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2025-01-09 04:10:59,166 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 16 [2025-01-09 04:10:59,166 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:10:59,166 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2025-01-09 04:10:59,167 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-01-09 04:10:59,167 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2025-01-09 04:10:59,168 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2025-01-09 04:10:59,168 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:10:59,168 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:10:59,168 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-09 04:10:59,168 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:10:59,169 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:10:59,169 INFO L85 PathProgramCache]: Analyzing trace with hash 715108188, now seen corresponding path program 1 times [2025-01-09 04:10:59,169 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:10:59,169 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649308175] [2025-01-09 04:10:59,169 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:10:59,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:10:59,197 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-01-09 04:10:59,246 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-01-09 04:10:59,247 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:10:59,247 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:00,531 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:11:00,532 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:00,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1649308175] [2025-01-09 04:11:00,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1649308175] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:11:00,533 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:11:00,533 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2025-01-09 04:11:00,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1053356407] [2025-01-09 04:11:00,533 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:11:00,534 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-01-09 04:11:00,535 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:00,536 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-01-09 04:11:00,536 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2025-01-09 04:11:00,536 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-01-09 04:11:01,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:01,957 INFO L93 Difference]: Finished difference Result 76 states and 99 transitions. [2025-01-09 04:11:01,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-01-09 04:11:01,958 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 17 [2025-01-09 04:11:01,958 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:01,960 INFO L225 Difference]: With dead ends: 76 [2025-01-09 04:11:01,960 INFO L226 Difference]: Without dead ends: 74 [2025-01-09 04:11:01,960 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2025-01-09 04:11:01,961 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 55 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 425 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 467 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 425 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:01,961 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 141 Invalid, 467 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 425 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-01-09 04:11:01,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-01-09 04:11:01,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 69. [2025-01-09 04:11:01,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 41 states have (on average 1.1219512195121952) internal successors, (46), 44 states have internal predecessors, (46), 20 states have call successors, (20), 5 states have call predecessors, (20), 7 states have return successors, (24), 19 states have call predecessors, (24), 19 states have call successors, (24) [2025-01-09 04:11:01,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 90 transitions. [2025-01-09 04:11:01,980 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 90 transitions. Word has length 17 [2025-01-09 04:11:01,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:01,980 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 90 transitions. [2025-01-09 04:11:01,980 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-01-09 04:11:01,980 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 90 transitions. [2025-01-09 04:11:01,981 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-01-09 04:11:01,981 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:01,981 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:01,981 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-09 04:11:01,982 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:01,982 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:01,982 INFO L85 PathProgramCache]: Analyzing trace with hash 1913135784, now seen corresponding path program 1 times [2025-01-09 04:11:01,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:01,982 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1698925578] [2025-01-09 04:11:01,982 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:01,982 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:01,998 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-01-09 04:11:02,015 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-01-09 04:11:02,016 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:02,016 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:02,019 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [455284311] [2025-01-09 04:11:02,020 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:02,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:02,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:02,024 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 04:11:02,026 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 04:11:02,103 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-01-09 04:11:02,261 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-01-09 04:11:02,262 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:02,262 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:02,270 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 88 conjuncts are in the unsatisfiable core [2025-01-09 04:11:02,282 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:02,314 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:02,328 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:02,336 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:02,343 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:03,062 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:03,063 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 39 treesize of output 35 [2025-01-09 04:11:03,081 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:03,081 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 31 treesize of output 31 [2025-01-09 04:11:03,175 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:11:03,175 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:04,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:04,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1698925578] [2025-01-09 04:11:04,563 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:04,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [455284311] [2025-01-09 04:11:04,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [455284311] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:04,563 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:04,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2025-01-09 04:11:04,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1289127817] [2025-01-09 04:11:04,563 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:04,564 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-01-09 04:11:04,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:04,564 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-01-09 04:11:04,565 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=202, Unknown=0, NotChecked=0, Total=240 [2025-01-09 04:11:04,565 INFO L87 Difference]: Start difference. First operand 69 states and 90 transitions. Second operand has 14 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 04:11:06,210 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:06,210 INFO L93 Difference]: Finished difference Result 92 states and 113 transitions. [2025-01-09 04:11:06,211 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-01-09 04:11:06,211 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2025-01-09 04:11:06,211 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:06,212 INFO L225 Difference]: With dead ends: 92 [2025-01-09 04:11:06,212 INFO L226 Difference]: Without dead ends: 90 [2025-01-09 04:11:06,213 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 11 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 88 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=93, Invalid=459, Unknown=0, NotChecked=0, Total=552 [2025-01-09 04:11:06,214 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 55 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 423 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 467 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 423 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:06,214 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 177 Invalid, 467 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 423 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2025-01-09 04:11:06,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-01-09 04:11:06,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2025-01-09 04:11:06,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 54 states have (on average 1.1296296296296295) internal successors, (61), 57 states have internal predecessors, (61), 23 states have call successors, (23), 8 states have call predecessors, (23), 10 states have return successors, (26), 22 states have call predecessors, (26), 21 states have call successors, (26) [2025-01-09 04:11:06,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 110 transitions. [2025-01-09 04:11:06,232 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 110 transitions. Word has length 23 [2025-01-09 04:11:06,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:06,233 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 110 transitions. [2025-01-09 04:11:06,233 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 10 states have internal predecessors, (17), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 04:11:06,233 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 110 transitions. [2025-01-09 04:11:06,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-01-09 04:11:06,233 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:06,233 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:06,243 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 04:11:06,434 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:06,434 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:06,435 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:06,435 INFO L85 PathProgramCache]: Analyzing trace with hash -1510470269, now seen corresponding path program 1 times [2025-01-09 04:11:06,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:06,435 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051022922] [2025-01-09 04:11:06,435 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:06,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:06,445 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-01-09 04:11:06,465 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-01-09 04:11:06,465 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:06,465 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:07,715 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-01-09 04:11:07,716 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:07,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051022922] [2025-01-09 04:11:07,716 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1051022922] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:07,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1172063124] [2025-01-09 04:11:07,716 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:07,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:07,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:07,719 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 04:11:07,720 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 04:11:07,780 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-01-09 04:11:07,841 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-01-09 04:11:07,841 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:07,841 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:07,843 INFO L256 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 89 conjuncts are in the unsatisfiable core [2025-01-09 04:11:07,846 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:07,851 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:07,854 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:07,860 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:08,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2025-01-09 04:11:08,342 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:08,343 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 40 treesize of output 40 [2025-01-09 04:11:12,553 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 25 treesize of output 17 [2025-01-09 04:11:12,557 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 21 treesize of output 13 [2025-01-09 04:11:12,669 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:11:12,669 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:13,125 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 37 treesize of output 33 [2025-01-09 04:11:13,892 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1172063124] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:13,893 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 04:11:13,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 30 [2025-01-09 04:11:13,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1391789308] [2025-01-09 04:11:13,893 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:13,893 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-01-09 04:11:13,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:13,895 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-01-09 04:11:13,896 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=1210, Unknown=1, NotChecked=0, Total=1332 [2025-01-09 04:11:13,896 INFO L87 Difference]: Start difference. First operand 88 states and 110 transitions. Second operand has 30 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 21 states have internal predecessors, (29), 8 states have call successors, (8), 7 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-01-09 04:11:18,243 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:18,243 INFO L93 Difference]: Finished difference Result 174 states and 227 transitions. [2025-01-09 04:11:18,244 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-01-09 04:11:18,244 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 21 states have internal predecessors, (29), 8 states have call successors, (8), 7 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 23 [2025-01-09 04:11:18,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:18,247 INFO L225 Difference]: With dead ends: 174 [2025-01-09 04:11:18,247 INFO L226 Difference]: Without dead ends: 172 [2025-01-09 04:11:18,249 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 15 SyntacticMatches, 2 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 565 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=301, Invalid=2668, Unknown=1, NotChecked=0, Total=2970 [2025-01-09 04:11:18,249 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 161 mSDsluCounter, 275 mSDsCounter, 0 mSdLazyCounter, 1478 mSolverCounterSat, 138 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 175 SdHoareTripleChecker+Valid, 312 SdHoareTripleChecker+Invalid, 1616 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 138 IncrementalHoareTripleChecker+Valid, 1478 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:18,249 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [175 Valid, 312 Invalid, 1616 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [138 Valid, 1478 Invalid, 0 Unknown, 0 Unchecked, 3.2s Time] [2025-01-09 04:11:18,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2025-01-09 04:11:18,284 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 140. [2025-01-09 04:11:18,284 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 85 states have (on average 1.1294117647058823) internal successors, (96), 89 states have internal predecessors, (96), 39 states have call successors, (39), 12 states have call predecessors, (39), 15 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2025-01-09 04:11:18,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 180 transitions. [2025-01-09 04:11:18,288 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 180 transitions. Word has length 23 [2025-01-09 04:11:18,288 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:18,288 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 180 transitions. [2025-01-09 04:11:18,288 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 21 states have internal predecessors, (29), 8 states have call successors, (8), 7 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-01-09 04:11:18,288 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 180 transitions. [2025-01-09 04:11:18,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-01-09 04:11:18,289 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:18,289 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-01-09 04:11:18,299 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-01-09 04:11:18,489 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:18,489 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:18,490 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:18,490 INFO L85 PathProgramCache]: Analyzing trace with hash -1343310350, now seen corresponding path program 1 times [2025-01-09 04:11:18,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:18,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1669259646] [2025-01-09 04:11:18,490 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:18,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:18,500 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-09 04:11:18,531 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-09 04:11:18,531 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:18,531 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:18,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1109325532] [2025-01-09 04:11:18,533 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:18,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:18,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:18,535 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 04:11:18,538 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 04:11:18,606 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-09 04:11:18,651 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-09 04:11:18,651 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:18,651 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:18,655 INFO L256 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 95 conjuncts are in the unsatisfiable core [2025-01-09 04:11:18,660 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:18,666 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:18,672 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:18,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:18,685 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:18,692 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:19,058 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 11 [2025-01-09 04:11:19,063 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:11:19,133 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:11:19,133 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:19,855 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:19,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1669259646] [2025-01-09 04:11:19,855 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:19,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1109325532] [2025-01-09 04:11:19,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1109325532] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:19,855 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:19,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2025-01-09 04:11:19,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [90231182] [2025-01-09 04:11:19,855 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:19,856 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 04:11:19,856 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:19,856 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 04:11:19,856 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2025-01-09 04:11:19,856 INFO L87 Difference]: Start difference. First operand 140 states and 180 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-09 04:11:20,831 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:20,832 INFO L93 Difference]: Finished difference Result 148 states and 186 transitions. [2025-01-09 04:11:20,833 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 04:11:20,833 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2025-01-09 04:11:20,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:20,834 INFO L225 Difference]: With dead ends: 148 [2025-01-09 04:11:20,835 INFO L226 Difference]: Without dead ends: 146 [2025-01-09 04:11:20,835 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 18 SyntacticMatches, 6 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2025-01-09 04:11:20,835 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 45 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:20,836 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 197 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 297 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-01-09 04:11:20,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2025-01-09 04:11:20,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 144. [2025-01-09 04:11:20,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 88 states have (on average 1.125) internal successors, (99), 92 states have internal predecessors, (99), 39 states have call successors, (39), 13 states have call predecessors, (39), 16 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2025-01-09 04:11:20,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 183 transitions. [2025-01-09 04:11:20,878 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 183 transitions. Word has length 29 [2025-01-09 04:11:20,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:20,879 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 183 transitions. [2025-01-09 04:11:20,879 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-09 04:11:20,880 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 183 transitions. [2025-01-09 04:11:20,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-01-09 04:11:20,880 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:20,880 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-01-09 04:11:20,889 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 04:11:21,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:21,081 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:21,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:21,081 INFO L85 PathProgramCache]: Analyzing trace with hash -1540028529, now seen corresponding path program 1 times [2025-01-09 04:11:21,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:21,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642836511] [2025-01-09 04:11:21,082 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:21,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:21,090 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-09 04:11:21,102 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-09 04:11:21,103 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:21,103 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:21,104 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1681129164] [2025-01-09 04:11:21,104 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:21,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:21,105 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:21,107 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 04:11:21,110 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 04:11:21,196 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-09 04:11:21,388 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-09 04:11:21,389 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:21,389 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:21,390 INFO L256 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-01-09 04:11:21,393 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:21,398 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:21,402 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:21,408 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:21,591 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 11 [2025-01-09 04:11:21,594 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:11:21,599 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:11:21,639 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-01-09 04:11:21,639 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:22,126 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:22,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [642836511] [2025-01-09 04:11:22,127 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:22,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1681129164] [2025-01-09 04:11:22,127 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1681129164] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:22,127 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:22,127 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-01-09 04:11:22,127 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [991115262] [2025-01-09 04:11:22,127 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:22,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-01-09 04:11:22,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:22,128 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-01-09 04:11:22,128 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2025-01-09 04:11:22,128 INFO L87 Difference]: Start difference. First operand 144 states and 183 transitions. Second operand has 9 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 04:11:22,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:22,810 INFO L93 Difference]: Finished difference Result 159 states and 200 transitions. [2025-01-09 04:11:22,810 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 04:11:22,810 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 29 [2025-01-09 04:11:22,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:22,812 INFO L225 Difference]: With dead ends: 159 [2025-01-09 04:11:22,812 INFO L226 Difference]: Without dead ends: 157 [2025-01-09 04:11:22,813 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 20 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2025-01-09 04:11:22,813 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 54 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 223 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 223 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:22,814 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 193 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 223 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-01-09 04:11:22,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2025-01-09 04:11:22,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 148. [2025-01-09 04:11:22,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 91 states have (on average 1.120879120879121) internal successors, (102), 95 states have internal predecessors, (102), 39 states have call successors, (39), 14 states have call predecessors, (39), 17 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2025-01-09 04:11:22,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 186 transitions. [2025-01-09 04:11:22,849 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 186 transitions. Word has length 29 [2025-01-09 04:11:22,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:22,849 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 186 transitions. [2025-01-09 04:11:22,849 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 04:11:22,849 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 186 transitions. [2025-01-09 04:11:22,850 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-01-09 04:11:22,850 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:22,850 INFO L218 NwaCegarLoop]: trace histogram [4, 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] [2025-01-09 04:11:22,857 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 04:11:23,051 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,SelfDestructingSolverStorable5 [2025-01-09 04:11:23,051 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:23,051 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:23,051 INFO L85 PathProgramCache]: Analyzing trace with hash -345050438, now seen corresponding path program 1 times [2025-01-09 04:11:23,051 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:23,052 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1621840163] [2025-01-09 04:11:23,052 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:23,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:23,061 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-01-09 04:11:23,083 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-01-09 04:11:23,083 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:23,083 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:23,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [857733500] [2025-01-09 04:11:23,085 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:23,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:23,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:23,088 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 04:11:23,090 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 04:11:23,160 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-01-09 04:11:23,285 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-01-09 04:11:23,286 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:23,286 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:23,298 INFO L256 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 117 conjuncts are in the unsatisfiable core [2025-01-09 04:11:23,304 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:23,318 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:23,335 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:23,349 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:23,401 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:23,414 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:23,926 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 40 treesize of output 20 [2025-01-09 04:11:23,934 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 36 treesize of output 16 [2025-01-09 04:11:24,073 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-09 04:11:24,074 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:29,358 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:29,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1621840163] [2025-01-09 04:11:29,358 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:29,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [857733500] [2025-01-09 04:11:29,358 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [857733500] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:29,358 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:29,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2025-01-09 04:11:29,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1767772097] [2025-01-09 04:11:29,358 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:29,359 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 04:11:29,359 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:29,359 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 04:11:29,359 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2025-01-09 04:11:29,359 INFO L87 Difference]: Start difference. First operand 148 states and 186 transitions. Second operand has 10 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:11:30,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:30,409 INFO L93 Difference]: Finished difference Result 156 states and 192 transitions. [2025-01-09 04:11:30,409 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 04:11:30,410 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2025-01-09 04:11:30,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:30,411 INFO L225 Difference]: With dead ends: 156 [2025-01-09 04:11:30,411 INFO L226 Difference]: Without dead ends: 154 [2025-01-09 04:11:30,411 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 22 SyntacticMatches, 8 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2025-01-09 04:11:30,412 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 44 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 299 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 299 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:30,412 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 196 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 299 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-01-09 04:11:30,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2025-01-09 04:11:30,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 152. [2025-01-09 04:11:30,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 94 states have (on average 1.1170212765957446) internal successors, (105), 98 states have internal predecessors, (105), 39 states have call successors, (39), 15 states have call predecessors, (39), 18 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2025-01-09 04:11:30,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 189 transitions. [2025-01-09 04:11:30,445 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 189 transitions. Word has length 35 [2025-01-09 04:11:30,445 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:30,445 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 189 transitions. [2025-01-09 04:11:30,445 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:11:30,445 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 189 transitions. [2025-01-09 04:11:30,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-01-09 04:11:30,446 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:30,446 INFO L218 NwaCegarLoop]: trace histogram [3, 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] [2025-01-09 04:11:30,454 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 04:11:30,646 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:30,647 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:30,647 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:30,647 INFO L85 PathProgramCache]: Analyzing trace with hash 1503662489, now seen corresponding path program 1 times [2025-01-09 04:11:30,647 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:30,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1443717999] [2025-01-09 04:11:30,647 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:30,647 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:30,657 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-01-09 04:11:30,703 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-01-09 04:11:30,703 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:30,703 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:30,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1370981284] [2025-01-09 04:11:30,709 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:30,710 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:30,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:30,713 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 04:11:30,716 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 04:11:30,793 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-01-09 04:11:30,863 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-01-09 04:11:30,863 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:30,863 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:30,865 INFO L256 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 87 conjuncts are in the unsatisfiable core [2025-01-09 04:11:30,869 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:30,873 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:30,876 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:30,880 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:30,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:31,196 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 29 treesize of output 13 [2025-01-09 04:11:31,214 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 26 treesize of output 14 [2025-01-09 04:11:31,218 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 29 treesize of output 13 [2025-01-09 04:11:31,290 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-01-09 04:11:31,290 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:39,712 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:39,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1443717999] [2025-01-09 04:11:39,713 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:39,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1370981284] [2025-01-09 04:11:39,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1370981284] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:39,713 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:39,713 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-01-09 04:11:39,713 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [409430862] [2025-01-09 04:11:39,713 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:39,713 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-01-09 04:11:39,713 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:39,714 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-01-09 04:11:39,714 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=85, Unknown=1, NotChecked=0, Total=110 [2025-01-09 04:11:39,714 INFO L87 Difference]: Start difference. First operand 152 states and 189 transitions. Second operand has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-01-09 04:11:40,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:40,123 INFO L93 Difference]: Finished difference Result 174 states and 210 transitions. [2025-01-09 04:11:40,123 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:11:40,123 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 35 [2025-01-09 04:11:40,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:40,125 INFO L225 Difference]: With dead ends: 174 [2025-01-09 04:11:40,125 INFO L226 Difference]: Without dead ends: 172 [2025-01-09 04:11:40,125 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 24 SyntacticMatches, 7 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=49, Invalid=160, Unknown=1, NotChecked=0, Total=210 [2025-01-09 04:11:40,125 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 26 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 222 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 240 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 222 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:40,126 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 221 Invalid, 240 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 222 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 04:11:40,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2025-01-09 04:11:40,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 170. [2025-01-09 04:11:40,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 106 states have (on average 1.1132075471698113) internal successors, (118), 110 states have internal predecessors, (118), 42 states have call successors, (42), 18 states have call predecessors, (42), 21 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2025-01-09 04:11:40,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 207 transitions. [2025-01-09 04:11:40,153 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 207 transitions. Word has length 35 [2025-01-09 04:11:40,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:40,153 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 207 transitions. [2025-01-09 04:11:40,153 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-01-09 04:11:40,153 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 207 transitions. [2025-01-09 04:11:40,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-01-09 04:11:40,154 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:40,154 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 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 04:11:40,162 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 04:11:40,355 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,SelfDestructingSolverStorable7 [2025-01-09 04:11:40,355 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:40,355 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:40,355 INFO L85 PathProgramCache]: Analyzing trace with hash -734576000, now seen corresponding path program 1 times [2025-01-09 04:11:40,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:40,356 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1082440879] [2025-01-09 04:11:40,356 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:40,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:40,366 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-01-09 04:11:40,390 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-01-09 04:11:40,391 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:40,391 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:40,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1048570205] [2025-01-09 04:11:40,392 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:40,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:40,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:40,394 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 04:11:40,399 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 04:11:40,486 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-01-09 04:11:40,593 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-01-09 04:11:40,594 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:40,594 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:40,597 INFO L256 TraceCheckSpWp]: Trace formula consists of 368 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-01-09 04:11:40,602 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:40,612 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:40,617 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:40,623 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 11 [2025-01-09 04:11:40,629 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:40,964 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 7 treesize of output 3 [2025-01-09 04:11:40,974 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 7 treesize of output 3 [2025-01-09 04:11:41,024 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-01-09 04:11:41,026 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:45,198 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:45,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1082440879] [2025-01-09 04:11:45,198 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:45,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1048570205] [2025-01-09 04:11:45,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1048570205] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:45,199 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:45,199 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-01-09 04:11:45,199 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443900686] [2025-01-09 04:11:45,199 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:45,199 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-01-09 04:11:45,199 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:45,199 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-01-09 04:11:45,200 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=85, Unknown=1, NotChecked=0, Total=110 [2025-01-09 04:11:45,200 INFO L87 Difference]: Start difference. First operand 170 states and 207 transitions. Second operand has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-01-09 04:11:45,495 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:45,495 INFO L93 Difference]: Finished difference Result 182 states and 217 transitions. [2025-01-09 04:11:45,496 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:11:45,496 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 41 [2025-01-09 04:11:45,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:45,497 INFO L225 Difference]: With dead ends: 182 [2025-01-09 04:11:45,497 INFO L226 Difference]: Without dead ends: 180 [2025-01-09 04:11:45,498 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 26 SyntacticMatches, 11 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=49, Invalid=160, Unknown=1, NotChecked=0, Total=210 [2025-01-09 04:11:45,498 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 27 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 215 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:45,498 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 218 Invalid, 215 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 04:11:45,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2025-01-09 04:11:45,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 178. [2025-01-09 04:11:45,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 112 states have (on average 1.1071428571428572) internal successors, (124), 116 states have internal predecessors, (124), 42 states have call successors, (42), 20 states have call predecessors, (42), 23 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2025-01-09 04:11:45,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 213 transitions. [2025-01-09 04:11:45,537 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 213 transitions. Word has length 41 [2025-01-09 04:11:45,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:45,538 INFO L471 AbstractCegarLoop]: Abstraction has 178 states and 213 transitions. [2025-01-09 04:11:45,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-01-09 04:11:45,538 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 213 transitions. [2025-01-09 04:11:45,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-01-09 04:11:45,539 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:45,539 INFO L218 NwaCegarLoop]: trace histogram [4, 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] [2025-01-09 04:11:45,548 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 04:11:45,740 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:45,740 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:45,740 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:45,740 INFO L85 PathProgramCache]: Analyzing trace with hash 631289121, now seen corresponding path program 1 times [2025-01-09 04:11:45,740 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:45,740 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [910524735] [2025-01-09 04:11:45,741 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:45,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:45,751 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-01-09 04:11:45,775 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-01-09 04:11:45,777 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:45,777 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:45,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1634158755] [2025-01-09 04:11:45,779 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:45,779 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:45,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:45,782 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 04:11:45,789 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 04:11:45,877 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-01-09 04:11:46,003 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-01-09 04:11:46,003 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:46,003 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:46,008 INFO L256 TraceCheckSpWp]: Trace formula consists of 352 conjuncts, 105 conjuncts are in the unsatisfiable core [2025-01-09 04:11:46,011 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:46,021 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:46,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:46,030 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:46,036 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:46,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 40 treesize of output 20 [2025-01-09 04:11:46,404 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 64 treesize of output 28 [2025-01-09 04:11:46,425 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 50 treesize of output 22 [2025-01-09 04:11:46,556 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2025-01-09 04:11:46,556 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:51,006 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:51,006 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [910524735] [2025-01-09 04:11:51,006 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:51,006 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1634158755] [2025-01-09 04:11:51,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1634158755] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:51,006 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:51,006 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-01-09 04:11:51,006 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619084291] [2025-01-09 04:11:51,006 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:51,006 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-01-09 04:11:51,007 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:51,007 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-01-09 04:11:51,007 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=85, Unknown=1, NotChecked=0, Total=110 [2025-01-09 04:11:51,007 INFO L87 Difference]: Start difference. First operand 178 states and 213 transitions. Second operand has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-01-09 04:11:52,223 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:52,224 INFO L93 Difference]: Finished difference Result 186 states and 219 transitions. [2025-01-09 04:11:52,224 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:11:52,224 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 41 [2025-01-09 04:11:52,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:52,226 INFO L225 Difference]: With dead ends: 186 [2025-01-09 04:11:52,226 INFO L226 Difference]: Without dead ends: 184 [2025-01-09 04:11:52,227 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 28 SyntacticMatches, 9 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=49, Invalid=160, Unknown=1, NotChecked=0, Total=210 [2025-01-09 04:11:52,227 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 25 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 222 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 222 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:52,228 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 221 Invalid, 238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 222 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-01-09 04:11:52,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2025-01-09 04:11:52,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 134. [2025-01-09 04:11:52,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 84 states have (on average 1.119047619047619) internal successors, (94), 88 states have internal predecessors, (94), 32 states have call successors, (32), 14 states have call predecessors, (32), 17 states have return successors, (36), 31 states have call predecessors, (36), 29 states have call successors, (36) [2025-01-09 04:11:52,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 162 transitions. [2025-01-09 04:11:52,265 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 162 transitions. Word has length 41 [2025-01-09 04:11:52,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:52,266 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 162 transitions. [2025-01-09 04:11:52,266 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-01-09 04:11:52,267 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 162 transitions. [2025-01-09 04:11:52,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-01-09 04:11:52,267 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:52,267 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 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 04:11:52,277 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 04:11:52,468 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:52,468 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:52,469 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:52,469 INFO L85 PathProgramCache]: Analyzing trace with hash 14741188, now seen corresponding path program 1 times [2025-01-09 04:11:52,469 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:52,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [960887341] [2025-01-09 04:11:52,470 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:52,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:52,479 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-01-09 04:11:52,506 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-01-09 04:11:52,506 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:52,506 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:52,508 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1992005966] [2025-01-09 04:11:52,508 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:52,508 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:52,508 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:52,510 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 04:11:52,513 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 04:11:52,605 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-01-09 04:11:52,664 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-01-09 04:11:52,665 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:52,665 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:52,668 INFO L256 TraceCheckSpWp]: Trace formula consists of 389 conjuncts, 79 conjuncts are in the unsatisfiable core [2025-01-09 04:11:52,672 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:52,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:52,681 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:52,687 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:52,693 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:53,367 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 11 [2025-01-09 04:11:53,369 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:11:53,419 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-01-09 04:11:53,419 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:54,002 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:54,002 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [960887341] [2025-01-09 04:11:54,002 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:54,002 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1992005966] [2025-01-09 04:11:54,002 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1992005966] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:54,002 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:54,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2025-01-09 04:11:54,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [686909940] [2025-01-09 04:11:54,002 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:54,002 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 04:11:54,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:54,003 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 04:11:54,003 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2025-01-09 04:11:54,003 INFO L87 Difference]: Start difference. First operand 134 states and 162 transitions. Second operand has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-01-09 04:11:55,265 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:55,265 INFO L93 Difference]: Finished difference Result 190 states and 222 transitions. [2025-01-09 04:11:55,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-01-09 04:11:55,265 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 47 [2025-01-09 04:11:55,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:55,267 INFO L225 Difference]: With dead ends: 190 [2025-01-09 04:11:55,267 INFO L226 Difference]: Without dead ends: 188 [2025-01-09 04:11:55,267 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 29 SyntacticMatches, 12 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=80, Invalid=300, Unknown=0, NotChecked=0, Total=380 [2025-01-09 04:11:55,268 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 45 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 344 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 215 SdHoareTripleChecker+Invalid, 373 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 344 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:55,269 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 215 Invalid, 373 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 344 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-01-09 04:11:55,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2025-01-09 04:11:55,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 186. [2025-01-09 04:11:55,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 118 states have (on average 1.1016949152542372) internal successors, (130), 122 states have internal predecessors, (130), 42 states have call successors, (42), 22 states have call predecessors, (42), 25 states have return successors, (47), 41 states have call predecessors, (47), 38 states have call successors, (47) [2025-01-09 04:11:55,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 219 transitions. [2025-01-09 04:11:55,320 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 219 transitions. Word has length 47 [2025-01-09 04:11:55,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:55,320 INFO L471 AbstractCegarLoop]: Abstraction has 186 states and 219 transitions. [2025-01-09 04:11:55,320 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-01-09 04:11:55,320 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 219 transitions. [2025-01-09 04:11:55,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2025-01-09 04:11:55,321 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:55,321 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 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] [2025-01-09 04:11:55,328 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-01-09 04:11:55,521 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:55,521 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:55,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:55,522 INFO L85 PathProgramCache]: Analyzing trace with hash -1154003285, now seen corresponding path program 1 times [2025-01-09 04:11:55,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:55,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [901030383] [2025-01-09 04:11:55,522 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:55,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:55,533 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 53 statements into 1 equivalence classes. [2025-01-09 04:11:55,569 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 53 of 53 statements. [2025-01-09 04:11:55,570 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:55,570 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:55,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [708856834] [2025-01-09 04:11:55,572 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:55,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:55,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:55,574 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 04:11:55,576 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 04:11:55,672 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 53 statements into 1 equivalence classes. [2025-01-09 04:11:55,861 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 53 of 53 statements. [2025-01-09 04:11:55,862 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:55,862 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:55,867 INFO L256 TraceCheckSpWp]: Trace formula consists of 418 conjuncts, 99 conjuncts are in the unsatisfiable core [2025-01-09 04:11:55,871 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:55,882 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:55,930 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:55,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:55,947 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:56,255 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 11 [2025-01-09 04:11:56,379 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 19 treesize of output 11 [2025-01-09 04:11:57,881 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:57,881 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 57 treesize of output 45 [2025-01-09 04:11:57,891 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:57,891 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 62 treesize of output 46 [2025-01-09 04:11:58,009 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-01-09 04:11:58,009 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:58,935 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:58,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [901030383] [2025-01-09 04:11:58,935 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:58,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [708856834] [2025-01-09 04:11:58,935 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [708856834] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:58,935 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:58,935 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2025-01-09 04:11:58,935 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1462026373] [2025-01-09 04:11:58,935 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:58,936 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-09 04:11:58,936 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:58,936 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-09 04:11:58,936 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=264, Unknown=0, NotChecked=0, Total=306 [2025-01-09 04:11:58,936 INFO L87 Difference]: Start difference. First operand 186 states and 219 transitions. Second operand has 16 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 13 states have internal predecessors, (25), 5 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:01,831 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:01,831 INFO L93 Difference]: Finished difference Result 244 states and 282 transitions. [2025-01-09 04:12:01,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-01-09 04:12:01,832 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 13 states have internal predecessors, (25), 5 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 53 [2025-01-09 04:12:01,832 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:01,833 INFO L225 Difference]: With dead ends: 244 [2025-01-09 04:12:01,833 INFO L226 Difference]: Without dead ends: 242 [2025-01-09 04:12:01,834 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 31 SyntacticMatches, 11 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2025-01-09 04:12:01,834 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 43 mSDsluCounter, 218 mSDsCounter, 0 mSdLazyCounter, 959 mSolverCounterSat, 27 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 987 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 959 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:01,834 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 258 Invalid, 987 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 959 Invalid, 1 Unknown, 0 Unchecked, 2.2s Time] [2025-01-09 04:12:01,835 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2025-01-09 04:12:01,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 188. [2025-01-09 04:12:01,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 119 states have (on average 1.1008403361344539) internal successors, (131), 123 states have internal predecessors, (131), 42 states have call successors, (42), 22 states have call predecessors, (42), 26 states have return successors, (49), 42 states have call predecessors, (49), 38 states have call successors, (49) [2025-01-09 04:12:01,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 222 transitions. [2025-01-09 04:12:01,885 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 222 transitions. Word has length 53 [2025-01-09 04:12:01,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:01,886 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 222 transitions. [2025-01-09 04:12:01,886 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 13 states have internal predecessors, (25), 5 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:01,886 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 222 transitions. [2025-01-09 04:12:01,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-01-09 04:12:01,886 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:01,887 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 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] [2025-01-09 04:12:01,895 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-01-09 04:12:02,087 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-01-09 04:12:02,087 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:02,088 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:02,088 INFO L85 PathProgramCache]: Analyzing trace with hash 676454098, now seen corresponding path program 2 times [2025-01-09 04:12:02,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:02,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1860029850] [2025-01-09 04:12:02,088 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:12:02,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:02,098 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 59 statements into 2 equivalence classes. [2025-01-09 04:12:02,152 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 59 of 59 statements. [2025-01-09 04:12:02,152 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:12:02,152 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:02,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1163754969] [2025-01-09 04:12:02,154 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:12:02,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:02,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:02,157 INFO L229 MonitoredProcess]: Starting monitored process 12 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 04:12:02,159 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-01-09 04:12:02,252 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 59 statements into 2 equivalence classes. [2025-01-09 04:12:02,397 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 59 of 59 statements. [2025-01-09 04:12:02,397 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:12:02,397 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:02,400 INFO L256 TraceCheckSpWp]: Trace formula consists of 447 conjuncts, 146 conjuncts are in the unsatisfiable core [2025-01-09 04:12:02,404 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:02,413 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:02,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:02,440 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:02,451 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:03,023 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 19 treesize of output 11 [2025-01-09 04:12:04,495 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:04,496 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 30 treesize of output 30 [2025-01-09 04:12:04,508 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:04,508 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 40 treesize of output 32 [2025-01-09 04:12:04,638 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-01-09 04:12:04,638 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:05,582 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:05,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1860029850] [2025-01-09 04:12:05,582 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:05,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1163754969] [2025-01-09 04:12:05,582 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1163754969] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:05,582 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:05,582 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-01-09 04:12:05,583 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952203994] [2025-01-09 04:12:05,583 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:05,583 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-01-09 04:12:05,583 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:05,583 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-01-09 04:12:05,584 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=535, Unknown=0, NotChecked=0, Total=600 [2025-01-09 04:12:05,584 INFO L87 Difference]: Start difference. First operand 188 states and 222 transitions. Second operand has 21 states, 16 states have (on average 1.75) internal successors, (28), 17 states have internal predecessors, (28), 6 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 04:12:08,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:08,997 INFO L93 Difference]: Finished difference Result 288 states and 330 transitions. [2025-01-09 04:12:08,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-01-09 04:12:08,998 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 1.75) internal successors, (28), 17 states have internal predecessors, (28), 6 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 59 [2025-01-09 04:12:08,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:09,000 INFO L225 Difference]: With dead ends: 288 [2025-01-09 04:12:09,000 INFO L226 Difference]: Without dead ends: 286 [2025-01-09 04:12:09,000 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 32 SyntacticMatches, 9 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 303 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=157, Invalid=1175, Unknown=0, NotChecked=0, Total=1332 [2025-01-09 04:12:09,004 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 46 mSDsluCounter, 278 mSDsCounter, 0 mSdLazyCounter, 1075 mSolverCounterSat, 35 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 320 SdHoareTripleChecker+Invalid, 1114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 1075 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:09,004 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 320 Invalid, 1114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 1075 Invalid, 4 Unknown, 0 Unchecked, 2.2s Time] [2025-01-09 04:12:09,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2025-01-09 04:12:09,067 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 190. [2025-01-09 04:12:09,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 120 states have (on average 1.1) internal successors, (132), 124 states have internal predecessors, (132), 42 states have call successors, (42), 22 states have call predecessors, (42), 27 states have return successors, (51), 43 states have call predecessors, (51), 38 states have call successors, (51) [2025-01-09 04:12:09,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 225 transitions. [2025-01-09 04:12:09,070 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 225 transitions. Word has length 59 [2025-01-09 04:12:09,070 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:09,070 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 225 transitions. [2025-01-09 04:12:09,070 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 1.75) internal successors, (28), 17 states have internal predecessors, (28), 6 states have call successors, (9), 4 states have call predecessors, (9), 5 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2025-01-09 04:12:09,070 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 225 transitions. [2025-01-09 04:12:09,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-01-09 04:12:09,071 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:09,071 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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 04:12:09,081 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-01-09 04:12:09,272 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-01-09 04:12:09,272 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:09,272 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:09,272 INFO L85 PathProgramCache]: Analyzing trace with hash -432212062, now seen corresponding path program 1 times [2025-01-09 04:12:09,273 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:09,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [339322445] [2025-01-09 04:12:09,273 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:09,273 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:09,286 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-01-09 04:12:09,317 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-01-09 04:12:09,317 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:09,317 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:09,319 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1145995486] [2025-01-09 04:12:09,319 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:09,320 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:09,320 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:09,322 INFO L229 MonitoredProcess]: Starting monitored process 13 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 04:12:09,334 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-01-09 04:12:09,437 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-01-09 04:12:09,586 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-01-09 04:12:09,586 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:09,586 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:09,589 INFO L256 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 61 conjuncts are in the unsatisfiable core [2025-01-09 04:12:09,594 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:09,599 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:09,605 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:09,611 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:09,617 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:09,728 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 11 treesize of output 7 [2025-01-09 04:12:09,835 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 26 treesize of output 14 [2025-01-09 04:12:09,844 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 22 treesize of output 10 [2025-01-09 04:12:09,934 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-01-09 04:12:09,934 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 04:12:09,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:09,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [339322445] [2025-01-09 04:12:09,934 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:09,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1145995486] [2025-01-09 04:12:09,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1145995486] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:09,934 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:12:09,934 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-01-09 04:12:09,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1184227287] [2025-01-09 04:12:09,934 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:09,935 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:09,935 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:09,935 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:09,935 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-01-09 04:12:09,935 INFO L87 Difference]: Start difference. First operand 190 states and 225 transitions. Second operand has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (9), 4 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 04:12:11,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:11,034 INFO L93 Difference]: Finished difference Result 202 states and 235 transitions. [2025-01-09 04:12:11,034 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:12:11,034 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (9), 4 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 57 [2025-01-09 04:12:11,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:11,035 INFO L225 Difference]: With dead ends: 202 [2025-01-09 04:12:11,035 INFO L226 Difference]: Without dead ends: 200 [2025-01-09 04:12:11,036 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=37, Invalid=95, Unknown=0, NotChecked=0, Total=132 [2025-01-09 04:12:11,036 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 40 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 43 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 272 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:11,036 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 102 Invalid, 272 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 227 Invalid, 2 Unknown, 0 Unchecked, 0.9s Time] [2025-01-09 04:12:11,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 200 states. [2025-01-09 04:12:11,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 200 to 198. [2025-01-09 04:12:11,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 126 states have (on average 1.0952380952380953) internal successors, (138), 130 states have internal predecessors, (138), 42 states have call successors, (42), 24 states have call predecessors, (42), 29 states have return successors, (51), 43 states have call predecessors, (51), 38 states have call successors, (51) [2025-01-09 04:12:11,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 231 transitions. [2025-01-09 04:12:11,095 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 231 transitions. Word has length 57 [2025-01-09 04:12:11,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:11,095 INFO L471 AbstractCegarLoop]: Abstraction has 198 states and 231 transitions. [2025-01-09 04:12:11,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (9), 4 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 04:12:11,096 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 231 transitions. [2025-01-09 04:12:11,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-01-09 04:12:11,096 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:11,097 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 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] [2025-01-09 04:12:11,106 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-01-09 04:12:11,301 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:11,301 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:11,301 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:11,301 INFO L85 PathProgramCache]: Analyzing trace with hash 1603950229, now seen corresponding path program 1 times [2025-01-09 04:12:11,301 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:11,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1621899955] [2025-01-09 04:12:11,301 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:11,302 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:11,316 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-01-09 04:12:11,334 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-01-09 04:12:11,334 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:11,334 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:11,626 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-01-09 04:12:11,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:11,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1621899955] [2025-01-09 04:12:11,627 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1621899955] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:11,627 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:12:11,627 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-01-09 04:12:11,627 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1014010284] [2025-01-09 04:12:11,627 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:11,628 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-01-09 04:12:11,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:11,629 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-01-09 04:12:11,629 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-01-09 04:12:11,629 INFO L87 Difference]: Start difference. First operand 198 states and 231 transitions. Second operand has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 3 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 04:12:12,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:12,357 INFO L93 Difference]: Finished difference Result 290 states and 353 transitions. [2025-01-09 04:12:12,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-09 04:12:12,357 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 3 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 58 [2025-01-09 04:12:12,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:12,359 INFO L225 Difference]: With dead ends: 290 [2025-01-09 04:12:12,359 INFO L226 Difference]: Without dead ends: 222 [2025-01-09 04:12:12,359 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2025-01-09 04:12:12,361 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 41 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 224 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:12,361 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 104 Invalid, 224 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-01-09 04:12:12,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2025-01-09 04:12:12,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 216. [2025-01-09 04:12:12,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 136 states have (on average 1.088235294117647) internal successors, (148), 140 states have internal predecessors, (148), 49 states have call successors, (49), 25 states have call predecessors, (49), 30 states have return successors, (58), 50 states have call predecessors, (58), 45 states have call successors, (58) [2025-01-09 04:12:12,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 255 transitions. [2025-01-09 04:12:12,429 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 255 transitions. Word has length 58 [2025-01-09 04:12:12,429 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:12,430 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 255 transitions. [2025-01-09 04:12:12,430 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 3 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 04:12:12,430 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 255 transitions. [2025-01-09 04:12:12,431 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-01-09 04:12:12,431 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:12,431 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 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 04:12:12,431 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2025-01-09 04:12:12,431 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:12,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:12,431 INFO L85 PathProgramCache]: Analyzing trace with hash -943517895, now seen corresponding path program 3 times [2025-01-09 04:12:12,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:12,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1237146936] [2025-01-09 04:12:12,432 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 04:12:12,432 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:12,444 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 65 statements into 6 equivalence classes. [2025-01-09 04:12:12,534 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 65 of 65 statements. [2025-01-09 04:12:12,534 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-09 04:12:12,534 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:12,537 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1903402768] [2025-01-09 04:12:12,537 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 04:12:12,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:12,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:12,539 INFO L229 MonitoredProcess]: Starting monitored process 14 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 04:12:12,541 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-01-09 04:12:12,649 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 65 statements into 6 equivalence classes. [2025-01-09 04:12:12,785 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) and asserted 29 of 65 statements. [2025-01-09 04:12:12,785 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2025-01-09 04:12:12,785 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:12,787 INFO L256 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 58 conjuncts are in the unsatisfiable core [2025-01-09 04:12:12,790 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:12,799 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:12,817 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:12,823 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:13,239 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 11 [2025-01-09 04:12:13,243 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:12:13,249 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:12:13,297 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2025-01-09 04:12:13,297 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:13,508 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 35 treesize of output 27 [2025-01-09 04:12:13,662 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:13,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1237146936] [2025-01-09 04:12:13,662 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:13,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1903402768] [2025-01-09 04:12:13,662 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1903402768] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:13,662 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:13,662 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2025-01-09 04:12:13,662 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1813514469] [2025-01-09 04:12:13,662 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:13,662 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 04:12:13,662 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:13,663 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 04:12:13,663 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2025-01-09 04:12:13,663 INFO L87 Difference]: Start difference. First operand 216 states and 255 transitions. Second operand has 10 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:14,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:14,419 INFO L93 Difference]: Finished difference Result 230 states and 269 transitions. [2025-01-09 04:12:14,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-09 04:12:14,419 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 65 [2025-01-09 04:12:14,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:14,420 INFO L225 Difference]: With dead ends: 230 [2025-01-09 04:12:14,420 INFO L226 Difference]: Without dead ends: 228 [2025-01-09 04:12:14,421 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 47 SyntacticMatches, 11 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2025-01-09 04:12:14,421 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 45 mSDsluCounter, 172 mSDsCounter, 0 mSdLazyCounter, 222 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 252 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 222 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:14,421 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 204 Invalid, 252 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 222 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-01-09 04:12:14,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2025-01-09 04:12:14,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 210. [2025-01-09 04:12:14,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 133 states have (on average 1.0827067669172932) internal successors, (144), 137 states have internal predecessors, (144), 46 states have call successors, (46), 25 states have call predecessors, (46), 30 states have return successors, (56), 47 states have call predecessors, (56), 43 states have call successors, (56) [2025-01-09 04:12:14,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 246 transitions. [2025-01-09 04:12:14,508 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 246 transitions. Word has length 65 [2025-01-09 04:12:14,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:14,508 INFO L471 AbstractCegarLoop]: Abstraction has 210 states and 246 transitions. [2025-01-09 04:12:14,509 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:14,509 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 246 transitions. [2025-01-09 04:12:14,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-01-09 04:12:14,510 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:14,510 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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 04:12:14,519 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-01-09 04:12:14,710 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:14,710 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:14,711 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:14,711 INFO L85 PathProgramCache]: Analyzing trace with hash -1600618501, now seen corresponding path program 1 times [2025-01-09 04:12:14,711 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:14,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1663641168] [2025-01-09 04:12:14,711 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:14,711 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:14,720 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-01-09 04:12:14,734 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-01-09 04:12:14,734 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:14,734 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:14,735 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1147156836] [2025-01-09 04:12:14,735 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:14,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:14,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:14,738 INFO L229 MonitoredProcess]: Starting monitored process 15 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 04:12:14,739 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-01-09 04:12:14,854 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-01-09 04:12:14,911 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-01-09 04:12:14,912 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:14,912 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:14,918 INFO L256 TraceCheckSpWp]: Trace formula consists of 447 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-01-09 04:12:14,921 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:14,926 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:14,930 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:15,000 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 11 treesize of output 7 [2025-01-09 04:12:15,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 11 [2025-01-09 04:12:15,141 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 7 [2025-01-09 04:12:15,183 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 36 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-01-09 04:12:15,184 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:15,280 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:15,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1663641168] [2025-01-09 04:12:15,280 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:15,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1147156836] [2025-01-09 04:12:15,280 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1147156836] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:15,280 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:15,280 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2025-01-09 04:12:15,280 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1187478964] [2025-01-09 04:12:15,280 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:15,280 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:15,280 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:15,281 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:15,281 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2025-01-09 04:12:15,281 INFO L87 Difference]: Start difference. First operand 210 states and 246 transitions. Second operand has 8 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 3 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-01-09 04:12:16,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:16,229 INFO L93 Difference]: Finished difference Result 218 states and 252 transitions. [2025-01-09 04:12:16,230 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:12:16,230 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 3 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 63 [2025-01-09 04:12:16,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:16,231 INFO L225 Difference]: With dead ends: 218 [2025-01-09 04:12:16,231 INFO L226 Difference]: Without dead ends: 214 [2025-01-09 04:12:16,232 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 57 SyntacticMatches, 5 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2025-01-09 04:12:16,232 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 43 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 249 mSolverCounterSat, 45 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 299 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 249 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:16,232 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 99 Invalid, 299 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 249 Invalid, 5 Unknown, 0 Unchecked, 0.8s Time] [2025-01-09 04:12:16,232 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2025-01-09 04:12:16,314 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 212. [2025-01-09 04:12:16,315 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 135 states have (on average 1.0740740740740742) internal successors, (145), 138 states have internal predecessors, (145), 46 states have call successors, (46), 26 states have call predecessors, (46), 30 states have return successors, (56), 47 states have call predecessors, (56), 43 states have call successors, (56) [2025-01-09 04:12:16,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 247 transitions. [2025-01-09 04:12:16,317 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 247 transitions. Word has length 63 [2025-01-09 04:12:16,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:16,318 INFO L471 AbstractCegarLoop]: Abstraction has 212 states and 247 transitions. [2025-01-09 04:12:16,318 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 3 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-01-09 04:12:16,318 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 247 transitions. [2025-01-09 04:12:16,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-01-09 04:12:16,319 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:16,319 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 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] [2025-01-09 04:12:16,329 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2025-01-09 04:12:16,519 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-01-09 04:12:16,520 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:16,520 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:16,521 INFO L85 PathProgramCache]: Analyzing trace with hash -785461170, now seen corresponding path program 1 times [2025-01-09 04:12:16,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:16,521 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [285295045] [2025-01-09 04:12:16,521 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:16,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:16,532 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-01-09 04:12:16,576 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-01-09 04:12:16,576 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:16,576 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:19,316 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2025-01-09 04:12:19,316 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:19,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [285295045] [2025-01-09 04:12:19,316 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [285295045] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:19,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [552747954] [2025-01-09 04:12:19,316 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:19,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:19,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:19,318 INFO L229 MonitoredProcess]: Starting monitored process 16 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 04:12:19,319 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-01-09 04:12:19,412 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-01-09 04:12:19,517 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-01-09 04:12:19,517 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:19,517 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:19,520 INFO L256 TraceCheckSpWp]: Trace formula consists of 509 conjuncts, 165 conjuncts are in the unsatisfiable core [2025-01-09 04:12:19,524 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:19,530 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:19,534 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:19,538 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:19,542 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:19,896 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 11 [2025-01-09 04:12:20,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 19 treesize of output 11 [2025-01-09 04:12:20,230 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:20,231 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 41 treesize of output 37 [2025-01-09 04:12:21,823 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:21,846 INFO L349 Elim1Store]: treesize reduction 37, result has 15.9 percent of original size [2025-01-09 04:12:21,846 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2025-01-09 04:12:21,857 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 19 treesize of output 11 [2025-01-09 04:12:21,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 36 treesize of output 20 [2025-01-09 04:12:21,965 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-01-09 04:12:21,965 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-01-09 04:12:22,165 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 30 treesize of output 18 [2025-01-09 04:12:22,328 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2025-01-09 04:12:22,328 INFO L312 TraceCheckSpWp]: Computing backward predicates...