./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-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_egcd2-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 020f2d3a270ed8dfae4a7c8fa8db16a8ad645d088f685c7c500cf3124112cf45 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 04:11:29,617 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 04:11:29,673 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:29,679 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 04:11:29,680 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 04:11:29,703 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 04:11:29,704 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 04:11:29,704 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 04:11:29,704 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 04:11:29,705 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 04:11:29,705 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 04:11:29,706 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 04:11:29,706 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 04:11:29,706 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 04:11:29,706 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 04:11:29,706 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 04:11:29,706 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 04:11:29,706 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 04:11:29,707 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 04:11:29,708 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 04:11:29,708 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:11:29,708 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:11:29,708 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:11:29,708 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:11:29,708 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 04:11:29,708 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:11:29,709 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 04:11:29,709 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 04:11:29,709 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 -> 020f2d3a270ed8dfae4a7c8fa8db16a8ad645d088f685c7c500cf3124112cf45 [2025-01-09 04:11:29,921 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 04:11:29,929 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 04:11:29,930 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 04:11:29,932 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 04:11:29,932 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 04:11:29,933 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c [2025-01-09 04:11:31,178 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/6560cb3c6/a36963ee4bad4bd4b499d4491995f4bd/FLAGa847ef358 [2025-01-09 04:11:31,474 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 04:11:31,474 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c [2025-01-09 04:11:31,489 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/6560cb3c6/a36963ee4bad4bd4b499d4491995f4bd/FLAGa847ef358 [2025-01-09 04:11:31,761 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/6560cb3c6/a36963ee4bad4bd4b499d4491995f4bd [2025-01-09 04:11:31,763 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 04:11:31,764 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 04:11:31,768 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 04:11:31,768 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 04:11:31,771 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 04:11:31,772 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:11:31" (1/1) ... [2025-01-09 04:11:31,772 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1324015d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:31, skipping insertion in model container [2025-01-09 04:11:31,773 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 04:11:31" (1/1) ... [2025-01-09 04:11:31,782 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 04:11:31,904 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_egcd2-ll.c[1037,1050] [2025-01-09 04:11:31,928 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:11:31,938 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 04:11:31,947 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c[1037,1050] [2025-01-09 04:11:31,967 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 04:11:31,982 INFO L204 MainTranslator]: Completed translation [2025-01-09 04:11:31,984 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:31 WrapperNode [2025-01-09 04:11:31,986 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 04:11:31,987 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 04:11:31,987 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 04:11:31,987 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 04:11:31,992 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:31" (1/1) ... [2025-01-09 04:11:32,003 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:31" (1/1) ... [2025-01-09 04:11:32,019 INFO L138 Inliner]: procedures = 17, calls = 141, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 137 [2025-01-09 04:11:32,021 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 04:11:32,022 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 04:11:32,023 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 04:11:32,023 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 04:11:32,029 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:31" (1/1) ... [2025-01-09 04:11:32,029 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:31" (1/1) ... [2025-01-09 04:11:32,033 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:31" (1/1) ... [2025-01-09 04:11:32,053 INFO L175 MemorySlicer]: Split 86 memory accesses to 13 slices as follows [3, 2, 9, 5, 8, 8, 3, 5, 7, 10, 7, 7, 12]. 14 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The 22 writes are split as follows [1, 0, 1, 2, 2, 2, 1, 2, 3, 2, 2, 3, 1]. [2025-01-09 04:11:32,057 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:31" (1/1) ... [2025-01-09 04:11:32,058 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:31" (1/1) ... [2025-01-09 04:11:32,067 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:31" (1/1) ... [2025-01-09 04:11:32,068 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:31" (1/1) ... [2025-01-09 04:11:32,072 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:31" (1/1) ... [2025-01-09 04:11:32,073 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:31" (1/1) ... [2025-01-09 04:11:32,074 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:31" (1/1) ... [2025-01-09 04:11:32,081 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 04:11:32,081 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 04:11:32,081 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 04:11:32,081 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 04:11:32,082 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:31" (1/1) ... [2025-01-09 04:11:32,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 04:11:32,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:32,121 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:32,123 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:32,141 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 04:11:32,141 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-01-09 04:11:32,141 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-01-09 04:11:32,141 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#9 [2025-01-09 04:11:32,142 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#10 [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#11 [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#12 [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-01-09 04:11:32,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-01-09 04:11:32,144 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-01-09 04:11:32,144 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-01-09 04:11:32,144 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2025-01-09 04:11:32,144 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2025-01-09 04:11:32,144 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#9 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#10 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#11 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#12 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_45_to_53_0 [2025-01-09 04:11:32,145 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_45_to_53_0 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_39_to_65_0 [2025-01-09 04:11:32,145 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_39_to_65_0 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 04:11:32,145 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-01-09 04:11:32,145 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#9 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#10 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#11 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#12 [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 04:11:32,146 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 04:11:32,146 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-01-09 04:11:32,282 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 04:11:32,283 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 04:11:32,537 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-01-09 04:11:32,537 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 04:11:32,545 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 04:11:32,546 INFO L312 CfgBuilder]: Removed 2 assume(true) statements. [2025-01-09 04:11:32,547 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:11:32 BoogieIcfgContainer [2025-01-09 04:11:32,547 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 04:11:32,549 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 04:11:32,552 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 04:11:32,555 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 04:11:32,559 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 04:11:31" (1/3) ... [2025-01-09 04:11:32,560 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@52a50f28 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:11:32, skipping insertion in model container [2025-01-09 04:11:32,560 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 04:11:31" (2/3) ... [2025-01-09 04:11:32,560 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@52a50f28 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 04:11:32, skipping insertion in model container [2025-01-09 04:11:32,560 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 04:11:32" (3/3) ... [2025-01-09 04:11:32,561 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_egcd2-ll.c [2025-01-09 04:11:32,572 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 04:11:32,573 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_egcd2-ll.c that has 5 procedures, 51 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-01-09 04:11:32,610 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 04:11:32,617 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;@7e0664f8, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 04:11:32,617 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 04:11:32,619 INFO L276 IsEmpty]: Start isEmpty. Operand has 51 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 34 states have internal predecessors, (38), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2025-01-09 04:11:32,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-01-09 04:11:32,623 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:32,623 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:32,623 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:32,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:32,626 INFO L85 PathProgramCache]: Analyzing trace with hash 1681658183, now seen corresponding path program 1 times [2025-01-09 04:11:32,631 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:32,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1417567240] [2025-01-09 04:11:32,631 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:32,631 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:32,706 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-09 04:11:32,750 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-09 04:11:32,750 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:32,752 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:32,871 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-09 04:11:32,871 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:32,872 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1417567240] [2025-01-09 04:11:32,872 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1417567240] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:32,872 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1091648253] [2025-01-09 04:11:32,872 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:32,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:32,873 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:32,880 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:32,882 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:32,977 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-09 04:11:33,064 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-09 04:11:33,065 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:33,065 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:33,067 INFO L256 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-01-09 04:11:33,071 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:33,078 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-09 04:11:33,078 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 04:11:33,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1091648253] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:11:33,078 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:33,079 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-01-09 04:11:33,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1419086829] [2025-01-09 04:11:33,080 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:11:33,082 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-01-09 04:11:33,083 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:33,093 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-01-09 04:11:33,094 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 04:11:33,095 INFO L87 Difference]: Start difference. First operand has 51 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 34 states have internal predecessors, (38), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:11:33,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:33,108 INFO L93 Difference]: Finished difference Result 99 states and 142 transitions. [2025-01-09 04:11:33,109 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-01-09 04:11:33,110 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 37 [2025-01-09 04:11:33,110 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:33,116 INFO L225 Difference]: With dead ends: 99 [2025-01-09 04:11:33,116 INFO L226 Difference]: Without dead ends: 47 [2025-01-09 04:11:33,119 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 38 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:33,122 INFO L435 NwaCegarLoop]: 62 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, 62 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:33,124 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 62 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:33,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-01-09 04:11:33,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2025-01-09 04:11:33,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 28 states have (on average 1.1071428571428572) internal successors, (31), 31 states have internal predecessors, (31), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-01-09 04:11:33,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 58 transitions. [2025-01-09 04:11:33,150 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 58 transitions. Word has length 37 [2025-01-09 04:11:33,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:33,150 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 58 transitions. [2025-01-09 04:11:33,150 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-01-09 04:11:33,151 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 58 transitions. [2025-01-09 04:11:33,151 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-01-09 04:11:33,152 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:33,152 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:33,160 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-01-09 04:11:33,352 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:33,353 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:33,353 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:33,354 INFO L85 PathProgramCache]: Analyzing trace with hash -1619629489, now seen corresponding path program 1 times [2025-01-09 04:11:33,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:33,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1361451482] [2025-01-09 04:11:33,354 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:33,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:33,382 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-09 04:11:33,447 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-09 04:11:33,447 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:33,447 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:33,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1330652257] [2025-01-09 04:11:33,452 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:33,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:33,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:33,454 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:33,455 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:33,543 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-09 04:11:33,603 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-09 04:11:33,604 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:33,604 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:33,606 INFO L256 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-01-09 04:11:33,609 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:33,634 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:33,643 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:33,651 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:33,709 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:33,712 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:33,745 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-01-09 04:11:33,745 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 04:11:33,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:33,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1361451482] [2025-01-09 04:11:33,746 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:33,746 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330652257] [2025-01-09 04:11:33,746 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1330652257] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 04:11:33,746 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 04:11:33,746 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-01-09 04:11:33,746 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [393657211] [2025-01-09 04:11:33,746 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:11:33,747 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 04:11:33,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:33,747 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 04:11:33,747 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-01-09 04:11:33,748 INFO L87 Difference]: Start difference. First operand 47 states and 58 transitions. Second operand has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-01-09 04:11:33,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:33,896 INFO L93 Difference]: Finished difference Result 67 states and 82 transitions. [2025-01-09 04:11:33,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-09 04:11:33,896 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 37 [2025-01-09 04:11:33,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:33,897 INFO L225 Difference]: With dead ends: 67 [2025-01-09 04:11:33,897 INFO L226 Difference]: Without dead ends: 65 [2025-01-09 04:11:33,898 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-01-09 04:11:33,898 INFO L435 NwaCegarLoop]: 51 mSDtfsCounter, 18 mSDsluCounter, 269 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 320 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:33,898 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 320 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 04:11:33,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-01-09 04:11:33,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 64. [2025-01-09 04:11:33,925 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 39 states have (on average 1.1025641025641026) internal successors, (43), 42 states have internal predecessors, (43), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2025-01-09 04:11:33,926 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 79 transitions. [2025-01-09 04:11:33,926 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 79 transitions. Word has length 37 [2025-01-09 04:11:33,926 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:33,926 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 79 transitions. [2025-01-09 04:11:33,926 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-01-09 04:11:33,926 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 79 transitions. [2025-01-09 04:11:33,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-01-09 04:11:33,927 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:33,927 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:33,938 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:34,127 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:34,128 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:34,130 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:34,130 INFO L85 PathProgramCache]: Analyzing trace with hash 509898258, now seen corresponding path program 1 times [2025-01-09 04:11:34,131 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:34,131 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [351334320] [2025-01-09 04:11:34,131 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:34,131 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:34,147 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-09 04:11:34,171 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-09 04:11:34,173 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:34,173 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:34,616 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-01-09 04:11:34,616 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:34,616 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [351334320] [2025-01-09 04:11:34,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [351334320] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:34,616 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [139626375] [2025-01-09 04:11:34,616 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:34,616 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:34,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:34,620 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:34,621 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:34,715 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-09 04:11:34,755 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-09 04:11:34,756 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:34,756 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:34,761 INFO L256 TraceCheckSpWp]: Trace formula consists of 375 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-01-09 04:11:34,763 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:34,798 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:34,802 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:35,048 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 13 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-01-09 04:11:35,049 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:35,320 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-01-09 04:11:35,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [139626375] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 04:11:35,321 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 04:11:35,321 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 11] total 24 [2025-01-09 04:11:35,322 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [181034717] [2025-01-09 04:11:35,322 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:35,322 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-01-09 04:11:35,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:35,323 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-01-09 04:11:35,323 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=477, Unknown=0, NotChecked=0, Total=552 [2025-01-09 04:11:35,323 INFO L87 Difference]: Start difference. First operand 64 states and 79 transitions. Second operand has 24 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 20 states have internal predecessors, (38), 7 states have call successors, (14), 5 states have call predecessors, (14), 7 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2025-01-09 04:11:39,810 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:11:43,870 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:47,972 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:51,991 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:11:52,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:52,025 INFO L93 Difference]: Finished difference Result 124 states and 148 transitions. [2025-01-09 04:11:52,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-01-09 04:11:52,026 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 20 states have internal predecessors, (38), 7 states have call successors, (14), 5 states have call predecessors, (14), 7 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) Word has length 37 [2025-01-09 04:11:52,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:52,028 INFO L225 Difference]: With dead ends: 124 [2025-01-09 04:11:52,028 INFO L226 Difference]: Without dead ends: 112 [2025-01-09 04:11:52,029 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 57 SyntacticMatches, 5 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 198 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=187, Invalid=1145, Unknown=0, NotChecked=0, Total=1332 [2025-01-09 04:11:52,030 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 111 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 529 mSolverCounterSat, 80 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 614 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 529 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.5s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:52,030 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 103 Invalid, 614 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 529 Invalid, 5 Unknown, 0 Unchecked, 16.5s Time] [2025-01-09 04:11:52,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2025-01-09 04:11:52,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 109. [2025-01-09 04:11:52,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 72 states have internal predecessors, (75), 28 states have call successors, (28), 12 states have call predecessors, (28), 12 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2025-01-09 04:11:52,051 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 133 transitions. [2025-01-09 04:11:52,053 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 133 transitions. Word has length 37 [2025-01-09 04:11:52,053 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:52,053 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 133 transitions. [2025-01-09 04:11:52,054 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 20 states have internal predecessors, (38), 7 states have call successors, (14), 5 states have call predecessors, (14), 7 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2025-01-09 04:11:52,054 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 133 transitions. [2025-01-09 04:11:52,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-01-09 04:11:52,055 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:52,055 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2025-01-09 04:11:52,066 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-01-09 04:11:52,255 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:52,256 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:52,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:52,257 INFO L85 PathProgramCache]: Analyzing trace with hash -257668564, now seen corresponding path program 1 times [2025-01-09 04:11:52,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:52,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [452010644] [2025-01-09 04:11:52,257 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:52,257 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:52,285 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-01-09 04:11:52,336 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-01-09 04:11:52,339 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:52,339 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:52,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [820800171] [2025-01-09 04:11:52,345 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:52,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:52,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:52,349 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:52,350 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:52,444 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-01-09 04:11:52,544 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-01-09 04:11:52,545 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:52,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:52,550 INFO L256 TraceCheckSpWp]: Trace formula consists of 499 conjuncts, 152 conjuncts are in the unsatisfiable core [2025-01-09 04:11:52,556 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:52,565 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:52,568 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:11:52,703 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:52,710 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-01-09 04:11:52,716 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:52,724 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:53,273 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:53,594 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:11:53,595 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 29 [2025-01-09 04:11:53,599 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-01-09 04:11:53,606 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-01-09 04:11:53,666 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 04:11:53,667 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:11:54,146 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:11:54,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [452010644] [2025-01-09 04:11:54,147 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:11:54,147 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [820800171] [2025-01-09 04:11:54,147 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [820800171] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:11:54,147 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:11:54,147 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2025-01-09 04:11:54,147 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1088478888] [2025-01-09 04:11:54,147 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:11:54,147 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-01-09 04:11:54,147 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:11:54,148 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-01-09 04:11:54,148 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=475, Unknown=0, NotChecked=0, Total=552 [2025-01-09 04:11:54,148 INFO L87 Difference]: Start difference. First operand 109 states and 133 transitions. Second operand has 22 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 16 states have internal predecessors, (27), 6 states have call successors, (8), 7 states have call predecessors, (8), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2025-01-09 04:11:58,197 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:59,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:11:59,393 INFO L93 Difference]: Finished difference Result 122 states and 143 transitions. [2025-01-09 04:11:59,393 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-01-09 04:11:59,393 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 16 states have internal predecessors, (27), 6 states have call successors, (8), 7 states have call predecessors, (8), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 43 [2025-01-09 04:11:59,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:11:59,394 INFO L225 Difference]: With dead ends: 122 [2025-01-09 04:11:59,394 INFO L226 Difference]: Without dead ends: 120 [2025-01-09 04:11:59,395 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 20 SyntacticMatches, 6 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 303 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=151, Invalid=971, Unknown=0, NotChecked=0, Total=1122 [2025-01-09 04:11:59,395 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 88 mSDsluCounter, 328 mSDsCounter, 0 mSdLazyCounter, 626 mSolverCounterSat, 33 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 660 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 626 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2025-01-09 04:11:59,396 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 364 Invalid, 660 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 626 Invalid, 1 Unknown, 0 Unchecked, 4.8s Time] [2025-01-09 04:11:59,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2025-01-09 04:11:59,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 117. [2025-01-09 04:11:59,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 74 states have (on average 1.0945945945945945) internal successors, (81), 78 states have internal predecessors, (81), 28 states have call successors, (28), 14 states have call predecessors, (28), 14 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2025-01-09 04:11:59,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 139 transitions. [2025-01-09 04:11:59,416 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 139 transitions. Word has length 43 [2025-01-09 04:11:59,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:11:59,416 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 139 transitions. [2025-01-09 04:11:59,416 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 16 states have internal predecessors, (27), 6 states have call successors, (8), 7 states have call predecessors, (8), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2025-01-09 04:11:59,416 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 139 transitions. [2025-01-09 04:11:59,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-01-09 04:11:59,417 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:11:59,417 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:11:59,432 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:59,617 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:59,618 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:11:59,618 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:11:59,618 INFO L85 PathProgramCache]: Analyzing trace with hash 670488903, now seen corresponding path program 1 times [2025-01-09 04:11:59,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:11:59,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2141477069] [2025-01-09 04:11:59,618 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:59,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:11:59,638 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-01-09 04:11:59,670 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-01-09 04:11:59,670 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:59,670 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:11:59,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [914682072] [2025-01-09 04:11:59,672 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:11:59,672 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:11:59,672 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:11:59,674 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:59,677 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:59,759 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-01-09 04:11:59,824 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-01-09 04:11:59,825 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:11:59,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:11:59,827 INFO L256 TraceCheckSpWp]: Trace formula consists of 518 conjuncts, 123 conjuncts are in the unsatisfiable core [2025-01-09 04:11:59,830 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:11:59,833 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:59,835 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:59,857 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:59,861 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:59,865 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:00,293 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2025-01-09 04:12:00,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2025-01-09 04:12:00,301 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:00,345 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 13 proven. 10 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-01-09 04:12:00,346 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:00,649 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 04:12:00,649 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:00,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2141477069] [2025-01-09 04:12:00,652 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:00,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [914682072] [2025-01-09 04:12:00,652 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [914682072] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:00,653 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:00,653 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [15] total 21 [2025-01-09 04:12:00,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1278113023] [2025-01-09 04:12:00,653 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 04:12:00,653 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 04:12:00,653 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:00,653 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 04:12:00,654 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=369, Unknown=0, NotChecked=0, Total=420 [2025-01-09 04:12:00,654 INFO L87 Difference]: Start difference. First operand 117 states and 139 transitions. Second operand has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (9), 4 states have call predecessors, (9), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-01-09 04:12:01,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:01,224 INFO L93 Difference]: Finished difference Result 124 states and 145 transitions. [2025-01-09 04:12:01,224 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 04:12:01,225 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (9), 4 states have call predecessors, (9), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 49 [2025-01-09 04:12:01,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:01,225 INFO L225 Difference]: With dead ends: 124 [2025-01-09 04:12:01,226 INFO L226 Difference]: Without dead ends: 122 [2025-01-09 04:12:01,226 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 68 SyntacticMatches, 9 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 131 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=69, Invalid=531, Unknown=0, NotChecked=0, Total=600 [2025-01-09 04:12:01,227 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 21 mSDsluCounter, 264 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 310 SdHoareTripleChecker+Invalid, 241 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:01,227 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 310 Invalid, 241 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 229 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-01-09 04:12:01,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2025-01-09 04:12:01,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 121. [2025-01-09 04:12:01,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 77 states have (on average 1.0909090909090908) internal successors, (84), 81 states have internal predecessors, (84), 28 states have call successors, (28), 15 states have call predecessors, (28), 15 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2025-01-09 04:12:01,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 142 transitions. [2025-01-09 04:12:01,249 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 142 transitions. Word has length 49 [2025-01-09 04:12:01,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:01,249 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 142 transitions. [2025-01-09 04:12:01,250 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (9), 4 states have call predecessors, (9), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-01-09 04:12:01,250 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 142 transitions. [2025-01-09 04:12:01,250 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-01-09 04:12:01,250 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:01,250 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 04:12:01,258 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:01,455 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:01,455 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:01,455 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:01,455 INFO L85 PathProgramCache]: Analyzing trace with hash 1286680864, now seen corresponding path program 1 times [2025-01-09 04:12:01,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:01,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1413575380] [2025-01-09 04:12:01,455 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:01,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:01,468 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-01-09 04:12:01,486 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-01-09 04:12:01,486 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:01,486 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:01,488 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1149391148] [2025-01-09 04:12:01,488 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:01,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:01,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:01,492 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:01,493 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:01,574 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-01-09 04:12:01,755 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-01-09 04:12:01,755 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:01,756 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:01,759 INFO L256 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 212 conjuncts are in the unsatisfiable core [2025-01-09 04:12:01,764 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:01,775 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:01,777 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:01,877 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 21 treesize of output 17 [2025-01-09 04:12:01,882 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:12:01,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:12:01,892 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:01,906 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:01,912 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 21 treesize of output 17 [2025-01-09 04:12:11,099 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,734 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 67 treesize of output 39 [2025-01-09 04:12:39,745 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-09 04:12:39,745 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 35 treesize of output 31 [2025-01-09 04:12:39,756 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,770 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,775 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2025-01-09 04:12:39,864 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 18 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-01-09 04:12:39,864 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:40,014 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:40,014 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1413575380] [2025-01-09 04:12:40,014 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:40,014 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1149391148] [2025-01-09 04:12:40,014 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1149391148] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:12:40,014 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-01-09 04:12:40,015 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2025-01-09 04:12:40,015 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [418655496] [2025-01-09 04:12:40,015 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:40,015 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-01-09 04:12:40,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:40,016 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-01-09 04:12:40,016 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=473, Unknown=2, NotChecked=0, Total=552 [2025-01-09 04:12:40,016 INFO L87 Difference]: Start difference. First operand 121 states and 142 transitions. Second operand has 22 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 6 states have call successors, (10), 7 states have call predecessors, (10), 4 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2025-01-09 04:12:44,032 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:45,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:12:45,928 INFO L93 Difference]: Finished difference Result 130 states and 149 transitions. [2025-01-09 04:12:45,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-01-09 04:12:45,929 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 6 states have call successors, (10), 7 states have call predecessors, (10), 4 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) Word has length 55 [2025-01-09 04:12:45,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:12:45,932 INFO L225 Difference]: With dead ends: 130 [2025-01-09 04:12:45,932 INFO L226 Difference]: Without dead ends: 128 [2025-01-09 04:12:45,935 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 28 SyntacticMatches, 10 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 335 ImplicationChecksByTransitivity, 37.5s TimeCoverageRelationStatistics Valid=151, Invalid=969, Unknown=2, NotChecked=0, Total=1122 [2025-01-09 04:12:45,935 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 90 mSDsluCounter, 273 mSDsCounter, 0 mSdLazyCounter, 570 mSolverCounterSat, 31 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 602 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 570 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.2s IncrementalHoareTripleChecker+Time [2025-01-09 04:12:45,936 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 308 Invalid, 602 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 570 Invalid, 1 Unknown, 0 Unchecked, 5.2s Time] [2025-01-09 04:12:45,936 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2025-01-09 04:12:45,965 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 125. [2025-01-09 04:12:45,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 80 states have (on average 1.0875) internal successors, (87), 84 states have internal predecessors, (87), 28 states have call successors, (28), 16 states have call predecessors, (28), 16 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2025-01-09 04:12:45,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 145 transitions. [2025-01-09 04:12:45,966 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 145 transitions. Word has length 55 [2025-01-09 04:12:45,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:12:45,966 INFO L471 AbstractCegarLoop]: Abstraction has 125 states and 145 transitions. [2025-01-09 04:12:45,966 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 6 states have call successors, (10), 7 states have call predecessors, (10), 4 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2025-01-09 04:12:45,966 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 145 transitions. [2025-01-09 04:12:45,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-01-09 04:12:45,970 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:12:45,971 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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] [2025-01-09 04:12:45,977 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:46,171 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,SelfDestructingSolverStorable5 [2025-01-09 04:12:46,172 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:12:46,172 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:12:46,172 INFO L85 PathProgramCache]: Analyzing trace with hash -1519499309, now seen corresponding path program 1 times [2025-01-09 04:12:46,172 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:12:46,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1229608796] [2025-01-09 04:12:46,172 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:46,172 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:12:46,194 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-01-09 04:12:46,243 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-01-09 04:12:46,245 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:46,245 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 04:12:46,248 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633767202] [2025-01-09 04:12:46,248 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:12:46,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:12:46,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:12:46,250 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:46,251 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:46,366 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-01-09 04:12:46,462 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-01-09 04:12:46,462 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:12:46,462 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:12:46,468 INFO L256 TraceCheckSpWp]: Trace formula consists of 679 conjuncts, 129 conjuncts are in the unsatisfiable core [2025-01-09 04:12:46,473 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:12:46,499 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:12:46,502 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:46,504 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:46,586 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:46,592 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:46,971 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:46,993 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:47,063 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2025-01-09 04:12:47,066 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 28 treesize of output 16 [2025-01-09 04:12:47,069 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:47,118 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 13 proven. 17 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-01-09 04:12:47,118 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:12:47,330 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-01-09 04:12:47,330 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:12:47,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1229608796] [2025-01-09 04:12:47,330 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 04:12:47,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633767202] [2025-01-09 04:12:47,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633767202] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 04:12:47,330 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 04:12:47,330 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 8] total 23 [2025-01-09 04:12:47,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1744051154] [2025-01-09 04:12:47,330 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 04:12:47,331 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-01-09 04:12:47,331 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:12:47,331 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-01-09 04:12:47,331 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=444, Unknown=0, NotChecked=0, Total=506 [2025-01-09 04:12:47,331 INFO L87 Difference]: Start difference. First operand 125 states and 145 transitions. Second operand has 23 states, 18 states have (on average 2.8333333333333335) internal successors, (51), 17 states have internal predecessors, (51), 10 states have call successors, (23), 8 states have call predecessors, (23), 4 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2025-01-09 04:12:51,893 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:12:56,526 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:00,586 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-01-09 04:13:04,693 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2025-01-09 04:13:08,770 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:08,771 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 04:13:08,771 INFO L93 Difference]: Finished difference Result 170 states and 194 transitions. [2025-01-09 04:13:08,805 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2025-01-09 04:13:08,805 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 18 states have (on average 2.8333333333333335) internal successors, (51), 17 states have internal predecessors, (51), 10 states have call successors, (23), 8 states have call predecessors, (23), 4 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 65 [2025-01-09 04:13:08,805 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 04:13:08,807 INFO L225 Difference]: With dead ends: 170 [2025-01-09 04:13:08,807 INFO L226 Difference]: Without dead ends: 168 [2025-01-09 04:13:08,808 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 96 SyntacticMatches, 12 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 391 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=220, Invalid=1672, Unknown=0, NotChecked=0, Total=1892 [2025-01-09 04:13:08,808 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 102 mSDsluCounter, 416 mSDsCounter, 0 mSdLazyCounter, 760 mSolverCounterSat, 52 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 104 SdHoareTripleChecker+Valid, 456 SdHoareTripleChecker+Invalid, 817 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 760 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.9s IncrementalHoareTripleChecker+Time [2025-01-09 04:13:08,809 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [104 Valid, 456 Invalid, 817 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 760 Invalid, 5 Unknown, 0 Unchecked, 20.9s Time] [2025-01-09 04:13:08,809 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2025-01-09 04:13:08,840 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 161. [2025-01-09 04:13:08,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 103 states have (on average 1.0679611650485437) internal successors, (110), 108 states have internal predecessors, (110), 33 states have call successors, (33), 21 states have call predecessors, (33), 24 states have return successors, (40), 32 states have call predecessors, (40), 32 states have call successors, (40) [2025-01-09 04:13:08,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 183 transitions. [2025-01-09 04:13:08,842 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 183 transitions. Word has length 65 [2025-01-09 04:13:08,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 04:13:08,842 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 183 transitions. [2025-01-09 04:13:08,842 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 18 states have (on average 2.8333333333333335) internal successors, (51), 17 states have internal predecessors, (51), 10 states have call successors, (23), 8 states have call predecessors, (23), 4 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2025-01-09 04:13:08,842 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 183 transitions. [2025-01-09 04:13:08,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-01-09 04:13:08,843 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 04:13:08,843 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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] [2025-01-09 04:13:08,851 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-01-09 04:13:09,046 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:09,046 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 04:13:09,046 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 04:13:09,046 INFO L85 PathProgramCache]: Analyzing trace with hash 49318782, now seen corresponding path program 1 times [2025-01-09 04:13:09,046 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 04:13:09,046 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [470768632] [2025-01-09 04:13:09,046 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:09,047 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 04:13:09,079 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-01-09 04:13:09,103 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-01-09 04:13:09,104 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:09,104 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:09,784 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-01-09 04:13:09,784 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 04:13:09,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [470768632] [2025-01-09 04:13:09,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [470768632] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:09,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1519396020] [2025-01-09 04:13:09,785 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 04:13:09,785 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 04:13:09,785 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 04:13:09,789 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 04:13:09,791 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-01-09 04:13:09,887 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-01-09 04:13:09,950 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-01-09 04:13:09,950 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 04:13:09,950 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 04:13:09,953 INFO L256 TraceCheckSpWp]: Trace formula consists of 717 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-01-09 04:13:09,955 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 04:13:10,066 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:13:10,071 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-09 04:13:10,238 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:10,302 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:13:10,305 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-01-09 04:13:10,411 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:13:10,439 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 22 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 04:13:10,439 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 04:13:10,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1519396020] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 04:13:10,970 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 04:13:10,970 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 19] total 28 [2025-01-09 04:13:10,970 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [786263915] [2025-01-09 04:13:10,971 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 04:13:10,971 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-01-09 04:13:10,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 04:13:10,971 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-01-09 04:13:10,972 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=1084, Unknown=0, NotChecked=0, Total=1190 [2025-01-09 04:13:10,972 INFO L87 Difference]: Start difference. First operand 161 states and 183 transitions. Second operand has 28 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 26 states have internal predecessors, (55), 12 states have call successors, (19), 7 states have call predecessors, (19), 9 states have return successors, (18), 10 states have call predecessors, (18), 11 states have call successors, (18)