./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/no-overflow.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_3.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 4a390ef5 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_3.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 9a8e2b8a66923dd7d46d9db92fbd8b38c75eb8108da5237ec87b15cd1ae67985 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4a390ef-m [2024-10-24 20:43:11,797 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-24 20:43:11,880 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2024-10-24 20:43:11,886 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-24 20:43:11,889 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-24 20:43:11,915 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-24 20:43:11,916 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-24 20:43:11,916 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-24 20:43:11,917 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-24 20:43:11,918 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-24 20:43:11,920 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-24 20:43:11,920 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-24 20:43:11,920 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-24 20:43:11,921 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-24 20:43:11,921 INFO L153 SettingsManager]: * Use SBE=true [2024-10-24 20:43:11,922 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-24 20:43:11,925 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-24 20:43:11,925 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-24 20:43:11,926 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-24 20:43:11,926 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-24 20:43:11,926 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-24 20:43:11,927 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-24 20:43:11,927 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-24 20:43:11,927 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-24 20:43:11,928 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-24 20:43:11,928 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2024-10-24 20:43:11,928 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-24 20:43:11,928 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-24 20:43:11,928 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-24 20:43:11,929 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-24 20:43:11,929 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-24 20:43:11,929 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-24 20:43:11,930 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-24 20:43:11,930 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-24 20:43:11,930 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 20:43:11,933 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-24 20:43:11,933 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-24 20:43:11,933 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-24 20:43:11,934 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-24 20:43:11,934 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-24 20:43:11,934 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-24 20:43:11,936 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-24 20:43:11,937 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-24 20:43:11,937 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-24 20:43:11,937 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 -> 9a8e2b8a66923dd7d46d9db92fbd8b38c75eb8108da5237ec87b15cd1ae67985 [2024-10-24 20:43:12,189 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-24 20:43:12,216 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-24 20:43:12,219 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-24 20:43:12,220 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-24 20:43:12,220 INFO L274 PluginConnector]: CDTParser initialized [2024-10-24 20:43:12,222 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_3.c [2024-10-24 20:43:13,752 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-24 20:43:13,941 INFO L384 CDTParser]: Found 1 translation units. [2024-10-24 20:43:13,941 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_3.c [2024-10-24 20:43:13,948 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/752a835e1/170a1238fe4a4cf8834e8a8bf8c53e9e/FLAGb9f491cd3 [2024-10-24 20:43:13,962 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/752a835e1/170a1238fe4a4cf8834e8a8bf8c53e9e [2024-10-24 20:43:13,965 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-24 20:43:13,966 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-24 20:43:13,967 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-24 20:43:13,967 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-24 20:43:13,973 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-24 20:43:13,973 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 08:43:13" (1/1) ... [2024-10-24 20:43:13,976 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7282a32 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:13, skipping insertion in model container [2024-10-24 20:43:13,976 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 08:43:13" (1/1) ... [2024-10-24 20:43:13,999 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-24 20:43:14,190 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 20:43:14,232 INFO L200 MainTranslator]: Completed pre-run [2024-10-24 20:43:14,257 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 20:43:14,277 INFO L204 MainTranslator]: Completed translation [2024-10-24 20:43:14,278 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14 WrapperNode [2024-10-24 20:43:14,278 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-24 20:43:14,279 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-24 20:43:14,279 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-24 20:43:14,279 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-24 20:43:14,302 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,311 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,329 INFO L138 Inliner]: procedures = 14, calls = 41, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 53 [2024-10-24 20:43:14,329 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-24 20:43:14,331 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-24 20:43:14,331 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-24 20:43:14,331 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-24 20:43:14,341 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,342 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,344 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,360 INFO L175 MemorySlicer]: Split 20 memory accesses to 4 slices as follows [2, 6, 6, 6]. 30 percent of accesses are in the largest equivalence class. The 5 initializations are split as follows [2, 1, 1, 1]. The 6 writes are split as follows [0, 2, 2, 2]. [2024-10-24 20:43:14,362 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,363 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,372 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,374 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,378 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,382 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,384 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-24 20:43:14,388 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-24 20:43:14,389 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-24 20:43:14,392 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-24 20:43:14,396 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (1/1) ... [2024-10-24 20:43:14,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 20:43:14,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:14,423 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-10-24 20:43:14,428 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-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-10-24 20:43:14,460 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-10-24 20:43:14,461 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-10-24 20:43:14,461 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-10-24 20:43:14,461 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-10-24 20:43:14,461 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_23_to_23_0 [2024-10-24 20:43:14,461 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_23_to_23_0 [2024-10-24 20:43:14,461 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_22_to_23_0 [2024-10-24 20:43:14,461 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_22_to_23_0 [2024-10-24 20:43:14,461 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-24 20:43:14,462 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-24 20:43:14,462 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-10-24 20:43:14,462 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-10-24 20:43:14,462 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-10-24 20:43:14,462 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-10-24 20:43:14,462 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_21_to_22_0 [2024-10-24 20:43:14,462 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_21_to_22_0 [2024-10-24 20:43:14,462 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-10-24 20:43:14,542 INFO L238 CfgBuilder]: Building ICFG [2024-10-24 20:43:14,545 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-24 20:43:14,722 INFO L? ?]: Removed 15 outVars from TransFormulas that were not future-live. [2024-10-24 20:43:14,722 INFO L287 CfgBuilder]: Performing block encoding [2024-10-24 20:43:14,754 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-24 20:43:14,754 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-24 20:43:14,759 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 08:43:14 BoogieIcfgContainer [2024-10-24 20:43:14,759 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-24 20:43:14,761 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-24 20:43:14,761 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-24 20:43:14,766 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-24 20:43:14,766 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.10 08:43:13" (1/3) ... [2024-10-24 20:43:14,767 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2b1e9956 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 08:43:14, skipping insertion in model container [2024-10-24 20:43:14,768 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 08:43:14" (2/3) ... [2024-10-24 20:43:14,768 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2b1e9956 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 08:43:14, skipping insertion in model container [2024-10-24 20:43:14,768 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 08:43:14" (3/3) ... [2024-10-24 20:43:14,770 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_nested_3.c [2024-10-24 20:43:14,787 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-24 20:43:14,787 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 6 error locations. [2024-10-24 20:43:14,840 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-24 20:43:14,846 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;@6d860fff, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-24 20:43:14,846 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2024-10-24 20:43:14,850 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 24 states have (on average 1.5) internal successors, (36), 33 states have internal predecessors, (36), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-24 20:43:14,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-10-24 20:43:14,855 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:14,856 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:14,856 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:14,860 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:14,861 INFO L85 PathProgramCache]: Analyzing trace with hash -1687961075, now seen corresponding path program 1 times [2024-10-24 20:43:14,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:14,869 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1849471657] [2024-10-24 20:43:14,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:14,870 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:14,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:15,381 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 20:43:15,381 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:15,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1849471657] [2024-10-24 20:43:15,384 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1849471657] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:15,384 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 20:43:15,385 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 20:43:15,386 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553052241] [2024-10-24 20:43:15,387 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:15,391 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 20:43:15,391 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:15,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 20:43:15,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-24 20:43:15,412 INFO L87 Difference]: Start difference. First operand has 40 states, 24 states have (on average 1.5) internal successors, (36), 33 states have internal predecessors, (36), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 6 states, 4 states have (on average 2.0) internal successors, (8), 5 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:15,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:15,563 INFO L93 Difference]: Finished difference Result 56 states and 65 transitions. [2024-10-24 20:43:15,564 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 20:43:15,566 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 4 states have (on average 2.0) internal successors, (8), 5 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-10-24 20:43:15,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:15,576 INFO L225 Difference]: With dead ends: 56 [2024-10-24 20:43:15,576 INFO L226 Difference]: Without dead ends: 43 [2024-10-24 20:43:15,578 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2024-10-24 20:43:15,581 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 15 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:15,582 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 185 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:15,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-10-24 20:43:15,617 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 37. [2024-10-24 20:43:15,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 30 states have internal predecessors, (31), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-10-24 20:43:15,619 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 42 transitions. [2024-10-24 20:43:15,621 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 42 transitions. Word has length 11 [2024-10-24 20:43:15,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:15,621 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 42 transitions. [2024-10-24 20:43:15,621 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 4 states have (on average 2.0) internal successors, (8), 5 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:15,622 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2024-10-24 20:43:15,622 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-10-24 20:43:15,623 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:15,623 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:15,623 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-24 20:43:15,623 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting func_to_recursive_line_21_to_22_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:15,624 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:15,624 INFO L85 PathProgramCache]: Analyzing trace with hash -1680998632, now seen corresponding path program 1 times [2024-10-24 20:43:15,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:15,625 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1258119857] [2024-10-24 20:43:15,625 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:15,625 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:15,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:15,819 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:15,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:15,830 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 20:43:15,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:15,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1258119857] [2024-10-24 20:43:15,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1258119857] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:15,830 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 20:43:15,830 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-24 20:43:15,831 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2009470439] [2024-10-24 20:43:15,831 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:15,832 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 20:43:15,832 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:15,833 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 20:43:15,837 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-10-24 20:43:15,837 INFO L87 Difference]: Start difference. First operand 37 states and 42 transitions. Second operand has 7 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 2 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-10-24 20:43:16,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:16,069 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2024-10-24 20:43:16,069 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 20:43:16,070 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 2 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 11 [2024-10-24 20:43:16,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:16,071 INFO L225 Difference]: With dead ends: 49 [2024-10-24 20:43:16,071 INFO L226 Difference]: Without dead ends: 47 [2024-10-24 20:43:16,072 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2024-10-24 20:43:16,074 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 19 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:16,074 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 85 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 20:43:16,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-10-24 20:43:16,083 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2024-10-24 20:43:16,083 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.3214285714285714) internal successors, (37), 35 states have internal predecessors, (37), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-10-24 20:43:16,084 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2024-10-24 20:43:16,085 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 11 [2024-10-24 20:43:16,085 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:16,085 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2024-10-24 20:43:16,085 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 2 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-10-24 20:43:16,085 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2024-10-24 20:43:16,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-10-24 20:43:16,086 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:16,086 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:16,087 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-24 20:43:16,087 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting func_to_recursive_line_22_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:16,088 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:16,088 INFO L85 PathProgramCache]: Analyzing trace with hash -564507169, now seen corresponding path program 1 times [2024-10-24 20:43:16,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:16,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1387666952] [2024-10-24 20:43:16,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:16,089 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:16,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:16,223 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 20:43:16,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:16,284 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 20:43:16,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:16,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1387666952] [2024-10-24 20:43:16,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1387666952] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:16,285 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 20:43:16,285 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-24 20:43:16,286 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1594165594] [2024-10-24 20:43:16,286 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:16,286 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 20:43:16,286 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:16,287 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 20:43:16,287 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-24 20:43:16,287 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-24 20:43:16,384 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:16,385 INFO L93 Difference]: Finished difference Result 96 states and 112 transitions. [2024-10-24 20:43:16,386 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 20:43:16,386 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2024-10-24 20:43:16,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:16,387 INFO L225 Difference]: With dead ends: 96 [2024-10-24 20:43:16,387 INFO L226 Difference]: Without dead ends: 54 [2024-10-24 20:43:16,388 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-24 20:43:16,389 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 17 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:16,389 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 103 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:16,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-10-24 20:43:16,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 43. [2024-10-24 20:43:16,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 33 states have internal predecessors, (35), 7 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-24 20:43:16,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 48 transitions. [2024-10-24 20:43:16,401 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 48 transitions. Word has length 14 [2024-10-24 20:43:16,401 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:16,401 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 48 transitions. [2024-10-24 20:43:16,401 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-24 20:43:16,401 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2024-10-24 20:43:16,402 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-10-24 20:43:16,402 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:16,402 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:16,402 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-10-24 20:43:16,402 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:16,403 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:16,403 INFO L85 PathProgramCache]: Analyzing trace with hash 789392049, now seen corresponding path program 1 times [2024-10-24 20:43:16,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:16,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1189093368] [2024-10-24 20:43:16,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:16,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:16,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:16,715 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 20:43:16,715 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:16,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1189093368] [2024-10-24 20:43:16,715 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1189093368] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:16,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111492860] [2024-10-24 20:43:16,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:16,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:16,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:16,718 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-10-24 20:43:16,719 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-10-24 20:43:16,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:16,820 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-24 20:43:16,830 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:16,877 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-10-24 20:43:16,948 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 23 treesize of output 3 [2024-10-24 20:43:16,969 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-10-24 20:43:16,974 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 20:43:16,975 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 20:43:17,148 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 20:43:17,151 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111492860] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:17,151 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2024-10-24 20:43:17,151 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9, 8] total 17 [2024-10-24 20:43:17,151 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [935216059] [2024-10-24 20:43:17,152 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:17,152 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-24 20:43:17,152 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:17,155 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-24 20:43:17,155 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=249, Unknown=0, NotChecked=0, Total=306 [2024-10-24 20:43:17,155 INFO L87 Difference]: Start difference. First operand 43 states and 48 transitions. Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 7 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:17,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:17,362 INFO L93 Difference]: Finished difference Result 46 states and 55 transitions. [2024-10-24 20:43:17,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-24 20:43:17,363 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 7 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 16 [2024-10-24 20:43:17,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:17,365 INFO L225 Difference]: With dead ends: 46 [2024-10-24 20:43:17,366 INFO L226 Difference]: Without dead ends: 45 [2024-10-24 20:43:17,367 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=102, Invalid=450, Unknown=0, NotChecked=0, Total=552 [2024-10-24 20:43:17,368 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 17 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:17,370 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 164 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:17,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-24 20:43:17,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 42. [2024-10-24 20:43:17,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 32 states have internal predecessors, (34), 7 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-24 20:43:17,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 47 transitions. [2024-10-24 20:43:17,383 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 47 transitions. Word has length 16 [2024-10-24 20:43:17,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:17,384 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 47 transitions. [2024-10-24 20:43:17,386 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 7 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:17,387 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 47 transitions. [2024-10-24 20:43:17,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-24 20:43:17,387 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:17,387 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:17,406 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-24 20:43:17,588 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:17,588 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:17,589 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:17,589 INFO L85 PathProgramCache]: Analyzing trace with hash -1298650220, now seen corresponding path program 1 times [2024-10-24 20:43:17,589 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:17,589 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1400506837] [2024-10-24 20:43:17,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:17,590 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:17,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:17,645 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-24 20:43:17,645 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:17,645 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1400506837] [2024-10-24 20:43:17,646 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1400506837] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:17,646 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 20:43:17,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-10-24 20:43:17,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [175378548] [2024-10-24 20:43:17,646 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:17,647 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-24 20:43:17,647 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:17,647 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-24 20:43:17,647 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-24 20:43:17,648 INFO L87 Difference]: Start difference. First operand 42 states and 47 transitions. Second operand has 4 states, 3 states have (on average 4.333333333333333) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 1 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:17,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:17,668 INFO L93 Difference]: Finished difference Result 42 states and 47 transitions. [2024-10-24 20:43:17,669 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-24 20:43:17,669 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 4.333333333333333) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 1 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 17 [2024-10-24 20:43:17,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:17,670 INFO L225 Difference]: With dead ends: 42 [2024-10-24 20:43:17,670 INFO L226 Difference]: Without dead ends: 41 [2024-10-24 20:43:17,670 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-24 20:43:17,671 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:17,671 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 82 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 20:43:17,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-10-24 20:43:17,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 39. [2024-10-24 20:43:17,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 29 states have internal predecessors, (31), 7 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-10-24 20:43:17,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 44 transitions. [2024-10-24 20:43:17,683 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 44 transitions. Word has length 17 [2024-10-24 20:43:17,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:17,683 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 44 transitions. [2024-10-24 20:43:17,684 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 4.333333333333333) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 1 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:17,684 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 44 transitions. [2024-10-24 20:43:17,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-10-24 20:43:17,687 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:17,687 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:17,688 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-10-24 20:43:17,688 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting func_to_recursive_line_22_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:17,688 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:17,688 INFO L85 PathProgramCache]: Analyzing trace with hash -1900896519, now seen corresponding path program 1 times [2024-10-24 20:43:17,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:17,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [47103261] [2024-10-24 20:43:17,689 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:17,689 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:17,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:17,811 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 20:43:17,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:17,819 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:17,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:17,824 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 20:43:17,824 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:17,824 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [47103261] [2024-10-24 20:43:17,824 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [47103261] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:17,824 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 20:43:17,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-24 20:43:17,825 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1518196130] [2024-10-24 20:43:17,825 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:17,826 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 20:43:17,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:17,827 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 20:43:17,827 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-10-24 20:43:17,827 INFO L87 Difference]: Start difference. First operand 39 states and 44 transitions. Second operand has 7 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 20:43:17,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:17,968 INFO L93 Difference]: Finished difference Result 60 states and 68 transitions. [2024-10-24 20:43:17,968 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 20:43:17,968 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2024-10-24 20:43:17,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:17,969 INFO L225 Difference]: With dead ends: 60 [2024-10-24 20:43:17,969 INFO L226 Difference]: Without dead ends: 58 [2024-10-24 20:43:17,969 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2024-10-24 20:43:17,970 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 34 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:17,970 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 110 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:17,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-10-24 20:43:17,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 49. [2024-10-24 20:43:17,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 32 states have (on average 1.21875) internal successors, (39), 36 states have internal predecessors, (39), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2024-10-24 20:43:17,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 57 transitions. [2024-10-24 20:43:17,983 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 57 transitions. Word has length 21 [2024-10-24 20:43:17,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:17,984 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 57 transitions. [2024-10-24 20:43:17,984 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 20:43:17,984 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 57 transitions. [2024-10-24 20:43:17,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-10-24 20:43:17,989 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:17,989 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:17,989 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-10-24 20:43:17,989 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting func_to_recursive_line_21_to_22_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:17,990 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:17,990 INFO L85 PathProgramCache]: Analyzing trace with hash -26304215, now seen corresponding path program 1 times [2024-10-24 20:43:17,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:17,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1369338623] [2024-10-24 20:43:17,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:17,990 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:18,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:18,123 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:18,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:18,168 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-10-24 20:43:18,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:18,172 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-24 20:43:18,172 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:18,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1369338623] [2024-10-24 20:43:18,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1369338623] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:18,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1615595690] [2024-10-24 20:43:18,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:18,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:18,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:18,175 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-10-24 20:43:18,176 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-10-24 20:43:18,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:18,265 INFO L255 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-24 20:43:18,267 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:18,279 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-10-24 20:43:18,344 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-24 20:43:18,344 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 20:43:18,345 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1615595690] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:18,348 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 20:43:18,348 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 9 [2024-10-24 20:43:18,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [696597784] [2024-10-24 20:43:18,349 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:18,349 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 20:43:18,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:18,350 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 20:43:18,350 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-10-24 20:43:18,350 INFO L87 Difference]: Start difference. First operand 49 states and 57 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 20:43:18,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:18,442 INFO L93 Difference]: Finished difference Result 93 states and 107 transitions. [2024-10-24 20:43:18,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 20:43:18,442 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2024-10-24 20:43:18,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:18,443 INFO L225 Difference]: With dead ends: 93 [2024-10-24 20:43:18,443 INFO L226 Difference]: Without dead ends: 47 [2024-10-24 20:43:18,444 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-10-24 20:43:18,445 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 13 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:18,445 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 57 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:18,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-10-24 20:43:18,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2024-10-24 20:43:18,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 34 states have internal predecessors, (37), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2024-10-24 20:43:18,452 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 53 transitions. [2024-10-24 20:43:18,453 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 53 transitions. Word has length 22 [2024-10-24 20:43:18,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:18,453 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 53 transitions. [2024-10-24 20:43:18,453 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 20:43:18,453 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 53 transitions. [2024-10-24 20:43:18,454 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-24 20:43:18,455 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:18,455 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:18,472 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-24 20:43:18,655 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-10-24 20:43:18,656 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting func_to_recursive_line_22_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:18,656 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:18,656 INFO L85 PathProgramCache]: Analyzing trace with hash -1958164554, now seen corresponding path program 1 times [2024-10-24 20:43:18,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:18,657 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346050585] [2024-10-24 20:43:18,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:18,657 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:18,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:18,888 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 20:43:18,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:19,047 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:19,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:19,092 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-24 20:43:19,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:19,099 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:19,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:19,103 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 3 proven. 18 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-10-24 20:43:19,103 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:19,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [346050585] [2024-10-24 20:43:19,103 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [346050585] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:19,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1806878184] [2024-10-24 20:43:19,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:19,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:19,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:19,107 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-10-24 20:43:19,108 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-10-24 20:43:19,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:19,198 INFO L255 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-24 20:43:19,201 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:19,209 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-10-24 20:43:19,414 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 22 proven. 3 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-24 20:43:19,415 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 20:43:19,829 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 22 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-24 20:43:19,829 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1806878184] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 20:43:19,829 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 20:43:19,829 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 11] total 24 [2024-10-24 20:43:19,829 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1690859114] [2024-10-24 20:43:19,829 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 20:43:19,830 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-10-24 20:43:19,830 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:19,830 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-24 20:43:19,831 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=445, Unknown=0, NotChecked=0, Total=552 [2024-10-24 20:43:19,831 INFO L87 Difference]: Start difference. First operand 47 states and 53 transitions. Second operand has 24 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 21 states have internal predecessors, (46), 7 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) [2024-10-24 20:43:20,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:20,066 INFO L93 Difference]: Finished difference Result 93 states and 111 transitions. [2024-10-24 20:43:20,066 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-24 20:43:20,066 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 21 states have internal predecessors, (46), 7 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) Word has length 39 [2024-10-24 20:43:20,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:20,067 INFO L225 Difference]: With dead ends: 93 [2024-10-24 20:43:20,067 INFO L226 Difference]: Without dead ends: 51 [2024-10-24 20:43:20,068 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 181 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=163, Invalid=649, Unknown=0, NotChecked=0, Total=812 [2024-10-24 20:43:20,068 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 17 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 206 SdHoareTripleChecker+Invalid, 161 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:20,069 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 206 Invalid, 161 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:20,069 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-10-24 20:43:20,074 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2024-10-24 20:43:20,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 33 states have (on average 1.1818181818181819) internal successors, (39), 36 states have internal predecessors, (39), 8 states have call successors, (8), 6 states have call predecessors, (8), 6 states have return successors, (10), 8 states have call predecessors, (10), 6 states have call successors, (10) [2024-10-24 20:43:20,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2024-10-24 20:43:20,075 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 39 [2024-10-24 20:43:20,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:20,075 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2024-10-24 20:43:20,075 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 21 states have internal predecessors, (46), 7 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) [2024-10-24 20:43:20,076 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2024-10-24 20:43:20,077 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-10-24 20:43:20,077 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:20,077 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:20,096 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-10-24 20:43:20,277 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:20,278 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting func_to_recursive_line_22_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:20,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:20,278 INFO L85 PathProgramCache]: Analyzing trace with hash 909113838, now seen corresponding path program 2 times [2024-10-24 20:43:20,279 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:20,279 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [80521138] [2024-10-24 20:43:20,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:20,279 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:20,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:20,732 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 20:43:20,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:20,939 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:20,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,097 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:21,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,177 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:21,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,224 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-10-24 20:43:21,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,246 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:21,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,256 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:21,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,260 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:21,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:21,264 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 11 proven. 90 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-10-24 20:43:21,264 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:21,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [80521138] [2024-10-24 20:43:21,265 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [80521138] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:21,265 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [956345133] [2024-10-24 20:43:21,265 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 20:43:21,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:21,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:21,267 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-10-24 20:43:21,268 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-10-24 20:43:21,389 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 20:43:21,390 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 20:43:21,396 INFO L255 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 20:43:21,401 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:21,432 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-10-24 20:43:21,644 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-10-24 20:43:21,665 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 96 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-10-24 20:43:21,665 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 20:43:21,665 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [956345133] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:21,665 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 20:43:21,666 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [15] total 20 [2024-10-24 20:43:21,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [139952746] [2024-10-24 20:43:21,666 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:21,666 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 20:43:21,666 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:21,667 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 20:43:21,667 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=323, Unknown=0, NotChecked=0, Total=380 [2024-10-24 20:43:21,667 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand has 7 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-24 20:43:21,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:21,811 INFO L93 Difference]: Finished difference Result 54 states and 65 transitions. [2024-10-24 20:43:21,811 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 20:43:21,811 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 67 [2024-10-24 20:43:21,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:21,813 INFO L225 Difference]: With dead ends: 54 [2024-10-24 20:43:21,815 INFO L226 Difference]: Without dead ends: 53 [2024-10-24 20:43:21,816 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 78 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=75, Invalid=431, Unknown=0, NotChecked=0, Total=506 [2024-10-24 20:43:21,816 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 34 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:21,817 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 84 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:21,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-10-24 20:43:21,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 50. [2024-10-24 20:43:21,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 35 states have internal predecessors, (38), 8 states have call successors, (8), 6 states have call predecessors, (8), 6 states have return successors, (10), 8 states have call predecessors, (10), 6 states have call successors, (10) [2024-10-24 20:43:21,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 56 transitions. [2024-10-24 20:43:21,835 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 56 transitions. Word has length 67 [2024-10-24 20:43:21,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:21,836 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 56 transitions. [2024-10-24 20:43:21,836 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-24 20:43:21,836 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 56 transitions. [2024-10-24 20:43:21,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-10-24 20:43:21,840 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:21,841 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:21,859 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-10-24 20:43:22,041 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:22,041 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting func_to_recursive_line_22_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:22,042 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:22,042 INFO L85 PathProgramCache]: Analyzing trace with hash -1882242042, now seen corresponding path program 1 times [2024-10-24 20:43:22,042 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:22,042 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2068862253] [2024-10-24 20:43:22,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:22,042 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:22,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,321 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-24 20:43:22,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,332 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:22,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,337 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:22,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,341 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:22,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,343 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-10-24 20:43:22,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,352 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:22,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:22,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:22,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,380 INFO L134 CoverageAnalysis]: Checked inductivity of 163 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2024-10-24 20:43:22,384 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:22,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2068862253] [2024-10-24 20:43:22,385 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2068862253] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:22,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1971890336] [2024-10-24 20:43:22,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:22,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:22,385 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:22,387 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-10-24 20:43:22,398 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-10-24 20:43:22,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:22,513 INFO L255 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-24 20:43:22,515 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:22,684 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-10-24 20:43:22,698 INFO L134 CoverageAnalysis]: Checked inductivity of 163 backedges. 96 proven. 0 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-10-24 20:43:22,699 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 20:43:22,699 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1971890336] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:22,699 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 20:43:22,700 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 13 [2024-10-24 20:43:22,700 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1340973393] [2024-10-24 20:43:22,700 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:22,700 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 20:43:22,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:22,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 20:43:22,702 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-10-24 20:43:22,702 INFO L87 Difference]: Start difference. First operand 50 states and 56 transitions. Second operand has 6 states, 5 states have (on average 5.0) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-24 20:43:26,775 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-10-24 20:43:26,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:26,790 INFO L93 Difference]: Finished difference Result 50 states and 56 transitions. [2024-10-24 20:43:26,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 20:43:26,791 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.0) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 68 [2024-10-24 20:43:26,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:26,792 INFO L225 Difference]: With dead ends: 50 [2024-10-24 20:43:26,793 INFO L226 Difference]: Without dead ends: 49 [2024-10-24 20:43:26,793 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=193, Unknown=0, NotChecked=0, Total=240 [2024-10-24 20:43:26,793 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 4 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:26,794 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 94 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2024-10-24 20:43:26,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-24 20:43:26,804 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 45. [2024-10-24 20:43:26,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 7 states have call successors, (7), 6 states have call predecessors, (7), 6 states have return successors, (9), 7 states have call predecessors, (9), 5 states have call successors, (9) [2024-10-24 20:43:26,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 50 transitions. [2024-10-24 20:43:26,805 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 50 transitions. Word has length 68 [2024-10-24 20:43:26,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:26,805 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 50 transitions. [2024-10-24 20:43:26,806 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.0) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-24 20:43:26,806 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 50 transitions. [2024-10-24 20:43:26,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-10-24 20:43:26,807 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:26,807 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 6, 6, 6, 6, 6, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:26,822 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-10-24 20:43:27,007 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-10-24 20:43:27,008 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting func_to_recursive_line_21_to_22_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:27,009 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:27,009 INFO L85 PathProgramCache]: Analyzing trace with hash -209581975, now seen corresponding path program 1 times [2024-10-24 20:43:27,009 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:27,009 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1256839900] [2024-10-24 20:43:27,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:27,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:27,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,243 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,443 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:27,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,629 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,796 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,897 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,941 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-10-24 20:43:27,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,944 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-10-24 20:43:27,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,960 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:27,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,975 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,981 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,985 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:27,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,987 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-10-24 20:43:27,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:27,989 INFO L134 CoverageAnalysis]: Checked inductivity of 191 backedges. 13 proven. 99 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2024-10-24 20:43:27,993 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:27,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1256839900] [2024-10-24 20:43:27,993 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1256839900] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:27,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [905370382] [2024-10-24 20:43:27,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:27,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:27,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:27,998 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-10-24 20:43:28,001 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-10-24 20:43:28,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:28,131 INFO L255 TraceCheckSpWp]: Trace formula consists of 440 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-10-24 20:43:28,135 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:28,142 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-10-24 20:43:28,374 INFO L134 CoverageAnalysis]: Checked inductivity of 191 backedges. 115 proven. 3 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2024-10-24 20:43:28,376 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 20:43:28,923 INFO L134 CoverageAnalysis]: Checked inductivity of 191 backedges. 3 proven. 25 refuted. 0 times theorem prover too weak. 163 trivial. 0 not checked. [2024-10-24 20:43:28,924 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [905370382] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 20:43:28,924 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 20:43:28,924 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 10, 11] total 33 [2024-10-24 20:43:28,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [742717513] [2024-10-24 20:43:28,924 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 20:43:28,925 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-10-24 20:43:28,925 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:28,926 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-10-24 20:43:28,926 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=923, Unknown=0, NotChecked=0, Total=1056 [2024-10-24 20:43:28,927 INFO L87 Difference]: Start difference. First operand 45 states and 50 transitions. Second operand has 33 states, 26 states have (on average 2.730769230769231) internal successors, (71), 28 states have internal predecessors, (71), 11 states have call successors, (25), 7 states have call predecessors, (25), 10 states have return successors, (20), 9 states have call predecessors, (20), 11 states have call successors, (20) [2024-10-24 20:43:29,497 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:29,498 INFO L93 Difference]: Finished difference Result 89 states and 104 transitions. [2024-10-24 20:43:29,498 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-24 20:43:29,499 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 26 states have (on average 2.730769230769231) internal successors, (71), 28 states have internal predecessors, (71), 11 states have call successors, (25), 7 states have call predecessors, (25), 10 states have return successors, (20), 9 states have call predecessors, (20), 11 states have call successors, (20) Word has length 90 [2024-10-24 20:43:29,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:29,500 INFO L225 Difference]: With dead ends: 89 [2024-10-24 20:43:29,500 INFO L226 Difference]: Without dead ends: 49 [2024-10-24 20:43:29,501 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 186 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 457 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=269, Invalid=1711, Unknown=0, NotChecked=0, Total=1980 [2024-10-24 20:43:29,501 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 38 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 371 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 393 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 371 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:29,502 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 146 Invalid, 393 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 371 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 20:43:29,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-24 20:43:29,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2024-10-24 20:43:29,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 32 states have (on average 1.125) internal successors, (36), 33 states have internal predecessors, (36), 7 states have call successors, (7), 6 states have call predecessors, (7), 8 states have return successors, (11), 9 states have call predecessors, (11), 5 states have call successors, (11) [2024-10-24 20:43:29,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2024-10-24 20:43:29,532 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 90 [2024-10-24 20:43:29,532 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:29,533 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2024-10-24 20:43:29,534 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 26 states have (on average 2.730769230769231) internal successors, (71), 28 states have internal predecessors, (71), 11 states have call successors, (25), 7 states have call predecessors, (25), 10 states have return successors, (20), 9 states have call predecessors, (20), 11 states have call successors, (20) [2024-10-24 20:43:29,534 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2024-10-24 20:43:29,536 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 187 [2024-10-24 20:43:29,536 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:29,537 INFO L215 NwaCegarLoop]: trace histogram [20, 20, 16, 16, 16, 16, 16, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:29,559 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-24 20:43:29,737 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:29,738 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting func_to_recursive_line_21_to_22_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:29,738 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:29,738 INFO L85 PathProgramCache]: Analyzing trace with hash -1245795159, now seen corresponding path program 2 times [2024-10-24 20:43:29,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:29,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [976703569] [2024-10-24 20:43:29,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:29,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:29,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,273 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,307 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:30,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,314 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,320 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,323 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,325 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,329 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,331 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:30,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,343 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:30,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,350 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,356 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,360 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,368 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:30,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-10-24 20:43:30,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:30,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,404 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,410 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,417 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,421 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,423 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:30,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,439 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:30,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,448 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,454 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,460 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,464 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:30,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,467 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:30,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:30,470 INFO L134 CoverageAnalysis]: Checked inductivity of 1215 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1210 trivial. 0 not checked. [2024-10-24 20:43:30,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:30,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [976703569] [2024-10-24 20:43:30,472 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [976703569] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:30,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1427173394] [2024-10-24 20:43:30,472 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 20:43:30,472 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:30,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:30,474 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-10-24 20:43:30,476 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-10-24 20:43:30,671 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 20:43:30,671 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 20:43:30,675 INFO L255 TraceCheckSpWp]: Trace formula consists of 774 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-10-24 20:43:30,682 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:30,710 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-10-24 20:43:31,003 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-10-24 20:43:31,024 INFO L134 CoverageAnalysis]: Checked inductivity of 1215 backedges. 653 proven. 0 refuted. 0 times theorem prover too weak. 562 trivial. 0 not checked. [2024-10-24 20:43:31,024 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 20:43:31,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1427173394] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:31,024 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 20:43:31,025 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [10] total 15 [2024-10-24 20:43:31,025 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [186602358] [2024-10-24 20:43:31,025 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:31,025 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 20:43:31,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:31,026 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 20:43:31,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2024-10-24 20:43:31,027 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand has 7 states, 6 states have (on average 6.0) internal successors, (36), 6 states have internal predecessors, (36), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-24 20:43:31,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:31,140 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2024-10-24 20:43:31,140 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 20:43:31,141 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 6.0) internal successors, (36), 6 states have internal predecessors, (36), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 186 [2024-10-24 20:43:31,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:31,142 INFO L225 Difference]: With dead ends: 50 [2024-10-24 20:43:31,142 INFO L226 Difference]: Without dead ends: 49 [2024-10-24 20:43:31,142 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 232 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=64, Invalid=278, Unknown=0, NotChecked=0, Total=342 [2024-10-24 20:43:31,143 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 16 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:31,143 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 84 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 20:43:31,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-24 20:43:31,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2024-10-24 20:43:31,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 32 states have (on average 1.09375) internal successors, (35), 32 states have internal predecessors, (35), 7 states have call successors, (7), 6 states have call predecessors, (7), 8 states have return successors, (11), 9 states have call predecessors, (11), 5 states have call successors, (11) [2024-10-24 20:43:31,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 53 transitions. [2024-10-24 20:43:31,156 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 53 transitions. Word has length 186 [2024-10-24 20:43:31,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:31,158 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 53 transitions. [2024-10-24 20:43:31,158 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 6.0) internal successors, (36), 6 states have internal predecessors, (36), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-24 20:43:31,158 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 53 transitions. [2024-10-24 20:43:31,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 188 [2024-10-24 20:43:31,162 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 20:43:31,162 INFO L215 NwaCegarLoop]: trace histogram [20, 20, 16, 16, 16, 16, 16, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-10-24 20:43:31,181 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-24 20:43:31,366 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:31,367 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting func_to_recursive_line_21_to_22_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW, func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (and 4 more)] === [2024-10-24 20:43:31,367 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 20:43:31,367 INFO L85 PathProgramCache]: Analyzing trace with hash 35055832, now seen corresponding path program 1 times [2024-10-24 20:43:31,367 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 20:43:31,367 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1815642719] [2024-10-24 20:43:31,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:31,367 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 20:43:31,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,824 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,855 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:31,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,861 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,867 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,871 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,874 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,876 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:31,880 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,885 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:31,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,891 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,897 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,901 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,904 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,905 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:31,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,907 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-10-24 20:43:31,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,933 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:31,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,942 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,948 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,956 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,959 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:31,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,968 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 20:43:31,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:31,976 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:31,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:32,004 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:32,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:32,011 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:32,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:32,014 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 20:43:32,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:32,016 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-24 20:43:32,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:32,019 INFO L134 CoverageAnalysis]: Checked inductivity of 1216 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1210 trivial. 0 not checked. [2024-10-24 20:43:32,019 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 20:43:32,019 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1815642719] [2024-10-24 20:43:32,020 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1815642719] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 20:43:32,020 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [147320465] [2024-10-24 20:43:32,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 20:43:32,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 20:43:32,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 20:43:32,022 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-10-24 20:43:32,023 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-10-24 20:43:32,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 20:43:32,236 INFO L255 TraceCheckSpWp]: Trace formula consists of 775 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-24 20:43:32,240 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 20:43:32,508 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-10-24 20:43:32,522 INFO L134 CoverageAnalysis]: Checked inductivity of 1216 backedges. 653 proven. 0 refuted. 0 times theorem prover too weak. 563 trivial. 0 not checked. [2024-10-24 20:43:32,523 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 20:43:32,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [147320465] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 20:43:32,523 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 20:43:32,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 14 [2024-10-24 20:43:32,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1250160568] [2024-10-24 20:43:32,524 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 20:43:32,524 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 20:43:32,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 20:43:32,525 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 20:43:32,525 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=169, Unknown=0, NotChecked=0, Total=210 [2024-10-24 20:43:32,525 INFO L87 Difference]: Start difference. First operand 48 states and 53 transitions. Second operand has 6 states, 5 states have (on average 7.4) internal successors, (37), 6 states have internal predecessors, (37), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-24 20:43:32,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 20:43:32,591 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2024-10-24 20:43:32,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 20:43:32,591 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 7.4) internal successors, (37), 6 states have internal predecessors, (37), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 187 [2024-10-24 20:43:32,591 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 20:43:32,592 INFO L225 Difference]: With dead ends: 48 [2024-10-24 20:43:32,592 INFO L226 Difference]: Without dead ends: 0 [2024-10-24 20:43:32,592 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 248 GetRequests, 232 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2024-10-24 20:43:32,593 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 72 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 20:43:32,594 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 72 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 20:43:32,594 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-10-24 20:43:32,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-10-24 20:43:32,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 20:43:32,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-10-24 20:43:32,594 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 187 [2024-10-24 20:43:32,594 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 20:43:32,594 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-24 20:43:32,595 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 7.4) internal successors, (37), 6 states have internal predecessors, (37), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-24 20:43:32,595 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-10-24 20:43:32,595 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-10-24 20:43:32,598 INFO L782 garLoopResultBuilder]: Registering result SAFE for location func_to_recursive_line_23_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW (5 of 6 remaining) [2024-10-24 20:43:32,599 INFO L782 garLoopResultBuilder]: Registering result SAFE for location func_to_recursive_line_23_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (4 of 6 remaining) [2024-10-24 20:43:32,599 INFO L782 garLoopResultBuilder]: Registering result SAFE for location func_to_recursive_line_22_to_23_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW (3 of 6 remaining) [2024-10-24 20:43:32,599 INFO L782 garLoopResultBuilder]: Registering result SAFE for location func_to_recursive_line_22_to_23_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (2 of 6 remaining) [2024-10-24 20:43:32,599 INFO L782 garLoopResultBuilder]: Registering result SAFE for location func_to_recursive_line_21_to_22_0Err0ASSERT_VIOLATIONINTEGER_OVERFLOW (1 of 6 remaining) [2024-10-24 20:43:32,600 INFO L782 garLoopResultBuilder]: Registering result SAFE for location func_to_recursive_line_21_to_22_0Err1ASSERT_VIOLATIONINTEGER_OVERFLOW (0 of 6 remaining) [2024-10-24 20:43:32,618 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-24 20:43:32,800 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,SelfDestructingSolverStorable12 [2024-10-24 20:43:32,803 INFO L407 BasicCegarLoop]: Path program histogram: [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 20:43:32,805 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-10-24 20:43:41,175 WARN L286 SmtUtils]: Spent 8.14s on a formula simplification. DAG size of input: 112 DAG size of output: 40 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-10-24 20:44:05,364 WARN L286 SmtUtils]: Spent 24.11s on a formula simplification. DAG size of input: 72 DAG size of output: 42 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-10-24 20:44:37,730 WARN L286 SmtUtils]: Spent 32.14s on a formula simplification. DAG size of input: 88 DAG size of output: 58 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter)