./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! overflow) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4a9aad6636e75eb788a44e63e1649ee5df89ecae877c31a886978a8e3fdd2e8f --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-17 04:59:36,588 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-17 04:59:36,691 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2024-11-17 04:59:36,697 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-17 04:59:36,699 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-17 04:59:36,728 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-17 04:59:36,729 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-17 04:59:36,729 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-17 04:59:36,730 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-17 04:59:36,731 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-17 04:59:36,731 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-17 04:59:36,732 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-17 04:59:36,732 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-17 04:59:36,734 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-17 04:59:36,734 INFO L153 SettingsManager]: * Use SBE=true [2024-11-17 04:59:36,735 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-17 04:59:36,735 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-17 04:59:36,735 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-17 04:59:36,736 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-17 04:59:36,736 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-17 04:59:36,740 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-17 04:59:36,740 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-17 04:59:36,741 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-17 04:59:36,741 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-17 04:59:36,741 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-17 04:59:36,741 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2024-11-17 04:59:36,742 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-17 04:59:36,742 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-17 04:59:36,742 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-17 04:59:36,742 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-17 04:59:36,743 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-17 04:59:36,743 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-17 04:59:36,743 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-17 04:59:36,743 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-17 04:59:36,744 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-17 04:59:36,744 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-17 04:59:36,744 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-17 04:59:36,745 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-17 04:59:36,745 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-17 04:59:36,745 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-17 04:59:36,745 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-17 04:59:36,746 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-17 04:59:36,746 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-17 04:59:36,746 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-17 04:59:36,747 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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/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 ! overflow) ) 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 -> 4a9aad6636e75eb788a44e63e1649ee5df89ecae877c31a886978a8e3fdd2e8f [2024-11-17 04:59:36,991 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-17 04:59:37,010 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-17 04:59:37,013 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-17 04:59:37,014 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-17 04:59:37,015 INFO L274 PluginConnector]: CDTParser initialized [2024-11-17 04:59:37,016 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c [2024-11-17 04:59:38,508 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-17 04:59:38,725 INFO L384 CDTParser]: Found 1 translation units. [2024-11-17 04:59:38,729 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra.c [2024-11-17 04:59:38,745 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2b1869489/67ca761ef64645998d710e5f02acb165/FLAGf1ee7c06b [2024-11-17 04:59:38,762 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2b1869489/67ca761ef64645998d710e5f02acb165 [2024-11-17 04:59:38,766 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-17 04:59:38,768 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-17 04:59:38,770 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-17 04:59:38,771 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-17 04:59:38,776 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-17 04:59:38,777 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 04:59:38" (1/1) ... [2024-11-17 04:59:38,778 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4af0a366 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:38, skipping insertion in model container [2024-11-17 04:59:38,778 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 04:59:38" (1/1) ... [2024-11-17 04:59:38,804 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-17 04:59:39,010 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 04:59:39,023 INFO L200 MainTranslator]: Completed pre-run [2024-11-17 04:59:39,067 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 04:59:39,089 INFO L204 MainTranslator]: Completed translation [2024-11-17 04:59:39,091 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39 WrapperNode [2024-11-17 04:59:39,094 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-17 04:59:39,097 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-17 04:59:39,098 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-17 04:59:39,098 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-17 04:59:39,105 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,118 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,150 INFO L138 Inliner]: procedures = 17, calls = 172, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 185 [2024-11-17 04:59:39,151 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-17 04:59:39,151 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-17 04:59:39,151 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-17 04:59:39,152 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-17 04:59:39,164 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,164 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,174 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,199 INFO L175 MemorySlicer]: Split 138 memory accesses to 6 slices as follows [2, 20, 35, 29, 22, 30]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 1, 3, 3, 2, 2]. [2024-11-17 04:59:39,199 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,200 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,217 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,218 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,221 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,224 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,231 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-17 04:59:39,235 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-17 04:59:39,235 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-17 04:59:39,236 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-17 04:59:39,236 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (1/1) ... [2024-11-17 04:59:39,243 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-17 04:59:39,255 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:39,271 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-17 04:59:39,274 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-17 04:59:39,314 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-17 04:59:39,314 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_28_to_32_0 [2024-11-17 04:59:39,314 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_28_to_32_0 [2024-11-17 04:59:39,314 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-17 04:59:39,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-17 04:59:39,316 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-17 04:59:39,316 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-17 04:59:39,316 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-17 04:59:39,316 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-17 04:59:39,316 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-17 04:59:39,316 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-17 04:59:39,316 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-17 04:59:39,322 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-17 04:59:39,322 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-17 04:59:39,322 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-17 04:59:39,322 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-17 04:59:39,323 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-17 04:59:39,323 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-17 04:59:39,323 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-17 04:59:39,323 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_36_to_52_0 [2024-11-17 04:59:39,323 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_36_to_52_0 [2024-11-17 04:59:39,323 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-17 04:59:39,446 INFO L256 CfgBuilder]: Building ICFG [2024-11-17 04:59:39,449 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-17 04:59:42,402 INFO L1250 $ProcedureCfgBuilder]: dead code at ProgramPoint L108: call ULTIMATE.dealloc(main_~#n~0#1.base, main_~#n~0#1.offset);havoc main_~#n~0#1.base, main_~#n~0#1.offset;call ULTIMATE.dealloc(main_~#p~0#1.base, main_~#p~0#1.offset);havoc main_~#p~0#1.base, main_~#p~0#1.offset;call ULTIMATE.dealloc(main_~#q~0#1.base, main_~#q~0#1.offset);havoc main_~#q~0#1.base, main_~#q~0#1.offset;call ULTIMATE.dealloc(main_~#r~0#1.base, main_~#r~0#1.offset);havoc main_~#r~0#1.base, main_~#r~0#1.offset;call ULTIMATE.dealloc(main_~#h~0#1.base, main_~#h~0#1.offset);havoc main_~#h~0#1.base, main_~#h~0#1.offset; [2024-11-17 04:59:42,474 INFO L? ?]: Removed 1170 outVars from TransFormulas that were not future-live. [2024-11-17 04:59:42,475 INFO L307 CfgBuilder]: Performing block encoding [2024-11-17 04:59:42,506 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-17 04:59:42,507 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-17 04:59:42,507 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 04:59:42 BoogieIcfgContainer [2024-11-17 04:59:42,507 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-17 04:59:42,510 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-17 04:59:42,510 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-17 04:59:42,513 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-17 04:59:42,513 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.11 04:59:38" (1/3) ... [2024-11-17 04:59:42,514 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6f63229f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.11 04:59:42, skipping insertion in model container [2024-11-17 04:59:42,514 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 04:59:39" (2/3) ... [2024-11-17 04:59:42,515 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6f63229f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.11 04:59:42, skipping insertion in model container [2024-11-17 04:59:42,515 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 04:59:42" (3/3) ... [2024-11-17 04:59:42,516 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra.c [2024-11-17 04:59:42,532 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-17 04:59:42,532 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 258 error locations. [2024-11-17 04:59:42,611 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-17 04:59:42,621 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;@578e1200, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-17 04:59:42,621 INFO L334 AbstractCegarLoop]: Starting to check reachability of 258 error locations. [2024-11-17 04:59:42,627 INFO L276 IsEmpty]: Start isEmpty. Operand has 649 states, 374 states have (on average 1.7058823529411764) internal successors, (638), 634 states have internal predecessors, (638), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-17 04:59:42,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-17 04:59:42,634 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:42,635 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:42,636 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting func_to_recursive_line_28_to_32_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:42,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:42,641 INFO L85 PathProgramCache]: Analyzing trace with hash -72649949, now seen corresponding path program 1 times [2024-11-17 04:59:42,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:42,651 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1761782184] [2024-11-17 04:59:42,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:42,652 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:42,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:43,161 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:43,162 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:43,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1761782184] [2024-11-17 04:59:43,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1761782184] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 04:59:43,163 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 04:59:43,163 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-17 04:59:43,164 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1595347309] [2024-11-17 04:59:43,165 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 04:59:43,169 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-17 04:59:43,171 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:43,197 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-17 04:59:43,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-17 04:59:43,201 INFO L87 Difference]: Start difference. First operand has 649 states, 374 states have (on average 1.7058823529411764) internal successors, (638), 634 states have internal predecessors, (638), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 04:59:43,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:43,489 INFO L93 Difference]: Finished difference Result 1296 states and 1339 transitions. [2024-11-17 04:59:43,490 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-17 04:59:43,492 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-17 04:59:43,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:43,503 INFO L225 Difference]: With dead ends: 1296 [2024-11-17 04:59:43,503 INFO L226 Difference]: Without dead ends: 651 [2024-11-17 04:59:43,535 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2024-11-17 04:59:43,540 INFO L432 NwaCegarLoop]: 653 mSDtfsCounter, 14 mSDsluCounter, 2514 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 3167 SdHoareTripleChecker+Invalid, 133 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:43,541 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 3167 Invalid, 133 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-17 04:59:43,560 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 651 states. [2024-11-17 04:59:43,639 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 651 to 649. [2024-11-17 04:59:43,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 649 states, 375 states have (on average 1.696) internal successors, (636), 634 states have internal predecessors, (636), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2024-11-17 04:59:43,645 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 649 states to 649 states and 661 transitions. [2024-11-17 04:59:43,647 INFO L78 Accepts]: Start accepts. Automaton has 649 states and 661 transitions. Word has length 7 [2024-11-17 04:59:43,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:43,647 INFO L471 AbstractCegarLoop]: Abstraction has 649 states and 661 transitions. [2024-11-17 04:59:43,647 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 04:59:43,647 INFO L276 IsEmpty]: Start isEmpty. Operand 649 states and 661 transitions. [2024-11-17 04:59:43,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-17 04:59:43,648 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:43,648 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:43,648 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-17 04:59:43,648 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting func_to_recursive_line_36_to_52_0Err185ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:43,649 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:43,649 INFO L85 PathProgramCache]: Analyzing trace with hash -622949570, now seen corresponding path program 1 times [2024-11-17 04:59:43,649 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:43,649 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1804263049] [2024-11-17 04:59:43,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:43,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:43,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:43,860 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-17 04:59:43,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:43,869 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:43,870 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:43,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1804263049] [2024-11-17 04:59:43,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1804263049] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 04:59:43,871 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 04:59:43,871 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-17 04:59:43,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070132912] [2024-11-17 04:59:43,871 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 04:59:43,872 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-17 04:59:43,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:43,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-17 04:59:43,875 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-17 04:59:43,875 INFO L87 Difference]: Start difference. First operand 649 states and 661 transitions. Second operand has 7 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-17 04:59:44,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:44,426 INFO L93 Difference]: Finished difference Result 1260 states and 1281 transitions. [2024-11-17 04:59:44,426 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-17 04:59:44,426 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-17 04:59:44,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:44,432 INFO L225 Difference]: With dead ends: 1260 [2024-11-17 04:59:44,433 INFO L226 Difference]: Without dead ends: 1258 [2024-11-17 04:59:44,434 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-11-17 04:59:44,437 INFO L432 NwaCegarLoop]: 584 mSDtfsCounter, 1895 mSDsluCounter, 2474 mSDsCounter, 0 mSdLazyCounter, 403 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1903 SdHoareTripleChecker+Valid, 3058 SdHoareTripleChecker+Invalid, 443 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 403 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:44,439 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1903 Valid, 3058 Invalid, 443 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 403 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-17 04:59:44,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1258 states. [2024-11-17 04:59:44,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1258 to 905. [2024-11-17 04:59:44,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 905 states, 622 states have (on average 1.7009646302250805) internal successors, (1058), 881 states have internal predecessors, (1058), 18 states have call successors, (18), 5 states have call predecessors, (18), 7 states have return successors, (22), 18 states have call predecessors, (22), 18 states have call successors, (22) [2024-11-17 04:59:44,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 905 states to 905 states and 1098 transitions. [2024-11-17 04:59:44,496 INFO L78 Accepts]: Start accepts. Automaton has 905 states and 1098 transitions. Word has length 12 [2024-11-17 04:59:44,496 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:44,497 INFO L471 AbstractCegarLoop]: Abstraction has 905 states and 1098 transitions. [2024-11-17 04:59:44,497 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-17 04:59:44,498 INFO L276 IsEmpty]: Start isEmpty. Operand 905 states and 1098 transitions. [2024-11-17 04:59:44,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-17 04:59:44,498 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:44,498 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:44,498 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-17 04:59:44,499 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting func_to_recursive_line_28_to_32_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:44,499 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:44,499 INFO L85 PathProgramCache]: Analyzing trace with hash 174056792, now seen corresponding path program 1 times [2024-11-17 04:59:44,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:44,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [975433293] [2024-11-17 04:59:44,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:44,500 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:44,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:44,819 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:44,820 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:44,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [975433293] [2024-11-17 04:59:44,821 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [975433293] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 04:59:44,821 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [219773763] [2024-11-17 04:59:44,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:44,822 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:44,822 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:44,824 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 04:59:44,825 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-17 04:59:44,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:44,925 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-17 04:59:44,930 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 04:59:44,974 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 04:59:45,029 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 21 treesize of output 13 [2024-11-17 04:59:45,106 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2024-11-17 04:59:45,122 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:45,122 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 04:59:45,258 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:45,258 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [219773763] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 04:59:45,259 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 04:59:45,259 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 19 [2024-11-17 04:59:45,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1640526449] [2024-11-17 04:59:45,259 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 04:59:45,260 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-17 04:59:45,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:45,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-17 04:59:45,261 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2024-11-17 04:59:45,261 INFO L87 Difference]: Start difference. First operand 905 states and 1098 transitions. Second operand has 20 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 15 states have internal predecessors, (30), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 04:59:45,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:45,729 INFO L93 Difference]: Finished difference Result 910 states and 1109 transitions. [2024-11-17 04:59:45,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-17 04:59:45,729 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 15 states have internal predecessors, (30), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2024-11-17 04:59:45,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:45,734 INFO L225 Difference]: With dead ends: 910 [2024-11-17 04:59:45,735 INFO L226 Difference]: Without dead ends: 909 [2024-11-17 04:59:45,736 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=135, Invalid=515, Unknown=0, NotChecked=0, Total=650 [2024-11-17 04:59:45,738 INFO L432 NwaCegarLoop]: 646 mSDtfsCounter, 35 mSDsluCounter, 7421 mSDsCounter, 0 mSdLazyCounter, 453 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 8067 SdHoareTripleChecker+Invalid, 461 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 453 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:45,739 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 8067 Invalid, 461 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 453 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-17 04:59:45,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 909 states. [2024-11-17 04:59:45,765 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 909 to 904. [2024-11-17 04:59:45,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 904 states, 622 states have (on average 1.6993569131832797) internal successors, (1057), 880 states have internal predecessors, (1057), 18 states have call successors, (18), 5 states have call predecessors, (18), 7 states have return successors, (22), 18 states have call predecessors, (22), 18 states have call successors, (22) [2024-11-17 04:59:45,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 904 states to 904 states and 1097 transitions. [2024-11-17 04:59:45,771 INFO L78 Accepts]: Start accepts. Automaton has 904 states and 1097 transitions. Word has length 14 [2024-11-17 04:59:45,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:45,772 INFO L471 AbstractCegarLoop]: Abstraction has 904 states and 1097 transitions. [2024-11-17 04:59:45,772 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 15 states have internal predecessors, (30), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 04:59:45,772 INFO L276 IsEmpty]: Start isEmpty. Operand 904 states and 1097 transitions. [2024-11-17 04:59:45,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-17 04:59:45,773 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:45,773 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:45,791 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-17 04:59:45,977 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:45,978 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting func_to_recursive_line_36_to_52_0Err183ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:45,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:45,978 INFO L85 PathProgramCache]: Analyzing trace with hash 263464165, now seen corresponding path program 1 times [2024-11-17 04:59:45,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:45,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1336749971] [2024-11-17 04:59:45,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:45,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:46,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:46,286 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-17 04:59:46,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:46,297 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:46,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:46,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1336749971] [2024-11-17 04:59:46,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1336749971] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 04:59:46,298 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 04:59:46,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-17 04:59:46,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [582029045] [2024-11-17 04:59:46,299 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 04:59:46,299 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-17 04:59:46,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:46,300 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-17 04:59:46,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-11-17 04:59:46,300 INFO L87 Difference]: Start difference. First operand 904 states and 1097 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 7 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-17 04:59:46,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:46,894 INFO L93 Difference]: Finished difference Result 1500 states and 1703 transitions. [2024-11-17 04:59:46,895 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-17 04:59:46,895 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 7 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-17 04:59:46,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:46,902 INFO L225 Difference]: With dead ends: 1500 [2024-11-17 04:59:46,903 INFO L226 Difference]: Without dead ends: 1498 [2024-11-17 04:59:46,904 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2024-11-17 04:59:46,905 INFO L432 NwaCegarLoop]: 584 mSDtfsCounter, 1864 mSDsluCounter, 3035 mSDsCounter, 0 mSdLazyCounter, 492 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1872 SdHoareTripleChecker+Valid, 3619 SdHoareTripleChecker+Invalid, 534 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 492 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:46,907 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1872 Valid, 3619 Invalid, 534 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 492 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-17 04:59:46,910 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1498 states. [2024-11-17 04:59:46,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1498 to 1157. [2024-11-17 04:59:46,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1157 states, 867 states have (on average 1.701268742791234) internal successors, (1475), 1125 states have internal predecessors, (1475), 25 states have call successors, (25), 6 states have call predecessors, (25), 8 states have return successors, (30), 25 states have call predecessors, (30), 25 states have call successors, (30) [2024-11-17 04:59:46,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1530 transitions. [2024-11-17 04:59:46,946 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1530 transitions. Word has length 15 [2024-11-17 04:59:46,946 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:46,947 INFO L471 AbstractCegarLoop]: Abstraction has 1157 states and 1530 transitions. [2024-11-17 04:59:46,947 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 7 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-17 04:59:46,947 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1530 transitions. [2024-11-17 04:59:46,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-17 04:59:46,948 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:46,948 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:46,948 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-17 04:59:46,948 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting func_to_recursive_line_28_to_32_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:46,948 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:46,949 INFO L85 PathProgramCache]: Analyzing trace with hash 1100793687, now seen corresponding path program 1 times [2024-11-17 04:59:46,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:46,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [869869796] [2024-11-17 04:59:46,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:46,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:46,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:47,234 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:47,235 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:47,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [869869796] [2024-11-17 04:59:47,235 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [869869796] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 04:59:47,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998627980] [2024-11-17 04:59:47,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:47,236 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:47,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:47,238 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 04:59:47,239 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-17 04:59:47,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:47,334 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-17 04:59:47,337 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 04:59:47,343 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 [2024-11-17 04:59:47,394 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 21 treesize of output 13 [2024-11-17 04:59:47,472 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2024-11-17 04:59:47,483 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:47,483 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 04:59:47,600 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:47,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998627980] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 04:59:47,601 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 04:59:47,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 19 [2024-11-17 04:59:47,601 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [422725233] [2024-11-17 04:59:47,602 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 04:59:47,602 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-17 04:59:47,602 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:47,603 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-17 04:59:47,603 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=308, Unknown=0, NotChecked=0, Total=380 [2024-11-17 04:59:47,603 INFO L87 Difference]: Start difference. First operand 1157 states and 1530 transitions. Second operand has 20 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 15 states have internal predecessors, (32), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 04:59:48,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:48,120 INFO L93 Difference]: Finished difference Result 1192 states and 1573 transitions. [2024-11-17 04:59:48,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-17 04:59:48,120 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 15 states have internal predecessors, (32), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-17 04:59:48,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:48,128 INFO L225 Difference]: With dead ends: 1192 [2024-11-17 04:59:48,128 INFO L226 Difference]: Without dead ends: 1191 [2024-11-17 04:59:48,129 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 183 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=204, Invalid=726, Unknown=0, NotChecked=0, Total=930 [2024-11-17 04:59:48,130 INFO L432 NwaCegarLoop]: 645 mSDtfsCounter, 71 mSDsluCounter, 5574 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 6219 SdHoareTripleChecker+Invalid, 424 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:48,130 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 6219 Invalid, 424 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-17 04:59:48,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1191 states. [2024-11-17 04:59:48,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1191 to 1190. [2024-11-17 04:59:48,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1190 states, 891 states have (on average 1.6857463524130192) internal successors, (1502), 1152 states have internal predecessors, (1502), 28 states have call successors, (28), 9 states have call predecessors, (28), 14 states have return successors, (39), 28 states have call predecessors, (39), 28 states have call successors, (39) [2024-11-17 04:59:48,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1190 states to 1190 states and 1569 transitions. [2024-11-17 04:59:48,170 INFO L78 Accepts]: Start accepts. Automaton has 1190 states and 1569 transitions. Word has length 15 [2024-11-17 04:59:48,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:48,170 INFO L471 AbstractCegarLoop]: Abstraction has 1190 states and 1569 transitions. [2024-11-17 04:59:48,171 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 15 states have internal predecessors, (32), 5 states have call successors, (5), 5 states have call predecessors, (5), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 04:59:48,171 INFO L276 IsEmpty]: Start isEmpty. Operand 1190 states and 1569 transitions. [2024-11-17 04:59:48,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-17 04:59:48,172 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:48,172 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:48,190 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-17 04:59:48,376 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:48,377 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting func_to_recursive_line_36_to_52_0Err181ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:48,377 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:48,377 INFO L85 PathProgramCache]: Analyzing trace with hash -2094887249, now seen corresponding path program 1 times [2024-11-17 04:59:48,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:48,377 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [690351409] [2024-11-17 04:59:48,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:48,378 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:48,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 04:59:48,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1098462757] [2024-11-17 04:59:48,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:48,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:48,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:48,405 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 04:59:48,406 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-17 04:59:48,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:48,504 INFO L255 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-17 04:59:48,506 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 04:59:48,511 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 [2024-11-17 04:59:48,608 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:48,608 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 04:59:48,608 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:48,608 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [690351409] [2024-11-17 04:59:48,609 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 04:59:48,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1098462757] [2024-11-17 04:59:48,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1098462757] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 04:59:48,609 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 04:59:48,609 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-17 04:59:48,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1238903254] [2024-11-17 04:59:48,610 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 04:59:48,610 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-17 04:59:48,610 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:48,610 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-17 04:59:48,611 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-17 04:59:48,611 INFO L87 Difference]: Start difference. First operand 1190 states and 1569 transitions. Second operand has 7 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 04:59:48,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:48,957 INFO L93 Difference]: Finished difference Result 1551 states and 1756 transitions. [2024-11-17 04:59:48,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-17 04:59:48,958 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2024-11-17 04:59:48,958 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:48,964 INFO L225 Difference]: With dead ends: 1551 [2024-11-17 04:59:48,964 INFO L226 Difference]: Without dead ends: 1549 [2024-11-17 04:59:48,965 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 14 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2024-11-17 04:59:48,966 INFO L432 NwaCegarLoop]: 612 mSDtfsCounter, 1636 mSDsluCounter, 1986 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1638 SdHoareTripleChecker+Valid, 2598 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:48,966 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1638 Valid, 2598 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 196 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-17 04:59:48,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1549 states. [2024-11-17 04:59:48,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1549 to 1251. [2024-11-17 04:59:48,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1251 states, 949 states have (on average 1.6817702845100104) internal successors, (1596), 1210 states have internal predecessors, (1596), 30 states have call successors, (30), 10 states have call predecessors, (30), 15 states have return successors, (41), 30 states have call predecessors, (41), 30 states have call successors, (41) [2024-11-17 04:59:49,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1251 states to 1251 states and 1667 transitions. [2024-11-17 04:59:49,003 INFO L78 Accepts]: Start accepts. Automaton has 1251 states and 1667 transitions. Word has length 23 [2024-11-17 04:59:49,003 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:49,003 INFO L471 AbstractCegarLoop]: Abstraction has 1251 states and 1667 transitions. [2024-11-17 04:59:49,004 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 3.6) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 04:59:49,004 INFO L276 IsEmpty]: Start isEmpty. Operand 1251 states and 1667 transitions. [2024-11-17 04:59:49,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-17 04:59:49,005 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:49,005 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:49,022 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-17 04:59:49,205 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:49,206 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting func_to_recursive_line_36_to_52_0Err183ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:49,206 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:49,206 INFO L85 PathProgramCache]: Analyzing trace with hash 186313938, now seen corresponding path program 1 times [2024-11-17 04:59:49,207 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:49,207 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1501717481] [2024-11-17 04:59:49,207 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:49,207 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:49,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:49,465 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-17 04:59:49,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:49,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-17 04:59:49,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:49,781 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 04:59:49,781 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:49,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1501717481] [2024-11-17 04:59:49,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1501717481] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 04:59:49,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1988668073] [2024-11-17 04:59:49,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:49,782 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:49,782 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:49,784 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 04:59:49,786 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-17 04:59:49,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:49,887 INFO L255 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-17 04:59:49,890 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 04:59:49,895 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 [2024-11-17 04:59:49,900 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 [2024-11-17 04:59:50,178 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_14| Int)) (let ((.cse0 (select |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (= (store |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_14| 4))) |c_#memory_int#2|) (<= (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|) |v_func_to_recursive_line_28_to_32_0_#t~mem98_14|)))) (exists ((|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_3| Int) (|v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_3| Int)) (= (select (select |c_#memory_int#3| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_3|) |v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_3|) 0))) is different from true [2024-11-17 04:59:50,227 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 21 treesize of output 13 [2024-11-17 04:59:50,457 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 [2024-11-17 04:59:50,487 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 2 not checked. [2024-11-17 04:59:50,488 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 04:59:50,900 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1988668073] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 04:59:50,901 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-17 04:59:50,901 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 25 [2024-11-17 04:59:50,901 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [329942988] [2024-11-17 04:59:50,901 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-17 04:59:50,902 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-17 04:59:50,902 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:50,903 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-17 04:59:50,903 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=900, Unknown=1, NotChecked=60, Total=1056 [2024-11-17 04:59:50,904 INFO L87 Difference]: Start difference. First operand 1251 states and 1667 transitions. Second operand has 26 states, 19 states have (on average 1.894736842105263) internal successors, (36), 22 states have internal predecessors, (36), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-17 04:59:54,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:54,967 INFO L93 Difference]: Finished difference Result 2793 states and 3064 transitions. [2024-11-17 04:59:54,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-17 04:59:54,967 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 19 states have (on average 1.894736842105263) internal successors, (36), 22 states have internal predecessors, (36), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 24 [2024-11-17 04:59:54,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:54,979 INFO L225 Difference]: With dead ends: 2793 [2024-11-17 04:59:54,979 INFO L226 Difference]: Without dead ends: 2792 [2024-11-17 04:59:54,982 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 44 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 354 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=237, Invalid=1746, Unknown=1, NotChecked=86, Total=2070 [2024-11-17 04:59:54,983 INFO L432 NwaCegarLoop]: 1692 mSDtfsCounter, 3472 mSDsluCounter, 28417 mSDsCounter, 0 mSdLazyCounter, 3636 mSolverCounterSat, 77 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3490 SdHoareTripleChecker+Valid, 30109 SdHoareTripleChecker+Invalid, 6200 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 3636 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 2487 IncrementalHoareTripleChecker+Unchecked, 3.3s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:54,983 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3490 Valid, 30109 Invalid, 6200 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [77 Valid, 3636 Invalid, 0 Unknown, 2487 Unchecked, 3.3s Time] [2024-11-17 04:59:54,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2792 states. [2024-11-17 04:59:55,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2792 to 1822. [2024-11-17 04:59:55,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1822 states, 1499 states have (on average 1.6877918612408271) internal successors, (2530), 1760 states have internal predecessors, (2530), 46 states have call successors, (46), 13 states have call predecessors, (46), 20 states have return successors, (66), 48 states have call predecessors, (66), 46 states have call successors, (66) [2024-11-17 04:59:55,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1822 states to 1822 states and 2642 transitions. [2024-11-17 04:59:55,045 INFO L78 Accepts]: Start accepts. Automaton has 1822 states and 2642 transitions. Word has length 24 [2024-11-17 04:59:55,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:55,045 INFO L471 AbstractCegarLoop]: Abstraction has 1822 states and 2642 transitions. [2024-11-17 04:59:55,045 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 19 states have (on average 1.894736842105263) internal successors, (36), 22 states have internal predecessors, (36), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-17 04:59:55,046 INFO L276 IsEmpty]: Start isEmpty. Operand 1822 states and 2642 transitions. [2024-11-17 04:59:55,047 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-17 04:59:55,048 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:55,048 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 04:59:55,067 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-17 04:59:55,249 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:55,249 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting func_to_recursive_line_36_to_52_0Err182ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:55,249 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:55,249 INFO L85 PathProgramCache]: Analyzing trace with hash 1480765198, now seen corresponding path program 1 times [2024-11-17 04:59:55,250 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:55,250 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1792514800] [2024-11-17 04:59:55,250 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:55,250 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:55,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:55,566 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-17 04:59:55,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:55,791 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-17 04:59:55,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:55,848 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 04:59:55,848 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:55,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1792514800] [2024-11-17 04:59:55,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1792514800] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 04:59:55,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1115503913] [2024-11-17 04:59:55,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:55,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:55,849 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:55,851 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 04:59:55,852 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-17 04:59:55,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:55,958 INFO L255 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-17 04:59:55,960 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 04:59:55,967 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 [2024-11-17 04:59:55,972 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 [2024-11-17 04:59:56,190 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_21| Int)) (let ((.cse0 (select |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (<= |v_func_to_recursive_line_28_to_32_0_#t~mem98_21| (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|)) (= (store |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_21| 4))) |c_#memory_int#2|)))) (exists ((|v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_6| Int) (|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_6| Int)) (= (select (select |c_#memory_int#3| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_6|) |v_ULTIMATE.start_main_~#p~0#1.offset_BEFORE_CALL_6|) 0))) is different from true [2024-11-17 04:59:56,208 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 21 treesize of output 13 [2024-11-17 04:59:56,450 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 [2024-11-17 04:59:56,484 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 2 not checked. [2024-11-17 04:59:56,484 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 04:59:56,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1115503913] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 04:59:56,866 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-17 04:59:56,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 24 [2024-11-17 04:59:56,866 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1772996541] [2024-11-17 04:59:56,866 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-17 04:59:56,867 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-17 04:59:56,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:56,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-17 04:59:56,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=827, Unknown=1, NotChecked=58, Total=992 [2024-11-17 04:59:56,868 INFO L87 Difference]: Start difference. First operand 1822 states and 2642 transitions. Second operand has 25 states, 19 states have (on average 1.9473684210526316) internal successors, (37), 21 states have internal predecessors, (37), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 04:59:59,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 04:59:59,072 INFO L93 Difference]: Finished difference Result 2472 states and 2915 transitions. [2024-11-17 04:59:59,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-17 04:59:59,072 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 19 states have (on average 1.9473684210526316) internal successors, (37), 21 states have internal predecessors, (37), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 25 [2024-11-17 04:59:59,073 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 04:59:59,084 INFO L225 Difference]: With dead ends: 2472 [2024-11-17 04:59:59,084 INFO L226 Difference]: Without dead ends: 2471 [2024-11-17 04:59:59,085 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 40 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 285 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=239, Invalid=1404, Unknown=1, NotChecked=78, Total=1722 [2024-11-17 04:59:59,087 INFO L432 NwaCegarLoop]: 1142 mSDtfsCounter, 4065 mSDsluCounter, 13007 mSDsCounter, 0 mSdLazyCounter, 2038 mSolverCounterSat, 100 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4075 SdHoareTripleChecker+Valid, 14149 SdHoareTripleChecker+Invalid, 4031 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 100 IncrementalHoareTripleChecker+Valid, 2038 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1893 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-11-17 04:59:59,087 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4075 Valid, 14149 Invalid, 4031 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [100 Valid, 2038 Invalid, 0 Unknown, 1893 Unchecked, 1.7s Time] [2024-11-17 04:59:59,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2471 states. [2024-11-17 04:59:59,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2471 to 1902. [2024-11-17 04:59:59,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1902 states, 1574 states have (on average 1.6867852604828462) internal successors, (2655), 1836 states have internal predecessors, (2655), 49 states have call successors, (49), 14 states have call predecessors, (49), 22 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 04:59:59,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1902 states to 1902 states and 2775 transitions. [2024-11-17 04:59:59,150 INFO L78 Accepts]: Start accepts. Automaton has 1902 states and 2775 transitions. Word has length 25 [2024-11-17 04:59:59,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 04:59:59,152 INFO L471 AbstractCegarLoop]: Abstraction has 1902 states and 2775 transitions. [2024-11-17 04:59:59,152 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 19 states have (on average 1.9473684210526316) internal successors, (37), 21 states have internal predecessors, (37), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 04:59:59,152 INFO L276 IsEmpty]: Start isEmpty. Operand 1902 states and 2775 transitions. [2024-11-17 04:59:59,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-17 04:59:59,154 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 04:59:59,154 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-17 04:59:59,172 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-17 04:59:59,355 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:59,355 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting func_to_recursive_line_36_to_52_0Err179ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 04:59:59,355 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 04:59:59,356 INFO L85 PathProgramCache]: Analyzing trace with hash 1384150313, now seen corresponding path program 1 times [2024-11-17 04:59:59,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 04:59:59,356 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1550717078] [2024-11-17 04:59:59,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:59,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 04:59:59,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 04:59:59,378 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1956868595] [2024-11-17 04:59:59,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 04:59:59,378 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 04:59:59,378 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 04:59:59,380 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 04:59:59,390 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-17 04:59:59,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 04:59:59,489 INFO L255 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 40 conjuncts are in the unsatisfiable core [2024-11-17 04:59:59,492 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 04:59:59,505 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 [2024-11-17 04:59:59,509 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 [2024-11-17 04:59:59,663 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 [2024-11-17 04:59:59,677 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 04:59:59,677 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 04:59:59,677 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 04:59:59,677 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1550717078] [2024-11-17 04:59:59,677 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 04:59:59,678 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1956868595] [2024-11-17 04:59:59,678 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1956868595] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 04:59:59,678 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 04:59:59,678 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-17 04:59:59,678 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2080545025] [2024-11-17 04:59:59,678 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 04:59:59,679 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-17 04:59:59,679 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 04:59:59,679 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-17 04:59:59,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-17 04:59:59,680 INFO L87 Difference]: Start difference. First operand 1902 states and 2775 transitions. Second operand has 8 states, 6 states have (on average 3.5) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:00,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:00,215 INFO L93 Difference]: Finished difference Result 2192 states and 2853 transitions. [2024-11-17 05:00:00,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-17 05:00:00,217 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 3.5) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2024-11-17 05:00:00,218 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:00,225 INFO L225 Difference]: With dead ends: 2192 [2024-11-17 05:00:00,226 INFO L226 Difference]: Without dead ends: 2191 [2024-11-17 05:00:00,226 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 17 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=88, Unknown=0, NotChecked=0, Total=132 [2024-11-17 05:00:00,227 INFO L432 NwaCegarLoop]: 584 mSDtfsCounter, 1995 mSDsluCounter, 2484 mSDsCounter, 0 mSdLazyCounter, 375 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1997 SdHoareTripleChecker+Valid, 3068 SdHoareTripleChecker+Invalid, 419 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 375 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:00,227 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1997 Valid, 3068 Invalid, 419 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 375 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-17 05:00:00,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2191 states. [2024-11-17 05:00:00,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2191 to 1906. [2024-11-17 05:00:00,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1906 states, 1577 states have (on average 1.684844641724794) internal successors, (2657), 1839 states have internal predecessors, (2657), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 05:00:00,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1906 states to 1906 states and 2777 transitions. [2024-11-17 05:00:00,279 INFO L78 Accepts]: Start accepts. Automaton has 1906 states and 2777 transitions. Word has length 26 [2024-11-17 05:00:00,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:00,280 INFO L471 AbstractCegarLoop]: Abstraction has 1906 states and 2777 transitions. [2024-11-17 05:00:00,280 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 3.5) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:00,280 INFO L276 IsEmpty]: Start isEmpty. Operand 1906 states and 2777 transitions. [2024-11-17 05:00:00,281 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-17 05:00:00,281 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:00,281 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-17 05:00:00,298 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-17 05:00:00,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:00,486 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting func_to_recursive_line_36_to_52_0Err178ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:00,486 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:00,486 INFO L85 PathProgramCache]: Analyzing trace with hash -41012852, now seen corresponding path program 1 times [2024-11-17 05:00:00,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:00,486 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [146429786] [2024-11-17 05:00:00,486 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:00,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:00,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:00,503 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1720386270] [2024-11-17 05:00:00,503 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:00,503 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:00,504 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:00,505 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:00,513 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-17 05:00:00,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:00,616 INFO L255 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-17 05:00:00,618 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:00,626 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 05:00:00,629 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 [2024-11-17 05:00:00,885 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 [2024-11-17 05:00:00,899 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:00,899 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 05:00:00,900 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:00,900 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [146429786] [2024-11-17 05:00:00,900 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:00,900 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1720386270] [2024-11-17 05:00:00,900 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1720386270] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 05:00:00,900 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 05:00:00,900 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-17 05:00:00,900 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [534084677] [2024-11-17 05:00:00,900 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 05:00:00,901 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-17 05:00:00,901 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:00,901 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-17 05:00:00,901 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-11-17 05:00:00,901 INFO L87 Difference]: Start difference. First operand 1906 states and 2777 transitions. Second operand has 13 states, 11 states have (on average 2.0) internal successors, (22), 11 states have internal predecessors, (22), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:01,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:01,783 INFO L93 Difference]: Finished difference Result 2191 states and 2852 transitions. [2024-11-17 05:00:01,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-17 05:00:01,784 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.0) internal successors, (22), 11 states have internal predecessors, (22), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2024-11-17 05:00:01,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:01,790 INFO L225 Difference]: With dead ends: 2191 [2024-11-17 05:00:01,790 INFO L226 Difference]: Without dead ends: 2190 [2024-11-17 05:00:01,791 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2024-11-17 05:00:01,791 INFO L432 NwaCegarLoop]: 568 mSDtfsCounter, 1847 mSDsluCounter, 5355 mSDsCounter, 0 mSdLazyCounter, 897 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1849 SdHoareTripleChecker+Valid, 5923 SdHoareTripleChecker+Invalid, 940 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 897 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:01,791 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1849 Valid, 5923 Invalid, 940 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 897 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-17 05:00:01,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2190 states. [2024-11-17 05:00:01,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2190 to 1906. [2024-11-17 05:00:01,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1906 states, 1577 states have (on average 1.6842105263157894) internal successors, (2656), 1839 states have internal predecessors, (2656), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 05:00:01,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1906 states to 1906 states and 2776 transitions. [2024-11-17 05:00:01,845 INFO L78 Accepts]: Start accepts. Automaton has 1906 states and 2776 transitions. Word has length 27 [2024-11-17 05:00:01,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:01,845 INFO L471 AbstractCegarLoop]: Abstraction has 1906 states and 2776 transitions. [2024-11-17 05:00:01,846 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.0) internal successors, (22), 11 states have internal predecessors, (22), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:01,846 INFO L276 IsEmpty]: Start isEmpty. Operand 1906 states and 2776 transitions. [2024-11-17 05:00:01,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-17 05:00:01,847 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:01,847 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-17 05:00:01,865 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-17 05:00:02,047 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:02,048 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting func_to_recursive_line_36_to_52_0Err177ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:02,049 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:02,049 INFO L85 PathProgramCache]: Analyzing trace with hash -1271398009, now seen corresponding path program 1 times [2024-11-17 05:00:02,049 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:02,049 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [636395201] [2024-11-17 05:00:02,050 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:02,050 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:02,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:02,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [307328582] [2024-11-17 05:00:02,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:02,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:02,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:02,073 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:02,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-17 05:00:02,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:02,173 INFO L255 TraceCheckSpWp]: Trace formula consists of 200 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-17 05:00:02,175 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:02,186 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 [2024-11-17 05:00:02,191 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 [2024-11-17 05:00:02,201 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 [2024-11-17 05:00:02,450 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 [2024-11-17 05:00:02,489 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:02,489 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 05:00:02,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:02,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [636395201] [2024-11-17 05:00:02,490 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:02,490 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [307328582] [2024-11-17 05:00:02,490 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [307328582] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 05:00:02,490 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 05:00:02,490 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-17 05:00:02,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1840355401] [2024-11-17 05:00:02,490 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 05:00:02,490 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-17 05:00:02,490 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:02,491 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-17 05:00:02,491 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2024-11-17 05:00:02,491 INFO L87 Difference]: Start difference. First operand 1906 states and 2776 transitions. Second operand has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:03,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:03,259 INFO L93 Difference]: Finished difference Result 2190 states and 2851 transitions. [2024-11-17 05:00:03,259 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-17 05:00:03,260 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2024-11-17 05:00:03,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:03,265 INFO L225 Difference]: With dead ends: 2190 [2024-11-17 05:00:03,265 INFO L226 Difference]: Without dead ends: 2189 [2024-11-17 05:00:03,266 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 18 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=124, Unknown=0, NotChecked=0, Total=182 [2024-11-17 05:00:03,267 INFO L432 NwaCegarLoop]: 566 mSDtfsCounter, 2001 mSDsluCounter, 2945 mSDsCounter, 0 mSdLazyCounter, 582 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2003 SdHoareTripleChecker+Valid, 3511 SdHoareTripleChecker+Invalid, 627 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 582 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:03,267 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2003 Valid, 3511 Invalid, 627 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 582 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-17 05:00:03,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2189 states. [2024-11-17 05:00:03,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2189 to 1906. [2024-11-17 05:00:03,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1906 states, 1577 states have (on average 1.683576410906785) internal successors, (2655), 1839 states have internal predecessors, (2655), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 05:00:03,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1906 states to 1906 states and 2775 transitions. [2024-11-17 05:00:03,354 INFO L78 Accepts]: Start accepts. Automaton has 1906 states and 2775 transitions. Word has length 28 [2024-11-17 05:00:03,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:03,355 INFO L471 AbstractCegarLoop]: Abstraction has 1906 states and 2775 transitions. [2024-11-17 05:00:03,355 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 8 states have internal predecessors, (23), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:03,355 INFO L276 IsEmpty]: Start isEmpty. Operand 1906 states and 2775 transitions. [2024-11-17 05:00:03,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-17 05:00:03,356 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:03,356 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-17 05:00:03,374 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-17 05:00:03,556 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-17 05:00:03,557 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting func_to_recursive_line_36_to_52_0Err176ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:03,557 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:03,557 INFO L85 PathProgramCache]: Analyzing trace with hash -758632214, now seen corresponding path program 1 times [2024-11-17 05:00:03,558 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:03,558 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1545346421] [2024-11-17 05:00:03,558 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:03,558 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:03,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:03,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1543705676] [2024-11-17 05:00:03,576 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:03,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:03,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:03,578 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:03,581 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-17 05:00:03,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:03,721 INFO L255 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-17 05:00:03,724 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:03,730 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 [2024-11-17 05:00:03,738 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 [2024-11-17 05:00:03,740 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 [2024-11-17 05:00:03,961 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 [2024-11-17 05:00:03,983 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:03,983 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 05:00:03,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:03,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1545346421] [2024-11-17 05:00:03,984 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:03,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1543705676] [2024-11-17 05:00:03,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1543705676] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 05:00:03,984 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 05:00:03,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-17 05:00:03,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2009116637] [2024-11-17 05:00:03,984 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 05:00:03,985 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-17 05:00:03,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:03,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-17 05:00:03,985 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2024-11-17 05:00:03,985 INFO L87 Difference]: Start difference. First operand 1906 states and 2775 transitions. Second operand has 9 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:04,776 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:04,776 INFO L93 Difference]: Finished difference Result 2189 states and 2850 transitions. [2024-11-17 05:00:04,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-17 05:00:04,777 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 29 [2024-11-17 05:00:04,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:04,782 INFO L225 Difference]: With dead ends: 2189 [2024-11-17 05:00:04,782 INFO L226 Difference]: Without dead ends: 2188 [2024-11-17 05:00:04,783 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=58, Invalid=124, Unknown=0, NotChecked=0, Total=182 [2024-11-17 05:00:04,783 INFO L432 NwaCegarLoop]: 567 mSDtfsCounter, 1996 mSDsluCounter, 2945 mSDsCounter, 0 mSdLazyCounter, 580 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1998 SdHoareTripleChecker+Valid, 3512 SdHoareTripleChecker+Invalid, 625 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 580 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:04,784 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1998 Valid, 3512 Invalid, 625 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 580 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-17 05:00:04,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2188 states. [2024-11-17 05:00:04,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2188 to 1906. [2024-11-17 05:00:04,830 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1906 states, 1577 states have (on average 1.6829422954977806) internal successors, (2654), 1839 states have internal predecessors, (2654), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 05:00:04,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1906 states to 1906 states and 2774 transitions. [2024-11-17 05:00:04,834 INFO L78 Accepts]: Start accepts. Automaton has 1906 states and 2774 transitions. Word has length 29 [2024-11-17 05:00:04,835 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:04,835 INFO L471 AbstractCegarLoop]: Abstraction has 1906 states and 2774 transitions. [2024-11-17 05:00:04,835 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:04,835 INFO L276 IsEmpty]: Start isEmpty. Operand 1906 states and 2774 transitions. [2024-11-17 05:00:04,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-17 05:00:04,836 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:04,836 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-17 05:00:04,854 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-17 05:00:05,037 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:05,037 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting func_to_recursive_line_36_to_52_0Err175ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:05,038 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:05,038 INFO L85 PathProgramCache]: Analyzing trace with hash 1098895464, now seen corresponding path program 1 times [2024-11-17 05:00:05,038 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:05,038 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280132248] [2024-11-17 05:00:05,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:05,038 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:05,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:05,060 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1381987454] [2024-11-17 05:00:05,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:05,060 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:05,060 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:05,063 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:05,064 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-17 05:00:05,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:05,180 INFO L255 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 70 conjuncts are in the unsatisfiable core [2024-11-17 05:00:05,183 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:05,190 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 [2024-11-17 05:00:05,193 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 [2024-11-17 05:00:05,197 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 [2024-11-17 05:00:05,204 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 [2024-11-17 05:00:05,378 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 [2024-11-17 05:00:05,685 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 05:00:05,685 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 29 [2024-11-17 05:00:05,713 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:05,713 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 05:00:05,713 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:05,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280132248] [2024-11-17 05:00:05,714 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:05,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1381987454] [2024-11-17 05:00:05,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1381987454] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 05:00:05,714 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 05:00:05,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-17 05:00:05,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1066893172] [2024-11-17 05:00:05,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 05:00:05,715 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-17 05:00:05,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:05,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-17 05:00:05,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-11-17 05:00:05,716 INFO L87 Difference]: Start difference. First operand 1906 states and 2774 transitions. Second operand has 13 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:07,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:07,297 INFO L93 Difference]: Finished difference Result 2188 states and 2849 transitions. [2024-11-17 05:00:07,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-17 05:00:07,297 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 31 [2024-11-17 05:00:07,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:07,302 INFO L225 Difference]: With dead ends: 2188 [2024-11-17 05:00:07,302 INFO L226 Difference]: Without dead ends: 2187 [2024-11-17 05:00:07,303 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2024-11-17 05:00:07,303 INFO L432 NwaCegarLoop]: 558 mSDtfsCounter, 2343 mSDsluCounter, 4091 mSDsCounter, 0 mSdLazyCounter, 846 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2345 SdHoareTripleChecker+Valid, 4649 SdHoareTripleChecker+Invalid, 898 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 846 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:07,303 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2345 Valid, 4649 Invalid, 898 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 846 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-17 05:00:07,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2187 states. [2024-11-17 05:00:07,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2187 to 1906. [2024-11-17 05:00:07,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1906 states, 1577 states have (on average 1.6823081800887763) internal successors, (2653), 1839 states have internal predecessors, (2653), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 05:00:07,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1906 states to 1906 states and 2773 transitions. [2024-11-17 05:00:07,353 INFO L78 Accepts]: Start accepts. Automaton has 1906 states and 2773 transitions. Word has length 31 [2024-11-17 05:00:07,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:07,353 INFO L471 AbstractCegarLoop]: Abstraction has 1906 states and 2773 transitions. [2024-11-17 05:00:07,353 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:07,353 INFO L276 IsEmpty]: Start isEmpty. Operand 1906 states and 2773 transitions. [2024-11-17 05:00:07,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-17 05:00:07,354 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:07,354 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-17 05:00:07,372 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-17 05:00:07,558 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-17 05:00:07,559 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting func_to_recursive_line_36_to_52_0Err174ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:07,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:07,559 INFO L85 PathProgramCache]: Analyzing trace with hash -293978588, now seen corresponding path program 1 times [2024-11-17 05:00:07,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:07,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [915082045] [2024-11-17 05:00:07,560 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:07,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:07,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:07,576 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [957903355] [2024-11-17 05:00:07,576 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:07,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:07,576 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:07,578 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:07,580 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-17 05:00:07,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:07,701 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 68 conjuncts are in the unsatisfiable core [2024-11-17 05:00:07,703 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:07,716 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 05:00:07,721 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 [2024-11-17 05:00:07,724 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 05:00:07,730 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 [2024-11-17 05:00:07,847 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 [2024-11-17 05:00:08,040 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 [2024-11-17 05:00:08,057 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:08,057 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-17 05:00:08,057 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:08,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [915082045] [2024-11-17 05:00:08,057 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:08,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [957903355] [2024-11-17 05:00:08,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [957903355] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 05:00:08,057 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 05:00:08,057 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-17 05:00:08,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [285861536] [2024-11-17 05:00:08,058 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 05:00:08,058 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-17 05:00:08,058 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:08,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-17 05:00:08,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-11-17 05:00:08,059 INFO L87 Difference]: Start difference. First operand 1906 states and 2773 transitions. Second operand has 13 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:09,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:09,325 INFO L93 Difference]: Finished difference Result 2187 states and 2848 transitions. [2024-11-17 05:00:09,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-17 05:00:09,325 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 32 [2024-11-17 05:00:09,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:09,331 INFO L225 Difference]: With dead ends: 2187 [2024-11-17 05:00:09,331 INFO L226 Difference]: Without dead ends: 2186 [2024-11-17 05:00:09,331 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 19 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=121, Invalid=385, Unknown=0, NotChecked=0, Total=506 [2024-11-17 05:00:09,332 INFO L432 NwaCegarLoop]: 559 mSDtfsCounter, 2218 mSDsluCounter, 4795 mSDsCounter, 0 mSdLazyCounter, 952 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2220 SdHoareTripleChecker+Valid, 5354 SdHoareTripleChecker+Invalid, 1000 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 952 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:09,332 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2220 Valid, 5354 Invalid, 1000 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 952 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-17 05:00:09,334 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2186 states. [2024-11-17 05:00:09,371 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2186 to 1906. [2024-11-17 05:00:09,374 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1906 states, 1577 states have (on average 1.6816740646797717) internal successors, (2652), 1839 states have internal predecessors, (2652), 49 states have call successors, (49), 15 states have call predecessors, (49), 23 states have return successors, (71), 51 states have call predecessors, (71), 49 states have call successors, (71) [2024-11-17 05:00:09,378 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1906 states to 1906 states and 2772 transitions. [2024-11-17 05:00:09,378 INFO L78 Accepts]: Start accepts. Automaton has 1906 states and 2772 transitions. Word has length 32 [2024-11-17 05:00:09,378 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:09,378 INFO L471 AbstractCegarLoop]: Abstraction has 1906 states and 2772 transitions. [2024-11-17 05:00:09,379 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 05:00:09,379 INFO L276 IsEmpty]: Start isEmpty. Operand 1906 states and 2772 transitions. [2024-11-17 05:00:09,379 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-17 05:00:09,379 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:09,380 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 05:00:09,397 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-17 05:00:09,583 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-17 05:00:09,584 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting func_to_recursive_line_36_to_52_0Err182ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:09,584 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:09,584 INFO L85 PathProgramCache]: Analyzing trace with hash 1870200587, now seen corresponding path program 2 times [2024-11-17 05:00:09,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:09,585 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [682669031] [2024-11-17 05:00:09,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:09,585 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:09,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:09,960 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-17 05:00:09,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:10,192 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-17 05:00:10,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:10,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-17 05:00:10,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:10,444 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-17 05:00:10,445 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:10,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [682669031] [2024-11-17 05:00:10,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [682669031] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 05:00:10,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1519066319] [2024-11-17 05:00:10,445 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-17 05:00:10,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:10,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:10,447 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:10,448 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-17 05:00:10,575 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-17 05:00:10,575 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 05:00:10,577 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-11-17 05:00:10,580 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:10,588 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 [2024-11-17 05:00:10,594 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 [2024-11-17 05:00:10,922 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19| Int)) (= (select (select |c_#memory_int#3| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19|) 0) 0)) (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_28| Int)) (let ((.cse0 (select |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (= (store |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_28| 4))) |c_#memory_int#2|) (<= |v_func_to_recursive_line_28_to_32_0_#t~mem98_28| (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|)))))) is different from true [2024-11-17 05:00:10,940 WARN L873 $PredicateComparison]: unable to prove that (and (exists ((|v_func_to_recursive_line_28_to_32_0_#t~mem98_30| Int)) (let ((.cse0 (select |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base|))) (and (<= |v_func_to_recursive_line_28_to_32_0_#t~mem98_30| (* (select .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset|) 4)) (= (store |c_old(#memory_int#2)| |c_func_to_recursive_line_28_to_32_0_#in~q.base| (store .cse0 |c_func_to_recursive_line_28_to_32_0_#in~q.offset| (* |v_func_to_recursive_line_28_to_32_0_#t~mem98_30| 4))) |c_#memory_int#2|)))) (exists ((|v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19| Int)) (= (select (select |c_#memory_int#3| |v_ULTIMATE.start_main_~#p~0#1.base_BEFORE_CALL_19|) 0) 0))) is different from true [2024-11-17 05:00:10,963 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 21 treesize of output 13 [2024-11-17 05:00:11,183 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2024-11-17 05:00:11,215 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 6 not checked. [2024-11-17 05:00:11,215 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 05:00:11,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1519066319] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 05:00:11,754 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-17 05:00:11,755 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13] total 30 [2024-11-17 05:00:11,755 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [865308774] [2024-11-17 05:00:11,755 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-17 05:00:11,755 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-17 05:00:11,755 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:11,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-17 05:00:11,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=1195, Unknown=2, NotChecked=142, Total=1482 [2024-11-17 05:00:11,756 INFO L87 Difference]: Start difference. First operand 1906 states and 2772 transitions. Second operand has 31 states, 23 states have (on average 1.9565217391304348) internal successors, (45), 27 states have internal predecessors, (45), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 05:00:14,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:14,509 INFO L93 Difference]: Finished difference Result 2550 states and 3045 transitions. [2024-11-17 05:00:14,510 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-17 05:00:14,511 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 23 states have (on average 1.9565217391304348) internal successors, (45), 27 states have internal predecessors, (45), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 34 [2024-11-17 05:00:14,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:14,522 INFO L225 Difference]: With dead ends: 2550 [2024-11-17 05:00:14,523 INFO L226 Difference]: Without dead ends: 2549 [2024-11-17 05:00:14,525 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 30 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 624 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=343, Invalid=2315, Unknown=2, NotChecked=202, Total=2862 [2024-11-17 05:00:14,526 INFO L432 NwaCegarLoop]: 1136 mSDtfsCounter, 3485 mSDsluCounter, 16938 mSDsCounter, 0 mSdLazyCounter, 2646 mSolverCounterSat, 90 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3495 SdHoareTripleChecker+Valid, 18074 SdHoareTripleChecker+Invalid, 6532 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 90 IncrementalHoareTripleChecker+Valid, 2646 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 3796 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:14,528 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3495 Valid, 18074 Invalid, 6532 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [90 Valid, 2646 Invalid, 0 Unknown, 3796 Unchecked, 2.0s Time] [2024-11-17 05:00:14,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2549 states. [2024-11-17 05:00:14,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2549 to 1653. [2024-11-17 05:00:14,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1653 states, 1332 states have (on average 1.677927927927928) internal successors, (2235), 1594 states have internal predecessors, (2235), 42 states have call successors, (42), 14 states have call predecessors, (42), 22 states have return successors, (63), 44 states have call predecessors, (63), 42 states have call successors, (63) [2024-11-17 05:00:14,584 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1653 states to 1653 states and 2340 transitions. [2024-11-17 05:00:14,585 INFO L78 Accepts]: Start accepts. Automaton has 1653 states and 2340 transitions. Word has length 34 [2024-11-17 05:00:14,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:14,586 INFO L471 AbstractCegarLoop]: Abstraction has 1653 states and 2340 transitions. [2024-11-17 05:00:14,586 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 23 states have (on average 1.9565217391304348) internal successors, (45), 27 states have internal predecessors, (45), 7 states have call successors, (7), 4 states have call predecessors, (7), 6 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 05:00:14,586 INFO L276 IsEmpty]: Start isEmpty. Operand 1653 states and 2340 transitions. [2024-11-17 05:00:14,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-17 05:00:14,586 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:14,587 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 05:00:14,604 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-17 05:00:14,790 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-17 05:00:14,791 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting func_to_recursive_line_36_to_52_0Err179ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:14,791 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:14,791 INFO L85 PathProgramCache]: Analyzing trace with hash -1839372516, now seen corresponding path program 1 times [2024-11-17 05:00:14,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:14,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1014772474] [2024-11-17 05:00:14,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:14,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:14,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:14,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1411513724] [2024-11-17 05:00:14,808 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:14,808 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:14,808 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:14,810 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:14,811 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-17 05:00:14,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:14,943 INFO L255 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 56 conjuncts are in the unsatisfiable core [2024-11-17 05:00:14,945 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:14,953 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 [2024-11-17 05:00:14,957 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 [2024-11-17 05:00:14,960 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 [2024-11-17 05:00:15,109 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 05:00:15,151 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 21 treesize of output 13 [2024-11-17 05:00:15,169 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 05:00:15,169 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 30 treesize of output 30 [2024-11-17 05:00:15,401 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 [2024-11-17 05:00:15,405 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 [2024-11-17 05:00:15,426 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-17 05:00:15,426 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 05:00:15,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:15,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1014772474] [2024-11-17 05:00:15,597 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:15,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1411513724] [2024-11-17 05:00:15,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1411513724] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 05:00:15,597 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-17 05:00:15,597 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-11-17 05:00:15,597 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1508226919] [2024-11-17 05:00:15,597 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-17 05:00:15,598 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-17 05:00:15,598 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:15,598 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-17 05:00:15,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2024-11-17 05:00:15,599 INFO L87 Difference]: Start difference. First operand 1653 states and 2340 transitions. Second operand has 13 states, 10 states have (on average 2.8) internal successors, (28), 11 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 05:00:21,225 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] [2024-11-17 05:00:26,191 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.59s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-17 05:00:30,245 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] [2024-11-17 05:00:30,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:30,572 INFO L93 Difference]: Finished difference Result 2422 states and 2954 transitions. [2024-11-17 05:00:30,572 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-17 05:00:30,572 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 2.8) internal successors, (28), 11 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 35 [2024-11-17 05:00:30,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:30,579 INFO L225 Difference]: With dead ends: 2422 [2024-11-17 05:00:30,579 INFO L226 Difference]: Without dead ends: 2421 [2024-11-17 05:00:30,580 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2024-11-17 05:00:30,581 INFO L432 NwaCegarLoop]: 1127 mSDtfsCounter, 1426 mSDsluCounter, 10176 mSDsCounter, 0 mSdLazyCounter, 1704 mSolverCounterSat, 28 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 14.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1434 SdHoareTripleChecker+Valid, 11303 SdHoareTripleChecker+Invalid, 1735 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 1704 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 14.8s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:30,581 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1434 Valid, 11303 Invalid, 1735 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 1704 Invalid, 3 Unknown, 0 Unchecked, 14.8s Time] [2024-11-17 05:00:30,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2421 states. [2024-11-17 05:00:30,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2421 to 1967. [2024-11-17 05:00:30,650 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1967 states, 1635 states have (on average 1.6807339449541285) internal successors, (2748), 1897 states have internal predecessors, (2748), 51 states have call successors, (51), 16 states have call predecessors, (51), 24 states have return successors, (74), 53 states have call predecessors, (74), 51 states have call successors, (74) [2024-11-17 05:00:30,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1967 states to 1967 states and 2873 transitions. [2024-11-17 05:00:30,656 INFO L78 Accepts]: Start accepts. Automaton has 1967 states and 2873 transitions. Word has length 35 [2024-11-17 05:00:30,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:30,657 INFO L471 AbstractCegarLoop]: Abstraction has 1967 states and 2873 transitions. [2024-11-17 05:00:30,657 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 2.8) internal successors, (28), 11 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 05:00:30,657 INFO L276 IsEmpty]: Start isEmpty. Operand 1967 states and 2873 transitions. [2024-11-17 05:00:30,658 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-17 05:00:30,658 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:30,658 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1] [2024-11-17 05:00:30,677 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-17 05:00:30,862 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-17 05:00:30,863 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting func_to_recursive_line_28_to_32_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:30,863 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:30,863 INFO L85 PathProgramCache]: Analyzing trace with hash 619585068, now seen corresponding path program 2 times [2024-11-17 05:00:30,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:30,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1764107866] [2024-11-17 05:00:30,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:30,864 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:30,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:31,601 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:31,602 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:31,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1764107866] [2024-11-17 05:00:31,603 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1764107866] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 05:00:31,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1262202737] [2024-11-17 05:00:31,603 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-17 05:00:31,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:31,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:31,606 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:31,608 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-17 05:00:31,737 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-17 05:00:31,737 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 05:00:31,740 INFO L255 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-17 05:00:31,742 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:31,746 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 05:00:31,785 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 21 treesize of output 13 [2024-11-17 05:00:31,913 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 39 treesize of output 23 [2024-11-17 05:00:32,052 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 39 treesize of output 23 [2024-11-17 05:00:32,186 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 29 [2024-11-17 05:00:32,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 26 treesize of output 14 [2024-11-17 05:00:32,268 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:32,269 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 05:00:32,707 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 05:00:32,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1262202737] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 05:00:32,707 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 05:00:32,707 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17, 17] total 49 [2024-11-17 05:00:32,707 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1268473259] [2024-11-17 05:00:32,707 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 05:00:32,708 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-17 05:00:32,708 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:32,708 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-17 05:00:32,709 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=420, Invalid=2030, Unknown=0, NotChecked=0, Total=2450 [2024-11-17 05:00:32,710 INFO L87 Difference]: Start difference. First operand 1967 states and 2873 transitions. Second operand has 50 states, 47 states have (on average 1.8297872340425532) internal successors, (86), 36 states have internal predecessors, (86), 14 states have call successors, (14), 14 states have call predecessors, (14), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 05:00:33,918 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:33,918 INFO L93 Difference]: Finished difference Result 2035 states and 2964 transitions. [2024-11-17 05:00:33,918 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2024-11-17 05:00:33,919 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 47 states have (on average 1.8297872340425532) internal successors, (86), 36 states have internal predecessors, (86), 14 states have call successors, (14), 14 states have call predecessors, (14), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 36 [2024-11-17 05:00:33,919 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:33,923 INFO L225 Difference]: With dead ends: 2035 [2024-11-17 05:00:33,923 INFO L226 Difference]: Without dead ends: 2034 [2024-11-17 05:00:33,926 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1938 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1113, Invalid=4587, Unknown=0, NotChecked=0, Total=5700 [2024-11-17 05:00:33,927 INFO L432 NwaCegarLoop]: 646 mSDtfsCounter, 360 mSDsluCounter, 4990 mSDsCounter, 0 mSdLazyCounter, 543 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 360 SdHoareTripleChecker+Valid, 5636 SdHoareTripleChecker+Invalid, 596 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 543 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:33,928 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [360 Valid, 5636 Invalid, 596 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 543 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-17 05:00:33,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2034 states. [2024-11-17 05:00:33,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2034 to 2033. [2024-11-17 05:00:33,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2033 states, 1683 states have (on average 1.6648841354723707) internal successors, (2802), 1951 states have internal predecessors, (2802), 57 states have call successors, (57), 22 states have call predecessors, (57), 36 states have return successors, (98), 59 states have call predecessors, (98), 57 states have call successors, (98) [2024-11-17 05:00:33,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2033 states to 2033 states and 2957 transitions. [2024-11-17 05:00:33,995 INFO L78 Accepts]: Start accepts. Automaton has 2033 states and 2957 transitions. Word has length 36 [2024-11-17 05:00:33,995 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:33,995 INFO L471 AbstractCegarLoop]: Abstraction has 2033 states and 2957 transitions. [2024-11-17 05:00:33,996 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 47 states have (on average 1.8297872340425532) internal successors, (86), 36 states have internal predecessors, (86), 14 states have call successors, (14), 14 states have call predecessors, (14), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 05:00:33,996 INFO L276 IsEmpty]: Start isEmpty. Operand 2033 states and 2957 transitions. [2024-11-17 05:00:33,996 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-17 05:00:33,996 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:33,996 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 05:00:34,015 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-17 05:00:34,197 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:34,197 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting func_to_recursive_line_36_to_52_0Err178ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:34,197 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:34,197 INFO L85 PathProgramCache]: Analyzing trace with hash -1185972743, now seen corresponding path program 1 times [2024-11-17 05:00:34,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:34,198 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [613420569] [2024-11-17 05:00:34,198 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:34,198 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:34,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:34,216 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [209703739] [2024-11-17 05:00:34,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:34,216 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:34,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:34,218 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:34,220 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-17 05:00:34,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:34,359 INFO L255 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 78 conjuncts are in the unsatisfiable core [2024-11-17 05:00:34,362 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:34,369 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 [2024-11-17 05:00:34,377 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 [2024-11-17 05:00:34,383 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 [2024-11-17 05:00:34,642 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 [2024-11-17 05:00:34,762 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 05:00:34,762 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 43 treesize of output 39 [2024-11-17 05:00:34,772 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 [2024-11-17 05:00:35,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2024-11-17 05:00:35,058 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 05:00:35,058 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 05:00:35,278 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 05:00:35,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [613420569] [2024-11-17 05:00:35,278 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-17 05:00:35,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [209703739] [2024-11-17 05:00:35,278 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [209703739] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 05:00:35,278 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-17 05:00:35,279 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-17 05:00:35,279 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1315717384] [2024-11-17 05:00:35,279 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-17 05:00:35,279 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-17 05:00:35,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 05:00:35,280 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-17 05:00:35,280 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=261, Unknown=0, NotChecked=0, Total=306 [2024-11-17 05:00:35,280 INFO L87 Difference]: Start difference. First operand 2033 states and 2957 transitions. Second operand has 16 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 13 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 05:00:39,697 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-17 05:00:43,872 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-17 05:00:49,293 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-17 05:00:53,368 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] [2024-11-17 05:00:57,423 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] [2024-11-17 05:00:57,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 05:00:57,653 INFO L93 Difference]: Finished difference Result 2487 states and 3037 transitions. [2024-11-17 05:00:57,653 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-17 05:00:57,654 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 13 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 36 [2024-11-17 05:00:57,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-17 05:00:57,658 INFO L225 Difference]: With dead ends: 2487 [2024-11-17 05:00:57,658 INFO L226 Difference]: Without dead ends: 2486 [2024-11-17 05:00:57,659 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=75, Invalid=431, Unknown=0, NotChecked=0, Total=506 [2024-11-17 05:00:57,659 INFO L432 NwaCegarLoop]: 1128 mSDtfsCounter, 1420 mSDsluCounter, 9846 mSDsCounter, 0 mSdLazyCounter, 1675 mSolverCounterSat, 29 mSolverCounterUnsat, 14 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 21.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1428 SdHoareTripleChecker+Valid, 10974 SdHoareTripleChecker+Invalid, 1718 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 1675 IncrementalHoareTripleChecker+Invalid, 14 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 22.0s IncrementalHoareTripleChecker+Time [2024-11-17 05:00:57,660 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1428 Valid, 10974 Invalid, 1718 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 1675 Invalid, 14 Unknown, 0 Unchecked, 22.0s Time] [2024-11-17 05:00:57,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2486 states. [2024-11-17 05:00:57,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2486 to 2033. [2024-11-17 05:00:57,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2033 states, 1683 states have (on average 1.6642899584076054) internal successors, (2801), 1951 states have internal predecessors, (2801), 57 states have call successors, (57), 22 states have call predecessors, (57), 36 states have return successors, (98), 59 states have call predecessors, (98), 57 states have call successors, (98) [2024-11-17 05:00:57,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2033 states to 2033 states and 2956 transitions. [2024-11-17 05:00:57,731 INFO L78 Accepts]: Start accepts. Automaton has 2033 states and 2956 transitions. Word has length 36 [2024-11-17 05:00:57,731 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-17 05:00:57,731 INFO L471 AbstractCegarLoop]: Abstraction has 2033 states and 2956 transitions. [2024-11-17 05:00:57,732 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 13 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 05:00:57,732 INFO L276 IsEmpty]: Start isEmpty. Operand 2033 states and 2956 transitions. [2024-11-17 05:00:57,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-17 05:00:57,732 INFO L207 NwaCegarLoop]: Found error trace [2024-11-17 05:00:57,733 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 05:00:57,748 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-17 05:00:57,936 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-17 05:00:57,937 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting func_to_recursive_line_36_to_52_0Err177ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_36_to_52_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_36_to_52_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 256 more)] === [2024-11-17 05:00:57,937 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 05:00:57,937 INFO L85 PathProgramCache]: Analyzing trace with hash 1889551034, now seen corresponding path program 1 times [2024-11-17 05:00:57,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 05:00:57,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1476836631] [2024-11-17 05:00:57,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:57,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 05:00:57,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-17 05:00:57,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1601065467] [2024-11-17 05:00:57,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 05:00:57,956 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 05:00:57,956 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 05:00:57,958 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 05:00:57,959 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-17 05:00:58,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 05:00:58,093 INFO L255 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 84 conjuncts are in the unsatisfiable core [2024-11-17 05:00:58,096 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 05:00:58,100 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-17 05:00:58,105 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 [2024-11-17 05:00:58,112 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 [2024-11-17 05:00:58,120 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 [2024-11-17 05:00:58,375 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 [2024-11-17 05:00:58,501 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 [2024-11-17 05:00:58,516 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 05:00:58,517 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 30 treesize of output 30 [2024-11-17 05:00:58,889 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 [2024-11-17 05:00:58,935 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-17 05:00:58,935 INFO L311 TraceCheckSpWp]: Computing backward predicates...