./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_loop-simple/recursified_nested_2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_loop-simple/recursified_nested_2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-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 ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 1a590e2514668f126114e4312bb6236a04cce9502b393533b5b4bfd230be904b --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 14:28:15,847 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 14:28:15,921 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 14:28:15,925 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 14:28:15,926 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 14:28:15,964 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 14:28:15,965 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 14:28:15,966 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 14:28:15,966 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 14:28:15,967 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 14:28:15,967 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 14:28:15,967 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 14:28:15,968 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 14:28:15,968 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 14:28:15,969 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 14:28:15,971 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 14:28:15,971 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 14:28:15,974 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 14:28:15,974 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 14:28:15,975 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 14:28:15,975 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 14:28:15,975 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 14:28:15,976 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 14:28:15,976 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 14:28:15,976 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 14:28:15,976 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 14:28:15,977 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 14:28:15,977 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 14:28:15,977 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 14:28:15,978 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 14:28:15,978 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 14:28:15,978 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 14:28:15,978 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 14:28:15,979 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 14:28:15,979 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 14:28:15,981 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 14:28:15,981 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 14:28:15,982 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 14:28:15,982 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 14:28:15,982 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 14:28:15,982 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 14:28:15,983 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 14:28:15,984 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 ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 1a590e2514668f126114e4312bb6236a04cce9502b393533b5b4bfd230be904b [2024-11-18 14:28:16,256 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 14:28:16,284 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 14:28:16,288 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 14:28:16,290 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 14:28:16,290 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 14:28:16,291 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_loop-simple/recursified_nested_2.c [2024-11-18 14:28:17,719 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 14:28:17,975 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 14:28:17,976 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_2.c [2024-11-18 14:28:17,983 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6035b6bac/6164a29c51cd4b61b41918b719e89afb/FLAGfaa0e4031 [2024-11-18 14:28:17,995 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6035b6bac/6164a29c51cd4b61b41918b719e89afb [2024-11-18 14:28:17,998 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 14:28:17,999 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 14:28:18,001 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 14:28:18,001 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 14:28:18,007 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 14:28:18,008 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 02:28:17" (1/1) ... [2024-11-18 14:28:18,009 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@10d17e5c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18, skipping insertion in model container [2024-11-18 14:28:18,009 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 02:28:17" (1/1) ... [2024-11-18 14:28:18,030 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 14:28:18,188 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_2.c[1611,1624] [2024-11-18 14:28:18,194 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 14:28:18,204 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 14:28:18,220 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_nested_2.c[1611,1624] [2024-11-18 14:28:18,221 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 14:28:18,236 INFO L204 MainTranslator]: Completed translation [2024-11-18 14:28:18,236 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18 WrapperNode [2024-11-18 14:28:18,237 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 14:28:18,238 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 14:28:18,238 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 14:28:18,238 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 14:28:18,244 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,250 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,264 INFO L138 Inliner]: procedures = 13, calls = 29, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 38 [2024-11-18 14:28:18,265 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 14:28:18,265 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 14:28:18,265 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 14:28:18,266 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 14:28:18,273 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,274 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,275 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,289 INFO L175 MemorySlicer]: Split 14 memory accesses to 3 slices as follows [2, 6, 6]. 43 percent of accesses are in the largest equivalence class. The 4 initializations are split as follows [2, 1, 1]. The 4 writes are split as follows [0, 2, 2]. [2024-11-18 14:28:18,289 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,289 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,294 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,296 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,301 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,302 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,304 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 14:28:18,305 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 14:28:18,305 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 14:28:18,305 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 14:28:18,306 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (1/1) ... [2024-11-18 14:28:18,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 14:28:18,323 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:18,341 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-18 14:28:18,348 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-18 14:28:18,397 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 14:28:18,398 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 14:28:18,398 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-18 14:28:18,398 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-18 14:28:18,398 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-18 14:28:18,398 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-18 14:28:18,399 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-18 14:28:18,399 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-18 14:28:18,400 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_20_to_21_0 [2024-11-18 14:28:18,401 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_20_to_21_0 [2024-11-18 14:28:18,401 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 14:28:18,401 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 14:28:18,401 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-18 14:28:18,401 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-18 14:28:18,401 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-18 14:28:18,402 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_21_to_21_0 [2024-11-18 14:28:18,403 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_21_to_21_0 [2024-11-18 14:28:18,403 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-18 14:28:18,490 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 14:28:18,493 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 14:28:18,674 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-18 14:28:18,674 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 14:28:18,690 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 14:28:18,690 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-18 14:28:18,690 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:28:18 BoogieIcfgContainer [2024-11-18 14:28:18,690 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 14:28:18,692 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 14:28:18,692 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 14:28:18,696 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 14:28:18,697 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 02:28:17" (1/3) ... [2024-11-18 14:28:18,698 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3df1eb61 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 02:28:18, skipping insertion in model container [2024-11-18 14:28:18,698 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:28:18" (2/3) ... [2024-11-18 14:28:18,699 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3df1eb61 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 02:28:18, skipping insertion in model container [2024-11-18 14:28:18,699 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:28:18" (3/3) ... [2024-11-18 14:28:18,700 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_nested_2.c [2024-11-18 14:28:18,717 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 14:28:18,717 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 14:28:18,787 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 14:28:18,796 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;@7bf2251d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 14:28:18,797 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 14:28:18,801 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 16 states have (on average 1.3125) internal successors, (21), 19 states have internal predecessors, (21), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-18 14:28:18,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-18 14:28:18,809 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:18,809 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:18,810 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:18,814 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:18,814 INFO L85 PathProgramCache]: Analyzing trace with hash -927054850, now seen corresponding path program 1 times [2024-11-18 14:28:18,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:18,824 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [800578477] [2024-11-18 14:28:18,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:28:18,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:18,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:28:19,366 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 14:28:19,366 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:19,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [800578477] [2024-11-18 14:28:19,367 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [800578477] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 14:28:19,367 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 14:28:19,367 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-18 14:28:19,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [190870138] [2024-11-18 14:28:19,369 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 14:28:19,373 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 14:28:19,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:19,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 14:28:19,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-18 14:28:19,400 INFO L87 Difference]: Start difference. First operand has 24 states, 16 states have (on average 1.3125) internal successors, (21), 19 states have internal predecessors, (21), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 6 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:28:19,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:19,539 INFO L93 Difference]: Finished difference Result 35 states and 42 transitions. [2024-11-18 14:28:19,541 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 14:28:19,542 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2024-11-18 14:28:19,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:19,550 INFO L225 Difference]: With dead ends: 35 [2024-11-18 14:28:19,550 INFO L226 Difference]: Without dead ends: 22 [2024-11-18 14:28:19,553 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-18 14:28:19,556 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 7 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:19,557 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 58 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:19,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-18 14:28:19,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-18 14:28:19,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 3 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-18 14:28:19,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 26 transitions. [2024-11-18 14:28:19,589 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 26 transitions. Word has length 11 [2024-11-18 14:28:19,589 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:19,589 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 26 transitions. [2024-11-18 14:28:19,590 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:28:19,590 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 26 transitions. [2024-11-18 14:28:19,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-18 14:28:19,591 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:19,591 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:19,592 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-18 14:28:19,592 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:19,592 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:19,592 INFO L85 PathProgramCache]: Analyzing trace with hash -1141956254, now seen corresponding path program 1 times [2024-11-18 14:28:19,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:19,593 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833459391] [2024-11-18 14:28:19,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:28:19,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:19,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:28:19,855 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-18 14:28:19,856 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:19,856 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833459391] [2024-11-18 14:28:19,856 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [833459391] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 14:28:19,856 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 14:28:19,857 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-18 14:28:19,857 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1280401793] [2024-11-18 14:28:19,857 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 14:28:19,859 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 14:28:19,860 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:19,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 14:28:19,861 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-18 14:28:19,861 INFO L87 Difference]: Start difference. First operand 22 states and 26 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-18 14:28:19,940 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:19,940 INFO L93 Difference]: Finished difference Result 43 states and 53 transitions. [2024-11-18 14:28:19,942 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 14:28:19,942 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), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) Word has length 22 [2024-11-18 14:28:19,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:19,943 INFO L225 Difference]: With dead ends: 43 [2024-11-18 14:28:19,943 INFO L226 Difference]: Without dead ends: 24 [2024-11-18 14:28:19,944 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-18 14:28:19,945 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 4 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:19,945 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 57 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:19,947 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-18 14:28:19,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-18 14:28:19,955 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 4 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-18 14:28:19,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 28 transitions. [2024-11-18 14:28:19,956 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 28 transitions. Word has length 22 [2024-11-18 14:28:19,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:19,957 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 28 transitions. [2024-11-18 14:28:19,957 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), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-18 14:28:19,957 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 28 transitions. [2024-11-18 14:28:19,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-18 14:28:19,958 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:19,958 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:19,958 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 14:28:19,959 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:19,959 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:19,959 INFO L85 PathProgramCache]: Analyzing trace with hash -1444799936, now seen corresponding path program 1 times [2024-11-18 14:28:19,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:19,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1747494581] [2024-11-18 14:28:19,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:28:19,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:19,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:28:20,363 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-18 14:28:20,363 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:20,363 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1747494581] [2024-11-18 14:28:20,363 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1747494581] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:20,364 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1409616616] [2024-11-18 14:28:20,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:28:20,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:20,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:20,367 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:20,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-18 14:28:20,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:28:20,490 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-18 14:28:20,506 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:20,612 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-18 14:28:20,875 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-18 14:28:20,876 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:21,292 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 14:28:21,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1409616616] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:28:21,293 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:28:21,293 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 10] total 24 [2024-11-18 14:28:21,293 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1596773673] [2024-11-18 14:28:21,294 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:21,294 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-18 14:28:21,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:21,296 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-18 14:28:21,296 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=466, Unknown=0, NotChecked=0, Total=552 [2024-11-18 14:28:21,297 INFO L87 Difference]: Start difference. First operand 24 states and 28 transitions. Second operand has 24 states, 18 states have (on average 2.111111111111111) internal successors, (38), 20 states have internal predecessors, (38), 10 states have call successors, (11), 5 states have call predecessors, (11), 8 states have return successors, (11), 7 states have call predecessors, (11), 10 states have call successors, (11) [2024-11-18 14:28:21,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:21,637 INFO L93 Difference]: Finished difference Result 49 states and 60 transitions. [2024-11-18 14:28:21,637 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-18 14:28:21,638 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 18 states have (on average 2.111111111111111) internal successors, (38), 20 states have internal predecessors, (38), 10 states have call successors, (11), 5 states have call predecessors, (11), 8 states have return successors, (11), 7 states have call predecessors, (11), 10 states have call successors, (11) Word has length 27 [2024-11-18 14:28:21,638 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:21,640 INFO L225 Difference]: With dead ends: 49 [2024-11-18 14:28:21,640 INFO L226 Difference]: Without dead ends: 28 [2024-11-18 14:28:21,641 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=178, Invalid=878, Unknown=0, NotChecked=0, Total=1056 [2024-11-18 14:28:21,642 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 25 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 198 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:21,642 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 105 Invalid, 198 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:21,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-18 14:28:21,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-18 14:28:21,652 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 6 states have return successors, (8), 6 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-18 14:28:21,653 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 32 transitions. [2024-11-18 14:28:21,653 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 32 transitions. Word has length 27 [2024-11-18 14:28:21,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:21,654 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 32 transitions. [2024-11-18 14:28:21,654 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 18 states have (on average 2.111111111111111) internal successors, (38), 20 states have internal predecessors, (38), 10 states have call successors, (11), 5 states have call predecessors, (11), 8 states have return successors, (11), 7 states have call predecessors, (11), 10 states have call successors, (11) [2024-11-18 14:28:21,654 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 32 transitions. [2024-11-18 14:28:21,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-11-18 14:28:21,656 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:21,656 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:21,674 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-18 14:28:21,860 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:21,861 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:21,861 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:21,862 INFO L85 PathProgramCache]: Analyzing trace with hash 211909574, now seen corresponding path program 2 times [2024-11-18 14:28:21,862 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:21,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2036388876] [2024-11-18 14:28:21,862 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:28:21,862 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:21,887 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:28:21,887 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:22,442 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 49 proven. 8 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 14:28:22,443 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:22,443 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2036388876] [2024-11-18 14:28:22,443 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2036388876] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:22,443 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1428622742] [2024-11-18 14:28:22,443 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:28:22,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:22,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:22,448 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:22,451 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-18 14:28:22,557 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:28:22,557 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:22,559 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-18 14:28:22,564 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:22,573 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-18 14:28:22,815 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 45 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-18 14:28:22,815 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:23,783 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 4 proven. 56 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-18 14:28:23,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1428622742] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:28:23,784 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:28:23,784 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10, 14] total 28 [2024-11-18 14:28:23,785 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [82758511] [2024-11-18 14:28:23,785 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:23,785 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-18 14:28:23,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:23,786 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-18 14:28:23,787 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=606, Unknown=0, NotChecked=0, Total=756 [2024-11-18 14:28:23,787 INFO L87 Difference]: Start difference. First operand 28 states and 32 transitions. Second operand has 28 states, 20 states have (on average 2.45) internal successors, (49), 24 states have internal predecessors, (49), 10 states have call successors, (16), 6 states have call predecessors, (16), 9 states have return successors, (18), 7 states have call predecessors, (18), 10 states have call successors, (18) [2024-11-18 14:28:24,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:24,046 INFO L93 Difference]: Finished difference Result 57 states and 69 transitions. [2024-11-18 14:28:24,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 14:28:24,047 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 20 states have (on average 2.45) internal successors, (49), 24 states have internal predecessors, (49), 10 states have call successors, (16), 6 states have call predecessors, (16), 9 states have return successors, (18), 7 states have call predecessors, (18), 10 states have call successors, (18) Word has length 53 [2024-11-18 14:28:24,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:24,048 INFO L225 Difference]: With dead ends: 57 [2024-11-18 14:28:24,048 INFO L226 Difference]: Without dead ends: 32 [2024-11-18 14:28:24,049 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 91 SyntacticMatches, 1 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 360 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=234, Invalid=888, Unknown=0, NotChecked=0, Total=1122 [2024-11-18 14:28:24,050 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 27 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 142 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:24,050 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 157 Invalid, 142 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 125 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:24,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-18 14:28:24,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-18 14:28:24,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 21 states have internal predecessors, (22), 4 states have call successors, (4), 2 states have call predecessors, (4), 8 states have return successors, (10), 8 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-18 14:28:24,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2024-11-18 14:28:24,059 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 53 [2024-11-18 14:28:24,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:24,059 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 36 transitions. [2024-11-18 14:28:24,059 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 20 states have (on average 2.45) internal successors, (49), 24 states have internal predecessors, (49), 10 states have call successors, (16), 6 states have call predecessors, (16), 9 states have return successors, (18), 7 states have call predecessors, (18), 10 states have call successors, (18) [2024-11-18 14:28:24,059 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 36 transitions. [2024-11-18 14:28:24,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-18 14:28:24,061 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:24,061 INFO L215 NwaCegarLoop]: trace histogram [10, 10, 8, 8, 8, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:24,079 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-18 14:28:24,262 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,SelfDestructingSolverStorable3 [2024-11-18 14:28:24,262 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:24,263 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:24,263 INFO L85 PathProgramCache]: Analyzing trace with hash -24620602, now seen corresponding path program 3 times [2024-11-18 14:28:24,263 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:24,263 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [769492019] [2024-11-18 14:28:24,263 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:28:24,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:24,294 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 14:28:24,294 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:24,715 INFO L134 CoverageAnalysis]: Checked inductivity of 223 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 211 trivial. 0 not checked. [2024-11-18 14:28:24,716 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:24,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [769492019] [2024-11-18 14:28:24,716 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [769492019] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:24,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [851506998] [2024-11-18 14:28:24,716 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:28:24,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:24,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:24,719 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:24,721 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-18 14:28:24,818 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 14:28:24,818 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:24,820 INFO L255 TraceCheckSpWp]: Trace formula consists of 200 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-18 14:28:24,825 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:24,831 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-18 14:28:25,058 INFO L134 CoverageAnalysis]: Checked inductivity of 223 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 215 trivial. 0 not checked. [2024-11-18 14:28:25,059 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:25,879 INFO L134 CoverageAnalysis]: Checked inductivity of 223 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 208 trivial. 0 not checked. [2024-11-18 14:28:25,880 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [851506998] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:28:25,880 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:28:25,880 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10, 14] total 29 [2024-11-18 14:28:25,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1123835548] [2024-11-18 14:28:25,880 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:25,881 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-18 14:28:25,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:25,882 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-18 14:28:25,883 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=653, Unknown=0, NotChecked=0, Total=812 [2024-11-18 14:28:25,883 INFO L87 Difference]: Start difference. First operand 32 states and 36 transitions. Second operand has 29 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 25 states have internal predecessors, (38), 13 states have call successors, (13), 5 states have call predecessors, (13), 8 states have return successors, (14), 11 states have call predecessors, (14), 13 states have call successors, (14) [2024-11-18 14:28:26,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:26,124 INFO L93 Difference]: Finished difference Result 41 states and 47 transitions. [2024-11-18 14:28:26,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-18 14:28:26,125 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 25 states have internal predecessors, (38), 13 states have call successors, (13), 5 states have call predecessors, (13), 8 states have return successors, (14), 11 states have call predecessors, (14), 13 states have call successors, (14) Word has length 73 [2024-11-18 14:28:26,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:26,126 INFO L225 Difference]: With dead ends: 41 [2024-11-18 14:28:26,127 INFO L226 Difference]: Without dead ends: 36 [2024-11-18 14:28:26,127 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 131 SyntacticMatches, 1 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=236, Invalid=886, Unknown=0, NotChecked=0, Total=1122 [2024-11-18 14:28:26,128 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 21 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 221 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:26,128 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 130 Invalid, 221 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 212 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:26,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-18 14:28:26,134 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2024-11-18 14:28:26,135 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 23 states have internal predecessors, (24), 4 states have call successors, (4), 2 states have call predecessors, (4), 10 states have return successors, (12), 10 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-18 14:28:26,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 40 transitions. [2024-11-18 14:28:26,136 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 40 transitions. Word has length 73 [2024-11-18 14:28:26,136 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:26,136 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 40 transitions. [2024-11-18 14:28:26,136 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 25 states have internal predecessors, (38), 13 states have call successors, (13), 5 states have call predecessors, (13), 8 states have return successors, (14), 11 states have call predecessors, (14), 13 states have call successors, (14) [2024-11-18 14:28:26,137 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 40 transitions. [2024-11-18 14:28:26,138 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2024-11-18 14:28:26,138 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:26,138 INFO L215 NwaCegarLoop]: trace histogram [20, 20, 16, 16, 16, 5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:26,155 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-18 14:28:26,342 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:26,343 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:26,343 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:26,343 INFO L85 PathProgramCache]: Analyzing trace with hash -1268827250, now seen corresponding path program 4 times [2024-11-18 14:28:26,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:26,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [652790482] [2024-11-18 14:28:26,343 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 14:28:26,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:26,375 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 14:28:26,375 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:27,458 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 137 proven. 262 refuted. 0 times theorem prover too weak. 539 trivial. 0 not checked. [2024-11-18 14:28:27,458 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:27,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [652790482] [2024-11-18 14:28:27,458 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [652790482] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:27,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1857270662] [2024-11-18 14:28:27,459 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 14:28:27,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:27,459 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:27,461 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:27,462 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-18 14:28:27,624 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 14:28:27,624 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:27,628 INFO L255 TraceCheckSpWp]: Trace formula consists of 562 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-11-18 14:28:27,635 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:27,641 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-18 14:28:27,962 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 359 proven. 24 refuted. 0 times theorem prover too weak. 555 trivial. 0 not checked. [2024-11-18 14:28:27,962 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:30,196 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 8 proven. 403 refuted. 0 times theorem prover too weak. 527 trivial. 0 not checked. [2024-11-18 14:28:30,197 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1857270662] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:28:30,197 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:28:30,197 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 22] total 38 [2024-11-18 14:28:30,197 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2061712883] [2024-11-18 14:28:30,197 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:30,198 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2024-11-18 14:28:30,198 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:30,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2024-11-18 14:28:30,200 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=275, Invalid=1131, Unknown=0, NotChecked=0, Total=1406 [2024-11-18 14:28:30,200 INFO L87 Difference]: Start difference. First operand 36 states and 40 transitions. Second operand has 38 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 32 states have internal predecessors, (57), 12 states have call successors, (18), 8 states have call predecessors, (18), 13 states have return successors, (24), 11 states have call predecessors, (24), 12 states have call successors, (24) [2024-11-18 14:28:30,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:30,507 INFO L93 Difference]: Finished difference Result 73 states and 87 transitions. [2024-11-18 14:28:30,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 14:28:30,508 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 32 states have internal predecessors, (57), 12 states have call successors, (18), 8 states have call predecessors, (18), 13 states have return successors, (24), 11 states have call predecessors, (24), 12 states have call successors, (24) Word has length 135 [2024-11-18 14:28:30,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:30,509 INFO L225 Difference]: With dead ends: 73 [2024-11-18 14:28:30,511 INFO L226 Difference]: Without dead ends: 40 [2024-11-18 14:28:30,513 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 298 GetRequests, 251 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 770 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=429, Invalid=1641, Unknown=0, NotChecked=0, Total=2070 [2024-11-18 14:28:30,514 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 21 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 224 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 270 SdHoareTripleChecker+Invalid, 242 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 224 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:30,516 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 270 Invalid, 242 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 224 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:30,516 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-11-18 14:28:30,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2024-11-18 14:28:30,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 25 states have internal predecessors, (26), 4 states have call successors, (4), 2 states have call predecessors, (4), 12 states have return successors, (14), 12 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-18 14:28:30,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 44 transitions. [2024-11-18 14:28:30,529 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 44 transitions. Word has length 135 [2024-11-18 14:28:30,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:30,529 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 44 transitions. [2024-11-18 14:28:30,530 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 32 states have internal predecessors, (57), 12 states have call successors, (18), 8 states have call predecessors, (18), 13 states have return successors, (24), 11 states have call predecessors, (24), 12 states have call successors, (24) [2024-11-18 14:28:30,530 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 44 transitions. [2024-11-18 14:28:30,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 176 [2024-11-18 14:28:30,535 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:30,535 INFO L215 NwaCegarLoop]: trace histogram [28, 28, 24, 24, 24, 5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:30,553 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-18 14:28:30,736 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:30,736 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:30,736 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:30,737 INFO L85 PathProgramCache]: Analyzing trace with hash 1558738830, now seen corresponding path program 5 times [2024-11-18 14:28:30,737 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:30,737 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [935483995] [2024-11-18 14:28:30,737 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 14:28:30,737 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:30,877 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) [2024-11-18 14:28:30,877 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:32,154 INFO L134 CoverageAnalysis]: Checked inductivity of 1846 backedges. 11 proven. 27 refuted. 0 times theorem prover too weak. 1808 trivial. 0 not checked. [2024-11-18 14:28:32,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:32,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [935483995] [2024-11-18 14:28:32,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [935483995] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:32,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [822485928] [2024-11-18 14:28:32,155 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 14:28:32,155 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:32,155 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:32,156 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:32,157 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-18 14:28:32,904 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) [2024-11-18 14:28:32,905 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:32,911 INFO L255 TraceCheckSpWp]: Trace formula consists of 733 conjuncts, 62 conjuncts are in the unsatisfiable core [2024-11-18 14:28:32,918 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:32,927 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-18 14:28:33,184 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 36 treesize of output 13 [2024-11-18 14:28:33,215 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-18 14:28:33,222 INFO L134 CoverageAnalysis]: Checked inductivity of 1846 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 1819 trivial. 0 not checked. [2024-11-18 14:28:33,222 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:33,876 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [822485928] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:33,877 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 14:28:33,877 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12] total 23 [2024-11-18 14:28:33,877 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1419601229] [2024-11-18 14:28:33,877 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:33,880 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-18 14:28:33,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:33,881 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-18 14:28:33,882 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=170, Invalid=532, Unknown=0, NotChecked=0, Total=702 [2024-11-18 14:28:33,882 INFO L87 Difference]: Start difference. First operand 40 states and 44 transitions. Second operand has 23 states, 17 states have (on average 2.0) internal successors, (34), 21 states have internal predecessors, (34), 10 states have call successors, (10), 2 states have call predecessors, (10), 10 states have return successors, (13), 13 states have call predecessors, (13), 10 states have call successors, (13) [2024-11-18 14:28:34,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:34,006 INFO L93 Difference]: Finished difference Result 51 states and 57 transitions. [2024-11-18 14:28:34,007 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 14:28:34,007 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 17 states have (on average 2.0) internal successors, (34), 21 states have internal predecessors, (34), 10 states have call successors, (10), 2 states have call predecessors, (10), 10 states have return successors, (13), 13 states have call predecessors, (13), 10 states have call successors, (13) Word has length 175 [2024-11-18 14:28:34,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:34,009 INFO L225 Difference]: With dead ends: 51 [2024-11-18 14:28:34,009 INFO L226 Difference]: Without dead ends: 48 [2024-11-18 14:28:34,009 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 182 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 273 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=178, Invalid=578, Unknown=0, NotChecked=0, Total=756 [2024-11-18 14:28:34,010 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 29 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 142 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:34,010 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 50 Invalid, 142 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:34,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-18 14:28:34,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 46. [2024-11-18 14:28:34,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 27 states have (on average 1.1111111111111112) internal successors, (30), 28 states have internal predecessors, (30), 4 states have call successors, (4), 2 states have call predecessors, (4), 14 states have return successors, (18), 15 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-18 14:28:34,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 52 transitions. [2024-11-18 14:28:34,018 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 52 transitions. Word has length 175 [2024-11-18 14:28:34,019 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:34,019 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 52 transitions. [2024-11-18 14:28:34,019 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 17 states have (on average 2.0) internal successors, (34), 21 states have internal predecessors, (34), 10 states have call successors, (10), 2 states have call predecessors, (10), 10 states have return successors, (13), 13 states have call predecessors, (13), 10 states have call successors, (13) [2024-11-18 14:28:34,019 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 52 transitions. [2024-11-18 14:28:34,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 176 [2024-11-18 14:28:34,021 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:34,021 INFO L215 NwaCegarLoop]: trace histogram [28, 28, 24, 24, 24, 5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:34,042 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-18 14:28:34,222 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:34,222 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:34,223 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:34,223 INFO L85 PathProgramCache]: Analyzing trace with hash 1558740752, now seen corresponding path program 1 times [2024-11-18 14:28:34,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:34,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [677928375] [2024-11-18 14:28:34,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:28:34,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:34,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:28:35,450 INFO L134 CoverageAnalysis]: Checked inductivity of 1846 backedges. 12 proven. 24 refuted. 0 times theorem prover too weak. 1810 trivial. 0 not checked. [2024-11-18 14:28:35,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:35,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [677928375] [2024-11-18 14:28:35,451 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [677928375] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:35,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [478749261] [2024-11-18 14:28:35,451 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:28:35,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:35,451 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:35,453 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:35,454 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-18 14:28:35,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:28:35,668 INFO L255 TraceCheckSpWp]: Trace formula consists of 730 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-11-18 14:28:35,674 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:35,682 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-18 14:28:36,023 INFO L134 CoverageAnalysis]: Checked inductivity of 1846 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 1822 trivial. 0 not checked. [2024-11-18 14:28:36,023 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:37,835 INFO L134 CoverageAnalysis]: Checked inductivity of 1846 backedges. 0 proven. 58 refuted. 0 times theorem prover too weak. 1788 trivial. 0 not checked. [2024-11-18 14:28:37,836 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [478749261] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:28:37,836 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:28:37,836 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12, 22] total 40 [2024-11-18 14:28:37,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1101107041] [2024-11-18 14:28:37,837 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:37,837 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 40 states [2024-11-18 14:28:37,837 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:37,838 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2024-11-18 14:28:37,839 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=313, Invalid=1247, Unknown=0, NotChecked=0, Total=1560 [2024-11-18 14:28:37,839 INFO L87 Difference]: Start difference. First operand 46 states and 52 transitions. Second operand has 40 states, 30 states have (on average 1.6666666666666667) internal successors, (50), 34 states have internal predecessors, (50), 17 states have call successors, (17), 7 states have call predecessors, (17), 12 states have return successors, (22), 17 states have call predecessors, (22), 17 states have call successors, (22) [2024-11-18 14:28:38,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:38,073 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2024-11-18 14:28:38,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 14:28:38,073 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 30 states have (on average 1.6666666666666667) internal successors, (50), 34 states have internal predecessors, (50), 17 states have call successors, (17), 7 states have call predecessors, (17), 12 states have return successors, (22), 17 states have call predecessors, (22), 17 states have call successors, (22) Word has length 175 [2024-11-18 14:28:38,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:38,074 INFO L225 Difference]: With dead ends: 49 [2024-11-18 14:28:38,074 INFO L226 Difference]: Without dead ends: 44 [2024-11-18 14:28:38,075 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 380 GetRequests, 333 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 857 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=433, Invalid=1637, Unknown=0, NotChecked=0, Total=2070 [2024-11-18 14:28:38,076 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 18 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 204 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 213 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 204 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:38,076 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 147 Invalid, 213 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 204 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:28:38,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-18 14:28:38,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2024-11-18 14:28:38,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 25 states have (on average 1.12) internal successors, (28), 27 states have internal predecessors, (28), 4 states have call successors, (4), 2 states have call predecessors, (4), 14 states have return successors, (16), 14 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-18 14:28:38,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 48 transitions. [2024-11-18 14:28:38,084 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 48 transitions. Word has length 175 [2024-11-18 14:28:38,084 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:38,084 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 48 transitions. [2024-11-18 14:28:38,085 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 40 states, 30 states have (on average 1.6666666666666667) internal successors, (50), 34 states have internal predecessors, (50), 17 states have call successors, (17), 7 states have call predecessors, (17), 12 states have return successors, (22), 17 states have call predecessors, (22), 17 states have call successors, (22) [2024-11-18 14:28:38,085 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 48 transitions. [2024-11-18 14:28:38,087 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 258 [2024-11-18 14:28:38,087 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:38,087 INFO L215 NwaCegarLoop]: trace histogram [42, 42, 36, 36, 36, 7, 7, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:38,101 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-18 14:28:38,288 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:38,288 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:38,289 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:38,289 INFO L85 PathProgramCache]: Analyzing trace with hash 33299286, now seen corresponding path program 6 times [2024-11-18 14:28:38,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:38,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1356398835] [2024-11-18 14:28:38,289 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 14:28:38,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:38,476 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 40 check-sat command(s) [2024-11-18 14:28:38,476 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:39,851 INFO L134 CoverageAnalysis]: Checked inductivity of 4203 backedges. 984 proven. 34 refuted. 0 times theorem prover too weak. 3185 trivial. 0 not checked. [2024-11-18 14:28:39,852 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:39,853 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1356398835] [2024-11-18 14:28:39,853 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1356398835] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:39,853 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [418410821] [2024-11-18 14:28:39,853 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 14:28:39,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:39,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:39,855 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:39,856 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-18 14:28:44,009 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 40 check-sat command(s) [2024-11-18 14:28:44,010 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:44,022 INFO L255 TraceCheckSpWp]: Trace formula consists of 1006 conjuncts, 160 conjuncts are in the unsatisfiable core [2024-11-18 14:28:44,030 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:44,122 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-18 14:28:44,361 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-18 14:28:44,420 INFO L134 CoverageAnalysis]: Checked inductivity of 4203 backedges. 1193 proven. 181 refuted. 0 times theorem prover too weak. 2829 trivial. 0 not checked. [2024-11-18 14:28:44,421 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:45,396 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 21 [2024-11-18 14:28:45,918 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 21 [2024-11-18 14:28:46,360 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 21 [2024-11-18 14:28:46,716 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 21 [2024-11-18 14:28:47,008 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 21 [2024-11-18 14:28:47,650 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [418410821] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:47,650 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 14:28:47,650 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 18] total 25 [2024-11-18 14:28:47,651 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1238182607] [2024-11-18 14:28:47,651 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:47,651 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-18 14:28:47,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:47,652 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-18 14:28:47,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=737, Unknown=0, NotChecked=0, Total=812 [2024-11-18 14:28:47,652 INFO L87 Difference]: Start difference. First operand 44 states and 48 transitions. Second operand has 25 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 25 states have internal predecessors, (44), 10 states have call successors, (12), 2 states have call predecessors, (12), 11 states have return successors, (17), 12 states have call predecessors, (17), 10 states have call successors, (17) [2024-11-18 14:28:48,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:48,124 INFO L93 Difference]: Finished difference Result 49 states and 53 transitions. [2024-11-18 14:28:48,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-18 14:28:48,125 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 25 states have internal predecessors, (44), 10 states have call successors, (12), 2 states have call predecessors, (12), 11 states have return successors, (17), 12 states have call predecessors, (17), 10 states have call successors, (17) Word has length 257 [2024-11-18 14:28:48,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:48,126 INFO L225 Difference]: With dead ends: 49 [2024-11-18 14:28:48,127 INFO L226 Difference]: Without dead ends: 46 [2024-11-18 14:28:48,127 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 335 GetRequests, 295 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 260 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=200, Invalid=1522, Unknown=0, NotChecked=0, Total=1722 [2024-11-18 14:28:48,128 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 26 mSDsluCounter, 256 mSDsCounter, 0 mSdLazyCounter, 365 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 276 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 365 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:48,128 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 276 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 365 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 14:28:48,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-18 14:28:48,137 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2024-11-18 14:28:48,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 25 states have (on average 1.08) internal successors, (27), 27 states have internal predecessors, (27), 4 states have call successors, (4), 2 states have call predecessors, (4), 14 states have return successors, (16), 14 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-18 14:28:48,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 47 transitions. [2024-11-18 14:28:48,138 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 47 transitions. Word has length 257 [2024-11-18 14:28:48,139 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:48,139 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 47 transitions. [2024-11-18 14:28:48,139 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 21 states have (on average 2.0952380952380953) internal successors, (44), 25 states have internal predecessors, (44), 10 states have call successors, (12), 2 states have call predecessors, (12), 11 states have return successors, (17), 12 states have call predecessors, (17), 10 states have call successors, (17) [2024-11-18 14:28:48,139 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 47 transitions. [2024-11-18 14:28:48,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 258 [2024-11-18 14:28:48,143 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:28:48,143 INFO L215 NwaCegarLoop]: trace histogram [42, 42, 36, 36, 36, 7, 7, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:28:48,167 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-18 14:28:48,343 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:48,344 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:28:48,344 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:28:48,344 INFO L85 PathProgramCache]: Analyzing trace with hash 33301208, now seen corresponding path program 2 times [2024-11-18 14:28:48,344 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:28:48,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1138394913] [2024-11-18 14:28:48,344 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:28:48,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:28:48,395 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:28:48,395 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:49,213 INFO L134 CoverageAnalysis]: Checked inductivity of 4203 backedges. 38 proven. 6 refuted. 0 times theorem prover too weak. 4159 trivial. 0 not checked. [2024-11-18 14:28:49,213 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:28:49,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1138394913] [2024-11-18 14:28:49,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1138394913] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:49,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2085954627] [2024-11-18 14:28:49,214 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:28:49,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:28:49,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:28:49,216 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:28:49,217 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-18 14:28:49,563 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:28:49,563 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:28:49,568 INFO L255 TraceCheckSpWp]: Trace formula consists of 1054 conjuncts, 69 conjuncts are in the unsatisfiable core [2024-11-18 14:28:49,576 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:28:49,786 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 36 treesize of output 13 [2024-11-18 14:28:49,867 INFO L134 CoverageAnalysis]: Checked inductivity of 4203 backedges. 1186 proven. 18 refuted. 0 times theorem prover too weak. 2999 trivial. 0 not checked. [2024-11-18 14:28:49,867 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:28:50,908 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-18 14:28:50,908 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 32 [2024-11-18 14:28:51,275 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-18 14:28:51,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 32 [2024-11-18 14:28:51,575 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-18 14:28:51,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 32 [2024-11-18 14:28:51,794 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-18 14:28:51,794 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 32 [2024-11-18 14:28:51,953 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-18 14:28:51,954 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 32 [2024-11-18 14:28:52,392 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2085954627] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:28:52,392 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 14:28:52,392 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 16 [2024-11-18 14:28:52,392 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1461479417] [2024-11-18 14:28:52,393 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 14:28:52,393 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 14:28:52,393 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:28:52,394 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 14:28:52,394 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-18 14:28:52,394 INFO L87 Difference]: Start difference. First operand 44 states and 47 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 14 states have internal predecessors, (29), 5 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-18 14:28:56,546 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-18 14:28:56,637 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:28:56,637 INFO L93 Difference]: Finished difference Result 48 states and 51 transitions. [2024-11-18 14:28:56,638 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 14:28:56,638 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 14 states have internal predecessors, (29), 5 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) Word has length 257 [2024-11-18 14:28:56,638 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:28:56,639 INFO L225 Difference]: With dead ends: 48 [2024-11-18 14:28:56,639 INFO L226 Difference]: Without dead ends: 0 [2024-11-18 14:28:56,639 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 313 GetRequests, 286 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 142 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=131, Invalid=625, Unknown=0, NotChecked=0, Total=756 [2024-11-18 14:28:56,640 INFO L432 NwaCegarLoop]: 7 mSDtfsCounter, 15 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 8 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:28:56,641 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 37 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 185 Invalid, 3 Unknown, 0 Unchecked, 4.1s Time] [2024-11-18 14:28:56,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-18 14:28:56,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-18 14:28:56,642 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-11-18 14:28:56,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-18 14:28:56,642 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 257 [2024-11-18 14:28:56,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:28:56,642 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-18 14:28:56,642 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 14 states have internal predecessors, (29), 5 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-18 14:28:56,642 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-18 14:28:56,643 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-18 14:28:56,645 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-18 14:28:56,661 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-11-18 14:28:56,845 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,SelfDestructingSolverStorable9 [2024-11-18 14:28:56,848 INFO L407 BasicCegarLoop]: Path program histogram: [6, 2, 1, 1] [2024-11-18 14:28:56,850 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-18 14:28:58,037 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-18 14:28:58,044 WARN L156 FloydHoareUtils]: Requires clause for func_to_recursive_line_20_to_21_0 contained old-variable. Original clause: (and (= (select (select |old(#memory_int#1)| |func_to_recursive_line_20_to_21_0_#in~b.base|) |func_to_recursive_line_20_to_21_0_#in~b.offset|) 6) (= |#memory_int#2| |old(#memory_int#2)|) (= |#memory_int#1| |old(#memory_int#1)|)) Eliminated clause: (= 6 (select (select |#memory_int#1| |func_to_recursive_line_20_to_21_0_#in~b.base|) |func_to_recursive_line_20_to_21_0_#in~b.offset|)) [2024-11-18 14:28:58,055 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,056 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] [2024-11-18 14:28:58,056 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] [2024-11-18 14:28:58,057 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,057 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array UnaryExpression[OLD,IdentifierExpression[#memory_int#1,GLOBAL]] [2024-11-18 14:28:58,057 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[UnaryExpression[OLD,IdentifierExpression[#memory_int#1,GLOBAL]],[IdentifierExpression[#in~b!base,]]] [2024-11-18 14:28:58,057 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#2 [2024-11-18 14:28:58,058 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#2,GLOBAL] [2024-11-18 14:28:58,058 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#2,GLOBAL],[IdentifierExpression[#in~a!base,]]] [2024-11-18 14:28:58,058 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#2 [2024-11-18 14:28:58,058 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#2 [2024-11-18 14:28:58,058 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,058 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,059 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,059 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] [2024-11-18 14:28:58,059 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] [2024-11-18 14:28:58,059 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#2 [2024-11-18 14:28:58,059 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#2,GLOBAL] [2024-11-18 14:28:58,059 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#2,GLOBAL],[IdentifierExpression[#in~a!base,]]] [2024-11-18 14:28:58,063 WARN L156 FloydHoareUtils]: Requires clause for func_to_recursive_line_21_to_21_0 contained old-variable. Original clause: (and (= |#memory_int#1| |old(#memory_int#1)|) (exists ((|v_func_to_recursive_line_20_to_21_0_#in~a.offset_BEFORE_CALL_47| Int) (|v_func_to_recursive_line_20_to_21_0_#in~a.base_BEFORE_CALL_47| Int)) (<= (select (select |#memory_int#2| |v_func_to_recursive_line_20_to_21_0_#in~a.base_BEFORE_CALL_47|) |v_func_to_recursive_line_20_to_21_0_#in~a.offset_BEFORE_CALL_47|) 5))) Eliminated clause: (exists ((|v_func_to_recursive_line_20_to_21_0_#in~a.offset_BEFORE_CALL_47| Int) (|v_func_to_recursive_line_20_to_21_0_#in~a.base_BEFORE_CALL_47| Int)) (<= (select (select |#memory_int#2| |v_func_to_recursive_line_20_to_21_0_#in~a.base_BEFORE_CALL_47|) |v_func_to_recursive_line_20_to_21_0_#in~a.offset_BEFORE_CALL_47|) 5)) [2024-11-18 14:28:58,066 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Expression type not yet supported in backtranslation: QuantifierExpression [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Expression type not yet supported in backtranslation: QuantifierExpression [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] [2024-11-18 14:28:58,067 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,068 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#1 [2024-11-18 14:28:58,068 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.11 02:28:58 BoogieIcfgContainer [2024-11-18 14:28:58,068 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-18 14:28:58,069 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-18 14:28:58,069 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-18 14:28:58,070 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-18 14:28:58,070 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:28:18" (3/4) ... [2024-11-18 14:28:58,072 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-18 14:28:58,076 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure func_to_recursive_line_20_to_21_0 [2024-11-18 14:28:58,077 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure func_to_recursive_line_21_to_21_0 [2024-11-18 14:28:58,081 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2024-11-18 14:28:58,081 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2024-11-18 14:28:58,082 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-18 14:28:58,082 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-18 14:28:58,165 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-18 14:28:58,166 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-18 14:28:58,166 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-18 14:28:58,167 INFO L158 Benchmark]: Toolchain (without parser) took 40167.52ms. Allocated memory was 172.0MB in the beginning and 685.8MB in the end (delta: 513.8MB). Free memory was 138.0MB in the beginning and 494.6MB in the end (delta: -356.6MB). Peak memory consumption was 158.7MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,167 INFO L158 Benchmark]: CDTParser took 0.20ms. Allocated memory is still 172.0MB. Free memory is still 139.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-18 14:28:58,167 INFO L158 Benchmark]: CACSL2BoogieTranslator took 235.67ms. Allocated memory is still 172.0MB. Free memory was 138.0MB in the beginning and 125.7MB in the end (delta: 12.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,167 INFO L158 Benchmark]: Boogie Procedure Inliner took 27.26ms. Allocated memory is still 172.0MB. Free memory was 125.7MB in the beginning and 124.2MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,168 INFO L158 Benchmark]: Boogie Preprocessor took 38.62ms. Allocated memory is still 172.0MB. Free memory was 124.2MB in the beginning and 122.1MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,168 INFO L158 Benchmark]: RCFGBuilder took 385.76ms. Allocated memory is still 172.0MB. Free memory was 122.1MB in the beginning and 110.2MB in the end (delta: 12.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,168 INFO L158 Benchmark]: TraceAbstraction took 39376.42ms. Allocated memory was 172.0MB in the beginning and 685.8MB in the end (delta: 513.8MB). Free memory was 109.6MB in the beginning and 498.8MB in the end (delta: -389.3MB). Peak memory consumption was 125.1MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,169 INFO L158 Benchmark]: Witness Printer took 97.06ms. Allocated memory is still 685.8MB. Free memory was 498.8MB in the beginning and 494.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-18 14:28:58,170 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.20ms. Allocated memory is still 172.0MB. Free memory is still 139.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 235.67ms. Allocated memory is still 172.0MB. Free memory was 138.0MB in the beginning and 125.7MB in the end (delta: 12.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 27.26ms. Allocated memory is still 172.0MB. Free memory was 125.7MB in the beginning and 124.2MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 38.62ms. Allocated memory is still 172.0MB. Free memory was 124.2MB in the beginning and 122.1MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 385.76ms. Allocated memory is still 172.0MB. Free memory was 122.1MB in the beginning and 110.2MB in the end (delta: 12.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 39376.42ms. Allocated memory was 172.0MB in the beginning and 685.8MB in the end (delta: 513.8MB). Free memory was 109.6MB in the beginning and 498.8MB in the end (delta: -389.3MB). Peak memory consumption was 125.1MB. Max. memory is 16.1GB. * Witness Printer took 97.06ms. Allocated memory is still 685.8MB. Free memory was 498.8MB in the beginning and 494.6MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array UnaryExpression[OLD,IdentifierExpression[#memory_int#1,GLOBAL]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[UnaryExpression[OLD,IdentifierExpression[#memory_int#1,GLOBAL]],[IdentifierExpression[#in~b!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#2 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#2,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#2,GLOBAL],[IdentifierExpression[#in~a!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#2 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#2 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#2 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#2,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#2,GLOBAL],[IdentifierExpression[#in~a!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Expression type not yet supported in backtranslation: QuantifierExpression - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Expression type not yet supported in backtranslation: QuantifierExpression - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#1,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#1,GLOBAL],[IdentifierExpression[#in~b!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#1 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 69]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 24 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 38.1s, OverallIterations: 10, TraceHistogramMax: 42, PathProgramHistogramMax: 6, EmptinessCheckTime: 0.0s, AutomataDifference: 6.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 3 mSolverCounterUnknown, 198 SdHoareTripleChecker+Valid, 5.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 193 mSDsluCounter, 1287 SdHoareTripleChecker+Invalid, 5.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1143 mSDsCounter, 111 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1729 IncrementalHoareTripleChecker+Invalid, 1843 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 111 mSolverCounterUnsat, 144 mSDtfsCounter, 1729 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1909 GetRequests, 1615 SyntacticMatches, 9 SemanticMatches, 285 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3211 ImplicationChecksByTransitivity, 4.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=46occurred in iteration=7, InterpolantAutomatonStates: 120, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 10 MinimizatonAttempts, 4 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.3s SsaConstructionTime, 5.5s SatisfiabilityAnalysisTime, 23.0s InterpolantComputationTime, 2337 NumberOfCodeBlocks, 2247 NumberOfCodeBlocksAsserted, 142 NumberOfCheckSat, 2777 ConstructedInterpolants, 34 QuantifiedInterpolants, 9623 SizeOfPredicates, 107 NumberOfNonLiveVariables, 4694 ConjunctsInSsa, 535 ConjunctsInUnsatCore, 23 InterpolantComputations, 2 PerfectInterpolantSequences, 28594/29796 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2024-11-18 14:28:58,208 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE