./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.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_egcd3-ll.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 31cf2fabf53e081c3004f39943d7e98ce7bd9dc5e02db94d5bcffe73b0927449 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 04:11:31,761 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 04:11:31,793 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:11:31,796 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 04:11:31,796 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 04:11:31,814 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 04:11:31,815 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 04:11:31,815 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 04:11:31,815 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 04:11:31,815 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 04:11:31,815 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 04:11:31,815 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 04:11:31,816 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 04:11:31,816 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 04:11:31,816 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 04:11:31,817 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:11:31,817 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:11:31,818 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:11:31,818 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 04:11:31,818 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 04:11:31,818 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 -> 31cf2fabf53e081c3004f39943d7e98ce7bd9dc5e02db94d5bcffe73b0927449 [2025-01-09 04:11:32,011 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 04:11:32,026 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 04:11:32,028 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 04:11:32,028 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 04:11:32,030 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 04:11:32,032 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c [2025-01-09 04:11:33,277 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/8a37d2bc4/7037c3bf24aa44d8a9b0d982cc968f83/FLAG5a9af0626 [2025-01-09 04:11:33,572 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 04:11:33,574 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c [2025-01-09 04:11:33,581 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/8a37d2bc4/7037c3bf24aa44d8a9b0d982cc968f83/FLAG5a9af0626 [2025-01-09 04:11:33,840 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/8a37d2bc4/7037c3bf24aa44d8a9b0d982cc968f83 [2025-01-09 04:11:33,842 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 04:11:33,843 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 04:11:33,845 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 04:11:33,845 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 04:11:33,847 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 04:11:33,848 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:11:33" (1/1) ... [2025-01-09 04:11:33,848 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5d3f89d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:33, skipping insertion in model container [2025-01-09 04:11:33,848 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:11:33" (1/1) ... [2025-01-09 04:11:33,865 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 04:11:33,959 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_egcd3-ll.c[1052,1065] [2025-01-09 04:11:33,975 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:11:33,984 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 04:11:33,994 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_egcd3-ll.c[1052,1065] [2025-01-09 04:11:34,015 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:11:34,026 INFO L204 MainTranslator]: Completed translation [2025-01-09 04:11:34,028 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34 WrapperNode [2025-01-09 04:11:34,029 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 04:11:34,029 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 04:11:34,030 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 04:11:34,030 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 04:11:34,034 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:11:34" (1/1) ... [2025-01-09 04:11:34,042 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:11:34" (1/1) ... [2025-01-09 04:11:34,056 INFO L138 Inliner]: procedures = 18, calls = 127, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 95 [2025-01-09 04:11:34,056 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 04:11:34,056 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 04:11:34,057 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 04:11:34,057 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 04:11:34,062 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,062 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,064 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,075 INFO L175 MemorySlicer]: Split 77 memory accesses to 13 slices as follows [2, 9, 6, 5, 6, 6, 5, 7, 6, 6, 5, 7, 7]. 12 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The 22 writes are split as follows [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]. [2025-01-09 04:11:34,076 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,076 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,082 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,082 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,083 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,089 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,089 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,092 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 04:11:34,092 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 04:11:34,092 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 04:11:34,092 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 04:11:34,093 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (1/1) ... [2025-01-09 04:11:34,096 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:11:34,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:34,118 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:11:34,121 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:11:34,137 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 04:11:34,137 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-01-09 04:11:34,138 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#9 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#10 [2025-01-09 04:11:34,138 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#11 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#12 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_47_to_56_0 [2025-01-09 04:11:34,139 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_47_to_56_0 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_33_to_70_0 [2025-01-09 04:11:34,139 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_33_to_70_0 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_40_to_59_0 [2025-01-09 04:11:34,139 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_40_to_59_0 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-01-09 04:11:34,139 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#9 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#10 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#11 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#12 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 04:11:34,140 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-01-09 04:11:34,140 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#9 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#10 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#11 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#12 [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 04:11:34,141 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 04:11:34,141 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-01-09 04:11:34,232 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 04:11:34,233 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 04:11:34,424 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2025-01-09 04:11:34,424 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 04:11:34,430 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 04:11:34,430 INFO L312 CfgBuilder]: Removed 3 assume(true) statements. [2025-01-09 04:11:34,431 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:11:34 BoogieIcfgContainer [2025-01-09 04:11:34,431 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 04:11:34,432 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 04:11:34,432 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 04:11:34,435 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 04:11:34,436 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 04:11:33" (1/3) ... [2025-01-09 04:11:34,436 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@48c37f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:11:34, skipping insertion in model container [2025-01-09 04:11:34,436 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:34" (2/3) ... [2025-01-09 04:11:34,436 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@48c37f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:11:34, skipping insertion in model container [2025-01-09 04:11:34,436 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:11:34" (3/3) ... [2025-01-09 04:11:34,437 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_egcd3-ll.c [2025-01-09 04:11:34,447 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 04:11:34,448 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_egcd3-ll.c that has 6 procedures, 53 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-01-09 04:11:34,487 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 04:11:34,494 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;@6c4a3ee2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 04:11:34,495 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 04:11:34,498 INFO L276 IsEmpty]: Start isEmpty. Operand has 53 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 37 states have internal predecessors, (42), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-01-09 04:11:34,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-01-09 04:11:34,502 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:34,503 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:34,504 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:34,507 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:34,508 INFO L85 PathProgramCache]: Analyzing trace with hash -909827079, now seen corresponding path program 1 times [2025-01-09 04:11:34,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:34,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1970622935] [2025-01-09 04:11:34,513 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:34,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:34,589 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-01-09 04:11:34,614 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-01-09 04:11:34,616 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:34,617 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:34,673 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-01-09 04:11:34,673 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:34,673 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1970622935] [2025-01-09 04:11:34,674 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1970622935] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:34,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [756110363] [2025-01-09 04:11:34,674 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:34,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:34,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:34,676 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:11:34,678 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-01-09 04:11:34,781 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-01-09 04:11:34,858 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-01-09 04:11:34,858 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:34,858 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:34,860 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-01-09 04:11:34,862 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:34,870 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-01-09 04:11:34,870 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 04:11:34,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [756110363] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:11:34,870 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:34,870 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-01-09 04:11:34,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1460147198] [2025-01-09 04:11:34,873 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:11:34,878 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-01-09 04:11:34,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:34,889 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-01-09 04:11:34,889 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 04:11:34,890 INFO L87 Difference]: Start difference. First operand has 53 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 37 states have internal predecessors, (42), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-09 04:11:34,902 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:34,903 INFO L93 Difference]: Finished difference Result 103 states and 145 transitions. [2025-01-09 04:11:34,903 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-01-09 04:11:34,904 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2025-01-09 04:11:34,904 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:34,907 INFO L225 Difference]: With dead ends: 103 [2025-01-09 04:11:34,907 INFO L226 Difference]: Without dead ends: 49 [2025-01-09 04:11:34,909 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 04:11:34,911 INFO L435 NwaCegarLoop]: 63 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:34,911 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 04:11:34,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-01-09 04:11:34,931 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2025-01-09 04:11:34,932 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 34 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-01-09 04:11:34,935 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 59 transitions. [2025-01-09 04:11:34,936 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 59 transitions. Word has length 24 [2025-01-09 04:11:34,936 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:34,936 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 59 transitions. [2025-01-09 04:11:34,936 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-09 04:11:34,938 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 59 transitions. [2025-01-09 04:11:34,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-01-09 04:11:34,940 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:34,940 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:34,948 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:11:35,145 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-01-09 04:11:35,146 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:35,147 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:35,147 INFO L85 PathProgramCache]: Analyzing trace with hash 665195867, now seen corresponding path program 1 times [2025-01-09 04:11:35,147 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:35,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [249258460] [2025-01-09 04:11:35,147 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:35,148 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:35,178 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-01-09 04:11:35,216 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-01-09 04:11:35,217 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:35,217 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:35,671 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 04:11:35,672 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:35,672 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [249258460] [2025-01-09 04:11:35,672 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [249258460] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:11:35,672 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:11:35,672 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2025-01-09 04:11:35,673 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539280837] [2025-01-09 04:11:35,673 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:11:35,674 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 04:11:35,674 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:35,674 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 04:11:35,674 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2025-01-09 04:11:35,675 INFO L87 Difference]: Start difference. First operand 49 states and 59 transitions. Second operand has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 04:11:36,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:36,025 INFO L93 Difference]: Finished difference Result 59 states and 69 transitions. [2025-01-09 04:11:36,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-09 04:11:36,025 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 25 [2025-01-09 04:11:36,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:36,030 INFO L225 Difference]: With dead ends: 59 [2025-01-09 04:11:36,030 INFO L226 Difference]: Without dead ends: 51 [2025-01-09 04:11:36,031 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2025-01-09 04:11:36,031 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 39 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 446 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 453 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 446 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:36,031 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 69 Invalid, 453 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 446 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 04:11:36,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2025-01-09 04:11:36,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2025-01-09 04:11:36,040 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 35 states have internal predecessors, (35), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2025-01-09 04:11:36,041 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 61 transitions. [2025-01-09 04:11:36,043 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 61 transitions. Word has length 25 [2025-01-09 04:11:36,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:36,043 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 61 transitions. [2025-01-09 04:11:36,043 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 04:11:36,044 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 61 transitions. [2025-01-09 04:11:36,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-01-09 04:11:36,044 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:36,044 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:36,045 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-09 04:11:36,045 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:36,045 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:36,045 INFO L85 PathProgramCache]: Analyzing trace with hash 977283434, now seen corresponding path program 1 times [2025-01-09 04:11:36,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:36,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [554287690] [2025-01-09 04:11:36,045 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:36,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:36,065 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-09 04:11:36,082 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-09 04:11:36,083 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:36,083 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:36,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1907133151] [2025-01-09 04:11:36,085 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:36,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:36,086 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:36,090 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:11:36,091 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-01-09 04:11:36,170 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-01-09 04:11:36,250 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-01-09 04:11:36,250 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:36,250 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:36,254 INFO L256 TraceCheckSpWp]: Trace formula consists of 528 conjuncts, 194 conjuncts are in the unsatisfiable core [2025-01-09 04:11:36,259 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:36,282 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:36,283 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:36,317 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:36,321 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:36,328 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:36,333 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:36,443 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:36,602 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:11:36,609 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:11:36,768 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2025-01-09 04:11:36,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:11:36,783 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2025-01-09 04:11:36,843 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 04:11:36,844 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 04:11:36,844 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:36,844 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [554287690] [2025-01-09 04:11:36,844 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:36,844 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1907133151] [2025-01-09 04:11:36,844 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1907133151] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:11:36,845 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:11:36,845 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [19] imperfect sequences [] total 19 [2025-01-09 04:11:36,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1060080338] [2025-01-09 04:11:36,845 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:11:36,845 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-01-09 04:11:36,845 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:36,845 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-01-09 04:11:36,845 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=305, Unknown=0, NotChecked=0, Total=342 [2025-01-09 04:11:36,846 INFO L87 Difference]: Start difference. First operand 51 states and 61 transitions. Second operand has 19 states, 14 states have (on average 1.5) internal successors, (21), 14 states have internal predecessors, (21), 6 states have call successors, (6), 5 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 04:11:37,706 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:37,706 INFO L93 Difference]: Finished difference Result 89 states and 106 transitions. [2025-01-09 04:11:37,707 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-01-09 04:11:37,707 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 14 states have (on average 1.5) internal successors, (21), 14 states have internal predecessors, (21), 6 states have call successors, (6), 5 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 29 [2025-01-09 04:11:37,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:37,708 INFO L225 Difference]: With dead ends: 89 [2025-01-09 04:11:37,708 INFO L226 Difference]: Without dead ends: 85 [2025-01-09 04:11:37,709 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=81, Invalid=675, Unknown=0, NotChecked=0, Total=756 [2025-01-09 04:11:37,709 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 38 mSDsluCounter, 368 mSDsCounter, 0 mSdLazyCounter, 567 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 404 SdHoareTripleChecker+Invalid, 588 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 567 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:37,709 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 404 Invalid, 588 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 567 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-01-09 04:11:37,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2025-01-09 04:11:37,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 81. [2025-01-09 04:11:37,719 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 50 states have (on average 1.12) internal successors, (56), 56 states have internal predecessors, (56), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (21), 19 states have call predecessors, (21), 20 states have call successors, (21) [2025-01-09 04:11:37,720 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 98 transitions. [2025-01-09 04:11:37,720 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 98 transitions. Word has length 29 [2025-01-09 04:11:37,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:37,721 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 98 transitions. [2025-01-09 04:11:37,721 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 14 states have (on average 1.5) internal successors, (21), 14 states have internal predecessors, (21), 6 states have call successors, (6), 5 states have call predecessors, (6), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 04:11:37,721 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 98 transitions. [2025-01-09 04:11:37,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-01-09 04:11:37,721 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:37,722 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:37,730 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-01-09 04:11:37,922 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:37,922 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:37,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:37,923 INFO L85 PathProgramCache]: Analyzing trace with hash -227438513, now seen corresponding path program 1 times [2025-01-09 04:11:37,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:37,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1644987664] [2025-01-09 04:11:37,923 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:37,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:37,943 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-01-09 04:11:37,972 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-01-09 04:11:37,973 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:37,973 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:37,977 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1782839720] [2025-01-09 04:11:37,977 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:37,977 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:37,977 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:37,981 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:11:37,984 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-01-09 04:11:38,068 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-01-09 04:11:38,127 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-01-09 04:11:38,127 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:38,127 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:38,131 INFO L256 TraceCheckSpWp]: Trace formula consists of 547 conjuncts, 125 conjuncts are in the unsatisfiable core [2025-01-09 04:11:38,136 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:38,141 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:38,148 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:38,152 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:38,156 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:38,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:11:38,413 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-01-09 04:11:38,455 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:11:38,456 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:38,574 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:38,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1644987664] [2025-01-09 04:11:38,574 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:38,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1782839720] [2025-01-09 04:11:38,575 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1782839720] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:38,575 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:38,575 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2025-01-09 04:11:38,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1882417174] [2025-01-09 04:11:38,575 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:38,575 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-01-09 04:11:38,575 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:38,576 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-01-09 04:11:38,576 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2025-01-09 04:11:38,576 INFO L87 Difference]: Start difference. First operand 81 states and 98 transitions. Second operand has 13 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (7), 6 states have call predecessors, (7), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-09 04:11:38,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:38,930 INFO L93 Difference]: Finished difference Result 116 states and 138 transitions. [2025-01-09 04:11:38,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-01-09 04:11:38,931 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (7), 6 states have call predecessors, (7), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2025-01-09 04:11:38,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:38,932 INFO L225 Difference]: With dead ends: 116 [2025-01-09 04:11:38,932 INFO L226 Difference]: Without dead ends: 114 [2025-01-09 04:11:38,932 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 24 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=71, Invalid=349, Unknown=0, NotChecked=0, Total=420 [2025-01-09 04:11:38,933 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 33 mSDsluCounter, 360 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 403 SdHoareTripleChecker+Invalid, 349 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:38,933 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 403 Invalid, 349 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 328 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 04:11:38,933 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2025-01-09 04:11:38,947 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 111. [2025-01-09 04:11:38,948 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 69 states have (on average 1.1304347826086956) internal successors, (78), 77 states have internal predecessors, (78), 28 states have call successors, (28), 13 states have call predecessors, (28), 13 states have return successors, (28), 26 states have call predecessors, (28), 27 states have call successors, (28) [2025-01-09 04:11:38,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 134 transitions. [2025-01-09 04:11:38,949 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 134 transitions. Word has length 35 [2025-01-09 04:11:38,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:38,949 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 134 transitions. [2025-01-09 04:11:38,949 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (7), 6 states have call predecessors, (7), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-09 04:11:38,949 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 134 transitions. [2025-01-09 04:11:38,950 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-01-09 04:11:38,950 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:38,950 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-01-09 04:11:38,957 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-01-09 04:11:39,154 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:39,154 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:39,155 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:39,155 INFO L85 PathProgramCache]: Analyzing trace with hash 524026268, now seen corresponding path program 1 times [2025-01-09 04:11:39,155 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:39,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [711212060] [2025-01-09 04:11:39,155 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:39,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:39,167 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-09 04:11:39,185 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-09 04:11:39,185 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:39,189 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:39,794 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 04:11:39,794 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:39,794 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [711212060] [2025-01-09 04:11:39,794 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [711212060] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:39,794 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [525192621] [2025-01-09 04:11:39,795 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:39,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:39,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:39,801 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:11:39,802 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-01-09 04:11:39,881 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-09 04:11:39,926 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-09 04:11:39,926 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:39,926 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:39,928 INFO L256 TraceCheckSpWp]: Trace formula consists of 533 conjuncts, 37 conjuncts are in the unsatisfiable core [2025-01-09 04:11:39,933 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:40,034 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 23 treesize of output 15 [2025-01-09 04:11:40,038 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:40,065 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:40,097 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 23 treesize of output 15 [2025-01-09 04:11:40,101 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:40,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:11:40,199 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:11:40,199 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:40,761 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 04:11:40,762 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [525192621] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 04:11:40,762 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 04:11:40,762 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 18, 17] total 38 [2025-01-09 04:11:40,762 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1474090626] [2025-01-09 04:11:40,762 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:40,762 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2025-01-09 04:11:40,762 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:40,764 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2025-01-09 04:11:40,765 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1279, Unknown=0, NotChecked=0, Total=1406 [2025-01-09 04:11:40,765 INFO L87 Difference]: Start difference. First operand 111 states and 134 transitions. Second operand has 38 states, 30 states have (on average 1.8333333333333333) internal successors, (55), 34 states have internal predecessors, (55), 14 states have call successors, (16), 9 states have call predecessors, (16), 11 states have return successors, (14), 8 states have call predecessors, (14), 13 states have call successors, (14) [2025-01-09 04:11:44,772 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 04:11:45,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:45,671 INFO L93 Difference]: Finished difference Result 133 states and 160 transitions. [2025-01-09 04:11:45,671 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-01-09 04:11:45,671 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 30 states have (on average 1.8333333333333333) internal successors, (55), 34 states have internal predecessors, (55), 14 states have call successors, (16), 9 states have call predecessors, (16), 11 states have return successors, (14), 8 states have call predecessors, (14), 13 states have call successors, (14) Word has length 38 [2025-01-09 04:11:45,672 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:45,673 INFO L225 Difference]: With dead ends: 133 [2025-01-09 04:11:45,673 INFO L226 Difference]: Without dead ends: 125 [2025-01-09 04:11:45,673 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 53 SyntacticMatches, 4 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 487 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=335, Invalid=2635, Unknown=0, NotChecked=0, Total=2970 [2025-01-09 04:11:45,674 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 148 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 957 mSolverCounterSat, 120 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 150 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 1078 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 120 IncrementalHoareTripleChecker+Valid, 957 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:45,674 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [150 Valid, 108 Invalid, 1078 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [120 Valid, 957 Invalid, 1 Unknown, 0 Unchecked, 4.5s Time] [2025-01-09 04:11:45,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2025-01-09 04:11:45,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 123. [2025-01-09 04:11:45,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 76 states have (on average 1.118421052631579) internal successors, (85), 84 states have internal predecessors, (85), 29 states have call successors, (29), 14 states have call predecessors, (29), 17 states have return successors, (35), 28 states have call predecessors, (35), 28 states have call successors, (35) [2025-01-09 04:11:45,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 149 transitions. [2025-01-09 04:11:45,692 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 149 transitions. Word has length 38 [2025-01-09 04:11:45,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:45,692 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 149 transitions. [2025-01-09 04:11:45,692 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 30 states have (on average 1.8333333333333333) internal successors, (55), 34 states have internal predecessors, (55), 14 states have call successors, (16), 9 states have call predecessors, (16), 11 states have return successors, (14), 8 states have call predecessors, (14), 13 states have call successors, (14) [2025-01-09 04:11:45,695 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 149 transitions. [2025-01-09 04:11:45,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2025-01-09 04:11:45,696 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:45,696 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-01-09 04:11:45,705 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-01-09 04:11:45,896 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:45,897 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:45,897 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:45,898 INFO L85 PathProgramCache]: Analyzing trace with hash -349777783, now seen corresponding path program 1 times [2025-01-09 04:11:45,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:45,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556576665] [2025-01-09 04:11:45,898 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:45,898 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:45,926 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-01-09 04:11:45,963 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-01-09 04:11:45,963 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:45,963 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:45,965 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1831306181] [2025-01-09 04:11:45,965 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:45,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:45,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:45,967 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:11:45,969 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-01-09 04:11:46,093 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-01-09 04:11:46,286 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-01-09 04:11:46,286 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:46,286 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:46,298 INFO L256 TraceCheckSpWp]: Trace formula consists of 777 conjuncts, 258 conjuncts are in the unsatisfiable core [2025-01-09 04:11:46,303 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:46,312 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:46,333 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:46,436 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:46,442 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:46,446 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:46,455 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:46,619 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:11:46,691 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:11:46,866 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:46,875 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 42 treesize of output 30 [2025-01-09 04:11:46,879 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 38 treesize of output 26 [2025-01-09 04:11:46,883 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 23 treesize of output 15 [2025-01-09 04:11:46,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:46,991 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:11:47,266 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:47,267 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 22 treesize of output 22 [2025-01-09 04:11:47,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:11:47,278 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2025-01-09 04:11:47,334 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 04:11:47,334 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:19,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:19,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1556576665] [2025-01-09 04:12:19,665 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:19,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1831306181] [2025-01-09 04:12:19,665 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1831306181] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:19,665 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:19,665 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2025-01-09 04:12:19,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1201912259] [2025-01-09 04:12:19,666 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:19,666 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-01-09 04:12:19,666 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:19,666 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-01-09 04:12:19,667 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=1015, Unknown=7, NotChecked=0, Total=1122 [2025-01-09 04:12:19,667 INFO L87 Difference]: Start difference. First operand 123 states and 149 transitions. Second operand has 26 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 18 states have internal predecessors, (29), 8 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 04:12:23,676 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 04:12:25,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:25,619 INFO L93 Difference]: Finished difference Result 177 states and 214 transitions. [2025-01-09 04:12:25,620 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-01-09 04:12:25,620 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 18 states have internal predecessors, (29), 8 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 40 [2025-01-09 04:12:25,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:25,621 INFO L225 Difference]: With dead ends: 177 [2025-01-09 04:12:25,621 INFO L226 Difference]: Without dead ends: 171 [2025-01-09 04:12:25,622 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 21 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 488 ImplicationChecksByTransitivity, 33.2s TimeCoverageRelationStatistics Valid=181, Invalid=1882, Unknown=7, NotChecked=0, Total=2070 [2025-01-09 04:12:25,622 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 144 mSDsluCounter, 372 mSDsCounter, 0 mSdLazyCounter, 1328 mSolverCounterSat, 48 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 412 SdHoareTripleChecker+Invalid, 1377 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 1328 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.3s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:25,622 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 412 Invalid, 1377 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 1328 Invalid, 1 Unknown, 0 Unchecked, 5.3s Time] [2025-01-09 04:12:25,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2025-01-09 04:12:25,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 165. [2025-01-09 04:12:25,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 103 states have (on average 1.116504854368932) internal successors, (115), 113 states have internal predecessors, (115), 38 states have call successors, (38), 20 states have call predecessors, (38), 23 states have return successors, (47), 36 states have call predecessors, (47), 37 states have call successors, (47) [2025-01-09 04:12:25,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 200 transitions. [2025-01-09 04:12:25,641 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 200 transitions. Word has length 40 [2025-01-09 04:12:25,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:25,642 INFO L471 AbstractCegarLoop]: Abstraction has 165 states and 200 transitions. [2025-01-09 04:12:25,642 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 18 states have internal predecessors, (29), 8 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 04:12:25,642 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 200 transitions. [2025-01-09 04:12:25,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-01-09 04:12:25,643 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:25,643 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:25,653 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-01-09 04:12:25,843 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:25,843 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:25,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:25,844 INFO L85 PathProgramCache]: Analyzing trace with hash 318259314, now seen corresponding path program 1 times [2025-01-09 04:12:25,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:25,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1627359022] [2025-01-09 04:12:25,844 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:25,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:25,855 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-01-09 04:12:25,870 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-01-09 04:12:25,870 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:25,870 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:25,873 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [997748600] [2025-01-09 04:12:25,873 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:25,873 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:25,873 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:25,875 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:25,879 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:25,966 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-01-09 04:12:26,025 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-01-09 04:12:26,026 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:26,026 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:26,028 INFO L256 TraceCheckSpWp]: Trace formula consists of 564 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-01-09 04:12:26,030 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:26,033 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:26,035 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:26,042 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:26,048 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:26,196 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-01-09 04:12:26,198 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:26,229 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-01-09 04:12:26,229 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:26,319 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-01-09 04:12:26,319 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:26,319 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1627359022] [2025-01-09 04:12:26,319 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:26,319 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [997748600] [2025-01-09 04:12:26,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [997748600] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:26,319 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:26,320 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [11] total 11 [2025-01-09 04:12:26,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [589200524] [2025-01-09 04:12:26,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:26,320 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 04:12:26,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:26,320 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 04:12:26,320 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2025-01-09 04:12:26,320 INFO L87 Difference]: Start difference. First operand 165 states and 200 transitions. Second operand has 10 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:12:26,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:26,589 INFO L93 Difference]: Finished difference Result 217 states and 263 transitions. [2025-01-09 04:12:26,590 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 04:12:26,590 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 41 [2025-01-09 04:12:26,590 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:26,592 INFO L225 Difference]: With dead ends: 217 [2025-01-09 04:12:26,592 INFO L226 Difference]: Without dead ends: 215 [2025-01-09 04:12:26,592 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 65 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2025-01-09 04:12:26,593 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 25 mSDsluCounter, 316 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:26,593 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 364 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 04:12:26,596 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-01-09 04:12:26,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 213. [2025-01-09 04:12:26,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 133 states have (on average 1.1203007518796992) internal successors, (149), 147 states have internal predecessors, (149), 50 states have call successors, (50), 26 states have call predecessors, (50), 29 states have return successors, (59), 46 states have call predecessors, (59), 49 states have call successors, (59) [2025-01-09 04:12:26,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 258 transitions. [2025-01-09 04:12:26,633 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 258 transitions. Word has length 41 [2025-01-09 04:12:26,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:26,634 INFO L471 AbstractCegarLoop]: Abstraction has 213 states and 258 transitions. [2025-01-09 04:12:26,634 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:12:26,634 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 258 transitions. [2025-01-09 04:12:26,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2025-01-09 04:12:26,637 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:26,637 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-01-09 04:12:26,644 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-01-09 04:12:26,838 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,SelfDestructingSolverStorable6 [2025-01-09 04:12:26,838 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:26,838 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:26,838 INFO L85 PathProgramCache]: Analyzing trace with hash 2002789422, now seen corresponding path program 1 times [2025-01-09 04:12:26,839 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:26,839 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1726742202] [2025-01-09 04:12:26,839 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:26,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:26,853 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-01-09 04:12:26,877 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-01-09 04:12:26,877 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:26,878 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:26,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1822989972] [2025-01-09 04:12:26,881 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:26,881 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:26,881 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:26,882 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:26,886 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:26,981 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-01-09 04:12:27,059 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-01-09 04:12:27,060 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:27,060 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:27,064 INFO L256 TraceCheckSpWp]: Trace formula consists of 796 conjuncts, 189 conjuncts are in the unsatisfiable core [2025-01-09 04:12:27,068 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:27,073 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:12:27,076 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:27,080 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:27,084 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:27,127 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:27,131 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 27 treesize of output 19 [2025-01-09 04:12:27,134 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:27,156 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:27,218 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:27,222 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 27 treesize of output 19 [2025-01-09 04:12:27,224 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:27,227 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:27,459 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:27,460 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:27,473 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:12:27,519 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:12:27,519 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:27,612 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 25 [2025-01-09 04:12:27,924 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 54 treesize of output 50 [2025-01-09 04:12:27,927 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 46 [2025-01-09 04:12:28,002 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:28,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1726742202] [2025-01-09 04:12:28,003 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:28,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1822989972] [2025-01-09 04:12:28,003 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1822989972] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:28,003 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:28,003 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2025-01-09 04:12:28,003 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [181738551] [2025-01-09 04:12:28,003 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:28,003 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-01-09 04:12:28,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:28,003 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-01-09 04:12:28,003 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=585, Unknown=0, NotChecked=0, Total=650 [2025-01-09 04:12:28,004 INFO L87 Difference]: Start difference. First operand 213 states and 258 transitions. Second operand has 17 states, 15 states have (on average 2.0) internal successors, (30), 12 states have internal predecessors, (30), 7 states have call successors, (9), 8 states have call predecessors, (9), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-01-09 04:12:29,052 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:29,053 INFO L93 Difference]: Finished difference Result 333 states and 408 transitions. [2025-01-09 04:12:29,053 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-01-09 04:12:29,053 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.0) internal successors, (30), 12 states have internal predecessors, (30), 7 states have call successors, (9), 8 states have call predecessors, (9), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 46 [2025-01-09 04:12:29,053 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:29,055 INFO L225 Difference]: With dead ends: 333 [2025-01-09 04:12:29,055 INFO L226 Difference]: Without dead ends: 331 [2025-01-09 04:12:29,056 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 40 SyntacticMatches, 4 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=130, Invalid=1130, Unknown=0, NotChecked=0, Total=1260 [2025-01-09 04:12:29,056 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 77 mSDsluCounter, 467 mSDsCounter, 0 mSdLazyCounter, 1029 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 520 SdHoareTripleChecker+Invalid, 1062 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 1029 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:29,056 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 520 Invalid, 1062 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 1029 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-01-09 04:12:29,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 331 states. [2025-01-09 04:12:29,111 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 331 to 321. [2025-01-09 04:12:29,112 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 321 states, 200 states have (on average 1.13) internal successors, (226), 222 states have internal predecessors, (226), 74 states have call successors, (74), 39 states have call predecessors, (74), 46 states have return successors, (93), 69 states have call predecessors, (93), 72 states have call successors, (93) [2025-01-09 04:12:29,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 321 states to 321 states and 393 transitions. [2025-01-09 04:12:29,118 INFO L78 Accepts]: Start accepts. Automaton has 321 states and 393 transitions. Word has length 46 [2025-01-09 04:12:29,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:29,119 INFO L471 AbstractCegarLoop]: Abstraction has 321 states and 393 transitions. [2025-01-09 04:12:29,119 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.0) internal successors, (30), 12 states have internal predecessors, (30), 7 states have call successors, (9), 8 states have call predecessors, (9), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-01-09 04:12:29,119 INFO L276 IsEmpty]: Start isEmpty. Operand 321 states and 393 transitions. [2025-01-09 04:12:29,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-01-09 04:12:29,119 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:29,119 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:29,127 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:12:29,320 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:29,320 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:29,320 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:29,320 INFO L85 PathProgramCache]: Analyzing trace with hash -1094986925, now seen corresponding path program 1 times [2025-01-09 04:12:29,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:29,321 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1062162379] [2025-01-09 04:12:29,321 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:29,321 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:29,333 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-01-09 04:12:29,367 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-01-09 04:12:29,367 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:29,367 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:29,373 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1200246161] [2025-01-09 04:12:29,373 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:29,373 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:29,373 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:29,375 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:12:29,376 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:12:29,462 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-01-09 04:12:29,517 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-01-09 04:12:29,517 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:29,517 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:29,519 INFO L256 TraceCheckSpWp]: Trace formula consists of 579 conjuncts, 67 conjuncts are in the unsatisfiable core [2025-01-09 04:12:29,522 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:29,523 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:29,525 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:29,526 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:29,529 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:29,532 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:29,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 19 treesize of output 11 [2025-01-09 04:12:29,657 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:29,680 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-01-09 04:12:29,680 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:29,767 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-01-09 04:12:29,767 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:29,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1062162379] [2025-01-09 04:12:29,767 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:29,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1200246161] [2025-01-09 04:12:29,767 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1200246161] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:29,767 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:29,767 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2025-01-09 04:12:29,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1815111123] [2025-01-09 04:12:29,768 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:29,768 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:12:29,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:29,768 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:12:29,768 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2025-01-09 04:12:29,768 INFO L87 Difference]: Start difference. First operand 321 states and 393 transitions. Second operand has 8 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-01-09 04:12:29,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:29,971 INFO L93 Difference]: Finished difference Result 380 states and 469 transitions. [2025-01-09 04:12:29,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-01-09 04:12:29,972 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 47 [2025-01-09 04:12:29,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:29,974 INFO L225 Difference]: With dead ends: 380 [2025-01-09 04:12:29,974 INFO L226 Difference]: Without dead ends: 378 [2025-01-09 04:12:29,974 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 74 SyntacticMatches, 7 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2025-01-09 04:12:29,975 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 16 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 118 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:29,975 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 293 Invalid, 118 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:12:29,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 378 states. [2025-01-09 04:12:30,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 378 to 337. [2025-01-09 04:12:30,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 337 states, 212 states have (on average 1.1179245283018868) internal successors, (237), 234 states have internal predecessors, (237), 74 states have call successors, (74), 43 states have call predecessors, (74), 50 states have return successors, (93), 69 states have call predecessors, (93), 72 states have call successors, (93) [2025-01-09 04:12:30,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 337 states to 337 states and 404 transitions. [2025-01-09 04:12:30,012 INFO L78 Accepts]: Start accepts. Automaton has 337 states and 404 transitions. Word has length 47 [2025-01-09 04:12:30,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:30,013 INFO L471 AbstractCegarLoop]: Abstraction has 337 states and 404 transitions. [2025-01-09 04:12:30,013 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-01-09 04:12:30,013 INFO L276 IsEmpty]: Start isEmpty. Operand 337 states and 404 transitions. [2025-01-09 04:12:30,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2025-01-09 04:12:30,013 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:30,013 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 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:30,022 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:12:30,218 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:30,218 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:30,218 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:30,218 INFO L85 PathProgramCache]: Analyzing trace with hash -1612394486, now seen corresponding path program 2 times [2025-01-09 04:12:30,218 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:30,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [48920880] [2025-01-09 04:12:30,219 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:12:30,219 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:30,244 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 51 statements into 2 equivalence classes. [2025-01-09 04:12:30,255 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 51 of 51 statements. [2025-01-09 04:12:30,256 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:12:30,256 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:31,619 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 8 proven. 16 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-01-09 04:12:31,619 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:31,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [48920880] [2025-01-09 04:12:31,620 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [48920880] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:31,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [26628708] [2025-01-09 04:12:31,620 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 04:12:31,620 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:31,620 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:31,622 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:12:31,626 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:12:31,734 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 51 statements into 2 equivalence classes. [2025-01-09 04:12:31,844 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 51 of 51 statements. [2025-01-09 04:12:31,844 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 04:12:31,844 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:31,852 INFO L256 TraceCheckSpWp]: Trace formula consists of 1026 conjuncts, 116 conjuncts are in the unsatisfiable core [2025-01-09 04:12:31,855 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:31,877 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:31,879 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:31,909 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:31,929 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:32,007 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 27 treesize of output 19 [2025-01-09 04:12:32,010 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 40 treesize of output 17 [2025-01-09 04:12:32,012 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:12:32,064 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:32,093 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:32,175 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 40 treesize of output 28 [2025-01-09 04:12:32,179 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 40 treesize of output 17 [2025-01-09 04:12:32,181 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:12:32,235 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 21 [2025-01-09 04:12:32,239 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:32,321 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:12:32,322 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:12:32,324 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:12:32,324 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:32,704 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:12:32,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [26628708] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 04:12:32,705 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 04:12:32,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 21, 14] total 33 [2025-01-09 04:12:32,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [580309585] [2025-01-09 04:12:32,705 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:32,705 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-01-09 04:12:32,705 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:32,706 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-01-09 04:12:32,706 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2025-01-09 04:12:32,706 INFO L87 Difference]: Start difference. First operand 337 states and 404 transitions. Second operand has 33 states, 31 states have (on average 2.064516129032258) internal successors, (64), 26 states have internal predecessors, (64), 12 states have call successors, (20), 12 states have call predecessors, (20), 6 states have return successors, (10), 6 states have call predecessors, (10), 5 states have call successors, (10) [2025-01-09 04:12:36,941 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 04:12:38,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:38,301 INFO L93 Difference]: Finished difference Result 656 states and 812 transitions. [2025-01-09 04:12:38,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-01-09 04:12:38,301 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 31 states have (on average 2.064516129032258) internal successors, (64), 26 states have internal predecessors, (64), 12 states have call successors, (20), 12 states have call predecessors, (20), 6 states have return successors, (10), 6 states have call predecessors, (10), 5 states have call successors, (10) Word has length 51 [2025-01-09 04:12:38,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:38,305 INFO L225 Difference]: With dead ends: 656 [2025-01-09 04:12:38,305 INFO L226 Difference]: Without dead ends: 458 [2025-01-09 04:12:38,308 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 82 SyntacticMatches, 15 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 744 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=279, Invalid=2271, Unknown=0, NotChecked=0, Total=2550 [2025-01-09 04:12:38,308 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 88 mSDsluCounter, 283 mSDsCounter, 0 mSdLazyCounter, 1741 mSolverCounterSat, 48 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 1790 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 1741 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:38,308 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 305 Invalid, 1790 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 1741 Invalid, 1 Unknown, 0 Unchecked, 5.2s Time] [2025-01-09 04:12:38,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 458 states. [2025-01-09 04:12:38,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 458 to 377. [2025-01-09 04:12:38,360 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 377 states, 240 states have (on average 1.1083333333333334) internal successors, (266), 260 states have internal predecessors, (266), 77 states have call successors, (77), 50 states have call predecessors, (77), 59 states have return successors, (111), 76 states have call predecessors, (111), 75 states have call successors, (111) [2025-01-09 04:12:38,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 377 states to 377 states and 454 transitions. [2025-01-09 04:12:38,363 INFO L78 Accepts]: Start accepts. Automaton has 377 states and 454 transitions. Word has length 51 [2025-01-09 04:12:38,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:38,363 INFO L471 AbstractCegarLoop]: Abstraction has 377 states and 454 transitions. [2025-01-09 04:12:38,363 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 31 states have (on average 2.064516129032258) internal successors, (64), 26 states have internal predecessors, (64), 12 states have call successors, (20), 12 states have call predecessors, (20), 6 states have return successors, (10), 6 states have call predecessors, (10), 5 states have call successors, (10) [2025-01-09 04:12:38,363 INFO L276 IsEmpty]: Start isEmpty. Operand 377 states and 454 transitions. [2025-01-09 04:12:38,364 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-01-09 04:12:38,364 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:38,364 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 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, 1, 1, 1, 1] [2025-01-09 04:12:38,375 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:12:38,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:38,565 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:38,566 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:38,566 INFO L85 PathProgramCache]: Analyzing trace with hash 348179029, now seen corresponding path program 1 times [2025-01-09 04:12:38,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:38,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [533748564] [2025-01-09 04:12:38,566 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:38,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:38,582 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-01-09 04:12:38,595 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-01-09 04:12:38,595 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:38,595 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:39,522 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 14 proven. 1 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 04:12:39,522 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:39,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [533748564] [2025-01-09 04:12:39,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [533748564] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:39,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1603835313] [2025-01-09 04:12:39,522 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:39,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:39,522 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:39,527 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:12:39,530 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:12:39,649 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-01-09 04:12:39,725 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-01-09 04:12:39,726 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:39,726 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:39,729 INFO L256 TraceCheckSpWp]: Trace formula consists of 845 conjuncts, 79 conjuncts are in the unsatisfiable core [2025-01-09 04:12:39,732 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:39,735 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:39,737 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:39,739 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:39,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 15 treesize of output 1 [2025-01-09 04:12:39,745 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:39,751 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:39,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 38 [2025-01-09 04:12:39,894 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 48 treesize of output 25 [2025-01-09 04:12:39,905 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:12:39,907 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:12:39,909 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 04:12:39,909 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 04:12:39,909 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1603835313] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:12:39,909 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:39,909 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [12] total 14 [2025-01-09 04:12:39,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1134179500] [2025-01-09 04:12:39,910 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:39,910 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 04:12:39,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:39,910 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 04:12:39,910 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=150, Unknown=0, NotChecked=0, Total=182 [2025-01-09 04:12:39,910 INFO L87 Difference]: Start difference. First operand 377 states and 454 transitions. Second operand has 11 states, 10 states have (on average 3.3) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (12), 4 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:40,282 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:40,283 INFO L93 Difference]: Finished difference Result 725 states and 913 transitions. [2025-01-09 04:12:40,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-09 04:12:40,283 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 3.3) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (12), 4 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 64 [2025-01-09 04:12:40,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:40,286 INFO L225 Difference]: With dead ends: 725 [2025-01-09 04:12:40,286 INFO L226 Difference]: Without dead ends: 435 [2025-01-09 04:12:40,287 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 72 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2025-01-09 04:12:40,287 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 29 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 314 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:40,288 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 197 Invalid, 314 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 297 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 04:12:40,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 435 states. [2025-01-09 04:12:40,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 435 to 425. [2025-01-09 04:12:40,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 425 states, 270 states have (on average 1.0962962962962963) internal successors, (296), 290 states have internal predecessors, (296), 82 states have call successors, (82), 54 states have call predecessors, (82), 72 states have return successors, (134), 81 states have call predecessors, (134), 80 states have call successors, (134) [2025-01-09 04:12:40,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 425 states to 425 states and 512 transitions. [2025-01-09 04:12:40,355 INFO L78 Accepts]: Start accepts. Automaton has 425 states and 512 transitions. Word has length 64 [2025-01-09 04:12:40,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:40,356 INFO L471 AbstractCegarLoop]: Abstraction has 425 states and 512 transitions. [2025-01-09 04:12:40,356 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 3.3) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (12), 4 states have call predecessors, (12), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-01-09 04:12:40,357 INFO L276 IsEmpty]: Start isEmpty. Operand 425 states and 512 transitions. [2025-01-09 04:12:40,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2025-01-09 04:12:40,357 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:40,357 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:40,364 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-01-09 04:12:40,557 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:40,558 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:40,558 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:40,558 INFO L85 PathProgramCache]: Analyzing trace with hash 457812220, now seen corresponding path program 1 times [2025-01-09 04:12:40,558 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:40,558 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [265682805] [2025-01-09 04:12:40,558 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:40,558 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:40,576 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 75 statements into 1 equivalence classes. [2025-01-09 04:12:40,614 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 75 of 75 statements. [2025-01-09 04:12:40,614 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:40,614 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:40,616 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [431592315] [2025-01-09 04:12:40,616 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:40,617 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:40,617 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:40,620 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:12:40,623 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-01-09 04:12:40,743 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 75 statements into 1 equivalence classes. [2025-01-09 04:12:40,919 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 75 of 75 statements. [2025-01-09 04:12:40,920 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:40,920 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:40,926 INFO L256 TraceCheckSpWp]: Trace formula consists of 852 conjuncts, 238 conjuncts are in the unsatisfiable core [2025-01-09 04:12:40,936 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:40,940 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:41,026 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:41,031 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:41,037 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:41,045 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:41,054 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:41,060 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:41,109 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:41,117 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:41,508 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:41,519 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:41,628 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:41,781 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:41,790 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:41,881 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:42,225 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 27 [2025-01-09 04:12:42,430 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 35 treesize of output 21 [2025-01-09 04:12:42,448 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:42,695 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 33 treesize of output 25 [2025-01-09 04:12:51,542 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:51,553 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:51,562 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:51,573 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 13 [2025-01-09 04:12:51,590 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:51,591 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 54 treesize of output 46 [2025-01-09 04:12:51,622 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 62 treesize of output 38 [2025-01-09 04:12:51,769 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:51,770 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 47 treesize of output 59 [2025-01-09 04:12:51,781 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 72 treesize of output 44 [2025-01-09 04:12:51,797 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:51,797 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 82 treesize of output 58 [2025-01-09 04:12:51,956 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 4 proven. 16 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2025-01-09 04:12:51,956 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:56,045 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:56,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [265682805] [2025-01-09 04:12:56,045 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:56,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [431592315] [2025-01-09 04:12:56,045 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [431592315] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:56,045 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:56,045 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [34] total 34 [2025-01-09 04:12:56,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [484576378] [2025-01-09 04:12:56,045 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:56,046 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2025-01-09 04:12:56,046 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:56,046 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2025-01-09 04:12:56,046 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=1193, Unknown=2, NotChecked=0, Total=1332 [2025-01-09 04:12:56,047 INFO L87 Difference]: Start difference. First operand 425 states and 512 transitions. Second operand has 34 states, 26 states have (on average 1.6538461538461537) internal successors, (43), 26 states have internal predecessors, (43), 9 states have call successors, (12), 7 states have call predecessors, (12), 8 states have return successors, (11), 8 states have call predecessors, (11), 8 states have call successors, (11) [2025-01-09 04:13:00,050 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 04:13:04,086 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-09 04:13:09,106 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-01-09 04:13:13,182 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0]