./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 c00e63dc Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_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-?-c00e63d-m [2025-02-05 16:02:46,614 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-05 16:02:46,658 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-02-05 16:02:46,662 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-05 16:02:46,663 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-05 16:02:46,676 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-05 16:02:46,677 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-05 16:02:46,677 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-05 16:02:46,677 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-05 16:02:46,677 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-05 16:02:46,677 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-05 16:02:46,677 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-05 16:02:46,678 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * Use SBE=true [2025-02-05 16:02:46,678 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-05 16:02:46,678 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-05 16:02:46,679 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-05 16:02:46,679 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 16:02:46,680 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-05 16:02:46,680 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-05 16:02:46,680 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-02-05 16:02:46,936 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-05 16:02:46,942 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-05 16:02:46,944 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-05 16:02:46,945 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-05 16:02:46,946 INFO L274 PluginConnector]: CDTParser initialized [2025-02-05 16:02:46,947 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-02-05 16:02:48,077 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/22bf45f27/088ef436cfe34d73895d5c92e00e63f7/FLAGb45af13ba [2025-02-05 16:02:48,365 INFO L384 CDTParser]: Found 1 translation units. [2025-02-05 16:02:48,365 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd2-ll.c [2025-02-05 16:02:48,373 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/22bf45f27/088ef436cfe34d73895d5c92e00e63f7/FLAGb45af13ba [2025-02-05 16:02:48,649 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/22bf45f27/088ef436cfe34d73895d5c92e00e63f7 [2025-02-05 16:02:48,651 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-05 16:02:48,653 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-05 16:02:48,655 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-05 16:02:48,655 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-05 16:02:48,658 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-05 16:02:48,659 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,660 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6f100305 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48, skipping insertion in model container [2025-02-05 16:02:48,661 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,671 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-05 16:02:48,775 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-02-05 16:02:48,798 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 16:02:48,804 INFO L200 MainTranslator]: Completed pre-run [2025-02-05 16:02:48,811 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-02-05 16:02:48,838 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 16:02:48,849 INFO L204 MainTranslator]: Completed translation [2025-02-05 16:02:48,849 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48 WrapperNode [2025-02-05 16:02:48,850 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-05 16:02:48,851 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-05 16:02:48,851 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-05 16:02:48,851 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-05 16:02:48,856 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,862 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,882 INFO L138 Inliner]: procedures = 17, calls = 141, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 137 [2025-02-05 16:02:48,883 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-05 16:02:48,884 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-05 16:02:48,884 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-05 16:02:48,884 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-05 16:02:48,890 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,891 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,898 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,919 INFO L175 MemorySlicer]: Split 86 memory accesses to 13 slices as follows [2, 7, 10, 7, 7, 3, 3, 8, 5, 8, 5, 12, 9]. 14 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The 22 writes are split as follows [0, 3, 2, 2, 3, 1, 1, 2, 2, 2, 2, 1, 1]. [2025-02-05 16:02:48,922 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,923 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,932 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,935 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,937 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,941 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,944 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-05 16:02:48,945 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-05 16:02:48,945 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-05 16:02:48,945 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-05 16:02:48,948 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (1/1) ... [2025-02-05 16:02:48,951 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 16:02:48,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:48,974 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-02-05 16:02:48,978 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-02-05 16:02:48,993 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-05 16:02:48,993 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-02-05 16:02:48,994 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#9 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#10 [2025-02-05 16:02:48,994 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#11 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#12 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#9 [2025-02-05 16:02:48,995 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#10 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#11 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#12 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_45_to_53_0 [2025-02-05 16:02:48,996 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_45_to_53_0 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_39_to_65_0 [2025-02-05 16:02:48,996 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_39_to_65_0 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-05 16:02:48,996 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-02-05 16:02:48,996 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#9 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#10 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#11 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#12 [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-02-05 16:02:48,997 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-02-05 16:02:48,997 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-02-05 16:02:49,117 INFO L257 CfgBuilder]: Building ICFG [2025-02-05 16:02:49,118 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-05 16:02:49,362 INFO L1309 $ProcedureCfgBuilder]: dead code at ProgramPoint L138: havoc main_#t~mem67#1;call ULTIMATE.dealloc(main_~#x~0#1.base, main_~#x~0#1.offset);havoc main_~#x~0#1.base, main_~#x~0#1.offset;call ULTIMATE.dealloc(main_~#y~0#1.base, main_~#y~0#1.offset);havoc main_~#y~0#1.base, main_~#y~0#1.offset;call ULTIMATE.dealloc(main_~#a~0#1.base, main_~#a~0#1.offset);havoc main_~#a~0#1.base, main_~#a~0#1.offset;call ULTIMATE.dealloc(main_~#b~0#1.base, main_~#b~0#1.offset);havoc main_~#b~0#1.base, main_~#b~0#1.offset;call ULTIMATE.dealloc(main_~#p~0#1.base, main_~#p~0#1.offset);havoc main_~#p~0#1.base, main_~#p~0#1.offset;call ULTIMATE.dealloc(main_~#q~0#1.base, main_~#q~0#1.offset);havoc main_~#q~0#1.base, main_~#q~0#1.offset;call ULTIMATE.dealloc(main_~#r~0#1.base, main_~#r~0#1.offset);havoc main_~#r~0#1.base, main_~#r~0#1.offset;call ULTIMATE.dealloc(main_~#s~0#1.base, main_~#s~0#1.offset);havoc main_~#s~0#1.base, main_~#s~0#1.offset;call ULTIMATE.dealloc(main_~#c~0#1.base, main_~#c~0#1.offset);havoc main_~#c~0#1.base, main_~#c~0#1.offset;call ULTIMATE.dealloc(main_~#k~0#1.base, main_~#k~0#1.offset);havoc main_~#k~0#1.base, main_~#k~0#1.offset;call ULTIMATE.dealloc(main_~#xy~0#1.base, main_~#xy~0#1.offset);havoc main_~#xy~0#1.base, main_~#xy~0#1.offset;call ULTIMATE.dealloc(main_~#yy~0#1.base, main_~#yy~0#1.offset);havoc main_~#yy~0#1.base, main_~#yy~0#1.offset; [2025-02-05 16:02:49,389 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-02-05 16:02:49,391 INFO L308 CfgBuilder]: Performing block encoding [2025-02-05 16:02:49,397 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-05 16:02:49,398 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-05 16:02:49,398 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 04:02:49 BoogieIcfgContainer [2025-02-05 16:02:49,398 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-05 16:02:49,400 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-05 16:02:49,400 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-05 16:02:49,403 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-05 16:02:49,403 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.02 04:02:48" (1/3) ... [2025-02-05 16:02:49,404 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@48fce350 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 04:02:49, skipping insertion in model container [2025-02-05 16:02:49,404 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 04:02:48" (2/3) ... [2025-02-05 16:02:49,404 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@48fce350 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 04:02:49, skipping insertion in model container [2025-02-05 16:02:49,404 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 04:02:49" (3/3) ... [2025-02-05 16:02:49,405 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_egcd2-ll.c [2025-02-05 16:02:49,416 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-05 16:02:49,417 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-02-05 16:02:49,459 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-05 16:02:49,468 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;@52f661e2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-05 16:02:49,468 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-02-05 16:02:49,472 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-02-05 16:02:49,477 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-02-05 16:02:49,477 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:49,478 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-02-05 16:02:49,478 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:49,482 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:49,482 INFO L85 PathProgramCache]: Analyzing trace with hash -1266269525, now seen corresponding path program 1 times [2025-02-05 16:02:49,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:49,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1669009417] [2025-02-05 16:02:49,488 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:49,489 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:49,578 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-05 16:02:49,614 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-05 16:02:49,614 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:49,615 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:49,709 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-05 16:02:49,710 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:49,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1669009417] [2025-02-05 16:02:49,711 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1669009417] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:49,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1523217052] [2025-02-05 16:02:49,711 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:49,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:02:49,712 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:49,715 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:02:49,715 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-02-05 16:02:49,810 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-05 16:02:49,889 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-05 16:02:49,889 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:49,889 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:49,892 INFO L256 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-02-05 16:02:49,897 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:02:49,907 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-05 16:02:49,907 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 16:02:49,907 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1523217052] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 16:02:49,907 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:02:49,908 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-02-05 16:02:49,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [588730744] [2025-02-05 16:02:49,909 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 16:02:49,912 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-02-05 16:02:49,912 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:49,925 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-02-05 16:02:49,925 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-02-05 16:02:49,927 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-02-05 16:02:49,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:02:49,946 INFO L93 Difference]: Finished difference Result 99 states and 142 transitions. [2025-02-05 16:02:49,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-02-05 16:02:49,948 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-02-05 16:02:49,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:02:49,952 INFO L225 Difference]: With dead ends: 99 [2025-02-05 16:02:49,952 INFO L226 Difference]: Without dead ends: 47 [2025-02-05 16:02:49,954 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-02-05 16:02:49,955 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-02-05 16:02:49,956 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-02-05 16:02:49,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-02-05 16:02:49,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2025-02-05 16:02:49,976 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-02-05 16:02:49,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 58 transitions. [2025-02-05 16:02:49,982 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 58 transitions. Word has length 37 [2025-02-05 16:02:49,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:02:49,982 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 58 transitions. [2025-02-05 16:02:49,983 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-02-05 16:02:49,983 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 58 transitions. [2025-02-05 16:02:49,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-02-05 16:02:49,984 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:49,984 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-02-05 16:02:49,991 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-02-05 16:02:50,188 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-02-05 16:02:50,188 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:50,189 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:50,189 INFO L85 PathProgramCache]: Analyzing trace with hash -769429713, now seen corresponding path program 1 times [2025-02-05 16:02:50,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:50,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1264901761] [2025-02-05 16:02:50,189 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:50,189 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:50,213 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-05 16:02:50,289 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-05 16:02:50,292 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:50,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:02:50,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1373815511] [2025-02-05 16:02:50,301 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:50,301 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:02:50,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:50,303 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:02:50,305 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-02-05 16:02:50,400 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-05 16:02:50,461 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-05 16:02:50,462 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:50,462 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:50,465 INFO L256 TraceCheckSpWp]: Trace formula consists of 480 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-02-05 16:02:50,470 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:02:50,506 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:02:50,511 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:02:50,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:02:50,528 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:02:50,539 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:02:50,611 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:02:50,616 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-02-05 16:02:50,623 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2025-02-05 16:02:50,652 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-02-05 16:02:50,652 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 16:02:50,653 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:50,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1264901761] [2025-02-05 16:02:50,653 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:02:50,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1373815511] [2025-02-05 16:02:50,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1373815511] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 16:02:50,653 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 16:02:50,653 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-02-05 16:02:50,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [924242572] [2025-02-05 16:02:50,653 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 16:02:50,654 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-02-05 16:02:50,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:50,654 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-02-05 16:02:50,654 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-02-05 16:02:50,654 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-02-05 16:02:50,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:02:50,838 INFO L93 Difference]: Finished difference Result 67 states and 82 transitions. [2025-02-05 16:02:50,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-02-05 16:02:50,839 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-02-05 16:02:50,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:02:50,840 INFO L225 Difference]: With dead ends: 67 [2025-02-05 16:02:50,840 INFO L226 Difference]: Without dead ends: 65 [2025-02-05 16:02:50,840 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-02-05 16:02:50,841 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-02-05 16:02:50,841 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-02-05 16:02:50,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-02-05 16:02:50,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 64. [2025-02-05 16:02:50,853 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-02-05 16:02:50,854 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 79 transitions. [2025-02-05 16:02:50,854 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 79 transitions. Word has length 37 [2025-02-05 16:02:50,854 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:02:50,854 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 79 transitions. [2025-02-05 16:02:50,854 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-02-05 16:02:50,854 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 79 transitions. [2025-02-05 16:02:50,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-02-05 16:02:50,855 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:02:50,855 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-02-05 16:02:50,862 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-02-05 16:02:51,055 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-02-05 16:02:51,056 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:02:51,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:02:51,056 INFO L85 PathProgramCache]: Analyzing trace with hash -29746185, now seen corresponding path program 1 times [2025-02-05 16:02:51,057 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:02:51,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510636287] [2025-02-05 16:02:51,057 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:51,057 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:02:51,072 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-05 16:02:51,101 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-05 16:02:51,101 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:51,101 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:51,523 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-02-05 16:02:51,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:02:51,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1510636287] [2025-02-05 16:02:51,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1510636287] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:02:51,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [207864207] [2025-02-05 16:02:51,523 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:02:51,523 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:02:51,524 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:02:51,525 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:02:51,529 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-02-05 16:02:51,608 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-02-05 16:02:51,643 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-02-05 16:02:51,644 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:02:51,644 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:02:51,645 INFO L256 TraceCheckSpWp]: Trace formula consists of 375 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-02-05 16:02:51,647 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:02:51,687 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:02:51,689 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:02:51,863 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 13 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-02-05 16:02:51,863 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:02:52,149 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-02-05 16:02:52,150 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [207864207] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 16:02:52,150 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-05 16:02:52,150 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 11] total 24 [2025-02-05 16:02:52,150 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1565017852] [2025-02-05 16:02:52,150 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-05 16:02:52,150 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-02-05 16:02:52,150 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:02:52,152 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-02-05 16:02:52,152 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=477, Unknown=0, NotChecked=0, Total=552 [2025-02-05 16:02:52,154 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-02-05 16:02:56,696 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-02-05 16:03:00,775 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:04,882 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:08,900 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-02-05 16:03:08,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:08,938 INFO L93 Difference]: Finished difference Result 124 states and 148 transitions. [2025-02-05 16:03:08,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-02-05 16:03:08,939 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-02-05 16:03:08,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:08,940 INFO L225 Difference]: With dead ends: 124 [2025-02-05 16:03:08,940 INFO L226 Difference]: Without dead ends: 112 [2025-02-05 16:03:08,941 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-02-05 16:03:08,943 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 111 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 526 mSolverCounterSat, 80 mSolverCounterUnsat, 8 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, 526 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.5s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:08,943 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 103 Invalid, 614 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 526 Invalid, 8 Unknown, 0 Unchecked, 16.5s Time] [2025-02-05 16:03:08,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2025-02-05 16:03:08,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 109. [2025-02-05 16:03:08,963 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-02-05 16:03:08,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 133 transitions. [2025-02-05 16:03:08,966 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 133 transitions. Word has length 37 [2025-02-05 16:03:08,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:08,967 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 133 transitions. [2025-02-05 16:03:08,967 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-02-05 16:03:08,967 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 133 transitions. [2025-02-05 16:03:08,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-02-05 16:03:08,967 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:08,968 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-02-05 16:03:08,976 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-02-05 16:03:09,168 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-02-05 16:03:09,168 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:09,169 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:09,169 INFO L85 PathProgramCache]: Analyzing trace with hash -1408670920, now seen corresponding path program 1 times [2025-02-05 16:03:09,169 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:09,169 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107753624] [2025-02-05 16:03:09,169 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:09,169 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:09,182 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-02-05 16:03:09,207 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-02-05 16:03:09,208 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:09,208 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:03:09,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [605162295] [2025-02-05 16:03:09,210 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:09,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:09,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:09,211 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:03:09,213 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-02-05 16:03:09,292 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-02-05 16:03:09,353 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-02-05 16:03:09,353 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:09,353 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:09,362 INFO L256 TraceCheckSpWp]: Trace formula consists of 499 conjuncts, 125 conjuncts are in the unsatisfiable core [2025-02-05 16:03:09,366 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:09,374 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:09,376 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:09,474 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:09,481 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:09,488 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:03:10,264 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:03:10,275 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:03:10,275 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 29 treesize of output 25 [2025-02-05 16:03:10,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-02-05 16:03:10,353 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-05 16:03:10,353 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:03:10,652 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-02-05 16:03:10,652 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:03:10,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107753624] [2025-02-05 16:03:10,653 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:03:10,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [605162295] [2025-02-05 16:03:10,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [605162295] provided 1 perfect and 1 imperfect interpolant sequences [2025-02-05 16:03:10,653 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:03:10,653 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [20] total 26 [2025-02-05 16:03:10,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [253107391] [2025-02-05 16:03:10,653 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 16:03:10,653 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-02-05 16:03:10,653 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:03:10,654 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-02-05 16:03:10,654 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=573, Unknown=0, NotChecked=0, Total=650 [2025-02-05 16:03:10,654 INFO L87 Difference]: Start difference. First operand 109 states and 133 transitions. Second operand has 10 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 7 states have internal predecessors, (21), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-02-05 16:03:11,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:11,219 INFO L93 Difference]: Finished difference Result 116 states and 139 transitions. [2025-02-05 16:03:11,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-02-05 16:03:11,219 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 7 states have internal predecessors, (21), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 43 [2025-02-05 16:03:11,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:11,220 INFO L225 Difference]: With dead ends: 116 [2025-02-05 16:03:11,220 INFO L226 Difference]: Without dead ends: 114 [2025-02-05 16:03:11,221 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 53 SyntacticMatches, 7 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 273 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=95, Invalid=775, Unknown=0, NotChecked=0, Total=870 [2025-02-05 16:03:11,222 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 22 mSDsluCounter, 280 mSDsCounter, 0 mSdLazyCounter, 211 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 328 SdHoareTripleChecker+Invalid, 224 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 211 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:11,222 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 328 Invalid, 224 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 211 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-02-05 16:03:11,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2025-02-05 16:03:11,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 113. [2025-02-05 16:03:11,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 71 states have (on average 1.0985915492957747) internal successors, (78), 75 states have internal predecessors, (78), 28 states have call successors, (28), 13 states have call predecessors, (28), 13 states have return successors, (30), 26 states have call predecessors, (30), 27 states have call successors, (30) [2025-02-05 16:03:11,243 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 136 transitions. [2025-02-05 16:03:11,244 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 136 transitions. Word has length 43 [2025-02-05 16:03:11,244 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:11,244 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 136 transitions. [2025-02-05 16:03:11,244 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 7 states have internal predecessors, (21), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-02-05 16:03:11,244 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 136 transitions. [2025-02-05 16:03:11,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-02-05 16:03:11,245 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:11,245 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-02-05 16:03:11,253 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-02-05 16:03:11,445 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-02-05 16:03:11,446 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:11,446 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:11,446 INFO L85 PathProgramCache]: Analyzing trace with hash 255435651, now seen corresponding path program 1 times [2025-02-05 16:03:11,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:11,446 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [63390728] [2025-02-05 16:03:11,446 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:11,446 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:11,464 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-02-05 16:03:11,502 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-02-05 16:03:11,503 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:11,503 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:03:11,505 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [167239274] [2025-02-05 16:03:11,505 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:11,505 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:11,505 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:11,507 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:03:11,508 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-02-05 16:03:11,588 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-02-05 16:03:11,648 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-02-05 16:03:11,649 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:11,649 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:11,652 INFO L256 TraceCheckSpWp]: Trace formula consists of 518 conjuncts, 93 conjuncts are in the unsatisfiable core [2025-02-05 16:03:11,657 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:11,662 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:11,668 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:03:11,671 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:11,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:11,965 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:03:11,967 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-02-05 16:03:11,995 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-02-05 16:03:11,996 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:03:12,062 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:03:12,062 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [63390728] [2025-02-05 16:03:12,062 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:03:12,062 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [167239274] [2025-02-05 16:03:12,062 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [167239274] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:03:12,062 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:03:12,062 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2025-02-05 16:03:12,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1314069390] [2025-02-05 16:03:12,062 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-02-05 16:03:12,062 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-02-05 16:03:12,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:03:12,063 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-02-05 16:03:12,063 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2025-02-05 16:03:12,063 INFO L87 Difference]: Start difference. First operand 113 states and 136 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-02-05 16:03:12,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:12,431 INFO L93 Difference]: Finished difference Result 122 states and 143 transitions. [2025-02-05 16:03:12,432 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-02-05 16:03:12,432 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 49 [2025-02-05 16:03:12,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:12,433 INFO L225 Difference]: With dead ends: 122 [2025-02-05 16:03:12,433 INFO L226 Difference]: Without dead ends: 120 [2025-02-05 16:03:12,434 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 34 SyntacticMatches, 9 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2025-02-05 16:03:12,434 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 23 mSDsluCounter, 310 mSDsCounter, 0 mSdLazyCounter, 262 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 354 SdHoareTripleChecker+Invalid, 276 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 262 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:12,434 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 354 Invalid, 276 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 262 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-05 16:03:12,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2025-02-05 16:03:12,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 117. [2025-02-05 16:03:12,452 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-02-05 16:03:12,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 139 transitions. [2025-02-05 16:03:12,455 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 139 transitions. Word has length 49 [2025-02-05 16:03:12,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:12,455 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 139 transitions. [2025-02-05 16:03:12,455 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 5 states have call successors, (9), 5 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-02-05 16:03:12,455 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 139 transitions. [2025-02-05 16:03:12,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-02-05 16:03:12,456 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:12,456 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-02-05 16:03:12,464 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-02-05 16:03:12,656 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-02-05 16:03:12,657 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:12,657 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:12,657 INFO L85 PathProgramCache]: Analyzing trace with hash 1495692944, now seen corresponding path program 1 times [2025-02-05 16:03:12,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:12,657 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1025031283] [2025-02-05 16:03:12,657 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:12,657 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:12,669 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-02-05 16:03:12,714 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-02-05 16:03:12,714 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:12,714 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:03:12,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [118981953] [2025-02-05 16:03:12,715 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:12,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:12,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:12,717 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-02-05 16:03:12,719 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-02-05 16:03:12,804 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-02-05 16:03:12,912 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-02-05 16:03:12,912 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:12,912 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:12,916 INFO L256 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 163 conjuncts are in the unsatisfiable core [2025-02-05 16:03:12,920 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:12,927 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:12,929 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:13,012 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:13,016 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-02-05 16:03:13,020 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:03:13,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:13,044 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:03:13,044 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 36 [2025-02-05 16:03:13,050 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 17 treesize of output 13 [2025-02-05 16:03:18,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 63 treesize of output 35 [2025-02-05 16:03:18,718 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2025-02-05 16:03:18,725 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-02-05 16:03:18,732 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2025-02-05 16:03:18,843 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 20 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-02-05 16:03:18,844 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:03:19,005 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:03:19,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1025031283] [2025-02-05 16:03:19,005 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:03:19,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [118981953] [2025-02-05 16:03:19,005 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [118981953] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:03:19,005 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:03:19,005 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-02-05 16:03:19,005 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [83918319] [2025-02-05 16:03:19,005 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-02-05 16:03:19,006 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-02-05 16:03:19,006 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:03:19,006 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-02-05 16:03:19,006 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=445, Unknown=0, NotChecked=0, Total=506 [2025-02-05 16:03:19,006 INFO L87 Difference]: Start difference. First operand 117 states and 139 transitions. Second operand has 21 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 15 states have internal predecessors, (29), 6 states have call successors, (10), 6 states have call predecessors, (10), 3 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2025-02-05 16:03:23,051 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:25,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:25,525 INFO L93 Difference]: Finished difference Result 130 states and 149 transitions. [2025-02-05 16:03:25,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-02-05 16:03:25,526 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 15 states have internal predecessors, (29), 6 states have call successors, (10), 6 states have call predecessors, (10), 3 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) Word has length 55 [2025-02-05 16:03:25,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:25,527 INFO L225 Difference]: With dead ends: 130 [2025-02-05 16:03:25,527 INFO L226 Difference]: Without dead ends: 128 [2025-02-05 16:03:25,527 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 28 SyntacticMatches, 11 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 342 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=163, Invalid=1169, Unknown=0, NotChecked=0, Total=1332 [2025-02-05 16:03:25,528 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 84 mSDsluCounter, 375 mSDsCounter, 0 mSdLazyCounter, 632 mSolverCounterSat, 35 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 87 SdHoareTripleChecker+Valid, 410 SdHoareTripleChecker+Invalid, 668 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 632 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.5s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:25,528 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [87 Valid, 410 Invalid, 668 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 632 Invalid, 1 Unknown, 0 Unchecked, 5.5s Time] [2025-02-05 16:03:25,528 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2025-02-05 16:03:25,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 125. [2025-02-05 16:03:25,545 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-02-05 16:03:25,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 145 transitions. [2025-02-05 16:03:25,546 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 145 transitions. Word has length 55 [2025-02-05 16:03:25,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:25,546 INFO L471 AbstractCegarLoop]: Abstraction has 125 states and 145 transitions. [2025-02-05 16:03:25,546 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 15 states have internal predecessors, (29), 6 states have call successors, (10), 6 states have call predecessors, (10), 3 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2025-02-05 16:03:25,546 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 145 transitions. [2025-02-05 16:03:25,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-02-05 16:03:25,547 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:25,547 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-02-05 16:03:25,554 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-02-05 16:03:25,747 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-02-05 16:03:25,748 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:25,748 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:25,748 INFO L85 PathProgramCache]: Analyzing trace with hash 2118624736, now seen corresponding path program 1 times [2025-02-05 16:03:25,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:25,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1903397104] [2025-02-05 16:03:25,748 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:25,748 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:25,761 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-02-05 16:03:25,796 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-02-05 16:03:25,797 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:25,797 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:03:25,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1863889373] [2025-02-05 16:03:25,799 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:25,800 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:25,800 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:25,801 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-02-05 16:03:25,803 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-02-05 16:03:25,896 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-02-05 16:03:26,009 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-02-05 16:03:26,009 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:26,009 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:26,014 INFO L256 TraceCheckSpWp]: Trace formula consists of 679 conjuncts, 161 conjuncts are in the unsatisfiable core [2025-02-05 16:03:26,019 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:26,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:26,052 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:03:26,056 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:26,058 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:03:26,533 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:03:26,539 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:03:26,913 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:03:27,021 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:03:27,025 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-02-05 16:03:27,080 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-02-05 16:03:27,082 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-02-05 16:03:27,085 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2025-02-05 16:03:27,127 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 13 proven. 29 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2025-02-05 16:03:27,127 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:03:27,306 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-02-05 16:03:27,306 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:03:27,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1903397104] [2025-02-05 16:03:27,306 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:03:27,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1863889373] [2025-02-05 16:03:27,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1863889373] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 16:03:27,306 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 16:03:27,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 8] total 25 [2025-02-05 16:03:27,306 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1038618998] [2025-02-05 16:03:27,306 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 16:03:27,306 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-02-05 16:03:27,306 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:03:27,307 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-02-05 16:03:27,307 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=528, Unknown=0, NotChecked=0, Total=600 [2025-02-05 16:03:27,307 INFO L87 Difference]: Start difference. First operand 125 states and 145 transitions. Second operand has 25 states, 20 states have (on average 2.7) internal successors, (54), 19 states have internal predecessors, (54), 11 states have call successors, (23), 9 states have call predecessors, (23), 5 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2025-02-05 16:03:32,486 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:36,965 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-02-05 16:03:40,986 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-02-05 16:03:41,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:03:41,046 INFO L93 Difference]: Finished difference Result 170 states and 194 transitions. [2025-02-05 16:03:41,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2025-02-05 16:03:41,046 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 20 states have (on average 2.7) internal successors, (54), 19 states have internal predecessors, (54), 11 states have call successors, (23), 9 states have call predecessors, (23), 5 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 65 [2025-02-05 16:03:41,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:03:41,048 INFO L225 Difference]: With dead ends: 170 [2025-02-05 16:03:41,048 INFO L226 Difference]: Without dead ends: 168 [2025-02-05 16:03:41,048 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 95 SyntacticMatches, 11 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 481 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=246, Invalid=1916, Unknown=0, NotChecked=0, Total=2162 [2025-02-05 16:03:41,049 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 93 mSDsluCounter, 497 mSDsCounter, 0 mSdLazyCounter, 893 mSolverCounterSat, 50 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 537 SdHoareTripleChecker+Invalid, 946 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 893 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.9s IncrementalHoareTripleChecker+Time [2025-02-05 16:03:41,049 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 537 Invalid, 946 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 893 Invalid, 3 Unknown, 0 Unchecked, 12.9s Time] [2025-02-05 16:03:41,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2025-02-05 16:03:41,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 161. [2025-02-05 16:03:41,078 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-02-05 16:03:41,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 183 transitions. [2025-02-05 16:03:41,079 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 183 transitions. Word has length 65 [2025-02-05 16:03:41,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:03:41,080 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 183 transitions. [2025-02-05 16:03:41,080 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 20 states have (on average 2.7) internal successors, (54), 19 states have internal predecessors, (54), 11 states have call successors, (23), 9 states have call predecessors, (23), 5 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2025-02-05 16:03:41,080 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 183 transitions. [2025-02-05 16:03:41,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-02-05 16:03:41,083 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:03:41,083 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-02-05 16:03:41,092 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-02-05 16:03:41,284 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-02-05 16:03:41,284 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:03:41,284 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:03:41,285 INFO L85 PathProgramCache]: Analyzing trace with hash 2003110460, now seen corresponding path program 1 times [2025-02-05 16:03:41,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:03:41,285 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [685242624] [2025-02-05 16:03:41,285 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:41,285 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:03:41,308 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-02-05 16:03:41,328 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-02-05 16:03:41,328 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:41,328 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:42,004 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-02-05 16:03:42,005 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:03:42,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [685242624] [2025-02-05 16:03:42,005 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [685242624] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:03:42,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1055899411] [2025-02-05 16:03:42,005 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:03:42,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:03:42,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:03:42,007 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-02-05 16:03:42,008 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-02-05 16:03:42,106 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-02-05 16:03:42,156 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-02-05 16:03:42,156 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:03:42,156 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:03:42,158 INFO L256 TraceCheckSpWp]: Trace formula consists of 717 conjuncts, 39 conjuncts are in the unsatisfiable core [2025-02-05 16:03:42,161 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:03:42,250 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:42,251 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:03:42,386 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:42,426 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:03:42,428 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-02-05 16:03:42,498 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-02-05 16:03:42,534 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 22 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-02-05 16:03:42,534 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:03:42,937 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1055899411] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:03:42,937 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 16:03:42,937 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 19] total 27 [2025-02-05 16:03:42,937 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792030733] [2025-02-05 16:03:42,937 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 16:03:42,937 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-02-05 16:03:42,937 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:03:42,938 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-02-05 16:03:42,938 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=1018, Unknown=0, NotChecked=0, Total=1122 [2025-02-05 16:03:42,938 INFO L87 Difference]: Start difference. First operand 161 states and 183 transitions. Second operand has 27 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 25 states have internal predecessors, (53), 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) [2025-02-05 16:03:46,942 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:03:51,753 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-02-05 16:03:55,873 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:04:00,059 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-02-05 16:04:04,151 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:04:08,187 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-02-05 16:04:12,311 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-02-05 16:04:12,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:04:12,312 INFO L93 Difference]: Finished difference Result 179 states and 205 transitions. [2025-02-05 16:04:12,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-02-05 16:04:12,321 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 25 states have internal predecessors, (53), 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) Word has length 74 [2025-02-05 16:04:12,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:04:12,322 INFO L225 Difference]: With dead ends: 179 [2025-02-05 16:04:12,322 INFO L226 Difference]: Without dead ends: 169 [2025-02-05 16:04:12,323 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 76 SyntacticMatches, 6 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 587 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=419, Invalid=3003, Unknown=0, NotChecked=0, Total=3422 [2025-02-05 16:04:12,324 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 167 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 1021 mSolverCounterSat, 153 mSolverCounterUnsat, 11 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 28.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 1185 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 1021 IncrementalHoareTripleChecker+Invalid, 11 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 28.8s IncrementalHoareTripleChecker+Time [2025-02-05 16:04:12,324 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [170 Valid, 145 Invalid, 1185 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 1021 Invalid, 11 Unknown, 0 Unchecked, 28.8s Time] [2025-02-05 16:04:12,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2025-02-05 16:04:12,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 167. [2025-02-05 16:04:12,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 106 states have (on average 1.0660377358490567) internal successors, (113), 111 states have internal predecessors, (113), 34 states have call successors, (34), 21 states have call predecessors, (34), 26 states have return successors, (45), 34 states have call predecessors, (45), 33 states have call successors, (45) [2025-02-05 16:04:12,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 192 transitions. [2025-02-05 16:04:12,365 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 192 transitions. Word has length 74 [2025-02-05 16:04:12,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:04:12,365 INFO L471 AbstractCegarLoop]: Abstraction has 167 states and 192 transitions. [2025-02-05 16:04:12,365 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 25 states have internal predecessors, (53), 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) [2025-02-05 16:04:12,365 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 192 transitions. [2025-02-05 16:04:12,365 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-02-05 16:04:12,365 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:04:12,365 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 16:04:12,373 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-02-05 16:04:12,566 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:04:12,566 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:04:12,566 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:04:12,566 INFO L85 PathProgramCache]: Analyzing trace with hash -2067524978, now seen corresponding path program 1 times [2025-02-05 16:04:12,567 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:04:12,567 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1542202469] [2025-02-05 16:04:12,567 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:04:12,567 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:04:12,581 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-02-05 16:04:12,619 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-02-05 16:04:12,620 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:04:12,620 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:04:12,622 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2145152133] [2025-02-05 16:04:12,622 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 16:04:12,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:04:12,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:04:12,624 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:04:12,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-02-05 16:04:12,731 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-02-05 16:04:12,892 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-02-05 16:04:12,892 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 16:04:12,892 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:04:12,898 INFO L256 TraceCheckSpWp]: Trace formula consists of 839 conjuncts, 283 conjuncts are in the unsatisfiable core [2025-02-05 16:04:12,904 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:04:12,910 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:04:12,913 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:04:12,990 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:12,995 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:04:13,004 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:13,016 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:04:13,456 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:04:13,492 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:14,579 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:14,591 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:14,591 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 51 treesize of output 47 [2025-02-05 16:04:14,627 INFO L349 Elim1Store]: treesize reduction 20, result has 58.3 percent of original size [2025-02-05 16:04:14,627 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 49 treesize of output 60 [2025-02-05 16:04:14,638 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 45 treesize of output 33 [2025-02-05 16:04:14,704 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:15,934 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:15,934 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 97 [2025-02-05 16:04:15,993 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:15,994 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 85 treesize of output 165 [2025-02-05 16:04:16,016 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:16,017 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 31 treesize of output 27 [2025-02-05 16:04:16,204 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 8 proven. 47 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-02-05 16:04:16,204 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:04:16,339 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:04:16,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1542202469] [2025-02-05 16:04:16,339 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:04:16,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2145152133] [2025-02-05 16:04:16,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2145152133] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:04:16,339 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:04:16,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30] total 30 [2025-02-05 16:04:16,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1562532057] [2025-02-05 16:04:16,340 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-02-05 16:04:16,341 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-02-05 16:04:16,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:04:16,341 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-02-05 16:04:16,341 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=881, Unknown=0, NotChecked=0, Total=992 [2025-02-05 16:04:16,341 INFO L87 Difference]: Start difference. First operand 167 states and 192 transitions. Second operand has 30 states, 26 states have (on average 1.6153846153846154) internal successors, (42), 21 states have internal predecessors, (42), 8 states have call successors, (14), 9 states have call predecessors, (14), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2025-02-05 16:04:20,389 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-02-05 16:04:23,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 16:04:23,257 INFO L93 Difference]: Finished difference Result 229 states and 263 transitions. [2025-02-05 16:04:23,257 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2025-02-05 16:04:23,257 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 26 states have (on average 1.6153846153846154) internal successors, (42), 21 states have internal predecessors, (42), 8 states have call successors, (14), 9 states have call predecessors, (14), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) Word has length 78 [2025-02-05 16:04:23,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 16:04:23,258 INFO L225 Difference]: With dead ends: 229 [2025-02-05 16:04:23,258 INFO L226 Difference]: Without dead ends: 223 [2025-02-05 16:04:23,260 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 39 SyntacticMatches, 14 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 755 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=235, Invalid=2117, Unknown=0, NotChecked=0, Total=2352 [2025-02-05 16:04:23,260 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 90 mSDsluCounter, 387 mSDsCounter, 0 mSdLazyCounter, 1127 mSolverCounterSat, 35 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 431 SdHoareTripleChecker+Invalid, 1163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 1127 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.7s IncrementalHoareTripleChecker+Time [2025-02-05 16:04:23,260 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 431 Invalid, 1163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 1127 Invalid, 1 Unknown, 0 Unchecked, 5.7s Time] [2025-02-05 16:04:23,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2025-02-05 16:04:23,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 218. [2025-02-05 16:04:23,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 139 states have (on average 1.0719424460431655) internal successors, (149), 145 states have internal predecessors, (149), 45 states have call successors, (45), 28 states have call predecessors, (45), 33 states have return successors, (59), 44 states have call predecessors, (59), 44 states have call successors, (59) [2025-02-05 16:04:23,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 253 transitions. [2025-02-05 16:04:23,303 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 253 transitions. Word has length 78 [2025-02-05 16:04:23,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 16:04:23,304 INFO L471 AbstractCegarLoop]: Abstraction has 218 states and 253 transitions. [2025-02-05 16:04:23,304 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 26 states have (on average 1.6153846153846154) internal successors, (42), 21 states have internal predecessors, (42), 8 states have call successors, (14), 9 states have call predecessors, (14), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2025-02-05 16:04:23,304 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 253 transitions. [2025-02-05 16:04:23,304 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2025-02-05 16:04:23,304 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 16:04:23,304 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 16:04:23,312 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-02-05 16:04:23,506 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:04:23,506 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 16:04:23,506 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 16:04:23,509 INFO L85 PathProgramCache]: Analyzing trace with hash 474806873, now seen corresponding path program 2 times [2025-02-05 16:04:23,509 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 16:04:23,510 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [136135805] [2025-02-05 16:04:23,510 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 16:04:23,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 16:04:23,527 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 84 statements into 2 equivalence classes. [2025-02-05 16:04:23,561 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 84 of 84 statements. [2025-02-05 16:04:23,561 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 16:04:23,561 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 16:04:23,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1559869536] [2025-02-05 16:04:23,563 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 16:04:23,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 16:04:23,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 16:04:23,567 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 16:04:23,569 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-02-05 16:04:23,686 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 84 statements into 2 equivalence classes. [2025-02-05 16:04:23,835 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 84 of 84 statements. [2025-02-05 16:04:23,835 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 16:04:23,835 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 16:04:23,840 INFO L256 TraceCheckSpWp]: Trace formula consists of 858 conjuncts, 273 conjuncts are in the unsatisfiable core [2025-02-05 16:04:23,847 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 16:04:23,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:04:23,869 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:04:24,019 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:24,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:04:24,034 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:24,046 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-02-05 16:04:24,548 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-02-05 16:04:24,552 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-02-05 16:04:24,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 11 treesize of output 7 [2025-02-05 16:04:24,614 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:25,295 INFO L349 Elim1Store]: treesize reduction 16, result has 55.6 percent of original size [2025-02-05 16:04:25,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 59 treesize of output 58 [2025-02-05 16:04:25,299 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 32 treesize of output 20 [2025-02-05 16:04:25,347 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:25,359 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-02-05 16:04:26,857 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:26,857 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 25 [2025-02-05 16:04:26,867 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:26,867 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 80 treesize of output 60 [2025-02-05 16:04:26,880 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-02-05 16:04:26,881 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 57 [2025-02-05 16:04:26,962 INFO L134 CoverageAnalysis]: Checked inductivity of 107 backedges. 14 proven. 64 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-02-05 16:04:26,962 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 16:04:27,094 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 16:04:27,094 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [136135805] [2025-02-05 16:04:27,094 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 16:04:27,094 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1559869536] [2025-02-05 16:04:27,094 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1559869536] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 16:04:27,095 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-02-05 16:04:27,095 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30] total 30 [2025-02-05 16:04:27,095 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325945837] [2025-02-05 16:04:27,095 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-02-05 16:04:27,095 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-02-05 16:04:27,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 16:04:27,095 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-02-05 16:04:27,096 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=1006, Unknown=0, NotChecked=0, Total=1122 [2025-02-05 16:04:27,096 INFO L87 Difference]: Start difference. First operand 218 states and 253 transitions. Second operand has 30 states, 27 states have (on average 1.7037037037037037) internal successors, (46), 24 states have internal predecessors, (46), 9 states have call successors, (15), 10 states have call predecessors, (15), 7 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11)