./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 551b0097 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.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 8571897e57404ad6e85df2c29745d5b56fa4d168673d3bc7c670c79b03a6c106 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 04:12:45,076 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 04:12:45,117 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-01-09 04:12:45,123 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 04:12:45,123 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 04:12:45,142 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 04:12:45,143 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 04:12:45,143 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 04:12:45,143 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 04:12:45,143 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 04:12:45,143 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 04:12:45,143 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 04:12:45,144 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 04:12:45,144 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 04:12:45,144 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 04:12:45,145 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:12:45,145 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:12:45,146 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:12:45,146 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 04:12:45,146 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 04:12:45,147 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 04:12:45,147 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 04:12:45,147 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 04:12:45,147 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 04:12:45,147 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 -> 8571897e57404ad6e85df2c29745d5b56fa4d168673d3bc7c670c79b03a6c106 [2025-01-09 04:12:45,343 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 04:12:45,349 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 04:12:45,351 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 04:12:45,352 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 04:12:45,352 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 04:12:45,353 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c [2025-01-09 04:12:46,511 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/5ca283a26/66282af9d066404c9faef360b8a73dff/FLAGa767421fd [2025-01-09 04:12:46,771 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 04:12:46,772 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c [2025-01-09 04:12:46,780 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/5ca283a26/66282af9d066404c9faef360b8a73dff/FLAGa767421fd [2025-01-09 04:12:46,799 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/5ca283a26/66282af9d066404c9faef360b8a73dff [2025-01-09 04:12:46,801 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 04:12:46,802 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 04:12:46,805 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 04:12:46,805 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 04:12:46,808 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 04:12:46,809 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:46,809 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5bf97972 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46, skipping insertion in model container [2025-01-09 04:12:46,809 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:46,821 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 04:12:46,914 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_hard2.c[1067,1080] [2025-01-09 04:12:46,934 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:12:46,940 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 04:12:46,947 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_hard2.c[1067,1080] [2025-01-09 04:12:46,962 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:12:46,975 INFO L204 MainTranslator]: Completed translation [2025-01-09 04:12:46,976 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46 WrapperNode [2025-01-09 04:12:46,977 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 04:12:46,978 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 04:12:46,978 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 04:12:46,978 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 04:12:46,983 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:46,992 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,006 INFO L138 Inliner]: procedures = 17, calls = 90, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 78 [2025-01-09 04:12:47,007 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 04:12:47,007 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 04:12:47,007 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 04:12:47,008 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 04:12:47,014 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,014 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,016 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,031 INFO L175 MemorySlicer]: Split 56 memory accesses to 8 slices as follows [2, 8, 9, 6, 5, 6, 8, 12]. 21 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8, 0, 0, 0, 0, 0, 0]. The 12 writes are split as follows [0, 0, 3, 2, 1, 1, 2, 3]. [2025-01-09 04:12:47,034 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,034 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,038 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,042 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,043 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,044 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,044 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,048 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 04:12:47,049 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 04:12:47,049 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 04:12:47,049 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 04:12:47,050 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (1/1) ... [2025-01-09 04:12:47,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:12:47,068 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:47,087 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-01-09 04:12:47,098 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_40_to_50_0 [2025-01-09 04:12:47,122 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_40_to_50_0 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2025-01-09 04:12:47,122 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_30_to_37_0 [2025-01-09 04:12:47,122 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_30_to_37_0 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 04:12:47,123 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 04:12:47,123 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 04:12:47,123 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-01-09 04:12:47,224 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 04:12:47,226 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 04:12:47,399 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2025-01-09 04:12:47,400 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 04:12:47,406 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 04:12:47,406 INFO L312 CfgBuilder]: Removed 2 assume(true) statements. [2025-01-09 04:12:47,407 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:12:47 BoogieIcfgContainer [2025-01-09 04:12:47,407 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 04:12:47,408 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 04:12:47,408 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 04:12:47,412 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 04:12:47,412 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 04:12:46" (1/3) ... [2025-01-09 04:12:47,412 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@cec4a2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:12:47, skipping insertion in model container [2025-01-09 04:12:47,412 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:12:46" (2/3) ... [2025-01-09 04:12:47,413 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@cec4a2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:12:47, skipping insertion in model container [2025-01-09 04:12:47,413 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:12:47" (3/3) ... [2025-01-09 04:12:47,413 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_hard2.c [2025-01-09 04:12:47,423 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 04:12:47,424 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_hard2.c that has 4 procedures, 41 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-01-09 04:12:47,457 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 04:12:47,464 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;@3ec20bd2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 04:12:47,465 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 04:12:47,467 INFO L276 IsEmpty]: Start isEmpty. Operand has 41 states, 25 states have (on average 1.28) internal successors, (32), 28 states have internal predecessors, (32), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-01-09 04:12:47,471 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-01-09 04:12:47,472 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:47,472 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:47,472 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:47,475 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:47,476 INFO L85 PathProgramCache]: Analyzing trace with hash -755414079, now seen corresponding path program 1 times [2025-01-09 04:12:47,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:47,481 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [315547709] [2025-01-09 04:12:47,482 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:47,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:47,543 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-01-09 04:12:47,571 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-01-09 04:12:47,572 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:47,574 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:47,962 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:12:47,966 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:47,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [315547709] [2025-01-09 04:12:47,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [315547709] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:47,967 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:12:47,969 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-01-09 04:12:47,969 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [308978392] [2025-01-09 04:12:47,970 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:47,973 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:47,973 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:47,986 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:47,987 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-01-09 04:12:47,989 INFO L87 Difference]: Start difference. First operand has 41 states, 25 states have (on average 1.28) internal successors, (32), 28 states have internal predecessors, (32), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 04:12:48,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:48,145 INFO L93 Difference]: Finished difference Result 83 states and 119 transitions. [2025-01-09 04:12:48,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-09 04:12:48,147 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2025-01-09 04:12:48,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:48,152 INFO L225 Difference]: With dead ends: 83 [2025-01-09 04:12:48,152 INFO L226 Difference]: Without dead ends: 41 [2025-01-09 04:12:48,156 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-01-09 04:12:48,159 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 18 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:48,161 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 246 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:48,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-01-09 04:12:48,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2025-01-09 04:12:48,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 25 states have (on average 1.16) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-01-09 04:12:48,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2025-01-09 04:12:48,189 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 9 [2025-01-09 04:12:48,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:48,189 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2025-01-09 04:12:48,189 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 04:12:48,190 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2025-01-09 04:12:48,190 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2025-01-09 04:12:48,190 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:48,190 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:48,190 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-09 04:12:48,190 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:48,191 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:48,191 INFO L85 PathProgramCache]: Analyzing trace with hash -682913725, now seen corresponding path program 1 times [2025-01-09 04:12:48,191 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:48,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1245216457] [2025-01-09 04:12:48,191 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:48,191 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:48,209 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 15 statements into 1 equivalence classes. [2025-01-09 04:12:48,215 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 15 of 15 statements. [2025-01-09 04:12:48,215 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:48,215 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:48,421 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:12:48,421 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:48,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1245216457] [2025-01-09 04:12:48,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1245216457] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:48,421 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:12:48,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-01-09 04:12:48,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [918088535] [2025-01-09 04:12:48,422 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:48,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:48,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:48,423 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:48,423 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-01-09 04:12:48,423 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-01-09 04:12:48,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:48,549 INFO L93 Difference]: Finished difference Result 47 states and 55 transitions. [2025-01-09 04:12:48,550 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-09 04:12:48,551 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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 15 [2025-01-09 04:12:48,551 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:48,551 INFO L225 Difference]: With dead ends: 47 [2025-01-09 04:12:48,551 INFO L226 Difference]: Without dead ends: 45 [2025-01-09 04:12:48,552 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-01-09 04:12:48,552 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 17 mSDsluCounter, 184 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:48,552 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 226 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:48,553 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-01-09 04:12:48,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2025-01-09 04:12:48,562 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 31 states have internal predecessors, (32), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-01-09 04:12:48,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 53 transitions. [2025-01-09 04:12:48,564 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 53 transitions. Word has length 15 [2025-01-09 04:12:48,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:48,564 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 53 transitions. [2025-01-09 04:12:48,564 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-01-09 04:12:48,564 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 53 transitions. [2025-01-09 04:12:48,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-01-09 04:12:48,565 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:48,565 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:48,565 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-09 04:12:48,565 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:48,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:48,565 INFO L85 PathProgramCache]: Analyzing trace with hash -565463997, now seen corresponding path program 1 times [2025-01-09 04:12:48,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:48,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1386838087] [2025-01-09 04:12:48,565 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:48,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:48,580 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-01-09 04:12:48,593 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-01-09 04:12:48,596 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:48,596 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:48,597 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [728982308] [2025-01-09 04:12:48,600 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:48,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:48,600 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:48,604 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:48,607 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-01-09 04:12:48,666 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-01-09 04:12:48,700 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-01-09 04:12:48,700 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:48,700 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:48,702 INFO L256 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-01-09 04:12:48,706 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:48,741 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:48,746 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:48,753 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:49,038 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:12:49,038 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:49,134 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:12:49,134 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:49,134 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1386838087] [2025-01-09 04:12:49,135 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:49,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [728982308] [2025-01-09 04:12:49,135 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [728982308] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:49,135 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:49,135 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2025-01-09 04:12:49,135 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1240750649] [2025-01-09 04:12:49,135 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:49,136 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:49,136 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:49,136 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:49,136 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2025-01-09 04:12:49,136 INFO L87 Difference]: Start difference. First operand 45 states and 53 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-01-09 04:12:49,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:49,278 INFO L93 Difference]: Finished difference Result 56 states and 66 transitions. [2025-01-09 04:12:49,278 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:12:49,278 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2025-01-09 04:12:49,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:49,280 INFO L225 Difference]: With dead ends: 56 [2025-01-09 04:12:49,280 INFO L226 Difference]: Without dead ends: 54 [2025-01-09 04:12:49,281 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 24 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2025-01-09 04:12:49,281 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 15 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:49,281 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 218 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:49,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2025-01-09 04:12:49,287 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 49. [2025-01-09 04:12:49,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 34 states have internal predecessors, (35), 11 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-01-09 04:12:49,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 56 transitions. [2025-01-09 04:12:49,288 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 56 transitions. Word has length 21 [2025-01-09 04:12:49,288 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:49,288 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 56 transitions. [2025-01-09 04:12:49,288 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-01-09 04:12:49,288 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 56 transitions. [2025-01-09 04:12:49,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-01-09 04:12:49,289 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:49,289 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] [2025-01-09 04:12:49,295 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-01-09 04:12:49,489 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:49,489 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:49,490 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:49,490 INFO L85 PathProgramCache]: Analyzing trace with hash 1188632215, now seen corresponding path program 1 times [2025-01-09 04:12:49,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:49,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680654383] [2025-01-09 04:12:49,490 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:49,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:49,507 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-01-09 04:12:49,518 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-01-09 04:12:49,519 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:49,519 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:49,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [133979742] [2025-01-09 04:12:49,519 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:49,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:49,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:49,524 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:49,528 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-01-09 04:12:49,577 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-01-09 04:12:49,608 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-01-09 04:12:49,608 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:49,608 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:49,614 INFO L256 TraceCheckSpWp]: Trace formula consists of 296 conjuncts, 57 conjuncts are in the unsatisfiable core [2025-01-09 04:12:49,617 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:49,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:49,626 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:49,630 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:49,786 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:49,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-01-09 04:12:49,811 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-09 04:12:49,811 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:49,919 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-09 04:12:49,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:49,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680654383] [2025-01-09 04:12:49,920 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:49,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [133979742] [2025-01-09 04:12:49,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [133979742] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:49,920 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:49,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 9 [2025-01-09 04:12:49,920 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [114679725] [2025-01-09 04:12:49,920 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:49,921 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:49,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:49,921 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:49,921 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2025-01-09 04:12:49,921 INFO L87 Difference]: Start difference. First operand 49 states and 56 transitions. Second operand has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:12:50,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:50,048 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2025-01-09 04:12:50,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:12:50,048 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 33 [2025-01-09 04:12:50,048 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:50,049 INFO L225 Difference]: With dead ends: 69 [2025-01-09 04:12:50,049 INFO L226 Difference]: Without dead ends: 67 [2025-01-09 04:12:50,050 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 53 SyntacticMatches, 4 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2025-01-09 04:12:50,050 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 19 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 244 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:50,050 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 244 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:50,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2025-01-09 04:12:50,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 66. [2025-01-09 04:12:50,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 42 states have (on average 1.1428571428571428) internal successors, (48), 46 states have internal predecessors, (48), 14 states have call successors, (14), 8 states have call predecessors, (14), 9 states have return successors, (17), 13 states have call predecessors, (17), 13 states have call successors, (17) [2025-01-09 04:12:50,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 79 transitions. [2025-01-09 04:12:50,059 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 79 transitions. Word has length 33 [2025-01-09 04:12:50,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:50,059 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 79 transitions. [2025-01-09 04:12:50,059 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:12:50,059 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 79 transitions. [2025-01-09 04:12:50,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2025-01-09 04:12:50,060 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:50,060 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:50,066 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-01-09 04:12:50,264 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:50,264 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:50,265 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:50,265 INFO L85 PathProgramCache]: Analyzing trace with hash 2141026318, now seen corresponding path program 1 times [2025-01-09 04:12:50,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:50,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [294081695] [2025-01-09 04:12:50,265 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:50,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:50,277 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-01-09 04:12:50,288 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-01-09 04:12:50,288 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:50,288 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:50,288 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [529285414] [2025-01-09 04:12:50,289 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:50,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:50,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:50,290 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:50,292 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-01-09 04:12:50,356 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-01-09 04:12:50,389 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-01-09 04:12:50,389 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:50,389 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:50,396 INFO L256 TraceCheckSpWp]: Trace formula consists of 311 conjuncts, 63 conjuncts are in the unsatisfiable core [2025-01-09 04:12:50,399 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:50,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:50,415 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:50,419 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:50,693 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-09 04:12:50,693 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:50,905 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:50,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [294081695] [2025-01-09 04:12:50,906 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:50,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [529285414] [2025-01-09 04:12:50,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [529285414] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:50,906 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:50,906 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2025-01-09 04:12:50,906 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [634384023] [2025-01-09 04:12:50,906 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:50,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 04:12:50,907 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:50,907 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 04:12:50,907 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2025-01-09 04:12:50,907 INFO L87 Difference]: Start difference. First operand 66 states and 79 transitions. Second operand has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-01-09 04:12:51,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:51,278 INFO L93 Difference]: Finished difference Result 123 states and 140 transitions. [2025-01-09 04:12:51,278 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-09 04:12:51,279 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 39 [2025-01-09 04:12:51,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:51,280 INFO L225 Difference]: With dead ends: 123 [2025-01-09 04:12:51,280 INFO L226 Difference]: Without dead ends: 121 [2025-01-09 04:12:51,280 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 39 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=102, Invalid=360, Unknown=0, NotChecked=0, Total=462 [2025-01-09 04:12:51,281 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 78 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 263 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 263 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:51,281 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 125 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 263 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 04:12:51,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2025-01-09 04:12:51,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 119. [2025-01-09 04:12:51,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 77 states have (on average 1.1168831168831168) internal successors, (86), 81 states have internal predecessors, (86), 22 states have call successors, (22), 16 states have call predecessors, (22), 19 states have return successors, (29), 21 states have call predecessors, (29), 20 states have call successors, (29) [2025-01-09 04:12:51,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 137 transitions. [2025-01-09 04:12:51,296 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 137 transitions. Word has length 39 [2025-01-09 04:12:51,296 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:51,296 INFO L471 AbstractCegarLoop]: Abstraction has 119 states and 137 transitions. [2025-01-09 04:12:51,296 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-01-09 04:12:51,296 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 137 transitions. [2025-01-09 04:12:51,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-01-09 04:12:51,297 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:51,297 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:51,304 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-01-09 04:12:51,502 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:51,502 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:51,503 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:51,503 INFO L85 PathProgramCache]: Analyzing trace with hash -684202243, now seen corresponding path program 1 times [2025-01-09 04:12:51,503 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:51,503 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2080348095] [2025-01-09 04:12:51,503 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:51,503 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:51,511 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-01-09 04:12:51,527 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-01-09 04:12:51,527 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:51,527 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:51,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1425007666] [2025-01-09 04:12:51,528 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:51,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:51,528 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:51,530 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:51,535 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-01-09 04:12:51,582 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-01-09 04:12:51,612 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-01-09 04:12:51,612 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:51,612 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:51,613 INFO L256 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-01-09 04:12:51,615 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:51,618 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:51,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:51,759 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:51,807 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:51,810 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-01-09 04:12:51,831 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 4 proven. 30 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-01-09 04:12:51,832 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:52,028 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:52,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2080348095] [2025-01-09 04:12:52,028 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:52,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1425007666] [2025-01-09 04:12:52,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1425007666] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:52,029 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:52,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2025-01-09 04:12:52,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [141793690] [2025-01-09 04:12:52,029 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:52,029 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:52,029 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:52,030 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:52,030 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-01-09 04:12:52,030 INFO L87 Difference]: Start difference. First operand 119 states and 137 transitions. Second operand has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:52,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:52,275 INFO L93 Difference]: Finished difference Result 144 states and 166 transitions. [2025-01-09 04:12:52,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:12:52,275 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 49 [2025-01-09 04:12:52,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:52,280 INFO L225 Difference]: With dead ends: 144 [2025-01-09 04:12:52,281 INFO L226 Difference]: Without dead ends: 140 [2025-01-09 04:12:52,281 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 50 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2025-01-09 04:12:52,281 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 37 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 214 mSolverCounterSat, 33 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 214 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:52,282 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 80 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 214 Invalid, 1 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 04:12:52,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2025-01-09 04:12:52,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 134. [2025-01-09 04:12:52,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 87 states have (on average 1.103448275862069) internal successors, (96), 91 states have internal predecessors, (96), 25 states have call successors, (25), 19 states have call predecessors, (25), 21 states have return successors, (32), 24 states have call predecessors, (32), 22 states have call successors, (32) [2025-01-09 04:12:52,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 153 transitions. [2025-01-09 04:12:52,306 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 153 transitions. Word has length 49 [2025-01-09 04:12:52,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:52,306 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 153 transitions. [2025-01-09 04:12:52,306 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:52,306 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 153 transitions. [2025-01-09 04:12:52,307 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-01-09 04:12:52,307 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:52,307 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:52,315 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-01-09 04:12:52,507 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2025-01-09 04:12:52,508 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:52,509 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:52,509 INFO L85 PathProgramCache]: Analyzing trace with hash 1621802541, now seen corresponding path program 1 times [2025-01-09 04:12:52,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:52,510 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1755480834] [2025-01-09 04:12:52,510 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:52,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:52,522 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-01-09 04:12:52,536 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-01-09 04:12:52,539 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:52,539 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:52,772 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-01-09 04:12:52,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:52,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1755480834] [2025-01-09 04:12:52,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1755480834] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:52,773 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:12:52,773 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-01-09 04:12:52,773 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1720425576] [2025-01-09 04:12:52,773 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:52,773 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-01-09 04:12:52,774 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:52,774 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-01-09 04:12:52,774 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-01-09 04:12:52,774 INFO L87 Difference]: Start difference. First operand 134 states and 153 transitions. Second operand has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-01-09 04:12:52,929 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:52,931 INFO L93 Difference]: Finished difference Result 189 states and 219 transitions. [2025-01-09 04:12:52,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-09 04:12:52,931 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 50 [2025-01-09 04:12:52,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:52,932 INFO L225 Difference]: With dead ends: 189 [2025-01-09 04:12:52,932 INFO L226 Difference]: Without dead ends: 136 [2025-01-09 04:12:52,933 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2025-01-09 04:12:52,933 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 166 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:52,933 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 103 Invalid, 166 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:52,934 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2025-01-09 04:12:52,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 132. [2025-01-09 04:12:52,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 86 states have (on average 1.0930232558139534) internal successors, (94), 90 states have internal predecessors, (94), 25 states have call successors, (25), 19 states have call predecessors, (25), 20 states have return successors, (28), 24 states have call predecessors, (28), 22 states have call successors, (28) [2025-01-09 04:12:52,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 147 transitions. [2025-01-09 04:12:52,958 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 147 transitions. Word has length 50 [2025-01-09 04:12:52,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:52,959 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 147 transitions. [2025-01-09 04:12:52,959 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-01-09 04:12:52,959 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 147 transitions. [2025-01-09 04:12:52,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-01-09 04:12:52,960 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:52,960 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:52,960 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-01-09 04:12:52,960 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:52,960 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:52,960 INFO L85 PathProgramCache]: Analyzing trace with hash 377968636, now seen corresponding path program 1 times [2025-01-09 04:12:52,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:52,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553196533] [2025-01-09 04:12:52,961 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:52,961 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:52,975 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-01-09 04:12:52,981 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-01-09 04:12:52,981 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:52,981 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:53,162 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-01-09 04:12:53,162 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:53,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553196533] [2025-01-09 04:12:53,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [553196533] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:53,163 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:12:53,163 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-01-09 04:12:53,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [456001830] [2025-01-09 04:12:53,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:53,163 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-01-09 04:12:53,163 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:53,164 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-01-09 04:12:53,164 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-01-09 04:12:53,164 INFO L87 Difference]: Start difference. First operand 132 states and 147 transitions. Second operand has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-01-09 04:12:53,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:53,291 INFO L93 Difference]: Finished difference Result 138 states and 154 transitions. [2025-01-09 04:12:53,291 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-09 04:12:53,291 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2025-01-09 04:12:53,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:53,292 INFO L225 Difference]: With dead ends: 138 [2025-01-09 04:12:53,294 INFO L226 Difference]: Without dead ends: 106 [2025-01-09 04:12:53,294 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-01-09 04:12:53,294 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 6 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 134 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 146 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 134 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:53,295 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 118 Invalid, 146 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 134 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:53,295 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2025-01-09 04:12:53,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 102. [2025-01-09 04:12:53,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 66 states have (on average 1.106060606060606) internal successors, (73), 70 states have internal predecessors, (73), 20 states have call successors, (20), 14 states have call predecessors, (20), 15 states have return successors, (23), 19 states have call predecessors, (23), 18 states have call successors, (23) [2025-01-09 04:12:53,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 116 transitions. [2025-01-09 04:12:53,312 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 116 transitions. Word has length 55 [2025-01-09 04:12:53,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:53,312 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 116 transitions. [2025-01-09 04:12:53,312 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-01-09 04:12:53,312 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 116 transitions. [2025-01-09 04:12:53,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-01-09 04:12:53,313 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:53,313 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:53,313 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2025-01-09 04:12:53,313 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:53,314 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:53,314 INFO L85 PathProgramCache]: Analyzing trace with hash 380342299, now seen corresponding path program 1 times [2025-01-09 04:12:53,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:53,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [939228855] [2025-01-09 04:12:53,314 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:53,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:53,326 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-01-09 04:12:53,338 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-01-09 04:12:53,338 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:53,338 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:53,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [186416217] [2025-01-09 04:12:53,339 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:53,339 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:53,339 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:53,341 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:53,342 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-01-09 04:12:53,400 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-01-09 04:12:53,441 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-01-09 04:12:53,441 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:53,441 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:53,449 INFO L256 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 87 conjuncts are in the unsatisfiable core [2025-01-09 04:12:53,452 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:53,457 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:53,460 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:53,463 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:53,752 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:53,756 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:53,945 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 24 proven. 24 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-01-09 04:12:53,946 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:54,256 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:54,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [939228855] [2025-01-09 04:12:54,256 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:54,256 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186416217] [2025-01-09 04:12:54,256 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186416217] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:54,256 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:54,256 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-01-09 04:12:54,256 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [591136171] [2025-01-09 04:12:54,257 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:54,257 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-01-09 04:12:54,257 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:54,257 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-01-09 04:12:54,258 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=320, Unknown=0, NotChecked=0, Total=380 [2025-01-09 04:12:54,258 INFO L87 Difference]: Start difference. First operand 102 states and 116 transitions. Second operand has 15 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 12 states have internal predecessors, (28), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2025-01-09 04:12:54,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:54,907 INFO L93 Difference]: Finished difference Result 142 states and 161 transitions. [2025-01-09 04:12:54,907 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-01-09 04:12:54,908 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 12 states have internal predecessors, (28), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 63 [2025-01-09 04:12:54,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:54,909 INFO L225 Difference]: With dead ends: 142 [2025-01-09 04:12:54,909 INFO L226 Difference]: Without dead ends: 138 [2025-01-09 04:12:54,909 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 58 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=120, Invalid=530, Unknown=0, NotChecked=0, Total=650 [2025-01-09 04:12:54,910 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 52 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 497 mSolverCounterSat, 25 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 524 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 497 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:54,910 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 156 Invalid, 524 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 497 Invalid, 2 Unknown, 0 Unchecked, 0.5s Time] [2025-01-09 04:12:54,910 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2025-01-09 04:12:54,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 134. [2025-01-09 04:12:54,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 87 states have (on average 1.0919540229885059) internal successors, (95), 90 states have internal predecessors, (95), 25 states have call successors, (25), 19 states have call predecessors, (25), 21 states have return successors, (33), 25 states have call predecessors, (33), 22 states have call successors, (33) [2025-01-09 04:12:54,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 153 transitions. [2025-01-09 04:12:54,935 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 153 transitions. Word has length 63 [2025-01-09 04:12:54,935 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:54,935 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 153 transitions. [2025-01-09 04:12:54,935 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 12 states have internal predecessors, (28), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2025-01-09 04:12:54,935 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 153 transitions. [2025-01-09 04:12:54,936 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-01-09 04:12:54,936 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:54,936 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:54,943 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-01-09 04:12:55,136 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:55,137 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:55,137 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:55,137 INFO L85 PathProgramCache]: Analyzing trace with hash -941273112, now seen corresponding path program 2 times [2025-01-09 04:12:55,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:55,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1934317070] [2025-01-09 04:12:55,137 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:12:55,137 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:55,151 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 87 statements into 2 equivalence classes. [2025-01-09 04:12:55,171 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 87 of 87 statements. [2025-01-09 04:12:55,172 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:12:55,172 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:55,173 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1186138676] [2025-01-09 04:12:55,173 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:12:55,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:55,174 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:55,178 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:55,179 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-01-09 04:12:55,248 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 87 statements into 2 equivalence classes. [2025-01-09 04:12:55,305 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 87 of 87 statements. [2025-01-09 04:12:55,305 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:12:55,305 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:55,312 INFO L256 TraceCheckSpWp]: Trace formula consists of 523 conjuncts, 107 conjuncts are in the unsatisfiable core [2025-01-09 04:12:55,318 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:55,324 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:55,327 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:55,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:55,779 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:55,783 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:55,984 INFO L134 CoverageAnalysis]: Checked inductivity of 234 backedges. 36 proven. 43 refuted. 0 times theorem prover too weak. 155 trivial. 0 not checked. [2025-01-09 04:12:55,984 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:56,537 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:56,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1934317070] [2025-01-09 04:12:56,538 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:56,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1186138676] [2025-01-09 04:12:56,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1186138676] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:56,538 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:56,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2025-01-09 04:12:56,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1096173601] [2025-01-09 04:12:56,538 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:56,538 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-01-09 04:12:56,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:56,539 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-01-09 04:12:56,539 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=432, Unknown=0, NotChecked=0, Total=506 [2025-01-09 04:12:56,539 INFO L87 Difference]: Start difference. First operand 134 states and 153 transitions. Second operand has 17 states, 12 states have (on average 2.5) internal successors, (30), 14 states have internal predecessors, (30), 8 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2025-01-09 04:12:57,248 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:57,248 INFO L93 Difference]: Finished difference Result 172 states and 195 transitions. [2025-01-09 04:12:57,248 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-01-09 04:12:57,249 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 12 states have (on average 2.5) internal successors, (30), 14 states have internal predecessors, (30), 8 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) Word has length 87 [2025-01-09 04:12:57,249 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:57,250 INFO L225 Difference]: With dead ends: 172 [2025-01-09 04:12:57,250 INFO L226 Difference]: Without dead ends: 168 [2025-01-09 04:12:57,250 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 79 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=134, Invalid=678, Unknown=0, NotChecked=0, Total=812 [2025-01-09 04:12:57,251 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 44 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 605 mSolverCounterSat, 20 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 626 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 605 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:57,251 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 211 Invalid, 626 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 605 Invalid, 1 Unknown, 0 Unchecked, 0.5s Time] [2025-01-09 04:12:57,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2025-01-09 04:12:57,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 136. [2025-01-09 04:12:57,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 88 states have (on average 1.0909090909090908) internal successors, (96), 91 states have internal predecessors, (96), 25 states have call successors, (25), 19 states have call predecessors, (25), 22 states have return successors, (35), 26 states have call predecessors, (35), 22 states have call successors, (35) [2025-01-09 04:12:57,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 156 transitions. [2025-01-09 04:12:57,266 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 156 transitions. Word has length 87 [2025-01-09 04:12:57,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:57,266 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 156 transitions. [2025-01-09 04:12:57,267 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 12 states have (on average 2.5) internal successors, (30), 14 states have internal predecessors, (30), 8 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2025-01-09 04:12:57,267 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 156 transitions. [2025-01-09 04:12:57,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2025-01-09 04:12:57,268 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:57,268 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:57,275 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-01-09 04:12:57,468 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-01-09 04:12:57,469 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:57,469 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:57,469 INFO L85 PathProgramCache]: Analyzing trace with hash -2016753803, now seen corresponding path program 3 times [2025-01-09 04:12:57,469 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:57,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [324079838] [2025-01-09 04:12:57,469 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 04:12:57,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:57,483 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 111 statements into 6 equivalence classes. [2025-01-09 04:12:57,527 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 111 of 111 statements. [2025-01-09 04:12:57,528 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-09 04:12:57,528 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:57,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [159906875] [2025-01-09 04:12:57,531 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 04:12:57,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:57,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:57,535 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:57,536 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-01-09 04:12:57,608 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 111 statements into 6 equivalence classes. [2025-01-09 04:12:57,733 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 83 of 111 statements. [2025-01-09 04:12:57,733 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-01-09 04:12:57,733 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:57,740 INFO L256 TraceCheckSpWp]: Trace formula consists of 571 conjuncts, 168 conjuncts are in the unsatisfiable core [2025-01-09 04:12:57,747 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:57,757 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 95 treesize of output 93 [2025-01-09 04:12:57,768 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:57,774 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:57,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:12:57,799 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2025-01-09 04:12:58,486 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:58,494 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:58,796 INFO L134 CoverageAnalysis]: Checked inductivity of 407 backedges. 48 proven. 64 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2025-01-09 04:12:58,797 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:59,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:59,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [324079838] [2025-01-09 04:12:59,832 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:59,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [159906875] [2025-01-09 04:12:59,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [159906875] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:59,832 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:59,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2025-01-09 04:12:59,834 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [927950520] [2025-01-09 04:12:59,834 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:59,834 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-01-09 04:12:59,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:59,834 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-01-09 04:12:59,835 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=566, Unknown=0, NotChecked=0, Total=650 [2025-01-09 04:12:59,835 INFO L87 Difference]: Start difference. First operand 136 states and 156 transitions. Second operand has 18 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 15 states have internal predecessors, (31), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2025-01-09 04:13:00,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:00,613 INFO L93 Difference]: Finished difference Result 174 states and 198 transitions. [2025-01-09 04:13:00,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-01-09 04:13:00,613 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 15 states have internal predecessors, (31), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) Word has length 111 [2025-01-09 04:13:00,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:00,615 INFO L225 Difference]: With dead ends: 174 [2025-01-09 04:13:00,615 INFO L226 Difference]: Without dead ends: 170 [2025-01-09 04:13:00,615 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 102 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 228 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=147, Invalid=845, Unknown=0, NotChecked=0, Total=992 [2025-01-09 04:13:00,615 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 49 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 23 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 648 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:00,616 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 203 Invalid, 648 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 622 Invalid, 3 Unknown, 0 Unchecked, 0.6s Time] [2025-01-09 04:13:00,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2025-01-09 04:13:00,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 138. [2025-01-09 04:13:00,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 89 states have (on average 1.0898876404494382) internal successors, (97), 92 states have internal predecessors, (97), 25 states have call successors, (25), 19 states have call predecessors, (25), 23 states have return successors, (37), 27 states have call predecessors, (37), 22 states have call successors, (37) [2025-01-09 04:13:00,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 159 transitions. [2025-01-09 04:13:00,660 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 159 transitions. Word has length 111 [2025-01-09 04:13:00,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:00,660 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 159 transitions. [2025-01-09 04:13:00,660 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 15 states have internal predecessors, (31), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2025-01-09 04:13:00,660 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 159 transitions. [2025-01-09 04:13:00,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2025-01-09 04:13:00,662 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:00,662 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:13:00,669 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-01-09 04:13:00,862 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:00,863 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:00,863 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:00,863 INFO L85 PathProgramCache]: Analyzing trace with hash 974653122, now seen corresponding path program 4 times [2025-01-09 04:13:00,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:00,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [785397481] [2025-01-09 04:13:00,863 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-09 04:13:00,863 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:00,878 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 135 statements into 2 equivalence classes. [2025-01-09 04:13:00,926 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 135 of 135 statements. [2025-01-09 04:13:00,926 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-01-09 04:13:00,926 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:13:00,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [400760796] [2025-01-09 04:13:00,929 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-09 04:13:00,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:00,929 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:00,931 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:00,933 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-01-09 04:13:01,030 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 135 statements into 2 equivalence classes. [2025-01-09 04:13:01,123 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 133 of 135 statements. [2025-01-09 04:13:01,123 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-01-09 04:13:01,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:01,127 INFO L256 TraceCheckSpWp]: Trace formula consists of 612 conjuncts, 170 conjuncts are in the unsatisfiable core [2025-01-09 04:13:01,132 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:05,617 WARN L873 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_40_to_50_0_~d.base_BEFORE_CALL_9 Int) (v_func_to_recursive_line_40_to_50_0_~p.offset_BEFORE_CALL_9 Int) (v_func_to_recursive_line_40_to_50_0_~B.base_BEFORE_CALL_9 Int) (v_func_to_recursive_line_40_to_50_0_~p.base_BEFORE_CALL_9 Int) (v_func_to_recursive_line_40_to_50_0_~B.offset_BEFORE_CALL_9 Int) (v_func_to_recursive_line_40_to_50_0_~d.offset_BEFORE_CALL_9 Int)) (= (select (select |c_#memory_int#7| v_func_to_recursive_line_40_to_50_0_~d.base_BEFORE_CALL_9) v_func_to_recursive_line_40_to_50_0_~d.offset_BEFORE_CALL_9) (* (select (select |c_#memory_int#2| v_func_to_recursive_line_40_to_50_0_~p.base_BEFORE_CALL_9) v_func_to_recursive_line_40_to_50_0_~p.offset_BEFORE_CALL_9) (select (select |c_#memory_int#5| v_func_to_recursive_line_40_to_50_0_~B.base_BEFORE_CALL_9) v_func_to_recursive_line_40_to_50_0_~B.offset_BEFORE_CALL_9)))) is different from true [2025-01-09 04:13:05,654 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2025-01-09 04:13:05,656 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-01-09 04:13:05,658 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-01-09 04:13:05,690 INFO L134 CoverageAnalysis]: Checked inductivity of 628 backedges. 128 proven. 13 refuted. 0 times theorem prover too weak. 482 trivial. 5 not checked. [2025-01-09 04:13:05,690 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:13:06,563 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:06,563 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 36 treesize of output 39 [2025-01-09 04:13:06,570 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:06,571 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 28 treesize of output 31 [2025-01-09 04:13:06,584 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:06,584 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 20 treesize of output 23 [2025-01-09 04:13:06,920 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:06,920 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 36 treesize of output 39 [2025-01-09 04:13:06,926 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:06,926 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 28 treesize of output 31 [2025-01-09 04:13:06,941 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:06,941 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 20 treesize of output 23 [2025-01-09 04:13:07,150 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,150 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 36 treesize of output 39 [2025-01-09 04:13:07,156 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,157 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 28 treesize of output 31 [2025-01-09 04:13:07,172 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,172 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 20 treesize of output 23 [2025-01-09 04:13:07,309 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,309 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 36 treesize of output 39 [2025-01-09 04:13:07,319 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,319 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 28 treesize of output 31 [2025-01-09 04:13:07,329 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,330 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 20 treesize of output 23 [2025-01-09 04:13:07,479 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,479 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 36 treesize of output 39 [2025-01-09 04:13:07,485 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,485 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 28 treesize of output 31 [2025-01-09 04:13:07,492 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:07,492 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 20 treesize of output 23 [2025-01-09 04:13:07,885 INFO L134 CoverageAnalysis]: Checked inductivity of 628 backedges. 73 proven. 16 refuted. 0 times theorem prover too weak. 539 trivial. 0 not checked. [2025-01-09 04:13:07,885 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:07,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [785397481] [2025-01-09 04:13:07,885 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:13:07,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [400760796] [2025-01-09 04:13:07,885 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [400760796] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 04:13:07,885 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 04:13:07,885 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 17 [2025-01-09 04:13:07,886 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [612759210] [2025-01-09 04:13:07,886 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 04:13:07,886 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-01-09 04:13:07,886 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:13:07,886 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-01-09 04:13:07,886 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=203, Unknown=1, NotChecked=28, Total=272 [2025-01-09 04:13:07,886 INFO L87 Difference]: Start difference. First operand 138 states and 159 transitions. Second operand has 17 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 14 states have internal predecessors, (31), 7 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2025-01-09 04:13:23,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:23,942 INFO L93 Difference]: Finished difference Result 160 states and 182 transitions. [2025-01-09 04:13:23,942 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-01-09 04:13:23,942 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 14 states have internal predecessors, (31), 7 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) Word has length 135 [2025-01-09 04:13:23,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:23,943 INFO L225 Difference]: With dead ends: 160 [2025-01-09 04:13:23,943 INFO L226 Difference]: Without dead ends: 158 [2025-01-09 04:13:23,944 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 250 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 19.9s TimeCoverageRelationStatistics Valid=79, Invalid=428, Unknown=3, NotChecked=42, Total=552 [2025-01-09 04:13:23,944 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 21 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 386 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 479 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 386 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 77 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:23,944 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 229 Invalid, 479 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 386 Invalid, 0 Unknown, 77 Unchecked, 0.3s Time] [2025-01-09 04:13:23,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2025-01-09 04:13:23,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 155. [2025-01-09 04:13:23,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 101 states have (on average 1.0891089108910892) internal successors, (110), 104 states have internal predecessors, (110), 27 states have call successors, (27), 22 states have call predecessors, (27), 26 states have return successors, (39), 29 states have call predecessors, (39), 24 states have call successors, (39) [2025-01-09 04:13:23,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 176 transitions. [2025-01-09 04:13:23,964 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 176 transitions. Word has length 135 [2025-01-09 04:13:23,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:23,964 INFO L471 AbstractCegarLoop]: Abstraction has 155 states and 176 transitions. [2025-01-09 04:13:23,964 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 14 states have internal predecessors, (31), 7 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2025-01-09 04:13:23,964 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 176 transitions. [2025-01-09 04:13:23,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-01-09 04:13:23,965 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:23,965 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:13:23,972 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-01-09 04:13:24,165 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:24,165 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:24,166 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:24,166 INFO L85 PathProgramCache]: Analyzing trace with hash -2140992512, now seen corresponding path program 1 times [2025-01-09 04:13:24,166 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:24,166 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1305558936] [2025-01-09 04:13:24,166 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:24,166 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:24,180 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-01-09 04:13:24,195 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-01-09 04:13:24,195 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:24,195 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:13:24,196 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [499177891] [2025-01-09 04:13:24,196 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:24,197 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:24,197 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:24,198 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:24,200 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-01-09 04:13:24,281 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-01-09 04:13:24,336 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-01-09 04:13:24,336 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:24,336 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:24,340 INFO L256 TraceCheckSpWp]: Trace formula consists of 514 conjuncts, 181 conjuncts are in the unsatisfiable core [2025-01-09 04:13:24,344 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:24,347 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:24,350 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:13:24,351 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:24,354 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:24,360 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:24,364 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:24,761 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:24,774 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:25,172 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:25,180 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:25,234 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-01-09 04:13:25,234 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-01-09 04:13:25,262 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2025-01-09 04:13:25,262 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 51 [2025-01-09 04:13:25,477 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:25,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 88 treesize of output 172 [2025-01-09 04:13:25,509 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:25,509 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 56 treesize of output 108 [2025-01-09 04:13:25,621 INFO L134 CoverageAnalysis]: Checked inductivity of 142 backedges. 48 proven. 29 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2025-01-09 04:13:25,622 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:13:29,392 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:29,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1305558936] [2025-01-09 04:13:29,393 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:13:29,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [499177891] [2025-01-09 04:13:29,393 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [499177891] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:29,393 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:13:29,393 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2025-01-09 04:13:29,393 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1942114749] [2025-01-09 04:13:29,393 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:13:29,394 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-01-09 04:13:29,394 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:13:29,394 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-01-09 04:13:29,394 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=572, Unknown=0, NotChecked=0, Total=650 [2025-01-09 04:13:29,394 INFO L87 Difference]: Start difference. First operand 155 states and 176 transitions. Second operand has 17 states, 14 states have (on average 2.357142857142857) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2025-01-09 04:13:30,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:30,556 INFO L93 Difference]: Finished difference Result 211 states and 246 transitions. [2025-01-09 04:13:30,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-01-09 04:13:30,556 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 2.357142857142857) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 74 [2025-01-09 04:13:30,556 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:30,558 INFO L225 Difference]: With dead ends: 211 [2025-01-09 04:13:30,558 INFO L226 Difference]: Without dead ends: 209 [2025-01-09 04:13:30,558 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 72 SyntacticMatches, 5 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 238 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=125, Invalid=867, Unknown=0, NotChecked=0, Total=992 [2025-01-09 04:13:30,558 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 84 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 728 mSolverCounterSat, 38 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 768 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 728 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:30,559 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [88 Valid, 225 Invalid, 768 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 728 Invalid, 2 Unknown, 0 Unchecked, 0.8s Time] [2025-01-09 04:13:30,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2025-01-09 04:13:30,585 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 194. [2025-01-09 04:13:30,586 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 126 states have (on average 1.1031746031746033) internal successors, (139), 131 states have internal predecessors, (139), 34 states have call successors, (34), 27 states have call predecessors, (34), 33 states have return successors, (55), 36 states have call predecessors, (55), 31 states have call successors, (55) [2025-01-09 04:13:30,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 228 transitions. [2025-01-09 04:13:30,587 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 228 transitions. Word has length 74 [2025-01-09 04:13:30,587 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:30,587 INFO L471 AbstractCegarLoop]: Abstraction has 194 states and 228 transitions. [2025-01-09 04:13:30,587 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 2.357142857142857) internal successors, (33), 13 states have internal predecessors, (33), 8 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2025-01-09 04:13:30,588 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 228 transitions. [2025-01-09 04:13:30,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-01-09 04:13:30,588 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:30,588 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:13:30,595 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-01-09 04:13:30,789 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:30,789 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:30,789 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:30,789 INFO L85 PathProgramCache]: Analyzing trace with hash -1255319021, now seen corresponding path program 2 times [2025-01-09 04:13:30,790 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:30,790 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1867453331] [2025-01-09 04:13:30,790 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:13:30,790 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:30,799 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 98 statements into 2 equivalence classes. [2025-01-09 04:13:30,824 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 98 of 98 statements. [2025-01-09 04:13:30,825 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:13:30,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:13:30,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [447038274] [2025-01-09 04:13:30,827 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:13:30,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:30,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:30,830 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:30,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-01-09 04:13:30,917 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 98 statements into 2 equivalence classes. [2025-01-09 04:13:30,991 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 98 of 98 statements. [2025-01-09 04:13:30,991 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:13:30,991 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:30,995 INFO L256 TraceCheckSpWp]: Trace formula consists of 620 conjuncts, 201 conjuncts are in the unsatisfiable core [2025-01-09 04:13:30,999 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:31,004 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:31,007 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:31,011 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:13:31,014 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:31,018 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:31,022 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:31,711 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:31,717 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:32,145 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:32,156 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:32,217 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2025-01-09 04:13:32,217 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 51 [2025-01-09 04:13:32,250 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-01-09 04:13:32,250 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-01-09 04:13:32,450 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:32,450 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 92 treesize of output 184 [2025-01-09 04:13:32,482 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:32,482 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 68 treesize of output 112 [2025-01-09 04:13:32,630 INFO L134 CoverageAnalysis]: Checked inductivity of 279 backedges. 72 proven. 48 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2025-01-09 04:13:32,631 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:13:39,013 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:39,014 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1867453331] [2025-01-09 04:13:39,014 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:13:39,014 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [447038274] [2025-01-09 04:13:39,014 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [447038274] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:39,014 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:13:39,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-01-09 04:13:39,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [601982803] [2025-01-09 04:13:39,014 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:13:39,015 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-01-09 04:13:39,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:13:39,015 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-01-09 04:13:39,015 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=776, Unknown=1, NotChecked=0, Total=870 [2025-01-09 04:13:39,016 INFO L87 Difference]: Start difference. First operand 194 states and 228 transitions. Second operand has 20 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 16 states have internal predecessors, (35), 9 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2025-01-09 04:13:41,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:41,099 INFO L93 Difference]: Finished difference Result 250 states and 298 transitions. [2025-01-09 04:13:41,100 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-01-09 04:13:41,100 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 16 states have internal predecessors, (35), 9 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) Word has length 98 [2025-01-09 04:13:41,100 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:41,101 INFO L225 Difference]: With dead ends: 250 [2025-01-09 04:13:41,101 INFO L226 Difference]: Without dead ends: 248 [2025-01-09 04:13:41,102 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 92 SyntacticMatches, 5 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 373 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=140, Invalid=1119, Unknown=1, NotChecked=0, Total=1260 [2025-01-09 04:13:41,102 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 58 mSDsluCounter, 300 mSDsCounter, 0 mSdLazyCounter, 1168 mSolverCounterSat, 24 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 346 SdHoareTripleChecker+Invalid, 1193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 1168 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:41,102 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 346 Invalid, 1193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 1168 Invalid, 1 Unknown, 0 Unchecked, 1.6s Time] [2025-01-09 04:13:41,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2025-01-09 04:13:41,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 194. [2025-01-09 04:13:41,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 126 states have (on average 1.1031746031746033) internal successors, (139), 131 states have internal predecessors, (139), 34 states have call successors, (34), 27 states have call predecessors, (34), 33 states have return successors, (55), 36 states have call predecessors, (55), 31 states have call successors, (55) [2025-01-09 04:13:41,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 228 transitions. [2025-01-09 04:13:41,143 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 228 transitions. Word has length 98 [2025-01-09 04:13:41,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:41,144 INFO L471 AbstractCegarLoop]: Abstraction has 194 states and 228 transitions. [2025-01-09 04:13:41,144 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 16 states have internal predecessors, (35), 9 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2025-01-09 04:13:41,144 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 228 transitions. [2025-01-09 04:13:41,145 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-01-09 04:13:41,145 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:41,145 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:13:41,156 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-01-09 04:13:41,350 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-01-09 04:13:41,350 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:41,350 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:41,350 INFO L85 PathProgramCache]: Analyzing trace with hash 1423939686, now seen corresponding path program 3 times [2025-01-09 04:13:41,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:41,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55514309] [2025-01-09 04:13:41,350 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 04:13:41,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:41,366 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 122 statements into 7 equivalence classes. [2025-01-09 04:13:41,445 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 122 of 122 statements. [2025-01-09 04:13:41,445 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-01-09 04:13:41,445 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:13:41,447 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [933920670] [2025-01-09 04:13:41,447 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 04:13:41,447 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:41,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:41,449 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:41,454 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-01-09 04:13:41,550 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 122 statements into 7 equivalence classes. [2025-01-09 04:13:42,058 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 86 of 122 statements. [2025-01-09 04:13:42,058 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-01-09 04:13:42,058 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:42,068 INFO L256 TraceCheckSpWp]: Trace formula consists of 651 conjuncts, 284 conjuncts are in the unsatisfiable core [2025-01-09 04:13:42,074 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:42,081 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:42,089 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:42,094 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:42,100 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:42,109 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:13:42,113 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:43,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:43,540 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:44,160 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:44,166 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:44,247 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2025-01-09 04:13:44,248 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 43 [2025-01-09 04:13:44,275 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2025-01-09 04:13:44,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2025-01-09 04:13:44,462 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:44,463 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 72 treesize of output 88 [2025-01-09 04:13:44,491 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:13:44,491 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 98 treesize of output 86 [2025-01-09 04:13:44,571 INFO L134 CoverageAnalysis]: Checked inductivity of 464 backedges. 96 proven. 85 refuted. 0 times theorem prover too weak. 283 trivial. 0 not checked. [2025-01-09 04:13:44,572 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:13:48,324 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:48,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55514309] [2025-01-09 04:13:48,324 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:13:48,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [933920670] [2025-01-09 04:13:48,324 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [933920670] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:48,324 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:13:48,324 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-01-09 04:13:48,324 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1250130327] [2025-01-09 04:13:48,325 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:13:48,325 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-01-09 04:13:48,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:13:48,325 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-01-09 04:13:48,325 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=1077, Unknown=0, NotChecked=0, Total=1190 [2025-01-09 04:13:48,325 INFO L87 Difference]: Start difference. First operand 194 states and 228 transitions. Second operand has 23 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 19 states have internal predecessors, (41), 10 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (15), 8 states have call predecessors, (15), 7 states have call successors, (15) [2025-01-09 04:13:50,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:50,488 INFO L93 Difference]: Finished difference Result 232 states and 277 transitions. [2025-01-09 04:13:50,488 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-01-09 04:13:50,488 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 19 states have internal predecessors, (41), 10 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (15), 8 states have call predecessors, (15), 7 states have call successors, (15) Word has length 122 [2025-01-09 04:13:50,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:50,491 INFO L225 Difference]: With dead ends: 232 [2025-01-09 04:13:50,491 INFO L226 Difference]: Without dead ends: 230 [2025-01-09 04:13:50,491 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 113 SyntacticMatches, 3 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 544 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=162, Invalid=1478, Unknown=0, NotChecked=0, Total=1640 [2025-01-09 04:13:50,492 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 63 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 1218 mSolverCounterSat, 26 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 353 SdHoareTripleChecker+Invalid, 1248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 1218 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:50,492 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 353 Invalid, 1248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 1218 Invalid, 4 Unknown, 0 Unchecked, 1.6s Time] [2025-01-09 04:13:50,492 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2025-01-09 04:13:50,530 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 176. [2025-01-09 04:13:50,531 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 114 states have (on average 1.105263157894737) internal successors, (126), 119 states have internal predecessors, (126), 31 states have call successors, (31), 24 states have call predecessors, (31), 30 states have return successors, (50), 33 states have call predecessors, (50), 28 states have call successors, (50) [2025-01-09 04:13:50,532 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 207 transitions. [2025-01-09 04:13:50,532 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 207 transitions. Word has length 122 [2025-01-09 04:13:50,532 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:50,532 INFO L471 AbstractCegarLoop]: Abstraction has 176 states and 207 transitions. [2025-01-09 04:13:50,532 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 19 states have internal predecessors, (41), 10 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (15), 8 states have call predecessors, (15), 7 states have call successors, (15) [2025-01-09 04:13:50,533 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 207 transitions. [2025-01-09 04:13:50,533 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2025-01-09 04:13:50,533 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:50,533 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:13:50,542 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-01-09 04:13:50,734 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-01-09 04:13:50,734 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:50,735 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:50,735 INFO L85 PathProgramCache]: Analyzing trace with hash -687491575, now seen corresponding path program 1 times [2025-01-09 04:13:50,735 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:50,735 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [720013835] [2025-01-09 04:13:50,735 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:50,735 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:50,743 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 79 statements into 1 equivalence classes. [2025-01-09 04:13:50,748 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 79 of 79 statements. [2025-01-09 04:13:50,748 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:50,748 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:50,952 INFO L134 CoverageAnalysis]: Checked inductivity of 173 backedges. 19 proven. 10 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2025-01-09 04:13:50,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:50,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [720013835] [2025-01-09 04:13:50,952 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [720013835] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:50,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2128117632] [2025-01-09 04:13:50,952 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:50,952 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:50,952 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:50,956 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:50,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-01-09 04:13:51,047 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 79 statements into 1 equivalence classes. [2025-01-09 04:13:51,085 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 79 of 79 statements. [2025-01-09 04:13:51,085 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:51,085 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:51,087 INFO L256 TraceCheckSpWp]: Trace formula consists of 453 conjuncts, 28 conjuncts are in the unsatisfiable core [2025-01-09 04:13:51,089 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:51,092 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:13:51,186 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:13:51,250 INFO L134 CoverageAnalysis]: Checked inductivity of 173 backedges. 48 proven. 10 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2025-01-09 04:13:51,251 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:13:51,506 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2025-01-09 04:13:51,546 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2128117632] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:51,546 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 04:13:51,546 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2025-01-09 04:13:51,546 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619040434] [2025-01-09 04:13:51,546 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 04:13:51,547 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-09 04:13:51,547 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:13:51,548 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-09 04:13:51,548 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=466, Unknown=0, NotChecked=0, Total=552 [2025-01-09 04:13:51,548 INFO L87 Difference]: Start difference. First operand 176 states and 207 transitions. Second operand has 16 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 14 states have internal predecessors, (43), 11 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (19), 9 states have call predecessors, (19), 11 states have call successors, (19) [2025-01-09 04:13:51,918 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:51,919 INFO L93 Difference]: Finished difference Result 193 states and 228 transitions. [2025-01-09 04:13:51,919 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-01-09 04:13:51,919 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 14 states have internal predecessors, (43), 11 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (19), 9 states have call predecessors, (19), 11 states have call successors, (19) Word has length 79 [2025-01-09 04:13:51,919 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:51,921 INFO L225 Difference]: With dead ends: 193 [2025-01-09 04:13:51,922 INFO L226 Difference]: Without dead ends: 165 [2025-01-09 04:13:51,923 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=134, Invalid=678, Unknown=0, NotChecked=0, Total=812 [2025-01-09 04:13:51,923 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 20 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 456 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 475 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 456 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:51,923 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 243 Invalid, 475 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 456 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 04:13:51,924 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2025-01-09 04:13:51,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 164. [2025-01-09 04:13:51,961 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 106 states have (on average 1.0943396226415094) internal successors, (116), 110 states have internal predecessors, (116), 29 states have call successors, (29), 22 states have call predecessors, (29), 28 states have return successors, (49), 31 states have call predecessors, (49), 27 states have call successors, (49) [2025-01-09 04:13:51,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 194 transitions. [2025-01-09 04:13:51,963 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 194 transitions. Word has length 79 [2025-01-09 04:13:51,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:51,964 INFO L471 AbstractCegarLoop]: Abstraction has 164 states and 194 transitions. [2025-01-09 04:13:51,964 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 14 states have internal predecessors, (43), 11 states have call successors, (20), 3 states have call predecessors, (20), 7 states have return successors, (19), 9 states have call predecessors, (19), 11 states have call successors, (19) [2025-01-09 04:13:51,964 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 194 transitions. [2025-01-09 04:13:51,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-01-09 04:13:51,965 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:51,965 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:13:51,973 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-01-09 04:13:52,165 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:52,166 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:52,166 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:52,166 INFO L85 PathProgramCache]: Analyzing trace with hash 2068155893, now seen corresponding path program 1 times [2025-01-09 04:13:52,167 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:52,167 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1739289304] [2025-01-09 04:13:52,167 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:52,167 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:52,179 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-01-09 04:13:52,186 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-01-09 04:13:52,187 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:52,187 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:53,022 INFO L134 CoverageAnalysis]: Checked inductivity of 178 backedges. 23 proven. 10 refuted. 0 times theorem prover too weak. 145 trivial. 0 not checked. [2025-01-09 04:13:53,022 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:53,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1739289304] [2025-01-09 04:13:53,022 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1739289304] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:53,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1773638722] [2025-01-09 04:13:53,022 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:53,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:53,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:53,027 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:53,028 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-01-09 04:13:53,129 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-01-09 04:13:53,173 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-01-09 04:13:53,173 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:53,173 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:53,176 INFO L256 TraceCheckSpWp]: Trace formula consists of 521 conjuncts, 76 conjuncts are in the unsatisfiable core [2025-01-09 04:13:53,178 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:53,182 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:53,185 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:13:53,188 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:14:01,320 WARN L873 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#r~0#1.offset_BEFORE_CALL_16| Int)) (= (select (select |c_#memory_int#4| |v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_16|) |v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_16|) (select (select |c_#memory_int#6| |v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_16|) |v_ULTIMATE.start_main_~#r~0#1.offset_BEFORE_CALL_16|))) is different from true [2025-01-09 04:14:05,528 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_16| Int) (|v_ULTIMATE.start_main_~#r~0#1.offset_BEFORE_CALL_16| Int)) (= (select (select |c_#memory_int#4| |v_ULTIMATE.start_main_~#A~0#1.base_BEFORE_CALL_16|) |v_ULTIMATE.start_main_~#A~0#1.offset_BEFORE_CALL_16|) (select (select |c_#memory_int#6| |v_ULTIMATE.start_main_~#r~0#1.base_BEFORE_CALL_16|) |v_ULTIMATE.start_main_~#r~0#1.offset_BEFORE_CALL_16|))) (exists ((|v_func_to_recursive_line_30_to_37_0_#in~r.base_BEFORE_CALL_14| Int) (v_func_to_recursive_line_30_to_37_0_~r.offset_BEFORE_CALL_14 Int) (|v_func_to_recursive_line_30_to_37_0_#in~A.base_BEFORE_CALL_11| Int) (|v_func_to_recursive_line_30_to_37_0_#in~A.offset_BEFORE_CALL_3| Int)) (<= (select (select |c_#memory_int#6| |v_func_to_recursive_line_30_to_37_0_#in~r.base_BEFORE_CALL_14|) v_func_to_recursive_line_30_to_37_0_~r.offset_BEFORE_CALL_14) (select (select |c_#memory_int#4| |v_func_to_recursive_line_30_to_37_0_#in~A.base_BEFORE_CALL_11|) |v_func_to_recursive_line_30_to_37_0_#in~A.offset_BEFORE_CALL_3|)))) is different from true [2025-01-09 04:14:05,737 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:14:09,843 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 20 [2025-01-09 04:14:09,853 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:14:09,854 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 34 treesize of output 34 [2025-01-09 04:14:11,024 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 68 treesize of output 37 [2025-01-09 04:14:11,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:14:11,038 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:14:11,039 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 33 treesize of output 21 [2025-01-09 04:14:11,072 INFO L134 CoverageAnalysis]: Checked inductivity of 178 backedges. 53 proven. 16 refuted. 0 times theorem prover too weak. 35 trivial. 74 not checked. [2025-01-09 04:14:11,072 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:14:11,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1773638722] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:14:11,610 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 04:14:11,610 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 18] total 29 [2025-01-09 04:14:11,610 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [367561727] [2025-01-09 04:14:11,610 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 04:14:11,610 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-01-09 04:14:11,610 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:14:11,611 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-01-09 04:14:11,611 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=845, Unknown=3, NotChecked=118, Total=1056 [2025-01-09 04:14:11,611 INFO L87 Difference]: Start difference. First operand 164 states and 194 transitions. Second operand has 29 states, 22 states have (on average 3.0) internal successors, (66), 25 states have internal predecessors, (66), 16 states have call successors, (26), 9 states have call predecessors, (26), 10 states have return successors, (22), 12 states have call predecessors, (22), 14 states have call successors, (22) [2025-01-09 04:14:15,625 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]