./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive-simple/id_i15_o15-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursive-simple/id_i15_o15-1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ --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 Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 715908359373978289cc76ce2f00faf49f4d4a3c6ddae64771646fc969bea981 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 04:57:29,100 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 04:57:29,220 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 04:57:29,227 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 04:57:29,228 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 04:57:29,268 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 04:57:29,269 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 04:57:29,270 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 04:57:29,271 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 04:57:29,276 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 04:57:29,277 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 04:57:29,278 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 04:57:29,278 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 04:57:29,280 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 04:57:29,281 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 04:57:29,281 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 04:57:29,282 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 04:57:29,282 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 04:57:29,283 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 04:57:29,283 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 04:57:29,284 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 04:57:29,285 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 04:57:29,286 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 04:57:29,287 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 04:57:29,287 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 04:57:29,288 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 04:57:29,288 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 04:57:29,289 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 04:57:29,289 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 04:57:29,290 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 04:57:29,291 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 04:57:29,292 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 04:57:29,292 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 04:57:29,293 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 04:57:29,293 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 04:57:29,293 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 04:57:29,294 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:57:29,294 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 04:57:29,294 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 04:57:29,295 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 04:57:29,295 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 04:57:29,295 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 04:57:29,296 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 04:57:29,296 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 04:57:29,297 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 04:57:29,297 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/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 -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ 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 -> Taipan 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 -> 715908359373978289cc76ce2f00faf49f4d4a3c6ddae64771646fc969bea981 [2023-11-19 04:57:29,649 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 04:57:29,684 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 04:57:29,687 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 04:57:29,688 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 04:57:29,689 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 04:57:29,691 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/recursive-simple/id_i15_o15-1.c [2023-11-19 04:57:32,841 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 04:57:33,116 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 04:57:33,116 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/sv-benchmarks/c/recursive-simple/id_i15_o15-1.c [2023-11-19 04:57:33,124 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/data/e8da6e42d/6d9f5dea224e4c77ab66f3f2807261a3/FLAG075d69811 [2023-11-19 04:57:33,140 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/data/e8da6e42d/6d9f5dea224e4c77ab66f3f2807261a3 [2023-11-19 04:57:33,143 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 04:57:33,145 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 04:57:33,146 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 04:57:33,146 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 04:57:33,152 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 04:57:33,153 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,154 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@22232244 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33, skipping insertion in model container [2023-11-19 04:57:33,154 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,176 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 04:57:33,348 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/sv-benchmarks/c/recursive-simple/id_i15_o15-1.c[454,467] [2023-11-19 04:57:33,354 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:57:33,371 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 04:57:33,390 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/sv-benchmarks/c/recursive-simple/id_i15_o15-1.c[454,467] [2023-11-19 04:57:33,391 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 04:57:33,406 INFO L206 MainTranslator]: Completed translation [2023-11-19 04:57:33,407 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33 WrapperNode [2023-11-19 04:57:33,407 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 04:57:33,408 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 04:57:33,409 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 04:57:33,409 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 04:57:33,417 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,426 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,441 INFO L138 Inliner]: procedures = 13, calls = 9, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 18 [2023-11-19 04:57:33,441 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 04:57:33,442 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 04:57:33,442 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 04:57:33,442 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 04:57:33,451 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,452 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,453 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,453 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,456 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,457 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,458 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,459 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,460 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 04:57:33,461 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 04:57:33,462 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 04:57:33,462 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 04:57:33,463 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (1/1) ... [2023-11-19 04:57:33,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 04:57:33,482 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:57:33,496 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 04:57:33,507 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 04:57:33,536 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 04:57:33,536 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 04:57:33,536 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 04:57:33,537 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 04:57:33,537 INFO L130 BoogieDeclarations]: Found specification of procedure id [2023-11-19 04:57:33,537 INFO L138 BoogieDeclarations]: Found implementation of procedure id [2023-11-19 04:57:33,604 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 04:57:33,611 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 04:57:33,724 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 04:57:33,742 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 04:57:33,742 INFO L302 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-19 04:57:33,747 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:57:33 BoogieIcfgContainer [2023-11-19 04:57:33,748 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 04:57:33,751 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 04:57:33,751 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 04:57:33,754 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 04:57:33,755 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 04:57:33" (1/3) ... [2023-11-19 04:57:33,756 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@579b68 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:57:33, skipping insertion in model container [2023-11-19 04:57:33,756 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 04:57:33" (2/3) ... [2023-11-19 04:57:33,757 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@579b68 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 04:57:33, skipping insertion in model container [2023-11-19 04:57:33,757 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:57:33" (3/3) ... [2023-11-19 04:57:33,758 INFO L112 eAbstractionObserver]: Analyzing ICFG id_i15_o15-1.c [2023-11-19 04:57:33,781 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 04:57:33,782 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 04:57:33,833 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 04:57:33,841 INFO L357 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, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, 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;@6f3ab39b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 04:57:33,841 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 04:57:33,845 INFO L276 IsEmpty]: Start isEmpty. Operand has 14 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 10 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 04:57:33,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-11-19 04:57:33,852 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:57:33,852 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:57:33,853 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:57:33,857 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:57:33,858 INFO L85 PathProgramCache]: Analyzing trace with hash 1493244868, now seen corresponding path program 1 times [2023-11-19 04:57:33,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:57:33,869 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [924484268] [2023-11-19 04:57:33,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:33,870 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:57:34,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:34,261 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 04:57:34,262 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:57:34,265 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [924484268] [2023-11-19 04:57:34,266 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [924484268] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:57:34,266 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 04:57:34,267 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-19 04:57:34,268 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [559271714] [2023-11-19 04:57:34,270 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:57:34,277 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 04:57:34,278 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:57:34,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 04:57:34,328 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 04:57:34,330 INFO L87 Difference]: Start difference. First operand has 14 states, 9 states have (on average 1.3333333333333333) internal successors, (12), 10 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 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) [2023-11-19 04:57:34,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:57:34,451 INFO L93 Difference]: Finished difference Result 22 states and 25 transitions. [2023-11-19 04:57:34,453 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 04:57:34,454 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 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 9 [2023-11-19 04:57:34,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:57:34,463 INFO L225 Difference]: With dead ends: 22 [2023-11-19 04:57:34,463 INFO L226 Difference]: Without dead ends: 14 [2023-11-19 04:57:34,466 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-19 04:57:34,472 INFO L413 NwaCegarLoop]: 9 mSDtfsCounter, 9 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 23 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:57:34,474 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 23 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:57:34,492 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2023-11-19 04:57:34,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2023-11-19 04:57:34,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 9 states have (on average 1.1111111111111112) internal successors, (10), 10 states have internal predecessors, (10), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-19 04:57:34,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 15 transitions. [2023-11-19 04:57:34,530 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 15 transitions. Word has length 9 [2023-11-19 04:57:34,531 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:57:34,532 INFO L495 AbstractCegarLoop]: Abstraction has 14 states and 15 transitions. [2023-11-19 04:57:34,532 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 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) [2023-11-19 04:57:34,533 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 15 transitions. [2023-11-19 04:57:34,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2023-11-19 04:57:34,535 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:57:34,536 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:57:34,536 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 04:57:34,537 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:57:34,538 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:57:34,538 INFO L85 PathProgramCache]: Analyzing trace with hash -642736818, now seen corresponding path program 1 times [2023-11-19 04:57:34,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:57:34,539 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [667704586] [2023-11-19 04:57:34,539 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:34,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:57:34,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:34,805 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-19 04:57:34,805 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:57:34,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [667704586] [2023-11-19 04:57:34,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [667704586] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:57:34,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [968494298] [2023-11-19 04:57:34,806 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:34,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:34,807 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:57:34,809 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:57:34,821 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 04:57:34,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:34,897 INFO L262 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-19 04:57:34,902 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:57:35,061 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-19 04:57:35,061 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:57:35,299 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-19 04:57:35,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [968494298] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:57:35,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [748659328] [2023-11-19 04:57:35,321 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 04:57:35,322 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:57:35,326 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:57:35,328 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:57:35,328 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6, 7] total 14 [2023-11-19 04:57:35,329 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1474701586] [2023-11-19 04:57:35,330 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:57:35,331 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 04:57:35,331 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:57:35,332 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 04:57:35,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2023-11-19 04:57:35,333 INFO L87 Difference]: Start difference. First operand 14 states and 15 transitions. Second operand has 14 states, 11 states have (on average 2.090909090909091) internal successors, (23), 13 states have internal predecessors, (23), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (6), 3 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-19 04:57:35,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:57:35,441 INFO L93 Difference]: Finished difference Result 33 states and 40 transitions. [2023-11-19 04:57:35,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-19 04:57:35,442 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 2.090909090909091) internal successors, (23), 13 states have internal predecessors, (23), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (6), 3 states have call predecessors, (6), 6 states have call successors, (6) Word has length 15 [2023-11-19 04:57:35,442 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:57:35,444 INFO L225 Difference]: With dead ends: 33 [2023-11-19 04:57:35,444 INFO L226 Difference]: Without dead ends: 29 [2023-11-19 04:57:35,445 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=101, Invalid=241, Unknown=0, NotChecked=0, Total=342 [2023-11-19 04:57:35,446 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 26 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 04:57:35,447 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 33 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 04:57:35,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-11-19 04:57:35,455 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 26. [2023-11-19 04:57:35,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 17 states have (on average 1.1176470588235294) internal successors, (19), 18 states have internal predecessors, (19), 3 states have call successors, (3), 2 states have call predecessors, (3), 5 states have return successors, (6), 5 states have call predecessors, (6), 3 states have call successors, (6) [2023-11-19 04:57:35,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 28 transitions. [2023-11-19 04:57:35,457 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 28 transitions. Word has length 15 [2023-11-19 04:57:35,457 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:57:35,457 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 28 transitions. [2023-11-19 04:57:35,458 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 2.090909090909091) internal successors, (23), 13 states have internal predecessors, (23), 6 states have call successors, (6), 1 states have call predecessors, (6), 4 states have return successors, (6), 3 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-19 04:57:35,458 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 28 transitions. [2023-11-19 04:57:35,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-11-19 04:57:35,459 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:57:35,460 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:57:35,486 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-19 04:57:35,681 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:35,682 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:57:35,682 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:57:35,683 INFO L85 PathProgramCache]: Analyzing trace with hash -1269749436, now seen corresponding path program 2 times [2023-11-19 04:57:35,683 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:57:35,683 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1607081286] [2023-11-19 04:57:35,683 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:35,684 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:57:35,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:35,968 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 5 proven. 33 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-19 04:57:35,968 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:57:35,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1607081286] [2023-11-19 04:57:35,969 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1607081286] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:57:35,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1380791875] [2023-11-19 04:57:35,970 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:57:35,970 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:35,970 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:57:35,971 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:57:36,005 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 04:57:36,057 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2023-11-19 04:57:36,058 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:57:36,060 INFO L262 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 04:57:36,065 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:57:36,192 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-11-19 04:57:36,192 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:57:37,355 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-11-19 04:57:37,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1380791875] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:57:37,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1715248843] [2023-11-19 04:57:37,359 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 04:57:37,359 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:57:37,360 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:57:37,360 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:57:37,360 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 13] total 20 [2023-11-19 04:57:37,361 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [502825886] [2023-11-19 04:57:37,361 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:57:37,361 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-11-19 04:57:37,362 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:57:37,363 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-11-19 04:57:37,363 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=286, Unknown=0, NotChecked=0, Total=380 [2023-11-19 04:57:37,364 INFO L87 Difference]: Start difference. First operand 26 states and 28 transitions. Second operand has 20 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 19 states have internal predecessors, (36), 10 states have call successors, (10), 1 states have call predecessors, (10), 7 states have return successors, (13), 7 states have call predecessors, (13), 10 states have call successors, (13) [2023-11-19 04:57:37,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:57:37,545 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2023-11-19 04:57:37,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-19 04:57:37,546 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 19 states have internal predecessors, (36), 10 states have call successors, (10), 1 states have call predecessors, (10), 7 states have return successors, (13), 7 states have call predecessors, (13), 10 states have call successors, (13) Word has length 33 [2023-11-19 04:57:37,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:57:37,548 INFO L225 Difference]: With dead ends: 48 [2023-11-19 04:57:37,548 INFO L226 Difference]: Without dead ends: 38 [2023-11-19 04:57:37,549 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 54 SyntacticMatches, 5 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=230, Invalid=526, Unknown=0, NotChecked=0, Total=756 [2023-11-19 04:57:37,551 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 45 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:57:37,552 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 50 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:57:37,553 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2023-11-19 04:57:37,558 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 35. [2023-11-19 04:57:37,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 3 states have call successors, (3), 2 states have call predecessors, (3), 8 states have return successors, (9), 8 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-19 04:57:37,560 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 37 transitions. [2023-11-19 04:57:37,560 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 37 transitions. Word has length 33 [2023-11-19 04:57:37,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:57:37,561 INFO L495 AbstractCegarLoop]: Abstraction has 35 states and 37 transitions. [2023-11-19 04:57:37,561 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 19 states have internal predecessors, (36), 10 states have call successors, (10), 1 states have call predecessors, (10), 7 states have return successors, (13), 7 states have call predecessors, (13), 10 states have call successors, (13) [2023-11-19 04:57:37,561 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2023-11-19 04:57:37,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-11-19 04:57:37,563 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:57:37,564 INFO L195 NwaCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:57:37,594 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 04:57:37,782 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:37,782 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:57:37,783 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:57:37,783 INFO L85 PathProgramCache]: Analyzing trace with hash 1466649358, now seen corresponding path program 3 times [2023-11-19 04:57:37,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:57:37,784 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [172852574] [2023-11-19 04:57:37,784 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:37,784 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:57:37,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:38,118 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 11 proven. 90 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2023-11-19 04:57:38,123 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:57:38,123 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [172852574] [2023-11-19 04:57:38,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [172852574] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:57:38,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [973972533] [2023-11-19 04:57:38,124 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:57:38,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:38,125 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:57:38,126 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:57:38,128 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 04:57:38,194 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:57:38,195 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:57:38,196 INFO L262 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 18 conjunts are in the unsatisfiable core [2023-11-19 04:57:38,200 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:57:38,334 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2023-11-19 04:57:38,334 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:57:41,467 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-19 04:57:41,468 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [973972533] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:57:41,468 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2141136021] [2023-11-19 04:57:41,473 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 04:57:41,473 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:57:41,473 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:57:41,474 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:57:41,475 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 19] total 26 [2023-11-19 04:57:41,475 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1753096337] [2023-11-19 04:57:41,475 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:57:41,477 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-11-19 04:57:41,477 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:57:41,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-11-19 04:57:41,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=160, Invalid=490, Unknown=0, NotChecked=0, Total=650 [2023-11-19 04:57:41,481 INFO L87 Difference]: Start difference. First operand 35 states and 37 transitions. Second operand has 26 states, 23 states have (on average 2.0869565217391304) internal successors, (48), 25 states have internal predecessors, (48), 13 states have call successors, (13), 1 states have call predecessors, (13), 10 states have return successors, (19), 10 states have call predecessors, (19), 13 states have call successors, (19) [2023-11-19 04:57:41,770 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:57:41,772 INFO L93 Difference]: Finished difference Result 57 states and 62 transitions. [2023-11-19 04:57:41,773 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-19 04:57:41,773 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 23 states have (on average 2.0869565217391304) internal successors, (48), 25 states have internal predecessors, (48), 13 states have call successors, (13), 1 states have call predecessors, (13), 10 states have return successors, (19), 10 states have call predecessors, (19), 13 states have call successors, (19) Word has length 51 [2023-11-19 04:57:41,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:57:41,776 INFO L225 Difference]: With dead ends: 57 [2023-11-19 04:57:41,777 INFO L226 Difference]: Without dead ends: 47 [2023-11-19 04:57:41,779 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 87 SyntacticMatches, 8 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 401 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=413, Invalid=919, Unknown=0, NotChecked=0, Total=1332 [2023-11-19 04:57:41,780 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 71 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:57:41,784 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 71 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:57:41,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-19 04:57:41,793 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2023-11-19 04:57:41,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 29 states have (on average 1.0689655172413792) internal successors, (31), 30 states have internal predecessors, (31), 3 states have call successors, (3), 2 states have call predecessors, (3), 11 states have return successors, (12), 11 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-19 04:57:41,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 46 transitions. [2023-11-19 04:57:41,802 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 46 transitions. Word has length 51 [2023-11-19 04:57:41,802 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:57:41,802 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 46 transitions. [2023-11-19 04:57:41,803 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 23 states have (on average 2.0869565217391304) internal successors, (48), 25 states have internal predecessors, (48), 13 states have call successors, (13), 1 states have call predecessors, (13), 10 states have return successors, (19), 10 states have call predecessors, (19), 13 states have call successors, (19) [2023-11-19 04:57:41,803 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 46 transitions. [2023-11-19 04:57:41,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2023-11-19 04:57:41,807 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:57:41,808 INFO L195 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:57:41,830 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 04:57:42,022 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:42,023 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:57:42,023 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:57:42,023 INFO L85 PathProgramCache]: Analyzing trace with hash 1904272772, now seen corresponding path program 4 times [2023-11-19 04:57:42,023 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:57:42,023 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1398575805] [2023-11-19 04:57:42,023 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:42,023 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:57:42,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:42,429 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 17 proven. 174 refuted. 0 times theorem prover too weak. 119 trivial. 0 not checked. [2023-11-19 04:57:42,429 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:57:42,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1398575805] [2023-11-19 04:57:42,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1398575805] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:57:42,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1189259808] [2023-11-19 04:57:42,434 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 04:57:42,434 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:42,434 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:57:42,443 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:57:42,457 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 04:57:42,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:42,582 INFO L262 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 24 conjunts are in the unsatisfiable core [2023-11-19 04:57:42,586 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:57:42,714 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 155 trivial. 0 not checked. [2023-11-19 04:57:42,715 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:57:49,456 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 0 proven. 255 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2023-11-19 04:57:49,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1189259808] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:57:49,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1456819320] [2023-11-19 04:57:49,459 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 04:57:49,459 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:57:49,460 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:57:49,460 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:57:49,460 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 15, 25] total 32 [2023-11-19 04:57:49,461 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1893744842] [2023-11-19 04:57:49,461 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:57:49,462 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-11-19 04:57:49,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:57:49,463 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-11-19 04:57:49,464 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=748, Unknown=0, NotChecked=0, Total=992 [2023-11-19 04:57:49,464 INFO L87 Difference]: Start difference. First operand 44 states and 46 transitions. Second operand has 32 states, 29 states have (on average 2.0689655172413794) internal successors, (60), 31 states have internal predecessors, (60), 16 states have call successors, (16), 1 states have call predecessors, (16), 13 states have return successors, (25), 13 states have call predecessors, (25), 16 states have call successors, (25) [2023-11-19 04:57:49,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:57:49,804 INFO L93 Difference]: Finished difference Result 66 states and 71 transitions. [2023-11-19 04:57:49,804 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-19 04:57:49,805 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 29 states have (on average 2.0689655172413794) internal successors, (60), 31 states have internal predecessors, (60), 16 states have call successors, (16), 1 states have call predecessors, (16), 13 states have return successors, (25), 13 states have call predecessors, (25), 16 states have call successors, (25) Word has length 69 [2023-11-19 04:57:49,809 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:57:49,816 INFO L225 Difference]: With dead ends: 66 [2023-11-19 04:57:49,816 INFO L226 Difference]: Without dead ends: 56 [2023-11-19 04:57:49,818 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 120 SyntacticMatches, 11 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 680 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=650, Invalid=1420, Unknown=0, NotChecked=0, Total=2070 [2023-11-19 04:57:49,819 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 174 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 114 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 189 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 114 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-19 04:57:49,820 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [189 Valid, 78 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [114 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-19 04:57:49,821 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2023-11-19 04:57:49,841 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 53. [2023-11-19 04:57:49,842 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 35 states have (on average 1.0571428571428572) internal successors, (37), 36 states have internal predecessors, (37), 3 states have call successors, (3), 2 states have call predecessors, (3), 14 states have return successors, (15), 14 states have call predecessors, (15), 3 states have call successors, (15) [2023-11-19 04:57:49,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 55 transitions. [2023-11-19 04:57:49,845 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 55 transitions. Word has length 69 [2023-11-19 04:57:49,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:57:49,847 INFO L495 AbstractCegarLoop]: Abstraction has 53 states and 55 transitions. [2023-11-19 04:57:49,847 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 29 states have (on average 2.0689655172413794) internal successors, (60), 31 states have internal predecessors, (60), 16 states have call successors, (16), 1 states have call predecessors, (16), 13 states have return successors, (25), 13 states have call predecessors, (25), 16 states have call successors, (25) [2023-11-19 04:57:49,847 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 55 transitions. [2023-11-19 04:57:49,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-11-19 04:57:49,856 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:57:49,856 INFO L195 NwaCegarLoop]: trace histogram [14, 14, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:57:49,882 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 04:57:50,077 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:50,077 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:57:50,078 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:57:50,078 INFO L85 PathProgramCache]: Analyzing trace with hash 1570097358, now seen corresponding path program 5 times [2023-11-19 04:57:50,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:57:50,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [609335518] [2023-11-19 04:57:50,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:57:50,078 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:57:50,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:57:50,843 INFO L134 CoverageAnalysis]: Checked inductivity of 520 backedges. 23 proven. 285 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2023-11-19 04:57:50,843 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:57:50,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [609335518] [2023-11-19 04:57:50,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [609335518] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:57:50,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [734328176] [2023-11-19 04:57:50,843 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 04:57:50,844 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:57:50,844 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:57:50,846 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:57:50,866 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 04:57:51,061 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) [2023-11-19 04:57:51,062 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:57:51,063 INFO L262 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 30 conjunts are in the unsatisfiable core [2023-11-19 04:57:51,074 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:57:51,222 INFO L134 CoverageAnalysis]: Checked inductivity of 520 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 260 trivial. 0 not checked. [2023-11-19 04:57:51,222 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:58:04,682 INFO L134 CoverageAnalysis]: Checked inductivity of 520 backedges. 0 proven. 429 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-19 04:58:04,682 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [734328176] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:58:04,682 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1240139697] [2023-11-19 04:58:04,685 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 04:58:04,685 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:58:04,685 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:58:04,686 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:58:04,687 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18, 31] total 38 [2023-11-19 04:58:04,687 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [843183646] [2023-11-19 04:58:04,687 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:58:04,688 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2023-11-19 04:58:04,688 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:58:04,690 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2023-11-19 04:58:04,691 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=347, Invalid=1059, Unknown=0, NotChecked=0, Total=1406 [2023-11-19 04:58:04,691 INFO L87 Difference]: Start difference. First operand 53 states and 55 transitions. Second operand has 38 states, 35 states have (on average 2.057142857142857) internal successors, (72), 37 states have internal predecessors, (72), 19 states have call successors, (19), 1 states have call predecessors, (19), 16 states have return successors, (31), 16 states have call predecessors, (31), 19 states have call successors, (31) [2023-11-19 04:58:05,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:58:05,039 INFO L93 Difference]: Finished difference Result 69 states and 73 transitions. [2023-11-19 04:58:05,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-11-19 04:58:05,040 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 35 states have (on average 2.057142857142857) internal successors, (72), 37 states have internal predecessors, (72), 19 states have call successors, (19), 1 states have call predecessors, (19), 16 states have return successors, (31), 16 states have call predecessors, (31), 19 states have call successors, (31) Word has length 87 [2023-11-19 04:58:05,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:58:05,042 INFO L225 Difference]: With dead ends: 69 [2023-11-19 04:58:05,042 INFO L226 Difference]: Without dead ends: 62 [2023-11-19 04:58:05,044 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 153 SyntacticMatches, 14 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1015 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=905, Invalid=1957, Unknown=0, NotChecked=0, Total=2862 [2023-11-19 04:58:05,045 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 91 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 162 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:58:05,046 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [108 Valid, 105 Invalid, 162 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:58:05,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2023-11-19 04:58:05,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 59. [2023-11-19 04:58:05,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 39 states have (on average 1.0512820512820513) internal successors, (41), 40 states have internal predecessors, (41), 3 states have call successors, (3), 2 states have call predecessors, (3), 16 states have return successors, (17), 16 states have call predecessors, (17), 3 states have call successors, (17) [2023-11-19 04:58:05,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 61 transitions. [2023-11-19 04:58:05,054 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 61 transitions. Word has length 87 [2023-11-19 04:58:05,055 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:58:05,055 INFO L495 AbstractCegarLoop]: Abstraction has 59 states and 61 transitions. [2023-11-19 04:58:05,055 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 35 states have (on average 2.057142857142857) internal successors, (72), 37 states have internal predecessors, (72), 19 states have call successors, (19), 1 states have call predecessors, (19), 16 states have return successors, (31), 16 states have call predecessors, (31), 19 states have call successors, (31) [2023-11-19 04:58:05,055 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 61 transitions. [2023-11-19 04:58:05,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2023-11-19 04:58:05,057 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:58:05,057 INFO L195 NwaCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:58:05,086 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 04:58:05,278 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-19 04:58:05,279 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:58:05,279 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:58:05,279 INFO L85 PathProgramCache]: Analyzing trace with hash -1758730226, now seen corresponding path program 6 times [2023-11-19 04:58:05,279 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:58:05,279 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1048490764] [2023-11-19 04:58:05,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:58:05,280 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:58:05,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:58:06,407 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2023-11-19 04:58:06,407 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:58:06,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1048490764] [2023-11-19 04:58:06,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1048490764] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:58:06,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1829777033] [2023-11-19 04:58:06,408 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-19 04:58:06,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:58:06,408 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:58:06,413 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:58:06,434 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 04:58:06,806 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-19 04:58:06,806 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 04:58:06,809 INFO L262 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 67 conjunts are in the unsatisfiable core [2023-11-19 04:58:06,812 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:58:06,916 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2023-11-19 04:58:06,916 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 04:58:08,053 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2023-11-19 04:58:08,053 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1829777033] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 04:58:08,053 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2020661743] [2023-11-19 04:58:08,055 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 04:58:08,056 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 04:58:08,056 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:337) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:415) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2023-11-19 04:58:08,056 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-19 04:58:08,056 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 35, 35] total 35 [2023-11-19 04:58:08,057 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1382458383] [2023-11-19 04:58:08,057 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-19 04:58:08,058 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2023-11-19 04:58:08,058 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:58:08,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2023-11-19 04:58:08,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=1123, Unknown=0, NotChecked=0, Total=1190 [2023-11-19 04:58:08,059 INFO L87 Difference]: Start difference. First operand 59 states and 61 transitions. Second operand has 35 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 19 states have internal predecessors, (38), 1 states have call successors, (2), 1 states have call predecessors, (2), 16 states have return successors, (16), 16 states have call predecessors, (16), 1 states have call successors, (16) [2023-11-19 04:58:08,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:58:08,533 INFO L93 Difference]: Finished difference Result 72 states and 75 transitions. [2023-11-19 04:58:08,533 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2023-11-19 04:58:08,534 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 19 states have internal predecessors, (38), 1 states have call successors, (2), 1 states have call predecessors, (2), 16 states have return successors, (16), 16 states have call predecessors, (16), 1 states have call successors, (16) Word has length 99 [2023-11-19 04:58:08,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:58:08,538 INFO L225 Difference]: With dead ends: 72 [2023-11-19 04:58:08,538 INFO L226 Difference]: Without dead ends: 65 [2023-11-19 04:58:08,539 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 231 GetRequests, 198 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=67, Invalid=1123, Unknown=0, NotChecked=0, Total=1190 [2023-11-19 04:58:08,541 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 1047 mSDsCounter, 0 mSdLazyCounter, 804 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 1087 SdHoareTripleChecker+Invalid, 804 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 804 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-19 04:58:08,541 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 1087 Invalid, 804 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 804 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-19 04:58:08,542 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2023-11-19 04:58:08,553 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 62. [2023-11-19 04:58:08,555 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 41 states have (on average 1.048780487804878) internal successors, (43), 42 states have internal predecessors, (43), 3 states have call successors, (3), 2 states have call predecessors, (3), 17 states have return successors, (18), 17 states have call predecessors, (18), 3 states have call successors, (18) [2023-11-19 04:58:08,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 64 transitions. [2023-11-19 04:58:08,559 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 64 transitions. Word has length 99 [2023-11-19 04:58:08,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:58:08,561 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 64 transitions. [2023-11-19 04:58:08,562 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 19 states have internal predecessors, (38), 1 states have call successors, (2), 1 states have call predecessors, (2), 16 states have return successors, (16), 16 states have call predecessors, (16), 1 states have call successors, (16) [2023-11-19 04:58:08,562 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 64 transitions. [2023-11-19 04:58:08,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2023-11-19 04:58:08,569 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 04:58:08,569 INFO L195 NwaCegarLoop]: trace histogram [17, 17, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 04:58:08,592 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 04:58:08,791 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:58:08,792 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 04:58:08,792 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 04:58:08,792 INFO L85 PathProgramCache]: Analyzing trace with hash -1678126652, now seen corresponding path program 7 times [2023-11-19 04:58:08,792 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 04:58:08,792 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1772621190] [2023-11-19 04:58:08,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 04:58:08,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 04:58:08,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:58:09,462 INFO L134 CoverageAnalysis]: Checked inductivity of 784 backedges. 330 proven. 122 refuted. 0 times theorem prover too weak. 332 trivial. 0 not checked. [2023-11-19 04:58:09,463 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 04:58:09,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1772621190] [2023-11-19 04:58:09,463 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1772621190] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 04:58:09,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633569723] [2023-11-19 04:58:09,463 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-19 04:58:09,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:58:09,463 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 04:58:09,464 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 04:58:09,465 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-19 04:58:09,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 04:58:09,794 INFO L262 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 36 conjunts are in the unsatisfiable core [2023-11-19 04:58:09,798 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 04:58:10,017 INFO L134 CoverageAnalysis]: Checked inductivity of 784 backedges. 392 proven. 0 refuted. 0 times theorem prover too weak. 392 trivial. 0 not checked. [2023-11-19 04:58:10,017 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 04:58:10,018 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633569723] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 04:58:10,018 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 04:58:10,018 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [21] imperfect sequences [23] total 26 [2023-11-19 04:58:10,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [461179380] [2023-11-19 04:58:10,019 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 04:58:10,019 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-11-19 04:58:10,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 04:58:10,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-11-19 04:58:10,021 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=195, Invalid=455, Unknown=0, NotChecked=0, Total=650 [2023-11-19 04:58:10,021 INFO L87 Difference]: Start difference. First operand 62 states and 64 transitions. Second operand has 21 states, 20 states have (on average 2.0) internal successors, (40), 20 states have internal predecessors, (40), 2 states have call successors, (2), 1 states have call predecessors, (2), 17 states have return successors, (17), 17 states have call predecessors, (17), 2 states have call successors, (17) [2023-11-19 04:58:10,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 04:58:10,320 INFO L93 Difference]: Finished difference Result 65 states and 68 transitions. [2023-11-19 04:58:10,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-11-19 04:58:10,321 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.0) internal successors, (40), 20 states have internal predecessors, (40), 2 states have call successors, (2), 1 states have call predecessors, (2), 17 states have return successors, (17), 17 states have call predecessors, (17), 2 states have call successors, (17) Word has length 105 [2023-11-19 04:58:10,322 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 04:58:10,322 INFO L225 Difference]: With dead ends: 65 [2023-11-19 04:58:10,322 INFO L226 Difference]: Without dead ends: 0 [2023-11-19 04:58:10,323 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 225 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=555, Invalid=1251, Unknown=0, NotChecked=0, Total=1806 [2023-11-19 04:58:10,324 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 04:58:10,324 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 130 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 04:58:10,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2023-11-19 04:58:10,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2023-11-19 04:58:10,325 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) [2023-11-19 04:58:10,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2023-11-19 04:58:10,325 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 105 [2023-11-19 04:58:10,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 04:58:10,326 INFO L495 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-11-19 04:58:10,326 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.0) internal successors, (40), 20 states have internal predecessors, (40), 2 states have call successors, (2), 1 states have call predecessors, (2), 17 states have return successors, (17), 17 states have call predecessors, (17), 2 states have call successors, (17) [2023-11-19 04:58:10,326 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2023-11-19 04:58:10,326 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2023-11-19 04:58:10,328 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-11-19 04:58:10,347 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-19 04:58:10,542 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 04:58:10,548 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2023-11-19 04:58:10,566 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2023-11-19 04:58:10,566 INFO L899 garLoopResultBuilder]: For program point ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION(line 15) no Hoare annotation was computed. [2023-11-19 04:58:10,566 INFO L899 garLoopResultBuilder]: For program point L15(line 15) no Hoare annotation was computed. [2023-11-19 04:58:10,567 INFO L899 garLoopResultBuilder]: For program point L14(lines 14 16) no Hoare annotation was computed. [2023-11-19 04:58:10,567 INFO L895 garLoopResultBuilder]: At program point L13(line 13) the Hoare annotation is: (= |ULTIMATE.start_main_~input~0#1| 15) [2023-11-19 04:58:10,567 INFO L899 garLoopResultBuilder]: For program point L13-1(line 13) no Hoare annotation was computed. [2023-11-19 04:58:10,567 INFO L899 garLoopResultBuilder]: For program point L11(lines 11 17) no Hoare annotation was computed. [2023-11-19 04:58:10,567 INFO L899 garLoopResultBuilder]: For program point $Ultimate##0(line -1) no Hoare annotation was computed. [2023-11-19 04:58:10,568 INFO L899 garLoopResultBuilder]: For program point idFINAL(lines 6 9) no Hoare annotation was computed. [2023-11-19 04:58:10,568 INFO L899 garLoopResultBuilder]: For program point idEXIT(lines 6 9) no Hoare annotation was computed. [2023-11-19 04:58:10,568 INFO L902 garLoopResultBuilder]: At program point $Ultimate##0(lines 6 9) the Hoare annotation is: true [2023-11-19 04:58:10,568 INFO L895 garLoopResultBuilder]: At program point L8(line 8) the Hoare annotation is: (= |id_#in~x| id_~x) [2023-11-19 04:58:10,568 INFO L899 garLoopResultBuilder]: For program point L7(line 7) no Hoare annotation was computed. [2023-11-19 04:58:10,568 INFO L899 garLoopResultBuilder]: For program point L8-1(line 8) no Hoare annotation was computed. [2023-11-19 04:58:10,572 INFO L445 BasicCegarLoop]: Path program histogram: [7, 1] [2023-11-19 04:58:10,574 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2023-11-19 04:58:10,578 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 19.11 04:58:10 BoogieIcfgContainer [2023-11-19 04:58:10,578 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-11-19 04:58:10,579 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-11-19 04:58:10,579 INFO L270 PluginConnector]: Initializing Witness Printer... [2023-11-19 04:58:10,579 INFO L274 PluginConnector]: Witness Printer initialized [2023-11-19 04:58:10,580 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 04:57:33" (3/4) ... [2023-11-19 04:58:10,582 INFO L137 WitnessPrinter]: Generating witness for correct program [2023-11-19 04:58:10,586 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure id [2023-11-19 04:58:10,590 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2023-11-19 04:58:10,590 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2023-11-19 04:58:10,590 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2023-11-19 04:58:10,590 INFO L943 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2023-11-19 04:58:10,668 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/witness.graphml [2023-11-19 04:58:10,668 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/witness.yml [2023-11-19 04:58:10,668 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-11-19 04:58:10,669 INFO L158 Benchmark]: Toolchain (without parser) took 37524.65ms. Allocated memory was 148.9MB in the beginning and 314.6MB in the end (delta: 165.7MB). Free memory was 114.9MB in the beginning and 268.0MB in the end (delta: -153.2MB). Peak memory consumption was 14.3MB. Max. memory is 16.1GB. [2023-11-19 04:58:10,670 INFO L158 Benchmark]: CDTParser took 0.33ms. Allocated memory is still 113.2MB. Free memory was 79.4MB in the beginning and 79.4MB in the end (delta: 26.4kB). There was no memory consumed. Max. memory is 16.1GB. [2023-11-19 04:58:10,670 INFO L158 Benchmark]: CACSL2BoogieTranslator took 261.45ms. Allocated memory is still 148.9MB. Free memory was 114.9MB in the beginning and 105.0MB in the end (delta: 9.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-11-19 04:58:10,670 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.97ms. Allocated memory is still 148.9MB. Free memory was 104.4MB in the beginning and 103.5MB in the end (delta: 874.2kB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-11-19 04:58:10,671 INFO L158 Benchmark]: Boogie Preprocessor took 18.57ms. Allocated memory is still 148.9MB. Free memory was 103.5MB in the beginning and 102.2MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2023-11-19 04:58:10,671 INFO L158 Benchmark]: RCFGBuilder took 286.53ms. Allocated memory is still 148.9MB. Free memory was 102.2MB in the beginning and 93.0MB in the end (delta: 9.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-11-19 04:58:10,671 INFO L158 Benchmark]: TraceAbstraction took 36827.96ms. Allocated memory was 148.9MB in the beginning and 314.6MB in the end (delta: 165.7MB). Free memory was 92.4MB in the beginning and 272.2MB in the end (delta: -179.8MB). There was no memory consumed. Max. memory is 16.1GB. [2023-11-19 04:58:10,672 INFO L158 Benchmark]: Witness Printer took 89.62ms. Allocated memory is still 314.6MB. Free memory was 272.2MB in the beginning and 268.0MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2023-11-19 04:58:10,674 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.33ms. Allocated memory is still 113.2MB. Free memory was 79.4MB in the beginning and 79.4MB in the end (delta: 26.4kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 261.45ms. Allocated memory is still 148.9MB. Free memory was 114.9MB in the beginning and 105.0MB in the end (delta: 9.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 32.97ms. Allocated memory is still 148.9MB. Free memory was 104.4MB in the beginning and 103.5MB in the end (delta: 874.2kB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 18.57ms. Allocated memory is still 148.9MB. Free memory was 103.5MB in the beginning and 102.2MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 286.53ms. Allocated memory is still 148.9MB. Free memory was 102.2MB in the beginning and 93.0MB in the end (delta: 9.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 36827.96ms. Allocated memory was 148.9MB in the beginning and 314.6MB in the end (delta: 165.7MB). Free memory was 92.4MB in the beginning and 272.2MB in the end (delta: -179.8MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 89.62ms. Allocated memory is still 314.6MB. Free memory was 272.2MB in the beginning and 268.0MB 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.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: 15]: 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 2 procedures, 14 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 36.8s, OverallIterations: 8, TraceHistogramMax: 17, PathProgramHistogramMax: 7, EmptinessCheckTime: 0.0s, AutomataDifference: 2.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 482 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 419 mSDsluCounter, 1577 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1457 mSDsCounter, 203 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1323 IncrementalHoareTripleChecker+Invalid, 1526 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 203 mSolverCounterUnsat, 120 mSDtfsCounter, 1323 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1044 GetRequests, 752 SyntacticMatches, 40 SemanticMatches, 252 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2569 ImplicationChecksByTransitivity, 3.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred in iteration=7, InterpolantAutomatonStates: 140, 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, 8 MinimizatonAttempts, 18 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 3 LocationsWithAnnotation, 7 PreInvPairs, 7 NumberOfFragments, 7 HoareAnnotationTreeSize, 7 FomulaSimplifications, 15 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 3 FomulaSimplificationsInter, 13 FormulaSimplificationTreeSizeReductionInter, 0.0s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 30.8s InterpolantComputationTime, 927 NumberOfCodeBlocks, 927 NumberOfCodeBlocksAsserted, 34 NumberOfCheckSat, 1260 ConstructedInterpolants, 0 QuantifiedInterpolants, 3458 SizeOfPredicates, 57 NumberOfNonLiveVariables, 1218 ConjunctsInSsa, 193 ConjunctsInUnsatCore, 21 InterpolantComputations, 2 PerfectInterpolantSequences, 3641/6758 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! [2023-11-19 04:58:10,710 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bee78178-99ac-4938-b446-254cc0fbcc21/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (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