./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 c00e63dc 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-?-c00e63d-m [2025-02-05 16:02:20,670 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-05 16:02:20,728 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-02-05 16:02:20,737 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-05 16:02:20,737 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-05 16:02:20,761 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-05 16:02:20,762 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-05 16:02:20,762 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-05 16:02:20,763 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-05 16:02:20,763 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-05 16:02:20,763 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-05 16:02:20,764 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-05 16:02:20,764 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-05 16:02:20,764 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-05 16:02:20,765 INFO L153 SettingsManager]: * Use SBE=true [2025-02-05 16:02:20,766 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-05 16:02:20,766 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-05 16:02:20,767 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-05 16:02:20,767 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-05 16:02:20,767 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-05 16:02:20,767 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-05 16:02:20,767 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-05 16:02:20,767 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-05 16:02:20,767 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-05 16:02:20,768 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 16:02:20,768 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-05 16:02:20,768 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-05 16:02:20,769 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-05 16:02:20,769 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-02-05 16:02:21,041 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-05 16:02:21,050 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-05 16:02:21,052 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-05 16:02:21,053 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-05 16:02:21,053 INFO L274 PluginConnector]: CDTParser initialized [2025-02-05 16:02:21,055 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-02-05 16:02:22,286 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/f61c35c51/01a49664da624fe09d5a3bfe87d78382/FLAGb17ef02f0 [2025-02-05 16:02:22,535 INFO L384 CDTParser]: Found 1 translation units. [2025-02-05 16:02:22,536 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2025-02-05 16:02:22,543 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/f61c35c51/01a49664da624fe09d5a3bfe87d78382/FLAGb17ef02f0 [2025-02-05 16:02:22,558 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/f61c35c51/01a49664da624fe09d5a3bfe87d78382 [2025-02-05 16:02:22,559 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-05 16:02:22,561 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-05 16:02:22,562 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-05 16:02:22,562 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-05 16:02:22,566 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-05 16:02:22,566 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,567 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3d1dffb9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22, skipping insertion in model container [2025-02-05 16:02:22,567 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,580 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-05 16:02:22,714 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-02-05 16:02:22,762 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 16:02:22,773 INFO L200 MainTranslator]: Completed pre-run [2025-02-05 16:02:22,782 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-02-05 16:02:22,818 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 16:02:22,835 INFO L204 MainTranslator]: Completed translation [2025-02-05 16:02:22,836 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22 WrapperNode [2025-02-05 16:02:22,836 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-05 16:02:22,838 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-05 16:02:22,838 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-05 16:02:22,838 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-05 16:02:22,843 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,853 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,878 INFO L138 Inliner]: procedures = 17, calls = 173, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 114 [2025-02-05 16:02:22,881 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-05 16:02:22,882 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-05 16:02:22,882 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-05 16:02:22,882 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-05 16:02:22,889 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,889 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,897 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,923 INFO L175 MemorySlicer]: Split 139 memory accesses to 6 slices as follows [2, 35, 29, 21, 22, 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, 3, 1, 2, 2]. [2025-02-05 16:02:22,925 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,926 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,932 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,934 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,935 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,936 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,939 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-05 16:02:22,940 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-05 16:02:22,940 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-05 16:02:22,940 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-05 16:02:22,941 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (1/1) ... [2025-02-05 16:02:22,945 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 16:02:22,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:22,965 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-02-05 16:02:22,967 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-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_33_0 [2025-02-05 16:02:22,985 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_33_0 [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-02-05 16:02:22,985 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_53_0 [2025-02-05 16:02:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_53_0 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-05 16:02:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-02-05 16:02:22,986 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-02-05 16:02:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-02-05 16:02:22,987 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-02-05 16:02:23,094 INFO L257 CfgBuilder]: Building ICFG [2025-02-05 16:02:23,095 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-05 16:02:23,356 INFO L1309 $ProcedureCfgBuilder]: dead code at ProgramPoint L108: call ULTIMATE.dealloc(main_~#n~0#1.base, main_~#n~0#1.offset);havoc main_~#n~0#1.base, main_~#n~0#1.offset;call ULTIMATE.dealloc(main_~#p~0#1.base, main_~#p~0#1.offset);havoc main_~#p~0#1.base, main_~#p~0#1.offset;call ULTIMATE.dealloc(main_~#q~0#1.base, main_~#q~0#1.offset);havoc main_~#q~0#1.base, main_~#q~0#1.offset;call ULTIMATE.dealloc(main_~#r~0#1.base, main_~#r~0#1.offset);havoc main_~#r~0#1.base, main_~#r~0#1.offset;call ULTIMATE.dealloc(main_~#h~0#1.base, main_~#h~0#1.offset);havoc main_~#h~0#1.base, main_~#h~0#1.offset; [2025-02-05 16:02:23,408 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-02-05 16:02:23,408 INFO L308 CfgBuilder]: Performing block encoding [2025-02-05 16:02:23,418 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-05 16:02:23,419 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-05 16:02:23,419 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 04:02:23 BoogieIcfgContainer [2025-02-05 16:02:23,419 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-05 16:02:23,421 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-05 16:02:23,421 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-05 16:02:23,425 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-05 16:02:23,426 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.02 04:02:22" (1/3) ... [2025-02-05 16:02:23,426 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@47fa7cae and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 04:02:23, skipping insertion in model container [2025-02-05 16:02:23,426 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:22" (2/3) ... [2025-02-05 16:02:23,427 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@47fa7cae and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 04:02:23, skipping insertion in model container [2025-02-05 16:02:23,427 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 04:02:23" (3/3) ... [2025-02-05 16:02:23,428 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra-u.c [2025-02-05 16:02:23,439 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-05 16:02:23,441 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-02-05 16:02:23,485 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-05 16:02:23,493 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;@1a694842, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-05 16:02:23,493 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-02-05 16:02:23,497 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-02-05 16:02:23,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2025-02-05 16:02:23,502 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:23,503 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 16:02:23,503 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:23,507 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:23,508 INFO L85 PathProgramCache]: Analyzing trace with hash 1780476219, now seen corresponding path program 1 times [2025-02-05 16:02:23,515 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:23,518 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [844992864] [2025-02-05 16:02:23,518 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:23,519 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:23,606 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-02-05 16:02:23,630 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-02-05 16:02:23,631 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:23,631 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:23,708 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 16:02:23,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:23,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [844992864] [2025-02-05 16:02:23,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [844992864] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 16:02:23,713 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 16:02:23,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-02-05 16:02:23,715 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1295315726] [2025-02-05 16:02:23,715 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 16:02:23,720 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-02-05 16:02:23,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:23,739 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-02-05 16:02:23,740 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-02-05 16:02:23,742 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-02-05 16:02:23,760 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:02:23,760 INFO L93 Difference]: Finished difference Result 91 states and 135 transitions. [2025-02-05 16:02:23,761 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-02-05 16:02:23,762 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-02-05 16:02:23,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:02:23,766 INFO L225 Difference]: With dead ends: 91 [2025-02-05 16:02:23,767 INFO L226 Difference]: Without dead ends: 43 [2025-02-05 16:02:23,770 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-02-05 16:02:23,772 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-02-05 16:02:23,773 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-02-05 16:02:23,782 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-02-05 16:02:23,794 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2025-02-05 16:02:23,796 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-02-05 16:02:23,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2025-02-05 16:02:23,804 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 16 [2025-02-05 16:02:23,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:02:23,805 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2025-02-05 16:02:23,806 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-02-05 16:02:23,806 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2025-02-05 16:02:23,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2025-02-05 16:02:23,807 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:23,807 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 16:02:23,807 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-02-05 16:02:23,807 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:23,808 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:23,808 INFO L85 PathProgramCache]: Analyzing trace with hash -278794398, now seen corresponding path program 1 times [2025-02-05 16:02:23,808 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:23,808 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [316662016] [2025-02-05 16:02:23,808 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:23,808 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:23,823 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-02-05 16:02:23,875 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-02-05 16:02:23,875 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:23,875 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:25,244 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 16:02:25,246 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:25,246 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [316662016] [2025-02-05 16:02:25,246 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [316662016] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 16:02:25,246 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 16:02:25,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2025-02-05 16:02:25,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [440456418] [2025-02-05 16:02:25,247 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 16:02:25,247 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-02-05 16:02:25,248 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:25,249 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-02-05 16:02:25,250 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-02-05 16:02:25,250 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-02-05 16:02:26,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:02:26,538 INFO L93 Difference]: Finished difference Result 76 states and 99 transitions. [2025-02-05 16:02:26,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-02-05 16:02:26,539 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-02-05 16:02:26,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:02:26,541 INFO L225 Difference]: With dead ends: 76 [2025-02-05 16:02:26,541 INFO L226 Difference]: Without dead ends: 74 [2025-02-05 16:02:26,542 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=65, Invalid=315, Unknown=0, NotChecked=0, Total=380 [2025-02-05 16:02:26,542 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 57 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 381 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 425 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 381 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2025-02-05 16:02:26,543 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 131 Invalid, 425 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 381 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2025-02-05 16:02:26,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-02-05 16:02:26,558 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 69. [2025-02-05 16:02:26,558 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-02-05 16:02:26,560 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 90 transitions. [2025-02-05 16:02:26,560 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 90 transitions. Word has length 17 [2025-02-05 16:02:26,560 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:02:26,560 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 90 transitions. [2025-02-05 16:02:26,560 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-02-05 16:02:26,560 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 90 transitions. [2025-02-05 16:02:26,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-02-05 16:02:26,564 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:26,564 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-02-05 16:02:26,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-02-05 16:02:26,564 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:26,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:26,565 INFO L85 PathProgramCache]: Analyzing trace with hash 106707940, now seen corresponding path program 1 times [2025-02-05 16:02:26,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:26,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1940999794] [2025-02-05 16:02:26,565 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:26,565 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:26,582 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-02-05 16:02:26,605 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-02-05 16:02:26,605 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:26,605 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:02:26,609 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1068924143] [2025-02-05 16:02:26,610 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:26,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:02:26,610 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:26,613 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-02-05 16:02:26,615 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-02-05 16:02:26,684 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-02-05 16:02:26,872 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-02-05 16:02:26,873 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:26,873 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:26,876 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-02-05 16:02:26,886 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:02:26,916 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-02-05 16:02:26,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-02-05 16:02:26,931 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-02-05 16:02:27,158 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-02-05 16:02:27,162 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-02-05 16:02:27,167 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-02-05 16:02:27,214 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 16:02:27,215 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:02:27,420 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-02-05 16:02:27,658 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:27,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1940999794] [2025-02-05 16:02:27,659 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:02:27,659 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1068924143] [2025-02-05 16:02:27,660 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1068924143] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:27,661 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:02:27,661 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-02-05 16:02:27,661 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1324783324] [2025-02-05 16:02:27,661 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-02-05 16:02:27,662 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-02-05 16:02:27,662 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:27,663 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-02-05 16:02:27,663 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2025-02-05 16:02:27,663 INFO L87 Difference]: Start difference. First operand 69 states and 90 transitions. Second operand has 9 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-05 16:02:28,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:02:28,388 INFO L93 Difference]: Finished difference Result 115 states and 151 transitions. [2025-02-05 16:02:28,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-02-05 16:02:28,389 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2025-02-05 16:02:28,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:02:28,392 INFO L225 Difference]: With dead ends: 115 [2025-02-05 16:02:28,392 INFO L226 Difference]: Without dead ends: 113 [2025-02-05 16:02:28,393 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 14 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2025-02-05 16:02:28,394 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 57 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 220 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 220 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-02-05 16:02:28,394 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 186 Invalid, 250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 220 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-02-05 16:02:28,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2025-02-05 16:02:28,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 104. [2025-02-05 16:02:28,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 62 states have (on average 1.1290322580645162) internal successors, (70), 66 states have internal predecessors, (70), 30 states have call successors, (30), 8 states have call predecessors, (30), 11 states have return successors, (37), 29 states have call predecessors, (37), 28 states have call successors, (37) [2025-02-05 16:02:28,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 137 transitions. [2025-02-05 16:02:28,430 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 137 transitions. Word has length 23 [2025-02-05 16:02:28,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:02:28,430 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 137 transitions. [2025-02-05 16:02:28,430 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 7 states have internal predecessors, (17), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-02-05 16:02:28,433 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 137 transitions. [2025-02-05 16:02:28,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-02-05 16:02:28,434 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:28,434 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-02-05 16:02:28,444 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-02-05 16:02:28,634 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-02-05 16:02:28,635 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:28,635 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:28,635 INFO L85 PathProgramCache]: Analyzing trace with hash 1424014755, now seen corresponding path program 1 times [2025-02-05 16:02:28,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:28,636 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1901244783] [2025-02-05 16:02:28,636 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:28,636 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:28,648 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-02-05 16:02:28,672 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-02-05 16:02:28,673 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:28,673 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:29,855 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-02-05 16:02:29,855 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:29,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1901244783] [2025-02-05 16:02:29,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1901244783] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:29,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1340908005] [2025-02-05 16:02:29,855 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:29,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:02:29,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:29,858 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-02-05 16:02:29,861 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-02-05 16:02:29,926 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-02-05 16:02:29,959 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-02-05 16:02:29,959 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:29,959 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:29,962 INFO L256 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 94 conjuncts are in the unsatisfiable core [2025-02-05 16:02:29,969 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:02:29,974 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-02-05 16:02:29,983 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-02-05 16:02:29,991 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-02-05 16:02:29,997 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-02-05 16:02:30,585 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-02-05 16:02:30,603 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:02:30,603 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 32 treesize of output 32 [2025-02-05 16:02:30,814 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 17 treesize of output 9 [2025-02-05 16:02:30,921 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-02-05 16:02:30,922 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:02:31,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1340908005] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:31,956 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 16:02:31,956 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 29 [2025-02-05 16:02:31,956 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1966925927] [2025-02-05 16:02:31,956 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 16:02:31,956 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-02-05 16:02:31,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:31,957 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-02-05 16:02:31,958 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1151, Unknown=0, NotChecked=0, Total=1260 [2025-02-05 16:02:31,958 INFO L87 Difference]: Start difference. First operand 104 states and 137 transitions. Second operand has 29 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 21 states have internal predecessors, (28), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-02-05 16:02:50,931 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:02:51,548 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:02:51,549 INFO L93 Difference]: Finished difference Result 154 states and 202 transitions. [2025-02-05 16:02:51,549 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-02-05 16:02:51,550 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 21 states have internal predecessors, (28), 8 states have call successors, (8), 6 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-02-05 16:02:51,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:02:51,552 INFO L225 Difference]: With dead ends: 154 [2025-02-05 16:02:51,552 INFO L226 Difference]: Without dead ends: 152 [2025-02-05 16:02:51,553 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 653 ImplicationChecksByTransitivity, 14.3s TimeCoverageRelationStatistics Valid=266, Invalid=2593, Unknown=3, NotChecked=0, Total=2862 [2025-02-05 16:02:51,554 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 129 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 1558 mSolverCounterSat, 93 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 319 SdHoareTripleChecker+Invalid, 1652 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 93 IncrementalHoareTripleChecker+Valid, 1558 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.6s IncrementalHoareTripleChecker+Time [2025-02-05 16:02:51,554 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 319 Invalid, 1652 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [93 Valid, 1558 Invalid, 1 Unknown, 0 Unchecked, 6.6s Time] [2025-02-05 16:02:51,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2025-02-05 16:02:51,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 136. [2025-02-05 16:02:51,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 82 states have (on average 1.1219512195121952) internal successors, (92), 86 states have internal predecessors, (92), 37 states have call successors, (37), 12 states have call predecessors, (37), 16 states have return successors, (48), 37 states have call predecessors, (48), 35 states have call successors, (48) [2025-02-05 16:02:51,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 177 transitions. [2025-02-05 16:02:51,582 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 177 transitions. Word has length 23 [2025-02-05 16:02:51,582 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:02:51,582 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 177 transitions. [2025-02-05 16:02:51,582 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 21 states have internal predecessors, (28), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-02-05 16:02:51,582 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 177 transitions. [2025-02-05 16:02:51,583 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-02-05 16:02:51,583 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:51,583 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 16:02:51,592 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-02-05 16:02:51,788 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-02-05 16:02:51,788 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:51,788 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:51,788 INFO L85 PathProgramCache]: Analyzing trace with hash -878258972, now seen corresponding path program 2 times [2025-02-05 16:02:51,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:51,789 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [139736841] [2025-02-05 16:02:51,789 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 16:02:51,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:51,799 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 29 statements into 2 equivalence classes. [2025-02-05 16:02:51,832 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 16:02:51,832 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 16:02:51,832 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:52,977 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-05 16:02:52,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:52,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [139736841] [2025-02-05 16:02:52,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [139736841] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:52,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [57366079] [2025-02-05 16:02:52,978 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 16:02:52,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:02:52,978 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:52,979 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-02-05 16:02:52,981 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-02-05 16:02:53,045 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 29 statements into 2 equivalence classes. [2025-02-05 16:02:53,082 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 16:02:53,082 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 16:02:53,082 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:53,087 WARN L254 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 131 conjuncts are in the unsatisfiable core [2025-02-05 16:02:53,090 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:02:53,103 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-02-05 16:02:53,164 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-02-05 16:02:53,173 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-02-05 16:02:53,183 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-02-05 16:02:53,800 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:02:53,800 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 36 [2025-02-05 16:02:53,814 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-02-05 16:02:54,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 17 treesize of output 9 [2025-02-05 16:02:54,108 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-02-05 16:02:54,108 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:02:55,108 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [57366079] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:55,108 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 16:02:55,108 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 34 [2025-02-05 16:02:55,109 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [900033441] [2025-02-05 16:02:55,109 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 16:02:55,109 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2025-02-05 16:02:55,109 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:55,110 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2025-02-05 16:02:55,110 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=1520, Unknown=0, NotChecked=0, Total=1640 [2025-02-05 16:02:55,111 INFO L87 Difference]: Start difference. First operand 136 states and 177 transitions. Second operand has 34 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 26 states have internal predecessors, (34), 9 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2025-02-05 16:03:00,454 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:14,046 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:27,220 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:31,256 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:31,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:31,544 INFO L93 Difference]: Finished difference Result 197 states and 260 transitions. [2025-02-05 16:03:31,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2025-02-05 16:03:31,545 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 26 states have internal predecessors, (34), 9 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 29 [2025-02-05 16:03:31,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:31,547 INFO L225 Difference]: With dead ends: 197 [2025-02-05 16:03:31,547 INFO L226 Difference]: Without dead ends: 195 [2025-02-05 16:03:31,549 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1141 ImplicationChecksByTransitivity, 18.9s TimeCoverageRelationStatistics Valid=404, Invalid=4562, Unknown=4, NotChecked=0, Total=4970 [2025-02-05 16:03:31,549 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 139 mSDsluCounter, 379 mSDsCounter, 0 mSdLazyCounter, 1744 mSolverCounterSat, 129 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 145 SdHoareTripleChecker+Valid, 416 SdHoareTripleChecker+Invalid, 1877 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 129 IncrementalHoareTripleChecker+Valid, 1744 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 18.8s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:31,550 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [145 Valid, 416 Invalid, 1877 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [129 Valid, 1744 Invalid, 4 Unknown, 0 Unchecked, 18.8s Time] [2025-02-05 16:03:31,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2025-02-05 16:03:31,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 138. [2025-02-05 16:03:31,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 85 states have (on average 1.1294117647058823) internal successors, (96), 89 states have internal predecessors, (96), 36 states have call successors, (36), 13 states have call predecessors, (36), 16 states have return successors, (43), 35 states have call predecessors, (43), 34 states have call successors, (43) [2025-02-05 16:03:31,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 175 transitions. [2025-02-05 16:03:31,585 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 175 transitions. Word has length 29 [2025-02-05 16:03:31,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:31,586 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 175 transitions. [2025-02-05 16:03:31,587 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 26 states have internal predecessors, (34), 9 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2025-02-05 16:03:31,587 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 175 transitions. [2025-02-05 16:03:31,587 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-02-05 16:03:31,587 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:31,588 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-02-05 16:03:31,597 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-02-05 16:03:31,793 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-02-05 16:03:31,793 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:31,794 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:31,794 INFO L85 PathProgramCache]: Analyzing trace with hash -1395599896, now seen corresponding path program 1 times [2025-02-05 16:03:31,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:31,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [201271531] [2025-02-05 16:03:31,794 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:31,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:31,806 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-05 16:03:31,822 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 16:03:31,822 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:31,822 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:03:31,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1123053607] [2025-02-05 16:03:31,824 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:31,824 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:31,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:31,826 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-02-05 16:03:31,828 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-02-05 16:03:31,899 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-05 16:03:31,968 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 16:03:31,968 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:31,968 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:31,975 INFO L256 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 101 conjuncts are in the unsatisfiable core [2025-02-05 16:03:31,979 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:31,982 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-02-05 16:03:31,986 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-02-05 16:03:31,992 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-02-05 16:03:31,998 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-02-05 16:03:32,005 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-02-05 16:03:32,288 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-02-05 16:03:44,469 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-02-05 16:03:44,555 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 4 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 16:03:44,556 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:03:45,313 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:03:45,313 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [201271531] [2025-02-05 16:03:45,314 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:03:45,314 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1123053607] [2025-02-05 16:03:45,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1123053607] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:03:45,317 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:03:45,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2025-02-05 16:03:45,318 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [237030371] [2025-02-05 16:03:45,318 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-02-05 16:03:45,318 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-02-05 16:03:45,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:03:45,318 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-02-05 16:03:45,318 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=168, Unknown=2, NotChecked=0, Total=210 [2025-02-05 16:03:45,319 INFO L87 Difference]: Start difference. First operand 138 states and 175 transitions. Second operand has 13 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 11 states have internal predecessors, (21), 4 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-05 16:03:46,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:46,719 INFO L93 Difference]: Finished difference Result 156 states and 193 transitions. [2025-02-05 16:03:46,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-05 16:03:46,719 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 11 states have internal predecessors, (21), 4 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 29 [2025-02-05 16:03:46,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:46,721 INFO L225 Difference]: With dead ends: 156 [2025-02-05 16:03:46,721 INFO L226 Difference]: Without dead ends: 154 [2025-02-05 16:03:46,721 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 16 SyntacticMatches, 5 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 13.5s TimeCoverageRelationStatistics Valid=100, Invalid=360, Unknown=2, NotChecked=0, Total=462 [2025-02-05 16:03:46,722 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 60 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 349 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 400 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 349 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:46,722 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 182 Invalid, 400 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 349 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-02-05 16:03:46,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2025-02-05 16:03:46,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 152. [2025-02-05 16:03:46,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 94 states have (on average 1.127659574468085) internal successors, (106), 98 states have internal predecessors, (106), 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-02-05 16:03:46,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 190 transitions. [2025-02-05 16:03:46,770 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 190 transitions. Word has length 29 [2025-02-05 16:03:46,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:46,770 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 190 transitions. [2025-02-05 16:03:46,770 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 11 states have internal predecessors, (21), 4 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-02-05 16:03:46,771 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 190 transitions. [2025-02-05 16:03:46,771 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-02-05 16:03:46,771 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:46,772 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-02-05 16:03:46,780 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-02-05 16:03:46,972 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-02-05 16:03:46,972 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:46,973 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:46,973 INFO L85 PathProgramCache]: Analyzing trace with hash -67365906, now seen corresponding path program 1 times [2025-02-05 16:03:46,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:46,973 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1468634529] [2025-02-05 16:03:46,973 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:46,973 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:46,982 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-02-05 16:03:47,015 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-02-05 16:03:47,016 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:47,016 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:03:47,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1451693717] [2025-02-05 16:03:47,017 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:47,017 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:47,017 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:47,020 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-02-05 16:03:47,021 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-02-05 16:03:47,098 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-02-05 16:03:47,261 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-02-05 16:03:47,261 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:47,261 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:47,265 INFO L256 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 132 conjuncts are in the unsatisfiable core [2025-02-05 16:03:47,269 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:47,272 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-02-05 16:03:47,278 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-02-05 16:03:47,283 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-02-05 16:03:47,289 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-02-05 16:03:47,295 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-02-05 16:03:48,173 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:03:48,174 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 74 treesize of output 50 [2025-02-05 16:03:48,205 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:03:48,206 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 59 treesize of output 43 [2025-02-05 16:03:48,375 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-05 16:03:48,375 INFO L312 TraceCheckSpWp]: Computing backward predicates...